Daily bump.
[official-gcc.git] / gcc / sel-sched.c
blob9c33b51efe1cc2145310b0a0b121cff79ceb7c6e
1 /* Instruction scheduling pass. Selective scheduler and pipeliner.
2 Copyright (C) 2006-2016 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 "backend.h"
24 #include "tree.h"
25 #include "rtl.h"
26 #include "df.h"
27 #include "memmodel.h"
28 #include "tm_p.h"
29 #include "regs.h"
30 #include "cfgbuild.h"
31 #include "insn-config.h"
32 #include "insn-attr.h"
33 #include "params.h"
34 #include "target.h"
35 #include "sched-int.h"
36 #include "rtlhooks-def.h"
37 #include "ira.h"
38 #include "ira-int.h"
39 #include "rtl-iter.h"
41 #ifdef INSN_SCHEDULING
42 #include "regset.h"
43 #include "cfgloop.h"
44 #include "sel-sched-ir.h"
45 #include "sel-sched-dump.h"
46 #include "sel-sched.h"
47 #include "dbgcnt.h"
49 /* Implementation of selective scheduling approach.
50 The below implementation follows the original approach with the following
51 changes:
53 o the scheduler works after register allocation (but can be also tuned
54 to work before RA);
55 o some instructions are not copied or register renamed;
56 o conditional jumps are not moved with code duplication;
57 o several jumps in one parallel group are not supported;
58 o when pipelining outer loops, code motion through inner loops
59 is not supported;
60 o control and data speculation are supported;
61 o some improvements for better compile time/performance were made.
63 Terminology
64 ===========
66 A vinsn, or virtual insn, is an insn with additional data characterizing
67 insn pattern, such as LHS, RHS, register sets used/set/clobbered, etc.
68 Vinsns also act as smart pointers to save memory by reusing them in
69 different expressions. A vinsn is described by vinsn_t type.
71 An expression is a vinsn with additional data characterizing its properties
72 at some point in the control flow graph. The data may be its usefulness,
73 priority, speculative status, whether it was renamed/subsituted, etc.
74 An expression is described by expr_t type.
76 Availability set (av_set) is a set of expressions at a given control flow
77 point. It is represented as av_set_t. The expressions in av sets are kept
78 sorted in the terms of expr_greater_p function. It allows to truncate
79 the set while leaving the best expressions.
81 A fence is a point through which code motion is prohibited. On each step,
82 we gather a parallel group of insns at a fence. It is possible to have
83 multiple fences. A fence is represented via fence_t.
85 A boundary is the border between the fence group and the rest of the code.
86 Currently, we never have more than one boundary per fence, as we finalize
87 the fence group when a jump is scheduled. A boundary is represented
88 via bnd_t.
90 High-level overview
91 ===================
93 The scheduler finds regions to schedule, schedules each one, and finalizes.
94 The regions are formed starting from innermost loops, so that when the inner
95 loop is pipelined, its prologue can be scheduled together with yet unprocessed
96 outer loop. The rest of acyclic regions are found using extend_rgns:
97 the blocks that are not yet allocated to any regions are traversed in top-down
98 order, and a block is added to a region to which all its predecessors belong;
99 otherwise, the block starts its own region.
101 The main scheduling loop (sel_sched_region_2) consists of just
102 scheduling on each fence and updating fences. For each fence,
103 we fill a parallel group of insns (fill_insns) until some insns can be added.
104 First, we compute available exprs (av-set) at the boundary of the current
105 group. Second, we choose the best expression from it. If the stall is
106 required to schedule any of the expressions, we advance the current cycle
107 appropriately. So, the final group does not exactly correspond to a VLIW
108 word. Third, we move the chosen expression to the boundary (move_op)
109 and update the intermediate av sets and liveness sets. We quit fill_insns
110 when either no insns left for scheduling or we have scheduled enough insns
111 so we feel like advancing a scheduling point.
113 Computing available expressions
114 ===============================
116 The computation (compute_av_set) is a bottom-up traversal. At each insn,
117 we're moving the union of its successors' sets through it via
118 moveup_expr_set. The dependent expressions are removed. Local
119 transformations (substitution, speculation) are applied to move more
120 exprs. Then the expr corresponding to the current insn is added.
121 The result is saved on each basic block header.
123 When traversing the CFG, we're moving down for no more than max_ws insns.
124 Also, we do not move down to ineligible successors (is_ineligible_successor),
125 which include moving along a back-edge, moving to already scheduled code,
126 and moving to another fence. The first two restrictions are lifted during
127 pipelining, which allows us to move insns along a back-edge. We always have
128 an acyclic region for scheduling because we forbid motion through fences.
130 Choosing the best expression
131 ============================
133 We sort the final availability set via sel_rank_for_schedule, then we remove
134 expressions which are not yet ready (tick_check_p) or which dest registers
135 cannot be used. For some of them, we choose another register via
136 find_best_reg. To do this, we run find_used_regs to calculate the set of
137 registers which cannot be used. The find_used_regs function performs
138 a traversal of code motion paths for an expr. We consider for renaming
139 only registers which are from the same regclass as the original one and
140 using which does not interfere with any live ranges. Finally, we convert
141 the resulting set to the ready list format and use max_issue and reorder*
142 hooks similarly to the Haifa scheduler.
144 Scheduling the best expression
145 ==============================
147 We run the move_op routine to perform the same type of code motion paths
148 traversal as in find_used_regs. (These are working via the same driver,
149 code_motion_path_driver.) When moving down the CFG, we look for original
150 instruction that gave birth to a chosen expression. We undo
151 the transformations performed on an expression via the history saved in it.
152 When found, we remove the instruction or leave a reg-reg copy/speculation
153 check if needed. On a way up, we insert bookkeeping copies at each join
154 point. If a copy is not needed, it will be removed later during this
155 traversal. We update the saved av sets and liveness sets on the way up, too.
157 Finalizing the schedule
158 =======================
160 When pipelining, we reschedule the blocks from which insns were pipelined
161 to get a tighter schedule. On Itanium, we also perform bundling via
162 the same routine from ia64.c.
164 Dependence analysis changes
165 ===========================
167 We augmented the sched-deps.c with hooks that get called when a particular
168 dependence is found in a particular part of an insn. Using these hooks, we
169 can do several actions such as: determine whether an insn can be moved through
170 another (has_dependence_p, moveup_expr); find out whether an insn can be
171 scheduled on the current cycle (tick_check_p); find out registers that
172 are set/used/clobbered by an insn and find out all the strange stuff that
173 restrict its movement, like SCHED_GROUP_P or CANT_MOVE (done in
174 init_global_and_expr_for_insn).
176 Initialization changes
177 ======================
179 There are parts of haifa-sched.c, sched-deps.c, and sched-rgn.c that are
180 reused in all of the schedulers. We have split up the initialization of data
181 of such parts into different functions prefixed with scheduler type and
182 postfixed with the type of data initialized: {,sel_,haifa_}sched_{init,finish},
183 sched_rgn_init/finish, sched_deps_init/finish, sched_init_{luids/bbs}, etc.
184 The same splitting is done with current_sched_info structure:
185 dependence-related parts are in sched_deps_info, common part is in
186 common_sched_info, and haifa/sel/etc part is in current_sched_info.
188 Target contexts
189 ===============
191 As we now have multiple-point scheduling, this would not work with backends
192 which save some of the scheduler state to use it in the target hooks.
193 For this purpose, we introduce a concept of target contexts, which
194 encapsulate such information. The backend should implement simple routines
195 of allocating/freeing/setting such a context. The scheduler calls these
196 as target hooks and handles the target context as an opaque pointer (similar
197 to the DFA state type, state_t).
199 Various speedups
200 ================
202 As the correct data dependence graph is not supported during scheduling (which
203 is to be changed in mid-term), we cache as much of the dependence analysis
204 results as possible to avoid reanalyzing. This includes: bitmap caches on
205 each insn in stream of the region saying yes/no for a query with a pair of
206 UIDs; hashtables with the previously done transformations on each insn in
207 stream; a vector keeping a history of transformations on each expr.
209 Also, we try to minimize the dependence context used on each fence to check
210 whether the given expression is ready for scheduling by removing from it
211 insns that are definitely completed the execution. The results of
212 tick_check_p checks are also cached in a vector on each fence.
214 We keep a valid liveness set on each insn in a region to avoid the high
215 cost of recomputation on large basic blocks.
217 Finally, we try to minimize the number of needed updates to the availability
218 sets. The updates happen in two cases: when fill_insns terminates,
219 we advance all fences and increase the stage number to show that the region
220 has changed and the sets are to be recomputed; and when the next iteration
221 of a loop in fill_insns happens (but this one reuses the saved av sets
222 on bb headers.) Thus, we try to break the fill_insns loop only when
223 "significant" number of insns from the current scheduling window was
224 scheduled. This should be made a target param.
227 TODO: correctly support the data dependence graph at all stages and get rid
228 of all caches. This should speed up the scheduler.
229 TODO: implement moving cond jumps with bookkeeping copies on both targets.
230 TODO: tune the scheduler before RA so it does not create too much pseudos.
233 References:
234 S.-M. Moon and K. Ebcioglu. Parallelizing nonnumerical code with
235 selective scheduling and software pipelining.
236 ACM TOPLAS, Vol 19, No. 6, pages 853--898, Nov. 1997.
238 Andrey Belevantsev, Maxim Kuvyrkov, Vladimir Makarov, Dmitry Melnik,
239 and Dmitry Zhurikhin. An interblock VLIW-targeted instruction scheduler
240 for GCC. In Proceedings of GCC Developers' Summit 2006.
242 Arutyun Avetisyan, Andrey Belevantsev, and Dmitry Melnik. GCC Instruction
243 Scheduler and Software Pipeliner on the Itanium Platform. EPIC-7 Workshop.
244 http://rogue.colorado.edu/EPIC7/.
248 /* True when pipelining is enabled. */
249 bool pipelining_p;
251 /* True if bookkeeping is enabled. */
252 bool bookkeeping_p;
254 /* Maximum number of insns that are eligible for renaming. */
255 int max_insns_to_rename;
258 /* Definitions of local types and macros. */
260 /* Represents possible outcomes of moving an expression through an insn. */
261 enum MOVEUP_EXPR_CODE
263 /* The expression is not changed. */
264 MOVEUP_EXPR_SAME,
266 /* Not changed, but requires a new destination register. */
267 MOVEUP_EXPR_AS_RHS,
269 /* Cannot be moved. */
270 MOVEUP_EXPR_NULL,
272 /* Changed (substituted or speculated). */
273 MOVEUP_EXPR_CHANGED
276 /* The container to be passed into rtx search & replace functions. */
277 struct rtx_search_arg
279 /* What we are searching for. */
280 rtx x;
282 /* The occurrence counter. */
283 int n;
286 typedef struct rtx_search_arg *rtx_search_arg_p;
288 /* This struct contains precomputed hard reg sets that are needed when
289 computing registers available for renaming. */
290 struct hard_regs_data
292 /* For every mode, this stores registers available for use with
293 that mode. */
294 HARD_REG_SET regs_for_mode[NUM_MACHINE_MODES];
296 /* True when regs_for_mode[mode] is initialized. */
297 bool regs_for_mode_ok[NUM_MACHINE_MODES];
299 /* For every register, it has regs that are ok to rename into it.
300 The register in question is always set. If not, this means
301 that the whole set is not computed yet. */
302 HARD_REG_SET regs_for_rename[FIRST_PSEUDO_REGISTER];
304 /* For every mode, this stores registers not available due to
305 call clobbering. */
306 HARD_REG_SET regs_for_call_clobbered[NUM_MACHINE_MODES];
308 /* All registers that are used or call used. */
309 HARD_REG_SET regs_ever_used;
311 #ifdef STACK_REGS
312 /* Stack registers. */
313 HARD_REG_SET stack_regs;
314 #endif
317 /* Holds the results of computation of available for renaming and
318 unavailable hard registers. */
319 struct reg_rename
321 /* These are unavailable due to calls crossing, globalness, etc. */
322 HARD_REG_SET unavailable_hard_regs;
324 /* These are *available* for renaming. */
325 HARD_REG_SET available_for_renaming;
327 /* Whether this code motion path crosses a call. */
328 bool crosses_call;
331 /* A global structure that contains the needed information about harg
332 regs. */
333 static struct hard_regs_data sel_hrd;
336 /* This structure holds local data used in code_motion_path_driver hooks on
337 the same or adjacent levels of recursion. Here we keep those parameters
338 that are not used in code_motion_path_driver routine itself, but only in
339 its hooks. Moreover, all parameters that can be modified in hooks are
340 in this structure, so all other parameters passed explicitly to hooks are
341 read-only. */
342 struct cmpd_local_params
344 /* Local params used in move_op_* functions. */
346 /* Edges for bookkeeping generation. */
347 edge e1, e2;
349 /* C_EXPR merged from all successors and locally allocated temporary C_EXPR. */
350 expr_t c_expr_merged, c_expr_local;
352 /* Local params used in fur_* functions. */
353 /* Copy of the ORIGINAL_INSN list, stores the original insns already
354 found before entering the current level of code_motion_path_driver. */
355 def_list_t old_original_insns;
357 /* Local params used in move_op_* functions. */
358 /* True when we have removed last insn in the block which was
359 also a boundary. Do not update anything or create bookkeeping copies. */
360 BOOL_BITFIELD removed_last_insn : 1;
363 /* Stores the static parameters for move_op_* calls. */
364 struct moveop_static_params
366 /* Destination register. */
367 rtx dest;
369 /* Current C_EXPR. */
370 expr_t c_expr;
372 /* An UID of expr_vliw which is to be moved up. If we find other exprs,
373 they are to be removed. */
374 int uid;
376 /* This is initialized to the insn on which the driver stopped its traversal. */
377 insn_t failed_insn;
379 /* True if we scheduled an insn with different register. */
380 bool was_renamed;
383 /* Stores the static parameters for fur_* calls. */
384 struct fur_static_params
386 /* Set of registers unavailable on the code motion path. */
387 regset used_regs;
389 /* Pointer to the list of original insns definitions. */
390 def_list_t *original_insns;
392 /* True if a code motion path contains a CALL insn. */
393 bool crosses_call;
396 typedef struct fur_static_params *fur_static_params_p;
397 typedef struct cmpd_local_params *cmpd_local_params_p;
398 typedef struct moveop_static_params *moveop_static_params_p;
400 /* Set of hooks and parameters that determine behavior specific to
401 move_op or find_used_regs functions. */
402 struct code_motion_path_driver_info_def
404 /* Called on enter to the basic block. */
405 int (*on_enter) (insn_t, cmpd_local_params_p, void *, bool);
407 /* Called when original expr is found. */
408 void (*orig_expr_found) (insn_t, expr_t, cmpd_local_params_p, void *);
410 /* Called while descending current basic block if current insn is not
411 the original EXPR we're searching for. */
412 bool (*orig_expr_not_found) (insn_t, av_set_t, void *);
414 /* Function to merge C_EXPRes from different successors. */
415 void (*merge_succs) (insn_t, insn_t, int, cmpd_local_params_p, void *);
417 /* Function to finalize merge from different successors and possibly
418 deallocate temporary data structures used for merging. */
419 void (*after_merge_succs) (cmpd_local_params_p, void *);
421 /* Called on the backward stage of recursion to do moveup_expr.
422 Used only with move_op_*. */
423 void (*ascend) (insn_t, void *);
425 /* Called on the ascending pass, before returning from the current basic
426 block or from the whole traversal. */
427 void (*at_first_insn) (insn_t, cmpd_local_params_p, void *);
429 /* When processing successors in move_op we need only descend into
430 SUCCS_NORMAL successors, while in find_used_regs we need SUCCS_ALL. */
431 int succ_flags;
433 /* The routine name to print in dumps ("move_op" of "find_used_regs"). */
434 const char *routine_name;
437 /* Global pointer to current hooks, either points to MOVE_OP_HOOKS or
438 FUR_HOOKS. */
439 struct code_motion_path_driver_info_def *code_motion_path_driver_info;
441 /* Set of hooks for performing move_op and find_used_regs routines with
442 code_motion_path_driver. */
443 extern struct code_motion_path_driver_info_def move_op_hooks, fur_hooks;
445 /* True if/when we want to emulate Haifa scheduler in the common code.
446 This is used in sched_rgn_local_init and in various places in
447 sched-deps.c. */
448 int sched_emulate_haifa_p;
450 /* GLOBAL_LEVEL is used to discard information stored in basic block headers
451 av_sets. Av_set of bb header is valid if its (bb header's) level is equal
452 to GLOBAL_LEVEL. And invalid if lesser. This is primarily used to advance
453 scheduling window. */
454 int global_level;
456 /* Current fences. */
457 flist_t fences;
459 /* True when separable insns should be scheduled as RHSes. */
460 static bool enable_schedule_as_rhs_p;
462 /* Used in verify_target_availability to assert that target reg is reported
463 unavailabile by both TARGET_UNAVAILABLE and find_used_regs only if
464 we haven't scheduled anything on the previous fence.
465 if scheduled_something_on_previous_fence is true, TARGET_UNAVAILABLE can
466 have more conservative value than the one returned by the
467 find_used_regs, thus we shouldn't assert that these values are equal. */
468 static bool scheduled_something_on_previous_fence;
470 /* All newly emitted insns will have their uids greater than this value. */
471 static int first_emitted_uid;
473 /* Set of basic blocks that are forced to start new ebbs. This is a subset
474 of all the ebb heads. */
475 static bitmap_head _forced_ebb_heads;
476 bitmap_head *forced_ebb_heads = &_forced_ebb_heads;
478 /* Blocks that need to be rescheduled after pipelining. */
479 bitmap blocks_to_reschedule = NULL;
481 /* True when the first lv set should be ignored when updating liveness. */
482 static bool ignore_first = false;
484 /* Number of insns max_issue has initialized data structures for. */
485 static int max_issue_size = 0;
487 /* Whether we can issue more instructions. */
488 static int can_issue_more;
490 /* Maximum software lookahead window size, reduced when rescheduling after
491 pipelining. */
492 static int max_ws;
494 /* Number of insns scheduled in current region. */
495 static int num_insns_scheduled;
497 /* A vector of expressions is used to be able to sort them. */
498 static vec<expr_t> vec_av_set;
500 /* A vector of vinsns is used to hold temporary lists of vinsns. */
501 typedef vec<vinsn_t> vinsn_vec_t;
503 /* This vector has the exprs which may still present in av_sets, but actually
504 can't be moved up due to bookkeeping created during code motion to another
505 fence. See comment near the call to update_and_record_unavailable_insns
506 for the detailed explanations. */
507 static vinsn_vec_t vec_bookkeeping_blocked_vinsns = vinsn_vec_t ();
509 /* This vector has vinsns which are scheduled with renaming on the first fence
510 and then seen on the second. For expressions with such vinsns, target
511 availability information may be wrong. */
512 static vinsn_vec_t vec_target_unavailable_vinsns = vinsn_vec_t ();
514 /* Vector to store temporary nops inserted in move_op to prevent removal
515 of empty bbs. */
516 static vec<insn_t> vec_temp_moveop_nops;
518 /* These bitmaps record original instructions scheduled on the current
519 iteration and bookkeeping copies created by them. */
520 static bitmap current_originators = NULL;
521 static bitmap current_copies = NULL;
523 /* This bitmap marks the blocks visited by code_motion_path_driver so we don't
524 visit them afterwards. */
525 static bitmap code_motion_visited_blocks = NULL;
527 /* Variables to accumulate different statistics. */
529 /* The number of bookkeeping copies created. */
530 static int stat_bookkeeping_copies;
532 /* The number of insns that required bookkeeiping for their scheduling. */
533 static int stat_insns_needed_bookkeeping;
535 /* The number of insns that got renamed. */
536 static int stat_renamed_scheduled;
538 /* The number of substitutions made during scheduling. */
539 static int stat_substitutions_total;
542 /* Forward declarations of static functions. */
543 static bool rtx_ok_for_substitution_p (rtx, rtx);
544 static int sel_rank_for_schedule (const void *, const void *);
545 static av_set_t find_sequential_best_exprs (bnd_t, expr_t, bool);
546 static basic_block find_block_for_bookkeeping (edge e1, edge e2, bool lax);
548 static rtx get_dest_from_orig_ops (av_set_t);
549 static basic_block generate_bookkeeping_insn (expr_t, edge, edge);
550 static bool find_used_regs (insn_t, av_set_t, regset, struct reg_rename *,
551 def_list_t *);
552 static bool move_op (insn_t, av_set_t, expr_t, rtx, expr_t, bool*);
553 static int code_motion_path_driver (insn_t, av_set_t, ilist_t,
554 cmpd_local_params_p, void *);
555 static void sel_sched_region_1 (void);
556 static void sel_sched_region_2 (int);
557 static av_set_t compute_av_set_inside_bb (insn_t, ilist_t, int, bool);
559 static void debug_state (state_t);
562 /* Functions that work with fences. */
564 /* Advance one cycle on FENCE. */
565 static void
566 advance_one_cycle (fence_t fence)
568 unsigned i;
569 int cycle;
570 rtx_insn *insn;
572 advance_state (FENCE_STATE (fence));
573 cycle = ++FENCE_CYCLE (fence);
574 FENCE_ISSUED_INSNS (fence) = 0;
575 FENCE_STARTS_CYCLE_P (fence) = 1;
576 can_issue_more = issue_rate;
577 FENCE_ISSUE_MORE (fence) = can_issue_more;
579 for (i = 0; vec_safe_iterate (FENCE_EXECUTING_INSNS (fence), i, &insn); )
581 if (INSN_READY_CYCLE (insn) < cycle)
583 remove_from_deps (FENCE_DC (fence), insn);
584 FENCE_EXECUTING_INSNS (fence)->unordered_remove (i);
585 continue;
587 i++;
589 if (sched_verbose >= 2)
591 sel_print ("Finished a cycle. Current cycle = %d\n", FENCE_CYCLE (fence));
592 debug_state (FENCE_STATE (fence));
596 /* Returns true when SUCC in a fallthru bb of INSN, possibly
597 skipping empty basic blocks. */
598 static bool
599 in_fallthru_bb_p (rtx_insn *insn, rtx succ)
601 basic_block bb = BLOCK_FOR_INSN (insn);
602 edge e;
604 if (bb == BLOCK_FOR_INSN (succ))
605 return true;
607 e = find_fallthru_edge_from (bb);
608 if (e)
609 bb = e->dest;
610 else
611 return false;
613 while (sel_bb_empty_p (bb))
614 bb = bb->next_bb;
616 return bb == BLOCK_FOR_INSN (succ);
619 /* Construct successor fences from OLD_FENCEs and put them in NEW_FENCES.
620 When a successor will continue a ebb, transfer all parameters of a fence
621 to the new fence. ORIG_MAX_SEQNO is the maximal seqno before this round
622 of scheduling helping to distinguish between the old and the new code. */
623 static void
624 extract_new_fences_from (flist_t old_fences, flist_tail_t new_fences,
625 int orig_max_seqno)
627 bool was_here_p = false;
628 insn_t insn = NULL;
629 insn_t succ;
630 succ_iterator si;
631 ilist_iterator ii;
632 fence_t fence = FLIST_FENCE (old_fences);
633 basic_block bb;
635 /* Get the only element of FENCE_BNDS (fence). */
636 FOR_EACH_INSN (insn, ii, FENCE_BNDS (fence))
638 gcc_assert (!was_here_p);
639 was_here_p = true;
641 gcc_assert (was_here_p && insn != NULL_RTX);
643 /* When in the "middle" of the block, just move this fence
644 to the new list. */
645 bb = BLOCK_FOR_INSN (insn);
646 if (! sel_bb_end_p (insn)
647 || (single_succ_p (bb)
648 && single_pred_p (single_succ (bb))))
650 insn_t succ;
652 succ = (sel_bb_end_p (insn)
653 ? sel_bb_head (single_succ (bb))
654 : NEXT_INSN (insn));
656 if (INSN_SEQNO (succ) > 0
657 && INSN_SEQNO (succ) <= orig_max_seqno
658 && INSN_SCHED_TIMES (succ) <= 0)
660 FENCE_INSN (fence) = succ;
661 move_fence_to_fences (old_fences, new_fences);
663 if (sched_verbose >= 1)
664 sel_print ("Fence %d continues as %d[%d] (state continue)\n",
665 INSN_UID (insn), INSN_UID (succ), BLOCK_NUM (succ));
667 return;
670 /* Otherwise copy fence's structures to (possibly) multiple successors. */
671 FOR_EACH_SUCC_1 (succ, si, insn, SUCCS_NORMAL | SUCCS_SKIP_TO_LOOP_EXITS)
673 int seqno = INSN_SEQNO (succ);
675 if (0 < seqno && seqno <= orig_max_seqno
676 && (pipelining_p || INSN_SCHED_TIMES (succ) <= 0))
678 bool b = (in_same_ebb_p (insn, succ)
679 || in_fallthru_bb_p (insn, succ));
681 if (sched_verbose >= 1)
682 sel_print ("Fence %d continues as %d[%d] (state %s)\n",
683 INSN_UID (insn), INSN_UID (succ),
684 BLOCK_NUM (succ), b ? "continue" : "reset");
686 if (b)
687 add_dirty_fence_to_fences (new_fences, succ, fence);
688 else
690 /* Mark block of the SUCC as head of the new ebb. */
691 bitmap_set_bit (forced_ebb_heads, BLOCK_NUM (succ));
692 add_clean_fence_to_fences (new_fences, succ, fence);
699 /* Functions to support substitution. */
701 /* Returns whether INSN with dependence status DS is eligible for
702 substitution, i.e. it's a copy operation x := y, and RHS that is
703 moved up through this insn should be substituted. */
704 static bool
705 can_substitute_through_p (insn_t insn, ds_t ds)
707 /* We can substitute only true dependencies. */
708 if ((ds & DEP_OUTPUT)
709 || (ds & DEP_ANTI)
710 || ! INSN_RHS (insn)
711 || ! INSN_LHS (insn))
712 return false;
714 /* Now we just need to make sure the INSN_RHS consists of only one
715 simple REG rtx. */
716 if (REG_P (INSN_LHS (insn))
717 && REG_P (INSN_RHS (insn)))
718 return true;
719 return false;
722 /* Substitute all occurrences of INSN's destination in EXPR' vinsn with INSN's
723 source (if INSN is eligible for substitution). Returns TRUE if
724 substitution was actually performed, FALSE otherwise. Substitution might
725 be not performed because it's either EXPR' vinsn doesn't contain INSN's
726 destination or the resulting insn is invalid for the target machine.
727 When UNDO is true, perform unsubstitution instead (the difference is in
728 the part of rtx on which validate_replace_rtx is called). */
729 static bool
730 substitute_reg_in_expr (expr_t expr, insn_t insn, bool undo)
732 rtx *where;
733 bool new_insn_valid;
734 vinsn_t *vi = &EXPR_VINSN (expr);
735 bool has_rhs = VINSN_RHS (*vi) != NULL;
736 rtx old, new_rtx;
738 /* Do not try to replace in SET_DEST. Although we'll choose new
739 register for the RHS, we don't want to change RHS' original reg.
740 If the insn is not SET, we may still be able to substitute something
741 in it, and if we're here (don't have deps), it doesn't write INSN's
742 dest. */
743 where = (has_rhs
744 ? &VINSN_RHS (*vi)
745 : &PATTERN (VINSN_INSN_RTX (*vi)));
746 old = undo ? INSN_RHS (insn) : INSN_LHS (insn);
748 /* Substitute if INSN has a form of x:=y and LHS(INSN) occurs in *VI. */
749 if (rtx_ok_for_substitution_p (old, *where))
751 rtx_insn *new_insn;
752 rtx *where_replace;
754 /* We should copy these rtxes before substitution. */
755 new_rtx = copy_rtx (undo ? INSN_LHS (insn) : INSN_RHS (insn));
756 new_insn = create_copy_of_insn_rtx (VINSN_INSN_RTX (*vi));
758 /* Where we'll replace.
759 WHERE_REPLACE should point inside NEW_INSN, so INSN_RHS couldn't be
760 used instead of SET_SRC. */
761 where_replace = (has_rhs
762 ? &SET_SRC (PATTERN (new_insn))
763 : &PATTERN (new_insn));
765 new_insn_valid
766 = validate_replace_rtx_part_nosimplify (old, new_rtx, where_replace,
767 new_insn);
769 /* ??? Actually, constrain_operands result depends upon choice of
770 destination register. E.g. if we allow single register to be an rhs,
771 and if we try to move dx=ax(as rhs) through ax=dx, we'll result
772 in invalid insn dx=dx, so we'll loose this rhs here.
773 Just can't come up with significant testcase for this, so just
774 leaving it for now. */
775 if (new_insn_valid)
777 change_vinsn_in_expr (expr,
778 create_vinsn_from_insn_rtx (new_insn, false));
780 /* Do not allow clobbering the address register of speculative
781 insns. */
782 if ((EXPR_SPEC_DONE_DS (expr) & SPECULATIVE)
783 && register_unavailable_p (VINSN_REG_USES (EXPR_VINSN (expr)),
784 expr_dest_reg (expr)))
785 EXPR_TARGET_AVAILABLE (expr) = false;
787 return true;
789 else
790 return false;
792 else
793 return false;
796 /* Return the number of places WHAT appears within WHERE.
797 Bail out when we found a reference occupying several hard registers. */
798 static int
799 count_occurrences_equiv (const_rtx what, const_rtx where)
801 int count = 0;
802 subrtx_iterator::array_type array;
803 FOR_EACH_SUBRTX (iter, array, where, NONCONST)
805 const_rtx x = *iter;
806 if (REG_P (x) && REGNO (x) == REGNO (what))
808 /* Bail out if mode is different or more than one register is
809 used. */
810 if (GET_MODE (x) != GET_MODE (what) || REG_NREGS (x) > 1)
811 return 0;
812 count += 1;
814 else if (GET_CODE (x) == SUBREG
815 && (!REG_P (SUBREG_REG (x))
816 || REGNO (SUBREG_REG (x)) == REGNO (what)))
817 /* ??? Do not support substituting regs inside subregs. In that case,
818 simplify_subreg will be called by validate_replace_rtx, and
819 unsubstitution will fail later. */
820 return 0;
822 return count;
825 /* Returns TRUE if WHAT is found in WHERE rtx tree. */
826 static bool
827 rtx_ok_for_substitution_p (rtx what, rtx where)
829 return (count_occurrences_equiv (what, where) > 0);
833 /* Functions to support register renaming. */
835 /* Substitute VI's set source with REGNO. Returns newly created pattern
836 that has REGNO as its source. */
837 static rtx_insn *
838 create_insn_rtx_with_rhs (vinsn_t vi, rtx rhs_rtx)
840 rtx lhs_rtx;
841 rtx pattern;
842 rtx_insn *insn_rtx;
844 lhs_rtx = copy_rtx (VINSN_LHS (vi));
846 pattern = gen_rtx_SET (lhs_rtx, rhs_rtx);
847 insn_rtx = create_insn_rtx_from_pattern (pattern, NULL_RTX);
849 return insn_rtx;
852 /* Returns whether INSN's src can be replaced with register number
853 NEW_SRC_REG. E.g. the following insn is valid for i386:
855 (insn:HI 2205 6585 2207 727 ../../gcc/libiberty/regex.c:3337
856 (set (mem/s:QI (plus:SI (plus:SI (reg/f:SI 7 sp)
857 (reg:SI 0 ax [orig:770 c1 ] [770]))
858 (const_int 288 [0x120])) [0 str S1 A8])
859 (const_int 0 [0x0])) 43 {*movqi_1} (nil)
860 (nil))
862 But if we change (const_int 0 [0x0]) to (reg:QI 4 si), it will be invalid
863 because of operand constraints:
865 (define_insn "*movqi_1"
866 [(set (match_operand:QI 0 "nonimmediate_operand" "=q,q ,q ,r,r ,?r,m")
867 (match_operand:QI 1 "general_operand" " q,qn,qm,q,rn,qm,qn")
870 So do constrain_operands here, before choosing NEW_SRC_REG as best
871 reg for rhs. */
873 static bool
874 replace_src_with_reg_ok_p (insn_t insn, rtx new_src_reg)
876 vinsn_t vi = INSN_VINSN (insn);
877 machine_mode mode;
878 rtx dst_loc;
879 bool res;
881 gcc_assert (VINSN_SEPARABLE_P (vi));
883 get_dest_and_mode (insn, &dst_loc, &mode);
884 gcc_assert (mode == GET_MODE (new_src_reg));
886 if (REG_P (dst_loc) && REGNO (new_src_reg) == REGNO (dst_loc))
887 return true;
889 /* See whether SET_SRC can be replaced with this register. */
890 validate_change (insn, &SET_SRC (PATTERN (insn)), new_src_reg, 1);
891 res = verify_changes (0);
892 cancel_changes (0);
894 return res;
897 /* Returns whether INSN still be valid after replacing it's DEST with
898 register NEW_REG. */
899 static bool
900 replace_dest_with_reg_ok_p (insn_t insn, rtx new_reg)
902 vinsn_t vi = INSN_VINSN (insn);
903 bool res;
905 /* We should deal here only with separable insns. */
906 gcc_assert (VINSN_SEPARABLE_P (vi));
907 gcc_assert (GET_MODE (VINSN_LHS (vi)) == GET_MODE (new_reg));
909 /* See whether SET_DEST can be replaced with this register. */
910 validate_change (insn, &SET_DEST (PATTERN (insn)), new_reg, 1);
911 res = verify_changes (0);
912 cancel_changes (0);
914 return res;
917 /* Create a pattern with rhs of VI and lhs of LHS_RTX. */
918 static rtx_insn *
919 create_insn_rtx_with_lhs (vinsn_t vi, rtx lhs_rtx)
921 rtx rhs_rtx;
922 rtx pattern;
923 rtx_insn *insn_rtx;
925 rhs_rtx = copy_rtx (VINSN_RHS (vi));
927 pattern = gen_rtx_SET (lhs_rtx, rhs_rtx);
928 insn_rtx = create_insn_rtx_from_pattern (pattern, NULL_RTX);
930 return insn_rtx;
933 /* Substitute lhs in the given expression EXPR for the register with number
934 NEW_REGNO. SET_DEST may be arbitrary rtx, not only register. */
935 static void
936 replace_dest_with_reg_in_expr (expr_t expr, rtx new_reg)
938 rtx_insn *insn_rtx;
939 vinsn_t vinsn;
941 insn_rtx = create_insn_rtx_with_lhs (EXPR_VINSN (expr), new_reg);
942 vinsn = create_vinsn_from_insn_rtx (insn_rtx, false);
944 change_vinsn_in_expr (expr, vinsn);
945 EXPR_WAS_RENAMED (expr) = 1;
946 EXPR_TARGET_AVAILABLE (expr) = 1;
949 /* Returns whether VI writes either one of the USED_REGS registers or,
950 if a register is a hard one, one of the UNAVAILABLE_HARD_REGS registers. */
951 static bool
952 vinsn_writes_one_of_regs_p (vinsn_t vi, regset used_regs,
953 HARD_REG_SET unavailable_hard_regs)
955 unsigned regno;
956 reg_set_iterator rsi;
958 EXECUTE_IF_SET_IN_REG_SET (VINSN_REG_SETS (vi), 0, regno, rsi)
960 if (REGNO_REG_SET_P (used_regs, regno))
961 return true;
962 if (HARD_REGISTER_NUM_P (regno)
963 && TEST_HARD_REG_BIT (unavailable_hard_regs, regno))
964 return true;
967 EXECUTE_IF_SET_IN_REG_SET (VINSN_REG_CLOBBERS (vi), 0, regno, rsi)
969 if (REGNO_REG_SET_P (used_regs, regno))
970 return true;
971 if (HARD_REGISTER_NUM_P (regno)
972 && TEST_HARD_REG_BIT (unavailable_hard_regs, regno))
973 return true;
976 return false;
979 /* Returns register class of the output register in INSN.
980 Returns NO_REGS for call insns because some targets have constraints on
981 destination register of a call insn.
983 Code adopted from regrename.c::build_def_use. */
984 static enum reg_class
985 get_reg_class (rtx_insn *insn)
987 int i, n_ops;
989 extract_constrain_insn (insn);
990 preprocess_constraints (insn);
991 n_ops = recog_data.n_operands;
993 const operand_alternative *op_alt = which_op_alt ();
994 if (asm_noperands (PATTERN (insn)) > 0)
996 for (i = 0; i < n_ops; i++)
997 if (recog_data.operand_type[i] == OP_OUT)
999 rtx *loc = recog_data.operand_loc[i];
1000 rtx op = *loc;
1001 enum reg_class cl = alternative_class (op_alt, i);
1003 if (REG_P (op)
1004 && REGNO (op) == ORIGINAL_REGNO (op))
1005 continue;
1007 return cl;
1010 else if (!CALL_P (insn))
1012 for (i = 0; i < n_ops + recog_data.n_dups; i++)
1014 int opn = i < n_ops ? i : recog_data.dup_num[i - n_ops];
1015 enum reg_class cl = alternative_class (op_alt, opn);
1017 if (recog_data.operand_type[opn] == OP_OUT ||
1018 recog_data.operand_type[opn] == OP_INOUT)
1019 return cl;
1023 /* Insns like
1024 (insn (set (reg:CCZ 17 flags) (compare:CCZ ...)))
1025 may result in returning NO_REGS, cause flags is written implicitly through
1026 CMP insn, which has no OP_OUT | OP_INOUT operands. */
1027 return NO_REGS;
1030 /* Calculate HARD_REGNO_RENAME_OK data for REGNO. */
1031 static void
1032 init_hard_regno_rename (int regno)
1034 int cur_reg;
1036 SET_HARD_REG_BIT (sel_hrd.regs_for_rename[regno], regno);
1038 for (cur_reg = 0; cur_reg < FIRST_PSEUDO_REGISTER; cur_reg++)
1040 /* We are not interested in renaming in other regs. */
1041 if (!TEST_HARD_REG_BIT (sel_hrd.regs_ever_used, cur_reg))
1042 continue;
1044 if (HARD_REGNO_RENAME_OK (regno, cur_reg))
1045 SET_HARD_REG_BIT (sel_hrd.regs_for_rename[regno], cur_reg);
1049 /* A wrapper around HARD_REGNO_RENAME_OK that will look into the hard regs
1050 data first. */
1051 static inline bool
1052 sel_hard_regno_rename_ok (int from ATTRIBUTE_UNUSED, int to ATTRIBUTE_UNUSED)
1054 /* Check whether this is all calculated. */
1055 if (TEST_HARD_REG_BIT (sel_hrd.regs_for_rename[from], from))
1056 return TEST_HARD_REG_BIT (sel_hrd.regs_for_rename[from], to);
1058 init_hard_regno_rename (from);
1060 return TEST_HARD_REG_BIT (sel_hrd.regs_for_rename[from], to);
1063 /* Calculate set of registers that are capable of holding MODE. */
1064 static void
1065 init_regs_for_mode (machine_mode mode)
1067 int cur_reg;
1069 CLEAR_HARD_REG_SET (sel_hrd.regs_for_mode[mode]);
1070 CLEAR_HARD_REG_SET (sel_hrd.regs_for_call_clobbered[mode]);
1072 for (cur_reg = 0; cur_reg < FIRST_PSEUDO_REGISTER; cur_reg++)
1074 int nregs;
1075 int i;
1077 /* See whether it accepts all modes that occur in
1078 original insns. */
1079 if (! HARD_REGNO_MODE_OK (cur_reg, mode))
1080 continue;
1082 nregs = hard_regno_nregs[cur_reg][mode];
1084 for (i = nregs - 1; i >= 0; --i)
1085 if (fixed_regs[cur_reg + i]
1086 || global_regs[cur_reg + i]
1087 /* Can't use regs which aren't saved by
1088 the prologue. */
1089 || !TEST_HARD_REG_BIT (sel_hrd.regs_ever_used, cur_reg + i)
1090 /* Can't use regs with non-null REG_BASE_VALUE, because adjusting
1091 it affects aliasing globally and invalidates all AV sets. */
1092 || get_reg_base_value (cur_reg + i)
1093 #ifdef LEAF_REGISTERS
1094 /* We can't use a non-leaf register if we're in a
1095 leaf function. */
1096 || (crtl->is_leaf
1097 && !LEAF_REGISTERS[cur_reg + i])
1098 #endif
1100 break;
1102 if (i >= 0)
1103 continue;
1105 if (HARD_REGNO_CALL_PART_CLOBBERED (cur_reg, mode))
1106 SET_HARD_REG_BIT (sel_hrd.regs_for_call_clobbered[mode],
1107 cur_reg);
1109 /* If the CUR_REG passed all the checks above,
1110 then it's ok. */
1111 SET_HARD_REG_BIT (sel_hrd.regs_for_mode[mode], cur_reg);
1114 sel_hrd.regs_for_mode_ok[mode] = true;
1117 /* Init all register sets gathered in HRD. */
1118 static void
1119 init_hard_regs_data (void)
1121 int cur_reg = 0;
1122 int cur_mode = 0;
1124 CLEAR_HARD_REG_SET (sel_hrd.regs_ever_used);
1125 for (cur_reg = 0; cur_reg < FIRST_PSEUDO_REGISTER; cur_reg++)
1126 if (df_regs_ever_live_p (cur_reg) || call_used_regs[cur_reg])
1127 SET_HARD_REG_BIT (sel_hrd.regs_ever_used, cur_reg);
1129 /* Initialize registers that are valid based on mode when this is
1130 really needed. */
1131 for (cur_mode = 0; cur_mode < NUM_MACHINE_MODES; cur_mode++)
1132 sel_hrd.regs_for_mode_ok[cur_mode] = false;
1134 /* Mark that all HARD_REGNO_RENAME_OK is not calculated. */
1135 for (cur_reg = 0; cur_reg < FIRST_PSEUDO_REGISTER; cur_reg++)
1136 CLEAR_HARD_REG_SET (sel_hrd.regs_for_rename[cur_reg]);
1138 #ifdef STACK_REGS
1139 CLEAR_HARD_REG_SET (sel_hrd.stack_regs);
1141 for (cur_reg = FIRST_STACK_REG; cur_reg <= LAST_STACK_REG; cur_reg++)
1142 SET_HARD_REG_BIT (sel_hrd.stack_regs, cur_reg);
1143 #endif
1146 /* Mark hardware regs in REG_RENAME_P that are not suitable
1147 for renaming rhs in INSN due to hardware restrictions (register class,
1148 modes compatibility etc). This doesn't affect original insn's dest reg,
1149 if it isn't in USED_REGS. DEF is a definition insn of rhs for which the
1150 destination register is sought. LHS (DEF->ORIG_INSN) may be REG or MEM.
1151 Registers that are in used_regs are always marked in
1152 unavailable_hard_regs as well. */
1154 static void
1155 mark_unavailable_hard_regs (def_t def, struct reg_rename *reg_rename_p,
1156 regset used_regs ATTRIBUTE_UNUSED)
1158 machine_mode mode;
1159 enum reg_class cl = NO_REGS;
1160 rtx orig_dest;
1161 unsigned cur_reg, regno;
1162 hard_reg_set_iterator hrsi;
1164 gcc_assert (GET_CODE (PATTERN (def->orig_insn)) == SET);
1165 gcc_assert (reg_rename_p);
1167 orig_dest = SET_DEST (PATTERN (def->orig_insn));
1169 /* We have decided not to rename 'mem = something;' insns, as 'something'
1170 is usually a register. */
1171 if (!REG_P (orig_dest))
1172 return;
1174 regno = REGNO (orig_dest);
1176 /* If before reload, don't try to work with pseudos. */
1177 if (!reload_completed && !HARD_REGISTER_NUM_P (regno))
1178 return;
1180 if (reload_completed)
1181 cl = get_reg_class (def->orig_insn);
1183 /* Stop if the original register is one of the fixed_regs, global_regs or
1184 frame pointer, or we could not discover its class. */
1185 if (fixed_regs[regno]
1186 || global_regs[regno]
1187 || (!HARD_FRAME_POINTER_IS_FRAME_POINTER && frame_pointer_needed
1188 && regno == HARD_FRAME_POINTER_REGNUM)
1189 || (HARD_FRAME_POINTER_IS_FRAME_POINTER && frame_pointer_needed
1190 && regno == FRAME_POINTER_REGNUM)
1191 || (reload_completed && cl == NO_REGS))
1193 SET_HARD_REG_SET (reg_rename_p->unavailable_hard_regs);
1195 /* Give a chance for original register, if it isn't in used_regs. */
1196 if (!def->crosses_call)
1197 CLEAR_HARD_REG_BIT (reg_rename_p->unavailable_hard_regs, regno);
1199 return;
1202 /* If something allocated on stack in this function, mark frame pointer
1203 register unavailable, considering also modes.
1204 FIXME: it is enough to do this once per all original defs. */
1205 if (frame_pointer_needed)
1207 add_to_hard_reg_set (&reg_rename_p->unavailable_hard_regs,
1208 Pmode, FRAME_POINTER_REGNUM);
1210 if (!HARD_FRAME_POINTER_IS_FRAME_POINTER)
1211 add_to_hard_reg_set (&reg_rename_p->unavailable_hard_regs,
1212 Pmode, HARD_FRAME_POINTER_REGNUM);
1215 #ifdef STACK_REGS
1216 /* For the stack registers the presence of FIRST_STACK_REG in USED_REGS
1217 is equivalent to as if all stack regs were in this set.
1218 I.e. no stack register can be renamed, and even if it's an original
1219 register here we make sure it won't be lifted over it's previous def
1220 (it's previous def will appear as if it's a FIRST_STACK_REG def.
1221 The HARD_REGNO_RENAME_OK covers other cases in condition below. */
1222 if (IN_RANGE (REGNO (orig_dest), FIRST_STACK_REG, LAST_STACK_REG)
1223 && REGNO_REG_SET_P (used_regs, FIRST_STACK_REG))
1224 IOR_HARD_REG_SET (reg_rename_p->unavailable_hard_regs,
1225 sel_hrd.stack_regs);
1226 #endif
1228 /* If there's a call on this path, make regs from call_used_reg_set
1229 unavailable. */
1230 if (def->crosses_call)
1231 IOR_HARD_REG_SET (reg_rename_p->unavailable_hard_regs,
1232 call_used_reg_set);
1234 /* Stop here before reload: we need FRAME_REGS, STACK_REGS, and crosses_call,
1235 but not register classes. */
1236 if (!reload_completed)
1237 return;
1239 /* Leave regs as 'available' only from the current
1240 register class. */
1241 COPY_HARD_REG_SET (reg_rename_p->available_for_renaming,
1242 reg_class_contents[cl]);
1244 mode = GET_MODE (orig_dest);
1246 /* Leave only registers available for this mode. */
1247 if (!sel_hrd.regs_for_mode_ok[mode])
1248 init_regs_for_mode (mode);
1249 AND_HARD_REG_SET (reg_rename_p->available_for_renaming,
1250 sel_hrd.regs_for_mode[mode]);
1252 /* Exclude registers that are partially call clobbered. */
1253 if (def->crosses_call
1254 && ! HARD_REGNO_CALL_PART_CLOBBERED (regno, mode))
1255 AND_COMPL_HARD_REG_SET (reg_rename_p->available_for_renaming,
1256 sel_hrd.regs_for_call_clobbered[mode]);
1258 /* Leave only those that are ok to rename. */
1259 EXECUTE_IF_SET_IN_HARD_REG_SET (reg_rename_p->available_for_renaming,
1260 0, cur_reg, hrsi)
1262 int nregs;
1263 int i;
1265 nregs = hard_regno_nregs[cur_reg][mode];
1266 gcc_assert (nregs > 0);
1268 for (i = nregs - 1; i >= 0; --i)
1269 if (! sel_hard_regno_rename_ok (regno + i, cur_reg + i))
1270 break;
1272 if (i >= 0)
1273 CLEAR_HARD_REG_BIT (reg_rename_p->available_for_renaming,
1274 cur_reg);
1277 AND_COMPL_HARD_REG_SET (reg_rename_p->available_for_renaming,
1278 reg_rename_p->unavailable_hard_regs);
1280 /* Regno is always ok from the renaming part of view, but it really
1281 could be in *unavailable_hard_regs already, so set it here instead
1282 of there. */
1283 SET_HARD_REG_BIT (reg_rename_p->available_for_renaming, regno);
1286 /* reg_rename_tick[REG1] > reg_rename_tick[REG2] if REG1 was chosen as the
1287 best register more recently than REG2. */
1288 static int reg_rename_tick[FIRST_PSEUDO_REGISTER];
1290 /* Indicates the number of times renaming happened before the current one. */
1291 static int reg_rename_this_tick;
1293 /* Choose the register among free, that is suitable for storing
1294 the rhs value.
1296 ORIGINAL_INSNS is the list of insns where the operation (rhs)
1297 originally appears. There could be multiple original operations
1298 for single rhs since we moving it up and merging along different
1299 paths.
1301 Some code is adapted from regrename.c (regrename_optimize).
1302 If original register is available, function returns it.
1303 Otherwise it performs the checks, so the new register should
1304 comply with the following:
1305 - it should not violate any live ranges (such registers are in
1306 REG_RENAME_P->available_for_renaming set);
1307 - it should not be in the HARD_REGS_USED regset;
1308 - it should be in the class compatible with original uses;
1309 - it should not be clobbered through reference with different mode;
1310 - if we're in the leaf function, then the new register should
1311 not be in the LEAF_REGISTERS;
1312 - etc.
1314 If several registers meet the conditions, the register with smallest
1315 tick is returned to achieve more even register allocation.
1317 If original register seems to be ok, we set *IS_ORIG_REG_P_PTR to true.
1319 If no register satisfies the above conditions, NULL_RTX is returned. */
1320 static rtx
1321 choose_best_reg_1 (HARD_REG_SET hard_regs_used,
1322 struct reg_rename *reg_rename_p,
1323 def_list_t original_insns, bool *is_orig_reg_p_ptr)
1325 int best_new_reg;
1326 unsigned cur_reg;
1327 machine_mode mode = VOIDmode;
1328 unsigned regno, i, n;
1329 hard_reg_set_iterator hrsi;
1330 def_list_iterator di;
1331 def_t def;
1333 /* If original register is available, return it. */
1334 *is_orig_reg_p_ptr = true;
1336 FOR_EACH_DEF (def, di, original_insns)
1338 rtx orig_dest = SET_DEST (PATTERN (def->orig_insn));
1340 gcc_assert (REG_P (orig_dest));
1342 /* Check that all original operations have the same mode.
1343 This is done for the next loop; if we'd return from this
1344 loop, we'd check only part of them, but in this case
1345 it doesn't matter. */
1346 if (mode == VOIDmode)
1347 mode = GET_MODE (orig_dest);
1348 gcc_assert (mode == GET_MODE (orig_dest));
1350 regno = REGNO (orig_dest);
1351 for (i = 0, n = hard_regno_nregs[regno][mode]; i < n; i++)
1352 if (TEST_HARD_REG_BIT (hard_regs_used, regno + i))
1353 break;
1355 /* All hard registers are available. */
1356 if (i == n)
1358 gcc_assert (mode != VOIDmode);
1360 /* Hard registers should not be shared. */
1361 return gen_rtx_REG (mode, regno);
1365 *is_orig_reg_p_ptr = false;
1366 best_new_reg = -1;
1368 /* Among all available regs choose the register that was
1369 allocated earliest. */
1370 EXECUTE_IF_SET_IN_HARD_REG_SET (reg_rename_p->available_for_renaming,
1371 0, cur_reg, hrsi)
1372 if (! TEST_HARD_REG_BIT (hard_regs_used, cur_reg))
1374 /* Check that all hard regs for mode are available. */
1375 for (i = 1, n = hard_regno_nregs[cur_reg][mode]; i < n; i++)
1376 if (TEST_HARD_REG_BIT (hard_regs_used, cur_reg + i)
1377 || !TEST_HARD_REG_BIT (reg_rename_p->available_for_renaming,
1378 cur_reg + i))
1379 break;
1381 if (i < n)
1382 continue;
1384 /* All hard registers are available. */
1385 if (best_new_reg < 0
1386 || reg_rename_tick[cur_reg] < reg_rename_tick[best_new_reg])
1388 best_new_reg = cur_reg;
1390 /* Return immediately when we know there's no better reg. */
1391 if (! reg_rename_tick[best_new_reg])
1392 break;
1396 if (best_new_reg >= 0)
1398 /* Use the check from the above loop. */
1399 gcc_assert (mode != VOIDmode);
1400 return gen_rtx_REG (mode, best_new_reg);
1403 return NULL_RTX;
1406 /* A wrapper around choose_best_reg_1 () to verify that we make correct
1407 assumptions about available registers in the function. */
1408 static rtx
1409 choose_best_reg (HARD_REG_SET hard_regs_used, struct reg_rename *reg_rename_p,
1410 def_list_t original_insns, bool *is_orig_reg_p_ptr)
1412 rtx best_reg = choose_best_reg_1 (hard_regs_used, reg_rename_p,
1413 original_insns, is_orig_reg_p_ptr);
1415 /* FIXME loop over hard_regno_nregs here. */
1416 gcc_assert (best_reg == NULL_RTX
1417 || TEST_HARD_REG_BIT (sel_hrd.regs_ever_used, REGNO (best_reg)));
1419 return best_reg;
1422 /* Choose the pseudo register for storing rhs value. As this is supposed
1423 to work before reload, we return either the original register or make
1424 the new one. The parameters are the same that in choose_nest_reg_1
1425 functions, except that USED_REGS may contain pseudos.
1426 If we work with hard regs, check also REG_RENAME_P->UNAVAILABLE_HARD_REGS.
1428 TODO: take into account register pressure while doing this. Up to this
1429 moment, this function would never return NULL for pseudos, but we should
1430 not rely on this. */
1431 static rtx
1432 choose_best_pseudo_reg (regset used_regs,
1433 struct reg_rename *reg_rename_p,
1434 def_list_t original_insns, bool *is_orig_reg_p_ptr)
1436 def_list_iterator i;
1437 def_t def;
1438 machine_mode mode = VOIDmode;
1439 bool bad_hard_regs = false;
1441 /* We should not use this after reload. */
1442 gcc_assert (!reload_completed);
1444 /* If original register is available, return it. */
1445 *is_orig_reg_p_ptr = true;
1447 FOR_EACH_DEF (def, i, original_insns)
1449 rtx dest = SET_DEST (PATTERN (def->orig_insn));
1450 int orig_regno;
1452 gcc_assert (REG_P (dest));
1454 /* Check that all original operations have the same mode. */
1455 if (mode == VOIDmode)
1456 mode = GET_MODE (dest);
1457 else
1458 gcc_assert (mode == GET_MODE (dest));
1459 orig_regno = REGNO (dest);
1461 /* Check that nothing in used_regs intersects with orig_regno. When
1462 we have a hard reg here, still loop over hard_regno_nregs. */
1463 if (HARD_REGISTER_NUM_P (orig_regno))
1465 int j, n;
1466 for (j = 0, n = hard_regno_nregs[orig_regno][mode]; j < n; j++)
1467 if (REGNO_REG_SET_P (used_regs, orig_regno + j))
1468 break;
1469 if (j < n)
1470 continue;
1472 else
1474 if (REGNO_REG_SET_P (used_regs, orig_regno))
1475 continue;
1477 if (HARD_REGISTER_NUM_P (orig_regno))
1479 gcc_assert (df_regs_ever_live_p (orig_regno));
1481 /* For hard registers, we have to check hardware imposed
1482 limitations (frame/stack registers, calls crossed). */
1483 if (!TEST_HARD_REG_BIT (reg_rename_p->unavailable_hard_regs,
1484 orig_regno))
1486 /* Don't let register cross a call if it doesn't already
1487 cross one. This condition is written in accordance with
1488 that in sched-deps.c sched_analyze_reg(). */
1489 if (!reg_rename_p->crosses_call
1490 || REG_N_CALLS_CROSSED (orig_regno) > 0)
1491 return gen_rtx_REG (mode, orig_regno);
1494 bad_hard_regs = true;
1496 else
1497 return dest;
1500 *is_orig_reg_p_ptr = false;
1502 /* We had some original hard registers that couldn't be used.
1503 Those were likely special. Don't try to create a pseudo. */
1504 if (bad_hard_regs)
1505 return NULL_RTX;
1507 /* We haven't found a register from original operations. Get a new one.
1508 FIXME: control register pressure somehow. */
1510 rtx new_reg = gen_reg_rtx (mode);
1512 gcc_assert (mode != VOIDmode);
1514 max_regno = max_reg_num ();
1515 maybe_extend_reg_info_p ();
1516 REG_N_CALLS_CROSSED (REGNO (new_reg)) = reg_rename_p->crosses_call ? 1 : 0;
1518 return new_reg;
1522 /* True when target of EXPR is available due to EXPR_TARGET_AVAILABLE,
1523 USED_REGS and REG_RENAME_P->UNAVAILABLE_HARD_REGS. */
1524 static void
1525 verify_target_availability (expr_t expr, regset used_regs,
1526 struct reg_rename *reg_rename_p)
1528 unsigned n, i, regno;
1529 machine_mode mode;
1530 bool target_available, live_available, hard_available;
1532 if (!REG_P (EXPR_LHS (expr)) || EXPR_TARGET_AVAILABLE (expr) < 0)
1533 return;
1535 regno = expr_dest_regno (expr);
1536 mode = GET_MODE (EXPR_LHS (expr));
1537 target_available = EXPR_TARGET_AVAILABLE (expr) == 1;
1538 n = HARD_REGISTER_NUM_P (regno) ? hard_regno_nregs[regno][mode] : 1;
1540 live_available = hard_available = true;
1541 for (i = 0; i < n; i++)
1543 if (bitmap_bit_p (used_regs, regno + i))
1544 live_available = false;
1545 if (TEST_HARD_REG_BIT (reg_rename_p->unavailable_hard_regs, regno + i))
1546 hard_available = false;
1549 /* When target is not available, it may be due to hard register
1550 restrictions, e.g. crosses calls, so we check hard_available too. */
1551 if (target_available)
1552 gcc_assert (live_available);
1553 else
1554 /* Check only if we haven't scheduled something on the previous fence,
1555 cause due to MAX_SOFTWARE_LOOKAHEAD_WINDOW_SIZE issues
1556 and having more than one fence, we may end having targ_un in a block
1557 in which successors target register is actually available.
1559 The last condition handles the case when a dependence from a call insn
1560 was created in sched-deps.c for insns with destination registers that
1561 never crossed a call before, but do cross one after our code motion.
1563 FIXME: in the latter case, we just uselessly called find_used_regs,
1564 because we can't move this expression with any other register
1565 as well. */
1566 gcc_assert (scheduled_something_on_previous_fence || !live_available
1567 || !hard_available
1568 || (!reload_completed && reg_rename_p->crosses_call
1569 && REG_N_CALLS_CROSSED (regno) == 0));
1572 /* Collect unavailable registers due to liveness for EXPR from BNDS
1573 into USED_REGS. Save additional information about available
1574 registers and unavailable due to hardware restriction registers
1575 into REG_RENAME_P structure. Save original insns into ORIGINAL_INSNS
1576 list. */
1577 static void
1578 collect_unavailable_regs_from_bnds (expr_t expr, blist_t bnds, regset used_regs,
1579 struct reg_rename *reg_rename_p,
1580 def_list_t *original_insns)
1582 for (; bnds; bnds = BLIST_NEXT (bnds))
1584 bool res;
1585 av_set_t orig_ops = NULL;
1586 bnd_t bnd = BLIST_BND (bnds);
1588 /* If the chosen best expr doesn't belong to current boundary,
1589 skip it. */
1590 if (!av_set_is_in_p (BND_AV1 (bnd), EXPR_VINSN (expr)))
1591 continue;
1593 /* Put in ORIG_OPS all exprs from this boundary that became
1594 RES on top. */
1595 orig_ops = find_sequential_best_exprs (bnd, expr, false);
1597 /* Compute used regs and OR it into the USED_REGS. */
1598 res = find_used_regs (BND_TO (bnd), orig_ops, used_regs,
1599 reg_rename_p, original_insns);
1601 /* FIXME: the assert is true until we'd have several boundaries. */
1602 gcc_assert (res);
1603 av_set_clear (&orig_ops);
1607 /* Return TRUE if it is possible to replace LHSes of ORIG_INSNS with BEST_REG.
1608 If BEST_REG is valid, replace LHS of EXPR with it. */
1609 static bool
1610 try_replace_dest_reg (ilist_t orig_insns, rtx best_reg, expr_t expr)
1612 /* Try whether we'll be able to generate the insn
1613 'dest := best_reg' at the place of the original operation. */
1614 for (; orig_insns; orig_insns = ILIST_NEXT (orig_insns))
1616 insn_t orig_insn = DEF_LIST_DEF (orig_insns)->orig_insn;
1618 gcc_assert (EXPR_SEPARABLE_P (INSN_EXPR (orig_insn)));
1620 if (REGNO (best_reg) != REGNO (INSN_LHS (orig_insn))
1621 && (! replace_src_with_reg_ok_p (orig_insn, best_reg)
1622 || ! replace_dest_with_reg_ok_p (orig_insn, best_reg)))
1623 return false;
1626 /* Make sure that EXPR has the right destination
1627 register. */
1628 if (expr_dest_regno (expr) != REGNO (best_reg))
1629 replace_dest_with_reg_in_expr (expr, best_reg);
1630 else
1631 EXPR_TARGET_AVAILABLE (expr) = 1;
1633 return true;
1636 /* Select and assign best register to EXPR searching from BNDS.
1637 Set *IS_ORIG_REG_P to TRUE if original register was selected.
1638 Return FALSE if no register can be chosen, which could happen when:
1639 * EXPR_SEPARABLE_P is true but we were unable to find suitable register;
1640 * EXPR_SEPARABLE_P is false but the insn sets/clobbers one of the registers
1641 that are used on the moving path. */
1642 static bool
1643 find_best_reg_for_expr (expr_t expr, blist_t bnds, bool *is_orig_reg_p)
1645 static struct reg_rename reg_rename_data;
1647 regset used_regs;
1648 def_list_t original_insns = NULL;
1649 bool reg_ok;
1651 *is_orig_reg_p = false;
1653 /* Don't bother to do anything if this insn doesn't set any registers. */
1654 if (bitmap_empty_p (VINSN_REG_SETS (EXPR_VINSN (expr)))
1655 && bitmap_empty_p (VINSN_REG_CLOBBERS (EXPR_VINSN (expr))))
1656 return true;
1658 used_regs = get_clear_regset_from_pool ();
1659 CLEAR_HARD_REG_SET (reg_rename_data.unavailable_hard_regs);
1661 collect_unavailable_regs_from_bnds (expr, bnds, used_regs, &reg_rename_data,
1662 &original_insns);
1664 /* If after reload, make sure we're working with hard regs here. */
1665 if (flag_checking && reload_completed)
1667 reg_set_iterator rsi;
1668 unsigned i;
1670 EXECUTE_IF_SET_IN_REG_SET (used_regs, FIRST_PSEUDO_REGISTER, i, rsi)
1671 gcc_unreachable ();
1674 if (EXPR_SEPARABLE_P (expr))
1676 rtx best_reg = NULL_RTX;
1677 /* Check that we have computed availability of a target register
1678 correctly. */
1679 verify_target_availability (expr, used_regs, &reg_rename_data);
1681 /* Turn everything in hard regs after reload. */
1682 if (reload_completed)
1684 HARD_REG_SET hard_regs_used;
1685 REG_SET_TO_HARD_REG_SET (hard_regs_used, used_regs);
1687 /* Join hard registers unavailable due to register class
1688 restrictions and live range intersection. */
1689 IOR_HARD_REG_SET (hard_regs_used,
1690 reg_rename_data.unavailable_hard_regs);
1692 best_reg = choose_best_reg (hard_regs_used, &reg_rename_data,
1693 original_insns, is_orig_reg_p);
1695 else
1696 best_reg = choose_best_pseudo_reg (used_regs, &reg_rename_data,
1697 original_insns, is_orig_reg_p);
1699 if (!best_reg)
1700 reg_ok = false;
1701 else if (*is_orig_reg_p)
1703 /* In case of unification BEST_REG may be different from EXPR's LHS
1704 when EXPR's LHS is unavailable, and there is another LHS among
1705 ORIGINAL_INSNS. */
1706 reg_ok = try_replace_dest_reg (original_insns, best_reg, expr);
1708 else
1710 /* Forbid renaming of low-cost insns. */
1711 if (sel_vinsn_cost (EXPR_VINSN (expr)) < 2)
1712 reg_ok = false;
1713 else
1714 reg_ok = try_replace_dest_reg (original_insns, best_reg, expr);
1717 else
1719 /* If !EXPR_SCHEDULE_AS_RHS (EXPR), just make sure INSN doesn't set
1720 any of the HARD_REGS_USED set. */
1721 if (vinsn_writes_one_of_regs_p (EXPR_VINSN (expr), used_regs,
1722 reg_rename_data.unavailable_hard_regs))
1724 reg_ok = false;
1725 gcc_assert (EXPR_TARGET_AVAILABLE (expr) <= 0);
1727 else
1729 reg_ok = true;
1730 gcc_assert (EXPR_TARGET_AVAILABLE (expr) != 0);
1734 ilist_clear (&original_insns);
1735 return_regset_to_pool (used_regs);
1737 return reg_ok;
1741 /* Return true if dependence described by DS can be overcomed. */
1742 static bool
1743 can_speculate_dep_p (ds_t ds)
1745 if (spec_info == NULL)
1746 return false;
1748 /* Leave only speculative data. */
1749 ds &= SPECULATIVE;
1751 if (ds == 0)
1752 return false;
1755 /* FIXME: make sched-deps.c produce only those non-hard dependencies,
1756 that we can overcome. */
1757 ds_t spec_mask = spec_info->mask;
1759 if ((ds & spec_mask) != ds)
1760 return false;
1763 if (ds_weak (ds) < spec_info->data_weakness_cutoff)
1764 return false;
1766 return true;
1769 /* Get a speculation check instruction.
1770 C_EXPR is a speculative expression,
1771 CHECK_DS describes speculations that should be checked,
1772 ORIG_INSN is the original non-speculative insn in the stream. */
1773 static insn_t
1774 create_speculation_check (expr_t c_expr, ds_t check_ds, insn_t orig_insn)
1776 rtx check_pattern;
1777 rtx_insn *insn_rtx;
1778 insn_t insn;
1779 basic_block recovery_block;
1780 rtx_insn *label;
1782 /* Create a recovery block if target is going to emit branchy check, or if
1783 ORIG_INSN was speculative already. */
1784 if (targetm.sched.needs_block_p (check_ds)
1785 || EXPR_SPEC_DONE_DS (INSN_EXPR (orig_insn)) != 0)
1787 recovery_block = sel_create_recovery_block (orig_insn);
1788 label = BB_HEAD (recovery_block);
1790 else
1792 recovery_block = NULL;
1793 label = NULL;
1796 /* Get pattern of the check. */
1797 check_pattern = targetm.sched.gen_spec_check (EXPR_INSN_RTX (c_expr), label,
1798 check_ds);
1800 gcc_assert (check_pattern != NULL);
1802 /* Emit check. */
1803 insn_rtx = create_insn_rtx_from_pattern (check_pattern, label);
1805 insn = sel_gen_insn_from_rtx_after (insn_rtx, INSN_EXPR (orig_insn),
1806 INSN_SEQNO (orig_insn), orig_insn);
1808 /* Make check to be non-speculative. */
1809 EXPR_SPEC_DONE_DS (INSN_EXPR (insn)) = 0;
1810 INSN_SPEC_CHECKED_DS (insn) = check_ds;
1812 /* Decrease priority of check by difference of load/check instruction
1813 latencies. */
1814 EXPR_PRIORITY (INSN_EXPR (insn)) -= (sel_vinsn_cost (INSN_VINSN (orig_insn))
1815 - sel_vinsn_cost (INSN_VINSN (insn)));
1817 /* Emit copy of original insn (though with replaced target register,
1818 if needed) to the recovery block. */
1819 if (recovery_block != NULL)
1821 rtx twin_rtx;
1823 twin_rtx = copy_rtx (PATTERN (EXPR_INSN_RTX (c_expr)));
1824 twin_rtx = create_insn_rtx_from_pattern (twin_rtx, NULL_RTX);
1825 sel_gen_recovery_insn_from_rtx_after (twin_rtx,
1826 INSN_EXPR (orig_insn),
1827 INSN_SEQNO (insn),
1828 bb_note (recovery_block));
1831 /* If we've generated a data speculation check, make sure
1832 that all the bookkeeping instruction we'll create during
1833 this move_op () will allocate an ALAT entry so that the
1834 check won't fail.
1835 In case of control speculation we must convert C_EXPR to control
1836 speculative mode, because failing to do so will bring us an exception
1837 thrown by the non-control-speculative load. */
1838 check_ds = ds_get_max_dep_weak (check_ds);
1839 speculate_expr (c_expr, check_ds);
1841 return insn;
1844 /* True when INSN is a "regN = regN" copy. */
1845 static bool
1846 identical_copy_p (rtx_insn *insn)
1848 rtx lhs, rhs, pat;
1850 pat = PATTERN (insn);
1852 if (GET_CODE (pat) != SET)
1853 return false;
1855 lhs = SET_DEST (pat);
1856 if (!REG_P (lhs))
1857 return false;
1859 rhs = SET_SRC (pat);
1860 if (!REG_P (rhs))
1861 return false;
1863 return REGNO (lhs) == REGNO (rhs);
1866 /* Undo all transformations on *AV_PTR that were done when
1867 moving through INSN. */
1868 static void
1869 undo_transformations (av_set_t *av_ptr, rtx_insn *insn)
1871 av_set_iterator av_iter;
1872 expr_t expr;
1873 av_set_t new_set = NULL;
1875 /* First, kill any EXPR that uses registers set by an insn. This is
1876 required for correctness. */
1877 FOR_EACH_EXPR_1 (expr, av_iter, av_ptr)
1878 if (!sched_insns_conditions_mutex_p (insn, EXPR_INSN_RTX (expr))
1879 && bitmap_intersect_p (INSN_REG_SETS (insn),
1880 VINSN_REG_USES (EXPR_VINSN (expr)))
1881 /* When an insn looks like 'r1 = r1', we could substitute through
1882 it, but the above condition will still hold. This happened with
1883 gcc.c-torture/execute/961125-1.c. */
1884 && !identical_copy_p (insn))
1886 if (sched_verbose >= 6)
1887 sel_print ("Expr %d removed due to use/set conflict\n",
1888 INSN_UID (EXPR_INSN_RTX (expr)));
1889 av_set_iter_remove (&av_iter);
1892 /* Undo transformations looking at the history vector. */
1893 FOR_EACH_EXPR (expr, av_iter, *av_ptr)
1895 int index = find_in_history_vect (EXPR_HISTORY_OF_CHANGES (expr),
1896 insn, EXPR_VINSN (expr), true);
1898 if (index >= 0)
1900 expr_history_def *phist;
1902 phist = &EXPR_HISTORY_OF_CHANGES (expr)[index];
1904 switch (phist->type)
1906 case TRANS_SPECULATION:
1908 ds_t old_ds, new_ds;
1910 /* Compute the difference between old and new speculative
1911 statuses: that's what we need to check.
1912 Earlier we used to assert that the status will really
1913 change. This no longer works because only the probability
1914 bits in the status may have changed during compute_av_set,
1915 and in the case of merging different probabilities of the
1916 same speculative status along different paths we do not
1917 record this in the history vector. */
1918 old_ds = phist->spec_ds;
1919 new_ds = EXPR_SPEC_DONE_DS (expr);
1921 old_ds &= SPECULATIVE;
1922 new_ds &= SPECULATIVE;
1923 new_ds &= ~old_ds;
1925 EXPR_SPEC_TO_CHECK_DS (expr) |= new_ds;
1926 break;
1928 case TRANS_SUBSTITUTION:
1930 expr_def _tmp_expr, *tmp_expr = &_tmp_expr;
1931 vinsn_t new_vi;
1932 bool add = true;
1934 new_vi = phist->old_expr_vinsn;
1936 gcc_assert (VINSN_SEPARABLE_P (new_vi)
1937 == EXPR_SEPARABLE_P (expr));
1938 copy_expr (tmp_expr, expr);
1940 if (vinsn_equal_p (phist->new_expr_vinsn,
1941 EXPR_VINSN (tmp_expr)))
1942 change_vinsn_in_expr (tmp_expr, new_vi);
1943 else
1944 /* This happens when we're unsubstituting on a bookkeeping
1945 copy, which was in turn substituted. The history is wrong
1946 in this case. Do it the hard way. */
1947 add = substitute_reg_in_expr (tmp_expr, insn, true);
1948 if (add)
1949 av_set_add (&new_set, tmp_expr);
1950 clear_expr (tmp_expr);
1951 break;
1953 default:
1954 gcc_unreachable ();
1960 av_set_union_and_clear (av_ptr, &new_set, NULL);
1964 /* Moveup_* helpers for code motion and computing av sets. */
1966 /* Propagates EXPR inside an insn group through THROUGH_INSN.
1967 The difference from the below function is that only substitution is
1968 performed. */
1969 static enum MOVEUP_EXPR_CODE
1970 moveup_expr_inside_insn_group (expr_t expr, insn_t through_insn)
1972 vinsn_t vi = EXPR_VINSN (expr);
1973 ds_t *has_dep_p;
1974 ds_t full_ds;
1976 /* Do this only inside insn group. */
1977 gcc_assert (INSN_SCHED_CYCLE (through_insn) > 0);
1979 full_ds = has_dependence_p (expr, through_insn, &has_dep_p);
1980 if (full_ds == 0)
1981 return MOVEUP_EXPR_SAME;
1983 /* Substitution is the possible choice in this case. */
1984 if (has_dep_p[DEPS_IN_RHS])
1986 /* Can't substitute UNIQUE VINSNs. */
1987 gcc_assert (!VINSN_UNIQUE_P (vi));
1989 if (can_substitute_through_p (through_insn,
1990 has_dep_p[DEPS_IN_RHS])
1991 && substitute_reg_in_expr (expr, through_insn, false))
1993 EXPR_WAS_SUBSTITUTED (expr) = true;
1994 return MOVEUP_EXPR_CHANGED;
1997 /* Don't care about this, as even true dependencies may be allowed
1998 in an insn group. */
1999 return MOVEUP_EXPR_SAME;
2002 /* This can catch output dependencies in COND_EXECs. */
2003 if (has_dep_p[DEPS_IN_INSN])
2004 return MOVEUP_EXPR_NULL;
2006 /* This is either an output or an anti dependence, which usually have
2007 a zero latency. Allow this here, if we'd be wrong, tick_check_p
2008 will fix this. */
2009 gcc_assert (has_dep_p[DEPS_IN_LHS]);
2010 return MOVEUP_EXPR_AS_RHS;
2013 /* True when a trapping EXPR cannot be moved through THROUGH_INSN. */
2014 #define CANT_MOVE_TRAPPING(expr, through_insn) \
2015 (VINSN_MAY_TRAP_P (EXPR_VINSN (expr)) \
2016 && !sel_insn_has_single_succ_p ((through_insn), SUCCS_ALL) \
2017 && !sel_insn_is_speculation_check (through_insn))
2019 /* True when a conflict on a target register was found during moveup_expr. */
2020 static bool was_target_conflict = false;
2022 /* Return true when moving a debug INSN across THROUGH_INSN will
2023 create a bookkeeping block. We don't want to create such blocks,
2024 for they would cause codegen differences between compilations with
2025 and without debug info. */
2027 static bool
2028 moving_insn_creates_bookkeeping_block_p (insn_t insn,
2029 insn_t through_insn)
2031 basic_block bbi, bbt;
2032 edge e1, e2;
2033 edge_iterator ei1, ei2;
2035 if (!bookkeeping_can_be_created_if_moved_through_p (through_insn))
2037 if (sched_verbose >= 9)
2038 sel_print ("no bookkeeping required: ");
2039 return FALSE;
2042 bbi = BLOCK_FOR_INSN (insn);
2044 if (EDGE_COUNT (bbi->preds) == 1)
2046 if (sched_verbose >= 9)
2047 sel_print ("only one pred edge: ");
2048 return TRUE;
2051 bbt = BLOCK_FOR_INSN (through_insn);
2053 FOR_EACH_EDGE (e1, ei1, bbt->succs)
2055 FOR_EACH_EDGE (e2, ei2, bbi->preds)
2057 if (find_block_for_bookkeeping (e1, e2, TRUE))
2059 if (sched_verbose >= 9)
2060 sel_print ("found existing block: ");
2061 return FALSE;
2066 if (sched_verbose >= 9)
2067 sel_print ("would create bookkeeping block: ");
2069 return TRUE;
2072 /* Return true when the conflict with newly created implicit clobbers
2073 between EXPR and THROUGH_INSN is found because of renaming. */
2074 static bool
2075 implicit_clobber_conflict_p (insn_t through_insn, expr_t expr)
2077 HARD_REG_SET temp;
2078 rtx_insn *insn;
2079 rtx reg, rhs, pat;
2080 hard_reg_set_iterator hrsi;
2081 unsigned regno;
2082 bool valid;
2084 /* Make a new pseudo register. */
2085 reg = gen_reg_rtx (GET_MODE (EXPR_LHS (expr)));
2086 max_regno = max_reg_num ();
2087 maybe_extend_reg_info_p ();
2089 /* Validate a change and bail out early. */
2090 insn = EXPR_INSN_RTX (expr);
2091 validate_change (insn, &SET_DEST (PATTERN (insn)), reg, true);
2092 valid = verify_changes (0);
2093 cancel_changes (0);
2094 if (!valid)
2096 if (sched_verbose >= 6)
2097 sel_print ("implicit clobbers failed validation, ");
2098 return true;
2101 /* Make a new insn with it. */
2102 rhs = copy_rtx (VINSN_RHS (EXPR_VINSN (expr)));
2103 pat = gen_rtx_SET (reg, rhs);
2104 start_sequence ();
2105 insn = emit_insn (pat);
2106 end_sequence ();
2108 /* Calculate implicit clobbers. */
2109 extract_insn (insn);
2110 preprocess_constraints (insn);
2111 alternative_mask prefrred = get_preferred_alternatives (insn);
2112 ira_implicitly_set_insn_hard_regs (&temp, prefrred);
2113 AND_COMPL_HARD_REG_SET (temp, ira_no_alloc_regs);
2115 /* If any implicit clobber registers intersect with regular ones in
2116 through_insn, we have a dependency and thus bail out. */
2117 EXECUTE_IF_SET_IN_HARD_REG_SET (temp, 0, regno, hrsi)
2119 vinsn_t vi = INSN_VINSN (through_insn);
2120 if (bitmap_bit_p (VINSN_REG_SETS (vi), regno)
2121 || bitmap_bit_p (VINSN_REG_CLOBBERS (vi), regno)
2122 || bitmap_bit_p (VINSN_REG_USES (vi), regno))
2123 return true;
2126 return false;
2129 /* Modifies EXPR so it can be moved through the THROUGH_INSN,
2130 performing necessary transformations. Record the type of transformation
2131 made in PTRANS_TYPE, when it is not NULL. When INSIDE_INSN_GROUP,
2132 permit all dependencies except true ones, and try to remove those
2133 too via forward substitution. All cases when a non-eliminable
2134 non-zero cost dependency exists inside an insn group will be fixed
2135 in tick_check_p instead. */
2136 static enum MOVEUP_EXPR_CODE
2137 moveup_expr (expr_t expr, insn_t through_insn, bool inside_insn_group,
2138 enum local_trans_type *ptrans_type)
2140 vinsn_t vi = EXPR_VINSN (expr);
2141 insn_t insn = VINSN_INSN_RTX (vi);
2142 bool was_changed = false;
2143 bool as_rhs = false;
2144 ds_t *has_dep_p;
2145 ds_t full_ds;
2147 /* ??? We use dependencies of non-debug insns on debug insns to
2148 indicate that the debug insns need to be reset if the non-debug
2149 insn is pulled ahead of it. It's hard to figure out how to
2150 introduce such a notion in sel-sched, but it already fails to
2151 support debug insns in other ways, so we just go ahead and
2152 let the deug insns go corrupt for now. */
2153 if (DEBUG_INSN_P (through_insn) && !DEBUG_INSN_P (insn))
2154 return MOVEUP_EXPR_SAME;
2156 /* When inside_insn_group, delegate to the helper. */
2157 if (inside_insn_group)
2158 return moveup_expr_inside_insn_group (expr, through_insn);
2160 /* Deal with unique insns and control dependencies. */
2161 if (VINSN_UNIQUE_P (vi))
2163 /* We can move jumps without side-effects or jumps that are
2164 mutually exclusive with instruction THROUGH_INSN (all in cases
2165 dependencies allow to do so and jump is not speculative). */
2166 if (control_flow_insn_p (insn))
2168 basic_block fallthru_bb;
2170 /* Do not move checks and do not move jumps through other
2171 jumps. */
2172 if (control_flow_insn_p (through_insn)
2173 || sel_insn_is_speculation_check (insn))
2174 return MOVEUP_EXPR_NULL;
2176 /* Don't move jumps through CFG joins. */
2177 if (bookkeeping_can_be_created_if_moved_through_p (through_insn))
2178 return MOVEUP_EXPR_NULL;
2180 /* The jump should have a clear fallthru block, and
2181 this block should be in the current region. */
2182 if ((fallthru_bb = fallthru_bb_of_jump (insn)) == NULL
2183 || ! in_current_region_p (fallthru_bb))
2184 return MOVEUP_EXPR_NULL;
2186 /* And it should be mutually exclusive with through_insn. */
2187 if (! sched_insns_conditions_mutex_p (insn, through_insn)
2188 && ! DEBUG_INSN_P (through_insn))
2189 return MOVEUP_EXPR_NULL;
2192 /* Don't move what we can't move. */
2193 if (EXPR_CANT_MOVE (expr)
2194 && BLOCK_FOR_INSN (through_insn) != BLOCK_FOR_INSN (insn))
2195 return MOVEUP_EXPR_NULL;
2197 /* Don't move SCHED_GROUP instruction through anything.
2198 If we don't force this, then it will be possible to start
2199 scheduling a sched_group before all its dependencies are
2200 resolved.
2201 ??? Haifa deals with this issue by delaying the SCHED_GROUP
2202 as late as possible through rank_for_schedule. */
2203 if (SCHED_GROUP_P (insn))
2204 return MOVEUP_EXPR_NULL;
2206 else
2207 gcc_assert (!control_flow_insn_p (insn));
2209 /* Don't move debug insns if this would require bookkeeping. */
2210 if (DEBUG_INSN_P (insn)
2211 && BLOCK_FOR_INSN (through_insn) != BLOCK_FOR_INSN (insn)
2212 && moving_insn_creates_bookkeeping_block_p (insn, through_insn))
2213 return MOVEUP_EXPR_NULL;
2215 /* Deal with data dependencies. */
2216 was_target_conflict = false;
2217 full_ds = has_dependence_p (expr, through_insn, &has_dep_p);
2218 if (full_ds == 0)
2220 if (!CANT_MOVE_TRAPPING (expr, through_insn))
2221 return MOVEUP_EXPR_SAME;
2223 else
2225 /* We can move UNIQUE insn up only as a whole and unchanged,
2226 so it shouldn't have any dependencies. */
2227 if (VINSN_UNIQUE_P (vi))
2228 return MOVEUP_EXPR_NULL;
2231 if (full_ds != 0 && can_speculate_dep_p (full_ds))
2233 int res;
2235 res = speculate_expr (expr, full_ds);
2236 if (res >= 0)
2238 /* Speculation was successful. */
2239 full_ds = 0;
2240 was_changed = (res > 0);
2241 if (res == 2)
2242 was_target_conflict = true;
2243 if (ptrans_type)
2244 *ptrans_type = TRANS_SPECULATION;
2245 sel_clear_has_dependence ();
2249 if (has_dep_p[DEPS_IN_INSN])
2250 /* We have some dependency that cannot be discarded. */
2251 return MOVEUP_EXPR_NULL;
2253 if (has_dep_p[DEPS_IN_LHS])
2255 /* Only separable insns can be moved up with the new register.
2256 Anyways, we should mark that the original register is
2257 unavailable. */
2258 if (!enable_schedule_as_rhs_p || !EXPR_SEPARABLE_P (expr))
2259 return MOVEUP_EXPR_NULL;
2261 /* When renaming a hard register to a pseudo before reload, extra
2262 dependencies can occur from the implicit clobbers of the insn.
2263 Filter out such cases here. */
2264 if (!reload_completed && REG_P (EXPR_LHS (expr))
2265 && HARD_REGISTER_P (EXPR_LHS (expr))
2266 && implicit_clobber_conflict_p (through_insn, expr))
2268 if (sched_verbose >= 6)
2269 sel_print ("implicit clobbers conflict detected, ");
2270 return MOVEUP_EXPR_NULL;
2272 EXPR_TARGET_AVAILABLE (expr) = false;
2273 was_target_conflict = true;
2274 as_rhs = true;
2277 /* At this point we have either separable insns, that will be lifted
2278 up only as RHSes, or non-separable insns with no dependency in lhs.
2279 If dependency is in RHS, then try to perform substitution and move up
2280 substituted RHS:
2282 Ex. 1: Ex.2
2283 y = x; y = x;
2284 z = y*2; y = y*2;
2286 In Ex.1 y*2 can be substituted for x*2 and the whole operation can be
2287 moved above y=x assignment as z=x*2.
2289 In Ex.2 y*2 also can be substituted for x*2, but only the right hand
2290 side can be moved because of the output dependency. The operation was
2291 cropped to its rhs above. */
2292 if (has_dep_p[DEPS_IN_RHS])
2294 ds_t *rhs_dsp = &has_dep_p[DEPS_IN_RHS];
2296 /* Can't substitute UNIQUE VINSNs. */
2297 gcc_assert (!VINSN_UNIQUE_P (vi));
2299 if (can_speculate_dep_p (*rhs_dsp))
2301 int res;
2303 res = speculate_expr (expr, *rhs_dsp);
2304 if (res >= 0)
2306 /* Speculation was successful. */
2307 *rhs_dsp = 0;
2308 was_changed = (res > 0);
2309 if (res == 2)
2310 was_target_conflict = true;
2311 if (ptrans_type)
2312 *ptrans_type = TRANS_SPECULATION;
2314 else
2315 return MOVEUP_EXPR_NULL;
2317 else if (can_substitute_through_p (through_insn,
2318 *rhs_dsp)
2319 && substitute_reg_in_expr (expr, through_insn, false))
2321 /* ??? We cannot perform substitution AND speculation on the same
2322 insn. */
2323 gcc_assert (!was_changed);
2324 was_changed = true;
2325 if (ptrans_type)
2326 *ptrans_type = TRANS_SUBSTITUTION;
2327 EXPR_WAS_SUBSTITUTED (expr) = true;
2329 else
2330 return MOVEUP_EXPR_NULL;
2333 /* Don't move trapping insns through jumps.
2334 This check should be at the end to give a chance to control speculation
2335 to perform its duties. */
2336 if (CANT_MOVE_TRAPPING (expr, through_insn))
2337 return MOVEUP_EXPR_NULL;
2339 return (was_changed
2340 ? MOVEUP_EXPR_CHANGED
2341 : (as_rhs
2342 ? MOVEUP_EXPR_AS_RHS
2343 : MOVEUP_EXPR_SAME));
2346 /* Try to look at bitmap caches for EXPR and INSN pair, return true
2347 if successful. When INSIDE_INSN_GROUP, also try ignore dependencies
2348 that can exist within a parallel group. Write to RES the resulting
2349 code for moveup_expr. */
2350 static bool
2351 try_bitmap_cache (expr_t expr, insn_t insn,
2352 bool inside_insn_group,
2353 enum MOVEUP_EXPR_CODE *res)
2355 int expr_uid = INSN_UID (EXPR_INSN_RTX (expr));
2357 /* First check whether we've analyzed this situation already. */
2358 if (bitmap_bit_p (INSN_ANALYZED_DEPS (insn), expr_uid))
2360 if (bitmap_bit_p (INSN_FOUND_DEPS (insn), expr_uid))
2362 if (sched_verbose >= 6)
2363 sel_print ("removed (cached)\n");
2364 *res = MOVEUP_EXPR_NULL;
2365 return true;
2367 else
2369 if (sched_verbose >= 6)
2370 sel_print ("unchanged (cached)\n");
2371 *res = MOVEUP_EXPR_SAME;
2372 return true;
2375 else if (bitmap_bit_p (INSN_FOUND_DEPS (insn), expr_uid))
2377 if (inside_insn_group)
2379 if (sched_verbose >= 6)
2380 sel_print ("unchanged (as RHS, cached, inside insn group)\n");
2381 *res = MOVEUP_EXPR_SAME;
2382 return true;
2385 else
2386 EXPR_TARGET_AVAILABLE (expr) = false;
2388 /* This is the only case when propagation result can change over time,
2389 as we can dynamically switch off scheduling as RHS. In this case,
2390 just check the flag to reach the correct decision. */
2391 if (enable_schedule_as_rhs_p)
2393 if (sched_verbose >= 6)
2394 sel_print ("unchanged (as RHS, cached)\n");
2395 *res = MOVEUP_EXPR_AS_RHS;
2396 return true;
2398 else
2400 if (sched_verbose >= 6)
2401 sel_print ("removed (cached as RHS, but renaming"
2402 " is now disabled)\n");
2403 *res = MOVEUP_EXPR_NULL;
2404 return true;
2408 return false;
2411 /* Try to look at bitmap caches for EXPR and INSN pair, return true
2412 if successful. Write to RES the resulting code for moveup_expr. */
2413 static bool
2414 try_transformation_cache (expr_t expr, insn_t insn,
2415 enum MOVEUP_EXPR_CODE *res)
2417 struct transformed_insns *pti
2418 = (struct transformed_insns *)
2419 htab_find_with_hash (INSN_TRANSFORMED_INSNS (insn),
2420 &EXPR_VINSN (expr),
2421 VINSN_HASH_RTX (EXPR_VINSN (expr)));
2422 if (pti)
2424 /* This EXPR was already moved through this insn and was
2425 changed as a result. Fetch the proper data from
2426 the hashtable. */
2427 insert_in_history_vect (&EXPR_HISTORY_OF_CHANGES (expr),
2428 INSN_UID (insn), pti->type,
2429 pti->vinsn_old, pti->vinsn_new,
2430 EXPR_SPEC_DONE_DS (expr));
2432 if (INSN_IN_STREAM_P (VINSN_INSN_RTX (pti->vinsn_new)))
2433 pti->vinsn_new = vinsn_copy (pti->vinsn_new, true);
2434 change_vinsn_in_expr (expr, pti->vinsn_new);
2435 if (pti->was_target_conflict)
2436 EXPR_TARGET_AVAILABLE (expr) = false;
2437 if (pti->type == TRANS_SPECULATION)
2439 EXPR_SPEC_DONE_DS (expr) = pti->ds;
2440 EXPR_NEEDS_SPEC_CHECK_P (expr) |= pti->needs_check;
2443 if (sched_verbose >= 6)
2445 sel_print ("changed (cached): ");
2446 dump_expr (expr);
2447 sel_print ("\n");
2450 *res = MOVEUP_EXPR_CHANGED;
2451 return true;
2454 return false;
2457 /* Update bitmap caches on INSN with result RES of propagating EXPR. */
2458 static void
2459 update_bitmap_cache (expr_t expr, insn_t insn, bool inside_insn_group,
2460 enum MOVEUP_EXPR_CODE res)
2462 int expr_uid = INSN_UID (EXPR_INSN_RTX (expr));
2464 /* Do not cache result of propagating jumps through an insn group,
2465 as it is always true, which is not useful outside the group. */
2466 if (inside_insn_group)
2467 return;
2469 if (res == MOVEUP_EXPR_NULL)
2471 bitmap_set_bit (INSN_ANALYZED_DEPS (insn), expr_uid);
2472 bitmap_set_bit (INSN_FOUND_DEPS (insn), expr_uid);
2474 else if (res == MOVEUP_EXPR_SAME)
2476 bitmap_set_bit (INSN_ANALYZED_DEPS (insn), expr_uid);
2477 bitmap_clear_bit (INSN_FOUND_DEPS (insn), expr_uid);
2479 else if (res == MOVEUP_EXPR_AS_RHS)
2481 bitmap_clear_bit (INSN_ANALYZED_DEPS (insn), expr_uid);
2482 bitmap_set_bit (INSN_FOUND_DEPS (insn), expr_uid);
2484 else
2485 gcc_unreachable ();
2488 /* Update hashtable on INSN with changed EXPR, old EXPR_OLD_VINSN
2489 and transformation type TRANS_TYPE. */
2490 static void
2491 update_transformation_cache (expr_t expr, insn_t insn,
2492 bool inside_insn_group,
2493 enum local_trans_type trans_type,
2494 vinsn_t expr_old_vinsn)
2496 struct transformed_insns *pti;
2498 if (inside_insn_group)
2499 return;
2501 pti = XNEW (struct transformed_insns);
2502 pti->vinsn_old = expr_old_vinsn;
2503 pti->vinsn_new = EXPR_VINSN (expr);
2504 pti->type = trans_type;
2505 pti->was_target_conflict = was_target_conflict;
2506 pti->ds = EXPR_SPEC_DONE_DS (expr);
2507 pti->needs_check = EXPR_NEEDS_SPEC_CHECK_P (expr);
2508 vinsn_attach (pti->vinsn_old);
2509 vinsn_attach (pti->vinsn_new);
2510 *((struct transformed_insns **)
2511 htab_find_slot_with_hash (INSN_TRANSFORMED_INSNS (insn),
2512 pti, VINSN_HASH_RTX (expr_old_vinsn),
2513 INSERT)) = pti;
2516 /* Same as moveup_expr, but first looks up the result of
2517 transformation in caches. */
2518 static enum MOVEUP_EXPR_CODE
2519 moveup_expr_cached (expr_t expr, insn_t insn, bool inside_insn_group)
2521 enum MOVEUP_EXPR_CODE res;
2522 bool got_answer = false;
2524 if (sched_verbose >= 6)
2526 sel_print ("Moving ");
2527 dump_expr (expr);
2528 sel_print (" through %d: ", INSN_UID (insn));
2531 if (DEBUG_INSN_P (EXPR_INSN_RTX (expr))
2532 && (sel_bb_head (BLOCK_FOR_INSN (EXPR_INSN_RTX (expr)))
2533 == EXPR_INSN_RTX (expr)))
2534 /* Don't use cached information for debug insns that are heads of
2535 basic blocks. */;
2536 else if (try_bitmap_cache (expr, insn, inside_insn_group, &res))
2537 /* When inside insn group, we do not want remove stores conflicting
2538 with previosly issued loads. */
2539 got_answer = ! inside_insn_group || res != MOVEUP_EXPR_NULL;
2540 else if (try_transformation_cache (expr, insn, &res))
2541 got_answer = true;
2543 if (! got_answer)
2545 /* Invoke moveup_expr and record the results. */
2546 vinsn_t expr_old_vinsn = EXPR_VINSN (expr);
2547 ds_t expr_old_spec_ds = EXPR_SPEC_DONE_DS (expr);
2548 int expr_uid = INSN_UID (VINSN_INSN_RTX (expr_old_vinsn));
2549 bool unique_p = VINSN_UNIQUE_P (expr_old_vinsn);
2550 enum local_trans_type trans_type = TRANS_SUBSTITUTION;
2552 /* ??? Invent something better than this. We can't allow old_vinsn
2553 to go, we need it for the history vector. */
2554 vinsn_attach (expr_old_vinsn);
2556 res = moveup_expr (expr, insn, inside_insn_group,
2557 &trans_type);
2558 switch (res)
2560 case MOVEUP_EXPR_NULL:
2561 update_bitmap_cache (expr, insn, inside_insn_group, res);
2562 if (sched_verbose >= 6)
2563 sel_print ("removed\n");
2564 break;
2566 case MOVEUP_EXPR_SAME:
2567 update_bitmap_cache (expr, insn, inside_insn_group, res);
2568 if (sched_verbose >= 6)
2569 sel_print ("unchanged\n");
2570 break;
2572 case MOVEUP_EXPR_AS_RHS:
2573 gcc_assert (!unique_p || inside_insn_group);
2574 update_bitmap_cache (expr, insn, inside_insn_group, res);
2575 if (sched_verbose >= 6)
2576 sel_print ("unchanged (as RHS)\n");
2577 break;
2579 case MOVEUP_EXPR_CHANGED:
2580 gcc_assert (INSN_UID (EXPR_INSN_RTX (expr)) != expr_uid
2581 || EXPR_SPEC_DONE_DS (expr) != expr_old_spec_ds);
2582 insert_in_history_vect (&EXPR_HISTORY_OF_CHANGES (expr),
2583 INSN_UID (insn), trans_type,
2584 expr_old_vinsn, EXPR_VINSN (expr),
2585 expr_old_spec_ds);
2586 update_transformation_cache (expr, insn, inside_insn_group,
2587 trans_type, expr_old_vinsn);
2588 if (sched_verbose >= 6)
2590 sel_print ("changed: ");
2591 dump_expr (expr);
2592 sel_print ("\n");
2594 break;
2595 default:
2596 gcc_unreachable ();
2599 vinsn_detach (expr_old_vinsn);
2602 return res;
2605 /* Moves an av set AVP up through INSN, performing necessary
2606 transformations. */
2607 static void
2608 moveup_set_expr (av_set_t *avp, insn_t insn, bool inside_insn_group)
2610 av_set_iterator i;
2611 expr_t expr;
2613 FOR_EACH_EXPR_1 (expr, i, avp)
2616 switch (moveup_expr_cached (expr, insn, inside_insn_group))
2618 case MOVEUP_EXPR_SAME:
2619 case MOVEUP_EXPR_AS_RHS:
2620 break;
2622 case MOVEUP_EXPR_NULL:
2623 av_set_iter_remove (&i);
2624 break;
2626 case MOVEUP_EXPR_CHANGED:
2627 expr = merge_with_other_exprs (avp, &i, expr);
2628 break;
2630 default:
2631 gcc_unreachable ();
2636 /* Moves AVP set along PATH. */
2637 static void
2638 moveup_set_inside_insn_group (av_set_t *avp, ilist_t path)
2640 int last_cycle;
2642 if (sched_verbose >= 6)
2643 sel_print ("Moving expressions up in the insn group...\n");
2644 if (! path)
2645 return;
2646 last_cycle = INSN_SCHED_CYCLE (ILIST_INSN (path));
2647 while (path
2648 && INSN_SCHED_CYCLE (ILIST_INSN (path)) == last_cycle)
2650 moveup_set_expr (avp, ILIST_INSN (path), true);
2651 path = ILIST_NEXT (path);
2655 /* Returns true if after moving EXPR along PATH it equals to EXPR_VLIW. */
2656 static bool
2657 equal_after_moveup_path_p (expr_t expr, ilist_t path, expr_t expr_vliw)
2659 expr_def _tmp, *tmp = &_tmp;
2660 int last_cycle;
2661 bool res = true;
2663 copy_expr_onside (tmp, expr);
2664 last_cycle = path ? INSN_SCHED_CYCLE (ILIST_INSN (path)) : 0;
2665 while (path
2666 && res
2667 && INSN_SCHED_CYCLE (ILIST_INSN (path)) == last_cycle)
2669 res = (moveup_expr_cached (tmp, ILIST_INSN (path), true)
2670 != MOVEUP_EXPR_NULL);
2671 path = ILIST_NEXT (path);
2674 if (res)
2676 vinsn_t tmp_vinsn = EXPR_VINSN (tmp);
2677 vinsn_t expr_vliw_vinsn = EXPR_VINSN (expr_vliw);
2679 if (tmp_vinsn != expr_vliw_vinsn)
2680 res = vinsn_equal_p (tmp_vinsn, expr_vliw_vinsn);
2683 clear_expr (tmp);
2684 return res;
2688 /* Functions that compute av and lv sets. */
2690 /* Returns true if INSN is not a downward continuation of the given path P in
2691 the current stage. */
2692 static bool
2693 is_ineligible_successor (insn_t insn, ilist_t p)
2695 insn_t prev_insn;
2697 /* Check if insn is not deleted. */
2698 if (PREV_INSN (insn) && NEXT_INSN (PREV_INSN (insn)) != insn)
2699 gcc_unreachable ();
2700 else if (NEXT_INSN (insn) && PREV_INSN (NEXT_INSN (insn)) != insn)
2701 gcc_unreachable ();
2703 /* If it's the first insn visited, then the successor is ok. */
2704 if (!p)
2705 return false;
2707 prev_insn = ILIST_INSN (p);
2709 if (/* a backward edge. */
2710 INSN_SEQNO (insn) < INSN_SEQNO (prev_insn)
2711 /* is already visited. */
2712 || (INSN_SEQNO (insn) == INSN_SEQNO (prev_insn)
2713 && (ilist_is_in_p (p, insn)
2714 /* We can reach another fence here and still seqno of insn
2715 would be equal to seqno of prev_insn. This is possible
2716 when prev_insn is a previously created bookkeeping copy.
2717 In that case it'd get a seqno of insn. Thus, check here
2718 whether insn is in current fence too. */
2719 || IN_CURRENT_FENCE_P (insn)))
2720 /* Was already scheduled on this round. */
2721 || (INSN_SEQNO (insn) > INSN_SEQNO (prev_insn)
2722 && IN_CURRENT_FENCE_P (insn))
2723 /* An insn from another fence could also be
2724 scheduled earlier even if this insn is not in
2725 a fence list right now. Check INSN_SCHED_CYCLE instead. */
2726 || (!pipelining_p
2727 && INSN_SCHED_TIMES (insn) > 0))
2728 return true;
2729 else
2730 return false;
2733 /* Computes the av_set below the last bb insn INSN, doing all the 'dirty work'
2734 of handling multiple successors and properly merging its av_sets. P is
2735 the current path traversed. WS is the size of lookahead window.
2736 Return the av set computed. */
2737 static av_set_t
2738 compute_av_set_at_bb_end (insn_t insn, ilist_t p, int ws)
2740 struct succs_info *sinfo;
2741 av_set_t expr_in_all_succ_branches = NULL;
2742 int is;
2743 insn_t succ, zero_succ = NULL;
2744 av_set_t av1 = NULL;
2746 gcc_assert (sel_bb_end_p (insn));
2748 /* Find different kind of successors needed for correct computing of
2749 SPEC and TARGET_AVAILABLE attributes. */
2750 sinfo = compute_succs_info (insn, SUCCS_NORMAL);
2752 /* Debug output. */
2753 if (sched_verbose >= 6)
2755 sel_print ("successors of bb end (%d): ", INSN_UID (insn));
2756 dump_insn_vector (sinfo->succs_ok);
2757 sel_print ("\n");
2758 if (sinfo->succs_ok_n != sinfo->all_succs_n)
2759 sel_print ("real successors num: %d\n", sinfo->all_succs_n);
2762 /* Add insn to the tail of current path. */
2763 ilist_add (&p, insn);
2765 FOR_EACH_VEC_ELT (sinfo->succs_ok, is, succ)
2767 av_set_t succ_set;
2769 /* We will edit SUCC_SET and EXPR_SPEC field of its elements. */
2770 succ_set = compute_av_set_inside_bb (succ, p, ws, true);
2772 av_set_split_usefulness (succ_set,
2773 sinfo->probs_ok[is],
2774 sinfo->all_prob);
2776 if (sinfo->all_succs_n > 1)
2778 /* Find EXPR'es that came from *all* successors and save them
2779 into expr_in_all_succ_branches. This set will be used later
2780 for calculating speculation attributes of EXPR'es. */
2781 if (is == 0)
2783 expr_in_all_succ_branches = av_set_copy (succ_set);
2785 /* Remember the first successor for later. */
2786 zero_succ = succ;
2788 else
2790 av_set_iterator i;
2791 expr_t expr;
2793 FOR_EACH_EXPR_1 (expr, i, &expr_in_all_succ_branches)
2794 if (!av_set_is_in_p (succ_set, EXPR_VINSN (expr)))
2795 av_set_iter_remove (&i);
2799 /* Union the av_sets. Check liveness restrictions on target registers
2800 in special case of two successors. */
2801 if (sinfo->succs_ok_n == 2 && is == 1)
2803 basic_block bb0 = BLOCK_FOR_INSN (zero_succ);
2804 basic_block bb1 = BLOCK_FOR_INSN (succ);
2806 gcc_assert (BB_LV_SET_VALID_P (bb0) && BB_LV_SET_VALID_P (bb1));
2807 av_set_union_and_live (&av1, &succ_set,
2808 BB_LV_SET (bb0),
2809 BB_LV_SET (bb1),
2810 insn);
2812 else
2813 av_set_union_and_clear (&av1, &succ_set, insn);
2816 /* Check liveness restrictions via hard way when there are more than
2817 two successors. */
2818 if (sinfo->succs_ok_n > 2)
2819 FOR_EACH_VEC_ELT (sinfo->succs_ok, is, succ)
2821 basic_block succ_bb = BLOCK_FOR_INSN (succ);
2823 gcc_assert (BB_LV_SET_VALID_P (succ_bb));
2824 mark_unavailable_targets (av1, BB_AV_SET (succ_bb),
2825 BB_LV_SET (succ_bb));
2828 /* Finally, check liveness restrictions on paths leaving the region. */
2829 if (sinfo->all_succs_n > sinfo->succs_ok_n)
2830 FOR_EACH_VEC_ELT (sinfo->succs_other, is, succ)
2831 mark_unavailable_targets
2832 (av1, NULL, BB_LV_SET (BLOCK_FOR_INSN (succ)));
2834 if (sinfo->all_succs_n > 1)
2836 av_set_iterator i;
2837 expr_t expr;
2839 /* Increase the spec attribute of all EXPR'es that didn't come
2840 from all successors. */
2841 FOR_EACH_EXPR (expr, i, av1)
2842 if (!av_set_is_in_p (expr_in_all_succ_branches, EXPR_VINSN (expr)))
2843 EXPR_SPEC (expr)++;
2845 av_set_clear (&expr_in_all_succ_branches);
2847 /* Do not move conditional branches through other
2848 conditional branches. So, remove all conditional
2849 branches from av_set if current operator is a conditional
2850 branch. */
2851 av_set_substract_cond_branches (&av1);
2854 ilist_remove (&p);
2855 free_succs_info (sinfo);
2857 if (sched_verbose >= 6)
2859 sel_print ("av_succs (%d): ", INSN_UID (insn));
2860 dump_av_set (av1);
2861 sel_print ("\n");
2864 return av1;
2867 /* This function computes av_set for the FIRST_INSN by dragging valid
2868 av_set through all basic block insns either from the end of basic block
2869 (computed using compute_av_set_at_bb_end) or from the insn on which
2870 MAX_WS was exceeded. It uses compute_av_set_at_bb_end to compute av_set
2871 below the basic block and handling conditional branches.
2872 FIRST_INSN - the basic block head, P - path consisting of the insns
2873 traversed on the way to the FIRST_INSN (the path is sparse, only bb heads
2874 and bb ends are added to the path), WS - current window size,
2875 NEED_COPY_P - true if we'll make a copy of av_set before returning it. */
2876 static av_set_t
2877 compute_av_set_inside_bb (insn_t first_insn, ilist_t p, int ws,
2878 bool need_copy_p)
2880 insn_t cur_insn;
2881 int end_ws = ws;
2882 insn_t bb_end = sel_bb_end (BLOCK_FOR_INSN (first_insn));
2883 insn_t after_bb_end = NEXT_INSN (bb_end);
2884 insn_t last_insn;
2885 av_set_t av = NULL;
2886 basic_block cur_bb = BLOCK_FOR_INSN (first_insn);
2888 /* Return NULL if insn is not on the legitimate downward path. */
2889 if (is_ineligible_successor (first_insn, p))
2891 if (sched_verbose >= 6)
2892 sel_print ("Insn %d is ineligible_successor\n", INSN_UID (first_insn));
2894 return NULL;
2897 /* If insn already has valid av(insn) computed, just return it. */
2898 if (AV_SET_VALID_P (first_insn))
2900 av_set_t av_set;
2902 if (sel_bb_head_p (first_insn))
2903 av_set = BB_AV_SET (BLOCK_FOR_INSN (first_insn));
2904 else
2905 av_set = NULL;
2907 if (sched_verbose >= 6)
2909 sel_print ("Insn %d has a valid av set: ", INSN_UID (first_insn));
2910 dump_av_set (av_set);
2911 sel_print ("\n");
2914 return need_copy_p ? av_set_copy (av_set) : av_set;
2917 ilist_add (&p, first_insn);
2919 /* As the result after this loop have completed, in LAST_INSN we'll
2920 have the insn which has valid av_set to start backward computation
2921 from: it either will be NULL because on it the window size was exceeded
2922 or other valid av_set as returned by compute_av_set for the last insn
2923 of the basic block. */
2924 for (last_insn = first_insn; last_insn != after_bb_end;
2925 last_insn = NEXT_INSN (last_insn))
2927 /* We may encounter valid av_set not only on bb_head, but also on
2928 those insns on which previously MAX_WS was exceeded. */
2929 if (AV_SET_VALID_P (last_insn))
2931 if (sched_verbose >= 6)
2932 sel_print ("Insn %d has a valid empty av set\n", INSN_UID (last_insn));
2933 break;
2936 /* The special case: the last insn of the BB may be an
2937 ineligible_successor due to its SEQ_NO that was set on
2938 it as a bookkeeping. */
2939 if (last_insn != first_insn
2940 && is_ineligible_successor (last_insn, p))
2942 if (sched_verbose >= 6)
2943 sel_print ("Insn %d is ineligible_successor\n", INSN_UID (last_insn));
2944 break;
2947 if (DEBUG_INSN_P (last_insn))
2948 continue;
2950 if (end_ws > max_ws)
2952 /* We can reach max lookahead size at bb_header, so clean av_set
2953 first. */
2954 INSN_WS_LEVEL (last_insn) = global_level;
2956 if (sched_verbose >= 6)
2957 sel_print ("Insn %d is beyond the software lookahead window size\n",
2958 INSN_UID (last_insn));
2959 break;
2962 end_ws++;
2965 /* Get the valid av_set into AV above the LAST_INSN to start backward
2966 computation from. It either will be empty av_set or av_set computed from
2967 the successors on the last insn of the current bb. */
2968 if (last_insn != after_bb_end)
2970 av = NULL;
2972 /* This is needed only to obtain av_sets that are identical to
2973 those computed by the old compute_av_set version. */
2974 if (last_insn == first_insn && !INSN_NOP_P (last_insn))
2975 av_set_add (&av, INSN_EXPR (last_insn));
2977 else
2978 /* END_WS is always already increased by 1 if LAST_INSN == AFTER_BB_END. */
2979 av = compute_av_set_at_bb_end (bb_end, p, end_ws);
2981 /* Compute av_set in AV starting from below the LAST_INSN up to
2982 location above the FIRST_INSN. */
2983 for (cur_insn = PREV_INSN (last_insn); cur_insn != PREV_INSN (first_insn);
2984 cur_insn = PREV_INSN (cur_insn))
2985 if (!INSN_NOP_P (cur_insn))
2987 expr_t expr;
2989 moveup_set_expr (&av, cur_insn, false);
2991 /* If the expression for CUR_INSN is already in the set,
2992 replace it by the new one. */
2993 expr = av_set_lookup (av, INSN_VINSN (cur_insn));
2994 if (expr != NULL)
2996 clear_expr (expr);
2997 copy_expr (expr, INSN_EXPR (cur_insn));
2999 else
3000 av_set_add (&av, INSN_EXPR (cur_insn));
3003 /* Clear stale bb_av_set. */
3004 if (sel_bb_head_p (first_insn))
3006 av_set_clear (&BB_AV_SET (cur_bb));
3007 BB_AV_SET (cur_bb) = need_copy_p ? av_set_copy (av) : av;
3008 BB_AV_LEVEL (cur_bb) = global_level;
3011 if (sched_verbose >= 6)
3013 sel_print ("Computed av set for insn %d: ", INSN_UID (first_insn));
3014 dump_av_set (av);
3015 sel_print ("\n");
3018 ilist_remove (&p);
3019 return av;
3022 /* Compute av set before INSN.
3023 INSN - the current operation (actual rtx INSN)
3024 P - the current path, which is list of insns visited so far
3025 WS - software lookahead window size.
3026 UNIQUE_P - TRUE, if returned av_set will be changed, hence
3027 if we want to save computed av_set in s_i_d, we should make a copy of it.
3029 In the resulting set we will have only expressions that don't have delay
3030 stalls and nonsubstitutable dependences. */
3031 static av_set_t
3032 compute_av_set (insn_t insn, ilist_t p, int ws, bool unique_p)
3034 return compute_av_set_inside_bb (insn, p, ws, unique_p);
3037 /* Propagate a liveness set LV through INSN. */
3038 static void
3039 propagate_lv_set (regset lv, insn_t insn)
3041 gcc_assert (INSN_P (insn));
3043 if (INSN_NOP_P (insn))
3044 return;
3046 df_simulate_one_insn_backwards (BLOCK_FOR_INSN (insn), insn, lv);
3049 /* Return livness set at the end of BB. */
3050 static regset
3051 compute_live_after_bb (basic_block bb)
3053 edge e;
3054 edge_iterator ei;
3055 regset lv = get_clear_regset_from_pool ();
3057 gcc_assert (!ignore_first);
3059 FOR_EACH_EDGE (e, ei, bb->succs)
3060 if (sel_bb_empty_p (e->dest))
3062 if (! BB_LV_SET_VALID_P (e->dest))
3064 gcc_unreachable ();
3065 gcc_assert (BB_LV_SET (e->dest) == NULL);
3066 BB_LV_SET (e->dest) = compute_live_after_bb (e->dest);
3067 BB_LV_SET_VALID_P (e->dest) = true;
3069 IOR_REG_SET (lv, BB_LV_SET (e->dest));
3071 else
3072 IOR_REG_SET (lv, compute_live (sel_bb_head (e->dest)));
3074 return lv;
3077 /* Compute the set of all live registers at the point before INSN and save
3078 it at INSN if INSN is bb header. */
3079 regset
3080 compute_live (insn_t insn)
3082 basic_block bb = BLOCK_FOR_INSN (insn);
3083 insn_t final, temp;
3084 regset lv;
3086 /* Return the valid set if we're already on it. */
3087 if (!ignore_first)
3089 regset src = NULL;
3091 if (sel_bb_head_p (insn) && BB_LV_SET_VALID_P (bb))
3092 src = BB_LV_SET (bb);
3093 else
3095 gcc_assert (in_current_region_p (bb));
3096 if (INSN_LIVE_VALID_P (insn))
3097 src = INSN_LIVE (insn);
3100 if (src)
3102 lv = get_regset_from_pool ();
3103 COPY_REG_SET (lv, src);
3105 if (sel_bb_head_p (insn) && ! BB_LV_SET_VALID_P (bb))
3107 COPY_REG_SET (BB_LV_SET (bb), lv);
3108 BB_LV_SET_VALID_P (bb) = true;
3111 return_regset_to_pool (lv);
3112 return lv;
3116 /* We've skipped the wrong lv_set. Don't skip the right one. */
3117 ignore_first = false;
3118 gcc_assert (in_current_region_p (bb));
3120 /* Find a valid LV set in this block or below, if needed.
3121 Start searching from the next insn: either ignore_first is true, or
3122 INSN doesn't have a correct live set. */
3123 temp = NEXT_INSN (insn);
3124 final = NEXT_INSN (BB_END (bb));
3125 while (temp != final && ! INSN_LIVE_VALID_P (temp))
3126 temp = NEXT_INSN (temp);
3127 if (temp == final)
3129 lv = compute_live_after_bb (bb);
3130 temp = PREV_INSN (temp);
3132 else
3134 lv = get_regset_from_pool ();
3135 COPY_REG_SET (lv, INSN_LIVE (temp));
3138 /* Put correct lv sets on the insns which have bad sets. */
3139 final = PREV_INSN (insn);
3140 while (temp != final)
3142 propagate_lv_set (lv, temp);
3143 COPY_REG_SET (INSN_LIVE (temp), lv);
3144 INSN_LIVE_VALID_P (temp) = true;
3145 temp = PREV_INSN (temp);
3148 /* Also put it in a BB. */
3149 if (sel_bb_head_p (insn))
3151 basic_block bb = BLOCK_FOR_INSN (insn);
3153 COPY_REG_SET (BB_LV_SET (bb), lv);
3154 BB_LV_SET_VALID_P (bb) = true;
3157 /* We return LV to the pool, but will not clear it there. Thus we can
3158 legimatelly use LV till the next use of regset_pool_get (). */
3159 return_regset_to_pool (lv);
3160 return lv;
3163 /* Update liveness sets for INSN. */
3164 static inline void
3165 update_liveness_on_insn (rtx_insn *insn)
3167 ignore_first = true;
3168 compute_live (insn);
3171 /* Compute liveness below INSN and write it into REGS. */
3172 static inline void
3173 compute_live_below_insn (rtx_insn *insn, regset regs)
3175 rtx_insn *succ;
3176 succ_iterator si;
3178 FOR_EACH_SUCC_1 (succ, si, insn, SUCCS_ALL)
3179 IOR_REG_SET (regs, compute_live (succ));
3182 /* Update the data gathered in av and lv sets starting from INSN. */
3183 static void
3184 update_data_sets (rtx_insn *insn)
3186 update_liveness_on_insn (insn);
3187 if (sel_bb_head_p (insn))
3189 gcc_assert (AV_LEVEL (insn) != 0);
3190 BB_AV_LEVEL (BLOCK_FOR_INSN (insn)) = -1;
3191 compute_av_set (insn, NULL, 0, 0);
3196 /* Helper for move_op () and find_used_regs ().
3197 Return speculation type for which a check should be created on the place
3198 of INSN. EXPR is one of the original ops we are searching for. */
3199 static ds_t
3200 get_spec_check_type_for_insn (insn_t insn, expr_t expr)
3202 ds_t to_check_ds;
3203 ds_t already_checked_ds = EXPR_SPEC_DONE_DS (INSN_EXPR (insn));
3205 to_check_ds = EXPR_SPEC_TO_CHECK_DS (expr);
3207 if (targetm.sched.get_insn_checked_ds)
3208 already_checked_ds |= targetm.sched.get_insn_checked_ds (insn);
3210 if (spec_info != NULL
3211 && (spec_info->flags & SEL_SCHED_SPEC_DONT_CHECK_CONTROL))
3212 already_checked_ds |= BEGIN_CONTROL;
3214 already_checked_ds = ds_get_speculation_types (already_checked_ds);
3216 to_check_ds &= ~already_checked_ds;
3218 return to_check_ds;
3221 /* Find the set of registers that are unavailable for storing expres
3222 while moving ORIG_OPS up on the path starting from INSN due to
3223 liveness (USED_REGS) or hardware restrictions (REG_RENAME_P).
3225 All the original operations found during the traversal are saved in the
3226 ORIGINAL_INSNS list.
3228 REG_RENAME_P denotes the set of hardware registers that
3229 can not be used with renaming due to the register class restrictions,
3230 mode restrictions and other (the register we'll choose should be
3231 compatible class with the original uses, shouldn't be in call_used_regs,
3232 should be HARD_REGNO_RENAME_OK etc).
3234 Returns TRUE if we've found all original insns, FALSE otherwise.
3236 This function utilizes code_motion_path_driver (formerly find_used_regs_1)
3237 to traverse the code motion paths. This helper function finds registers
3238 that are not available for storing expres while moving ORIG_OPS up on the
3239 path starting from INSN. A register considered as used on the moving path,
3240 if one of the following conditions is not satisfied:
3242 (1) a register not set or read on any path from xi to an instance of
3243 the original operation,
3244 (2) not among the live registers of the point immediately following the
3245 first original operation on a given downward path, except for the
3246 original target register of the operation,
3247 (3) not live on the other path of any conditional branch that is passed
3248 by the operation, in case original operations are not present on
3249 both paths of the conditional branch.
3251 All the original operations found during the traversal are saved in the
3252 ORIGINAL_INSNS list.
3254 REG_RENAME_P->CROSSES_CALL is true, if there is a call insn on the path
3255 from INSN to original insn. In this case CALL_USED_REG_SET will be added
3256 to unavailable hard regs at the point original operation is found. */
3258 static bool
3259 find_used_regs (insn_t insn, av_set_t orig_ops, regset used_regs,
3260 struct reg_rename *reg_rename_p, def_list_t *original_insns)
3262 def_list_iterator i;
3263 def_t def;
3264 int res;
3265 bool needs_spec_check_p = false;
3266 expr_t expr;
3267 av_set_iterator expr_iter;
3268 struct fur_static_params sparams;
3269 struct cmpd_local_params lparams;
3271 /* We haven't visited any blocks yet. */
3272 bitmap_clear (code_motion_visited_blocks);
3274 /* Init parameters for code_motion_path_driver. */
3275 sparams.crosses_call = false;
3276 sparams.original_insns = original_insns;
3277 sparams.used_regs = used_regs;
3279 /* Set the appropriate hooks and data. */
3280 code_motion_path_driver_info = &fur_hooks;
3282 res = code_motion_path_driver (insn, orig_ops, NULL, &lparams, &sparams);
3284 reg_rename_p->crosses_call |= sparams.crosses_call;
3286 gcc_assert (res == 1);
3287 gcc_assert (original_insns && *original_insns);
3289 /* ??? We calculate whether an expression needs a check when computing
3290 av sets. This information is not as precise as it could be due to
3291 merging this bit in merge_expr. We can do better in find_used_regs,
3292 but we want to avoid multiple traversals of the same code motion
3293 paths. */
3294 FOR_EACH_EXPR (expr, expr_iter, orig_ops)
3295 needs_spec_check_p |= EXPR_NEEDS_SPEC_CHECK_P (expr);
3297 /* Mark hardware regs in REG_RENAME_P that are not suitable
3298 for renaming expr in INSN due to hardware restrictions (register class,
3299 modes compatibility etc). */
3300 FOR_EACH_DEF (def, i, *original_insns)
3302 vinsn_t vinsn = INSN_VINSN (def->orig_insn);
3304 if (VINSN_SEPARABLE_P (vinsn))
3305 mark_unavailable_hard_regs (def, reg_rename_p, used_regs);
3307 /* Do not allow clobbering of ld.[sa] address in case some of the
3308 original operations need a check. */
3309 if (needs_spec_check_p)
3310 IOR_REG_SET (used_regs, VINSN_REG_USES (vinsn));
3313 return true;
3317 /* Functions to choose the best insn from available ones. */
3319 /* Adjusts the priority for EXPR using the backend *_adjust_priority hook. */
3320 static int
3321 sel_target_adjust_priority (expr_t expr)
3323 int priority = EXPR_PRIORITY (expr);
3324 int new_priority;
3326 if (targetm.sched.adjust_priority)
3327 new_priority = targetm.sched.adjust_priority (EXPR_INSN_RTX (expr), priority);
3328 else
3329 new_priority = priority;
3331 /* If the priority has changed, adjust EXPR_PRIORITY_ADJ accordingly. */
3332 EXPR_PRIORITY_ADJ (expr) = new_priority - EXPR_PRIORITY (expr);
3334 gcc_assert (EXPR_PRIORITY_ADJ (expr) >= 0);
3336 if (sched_verbose >= 4)
3337 sel_print ("sel_target_adjust_priority: insn %d, %d+%d = %d.\n",
3338 INSN_UID (EXPR_INSN_RTX (expr)), EXPR_PRIORITY (expr),
3339 EXPR_PRIORITY_ADJ (expr), new_priority);
3341 return new_priority;
3344 /* Rank two available exprs for schedule. Never return 0 here. */
3345 static int
3346 sel_rank_for_schedule (const void *x, const void *y)
3348 expr_t tmp = *(const expr_t *) y;
3349 expr_t tmp2 = *(const expr_t *) x;
3350 insn_t tmp_insn, tmp2_insn;
3351 vinsn_t tmp_vinsn, tmp2_vinsn;
3352 int val;
3354 tmp_vinsn = EXPR_VINSN (tmp);
3355 tmp2_vinsn = EXPR_VINSN (tmp2);
3356 tmp_insn = EXPR_INSN_RTX (tmp);
3357 tmp2_insn = EXPR_INSN_RTX (tmp2);
3359 /* Schedule debug insns as early as possible. */
3360 if (DEBUG_INSN_P (tmp_insn) && !DEBUG_INSN_P (tmp2_insn))
3361 return -1;
3362 else if (DEBUG_INSN_P (tmp2_insn))
3363 return 1;
3365 /* Prefer SCHED_GROUP_P insns to any others. */
3366 if (SCHED_GROUP_P (tmp_insn) != SCHED_GROUP_P (tmp2_insn))
3368 if (VINSN_UNIQUE_P (tmp_vinsn) && VINSN_UNIQUE_P (tmp2_vinsn))
3369 return SCHED_GROUP_P (tmp2_insn) ? 1 : -1;
3371 /* Now uniqueness means SCHED_GROUP_P is set, because schedule groups
3372 cannot be cloned. */
3373 if (VINSN_UNIQUE_P (tmp2_vinsn))
3374 return 1;
3375 return -1;
3378 /* Discourage scheduling of speculative checks. */
3379 val = (sel_insn_is_speculation_check (tmp_insn)
3380 - sel_insn_is_speculation_check (tmp2_insn));
3381 if (val)
3382 return val;
3384 /* Prefer not scheduled insn over scheduled one. */
3385 if (EXPR_SCHED_TIMES (tmp) > 0 || EXPR_SCHED_TIMES (tmp2) > 0)
3387 val = EXPR_SCHED_TIMES (tmp) - EXPR_SCHED_TIMES (tmp2);
3388 if (val)
3389 return val;
3392 /* Prefer jump over non-jump instruction. */
3393 if (control_flow_insn_p (tmp_insn) && !control_flow_insn_p (tmp2_insn))
3394 return -1;
3395 else if (control_flow_insn_p (tmp2_insn) && !control_flow_insn_p (tmp_insn))
3396 return 1;
3398 /* Prefer an expr with greater priority. */
3399 if (EXPR_USEFULNESS (tmp) != 0 && EXPR_USEFULNESS (tmp2) != 0)
3401 int p2 = EXPR_PRIORITY (tmp2) + EXPR_PRIORITY_ADJ (tmp2),
3402 p1 = EXPR_PRIORITY (tmp) + EXPR_PRIORITY_ADJ (tmp);
3404 val = p2 * EXPR_USEFULNESS (tmp2) - p1 * EXPR_USEFULNESS (tmp);
3406 else
3407 val = EXPR_PRIORITY (tmp2) - EXPR_PRIORITY (tmp)
3408 + EXPR_PRIORITY_ADJ (tmp2) - EXPR_PRIORITY_ADJ (tmp);
3409 if (val)
3410 return val;
3412 if (spec_info != NULL && spec_info->mask != 0)
3413 /* This code was taken from haifa-sched.c: rank_for_schedule (). */
3415 ds_t ds1, ds2;
3416 dw_t dw1, dw2;
3417 int dw;
3419 ds1 = EXPR_SPEC_DONE_DS (tmp);
3420 if (ds1)
3421 dw1 = ds_weak (ds1);
3422 else
3423 dw1 = NO_DEP_WEAK;
3425 ds2 = EXPR_SPEC_DONE_DS (tmp2);
3426 if (ds2)
3427 dw2 = ds_weak (ds2);
3428 else
3429 dw2 = NO_DEP_WEAK;
3431 dw = dw2 - dw1;
3432 if (dw > (NO_DEP_WEAK / 8) || dw < -(NO_DEP_WEAK / 8))
3433 return dw;
3436 /* Prefer an old insn to a bookkeeping insn. */
3437 if (INSN_UID (tmp_insn) < first_emitted_uid
3438 && INSN_UID (tmp2_insn) >= first_emitted_uid)
3439 return -1;
3440 if (INSN_UID (tmp_insn) >= first_emitted_uid
3441 && INSN_UID (tmp2_insn) < first_emitted_uid)
3442 return 1;
3444 /* Prefer an insn with smaller UID, as a last resort.
3445 We can't safely use INSN_LUID as it is defined only for those insns
3446 that are in the stream. */
3447 return INSN_UID (tmp_insn) - INSN_UID (tmp2_insn);
3450 /* Filter out expressions from av set pointed to by AV_PTR
3451 that are pipelined too many times. */
3452 static void
3453 process_pipelined_exprs (av_set_t *av_ptr)
3455 expr_t expr;
3456 av_set_iterator si;
3458 /* Don't pipeline already pipelined code as that would increase
3459 number of unnecessary register moves. */
3460 FOR_EACH_EXPR_1 (expr, si, av_ptr)
3462 if (EXPR_SCHED_TIMES (expr)
3463 >= PARAM_VALUE (PARAM_SELSCHED_MAX_SCHED_TIMES))
3464 av_set_iter_remove (&si);
3468 /* Filter speculative insns from AV_PTR if we don't want them. */
3469 static void
3470 process_spec_exprs (av_set_t *av_ptr)
3472 expr_t expr;
3473 av_set_iterator si;
3475 if (spec_info == NULL)
3476 return;
3478 /* Scan *AV_PTR to find out if we want to consider speculative
3479 instructions for scheduling. */
3480 FOR_EACH_EXPR_1 (expr, si, av_ptr)
3482 ds_t ds;
3484 ds = EXPR_SPEC_DONE_DS (expr);
3486 /* The probability of a success is too low - don't speculate. */
3487 if ((ds & SPECULATIVE)
3488 && (ds_weak (ds) < spec_info->data_weakness_cutoff
3489 || EXPR_USEFULNESS (expr) < spec_info->control_weakness_cutoff
3490 || (pipelining_p && false
3491 && (ds & DATA_SPEC)
3492 && (ds & CONTROL_SPEC))))
3494 av_set_iter_remove (&si);
3495 continue;
3500 /* Search for any use-like insns in AV_PTR and decide on scheduling
3501 them. Return one when found, and NULL otherwise.
3502 Note that we check here whether a USE could be scheduled to avoid
3503 an infinite loop later. */
3504 static expr_t
3505 process_use_exprs (av_set_t *av_ptr)
3507 expr_t expr;
3508 av_set_iterator si;
3509 bool uses_present_p = false;
3510 bool try_uses_p = true;
3512 FOR_EACH_EXPR_1 (expr, si, av_ptr)
3514 /* This will also initialize INSN_CODE for later use. */
3515 if (recog_memoized (EXPR_INSN_RTX (expr)) < 0)
3517 /* If we have a USE in *AV_PTR that was not scheduled yet,
3518 do so because it will do good only. */
3519 if (EXPR_SCHED_TIMES (expr) <= 0)
3521 if (EXPR_TARGET_AVAILABLE (expr) == 1)
3522 return expr;
3524 av_set_iter_remove (&si);
3526 else
3528 gcc_assert (pipelining_p);
3530 uses_present_p = true;
3533 else
3534 try_uses_p = false;
3537 if (uses_present_p)
3539 /* If we don't want to schedule any USEs right now and we have some
3540 in *AV_PTR, remove them, else just return the first one found. */
3541 if (!try_uses_p)
3543 FOR_EACH_EXPR_1 (expr, si, av_ptr)
3544 if (INSN_CODE (EXPR_INSN_RTX (expr)) < 0)
3545 av_set_iter_remove (&si);
3547 else
3549 FOR_EACH_EXPR_1 (expr, si, av_ptr)
3551 gcc_assert (INSN_CODE (EXPR_INSN_RTX (expr)) < 0);
3553 if (EXPR_TARGET_AVAILABLE (expr) == 1)
3554 return expr;
3556 av_set_iter_remove (&si);
3561 return NULL;
3564 /* Lookup EXPR in VINSN_VEC and return TRUE if found. Also check patterns from
3565 EXPR's history of changes. */
3566 static bool
3567 vinsn_vec_has_expr_p (vinsn_vec_t vinsn_vec, expr_t expr)
3569 vinsn_t vinsn, expr_vinsn;
3570 int n;
3571 unsigned i;
3573 /* Start with checking expr itself and then proceed with all the old forms
3574 of expr taken from its history vector. */
3575 for (i = 0, expr_vinsn = EXPR_VINSN (expr);
3576 expr_vinsn;
3577 expr_vinsn = (i < EXPR_HISTORY_OF_CHANGES (expr).length ()
3578 ? EXPR_HISTORY_OF_CHANGES (expr)[i++].old_expr_vinsn
3579 : NULL))
3580 FOR_EACH_VEC_ELT (vinsn_vec, n, vinsn)
3581 if (VINSN_SEPARABLE_P (vinsn))
3583 if (vinsn_equal_p (vinsn, expr_vinsn))
3584 return true;
3586 else
3588 /* For non-separable instructions, the blocking insn can have
3589 another pattern due to substitution, and we can't choose
3590 different register as in the above case. Check all registers
3591 being written instead. */
3592 if (bitmap_intersect_p (VINSN_REG_SETS (vinsn),
3593 VINSN_REG_SETS (expr_vinsn)))
3594 return true;
3597 return false;
3600 /* Return true if either of expressions from ORIG_OPS can be blocked
3601 by previously created bookkeeping code. STATIC_PARAMS points to static
3602 parameters of move_op. */
3603 static bool
3604 av_set_could_be_blocked_by_bookkeeping_p (av_set_t orig_ops, void *static_params)
3606 expr_t expr;
3607 av_set_iterator iter;
3608 moveop_static_params_p sparams;
3610 /* This checks that expressions in ORIG_OPS are not blocked by bookkeeping
3611 created while scheduling on another fence. */
3612 FOR_EACH_EXPR (expr, iter, orig_ops)
3613 if (vinsn_vec_has_expr_p (vec_bookkeeping_blocked_vinsns, expr))
3614 return true;
3616 gcc_assert (code_motion_path_driver_info == &move_op_hooks);
3617 sparams = (moveop_static_params_p) static_params;
3619 /* Expressions can be also blocked by bookkeeping created during current
3620 move_op. */
3621 if (bitmap_bit_p (current_copies, INSN_UID (sparams->failed_insn)))
3622 FOR_EACH_EXPR (expr, iter, orig_ops)
3623 if (moveup_expr_cached (expr, sparams->failed_insn, false) != MOVEUP_EXPR_NULL)
3624 return true;
3626 /* Expressions in ORIG_OPS may have wrong destination register due to
3627 renaming. Check with the right register instead. */
3628 if (sparams->dest && REG_P (sparams->dest))
3630 rtx reg = sparams->dest;
3631 vinsn_t failed_vinsn = INSN_VINSN (sparams->failed_insn);
3633 if (register_unavailable_p (VINSN_REG_SETS (failed_vinsn), reg)
3634 || register_unavailable_p (VINSN_REG_USES (failed_vinsn), reg)
3635 || register_unavailable_p (VINSN_REG_CLOBBERS (failed_vinsn), reg))
3636 return true;
3639 return false;
3642 /* Clear VINSN_VEC and detach vinsns. */
3643 static void
3644 vinsn_vec_clear (vinsn_vec_t *vinsn_vec)
3646 unsigned len = vinsn_vec->length ();
3647 if (len > 0)
3649 vinsn_t vinsn;
3650 int n;
3652 FOR_EACH_VEC_ELT (*vinsn_vec, n, vinsn)
3653 vinsn_detach (vinsn);
3654 vinsn_vec->block_remove (0, len);
3658 /* Add the vinsn of EXPR to the VINSN_VEC. */
3659 static void
3660 vinsn_vec_add (vinsn_vec_t *vinsn_vec, expr_t expr)
3662 vinsn_attach (EXPR_VINSN (expr));
3663 vinsn_vec->safe_push (EXPR_VINSN (expr));
3666 /* Free the vector representing blocked expressions. */
3667 static void
3668 vinsn_vec_free (vinsn_vec_t &vinsn_vec)
3670 vinsn_vec.release ();
3673 /* Increase EXPR_PRIORITY_ADJ for INSN by AMOUNT. */
3675 void sel_add_to_insn_priority (rtx insn, int amount)
3677 EXPR_PRIORITY_ADJ (INSN_EXPR (insn)) += amount;
3679 if (sched_verbose >= 2)
3680 sel_print ("sel_add_to_insn_priority: insn %d, by %d (now %d+%d).\n",
3681 INSN_UID (insn), amount, EXPR_PRIORITY (INSN_EXPR (insn)),
3682 EXPR_PRIORITY_ADJ (INSN_EXPR (insn)));
3685 /* Turn AV into a vector, filter inappropriate insns and sort it. Return
3686 true if there is something to schedule. BNDS and FENCE are current
3687 boundaries and fence, respectively. If we need to stall for some cycles
3688 before an expr from AV would become available, write this number to
3689 *PNEED_STALL. */
3690 static bool
3691 fill_vec_av_set (av_set_t av, blist_t bnds, fence_t fence,
3692 int *pneed_stall)
3694 av_set_iterator si;
3695 expr_t expr;
3696 int sched_next_worked = 0, stalled, n;
3697 static int av_max_prio, est_ticks_till_branch;
3698 int min_need_stall = -1;
3699 deps_t dc = BND_DC (BLIST_BND (bnds));
3701 /* Bail out early when the ready list contained only USEs/CLOBBERs that are
3702 already scheduled. */
3703 if (av == NULL)
3704 return false;
3706 /* Empty vector from the previous stuff. */
3707 if (vec_av_set.length () > 0)
3708 vec_av_set.block_remove (0, vec_av_set.length ());
3710 /* Turn the set into a vector for sorting and call sel_target_adjust_priority
3711 for each insn. */
3712 gcc_assert (vec_av_set.is_empty ());
3713 FOR_EACH_EXPR (expr, si, av)
3715 vec_av_set.safe_push (expr);
3717 gcc_assert (EXPR_PRIORITY_ADJ (expr) == 0 || *pneed_stall);
3719 /* Adjust priority using target backend hook. */
3720 sel_target_adjust_priority (expr);
3723 /* Sort the vector. */
3724 vec_av_set.qsort (sel_rank_for_schedule);
3726 /* We record maximal priority of insns in av set for current instruction
3727 group. */
3728 if (FENCE_STARTS_CYCLE_P (fence))
3729 av_max_prio = est_ticks_till_branch = INT_MIN;
3731 /* Filter out inappropriate expressions. Loop's direction is reversed to
3732 visit "best" instructions first. We assume that vec::unordered_remove
3733 moves last element in place of one being deleted. */
3734 for (n = vec_av_set.length () - 1, stalled = 0; n >= 0; n--)
3736 expr_t expr = vec_av_set[n];
3737 insn_t insn = EXPR_INSN_RTX (expr);
3738 signed char target_available;
3739 bool is_orig_reg_p = true;
3740 int need_cycles, new_prio;
3741 bool fence_insn_p = INSN_UID (insn) == INSN_UID (FENCE_INSN (fence));
3743 /* Don't allow any insns other than from SCHED_GROUP if we have one. */
3744 if (FENCE_SCHED_NEXT (fence) && insn != FENCE_SCHED_NEXT (fence))
3746 vec_av_set.unordered_remove (n);
3747 continue;
3750 /* Set number of sched_next insns (just in case there
3751 could be several). */
3752 if (FENCE_SCHED_NEXT (fence))
3753 sched_next_worked++;
3755 /* Check all liveness requirements and try renaming.
3756 FIXME: try to minimize calls to this. */
3757 target_available = EXPR_TARGET_AVAILABLE (expr);
3759 /* If insn was already scheduled on the current fence,
3760 set TARGET_AVAILABLE to -1 no matter what expr's attribute says. */
3761 if (vinsn_vec_has_expr_p (vec_target_unavailable_vinsns, expr)
3762 && !fence_insn_p)
3763 target_available = -1;
3765 /* If the availability of the EXPR is invalidated by the insertion of
3766 bookkeeping earlier, make sure that we won't choose this expr for
3767 scheduling if it's not separable, and if it is separable, then
3768 we have to recompute the set of available registers for it. */
3769 if (vinsn_vec_has_expr_p (vec_bookkeeping_blocked_vinsns, expr))
3771 vec_av_set.unordered_remove (n);
3772 if (sched_verbose >= 4)
3773 sel_print ("Expr %d is blocked by bookkeeping inserted earlier\n",
3774 INSN_UID (insn));
3775 continue;
3778 if (target_available == true)
3780 /* Do nothing -- we can use an existing register. */
3781 is_orig_reg_p = EXPR_SEPARABLE_P (expr);
3783 else if (/* Non-separable instruction will never
3784 get another register. */
3785 (target_available == false
3786 && !EXPR_SEPARABLE_P (expr))
3787 /* Don't try to find a register for low-priority expression. */
3788 || (int) vec_av_set.length () - 1 - n >= max_insns_to_rename
3789 /* ??? FIXME: Don't try to rename data speculation. */
3790 || (EXPR_SPEC_DONE_DS (expr) & BEGIN_DATA)
3791 || ! find_best_reg_for_expr (expr, bnds, &is_orig_reg_p))
3793 vec_av_set.unordered_remove (n);
3794 if (sched_verbose >= 4)
3795 sel_print ("Expr %d has no suitable target register\n",
3796 INSN_UID (insn));
3798 /* A fence insn should not get here. */
3799 gcc_assert (!fence_insn_p);
3800 continue;
3803 /* At this point a fence insn should always be available. */
3804 gcc_assert (!fence_insn_p
3805 || INSN_UID (FENCE_INSN (fence)) == INSN_UID (EXPR_INSN_RTX (expr)));
3807 /* Filter expressions that need to be renamed or speculated when
3808 pipelining, because compensating register copies or speculation
3809 checks are likely to be placed near the beginning of the loop,
3810 causing a stall. */
3811 if (pipelining_p && EXPR_ORIG_SCHED_CYCLE (expr) > 0
3812 && (!is_orig_reg_p || EXPR_SPEC_DONE_DS (expr) != 0))
3814 /* Estimation of number of cycles until loop branch for
3815 renaming/speculation to be successful. */
3816 int need_n_ticks_till_branch = sel_vinsn_cost (EXPR_VINSN (expr));
3818 if ((int) current_loop_nest->ninsns < 9)
3820 vec_av_set.unordered_remove (n);
3821 if (sched_verbose >= 4)
3822 sel_print ("Pipelining expr %d will likely cause stall\n",
3823 INSN_UID (insn));
3824 continue;
3827 if ((int) current_loop_nest->ninsns - num_insns_scheduled
3828 < need_n_ticks_till_branch * issue_rate / 2
3829 && est_ticks_till_branch < need_n_ticks_till_branch)
3831 vec_av_set.unordered_remove (n);
3832 if (sched_verbose >= 4)
3833 sel_print ("Pipelining expr %d will likely cause stall\n",
3834 INSN_UID (insn));
3835 continue;
3839 /* We want to schedule speculation checks as late as possible. Discard
3840 them from av set if there are instructions with higher priority. */
3841 if (sel_insn_is_speculation_check (insn)
3842 && EXPR_PRIORITY (expr) < av_max_prio)
3844 stalled++;
3845 min_need_stall = min_need_stall < 0 ? 1 : MIN (min_need_stall, 1);
3846 vec_av_set.unordered_remove (n);
3847 if (sched_verbose >= 4)
3848 sel_print ("Delaying speculation check %d until its first use\n",
3849 INSN_UID (insn));
3850 continue;
3853 /* Ignore EXPRs available from pipelining to update AV_MAX_PRIO. */
3854 if (EXPR_ORIG_SCHED_CYCLE (expr) <= 0)
3855 av_max_prio = MAX (av_max_prio, EXPR_PRIORITY (expr));
3857 /* Don't allow any insns whose data is not yet ready.
3858 Check first whether we've already tried them and failed. */
3859 if (INSN_UID (insn) < FENCE_READY_TICKS_SIZE (fence))
3861 need_cycles = (FENCE_READY_TICKS (fence)[INSN_UID (insn)]
3862 - FENCE_CYCLE (fence));
3863 if (EXPR_ORIG_SCHED_CYCLE (expr) <= 0)
3864 est_ticks_till_branch = MAX (est_ticks_till_branch,
3865 EXPR_PRIORITY (expr) + need_cycles);
3867 if (need_cycles > 0)
3869 stalled++;
3870 min_need_stall = (min_need_stall < 0
3871 ? need_cycles
3872 : MIN (min_need_stall, need_cycles));
3873 vec_av_set.unordered_remove (n);
3875 if (sched_verbose >= 4)
3876 sel_print ("Expr %d is not ready until cycle %d (cached)\n",
3877 INSN_UID (insn),
3878 FENCE_READY_TICKS (fence)[INSN_UID (insn)]);
3879 continue;
3883 /* Now resort to dependence analysis to find whether EXPR might be
3884 stalled due to dependencies from FENCE's context. */
3885 need_cycles = tick_check_p (expr, dc, fence);
3886 new_prio = EXPR_PRIORITY (expr) + EXPR_PRIORITY_ADJ (expr) + need_cycles;
3888 if (EXPR_ORIG_SCHED_CYCLE (expr) <= 0)
3889 est_ticks_till_branch = MAX (est_ticks_till_branch,
3890 new_prio);
3892 if (need_cycles > 0)
3894 if (INSN_UID (insn) >= FENCE_READY_TICKS_SIZE (fence))
3896 int new_size = INSN_UID (insn) * 3 / 2;
3898 FENCE_READY_TICKS (fence)
3899 = (int *) xrecalloc (FENCE_READY_TICKS (fence),
3900 new_size, FENCE_READY_TICKS_SIZE (fence),
3901 sizeof (int));
3903 FENCE_READY_TICKS (fence)[INSN_UID (insn)]
3904 = FENCE_CYCLE (fence) + need_cycles;
3906 stalled++;
3907 min_need_stall = (min_need_stall < 0
3908 ? need_cycles
3909 : MIN (min_need_stall, need_cycles));
3911 vec_av_set.unordered_remove (n);
3913 if (sched_verbose >= 4)
3914 sel_print ("Expr %d is not ready yet until cycle %d\n",
3915 INSN_UID (insn),
3916 FENCE_READY_TICKS (fence)[INSN_UID (insn)]);
3917 continue;
3920 if (sched_verbose >= 4)
3921 sel_print ("Expr %d is ok\n", INSN_UID (insn));
3922 min_need_stall = 0;
3925 /* Clear SCHED_NEXT. */
3926 if (FENCE_SCHED_NEXT (fence))
3928 gcc_assert (sched_next_worked == 1);
3929 FENCE_SCHED_NEXT (fence) = NULL;
3932 /* No need to stall if this variable was not initialized. */
3933 if (min_need_stall < 0)
3934 min_need_stall = 0;
3936 if (vec_av_set.is_empty ())
3938 /* We need to set *pneed_stall here, because later we skip this code
3939 when ready list is empty. */
3940 *pneed_stall = min_need_stall;
3941 return false;
3943 else
3944 gcc_assert (min_need_stall == 0);
3946 /* Sort the vector. */
3947 vec_av_set.qsort (sel_rank_for_schedule);
3949 if (sched_verbose >= 4)
3951 sel_print ("Total ready exprs: %d, stalled: %d\n",
3952 vec_av_set.length (), stalled);
3953 sel_print ("Sorted av set (%d): ", vec_av_set.length ());
3954 FOR_EACH_VEC_ELT (vec_av_set, n, expr)
3955 dump_expr (expr);
3956 sel_print ("\n");
3959 *pneed_stall = 0;
3960 return true;
3963 /* Convert a vectored and sorted av set to the ready list that
3964 the rest of the backend wants to see. */
3965 static void
3966 convert_vec_av_set_to_ready (void)
3968 int n;
3969 expr_t expr;
3971 /* Allocate and fill the ready list from the sorted vector. */
3972 ready.n_ready = vec_av_set.length ();
3973 ready.first = ready.n_ready - 1;
3975 gcc_assert (ready.n_ready > 0);
3977 if (ready.n_ready > max_issue_size)
3979 max_issue_size = ready.n_ready;
3980 sched_extend_ready_list (ready.n_ready);
3983 FOR_EACH_VEC_ELT (vec_av_set, n, expr)
3985 vinsn_t vi = EXPR_VINSN (expr);
3986 insn_t insn = VINSN_INSN_RTX (vi);
3988 ready_try[n] = 0;
3989 ready.vec[n] = insn;
3993 /* Initialize ready list from *AV_PTR for the max_issue () call.
3994 If any unrecognizable insn found in *AV_PTR, return it (and skip
3995 max_issue). BND and FENCE are current boundary and fence,
3996 respectively. If we need to stall for some cycles before an expr
3997 from *AV_PTR would become available, write this number to *PNEED_STALL. */
3998 static expr_t
3999 fill_ready_list (av_set_t *av_ptr, blist_t bnds, fence_t fence,
4000 int *pneed_stall)
4002 expr_t expr;
4004 /* We do not support multiple boundaries per fence. */
4005 gcc_assert (BLIST_NEXT (bnds) == NULL);
4007 /* Process expressions required special handling, i.e. pipelined,
4008 speculative and recog() < 0 expressions first. */
4009 process_pipelined_exprs (av_ptr);
4010 process_spec_exprs (av_ptr);
4012 /* A USE could be scheduled immediately. */
4013 expr = process_use_exprs (av_ptr);
4014 if (expr)
4016 *pneed_stall = 0;
4017 return expr;
4020 /* Turn the av set to a vector for sorting. */
4021 if (! fill_vec_av_set (*av_ptr, bnds, fence, pneed_stall))
4023 ready.n_ready = 0;
4024 return NULL;
4027 /* Build the final ready list. */
4028 convert_vec_av_set_to_ready ();
4029 return NULL;
4032 /* Wrapper for dfa_new_cycle (). Returns TRUE if cycle was advanced. */
4033 static bool
4034 sel_dfa_new_cycle (insn_t insn, fence_t fence)
4036 int last_scheduled_cycle = FENCE_LAST_SCHEDULED_INSN (fence)
4037 ? INSN_SCHED_CYCLE (FENCE_LAST_SCHEDULED_INSN (fence))
4038 : FENCE_CYCLE (fence) - 1;
4039 bool res = false;
4040 int sort_p = 0;
4042 if (!targetm.sched.dfa_new_cycle)
4043 return false;
4045 memcpy (curr_state, FENCE_STATE (fence), dfa_state_size);
4047 while (!sort_p && targetm.sched.dfa_new_cycle (sched_dump, sched_verbose,
4048 insn, last_scheduled_cycle,
4049 FENCE_CYCLE (fence), &sort_p))
4051 memcpy (FENCE_STATE (fence), curr_state, dfa_state_size);
4052 advance_one_cycle (fence);
4053 memcpy (curr_state, FENCE_STATE (fence), dfa_state_size);
4054 res = true;
4057 return res;
4060 /* Invoke reorder* target hooks on the ready list. Return the number of insns
4061 we can issue. FENCE is the current fence. */
4062 static int
4063 invoke_reorder_hooks (fence_t fence)
4065 int issue_more;
4066 bool ran_hook = false;
4068 /* Call the reorder hook at the beginning of the cycle, and call
4069 the reorder2 hook in the middle of the cycle. */
4070 if (FENCE_ISSUED_INSNS (fence) == 0)
4072 if (targetm.sched.reorder
4073 && !SCHED_GROUP_P (ready_element (&ready, 0))
4074 && ready.n_ready > 1)
4076 /* Don't give reorder the most prioritized insn as it can break
4077 pipelining. */
4078 if (pipelining_p)
4079 --ready.n_ready;
4081 issue_more
4082 = targetm.sched.reorder (sched_dump, sched_verbose,
4083 ready_lastpos (&ready),
4084 &ready.n_ready, FENCE_CYCLE (fence));
4086 if (pipelining_p)
4087 ++ready.n_ready;
4089 ran_hook = true;
4091 else
4092 /* Initialize can_issue_more for variable_issue. */
4093 issue_more = issue_rate;
4095 else if (targetm.sched.reorder2
4096 && !SCHED_GROUP_P (ready_element (&ready, 0)))
4098 if (ready.n_ready == 1)
4099 issue_more =
4100 targetm.sched.reorder2 (sched_dump, sched_verbose,
4101 ready_lastpos (&ready),
4102 &ready.n_ready, FENCE_CYCLE (fence));
4103 else
4105 if (pipelining_p)
4106 --ready.n_ready;
4108 issue_more =
4109 targetm.sched.reorder2 (sched_dump, sched_verbose,
4110 ready.n_ready
4111 ? ready_lastpos (&ready) : NULL,
4112 &ready.n_ready, FENCE_CYCLE (fence));
4114 if (pipelining_p)
4115 ++ready.n_ready;
4118 ran_hook = true;
4120 else
4121 issue_more = FENCE_ISSUE_MORE (fence);
4123 /* Ensure that ready list and vec_av_set are in line with each other,
4124 i.e. vec_av_set[i] == ready_element (&ready, i). */
4125 if (issue_more && ran_hook)
4127 int i, j, n;
4128 rtx_insn **arr = ready.vec;
4129 expr_t *vec = vec_av_set.address ();
4131 for (i = 0, n = ready.n_ready; i < n; i++)
4132 if (EXPR_INSN_RTX (vec[i]) != arr[i])
4134 for (j = i; j < n; j++)
4135 if (EXPR_INSN_RTX (vec[j]) == arr[i])
4136 break;
4137 gcc_assert (j < n);
4139 std::swap (vec[i], vec[j]);
4143 return issue_more;
4146 /* Return an EXPR corresponding to INDEX element of ready list, if
4147 FOLLOW_READY_ELEMENT is true (i.e., an expr of
4148 ready_element (&ready, INDEX) will be returned), and to INDEX element of
4149 ready.vec otherwise. */
4150 static inline expr_t
4151 find_expr_for_ready (int index, bool follow_ready_element)
4153 expr_t expr;
4154 int real_index;
4156 real_index = follow_ready_element ? ready.first - index : index;
4158 expr = vec_av_set[real_index];
4159 gcc_assert (ready.vec[real_index] == EXPR_INSN_RTX (expr));
4161 return expr;
4164 /* Calculate insns worth trying via lookahead_guard hook. Return a number
4165 of such insns found. */
4166 static int
4167 invoke_dfa_lookahead_guard (void)
4169 int i, n;
4170 bool have_hook
4171 = targetm.sched.first_cycle_multipass_dfa_lookahead_guard != NULL;
4173 if (sched_verbose >= 2)
4174 sel_print ("ready after reorder: ");
4176 for (i = 0, n = 0; i < ready.n_ready; i++)
4178 expr_t expr;
4179 insn_t insn;
4180 int r;
4182 /* In this loop insn is Ith element of the ready list given by
4183 ready_element, not Ith element of ready.vec. */
4184 insn = ready_element (&ready, i);
4186 if (! have_hook || i == 0)
4187 r = 0;
4188 else
4189 r = targetm.sched.first_cycle_multipass_dfa_lookahead_guard (insn, i);
4191 gcc_assert (INSN_CODE (insn) >= 0);
4193 /* Only insns with ready_try = 0 can get here
4194 from fill_ready_list. */
4195 gcc_assert (ready_try [i] == 0);
4196 ready_try[i] = r;
4197 if (!r)
4198 n++;
4200 expr = find_expr_for_ready (i, true);
4202 if (sched_verbose >= 2)
4204 dump_vinsn (EXPR_VINSN (expr));
4205 sel_print (":%d; ", ready_try[i]);
4209 if (sched_verbose >= 2)
4210 sel_print ("\n");
4211 return n;
4214 /* Calculate the number of privileged insns and return it. */
4215 static int
4216 calculate_privileged_insns (void)
4218 expr_t cur_expr, min_spec_expr = NULL;
4219 int privileged_n = 0, i;
4221 for (i = 0; i < ready.n_ready; i++)
4223 if (ready_try[i])
4224 continue;
4226 if (! min_spec_expr)
4227 min_spec_expr = find_expr_for_ready (i, true);
4229 cur_expr = find_expr_for_ready (i, true);
4231 if (EXPR_SPEC (cur_expr) > EXPR_SPEC (min_spec_expr))
4232 break;
4234 ++privileged_n;
4237 if (i == ready.n_ready)
4238 privileged_n = 0;
4240 if (sched_verbose >= 2)
4241 sel_print ("privileged_n: %d insns with SPEC %d\n",
4242 privileged_n, privileged_n ? EXPR_SPEC (min_spec_expr) : -1);
4243 return privileged_n;
4246 /* Call the rest of the hooks after the choice was made. Return
4247 the number of insns that still can be issued given that the current
4248 number is ISSUE_MORE. FENCE and BEST_INSN are the current fence
4249 and the insn chosen for scheduling, respectively. */
4250 static int
4251 invoke_aftermath_hooks (fence_t fence, rtx_insn *best_insn, int issue_more)
4253 gcc_assert (INSN_P (best_insn));
4255 /* First, call dfa_new_cycle, and then variable_issue, if available. */
4256 sel_dfa_new_cycle (best_insn, fence);
4258 if (targetm.sched.variable_issue)
4260 memcpy (curr_state, FENCE_STATE (fence), dfa_state_size);
4261 issue_more =
4262 targetm.sched.variable_issue (sched_dump, sched_verbose, best_insn,
4263 issue_more);
4264 memcpy (FENCE_STATE (fence), curr_state, dfa_state_size);
4266 else if (!DEBUG_INSN_P (best_insn)
4267 && GET_CODE (PATTERN (best_insn)) != USE
4268 && GET_CODE (PATTERN (best_insn)) != CLOBBER)
4269 issue_more--;
4271 return issue_more;
4274 /* Estimate the cost of issuing INSN on DFA state STATE. */
4275 static int
4276 estimate_insn_cost (rtx_insn *insn, state_t state)
4278 static state_t temp = NULL;
4279 int cost;
4281 if (!temp)
4282 temp = xmalloc (dfa_state_size);
4284 memcpy (temp, state, dfa_state_size);
4285 cost = state_transition (temp, insn);
4287 if (cost < 0)
4288 return 0;
4289 else if (cost == 0)
4290 return 1;
4291 return cost;
4294 /* Return the cost of issuing EXPR on the FENCE as estimated by DFA.
4295 This function properly handles ASMs, USEs etc. */
4296 static int
4297 get_expr_cost (expr_t expr, fence_t fence)
4299 rtx_insn *insn = EXPR_INSN_RTX (expr);
4301 if (recog_memoized (insn) < 0)
4303 if (!FENCE_STARTS_CYCLE_P (fence)
4304 && INSN_ASM_P (insn))
4305 /* This is asm insn which is tryed to be issued on the
4306 cycle not first. Issue it on the next cycle. */
4307 return 1;
4308 else
4309 /* A USE insn, or something else we don't need to
4310 understand. We can't pass these directly to
4311 state_transition because it will trigger a
4312 fatal error for unrecognizable insns. */
4313 return 0;
4315 else
4316 return estimate_insn_cost (insn, FENCE_STATE (fence));
4319 /* Find the best insn for scheduling, either via max_issue or just take
4320 the most prioritized available. */
4321 static int
4322 choose_best_insn (fence_t fence, int privileged_n, int *index)
4324 int can_issue = 0;
4326 if (dfa_lookahead > 0)
4328 cycle_issued_insns = FENCE_ISSUED_INSNS (fence);
4329 /* TODO: pass equivalent of first_cycle_insn_p to max_issue (). */
4330 can_issue = max_issue (&ready, privileged_n,
4331 FENCE_STATE (fence), true, index);
4332 if (sched_verbose >= 2)
4333 sel_print ("max_issue: we can issue %d insns, already did %d insns\n",
4334 can_issue, FENCE_ISSUED_INSNS (fence));
4336 else
4338 /* We can't use max_issue; just return the first available element. */
4339 int i;
4341 for (i = 0; i < ready.n_ready; i++)
4343 expr_t expr = find_expr_for_ready (i, true);
4345 if (get_expr_cost (expr, fence) < 1)
4347 can_issue = can_issue_more;
4348 *index = i;
4350 if (sched_verbose >= 2)
4351 sel_print ("using %dth insn from the ready list\n", i + 1);
4353 break;
4357 if (i == ready.n_ready)
4359 can_issue = 0;
4360 *index = -1;
4364 return can_issue;
4367 /* Choose the best expr from *AV_VLIW_PTR and a suitable register for it.
4368 BNDS and FENCE are current boundaries and scheduling fence respectively.
4369 Return the expr found and NULL if nothing can be issued atm.
4370 Write to PNEED_STALL the number of cycles to stall if no expr was found. */
4371 static expr_t
4372 find_best_expr (av_set_t *av_vliw_ptr, blist_t bnds, fence_t fence,
4373 int *pneed_stall)
4375 expr_t best;
4377 /* Choose the best insn for scheduling via:
4378 1) sorting the ready list based on priority;
4379 2) calling the reorder hook;
4380 3) calling max_issue. */
4381 best = fill_ready_list (av_vliw_ptr, bnds, fence, pneed_stall);
4382 if (best == NULL && ready.n_ready > 0)
4384 int privileged_n, index;
4386 can_issue_more = invoke_reorder_hooks (fence);
4387 if (can_issue_more > 0)
4389 /* Try choosing the best insn until we find one that is could be
4390 scheduled due to liveness restrictions on its destination register.
4391 In the future, we'd like to choose once and then just probe insns
4392 in the order of their priority. */
4393 invoke_dfa_lookahead_guard ();
4394 privileged_n = calculate_privileged_insns ();
4395 can_issue_more = choose_best_insn (fence, privileged_n, &index);
4396 if (can_issue_more)
4397 best = find_expr_for_ready (index, true);
4399 /* We had some available insns, so if we can't issue them,
4400 we have a stall. */
4401 if (can_issue_more == 0)
4403 best = NULL;
4404 *pneed_stall = 1;
4408 if (best != NULL)
4410 can_issue_more = invoke_aftermath_hooks (fence, EXPR_INSN_RTX (best),
4411 can_issue_more);
4412 if (targetm.sched.variable_issue
4413 && can_issue_more == 0)
4414 *pneed_stall = 1;
4417 if (sched_verbose >= 2)
4419 if (best != NULL)
4421 sel_print ("Best expression (vliw form): ");
4422 dump_expr (best);
4423 sel_print ("; cycle %d\n", FENCE_CYCLE (fence));
4425 else
4426 sel_print ("No best expr found!\n");
4429 return best;
4433 /* Functions that implement the core of the scheduler. */
4436 /* Emit an instruction from EXPR with SEQNO and VINSN after
4437 PLACE_TO_INSERT. */
4438 static insn_t
4439 emit_insn_from_expr_after (expr_t expr, vinsn_t vinsn, int seqno,
4440 insn_t place_to_insert)
4442 /* This assert fails when we have identical instructions
4443 one of which dominates the other. In this case move_op ()
4444 finds the first instruction and doesn't search for second one.
4445 The solution would be to compute av_set after the first found
4446 insn and, if insn present in that set, continue searching.
4447 For now we workaround this issue in move_op. */
4448 gcc_assert (!INSN_IN_STREAM_P (EXPR_INSN_RTX (expr)));
4450 if (EXPR_WAS_RENAMED (expr))
4452 unsigned regno = expr_dest_regno (expr);
4454 if (HARD_REGISTER_NUM_P (regno))
4456 df_set_regs_ever_live (regno, true);
4457 reg_rename_tick[regno] = ++reg_rename_this_tick;
4461 return sel_gen_insn_from_expr_after (expr, vinsn, seqno,
4462 place_to_insert);
4465 /* Return TRUE if BB can hold bookkeeping code. */
4466 static bool
4467 block_valid_for_bookkeeping_p (basic_block bb)
4469 insn_t bb_end = BB_END (bb);
4471 if (!in_current_region_p (bb) || EDGE_COUNT (bb->succs) > 1)
4472 return false;
4474 if (INSN_P (bb_end))
4476 if (INSN_SCHED_TIMES (bb_end) > 0)
4477 return false;
4479 else
4480 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (bb_end));
4482 return true;
4485 /* Attempt to find a block that can hold bookkeeping code for path(s) incoming
4486 into E2->dest, except from E1->src (there may be a sequence of empty basic
4487 blocks between E1->src and E2->dest). Return found block, or NULL if new
4488 one must be created. If LAX holds, don't assume there is a simple path
4489 from E1->src to E2->dest. */
4490 static basic_block
4491 find_block_for_bookkeeping (edge e1, edge e2, bool lax)
4493 basic_block candidate_block = NULL;
4494 edge e;
4496 /* Loop over edges from E1 to E2, inclusive. */
4497 for (e = e1; !lax || e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun); e =
4498 EDGE_SUCC (e->dest, 0))
4500 if (EDGE_COUNT (e->dest->preds) == 2)
4502 if (candidate_block == NULL)
4503 candidate_block = (EDGE_PRED (e->dest, 0) == e
4504 ? EDGE_PRED (e->dest, 1)->src
4505 : EDGE_PRED (e->dest, 0)->src);
4506 else
4507 /* Found additional edge leading to path from e1 to e2
4508 from aside. */
4509 return NULL;
4511 else if (EDGE_COUNT (e->dest->preds) > 2)
4512 /* Several edges leading to path from e1 to e2 from aside. */
4513 return NULL;
4515 if (e == e2)
4516 return ((!lax || candidate_block)
4517 && block_valid_for_bookkeeping_p (candidate_block)
4518 ? candidate_block
4519 : NULL);
4521 if (lax && EDGE_COUNT (e->dest->succs) != 1)
4522 return NULL;
4525 if (lax)
4526 return NULL;
4528 gcc_unreachable ();
4531 /* Create new basic block for bookkeeping code for path(s) incoming into
4532 E2->dest, except from E1->src. Return created block. */
4533 static basic_block
4534 create_block_for_bookkeeping (edge e1, edge e2)
4536 basic_block new_bb, bb = e2->dest;
4538 /* Check that we don't spoil the loop structure. */
4539 if (current_loop_nest)
4541 basic_block latch = current_loop_nest->latch;
4543 /* We do not split header. */
4544 gcc_assert (e2->dest != current_loop_nest->header);
4546 /* We do not redirect the only edge to the latch block. */
4547 gcc_assert (e1->dest != latch
4548 || !single_pred_p (latch)
4549 || e1 != single_pred_edge (latch));
4552 /* Split BB to insert BOOK_INSN there. */
4553 new_bb = sched_split_block (bb, NULL);
4555 /* Move note_list from the upper bb. */
4556 gcc_assert (BB_NOTE_LIST (new_bb) == NULL_RTX);
4557 BB_NOTE_LIST (new_bb) = BB_NOTE_LIST (bb);
4558 BB_NOTE_LIST (bb) = NULL;
4560 gcc_assert (e2->dest == bb);
4562 /* Skip block for bookkeeping copy when leaving E1->src. */
4563 if (e1->flags & EDGE_FALLTHRU)
4564 sel_redirect_edge_and_branch_force (e1, new_bb);
4565 else
4566 sel_redirect_edge_and_branch (e1, new_bb);
4568 gcc_assert (e1->dest == new_bb);
4569 gcc_assert (sel_bb_empty_p (bb));
4571 /* To keep basic block numbers in sync between debug and non-debug
4572 compilations, we have to rotate blocks here. Consider that we
4573 started from (a,b)->d, (c,d)->e, and d contained only debug
4574 insns. It would have been removed before if the debug insns
4575 weren't there, so we'd have split e rather than d. So what we do
4576 now is to swap the block numbers of new_bb and
4577 single_succ(new_bb) == e, so that the insns that were in e before
4578 get the new block number. */
4580 if (MAY_HAVE_DEBUG_INSNS)
4582 basic_block succ;
4583 insn_t insn = sel_bb_head (new_bb);
4584 insn_t last;
4586 if (DEBUG_INSN_P (insn)
4587 && single_succ_p (new_bb)
4588 && (succ = single_succ (new_bb))
4589 && succ != EXIT_BLOCK_PTR_FOR_FN (cfun)
4590 && DEBUG_INSN_P ((last = sel_bb_end (new_bb))))
4592 while (insn != last && (DEBUG_INSN_P (insn) || NOTE_P (insn)))
4593 insn = NEXT_INSN (insn);
4595 if (insn == last)
4597 sel_global_bb_info_def gbi;
4598 sel_region_bb_info_def rbi;
4600 if (sched_verbose >= 2)
4601 sel_print ("Swapping block ids %i and %i\n",
4602 new_bb->index, succ->index);
4604 std::swap (new_bb->index, succ->index);
4606 SET_BASIC_BLOCK_FOR_FN (cfun, new_bb->index, new_bb);
4607 SET_BASIC_BLOCK_FOR_FN (cfun, succ->index, succ);
4609 memcpy (&gbi, SEL_GLOBAL_BB_INFO (new_bb), sizeof (gbi));
4610 memcpy (SEL_GLOBAL_BB_INFO (new_bb), SEL_GLOBAL_BB_INFO (succ),
4611 sizeof (gbi));
4612 memcpy (SEL_GLOBAL_BB_INFO (succ), &gbi, sizeof (gbi));
4614 memcpy (&rbi, SEL_REGION_BB_INFO (new_bb), sizeof (rbi));
4615 memcpy (SEL_REGION_BB_INFO (new_bb), SEL_REGION_BB_INFO (succ),
4616 sizeof (rbi));
4617 memcpy (SEL_REGION_BB_INFO (succ), &rbi, sizeof (rbi));
4619 std::swap (BLOCK_TO_BB (new_bb->index),
4620 BLOCK_TO_BB (succ->index));
4622 std::swap (CONTAINING_RGN (new_bb->index),
4623 CONTAINING_RGN (succ->index));
4625 for (int i = 0; i < current_nr_blocks; i++)
4626 if (BB_TO_BLOCK (i) == succ->index)
4627 BB_TO_BLOCK (i) = new_bb->index;
4628 else if (BB_TO_BLOCK (i) == new_bb->index)
4629 BB_TO_BLOCK (i) = succ->index;
4631 FOR_BB_INSNS (new_bb, insn)
4632 if (INSN_P (insn))
4633 EXPR_ORIG_BB_INDEX (INSN_EXPR (insn)) = new_bb->index;
4635 FOR_BB_INSNS (succ, insn)
4636 if (INSN_P (insn))
4637 EXPR_ORIG_BB_INDEX (INSN_EXPR (insn)) = succ->index;
4639 if (bitmap_clear_bit (code_motion_visited_blocks, new_bb->index))
4640 bitmap_set_bit (code_motion_visited_blocks, succ->index);
4642 gcc_assert (LABEL_P (BB_HEAD (new_bb))
4643 && LABEL_P (BB_HEAD (succ)));
4645 if (sched_verbose >= 4)
4646 sel_print ("Swapping code labels %i and %i\n",
4647 CODE_LABEL_NUMBER (BB_HEAD (new_bb)),
4648 CODE_LABEL_NUMBER (BB_HEAD (succ)));
4650 std::swap (CODE_LABEL_NUMBER (BB_HEAD (new_bb)),
4651 CODE_LABEL_NUMBER (BB_HEAD (succ)));
4656 return bb;
4659 /* Return insn after which we must insert bookkeeping code for path(s) incoming
4660 into E2->dest, except from E1->src. If the returned insn immediately
4661 precedes a fence, assign that fence to *FENCE_TO_REWIND. */
4662 static insn_t
4663 find_place_for_bookkeeping (edge e1, edge e2, fence_t *fence_to_rewind)
4665 insn_t place_to_insert;
4666 /* Find a basic block that can hold bookkeeping. If it can be found, do not
4667 create new basic block, but insert bookkeeping there. */
4668 basic_block book_block = find_block_for_bookkeeping (e1, e2, FALSE);
4670 if (book_block)
4672 place_to_insert = BB_END (book_block);
4674 /* Don't use a block containing only debug insns for
4675 bookkeeping, this causes scheduling differences between debug
4676 and non-debug compilations, for the block would have been
4677 removed already. */
4678 if (DEBUG_INSN_P (place_to_insert))
4680 rtx_insn *insn = sel_bb_head (book_block);
4682 while (insn != place_to_insert &&
4683 (DEBUG_INSN_P (insn) || NOTE_P (insn)))
4684 insn = NEXT_INSN (insn);
4686 if (insn == place_to_insert)
4687 book_block = NULL;
4691 if (!book_block)
4693 book_block = create_block_for_bookkeeping (e1, e2);
4694 place_to_insert = BB_END (book_block);
4695 if (sched_verbose >= 9)
4696 sel_print ("New block is %i, split from bookkeeping block %i\n",
4697 EDGE_SUCC (book_block, 0)->dest->index, book_block->index);
4699 else
4701 if (sched_verbose >= 9)
4702 sel_print ("Pre-existing bookkeeping block is %i\n", book_block->index);
4705 *fence_to_rewind = NULL;
4706 /* If basic block ends with a jump, insert bookkeeping code right before it.
4707 Notice if we are crossing a fence when taking PREV_INSN. */
4708 if (INSN_P (place_to_insert) && control_flow_insn_p (place_to_insert))
4710 *fence_to_rewind = flist_lookup (fences, place_to_insert);
4711 place_to_insert = PREV_INSN (place_to_insert);
4714 return place_to_insert;
4717 /* Find a proper seqno for bookkeeing insn inserted at PLACE_TO_INSERT
4718 for JOIN_POINT. */
4719 static int
4720 find_seqno_for_bookkeeping (insn_t place_to_insert, insn_t join_point)
4722 int seqno;
4724 /* Check if we are about to insert bookkeeping copy before a jump, and use
4725 jump's seqno for the copy; otherwise, use JOIN_POINT's seqno. */
4726 rtx_insn *next = NEXT_INSN (place_to_insert);
4727 if (INSN_P (next)
4728 && JUMP_P (next)
4729 && BLOCK_FOR_INSN (next) == BLOCK_FOR_INSN (place_to_insert))
4731 gcc_assert (INSN_SCHED_TIMES (next) == 0);
4732 seqno = INSN_SEQNO (next);
4734 else if (INSN_SEQNO (join_point) > 0)
4735 seqno = INSN_SEQNO (join_point);
4736 else
4738 seqno = get_seqno_by_preds (place_to_insert);
4740 /* Sometimes the fences can move in such a way that there will be
4741 no instructions with positive seqno around this bookkeeping.
4742 This means that there will be no way to get to it by a regular
4743 fence movement. Never mind because we pick up such pieces for
4744 rescheduling anyways, so any positive value will do for now. */
4745 if (seqno < 0)
4747 gcc_assert (pipelining_p);
4748 seqno = 1;
4752 gcc_assert (seqno > 0);
4753 return seqno;
4756 /* Insert bookkeeping copy of C_EXPS's insn after PLACE_TO_INSERT, assigning
4757 NEW_SEQNO to it. Return created insn. */
4758 static insn_t
4759 emit_bookkeeping_insn (insn_t place_to_insert, expr_t c_expr, int new_seqno)
4761 rtx_insn *new_insn_rtx = create_copy_of_insn_rtx (EXPR_INSN_RTX (c_expr));
4763 vinsn_t new_vinsn
4764 = create_vinsn_from_insn_rtx (new_insn_rtx,
4765 VINSN_UNIQUE_P (EXPR_VINSN (c_expr)));
4767 insn_t new_insn = emit_insn_from_expr_after (c_expr, new_vinsn, new_seqno,
4768 place_to_insert);
4770 INSN_SCHED_TIMES (new_insn) = 0;
4771 bitmap_set_bit (current_copies, INSN_UID (new_insn));
4773 return new_insn;
4776 /* Generate a bookkeeping copy of C_EXPR's insn for path(s) incoming into to
4777 E2->dest, except from E1->src (there may be a sequence of empty blocks
4778 between E1->src and E2->dest). Return block containing the copy.
4779 All scheduler data is initialized for the newly created insn. */
4780 static basic_block
4781 generate_bookkeeping_insn (expr_t c_expr, edge e1, edge e2)
4783 insn_t join_point, place_to_insert, new_insn;
4784 int new_seqno;
4785 bool need_to_exchange_data_sets;
4786 fence_t fence_to_rewind;
4788 if (sched_verbose >= 4)
4789 sel_print ("Generating bookkeeping insn (%d->%d)\n", e1->src->index,
4790 e2->dest->index);
4792 join_point = sel_bb_head (e2->dest);
4793 place_to_insert = find_place_for_bookkeeping (e1, e2, &fence_to_rewind);
4794 new_seqno = find_seqno_for_bookkeeping (place_to_insert, join_point);
4795 need_to_exchange_data_sets
4796 = sel_bb_empty_p (BLOCK_FOR_INSN (place_to_insert));
4798 new_insn = emit_bookkeeping_insn (place_to_insert, c_expr, new_seqno);
4800 if (fence_to_rewind)
4801 FENCE_INSN (fence_to_rewind) = new_insn;
4803 /* When inserting bookkeeping insn in new block, av sets should be
4804 following: old basic block (that now holds bookkeeping) data sets are
4805 the same as was before generation of bookkeeping, and new basic block
4806 (that now hold all other insns of old basic block) data sets are
4807 invalid. So exchange data sets for these basic blocks as sel_split_block
4808 mistakenly exchanges them in this case. Cannot do it earlier because
4809 when single instruction is added to new basic block it should hold NULL
4810 lv_set. */
4811 if (need_to_exchange_data_sets)
4812 exchange_data_sets (BLOCK_FOR_INSN (new_insn),
4813 BLOCK_FOR_INSN (join_point));
4815 stat_bookkeeping_copies++;
4816 return BLOCK_FOR_INSN (new_insn);
4819 /* Remove from AV_PTR all insns that may need bookkeeping when scheduling
4820 on FENCE, but we are unable to copy them. */
4821 static void
4822 remove_insns_that_need_bookkeeping (fence_t fence, av_set_t *av_ptr)
4824 expr_t expr;
4825 av_set_iterator i;
4827 /* An expression does not need bookkeeping if it is available on all paths
4828 from current block to original block and current block dominates
4829 original block. We check availability on all paths by examining
4830 EXPR_SPEC; this is not equivalent, because it may be positive even
4831 if expr is available on all paths (but if expr is not available on
4832 any path, EXPR_SPEC will be positive). */
4834 FOR_EACH_EXPR_1 (expr, i, av_ptr)
4836 if (!control_flow_insn_p (EXPR_INSN_RTX (expr))
4837 && (!bookkeeping_p || VINSN_UNIQUE_P (EXPR_VINSN (expr)))
4838 && (EXPR_SPEC (expr)
4839 || !EXPR_ORIG_BB_INDEX (expr)
4840 || !dominated_by_p (CDI_DOMINATORS,
4841 BASIC_BLOCK_FOR_FN (cfun,
4842 EXPR_ORIG_BB_INDEX (expr)),
4843 BLOCK_FOR_INSN (FENCE_INSN (fence)))))
4845 if (sched_verbose >= 4)
4846 sel_print ("Expr %d removed because it would need bookkeeping, which "
4847 "cannot be created\n", INSN_UID (EXPR_INSN_RTX (expr)));
4848 av_set_iter_remove (&i);
4853 /* Moving conditional jump through some instructions.
4855 Consider example:
4857 ... <- current scheduling point
4858 NOTE BASIC BLOCK: <- bb header
4859 (p8) add r14=r14+0x9;;
4860 (p8) mov [r14]=r23
4861 (!p8) jump L1;;
4862 NOTE BASIC BLOCK:
4865 We can schedule jump one cycle earlier, than mov, because they cannot be
4866 executed together as their predicates are mutually exclusive.
4868 This is done in this way: first, new fallthrough basic block is created
4869 after jump (it is always can be done, because there already should be a
4870 fallthrough block, where control flow goes in case of predicate being true -
4871 in our example; otherwise there should be a dependence between those
4872 instructions and jump and we cannot schedule jump right now);
4873 next, all instructions between jump and current scheduling point are moved
4874 to this new block. And the result is this:
4876 NOTE BASIC BLOCK:
4877 (!p8) jump L1 <- current scheduling point
4878 NOTE BASIC BLOCK: <- bb header
4879 (p8) add r14=r14+0x9;;
4880 (p8) mov [r14]=r23
4881 NOTE BASIC BLOCK:
4884 static void
4885 move_cond_jump (rtx_insn *insn, bnd_t bnd)
4887 edge ft_edge;
4888 basic_block block_from, block_next, block_new, block_bnd, bb;
4889 rtx_insn *next, *prev, *link, *head;
4891 block_from = BLOCK_FOR_INSN (insn);
4892 block_bnd = BLOCK_FOR_INSN (BND_TO (bnd));
4893 prev = BND_TO (bnd);
4895 /* Moving of jump should not cross any other jumps or beginnings of new
4896 basic blocks. The only exception is when we move a jump through
4897 mutually exclusive insns along fallthru edges. */
4898 if (flag_checking && block_from != block_bnd)
4900 bb = block_from;
4901 for (link = PREV_INSN (insn); link != PREV_INSN (prev);
4902 link = PREV_INSN (link))
4904 if (INSN_P (link))
4905 gcc_assert (sched_insns_conditions_mutex_p (insn, link));
4906 if (BLOCK_FOR_INSN (link) && BLOCK_FOR_INSN (link) != bb)
4908 gcc_assert (single_pred (bb) == BLOCK_FOR_INSN (link));
4909 bb = BLOCK_FOR_INSN (link);
4914 /* Jump is moved to the boundary. */
4915 next = PREV_INSN (insn);
4916 BND_TO (bnd) = insn;
4918 ft_edge = find_fallthru_edge_from (block_from);
4919 block_next = ft_edge->dest;
4920 /* There must be a fallthrough block (or where should go
4921 control flow in case of false jump predicate otherwise?). */
4922 gcc_assert (block_next);
4924 /* Create new empty basic block after source block. */
4925 block_new = sel_split_edge (ft_edge);
4926 gcc_assert (block_new->next_bb == block_next
4927 && block_from->next_bb == block_new);
4929 /* Move all instructions except INSN to BLOCK_NEW. */
4930 bb = block_bnd;
4931 head = BB_HEAD (block_new);
4932 while (bb != block_from->next_bb)
4934 rtx_insn *from, *to;
4935 from = bb == block_bnd ? prev : sel_bb_head (bb);
4936 to = bb == block_from ? next : sel_bb_end (bb);
4938 /* The jump being moved can be the first insn in the block.
4939 In this case we don't have to move anything in this block. */
4940 if (NEXT_INSN (to) != from)
4942 reorder_insns (from, to, head);
4944 for (link = to; link != head; link = PREV_INSN (link))
4945 EXPR_ORIG_BB_INDEX (INSN_EXPR (link)) = block_new->index;
4946 head = to;
4949 /* Cleanup possibly empty blocks left. */
4950 block_next = bb->next_bb;
4951 if (bb != block_from)
4952 tidy_control_flow (bb, false);
4953 bb = block_next;
4956 /* Assert there is no jump to BLOCK_NEW, only fallthrough edge. */
4957 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (BB_HEAD (block_new)));
4959 gcc_assert (!sel_bb_empty_p (block_from)
4960 && !sel_bb_empty_p (block_new));
4962 /* Update data sets for BLOCK_NEW to represent that INSN and
4963 instructions from the other branch of INSN is no longer
4964 available at BLOCK_NEW. */
4965 BB_AV_LEVEL (block_new) = global_level;
4966 gcc_assert (BB_LV_SET (block_new) == NULL);
4967 BB_LV_SET (block_new) = get_clear_regset_from_pool ();
4968 update_data_sets (sel_bb_head (block_new));
4970 /* INSN is a new basic block header - so prepare its data
4971 structures and update availability and liveness sets. */
4972 update_data_sets (insn);
4974 if (sched_verbose >= 4)
4975 sel_print ("Moving jump %d\n", INSN_UID (insn));
4978 /* Remove nops generated during move_op for preventing removal of empty
4979 basic blocks. */
4980 static void
4981 remove_temp_moveop_nops (bool full_tidying)
4983 int i;
4984 insn_t insn;
4986 FOR_EACH_VEC_ELT (vec_temp_moveop_nops, i, insn)
4988 gcc_assert (INSN_NOP_P (insn));
4989 return_nop_to_pool (insn, full_tidying);
4992 /* Empty the vector. */
4993 if (vec_temp_moveop_nops.length () > 0)
4994 vec_temp_moveop_nops.block_remove (0, vec_temp_moveop_nops.length ());
4997 /* Records the maximal UID before moving up an instruction. Used for
4998 distinguishing between bookkeeping copies and original insns. */
4999 static int max_uid_before_move_op = 0;
5001 /* Remove from AV_VLIW_P all instructions but next when debug counter
5002 tells us so. Next instruction is fetched from BNDS. */
5003 static void
5004 remove_insns_for_debug (blist_t bnds, av_set_t *av_vliw_p)
5006 if (! dbg_cnt (sel_sched_insn_cnt))
5007 /* Leave only the next insn in av_vliw. */
5009 av_set_iterator av_it;
5010 expr_t expr;
5011 bnd_t bnd = BLIST_BND (bnds);
5012 insn_t next = BND_TO (bnd);
5014 gcc_assert (BLIST_NEXT (bnds) == NULL);
5016 FOR_EACH_EXPR_1 (expr, av_it, av_vliw_p)
5017 if (EXPR_INSN_RTX (expr) != next)
5018 av_set_iter_remove (&av_it);
5022 /* Compute available instructions on BNDS. FENCE is the current fence. Write
5023 the computed set to *AV_VLIW_P. */
5024 static void
5025 compute_av_set_on_boundaries (fence_t fence, blist_t bnds, av_set_t *av_vliw_p)
5027 if (sched_verbose >= 2)
5029 sel_print ("Boundaries: ");
5030 dump_blist (bnds);
5031 sel_print ("\n");
5034 for (; bnds; bnds = BLIST_NEXT (bnds))
5036 bnd_t bnd = BLIST_BND (bnds);
5037 av_set_t av1_copy;
5038 insn_t bnd_to = BND_TO (bnd);
5040 /* Rewind BND->TO to the basic block header in case some bookkeeping
5041 instructions were inserted before BND->TO and it needs to be
5042 adjusted. */
5043 if (sel_bb_head_p (bnd_to))
5044 gcc_assert (INSN_SCHED_TIMES (bnd_to) == 0);
5045 else
5046 while (INSN_SCHED_TIMES (PREV_INSN (bnd_to)) == 0)
5048 bnd_to = PREV_INSN (bnd_to);
5049 if (sel_bb_head_p (bnd_to))
5050 break;
5053 if (BND_TO (bnd) != bnd_to)
5055 gcc_assert (FENCE_INSN (fence) == BND_TO (bnd));
5056 FENCE_INSN (fence) = bnd_to;
5057 BND_TO (bnd) = bnd_to;
5060 av_set_clear (&BND_AV (bnd));
5061 BND_AV (bnd) = compute_av_set (BND_TO (bnd), NULL, 0, true);
5063 av_set_clear (&BND_AV1 (bnd));
5064 BND_AV1 (bnd) = av_set_copy (BND_AV (bnd));
5066 moveup_set_inside_insn_group (&BND_AV1 (bnd), NULL);
5068 av1_copy = av_set_copy (BND_AV1 (bnd));
5069 av_set_union_and_clear (av_vliw_p, &av1_copy, NULL);
5072 if (sched_verbose >= 2)
5074 sel_print ("Available exprs (vliw form): ");
5075 dump_av_set (*av_vliw_p);
5076 sel_print ("\n");
5080 /* Calculate the sequential av set on BND corresponding to the EXPR_VLIW
5081 expression. When FOR_MOVEOP is true, also replace the register of
5082 expressions found with the register from EXPR_VLIW. */
5083 static av_set_t
5084 find_sequential_best_exprs (bnd_t bnd, expr_t expr_vliw, bool for_moveop)
5086 av_set_t expr_seq = NULL;
5087 expr_t expr;
5088 av_set_iterator i;
5090 FOR_EACH_EXPR (expr, i, BND_AV (bnd))
5092 if (equal_after_moveup_path_p (expr, NULL, expr_vliw))
5094 if (for_moveop)
5096 /* The sequential expression has the right form to pass
5097 to move_op except when renaming happened. Put the
5098 correct register in EXPR then. */
5099 if (EXPR_SEPARABLE_P (expr) && REG_P (EXPR_LHS (expr)))
5101 if (expr_dest_regno (expr) != expr_dest_regno (expr_vliw))
5103 replace_dest_with_reg_in_expr (expr, EXPR_LHS (expr_vliw));
5104 stat_renamed_scheduled++;
5106 /* Also put the correct TARGET_AVAILABLE bit on the expr.
5107 This is needed when renaming came up with original
5108 register. */
5109 else if (EXPR_TARGET_AVAILABLE (expr)
5110 != EXPR_TARGET_AVAILABLE (expr_vliw))
5112 gcc_assert (EXPR_TARGET_AVAILABLE (expr_vliw) == 1);
5113 EXPR_TARGET_AVAILABLE (expr) = 1;
5116 if (EXPR_WAS_SUBSTITUTED (expr))
5117 stat_substitutions_total++;
5120 av_set_add (&expr_seq, expr);
5122 /* With substitution inside insn group, it is possible
5123 that more than one expression in expr_seq will correspond
5124 to expr_vliw. In this case, choose one as the attempt to
5125 move both leads to miscompiles. */
5126 break;
5130 if (for_moveop && sched_verbose >= 2)
5132 sel_print ("Best expression(s) (sequential form): ");
5133 dump_av_set (expr_seq);
5134 sel_print ("\n");
5137 return expr_seq;
5141 /* Move nop to previous block. */
5142 static void ATTRIBUTE_UNUSED
5143 move_nop_to_previous_block (insn_t nop, basic_block prev_bb)
5145 insn_t prev_insn, next_insn;
5147 gcc_assert (sel_bb_head_p (nop)
5148 && prev_bb == BLOCK_FOR_INSN (nop)->prev_bb);
5149 rtx_note *note = bb_note (BLOCK_FOR_INSN (nop));
5150 prev_insn = sel_bb_end (prev_bb);
5151 next_insn = NEXT_INSN (nop);
5152 gcc_assert (prev_insn != NULL_RTX
5153 && PREV_INSN (note) == prev_insn);
5155 SET_NEXT_INSN (prev_insn) = nop;
5156 SET_PREV_INSN (nop) = prev_insn;
5158 SET_PREV_INSN (note) = nop;
5159 SET_NEXT_INSN (note) = next_insn;
5161 SET_NEXT_INSN (nop) = note;
5162 SET_PREV_INSN (next_insn) = note;
5164 BB_END (prev_bb) = nop;
5165 BLOCK_FOR_INSN (nop) = prev_bb;
5168 /* Prepare a place to insert the chosen expression on BND. */
5169 static insn_t
5170 prepare_place_to_insert (bnd_t bnd)
5172 insn_t place_to_insert;
5174 /* Init place_to_insert before calling move_op, as the later
5175 can possibly remove BND_TO (bnd). */
5176 if (/* If this is not the first insn scheduled. */
5177 BND_PTR (bnd))
5179 /* Add it after last scheduled. */
5180 place_to_insert = ILIST_INSN (BND_PTR (bnd));
5181 if (DEBUG_INSN_P (place_to_insert))
5183 ilist_t l = BND_PTR (bnd);
5184 while ((l = ILIST_NEXT (l)) &&
5185 DEBUG_INSN_P (ILIST_INSN (l)))
5187 if (!l)
5188 place_to_insert = NULL;
5191 else
5192 place_to_insert = NULL;
5194 if (!place_to_insert)
5196 /* Add it before BND_TO. The difference is in the
5197 basic block, where INSN will be added. */
5198 place_to_insert = get_nop_from_pool (BND_TO (bnd));
5199 gcc_assert (BLOCK_FOR_INSN (place_to_insert)
5200 == BLOCK_FOR_INSN (BND_TO (bnd)));
5203 return place_to_insert;
5206 /* Find original instructions for EXPR_SEQ and move it to BND boundary.
5207 Return the expression to emit in C_EXPR. */
5208 static bool
5209 move_exprs_to_boundary (bnd_t bnd, expr_t expr_vliw,
5210 av_set_t expr_seq, expr_t c_expr)
5212 bool b, should_move;
5213 unsigned book_uid;
5214 bitmap_iterator bi;
5215 int n_bookkeeping_copies_before_moveop;
5217 /* Make a move. This call will remove the original operation,
5218 insert all necessary bookkeeping instructions and update the
5219 data sets. After that all we have to do is add the operation
5220 at before BND_TO (BND). */
5221 n_bookkeeping_copies_before_moveop = stat_bookkeeping_copies;
5222 max_uid_before_move_op = get_max_uid ();
5223 bitmap_clear (current_copies);
5224 bitmap_clear (current_originators);
5226 b = move_op (BND_TO (bnd), expr_seq, expr_vliw,
5227 get_dest_from_orig_ops (expr_seq), c_expr, &should_move);
5229 /* We should be able to find the expression we've chosen for
5230 scheduling. */
5231 gcc_assert (b);
5233 if (stat_bookkeeping_copies > n_bookkeeping_copies_before_moveop)
5234 stat_insns_needed_bookkeeping++;
5236 EXECUTE_IF_SET_IN_BITMAP (current_copies, 0, book_uid, bi)
5238 unsigned uid;
5239 bitmap_iterator bi;
5241 /* We allocate these bitmaps lazily. */
5242 if (! INSN_ORIGINATORS_BY_UID (book_uid))
5243 INSN_ORIGINATORS_BY_UID (book_uid) = BITMAP_ALLOC (NULL);
5245 bitmap_copy (INSN_ORIGINATORS_BY_UID (book_uid),
5246 current_originators);
5248 /* Transitively add all originators' originators. */
5249 EXECUTE_IF_SET_IN_BITMAP (current_originators, 0, uid, bi)
5250 if (INSN_ORIGINATORS_BY_UID (uid))
5251 bitmap_ior_into (INSN_ORIGINATORS_BY_UID (book_uid),
5252 INSN_ORIGINATORS_BY_UID (uid));
5255 return should_move;
5259 /* Debug a DFA state as an array of bytes. */
5260 static void
5261 debug_state (state_t state)
5263 unsigned char *p;
5264 unsigned int i, size = dfa_state_size;
5266 sel_print ("state (%u):", size);
5267 for (i = 0, p = (unsigned char *) state; i < size; i++)
5268 sel_print (" %d", p[i]);
5269 sel_print ("\n");
5272 /* Advance state on FENCE with INSN. Return true if INSN is
5273 an ASM, and we should advance state once more. */
5274 static bool
5275 advance_state_on_fence (fence_t fence, insn_t insn)
5277 bool asm_p;
5279 if (recog_memoized (insn) >= 0)
5281 int res;
5282 state_t temp_state = alloca (dfa_state_size);
5284 gcc_assert (!INSN_ASM_P (insn));
5285 asm_p = false;
5287 memcpy (temp_state, FENCE_STATE (fence), dfa_state_size);
5288 res = state_transition (FENCE_STATE (fence), insn);
5289 gcc_assert (res < 0);
5291 if (memcmp (temp_state, FENCE_STATE (fence), dfa_state_size))
5293 FENCE_ISSUED_INSNS (fence)++;
5295 /* We should never issue more than issue_rate insns. */
5296 if (FENCE_ISSUED_INSNS (fence) > issue_rate)
5297 gcc_unreachable ();
5300 else
5302 /* This could be an ASM insn which we'd like to schedule
5303 on the next cycle. */
5304 asm_p = INSN_ASM_P (insn);
5305 if (!FENCE_STARTS_CYCLE_P (fence) && asm_p)
5306 advance_one_cycle (fence);
5309 if (sched_verbose >= 2)
5310 debug_state (FENCE_STATE (fence));
5311 if (!DEBUG_INSN_P (insn))
5312 FENCE_STARTS_CYCLE_P (fence) = 0;
5313 FENCE_ISSUE_MORE (fence) = can_issue_more;
5314 return asm_p;
5317 /* Update FENCE on which INSN was scheduled and this INSN, too. NEED_STALL
5318 is nonzero if we need to stall after issuing INSN. */
5319 static void
5320 update_fence_and_insn (fence_t fence, insn_t insn, int need_stall)
5322 bool asm_p;
5324 /* First, reflect that something is scheduled on this fence. */
5325 asm_p = advance_state_on_fence (fence, insn);
5326 FENCE_LAST_SCHEDULED_INSN (fence) = insn;
5327 vec_safe_push (FENCE_EXECUTING_INSNS (fence), insn);
5328 if (SCHED_GROUP_P (insn))
5330 FENCE_SCHED_NEXT (fence) = INSN_SCHED_NEXT (insn);
5331 SCHED_GROUP_P (insn) = 0;
5333 else
5334 FENCE_SCHED_NEXT (fence) = NULL;
5335 if (INSN_UID (insn) < FENCE_READY_TICKS_SIZE (fence))
5336 FENCE_READY_TICKS (fence) [INSN_UID (insn)] = 0;
5338 /* Set instruction scheduling info. This will be used in bundling,
5339 pipelining, tick computations etc. */
5340 ++INSN_SCHED_TIMES (insn);
5341 EXPR_TARGET_AVAILABLE (INSN_EXPR (insn)) = true;
5342 EXPR_ORIG_SCHED_CYCLE (INSN_EXPR (insn)) = FENCE_CYCLE (fence);
5343 INSN_AFTER_STALL_P (insn) = FENCE_AFTER_STALL_P (fence);
5344 INSN_SCHED_CYCLE (insn) = FENCE_CYCLE (fence);
5346 /* This does not account for adjust_cost hooks, just add the biggest
5347 constant the hook may add to the latency. TODO: make this
5348 a target dependent constant. */
5349 INSN_READY_CYCLE (insn)
5350 = INSN_SCHED_CYCLE (insn) + (INSN_CODE (insn) < 0
5352 : maximal_insn_latency (insn) + 1);
5354 /* Change these fields last, as they're used above. */
5355 FENCE_AFTER_STALL_P (fence) = 0;
5356 if (asm_p || need_stall)
5357 advance_one_cycle (fence);
5359 /* Indicate that we've scheduled something on this fence. */
5360 FENCE_SCHEDULED_P (fence) = true;
5361 scheduled_something_on_previous_fence = true;
5363 /* Print debug information when insn's fields are updated. */
5364 if (sched_verbose >= 2)
5366 sel_print ("Scheduling insn: ");
5367 dump_insn_1 (insn, 1);
5368 sel_print ("\n");
5372 /* Update boundary BND (and, if needed, FENCE) with INSN, remove the
5373 old boundary from BNDSP, add new boundaries to BNDS_TAIL_P and
5374 return it. */
5375 static blist_t *
5376 update_boundaries (fence_t fence, bnd_t bnd, insn_t insn, blist_t *bndsp,
5377 blist_t *bnds_tailp)
5379 succ_iterator si;
5380 insn_t succ;
5382 advance_deps_context (BND_DC (bnd), insn);
5383 FOR_EACH_SUCC_1 (succ, si, insn,
5384 SUCCS_NORMAL | SUCCS_SKIP_TO_LOOP_EXITS)
5386 ilist_t ptr = ilist_copy (BND_PTR (bnd));
5388 ilist_add (&ptr, insn);
5390 if (DEBUG_INSN_P (insn) && sel_bb_end_p (insn)
5391 && is_ineligible_successor (succ, ptr))
5393 ilist_clear (&ptr);
5394 continue;
5397 if (FENCE_INSN (fence) == insn && !sel_bb_end_p (insn))
5399 if (sched_verbose >= 9)
5400 sel_print ("Updating fence insn from %i to %i\n",
5401 INSN_UID (insn), INSN_UID (succ));
5402 FENCE_INSN (fence) = succ;
5404 blist_add (bnds_tailp, succ, ptr, BND_DC (bnd));
5405 bnds_tailp = &BLIST_NEXT (*bnds_tailp);
5408 blist_remove (bndsp);
5409 return bnds_tailp;
5412 /* Schedule EXPR_VLIW on BND. Return the insn emitted. */
5413 static insn_t
5414 schedule_expr_on_boundary (bnd_t bnd, expr_t expr_vliw, int seqno)
5416 av_set_t expr_seq;
5417 expr_t c_expr = XALLOCA (expr_def);
5418 insn_t place_to_insert;
5419 insn_t insn;
5420 bool should_move;
5422 expr_seq = find_sequential_best_exprs (bnd, expr_vliw, true);
5424 /* In case of scheduling a jump skipping some other instructions,
5425 prepare CFG. After this, jump is at the boundary and can be
5426 scheduled as usual insn by MOVE_OP. */
5427 if (vinsn_cond_branch_p (EXPR_VINSN (expr_vliw)))
5429 insn = EXPR_INSN_RTX (expr_vliw);
5431 /* Speculative jumps are not handled. */
5432 if (insn != BND_TO (bnd)
5433 && !sel_insn_is_speculation_check (insn))
5434 move_cond_jump (insn, bnd);
5437 /* Find a place for C_EXPR to schedule. */
5438 place_to_insert = prepare_place_to_insert (bnd);
5439 should_move = move_exprs_to_boundary (bnd, expr_vliw, expr_seq, c_expr);
5440 clear_expr (c_expr);
5442 /* Add the instruction. The corner case to care about is when
5443 the expr_seq set has more than one expr, and we chose the one that
5444 is not equal to expr_vliw. Then expr_vliw may be insn in stream, and
5445 we can't use it. Generate the new vinsn. */
5446 if (INSN_IN_STREAM_P (EXPR_INSN_RTX (expr_vliw)))
5448 vinsn_t vinsn_new;
5450 vinsn_new = vinsn_copy (EXPR_VINSN (expr_vliw), false);
5451 change_vinsn_in_expr (expr_vliw, vinsn_new);
5452 should_move = false;
5454 if (should_move)
5455 insn = sel_move_insn (expr_vliw, seqno, place_to_insert);
5456 else
5457 insn = emit_insn_from_expr_after (expr_vliw, NULL, seqno,
5458 place_to_insert);
5460 /* Return the nops generated for preserving of data sets back
5461 into pool. */
5462 if (INSN_NOP_P (place_to_insert))
5463 return_nop_to_pool (place_to_insert, !DEBUG_INSN_P (insn));
5464 remove_temp_moveop_nops (!DEBUG_INSN_P (insn));
5466 av_set_clear (&expr_seq);
5468 /* Save the expression scheduled so to reset target availability if we'll
5469 meet it later on the same fence. */
5470 if (EXPR_WAS_RENAMED (expr_vliw))
5471 vinsn_vec_add (&vec_target_unavailable_vinsns, INSN_EXPR (insn));
5473 /* Check that the recent movement didn't destroyed loop
5474 structure. */
5475 gcc_assert (!pipelining_p
5476 || current_loop_nest == NULL
5477 || loop_latch_edge (current_loop_nest));
5478 return insn;
5481 /* Stall for N cycles on FENCE. */
5482 static void
5483 stall_for_cycles (fence_t fence, int n)
5485 int could_more;
5487 could_more = n > 1 || FENCE_ISSUED_INSNS (fence) < issue_rate;
5488 while (n--)
5489 advance_one_cycle (fence);
5490 if (could_more)
5491 FENCE_AFTER_STALL_P (fence) = 1;
5494 /* Gather a parallel group of insns at FENCE and assign their seqno
5495 to SEQNO. All scheduled insns are gathered in SCHEDULED_INSNS_TAILPP
5496 list for later recalculation of seqnos. */
5497 static void
5498 fill_insns (fence_t fence, int seqno, ilist_t **scheduled_insns_tailpp)
5500 blist_t bnds = NULL, *bnds_tailp;
5501 av_set_t av_vliw = NULL;
5502 insn_t insn = FENCE_INSN (fence);
5504 if (sched_verbose >= 2)
5505 sel_print ("Starting fill_insns for insn %d, cycle %d\n",
5506 INSN_UID (insn), FENCE_CYCLE (fence));
5508 blist_add (&bnds, insn, NULL, FENCE_DC (fence));
5509 bnds_tailp = &BLIST_NEXT (bnds);
5510 set_target_context (FENCE_TC (fence));
5511 can_issue_more = FENCE_ISSUE_MORE (fence);
5512 target_bb = INSN_BB (insn);
5514 /* Do while we can add any operation to the current group. */
5517 blist_t *bnds_tailp1, *bndsp;
5518 expr_t expr_vliw;
5519 int need_stall = false;
5520 int was_stall = 0, scheduled_insns = 0;
5521 int max_insns = pipelining_p ? issue_rate : 2 * issue_rate;
5522 int max_stall = pipelining_p ? 1 : 3;
5523 bool last_insn_was_debug = false;
5524 bool was_debug_bb_end_p = false;
5526 compute_av_set_on_boundaries (fence, bnds, &av_vliw);
5527 remove_insns_that_need_bookkeeping (fence, &av_vliw);
5528 remove_insns_for_debug (bnds, &av_vliw);
5530 /* Return early if we have nothing to schedule. */
5531 if (av_vliw == NULL)
5532 break;
5534 /* Choose the best expression and, if needed, destination register
5535 for it. */
5538 expr_vliw = find_best_expr (&av_vliw, bnds, fence, &need_stall);
5539 if (! expr_vliw && need_stall)
5541 /* All expressions required a stall. Do not recompute av sets
5542 as we'll get the same answer (modulo the insns between
5543 the fence and its boundary, which will not be available for
5544 pipelining).
5545 If we are going to stall for too long, break to recompute av
5546 sets and bring more insns for pipelining. */
5547 was_stall++;
5548 if (need_stall <= 3)
5549 stall_for_cycles (fence, need_stall);
5550 else
5552 stall_for_cycles (fence, 1);
5553 break;
5557 while (! expr_vliw && need_stall);
5559 /* Now either we've selected expr_vliw or we have nothing to schedule. */
5560 if (!expr_vliw)
5562 av_set_clear (&av_vliw);
5563 break;
5566 bndsp = &bnds;
5567 bnds_tailp1 = bnds_tailp;
5570 /* This code will be executed only once until we'd have several
5571 boundaries per fence. */
5573 bnd_t bnd = BLIST_BND (*bndsp);
5575 if (!av_set_is_in_p (BND_AV1 (bnd), EXPR_VINSN (expr_vliw)))
5577 bndsp = &BLIST_NEXT (*bndsp);
5578 continue;
5581 insn = schedule_expr_on_boundary (bnd, expr_vliw, seqno);
5582 last_insn_was_debug = DEBUG_INSN_P (insn);
5583 if (last_insn_was_debug)
5584 was_debug_bb_end_p = (insn == BND_TO (bnd) && sel_bb_end_p (insn));
5585 update_fence_and_insn (fence, insn, need_stall);
5586 bnds_tailp = update_boundaries (fence, bnd, insn, bndsp, bnds_tailp);
5588 /* Add insn to the list of scheduled on this cycle instructions. */
5589 ilist_add (*scheduled_insns_tailpp, insn);
5590 *scheduled_insns_tailpp = &ILIST_NEXT (**scheduled_insns_tailpp);
5592 while (*bndsp != *bnds_tailp1);
5594 av_set_clear (&av_vliw);
5595 if (!last_insn_was_debug)
5596 scheduled_insns++;
5598 /* We currently support information about candidate blocks only for
5599 one 'target_bb' block. Hence we can't schedule after jump insn,
5600 as this will bring two boundaries and, hence, necessity to handle
5601 information for two or more blocks concurrently. */
5602 if ((last_insn_was_debug ? was_debug_bb_end_p : sel_bb_end_p (insn))
5603 || (was_stall
5604 && (was_stall >= max_stall
5605 || scheduled_insns >= max_insns)))
5606 break;
5608 while (bnds);
5610 gcc_assert (!FENCE_BNDS (fence));
5612 /* Update boundaries of the FENCE. */
5613 while (bnds)
5615 ilist_t ptr = BND_PTR (BLIST_BND (bnds));
5617 if (ptr)
5619 insn = ILIST_INSN (ptr);
5621 if (!ilist_is_in_p (FENCE_BNDS (fence), insn))
5622 ilist_add (&FENCE_BNDS (fence), insn);
5625 blist_remove (&bnds);
5628 /* Update target context on the fence. */
5629 reset_target_context (FENCE_TC (fence), false);
5632 /* All exprs in ORIG_OPS must have the same destination register or memory.
5633 Return that destination. */
5634 static rtx
5635 get_dest_from_orig_ops (av_set_t orig_ops)
5637 rtx dest = NULL_RTX;
5638 av_set_iterator av_it;
5639 expr_t expr;
5640 bool first_p = true;
5642 FOR_EACH_EXPR (expr, av_it, orig_ops)
5644 rtx x = EXPR_LHS (expr);
5646 if (first_p)
5648 first_p = false;
5649 dest = x;
5651 else
5652 gcc_assert (dest == x
5653 || (dest != NULL_RTX && x != NULL_RTX
5654 && rtx_equal_p (dest, x)));
5657 return dest;
5660 /* Update data sets for the bookkeeping block and record those expressions
5661 which become no longer available after inserting this bookkeeping. */
5662 static void
5663 update_and_record_unavailable_insns (basic_block book_block)
5665 av_set_iterator i;
5666 av_set_t old_av_set = NULL;
5667 expr_t cur_expr;
5668 rtx_insn *bb_end = sel_bb_end (book_block);
5670 /* First, get correct liveness in the bookkeeping block. The problem is
5671 the range between the bookeeping insn and the end of block. */
5672 update_liveness_on_insn (bb_end);
5673 if (control_flow_insn_p (bb_end))
5674 update_liveness_on_insn (PREV_INSN (bb_end));
5676 /* If there's valid av_set on BOOK_BLOCK, then there might exist another
5677 fence above, where we may choose to schedule an insn which is
5678 actually blocked from moving up with the bookkeeping we create here. */
5679 if (AV_SET_VALID_P (sel_bb_head (book_block)))
5681 old_av_set = av_set_copy (BB_AV_SET (book_block));
5682 update_data_sets (sel_bb_head (book_block));
5684 /* Traverse all the expressions in the old av_set and check whether
5685 CUR_EXPR is in new AV_SET. */
5686 FOR_EACH_EXPR (cur_expr, i, old_av_set)
5688 expr_t new_expr = av_set_lookup (BB_AV_SET (book_block),
5689 EXPR_VINSN (cur_expr));
5691 if (! new_expr
5692 /* In this case, we can just turn off the E_T_A bit, but we can't
5693 represent this information with the current vector. */
5694 || EXPR_TARGET_AVAILABLE (new_expr)
5695 != EXPR_TARGET_AVAILABLE (cur_expr))
5696 /* Unfortunately, the below code could be also fired up on
5697 separable insns, e.g. when moving insns through the new
5698 speculation check as in PR 53701. */
5699 vinsn_vec_add (&vec_bookkeeping_blocked_vinsns, cur_expr);
5702 av_set_clear (&old_av_set);
5706 /* The main effect of this function is that sparams->c_expr is merged
5707 with (or copied to) lparams->c_expr_merged. If there's only one successor,
5708 we avoid merging anything by copying sparams->c_expr to lparams->c_expr_merged.
5709 lparams->c_expr_merged is copied back to sparams->c_expr after all
5710 successors has been traversed. lparams->c_expr_local is an expr allocated
5711 on stack in the caller function, and is used if there is more than one
5712 successor.
5714 SUCC is one of the SUCCS_NORMAL successors of INSN,
5715 MOVEOP_DRV_CALL_RES is the result of call code_motion_path_driver on succ,
5716 LPARAMS and STATIC_PARAMS contain the parameters described above. */
5717 static void
5718 move_op_merge_succs (insn_t insn ATTRIBUTE_UNUSED,
5719 insn_t succ ATTRIBUTE_UNUSED,
5720 int moveop_drv_call_res,
5721 cmpd_local_params_p lparams, void *static_params)
5723 moveop_static_params_p sparams = (moveop_static_params_p) static_params;
5725 /* Nothing to do, if original expr wasn't found below. */
5726 if (moveop_drv_call_res != 1)
5727 return;
5729 /* If this is a first successor. */
5730 if (!lparams->c_expr_merged)
5732 lparams->c_expr_merged = sparams->c_expr;
5733 sparams->c_expr = lparams->c_expr_local;
5735 else
5737 /* We must merge all found expressions to get reasonable
5738 EXPR_SPEC_DONE_DS for the resulting insn. If we don't
5739 do so then we can first find the expr with epsilon
5740 speculation success probability and only then with the
5741 good probability. As a result the insn will get epsilon
5742 probability and will never be scheduled because of
5743 weakness_cutoff in find_best_expr.
5745 We call merge_expr_data here instead of merge_expr
5746 because due to speculation C_EXPR and X may have the
5747 same insns with different speculation types. And as of
5748 now such insns are considered non-equal.
5750 However, EXPR_SCHED_TIMES is different -- we must get
5751 SCHED_TIMES from a real insn, not a bookkeeping copy.
5752 We force this here. Instead, we may consider merging
5753 SCHED_TIMES to the maximum instead of minimum in the
5754 below function. */
5755 int old_times = EXPR_SCHED_TIMES (lparams->c_expr_merged);
5757 merge_expr_data (lparams->c_expr_merged, sparams->c_expr, NULL);
5758 if (EXPR_SCHED_TIMES (sparams->c_expr) == 0)
5759 EXPR_SCHED_TIMES (lparams->c_expr_merged) = old_times;
5761 clear_expr (sparams->c_expr);
5765 /* Add used regs for the successor SUCC into SPARAMS->USED_REGS.
5767 SUCC is one of the SUCCS_NORMAL successors of INSN,
5768 MOVEOP_DRV_CALL_RES is the result of call code_motion_path_driver on succ or 0,
5769 if SUCC is one of SUCCS_BACK or SUCCS_OUT.
5770 STATIC_PARAMS contain USED_REGS set. */
5771 static void
5772 fur_merge_succs (insn_t insn ATTRIBUTE_UNUSED, insn_t succ,
5773 int moveop_drv_call_res,
5774 cmpd_local_params_p lparams ATTRIBUTE_UNUSED,
5775 void *static_params)
5777 regset succ_live;
5778 fur_static_params_p sparams = (fur_static_params_p) static_params;
5780 /* Here we compute live regsets only for branches that do not lie
5781 on the code motion paths. These branches correspond to value
5782 MOVEOP_DRV_CALL_RES==0 and include SUCCS_BACK and SUCCS_OUT, though
5783 for such branches code_motion_path_driver is not called. */
5784 if (moveop_drv_call_res != 0)
5785 return;
5787 /* Mark all registers that do not meet the following condition:
5788 (3) not live on the other path of any conditional branch
5789 that is passed by the operation, in case original
5790 operations are not present on both paths of the
5791 conditional branch. */
5792 succ_live = compute_live (succ);
5793 IOR_REG_SET (sparams->used_regs, succ_live);
5796 /* This function is called after the last successor. Copies LP->C_EXPR_MERGED
5797 into SP->CEXPR. */
5798 static void
5799 move_op_after_merge_succs (cmpd_local_params_p lp, void *sparams)
5801 moveop_static_params_p sp = (moveop_static_params_p) sparams;
5803 sp->c_expr = lp->c_expr_merged;
5806 /* Track bookkeeping copies created, insns scheduled, and blocks for
5807 rescheduling when INSN is found by move_op. */
5808 static void
5809 track_scheduled_insns_and_blocks (rtx_insn *insn)
5811 /* Even if this insn can be a copy that will be removed during current move_op,
5812 we still need to count it as an originator. */
5813 bitmap_set_bit (current_originators, INSN_UID (insn));
5815 if (!bitmap_clear_bit (current_copies, INSN_UID (insn)))
5817 /* Note that original block needs to be rescheduled, as we pulled an
5818 instruction out of it. */
5819 if (INSN_SCHED_TIMES (insn) > 0)
5820 bitmap_set_bit (blocks_to_reschedule, BLOCK_FOR_INSN (insn)->index);
5821 else if (INSN_UID (insn) < first_emitted_uid && !DEBUG_INSN_P (insn))
5822 num_insns_scheduled++;
5825 /* For instructions we must immediately remove insn from the
5826 stream, so subsequent update_data_sets () won't include this
5827 insn into av_set.
5828 For expr we must make insn look like "INSN_REG (insn) := c_expr". */
5829 if (INSN_UID (insn) > max_uid_before_move_op)
5830 stat_bookkeeping_copies--;
5833 /* Emit a register-register copy for INSN if needed. Return true if
5834 emitted one. PARAMS is the move_op static parameters. */
5835 static bool
5836 maybe_emit_renaming_copy (rtx_insn *insn,
5837 moveop_static_params_p params)
5839 bool insn_emitted = false;
5840 rtx cur_reg;
5842 /* Bail out early when expression can not be renamed at all. */
5843 if (!EXPR_SEPARABLE_P (params->c_expr))
5844 return false;
5846 cur_reg = expr_dest_reg (params->c_expr);
5847 gcc_assert (cur_reg && params->dest && REG_P (params->dest));
5849 /* If original operation has expr and the register chosen for
5850 that expr is not original operation's dest reg, substitute
5851 operation's right hand side with the register chosen. */
5852 if (REGNO (params->dest) != REGNO (cur_reg))
5854 insn_t reg_move_insn, reg_move_insn_rtx;
5856 reg_move_insn_rtx = create_insn_rtx_with_rhs (INSN_VINSN (insn),
5857 params->dest);
5858 reg_move_insn = sel_gen_insn_from_rtx_after (reg_move_insn_rtx,
5859 INSN_EXPR (insn),
5860 INSN_SEQNO (insn),
5861 insn);
5862 EXPR_SPEC_DONE_DS (INSN_EXPR (reg_move_insn)) = 0;
5863 replace_dest_with_reg_in_expr (params->c_expr, params->dest);
5865 insn_emitted = true;
5866 params->was_renamed = true;
5869 return insn_emitted;
5872 /* Emit a speculative check for INSN speculated as EXPR if needed.
5873 Return true if we've emitted one. PARAMS is the move_op static
5874 parameters. */
5875 static bool
5876 maybe_emit_speculative_check (rtx_insn *insn, expr_t expr,
5877 moveop_static_params_p params)
5879 bool insn_emitted = false;
5880 insn_t x;
5881 ds_t check_ds;
5883 check_ds = get_spec_check_type_for_insn (insn, expr);
5884 if (check_ds != 0)
5886 /* A speculation check should be inserted. */
5887 x = create_speculation_check (params->c_expr, check_ds, insn);
5888 insn_emitted = true;
5890 else
5892 EXPR_SPEC_DONE_DS (INSN_EXPR (insn)) = 0;
5893 x = insn;
5896 gcc_assert (EXPR_SPEC_DONE_DS (INSN_EXPR (x)) == 0
5897 && EXPR_SPEC_TO_CHECK_DS (INSN_EXPR (x)) == 0);
5898 return insn_emitted;
5901 /* Handle transformations that leave an insn in place of original
5902 insn such as renaming/speculation. Return true if one of such
5903 transformations actually happened, and we have emitted this insn. */
5904 static bool
5905 handle_emitting_transformations (rtx_insn *insn, expr_t expr,
5906 moveop_static_params_p params)
5908 bool insn_emitted = false;
5910 insn_emitted = maybe_emit_renaming_copy (insn, params);
5911 insn_emitted |= maybe_emit_speculative_check (insn, expr, params);
5913 return insn_emitted;
5916 /* If INSN is the only insn in the basic block (not counting JUMP,
5917 which may be a jump to next insn, and DEBUG_INSNs), we want to
5918 leave a NOP there till the return to fill_insns. */
5920 static bool
5921 need_nop_to_preserve_insn_bb (rtx_insn *insn)
5923 insn_t bb_head, bb_end, bb_next, in_next;
5924 basic_block bb = BLOCK_FOR_INSN (insn);
5926 bb_head = sel_bb_head (bb);
5927 bb_end = sel_bb_end (bb);
5929 if (bb_head == bb_end)
5930 return true;
5932 while (bb_head != bb_end && DEBUG_INSN_P (bb_head))
5933 bb_head = NEXT_INSN (bb_head);
5935 if (bb_head == bb_end)
5936 return true;
5938 while (bb_head != bb_end && DEBUG_INSN_P (bb_end))
5939 bb_end = PREV_INSN (bb_end);
5941 if (bb_head == bb_end)
5942 return true;
5944 bb_next = NEXT_INSN (bb_head);
5945 while (bb_next != bb_end && DEBUG_INSN_P (bb_next))
5946 bb_next = NEXT_INSN (bb_next);
5948 if (bb_next == bb_end && JUMP_P (bb_end))
5949 return true;
5951 in_next = NEXT_INSN (insn);
5952 while (DEBUG_INSN_P (in_next))
5953 in_next = NEXT_INSN (in_next);
5955 if (IN_CURRENT_FENCE_P (in_next))
5956 return true;
5958 return false;
5961 /* Remove INSN from stream. When ONLY_DISCONNECT is true, its data
5962 is not removed but reused when INSN is re-emitted. */
5963 static void
5964 remove_insn_from_stream (rtx_insn *insn, bool only_disconnect)
5966 /* If there's only one insn in the BB, make sure that a nop is
5967 inserted into it, so the basic block won't disappear when we'll
5968 delete INSN below with sel_remove_insn. It should also survive
5969 till the return to fill_insns. */
5970 if (need_nop_to_preserve_insn_bb (insn))
5972 insn_t nop = get_nop_from_pool (insn);
5973 gcc_assert (INSN_NOP_P (nop));
5974 vec_temp_moveop_nops.safe_push (nop);
5977 sel_remove_insn (insn, only_disconnect, false);
5980 /* This function is called when original expr is found.
5981 INSN - current insn traversed, EXPR - the corresponding expr found.
5982 LPARAMS is the local parameters of code modion driver, STATIC_PARAMS
5983 is static parameters of move_op. */
5984 static void
5985 move_op_orig_expr_found (insn_t insn, expr_t expr,
5986 cmpd_local_params_p lparams ATTRIBUTE_UNUSED,
5987 void *static_params)
5989 bool only_disconnect;
5990 moveop_static_params_p params = (moveop_static_params_p) static_params;
5992 copy_expr_onside (params->c_expr, INSN_EXPR (insn));
5993 track_scheduled_insns_and_blocks (insn);
5994 handle_emitting_transformations (insn, expr, params);
5995 only_disconnect = params->uid == INSN_UID (insn);
5997 /* Mark that we've disconnected an insn. */
5998 if (only_disconnect)
5999 params->uid = -1;
6000 remove_insn_from_stream (insn, only_disconnect);
6003 /* The function is called when original expr is found.
6004 INSN - current insn traversed, EXPR - the corresponding expr found,
6005 crosses_call and original_insns in STATIC_PARAMS are updated. */
6006 static void
6007 fur_orig_expr_found (insn_t insn, expr_t expr ATTRIBUTE_UNUSED,
6008 cmpd_local_params_p lparams ATTRIBUTE_UNUSED,
6009 void *static_params)
6011 fur_static_params_p params = (fur_static_params_p) static_params;
6012 regset tmp;
6014 if (CALL_P (insn))
6015 params->crosses_call = true;
6017 def_list_add (params->original_insns, insn, params->crosses_call);
6019 /* Mark the registers that do not meet the following condition:
6020 (2) not among the live registers of the point
6021 immediately following the first original operation on
6022 a given downward path, except for the original target
6023 register of the operation. */
6024 tmp = get_clear_regset_from_pool ();
6025 compute_live_below_insn (insn, tmp);
6026 AND_COMPL_REG_SET (tmp, INSN_REG_SETS (insn));
6027 AND_COMPL_REG_SET (tmp, INSN_REG_CLOBBERS (insn));
6028 IOR_REG_SET (params->used_regs, tmp);
6029 return_regset_to_pool (tmp);
6031 /* (*1) We need to add to USED_REGS registers that are read by
6032 INSN's lhs. This may lead to choosing wrong src register.
6033 E.g. (scheduling const expr enabled):
6035 429: ax=0x0 <- Can't use AX for this expr (0x0)
6036 433: dx=[bp-0x18]
6037 427: [ax+dx+0x1]=ax
6038 REG_DEAD: ax
6039 168: di=dx
6040 REG_DEAD: dx
6042 /* FIXME: see comment above and enable MEM_P
6043 in vinsn_separable_p. */
6044 gcc_assert (!VINSN_SEPARABLE_P (INSN_VINSN (insn))
6045 || !MEM_P (INSN_LHS (insn)));
6048 /* This function is called on the ascending pass, before returning from
6049 current basic block. */
6050 static void
6051 move_op_at_first_insn (insn_t insn, cmpd_local_params_p lparams,
6052 void *static_params)
6054 moveop_static_params_p sparams = (moveop_static_params_p) static_params;
6055 basic_block book_block = NULL;
6057 /* When we have removed the boundary insn for scheduling, which also
6058 happened to be the end insn in its bb, we don't need to update sets. */
6059 if (!lparams->removed_last_insn
6060 && lparams->e1
6061 && sel_bb_head_p (insn))
6063 /* We should generate bookkeeping code only if we are not at the
6064 top level of the move_op. */
6065 if (sel_num_cfg_preds_gt_1 (insn))
6066 book_block = generate_bookkeeping_insn (sparams->c_expr,
6067 lparams->e1, lparams->e2);
6068 /* Update data sets for the current insn. */
6069 update_data_sets (insn);
6072 /* If bookkeeping code was inserted, we need to update av sets of basic
6073 block that received bookkeeping. After generation of bookkeeping insn,
6074 bookkeeping block does not contain valid av set because we are not following
6075 the original algorithm in every detail with regards to e.g. renaming
6076 simple reg-reg copies. Consider example:
6078 bookkeeping block scheduling fence
6080 \ join /
6081 ----------
6083 ----------
6086 r1 := r2 r1 := r3
6088 We try to schedule insn "r1 := r3" on the current
6089 scheduling fence. Also, note that av set of bookkeeping block
6090 contain both insns "r1 := r2" and "r1 := r3". When the insn has
6091 been scheduled, the CFG is as follows:
6093 r1 := r3 r1 := r3
6094 bookkeeping block scheduling fence
6096 \ join /
6097 ----------
6099 ----------
6102 r1 := r2
6104 Here, insn "r1 := r3" was scheduled at the current scheduling point
6105 and bookkeeping code was generated at the bookeeping block. This
6106 way insn "r1 := r2" is no longer available as a whole instruction
6107 (but only as expr) ahead of insn "r1 := r3" in bookkeeping block.
6108 This situation is handled by calling update_data_sets.
6110 Since update_data_sets is called only on the bookkeeping block, and
6111 it also may have predecessors with av_sets, containing instructions that
6112 are no longer available, we save all such expressions that become
6113 unavailable during data sets update on the bookkeeping block in
6114 VEC_BOOKKEEPING_BLOCKED_VINSNS. Later we avoid selecting such
6115 expressions for scheduling. This allows us to avoid recomputation of
6116 av_sets outside the code motion path. */
6118 if (book_block)
6119 update_and_record_unavailable_insns (book_block);
6121 /* If INSN was previously marked for deletion, it's time to do it. */
6122 if (lparams->removed_last_insn)
6123 insn = PREV_INSN (insn);
6125 /* Do not tidy control flow at the topmost moveop, as we can erroneously
6126 kill a block with a single nop in which the insn should be emitted. */
6127 if (lparams->e1)
6128 tidy_control_flow (BLOCK_FOR_INSN (insn), true);
6131 /* This function is called on the ascending pass, before returning from the
6132 current basic block. */
6133 static void
6134 fur_at_first_insn (insn_t insn,
6135 cmpd_local_params_p lparams ATTRIBUTE_UNUSED,
6136 void *static_params ATTRIBUTE_UNUSED)
6138 gcc_assert (!sel_bb_head_p (insn) || AV_SET_VALID_P (insn)
6139 || AV_LEVEL (insn) == -1);
6142 /* Called on the backward stage of recursion to call moveup_expr for insn
6143 and sparams->c_expr. */
6144 static void
6145 move_op_ascend (insn_t insn, void *static_params)
6147 enum MOVEUP_EXPR_CODE res;
6148 moveop_static_params_p sparams = (moveop_static_params_p) static_params;
6150 if (! INSN_NOP_P (insn))
6152 res = moveup_expr_cached (sparams->c_expr, insn, false);
6153 gcc_assert (res != MOVEUP_EXPR_NULL);
6156 /* Update liveness for this insn as it was invalidated. */
6157 update_liveness_on_insn (insn);
6160 /* This function is called on enter to the basic block.
6161 Returns TRUE if this block already have been visited and
6162 code_motion_path_driver should return 1, FALSE otherwise. */
6163 static int
6164 fur_on_enter (insn_t insn ATTRIBUTE_UNUSED, cmpd_local_params_p local_params,
6165 void *static_params, bool visited_p)
6167 fur_static_params_p sparams = (fur_static_params_p) static_params;
6169 if (visited_p)
6171 /* If we have found something below this block, there should be at
6172 least one insn in ORIGINAL_INSNS. */
6173 gcc_assert (*sparams->original_insns);
6175 /* Adjust CROSSES_CALL, since we may have come to this block along
6176 different path. */
6177 DEF_LIST_DEF (*sparams->original_insns)->crosses_call
6178 |= sparams->crosses_call;
6180 else
6181 local_params->old_original_insns = *sparams->original_insns;
6183 return 1;
6186 /* Same as above but for move_op. */
6187 static int
6188 move_op_on_enter (insn_t insn ATTRIBUTE_UNUSED,
6189 cmpd_local_params_p local_params ATTRIBUTE_UNUSED,
6190 void *static_params ATTRIBUTE_UNUSED, bool visited_p)
6192 if (visited_p)
6193 return -1;
6194 return 1;
6197 /* This function is called while descending current basic block if current
6198 insn is not the original EXPR we're searching for.
6200 Return value: FALSE, if code_motion_path_driver should perform a local
6201 cleanup and return 0 itself;
6202 TRUE, if code_motion_path_driver should continue. */
6203 static bool
6204 move_op_orig_expr_not_found (insn_t insn, av_set_t orig_ops ATTRIBUTE_UNUSED,
6205 void *static_params)
6207 moveop_static_params_p sparams = (moveop_static_params_p) static_params;
6209 sparams->failed_insn = insn;
6211 /* If we're scheduling separate expr, in order to generate correct code
6212 we need to stop the search at bookkeeping code generated with the
6213 same destination register or memory. */
6214 if (lhs_of_insn_equals_to_dest_p (insn, sparams->dest))
6215 return false;
6216 return true;
6219 /* This function is called while descending current basic block if current
6220 insn is not the original EXPR we're searching for.
6222 Return value: TRUE (code_motion_path_driver should continue). */
6223 static bool
6224 fur_orig_expr_not_found (insn_t insn, av_set_t orig_ops, void *static_params)
6226 bool mutexed;
6227 expr_t r;
6228 av_set_iterator avi;
6229 fur_static_params_p sparams = (fur_static_params_p) static_params;
6231 if (CALL_P (insn))
6232 sparams->crosses_call = true;
6233 else if (DEBUG_INSN_P (insn))
6234 return true;
6236 /* If current insn we are looking at cannot be executed together
6237 with original insn, then we can skip it safely.
6239 Example: ORIG_OPS = { (p6) r14 = sign_extend (r15); }
6240 INSN = (!p6) r14 = r14 + 1;
6242 Here we can schedule ORIG_OP with lhs = r14, though only
6243 looking at the set of used and set registers of INSN we must
6244 forbid it. So, add set/used in INSN registers to the
6245 untouchable set only if there is an insn in ORIG_OPS that can
6246 affect INSN. */
6247 mutexed = true;
6248 FOR_EACH_EXPR (r, avi, orig_ops)
6249 if (!sched_insns_conditions_mutex_p (insn, EXPR_INSN_RTX (r)))
6251 mutexed = false;
6252 break;
6255 /* Mark all registers that do not meet the following condition:
6256 (1) Not set or read on any path from xi to an instance of the
6257 original operation. */
6258 if (!mutexed)
6260 IOR_REG_SET (sparams->used_regs, INSN_REG_SETS (insn));
6261 IOR_REG_SET (sparams->used_regs, INSN_REG_USES (insn));
6262 IOR_REG_SET (sparams->used_regs, INSN_REG_CLOBBERS (insn));
6265 return true;
6268 /* Hooks and data to perform move_op operations with code_motion_path_driver. */
6269 struct code_motion_path_driver_info_def move_op_hooks = {
6270 move_op_on_enter,
6271 move_op_orig_expr_found,
6272 move_op_orig_expr_not_found,
6273 move_op_merge_succs,
6274 move_op_after_merge_succs,
6275 move_op_ascend,
6276 move_op_at_first_insn,
6277 SUCCS_NORMAL,
6278 "move_op"
6281 /* Hooks and data to perform find_used_regs operations
6282 with code_motion_path_driver. */
6283 struct code_motion_path_driver_info_def fur_hooks = {
6284 fur_on_enter,
6285 fur_orig_expr_found,
6286 fur_orig_expr_not_found,
6287 fur_merge_succs,
6288 NULL, /* fur_after_merge_succs */
6289 NULL, /* fur_ascend */
6290 fur_at_first_insn,
6291 SUCCS_ALL,
6292 "find_used_regs"
6295 /* Traverse all successors of INSN. For each successor that is SUCCS_NORMAL
6296 code_motion_path_driver is called recursively. Original operation
6297 was found at least on one path that is starting with one of INSN's
6298 successors (this fact is asserted). ORIG_OPS is expressions we're looking
6299 for, PATH is the path we've traversed, STATIC_PARAMS is the parameters
6300 of either move_op or find_used_regs depending on the caller.
6302 Return 0 if we haven't found expression, 1 if we found it, -1 if we don't
6303 know for sure at this point. */
6304 static int
6305 code_motion_process_successors (insn_t insn, av_set_t orig_ops,
6306 ilist_t path, void *static_params)
6308 int res = 0;
6309 succ_iterator succ_i;
6310 insn_t succ;
6311 basic_block bb;
6312 int old_index;
6313 unsigned old_succs;
6315 struct cmpd_local_params lparams;
6316 expr_def _x;
6318 lparams.c_expr_local = &_x;
6319 lparams.c_expr_merged = NULL;
6321 /* We need to process only NORMAL succs for move_op, and collect live
6322 registers from ALL branches (including those leading out of the
6323 region) for find_used_regs.
6325 In move_op, there can be a case when insn's bb number has changed
6326 due to created bookkeeping. This happens very rare, as we need to
6327 move expression from the beginning to the end of the same block.
6328 Rescan successors in this case. */
6330 rescan:
6331 bb = BLOCK_FOR_INSN (insn);
6332 old_index = bb->index;
6333 old_succs = EDGE_COUNT (bb->succs);
6335 FOR_EACH_SUCC_1 (succ, succ_i, insn, code_motion_path_driver_info->succ_flags)
6337 int b;
6339 lparams.e1 = succ_i.e1;
6340 lparams.e2 = succ_i.e2;
6342 /* Go deep into recursion only for NORMAL edges (non-backedges within the
6343 current region). */
6344 if (succ_i.current_flags == SUCCS_NORMAL)
6345 b = code_motion_path_driver (succ, orig_ops, path, &lparams,
6346 static_params);
6347 else
6348 b = 0;
6350 /* Merge c_expres found or unify live register sets from different
6351 successors. */
6352 code_motion_path_driver_info->merge_succs (insn, succ, b, &lparams,
6353 static_params);
6354 if (b == 1)
6355 res = b;
6356 else if (b == -1 && res != 1)
6357 res = b;
6359 /* We have simplified the control flow below this point. In this case,
6360 the iterator becomes invalid. We need to try again.
6361 If we have removed the insn itself, it could be only an
6362 unconditional jump. Thus, do not rescan but break immediately --
6363 we have already visited the only successor block. */
6364 if (!BLOCK_FOR_INSN (insn))
6366 if (sched_verbose >= 6)
6367 sel_print ("Not doing rescan: already visited the only successor"
6368 " of block %d\n", old_index);
6369 break;
6371 if (BLOCK_FOR_INSN (insn)->index != old_index
6372 || EDGE_COUNT (bb->succs) != old_succs)
6374 if (sched_verbose >= 6)
6375 sel_print ("Rescan: CFG was simplified below insn %d, block %d\n",
6376 INSN_UID (insn), BLOCK_FOR_INSN (insn)->index);
6377 insn = sel_bb_end (BLOCK_FOR_INSN (insn));
6378 goto rescan;
6382 /* Here, RES==1 if original expr was found at least for one of the
6383 successors. After the loop, RES may happen to have zero value
6384 only if at some point the expr searched is present in av_set, but is
6385 not found below. In most cases, this situation is an error.
6386 The exception is when the original operation is blocked by
6387 bookkeeping generated for another fence or for another path in current
6388 move_op. */
6389 gcc_checking_assert (res == 1
6390 || (res == 0
6391 && av_set_could_be_blocked_by_bookkeeping_p (orig_ops, static_params))
6392 || res == -1);
6394 /* Merge data, clean up, etc. */
6395 if (res != -1 && code_motion_path_driver_info->after_merge_succs)
6396 code_motion_path_driver_info->after_merge_succs (&lparams, static_params);
6398 return res;
6402 /* Perform a cleanup when the driver is about to terminate. ORIG_OPS_P
6403 is the pointer to the av set with expressions we were looking for,
6404 PATH_P is the pointer to the traversed path. */
6405 static inline void
6406 code_motion_path_driver_cleanup (av_set_t *orig_ops_p, ilist_t *path_p)
6408 ilist_remove (path_p);
6409 av_set_clear (orig_ops_p);
6412 /* The driver function that implements move_op or find_used_regs
6413 functionality dependent whether code_motion_path_driver_INFO is set to
6414 &MOVE_OP_HOOKS or &FUR_HOOKS. This function implements the common parts
6415 of code (CFG traversal etc) that are shared among both functions. INSN
6416 is the insn we're starting the search from, ORIG_OPS are the expressions
6417 we're searching for, PATH is traversed path, LOCAL_PARAMS_IN are local
6418 parameters of the driver, and STATIC_PARAMS are static parameters of
6419 the caller.
6421 Returns whether original instructions were found. Note that top-level
6422 code_motion_path_driver always returns true. */
6423 static int
6424 code_motion_path_driver (insn_t insn, av_set_t orig_ops, ilist_t path,
6425 cmpd_local_params_p local_params_in,
6426 void *static_params)
6428 expr_t expr = NULL;
6429 basic_block bb = BLOCK_FOR_INSN (insn);
6430 insn_t first_insn, bb_tail, before_first;
6431 bool removed_last_insn = false;
6433 if (sched_verbose >= 6)
6435 sel_print ("%s (", code_motion_path_driver_info->routine_name);
6436 dump_insn (insn);
6437 sel_print (",");
6438 dump_av_set (orig_ops);
6439 sel_print (")\n");
6442 gcc_assert (orig_ops);
6444 /* If no original operations exist below this insn, return immediately. */
6445 if (is_ineligible_successor (insn, path))
6447 if (sched_verbose >= 6)
6448 sel_print ("Insn %d is ineligible successor\n", INSN_UID (insn));
6449 return false;
6452 /* The block can have invalid av set, in which case it was created earlier
6453 during move_op. Return immediately. */
6454 if (sel_bb_head_p (insn))
6456 if (! AV_SET_VALID_P (insn))
6458 if (sched_verbose >= 6)
6459 sel_print ("Returned from block %d as it had invalid av set\n",
6460 bb->index);
6461 return false;
6464 if (bitmap_bit_p (code_motion_visited_blocks, bb->index))
6466 /* We have already found an original operation on this branch, do not
6467 go any further and just return TRUE here. If we don't stop here,
6468 function can have exponential behavior even on the small code
6469 with many different paths (e.g. with data speculation and
6470 recovery blocks). */
6471 if (sched_verbose >= 6)
6472 sel_print ("Block %d already visited in this traversal\n", bb->index);
6473 if (code_motion_path_driver_info->on_enter)
6474 return code_motion_path_driver_info->on_enter (insn,
6475 local_params_in,
6476 static_params,
6477 true);
6481 if (code_motion_path_driver_info->on_enter)
6482 code_motion_path_driver_info->on_enter (insn, local_params_in,
6483 static_params, false);
6484 orig_ops = av_set_copy (orig_ops);
6486 /* Filter the orig_ops set. */
6487 if (AV_SET_VALID_P (insn))
6488 av_set_code_motion_filter (&orig_ops, AV_SET (insn));
6490 /* If no more original ops, return immediately. */
6491 if (!orig_ops)
6493 if (sched_verbose >= 6)
6494 sel_print ("No intersection with av set of block %d\n", bb->index);
6495 return false;
6498 /* For non-speculative insns we have to leave only one form of the
6499 original operation, because if we don't, we may end up with
6500 different C_EXPRes and, consequently, with bookkeepings for different
6501 expression forms along the same code motion path. That may lead to
6502 generation of incorrect code. So for each code motion we stick to
6503 the single form of the instruction, except for speculative insns
6504 which we need to keep in different forms with all speculation
6505 types. */
6506 av_set_leave_one_nonspec (&orig_ops);
6508 /* It is not possible that all ORIG_OPS are filtered out. */
6509 gcc_assert (orig_ops);
6511 /* It is enough to place only heads and tails of visited basic blocks into
6512 the PATH. */
6513 ilist_add (&path, insn);
6514 first_insn = insn;
6515 bb_tail = sel_bb_end (bb);
6517 /* Descend the basic block in search of the original expr; this part
6518 corresponds to the part of the original move_op procedure executed
6519 before the recursive call. */
6520 for (;;)
6522 /* Look at the insn and decide if it could be an ancestor of currently
6523 scheduling operation. If it is so, then the insn "dest = op" could
6524 either be replaced with "dest = reg", because REG now holds the result
6525 of OP, or just removed, if we've scheduled the insn as a whole.
6527 If this insn doesn't contain currently scheduling OP, then proceed
6528 with searching and look at its successors. Operations we're searching
6529 for could have changed when moving up through this insn via
6530 substituting. In this case, perform unsubstitution on them first.
6532 When traversing the DAG below this insn is finished, insert
6533 bookkeeping code, if the insn is a joint point, and remove
6534 leftovers. */
6536 expr = av_set_lookup (orig_ops, INSN_VINSN (insn));
6537 if (expr)
6539 insn_t last_insn = PREV_INSN (insn);
6541 /* We have found the original operation. */
6542 if (sched_verbose >= 6)
6543 sel_print ("Found original operation at insn %d\n", INSN_UID (insn));
6545 code_motion_path_driver_info->orig_expr_found
6546 (insn, expr, local_params_in, static_params);
6548 /* Step back, so on the way back we'll start traversing from the
6549 previous insn (or we'll see that it's bb_note and skip that
6550 loop). */
6551 if (insn == first_insn)
6553 first_insn = NEXT_INSN (last_insn);
6554 removed_last_insn = sel_bb_end_p (last_insn);
6556 insn = last_insn;
6557 break;
6559 else
6561 /* We haven't found the original expr, continue descending the basic
6562 block. */
6563 if (code_motion_path_driver_info->orig_expr_not_found
6564 (insn, orig_ops, static_params))
6566 /* Av set ops could have been changed when moving through this
6567 insn. To find them below it, we have to un-substitute them. */
6568 undo_transformations (&orig_ops, insn);
6570 else
6572 /* Clean up and return, if the hook tells us to do so. It may
6573 happen if we've encountered the previously created
6574 bookkeeping. */
6575 code_motion_path_driver_cleanup (&orig_ops, &path);
6576 return -1;
6579 gcc_assert (orig_ops);
6582 /* Stop at insn if we got to the end of BB. */
6583 if (insn == bb_tail)
6584 break;
6586 insn = NEXT_INSN (insn);
6589 /* Here INSN either points to the insn before the original insn (may be
6590 bb_note, if original insn was a bb_head) or to the bb_end. */
6591 if (!expr)
6593 int res;
6594 rtx_insn *last_insn = PREV_INSN (insn);
6595 bool added_to_path;
6597 gcc_assert (insn == sel_bb_end (bb));
6599 /* Add bb tail to PATH (but it doesn't make any sense if it's a bb_head -
6600 it's already in PATH then). */
6601 if (insn != first_insn)
6603 ilist_add (&path, insn);
6604 added_to_path = true;
6606 else
6607 added_to_path = false;
6609 /* Process_successors should be able to find at least one
6610 successor for which code_motion_path_driver returns TRUE. */
6611 res = code_motion_process_successors (insn, orig_ops,
6612 path, static_params);
6614 /* Jump in the end of basic block could have been removed or replaced
6615 during code_motion_process_successors, so recompute insn as the
6616 last insn in bb. */
6617 if (NEXT_INSN (last_insn) != insn)
6619 insn = sel_bb_end (bb);
6620 first_insn = sel_bb_head (bb);
6623 /* Remove bb tail from path. */
6624 if (added_to_path)
6625 ilist_remove (&path);
6627 if (res != 1)
6629 /* This is the case when one of the original expr is no longer available
6630 due to bookkeeping created on this branch with the same register.
6631 In the original algorithm, which doesn't have update_data_sets call
6632 on a bookkeeping block, it would simply result in returning
6633 FALSE when we've encountered a previously generated bookkeeping
6634 insn in moveop_orig_expr_not_found. */
6635 code_motion_path_driver_cleanup (&orig_ops, &path);
6636 return res;
6640 /* Don't need it any more. */
6641 av_set_clear (&orig_ops);
6643 /* Backward pass: now, when we have C_EXPR computed, we'll drag it to
6644 the beginning of the basic block. */
6645 before_first = PREV_INSN (first_insn);
6646 while (insn != before_first)
6648 if (code_motion_path_driver_info->ascend)
6649 code_motion_path_driver_info->ascend (insn, static_params);
6651 insn = PREV_INSN (insn);
6654 /* Now we're at the bb head. */
6655 insn = first_insn;
6656 ilist_remove (&path);
6657 local_params_in->removed_last_insn = removed_last_insn;
6658 code_motion_path_driver_info->at_first_insn (insn, local_params_in, static_params);
6660 /* This should be the very last operation as at bb head we could change
6661 the numbering by creating bookkeeping blocks. */
6662 if (removed_last_insn)
6663 insn = PREV_INSN (insn);
6665 /* If we have simplified the control flow and removed the first jump insn,
6666 there's no point in marking this block in the visited blocks bitmap. */
6667 if (BLOCK_FOR_INSN (insn))
6668 bitmap_set_bit (code_motion_visited_blocks, BLOCK_FOR_INSN (insn)->index);
6669 return true;
6672 /* Move up the operations from ORIG_OPS set traversing the dag starting
6673 from INSN. PATH represents the edges traversed so far.
6674 DEST is the register chosen for scheduling the current expr. Insert
6675 bookkeeping code in the join points. EXPR_VLIW is the chosen expression,
6676 C_EXPR is how it looks like at the given cfg point.
6677 Set *SHOULD_MOVE to indicate whether we have only disconnected
6678 one of the insns found.
6680 Returns whether original instructions were found, which is asserted
6681 to be true in the caller. */
6682 static bool
6683 move_op (insn_t insn, av_set_t orig_ops, expr_t expr_vliw,
6684 rtx dest, expr_t c_expr, bool *should_move)
6686 struct moveop_static_params sparams;
6687 struct cmpd_local_params lparams;
6688 int res;
6690 /* Init params for code_motion_path_driver. */
6691 sparams.dest = dest;
6692 sparams.c_expr = c_expr;
6693 sparams.uid = INSN_UID (EXPR_INSN_RTX (expr_vliw));
6694 sparams.failed_insn = NULL;
6695 sparams.was_renamed = false;
6696 lparams.e1 = NULL;
6698 /* We haven't visited any blocks yet. */
6699 bitmap_clear (code_motion_visited_blocks);
6701 /* Set appropriate hooks and data. */
6702 code_motion_path_driver_info = &move_op_hooks;
6703 res = code_motion_path_driver (insn, orig_ops, NULL, &lparams, &sparams);
6705 gcc_assert (res != -1);
6707 if (sparams.was_renamed)
6708 EXPR_WAS_RENAMED (expr_vliw) = true;
6710 *should_move = (sparams.uid == -1);
6712 return res;
6716 /* Functions that work with regions. */
6718 /* Current number of seqno used in init_seqno and init_seqno_1. */
6719 static int cur_seqno;
6721 /* A helper for init_seqno. Traverse the region starting from BB and
6722 compute seqnos for visited insns, marking visited bbs in VISITED_BBS.
6723 Clear visited blocks from BLOCKS_TO_RESCHEDULE. */
6724 static void
6725 init_seqno_1 (basic_block bb, sbitmap visited_bbs, bitmap blocks_to_reschedule)
6727 int bbi = BLOCK_TO_BB (bb->index);
6728 insn_t insn;
6729 insn_t succ_insn;
6730 succ_iterator si;
6732 rtx_note *note = bb_note (bb);
6733 bitmap_set_bit (visited_bbs, bbi);
6734 if (blocks_to_reschedule)
6735 bitmap_clear_bit (blocks_to_reschedule, bb->index);
6737 FOR_EACH_SUCC_1 (succ_insn, si, BB_END (bb),
6738 SUCCS_NORMAL | SUCCS_SKIP_TO_LOOP_EXITS)
6740 basic_block succ = BLOCK_FOR_INSN (succ_insn);
6741 int succ_bbi = BLOCK_TO_BB (succ->index);
6743 gcc_assert (in_current_region_p (succ));
6745 if (!bitmap_bit_p (visited_bbs, succ_bbi))
6747 gcc_assert (succ_bbi > bbi);
6749 init_seqno_1 (succ, visited_bbs, blocks_to_reschedule);
6751 else if (blocks_to_reschedule)
6752 bitmap_set_bit (forced_ebb_heads, succ->index);
6755 for (insn = BB_END (bb); insn != note; insn = PREV_INSN (insn))
6756 INSN_SEQNO (insn) = cur_seqno--;
6759 /* Initialize seqnos for the current region. BLOCKS_TO_RESCHEDULE contains
6760 blocks on which we're rescheduling when pipelining, FROM is the block where
6761 traversing region begins (it may not be the head of the region when
6762 pipelining, but the head of the loop instead).
6764 Returns the maximal seqno found. */
6765 static int
6766 init_seqno (bitmap blocks_to_reschedule, basic_block from)
6768 bitmap_iterator bi;
6769 unsigned bbi;
6771 auto_sbitmap visited_bbs (current_nr_blocks);
6773 if (blocks_to_reschedule)
6775 bitmap_ones (visited_bbs);
6776 EXECUTE_IF_SET_IN_BITMAP (blocks_to_reschedule, 0, bbi, bi)
6778 gcc_assert (BLOCK_TO_BB (bbi) < current_nr_blocks);
6779 bitmap_clear_bit (visited_bbs, BLOCK_TO_BB (bbi));
6782 else
6784 bitmap_clear (visited_bbs);
6785 from = EBB_FIRST_BB (0);
6788 cur_seqno = sched_max_luid - 1;
6789 init_seqno_1 (from, visited_bbs, blocks_to_reschedule);
6791 /* cur_seqno may be positive if the number of instructions is less than
6792 sched_max_luid - 1 (when rescheduling or if some instructions have been
6793 removed by the call to purge_empty_blocks in sel_sched_region_1). */
6794 gcc_assert (cur_seqno >= 0);
6796 return sched_max_luid - 1;
6799 /* Initialize scheduling parameters for current region. */
6800 static void
6801 sel_setup_region_sched_flags (void)
6803 enable_schedule_as_rhs_p = 1;
6804 bookkeeping_p = 1;
6805 pipelining_p = (bookkeeping_p
6806 && (flag_sel_sched_pipelining != 0)
6807 && current_loop_nest != NULL
6808 && loop_has_exit_edges (current_loop_nest));
6809 max_insns_to_rename = PARAM_VALUE (PARAM_SELSCHED_INSNS_TO_RENAME);
6810 max_ws = MAX_WS;
6813 /* Return true if all basic blocks of current region are empty. */
6814 static bool
6815 current_region_empty_p (void)
6817 int i;
6818 for (i = 0; i < current_nr_blocks; i++)
6819 if (! sel_bb_empty_p (BASIC_BLOCK_FOR_FN (cfun, BB_TO_BLOCK (i))))
6820 return false;
6822 return true;
6825 /* Prepare and verify loop nest for pipelining. */
6826 static void
6827 setup_current_loop_nest (int rgn, bb_vec_t *bbs)
6829 current_loop_nest = get_loop_nest_for_rgn (rgn);
6831 if (!current_loop_nest)
6832 return;
6834 /* If this loop has any saved loop preheaders from nested loops,
6835 add these basic blocks to the current region. */
6836 sel_add_loop_preheaders (bbs);
6838 /* Check that we're starting with a valid information. */
6839 gcc_assert (loop_latch_edge (current_loop_nest));
6840 gcc_assert (LOOP_MARKED_FOR_PIPELINING_P (current_loop_nest));
6843 /* Compute instruction priorities for current region. */
6844 static void
6845 sel_compute_priorities (int rgn)
6847 sched_rgn_compute_dependencies (rgn);
6849 /* Compute insn priorities in haifa style. Then free haifa style
6850 dependencies that we've calculated for this. */
6851 compute_priorities ();
6853 if (sched_verbose >= 5)
6854 debug_rgn_dependencies (0);
6856 free_rgn_deps ();
6859 /* Init scheduling data for RGN. Returns true when this region should not
6860 be scheduled. */
6861 static bool
6862 sel_region_init (int rgn)
6864 int i;
6865 bb_vec_t bbs;
6867 rgn_setup_region (rgn);
6869 /* Even if sched_is_disabled_for_current_region_p() is true, we still
6870 do region initialization here so the region can be bundled correctly,
6871 but we'll skip the scheduling in sel_sched_region (). */
6872 if (current_region_empty_p ())
6873 return true;
6875 bbs.create (current_nr_blocks);
6877 for (i = 0; i < current_nr_blocks; i++)
6878 bbs.quick_push (BASIC_BLOCK_FOR_FN (cfun, BB_TO_BLOCK (i)));
6880 sel_init_bbs (bbs);
6882 if (flag_sel_sched_pipelining)
6883 setup_current_loop_nest (rgn, &bbs);
6885 sel_setup_region_sched_flags ();
6887 /* Initialize luids and dependence analysis which both sel-sched and haifa
6888 need. */
6889 sched_init_luids (bbs);
6890 sched_deps_init (false);
6892 /* Initialize haifa data. */
6893 rgn_setup_sched_infos ();
6894 sel_set_sched_flags ();
6895 haifa_init_h_i_d (bbs);
6897 sel_compute_priorities (rgn);
6898 init_deps_global ();
6900 /* Main initialization. */
6901 sel_setup_sched_infos ();
6902 sel_init_global_and_expr (bbs);
6904 bbs.release ();
6906 blocks_to_reschedule = BITMAP_ALLOC (NULL);
6908 /* Init correct liveness sets on each instruction of a single-block loop.
6909 This is the only situation when we can't update liveness when calling
6910 compute_live for the first insn of the loop. */
6911 if (current_loop_nest)
6913 int header =
6914 (sel_is_loop_preheader_p (BASIC_BLOCK_FOR_FN (cfun, BB_TO_BLOCK (0)))
6916 : 0);
6918 if (current_nr_blocks == header + 1)
6919 update_liveness_on_insn
6920 (sel_bb_head (BASIC_BLOCK_FOR_FN (cfun, BB_TO_BLOCK (header))));
6923 /* Set hooks so that no newly generated insn will go out unnoticed. */
6924 sel_register_cfg_hooks ();
6926 /* !!! We call target.sched.init () for the whole region, but we invoke
6927 targetm.sched.finish () for every ebb. */
6928 if (targetm.sched.init)
6929 /* None of the arguments are actually used in any target. */
6930 targetm.sched.init (sched_dump, sched_verbose, -1);
6932 first_emitted_uid = get_max_uid () + 1;
6933 preheader_removed = false;
6935 /* Reset register allocation ticks array. */
6936 memset (reg_rename_tick, 0, sizeof reg_rename_tick);
6937 reg_rename_this_tick = 0;
6939 bitmap_initialize (forced_ebb_heads, 0);
6940 bitmap_clear (forced_ebb_heads);
6942 setup_nop_vinsn ();
6943 current_copies = BITMAP_ALLOC (NULL);
6944 current_originators = BITMAP_ALLOC (NULL);
6945 code_motion_visited_blocks = BITMAP_ALLOC (NULL);
6947 return false;
6950 /* Simplify insns after the scheduling. */
6951 static void
6952 simplify_changed_insns (void)
6954 int i;
6956 for (i = 0; i < current_nr_blocks; i++)
6958 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, BB_TO_BLOCK (i));
6959 rtx_insn *insn;
6961 FOR_BB_INSNS (bb, insn)
6962 if (INSN_P (insn))
6964 expr_t expr = INSN_EXPR (insn);
6966 if (EXPR_WAS_SUBSTITUTED (expr))
6967 validate_simplify_insn (insn);
6972 /* Find boundaries of the EBB starting from basic block BB, marking blocks of
6973 this EBB in SCHEDULED_BLOCKS and appropriately filling in HEAD, TAIL,
6974 PREV_HEAD, and NEXT_TAIL fields of CURRENT_SCHED_INFO structure. */
6975 static void
6976 find_ebb_boundaries (basic_block bb, bitmap scheduled_blocks)
6978 rtx_insn *head, *tail;
6979 basic_block bb1 = bb;
6980 if (sched_verbose >= 2)
6981 sel_print ("Finishing schedule in bbs: ");
6985 bitmap_set_bit (scheduled_blocks, BLOCK_TO_BB (bb1->index));
6987 if (sched_verbose >= 2)
6988 sel_print ("%d; ", bb1->index);
6990 while (!bb_ends_ebb_p (bb1) && (bb1 = bb_next_bb (bb1)));
6992 if (sched_verbose >= 2)
6993 sel_print ("\n");
6995 get_ebb_head_tail (bb, bb1, &head, &tail);
6997 current_sched_info->head = head;
6998 current_sched_info->tail = tail;
6999 current_sched_info->prev_head = PREV_INSN (head);
7000 current_sched_info->next_tail = NEXT_INSN (tail);
7003 /* Regenerate INSN_SCHED_CYCLEs for insns of current EBB. */
7004 static void
7005 reset_sched_cycles_in_current_ebb (void)
7007 int last_clock = 0;
7008 int haifa_last_clock = -1;
7009 int haifa_clock = 0;
7010 int issued_insns = 0;
7011 insn_t insn;
7013 if (targetm.sched.init)
7015 /* None of the arguments are actually used in any target.
7016 NB: We should have md_reset () hook for cases like this. */
7017 targetm.sched.init (sched_dump, sched_verbose, -1);
7020 state_reset (curr_state);
7021 advance_state (curr_state);
7023 for (insn = current_sched_info->head;
7024 insn != current_sched_info->next_tail;
7025 insn = NEXT_INSN (insn))
7027 int cost, haifa_cost;
7028 int sort_p;
7029 bool asm_p, real_insn, after_stall, all_issued;
7030 int clock;
7032 if (!INSN_P (insn))
7033 continue;
7035 asm_p = false;
7036 real_insn = recog_memoized (insn) >= 0;
7037 clock = INSN_SCHED_CYCLE (insn);
7039 cost = clock - last_clock;
7041 /* Initialize HAIFA_COST. */
7042 if (! real_insn)
7044 asm_p = INSN_ASM_P (insn);
7046 if (asm_p)
7047 /* This is asm insn which *had* to be scheduled first
7048 on the cycle. */
7049 haifa_cost = 1;
7050 else
7051 /* This is a use/clobber insn. It should not change
7052 cost. */
7053 haifa_cost = 0;
7055 else
7056 haifa_cost = estimate_insn_cost (insn, curr_state);
7058 /* Stall for whatever cycles we've stalled before. */
7059 after_stall = 0;
7060 if (INSN_AFTER_STALL_P (insn) && cost > haifa_cost)
7062 haifa_cost = cost;
7063 after_stall = 1;
7065 all_issued = issued_insns == issue_rate;
7066 if (haifa_cost == 0 && all_issued)
7067 haifa_cost = 1;
7068 if (haifa_cost > 0)
7070 int i = 0;
7072 while (haifa_cost--)
7074 advance_state (curr_state);
7075 issued_insns = 0;
7076 i++;
7078 if (sched_verbose >= 2)
7080 sel_print ("advance_state (state_transition)\n");
7081 debug_state (curr_state);
7084 /* The DFA may report that e.g. insn requires 2 cycles to be
7085 issued, but on the next cycle it says that insn is ready
7086 to go. Check this here. */
7087 if (!after_stall
7088 && real_insn
7089 && haifa_cost > 0
7090 && estimate_insn_cost (insn, curr_state) == 0)
7091 break;
7093 /* When the data dependency stall is longer than the DFA stall,
7094 and when we have issued exactly issue_rate insns and stalled,
7095 it could be that after this longer stall the insn will again
7096 become unavailable to the DFA restrictions. Looks strange
7097 but happens e.g. on x86-64. So recheck DFA on the last
7098 iteration. */
7099 if ((after_stall || all_issued)
7100 && real_insn
7101 && haifa_cost == 0)
7102 haifa_cost = estimate_insn_cost (insn, curr_state);
7105 haifa_clock += i;
7106 if (sched_verbose >= 2)
7107 sel_print ("haifa clock: %d\n", haifa_clock);
7109 else
7110 gcc_assert (haifa_cost == 0);
7112 if (sched_verbose >= 2)
7113 sel_print ("Haifa cost for insn %d: %d\n", INSN_UID (insn), haifa_cost);
7115 if (targetm.sched.dfa_new_cycle)
7116 while (targetm.sched.dfa_new_cycle (sched_dump, sched_verbose, insn,
7117 haifa_last_clock, haifa_clock,
7118 &sort_p))
7120 advance_state (curr_state);
7121 issued_insns = 0;
7122 haifa_clock++;
7123 if (sched_verbose >= 2)
7125 sel_print ("advance_state (dfa_new_cycle)\n");
7126 debug_state (curr_state);
7127 sel_print ("haifa clock: %d\n", haifa_clock + 1);
7131 if (real_insn)
7133 static state_t temp = NULL;
7135 if (!temp)
7136 temp = xmalloc (dfa_state_size);
7137 memcpy (temp, curr_state, dfa_state_size);
7139 cost = state_transition (curr_state, insn);
7140 if (memcmp (temp, curr_state, dfa_state_size))
7141 issued_insns++;
7143 if (sched_verbose >= 2)
7145 sel_print ("scheduled insn %d, clock %d\n", INSN_UID (insn),
7146 haifa_clock + 1);
7147 debug_state (curr_state);
7149 gcc_assert (cost < 0);
7152 if (targetm.sched.variable_issue)
7153 targetm.sched.variable_issue (sched_dump, sched_verbose, insn, 0);
7155 INSN_SCHED_CYCLE (insn) = haifa_clock;
7157 last_clock = clock;
7158 haifa_last_clock = haifa_clock;
7162 /* Put TImode markers on insns starting a new issue group. */
7163 static void
7164 put_TImodes (void)
7166 int last_clock = -1;
7167 insn_t insn;
7169 for (insn = current_sched_info->head; insn != current_sched_info->next_tail;
7170 insn = NEXT_INSN (insn))
7172 int cost, clock;
7174 if (!INSN_P (insn))
7175 continue;
7177 clock = INSN_SCHED_CYCLE (insn);
7178 cost = (last_clock == -1) ? 1 : clock - last_clock;
7180 gcc_assert (cost >= 0);
7182 if (issue_rate > 1
7183 && GET_CODE (PATTERN (insn)) != USE
7184 && GET_CODE (PATTERN (insn)) != CLOBBER)
7186 if (reload_completed && cost > 0)
7187 PUT_MODE (insn, TImode);
7189 last_clock = clock;
7192 if (sched_verbose >= 2)
7193 sel_print ("Cost for insn %d is %d\n", INSN_UID (insn), cost);
7197 /* Perform MD_FINISH on EBBs comprising current region. When
7198 RESET_SCHED_CYCLES_P is true, run a pass emulating the scheduler
7199 to produce correct sched cycles on insns. */
7200 static void
7201 sel_region_target_finish (bool reset_sched_cycles_p)
7203 int i;
7204 bitmap scheduled_blocks = BITMAP_ALLOC (NULL);
7206 for (i = 0; i < current_nr_blocks; i++)
7208 if (bitmap_bit_p (scheduled_blocks, i))
7209 continue;
7211 /* While pipelining outer loops, skip bundling for loop
7212 preheaders. Those will be rescheduled in the outer loop. */
7213 if (sel_is_loop_preheader_p (EBB_FIRST_BB (i)))
7214 continue;
7216 find_ebb_boundaries (EBB_FIRST_BB (i), scheduled_blocks);
7218 if (no_real_insns_p (current_sched_info->head, current_sched_info->tail))
7219 continue;
7221 if (reset_sched_cycles_p)
7222 reset_sched_cycles_in_current_ebb ();
7224 if (targetm.sched.init)
7225 targetm.sched.init (sched_dump, sched_verbose, -1);
7227 put_TImodes ();
7229 if (targetm.sched.finish)
7231 targetm.sched.finish (sched_dump, sched_verbose);
7233 /* Extend luids so that insns generated by the target will
7234 get zero luid. */
7235 sched_extend_luids ();
7239 BITMAP_FREE (scheduled_blocks);
7242 /* Free the scheduling data for the current region. When RESET_SCHED_CYCLES_P
7243 is true, make an additional pass emulating scheduler to get correct insn
7244 cycles for md_finish calls. */
7245 static void
7246 sel_region_finish (bool reset_sched_cycles_p)
7248 simplify_changed_insns ();
7249 sched_finish_ready_list ();
7250 free_nop_pool ();
7252 /* Free the vectors. */
7253 vec_av_set.release ();
7254 BITMAP_FREE (current_copies);
7255 BITMAP_FREE (current_originators);
7256 BITMAP_FREE (code_motion_visited_blocks);
7257 vinsn_vec_free (vec_bookkeeping_blocked_vinsns);
7258 vinsn_vec_free (vec_target_unavailable_vinsns);
7260 /* If LV_SET of the region head should be updated, do it now because
7261 there will be no other chance. */
7263 succ_iterator si;
7264 insn_t insn;
7266 FOR_EACH_SUCC_1 (insn, si, bb_note (EBB_FIRST_BB (0)),
7267 SUCCS_NORMAL | SUCCS_SKIP_TO_LOOP_EXITS)
7269 basic_block bb = BLOCK_FOR_INSN (insn);
7271 if (!BB_LV_SET_VALID_P (bb))
7272 compute_live (insn);
7276 /* Emulate the Haifa scheduler for bundling. */
7277 if (reload_completed)
7278 sel_region_target_finish (reset_sched_cycles_p);
7280 sel_finish_global_and_expr ();
7282 bitmap_clear (forced_ebb_heads);
7284 free_nop_vinsn ();
7286 finish_deps_global ();
7287 sched_finish_luids ();
7288 h_d_i_d.release ();
7290 sel_finish_bbs ();
7291 BITMAP_FREE (blocks_to_reschedule);
7293 sel_unregister_cfg_hooks ();
7295 max_issue_size = 0;
7299 /* Functions that implement the scheduler driver. */
7301 /* Schedule a parallel instruction group on each of FENCES. MAX_SEQNO
7302 is the current maximum seqno. SCHEDULED_INSNS_TAILPP is the list
7303 of insns scheduled -- these would be postprocessed later. */
7304 static void
7305 schedule_on_fences (flist_t fences, int max_seqno,
7306 ilist_t **scheduled_insns_tailpp)
7308 flist_t old_fences = fences;
7310 if (sched_verbose >= 1)
7312 sel_print ("\nScheduling on fences: ");
7313 dump_flist (fences);
7314 sel_print ("\n");
7317 scheduled_something_on_previous_fence = false;
7318 for (; fences; fences = FLIST_NEXT (fences))
7320 fence_t fence = NULL;
7321 int seqno = 0;
7322 flist_t fences2;
7323 bool first_p = true;
7325 /* Choose the next fence group to schedule.
7326 The fact that insn can be scheduled only once
7327 on the cycle is guaranteed by two properties:
7328 1. seqnos of parallel groups decrease with each iteration.
7329 2. If is_ineligible_successor () sees the larger seqno, it
7330 checks if candidate insn is_in_current_fence_p (). */
7331 for (fences2 = old_fences; fences2; fences2 = FLIST_NEXT (fences2))
7333 fence_t f = FLIST_FENCE (fences2);
7335 if (!FENCE_PROCESSED_P (f))
7337 int i = INSN_SEQNO (FENCE_INSN (f));
7339 if (first_p || i > seqno)
7341 seqno = i;
7342 fence = f;
7343 first_p = false;
7345 else
7346 /* ??? Seqnos of different groups should be different. */
7347 gcc_assert (1 || i != seqno);
7351 gcc_assert (fence);
7353 /* As FENCE is nonnull, SEQNO is initialized. */
7354 seqno -= max_seqno + 1;
7355 fill_insns (fence, seqno, scheduled_insns_tailpp);
7356 FENCE_PROCESSED_P (fence) = true;
7359 /* All av_sets are invalidated by GLOBAL_LEVEL increase, thus we
7360 don't need to keep bookkeeping-invalidated and target-unavailable
7361 vinsns any more. */
7362 vinsn_vec_clear (&vec_bookkeeping_blocked_vinsns);
7363 vinsn_vec_clear (&vec_target_unavailable_vinsns);
7366 /* Calculate MIN_SEQNO and MAX_SEQNO. */
7367 static void
7368 find_min_max_seqno (flist_t fences, int *min_seqno, int *max_seqno)
7370 *min_seqno = *max_seqno = INSN_SEQNO (FENCE_INSN (FLIST_FENCE (fences)));
7372 /* The first element is already processed. */
7373 while ((fences = FLIST_NEXT (fences)))
7375 int seqno = INSN_SEQNO (FENCE_INSN (FLIST_FENCE (fences)));
7377 if (*min_seqno > seqno)
7378 *min_seqno = seqno;
7379 else if (*max_seqno < seqno)
7380 *max_seqno = seqno;
7384 /* Calculate new fences from FENCES. Write the current time to PTIME. */
7385 static flist_t
7386 calculate_new_fences (flist_t fences, int orig_max_seqno, int *ptime)
7388 flist_t old_fences = fences;
7389 struct flist_tail_def _new_fences, *new_fences = &_new_fences;
7390 int max_time = 0;
7392 flist_tail_init (new_fences);
7393 for (; fences; fences = FLIST_NEXT (fences))
7395 fence_t fence = FLIST_FENCE (fences);
7396 insn_t insn;
7398 if (!FENCE_BNDS (fence))
7400 /* This fence doesn't have any successors. */
7401 if (!FENCE_SCHEDULED_P (fence))
7403 /* Nothing was scheduled on this fence. */
7404 int seqno;
7406 insn = FENCE_INSN (fence);
7407 seqno = INSN_SEQNO (insn);
7408 gcc_assert (seqno > 0 && seqno <= orig_max_seqno);
7410 if (sched_verbose >= 1)
7411 sel_print ("Fence %d[%d] has not changed\n",
7412 INSN_UID (insn),
7413 BLOCK_NUM (insn));
7414 move_fence_to_fences (fences, new_fences);
7417 else
7418 extract_new_fences_from (fences, new_fences, orig_max_seqno);
7419 max_time = MAX (max_time, FENCE_CYCLE (fence));
7422 flist_clear (&old_fences);
7423 *ptime = max_time;
7424 return FLIST_TAIL_HEAD (new_fences);
7427 /* Update seqnos of insns given by PSCHEDULED_INSNS. MIN_SEQNO and MAX_SEQNO
7428 are the miminum and maximum seqnos of the group, HIGHEST_SEQNO_IN_USE is
7429 the highest seqno used in a region. Return the updated highest seqno. */
7430 static int
7431 update_seqnos_and_stage (int min_seqno, int max_seqno,
7432 int highest_seqno_in_use,
7433 ilist_t *pscheduled_insns)
7435 int new_hs;
7436 ilist_iterator ii;
7437 insn_t insn;
7439 /* Actually, new_hs is the seqno of the instruction, that was
7440 scheduled first (i.e. it is the first one in SCHEDULED_INSNS). */
7441 if (*pscheduled_insns)
7443 new_hs = (INSN_SEQNO (ILIST_INSN (*pscheduled_insns))
7444 + highest_seqno_in_use + max_seqno - min_seqno + 2);
7445 gcc_assert (new_hs > highest_seqno_in_use);
7447 else
7448 new_hs = highest_seqno_in_use;
7450 FOR_EACH_INSN (insn, ii, *pscheduled_insns)
7452 gcc_assert (INSN_SEQNO (insn) < 0);
7453 INSN_SEQNO (insn) += highest_seqno_in_use + max_seqno - min_seqno + 2;
7454 gcc_assert (INSN_SEQNO (insn) <= new_hs);
7456 /* When not pipelining, purge unneeded insn info on the scheduled insns.
7457 For example, having reg_last array of INSN_DEPS_CONTEXT in memory may
7458 require > 1GB of memory e.g. on limit-fnargs.c. */
7459 if (! pipelining_p)
7460 free_data_for_scheduled_insn (insn);
7463 ilist_clear (pscheduled_insns);
7464 global_level++;
7466 return new_hs;
7469 /* The main driver for scheduling a region. This function is responsible
7470 for correct propagation of fences (i.e. scheduling points) and creating
7471 a group of parallel insns at each of them. It also supports
7472 pipelining. ORIG_MAX_SEQNO is the maximal seqno before this pass
7473 of scheduling. */
7474 static void
7475 sel_sched_region_2 (int orig_max_seqno)
7477 int highest_seqno_in_use = orig_max_seqno;
7478 int max_time = 0;
7480 stat_bookkeeping_copies = 0;
7481 stat_insns_needed_bookkeeping = 0;
7482 stat_renamed_scheduled = 0;
7483 stat_substitutions_total = 0;
7484 num_insns_scheduled = 0;
7486 while (fences)
7488 int min_seqno, max_seqno;
7489 ilist_t scheduled_insns = NULL;
7490 ilist_t *scheduled_insns_tailp = &scheduled_insns;
7492 find_min_max_seqno (fences, &min_seqno, &max_seqno);
7493 schedule_on_fences (fences, max_seqno, &scheduled_insns_tailp);
7494 fences = calculate_new_fences (fences, orig_max_seqno, &max_time);
7495 highest_seqno_in_use = update_seqnos_and_stage (min_seqno, max_seqno,
7496 highest_seqno_in_use,
7497 &scheduled_insns);
7500 if (sched_verbose >= 1)
7502 sel_print ("Total scheduling time: %d cycles\n", max_time);
7503 sel_print ("Scheduled %d bookkeeping copies, %d insns needed "
7504 "bookkeeping, %d insns renamed, %d insns substituted\n",
7505 stat_bookkeeping_copies,
7506 stat_insns_needed_bookkeeping,
7507 stat_renamed_scheduled,
7508 stat_substitutions_total);
7512 /* Schedule a region. When pipelining, search for possibly never scheduled
7513 bookkeeping code and schedule it. Reschedule pipelined code without
7514 pipelining after. */
7515 static void
7516 sel_sched_region_1 (void)
7518 int orig_max_seqno;
7520 /* Remove empty blocks that might be in the region from the beginning. */
7521 purge_empty_blocks ();
7523 orig_max_seqno = init_seqno (NULL, NULL);
7524 gcc_assert (orig_max_seqno >= 1);
7526 /* When pipelining outer loops, create fences on the loop header,
7527 not preheader. */
7528 fences = NULL;
7529 if (current_loop_nest)
7530 init_fences (BB_END (EBB_FIRST_BB (0)));
7531 else
7532 init_fences (bb_note (EBB_FIRST_BB (0)));
7533 global_level = 1;
7535 sel_sched_region_2 (orig_max_seqno);
7537 gcc_assert (fences == NULL);
7539 if (pipelining_p)
7541 int i;
7542 basic_block bb;
7543 struct flist_tail_def _new_fences;
7544 flist_tail_t new_fences = &_new_fences;
7545 bool do_p = true;
7547 pipelining_p = false;
7548 max_ws = MIN (max_ws, issue_rate * 3 / 2);
7549 bookkeeping_p = false;
7550 enable_schedule_as_rhs_p = false;
7552 /* Schedule newly created code, that has not been scheduled yet. */
7553 do_p = true;
7555 while (do_p)
7557 do_p = false;
7559 for (i = 0; i < current_nr_blocks; i++)
7561 basic_block bb = EBB_FIRST_BB (i);
7563 if (bitmap_bit_p (blocks_to_reschedule, bb->index))
7565 if (! bb_ends_ebb_p (bb))
7566 bitmap_set_bit (blocks_to_reschedule, bb_next_bb (bb)->index);
7567 if (sel_bb_empty_p (bb))
7569 bitmap_clear_bit (blocks_to_reschedule, bb->index);
7570 continue;
7572 clear_outdated_rtx_info (bb);
7573 if (sel_insn_is_speculation_check (BB_END (bb))
7574 && JUMP_P (BB_END (bb)))
7575 bitmap_set_bit (blocks_to_reschedule,
7576 BRANCH_EDGE (bb)->dest->index);
7578 else if (! sel_bb_empty_p (bb)
7579 && INSN_SCHED_TIMES (sel_bb_head (bb)) <= 0)
7580 bitmap_set_bit (blocks_to_reschedule, bb->index);
7583 for (i = 0; i < current_nr_blocks; i++)
7585 bb = EBB_FIRST_BB (i);
7587 /* While pipelining outer loops, skip bundling for loop
7588 preheaders. Those will be rescheduled in the outer
7589 loop. */
7590 if (sel_is_loop_preheader_p (bb))
7592 clear_outdated_rtx_info (bb);
7593 continue;
7596 if (bitmap_bit_p (blocks_to_reschedule, bb->index))
7598 flist_tail_init (new_fences);
7600 orig_max_seqno = init_seqno (blocks_to_reschedule, bb);
7602 /* Mark BB as head of the new ebb. */
7603 bitmap_set_bit (forced_ebb_heads, bb->index);
7605 gcc_assert (fences == NULL);
7607 init_fences (bb_note (bb));
7609 sel_sched_region_2 (orig_max_seqno);
7611 do_p = true;
7612 break;
7619 /* Schedule the RGN region. */
7620 void
7621 sel_sched_region (int rgn)
7623 bool schedule_p;
7624 bool reset_sched_cycles_p;
7626 if (sel_region_init (rgn))
7627 return;
7629 if (sched_verbose >= 1)
7630 sel_print ("Scheduling region %d\n", rgn);
7632 schedule_p = (!sched_is_disabled_for_current_region_p ()
7633 && dbg_cnt (sel_sched_region_cnt));
7634 reset_sched_cycles_p = pipelining_p;
7635 if (schedule_p)
7636 sel_sched_region_1 ();
7637 else
7638 /* Force initialization of INSN_SCHED_CYCLEs for correct bundling. */
7639 reset_sched_cycles_p = true;
7641 sel_region_finish (reset_sched_cycles_p);
7644 /* Perform global init for the scheduler. */
7645 static void
7646 sel_global_init (void)
7648 calculate_dominance_info (CDI_DOMINATORS);
7649 alloc_sched_pools ();
7651 /* Setup the infos for sched_init. */
7652 sel_setup_sched_infos ();
7653 setup_sched_dump ();
7655 sched_rgn_init (false);
7656 sched_init ();
7658 sched_init_bbs ();
7659 /* Reset AFTER_RECOVERY if it has been set by the 1st scheduler pass. */
7660 after_recovery = 0;
7661 can_issue_more = issue_rate;
7663 sched_extend_target ();
7664 sched_deps_init (true);
7665 setup_nop_and_exit_insns ();
7666 sel_extend_global_bb_info ();
7667 init_lv_sets ();
7668 init_hard_regs_data ();
7671 /* Free the global data of the scheduler. */
7672 static void
7673 sel_global_finish (void)
7675 free_bb_note_pool ();
7676 free_lv_sets ();
7677 sel_finish_global_bb_info ();
7679 free_regset_pool ();
7680 free_nop_and_exit_insns ();
7682 sched_rgn_finish ();
7683 sched_deps_finish ();
7684 sched_finish ();
7686 if (current_loops)
7687 sel_finish_pipelining ();
7689 free_sched_pools ();
7690 free_dominance_info (CDI_DOMINATORS);
7693 /* Return true when we need to skip selective scheduling. Used for debugging. */
7694 bool
7695 maybe_skip_selective_scheduling (void)
7697 return ! dbg_cnt (sel_sched_cnt);
7700 /* The entry point. */
7701 void
7702 run_selective_scheduling (void)
7704 int rgn;
7706 if (n_basic_blocks_for_fn (cfun) == NUM_FIXED_BLOCKS)
7707 return;
7709 sel_global_init ();
7711 for (rgn = 0; rgn < nr_regions; rgn++)
7712 sel_sched_region (rgn);
7714 sel_global_finish ();
7717 #endif