Merge branch 'vendor/GCC47'
[dragonfly.git] / contrib / gcc-4.7 / gcc / sel-sched.c
1 /* Instruction scheduling pass.  Selective scheduler and pipeliner.
2    Copyright (C) 2006, 2007, 2008, 2009, 2010, 2011
3    Free Software Foundation, Inc.
4
5 This file is part of GCC.
6
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
10 version.
11
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15 for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3.  If not see
19 <http://www.gnu.org/licenses/>.  */
20
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "rtl-error.h"
26 #include "tm_p.h"
27 #include "hard-reg-set.h"
28 #include "regs.h"
29 #include "function.h"
30 #include "flags.h"
31 #include "insn-config.h"
32 #include "insn-attr.h"
33 #include "except.h"
34 #include "recog.h"
35 #include "params.h"
36 #include "target.h"
37 #include "output.h"
38 #include "timevar.h"
39 #include "tree-pass.h"
40 #include "sched-int.h"
41 #include "ggc.h"
42 #include "tree.h"
43 #include "vec.h"
44 #include "langhooks.h"
45 #include "rtlhooks-def.h"
46 #include "output.h"
47 #include "emit-rtl.h"
48 #include "ira.h"
49
50 #ifdef INSN_SCHEDULING
51 #include "sel-sched-ir.h"
52 #include "sel-sched-dump.h"
53 #include "sel-sched.h"
54 #include "dbgcnt.h"
55
56 /* Implementation of selective scheduling approach.
57    The below implementation follows the original approach with the following
58    changes:
59
60    o the scheduler works after register allocation (but can be also tuned
61    to work before RA);
62    o some instructions are not copied or register renamed;
63    o conditional jumps are not moved with code duplication;
64    o several jumps in one parallel group are not supported;
65    o when pipelining outer loops, code motion through inner loops
66    is not supported;
67    o control and data speculation are supported;
68    o some improvements for better compile time/performance were made.
69
70    Terminology
71    ===========
72
73    A vinsn, or virtual insn, is an insn with additional data characterizing
74    insn pattern, such as LHS, RHS, register sets used/set/clobbered, etc.
75    Vinsns also act as smart pointers to save memory by reusing them in
76    different expressions.  A vinsn is described by vinsn_t type.
77
78    An expression is a vinsn with additional data characterizing its properties
79    at some point in the control flow graph.  The data may be its usefulness,
80    priority, speculative status, whether it was renamed/subsituted, etc.
81    An expression is described by expr_t type.
82
83    Availability set (av_set) is a set of expressions at a given control flow
84    point. It is represented as av_set_t.  The expressions in av sets are kept
85    sorted in the terms of expr_greater_p function.  It allows to truncate
86    the set while leaving the best expressions.
87
88    A fence is a point through which code motion is prohibited.  On each step,
89    we gather a parallel group of insns at a fence.  It is possible to have
90    multiple fences. A fence is represented via fence_t.
91
92    A boundary is the border between the fence group and the rest of the code.
93    Currently, we never have more than one boundary per fence, as we finalize
94    the fence group when a jump is scheduled. A boundary is represented
95    via bnd_t.
96
97    High-level overview
98    ===================
99
100    The scheduler finds regions to schedule, schedules each one, and finalizes.
101    The regions are formed starting from innermost loops, so that when the inner
102    loop is pipelined, its prologue can be scheduled together with yet unprocessed
103    outer loop. The rest of acyclic regions are found using extend_rgns:
104    the blocks that are not yet allocated to any regions are traversed in top-down
105    order, and a block is added to a region to which all its predecessors belong;
106    otherwise, the block starts its own region.
107
108    The main scheduling loop (sel_sched_region_2) consists of just
109    scheduling on each fence and updating fences.  For each fence,
110    we fill a parallel group of insns (fill_insns) until some insns can be added.
111    First, we compute available exprs (av-set) at the boundary of the current
112    group.  Second, we choose the best expression from it.  If the stall is
113    required to schedule any of the expressions, we advance the current cycle
114    appropriately.  So, the final group does not exactly correspond to a VLIW
115    word.  Third, we move the chosen expression to the boundary (move_op)
116    and update the intermediate av sets and liveness sets.  We quit fill_insns
117    when either no insns left for scheduling or we have scheduled enough insns
118    so we feel like advancing a scheduling point.
119
120    Computing available expressions
121    ===============================
122
123    The computation (compute_av_set) is a bottom-up traversal.  At each insn,
124    we're moving the union of its successors' sets through it via
125    moveup_expr_set.  The dependent expressions are removed.  Local
126    transformations (substitution, speculation) are applied to move more
127    exprs.  Then the expr corresponding to the current insn is added.
128    The result is saved on each basic block header.
129
130    When traversing the CFG, we're moving down for no more than max_ws insns.
131    Also, we do not move down to ineligible successors (is_ineligible_successor),
132    which include moving along a back-edge, moving to already scheduled code,
133    and moving to another fence.  The first two restrictions are lifted during
134    pipelining, which allows us to move insns along a back-edge.  We always have
135    an acyclic region for scheduling because we forbid motion through fences.
136
137    Choosing the best expression
138    ============================
139
140    We sort the final availability set via sel_rank_for_schedule, then we remove
141    expressions which are not yet ready (tick_check_p) or which dest registers
142    cannot be used.  For some of them, we choose another register via
143    find_best_reg.  To do this, we run find_used_regs to calculate the set of
144    registers which cannot be used.  The find_used_regs function performs
145    a traversal of code motion paths for an expr.  We consider for renaming
146    only registers which are from the same regclass as the original one and
147    using which does not interfere with any live ranges.  Finally, we convert
148    the resulting set to the ready list format and use max_issue and reorder*
149    hooks similarly to the Haifa scheduler.
150
151    Scheduling the best expression
152    ==============================
153
154    We run the move_op routine to perform the same type of code motion paths
155    traversal as in find_used_regs.  (These are working via the same driver,
156    code_motion_path_driver.)  When moving down the CFG, we look for original
157    instruction that gave birth to a chosen expression.  We undo
158    the transformations performed on an expression via the history saved in it.
159    When found, we remove the instruction or leave a reg-reg copy/speculation
160    check if needed.  On a way up, we insert bookkeeping copies at each join
161    point.  If a copy is not needed, it will be removed later during this
162    traversal.  We update the saved av sets and liveness sets on the way up, too.
163
164    Finalizing the schedule
165    =======================
166
167    When pipelining, we reschedule the blocks from which insns were pipelined
168    to get a tighter schedule.  On Itanium, we also perform bundling via
169    the same routine from ia64.c.
170
171    Dependence analysis changes
172    ===========================
173
174    We augmented the sched-deps.c with hooks that get called when a particular
175    dependence is found in a particular part of an insn.  Using these hooks, we
176    can do several actions such as: determine whether an insn can be moved through
177    another (has_dependence_p, moveup_expr); find out whether an insn can be
178    scheduled on the current cycle (tick_check_p); find out registers that
179    are set/used/clobbered by an insn and find out all the strange stuff that
180    restrict its movement, like SCHED_GROUP_P or CANT_MOVE (done in
181    init_global_and_expr_for_insn).
182
183    Initialization changes
184    ======================
185
186    There are parts of haifa-sched.c, sched-deps.c, and sched-rgn.c that are
187    reused in all of the schedulers.  We have split up the initialization of data
188    of such parts into different functions prefixed with scheduler type and
189    postfixed with the type of data initialized: {,sel_,haifa_}sched_{init,finish},
190    sched_rgn_init/finish, sched_deps_init/finish, sched_init_{luids/bbs}, etc.
191    The same splitting is done with current_sched_info structure:
192    dependence-related parts are in sched_deps_info, common part is in
193    common_sched_info, and haifa/sel/etc part is in current_sched_info.
194
195    Target contexts
196    ===============
197
198    As we now have multiple-point scheduling, this would not work with backends
199    which save some of the scheduler state to use it in the target hooks.
200    For this purpose, we introduce a concept of target contexts, which
201    encapsulate such information.  The backend should implement simple routines
202    of allocating/freeing/setting such a context.  The scheduler calls these
203    as target hooks and handles the target context as an opaque pointer (similar
204    to the DFA state type, state_t).
205
206    Various speedups
207    ================
208
209    As the correct data dependence graph is not supported during scheduling (which
210    is to be changed in mid-term), we cache as much of the dependence analysis
211    results as possible to avoid reanalyzing.  This includes: bitmap caches on
212    each insn in stream of the region saying yes/no for a query with a pair of
213    UIDs; hashtables with the previously done transformations on each insn in
214    stream; a vector keeping a history of transformations on each expr.
215
216    Also, we try to minimize the dependence context used on each fence to check
217    whether the given expression is ready for scheduling by removing from it
218    insns that are definitely completed the execution.  The results of
219    tick_check_p checks are also cached in a vector on each fence.
220
221    We keep a valid liveness set on each insn in a region to avoid the high
222    cost of recomputation on large basic blocks.
223
224    Finally, we try to minimize the number of needed updates to the availability
225    sets.  The updates happen in two cases: when fill_insns terminates,
226    we advance all fences and increase the stage number to show that the region
227    has changed and the sets are to be recomputed; and when the next iteration
228    of a loop in fill_insns happens (but this one reuses the saved av sets
229    on bb headers.)  Thus, we try to break the fill_insns loop only when
230    "significant" number of insns from the current scheduling window was
231    scheduled.  This should be made a target param.
232
233
234    TODO: correctly support the data dependence graph at all stages and get rid
235    of all caches.  This should speed up the scheduler.
236    TODO: implement moving cond jumps with bookkeeping copies on both targets.
237    TODO: tune the scheduler before RA so it does not create too much pseudos.
238
239
240    References:
241    S.-M. Moon and K. Ebcioglu. Parallelizing nonnumerical code with
242    selective scheduling and software pipelining.
243    ACM TOPLAS, Vol 19, No. 6, pages 853--898, Nov. 1997.
244
245    Andrey Belevantsev, Maxim Kuvyrkov, Vladimir Makarov, Dmitry Melnik,
246    and Dmitry Zhurikhin.  An interblock VLIW-targeted instruction scheduler
247    for GCC. In Proceedings of GCC Developers' Summit 2006.
248
249    Arutyun Avetisyan, Andrey Belevantsev, and Dmitry Melnik.  GCC Instruction
250    Scheduler and Software Pipeliner on the Itanium Platform.   EPIC-7 Workshop.
251    http://rogue.colorado.edu/EPIC7/.
252
253 */
254
255 /* True when pipelining is enabled.  */
256 bool pipelining_p;
257
258 /* True if bookkeeping is enabled.  */
259 bool bookkeeping_p;
260
261 /* Maximum number of insns that are eligible for renaming.  */
262 int max_insns_to_rename;
263 \f
264
265 /* Definitions of local types and macros.  */
266
267 /* Represents possible outcomes of moving an expression through an insn.  */
268 enum MOVEUP_EXPR_CODE
269   {
270     /* The expression is not changed.  */
271     MOVEUP_EXPR_SAME,
272
273     /* Not changed, but requires a new destination register.  */
274     MOVEUP_EXPR_AS_RHS,
275
276     /* Cannot be moved.  */
277     MOVEUP_EXPR_NULL,
278
279     /* Changed (substituted or speculated).  */
280     MOVEUP_EXPR_CHANGED
281   };
282
283 /* The container to be passed into rtx search & replace functions.  */
284 struct rtx_search_arg
285 {
286   /* What we are searching for.  */
287   rtx x;
288
289   /* The occurence counter.  */
290   int n;
291 };
292
293 typedef struct rtx_search_arg *rtx_search_arg_p;
294
295 /* This struct contains precomputed hard reg sets that are needed when
296    computing registers available for renaming.  */
297 struct hard_regs_data
298 {
299   /* For every mode, this stores registers available for use with
300      that mode.  */
301   HARD_REG_SET regs_for_mode[NUM_MACHINE_MODES];
302
303   /* True when regs_for_mode[mode] is initialized.  */
304   bool regs_for_mode_ok[NUM_MACHINE_MODES];
305
306   /* For every register, it has regs that are ok to rename into it.
307      The register in question is always set.  If not, this means
308      that the whole set is not computed yet.  */
309   HARD_REG_SET regs_for_rename[FIRST_PSEUDO_REGISTER];
310
311   /* For every mode, this stores registers not available due to
312      call clobbering.  */
313   HARD_REG_SET regs_for_call_clobbered[NUM_MACHINE_MODES];
314
315   /* All registers that are used or call used.  */
316   HARD_REG_SET regs_ever_used;
317
318 #ifdef STACK_REGS
319   /* Stack registers.  */
320   HARD_REG_SET stack_regs;
321 #endif
322 };
323
324 /* Holds the results of computation of available for renaming and
325    unavailable hard registers.  */
326 struct reg_rename
327 {
328   /* These are unavailable due to calls crossing, globalness, etc.  */
329   HARD_REG_SET unavailable_hard_regs;
330
331   /* These are *available* for renaming.  */
332   HARD_REG_SET available_for_renaming;
333
334   /* Whether this code motion path crosses a call.  */
335   bool crosses_call;
336 };
337
338 /* A global structure that contains the needed information about harg
339    regs.  */
340 static struct hard_regs_data sel_hrd;
341 \f
342
343 /* This structure holds local data used in code_motion_path_driver hooks on
344    the same or adjacent levels of recursion.  Here we keep those parameters
345    that are not used in code_motion_path_driver routine itself, but only in
346    its hooks.  Moreover, all parameters that can be modified in hooks are
347    in this structure, so all other parameters passed explicitly to hooks are
348    read-only.  */
349 struct cmpd_local_params
350 {
351   /* Local params used in move_op_* functions.  */
352
353   /* Edges for bookkeeping generation.  */
354   edge e1, e2;
355
356   /* C_EXPR merged from all successors and locally allocated temporary C_EXPR.  */
357   expr_t c_expr_merged, c_expr_local;
358
359   /* Local params used in fur_* functions.  */
360   /* Copy of the ORIGINAL_INSN list, stores the original insns already
361      found before entering the current level of code_motion_path_driver.  */
362   def_list_t old_original_insns;
363
364   /* Local params used in move_op_* functions.  */
365   /* True when we have removed last insn in the block which was
366      also a boundary.  Do not update anything or create bookkeeping copies.  */
367   BOOL_BITFIELD removed_last_insn : 1;
368 };
369
370 /* Stores the static parameters for move_op_* calls.  */
371 struct moveop_static_params
372 {
373   /* Destination register.  */
374   rtx dest;
375
376   /* Current C_EXPR.  */
377   expr_t c_expr;
378
379   /* An UID of expr_vliw which is to be moved up.  If we find other exprs,
380      they are to be removed.  */
381   int uid;
382
383 #ifdef ENABLE_CHECKING
384   /* This is initialized to the insn on which the driver stopped its traversal.  */
385   insn_t failed_insn;
386 #endif
387
388   /* True if we scheduled an insn with different register.  */
389   bool was_renamed;
390 };
391
392 /* Stores the static parameters for fur_* calls.  */
393 struct fur_static_params
394 {
395   /* Set of registers unavailable on the code motion path.  */
396   regset used_regs;
397
398   /* Pointer to the list of original insns definitions.  */
399   def_list_t *original_insns;
400
401   /* True if a code motion path contains a CALL insn.  */
402   bool crosses_call;
403 };
404
405 typedef struct fur_static_params *fur_static_params_p;
406 typedef struct cmpd_local_params *cmpd_local_params_p;
407 typedef struct moveop_static_params *moveop_static_params_p;
408
409 /* Set of hooks and parameters that determine behaviour specific to
410    move_op or find_used_regs functions.  */
411 struct code_motion_path_driver_info_def
412 {
413   /* Called on enter to the basic block.  */
414   int (*on_enter) (insn_t, cmpd_local_params_p, void *, bool);
415
416   /* Called when original expr is found.  */
417   void (*orig_expr_found) (insn_t, expr_t, cmpd_local_params_p, void *);
418
419   /* Called while descending current basic block if current insn is not
420      the original EXPR we're searching for.  */
421   bool (*orig_expr_not_found) (insn_t, av_set_t, void *);
422
423   /* Function to merge C_EXPRes from different successors.  */
424   void (*merge_succs) (insn_t, insn_t, int, cmpd_local_params_p, void *);
425
426   /* Function to finalize merge from different successors and possibly
427      deallocate temporary data structures used for merging.  */
428   void (*after_merge_succs) (cmpd_local_params_p, void *);
429
430   /* Called on the backward stage of recursion to do moveup_expr.
431      Used only with move_op_*.  */
432   void (*ascend) (insn_t, void *);
433
434   /* Called on the ascending pass, before returning from the current basic
435      block or from the whole traversal.  */
436   void (*at_first_insn) (insn_t, cmpd_local_params_p, void *);
437
438   /* When processing successors in move_op we need only descend into
439      SUCCS_NORMAL successors, while in find_used_regs we need SUCCS_ALL.  */
440   int succ_flags;
441
442   /* The routine name to print in dumps ("move_op" of "find_used_regs").  */
443   const char *routine_name;
444 };
445
446 /* Global pointer to current hooks, either points to MOVE_OP_HOOKS or
447    FUR_HOOKS.  */
448 struct code_motion_path_driver_info_def *code_motion_path_driver_info;
449
450 /* Set of hooks for performing move_op and find_used_regs routines with
451    code_motion_path_driver.  */
452 extern struct code_motion_path_driver_info_def move_op_hooks, fur_hooks;
453
454 /* True if/when we want to emulate Haifa scheduler in the common code.
455    This is used in sched_rgn_local_init and in various places in
456    sched-deps.c.  */
457 int sched_emulate_haifa_p;
458
459 /* GLOBAL_LEVEL is used to discard information stored in basic block headers
460    av_sets.  Av_set of bb header is valid if its (bb header's) level is equal
461    to GLOBAL_LEVEL.  And invalid if lesser.  This is primarily used to advance
462    scheduling window.  */
463 int global_level;
464
465 /* Current fences.  */
466 flist_t fences;
467
468 /* True when separable insns should be scheduled as RHSes.  */
469 static bool enable_schedule_as_rhs_p;
470
471 /* Used in verify_target_availability to assert that target reg is reported
472    unavailabile by both TARGET_UNAVAILABLE and find_used_regs only if
473    we haven't scheduled anything on the previous fence.
474    if scheduled_something_on_previous_fence is true, TARGET_UNAVAILABLE can
475    have more conservative value than the one returned by the
476    find_used_regs, thus we shouldn't assert that these values are equal.  */
477 static bool scheduled_something_on_previous_fence;
478
479 /* All newly emitted insns will have their uids greater than this value.  */
480 static int first_emitted_uid;
481
482 /* Set of basic blocks that are forced to start new ebbs.  This is a subset
483    of all the ebb heads.  */
484 static bitmap_head _forced_ebb_heads;
485 bitmap_head *forced_ebb_heads = &_forced_ebb_heads;
486
487 /* Blocks that need to be rescheduled after pipelining.  */
488 bitmap blocks_to_reschedule = NULL;
489
490 /* True when the first lv set should be ignored when updating liveness.  */
491 static bool ignore_first = false;
492
493 /* Number of insns max_issue has initialized data structures for.  */
494 static int max_issue_size = 0;
495
496 /* Whether we can issue more instructions.  */
497 static int can_issue_more;
498
499 /* Maximum software lookahead window size, reduced when rescheduling after
500    pipelining.  */
501 static int max_ws;
502
503 /* Number of insns scheduled in current region.  */
504 static int num_insns_scheduled;
505
506 /* A vector of expressions is used to be able to sort them.  */
507 DEF_VEC_P(expr_t);
508 DEF_VEC_ALLOC_P(expr_t,heap);
509 static VEC(expr_t, heap) *vec_av_set = NULL;
510
511 /* A vector of vinsns is used to hold temporary lists of vinsns.  */
512 DEF_VEC_P(vinsn_t);
513 DEF_VEC_ALLOC_P(vinsn_t,heap);
514 typedef VEC(vinsn_t, heap) *vinsn_vec_t;
515
516 /* This vector has the exprs which may still present in av_sets, but actually
517    can't be moved up due to bookkeeping created during code motion to another
518    fence.  See comment near the call to update_and_record_unavailable_insns
519    for the detailed explanations.  */
520 static vinsn_vec_t vec_bookkeeping_blocked_vinsns = NULL;
521
522 /* This vector has vinsns which are scheduled with renaming on the first fence
523    and then seen on the second.  For expressions with such vinsns, target
524    availability information may be wrong.  */
525 static vinsn_vec_t vec_target_unavailable_vinsns = NULL;
526
527 /* Vector to store temporary nops inserted in move_op to prevent removal
528    of empty bbs.  */
529 DEF_VEC_P(insn_t);
530 DEF_VEC_ALLOC_P(insn_t,heap);
531 static VEC(insn_t, heap) *vec_temp_moveop_nops = NULL;
532
533 /* These bitmaps record original instructions scheduled on the current
534    iteration and bookkeeping copies created by them.  */
535 static bitmap current_originators = NULL;
536 static bitmap current_copies = NULL;
537
538 /* This bitmap marks the blocks visited by code_motion_path_driver so we don't
539    visit them afterwards.  */
540 static bitmap code_motion_visited_blocks = NULL;
541
542 /* Variables to accumulate different statistics.  */
543
544 /* The number of bookkeeping copies created.  */
545 static int stat_bookkeeping_copies;
546
547 /* The number of insns that required bookkeeiping for their scheduling.  */
548 static int stat_insns_needed_bookkeeping;
549
550 /* The number of insns that got renamed.  */
551 static int stat_renamed_scheduled;
552
553 /* The number of substitutions made during scheduling.  */
554 static int stat_substitutions_total;
555 \f
556
557 /* Forward declarations of static functions.  */
558 static bool rtx_ok_for_substitution_p (rtx, rtx);
559 static int sel_rank_for_schedule (const void *, const void *);
560 static av_set_t find_sequential_best_exprs (bnd_t, expr_t, bool);
561 static basic_block find_block_for_bookkeeping (edge e1, edge e2, bool lax);
562
563 static rtx get_dest_from_orig_ops (av_set_t);
564 static basic_block generate_bookkeeping_insn (expr_t, edge, edge);
565 static bool find_used_regs (insn_t, av_set_t, regset, struct reg_rename *,
566                             def_list_t *);
567 static bool move_op (insn_t, av_set_t, expr_t, rtx, expr_t, bool*);
568 static int code_motion_path_driver (insn_t, av_set_t, ilist_t,
569                                     cmpd_local_params_p, void *);
570 static void sel_sched_region_1 (void);
571 static void sel_sched_region_2 (int);
572 static av_set_t compute_av_set_inside_bb (insn_t, ilist_t, int, bool);
573
574 static void debug_state (state_t);
575 \f
576
577 /* Functions that work with fences.  */
578
579 /* Advance one cycle on FENCE.  */
580 static void
581 advance_one_cycle (fence_t fence)
582 {
583   unsigned i;
584   int cycle;
585   rtx insn;
586
587   advance_state (FENCE_STATE (fence));
588   cycle = ++FENCE_CYCLE (fence);
589   FENCE_ISSUED_INSNS (fence) = 0;
590   FENCE_STARTS_CYCLE_P (fence) = 1;
591   can_issue_more = issue_rate;
592   FENCE_ISSUE_MORE (fence) = can_issue_more;
593
594   for (i = 0; VEC_iterate (rtx, FENCE_EXECUTING_INSNS (fence), i, insn); )
595     {
596       if (INSN_READY_CYCLE (insn) < cycle)
597         {
598           remove_from_deps (FENCE_DC (fence), insn);
599           VEC_unordered_remove (rtx, FENCE_EXECUTING_INSNS (fence), i);
600           continue;
601         }
602       i++;
603     }
604   if (sched_verbose >= 2)
605     {
606       sel_print ("Finished a cycle.  Current cycle = %d\n", FENCE_CYCLE (fence));
607       debug_state (FENCE_STATE (fence));
608     }
609 }
610
611 /* Returns true when SUCC in a fallthru bb of INSN, possibly
612    skipping empty basic blocks.  */
613 static bool
614 in_fallthru_bb_p (rtx insn, rtx succ)
615 {
616   basic_block bb = BLOCK_FOR_INSN (insn);
617   edge e;
618
619   if (bb == BLOCK_FOR_INSN (succ))
620     return true;
621
622   e = find_fallthru_edge_from (bb);
623   if (e)
624     bb = e->dest;
625   else
626     return false;
627
628   while (sel_bb_empty_p (bb))
629     bb = bb->next_bb;
630
631   return bb == BLOCK_FOR_INSN (succ);
632 }
633
634 /* Construct successor fences from OLD_FENCEs and put them in NEW_FENCES.
635    When a successor will continue a ebb, transfer all parameters of a fence
636    to the new fence.  ORIG_MAX_SEQNO is the maximal seqno before this round
637    of scheduling helping to distinguish between the old and the new code.  */
638 static void
639 extract_new_fences_from (flist_t old_fences, flist_tail_t new_fences,
640                          int orig_max_seqno)
641 {
642   bool was_here_p = false;
643   insn_t insn = NULL_RTX;
644   insn_t succ;
645   succ_iterator si;
646   ilist_iterator ii;
647   fence_t fence = FLIST_FENCE (old_fences);
648   basic_block bb;
649
650   /* Get the only element of FENCE_BNDS (fence).  */
651   FOR_EACH_INSN (insn, ii, FENCE_BNDS (fence))
652     {
653       gcc_assert (!was_here_p);
654       was_here_p = true;
655     }
656   gcc_assert (was_here_p && insn != NULL_RTX);
657
658   /* When in the "middle" of the block, just move this fence
659      to the new list.  */
660   bb = BLOCK_FOR_INSN (insn);
661   if (! sel_bb_end_p (insn)
662       || (single_succ_p (bb)
663           && single_pred_p (single_succ (bb))))
664     {
665       insn_t succ;
666
667       succ = (sel_bb_end_p (insn)
668               ? sel_bb_head (single_succ (bb))
669               : NEXT_INSN (insn));
670
671       if (INSN_SEQNO (succ) > 0
672           && INSN_SEQNO (succ) <= orig_max_seqno
673           && INSN_SCHED_TIMES (succ) <= 0)
674         {
675           FENCE_INSN (fence) = succ;
676           move_fence_to_fences (old_fences, new_fences);
677
678           if (sched_verbose >= 1)
679             sel_print ("Fence %d continues as %d[%d] (state continue)\n",
680                        INSN_UID (insn), INSN_UID (succ), BLOCK_NUM (succ));
681         }
682       return;
683     }
684
685   /* Otherwise copy fence's structures to (possibly) multiple successors.  */
686   FOR_EACH_SUCC_1 (succ, si, insn, SUCCS_NORMAL | SUCCS_SKIP_TO_LOOP_EXITS)
687     {
688       int seqno = INSN_SEQNO (succ);
689
690       if (0 < seqno && seqno <= orig_max_seqno
691           && (pipelining_p || INSN_SCHED_TIMES (succ) <= 0))
692         {
693           bool b = (in_same_ebb_p (insn, succ)
694                     || in_fallthru_bb_p (insn, succ));
695
696           if (sched_verbose >= 1)
697             sel_print ("Fence %d continues as %d[%d] (state %s)\n",
698                        INSN_UID (insn), INSN_UID (succ),
699                        BLOCK_NUM (succ), b ? "continue" : "reset");
700
701           if (b)
702             add_dirty_fence_to_fences (new_fences, succ, fence);
703           else
704             {
705               /* Mark block of the SUCC as head of the new ebb.  */
706               bitmap_set_bit (forced_ebb_heads, BLOCK_NUM (succ));
707               add_clean_fence_to_fences (new_fences, succ, fence);
708             }
709         }
710     }
711 }
712 \f
713
714 /* Functions to support substitution.  */
715
716 /* Returns whether INSN with dependence status DS is eligible for
717    substitution, i.e. it's a copy operation x := y, and RHS that is
718    moved up through this insn should be substituted.  */
719 static bool
720 can_substitute_through_p (insn_t insn, ds_t ds)
721 {
722   /* We can substitute only true dependencies.  */
723   if ((ds & DEP_OUTPUT)
724       || (ds & DEP_ANTI)
725       || ! INSN_RHS (insn)
726       || ! INSN_LHS (insn))
727     return false;
728
729   /* Now we just need to make sure the INSN_RHS consists of only one
730      simple REG rtx.  */
731   if (REG_P (INSN_LHS (insn))
732       && REG_P (INSN_RHS (insn)))
733     return true;
734   return false;
735 }
736
737 /* Substitute all occurences of INSN's destination in EXPR' vinsn with INSN's
738    source (if INSN is eligible for substitution).  Returns TRUE if
739    substitution was actually performed, FALSE otherwise.  Substitution might
740    be not performed because it's either EXPR' vinsn doesn't contain INSN's
741    destination or the resulting insn is invalid for the target machine.
742    When UNDO is true, perform unsubstitution instead (the difference is in
743    the part of rtx on which validate_replace_rtx is called).  */
744 static bool
745 substitute_reg_in_expr (expr_t expr, insn_t insn, bool undo)
746 {
747   rtx *where;
748   bool new_insn_valid;
749   vinsn_t *vi = &EXPR_VINSN (expr);
750   bool has_rhs = VINSN_RHS (*vi) != NULL;
751   rtx old, new_rtx;
752
753   /* Do not try to replace in SET_DEST.  Although we'll choose new
754      register for the RHS, we don't want to change RHS' original reg.
755      If the insn is not SET, we may still be able to substitute something
756      in it, and if we're here (don't have deps), it doesn't write INSN's
757      dest.  */
758   where = (has_rhs
759            ? &VINSN_RHS (*vi)
760            : &PATTERN (VINSN_INSN_RTX (*vi)));
761   old = undo ? INSN_RHS (insn) : INSN_LHS (insn);
762
763   /* Substitute if INSN has a form of x:=y and LHS(INSN) occurs in *VI.  */
764   if (rtx_ok_for_substitution_p (old, *where))
765     {
766       rtx new_insn;
767       rtx *where_replace;
768
769       /* We should copy these rtxes before substitution.  */
770       new_rtx = copy_rtx (undo ? INSN_LHS (insn) : INSN_RHS (insn));
771       new_insn = create_copy_of_insn_rtx (VINSN_INSN_RTX (*vi));
772
773       /* Where we'll replace.
774          WHERE_REPLACE should point inside NEW_INSN, so INSN_RHS couldn't be
775          used instead of SET_SRC.  */
776       where_replace = (has_rhs
777                        ? &SET_SRC (PATTERN (new_insn))
778                        : &PATTERN (new_insn));
779
780       new_insn_valid
781         = validate_replace_rtx_part_nosimplify (old, new_rtx, where_replace,
782                                                 new_insn);
783
784       /* ??? Actually, constrain_operands result depends upon choice of
785          destination register.  E.g. if we allow single register to be an rhs,
786          and if we try to move dx=ax(as rhs) through ax=dx, we'll result
787          in invalid insn dx=dx, so we'll loose this rhs here.
788          Just can't come up with significant testcase for this, so just
789          leaving it for now.  */
790       if (new_insn_valid)
791         {
792           change_vinsn_in_expr (expr,
793                                 create_vinsn_from_insn_rtx (new_insn, false));
794
795           /* Do not allow clobbering the address register of speculative
796              insns.  */
797           if ((EXPR_SPEC_DONE_DS (expr) & SPECULATIVE)
798               && register_unavailable_p (VINSN_REG_USES (EXPR_VINSN (expr)),
799                                          expr_dest_reg (expr)))
800             EXPR_TARGET_AVAILABLE (expr) = false;
801
802           return true;
803         }
804       else
805         return false;
806     }
807   else
808     return false;
809 }
810
811 /* Helper function for count_occurences_equiv.  */
812 static int
813 count_occurrences_1 (rtx *cur_rtx, void *arg)
814 {
815   rtx_search_arg_p p = (rtx_search_arg_p) arg;
816
817   if (REG_P (*cur_rtx) && REGNO (*cur_rtx) == REGNO (p->x))
818     {
819       /* Bail out if mode is different or more than one register is used.  */
820       if (GET_MODE (*cur_rtx) != GET_MODE (p->x)
821           || (HARD_REGISTER_P (*cur_rtx)
822               && hard_regno_nregs[REGNO(*cur_rtx)][GET_MODE (*cur_rtx)] > 1))
823         {
824           p->n = 0;
825           return 1;
826         }
827
828       p->n++;
829
830       /* Do not traverse subexprs.  */
831       return -1;
832     }
833
834   if (GET_CODE (*cur_rtx) == SUBREG
835       && (!REG_P (SUBREG_REG (*cur_rtx))
836           || REGNO (SUBREG_REG (*cur_rtx)) == REGNO (p->x)))
837     {
838       /* ??? Do not support substituting regs inside subregs.  In that case,
839          simplify_subreg will be called by validate_replace_rtx, and
840          unsubstitution will fail later.  */
841       p->n = 0;
842       return 1;
843     }
844
845   /* Continue search.  */
846   return 0;
847 }
848
849 /* Return the number of places WHAT appears within WHERE.
850    Bail out when we found a reference occupying several hard registers.  */
851 static int
852 count_occurrences_equiv (rtx what, rtx where)
853 {
854   struct rtx_search_arg arg;
855
856   gcc_assert (REG_P (what));
857   arg.x = what;
858   arg.n = 0;
859
860   for_each_rtx (&where, &count_occurrences_1, (void *) &arg);
861
862   return arg.n;
863 }
864
865 /* Returns TRUE if WHAT is found in WHERE rtx tree.  */
866 static bool
867 rtx_ok_for_substitution_p (rtx what, rtx where)
868 {
869   return (count_occurrences_equiv (what, where) > 0);
870 }
871 \f
872
873 /* Functions to support register renaming.  */
874
875 /* Substitute VI's set source with REGNO.  Returns newly created pattern
876    that has REGNO as its source.  */
877 static rtx
878 create_insn_rtx_with_rhs (vinsn_t vi, rtx rhs_rtx)
879 {
880   rtx lhs_rtx;
881   rtx pattern;
882   rtx insn_rtx;
883
884   lhs_rtx = copy_rtx (VINSN_LHS (vi));
885
886   pattern = gen_rtx_SET (VOIDmode, lhs_rtx, rhs_rtx);
887   insn_rtx = create_insn_rtx_from_pattern (pattern, NULL_RTX);
888
889   return insn_rtx;
890 }
891
892 /* Returns whether INSN's src can be replaced with register number
893    NEW_SRC_REG. E.g. the following insn is valid for i386:
894
895     (insn:HI 2205 6585 2207 727 ../../gcc/libiberty/regex.c:3337
896       (set (mem/s:QI (plus:SI (plus:SI (reg/f:SI 7 sp)
897                         (reg:SI 0 ax [orig:770 c1 ] [770]))
898                     (const_int 288 [0x120])) [0 str S1 A8])
899             (const_int 0 [0x0])) 43 {*movqi_1} (nil)
900         (nil))
901
902   But if we change (const_int 0 [0x0]) to (reg:QI 4 si), it will be invalid
903   because of operand constraints:
904
905     (define_insn "*movqi_1"
906       [(set (match_operand:QI 0 "nonimmediate_operand" "=q,q ,q ,r,r ,?r,m")
907             (match_operand:QI 1 "general_operand"      " q,qn,qm,q,rn,qm,qn")
908             )]
909
910   So do constrain_operands here, before choosing NEW_SRC_REG as best
911   reg for rhs.  */
912
913 static bool
914 replace_src_with_reg_ok_p (insn_t insn, rtx new_src_reg)
915 {
916   vinsn_t vi = INSN_VINSN (insn);
917   enum machine_mode mode;
918   rtx dst_loc;
919   bool res;
920
921   gcc_assert (VINSN_SEPARABLE_P (vi));
922
923   get_dest_and_mode (insn, &dst_loc, &mode);
924   gcc_assert (mode == GET_MODE (new_src_reg));
925
926   if (REG_P (dst_loc) && REGNO (new_src_reg) == REGNO (dst_loc))
927     return true;
928
929   /* See whether SET_SRC can be replaced with this register.  */
930   validate_change (insn, &SET_SRC (PATTERN (insn)), new_src_reg, 1);
931   res = verify_changes (0);
932   cancel_changes (0);
933
934   return res;
935 }
936
937 /* Returns whether INSN still be valid after replacing it's DEST with
938    register NEW_REG.  */
939 static bool
940 replace_dest_with_reg_ok_p (insn_t insn, rtx new_reg)
941 {
942   vinsn_t vi = INSN_VINSN (insn);
943   bool res;
944
945   /* We should deal here only with separable insns.  */
946   gcc_assert (VINSN_SEPARABLE_P (vi));
947   gcc_assert (GET_MODE (VINSN_LHS (vi)) == GET_MODE (new_reg));
948
949   /* See whether SET_DEST can be replaced with this register.  */
950   validate_change (insn, &SET_DEST (PATTERN (insn)), new_reg, 1);
951   res = verify_changes (0);
952   cancel_changes (0);
953
954   return res;
955 }
956
957 /* Create a pattern with rhs of VI and lhs of LHS_RTX.  */
958 static rtx
959 create_insn_rtx_with_lhs (vinsn_t vi, rtx lhs_rtx)
960 {
961   rtx rhs_rtx;
962   rtx pattern;
963   rtx insn_rtx;
964
965   rhs_rtx = copy_rtx (VINSN_RHS (vi));
966
967   pattern = gen_rtx_SET (VOIDmode, lhs_rtx, rhs_rtx);
968   insn_rtx = create_insn_rtx_from_pattern (pattern, NULL_RTX);
969
970   return insn_rtx;
971 }
972
973 /* Substitute lhs in the given expression EXPR for the register with number
974    NEW_REGNO.  SET_DEST may be arbitrary rtx, not only register.  */
975 static void
976 replace_dest_with_reg_in_expr (expr_t expr, rtx new_reg)
977 {
978   rtx insn_rtx;
979   vinsn_t vinsn;
980
981   insn_rtx = create_insn_rtx_with_lhs (EXPR_VINSN (expr), new_reg);
982   vinsn = create_vinsn_from_insn_rtx (insn_rtx, false);
983
984   change_vinsn_in_expr (expr, vinsn);
985   EXPR_WAS_RENAMED (expr) = 1;
986   EXPR_TARGET_AVAILABLE (expr) = 1;
987 }
988
989 /* Returns whether VI writes either one of the USED_REGS registers or,
990    if a register is a hard one, one of the UNAVAILABLE_HARD_REGS registers.  */
991 static bool
992 vinsn_writes_one_of_regs_p (vinsn_t vi, regset used_regs,
993                             HARD_REG_SET unavailable_hard_regs)
994 {
995   unsigned regno;
996   reg_set_iterator rsi;
997
998   EXECUTE_IF_SET_IN_REG_SET (VINSN_REG_SETS (vi), 0, regno, rsi)
999     {
1000       if (REGNO_REG_SET_P (used_regs, regno))
1001         return true;
1002       if (HARD_REGISTER_NUM_P (regno)
1003           && TEST_HARD_REG_BIT (unavailable_hard_regs, regno))
1004         return true;
1005     }
1006
1007   EXECUTE_IF_SET_IN_REG_SET (VINSN_REG_CLOBBERS (vi), 0, regno, rsi)
1008     {
1009       if (REGNO_REG_SET_P (used_regs, regno))
1010         return true;
1011       if (HARD_REGISTER_NUM_P (regno)
1012           && TEST_HARD_REG_BIT (unavailable_hard_regs, regno))
1013         return true;
1014     }
1015
1016   return false;
1017 }
1018
1019 /* Returns register class of the output register in INSN.
1020    Returns NO_REGS for call insns because some targets have constraints on
1021    destination register of a call insn.
1022
1023    Code adopted from regrename.c::build_def_use.  */
1024 static enum reg_class
1025 get_reg_class (rtx insn)
1026 {
1027   int alt, i, n_ops;
1028
1029   extract_insn (insn);
1030   if (! constrain_operands (1))
1031     fatal_insn_not_found (insn);
1032   preprocess_constraints ();
1033   alt = which_alternative;
1034   n_ops = recog_data.n_operands;
1035
1036   for (i = 0; i < n_ops; ++i)
1037     {
1038       int matches = recog_op_alt[i][alt].matches;
1039       if (matches >= 0)
1040         recog_op_alt[i][alt].cl = recog_op_alt[matches][alt].cl;
1041     }
1042
1043   if (asm_noperands (PATTERN (insn)) > 0)
1044     {
1045       for (i = 0; i < n_ops; i++)
1046         if (recog_data.operand_type[i] == OP_OUT)
1047           {
1048             rtx *loc = recog_data.operand_loc[i];
1049             rtx op = *loc;
1050             enum reg_class cl = recog_op_alt[i][alt].cl;
1051
1052             if (REG_P (op)
1053                 && REGNO (op) == ORIGINAL_REGNO (op))
1054               continue;
1055
1056             return cl;
1057           }
1058     }
1059   else if (!CALL_P (insn))
1060     {
1061       for (i = 0; i < n_ops + recog_data.n_dups; i++)
1062        {
1063          int opn = i < n_ops ? i : recog_data.dup_num[i - n_ops];
1064          enum reg_class cl = recog_op_alt[opn][alt].cl;
1065
1066          if (recog_data.operand_type[opn] == OP_OUT ||
1067              recog_data.operand_type[opn] == OP_INOUT)
1068            return cl;
1069        }
1070     }
1071
1072 /*  Insns like
1073     (insn (set (reg:CCZ 17 flags) (compare:CCZ ...)))
1074     may result in returning NO_REGS, cause flags is written implicitly through
1075     CMP insn, which has no OP_OUT | OP_INOUT operands.  */
1076   return NO_REGS;
1077 }
1078
1079 #ifdef HARD_REGNO_RENAME_OK
1080 /* Calculate HARD_REGNO_RENAME_OK data for REGNO.  */
1081 static void
1082 init_hard_regno_rename (int regno)
1083 {
1084   int cur_reg;
1085
1086   SET_HARD_REG_BIT (sel_hrd.regs_for_rename[regno], regno);
1087
1088   for (cur_reg = 0; cur_reg < FIRST_PSEUDO_REGISTER; cur_reg++)
1089     {
1090       /* We are not interested in renaming in other regs.  */
1091       if (!TEST_HARD_REG_BIT (sel_hrd.regs_ever_used, cur_reg))
1092         continue;
1093
1094       if (HARD_REGNO_RENAME_OK (regno, cur_reg))
1095         SET_HARD_REG_BIT (sel_hrd.regs_for_rename[regno], cur_reg);
1096     }
1097 }
1098 #endif
1099
1100 /* A wrapper around HARD_REGNO_RENAME_OK that will look into the hard regs
1101    data first.  */
1102 static inline bool
1103 sel_hard_regno_rename_ok (int from ATTRIBUTE_UNUSED, int to ATTRIBUTE_UNUSED)
1104 {
1105 #ifdef HARD_REGNO_RENAME_OK
1106   /* Check whether this is all calculated.  */
1107   if (TEST_HARD_REG_BIT (sel_hrd.regs_for_rename[from], from))
1108     return TEST_HARD_REG_BIT (sel_hrd.regs_for_rename[from], to);
1109
1110   init_hard_regno_rename (from);
1111
1112   return TEST_HARD_REG_BIT (sel_hrd.regs_for_rename[from], to);
1113 #else
1114   return true;
1115 #endif
1116 }
1117
1118 /* Calculate set of registers that are capable of holding MODE.  */
1119 static void
1120 init_regs_for_mode (enum machine_mode mode)
1121 {
1122   int cur_reg;
1123
1124   CLEAR_HARD_REG_SET (sel_hrd.regs_for_mode[mode]);
1125   CLEAR_HARD_REG_SET (sel_hrd.regs_for_call_clobbered[mode]);
1126
1127   for (cur_reg = 0; cur_reg < FIRST_PSEUDO_REGISTER; cur_reg++)
1128     {
1129       int nregs = hard_regno_nregs[cur_reg][mode];
1130       int i;
1131
1132       for (i = nregs - 1; i >= 0; --i)
1133         if (fixed_regs[cur_reg + i]
1134                 || global_regs[cur_reg + i]
1135             /* Can't use regs which aren't saved by
1136                the prologue.  */
1137             || !TEST_HARD_REG_BIT (sel_hrd.regs_ever_used, cur_reg + i)
1138             /* Can't use regs with non-null REG_BASE_VALUE, because adjusting
1139                it affects aliasing globally and invalidates all AV sets.  */
1140             || get_reg_base_value (cur_reg + i)
1141 #ifdef LEAF_REGISTERS
1142             /* We can't use a non-leaf register if we're in a
1143                leaf function.  */
1144             || (current_function_is_leaf
1145                 && !LEAF_REGISTERS[cur_reg + i])
1146 #endif
1147             )
1148           break;
1149
1150       if (i >= 0)
1151         continue;
1152
1153       /* See whether it accepts all modes that occur in
1154          original insns.  */
1155       if (! HARD_REGNO_MODE_OK (cur_reg, mode))
1156         continue;
1157
1158       if (HARD_REGNO_CALL_PART_CLOBBERED (cur_reg, mode))
1159         SET_HARD_REG_BIT (sel_hrd.regs_for_call_clobbered[mode],
1160                           cur_reg);
1161
1162       /* If the CUR_REG passed all the checks above,
1163          then it's ok.  */
1164       SET_HARD_REG_BIT (sel_hrd.regs_for_mode[mode], cur_reg);
1165     }
1166
1167   sel_hrd.regs_for_mode_ok[mode] = true;
1168 }
1169
1170 /* Init all register sets gathered in HRD.  */
1171 static void
1172 init_hard_regs_data (void)
1173 {
1174   int cur_reg = 0;
1175   int cur_mode = 0;
1176
1177   CLEAR_HARD_REG_SET (sel_hrd.regs_ever_used);
1178   for (cur_reg = 0; cur_reg < FIRST_PSEUDO_REGISTER; cur_reg++)
1179     if (df_regs_ever_live_p (cur_reg) || call_used_regs[cur_reg])
1180       SET_HARD_REG_BIT (sel_hrd.regs_ever_used, cur_reg);
1181
1182   /* Initialize registers that are valid based on mode when this is
1183      really needed.  */
1184   for (cur_mode = 0; cur_mode < NUM_MACHINE_MODES; cur_mode++)
1185     sel_hrd.regs_for_mode_ok[cur_mode] = false;
1186
1187   /* Mark that all HARD_REGNO_RENAME_OK is not calculated.  */
1188   for (cur_reg = 0; cur_reg < FIRST_PSEUDO_REGISTER; cur_reg++)
1189     CLEAR_HARD_REG_SET (sel_hrd.regs_for_rename[cur_reg]);
1190
1191 #ifdef STACK_REGS
1192   CLEAR_HARD_REG_SET (sel_hrd.stack_regs);
1193
1194   for (cur_reg = FIRST_STACK_REG; cur_reg <= LAST_STACK_REG; cur_reg++)
1195     SET_HARD_REG_BIT (sel_hrd.stack_regs, cur_reg);
1196 #endif
1197 }
1198
1199 /* Mark hardware regs in REG_RENAME_P that are not suitable
1200    for renaming rhs in INSN due to hardware restrictions (register class,
1201    modes compatibility etc).  This doesn't affect original insn's dest reg,
1202    if it isn't in USED_REGS.  DEF is a definition insn of rhs for which the
1203    destination register is sought.  LHS (DEF->ORIG_INSN) may be REG or MEM.
1204    Registers that are in used_regs are always marked in
1205    unavailable_hard_regs as well.  */
1206
1207 static void
1208 mark_unavailable_hard_regs (def_t def, struct reg_rename *reg_rename_p,
1209                             regset used_regs ATTRIBUTE_UNUSED)
1210 {
1211   enum machine_mode mode;
1212   enum reg_class cl = NO_REGS;
1213   rtx orig_dest;
1214   unsigned cur_reg, regno;
1215   hard_reg_set_iterator hrsi;
1216
1217   gcc_assert (GET_CODE (PATTERN (def->orig_insn)) == SET);
1218   gcc_assert (reg_rename_p);
1219
1220   orig_dest = SET_DEST (PATTERN (def->orig_insn));
1221
1222   /* We have decided not to rename 'mem = something;' insns, as 'something'
1223      is usually a register.  */
1224   if (!REG_P (orig_dest))
1225     return;
1226
1227   regno = REGNO (orig_dest);
1228
1229   /* If before reload, don't try to work with pseudos.  */
1230   if (!reload_completed && !HARD_REGISTER_NUM_P (regno))
1231     return;
1232
1233   if (reload_completed)
1234     cl = get_reg_class (def->orig_insn);
1235
1236   /* Stop if the original register is one of the fixed_regs, global_regs or
1237      frame pointer, or we could not discover its class.  */
1238   if (fixed_regs[regno]
1239       || global_regs[regno]
1240 #if !HARD_FRAME_POINTER_IS_FRAME_POINTER
1241       || (frame_pointer_needed && regno == HARD_FRAME_POINTER_REGNUM)
1242 #else
1243       || (frame_pointer_needed && regno == FRAME_POINTER_REGNUM)
1244 #endif
1245       || (reload_completed && cl == NO_REGS))
1246     {
1247       SET_HARD_REG_SET (reg_rename_p->unavailable_hard_regs);
1248
1249       /* Give a chance for original register, if it isn't in used_regs.  */
1250       if (!def->crosses_call)
1251         CLEAR_HARD_REG_BIT (reg_rename_p->unavailable_hard_regs, regno);
1252
1253       return;
1254     }
1255
1256   /* If something allocated on stack in this function, mark frame pointer
1257      register unavailable, considering also modes.
1258      FIXME: it is enough to do this once per all original defs.  */
1259   if (frame_pointer_needed)
1260     {
1261       add_to_hard_reg_set (&reg_rename_p->unavailable_hard_regs,
1262                            Pmode, FRAME_POINTER_REGNUM);
1263
1264       if (!HARD_FRAME_POINTER_IS_FRAME_POINTER)
1265         add_to_hard_reg_set (&reg_rename_p->unavailable_hard_regs, 
1266                              Pmode, HARD_FRAME_POINTER_REGNUM);
1267     }
1268
1269 #ifdef STACK_REGS
1270   /* For the stack registers the presence of FIRST_STACK_REG in USED_REGS
1271      is equivalent to as if all stack regs were in this set.
1272      I.e. no stack register can be renamed, and even if it's an original
1273      register here we make sure it won't be lifted over it's previous def
1274      (it's previous def will appear as if it's a FIRST_STACK_REG def.
1275      The HARD_REGNO_RENAME_OK covers other cases in condition below.  */
1276   if (IN_RANGE (REGNO (orig_dest), FIRST_STACK_REG, LAST_STACK_REG)
1277       && REGNO_REG_SET_P (used_regs, FIRST_STACK_REG))
1278     IOR_HARD_REG_SET (reg_rename_p->unavailable_hard_regs,
1279                       sel_hrd.stack_regs);
1280 #endif
1281
1282   /* If there's a call on this path, make regs from call_used_reg_set
1283      unavailable.  */
1284   if (def->crosses_call)
1285     IOR_HARD_REG_SET (reg_rename_p->unavailable_hard_regs,
1286                       call_used_reg_set);
1287
1288   /* Stop here before reload: we need FRAME_REGS, STACK_REGS, and crosses_call,
1289      but not register classes.  */
1290   if (!reload_completed)
1291     return;
1292
1293   /* Leave regs as 'available' only from the current
1294      register class.  */
1295   COPY_HARD_REG_SET (reg_rename_p->available_for_renaming,
1296                      reg_class_contents[cl]);
1297
1298   mode = GET_MODE (orig_dest);
1299
1300   /* Leave only registers available for this mode.  */
1301   if (!sel_hrd.regs_for_mode_ok[mode])
1302     init_regs_for_mode (mode);
1303   AND_HARD_REG_SET (reg_rename_p->available_for_renaming,
1304                     sel_hrd.regs_for_mode[mode]);
1305
1306   /* Exclude registers that are partially call clobbered.  */
1307   if (def->crosses_call
1308       && ! HARD_REGNO_CALL_PART_CLOBBERED (regno, mode))
1309     AND_COMPL_HARD_REG_SET (reg_rename_p->available_for_renaming,
1310                             sel_hrd.regs_for_call_clobbered[mode]);
1311
1312   /* Leave only those that are ok to rename.  */
1313   EXECUTE_IF_SET_IN_HARD_REG_SET (reg_rename_p->available_for_renaming,
1314                                   0, cur_reg, hrsi)
1315     {
1316       int nregs;
1317       int i;
1318
1319       nregs = hard_regno_nregs[cur_reg][mode];
1320       gcc_assert (nregs > 0);
1321
1322       for (i = nregs - 1; i >= 0; --i)
1323         if (! sel_hard_regno_rename_ok (regno + i, cur_reg + i))
1324           break;
1325
1326       if (i >= 0)
1327         CLEAR_HARD_REG_BIT (reg_rename_p->available_for_renaming,
1328                             cur_reg);
1329     }
1330
1331   AND_COMPL_HARD_REG_SET (reg_rename_p->available_for_renaming,
1332                           reg_rename_p->unavailable_hard_regs);
1333
1334   /* Regno is always ok from the renaming part of view, but it really
1335      could be in *unavailable_hard_regs already, so set it here instead
1336      of there.  */
1337   SET_HARD_REG_BIT (reg_rename_p->available_for_renaming, regno);
1338 }
1339
1340 /* reg_rename_tick[REG1] > reg_rename_tick[REG2] if REG1 was chosen as the
1341    best register more recently than REG2.  */
1342 static int reg_rename_tick[FIRST_PSEUDO_REGISTER];
1343
1344 /* Indicates the number of times renaming happened before the current one.  */
1345 static int reg_rename_this_tick;
1346
1347 /* Choose the register among free, that is suitable for storing
1348    the rhs value.
1349
1350    ORIGINAL_INSNS is the list of insns where the operation (rhs)
1351    originally appears.  There could be multiple original operations
1352    for single rhs since we moving it up and merging along different
1353    paths.
1354
1355    Some code is adapted from regrename.c (regrename_optimize).
1356    If original register is available, function returns it.
1357    Otherwise it performs the checks, so the new register should
1358    comply with the following:
1359     - it should not violate any live ranges (such registers are in
1360       REG_RENAME_P->available_for_renaming set);
1361     - it should not be in the HARD_REGS_USED regset;
1362     - it should be in the class compatible with original uses;
1363     - it should not be clobbered through reference with different mode;
1364     - if we're in the leaf function, then the new register should
1365       not be in the LEAF_REGISTERS;
1366     - etc.
1367
1368    If several registers meet the conditions, the register with smallest
1369    tick is returned to achieve more even register allocation.
1370
1371    If original register seems to be ok, we set *IS_ORIG_REG_P_PTR to true.
1372
1373    If no register satisfies the above conditions, NULL_RTX is returned.  */
1374 static rtx
1375 choose_best_reg_1 (HARD_REG_SET hard_regs_used,
1376                    struct reg_rename *reg_rename_p,
1377                    def_list_t original_insns, bool *is_orig_reg_p_ptr)
1378 {
1379   int best_new_reg;
1380   unsigned cur_reg;
1381   enum machine_mode mode = VOIDmode;
1382   unsigned regno, i, n;
1383   hard_reg_set_iterator hrsi;
1384   def_list_iterator di;
1385   def_t def;
1386
1387   /* If original register is available, return it.  */
1388   *is_orig_reg_p_ptr = true;
1389
1390   FOR_EACH_DEF (def, di, original_insns)
1391     {
1392       rtx orig_dest = SET_DEST (PATTERN (def->orig_insn));
1393
1394       gcc_assert (REG_P (orig_dest));
1395
1396       /* Check that all original operations have the same mode.
1397          This is done for the next loop; if we'd return from this
1398          loop, we'd check only part of them, but in this case
1399          it doesn't matter.  */
1400       if (mode == VOIDmode)
1401         mode = GET_MODE (orig_dest);
1402       gcc_assert (mode == GET_MODE (orig_dest));
1403
1404       regno = REGNO (orig_dest);
1405       for (i = 0, n = hard_regno_nregs[regno][mode]; i < n; i++)
1406         if (TEST_HARD_REG_BIT (hard_regs_used, regno + i))
1407           break;
1408
1409       /* All hard registers are available.  */
1410       if (i == n)
1411         {
1412           gcc_assert (mode != VOIDmode);
1413
1414           /* Hard registers should not be shared.  */
1415           return gen_rtx_REG (mode, regno);
1416         }
1417     }
1418
1419   *is_orig_reg_p_ptr = false;
1420   best_new_reg = -1;
1421
1422   /* Among all available regs choose the register that was
1423      allocated earliest.  */
1424   EXECUTE_IF_SET_IN_HARD_REG_SET (reg_rename_p->available_for_renaming,
1425                                   0, cur_reg, hrsi)
1426     if (! TEST_HARD_REG_BIT (hard_regs_used, cur_reg))
1427       {
1428         /* Check that all hard regs for mode are available.  */
1429         for (i = 1, n = hard_regno_nregs[cur_reg][mode]; i < n; i++)
1430           if (TEST_HARD_REG_BIT (hard_regs_used, cur_reg + i)
1431               || !TEST_HARD_REG_BIT (reg_rename_p->available_for_renaming,
1432                                      cur_reg + i))
1433             break;
1434
1435         if (i < n)
1436           continue;
1437
1438         /* All hard registers are available.  */
1439         if (best_new_reg < 0
1440             || reg_rename_tick[cur_reg] < reg_rename_tick[best_new_reg])
1441           {
1442             best_new_reg = cur_reg;
1443
1444             /* Return immediately when we know there's no better reg.  */
1445             if (! reg_rename_tick[best_new_reg])
1446               break;
1447           }
1448       }
1449
1450   if (best_new_reg >= 0)
1451     {
1452       /* Use the check from the above loop.  */
1453       gcc_assert (mode != VOIDmode);
1454       return gen_rtx_REG (mode, best_new_reg);
1455     }
1456
1457   return NULL_RTX;
1458 }
1459
1460 /* A wrapper around choose_best_reg_1 () to verify that we make correct
1461    assumptions about available registers in the function.  */
1462 static rtx
1463 choose_best_reg (HARD_REG_SET hard_regs_used, struct reg_rename *reg_rename_p,
1464                  def_list_t original_insns, bool *is_orig_reg_p_ptr)
1465 {
1466   rtx best_reg = choose_best_reg_1 (hard_regs_used, reg_rename_p,
1467                                     original_insns, is_orig_reg_p_ptr);
1468
1469   /* FIXME loop over hard_regno_nregs here.  */
1470   gcc_assert (best_reg == NULL_RTX
1471               || TEST_HARD_REG_BIT (sel_hrd.regs_ever_used, REGNO (best_reg)));
1472
1473   return best_reg;
1474 }
1475
1476 /* Choose the pseudo register for storing rhs value.  As this is supposed
1477    to work before reload, we return either the original register or make
1478    the new one.  The parameters are the same that in choose_nest_reg_1
1479    functions, except that USED_REGS may contain pseudos.
1480    If we work with hard regs, check also REG_RENAME_P->UNAVAILABLE_HARD_REGS.
1481
1482    TODO: take into account register pressure while doing this.  Up to this
1483    moment, this function would never return NULL for pseudos, but we should
1484    not rely on this.  */
1485 static rtx
1486 choose_best_pseudo_reg (regset used_regs,
1487                         struct reg_rename *reg_rename_p,
1488                         def_list_t original_insns, bool *is_orig_reg_p_ptr)
1489 {
1490   def_list_iterator i;
1491   def_t def;
1492   enum machine_mode mode = VOIDmode;
1493   bool bad_hard_regs = false;
1494
1495   /* We should not use this after reload.  */
1496   gcc_assert (!reload_completed);
1497
1498   /* If original register is available, return it.  */
1499   *is_orig_reg_p_ptr = true;
1500
1501   FOR_EACH_DEF (def, i, original_insns)
1502     {
1503       rtx dest = SET_DEST (PATTERN (def->orig_insn));
1504       int orig_regno;
1505
1506       gcc_assert (REG_P (dest));
1507
1508       /* Check that all original operations have the same mode.  */
1509       if (mode == VOIDmode)
1510         mode = GET_MODE (dest);
1511       else
1512         gcc_assert (mode == GET_MODE (dest));
1513       orig_regno = REGNO (dest);
1514
1515       if (!REGNO_REG_SET_P (used_regs, orig_regno))
1516         {
1517           if (orig_regno < FIRST_PSEUDO_REGISTER)
1518             {
1519               gcc_assert (df_regs_ever_live_p (orig_regno));
1520
1521               /* For hard registers, we have to check hardware imposed
1522                  limitations (frame/stack registers, calls crossed).  */
1523               if (!TEST_HARD_REG_BIT (reg_rename_p->unavailable_hard_regs,
1524                                       orig_regno))
1525                 {
1526                   /* Don't let register cross a call if it doesn't already
1527                      cross one.  This condition is written in accordance with
1528                      that in sched-deps.c sched_analyze_reg().  */
1529                   if (!reg_rename_p->crosses_call
1530                       || REG_N_CALLS_CROSSED (orig_regno) > 0)
1531                     return gen_rtx_REG (mode, orig_regno);
1532                 }
1533
1534               bad_hard_regs = true;
1535             }
1536           else
1537             return dest;
1538         }
1539      }
1540
1541   *is_orig_reg_p_ptr = false;
1542
1543   /* We had some original hard registers that couldn't be used.
1544      Those were likely special.  Don't try to create a pseudo.  */
1545   if (bad_hard_regs)
1546     return NULL_RTX;
1547
1548   /* We haven't found a register from original operations.  Get a new one.
1549      FIXME: control register pressure somehow.  */
1550   {
1551     rtx new_reg = gen_reg_rtx (mode);
1552
1553     gcc_assert (mode != VOIDmode);
1554
1555     max_regno = max_reg_num ();
1556     maybe_extend_reg_info_p ();
1557     REG_N_CALLS_CROSSED (REGNO (new_reg)) = reg_rename_p->crosses_call ? 1 : 0;
1558
1559     return new_reg;
1560   }
1561 }
1562
1563 /* True when target of EXPR is available due to EXPR_TARGET_AVAILABLE,
1564    USED_REGS and REG_RENAME_P->UNAVAILABLE_HARD_REGS.  */
1565 static void
1566 verify_target_availability (expr_t expr, regset used_regs,
1567                             struct reg_rename *reg_rename_p)
1568 {
1569   unsigned n, i, regno;
1570   enum machine_mode mode;
1571   bool target_available, live_available, hard_available;
1572
1573   if (!REG_P (EXPR_LHS (expr)) || EXPR_TARGET_AVAILABLE (expr) < 0)
1574     return;
1575
1576   regno = expr_dest_regno (expr);
1577   mode = GET_MODE (EXPR_LHS (expr));
1578   target_available = EXPR_TARGET_AVAILABLE (expr) == 1;
1579   n = HARD_REGISTER_NUM_P (regno) ? hard_regno_nregs[regno][mode] : 1;
1580
1581   live_available = hard_available = true;
1582   for (i = 0; i < n; i++)
1583     {
1584       if (bitmap_bit_p (used_regs, regno + i))
1585         live_available = false;
1586       if (TEST_HARD_REG_BIT (reg_rename_p->unavailable_hard_regs, regno + i))
1587         hard_available = false;
1588     }
1589
1590   /* When target is not available, it may be due to hard register
1591      restrictions, e.g. crosses calls, so we check hard_available too.  */
1592   if (target_available)
1593     gcc_assert (live_available);
1594   else
1595     /* Check only if we haven't scheduled something on the previous fence,
1596        cause due to MAX_SOFTWARE_LOOKAHEAD_WINDOW_SIZE issues
1597        and having more than one fence, we may end having targ_un in a block
1598        in which successors target register is actually available.
1599
1600        The last condition handles the case when a dependence from a call insn
1601        was created in sched-deps.c for insns with destination registers that
1602        never crossed a call before, but do cross one after our code motion.
1603
1604        FIXME: in the latter case, we just uselessly called find_used_regs,
1605        because we can't move this expression with any other register
1606        as well.  */
1607     gcc_assert (scheduled_something_on_previous_fence || !live_available
1608                 || !hard_available
1609                 || (!reload_completed && reg_rename_p->crosses_call
1610                     && REG_N_CALLS_CROSSED (regno) == 0));
1611 }
1612
1613 /* Collect unavailable registers due to liveness for EXPR from BNDS
1614    into USED_REGS.  Save additional information about available
1615    registers and unavailable due to hardware restriction registers
1616    into REG_RENAME_P structure.  Save original insns into ORIGINAL_INSNS
1617    list.  */
1618 static void
1619 collect_unavailable_regs_from_bnds (expr_t expr, blist_t bnds, regset used_regs,
1620                                     struct reg_rename *reg_rename_p,
1621                                     def_list_t *original_insns)
1622 {
1623   for (; bnds; bnds = BLIST_NEXT (bnds))
1624     {
1625       bool res;
1626       av_set_t orig_ops = NULL;
1627       bnd_t bnd = BLIST_BND (bnds);
1628
1629       /* If the chosen best expr doesn't belong to current boundary,
1630          skip it.  */
1631       if (!av_set_is_in_p (BND_AV1 (bnd), EXPR_VINSN (expr)))
1632         continue;
1633
1634       /* Put in ORIG_OPS all exprs from this boundary that became
1635          RES on top.  */
1636       orig_ops = find_sequential_best_exprs (bnd, expr, false);
1637
1638       /* Compute used regs and OR it into the USED_REGS.  */
1639       res = find_used_regs (BND_TO (bnd), orig_ops, used_regs,
1640                             reg_rename_p, original_insns);
1641
1642       /* FIXME: the assert is true until we'd have several boundaries.  */
1643       gcc_assert (res);
1644       av_set_clear (&orig_ops);
1645     }
1646 }
1647
1648 /* Return TRUE if it is possible to replace LHSes of ORIG_INSNS with BEST_REG.
1649    If BEST_REG is valid, replace LHS of EXPR with it.  */
1650 static bool
1651 try_replace_dest_reg (ilist_t orig_insns, rtx best_reg, expr_t expr)
1652 {
1653   /* Try whether we'll be able to generate the insn
1654      'dest := best_reg' at the place of the original operation.  */
1655   for (; orig_insns; orig_insns = ILIST_NEXT (orig_insns))
1656     {
1657       insn_t orig_insn = DEF_LIST_DEF (orig_insns)->orig_insn;
1658
1659       gcc_assert (EXPR_SEPARABLE_P (INSN_EXPR (orig_insn)));
1660
1661       if (REGNO (best_reg) != REGNO (INSN_LHS (orig_insn))
1662           && (! replace_src_with_reg_ok_p (orig_insn, best_reg)
1663               || ! replace_dest_with_reg_ok_p (orig_insn, best_reg)))
1664         return false;
1665     }
1666
1667   /* Make sure that EXPR has the right destination
1668      register.  */
1669   if (expr_dest_regno (expr) != REGNO (best_reg))
1670     replace_dest_with_reg_in_expr (expr, best_reg);
1671   else
1672     EXPR_TARGET_AVAILABLE (expr) = 1;
1673
1674   return true;
1675 }
1676
1677 /* Select and assign best register to EXPR searching from BNDS.
1678    Set *IS_ORIG_REG_P to TRUE if original register was selected.
1679    Return FALSE if no register can be chosen, which could happen when:
1680    * EXPR_SEPARABLE_P is true but we were unable to find suitable register;
1681    * EXPR_SEPARABLE_P is false but the insn sets/clobbers one of the registers
1682      that are used on the moving path.  */
1683 static bool
1684 find_best_reg_for_expr (expr_t expr, blist_t bnds, bool *is_orig_reg_p)
1685 {
1686   static struct reg_rename reg_rename_data;
1687
1688   regset used_regs;
1689   def_list_t original_insns = NULL;
1690   bool reg_ok;
1691
1692   *is_orig_reg_p = false;
1693
1694   /* Don't bother to do anything if this insn doesn't set any registers.  */
1695   if (bitmap_empty_p (VINSN_REG_SETS (EXPR_VINSN (expr)))
1696       && bitmap_empty_p (VINSN_REG_CLOBBERS (EXPR_VINSN (expr))))
1697     return true;
1698
1699   used_regs = get_clear_regset_from_pool ();
1700   CLEAR_HARD_REG_SET (reg_rename_data.unavailable_hard_regs);
1701
1702   collect_unavailable_regs_from_bnds (expr, bnds, used_regs, &reg_rename_data,
1703                                       &original_insns);
1704
1705 #ifdef ENABLE_CHECKING
1706   /* If after reload, make sure we're working with hard regs here.  */
1707   if (reload_completed)
1708     {
1709       reg_set_iterator rsi;
1710       unsigned i;
1711
1712       EXECUTE_IF_SET_IN_REG_SET (used_regs, FIRST_PSEUDO_REGISTER, i, rsi)
1713         gcc_unreachable ();
1714     }
1715 #endif
1716
1717   if (EXPR_SEPARABLE_P (expr))
1718     {
1719       rtx best_reg = NULL_RTX;
1720       /* Check that we have computed availability of a target register
1721          correctly.  */
1722       verify_target_availability (expr, used_regs, &reg_rename_data);
1723
1724       /* Turn everything in hard regs after reload.  */
1725       if (reload_completed)
1726         {
1727           HARD_REG_SET hard_regs_used;
1728           REG_SET_TO_HARD_REG_SET (hard_regs_used, used_regs);
1729
1730           /* Join hard registers unavailable due to register class
1731              restrictions and live range intersection.  */
1732           IOR_HARD_REG_SET (hard_regs_used,
1733                             reg_rename_data.unavailable_hard_regs);
1734
1735           best_reg = choose_best_reg (hard_regs_used, &reg_rename_data,
1736                                       original_insns, is_orig_reg_p);
1737         }
1738       else
1739         best_reg = choose_best_pseudo_reg (used_regs, &reg_rename_data,
1740                                            original_insns, is_orig_reg_p);
1741
1742       if (!best_reg)
1743         reg_ok = false;
1744       else if (*is_orig_reg_p)
1745         {
1746           /* In case of unification BEST_REG may be different from EXPR's LHS
1747              when EXPR's LHS is unavailable, and there is another LHS among
1748              ORIGINAL_INSNS.  */
1749           reg_ok = try_replace_dest_reg (original_insns, best_reg, expr);
1750         }
1751       else
1752         {
1753           /* Forbid renaming of low-cost insns.  */
1754           if (sel_vinsn_cost (EXPR_VINSN (expr)) < 2)
1755             reg_ok = false;
1756           else
1757             reg_ok = try_replace_dest_reg (original_insns, best_reg, expr);
1758         }
1759     }
1760   else
1761     {
1762       /* If !EXPR_SCHEDULE_AS_RHS (EXPR), just make sure INSN doesn't set
1763          any of the HARD_REGS_USED set.  */
1764       if (vinsn_writes_one_of_regs_p (EXPR_VINSN (expr), used_regs,
1765                                       reg_rename_data.unavailable_hard_regs))
1766         {
1767           reg_ok = false;
1768           gcc_assert (EXPR_TARGET_AVAILABLE (expr) <= 0);
1769         }
1770       else
1771         {
1772           reg_ok = true;
1773           gcc_assert (EXPR_TARGET_AVAILABLE (expr) != 0);
1774         }
1775     }
1776
1777   ilist_clear (&original_insns);
1778   return_regset_to_pool (used_regs);
1779
1780   return reg_ok;
1781 }
1782 \f
1783
1784 /* Return true if dependence described by DS can be overcomed.  */
1785 static bool
1786 can_speculate_dep_p (ds_t ds)
1787 {
1788   if (spec_info == NULL)
1789     return false;
1790
1791   /* Leave only speculative data.  */
1792   ds &= SPECULATIVE;
1793
1794   if (ds == 0)
1795     return false;
1796
1797   {
1798     /* FIXME: make sched-deps.c produce only those non-hard dependencies,
1799        that we can overcome.  */
1800     ds_t spec_mask = spec_info->mask;
1801
1802     if ((ds & spec_mask) != ds)
1803       return false;
1804   }
1805
1806   if (ds_weak (ds) < spec_info->data_weakness_cutoff)
1807     return false;
1808
1809   return true;
1810 }
1811
1812 /* Get a speculation check instruction.
1813    C_EXPR is a speculative expression,
1814    CHECK_DS describes speculations that should be checked,
1815    ORIG_INSN is the original non-speculative insn in the stream.  */
1816 static insn_t
1817 create_speculation_check (expr_t c_expr, ds_t check_ds, insn_t orig_insn)
1818 {
1819   rtx check_pattern;
1820   rtx insn_rtx;
1821   insn_t insn;
1822   basic_block recovery_block;
1823   rtx label;
1824
1825   /* Create a recovery block if target is going to emit branchy check, or if
1826      ORIG_INSN was speculative already.  */
1827   if (targetm.sched.needs_block_p (check_ds)
1828       || EXPR_SPEC_DONE_DS (INSN_EXPR (orig_insn)) != 0)
1829     {
1830       recovery_block = sel_create_recovery_block (orig_insn);
1831       label = BB_HEAD (recovery_block);
1832     }
1833   else
1834     {
1835       recovery_block = NULL;
1836       label = NULL_RTX;
1837     }
1838
1839   /* Get pattern of the check.  */
1840   check_pattern = targetm.sched.gen_spec_check (EXPR_INSN_RTX (c_expr), label,
1841                                                 check_ds);
1842
1843   gcc_assert (check_pattern != NULL);
1844
1845   /* Emit check.  */
1846   insn_rtx = create_insn_rtx_from_pattern (check_pattern, label);
1847
1848   insn = sel_gen_insn_from_rtx_after (insn_rtx, INSN_EXPR (orig_insn),
1849                                       INSN_SEQNO (orig_insn), orig_insn);
1850
1851   /* Make check to be non-speculative.  */
1852   EXPR_SPEC_DONE_DS (INSN_EXPR (insn)) = 0;
1853   INSN_SPEC_CHECKED_DS (insn) = check_ds;
1854
1855   /* Decrease priority of check by difference of load/check instruction
1856      latencies.  */
1857   EXPR_PRIORITY (INSN_EXPR (insn)) -= (sel_vinsn_cost (INSN_VINSN (orig_insn))
1858                                        - sel_vinsn_cost (INSN_VINSN (insn)));
1859
1860   /* Emit copy of original insn (though with replaced target register,
1861      if needed) to the recovery block.  */
1862   if (recovery_block != NULL)
1863     {
1864       rtx twin_rtx;
1865
1866       twin_rtx = copy_rtx (PATTERN (EXPR_INSN_RTX (c_expr)));
1867       twin_rtx = create_insn_rtx_from_pattern (twin_rtx, NULL_RTX);
1868       sel_gen_recovery_insn_from_rtx_after (twin_rtx,
1869                                             INSN_EXPR (orig_insn),
1870                                             INSN_SEQNO (insn),
1871                                             bb_note (recovery_block));
1872     }
1873
1874   /* If we've generated a data speculation check, make sure
1875      that all the bookkeeping instruction we'll create during
1876      this move_op () will allocate an ALAT entry so that the
1877      check won't fail.
1878      In case of control speculation we must convert C_EXPR to control
1879      speculative mode, because failing to do so will bring us an exception
1880      thrown by the non-control-speculative load.  */
1881   check_ds = ds_get_max_dep_weak (check_ds);
1882   speculate_expr (c_expr, check_ds);
1883
1884   return insn;
1885 }
1886
1887 /* True when INSN is a "regN = regN" copy.  */
1888 static bool
1889 identical_copy_p (rtx insn)
1890 {
1891   rtx lhs, rhs, pat;
1892
1893   pat = PATTERN (insn);
1894
1895   if (GET_CODE (pat) != SET)
1896     return false;
1897
1898   lhs = SET_DEST (pat);
1899   if (!REG_P (lhs))
1900     return false;
1901
1902   rhs = SET_SRC (pat);
1903   if (!REG_P (rhs))
1904     return false;
1905
1906   return REGNO (lhs) == REGNO (rhs);
1907 }
1908
1909 /* Undo all transformations on *AV_PTR that were done when
1910    moving through INSN.  */
1911 static void
1912 undo_transformations (av_set_t *av_ptr, rtx insn)
1913 {
1914   av_set_iterator av_iter;
1915   expr_t expr;
1916   av_set_t new_set = NULL;
1917
1918   /* First, kill any EXPR that uses registers set by an insn.  This is
1919      required for correctness.  */
1920   FOR_EACH_EXPR_1 (expr, av_iter, av_ptr)
1921     if (!sched_insns_conditions_mutex_p (insn, EXPR_INSN_RTX (expr))
1922         && bitmap_intersect_p (INSN_REG_SETS (insn),
1923                                VINSN_REG_USES (EXPR_VINSN (expr)))
1924         /* When an insn looks like 'r1 = r1', we could substitute through
1925            it, but the above condition will still hold.  This happened with
1926            gcc.c-torture/execute/961125-1.c.  */
1927         && !identical_copy_p (insn))
1928       {
1929         if (sched_verbose >= 6)
1930           sel_print ("Expr %d removed due to use/set conflict\n",
1931                      INSN_UID (EXPR_INSN_RTX (expr)));
1932         av_set_iter_remove (&av_iter);
1933       }
1934
1935   /* Undo transformations looking at the history vector.  */
1936   FOR_EACH_EXPR (expr, av_iter, *av_ptr)
1937     {
1938       int index = find_in_history_vect (EXPR_HISTORY_OF_CHANGES (expr),
1939                                         insn, EXPR_VINSN (expr), true);
1940
1941       if (index >= 0)
1942         {
1943           expr_history_def *phist;
1944
1945           phist = VEC_index (expr_history_def,
1946                              EXPR_HISTORY_OF_CHANGES (expr),
1947                              index);
1948
1949           switch (phist->type)
1950             {
1951             case TRANS_SPECULATION:
1952               {
1953                 ds_t old_ds, new_ds;
1954
1955                 /* Compute the difference between old and new speculative
1956                    statuses: that's what we need to check.
1957                    Earlier we used to assert that the status will really
1958                    change.  This no longer works because only the probability
1959                    bits in the status may have changed during compute_av_set,
1960                    and in the case of merging different probabilities of the
1961                    same speculative status along different paths we do not
1962                    record this in the history vector.  */
1963                 old_ds = phist->spec_ds;
1964                 new_ds = EXPR_SPEC_DONE_DS (expr);
1965
1966                 old_ds &= SPECULATIVE;
1967                 new_ds &= SPECULATIVE;
1968                 new_ds &= ~old_ds;
1969
1970                 EXPR_SPEC_TO_CHECK_DS (expr) |= new_ds;
1971                 break;
1972               }
1973             case TRANS_SUBSTITUTION:
1974               {
1975                 expr_def _tmp_expr, *tmp_expr = &_tmp_expr;
1976                 vinsn_t new_vi;
1977                 bool add = true;
1978
1979                 new_vi = phist->old_expr_vinsn;
1980
1981                 gcc_assert (VINSN_SEPARABLE_P (new_vi)
1982                             == EXPR_SEPARABLE_P (expr));
1983                 copy_expr (tmp_expr, expr);
1984
1985                 if (vinsn_equal_p (phist->new_expr_vinsn,
1986                                    EXPR_VINSN (tmp_expr)))
1987                   change_vinsn_in_expr (tmp_expr, new_vi);
1988                 else
1989                   /* This happens when we're unsubstituting on a bookkeeping
1990                      copy, which was in turn substituted.  The history is wrong
1991                      in this case.  Do it the hard way.  */
1992                   add = substitute_reg_in_expr (tmp_expr, insn, true);
1993                 if (add)
1994                   av_set_add (&new_set, tmp_expr);
1995                 clear_expr (tmp_expr);
1996                 break;
1997               }
1998             default:
1999               gcc_unreachable ();
2000             }
2001         }
2002
2003     }
2004
2005   av_set_union_and_clear (av_ptr, &new_set, NULL);
2006 }
2007 \f
2008
2009 /* Moveup_* helpers for code motion and computing av sets.  */
2010
2011 /* Propagates EXPR inside an insn group through THROUGH_INSN.
2012    The difference from the below function is that only substitution is
2013    performed.  */
2014 static enum MOVEUP_EXPR_CODE
2015 moveup_expr_inside_insn_group (expr_t expr, insn_t through_insn)
2016 {
2017   vinsn_t vi = EXPR_VINSN (expr);
2018   ds_t *has_dep_p;
2019   ds_t full_ds;
2020
2021   /* Do this only inside insn group.  */
2022   gcc_assert (INSN_SCHED_CYCLE (through_insn) > 0);
2023
2024   full_ds = has_dependence_p (expr, through_insn, &has_dep_p);
2025   if (full_ds == 0)
2026     return MOVEUP_EXPR_SAME;
2027
2028   /* Substitution is the possible choice in this case.  */
2029   if (has_dep_p[DEPS_IN_RHS])
2030     {
2031       /* Can't substitute UNIQUE VINSNs.  */
2032       gcc_assert (!VINSN_UNIQUE_P (vi));
2033
2034       if (can_substitute_through_p (through_insn,
2035                                     has_dep_p[DEPS_IN_RHS])
2036           && substitute_reg_in_expr (expr, through_insn, false))
2037         {
2038           EXPR_WAS_SUBSTITUTED (expr) = true;
2039           return MOVEUP_EXPR_CHANGED;
2040         }
2041
2042       /* Don't care about this, as even true dependencies may be allowed
2043          in an insn group.  */
2044       return MOVEUP_EXPR_SAME;
2045     }
2046
2047   /* This can catch output dependencies in COND_EXECs.  */
2048   if (has_dep_p[DEPS_IN_INSN])
2049     return MOVEUP_EXPR_NULL;
2050
2051   /* This is either an output or an anti dependence, which usually have
2052      a zero latency.  Allow this here, if we'd be wrong, tick_check_p
2053      will fix this.  */
2054   gcc_assert (has_dep_p[DEPS_IN_LHS]);
2055   return MOVEUP_EXPR_AS_RHS;
2056 }
2057
2058 /* True when a trapping EXPR cannot be moved through THROUGH_INSN.  */
2059 #define CANT_MOVE_TRAPPING(expr, through_insn)                \
2060   (VINSN_MAY_TRAP_P (EXPR_VINSN (expr))                       \
2061    && !sel_insn_has_single_succ_p ((through_insn), SUCCS_ALL) \
2062    && !sel_insn_is_speculation_check (through_insn))
2063
2064 /* True when a conflict on a target register was found during moveup_expr.  */
2065 static bool was_target_conflict = false;
2066
2067 /* Return true when moving a debug INSN across THROUGH_INSN will
2068    create a bookkeeping block.  We don't want to create such blocks,
2069    for they would cause codegen differences between compilations with
2070    and without debug info.  */
2071
2072 static bool
2073 moving_insn_creates_bookkeeping_block_p (insn_t insn,
2074                                          insn_t through_insn)
2075 {
2076   basic_block bbi, bbt;
2077   edge e1, e2;
2078   edge_iterator ei1, ei2;
2079
2080   if (!bookkeeping_can_be_created_if_moved_through_p (through_insn))
2081     {
2082       if (sched_verbose >= 9)
2083         sel_print ("no bookkeeping required: ");
2084       return FALSE;
2085     }
2086
2087   bbi = BLOCK_FOR_INSN (insn);
2088
2089   if (EDGE_COUNT (bbi->preds) == 1)
2090     {
2091       if (sched_verbose >= 9)
2092         sel_print ("only one pred edge: ");
2093       return TRUE;
2094     }
2095
2096   bbt = BLOCK_FOR_INSN (through_insn);
2097
2098   FOR_EACH_EDGE (e1, ei1, bbt->succs)
2099     {
2100       FOR_EACH_EDGE (e2, ei2, bbi->preds)
2101         {
2102           if (find_block_for_bookkeeping (e1, e2, TRUE))
2103             {
2104               if (sched_verbose >= 9)
2105                 sel_print ("found existing block: ");
2106               return FALSE;
2107             }
2108         }
2109     }
2110
2111   if (sched_verbose >= 9)
2112     sel_print ("would create bookkeeping block: ");
2113
2114   return TRUE;
2115 }
2116
2117 /* Return true when the conflict with newly created implicit clobbers
2118    between EXPR and THROUGH_INSN is found because of renaming.  */
2119 static bool
2120 implicit_clobber_conflict_p (insn_t through_insn, expr_t expr)
2121 {
2122   HARD_REG_SET temp;
2123   rtx insn, reg, rhs, pat;
2124   hard_reg_set_iterator hrsi;
2125   unsigned regno;
2126   bool valid;
2127
2128   /* Make a new pseudo register.  */
2129   reg = gen_reg_rtx (GET_MODE (EXPR_LHS (expr)));
2130   max_regno = max_reg_num ();
2131   maybe_extend_reg_info_p ();
2132
2133   /* Validate a change and bail out early.  */
2134   insn = EXPR_INSN_RTX (expr);
2135   validate_change (insn, &SET_DEST (PATTERN (insn)), reg, true);
2136   valid = verify_changes (0);
2137   cancel_changes (0);
2138   if (!valid)
2139     {
2140       if (sched_verbose >= 6)
2141         sel_print ("implicit clobbers failed validation, ");
2142       return true;
2143     }
2144
2145   /* Make a new insn with it.  */
2146   rhs = copy_rtx (VINSN_RHS (EXPR_VINSN (expr)));
2147   pat = gen_rtx_SET (VOIDmode, reg, rhs);
2148   start_sequence ();
2149   insn = emit_insn (pat);
2150   end_sequence ();
2151
2152   /* Calculate implicit clobbers.  */
2153   extract_insn (insn);
2154   preprocess_constraints ();
2155   ira_implicitly_set_insn_hard_regs (&temp);
2156   AND_COMPL_HARD_REG_SET (temp, ira_no_alloc_regs);
2157
2158   /* If any implicit clobber registers intersect with regular ones in
2159      through_insn, we have a dependency and thus bail out.  */
2160   EXECUTE_IF_SET_IN_HARD_REG_SET (temp, 0, regno, hrsi)
2161     {
2162       vinsn_t vi = INSN_VINSN (through_insn);
2163       if (bitmap_bit_p (VINSN_REG_SETS (vi), regno)
2164           || bitmap_bit_p (VINSN_REG_CLOBBERS (vi), regno)
2165           || bitmap_bit_p (VINSN_REG_USES (vi), regno))
2166         return true;
2167     }
2168
2169   return false;
2170 }
2171
2172 /* Modifies EXPR so it can be moved through the THROUGH_INSN,
2173    performing necessary transformations.  Record the type of transformation
2174    made in PTRANS_TYPE, when it is not NULL.  When INSIDE_INSN_GROUP,
2175    permit all dependencies except true ones, and try to remove those
2176    too via forward substitution.  All cases when a non-eliminable
2177    non-zero cost dependency exists inside an insn group will be fixed
2178    in tick_check_p instead.  */
2179 static enum MOVEUP_EXPR_CODE
2180 moveup_expr (expr_t expr, insn_t through_insn, bool inside_insn_group,
2181             enum local_trans_type *ptrans_type)
2182 {
2183   vinsn_t vi = EXPR_VINSN (expr);
2184   insn_t insn = VINSN_INSN_RTX (vi);
2185   bool was_changed = false;
2186   bool as_rhs = false;
2187   ds_t *has_dep_p;
2188   ds_t full_ds;
2189
2190   /* ??? We use dependencies of non-debug insns on debug insns to
2191      indicate that the debug insns need to be reset if the non-debug
2192      insn is pulled ahead of it.  It's hard to figure out how to
2193      introduce such a notion in sel-sched, but it already fails to
2194      support debug insns in other ways, so we just go ahead and
2195      let the deug insns go corrupt for now.  */
2196   if (DEBUG_INSN_P (through_insn) && !DEBUG_INSN_P (insn))
2197     return MOVEUP_EXPR_SAME;
2198
2199   /* When inside_insn_group, delegate to the helper.  */
2200   if (inside_insn_group)
2201     return moveup_expr_inside_insn_group (expr, through_insn);
2202
2203   /* Deal with unique insns and control dependencies.  */
2204   if (VINSN_UNIQUE_P (vi))
2205     {
2206       /* We can move jumps without side-effects or jumps that are
2207          mutually exclusive with instruction THROUGH_INSN (all in cases
2208          dependencies allow to do so and jump is not speculative).  */
2209       if (control_flow_insn_p (insn))
2210         {
2211           basic_block fallthru_bb;
2212
2213           /* Do not move checks and do not move jumps through other
2214              jumps.  */
2215           if (control_flow_insn_p (through_insn)
2216               || sel_insn_is_speculation_check (insn))
2217             return MOVEUP_EXPR_NULL;
2218
2219           /* Don't move jumps through CFG joins.  */
2220           if (bookkeeping_can_be_created_if_moved_through_p (through_insn))
2221             return MOVEUP_EXPR_NULL;
2222
2223           /* The jump should have a clear fallthru block, and
2224              this block should be in the current region.  */
2225           if ((fallthru_bb = fallthru_bb_of_jump (insn)) == NULL
2226               || ! in_current_region_p (fallthru_bb))
2227             return MOVEUP_EXPR_NULL;
2228
2229           /* And it should be mutually exclusive with through_insn.  */
2230           if (! sched_insns_conditions_mutex_p (insn, through_insn)
2231               && ! DEBUG_INSN_P (through_insn))
2232             return MOVEUP_EXPR_NULL;
2233         }
2234
2235       /* Don't move what we can't move.  */
2236       if (EXPR_CANT_MOVE (expr)
2237           && BLOCK_FOR_INSN (through_insn) != BLOCK_FOR_INSN (insn))
2238         return MOVEUP_EXPR_NULL;
2239
2240       /* Don't move SCHED_GROUP instruction through anything.
2241          If we don't force this, then it will be possible to start
2242          scheduling a sched_group before all its dependencies are
2243          resolved.
2244          ??? Haifa deals with this issue by delaying the SCHED_GROUP
2245          as late as possible through rank_for_schedule.  */
2246       if (SCHED_GROUP_P (insn))
2247         return MOVEUP_EXPR_NULL;
2248     }
2249   else
2250     gcc_assert (!control_flow_insn_p (insn));
2251
2252   /* Don't move debug insns if this would require bookkeeping.  */
2253   if (DEBUG_INSN_P (insn)
2254       && BLOCK_FOR_INSN (through_insn) != BLOCK_FOR_INSN (insn)
2255       && moving_insn_creates_bookkeeping_block_p (insn, through_insn))
2256     return MOVEUP_EXPR_NULL;
2257
2258   /* Deal with data dependencies.  */
2259   was_target_conflict = false;
2260   full_ds = has_dependence_p (expr, through_insn, &has_dep_p);
2261   if (full_ds == 0)
2262     {
2263       if (!CANT_MOVE_TRAPPING (expr, through_insn))
2264         return MOVEUP_EXPR_SAME;
2265     }
2266   else
2267     {
2268       /* We can move UNIQUE insn up only as a whole and unchanged,
2269          so it shouldn't have any dependencies.  */
2270       if (VINSN_UNIQUE_P (vi))
2271         return MOVEUP_EXPR_NULL;
2272     }
2273
2274   if (full_ds != 0 && can_speculate_dep_p (full_ds))
2275     {
2276       int res;
2277
2278       res = speculate_expr (expr, full_ds);
2279       if (res >= 0)
2280         {
2281           /* Speculation was successful.  */
2282           full_ds = 0;
2283           was_changed = (res > 0);
2284           if (res == 2)
2285             was_target_conflict = true;
2286           if (ptrans_type)
2287             *ptrans_type = TRANS_SPECULATION;
2288           sel_clear_has_dependence ();
2289         }
2290     }
2291
2292   if (has_dep_p[DEPS_IN_INSN])
2293     /* We have some dependency that cannot be discarded.  */
2294     return MOVEUP_EXPR_NULL;
2295
2296   if (has_dep_p[DEPS_IN_LHS])
2297     {
2298       /* Only separable insns can be moved up with the new register.
2299          Anyways, we should mark that the original register is
2300          unavailable.  */
2301       if (!enable_schedule_as_rhs_p || !EXPR_SEPARABLE_P (expr))
2302         return MOVEUP_EXPR_NULL;
2303
2304       /* When renaming a hard register to a pseudo before reload, extra
2305          dependencies can occur from the implicit clobbers of the insn.
2306          Filter out such cases here.  */
2307       if (!reload_completed && REG_P (EXPR_LHS (expr))
2308           && HARD_REGISTER_P (EXPR_LHS (expr))
2309           && implicit_clobber_conflict_p (through_insn, expr))
2310         {
2311           if (sched_verbose >= 6)
2312             sel_print ("implicit clobbers conflict detected, ");
2313           return MOVEUP_EXPR_NULL;
2314         }
2315       EXPR_TARGET_AVAILABLE (expr) = false;
2316       was_target_conflict = true;
2317       as_rhs = true;
2318     }
2319
2320   /* At this point we have either separable insns, that will be lifted
2321      up only as RHSes, or non-separable insns with no dependency in lhs.
2322      If dependency is in RHS, then try to perform substitution and move up
2323      substituted RHS:
2324
2325       Ex. 1:                              Ex.2
2326         y = x;                              y = x;
2327         z = y*2;                            y = y*2;
2328
2329     In Ex.1 y*2 can be substituted for x*2 and the whole operation can be
2330     moved above y=x assignment as z=x*2.
2331
2332     In Ex.2 y*2 also can be substituted for x*2, but only the right hand
2333     side can be moved because of the output dependency.  The operation was
2334     cropped to its rhs above.  */
2335   if (has_dep_p[DEPS_IN_RHS])
2336     {
2337       ds_t *rhs_dsp = &has_dep_p[DEPS_IN_RHS];
2338
2339       /* Can't substitute UNIQUE VINSNs.  */
2340       gcc_assert (!VINSN_UNIQUE_P (vi));
2341
2342       if (can_speculate_dep_p (*rhs_dsp))
2343         {
2344           int res;
2345
2346           res = speculate_expr (expr, *rhs_dsp);
2347           if (res >= 0)
2348             {
2349               /* Speculation was successful.  */
2350               *rhs_dsp = 0;
2351               was_changed = (res > 0);
2352               if (res == 2)
2353                 was_target_conflict = true;
2354               if (ptrans_type)
2355                 *ptrans_type = TRANS_SPECULATION;
2356             }
2357           else
2358             return MOVEUP_EXPR_NULL;
2359         }
2360       else if (can_substitute_through_p (through_insn,
2361                                          *rhs_dsp)
2362                && substitute_reg_in_expr (expr, through_insn, false))
2363         {
2364           /* ??? We cannot perform substitution AND speculation on the same
2365              insn.  */
2366           gcc_assert (!was_changed);
2367           was_changed = true;
2368           if (ptrans_type)
2369             *ptrans_type = TRANS_SUBSTITUTION;
2370           EXPR_WAS_SUBSTITUTED (expr) = true;
2371         }
2372       else
2373         return MOVEUP_EXPR_NULL;
2374     }
2375
2376   /* Don't move trapping insns through jumps.
2377      This check should be at the end to give a chance to control speculation
2378      to perform its duties.  */
2379   if (CANT_MOVE_TRAPPING (expr, through_insn))
2380     return MOVEUP_EXPR_NULL;
2381
2382   return (was_changed
2383           ? MOVEUP_EXPR_CHANGED
2384           : (as_rhs
2385              ? MOVEUP_EXPR_AS_RHS
2386              : MOVEUP_EXPR_SAME));
2387 }
2388
2389 /* Try to look at bitmap caches for EXPR and INSN pair, return true
2390    if successful.  When INSIDE_INSN_GROUP, also try ignore dependencies
2391    that can exist within a parallel group.  Write to RES the resulting
2392    code for moveup_expr.  */
2393 static bool
2394 try_bitmap_cache (expr_t expr, insn_t insn,
2395                   bool inside_insn_group,
2396                   enum MOVEUP_EXPR_CODE *res)
2397 {
2398   int expr_uid = INSN_UID (EXPR_INSN_RTX (expr));
2399
2400   /* First check whether we've analyzed this situation already.  */
2401   if (bitmap_bit_p (INSN_ANALYZED_DEPS (insn), expr_uid))
2402     {
2403       if (bitmap_bit_p (INSN_FOUND_DEPS (insn), expr_uid))
2404         {
2405           if (sched_verbose >= 6)
2406             sel_print ("removed (cached)\n");
2407           *res = MOVEUP_EXPR_NULL;
2408           return true;
2409         }
2410       else
2411         {
2412           if (sched_verbose >= 6)
2413             sel_print ("unchanged (cached)\n");
2414           *res = MOVEUP_EXPR_SAME;
2415           return true;
2416         }
2417     }
2418   else if (bitmap_bit_p (INSN_FOUND_DEPS (insn), expr_uid))
2419     {
2420       if (inside_insn_group)
2421         {
2422           if (sched_verbose >= 6)
2423             sel_print ("unchanged (as RHS, cached, inside insn group)\n");
2424           *res = MOVEUP_EXPR_SAME;
2425           return true;
2426
2427         }
2428       else
2429         EXPR_TARGET_AVAILABLE (expr) = false;
2430
2431       /* This is the only case when propagation result can change over time,
2432          as we can dynamically switch off scheduling as RHS.  In this case,
2433          just check the flag to reach the correct decision.  */
2434       if (enable_schedule_as_rhs_p)
2435         {
2436           if (sched_verbose >= 6)
2437             sel_print ("unchanged (as RHS, cached)\n");
2438           *res = MOVEUP_EXPR_AS_RHS;
2439           return true;
2440         }
2441       else
2442         {
2443           if (sched_verbose >= 6)
2444             sel_print ("removed (cached as RHS, but renaming"
2445                        " is now disabled)\n");
2446           *res = MOVEUP_EXPR_NULL;
2447           return true;
2448         }
2449     }
2450
2451   return false;
2452 }
2453
2454 /* Try to look at bitmap caches for EXPR and INSN pair, return true
2455    if successful.  Write to RES the resulting code for moveup_expr.  */
2456 static bool
2457 try_transformation_cache (expr_t expr, insn_t insn,
2458                           enum MOVEUP_EXPR_CODE *res)
2459 {
2460   struct transformed_insns *pti
2461     = (struct transformed_insns *)
2462     htab_find_with_hash (INSN_TRANSFORMED_INSNS (insn),
2463                          &EXPR_VINSN (expr),
2464                          VINSN_HASH_RTX (EXPR_VINSN (expr)));
2465   if (pti)
2466     {
2467       /* This EXPR was already moved through this insn and was
2468          changed as a result.  Fetch the proper data from
2469          the hashtable.  */
2470       insert_in_history_vect (&EXPR_HISTORY_OF_CHANGES (expr),
2471                               INSN_UID (insn), pti->type,
2472                               pti->vinsn_old, pti->vinsn_new,
2473                               EXPR_SPEC_DONE_DS (expr));
2474
2475       if (INSN_IN_STREAM_P (VINSN_INSN_RTX (pti->vinsn_new)))
2476         pti->vinsn_new = vinsn_copy (pti->vinsn_new, true);
2477       change_vinsn_in_expr (expr, pti->vinsn_new);
2478       if (pti->was_target_conflict)
2479         EXPR_TARGET_AVAILABLE (expr) = false;
2480       if (pti->type == TRANS_SPECULATION)
2481         {
2482           EXPR_SPEC_DONE_DS (expr) = pti->ds;
2483           EXPR_NEEDS_SPEC_CHECK_P (expr) |= pti->needs_check;
2484         }
2485
2486       if (sched_verbose >= 6)
2487         {
2488           sel_print ("changed (cached): ");
2489           dump_expr (expr);
2490           sel_print ("\n");
2491         }
2492
2493       *res = MOVEUP_EXPR_CHANGED;
2494       return true;
2495     }
2496
2497   return false;
2498 }
2499
2500 /* Update bitmap caches on INSN with result RES of propagating EXPR.  */
2501 static void
2502 update_bitmap_cache (expr_t expr, insn_t insn, bool inside_insn_group,
2503                      enum MOVEUP_EXPR_CODE res)
2504 {
2505   int expr_uid = INSN_UID (EXPR_INSN_RTX (expr));
2506
2507   /* Do not cache result of propagating jumps through an insn group,
2508      as it is always true, which is not useful outside the group.  */
2509   if (inside_insn_group)
2510     return;
2511
2512   if (res == MOVEUP_EXPR_NULL)
2513     {
2514       bitmap_set_bit (INSN_ANALYZED_DEPS (insn), expr_uid);
2515       bitmap_set_bit (INSN_FOUND_DEPS (insn), expr_uid);
2516     }
2517   else if (res == MOVEUP_EXPR_SAME)
2518     {
2519       bitmap_set_bit (INSN_ANALYZED_DEPS (insn), expr_uid);
2520       bitmap_clear_bit (INSN_FOUND_DEPS (insn), expr_uid);
2521     }
2522   else if (res == MOVEUP_EXPR_AS_RHS)
2523     {
2524       bitmap_clear_bit (INSN_ANALYZED_DEPS (insn), expr_uid);
2525       bitmap_set_bit (INSN_FOUND_DEPS (insn), expr_uid);
2526     }
2527   else
2528     gcc_unreachable ();
2529 }
2530
2531 /* Update hashtable on INSN with changed EXPR, old EXPR_OLD_VINSN
2532    and transformation type TRANS_TYPE.  */
2533 static void
2534 update_transformation_cache (expr_t expr, insn_t insn,
2535                              bool inside_insn_group,
2536                              enum local_trans_type trans_type,
2537                              vinsn_t expr_old_vinsn)
2538 {
2539   struct transformed_insns *pti;
2540
2541   if (inside_insn_group)
2542     return;
2543
2544   pti = XNEW (struct transformed_insns);
2545   pti->vinsn_old = expr_old_vinsn;
2546   pti->vinsn_new = EXPR_VINSN (expr);
2547   pti->type = trans_type;
2548   pti->was_target_conflict = was_target_conflict;
2549   pti->ds = EXPR_SPEC_DONE_DS (expr);
2550   pti->needs_check = EXPR_NEEDS_SPEC_CHECK_P (expr);
2551   vinsn_attach (pti->vinsn_old);
2552   vinsn_attach (pti->vinsn_new);
2553   *((struct transformed_insns **)
2554     htab_find_slot_with_hash (INSN_TRANSFORMED_INSNS (insn),
2555                               pti, VINSN_HASH_RTX (expr_old_vinsn),
2556                               INSERT)) = pti;
2557 }
2558
2559 /* Same as moveup_expr, but first looks up the result of
2560    transformation in caches.  */
2561 static enum MOVEUP_EXPR_CODE
2562 moveup_expr_cached (expr_t expr, insn_t insn, bool inside_insn_group)
2563 {
2564   enum MOVEUP_EXPR_CODE res;
2565   bool got_answer = false;
2566
2567   if (sched_verbose >= 6)
2568     {
2569       sel_print ("Moving ");
2570       dump_expr (expr);
2571       sel_print (" through %d: ", INSN_UID (insn));
2572     }
2573
2574   if (DEBUG_INSN_P (EXPR_INSN_RTX (expr))
2575       && (sel_bb_head (BLOCK_FOR_INSN (EXPR_INSN_RTX (expr)))
2576           == EXPR_INSN_RTX (expr)))
2577     /* Don't use cached information for debug insns that are heads of
2578        basic blocks.  */;
2579   else if (try_bitmap_cache (expr, insn, inside_insn_group, &res))
2580     /* When inside insn group, we do not want remove stores conflicting
2581        with previosly issued loads.  */
2582     got_answer = ! inside_insn_group || res != MOVEUP_EXPR_NULL;
2583   else if (try_transformation_cache (expr, insn, &res))
2584     got_answer = true;
2585
2586   if (! got_answer)
2587     {
2588       /* Invoke moveup_expr and record the results.  */
2589       vinsn_t expr_old_vinsn = EXPR_VINSN (expr);
2590       ds_t expr_old_spec_ds = EXPR_SPEC_DONE_DS (expr);
2591       int expr_uid = INSN_UID (VINSN_INSN_RTX (expr_old_vinsn));
2592       bool unique_p = VINSN_UNIQUE_P (expr_old_vinsn);
2593       enum local_trans_type trans_type = TRANS_SUBSTITUTION;
2594
2595       /* ??? Invent something better than this.  We can't allow old_vinsn
2596          to go, we need it for the history vector.  */
2597       vinsn_attach (expr_old_vinsn);
2598
2599       res = moveup_expr (expr, insn, inside_insn_group,
2600                          &trans_type);
2601       switch (res)
2602         {
2603         case MOVEUP_EXPR_NULL:
2604           update_bitmap_cache (expr, insn, inside_insn_group, res);
2605           if (sched_verbose >= 6)
2606             sel_print ("removed\n");
2607           break;
2608
2609         case MOVEUP_EXPR_SAME:
2610           update_bitmap_cache (expr, insn, inside_insn_group, res);
2611           if (sched_verbose >= 6)
2612             sel_print ("unchanged\n");
2613           break;
2614
2615         case MOVEUP_EXPR_AS_RHS:
2616           gcc_assert (!unique_p || inside_insn_group);
2617           update_bitmap_cache (expr, insn, inside_insn_group, res);
2618           if (sched_verbose >= 6)
2619             sel_print ("unchanged (as RHS)\n");
2620           break;
2621
2622         case MOVEUP_EXPR_CHANGED:
2623           gcc_assert (INSN_UID (EXPR_INSN_RTX (expr)) != expr_uid
2624                       || EXPR_SPEC_DONE_DS (expr) != expr_old_spec_ds);
2625           insert_in_history_vect (&EXPR_HISTORY_OF_CHANGES (expr),
2626                                   INSN_UID (insn), trans_type,
2627                                   expr_old_vinsn, EXPR_VINSN (expr),
2628                                   expr_old_spec_ds);
2629           update_transformation_cache (expr, insn, inside_insn_group,
2630                                        trans_type, expr_old_vinsn);
2631           if (sched_verbose >= 6)
2632             {
2633               sel_print ("changed: ");
2634               dump_expr (expr);
2635               sel_print ("\n");
2636             }
2637           break;
2638         default:
2639           gcc_unreachable ();
2640         }
2641
2642       vinsn_detach (expr_old_vinsn);
2643     }
2644
2645   return res;
2646 }
2647
2648 /* Moves an av set AVP up through INSN, performing necessary
2649    transformations.  */
2650 static void
2651 moveup_set_expr (av_set_t *avp, insn_t insn, bool inside_insn_group)
2652 {
2653   av_set_iterator i;
2654   expr_t expr;
2655
2656   FOR_EACH_EXPR_1 (expr, i, avp)
2657     {
2658
2659       switch (moveup_expr_cached (expr, insn, inside_insn_group))
2660         {
2661         case MOVEUP_EXPR_SAME:
2662         case MOVEUP_EXPR_AS_RHS:
2663           break;
2664
2665         case MOVEUP_EXPR_NULL:
2666           av_set_iter_remove (&i);
2667           break;
2668
2669         case MOVEUP_EXPR_CHANGED:
2670           expr = merge_with_other_exprs (avp, &i, expr);
2671           break;
2672
2673         default:
2674           gcc_unreachable ();
2675         }
2676     }
2677 }
2678
2679 /* Moves AVP set along PATH.  */
2680 static void
2681 moveup_set_inside_insn_group (av_set_t *avp, ilist_t path)
2682 {
2683   int last_cycle;
2684
2685   if (sched_verbose >= 6)
2686     sel_print ("Moving expressions up in the insn group...\n");
2687   if (! path)
2688     return;
2689   last_cycle = INSN_SCHED_CYCLE (ILIST_INSN (path));
2690   while (path
2691          && INSN_SCHED_CYCLE (ILIST_INSN (path)) == last_cycle)
2692     {
2693       moveup_set_expr (avp, ILIST_INSN (path), true);
2694       path = ILIST_NEXT (path);
2695     }
2696 }
2697
2698 /* Returns true if after moving EXPR along PATH it equals to EXPR_VLIW.  */
2699 static bool
2700 equal_after_moveup_path_p (expr_t expr, ilist_t path, expr_t expr_vliw)
2701 {
2702   expr_def _tmp, *tmp = &_tmp;
2703   int last_cycle;
2704   bool res = true;
2705
2706   copy_expr_onside (tmp, expr);
2707   last_cycle = path ? INSN_SCHED_CYCLE (ILIST_INSN (path)) : 0;
2708   while (path
2709          && res
2710          && INSN_SCHED_CYCLE (ILIST_INSN (path)) == last_cycle)
2711     {
2712       res = (moveup_expr_cached (tmp, ILIST_INSN (path), true)
2713              != MOVEUP_EXPR_NULL);
2714       path = ILIST_NEXT (path);
2715     }
2716
2717   if (res)
2718     {
2719       vinsn_t tmp_vinsn = EXPR_VINSN (tmp);
2720       vinsn_t expr_vliw_vinsn = EXPR_VINSN (expr_vliw);
2721
2722       if (tmp_vinsn != expr_vliw_vinsn)
2723         res = vinsn_equal_p (tmp_vinsn, expr_vliw_vinsn);
2724     }
2725
2726   clear_expr (tmp);
2727   return res;
2728 }
2729 \f
2730
2731 /* Functions that compute av and lv sets.  */
2732
2733 /* Returns true if INSN is not a downward continuation of the given path P in
2734    the current stage.  */
2735 static bool
2736 is_ineligible_successor (insn_t insn, ilist_t p)
2737 {
2738   insn_t prev_insn;
2739
2740   /* Check if insn is not deleted.  */
2741   if (PREV_INSN (insn) && NEXT_INSN (PREV_INSN (insn)) != insn)
2742     gcc_unreachable ();
2743   else if (NEXT_INSN (insn) && PREV_INSN (NEXT_INSN (insn)) != insn)
2744     gcc_unreachable ();
2745
2746   /* If it's the first insn visited, then the successor is ok.  */
2747   if (!p)
2748     return false;
2749
2750   prev_insn = ILIST_INSN (p);
2751
2752   if (/* a backward edge.  */
2753       INSN_SEQNO (insn) < INSN_SEQNO (prev_insn)
2754       /* is already visited.  */
2755       || (INSN_SEQNO (insn) == INSN_SEQNO (prev_insn)
2756           && (ilist_is_in_p (p, insn)
2757               /* We can reach another fence here and still seqno of insn
2758                  would be equal to seqno of prev_insn.  This is possible
2759                  when prev_insn is a previously created bookkeeping copy.
2760                  In that case it'd get a seqno of insn.  Thus, check here
2761                  whether insn is in current fence too.  */
2762               || IN_CURRENT_FENCE_P (insn)))
2763       /* Was already scheduled on this round.  */
2764       || (INSN_SEQNO (insn) > INSN_SEQNO (prev_insn)
2765           && IN_CURRENT_FENCE_P (insn))
2766       /* An insn from another fence could also be
2767          scheduled earlier even if this insn is not in
2768          a fence list right now.  Check INSN_SCHED_CYCLE instead.  */
2769       || (!pipelining_p
2770           && INSN_SCHED_TIMES (insn) > 0))
2771     return true;
2772   else
2773     return false;
2774 }
2775
2776 /* Computes the av_set below the last bb insn INSN, doing all the 'dirty work'
2777    of handling multiple successors and properly merging its av_sets.  P is
2778    the current path traversed.  WS is the size of lookahead window.
2779    Return the av set computed.  */
2780 static av_set_t
2781 compute_av_set_at_bb_end (insn_t insn, ilist_t p, int ws)
2782 {
2783   struct succs_info *sinfo;
2784   av_set_t expr_in_all_succ_branches = NULL;
2785   int is;
2786   insn_t succ, zero_succ = NULL;
2787   av_set_t av1 = NULL;
2788
2789   gcc_assert (sel_bb_end_p (insn));
2790
2791   /* Find different kind of successors needed for correct computing of
2792      SPEC and TARGET_AVAILABLE attributes.  */
2793   sinfo = compute_succs_info (insn, SUCCS_NORMAL);
2794
2795   /* Debug output.  */
2796   if (sched_verbose >= 6)
2797     {
2798       sel_print ("successors of bb end (%d): ", INSN_UID (insn));
2799       dump_insn_vector (sinfo->succs_ok);
2800       sel_print ("\n");
2801       if (sinfo->succs_ok_n != sinfo->all_succs_n)
2802         sel_print ("real successors num: %d\n", sinfo->all_succs_n);
2803     }
2804
2805   /* Add insn to the tail of current path.  */
2806   ilist_add (&p, insn);
2807
2808   FOR_EACH_VEC_ELT (rtx, sinfo->succs_ok, is, succ)
2809     {
2810       av_set_t succ_set;
2811
2812       /* We will edit SUCC_SET and EXPR_SPEC field of its elements.  */
2813       succ_set = compute_av_set_inside_bb (succ, p, ws, true);
2814
2815       av_set_split_usefulness (succ_set,
2816                                VEC_index (int, sinfo->probs_ok, is),
2817                                sinfo->all_prob);
2818
2819       if (sinfo->all_succs_n > 1)
2820         {
2821           /* Find EXPR'es that came from *all* successors and save them
2822              into expr_in_all_succ_branches.  This set will be used later
2823              for calculating speculation attributes of EXPR'es.  */
2824           if (is == 0)
2825             {
2826               expr_in_all_succ_branches = av_set_copy (succ_set);
2827
2828               /* Remember the first successor for later. */
2829               zero_succ = succ;
2830             }
2831           else
2832             {
2833               av_set_iterator i;
2834               expr_t expr;
2835
2836               FOR_EACH_EXPR_1 (expr, i, &expr_in_all_succ_branches)
2837                 if (!av_set_is_in_p (succ_set, EXPR_VINSN (expr)))
2838                   av_set_iter_remove (&i);
2839             }
2840         }
2841
2842       /* Union the av_sets.  Check liveness restrictions on target registers
2843          in special case of two successors.  */
2844       if (sinfo->succs_ok_n == 2 && is == 1)
2845         {
2846           basic_block bb0 = BLOCK_FOR_INSN (zero_succ);
2847           basic_block bb1 = BLOCK_FOR_INSN (succ);
2848
2849           gcc_assert (BB_LV_SET_VALID_P (bb0) && BB_LV_SET_VALID_P (bb1));
2850           av_set_union_and_live (&av1, &succ_set,
2851                                  BB_LV_SET (bb0),
2852                                  BB_LV_SET (bb1),
2853                                  insn);
2854         }
2855       else
2856         av_set_union_and_clear (&av1, &succ_set, insn);
2857     }
2858
2859   /* Check liveness restrictions via hard way when there are more than
2860      two successors.  */
2861   if (sinfo->succs_ok_n > 2)
2862     FOR_EACH_VEC_ELT (rtx, sinfo->succs_ok, is, succ)
2863       {
2864         basic_block succ_bb = BLOCK_FOR_INSN (succ);
2865
2866         gcc_assert (BB_LV_SET_VALID_P (succ_bb));
2867         mark_unavailable_targets (av1, BB_AV_SET (succ_bb),
2868                                   BB_LV_SET (succ_bb));
2869       }
2870
2871   /* Finally, check liveness restrictions on paths leaving the region.  */
2872   if (sinfo->all_succs_n > sinfo->succs_ok_n)
2873     FOR_EACH_VEC_ELT (rtx, sinfo->succs_other, is, succ)
2874       mark_unavailable_targets
2875         (av1, NULL, BB_LV_SET (BLOCK_FOR_INSN (succ)));
2876
2877   if (sinfo->all_succs_n > 1)
2878     {
2879       av_set_iterator i;
2880       expr_t expr;
2881
2882       /* Increase the spec attribute of all EXPR'es that didn't come
2883          from all successors.  */
2884       FOR_EACH_EXPR (expr, i, av1)
2885         if (!av_set_is_in_p (expr_in_all_succ_branches, EXPR_VINSN (expr)))
2886           EXPR_SPEC (expr)++;
2887
2888       av_set_clear (&expr_in_all_succ_branches);
2889
2890       /* Do not move conditional branches through other
2891          conditional branches.  So, remove all conditional
2892          branches from av_set if current operator is a conditional
2893          branch.  */
2894       av_set_substract_cond_branches (&av1);
2895     }
2896
2897   ilist_remove (&p);
2898   free_succs_info (sinfo);
2899
2900   if (sched_verbose >= 6)
2901     {
2902       sel_print ("av_succs (%d): ", INSN_UID (insn));
2903       dump_av_set (av1);
2904       sel_print ("\n");
2905     }
2906
2907   return av1;
2908 }
2909
2910 /* This function computes av_set for the FIRST_INSN by dragging valid
2911    av_set through all basic block insns either from the end of basic block
2912    (computed using compute_av_set_at_bb_end) or from the insn on which
2913    MAX_WS was exceeded.  It uses compute_av_set_at_bb_end to compute av_set
2914    below the basic block and handling conditional branches.
2915    FIRST_INSN - the basic block head, P - path consisting of the insns
2916    traversed on the way to the FIRST_INSN (the path is sparse, only bb heads
2917    and bb ends are added to the path), WS - current window size,
2918    NEED_COPY_P - true if we'll make a copy of av_set before returning it.  */
2919 static av_set_t
2920 compute_av_set_inside_bb (insn_t first_insn, ilist_t p, int ws,
2921                           bool need_copy_p)
2922 {
2923   insn_t cur_insn;
2924   int end_ws = ws;
2925   insn_t bb_end = sel_bb_end (BLOCK_FOR_INSN (first_insn));
2926   insn_t after_bb_end = NEXT_INSN (bb_end);
2927   insn_t last_insn;
2928   av_set_t av = NULL;
2929   basic_block cur_bb = BLOCK_FOR_INSN (first_insn);
2930
2931   /* Return NULL if insn is not on the legitimate downward path.  */
2932   if (is_ineligible_successor (first_insn, p))
2933     {
2934       if (sched_verbose >= 6)
2935         sel_print ("Insn %d is ineligible_successor\n", INSN_UID (first_insn));
2936
2937       return NULL;
2938     }
2939
2940   /* If insn already has valid av(insn) computed, just return it.  */
2941   if (AV_SET_VALID_P (first_insn))
2942     {
2943       av_set_t av_set;
2944
2945       if (sel_bb_head_p (first_insn))
2946         av_set = BB_AV_SET (BLOCK_FOR_INSN (first_insn));
2947       else
2948         av_set = NULL;
2949
2950       if (sched_verbose >= 6)
2951         {
2952           sel_print ("Insn %d has a valid av set: ", INSN_UID (first_insn));
2953           dump_av_set (av_set);
2954           sel_print ("\n");
2955         }
2956
2957       return need_copy_p ? av_set_copy (av_set) : av_set;
2958     }
2959
2960   ilist_add (&p, first_insn);
2961
2962   /* As the result after this loop have completed, in LAST_INSN we'll
2963      have the insn which has valid av_set to start backward computation
2964      from: it either will be NULL because on it the window size was exceeded
2965      or other valid av_set as returned by compute_av_set for the last insn
2966      of the basic block.  */
2967   for (last_insn = first_insn; last_insn != after_bb_end;
2968        last_insn = NEXT_INSN (last_insn))
2969     {
2970       /* We may encounter valid av_set not only on bb_head, but also on
2971          those insns on which previously MAX_WS was exceeded.  */
2972       if (AV_SET_VALID_P (last_insn))
2973         {
2974           if (sched_verbose >= 6)
2975             sel_print ("Insn %d has a valid empty av set\n", INSN_UID (last_insn));
2976           break;
2977         }
2978
2979       /* The special case: the last insn of the BB may be an
2980          ineligible_successor due to its SEQ_NO that was set on
2981          it as a bookkeeping.  */
2982       if (last_insn != first_insn
2983           && is_ineligible_successor (last_insn, p))
2984         {
2985           if (sched_verbose >= 6)
2986             sel_print ("Insn %d is ineligible_successor\n", INSN_UID (last_insn));
2987           break;
2988         }
2989
2990       if (DEBUG_INSN_P (last_insn))
2991         continue;
2992
2993       if (end_ws > max_ws)
2994         {
2995           /* We can reach max lookahead size at bb_header, so clean av_set
2996              first.  */
2997           INSN_WS_LEVEL (last_insn) = global_level;
2998
2999           if (sched_verbose >= 6)
3000             sel_print ("Insn %d is beyond the software lookahead window size\n",
3001                        INSN_UID (last_insn));
3002           break;
3003         }
3004
3005       end_ws++;
3006     }
3007
3008   /* Get the valid av_set into AV above the LAST_INSN to start backward
3009      computation from.  It either will be empty av_set or av_set computed from
3010      the successors on the last insn of the current bb.  */
3011   if (last_insn != after_bb_end)
3012     {
3013       av = NULL;
3014
3015       /* This is needed only to obtain av_sets that are identical to
3016          those computed by the old compute_av_set version.  */
3017       if (last_insn == first_insn && !INSN_NOP_P (last_insn))
3018         av_set_add (&av, INSN_EXPR (last_insn));
3019     }
3020   else
3021     /* END_WS is always already increased by 1 if LAST_INSN == AFTER_BB_END.  */
3022     av = compute_av_set_at_bb_end (bb_end, p, end_ws);
3023
3024   /* Compute av_set in AV starting from below the LAST_INSN up to
3025      location above the FIRST_INSN.  */
3026   for (cur_insn = PREV_INSN (last_insn); cur_insn != PREV_INSN (first_insn);
3027        cur_insn = PREV_INSN (cur_insn))
3028     if (!INSN_NOP_P (cur_insn))
3029       {
3030         expr_t expr;
3031
3032         moveup_set_expr (&av, cur_insn, false);
3033
3034         /* If the expression for CUR_INSN is already in the set,
3035            replace it by the new one.  */
3036         expr = av_set_lookup (av, INSN_VINSN (cur_insn));
3037         if (expr != NULL)
3038           {
3039             clear_expr (expr);
3040             copy_expr (expr, INSN_EXPR (cur_insn));
3041           }
3042         else
3043           av_set_add (&av, INSN_EXPR (cur_insn));
3044       }
3045
3046   /* Clear stale bb_av_set.  */
3047   if (sel_bb_head_p (first_insn))
3048     {
3049       av_set_clear (&BB_AV_SET (cur_bb));
3050       BB_AV_SET (cur_bb) = need_copy_p ? av_set_copy (av) : av;
3051       BB_AV_LEVEL (cur_bb) = global_level;
3052     }
3053
3054   if (sched_verbose >= 6)
3055     {
3056       sel_print ("Computed av set for insn %d: ", INSN_UID (first_insn));
3057       dump_av_set (av);
3058       sel_print ("\n");
3059     }
3060
3061   ilist_remove (&p);
3062   return av;
3063 }
3064
3065 /* Compute av set before INSN.
3066    INSN - the current operation (actual rtx INSN)
3067    P - the current path, which is list of insns visited so far
3068    WS - software lookahead window size.
3069    UNIQUE_P - TRUE, if returned av_set will be changed, hence
3070    if we want to save computed av_set in s_i_d, we should make a copy of it.
3071
3072    In the resulting set we will have only expressions that don't have delay
3073    stalls and nonsubstitutable dependences.  */
3074 static av_set_t
3075 compute_av_set (insn_t insn, ilist_t p, int ws, bool unique_p)
3076 {
3077   return compute_av_set_inside_bb (insn, p, ws, unique_p);
3078 }
3079
3080 /* Propagate a liveness set LV through INSN.  */
3081 static void
3082 propagate_lv_set (regset lv, insn_t insn)
3083 {
3084   gcc_assert (INSN_P (insn));
3085
3086   if (INSN_NOP_P (insn))
3087     return;
3088
3089   df_simulate_one_insn_backwards (BLOCK_FOR_INSN (insn), insn, lv);
3090 }
3091
3092 /* Return livness set at the end of BB.  */
3093 static regset
3094 compute_live_after_bb (basic_block bb)
3095 {
3096   edge e;
3097   edge_iterator ei;
3098   regset lv = get_clear_regset_from_pool ();
3099
3100   gcc_assert (!ignore_first);
3101
3102   FOR_EACH_EDGE (e, ei, bb->succs)
3103     if (sel_bb_empty_p (e->dest))
3104       {
3105         if (! BB_LV_SET_VALID_P (e->dest))
3106           {
3107             gcc_unreachable ();
3108             gcc_assert (BB_LV_SET (e->dest) == NULL);
3109             BB_LV_SET (e->dest) = compute_live_after_bb (e->dest);
3110             BB_LV_SET_VALID_P (e->dest) = true;
3111           }
3112         IOR_REG_SET (lv, BB_LV_SET (e->dest));
3113       }
3114     else
3115       IOR_REG_SET (lv, compute_live (sel_bb_head (e->dest)));
3116
3117   return lv;
3118 }
3119
3120 /* Compute the set of all live registers at the point before INSN and save
3121    it at INSN if INSN is bb header.  */
3122 regset
3123 compute_live (insn_t insn)
3124 {
3125   basic_block bb = BLOCK_FOR_INSN (insn);
3126   insn_t final, temp;
3127   regset lv;
3128
3129   /* Return the valid set if we're already on it.  */
3130   if (!ignore_first)
3131     {
3132       regset src = NULL;
3133
3134       if (sel_bb_head_p (insn) && BB_LV_SET_VALID_P (bb))
3135         src = BB_LV_SET (bb);
3136       else
3137         {
3138           gcc_assert (in_current_region_p (bb));
3139           if (INSN_LIVE_VALID_P (insn))
3140             src = INSN_LIVE (insn);
3141         }
3142
3143       if (src)
3144         {
3145           lv = get_regset_from_pool ();
3146           COPY_REG_SET (lv, src);
3147
3148           if (sel_bb_head_p (insn) && ! BB_LV_SET_VALID_P (bb))
3149             {
3150               COPY_REG_SET (BB_LV_SET (bb), lv);
3151               BB_LV_SET_VALID_P (bb) = true;
3152             }
3153
3154           return_regset_to_pool (lv);
3155           return lv;
3156         }
3157     }
3158
3159   /* We've skipped the wrong lv_set.  Don't skip the right one.  */
3160   ignore_first = false;
3161   gcc_assert (in_current_region_p (bb));
3162
3163   /* Find a valid LV set in this block or below, if needed.
3164      Start searching from the next insn: either ignore_first is true, or
3165      INSN doesn't have a correct live set.  */
3166   temp = NEXT_INSN (insn);
3167   final = NEXT_INSN (BB_END (bb));
3168   while (temp != final && ! INSN_LIVE_VALID_P (temp))
3169     temp = NEXT_INSN (temp);
3170   if (temp == final)
3171     {
3172       lv = compute_live_after_bb (bb);
3173       temp = PREV_INSN (temp);
3174     }
3175   else
3176     {
3177       lv = get_regset_from_pool ();
3178       COPY_REG_SET (lv, INSN_LIVE (temp));
3179     }
3180
3181   /* Put correct lv sets on the insns which have bad sets.  */
3182   final = PREV_INSN (insn);
3183   while (temp != final)
3184     {
3185       propagate_lv_set (lv, temp);
3186       COPY_REG_SET (INSN_LIVE (temp), lv);
3187       INSN_LIVE_VALID_P (temp) = true;
3188       temp = PREV_INSN (temp);
3189     }
3190
3191   /* Also put it in a BB.  */
3192   if (sel_bb_head_p (insn))
3193     {
3194       basic_block bb = BLOCK_FOR_INSN (insn);
3195
3196       COPY_REG_SET (BB_LV_SET (bb), lv);
3197       BB_LV_SET_VALID_P (bb) = true;
3198     }
3199
3200   /* We return LV to the pool, but will not clear it there.  Thus we can
3201      legimatelly use LV till the next use of regset_pool_get ().  */
3202   return_regset_to_pool (lv);
3203   return lv;
3204 }
3205
3206 /* Update liveness sets for INSN.  */
3207 static inline void
3208 update_liveness_on_insn (rtx insn)
3209 {
3210   ignore_first = true;
3211   compute_live (insn);
3212 }
3213
3214 /* Compute liveness below INSN and write it into REGS.  */
3215 static inline void
3216 compute_live_below_insn (rtx insn, regset regs)
3217 {
3218   rtx succ;
3219   succ_iterator si;
3220
3221   FOR_EACH_SUCC_1 (succ, si, insn, SUCCS_ALL)
3222     IOR_REG_SET (regs, compute_live (succ));
3223 }
3224
3225 /* Update the data gathered in av and lv sets starting from INSN.  */
3226 static void
3227 update_data_sets (rtx insn)
3228 {
3229   update_liveness_on_insn (insn);
3230   if (sel_bb_head_p (insn))
3231     {
3232       gcc_assert (AV_LEVEL (insn) != 0);
3233       BB_AV_LEVEL (BLOCK_FOR_INSN (insn)) = -1;
3234       compute_av_set (insn, NULL, 0, 0);
3235     }
3236 }
3237 \f
3238
3239 /* Helper for move_op () and find_used_regs ().
3240    Return speculation type for which a check should be created on the place
3241    of INSN.  EXPR is one of the original ops we are searching for.  */
3242 static ds_t
3243 get_spec_check_type_for_insn (insn_t insn, expr_t expr)
3244 {
3245   ds_t to_check_ds;
3246   ds_t already_checked_ds = EXPR_SPEC_DONE_DS (INSN_EXPR (insn));
3247
3248   to_check_ds = EXPR_SPEC_TO_CHECK_DS (expr);
3249
3250   if (targetm.sched.get_insn_checked_ds)
3251     already_checked_ds |= targetm.sched.get_insn_checked_ds (insn);
3252
3253   if (spec_info != NULL
3254       && (spec_info->flags & SEL_SCHED_SPEC_DONT_CHECK_CONTROL))
3255     already_checked_ds |= BEGIN_CONTROL;
3256
3257   already_checked_ds = ds_get_speculation_types (already_checked_ds);
3258
3259   to_check_ds &= ~already_checked_ds;
3260
3261   return to_check_ds;
3262 }
3263
3264 /* Find the set of registers that are unavailable for storing expres
3265    while moving ORIG_OPS up on the path starting from INSN due to
3266    liveness (USED_REGS) or hardware restrictions (REG_RENAME_P).
3267
3268    All the original operations found during the traversal are saved in the
3269    ORIGINAL_INSNS list.
3270
3271    REG_RENAME_P denotes the set of hardware registers that
3272    can not be used with renaming due to the register class restrictions,
3273    mode restrictions and other (the register we'll choose should be
3274    compatible class with the original uses, shouldn't be in call_used_regs,
3275    should be HARD_REGNO_RENAME_OK etc).
3276
3277    Returns TRUE if we've found all original insns, FALSE otherwise.
3278
3279    This function utilizes code_motion_path_driver (formerly find_used_regs_1)
3280    to traverse the code motion paths.  This helper function finds registers
3281    that are not available for storing expres while moving ORIG_OPS up on the
3282    path starting from INSN.  A register considered as used on the moving path,
3283    if one of the following conditions is not satisfied:
3284
3285       (1) a register not set or read on any path from xi to an instance of
3286           the original operation,
3287       (2) not among the live registers of the point immediately following the
3288           first original operation on a given downward path, except for the
3289           original target register of the operation,
3290       (3) not live on the other path of any conditional branch that is passed
3291           by the operation, in case original operations are not present on
3292           both paths of the conditional branch.
3293
3294    All the original operations found during the traversal are saved in the
3295    ORIGINAL_INSNS list.
3296
3297    REG_RENAME_P->CROSSES_CALL is true, if there is a call insn on the path
3298    from INSN to original insn. In this case CALL_USED_REG_SET will be added
3299    to unavailable hard regs at the point original operation is found.  */
3300
3301 static bool
3302 find_used_regs (insn_t insn, av_set_t orig_ops, regset used_regs,
3303                 struct reg_rename  *reg_rename_p, def_list_t *original_insns)
3304 {
3305   def_list_iterator i;
3306   def_t def;
3307   int res;
3308   bool needs_spec_check_p = false;
3309   expr_t expr;
3310   av_set_iterator expr_iter;
3311   struct fur_static_params sparams;
3312   struct cmpd_local_params lparams;
3313
3314   /* We haven't visited any blocks yet.  */
3315   bitmap_clear (code_motion_visited_blocks);
3316
3317   /* Init parameters for code_motion_path_driver.  */
3318   sparams.crosses_call = false;
3319   sparams.original_insns = original_insns;
3320   sparams.used_regs = used_regs;
3321
3322   /* Set the appropriate hooks and data.  */
3323   code_motion_path_driver_info = &fur_hooks;
3324
3325   res = code_motion_path_driver (insn, orig_ops, NULL, &lparams, &sparams);
3326
3327   reg_rename_p->crosses_call |= sparams.crosses_call;
3328
3329   gcc_assert (res == 1);
3330   gcc_assert (original_insns && *original_insns);
3331
3332   /* ??? We calculate whether an expression needs a check when computing
3333      av sets.  This information is not as precise as it could be due to
3334      merging this bit in merge_expr.  We can do better in find_used_regs,
3335      but we want to avoid multiple traversals of the same code motion
3336      paths.  */
3337   FOR_EACH_EXPR (expr, expr_iter, orig_ops)
3338     needs_spec_check_p |= EXPR_NEEDS_SPEC_CHECK_P (expr);
3339
3340   /* Mark hardware regs in REG_RENAME_P that are not suitable
3341      for renaming expr in INSN due to hardware restrictions (register class,
3342      modes compatibility etc).  */
3343   FOR_EACH_DEF (def, i, *original_insns)
3344     {
3345       vinsn_t vinsn = INSN_VINSN (def->orig_insn);
3346
3347       if (VINSN_SEPARABLE_P (vinsn))
3348         mark_unavailable_hard_regs (def, reg_rename_p, used_regs);
3349
3350       /* Do not allow clobbering of ld.[sa] address in case some of the
3351          original operations need a check.  */
3352       if (needs_spec_check_p)
3353         IOR_REG_SET (used_regs, VINSN_REG_USES (vinsn));
3354     }
3355
3356   return true;
3357 }
3358 \f
3359
3360 /* Functions to choose the best insn from available ones.  */
3361
3362 /* Adjusts the priority for EXPR using the backend *_adjust_priority hook.  */
3363 static int
3364 sel_target_adjust_priority (expr_t expr)
3365 {
3366   int priority = EXPR_PRIORITY (expr);
3367   int new_priority;
3368
3369   if (targetm.sched.adjust_priority)
3370     new_priority = targetm.sched.adjust_priority (EXPR_INSN_RTX (expr), priority);
3371   else
3372     new_priority = priority;
3373
3374   /* If the priority has changed, adjust EXPR_PRIORITY_ADJ accordingly.  */
3375   EXPR_PRIORITY_ADJ (expr) = new_priority - EXPR_PRIORITY (expr);
3376
3377   gcc_assert (EXPR_PRIORITY_ADJ (expr) >= 0);
3378
3379   if (sched_verbose >= 4)
3380     sel_print ("sel_target_adjust_priority: insn %d,  %d+%d = %d.\n",
3381                INSN_UID (EXPR_INSN_RTX (expr)), EXPR_PRIORITY (expr),
3382                EXPR_PRIORITY_ADJ (expr), new_priority);
3383
3384   return new_priority;
3385 }
3386
3387 /* Rank two available exprs for schedule.  Never return 0 here.  */
3388 static int
3389 sel_rank_for_schedule (const void *x, const void *y)
3390 {
3391   expr_t tmp = *(const expr_t *) y;
3392   expr_t tmp2 = *(const expr_t *) x;
3393   insn_t tmp_insn, tmp2_insn;
3394   vinsn_t tmp_vinsn, tmp2_vinsn;
3395   int val;
3396
3397   tmp_vinsn = EXPR_VINSN (tmp);
3398   tmp2_vinsn = EXPR_VINSN (tmp2);
3399   tmp_insn = EXPR_INSN_RTX (tmp);
3400   tmp2_insn = EXPR_INSN_RTX (tmp2);
3401
3402   /* Schedule debug insns as early as possible.  */
3403   if (DEBUG_INSN_P (tmp_insn) && !DEBUG_INSN_P (tmp2_insn))
3404     return -1;
3405   else if (DEBUG_INSN_P (tmp2_insn))
3406     return 1;
3407
3408   /* Prefer SCHED_GROUP_P insns to any others.  */
3409   if (SCHED_GROUP_P (tmp_insn) != SCHED_GROUP_P (tmp2_insn))
3410     {
3411       if (VINSN_UNIQUE_P (tmp_vinsn) && VINSN_UNIQUE_P (tmp2_vinsn))
3412         return SCHED_GROUP_P (tmp2_insn) ? 1 : -1;
3413
3414       /* Now uniqueness means SCHED_GROUP_P is set, because schedule groups
3415          cannot be cloned.  */
3416       if (VINSN_UNIQUE_P (tmp2_vinsn))
3417         return 1;
3418       return -1;
3419     }
3420
3421   /* Discourage scheduling of speculative checks.  */
3422   val = (sel_insn_is_speculation_check (tmp_insn)
3423          - sel_insn_is_speculation_check (tmp2_insn));
3424   if (val)
3425     return val;
3426
3427   /* Prefer not scheduled insn over scheduled one.  */
3428   if (EXPR_SCHED_TIMES (tmp) > 0 || EXPR_SCHED_TIMES (tmp2) > 0)
3429     {
3430       val = EXPR_SCHED_TIMES (tmp) - EXPR_SCHED_TIMES (tmp2);
3431       if (val)
3432         return val;
3433     }
3434
3435   /* Prefer jump over non-jump instruction.  */
3436   if (control_flow_insn_p (tmp_insn) && !control_flow_insn_p (tmp2_insn))
3437     return -1;
3438   else if (control_flow_insn_p (tmp2_insn) && !control_flow_insn_p (tmp_insn))
3439     return 1;
3440
3441   /* Prefer an expr with greater priority.  */
3442   if (EXPR_USEFULNESS (tmp) != 0 && EXPR_USEFULNESS (tmp2) != 0)
3443     {
3444       int p2 = EXPR_PRIORITY (tmp2) + EXPR_PRIORITY_ADJ (tmp2),
3445           p1 = EXPR_PRIORITY (tmp) + EXPR_PRIORITY_ADJ (tmp);
3446
3447       val = p2 * EXPR_USEFULNESS (tmp2) - p1 * EXPR_USEFULNESS (tmp);
3448     }
3449   else
3450     val = EXPR_PRIORITY (tmp2) - EXPR_PRIORITY (tmp)
3451           + EXPR_PRIORITY_ADJ (tmp2) - EXPR_PRIORITY_ADJ (tmp);
3452   if (val)
3453     return val;
3454
3455   if (spec_info != NULL && spec_info->mask != 0)
3456     /* This code was taken from haifa-sched.c: rank_for_schedule ().  */
3457     {
3458       ds_t ds1, ds2;
3459       dw_t dw1, dw2;
3460       int dw;
3461
3462       ds1 = EXPR_SPEC_DONE_DS (tmp);
3463       if (ds1)
3464         dw1 = ds_weak (ds1);
3465       else
3466         dw1 = NO_DEP_WEAK;
3467
3468       ds2 = EXPR_SPEC_DONE_DS (tmp2);
3469       if (ds2)
3470         dw2 = ds_weak (ds2);
3471       else
3472         dw2 = NO_DEP_WEAK;
3473
3474       dw = dw2 - dw1;
3475       if (dw > (NO_DEP_WEAK / 8) || dw < -(NO_DEP_WEAK / 8))
3476         return dw;
3477     }
3478
3479   /* Prefer an old insn to a bookkeeping insn.  */
3480   if (INSN_UID (tmp_insn) < first_emitted_uid
3481       && INSN_UID (tmp2_insn) >= first_emitted_uid)
3482     return -1;
3483   if (INSN_UID (tmp_insn) >= first_emitted_uid
3484       && INSN_UID (tmp2_insn) < first_emitted_uid)
3485     return 1;
3486
3487   /* Prefer an insn with smaller UID, as a last resort.
3488      We can't safely use INSN_LUID as it is defined only for those insns
3489      that are in the stream.  */
3490   return INSN_UID (tmp_insn) - INSN_UID (tmp2_insn);
3491 }
3492
3493 /* Filter out expressions from av set pointed to by AV_PTR
3494    that are pipelined too many times.  */
3495 static void
3496 process_pipelined_exprs (av_set_t *av_ptr)
3497 {
3498   expr_t expr;
3499   av_set_iterator si;
3500
3501   /* Don't pipeline already pipelined code as that would increase
3502      number of unnecessary register moves.  */
3503   FOR_EACH_EXPR_1 (expr, si, av_ptr)
3504     {
3505       if (EXPR_SCHED_TIMES (expr)
3506           >= PARAM_VALUE (PARAM_SELSCHED_MAX_SCHED_TIMES))
3507         av_set_iter_remove (&si);
3508     }
3509 }
3510
3511 /* Filter speculative insns from AV_PTR if we don't want them.  */
3512 static void
3513 process_spec_exprs (av_set_t *av_ptr)
3514 {
3515   bool try_data_p = true;
3516   bool try_control_p = true;
3517   expr_t expr;
3518   av_set_iterator si;
3519
3520   if (spec_info == NULL)
3521     return;
3522
3523   /* Scan *AV_PTR to find out if we want to consider speculative
3524      instructions for scheduling.  */
3525   FOR_EACH_EXPR_1 (expr, si, av_ptr)
3526     {
3527       ds_t ds;
3528
3529       ds = EXPR_SPEC_DONE_DS (expr);
3530
3531       /* The probability of a success is too low - don't speculate.  */
3532       if ((ds & SPECULATIVE)
3533           && (ds_weak (ds) < spec_info->data_weakness_cutoff
3534               || EXPR_USEFULNESS (expr) < spec_info->control_weakness_cutoff
3535               || (pipelining_p && false
3536                   && (ds & DATA_SPEC)
3537                   && (ds & CONTROL_SPEC))))
3538         {
3539           av_set_iter_remove (&si);
3540           continue;
3541         }
3542
3543       if ((spec_info->flags & PREFER_NON_DATA_SPEC)
3544           && !(ds & BEGIN_DATA))
3545         try_data_p = false;
3546
3547       if ((spec_info->flags & PREFER_NON_CONTROL_SPEC)
3548           && !(ds & BEGIN_CONTROL))
3549         try_control_p = false;
3550     }
3551
3552   FOR_EACH_EXPR_1 (expr, si, av_ptr)
3553     {
3554       ds_t ds;
3555
3556       ds = EXPR_SPEC_DONE_DS (expr);
3557
3558       if (ds & SPECULATIVE)
3559         {
3560           if ((ds & BEGIN_DATA) && !try_data_p)
3561             /* We don't want any data speculative instructions right
3562                now.  */
3563             av_set_iter_remove (&si);
3564
3565           if ((ds & BEGIN_CONTROL) && !try_control_p)
3566             /* We don't want any control speculative instructions right
3567                now.  */
3568             av_set_iter_remove (&si);
3569         }
3570     }
3571 }
3572
3573 /* Search for any use-like insns in AV_PTR and decide on scheduling
3574    them.  Return one when found, and NULL otherwise.
3575    Note that we check here whether a USE could be scheduled to avoid
3576    an infinite loop later.  */
3577 static expr_t
3578 process_use_exprs (av_set_t *av_ptr)
3579 {
3580   expr_t expr;
3581   av_set_iterator si;
3582   bool uses_present_p = false;
3583   bool try_uses_p = true;
3584
3585   FOR_EACH_EXPR_1 (expr, si, av_ptr)
3586     {
3587       /* This will also initialize INSN_CODE for later use.  */
3588       if (recog_memoized (EXPR_INSN_RTX (expr)) < 0)
3589         {
3590           /* If we have a USE in *AV_PTR that was not scheduled yet,
3591              do so because it will do good only.  */
3592           if (EXPR_SCHED_TIMES (expr) <= 0)
3593             {
3594               if (EXPR_TARGET_AVAILABLE (expr) == 1)
3595                 return expr;
3596
3597               av_set_iter_remove (&si);
3598             }
3599           else
3600             {
3601               gcc_assert (pipelining_p);
3602
3603               uses_present_p = true;
3604             }
3605         }
3606       else
3607         try_uses_p = false;
3608     }
3609
3610   if (uses_present_p)
3611     {
3612       /* If we don't want to schedule any USEs right now and we have some
3613            in *AV_PTR, remove them, else just return the first one found.  */
3614       if (!try_uses_p)
3615         {
3616           FOR_EACH_EXPR_1 (expr, si, av_ptr)
3617             if (INSN_CODE (EXPR_INSN_RTX (expr)) < 0)
3618               av_set_iter_remove (&si);
3619         }
3620       else
3621         {
3622           FOR_EACH_EXPR_1 (expr, si, av_ptr)
3623             {
3624               gcc_assert (INSN_CODE (EXPR_INSN_RTX (expr)) < 0);
3625
3626               if (EXPR_TARGET_AVAILABLE (expr) == 1)
3627                 return expr;
3628
3629               av_set_iter_remove (&si);
3630             }
3631         }
3632     }
3633
3634   return NULL;
3635 }
3636
3637 /* Lookup EXPR in VINSN_VEC and return TRUE if found.  Also check patterns from
3638    EXPR's history of changes.  */
3639 static bool
3640 vinsn_vec_has_expr_p (vinsn_vec_t vinsn_vec, expr_t expr)
3641 {
3642   vinsn_t vinsn, expr_vinsn;
3643   int n;
3644   unsigned i;
3645
3646   /* Start with checking expr itself and then proceed with all the old forms
3647      of expr taken from its history vector.  */
3648   for (i = 0, expr_vinsn = EXPR_VINSN (expr);
3649        expr_vinsn;
3650        expr_vinsn = (i < VEC_length (expr_history_def,
3651                                      EXPR_HISTORY_OF_CHANGES (expr))
3652                      ? VEC_index (expr_history_def,
3653                                   EXPR_HISTORY_OF_CHANGES (expr),
3654                                   i++)->old_expr_vinsn
3655                      : NULL))
3656     FOR_EACH_VEC_ELT (vinsn_t, vinsn_vec, n, vinsn)
3657       if (VINSN_SEPARABLE_P (vinsn))
3658         {
3659           if (vinsn_equal_p (vinsn, expr_vinsn))
3660             return true;
3661         }
3662       else
3663         {
3664           /* For non-separable instructions, the blocking insn can have
3665              another pattern due to substitution, and we can't choose
3666              different register as in the above case.  Check all registers
3667              being written instead.  */
3668           if (bitmap_intersect_p (VINSN_REG_SETS (vinsn),
3669                                   VINSN_REG_SETS (expr_vinsn)))
3670             return true;
3671         }
3672
3673   return false;
3674 }
3675
3676 #ifdef ENABLE_CHECKING
3677 /* Return true if either of expressions from ORIG_OPS can be blocked
3678    by previously created bookkeeping code.  STATIC_PARAMS points to static
3679    parameters of move_op.  */
3680 static bool
3681 av_set_could_be_blocked_by_bookkeeping_p (av_set_t orig_ops, void *static_params)
3682 {
3683   expr_t expr;
3684   av_set_iterator iter;
3685   moveop_static_params_p sparams;
3686
3687   /* This checks that expressions in ORIG_OPS are not blocked by bookkeeping
3688      created while scheduling on another fence.  */
3689   FOR_EACH_EXPR (expr, iter, orig_ops)
3690     if (vinsn_vec_has_expr_p (vec_bookkeeping_blocked_vinsns, expr))
3691       return true;
3692
3693   gcc_assert (code_motion_path_driver_info == &move_op_hooks);
3694   sparams = (moveop_static_params_p) static_params;
3695
3696   /* Expressions can be also blocked by bookkeeping created during current
3697      move_op.  */
3698   if (bitmap_bit_p (current_copies, INSN_UID (sparams->failed_insn)))
3699     FOR_EACH_EXPR (expr, iter, orig_ops)
3700       if (moveup_expr_cached (expr, sparams->failed_insn, false) != MOVEUP_EXPR_NULL)
3701         return true;
3702
3703   /* Expressions in ORIG_OPS may have wrong destination register due to
3704      renaming.  Check with the right register instead.  */
3705   if (sparams->dest && REG_P (sparams->dest))
3706     {
3707       rtx reg = sparams->dest;
3708       vinsn_t failed_vinsn = INSN_VINSN (sparams->failed_insn);
3709
3710       if (register_unavailable_p (VINSN_REG_SETS (failed_vinsn), reg)
3711           || register_unavailable_p (VINSN_REG_USES (failed_vinsn), reg)
3712           || register_unavailable_p (VINSN_REG_CLOBBERS (failed_vinsn), reg))
3713         return true;
3714     }
3715
3716   return false;
3717 }
3718 #endif
3719
3720 /* Clear VINSN_VEC and detach vinsns.  */
3721 static void
3722 vinsn_vec_clear (vinsn_vec_t *vinsn_vec)
3723 {
3724   unsigned len = VEC_length (vinsn_t, *vinsn_vec);
3725   if (len > 0)
3726     {
3727       vinsn_t vinsn;
3728       int n;
3729
3730       FOR_EACH_VEC_ELT (vinsn_t, *vinsn_vec, n, vinsn)
3731         vinsn_detach (vinsn);
3732       VEC_block_remove (vinsn_t, *vinsn_vec, 0, len);
3733     }
3734 }
3735
3736 /* Add the vinsn of EXPR to the VINSN_VEC.  */
3737 static void
3738 vinsn_vec_add (vinsn_vec_t *vinsn_vec, expr_t expr)
3739 {
3740   vinsn_attach (EXPR_VINSN (expr));
3741   VEC_safe_push (vinsn_t, heap, *vinsn_vec, EXPR_VINSN (expr));
3742 }
3743
3744 /* Free the vector representing blocked expressions.  */
3745 static void
3746 vinsn_vec_free (vinsn_vec_t *vinsn_vec)
3747 {
3748   if (*vinsn_vec)
3749     VEC_free (vinsn_t, heap, *vinsn_vec);
3750 }
3751
3752 /* Increase EXPR_PRIORITY_ADJ for INSN by AMOUNT.  */
3753
3754 void sel_add_to_insn_priority (rtx insn, int amount)
3755 {
3756   EXPR_PRIORITY_ADJ (INSN_EXPR (insn)) += amount;
3757
3758   if (sched_verbose >= 2)
3759     sel_print ("sel_add_to_insn_priority: insn %d, by %d (now %d+%d).\n",
3760                INSN_UID (insn), amount, EXPR_PRIORITY (INSN_EXPR (insn)),
3761                EXPR_PRIORITY_ADJ (INSN_EXPR (insn)));
3762 }
3763
3764 /* Turn AV into a vector, filter inappropriate insns and sort it.  Return
3765    true if there is something to schedule.  BNDS and FENCE are current
3766    boundaries and fence, respectively.  If we need to stall for some cycles
3767    before an expr from AV would become available, write this number to
3768    *PNEED_STALL.  */
3769 static bool
3770 fill_vec_av_set (av_set_t av, blist_t bnds, fence_t fence,
3771                  int *pneed_stall)
3772 {
3773   av_set_iterator si;
3774   expr_t expr;
3775   int sched_next_worked = 0, stalled, n;
3776   static int av_max_prio, est_ticks_till_branch;
3777   int min_need_stall = -1;
3778   deps_t dc = BND_DC (BLIST_BND (bnds));
3779
3780   /* Bail out early when the ready list contained only USEs/CLOBBERs that are
3781      already scheduled.  */
3782   if (av == NULL)
3783     return false;
3784
3785   /* Empty vector from the previous stuff.  */
3786   if (VEC_length (expr_t, vec_av_set) > 0)
3787     VEC_block_remove (expr_t, vec_av_set, 0, VEC_length (expr_t, vec_av_set));
3788
3789   /* Turn the set into a vector for sorting and call sel_target_adjust_priority
3790      for each insn.  */
3791   gcc_assert (VEC_empty (expr_t, vec_av_set));
3792   FOR_EACH_EXPR (expr, si, av)
3793     {
3794       VEC_safe_push (expr_t, heap, vec_av_set, expr);
3795
3796       gcc_assert (EXPR_PRIORITY_ADJ (expr) == 0 || *pneed_stall);
3797
3798       /* Adjust priority using target backend hook.  */
3799       sel_target_adjust_priority (expr);
3800     }
3801
3802   /* Sort the vector.  */
3803   VEC_qsort (expr_t, vec_av_set, sel_rank_for_schedule);
3804
3805   /* We record maximal priority of insns in av set for current instruction
3806      group.  */
3807   if (FENCE_STARTS_CYCLE_P (fence))
3808     av_max_prio = est_ticks_till_branch = INT_MIN;
3809
3810   /* Filter out inappropriate expressions.  Loop's direction is reversed to
3811      visit "best" instructions first.  We assume that VEC_unordered_remove
3812      moves last element in place of one being deleted.  */
3813   for (n = VEC_length (expr_t, vec_av_set) - 1, stalled = 0; n >= 0; n--)
3814     {
3815       expr_t expr = VEC_index (expr_t, vec_av_set, n);
3816       insn_t insn = EXPR_INSN_RTX (expr);
3817       signed char target_available;
3818       bool is_orig_reg_p = true;
3819       int need_cycles, new_prio;
3820
3821       /* Don't allow any insns other than from SCHED_GROUP if we have one.  */
3822       if (FENCE_SCHED_NEXT (fence) && insn != FENCE_SCHED_NEXT (fence))
3823         {
3824           VEC_unordered_remove (expr_t, vec_av_set, n);
3825           continue;
3826         }
3827
3828       /* Set number of sched_next insns (just in case there
3829          could be several).  */
3830       if (FENCE_SCHED_NEXT (fence))
3831         sched_next_worked++;
3832
3833       /* Check all liveness requirements and try renaming.
3834          FIXME: try to minimize calls to this.  */
3835       target_available = EXPR_TARGET_AVAILABLE (expr);
3836
3837       /* If insn was already scheduled on the current fence,
3838          set TARGET_AVAILABLE to -1 no matter what expr's attribute says.  */
3839       if (vinsn_vec_has_expr_p (vec_target_unavailable_vinsns, expr))
3840         target_available = -1;
3841
3842       /* If the availability of the EXPR is invalidated by the insertion of
3843          bookkeeping earlier, make sure that we won't choose this expr for
3844          scheduling if it's not separable, and if it is separable, then
3845          we have to recompute the set of available registers for it.  */
3846       if (vinsn_vec_has_expr_p (vec_bookkeeping_blocked_vinsns, expr))
3847         {
3848           VEC_unordered_remove (expr_t, vec_av_set, n);
3849           if (sched_verbose >= 4)
3850             sel_print ("Expr %d is blocked by bookkeeping inserted earlier\n",
3851                        INSN_UID (insn));
3852           continue;
3853         }
3854
3855       if (target_available == true)
3856         {
3857           /* Do nothing -- we can use an existing register.  */
3858           is_orig_reg_p = EXPR_SEPARABLE_P (expr);
3859         }
3860       else if (/* Non-separable instruction will never
3861                   get another register. */
3862                (target_available == false
3863                 && !EXPR_SEPARABLE_P (expr))
3864                /* Don't try to find a register for low-priority expression.  */
3865                || (int) VEC_length (expr_t, vec_av_set) - 1 - n >= max_insns_to_rename
3866                /* ??? FIXME: Don't try to rename data speculation.  */
3867                || (EXPR_SPEC_DONE_DS (expr) & BEGIN_DATA)
3868                || ! find_best_reg_for_expr (expr, bnds, &is_orig_reg_p))
3869         {
3870           VEC_unordered_remove (expr_t, vec_av_set, n);
3871           if (sched_verbose >= 4)
3872             sel_print ("Expr %d has no suitable target register\n",
3873                        INSN_UID (insn));
3874           continue;
3875         }
3876
3877       /* Filter expressions that need to be renamed or speculated when
3878          pipelining, because compensating register copies or speculation
3879          checks are likely to be placed near the beginning of the loop,
3880          causing a stall.  */
3881       if (pipelining_p && EXPR_ORIG_SCHED_CYCLE (expr) > 0
3882           && (!is_orig_reg_p || EXPR_SPEC_DONE_DS (expr) != 0))
3883         {
3884           /* Estimation of number of cycles until loop branch for
3885              renaming/speculation to be successful.  */
3886           int need_n_ticks_till_branch = sel_vinsn_cost (EXPR_VINSN (expr));
3887
3888           if ((int) current_loop_nest->ninsns < 9)
3889             {
3890               VEC_unordered_remove (expr_t, vec_av_set, n);
3891               if (sched_verbose >= 4)
3892                 sel_print ("Pipelining expr %d will likely cause stall\n",
3893                            INSN_UID (insn));
3894               continue;
3895             }
3896
3897           if ((int) current_loop_nest->ninsns - num_insns_scheduled
3898               < need_n_ticks_till_branch * issue_rate / 2
3899               && est_ticks_till_branch < need_n_ticks_till_branch)
3900              {
3901                VEC_unordered_remove (expr_t, vec_av_set, n);
3902                if (sched_verbose >= 4)
3903                  sel_print ("Pipelining expr %d will likely cause stall\n",
3904                             INSN_UID (insn));
3905                continue;
3906              }
3907         }
3908
3909       /* We want to schedule speculation checks as late as possible.  Discard
3910          them from av set if there are instructions with higher priority.  */
3911       if (sel_insn_is_speculation_check (insn)
3912           && EXPR_PRIORITY (expr) < av_max_prio)
3913         {
3914           stalled++;
3915           min_need_stall = min_need_stall < 0 ? 1 : MIN (min_need_stall, 1);
3916           VEC_unordered_remove (expr_t, vec_av_set, n);
3917           if (sched_verbose >= 4)
3918             sel_print ("Delaying speculation check %d until its first use\n",
3919                        INSN_UID (insn));
3920           continue;
3921         }
3922
3923       /* Ignore EXPRs available from pipelining to update AV_MAX_PRIO.  */
3924       if (EXPR_ORIG_SCHED_CYCLE (expr) <= 0)
3925         av_max_prio = MAX (av_max_prio, EXPR_PRIORITY (expr));
3926
3927       /* Don't allow any insns whose data is not yet ready.
3928          Check first whether we've already tried them and failed.  */
3929       if (INSN_UID (insn) < FENCE_READY_TICKS_SIZE (fence))
3930         {
3931           need_cycles = (FENCE_READY_TICKS (fence)[INSN_UID (insn)]
3932                          - FENCE_CYCLE (fence));
3933           if (EXPR_ORIG_SCHED_CYCLE (expr) <= 0)
3934             est_ticks_till_branch = MAX (est_ticks_till_branch,
3935                                          EXPR_PRIORITY (expr) + need_cycles);
3936
3937           if (need_cycles > 0)
3938             {
3939               stalled++;
3940               min_need_stall = (min_need_stall < 0
3941                                 ? need_cycles
3942                                 : MIN (min_need_stall, need_cycles));
3943               VEC_unordered_remove (expr_t, vec_av_set, n);
3944
3945               if (sched_verbose >= 4)
3946                 sel_print ("Expr %d is not ready until cycle %d (cached)\n",
3947                            INSN_UID (insn),
3948                            FENCE_READY_TICKS (fence)[INSN_UID (insn)]);
3949               continue;
3950             }
3951         }
3952
3953       /* Now resort to dependence analysis to find whether EXPR might be
3954          stalled due to dependencies from FENCE's context.  */
3955       need_cycles = tick_check_p (expr, dc, fence);
3956       new_prio = EXPR_PRIORITY (expr) + EXPR_PRIORITY_ADJ (expr) + need_cycles;
3957
3958       if (EXPR_ORIG_SCHED_CYCLE (expr) <= 0)
3959         est_ticks_till_branch = MAX (est_ticks_till_branch,
3960                                      new_prio);
3961
3962       if (need_cycles > 0)
3963         {
3964           if (INSN_UID (insn) >= FENCE_READY_TICKS_SIZE (fence))
3965             {
3966               int new_size = INSN_UID (insn) * 3 / 2;
3967
3968               FENCE_READY_TICKS (fence)
3969                 = (int *) xrecalloc (FENCE_READY_TICKS (fence),
3970                                      new_size, FENCE_READY_TICKS_SIZE (fence),
3971                                      sizeof (int));
3972             }
3973           FENCE_READY_TICKS (fence)[INSN_UID (insn)]
3974             = FENCE_CYCLE (fence) + need_cycles;
3975
3976           stalled++;
3977           min_need_stall = (min_need_stall < 0
3978                             ? need_cycles
3979                             : MIN (min_need_stall, need_cycles));
3980
3981           VEC_unordered_remove (expr_t, vec_av_set, n);
3982
3983           if (sched_verbose >= 4)
3984             sel_print ("Expr %d is not ready yet until cycle %d\n",
3985                        INSN_UID (insn),
3986                        FENCE_READY_TICKS (fence)[INSN_UID (insn)]);
3987           continue;
3988         }
3989
3990       if (sched_verbose >= 4)
3991         sel_print ("Expr %d is ok\n", INSN_UID (insn));
3992       min_need_stall = 0;
3993     }
3994
3995   /* Clear SCHED_NEXT.  */
3996   if (FENCE_SCHED_NEXT (fence))
3997     {
3998       gcc_assert (sched_next_worked == 1);
3999       FENCE_SCHED_NEXT (fence) = NULL_RTX;
4000     }
4001
4002   /* No need to stall if this variable was not initialized.  */
4003   if (min_need_stall < 0)
4004     min_need_stall = 0;
4005
4006   if (VEC_empty (expr_t, vec_av_set))
4007     {
4008       /* We need to set *pneed_stall here, because later we skip this code
4009          when ready list is empty.  */
4010       *pneed_stall = min_need_stall;
4011       return false;
4012     }
4013   else
4014     gcc_assert (min_need_stall == 0);
4015
4016   /* Sort the vector.  */
4017   VEC_qsort (expr_t, vec_av_set, sel_rank_for_schedule);
4018
4019   if (sched_verbose >= 4)
4020     {
4021       sel_print ("Total ready exprs: %d, stalled: %d\n",
4022                  VEC_length (expr_t, vec_av_set), stalled);
4023       sel_print ("Sorted av set (%d): ", VEC_length (expr_t, vec_av_set));
4024       FOR_EACH_VEC_ELT (expr_t, vec_av_set, n, expr)
4025         dump_expr (expr);
4026       sel_print ("\n");
4027     }
4028
4029   *pneed_stall = 0;
4030   return true;
4031 }
4032
4033 /* Convert a vectored and sorted av set to the ready list that
4034    the rest of the backend wants to see.  */
4035 static void
4036 convert_vec_av_set_to_ready (void)
4037 {
4038   int n;
4039   expr_t expr;
4040
4041   /* Allocate and fill the ready list from the sorted vector.  */
4042   ready.n_ready = VEC_length (expr_t, vec_av_set);
4043   ready.first = ready.n_ready - 1;
4044
4045   gcc_assert (ready.n_ready > 0);
4046
4047   if (ready.n_ready > max_issue_size)
4048     {
4049       max_issue_size = ready.n_ready;
4050       sched_extend_ready_list (ready.n_ready);
4051     }
4052
4053   FOR_EACH_VEC_ELT (expr_t, vec_av_set, n, expr)
4054     {
4055       vinsn_t vi = EXPR_VINSN (expr);
4056       insn_t insn = VINSN_INSN_RTX (vi);
4057
4058       ready_try[n] = 0;
4059       ready.vec[n] = insn;
4060     }
4061 }
4062
4063 /* Initialize ready list from *AV_PTR for the max_issue () call.
4064    If any unrecognizable insn found in *AV_PTR, return it (and skip
4065    max_issue).  BND and FENCE are current boundary and fence,
4066    respectively.  If we need to stall for some cycles before an expr
4067    from *AV_PTR would become available, write this number to *PNEED_STALL.  */
4068 static expr_t
4069 fill_ready_list (av_set_t *av_ptr, blist_t bnds, fence_t fence,
4070                  int *pneed_stall)
4071 {
4072   expr_t expr;
4073
4074   /* We do not support multiple boundaries per fence.  */
4075   gcc_assert (BLIST_NEXT (bnds) == NULL);
4076
4077   /* Process expressions required special handling, i.e.  pipelined,
4078      speculative and recog() < 0 expressions first.  */
4079   process_pipelined_exprs (av_ptr);
4080   process_spec_exprs (av_ptr);
4081
4082   /* A USE could be scheduled immediately.  */
4083   expr = process_use_exprs (av_ptr);
4084   if (expr)
4085     {
4086       *pneed_stall = 0;
4087       return expr;
4088     }
4089
4090   /* Turn the av set to a vector for sorting.  */
4091   if (! fill_vec_av_set (*av_ptr, bnds, fence, pneed_stall))
4092     {
4093       ready.n_ready = 0;
4094       return NULL;
4095     }
4096
4097   /* Build the final ready list.  */
4098   convert_vec_av_set_to_ready ();
4099   return NULL;
4100 }
4101
4102 /* Wrapper for dfa_new_cycle ().  Returns TRUE if cycle was advanced.  */
4103 static bool
4104 sel_dfa_new_cycle (insn_t insn, fence_t fence)
4105 {
4106   int last_scheduled_cycle = FENCE_LAST_SCHEDULED_INSN (fence)
4107                              ? INSN_SCHED_CYCLE (FENCE_LAST_SCHEDULED_INSN (fence))
4108                              : FENCE_CYCLE (fence) - 1;
4109   bool res = false;
4110   int sort_p = 0;
4111
4112   if (!targetm.sched.dfa_new_cycle)
4113     return false;
4114
4115   memcpy (curr_state, FENCE_STATE (fence), dfa_state_size);
4116
4117   while (!sort_p && targetm.sched.dfa_new_cycle (sched_dump, sched_verbose,
4118                                                  insn, last_scheduled_cycle,
4119                                                  FENCE_CYCLE (fence), &sort_p))
4120     {
4121       memcpy (FENCE_STATE (fence), curr_state, dfa_state_size);
4122       advance_one_cycle (fence);
4123       memcpy (curr_state, FENCE_STATE (fence), dfa_state_size);
4124       res = true;
4125     }
4126
4127   return res;
4128 }
4129
4130 /* Invoke reorder* target hooks on the ready list.  Return the number of insns
4131    we can issue.  FENCE is the current fence.  */
4132 static int
4133 invoke_reorder_hooks (fence_t fence)
4134 {
4135   int issue_more;
4136   bool ran_hook = false;
4137
4138   /* Call the reorder hook at the beginning of the cycle, and call
4139      the reorder2 hook in the middle of the cycle.  */
4140   if (FENCE_ISSUED_INSNS (fence) == 0)
4141     {
4142       if (targetm.sched.reorder
4143           && !SCHED_GROUP_P (ready_element (&ready, 0))
4144           && ready.n_ready > 1)
4145         {
4146           /* Don't give reorder the most prioritized insn as it can break
4147              pipelining.  */
4148           if (pipelining_p)
4149             --ready.n_ready;
4150
4151           issue_more
4152             = targetm.sched.reorder (sched_dump, sched_verbose,
4153                                      ready_lastpos (&ready),
4154                                      &ready.n_ready, FENCE_CYCLE (fence));
4155
4156           if (pipelining_p)
4157             ++ready.n_ready;
4158
4159           ran_hook = true;
4160         }
4161       else
4162         /* Initialize can_issue_more for variable_issue.  */
4163         issue_more = issue_rate;
4164     }
4165   else if (targetm.sched.reorder2
4166            && !SCHED_GROUP_P (ready_element (&ready, 0)))