* c-c++-common/ubsan/float-cast-overflow-6.c: Add i?86-*-* target.
[official-gcc.git] / gcc / sel-sched.c
blobe755a19428433afeadb76de7c21bf7c3d9240a98
1 /* Instruction scheduling pass. Selective scheduler and pipeliner.
2 Copyright (C) 2006-2014 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, or (at your option) any later
9 version.
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 for more details.
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
20 #include "config.h"
21 #include "system.h"
22 #include "coretypes.h"
23 #include "tm.h"
24 #include "rtl-error.h"
25 #include "tm_p.h"
26 #include "hard-reg-set.h"
27 #include "regs.h"
28 #include "hashtab.h"
29 #include "hash-set.h"
30 #include "vec.h"
31 #include "machmode.h"
32 #include "input.h"
33 #include "function.h"
34 #include "predict.h"
35 #include "dominance.h"
36 #include "cfg.h"
37 #include "cfgbuild.h"
38 #include "basic-block.h"
39 #include "flags.h"
40 #include "insn-config.h"
41 #include "insn-attr.h"
42 #include "except.h"
43 #include "recog.h"
44 #include "params.h"
45 #include "target.h"
46 #include "output.h"
47 #include "sched-int.h"
48 #include "ggc.h"
49 #include "tree.h"
50 #include "langhooks.h"
51 #include "rtlhooks-def.h"
52 #include "emit-rtl.h"
53 #include "ira.h"
54 #include "rtl-iter.h"
56 #ifdef INSN_SCHEDULING
57 #include "sel-sched-ir.h"
58 #include "sel-sched-dump.h"
59 #include "sel-sched.h"
60 #include "dbgcnt.h"
62 /* Implementation of selective scheduling approach.
63 The below implementation follows the original approach with the following
64 changes:
66 o the scheduler works after register allocation (but can be also tuned
67 to work before RA);
68 o some instructions are not copied or register renamed;
69 o conditional jumps are not moved with code duplication;
70 o several jumps in one parallel group are not supported;
71 o when pipelining outer loops, code motion through inner loops
72 is not supported;
73 o control and data speculation are supported;
74 o some improvements for better compile time/performance were made.
76 Terminology
77 ===========
79 A vinsn, or virtual insn, is an insn with additional data characterizing
80 insn pattern, such as LHS, RHS, register sets used/set/clobbered, etc.
81 Vinsns also act as smart pointers to save memory by reusing them in
82 different expressions. A vinsn is described by vinsn_t type.
84 An expression is a vinsn with additional data characterizing its properties
85 at some point in the control flow graph. The data may be its usefulness,
86 priority, speculative status, whether it was renamed/subsituted, etc.
87 An expression is described by expr_t type.
89 Availability set (av_set) is a set of expressions at a given control flow
90 point. It is represented as av_set_t. The expressions in av sets are kept
91 sorted in the terms of expr_greater_p function. It allows to truncate
92 the set while leaving the best expressions.
94 A fence is a point through which code motion is prohibited. On each step,
95 we gather a parallel group of insns at a fence. It is possible to have
96 multiple fences. A fence is represented via fence_t.
98 A boundary is the border between the fence group and the rest of the code.
99 Currently, we never have more than one boundary per fence, as we finalize
100 the fence group when a jump is scheduled. A boundary is represented
101 via bnd_t.
103 High-level overview
104 ===================
106 The scheduler finds regions to schedule, schedules each one, and finalizes.
107 The regions are formed starting from innermost loops, so that when the inner
108 loop is pipelined, its prologue can be scheduled together with yet unprocessed
109 outer loop. The rest of acyclic regions are found using extend_rgns:
110 the blocks that are not yet allocated to any regions are traversed in top-down
111 order, and a block is added to a region to which all its predecessors belong;
112 otherwise, the block starts its own region.
114 The main scheduling loop (sel_sched_region_2) consists of just
115 scheduling on each fence and updating fences. For each fence,
116 we fill a parallel group of insns (fill_insns) until some insns can be added.
117 First, we compute available exprs (av-set) at the boundary of the current
118 group. Second, we choose the best expression from it. If the stall is
119 required to schedule any of the expressions, we advance the current cycle
120 appropriately. So, the final group does not exactly correspond to a VLIW
121 word. Third, we move the chosen expression to the boundary (move_op)
122 and update the intermediate av sets and liveness sets. We quit fill_insns
123 when either no insns left for scheduling or we have scheduled enough insns
124 so we feel like advancing a scheduling point.
126 Computing available expressions
127 ===============================
129 The computation (compute_av_set) is a bottom-up traversal. At each insn,
130 we're moving the union of its successors' sets through it via
131 moveup_expr_set. The dependent expressions are removed. Local
132 transformations (substitution, speculation) are applied to move more
133 exprs. Then the expr corresponding to the current insn is added.
134 The result is saved on each basic block header.
136 When traversing the CFG, we're moving down for no more than max_ws insns.
137 Also, we do not move down to ineligible successors (is_ineligible_successor),
138 which include moving along a back-edge, moving to already scheduled code,
139 and moving to another fence. The first two restrictions are lifted during
140 pipelining, which allows us to move insns along a back-edge. We always have
141 an acyclic region for scheduling because we forbid motion through fences.
143 Choosing the best expression
144 ============================
146 We sort the final availability set via sel_rank_for_schedule, then we remove
147 expressions which are not yet ready (tick_check_p) or which dest registers
148 cannot be used. For some of them, we choose another register via
149 find_best_reg. To do this, we run find_used_regs to calculate the set of
150 registers which cannot be used. The find_used_regs function performs
151 a traversal of code motion paths for an expr. We consider for renaming
152 only registers which are from the same regclass as the original one and
153 using which does not interfere with any live ranges. Finally, we convert
154 the resulting set to the ready list format and use max_issue and reorder*
155 hooks similarly to the Haifa scheduler.
157 Scheduling the best expression
158 ==============================
160 We run the move_op routine to perform the same type of code motion paths
161 traversal as in find_used_regs. (These are working via the same driver,
162 code_motion_path_driver.) When moving down the CFG, we look for original
163 instruction that gave birth to a chosen expression. We undo
164 the transformations performed on an expression via the history saved in it.
165 When found, we remove the instruction or leave a reg-reg copy/speculation
166 check if needed. On a way up, we insert bookkeeping copies at each join
167 point. If a copy is not needed, it will be removed later during this
168 traversal. We update the saved av sets and liveness sets on the way up, too.
170 Finalizing the schedule
171 =======================
173 When pipelining, we reschedule the blocks from which insns were pipelined
174 to get a tighter schedule. On Itanium, we also perform bundling via
175 the same routine from ia64.c.
177 Dependence analysis changes
178 ===========================
180 We augmented the sched-deps.c with hooks that get called when a particular
181 dependence is found in a particular part of an insn. Using these hooks, we
182 can do several actions such as: determine whether an insn can be moved through
183 another (has_dependence_p, moveup_expr); find out whether an insn can be
184 scheduled on the current cycle (tick_check_p); find out registers that
185 are set/used/clobbered by an insn and find out all the strange stuff that
186 restrict its movement, like SCHED_GROUP_P or CANT_MOVE (done in
187 init_global_and_expr_for_insn).
189 Initialization changes
190 ======================
192 There are parts of haifa-sched.c, sched-deps.c, and sched-rgn.c that are
193 reused in all of the schedulers. We have split up the initialization of data
194 of such parts into different functions prefixed with scheduler type and
195 postfixed with the type of data initialized: {,sel_,haifa_}sched_{init,finish},
196 sched_rgn_init/finish, sched_deps_init/finish, sched_init_{luids/bbs}, etc.
197 The same splitting is done with current_sched_info structure:
198 dependence-related parts are in sched_deps_info, common part is in
199 common_sched_info, and haifa/sel/etc part is in current_sched_info.
201 Target contexts
202 ===============
204 As we now have multiple-point scheduling, this would not work with backends
205 which save some of the scheduler state to use it in the target hooks.
206 For this purpose, we introduce a concept of target contexts, which
207 encapsulate such information. The backend should implement simple routines
208 of allocating/freeing/setting such a context. The scheduler calls these
209 as target hooks and handles the target context as an opaque pointer (similar
210 to the DFA state type, state_t).
212 Various speedups
213 ================
215 As the correct data dependence graph is not supported during scheduling (which
216 is to be changed in mid-term), we cache as much of the dependence analysis
217 results as possible to avoid reanalyzing. This includes: bitmap caches on
218 each insn in stream of the region saying yes/no for a query with a pair of
219 UIDs; hashtables with the previously done transformations on each insn in
220 stream; a vector keeping a history of transformations on each expr.
222 Also, we try to minimize the dependence context used on each fence to check
223 whether the given expression is ready for scheduling by removing from it
224 insns that are definitely completed the execution. The results of
225 tick_check_p checks are also cached in a vector on each fence.
227 We keep a valid liveness set on each insn in a region to avoid the high
228 cost of recomputation on large basic blocks.
230 Finally, we try to minimize the number of needed updates to the availability
231 sets. The updates happen in two cases: when fill_insns terminates,
232 we advance all fences and increase the stage number to show that the region
233 has changed and the sets are to be recomputed; and when the next iteration
234 of a loop in fill_insns happens (but this one reuses the saved av sets
235 on bb headers.) Thus, we try to break the fill_insns loop only when
236 "significant" number of insns from the current scheduling window was
237 scheduled. This should be made a target param.
240 TODO: correctly support the data dependence graph at all stages and get rid
241 of all caches. This should speed up the scheduler.
242 TODO: implement moving cond jumps with bookkeeping copies on both targets.
243 TODO: tune the scheduler before RA so it does not create too much pseudos.
246 References:
247 S.-M. Moon and K. Ebcioglu. Parallelizing nonnumerical code with
248 selective scheduling and software pipelining.
249 ACM TOPLAS, Vol 19, No. 6, pages 853--898, Nov. 1997.
251 Andrey Belevantsev, Maxim Kuvyrkov, Vladimir Makarov, Dmitry Melnik,
252 and Dmitry Zhurikhin. An interblock VLIW-targeted instruction scheduler
253 for GCC. In Proceedings of GCC Developers' Summit 2006.
255 Arutyun Avetisyan, Andrey Belevantsev, and Dmitry Melnik. GCC Instruction
256 Scheduler and Software Pipeliner on the Itanium Platform. EPIC-7 Workshop.
257 http://rogue.colorado.edu/EPIC7/.
261 /* True when pipelining is enabled. */
262 bool pipelining_p;
264 /* True if bookkeeping is enabled. */
265 bool bookkeeping_p;
267 /* Maximum number of insns that are eligible for renaming. */
268 int max_insns_to_rename;
271 /* Definitions of local types and macros. */
273 /* Represents possible outcomes of moving an expression through an insn. */
274 enum MOVEUP_EXPR_CODE
276 /* The expression is not changed. */
277 MOVEUP_EXPR_SAME,
279 /* Not changed, but requires a new destination register. */
280 MOVEUP_EXPR_AS_RHS,
282 /* Cannot be moved. */
283 MOVEUP_EXPR_NULL,
285 /* Changed (substituted or speculated). */
286 MOVEUP_EXPR_CHANGED
289 /* The container to be passed into rtx search & replace functions. */
290 struct rtx_search_arg
292 /* What we are searching for. */
293 rtx x;
295 /* The occurrence counter. */
296 int n;
299 typedef struct rtx_search_arg *rtx_search_arg_p;
301 /* This struct contains precomputed hard reg sets that are needed when
302 computing registers available for renaming. */
303 struct hard_regs_data
305 /* For every mode, this stores registers available for use with
306 that mode. */
307 HARD_REG_SET regs_for_mode[NUM_MACHINE_MODES];
309 /* True when regs_for_mode[mode] is initialized. */
310 bool regs_for_mode_ok[NUM_MACHINE_MODES];
312 /* For every register, it has regs that are ok to rename into it.
313 The register in question is always set. If not, this means
314 that the whole set is not computed yet. */
315 HARD_REG_SET regs_for_rename[FIRST_PSEUDO_REGISTER];
317 /* For every mode, this stores registers not available due to
318 call clobbering. */
319 HARD_REG_SET regs_for_call_clobbered[NUM_MACHINE_MODES];
321 /* All registers that are used or call used. */
322 HARD_REG_SET regs_ever_used;
324 #ifdef STACK_REGS
325 /* Stack registers. */
326 HARD_REG_SET stack_regs;
327 #endif
330 /* Holds the results of computation of available for renaming and
331 unavailable hard registers. */
332 struct reg_rename
334 /* These are unavailable due to calls crossing, globalness, etc. */
335 HARD_REG_SET unavailable_hard_regs;
337 /* These are *available* for renaming. */
338 HARD_REG_SET available_for_renaming;
340 /* Whether this code motion path crosses a call. */
341 bool crosses_call;
344 /* A global structure that contains the needed information about harg
345 regs. */
346 static struct hard_regs_data sel_hrd;
349 /* This structure holds local data used in code_motion_path_driver hooks on
350 the same or adjacent levels of recursion. Here we keep those parameters
351 that are not used in code_motion_path_driver routine itself, but only in
352 its hooks. Moreover, all parameters that can be modified in hooks are
353 in this structure, so all other parameters passed explicitly to hooks are
354 read-only. */
355 struct cmpd_local_params
357 /* Local params used in move_op_* functions. */
359 /* Edges for bookkeeping generation. */
360 edge e1, e2;
362 /* C_EXPR merged from all successors and locally allocated temporary C_EXPR. */
363 expr_t c_expr_merged, c_expr_local;
365 /* Local params used in fur_* functions. */
366 /* Copy of the ORIGINAL_INSN list, stores the original insns already
367 found before entering the current level of code_motion_path_driver. */
368 def_list_t old_original_insns;
370 /* Local params used in move_op_* functions. */
371 /* True when we have removed last insn in the block which was
372 also a boundary. Do not update anything or create bookkeeping copies. */
373 BOOL_BITFIELD removed_last_insn : 1;
376 /* Stores the static parameters for move_op_* calls. */
377 struct moveop_static_params
379 /* Destination register. */
380 rtx dest;
382 /* Current C_EXPR. */
383 expr_t c_expr;
385 /* An UID of expr_vliw which is to be moved up. If we find other exprs,
386 they are to be removed. */
387 int uid;
389 #ifdef ENABLE_CHECKING
390 /* This is initialized to the insn on which the driver stopped its traversal. */
391 insn_t failed_insn;
392 #endif
394 /* True if we scheduled an insn with different register. */
395 bool was_renamed;
398 /* Stores the static parameters for fur_* calls. */
399 struct fur_static_params
401 /* Set of registers unavailable on the code motion path. */
402 regset used_regs;
404 /* Pointer to the list of original insns definitions. */
405 def_list_t *original_insns;
407 /* True if a code motion path contains a CALL insn. */
408 bool crosses_call;
411 typedef struct fur_static_params *fur_static_params_p;
412 typedef struct cmpd_local_params *cmpd_local_params_p;
413 typedef struct moveop_static_params *moveop_static_params_p;
415 /* Set of hooks and parameters that determine behaviour specific to
416 move_op or find_used_regs functions. */
417 struct code_motion_path_driver_info_def
419 /* Called on enter to the basic block. */
420 int (*on_enter) (insn_t, cmpd_local_params_p, void *, bool);
422 /* Called when original expr is found. */
423 void (*orig_expr_found) (insn_t, expr_t, cmpd_local_params_p, void *);
425 /* Called while descending current basic block if current insn is not
426 the original EXPR we're searching for. */
427 bool (*orig_expr_not_found) (insn_t, av_set_t, void *);
429 /* Function to merge C_EXPRes from different successors. */
430 void (*merge_succs) (insn_t, insn_t, int, cmpd_local_params_p, void *);
432 /* Function to finalize merge from different successors and possibly
433 deallocate temporary data structures used for merging. */
434 void (*after_merge_succs) (cmpd_local_params_p, void *);
436 /* Called on the backward stage of recursion to do moveup_expr.
437 Used only with move_op_*. */
438 void (*ascend) (insn_t, void *);
440 /* Called on the ascending pass, before returning from the current basic
441 block or from the whole traversal. */
442 void (*at_first_insn) (insn_t, cmpd_local_params_p, void *);
444 /* When processing successors in move_op we need only descend into
445 SUCCS_NORMAL successors, while in find_used_regs we need SUCCS_ALL. */
446 int succ_flags;
448 /* The routine name to print in dumps ("move_op" of "find_used_regs"). */
449 const char *routine_name;
452 /* Global pointer to current hooks, either points to MOVE_OP_HOOKS or
453 FUR_HOOKS. */
454 struct code_motion_path_driver_info_def *code_motion_path_driver_info;
456 /* Set of hooks for performing move_op and find_used_regs routines with
457 code_motion_path_driver. */
458 extern struct code_motion_path_driver_info_def move_op_hooks, fur_hooks;
460 /* True if/when we want to emulate Haifa scheduler in the common code.
461 This is used in sched_rgn_local_init and in various places in
462 sched-deps.c. */
463 int sched_emulate_haifa_p;
465 /* GLOBAL_LEVEL is used to discard information stored in basic block headers
466 av_sets. Av_set of bb header is valid if its (bb header's) level is equal
467 to GLOBAL_LEVEL. And invalid if lesser. This is primarily used to advance
468 scheduling window. */
469 int global_level;
471 /* Current fences. */
472 flist_t fences;
474 /* True when separable insns should be scheduled as RHSes. */
475 static bool enable_schedule_as_rhs_p;
477 /* Used in verify_target_availability to assert that target reg is reported
478 unavailabile by both TARGET_UNAVAILABLE and find_used_regs only if
479 we haven't scheduled anything on the previous fence.
480 if scheduled_something_on_previous_fence is true, TARGET_UNAVAILABLE can
481 have more conservative value than the one returned by the
482 find_used_regs, thus we shouldn't assert that these values are equal. */
483 static bool scheduled_something_on_previous_fence;
485 /* All newly emitted insns will have their uids greater than this value. */
486 static int first_emitted_uid;
488 /* Set of basic blocks that are forced to start new ebbs. This is a subset
489 of all the ebb heads. */
490 static bitmap_head _forced_ebb_heads;
491 bitmap_head *forced_ebb_heads = &_forced_ebb_heads;
493 /* Blocks that need to be rescheduled after pipelining. */
494 bitmap blocks_to_reschedule = NULL;
496 /* True when the first lv set should be ignored when updating liveness. */
497 static bool ignore_first = false;
499 /* Number of insns max_issue has initialized data structures for. */
500 static int max_issue_size = 0;
502 /* Whether we can issue more instructions. */
503 static int can_issue_more;
505 /* Maximum software lookahead window size, reduced when rescheduling after
506 pipelining. */
507 static int max_ws;
509 /* Number of insns scheduled in current region. */
510 static int num_insns_scheduled;
512 /* A vector of expressions is used to be able to sort them. */
513 static vec<expr_t> vec_av_set = vNULL;
515 /* A vector of vinsns is used to hold temporary lists of vinsns. */
516 typedef vec<vinsn_t> vinsn_vec_t;
518 /* This vector has the exprs which may still present in av_sets, but actually
519 can't be moved up due to bookkeeping created during code motion to another
520 fence. See comment near the call to update_and_record_unavailable_insns
521 for the detailed explanations. */
522 static vinsn_vec_t vec_bookkeeping_blocked_vinsns = vinsn_vec_t ();
524 /* This vector has vinsns which are scheduled with renaming on the first fence
525 and then seen on the second. For expressions with such vinsns, target
526 availability information may be wrong. */
527 static vinsn_vec_t vec_target_unavailable_vinsns = vinsn_vec_t ();
529 /* Vector to store temporary nops inserted in move_op to prevent removal
530 of empty bbs. */
531 static vec<insn_t> vec_temp_moveop_nops = vNULL;
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;
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;
542 /* Variables to accumulate different statistics. */
544 /* The number of bookkeeping copies created. */
545 static int stat_bookkeeping_copies;
547 /* The number of insns that required bookkeeiping for their scheduling. */
548 static int stat_insns_needed_bookkeeping;
550 /* The number of insns that got renamed. */
551 static int stat_renamed_scheduled;
553 /* The number of substitutions made during scheduling. */
554 static int stat_substitutions_total;
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);
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);
574 static void debug_state (state_t);
577 /* Functions that work with fences. */
579 /* Advance one cycle on FENCE. */
580 static void
581 advance_one_cycle (fence_t fence)
583 unsigned i;
584 int cycle;
585 rtx_insn *insn;
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;
594 for (i = 0; vec_safe_iterate (FENCE_EXECUTING_INSNS (fence), i, &insn); )
596 if (INSN_READY_CYCLE (insn) < cycle)
598 remove_from_deps (FENCE_DC (fence), insn);
599 FENCE_EXECUTING_INSNS (fence)->unordered_remove (i);
600 continue;
602 i++;
604 if (sched_verbose >= 2)
606 sel_print ("Finished a cycle. Current cycle = %d\n", FENCE_CYCLE (fence));
607 debug_state (FENCE_STATE (fence));
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)
616 basic_block bb = BLOCK_FOR_INSN (insn);
617 edge e;
619 if (bb == BLOCK_FOR_INSN (succ))
620 return true;
622 e = find_fallthru_edge_from (bb);
623 if (e)
624 bb = e->dest;
625 else
626 return false;
628 while (sel_bb_empty_p (bb))
629 bb = bb->next_bb;
631 return bb == BLOCK_FOR_INSN (succ);
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)
642 bool was_here_p = false;
643 insn_t insn = NULL;
644 insn_t succ;
645 succ_iterator si;
646 ilist_iterator ii;
647 fence_t fence = FLIST_FENCE (old_fences);
648 basic_block bb;
650 /* Get the only element of FENCE_BNDS (fence). */
651 FOR_EACH_INSN (insn, ii, FENCE_BNDS (fence))
653 gcc_assert (!was_here_p);
654 was_here_p = true;
656 gcc_assert (was_here_p && insn != NULL_RTX);
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))))
665 insn_t succ;
667 succ = (sel_bb_end_p (insn)
668 ? sel_bb_head (single_succ (bb))
669 : NEXT_INSN (insn));
671 if (INSN_SEQNO (succ) > 0
672 && INSN_SEQNO (succ) <= orig_max_seqno
673 && INSN_SCHED_TIMES (succ) <= 0)
675 FENCE_INSN (fence) = succ;
676 move_fence_to_fences (old_fences, new_fences);
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));
682 return;
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)
688 int seqno = INSN_SEQNO (succ);
690 if (0 < seqno && seqno <= orig_max_seqno
691 && (pipelining_p || INSN_SCHED_TIMES (succ) <= 0))
693 bool b = (in_same_ebb_p (insn, succ)
694 || in_fallthru_bb_p (insn, succ));
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");
701 if (b)
702 add_dirty_fence_to_fences (new_fences, succ, fence);
703 else
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);
714 /* Functions to support substitution. */
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)
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;
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;
737 /* Substitute all occurrences 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)
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;
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);
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))
766 rtx_insn *new_insn;
767 rtx *where_replace;
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));
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));
780 new_insn_valid
781 = validate_replace_rtx_part_nosimplify (old, new_rtx, where_replace,
782 new_insn);
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)
792 change_vinsn_in_expr (expr,
793 create_vinsn_from_insn_rtx (new_insn, false));
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;
802 return true;
804 else
805 return false;
807 else
808 return false;
811 /* Return the number of places WHAT appears within WHERE.
812 Bail out when we found a reference occupying several hard registers. */
813 static int
814 count_occurrences_equiv (const_rtx what, const_rtx where)
816 int count = 0;
817 subrtx_iterator::array_type array;
818 FOR_EACH_SUBRTX (iter, array, where, NONCONST)
820 const_rtx x = *iter;
821 if (REG_P (x) && REGNO (x) == REGNO (what))
823 /* Bail out if mode is different or more than one register is
824 used. */
825 if (GET_MODE (x) != GET_MODE (what)
826 || (HARD_REGISTER_P (x)
827 && hard_regno_nregs[REGNO (x)][GET_MODE (x)] > 1))
828 return 0;
829 count += 1;
831 else if (GET_CODE (x) == SUBREG
832 && (!REG_P (SUBREG_REG (x))
833 || REGNO (SUBREG_REG (x)) == REGNO (what)))
834 /* ??? Do not support substituting regs inside subregs. In that case,
835 simplify_subreg will be called by validate_replace_rtx, and
836 unsubstitution will fail later. */
837 return 0;
839 return count;
842 /* Returns TRUE if WHAT is found in WHERE rtx tree. */
843 static bool
844 rtx_ok_for_substitution_p (rtx what, rtx where)
846 return (count_occurrences_equiv (what, where) > 0);
850 /* Functions to support register renaming. */
852 /* Substitute VI's set source with REGNO. Returns newly created pattern
853 that has REGNO as its source. */
854 static rtx_insn *
855 create_insn_rtx_with_rhs (vinsn_t vi, rtx rhs_rtx)
857 rtx lhs_rtx;
858 rtx pattern;
859 rtx_insn *insn_rtx;
861 lhs_rtx = copy_rtx (VINSN_LHS (vi));
863 pattern = gen_rtx_SET (VOIDmode, lhs_rtx, rhs_rtx);
864 insn_rtx = create_insn_rtx_from_pattern (pattern, NULL_RTX);
866 return insn_rtx;
869 /* Returns whether INSN's src can be replaced with register number
870 NEW_SRC_REG. E.g. the following insn is valid for i386:
872 (insn:HI 2205 6585 2207 727 ../../gcc/libiberty/regex.c:3337
873 (set (mem/s:QI (plus:SI (plus:SI (reg/f:SI 7 sp)
874 (reg:SI 0 ax [orig:770 c1 ] [770]))
875 (const_int 288 [0x120])) [0 str S1 A8])
876 (const_int 0 [0x0])) 43 {*movqi_1} (nil)
877 (nil))
879 But if we change (const_int 0 [0x0]) to (reg:QI 4 si), it will be invalid
880 because of operand constraints:
882 (define_insn "*movqi_1"
883 [(set (match_operand:QI 0 "nonimmediate_operand" "=q,q ,q ,r,r ,?r,m")
884 (match_operand:QI 1 "general_operand" " q,qn,qm,q,rn,qm,qn")
887 So do constrain_operands here, before choosing NEW_SRC_REG as best
888 reg for rhs. */
890 static bool
891 replace_src_with_reg_ok_p (insn_t insn, rtx new_src_reg)
893 vinsn_t vi = INSN_VINSN (insn);
894 machine_mode mode;
895 rtx dst_loc;
896 bool res;
898 gcc_assert (VINSN_SEPARABLE_P (vi));
900 get_dest_and_mode (insn, &dst_loc, &mode);
901 gcc_assert (mode == GET_MODE (new_src_reg));
903 if (REG_P (dst_loc) && REGNO (new_src_reg) == REGNO (dst_loc))
904 return true;
906 /* See whether SET_SRC can be replaced with this register. */
907 validate_change (insn, &SET_SRC (PATTERN (insn)), new_src_reg, 1);
908 res = verify_changes (0);
909 cancel_changes (0);
911 return res;
914 /* Returns whether INSN still be valid after replacing it's DEST with
915 register NEW_REG. */
916 static bool
917 replace_dest_with_reg_ok_p (insn_t insn, rtx new_reg)
919 vinsn_t vi = INSN_VINSN (insn);
920 bool res;
922 /* We should deal here only with separable insns. */
923 gcc_assert (VINSN_SEPARABLE_P (vi));
924 gcc_assert (GET_MODE (VINSN_LHS (vi)) == GET_MODE (new_reg));
926 /* See whether SET_DEST can be replaced with this register. */
927 validate_change (insn, &SET_DEST (PATTERN (insn)), new_reg, 1);
928 res = verify_changes (0);
929 cancel_changes (0);
931 return res;
934 /* Create a pattern with rhs of VI and lhs of LHS_RTX. */
935 static rtx_insn *
936 create_insn_rtx_with_lhs (vinsn_t vi, rtx lhs_rtx)
938 rtx rhs_rtx;
939 rtx pattern;
940 rtx_insn *insn_rtx;
942 rhs_rtx = copy_rtx (VINSN_RHS (vi));
944 pattern = gen_rtx_SET (VOIDmode, lhs_rtx, rhs_rtx);
945 insn_rtx = create_insn_rtx_from_pattern (pattern, NULL_RTX);
947 return insn_rtx;
950 /* Substitute lhs in the given expression EXPR for the register with number
951 NEW_REGNO. SET_DEST may be arbitrary rtx, not only register. */
952 static void
953 replace_dest_with_reg_in_expr (expr_t expr, rtx new_reg)
955 rtx_insn *insn_rtx;
956 vinsn_t vinsn;
958 insn_rtx = create_insn_rtx_with_lhs (EXPR_VINSN (expr), new_reg);
959 vinsn = create_vinsn_from_insn_rtx (insn_rtx, false);
961 change_vinsn_in_expr (expr, vinsn);
962 EXPR_WAS_RENAMED (expr) = 1;
963 EXPR_TARGET_AVAILABLE (expr) = 1;
966 /* Returns whether VI writes either one of the USED_REGS registers or,
967 if a register is a hard one, one of the UNAVAILABLE_HARD_REGS registers. */
968 static bool
969 vinsn_writes_one_of_regs_p (vinsn_t vi, regset used_regs,
970 HARD_REG_SET unavailable_hard_regs)
972 unsigned regno;
973 reg_set_iterator rsi;
975 EXECUTE_IF_SET_IN_REG_SET (VINSN_REG_SETS (vi), 0, regno, rsi)
977 if (REGNO_REG_SET_P (used_regs, regno))
978 return true;
979 if (HARD_REGISTER_NUM_P (regno)
980 && TEST_HARD_REG_BIT (unavailable_hard_regs, regno))
981 return true;
984 EXECUTE_IF_SET_IN_REG_SET (VINSN_REG_CLOBBERS (vi), 0, regno, rsi)
986 if (REGNO_REG_SET_P (used_regs, regno))
987 return true;
988 if (HARD_REGISTER_NUM_P (regno)
989 && TEST_HARD_REG_BIT (unavailable_hard_regs, regno))
990 return true;
993 return false;
996 /* Returns register class of the output register in INSN.
997 Returns NO_REGS for call insns because some targets have constraints on
998 destination register of a call insn.
1000 Code adopted from regrename.c::build_def_use. */
1001 static enum reg_class
1002 get_reg_class (rtx_insn *insn)
1004 int i, n_ops;
1006 extract_constrain_insn (insn);
1007 preprocess_constraints (insn);
1008 n_ops = recog_data.n_operands;
1010 const operand_alternative *op_alt = which_op_alt ();
1011 if (asm_noperands (PATTERN (insn)) > 0)
1013 for (i = 0; i < n_ops; i++)
1014 if (recog_data.operand_type[i] == OP_OUT)
1016 rtx *loc = recog_data.operand_loc[i];
1017 rtx op = *loc;
1018 enum reg_class cl = alternative_class (op_alt, i);
1020 if (REG_P (op)
1021 && REGNO (op) == ORIGINAL_REGNO (op))
1022 continue;
1024 return cl;
1027 else if (!CALL_P (insn))
1029 for (i = 0; i < n_ops + recog_data.n_dups; i++)
1031 int opn = i < n_ops ? i : recog_data.dup_num[i - n_ops];
1032 enum reg_class cl = alternative_class (op_alt, opn);
1034 if (recog_data.operand_type[opn] == OP_OUT ||
1035 recog_data.operand_type[opn] == OP_INOUT)
1036 return cl;
1040 /* Insns like
1041 (insn (set (reg:CCZ 17 flags) (compare:CCZ ...)))
1042 may result in returning NO_REGS, cause flags is written implicitly through
1043 CMP insn, which has no OP_OUT | OP_INOUT operands. */
1044 return NO_REGS;
1047 #ifdef HARD_REGNO_RENAME_OK
1048 /* Calculate HARD_REGNO_RENAME_OK data for REGNO. */
1049 static void
1050 init_hard_regno_rename (int regno)
1052 int cur_reg;
1054 SET_HARD_REG_BIT (sel_hrd.regs_for_rename[regno], regno);
1056 for (cur_reg = 0; cur_reg < FIRST_PSEUDO_REGISTER; cur_reg++)
1058 /* We are not interested in renaming in other regs. */
1059 if (!TEST_HARD_REG_BIT (sel_hrd.regs_ever_used, cur_reg))
1060 continue;
1062 if (HARD_REGNO_RENAME_OK (regno, cur_reg))
1063 SET_HARD_REG_BIT (sel_hrd.regs_for_rename[regno], cur_reg);
1066 #endif
1068 /* A wrapper around HARD_REGNO_RENAME_OK that will look into the hard regs
1069 data first. */
1070 static inline bool
1071 sel_hard_regno_rename_ok (int from ATTRIBUTE_UNUSED, int to ATTRIBUTE_UNUSED)
1073 #ifdef HARD_REGNO_RENAME_OK
1074 /* Check whether this is all calculated. */
1075 if (TEST_HARD_REG_BIT (sel_hrd.regs_for_rename[from], from))
1076 return TEST_HARD_REG_BIT (sel_hrd.regs_for_rename[from], to);
1078 init_hard_regno_rename (from);
1080 return TEST_HARD_REG_BIT (sel_hrd.regs_for_rename[from], to);
1081 #else
1082 return true;
1083 #endif
1086 /* Calculate set of registers that are capable of holding MODE. */
1087 static void
1088 init_regs_for_mode (machine_mode mode)
1090 int cur_reg;
1092 CLEAR_HARD_REG_SET (sel_hrd.regs_for_mode[mode]);
1093 CLEAR_HARD_REG_SET (sel_hrd.regs_for_call_clobbered[mode]);
1095 for (cur_reg = 0; cur_reg < FIRST_PSEUDO_REGISTER; cur_reg++)
1097 int nregs;
1098 int i;
1100 /* See whether it accepts all modes that occur in
1101 original insns. */
1102 if (! HARD_REGNO_MODE_OK (cur_reg, mode))
1103 continue;
1105 nregs = hard_regno_nregs[cur_reg][mode];
1107 for (i = nregs - 1; i >= 0; --i)
1108 if (fixed_regs[cur_reg + i]
1109 || global_regs[cur_reg + i]
1110 /* Can't use regs which aren't saved by
1111 the prologue. */
1112 || !TEST_HARD_REG_BIT (sel_hrd.regs_ever_used, cur_reg + i)
1113 /* Can't use regs with non-null REG_BASE_VALUE, because adjusting
1114 it affects aliasing globally and invalidates all AV sets. */
1115 || get_reg_base_value (cur_reg + i)
1116 #ifdef LEAF_REGISTERS
1117 /* We can't use a non-leaf register if we're in a
1118 leaf function. */
1119 || (crtl->is_leaf
1120 && !LEAF_REGISTERS[cur_reg + i])
1121 #endif
1123 break;
1125 if (i >= 0)
1126 continue;
1128 if (HARD_REGNO_CALL_PART_CLOBBERED (cur_reg, mode))
1129 SET_HARD_REG_BIT (sel_hrd.regs_for_call_clobbered[mode],
1130 cur_reg);
1132 /* If the CUR_REG passed all the checks above,
1133 then it's ok. */
1134 SET_HARD_REG_BIT (sel_hrd.regs_for_mode[mode], cur_reg);
1137 sel_hrd.regs_for_mode_ok[mode] = true;
1140 /* Init all register sets gathered in HRD. */
1141 static void
1142 init_hard_regs_data (void)
1144 int cur_reg = 0;
1145 int cur_mode = 0;
1147 CLEAR_HARD_REG_SET (sel_hrd.regs_ever_used);
1148 for (cur_reg = 0; cur_reg < FIRST_PSEUDO_REGISTER; cur_reg++)
1149 if (df_regs_ever_live_p (cur_reg) || call_used_regs[cur_reg])
1150 SET_HARD_REG_BIT (sel_hrd.regs_ever_used, cur_reg);
1152 /* Initialize registers that are valid based on mode when this is
1153 really needed. */
1154 for (cur_mode = 0; cur_mode < NUM_MACHINE_MODES; cur_mode++)
1155 sel_hrd.regs_for_mode_ok[cur_mode] = false;
1157 /* Mark that all HARD_REGNO_RENAME_OK is not calculated. */
1158 for (cur_reg = 0; cur_reg < FIRST_PSEUDO_REGISTER; cur_reg++)
1159 CLEAR_HARD_REG_SET (sel_hrd.regs_for_rename[cur_reg]);
1161 #ifdef STACK_REGS
1162 CLEAR_HARD_REG_SET (sel_hrd.stack_regs);
1164 for (cur_reg = FIRST_STACK_REG; cur_reg <= LAST_STACK_REG; cur_reg++)
1165 SET_HARD_REG_BIT (sel_hrd.stack_regs, cur_reg);
1166 #endif
1169 /* Mark hardware regs in REG_RENAME_P that are not suitable
1170 for renaming rhs in INSN due to hardware restrictions (register class,
1171 modes compatibility etc). This doesn't affect original insn's dest reg,
1172 if it isn't in USED_REGS. DEF is a definition insn of rhs for which the
1173 destination register is sought. LHS (DEF->ORIG_INSN) may be REG or MEM.
1174 Registers that are in used_regs are always marked in
1175 unavailable_hard_regs as well. */
1177 static void
1178 mark_unavailable_hard_regs (def_t def, struct reg_rename *reg_rename_p,
1179 regset used_regs ATTRIBUTE_UNUSED)
1181 machine_mode mode;
1182 enum reg_class cl = NO_REGS;
1183 rtx orig_dest;
1184 unsigned cur_reg, regno;
1185 hard_reg_set_iterator hrsi;
1187 gcc_assert (GET_CODE (PATTERN (def->orig_insn)) == SET);
1188 gcc_assert (reg_rename_p);
1190 orig_dest = SET_DEST (PATTERN (def->orig_insn));
1192 /* We have decided not to rename 'mem = something;' insns, as 'something'
1193 is usually a register. */
1194 if (!REG_P (orig_dest))
1195 return;
1197 regno = REGNO (orig_dest);
1199 /* If before reload, don't try to work with pseudos. */
1200 if (!reload_completed && !HARD_REGISTER_NUM_P (regno))
1201 return;
1203 if (reload_completed)
1204 cl = get_reg_class (def->orig_insn);
1206 /* Stop if the original register is one of the fixed_regs, global_regs or
1207 frame pointer, or we could not discover its class. */
1208 if (fixed_regs[regno]
1209 || global_regs[regno]
1210 #if !HARD_FRAME_POINTER_IS_FRAME_POINTER
1211 || (frame_pointer_needed && regno == HARD_FRAME_POINTER_REGNUM)
1212 #else
1213 || (frame_pointer_needed && regno == FRAME_POINTER_REGNUM)
1214 #endif
1215 || (reload_completed && cl == NO_REGS))
1217 SET_HARD_REG_SET (reg_rename_p->unavailable_hard_regs);
1219 /* Give a chance for original register, if it isn't in used_regs. */
1220 if (!def->crosses_call)
1221 CLEAR_HARD_REG_BIT (reg_rename_p->unavailable_hard_regs, regno);
1223 return;
1226 /* If something allocated on stack in this function, mark frame pointer
1227 register unavailable, considering also modes.
1228 FIXME: it is enough to do this once per all original defs. */
1229 if (frame_pointer_needed)
1231 add_to_hard_reg_set (&reg_rename_p->unavailable_hard_regs,
1232 Pmode, FRAME_POINTER_REGNUM);
1234 if (!HARD_FRAME_POINTER_IS_FRAME_POINTER)
1235 add_to_hard_reg_set (&reg_rename_p->unavailable_hard_regs,
1236 Pmode, HARD_FRAME_POINTER_REGNUM);
1239 #ifdef STACK_REGS
1240 /* For the stack registers the presence of FIRST_STACK_REG in USED_REGS
1241 is equivalent to as if all stack regs were in this set.
1242 I.e. no stack register can be renamed, and even if it's an original
1243 register here we make sure it won't be lifted over it's previous def
1244 (it's previous def will appear as if it's a FIRST_STACK_REG def.
1245 The HARD_REGNO_RENAME_OK covers other cases in condition below. */
1246 if (IN_RANGE (REGNO (orig_dest), FIRST_STACK_REG, LAST_STACK_REG)
1247 && REGNO_REG_SET_P (used_regs, FIRST_STACK_REG))
1248 IOR_HARD_REG_SET (reg_rename_p->unavailable_hard_regs,
1249 sel_hrd.stack_regs);
1250 #endif
1252 /* If there's a call on this path, make regs from call_used_reg_set
1253 unavailable. */
1254 if (def->crosses_call)
1255 IOR_HARD_REG_SET (reg_rename_p->unavailable_hard_regs,
1256 call_used_reg_set);
1258 /* Stop here before reload: we need FRAME_REGS, STACK_REGS, and crosses_call,
1259 but not register classes. */
1260 if (!reload_completed)
1261 return;
1263 /* Leave regs as 'available' only from the current
1264 register class. */
1265 COPY_HARD_REG_SET (reg_rename_p->available_for_renaming,
1266 reg_class_contents[cl]);
1268 mode = GET_MODE (orig_dest);
1270 /* Leave only registers available for this mode. */
1271 if (!sel_hrd.regs_for_mode_ok[mode])
1272 init_regs_for_mode (mode);
1273 AND_HARD_REG_SET (reg_rename_p->available_for_renaming,
1274 sel_hrd.regs_for_mode[mode]);
1276 /* Exclude registers that are partially call clobbered. */
1277 if (def->crosses_call
1278 && ! HARD_REGNO_CALL_PART_CLOBBERED (regno, mode))
1279 AND_COMPL_HARD_REG_SET (reg_rename_p->available_for_renaming,
1280 sel_hrd.regs_for_call_clobbered[mode]);
1282 /* Leave only those that are ok to rename. */
1283 EXECUTE_IF_SET_IN_HARD_REG_SET (reg_rename_p->available_for_renaming,
1284 0, cur_reg, hrsi)
1286 int nregs;
1287 int i;
1289 nregs = hard_regno_nregs[cur_reg][mode];
1290 gcc_assert (nregs > 0);
1292 for (i = nregs - 1; i >= 0; --i)
1293 if (! sel_hard_regno_rename_ok (regno + i, cur_reg + i))
1294 break;
1296 if (i >= 0)
1297 CLEAR_HARD_REG_BIT (reg_rename_p->available_for_renaming,
1298 cur_reg);
1301 AND_COMPL_HARD_REG_SET (reg_rename_p->available_for_renaming,
1302 reg_rename_p->unavailable_hard_regs);
1304 /* Regno is always ok from the renaming part of view, but it really
1305 could be in *unavailable_hard_regs already, so set it here instead
1306 of there. */
1307 SET_HARD_REG_BIT (reg_rename_p->available_for_renaming, regno);
1310 /* reg_rename_tick[REG1] > reg_rename_tick[REG2] if REG1 was chosen as the
1311 best register more recently than REG2. */
1312 static int reg_rename_tick[FIRST_PSEUDO_REGISTER];
1314 /* Indicates the number of times renaming happened before the current one. */
1315 static int reg_rename_this_tick;
1317 /* Choose the register among free, that is suitable for storing
1318 the rhs value.
1320 ORIGINAL_INSNS is the list of insns where the operation (rhs)
1321 originally appears. There could be multiple original operations
1322 for single rhs since we moving it up and merging along different
1323 paths.
1325 Some code is adapted from regrename.c (regrename_optimize).
1326 If original register is available, function returns it.
1327 Otherwise it performs the checks, so the new register should
1328 comply with the following:
1329 - it should not violate any live ranges (such registers are in
1330 REG_RENAME_P->available_for_renaming set);
1331 - it should not be in the HARD_REGS_USED regset;
1332 - it should be in the class compatible with original uses;
1333 - it should not be clobbered through reference with different mode;
1334 - if we're in the leaf function, then the new register should
1335 not be in the LEAF_REGISTERS;
1336 - etc.
1338 If several registers meet the conditions, the register with smallest
1339 tick is returned to achieve more even register allocation.
1341 If original register seems to be ok, we set *IS_ORIG_REG_P_PTR to true.
1343 If no register satisfies the above conditions, NULL_RTX is returned. */
1344 static rtx
1345 choose_best_reg_1 (HARD_REG_SET hard_regs_used,
1346 struct reg_rename *reg_rename_p,
1347 def_list_t original_insns, bool *is_orig_reg_p_ptr)
1349 int best_new_reg;
1350 unsigned cur_reg;
1351 machine_mode mode = VOIDmode;
1352 unsigned regno, i, n;
1353 hard_reg_set_iterator hrsi;
1354 def_list_iterator di;
1355 def_t def;
1357 /* If original register is available, return it. */
1358 *is_orig_reg_p_ptr = true;
1360 FOR_EACH_DEF (def, di, original_insns)
1362 rtx orig_dest = SET_DEST (PATTERN (def->orig_insn));
1364 gcc_assert (REG_P (orig_dest));
1366 /* Check that all original operations have the same mode.
1367 This is done for the next loop; if we'd return from this
1368 loop, we'd check only part of them, but in this case
1369 it doesn't matter. */
1370 if (mode == VOIDmode)
1371 mode = GET_MODE (orig_dest);
1372 gcc_assert (mode == GET_MODE (orig_dest));
1374 regno = REGNO (orig_dest);
1375 for (i = 0, n = hard_regno_nregs[regno][mode]; i < n; i++)
1376 if (TEST_HARD_REG_BIT (hard_regs_used, regno + i))
1377 break;
1379 /* All hard registers are available. */
1380 if (i == n)
1382 gcc_assert (mode != VOIDmode);
1384 /* Hard registers should not be shared. */
1385 return gen_rtx_REG (mode, regno);
1389 *is_orig_reg_p_ptr = false;
1390 best_new_reg = -1;
1392 /* Among all available regs choose the register that was
1393 allocated earliest. */
1394 EXECUTE_IF_SET_IN_HARD_REG_SET (reg_rename_p->available_for_renaming,
1395 0, cur_reg, hrsi)
1396 if (! TEST_HARD_REG_BIT (hard_regs_used, cur_reg))
1398 /* Check that all hard regs for mode are available. */
1399 for (i = 1, n = hard_regno_nregs[cur_reg][mode]; i < n; i++)
1400 if (TEST_HARD_REG_BIT (hard_regs_used, cur_reg + i)
1401 || !TEST_HARD_REG_BIT (reg_rename_p->available_for_renaming,
1402 cur_reg + i))
1403 break;
1405 if (i < n)
1406 continue;
1408 /* All hard registers are available. */
1409 if (best_new_reg < 0
1410 || reg_rename_tick[cur_reg] < reg_rename_tick[best_new_reg])
1412 best_new_reg = cur_reg;
1414 /* Return immediately when we know there's no better reg. */
1415 if (! reg_rename_tick[best_new_reg])
1416 break;
1420 if (best_new_reg >= 0)
1422 /* Use the check from the above loop. */
1423 gcc_assert (mode != VOIDmode);
1424 return gen_rtx_REG (mode, best_new_reg);
1427 return NULL_RTX;
1430 /* A wrapper around choose_best_reg_1 () to verify that we make correct
1431 assumptions about available registers in the function. */
1432 static rtx
1433 choose_best_reg (HARD_REG_SET hard_regs_used, struct reg_rename *reg_rename_p,
1434 def_list_t original_insns, bool *is_orig_reg_p_ptr)
1436 rtx best_reg = choose_best_reg_1 (hard_regs_used, reg_rename_p,
1437 original_insns, is_orig_reg_p_ptr);
1439 /* FIXME loop over hard_regno_nregs here. */
1440 gcc_assert (best_reg == NULL_RTX
1441 || TEST_HARD_REG_BIT (sel_hrd.regs_ever_used, REGNO (best_reg)));
1443 return best_reg;
1446 /* Choose the pseudo register for storing rhs value. As this is supposed
1447 to work before reload, we return either the original register or make
1448 the new one. The parameters are the same that in choose_nest_reg_1
1449 functions, except that USED_REGS may contain pseudos.
1450 If we work with hard regs, check also REG_RENAME_P->UNAVAILABLE_HARD_REGS.
1452 TODO: take into account register pressure while doing this. Up to this
1453 moment, this function would never return NULL for pseudos, but we should
1454 not rely on this. */
1455 static rtx
1456 choose_best_pseudo_reg (regset used_regs,
1457 struct reg_rename *reg_rename_p,
1458 def_list_t original_insns, bool *is_orig_reg_p_ptr)
1460 def_list_iterator i;
1461 def_t def;
1462 machine_mode mode = VOIDmode;
1463 bool bad_hard_regs = false;
1465 /* We should not use this after reload. */
1466 gcc_assert (!reload_completed);
1468 /* If original register is available, return it. */
1469 *is_orig_reg_p_ptr = true;
1471 FOR_EACH_DEF (def, i, original_insns)
1473 rtx dest = SET_DEST (PATTERN (def->orig_insn));
1474 int orig_regno;
1476 gcc_assert (REG_P (dest));
1478 /* Check that all original operations have the same mode. */
1479 if (mode == VOIDmode)
1480 mode = GET_MODE (dest);
1481 else
1482 gcc_assert (mode == GET_MODE (dest));
1483 orig_regno = REGNO (dest);
1485 if (!REGNO_REG_SET_P (used_regs, orig_regno))
1487 if (orig_regno < FIRST_PSEUDO_REGISTER)
1489 gcc_assert (df_regs_ever_live_p (orig_regno));
1491 /* For hard registers, we have to check hardware imposed
1492 limitations (frame/stack registers, calls crossed). */
1493 if (!TEST_HARD_REG_BIT (reg_rename_p->unavailable_hard_regs,
1494 orig_regno))
1496 /* Don't let register cross a call if it doesn't already
1497 cross one. This condition is written in accordance with
1498 that in sched-deps.c sched_analyze_reg(). */
1499 if (!reg_rename_p->crosses_call
1500 || REG_N_CALLS_CROSSED (orig_regno) > 0)
1501 return gen_rtx_REG (mode, orig_regno);
1504 bad_hard_regs = true;
1506 else
1507 return dest;
1511 *is_orig_reg_p_ptr = false;
1513 /* We had some original hard registers that couldn't be used.
1514 Those were likely special. Don't try to create a pseudo. */
1515 if (bad_hard_regs)
1516 return NULL_RTX;
1518 /* We haven't found a register from original operations. Get a new one.
1519 FIXME: control register pressure somehow. */
1521 rtx new_reg = gen_reg_rtx (mode);
1523 gcc_assert (mode != VOIDmode);
1525 max_regno = max_reg_num ();
1526 maybe_extend_reg_info_p ();
1527 REG_N_CALLS_CROSSED (REGNO (new_reg)) = reg_rename_p->crosses_call ? 1 : 0;
1529 return new_reg;
1533 /* True when target of EXPR is available due to EXPR_TARGET_AVAILABLE,
1534 USED_REGS and REG_RENAME_P->UNAVAILABLE_HARD_REGS. */
1535 static void
1536 verify_target_availability (expr_t expr, regset used_regs,
1537 struct reg_rename *reg_rename_p)
1539 unsigned n, i, regno;
1540 machine_mode mode;
1541 bool target_available, live_available, hard_available;
1543 if (!REG_P (EXPR_LHS (expr)) || EXPR_TARGET_AVAILABLE (expr) < 0)
1544 return;
1546 regno = expr_dest_regno (expr);
1547 mode = GET_MODE (EXPR_LHS (expr));
1548 target_available = EXPR_TARGET_AVAILABLE (expr) == 1;
1549 n = HARD_REGISTER_NUM_P (regno) ? hard_regno_nregs[regno][mode] : 1;
1551 live_available = hard_available = true;
1552 for (i = 0; i < n; i++)
1554 if (bitmap_bit_p (used_regs, regno + i))
1555 live_available = false;
1556 if (TEST_HARD_REG_BIT (reg_rename_p->unavailable_hard_regs, regno + i))
1557 hard_available = false;
1560 /* When target is not available, it may be due to hard register
1561 restrictions, e.g. crosses calls, so we check hard_available too. */
1562 if (target_available)
1563 gcc_assert (live_available);
1564 else
1565 /* Check only if we haven't scheduled something on the previous fence,
1566 cause due to MAX_SOFTWARE_LOOKAHEAD_WINDOW_SIZE issues
1567 and having more than one fence, we may end having targ_un in a block
1568 in which successors target register is actually available.
1570 The last condition handles the case when a dependence from a call insn
1571 was created in sched-deps.c for insns with destination registers that
1572 never crossed a call before, but do cross one after our code motion.
1574 FIXME: in the latter case, we just uselessly called find_used_regs,
1575 because we can't move this expression with any other register
1576 as well. */
1577 gcc_assert (scheduled_something_on_previous_fence || !live_available
1578 || !hard_available
1579 || (!reload_completed && reg_rename_p->crosses_call
1580 && REG_N_CALLS_CROSSED (regno) == 0));
1583 /* Collect unavailable registers due to liveness for EXPR from BNDS
1584 into USED_REGS. Save additional information about available
1585 registers and unavailable due to hardware restriction registers
1586 into REG_RENAME_P structure. Save original insns into ORIGINAL_INSNS
1587 list. */
1588 static void
1589 collect_unavailable_regs_from_bnds (expr_t expr, blist_t bnds, regset used_regs,
1590 struct reg_rename *reg_rename_p,
1591 def_list_t *original_insns)
1593 for (; bnds; bnds = BLIST_NEXT (bnds))
1595 bool res;
1596 av_set_t orig_ops = NULL;
1597 bnd_t bnd = BLIST_BND (bnds);
1599 /* If the chosen best expr doesn't belong to current boundary,
1600 skip it. */
1601 if (!av_set_is_in_p (BND_AV1 (bnd), EXPR_VINSN (expr)))
1602 continue;
1604 /* Put in ORIG_OPS all exprs from this boundary that became
1605 RES on top. */
1606 orig_ops = find_sequential_best_exprs (bnd, expr, false);
1608 /* Compute used regs and OR it into the USED_REGS. */
1609 res = find_used_regs (BND_TO (bnd), orig_ops, used_regs,
1610 reg_rename_p, original_insns);
1612 /* FIXME: the assert is true until we'd have several boundaries. */
1613 gcc_assert (res);
1614 av_set_clear (&orig_ops);
1618 /* Return TRUE if it is possible to replace LHSes of ORIG_INSNS with BEST_REG.
1619 If BEST_REG is valid, replace LHS of EXPR with it. */
1620 static bool
1621 try_replace_dest_reg (ilist_t orig_insns, rtx best_reg, expr_t expr)
1623 /* Try whether we'll be able to generate the insn
1624 'dest := best_reg' at the place of the original operation. */
1625 for (; orig_insns; orig_insns = ILIST_NEXT (orig_insns))
1627 insn_t orig_insn = DEF_LIST_DEF (orig_insns)->orig_insn;
1629 gcc_assert (EXPR_SEPARABLE_P (INSN_EXPR (orig_insn)));
1631 if (REGNO (best_reg) != REGNO (INSN_LHS (orig_insn))
1632 && (! replace_src_with_reg_ok_p (orig_insn, best_reg)
1633 || ! replace_dest_with_reg_ok_p (orig_insn, best_reg)))
1634 return false;
1637 /* Make sure that EXPR has the right destination
1638 register. */
1639 if (expr_dest_regno (expr) != REGNO (best_reg))
1640 replace_dest_with_reg_in_expr (expr, best_reg);
1641 else
1642 EXPR_TARGET_AVAILABLE (expr) = 1;
1644 return true;
1647 /* Select and assign best register to EXPR searching from BNDS.
1648 Set *IS_ORIG_REG_P to TRUE if original register was selected.
1649 Return FALSE if no register can be chosen, which could happen when:
1650 * EXPR_SEPARABLE_P is true but we were unable to find suitable register;
1651 * EXPR_SEPARABLE_P is false but the insn sets/clobbers one of the registers
1652 that are used on the moving path. */
1653 static bool
1654 find_best_reg_for_expr (expr_t expr, blist_t bnds, bool *is_orig_reg_p)
1656 static struct reg_rename reg_rename_data;
1658 regset used_regs;
1659 def_list_t original_insns = NULL;
1660 bool reg_ok;
1662 *is_orig_reg_p = false;
1664 /* Don't bother to do anything if this insn doesn't set any registers. */
1665 if (bitmap_empty_p (VINSN_REG_SETS (EXPR_VINSN (expr)))
1666 && bitmap_empty_p (VINSN_REG_CLOBBERS (EXPR_VINSN (expr))))
1667 return true;
1669 used_regs = get_clear_regset_from_pool ();
1670 CLEAR_HARD_REG_SET (reg_rename_data.unavailable_hard_regs);
1672 collect_unavailable_regs_from_bnds (expr, bnds, used_regs, &reg_rename_data,
1673 &original_insns);
1675 #ifdef ENABLE_CHECKING
1676 /* If after reload, make sure we're working with hard regs here. */
1677 if (reload_completed)
1679 reg_set_iterator rsi;
1680 unsigned i;
1682 EXECUTE_IF_SET_IN_REG_SET (used_regs, FIRST_PSEUDO_REGISTER, i, rsi)
1683 gcc_unreachable ();
1685 #endif
1687 if (EXPR_SEPARABLE_P (expr))
1689 rtx best_reg = NULL_RTX;
1690 /* Check that we have computed availability of a target register
1691 correctly. */
1692 verify_target_availability (expr, used_regs, &reg_rename_data);
1694 /* Turn everything in hard regs after reload. */
1695 if (reload_completed)
1697 HARD_REG_SET hard_regs_used;
1698 REG_SET_TO_HARD_REG_SET (hard_regs_used, used_regs);
1700 /* Join hard registers unavailable due to register class
1701 restrictions and live range intersection. */
1702 IOR_HARD_REG_SET (hard_regs_used,
1703 reg_rename_data.unavailable_hard_regs);
1705 best_reg = choose_best_reg (hard_regs_used, &reg_rename_data,
1706 original_insns, is_orig_reg_p);
1708 else
1709 best_reg = choose_best_pseudo_reg (used_regs, &reg_rename_data,
1710 original_insns, is_orig_reg_p);
1712 if (!best_reg)
1713 reg_ok = false;
1714 else if (*is_orig_reg_p)
1716 /* In case of unification BEST_REG may be different from EXPR's LHS
1717 when EXPR's LHS is unavailable, and there is another LHS among
1718 ORIGINAL_INSNS. */
1719 reg_ok = try_replace_dest_reg (original_insns, best_reg, expr);
1721 else
1723 /* Forbid renaming of low-cost insns. */
1724 if (sel_vinsn_cost (EXPR_VINSN (expr)) < 2)
1725 reg_ok = false;
1726 else
1727 reg_ok = try_replace_dest_reg (original_insns, best_reg, expr);
1730 else
1732 /* If !EXPR_SCHEDULE_AS_RHS (EXPR), just make sure INSN doesn't set
1733 any of the HARD_REGS_USED set. */
1734 if (vinsn_writes_one_of_regs_p (EXPR_VINSN (expr), used_regs,
1735 reg_rename_data.unavailable_hard_regs))
1737 reg_ok = false;
1738 gcc_assert (EXPR_TARGET_AVAILABLE (expr) <= 0);
1740 else
1742 reg_ok = true;
1743 gcc_assert (EXPR_TARGET_AVAILABLE (expr) != 0);
1747 ilist_clear (&original_insns);
1748 return_regset_to_pool (used_regs);
1750 return reg_ok;
1754 /* Return true if dependence described by DS can be overcomed. */
1755 static bool
1756 can_speculate_dep_p (ds_t ds)
1758 if (spec_info == NULL)
1759 return false;
1761 /* Leave only speculative data. */
1762 ds &= SPECULATIVE;
1764 if (ds == 0)
1765 return false;
1768 /* FIXME: make sched-deps.c produce only those non-hard dependencies,
1769 that we can overcome. */
1770 ds_t spec_mask = spec_info->mask;
1772 if ((ds & spec_mask) != ds)
1773 return false;
1776 if (ds_weak (ds) < spec_info->data_weakness_cutoff)
1777 return false;
1779 return true;
1782 /* Get a speculation check instruction.
1783 C_EXPR is a speculative expression,
1784 CHECK_DS describes speculations that should be checked,
1785 ORIG_INSN is the original non-speculative insn in the stream. */
1786 static insn_t
1787 create_speculation_check (expr_t c_expr, ds_t check_ds, insn_t orig_insn)
1789 rtx check_pattern;
1790 rtx_insn *insn_rtx;
1791 insn_t insn;
1792 basic_block recovery_block;
1793 rtx_insn *label;
1795 /* Create a recovery block if target is going to emit branchy check, or if
1796 ORIG_INSN was speculative already. */
1797 if (targetm.sched.needs_block_p (check_ds)
1798 || EXPR_SPEC_DONE_DS (INSN_EXPR (orig_insn)) != 0)
1800 recovery_block = sel_create_recovery_block (orig_insn);
1801 label = BB_HEAD (recovery_block);
1803 else
1805 recovery_block = NULL;
1806 label = NULL;
1809 /* Get pattern of the check. */
1810 check_pattern = targetm.sched.gen_spec_check (EXPR_INSN_RTX (c_expr), label,
1811 check_ds);
1813 gcc_assert (check_pattern != NULL);
1815 /* Emit check. */
1816 insn_rtx = create_insn_rtx_from_pattern (check_pattern, label);
1818 insn = sel_gen_insn_from_rtx_after (insn_rtx, INSN_EXPR (orig_insn),
1819 INSN_SEQNO (orig_insn), orig_insn);
1821 /* Make check to be non-speculative. */
1822 EXPR_SPEC_DONE_DS (INSN_EXPR (insn)) = 0;
1823 INSN_SPEC_CHECKED_DS (insn) = check_ds;
1825 /* Decrease priority of check by difference of load/check instruction
1826 latencies. */
1827 EXPR_PRIORITY (INSN_EXPR (insn)) -= (sel_vinsn_cost (INSN_VINSN (orig_insn))
1828 - sel_vinsn_cost (INSN_VINSN (insn)));
1830 /* Emit copy of original insn (though with replaced target register,
1831 if needed) to the recovery block. */
1832 if (recovery_block != NULL)
1834 rtx twin_rtx;
1836 twin_rtx = copy_rtx (PATTERN (EXPR_INSN_RTX (c_expr)));
1837 twin_rtx = create_insn_rtx_from_pattern (twin_rtx, NULL_RTX);
1838 sel_gen_recovery_insn_from_rtx_after (twin_rtx,
1839 INSN_EXPR (orig_insn),
1840 INSN_SEQNO (insn),
1841 bb_note (recovery_block));
1844 /* If we've generated a data speculation check, make sure
1845 that all the bookkeeping instruction we'll create during
1846 this move_op () will allocate an ALAT entry so that the
1847 check won't fail.
1848 In case of control speculation we must convert C_EXPR to control
1849 speculative mode, because failing to do so will bring us an exception
1850 thrown by the non-control-speculative load. */
1851 check_ds = ds_get_max_dep_weak (check_ds);
1852 speculate_expr (c_expr, check_ds);
1854 return insn;
1857 /* True when INSN is a "regN = regN" copy. */
1858 static bool
1859 identical_copy_p (rtx insn)
1861 rtx lhs, rhs, pat;
1863 pat = PATTERN (insn);
1865 if (GET_CODE (pat) != SET)
1866 return false;
1868 lhs = SET_DEST (pat);
1869 if (!REG_P (lhs))
1870 return false;
1872 rhs = SET_SRC (pat);
1873 if (!REG_P (rhs))
1874 return false;
1876 return REGNO (lhs) == REGNO (rhs);
1879 /* Undo all transformations on *AV_PTR that were done when
1880 moving through INSN. */
1881 static void
1882 undo_transformations (av_set_t *av_ptr, rtx_insn *insn)
1884 av_set_iterator av_iter;
1885 expr_t expr;
1886 av_set_t new_set = NULL;
1888 /* First, kill any EXPR that uses registers set by an insn. This is
1889 required for correctness. */
1890 FOR_EACH_EXPR_1 (expr, av_iter, av_ptr)
1891 if (!sched_insns_conditions_mutex_p (insn, EXPR_INSN_RTX (expr))
1892 && bitmap_intersect_p (INSN_REG_SETS (insn),
1893 VINSN_REG_USES (EXPR_VINSN (expr)))
1894 /* When an insn looks like 'r1 = r1', we could substitute through
1895 it, but the above condition will still hold. This happened with
1896 gcc.c-torture/execute/961125-1.c. */
1897 && !identical_copy_p (insn))
1899 if (sched_verbose >= 6)
1900 sel_print ("Expr %d removed due to use/set conflict\n",
1901 INSN_UID (EXPR_INSN_RTX (expr)));
1902 av_set_iter_remove (&av_iter);
1905 /* Undo transformations looking at the history vector. */
1906 FOR_EACH_EXPR (expr, av_iter, *av_ptr)
1908 int index = find_in_history_vect (EXPR_HISTORY_OF_CHANGES (expr),
1909 insn, EXPR_VINSN (expr), true);
1911 if (index >= 0)
1913 expr_history_def *phist;
1915 phist = &EXPR_HISTORY_OF_CHANGES (expr)[index];
1917 switch (phist->type)
1919 case TRANS_SPECULATION:
1921 ds_t old_ds, new_ds;
1923 /* Compute the difference between old and new speculative
1924 statuses: that's what we need to check.
1925 Earlier we used to assert that the status will really
1926 change. This no longer works because only the probability
1927 bits in the status may have changed during compute_av_set,
1928 and in the case of merging different probabilities of the
1929 same speculative status along different paths we do not
1930 record this in the history vector. */
1931 old_ds = phist->spec_ds;
1932 new_ds = EXPR_SPEC_DONE_DS (expr);
1934 old_ds &= SPECULATIVE;
1935 new_ds &= SPECULATIVE;
1936 new_ds &= ~old_ds;
1938 EXPR_SPEC_TO_CHECK_DS (expr) |= new_ds;
1939 break;
1941 case TRANS_SUBSTITUTION:
1943 expr_def _tmp_expr, *tmp_expr = &_tmp_expr;
1944 vinsn_t new_vi;
1945 bool add = true;
1947 new_vi = phist->old_expr_vinsn;
1949 gcc_assert (VINSN_SEPARABLE_P (new_vi)
1950 == EXPR_SEPARABLE_P (expr));
1951 copy_expr (tmp_expr, expr);
1953 if (vinsn_equal_p (phist->new_expr_vinsn,
1954 EXPR_VINSN (tmp_expr)))
1955 change_vinsn_in_expr (tmp_expr, new_vi);
1956 else
1957 /* This happens when we're unsubstituting on a bookkeeping
1958 copy, which was in turn substituted. The history is wrong
1959 in this case. Do it the hard way. */
1960 add = substitute_reg_in_expr (tmp_expr, insn, true);
1961 if (add)
1962 av_set_add (&new_set, tmp_expr);
1963 clear_expr (tmp_expr);
1964 break;
1966 default:
1967 gcc_unreachable ();
1973 av_set_union_and_clear (av_ptr, &new_set, NULL);
1977 /* Moveup_* helpers for code motion and computing av sets. */
1979 /* Propagates EXPR inside an insn group through THROUGH_INSN.
1980 The difference from the below function is that only substitution is
1981 performed. */
1982 static enum MOVEUP_EXPR_CODE
1983 moveup_expr_inside_insn_group (expr_t expr, insn_t through_insn)
1985 vinsn_t vi = EXPR_VINSN (expr);
1986 ds_t *has_dep_p;
1987 ds_t full_ds;
1989 /* Do this only inside insn group. */
1990 gcc_assert (INSN_SCHED_CYCLE (through_insn) > 0);
1992 full_ds = has_dependence_p (expr, through_insn, &has_dep_p);
1993 if (full_ds == 0)
1994 return MOVEUP_EXPR_SAME;
1996 /* Substitution is the possible choice in this case. */
1997 if (has_dep_p[DEPS_IN_RHS])
1999 /* Can't substitute UNIQUE VINSNs. */
2000 gcc_assert (!VINSN_UNIQUE_P (vi));
2002 if (can_substitute_through_p (through_insn,
2003 has_dep_p[DEPS_IN_RHS])
2004 && substitute_reg_in_expr (expr, through_insn, false))
2006 EXPR_WAS_SUBSTITUTED (expr) = true;
2007 return MOVEUP_EXPR_CHANGED;
2010 /* Don't care about this, as even true dependencies may be allowed
2011 in an insn group. */
2012 return MOVEUP_EXPR_SAME;
2015 /* This can catch output dependencies in COND_EXECs. */
2016 if (has_dep_p[DEPS_IN_INSN])
2017 return MOVEUP_EXPR_NULL;
2019 /* This is either an output or an anti dependence, which usually have
2020 a zero latency. Allow this here, if we'd be wrong, tick_check_p
2021 will fix this. */
2022 gcc_assert (has_dep_p[DEPS_IN_LHS]);
2023 return MOVEUP_EXPR_AS_RHS;
2026 /* True when a trapping EXPR cannot be moved through THROUGH_INSN. */
2027 #define CANT_MOVE_TRAPPING(expr, through_insn) \
2028 (VINSN_MAY_TRAP_P (EXPR_VINSN (expr)) \
2029 && !sel_insn_has_single_succ_p ((through_insn), SUCCS_ALL) \
2030 && !sel_insn_is_speculation_check (through_insn))
2032 /* True when a conflict on a target register was found during moveup_expr. */
2033 static bool was_target_conflict = false;
2035 /* Return true when moving a debug INSN across THROUGH_INSN will
2036 create a bookkeeping block. We don't want to create such blocks,
2037 for they would cause codegen differences between compilations with
2038 and without debug info. */
2040 static bool
2041 moving_insn_creates_bookkeeping_block_p (insn_t insn,
2042 insn_t through_insn)
2044 basic_block bbi, bbt;
2045 edge e1, e2;
2046 edge_iterator ei1, ei2;
2048 if (!bookkeeping_can_be_created_if_moved_through_p (through_insn))
2050 if (sched_verbose >= 9)
2051 sel_print ("no bookkeeping required: ");
2052 return FALSE;
2055 bbi = BLOCK_FOR_INSN (insn);
2057 if (EDGE_COUNT (bbi->preds) == 1)
2059 if (sched_verbose >= 9)
2060 sel_print ("only one pred edge: ");
2061 return TRUE;
2064 bbt = BLOCK_FOR_INSN (through_insn);
2066 FOR_EACH_EDGE (e1, ei1, bbt->succs)
2068 FOR_EACH_EDGE (e2, ei2, bbi->preds)
2070 if (find_block_for_bookkeeping (e1, e2, TRUE))
2072 if (sched_verbose >= 9)
2073 sel_print ("found existing block: ");
2074 return FALSE;
2079 if (sched_verbose >= 9)
2080 sel_print ("would create bookkeeping block: ");
2082 return TRUE;
2085 /* Return true when the conflict with newly created implicit clobbers
2086 between EXPR and THROUGH_INSN is found because of renaming. */
2087 static bool
2088 implicit_clobber_conflict_p (insn_t through_insn, expr_t expr)
2090 HARD_REG_SET temp;
2091 rtx_insn *insn;
2092 rtx reg, rhs, pat;
2093 hard_reg_set_iterator hrsi;
2094 unsigned regno;
2095 bool valid;
2097 /* Make a new pseudo register. */
2098 reg = gen_reg_rtx (GET_MODE (EXPR_LHS (expr)));
2099 max_regno = max_reg_num ();
2100 maybe_extend_reg_info_p ();
2102 /* Validate a change and bail out early. */
2103 insn = EXPR_INSN_RTX (expr);
2104 validate_change (insn, &SET_DEST (PATTERN (insn)), reg, true);
2105 valid = verify_changes (0);
2106 cancel_changes (0);
2107 if (!valid)
2109 if (sched_verbose >= 6)
2110 sel_print ("implicit clobbers failed validation, ");
2111 return true;
2114 /* Make a new insn with it. */
2115 rhs = copy_rtx (VINSN_RHS (EXPR_VINSN (expr)));
2116 pat = gen_rtx_SET (VOIDmode, reg, rhs);
2117 start_sequence ();
2118 insn = emit_insn (pat);
2119 end_sequence ();
2121 /* Calculate implicit clobbers. */
2122 extract_insn (insn);
2123 preprocess_constraints (insn);
2124 ira_implicitly_set_insn_hard_regs (&temp);
2125 AND_COMPL_HARD_REG_SET (temp, ira_no_alloc_regs);
2127 /* If any implicit clobber registers intersect with regular ones in
2128 through_insn, we have a dependency and thus bail out. */
2129 EXECUTE_IF_SET_IN_HARD_REG_SET (temp, 0, regno, hrsi)
2131 vinsn_t vi = INSN_VINSN (through_insn);
2132 if (bitmap_bit_p (VINSN_REG_SETS (vi), regno)
2133 || bitmap_bit_p (VINSN_REG_CLOBBERS (vi), regno)
2134 || bitmap_bit_p (VINSN_REG_USES (vi), regno))
2135 return true;
2138 return false;
2141 /* Modifies EXPR so it can be moved through the THROUGH_INSN,
2142 performing necessary transformations. Record the type of transformation
2143 made in PTRANS_TYPE, when it is not NULL. When INSIDE_INSN_GROUP,
2144 permit all dependencies except true ones, and try to remove those
2145 too via forward substitution. All cases when a non-eliminable
2146 non-zero cost dependency exists inside an insn group will be fixed
2147 in tick_check_p instead. */
2148 static enum MOVEUP_EXPR_CODE
2149 moveup_expr (expr_t expr, insn_t through_insn, bool inside_insn_group,
2150 enum local_trans_type *ptrans_type)
2152 vinsn_t vi = EXPR_VINSN (expr);
2153 insn_t insn = VINSN_INSN_RTX (vi);
2154 bool was_changed = false;
2155 bool as_rhs = false;
2156 ds_t *has_dep_p;
2157 ds_t full_ds;
2159 /* ??? We use dependencies of non-debug insns on debug insns to
2160 indicate that the debug insns need to be reset if the non-debug
2161 insn is pulled ahead of it. It's hard to figure out how to
2162 introduce such a notion in sel-sched, but it already fails to
2163 support debug insns in other ways, so we just go ahead and
2164 let the deug insns go corrupt for now. */
2165 if (DEBUG_INSN_P (through_insn) && !DEBUG_INSN_P (insn))
2166 return MOVEUP_EXPR_SAME;
2168 /* When inside_insn_group, delegate to the helper. */
2169 if (inside_insn_group)
2170 return moveup_expr_inside_insn_group (expr, through_insn);
2172 /* Deal with unique insns and control dependencies. */
2173 if (VINSN_UNIQUE_P (vi))
2175 /* We can move jumps without side-effects or jumps that are
2176 mutually exclusive with instruction THROUGH_INSN (all in cases
2177 dependencies allow to do so and jump is not speculative). */
2178 if (control_flow_insn_p (insn))
2180 basic_block fallthru_bb;
2182 /* Do not move checks and do not move jumps through other
2183 jumps. */
2184 if (control_flow_insn_p (through_insn)
2185 || sel_insn_is_speculation_check (insn))
2186 return MOVEUP_EXPR_NULL;
2188 /* Don't move jumps through CFG joins. */
2189 if (bookkeeping_can_be_created_if_moved_through_p (through_insn))
2190 return MOVEUP_EXPR_NULL;
2192 /* The jump should have a clear fallthru block, and
2193 this block should be in the current region. */
2194 if ((fallthru_bb = fallthru_bb_of_jump (insn)) == NULL
2195 || ! in_current_region_p (fallthru_bb))
2196 return MOVEUP_EXPR_NULL;
2198 /* And it should be mutually exclusive with through_insn. */
2199 if (! sched_insns_conditions_mutex_p (insn, through_insn)
2200 && ! DEBUG_INSN_P (through_insn))
2201 return MOVEUP_EXPR_NULL;
2204 /* Don't move what we can't move. */
2205 if (EXPR_CANT_MOVE (expr)
2206 && BLOCK_FOR_INSN (through_insn) != BLOCK_FOR_INSN (insn))
2207 return MOVEUP_EXPR_NULL;
2209 /* Don't move SCHED_GROUP instruction through anything.
2210 If we don't force this, then it will be possible to start
2211 scheduling a sched_group before all its dependencies are
2212 resolved.
2213 ??? Haifa deals with this issue by delaying the SCHED_GROUP
2214 as late as possible through rank_for_schedule. */
2215 if (SCHED_GROUP_P (insn))
2216 return MOVEUP_EXPR_NULL;
2218 else
2219 gcc_assert (!control_flow_insn_p (insn));
2221 /* Don't move debug insns if this would require bookkeeping. */
2222 if (DEBUG_INSN_P (insn)
2223 && BLOCK_FOR_INSN (through_insn) != BLOCK_FOR_INSN (insn)
2224 && moving_insn_creates_bookkeeping_block_p (insn, through_insn))
2225 return MOVEUP_EXPR_NULL;
2227 /* Deal with data dependencies. */
2228 was_target_conflict = false;
2229 full_ds = has_dependence_p (expr, through_insn, &has_dep_p);
2230 if (full_ds == 0)
2232 if (!CANT_MOVE_TRAPPING (expr, through_insn))
2233 return MOVEUP_EXPR_SAME;
2235 else
2237 /* We can move UNIQUE insn up only as a whole and unchanged,
2238 so it shouldn't have any dependencies. */
2239 if (VINSN_UNIQUE_P (vi))
2240 return MOVEUP_EXPR_NULL;
2243 if (full_ds != 0 && can_speculate_dep_p (full_ds))
2245 int res;
2247 res = speculate_expr (expr, full_ds);
2248 if (res >= 0)
2250 /* Speculation was successful. */
2251 full_ds = 0;
2252 was_changed = (res > 0);
2253 if (res == 2)
2254 was_target_conflict = true;
2255 if (ptrans_type)
2256 *ptrans_type = TRANS_SPECULATION;
2257 sel_clear_has_dependence ();
2261 if (has_dep_p[DEPS_IN_INSN])
2262 /* We have some dependency that cannot be discarded. */
2263 return MOVEUP_EXPR_NULL;
2265 if (has_dep_p[DEPS_IN_LHS])
2267 /* Only separable insns can be moved up with the new register.
2268 Anyways, we should mark that the original register is
2269 unavailable. */
2270 if (!enable_schedule_as_rhs_p || !EXPR_SEPARABLE_P (expr))
2271 return MOVEUP_EXPR_NULL;
2273 /* When renaming a hard register to a pseudo before reload, extra
2274 dependencies can occur from the implicit clobbers of the insn.
2275 Filter out such cases here. */
2276 if (!reload_completed && REG_P (EXPR_LHS (expr))
2277 && HARD_REGISTER_P (EXPR_LHS (expr))
2278 && implicit_clobber_conflict_p (through_insn, expr))
2280 if (sched_verbose >= 6)
2281 sel_print ("implicit clobbers conflict detected, ");
2282 return MOVEUP_EXPR_NULL;
2284 EXPR_TARGET_AVAILABLE (expr) = false;
2285 was_target_conflict = true;
2286 as_rhs = true;
2289 /* At this point we have either separable insns, that will be lifted
2290 up only as RHSes, or non-separable insns with no dependency in lhs.
2291 If dependency is in RHS, then try to perform substitution and move up
2292 substituted RHS:
2294 Ex. 1: Ex.2
2295 y = x; y = x;
2296 z = y*2; y = y*2;
2298 In Ex.1 y*2 can be substituted for x*2 and the whole operation can be
2299 moved above y=x assignment as z=x*2.
2301 In Ex.2 y*2 also can be substituted for x*2, but only the right hand
2302 side can be moved because of the output dependency. The operation was
2303 cropped to its rhs above. */
2304 if (has_dep_p[DEPS_IN_RHS])
2306 ds_t *rhs_dsp = &has_dep_p[DEPS_IN_RHS];
2308 /* Can't substitute UNIQUE VINSNs. */
2309 gcc_assert (!VINSN_UNIQUE_P (vi));
2311 if (can_speculate_dep_p (*rhs_dsp))
2313 int res;
2315 res = speculate_expr (expr, *rhs_dsp);
2316 if (res >= 0)
2318 /* Speculation was successful. */
2319 *rhs_dsp = 0;
2320 was_changed = (res > 0);
2321 if (res == 2)
2322 was_target_conflict = true;
2323 if (ptrans_type)
2324 *ptrans_type = TRANS_SPECULATION;
2326 else
2327 return MOVEUP_EXPR_NULL;
2329 else if (can_substitute_through_p (through_insn,
2330 *rhs_dsp)
2331 && substitute_reg_in_expr (expr, through_insn, false))
2333 /* ??? We cannot perform substitution AND speculation on the same
2334 insn. */
2335 gcc_assert (!was_changed);
2336 was_changed = true;
2337 if (ptrans_type)
2338 *ptrans_type = TRANS_SUBSTITUTION;
2339 EXPR_WAS_SUBSTITUTED (expr) = true;
2341 else
2342 return MOVEUP_EXPR_NULL;
2345 /* Don't move trapping insns through jumps.
2346 This check should be at the end to give a chance to control speculation
2347 to perform its duties. */
2348 if (CANT_MOVE_TRAPPING (expr, through_insn))
2349 return MOVEUP_EXPR_NULL;
2351 return (was_changed
2352 ? MOVEUP_EXPR_CHANGED
2353 : (as_rhs
2354 ? MOVEUP_EXPR_AS_RHS
2355 : MOVEUP_EXPR_SAME));
2358 /* Try to look at bitmap caches for EXPR and INSN pair, return true
2359 if successful. When INSIDE_INSN_GROUP, also try ignore dependencies
2360 that can exist within a parallel group. Write to RES the resulting
2361 code for moveup_expr. */
2362 static bool
2363 try_bitmap_cache (expr_t expr, insn_t insn,
2364 bool inside_insn_group,
2365 enum MOVEUP_EXPR_CODE *res)
2367 int expr_uid = INSN_UID (EXPR_INSN_RTX (expr));
2369 /* First check whether we've analyzed this situation already. */
2370 if (bitmap_bit_p (INSN_ANALYZED_DEPS (insn), expr_uid))
2372 if (bitmap_bit_p (INSN_FOUND_DEPS (insn), expr_uid))
2374 if (sched_verbose >= 6)
2375 sel_print ("removed (cached)\n");
2376 *res = MOVEUP_EXPR_NULL;
2377 return true;
2379 else
2381 if (sched_verbose >= 6)
2382 sel_print ("unchanged (cached)\n");
2383 *res = MOVEUP_EXPR_SAME;
2384 return true;
2387 else if (bitmap_bit_p (INSN_FOUND_DEPS (insn), expr_uid))
2389 if (inside_insn_group)
2391 if (sched_verbose >= 6)
2392 sel_print ("unchanged (as RHS, cached, inside insn group)\n");
2393 *res = MOVEUP_EXPR_SAME;
2394 return true;
2397 else
2398 EXPR_TARGET_AVAILABLE (expr) = false;
2400 /* This is the only case when propagation result can change over time,
2401 as we can dynamically switch off scheduling as RHS. In this case,
2402 just check the flag to reach the correct decision. */
2403 if (enable_schedule_as_rhs_p)
2405 if (sched_verbose >= 6)
2406 sel_print ("unchanged (as RHS, cached)\n");
2407 *res = MOVEUP_EXPR_AS_RHS;
2408 return true;
2410 else
2412 if (sched_verbose >= 6)
2413 sel_print ("removed (cached as RHS, but renaming"
2414 " is now disabled)\n");
2415 *res = MOVEUP_EXPR_NULL;
2416 return true;
2420 return false;
2423 /* Try to look at bitmap caches for EXPR and INSN pair, return true
2424 if successful. Write to RES the resulting code for moveup_expr. */
2425 static bool
2426 try_transformation_cache (expr_t expr, insn_t insn,
2427 enum MOVEUP_EXPR_CODE *res)
2429 struct transformed_insns *pti
2430 = (struct transformed_insns *)
2431 htab_find_with_hash (INSN_TRANSFORMED_INSNS (insn),
2432 &EXPR_VINSN (expr),
2433 VINSN_HASH_RTX (EXPR_VINSN (expr)));
2434 if (pti)
2436 /* This EXPR was already moved through this insn and was
2437 changed as a result. Fetch the proper data from
2438 the hashtable. */
2439 insert_in_history_vect (&EXPR_HISTORY_OF_CHANGES (expr),
2440 INSN_UID (insn), pti->type,
2441 pti->vinsn_old, pti->vinsn_new,
2442 EXPR_SPEC_DONE_DS (expr));
2444 if (INSN_IN_STREAM_P (VINSN_INSN_RTX (pti->vinsn_new)))
2445 pti->vinsn_new = vinsn_copy (pti->vinsn_new, true);
2446 change_vinsn_in_expr (expr, pti->vinsn_new);
2447 if (pti->was_target_conflict)
2448 EXPR_TARGET_AVAILABLE (expr) = false;
2449 if (pti->type == TRANS_SPECULATION)
2451 EXPR_SPEC_DONE_DS (expr) = pti->ds;
2452 EXPR_NEEDS_SPEC_CHECK_P (expr) |= pti->needs_check;
2455 if (sched_verbose >= 6)
2457 sel_print ("changed (cached): ");
2458 dump_expr (expr);
2459 sel_print ("\n");
2462 *res = MOVEUP_EXPR_CHANGED;
2463 return true;
2466 return false;
2469 /* Update bitmap caches on INSN with result RES of propagating EXPR. */
2470 static void
2471 update_bitmap_cache (expr_t expr, insn_t insn, bool inside_insn_group,
2472 enum MOVEUP_EXPR_CODE res)
2474 int expr_uid = INSN_UID (EXPR_INSN_RTX (expr));
2476 /* Do not cache result of propagating jumps through an insn group,
2477 as it is always true, which is not useful outside the group. */
2478 if (inside_insn_group)
2479 return;
2481 if (res == MOVEUP_EXPR_NULL)
2483 bitmap_set_bit (INSN_ANALYZED_DEPS (insn), expr_uid);
2484 bitmap_set_bit (INSN_FOUND_DEPS (insn), expr_uid);
2486 else if (res == MOVEUP_EXPR_SAME)
2488 bitmap_set_bit (INSN_ANALYZED_DEPS (insn), expr_uid);
2489 bitmap_clear_bit (INSN_FOUND_DEPS (insn), expr_uid);
2491 else if (res == MOVEUP_EXPR_AS_RHS)
2493 bitmap_clear_bit (INSN_ANALYZED_DEPS (insn), expr_uid);
2494 bitmap_set_bit (INSN_FOUND_DEPS (insn), expr_uid);
2496 else
2497 gcc_unreachable ();
2500 /* Update hashtable on INSN with changed EXPR, old EXPR_OLD_VINSN
2501 and transformation type TRANS_TYPE. */
2502 static void
2503 update_transformation_cache (expr_t expr, insn_t insn,
2504 bool inside_insn_group,
2505 enum local_trans_type trans_type,
2506 vinsn_t expr_old_vinsn)
2508 struct transformed_insns *pti;
2510 if (inside_insn_group)
2511 return;
2513 pti = XNEW (struct transformed_insns);
2514 pti->vinsn_old = expr_old_vinsn;
2515 pti->vinsn_new = EXPR_VINSN (expr);
2516 pti->type = trans_type;
2517 pti->was_target_conflict = was_target_conflict;
2518 pti->ds = EXPR_SPEC_DONE_DS (expr);
2519 pti->needs_check = EXPR_NEEDS_SPEC_CHECK_P (expr);
2520 vinsn_attach (pti->vinsn_old);
2521 vinsn_attach (pti->vinsn_new);
2522 *((struct transformed_insns **)
2523 htab_find_slot_with_hash (INSN_TRANSFORMED_INSNS (insn),
2524 pti, VINSN_HASH_RTX (expr_old_vinsn),
2525 INSERT)) = pti;
2528 /* Same as moveup_expr, but first looks up the result of
2529 transformation in caches. */
2530 static enum MOVEUP_EXPR_CODE
2531 moveup_expr_cached (expr_t expr, insn_t insn, bool inside_insn_group)
2533 enum MOVEUP_EXPR_CODE res;
2534 bool got_answer = false;
2536 if (sched_verbose >= 6)
2538 sel_print ("Moving ");
2539 dump_expr (expr);
2540 sel_print (" through %d: ", INSN_UID (insn));
2543 if (DEBUG_INSN_P (EXPR_INSN_RTX (expr))
2544 && (sel_bb_head (BLOCK_FOR_INSN (EXPR_INSN_RTX (expr)))
2545 == EXPR_INSN_RTX (expr)))
2546 /* Don't use cached information for debug insns that are heads of
2547 basic blocks. */;
2548 else if (try_bitmap_cache (expr, insn, inside_insn_group, &res))
2549 /* When inside insn group, we do not want remove stores conflicting
2550 with previosly issued loads. */
2551 got_answer = ! inside_insn_group || res != MOVEUP_EXPR_NULL;
2552 else if (try_transformation_cache (expr, insn, &res))
2553 got_answer = true;
2555 if (! got_answer)
2557 /* Invoke moveup_expr and record the results. */
2558 vinsn_t expr_old_vinsn = EXPR_VINSN (expr);
2559 ds_t expr_old_spec_ds = EXPR_SPEC_DONE_DS (expr);
2560 int expr_uid = INSN_UID (VINSN_INSN_RTX (expr_old_vinsn));
2561 bool unique_p = VINSN_UNIQUE_P (expr_old_vinsn);
2562 enum local_trans_type trans_type = TRANS_SUBSTITUTION;
2564 /* ??? Invent something better than this. We can't allow old_vinsn
2565 to go, we need it for the history vector. */
2566 vinsn_attach (expr_old_vinsn);
2568 res = moveup_expr (expr, insn, inside_insn_group,
2569 &trans_type);
2570 switch (res)
2572 case MOVEUP_EXPR_NULL:
2573 update_bitmap_cache (expr, insn, inside_insn_group, res);
2574 if (sched_verbose >= 6)
2575 sel_print ("removed\n");
2576 break;
2578 case MOVEUP_EXPR_SAME:
2579 update_bitmap_cache (expr, insn, inside_insn_group, res);
2580 if (sched_verbose >= 6)
2581 sel_print ("unchanged\n");
2582 break;
2584 case MOVEUP_EXPR_AS_RHS:
2585 gcc_assert (!unique_p || inside_insn_group);
2586 update_bitmap_cache (expr, insn, inside_insn_group, res);
2587 if (sched_verbose >= 6)
2588 sel_print ("unchanged (as RHS)\n");
2589 break;
2591 case MOVEUP_EXPR_CHANGED:
2592 gcc_assert (INSN_UID (EXPR_INSN_RTX (expr)) != expr_uid
2593 || EXPR_SPEC_DONE_DS (expr) != expr_old_spec_ds);
2594 insert_in_history_vect (&EXPR_HISTORY_OF_CHANGES (expr),
2595 INSN_UID (insn), trans_type,
2596 expr_old_vinsn, EXPR_VINSN (expr),
2597 expr_old_spec_ds);
2598 update_transformation_cache (expr, insn, inside_insn_group,
2599 trans_type, expr_old_vinsn);
2600 if (sched_verbose >= 6)
2602 sel_print ("changed: ");
2603 dump_expr (expr);
2604 sel_print ("\n");
2606 break;
2607 default:
2608 gcc_unreachable ();
2611 vinsn_detach (expr_old_vinsn);
2614 return res;
2617 /* Moves an av set AVP up through INSN, performing necessary
2618 transformations. */
2619 static void
2620 moveup_set_expr (av_set_t *avp, insn_t insn, bool inside_insn_group)
2622 av_set_iterator i;
2623 expr_t expr;
2625 FOR_EACH_EXPR_1 (expr, i, avp)
2628 switch (moveup_expr_cached (expr, insn, inside_insn_group))
2630 case MOVEUP_EXPR_SAME:
2631 case MOVEUP_EXPR_AS_RHS:
2632 break;
2634 case MOVEUP_EXPR_NULL:
2635 av_set_iter_remove (&i);
2636 break;
2638 case MOVEUP_EXPR_CHANGED:
2639 expr = merge_with_other_exprs (avp, &i, expr);
2640 break;
2642 default:
2643 gcc_unreachable ();
2648 /* Moves AVP set along PATH. */
2649 static void
2650 moveup_set_inside_insn_group (av_set_t *avp, ilist_t path)
2652 int last_cycle;
2654 if (sched_verbose >= 6)
2655 sel_print ("Moving expressions up in the insn group...\n");
2656 if (! path)
2657 return;
2658 last_cycle = INSN_SCHED_CYCLE (ILIST_INSN (path));
2659 while (path
2660 && INSN_SCHED_CYCLE (ILIST_INSN (path)) == last_cycle)
2662 moveup_set_expr (avp, ILIST_INSN (path), true);
2663 path = ILIST_NEXT (path);
2667 /* Returns true if after moving EXPR along PATH it equals to EXPR_VLIW. */
2668 static bool
2669 equal_after_moveup_path_p (expr_t expr, ilist_t path, expr_t expr_vliw)
2671 expr_def _tmp, *tmp = &_tmp;
2672 int last_cycle;
2673 bool res = true;
2675 copy_expr_onside (tmp, expr);
2676 last_cycle = path ? INSN_SCHED_CYCLE (ILIST_INSN (path)) : 0;
2677 while (path
2678 && res
2679 && INSN_SCHED_CYCLE (ILIST_INSN (path)) == last_cycle)
2681 res = (moveup_expr_cached (tmp, ILIST_INSN (path), true)
2682 != MOVEUP_EXPR_NULL);
2683 path = ILIST_NEXT (path);
2686 if (res)
2688 vinsn_t tmp_vinsn = EXPR_VINSN (tmp);
2689 vinsn_t expr_vliw_vinsn = EXPR_VINSN (expr_vliw);
2691 if (tmp_vinsn != expr_vliw_vinsn)
2692 res = vinsn_equal_p (tmp_vinsn, expr_vliw_vinsn);
2695 clear_expr (tmp);
2696 return res;
2700 /* Functions that compute av and lv sets. */
2702 /* Returns true if INSN is not a downward continuation of the given path P in
2703 the current stage. */
2704 static bool
2705 is_ineligible_successor (insn_t insn, ilist_t p)
2707 insn_t prev_insn;
2709 /* Check if insn is not deleted. */
2710 if (PREV_INSN (insn) && NEXT_INSN (PREV_INSN (insn)) != insn)
2711 gcc_unreachable ();
2712 else if (NEXT_INSN (insn) && PREV_INSN (NEXT_INSN (insn)) != insn)
2713 gcc_unreachable ();
2715 /* If it's the first insn visited, then the successor is ok. */
2716 if (!p)
2717 return false;
2719 prev_insn = ILIST_INSN (p);
2721 if (/* a backward edge. */
2722 INSN_SEQNO (insn) < INSN_SEQNO (prev_insn)
2723 /* is already visited. */
2724 || (INSN_SEQNO (insn) == INSN_SEQNO (prev_insn)
2725 && (ilist_is_in_p (p, insn)
2726 /* We can reach another fence here and still seqno of insn
2727 would be equal to seqno of prev_insn. This is possible
2728 when prev_insn is a previously created bookkeeping copy.
2729 In that case it'd get a seqno of insn. Thus, check here
2730 whether insn is in current fence too. */
2731 || IN_CURRENT_FENCE_P (insn)))
2732 /* Was already scheduled on this round. */
2733 || (INSN_SEQNO (insn) > INSN_SEQNO (prev_insn)
2734 && IN_CURRENT_FENCE_P (insn))
2735 /* An insn from another fence could also be
2736 scheduled earlier even if this insn is not in
2737 a fence list right now. Check INSN_SCHED_CYCLE instead. */
2738 || (!pipelining_p
2739 && INSN_SCHED_TIMES (insn) > 0))
2740 return true;
2741 else
2742 return false;
2745 /* Computes the av_set below the last bb insn INSN, doing all the 'dirty work'
2746 of handling multiple successors and properly merging its av_sets. P is
2747 the current path traversed. WS is the size of lookahead window.
2748 Return the av set computed. */
2749 static av_set_t
2750 compute_av_set_at_bb_end (insn_t insn, ilist_t p, int ws)
2752 struct succs_info *sinfo;
2753 av_set_t expr_in_all_succ_branches = NULL;
2754 int is;
2755 insn_t succ, zero_succ = NULL;
2756 av_set_t av1 = NULL;
2758 gcc_assert (sel_bb_end_p (insn));
2760 /* Find different kind of successors needed for correct computing of
2761 SPEC and TARGET_AVAILABLE attributes. */
2762 sinfo = compute_succs_info (insn, SUCCS_NORMAL);
2764 /* Debug output. */
2765 if (sched_verbose >= 6)
2767 sel_print ("successors of bb end (%d): ", INSN_UID (insn));
2768 dump_insn_vector (sinfo->succs_ok);
2769 sel_print ("\n");
2770 if (sinfo->succs_ok_n != sinfo->all_succs_n)
2771 sel_print ("real successors num: %d\n", sinfo->all_succs_n);
2774 /* Add insn to the tail of current path. */
2775 ilist_add (&p, insn);
2777 FOR_EACH_VEC_ELT (sinfo->succs_ok, is, succ)
2779 av_set_t succ_set;
2781 /* We will edit SUCC_SET and EXPR_SPEC field of its elements. */
2782 succ_set = compute_av_set_inside_bb (succ, p, ws, true);
2784 av_set_split_usefulness (succ_set,
2785 sinfo->probs_ok[is],
2786 sinfo->all_prob);
2788 if (sinfo->all_succs_n > 1)
2790 /* Find EXPR'es that came from *all* successors and save them
2791 into expr_in_all_succ_branches. This set will be used later
2792 for calculating speculation attributes of EXPR'es. */
2793 if (is == 0)
2795 expr_in_all_succ_branches = av_set_copy (succ_set);
2797 /* Remember the first successor for later. */
2798 zero_succ = succ;
2800 else
2802 av_set_iterator i;
2803 expr_t expr;
2805 FOR_EACH_EXPR_1 (expr, i, &expr_in_all_succ_branches)
2806 if (!av_set_is_in_p (succ_set, EXPR_VINSN (expr)))
2807 av_set_iter_remove (&i);
2811 /* Union the av_sets. Check liveness restrictions on target registers
2812 in special case of two successors. */
2813 if (sinfo->succs_ok_n == 2 && is == 1)
2815 basic_block bb0 = BLOCK_FOR_INSN (zero_succ);
2816 basic_block bb1 = BLOCK_FOR_INSN (succ);
2818 gcc_assert (BB_LV_SET_VALID_P (bb0) && BB_LV_SET_VALID_P (bb1));
2819 av_set_union_and_live (&av1, &succ_set,
2820 BB_LV_SET (bb0),
2821 BB_LV_SET (bb1),
2822 insn);
2824 else
2825 av_set_union_and_clear (&av1, &succ_set, insn);
2828 /* Check liveness restrictions via hard way when there are more than
2829 two successors. */
2830 if (sinfo->succs_ok_n > 2)
2831 FOR_EACH_VEC_ELT (sinfo->succs_ok, is, succ)
2833 basic_block succ_bb = BLOCK_FOR_INSN (succ);
2835 gcc_assert (BB_LV_SET_VALID_P (succ_bb));
2836 mark_unavailable_targets (av1, BB_AV_SET (succ_bb),
2837 BB_LV_SET (succ_bb));
2840 /* Finally, check liveness restrictions on paths leaving the region. */
2841 if (sinfo->all_succs_n > sinfo->succs_ok_n)
2842 FOR_EACH_VEC_ELT (sinfo->succs_other, is, succ)
2843 mark_unavailable_targets
2844 (av1, NULL, BB_LV_SET (BLOCK_FOR_INSN (succ)));
2846 if (sinfo->all_succs_n > 1)
2848 av_set_iterator i;
2849 expr_t expr;
2851 /* Increase the spec attribute of all EXPR'es that didn't come
2852 from all successors. */
2853 FOR_EACH_EXPR (expr, i, av1)
2854 if (!av_set_is_in_p (expr_in_all_succ_branches, EXPR_VINSN (expr)))
2855 EXPR_SPEC (expr)++;
2857 av_set_clear (&expr_in_all_succ_branches);
2859 /* Do not move conditional branches through other
2860 conditional branches. So, remove all conditional
2861 branches from av_set if current operator is a conditional
2862 branch. */
2863 av_set_substract_cond_branches (&av1);
2866 ilist_remove (&p);
2867 free_succs_info (sinfo);
2869 if (sched_verbose >= 6)
2871 sel_print ("av_succs (%d): ", INSN_UID (insn));
2872 dump_av_set (av1);
2873 sel_print ("\n");
2876 return av1;
2879 /* This function computes av_set for the FIRST_INSN by dragging valid
2880 av_set through all basic block insns either from the end of basic block
2881 (computed using compute_av_set_at_bb_end) or from the insn on which
2882 MAX_WS was exceeded. It uses compute_av_set_at_bb_end to compute av_set
2883 below the basic block and handling conditional branches.
2884 FIRST_INSN - the basic block head, P - path consisting of the insns
2885 traversed on the way to the FIRST_INSN (the path is sparse, only bb heads
2886 and bb ends are added to the path), WS - current window size,
2887 NEED_COPY_P - true if we'll make a copy of av_set before returning it. */
2888 static av_set_t
2889 compute_av_set_inside_bb (insn_t first_insn, ilist_t p, int ws,
2890 bool need_copy_p)
2892 insn_t cur_insn;
2893 int end_ws = ws;
2894 insn_t bb_end = sel_bb_end (BLOCK_FOR_INSN (first_insn));
2895 insn_t after_bb_end = NEXT_INSN (bb_end);
2896 insn_t last_insn;
2897 av_set_t av = NULL;
2898 basic_block cur_bb = BLOCK_FOR_INSN (first_insn);
2900 /* Return NULL if insn is not on the legitimate downward path. */
2901 if (is_ineligible_successor (first_insn, p))
2903 if (sched_verbose >= 6)
2904 sel_print ("Insn %d is ineligible_successor\n", INSN_UID (first_insn));
2906 return NULL;
2909 /* If insn already has valid av(insn) computed, just return it. */
2910 if (AV_SET_VALID_P (first_insn))
2912 av_set_t av_set;
2914 if (sel_bb_head_p (first_insn))
2915 av_set = BB_AV_SET (BLOCK_FOR_INSN (first_insn));
2916 else
2917 av_set = NULL;
2919 if (sched_verbose >= 6)
2921 sel_print ("Insn %d has a valid av set: ", INSN_UID (first_insn));
2922 dump_av_set (av_set);
2923 sel_print ("\n");
2926 return need_copy_p ? av_set_copy (av_set) : av_set;
2929 ilist_add (&p, first_insn);
2931 /* As the result after this loop have completed, in LAST_INSN we'll
2932 have the insn which has valid av_set to start backward computation
2933 from: it either will be NULL because on it the window size was exceeded
2934 or other valid av_set as returned by compute_av_set for the last insn
2935 of the basic block. */
2936 for (last_insn = first_insn; last_insn != after_bb_end;
2937 last_insn = NEXT_INSN (last_insn))
2939 /* We may encounter valid av_set not only on bb_head, but also on
2940 those insns on which previously MAX_WS was exceeded. */
2941 if (AV_SET_VALID_P (last_insn))
2943 if (sched_verbose >= 6)
2944 sel_print ("Insn %d has a valid empty av set\n", INSN_UID (last_insn));
2945 break;
2948 /* The special case: the last insn of the BB may be an
2949 ineligible_successor due to its SEQ_NO that was set on
2950 it as a bookkeeping. */
2951 if (last_insn != first_insn
2952 && is_ineligible_successor (last_insn, p))
2954 if (sched_verbose >= 6)
2955 sel_print ("Insn %d is ineligible_successor\n", INSN_UID (last_insn));
2956 break;
2959 if (DEBUG_INSN_P (last_insn))
2960 continue;
2962 if (end_ws > max_ws)
2964 /* We can reach max lookahead size at bb_header, so clean av_set
2965 first. */
2966 INSN_WS_LEVEL (last_insn) = global_level;
2968 if (sched_verbose >= 6)
2969 sel_print ("Insn %d is beyond the software lookahead window size\n",
2970 INSN_UID (last_insn));
2971 break;
2974 end_ws++;
2977 /* Get the valid av_set into AV above the LAST_INSN to start backward
2978 computation from. It either will be empty av_set or av_set computed from
2979 the successors on the last insn of the current bb. */
2980 if (last_insn != after_bb_end)
2982 av = NULL;
2984 /* This is needed only to obtain av_sets that are identical to
2985 those computed by the old compute_av_set version. */
2986 if (last_insn == first_insn && !INSN_NOP_P (last_insn))
2987 av_set_add (&av, INSN_EXPR (last_insn));
2989 else
2990 /* END_WS is always already increased by 1 if LAST_INSN == AFTER_BB_END. */
2991 av = compute_av_set_at_bb_end (bb_end, p, end_ws);
2993 /* Compute av_set in AV starting from below the LAST_INSN up to
2994 location above the FIRST_INSN. */
2995 for (cur_insn = PREV_INSN (last_insn); cur_insn != PREV_INSN (first_insn);
2996 cur_insn = PREV_INSN (cur_insn))
2997 if (!INSN_NOP_P (cur_insn))
2999 expr_t expr;
3001 moveup_set_expr (&av, cur_insn, false);
3003 /* If the expression for CUR_INSN is already in the set,
3004 replace it by the new one. */
3005 expr = av_set_lookup (av, INSN_VINSN (cur_insn));
3006 if (expr != NULL)
3008 clear_expr (expr);
3009 copy_expr (expr, INSN_EXPR (cur_insn));
3011 else
3012 av_set_add (&av, INSN_EXPR (cur_insn));
3015 /* Clear stale bb_av_set. */
3016 if (sel_bb_head_p (first_insn))
3018 av_set_clear (&BB_AV_SET (cur_bb));
3019 BB_AV_SET (cur_bb) = need_copy_p ? av_set_copy (av) : av;
3020 BB_AV_LEVEL (cur_bb) = global_level;
3023 if (sched_verbose >= 6)
3025 sel_print ("Computed av set for insn %d: ", INSN_UID (first_insn));
3026 dump_av_set (av);
3027 sel_print ("\n");
3030 ilist_remove (&p);
3031 return av;
3034 /* Compute av set before INSN.
3035 INSN - the current operation (actual rtx INSN)
3036 P - the current path, which is list of insns visited so far
3037 WS - software lookahead window size.
3038 UNIQUE_P - TRUE, if returned av_set will be changed, hence
3039 if we want to save computed av_set in s_i_d, we should make a copy of it.
3041 In the resulting set we will have only expressions that don't have delay
3042 stalls and nonsubstitutable dependences. */
3043 static av_set_t
3044 compute_av_set (insn_t insn, ilist_t p, int ws, bool unique_p)
3046 return compute_av_set_inside_bb (insn, p, ws, unique_p);
3049 /* Propagate a liveness set LV through INSN. */
3050 static void
3051 propagate_lv_set (regset lv, insn_t insn)
3053 gcc_assert (INSN_P (insn));
3055 if (INSN_NOP_P (insn))
3056 return;
3058 df_simulate_one_insn_backwards (BLOCK_FOR_INSN (insn), insn, lv);
3061 /* Return livness set at the end of BB. */
3062 static regset
3063 compute_live_after_bb (basic_block bb)
3065 edge e;
3066 edge_iterator ei;
3067 regset lv = get_clear_regset_from_pool ();
3069 gcc_assert (!ignore_first);
3071 FOR_EACH_EDGE (e, ei, bb->succs)
3072 if (sel_bb_empty_p (e->dest))
3074 if (! BB_LV_SET_VALID_P (e->dest))
3076 gcc_unreachable ();
3077 gcc_assert (BB_LV_SET (e->dest) == NULL);
3078 BB_LV_SET (e->dest) = compute_live_after_bb (e->dest);
3079 BB_LV_SET_VALID_P (e->dest) = true;
3081 IOR_REG_SET (lv, BB_LV_SET (e->dest));
3083 else
3084 IOR_REG_SET (lv, compute_live (sel_bb_head (e->dest)));
3086 return lv;
3089 /* Compute the set of all live registers at the point before INSN and save
3090 it at INSN if INSN is bb header. */
3091 regset
3092 compute_live (insn_t insn)
3094 basic_block bb = BLOCK_FOR_INSN (insn);
3095 insn_t final, temp;
3096 regset lv;
3098 /* Return the valid set if we're already on it. */
3099 if (!ignore_first)
3101 regset src = NULL;
3103 if (sel_bb_head_p (insn) && BB_LV_SET_VALID_P (bb))
3104 src = BB_LV_SET (bb);
3105 else
3107 gcc_assert (in_current_region_p (bb));
3108 if (INSN_LIVE_VALID_P (insn))
3109 src = INSN_LIVE (insn);
3112 if (src)
3114 lv = get_regset_from_pool ();
3115 COPY_REG_SET (lv, src);
3117 if (sel_bb_head_p (insn) && ! BB_LV_SET_VALID_P (bb))
3119 COPY_REG_SET (BB_LV_SET (bb), lv);
3120 BB_LV_SET_VALID_P (bb) = true;
3123 return_regset_to_pool (lv);
3124 return lv;
3128 /* We've skipped the wrong lv_set. Don't skip the right one. */
3129 ignore_first = false;
3130 gcc_assert (in_current_region_p (bb));
3132 /* Find a valid LV set in this block or below, if needed.
3133 Start searching from the next insn: either ignore_first is true, or
3134 INSN doesn't have a correct live set. */
3135 temp = NEXT_INSN (insn);
3136 final = NEXT_INSN (BB_END (bb));
3137 while (temp != final && ! INSN_LIVE_VALID_P (temp))
3138 temp = NEXT_INSN (temp);
3139 if (temp == final)
3141 lv = compute_live_after_bb (bb);
3142 temp = PREV_INSN (temp);
3144 else
3146 lv = get_regset_from_pool ();
3147 COPY_REG_SET (lv, INSN_LIVE (temp));
3150 /* Put correct lv sets on the insns which have bad sets. */
3151 final = PREV_INSN (insn);
3152 while (temp != final)
3154 propagate_lv_set (lv, temp);
3155 COPY_REG_SET (INSN_LIVE (temp), lv);
3156 INSN_LIVE_VALID_P (temp) = true;
3157 temp = PREV_INSN (temp);
3160 /* Also put it in a BB. */
3161 if (sel_bb_head_p (insn))
3163 basic_block bb = BLOCK_FOR_INSN (insn);
3165 COPY_REG_SET (BB_LV_SET (bb), lv);
3166 BB_LV_SET_VALID_P (bb) = true;
3169 /* We return LV to the pool, but will not clear it there. Thus we can
3170 legimatelly use LV till the next use of regset_pool_get (). */
3171 return_regset_to_pool (lv);
3172 return lv;
3175 /* Update liveness sets for INSN. */
3176 static inline void
3177 update_liveness_on_insn (rtx_insn *insn)
3179 ignore_first = true;
3180 compute_live (insn);
3183 /* Compute liveness below INSN and write it into REGS. */
3184 static inline void
3185 compute_live_below_insn (rtx_insn *insn, regset regs)
3187 rtx_insn *succ;
3188 succ_iterator si;
3190 FOR_EACH_SUCC_1 (succ, si, insn, SUCCS_ALL)
3191 IOR_REG_SET (regs, compute_live (succ));
3194 /* Update the data gathered in av and lv sets starting from INSN. */
3195 static void
3196 update_data_sets (rtx_insn *insn)
3198 update_liveness_on_insn (insn);
3199 if (sel_bb_head_p (insn))
3201 gcc_assert (AV_LEVEL (insn) != 0);
3202 BB_AV_LEVEL (BLOCK_FOR_INSN (insn)) = -1;
3203 compute_av_set (insn, NULL, 0, 0);
3208 /* Helper for move_op () and find_used_regs ().
3209 Return speculation type for which a check should be created on the place
3210 of INSN. EXPR is one of the original ops we are searching for. */
3211 static ds_t
3212 get_spec_check_type_for_insn (insn_t insn, expr_t expr)
3214 ds_t to_check_ds;
3215 ds_t already_checked_ds = EXPR_SPEC_DONE_DS (INSN_EXPR (insn));
3217 to_check_ds = EXPR_SPEC_TO_CHECK_DS (expr);
3219 if (targetm.sched.get_insn_checked_ds)
3220 already_checked_ds |= targetm.sched.get_insn_checked_ds (insn);
3222 if (spec_info != NULL
3223 && (spec_info->flags & SEL_SCHED_SPEC_DONT_CHECK_CONTROL))
3224 already_checked_ds |= BEGIN_CONTROL;
3226 already_checked_ds = ds_get_speculation_types (already_checked_ds);
3228 to_check_ds &= ~already_checked_ds;
3230 return to_check_ds;
3233 /* Find the set of registers that are unavailable for storing expres
3234 while moving ORIG_OPS up on the path starting from INSN due to
3235 liveness (USED_REGS) or hardware restrictions (REG_RENAME_P).
3237 All the original operations found during the traversal are saved in the
3238 ORIGINAL_INSNS list.
3240 REG_RENAME_P denotes the set of hardware registers that
3241 can not be used with renaming due to the register class restrictions,
3242 mode restrictions and other (the register we'll choose should be
3243 compatible class with the original uses, shouldn't be in call_used_regs,
3244 should be HARD_REGNO_RENAME_OK etc).
3246 Returns TRUE if we've found all original insns, FALSE otherwise.
3248 This function utilizes code_motion_path_driver (formerly find_used_regs_1)
3249 to traverse the code motion paths. This helper function finds registers
3250 that are not available for storing expres while moving ORIG_OPS up on the
3251 path starting from INSN. A register considered as used on the moving path,
3252 if one of the following conditions is not satisfied:
3254 (1) a register not set or read on any path from xi to an instance of
3255 the original operation,
3256 (2) not among the live registers of the point immediately following the
3257 first original operation on a given downward path, except for the
3258 original target register of the operation,
3259 (3) not live on the other path of any conditional branch that is passed
3260 by the operation, in case original operations are not present on
3261 both paths of the conditional branch.
3263 All the original operations found during the traversal are saved in the
3264 ORIGINAL_INSNS list.
3266 REG_RENAME_P->CROSSES_CALL is true, if there is a call insn on the path
3267 from INSN to original insn. In this case CALL_USED_REG_SET will be added
3268 to unavailable hard regs at the point original operation is found. */
3270 static bool
3271 find_used_regs (insn_t insn, av_set_t orig_ops, regset used_regs,
3272 struct reg_rename *reg_rename_p, def_list_t *original_insns)
3274 def_list_iterator i;
3275 def_t def;
3276 int res;
3277 bool needs_spec_check_p = false;
3278 expr_t expr;
3279 av_set_iterator expr_iter;
3280 struct fur_static_params sparams;
3281 struct cmpd_local_params lparams;
3283 /* We haven't visited any blocks yet. */
3284 bitmap_clear (code_motion_visited_blocks);
3286 /* Init parameters for code_motion_path_driver. */
3287 sparams.crosses_call = false;
3288 sparams.original_insns = original_insns;
3289 sparams.used_regs = used_regs;
3291 /* Set the appropriate hooks and data. */
3292 code_motion_path_driver_info = &fur_hooks;
3294 res = code_motion_path_driver (insn, orig_ops, NULL, &lparams, &sparams);
3296 reg_rename_p->crosses_call |= sparams.crosses_call;
3298 gcc_assert (res == 1);
3299 gcc_assert (original_insns && *original_insns);
3301 /* ??? We calculate whether an expression needs a check when computing
3302 av sets. This information is not as precise as it could be due to
3303 merging this bit in merge_expr. We can do better in find_used_regs,
3304 but we want to avoid multiple traversals of the same code motion
3305 paths. */
3306 FOR_EACH_EXPR (expr, expr_iter, orig_ops)
3307 needs_spec_check_p |= EXPR_NEEDS_SPEC_CHECK_P (expr);
3309 /* Mark hardware regs in REG_RENAME_P that are not suitable
3310 for renaming expr in INSN due to hardware restrictions (register class,
3311 modes compatibility etc). */
3312 FOR_EACH_DEF (def, i, *original_insns)
3314 vinsn_t vinsn = INSN_VINSN (def->orig_insn);
3316 if (VINSN_SEPARABLE_P (vinsn))
3317 mark_unavailable_hard_regs (def, reg_rename_p, used_regs);
3319 /* Do not allow clobbering of ld.[sa] address in case some of the
3320 original operations need a check. */
3321 if (needs_spec_check_p)
3322 IOR_REG_SET (used_regs, VINSN_REG_USES (vinsn));
3325 return true;
3329 /* Functions to choose the best insn from available ones. */
3331 /* Adjusts the priority for EXPR using the backend *_adjust_priority hook. */
3332 static int
3333 sel_target_adjust_priority (expr_t expr)
3335 int priority = EXPR_PRIORITY (expr);
3336 int new_priority;
3338 if (targetm.sched.adjust_priority)
3339 new_priority = targetm.sched.adjust_priority (EXPR_INSN_RTX (expr), priority);
3340 else
3341 new_priority = priority;
3343 /* If the priority has changed, adjust EXPR_PRIORITY_ADJ accordingly. */
3344 EXPR_PRIORITY_ADJ (expr) = new_priority - EXPR_PRIORITY (expr);
3346 gcc_assert (EXPR_PRIORITY_ADJ (expr) >= 0);
3348 if (sched_verbose >= 4)
3349 sel_print ("sel_target_adjust_priority: insn %d, %d+%d = %d.\n",
3350 INSN_UID (EXPR_INSN_RTX (expr)), EXPR_PRIORITY (expr),
3351 EXPR_PRIORITY_ADJ (expr), new_priority);
3353 return new_priority;
3356 /* Rank two available exprs for schedule. Never return 0 here. */
3357 static int
3358 sel_rank_for_schedule (const void *x, const void *y)
3360 expr_t tmp = *(const expr_t *) y;
3361 expr_t tmp2 = *(const expr_t *) x;
3362 insn_t tmp_insn, tmp2_insn;
3363 vinsn_t tmp_vinsn, tmp2_vinsn;
3364 int val;
3366 tmp_vinsn = EXPR_VINSN (tmp);
3367 tmp2_vinsn = EXPR_VINSN (tmp2);
3368 tmp_insn = EXPR_INSN_RTX (tmp);
3369 tmp2_insn = EXPR_INSN_RTX (tmp2);
3371 /* Schedule debug insns as early as possible. */
3372 if (DEBUG_INSN_P (tmp_insn) && !DEBUG_INSN_P (tmp2_insn))
3373 return -1;
3374 else if (DEBUG_INSN_P (tmp2_insn))
3375 return 1;
3377 /* Prefer SCHED_GROUP_P insns to any others. */
3378 if (SCHED_GROUP_P (tmp_insn) != SCHED_GROUP_P (tmp2_insn))
3380 if (VINSN_UNIQUE_P (tmp_vinsn) && VINSN_UNIQUE_P (tmp2_vinsn))
3381 return SCHED_GROUP_P (tmp2_insn) ? 1 : -1;
3383 /* Now uniqueness means SCHED_GROUP_P is set, because schedule groups
3384 cannot be cloned. */
3385 if (VINSN_UNIQUE_P (tmp2_vinsn))
3386 return 1;
3387 return -1;
3390 /* Discourage scheduling of speculative checks. */
3391 val = (sel_insn_is_speculation_check (tmp_insn)
3392 - sel_insn_is_speculation_check (tmp2_insn));
3393 if (val)
3394 return val;
3396 /* Prefer not scheduled insn over scheduled one. */
3397 if (EXPR_SCHED_TIMES (tmp) > 0 || EXPR_SCHED_TIMES (tmp2) > 0)
3399 val = EXPR_SCHED_TIMES (tmp) - EXPR_SCHED_TIMES (tmp2);
3400 if (val)
3401 return val;
3404 /* Prefer jump over non-jump instruction. */
3405 if (control_flow_insn_p (tmp_insn) && !control_flow_insn_p (tmp2_insn))
3406 return -1;
3407 else if (control_flow_insn_p (tmp2_insn) && !control_flow_insn_p (tmp_insn))
3408 return 1;
3410 /* Prefer an expr with greater priority. */
3411 if (EXPR_USEFULNESS (tmp) != 0 && EXPR_USEFULNESS (tmp2) != 0)
3413 int p2 = EXPR_PRIORITY (tmp2) + EXPR_PRIORITY_ADJ (tmp2),
3414 p1 = EXPR_PRIORITY (tmp) + EXPR_PRIORITY_ADJ (tmp);
3416 val = p2 * EXPR_USEFULNESS (tmp2) - p1 * EXPR_USEFULNESS (tmp);
3418 else
3419 val = EXPR_PRIORITY (tmp2) - EXPR_PRIORITY (tmp)
3420 + EXPR_PRIORITY_ADJ (tmp2) - EXPR_PRIORITY_ADJ (tmp);
3421 if (val)
3422 return val;
3424 if (spec_info != NULL && spec_info->mask != 0)
3425 /* This code was taken from haifa-sched.c: rank_for_schedule (). */
3427 ds_t ds1, ds2;
3428 dw_t dw1, dw2;
3429 int dw;
3431 ds1 = EXPR_SPEC_DONE_DS (tmp);
3432 if (ds1)
3433 dw1 = ds_weak (ds1);
3434 else
3435 dw1 = NO_DEP_WEAK;
3437 ds2 = EXPR_SPEC_DONE_DS (tmp2);
3438 if (ds2)
3439 dw2 = ds_weak (ds2);
3440 else
3441 dw2 = NO_DEP_WEAK;
3443 dw = dw2 - dw1;
3444 if (dw > (NO_DEP_WEAK / 8) || dw < -(NO_DEP_WEAK / 8))
3445 return dw;
3448 /* Prefer an old insn to a bookkeeping insn. */
3449 if (INSN_UID (tmp_insn) < first_emitted_uid
3450 && INSN_UID (tmp2_insn) >= first_emitted_uid)
3451 return -1;
3452 if (INSN_UID (tmp_insn) >= first_emitted_uid
3453 && INSN_UID (tmp2_insn) < first_emitted_uid)
3454 return 1;
3456 /* Prefer an insn with smaller UID, as a last resort.
3457 We can't safely use INSN_LUID as it is defined only for those insns
3458 that are in the stream. */
3459 return INSN_UID (tmp_insn) - INSN_UID (tmp2_insn);
3462 /* Filter out expressions from av set pointed to by AV_PTR
3463 that are pipelined too many times. */
3464 static void
3465 process_pipelined_exprs (av_set_t *av_ptr)
3467 expr_t expr;
3468 av_set_iterator si;
3470 /* Don't pipeline already pipelined code as that would increase
3471 number of unnecessary register moves. */
3472 FOR_EACH_EXPR_1 (expr, si, av_ptr)
3474 if (EXPR_SCHED_TIMES (expr)
3475 >= PARAM_VALUE (PARAM_SELSCHED_MAX_SCHED_TIMES))
3476 av_set_iter_remove (&si);
3480 /* Filter speculative insns from AV_PTR if we don't want them. */
3481 static void
3482 process_spec_exprs (av_set_t *av_ptr)
3484 expr_t expr;
3485 av_set_iterator si;
3487 if (spec_info == NULL)
3488 return;
3490 /* Scan *AV_PTR to find out if we want to consider speculative
3491 instructions for scheduling. */
3492 FOR_EACH_EXPR_1 (expr, si, av_ptr)
3494 ds_t ds;
3496 ds = EXPR_SPEC_DONE_DS (expr);
3498 /* The probability of a success is too low - don't speculate. */
3499 if ((ds & SPECULATIVE)
3500 && (ds_weak (ds) < spec_info->data_weakness_cutoff
3501 || EXPR_USEFULNESS (expr) < spec_info->control_weakness_cutoff
3502 || (pipelining_p && false
3503 && (ds & DATA_SPEC)
3504 && (ds & CONTROL_SPEC))))
3506 av_set_iter_remove (&si);
3507 continue;
3512 /* Search for any use-like insns in AV_PTR and decide on scheduling
3513 them. Return one when found, and NULL otherwise.
3514 Note that we check here whether a USE could be scheduled to avoid
3515 an infinite loop later. */
3516 static expr_t
3517 process_use_exprs (av_set_t *av_ptr)
3519 expr_t expr;
3520 av_set_iterator si;
3521 bool uses_present_p = false;
3522 bool try_uses_p = true;
3524 FOR_EACH_EXPR_1 (expr, si, av_ptr)
3526 /* This will also initialize INSN_CODE for later use. */
3527 if (recog_memoized (EXPR_INSN_RTX (expr)) < 0)
3529 /* If we have a USE in *AV_PTR that was not scheduled yet,
3530 do so because it will do good only. */
3531 if (EXPR_SCHED_TIMES (expr) <= 0)
3533 if (EXPR_TARGET_AVAILABLE (expr) == 1)
3534 return expr;
3536 av_set_iter_remove (&si);
3538 else
3540 gcc_assert (pipelining_p);
3542 uses_present_p = true;
3545 else
3546 try_uses_p = false;
3549 if (uses_present_p)
3551 /* If we don't want to schedule any USEs right now and we have some
3552 in *AV_PTR, remove them, else just return the first one found. */
3553 if (!try_uses_p)
3555 FOR_EACH_EXPR_1 (expr, si, av_ptr)
3556 if (INSN_CODE (EXPR_INSN_RTX (expr)) < 0)
3557 av_set_iter_remove (&si);
3559 else
3561 FOR_EACH_EXPR_1 (expr, si, av_ptr)
3563 gcc_assert (INSN_CODE (EXPR_INSN_RTX (expr)) < 0);
3565 if (EXPR_TARGET_AVAILABLE (expr) == 1)
3566 return expr;
3568 av_set_iter_remove (&si);
3573 return NULL;
3576 /* Lookup EXPR in VINSN_VEC and return TRUE if found. Also check patterns from
3577 EXPR's history of changes. */
3578 static bool
3579 vinsn_vec_has_expr_p (vinsn_vec_t vinsn_vec, expr_t expr)
3581 vinsn_t vinsn, expr_vinsn;
3582 int n;
3583 unsigned i;
3585 /* Start with checking expr itself and then proceed with all the old forms
3586 of expr taken from its history vector. */
3587 for (i = 0, expr_vinsn = EXPR_VINSN (expr);
3588 expr_vinsn;
3589 expr_vinsn = (i < EXPR_HISTORY_OF_CHANGES (expr).length ()
3590 ? EXPR_HISTORY_OF_CHANGES (expr)[i++].old_expr_vinsn
3591 : NULL))
3592 FOR_EACH_VEC_ELT (vinsn_vec, n, vinsn)
3593 if (VINSN_SEPARABLE_P (vinsn))
3595 if (vinsn_equal_p (vinsn, expr_vinsn))
3596 return true;
3598 else
3600 /* For non-separable instructions, the blocking insn can have
3601 another pattern due to substitution, and we can't choose
3602 different register as in the above case. Check all registers
3603 being written instead. */
3604 if (bitmap_intersect_p (VINSN_REG_SETS (vinsn),
3605 VINSN_REG_SETS (expr_vinsn)))
3606 return true;
3609 return false;
3612 #ifdef ENABLE_CHECKING
3613 /* Return true if either of expressions from ORIG_OPS can be blocked
3614 by previously created bookkeeping code. STATIC_PARAMS points to static
3615 parameters of move_op. */
3616 static bool
3617 av_set_could_be_blocked_by_bookkeeping_p (av_set_t orig_ops, void *static_params)
3619 expr_t expr;
3620 av_set_iterator iter;
3621 moveop_static_params_p sparams;
3623 /* This checks that expressions in ORIG_OPS are not blocked by bookkeeping
3624 created while scheduling on another fence. */
3625 FOR_EACH_EXPR (expr, iter, orig_ops)
3626 if (vinsn_vec_has_expr_p (vec_bookkeeping_blocked_vinsns, expr))
3627 return true;
3629 gcc_assert (code_motion_path_driver_info == &move_op_hooks);
3630 sparams = (moveop_static_params_p) static_params;
3632 /* Expressions can be also blocked by bookkeeping created during current
3633 move_op. */
3634 if (bitmap_bit_p (current_copies, INSN_UID (sparams->failed_insn)))
3635 FOR_EACH_EXPR (expr, iter, orig_ops)
3636 if (moveup_expr_cached (expr, sparams->failed_insn, false) != MOVEUP_EXPR_NULL)
3637 return true;
3639 /* Expressions in ORIG_OPS may have wrong destination register due to
3640 renaming. Check with the right register instead. */
3641 if (sparams->dest && REG_P (sparams->dest))
3643 rtx reg = sparams->dest;
3644 vinsn_t failed_vinsn = INSN_VINSN (sparams->failed_insn);
3646 if (register_unavailable_p (VINSN_REG_SETS (failed_vinsn), reg)
3647 || register_unavailable_p (VINSN_REG_USES (failed_vinsn), reg)
3648 || register_unavailable_p (VINSN_REG_CLOBBERS (failed_vinsn), reg))
3649 return true;
3652 return false;
3654 #endif
3656 /* Clear VINSN_VEC and detach vinsns. */
3657 static void
3658 vinsn_vec_clear (vinsn_vec_t *vinsn_vec)
3660 unsigned len = vinsn_vec->length ();
3661 if (len > 0)
3663 vinsn_t vinsn;
3664 int n;
3666 FOR_EACH_VEC_ELT (*vinsn_vec, n, vinsn)
3667 vinsn_detach (vinsn);
3668 vinsn_vec->block_remove (0, len);
3672 /* Add the vinsn of EXPR to the VINSN_VEC. */
3673 static void
3674 vinsn_vec_add (vinsn_vec_t *vinsn_vec, expr_t expr)
3676 vinsn_attach (EXPR_VINSN (expr));
3677 vinsn_vec->safe_push (EXPR_VINSN (expr));
3680 /* Free the vector representing blocked expressions. */
3681 static void
3682 vinsn_vec_free (vinsn_vec_t &vinsn_vec)
3684 vinsn_vec.release ();
3687 /* Increase EXPR_PRIORITY_ADJ for INSN by AMOUNT. */
3689 void sel_add_to_insn_priority (rtx insn, int amount)
3691 EXPR_PRIORITY_ADJ (INSN_EXPR (insn)) += amount;
3693 if (sched_verbose >= 2)
3694 sel_print ("sel_add_to_insn_priority: insn %d, by %d (now %d+%d).\n",
3695 INSN_UID (insn), amount, EXPR_PRIORITY (INSN_EXPR (insn)),
3696 EXPR_PRIORITY_ADJ (INSN_EXPR (insn)));
3699 /* Turn AV into a vector, filter inappropriate insns and sort it. Return
3700 true if there is something to schedule. BNDS and FENCE are current
3701 boundaries and fence, respectively. If we need to stall for some cycles
3702 before an expr from AV would become available, write this number to
3703 *PNEED_STALL. */
3704 static bool
3705 fill_vec_av_set (av_set_t av, blist_t bnds, fence_t fence,
3706 int *pneed_stall)
3708 av_set_iterator si;
3709 expr_t expr;
3710 int sched_next_worked = 0, stalled, n;
3711 static int av_max_prio, est_ticks_till_branch;
3712 int min_need_stall = -1;
3713 deps_t dc = BND_DC (BLIST_BND (bnds));
3715 /* Bail out early when the ready list contained only USEs/CLOBBERs that are
3716 already scheduled. */
3717 if (av == NULL)
3718 return false;
3720 /* Empty vector from the previous stuff. */
3721 if (vec_av_set.length () > 0)
3722 vec_av_set.block_remove (0, vec_av_set.length ());
3724 /* Turn the set into a vector for sorting and call sel_target_adjust_priority
3725 for each insn. */
3726 gcc_assert (vec_av_set.is_empty ());
3727 FOR_EACH_EXPR (expr, si, av)
3729 vec_av_set.safe_push (expr);
3731 gcc_assert (EXPR_PRIORITY_ADJ (expr) == 0 || *pneed_stall);
3733 /* Adjust priority using target backend hook. */
3734 sel_target_adjust_priority (expr);
3737 /* Sort the vector. */
3738 vec_av_set.qsort (sel_rank_for_schedule);
3740 /* We record maximal priority of insns in av set for current instruction
3741 group. */
3742 if (FENCE_STARTS_CYCLE_P (fence))
3743 av_max_prio = est_ticks_till_branch = INT_MIN;
3745 /* Filter out inappropriate expressions. Loop's direction is reversed to
3746 visit "best" instructions first. We assume that vec::unordered_remove
3747 moves last element in place of one being deleted. */
3748 for (n = vec_av_set.length () - 1, stalled = 0; n >= 0; n--)
3750 expr_t expr = vec_av_set[n];
3751 insn_t insn = EXPR_INSN_RTX (expr);
3752 signed char target_available;
3753 bool is_orig_reg_p = true;
3754 int need_cycles, new_prio;
3755 bool fence_insn_p = INSN_UID (insn) == INSN_UID (FENCE_INSN (fence));
3757 /* Don't allow any insns other than from SCHED_GROUP if we have one. */
3758 if (FENCE_SCHED_NEXT (fence) && insn != FENCE_SCHED_NEXT (fence))
3760 vec_av_set.unordered_remove (n);
3761 continue;
3764 /* Set number of sched_next insns (just in case there
3765 could be several). */
3766 if (FENCE_SCHED_NEXT (fence))
3767 sched_next_worked++;
3769 /* Check all liveness requirements and try renaming.
3770 FIXME: try to minimize calls to this. */
3771 target_available = EXPR_TARGET_AVAILABLE (expr);
3773 /* If insn was already scheduled on the current fence,
3774 set TARGET_AVAILABLE to -1 no matter what expr's attribute says. */
3775 if (vinsn_vec_has_expr_p (vec_target_unavailable_vinsns, expr)
3776 && !fence_insn_p)
3777 target_available = -1;
3779 /* If the availability of the EXPR is invalidated by the insertion of
3780 bookkeeping earlier, make sure that we won't choose this expr for
3781 scheduling if it's not separable, and if it is separable, then
3782 we have to recompute the set of available registers for it. */
3783 if (vinsn_vec_has_expr_p (vec_bookkeeping_blocked_vinsns, expr))
3785 vec_av_set.unordered_remove (n);
3786 if (sched_verbose >= 4)
3787 sel_print ("Expr %d is blocked by bookkeeping inserted earlier\n",
3788 INSN_UID (insn));
3789 continue;
3792 if (target_available == true)
3794 /* Do nothing -- we can use an existing register. */
3795 is_orig_reg_p = EXPR_SEPARABLE_P (expr);
3797 else if (/* Non-separable instruction will never
3798 get another register. */
3799 (target_available == false
3800 && !EXPR_SEPARABLE_P (expr))
3801 /* Don't try to find a register for low-priority expression. */
3802 || (int) vec_av_set.length () - 1 - n >= max_insns_to_rename
3803 /* ??? FIXME: Don't try to rename data speculation. */
3804 || (EXPR_SPEC_DONE_DS (expr) & BEGIN_DATA)
3805 || ! find_best_reg_for_expr (expr, bnds, &is_orig_reg_p))
3807 vec_av_set.unordered_remove (n);
3808 if (sched_verbose >= 4)
3809 sel_print ("Expr %d has no suitable target register\n",
3810 INSN_UID (insn));
3812 /* A fence insn should not get here. */
3813 gcc_assert (!fence_insn_p);
3814 continue;
3817 /* At this point a fence insn should always be available. */
3818 gcc_assert (!fence_insn_p
3819 || INSN_UID (FENCE_INSN (fence)) == INSN_UID (EXPR_INSN_RTX (expr)));
3821 /* Filter expressions that need to be renamed or speculated when
3822 pipelining, because compensating register copies or speculation
3823 checks are likely to be placed near the beginning of the loop,
3824 causing a stall. */
3825 if (pipelining_p && EXPR_ORIG_SCHED_CYCLE (expr) > 0
3826 && (!is_orig_reg_p || EXPR_SPEC_DONE_DS (expr) != 0))
3828 /* Estimation of number of cycles until loop branch for
3829 renaming/speculation to be successful. */
3830 int need_n_ticks_till_branch = sel_vinsn_cost (EXPR_VINSN (expr));
3832 if ((int) current_loop_nest->ninsns < 9)
3834 vec_av_set.unordered_remove (n);
3835 if (sched_verbose >= 4)
3836 sel_print ("Pipelining expr %d will likely cause stall\n",
3837 INSN_UID (insn));
3838 continue;
3841 if ((int) current_loop_nest->ninsns - num_insns_scheduled
3842 < need_n_ticks_till_branch * issue_rate / 2
3843 && est_ticks_till_branch < need_n_ticks_till_branch)
3845 vec_av_set.unordered_remove (n);
3846 if (sched_verbose >= 4)
3847 sel_print ("Pipelining expr %d will likely cause stall\n",
3848 INSN_UID (insn));
3849 continue;
3853 /* We want to schedule speculation checks as late as possible. Discard
3854 them from av set if there are instructions with higher priority. */
3855 if (sel_insn_is_speculation_check (insn)
3856 && EXPR_PRIORITY (expr) < av_max_prio)
3858 stalled++;
3859 min_need_stall = min_need_stall < 0 ? 1 : MIN (min_need_stall, 1);
3860 vec_av_set.unordered_remove (n);
3861 if (sched_verbose >= 4)
3862 sel_print ("Delaying speculation check %d until its first use\n",
3863 INSN_UID (insn));
3864 continue;
3867 /* Ignore EXPRs available from pipelining to update AV_MAX_PRIO. */
3868 if (EXPR_ORIG_SCHED_CYCLE (expr) <= 0)
3869 av_max_prio = MAX (av_max_prio, EXPR_PRIORITY (expr));
3871 /* Don't allow any insns whose data is not yet ready.
3872 Check first whether we've already tried them and failed. */
3873 if (INSN_UID (insn) < FENCE_READY_TICKS_SIZE (fence))
3875 need_cycles = (FENCE_READY_TICKS (fence)[INSN_UID (insn)]
3876 - FENCE_CYCLE (fence));
3877 if (EXPR_ORIG_SCHED_CYCLE (expr) <= 0)
3878 est_ticks_till_branch = MAX (est_ticks_till_branch,
3879 EXPR_PRIORITY (expr) + need_cycles);
3881 if (need_cycles > 0)
3883 stalled++;
3884 min_need_stall = (min_need_stall < 0
3885 ? need_cycles
3886 : MIN (min_need_stall, need_cycles));
3887 vec_av_set.unordered_remove (n);
3889 if (sched_verbose >= 4)
3890 sel_print ("Expr %d is not ready until cycle %d (cached)\n",
3891 INSN_UID (insn),
3892 FENCE_READY_TICKS (fence)[INSN_UID (insn)]);
3893 continue;
3897 /* Now resort to dependence analysis to find whether EXPR might be
3898 stalled due to dependencies from FENCE's context. */
3899 need_cycles = tick_check_p (expr, dc, fence);
3900 new_prio = EXPR_PRIORITY (expr) + EXPR_PRIORITY_ADJ (expr) + need_cycles;
3902 if (EXPR_ORIG_SCHED_CYCLE (expr) <= 0)
3903 est_ticks_till_branch = MAX (est_ticks_till_branch,
3904 new_prio);
3906 if (need_cycles > 0)
3908 if (INSN_UID (insn) >= FENCE_READY_TICKS_SIZE (fence))
3910 int new_size = INSN_UID (insn) * 3 / 2;
3912 FENCE_READY_TICKS (fence)
3913 = (int *) xrecalloc (FENCE_READY_TICKS (fence),
3914 new_size, FENCE_READY_TICKS_SIZE (fence),
3915 sizeof (int));
3917 FENCE_READY_TICKS (fence)[INSN_UID (insn)]
3918 = FENCE_CYCLE (fence) + need_cycles;
3920 stalled++;
3921 min_need_stall = (min_need_stall < 0
3922 ? need_cycles
3923 : MIN (min_need_stall, need_cycles));
3925 vec_av_set.unordered_remove (n);
3927 if (sched_verbose >= 4)
3928 sel_print ("Expr %d is not ready yet until cycle %d\n",
3929 INSN_UID (insn),
3930 FENCE_READY_TICKS (fence)[INSN_UID (insn)]);
3931 continue;
3934 if (sched_verbose >= 4)
3935 sel_print ("Expr %d is ok\n", INSN_UID (insn));
3936 min_need_stall = 0;
3939 /* Clear SCHED_NEXT. */
3940 if (FENCE_SCHED_NEXT (fence))
3942 gcc_assert (sched_next_worked == 1);
3943 FENCE_SCHED_NEXT (fence) = NULL;
3946 /* No need to stall if this variable was not initialized. */
3947 if (min_need_stall < 0)
3948 min_need_stall = 0;
3950 if (vec_av_set.is_empty ())
3952 /* We need to set *pneed_stall here, because later we skip this code
3953 when ready list is empty. */
3954 *pneed_stall = min_need_stall;
3955 return false;
3957 else
3958 gcc_assert (min_need_stall == 0);
3960 /* Sort the vector. */
3961 vec_av_set.qsort (sel_rank_for_schedule);
3963 if (sched_verbose >= 4)
3965 sel_print ("Total ready exprs: %d, stalled: %d\n",
3966 vec_av_set.length (), stalled);
3967 sel_print ("Sorted av set (%d): ", vec_av_set.length ());
3968 FOR_EACH_VEC_ELT (vec_av_set, n, expr)
3969 dump_expr (expr);
3970 sel_print ("\n");
3973 *pneed_stall = 0;
3974 return true;
3977 /* Convert a vectored and sorted av set to the ready list that
3978 the rest of the backend wants to see. */
3979 static void
3980 convert_vec_av_set_to_ready (void)
3982 int n;
3983 expr_t expr;
3985 /* Allocate and fill the ready list from the sorted vector. */
3986 ready.n_ready = vec_av_set.length ();
3987 ready.first = ready.n_ready - 1;
3989 gcc_assert (ready.n_ready > 0);
3991 if (ready.n_ready > max_issue_size)
3993 max_issue_size = ready.n_ready;
3994 sched_extend_ready_list (ready.n_ready);
3997 FOR_EACH_VEC_ELT (vec_av_set, n, expr)
3999 vinsn_t vi = EXPR_VINSN (expr);
4000 insn_t insn = VINSN_INSN_RTX (vi);
4002 ready_try[n] = 0;
4003 ready.vec[n] = insn;
4007 /* Initialize ready list from *AV_PTR for the max_issue () call.
4008 If any unrecognizable insn found in *AV_PTR, return it (and skip
4009 max_issue). BND and FENCE are current boundary and fence,
4010 respectively. If we need to stall for some cycles before an expr
4011 from *AV_PTR would become available, write this number to *PNEED_STALL. */
4012 static expr_t
4013 fill_ready_list (av_set_t *av_ptr, blist_t bnds, fence_t fence,
4014 int *pneed_stall)
4016 expr_t expr;
4018 /* We do not support multiple boundaries per fence. */
4019 gcc_assert (BLIST_NEXT (bnds) == NULL);
4021 /* Process expressions required special handling, i.e. pipelined,
4022 speculative and recog() < 0 expressions first. */
4023 process_pipelined_exprs (av_ptr);
4024 process_spec_exprs (av_ptr);
4026 /* A USE could be scheduled immediately. */
4027 expr = process_use_exprs (av_ptr);
4028 if (expr)
4030 *pneed_stall = 0;
4031 return expr;
4034 /* Turn the av set to a vector for sorting. */
4035 if (! fill_vec_av_set (*av_ptr, bnds, fence, pneed_stall))
4037 ready.n_ready = 0;
4038 return NULL;
4041 /* Build the final ready list. */
4042 convert_vec_av_set_to_ready ();
4043 return NULL;
4046 /* Wrapper for dfa_new_cycle (). Returns TRUE if cycle was advanced. */
4047 static bool
4048 sel_dfa_new_cycle (insn_t insn, fence_t fence)
4050 int last_scheduled_cycle = FENCE_LAST_SCHEDULED_INSN (fence)
4051 ? INSN_SCHED_CYCLE (FENCE_LAST_SCHEDULED_INSN (fence))
4052 : FENCE_CYCLE (fence) - 1;
4053 bool res = false;
4054 int sort_p = 0;
4056 if (!targetm.sched.dfa_new_cycle)
4057 return false;
4059 memcpy (curr_state, FENCE_STATE (fence), dfa_state_size);
4061 while (!sort_p && targetm.sched.dfa_new_cycle (sched_dump, sched_verbose,
4062 insn, last_scheduled_cycle,
4063 FENCE_CYCLE (fence), &sort_p))
4065 memcpy (FENCE_STATE (fence), curr_state, dfa_state_size);
4066 advance_one_cycle (fence);
4067 memcpy (curr_state, FENCE_STATE (fence), dfa_state_size);
4068 res = true;
4071 return res;
4074 /* Invoke reorder* target hooks on the ready list. Return the number of insns
4075 we can issue. FENCE is the current fence. */
4076 static int
4077 invoke_reorder_hooks (fence_t fence)
4079 int issue_more;
4080 bool ran_hook = false;
4082 /* Call the reorder hook at the beginning of the cycle, and call
4083 the reorder2 hook in the middle of the cycle. */
4084 if (FENCE_ISSUED_INSNS (fence) == 0)
4086 if (targetm.sched.reorder
4087 && !SCHED_GROUP_P (ready_element (&ready, 0))
4088 && ready.n_ready > 1)
4090 /* Don't give reorder the most prioritized insn as it can break
4091 pipelining. */
4092 if (pipelining_p)
4093 --ready.n_ready;
4095 issue_more
4096 = targetm.sched.reorder (sched_dump, sched_verbose,
4097 ready_lastpos (&ready),
4098 &ready.n_ready, FENCE_CYCLE (fence));
4100 if (pipelining_p)
4101 ++ready.n_ready;
4103 ran_hook = true;
4105 else
4106 /* Initialize can_issue_more for variable_issue. */
4107 issue_more = issue_rate;
4109 else if (targetm.sched.reorder2
4110 && !SCHED_GROUP_P (ready_element (&ready, 0)))
4112 if (ready.n_ready == 1)
4113 issue_more =
4114 targetm.sched.reorder2 (sched_dump, sched_verbose,
4115 ready_lastpos (&ready),
4116 &ready.n_ready, FENCE_CYCLE (fence));
4117 else
4119 if (pipelining_p)
4120 --ready.n_ready;
4122 issue_more =
4123 targetm.sched.reorder2 (sched_dump, sched_verbose,
4124 ready.n_ready
4125 ? ready_lastpos (&ready) : NULL,
4126 &ready.n_ready, FENCE_CYCLE (fence));
4128 if (pipelining_p)
4129 ++ready.n_ready;
4132 ran_hook = true;
4134 else
4135 issue_more = FENCE_ISSUE_MORE (fence);
4137 /* Ensure that ready list and vec_av_set are in line with each other,
4138 i.e. vec_av_set[i] == ready_element (&ready, i). */
4139 if (issue_more && ran_hook)
4141 int i, j, n;
4142 rtx_insn **arr = ready.vec;
4143 expr_t *vec = vec_av_set.address ();
4145 for (i = 0, n = ready.n_ready; i < n; i++)
4146 if (EXPR_INSN_RTX (vec[i]) != arr[i])
4148 expr_t tmp;
4150 for (j = i; j < n; j++)
4151 if (EXPR_INSN_RTX (vec[j]) == arr[i])
4152 break;
4153 gcc_assert (j < n);
4155 tmp = vec[i];
4156 vec[i] = vec[j];
4157 vec[j] = tmp;
4161 return issue_more;
4164 /* Return an EXPR corresponding to INDEX element of ready list, if
4165 FOLLOW_READY_ELEMENT is true (i.e., an expr of
4166 ready_element (&ready, INDEX) will be returned), and to INDEX element of
4167 ready.vec otherwise. */
4168 static inline expr_t
4169 find_expr_for_ready (int index, bool follow_ready_element)
4171 expr_t expr;
4172 int real_index;
4174 real_index = follow_ready_element ? ready.first - index : index;
4176 expr = vec_av_set[real_index];
4177 gcc_assert (ready.vec[real_index] == EXPR_INSN_RTX (expr));
4179 return expr;
4182 /* Calculate insns worth trying via lookahead_guard hook. Return a number
4183 of such insns found. */
4184 static int
4185 invoke_dfa_lookahead_guard (void)
4187 int i, n;
4188 bool have_hook
4189 = targetm.sched.first_cycle_multipass_dfa_lookahead_guard != NULL;
4191 if (sched_verbose >= 2)
4192 sel_print ("ready after reorder: ");
4194 for (i = 0, n = 0; i < ready.n_ready; i++)
4196 expr_t expr;
4197 insn_t insn;
4198 int r;
4200 /* In this loop insn is Ith element of the ready list given by
4201 ready_element, not Ith element of ready.vec. */
4202 insn = ready_element (&ready, i);
4204 if (! have_hook || i == 0)
4205 r = 0;
4206 else
4207 r = targetm.sched.first_cycle_multipass_dfa_lookahead_guard (insn, i);
4209 gcc_assert (INSN_CODE (insn) >= 0);
4211 /* Only insns with ready_try = 0 can get here
4212 from fill_ready_list. */
4213 gcc_assert (ready_try [i] == 0);
4214 ready_try[i] = r;
4215 if (!r)
4216 n++;
4218 expr = find_expr_for_ready (i, true);
4220 if (sched_verbose >= 2)
4222 dump_vinsn (EXPR_VINSN (expr));
4223 sel_print (":%d; ", ready_try[i]);
4227 if (sched_verbose >= 2)
4228 sel_print ("\n");
4229 return n;
4232 /* Calculate the number of privileged insns and return it. */
4233 static int
4234 calculate_privileged_insns (void)
4236 expr_t cur_expr, min_spec_expr = NULL;
4237 int privileged_n = 0, i;
4239 for (i = 0; i < ready.n_ready; i++)
4241 if (ready_try[i])
4242 continue;
4244 if (! min_spec_expr)
4245 min_spec_expr = find_expr_for_ready (i, true);
4247 cur_expr = find_expr_for_ready (i, true);
4249 if (EXPR_SPEC (cur_expr) > EXPR_SPEC (min_spec_expr))
4250 break;
4252 ++privileged_n;
4255 if (i == ready.n_ready)
4256 privileged_n = 0;
4258 if (sched_verbose >= 2)
4259 sel_print ("privileged_n: %d insns with SPEC %d\n",
4260 privileged_n, privileged_n ? EXPR_SPEC (min_spec_expr) : -1);
4261 return privileged_n;
4264 /* Call the rest of the hooks after the choice was made. Return
4265 the number of insns that still can be issued given that the current
4266 number is ISSUE_MORE. FENCE and BEST_INSN are the current fence
4267 and the insn chosen for scheduling, respectively. */
4268 static int
4269 invoke_aftermath_hooks (fence_t fence, rtx_insn *best_insn, int issue_more)
4271 gcc_assert (INSN_P (best_insn));
4273 /* First, call dfa_new_cycle, and then variable_issue, if available. */
4274 sel_dfa_new_cycle (best_insn, fence);
4276 if (targetm.sched.variable_issue)
4278 memcpy (curr_state, FENCE_STATE (fence), dfa_state_size);
4279 issue_more =
4280 targetm.sched.variable_issue (sched_dump, sched_verbose, best_insn,
4281 issue_more);
4282 memcpy (FENCE_STATE (fence), curr_state, dfa_state_size);
4284 else if (GET_CODE (PATTERN (best_insn)) != USE
4285 && GET_CODE (PATTERN (best_insn)) != CLOBBER)
4286 issue_more--;
4288 return issue_more;
4291 /* Estimate the cost of issuing INSN on DFA state STATE. */
4292 static int
4293 estimate_insn_cost (rtx_insn *insn, state_t state)
4295 static state_t temp = NULL;
4296 int cost;
4298 if (!temp)
4299 temp = xmalloc (dfa_state_size);
4301 memcpy (temp, state, dfa_state_size);
4302 cost = state_transition (temp, insn);
4304 if (cost < 0)
4305 return 0;
4306 else if (cost == 0)
4307 return 1;
4308 return cost;
4311 /* Return the cost of issuing EXPR on the FENCE as estimated by DFA.
4312 This function properly handles ASMs, USEs etc. */
4313 static int
4314 get_expr_cost (expr_t expr, fence_t fence)
4316 rtx_insn *insn = EXPR_INSN_RTX (expr);
4318 if (recog_memoized (insn) < 0)
4320 if (!FENCE_STARTS_CYCLE_P (fence)
4321 && INSN_ASM_P (insn))
4322 /* This is asm insn which is tryed to be issued on the
4323 cycle not first. Issue it on the next cycle. */
4324 return 1;
4325 else
4326 /* A USE insn, or something else we don't need to
4327 understand. We can't pass these directly to
4328 state_transition because it will trigger a
4329 fatal error for unrecognizable insns. */
4330 return 0;
4332 else
4333 return estimate_insn_cost (insn, FENCE_STATE (fence));
4336 /* Find the best insn for scheduling, either via max_issue or just take
4337 the most prioritized available. */
4338 static int
4339 choose_best_insn (fence_t fence, int privileged_n, int *index)
4341 int can_issue = 0;
4343 if (dfa_lookahead > 0)
4345 cycle_issued_insns = FENCE_ISSUED_INSNS (fence);
4346 /* TODO: pass equivalent of first_cycle_insn_p to max_issue (). */
4347 can_issue = max_issue (&ready, privileged_n,
4348 FENCE_STATE (fence), true, index);
4349 if (sched_verbose >= 2)
4350 sel_print ("max_issue: we can issue %d insns, already did %d insns\n",
4351 can_issue, FENCE_ISSUED_INSNS (fence));
4353 else
4355 /* We can't use max_issue; just return the first available element. */
4356 int i;
4358 for (i = 0; i < ready.n_ready; i++)
4360 expr_t expr = find_expr_for_ready (i, true);
4362 if (get_expr_cost (expr, fence) < 1)
4364 can_issue = can_issue_more;
4365 *index = i;
4367 if (sched_verbose >= 2)
4368 sel_print ("using %dth insn from the ready list\n", i + 1);
4370 break;
4374 if (i == ready.n_ready)
4376 can_issue = 0;
4377 *index = -1;
4381 return can_issue;
4384 /* Choose the best expr from *AV_VLIW_PTR and a suitable register for it.
4385 BNDS and FENCE are current boundaries and scheduling fence respectively.
4386 Return the expr found and NULL if nothing can be issued atm.
4387 Write to PNEED_STALL the number of cycles to stall if no expr was found. */
4388 static expr_t
4389 find_best_expr (av_set_t *av_vliw_ptr, blist_t bnds, fence_t fence,
4390 int *pneed_stall)
4392 expr_t best;
4394 /* Choose the best insn for scheduling via:
4395 1) sorting the ready list based on priority;
4396 2) calling the reorder hook;
4397 3) calling max_issue. */
4398 best = fill_ready_list (av_vliw_ptr, bnds, fence, pneed_stall);
4399 if (best == NULL && ready.n_ready > 0)
4401 int privileged_n, index;
4403 can_issue_more = invoke_reorder_hooks (fence);
4404 if (can_issue_more > 0)
4406 /* Try choosing the best insn until we find one that is could be
4407 scheduled due to liveness restrictions on its destination register.
4408 In the future, we'd like to choose once and then just probe insns
4409 in the order of their priority. */
4410 invoke_dfa_lookahead_guard ();
4411 privileged_n = calculate_privileged_insns ();
4412 can_issue_more = choose_best_insn (fence, privileged_n, &index);
4413 if (can_issue_more)
4414 best = find_expr_for_ready (index, true);
4416 /* We had some available insns, so if we can't issue them,
4417 we have a stall. */
4418 if (can_issue_more == 0)
4420 best = NULL;
4421 *pneed_stall = 1;
4425 if (best != NULL)
4427 can_issue_more = invoke_aftermath_hooks (fence, EXPR_INSN_RTX (best),
4428 can_issue_more);
4429 if (targetm.sched.variable_issue
4430 && can_issue_more == 0)
4431 *pneed_stall = 1;
4434 if (sched_verbose >= 2)
4436 if (best != NULL)
4438 sel_print ("Best expression (vliw form): ");
4439 dump_expr (best);
4440 sel_print ("; cycle %d\n", FENCE_CYCLE (fence));
4442 else
4443 sel_print ("No best expr found!\n");
4446 return best;
4450 /* Functions that implement the core of the scheduler. */
4453 /* Emit an instruction from EXPR with SEQNO and VINSN after
4454 PLACE_TO_INSERT. */
4455 static insn_t
4456 emit_insn_from_expr_after (expr_t expr, vinsn_t vinsn, int seqno,
4457 insn_t place_to_insert)
4459 /* This assert fails when we have identical instructions
4460 one of which dominates the other. In this case move_op ()
4461 finds the first instruction and doesn't search for second one.
4462 The solution would be to compute av_set after the first found
4463 insn and, if insn present in that set, continue searching.
4464 For now we workaround this issue in move_op. */
4465 gcc_assert (!INSN_IN_STREAM_P (EXPR_INSN_RTX (expr)));
4467 if (EXPR_WAS_RENAMED (expr))
4469 unsigned regno = expr_dest_regno (expr);
4471 if (HARD_REGISTER_NUM_P (regno))
4473 df_set_regs_ever_live (regno, true);
4474 reg_rename_tick[regno] = ++reg_rename_this_tick;
4478 return sel_gen_insn_from_expr_after (expr, vinsn, seqno,
4479 place_to_insert);
4482 /* Return TRUE if BB can hold bookkeeping code. */
4483 static bool
4484 block_valid_for_bookkeeping_p (basic_block bb)
4486 insn_t bb_end = BB_END (bb);
4488 if (!in_current_region_p (bb) || EDGE_COUNT (bb->succs) > 1)
4489 return false;
4491 if (INSN_P (bb_end))
4493 if (INSN_SCHED_TIMES (bb_end) > 0)
4494 return false;
4496 else
4497 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (bb_end));
4499 return true;
4502 /* Attempt to find a block that can hold bookkeeping code for path(s) incoming
4503 into E2->dest, except from E1->src (there may be a sequence of empty basic
4504 blocks between E1->src and E2->dest). Return found block, or NULL if new
4505 one must be created. If LAX holds, don't assume there is a simple path
4506 from E1->src to E2->dest. */
4507 static basic_block
4508 find_block_for_bookkeeping (edge e1, edge e2, bool lax)
4510 basic_block candidate_block = NULL;
4511 edge e;
4513 /* Loop over edges from E1 to E2, inclusive. */
4514 for (e = e1; !lax || e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun); e =
4515 EDGE_SUCC (e->dest, 0))
4517 if (EDGE_COUNT (e->dest->preds) == 2)
4519 if (candidate_block == NULL)
4520 candidate_block = (EDGE_PRED (e->dest, 0) == e
4521 ? EDGE_PRED (e->dest, 1)->src
4522 : EDGE_PRED (e->dest, 0)->src);
4523 else
4524 /* Found additional edge leading to path from e1 to e2
4525 from aside. */
4526 return NULL;
4528 else if (EDGE_COUNT (e->dest->preds) > 2)
4529 /* Several edges leading to path from e1 to e2 from aside. */
4530 return NULL;
4532 if (e == e2)
4533 return ((!lax || candidate_block)
4534 && block_valid_for_bookkeeping_p (candidate_block)
4535 ? candidate_block
4536 : NULL);
4538 if (lax && EDGE_COUNT (e->dest->succs) != 1)
4539 return NULL;
4542 if (lax)
4543 return NULL;
4545 gcc_unreachable ();
4548 /* Create new basic block for bookkeeping code for path(s) incoming into
4549 E2->dest, except from E1->src. Return created block. */
4550 static basic_block
4551 create_block_for_bookkeeping (edge e1, edge e2)
4553 basic_block new_bb, bb = e2->dest;
4555 /* Check that we don't spoil the loop structure. */
4556 if (current_loop_nest)
4558 basic_block latch = current_loop_nest->latch;
4560 /* We do not split header. */
4561 gcc_assert (e2->dest != current_loop_nest->header);
4563 /* We do not redirect the only edge to the latch block. */
4564 gcc_assert (e1->dest != latch
4565 || !single_pred_p (latch)
4566 || e1 != single_pred_edge (latch));
4569 /* Split BB to insert BOOK_INSN there. */
4570 new_bb = sched_split_block (bb, NULL);
4572 /* Move note_list from the upper bb. */
4573 gcc_assert (BB_NOTE_LIST (new_bb) == NULL_RTX);
4574 BB_NOTE_LIST (new_bb) = BB_NOTE_LIST (bb);
4575 BB_NOTE_LIST (bb) = NULL;
4577 gcc_assert (e2->dest == bb);
4579 /* Skip block for bookkeeping copy when leaving E1->src. */
4580 if (e1->flags & EDGE_FALLTHRU)
4581 sel_redirect_edge_and_branch_force (e1, new_bb);
4582 else
4583 sel_redirect_edge_and_branch (e1, new_bb);
4585 gcc_assert (e1->dest == new_bb);
4586 gcc_assert (sel_bb_empty_p (bb));
4588 /* To keep basic block numbers in sync between debug and non-debug
4589 compilations, we have to rotate blocks here. Consider that we
4590 started from (a,b)->d, (c,d)->e, and d contained only debug
4591 insns. It would have been removed before if the debug insns
4592 weren't there, so we'd have split e rather than d. So what we do
4593 now is to swap the block numbers of new_bb and
4594 single_succ(new_bb) == e, so that the insns that were in e before
4595 get the new block number. */
4597 if (MAY_HAVE_DEBUG_INSNS)
4599 basic_block succ;
4600 insn_t insn = sel_bb_head (new_bb);
4601 insn_t last;
4603 if (DEBUG_INSN_P (insn)
4604 && single_succ_p (new_bb)
4605 && (succ = single_succ (new_bb))
4606 && succ != EXIT_BLOCK_PTR_FOR_FN (cfun)
4607 && DEBUG_INSN_P ((last = sel_bb_end (new_bb))))
4609 while (insn != last && (DEBUG_INSN_P (insn) || NOTE_P (insn)))
4610 insn = NEXT_INSN (insn);
4612 if (insn == last)
4614 sel_global_bb_info_def gbi;
4615 sel_region_bb_info_def rbi;
4616 int i;
4618 if (sched_verbose >= 2)
4619 sel_print ("Swapping block ids %i and %i\n",
4620 new_bb->index, succ->index);
4622 i = new_bb->index;
4623 new_bb->index = succ->index;
4624 succ->index = i;
4626 SET_BASIC_BLOCK_FOR_FN (cfun, new_bb->index, new_bb);
4627 SET_BASIC_BLOCK_FOR_FN (cfun, succ->index, succ);
4629 memcpy (&gbi, SEL_GLOBAL_BB_INFO (new_bb), sizeof (gbi));
4630 memcpy (SEL_GLOBAL_BB_INFO (new_bb), SEL_GLOBAL_BB_INFO (succ),
4631 sizeof (gbi));
4632 memcpy (SEL_GLOBAL_BB_INFO (succ), &gbi, sizeof (gbi));
4634 memcpy (&rbi, SEL_REGION_BB_INFO (new_bb), sizeof (rbi));
4635 memcpy (SEL_REGION_BB_INFO (new_bb), SEL_REGION_BB_INFO (succ),
4636 sizeof (rbi));
4637 memcpy (SEL_REGION_BB_INFO (succ), &rbi, sizeof (rbi));
4639 i = BLOCK_TO_BB (new_bb->index);
4640 BLOCK_TO_BB (new_bb->index) = BLOCK_TO_BB (succ->index);
4641 BLOCK_TO_BB (succ->index) = i;
4643 i = CONTAINING_RGN (new_bb->index);
4644 CONTAINING_RGN (new_bb->index) = CONTAINING_RGN (succ->index);
4645 CONTAINING_RGN (succ->index) = i;
4647 for (i = 0; i < current_nr_blocks; i++)
4648 if (BB_TO_BLOCK (i) == succ->index)
4649 BB_TO_BLOCK (i) = new_bb->index;
4650 else if (BB_TO_BLOCK (i) == new_bb->index)
4651 BB_TO_BLOCK (i) = succ->index;
4653 FOR_BB_INSNS (new_bb, insn)
4654 if (INSN_P (insn))
4655 EXPR_ORIG_BB_INDEX (INSN_EXPR (insn)) = new_bb->index;
4657 FOR_BB_INSNS (succ, insn)
4658 if (INSN_P (insn))
4659 EXPR_ORIG_BB_INDEX (INSN_EXPR (insn)) = succ->index;
4661 if (bitmap_clear_bit (code_motion_visited_blocks, new_bb->index))
4662 bitmap_set_bit (code_motion_visited_blocks, succ->index);
4664 gcc_assert (LABEL_P (BB_HEAD (new_bb))
4665 && LABEL_P (BB_HEAD (succ)));
4667 if (sched_verbose >= 4)
4668 sel_print ("Swapping code labels %i and %i\n",
4669 CODE_LABEL_NUMBER (BB_HEAD (new_bb)),
4670 CODE_LABEL_NUMBER (BB_HEAD (succ)));
4672 i = CODE_LABEL_NUMBER (BB_HEAD (new_bb));
4673 CODE_LABEL_NUMBER (BB_HEAD (new_bb))
4674 = CODE_LABEL_NUMBER (BB_HEAD (succ));
4675 CODE_LABEL_NUMBER (BB_HEAD (succ)) = i;
4680 return bb;
4683 /* Return insn after which we must insert bookkeeping code for path(s) incoming
4684 into E2->dest, except from E1->src. If the returned insn immediately
4685 precedes a fence, assign that fence to *FENCE_TO_REWIND. */
4686 static insn_t
4687 find_place_for_bookkeeping (edge e1, edge e2, fence_t *fence_to_rewind)
4689 insn_t place_to_insert;
4690 /* Find a basic block that can hold bookkeeping. If it can be found, do not
4691 create new basic block, but insert bookkeeping there. */
4692 basic_block book_block = find_block_for_bookkeeping (e1, e2, FALSE);
4694 if (book_block)
4696 place_to_insert = BB_END (book_block);
4698 /* Don't use a block containing only debug insns for
4699 bookkeeping, this causes scheduling differences between debug
4700 and non-debug compilations, for the block would have been
4701 removed already. */
4702 if (DEBUG_INSN_P (place_to_insert))
4704 rtx_insn *insn = sel_bb_head (book_block);
4706 while (insn != place_to_insert &&
4707 (DEBUG_INSN_P (insn) || NOTE_P (insn)))
4708 insn = NEXT_INSN (insn);
4710 if (insn == place_to_insert)
4711 book_block = NULL;
4715 if (!book_block)
4717 book_block = create_block_for_bookkeeping (e1, e2);
4718 place_to_insert = BB_END (book_block);
4719 if (sched_verbose >= 9)
4720 sel_print ("New block is %i, split from bookkeeping block %i\n",
4721 EDGE_SUCC (book_block, 0)->dest->index, book_block->index);
4723 else
4725 if (sched_verbose >= 9)
4726 sel_print ("Pre-existing bookkeeping block is %i\n", book_block->index);
4729 *fence_to_rewind = NULL;
4730 /* If basic block ends with a jump, insert bookkeeping code right before it.
4731 Notice if we are crossing a fence when taking PREV_INSN. */
4732 if (INSN_P (place_to_insert) && control_flow_insn_p (place_to_insert))
4734 *fence_to_rewind = flist_lookup (fences, place_to_insert);
4735 place_to_insert = PREV_INSN (place_to_insert);
4738 return place_to_insert;
4741 /* Find a proper seqno for bookkeeing insn inserted at PLACE_TO_INSERT
4742 for JOIN_POINT. */
4743 static int
4744 find_seqno_for_bookkeeping (insn_t place_to_insert, insn_t join_point)
4746 int seqno;
4747 rtx next;
4749 /* Check if we are about to insert bookkeeping copy before a jump, and use
4750 jump's seqno for the copy; otherwise, use JOIN_POINT's seqno. */
4751 next = NEXT_INSN (place_to_insert);
4752 if (INSN_P (next)
4753 && JUMP_P (next)
4754 && BLOCK_FOR_INSN (next) == BLOCK_FOR_INSN (place_to_insert))
4756 gcc_assert (INSN_SCHED_TIMES (next) == 0);
4757 seqno = INSN_SEQNO (next);
4759 else if (INSN_SEQNO (join_point) > 0)
4760 seqno = INSN_SEQNO (join_point);
4761 else
4763 seqno = get_seqno_by_preds (place_to_insert);
4765 /* Sometimes the fences can move in such a way that there will be
4766 no instructions with positive seqno around this bookkeeping.
4767 This means that there will be no way to get to it by a regular
4768 fence movement. Never mind because we pick up such pieces for
4769 rescheduling anyways, so any positive value will do for now. */
4770 if (seqno < 0)
4772 gcc_assert (pipelining_p);
4773 seqno = 1;
4777 gcc_assert (seqno > 0);
4778 return seqno;
4781 /* Insert bookkeeping copy of C_EXPS's insn after PLACE_TO_INSERT, assigning
4782 NEW_SEQNO to it. Return created insn. */
4783 static insn_t
4784 emit_bookkeeping_insn (insn_t place_to_insert, expr_t c_expr, int new_seqno)
4786 rtx_insn *new_insn_rtx = create_copy_of_insn_rtx (EXPR_INSN_RTX (c_expr));
4788 vinsn_t new_vinsn
4789 = create_vinsn_from_insn_rtx (new_insn_rtx,
4790 VINSN_UNIQUE_P (EXPR_VINSN (c_expr)));
4792 insn_t new_insn = emit_insn_from_expr_after (c_expr, new_vinsn, new_seqno,
4793 place_to_insert);
4795 INSN_SCHED_TIMES (new_insn) = 0;
4796 bitmap_set_bit (current_copies, INSN_UID (new_insn));
4798 return new_insn;
4801 /* Generate a bookkeeping copy of C_EXPR's insn for path(s) incoming into to
4802 E2->dest, except from E1->src (there may be a sequence of empty blocks
4803 between E1->src and E2->dest). Return block containing the copy.
4804 All scheduler data is initialized for the newly created insn. */
4805 static basic_block
4806 generate_bookkeeping_insn (expr_t c_expr, edge e1, edge e2)
4808 insn_t join_point, place_to_insert, new_insn;
4809 int new_seqno;
4810 bool need_to_exchange_data_sets;
4811 fence_t fence_to_rewind;
4813 if (sched_verbose >= 4)
4814 sel_print ("Generating bookkeeping insn (%d->%d)\n", e1->src->index,
4815 e2->dest->index);
4817 join_point = sel_bb_head (e2->dest);
4818 place_to_insert = find_place_for_bookkeeping (e1, e2, &fence_to_rewind);
4819 new_seqno = find_seqno_for_bookkeeping (place_to_insert, join_point);
4820 need_to_exchange_data_sets
4821 = sel_bb_empty_p (BLOCK_FOR_INSN (place_to_insert));
4823 new_insn = emit_bookkeeping_insn (place_to_insert, c_expr, new_seqno);
4825 if (fence_to_rewind)
4826 FENCE_INSN (fence_to_rewind) = new_insn;
4828 /* When inserting bookkeeping insn in new block, av sets should be
4829 following: old basic block (that now holds bookkeeping) data sets are
4830 the same as was before generation of bookkeeping, and new basic block
4831 (that now hold all other insns of old basic block) data sets are
4832 invalid. So exchange data sets for these basic blocks as sel_split_block
4833 mistakenly exchanges them in this case. Cannot do it earlier because
4834 when single instruction is added to new basic block it should hold NULL
4835 lv_set. */
4836 if (need_to_exchange_data_sets)
4837 exchange_data_sets (BLOCK_FOR_INSN (new_insn),
4838 BLOCK_FOR_INSN (join_point));
4840 stat_bookkeeping_copies++;
4841 return BLOCK_FOR_INSN (new_insn);
4844 /* Remove from AV_PTR all insns that may need bookkeeping when scheduling
4845 on FENCE, but we are unable to copy them. */
4846 static void
4847 remove_insns_that_need_bookkeeping (fence_t fence, av_set_t *av_ptr)
4849 expr_t expr;
4850 av_set_iterator i;
4852 /* An expression does not need bookkeeping if it is available on all paths
4853 from current block to original block and current block dominates
4854 original block. We check availability on all paths by examining
4855 EXPR_SPEC; this is not equivalent, because it may be positive even
4856 if expr is available on all paths (but if expr is not available on
4857 any path, EXPR_SPEC will be positive). */
4859 FOR_EACH_EXPR_1 (expr, i, av_ptr)
4861 if (!control_flow_insn_p (EXPR_INSN_RTX (expr))
4862 && (!bookkeeping_p || VINSN_UNIQUE_P (EXPR_VINSN (expr)))
4863 && (EXPR_SPEC (expr)
4864 || !EXPR_ORIG_BB_INDEX (expr)
4865 || !dominated_by_p (CDI_DOMINATORS,
4866 BASIC_BLOCK_FOR_FN (cfun,
4867 EXPR_ORIG_BB_INDEX (expr)),
4868 BLOCK_FOR_INSN (FENCE_INSN (fence)))))
4870 if (sched_verbose >= 4)
4871 sel_print ("Expr %d removed because it would need bookkeeping, which "
4872 "cannot be created\n", INSN_UID (EXPR_INSN_RTX (expr)));
4873 av_set_iter_remove (&i);
4878 /* Moving conditional jump through some instructions.
4880 Consider example:
4882 ... <- current scheduling point
4883 NOTE BASIC BLOCK: <- bb header
4884 (p8) add r14=r14+0x9;;
4885 (p8) mov [r14]=r23
4886 (!p8) jump L1;;
4887 NOTE BASIC BLOCK:
4890 We can schedule jump one cycle earlier, than mov, because they cannot be
4891 executed together as their predicates are mutually exclusive.
4893 This is done in this way: first, new fallthrough basic block is created
4894 after jump (it is always can be done, because there already should be a
4895 fallthrough block, where control flow goes in case of predicate being true -
4896 in our example; otherwise there should be a dependence between those
4897 instructions and jump and we cannot schedule jump right now);
4898 next, all instructions between jump and current scheduling point are moved
4899 to this new block. And the result is this:
4901 NOTE BASIC BLOCK:
4902 (!p8) jump L1 <- current scheduling point
4903 NOTE BASIC BLOCK: <- bb header
4904 (p8) add r14=r14+0x9;;
4905 (p8) mov [r14]=r23
4906 NOTE BASIC BLOCK:
4909 static void
4910 move_cond_jump (rtx_insn *insn, bnd_t bnd)
4912 edge ft_edge;
4913 basic_block block_from, block_next, block_new, block_bnd, bb;
4914 rtx_insn *next, *prev, *link, *head;
4916 block_from = BLOCK_FOR_INSN (insn);
4917 block_bnd = BLOCK_FOR_INSN (BND_TO (bnd));
4918 prev = BND_TO (bnd);
4920 #ifdef ENABLE_CHECKING
4921 /* Moving of jump should not cross any other jumps or beginnings of new
4922 basic blocks. The only exception is when we move a jump through
4923 mutually exclusive insns along fallthru edges. */
4924 if (block_from != block_bnd)
4926 bb = block_from;
4927 for (link = PREV_INSN (insn); link != PREV_INSN (prev);
4928 link = PREV_INSN (link))
4930 if (INSN_P (link))
4931 gcc_assert (sched_insns_conditions_mutex_p (insn, link));
4932 if (BLOCK_FOR_INSN (link) && BLOCK_FOR_INSN (link) != bb)
4934 gcc_assert (single_pred (bb) == BLOCK_FOR_INSN (link));
4935 bb = BLOCK_FOR_INSN (link);
4939 #endif
4941 /* Jump is moved to the boundary. */
4942 next = PREV_INSN (insn);
4943 BND_TO (bnd) = insn;
4945 ft_edge = find_fallthru_edge_from (block_from);
4946 block_next = ft_edge->dest;
4947 /* There must be a fallthrough block (or where should go
4948 control flow in case of false jump predicate otherwise?). */
4949 gcc_assert (block_next);
4951 /* Create new empty basic block after source block. */
4952 block_new = sel_split_edge (ft_edge);
4953 gcc_assert (block_new->next_bb == block_next
4954 && block_from->next_bb == block_new);
4956 /* Move all instructions except INSN to BLOCK_NEW. */
4957 bb = block_bnd;
4958 head = BB_HEAD (block_new);
4959 while (bb != block_from->next_bb)
4961 rtx_insn *from, *to;
4962 from = bb == block_bnd ? prev : sel_bb_head (bb);
4963 to = bb == block_from ? next : sel_bb_end (bb);
4965 /* The jump being moved can be the first insn in the block.
4966 In this case we don't have to move anything in this block. */
4967 if (NEXT_INSN (to) != from)
4969 reorder_insns (from, to, head);
4971 for (link = to; link != head; link = PREV_INSN (link))
4972 EXPR_ORIG_BB_INDEX (INSN_EXPR (link)) = block_new->index;
4973 head = to;
4976 /* Cleanup possibly empty blocks left. */
4977 block_next = bb->next_bb;
4978 if (bb != block_from)
4979 tidy_control_flow (bb, false);
4980 bb = block_next;
4983 /* Assert there is no jump to BLOCK_NEW, only fallthrough edge. */
4984 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (BB_HEAD (block_new)));
4986 gcc_assert (!sel_bb_empty_p (block_from)
4987 && !sel_bb_empty_p (block_new));
4989 /* Update data sets for BLOCK_NEW to represent that INSN and
4990 instructions from the other branch of INSN is no longer
4991 available at BLOCK_NEW. */
4992 BB_AV_LEVEL (block_new) = global_level;
4993 gcc_assert (BB_LV_SET (block_new) == NULL);
4994 BB_LV_SET (block_new) = get_clear_regset_from_pool ();
4995 update_data_sets (sel_bb_head (block_new));
4997 /* INSN is a new basic block header - so prepare its data
4998 structures and update availability and liveness sets. */
4999 update_data_sets (insn);
5001 if (sched_verbose >= 4)
5002 sel_print ("Moving jump %d\n", INSN_UID (insn));
5005 /* Remove nops generated during move_op for preventing removal of empty
5006 basic blocks. */
5007 static void
5008 remove_temp_moveop_nops (bool full_tidying)
5010 int i;
5011 insn_t insn;
5013 FOR_EACH_VEC_ELT (vec_temp_moveop_nops, i, insn)
5015 gcc_assert (INSN_NOP_P (insn));
5016 return_nop_to_pool (insn, full_tidying);
5019 /* Empty the vector. */
5020 if (vec_temp_moveop_nops.length () > 0)
5021 vec_temp_moveop_nops.block_remove (0, vec_temp_moveop_nops.length ());
5024 /* Records the maximal UID before moving up an instruction. Used for
5025 distinguishing between bookkeeping copies and original insns. */
5026 static int max_uid_before_move_op = 0;
5028 /* Remove from AV_VLIW_P all instructions but next when debug counter
5029 tells us so. Next instruction is fetched from BNDS. */
5030 static void
5031 remove_insns_for_debug (blist_t bnds, av_set_t *av_vliw_p)
5033 if (! dbg_cnt (sel_sched_insn_cnt))
5034 /* Leave only the next insn in av_vliw. */
5036 av_set_iterator av_it;
5037 expr_t expr;
5038 bnd_t bnd = BLIST_BND (bnds);
5039 insn_t next = BND_TO (bnd);
5041 gcc_assert (BLIST_NEXT (bnds) == NULL);
5043 FOR_EACH_EXPR_1 (expr, av_it, av_vliw_p)
5044 if (EXPR_INSN_RTX (expr) != next)
5045 av_set_iter_remove (&av_it);
5049 /* Compute available instructions on BNDS. FENCE is the current fence. Write
5050 the computed set to *AV_VLIW_P. */
5051 static void
5052 compute_av_set_on_boundaries (fence_t fence, blist_t bnds, av_set_t *av_vliw_p)
5054 if (sched_verbose >= 2)
5056 sel_print ("Boundaries: ");
5057 dump_blist (bnds);
5058 sel_print ("\n");
5061 for (; bnds; bnds = BLIST_NEXT (bnds))
5063 bnd_t bnd = BLIST_BND (bnds);
5064 av_set_t av1_copy;
5065 insn_t bnd_to = BND_TO (bnd);
5067 /* Rewind BND->TO to the basic block header in case some bookkeeping
5068 instructions were inserted before BND->TO and it needs to be
5069 adjusted. */
5070 if (sel_bb_head_p (bnd_to))
5071 gcc_assert (INSN_SCHED_TIMES (bnd_to) == 0);
5072 else
5073 while (INSN_SCHED_TIMES (PREV_INSN (bnd_to)) == 0)
5075 bnd_to = PREV_INSN (bnd_to);
5076 if (sel_bb_head_p (bnd_to))
5077 break;
5080 if (BND_TO (bnd) != bnd_to)
5082 gcc_assert (FENCE_INSN (fence) == BND_TO (bnd));
5083 FENCE_INSN (fence) = bnd_to;
5084 BND_TO (bnd) = bnd_to;
5087 av_set_clear (&BND_AV (bnd));
5088 BND_AV (bnd) = compute_av_set (BND_TO (bnd), NULL, 0, true);
5090 av_set_clear (&BND_AV1 (bnd));
5091 BND_AV1 (bnd) = av_set_copy (BND_AV (bnd));
5093 moveup_set_inside_insn_group (&BND_AV1 (bnd), NULL);
5095 av1_copy = av_set_copy (BND_AV1 (bnd));
5096 av_set_union_and_clear (av_vliw_p, &av1_copy, NULL);
5099 if (sched_verbose >= 2)
5101 sel_print ("Available exprs (vliw form): ");
5102 dump_av_set (*av_vliw_p);
5103 sel_print ("\n");
5107 /* Calculate the sequential av set on BND corresponding to the EXPR_VLIW
5108 expression. When FOR_MOVEOP is true, also replace the register of
5109 expressions found with the register from EXPR_VLIW. */
5110 static av_set_t
5111 find_sequential_best_exprs (bnd_t bnd, expr_t expr_vliw, bool for_moveop)
5113 av_set_t expr_seq = NULL;
5114 expr_t expr;
5115 av_set_iterator i;
5117 FOR_EACH_EXPR (expr, i, BND_AV (bnd))
5119 if (equal_after_moveup_path_p (expr, NULL, expr_vliw))
5121 if (for_moveop)
5123 /* The sequential expression has the right form to pass
5124 to move_op except when renaming happened. Put the
5125 correct register in EXPR then. */
5126 if (EXPR_SEPARABLE_P (expr) && REG_P (EXPR_LHS (expr)))
5128 if (expr_dest_regno (expr) != expr_dest_regno (expr_vliw))
5130 replace_dest_with_reg_in_expr (expr, EXPR_LHS (expr_vliw));
5131 stat_renamed_scheduled++;
5133 /* Also put the correct TARGET_AVAILABLE bit on the expr.
5134 This is needed when renaming came up with original
5135 register. */
5136 else if (EXPR_TARGET_AVAILABLE (expr)
5137 != EXPR_TARGET_AVAILABLE (expr_vliw))
5139 gcc_assert (EXPR_TARGET_AVAILABLE (expr_vliw) == 1);
5140 EXPR_TARGET_AVAILABLE (expr) = 1;
5143 if (EXPR_WAS_SUBSTITUTED (expr))
5144 stat_substitutions_total++;
5147 av_set_add (&expr_seq, expr);
5149 /* With substitution inside insn group, it is possible
5150 that more than one expression in expr_seq will correspond
5151 to expr_vliw. In this case, choose one as the attempt to
5152 move both leads to miscompiles. */
5153 break;
5157 if (for_moveop && sched_verbose >= 2)
5159 sel_print ("Best expression(s) (sequential form): ");
5160 dump_av_set (expr_seq);
5161 sel_print ("\n");
5164 return expr_seq;
5168 /* Move nop to previous block. */
5169 static void ATTRIBUTE_UNUSED
5170 move_nop_to_previous_block (insn_t nop, basic_block prev_bb)
5172 insn_t prev_insn, next_insn, note;
5174 gcc_assert (sel_bb_head_p (nop)
5175 && prev_bb == BLOCK_FOR_INSN (nop)->prev_bb);
5176 note = bb_note (BLOCK_FOR_INSN (nop));
5177 prev_insn = sel_bb_end (prev_bb);
5178 next_insn = NEXT_INSN (nop);
5179 gcc_assert (prev_insn != NULL_RTX
5180 && PREV_INSN (note) == prev_insn);
5182 SET_NEXT_INSN (prev_insn) = nop;
5183 SET_PREV_INSN (nop) = prev_insn;
5185 SET_PREV_INSN (note) = nop;
5186 SET_NEXT_INSN (note) = next_insn;
5188 SET_NEXT_INSN (nop) = note;
5189 SET_PREV_INSN (next_insn) = note;
5191 BB_END (prev_bb) = nop;
5192 BLOCK_FOR_INSN (nop) = prev_bb;
5195 /* Prepare a place to insert the chosen expression on BND. */
5196 static insn_t
5197 prepare_place_to_insert (bnd_t bnd)
5199 insn_t place_to_insert;
5201 /* Init place_to_insert before calling move_op, as the later
5202 can possibly remove BND_TO (bnd). */
5203 if (/* If this is not the first insn scheduled. */
5204 BND_PTR (bnd))
5206 /* Add it after last scheduled. */
5207 place_to_insert = ILIST_INSN (BND_PTR (bnd));
5208 if (DEBUG_INSN_P (place_to_insert))
5210 ilist_t l = BND_PTR (bnd);
5211 while ((l = ILIST_NEXT (l)) &&
5212 DEBUG_INSN_P (ILIST_INSN (l)))
5214 if (!l)
5215 place_to_insert = NULL;
5218 else
5219 place_to_insert = NULL;
5221 if (!place_to_insert)
5223 /* Add it before BND_TO. The difference is in the
5224 basic block, where INSN will be added. */
5225 place_to_insert = get_nop_from_pool (BND_TO (bnd));
5226 gcc_assert (BLOCK_FOR_INSN (place_to_insert)
5227 == BLOCK_FOR_INSN (BND_TO (bnd)));
5230 return place_to_insert;
5233 /* Find original instructions for EXPR_SEQ and move it to BND boundary.
5234 Return the expression to emit in C_EXPR. */
5235 static bool
5236 move_exprs_to_boundary (bnd_t bnd, expr_t expr_vliw,
5237 av_set_t expr_seq, expr_t c_expr)
5239 bool b, should_move;
5240 unsigned book_uid;
5241 bitmap_iterator bi;
5242 int n_bookkeeping_copies_before_moveop;
5244 /* Make a move. This call will remove the original operation,
5245 insert all necessary bookkeeping instructions and update the
5246 data sets. After that all we have to do is add the operation
5247 at before BND_TO (BND). */
5248 n_bookkeeping_copies_before_moveop = stat_bookkeeping_copies;
5249 max_uid_before_move_op = get_max_uid ();
5250 bitmap_clear (current_copies);
5251 bitmap_clear (current_originators);
5253 b = move_op (BND_TO (bnd), expr_seq, expr_vliw,
5254 get_dest_from_orig_ops (expr_seq), c_expr, &should_move);
5256 /* We should be able to find the expression we've chosen for
5257 scheduling. */
5258 gcc_assert (b);
5260 if (stat_bookkeeping_copies > n_bookkeeping_copies_before_moveop)
5261 stat_insns_needed_bookkeeping++;
5263 EXECUTE_IF_SET_IN_BITMAP (current_copies, 0, book_uid, bi)
5265 unsigned uid;
5266 bitmap_iterator bi;
5268 /* We allocate these bitmaps lazily. */
5269 if (! INSN_ORIGINATORS_BY_UID (book_uid))
5270 INSN_ORIGINATORS_BY_UID (book_uid) = BITMAP_ALLOC (NULL);
5272 bitmap_copy (INSN_ORIGINATORS_BY_UID (book_uid),
5273 current_originators);
5275 /* Transitively add all originators' originators. */
5276 EXECUTE_IF_SET_IN_BITMAP (current_originators, 0, uid, bi)
5277 if (INSN_ORIGINATORS_BY_UID (uid))
5278 bitmap_ior_into (INSN_ORIGINATORS_BY_UID (book_uid),
5279 INSN_ORIGINATORS_BY_UID (uid));
5282 return should_move;
5286 /* Debug a DFA state as an array of bytes. */
5287 static void
5288 debug_state (state_t state)
5290 unsigned char *p;
5291 unsigned int i, size = dfa_state_size;
5293 sel_print ("state (%u):", size);
5294 for (i = 0, p = (unsigned char *) state; i < size; i++)
5295 sel_print (" %d", p[i]);
5296 sel_print ("\n");
5299 /* Advance state on FENCE with INSN. Return true if INSN is
5300 an ASM, and we should advance state once more. */
5301 static bool
5302 advance_state_on_fence (fence_t fence, insn_t insn)
5304 bool asm_p;
5306 if (recog_memoized (insn) >= 0)
5308 int res;
5309 state_t temp_state = alloca (dfa_state_size);
5311 gcc_assert (!INSN_ASM_P (insn));
5312 asm_p = false;
5314 memcpy (temp_state, FENCE_STATE (fence), dfa_state_size);
5315 res = state_transition (FENCE_STATE (fence), insn);
5316 gcc_assert (res < 0);
5318 if (memcmp (temp_state, FENCE_STATE (fence), dfa_state_size))
5320 FENCE_ISSUED_INSNS (fence)++;
5322 /* We should never issue more than issue_rate insns. */
5323 if (FENCE_ISSUED_INSNS (fence) > issue_rate)
5324 gcc_unreachable ();
5327 else
5329 /* This could be an ASM insn which we'd like to schedule
5330 on the next cycle. */
5331 asm_p = INSN_ASM_P (insn);
5332 if (!FENCE_STARTS_CYCLE_P (fence) && asm_p)
5333 advance_one_cycle (fence);
5336 if (sched_verbose >= 2)
5337 debug_state (FENCE_STATE (fence));
5338 if (!DEBUG_INSN_P (insn))
5339 FENCE_STARTS_CYCLE_P (fence) = 0;
5340 FENCE_ISSUE_MORE (fence) = can_issue_more;
5341 return asm_p;
5344 /* Update FENCE on which INSN was scheduled and this INSN, too. NEED_STALL
5345 is nonzero if we need to stall after issuing INSN. */
5346 static void
5347 update_fence_and_insn (fence_t fence, insn_t insn, int need_stall)
5349 bool asm_p;
5351 /* First, reflect that something is scheduled on this fence. */
5352 asm_p = advance_state_on_fence (fence, insn);
5353 FENCE_LAST_SCHEDULED_INSN (fence) = insn;
5354 vec_safe_push (FENCE_EXECUTING_INSNS (fence), insn);
5355 if (SCHED_GROUP_P (insn))
5357 FENCE_SCHED_NEXT (fence) = INSN_SCHED_NEXT (insn);
5358 SCHED_GROUP_P (insn) = 0;
5360 else
5361 FENCE_SCHED_NEXT (fence) = NULL;
5362 if (INSN_UID (insn) < FENCE_READY_TICKS_SIZE (fence))
5363 FENCE_READY_TICKS (fence) [INSN_UID (insn)] = 0;
5365 /* Set instruction scheduling info. This will be used in bundling,
5366 pipelining, tick computations etc. */
5367 ++INSN_SCHED_TIMES (insn);
5368 EXPR_TARGET_AVAILABLE (INSN_EXPR (insn)) = true;
5369 EXPR_ORIG_SCHED_CYCLE (INSN_EXPR (insn)) = FENCE_CYCLE (fence);
5370 INSN_AFTER_STALL_P (insn) = FENCE_AFTER_STALL_P (fence);
5371 INSN_SCHED_CYCLE (insn) = FENCE_CYCLE (fence);
5373 /* This does not account for adjust_cost hooks, just add the biggest
5374 constant the hook may add to the latency. TODO: make this
5375 a target dependent constant. */
5376 INSN_READY_CYCLE (insn)
5377 = INSN_SCHED_CYCLE (insn) + (INSN_CODE (insn) < 0
5379 : maximal_insn_latency (insn) + 1);
5381 /* Change these fields last, as they're used above. */
5382 FENCE_AFTER_STALL_P (fence) = 0;
5383 if (asm_p || need_stall)
5384 advance_one_cycle (fence);
5386 /* Indicate that we've scheduled something on this fence. */
5387 FENCE_SCHEDULED_P (fence) = true;
5388 scheduled_something_on_previous_fence = true;
5390 /* Print debug information when insn's fields are updated. */
5391 if (sched_verbose >= 2)
5393 sel_print ("Scheduling insn: ");
5394 dump_insn_1 (insn, 1);
5395 sel_print ("\n");
5399 /* Update boundary BND (and, if needed, FENCE) with INSN, remove the
5400 old boundary from BNDSP, add new boundaries to BNDS_TAIL_P and
5401 return it. */
5402 static blist_t *
5403 update_boundaries (fence_t fence, bnd_t bnd, insn_t insn, blist_t *bndsp,
5404 blist_t *bnds_tailp)
5406 succ_iterator si;
5407 insn_t succ;
5409 advance_deps_context (BND_DC (bnd), insn);
5410 FOR_EACH_SUCC_1 (succ, si, insn,
5411 SUCCS_NORMAL | SUCCS_SKIP_TO_LOOP_EXITS)
5413 ilist_t ptr = ilist_copy (BND_PTR (bnd));
5415 ilist_add (&ptr, insn);
5417 if (DEBUG_INSN_P (insn) && sel_bb_end_p (insn)
5418 && is_ineligible_successor (succ, ptr))
5420 ilist_clear (&ptr);
5421 continue;
5424 if (FENCE_INSN (fence) == insn && !sel_bb_end_p (insn))
5426 if (sched_verbose >= 9)
5427 sel_print ("Updating fence insn from %i to %i\n",
5428 INSN_UID (insn), INSN_UID (succ));
5429 FENCE_INSN (fence) = succ;
5431 blist_add (bnds_tailp, succ, ptr, BND_DC (bnd));
5432 bnds_tailp = &BLIST_NEXT (*bnds_tailp);
5435 blist_remove (bndsp);
5436 return bnds_tailp;
5439 /* Schedule EXPR_VLIW on BND. Return the insn emitted. */
5440 static insn_t
5441 schedule_expr_on_boundary (bnd_t bnd, expr_t expr_vliw, int seqno)
5443 av_set_t expr_seq;
5444 expr_t c_expr = XALLOCA (expr_def);
5445 insn_t place_to_insert;
5446 insn_t insn;
5447 bool should_move;
5449 expr_seq = find_sequential_best_exprs (bnd, expr_vliw, true);
5451 /* In case of scheduling a jump skipping some other instructions,
5452 prepare CFG. After this, jump is at the boundary and can be
5453 scheduled as usual insn by MOVE_OP. */
5454 if (vinsn_cond_branch_p (EXPR_VINSN (expr_vliw)))
5456 insn = EXPR_INSN_RTX (expr_vliw);
5458 /* Speculative jumps are not handled. */
5459 if (insn != BND_TO (bnd)
5460 && !sel_insn_is_speculation_check (insn))
5461 move_cond_jump (insn, bnd);
5464 /* Find a place for C_EXPR to schedule. */
5465 place_to_insert = prepare_place_to_insert (bnd);
5466 should_move = move_exprs_to_boundary (bnd, expr_vliw, expr_seq, c_expr);
5467 clear_expr (c_expr);
5469 /* Add the instruction. The corner case to care about is when
5470 the expr_seq set has more than one expr, and we chose the one that
5471 is not equal to expr_vliw. Then expr_vliw may be insn in stream, and
5472 we can't use it. Generate the new vinsn. */
5473 if (INSN_IN_STREAM_P (EXPR_INSN_RTX (expr_vliw)))
5475 vinsn_t vinsn_new;
5477 vinsn_new = vinsn_copy (EXPR_VINSN (expr_vliw), false);
5478 change_vinsn_in_expr (expr_vliw, vinsn_new);
5479 should_move = false;
5481 if (should_move)
5482 insn = sel_move_insn (expr_vliw, seqno, place_to_insert);
5483 else
5484 insn = emit_insn_from_expr_after (expr_vliw, NULL, seqno,
5485 place_to_insert);
5487 /* Return the nops generated for preserving of data sets back
5488 into pool. */
5489 if (INSN_NOP_P (place_to_insert))
5490 return_nop_to_pool (place_to_insert, !DEBUG_INSN_P (insn));
5491 remove_temp_moveop_nops (!DEBUG_INSN_P (insn));
5493 av_set_clear (&expr_seq);
5495 /* Save the expression scheduled so to reset target availability if we'll
5496 meet it later on the same fence. */
5497 if (EXPR_WAS_RENAMED (expr_vliw))
5498 vinsn_vec_add (&vec_target_unavailable_vinsns, INSN_EXPR (insn));
5500 /* Check that the recent movement didn't destroyed loop
5501 structure. */
5502 gcc_assert (!pipelining_p
5503 || current_loop_nest == NULL
5504 || loop_latch_edge (current_loop_nest));
5505 return insn;
5508 /* Stall for N cycles on FENCE. */
5509 static void
5510 stall_for_cycles (fence_t fence, int n)
5512 int could_more;
5514 could_more = n > 1 || FENCE_ISSUED_INSNS (fence) < issue_rate;
5515 while (n--)
5516 advance_one_cycle (fence);
5517 if (could_more)
5518 FENCE_AFTER_STALL_P (fence) = 1;
5521 /* Gather a parallel group of insns at FENCE and assign their seqno
5522 to SEQNO. All scheduled insns are gathered in SCHEDULED_INSNS_TAILPP
5523 list for later recalculation of seqnos. */
5524 static void
5525 fill_insns (fence_t fence, int seqno, ilist_t **scheduled_insns_tailpp)
5527 blist_t bnds = NULL, *bnds_tailp;
5528 av_set_t av_vliw = NULL;
5529 insn_t insn = FENCE_INSN (fence);
5531 if (sched_verbose >= 2)
5532 sel_print ("Starting fill_insns for insn %d, cycle %d\n",
5533 INSN_UID (insn), FENCE_CYCLE (fence));
5535 blist_add (&bnds, insn, NULL, FENCE_DC (fence));
5536 bnds_tailp = &BLIST_NEXT (bnds);
5537 set_target_context (FENCE_TC (fence));
5538 can_issue_more = FENCE_ISSUE_MORE (fence);
5539 target_bb = INSN_BB (insn);
5541 /* Do while we can add any operation to the current group. */
5544 blist_t *bnds_tailp1, *bndsp;
5545 expr_t expr_vliw;
5546 int need_stall = false;
5547 int was_stall = 0, scheduled_insns = 0;
5548 int max_insns = pipelining_p ? issue_rate : 2 * issue_rate;
5549 int max_stall = pipelining_p ? 1 : 3;
5550 bool last_insn_was_debug = false;
5551 bool was_debug_bb_end_p = false;
5553 compute_av_set_on_boundaries (fence, bnds, &av_vliw);
5554 remove_insns_that_need_bookkeeping (fence, &av_vliw);
5555 remove_insns_for_debug (bnds, &av_vliw);
5557 /* Return early if we have nothing to schedule. */
5558 if (av_vliw == NULL)
5559 break;
5561 /* Choose the best expression and, if needed, destination register
5562 for it. */
5565 expr_vliw = find_best_expr (&av_vliw, bnds, fence, &need_stall);
5566 if (! expr_vliw && need_stall)
5568 /* All expressions required a stall. Do not recompute av sets
5569 as we'll get the same answer (modulo the insns between
5570 the fence and its boundary, which will not be available for
5571 pipelining).
5572 If we are going to stall for too long, break to recompute av
5573 sets and bring more insns for pipelining. */
5574 was_stall++;
5575 if (need_stall <= 3)
5576 stall_for_cycles (fence, need_stall);
5577 else
5579 stall_for_cycles (fence, 1);
5580 break;
5584 while (! expr_vliw && need_stall);
5586 /* Now either we've selected expr_vliw or we have nothing to schedule. */
5587 if (!expr_vliw)
5589 av_set_clear (&av_vliw);
5590 break;
5593 bndsp = &bnds;
5594 bnds_tailp1 = bnds_tailp;
5597 /* This code will be executed only once until we'd have several
5598 boundaries per fence. */
5600 bnd_t bnd = BLIST_BND (*bndsp);
5602 if (!av_set_is_in_p (BND_AV1 (bnd), EXPR_VINSN (expr_vliw)))
5604 bndsp = &BLIST_NEXT (*bndsp);
5605 continue;
5608 insn = schedule_expr_on_boundary (bnd, expr_vliw, seqno);
5609 last_insn_was_debug = DEBUG_INSN_P (insn);
5610 if (last_insn_was_debug)
5611 was_debug_bb_end_p = (insn == BND_TO (bnd) && sel_bb_end_p (insn));
5612 update_fence_and_insn (fence, insn, need_stall);
5613 bnds_tailp = update_boundaries (fence, bnd, insn, bndsp, bnds_tailp);
5615 /* Add insn to the list of scheduled on this cycle instructions. */
5616 ilist_add (*scheduled_insns_tailpp, insn);
5617 *scheduled_insns_tailpp = &ILIST_NEXT (**scheduled_insns_tailpp);
5619 while (*bndsp != *bnds_tailp1);
5621 av_set_clear (&av_vliw);
5622 if (!last_insn_was_debug)
5623 scheduled_insns++;
5625 /* We currently support information about candidate blocks only for
5626 one 'target_bb' block. Hence we can't schedule after jump insn,
5627 as this will bring two boundaries and, hence, necessity to handle
5628 information for two or more blocks concurrently. */
5629 if ((last_insn_was_debug ? was_debug_bb_end_p : sel_bb_end_p (insn))
5630 || (was_stall
5631 && (was_stall >= max_stall
5632 || scheduled_insns >= max_insns)))
5633 break;
5635 while (bnds);
5637 gcc_assert (!FENCE_BNDS (fence));
5639 /* Update boundaries of the FENCE. */
5640 while (bnds)
5642 ilist_t ptr = BND_PTR (BLIST_BND (bnds));
5644 if (ptr)
5646 insn = ILIST_INSN (ptr);
5648 if (!ilist_is_in_p (FENCE_BNDS (fence), insn))
5649 ilist_add (&FENCE_BNDS (fence), insn);
5652 blist_remove (&bnds);
5655 /* Update target context on the fence. */
5656 reset_target_context (FENCE_TC (fence), false);
5659 /* All exprs in ORIG_OPS must have the same destination register or memory.
5660 Return that destination. */
5661 static rtx
5662 get_dest_from_orig_ops (av_set_t orig_ops)
5664 rtx dest = NULL_RTX;
5665 av_set_iterator av_it;
5666 expr_t expr;
5667 bool first_p = true;
5669 FOR_EACH_EXPR (expr, av_it, orig_ops)
5671 rtx x = EXPR_LHS (expr);
5673 if (first_p)
5675 first_p = false;
5676 dest = x;
5678 else
5679 gcc_assert (dest == x
5680 || (dest != NULL_RTX && x != NULL_RTX
5681 && rtx_equal_p (dest, x)));
5684 return dest;
5687 /* Update data sets for the bookkeeping block and record those expressions
5688 which become no longer available after inserting this bookkeeping. */
5689 static void
5690 update_and_record_unavailable_insns (basic_block book_block)
5692 av_set_iterator i;
5693 av_set_t old_av_set = NULL;
5694 expr_t cur_expr;
5695 rtx_insn *bb_end = sel_bb_end (book_block);
5697 /* First, get correct liveness in the bookkeeping block. The problem is
5698 the range between the bookeeping insn and the end of block. */
5699 update_liveness_on_insn (bb_end);
5700 if (control_flow_insn_p (bb_end))
5701 update_liveness_on_insn (PREV_INSN (bb_end));
5703 /* If there's valid av_set on BOOK_BLOCK, then there might exist another
5704 fence above, where we may choose to schedule an insn which is
5705 actually blocked from moving up with the bookkeeping we create here. */
5706 if (AV_SET_VALID_P (sel_bb_head (book_block)))
5708 old_av_set = av_set_copy (BB_AV_SET (book_block));
5709 update_data_sets (sel_bb_head (book_block));
5711 /* Traverse all the expressions in the old av_set and check whether
5712 CUR_EXPR is in new AV_SET. */
5713 FOR_EACH_EXPR (cur_expr, i, old_av_set)
5715 expr_t new_expr = av_set_lookup (BB_AV_SET (book_block),
5716 EXPR_VINSN (cur_expr));
5718 if (! new_expr
5719 /* In this case, we can just turn off the E_T_A bit, but we can't
5720 represent this information with the current vector. */
5721 || EXPR_TARGET_AVAILABLE (new_expr)
5722 != EXPR_TARGET_AVAILABLE (cur_expr))
5723 /* Unfortunately, the below code could be also fired up on
5724 separable insns, e.g. when moving insns through the new
5725 speculation check as in PR 53701. */
5726 vinsn_vec_add (&vec_bookkeeping_blocked_vinsns, cur_expr);
5729 av_set_clear (&old_av_set);
5733 /* The main effect of this function is that sparams->c_expr is merged
5734 with (or copied to) lparams->c_expr_merged. If there's only one successor,
5735 we avoid merging anything by copying sparams->c_expr to lparams->c_expr_merged.
5736 lparams->c_expr_merged is copied back to sparams->c_expr after all
5737 successors has been traversed. lparams->c_expr_local is an expr allocated
5738 on stack in the caller function, and is used if there is more than one
5739 successor.
5741 SUCC is one of the SUCCS_NORMAL successors of INSN,
5742 MOVEOP_DRV_CALL_RES is the result of call code_motion_path_driver on succ,
5743 LPARAMS and STATIC_PARAMS contain the parameters described above. */
5744 static void
5745 move_op_merge_succs (insn_t insn ATTRIBUTE_UNUSED,
5746 insn_t succ ATTRIBUTE_UNUSED,
5747 int moveop_drv_call_res,
5748 cmpd_local_params_p lparams, void *static_params)
5750 moveop_static_params_p sparams = (moveop_static_params_p) static_params;
5752 /* Nothing to do, if original expr wasn't found below. */
5753 if (moveop_drv_call_res != 1)
5754 return;
5756 /* If this is a first successor. */
5757 if (!lparams->c_expr_merged)
5759 lparams->c_expr_merged = sparams->c_expr;
5760 sparams->c_expr = lparams->c_expr_local;
5762 else
5764 /* We must merge all found expressions to get reasonable
5765 EXPR_SPEC_DONE_DS for the resulting insn. If we don't
5766 do so then we can first find the expr with epsilon
5767 speculation success probability and only then with the
5768 good probability. As a result the insn will get epsilon
5769 probability and will never be scheduled because of
5770 weakness_cutoff in find_best_expr.
5772 We call merge_expr_data here instead of merge_expr
5773 because due to speculation C_EXPR and X may have the
5774 same insns with different speculation types. And as of
5775 now such insns are considered non-equal.
5777 However, EXPR_SCHED_TIMES is different -- we must get
5778 SCHED_TIMES from a real insn, not a bookkeeping copy.
5779 We force this here. Instead, we may consider merging
5780 SCHED_TIMES to the maximum instead of minimum in the
5781 below function. */
5782 int old_times = EXPR_SCHED_TIMES (lparams->c_expr_merged);
5784 merge_expr_data (lparams->c_expr_merged, sparams->c_expr, NULL);
5785 if (EXPR_SCHED_TIMES (sparams->c_expr) == 0)
5786 EXPR_SCHED_TIMES (lparams->c_expr_merged) = old_times;
5788 clear_expr (sparams->c_expr);
5792 /* Add used regs for the successor SUCC into SPARAMS->USED_REGS.
5794 SUCC is one of the SUCCS_NORMAL successors of INSN,
5795 MOVEOP_DRV_CALL_RES is the result of call code_motion_path_driver on succ or 0,
5796 if SUCC is one of SUCCS_BACK or SUCCS_OUT.
5797 STATIC_PARAMS contain USED_REGS set. */
5798 static void
5799 fur_merge_succs (insn_t insn ATTRIBUTE_UNUSED, insn_t succ,
5800 int moveop_drv_call_res,
5801 cmpd_local_params_p lparams ATTRIBUTE_UNUSED,
5802 void *static_params)
5804 regset succ_live;
5805 fur_static_params_p sparams = (fur_static_params_p) static_params;
5807 /* Here we compute live regsets only for branches that do not lie
5808 on the code motion paths. These branches correspond to value
5809 MOVEOP_DRV_CALL_RES==0 and include SUCCS_BACK and SUCCS_OUT, though
5810 for such branches code_motion_path_driver is not called. */
5811 if (moveop_drv_call_res != 0)
5812 return;
5814 /* Mark all registers that do not meet the following condition:
5815 (3) not live on the other path of any conditional branch
5816 that is passed by the operation, in case original
5817 operations are not present on both paths of the
5818 conditional branch. */
5819 succ_live = compute_live (succ);
5820 IOR_REG_SET (sparams->used_regs, succ_live);
5823 /* This function is called after the last successor. Copies LP->C_EXPR_MERGED
5824 into SP->CEXPR. */
5825 static void
5826 move_op_after_merge_succs (cmpd_local_params_p lp, void *sparams)
5828 moveop_static_params_p sp = (moveop_static_params_p) sparams;
5830 sp->c_expr = lp->c_expr_merged;
5833 /* Track bookkeeping copies created, insns scheduled, and blocks for
5834 rescheduling when INSN is found by move_op. */
5835 static void
5836 track_scheduled_insns_and_blocks (rtx insn)
5838 /* Even if this insn can be a copy that will be removed during current move_op,
5839 we still need to count it as an originator. */
5840 bitmap_set_bit (current_originators, INSN_UID (insn));
5842 if (!bitmap_clear_bit (current_copies, INSN_UID (insn)))
5844 /* Note that original block needs to be rescheduled, as we pulled an
5845 instruction out of it. */
5846 if (INSN_SCHED_TIMES (insn) > 0)
5847 bitmap_set_bit (blocks_to_reschedule, BLOCK_FOR_INSN (insn)->index);
5848 else if (INSN_UID (insn) < first_emitted_uid && !DEBUG_INSN_P (insn))
5849 num_insns_scheduled++;
5852 /* For instructions we must immediately remove insn from the
5853 stream, so subsequent update_data_sets () won't include this
5854 insn into av_set.
5855 For expr we must make insn look like "INSN_REG (insn) := c_expr". */
5856 if (INSN_UID (insn) > max_uid_before_move_op)
5857 stat_bookkeeping_copies--;
5860 /* Emit a register-register copy for INSN if needed. Return true if
5861 emitted one. PARAMS is the move_op static parameters. */
5862 static bool
5863 maybe_emit_renaming_copy (rtx_insn *insn,
5864 moveop_static_params_p params)
5866 bool insn_emitted = false;
5867 rtx cur_reg;
5869 /* Bail out early when expression can not be renamed at all. */
5870 if (!EXPR_SEPARABLE_P (params->c_expr))
5871 return false;
5873 cur_reg = expr_dest_reg (params->c_expr);
5874 gcc_assert (cur_reg && params->dest && REG_P (params->dest));
5876 /* If original operation has expr and the register chosen for
5877 that expr is not original operation's dest reg, substitute
5878 operation's right hand side with the register chosen. */
5879 if (REGNO (params->dest) != REGNO (cur_reg))
5881 insn_t reg_move_insn, reg_move_insn_rtx;
5883 reg_move_insn_rtx = create_insn_rtx_with_rhs (INSN_VINSN (insn),
5884 params->dest);
5885 reg_move_insn = sel_gen_insn_from_rtx_after (reg_move_insn_rtx,
5886 INSN_EXPR (insn),
5887 INSN_SEQNO (insn),
5888 insn);
5889 EXPR_SPEC_DONE_DS (INSN_EXPR (reg_move_insn)) = 0;
5890 replace_dest_with_reg_in_expr (params->c_expr, params->dest);
5892 insn_emitted = true;
5893 params->was_renamed = true;
5896 return insn_emitted;
5899 /* Emit a speculative check for INSN speculated as EXPR if needed.
5900 Return true if we've emitted one. PARAMS is the move_op static
5901 parameters. */
5902 static bool
5903 maybe_emit_speculative_check (rtx_insn *insn, expr_t expr,
5904 moveop_static_params_p params)
5906 bool insn_emitted = false;
5907 insn_t x;
5908 ds_t check_ds;
5910 check_ds = get_spec_check_type_for_insn (insn, expr);
5911 if (check_ds != 0)
5913 /* A speculation check should be inserted. */
5914 x = create_speculation_check (params->c_expr, check_ds, insn);
5915 insn_emitted = true;
5917 else
5919 EXPR_SPEC_DONE_DS (INSN_EXPR (insn)) = 0;
5920 x = insn;
5923 gcc_assert (EXPR_SPEC_DONE_DS (INSN_EXPR (x)) == 0
5924 && EXPR_SPEC_TO_CHECK_DS (INSN_EXPR (x)) == 0);
5925 return insn_emitted;
5928 /* Handle transformations that leave an insn in place of original
5929 insn such as renaming/speculation. Return true if one of such
5930 transformations actually happened, and we have emitted this insn. */
5931 static bool
5932 handle_emitting_transformations (rtx_insn *insn, expr_t expr,
5933 moveop_static_params_p params)
5935 bool insn_emitted = false;
5937 insn_emitted = maybe_emit_renaming_copy (insn, params);
5938 insn_emitted |= maybe_emit_speculative_check (insn, expr, params);
5940 return insn_emitted;
5943 /* If INSN is the only insn in the basic block (not counting JUMP,
5944 which may be a jump to next insn, and DEBUG_INSNs), we want to
5945 leave a NOP there till the return to fill_insns. */
5947 static bool
5948 need_nop_to_preserve_insn_bb (rtx_insn *insn)
5950 insn_t bb_head, bb_end, bb_next, in_next;
5951 basic_block bb = BLOCK_FOR_INSN (insn);
5953 bb_head = sel_bb_head (bb);
5954 bb_end = sel_bb_end (bb);
5956 if (bb_head == bb_end)
5957 return true;
5959 while (bb_head != bb_end && DEBUG_INSN_P (bb_head))
5960 bb_head = NEXT_INSN (bb_head);
5962 if (bb_head == bb_end)
5963 return true;
5965 while (bb_head != bb_end && DEBUG_INSN_P (bb_end))
5966 bb_end = PREV_INSN (bb_end);
5968 if (bb_head == bb_end)
5969 return true;
5971 bb_next = NEXT_INSN (bb_head);
5972 while (bb_next != bb_end && DEBUG_INSN_P (bb_next))
5973 bb_next = NEXT_INSN (bb_next);
5975 if (bb_next == bb_end && JUMP_P (bb_end))
5976 return true;
5978 in_next = NEXT_INSN (insn);
5979 while (DEBUG_INSN_P (in_next))
5980 in_next = NEXT_INSN (in_next);
5982 if (IN_CURRENT_FENCE_P (in_next))
5983 return true;
5985 return false;
5988 /* Remove INSN from stream. When ONLY_DISCONNECT is true, its data
5989 is not removed but reused when INSN is re-emitted. */
5990 static void
5991 remove_insn_from_stream (rtx_insn *insn, bool only_disconnect)
5993 /* If there's only one insn in the BB, make sure that a nop is
5994 inserted into it, so the basic block won't disappear when we'll
5995 delete INSN below with sel_remove_insn. It should also survive
5996 till the return to fill_insns. */
5997 if (need_nop_to_preserve_insn_bb (insn))
5999 insn_t nop = get_nop_from_pool (insn);
6000 gcc_assert (INSN_NOP_P (nop));
6001 vec_temp_moveop_nops.safe_push (nop);
6004 sel_remove_insn (insn, only_disconnect, false);
6007 /* This function is called when original expr is found.
6008 INSN - current insn traversed, EXPR - the corresponding expr found.
6009 LPARAMS is the local parameters of code modion driver, STATIC_PARAMS
6010 is static parameters of move_op. */
6011 static void
6012 move_op_orig_expr_found (insn_t insn, expr_t expr,
6013 cmpd_local_params_p lparams ATTRIBUTE_UNUSED,
6014 void *static_params)
6016 bool only_disconnect;
6017 moveop_static_params_p params = (moveop_static_params_p) static_params;
6019 copy_expr_onside (params->c_expr, INSN_EXPR (insn));
6020 track_scheduled_insns_and_blocks (insn);
6021 handle_emitting_transformations (insn, expr, params);
6022 only_disconnect = params->uid == INSN_UID (insn);
6024 /* Mark that we've disconnected an insn. */
6025 if (only_disconnect)
6026 params->uid = -1;
6027 remove_insn_from_stream (insn, only_disconnect);
6030 /* The function is called when original expr is found.
6031 INSN - current insn traversed, EXPR - the corresponding expr found,
6032 crosses_call and original_insns in STATIC_PARAMS are updated. */
6033 static void
6034 fur_orig_expr_found (insn_t insn, expr_t expr ATTRIBUTE_UNUSED,
6035 cmpd_local_params_p lparams ATTRIBUTE_UNUSED,
6036 void *static_params)
6038 fur_static_params_p params = (fur_static_params_p) static_params;
6039 regset tmp;
6041 if (CALL_P (insn))
6042 params->crosses_call = true;
6044 def_list_add (params->original_insns, insn, params->crosses_call);
6046 /* Mark the registers that do not meet the following condition:
6047 (2) not among the live registers of the point
6048 immediately following the first original operation on
6049 a given downward path, except for the original target
6050 register of the operation. */
6051 tmp = get_clear_regset_from_pool ();
6052 compute_live_below_insn (insn, tmp);
6053 AND_COMPL_REG_SET (tmp, INSN_REG_SETS (insn));
6054 AND_COMPL_REG_SET (tmp, INSN_REG_CLOBBERS (insn));
6055 IOR_REG_SET (params->used_regs, tmp);
6056 return_regset_to_pool (tmp);
6058 /* (*1) We need to add to USED_REGS registers that are read by
6059 INSN's lhs. This may lead to choosing wrong src register.
6060 E.g. (scheduling const expr enabled):
6062 429: ax=0x0 <- Can't use AX for this expr (0x0)
6063 433: dx=[bp-0x18]
6064 427: [ax+dx+0x1]=ax
6065 REG_DEAD: ax
6066 168: di=dx
6067 REG_DEAD: dx
6069 /* FIXME: see comment above and enable MEM_P
6070 in vinsn_separable_p. */
6071 gcc_assert (!VINSN_SEPARABLE_P (INSN_VINSN (insn))
6072 || !MEM_P (INSN_LHS (insn)));
6075 /* This function is called on the ascending pass, before returning from
6076 current basic block. */
6077 static void
6078 move_op_at_first_insn (insn_t insn, cmpd_local_params_p lparams,
6079 void *static_params)
6081 moveop_static_params_p sparams = (moveop_static_params_p) static_params;
6082 basic_block book_block = NULL;
6084 /* When we have removed the boundary insn for scheduling, which also
6085 happened to be the end insn in its bb, we don't need to update sets. */
6086 if (!lparams->removed_last_insn
6087 && lparams->e1
6088 && sel_bb_head_p (insn))
6090 /* We should generate bookkeeping code only if we are not at the
6091 top level of the move_op. */
6092 if (sel_num_cfg_preds_gt_1 (insn))
6093 book_block = generate_bookkeeping_insn (sparams->c_expr,
6094 lparams->e1, lparams->e2);
6095 /* Update data sets for the current insn. */
6096 update_data_sets (insn);
6099 /* If bookkeeping code was inserted, we need to update av sets of basic
6100 block that received bookkeeping. After generation of bookkeeping insn,
6101 bookkeeping block does not contain valid av set because we are not following
6102 the original algorithm in every detail with regards to e.g. renaming
6103 simple reg-reg copies. Consider example:
6105 bookkeeping block scheduling fence
6107 \ join /
6108 ----------
6110 ----------
6113 r1 := r2 r1 := r3
6115 We try to schedule insn "r1 := r3" on the current
6116 scheduling fence. Also, note that av set of bookkeeping block
6117 contain both insns "r1 := r2" and "r1 := r3". When the insn has
6118 been scheduled, the CFG is as follows:
6120 r1 := r3 r1 := r3
6121 bookkeeping block scheduling fence
6123 \ join /
6124 ----------
6126 ----------
6129 r1 := r2
6131 Here, insn "r1 := r3" was scheduled at the current scheduling point
6132 and bookkeeping code was generated at the bookeeping block. This
6133 way insn "r1 := r2" is no longer available as a whole instruction
6134 (but only as expr) ahead of insn "r1 := r3" in bookkeeping block.
6135 This situation is handled by calling update_data_sets.
6137 Since update_data_sets is called only on the bookkeeping block, and
6138 it also may have predecessors with av_sets, containing instructions that
6139 are no longer available, we save all such expressions that become
6140 unavailable during data sets update on the bookkeeping block in
6141 VEC_BOOKKEEPING_BLOCKED_VINSNS. Later we avoid selecting such
6142 expressions for scheduling. This allows us to avoid recomputation of
6143 av_sets outside the code motion path. */
6145 if (book_block)
6146 update_and_record_unavailable_insns (book_block);
6148 /* If INSN was previously marked for deletion, it's time to do it. */
6149 if (lparams->removed_last_insn)
6150 insn = PREV_INSN (insn);
6152 /* Do not tidy control flow at the topmost moveop, as we can erroneously
6153 kill a block with a single nop in which the insn should be emitted. */
6154 if (lparams->e1)
6155 tidy_control_flow (BLOCK_FOR_INSN (insn), true);
6158 /* This function is called on the ascending pass, before returning from the
6159 current basic block. */
6160 static void
6161 fur_at_first_insn (insn_t insn,
6162 cmpd_local_params_p lparams ATTRIBUTE_UNUSED,
6163 void *static_params ATTRIBUTE_UNUSED)
6165 gcc_assert (!sel_bb_head_p (insn) || AV_SET_VALID_P (insn)
6166 || AV_LEVEL (insn) == -1);
6169 /* Called on the backward stage of recursion to call moveup_expr for insn
6170 and sparams->c_expr. */
6171 static void
6172 move_op_ascend (insn_t insn, void *static_params)
6174 enum MOVEUP_EXPR_CODE res;
6175 moveop_static_params_p sparams = (moveop_static_params_p) static_params;
6177 if (! INSN_NOP_P (insn))
6179 res = moveup_expr_cached (sparams->c_expr, insn, false);
6180 gcc_assert (res != MOVEUP_EXPR_NULL);
6183 /* Update liveness for this insn as it was invalidated. */
6184 update_liveness_on_insn (insn);
6187 /* This function is called on enter to the basic block.
6188 Returns TRUE if this block already have been visited and
6189 code_motion_path_driver should return 1, FALSE otherwise. */
6190 static int
6191 fur_on_enter (insn_t insn ATTRIBUTE_UNUSED, cmpd_local_params_p local_params,
6192 void *static_params, bool visited_p)
6194 fur_static_params_p sparams = (fur_static_params_p) static_params;
6196 if (visited_p)
6198 /* If we have found something below this block, there should be at
6199 least one insn in ORIGINAL_INSNS. */
6200 gcc_assert (*sparams->original_insns);
6202 /* Adjust CROSSES_CALL, since we may have come to this block along
6203 different path. */
6204 DEF_LIST_DEF (*sparams->original_insns)->crosses_call
6205 |= sparams->crosses_call;
6207 else
6208 local_params->old_original_insns = *sparams->original_insns;
6210 return 1;
6213 /* Same as above but for move_op. */
6214 static int
6215 move_op_on_enter (insn_t insn ATTRIBUTE_UNUSED,
6216 cmpd_local_params_p local_params ATTRIBUTE_UNUSED,
6217 void *static_params ATTRIBUTE_UNUSED, bool visited_p)
6219 if (visited_p)
6220 return -1;
6221 return 1;
6224 /* This function is called while descending current basic block if current
6225 insn is not the original EXPR we're searching for.
6227 Return value: FALSE, if code_motion_path_driver should perform a local
6228 cleanup and return 0 itself;
6229 TRUE, if code_motion_path_driver should continue. */
6230 static bool
6231 move_op_orig_expr_not_found (insn_t insn, av_set_t orig_ops ATTRIBUTE_UNUSED,
6232 void *static_params)
6234 moveop_static_params_p sparams = (moveop_static_params_p) static_params;
6236 #ifdef ENABLE_CHECKING
6237 sparams->failed_insn = insn;
6238 #endif
6240 /* If we're scheduling separate expr, in order to generate correct code
6241 we need to stop the search at bookkeeping code generated with the
6242 same destination register or memory. */
6243 if (lhs_of_insn_equals_to_dest_p (insn, sparams->dest))
6244 return false;
6245 return true;
6248 /* This function is called while descending current basic block if current
6249 insn is not the original EXPR we're searching for.
6251 Return value: TRUE (code_motion_path_driver should continue). */
6252 static bool
6253 fur_orig_expr_not_found (insn_t insn, av_set_t orig_ops, void *static_params)
6255 bool mutexed;
6256 expr_t r;
6257 av_set_iterator avi;
6258 fur_static_params_p sparams = (fur_static_params_p) static_params;
6260 if (CALL_P (insn))
6261 sparams->crosses_call = true;
6262 else if (DEBUG_INSN_P (insn))
6263 return true;
6265 /* If current insn we are looking at cannot be executed together
6266 with original insn, then we can skip it safely.
6268 Example: ORIG_OPS = { (p6) r14 = sign_extend (r15); }
6269 INSN = (!p6) r14 = r14 + 1;
6271 Here we can schedule ORIG_OP with lhs = r14, though only
6272 looking at the set of used and set registers of INSN we must
6273 forbid it. So, add set/used in INSN registers to the
6274 untouchable set only if there is an insn in ORIG_OPS that can
6275 affect INSN. */
6276 mutexed = true;
6277 FOR_EACH_EXPR (r, avi, orig_ops)
6278 if (!sched_insns_conditions_mutex_p (insn, EXPR_INSN_RTX (r)))
6280 mutexed = false;
6281 break;
6284 /* Mark all registers that do not meet the following condition:
6285 (1) Not set or read on any path from xi to an instance of the
6286 original operation. */
6287 if (!mutexed)
6289 IOR_REG_SET (sparams->used_regs, INSN_REG_SETS (insn));
6290 IOR_REG_SET (sparams->used_regs, INSN_REG_USES (insn));
6291 IOR_REG_SET (sparams->used_regs, INSN_REG_CLOBBERS (insn));
6294 return true;
6297 /* Hooks and data to perform move_op operations with code_motion_path_driver. */
6298 struct code_motion_path_driver_info_def move_op_hooks = {
6299 move_op_on_enter,
6300 move_op_orig_expr_found,
6301 move_op_orig_expr_not_found,
6302 move_op_merge_succs,
6303 move_op_after_merge_succs,
6304 move_op_ascend,
6305 move_op_at_first_insn,
6306 SUCCS_NORMAL,
6307 "move_op"
6310 /* Hooks and data to perform find_used_regs operations
6311 with code_motion_path_driver. */
6312 struct code_motion_path_driver_info_def fur_hooks = {
6313 fur_on_enter,
6314 fur_orig_expr_found,
6315 fur_orig_expr_not_found,
6316 fur_merge_succs,
6317 NULL, /* fur_after_merge_succs */
6318 NULL, /* fur_ascend */
6319 fur_at_first_insn,
6320 SUCCS_ALL,
6321 "find_used_regs"
6324 /* Traverse all successors of INSN. For each successor that is SUCCS_NORMAL
6325 code_motion_path_driver is called recursively. Original operation
6326 was found at least on one path that is starting with one of INSN's
6327 successors (this fact is asserted). ORIG_OPS is expressions we're looking
6328 for, PATH is the path we've traversed, STATIC_PARAMS is the parameters
6329 of either move_op or find_used_regs depending on the caller.
6331 Return 0 if we haven't found expression, 1 if we found it, -1 if we don't
6332 know for sure at this point. */
6333 static int
6334 code_motion_process_successors (insn_t insn, av_set_t orig_ops,
6335 ilist_t path, void *static_params)
6337 int res = 0;
6338 succ_iterator succ_i;
6339 insn_t succ;
6340 basic_block bb;
6341 int old_index;
6342 unsigned old_succs;
6344 struct cmpd_local_params lparams;
6345 expr_def _x;
6347 lparams.c_expr_local = &_x;
6348 lparams.c_expr_merged = NULL;
6350 /* We need to process only NORMAL succs for move_op, and collect live
6351 registers from ALL branches (including those leading out of the
6352 region) for find_used_regs.
6354 In move_op, there can be a case when insn's bb number has changed
6355 due to created bookkeeping. This happens very rare, as we need to
6356 move expression from the beginning to the end of the same block.
6357 Rescan successors in this case. */
6359 rescan:
6360 bb = BLOCK_FOR_INSN (insn);
6361 old_index = bb->index;
6362 old_succs = EDGE_COUNT (bb->succs);
6364 FOR_EACH_SUCC_1 (succ, succ_i, insn, code_motion_path_driver_info->succ_flags)
6366 int b;
6368 lparams.e1 = succ_i.e1;
6369 lparams.e2 = succ_i.e2;
6371 /* Go deep into recursion only for NORMAL edges (non-backedges within the
6372 current region). */
6373 if (succ_i.current_flags == SUCCS_NORMAL)
6374 b = code_motion_path_driver (succ, orig_ops, path, &lparams,
6375 static_params);
6376 else
6377 b = 0;
6379 /* Merge c_expres found or unify live register sets from different
6380 successors. */
6381 code_motion_path_driver_info->merge_succs (insn, succ, b, &lparams,
6382 static_params);
6383 if (b == 1)
6384 res = b;
6385 else if (b == -1 && res != 1)
6386 res = b;
6388 /* We have simplified the control flow below this point. In this case,
6389 the iterator becomes invalid. We need to try again.
6390 If we have removed the insn itself, it could be only an
6391 unconditional jump. Thus, do not rescan but break immediately --
6392 we have already visited the only successor block. */
6393 if (!BLOCK_FOR_INSN (insn))
6395 if (sched_verbose >= 6)
6396 sel_print ("Not doing rescan: already visited the only successor"
6397 " of block %d\n", old_index);
6398 break;
6400 if (BLOCK_FOR_INSN (insn)->index != old_index
6401 || EDGE_COUNT (bb->succs) != old_succs)
6403 if (sched_verbose >= 6)
6404 sel_print ("Rescan: CFG was simplified below insn %d, block %d\n",
6405 INSN_UID (insn), BLOCK_FOR_INSN (insn)->index);
6406 insn = sel_bb_end (BLOCK_FOR_INSN (insn));
6407 goto rescan;
6411 #ifdef ENABLE_CHECKING
6412 /* Here, RES==1 if original expr was found at least for one of the
6413 successors. After the loop, RES may happen to have zero value
6414 only if at some point the expr searched is present in av_set, but is
6415 not found below. In most cases, this situation is an error.
6416 The exception is when the original operation is blocked by
6417 bookkeeping generated for another fence or for another path in current
6418 move_op. */
6419 gcc_assert (res == 1
6420 || (res == 0
6421 && av_set_could_be_blocked_by_bookkeeping_p (orig_ops,
6422 static_params))
6423 || res == -1);
6424 #endif
6426 /* Merge data, clean up, etc. */
6427 if (res != -1 && code_motion_path_driver_info->after_merge_succs)
6428 code_motion_path_driver_info->after_merge_succs (&lparams, static_params);
6430 return res;
6434 /* Perform a cleanup when the driver is about to terminate. ORIG_OPS_P
6435 is the pointer to the av set with expressions we were looking for,
6436 PATH_P is the pointer to the traversed path. */
6437 static inline void
6438 code_motion_path_driver_cleanup (av_set_t *orig_ops_p, ilist_t *path_p)
6440 ilist_remove (path_p);
6441 av_set_clear (orig_ops_p);
6444 /* The driver function that implements move_op or find_used_regs
6445 functionality dependent whether code_motion_path_driver_INFO is set to
6446 &MOVE_OP_HOOKS or &FUR_HOOKS. This function implements the common parts
6447 of code (CFG traversal etc) that are shared among both functions. INSN
6448 is the insn we're starting the search from, ORIG_OPS are the expressions
6449 we're searching for, PATH is traversed path, LOCAL_PARAMS_IN are local
6450 parameters of the driver, and STATIC_PARAMS are static parameters of
6451 the caller.
6453 Returns whether original instructions were found. Note that top-level
6454 code_motion_path_driver always returns true. */
6455 static int
6456 code_motion_path_driver (insn_t insn, av_set_t orig_ops, ilist_t path,
6457 cmpd_local_params_p local_params_in,
6458 void *static_params)
6460 expr_t expr = NULL;
6461 basic_block bb = BLOCK_FOR_INSN (insn);
6462 insn_t first_insn, bb_tail, before_first;
6463 bool removed_last_insn = false;
6465 if (sched_verbose >= 6)
6467 sel_print ("%s (", code_motion_path_driver_info->routine_name);
6468 dump_insn (insn);
6469 sel_print (",");
6470 dump_av_set (orig_ops);
6471 sel_print (")\n");
6474 gcc_assert (orig_ops);
6476 /* If no original operations exist below this insn, return immediately. */
6477 if (is_ineligible_successor (insn, path))
6479 if (sched_verbose >= 6)
6480 sel_print ("Insn %d is ineligible successor\n", INSN_UID (insn));
6481 return false;
6484 /* The block can have invalid av set, in which case it was created earlier
6485 during move_op. Return immediately. */
6486 if (sel_bb_head_p (insn))
6488 if (! AV_SET_VALID_P (insn))
6490 if (sched_verbose >= 6)
6491 sel_print ("Returned from block %d as it had invalid av set\n",
6492 bb->index);
6493 return false;
6496 if (bitmap_bit_p (code_motion_visited_blocks, bb->index))
6498 /* We have already found an original operation on this branch, do not
6499 go any further and just return TRUE here. If we don't stop here,
6500 function can have exponential behaviour even on the small code
6501 with many different paths (e.g. with data speculation and
6502 recovery blocks). */
6503 if (sched_verbose >= 6)
6504 sel_print ("Block %d already visited in this traversal\n", bb->index);
6505 if (code_motion_path_driver_info->on_enter)
6506 return code_motion_path_driver_info->on_enter (insn,
6507 local_params_in,
6508 static_params,
6509 true);
6513 if (code_motion_path_driver_info->on_enter)
6514 code_motion_path_driver_info->on_enter (insn, local_params_in,
6515 static_params, false);
6516 orig_ops = av_set_copy (orig_ops);
6518 /* Filter the orig_ops set. */
6519 if (AV_SET_VALID_P (insn))
6520 av_set_code_motion_filter (&orig_ops, AV_SET (insn));
6522 /* If no more original ops, return immediately. */
6523 if (!orig_ops)
6525 if (sched_verbose >= 6)
6526 sel_print ("No intersection with av set of block %d\n", bb->index);
6527 return false;
6530 /* For non-speculative insns we have to leave only one form of the
6531 original operation, because if we don't, we may end up with
6532 different C_EXPRes and, consequently, with bookkeepings for different
6533 expression forms along the same code motion path. That may lead to
6534 generation of incorrect code. So for each code motion we stick to
6535 the single form of the instruction, except for speculative insns
6536 which we need to keep in different forms with all speculation
6537 types. */
6538 av_set_leave_one_nonspec (&orig_ops);
6540 /* It is not possible that all ORIG_OPS are filtered out. */
6541 gcc_assert (orig_ops);
6543 /* It is enough to place only heads and tails of visited basic blocks into
6544 the PATH. */
6545 ilist_add (&path, insn);
6546 first_insn = insn;
6547 bb_tail = sel_bb_end (bb);
6549 /* Descend the basic block in search of the original expr; this part
6550 corresponds to the part of the original move_op procedure executed
6551 before the recursive call. */
6552 for (;;)
6554 /* Look at the insn and decide if it could be an ancestor of currently
6555 scheduling operation. If it is so, then the insn "dest = op" could
6556 either be replaced with "dest = reg", because REG now holds the result
6557 of OP, or just removed, if we've scheduled the insn as a whole.
6559 If this insn doesn't contain currently scheduling OP, then proceed
6560 with searching and look at its successors. Operations we're searching
6561 for could have changed when moving up through this insn via
6562 substituting. In this case, perform unsubstitution on them first.
6564 When traversing the DAG below this insn is finished, insert
6565 bookkeeping code, if the insn is a joint point, and remove
6566 leftovers. */
6568 expr = av_set_lookup (orig_ops, INSN_VINSN (insn));
6569 if (expr)
6571 insn_t last_insn = PREV_INSN (insn);
6573 /* We have found the original operation. */
6574 if (sched_verbose >= 6)
6575 sel_print ("Found original operation at insn %d\n", INSN_UID (insn));
6577 code_motion_path_driver_info->orig_expr_found
6578 (insn, expr, local_params_in, static_params);
6580 /* Step back, so on the way back we'll start traversing from the
6581 previous insn (or we'll see that it's bb_note and skip that
6582 loop). */
6583 if (insn == first_insn)
6585 first_insn = NEXT_INSN (last_insn);
6586 removed_last_insn = sel_bb_end_p (last_insn);
6588 insn = last_insn;
6589 break;
6591 else
6593 /* We haven't found the original expr, continue descending the basic
6594 block. */
6595 if (code_motion_path_driver_info->orig_expr_not_found
6596 (insn, orig_ops, static_params))
6598 /* Av set ops could have been changed when moving through this
6599 insn. To find them below it, we have to un-substitute them. */
6600 undo_transformations (&orig_ops, insn);
6602 else
6604 /* Clean up and return, if the hook tells us to do so. It may
6605 happen if we've encountered the previously created
6606 bookkeeping. */
6607 code_motion_path_driver_cleanup (&orig_ops, &path);
6608 return -1;
6611 gcc_assert (orig_ops);
6614 /* Stop at insn if we got to the end of BB. */
6615 if (insn == bb_tail)
6616 break;
6618 insn = NEXT_INSN (insn);
6621 /* Here INSN either points to the insn before the original insn (may be
6622 bb_note, if original insn was a bb_head) or to the bb_end. */
6623 if (!expr)
6625 int res;
6626 rtx_insn *last_insn = PREV_INSN (insn);
6627 bool added_to_path;
6629 gcc_assert (insn == sel_bb_end (bb));
6631 /* Add bb tail to PATH (but it doesn't make any sense if it's a bb_head -
6632 it's already in PATH then). */
6633 if (insn != first_insn)
6635 ilist_add (&path, insn);
6636 added_to_path = true;
6638 else
6639 added_to_path = false;
6641 /* Process_successors should be able to find at least one
6642 successor for which code_motion_path_driver returns TRUE. */
6643 res = code_motion_process_successors (insn, orig_ops,
6644 path, static_params);
6646 /* Jump in the end of basic block could have been removed or replaced
6647 during code_motion_process_successors, so recompute insn as the
6648 last insn in bb. */
6649 if (NEXT_INSN (last_insn) != insn)
6651 insn = sel_bb_end (bb);
6652 first_insn = sel_bb_head (bb);
6655 /* Remove bb tail from path. */
6656 if (added_to_path)
6657 ilist_remove (&path);
6659 if (res != 1)
6661 /* This is the case when one of the original expr is no longer available
6662 due to bookkeeping created on this branch with the same register.
6663 In the original algorithm, which doesn't have update_data_sets call
6664 on a bookkeeping block, it would simply result in returning
6665 FALSE when we've encountered a previously generated bookkeeping
6666 insn in moveop_orig_expr_not_found. */
6667 code_motion_path_driver_cleanup (&orig_ops, &path);
6668 return res;
6672 /* Don't need it any more. */
6673 av_set_clear (&orig_ops);
6675 /* Backward pass: now, when we have C_EXPR computed, we'll drag it to
6676 the beginning of the basic block. */
6677 before_first = PREV_INSN (first_insn);
6678 while (insn != before_first)
6680 if (code_motion_path_driver_info->ascend)
6681 code_motion_path_driver_info->ascend (insn, static_params);
6683 insn = PREV_INSN (insn);
6686 /* Now we're at the bb head. */
6687 insn = first_insn;
6688 ilist_remove (&path);
6689 local_params_in->removed_last_insn = removed_last_insn;
6690 code_motion_path_driver_info->at_first_insn (insn, local_params_in, static_params);
6692 /* This should be the very last operation as at bb head we could change
6693 the numbering by creating bookkeeping blocks. */
6694 if (removed_last_insn)
6695 insn = PREV_INSN (insn);
6697 /* If we have simplified the control flow and removed the first jump insn,
6698 there's no point in marking this block in the visited blocks bitmap. */
6699 if (BLOCK_FOR_INSN (insn))
6700 bitmap_set_bit (code_motion_visited_blocks, BLOCK_FOR_INSN (insn)->index);
6701 return true;
6704 /* Move up the operations from ORIG_OPS set traversing the dag starting
6705 from INSN. PATH represents the edges traversed so far.
6706 DEST is the register chosen for scheduling the current expr. Insert
6707 bookkeeping code in the join points. EXPR_VLIW is the chosen expression,
6708 C_EXPR is how it looks like at the given cfg point.
6709 Set *SHOULD_MOVE to indicate whether we have only disconnected
6710 one of the insns found.
6712 Returns whether original instructions were found, which is asserted
6713 to be true in the caller. */
6714 static bool
6715 move_op (insn_t insn, av_set_t orig_ops, expr_t expr_vliw,
6716 rtx dest, expr_t c_expr, bool *should_move)
6718 struct moveop_static_params sparams;
6719 struct cmpd_local_params lparams;
6720 int res;
6722 /* Init params for code_motion_path_driver. */
6723 sparams.dest = dest;
6724 sparams.c_expr = c_expr;
6725 sparams.uid = INSN_UID (EXPR_INSN_RTX (expr_vliw));
6726 #ifdef ENABLE_CHECKING
6727 sparams.failed_insn = NULL;
6728 #endif
6729 sparams.was_renamed = false;
6730 lparams.e1 = NULL;
6732 /* We haven't visited any blocks yet. */
6733 bitmap_clear (code_motion_visited_blocks);
6735 /* Set appropriate hooks and data. */
6736 code_motion_path_driver_info = &move_op_hooks;
6737 res = code_motion_path_driver (insn, orig_ops, NULL, &lparams, &sparams);
6739 gcc_assert (res != -1);
6741 if (sparams.was_renamed)
6742 EXPR_WAS_RENAMED (expr_vliw) = true;
6744 *should_move = (sparams.uid == -1);
6746 return res;
6750 /* Functions that work with regions. */
6752 /* Current number of seqno used in init_seqno and init_seqno_1. */
6753 static int cur_seqno;
6755 /* A helper for init_seqno. Traverse the region starting from BB and
6756 compute seqnos for visited insns, marking visited bbs in VISITED_BBS.
6757 Clear visited blocks from BLOCKS_TO_RESCHEDULE. */
6758 static void
6759 init_seqno_1 (basic_block bb, sbitmap visited_bbs, bitmap blocks_to_reschedule)
6761 int bbi = BLOCK_TO_BB (bb->index);
6762 insn_t insn, note = bb_note (bb);
6763 insn_t succ_insn;
6764 succ_iterator si;
6766 bitmap_set_bit (visited_bbs, bbi);
6767 if (blocks_to_reschedule)
6768 bitmap_clear_bit (blocks_to_reschedule, bb->index);
6770 FOR_EACH_SUCC_1 (succ_insn, si, BB_END (bb),
6771 SUCCS_NORMAL | SUCCS_SKIP_TO_LOOP_EXITS)
6773 basic_block succ = BLOCK_FOR_INSN (succ_insn);
6774 int succ_bbi = BLOCK_TO_BB (succ->index);
6776 gcc_assert (in_current_region_p (succ));
6778 if (!bitmap_bit_p (visited_bbs, succ_bbi))
6780 gcc_assert (succ_bbi > bbi);
6782 init_seqno_1 (succ, visited_bbs, blocks_to_reschedule);
6784 else if (blocks_to_reschedule)
6785 bitmap_set_bit (forced_ebb_heads, succ->index);
6788 for (insn = BB_END (bb); insn != note; insn = PREV_INSN (insn))
6789 INSN_SEQNO (insn) = cur_seqno--;
6792 /* Initialize seqnos for the current region. BLOCKS_TO_RESCHEDULE contains
6793 blocks on which we're rescheduling when pipelining, FROM is the block where
6794 traversing region begins (it may not be the head of the region when
6795 pipelining, but the head of the loop instead).
6797 Returns the maximal seqno found. */
6798 static int
6799 init_seqno (bitmap blocks_to_reschedule, basic_block from)
6801 sbitmap visited_bbs;
6802 bitmap_iterator bi;
6803 unsigned bbi;
6805 visited_bbs = sbitmap_alloc (current_nr_blocks);
6807 if (blocks_to_reschedule)
6809 bitmap_ones (visited_bbs);
6810 EXECUTE_IF_SET_IN_BITMAP (blocks_to_reschedule, 0, bbi, bi)
6812 gcc_assert (BLOCK_TO_BB (bbi) < current_nr_blocks);
6813 bitmap_clear_bit (visited_bbs, BLOCK_TO_BB (bbi));
6816 else
6818 bitmap_clear (visited_bbs);
6819 from = EBB_FIRST_BB (0);
6822 cur_seqno = sched_max_luid - 1;
6823 init_seqno_1 (from, visited_bbs, blocks_to_reschedule);
6825 /* cur_seqno may be positive if the number of instructions is less than
6826 sched_max_luid - 1 (when rescheduling or if some instructions have been
6827 removed by the call to purge_empty_blocks in sel_sched_region_1). */
6828 gcc_assert (cur_seqno >= 0);
6830 sbitmap_free (visited_bbs);
6831 return sched_max_luid - 1;
6834 /* Initialize scheduling parameters for current region. */
6835 static void
6836 sel_setup_region_sched_flags (void)
6838 enable_schedule_as_rhs_p = 1;
6839 bookkeeping_p = 1;
6840 pipelining_p = (bookkeeping_p
6841 && (flag_sel_sched_pipelining != 0)
6842 && current_loop_nest != NULL
6843 && loop_has_exit_edges (current_loop_nest));
6844 max_insns_to_rename = PARAM_VALUE (PARAM_SELSCHED_INSNS_TO_RENAME);
6845 max_ws = MAX_WS;
6848 /* Return true if all basic blocks of current region are empty. */
6849 static bool
6850 current_region_empty_p (void)
6852 int i;
6853 for (i = 0; i < current_nr_blocks; i++)
6854 if (! sel_bb_empty_p (BASIC_BLOCK_FOR_FN (cfun, BB_TO_BLOCK (i))))
6855 return false;
6857 return true;
6860 /* Prepare and verify loop nest for pipelining. */
6861 static void
6862 setup_current_loop_nest (int rgn, bb_vec_t *bbs)
6864 current_loop_nest = get_loop_nest_for_rgn (rgn);
6866 if (!current_loop_nest)
6867 return;
6869 /* If this loop has any saved loop preheaders from nested loops,
6870 add these basic blocks to the current region. */
6871 sel_add_loop_preheaders (bbs);
6873 /* Check that we're starting with a valid information. */
6874 gcc_assert (loop_latch_edge (current_loop_nest));
6875 gcc_assert (LOOP_MARKED_FOR_PIPELINING_P (current_loop_nest));
6878 /* Compute instruction priorities for current region. */
6879 static void
6880 sel_compute_priorities (int rgn)
6882 sched_rgn_compute_dependencies (rgn);
6884 /* Compute insn priorities in haifa style. Then free haifa style
6885 dependencies that we've calculated for this. */
6886 compute_priorities ();
6888 if (sched_verbose >= 5)
6889 debug_rgn_dependencies (0);
6891 free_rgn_deps ();
6894 /* Init scheduling data for RGN. Returns true when this region should not
6895 be scheduled. */
6896 static bool
6897 sel_region_init (int rgn)
6899 int i;
6900 bb_vec_t bbs;
6902 rgn_setup_region (rgn);
6904 /* Even if sched_is_disabled_for_current_region_p() is true, we still
6905 do region initialization here so the region can be bundled correctly,
6906 but we'll skip the scheduling in sel_sched_region (). */
6907 if (current_region_empty_p ())
6908 return true;
6910 bbs.create (current_nr_blocks);
6912 for (i = 0; i < current_nr_blocks; i++)
6913 bbs.quick_push (BASIC_BLOCK_FOR_FN (cfun, BB_TO_BLOCK (i)));
6915 sel_init_bbs (bbs);
6917 if (flag_sel_sched_pipelining)
6918 setup_current_loop_nest (rgn, &bbs);
6920 sel_setup_region_sched_flags ();
6922 /* Initialize luids and dependence analysis which both sel-sched and haifa
6923 need. */
6924 sched_init_luids (bbs);
6925 sched_deps_init (false);
6927 /* Initialize haifa data. */
6928 rgn_setup_sched_infos ();
6929 sel_set_sched_flags ();
6930 haifa_init_h_i_d (bbs);
6932 sel_compute_priorities (rgn);
6933 init_deps_global ();
6935 /* Main initialization. */
6936 sel_setup_sched_infos ();
6937 sel_init_global_and_expr (bbs);
6939 bbs.release ();
6941 blocks_to_reschedule = BITMAP_ALLOC (NULL);
6943 /* Init correct liveness sets on each instruction of a single-block loop.
6944 This is the only situation when we can't update liveness when calling
6945 compute_live for the first insn of the loop. */
6946 if (current_loop_nest)
6948 int header =
6949 (sel_is_loop_preheader_p (BASIC_BLOCK_FOR_FN (cfun, BB_TO_BLOCK (0)))
6951 : 0);
6953 if (current_nr_blocks == header + 1)
6954 update_liveness_on_insn
6955 (sel_bb_head (BASIC_BLOCK_FOR_FN (cfun, BB_TO_BLOCK (header))));
6958 /* Set hooks so that no newly generated insn will go out unnoticed. */
6959 sel_register_cfg_hooks ();
6961 /* !!! We call target.sched.init () for the whole region, but we invoke
6962 targetm.sched.finish () for every ebb. */
6963 if (targetm.sched.init)
6964 /* None of the arguments are actually used in any target. */
6965 targetm.sched.init (sched_dump, sched_verbose, -1);
6967 first_emitted_uid = get_max_uid () + 1;
6968 preheader_removed = false;
6970 /* Reset register allocation ticks array. */
6971 memset (reg_rename_tick, 0, sizeof reg_rename_tick);
6972 reg_rename_this_tick = 0;
6974 bitmap_initialize (forced_ebb_heads, 0);
6975 bitmap_clear (forced_ebb_heads);
6977 setup_nop_vinsn ();
6978 current_copies = BITMAP_ALLOC (NULL);
6979 current_originators = BITMAP_ALLOC (NULL);
6980 code_motion_visited_blocks = BITMAP_ALLOC (NULL);
6982 return false;
6985 /* Simplify insns after the scheduling. */
6986 static void
6987 simplify_changed_insns (void)
6989 int i;
6991 for (i = 0; i < current_nr_blocks; i++)
6993 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, BB_TO_BLOCK (i));
6994 rtx_insn *insn;
6996 FOR_BB_INSNS (bb, insn)
6997 if (INSN_P (insn))
6999 expr_t expr = INSN_EXPR (insn);
7001 if (EXPR_WAS_SUBSTITUTED (expr))
7002 validate_simplify_insn (insn);
7007 /* Find boundaries of the EBB starting from basic block BB, marking blocks of
7008 this EBB in SCHEDULED_BLOCKS and appropriately filling in HEAD, TAIL,
7009 PREV_HEAD, and NEXT_TAIL fields of CURRENT_SCHED_INFO structure. */
7010 static void
7011 find_ebb_boundaries (basic_block bb, bitmap scheduled_blocks)
7013 rtx_insn *head, *tail;
7014 basic_block bb1 = bb;
7015 if (sched_verbose >= 2)
7016 sel_print ("Finishing schedule in bbs: ");
7020 bitmap_set_bit (scheduled_blocks, BLOCK_TO_BB (bb1->index));
7022 if (sched_verbose >= 2)
7023 sel_print ("%d; ", bb1->index);
7025 while (!bb_ends_ebb_p (bb1) && (bb1 = bb_next_bb (bb1)));
7027 if (sched_verbose >= 2)
7028 sel_print ("\n");
7030 get_ebb_head_tail (bb, bb1, &head, &tail);
7032 current_sched_info->head = head;
7033 current_sched_info->tail = tail;
7034 current_sched_info->prev_head = PREV_INSN (head);
7035 current_sched_info->next_tail = NEXT_INSN (tail);
7038 /* Regenerate INSN_SCHED_CYCLEs for insns of current EBB. */
7039 static void
7040 reset_sched_cycles_in_current_ebb (void)
7042 int last_clock = 0;
7043 int haifa_last_clock = -1;
7044 int haifa_clock = 0;
7045 int issued_insns = 0;
7046 insn_t insn;
7048 if (targetm.sched.init)
7050 /* None of the arguments are actually used in any target.
7051 NB: We should have md_reset () hook for cases like this. */
7052 targetm.sched.init (sched_dump, sched_verbose, -1);
7055 state_reset (curr_state);
7056 advance_state (curr_state);
7058 for (insn = current_sched_info->head;
7059 insn != current_sched_info->next_tail;
7060 insn = NEXT_INSN (insn))
7062 int cost, haifa_cost;
7063 int sort_p;
7064 bool asm_p, real_insn, after_stall, all_issued;
7065 int clock;
7067 if (!INSN_P (insn))
7068 continue;
7070 asm_p = false;
7071 real_insn = recog_memoized (insn) >= 0;
7072 clock = INSN_SCHED_CYCLE (insn);
7074 cost = clock - last_clock;
7076 /* Initialize HAIFA_COST. */
7077 if (! real_insn)
7079 asm_p = INSN_ASM_P (insn);
7081 if (asm_p)
7082 /* This is asm insn which *had* to be scheduled first
7083 on the cycle. */
7084 haifa_cost = 1;
7085 else
7086 /* This is a use/clobber insn. It should not change
7087 cost. */
7088 haifa_cost = 0;
7090 else
7091 haifa_cost = estimate_insn_cost (insn, curr_state);
7093 /* Stall for whatever cycles we've stalled before. */
7094 after_stall = 0;
7095 if (INSN_AFTER_STALL_P (insn) && cost > haifa_cost)
7097 haifa_cost = cost;
7098 after_stall = 1;
7100 all_issued = issued_insns == issue_rate;
7101 if (haifa_cost == 0 && all_issued)
7102 haifa_cost = 1;
7103 if (haifa_cost > 0)
7105 int i = 0;
7107 while (haifa_cost--)
7109 advance_state (curr_state);
7110 issued_insns = 0;
7111 i++;
7113 if (sched_verbose >= 2)
7115 sel_print ("advance_state (state_transition)\n");
7116 debug_state (curr_state);
7119 /* The DFA may report that e.g. insn requires 2 cycles to be
7120 issued, but on the next cycle it says that insn is ready
7121 to go. Check this here. */
7122 if (!after_stall
7123 && real_insn
7124 && haifa_cost > 0
7125 && estimate_insn_cost (insn, curr_state) == 0)
7126 break;
7128 /* When the data dependency stall is longer than the DFA stall,
7129 and when we have issued exactly issue_rate insns and stalled,
7130 it could be that after this longer stall the insn will again
7131 become unavailable to the DFA restrictions. Looks strange
7132 but happens e.g. on x86-64. So recheck DFA on the last
7133 iteration. */
7134 if ((after_stall || all_issued)
7135 && real_insn
7136 && haifa_cost == 0)
7137 haifa_cost = estimate_insn_cost (insn, curr_state);
7140 haifa_clock += i;
7141 if (sched_verbose >= 2)
7142 sel_print ("haifa clock: %d\n", haifa_clock);
7144 else
7145 gcc_assert (haifa_cost == 0);
7147 if (sched_verbose >= 2)
7148 sel_print ("Haifa cost for insn %d: %d\n", INSN_UID (insn), haifa_cost);
7150 if (targetm.sched.dfa_new_cycle)
7151 while (targetm.sched.dfa_new_cycle (sched_dump, sched_verbose, insn,
7152 haifa_last_clock, haifa_clock,
7153 &sort_p))
7155 advance_state (curr_state);
7156 issued_insns = 0;
7157 haifa_clock++;
7158 if (sched_verbose >= 2)
7160 sel_print ("advance_state (dfa_new_cycle)\n");
7161 debug_state (curr_state);
7162 sel_print ("haifa clock: %d\n", haifa_clock + 1);
7166 if (real_insn)
7168 static state_t temp = NULL;
7170 if (!temp)
7171 temp = xmalloc (dfa_state_size);
7172 memcpy (temp, curr_state, dfa_state_size);
7174 cost = state_transition (curr_state, insn);
7175 if (memcmp (temp, curr_state, dfa_state_size))
7176 issued_insns++;
7178 if (sched_verbose >= 2)
7180 sel_print ("scheduled insn %d, clock %d\n", INSN_UID (insn),
7181 haifa_clock + 1);
7182 debug_state (curr_state);
7184 gcc_assert (cost < 0);
7187 if (targetm.sched.variable_issue)
7188 targetm.sched.variable_issue (sched_dump, sched_verbose, insn, 0);
7190 INSN_SCHED_CYCLE (insn) = haifa_clock;
7192 last_clock = clock;
7193 haifa_last_clock = haifa_clock;
7197 /* Put TImode markers on insns starting a new issue group. */
7198 static void
7199 put_TImodes (void)
7201 int last_clock = -1;
7202 insn_t insn;
7204 for (insn = current_sched_info->head; insn != current_sched_info->next_tail;
7205 insn = NEXT_INSN (insn))
7207 int cost, clock;
7209 if (!INSN_P (insn))
7210 continue;
7212 clock = INSN_SCHED_CYCLE (insn);
7213 cost = (last_clock == -1) ? 1 : clock - last_clock;
7215 gcc_assert (cost >= 0);
7217 if (issue_rate > 1
7218 && GET_CODE (PATTERN (insn)) != USE
7219 && GET_CODE (PATTERN (insn)) != CLOBBER)
7221 if (reload_completed && cost > 0)
7222 PUT_MODE (insn, TImode);
7224 last_clock = clock;
7227 if (sched_verbose >= 2)
7228 sel_print ("Cost for insn %d is %d\n", INSN_UID (insn), cost);
7232 /* Perform MD_FINISH on EBBs comprising current region. When
7233 RESET_SCHED_CYCLES_P is true, run a pass emulating the scheduler
7234 to produce correct sched cycles on insns. */
7235 static void
7236 sel_region_target_finish (bool reset_sched_cycles_p)
7238 int i;
7239 bitmap scheduled_blocks = BITMAP_ALLOC (NULL);
7241 for (i = 0; i < current_nr_blocks; i++)
7243 if (bitmap_bit_p (scheduled_blocks, i))
7244 continue;
7246 /* While pipelining outer loops, skip bundling for loop
7247 preheaders. Those will be rescheduled in the outer loop. */
7248 if (sel_is_loop_preheader_p (EBB_FIRST_BB (i)))
7249 continue;
7251 find_ebb_boundaries (EBB_FIRST_BB (i), scheduled_blocks);
7253 if (no_real_insns_p (current_sched_info->head, current_sched_info->tail))
7254 continue;
7256 if (reset_sched_cycles_p)
7257 reset_sched_cycles_in_current_ebb ();
7259 if (targetm.sched.init)
7260 targetm.sched.init (sched_dump, sched_verbose, -1);
7262 put_TImodes ();
7264 if (targetm.sched.finish)
7266 targetm.sched.finish (sched_dump, sched_verbose);
7268 /* Extend luids so that insns generated by the target will
7269 get zero luid. */
7270 sched_extend_luids ();
7274 BITMAP_FREE (scheduled_blocks);
7277 /* Free the scheduling data for the current region. When RESET_SCHED_CYCLES_P
7278 is true, make an additional pass emulating scheduler to get correct insn
7279 cycles for md_finish calls. */
7280 static void
7281 sel_region_finish (bool reset_sched_cycles_p)
7283 simplify_changed_insns ();
7284 sched_finish_ready_list ();
7285 free_nop_pool ();
7287 /* Free the vectors. */
7288 vec_av_set.release ();
7289 BITMAP_FREE (current_copies);
7290 BITMAP_FREE (current_originators);
7291 BITMAP_FREE (code_motion_visited_blocks);
7292 vinsn_vec_free (vec_bookkeeping_blocked_vinsns);
7293 vinsn_vec_free (vec_target_unavailable_vinsns);
7295 /* If LV_SET of the region head should be updated, do it now because
7296 there will be no other chance. */
7298 succ_iterator si;
7299 insn_t insn;
7301 FOR_EACH_SUCC_1 (insn, si, bb_note (EBB_FIRST_BB (0)),
7302 SUCCS_NORMAL | SUCCS_SKIP_TO_LOOP_EXITS)
7304 basic_block bb = BLOCK_FOR_INSN (insn);
7306 if (!BB_LV_SET_VALID_P (bb))
7307 compute_live (insn);
7311 /* Emulate the Haifa scheduler for bundling. */
7312 if (reload_completed)
7313 sel_region_target_finish (reset_sched_cycles_p);
7315 sel_finish_global_and_expr ();
7317 bitmap_clear (forced_ebb_heads);
7319 free_nop_vinsn ();
7321 finish_deps_global ();
7322 sched_finish_luids ();
7323 h_d_i_d.release ();
7325 sel_finish_bbs ();
7326 BITMAP_FREE (blocks_to_reschedule);
7328 sel_unregister_cfg_hooks ();
7330 max_issue_size = 0;
7334 /* Functions that implement the scheduler driver. */
7336 /* Schedule a parallel instruction group on each of FENCES. MAX_SEQNO
7337 is the current maximum seqno. SCHEDULED_INSNS_TAILPP is the list
7338 of insns scheduled -- these would be postprocessed later. */
7339 static void
7340 schedule_on_fences (flist_t fences, int max_seqno,
7341 ilist_t **scheduled_insns_tailpp)
7343 flist_t old_fences = fences;
7345 if (sched_verbose >= 1)
7347 sel_print ("\nScheduling on fences: ");
7348 dump_flist (fences);
7349 sel_print ("\n");
7352 scheduled_something_on_previous_fence = false;
7353 for (; fences; fences = FLIST_NEXT (fences))
7355 fence_t fence = NULL;
7356 int seqno = 0;
7357 flist_t fences2;
7358 bool first_p = true;
7360 /* Choose the next fence group to schedule.
7361 The fact that insn can be scheduled only once
7362 on the cycle is guaranteed by two properties:
7363 1. seqnos of parallel groups decrease with each iteration.
7364 2. If is_ineligible_successor () sees the larger seqno, it
7365 checks if candidate insn is_in_current_fence_p (). */
7366 for (fences2 = old_fences; fences2; fences2 = FLIST_NEXT (fences2))
7368 fence_t f = FLIST_FENCE (fences2);
7370 if (!FENCE_PROCESSED_P (f))
7372 int i = INSN_SEQNO (FENCE_INSN (f));
7374 if (first_p || i > seqno)
7376 seqno = i;
7377 fence = f;
7378 first_p = false;
7380 else
7381 /* ??? Seqnos of different groups should be different. */
7382 gcc_assert (1 || i != seqno);
7386 gcc_assert (fence);
7388 /* As FENCE is nonnull, SEQNO is initialized. */
7389 seqno -= max_seqno + 1;
7390 fill_insns (fence, seqno, scheduled_insns_tailpp);
7391 FENCE_PROCESSED_P (fence) = true;
7394 /* All av_sets are invalidated by GLOBAL_LEVEL increase, thus we
7395 don't need to keep bookkeeping-invalidated and target-unavailable
7396 vinsns any more. */
7397 vinsn_vec_clear (&vec_bookkeeping_blocked_vinsns);
7398 vinsn_vec_clear (&vec_target_unavailable_vinsns);
7401 /* Calculate MIN_SEQNO and MAX_SEQNO. */
7402 static void
7403 find_min_max_seqno (flist_t fences, int *min_seqno, int *max_seqno)
7405 *min_seqno = *max_seqno = INSN_SEQNO (FENCE_INSN (FLIST_FENCE (fences)));
7407 /* The first element is already processed. */
7408 while ((fences = FLIST_NEXT (fences)))
7410 int seqno = INSN_SEQNO (FENCE_INSN (FLIST_FENCE (fences)));
7412 if (*min_seqno > seqno)
7413 *min_seqno = seqno;
7414 else if (*max_seqno < seqno)
7415 *max_seqno = seqno;
7419 /* Calculate new fences from FENCES. Write the current time to PTIME. */
7420 static flist_t
7421 calculate_new_fences (flist_t fences, int orig_max_seqno, int *ptime)
7423 flist_t old_fences = fences;
7424 struct flist_tail_def _new_fences, *new_fences = &_new_fences;
7425 int max_time = 0;
7427 flist_tail_init (new_fences);
7428 for (; fences; fences = FLIST_NEXT (fences))
7430 fence_t fence = FLIST_FENCE (fences);
7431 insn_t insn;
7433 if (!FENCE_BNDS (fence))
7435 /* This fence doesn't have any successors. */
7436 if (!FENCE_SCHEDULED_P (fence))
7438 /* Nothing was scheduled on this fence. */
7439 int seqno;
7441 insn = FENCE_INSN (fence);
7442 seqno = INSN_SEQNO (insn);
7443 gcc_assert (seqno > 0 && seqno <= orig_max_seqno);
7445 if (sched_verbose >= 1)
7446 sel_print ("Fence %d[%d] has not changed\n",
7447 INSN_UID (insn),
7448 BLOCK_NUM (insn));
7449 move_fence_to_fences (fences, new_fences);
7452 else
7453 extract_new_fences_from (fences, new_fences, orig_max_seqno);
7454 max_time = MAX (max_time, FENCE_CYCLE (fence));
7457 flist_clear (&old_fences);
7458 *ptime = max_time;
7459 return FLIST_TAIL_HEAD (new_fences);
7462 /* Update seqnos of insns given by PSCHEDULED_INSNS. MIN_SEQNO and MAX_SEQNO
7463 are the miminum and maximum seqnos of the group, HIGHEST_SEQNO_IN_USE is
7464 the highest seqno used in a region. Return the updated highest seqno. */
7465 static int
7466 update_seqnos_and_stage (int min_seqno, int max_seqno,
7467 int highest_seqno_in_use,
7468 ilist_t *pscheduled_insns)
7470 int new_hs;
7471 ilist_iterator ii;
7472 insn_t insn;
7474 /* Actually, new_hs is the seqno of the instruction, that was
7475 scheduled first (i.e. it is the first one in SCHEDULED_INSNS). */
7476 if (*pscheduled_insns)
7478 new_hs = (INSN_SEQNO (ILIST_INSN (*pscheduled_insns))
7479 + highest_seqno_in_use + max_seqno - min_seqno + 2);
7480 gcc_assert (new_hs > highest_seqno_in_use);
7482 else
7483 new_hs = highest_seqno_in_use;
7485 FOR_EACH_INSN (insn, ii, *pscheduled_insns)
7487 gcc_assert (INSN_SEQNO (insn) < 0);
7488 INSN_SEQNO (insn) += highest_seqno_in_use + max_seqno - min_seqno + 2;
7489 gcc_assert (INSN_SEQNO (insn) <= new_hs);
7491 /* When not pipelining, purge unneeded insn info on the scheduled insns.
7492 For example, having reg_last array of INSN_DEPS_CONTEXT in memory may
7493 require > 1GB of memory e.g. on limit-fnargs.c. */
7494 if (! pipelining_p)
7495 free_data_for_scheduled_insn (insn);
7498 ilist_clear (pscheduled_insns);
7499 global_level++;
7501 return new_hs;
7504 /* The main driver for scheduling a region. This function is responsible
7505 for correct propagation of fences (i.e. scheduling points) and creating
7506 a group of parallel insns at each of them. It also supports
7507 pipelining. ORIG_MAX_SEQNO is the maximal seqno before this pass
7508 of scheduling. */
7509 static void
7510 sel_sched_region_2 (int orig_max_seqno)
7512 int highest_seqno_in_use = orig_max_seqno;
7513 int max_time = 0;
7515 stat_bookkeeping_copies = 0;
7516 stat_insns_needed_bookkeeping = 0;
7517 stat_renamed_scheduled = 0;
7518 stat_substitutions_total = 0;
7519 num_insns_scheduled = 0;
7521 while (fences)
7523 int min_seqno, max_seqno;
7524 ilist_t scheduled_insns = NULL;
7525 ilist_t *scheduled_insns_tailp = &scheduled_insns;
7527 find_min_max_seqno (fences, &min_seqno, &max_seqno);
7528 schedule_on_fences (fences, max_seqno, &scheduled_insns_tailp);
7529 fences = calculate_new_fences (fences, orig_max_seqno, &max_time);
7530 highest_seqno_in_use = update_seqnos_and_stage (min_seqno, max_seqno,
7531 highest_seqno_in_use,
7532 &scheduled_insns);
7535 if (sched_verbose >= 1)
7537 sel_print ("Total scheduling time: %d cycles\n", max_time);
7538 sel_print ("Scheduled %d bookkeeping copies, %d insns needed "
7539 "bookkeeping, %d insns renamed, %d insns substituted\n",
7540 stat_bookkeeping_copies,
7541 stat_insns_needed_bookkeeping,
7542 stat_renamed_scheduled,
7543 stat_substitutions_total);
7547 /* Schedule a region. When pipelining, search for possibly never scheduled
7548 bookkeeping code and schedule it. Reschedule pipelined code without
7549 pipelining after. */
7550 static void
7551 sel_sched_region_1 (void)
7553 int orig_max_seqno;
7555 /* Remove empty blocks that might be in the region from the beginning. */
7556 purge_empty_blocks ();
7558 orig_max_seqno = init_seqno (NULL, NULL);
7559 gcc_assert (orig_max_seqno >= 1);
7561 /* When pipelining outer loops, create fences on the loop header,
7562 not preheader. */
7563 fences = NULL;
7564 if (current_loop_nest)
7565 init_fences (BB_END (EBB_FIRST_BB (0)));
7566 else
7567 init_fences (bb_note (EBB_FIRST_BB (0)));
7568 global_level = 1;
7570 sel_sched_region_2 (orig_max_seqno);
7572 gcc_assert (fences == NULL);
7574 if (pipelining_p)
7576 int i;
7577 basic_block bb;
7578 struct flist_tail_def _new_fences;
7579 flist_tail_t new_fences = &_new_fences;
7580 bool do_p = true;
7582 pipelining_p = false;
7583 max_ws = MIN (max_ws, issue_rate * 3 / 2);
7584 bookkeeping_p = false;
7585 enable_schedule_as_rhs_p = false;
7587 /* Schedule newly created code, that has not been scheduled yet. */
7588 do_p = true;
7590 while (do_p)
7592 do_p = false;
7594 for (i = 0; i < current_nr_blocks; i++)
7596 basic_block bb = EBB_FIRST_BB (i);
7598 if (bitmap_bit_p (blocks_to_reschedule, bb->index))
7600 if (! bb_ends_ebb_p (bb))
7601 bitmap_set_bit (blocks_to_reschedule, bb_next_bb (bb)->index);
7602 if (sel_bb_empty_p (bb))
7604 bitmap_clear_bit (blocks_to_reschedule, bb->index);
7605 continue;
7607 clear_outdated_rtx_info (bb);
7608 if (sel_insn_is_speculation_check (BB_END (bb))
7609 && JUMP_P (BB_END (bb)))
7610 bitmap_set_bit (blocks_to_reschedule,
7611 BRANCH_EDGE (bb)->dest->index);
7613 else if (! sel_bb_empty_p (bb)
7614 && INSN_SCHED_TIMES (sel_bb_head (bb)) <= 0)
7615 bitmap_set_bit (blocks_to_reschedule, bb->index);
7618 for (i = 0; i < current_nr_blocks; i++)
7620 bb = EBB_FIRST_BB (i);
7622 /* While pipelining outer loops, skip bundling for loop
7623 preheaders. Those will be rescheduled in the outer
7624 loop. */
7625 if (sel_is_loop_preheader_p (bb))
7627 clear_outdated_rtx_info (bb);
7628 continue;
7631 if (bitmap_bit_p (blocks_to_reschedule, bb->index))
7633 flist_tail_init (new_fences);
7635 orig_max_seqno = init_seqno (blocks_to_reschedule, bb);
7637 /* Mark BB as head of the new ebb. */
7638 bitmap_set_bit (forced_ebb_heads, bb->index);
7640 gcc_assert (fences == NULL);
7642 init_fences (bb_note (bb));
7644 sel_sched_region_2 (orig_max_seqno);
7646 do_p = true;
7647 break;
7654 /* Schedule the RGN region. */
7655 void
7656 sel_sched_region (int rgn)
7658 bool schedule_p;
7659 bool reset_sched_cycles_p;
7661 if (sel_region_init (rgn))
7662 return;
7664 if (sched_verbose >= 1)
7665 sel_print ("Scheduling region %d\n", rgn);
7667 schedule_p = (!sched_is_disabled_for_current_region_p ()
7668 && dbg_cnt (sel_sched_region_cnt));
7669 reset_sched_cycles_p = pipelining_p;
7670 if (schedule_p)
7671 sel_sched_region_1 ();
7672 else
7673 /* Force initialization of INSN_SCHED_CYCLEs for correct bundling. */
7674 reset_sched_cycles_p = true;
7676 sel_region_finish (reset_sched_cycles_p);
7679 /* Perform global init for the scheduler. */
7680 static void
7681 sel_global_init (void)
7683 calculate_dominance_info (CDI_DOMINATORS);
7684 alloc_sched_pools ();
7686 /* Setup the infos for sched_init. */
7687 sel_setup_sched_infos ();
7688 setup_sched_dump ();
7690 sched_rgn_init (false);
7691 sched_init ();
7693 sched_init_bbs ();
7694 /* Reset AFTER_RECOVERY if it has been set by the 1st scheduler pass. */
7695 after_recovery = 0;
7696 can_issue_more = issue_rate;
7698 sched_extend_target ();
7699 sched_deps_init (true);
7700 setup_nop_and_exit_insns ();
7701 sel_extend_global_bb_info ();
7702 init_lv_sets ();
7703 init_hard_regs_data ();
7706 /* Free the global data of the scheduler. */
7707 static void
7708 sel_global_finish (void)
7710 free_bb_note_pool ();
7711 free_lv_sets ();
7712 sel_finish_global_bb_info ();
7714 free_regset_pool ();
7715 free_nop_and_exit_insns ();
7717 sched_rgn_finish ();
7718 sched_deps_finish ();
7719 sched_finish ();
7721 if (current_loops)
7722 sel_finish_pipelining ();
7724 free_sched_pools ();
7725 free_dominance_info (CDI_DOMINATORS);
7728 /* Return true when we need to skip selective scheduling. Used for debugging. */
7729 bool
7730 maybe_skip_selective_scheduling (void)
7732 return ! dbg_cnt (sel_sched_cnt);
7735 /* The entry point. */
7736 void
7737 run_selective_scheduling (void)
7739 int rgn;
7741 if (n_basic_blocks_for_fn (cfun) == NUM_FIXED_BLOCKS)
7742 return;
7744 sel_global_init ();
7746 for (rgn = 0; rgn < nr_regions; rgn++)
7747 sel_sched_region (rgn);
7749 sel_global_finish ();
7752 #endif