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