PR middle-end/86864
[official-gcc.git] / gcc / sel-sched.c
blob824f1ec3403d96367afc5274d2d0f422202320c1
1 /* Instruction scheduling pass. Selective scheduler and pipeliner.
2 Copyright (C) 2006-2018 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 "cfgcleanup.h"
32 #include "insn-config.h"
33 #include "insn-attr.h"
34 #include "params.h"
35 #include "target.h"
36 #include "sched-int.h"
37 #include "rtlhooks-def.h"
38 #include "ira.h"
39 #include "ira-int.h"
40 #include "rtl-iter.h"
42 #ifdef INSN_SCHEDULING
43 #include "regset.h"
44 #include "cfgloop.h"
45 #include "sel-sched-ir.h"
46 #include "sel-sched-dump.h"
47 #include "sel-sched.h"
48 #include "dbgcnt.h"
50 /* Implementation of selective scheduling approach.
51 The below implementation follows the original approach with the following
52 changes:
54 o the scheduler works after register allocation (but can be also tuned
55 to work before RA);
56 o some instructions are not copied or register renamed;
57 o conditional jumps are not moved with code duplication;
58 o several jumps in one parallel group are not supported;
59 o when pipelining outer loops, code motion through inner loops
60 is not supported;
61 o control and data speculation are supported;
62 o some improvements for better compile time/performance were made.
64 Terminology
65 ===========
67 A vinsn, or virtual insn, is an insn with additional data characterizing
68 insn pattern, such as LHS, RHS, register sets used/set/clobbered, etc.
69 Vinsns also act as smart pointers to save memory by reusing them in
70 different expressions. A vinsn is described by vinsn_t type.
72 An expression is a vinsn with additional data characterizing its properties
73 at some point in the control flow graph. The data may be its usefulness,
74 priority, speculative status, whether it was renamed/subsituted, etc.
75 An expression is described by expr_t type.
77 Availability set (av_set) is a set of expressions at a given control flow
78 point. It is represented as av_set_t. The expressions in av sets are kept
79 sorted in the terms of expr_greater_p function. It allows to truncate
80 the set while leaving the best expressions.
82 A fence is a point through which code motion is prohibited. On each step,
83 we gather a parallel group of insns at a fence. It is possible to have
84 multiple fences. A fence is represented via fence_t.
86 A boundary is the border between the fence group and the rest of the code.
87 Currently, we never have more than one boundary per fence, as we finalize
88 the fence group when a jump is scheduled. A boundary is represented
89 via bnd_t.
91 High-level overview
92 ===================
94 The scheduler finds regions to schedule, schedules each one, and finalizes.
95 The regions are formed starting from innermost loops, so that when the inner
96 loop is pipelined, its prologue can be scheduled together with yet unprocessed
97 outer loop. The rest of acyclic regions are found using extend_rgns:
98 the blocks that are not yet allocated to any regions are traversed in top-down
99 order, and a block is added to a region to which all its predecessors belong;
100 otherwise, the block starts its own region.
102 The main scheduling loop (sel_sched_region_2) consists of just
103 scheduling on each fence and updating fences. For each fence,
104 we fill a parallel group of insns (fill_insns) until some insns can be added.
105 First, we compute available exprs (av-set) at the boundary of the current
106 group. Second, we choose the best expression from it. If the stall is
107 required to schedule any of the expressions, we advance the current cycle
108 appropriately. So, the final group does not exactly correspond to a VLIW
109 word. Third, we move the chosen expression to the boundary (move_op)
110 and update the intermediate av sets and liveness sets. We quit fill_insns
111 when either no insns left for scheduling or we have scheduled enough insns
112 so we feel like advancing a scheduling point.
114 Computing available expressions
115 ===============================
117 The computation (compute_av_set) is a bottom-up traversal. At each insn,
118 we're moving the union of its successors' sets through it via
119 moveup_expr_set. The dependent expressions are removed. Local
120 transformations (substitution, speculation) are applied to move more
121 exprs. Then the expr corresponding to the current insn is added.
122 The result is saved on each basic block header.
124 When traversing the CFG, we're moving down for no more than max_ws insns.
125 Also, we do not move down to ineligible successors (is_ineligible_successor),
126 which include moving along a back-edge, moving to already scheduled code,
127 and moving to another fence. The first two restrictions are lifted during
128 pipelining, which allows us to move insns along a back-edge. We always have
129 an acyclic region for scheduling because we forbid motion through fences.
131 Choosing the best expression
132 ============================
134 We sort the final availability set via sel_rank_for_schedule, then we remove
135 expressions which are not yet ready (tick_check_p) or which dest registers
136 cannot be used. For some of them, we choose another register via
137 find_best_reg. To do this, we run find_used_regs to calculate the set of
138 registers which cannot be used. The find_used_regs function performs
139 a traversal of code motion paths for an expr. We consider for renaming
140 only registers which are from the same regclass as the original one and
141 using which does not interfere with any live ranges. Finally, we convert
142 the resulting set to the ready list format and use max_issue and reorder*
143 hooks similarly to the Haifa scheduler.
145 Scheduling the best expression
146 ==============================
148 We run the move_op routine to perform the same type of code motion paths
149 traversal as in find_used_regs. (These are working via the same driver,
150 code_motion_path_driver.) When moving down the CFG, we look for original
151 instruction that gave birth to a chosen expression. We undo
152 the transformations performed on an expression via the history saved in it.
153 When found, we remove the instruction or leave a reg-reg copy/speculation
154 check if needed. On a way up, we insert bookkeeping copies at each join
155 point. If a copy is not needed, it will be removed later during this
156 traversal. We update the saved av sets and liveness sets on the way up, too.
158 Finalizing the schedule
159 =======================
161 When pipelining, we reschedule the blocks from which insns were pipelined
162 to get a tighter schedule. On Itanium, we also perform bundling via
163 the same routine from ia64.c.
165 Dependence analysis changes
166 ===========================
168 We augmented the sched-deps.c with hooks that get called when a particular
169 dependence is found in a particular part of an insn. Using these hooks, we
170 can do several actions such as: determine whether an insn can be moved through
171 another (has_dependence_p, moveup_expr); find out whether an insn can be
172 scheduled on the current cycle (tick_check_p); find out registers that
173 are set/used/clobbered by an insn and find out all the strange stuff that
174 restrict its movement, like SCHED_GROUP_P or CANT_MOVE (done in
175 init_global_and_expr_for_insn).
177 Initialization changes
178 ======================
180 There are parts of haifa-sched.c, sched-deps.c, and sched-rgn.c that are
181 reused in all of the schedulers. We have split up the initialization of data
182 of such parts into different functions prefixed with scheduler type and
183 postfixed with the type of data initialized: {,sel_,haifa_}sched_{init,finish},
184 sched_rgn_init/finish, sched_deps_init/finish, sched_init_{luids/bbs}, etc.
185 The same splitting is done with current_sched_info structure:
186 dependence-related parts are in sched_deps_info, common part is in
187 common_sched_info, and haifa/sel/etc part is in current_sched_info.
189 Target contexts
190 ===============
192 As we now have multiple-point scheduling, this would not work with backends
193 which save some of the scheduler state to use it in the target hooks.
194 For this purpose, we introduce a concept of target contexts, which
195 encapsulate such information. The backend should implement simple routines
196 of allocating/freeing/setting such a context. The scheduler calls these
197 as target hooks and handles the target context as an opaque pointer (similar
198 to the DFA state type, state_t).
200 Various speedups
201 ================
203 As the correct data dependence graph is not supported during scheduling (which
204 is to be changed in mid-term), we cache as much of the dependence analysis
205 results as possible to avoid reanalyzing. This includes: bitmap caches on
206 each insn in stream of the region saying yes/no for a query with a pair of
207 UIDs; hashtables with the previously done transformations on each insn in
208 stream; a vector keeping a history of transformations on each expr.
210 Also, we try to minimize the dependence context used on each fence to check
211 whether the given expression is ready for scheduling by removing from it
212 insns that are definitely completed the execution. The results of
213 tick_check_p checks are also cached in a vector on each fence.
215 We keep a valid liveness set on each insn in a region to avoid the high
216 cost of recomputation on large basic blocks.
218 Finally, we try to minimize the number of needed updates to the availability
219 sets. The updates happen in two cases: when fill_insns terminates,
220 we advance all fences and increase the stage number to show that the region
221 has changed and the sets are to be recomputed; and when the next iteration
222 of a loop in fill_insns happens (but this one reuses the saved av sets
223 on bb headers.) Thus, we try to break the fill_insns loop only when
224 "significant" number of insns from the current scheduling window was
225 scheduled. This should be made a target param.
228 TODO: correctly support the data dependence graph at all stages and get rid
229 of all caches. This should speed up the scheduler.
230 TODO: implement moving cond jumps with bookkeeping copies on both targets.
231 TODO: tune the scheduler before RA so it does not create too much pseudos.
234 References:
235 S.-M. Moon and K. Ebcioglu. Parallelizing nonnumerical code with
236 selective scheduling and software pipelining.
237 ACM TOPLAS, Vol 19, No. 6, pages 853--898, Nov. 1997.
239 Andrey Belevantsev, Maxim Kuvyrkov, Vladimir Makarov, Dmitry Melnik,
240 and Dmitry Zhurikhin. An interblock VLIW-targeted instruction scheduler
241 for GCC. In Proceedings of GCC Developers' Summit 2006.
243 Arutyun Avetisyan, Andrey Belevantsev, and Dmitry Melnik. GCC Instruction
244 Scheduler and Software Pipeliner on the Itanium Platform. EPIC-7 Workshop.
245 http://rogue.colorado.edu/EPIC7/.
249 /* True when pipelining is enabled. */
250 bool pipelining_p;
252 /* True if bookkeeping is enabled. */
253 bool bookkeeping_p;
255 /* Maximum number of insns that are eligible for renaming. */
256 int max_insns_to_rename;
259 /* Definitions of local types and macros. */
261 /* Represents possible outcomes of moving an expression through an insn. */
262 enum MOVEUP_EXPR_CODE
264 /* The expression is not changed. */
265 MOVEUP_EXPR_SAME,
267 /* Not changed, but requires a new destination register. */
268 MOVEUP_EXPR_AS_RHS,
270 /* Cannot be moved. */
271 MOVEUP_EXPR_NULL,
273 /* Changed (substituted or speculated). */
274 MOVEUP_EXPR_CHANGED
277 /* The container to be passed into rtx search & replace functions. */
278 struct rtx_search_arg
280 /* What we are searching for. */
281 rtx x;
283 /* The occurrence counter. */
284 int n;
287 typedef struct rtx_search_arg *rtx_search_arg_p;
289 /* This struct contains precomputed hard reg sets that are needed when
290 computing registers available for renaming. */
291 struct hard_regs_data
293 /* For every mode, this stores registers available for use with
294 that mode. */
295 HARD_REG_SET regs_for_mode[NUM_MACHINE_MODES];
297 /* True when regs_for_mode[mode] is initialized. */
298 bool regs_for_mode_ok[NUM_MACHINE_MODES];
300 /* For every register, it has regs that are ok to rename into it.
301 The register in question is always set. If not, this means
302 that the whole set is not computed yet. */
303 HARD_REG_SET regs_for_rename[FIRST_PSEUDO_REGISTER];
305 /* For every mode, this stores registers not available due to
306 call clobbering. */
307 HARD_REG_SET regs_for_call_clobbered[NUM_MACHINE_MODES];
309 /* All registers that are used or call used. */
310 HARD_REG_SET regs_ever_used;
312 #ifdef STACK_REGS
313 /* Stack registers. */
314 HARD_REG_SET stack_regs;
315 #endif
318 /* Holds the results of computation of available for renaming and
319 unavailable hard registers. */
320 struct reg_rename
322 /* These are unavailable due to calls crossing, globalness, etc. */
323 HARD_REG_SET unavailable_hard_regs;
325 /* These are *available* for renaming. */
326 HARD_REG_SET available_for_renaming;
328 /* Whether this code motion path crosses a call. */
329 bool crosses_call;
332 /* A global structure that contains the needed information about harg
333 regs. */
334 static struct hard_regs_data sel_hrd;
337 /* This structure holds local data used in code_motion_path_driver hooks on
338 the same or adjacent levels of recursion. Here we keep those parameters
339 that are not used in code_motion_path_driver routine itself, but only in
340 its hooks. Moreover, all parameters that can be modified in hooks are
341 in this structure, so all other parameters passed explicitly to hooks are
342 read-only. */
343 struct cmpd_local_params
345 /* Local params used in move_op_* functions. */
347 /* Edges for bookkeeping generation. */
348 edge e1, e2;
350 /* C_EXPR merged from all successors and locally allocated temporary C_EXPR. */
351 expr_t c_expr_merged, c_expr_local;
353 /* Local params used in fur_* functions. */
354 /* Copy of the ORIGINAL_INSN list, stores the original insns already
355 found before entering the current level of code_motion_path_driver. */
356 def_list_t old_original_insns;
358 /* Local params used in move_op_* functions. */
359 /* True when we have removed last insn in the block which was
360 also a boundary. Do not update anything or create bookkeeping copies. */
361 BOOL_BITFIELD removed_last_insn : 1;
364 /* Stores the static parameters for move_op_* calls. */
365 struct moveop_static_params
367 /* Destination register. */
368 rtx dest;
370 /* Current C_EXPR. */
371 expr_t c_expr;
373 /* An UID of expr_vliw which is to be moved up. If we find other exprs,
374 they are to be removed. */
375 int uid;
377 /* This is initialized to the insn on which the driver stopped its traversal. */
378 insn_t failed_insn;
380 /* True if we scheduled an insn with different register. */
381 bool was_renamed;
384 /* Stores the static parameters for fur_* calls. */
385 struct fur_static_params
387 /* Set of registers unavailable on the code motion path. */
388 regset used_regs;
390 /* Pointer to the list of original insns definitions. */
391 def_list_t *original_insns;
393 /* True if a code motion path contains a CALL insn. */
394 bool crosses_call;
397 typedef struct fur_static_params *fur_static_params_p;
398 typedef struct cmpd_local_params *cmpd_local_params_p;
399 typedef struct moveop_static_params *moveop_static_params_p;
401 /* Set of hooks and parameters that determine behavior specific to
402 move_op or find_used_regs functions. */
403 struct code_motion_path_driver_info_def
405 /* Called on enter to the basic block. */
406 int (*on_enter) (insn_t, cmpd_local_params_p, void *, bool);
408 /* Called when original expr is found. */
409 void (*orig_expr_found) (insn_t, expr_t, cmpd_local_params_p, void *);
411 /* Called while descending current basic block if current insn is not
412 the original EXPR we're searching for. */
413 bool (*orig_expr_not_found) (insn_t, av_set_t, void *);
415 /* Function to merge C_EXPRes from different successors. */
416 void (*merge_succs) (insn_t, insn_t, int, cmpd_local_params_p, void *);
418 /* Function to finalize merge from different successors and possibly
419 deallocate temporary data structures used for merging. */
420 void (*after_merge_succs) (cmpd_local_params_p, void *);
422 /* Called on the backward stage of recursion to do moveup_expr.
423 Used only with move_op_*. */
424 void (*ascend) (insn_t, void *);
426 /* Called on the ascending pass, before returning from the current basic
427 block or from the whole traversal. */
428 void (*at_first_insn) (insn_t, cmpd_local_params_p, void *);
430 /* When processing successors in move_op we need only descend into
431 SUCCS_NORMAL successors, while in find_used_regs we need SUCCS_ALL. */
432 int succ_flags;
434 /* The routine name to print in dumps ("move_op" of "find_used_regs"). */
435 const char *routine_name;
438 /* Global pointer to current hooks, either points to MOVE_OP_HOOKS or
439 FUR_HOOKS. */
440 struct code_motion_path_driver_info_def *code_motion_path_driver_info;
442 /* Set of hooks for performing move_op and find_used_regs routines with
443 code_motion_path_driver. */
444 extern struct code_motion_path_driver_info_def move_op_hooks, fur_hooks;
446 /* True if/when we want to emulate Haifa scheduler in the common code.
447 This is used in sched_rgn_local_init and in various places in
448 sched-deps.c. */
449 int sched_emulate_haifa_p;
451 /* GLOBAL_LEVEL is used to discard information stored in basic block headers
452 av_sets. Av_set of bb header is valid if its (bb header's) level is equal
453 to GLOBAL_LEVEL. And invalid if lesser. This is primarily used to advance
454 scheduling window. */
455 int global_level;
457 /* Current fences. */
458 flist_t fences;
460 /* True when separable insns should be scheduled as RHSes. */
461 static bool enable_schedule_as_rhs_p;
463 /* Used in verify_target_availability to assert that target reg is reported
464 unavailabile by both TARGET_UNAVAILABLE and find_used_regs only if
465 we haven't scheduled anything on the previous fence.
466 if scheduled_something_on_previous_fence is true, TARGET_UNAVAILABLE can
467 have more conservative value than the one returned by the
468 find_used_regs, thus we shouldn't assert that these values are equal. */
469 static bool scheduled_something_on_previous_fence;
471 /* All newly emitted insns will have their uids greater than this value. */
472 static int first_emitted_uid;
474 /* Set of basic blocks that are forced to start new ebbs. This is a subset
475 of all the ebb heads. */
476 static bitmap_head _forced_ebb_heads;
477 bitmap_head *forced_ebb_heads = &_forced_ebb_heads;
479 /* Blocks that need to be rescheduled after pipelining. */
480 bitmap blocks_to_reschedule = NULL;
482 /* True when the first lv set should be ignored when updating liveness. */
483 static bool ignore_first = false;
485 /* Number of insns max_issue has initialized data structures for. */
486 static int max_issue_size = 0;
488 /* Whether we can issue more instructions. */
489 static int can_issue_more;
491 /* Maximum software lookahead window size, reduced when rescheduling after
492 pipelining. */
493 static int max_ws;
495 /* Number of insns scheduled in current region. */
496 static int num_insns_scheduled;
498 /* A vector of expressions is used to be able to sort them. */
499 static vec<expr_t> vec_av_set;
501 /* A vector of vinsns is used to hold temporary lists of vinsns. */
502 typedef vec<vinsn_t> vinsn_vec_t;
504 /* This vector has the exprs which may still present in av_sets, but actually
505 can't be moved up due to bookkeeping created during code motion to another
506 fence. See comment near the call to update_and_record_unavailable_insns
507 for the detailed explanations. */
508 static vinsn_vec_t vec_bookkeeping_blocked_vinsns = vinsn_vec_t ();
510 /* This vector has vinsns which are scheduled with renaming on the first fence
511 and then seen on the second. For expressions with such vinsns, target
512 availability information may be wrong. */
513 static vinsn_vec_t vec_target_unavailable_vinsns = vinsn_vec_t ();
515 /* Vector to store temporary nops inserted in move_op to prevent removal
516 of empty bbs. */
517 static vec<insn_t> vec_temp_moveop_nops;
519 /* These bitmaps record original instructions scheduled on the current
520 iteration and bookkeeping copies created by them. */
521 static bitmap current_originators = NULL;
522 static bitmap current_copies = NULL;
524 /* This bitmap marks the blocks visited by code_motion_path_driver so we don't
525 visit them afterwards. */
526 static bitmap code_motion_visited_blocks = NULL;
528 /* Variables to accumulate different statistics. */
530 /* The number of bookkeeping copies created. */
531 static int stat_bookkeeping_copies;
533 /* The number of insns that required bookkeeiping for their scheduling. */
534 static int stat_insns_needed_bookkeeping;
536 /* The number of insns that got renamed. */
537 static int stat_renamed_scheduled;
539 /* The number of substitutions made during scheduling. */
540 static int stat_substitutions_total;
543 /* Forward declarations of static functions. */
544 static bool rtx_ok_for_substitution_p (rtx, rtx);
545 static int sel_rank_for_schedule (const void *, const void *);
546 static av_set_t find_sequential_best_exprs (bnd_t, expr_t, bool);
547 static basic_block find_block_for_bookkeeping (edge e1, edge e2, bool lax);
549 static rtx get_dest_from_orig_ops (av_set_t);
550 static basic_block generate_bookkeeping_insn (expr_t, edge, edge);
551 static bool find_used_regs (insn_t, av_set_t, regset, struct reg_rename *,
552 def_list_t *);
553 static bool move_op (insn_t, av_set_t, expr_t, rtx, expr_t, bool*);
554 static int code_motion_path_driver (insn_t, av_set_t, ilist_t,
555 cmpd_local_params_p, void *);
556 static void sel_sched_region_1 (void);
557 static void sel_sched_region_2 (int);
558 static av_set_t compute_av_set_inside_bb (insn_t, ilist_t, int, bool);
560 static void debug_state (state_t);
563 /* Functions that work with fences. */
565 /* Advance one cycle on FENCE. */
566 static void
567 advance_one_cycle (fence_t fence)
569 unsigned i;
570 int cycle;
571 rtx_insn *insn;
573 advance_state (FENCE_STATE (fence));
574 cycle = ++FENCE_CYCLE (fence);
575 FENCE_ISSUED_INSNS (fence) = 0;
576 FENCE_STARTS_CYCLE_P (fence) = 1;
577 can_issue_more = issue_rate;
578 FENCE_ISSUE_MORE (fence) = can_issue_more;
580 for (i = 0; vec_safe_iterate (FENCE_EXECUTING_INSNS (fence), i, &insn); )
582 if (INSN_READY_CYCLE (insn) < cycle)
584 remove_from_deps (FENCE_DC (fence), insn);
585 FENCE_EXECUTING_INSNS (fence)->unordered_remove (i);
586 continue;
588 i++;
590 if (sched_verbose >= 2)
592 sel_print ("Finished a cycle. Current cycle = %d\n", FENCE_CYCLE (fence));
593 debug_state (FENCE_STATE (fence));
597 /* Returns true when SUCC in a fallthru bb of INSN, possibly
598 skipping empty basic blocks. */
599 static bool
600 in_fallthru_bb_p (rtx_insn *insn, rtx succ)
602 basic_block bb = BLOCK_FOR_INSN (insn);
603 edge e;
605 if (bb == BLOCK_FOR_INSN (succ))
606 return true;
608 e = find_fallthru_edge_from (bb);
609 if (e)
610 bb = e->dest;
611 else
612 return false;
614 while (sel_bb_empty_p (bb))
615 bb = bb->next_bb;
617 return bb == BLOCK_FOR_INSN (succ);
620 /* Construct successor fences from OLD_FENCEs and put them in NEW_FENCES.
621 When a successor will continue a ebb, transfer all parameters of a fence
622 to the new fence. ORIG_MAX_SEQNO is the maximal seqno before this round
623 of scheduling helping to distinguish between the old and the new code. */
624 static void
625 extract_new_fences_from (flist_t old_fences, flist_tail_t new_fences,
626 int orig_max_seqno)
628 bool was_here_p = false;
629 insn_t insn = NULL;
630 insn_t succ;
631 succ_iterator si;
632 ilist_iterator ii;
633 fence_t fence = FLIST_FENCE (old_fences);
634 basic_block bb;
636 /* Get the only element of FENCE_BNDS (fence). */
637 FOR_EACH_INSN (insn, ii, FENCE_BNDS (fence))
639 gcc_assert (!was_here_p);
640 was_here_p = true;
642 gcc_assert (was_here_p && insn != NULL_RTX);
644 /* When in the "middle" of the block, just move this fence
645 to the new list. */
646 bb = BLOCK_FOR_INSN (insn);
647 if (! sel_bb_end_p (insn)
648 || (single_succ_p (bb)
649 && single_pred_p (single_succ (bb))))
651 insn_t succ;
653 succ = (sel_bb_end_p (insn)
654 ? sel_bb_head (single_succ (bb))
655 : NEXT_INSN (insn));
657 if (INSN_SEQNO (succ) > 0
658 && INSN_SEQNO (succ) <= orig_max_seqno
659 && INSN_SCHED_TIMES (succ) <= 0)
661 FENCE_INSN (fence) = succ;
662 move_fence_to_fences (old_fences, new_fences);
664 if (sched_verbose >= 1)
665 sel_print ("Fence %d continues as %d[%d] (state continue)\n",
666 INSN_UID (insn), INSN_UID (succ), BLOCK_NUM (succ));
668 return;
671 /* Otherwise copy fence's structures to (possibly) multiple successors. */
672 FOR_EACH_SUCC_1 (succ, si, insn, SUCCS_NORMAL | SUCCS_SKIP_TO_LOOP_EXITS)
674 int seqno = INSN_SEQNO (succ);
676 if (seqno > 0 && seqno <= orig_max_seqno
677 && (pipelining_p || INSN_SCHED_TIMES (succ) <= 0))
679 bool b = (in_same_ebb_p (insn, succ)
680 || in_fallthru_bb_p (insn, succ));
682 if (sched_verbose >= 1)
683 sel_print ("Fence %d continues as %d[%d] (state %s)\n",
684 INSN_UID (insn), INSN_UID (succ),
685 BLOCK_NUM (succ), b ? "continue" : "reset");
687 if (b)
688 add_dirty_fence_to_fences (new_fences, succ, fence);
689 else
691 /* Mark block of the SUCC as head of the new ebb. */
692 bitmap_set_bit (forced_ebb_heads, BLOCK_NUM (succ));
693 add_clean_fence_to_fences (new_fences, succ, fence);
700 /* Functions to support substitution. */
702 /* Returns whether INSN with dependence status DS is eligible for
703 substitution, i.e. it's a copy operation x := y, and RHS that is
704 moved up through this insn should be substituted. */
705 static bool
706 can_substitute_through_p (insn_t insn, ds_t ds)
708 /* We can substitute only true dependencies. */
709 if ((ds & DEP_OUTPUT)
710 || (ds & DEP_ANTI)
711 || ! INSN_RHS (insn)
712 || ! INSN_LHS (insn))
713 return false;
715 /* Now we just need to make sure the INSN_RHS consists of only one
716 simple REG rtx. */
717 if (REG_P (INSN_LHS (insn))
718 && REG_P (INSN_RHS (insn)))
719 return true;
720 return false;
723 /* Substitute all occurrences of INSN's destination in EXPR' vinsn with INSN's
724 source (if INSN is eligible for substitution). Returns TRUE if
725 substitution was actually performed, FALSE otherwise. Substitution might
726 be not performed because it's either EXPR' vinsn doesn't contain INSN's
727 destination or the resulting insn is invalid for the target machine.
728 When UNDO is true, perform unsubstitution instead (the difference is in
729 the part of rtx on which validate_replace_rtx is called). */
730 static bool
731 substitute_reg_in_expr (expr_t expr, insn_t insn, bool undo)
733 rtx *where;
734 bool new_insn_valid;
735 vinsn_t *vi = &EXPR_VINSN (expr);
736 bool has_rhs = VINSN_RHS (*vi) != NULL;
737 rtx old, new_rtx;
739 /* Do not try to replace in SET_DEST. Although we'll choose new
740 register for the RHS, we don't want to change RHS' original reg.
741 If the insn is not SET, we may still be able to substitute something
742 in it, and if we're here (don't have deps), it doesn't write INSN's
743 dest. */
744 where = (has_rhs
745 ? &VINSN_RHS (*vi)
746 : &PATTERN (VINSN_INSN_RTX (*vi)));
747 old = undo ? INSN_RHS (insn) : INSN_LHS (insn);
749 /* Substitute if INSN has a form of x:=y and LHS(INSN) occurs in *VI. */
750 if (rtx_ok_for_substitution_p (old, *where))
752 rtx_insn *new_insn;
753 rtx *where_replace;
755 /* We should copy these rtxes before substitution. */
756 new_rtx = copy_rtx (undo ? INSN_LHS (insn) : INSN_RHS (insn));
757 new_insn = create_copy_of_insn_rtx (VINSN_INSN_RTX (*vi));
759 /* Where we'll replace.
760 WHERE_REPLACE should point inside NEW_INSN, so INSN_RHS couldn't be
761 used instead of SET_SRC. */
762 where_replace = (has_rhs
763 ? &SET_SRC (PATTERN (new_insn))
764 : &PATTERN (new_insn));
766 new_insn_valid
767 = validate_replace_rtx_part_nosimplify (old, new_rtx, where_replace,
768 new_insn);
770 /* ??? Actually, constrain_operands result depends upon choice of
771 destination register. E.g. if we allow single register to be an rhs,
772 and if we try to move dx=ax(as rhs) through ax=dx, we'll result
773 in invalid insn dx=dx, so we'll loose this rhs here.
774 Just can't come up with significant testcase for this, so just
775 leaving it for now. */
776 if (new_insn_valid)
778 change_vinsn_in_expr (expr,
779 create_vinsn_from_insn_rtx (new_insn, false));
781 /* Do not allow clobbering the address register of speculative
782 insns. */
783 if ((EXPR_SPEC_DONE_DS (expr) & SPECULATIVE)
784 && register_unavailable_p (VINSN_REG_USES (EXPR_VINSN (expr)),
785 expr_dest_reg (expr)))
786 EXPR_TARGET_AVAILABLE (expr) = false;
788 return true;
790 else
791 return false;
793 else
794 return false;
797 /* Return the number of places WHAT appears within WHERE.
798 Bail out when we found a reference occupying several hard registers. */
799 static int
800 count_occurrences_equiv (const_rtx what, const_rtx where)
802 int count = 0;
803 subrtx_iterator::array_type array;
804 FOR_EACH_SUBRTX (iter, array, where, NONCONST)
806 const_rtx x = *iter;
807 if (REG_P (x) && REGNO (x) == REGNO (what))
809 /* Bail out if mode is different or more than one register is
810 used. */
811 if (GET_MODE (x) != GET_MODE (what) || REG_NREGS (x) > 1)
812 return 0;
813 count += 1;
815 else if (GET_CODE (x) == SUBREG
816 && (!REG_P (SUBREG_REG (x))
817 || REGNO (SUBREG_REG (x)) == REGNO (what)))
818 /* ??? Do not support substituting regs inside subregs. In that case,
819 simplify_subreg will be called by validate_replace_rtx, and
820 unsubstitution will fail later. */
821 return 0;
823 return count;
826 /* Returns TRUE if WHAT is found in WHERE rtx tree. */
827 static bool
828 rtx_ok_for_substitution_p (rtx what, rtx where)
830 return (count_occurrences_equiv (what, where) > 0);
834 /* Functions to support register renaming. */
836 /* Substitute VI's set source with REGNO. Returns newly created pattern
837 that has REGNO as its source. */
838 static rtx_insn *
839 create_insn_rtx_with_rhs (vinsn_t vi, rtx rhs_rtx)
841 rtx lhs_rtx;
842 rtx pattern;
843 rtx_insn *insn_rtx;
845 lhs_rtx = copy_rtx (VINSN_LHS (vi));
847 pattern = gen_rtx_SET (lhs_rtx, rhs_rtx);
848 insn_rtx = create_insn_rtx_from_pattern (pattern, NULL_RTX);
850 return insn_rtx;
853 /* Returns whether INSN's src can be replaced with register number
854 NEW_SRC_REG. E.g. the following insn is valid for i386:
856 (insn:HI 2205 6585 2207 727 ../../gcc/libiberty/regex.c:3337
857 (set (mem/s:QI (plus:SI (plus:SI (reg/f:SI 7 sp)
858 (reg:SI 0 ax [orig:770 c1 ] [770]))
859 (const_int 288 [0x120])) [0 str S1 A8])
860 (const_int 0 [0x0])) 43 {*movqi_1} (nil)
861 (nil))
863 But if we change (const_int 0 [0x0]) to (reg:QI 4 si), it will be invalid
864 because of operand constraints:
866 (define_insn "*movqi_1"
867 [(set (match_operand:QI 0 "nonimmediate_operand" "=q,q ,q ,r,r ,?r,m")
868 (match_operand:QI 1 "general_operand" " q,qn,qm,q,rn,qm,qn")
871 So do constrain_operands here, before choosing NEW_SRC_REG as best
872 reg for rhs. */
874 static bool
875 replace_src_with_reg_ok_p (insn_t insn, rtx new_src_reg)
877 vinsn_t vi = INSN_VINSN (insn);
878 machine_mode mode;
879 rtx dst_loc;
880 bool res;
882 gcc_assert (VINSN_SEPARABLE_P (vi));
884 get_dest_and_mode (insn, &dst_loc, &mode);
885 gcc_assert (mode == GET_MODE (new_src_reg));
887 if (REG_P (dst_loc) && REGNO (new_src_reg) == REGNO (dst_loc))
888 return true;
890 /* See whether SET_SRC can be replaced with this register. */
891 validate_change (insn, &SET_SRC (PATTERN (insn)), new_src_reg, 1);
892 res = verify_changes (0);
893 cancel_changes (0);
895 return res;
898 /* Returns whether INSN still be valid after replacing it's DEST with
899 register NEW_REG. */
900 static bool
901 replace_dest_with_reg_ok_p (insn_t insn, rtx new_reg)
903 vinsn_t vi = INSN_VINSN (insn);
904 bool res;
906 /* We should deal here only with separable insns. */
907 gcc_assert (VINSN_SEPARABLE_P (vi));
908 gcc_assert (GET_MODE (VINSN_LHS (vi)) == GET_MODE (new_reg));
910 /* See whether SET_DEST can be replaced with this register. */
911 validate_change (insn, &SET_DEST (PATTERN (insn)), new_reg, 1);
912 res = verify_changes (0);
913 cancel_changes (0);
915 return res;
918 /* Create a pattern with rhs of VI and lhs of LHS_RTX. */
919 static rtx_insn *
920 create_insn_rtx_with_lhs (vinsn_t vi, rtx lhs_rtx)
922 rtx rhs_rtx;
923 rtx pattern;
924 rtx_insn *insn_rtx;
926 rhs_rtx = copy_rtx (VINSN_RHS (vi));
928 pattern = gen_rtx_SET (lhs_rtx, rhs_rtx);
929 insn_rtx = create_insn_rtx_from_pattern (pattern, NULL_RTX);
931 return insn_rtx;
934 /* Substitute lhs in the given expression EXPR for the register with number
935 NEW_REGNO. SET_DEST may be arbitrary rtx, not only register. */
936 static void
937 replace_dest_with_reg_in_expr (expr_t expr, rtx new_reg)
939 rtx_insn *insn_rtx;
940 vinsn_t vinsn;
942 insn_rtx = create_insn_rtx_with_lhs (EXPR_VINSN (expr), new_reg);
943 vinsn = create_vinsn_from_insn_rtx (insn_rtx, false);
945 change_vinsn_in_expr (expr, vinsn);
946 EXPR_WAS_RENAMED (expr) = 1;
947 EXPR_TARGET_AVAILABLE (expr) = 1;
950 /* Returns whether VI writes either one of the USED_REGS registers or,
951 if a register is a hard one, one of the UNAVAILABLE_HARD_REGS registers. */
952 static bool
953 vinsn_writes_one_of_regs_p (vinsn_t vi, regset used_regs,
954 HARD_REG_SET unavailable_hard_regs)
956 unsigned regno;
957 reg_set_iterator rsi;
959 EXECUTE_IF_SET_IN_REG_SET (VINSN_REG_SETS (vi), 0, regno, rsi)
961 if (REGNO_REG_SET_P (used_regs, regno))
962 return true;
963 if (HARD_REGISTER_NUM_P (regno)
964 && TEST_HARD_REG_BIT (unavailable_hard_regs, regno))
965 return true;
968 EXECUTE_IF_SET_IN_REG_SET (VINSN_REG_CLOBBERS (vi), 0, regno, rsi)
970 if (REGNO_REG_SET_P (used_regs, regno))
971 return true;
972 if (HARD_REGISTER_NUM_P (regno)
973 && TEST_HARD_REG_BIT (unavailable_hard_regs, regno))
974 return true;
977 return false;
980 /* Returns register class of the output register in INSN.
981 Returns NO_REGS for call insns because some targets have constraints on
982 destination register of a call insn.
984 Code adopted from regrename.c::build_def_use. */
985 static enum reg_class
986 get_reg_class (rtx_insn *insn)
988 int i, n_ops;
990 extract_constrain_insn (insn);
991 preprocess_constraints (insn);
992 n_ops = recog_data.n_operands;
994 const operand_alternative *op_alt = which_op_alt ();
995 if (asm_noperands (PATTERN (insn)) > 0)
997 for (i = 0; i < n_ops; i++)
998 if (recog_data.operand_type[i] == OP_OUT)
1000 rtx *loc = recog_data.operand_loc[i];
1001 rtx op = *loc;
1002 enum reg_class cl = alternative_class (op_alt, i);
1004 if (REG_P (op)
1005 && REGNO (op) == ORIGINAL_REGNO (op))
1006 continue;
1008 return cl;
1011 else if (!CALL_P (insn))
1013 for (i = 0; i < n_ops + recog_data.n_dups; i++)
1015 int opn = i < n_ops ? i : recog_data.dup_num[i - n_ops];
1016 enum reg_class cl = alternative_class (op_alt, opn);
1018 if (recog_data.operand_type[opn] == OP_OUT ||
1019 recog_data.operand_type[opn] == OP_INOUT)
1020 return cl;
1024 /* Insns like
1025 (insn (set (reg:CCZ 17 flags) (compare:CCZ ...)))
1026 may result in returning NO_REGS, cause flags is written implicitly through
1027 CMP insn, which has no OP_OUT | OP_INOUT operands. */
1028 return NO_REGS;
1031 /* Calculate HARD_REGNO_RENAME_OK data for REGNO. */
1032 static void
1033 init_hard_regno_rename (int regno)
1035 int cur_reg;
1037 SET_HARD_REG_BIT (sel_hrd.regs_for_rename[regno], regno);
1039 for (cur_reg = 0; cur_reg < FIRST_PSEUDO_REGISTER; cur_reg++)
1041 /* We are not interested in renaming in other regs. */
1042 if (!TEST_HARD_REG_BIT (sel_hrd.regs_ever_used, cur_reg))
1043 continue;
1045 if (HARD_REGNO_RENAME_OK (regno, cur_reg))
1046 SET_HARD_REG_BIT (sel_hrd.regs_for_rename[regno], cur_reg);
1050 /* A wrapper around HARD_REGNO_RENAME_OK that will look into the hard regs
1051 data first. */
1052 static inline bool
1053 sel_hard_regno_rename_ok (int from ATTRIBUTE_UNUSED, int to ATTRIBUTE_UNUSED)
1055 /* Check whether this is all calculated. */
1056 if (TEST_HARD_REG_BIT (sel_hrd.regs_for_rename[from], from))
1057 return TEST_HARD_REG_BIT (sel_hrd.regs_for_rename[from], to);
1059 init_hard_regno_rename (from);
1061 return TEST_HARD_REG_BIT (sel_hrd.regs_for_rename[from], to);
1064 /* Calculate set of registers that are capable of holding MODE. */
1065 static void
1066 init_regs_for_mode (machine_mode mode)
1068 int cur_reg;
1070 CLEAR_HARD_REG_SET (sel_hrd.regs_for_mode[mode]);
1071 CLEAR_HARD_REG_SET (sel_hrd.regs_for_call_clobbered[mode]);
1073 for (cur_reg = 0; cur_reg < FIRST_PSEUDO_REGISTER; cur_reg++)
1075 int nregs;
1076 int i;
1078 /* See whether it accepts all modes that occur in
1079 original insns. */
1080 if (!targetm.hard_regno_mode_ok (cur_reg, mode))
1081 continue;
1083 nregs = hard_regno_nregs (cur_reg, mode);
1085 for (i = nregs - 1; i >= 0; --i)
1086 if (fixed_regs[cur_reg + i]
1087 || global_regs[cur_reg + i]
1088 /* Can't use regs which aren't saved by
1089 the prologue. */
1090 || !TEST_HARD_REG_BIT (sel_hrd.regs_ever_used, cur_reg + i)
1091 /* Can't use regs with non-null REG_BASE_VALUE, because adjusting
1092 it affects aliasing globally and invalidates all AV sets. */
1093 || get_reg_base_value (cur_reg + i)
1094 #ifdef LEAF_REGISTERS
1095 /* We can't use a non-leaf register if we're in a
1096 leaf function. */
1097 || (crtl->is_leaf
1098 && !LEAF_REGISTERS[cur_reg + i])
1099 #endif
1101 break;
1103 if (i >= 0)
1104 continue;
1106 if (targetm.hard_regno_call_part_clobbered (cur_reg, mode))
1107 SET_HARD_REG_BIT (sel_hrd.regs_for_call_clobbered[mode],
1108 cur_reg);
1110 /* If the CUR_REG passed all the checks above,
1111 then it's ok. */
1112 SET_HARD_REG_BIT (sel_hrd.regs_for_mode[mode], cur_reg);
1115 sel_hrd.regs_for_mode_ok[mode] = true;
1118 /* Init all register sets gathered in HRD. */
1119 static void
1120 init_hard_regs_data (void)
1122 int cur_reg = 0;
1123 int cur_mode = 0;
1125 CLEAR_HARD_REG_SET (sel_hrd.regs_ever_used);
1126 for (cur_reg = 0; cur_reg < FIRST_PSEUDO_REGISTER; cur_reg++)
1127 if (df_regs_ever_live_p (cur_reg) || call_used_regs[cur_reg])
1128 SET_HARD_REG_BIT (sel_hrd.regs_ever_used, cur_reg);
1130 /* Initialize registers that are valid based on mode when this is
1131 really needed. */
1132 for (cur_mode = 0; cur_mode < NUM_MACHINE_MODES; cur_mode++)
1133 sel_hrd.regs_for_mode_ok[cur_mode] = false;
1135 /* Mark that all HARD_REGNO_RENAME_OK is not calculated. */
1136 for (cur_reg = 0; cur_reg < FIRST_PSEUDO_REGISTER; cur_reg++)
1137 CLEAR_HARD_REG_SET (sel_hrd.regs_for_rename[cur_reg]);
1139 #ifdef STACK_REGS
1140 CLEAR_HARD_REG_SET (sel_hrd.stack_regs);
1142 for (cur_reg = FIRST_STACK_REG; cur_reg <= LAST_STACK_REG; cur_reg++)
1143 SET_HARD_REG_BIT (sel_hrd.stack_regs, cur_reg);
1144 #endif
1147 /* Mark hardware regs in REG_RENAME_P that are not suitable
1148 for renaming rhs in INSN due to hardware restrictions (register class,
1149 modes compatibility etc). This doesn't affect original insn's dest reg,
1150 if it isn't in USED_REGS. DEF is a definition insn of rhs for which the
1151 destination register is sought. LHS (DEF->ORIG_INSN) may be REG or MEM.
1152 Registers that are in used_regs are always marked in
1153 unavailable_hard_regs as well. */
1155 static void
1156 mark_unavailable_hard_regs (def_t def, struct reg_rename *reg_rename_p,
1157 regset used_regs ATTRIBUTE_UNUSED)
1159 machine_mode mode;
1160 enum reg_class cl = NO_REGS;
1161 rtx orig_dest;
1162 unsigned cur_reg, regno;
1163 hard_reg_set_iterator hrsi;
1165 gcc_assert (GET_CODE (PATTERN (def->orig_insn)) == SET);
1166 gcc_assert (reg_rename_p);
1168 orig_dest = SET_DEST (PATTERN (def->orig_insn));
1170 /* We have decided not to rename 'mem = something;' insns, as 'something'
1171 is usually a register. */
1172 if (!REG_P (orig_dest))
1173 return;
1175 regno = REGNO (orig_dest);
1177 /* If before reload, don't try to work with pseudos. */
1178 if (!reload_completed && !HARD_REGISTER_NUM_P (regno))
1179 return;
1181 if (reload_completed)
1182 cl = get_reg_class (def->orig_insn);
1184 /* Stop if the original register is one of the fixed_regs, global_regs or
1185 frame pointer, or we could not discover its class. */
1186 if (fixed_regs[regno]
1187 || global_regs[regno]
1188 || (!HARD_FRAME_POINTER_IS_FRAME_POINTER && frame_pointer_needed
1189 && regno == HARD_FRAME_POINTER_REGNUM)
1190 || (HARD_FRAME_POINTER_IS_FRAME_POINTER && frame_pointer_needed
1191 && regno == FRAME_POINTER_REGNUM)
1192 || (reload_completed && cl == NO_REGS))
1194 SET_HARD_REG_SET (reg_rename_p->unavailable_hard_regs);
1196 /* Give a chance for original register, if it isn't in used_regs. */
1197 if (!def->crosses_call)
1198 CLEAR_HARD_REG_BIT (reg_rename_p->unavailable_hard_regs, regno);
1200 return;
1203 /* If something allocated on stack in this function, mark frame pointer
1204 register unavailable, considering also modes.
1205 FIXME: it is enough to do this once per all original defs. */
1206 if (frame_pointer_needed)
1208 add_to_hard_reg_set (&reg_rename_p->unavailable_hard_regs,
1209 Pmode, FRAME_POINTER_REGNUM);
1211 if (!HARD_FRAME_POINTER_IS_FRAME_POINTER)
1212 add_to_hard_reg_set (&reg_rename_p->unavailable_hard_regs,
1213 Pmode, HARD_FRAME_POINTER_REGNUM);
1216 #ifdef STACK_REGS
1217 /* For the stack registers the presence of FIRST_STACK_REG in USED_REGS
1218 is equivalent to as if all stack regs were in this set.
1219 I.e. no stack register can be renamed, and even if it's an original
1220 register here we make sure it won't be lifted over it's previous def
1221 (it's previous def will appear as if it's a FIRST_STACK_REG def.
1222 The HARD_REGNO_RENAME_OK covers other cases in condition below. */
1223 if (IN_RANGE (REGNO (orig_dest), FIRST_STACK_REG, LAST_STACK_REG)
1224 && REGNO_REG_SET_P (used_regs, FIRST_STACK_REG))
1225 IOR_HARD_REG_SET (reg_rename_p->unavailable_hard_regs,
1226 sel_hrd.stack_regs);
1227 #endif
1229 /* If there's a call on this path, make regs from call_used_reg_set
1230 unavailable. */
1231 if (def->crosses_call)
1232 IOR_HARD_REG_SET (reg_rename_p->unavailable_hard_regs,
1233 call_used_reg_set);
1235 /* Stop here before reload: we need FRAME_REGS, STACK_REGS, and crosses_call,
1236 but not register classes. */
1237 if (!reload_completed)
1238 return;
1240 /* Leave regs as 'available' only from the current
1241 register class. */
1242 COPY_HARD_REG_SET (reg_rename_p->available_for_renaming,
1243 reg_class_contents[cl]);
1245 mode = GET_MODE (orig_dest);
1247 /* Leave only registers available for this mode. */
1248 if (!sel_hrd.regs_for_mode_ok[mode])
1249 init_regs_for_mode (mode);
1250 AND_HARD_REG_SET (reg_rename_p->available_for_renaming,
1251 sel_hrd.regs_for_mode[mode]);
1253 /* Exclude registers that are partially call clobbered. */
1254 if (def->crosses_call
1255 && !targetm.hard_regno_call_part_clobbered (regno, mode))
1256 AND_COMPL_HARD_REG_SET (reg_rename_p->available_for_renaming,
1257 sel_hrd.regs_for_call_clobbered[mode]);
1259 /* Leave only those that are ok to rename. */
1260 EXECUTE_IF_SET_IN_HARD_REG_SET (reg_rename_p->available_for_renaming,
1261 0, cur_reg, hrsi)
1263 int nregs;
1264 int i;
1266 nregs = hard_regno_nregs (cur_reg, mode);
1267 gcc_assert (nregs > 0);
1269 for (i = nregs - 1; i >= 0; --i)
1270 if (! sel_hard_regno_rename_ok (regno + i, cur_reg + i))
1271 break;
1273 if (i >= 0)
1274 CLEAR_HARD_REG_BIT (reg_rename_p->available_for_renaming,
1275 cur_reg);
1278 AND_COMPL_HARD_REG_SET (reg_rename_p->available_for_renaming,
1279 reg_rename_p->unavailable_hard_regs);
1281 /* Regno is always ok from the renaming part of view, but it really
1282 could be in *unavailable_hard_regs already, so set it here instead
1283 of there. */
1284 SET_HARD_REG_BIT (reg_rename_p->available_for_renaming, regno);
1287 /* reg_rename_tick[REG1] > reg_rename_tick[REG2] if REG1 was chosen as the
1288 best register more recently than REG2. */
1289 static int reg_rename_tick[FIRST_PSEUDO_REGISTER];
1291 /* Indicates the number of times renaming happened before the current one. */
1292 static int reg_rename_this_tick;
1294 /* Choose the register among free, that is suitable for storing
1295 the rhs value.
1297 ORIGINAL_INSNS is the list of insns where the operation (rhs)
1298 originally appears. There could be multiple original operations
1299 for single rhs since we moving it up and merging along different
1300 paths.
1302 Some code is adapted from regrename.c (regrename_optimize).
1303 If original register is available, function returns it.
1304 Otherwise it performs the checks, so the new register should
1305 comply with the following:
1306 - it should not violate any live ranges (such registers are in
1307 REG_RENAME_P->available_for_renaming set);
1308 - it should not be in the HARD_REGS_USED regset;
1309 - it should be in the class compatible with original uses;
1310 - it should not be clobbered through reference with different mode;
1311 - if we're in the leaf function, then the new register should
1312 not be in the LEAF_REGISTERS;
1313 - etc.
1315 If several registers meet the conditions, the register with smallest
1316 tick is returned to achieve more even register allocation.
1318 If original register seems to be ok, we set *IS_ORIG_REG_P_PTR to true.
1320 If no register satisfies the above conditions, NULL_RTX is returned. */
1321 static rtx
1322 choose_best_reg_1 (HARD_REG_SET hard_regs_used,
1323 struct reg_rename *reg_rename_p,
1324 def_list_t original_insns, bool *is_orig_reg_p_ptr)
1326 int best_new_reg;
1327 unsigned cur_reg;
1328 machine_mode mode = VOIDmode;
1329 unsigned regno, i, n;
1330 hard_reg_set_iterator hrsi;
1331 def_list_iterator di;
1332 def_t def;
1334 /* If original register is available, return it. */
1335 *is_orig_reg_p_ptr = true;
1337 FOR_EACH_DEF (def, di, original_insns)
1339 rtx orig_dest = SET_DEST (PATTERN (def->orig_insn));
1341 gcc_assert (REG_P (orig_dest));
1343 /* Check that all original operations have the same mode.
1344 This is done for the next loop; if we'd return from this
1345 loop, we'd check only part of them, but in this case
1346 it doesn't matter. */
1347 if (mode == VOIDmode)
1348 mode = GET_MODE (orig_dest);
1349 gcc_assert (mode == GET_MODE (orig_dest));
1351 regno = REGNO (orig_dest);
1352 for (i = 0, n = REG_NREGS (orig_dest); i < n; i++)
1353 if (TEST_HARD_REG_BIT (hard_regs_used, regno + i))
1354 break;
1356 /* All hard registers are available. */
1357 if (i == n)
1359 gcc_assert (mode != VOIDmode);
1361 /* Hard registers should not be shared. */
1362 return gen_rtx_REG (mode, regno);
1366 *is_orig_reg_p_ptr = false;
1367 best_new_reg = -1;
1369 /* Among all available regs choose the register that was
1370 allocated earliest. */
1371 EXECUTE_IF_SET_IN_HARD_REG_SET (reg_rename_p->available_for_renaming,
1372 0, cur_reg, hrsi)
1373 if (! TEST_HARD_REG_BIT (hard_regs_used, cur_reg))
1375 /* Check that all hard regs for mode are available. */
1376 for (i = 1, n = hard_regno_nregs (cur_reg, mode); i < n; i++)
1377 if (TEST_HARD_REG_BIT (hard_regs_used, cur_reg + i)
1378 || !TEST_HARD_REG_BIT (reg_rename_p->available_for_renaming,
1379 cur_reg + i))
1380 break;
1382 if (i < n)
1383 continue;
1385 /* All hard registers are available. */
1386 if (best_new_reg < 0
1387 || reg_rename_tick[cur_reg] < reg_rename_tick[best_new_reg])
1389 best_new_reg = cur_reg;
1391 /* Return immediately when we know there's no better reg. */
1392 if (! reg_rename_tick[best_new_reg])
1393 break;
1397 if (best_new_reg >= 0)
1399 /* Use the check from the above loop. */
1400 gcc_assert (mode != VOIDmode);
1401 return gen_rtx_REG (mode, best_new_reg);
1404 return NULL_RTX;
1407 /* A wrapper around choose_best_reg_1 () to verify that we make correct
1408 assumptions about available registers in the function. */
1409 static rtx
1410 choose_best_reg (HARD_REG_SET hard_regs_used, struct reg_rename *reg_rename_p,
1411 def_list_t original_insns, bool *is_orig_reg_p_ptr)
1413 rtx best_reg = choose_best_reg_1 (hard_regs_used, reg_rename_p,
1414 original_insns, is_orig_reg_p_ptr);
1416 /* FIXME loop over hard_regno_nregs here. */
1417 gcc_assert (best_reg == NULL_RTX
1418 || TEST_HARD_REG_BIT (sel_hrd.regs_ever_used, REGNO (best_reg)));
1420 return best_reg;
1423 /* Choose the pseudo register for storing rhs value. As this is supposed
1424 to work before reload, we return either the original register or make
1425 the new one. The parameters are the same that in choose_nest_reg_1
1426 functions, except that USED_REGS may contain pseudos.
1427 If we work with hard regs, check also REG_RENAME_P->UNAVAILABLE_HARD_REGS.
1429 TODO: take into account register pressure while doing this. Up to this
1430 moment, this function would never return NULL for pseudos, but we should
1431 not rely on this. */
1432 static rtx
1433 choose_best_pseudo_reg (regset used_regs,
1434 struct reg_rename *reg_rename_p,
1435 def_list_t original_insns, bool *is_orig_reg_p_ptr)
1437 def_list_iterator i;
1438 def_t def;
1439 machine_mode mode = VOIDmode;
1440 bool bad_hard_regs = false;
1442 /* We should not use this after reload. */
1443 gcc_assert (!reload_completed);
1445 /* If original register is available, return it. */
1446 *is_orig_reg_p_ptr = true;
1448 FOR_EACH_DEF (def, i, original_insns)
1450 rtx dest = SET_DEST (PATTERN (def->orig_insn));
1451 int orig_regno;
1453 gcc_assert (REG_P (dest));
1455 /* Check that all original operations have the same mode. */
1456 if (mode == VOIDmode)
1457 mode = GET_MODE (dest);
1458 else
1459 gcc_assert (mode == GET_MODE (dest));
1460 orig_regno = REGNO (dest);
1462 /* Check that nothing in used_regs intersects with orig_regno. When
1463 we have a hard reg here, still loop over hard_regno_nregs. */
1464 if (HARD_REGISTER_NUM_P (orig_regno))
1466 int j, n;
1467 for (j = 0, n = REG_NREGS (dest); j < n; j++)
1468 if (REGNO_REG_SET_P (used_regs, orig_regno + j))
1469 break;
1470 if (j < n)
1471 continue;
1473 else
1475 if (REGNO_REG_SET_P (used_regs, orig_regno))
1476 continue;
1478 if (HARD_REGISTER_NUM_P (orig_regno))
1480 gcc_assert (df_regs_ever_live_p (orig_regno));
1482 /* For hard registers, we have to check hardware imposed
1483 limitations (frame/stack registers, calls crossed). */
1484 if (!TEST_HARD_REG_BIT (reg_rename_p->unavailable_hard_regs,
1485 orig_regno))
1487 /* Don't let register cross a call if it doesn't already
1488 cross one. This condition is written in accordance with
1489 that in sched-deps.c sched_analyze_reg(). */
1490 if (!reg_rename_p->crosses_call
1491 || REG_N_CALLS_CROSSED (orig_regno) > 0)
1492 return gen_rtx_REG (mode, orig_regno);
1495 bad_hard_regs = true;
1497 else
1498 return dest;
1501 *is_orig_reg_p_ptr = false;
1503 /* We had some original hard registers that couldn't be used.
1504 Those were likely special. Don't try to create a pseudo. */
1505 if (bad_hard_regs)
1506 return NULL_RTX;
1508 /* We haven't found a register from original operations. Get a new one.
1509 FIXME: control register pressure somehow. */
1511 rtx new_reg = gen_reg_rtx (mode);
1513 gcc_assert (mode != VOIDmode);
1515 max_regno = max_reg_num ();
1516 maybe_extend_reg_info_p ();
1517 REG_N_CALLS_CROSSED (REGNO (new_reg)) = reg_rename_p->crosses_call ? 1 : 0;
1519 return new_reg;
1523 /* True when target of EXPR is available due to EXPR_TARGET_AVAILABLE,
1524 USED_REGS and REG_RENAME_P->UNAVAILABLE_HARD_REGS. */
1525 static void
1526 verify_target_availability (expr_t expr, regset used_regs,
1527 struct reg_rename *reg_rename_p)
1529 unsigned n, i, regno;
1530 machine_mode mode;
1531 bool target_available, live_available, hard_available;
1533 if (!REG_P (EXPR_LHS (expr)) || EXPR_TARGET_AVAILABLE (expr) < 0)
1534 return;
1536 regno = expr_dest_regno (expr);
1537 mode = GET_MODE (EXPR_LHS (expr));
1538 target_available = EXPR_TARGET_AVAILABLE (expr) == 1;
1539 n = HARD_REGISTER_NUM_P (regno) ? hard_regno_nregs (regno, mode) : 1;
1541 live_available = hard_available = true;
1542 for (i = 0; i < n; i++)
1544 if (bitmap_bit_p (used_regs, regno + i))
1545 live_available = false;
1546 if (TEST_HARD_REG_BIT (reg_rename_p->unavailable_hard_regs, regno + i))
1547 hard_available = false;
1550 /* When target is not available, it may be due to hard register
1551 restrictions, e.g. crosses calls, so we check hard_available too. */
1552 if (target_available)
1553 gcc_assert (live_available);
1554 else
1555 /* Check only if we haven't scheduled something on the previous fence,
1556 cause due to MAX_SOFTWARE_LOOKAHEAD_WINDOW_SIZE issues
1557 and having more than one fence, we may end having targ_un in a block
1558 in which successors target register is actually available.
1560 The last condition handles the case when a dependence from a call insn
1561 was created in sched-deps.c for insns with destination registers that
1562 never crossed a call before, but do cross one after our code motion.
1564 FIXME: in the latter case, we just uselessly called find_used_regs,
1565 because we can't move this expression with any other register
1566 as well. */
1567 gcc_assert (scheduled_something_on_previous_fence || !live_available
1568 || !hard_available
1569 || (!reload_completed && reg_rename_p->crosses_call
1570 && REG_N_CALLS_CROSSED (regno) == 0));
1573 /* Collect unavailable registers due to liveness for EXPR from BNDS
1574 into USED_REGS. Save additional information about available
1575 registers and unavailable due to hardware restriction registers
1576 into REG_RENAME_P structure. Save original insns into ORIGINAL_INSNS
1577 list. */
1578 static void
1579 collect_unavailable_regs_from_bnds (expr_t expr, blist_t bnds, regset used_regs,
1580 struct reg_rename *reg_rename_p,
1581 def_list_t *original_insns)
1583 for (; bnds; bnds = BLIST_NEXT (bnds))
1585 bool res;
1586 av_set_t orig_ops = NULL;
1587 bnd_t bnd = BLIST_BND (bnds);
1589 /* If the chosen best expr doesn't belong to current boundary,
1590 skip it. */
1591 if (!av_set_is_in_p (BND_AV1 (bnd), EXPR_VINSN (expr)))
1592 continue;
1594 /* Put in ORIG_OPS all exprs from this boundary that became
1595 RES on top. */
1596 orig_ops = find_sequential_best_exprs (bnd, expr, false);
1598 /* Compute used regs and OR it into the USED_REGS. */
1599 res = find_used_regs (BND_TO (bnd), orig_ops, used_regs,
1600 reg_rename_p, original_insns);
1602 /* FIXME: the assert is true until we'd have several boundaries. */
1603 gcc_assert (res);
1604 av_set_clear (&orig_ops);
1608 /* Return TRUE if it is possible to replace LHSes of ORIG_INSNS with BEST_REG.
1609 If BEST_REG is valid, replace LHS of EXPR with it. */
1610 static bool
1611 try_replace_dest_reg (ilist_t orig_insns, rtx best_reg, expr_t expr)
1613 /* Try whether we'll be able to generate the insn
1614 'dest := best_reg' at the place of the original operation. */
1615 for (; orig_insns; orig_insns = ILIST_NEXT (orig_insns))
1617 insn_t orig_insn = DEF_LIST_DEF (orig_insns)->orig_insn;
1619 gcc_assert (EXPR_SEPARABLE_P (INSN_EXPR (orig_insn)));
1621 if (REGNO (best_reg) != REGNO (INSN_LHS (orig_insn))
1622 && (! replace_src_with_reg_ok_p (orig_insn, best_reg)
1623 || ! replace_dest_with_reg_ok_p (orig_insn, best_reg)))
1624 return false;
1627 /* Make sure that EXPR has the right destination
1628 register. */
1629 if (expr_dest_regno (expr) != REGNO (best_reg))
1630 replace_dest_with_reg_in_expr (expr, best_reg);
1631 else
1632 EXPR_TARGET_AVAILABLE (expr) = 1;
1634 return true;
1637 /* Select and assign best register to EXPR searching from BNDS.
1638 Set *IS_ORIG_REG_P to TRUE if original register was selected.
1639 Return FALSE if no register can be chosen, which could happen when:
1640 * EXPR_SEPARABLE_P is true but we were unable to find suitable register;
1641 * EXPR_SEPARABLE_P is false but the insn sets/clobbers one of the registers
1642 that are used on the moving path. */
1643 static bool
1644 find_best_reg_for_expr (expr_t expr, blist_t bnds, bool *is_orig_reg_p)
1646 static struct reg_rename reg_rename_data;
1648 regset used_regs;
1649 def_list_t original_insns = NULL;
1650 bool reg_ok;
1652 *is_orig_reg_p = false;
1654 /* Don't bother to do anything if this insn doesn't set any registers. */
1655 if (bitmap_empty_p (VINSN_REG_SETS (EXPR_VINSN (expr)))
1656 && bitmap_empty_p (VINSN_REG_CLOBBERS (EXPR_VINSN (expr))))
1657 return true;
1659 used_regs = get_clear_regset_from_pool ();
1660 CLEAR_HARD_REG_SET (reg_rename_data.unavailable_hard_regs);
1662 collect_unavailable_regs_from_bnds (expr, bnds, used_regs, &reg_rename_data,
1663 &original_insns);
1665 /* If after reload, make sure we're working with hard regs here. */
1666 if (flag_checking && reload_completed)
1668 reg_set_iterator rsi;
1669 unsigned i;
1671 EXECUTE_IF_SET_IN_REG_SET (used_regs, FIRST_PSEUDO_REGISTER, i, rsi)
1672 gcc_unreachable ();
1675 if (EXPR_SEPARABLE_P (expr))
1677 rtx best_reg = NULL_RTX;
1678 /* Check that we have computed availability of a target register
1679 correctly. */
1680 verify_target_availability (expr, used_regs, &reg_rename_data);
1682 /* Turn everything in hard regs after reload. */
1683 if (reload_completed)
1685 HARD_REG_SET hard_regs_used;
1686 REG_SET_TO_HARD_REG_SET (hard_regs_used, used_regs);
1688 /* Join hard registers unavailable due to register class
1689 restrictions and live range intersection. */
1690 IOR_HARD_REG_SET (hard_regs_used,
1691 reg_rename_data.unavailable_hard_regs);
1693 best_reg = choose_best_reg (hard_regs_used, &reg_rename_data,
1694 original_insns, is_orig_reg_p);
1696 else
1697 best_reg = choose_best_pseudo_reg (used_regs, &reg_rename_data,
1698 original_insns, is_orig_reg_p);
1700 if (!best_reg)
1701 reg_ok = false;
1702 else if (*is_orig_reg_p)
1704 /* In case of unification BEST_REG may be different from EXPR's LHS
1705 when EXPR's LHS is unavailable, and there is another LHS among
1706 ORIGINAL_INSNS. */
1707 reg_ok = try_replace_dest_reg (original_insns, best_reg, expr);
1709 else
1711 /* Forbid renaming of low-cost insns. */
1712 if (sel_vinsn_cost (EXPR_VINSN (expr)) < 2)
1713 reg_ok = false;
1714 else
1715 reg_ok = try_replace_dest_reg (original_insns, best_reg, expr);
1718 else
1720 /* If !EXPR_SCHEDULE_AS_RHS (EXPR), just make sure INSN doesn't set
1721 any of the HARD_REGS_USED set. */
1722 if (vinsn_writes_one_of_regs_p (EXPR_VINSN (expr), used_regs,
1723 reg_rename_data.unavailable_hard_regs))
1725 reg_ok = false;
1726 gcc_assert (EXPR_TARGET_AVAILABLE (expr) <= 0);
1728 else
1730 reg_ok = true;
1731 gcc_assert (EXPR_TARGET_AVAILABLE (expr) != 0);
1735 ilist_clear (&original_insns);
1736 return_regset_to_pool (used_regs);
1738 return reg_ok;
1742 /* Return true if dependence described by DS can be overcomed. */
1743 static bool
1744 can_speculate_dep_p (ds_t ds)
1746 if (spec_info == NULL)
1747 return false;
1749 /* Leave only speculative data. */
1750 ds &= SPECULATIVE;
1752 if (ds == 0)
1753 return false;
1756 /* FIXME: make sched-deps.c produce only those non-hard dependencies,
1757 that we can overcome. */
1758 ds_t spec_mask = spec_info->mask;
1760 if ((ds & spec_mask) != ds)
1761 return false;
1764 if (ds_weak (ds) < spec_info->data_weakness_cutoff)
1765 return false;
1767 return true;
1770 /* Get a speculation check instruction.
1771 C_EXPR is a speculative expression,
1772 CHECK_DS describes speculations that should be checked,
1773 ORIG_INSN is the original non-speculative insn in the stream. */
1774 static insn_t
1775 create_speculation_check (expr_t c_expr, ds_t check_ds, insn_t orig_insn)
1777 rtx check_pattern;
1778 rtx_insn *insn_rtx;
1779 insn_t insn;
1780 basic_block recovery_block;
1781 rtx_insn *label;
1783 /* Create a recovery block if target is going to emit branchy check, or if
1784 ORIG_INSN was speculative already. */
1785 if (targetm.sched.needs_block_p (check_ds)
1786 || EXPR_SPEC_DONE_DS (INSN_EXPR (orig_insn)) != 0)
1788 recovery_block = sel_create_recovery_block (orig_insn);
1789 label = BB_HEAD (recovery_block);
1791 else
1793 recovery_block = NULL;
1794 label = NULL;
1797 /* Get pattern of the check. */
1798 check_pattern = targetm.sched.gen_spec_check (EXPR_INSN_RTX (c_expr), label,
1799 check_ds);
1801 gcc_assert (check_pattern != NULL);
1803 /* Emit check. */
1804 insn_rtx = create_insn_rtx_from_pattern (check_pattern, label);
1806 insn = sel_gen_insn_from_rtx_after (insn_rtx, INSN_EXPR (orig_insn),
1807 INSN_SEQNO (orig_insn), orig_insn);
1809 /* Make check to be non-speculative. */
1810 EXPR_SPEC_DONE_DS (INSN_EXPR (insn)) = 0;
1811 INSN_SPEC_CHECKED_DS (insn) = check_ds;
1813 /* Decrease priority of check by difference of load/check instruction
1814 latencies. */
1815 EXPR_PRIORITY (INSN_EXPR (insn)) -= (sel_vinsn_cost (INSN_VINSN (orig_insn))
1816 - sel_vinsn_cost (INSN_VINSN (insn)));
1818 /* Emit copy of original insn (though with replaced target register,
1819 if needed) to the recovery block. */
1820 if (recovery_block != NULL)
1822 rtx twin_rtx;
1824 twin_rtx = copy_rtx (PATTERN (EXPR_INSN_RTX (c_expr)));
1825 twin_rtx = create_insn_rtx_from_pattern (twin_rtx, NULL_RTX);
1826 sel_gen_recovery_insn_from_rtx_after (twin_rtx,
1827 INSN_EXPR (orig_insn),
1828 INSN_SEQNO (insn),
1829 bb_note (recovery_block));
1832 /* If we've generated a data speculation check, make sure
1833 that all the bookkeeping instruction we'll create during
1834 this move_op () will allocate an ALAT entry so that the
1835 check won't fail.
1836 In case of control speculation we must convert C_EXPR to control
1837 speculative mode, because failing to do so will bring us an exception
1838 thrown by the non-control-speculative load. */
1839 check_ds = ds_get_max_dep_weak (check_ds);
1840 speculate_expr (c_expr, check_ds);
1842 return insn;
1845 /* True when INSN is a "regN = regN" copy. */
1846 static bool
1847 identical_copy_p (rtx_insn *insn)
1849 rtx lhs, rhs, pat;
1851 pat = PATTERN (insn);
1853 if (GET_CODE (pat) != SET)
1854 return false;
1856 lhs = SET_DEST (pat);
1857 if (!REG_P (lhs))
1858 return false;
1860 rhs = SET_SRC (pat);
1861 if (!REG_P (rhs))
1862 return false;
1864 return REGNO (lhs) == REGNO (rhs);
1867 /* Undo all transformations on *AV_PTR that were done when
1868 moving through INSN. */
1869 static void
1870 undo_transformations (av_set_t *av_ptr, rtx_insn *insn)
1872 av_set_iterator av_iter;
1873 expr_t expr;
1874 av_set_t new_set = NULL;
1876 /* First, kill any EXPR that uses registers set by an insn. This is
1877 required for correctness. */
1878 FOR_EACH_EXPR_1 (expr, av_iter, av_ptr)
1879 if (!sched_insns_conditions_mutex_p (insn, EXPR_INSN_RTX (expr))
1880 && bitmap_intersect_p (INSN_REG_SETS (insn),
1881 VINSN_REG_USES (EXPR_VINSN (expr)))
1882 /* When an insn looks like 'r1 = r1', we could substitute through
1883 it, but the above condition will still hold. This happened with
1884 gcc.c-torture/execute/961125-1.c. */
1885 && !identical_copy_p (insn))
1887 if (sched_verbose >= 6)
1888 sel_print ("Expr %d removed due to use/set conflict\n",
1889 INSN_UID (EXPR_INSN_RTX (expr)));
1890 av_set_iter_remove (&av_iter);
1893 /* Undo transformations looking at the history vector. */
1894 FOR_EACH_EXPR (expr, av_iter, *av_ptr)
1896 int index = find_in_history_vect (EXPR_HISTORY_OF_CHANGES (expr),
1897 insn, EXPR_VINSN (expr), true);
1899 if (index >= 0)
1901 expr_history_def *phist;
1903 phist = &EXPR_HISTORY_OF_CHANGES (expr)[index];
1905 switch (phist->type)
1907 case TRANS_SPECULATION:
1909 ds_t old_ds, new_ds;
1911 /* Compute the difference between old and new speculative
1912 statuses: that's what we need to check.
1913 Earlier we used to assert that the status will really
1914 change. This no longer works because only the probability
1915 bits in the status may have changed during compute_av_set,
1916 and in the case of merging different probabilities of the
1917 same speculative status along different paths we do not
1918 record this in the history vector. */
1919 old_ds = phist->spec_ds;
1920 new_ds = EXPR_SPEC_DONE_DS (expr);
1922 old_ds &= SPECULATIVE;
1923 new_ds &= SPECULATIVE;
1924 new_ds &= ~old_ds;
1926 EXPR_SPEC_TO_CHECK_DS (expr) |= new_ds;
1927 break;
1929 case TRANS_SUBSTITUTION:
1931 expr_def _tmp_expr, *tmp_expr = &_tmp_expr;
1932 vinsn_t new_vi;
1933 bool add = true;
1935 new_vi = phist->old_expr_vinsn;
1937 gcc_assert (VINSN_SEPARABLE_P (new_vi)
1938 == EXPR_SEPARABLE_P (expr));
1939 copy_expr (tmp_expr, expr);
1941 if (vinsn_equal_p (phist->new_expr_vinsn,
1942 EXPR_VINSN (tmp_expr)))
1943 change_vinsn_in_expr (tmp_expr, new_vi);
1944 else
1945 /* This happens when we're unsubstituting on a bookkeeping
1946 copy, which was in turn substituted. The history is wrong
1947 in this case. Do it the hard way. */
1948 add = substitute_reg_in_expr (tmp_expr, insn, true);
1949 if (add)
1950 av_set_add (&new_set, tmp_expr);
1951 clear_expr (tmp_expr);
1952 break;
1954 default:
1955 gcc_unreachable ();
1961 av_set_union_and_clear (av_ptr, &new_set, NULL);
1965 /* Moveup_* helpers for code motion and computing av sets. */
1967 /* Propagates EXPR inside an insn group through THROUGH_INSN.
1968 The difference from the below function is that only substitution is
1969 performed. */
1970 static enum MOVEUP_EXPR_CODE
1971 moveup_expr_inside_insn_group (expr_t expr, insn_t through_insn)
1973 vinsn_t vi = EXPR_VINSN (expr);
1974 ds_t *has_dep_p;
1975 ds_t full_ds;
1977 /* Do this only inside insn group. */
1978 gcc_assert (INSN_SCHED_CYCLE (through_insn) > 0);
1980 full_ds = has_dependence_p (expr, through_insn, &has_dep_p);
1981 if (full_ds == 0)
1982 return MOVEUP_EXPR_SAME;
1984 /* Substitution is the possible choice in this case. */
1985 if (has_dep_p[DEPS_IN_RHS])
1987 /* Can't substitute UNIQUE VINSNs. */
1988 gcc_assert (!VINSN_UNIQUE_P (vi));
1990 if (can_substitute_through_p (through_insn,
1991 has_dep_p[DEPS_IN_RHS])
1992 && substitute_reg_in_expr (expr, through_insn, false))
1994 EXPR_WAS_SUBSTITUTED (expr) = true;
1995 return MOVEUP_EXPR_CHANGED;
1998 /* Don't care about this, as even true dependencies may be allowed
1999 in an insn group. */
2000 return MOVEUP_EXPR_SAME;
2003 /* This can catch output dependencies in COND_EXECs. */
2004 if (has_dep_p[DEPS_IN_INSN])
2005 return MOVEUP_EXPR_NULL;
2007 /* This is either an output or an anti dependence, which usually have
2008 a zero latency. Allow this here, if we'd be wrong, tick_check_p
2009 will fix this. */
2010 gcc_assert (has_dep_p[DEPS_IN_LHS]);
2011 return MOVEUP_EXPR_AS_RHS;
2014 /* True when a trapping EXPR cannot be moved through THROUGH_INSN. */
2015 #define CANT_MOVE_TRAPPING(expr, through_insn) \
2016 (VINSN_MAY_TRAP_P (EXPR_VINSN (expr)) \
2017 && !sel_insn_has_single_succ_p ((through_insn), SUCCS_ALL) \
2018 && !sel_insn_is_speculation_check (through_insn))
2020 /* True when a conflict on a target register was found during moveup_expr. */
2021 static bool was_target_conflict = false;
2023 /* Return true when moving a debug INSN across THROUGH_INSN will
2024 create a bookkeeping block. We don't want to create such blocks,
2025 for they would cause codegen differences between compilations with
2026 and without debug info. */
2028 static bool
2029 moving_insn_creates_bookkeeping_block_p (insn_t insn,
2030 insn_t through_insn)
2032 basic_block bbi, bbt;
2033 edge e1, e2;
2034 edge_iterator ei1, ei2;
2036 if (!bookkeeping_can_be_created_if_moved_through_p (through_insn))
2038 if (sched_verbose >= 9)
2039 sel_print ("no bookkeeping required: ");
2040 return FALSE;
2043 bbi = BLOCK_FOR_INSN (insn);
2045 if (EDGE_COUNT (bbi->preds) == 1)
2047 if (sched_verbose >= 9)
2048 sel_print ("only one pred edge: ");
2049 return TRUE;
2052 bbt = BLOCK_FOR_INSN (through_insn);
2054 FOR_EACH_EDGE (e1, ei1, bbt->succs)
2056 FOR_EACH_EDGE (e2, ei2, bbi->preds)
2058 if (find_block_for_bookkeeping (e1, e2, TRUE))
2060 if (sched_verbose >= 9)
2061 sel_print ("found existing block: ");
2062 return FALSE;
2067 if (sched_verbose >= 9)
2068 sel_print ("would create bookkeeping block: ");
2070 return TRUE;
2073 /* Return true when the conflict with newly created implicit clobbers
2074 between EXPR and THROUGH_INSN is found because of renaming. */
2075 static bool
2076 implicit_clobber_conflict_p (insn_t through_insn, expr_t expr)
2078 HARD_REG_SET temp;
2079 rtx_insn *insn;
2080 rtx reg, rhs, pat;
2081 hard_reg_set_iterator hrsi;
2082 unsigned regno;
2083 bool valid;
2085 /* Make a new pseudo register. */
2086 reg = gen_reg_rtx (GET_MODE (EXPR_LHS (expr)));
2087 max_regno = max_reg_num ();
2088 maybe_extend_reg_info_p ();
2090 /* Validate a change and bail out early. */
2091 insn = EXPR_INSN_RTX (expr);
2092 validate_change (insn, &SET_DEST (PATTERN (insn)), reg, true);
2093 valid = verify_changes (0);
2094 cancel_changes (0);
2095 if (!valid)
2097 if (sched_verbose >= 6)
2098 sel_print ("implicit clobbers failed validation, ");
2099 return true;
2102 /* Make a new insn with it. */
2103 rhs = copy_rtx (VINSN_RHS (EXPR_VINSN (expr)));
2104 pat = gen_rtx_SET (reg, rhs);
2105 start_sequence ();
2106 insn = emit_insn (pat);
2107 end_sequence ();
2109 /* Calculate implicit clobbers. */
2110 extract_insn (insn);
2111 preprocess_constraints (insn);
2112 alternative_mask prefrred = get_preferred_alternatives (insn);
2113 ira_implicitly_set_insn_hard_regs (&temp, prefrred);
2114 AND_COMPL_HARD_REG_SET (temp, ira_no_alloc_regs);
2116 /* If any implicit clobber registers intersect with regular ones in
2117 through_insn, we have a dependency and thus bail out. */
2118 EXECUTE_IF_SET_IN_HARD_REG_SET (temp, 0, regno, hrsi)
2120 vinsn_t vi = INSN_VINSN (through_insn);
2121 if (bitmap_bit_p (VINSN_REG_SETS (vi), regno)
2122 || bitmap_bit_p (VINSN_REG_CLOBBERS (vi), regno)
2123 || bitmap_bit_p (VINSN_REG_USES (vi), regno))
2124 return true;
2127 return false;
2130 /* Modifies EXPR so it can be moved through the THROUGH_INSN,
2131 performing necessary transformations. Record the type of transformation
2132 made in PTRANS_TYPE, when it is not NULL. When INSIDE_INSN_GROUP,
2133 permit all dependencies except true ones, and try to remove those
2134 too via forward substitution. All cases when a non-eliminable
2135 non-zero cost dependency exists inside an insn group will be fixed
2136 in tick_check_p instead. */
2137 static enum MOVEUP_EXPR_CODE
2138 moveup_expr (expr_t expr, insn_t through_insn, bool inside_insn_group,
2139 enum local_trans_type *ptrans_type)
2141 vinsn_t vi = EXPR_VINSN (expr);
2142 insn_t insn = VINSN_INSN_RTX (vi);
2143 bool was_changed = false;
2144 bool as_rhs = false;
2145 ds_t *has_dep_p;
2146 ds_t full_ds;
2148 /* ??? We use dependencies of non-debug insns on debug insns to
2149 indicate that the debug insns need to be reset if the non-debug
2150 insn is pulled ahead of it. It's hard to figure out how to
2151 introduce such a notion in sel-sched, but it already fails to
2152 support debug insns in other ways, so we just go ahead and
2153 let the deug insns go corrupt for now. */
2154 if (DEBUG_INSN_P (through_insn) && !DEBUG_INSN_P (insn))
2155 return MOVEUP_EXPR_SAME;
2157 /* When inside_insn_group, delegate to the helper. */
2158 if (inside_insn_group)
2159 return moveup_expr_inside_insn_group (expr, through_insn);
2161 /* Deal with unique insns and control dependencies. */
2162 if (VINSN_UNIQUE_P (vi))
2164 /* We can move jumps without side-effects or jumps that are
2165 mutually exclusive with instruction THROUGH_INSN (all in cases
2166 dependencies allow to do so and jump is not speculative). */
2167 if (control_flow_insn_p (insn))
2169 basic_block fallthru_bb;
2171 /* Do not move checks and do not move jumps through other
2172 jumps. */
2173 if (control_flow_insn_p (through_insn)
2174 || sel_insn_is_speculation_check (insn))
2175 return MOVEUP_EXPR_NULL;
2177 /* Don't move jumps through CFG joins. */
2178 if (bookkeeping_can_be_created_if_moved_through_p (through_insn))
2179 return MOVEUP_EXPR_NULL;
2181 /* The jump should have a clear fallthru block, and
2182 this block should be in the current region. */
2183 if ((fallthru_bb = fallthru_bb_of_jump (insn)) == NULL
2184 || ! in_current_region_p (fallthru_bb))
2185 return MOVEUP_EXPR_NULL;
2187 /* And it should be mutually exclusive with through_insn. */
2188 if (! sched_insns_conditions_mutex_p (insn, through_insn)
2189 && ! DEBUG_INSN_P (through_insn))
2190 return MOVEUP_EXPR_NULL;
2193 /* Don't move what we can't move. */
2194 if (EXPR_CANT_MOVE (expr)
2195 && BLOCK_FOR_INSN (through_insn) != BLOCK_FOR_INSN (insn))
2196 return MOVEUP_EXPR_NULL;
2198 /* Don't move SCHED_GROUP instruction through anything.
2199 If we don't force this, then it will be possible to start
2200 scheduling a sched_group before all its dependencies are
2201 resolved.
2202 ??? Haifa deals with this issue by delaying the SCHED_GROUP
2203 as late as possible through rank_for_schedule. */
2204 if (SCHED_GROUP_P (insn))
2205 return MOVEUP_EXPR_NULL;
2207 else
2208 gcc_assert (!control_flow_insn_p (insn));
2210 /* Don't move debug insns if this would require bookkeeping. */
2211 if (DEBUG_INSN_P (insn)
2212 && BLOCK_FOR_INSN (through_insn) != BLOCK_FOR_INSN (insn)
2213 && moving_insn_creates_bookkeeping_block_p (insn, through_insn))
2214 return MOVEUP_EXPR_NULL;
2216 /* Deal with data dependencies. */
2217 was_target_conflict = false;
2218 full_ds = has_dependence_p (expr, through_insn, &has_dep_p);
2219 if (full_ds == 0)
2221 if (!CANT_MOVE_TRAPPING (expr, through_insn))
2222 return MOVEUP_EXPR_SAME;
2224 else
2226 /* We can move UNIQUE insn up only as a whole and unchanged,
2227 so it shouldn't have any dependencies. */
2228 if (VINSN_UNIQUE_P (vi))
2229 return MOVEUP_EXPR_NULL;
2232 if (full_ds != 0 && can_speculate_dep_p (full_ds))
2234 int res;
2236 res = speculate_expr (expr, full_ds);
2237 if (res >= 0)
2239 /* Speculation was successful. */
2240 full_ds = 0;
2241 was_changed = (res > 0);
2242 if (res == 2)
2243 was_target_conflict = true;
2244 if (ptrans_type)
2245 *ptrans_type = TRANS_SPECULATION;
2246 sel_clear_has_dependence ();
2250 if (has_dep_p[DEPS_IN_INSN])
2251 /* We have some dependency that cannot be discarded. */
2252 return MOVEUP_EXPR_NULL;
2254 if (has_dep_p[DEPS_IN_LHS])
2256 /* Only separable insns can be moved up with the new register.
2257 Anyways, we should mark that the original register is
2258 unavailable. */
2259 if (!enable_schedule_as_rhs_p || !EXPR_SEPARABLE_P (expr))
2260 return MOVEUP_EXPR_NULL;
2262 /* When renaming a hard register to a pseudo before reload, extra
2263 dependencies can occur from the implicit clobbers of the insn.
2264 Filter out such cases here. */
2265 if (!reload_completed && REG_P (EXPR_LHS (expr))
2266 && HARD_REGISTER_P (EXPR_LHS (expr))
2267 && implicit_clobber_conflict_p (through_insn, expr))
2269 if (sched_verbose >= 6)
2270 sel_print ("implicit clobbers conflict detected, ");
2271 return MOVEUP_EXPR_NULL;
2273 EXPR_TARGET_AVAILABLE (expr) = false;
2274 was_target_conflict = true;
2275 as_rhs = true;
2278 /* At this point we have either separable insns, that will be lifted
2279 up only as RHSes, or non-separable insns with no dependency in lhs.
2280 If dependency is in RHS, then try to perform substitution and move up
2281 substituted RHS:
2283 Ex. 1: Ex.2
2284 y = x; y = x;
2285 z = y*2; y = y*2;
2287 In Ex.1 y*2 can be substituted for x*2 and the whole operation can be
2288 moved above y=x assignment as z=x*2.
2290 In Ex.2 y*2 also can be substituted for x*2, but only the right hand
2291 side can be moved because of the output dependency. The operation was
2292 cropped to its rhs above. */
2293 if (has_dep_p[DEPS_IN_RHS])
2295 ds_t *rhs_dsp = &has_dep_p[DEPS_IN_RHS];
2297 /* Can't substitute UNIQUE VINSNs. */
2298 gcc_assert (!VINSN_UNIQUE_P (vi));
2300 if (can_speculate_dep_p (*rhs_dsp))
2302 int res;
2304 res = speculate_expr (expr, *rhs_dsp);
2305 if (res >= 0)
2307 /* Speculation was successful. */
2308 *rhs_dsp = 0;
2309 was_changed = (res > 0);
2310 if (res == 2)
2311 was_target_conflict = true;
2312 if (ptrans_type)
2313 *ptrans_type = TRANS_SPECULATION;
2315 else
2316 return MOVEUP_EXPR_NULL;
2318 else if (can_substitute_through_p (through_insn,
2319 *rhs_dsp)
2320 && substitute_reg_in_expr (expr, through_insn, false))
2322 /* ??? We cannot perform substitution AND speculation on the same
2323 insn. */
2324 gcc_assert (!was_changed);
2325 was_changed = true;
2326 if (ptrans_type)
2327 *ptrans_type = TRANS_SUBSTITUTION;
2328 EXPR_WAS_SUBSTITUTED (expr) = true;
2330 else
2331 return MOVEUP_EXPR_NULL;
2334 /* Don't move trapping insns through jumps.
2335 This check should be at the end to give a chance to control speculation
2336 to perform its duties. */
2337 if (CANT_MOVE_TRAPPING (expr, through_insn))
2338 return MOVEUP_EXPR_NULL;
2340 return (was_changed
2341 ? MOVEUP_EXPR_CHANGED
2342 : (as_rhs
2343 ? MOVEUP_EXPR_AS_RHS
2344 : MOVEUP_EXPR_SAME));
2347 /* Try to look at bitmap caches for EXPR and INSN pair, return true
2348 if successful. When INSIDE_INSN_GROUP, also try ignore dependencies
2349 that can exist within a parallel group. Write to RES the resulting
2350 code for moveup_expr. */
2351 static bool
2352 try_bitmap_cache (expr_t expr, insn_t insn,
2353 bool inside_insn_group,
2354 enum MOVEUP_EXPR_CODE *res)
2356 int expr_uid = INSN_UID (EXPR_INSN_RTX (expr));
2358 /* First check whether we've analyzed this situation already. */
2359 if (bitmap_bit_p (INSN_ANALYZED_DEPS (insn), expr_uid))
2361 if (bitmap_bit_p (INSN_FOUND_DEPS (insn), expr_uid))
2363 if (sched_verbose >= 6)
2364 sel_print ("removed (cached)\n");
2365 *res = MOVEUP_EXPR_NULL;
2366 return true;
2368 else
2370 if (sched_verbose >= 6)
2371 sel_print ("unchanged (cached)\n");
2372 *res = MOVEUP_EXPR_SAME;
2373 return true;
2376 else if (bitmap_bit_p (INSN_FOUND_DEPS (insn), expr_uid))
2378 if (inside_insn_group)
2380 if (sched_verbose >= 6)
2381 sel_print ("unchanged (as RHS, cached, inside insn group)\n");
2382 *res = MOVEUP_EXPR_SAME;
2383 return true;
2386 else
2387 EXPR_TARGET_AVAILABLE (expr) = false;
2389 /* This is the only case when propagation result can change over time,
2390 as we can dynamically switch off scheduling as RHS. In this case,
2391 just check the flag to reach the correct decision. */
2392 if (enable_schedule_as_rhs_p)
2394 if (sched_verbose >= 6)
2395 sel_print ("unchanged (as RHS, cached)\n");
2396 *res = MOVEUP_EXPR_AS_RHS;
2397 return true;
2399 else
2401 if (sched_verbose >= 6)
2402 sel_print ("removed (cached as RHS, but renaming"
2403 " is now disabled)\n");
2404 *res = MOVEUP_EXPR_NULL;
2405 return true;
2409 return false;
2412 /* Try to look at bitmap caches for EXPR and INSN pair, return true
2413 if successful. Write to RES the resulting code for moveup_expr. */
2414 static bool
2415 try_transformation_cache (expr_t expr, insn_t insn,
2416 enum MOVEUP_EXPR_CODE *res)
2418 struct transformed_insns *pti
2419 = (struct transformed_insns *)
2420 htab_find_with_hash (INSN_TRANSFORMED_INSNS (insn),
2421 &EXPR_VINSN (expr),
2422 VINSN_HASH_RTX (EXPR_VINSN (expr)));
2423 if (pti)
2425 /* This EXPR was already moved through this insn and was
2426 changed as a result. Fetch the proper data from
2427 the hashtable. */
2428 insert_in_history_vect (&EXPR_HISTORY_OF_CHANGES (expr),
2429 INSN_UID (insn), pti->type,
2430 pti->vinsn_old, pti->vinsn_new,
2431 EXPR_SPEC_DONE_DS (expr));
2433 if (INSN_IN_STREAM_P (VINSN_INSN_RTX (pti->vinsn_new)))
2434 pti->vinsn_new = vinsn_copy (pti->vinsn_new, true);
2435 change_vinsn_in_expr (expr, pti->vinsn_new);
2436 if (pti->was_target_conflict)
2437 EXPR_TARGET_AVAILABLE (expr) = false;
2438 if (pti->type == TRANS_SPECULATION)
2440 EXPR_SPEC_DONE_DS (expr) = pti->ds;
2441 EXPR_NEEDS_SPEC_CHECK_P (expr) |= pti->needs_check;
2444 if (sched_verbose >= 6)
2446 sel_print ("changed (cached): ");
2447 dump_expr (expr);
2448 sel_print ("\n");
2451 *res = MOVEUP_EXPR_CHANGED;
2452 return true;
2455 return false;
2458 /* Update bitmap caches on INSN with result RES of propagating EXPR. */
2459 static void
2460 update_bitmap_cache (expr_t expr, insn_t insn, bool inside_insn_group,
2461 enum MOVEUP_EXPR_CODE res)
2463 int expr_uid = INSN_UID (EXPR_INSN_RTX (expr));
2465 /* Do not cache result of propagating jumps through an insn group,
2466 as it is always true, which is not useful outside the group. */
2467 if (inside_insn_group)
2468 return;
2470 if (res == MOVEUP_EXPR_NULL)
2472 bitmap_set_bit (INSN_ANALYZED_DEPS (insn), expr_uid);
2473 bitmap_set_bit (INSN_FOUND_DEPS (insn), expr_uid);
2475 else if (res == MOVEUP_EXPR_SAME)
2477 bitmap_set_bit (INSN_ANALYZED_DEPS (insn), expr_uid);
2478 bitmap_clear_bit (INSN_FOUND_DEPS (insn), expr_uid);
2480 else if (res == MOVEUP_EXPR_AS_RHS)
2482 bitmap_clear_bit (INSN_ANALYZED_DEPS (insn), expr_uid);
2483 bitmap_set_bit (INSN_FOUND_DEPS (insn), expr_uid);
2485 else
2486 gcc_unreachable ();
2489 /* Update hashtable on INSN with changed EXPR, old EXPR_OLD_VINSN
2490 and transformation type TRANS_TYPE. */
2491 static void
2492 update_transformation_cache (expr_t expr, insn_t insn,
2493 bool inside_insn_group,
2494 enum local_trans_type trans_type,
2495 vinsn_t expr_old_vinsn)
2497 struct transformed_insns *pti;
2499 if (inside_insn_group)
2500 return;
2502 pti = XNEW (struct transformed_insns);
2503 pti->vinsn_old = expr_old_vinsn;
2504 pti->vinsn_new = EXPR_VINSN (expr);
2505 pti->type = trans_type;
2506 pti->was_target_conflict = was_target_conflict;
2507 pti->ds = EXPR_SPEC_DONE_DS (expr);
2508 pti->needs_check = EXPR_NEEDS_SPEC_CHECK_P (expr);
2509 vinsn_attach (pti->vinsn_old);
2510 vinsn_attach (pti->vinsn_new);
2511 *((struct transformed_insns **)
2512 htab_find_slot_with_hash (INSN_TRANSFORMED_INSNS (insn),
2513 pti, VINSN_HASH_RTX (expr_old_vinsn),
2514 INSERT)) = pti;
2517 /* Same as moveup_expr, but first looks up the result of
2518 transformation in caches. */
2519 static enum MOVEUP_EXPR_CODE
2520 moveup_expr_cached (expr_t expr, insn_t insn, bool inside_insn_group)
2522 enum MOVEUP_EXPR_CODE res;
2523 bool got_answer = false;
2525 if (sched_verbose >= 6)
2527 sel_print ("Moving ");
2528 dump_expr (expr);
2529 sel_print (" through %d: ", INSN_UID (insn));
2532 if (DEBUG_INSN_P (EXPR_INSN_RTX (expr))
2533 && BLOCK_FOR_INSN (EXPR_INSN_RTX (expr))
2534 && (sel_bb_head (BLOCK_FOR_INSN (EXPR_INSN_RTX (expr)))
2535 == EXPR_INSN_RTX (expr)))
2536 /* Don't use cached information for debug insns that are heads of
2537 basic blocks. */;
2538 else if (try_bitmap_cache (expr, insn, inside_insn_group, &res))
2539 /* When inside insn group, we do not want remove stores conflicting
2540 with previosly issued loads. */
2541 got_answer = ! inside_insn_group || res != MOVEUP_EXPR_NULL;
2542 else if (try_transformation_cache (expr, insn, &res))
2543 got_answer = true;
2545 if (! got_answer)
2547 /* Invoke moveup_expr and record the results. */
2548 vinsn_t expr_old_vinsn = EXPR_VINSN (expr);
2549 ds_t expr_old_spec_ds = EXPR_SPEC_DONE_DS (expr);
2550 int expr_uid = INSN_UID (VINSN_INSN_RTX (expr_old_vinsn));
2551 bool unique_p = VINSN_UNIQUE_P (expr_old_vinsn);
2552 enum local_trans_type trans_type = TRANS_SUBSTITUTION;
2554 /* ??? Invent something better than this. We can't allow old_vinsn
2555 to go, we need it for the history vector. */
2556 vinsn_attach (expr_old_vinsn);
2558 res = moveup_expr (expr, insn, inside_insn_group,
2559 &trans_type);
2560 switch (res)
2562 case MOVEUP_EXPR_NULL:
2563 update_bitmap_cache (expr, insn, inside_insn_group, res);
2564 if (sched_verbose >= 6)
2565 sel_print ("removed\n");
2566 break;
2568 case MOVEUP_EXPR_SAME:
2569 update_bitmap_cache (expr, insn, inside_insn_group, res);
2570 if (sched_verbose >= 6)
2571 sel_print ("unchanged\n");
2572 break;
2574 case MOVEUP_EXPR_AS_RHS:
2575 gcc_assert (!unique_p || inside_insn_group);
2576 update_bitmap_cache (expr, insn, inside_insn_group, res);
2577 if (sched_verbose >= 6)
2578 sel_print ("unchanged (as RHS)\n");
2579 break;
2581 case MOVEUP_EXPR_CHANGED:
2582 gcc_assert (INSN_UID (EXPR_INSN_RTX (expr)) != expr_uid
2583 || EXPR_SPEC_DONE_DS (expr) != expr_old_spec_ds);
2584 insert_in_history_vect (&EXPR_HISTORY_OF_CHANGES (expr),
2585 INSN_UID (insn), trans_type,
2586 expr_old_vinsn, EXPR_VINSN (expr),
2587 expr_old_spec_ds);
2588 update_transformation_cache (expr, insn, inside_insn_group,
2589 trans_type, expr_old_vinsn);
2590 if (sched_verbose >= 6)
2592 sel_print ("changed: ");
2593 dump_expr (expr);
2594 sel_print ("\n");
2596 break;
2597 default:
2598 gcc_unreachable ();
2601 vinsn_detach (expr_old_vinsn);
2604 return res;
2607 /* Moves an av set AVP up through INSN, performing necessary
2608 transformations. */
2609 static void
2610 moveup_set_expr (av_set_t *avp, insn_t insn, bool inside_insn_group)
2612 av_set_iterator i;
2613 expr_t expr;
2615 FOR_EACH_EXPR_1 (expr, i, avp)
2618 switch (moveup_expr_cached (expr, insn, inside_insn_group))
2620 case MOVEUP_EXPR_SAME:
2621 case MOVEUP_EXPR_AS_RHS:
2622 break;
2624 case MOVEUP_EXPR_NULL:
2625 av_set_iter_remove (&i);
2626 break;
2628 case MOVEUP_EXPR_CHANGED:
2629 expr = merge_with_other_exprs (avp, &i, expr);
2630 break;
2632 default:
2633 gcc_unreachable ();
2638 /* Moves AVP set along PATH. */
2639 static void
2640 moveup_set_inside_insn_group (av_set_t *avp, ilist_t path)
2642 int last_cycle;
2644 if (sched_verbose >= 6)
2645 sel_print ("Moving expressions up in the insn group...\n");
2646 if (! path)
2647 return;
2648 last_cycle = INSN_SCHED_CYCLE (ILIST_INSN (path));
2649 while (path
2650 && INSN_SCHED_CYCLE (ILIST_INSN (path)) == last_cycle)
2652 moveup_set_expr (avp, ILIST_INSN (path), true);
2653 path = ILIST_NEXT (path);
2657 /* Returns true if after moving EXPR along PATH it equals to EXPR_VLIW. */
2658 static bool
2659 equal_after_moveup_path_p (expr_t expr, ilist_t path, expr_t expr_vliw)
2661 expr_def _tmp, *tmp = &_tmp;
2662 int last_cycle;
2663 bool res = true;
2665 copy_expr_onside (tmp, expr);
2666 last_cycle = path ? INSN_SCHED_CYCLE (ILIST_INSN (path)) : 0;
2667 while (path
2668 && res
2669 && INSN_SCHED_CYCLE (ILIST_INSN (path)) == last_cycle)
2671 res = (moveup_expr_cached (tmp, ILIST_INSN (path), true)
2672 != MOVEUP_EXPR_NULL);
2673 path = ILIST_NEXT (path);
2676 if (res)
2678 vinsn_t tmp_vinsn = EXPR_VINSN (tmp);
2679 vinsn_t expr_vliw_vinsn = EXPR_VINSN (expr_vliw);
2681 if (tmp_vinsn != expr_vliw_vinsn)
2682 res = vinsn_equal_p (tmp_vinsn, expr_vliw_vinsn);
2685 clear_expr (tmp);
2686 return res;
2690 /* Functions that compute av and lv sets. */
2692 /* Returns true if INSN is not a downward continuation of the given path P in
2693 the current stage. */
2694 static bool
2695 is_ineligible_successor (insn_t insn, ilist_t p)
2697 insn_t prev_insn;
2699 /* Check if insn is not deleted. */
2700 if (PREV_INSN (insn) && NEXT_INSN (PREV_INSN (insn)) != insn)
2701 gcc_unreachable ();
2702 else if (NEXT_INSN (insn) && PREV_INSN (NEXT_INSN (insn)) != insn)
2703 gcc_unreachable ();
2705 /* If it's the first insn visited, then the successor is ok. */
2706 if (!p)
2707 return false;
2709 prev_insn = ILIST_INSN (p);
2711 if (/* a backward edge. */
2712 INSN_SEQNO (insn) < INSN_SEQNO (prev_insn)
2713 /* is already visited. */
2714 || (INSN_SEQNO (insn) == INSN_SEQNO (prev_insn)
2715 && (ilist_is_in_p (p, insn)
2716 /* We can reach another fence here and still seqno of insn
2717 would be equal to seqno of prev_insn. This is possible
2718 when prev_insn is a previously created bookkeeping copy.
2719 In that case it'd get a seqno of insn. Thus, check here
2720 whether insn is in current fence too. */
2721 || IN_CURRENT_FENCE_P (insn)))
2722 /* Was already scheduled on this round. */
2723 || (INSN_SEQNO (insn) > INSN_SEQNO (prev_insn)
2724 && IN_CURRENT_FENCE_P (insn))
2725 /* An insn from another fence could also be
2726 scheduled earlier even if this insn is not in
2727 a fence list right now. Check INSN_SCHED_CYCLE instead. */
2728 || (!pipelining_p
2729 && INSN_SCHED_TIMES (insn) > 0))
2730 return true;
2731 else
2732 return false;
2735 /* Computes the av_set below the last bb insn INSN, doing all the 'dirty work'
2736 of handling multiple successors and properly merging its av_sets. P is
2737 the current path traversed. WS is the size of lookahead window.
2738 Return the av set computed. */
2739 static av_set_t
2740 compute_av_set_at_bb_end (insn_t insn, ilist_t p, int ws)
2742 struct succs_info *sinfo;
2743 av_set_t expr_in_all_succ_branches = NULL;
2744 int is;
2745 insn_t succ, zero_succ = NULL;
2746 av_set_t av1 = NULL;
2748 gcc_assert (sel_bb_end_p (insn));
2750 /* Find different kind of successors needed for correct computing of
2751 SPEC and TARGET_AVAILABLE attributes. */
2752 sinfo = compute_succs_info (insn, SUCCS_NORMAL);
2754 /* Debug output. */
2755 if (sched_verbose >= 6)
2757 sel_print ("successors of bb end (%d): ", INSN_UID (insn));
2758 dump_insn_vector (sinfo->succs_ok);
2759 sel_print ("\n");
2760 if (sinfo->succs_ok_n != sinfo->all_succs_n)
2761 sel_print ("real successors num: %d\n", sinfo->all_succs_n);
2764 /* Add insn to the tail of current path. */
2765 ilist_add (&p, insn);
2767 FOR_EACH_VEC_ELT (sinfo->succs_ok, is, succ)
2769 av_set_t succ_set;
2771 /* We will edit SUCC_SET and EXPR_SPEC field of its elements. */
2772 succ_set = compute_av_set_inside_bb (succ, p, ws, true);
2774 av_set_split_usefulness (succ_set,
2775 sinfo->probs_ok[is],
2776 sinfo->all_prob);
2778 if (sinfo->all_succs_n > 1)
2780 /* Find EXPR'es that came from *all* successors and save them
2781 into expr_in_all_succ_branches. This set will be used later
2782 for calculating speculation attributes of EXPR'es. */
2783 if (is == 0)
2785 expr_in_all_succ_branches = av_set_copy (succ_set);
2787 /* Remember the first successor for later. */
2788 zero_succ = succ;
2790 else
2792 av_set_iterator i;
2793 expr_t expr;
2795 FOR_EACH_EXPR_1 (expr, i, &expr_in_all_succ_branches)
2796 if (!av_set_is_in_p (succ_set, EXPR_VINSN (expr)))
2797 av_set_iter_remove (&i);
2801 /* Union the av_sets. Check liveness restrictions on target registers
2802 in special case of two successors. */
2803 if (sinfo->succs_ok_n == 2 && is == 1)
2805 basic_block bb0 = BLOCK_FOR_INSN (zero_succ);
2806 basic_block bb1 = BLOCK_FOR_INSN (succ);
2808 gcc_assert (BB_LV_SET_VALID_P (bb0) && BB_LV_SET_VALID_P (bb1));
2809 av_set_union_and_live (&av1, &succ_set,
2810 BB_LV_SET (bb0),
2811 BB_LV_SET (bb1),
2812 insn);
2814 else
2815 av_set_union_and_clear (&av1, &succ_set, insn);
2818 /* Check liveness restrictions via hard way when there are more than
2819 two successors. */
2820 if (sinfo->succs_ok_n > 2)
2821 FOR_EACH_VEC_ELT (sinfo->succs_ok, is, succ)
2823 basic_block succ_bb = BLOCK_FOR_INSN (succ);
2825 gcc_assert (BB_LV_SET_VALID_P (succ_bb));
2826 mark_unavailable_targets (av1, BB_AV_SET (succ_bb),
2827 BB_LV_SET (succ_bb));
2830 /* Finally, check liveness restrictions on paths leaving the region. */
2831 if (sinfo->all_succs_n > sinfo->succs_ok_n)
2832 FOR_EACH_VEC_ELT (sinfo->succs_other, is, succ)
2833 mark_unavailable_targets
2834 (av1, NULL, BB_LV_SET (BLOCK_FOR_INSN (succ)));
2836 if (sinfo->all_succs_n > 1)
2838 av_set_iterator i;
2839 expr_t expr;
2841 /* Increase the spec attribute of all EXPR'es that didn't come
2842 from all successors. */
2843 FOR_EACH_EXPR (expr, i, av1)
2844 if (!av_set_is_in_p (expr_in_all_succ_branches, EXPR_VINSN (expr)))
2845 EXPR_SPEC (expr)++;
2847 av_set_clear (&expr_in_all_succ_branches);
2849 /* Do not move conditional branches through other
2850 conditional branches. So, remove all conditional
2851 branches from av_set if current operator is a conditional
2852 branch. */
2853 av_set_substract_cond_branches (&av1);
2856 ilist_remove (&p);
2857 free_succs_info (sinfo);
2859 if (sched_verbose >= 6)
2861 sel_print ("av_succs (%d): ", INSN_UID (insn));
2862 dump_av_set (av1);
2863 sel_print ("\n");
2866 return av1;
2869 /* This function computes av_set for the FIRST_INSN by dragging valid
2870 av_set through all basic block insns either from the end of basic block
2871 (computed using compute_av_set_at_bb_end) or from the insn on which
2872 MAX_WS was exceeded. It uses compute_av_set_at_bb_end to compute av_set
2873 below the basic block and handling conditional branches.
2874 FIRST_INSN - the basic block head, P - path consisting of the insns
2875 traversed on the way to the FIRST_INSN (the path is sparse, only bb heads
2876 and bb ends are added to the path), WS - current window size,
2877 NEED_COPY_P - true if we'll make a copy of av_set before returning it. */
2878 static av_set_t
2879 compute_av_set_inside_bb (insn_t first_insn, ilist_t p, int ws,
2880 bool need_copy_p)
2882 insn_t cur_insn;
2883 int end_ws = ws;
2884 insn_t bb_end = sel_bb_end (BLOCK_FOR_INSN (first_insn));
2885 insn_t after_bb_end = NEXT_INSN (bb_end);
2886 insn_t last_insn;
2887 av_set_t av = NULL;
2888 basic_block cur_bb = BLOCK_FOR_INSN (first_insn);
2890 /* Return NULL if insn is not on the legitimate downward path. */
2891 if (is_ineligible_successor (first_insn, p))
2893 if (sched_verbose >= 6)
2894 sel_print ("Insn %d is ineligible_successor\n", INSN_UID (first_insn));
2896 return NULL;
2899 /* If insn already has valid av(insn) computed, just return it. */
2900 if (AV_SET_VALID_P (first_insn))
2902 av_set_t av_set;
2904 if (sel_bb_head_p (first_insn))
2905 av_set = BB_AV_SET (BLOCK_FOR_INSN (first_insn));
2906 else
2907 av_set = NULL;
2909 if (sched_verbose >= 6)
2911 sel_print ("Insn %d has a valid av set: ", INSN_UID (first_insn));
2912 dump_av_set (av_set);
2913 sel_print ("\n");
2916 return need_copy_p ? av_set_copy (av_set) : av_set;
2919 ilist_add (&p, first_insn);
2921 /* As the result after this loop have completed, in LAST_INSN we'll
2922 have the insn which has valid av_set to start backward computation
2923 from: it either will be NULL because on it the window size was exceeded
2924 or other valid av_set as returned by compute_av_set for the last insn
2925 of the basic block. */
2926 for (last_insn = first_insn; last_insn != after_bb_end;
2927 last_insn = NEXT_INSN (last_insn))
2929 /* We may encounter valid av_set not only on bb_head, but also on
2930 those insns on which previously MAX_WS was exceeded. */
2931 if (AV_SET_VALID_P (last_insn))
2933 if (sched_verbose >= 6)
2934 sel_print ("Insn %d has a valid empty av set\n", INSN_UID (last_insn));
2935 break;
2938 /* The special case: the last insn of the BB may be an
2939 ineligible_successor due to its SEQ_NO that was set on
2940 it as a bookkeeping. */
2941 if (last_insn != first_insn
2942 && is_ineligible_successor (last_insn, p))
2944 if (sched_verbose >= 6)
2945 sel_print ("Insn %d is ineligible_successor\n", INSN_UID (last_insn));
2946 break;
2949 if (DEBUG_INSN_P (last_insn))
2950 continue;
2952 if (end_ws > max_ws)
2954 /* We can reach max lookahead size at bb_header, so clean av_set
2955 first. */
2956 INSN_WS_LEVEL (last_insn) = global_level;
2958 if (sched_verbose >= 6)
2959 sel_print ("Insn %d is beyond the software lookahead window size\n",
2960 INSN_UID (last_insn));
2961 break;
2964 end_ws++;
2967 /* Get the valid av_set into AV above the LAST_INSN to start backward
2968 computation from. It either will be empty av_set or av_set computed from
2969 the successors on the last insn of the current bb. */
2970 if (last_insn != after_bb_end)
2972 av = NULL;
2974 /* This is needed only to obtain av_sets that are identical to
2975 those computed by the old compute_av_set version. */
2976 if (last_insn == first_insn && !INSN_NOP_P (last_insn))
2977 av_set_add (&av, INSN_EXPR (last_insn));
2979 else
2980 /* END_WS is always already increased by 1 if LAST_INSN == AFTER_BB_END. */
2981 av = compute_av_set_at_bb_end (bb_end, p, end_ws);
2983 /* Compute av_set in AV starting from below the LAST_INSN up to
2984 location above the FIRST_INSN. */
2985 for (cur_insn = PREV_INSN (last_insn); cur_insn != PREV_INSN (first_insn);
2986 cur_insn = PREV_INSN (cur_insn))
2987 if (!INSN_NOP_P (cur_insn))
2989 expr_t expr;
2991 moveup_set_expr (&av, cur_insn, false);
2993 /* If the expression for CUR_INSN is already in the set,
2994 replace it by the new one. */
2995 expr = av_set_lookup (av, INSN_VINSN (cur_insn));
2996 if (expr != NULL)
2998 clear_expr (expr);
2999 copy_expr (expr, INSN_EXPR (cur_insn));
3001 else
3002 av_set_add (&av, INSN_EXPR (cur_insn));
3005 /* Clear stale bb_av_set. */
3006 if (sel_bb_head_p (first_insn))
3008 av_set_clear (&BB_AV_SET (cur_bb));
3009 BB_AV_SET (cur_bb) = need_copy_p ? av_set_copy (av) : av;
3010 BB_AV_LEVEL (cur_bb) = global_level;
3013 if (sched_verbose >= 6)
3015 sel_print ("Computed av set for insn %d: ", INSN_UID (first_insn));
3016 dump_av_set (av);
3017 sel_print ("\n");
3020 ilist_remove (&p);
3021 return av;
3024 /* Compute av set before INSN.
3025 INSN - the current operation (actual rtx INSN)
3026 P - the current path, which is list of insns visited so far
3027 WS - software lookahead window size.
3028 UNIQUE_P - TRUE, if returned av_set will be changed, hence
3029 if we want to save computed av_set in s_i_d, we should make a copy of it.
3031 In the resulting set we will have only expressions that don't have delay
3032 stalls and nonsubstitutable dependences. */
3033 static av_set_t
3034 compute_av_set (insn_t insn, ilist_t p, int ws, bool unique_p)
3036 return compute_av_set_inside_bb (insn, p, ws, unique_p);
3039 /* Propagate a liveness set LV through INSN. */
3040 static void
3041 propagate_lv_set (regset lv, insn_t insn)
3043 gcc_assert (INSN_P (insn));
3045 if (INSN_NOP_P (insn))
3046 return;
3048 df_simulate_one_insn_backwards (BLOCK_FOR_INSN (insn), insn, lv);
3051 /* Return livness set at the end of BB. */
3052 static regset
3053 compute_live_after_bb (basic_block bb)
3055 edge e;
3056 edge_iterator ei;
3057 regset lv = get_clear_regset_from_pool ();
3059 gcc_assert (!ignore_first);
3061 FOR_EACH_EDGE (e, ei, bb->succs)
3062 if (sel_bb_empty_p (e->dest))
3064 if (! BB_LV_SET_VALID_P (e->dest))
3066 gcc_unreachable ();
3067 gcc_assert (BB_LV_SET (e->dest) == NULL);
3068 BB_LV_SET (e->dest) = compute_live_after_bb (e->dest);
3069 BB_LV_SET_VALID_P (e->dest) = true;
3071 IOR_REG_SET (lv, BB_LV_SET (e->dest));
3073 else
3074 IOR_REG_SET (lv, compute_live (sel_bb_head (e->dest)));
3076 return lv;
3079 /* Compute the set of all live registers at the point before INSN and save
3080 it at INSN if INSN is bb header. */
3081 regset
3082 compute_live (insn_t insn)
3084 basic_block bb = BLOCK_FOR_INSN (insn);
3085 insn_t final, temp;
3086 regset lv;
3088 /* Return the valid set if we're already on it. */
3089 if (!ignore_first)
3091 regset src = NULL;
3093 if (sel_bb_head_p (insn) && BB_LV_SET_VALID_P (bb))
3094 src = BB_LV_SET (bb);
3095 else
3097 gcc_assert (in_current_region_p (bb));
3098 if (INSN_LIVE_VALID_P (insn))
3099 src = INSN_LIVE (insn);
3102 if (src)
3104 lv = get_regset_from_pool ();
3105 COPY_REG_SET (lv, src);
3107 if (sel_bb_head_p (insn) && ! BB_LV_SET_VALID_P (bb))
3109 COPY_REG_SET (BB_LV_SET (bb), lv);
3110 BB_LV_SET_VALID_P (bb) = true;
3113 return_regset_to_pool (lv);
3114 return lv;
3118 /* We've skipped the wrong lv_set. Don't skip the right one. */
3119 ignore_first = false;
3120 gcc_assert (in_current_region_p (bb));
3122 /* Find a valid LV set in this block or below, if needed.
3123 Start searching from the next insn: either ignore_first is true, or
3124 INSN doesn't have a correct live set. */
3125 temp = NEXT_INSN (insn);
3126 final = NEXT_INSN (BB_END (bb));
3127 while (temp != final && ! INSN_LIVE_VALID_P (temp))
3128 temp = NEXT_INSN (temp);
3129 if (temp == final)
3131 lv = compute_live_after_bb (bb);
3132 temp = PREV_INSN (temp);
3134 else
3136 lv = get_regset_from_pool ();
3137 COPY_REG_SET (lv, INSN_LIVE (temp));
3140 /* Put correct lv sets on the insns which have bad sets. */
3141 final = PREV_INSN (insn);
3142 while (temp != final)
3144 propagate_lv_set (lv, temp);
3145 COPY_REG_SET (INSN_LIVE (temp), lv);
3146 INSN_LIVE_VALID_P (temp) = true;
3147 temp = PREV_INSN (temp);
3150 /* Also put it in a BB. */
3151 if (sel_bb_head_p (insn))
3153 basic_block bb = BLOCK_FOR_INSN (insn);
3155 COPY_REG_SET (BB_LV_SET (bb), lv);
3156 BB_LV_SET_VALID_P (bb) = true;
3159 /* We return LV to the pool, but will not clear it there. Thus we can
3160 legimatelly use LV till the next use of regset_pool_get (). */
3161 return_regset_to_pool (lv);
3162 return lv;
3165 /* Update liveness sets for INSN. */
3166 static inline void
3167 update_liveness_on_insn (rtx_insn *insn)
3169 ignore_first = true;
3170 compute_live (insn);
3173 /* Compute liveness below INSN and write it into REGS. */
3174 static inline void
3175 compute_live_below_insn (rtx_insn *insn, regset regs)
3177 rtx_insn *succ;
3178 succ_iterator si;
3180 FOR_EACH_SUCC_1 (succ, si, insn, SUCCS_ALL)
3181 IOR_REG_SET (regs, compute_live (succ));
3184 /* Update the data gathered in av and lv sets starting from INSN. */
3185 static void
3186 update_data_sets (rtx_insn *insn)
3188 update_liveness_on_insn (insn);
3189 if (sel_bb_head_p (insn))
3191 gcc_assert (AV_LEVEL (insn) != 0);
3192 BB_AV_LEVEL (BLOCK_FOR_INSN (insn)) = -1;
3193 compute_av_set (insn, NULL, 0, 0);
3198 /* Helper for move_op () and find_used_regs ().
3199 Return speculation type for which a check should be created on the place
3200 of INSN. EXPR is one of the original ops we are searching for. */
3201 static ds_t
3202 get_spec_check_type_for_insn (insn_t insn, expr_t expr)
3204 ds_t to_check_ds;
3205 ds_t already_checked_ds = EXPR_SPEC_DONE_DS (INSN_EXPR (insn));
3207 to_check_ds = EXPR_SPEC_TO_CHECK_DS (expr);
3209 if (targetm.sched.get_insn_checked_ds)
3210 already_checked_ds |= targetm.sched.get_insn_checked_ds (insn);
3212 if (spec_info != NULL
3213 && (spec_info->flags & SEL_SCHED_SPEC_DONT_CHECK_CONTROL))
3214 already_checked_ds |= BEGIN_CONTROL;
3216 already_checked_ds = ds_get_speculation_types (already_checked_ds);
3218 to_check_ds &= ~already_checked_ds;
3220 return to_check_ds;
3223 /* Find the set of registers that are unavailable for storing expres
3224 while moving ORIG_OPS up on the path starting from INSN due to
3225 liveness (USED_REGS) or hardware restrictions (REG_RENAME_P).
3227 All the original operations found during the traversal are saved in the
3228 ORIGINAL_INSNS list.
3230 REG_RENAME_P denotes the set of hardware registers that
3231 can not be used with renaming due to the register class restrictions,
3232 mode restrictions and other (the register we'll choose should be
3233 compatible class with the original uses, shouldn't be in call_used_regs,
3234 should be HARD_REGNO_RENAME_OK etc).
3236 Returns TRUE if we've found all original insns, FALSE otherwise.
3238 This function utilizes code_motion_path_driver (formerly find_used_regs_1)
3239 to traverse the code motion paths. This helper function finds registers
3240 that are not available for storing expres while moving ORIG_OPS up on the
3241 path starting from INSN. A register considered as used on the moving path,
3242 if one of the following conditions is not satisfied:
3244 (1) a register not set or read on any path from xi to an instance of
3245 the original operation,
3246 (2) not among the live registers of the point immediately following the
3247 first original operation on a given downward path, except for the
3248 original target register of the operation,
3249 (3) not live on the other path of any conditional branch that is passed
3250 by the operation, in case original operations are not present on
3251 both paths of the conditional branch.
3253 All the original operations found during the traversal are saved in the
3254 ORIGINAL_INSNS list.
3256 REG_RENAME_P->CROSSES_CALL is true, if there is a call insn on the path
3257 from INSN to original insn. In this case CALL_USED_REG_SET will be added
3258 to unavailable hard regs at the point original operation is found. */
3260 static bool
3261 find_used_regs (insn_t insn, av_set_t orig_ops, regset used_regs,
3262 struct reg_rename *reg_rename_p, def_list_t *original_insns)
3264 def_list_iterator i;
3265 def_t def;
3266 int res;
3267 bool needs_spec_check_p = false;
3268 expr_t expr;
3269 av_set_iterator expr_iter;
3270 struct fur_static_params sparams;
3271 struct cmpd_local_params lparams;
3273 /* We haven't visited any blocks yet. */
3274 bitmap_clear (code_motion_visited_blocks);
3276 /* Init parameters for code_motion_path_driver. */
3277 sparams.crosses_call = false;
3278 sparams.original_insns = original_insns;
3279 sparams.used_regs = used_regs;
3281 /* Set the appropriate hooks and data. */
3282 code_motion_path_driver_info = &fur_hooks;
3284 res = code_motion_path_driver (insn, orig_ops, NULL, &lparams, &sparams);
3286 reg_rename_p->crosses_call |= sparams.crosses_call;
3288 gcc_assert (res == 1);
3289 gcc_assert (original_insns && *original_insns);
3291 /* ??? We calculate whether an expression needs a check when computing
3292 av sets. This information is not as precise as it could be due to
3293 merging this bit in merge_expr. We can do better in find_used_regs,
3294 but we want to avoid multiple traversals of the same code motion
3295 paths. */
3296 FOR_EACH_EXPR (expr, expr_iter, orig_ops)
3297 needs_spec_check_p |= EXPR_NEEDS_SPEC_CHECK_P (expr);
3299 /* Mark hardware regs in REG_RENAME_P that are not suitable
3300 for renaming expr in INSN due to hardware restrictions (register class,
3301 modes compatibility etc). */
3302 FOR_EACH_DEF (def, i, *original_insns)
3304 vinsn_t vinsn = INSN_VINSN (def->orig_insn);
3306 if (VINSN_SEPARABLE_P (vinsn))
3307 mark_unavailable_hard_regs (def, reg_rename_p, used_regs);
3309 /* Do not allow clobbering of ld.[sa] address in case some of the
3310 original operations need a check. */
3311 if (needs_spec_check_p)
3312 IOR_REG_SET (used_regs, VINSN_REG_USES (vinsn));
3315 return true;
3319 /* Functions to choose the best insn from available ones. */
3321 /* Adjusts the priority for EXPR using the backend *_adjust_priority hook. */
3322 static int
3323 sel_target_adjust_priority (expr_t expr)
3325 int priority = EXPR_PRIORITY (expr);
3326 int new_priority;
3328 if (targetm.sched.adjust_priority)
3329 new_priority = targetm.sched.adjust_priority (EXPR_INSN_RTX (expr), priority);
3330 else
3331 new_priority = priority;
3333 gcc_assert (new_priority >= 0);
3335 /* If the priority has changed, adjust EXPR_PRIORITY_ADJ accordingly. */
3336 EXPR_PRIORITY_ADJ (expr) = new_priority - EXPR_PRIORITY (expr);
3338 if (sched_verbose >= 4)
3339 sel_print ("sel_target_adjust_priority: insn %d, %d+%d = %d.\n",
3340 INSN_UID (EXPR_INSN_RTX (expr)), EXPR_PRIORITY (expr),
3341 EXPR_PRIORITY_ADJ (expr), new_priority);
3343 return new_priority;
3346 /* Rank two available exprs for schedule. Never return 0 here. */
3347 static int
3348 sel_rank_for_schedule (const void *x, const void *y)
3350 expr_t tmp = *(const expr_t *) y;
3351 expr_t tmp2 = *(const expr_t *) x;
3352 insn_t tmp_insn, tmp2_insn;
3353 vinsn_t tmp_vinsn, tmp2_vinsn;
3354 int val;
3356 tmp_vinsn = EXPR_VINSN (tmp);
3357 tmp2_vinsn = EXPR_VINSN (tmp2);
3358 tmp_insn = EXPR_INSN_RTX (tmp);
3359 tmp2_insn = EXPR_INSN_RTX (tmp2);
3361 /* Schedule debug insns as early as possible. */
3362 if (DEBUG_INSN_P (tmp_insn) && !DEBUG_INSN_P (tmp2_insn))
3363 return -1;
3364 else if (DEBUG_INSN_P (tmp2_insn))
3365 return 1;
3367 /* Prefer SCHED_GROUP_P insns to any others. */
3368 if (SCHED_GROUP_P (tmp_insn) != SCHED_GROUP_P (tmp2_insn))
3370 if (VINSN_UNIQUE_P (tmp_vinsn) && VINSN_UNIQUE_P (tmp2_vinsn))
3371 return SCHED_GROUP_P (tmp2_insn) ? 1 : -1;
3373 /* Now uniqueness means SCHED_GROUP_P is set, because schedule groups
3374 cannot be cloned. */
3375 if (VINSN_UNIQUE_P (tmp2_vinsn))
3376 return 1;
3377 return -1;
3380 /* Discourage scheduling of speculative checks. */
3381 val = (sel_insn_is_speculation_check (tmp_insn)
3382 - sel_insn_is_speculation_check (tmp2_insn));
3383 if (val)
3384 return val;
3386 /* Prefer not scheduled insn over scheduled one. */
3387 if (EXPR_SCHED_TIMES (tmp) > 0 || EXPR_SCHED_TIMES (tmp2) > 0)
3389 val = EXPR_SCHED_TIMES (tmp) - EXPR_SCHED_TIMES (tmp2);
3390 if (val)
3391 return val;
3394 /* Prefer jump over non-jump instruction. */
3395 if (control_flow_insn_p (tmp_insn) && !control_flow_insn_p (tmp2_insn))
3396 return -1;
3397 else if (control_flow_insn_p (tmp2_insn) && !control_flow_insn_p (tmp_insn))
3398 return 1;
3400 /* Prefer an expr with non-zero usefulness. */
3401 int u1 = EXPR_USEFULNESS (tmp), u2 = EXPR_USEFULNESS (tmp2);
3403 if (u1 == 0)
3405 if (u2 == 0)
3406 u1 = u2 = 1;
3407 else
3408 return 1;
3410 else if (u2 == 0)
3411 return -1;
3413 /* Prefer an expr with greater priority. */
3414 val = (u2 * (EXPR_PRIORITY (tmp2) + EXPR_PRIORITY_ADJ (tmp2))
3415 - u1 * (EXPR_PRIORITY (tmp) + EXPR_PRIORITY_ADJ (tmp)));
3416 if (val)
3417 return val;
3419 if (spec_info != NULL && spec_info->mask != 0)
3420 /* This code was taken from haifa-sched.c: rank_for_schedule (). */
3422 ds_t ds1, ds2;
3423 dw_t dw1, dw2;
3424 int dw;
3426 ds1 = EXPR_SPEC_DONE_DS (tmp);
3427 if (ds1)
3428 dw1 = ds_weak (ds1);
3429 else
3430 dw1 = NO_DEP_WEAK;
3432 ds2 = EXPR_SPEC_DONE_DS (tmp2);
3433 if (ds2)
3434 dw2 = ds_weak (ds2);
3435 else
3436 dw2 = NO_DEP_WEAK;
3438 dw = dw2 - dw1;
3439 if (dw > (NO_DEP_WEAK / 8) || dw < -(NO_DEP_WEAK / 8))
3440 return dw;
3443 /* Prefer an old insn to a bookkeeping insn. */
3444 if (INSN_UID (tmp_insn) < first_emitted_uid
3445 && INSN_UID (tmp2_insn) >= first_emitted_uid)
3446 return -1;
3447 if (INSN_UID (tmp_insn) >= first_emitted_uid
3448 && INSN_UID (tmp2_insn) < first_emitted_uid)
3449 return 1;
3451 /* Prefer an insn with smaller UID, as a last resort.
3452 We can't safely use INSN_LUID as it is defined only for those insns
3453 that are in the stream. */
3454 return INSN_UID (tmp_insn) - INSN_UID (tmp2_insn);
3457 /* Filter out expressions from av set pointed to by AV_PTR
3458 that are pipelined too many times. */
3459 static void
3460 process_pipelined_exprs (av_set_t *av_ptr)
3462 expr_t expr;
3463 av_set_iterator si;
3465 /* Don't pipeline already pipelined code as that would increase
3466 number of unnecessary register moves. */
3467 FOR_EACH_EXPR_1 (expr, si, av_ptr)
3469 if (EXPR_SCHED_TIMES (expr)
3470 >= PARAM_VALUE (PARAM_SELSCHED_MAX_SCHED_TIMES))
3471 av_set_iter_remove (&si);
3475 /* Filter speculative insns from AV_PTR if we don't want them. */
3476 static void
3477 process_spec_exprs (av_set_t *av_ptr)
3479 expr_t expr;
3480 av_set_iterator si;
3482 if (spec_info == NULL)
3483 return;
3485 /* Scan *AV_PTR to find out if we want to consider speculative
3486 instructions for scheduling. */
3487 FOR_EACH_EXPR_1 (expr, si, av_ptr)
3489 ds_t ds;
3491 ds = EXPR_SPEC_DONE_DS (expr);
3493 /* The probability of a success is too low - don't speculate. */
3494 if ((ds & SPECULATIVE)
3495 && (ds_weak (ds) < spec_info->data_weakness_cutoff
3496 || EXPR_USEFULNESS (expr) < spec_info->control_weakness_cutoff
3497 || (pipelining_p && false
3498 && (ds & DATA_SPEC)
3499 && (ds & CONTROL_SPEC))))
3501 av_set_iter_remove (&si);
3502 continue;
3507 /* Search for any use-like insns in AV_PTR and decide on scheduling
3508 them. Return one when found, and NULL otherwise.
3509 Note that we check here whether a USE could be scheduled to avoid
3510 an infinite loop later. */
3511 static expr_t
3512 process_use_exprs (av_set_t *av_ptr)
3514 expr_t expr;
3515 av_set_iterator si;
3516 bool uses_present_p = false;
3517 bool try_uses_p = true;
3519 FOR_EACH_EXPR_1 (expr, si, av_ptr)
3521 /* This will also initialize INSN_CODE for later use. */
3522 if (recog_memoized (EXPR_INSN_RTX (expr)) < 0)
3524 /* If we have a USE in *AV_PTR that was not scheduled yet,
3525 do so because it will do good only. */
3526 if (EXPR_SCHED_TIMES (expr) <= 0)
3528 if (EXPR_TARGET_AVAILABLE (expr) == 1)
3529 return expr;
3531 av_set_iter_remove (&si);
3533 else
3535 gcc_assert (pipelining_p);
3537 uses_present_p = true;
3540 else
3541 try_uses_p = false;
3544 if (uses_present_p)
3546 /* If we don't want to schedule any USEs right now and we have some
3547 in *AV_PTR, remove them, else just return the first one found. */
3548 if (!try_uses_p)
3550 FOR_EACH_EXPR_1 (expr, si, av_ptr)
3551 if (INSN_CODE (EXPR_INSN_RTX (expr)) < 0)
3552 av_set_iter_remove (&si);
3554 else
3556 FOR_EACH_EXPR_1 (expr, si, av_ptr)
3558 gcc_assert (INSN_CODE (EXPR_INSN_RTX (expr)) < 0);
3560 if (EXPR_TARGET_AVAILABLE (expr) == 1)
3561 return expr;
3563 av_set_iter_remove (&si);
3568 return NULL;
3571 /* Lookup EXPR in VINSN_VEC and return TRUE if found. Also check patterns from
3572 EXPR's history of changes. */
3573 static bool
3574 vinsn_vec_has_expr_p (vinsn_vec_t vinsn_vec, expr_t expr)
3576 vinsn_t vinsn, expr_vinsn;
3577 int n;
3578 unsigned i;
3580 /* Start with checking expr itself and then proceed with all the old forms
3581 of expr taken from its history vector. */
3582 for (i = 0, expr_vinsn = EXPR_VINSN (expr);
3583 expr_vinsn;
3584 expr_vinsn = (i < EXPR_HISTORY_OF_CHANGES (expr).length ()
3585 ? EXPR_HISTORY_OF_CHANGES (expr)[i++].old_expr_vinsn
3586 : NULL))
3587 FOR_EACH_VEC_ELT (vinsn_vec, n, vinsn)
3588 if (VINSN_SEPARABLE_P (vinsn))
3590 if (vinsn_equal_p (vinsn, expr_vinsn))
3591 return true;
3593 else
3595 /* For non-separable instructions, the blocking insn can have
3596 another pattern due to substitution, and we can't choose
3597 different register as in the above case. Check all registers
3598 being written instead. */
3599 if (bitmap_intersect_p (VINSN_REG_SETS (vinsn),
3600 VINSN_REG_SETS (expr_vinsn)))
3601 return true;
3604 return false;
3607 /* Return true if either of expressions from ORIG_OPS can be blocked
3608 by previously created bookkeeping code. STATIC_PARAMS points to static
3609 parameters of move_op. */
3610 static bool
3611 av_set_could_be_blocked_by_bookkeeping_p (av_set_t orig_ops, void *static_params)
3613 expr_t expr;
3614 av_set_iterator iter;
3615 moveop_static_params_p sparams;
3617 /* This checks that expressions in ORIG_OPS are not blocked by bookkeeping
3618 created while scheduling on another fence. */
3619 FOR_EACH_EXPR (expr, iter, orig_ops)
3620 if (vinsn_vec_has_expr_p (vec_bookkeeping_blocked_vinsns, expr))
3621 return true;
3623 gcc_assert (code_motion_path_driver_info == &move_op_hooks);
3624 sparams = (moveop_static_params_p) static_params;
3626 /* Expressions can be also blocked by bookkeeping created during current
3627 move_op. */
3628 if (bitmap_bit_p (current_copies, INSN_UID (sparams->failed_insn)))
3629 FOR_EACH_EXPR (expr, iter, orig_ops)
3630 if (moveup_expr_cached (expr, sparams->failed_insn, false) != MOVEUP_EXPR_NULL)
3631 return true;
3633 /* Expressions in ORIG_OPS may have wrong destination register due to
3634 renaming. Check with the right register instead. */
3635 if (sparams->dest && REG_P (sparams->dest))
3637 rtx reg = sparams->dest;
3638 vinsn_t failed_vinsn = INSN_VINSN (sparams->failed_insn);
3640 if (register_unavailable_p (VINSN_REG_SETS (failed_vinsn), reg)
3641 || register_unavailable_p (VINSN_REG_USES (failed_vinsn), reg)
3642 || register_unavailable_p (VINSN_REG_CLOBBERS (failed_vinsn), reg))
3643 return true;
3646 return false;
3649 /* Clear VINSN_VEC and detach vinsns. */
3650 static void
3651 vinsn_vec_clear (vinsn_vec_t *vinsn_vec)
3653 unsigned len = vinsn_vec->length ();
3654 if (len > 0)
3656 vinsn_t vinsn;
3657 int n;
3659 FOR_EACH_VEC_ELT (*vinsn_vec, n, vinsn)
3660 vinsn_detach (vinsn);
3661 vinsn_vec->block_remove (0, len);
3665 /* Add the vinsn of EXPR to the VINSN_VEC. */
3666 static void
3667 vinsn_vec_add (vinsn_vec_t *vinsn_vec, expr_t expr)
3669 vinsn_attach (EXPR_VINSN (expr));
3670 vinsn_vec->safe_push (EXPR_VINSN (expr));
3673 /* Free the vector representing blocked expressions. */
3674 static void
3675 vinsn_vec_free (vinsn_vec_t &vinsn_vec)
3677 vinsn_vec.release ();
3680 /* Increase EXPR_PRIORITY_ADJ for INSN by AMOUNT. */
3682 void sel_add_to_insn_priority (rtx insn, int amount)
3684 EXPR_PRIORITY_ADJ (INSN_EXPR (insn)) += amount;
3686 if (sched_verbose >= 2)
3687 sel_print ("sel_add_to_insn_priority: insn %d, by %d (now %d+%d).\n",
3688 INSN_UID (insn), amount, EXPR_PRIORITY (INSN_EXPR (insn)),
3689 EXPR_PRIORITY_ADJ (INSN_EXPR (insn)));
3692 /* Turn AV into a vector, filter inappropriate insns and sort it. Return
3693 true if there is something to schedule. BNDS and FENCE are current
3694 boundaries and fence, respectively. If we need to stall for some cycles
3695 before an expr from AV would become available, write this number to
3696 *PNEED_STALL. */
3697 static bool
3698 fill_vec_av_set (av_set_t av, blist_t bnds, fence_t fence,
3699 int *pneed_stall)
3701 av_set_iterator si;
3702 expr_t expr;
3703 int sched_next_worked = 0, stalled, n;
3704 static int av_max_prio, est_ticks_till_branch;
3705 int min_need_stall = -1;
3706 deps_t dc = BND_DC (BLIST_BND (bnds));
3708 /* Bail out early when the ready list contained only USEs/CLOBBERs that are
3709 already scheduled. */
3710 if (av == NULL)
3711 return false;
3713 /* Empty vector from the previous stuff. */
3714 if (vec_av_set.length () > 0)
3715 vec_av_set.block_remove (0, vec_av_set.length ());
3717 /* Turn the set into a vector for sorting and call sel_target_adjust_priority
3718 for each insn. */
3719 gcc_assert (vec_av_set.is_empty ());
3720 FOR_EACH_EXPR (expr, si, av)
3722 vec_av_set.safe_push (expr);
3724 gcc_assert (EXPR_PRIORITY_ADJ (expr) == 0 || *pneed_stall);
3726 /* Adjust priority using target backend hook. */
3727 sel_target_adjust_priority (expr);
3730 /* Sort the vector. */
3731 vec_av_set.qsort (sel_rank_for_schedule);
3733 /* We record maximal priority of insns in av set for current instruction
3734 group. */
3735 if (FENCE_STARTS_CYCLE_P (fence))
3736 av_max_prio = est_ticks_till_branch = INT_MIN;
3738 /* Filter out inappropriate expressions. Loop's direction is reversed to
3739 visit "best" instructions first. We assume that vec::unordered_remove
3740 moves last element in place of one being deleted. */
3741 for (n = vec_av_set.length () - 1, stalled = 0; n >= 0; n--)
3743 expr_t expr = vec_av_set[n];
3744 insn_t insn = EXPR_INSN_RTX (expr);
3745 signed char target_available;
3746 bool is_orig_reg_p = true;
3747 int need_cycles, new_prio;
3748 bool fence_insn_p = INSN_UID (insn) == INSN_UID (FENCE_INSN (fence));
3750 /* Don't allow any insns other than from SCHED_GROUP if we have one. */
3751 if (FENCE_SCHED_NEXT (fence) && insn != FENCE_SCHED_NEXT (fence))
3753 vec_av_set.unordered_remove (n);
3754 continue;
3757 /* Set number of sched_next insns (just in case there
3758 could be several). */
3759 if (FENCE_SCHED_NEXT (fence))
3760 sched_next_worked++;
3762 /* Check all liveness requirements and try renaming.
3763 FIXME: try to minimize calls to this. */
3764 target_available = EXPR_TARGET_AVAILABLE (expr);
3766 /* If insn was already scheduled on the current fence,
3767 set TARGET_AVAILABLE to -1 no matter what expr's attribute says. */
3768 if (vinsn_vec_has_expr_p (vec_target_unavailable_vinsns, expr)
3769 && !fence_insn_p)
3770 target_available = -1;
3772 /* If the availability of the EXPR is invalidated by the insertion of
3773 bookkeeping earlier, make sure that we won't choose this expr for
3774 scheduling if it's not separable, and if it is separable, then
3775 we have to recompute the set of available registers for it. */
3776 if (vinsn_vec_has_expr_p (vec_bookkeeping_blocked_vinsns, expr))
3778 vec_av_set.unordered_remove (n);
3779 if (sched_verbose >= 4)
3780 sel_print ("Expr %d is blocked by bookkeeping inserted earlier\n",
3781 INSN_UID (insn));
3782 continue;
3785 if (target_available == true)
3787 /* Do nothing -- we can use an existing register. */
3788 is_orig_reg_p = EXPR_SEPARABLE_P (expr);
3790 else if (/* Non-separable instruction will never
3791 get another register. */
3792 (target_available == false
3793 && !EXPR_SEPARABLE_P (expr))
3794 /* Don't try to find a register for low-priority expression. */
3795 || (int) vec_av_set.length () - 1 - n >= max_insns_to_rename
3796 /* ??? FIXME: Don't try to rename data speculation. */
3797 || (EXPR_SPEC_DONE_DS (expr) & BEGIN_DATA)
3798 || ! find_best_reg_for_expr (expr, bnds, &is_orig_reg_p))
3800 vec_av_set.unordered_remove (n);
3801 if (sched_verbose >= 4)
3802 sel_print ("Expr %d has no suitable target register\n",
3803 INSN_UID (insn));
3805 /* A fence insn should not get here. */
3806 gcc_assert (!fence_insn_p);
3807 continue;
3810 /* At this point a fence insn should always be available. */
3811 gcc_assert (!fence_insn_p
3812 || INSN_UID (FENCE_INSN (fence)) == INSN_UID (EXPR_INSN_RTX (expr)));
3814 /* Filter expressions that need to be renamed or speculated when
3815 pipelining, because compensating register copies or speculation
3816 checks are likely to be placed near the beginning of the loop,
3817 causing a stall. */
3818 if (pipelining_p && EXPR_ORIG_SCHED_CYCLE (expr) > 0
3819 && (!is_orig_reg_p || EXPR_SPEC_DONE_DS (expr) != 0))
3821 /* Estimation of number of cycles until loop branch for
3822 renaming/speculation to be successful. */
3823 int need_n_ticks_till_branch = sel_vinsn_cost (EXPR_VINSN (expr));
3825 if ((int) current_loop_nest->ninsns < 9)
3827 vec_av_set.unordered_remove (n);
3828 if (sched_verbose >= 4)
3829 sel_print ("Pipelining expr %d will likely cause stall\n",
3830 INSN_UID (insn));
3831 continue;
3834 if ((int) current_loop_nest->ninsns - num_insns_scheduled
3835 < need_n_ticks_till_branch * issue_rate / 2
3836 && est_ticks_till_branch < need_n_ticks_till_branch)
3838 vec_av_set.unordered_remove (n);
3839 if (sched_verbose >= 4)
3840 sel_print ("Pipelining expr %d will likely cause stall\n",
3841 INSN_UID (insn));
3842 continue;
3846 /* We want to schedule speculation checks as late as possible. Discard
3847 them from av set if there are instructions with higher priority. */
3848 if (sel_insn_is_speculation_check (insn)
3849 && EXPR_PRIORITY (expr) < av_max_prio)
3851 stalled++;
3852 min_need_stall = min_need_stall < 0 ? 1 : MIN (min_need_stall, 1);
3853 vec_av_set.unordered_remove (n);
3854 if (sched_verbose >= 4)
3855 sel_print ("Delaying speculation check %d until its first use\n",
3856 INSN_UID (insn));
3857 continue;
3860 /* Ignore EXPRs available from pipelining to update AV_MAX_PRIO. */
3861 if (EXPR_ORIG_SCHED_CYCLE (expr) <= 0)
3862 av_max_prio = MAX (av_max_prio, EXPR_PRIORITY (expr));
3864 /* Don't allow any insns whose data is not yet ready.
3865 Check first whether we've already tried them and failed. */
3866 if (INSN_UID (insn) < FENCE_READY_TICKS_SIZE (fence))
3868 need_cycles = (FENCE_READY_TICKS (fence)[INSN_UID (insn)]
3869 - FENCE_CYCLE (fence));
3870 if (EXPR_ORIG_SCHED_CYCLE (expr) <= 0)
3871 est_ticks_till_branch = MAX (est_ticks_till_branch,
3872 EXPR_PRIORITY (expr) + need_cycles);
3874 if (need_cycles > 0)
3876 stalled++;
3877 min_need_stall = (min_need_stall < 0
3878 ? need_cycles
3879 : MIN (min_need_stall, need_cycles));
3880 vec_av_set.unordered_remove (n);
3882 if (sched_verbose >= 4)
3883 sel_print ("Expr %d is not ready until cycle %d (cached)\n",
3884 INSN_UID (insn),
3885 FENCE_READY_TICKS (fence)[INSN_UID (insn)]);
3886 continue;
3890 /* Now resort to dependence analysis to find whether EXPR might be
3891 stalled due to dependencies from FENCE's context. */
3892 need_cycles = tick_check_p (expr, dc, fence);
3893 new_prio = EXPR_PRIORITY (expr) + EXPR_PRIORITY_ADJ (expr) + need_cycles;
3895 if (EXPR_ORIG_SCHED_CYCLE (expr) <= 0)
3896 est_ticks_till_branch = MAX (est_ticks_till_branch,
3897 new_prio);
3899 if (need_cycles > 0)
3901 if (INSN_UID (insn) >= FENCE_READY_TICKS_SIZE (fence))
3903 int new_size = INSN_UID (insn) * 3 / 2;
3905 FENCE_READY_TICKS (fence)
3906 = (int *) xrecalloc (FENCE_READY_TICKS (fence),
3907 new_size, FENCE_READY_TICKS_SIZE (fence),
3908 sizeof (int));
3910 FENCE_READY_TICKS (fence)[INSN_UID (insn)]
3911 = FENCE_CYCLE (fence) + need_cycles;
3913 stalled++;
3914 min_need_stall = (min_need_stall < 0
3915 ? need_cycles
3916 : MIN (min_need_stall, need_cycles));
3918 vec_av_set.unordered_remove (n);
3920 if (sched_verbose >= 4)
3921 sel_print ("Expr %d is not ready yet until cycle %d\n",
3922 INSN_UID (insn),
3923 FENCE_READY_TICKS (fence)[INSN_UID (insn)]);
3924 continue;
3927 if (sched_verbose >= 4)
3928 sel_print ("Expr %d is ok\n", INSN_UID (insn));
3929 min_need_stall = 0;
3932 /* Clear SCHED_NEXT. */
3933 if (FENCE_SCHED_NEXT (fence))
3935 gcc_assert (sched_next_worked == 1);
3936 FENCE_SCHED_NEXT (fence) = NULL;
3939 /* No need to stall if this variable was not initialized. */
3940 if (min_need_stall < 0)
3941 min_need_stall = 0;
3943 if (vec_av_set.is_empty ())
3945 /* We need to set *pneed_stall here, because later we skip this code
3946 when ready list is empty. */
3947 *pneed_stall = min_need_stall;
3948 return false;
3950 else
3951 gcc_assert (min_need_stall == 0);
3953 /* Sort the vector. */
3954 vec_av_set.qsort (sel_rank_for_schedule);
3956 if (sched_verbose >= 4)
3958 sel_print ("Total ready exprs: %d, stalled: %d\n",
3959 vec_av_set.length (), stalled);
3960 sel_print ("Sorted av set (%d): ", vec_av_set.length ());
3961 FOR_EACH_VEC_ELT (vec_av_set, n, expr)
3962 dump_expr (expr);
3963 sel_print ("\n");
3966 *pneed_stall = 0;
3967 return true;
3970 /* Convert a vectored and sorted av set to the ready list that
3971 the rest of the backend wants to see. */
3972 static void
3973 convert_vec_av_set_to_ready (void)
3975 int n;
3976 expr_t expr;
3978 /* Allocate and fill the ready list from the sorted vector. */
3979 ready.n_ready = vec_av_set.length ();
3980 ready.first = ready.n_ready - 1;
3982 gcc_assert (ready.n_ready > 0);
3984 if (ready.n_ready > max_issue_size)
3986 max_issue_size = ready.n_ready;
3987 sched_extend_ready_list (ready.n_ready);
3990 FOR_EACH_VEC_ELT (vec_av_set, n, expr)
3992 vinsn_t vi = EXPR_VINSN (expr);
3993 insn_t insn = VINSN_INSN_RTX (vi);
3995 ready_try[n] = 0;
3996 ready.vec[n] = insn;
4000 /* Initialize ready list from *AV_PTR for the max_issue () call.
4001 If any unrecognizable insn found in *AV_PTR, return it (and skip
4002 max_issue). BND and FENCE are current boundary and fence,
4003 respectively. If we need to stall for some cycles before an expr
4004 from *AV_PTR would become available, write this number to *PNEED_STALL. */
4005 static expr_t
4006 fill_ready_list (av_set_t *av_ptr, blist_t bnds, fence_t fence,
4007 int *pneed_stall)
4009 expr_t expr;
4011 /* We do not support multiple boundaries per fence. */
4012 gcc_assert (BLIST_NEXT (bnds) == NULL);
4014 /* Process expressions required special handling, i.e. pipelined,
4015 speculative and recog() < 0 expressions first. */
4016 process_pipelined_exprs (av_ptr);
4017 process_spec_exprs (av_ptr);
4019 /* A USE could be scheduled immediately. */
4020 expr = process_use_exprs (av_ptr);
4021 if (expr)
4023 *pneed_stall = 0;
4024 return expr;
4027 /* Turn the av set to a vector for sorting. */
4028 if (! fill_vec_av_set (*av_ptr, bnds, fence, pneed_stall))
4030 ready.n_ready = 0;
4031 return NULL;
4034 /* Build the final ready list. */
4035 convert_vec_av_set_to_ready ();
4036 return NULL;
4039 /* Wrapper for dfa_new_cycle (). Returns TRUE if cycle was advanced. */
4040 static bool
4041 sel_dfa_new_cycle (insn_t insn, fence_t fence)
4043 int last_scheduled_cycle = FENCE_LAST_SCHEDULED_INSN (fence)
4044 ? INSN_SCHED_CYCLE (FENCE_LAST_SCHEDULED_INSN (fence))
4045 : FENCE_CYCLE (fence) - 1;
4046 bool res = false;
4047 int sort_p = 0;
4049 if (!targetm.sched.dfa_new_cycle)
4050 return false;
4052 memcpy (curr_state, FENCE_STATE (fence), dfa_state_size);
4054 while (!sort_p && targetm.sched.dfa_new_cycle (sched_dump, sched_verbose,
4055 insn, last_scheduled_cycle,
4056 FENCE_CYCLE (fence), &sort_p))
4058 memcpy (FENCE_STATE (fence), curr_state, dfa_state_size);
4059 advance_one_cycle (fence);
4060 memcpy (curr_state, FENCE_STATE (fence), dfa_state_size);
4061 res = true;
4064 return res;
4067 /* Invoke reorder* target hooks on the ready list. Return the number of insns
4068 we can issue. FENCE is the current fence. */
4069 static int
4070 invoke_reorder_hooks (fence_t fence)
4072 int issue_more;
4073 bool ran_hook = false;
4075 /* Call the reorder hook at the beginning of the cycle, and call
4076 the reorder2 hook in the middle of the cycle. */
4077 if (FENCE_ISSUED_INSNS (fence) == 0)
4079 if (targetm.sched.reorder
4080 && !SCHED_GROUP_P (ready_element (&ready, 0))
4081 && ready.n_ready > 1)
4083 /* Don't give reorder the most prioritized insn as it can break
4084 pipelining. */
4085 if (pipelining_p)
4086 --ready.n_ready;
4088 issue_more
4089 = targetm.sched.reorder (sched_dump, sched_verbose,
4090 ready_lastpos (&ready),
4091 &ready.n_ready, FENCE_CYCLE (fence));
4093 if (pipelining_p)
4094 ++ready.n_ready;
4096 ran_hook = true;
4098 else
4099 /* Initialize can_issue_more for variable_issue. */
4100 issue_more = issue_rate;
4102 else if (targetm.sched.reorder2
4103 && !SCHED_GROUP_P (ready_element (&ready, 0)))
4105 if (ready.n_ready == 1)
4106 issue_more =
4107 targetm.sched.reorder2 (sched_dump, sched_verbose,
4108 ready_lastpos (&ready),
4109 &ready.n_ready, FENCE_CYCLE (fence));
4110 else
4112 if (pipelining_p)
4113 --ready.n_ready;
4115 issue_more =
4116 targetm.sched.reorder2 (sched_dump, sched_verbose,
4117 ready.n_ready
4118 ? ready_lastpos (&ready) : NULL,
4119 &ready.n_ready, FENCE_CYCLE (fence));
4121 if (pipelining_p)
4122 ++ready.n_ready;
4125 ran_hook = true;
4127 else
4128 issue_more = FENCE_ISSUE_MORE (fence);
4130 /* Ensure that ready list and vec_av_set are in line with each other,
4131 i.e. vec_av_set[i] == ready_element (&ready, i). */
4132 if (issue_more && ran_hook)
4134 int i, j, n;
4135 rtx_insn **arr = ready.vec;
4136 expr_t *vec = vec_av_set.address ();
4138 for (i = 0, n = ready.n_ready; i < n; i++)
4139 if (EXPR_INSN_RTX (vec[i]) != arr[i])
4141 for (j = i; j < n; j++)
4142 if (EXPR_INSN_RTX (vec[j]) == arr[i])
4143 break;
4144 gcc_assert (j < n);
4146 std::swap (vec[i], vec[j]);
4150 return issue_more;
4153 /* Return an EXPR corresponding to INDEX element of ready list, if
4154 FOLLOW_READY_ELEMENT is true (i.e., an expr of
4155 ready_element (&ready, INDEX) will be returned), and to INDEX element of
4156 ready.vec otherwise. */
4157 static inline expr_t
4158 find_expr_for_ready (int index, bool follow_ready_element)
4160 expr_t expr;
4161 int real_index;
4163 real_index = follow_ready_element ? ready.first - index : index;
4165 expr = vec_av_set[real_index];
4166 gcc_assert (ready.vec[real_index] == EXPR_INSN_RTX (expr));
4168 return expr;
4171 /* Calculate insns worth trying via lookahead_guard hook. Return a number
4172 of such insns found. */
4173 static int
4174 invoke_dfa_lookahead_guard (void)
4176 int i, n;
4177 bool have_hook
4178 = targetm.sched.first_cycle_multipass_dfa_lookahead_guard != NULL;
4180 if (sched_verbose >= 2)
4181 sel_print ("ready after reorder: ");
4183 for (i = 0, n = 0; i < ready.n_ready; i++)
4185 expr_t expr;
4186 insn_t insn;
4187 int r;
4189 /* In this loop insn is Ith element of the ready list given by
4190 ready_element, not Ith element of ready.vec. */
4191 insn = ready_element (&ready, i);
4193 if (! have_hook || i == 0)
4194 r = 0;
4195 else
4196 r = targetm.sched.first_cycle_multipass_dfa_lookahead_guard (insn, i);
4198 gcc_assert (INSN_CODE (insn) >= 0);
4200 /* Only insns with ready_try = 0 can get here
4201 from fill_ready_list. */
4202 gcc_assert (ready_try [i] == 0);
4203 ready_try[i] = r;
4204 if (!r)
4205 n++;
4207 expr = find_expr_for_ready (i, true);
4209 if (sched_verbose >= 2)
4211 dump_vinsn (EXPR_VINSN (expr));
4212 sel_print (":%d; ", ready_try[i]);
4216 if (sched_verbose >= 2)
4217 sel_print ("\n");
4218 return n;
4221 /* Calculate the number of privileged insns and return it. */
4222 static int
4223 calculate_privileged_insns (void)
4225 expr_t cur_expr, min_spec_expr = NULL;
4226 int privileged_n = 0, i;
4228 for (i = 0; i < ready.n_ready; i++)
4230 if (ready_try[i])
4231 continue;
4233 if (! min_spec_expr)
4234 min_spec_expr = find_expr_for_ready (i, true);
4236 cur_expr = find_expr_for_ready (i, true);
4238 if (EXPR_SPEC (cur_expr) > EXPR_SPEC (min_spec_expr))
4239 break;
4241 ++privileged_n;
4244 if (i == ready.n_ready)
4245 privileged_n = 0;
4247 if (sched_verbose >= 2)
4248 sel_print ("privileged_n: %d insns with SPEC %d\n",
4249 privileged_n, privileged_n ? EXPR_SPEC (min_spec_expr) : -1);
4250 return privileged_n;
4253 /* Call the rest of the hooks after the choice was made. Return
4254 the number of insns that still can be issued given that the current
4255 number is ISSUE_MORE. FENCE and BEST_INSN are the current fence
4256 and the insn chosen for scheduling, respectively. */
4257 static int
4258 invoke_aftermath_hooks (fence_t fence, rtx_insn *best_insn, int issue_more)
4260 gcc_assert (INSN_P (best_insn));
4262 /* First, call dfa_new_cycle, and then variable_issue, if available. */
4263 sel_dfa_new_cycle (best_insn, fence);
4265 if (targetm.sched.variable_issue)
4267 memcpy (curr_state, FENCE_STATE (fence), dfa_state_size);
4268 issue_more =
4269 targetm.sched.variable_issue (sched_dump, sched_verbose, best_insn,
4270 issue_more);
4271 memcpy (FENCE_STATE (fence), curr_state, dfa_state_size);
4273 else if (!DEBUG_INSN_P (best_insn)
4274 && GET_CODE (PATTERN (best_insn)) != USE
4275 && GET_CODE (PATTERN (best_insn)) != CLOBBER)
4276 issue_more--;
4278 return issue_more;
4281 /* Estimate the cost of issuing INSN on DFA state STATE. */
4282 static int
4283 estimate_insn_cost (rtx_insn *insn, state_t state)
4285 static state_t temp = NULL;
4286 int cost;
4288 if (!temp)
4289 temp = xmalloc (dfa_state_size);
4291 memcpy (temp, state, dfa_state_size);
4292 cost = state_transition (temp, insn);
4294 if (cost < 0)
4295 return 0;
4296 else if (cost == 0)
4297 return 1;
4298 return cost;
4301 /* Return the cost of issuing EXPR on the FENCE as estimated by DFA.
4302 This function properly handles ASMs, USEs etc. */
4303 static int
4304 get_expr_cost (expr_t expr, fence_t fence)
4306 rtx_insn *insn = EXPR_INSN_RTX (expr);
4308 if (recog_memoized (insn) < 0)
4310 if (!FENCE_STARTS_CYCLE_P (fence)
4311 && INSN_ASM_P (insn))
4312 /* This is asm insn which is tryed to be issued on the
4313 cycle not first. Issue it on the next cycle. */
4314 return 1;
4315 else
4316 /* A USE insn, or something else we don't need to
4317 understand. We can't pass these directly to
4318 state_transition because it will trigger a
4319 fatal error for unrecognizable insns. */
4320 return 0;
4322 else
4323 return estimate_insn_cost (insn, FENCE_STATE (fence));
4326 /* Find the best insn for scheduling, either via max_issue or just take
4327 the most prioritized available. */
4328 static int
4329 choose_best_insn (fence_t fence, int privileged_n, int *index)
4331 int can_issue = 0;
4333 if (dfa_lookahead > 0)
4335 cycle_issued_insns = FENCE_ISSUED_INSNS (fence);
4336 /* TODO: pass equivalent of first_cycle_insn_p to max_issue (). */
4337 can_issue = max_issue (&ready, privileged_n,
4338 FENCE_STATE (fence), true, index);
4339 if (sched_verbose >= 2)
4340 sel_print ("max_issue: we can issue %d insns, already did %d insns\n",
4341 can_issue, FENCE_ISSUED_INSNS (fence));
4343 else
4345 /* We can't use max_issue; just return the first available element. */
4346 int i;
4348 for (i = 0; i < ready.n_ready; i++)
4350 expr_t expr = find_expr_for_ready (i, true);
4352 if (get_expr_cost (expr, fence) < 1)
4354 can_issue = can_issue_more;
4355 *index = i;
4357 if (sched_verbose >= 2)
4358 sel_print ("using %dth insn from the ready list\n", i + 1);
4360 break;
4364 if (i == ready.n_ready)
4366 can_issue = 0;
4367 *index = -1;
4371 return can_issue;
4374 /* Choose the best expr from *AV_VLIW_PTR and a suitable register for it.
4375 BNDS and FENCE are current boundaries and scheduling fence respectively.
4376 Return the expr found and NULL if nothing can be issued atm.
4377 Write to PNEED_STALL the number of cycles to stall if no expr was found. */
4378 static expr_t
4379 find_best_expr (av_set_t *av_vliw_ptr, blist_t bnds, fence_t fence,
4380 int *pneed_stall)
4382 expr_t best;
4384 /* Choose the best insn for scheduling via:
4385 1) sorting the ready list based on priority;
4386 2) calling the reorder hook;
4387 3) calling max_issue. */
4388 best = fill_ready_list (av_vliw_ptr, bnds, fence, pneed_stall);
4389 if (best == NULL && ready.n_ready > 0)
4391 int privileged_n, index;
4393 can_issue_more = invoke_reorder_hooks (fence);
4394 if (can_issue_more > 0)
4396 /* Try choosing the best insn until we find one that is could be
4397 scheduled due to liveness restrictions on its destination register.
4398 In the future, we'd like to choose once and then just probe insns
4399 in the order of their priority. */
4400 invoke_dfa_lookahead_guard ();
4401 privileged_n = calculate_privileged_insns ();
4402 can_issue_more = choose_best_insn (fence, privileged_n, &index);
4403 if (can_issue_more)
4404 best = find_expr_for_ready (index, true);
4406 /* We had some available insns, so if we can't issue them,
4407 we have a stall. */
4408 if (can_issue_more == 0)
4410 best = NULL;
4411 *pneed_stall = 1;
4415 if (best != NULL)
4417 can_issue_more = invoke_aftermath_hooks (fence, EXPR_INSN_RTX (best),
4418 can_issue_more);
4419 if (targetm.sched.variable_issue
4420 && can_issue_more == 0)
4421 *pneed_stall = 1;
4424 if (sched_verbose >= 2)
4426 if (best != NULL)
4428 sel_print ("Best expression (vliw form): ");
4429 dump_expr (best);
4430 sel_print ("; cycle %d\n", FENCE_CYCLE (fence));
4432 else
4433 sel_print ("No best expr found!\n");
4436 return best;
4440 /* Functions that implement the core of the scheduler. */
4443 /* Emit an instruction from EXPR with SEQNO and VINSN after
4444 PLACE_TO_INSERT. */
4445 static insn_t
4446 emit_insn_from_expr_after (expr_t expr, vinsn_t vinsn, int seqno,
4447 insn_t place_to_insert)
4449 /* This assert fails when we have identical instructions
4450 one of which dominates the other. In this case move_op ()
4451 finds the first instruction and doesn't search for second one.
4452 The solution would be to compute av_set after the first found
4453 insn and, if insn present in that set, continue searching.
4454 For now we workaround this issue in move_op. */
4455 gcc_assert (!INSN_IN_STREAM_P (EXPR_INSN_RTX (expr)));
4457 if (EXPR_WAS_RENAMED (expr))
4459 unsigned regno = expr_dest_regno (expr);
4461 if (HARD_REGISTER_NUM_P (regno))
4463 df_set_regs_ever_live (regno, true);
4464 reg_rename_tick[regno] = ++reg_rename_this_tick;
4468 return sel_gen_insn_from_expr_after (expr, vinsn, seqno,
4469 place_to_insert);
4472 /* Return TRUE if BB can hold bookkeeping code. */
4473 static bool
4474 block_valid_for_bookkeeping_p (basic_block bb)
4476 insn_t bb_end = BB_END (bb);
4478 if (!in_current_region_p (bb) || EDGE_COUNT (bb->succs) > 1)
4479 return false;
4481 if (INSN_P (bb_end))
4483 if (INSN_SCHED_TIMES (bb_end) > 0)
4484 return false;
4486 else
4487 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (bb_end));
4489 return true;
4492 /* Attempt to find a block that can hold bookkeeping code for path(s) incoming
4493 into E2->dest, except from E1->src (there may be a sequence of empty basic
4494 blocks between E1->src and E2->dest). Return found block, or NULL if new
4495 one must be created. If LAX holds, don't assume there is a simple path
4496 from E1->src to E2->dest. */
4497 static basic_block
4498 find_block_for_bookkeeping (edge e1, edge e2, bool lax)
4500 basic_block candidate_block = NULL;
4501 edge e;
4503 /* Loop over edges from E1 to E2, inclusive. */
4504 for (e = e1; !lax || e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun); e =
4505 EDGE_SUCC (e->dest, 0))
4507 if (EDGE_COUNT (e->dest->preds) == 2)
4509 if (candidate_block == NULL)
4510 candidate_block = (EDGE_PRED (e->dest, 0) == e
4511 ? EDGE_PRED (e->dest, 1)->src
4512 : EDGE_PRED (e->dest, 0)->src);
4513 else
4514 /* Found additional edge leading to path from e1 to e2
4515 from aside. */
4516 return NULL;
4518 else if (EDGE_COUNT (e->dest->preds) > 2)
4519 /* Several edges leading to path from e1 to e2 from aside. */
4520 return NULL;
4522 if (e == e2)
4523 return ((!lax || candidate_block)
4524 && block_valid_for_bookkeeping_p (candidate_block)
4525 ? candidate_block
4526 : NULL);
4528 if (lax && EDGE_COUNT (e->dest->succs) != 1)
4529 return NULL;
4532 if (lax)
4533 return NULL;
4535 gcc_unreachable ();
4538 /* Create new basic block for bookkeeping code for path(s) incoming into
4539 E2->dest, except from E1->src. Return created block. */
4540 static basic_block
4541 create_block_for_bookkeeping (edge e1, edge e2)
4543 basic_block new_bb, bb = e2->dest;
4545 /* Check that we don't spoil the loop structure. */
4546 if (current_loop_nest)
4548 basic_block latch = current_loop_nest->latch;
4550 /* We do not split header. */
4551 gcc_assert (e2->dest != current_loop_nest->header);
4553 /* We do not redirect the only edge to the latch block. */
4554 gcc_assert (e1->dest != latch
4555 || !single_pred_p (latch)
4556 || e1 != single_pred_edge (latch));
4559 /* Split BB to insert BOOK_INSN there. */
4560 new_bb = sched_split_block (bb, NULL);
4562 /* Move note_list from the upper bb. */
4563 gcc_assert (BB_NOTE_LIST (new_bb) == NULL_RTX);
4564 BB_NOTE_LIST (new_bb) = BB_NOTE_LIST (bb);
4565 BB_NOTE_LIST (bb) = NULL;
4567 gcc_assert (e2->dest == bb);
4569 /* Skip block for bookkeeping copy when leaving E1->src. */
4570 if (e1->flags & EDGE_FALLTHRU)
4571 sel_redirect_edge_and_branch_force (e1, new_bb);
4572 else
4573 sel_redirect_edge_and_branch (e1, new_bb);
4575 gcc_assert (e1->dest == new_bb);
4576 gcc_assert (sel_bb_empty_p (bb));
4578 /* To keep basic block numbers in sync between debug and non-debug
4579 compilations, we have to rotate blocks here. Consider that we
4580 started from (a,b)->d, (c,d)->e, and d contained only debug
4581 insns. It would have been removed before if the debug insns
4582 weren't there, so we'd have split e rather than d. So what we do
4583 now is to swap the block numbers of new_bb and
4584 single_succ(new_bb) == e, so that the insns that were in e before
4585 get the new block number. */
4587 if (MAY_HAVE_DEBUG_INSNS)
4589 basic_block succ;
4590 insn_t insn = sel_bb_head (new_bb);
4591 insn_t last;
4593 if (DEBUG_INSN_P (insn)
4594 && single_succ_p (new_bb)
4595 && (succ = single_succ (new_bb))
4596 && succ != EXIT_BLOCK_PTR_FOR_FN (cfun)
4597 && DEBUG_INSN_P ((last = sel_bb_end (new_bb))))
4599 while (insn != last && (DEBUG_INSN_P (insn) || NOTE_P (insn)))
4600 insn = NEXT_INSN (insn);
4602 if (insn == last)
4604 sel_global_bb_info_def gbi;
4605 sel_region_bb_info_def rbi;
4607 if (sched_verbose >= 2)
4608 sel_print ("Swapping block ids %i and %i\n",
4609 new_bb->index, succ->index);
4611 std::swap (new_bb->index, succ->index);
4613 SET_BASIC_BLOCK_FOR_FN (cfun, new_bb->index, new_bb);
4614 SET_BASIC_BLOCK_FOR_FN (cfun, succ->index, succ);
4616 memcpy (&gbi, SEL_GLOBAL_BB_INFO (new_bb), sizeof (gbi));
4617 memcpy (SEL_GLOBAL_BB_INFO (new_bb), SEL_GLOBAL_BB_INFO (succ),
4618 sizeof (gbi));
4619 memcpy (SEL_GLOBAL_BB_INFO (succ), &gbi, sizeof (gbi));
4621 memcpy (&rbi, SEL_REGION_BB_INFO (new_bb), sizeof (rbi));
4622 memcpy (SEL_REGION_BB_INFO (new_bb), SEL_REGION_BB_INFO (succ),
4623 sizeof (rbi));
4624 memcpy (SEL_REGION_BB_INFO (succ), &rbi, sizeof (rbi));
4626 std::swap (BLOCK_TO_BB (new_bb->index),
4627 BLOCK_TO_BB (succ->index));
4629 std::swap (CONTAINING_RGN (new_bb->index),
4630 CONTAINING_RGN (succ->index));
4632 for (int i = 0; i < current_nr_blocks; i++)
4633 if (BB_TO_BLOCK (i) == succ->index)
4634 BB_TO_BLOCK (i) = new_bb->index;
4635 else if (BB_TO_BLOCK (i) == new_bb->index)
4636 BB_TO_BLOCK (i) = succ->index;
4638 FOR_BB_INSNS (new_bb, insn)
4639 if (INSN_P (insn))
4640 EXPR_ORIG_BB_INDEX (INSN_EXPR (insn)) = new_bb->index;
4642 FOR_BB_INSNS (succ, insn)
4643 if (INSN_P (insn))
4644 EXPR_ORIG_BB_INDEX (INSN_EXPR (insn)) = succ->index;
4646 if (bitmap_clear_bit (code_motion_visited_blocks, new_bb->index))
4647 bitmap_set_bit (code_motion_visited_blocks, succ->index);
4649 gcc_assert (LABEL_P (BB_HEAD (new_bb))
4650 && LABEL_P (BB_HEAD (succ)));
4652 if (sched_verbose >= 4)
4653 sel_print ("Swapping code labels %i and %i\n",
4654 CODE_LABEL_NUMBER (BB_HEAD (new_bb)),
4655 CODE_LABEL_NUMBER (BB_HEAD (succ)));
4657 std::swap (CODE_LABEL_NUMBER (BB_HEAD (new_bb)),
4658 CODE_LABEL_NUMBER (BB_HEAD (succ)));
4663 return bb;
4666 /* Return insn after which we must insert bookkeeping code for path(s) incoming
4667 into E2->dest, except from E1->src. If the returned insn immediately
4668 precedes a fence, assign that fence to *FENCE_TO_REWIND. */
4669 static insn_t
4670 find_place_for_bookkeeping (edge e1, edge e2, fence_t *fence_to_rewind)
4672 insn_t place_to_insert;
4673 /* Find a basic block that can hold bookkeeping. If it can be found, do not
4674 create new basic block, but insert bookkeeping there. */
4675 basic_block book_block = find_block_for_bookkeeping (e1, e2, FALSE);
4677 if (book_block)
4679 place_to_insert = BB_END (book_block);
4681 /* Don't use a block containing only debug insns for
4682 bookkeeping, this causes scheduling differences between debug
4683 and non-debug compilations, for the block would have been
4684 removed already. */
4685 if (DEBUG_INSN_P (place_to_insert))
4687 rtx_insn *insn = sel_bb_head (book_block);
4689 while (insn != place_to_insert &&
4690 (DEBUG_INSN_P (insn) || NOTE_P (insn)))
4691 insn = NEXT_INSN (insn);
4693 if (insn == place_to_insert)
4694 book_block = NULL;
4698 if (!book_block)
4700 book_block = create_block_for_bookkeeping (e1, e2);
4701 place_to_insert = BB_END (book_block);
4702 if (sched_verbose >= 9)
4703 sel_print ("New block is %i, split from bookkeeping block %i\n",
4704 EDGE_SUCC (book_block, 0)->dest->index, book_block->index);
4706 else
4708 if (sched_verbose >= 9)
4709 sel_print ("Pre-existing bookkeeping block is %i\n", book_block->index);
4712 *fence_to_rewind = NULL;
4713 /* If basic block ends with a jump, insert bookkeeping code right before it.
4714 Notice if we are crossing a fence when taking PREV_INSN. */
4715 if (INSN_P (place_to_insert) && control_flow_insn_p (place_to_insert))
4717 *fence_to_rewind = flist_lookup (fences, place_to_insert);
4718 place_to_insert = PREV_INSN (place_to_insert);
4721 return place_to_insert;
4724 /* Find a proper seqno for bookkeeing insn inserted at PLACE_TO_INSERT
4725 for JOIN_POINT. */
4726 static int
4727 find_seqno_for_bookkeeping (insn_t place_to_insert, insn_t join_point)
4729 int seqno;
4731 /* Check if we are about to insert bookkeeping copy before a jump, and use
4732 jump's seqno for the copy; otherwise, use JOIN_POINT's seqno. */
4733 rtx_insn *next = NEXT_INSN (place_to_insert);
4734 if (INSN_P (next)
4735 && JUMP_P (next)
4736 && BLOCK_FOR_INSN (next) == BLOCK_FOR_INSN (place_to_insert))
4738 gcc_assert (INSN_SCHED_TIMES (next) == 0);
4739 seqno = INSN_SEQNO (next);
4741 else if (INSN_SEQNO (join_point) > 0)
4742 seqno = INSN_SEQNO (join_point);
4743 else
4745 seqno = get_seqno_by_preds (place_to_insert);
4747 /* Sometimes the fences can move in such a way that there will be
4748 no instructions with positive seqno around this bookkeeping.
4749 This means that there will be no way to get to it by a regular
4750 fence movement. Never mind because we pick up such pieces for
4751 rescheduling anyways, so any positive value will do for now. */
4752 if (seqno < 0)
4754 gcc_assert (pipelining_p);
4755 seqno = 1;
4759 gcc_assert (seqno > 0);
4760 return seqno;
4763 /* Insert bookkeeping copy of C_EXPS's insn after PLACE_TO_INSERT, assigning
4764 NEW_SEQNO to it. Return created insn. */
4765 static insn_t
4766 emit_bookkeeping_insn (insn_t place_to_insert, expr_t c_expr, int new_seqno)
4768 rtx_insn *new_insn_rtx = create_copy_of_insn_rtx (EXPR_INSN_RTX (c_expr));
4770 vinsn_t new_vinsn
4771 = create_vinsn_from_insn_rtx (new_insn_rtx,
4772 VINSN_UNIQUE_P (EXPR_VINSN (c_expr)));
4774 insn_t new_insn = emit_insn_from_expr_after (c_expr, new_vinsn, new_seqno,
4775 place_to_insert);
4777 INSN_SCHED_TIMES (new_insn) = 0;
4778 bitmap_set_bit (current_copies, INSN_UID (new_insn));
4780 return new_insn;
4783 /* Generate a bookkeeping copy of C_EXPR's insn for path(s) incoming into to
4784 E2->dest, except from E1->src (there may be a sequence of empty blocks
4785 between E1->src and E2->dest). Return block containing the copy.
4786 All scheduler data is initialized for the newly created insn. */
4787 static basic_block
4788 generate_bookkeeping_insn (expr_t c_expr, edge e1, edge e2)
4790 insn_t join_point, place_to_insert, new_insn;
4791 int new_seqno;
4792 bool need_to_exchange_data_sets;
4793 fence_t fence_to_rewind;
4795 if (sched_verbose >= 4)
4796 sel_print ("Generating bookkeeping insn (%d->%d)\n", e1->src->index,
4797 e2->dest->index);
4799 join_point = sel_bb_head (e2->dest);
4800 place_to_insert = find_place_for_bookkeeping (e1, e2, &fence_to_rewind);
4801 new_seqno = find_seqno_for_bookkeeping (place_to_insert, join_point);
4802 need_to_exchange_data_sets
4803 = sel_bb_empty_p (BLOCK_FOR_INSN (place_to_insert));
4805 new_insn = emit_bookkeeping_insn (place_to_insert, c_expr, new_seqno);
4807 if (fence_to_rewind)
4808 FENCE_INSN (fence_to_rewind) = new_insn;
4810 /* When inserting bookkeeping insn in new block, av sets should be
4811 following: old basic block (that now holds bookkeeping) data sets are
4812 the same as was before generation of bookkeeping, and new basic block
4813 (that now hold all other insns of old basic block) data sets are
4814 invalid. So exchange data sets for these basic blocks as sel_split_block
4815 mistakenly exchanges them in this case. Cannot do it earlier because
4816 when single instruction is added to new basic block it should hold NULL
4817 lv_set. */
4818 if (need_to_exchange_data_sets)
4819 exchange_data_sets (BLOCK_FOR_INSN (new_insn),
4820 BLOCK_FOR_INSN (join_point));
4822 stat_bookkeeping_copies++;
4823 return BLOCK_FOR_INSN (new_insn);
4826 /* Remove from AV_PTR all insns that may need bookkeeping when scheduling
4827 on FENCE, but we are unable to copy them. */
4828 static void
4829 remove_insns_that_need_bookkeeping (fence_t fence, av_set_t *av_ptr)
4831 expr_t expr;
4832 av_set_iterator i;
4834 /* An expression does not need bookkeeping if it is available on all paths
4835 from current block to original block and current block dominates
4836 original block. We check availability on all paths by examining
4837 EXPR_SPEC; this is not equivalent, because it may be positive even
4838 if expr is available on all paths (but if expr is not available on
4839 any path, EXPR_SPEC will be positive). */
4841 FOR_EACH_EXPR_1 (expr, i, av_ptr)
4843 if (!control_flow_insn_p (EXPR_INSN_RTX (expr))
4844 && (!bookkeeping_p || VINSN_UNIQUE_P (EXPR_VINSN (expr)))
4845 && (EXPR_SPEC (expr)
4846 || !EXPR_ORIG_BB_INDEX (expr)
4847 || !dominated_by_p (CDI_DOMINATORS,
4848 BASIC_BLOCK_FOR_FN (cfun,
4849 EXPR_ORIG_BB_INDEX (expr)),
4850 BLOCK_FOR_INSN (FENCE_INSN (fence)))))
4852 if (sched_verbose >= 4)
4853 sel_print ("Expr %d removed because it would need bookkeeping, which "
4854 "cannot be created\n", INSN_UID (EXPR_INSN_RTX (expr)));
4855 av_set_iter_remove (&i);
4860 /* Moving conditional jump through some instructions.
4862 Consider example:
4864 ... <- current scheduling point
4865 NOTE BASIC BLOCK: <- bb header
4866 (p8) add r14=r14+0x9;;
4867 (p8) mov [r14]=r23
4868 (!p8) jump L1;;
4869 NOTE BASIC BLOCK:
4872 We can schedule jump one cycle earlier, than mov, because they cannot be
4873 executed together as their predicates are mutually exclusive.
4875 This is done in this way: first, new fallthrough basic block is created
4876 after jump (it is always can be done, because there already should be a
4877 fallthrough block, where control flow goes in case of predicate being true -
4878 in our example; otherwise there should be a dependence between those
4879 instructions and jump and we cannot schedule jump right now);
4880 next, all instructions between jump and current scheduling point are moved
4881 to this new block. And the result is this:
4883 NOTE BASIC BLOCK:
4884 (!p8) jump L1 <- current scheduling point
4885 NOTE BASIC BLOCK: <- bb header
4886 (p8) add r14=r14+0x9;;
4887 (p8) mov [r14]=r23
4888 NOTE BASIC BLOCK:
4891 static void
4892 move_cond_jump (rtx_insn *insn, bnd_t bnd)
4894 edge ft_edge;
4895 basic_block block_from, block_next, block_new, block_bnd, bb;
4896 rtx_insn *next, *prev, *link, *head;
4898 block_from = BLOCK_FOR_INSN (insn);
4899 block_bnd = BLOCK_FOR_INSN (BND_TO (bnd));
4900 prev = BND_TO (bnd);
4902 /* Moving of jump should not cross any other jumps or beginnings of new
4903 basic blocks. The only exception is when we move a jump through
4904 mutually exclusive insns along fallthru edges. */
4905 if (flag_checking && block_from != block_bnd)
4907 bb = block_from;
4908 for (link = PREV_INSN (insn); link != PREV_INSN (prev);
4909 link = PREV_INSN (link))
4911 if (INSN_P (link))
4912 gcc_assert (sched_insns_conditions_mutex_p (insn, link));
4913 if (BLOCK_FOR_INSN (link) && BLOCK_FOR_INSN (link) != bb)
4915 gcc_assert (single_pred (bb) == BLOCK_FOR_INSN (link));
4916 bb = BLOCK_FOR_INSN (link);
4921 /* Jump is moved to the boundary. */
4922 next = PREV_INSN (insn);
4923 BND_TO (bnd) = insn;
4925 ft_edge = find_fallthru_edge_from (block_from);
4926 block_next = ft_edge->dest;
4927 /* There must be a fallthrough block (or where should go
4928 control flow in case of false jump predicate otherwise?). */
4929 gcc_assert (block_next);
4931 /* Create new empty basic block after source block. */
4932 block_new = sel_split_edge (ft_edge);
4933 gcc_assert (block_new->next_bb == block_next
4934 && block_from->next_bb == block_new);
4936 /* Move all instructions except INSN to BLOCK_NEW. */
4937 bb = block_bnd;
4938 head = BB_HEAD (block_new);
4939 while (bb != block_from->next_bb)
4941 rtx_insn *from, *to;
4942 from = bb == block_bnd ? prev : sel_bb_head (bb);
4943 to = bb == block_from ? next : sel_bb_end (bb);
4945 /* The jump being moved can be the first insn in the block.
4946 In this case we don't have to move anything in this block. */
4947 if (NEXT_INSN (to) != from)
4949 reorder_insns (from, to, head);
4951 for (link = to; link != head; link = PREV_INSN (link))
4952 EXPR_ORIG_BB_INDEX (INSN_EXPR (link)) = block_new->index;
4953 head = to;
4956 /* Cleanup possibly empty blocks left. */
4957 block_next = bb->next_bb;
4958 if (bb != block_from)
4959 tidy_control_flow (bb, false);
4960 bb = block_next;
4963 /* Assert there is no jump to BLOCK_NEW, only fallthrough edge. */
4964 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (BB_HEAD (block_new)));
4966 gcc_assert (!sel_bb_empty_p (block_from)
4967 && !sel_bb_empty_p (block_new));
4969 /* Update data sets for BLOCK_NEW to represent that INSN and
4970 instructions from the other branch of INSN is no longer
4971 available at BLOCK_NEW. */
4972 BB_AV_LEVEL (block_new) = global_level;
4973 gcc_assert (BB_LV_SET (block_new) == NULL);
4974 BB_LV_SET (block_new) = get_clear_regset_from_pool ();
4975 update_data_sets (sel_bb_head (block_new));
4977 /* INSN is a new basic block header - so prepare its data
4978 structures and update availability and liveness sets. */
4979 update_data_sets (insn);
4981 if (sched_verbose >= 4)
4982 sel_print ("Moving jump %d\n", INSN_UID (insn));
4985 /* Remove nops generated during move_op for preventing removal of empty
4986 basic blocks. */
4987 static void
4988 remove_temp_moveop_nops (bool full_tidying)
4990 int i;
4991 insn_t insn;
4993 FOR_EACH_VEC_ELT (vec_temp_moveop_nops, i, insn)
4995 gcc_assert (INSN_NOP_P (insn));
4996 return_nop_to_pool (insn, full_tidying);
4999 /* Empty the vector. */
5000 if (vec_temp_moveop_nops.length () > 0)
5001 vec_temp_moveop_nops.block_remove (0, vec_temp_moveop_nops.length ());
5004 /* Records the maximal UID before moving up an instruction. Used for
5005 distinguishing between bookkeeping copies and original insns. */
5006 static int max_uid_before_move_op = 0;
5008 /* When true, we're always scheduling next insn on the already scheduled code
5009 to get the right insn data for the following bundling or other passes. */
5010 static int force_next_insn = 0;
5012 /* Remove from AV_VLIW_P all instructions but next when debug counter
5013 tells us so. Next instruction is fetched from BNDS. */
5014 static void
5015 remove_insns_for_debug (blist_t bnds, av_set_t *av_vliw_p)
5017 if (! dbg_cnt (sel_sched_insn_cnt) || force_next_insn)
5018 /* Leave only the next insn in av_vliw. */
5020 av_set_iterator av_it;
5021 expr_t expr;
5022 bnd_t bnd = BLIST_BND (bnds);
5023 insn_t next = BND_TO (bnd);
5025 gcc_assert (BLIST_NEXT (bnds) == NULL);
5027 FOR_EACH_EXPR_1 (expr, av_it, av_vliw_p)
5028 if (EXPR_INSN_RTX (expr) != next)
5029 av_set_iter_remove (&av_it);
5033 /* Compute available instructions on BNDS. FENCE is the current fence. Write
5034 the computed set to *AV_VLIW_P. */
5035 static void
5036 compute_av_set_on_boundaries (fence_t fence, blist_t bnds, av_set_t *av_vliw_p)
5038 if (sched_verbose >= 2)
5040 sel_print ("Boundaries: ");
5041 dump_blist (bnds);
5042 sel_print ("\n");
5045 for (; bnds; bnds = BLIST_NEXT (bnds))
5047 bnd_t bnd = BLIST_BND (bnds);
5048 av_set_t av1_copy;
5049 insn_t bnd_to = BND_TO (bnd);
5051 /* Rewind BND->TO to the basic block header in case some bookkeeping
5052 instructions were inserted before BND->TO and it needs to be
5053 adjusted. */
5054 if (sel_bb_head_p (bnd_to))
5055 gcc_assert (INSN_SCHED_TIMES (bnd_to) == 0);
5056 else
5057 while (INSN_SCHED_TIMES (PREV_INSN (bnd_to)) == 0)
5059 bnd_to = PREV_INSN (bnd_to);
5060 if (sel_bb_head_p (bnd_to))
5061 break;
5064 if (BND_TO (bnd) != bnd_to)
5066 gcc_assert (FENCE_INSN (fence) == BND_TO (bnd));
5067 FENCE_INSN (fence) = bnd_to;
5068 BND_TO (bnd) = bnd_to;
5071 av_set_clear (&BND_AV (bnd));
5072 BND_AV (bnd) = compute_av_set (BND_TO (bnd), NULL, 0, true);
5074 av_set_clear (&BND_AV1 (bnd));
5075 BND_AV1 (bnd) = av_set_copy (BND_AV (bnd));
5077 moveup_set_inside_insn_group (&BND_AV1 (bnd), NULL);
5079 av1_copy = av_set_copy (BND_AV1 (bnd));
5080 av_set_union_and_clear (av_vliw_p, &av1_copy, NULL);
5083 if (sched_verbose >= 2)
5085 sel_print ("Available exprs (vliw form): ");
5086 dump_av_set (*av_vliw_p);
5087 sel_print ("\n");
5091 /* Calculate the sequential av set on BND corresponding to the EXPR_VLIW
5092 expression. When FOR_MOVEOP is true, also replace the register of
5093 expressions found with the register from EXPR_VLIW. */
5094 static av_set_t
5095 find_sequential_best_exprs (bnd_t bnd, expr_t expr_vliw, bool for_moveop)
5097 av_set_t expr_seq = NULL;
5098 expr_t expr;
5099 av_set_iterator i;
5101 FOR_EACH_EXPR (expr, i, BND_AV (bnd))
5103 if (equal_after_moveup_path_p (expr, NULL, expr_vliw))
5105 if (for_moveop)
5107 /* The sequential expression has the right form to pass
5108 to move_op except when renaming happened. Put the
5109 correct register in EXPR then. */
5110 if (EXPR_SEPARABLE_P (expr) && REG_P (EXPR_LHS (expr)))
5112 if (expr_dest_regno (expr) != expr_dest_regno (expr_vliw))
5114 replace_dest_with_reg_in_expr (expr, EXPR_LHS (expr_vliw));
5115 stat_renamed_scheduled++;
5117 /* Also put the correct TARGET_AVAILABLE bit on the expr.
5118 This is needed when renaming came up with original
5119 register. */
5120 else if (EXPR_TARGET_AVAILABLE (expr)
5121 != EXPR_TARGET_AVAILABLE (expr_vliw))
5123 gcc_assert (EXPR_TARGET_AVAILABLE (expr_vliw) == 1);
5124 EXPR_TARGET_AVAILABLE (expr) = 1;
5127 if (EXPR_WAS_SUBSTITUTED (expr))
5128 stat_substitutions_total++;
5131 av_set_add (&expr_seq, expr);
5133 /* With substitution inside insn group, it is possible
5134 that more than one expression in expr_seq will correspond
5135 to expr_vliw. In this case, choose one as the attempt to
5136 move both leads to miscompiles. */
5137 break;
5141 if (for_moveop && sched_verbose >= 2)
5143 sel_print ("Best expression(s) (sequential form): ");
5144 dump_av_set (expr_seq);
5145 sel_print ("\n");
5148 return expr_seq;
5152 /* Move nop to previous block. */
5153 static void ATTRIBUTE_UNUSED
5154 move_nop_to_previous_block (insn_t nop, basic_block prev_bb)
5156 insn_t prev_insn, next_insn;
5158 gcc_assert (sel_bb_head_p (nop)
5159 && prev_bb == BLOCK_FOR_INSN (nop)->prev_bb);
5160 rtx_note *note = bb_note (BLOCK_FOR_INSN (nop));
5161 prev_insn = sel_bb_end (prev_bb);
5162 next_insn = NEXT_INSN (nop);
5163 gcc_assert (prev_insn != NULL_RTX
5164 && PREV_INSN (note) == prev_insn);
5166 SET_NEXT_INSN (prev_insn) = nop;
5167 SET_PREV_INSN (nop) = prev_insn;
5169 SET_PREV_INSN (note) = nop;
5170 SET_NEXT_INSN (note) = next_insn;
5172 SET_NEXT_INSN (nop) = note;
5173 SET_PREV_INSN (next_insn) = note;
5175 BB_END (prev_bb) = nop;
5176 BLOCK_FOR_INSN (nop) = prev_bb;
5179 /* Prepare a place to insert the chosen expression on BND. */
5180 static insn_t
5181 prepare_place_to_insert (bnd_t bnd)
5183 insn_t place_to_insert;
5185 /* Init place_to_insert before calling move_op, as the later
5186 can possibly remove BND_TO (bnd). */
5187 if (/* If this is not the first insn scheduled. */
5188 BND_PTR (bnd))
5190 /* Add it after last scheduled. */
5191 place_to_insert = ILIST_INSN (BND_PTR (bnd));
5192 if (DEBUG_INSN_P (place_to_insert))
5194 ilist_t l = BND_PTR (bnd);
5195 while ((l = ILIST_NEXT (l)) &&
5196 DEBUG_INSN_P (ILIST_INSN (l)))
5198 if (!l)
5199 place_to_insert = NULL;
5202 else
5203 place_to_insert = NULL;
5205 if (!place_to_insert)
5207 /* Add it before BND_TO. The difference is in the
5208 basic block, where INSN will be added. */
5209 place_to_insert = get_nop_from_pool (BND_TO (bnd));
5210 gcc_assert (BLOCK_FOR_INSN (place_to_insert)
5211 == BLOCK_FOR_INSN (BND_TO (bnd)));
5214 return place_to_insert;
5217 /* Find original instructions for EXPR_SEQ and move it to BND boundary.
5218 Return the expression to emit in C_EXPR. */
5219 static bool
5220 move_exprs_to_boundary (bnd_t bnd, expr_t expr_vliw,
5221 av_set_t expr_seq, expr_t c_expr)
5223 bool b, should_move;
5224 unsigned book_uid;
5225 bitmap_iterator bi;
5226 int n_bookkeeping_copies_before_moveop;
5228 /* Make a move. This call will remove the original operation,
5229 insert all necessary bookkeeping instructions and update the
5230 data sets. After that all we have to do is add the operation
5231 at before BND_TO (BND). */
5232 n_bookkeeping_copies_before_moveop = stat_bookkeeping_copies;
5233 max_uid_before_move_op = get_max_uid ();
5234 bitmap_clear (current_copies);
5235 bitmap_clear (current_originators);
5237 b = move_op (BND_TO (bnd), expr_seq, expr_vliw,
5238 get_dest_from_orig_ops (expr_seq), c_expr, &should_move);
5240 /* We should be able to find the expression we've chosen for
5241 scheduling. */
5242 gcc_assert (b);
5244 if (stat_bookkeeping_copies > n_bookkeeping_copies_before_moveop)
5245 stat_insns_needed_bookkeeping++;
5247 EXECUTE_IF_SET_IN_BITMAP (current_copies, 0, book_uid, bi)
5249 unsigned uid;
5250 bitmap_iterator bi;
5252 /* We allocate these bitmaps lazily. */
5253 if (! INSN_ORIGINATORS_BY_UID (book_uid))
5254 INSN_ORIGINATORS_BY_UID (book_uid) = BITMAP_ALLOC (NULL);
5256 bitmap_copy (INSN_ORIGINATORS_BY_UID (book_uid),
5257 current_originators);
5259 /* Transitively add all originators' originators. */
5260 EXECUTE_IF_SET_IN_BITMAP (current_originators, 0, uid, bi)
5261 if (INSN_ORIGINATORS_BY_UID (uid))
5262 bitmap_ior_into (INSN_ORIGINATORS_BY_UID (book_uid),
5263 INSN_ORIGINATORS_BY_UID (uid));
5266 return should_move;
5270 /* Debug a DFA state as an array of bytes. */
5271 static void
5272 debug_state (state_t state)
5274 unsigned char *p;
5275 unsigned int i, size = dfa_state_size;
5277 sel_print ("state (%u):", size);
5278 for (i = 0, p = (unsigned char *) state; i < size; i++)
5279 sel_print (" %d", p[i]);
5280 sel_print ("\n");
5283 /* Advance state on FENCE with INSN. Return true if INSN is
5284 an ASM, and we should advance state once more. */
5285 static bool
5286 advance_state_on_fence (fence_t fence, insn_t insn)
5288 bool asm_p;
5290 if (recog_memoized (insn) >= 0)
5292 int res;
5293 state_t temp_state = alloca (dfa_state_size);
5295 gcc_assert (!INSN_ASM_P (insn));
5296 asm_p = false;
5298 memcpy (temp_state, FENCE_STATE (fence), dfa_state_size);
5299 res = state_transition (FENCE_STATE (fence), insn);
5300 gcc_assert (res < 0);
5302 if (memcmp (temp_state, FENCE_STATE (fence), dfa_state_size))
5304 FENCE_ISSUED_INSNS (fence)++;
5306 /* We should never issue more than issue_rate insns. */
5307 if (FENCE_ISSUED_INSNS (fence) > issue_rate)
5308 gcc_unreachable ();
5311 else
5313 /* This could be an ASM insn which we'd like to schedule
5314 on the next cycle. */
5315 asm_p = INSN_ASM_P (insn);
5316 if (!FENCE_STARTS_CYCLE_P (fence) && asm_p)
5317 advance_one_cycle (fence);
5320 if (sched_verbose >= 2)
5321 debug_state (FENCE_STATE (fence));
5322 if (!DEBUG_INSN_P (insn))
5323 FENCE_STARTS_CYCLE_P (fence) = 0;
5324 FENCE_ISSUE_MORE (fence) = can_issue_more;
5325 return asm_p;
5328 /* Update FENCE on which INSN was scheduled and this INSN, too. NEED_STALL
5329 is nonzero if we need to stall after issuing INSN. */
5330 static void
5331 update_fence_and_insn (fence_t fence, insn_t insn, int need_stall)
5333 bool asm_p;
5335 /* First, reflect that something is scheduled on this fence. */
5336 asm_p = advance_state_on_fence (fence, insn);
5337 FENCE_LAST_SCHEDULED_INSN (fence) = insn;
5338 vec_safe_push (FENCE_EXECUTING_INSNS (fence), insn);
5339 if (SCHED_GROUP_P (insn))
5341 FENCE_SCHED_NEXT (fence) = INSN_SCHED_NEXT (insn);
5342 SCHED_GROUP_P (insn) = 0;
5344 else
5345 FENCE_SCHED_NEXT (fence) = NULL;
5346 if (INSN_UID (insn) < FENCE_READY_TICKS_SIZE (fence))
5347 FENCE_READY_TICKS (fence) [INSN_UID (insn)] = 0;
5349 /* Set instruction scheduling info. This will be used in bundling,
5350 pipelining, tick computations etc. */
5351 ++INSN_SCHED_TIMES (insn);
5352 EXPR_TARGET_AVAILABLE (INSN_EXPR (insn)) = true;
5353 EXPR_ORIG_SCHED_CYCLE (INSN_EXPR (insn)) = FENCE_CYCLE (fence);
5354 INSN_AFTER_STALL_P (insn) = FENCE_AFTER_STALL_P (fence);
5355 INSN_SCHED_CYCLE (insn) = FENCE_CYCLE (fence);
5357 /* This does not account for adjust_cost hooks, just add the biggest
5358 constant the hook may add to the latency. TODO: make this
5359 a target dependent constant. */
5360 INSN_READY_CYCLE (insn)
5361 = INSN_SCHED_CYCLE (insn) + (INSN_CODE (insn) < 0
5363 : maximal_insn_latency (insn) + 1);
5365 /* Change these fields last, as they're used above. */
5366 FENCE_AFTER_STALL_P (fence) = 0;
5367 if (asm_p || need_stall)
5368 advance_one_cycle (fence);
5370 /* Indicate that we've scheduled something on this fence. */
5371 FENCE_SCHEDULED_P (fence) = true;
5372 scheduled_something_on_previous_fence = true;
5374 /* Print debug information when insn's fields are updated. */
5375 if (sched_verbose >= 2)
5377 sel_print ("Scheduling insn: ");
5378 dump_insn_1 (insn, 1);
5379 sel_print ("\n");
5383 /* Update boundary BND (and, if needed, FENCE) with INSN, remove the
5384 old boundary from BNDSP, add new boundaries to BNDS_TAIL_P and
5385 return it. */
5386 static blist_t *
5387 update_boundaries (fence_t fence, bnd_t bnd, insn_t insn, blist_t *bndsp,
5388 blist_t *bnds_tailp)
5390 succ_iterator si;
5391 insn_t succ;
5393 advance_deps_context (BND_DC (bnd), insn);
5394 FOR_EACH_SUCC_1 (succ, si, insn,
5395 SUCCS_NORMAL | SUCCS_SKIP_TO_LOOP_EXITS)
5397 ilist_t ptr = ilist_copy (BND_PTR (bnd));
5399 ilist_add (&ptr, insn);
5401 if (DEBUG_INSN_P (insn) && sel_bb_end_p (insn)
5402 && is_ineligible_successor (succ, ptr))
5404 ilist_clear (&ptr);
5405 continue;
5408 if (FENCE_INSN (fence) == insn && !sel_bb_end_p (insn))
5410 if (sched_verbose >= 9)
5411 sel_print ("Updating fence insn from %i to %i\n",
5412 INSN_UID (insn), INSN_UID (succ));
5413 FENCE_INSN (fence) = succ;
5415 blist_add (bnds_tailp, succ, ptr, BND_DC (bnd));
5416 bnds_tailp = &BLIST_NEXT (*bnds_tailp);
5419 blist_remove (bndsp);
5420 return bnds_tailp;
5423 /* Schedule EXPR_VLIW on BND. Return the insn emitted. */
5424 static insn_t
5425 schedule_expr_on_boundary (bnd_t bnd, expr_t expr_vliw, int seqno)
5427 av_set_t expr_seq;
5428 expr_t c_expr = XALLOCA (expr_def);
5429 insn_t place_to_insert;
5430 insn_t insn;
5431 bool should_move;
5433 expr_seq = find_sequential_best_exprs (bnd, expr_vliw, true);
5435 /* In case of scheduling a jump skipping some other instructions,
5436 prepare CFG. After this, jump is at the boundary and can be
5437 scheduled as usual insn by MOVE_OP. */
5438 if (vinsn_cond_branch_p (EXPR_VINSN (expr_vliw)))
5440 insn = EXPR_INSN_RTX (expr_vliw);
5442 /* Speculative jumps are not handled. */
5443 if (insn != BND_TO (bnd)
5444 && !sel_insn_is_speculation_check (insn))
5445 move_cond_jump (insn, bnd);
5448 /* Find a place for C_EXPR to schedule. */
5449 place_to_insert = prepare_place_to_insert (bnd);
5450 should_move = move_exprs_to_boundary (bnd, expr_vliw, expr_seq, c_expr);
5451 clear_expr (c_expr);
5453 /* Add the instruction. The corner case to care about is when
5454 the expr_seq set has more than one expr, and we chose the one that
5455 is not equal to expr_vliw. Then expr_vliw may be insn in stream, and
5456 we can't use it. Generate the new vinsn. */
5457 if (INSN_IN_STREAM_P (EXPR_INSN_RTX (expr_vliw)))
5459 vinsn_t vinsn_new;
5461 vinsn_new = vinsn_copy (EXPR_VINSN (expr_vliw), false);
5462 change_vinsn_in_expr (expr_vliw, vinsn_new);
5463 should_move = false;
5465 if (should_move)
5466 insn = sel_move_insn (expr_vliw, seqno, place_to_insert);
5467 else
5468 insn = emit_insn_from_expr_after (expr_vliw, NULL, seqno,
5469 place_to_insert);
5471 /* Return the nops generated for preserving of data sets back
5472 into pool. */
5473 if (INSN_NOP_P (place_to_insert))
5474 return_nop_to_pool (place_to_insert, !DEBUG_INSN_P (insn));
5475 remove_temp_moveop_nops (!DEBUG_INSN_P (insn));
5477 av_set_clear (&expr_seq);
5479 /* Save the expression scheduled so to reset target availability if we'll
5480 meet it later on the same fence. */
5481 if (EXPR_WAS_RENAMED (expr_vliw))
5482 vinsn_vec_add (&vec_target_unavailable_vinsns, INSN_EXPR (insn));
5484 /* Check that the recent movement didn't destroyed loop
5485 structure. */
5486 gcc_assert (!pipelining_p
5487 || current_loop_nest == NULL
5488 || loop_latch_edge (current_loop_nest));
5489 return insn;
5492 /* Stall for N cycles on FENCE. */
5493 static void
5494 stall_for_cycles (fence_t fence, int n)
5496 int could_more;
5498 could_more = n > 1 || FENCE_ISSUED_INSNS (fence) < issue_rate;
5499 while (n--)
5500 advance_one_cycle (fence);
5501 if (could_more)
5502 FENCE_AFTER_STALL_P (fence) = 1;
5505 /* Gather a parallel group of insns at FENCE and assign their seqno
5506 to SEQNO. All scheduled insns are gathered in SCHEDULED_INSNS_TAILPP
5507 list for later recalculation of seqnos. */
5508 static void
5509 fill_insns (fence_t fence, int seqno, ilist_t **scheduled_insns_tailpp)
5511 blist_t bnds = NULL, *bnds_tailp;
5512 av_set_t av_vliw = NULL;
5513 insn_t insn = FENCE_INSN (fence);
5515 if (sched_verbose >= 2)
5516 sel_print ("Starting fill_insns for insn %d, cycle %d\n",
5517 INSN_UID (insn), FENCE_CYCLE (fence));
5519 blist_add (&bnds, insn, NULL, FENCE_DC (fence));
5520 bnds_tailp = &BLIST_NEXT (bnds);
5521 set_target_context (FENCE_TC (fence));
5522 can_issue_more = FENCE_ISSUE_MORE (fence);
5523 target_bb = INSN_BB (insn);
5525 /* Do while we can add any operation to the current group. */
5528 blist_t *bnds_tailp1, *bndsp;
5529 expr_t expr_vliw;
5530 int need_stall = false;
5531 int was_stall = 0, scheduled_insns = 0;
5532 int max_insns = pipelining_p ? issue_rate : 2 * issue_rate;
5533 int max_stall = pipelining_p ? 1 : 3;
5534 bool last_insn_was_debug = false;
5535 bool was_debug_bb_end_p = false;
5537 compute_av_set_on_boundaries (fence, bnds, &av_vliw);
5538 remove_insns_that_need_bookkeeping (fence, &av_vliw);
5539 remove_insns_for_debug (bnds, &av_vliw);
5541 /* Return early if we have nothing to schedule. */
5542 if (av_vliw == NULL)
5543 break;
5545 /* Choose the best expression and, if needed, destination register
5546 for it. */
5549 expr_vliw = find_best_expr (&av_vliw, bnds, fence, &need_stall);
5550 if (! expr_vliw && need_stall)
5552 /* All expressions required a stall. Do not recompute av sets
5553 as we'll get the same answer (modulo the insns between
5554 the fence and its boundary, which will not be available for
5555 pipelining).
5556 If we are going to stall for too long, break to recompute av
5557 sets and bring more insns for pipelining. */
5558 was_stall++;
5559 if (need_stall <= 3)
5560 stall_for_cycles (fence, need_stall);
5561 else
5563 stall_for_cycles (fence, 1);
5564 break;
5568 while (! expr_vliw && need_stall);
5570 /* Now either we've selected expr_vliw or we have nothing to schedule. */
5571 if (!expr_vliw)
5573 av_set_clear (&av_vliw);
5574 break;
5577 bndsp = &bnds;
5578 bnds_tailp1 = bnds_tailp;
5581 /* This code will be executed only once until we'd have several
5582 boundaries per fence. */
5584 bnd_t bnd = BLIST_BND (*bndsp);
5586 if (!av_set_is_in_p (BND_AV1 (bnd), EXPR_VINSN (expr_vliw)))
5588 bndsp = &BLIST_NEXT (*bndsp);
5589 continue;
5592 insn = schedule_expr_on_boundary (bnd, expr_vliw, seqno);
5593 last_insn_was_debug = DEBUG_INSN_P (insn);
5594 if (last_insn_was_debug)
5595 was_debug_bb_end_p = (insn == BND_TO (bnd) && sel_bb_end_p (insn));
5596 update_fence_and_insn (fence, insn, need_stall);
5597 bnds_tailp = update_boundaries (fence, bnd, insn, bndsp, bnds_tailp);
5599 /* Add insn to the list of scheduled on this cycle instructions. */
5600 ilist_add (*scheduled_insns_tailpp, insn);
5601 *scheduled_insns_tailpp = &ILIST_NEXT (**scheduled_insns_tailpp);
5603 while (*bndsp != *bnds_tailp1);
5605 av_set_clear (&av_vliw);
5606 if (!last_insn_was_debug)
5607 scheduled_insns++;
5609 /* We currently support information about candidate blocks only for
5610 one 'target_bb' block. Hence we can't schedule after jump insn,
5611 as this will bring two boundaries and, hence, necessity to handle
5612 information for two or more blocks concurrently. */
5613 if ((last_insn_was_debug ? was_debug_bb_end_p : sel_bb_end_p (insn))
5614 || (was_stall
5615 && (was_stall >= max_stall
5616 || scheduled_insns >= max_insns)))
5617 break;
5619 while (bnds);
5621 gcc_assert (!FENCE_BNDS (fence));
5623 /* Update boundaries of the FENCE. */
5624 while (bnds)
5626 ilist_t ptr = BND_PTR (BLIST_BND (bnds));
5628 if (ptr)
5630 insn = ILIST_INSN (ptr);
5632 if (!ilist_is_in_p (FENCE_BNDS (fence), insn))
5633 ilist_add (&FENCE_BNDS (fence), insn);
5636 blist_remove (&bnds);
5639 /* Update target context on the fence. */
5640 reset_target_context (FENCE_TC (fence), false);
5643 /* All exprs in ORIG_OPS must have the same destination register or memory.
5644 Return that destination. */
5645 static rtx
5646 get_dest_from_orig_ops (av_set_t orig_ops)
5648 rtx dest = NULL_RTX;
5649 av_set_iterator av_it;
5650 expr_t expr;
5651 bool first_p = true;
5653 FOR_EACH_EXPR (expr, av_it, orig_ops)
5655 rtx x = EXPR_LHS (expr);
5657 if (first_p)
5659 first_p = false;
5660 dest = x;
5662 else
5663 gcc_assert (dest == x
5664 || (dest != NULL_RTX && x != NULL_RTX
5665 && rtx_equal_p (dest, x)));
5668 return dest;
5671 /* Update data sets for the bookkeeping block and record those expressions
5672 which become no longer available after inserting this bookkeeping. */
5673 static void
5674 update_and_record_unavailable_insns (basic_block book_block)
5676 av_set_iterator i;
5677 av_set_t old_av_set = NULL;
5678 expr_t cur_expr;
5679 rtx_insn *bb_end = sel_bb_end (book_block);
5681 /* First, get correct liveness in the bookkeeping block. The problem is
5682 the range between the bookeeping insn and the end of block. */
5683 update_liveness_on_insn (bb_end);
5684 if (control_flow_insn_p (bb_end))
5685 update_liveness_on_insn (PREV_INSN (bb_end));
5687 /* If there's valid av_set on BOOK_BLOCK, then there might exist another
5688 fence above, where we may choose to schedule an insn which is
5689 actually blocked from moving up with the bookkeeping we create here. */
5690 if (AV_SET_VALID_P (sel_bb_head (book_block)))
5692 old_av_set = av_set_copy (BB_AV_SET (book_block));
5693 update_data_sets (sel_bb_head (book_block));
5695 /* Traverse all the expressions in the old av_set and check whether
5696 CUR_EXPR is in new AV_SET. */
5697 FOR_EACH_EXPR (cur_expr, i, old_av_set)
5699 expr_t new_expr = av_set_lookup (BB_AV_SET (book_block),
5700 EXPR_VINSN (cur_expr));
5702 if (! new_expr
5703 /* In this case, we can just turn off the E_T_A bit, but we can't
5704 represent this information with the current vector. */
5705 || EXPR_TARGET_AVAILABLE (new_expr)
5706 != EXPR_TARGET_AVAILABLE (cur_expr))
5707 /* Unfortunately, the below code could be also fired up on
5708 separable insns, e.g. when moving insns through the new
5709 speculation check as in PR 53701. */
5710 vinsn_vec_add (&vec_bookkeeping_blocked_vinsns, cur_expr);
5713 av_set_clear (&old_av_set);
5717 /* The main effect of this function is that sparams->c_expr is merged
5718 with (or copied to) lparams->c_expr_merged. If there's only one successor,
5719 we avoid merging anything by copying sparams->c_expr to lparams->c_expr_merged.
5720 lparams->c_expr_merged is copied back to sparams->c_expr after all
5721 successors has been traversed. lparams->c_expr_local is an expr allocated
5722 on stack in the caller function, and is used if there is more than one
5723 successor.
5725 SUCC is one of the SUCCS_NORMAL successors of INSN,
5726 MOVEOP_DRV_CALL_RES is the result of call code_motion_path_driver on succ,
5727 LPARAMS and STATIC_PARAMS contain the parameters described above. */
5728 static void
5729 move_op_merge_succs (insn_t insn ATTRIBUTE_UNUSED,
5730 insn_t succ ATTRIBUTE_UNUSED,
5731 int moveop_drv_call_res,
5732 cmpd_local_params_p lparams, void *static_params)
5734 moveop_static_params_p sparams = (moveop_static_params_p) static_params;
5736 /* Nothing to do, if original expr wasn't found below. */
5737 if (moveop_drv_call_res != 1)
5738 return;
5740 /* If this is a first successor. */
5741 if (!lparams->c_expr_merged)
5743 lparams->c_expr_merged = sparams->c_expr;
5744 sparams->c_expr = lparams->c_expr_local;
5746 else
5748 /* We must merge all found expressions to get reasonable
5749 EXPR_SPEC_DONE_DS for the resulting insn. If we don't
5750 do so then we can first find the expr with epsilon
5751 speculation success probability and only then with the
5752 good probability. As a result the insn will get epsilon
5753 probability and will never be scheduled because of
5754 weakness_cutoff in find_best_expr.
5756 We call merge_expr_data here instead of merge_expr
5757 because due to speculation C_EXPR and X may have the
5758 same insns with different speculation types. And as of
5759 now such insns are considered non-equal.
5761 However, EXPR_SCHED_TIMES is different -- we must get
5762 SCHED_TIMES from a real insn, not a bookkeeping copy.
5763 We force this here. Instead, we may consider merging
5764 SCHED_TIMES to the maximum instead of minimum in the
5765 below function. */
5766 int old_times = EXPR_SCHED_TIMES (lparams->c_expr_merged);
5768 merge_expr_data (lparams->c_expr_merged, sparams->c_expr, NULL);
5769 if (EXPR_SCHED_TIMES (sparams->c_expr) == 0)
5770 EXPR_SCHED_TIMES (lparams->c_expr_merged) = old_times;
5772 clear_expr (sparams->c_expr);
5776 /* Add used regs for the successor SUCC into SPARAMS->USED_REGS.
5778 SUCC is one of the SUCCS_NORMAL successors of INSN,
5779 MOVEOP_DRV_CALL_RES is the result of call code_motion_path_driver on succ or 0,
5780 if SUCC is one of SUCCS_BACK or SUCCS_OUT.
5781 STATIC_PARAMS contain USED_REGS set. */
5782 static void
5783 fur_merge_succs (insn_t insn ATTRIBUTE_UNUSED, insn_t succ,
5784 int moveop_drv_call_res,
5785 cmpd_local_params_p lparams ATTRIBUTE_UNUSED,
5786 void *static_params)
5788 regset succ_live;
5789 fur_static_params_p sparams = (fur_static_params_p) static_params;
5791 /* Here we compute live regsets only for branches that do not lie
5792 on the code motion paths. These branches correspond to value
5793 MOVEOP_DRV_CALL_RES==0 and include SUCCS_BACK and SUCCS_OUT, though
5794 for such branches code_motion_path_driver is not called. */
5795 if (moveop_drv_call_res != 0)
5796 return;
5798 /* Mark all registers that do not meet the following condition:
5799 (3) not live on the other path of any conditional branch
5800 that is passed by the operation, in case original
5801 operations are not present on both paths of the
5802 conditional branch. */
5803 succ_live = compute_live (succ);
5804 IOR_REG_SET (sparams->used_regs, succ_live);
5807 /* This function is called after the last successor. Copies LP->C_EXPR_MERGED
5808 into SP->CEXPR. */
5809 static void
5810 move_op_after_merge_succs (cmpd_local_params_p lp, void *sparams)
5812 moveop_static_params_p sp = (moveop_static_params_p) sparams;
5814 sp->c_expr = lp->c_expr_merged;
5817 /* Track bookkeeping copies created, insns scheduled, and blocks for
5818 rescheduling when INSN is found by move_op. */
5819 static void
5820 track_scheduled_insns_and_blocks (rtx_insn *insn)
5822 /* Even if this insn can be a copy that will be removed during current move_op,
5823 we still need to count it as an originator. */
5824 bitmap_set_bit (current_originators, INSN_UID (insn));
5826 if (!bitmap_clear_bit (current_copies, INSN_UID (insn)))
5828 /* Note that original block needs to be rescheduled, as we pulled an
5829 instruction out of it. */
5830 if (INSN_SCHED_TIMES (insn) > 0)
5831 bitmap_set_bit (blocks_to_reschedule, BLOCK_FOR_INSN (insn)->index);
5832 else if (INSN_UID (insn) < first_emitted_uid && !DEBUG_INSN_P (insn))
5833 num_insns_scheduled++;
5836 /* For instructions we must immediately remove insn from the
5837 stream, so subsequent update_data_sets () won't include this
5838 insn into av_set.
5839 For expr we must make insn look like "INSN_REG (insn) := c_expr". */
5840 if (INSN_UID (insn) > max_uid_before_move_op)
5841 stat_bookkeeping_copies--;
5844 /* Emit a register-register copy for INSN if needed. Return true if
5845 emitted one. PARAMS is the move_op static parameters. */
5846 static bool
5847 maybe_emit_renaming_copy (rtx_insn *insn,
5848 moveop_static_params_p params)
5850 bool insn_emitted = false;
5851 rtx cur_reg;
5853 /* Bail out early when expression can not be renamed at all. */
5854 if (!EXPR_SEPARABLE_P (params->c_expr))
5855 return false;
5857 cur_reg = expr_dest_reg (params->c_expr);
5858 gcc_assert (cur_reg && params->dest && REG_P (params->dest));
5860 /* If original operation has expr and the register chosen for
5861 that expr is not original operation's dest reg, substitute
5862 operation's right hand side with the register chosen. */
5863 if (REGNO (params->dest) != REGNO (cur_reg))
5865 insn_t reg_move_insn, reg_move_insn_rtx;
5867 reg_move_insn_rtx = create_insn_rtx_with_rhs (INSN_VINSN (insn),
5868 params->dest);
5869 reg_move_insn = sel_gen_insn_from_rtx_after (reg_move_insn_rtx,
5870 INSN_EXPR (insn),
5871 INSN_SEQNO (insn),
5872 insn);
5873 EXPR_SPEC_DONE_DS (INSN_EXPR (reg_move_insn)) = 0;
5874 replace_dest_with_reg_in_expr (params->c_expr, params->dest);
5876 insn_emitted = true;
5877 params->was_renamed = true;
5880 return insn_emitted;
5883 /* Emit a speculative check for INSN speculated as EXPR if needed.
5884 Return true if we've emitted one. PARAMS is the move_op static
5885 parameters. */
5886 static bool
5887 maybe_emit_speculative_check (rtx_insn *insn, expr_t expr,
5888 moveop_static_params_p params)
5890 bool insn_emitted = false;
5891 insn_t x;
5892 ds_t check_ds;
5894 check_ds = get_spec_check_type_for_insn (insn, expr);
5895 if (check_ds != 0)
5897 /* A speculation check should be inserted. */
5898 x = create_speculation_check (params->c_expr, check_ds, insn);
5899 insn_emitted = true;
5901 else
5903 EXPR_SPEC_DONE_DS (INSN_EXPR (insn)) = 0;
5904 x = insn;
5907 gcc_assert (EXPR_SPEC_DONE_DS (INSN_EXPR (x)) == 0
5908 && EXPR_SPEC_TO_CHECK_DS (INSN_EXPR (x)) == 0);
5909 return insn_emitted;
5912 /* Handle transformations that leave an insn in place of original
5913 insn such as renaming/speculation. Return true if one of such
5914 transformations actually happened, and we have emitted this insn. */
5915 static bool
5916 handle_emitting_transformations (rtx_insn *insn, expr_t expr,
5917 moveop_static_params_p params)
5919 bool insn_emitted = false;
5921 insn_emitted = maybe_emit_renaming_copy (insn, params);
5922 insn_emitted |= maybe_emit_speculative_check (insn, expr, params);
5924 return insn_emitted;
5927 /* If INSN is the only insn in the basic block (not counting JUMP,
5928 which may be a jump to next insn, and DEBUG_INSNs), we want to
5929 leave a NOP there till the return to fill_insns. */
5931 static bool
5932 need_nop_to_preserve_insn_bb (rtx_insn *insn)
5934 insn_t bb_head, bb_end, bb_next, in_next;
5935 basic_block bb = BLOCK_FOR_INSN (insn);
5937 bb_head = sel_bb_head (bb);
5938 bb_end = sel_bb_end (bb);
5940 if (bb_head == bb_end)
5941 return true;
5943 while (bb_head != bb_end && DEBUG_INSN_P (bb_head))
5944 bb_head = NEXT_INSN (bb_head);
5946 if (bb_head == bb_end)
5947 return true;
5949 while (bb_head != bb_end && DEBUG_INSN_P (bb_end))
5950 bb_end = PREV_INSN (bb_end);
5952 if (bb_head == bb_end)
5953 return true;
5955 bb_next = NEXT_INSN (bb_head);
5956 while (bb_next != bb_end && DEBUG_INSN_P (bb_next))
5957 bb_next = NEXT_INSN (bb_next);
5959 if (bb_next == bb_end && JUMP_P (bb_end))
5960 return true;
5962 in_next = NEXT_INSN (insn);
5963 while (DEBUG_INSN_P (in_next))
5964 in_next = NEXT_INSN (in_next);
5966 if (IN_CURRENT_FENCE_P (in_next))
5967 return true;
5969 return false;
5972 /* Remove INSN from stream. When ONLY_DISCONNECT is true, its data
5973 is not removed but reused when INSN is re-emitted. */
5974 static void
5975 remove_insn_from_stream (rtx_insn *insn, bool only_disconnect)
5977 /* If there's only one insn in the BB, make sure that a nop is
5978 inserted into it, so the basic block won't disappear when we'll
5979 delete INSN below with sel_remove_insn. It should also survive
5980 till the return to fill_insns. */
5981 if (need_nop_to_preserve_insn_bb (insn))
5983 insn_t nop = get_nop_from_pool (insn);
5984 gcc_assert (INSN_NOP_P (nop));
5985 vec_temp_moveop_nops.safe_push (nop);
5988 sel_remove_insn (insn, only_disconnect, false);
5991 /* This function is called when original expr is found.
5992 INSN - current insn traversed, EXPR - the corresponding expr found.
5993 LPARAMS is the local parameters of code modion driver, STATIC_PARAMS
5994 is static parameters of move_op. */
5995 static void
5996 move_op_orig_expr_found (insn_t insn, expr_t expr,
5997 cmpd_local_params_p lparams ATTRIBUTE_UNUSED,
5998 void *static_params)
6000 bool only_disconnect;
6001 moveop_static_params_p params = (moveop_static_params_p) static_params;
6003 copy_expr_onside (params->c_expr, INSN_EXPR (insn));
6004 track_scheduled_insns_and_blocks (insn);
6005 handle_emitting_transformations (insn, expr, params);
6006 only_disconnect = params->uid == INSN_UID (insn);
6008 /* Mark that we've disconnected an insn. */
6009 if (only_disconnect)
6010 params->uid = -1;
6011 remove_insn_from_stream (insn, only_disconnect);
6014 /* The function is called when original expr is found.
6015 INSN - current insn traversed, EXPR - the corresponding expr found,
6016 crosses_call and original_insns in STATIC_PARAMS are updated. */
6017 static void
6018 fur_orig_expr_found (insn_t insn, expr_t expr ATTRIBUTE_UNUSED,
6019 cmpd_local_params_p lparams ATTRIBUTE_UNUSED,
6020 void *static_params)
6022 fur_static_params_p params = (fur_static_params_p) static_params;
6023 regset tmp;
6025 if (CALL_P (insn))
6026 params->crosses_call = true;
6028 def_list_add (params->original_insns, insn, params->crosses_call);
6030 /* Mark the registers that do not meet the following condition:
6031 (2) not among the live registers of the point
6032 immediately following the first original operation on
6033 a given downward path, except for the original target
6034 register of the operation. */
6035 tmp = get_clear_regset_from_pool ();
6036 compute_live_below_insn (insn, tmp);
6037 AND_COMPL_REG_SET (tmp, INSN_REG_SETS (insn));
6038 AND_COMPL_REG_SET (tmp, INSN_REG_CLOBBERS (insn));
6039 IOR_REG_SET (params->used_regs, tmp);
6040 return_regset_to_pool (tmp);
6042 /* (*1) We need to add to USED_REGS registers that are read by
6043 INSN's lhs. This may lead to choosing wrong src register.
6044 E.g. (scheduling const expr enabled):
6046 429: ax=0x0 <- Can't use AX for this expr (0x0)
6047 433: dx=[bp-0x18]
6048 427: [ax+dx+0x1]=ax
6049 REG_DEAD: ax
6050 168: di=dx
6051 REG_DEAD: dx
6053 /* FIXME: see comment above and enable MEM_P
6054 in vinsn_separable_p. */
6055 gcc_assert (!VINSN_SEPARABLE_P (INSN_VINSN (insn))
6056 || !MEM_P (INSN_LHS (insn)));
6059 /* This function is called on the ascending pass, before returning from
6060 current basic block. */
6061 static void
6062 move_op_at_first_insn (insn_t insn, cmpd_local_params_p lparams,
6063 void *static_params)
6065 moveop_static_params_p sparams = (moveop_static_params_p) static_params;
6066 basic_block book_block = NULL;
6068 /* When we have removed the boundary insn for scheduling, which also
6069 happened to be the end insn in its bb, we don't need to update sets. */
6070 if (!lparams->removed_last_insn
6071 && lparams->e1
6072 && sel_bb_head_p (insn))
6074 /* We should generate bookkeeping code only if we are not at the
6075 top level of the move_op. */
6076 if (sel_num_cfg_preds_gt_1 (insn))
6077 book_block = generate_bookkeeping_insn (sparams->c_expr,
6078 lparams->e1, lparams->e2);
6079 /* Update data sets for the current insn. */
6080 update_data_sets (insn);
6083 /* If bookkeeping code was inserted, we need to update av sets of basic
6084 block that received bookkeeping. After generation of bookkeeping insn,
6085 bookkeeping block does not contain valid av set because we are not following
6086 the original algorithm in every detail with regards to e.g. renaming
6087 simple reg-reg copies. Consider example:
6089 bookkeeping block scheduling fence
6091 \ join /
6092 ----------
6094 ----------
6097 r1 := r2 r1 := r3
6099 We try to schedule insn "r1 := r3" on the current
6100 scheduling fence. Also, note that av set of bookkeeping block
6101 contain both insns "r1 := r2" and "r1 := r3". When the insn has
6102 been scheduled, the CFG is as follows:
6104 r1 := r3 r1 := r3
6105 bookkeeping block scheduling fence
6107 \ join /
6108 ----------
6110 ----------
6113 r1 := r2
6115 Here, insn "r1 := r3" was scheduled at the current scheduling point
6116 and bookkeeping code was generated at the bookeeping block. This
6117 way insn "r1 := r2" is no longer available as a whole instruction
6118 (but only as expr) ahead of insn "r1 := r3" in bookkeeping block.
6119 This situation is handled by calling update_data_sets.
6121 Since update_data_sets is called only on the bookkeeping block, and
6122 it also may have predecessors with av_sets, containing instructions that
6123 are no longer available, we save all such expressions that become
6124 unavailable during data sets update on the bookkeeping block in
6125 VEC_BOOKKEEPING_BLOCKED_VINSNS. Later we avoid selecting such
6126 expressions for scheduling. This allows us to avoid recomputation of
6127 av_sets outside the code motion path. */
6129 if (book_block)
6130 update_and_record_unavailable_insns (book_block);
6132 /* If INSN was previously marked for deletion, it's time to do it. */
6133 if (lparams->removed_last_insn)
6134 insn = PREV_INSN (insn);
6136 /* Do not tidy control flow at the topmost moveop, as we can erroneously
6137 kill a block with a single nop in which the insn should be emitted. */
6138 if (lparams->e1)
6139 tidy_control_flow (BLOCK_FOR_INSN (insn), true);
6142 /* This function is called on the ascending pass, before returning from the
6143 current basic block. */
6144 static void
6145 fur_at_first_insn (insn_t insn,
6146 cmpd_local_params_p lparams ATTRIBUTE_UNUSED,
6147 void *static_params ATTRIBUTE_UNUSED)
6149 gcc_assert (!sel_bb_head_p (insn) || AV_SET_VALID_P (insn)
6150 || AV_LEVEL (insn) == -1);
6153 /* Called on the backward stage of recursion to call moveup_expr for insn
6154 and sparams->c_expr. */
6155 static void
6156 move_op_ascend (insn_t insn, void *static_params)
6158 enum MOVEUP_EXPR_CODE res;
6159 moveop_static_params_p sparams = (moveop_static_params_p) static_params;
6161 if (! INSN_NOP_P (insn))
6163 res = moveup_expr_cached (sparams->c_expr, insn, false);
6164 gcc_assert (res != MOVEUP_EXPR_NULL);
6167 /* Update liveness for this insn as it was invalidated. */
6168 update_liveness_on_insn (insn);
6171 /* This function is called on enter to the basic block.
6172 Returns TRUE if this block already have been visited and
6173 code_motion_path_driver should return 1, FALSE otherwise. */
6174 static int
6175 fur_on_enter (insn_t insn ATTRIBUTE_UNUSED, cmpd_local_params_p local_params,
6176 void *static_params, bool visited_p)
6178 fur_static_params_p sparams = (fur_static_params_p) static_params;
6180 if (visited_p)
6182 /* If we have found something below this block, there should be at
6183 least one insn in ORIGINAL_INSNS. */
6184 gcc_assert (*sparams->original_insns);
6186 /* Adjust CROSSES_CALL, since we may have come to this block along
6187 different path. */
6188 DEF_LIST_DEF (*sparams->original_insns)->crosses_call
6189 |= sparams->crosses_call;
6191 else
6192 local_params->old_original_insns = *sparams->original_insns;
6194 return 1;
6197 /* Same as above but for move_op. */
6198 static int
6199 move_op_on_enter (insn_t insn ATTRIBUTE_UNUSED,
6200 cmpd_local_params_p local_params ATTRIBUTE_UNUSED,
6201 void *static_params ATTRIBUTE_UNUSED, bool visited_p)
6203 if (visited_p)
6204 return -1;
6205 return 1;
6208 /* This function is called while descending current basic block if current
6209 insn is not the original EXPR we're searching for.
6211 Return value: FALSE, if code_motion_path_driver should perform a local
6212 cleanup and return 0 itself;
6213 TRUE, if code_motion_path_driver should continue. */
6214 static bool
6215 move_op_orig_expr_not_found (insn_t insn, av_set_t orig_ops ATTRIBUTE_UNUSED,
6216 void *static_params)
6218 moveop_static_params_p sparams = (moveop_static_params_p) static_params;
6220 sparams->failed_insn = insn;
6222 /* If we're scheduling separate expr, in order to generate correct code
6223 we need to stop the search at bookkeeping code generated with the
6224 same destination register or memory. */
6225 if (lhs_of_insn_equals_to_dest_p (insn, sparams->dest))
6226 return false;
6227 return true;
6230 /* This function is called while descending current basic block if current
6231 insn is not the original EXPR we're searching for.
6233 Return value: TRUE (code_motion_path_driver should continue). */
6234 static bool
6235 fur_orig_expr_not_found (insn_t insn, av_set_t orig_ops, void *static_params)
6237 bool mutexed;
6238 expr_t r;
6239 av_set_iterator avi;
6240 fur_static_params_p sparams = (fur_static_params_p) static_params;
6242 if (CALL_P (insn))
6243 sparams->crosses_call = true;
6244 else if (DEBUG_INSN_P (insn))
6245 return true;
6247 /* If current insn we are looking at cannot be executed together
6248 with original insn, then we can skip it safely.
6250 Example: ORIG_OPS = { (p6) r14 = sign_extend (r15); }
6251 INSN = (!p6) r14 = r14 + 1;
6253 Here we can schedule ORIG_OP with lhs = r14, though only
6254 looking at the set of used and set registers of INSN we must
6255 forbid it. So, add set/used in INSN registers to the
6256 untouchable set only if there is an insn in ORIG_OPS that can
6257 affect INSN. */
6258 mutexed = true;
6259 FOR_EACH_EXPR (r, avi, orig_ops)
6260 if (!sched_insns_conditions_mutex_p (insn, EXPR_INSN_RTX (r)))
6262 mutexed = false;
6263 break;
6266 /* Mark all registers that do not meet the following condition:
6267 (1) Not set or read on any path from xi to an instance of the
6268 original operation. */
6269 if (!mutexed)
6271 IOR_REG_SET (sparams->used_regs, INSN_REG_SETS (insn));
6272 IOR_REG_SET (sparams->used_regs, INSN_REG_USES (insn));
6273 IOR_REG_SET (sparams->used_regs, INSN_REG_CLOBBERS (insn));
6276 return true;
6279 /* Hooks and data to perform move_op operations with code_motion_path_driver. */
6280 struct code_motion_path_driver_info_def move_op_hooks = {
6281 move_op_on_enter,
6282 move_op_orig_expr_found,
6283 move_op_orig_expr_not_found,
6284 move_op_merge_succs,
6285 move_op_after_merge_succs,
6286 move_op_ascend,
6287 move_op_at_first_insn,
6288 SUCCS_NORMAL,
6289 "move_op"
6292 /* Hooks and data to perform find_used_regs operations
6293 with code_motion_path_driver. */
6294 struct code_motion_path_driver_info_def fur_hooks = {
6295 fur_on_enter,
6296 fur_orig_expr_found,
6297 fur_orig_expr_not_found,
6298 fur_merge_succs,
6299 NULL, /* fur_after_merge_succs */
6300 NULL, /* fur_ascend */
6301 fur_at_first_insn,
6302 SUCCS_ALL,
6303 "find_used_regs"
6306 /* Traverse all successors of INSN. For each successor that is SUCCS_NORMAL
6307 code_motion_path_driver is called recursively. Original operation
6308 was found at least on one path that is starting with one of INSN's
6309 successors (this fact is asserted). ORIG_OPS is expressions we're looking
6310 for, PATH is the path we've traversed, STATIC_PARAMS is the parameters
6311 of either move_op or find_used_regs depending on the caller.
6313 Return 0 if we haven't found expression, 1 if we found it, -1 if we don't
6314 know for sure at this point. */
6315 static int
6316 code_motion_process_successors (insn_t insn, av_set_t orig_ops,
6317 ilist_t path, void *static_params)
6319 int res = 0;
6320 succ_iterator succ_i;
6321 insn_t succ;
6322 basic_block bb;
6323 int old_index;
6324 unsigned old_succs;
6326 struct cmpd_local_params lparams;
6327 expr_def _x;
6329 lparams.c_expr_local = &_x;
6330 lparams.c_expr_merged = NULL;
6332 /* We need to process only NORMAL succs for move_op, and collect live
6333 registers from ALL branches (including those leading out of the
6334 region) for find_used_regs.
6336 In move_op, there can be a case when insn's bb number has changed
6337 due to created bookkeeping. This happens very rare, as we need to
6338 move expression from the beginning to the end of the same block.
6339 Rescan successors in this case. */
6341 rescan:
6342 bb = BLOCK_FOR_INSN (insn);
6343 old_index = bb->index;
6344 old_succs = EDGE_COUNT (bb->succs);
6346 FOR_EACH_SUCC_1 (succ, succ_i, insn, code_motion_path_driver_info->succ_flags)
6348 int b;
6350 lparams.e1 = succ_i.e1;
6351 lparams.e2 = succ_i.e2;
6353 /* Go deep into recursion only for NORMAL edges (non-backedges within the
6354 current region). */
6355 if (succ_i.current_flags == SUCCS_NORMAL)
6356 b = code_motion_path_driver (succ, orig_ops, path, &lparams,
6357 static_params);
6358 else
6359 b = 0;
6361 /* Merge c_expres found or unify live register sets from different
6362 successors. */
6363 code_motion_path_driver_info->merge_succs (insn, succ, b, &lparams,
6364 static_params);
6365 if (b == 1)
6366 res = b;
6367 else if (b == -1 && res != 1)
6368 res = b;
6370 /* We have simplified the control flow below this point. In this case,
6371 the iterator becomes invalid. We need to try again.
6372 If we have removed the insn itself, it could be only an
6373 unconditional jump. Thus, do not rescan but break immediately --
6374 we have already visited the only successor block. */
6375 if (!BLOCK_FOR_INSN (insn))
6377 if (sched_verbose >= 6)
6378 sel_print ("Not doing rescan: already visited the only successor"
6379 " of block %d\n", old_index);
6380 break;
6382 if (BLOCK_FOR_INSN (insn)->index != old_index
6383 || EDGE_COUNT (bb->succs) != old_succs)
6385 if (sched_verbose >= 6)
6386 sel_print ("Rescan: CFG was simplified below insn %d, block %d\n",
6387 INSN_UID (insn), BLOCK_FOR_INSN (insn)->index);
6388 insn = sel_bb_end (BLOCK_FOR_INSN (insn));
6389 goto rescan;
6393 /* Here, RES==1 if original expr was found at least for one of the
6394 successors. After the loop, RES may happen to have zero value
6395 only if at some point the expr searched is present in av_set, but is
6396 not found below. In most cases, this situation is an error.
6397 The exception is when the original operation is blocked by
6398 bookkeeping generated for another fence or for another path in current
6399 move_op. */
6400 gcc_checking_assert (res == 1
6401 || (res == 0
6402 && av_set_could_be_blocked_by_bookkeeping_p (orig_ops, static_params))
6403 || res == -1);
6405 /* Merge data, clean up, etc. */
6406 if (res != -1 && code_motion_path_driver_info->after_merge_succs)
6407 code_motion_path_driver_info->after_merge_succs (&lparams, static_params);
6409 return res;
6413 /* Perform a cleanup when the driver is about to terminate. ORIG_OPS_P
6414 is the pointer to the av set with expressions we were looking for,
6415 PATH_P is the pointer to the traversed path. */
6416 static inline void
6417 code_motion_path_driver_cleanup (av_set_t *orig_ops_p, ilist_t *path_p)
6419 ilist_remove (path_p);
6420 av_set_clear (orig_ops_p);
6423 /* The driver function that implements move_op or find_used_regs
6424 functionality dependent whether code_motion_path_driver_INFO is set to
6425 &MOVE_OP_HOOKS or &FUR_HOOKS. This function implements the common parts
6426 of code (CFG traversal etc) that are shared among both functions. INSN
6427 is the insn we're starting the search from, ORIG_OPS are the expressions
6428 we're searching for, PATH is traversed path, LOCAL_PARAMS_IN are local
6429 parameters of the driver, and STATIC_PARAMS are static parameters of
6430 the caller.
6432 Returns whether original instructions were found. Note that top-level
6433 code_motion_path_driver always returns true. */
6434 static int
6435 code_motion_path_driver (insn_t insn, av_set_t orig_ops, ilist_t path,
6436 cmpd_local_params_p local_params_in,
6437 void *static_params)
6439 expr_t expr = NULL;
6440 basic_block bb = BLOCK_FOR_INSN (insn);
6441 insn_t first_insn, bb_tail, before_first;
6442 bool removed_last_insn = false;
6444 if (sched_verbose >= 6)
6446 sel_print ("%s (", code_motion_path_driver_info->routine_name);
6447 dump_insn (insn);
6448 sel_print (",");
6449 dump_av_set (orig_ops);
6450 sel_print (")\n");
6453 gcc_assert (orig_ops);
6455 /* If no original operations exist below this insn, return immediately. */
6456 if (is_ineligible_successor (insn, path))
6458 if (sched_verbose >= 6)
6459 sel_print ("Insn %d is ineligible successor\n", INSN_UID (insn));
6460 return false;
6463 /* The block can have invalid av set, in which case it was created earlier
6464 during move_op. Return immediately. */
6465 if (sel_bb_head_p (insn))
6467 if (! AV_SET_VALID_P (insn))
6469 if (sched_verbose >= 6)
6470 sel_print ("Returned from block %d as it had invalid av set\n",
6471 bb->index);
6472 return false;
6475 if (bitmap_bit_p (code_motion_visited_blocks, bb->index))
6477 /* We have already found an original operation on this branch, do not
6478 go any further and just return TRUE here. If we don't stop here,
6479 function can have exponential behavior even on the small code
6480 with many different paths (e.g. with data speculation and
6481 recovery blocks). */
6482 if (sched_verbose >= 6)
6483 sel_print ("Block %d already visited in this traversal\n", bb->index);
6484 if (code_motion_path_driver_info->on_enter)
6485 return code_motion_path_driver_info->on_enter (insn,
6486 local_params_in,
6487 static_params,
6488 true);
6492 if (code_motion_path_driver_info->on_enter)
6493 code_motion_path_driver_info->on_enter (insn, local_params_in,
6494 static_params, false);
6495 orig_ops = av_set_copy (orig_ops);
6497 /* Filter the orig_ops set. */
6498 if (AV_SET_VALID_P (insn))
6499 av_set_code_motion_filter (&orig_ops, AV_SET (insn));
6501 /* If no more original ops, return immediately. */
6502 if (!orig_ops)
6504 if (sched_verbose >= 6)
6505 sel_print ("No intersection with av set of block %d\n", bb->index);
6506 return false;
6509 /* For non-speculative insns we have to leave only one form of the
6510 original operation, because if we don't, we may end up with
6511 different C_EXPRes and, consequently, with bookkeepings for different
6512 expression forms along the same code motion path. That may lead to
6513 generation of incorrect code. So for each code motion we stick to
6514 the single form of the instruction, except for speculative insns
6515 which we need to keep in different forms with all speculation
6516 types. */
6517 av_set_leave_one_nonspec (&orig_ops);
6519 /* It is not possible that all ORIG_OPS are filtered out. */
6520 gcc_assert (orig_ops);
6522 /* It is enough to place only heads and tails of visited basic blocks into
6523 the PATH. */
6524 ilist_add (&path, insn);
6525 first_insn = insn;
6526 bb_tail = sel_bb_end (bb);
6528 /* Descend the basic block in search of the original expr; this part
6529 corresponds to the part of the original move_op procedure executed
6530 before the recursive call. */
6531 for (;;)
6533 /* Look at the insn and decide if it could be an ancestor of currently
6534 scheduling operation. If it is so, then the insn "dest = op" could
6535 either be replaced with "dest = reg", because REG now holds the result
6536 of OP, or just removed, if we've scheduled the insn as a whole.
6538 If this insn doesn't contain currently scheduling OP, then proceed
6539 with searching and look at its successors. Operations we're searching
6540 for could have changed when moving up through this insn via
6541 substituting. In this case, perform unsubstitution on them first.
6543 When traversing the DAG below this insn is finished, insert
6544 bookkeeping code, if the insn is a joint point, and remove
6545 leftovers. */
6547 expr = av_set_lookup (orig_ops, INSN_VINSN (insn));
6548 if (expr)
6550 insn_t last_insn = PREV_INSN (insn);
6552 /* We have found the original operation. */
6553 if (sched_verbose >= 6)
6554 sel_print ("Found original operation at insn %d\n", INSN_UID (insn));
6556 code_motion_path_driver_info->orig_expr_found
6557 (insn, expr, local_params_in, static_params);
6559 /* Step back, so on the way back we'll start traversing from the
6560 previous insn (or we'll see that it's bb_note and skip that
6561 loop). */
6562 if (insn == first_insn)
6564 first_insn = NEXT_INSN (last_insn);
6565 removed_last_insn = sel_bb_end_p (last_insn);
6567 insn = last_insn;
6568 break;
6570 else
6572 /* We haven't found the original expr, continue descending the basic
6573 block. */
6574 if (code_motion_path_driver_info->orig_expr_not_found
6575 (insn, orig_ops, static_params))
6577 /* Av set ops could have been changed when moving through this
6578 insn. To find them below it, we have to un-substitute them. */
6579 undo_transformations (&orig_ops, insn);
6581 else
6583 /* Clean up and return, if the hook tells us to do so. It may
6584 happen if we've encountered the previously created
6585 bookkeeping. */
6586 code_motion_path_driver_cleanup (&orig_ops, &path);
6587 return -1;
6590 gcc_assert (orig_ops);
6593 /* Stop at insn if we got to the end of BB. */
6594 if (insn == bb_tail)
6595 break;
6597 insn = NEXT_INSN (insn);
6600 /* Here INSN either points to the insn before the original insn (may be
6601 bb_note, if original insn was a bb_head) or to the bb_end. */
6602 if (!expr)
6604 int res;
6605 rtx_insn *last_insn = PREV_INSN (insn);
6606 bool added_to_path;
6608 gcc_assert (insn == sel_bb_end (bb));
6610 /* Add bb tail to PATH (but it doesn't make any sense if it's a bb_head -
6611 it's already in PATH then). */
6612 if (insn != first_insn)
6614 ilist_add (&path, insn);
6615 added_to_path = true;
6617 else
6618 added_to_path = false;
6620 /* Process_successors should be able to find at least one
6621 successor for which code_motion_path_driver returns TRUE. */
6622 res = code_motion_process_successors (insn, orig_ops,
6623 path, static_params);
6625 /* Jump in the end of basic block could have been removed or replaced
6626 during code_motion_process_successors, so recompute insn as the
6627 last insn in bb. */
6628 if (NEXT_INSN (last_insn) != insn)
6630 insn = sel_bb_end (bb);
6631 first_insn = sel_bb_head (bb);
6634 /* Remove bb tail from path. */
6635 if (added_to_path)
6636 ilist_remove (&path);
6638 if (res != 1)
6640 /* This is the case when one of the original expr is no longer available
6641 due to bookkeeping created on this branch with the same register.
6642 In the original algorithm, which doesn't have update_data_sets call
6643 on a bookkeeping block, it would simply result in returning
6644 FALSE when we've encountered a previously generated bookkeeping
6645 insn in moveop_orig_expr_not_found. */
6646 code_motion_path_driver_cleanup (&orig_ops, &path);
6647 return res;
6651 /* Don't need it any more. */
6652 av_set_clear (&orig_ops);
6654 /* Backward pass: now, when we have C_EXPR computed, we'll drag it to
6655 the beginning of the basic block. */
6656 before_first = PREV_INSN (first_insn);
6657 while (insn != before_first)
6659 if (code_motion_path_driver_info->ascend)
6660 code_motion_path_driver_info->ascend (insn, static_params);
6662 insn = PREV_INSN (insn);
6665 /* Now we're at the bb head. */
6666 insn = first_insn;
6667 ilist_remove (&path);
6668 local_params_in->removed_last_insn = removed_last_insn;
6669 code_motion_path_driver_info->at_first_insn (insn, local_params_in, static_params);
6671 /* This should be the very last operation as at bb head we could change
6672 the numbering by creating bookkeeping blocks. */
6673 if (removed_last_insn)
6674 insn = PREV_INSN (insn);
6676 /* If we have simplified the control flow and removed the first jump insn,
6677 there's no point in marking this block in the visited blocks bitmap. */
6678 if (BLOCK_FOR_INSN (insn))
6679 bitmap_set_bit (code_motion_visited_blocks, BLOCK_FOR_INSN (insn)->index);
6680 return true;
6683 /* Move up the operations from ORIG_OPS set traversing the dag starting
6684 from INSN. PATH represents the edges traversed so far.
6685 DEST is the register chosen for scheduling the current expr. Insert
6686 bookkeeping code in the join points. EXPR_VLIW is the chosen expression,
6687 C_EXPR is how it looks like at the given cfg point.
6688 Set *SHOULD_MOVE to indicate whether we have only disconnected
6689 one of the insns found.
6691 Returns whether original instructions were found, which is asserted
6692 to be true in the caller. */
6693 static bool
6694 move_op (insn_t insn, av_set_t orig_ops, expr_t expr_vliw,
6695 rtx dest, expr_t c_expr, bool *should_move)
6697 struct moveop_static_params sparams;
6698 struct cmpd_local_params lparams;
6699 int res;
6701 /* Init params for code_motion_path_driver. */
6702 sparams.dest = dest;
6703 sparams.c_expr = c_expr;
6704 sparams.uid = INSN_UID (EXPR_INSN_RTX (expr_vliw));
6705 sparams.failed_insn = NULL;
6706 sparams.was_renamed = false;
6707 lparams.e1 = NULL;
6709 /* We haven't visited any blocks yet. */
6710 bitmap_clear (code_motion_visited_blocks);
6712 /* Set appropriate hooks and data. */
6713 code_motion_path_driver_info = &move_op_hooks;
6714 res = code_motion_path_driver (insn, orig_ops, NULL, &lparams, &sparams);
6716 gcc_assert (res != -1);
6718 if (sparams.was_renamed)
6719 EXPR_WAS_RENAMED (expr_vliw) = true;
6721 *should_move = (sparams.uid == -1);
6723 return res;
6727 /* Functions that work with regions. */
6729 /* Current number of seqno used in init_seqno and init_seqno_1. */
6730 static int cur_seqno;
6732 /* A helper for init_seqno. Traverse the region starting from BB and
6733 compute seqnos for visited insns, marking visited bbs in VISITED_BBS.
6734 Clear visited blocks from BLOCKS_TO_RESCHEDULE. */
6735 static void
6736 init_seqno_1 (basic_block bb, sbitmap visited_bbs, bitmap blocks_to_reschedule)
6738 int bbi = BLOCK_TO_BB (bb->index);
6739 insn_t insn;
6740 insn_t succ_insn;
6741 succ_iterator si;
6743 rtx_note *note = bb_note (bb);
6744 bitmap_set_bit (visited_bbs, bbi);
6745 if (blocks_to_reschedule)
6746 bitmap_clear_bit (blocks_to_reschedule, bb->index);
6748 FOR_EACH_SUCC_1 (succ_insn, si, BB_END (bb),
6749 SUCCS_NORMAL | SUCCS_SKIP_TO_LOOP_EXITS)
6751 basic_block succ = BLOCK_FOR_INSN (succ_insn);
6752 int succ_bbi = BLOCK_TO_BB (succ->index);
6754 gcc_assert (in_current_region_p (succ));
6756 if (!bitmap_bit_p (visited_bbs, succ_bbi))
6758 gcc_assert (succ_bbi > bbi);
6760 init_seqno_1 (succ, visited_bbs, blocks_to_reschedule);
6762 else if (blocks_to_reschedule)
6763 bitmap_set_bit (forced_ebb_heads, succ->index);
6766 for (insn = BB_END (bb); insn != note; insn = PREV_INSN (insn))
6767 INSN_SEQNO (insn) = cur_seqno--;
6770 /* Initialize seqnos for the current region. BLOCKS_TO_RESCHEDULE contains
6771 blocks on which we're rescheduling when pipelining, FROM is the block where
6772 traversing region begins (it may not be the head of the region when
6773 pipelining, but the head of the loop instead).
6775 Returns the maximal seqno found. */
6776 static int
6777 init_seqno (bitmap blocks_to_reschedule, basic_block from)
6779 bitmap_iterator bi;
6780 unsigned bbi;
6782 auto_sbitmap visited_bbs (current_nr_blocks);
6784 if (blocks_to_reschedule)
6786 bitmap_ones (visited_bbs);
6787 EXECUTE_IF_SET_IN_BITMAP (blocks_to_reschedule, 0, bbi, bi)
6789 gcc_assert (BLOCK_TO_BB (bbi) < current_nr_blocks);
6790 bitmap_clear_bit (visited_bbs, BLOCK_TO_BB (bbi));
6793 else
6795 bitmap_clear (visited_bbs);
6796 from = EBB_FIRST_BB (0);
6799 cur_seqno = sched_max_luid - 1;
6800 init_seqno_1 (from, visited_bbs, blocks_to_reschedule);
6802 /* cur_seqno may be positive if the number of instructions is less than
6803 sched_max_luid - 1 (when rescheduling or if some instructions have been
6804 removed by the call to purge_empty_blocks in sel_sched_region_1). */
6805 gcc_assert (cur_seqno >= 0);
6807 return sched_max_luid - 1;
6810 /* Initialize scheduling parameters for current region. */
6811 static void
6812 sel_setup_region_sched_flags (void)
6814 enable_schedule_as_rhs_p = 1;
6815 bookkeeping_p = 1;
6816 pipelining_p = (bookkeeping_p
6817 && (flag_sel_sched_pipelining != 0)
6818 && current_loop_nest != NULL
6819 && loop_has_exit_edges (current_loop_nest));
6820 max_insns_to_rename = PARAM_VALUE (PARAM_SELSCHED_INSNS_TO_RENAME);
6821 max_ws = MAX_WS;
6824 /* Return true if all basic blocks of current region are empty. */
6825 static bool
6826 current_region_empty_p (void)
6828 int i;
6829 for (i = 0; i < current_nr_blocks; i++)
6830 if (! sel_bb_empty_p (BASIC_BLOCK_FOR_FN (cfun, BB_TO_BLOCK (i))))
6831 return false;
6833 return true;
6836 /* Prepare and verify loop nest for pipelining. */
6837 static void
6838 setup_current_loop_nest (int rgn, bb_vec_t *bbs)
6840 current_loop_nest = get_loop_nest_for_rgn (rgn);
6842 if (!current_loop_nest)
6843 return;
6845 /* If this loop has any saved loop preheaders from nested loops,
6846 add these basic blocks to the current region. */
6847 sel_add_loop_preheaders (bbs);
6849 /* Check that we're starting with a valid information. */
6850 gcc_assert (loop_latch_edge (current_loop_nest));
6851 gcc_assert (LOOP_MARKED_FOR_PIPELINING_P (current_loop_nest));
6854 /* Compute instruction priorities for current region. */
6855 static void
6856 sel_compute_priorities (int rgn)
6858 sched_rgn_compute_dependencies (rgn);
6860 /* Compute insn priorities in haifa style. Then free haifa style
6861 dependencies that we've calculated for this. */
6862 compute_priorities ();
6864 if (sched_verbose >= 5)
6865 debug_rgn_dependencies (0);
6867 free_rgn_deps ();
6870 /* Init scheduling data for RGN. Returns true when this region should not
6871 be scheduled. */
6872 static bool
6873 sel_region_init (int rgn)
6875 int i;
6876 bb_vec_t bbs;
6878 rgn_setup_region (rgn);
6880 /* Even if sched_is_disabled_for_current_region_p() is true, we still
6881 do region initialization here so the region can be bundled correctly,
6882 but we'll skip the scheduling in sel_sched_region (). */
6883 if (current_region_empty_p ())
6884 return true;
6886 bbs.create (current_nr_blocks);
6888 for (i = 0; i < current_nr_blocks; i++)
6889 bbs.quick_push (BASIC_BLOCK_FOR_FN (cfun, BB_TO_BLOCK (i)));
6891 sel_init_bbs (bbs);
6893 if (flag_sel_sched_pipelining)
6894 setup_current_loop_nest (rgn, &bbs);
6896 sel_setup_region_sched_flags ();
6898 /* Initialize luids and dependence analysis which both sel-sched and haifa
6899 need. */
6900 sched_init_luids (bbs);
6901 sched_deps_init (false);
6903 /* Initialize haifa data. */
6904 rgn_setup_sched_infos ();
6905 sel_set_sched_flags ();
6906 haifa_init_h_i_d (bbs);
6908 sel_compute_priorities (rgn);
6909 init_deps_global ();
6911 /* Main initialization. */
6912 sel_setup_sched_infos ();
6913 sel_init_global_and_expr (bbs);
6915 bbs.release ();
6917 blocks_to_reschedule = BITMAP_ALLOC (NULL);
6919 /* Init correct liveness sets on each instruction of a single-block loop.
6920 This is the only situation when we can't update liveness when calling
6921 compute_live for the first insn of the loop. */
6922 if (current_loop_nest)
6924 int header =
6925 (sel_is_loop_preheader_p (BASIC_BLOCK_FOR_FN (cfun, BB_TO_BLOCK (0)))
6927 : 0);
6929 if (current_nr_blocks == header + 1)
6930 update_liveness_on_insn
6931 (sel_bb_head (BASIC_BLOCK_FOR_FN (cfun, BB_TO_BLOCK (header))));
6934 /* Set hooks so that no newly generated insn will go out unnoticed. */
6935 sel_register_cfg_hooks ();
6937 /* !!! We call target.sched.init () for the whole region, but we invoke
6938 targetm.sched.finish () for every ebb. */
6939 if (targetm.sched.init)
6940 /* None of the arguments are actually used in any target. */
6941 targetm.sched.init (sched_dump, sched_verbose, -1);
6943 first_emitted_uid = get_max_uid () + 1;
6944 preheader_removed = false;
6946 /* Reset register allocation ticks array. */
6947 memset (reg_rename_tick, 0, sizeof reg_rename_tick);
6948 reg_rename_this_tick = 0;
6950 bitmap_initialize (forced_ebb_heads, 0);
6951 bitmap_clear (forced_ebb_heads);
6953 setup_nop_vinsn ();
6954 current_copies = BITMAP_ALLOC (NULL);
6955 current_originators = BITMAP_ALLOC (NULL);
6956 code_motion_visited_blocks = BITMAP_ALLOC (NULL);
6958 return false;
6961 /* Simplify insns after the scheduling. */
6962 static void
6963 simplify_changed_insns (void)
6965 int i;
6967 for (i = 0; i < current_nr_blocks; i++)
6969 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, BB_TO_BLOCK (i));
6970 rtx_insn *insn;
6972 FOR_BB_INSNS (bb, insn)
6973 if (INSN_P (insn))
6975 expr_t expr = INSN_EXPR (insn);
6977 if (EXPR_WAS_SUBSTITUTED (expr))
6978 validate_simplify_insn (insn);
6983 /* Find boundaries of the EBB starting from basic block BB, marking blocks of
6984 this EBB in SCHEDULED_BLOCKS and appropriately filling in HEAD, TAIL,
6985 PREV_HEAD, and NEXT_TAIL fields of CURRENT_SCHED_INFO structure. */
6986 static void
6987 find_ebb_boundaries (basic_block bb, bitmap scheduled_blocks)
6989 rtx_insn *head, *tail;
6990 basic_block bb1 = bb;
6991 if (sched_verbose >= 2)
6992 sel_print ("Finishing schedule in bbs: ");
6996 bitmap_set_bit (scheduled_blocks, BLOCK_TO_BB (bb1->index));
6998 if (sched_verbose >= 2)
6999 sel_print ("%d; ", bb1->index);
7001 while (!bb_ends_ebb_p (bb1) && (bb1 = bb_next_bb (bb1)));
7003 if (sched_verbose >= 2)
7004 sel_print ("\n");
7006 get_ebb_head_tail (bb, bb1, &head, &tail);
7008 current_sched_info->head = head;
7009 current_sched_info->tail = tail;
7010 current_sched_info->prev_head = PREV_INSN (head);
7011 current_sched_info->next_tail = NEXT_INSN (tail);
7014 /* Regenerate INSN_SCHED_CYCLEs for insns of current EBB. */
7015 static void
7016 reset_sched_cycles_in_current_ebb (void)
7018 int last_clock = 0;
7019 int haifa_last_clock = -1;
7020 int haifa_clock = 0;
7021 int issued_insns = 0;
7022 insn_t insn;
7024 if (targetm.sched.init)
7026 /* None of the arguments are actually used in any target.
7027 NB: We should have md_reset () hook for cases like this. */
7028 targetm.sched.init (sched_dump, sched_verbose, -1);
7031 state_reset (curr_state);
7032 advance_state (curr_state);
7034 for (insn = current_sched_info->head;
7035 insn != current_sched_info->next_tail;
7036 insn = NEXT_INSN (insn))
7038 int cost, haifa_cost;
7039 int sort_p;
7040 bool asm_p, real_insn, after_stall, all_issued;
7041 int clock;
7043 if (!INSN_P (insn))
7044 continue;
7046 asm_p = false;
7047 real_insn = recog_memoized (insn) >= 0;
7048 clock = INSN_SCHED_CYCLE (insn);
7050 cost = clock - last_clock;
7052 /* Initialize HAIFA_COST. */
7053 if (! real_insn)
7055 asm_p = INSN_ASM_P (insn);
7057 if (asm_p)
7058 /* This is asm insn which *had* to be scheduled first
7059 on the cycle. */
7060 haifa_cost = 1;
7061 else
7062 /* This is a use/clobber insn. It should not change
7063 cost. */
7064 haifa_cost = 0;
7066 else
7067 haifa_cost = estimate_insn_cost (insn, curr_state);
7069 /* Stall for whatever cycles we've stalled before. */
7070 after_stall = 0;
7071 if (INSN_AFTER_STALL_P (insn) && cost > haifa_cost)
7073 haifa_cost = cost;
7074 after_stall = 1;
7076 all_issued = issued_insns == issue_rate;
7077 if (haifa_cost == 0 && all_issued)
7078 haifa_cost = 1;
7079 if (haifa_cost > 0)
7081 int i = 0;
7083 while (haifa_cost--)
7085 advance_state (curr_state);
7086 issued_insns = 0;
7087 i++;
7089 if (sched_verbose >= 2)
7091 sel_print ("advance_state (state_transition)\n");
7092 debug_state (curr_state);
7095 /* The DFA may report that e.g. insn requires 2 cycles to be
7096 issued, but on the next cycle it says that insn is ready
7097 to go. Check this here. */
7098 if (!after_stall
7099 && real_insn
7100 && haifa_cost > 0
7101 && estimate_insn_cost (insn, curr_state) == 0)
7102 break;
7104 /* When the data dependency stall is longer than the DFA stall,
7105 and when we have issued exactly issue_rate insns and stalled,
7106 it could be that after this longer stall the insn will again
7107 become unavailable to the DFA restrictions. Looks strange
7108 but happens e.g. on x86-64. So recheck DFA on the last
7109 iteration. */
7110 if ((after_stall || all_issued)
7111 && real_insn
7112 && haifa_cost == 0)
7113 haifa_cost = estimate_insn_cost (insn, curr_state);
7116 haifa_clock += i;
7117 if (sched_verbose >= 2)
7118 sel_print ("haifa clock: %d\n", haifa_clock);
7120 else
7121 gcc_assert (haifa_cost == 0);
7123 if (sched_verbose >= 2)
7124 sel_print ("Haifa cost for insn %d: %d\n", INSN_UID (insn), haifa_cost);
7126 if (targetm.sched.dfa_new_cycle)
7127 while (targetm.sched.dfa_new_cycle (sched_dump, sched_verbose, insn,
7128 haifa_last_clock, haifa_clock,
7129 &sort_p))
7131 advance_state (curr_state);
7132 issued_insns = 0;
7133 haifa_clock++;
7134 if (sched_verbose >= 2)
7136 sel_print ("advance_state (dfa_new_cycle)\n");
7137 debug_state (curr_state);
7138 sel_print ("haifa clock: %d\n", haifa_clock + 1);
7142 if (real_insn)
7144 static state_t temp = NULL;
7146 if (!temp)
7147 temp = xmalloc (dfa_state_size);
7148 memcpy (temp, curr_state, dfa_state_size);
7150 cost = state_transition (curr_state, insn);
7151 if (memcmp (temp, curr_state, dfa_state_size))
7152 issued_insns++;
7154 if (sched_verbose >= 2)
7156 sel_print ("scheduled insn %d, clock %d\n", INSN_UID (insn),
7157 haifa_clock + 1);
7158 debug_state (curr_state);
7160 gcc_assert (cost < 0);
7163 if (targetm.sched.variable_issue)
7164 targetm.sched.variable_issue (sched_dump, sched_verbose, insn, 0);
7166 INSN_SCHED_CYCLE (insn) = haifa_clock;
7168 last_clock = clock;
7169 haifa_last_clock = haifa_clock;
7173 /* Put TImode markers on insns starting a new issue group. */
7174 static void
7175 put_TImodes (void)
7177 int last_clock = -1;
7178 insn_t insn;
7180 for (insn = current_sched_info->head; insn != current_sched_info->next_tail;
7181 insn = NEXT_INSN (insn))
7183 int cost, clock;
7185 if (!INSN_P (insn))
7186 continue;
7188 clock = INSN_SCHED_CYCLE (insn);
7189 cost = (last_clock == -1) ? 1 : clock - last_clock;
7191 gcc_assert (cost >= 0);
7193 if (issue_rate > 1
7194 && GET_CODE (PATTERN (insn)) != USE
7195 && GET_CODE (PATTERN (insn)) != CLOBBER)
7197 if (reload_completed && cost > 0)
7198 PUT_MODE (insn, TImode);
7200 last_clock = clock;
7203 if (sched_verbose >= 2)
7204 sel_print ("Cost for insn %d is %d\n", INSN_UID (insn), cost);
7208 /* Perform MD_FINISH on EBBs comprising current region. When
7209 RESET_SCHED_CYCLES_P is true, run a pass emulating the scheduler
7210 to produce correct sched cycles on insns. */
7211 static void
7212 sel_region_target_finish (bool reset_sched_cycles_p)
7214 int i;
7215 bitmap scheduled_blocks = BITMAP_ALLOC (NULL);
7217 for (i = 0; i < current_nr_blocks; i++)
7219 if (bitmap_bit_p (scheduled_blocks, i))
7220 continue;
7222 /* While pipelining outer loops, skip bundling for loop
7223 preheaders. Those will be rescheduled in the outer loop. */
7224 if (sel_is_loop_preheader_p (EBB_FIRST_BB (i)))
7225 continue;
7227 find_ebb_boundaries (EBB_FIRST_BB (i), scheduled_blocks);
7229 if (no_real_insns_p (current_sched_info->head, current_sched_info->tail))
7230 continue;
7232 if (reset_sched_cycles_p)
7233 reset_sched_cycles_in_current_ebb ();
7235 if (targetm.sched.init)
7236 targetm.sched.init (sched_dump, sched_verbose, -1);
7238 put_TImodes ();
7240 if (targetm.sched.finish)
7242 targetm.sched.finish (sched_dump, sched_verbose);
7244 /* Extend luids so that insns generated by the target will
7245 get zero luid. */
7246 sched_extend_luids ();
7250 BITMAP_FREE (scheduled_blocks);
7253 /* Free the scheduling data for the current region. When RESET_SCHED_CYCLES_P
7254 is true, make an additional pass emulating scheduler to get correct insn
7255 cycles for md_finish calls. */
7256 static void
7257 sel_region_finish (bool reset_sched_cycles_p)
7259 simplify_changed_insns ();
7260 sched_finish_ready_list ();
7261 free_nop_pool ();
7263 /* Free the vectors. */
7264 vec_av_set.release ();
7265 BITMAP_FREE (current_copies);
7266 BITMAP_FREE (current_originators);
7267 BITMAP_FREE (code_motion_visited_blocks);
7268 vinsn_vec_free (vec_bookkeeping_blocked_vinsns);
7269 vinsn_vec_free (vec_target_unavailable_vinsns);
7271 /* If LV_SET of the region head should be updated, do it now because
7272 there will be no other chance. */
7274 succ_iterator si;
7275 insn_t insn;
7277 FOR_EACH_SUCC_1 (insn, si, bb_note (EBB_FIRST_BB (0)),
7278 SUCCS_NORMAL | SUCCS_SKIP_TO_LOOP_EXITS)
7280 basic_block bb = BLOCK_FOR_INSN (insn);
7282 if (!BB_LV_SET_VALID_P (bb))
7283 compute_live (insn);
7287 /* Emulate the Haifa scheduler for bundling. */
7288 if (reload_completed)
7289 sel_region_target_finish (reset_sched_cycles_p);
7291 sel_finish_global_and_expr ();
7293 bitmap_clear (forced_ebb_heads);
7295 free_nop_vinsn ();
7297 finish_deps_global ();
7298 sched_finish_luids ();
7299 h_d_i_d.release ();
7301 sel_finish_bbs ();
7302 BITMAP_FREE (blocks_to_reschedule);
7304 sel_unregister_cfg_hooks ();
7306 max_issue_size = 0;
7310 /* Functions that implement the scheduler driver. */
7312 /* Schedule a parallel instruction group on each of FENCES. MAX_SEQNO
7313 is the current maximum seqno. SCHEDULED_INSNS_TAILPP is the list
7314 of insns scheduled -- these would be postprocessed later. */
7315 static void
7316 schedule_on_fences (flist_t fences, int max_seqno,
7317 ilist_t **scheduled_insns_tailpp)
7319 flist_t old_fences = fences;
7321 if (sched_verbose >= 1)
7323 sel_print ("\nScheduling on fences: ");
7324 dump_flist (fences);
7325 sel_print ("\n");
7328 scheduled_something_on_previous_fence = false;
7329 for (; fences; fences = FLIST_NEXT (fences))
7331 fence_t fence = NULL;
7332 int seqno = 0;
7333 flist_t fences2;
7334 bool first_p = true;
7336 /* Choose the next fence group to schedule.
7337 The fact that insn can be scheduled only once
7338 on the cycle is guaranteed by two properties:
7339 1. seqnos of parallel groups decrease with each iteration.
7340 2. If is_ineligible_successor () sees the larger seqno, it
7341 checks if candidate insn is_in_current_fence_p (). */
7342 for (fences2 = old_fences; fences2; fences2 = FLIST_NEXT (fences2))
7344 fence_t f = FLIST_FENCE (fences2);
7346 if (!FENCE_PROCESSED_P (f))
7348 int i = INSN_SEQNO (FENCE_INSN (f));
7350 if (first_p || i > seqno)
7352 seqno = i;
7353 fence = f;
7354 first_p = false;
7356 else
7357 /* ??? Seqnos of different groups should be different. */
7358 gcc_assert (1 || i != seqno);
7362 gcc_assert (fence);
7364 /* As FENCE is nonnull, SEQNO is initialized. */
7365 seqno -= max_seqno + 1;
7366 fill_insns (fence, seqno, scheduled_insns_tailpp);
7367 FENCE_PROCESSED_P (fence) = true;
7370 /* All av_sets are invalidated by GLOBAL_LEVEL increase, thus we
7371 don't need to keep bookkeeping-invalidated and target-unavailable
7372 vinsns any more. */
7373 vinsn_vec_clear (&vec_bookkeeping_blocked_vinsns);
7374 vinsn_vec_clear (&vec_target_unavailable_vinsns);
7377 /* Calculate MIN_SEQNO and MAX_SEQNO. */
7378 static void
7379 find_min_max_seqno (flist_t fences, int *min_seqno, int *max_seqno)
7381 *min_seqno = *max_seqno = INSN_SEQNO (FENCE_INSN (FLIST_FENCE (fences)));
7383 /* The first element is already processed. */
7384 while ((fences = FLIST_NEXT (fences)))
7386 int seqno = INSN_SEQNO (FENCE_INSN (FLIST_FENCE (fences)));
7388 if (*min_seqno > seqno)
7389 *min_seqno = seqno;
7390 else if (*max_seqno < seqno)
7391 *max_seqno = seqno;
7395 /* Calculate new fences from FENCES. Write the current time to PTIME. */
7396 static flist_t
7397 calculate_new_fences (flist_t fences, int orig_max_seqno, int *ptime)
7399 flist_t old_fences = fences;
7400 struct flist_tail_def _new_fences, *new_fences = &_new_fences;
7401 int max_time = 0;
7403 flist_tail_init (new_fences);
7404 for (; fences; fences = FLIST_NEXT (fences))
7406 fence_t fence = FLIST_FENCE (fences);
7407 insn_t insn;
7409 if (!FENCE_BNDS (fence))
7411 /* This fence doesn't have any successors. */
7412 if (!FENCE_SCHEDULED_P (fence))
7414 /* Nothing was scheduled on this fence. */
7415 int seqno;
7417 insn = FENCE_INSN (fence);
7418 seqno = INSN_SEQNO (insn);
7419 gcc_assert (seqno > 0 && seqno <= orig_max_seqno);
7421 if (sched_verbose >= 1)
7422 sel_print ("Fence %d[%d] has not changed\n",
7423 INSN_UID (insn),
7424 BLOCK_NUM (insn));
7425 move_fence_to_fences (fences, new_fences);
7428 else
7429 extract_new_fences_from (fences, new_fences, orig_max_seqno);
7430 max_time = MAX (max_time, FENCE_CYCLE (fence));
7433 flist_clear (&old_fences);
7434 *ptime = max_time;
7435 return FLIST_TAIL_HEAD (new_fences);
7438 /* Update seqnos of insns given by PSCHEDULED_INSNS. MIN_SEQNO and MAX_SEQNO
7439 are the miminum and maximum seqnos of the group, HIGHEST_SEQNO_IN_USE is
7440 the highest seqno used in a region. Return the updated highest seqno. */
7441 static int
7442 update_seqnos_and_stage (int min_seqno, int max_seqno,
7443 int highest_seqno_in_use,
7444 ilist_t *pscheduled_insns)
7446 int new_hs;
7447 ilist_iterator ii;
7448 insn_t insn;
7450 /* Actually, new_hs is the seqno of the instruction, that was
7451 scheduled first (i.e. it is the first one in SCHEDULED_INSNS). */
7452 if (*pscheduled_insns)
7454 new_hs = (INSN_SEQNO (ILIST_INSN (*pscheduled_insns))
7455 + highest_seqno_in_use + max_seqno - min_seqno + 2);
7456 gcc_assert (new_hs > highest_seqno_in_use);
7458 else
7459 new_hs = highest_seqno_in_use;
7461 FOR_EACH_INSN (insn, ii, *pscheduled_insns)
7463 gcc_assert (INSN_SEQNO (insn) < 0);
7464 INSN_SEQNO (insn) += highest_seqno_in_use + max_seqno - min_seqno + 2;
7465 gcc_assert (INSN_SEQNO (insn) <= new_hs);
7467 /* When not pipelining, purge unneeded insn info on the scheduled insns.
7468 For example, having reg_last array of INSN_DEPS_CONTEXT in memory may
7469 require > 1GB of memory e.g. on limit-fnargs.c. */
7470 if (! pipelining_p)
7471 free_data_for_scheduled_insn (insn);
7474 ilist_clear (pscheduled_insns);
7475 global_level++;
7477 return new_hs;
7480 /* The main driver for scheduling a region. This function is responsible
7481 for correct propagation of fences (i.e. scheduling points) and creating
7482 a group of parallel insns at each of them. It also supports
7483 pipelining. ORIG_MAX_SEQNO is the maximal seqno before this pass
7484 of scheduling. */
7485 static void
7486 sel_sched_region_2 (int orig_max_seqno)
7488 int highest_seqno_in_use = orig_max_seqno;
7489 int max_time = 0;
7491 stat_bookkeeping_copies = 0;
7492 stat_insns_needed_bookkeeping = 0;
7493 stat_renamed_scheduled = 0;
7494 stat_substitutions_total = 0;
7495 num_insns_scheduled = 0;
7497 while (fences)
7499 int min_seqno, max_seqno;
7500 ilist_t scheduled_insns = NULL;
7501 ilist_t *scheduled_insns_tailp = &scheduled_insns;
7503 find_min_max_seqno (fences, &min_seqno, &max_seqno);
7504 schedule_on_fences (fences, max_seqno, &scheduled_insns_tailp);
7505 fences = calculate_new_fences (fences, orig_max_seqno, &max_time);
7506 highest_seqno_in_use = update_seqnos_and_stage (min_seqno, max_seqno,
7507 highest_seqno_in_use,
7508 &scheduled_insns);
7511 if (sched_verbose >= 1)
7513 sel_print ("Total scheduling time: %d cycles\n", max_time);
7514 sel_print ("Scheduled %d bookkeeping copies, %d insns needed "
7515 "bookkeeping, %d insns renamed, %d insns substituted\n",
7516 stat_bookkeeping_copies,
7517 stat_insns_needed_bookkeeping,
7518 stat_renamed_scheduled,
7519 stat_substitutions_total);
7523 /* Schedule a region. When pipelining, search for possibly never scheduled
7524 bookkeeping code and schedule it. Reschedule pipelined code without
7525 pipelining after. */
7526 static void
7527 sel_sched_region_1 (void)
7529 int orig_max_seqno;
7531 /* Remove empty blocks that might be in the region from the beginning. */
7532 purge_empty_blocks ();
7534 orig_max_seqno = init_seqno (NULL, NULL);
7535 gcc_assert (orig_max_seqno >= 1);
7537 /* When pipelining outer loops, create fences on the loop header,
7538 not preheader. */
7539 fences = NULL;
7540 if (current_loop_nest)
7541 init_fences (BB_END (EBB_FIRST_BB (0)));
7542 else
7543 init_fences (bb_note (EBB_FIRST_BB (0)));
7544 global_level = 1;
7546 sel_sched_region_2 (orig_max_seqno);
7548 gcc_assert (fences == NULL);
7550 if (pipelining_p)
7552 int i;
7553 basic_block bb;
7554 struct flist_tail_def _new_fences;
7555 flist_tail_t new_fences = &_new_fences;
7556 bool do_p = true;
7558 pipelining_p = false;
7559 max_ws = MIN (max_ws, issue_rate * 3 / 2);
7560 bookkeeping_p = false;
7561 enable_schedule_as_rhs_p = false;
7563 /* Schedule newly created code, that has not been scheduled yet. */
7564 do_p = true;
7566 while (do_p)
7568 do_p = false;
7570 for (i = 0; i < current_nr_blocks; i++)
7572 basic_block bb = EBB_FIRST_BB (i);
7574 if (bitmap_bit_p (blocks_to_reschedule, bb->index))
7576 if (! bb_ends_ebb_p (bb))
7577 bitmap_set_bit (blocks_to_reschedule, bb_next_bb (bb)->index);
7578 if (sel_bb_empty_p (bb))
7580 bitmap_clear_bit (blocks_to_reschedule, bb->index);
7581 continue;
7583 clear_outdated_rtx_info (bb);
7584 if (sel_insn_is_speculation_check (BB_END (bb))
7585 && JUMP_P (BB_END (bb)))
7586 bitmap_set_bit (blocks_to_reschedule,
7587 BRANCH_EDGE (bb)->dest->index);
7589 else if (! sel_bb_empty_p (bb)
7590 && INSN_SCHED_TIMES (sel_bb_head (bb)) <= 0)
7591 bitmap_set_bit (blocks_to_reschedule, bb->index);
7594 for (i = 0; i < current_nr_blocks; i++)
7596 bb = EBB_FIRST_BB (i);
7598 /* While pipelining outer loops, skip bundling for loop
7599 preheaders. Those will be rescheduled in the outer
7600 loop. */
7601 if (sel_is_loop_preheader_p (bb))
7603 clear_outdated_rtx_info (bb);
7604 continue;
7607 if (bitmap_bit_p (blocks_to_reschedule, bb->index))
7609 flist_tail_init (new_fences);
7611 orig_max_seqno = init_seqno (blocks_to_reschedule, bb);
7613 /* Mark BB as head of the new ebb. */
7614 bitmap_set_bit (forced_ebb_heads, bb->index);
7616 gcc_assert (fences == NULL);
7618 init_fences (bb_note (bb));
7620 sel_sched_region_2 (orig_max_seqno);
7622 do_p = true;
7623 break;
7630 /* Schedule the RGN region. */
7631 void
7632 sel_sched_region (int rgn)
7634 bool schedule_p;
7635 bool reset_sched_cycles_p;
7637 if (sel_region_init (rgn))
7638 return;
7640 if (sched_verbose >= 1)
7641 sel_print ("Scheduling region %d\n", rgn);
7643 schedule_p = (!sched_is_disabled_for_current_region_p ()
7644 && dbg_cnt (sel_sched_region_cnt));
7645 reset_sched_cycles_p = pipelining_p;
7646 if (schedule_p)
7647 sel_sched_region_1 ();
7648 else
7650 /* Schedule always selecting the next insn to make the correct data
7651 for bundling or other later passes. */
7652 pipelining_p = false;
7653 force_next_insn = 1;
7654 sel_sched_region_1 ();
7655 force_next_insn = 0;
7657 reset_sched_cycles_p = pipelining_p;
7658 sel_region_finish (reset_sched_cycles_p);
7661 /* Perform global init for the scheduler. */
7662 static void
7663 sel_global_init (void)
7665 /* Remove empty blocks: their presence can break assumptions elsewhere,
7666 e.g. the logic to invoke update_liveness_on_insn in sel_region_init. */
7667 cleanup_cfg (0);
7669 calculate_dominance_info (CDI_DOMINATORS);
7670 alloc_sched_pools ();
7672 /* Setup the infos for sched_init. */
7673 sel_setup_sched_infos ();
7674 setup_sched_dump ();
7676 sched_rgn_init (false);
7677 sched_init ();
7679 sched_init_bbs ();
7680 /* Reset AFTER_RECOVERY if it has been set by the 1st scheduler pass. */
7681 after_recovery = 0;
7682 can_issue_more = issue_rate;
7684 sched_extend_target ();
7685 sched_deps_init (true);
7686 setup_nop_and_exit_insns ();
7687 sel_extend_global_bb_info ();
7688 init_lv_sets ();
7689 init_hard_regs_data ();
7692 /* Free the global data of the scheduler. */
7693 static void
7694 sel_global_finish (void)
7696 free_bb_note_pool ();
7697 free_lv_sets ();
7698 sel_finish_global_bb_info ();
7700 free_regset_pool ();
7701 free_nop_and_exit_insns ();
7703 sched_rgn_finish ();
7704 sched_deps_finish ();
7705 sched_finish ();
7707 if (current_loops)
7708 sel_finish_pipelining ();
7710 free_sched_pools ();
7711 free_dominance_info (CDI_DOMINATORS);
7714 /* Return true when we need to skip selective scheduling. Used for debugging. */
7715 bool
7716 maybe_skip_selective_scheduling (void)
7718 return ! dbg_cnt (sel_sched_cnt);
7721 /* The entry point. */
7722 void
7723 run_selective_scheduling (void)
7725 int rgn;
7727 if (n_basic_blocks_for_fn (cfun) == NUM_FIXED_BLOCKS)
7728 return;
7730 sel_global_init ();
7732 for (rgn = 0; rgn < nr_regions; rgn++)
7733 sel_sched_region (rgn);
7735 sel_global_finish ();
7738 #endif