Line data Source code
1 : /* Instruction scheduling pass. Selective scheduler and pipeliner.
2 : Copyright (C) 2006-2026 Free Software Foundation, Inc.
3 :
4 : This file is part of GCC.
5 :
6 : GCC is free software; you can redistribute it and/or modify it under
7 : the terms of the GNU General Public License as published by the Free
8 : Software Foundation; either version 3, or (at your option) any later
9 : version.
10 :
11 : GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 : WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 : FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 : for more details.
15 :
16 : You should have received a copy of the GNU General Public License
17 : along with GCC; see the file COPYING3. If not see
18 : <http://www.gnu.org/licenses/>. */
19 :
20 : #include "config.h"
21 : #include "system.h"
22 : #include "coretypes.h"
23 : #include "backend.h"
24 : #include "cfghooks.h"
25 : #include "tree.h"
26 : #include "rtl.h"
27 : #include "df.h"
28 : #include "memmodel.h"
29 : #include "tm_p.h"
30 : #include "cfgrtl.h"
31 : #include "cfganal.h"
32 : #include "cfgbuild.h"
33 : #include "insn-config.h"
34 : #include "insn-attr.h"
35 : #include "recog.h"
36 : #include "target.h"
37 : #include "sched-int.h"
38 : #include "emit-rtl.h" /* FIXME: Can go away once crtl is moved to rtl.h. */
39 :
40 : #ifdef INSN_SCHEDULING
41 : #include "regset.h"
42 : #include "cfgloop.h"
43 : #include "sel-sched-ir.h"
44 : /* We don't have to use it except for sel_print_insn. */
45 : #include "sel-sched-dump.h"
46 :
47 : /* A vector holding bb info for whole scheduling pass. */
48 : vec<sel_global_bb_info_def> sel_global_bb_info;
49 :
50 : /* A vector holding bb info. */
51 : vec<sel_region_bb_info_def> sel_region_bb_info;
52 :
53 : /* A pool for allocating all lists. */
54 : object_allocator<_list_node> sched_lists_pool ("sel-sched-lists");
55 :
56 : /* Data structure to describe interaction with the generic scheduler utils. */
57 : static struct common_sched_info_def sel_common_sched_info;
58 :
59 : /* The loop nest being pipelined. */
60 : class loop *current_loop_nest;
61 :
62 : /* LOOP_NESTS is a vector containing the corresponding loop nest for
63 : each region. */
64 : static vec<loop_p> loop_nests;
65 :
66 : /* Saves blocks already in loop regions, indexed by bb->index. */
67 : static sbitmap bbs_in_loop_rgns = NULL;
68 :
69 : /* CFG hooks that are saved before changing create_basic_block hook. */
70 : static const struct cfg_hooks *orig_cfg_hooks;
71 :
72 :
73 : /* Array containing reverse topological index of function basic blocks,
74 : indexed by BB->INDEX. */
75 : static int *rev_top_order_index = NULL;
76 :
77 : /* Length of the above array. */
78 : static int rev_top_order_index_len = -1;
79 :
80 : /* A regset pool structure. */
81 : static struct
82 : {
83 : /* The stack to which regsets are returned. */
84 : regset *v;
85 :
86 : /* Its pointer. */
87 : int n;
88 :
89 : /* Its size. */
90 : int s;
91 :
92 : /* In VV we save all generated regsets so that, when destructing the
93 : pool, we can compare it with V and check that every regset was returned
94 : back to pool. */
95 : regset *vv;
96 :
97 : /* The pointer of VV stack. */
98 : int nn;
99 :
100 : /* Its size. */
101 : int ss;
102 :
103 : /* The difference between allocated and returned regsets. */
104 : int diff;
105 : } regset_pool = { NULL, 0, 0, NULL, 0, 0, 0 };
106 :
107 : /* This represents the nop pool. */
108 : static struct
109 : {
110 : /* The vector which holds previously emitted nops. */
111 : insn_t *v;
112 :
113 : /* Its pointer. */
114 : int n;
115 :
116 : /* Its size. */
117 : int s;
118 : } nop_pool = { NULL, 0, 0 };
119 :
120 : /* The pool for basic block notes. */
121 : static vec<rtx_note *> bb_note_pool;
122 :
123 : /* A NOP pattern used to emit placeholder insns. */
124 : rtx nop_pattern = NULL_RTX;
125 : /* A special instruction that resides in EXIT_BLOCK.
126 : EXIT_INSN is successor of the insns that lead to EXIT_BLOCK. */
127 : rtx_insn *exit_insn = NULL;
128 :
129 : /* TRUE if while scheduling current region, which is loop, its preheader
130 : was removed. */
131 : bool preheader_removed = false;
132 :
133 :
134 : /* Forward static declarations. */
135 : static void fence_clear (fence_t);
136 :
137 : static void deps_init_id (idata_t, insn_t, bool);
138 : static void init_id_from_df (idata_t, insn_t, bool);
139 : static expr_t set_insn_init (expr_t, vinsn_t, int);
140 :
141 : static void cfg_preds (basic_block, insn_t **, int *);
142 : static void prepare_insn_expr (insn_t, int);
143 : static void free_history_vect (vec<expr_history_def> &);
144 :
145 : static void move_bb_info (basic_block, basic_block);
146 : static void remove_empty_bb (basic_block, bool);
147 : static void sel_merge_blocks (basic_block, basic_block);
148 : static void sel_remove_loop_preheader (void);
149 : static bool bb_has_removable_jump_to_p (basic_block, basic_block);
150 :
151 : static bool insn_is_the_only_one_in_bb_p (insn_t);
152 : static void create_initial_data_sets (basic_block);
153 :
154 : static void free_av_set (basic_block);
155 : static void invalidate_av_set (basic_block);
156 : static void extend_insn_data (void);
157 : static void sel_init_new_insn (insn_t, int, int = -1);
158 : static void finish_insns (void);
159 :
160 : /* Various list functions. */
161 :
162 : /* Copy an instruction list L. */
163 : ilist_t
164 4126 : ilist_copy (ilist_t l)
165 : {
166 4126 : ilist_t head = NULL, *tailp = &head;
167 :
168 18482 : while (l)
169 : {
170 14356 : ilist_add (tailp, ILIST_INSN (l));
171 14356 : tailp = &ILIST_NEXT (*tailp);
172 14356 : l = ILIST_NEXT (l);
173 : }
174 :
175 4126 : return head;
176 : }
177 :
178 : /* Invert an instruction list L. */
179 : ilist_t
180 0 : ilist_invert (ilist_t l)
181 : {
182 0 : ilist_t res = NULL;
183 :
184 0 : while (l)
185 : {
186 0 : ilist_add (&res, ILIST_INSN (l));
187 0 : l = ILIST_NEXT (l);
188 : }
189 :
190 0 : return res;
191 : }
192 :
193 : /* Add a new boundary to the LP list with parameters TO, PTR, and DC. */
194 : void
195 5936 : blist_add (blist_t *lp, insn_t to, ilist_t ptr, deps_t dc)
196 : {
197 5936 : bnd_t bnd;
198 :
199 5936 : _list_add (lp);
200 5936 : bnd = BLIST_BND (*lp);
201 :
202 5936 : BND_TO (bnd) = to;
203 5936 : BND_PTR (bnd) = ptr;
204 5936 : BND_AV (bnd) = NULL;
205 5936 : BND_AV1 (bnd) = NULL;
206 5936 : BND_DC (bnd) = dc;
207 5936 : }
208 :
209 : /* Remove the list note pointed to by LP. */
210 : void
211 5936 : blist_remove (blist_t *lp)
212 : {
213 5936 : bnd_t b = BLIST_BND (*lp);
214 :
215 5936 : av_set_clear (&BND_AV (b));
216 5936 : av_set_clear (&BND_AV1 (b));
217 5936 : ilist_clear (&BND_PTR (b));
218 :
219 5936 : _list_remove (lp);
220 5936 : }
221 :
222 : /* Init a fence tail L. */
223 : void
224 1686 : flist_tail_init (flist_tail_t l)
225 : {
226 1686 : FLIST_TAIL_HEAD (l) = NULL;
227 1686 : FLIST_TAIL_TAILP (l) = &FLIST_TAIL_HEAD (l);
228 1686 : }
229 :
230 : /* Try to find fence corresponding to INSN in L. */
231 : fence_t
232 64479 : flist_lookup (flist_t l, insn_t insn)
233 : {
234 135907 : while (l)
235 : {
236 71445 : if (FENCE_INSN (FLIST_FENCE (l)) == insn)
237 17 : return FLIST_FENCE (l);
238 :
239 71428 : l = FLIST_NEXT (l);
240 : }
241 :
242 : return NULL;
243 : }
244 :
245 : /* Init the fields of F before running fill_insns. */
246 : static void
247 1810 : init_fence_for_scheduling (fence_t f)
248 : {
249 1810 : FENCE_BNDS (f) = NULL;
250 1810 : FENCE_PROCESSED_P (f) = false;
251 1810 : FENCE_SCHEDULED_P (f) = false;
252 815 : }
253 :
254 : /* Add new fence consisting of INSN and STATE to the list pointed to by LP. */
255 : static void
256 995 : flist_add (flist_t *lp, insn_t insn, state_t state, deps_t dc, void *tc,
257 : insn_t last_scheduled_insn, vec<rtx_insn *, va_gc> *executing_insns,
258 : int *ready_ticks, int ready_ticks_size, insn_t sched_next,
259 : int cycle, int cycle_issued_insns, int issue_more,
260 : bool starts_cycle_p, bool after_stall_p)
261 : {
262 995 : fence_t f;
263 :
264 995 : _list_add (lp);
265 995 : f = FLIST_FENCE (*lp);
266 :
267 995 : FENCE_INSN (f) = insn;
268 :
269 995 : gcc_assert (state != NULL);
270 995 : FENCE_STATE (f) = state;
271 :
272 995 : FENCE_CYCLE (f) = cycle;
273 995 : FENCE_ISSUED_INSNS (f) = cycle_issued_insns;
274 995 : FENCE_STARTS_CYCLE_P (f) = starts_cycle_p;
275 995 : FENCE_AFTER_STALL_P (f) = after_stall_p;
276 :
277 995 : gcc_assert (dc != NULL);
278 995 : FENCE_DC (f) = dc;
279 :
280 995 : gcc_assert (tc != NULL || targetm.sched.alloc_sched_context == NULL);
281 995 : FENCE_TC (f) = tc;
282 :
283 995 : FENCE_LAST_SCHEDULED_INSN (f) = last_scheduled_insn;
284 995 : FENCE_ISSUE_MORE (f) = issue_more;
285 995 : FENCE_EXECUTING_INSNS (f) = executing_insns;
286 995 : FENCE_READY_TICKS (f) = ready_ticks;
287 995 : FENCE_READY_TICKS_SIZE (f) = ready_ticks_size;
288 995 : FENCE_SCHED_NEXT (f) = sched_next;
289 :
290 995 : init_fence_for_scheduling (f);
291 995 : }
292 :
293 : /* Remove the head node of the list pointed to by LP. */
294 : static void
295 1810 : flist_remove (flist_t *lp)
296 : {
297 1810 : if (FENCE_INSN (FLIST_FENCE (*lp)))
298 994 : fence_clear (FLIST_FENCE (*lp));
299 1810 : _list_remove (lp);
300 1810 : }
301 :
302 : /* Clear the fence list pointed to by LP. */
303 : void
304 1667 : flist_clear (flist_t *lp)
305 : {
306 3477 : while (*lp)
307 1810 : flist_remove (lp);
308 1667 : }
309 :
310 : /* Add ORIGINAL_INSN the def list DL honoring CROSSED_CALL_ABIS. */
311 : void
312 3888 : def_list_add (def_list_t *dl, insn_t original_insn,
313 : unsigned int crossed_call_abis)
314 : {
315 3888 : def_t d;
316 :
317 3888 : _list_add (dl);
318 3888 : d = DEF_LIST_DEF (*dl);
319 :
320 3888 : d->orig_insn = original_insn;
321 3888 : d->crossed_call_abis = crossed_call_abis;
322 3888 : }
323 :
324 :
325 : /* Functions to work with target contexts. */
326 :
327 : /* Bulk target context. It is convenient for debugging purposes to ensure
328 : that there are no uninitialized (null) target contexts. */
329 : static tc_t bulk_tc = (tc_t) 1;
330 :
331 : /* Target hooks wrappers. In the future we can provide some default
332 : implementations for them. */
333 :
334 : /* Allocate a store for the target context. */
335 : static tc_t
336 1167 : alloc_target_context (void)
337 : {
338 1167 : return (targetm.sched.alloc_sched_context
339 1167 : ? targetm.sched.alloc_sched_context () : bulk_tc);
340 : }
341 :
342 : /* Init target context TC.
343 : If CLEAN_P is true, then make TC as it is beginning of the scheduler.
344 : Otherwise, copy current backend context to TC. */
345 : static void
346 2988 : init_target_context (tc_t tc, bool clean_p)
347 : {
348 0 : if (targetm.sched.init_sched_context)
349 0 : targetm.sched.init_sched_context (tc, clean_p);
350 0 : }
351 :
352 : /* Allocate and initialize a target context. Meaning of CLEAN_P is the same as
353 : int init_target_context (). */
354 : tc_t
355 1005 : create_target_context (bool clean_p)
356 : {
357 1005 : tc_t tc = alloc_target_context ();
358 :
359 1005 : init_target_context (tc, clean_p);
360 1005 : return tc;
361 : }
362 :
363 : /* Copy TC to the current backend context. */
364 : void
365 2134 : set_target_context (tc_t tc)
366 : {
367 2134 : if (targetm.sched.set_sched_context)
368 0 : targetm.sched.set_sched_context (tc);
369 2134 : }
370 :
371 : /* TC is about to be destroyed. Free any internal data. */
372 : static void
373 2988 : clear_target_context (tc_t tc)
374 : {
375 0 : if (targetm.sched.clear_sched_context)
376 0 : targetm.sched.clear_sched_context (tc);
377 0 : }
378 :
379 : /* Clear and free it. */
380 : static void
381 1167 : delete_target_context (tc_t tc)
382 : {
383 1167 : clear_target_context (tc);
384 :
385 1167 : if (targetm.sched.free_sched_context)
386 0 : targetm.sched.free_sched_context (tc);
387 1167 : }
388 :
389 : /* Make a copy of FROM in TO.
390 : NB: May be this should be a hook. */
391 : static void
392 162 : copy_target_context (tc_t to, tc_t from)
393 : {
394 162 : tc_t tmp = create_target_context (false);
395 :
396 162 : set_target_context (from);
397 162 : init_target_context (to, false);
398 :
399 162 : set_target_context (tmp);
400 162 : delete_target_context (tmp);
401 162 : }
402 :
403 : /* Create a copy of TC. */
404 : static tc_t
405 162 : create_copy_of_target_context (tc_t tc)
406 : {
407 162 : tc_t copy = alloc_target_context ();
408 :
409 162 : copy_target_context (copy, tc);
410 :
411 162 : return copy;
412 : }
413 :
414 : /* Clear TC and initialize it according to CLEAN_P. The meaning of CLEAN_P
415 : is the same as in init_target_context (). */
416 : void
417 1821 : reset_target_context (tc_t tc, bool clean_p)
418 : {
419 1821 : clear_target_context (tc);
420 1821 : init_target_context (tc, clean_p);
421 1821 : }
422 :
423 : /* Functions to work with dependence contexts.
424 : Dc (aka deps context, aka deps_t, aka class deps_desc *) is short for dependence
425 : context. It accumulates information about processed insns to decide if
426 : current insn is dependent on the processed ones. */
427 :
428 : /* Make a copy of FROM in TO. */
429 : static void
430 162 : copy_deps_context (deps_t to, deps_t from)
431 : {
432 162 : init_deps (to, false);
433 162 : deps_join (to, from);
434 162 : }
435 :
436 : /* Allocate store for dep context. */
437 : static deps_t
438 1005 : alloc_deps_context (void)
439 : {
440 0 : return XNEW (class deps_desc);
441 : }
442 :
443 : /* Allocate and initialize dep context. */
444 : static deps_t
445 843 : create_deps_context (void)
446 : {
447 843 : deps_t dc = alloc_deps_context ();
448 :
449 843 : init_deps (dc, false);
450 843 : return dc;
451 : }
452 :
453 : /* Create a copy of FROM. */
454 : static deps_t
455 162 : create_copy_of_deps_context (deps_t from)
456 : {
457 162 : deps_t to = alloc_deps_context ();
458 :
459 162 : copy_deps_context (to, from);
460 162 : return to;
461 : }
462 :
463 : /* Clean up internal data of DC. */
464 : static void
465 1016 : clear_deps_context (deps_t dc)
466 : {
467 0 : free_deps (dc);
468 0 : }
469 :
470 : /* Clear and free DC. */
471 : static void
472 1005 : delete_deps_context (deps_t dc)
473 : {
474 0 : clear_deps_context (dc);
475 1005 : free (dc);
476 994 : }
477 :
478 : /* Clear and init DC. */
479 : static void
480 11 : reset_deps_context (deps_t dc)
481 : {
482 11 : clear_deps_context (dc);
483 11 : init_deps (dc, false);
484 11 : }
485 :
486 : /* This structure describes the dependence analysis hooks for advancing
487 : dependence context. */
488 : static struct sched_deps_info_def advance_deps_context_sched_deps_info =
489 : {
490 : NULL,
491 :
492 : NULL, /* start_insn */
493 : NULL, /* finish_insn */
494 : NULL, /* start_lhs */
495 : NULL, /* finish_lhs */
496 : NULL, /* start_rhs */
497 : NULL, /* finish_rhs */
498 : haifa_note_reg_set,
499 : haifa_note_reg_clobber,
500 : haifa_note_reg_use,
501 : NULL, /* note_mem_dep */
502 : NULL, /* note_dep */
503 :
504 : 0, 0, 0
505 : };
506 :
507 : /* Process INSN and add its impact on DC. */
508 : void
509 8055 : advance_deps_context (deps_t dc, insn_t insn)
510 : {
511 8055 : sched_deps_info = &advance_deps_context_sched_deps_info;
512 8055 : deps_analyze_insn (dc, insn);
513 8055 : }
514 :
515 :
516 : /* Functions to work with DFA states. */
517 :
518 : /* Allocate store for a DFA state. */
519 : static state_t
520 1005 : state_alloc (void)
521 : {
522 0 : return xmalloc (dfa_state_size);
523 : }
524 :
525 : /* Allocate and initialize DFA state. */
526 : static state_t
527 843 : state_create (void)
528 : {
529 843 : state_t state = state_alloc ();
530 :
531 843 : state_reset (state);
532 843 : advance_state (state);
533 843 : return state;
534 : }
535 :
536 : /* Free DFA state. */
537 : static void
538 11 : state_free (state_t state)
539 : {
540 11 : free (state);
541 0 : }
542 :
543 : /* Make a copy of FROM in TO. */
544 : static void
545 162 : state_copy (state_t to, state_t from)
546 : {
547 162 : memcpy (to, from, dfa_state_size);
548 0 : }
549 :
550 : /* Create a copy of FROM. */
551 : static state_t
552 162 : state_create_copy (state_t from)
553 : {
554 162 : state_t to = state_alloc ();
555 :
556 162 : state_copy (to, from);
557 162 : return to;
558 : }
559 :
560 :
561 : /* Functions to work with fences. */
562 :
563 : /* Clear the fence. */
564 : static void
565 994 : fence_clear (fence_t f)
566 : {
567 994 : state_t s = FENCE_STATE (f);
568 994 : deps_t dc = FENCE_DC (f);
569 994 : void *tc = FENCE_TC (f);
570 :
571 994 : ilist_clear (&FENCE_BNDS (f));
572 :
573 994 : gcc_assert ((s != NULL && dc != NULL && tc != NULL)
574 : || (s == NULL && dc == NULL && tc == NULL));
575 :
576 994 : free (s);
577 :
578 994 : if (dc != NULL)
579 994 : delete_deps_context (dc);
580 :
581 994 : if (tc != NULL)
582 994 : delete_target_context (tc);
583 994 : vec_free (FENCE_EXECUTING_INSNS (f));
584 994 : free (FENCE_READY_TICKS (f));
585 994 : FENCE_READY_TICKS (f) = NULL;
586 994 : }
587 :
588 : /* Init a list of fences with successors of OLD_FENCE. */
589 : void
590 752 : init_fences (insn_t old_fence)
591 : {
592 752 : insn_t succ;
593 752 : succ_iterator si;
594 752 : bool first = true;
595 752 : int ready_ticks_size = get_max_uid () + 1;
596 :
597 1504 : FOR_EACH_SUCC_1 (succ, si, old_fence,
598 : SUCCS_NORMAL | SUCCS_SKIP_TO_LOOP_EXITS)
599 : {
600 :
601 752 : if (first)
602 : first = false;
603 : else
604 0 : gcc_assert (flag_sel_sched_pipelining_outer_loops);
605 :
606 752 : flist_add (&fences, succ,
607 : state_create (),
608 : create_deps_context () /* dc */,
609 : create_target_context (true) /* tc */,
610 : NULL /* last_scheduled_insn */,
611 : NULL, /* executing_insns */
612 752 : XCNEWVEC (int, ready_ticks_size), /* ready_ticks */
613 : ready_ticks_size,
614 : NULL /* sched_next */,
615 : 1 /* cycle */, 0 /* cycle_issued_insns */,
616 : issue_rate, /* issue_more */
617 : 1 /* starts_cycle_p */, 0 /* after_stall_p */);
618 : }
619 752 : }
620 :
621 : /* Merges two fences (filling fields of fence F with resulting values) by
622 : following rules: 1) state, target context and last scheduled insn are
623 : propagated from fallthrough edge if it is available;
624 : 2) deps context and cycle is propagated from more probable edge;
625 : 3) all other fields are set to corresponding constant values.
626 :
627 : INSN, STATE, DC, TC, LAST_SCHEDULED_INSN, EXECUTING_INSNS,
628 : READY_TICKS, READY_TICKS_SIZE, SCHED_NEXT, CYCLE, ISSUE_MORE
629 : and AFTER_STALL_P are the corresponding fields of the second fence. */
630 : static void
631 11 : merge_fences (fence_t f, insn_t insn,
632 : state_t state, deps_t dc, void *tc,
633 : rtx_insn *last_scheduled_insn,
634 : vec<rtx_insn *, va_gc> *executing_insns,
635 : int *ready_ticks, int ready_ticks_size,
636 : rtx sched_next, int cycle, int issue_more, bool after_stall_p)
637 : {
638 11 : insn_t last_scheduled_insn_old = FENCE_LAST_SCHEDULED_INSN (f);
639 :
640 11 : gcc_assert (sel_bb_head_p (FENCE_INSN (f))
641 : && !sched_next && !FENCE_SCHED_NEXT (f));
642 :
643 : /* Check if we can decide which path fences came.
644 : If we can't (or don't want to) - reset all. */
645 11 : if (last_scheduled_insn == NULL
646 11 : || last_scheduled_insn_old == NULL
647 : /* This is a case when INSN is reachable on several paths from
648 : one insn (this can happen when pipelining of outer loops is on and
649 : there are two edges: one going around of inner loop and the other -
650 : right through it; in such case just reset everything). */
651 0 : || last_scheduled_insn == last_scheduled_insn_old)
652 : {
653 11 : state_reset (FENCE_STATE (f));
654 11 : state_free (state);
655 :
656 11 : reset_deps_context (FENCE_DC (f));
657 11 : delete_deps_context (dc);
658 :
659 11 : reset_target_context (FENCE_TC (f), true);
660 11 : delete_target_context (tc);
661 :
662 11 : if (cycle > FENCE_CYCLE (f))
663 1 : FENCE_CYCLE (f) = cycle;
664 :
665 11 : FENCE_LAST_SCHEDULED_INSN (f) = NULL;
666 11 : FENCE_ISSUE_MORE (f) = issue_rate;
667 11 : vec_free (executing_insns);
668 11 : free (ready_ticks);
669 11 : if (FENCE_EXECUTING_INSNS (f))
670 3 : FENCE_EXECUTING_INSNS (f)->block_remove (0,
671 3 : FENCE_EXECUTING_INSNS (f)->length ());
672 11 : if (FENCE_READY_TICKS (f))
673 11 : memset (FENCE_READY_TICKS (f), 0, FENCE_READY_TICKS_SIZE (f));
674 : }
675 : else
676 : {
677 0 : edge edge_old = NULL, edge_new = NULL;
678 0 : edge candidate;
679 0 : succ_iterator si;
680 0 : insn_t succ;
681 :
682 : /* Find fallthrough edge. */
683 0 : gcc_assert (BLOCK_FOR_INSN (insn)->prev_bb);
684 0 : candidate = find_fallthru_edge_from (BLOCK_FOR_INSN (insn)->prev_bb);
685 :
686 0 : if (!candidate
687 0 : || (candidate->src != BLOCK_FOR_INSN (last_scheduled_insn)
688 0 : && candidate->src != BLOCK_FOR_INSN (last_scheduled_insn_old)))
689 : {
690 : /* No fallthrough edge leading to basic block of INSN. */
691 0 : state_reset (FENCE_STATE (f));
692 0 : state_free (state);
693 :
694 0 : reset_target_context (FENCE_TC (f), true);
695 0 : delete_target_context (tc);
696 :
697 0 : FENCE_LAST_SCHEDULED_INSN (f) = NULL;
698 0 : FENCE_ISSUE_MORE (f) = issue_rate;
699 : }
700 : else
701 0 : if (candidate->src == BLOCK_FOR_INSN (last_scheduled_insn))
702 : {
703 0 : state_free (FENCE_STATE (f));
704 0 : FENCE_STATE (f) = state;
705 :
706 0 : delete_target_context (FENCE_TC (f));
707 0 : FENCE_TC (f) = tc;
708 :
709 0 : FENCE_LAST_SCHEDULED_INSN (f) = last_scheduled_insn;
710 0 : FENCE_ISSUE_MORE (f) = issue_more;
711 : }
712 : else
713 : {
714 : /* Leave STATE, TC and LAST_SCHEDULED_INSN fields untouched. */
715 0 : state_free (state);
716 0 : delete_target_context (tc);
717 :
718 0 : gcc_assert (BLOCK_FOR_INSN (insn)->prev_bb
719 : != BLOCK_FOR_INSN (last_scheduled_insn));
720 : }
721 :
722 : /* Find edge of first predecessor (last_scheduled_insn_old->insn). */
723 0 : FOR_EACH_SUCC_1 (succ, si, last_scheduled_insn_old,
724 : SUCCS_NORMAL | SUCCS_SKIP_TO_LOOP_EXITS)
725 : {
726 0 : if (succ == insn)
727 : {
728 : /* No same successor allowed from several edges. */
729 0 : gcc_assert (!edge_old);
730 0 : edge_old = si.e1;
731 : }
732 : }
733 : /* Find edge of second predecessor (last_scheduled_insn->insn). */
734 0 : FOR_EACH_SUCC_1 (succ, si, last_scheduled_insn,
735 : SUCCS_NORMAL | SUCCS_SKIP_TO_LOOP_EXITS)
736 : {
737 0 : if (succ == insn)
738 : {
739 : /* No same successor allowed from several edges. */
740 0 : gcc_assert (!edge_new);
741 0 : edge_new = si.e1;
742 : }
743 : }
744 :
745 : /* Check if we can choose most probable predecessor. */
746 0 : if (edge_old == NULL || edge_new == NULL)
747 : {
748 0 : reset_deps_context (FENCE_DC (f));
749 0 : delete_deps_context (dc);
750 0 : vec_free (executing_insns);
751 0 : free (ready_ticks);
752 :
753 0 : FENCE_CYCLE (f) = MAX (FENCE_CYCLE (f), cycle);
754 0 : if (FENCE_EXECUTING_INSNS (f))
755 0 : FENCE_EXECUTING_INSNS (f)->block_remove (0,
756 0 : FENCE_EXECUTING_INSNS (f)->length ());
757 0 : if (FENCE_READY_TICKS (f))
758 0 : memset (FENCE_READY_TICKS (f), 0, FENCE_READY_TICKS_SIZE (f));
759 : }
760 : else
761 0 : if (edge_new->probability > edge_old->probability)
762 : {
763 0 : delete_deps_context (FENCE_DC (f));
764 0 : FENCE_DC (f) = dc;
765 0 : vec_free (FENCE_EXECUTING_INSNS (f));
766 0 : FENCE_EXECUTING_INSNS (f) = executing_insns;
767 0 : free (FENCE_READY_TICKS (f));
768 0 : FENCE_READY_TICKS (f) = ready_ticks;
769 0 : FENCE_READY_TICKS_SIZE (f) = ready_ticks_size;
770 0 : FENCE_CYCLE (f) = cycle;
771 : }
772 : else
773 : {
774 : /* Leave DC and CYCLE untouched. */
775 0 : delete_deps_context (dc);
776 0 : vec_free (executing_insns);
777 0 : free (ready_ticks);
778 : }
779 : }
780 :
781 : /* Fill remaining invariant fields. */
782 11 : if (after_stall_p)
783 1 : FENCE_AFTER_STALL_P (f) = 1;
784 :
785 11 : FENCE_ISSUED_INSNS (f) = 0;
786 11 : FENCE_STARTS_CYCLE_P (f) = 1;
787 11 : FENCE_SCHED_NEXT (f) = NULL;
788 11 : }
789 :
790 : /* Add a new fence to NEW_FENCES list, initializing it from all
791 : other parameters. */
792 : static void
793 253 : add_to_fences (flist_tail_t new_fences, insn_t insn,
794 : state_t state, deps_t dc, void *tc,
795 : rtx_insn *last_scheduled_insn,
796 : vec<rtx_insn *, va_gc> *executing_insns, int *ready_ticks,
797 : int ready_ticks_size, rtx_insn *sched_next, int cycle,
798 : int cycle_issued_insns, int issue_rate,
799 : bool starts_cycle_p, bool after_stall_p)
800 : {
801 253 : fence_t f = flist_lookup (FLIST_TAIL_HEAD (new_fences), insn);
802 :
803 253 : if (! f)
804 : {
805 243 : flist_add (FLIST_TAIL_TAILP (new_fences), insn, state, dc, tc,
806 : last_scheduled_insn, executing_insns, ready_ticks,
807 : ready_ticks_size, sched_next, cycle, cycle_issued_insns,
808 : issue_rate, starts_cycle_p, after_stall_p);
809 :
810 243 : FLIST_TAIL_TAILP (new_fences)
811 243 : = &FLIST_NEXT (*FLIST_TAIL_TAILP (new_fences));
812 : }
813 : else
814 : {
815 10 : merge_fences (f, insn, state, dc, tc, last_scheduled_insn,
816 : executing_insns, ready_ticks, ready_ticks_size,
817 : sched_next, cycle, issue_rate, after_stall_p);
818 : }
819 253 : }
820 :
821 : /* Move the first fence in the OLD_FENCES list to NEW_FENCES. */
822 : void
823 816 : move_fence_to_fences (flist_t old_fences, flist_tail_t new_fences)
824 : {
825 816 : fence_t f, old;
826 816 : flist_t *tailp = FLIST_TAIL_TAILP (new_fences);
827 :
828 816 : old = FLIST_FENCE (old_fences);
829 816 : f = flist_lookup (FLIST_TAIL_HEAD (new_fences),
830 : FENCE_INSN (FLIST_FENCE (old_fences)));
831 816 : if (f)
832 : {
833 1 : merge_fences (f, old->insn, old->state, old->dc, old->tc,
834 : old->last_scheduled_insn, old->executing_insns,
835 : old->ready_ticks, old->ready_ticks_size,
836 1 : old->sched_next, old->cycle, old->issue_more,
837 1 : old->after_stall_p);
838 : }
839 : else
840 : {
841 815 : _list_add (tailp);
842 815 : FLIST_TAIL_TAILP (new_fences) = &FLIST_NEXT (*tailp);
843 815 : *FLIST_FENCE (*tailp) = *old;
844 815 : init_fence_for_scheduling (FLIST_FENCE (*tailp));
845 : }
846 816 : FENCE_INSN (old) = NULL;
847 816 : }
848 :
849 : /* Add a new fence to NEW_FENCES list and initialize most of its data
850 : as a clean one. */
851 : void
852 91 : add_clean_fence_to_fences (flist_tail_t new_fences, insn_t succ, fence_t fence)
853 : {
854 91 : int ready_ticks_size = get_max_uid () + 1;
855 :
856 91 : add_to_fences (new_fences,
857 : succ, state_create (), create_deps_context (),
858 : create_target_context (true),
859 : NULL, NULL,
860 91 : XCNEWVEC (int, ready_ticks_size), ready_ticks_size,
861 91 : NULL, FENCE_CYCLE (fence) + 1,
862 91 : 0, issue_rate, 1, FENCE_AFTER_STALL_P (fence));
863 91 : }
864 :
865 : /* Add a new fence to NEW_FENCES list and initialize all of its data
866 : from FENCE and SUCC. */
867 : void
868 162 : add_dirty_fence_to_fences (flist_tail_t new_fences, insn_t succ, fence_t fence)
869 : {
870 162 : int * new_ready_ticks
871 162 : = XNEWVEC (int, FENCE_READY_TICKS_SIZE (fence));
872 :
873 162 : memcpy (new_ready_ticks, FENCE_READY_TICKS (fence),
874 162 : FENCE_READY_TICKS_SIZE (fence) * sizeof (int));
875 162 : add_to_fences (new_fences,
876 : succ, state_create_copy (FENCE_STATE (fence)),
877 : create_copy_of_deps_context (FENCE_DC (fence)),
878 : create_copy_of_target_context (FENCE_TC (fence)),
879 : FENCE_LAST_SCHEDULED_INSN (fence),
880 : vec_safe_copy (FENCE_EXECUTING_INSNS (fence)),
881 : new_ready_ticks,
882 : FENCE_READY_TICKS_SIZE (fence),
883 : FENCE_SCHED_NEXT (fence),
884 : FENCE_CYCLE (fence),
885 : FENCE_ISSUED_INSNS (fence),
886 : FENCE_ISSUE_MORE (fence),
887 162 : FENCE_STARTS_CYCLE_P (fence),
888 162 : FENCE_AFTER_STALL_P (fence));
889 162 : }
890 :
891 :
892 : /* Functions to work with regset and nop pools. */
893 :
894 : /* Returns the new regset from pool. It might have some of the bits set
895 : from the previous usage. */
896 : regset
897 50542 : get_regset_from_pool (void)
898 : {
899 50542 : regset rs;
900 :
901 50542 : if (regset_pool.n != 0)
902 39892 : rs = regset_pool.v[--regset_pool.n];
903 : else
904 : /* We need to create the regset. */
905 : {
906 10650 : rs = ALLOC_REG_SET (®_obstack);
907 :
908 10650 : if (regset_pool.nn == regset_pool.ss)
909 798 : regset_pool.vv = XRESIZEVEC (regset, regset_pool.vv,
910 : (regset_pool.ss = 2 * regset_pool.ss + 1));
911 10650 : regset_pool.vv[regset_pool.nn++] = rs;
912 : }
913 :
914 50542 : regset_pool.diff++;
915 :
916 50542 : return rs;
917 : }
918 :
919 : /* Same as above, but returns the empty regset. */
920 : regset
921 27927 : get_clear_regset_from_pool (void)
922 : {
923 27927 : regset rs = get_regset_from_pool ();
924 :
925 27927 : CLEAR_REG_SET (rs);
926 27927 : return rs;
927 : }
928 :
929 : /* Return regset RS to the pool for future use. */
930 : void
931 50542 : return_regset_to_pool (regset rs)
932 : {
933 50542 : gcc_assert (rs);
934 50542 : regset_pool.diff--;
935 :
936 50542 : if (regset_pool.n == regset_pool.s)
937 798 : regset_pool.v = XRESIZEVEC (regset, regset_pool.v,
938 : (regset_pool.s = 2 * regset_pool.s + 1));
939 50542 : regset_pool.v[regset_pool.n++] = rs;
940 50542 : }
941 :
942 : /* This is used as a qsort callback for sorting regset pool stacks.
943 : X and XX are addresses of two regsets. They are never equal. */
944 : static int
945 772360 : cmp_v_in_regset_pool (const void *x, const void *xx)
946 : {
947 772360 : uintptr_t r1 = (uintptr_t) *((const regset *) x);
948 772360 : uintptr_t r2 = (uintptr_t) *((const regset *) xx);
949 772360 : if (r1 > r2)
950 : return 1;
951 389718 : else if (r1 < r2)
952 : return -1;
953 0 : gcc_unreachable ();
954 : }
955 :
956 : /* Free the regset pool possibly checking for memory leaks. */
957 : void
958 131 : free_regset_pool (void)
959 : {
960 131 : if (flag_checking)
961 : {
962 131 : regset *v = regset_pool.v;
963 131 : int i = 0;
964 131 : int n = regset_pool.n;
965 :
966 131 : regset *vv = regset_pool.vv;
967 131 : int ii = 0;
968 131 : int nn = regset_pool.nn;
969 :
970 131 : int diff = 0;
971 :
972 131 : gcc_assert (n <= nn);
973 :
974 : /* Sort both vectors so it will be possible to compare them. */
975 131 : qsort (v, n, sizeof (*v), cmp_v_in_regset_pool);
976 131 : qsort (vv, nn, sizeof (*vv), cmp_v_in_regset_pool);
977 :
978 10912 : while (ii < nn)
979 : {
980 10650 : if (v[i] == vv[ii])
981 10650 : i++;
982 : else
983 : /* VV[II] was lost. */
984 0 : diff++;
985 :
986 10650 : ii++;
987 : }
988 :
989 131 : gcc_assert (diff == regset_pool.diff);
990 : }
991 :
992 : /* If not true - we have a memory leak. */
993 131 : gcc_assert (regset_pool.diff == 0);
994 :
995 10781 : while (regset_pool.n)
996 : {
997 10650 : --regset_pool.n;
998 10650 : FREE_REG_SET (regset_pool.v[regset_pool.n]);
999 : }
1000 :
1001 131 : free (regset_pool.v);
1002 131 : regset_pool.v = NULL;
1003 131 : regset_pool.s = 0;
1004 :
1005 131 : free (regset_pool.vv);
1006 131 : regset_pool.vv = NULL;
1007 131 : regset_pool.nn = 0;
1008 131 : regset_pool.ss = 0;
1009 :
1010 131 : regset_pool.diff = 0;
1011 131 : }
1012 :
1013 :
1014 : /* Functions to work with nop pools. NOP insns are used as temporary
1015 : placeholders of the insns being scheduled to allow correct update of
1016 : the data sets. When update is finished, NOPs are deleted. */
1017 :
1018 : /* A vinsn that is used to represent a nop. This vinsn is shared among all
1019 : nops sel-sched generates. */
1020 : static vinsn_t nop_vinsn = NULL;
1021 :
1022 : /* Emit a nop before INSN, taking it from pool. */
1023 : insn_t
1024 1976 : get_nop_from_pool (insn_t insn)
1025 : {
1026 1976 : rtx nop_pat;
1027 1976 : insn_t nop;
1028 1976 : bool old_p = nop_pool.n != 0;
1029 1976 : int flags;
1030 :
1031 1976 : if (old_p)
1032 1155 : nop_pat = nop_pool.v[--nop_pool.n];
1033 : else
1034 821 : nop_pat = nop_pattern;
1035 :
1036 1976 : nop = emit_insn_before (nop_pat, insn);
1037 :
1038 1976 : if (old_p)
1039 : flags = INSN_INIT_TODO_SSID;
1040 : else
1041 821 : flags = INSN_INIT_TODO_LUID | INSN_INIT_TODO_SSID;
1042 :
1043 1976 : set_insn_init (INSN_EXPR (insn), nop_vinsn, INSN_SEQNO (insn));
1044 1976 : sel_init_new_insn (nop, flags);
1045 :
1046 1976 : return nop;
1047 : }
1048 :
1049 : /* Remove NOP from the instruction stream and return it to the pool. */
1050 : void
1051 1976 : return_nop_to_pool (insn_t nop, bool full_tidying)
1052 : {
1053 3952 : gcc_assert (INSN_IN_STREAM_P (nop));
1054 1976 : sel_remove_insn (nop, false, full_tidying);
1055 :
1056 : /* We'll recycle this nop. */
1057 1976 : nop->set_undeleted ();
1058 :
1059 1976 : if (nop_pool.n == nop_pool.s)
1060 818 : nop_pool.v = XRESIZEVEC (rtx_insn *, nop_pool.v,
1061 : (nop_pool.s = 2 * nop_pool.s + 1));
1062 1976 : nop_pool.v[nop_pool.n++] = nop;
1063 1976 : }
1064 :
1065 : /* Free the nop pool. */
1066 : void
1067 733 : free_nop_pool (void)
1068 : {
1069 733 : nop_pool.n = 0;
1070 733 : nop_pool.s = 0;
1071 733 : free (nop_pool.v);
1072 733 : nop_pool.v = NULL;
1073 733 : }
1074 :
1075 :
1076 : /* Skip unspec to support ia64 speculation. Called from rtx_equal_p.
1077 : The callback is given two rtxes XX and YY and writes the new rtxes
1078 : to NX and NY in case some needs to be skipped. */
1079 : static bool
1080 0 : skip_unspecs_callback (const_rtx *xx, const_rtx *yy, rtx *nx, rtx* ny)
1081 : {
1082 0 : const_rtx x = *xx;
1083 0 : const_rtx y = *yy;
1084 :
1085 0 : if (GET_CODE (x) == UNSPEC
1086 0 : && (targetm.sched.skip_rtx_p == NULL
1087 0 : || targetm.sched.skip_rtx_p (x)))
1088 : {
1089 0 : *nx = XVECEXP (x, 0, 0);
1090 0 : *ny = const_cast<rtx> (y);
1091 0 : return true;
1092 : }
1093 :
1094 0 : if (GET_CODE (y) == UNSPEC
1095 0 : && (targetm.sched.skip_rtx_p == NULL
1096 0 : || targetm.sched.skip_rtx_p (y)))
1097 : {
1098 0 : *nx = const_cast<rtx> (x);
1099 0 : *ny = XVECEXP (y, 0, 0);
1100 0 : return true;
1101 : }
1102 :
1103 : return false;
1104 : }
1105 :
1106 : /* Callback, called from hash_rtx. Helps to hash UNSPEC rtx X in a correct way
1107 : to support ia64 speculation. When changes are needed, new rtx X and new mode
1108 : NMODE are written, and the callback returns true. */
1109 : static bool
1110 0 : hash_with_unspec_callback (const_rtx x, machine_mode mode ATTRIBUTE_UNUSED,
1111 : rtx *nx, machine_mode* nmode)
1112 : {
1113 0 : if (GET_CODE (x) == UNSPEC
1114 0 : && targetm.sched.skip_rtx_p
1115 0 : && targetm.sched.skip_rtx_p (x))
1116 : {
1117 0 : *nx = XVECEXP (x, 0 ,0);
1118 0 : *nmode = VOIDmode;
1119 0 : return true;
1120 : }
1121 :
1122 : return false;
1123 : }
1124 :
1125 : /* Returns LHS and RHS are ok to be scheduled separately. */
1126 : static bool
1127 2739 : lhs_and_rhs_separable_p (rtx lhs, rtx rhs)
1128 : {
1129 2739 : if (lhs == NULL || rhs == NULL)
1130 : return false;
1131 :
1132 : /* Do not schedule constants as rhs: no point to use reg, if const
1133 : can be used. Moreover, scheduling const as rhs may lead to mode
1134 : mismatch cause consts don't have modes but they could be merged
1135 : from branches where the same const used in different modes. */
1136 2739 : if (CONSTANT_P (rhs))
1137 : return false;
1138 :
1139 : /* ??? Do not rename predicate registers to avoid ICEs in bundling. */
1140 2363 : if (COMPARISON_P (rhs))
1141 : return false;
1142 :
1143 : /* Do not allow single REG to be an rhs. */
1144 2338 : if (REG_P (rhs))
1145 : return false;
1146 :
1147 : /* See comment at find_used_regs_1 (*1) for explanation of this
1148 : restriction. */
1149 : /* FIXME: remove this later. */
1150 1406 : if (MEM_P (lhs))
1151 : return false;
1152 :
1153 : /* This will filter all tricky things like ZERO_EXTRACT etc.
1154 : For now we don't handle it. */
1155 1374 : if (!REG_P (lhs) && !MEM_P (lhs))
1156 1 : return false;
1157 :
1158 : return true;
1159 : }
1160 :
1161 : /* Initialize vinsn VI for INSN. Only for use from vinsn_create (). When
1162 : FORCE_UNIQUE_P is true, the resulting vinsn will not be clonable. This is
1163 : used e.g. for insns from recovery blocks. */
1164 : static void
1165 5787 : vinsn_init (vinsn_t vi, insn_t insn, bool force_unique_p)
1166 : {
1167 5787 : hash_rtx_callback_function hrcf;
1168 5787 : int insn_class;
1169 :
1170 5787 : VINSN_INSN_RTX (vi) = insn;
1171 5787 : VINSN_COUNT (vi) = 0;
1172 5787 : vi->cost = -1;
1173 :
1174 5787 : if (INSN_NOP_P (insn))
1175 : return;
1176 :
1177 5054 : if (DF_INSN_UID_SAFE_GET (INSN_UID (insn)) != NULL)
1178 4393 : init_id_from_df (VINSN_ID (vi), insn, force_unique_p);
1179 : else
1180 661 : deps_init_id (VINSN_ID (vi), insn, force_unique_p);
1181 :
1182 : /* Hash vinsn depending on whether it is separable or not. */
1183 5054 : hrcf = targetm.sched.skip_rtx_p ? hash_with_unspec_callback : NULL;
1184 5054 : if (VINSN_SEPARABLE_P (vi))
1185 : {
1186 1370 : rtx rhs = VINSN_RHS (vi);
1187 :
1188 1370 : VINSN_HASH (vi) = hash_rtx (rhs, GET_MODE (rhs),
1189 : NULL, NULL, false, hrcf);
1190 1370 : VINSN_HASH_RTX (vi) = hash_rtx (VINSN_PATTERN (vi),
1191 : VOIDmode, NULL, NULL,
1192 : false, hrcf);
1193 : }
1194 : else
1195 : {
1196 3684 : VINSN_HASH (vi) = hash_rtx (VINSN_PATTERN (vi), VOIDmode,
1197 : NULL, NULL, false, hrcf);
1198 3684 : VINSN_HASH_RTX (vi) = VINSN_HASH (vi);
1199 : }
1200 :
1201 5054 : insn_class = haifa_classify_insn (insn);
1202 5054 : if (insn_class >= 2
1203 5054 : && (!targetm.sched.get_insn_spec_ds
1204 0 : || ((targetm.sched.get_insn_spec_ds (insn) & BEGIN_CONTROL)
1205 : == 0)))
1206 711 : VINSN_MAY_TRAP_P (vi) = true;
1207 : else
1208 4343 : VINSN_MAY_TRAP_P (vi) = false;
1209 : }
1210 :
1211 : /* Indicate that VI has become the part of an rtx object. */
1212 : void
1213 195432 : vinsn_attach (vinsn_t vi)
1214 : {
1215 : /* Assert that VI is not pending for deletion. */
1216 195432 : gcc_assert (VINSN_INSN_RTX (vi));
1217 :
1218 195432 : VINSN_COUNT (vi)++;
1219 195432 : }
1220 :
1221 : /* Create and init VI from the INSN. Use UNIQUE_P for determining the correct
1222 : VINSN_TYPE (VI). */
1223 : static vinsn_t
1224 5787 : vinsn_create (insn_t insn, bool force_unique_p)
1225 : {
1226 5787 : vinsn_t vi = XCNEW (struct vinsn_def);
1227 :
1228 5787 : vinsn_init (vi, insn, force_unique_p);
1229 5787 : return vi;
1230 : }
1231 :
1232 : /* Return a copy of VI. When REATTACH_P is true, detach VI and attach
1233 : the copy. */
1234 : vinsn_t
1235 2 : vinsn_copy (vinsn_t vi, bool reattach_p)
1236 : {
1237 2 : rtx_insn *copy;
1238 2 : bool unique = VINSN_UNIQUE_P (vi);
1239 2 : vinsn_t new_vi;
1240 :
1241 2 : copy = create_copy_of_insn_rtx (VINSN_INSN_RTX (vi));
1242 2 : new_vi = create_vinsn_from_insn_rtx (copy, unique);
1243 2 : if (reattach_p)
1244 : {
1245 2 : vinsn_detach (vi);
1246 2 : vinsn_attach (new_vi);
1247 : }
1248 :
1249 2 : return new_vi;
1250 : }
1251 :
1252 : /* Delete the VI vinsn and free its data. */
1253 : static void
1254 5787 : vinsn_delete (vinsn_t vi)
1255 : {
1256 5787 : gcc_assert (VINSN_COUNT (vi) == 0);
1257 :
1258 5787 : if (!INSN_NOP_P (VINSN_INSN_RTX (vi)))
1259 : {
1260 5054 : return_regset_to_pool (VINSN_REG_SETS (vi));
1261 5054 : return_regset_to_pool (VINSN_REG_USES (vi));
1262 5054 : return_regset_to_pool (VINSN_REG_CLOBBERS (vi));
1263 : }
1264 :
1265 5787 : free (vi);
1266 5787 : }
1267 :
1268 : /* Indicate that VI is no longer a part of some rtx object.
1269 : Remove VI if it is no longer needed. */
1270 : void
1271 195432 : vinsn_detach (vinsn_t vi)
1272 : {
1273 195432 : gcc_assert (VINSN_COUNT (vi) > 0);
1274 :
1275 195432 : if (--VINSN_COUNT (vi) == 0)
1276 5787 : vinsn_delete (vi);
1277 195432 : }
1278 :
1279 : /* Returns TRUE if VI is a branch. */
1280 : bool
1281 17061 : vinsn_cond_branch_p (vinsn_t vi)
1282 : {
1283 17061 : insn_t insn;
1284 :
1285 17061 : if (!VINSN_UNIQUE_P (vi))
1286 : return false;
1287 :
1288 2410 : insn = VINSN_INSN_RTX (vi);
1289 2410 : if (BB_END (BLOCK_FOR_INSN (insn)) != insn)
1290 : return false;
1291 :
1292 1241 : return control_flow_insn_p (insn);
1293 : }
1294 :
1295 : /* Return latency of INSN. */
1296 : static int
1297 202 : sel_insn_rtx_cost (rtx_insn *insn)
1298 : {
1299 202 : int cost;
1300 :
1301 : /* A USE insn, or something else we don't need to
1302 : understand. We can't pass these directly to
1303 : result_ready_cost or insn_default_latency because it will
1304 : trigger a fatal error for unrecognizable insns. */
1305 202 : if (recog_memoized (insn) < 0)
1306 : cost = 0;
1307 : else
1308 : {
1309 202 : cost = insn_default_latency (insn);
1310 :
1311 202 : if (cost < 0)
1312 0 : cost = 0;
1313 : }
1314 :
1315 202 : return cost;
1316 : }
1317 :
1318 : /* Return the cost of the VI.
1319 : !!! FIXME: Unify with haifa-sched.cc: insn_sched_cost (). */
1320 : int
1321 991 : sel_vinsn_cost (vinsn_t vi)
1322 : {
1323 991 : int cost = vi->cost;
1324 :
1325 991 : if (cost < 0)
1326 : {
1327 202 : cost = sel_insn_rtx_cost (VINSN_INSN_RTX (vi));
1328 202 : vi->cost = cost;
1329 : }
1330 :
1331 991 : return cost;
1332 : }
1333 :
1334 :
1335 : /* Functions for insn emitting. */
1336 :
1337 : /* Emit new insn after AFTER based on PATTERN and initialize its data from
1338 : EXPR and SEQNO. */
1339 : insn_t
1340 29 : sel_gen_insn_from_rtx_after (rtx pattern, expr_t expr, int seqno, insn_t after)
1341 : {
1342 29 : insn_t new_insn;
1343 :
1344 29 : gcc_assert (EXPR_TARGET_AVAILABLE (expr) == true);
1345 :
1346 29 : new_insn = emit_insn_after (pattern, after);
1347 29 : set_insn_init (expr, NULL, seqno);
1348 29 : sel_init_new_insn (new_insn, INSN_INIT_TODO_LUID | INSN_INIT_TODO_SSID);
1349 :
1350 29 : return new_insn;
1351 : }
1352 :
1353 : /* Force newly generated vinsns to be unique. */
1354 : static bool init_insn_force_unique_p = false;
1355 :
1356 : /* Emit new speculation recovery insn after AFTER based on PATTERN and
1357 : initialize its data from EXPR and SEQNO. */
1358 : insn_t
1359 0 : sel_gen_recovery_insn_from_rtx_after (rtx pattern, expr_t expr, int seqno,
1360 : insn_t after)
1361 : {
1362 0 : insn_t insn;
1363 :
1364 0 : gcc_assert (!init_insn_force_unique_p);
1365 :
1366 0 : init_insn_force_unique_p = true;
1367 0 : insn = sel_gen_insn_from_rtx_after (pattern, expr, seqno, after);
1368 0 : CANT_MOVE (insn) = 1;
1369 0 : init_insn_force_unique_p = false;
1370 :
1371 0 : return insn;
1372 : }
1373 :
1374 : /* Emit new insn after AFTER based on EXPR and SEQNO. If VINSN is not NULL,
1375 : take it as a new vinsn instead of EXPR's vinsn.
1376 : We simplify insns later, after scheduling region in
1377 : simplify_changed_insns. */
1378 : insn_t
1379 412 : sel_gen_insn_from_expr_after (expr_t expr, vinsn_t vinsn, int seqno,
1380 : insn_t after)
1381 : {
1382 412 : expr_t emit_expr;
1383 412 : insn_t insn;
1384 412 : int flags;
1385 :
1386 412 : emit_expr = set_insn_init (expr, vinsn ? vinsn : EXPR_VINSN (expr),
1387 : seqno);
1388 412 : insn = EXPR_INSN_RTX (emit_expr);
1389 :
1390 : /* The insn may come from the transformation cache, which may hold already
1391 : deleted insns, so mark it as not deleted. */
1392 412 : insn->set_undeleted ();
1393 :
1394 412 : add_insn_after (insn, after, BLOCK_FOR_INSN (insn));
1395 :
1396 412 : flags = INSN_INIT_TODO_SSID;
1397 412 : if (INSN_LUID (insn) == 0)
1398 412 : flags |= INSN_INIT_TODO_LUID;
1399 412 : sel_init_new_insn (insn, flags);
1400 :
1401 412 : return insn;
1402 : }
1403 :
1404 : /* Move insn from EXPR after AFTER. */
1405 : insn_t
1406 4713 : sel_move_insn (expr_t expr, int seqno, insn_t after)
1407 : {
1408 4713 : insn_t insn = EXPR_INSN_RTX (expr);
1409 4713 : basic_block bb = BLOCK_FOR_INSN (after);
1410 4713 : insn_t next = NEXT_INSN (after);
1411 :
1412 : /* Assert that in move_op we disconnected this insn properly. */
1413 4713 : gcc_assert (EXPR_VINSN (INSN_EXPR (insn)) != NULL);
1414 4713 : SET_PREV_INSN (insn) = after;
1415 4713 : SET_NEXT_INSN (insn) = next;
1416 :
1417 4713 : SET_NEXT_INSN (after) = insn;
1418 4713 : SET_PREV_INSN (next) = insn;
1419 :
1420 : /* Update links from insn to bb and vice versa. */
1421 4713 : df_insn_change_bb (insn, bb);
1422 4713 : if (BB_END (bb) == after)
1423 741 : BB_END (bb) = insn;
1424 :
1425 4713 : prepare_insn_expr (insn, seqno);
1426 4713 : return insn;
1427 : }
1428 :
1429 :
1430 : /* Functions to work with right-hand sides. */
1431 :
1432 : /* Search for a hash value determined by UID/NEW_VINSN in a sorted vector
1433 : VECT and return true when found. Use NEW_VINSN for comparison only when
1434 : COMPARE_VINSNS is true. Write to INDP the index on which
1435 : the search has stopped, such that inserting the new element at INDP will
1436 : retain VECT's sort order. */
1437 : static bool
1438 93420 : find_in_history_vect_1 (vec<expr_history_def> vect,
1439 : unsigned uid, vinsn_t new_vinsn,
1440 : bool compare_vinsns, int *indp)
1441 : {
1442 93420 : expr_history_def *arr;
1443 93420 : int i, j, len = vect.length ();
1444 :
1445 2289 : if (len == 0)
1446 : {
1447 91131 : *indp = 0;
1448 91131 : return false;
1449 : }
1450 :
1451 : arr = vect.address ();
1452 3896 : i = 0, j = len - 1;
1453 :
1454 3896 : while (i <= j)
1455 : {
1456 2796 : unsigned auid = arr[i].uid;
1457 2796 : vinsn_t avinsn = arr[i].new_expr_vinsn;
1458 :
1459 2796 : if (auid == uid
1460 : /* When undoing transformation on a bookkeeping copy, the new vinsn
1461 : may not be exactly equal to the one that is saved in the vector.
1462 : This is because the insn whose copy we're checking was possibly
1463 : substituted itself. */
1464 2796 : && (! compare_vinsns
1465 238 : || vinsn_equal_p (avinsn, new_vinsn)))
1466 : {
1467 400 : *indp = i;
1468 400 : return true;
1469 : }
1470 2396 : else if (auid > uid)
1471 : break;
1472 1607 : i++;
1473 : }
1474 :
1475 1889 : *indp = i;
1476 1889 : return false;
1477 : }
1478 :
1479 : /* Search for a uid of INSN and NEW_VINSN in a sorted vector VECT. Return
1480 : the position found or -1, if no such value is in vector.
1481 : Search also for UIDs of insn's originators, if ORIGINATORS_P is true. */
1482 : int
1483 48805 : find_in_history_vect (vec<expr_history_def> vect, rtx insn,
1484 : vinsn_t new_vinsn, bool originators_p)
1485 : {
1486 48805 : int ind;
1487 :
1488 48805 : if (find_in_history_vect_1 (vect, INSN_UID (insn), new_vinsn,
1489 : false, &ind))
1490 162 : return ind;
1491 :
1492 48643 : if (INSN_ORIGINATORS (insn) && originators_p)
1493 : {
1494 1567 : unsigned uid;
1495 1567 : bitmap_iterator bi;
1496 :
1497 45528 : EXECUTE_IF_SET_IN_BITMAP (INSN_ORIGINATORS (insn), 0, uid, bi)
1498 43961 : if (find_in_history_vect_1 (vect, uid, new_vinsn, false, &ind))
1499 0 : return ind;
1500 : }
1501 :
1502 : return -1;
1503 : }
1504 :
1505 : /* Insert new element in a sorted history vector pointed to by PVECT,
1506 : if it is not there already. The element is searched using
1507 : UID/NEW_EXPR_VINSN pair. TYPE, OLD_EXPR_VINSN and SPEC_DS save
1508 : the history of a transformation. */
1509 : void
1510 654 : insert_in_history_vect (vec<expr_history_def> *pvect,
1511 : unsigned uid, enum local_trans_type type,
1512 : vinsn_t old_expr_vinsn, vinsn_t new_expr_vinsn,
1513 : ds_t spec_ds)
1514 : {
1515 654 : vec<expr_history_def> vect = *pvect;
1516 654 : expr_history_def temp;
1517 654 : bool res;
1518 654 : int ind;
1519 :
1520 654 : res = find_in_history_vect_1 (vect, uid, new_expr_vinsn, true, &ind);
1521 :
1522 654 : if (res)
1523 : {
1524 238 : expr_history_def *phist = &vect[ind];
1525 :
1526 : /* It is possible that speculation types of expressions that were
1527 : propagated through different paths will be different here. In this
1528 : case, merge the status to get the correct check later. */
1529 238 : if (phist->spec_ds != spec_ds)
1530 0 : phist->spec_ds = ds_max_merge (phist->spec_ds, spec_ds);
1531 238 : return;
1532 : }
1533 :
1534 416 : temp.uid = uid;
1535 416 : temp.old_expr_vinsn = old_expr_vinsn;
1536 416 : temp.new_expr_vinsn = new_expr_vinsn;
1537 416 : temp.spec_ds = spec_ds;
1538 416 : temp.type = type;
1539 :
1540 416 : vinsn_attach (old_expr_vinsn);
1541 416 : vinsn_attach (new_expr_vinsn);
1542 416 : vect.safe_insert (ind, temp);
1543 416 : *pvect = vect;
1544 : }
1545 :
1546 : /* Free history vector PVECT. */
1547 : static void
1548 174418 : free_history_vect (vec<expr_history_def> &pvect)
1549 : {
1550 174418 : unsigned i;
1551 174418 : expr_history_def *phist;
1552 :
1553 174418 : if (! pvect.exists ())
1554 174418 : return;
1555 :
1556 4642 : for (i = 0; pvect.iterate (i, &phist); i++)
1557 : {
1558 2524 : vinsn_detach (phist->old_expr_vinsn);
1559 2524 : vinsn_detach (phist->new_expr_vinsn);
1560 : }
1561 :
1562 2118 : pvect.release ();
1563 : }
1564 :
1565 : /* Merge vector FROM to PVECT. */
1566 : static void
1567 9813 : merge_history_vect (vec<expr_history_def> *pvect,
1568 : vec<expr_history_def> from)
1569 : {
1570 9813 : expr_history_def *phist;
1571 9813 : int i;
1572 :
1573 : /* We keep this vector sorted. */
1574 10057 : for (i = 0; from.iterate (i, &phist); i++)
1575 244 : insert_in_history_vect (pvect, phist->uid, phist->type,
1576 : phist->old_expr_vinsn, phist->new_expr_vinsn,
1577 : phist->spec_ds);
1578 9813 : }
1579 :
1580 : /* Compare two vinsns as rhses if possible and as vinsns otherwise. */
1581 : bool
1582 297887 : vinsn_equal_p (vinsn_t x, vinsn_t y)
1583 : {
1584 297887 : rtx_equal_p_callback_function repcf;
1585 :
1586 297887 : if (x == y)
1587 : return true;
1588 :
1589 266811 : if (VINSN_TYPE (x) != VINSN_TYPE (y))
1590 : return false;
1591 :
1592 124472 : if (VINSN_HASH (x) != VINSN_HASH (y))
1593 : return false;
1594 :
1595 10304 : repcf = targetm.sched.skip_rtx_p ? skip_unspecs_callback : NULL;
1596 10304 : if (VINSN_SEPARABLE_P (x))
1597 : {
1598 : /* Compare RHSes of VINSNs. */
1599 4909 : gcc_assert (VINSN_RHS (x));
1600 4909 : gcc_assert (VINSN_RHS (y));
1601 :
1602 4909 : return rtx_equal_p (VINSN_RHS (x), VINSN_RHS (y), repcf);
1603 : }
1604 :
1605 5395 : return rtx_equal_p (VINSN_PATTERN (x), VINSN_PATTERN (y), repcf);
1606 : }
1607 :
1608 :
1609 : /* Functions for working with expressions. */
1610 :
1611 : /* Initialize EXPR. */
1612 : static void
1613 167288 : init_expr (expr_t expr, vinsn_t vi, int spec, int use, int priority,
1614 : int sched_times, int orig_bb_index, ds_t spec_done_ds,
1615 : ds_t spec_to_check_ds, int orig_sched_cycle,
1616 : vec<expr_history_def> history,
1617 : signed char target_available,
1618 : bool was_substituted, bool was_renamed, bool needs_spec_check_p,
1619 : bool cant_move)
1620 : {
1621 0 : vinsn_attach (vi);
1622 :
1623 167288 : EXPR_VINSN (expr) = vi;
1624 167288 : EXPR_SPEC (expr) = spec;
1625 167288 : EXPR_USEFULNESS (expr) = use;
1626 167288 : EXPR_PRIORITY (expr) = priority;
1627 167288 : EXPR_PRIORITY_ADJ (expr) = 0;
1628 167288 : EXPR_SCHED_TIMES (expr) = sched_times;
1629 167288 : EXPR_ORIG_BB_INDEX (expr) = orig_bb_index;
1630 167288 : EXPR_ORIG_SCHED_CYCLE (expr) = orig_sched_cycle;
1631 167288 : EXPR_SPEC_DONE_DS (expr) = spec_done_ds;
1632 167288 : EXPR_SPEC_TO_CHECK_DS (expr) = spec_to_check_ds;
1633 :
1634 137900 : if (history.exists ())
1635 1723 : EXPR_HISTORY_OF_CHANGES (expr) = history;
1636 : else
1637 140541 : EXPR_HISTORY_OF_CHANGES (expr).create (0);
1638 :
1639 167288 : EXPR_TARGET_AVAILABLE (expr) = target_available;
1640 167288 : EXPR_WAS_SUBSTITUTED (expr) = was_substituted;
1641 167288 : EXPR_WAS_RENAMED (expr) = was_renamed;
1642 167288 : EXPR_NEEDS_SPEC_CHECK_P (expr) = needs_spec_check_p;
1643 167288 : EXPR_CANT_MOVE (expr) = cant_move;
1644 0 : }
1645 :
1646 : /* Make a copy of the expr FROM into the expr TO. */
1647 : void
1648 137900 : copy_expr (expr_t to, expr_t from)
1649 : {
1650 137900 : vec<expr_history_def> temp = vNULL;
1651 :
1652 137900 : if (EXPR_HISTORY_OF_CHANGES (from).exists ())
1653 : {
1654 1723 : unsigned i;
1655 1723 : expr_history_def *phist;
1656 :
1657 1723 : temp = EXPR_HISTORY_OF_CHANGES (from).copy ();
1658 3831 : for (i = 0;
1659 3831 : temp.iterate (i, &phist);
1660 : i++)
1661 : {
1662 2108 : vinsn_attach (phist->old_expr_vinsn);
1663 2108 : vinsn_attach (phist->new_expr_vinsn);
1664 : }
1665 : }
1666 :
1667 275800 : init_expr (to, EXPR_VINSN (from), EXPR_SPEC (from),
1668 : EXPR_USEFULNESS (from), EXPR_PRIORITY (from),
1669 : EXPR_SCHED_TIMES (from), EXPR_ORIG_BB_INDEX (from),
1670 : EXPR_SPEC_DONE_DS (from), EXPR_SPEC_TO_CHECK_DS (from),
1671 : EXPR_ORIG_SCHED_CYCLE (from), temp,
1672 137900 : EXPR_TARGET_AVAILABLE (from), EXPR_WAS_SUBSTITUTED (from),
1673 137900 : EXPR_WAS_RENAMED (from), EXPR_NEEDS_SPEC_CHECK_P (from),
1674 137900 : EXPR_CANT_MOVE (from));
1675 137900 : }
1676 :
1677 : /* Same, but the final expr will not ever be in av sets, so don't copy
1678 : "uninteresting" data such as bitmap cache. */
1679 : void
1680 25024 : copy_expr_onside (expr_t to, expr_t from)
1681 : {
1682 50048 : init_expr (to, EXPR_VINSN (from), EXPR_SPEC (from), EXPR_USEFULNESS (from),
1683 : EXPR_PRIORITY (from), EXPR_SCHED_TIMES (from), 0,
1684 : EXPR_SPEC_DONE_DS (from), EXPR_SPEC_TO_CHECK_DS (from), 0,
1685 25024 : vNULL,
1686 25024 : EXPR_TARGET_AVAILABLE (from), EXPR_WAS_SUBSTITUTED (from),
1687 25024 : EXPR_WAS_RENAMED (from), EXPR_NEEDS_SPEC_CHECK_P (from),
1688 25024 : EXPR_CANT_MOVE (from));
1689 25024 : }
1690 :
1691 : /* Prepare the expr of INSN for scheduling. Used when moving insn and when
1692 : initializing new insns. */
1693 : static void
1694 7130 : prepare_insn_expr (insn_t insn, int seqno)
1695 : {
1696 7130 : expr_t expr = INSN_EXPR (insn);
1697 7130 : ds_t ds;
1698 :
1699 7130 : INSN_SEQNO (insn) = seqno;
1700 7130 : EXPR_ORIG_BB_INDEX (expr) = BLOCK_NUM (insn);
1701 7130 : EXPR_SPEC (expr) = 0;
1702 7130 : EXPR_ORIG_SCHED_CYCLE (expr) = 0;
1703 7130 : EXPR_WAS_SUBSTITUTED (expr) = 0;
1704 7130 : EXPR_WAS_RENAMED (expr) = 0;
1705 7130 : EXPR_TARGET_AVAILABLE (expr) = 1;
1706 7130 : INSN_LIVE_VALID_P (insn) = false;
1707 :
1708 : /* ??? If this expression is speculative, make its dependence
1709 : as weak as possible. We can filter this expression later
1710 : in process_spec_exprs, because we do not distinguish
1711 : between the status we got during compute_av_set and the
1712 : existing status. To be fixed. */
1713 7130 : ds = EXPR_SPEC_DONE_DS (expr);
1714 7130 : if (ds)
1715 0 : EXPR_SPEC_DONE_DS (expr) = ds_get_max_dep_weak (ds);
1716 :
1717 7130 : free_history_vect (EXPR_HISTORY_OF_CHANGES (expr));
1718 7130 : }
1719 :
1720 : /* Update target_available bits when merging exprs TO and FROM. SPLIT_POINT
1721 : is non-null when expressions are merged from different successors at
1722 : a split point. */
1723 : static void
1724 2176 : update_target_availability (expr_t to, expr_t from, insn_t split_point)
1725 : {
1726 2176 : if (EXPR_TARGET_AVAILABLE (to) < 0
1727 1273 : || EXPR_TARGET_AVAILABLE (from) < 0)
1728 964 : EXPR_TARGET_AVAILABLE (to) = -1;
1729 : else
1730 : {
1731 : /* We try to detect the case when one of the expressions
1732 : can only be reached through another one. In this case,
1733 : we can do better. */
1734 1212 : if (split_point == NULL)
1735 : {
1736 66 : int toind, fromind;
1737 :
1738 66 : toind = EXPR_ORIG_BB_INDEX (to);
1739 66 : fromind = EXPR_ORIG_BB_INDEX (from);
1740 :
1741 66 : if (toind && toind == fromind)
1742 : /* Do nothing -- everything is done in
1743 : merge_with_other_exprs. */
1744 : ;
1745 : else
1746 66 : EXPR_TARGET_AVAILABLE (to) = -1;
1747 : }
1748 1146 : else if (EXPR_TARGET_AVAILABLE (from) == 0
1749 616 : && EXPR_LHS (from)
1750 616 : && REG_P (EXPR_LHS (from))
1751 1762 : && REGNO (EXPR_LHS (to)) != REGNO (EXPR_LHS (from)))
1752 0 : EXPR_TARGET_AVAILABLE (to) = -1;
1753 : else
1754 1146 : EXPR_TARGET_AVAILABLE (to) &= EXPR_TARGET_AVAILABLE (from);
1755 : }
1756 2176 : }
1757 :
1758 : /* Update speculation bits when merging exprs TO and FROM. SPLIT_POINT
1759 : is non-null when expressions are merged from different successors at
1760 : a split point. */
1761 : static void
1762 2176 : update_speculative_bits (expr_t to, expr_t from, insn_t split_point)
1763 : {
1764 2176 : ds_t old_to_ds, old_from_ds;
1765 :
1766 2176 : old_to_ds = EXPR_SPEC_DONE_DS (to);
1767 2176 : old_from_ds = EXPR_SPEC_DONE_DS (from);
1768 :
1769 2176 : EXPR_SPEC_DONE_DS (to) = ds_max_merge (old_to_ds, old_from_ds);
1770 2176 : EXPR_SPEC_TO_CHECK_DS (to) |= EXPR_SPEC_TO_CHECK_DS (from);
1771 2176 : EXPR_NEEDS_SPEC_CHECK_P (to) |= EXPR_NEEDS_SPEC_CHECK_P (from);
1772 :
1773 : /* When merging e.g. control & data speculative exprs, or a control
1774 : speculative with a control&data speculative one, we really have
1775 : to change vinsn too. Also, when speculative status is changed,
1776 : we also need to record this as a transformation in expr's history. */
1777 2176 : if ((old_to_ds & SPECULATIVE) || (old_from_ds & SPECULATIVE))
1778 : {
1779 0 : old_to_ds = ds_get_speculation_types (old_to_ds);
1780 0 : old_from_ds = ds_get_speculation_types (old_from_ds);
1781 :
1782 0 : if (old_to_ds != old_from_ds)
1783 : {
1784 0 : ds_t record_ds;
1785 :
1786 : /* When both expressions are speculative, we need to change
1787 : the vinsn first. */
1788 0 : if ((old_to_ds & SPECULATIVE) && (old_from_ds & SPECULATIVE))
1789 : {
1790 0 : int res;
1791 :
1792 0 : res = speculate_expr (to, EXPR_SPEC_DONE_DS (to));
1793 0 : gcc_assert (res >= 0);
1794 : }
1795 :
1796 0 : if (split_point != NULL)
1797 : {
1798 : /* Record the change with proper status. */
1799 0 : record_ds = EXPR_SPEC_DONE_DS (to) & SPECULATIVE;
1800 0 : record_ds &= ~(old_to_ds & SPECULATIVE);
1801 0 : record_ds &= ~(old_from_ds & SPECULATIVE);
1802 :
1803 0 : insert_in_history_vect (&EXPR_HISTORY_OF_CHANGES (to),
1804 0 : INSN_UID (split_point), TRANS_SPECULATION,
1805 : EXPR_VINSN (from), EXPR_VINSN (to),
1806 : record_ds);
1807 : }
1808 : }
1809 : }
1810 2176 : }
1811 :
1812 :
1813 : /* Merge bits of FROM expr to TO expr. When SPLIT_POINT is not NULL,
1814 : this is done along different paths. */
1815 : void
1816 2176 : merge_expr_data (expr_t to, expr_t from, insn_t split_point)
1817 : {
1818 : /* Choose the maximum of the specs of merged exprs. This is required
1819 : for correctness of bookkeeping. */
1820 2176 : if (EXPR_SPEC (to) < EXPR_SPEC (from))
1821 929 : EXPR_SPEC (to) = EXPR_SPEC (from);
1822 :
1823 2176 : if (split_point)
1824 1918 : EXPR_USEFULNESS (to) += EXPR_USEFULNESS (from);
1825 : else
1826 258 : EXPR_USEFULNESS (to) = MAX (EXPR_USEFULNESS (to),
1827 : EXPR_USEFULNESS (from));
1828 :
1829 2176 : if (EXPR_PRIORITY (to) < EXPR_PRIORITY (from))
1830 101 : EXPR_PRIORITY (to) = EXPR_PRIORITY (from);
1831 :
1832 : /* We merge sched-times half-way to the larger value to avoid the endless
1833 : pipelining of unneeded insns. The average seems to be good compromise
1834 : between pipelining opportunities and avoiding extra work. */
1835 2176 : if (EXPR_SCHED_TIMES (to) != EXPR_SCHED_TIMES (from))
1836 803 : EXPR_SCHED_TIMES (to) = ((EXPR_SCHED_TIMES (from) + EXPR_SCHED_TIMES (to)
1837 803 : + 1) / 2);
1838 :
1839 2176 : if (EXPR_ORIG_BB_INDEX (to) != EXPR_ORIG_BB_INDEX (from))
1840 1085 : EXPR_ORIG_BB_INDEX (to) = 0;
1841 :
1842 2176 : EXPR_ORIG_SCHED_CYCLE (to) = MIN (EXPR_ORIG_SCHED_CYCLE (to),
1843 : EXPR_ORIG_SCHED_CYCLE (from));
1844 :
1845 2176 : EXPR_WAS_SUBSTITUTED (to) |= EXPR_WAS_SUBSTITUTED (from);
1846 2176 : EXPR_WAS_RENAMED (to) |= EXPR_WAS_RENAMED (from);
1847 2176 : EXPR_CANT_MOVE (to) |= EXPR_CANT_MOVE (from);
1848 :
1849 2176 : merge_history_vect (&EXPR_HISTORY_OF_CHANGES (to),
1850 : EXPR_HISTORY_OF_CHANGES (from));
1851 2176 : update_target_availability (to, from, split_point);
1852 2176 : update_speculative_bits (to, from, split_point);
1853 2176 : }
1854 :
1855 : /* Merge bits of FROM expr to TO expr. Vinsns in the exprs should be equal
1856 : in terms of vinsn_equal_p. SPLIT_POINT is non-null when expressions
1857 : are merged from different successors at a split point. */
1858 : void
1859 1922 : merge_expr (expr_t to, expr_t from, insn_t split_point)
1860 : {
1861 1922 : vinsn_t to_vi = EXPR_VINSN (to);
1862 1922 : vinsn_t from_vi = EXPR_VINSN (from);
1863 :
1864 1922 : gcc_assert (vinsn_equal_p (to_vi, from_vi));
1865 :
1866 : /* Make sure that speculative pattern is propagated into exprs that
1867 : have non-speculative one. This will provide us with consistent
1868 : speculative bits and speculative patterns inside expr. */
1869 1922 : if (EXPR_SPEC_DONE_DS (to) == 0
1870 1922 : && (EXPR_SPEC_DONE_DS (from) != 0
1871 : /* Do likewise for volatile insns, so that we always retain
1872 : the may_trap_p bit on the resulting expression. However,
1873 : avoid propagating the trapping bit into the instructions
1874 : already speculated. This would result in replacing the
1875 : speculative pattern with the non-speculative one and breaking
1876 : the speculation support. */
1877 1922 : || (!VINSN_MAY_TRAP_P (EXPR_VINSN (to))
1878 1922 : && VINSN_MAY_TRAP_P (EXPR_VINSN (from)))))
1879 0 : change_vinsn_in_expr (to, EXPR_VINSN (from));
1880 :
1881 1922 : merge_expr_data (to, from, split_point);
1882 1922 : gcc_assert (EXPR_USEFULNESS (to) <= REG_BR_PROB_BASE);
1883 1922 : }
1884 :
1885 : /* Clear the information of this EXPR. */
1886 : void
1887 167288 : clear_expr (expr_t expr)
1888 : {
1889 :
1890 167288 : vinsn_detach (EXPR_VINSN (expr));
1891 167288 : EXPR_VINSN (expr) = NULL;
1892 :
1893 167288 : free_history_vect (EXPR_HISTORY_OF_CHANGES (expr));
1894 167288 : }
1895 :
1896 : /* For a given LV_SET, mark EXPR having unavailable target register. */
1897 : static void
1898 10402 : set_unavailable_target_for_expr (expr_t expr, regset lv_set)
1899 : {
1900 10402 : if (EXPR_SEPARABLE_P (expr))
1901 : {
1902 5743 : if (REG_P (EXPR_LHS (expr))
1903 5743 : && register_unavailable_p (lv_set, EXPR_LHS (expr)))
1904 : {
1905 : /* If it's an insn like r1 = use (r1, ...), and it exists in
1906 : different forms in each of the av_sets being merged, we can't say
1907 : whether original destination register is available or not.
1908 : However, this still works if destination register is not used
1909 : in the original expression: if the branch at which LV_SET we're
1910 : looking here is not actually 'other branch' in sense that same
1911 : expression is available through it (but it can't be determined
1912 : at computation stage because of transformations on one of the
1913 : branches), it still won't affect the availability.
1914 : Liveness of a register somewhere on a code motion path means
1915 : it's either read somewhere on a codemotion path, live on
1916 : 'other' branch, live at the point immediately following
1917 : the original operation, or is read by the original operation.
1918 : The latter case is filtered out in the condition below.
1919 : It still doesn't cover the case when register is defined and used
1920 : somewhere within the code motion path, and in this case we could
1921 : miss a unifying code motion along both branches using a renamed
1922 : register, but it won't affect a code correctness since upon
1923 : an actual code motion a bookkeeping code would be generated. */
1924 1420 : if (register_unavailable_p (VINSN_REG_USES (EXPR_VINSN (expr)),
1925 1420 : EXPR_LHS (expr)))
1926 185 : EXPR_TARGET_AVAILABLE (expr) = -1;
1927 : else
1928 1235 : EXPR_TARGET_AVAILABLE (expr) = false;
1929 : }
1930 : }
1931 : else
1932 : {
1933 4659 : unsigned regno;
1934 4659 : reg_set_iterator rsi;
1935 :
1936 6664 : EXECUTE_IF_SET_IN_REG_SET (VINSN_REG_SETS (EXPR_VINSN (expr)),
1937 : 0, regno, rsi)
1938 3960 : if (bitmap_bit_p (lv_set, regno))
1939 : {
1940 1955 : EXPR_TARGET_AVAILABLE (expr) = false;
1941 1955 : break;
1942 : }
1943 :
1944 6357 : EXECUTE_IF_SET_IN_REG_SET (VINSN_REG_CLOBBERS (EXPR_VINSN (expr)),
1945 : 0, regno, rsi)
1946 1715 : if (bitmap_bit_p (lv_set, regno))
1947 : {
1948 17 : EXPR_TARGET_AVAILABLE (expr) = false;
1949 17 : break;
1950 : }
1951 : }
1952 10402 : }
1953 :
1954 : /* Try to make EXPR speculative. Return 1 when EXPR's pattern
1955 : or dependence status have changed, 2 when also the target register
1956 : became unavailable, 0 if nothing had to be changed. */
1957 : int
1958 0 : speculate_expr (expr_t expr, ds_t ds)
1959 : {
1960 0 : int res;
1961 0 : rtx_insn *orig_insn_rtx;
1962 0 : rtx spec_pat;
1963 0 : ds_t target_ds, current_ds;
1964 :
1965 : /* Obtain the status we need to put on EXPR. */
1966 0 : target_ds = (ds & SPECULATIVE);
1967 0 : current_ds = EXPR_SPEC_DONE_DS (expr);
1968 0 : ds = ds_full_merge (current_ds, target_ds, NULL_RTX, NULL_RTX);
1969 :
1970 0 : orig_insn_rtx = EXPR_INSN_RTX (expr);
1971 :
1972 0 : res = sched_speculate_insn (orig_insn_rtx, ds, &spec_pat);
1973 :
1974 0 : switch (res)
1975 : {
1976 0 : case 0:
1977 0 : EXPR_SPEC_DONE_DS (expr) = ds;
1978 0 : return current_ds != ds ? 1 : 0;
1979 :
1980 0 : case 1:
1981 0 : {
1982 0 : rtx_insn *spec_insn_rtx =
1983 0 : create_insn_rtx_from_pattern (spec_pat, NULL_RTX);
1984 0 : vinsn_t spec_vinsn = create_vinsn_from_insn_rtx (spec_insn_rtx, false);
1985 :
1986 0 : change_vinsn_in_expr (expr, spec_vinsn);
1987 0 : EXPR_SPEC_DONE_DS (expr) = ds;
1988 0 : EXPR_NEEDS_SPEC_CHECK_P (expr) = true;
1989 :
1990 : /* Do not allow clobbering the address register of speculative
1991 : insns. */
1992 0 : if (register_unavailable_p (VINSN_REG_USES (EXPR_VINSN (expr)),
1993 : expr_dest_reg (expr)))
1994 : {
1995 0 : EXPR_TARGET_AVAILABLE (expr) = false;
1996 0 : return 2;
1997 : }
1998 :
1999 : return 1;
2000 : }
2001 :
2002 : case -1:
2003 : return -1;
2004 :
2005 0 : default:
2006 0 : gcc_unreachable ();
2007 : return -1;
2008 : }
2009 : }
2010 :
2011 : /* Return a destination register, if any, of EXPR. */
2012 : rtx
2013 8322 : expr_dest_reg (expr_t expr)
2014 : {
2015 8322 : rtx dest = VINSN_LHS (EXPR_VINSN (expr));
2016 :
2017 8322 : if (dest != NULL_RTX && REG_P (dest))
2018 8322 : return dest;
2019 :
2020 : return NULL_RTX;
2021 : }
2022 :
2023 : /* Returns the REGNO of the R's destination. */
2024 : unsigned
2025 7060 : expr_dest_regno (expr_t expr)
2026 : {
2027 7060 : rtx dest = expr_dest_reg (expr);
2028 :
2029 7060 : gcc_assert (dest != NULL_RTX);
2030 7060 : return REGNO (dest);
2031 : }
2032 :
2033 : /* For a given LV_SET, mark all expressions in JOIN_SET, but not present in
2034 : AV_SET having unavailable target register. */
2035 : void
2036 6882 : mark_unavailable_targets (av_set_t join_set, av_set_t av_set, regset lv_set)
2037 : {
2038 6882 : expr_t expr;
2039 6882 : av_set_iterator avi;
2040 :
2041 13959 : FOR_EACH_EXPR (expr, avi, join_set)
2042 7077 : if (av_set_lookup (av_set, EXPR_VINSN (expr)) == NULL)
2043 7077 : set_unavailable_target_for_expr (expr, lv_set);
2044 6882 : }
2045 :
2046 :
2047 : /* Returns true if REG (at least partially) is present in REGS. */
2048 : bool
2049 7163 : register_unavailable_p (regset regs, rtx reg)
2050 : {
2051 7163 : unsigned regno, end_regno;
2052 :
2053 7163 : regno = REGNO (reg);
2054 7163 : if (bitmap_bit_p (regs, regno))
2055 : return true;
2056 :
2057 5558 : end_regno = END_REGNO (reg);
2058 :
2059 5558 : while (++regno < end_regno)
2060 0 : if (bitmap_bit_p (regs, regno))
2061 : return true;
2062 :
2063 : return false;
2064 : }
2065 :
2066 : /* Av set functions. */
2067 :
2068 : /* Add a new element to av set SETP.
2069 : Return the element added. */
2070 : static av_set_t
2071 136601 : av_set_add_element (av_set_t *setp)
2072 : {
2073 : /* Insert at the beginning of the list. */
2074 0 : _list_add (setp);
2075 136601 : return *setp;
2076 : }
2077 :
2078 : /* Add EXPR to SETP. */
2079 : void
2080 134683 : av_set_add (av_set_t *setp, expr_t expr)
2081 : {
2082 134683 : av_set_t elem;
2083 :
2084 134683 : gcc_assert (!INSN_NOP_P (EXPR_INSN_RTX (expr)));
2085 134683 : elem = av_set_add_element (setp);
2086 134683 : copy_expr (_AV_SET_EXPR (elem), expr);
2087 134683 : }
2088 :
2089 : /* Same, but do not copy EXPR. */
2090 : static void
2091 1918 : av_set_add_nocopy (av_set_t *setp, expr_t expr)
2092 : {
2093 1918 : av_set_t elem;
2094 :
2095 1918 : elem = av_set_add_element (setp);
2096 1918 : *_AV_SET_EXPR (elem) = *expr;
2097 1918 : }
2098 :
2099 : /* Remove expr pointed to by IP from the av_set. */
2100 : void
2101 134683 : av_set_iter_remove (av_set_iterator *ip)
2102 : {
2103 134683 : clear_expr (_AV_SET_EXPR (*ip->lp));
2104 134683 : _list_iter_remove (ip);
2105 134683 : }
2106 :
2107 : /* Search for an expr in SET, such that it's equivalent to SOUGHT_VINSN in the
2108 : sense of vinsn_equal_p function. Return NULL if no such expr is
2109 : in SET was found. */
2110 : expr_t
2111 203871 : av_set_lookup (av_set_t set, vinsn_t sought_vinsn)
2112 : {
2113 203871 : expr_t expr;
2114 203871 : av_set_iterator i;
2115 :
2116 440155 : FOR_EACH_EXPR (expr, i, set)
2117 272984 : if (vinsn_equal_p (EXPR_VINSN (expr), sought_vinsn))
2118 : return expr;
2119 : return NULL;
2120 : }
2121 :
2122 : /* Same, but also remove the EXPR found. */
2123 : static expr_t
2124 3771 : av_set_lookup_and_remove (av_set_t *setp, vinsn_t sought_vinsn)
2125 : {
2126 3771 : expr_t expr;
2127 3771 : av_set_iterator i;
2128 :
2129 10644 : FOR_EACH_EXPR_1 (expr, i, setp)
2130 8791 : if (vinsn_equal_p (EXPR_VINSN (expr), sought_vinsn))
2131 : {
2132 1918 : _list_iter_remove_nofree (&i);
2133 1918 : return expr;
2134 : }
2135 : return NULL;
2136 : }
2137 :
2138 : /* Search for an expr in SET, such that it's equivalent to EXPR in the
2139 : sense of vinsn_equal_p function of their vinsns, but not EXPR itself.
2140 : Returns NULL if no such expr is in SET was found. */
2141 : static expr_t
2142 408 : av_set_lookup_other_equiv_expr (av_set_t set, expr_t expr)
2143 : {
2144 408 : expr_t cur_expr;
2145 408 : av_set_iterator i;
2146 :
2147 2183 : FOR_EACH_EXPR (cur_expr, i, set)
2148 : {
2149 1779 : if (cur_expr == expr)
2150 404 : continue;
2151 1375 : if (vinsn_equal_p (EXPR_VINSN (cur_expr), EXPR_VINSN (expr)))
2152 : return cur_expr;
2153 : }
2154 :
2155 : return NULL;
2156 : }
2157 :
2158 : /* If other expression is already in AVP, remove one of them. */
2159 : expr_t
2160 408 : merge_with_other_exprs (av_set_t *avp, av_set_iterator *ip, expr_t expr)
2161 : {
2162 408 : expr_t expr2;
2163 :
2164 408 : expr2 = av_set_lookup_other_equiv_expr (*avp, expr);
2165 408 : if (expr2 != NULL)
2166 : {
2167 : /* Reset target availability on merge, since taking it only from one
2168 : of the exprs would be controversial for different code. */
2169 4 : EXPR_TARGET_AVAILABLE (expr2) = -1;
2170 4 : EXPR_USEFULNESS (expr2) = 0;
2171 :
2172 4 : merge_expr (expr2, expr, NULL);
2173 :
2174 : /* Fix usefulness as it should be now REG_BR_PROB_BASE. */
2175 4 : EXPR_USEFULNESS (expr2) = REG_BR_PROB_BASE;
2176 :
2177 4 : av_set_iter_remove (ip);
2178 4 : return expr2;
2179 : }
2180 :
2181 : return expr;
2182 : }
2183 :
2184 : /* Return true if there is an expr that correlates to VI in SET. */
2185 : bool
2186 27742 : av_set_is_in_p (av_set_t set, vinsn_t vi)
2187 : {
2188 27742 : return av_set_lookup (set, vi) != NULL;
2189 : }
2190 :
2191 : /* Return a copy of SET. */
2192 : av_set_t
2193 35973 : av_set_copy (av_set_t set)
2194 : {
2195 35973 : expr_t expr;
2196 35973 : av_set_iterator i;
2197 35973 : av_set_t res = NULL;
2198 :
2199 110376 : FOR_EACH_EXPR (expr, i, set)
2200 74403 : av_set_add (&res, expr);
2201 :
2202 35973 : return res;
2203 : }
2204 :
2205 : /* Join two av sets that do not have common elements by attaching second set
2206 : (pointed to by FROMP) to the end of first set (TO_TAILP must point to
2207 : _AV_SET_NEXT of first set's last element). */
2208 : static void
2209 60727 : join_distinct_sets (av_set_t *to_tailp, av_set_t *fromp)
2210 : {
2211 60727 : gcc_assert (*to_tailp == NULL);
2212 60727 : *to_tailp = *fromp;
2213 60727 : *fromp = NULL;
2214 60727 : }
2215 :
2216 : /* Makes set pointed to by TO to be the union of TO and FROM. Clear av_set
2217 : pointed to by FROMP afterwards. */
2218 : void
2219 58531 : av_set_union_and_clear (av_set_t *top, av_set_t *fromp, insn_t insn)
2220 : {
2221 58531 : expr_t expr1;
2222 58531 : av_set_iterator i;
2223 :
2224 : /* Delete from TOP all exprs, that present in FROMP. */
2225 156141 : FOR_EACH_EXPR_1 (expr1, i, top)
2226 : {
2227 48805 : expr_t expr2 = av_set_lookup (*fromp, EXPR_VINSN (expr1));
2228 :
2229 48805 : if (expr2)
2230 : {
2231 0 : merge_expr (expr2, expr1, insn);
2232 0 : av_set_iter_remove (&i);
2233 : }
2234 : }
2235 :
2236 58531 : join_distinct_sets (i.lp, fromp);
2237 58531 : }
2238 :
2239 : /* Same as above, but also update availability of target register in
2240 : TOP judging by TO_LV_SET and FROM_LV_SET. */
2241 : void
2242 1098 : av_set_union_and_live (av_set_t *top, av_set_t *fromp, regset to_lv_set,
2243 : regset from_lv_set, insn_t insn)
2244 : {
2245 1098 : expr_t expr1;
2246 1098 : av_set_iterator i;
2247 1098 : av_set_t *to_tailp, in_both_set = NULL;
2248 :
2249 : /* Delete from TOP all exprs, that present in FROMP. */
2250 8640 : FOR_EACH_EXPR_1 (expr1, i, top)
2251 : {
2252 3771 : expr_t expr2 = av_set_lookup_and_remove (fromp, EXPR_VINSN (expr1));
2253 :
2254 3771 : if (expr2)
2255 : {
2256 : /* It may be that the expressions have different destination
2257 : registers, in which case we need to check liveness here. */
2258 1918 : if (EXPR_SEPARABLE_P (expr1))
2259 : {
2260 905 : int regno1 = (REG_P (EXPR_LHS (expr1))
2261 905 : ? (int) expr_dest_regno (expr1) : -1);
2262 905 : int regno2 = (REG_P (EXPR_LHS (expr2))
2263 905 : ? (int) expr_dest_regno (expr2) : -1);
2264 :
2265 : /* ??? We don't have a way to check restrictions for
2266 : *other* register on the current path, we did it only
2267 : for the current target register. Give up. */
2268 905 : if (regno1 != regno2)
2269 64 : EXPR_TARGET_AVAILABLE (expr2) = -1;
2270 : }
2271 1013 : else if (EXPR_INSN_RTX (expr1) != EXPR_INSN_RTX (expr2))
2272 535 : EXPR_TARGET_AVAILABLE (expr2) = -1;
2273 :
2274 1918 : merge_expr (expr2, expr1, insn);
2275 1918 : av_set_add_nocopy (&in_both_set, expr2);
2276 1918 : av_set_iter_remove (&i);
2277 : }
2278 : else
2279 : /* EXPR1 is present in TOP, but not in FROMP. Check it on
2280 : FROM_LV_SET. */
2281 1853 : set_unavailable_target_for_expr (expr1, from_lv_set);
2282 : }
2283 1098 : to_tailp = i.lp;
2284 :
2285 : /* These expressions are not present in TOP. Check liveness
2286 : restrictions on TO_LV_SET. */
2287 4042 : FOR_EACH_EXPR (expr1, i, *fromp)
2288 1472 : set_unavailable_target_for_expr (expr1, to_lv_set);
2289 :
2290 1098 : join_distinct_sets (i.lp, &in_both_set);
2291 1098 : join_distinct_sets (to_tailp, fromp);
2292 1098 : }
2293 :
2294 : /* Clear av_set pointed to by SETP. */
2295 : void
2296 60572 : av_set_clear (av_set_t *setp)
2297 : {
2298 60572 : expr_t expr;
2299 60572 : av_set_iterator i;
2300 :
2301 232376 : FOR_EACH_EXPR_1 (expr, i, setp)
2302 85902 : av_set_iter_remove (&i);
2303 :
2304 60572 : gcc_assert (*setp == NULL);
2305 60572 : }
2306 :
2307 : /* Leave only one non-speculative element in the SETP. */
2308 : void
2309 14994 : av_set_leave_one_nonspec (av_set_t *setp)
2310 : {
2311 14994 : expr_t expr;
2312 14994 : av_set_iterator i;
2313 14994 : bool has_one_nonspec = false;
2314 :
2315 : /* Keep all speculative exprs, and leave one non-speculative
2316 : (the first one). */
2317 44982 : FOR_EACH_EXPR_1 (expr, i, setp)
2318 : {
2319 14994 : if (!EXPR_SPEC_DONE_DS (expr))
2320 : {
2321 14994 : if (has_one_nonspec)
2322 0 : av_set_iter_remove (&i);
2323 : else
2324 : has_one_nonspec = true;
2325 : }
2326 : }
2327 14994 : }
2328 :
2329 : /* Return the N'th element of the SET. */
2330 : expr_t
2331 0 : av_set_element (av_set_t set, int n)
2332 : {
2333 0 : expr_t expr;
2334 0 : av_set_iterator i;
2335 :
2336 0 : FOR_EACH_EXPR (expr, i, set)
2337 0 : if (n-- == 0)
2338 0 : return expr;
2339 :
2340 0 : gcc_unreachable ();
2341 : return NULL;
2342 : }
2343 :
2344 : /* Deletes all expressions from AVP that are conditional branches (IFs). */
2345 : void
2346 4604 : av_set_substract_cond_branches (av_set_t *avp)
2347 : {
2348 4604 : av_set_iterator i;
2349 4604 : expr_t expr;
2350 :
2351 29244 : FOR_EACH_EXPR_1 (expr, i, avp)
2352 12320 : if (vinsn_cond_branch_p (EXPR_VINSN (expr)))
2353 420 : av_set_iter_remove (&i);
2354 4604 : }
2355 :
2356 : /* Multiplies usefulness attribute of each member of av-set *AVP by
2357 : value PROB / ALL_PROB. */
2358 : void
2359 6089 : av_set_split_usefulness (av_set_t av, int prob, int all_prob)
2360 : {
2361 6089 : av_set_iterator i;
2362 6089 : expr_t expr;
2363 :
2364 25980 : FOR_EACH_EXPR (expr, i, av)
2365 19891 : EXPR_USEFULNESS (expr) = (all_prob
2366 18442 : ? (EXPR_USEFULNESS (expr) * prob) / all_prob
2367 : : 0);
2368 6089 : }
2369 :
2370 : /* Leave in AVP only those expressions, which are present in AV,
2371 : and return it, merging history expressions. */
2372 : void
2373 8404 : av_set_code_motion_filter (av_set_t *avp, av_set_t av)
2374 : {
2375 8404 : av_set_iterator i;
2376 8404 : expr_t expr, expr2;
2377 :
2378 25426 : FOR_EACH_EXPR_1 (expr, i, avp)
2379 8511 : if ((expr2 = av_set_lookup (av, EXPR_VINSN (expr))) == NULL)
2380 874 : av_set_iter_remove (&i);
2381 : else
2382 : /* When updating av sets in bookkeeping blocks, we can add more insns
2383 : there which will be transformed but the upper av sets will not
2384 : reflect those transformations. We then fail to undo those
2385 : when searching for such insns. So merge the history saved
2386 : in the av set of the block we are processing. */
2387 7637 : merge_history_vect (&EXPR_HISTORY_OF_CHANGES (expr),
2388 : EXPR_HISTORY_OF_CHANGES (expr2));
2389 8404 : }
2390 :
2391 :
2392 :
2393 : /* Dependence hooks to initialize insn data. */
2394 :
2395 : /* This is used in hooks callable from dependence analysis when initializing
2396 : instruction's data. */
2397 : static struct
2398 : {
2399 : /* Where the dependence was found (lhs/rhs). */
2400 : deps_where_t where;
2401 :
2402 : /* The actual data object to initialize. */
2403 : idata_t id;
2404 :
2405 : /* True when the insn should not be made clonable. */
2406 : bool force_unique_p;
2407 :
2408 : /* True when insn should be treated as of type USE, i.e. never renamed. */
2409 : bool force_use_p;
2410 : } deps_init_id_data;
2411 :
2412 :
2413 : /* Setup ID for INSN. FORCE_UNIQUE_P is true when INSN should not be
2414 : clonable. */
2415 : static void
2416 5054 : setup_id_for_insn (idata_t id, insn_t insn, bool force_unique_p)
2417 : {
2418 5054 : int type;
2419 :
2420 : /* Determine whether INSN could be cloned and return appropriate vinsn type.
2421 : That clonable insns which can be separated into lhs and rhs have type SET.
2422 : Other clonable insns have type USE. */
2423 5054 : type = GET_CODE (insn);
2424 :
2425 : /* Only regular insns could be cloned. */
2426 5054 : if (type == INSN && !force_unique_p)
2427 : type = SET;
2428 1663 : else if (type == JUMP_INSN && simplejump_p (insn))
2429 : type = PC;
2430 1467 : else if (type == DEBUG_INSN)
2431 44 : type = !force_unique_p ? USE : INSN;
2432 :
2433 5054 : IDATA_TYPE (id) = type;
2434 5054 : IDATA_REG_SETS (id) = get_clear_regset_from_pool ();
2435 5054 : IDATA_REG_USES (id) = get_clear_regset_from_pool ();
2436 5054 : IDATA_REG_CLOBBERS (id) = get_clear_regset_from_pool ();
2437 5054 : }
2438 :
2439 : /* Start initializing insn data. */
2440 : static void
2441 661 : deps_init_id_start_insn (insn_t insn)
2442 : {
2443 661 : gcc_assert (deps_init_id_data.where == DEPS_IN_NOWHERE);
2444 :
2445 661 : setup_id_for_insn (deps_init_id_data.id, insn,
2446 661 : deps_init_id_data.force_unique_p);
2447 661 : deps_init_id_data.where = DEPS_IN_INSN;
2448 661 : }
2449 :
2450 : /* Start initializing lhs data. */
2451 : static void
2452 648 : deps_init_id_start_lhs (rtx lhs)
2453 : {
2454 648 : gcc_assert (deps_init_id_data.where == DEPS_IN_INSN);
2455 648 : gcc_assert (IDATA_LHS (deps_init_id_data.id) == NULL);
2456 :
2457 648 : if (IDATA_TYPE (deps_init_id_data.id) == SET)
2458 : {
2459 648 : IDATA_LHS (deps_init_id_data.id) = lhs;
2460 648 : deps_init_id_data.where = DEPS_IN_LHS;
2461 : }
2462 648 : }
2463 :
2464 : /* Finish initializing lhs data. */
2465 : static void
2466 648 : deps_init_id_finish_lhs (void)
2467 : {
2468 648 : deps_init_id_data.where = DEPS_IN_INSN;
2469 648 : }
2470 :
2471 : /* Note a set of REGNO. */
2472 : static void
2473 653 : deps_init_id_note_reg_set (int regno)
2474 : {
2475 653 : haifa_note_reg_set (regno);
2476 :
2477 653 : if (deps_init_id_data.where == DEPS_IN_RHS)
2478 0 : deps_init_id_data.force_use_p = true;
2479 :
2480 653 : if (IDATA_TYPE (deps_init_id_data.id) != PC)
2481 653 : SET_REGNO_REG_SET (IDATA_REG_SETS (deps_init_id_data.id), regno);
2482 :
2483 : #ifdef STACK_REGS
2484 : /* Make instructions that set stack registers to be ineligible for
2485 : renaming to avoid issues with find_used_regs. */
2486 653 : if (IN_RANGE (regno, FIRST_STACK_REG, LAST_STACK_REG))
2487 0 : deps_init_id_data.force_use_p = true;
2488 : #endif
2489 653 : }
2490 :
2491 : /* Note a clobber of REGNO. */
2492 : static void
2493 8 : deps_init_id_note_reg_clobber (int regno)
2494 : {
2495 8 : haifa_note_reg_clobber (regno);
2496 :
2497 8 : if (deps_init_id_data.where == DEPS_IN_RHS)
2498 0 : deps_init_id_data.force_use_p = true;
2499 :
2500 8 : if (IDATA_TYPE (deps_init_id_data.id) != PC)
2501 8 : SET_REGNO_REG_SET (IDATA_REG_CLOBBERS (deps_init_id_data.id), regno);
2502 8 : }
2503 :
2504 : /* Note a use of REGNO. */
2505 : static void
2506 655 : deps_init_id_note_reg_use (int regno)
2507 : {
2508 655 : haifa_note_reg_use (regno);
2509 :
2510 655 : if (IDATA_TYPE (deps_init_id_data.id) != PC)
2511 655 : SET_REGNO_REG_SET (IDATA_REG_USES (deps_init_id_data.id), regno);
2512 655 : }
2513 :
2514 : /* Start initializing rhs data. */
2515 : static void
2516 648 : deps_init_id_start_rhs (rtx rhs)
2517 : {
2518 648 : gcc_assert (deps_init_id_data.where == DEPS_IN_INSN);
2519 :
2520 : /* And there was no sel_deps_reset_to_insn (). */
2521 648 : if (IDATA_LHS (deps_init_id_data.id) != NULL)
2522 : {
2523 648 : IDATA_RHS (deps_init_id_data.id) = rhs;
2524 648 : deps_init_id_data.where = DEPS_IN_RHS;
2525 : }
2526 648 : }
2527 :
2528 : /* Finish initializing rhs data. */
2529 : static void
2530 648 : deps_init_id_finish_rhs (void)
2531 : {
2532 648 : gcc_assert (deps_init_id_data.where == DEPS_IN_RHS
2533 : || deps_init_id_data.where == DEPS_IN_INSN);
2534 648 : deps_init_id_data.where = DEPS_IN_INSN;
2535 648 : }
2536 :
2537 : /* Finish initializing insn data. */
2538 : static void
2539 661 : deps_init_id_finish_insn (void)
2540 : {
2541 661 : gcc_assert (deps_init_id_data.where == DEPS_IN_INSN);
2542 :
2543 661 : if (IDATA_TYPE (deps_init_id_data.id) == SET)
2544 : {
2545 657 : rtx lhs = IDATA_LHS (deps_init_id_data.id);
2546 657 : rtx rhs = IDATA_RHS (deps_init_id_data.id);
2547 :
2548 648 : if (lhs == NULL || rhs == NULL || !lhs_and_rhs_separable_p (lhs, rhs)
2549 987 : || deps_init_id_data.force_use_p)
2550 : {
2551 : /* This should be a USE, as we don't want to schedule its RHS
2552 : separately. However, we still want to have them recorded
2553 : for the purposes of substitution. That's why we don't
2554 : simply call downgrade_to_use () here. */
2555 327 : gcc_assert (IDATA_TYPE (deps_init_id_data.id) == SET);
2556 327 : gcc_assert (!lhs == !rhs);
2557 :
2558 327 : IDATA_TYPE (deps_init_id_data.id) = USE;
2559 : }
2560 : }
2561 :
2562 661 : deps_init_id_data.where = DEPS_IN_NOWHERE;
2563 661 : }
2564 :
2565 : /* This is dependence info used for initializing insn's data. */
2566 : static struct sched_deps_info_def deps_init_id_sched_deps_info;
2567 :
2568 : /* This initializes most of the static part of the above structure. */
2569 : static const struct sched_deps_info_def const_deps_init_id_sched_deps_info =
2570 : {
2571 : NULL,
2572 :
2573 : deps_init_id_start_insn,
2574 : deps_init_id_finish_insn,
2575 : deps_init_id_start_lhs,
2576 : deps_init_id_finish_lhs,
2577 : deps_init_id_start_rhs,
2578 : deps_init_id_finish_rhs,
2579 : deps_init_id_note_reg_set,
2580 : deps_init_id_note_reg_clobber,
2581 : deps_init_id_note_reg_use,
2582 : NULL, /* note_mem_dep */
2583 : NULL, /* note_dep */
2584 :
2585 : 0, /* use_cselib */
2586 : 0, /* use_deps_list */
2587 : 0 /* generate_spec_deps */
2588 : };
2589 :
2590 : /* Initialize INSN's lhs and rhs in ID. When FORCE_UNIQUE_P is true,
2591 : we don't actually need information about lhs and rhs. */
2592 : static void
2593 4393 : setup_id_lhs_rhs (idata_t id, insn_t insn, bool force_unique_p)
2594 : {
2595 4393 : rtx pat = PATTERN (insn);
2596 :
2597 4393 : if (NONJUMP_INSN_P (insn)
2598 3468 : && GET_CODE (pat) == SET
2599 2663 : && !force_unique_p)
2600 : {
2601 2091 : IDATA_RHS (id) = SET_SRC (pat);
2602 2091 : IDATA_LHS (id) = SET_DEST (pat);
2603 : }
2604 : else
2605 2302 : IDATA_LHS (id) = IDATA_RHS (id) = NULL;
2606 4393 : }
2607 :
2608 : /* Possibly downgrade INSN to USE. */
2609 : static void
2610 4393 : maybe_downgrade_id_to_use (idata_t id, insn_t insn)
2611 : {
2612 4393 : bool must_be_use = false;
2613 4393 : df_ref def;
2614 4393 : rtx lhs = IDATA_LHS (id);
2615 4393 : rtx rhs = IDATA_RHS (id);
2616 :
2617 : /* We downgrade only SETs. */
2618 4393 : if (IDATA_TYPE (id) != SET)
2619 : return;
2620 :
2621 2734 : if (!lhs || !lhs_and_rhs_separable_p (lhs, rhs))
2622 : {
2623 1691 : IDATA_TYPE (id) = USE;
2624 1691 : return;
2625 : }
2626 :
2627 2085 : FOR_EACH_INSN_DEF (def, insn)
2628 : {
2629 1045 : if (DF_REF_INSN (def)
2630 1045 : && DF_REF_FLAGS_IS_SET (def, DF_REF_PRE_POST_MODIFY)
2631 1047 : && loc_mentioned_in_p (DF_REF_LOC (def), IDATA_RHS (id)))
2632 : {
2633 : must_be_use = true;
2634 : break;
2635 : }
2636 :
2637 : #ifdef STACK_REGS
2638 : /* Make instructions that set stack registers to be ineligible for
2639 : renaming to avoid issues with find_used_regs. */
2640 1043 : if (IN_RANGE (DF_REF_REGNO (def), FIRST_STACK_REG, LAST_STACK_REG))
2641 : {
2642 : must_be_use = true;
2643 : break;
2644 : }
2645 : #endif
2646 : }
2647 :
2648 1043 : if (must_be_use)
2649 3 : IDATA_TYPE (id) = USE;
2650 : }
2651 :
2652 : /* Setup implicit register clobbers calculated by sched-deps for INSN
2653 : before reload and save them in ID. */
2654 : static void
2655 5054 : setup_id_implicit_regs (idata_t id, insn_t insn)
2656 : {
2657 5054 : if (reload_completed)
2658 3415 : return;
2659 :
2660 1639 : HARD_REG_SET temp;
2661 :
2662 1639 : get_implicit_reg_pending_clobbers (&temp, insn);
2663 1639 : IOR_REG_SET_HRS (IDATA_REG_SETS (id), temp);
2664 : }
2665 :
2666 : /* Setup register sets describing INSN in ID. */
2667 : static void
2668 4393 : setup_id_reg_sets (idata_t id, insn_t insn)
2669 : {
2670 4393 : struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
2671 4393 : df_ref def, use;
2672 4393 : regset tmp = get_clear_regset_from_pool ();
2673 :
2674 22131 : FOR_EACH_INSN_INFO_DEF (def, insn_info)
2675 : {
2676 17738 : unsigned int regno = DF_REF_REGNO (def);
2677 :
2678 : /* Post modifies are treated like clobbers by sched-deps.cc. */
2679 17738 : if (DF_REF_FLAGS_IS_SET (def, (DF_REF_MUST_CLOBBER
2680 : | DF_REF_PRE_POST_MODIFY)))
2681 856 : SET_REGNO_REG_SET (IDATA_REG_CLOBBERS (id), regno);
2682 16882 : else if (! DF_REF_FLAGS_IS_SET (def, DF_REF_MAY_CLOBBER))
2683 : {
2684 3042 : SET_REGNO_REG_SET (IDATA_REG_SETS (id), regno);
2685 :
2686 : #ifdef STACK_REGS
2687 : /* For stack registers, treat writes to them as writes
2688 : to the first one to be consistent with sched-deps.cc. */
2689 3042 : if (IN_RANGE (regno, FIRST_STACK_REG, LAST_STACK_REG))
2690 1 : SET_REGNO_REG_SET (IDATA_REG_SETS (id), FIRST_STACK_REG);
2691 : #endif
2692 : }
2693 : /* Mark special refs that generate read/write def pair. */
2694 17738 : if (DF_REF_FLAGS_IS_SET (def, DF_REF_CONDITIONAL)
2695 17738 : || regno == STACK_POINTER_REGNUM)
2696 283 : bitmap_set_bit (tmp, regno);
2697 : }
2698 :
2699 9373 : FOR_EACH_INSN_INFO_USE (use, insn_info)
2700 : {
2701 4980 : unsigned int regno = DF_REF_REGNO (use);
2702 :
2703 : /* When these refs are met for the first time, skip them, as
2704 : these uses are just counterparts of some defs. */
2705 4980 : if (bitmap_bit_p (tmp, regno))
2706 283 : bitmap_clear_bit (tmp, regno);
2707 4697 : else if (! DF_REF_FLAGS_IS_SET (use, DF_REF_CALL_STACK_USAGE))
2708 : {
2709 4529 : SET_REGNO_REG_SET (IDATA_REG_USES (id), regno);
2710 :
2711 : #ifdef STACK_REGS
2712 : /* For stack registers, treat reads from them as reads from
2713 : the first one to be consistent with sched-deps.cc. */
2714 4529 : if (IN_RANGE (regno, FIRST_STACK_REG, LAST_STACK_REG))
2715 3 : SET_REGNO_REG_SET (IDATA_REG_USES (id), FIRST_STACK_REG);
2716 : #endif
2717 : }
2718 : }
2719 :
2720 : /* Also get implicit reg clobbers from sched-deps. */
2721 4393 : setup_id_implicit_regs (id, insn);
2722 :
2723 4393 : return_regset_to_pool (tmp);
2724 4393 : }
2725 :
2726 : /* Initialize instruction data for INSN in ID using DF's data. */
2727 : static void
2728 4393 : init_id_from_df (idata_t id, insn_t insn, bool force_unique_p)
2729 : {
2730 4393 : gcc_assert (DF_INSN_UID_SAFE_GET (INSN_UID (insn)) != NULL);
2731 :
2732 4393 : setup_id_for_insn (id, insn, force_unique_p);
2733 4393 : setup_id_lhs_rhs (id, insn, force_unique_p);
2734 :
2735 4393 : if (INSN_NOP_P (insn))
2736 : return;
2737 :
2738 4393 : maybe_downgrade_id_to_use (id, insn);
2739 4393 : setup_id_reg_sets (id, insn);
2740 : }
2741 :
2742 : /* Initialize instruction data for INSN in ID. */
2743 : static void
2744 661 : deps_init_id (idata_t id, insn_t insn, bool force_unique_p)
2745 : {
2746 661 : class deps_desc _dc, *dc = &_dc;
2747 :
2748 661 : deps_init_id_data.where = DEPS_IN_NOWHERE;
2749 661 : deps_init_id_data.id = id;
2750 661 : deps_init_id_data.force_unique_p = force_unique_p;
2751 661 : deps_init_id_data.force_use_p = false;
2752 :
2753 661 : init_deps (dc, false);
2754 661 : memcpy (&deps_init_id_sched_deps_info,
2755 : &const_deps_init_id_sched_deps_info,
2756 : sizeof (deps_init_id_sched_deps_info));
2757 661 : if (spec_info != NULL)
2758 0 : deps_init_id_sched_deps_info.generate_spec_deps = 1;
2759 661 : sched_deps_info = &deps_init_id_sched_deps_info;
2760 :
2761 661 : deps_analyze_insn (dc, insn);
2762 : /* Implicit reg clobbers received from sched-deps separately. */
2763 661 : setup_id_implicit_regs (id, insn);
2764 :
2765 661 : free_deps (dc);
2766 661 : deps_init_id_data.id = NULL;
2767 661 : }
2768 :
2769 :
2770 : struct sched_scan_info_def
2771 : {
2772 : /* This hook notifies scheduler frontend to extend its internal per basic
2773 : block data structures. This hook should be called once before a series of
2774 : calls to bb_init (). */
2775 : void (*extend_bb) (void);
2776 :
2777 : /* This hook makes scheduler frontend to initialize its internal data
2778 : structures for the passed basic block. */
2779 : void (*init_bb) (basic_block);
2780 :
2781 : /* This hook notifies scheduler frontend to extend its internal per insn data
2782 : structures. This hook should be called once before a series of calls to
2783 : insn_init (). */
2784 : void (*extend_insn) (void);
2785 :
2786 : /* This hook makes scheduler frontend to initialize its internal data
2787 : structures for the passed insn. */
2788 : void (*init_insn) (insn_t);
2789 : };
2790 :
2791 : /* A driver function to add a set of basic blocks (BBS) to the
2792 : scheduling region. */
2793 : static void
2794 2270 : sched_scan (const struct sched_scan_info_def *ssi, bb_vec_t bbs)
2795 : {
2796 2270 : unsigned i;
2797 2270 : basic_block bb;
2798 :
2799 2270 : if (ssi->extend_bb)
2800 804 : ssi->extend_bb ();
2801 :
2802 2270 : if (ssi->init_bb)
2803 5359 : FOR_EACH_VEC_ELT (bbs, i, bb)
2804 3089 : ssi->init_bb (bb);
2805 :
2806 2270 : if (ssi->extend_insn)
2807 733 : ssi->extend_insn ();
2808 :
2809 2270 : if (ssi->init_insn)
2810 3484 : FOR_EACH_VEC_ELT (bbs, i, bb)
2811 : {
2812 2018 : rtx_insn *insn;
2813 :
2814 13881 : FOR_BB_INSNS (bb, insn)
2815 11863 : ssi->init_insn (insn);
2816 : }
2817 2270 : }
2818 :
2819 : /* Implement hooks for collecting fundamental insn properties like if insn is
2820 : an ASM or is within a SCHED_GROUP. */
2821 :
2822 : /* True when a "one-time init" data for INSN was already inited. */
2823 : static bool
2824 20573 : first_time_insn_init (insn_t insn)
2825 : {
2826 20573 : return INSN_LIVE (insn) == NULL;
2827 : }
2828 :
2829 : /* Hash an entry in a transformed_insns hashtable. */
2830 : static hashval_t
2831 0 : hash_transformed_insns (const void *p)
2832 : {
2833 0 : return VINSN_HASH_RTX (((const struct transformed_insns *) p)->vinsn_old);
2834 : }
2835 :
2836 : /* Compare the entries in a transformed_insns hashtable. */
2837 : static int
2838 355 : eq_transformed_insns (const void *p, const void *q)
2839 : {
2840 355 : rtx_insn *i1 =
2841 355 : VINSN_INSN_RTX (((const struct transformed_insns *) p)->vinsn_old);
2842 355 : rtx_insn *i2 =
2843 355 : VINSN_INSN_RTX (((const struct transformed_insns *) q)->vinsn_old);
2844 :
2845 355 : if (INSN_UID (i1) == INSN_UID (i2))
2846 : return 1;
2847 45 : return rtx_equal_p (PATTERN (i1), PATTERN (i2));
2848 : }
2849 :
2850 : /* Free an entry in a transformed_insns hashtable. */
2851 : static void
2852 65 : free_transformed_insns (void *p)
2853 : {
2854 65 : struct transformed_insns *pti = (struct transformed_insns *) p;
2855 :
2856 65 : vinsn_detach (pti->vinsn_old);
2857 65 : vinsn_detach (pti->vinsn_new);
2858 65 : free (pti);
2859 65 : }
2860 :
2861 : /* Init the s_i_d data for INSN which should be inited just once, when
2862 : we first see the insn. */
2863 : static void
2864 5626 : init_first_time_insn_data (insn_t insn)
2865 : {
2866 : /* This should not be set if this is the first time we init data for
2867 : insn. */
2868 5626 : gcc_assert (first_time_insn_init (insn));
2869 :
2870 : /* These are needed for nops too. */
2871 5626 : INSN_LIVE (insn) = get_regset_from_pool ();
2872 5626 : INSN_LIVE_VALID_P (insn) = false;
2873 :
2874 5626 : if (!INSN_NOP_P (insn))
2875 : {
2876 4805 : INSN_ANALYZED_DEPS (insn) = BITMAP_ALLOC (NULL);
2877 4805 : INSN_FOUND_DEPS (insn) = BITMAP_ALLOC (NULL);
2878 4805 : INSN_TRANSFORMED_INSNS (insn)
2879 4805 : = htab_create (16, hash_transformed_insns,
2880 : eq_transformed_insns, free_transformed_insns);
2881 4805 : init_deps (&INSN_DEPS_CONTEXT (insn), true);
2882 : }
2883 5626 : }
2884 :
2885 : /* Free almost all above data for INSN that is scheduled already.
2886 : Used for extra-large basic blocks. */
2887 : void
2888 8019 : free_data_for_scheduled_insn (insn_t insn)
2889 : {
2890 8019 : gcc_assert (! first_time_insn_init (insn));
2891 :
2892 8019 : if (! INSN_ANALYZED_DEPS (insn))
2893 : return;
2894 :
2895 4511 : BITMAP_FREE (INSN_ANALYZED_DEPS (insn));
2896 4511 : BITMAP_FREE (INSN_FOUND_DEPS (insn));
2897 4511 : htab_delete (INSN_TRANSFORMED_INSNS (insn));
2898 :
2899 : /* This is allocated only for bookkeeping insns. */
2900 4511 : if (INSN_ORIGINATORS (insn))
2901 152 : BITMAP_FREE (INSN_ORIGINATORS (insn));
2902 4511 : free_deps (&INSN_DEPS_CONTEXT (insn));
2903 :
2904 4511 : INSN_ANALYZED_DEPS (insn) = NULL;
2905 :
2906 : /* Clear the readonly flag so we would ICE when trying to recalculate
2907 : the deps context (as we believe that it should not happen). */
2908 4511 : (&INSN_DEPS_CONTEXT (insn))->readonly = 0;
2909 : }
2910 :
2911 : /* Free the same data as above for INSN. */
2912 : static void
2913 4511 : free_first_time_insn_data (insn_t insn)
2914 : {
2915 4511 : gcc_assert (! first_time_insn_init (insn));
2916 :
2917 4511 : free_data_for_scheduled_insn (insn);
2918 4511 : return_regset_to_pool (INSN_LIVE (insn));
2919 4511 : INSN_LIVE (insn) = NULL;
2920 4511 : INSN_LIVE_VALID_P (insn) = false;
2921 4511 : }
2922 :
2923 : /* Initialize region-scope data structures for basic blocks. */
2924 : static void
2925 1007 : init_global_and_expr_for_bb (basic_block bb)
2926 : {
2927 1007 : if (sel_bb_empty_p (bb))
2928 : return;
2929 :
2930 978 : invalidate_av_set (bb);
2931 : }
2932 :
2933 : /* Data for global dependency analysis (to initialize CANT_MOVE and
2934 : SCHED_GROUP_P). */
2935 : static struct
2936 : {
2937 : /* Previous insn. */
2938 : insn_t prev_insn;
2939 : } init_global_data;
2940 :
2941 : /* Determine if INSN is in the sched_group, is an asm or should not be
2942 : cloned. After that initialize its expr. */
2943 : static void
2944 5848 : init_global_and_expr_for_insn (insn_t insn)
2945 : {
2946 5848 : if (LABEL_P (insn))
2947 : return;
2948 :
2949 5359 : if (NOTE_INSN_BASIC_BLOCK_P (insn))
2950 : {
2951 1007 : init_global_data.prev_insn = NULL;
2952 1007 : return;
2953 : }
2954 :
2955 4352 : gcc_assert (INSN_P (insn));
2956 :
2957 4352 : if (SCHED_GROUP_P (insn))
2958 : /* Setup a sched_group. */
2959 : {
2960 332 : insn_t prev_insn = init_global_data.prev_insn;
2961 :
2962 332 : if (prev_insn)
2963 0 : INSN_SCHED_NEXT (prev_insn) = insn;
2964 :
2965 332 : init_global_data.prev_insn = insn;
2966 : }
2967 : else
2968 4020 : init_global_data.prev_insn = NULL;
2969 :
2970 4352 : if (GET_CODE (PATTERN (insn)) == ASM_INPUT
2971 4352 : || asm_noperands (PATTERN (insn)) >= 0)
2972 : /* Mark INSN as an asm. */
2973 10 : INSN_ASM_P (insn) = true;
2974 :
2975 4352 : {
2976 4352 : bool force_unique_p;
2977 4352 : ds_t spec_done_ds;
2978 :
2979 : /* Certain instructions cannot be cloned, and frame related insns and
2980 : the insn adjacent to NOTE_INSN_EPILOGUE_BEG cannot be moved out of
2981 : their block. */
2982 4352 : if (prologue_epilogue_contains (insn))
2983 : {
2984 382 : if (RTX_FRAME_RELATED_P (insn))
2985 289 : CANT_MOVE (insn) = 1;
2986 : else
2987 : {
2988 93 : rtx note;
2989 100 : for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
2990 35 : if (REG_NOTE_KIND (note) == REG_SAVE_NOTE
2991 28 : && ((enum insn_note) INTVAL (XEXP (note, 0))
2992 : == NOTE_INSN_EPILOGUE_BEG))
2993 : {
2994 28 : CANT_MOVE (insn) = 1;
2995 28 : break;
2996 : }
2997 : }
2998 : force_unique_p = true;
2999 : }
3000 : else
3001 3970 : if (CANT_MOVE (insn)
3002 2765 : || INSN_ASM_P (insn)
3003 2757 : || SCHED_GROUP_P (insn)
3004 2757 : || CALL_P (insn)
3005 : /* Exception handling insns are always unique. */
3006 2757 : || (cfun->can_throw_non_call_exceptions && can_throw_internal (insn))
3007 : /* TRAP_IF though have an INSN code is control_flow_insn_p (). */
3008 2757 : || control_flow_insn_p (insn)
3009 2746 : || volatile_insn_p (PATTERN (insn))
3010 6715 : || (targetm.cannot_copy_insn_p
3011 0 : && targetm.cannot_copy_insn_p (insn)))
3012 : force_unique_p = true;
3013 : else
3014 : force_unique_p = false;
3015 :
3016 4352 : if (targetm.sched.get_insn_spec_ds)
3017 : {
3018 0 : spec_done_ds = targetm.sched.get_insn_spec_ds (insn);
3019 0 : spec_done_ds = ds_get_max_dep_weak (spec_done_ds);
3020 : }
3021 : else
3022 : spec_done_ds = 0;
3023 :
3024 : /* Initialize INSN's expr. */
3025 4352 : init_expr (INSN_EXPR (insn), vinsn_create (insn, force_unique_p), 0,
3026 4352 : REG_BR_PROB_BASE, INSN_PRIORITY (insn), 0, BLOCK_NUM (insn),
3027 4352 : spec_done_ds, 0, 0, vNULL, true,
3028 4352 : false, false, false, CANT_MOVE (insn));
3029 : }
3030 :
3031 4352 : init_first_time_insn_data (insn);
3032 : }
3033 :
3034 : /* Scan the region and initialize instruction data for basic blocks BBS. */
3035 : void
3036 733 : sel_init_global_and_expr (bb_vec_t bbs)
3037 : {
3038 : /* ??? It would be nice to implement push / pop scheme for sched_infos. */
3039 733 : const struct sched_scan_info_def ssi =
3040 : {
3041 : NULL, /* extend_bb */
3042 : init_global_and_expr_for_bb, /* init_bb */
3043 : extend_insn_data, /* extend_insn */
3044 : init_global_and_expr_for_insn /* init_insn */
3045 : };
3046 :
3047 733 : sched_scan (&ssi, bbs);
3048 733 : }
3049 :
3050 : /* Finalize region-scope data structures for basic blocks. */
3051 : static void
3052 1011 : finish_global_and_expr_for_bb (basic_block bb)
3053 : {
3054 1011 : av_set_clear (&BB_AV_SET (bb));
3055 1011 : BB_AV_LEVEL (bb) = 0;
3056 1011 : }
3057 :
3058 : /* Finalize INSN's data. */
3059 : static void
3060 6015 : finish_global_and_expr_insn (insn_t insn)
3061 : {
3062 6015 : if (LABEL_P (insn) || NOTE_INSN_BASIC_BLOCK_P (insn))
3063 : return;
3064 :
3065 4511 : gcc_assert (INSN_P (insn));
3066 :
3067 4511 : if (INSN_LUID (insn) > 0)
3068 : {
3069 4511 : free_first_time_insn_data (insn);
3070 4511 : INSN_WS_LEVEL (insn) = 0;
3071 4511 : CANT_MOVE (insn) = 0;
3072 :
3073 : /* We can no longer assert this, as vinsns of this insn could be
3074 : easily live in other insn's caches. This should be changed to
3075 : a counter-like approach among all vinsns. */
3076 4511 : gcc_assert (true || VINSN_COUNT (INSN_VINSN (insn)) == 1);
3077 4511 : clear_expr (INSN_EXPR (insn));
3078 : }
3079 : }
3080 :
3081 : /* Finalize per instruction data for the whole region. */
3082 : void
3083 733 : sel_finish_global_and_expr (void)
3084 : {
3085 733 : {
3086 733 : bb_vec_t bbs;
3087 733 : int i;
3088 :
3089 733 : bbs.create (current_nr_blocks);
3090 :
3091 2477 : for (i = 0; i < current_nr_blocks; i++)
3092 1011 : bbs.quick_push (BASIC_BLOCK_FOR_FN (cfun, BB_TO_BLOCK (i)));
3093 :
3094 : /* Clear AV_SETs and INSN_EXPRs. */
3095 733 : {
3096 733 : const struct sched_scan_info_def ssi =
3097 : {
3098 : NULL, /* extend_bb */
3099 : finish_global_and_expr_for_bb, /* init_bb */
3100 : NULL, /* extend_insn */
3101 : finish_global_and_expr_insn /* init_insn */
3102 : };
3103 :
3104 733 : sched_scan (&ssi, bbs);
3105 : }
3106 :
3107 733 : bbs.release ();
3108 : }
3109 :
3110 733 : finish_insns ();
3111 733 : }
3112 :
3113 :
3114 : /* In the below hooks, we merely calculate whether or not a dependence
3115 : exists, and in what part of insn. However, we will need more data
3116 : when we'll start caching dependence requests. */
3117 :
3118 : /* Container to hold information for dependency analysis. */
3119 : static struct
3120 : {
3121 : deps_t dc;
3122 :
3123 : /* A variable to track which part of rtx we are scanning in
3124 : sched-deps.cc: sched_analyze_insn (). */
3125 : deps_where_t where;
3126 :
3127 : /* Current producer. */
3128 : insn_t pro;
3129 :
3130 : /* Current consumer. */
3131 : vinsn_t con;
3132 :
3133 : /* Is SEL_DEPS_HAS_DEP_P[DEPS_IN_X] is true, then X has a dependence.
3134 : X is from { INSN, LHS, RHS }. */
3135 : ds_t has_dep_p[DEPS_IN_NOWHERE];
3136 : } has_dependence_data;
3137 :
3138 : /* Start analyzing dependencies of INSN. */
3139 : static void
3140 17781 : has_dependence_start_insn (insn_t insn ATTRIBUTE_UNUSED)
3141 : {
3142 17781 : gcc_assert (has_dependence_data.where == DEPS_IN_NOWHERE);
3143 :
3144 17781 : has_dependence_data.where = DEPS_IN_INSN;
3145 17781 : }
3146 :
3147 : /* Finish analyzing dependencies of an insn. */
3148 : static void
3149 17781 : has_dependence_finish_insn (void)
3150 : {
3151 17781 : gcc_assert (has_dependence_data.where == DEPS_IN_INSN);
3152 :
3153 17781 : has_dependence_data.where = DEPS_IN_NOWHERE;
3154 17781 : }
3155 :
3156 : /* Start analyzing dependencies of LHS. */
3157 : static void
3158 15638 : has_dependence_start_lhs (rtx lhs ATTRIBUTE_UNUSED)
3159 : {
3160 15638 : gcc_assert (has_dependence_data.where == DEPS_IN_INSN);
3161 :
3162 15638 : if (VINSN_LHS (has_dependence_data.con) != NULL)
3163 15061 : has_dependence_data.where = DEPS_IN_LHS;
3164 15638 : }
3165 :
3166 : /* Finish analyzing dependencies of an lhs. */
3167 : static void
3168 15638 : has_dependence_finish_lhs (void)
3169 : {
3170 15638 : has_dependence_data.where = DEPS_IN_INSN;
3171 15638 : }
3172 :
3173 : /* Start analyzing dependencies of RHS. */
3174 : static void
3175 15638 : has_dependence_start_rhs (rtx rhs ATTRIBUTE_UNUSED)
3176 : {
3177 15638 : gcc_assert (has_dependence_data.where == DEPS_IN_INSN);
3178 :
3179 15638 : if (VINSN_RHS (has_dependence_data.con) != NULL)
3180 15061 : has_dependence_data.where = DEPS_IN_RHS;
3181 15638 : }
3182 :
3183 : /* Start analyzing dependencies of an rhs. */
3184 : static void
3185 15638 : has_dependence_finish_rhs (void)
3186 : {
3187 15638 : gcc_assert (has_dependence_data.where == DEPS_IN_RHS
3188 : || has_dependence_data.where == DEPS_IN_INSN);
3189 :
3190 15638 : has_dependence_data.where = DEPS_IN_INSN;
3191 15638 : }
3192 :
3193 : /* Note a set of REGNO. */
3194 : static void
3195 16894 : has_dependence_note_reg_set (int regno)
3196 : {
3197 16894 : struct deps_reg *reg_last = &has_dependence_data.dc->reg_last[regno];
3198 :
3199 16894 : if (!sched_insns_conditions_mutex_p (has_dependence_data.pro,
3200 16894 : VINSN_INSN_RTX
3201 : (has_dependence_data.con)))
3202 : {
3203 16894 : ds_t *dsp = &has_dependence_data.has_dep_p[has_dependence_data.where];
3204 :
3205 16894 : if (reg_last->sets != NULL
3206 15785 : || reg_last->clobbers != NULL)
3207 1613 : *dsp = (*dsp & ~SPECULATIVE) | DEP_OUTPUT;
3208 :
3209 16894 : if (reg_last->uses || reg_last->implicit_sets)
3210 873 : *dsp = (*dsp & ~SPECULATIVE) | DEP_ANTI;
3211 : }
3212 16894 : }
3213 :
3214 : /* Note a clobber of REGNO. */
3215 : static void
3216 1588 : has_dependence_note_reg_clobber (int regno)
3217 : {
3218 1588 : struct deps_reg *reg_last = &has_dependence_data.dc->reg_last[regno];
3219 :
3220 1588 : if (!sched_insns_conditions_mutex_p (has_dependence_data.pro,
3221 1588 : VINSN_INSN_RTX
3222 : (has_dependence_data.con)))
3223 : {
3224 1588 : ds_t *dsp = &has_dependence_data.has_dep_p[has_dependence_data.where];
3225 :
3226 1588 : if (reg_last->sets)
3227 39 : *dsp = (*dsp & ~SPECULATIVE) | DEP_OUTPUT;
3228 :
3229 1588 : if (reg_last->uses || reg_last->implicit_sets)
3230 248 : *dsp = (*dsp & ~SPECULATIVE) | DEP_ANTI;
3231 : }
3232 1588 : }
3233 :
3234 : /* Note a use of REGNO. */
3235 : static void
3236 19785 : has_dependence_note_reg_use (int regno)
3237 : {
3238 19785 : struct deps_reg *reg_last = &has_dependence_data.dc->reg_last[regno];
3239 :
3240 19785 : if (!sched_insns_conditions_mutex_p (has_dependence_data.pro,
3241 19785 : VINSN_INSN_RTX
3242 : (has_dependence_data.con)))
3243 : {
3244 19785 : ds_t *dsp = &has_dependence_data.has_dep_p[has_dependence_data.where];
3245 :
3246 19785 : if (reg_last->sets)
3247 1851 : *dsp = (*dsp & ~SPECULATIVE) | DEP_TRUE;
3248 :
3249 19785 : if (reg_last->clobbers || reg_last->implicit_sets)
3250 137 : *dsp = (*dsp & ~SPECULATIVE) | DEP_ANTI;
3251 :
3252 : /* Merge BE_IN_SPEC bits into *DSP when the dependency producer
3253 : is actually a check insn. We need to do this for any register
3254 : read-read dependency with the check unless we track properly
3255 : all registers written by BE_IN_SPEC-speculated insns, as
3256 : we don't have explicit dependence lists. See PR 53975. */
3257 19785 : if (reg_last->uses)
3258 : {
3259 2725 : ds_t pro_spec_checked_ds;
3260 :
3261 2725 : pro_spec_checked_ds = INSN_SPEC_CHECKED_DS (has_dependence_data.pro);
3262 2725 : pro_spec_checked_ds = ds_get_max_dep_weak (pro_spec_checked_ds);
3263 :
3264 2725 : if (pro_spec_checked_ds != 0)
3265 0 : *dsp = ds_full_merge (*dsp, pro_spec_checked_ds,
3266 : NULL_RTX, NULL_RTX);
3267 : }
3268 : }
3269 19785 : }
3270 :
3271 : /* Note a memory dependence. */
3272 : static void
3273 441 : has_dependence_note_mem_dep (rtx mem ATTRIBUTE_UNUSED,
3274 : rtx pending_mem ATTRIBUTE_UNUSED,
3275 : insn_t pending_insn ATTRIBUTE_UNUSED,
3276 : ds_t ds ATTRIBUTE_UNUSED)
3277 : {
3278 441 : if (!sched_insns_conditions_mutex_p (has_dependence_data.pro,
3279 441 : VINSN_INSN_RTX (has_dependence_data.con)))
3280 : {
3281 441 : ds_t *dsp = &has_dependence_data.has_dep_p[has_dependence_data.where];
3282 :
3283 441 : *dsp = ds_full_merge (ds, *dsp, pending_mem, mem);
3284 : }
3285 441 : }
3286 :
3287 : /* Note a dependence. */
3288 : static void
3289 849 : has_dependence_note_dep (insn_t pro, ds_t ds ATTRIBUTE_UNUSED)
3290 : {
3291 849 : insn_t real_pro = has_dependence_data.pro;
3292 849 : insn_t real_con = VINSN_INSN_RTX (has_dependence_data.con);
3293 :
3294 : /* We do not allow for debug insns to move through others unless they
3295 : are at the start of bb. This movement may create bookkeeping copies
3296 : that later would not be able to move up, violating the invariant
3297 : that a bookkeeping copy should be movable as the original insn.
3298 : Detect that here and allow that movement if we allowed it before
3299 : in the first place. */
3300 73 : if (DEBUG_INSN_P (real_con) && !DEBUG_INSN_P (real_pro)
3301 889 : && INSN_UID (NEXT_INSN (pro)) == INSN_UID (real_con))
3302 : return;
3303 :
3304 809 : if (!sched_insns_conditions_mutex_p (real_pro, real_con))
3305 : {
3306 809 : ds_t *dsp = &has_dependence_data.has_dep_p[has_dependence_data.where];
3307 :
3308 809 : *dsp = ds_full_merge (ds, *dsp, NULL_RTX, NULL_RTX);
3309 : }
3310 : }
3311 :
3312 : /* Mark the insn as having a hard dependence that prevents speculation. */
3313 : void
3314 0 : sel_mark_hard_insn (rtx insn)
3315 : {
3316 0 : int i;
3317 :
3318 : /* Only work when we're in has_dependence_p mode.
3319 : ??? This is a hack, this should actually be a hook. */
3320 0 : if (!has_dependence_data.dc || !has_dependence_data.pro)
3321 : return;
3322 :
3323 0 : gcc_assert (insn == VINSN_INSN_RTX (has_dependence_data.con));
3324 0 : gcc_assert (has_dependence_data.where == DEPS_IN_INSN);
3325 :
3326 0 : for (i = 0; i < DEPS_IN_NOWHERE; i++)
3327 0 : has_dependence_data.has_dep_p[i] &= ~SPECULATIVE;
3328 : }
3329 :
3330 : /* This structure holds the hooks for the dependency analysis used when
3331 : actually processing dependencies in the scheduler. */
3332 : static struct sched_deps_info_def has_dependence_sched_deps_info;
3333 :
3334 : /* This initializes most of the fields of the above structure. */
3335 : static const struct sched_deps_info_def const_has_dependence_sched_deps_info =
3336 : {
3337 : NULL,
3338 :
3339 : has_dependence_start_insn,
3340 : has_dependence_finish_insn,
3341 : has_dependence_start_lhs,
3342 : has_dependence_finish_lhs,
3343 : has_dependence_start_rhs,
3344 : has_dependence_finish_rhs,
3345 : has_dependence_note_reg_set,
3346 : has_dependence_note_reg_clobber,
3347 : has_dependence_note_reg_use,
3348 : has_dependence_note_mem_dep,
3349 : has_dependence_note_dep,
3350 :
3351 : 0, /* use_cselib */
3352 : 0, /* use_deps_list */
3353 : 0 /* generate_spec_deps */
3354 : };
3355 :
3356 : /* Initialize has_dependence_sched_deps_info with extra spec field. */
3357 : static void
3358 17781 : setup_has_dependence_sched_deps_info (void)
3359 : {
3360 17781 : memcpy (&has_dependence_sched_deps_info,
3361 : &const_has_dependence_sched_deps_info,
3362 : sizeof (has_dependence_sched_deps_info));
3363 :
3364 17781 : if (spec_info != NULL)
3365 0 : has_dependence_sched_deps_info.generate_spec_deps = 1;
3366 :
3367 17781 : sched_deps_info = &has_dependence_sched_deps_info;
3368 17781 : }
3369 :
3370 : /* Remove all dependences found and recorded in has_dependence_data array. */
3371 : void
3372 17781 : sel_clear_has_dependence (void)
3373 : {
3374 17781 : int i;
3375 :
3376 71124 : for (i = 0; i < DEPS_IN_NOWHERE; i++)
3377 53343 : has_dependence_data.has_dep_p[i] = 0;
3378 17781 : }
3379 :
3380 : /* Return nonzero if EXPR has is dependent upon PRED. Return the pointer
3381 : to the dependence information array in HAS_DEP_PP. */
3382 : ds_t
3383 17974 : has_dependence_p (expr_t expr, insn_t pred, ds_t **has_dep_pp)
3384 : {
3385 17974 : int i;
3386 17974 : ds_t ds;
3387 17974 : class deps_desc *dc;
3388 :
3389 17974 : if (INSN_SIMPLEJUMP_P (pred))
3390 : /* Unconditional jump is just a transfer of control flow.
3391 : Ignore it. */
3392 : return false;
3393 :
3394 17781 : dc = &INSN_DEPS_CONTEXT (pred);
3395 :
3396 : /* We init this field lazily. */
3397 17781 : if (dc->reg_last == NULL)
3398 3314 : init_deps_reg_last (dc);
3399 :
3400 17781 : if (!dc->readonly)
3401 : {
3402 3314 : has_dependence_data.pro = NULL;
3403 : /* Initialize empty dep context with information about PRED. */
3404 3314 : advance_deps_context (dc, pred);
3405 3314 : dc->readonly = 1;
3406 : }
3407 :
3408 17781 : has_dependence_data.where = DEPS_IN_NOWHERE;
3409 17781 : has_dependence_data.pro = pred;
3410 17781 : has_dependence_data.con = EXPR_VINSN (expr);
3411 17781 : has_dependence_data.dc = dc;
3412 :
3413 17781 : sel_clear_has_dependence ();
3414 :
3415 : /* Now catch all dependencies that would be generated between PRED and
3416 : INSN. */
3417 17781 : setup_has_dependence_sched_deps_info ();
3418 17781 : deps_analyze_insn (dc, EXPR_INSN_RTX (expr));
3419 17781 : has_dependence_data.dc = NULL;
3420 :
3421 : /* When a barrier was found, set DEPS_IN_INSN bits. */
3422 17781 : if (dc->last_reg_pending_barrier == TRUE_BARRIER)
3423 10 : has_dependence_data.has_dep_p[DEPS_IN_INSN] = DEP_TRUE;
3424 17771 : else if (dc->last_reg_pending_barrier == MOVE_BARRIER)
3425 65 : has_dependence_data.has_dep_p[DEPS_IN_INSN] = DEP_ANTI;
3426 :
3427 : /* Do not allow stores to memory to move through checks. Currently
3428 : we don't move this to sched-deps.cc as the check doesn't have
3429 : obvious places to which this dependence can be attached.
3430 : FIMXE: this should go to a hook. */
3431 17781 : if (EXPR_LHS (expr)
3432 15061 : && MEM_P (EXPR_LHS (expr))
3433 18530 : && sel_insn_is_speculation_check (pred))
3434 0 : has_dependence_data.has_dep_p[DEPS_IN_INSN] = DEP_ANTI;
3435 :
3436 17781 : *has_dep_pp = has_dependence_data.has_dep_p;
3437 17781 : ds = 0;
3438 71124 : for (i = 0; i < DEPS_IN_NOWHERE; i++)
3439 53343 : ds = ds_full_merge (ds, has_dependence_data.has_dep_p[i],
3440 : NULL_RTX, NULL_RTX);
3441 :
3442 : return ds;
3443 : }
3444 :
3445 :
3446 : /* Dependence hooks implementation that checks dependence latency constraints
3447 : on the insns being scheduled. The entry point for these routines is
3448 : tick_check_p predicate. */
3449 :
3450 : static struct
3451 : {
3452 : /* An expr we are currently checking. */
3453 : expr_t expr;
3454 :
3455 : /* A minimal cycle for its scheduling. */
3456 : int cycle;
3457 :
3458 : /* Whether we have seen a true dependence while checking. */
3459 : bool seen_true_dep_p;
3460 : } tick_check_data;
3461 :
3462 : /* Update minimal scheduling cycle for tick_check_insn given that it depends
3463 : on PRO with status DS and weight DW. */
3464 : static void
3465 28428 : tick_check_dep_with_dw (insn_t pro_insn, ds_t ds, dw_t dw)
3466 : {
3467 28428 : expr_t con_expr = tick_check_data.expr;
3468 28428 : insn_t con_insn = EXPR_INSN_RTX (con_expr);
3469 :
3470 28428 : if (con_insn != pro_insn)
3471 : {
3472 28424 : enum reg_note dt;
3473 28424 : int tick;
3474 :
3475 28424 : if (/* PROducer was removed from above due to pipelining. */
3476 28416 : !INSN_IN_STREAM_P (pro_insn)
3477 : /* Or PROducer was originally on the next iteration regarding the
3478 : CONsumer. */
3479 56840 : || (INSN_SCHED_TIMES (pro_insn)
3480 28416 : - EXPR_SCHED_TIMES (con_expr)) > 1)
3481 : /* Don't count this dependence. */
3482 : return;
3483 :
3484 28364 : dt = ds_to_dt (ds);
3485 28364 : if (dt == REG_DEP_TRUE)
3486 6788 : tick_check_data.seen_true_dep_p = true;
3487 :
3488 28364 : gcc_assert (INSN_SCHED_CYCLE (pro_insn) > 0);
3489 :
3490 28364 : {
3491 28364 : dep_def _dep, *dep = &_dep;
3492 :
3493 28364 : init_dep (dep, pro_insn, con_insn, dt);
3494 :
3495 28364 : tick = INSN_SCHED_CYCLE (pro_insn) + dep_cost_1 (dep, dw);
3496 : }
3497 :
3498 : /* When there are several kinds of dependencies between pro and con,
3499 : only REG_DEP_TRUE should be taken into account. */
3500 28364 : if (tick > tick_check_data.cycle
3501 9994 : && (dt == REG_DEP_TRUE || !tick_check_data.seen_true_dep_p))
3502 9843 : tick_check_data.cycle = tick;
3503 : }
3504 : }
3505 :
3506 : /* An implementation of note_dep hook. */
3507 : static void
3508 25403 : tick_check_note_dep (insn_t pro, ds_t ds)
3509 : {
3510 25403 : tick_check_dep_with_dw (pro, ds, 0);
3511 25403 : }
3512 :
3513 : /* An implementation of note_mem_dep hook. */
3514 : static void
3515 3025 : tick_check_note_mem_dep (rtx mem1, rtx mem2, insn_t pro, ds_t ds)
3516 : {
3517 3025 : dw_t dw;
3518 :
3519 3025 : dw = (ds_to_dt (ds) == REG_DEP_TRUE
3520 3025 : ? estimate_dep_weak (mem1, mem2)
3521 : : 0);
3522 :
3523 3025 : tick_check_dep_with_dw (pro, ds, dw);
3524 3025 : }
3525 :
3526 : /* This structure contains hooks for dependence analysis used when determining
3527 : whether an insn is ready for scheduling. */
3528 : static struct sched_deps_info_def tick_check_sched_deps_info =
3529 : {
3530 : NULL,
3531 :
3532 : NULL,
3533 : NULL,
3534 : NULL,
3535 : NULL,
3536 : NULL,
3537 : NULL,
3538 : haifa_note_reg_set,
3539 : haifa_note_reg_clobber,
3540 : haifa_note_reg_use,
3541 : tick_check_note_mem_dep,
3542 : tick_check_note_dep,
3543 :
3544 : 0, 0, 0
3545 : };
3546 :
3547 : /* Estimate number of cycles from the current cycle of FENCE until EXPR can be
3548 : scheduled. Return 0 if all data from producers in DC is ready. */
3549 : int
3550 11672 : tick_check_p (expr_t expr, deps_t dc, fence_t fence)
3551 : {
3552 11672 : int cycles_left;
3553 : /* Initialize variables. */
3554 11672 : tick_check_data.expr = expr;
3555 11672 : tick_check_data.cycle = 0;
3556 11672 : tick_check_data.seen_true_dep_p = false;
3557 11672 : sched_deps_info = &tick_check_sched_deps_info;
3558 :
3559 11672 : gcc_assert (!dc->readonly);
3560 11672 : dc->readonly = 1;
3561 11672 : deps_analyze_insn (dc, EXPR_INSN_RTX (expr));
3562 11672 : dc->readonly = 0;
3563 :
3564 11672 : cycles_left = tick_check_data.cycle - FENCE_CYCLE (fence);
3565 :
3566 11672 : return cycles_left >= 0 ? cycles_left : 0;
3567 : }
3568 :
3569 :
3570 : /* Functions to work with insns. */
3571 :
3572 : /* Returns true if LHS of INSN is the same as DEST of an insn
3573 : being moved. */
3574 : bool
3575 6584 : lhs_of_insn_equals_to_dest_p (insn_t insn, rtx dest)
3576 : {
3577 6584 : rtx lhs = INSN_LHS (insn);
3578 :
3579 6584 : if (lhs == NULL || dest == NULL)
3580 : return false;
3581 :
3582 3813 : return rtx_equal_p (lhs, dest);
3583 : }
3584 :
3585 : /* Return s_i_d entry of INSN. Callable from debugger. */
3586 : sel_insn_data_def
3587 0 : insn_sid (insn_t insn)
3588 : {
3589 0 : return *SID (insn);
3590 : }
3591 :
3592 : /* True when INSN is a speculative check. We can tell this by looking
3593 : at the data structures of the selective scheduler, not by examining
3594 : the pattern. */
3595 : bool
3596 256966 : sel_insn_is_speculation_check (rtx insn)
3597 : {
3598 256966 : return s_i_d.exists () && !! INSN_SPEC_CHECKED_DS (insn);
3599 : }
3600 :
3601 : /* Extracts machine mode MODE and destination location DST_LOC
3602 : for given INSN. */
3603 : void
3604 166 : get_dest_and_mode (rtx insn, rtx *dst_loc, machine_mode *mode)
3605 : {
3606 166 : rtx pat = PATTERN (insn);
3607 :
3608 166 : gcc_assert (dst_loc);
3609 166 : gcc_assert (GET_CODE (pat) == SET);
3610 :
3611 166 : *dst_loc = SET_DEST (pat);
3612 :
3613 166 : gcc_assert (*dst_loc);
3614 166 : gcc_assert (MEM_P (*dst_loc) || REG_P (*dst_loc));
3615 :
3616 166 : if (mode)
3617 166 : *mode = GET_MODE (*dst_loc);
3618 166 : }
3619 :
3620 : /* Returns true when moving through JUMP will result in bookkeeping
3621 : creation. */
3622 : bool
3623 856 : bookkeeping_can_be_created_if_moved_through_p (insn_t jump)
3624 : {
3625 856 : insn_t succ;
3626 856 : succ_iterator si;
3627 :
3628 1701 : FOR_EACH_SUCC (succ, si, jump)
3629 871 : if (sel_num_cfg_preds_gt_1 (succ))
3630 : return true;
3631 :
3632 : return false;
3633 : }
3634 :
3635 : /* Return 'true' if INSN is the only one in its basic block. */
3636 : static bool
3637 2429 : insn_is_the_only_one_in_bb_p (insn_t insn)
3638 : {
3639 2429 : return sel_bb_head_p (insn) && sel_bb_end_p (insn);
3640 : }
3641 :
3642 : /* Check that the region we're scheduling still has at most one
3643 : backedge. */
3644 : static void
3645 2757 : verify_backedges (void)
3646 : {
3647 2757 : if (pipelining_p)
3648 : {
3649 : int i, n = 0;
3650 : edge e;
3651 : edge_iterator ei;
3652 :
3653 18555 : for (i = 0; i < current_nr_blocks; i++)
3654 42541 : FOR_EACH_EDGE (e, ei, BASIC_BLOCK_FOR_FN (cfun, BB_TO_BLOCK (i))->succs)
3655 25591 : if (in_current_region_p (e->dest)
3656 25591 : && BLOCK_TO_BB (e->dest->index) < i)
3657 1391 : n++;
3658 :
3659 1605 : gcc_assert (n <= 1);
3660 : }
3661 2757 : }
3662 :
3663 :
3664 : /* Functions to work with control flow. */
3665 :
3666 : /* Recompute BLOCK_TO_BB and BB_FOR_BLOCK for current region so that blocks
3667 : are sorted in topological order (it might have been invalidated by
3668 : redirecting an edge). */
3669 : static void
3670 0 : sel_recompute_toporder (void)
3671 : {
3672 0 : int i, n, rgn;
3673 0 : int *postorder, n_blocks;
3674 :
3675 0 : postorder = XALLOCAVEC (int, n_basic_blocks_for_fn (cfun));
3676 0 : n_blocks = post_order_compute (postorder, false, false);
3677 :
3678 0 : rgn = CONTAINING_RGN (BB_TO_BLOCK (0));
3679 0 : for (n = 0, i = n_blocks - 1; i >= 0; i--)
3680 0 : if (CONTAINING_RGN (postorder[i]) == rgn)
3681 : {
3682 0 : BLOCK_TO_BB (postorder[i]) = n;
3683 0 : BB_TO_BLOCK (n) = postorder[i];
3684 0 : n++;
3685 : }
3686 :
3687 : /* Assert that we updated info for all blocks. We may miss some blocks if
3688 : this function is called when redirecting an edge made a block
3689 : unreachable, but that block is not deleted yet. */
3690 0 : gcc_assert (n == RGN_NR_BLOCKS (rgn));
3691 0 : }
3692 :
3693 : /* Tidy the possibly empty block BB. */
3694 : static bool
3695 8125 : maybe_tidy_empty_bb (basic_block bb)
3696 : {
3697 8125 : basic_block succ_bb, pred_bb, note_bb;
3698 8125 : vec<basic_block> dom_bbs;
3699 8125 : edge e;
3700 8125 : edge_iterator ei;
3701 8125 : bool rescan_p;
3702 :
3703 : /* Keep empty bb only if this block immediately precedes EXIT and
3704 : has incoming non-fallthrough edge, or it has no predecessors or
3705 : successors. Otherwise remove it. */
3706 8125 : if (!sel_bb_empty_p (bb)
3707 61 : || (single_succ_p (bb)
3708 61 : && single_succ (bb) == EXIT_BLOCK_PTR_FOR_FN (cfun)
3709 8066 : && (!single_pred_p (bb)
3710 1 : || !(single_pred_edge (bb)->flags & EDGE_FALLTHRU)))
3711 61 : || EDGE_COUNT (bb->preds) == 0
3712 8187 : || EDGE_COUNT (bb->succs) == 0)
3713 : return false;
3714 :
3715 : /* Do not attempt to redirect complex edges. */
3716 141 : FOR_EACH_EDGE (e, ei, bb->preds)
3717 81 : if (e->flags & EDGE_COMPLEX)
3718 : return false;
3719 81 : else if (e->flags & EDGE_FALLTHRU)
3720 : {
3721 50 : rtx note;
3722 : /* If prev bb ends with asm goto, see if any of the
3723 : ASM_OPERANDS_LABELs don't point to the fallthru
3724 : label. Do not attempt to redirect it in that case. */
3725 50 : if (JUMP_P (BB_END (e->src))
3726 50 : && (note = extract_asm_operands (PATTERN (BB_END (e->src)))))
3727 : {
3728 1 : int i, n = ASM_OPERANDS_LABEL_LENGTH (note);
3729 :
3730 1 : for (i = 0; i < n; ++i)
3731 1 : if (XEXP (ASM_OPERANDS_LABEL (note, i), 0) == BB_HEAD (bb))
3732 : return false;
3733 : }
3734 : }
3735 :
3736 60 : free_data_sets (bb);
3737 :
3738 : /* Do not delete BB if it has more than one successor.
3739 : That can occur when we moving a jump. */
3740 60 : if (!single_succ_p (bb))
3741 : {
3742 0 : gcc_assert (can_merge_blocks_p (bb->prev_bb, bb));
3743 0 : sel_merge_blocks (bb->prev_bb, bb);
3744 0 : return true;
3745 : }
3746 :
3747 60 : succ_bb = single_succ (bb);
3748 60 : rescan_p = true;
3749 60 : pred_bb = NULL;
3750 60 : dom_bbs.create (0);
3751 :
3752 : /* Save a pred/succ from the current region to attach the notes to. */
3753 60 : note_bb = NULL;
3754 60 : FOR_EACH_EDGE (e, ei, bb->preds)
3755 60 : if (in_current_region_p (e->src))
3756 : {
3757 60 : note_bb = e->src;
3758 60 : break;
3759 : }
3760 60 : if (note_bb == NULL)
3761 0 : note_bb = succ_bb;
3762 :
3763 : /* Redirect all non-fallthru edges to the next bb. */
3764 151 : while (rescan_p)
3765 : {
3766 91 : rescan_p = false;
3767 :
3768 150 : FOR_EACH_EDGE (e, ei, bb->preds)
3769 : {
3770 90 : pred_bb = e->src;
3771 :
3772 90 : if (!(e->flags & EDGE_FALLTHRU))
3773 : {
3774 : /* We cannot invalidate computed topological order by moving
3775 : the edge destination block (E->SUCC) along a fallthru edge.
3776 :
3777 : We will update dominators here only when we'll get
3778 : an unreachable block when redirecting, otherwise
3779 : sel_redirect_edge_and_branch will take care of it. */
3780 31 : if (e->dest != bb
3781 31 : && single_pred_p (e->dest))
3782 0 : dom_bbs.safe_push (e->dest);
3783 31 : sel_redirect_edge_and_branch (e, succ_bb);
3784 31 : rescan_p = true;
3785 31 : break;
3786 : }
3787 : /* If the edge is fallthru, but PRED_BB ends in a conditional jump
3788 : to BB (so there is no non-fallthru edge from PRED_BB to BB), we
3789 : still have to adjust it. */
3790 59 : else if (single_succ_p (pred_bb) && any_condjump_p (BB_END (pred_bb)))
3791 : {
3792 : /* If possible, try to remove the unneeded conditional jump. */
3793 0 : if (onlyjump_p (BB_END (pred_bb))
3794 0 : && INSN_SCHED_TIMES (BB_END (pred_bb)) == 0
3795 0 : && !IN_CURRENT_FENCE_P (BB_END (pred_bb)))
3796 : {
3797 0 : if (!sel_remove_insn (BB_END (pred_bb), false, false))
3798 0 : tidy_fallthru_edge (e);
3799 : }
3800 : else
3801 0 : sel_redirect_edge_and_branch (e, succ_bb);
3802 91 : rescan_p = true;
3803 : break;
3804 : }
3805 : }
3806 : }
3807 :
3808 60 : if (can_merge_blocks_p (bb->prev_bb, bb))
3809 48 : sel_merge_blocks (bb->prev_bb, bb);
3810 : else
3811 : {
3812 : /* This is a block without fallthru predecessor. Just delete it. */
3813 12 : gcc_assert (note_bb);
3814 12 : move_bb_info (note_bb, bb);
3815 12 : remove_empty_bb (bb, true);
3816 : }
3817 :
3818 60 : if (!dom_bbs.is_empty ())
3819 : {
3820 0 : dom_bbs.safe_push (succ_bb);
3821 0 : iterate_fix_dominators (CDI_DOMINATORS, dom_bbs, false);
3822 0 : dom_bbs.release ();
3823 : }
3824 :
3825 : return true;
3826 : }
3827 :
3828 : /* Tidy the control flow after we have removed original insn from
3829 : XBB. Return true if we have removed some blocks. When FULL_TIDYING
3830 : is true, also try to optimize control flow on non-empty blocks. */
3831 : bool
3832 7851 : tidy_control_flow (basic_block xbb, bool full_tidying)
3833 : {
3834 7851 : bool changed = true;
3835 7851 : insn_t first, last;
3836 :
3837 : /* First check whether XBB is empty. */
3838 7851 : changed = maybe_tidy_empty_bb (xbb);
3839 7851 : if (changed || !full_tidying)
3840 : return changed;
3841 :
3842 : /* Check if there is a unnecessary jump after insn left. */
3843 2757 : if (bb_has_removable_jump_to_p (xbb, xbb->next_bb)
3844 2 : && INSN_SCHED_TIMES (BB_END (xbb)) == 0
3845 2759 : && !IN_CURRENT_FENCE_P (BB_END (xbb)))
3846 : {
3847 : /* We used to call sel_remove_insn here that can trigger tidy_control_flow
3848 : before we fix up the fallthru edge. Correct that ordering by
3849 : explicitly doing the latter before the former. */
3850 2 : clear_expr (INSN_EXPR (BB_END (xbb)));
3851 2 : tidy_fallthru_edge (EDGE_SUCC (xbb, 0));
3852 2 : if (tidy_control_flow (xbb, false))
3853 : return true;
3854 : }
3855 :
3856 2757 : first = sel_bb_head (xbb);
3857 2757 : last = sel_bb_end (xbb);
3858 2757 : if (MAY_HAVE_DEBUG_INSNS)
3859 : {
3860 79 : if (first != last && DEBUG_INSN_P (first))
3861 59 : do
3862 59 : first = NEXT_INSN (first);
3863 59 : while (first != last && (DEBUG_INSN_P (first) || NOTE_P (first)));
3864 :
3865 79 : if (first != last && DEBUG_INSN_P (last))
3866 1 : do
3867 1 : last = PREV_INSN (last);
3868 1 : while (first != last && (DEBUG_INSN_P (last) || NOTE_P (last)));
3869 : }
3870 : /* Check if there is an unnecessary jump in previous basic block leading
3871 : to next basic block left after removing INSN from stream.
3872 : If it is so, remove that jump and redirect edge to current
3873 : basic block (where there was INSN before deletion). This way
3874 : when NOP will be deleted several instructions later with its
3875 : basic block we will not get a jump to next instruction, which
3876 : can be harmful. */
3877 2757 : if (first == last
3878 318 : && !sel_bb_empty_p (xbb)
3879 318 : && INSN_NOP_P (last)
3880 : /* Flow goes fallthru from current block to the next. */
3881 55 : && EDGE_COUNT (xbb->succs) == 1
3882 55 : && (EDGE_SUCC (xbb, 0)->flags & EDGE_FALLTHRU)
3883 : /* When successor is an EXIT block, it may not be the next block. */
3884 55 : && single_succ (xbb) != EXIT_BLOCK_PTR_FOR_FN (cfun)
3885 : /* And unconditional jump in previous basic block leads to
3886 : next basic block of XBB and this jump can be safely removed. */
3887 55 : && in_current_region_p (xbb->prev_bb)
3888 49 : && bb_has_removable_jump_to_p (xbb->prev_bb, xbb->next_bb)
3889 10 : && INSN_SCHED_TIMES (BB_END (xbb->prev_bb)) == 0
3890 : /* Also this jump is not at the scheduling boundary. */
3891 2767 : && !IN_CURRENT_FENCE_P (BB_END (xbb->prev_bb)))
3892 : {
3893 10 : bool recompute_toporder_p;
3894 : /* Clear data structures of jump - jump itself will be removed
3895 : by sel_redirect_edge_and_branch. */
3896 10 : clear_expr (INSN_EXPR (BB_END (xbb->prev_bb)));
3897 10 : recompute_toporder_p
3898 10 : = sel_redirect_edge_and_branch (EDGE_SUCC (xbb->prev_bb, 0), xbb);
3899 :
3900 10 : gcc_assert (EDGE_SUCC (xbb->prev_bb, 0)->flags & EDGE_FALLTHRU);
3901 :
3902 : /* We could have skipped some debug insns which did not get removed with the block,
3903 : and the seqnos could become incorrect. Fix them up here. */
3904 10 : if (MAY_HAVE_DEBUG_INSNS && (sel_bb_head (xbb) != first || sel_bb_end (xbb) != last))
3905 : {
3906 0 : if (!sel_bb_empty_p (xbb->prev_bb))
3907 : {
3908 0 : int prev_seqno = INSN_SEQNO (sel_bb_end (xbb->prev_bb));
3909 0 : if (prev_seqno > INSN_SEQNO (sel_bb_head (xbb)))
3910 0 : for (insn_t insn = sel_bb_head (xbb); insn != first; insn = NEXT_INSN (insn))
3911 0 : INSN_SEQNO (insn) = prev_seqno + 1;
3912 : }
3913 : }
3914 :
3915 : /* It can turn out that after removing unused jump, basic block
3916 : that contained that jump, becomes empty too. In such case
3917 : remove it too. */
3918 10 : if (sel_bb_empty_p (xbb->prev_bb))
3919 0 : changed = maybe_tidy_empty_bb (xbb->prev_bb);
3920 10 : if (recompute_toporder_p)
3921 0 : sel_recompute_toporder ();
3922 : }
3923 :
3924 : /* TODO: use separate flag for CFG checking. */
3925 2757 : if (flag_checking)
3926 : {
3927 2757 : verify_backedges ();
3928 2757 : verify_dominators (CDI_DOMINATORS);
3929 : }
3930 :
3931 : return changed;
3932 : }
3933 :
3934 : /* Purge meaningless empty blocks in the middle of a region. */
3935 : void
3936 733 : purge_empty_blocks (void)
3937 : {
3938 733 : int i;
3939 :
3940 : /* Do not attempt to delete the first basic block in the region. */
3941 1007 : for (i = 1; i < current_nr_blocks; )
3942 : {
3943 274 : basic_block b = BASIC_BLOCK_FOR_FN (cfun, BB_TO_BLOCK (i));
3944 :
3945 274 : if (maybe_tidy_empty_bb (b))
3946 5 : continue;
3947 :
3948 269 : i++;
3949 : }
3950 733 : }
3951 :
3952 : /* Rip-off INSN from the insn stream. When ONLY_DISCONNECT is true,
3953 : do not delete insn's data, because it will be later re-emitted.
3954 : Return true if we have removed some blocks afterwards. */
3955 : bool
3956 6971 : sel_remove_insn (insn_t insn, bool only_disconnect, bool full_tidying)
3957 : {
3958 6971 : basic_block bb = BLOCK_FOR_INSN (insn);
3959 :
3960 13942 : gcc_assert (INSN_IN_STREAM_P (insn));
3961 :
3962 6971 : if (DEBUG_INSN_P (insn) && BB_AV_SET_VALID_P (bb))
3963 : {
3964 43 : expr_t expr;
3965 43 : av_set_iterator i;
3966 :
3967 : /* When we remove a debug insn that is head of a BB, it remains
3968 : in the AV_SET of the block, but it shouldn't. */
3969 128 : FOR_EACH_EXPR_1 (expr, i, &BB_AV_SET (bb))
3970 85 : if (EXPR_INSN_RTX (expr) == insn)
3971 : {
3972 28 : av_set_iter_remove (&i);
3973 28 : break;
3974 : }
3975 : }
3976 :
3977 6971 : if (only_disconnect)
3978 4713 : remove_insn (insn);
3979 : else
3980 : {
3981 2258 : delete_insn (insn);
3982 2258 : clear_expr (INSN_EXPR (insn));
3983 : }
3984 :
3985 : /* It is necessary to NULL these fields in case we are going to re-insert
3986 : INSN into the insns stream, as will usually happen in the ONLY_DISCONNECT
3987 : case, but also for NOPs that we will return to the nop pool. */
3988 6971 : SET_PREV_INSN (insn) = NULL_RTX;
3989 6971 : SET_NEXT_INSN (insn) = NULL_RTX;
3990 6971 : set_block_for_insn (insn, NULL);
3991 :
3992 6971 : return tidy_control_flow (bb, full_tidying);
3993 : }
3994 :
3995 : /* Estimate number of the insns in BB. */
3996 : static int
3997 95 : sel_estimate_number_of_insns (basic_block bb)
3998 : {
3999 95 : int res = 0;
4000 95 : insn_t insn = NEXT_INSN (BB_HEAD (bb)), next_tail = NEXT_INSN (BB_END (bb));
4001 :
4002 871 : for (; insn != next_tail; insn = NEXT_INSN (insn))
4003 681 : if (NONDEBUG_INSN_P (insn))
4004 544 : res++;
4005 :
4006 95 : return res;
4007 : }
4008 :
4009 : /* We don't need separate luids for notes or labels. */
4010 : static int
4011 1496 : sel_luid_for_non_insn (rtx x)
4012 : {
4013 1496 : gcc_assert (NOTE_P (x) || LABEL_P (x));
4014 :
4015 1496 : return -1;
4016 : }
4017 :
4018 : /* Find the proper seqno for inserting at INSN by successors.
4019 : Return -1 if no successors with positive seqno exist. */
4020 : static int
4021 0 : get_seqno_by_succs (rtx_insn *insn)
4022 : {
4023 0 : basic_block bb = BLOCK_FOR_INSN (insn);
4024 0 : rtx_insn *tmp = insn, *end = BB_END (bb);
4025 0 : int seqno;
4026 0 : insn_t succ = NULL;
4027 0 : succ_iterator si;
4028 :
4029 0 : while (tmp != end)
4030 : {
4031 0 : tmp = NEXT_INSN (tmp);
4032 0 : if (INSN_P (tmp))
4033 0 : return INSN_SEQNO (tmp);
4034 : }
4035 :
4036 0 : seqno = INT_MAX;
4037 :
4038 0 : FOR_EACH_SUCC_1 (succ, si, end, SUCCS_NORMAL)
4039 0 : if (INSN_SEQNO (succ) > 0)
4040 0 : seqno = MIN (seqno, INSN_SEQNO (succ));
4041 :
4042 0 : if (seqno == INT_MAX)
4043 0 : return -1;
4044 :
4045 : return seqno;
4046 : }
4047 :
4048 : /* Compute seqno for INSN by its preds or succs. Use OLD_SEQNO to compute
4049 : seqno in corner cases. */
4050 : static int
4051 12 : get_seqno_for_a_jump (insn_t insn, int old_seqno)
4052 : {
4053 12 : int seqno;
4054 :
4055 12 : gcc_assert (INSN_SIMPLEJUMP_P (insn));
4056 :
4057 12 : if (!sel_bb_head_p (insn))
4058 11 : seqno = INSN_SEQNO (PREV_INSN (insn));
4059 : else
4060 : {
4061 1 : basic_block bb = BLOCK_FOR_INSN (insn);
4062 :
4063 1 : if (single_pred_p (bb)
4064 2 : && !in_current_region_p (single_pred (bb)))
4065 : {
4066 : /* We can have preds outside a region when splitting edges
4067 : for pipelining of an outer loop. Use succ instead.
4068 : There should be only one of them. */
4069 0 : insn_t succ = NULL;
4070 0 : succ_iterator si;
4071 0 : bool first = true;
4072 :
4073 0 : gcc_assert (flag_sel_sched_pipelining_outer_loops
4074 : && current_loop_nest);
4075 0 : FOR_EACH_SUCC_1 (succ, si, insn,
4076 : SUCCS_NORMAL | SUCCS_SKIP_TO_LOOP_EXITS)
4077 : {
4078 0 : gcc_assert (first);
4079 0 : first = false;
4080 : }
4081 :
4082 0 : gcc_assert (succ != NULL);
4083 0 : seqno = INSN_SEQNO (succ);
4084 : }
4085 : else
4086 : {
4087 1 : insn_t *preds;
4088 1 : int n;
4089 :
4090 2 : cfg_preds (BLOCK_FOR_INSN (insn), &preds, &n);
4091 :
4092 1 : gcc_assert (n > 0);
4093 : /* For one predecessor, use simple method. */
4094 1 : if (n == 1)
4095 1 : seqno = INSN_SEQNO (preds[0]);
4096 : else
4097 0 : seqno = get_seqno_by_preds (insn);
4098 :
4099 1 : free (preds);
4100 : }
4101 : }
4102 :
4103 : /* We were unable to find a good seqno among preds. */
4104 12 : if (seqno < 0)
4105 0 : seqno = get_seqno_by_succs (insn);
4106 :
4107 0 : if (seqno < 0)
4108 : {
4109 : /* The only case where this could be here legally is that the only
4110 : unscheduled insn was a conditional jump that got removed and turned
4111 : into this unconditional one. Initialize from the old seqno
4112 : of that jump passed down to here. */
4113 0 : seqno = old_seqno;
4114 : }
4115 :
4116 0 : gcc_assert (seqno >= 0);
4117 12 : return seqno;
4118 : }
4119 :
4120 : /* Find the proper seqno for inserting at INSN. Returns -1 if no predecessors
4121 : with positive seqno exist. */
4122 : int
4123 0 : get_seqno_by_preds (rtx_insn *insn)
4124 : {
4125 0 : basic_block bb = BLOCK_FOR_INSN (insn);
4126 0 : rtx_insn *tmp = insn, *head = BB_HEAD (bb);
4127 0 : insn_t *preds;
4128 0 : int n, i, seqno;
4129 :
4130 : /* Loop backwards from INSN to HEAD including both. */
4131 0 : while (1)
4132 : {
4133 0 : if (INSN_P (tmp))
4134 0 : return INSN_SEQNO (tmp);
4135 0 : if (tmp == head)
4136 : break;
4137 0 : tmp = PREV_INSN (tmp);
4138 : }
4139 :
4140 0 : cfg_preds (bb, &preds, &n);
4141 0 : for (i = 0, seqno = -1; i < n; i++)
4142 0 : seqno = MAX (seqno, INSN_SEQNO (preds[i]));
4143 :
4144 : return seqno;
4145 : }
4146 :
4147 :
4148 :
4149 : /* Extend pass-scope data structures for basic blocks. */
4150 : void
4151 1007 : sel_extend_global_bb_info (void)
4152 : {
4153 1007 : sel_global_bb_info.safe_grow_cleared (last_basic_block_for_fn (cfun), true);
4154 1007 : }
4155 :
4156 : /* Extend region-scope data structures for basic blocks. */
4157 : static void
4158 876 : extend_region_bb_info (void)
4159 : {
4160 876 : sel_region_bb_info.safe_grow_cleared (last_basic_block_for_fn (cfun), true);
4161 876 : }
4162 :
4163 : /* Extend all data structures to fit for all basic blocks. */
4164 : static void
4165 876 : extend_bb_info (void)
4166 : {
4167 804 : sel_extend_global_bb_info ();
4168 876 : extend_region_bb_info ();
4169 804 : }
4170 :
4171 : /* Finalize pass-scope data structures for basic blocks. */
4172 : void
4173 131 : sel_finish_global_bb_info (void)
4174 : {
4175 131 : sel_global_bb_info.release ();
4176 131 : }
4177 :
4178 : /* Finalize region-scope data structures for basic blocks. */
4179 : static void
4180 733 : finish_region_bb_info (void)
4181 : {
4182 0 : sel_region_bb_info.release ();
4183 0 : }
4184 :
4185 :
4186 : /* Data for each insn in current region. */
4187 : vec<sel_insn_data_def> s_i_d;
4188 :
4189 : /* Extend data structures for insns from current region. */
4190 : static void
4191 3162 : extend_insn_data (void)
4192 : {
4193 3162 : int reserve;
4194 :
4195 3162 : sched_extend_target ();
4196 3162 : sched_deps_init (false);
4197 :
4198 : /* Extend data structures for insns from current region. */
4199 3162 : reserve = (sched_max_luid + 1 - s_i_d.length ());
4200 4266 : if (reserve > 0 && ! s_i_d.space (reserve))
4201 : {
4202 1104 : int size;
4203 :
4204 1104 : if (sched_max_luid / 2 > 1024)
4205 0 : size = sched_max_luid + 1024;
4206 : else
4207 1104 : size = 3 * sched_max_luid / 2;
4208 :
4209 :
4210 1104 : s_i_d.safe_grow_cleared (size, true);
4211 : }
4212 3162 : }
4213 :
4214 : /* Finalize data structures for insns from current region. */
4215 : static void
4216 733 : finish_insns (void)
4217 : {
4218 733 : unsigned i;
4219 :
4220 : /* Clear here all dependence contexts that may have left from insns that were
4221 : removed during the scheduling. */
4222 9218 : for (i = 0; i < s_i_d.length (); i++)
4223 : {
4224 8485 : sel_insn_data_def *sid_entry = &s_i_d[i];
4225 :
4226 8485 : if (sid_entry->live)
4227 1115 : return_regset_to_pool (sid_entry->live);
4228 8485 : if (sid_entry->analyzed_deps)
4229 : {
4230 294 : BITMAP_FREE (sid_entry->analyzed_deps);
4231 294 : BITMAP_FREE (sid_entry->found_deps);
4232 294 : htab_delete (sid_entry->transformed_insns);
4233 294 : free_deps (&sid_entry->deps_context);
4234 : }
4235 8485 : if (EXPR_VINSN (&sid_entry->expr))
4236 : {
4237 0 : clear_expr (&sid_entry->expr);
4238 :
4239 : /* Also, clear CANT_MOVE bit here, because we really don't want it
4240 : to be passed to the next region. */
4241 0 : CANT_MOVE_BY_LUID (i) = 0;
4242 : }
4243 : }
4244 :
4245 733 : s_i_d.release ();
4246 733 : }
4247 :
4248 : /* A proxy to pass initialization data to init_insn (). */
4249 : static sel_insn_data_def _insn_init_ssid;
4250 : static sel_insn_data_t insn_init_ssid = &_insn_init_ssid;
4251 :
4252 : /* If true create a new vinsn. Otherwise use the one from EXPR. */
4253 : static bool insn_init_create_new_vinsn_p;
4254 :
4255 : /* Set all necessary data for initialization of the new insn[s]. */
4256 : static expr_t
4257 2417 : set_insn_init (expr_t expr, vinsn_t vi, int seqno)
4258 : {
4259 2417 : expr_t x = &insn_init_ssid->expr;
4260 :
4261 2417 : copy_expr_onside (x, expr);
4262 2417 : if (vi != NULL)
4263 : {
4264 2388 : insn_init_create_new_vinsn_p = false;
4265 2388 : change_vinsn_in_expr (x, vi);
4266 : }
4267 : else
4268 29 : insn_init_create_new_vinsn_p = true;
4269 :
4270 2417 : insn_init_ssid->seqno = seqno;
4271 2417 : return x;
4272 : }
4273 :
4274 : /* Init data for INSN. */
4275 : static void
4276 2417 : init_insn_data (insn_t insn)
4277 : {
4278 2417 : expr_t expr;
4279 2417 : sel_insn_data_t ssid = insn_init_ssid;
4280 :
4281 : /* The fields mentioned below are special and hence are not being
4282 : propagated to the new insns. */
4283 2417 : gcc_assert (!ssid->asm_p && ssid->sched_next == NULL
4284 : && !ssid->after_stall_p && ssid->sched_cycle == 0);
4285 2417 : gcc_assert (INSN_P (insn) && INSN_LUID (insn) > 0);
4286 :
4287 2417 : expr = INSN_EXPR (insn);
4288 2417 : copy_expr (expr, &ssid->expr);
4289 2417 : prepare_insn_expr (insn, ssid->seqno);
4290 :
4291 2417 : if (insn_init_create_new_vinsn_p)
4292 29 : change_vinsn_in_expr (expr, vinsn_create (insn, init_insn_force_unique_p));
4293 :
4294 2417 : if (first_time_insn_init (insn))
4295 1262 : init_first_time_insn_data (insn);
4296 2417 : }
4297 :
4298 : /* This is used to initialize spurious jumps generated by
4299 : sel_redirect_edge (). OLD_SEQNO is used for initializing seqnos
4300 : in corner cases within get_seqno_for_a_jump. */
4301 : static void
4302 12 : init_simplejump_data (insn_t insn, int old_seqno)
4303 : {
4304 12 : init_expr (INSN_EXPR (insn), vinsn_create (insn, false), 0,
4305 : REG_BR_PROB_BASE, 0, 0, 0, 0, 0, 0,
4306 12 : vNULL, true, false, false,
4307 : false, true);
4308 12 : INSN_SEQNO (insn) = get_seqno_for_a_jump (insn, old_seqno);
4309 12 : init_first_time_insn_data (insn);
4310 12 : }
4311 :
4312 : /* Perform deferred initialization of insns. This is used to process
4313 : a new jump that may be created by redirect_edge. OLD_SEQNO is used
4314 : for initializing simplejumps in init_simplejump_data. */
4315 : static void
4316 2429 : sel_init_new_insn (insn_t insn, int flags, int old_seqno)
4317 : {
4318 : /* We create data structures for bb when the first insn is emitted in it. */
4319 2429 : if (INSN_P (insn)
4320 4858 : && INSN_IN_STREAM_P (insn)
4321 4858 : && insn_is_the_only_one_in_bb_p (insn))
4322 : {
4323 72 : extend_bb_info ();
4324 72 : create_initial_data_sets (BLOCK_FOR_INSN (insn));
4325 : }
4326 :
4327 2429 : if (flags & INSN_INIT_TODO_LUID)
4328 : {
4329 1274 : sched_extend_luids ();
4330 1274 : sched_init_insn_luid (insn);
4331 : }
4332 :
4333 2429 : if (flags & INSN_INIT_TODO_SSID)
4334 : {
4335 2417 : extend_insn_data ();
4336 2417 : init_insn_data (insn);
4337 2417 : clear_expr (&insn_init_ssid->expr);
4338 : }
4339 :
4340 2429 : if (flags & INSN_INIT_TODO_SIMPLEJUMP)
4341 : {
4342 12 : extend_insn_data ();
4343 12 : init_simplejump_data (insn, old_seqno);
4344 : }
4345 :
4346 2429 : gcc_assert (CONTAINING_RGN (BLOCK_NUM (insn))
4347 : == CONTAINING_RGN (BB_TO_BLOCK (0)));
4348 2429 : }
4349 :
4350 :
4351 : /* Functions to init/finish work with lv sets. */
4352 :
4353 : /* Init BB_LV_SET of BB from DF_LR_IN set of BB. */
4354 : static void
4355 1104 : init_lv_set (basic_block bb)
4356 : {
4357 1104 : gcc_assert (!BB_LV_SET_VALID_P (bb));
4358 :
4359 1104 : BB_LV_SET (bb) = get_regset_from_pool ();
4360 2208 : COPY_REG_SET (BB_LV_SET (bb), DF_LR_IN (bb));
4361 1104 : BB_LV_SET_VALID_P (bb) = true;
4362 1104 : }
4363 :
4364 : /* Copy liveness information to BB from FROM_BB. */
4365 : static void
4366 0 : copy_lv_set_from (basic_block bb, basic_block from_bb)
4367 : {
4368 0 : gcc_assert (!BB_LV_SET_VALID_P (bb));
4369 :
4370 0 : COPY_REG_SET (BB_LV_SET (bb), BB_LV_SET (from_bb));
4371 0 : BB_LV_SET_VALID_P (bb) = true;
4372 0 : }
4373 :
4374 : /* Initialize lv set of all bb headers. */
4375 : void
4376 131 : init_lv_sets (void)
4377 : {
4378 131 : basic_block bb;
4379 :
4380 : /* Initialize of LV sets. */
4381 1104 : FOR_EACH_BB_FN (bb, cfun)
4382 973 : init_lv_set (bb);
4383 :
4384 : /* Don't forget EXIT_BLOCK. */
4385 131 : init_lv_set (EXIT_BLOCK_PTR_FOR_FN (cfun));
4386 131 : }
4387 :
4388 : /* Release lv set of HEAD. */
4389 : static void
4390 1231 : free_lv_set (basic_block bb)
4391 : {
4392 1231 : gcc_assert (BB_LV_SET (bb) != NULL);
4393 :
4394 1231 : return_regset_to_pool (BB_LV_SET (bb));
4395 1231 : BB_LV_SET (bb) = NULL;
4396 1231 : BB_LV_SET_VALID_P (bb) = false;
4397 1231 : }
4398 :
4399 : /* Finalize lv sets of all bb headers. */
4400 : void
4401 131 : free_lv_sets (void)
4402 : {
4403 131 : basic_block bb;
4404 :
4405 : /* Don't forget EXIT_BLOCK. */
4406 131 : free_lv_set (EXIT_BLOCK_PTR_FOR_FN (cfun));
4407 :
4408 : /* Free LV sets. */
4409 1098 : FOR_EACH_BB_FN (bb, cfun)
4410 967 : if (BB_LV_SET (bb))
4411 967 : free_lv_set (bb);
4412 131 : }
4413 :
4414 : /* Mark AV_SET for BB as invalid, so this set will be updated the next time
4415 : compute_av() processes BB. This function is called when creating new basic
4416 : blocks, as well as for blocks (either new or existing) where new jumps are
4417 : created when the control flow is being updated. */
4418 : static void
4419 1114 : invalidate_av_set (basic_block bb)
4420 : {
4421 1114 : BB_AV_LEVEL (bb) = -1;
4422 1114 : }
4423 :
4424 : /* Create initial data sets for BB (they will be invalid). */
4425 : static void
4426 136 : create_initial_data_sets (basic_block bb)
4427 : {
4428 136 : if (BB_LV_SET (bb))
4429 9 : BB_LV_SET_VALID_P (bb) = false;
4430 : else
4431 127 : BB_LV_SET (bb) = get_regset_from_pool ();
4432 136 : invalidate_av_set (bb);
4433 136 : }
4434 :
4435 : /* Free av set of BB. */
4436 : static void
4437 123 : free_av_set (basic_block bb)
4438 : {
4439 123 : av_set_clear (&BB_AV_SET (bb));
4440 123 : BB_AV_LEVEL (bb) = 0;
4441 123 : }
4442 :
4443 : /* Free data sets of BB. */
4444 : void
4445 123 : free_data_sets (basic_block bb)
4446 : {
4447 123 : free_lv_set (bb);
4448 123 : free_av_set (bb);
4449 123 : }
4450 :
4451 : /* Exchange data sets of TO and FROM. */
4452 : void
4453 134 : exchange_data_sets (basic_block to, basic_block from)
4454 : {
4455 : /* Exchange lv sets of TO and FROM. */
4456 134 : std::swap (BB_LV_SET (from), BB_LV_SET (to));
4457 134 : std::swap (BB_LV_SET_VALID_P (from), BB_LV_SET_VALID_P (to));
4458 :
4459 : /* Exchange av sets of TO and FROM. */
4460 134 : std::swap (BB_AV_SET (from), BB_AV_SET (to));
4461 134 : std::swap (BB_AV_LEVEL (from), BB_AV_LEVEL (to));
4462 134 : }
4463 :
4464 : /* Copy data sets of FROM to TO. */
4465 : void
4466 0 : copy_data_sets (basic_block to, basic_block from)
4467 : {
4468 0 : gcc_assert (!BB_LV_SET_VALID_P (to) && !BB_AV_SET_VALID_P (to));
4469 0 : gcc_assert (BB_AV_SET (to) == NULL);
4470 :
4471 0 : BB_AV_LEVEL (to) = BB_AV_LEVEL (from);
4472 0 : BB_LV_SET_VALID_P (to) = BB_LV_SET_VALID_P (from);
4473 :
4474 0 : if (BB_AV_SET_VALID_P (from))
4475 : {
4476 0 : BB_AV_SET (to) = av_set_copy (BB_AV_SET (from));
4477 : }
4478 0 : if (BB_LV_SET_VALID_P (from))
4479 : {
4480 0 : gcc_assert (BB_LV_SET (to) != NULL);
4481 0 : COPY_REG_SET (BB_LV_SET (to), BB_LV_SET (from));
4482 : }
4483 0 : }
4484 :
4485 : /* Return an av set for INSN, if any. */
4486 : av_set_t
4487 8404 : get_av_set (insn_t insn)
4488 : {
4489 8404 : av_set_t av_set;
4490 :
4491 8404 : gcc_assert (AV_SET_VALID_P (insn));
4492 :
4493 8404 : if (sel_bb_head_p (insn))
4494 8404 : av_set = BB_AV_SET (BLOCK_FOR_INSN (insn));
4495 : else
4496 : av_set = NULL;
4497 :
4498 8404 : return av_set;
4499 : }
4500 :
4501 : /* Implementation of AV_LEVEL () macro. Return AV_LEVEL () of INSN. */
4502 : int
4503 107357 : get_av_level (insn_t insn)
4504 : {
4505 107357 : int av_level;
4506 :
4507 107357 : gcc_assert (INSN_P (insn));
4508 :
4509 107357 : if (sel_bb_head_p (insn))
4510 46939 : av_level = BB_AV_LEVEL (BLOCK_FOR_INSN (insn));
4511 : else
4512 60418 : av_level = INSN_WS_LEVEL (insn);
4513 :
4514 107357 : return av_level;
4515 : }
4516 :
4517 :
4518 :
4519 : /* Variables to work with control-flow graph. */
4520 :
4521 : /* The basic block that already has been processed by the sched_data_update (),
4522 : but hasn't been in sel_add_bb () yet. */
4523 : static vec<basic_block> last_added_blocks;
4524 :
4525 : /* A pool for allocating successor infos. */
4526 : static struct
4527 : {
4528 : /* A stack for saving succs_info structures. */
4529 : struct succs_info *stack;
4530 :
4531 : /* Its size. */
4532 : int size;
4533 :
4534 : /* Top of the stack. */
4535 : int top;
4536 :
4537 : /* Maximal value of the top. */
4538 : int max_top;
4539 : } succs_info_pool;
4540 :
4541 : /* Functions to work with control-flow graph. */
4542 :
4543 : /* Return basic block note of BB. */
4544 : rtx_insn *
4545 363968 : sel_bb_head (basic_block bb)
4546 : {
4547 363968 : rtx_insn *head;
4548 :
4549 363968 : if (bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
4550 : {
4551 2234 : gcc_assert (exit_insn != NULL_RTX);
4552 : head = exit_insn;
4553 : }
4554 : else
4555 : {
4556 361734 : rtx_note *note = bb_note (bb);
4557 361734 : head = next_nonnote_insn (note);
4558 :
4559 361734 : if (head && (BARRIER_P (head) || BLOCK_FOR_INSN (head) != bb))
4560 : head = NULL;
4561 : }
4562 :
4563 363968 : return head;
4564 : }
4565 :
4566 : /* Return true if INSN is a basic block header. */
4567 : bool
4568 191243 : sel_bb_head_p (insn_t insn)
4569 : {
4570 191243 : return sel_bb_head (BLOCK_FOR_INSN (insn)) == insn;
4571 : }
4572 :
4573 : /* Return last insn of BB. */
4574 : rtx_insn *
4575 64812 : sel_bb_end (basic_block bb)
4576 : {
4577 64812 : if (sel_bb_empty_p (bb))
4578 : return NULL;
4579 :
4580 64812 : gcc_assert (bb != EXIT_BLOCK_PTR_FOR_FN (cfun));
4581 :
4582 64812 : return BB_END (bb);
4583 : }
4584 :
4585 : /* Return true if INSN is the last insn in its basic block. */
4586 : bool
4587 23105 : sel_bb_end_p (insn_t insn)
4588 : {
4589 23105 : return insn == sel_bb_end (BLOCK_FOR_INSN (insn));
4590 : }
4591 :
4592 : /* Return true if BB consist of single NOTE_INSN_BASIC_BLOCK. */
4593 : bool
4594 107534 : sel_bb_empty_p (basic_block bb)
4595 : {
4596 107534 : return sel_bb_head (bb) == NULL;
4597 : }
4598 :
4599 : /* True when BB belongs to the current scheduling region. */
4600 : bool
4601 97011 : in_current_region_p (basic_block bb)
4602 : {
4603 97011 : if (bb->index < NUM_FIXED_BLOCKS)
4604 : return false;
4605 :
4606 95910 : return CONTAINING_RGN (bb->index) == CONTAINING_RGN (BB_TO_BLOCK (0));
4607 : }
4608 :
4609 : /* Return the block which is a fallthru bb of a conditional jump JUMP. */
4610 : basic_block
4611 771 : fallthru_bb_of_jump (const rtx_insn *jump)
4612 : {
4613 771 : if (!JUMP_P (jump))
4614 : return NULL;
4615 :
4616 754 : if (!any_condjump_p (jump))
4617 : return NULL;
4618 :
4619 : /* A basic block that ends with a conditional jump may still have one successor
4620 : (and be followed by a barrier), we are not interested. */
4621 504 : if (single_succ_p (BLOCK_FOR_INSN (jump)))
4622 : return NULL;
4623 :
4624 504 : return FALLTHRU_EDGE (BLOCK_FOR_INSN (jump))->dest;
4625 : }
4626 :
4627 : /* Remove all notes from BB. */
4628 : static void
4629 1071 : init_bb (basic_block bb)
4630 : {
4631 1071 : remove_notes (bb_note (bb), BB_END (bb));
4632 1071 : BB_NOTE_LIST (bb) = note_list;
4633 1071 : }
4634 :
4635 : void
4636 804 : sel_init_bbs (bb_vec_t bbs)
4637 : {
4638 804 : const struct sched_scan_info_def ssi =
4639 : {
4640 : extend_bb_info, /* extend_bb */
4641 : init_bb, /* init_bb */
4642 : NULL, /* extend_insn */
4643 : NULL /* init_insn */
4644 : };
4645 :
4646 804 : sched_scan (&ssi, bbs);
4647 804 : }
4648 :
4649 : /* Restore notes for the whole region. */
4650 : static void
4651 733 : sel_restore_notes (void)
4652 : {
4653 733 : int bb;
4654 733 : insn_t insn;
4655 :
4656 1744 : for (bb = 0; bb < current_nr_blocks; bb++)
4657 : {
4658 1011 : basic_block first, last;
4659 :
4660 1011 : first = EBB_FIRST_BB (bb);
4661 1011 : last = EBB_LAST_BB (bb)->next_bb;
4662 :
4663 1011 : do
4664 : {
4665 1011 : note_list = BB_NOTE_LIST (first);
4666 1011 : restore_other_notes (NULL, first);
4667 1011 : BB_NOTE_LIST (first) = NULL;
4668 :
4669 7753 : FOR_BB_INSNS (first, insn)
4670 6742 : if (NONDEBUG_INSN_P (insn))
4671 4467 : reemit_notes (insn);
4672 :
4673 1011 : first = first->next_bb;
4674 : }
4675 1011 : while (first != last);
4676 : }
4677 733 : }
4678 :
4679 : /* Free per-bb data structures. */
4680 : void
4681 733 : sel_finish_bbs (void)
4682 : {
4683 733 : sel_restore_notes ();
4684 :
4685 : /* Remove current loop preheader from this loop. */
4686 733 : if (current_loop_nest)
4687 55 : sel_remove_loop_preheader ();
4688 :
4689 733 : finish_region_bb_info ();
4690 733 : }
4691 :
4692 : /* Return true if INSN has a single successor of type FLAGS. */
4693 : bool
4694 1443 : sel_insn_has_single_succ_p (insn_t insn, int flags)
4695 : {
4696 1443 : insn_t succ;
4697 1443 : succ_iterator si;
4698 1443 : bool first_p = true;
4699 :
4700 2886 : FOR_EACH_SUCC_1 (succ, si, insn, flags)
4701 : {
4702 1446 : if (first_p)
4703 1443 : first_p = false;
4704 : else
4705 : return false;
4706 : }
4707 :
4708 : return true;
4709 : }
4710 :
4711 : /* Allocate successor's info. */
4712 : static struct succs_info *
4713 8222 : alloc_succs_info (void)
4714 : {
4715 8222 : if (succs_info_pool.top == succs_info_pool.max_top)
4716 : {
4717 293 : int i;
4718 :
4719 293 : if (++succs_info_pool.max_top >= succs_info_pool.size)
4720 0 : gcc_unreachable ();
4721 :
4722 293 : i = ++succs_info_pool.top;
4723 293 : succs_info_pool.stack[i].succs_ok.create (10);
4724 293 : succs_info_pool.stack[i].succs_other.create (10);
4725 293 : succs_info_pool.stack[i].probs_ok.create (10);
4726 : }
4727 : else
4728 7929 : succs_info_pool.top++;
4729 :
4730 8222 : return &succs_info_pool.stack[succs_info_pool.top];
4731 : }
4732 :
4733 : /* Free successor's info. */
4734 : void
4735 8222 : free_succs_info (struct succs_info * sinfo)
4736 : {
4737 8222 : gcc_assert (succs_info_pool.top >= 0
4738 : && &succs_info_pool.stack[succs_info_pool.top] == sinfo);
4739 8222 : succs_info_pool.top--;
4740 :
4741 : /* Clear stale info. */
4742 16444 : sinfo->succs_ok.block_remove (0, sinfo->succs_ok.length ());
4743 16444 : sinfo->succs_other.block_remove (0, sinfo->succs_other.length ());
4744 16444 : sinfo->probs_ok.block_remove (0, sinfo->probs_ok.length ());
4745 8222 : sinfo->all_prob = 0;
4746 8222 : sinfo->succs_ok_n = 0;
4747 8222 : sinfo->all_succs_n = 0;
4748 8222 : }
4749 :
4750 : /* Compute successor info for INSN. FLAGS are the flags passed
4751 : to the FOR_EACH_SUCC_1 iterator. */
4752 : struct succs_info *
4753 8222 : compute_succs_info (insn_t insn, short flags)
4754 : {
4755 8222 : succ_iterator si;
4756 8222 : insn_t succ;
4757 8222 : struct succs_info *sinfo = alloc_succs_info ();
4758 :
4759 : /* Traverse *all* successors and decide what to do with each. */
4760 21193 : FOR_EACH_SUCC_1 (succ, si, insn, SUCCS_ALL)
4761 : {
4762 : /* FIXME: this doesn't work for skipping to loop exits, as we don't
4763 : perform code motion through inner loops. */
4764 12971 : short current_flags = si.current_flags & ~SUCCS_SKIP_TO_LOOP_EXITS;
4765 :
4766 12971 : if (current_flags & flags)
4767 : {
4768 6089 : sinfo->succs_ok.safe_push (succ);
4769 12178 : sinfo->probs_ok.safe_push (
4770 : /* FIXME: Improve calculation when skipping
4771 : inner loop to exits. */
4772 6089 : si.bb_end
4773 11564 : ? (si.e1->probability.initialized_p ()
4774 6089 : ? si.e1->probability.to_reg_br_prob_base ()
4775 : : 0)
4776 : : REG_BR_PROB_BASE);
4777 6089 : sinfo->succs_ok_n++;
4778 : }
4779 : else
4780 6882 : sinfo->succs_other.safe_push (succ);
4781 :
4782 : /* Compute all_prob. */
4783 12971 : if (!si.bb_end)
4784 0 : sinfo->all_prob = REG_BR_PROB_BASE;
4785 12971 : else if (si.e1->probability.initialized_p ())
4786 12143 : sinfo->all_prob += si.e1->probability.to_reg_br_prob_base ();
4787 :
4788 12971 : sinfo->all_succs_n++;
4789 : }
4790 :
4791 8222 : return sinfo;
4792 : }
4793 :
4794 : /* Return the predecessors of BB in PREDS and their number in N.
4795 : Empty blocks are skipped. SIZE is used to allocate PREDS. */
4796 : static void
4797 1 : cfg_preds_1 (basic_block bb, insn_t **preds, int *n, int *size)
4798 : {
4799 1 : edge e;
4800 1 : edge_iterator ei;
4801 :
4802 1 : gcc_assert (BLOCK_TO_BB (bb->index) != 0);
4803 :
4804 2 : FOR_EACH_EDGE (e, ei, bb->preds)
4805 : {
4806 1 : basic_block pred_bb = e->src;
4807 1 : insn_t bb_end = BB_END (pred_bb);
4808 :
4809 1 : if (!in_current_region_p (pred_bb))
4810 : {
4811 0 : gcc_assert (flag_sel_sched_pipelining_outer_loops
4812 : && current_loop_nest);
4813 0 : continue;
4814 : }
4815 :
4816 1 : if (sel_bb_empty_p (pred_bb))
4817 0 : cfg_preds_1 (pred_bb, preds, n, size);
4818 : else
4819 : {
4820 1 : if (*n == *size)
4821 1 : *preds = XRESIZEVEC (insn_t, *preds,
4822 : (*size = 2 * *size + 1));
4823 1 : (*preds)[(*n)++] = bb_end;
4824 : }
4825 : }
4826 :
4827 1 : gcc_assert (*n != 0
4828 : || (flag_sel_sched_pipelining_outer_loops
4829 : && current_loop_nest));
4830 1 : }
4831 :
4832 : /* Find all predecessors of BB and record them in PREDS and their number
4833 : in N. Empty blocks are skipped, and only normal (forward in-region)
4834 : edges are processed. */
4835 : static void
4836 1 : cfg_preds (basic_block bb, insn_t **preds, int *n)
4837 : {
4838 1 : int size = 0;
4839 :
4840 1 : *preds = NULL;
4841 1 : *n = 0;
4842 1 : cfg_preds_1 (bb, preds, n, &size);
4843 0 : }
4844 :
4845 : /* Returns true if we are moving INSN through join point. */
4846 : bool
4847 1749 : sel_num_cfg_preds_gt_1 (insn_t insn)
4848 : {
4849 1749 : basic_block bb;
4850 :
4851 1749 : if (!sel_bb_head_p (insn) || INSN_BB (insn) == 0)
4852 : return false;
4853 :
4854 : bb = BLOCK_FOR_INSN (insn);
4855 :
4856 936 : while (1)
4857 : {
4858 936 : if (EDGE_COUNT (bb->preds) > 1)
4859 : return true;
4860 :
4861 526 : gcc_assert (EDGE_PRED (bb, 0)->dest == bb);
4862 526 : bb = EDGE_PRED (bb, 0)->src;
4863 :
4864 526 : if (!sel_bb_empty_p (bb))
4865 : break;
4866 : }
4867 :
4868 : return false;
4869 : }
4870 :
4871 : /* Returns true when BB should be the end of an ebb. Adapted from the
4872 : code in sched-ebb.cc. */
4873 : bool
4874 1100 : bb_ends_ebb_p (basic_block bb)
4875 : {
4876 1100 : basic_block next_bb = bb_next_bb (bb);
4877 1100 : edge e;
4878 :
4879 1100 : if (next_bb == EXIT_BLOCK_PTR_FOR_FN (cfun)
4880 987 : || bitmap_bit_p (forced_ebb_heads, next_bb->index)
4881 2000 : || (LABEL_P (BB_HEAD (next_bb))
4882 : /* NB: LABEL_NUSES () is not maintained outside of jump.cc.
4883 : Work around that. */
4884 362 : && !single_pred_p (next_bb)))
4885 538 : return true;
4886 :
4887 562 : if (!in_current_region_p (next_bb))
4888 : return true;
4889 :
4890 368 : e = find_fallthru_edge (bb->succs);
4891 368 : if (e)
4892 : {
4893 366 : gcc_assert (e->dest == next_bb);
4894 :
4895 : return false;
4896 : }
4897 :
4898 : return true;
4899 : }
4900 :
4901 : /* Returns true when INSN and SUCC are in the same EBB, given that SUCC is a
4902 : successor of INSN. */
4903 : bool
4904 253 : in_same_ebb_p (insn_t insn, insn_t succ)
4905 : {
4906 253 : basic_block ptr = BLOCK_FOR_INSN (insn);
4907 :
4908 719 : for (;;)
4909 : {
4910 486 : if (ptr == BLOCK_FOR_INSN (succ))
4911 : return true;
4912 :
4913 341 : if (bb_ends_ebb_p (ptr))
4914 : return false;
4915 :
4916 233 : ptr = bb_next_bb (ptr);
4917 : }
4918 : }
4919 :
4920 : /* Recomputes the reverse topological order for the function and
4921 : saves it in REV_TOP_ORDER_INDEX. REV_TOP_ORDER_INDEX_LEN is also
4922 : modified appropriately. */
4923 : static void
4924 44 : recompute_rev_top_order (void)
4925 : {
4926 44 : int *postorder;
4927 44 : int n_blocks, i;
4928 :
4929 44 : if (!rev_top_order_index
4930 1 : || rev_top_order_index_len < last_basic_block_for_fn (cfun))
4931 : {
4932 43 : rev_top_order_index_len = last_basic_block_for_fn (cfun);
4933 43 : rev_top_order_index = XRESIZEVEC (int, rev_top_order_index,
4934 : rev_top_order_index_len);
4935 : }
4936 :
4937 44 : postorder = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
4938 :
4939 44 : n_blocks = post_order_compute (postorder, true, false);
4940 44 : gcc_assert (n_basic_blocks_for_fn (cfun) == n_blocks);
4941 :
4942 : /* Build reverse function: for each basic block with BB->INDEX == K
4943 : rev_top_order_index[K] is it's reverse topological sort number. */
4944 658 : for (i = 0; i < n_blocks; i++)
4945 : {
4946 614 : gcc_assert (postorder[i] < rev_top_order_index_len);
4947 614 : rev_top_order_index[postorder[i]] = i;
4948 : }
4949 :
4950 44 : free (postorder);
4951 44 : }
4952 :
4953 : /* Clear all flags from insns in BB that could spoil its rescheduling. */
4954 : void
4955 136 : clear_outdated_rtx_info (basic_block bb)
4956 : {
4957 136 : rtx_insn *insn;
4958 :
4959 1133 : FOR_BB_INSNS (bb, insn)
4960 997 : if (INSN_P (insn))
4961 : {
4962 790 : SCHED_GROUP_P (insn) = 0;
4963 790 : INSN_AFTER_STALL_P (insn) = 0;
4964 790 : INSN_SCHED_TIMES (insn) = 0;
4965 790 : EXPR_PRIORITY_ADJ (INSN_EXPR (insn)) = 0;
4966 :
4967 : /* We cannot use the changed caches, as previously we could ignore
4968 : the LHS dependence due to enabled renaming and transform
4969 : the expression, and currently we'll be unable to do this. */
4970 790 : htab_empty (INSN_TRANSFORMED_INSNS (insn));
4971 : }
4972 136 : }
4973 :
4974 : /* Add BB_NOTE to the pool of available basic block notes. */
4975 : static void
4976 115 : return_bb_to_pool (basic_block bb)
4977 : {
4978 115 : rtx_note *note = bb_note (bb);
4979 :
4980 115 : gcc_assert (NOTE_BASIC_BLOCK (note) == bb
4981 : && bb->aux == NULL);
4982 :
4983 : /* It turns out that current cfg infrastructure does not support
4984 : reuse of basic blocks. Don't bother for now. */
4985 : /*bb_note_pool.safe_push (note);*/
4986 115 : }
4987 :
4988 : /* Get a bb_note from pool or return NULL_RTX if pool is empty. */
4989 : static rtx_note *
4990 64 : get_bb_note_from_pool (void)
4991 : {
4992 64 : if (bb_note_pool.is_empty ())
4993 : return NULL;
4994 : else
4995 : {
4996 0 : rtx_note *note = bb_note_pool.pop ();
4997 :
4998 0 : SET_PREV_INSN (note) = NULL_RTX;
4999 0 : SET_NEXT_INSN (note) = NULL_RTX;
5000 :
5001 0 : return note;
5002 : }
5003 : }
5004 :
5005 : /* Free bb_note_pool. */
5006 : void
5007 131 : free_bb_note_pool (void)
5008 : {
5009 131 : bb_note_pool.release ();
5010 131 : }
5011 :
5012 : /* Setup scheduler pool and successor structure. */
5013 : void
5014 131 : alloc_sched_pools (void)
5015 : {
5016 131 : int succs_size;
5017 :
5018 131 : succs_size = MAX_WS + 1;
5019 131 : succs_info_pool.stack = XCNEWVEC (struct succs_info, succs_size);
5020 131 : succs_info_pool.size = succs_size;
5021 131 : succs_info_pool.top = -1;
5022 131 : succs_info_pool.max_top = -1;
5023 131 : }
5024 :
5025 : /* Free the pools. */
5026 : void
5027 131 : free_sched_pools (void)
5028 : {
5029 131 : int i;
5030 :
5031 131 : sched_lists_pool.release ();
5032 131 : gcc_assert (succs_info_pool.top == -1);
5033 424 : for (i = 0; i <= succs_info_pool.max_top; i++)
5034 : {
5035 293 : succs_info_pool.stack[i].succs_ok.release ();
5036 293 : succs_info_pool.stack[i].succs_other.release ();
5037 293 : succs_info_pool.stack[i].probs_ok.release ();
5038 : }
5039 131 : free (succs_info_pool.stack);
5040 131 : }
5041 :
5042 :
5043 : /* Returns a position in RGN where BB can be inserted retaining
5044 : topological order. */
5045 : static int
5046 71 : find_place_to_insert_bb (basic_block bb, int rgn)
5047 : {
5048 71 : bool has_preds_outside_rgn = false;
5049 71 : edge e;
5050 71 : edge_iterator ei;
5051 :
5052 : /* Find whether we have preds outside the region. */
5053 143 : FOR_EACH_EDGE (e, ei, bb->preds)
5054 72 : if (!in_current_region_p (e->src))
5055 : {
5056 : has_preds_outside_rgn = true;
5057 : break;
5058 : }
5059 :
5060 : /* Recompute the top order -- needed when we have > 1 pred
5061 : and in case we don't have preds outside. */
5062 71 : if (flag_sel_sched_pipelining_outer_loops
5063 71 : && (has_preds_outside_rgn || EDGE_COUNT (bb->preds) > 1))
5064 : {
5065 1 : int i, bbi = bb->index, cur_bbi;
5066 :
5067 1 : recompute_rev_top_order ();
5068 2 : for (i = RGN_NR_BLOCKS (rgn) - 1; i >= 0; i--)
5069 : {
5070 2 : cur_bbi = BB_TO_BLOCK (i);
5071 2 : if (rev_top_order_index[bbi]
5072 2 : < rev_top_order_index[cur_bbi])
5073 : break;
5074 : }
5075 :
5076 : /* We skipped the right block, so we increase i. We accommodate
5077 : it for increasing by step later, so we decrease i. */
5078 : return (i + 1) - 1;
5079 : }
5080 70 : else if (has_preds_outside_rgn)
5081 : {
5082 : /* This is the case when we generate an extra empty block
5083 : to serve as region head during pipelining. */
5084 0 : e = EDGE_SUCC (bb, 0);
5085 0 : gcc_assert (EDGE_COUNT (bb->succs) == 1
5086 : && in_current_region_p (EDGE_SUCC (bb, 0)->dest)
5087 : && (BLOCK_TO_BB (e->dest->index) == 0));
5088 : return -1;
5089 : }
5090 :
5091 : /* We don't have preds outside the region. We should have
5092 : the only pred, because the multiple preds case comes from
5093 : the pipelining of outer loops, and that is handled above.
5094 : Just take the bbi of this single pred. */
5095 70 : if (EDGE_COUNT (bb->succs) > 0)
5096 : {
5097 70 : int pred_bbi;
5098 :
5099 70 : gcc_assert (EDGE_COUNT (bb->preds) == 1);
5100 :
5101 70 : pred_bbi = EDGE_PRED (bb, 0)->src->index;
5102 70 : return BLOCK_TO_BB (pred_bbi);
5103 : }
5104 : else
5105 : /* BB has no successors. It is safe to put it in the end. */
5106 0 : return current_nr_blocks - 1;
5107 : }
5108 :
5109 : /* Deletes an empty basic block freeing its data. */
5110 : static void
5111 22 : delete_and_free_basic_block (basic_block bb)
5112 : {
5113 22 : gcc_assert (sel_bb_empty_p (bb));
5114 :
5115 22 : if (BB_LV_SET (bb))
5116 10 : free_lv_set (bb);
5117 :
5118 22 : bitmap_clear_bit (blocks_to_reschedule, bb->index);
5119 :
5120 : /* Can't assert av_set properties because we use sel_aremove_bb
5121 : when removing loop preheader from the region. At the point of
5122 : removing the preheader we already have deallocated sel_region_bb_info. */
5123 22 : gcc_assert (BB_LV_SET (bb) == NULL
5124 : && !BB_LV_SET_VALID_P (bb)
5125 : && BB_AV_LEVEL (bb) == 0
5126 : && BB_AV_SET (bb) == NULL);
5127 :
5128 22 : delete_basic_block (bb);
5129 22 : }
5130 :
5131 : /* Add BB to the current region and update the region data. */
5132 : static void
5133 71 : add_block_to_current_region (basic_block bb)
5134 : {
5135 71 : int i, pos, bbi = -2, rgn;
5136 :
5137 71 : rgn = CONTAINING_RGN (BB_TO_BLOCK (0));
5138 71 : bbi = find_place_to_insert_bb (bb, rgn);
5139 71 : bbi += 1;
5140 71 : pos = RGN_BLOCKS (rgn) + bbi;
5141 :
5142 71 : gcc_assert (RGN_HAS_REAL_EBB (rgn) == 0
5143 : && ebb_head[bbi] == pos);
5144 :
5145 : /* Make a place for the new block. */
5146 71 : extend_regions ();
5147 :
5148 459 : for (i = RGN_BLOCKS (rgn + 1) - 1; i >= pos; i--)
5149 388 : BLOCK_TO_BB (rgn_bb_table[i])++;
5150 :
5151 71 : memmove (rgn_bb_table + pos + 1,
5152 71 : rgn_bb_table + pos,
5153 71 : (RGN_BLOCKS (nr_regions) - pos) * sizeof (*rgn_bb_table));
5154 :
5155 : /* Initialize data for BB. */
5156 71 : rgn_bb_table[pos] = bb->index;
5157 71 : BLOCK_TO_BB (bb->index) = bbi;
5158 71 : CONTAINING_RGN (bb->index) = rgn;
5159 :
5160 71 : RGN_NR_BLOCKS (rgn)++;
5161 :
5162 419 : for (i = rgn + 1; i <= nr_regions; i++)
5163 348 : RGN_BLOCKS (i)++;
5164 71 : }
5165 :
5166 : /* Remove BB from the current region and update the region data. */
5167 : static void
5168 115 : remove_bb_from_region (basic_block bb)
5169 : {
5170 115 : int i, pos, bbi = -2, rgn;
5171 :
5172 115 : rgn = CONTAINING_RGN (BB_TO_BLOCK (0));
5173 115 : bbi = BLOCK_TO_BB (bb->index);
5174 115 : pos = RGN_BLOCKS (rgn) + bbi;
5175 :
5176 115 : gcc_assert (RGN_HAS_REAL_EBB (rgn) == 0
5177 : && ebb_head[bbi] == pos);
5178 :
5179 857 : for (i = RGN_BLOCKS (rgn + 1) - 1; i >= pos; i--)
5180 742 : BLOCK_TO_BB (rgn_bb_table[i])--;
5181 :
5182 115 : memmove (rgn_bb_table + pos,
5183 115 : rgn_bb_table + pos + 1,
5184 115 : (RGN_BLOCKS (nr_regions) - pos) * sizeof (*rgn_bb_table));
5185 :
5186 115 : RGN_NR_BLOCKS (rgn)--;
5187 788 : for (i = rgn + 1; i <= nr_regions; i++)
5188 673 : RGN_BLOCKS (i)--;
5189 115 : }
5190 :
5191 : /* Add BB to the current region and update all data. If BB is NULL, add all
5192 : blocks from last_added_blocks vector. */
5193 : static void
5194 71 : sel_add_bb (basic_block bb)
5195 : {
5196 : /* Extend luids so that new notes will receive zero luids. */
5197 71 : sched_extend_luids ();
5198 71 : sched_init_bbs ();
5199 71 : sel_init_bbs (last_added_blocks);
5200 :
5201 : /* When bb is passed explicitly, the vector should contain
5202 : the only element that equals to bb; otherwise, the vector
5203 : should not be NULL. */
5204 71 : gcc_assert (last_added_blocks.exists ());
5205 :
5206 71 : if (bb != NULL)
5207 : {
5208 142 : gcc_assert (last_added_blocks.length () == 1
5209 : && last_added_blocks[0] == bb);
5210 71 : add_block_to_current_region (bb);
5211 :
5212 : /* We associate creating/deleting data sets with the first insn
5213 : appearing / disappearing in the bb. */
5214 71 : if (!sel_bb_empty_p (bb) && BB_LV_SET (bb) == NULL)
5215 64 : create_initial_data_sets (bb);
5216 :
5217 71 : last_added_blocks.release ();
5218 : }
5219 : else
5220 : /* BB is NULL - process LAST_ADDED_BLOCKS instead. */
5221 : {
5222 : int i;
5223 : basic_block temp_bb = NULL;
5224 :
5225 0 : for (i = 0;
5226 0 : last_added_blocks.iterate (i, &bb); i++)
5227 : {
5228 0 : add_block_to_current_region (bb);
5229 0 : temp_bb = bb;
5230 : }
5231 :
5232 : /* We need to fetch at least one bb so we know the region
5233 : to update. */
5234 0 : gcc_assert (temp_bb != NULL);
5235 0 : bb = temp_bb;
5236 :
5237 0 : last_added_blocks.release ();
5238 : }
5239 :
5240 71 : rgn_setup_region (CONTAINING_RGN (bb->index));
5241 71 : }
5242 :
5243 : /* Remove BB from the current region and update all data.
5244 : If REMOVE_FROM_CFG_PBB is true, also remove the block cfom cfg. */
5245 : static void
5246 115 : sel_remove_bb (basic_block bb, bool remove_from_cfg_p)
5247 : {
5248 115 : unsigned idx = bb->index;
5249 :
5250 115 : gcc_assert (bb != NULL && BB_NOTE_LIST (bb) == NULL_RTX);
5251 :
5252 115 : remove_bb_from_region (bb);
5253 115 : return_bb_to_pool (bb);
5254 115 : bitmap_clear_bit (blocks_to_reschedule, idx);
5255 :
5256 115 : if (remove_from_cfg_p)
5257 : {
5258 12 : basic_block succ = single_succ (bb);
5259 12 : delete_and_free_basic_block (bb);
5260 12 : set_immediate_dominator (CDI_DOMINATORS, succ,
5261 : recompute_dominator (CDI_DOMINATORS, succ));
5262 : }
5263 :
5264 115 : rgn_setup_region (CONTAINING_RGN (idx));
5265 115 : }
5266 :
5267 : /* Concatenate info of EMPTY_BB to info of MERGE_BB. */
5268 : static void
5269 60 : move_bb_info (basic_block merge_bb, basic_block empty_bb)
5270 : {
5271 60 : if (in_current_region_p (merge_bb))
5272 60 : concat_note_lists (BB_NOTE_LIST (empty_bb),
5273 60 : &BB_NOTE_LIST (merge_bb));
5274 60 : BB_NOTE_LIST (empty_bb) = NULL;
5275 :
5276 60 : }
5277 :
5278 : /* Remove EMPTY_BB. If REMOVE_FROM_CFG_P is false, remove EMPTY_BB from
5279 : region, but keep it in CFG. */
5280 : static void
5281 60 : remove_empty_bb (basic_block empty_bb, bool remove_from_cfg_p)
5282 : {
5283 : /* The block should contain just a note or a label.
5284 : We try to check whether it is unused below. */
5285 60 : gcc_assert (BB_HEAD (empty_bb) == BB_END (empty_bb)
5286 : || LABEL_P (BB_HEAD (empty_bb)));
5287 :
5288 : /* If basic block has predecessors or successors, redirect them. */
5289 60 : if (remove_from_cfg_p
5290 60 : && (EDGE_COUNT (empty_bb->preds) > 0
5291 11 : || EDGE_COUNT (empty_bb->succs) > 0))
5292 : {
5293 12 : basic_block pred;
5294 12 : basic_block succ;
5295 :
5296 : /* We need to init PRED and SUCC before redirecting edges. */
5297 12 : if (EDGE_COUNT (empty_bb->preds) > 0)
5298 : {
5299 1 : edge e;
5300 :
5301 1 : gcc_assert (EDGE_COUNT (empty_bb->preds) == 1);
5302 :
5303 1 : e = EDGE_PRED (empty_bb, 0);
5304 1 : gcc_assert (e->src == empty_bb->prev_bb
5305 : && (e->flags & EDGE_FALLTHRU));
5306 :
5307 : pred = empty_bb->prev_bb;
5308 : }
5309 : else
5310 : pred = NULL;
5311 :
5312 12 : if (EDGE_COUNT (empty_bb->succs) > 0)
5313 : {
5314 : /* We do not check fallthruness here as above, because
5315 : after removing a jump the edge may actually be not fallthru. */
5316 12 : gcc_assert (EDGE_COUNT (empty_bb->succs) == 1);
5317 12 : succ = EDGE_SUCC (empty_bb, 0)->dest;
5318 : }
5319 : else
5320 : succ = NULL;
5321 :
5322 12 : if (EDGE_COUNT (empty_bb->preds) > 0 && succ != NULL)
5323 : {
5324 1 : edge e = EDGE_PRED (empty_bb, 0);
5325 :
5326 1 : if (e->flags & EDGE_FALLTHRU)
5327 1 : redirect_edge_succ_nodup (e, succ);
5328 : else
5329 0 : sel_redirect_edge_and_branch (EDGE_PRED (empty_bb, 0), succ);
5330 : }
5331 :
5332 12 : if (EDGE_COUNT (empty_bb->succs) > 0 && pred != NULL)
5333 : {
5334 1 : edge e = EDGE_SUCC (empty_bb, 0);
5335 :
5336 1 : if (find_edge (pred, e->dest) == NULL)
5337 0 : redirect_edge_pred (e, pred);
5338 : }
5339 : }
5340 :
5341 : /* Finish removing. */
5342 60 : sel_remove_bb (empty_bb, remove_from_cfg_p);
5343 60 : }
5344 :
5345 : /* An implementation of create_basic_block hook, which additionally updates
5346 : per-bb data structures. */
5347 : static basic_block
5348 64 : sel_create_basic_block (void *headp, void *endp, basic_block after)
5349 : {
5350 64 : basic_block new_bb;
5351 64 : rtx_note *new_bb_note;
5352 :
5353 64 : gcc_assert (flag_sel_sched_pipelining_outer_loops
5354 : || !last_added_blocks.exists ());
5355 :
5356 64 : new_bb_note = get_bb_note_from_pool ();
5357 :
5358 64 : if (new_bb_note == NULL_RTX)
5359 64 : new_bb = orig_cfg_hooks->create_basic_block (headp, endp, after);
5360 : else
5361 : {
5362 0 : new_bb = create_basic_block_structure ((rtx_insn *) headp,
5363 : (rtx_insn *) endp,
5364 : new_bb_note, after);
5365 0 : new_bb->aux = NULL;
5366 : }
5367 :
5368 64 : last_added_blocks.safe_push (new_bb);
5369 :
5370 64 : return new_bb;
5371 : }
5372 :
5373 : /* Implement sched_init_only_bb (). */
5374 : static void
5375 0 : sel_init_only_bb (basic_block bb, basic_block after)
5376 : {
5377 0 : gcc_assert (after == NULL);
5378 :
5379 0 : extend_regions ();
5380 0 : rgn_make_new_region_out_of_new_block (bb);
5381 0 : }
5382 :
5383 : /* Update the latch when we've splitted or merged it from FROM block to TO.
5384 : This should be checked for all outer loops, too. */
5385 : static void
5386 111 : change_loops_latches (basic_block from, basic_block to)
5387 : {
5388 111 : gcc_assert (from != to);
5389 :
5390 111 : if (current_loop_nest)
5391 : {
5392 : class loop *loop;
5393 :
5394 321 : for (loop = current_loop_nest; loop; loop = loop_outer (loop))
5395 214 : if (considered_for_pipelining_p (loop) && loop->latch == from)
5396 : {
5397 0 : gcc_assert (loop == current_loop_nest);
5398 0 : loop->latch = to;
5399 0 : gcc_assert (loop_latch_edge (loop));
5400 : }
5401 : }
5402 111 : }
5403 :
5404 : /* Splits BB on two basic blocks, adding it to the region and extending
5405 : per-bb data structures. Returns the newly created bb. */
5406 : static basic_block
5407 63 : sel_split_block (basic_block bb, rtx after)
5408 : {
5409 63 : basic_block new_bb;
5410 63 : insn_t insn;
5411 :
5412 63 : new_bb = sched_split_block_1 (bb, after);
5413 63 : sel_add_bb (new_bb);
5414 :
5415 : /* This should be called after sel_add_bb, because this uses
5416 : CONTAINING_RGN for the new block, which is not yet initialized.
5417 : FIXME: this function may be a no-op now. */
5418 63 : change_loops_latches (bb, new_bb);
5419 :
5420 : /* Update ORIG_BB_INDEX for insns moved into the new block. */
5421 456 : FOR_BB_INSNS (new_bb, insn)
5422 393 : if (INSN_P (insn))
5423 330 : EXPR_ORIG_BB_INDEX (INSN_EXPR (insn)) = new_bb->index;
5424 :
5425 63 : if (sel_bb_empty_p (bb))
5426 : {
5427 63 : gcc_assert (!sel_bb_empty_p (new_bb));
5428 :
5429 : /* NEW_BB has data sets that need to be updated and BB holds
5430 : data sets that should be removed. Exchange these data sets
5431 : so that we won't lose BB's valid data sets. */
5432 63 : exchange_data_sets (new_bb, bb);
5433 63 : free_data_sets (bb);
5434 : }
5435 :
5436 63 : if (!sel_bb_empty_p (new_bb)
5437 63 : && bitmap_bit_p (blocks_to_reschedule, bb->index))
5438 31 : bitmap_set_bit (blocks_to_reschedule, new_bb->index);
5439 :
5440 63 : return new_bb;
5441 : }
5442 :
5443 : /* If BB ends with a jump insn whose ID is bigger then PREV_MAX_UID, return it.
5444 : Otherwise returns NULL. */
5445 : static rtx_insn *
5446 64 : check_for_new_jump (basic_block bb, int prev_max_uid)
5447 : {
5448 64 : rtx_insn *end;
5449 :
5450 64 : end = sel_bb_end (bb);
5451 64 : if (end && INSN_UID (end) >= prev_max_uid)
5452 12 : return end;
5453 : return NULL;
5454 : }
5455 :
5456 : /* Look for a new jump either in FROM_BB block or in newly created JUMP_BB block.
5457 : New means having UID at least equal to PREV_MAX_UID. */
5458 : static rtx_insn *
5459 104 : find_new_jump (basic_block from, basic_block jump_bb, int prev_max_uid)
5460 : {
5461 104 : rtx_insn *jump;
5462 :
5463 : /* Return immediately if no new insns were emitted. */
5464 104 : if (get_max_uid () == prev_max_uid)
5465 : return NULL;
5466 :
5467 : /* Now check both blocks for new jumps. It will ever be only one. */
5468 63 : if ((jump = check_for_new_jump (from, prev_max_uid)))
5469 : return jump;
5470 :
5471 52 : if (jump_bb != NULL
5472 52 : && (jump = check_for_new_jump (jump_bb, prev_max_uid)))
5473 : return jump;
5474 : return NULL;
5475 : }
5476 :
5477 : /* Splits E and adds the newly created basic block to the current region.
5478 : Returns this basic block. */
5479 : basic_block
5480 0 : sel_split_edge (edge e)
5481 : {
5482 0 : basic_block new_bb, src, other_bb = NULL;
5483 0 : int prev_max_uid;
5484 0 : rtx_insn *jump;
5485 :
5486 0 : src = e->src;
5487 0 : prev_max_uid = get_max_uid ();
5488 0 : new_bb = split_edge (e);
5489 :
5490 0 : if (flag_sel_sched_pipelining_outer_loops
5491 0 : && current_loop_nest)
5492 : {
5493 : int i;
5494 : basic_block bb;
5495 :
5496 : /* Some of the basic blocks might not have been added to the loop.
5497 : Add them here, until this is fixed in force_fallthru. */
5498 0 : for (i = 0;
5499 0 : last_added_blocks.iterate (i, &bb); i++)
5500 0 : if (!bb->loop_father)
5501 : {
5502 0 : add_bb_to_loop (bb, e->dest->loop_father);
5503 :
5504 0 : gcc_assert (!other_bb && (new_bb->index != bb->index));
5505 : other_bb = bb;
5506 : }
5507 : }
5508 :
5509 : /* Add all last_added_blocks to the region. */
5510 0 : sel_add_bb (NULL);
5511 :
5512 0 : jump = find_new_jump (src, new_bb, prev_max_uid);
5513 0 : if (jump)
5514 0 : sel_init_new_insn (jump, INSN_INIT_TODO_LUID | INSN_INIT_TODO_SIMPLEJUMP);
5515 :
5516 : /* Put the correct lv set on this block. */
5517 0 : if (other_bb && !sel_bb_empty_p (other_bb))
5518 0 : compute_live (sel_bb_head (other_bb));
5519 :
5520 0 : return new_bb;
5521 : }
5522 :
5523 : /* Implement sched_create_empty_bb (). */
5524 : static basic_block
5525 0 : sel_create_empty_bb (basic_block after)
5526 : {
5527 0 : basic_block new_bb;
5528 :
5529 0 : new_bb = sched_create_empty_bb_1 (after);
5530 :
5531 : /* We'll explicitly initialize NEW_BB via sel_init_only_bb () a bit
5532 : later. */
5533 0 : gcc_assert (last_added_blocks.length () == 1
5534 : && last_added_blocks[0] == new_bb);
5535 :
5536 0 : last_added_blocks.release ();
5537 0 : return new_bb;
5538 : }
5539 :
5540 : /* Implement sched_create_recovery_block. ORIG_INSN is where block
5541 : will be splitted to insert a check. */
5542 : basic_block
5543 0 : sel_create_recovery_block (insn_t orig_insn)
5544 : {
5545 0 : basic_block first_bb, second_bb, recovery_block;
5546 0 : basic_block before_recovery = NULL;
5547 0 : rtx_insn *jump;
5548 :
5549 0 : first_bb = BLOCK_FOR_INSN (orig_insn);
5550 0 : if (sel_bb_end_p (orig_insn))
5551 : {
5552 : /* Avoid introducing an empty block while splitting. */
5553 0 : gcc_assert (single_succ_p (first_bb));
5554 0 : second_bb = single_succ (first_bb);
5555 : }
5556 : else
5557 0 : second_bb = sched_split_block (first_bb, orig_insn);
5558 :
5559 0 : recovery_block = sched_create_recovery_block (&before_recovery);
5560 0 : if (before_recovery)
5561 0 : copy_lv_set_from (before_recovery, EXIT_BLOCK_PTR_FOR_FN (cfun));
5562 :
5563 0 : gcc_assert (sel_bb_empty_p (recovery_block));
5564 0 : sched_create_recovery_edges (first_bb, recovery_block, second_bb);
5565 0 : if (current_loops != NULL)
5566 0 : add_bb_to_loop (recovery_block, first_bb->loop_father);
5567 :
5568 0 : sel_add_bb (recovery_block);
5569 :
5570 0 : jump = BB_END (recovery_block);
5571 0 : gcc_assert (sel_bb_head (recovery_block) == jump);
5572 0 : sel_init_new_insn (jump, INSN_INIT_TODO_LUID | INSN_INIT_TODO_SIMPLEJUMP);
5573 :
5574 0 : return recovery_block;
5575 : }
5576 :
5577 : /* Merge basic block B into basic block A. */
5578 : static void
5579 48 : sel_merge_blocks (basic_block a, basic_block b)
5580 : {
5581 48 : gcc_assert (sel_bb_empty_p (b)
5582 : && EDGE_COUNT (b->preds) == 1
5583 : && EDGE_PRED (b, 0)->src == b->prev_bb);
5584 :
5585 48 : move_bb_info (b->prev_bb, b);
5586 48 : remove_empty_bb (b, false);
5587 48 : merge_blocks (a, b);
5588 48 : change_loops_latches (b, a);
5589 48 : }
5590 :
5591 : /* A wrapper for redirect_edge_and_branch_force, which also initializes
5592 : data structures for possibly created bb and insns. */
5593 : void
5594 12 : sel_redirect_edge_and_branch_force (edge e, basic_block to)
5595 : {
5596 12 : basic_block jump_bb, src, orig_dest = e->dest;
5597 12 : int prev_max_uid;
5598 12 : rtx_insn *jump;
5599 12 : int old_seqno = -1;
5600 :
5601 : /* This function is now used only for bookkeeping code creation, where
5602 : we'll never get the single pred of orig_dest block and thus will not
5603 : hit unreachable blocks when updating dominator info. */
5604 24 : gcc_assert (!sel_bb_empty_p (e->src)
5605 : && !single_pred_p (orig_dest));
5606 12 : src = e->src;
5607 12 : prev_max_uid = get_max_uid ();
5608 : /* Compute and pass old_seqno down to sel_init_new_insn only for the case
5609 : when the conditional jump being redirected may become unconditional. */
5610 12 : if (any_condjump_p (BB_END (src))
5611 12 : && INSN_SEQNO (BB_END (src)) >= 0)
5612 : old_seqno = INSN_SEQNO (BB_END (src));
5613 :
5614 12 : jump_bb = redirect_edge_and_branch_force (e, to);
5615 12 : if (jump_bb != NULL)
5616 1 : sel_add_bb (jump_bb);
5617 :
5618 : /* This function could not be used to spoil the loop structure by now,
5619 : thus we don't care to update anything. But check it to be sure. */
5620 12 : if (current_loop_nest
5621 11 : && pipelining_p)
5622 11 : gcc_assert (loop_latch_edge (current_loop_nest));
5623 :
5624 12 : jump = find_new_jump (src, jump_bb, prev_max_uid);
5625 12 : if (jump)
5626 12 : sel_init_new_insn (jump, INSN_INIT_TODO_LUID | INSN_INIT_TODO_SIMPLEJUMP,
5627 : old_seqno);
5628 12 : set_immediate_dominator (CDI_DOMINATORS, to,
5629 : recompute_dominator (CDI_DOMINATORS, to));
5630 12 : set_immediate_dominator (CDI_DOMINATORS, orig_dest,
5631 : recompute_dominator (CDI_DOMINATORS, orig_dest));
5632 12 : if (jump && sel_bb_head_p (jump))
5633 1 : compute_live (jump);
5634 12 : }
5635 :
5636 : /* A wrapper for redirect_edge_and_branch. Return TRUE if blocks connected by
5637 : redirected edge are in reverse topological order. */
5638 : bool
5639 92 : sel_redirect_edge_and_branch (edge e, basic_block to)
5640 : {
5641 92 : bool latch_edge_p;
5642 92 : basic_block src, orig_dest = e->dest;
5643 92 : int prev_max_uid;
5644 92 : rtx_insn *jump;
5645 92 : edge redirected;
5646 92 : bool recompute_toporder_p = false;
5647 92 : bool maybe_unreachable = single_pred_p (orig_dest);
5648 92 : int old_seqno = -1;
5649 :
5650 184 : latch_edge_p = (pipelining_p
5651 86 : && current_loop_nest
5652 178 : && e == loop_latch_edge (current_loop_nest));
5653 :
5654 92 : src = e->src;
5655 92 : prev_max_uid = get_max_uid ();
5656 :
5657 : /* Compute and pass old_seqno down to sel_init_new_insn only for the case
5658 : when the conditional jump being redirected may become unconditional. */
5659 92 : if (any_condjump_p (BB_END (src))
5660 92 : && INSN_SEQNO (BB_END (src)) >= 0)
5661 : old_seqno = INSN_SEQNO (BB_END (src));
5662 :
5663 92 : redirected = redirect_edge_and_branch (e, to);
5664 :
5665 92 : gcc_assert (redirected && !last_added_blocks.exists ());
5666 :
5667 : /* When we've redirected a latch edge, update the header. */
5668 92 : if (latch_edge_p)
5669 : {
5670 0 : current_loop_nest->header = to;
5671 0 : gcc_assert (loop_latch_edge (current_loop_nest));
5672 : }
5673 :
5674 : /* In rare situations, the topological relation between the blocks connected
5675 : by the redirected edge can change (see PR42245 for an example). Update
5676 : block_to_bb/bb_to_block. */
5677 92 : if (CONTAINING_RGN (e->src->index) == CONTAINING_RGN (to->index)
5678 88 : && BLOCK_TO_BB (e->src->index) > BLOCK_TO_BB (to->index))
5679 92 : recompute_toporder_p = true;
5680 :
5681 92 : jump = find_new_jump (src, NULL, prev_max_uid);
5682 92 : if (jump)
5683 0 : sel_init_new_insn (jump, INSN_INIT_TODO_LUID | INSN_INIT_TODO_SIMPLEJUMP, old_seqno);
5684 :
5685 : /* Only update dominator info when we don't have unreachable blocks.
5686 : Otherwise we'll update in maybe_tidy_empty_bb. */
5687 92 : if (!maybe_unreachable)
5688 : {
5689 81 : set_immediate_dominator (CDI_DOMINATORS, to,
5690 : recompute_dominator (CDI_DOMINATORS, to));
5691 81 : set_immediate_dominator (CDI_DOMINATORS, orig_dest,
5692 : recompute_dominator (CDI_DOMINATORS, orig_dest));
5693 : }
5694 92 : if (jump && sel_bb_head_p (jump))
5695 0 : compute_live (jump);
5696 92 : return recompute_toporder_p;
5697 : }
5698 :
5699 : /* This variable holds the cfg hooks used by the selective scheduler. */
5700 : static struct cfg_hooks sel_cfg_hooks;
5701 :
5702 : /* Register sel-sched cfg hooks. */
5703 : void
5704 733 : sel_register_cfg_hooks (void)
5705 : {
5706 733 : sched_split_block = sel_split_block;
5707 :
5708 733 : orig_cfg_hooks = get_cfg_hooks ();
5709 733 : sel_cfg_hooks = *orig_cfg_hooks;
5710 :
5711 733 : sel_cfg_hooks.create_basic_block = sel_create_basic_block;
5712 :
5713 733 : set_cfg_hooks (&sel_cfg_hooks);
5714 :
5715 733 : sched_init_only_bb = sel_init_only_bb;
5716 733 : sched_split_block = sel_split_block;
5717 733 : sched_create_empty_bb = sel_create_empty_bb;
5718 733 : }
5719 :
5720 : /* Unregister sel-sched cfg hooks. */
5721 : void
5722 733 : sel_unregister_cfg_hooks (void)
5723 : {
5724 733 : sched_create_empty_bb = NULL;
5725 733 : sched_split_block = NULL;
5726 733 : sched_init_only_bb = NULL;
5727 :
5728 733 : set_cfg_hooks (orig_cfg_hooks);
5729 733 : }
5730 :
5731 :
5732 : /* Emit an insn rtx based on PATTERN. If a jump insn is wanted,
5733 : LABEL is where this jump should be directed. */
5734 : rtx_insn *
5735 714 : create_insn_rtx_from_pattern (rtx pattern, rtx label)
5736 : {
5737 714 : rtx_insn *insn_rtx;
5738 :
5739 714 : gcc_assert (!INSN_P (pattern));
5740 :
5741 714 : start_sequence ();
5742 :
5743 714 : if (label == NULL_RTX)
5744 710 : insn_rtx = emit_insn (pattern);
5745 4 : else if (DEBUG_INSN_P (label))
5746 4 : insn_rtx = emit_debug_insn (pattern);
5747 : else
5748 : {
5749 0 : insn_rtx = emit_jump_insn (pattern);
5750 0 : JUMP_LABEL (insn_rtx) = label;
5751 0 : ++LABEL_NUSES (label);
5752 : }
5753 :
5754 714 : end_sequence ();
5755 :
5756 714 : sched_extend_luids ();
5757 714 : sched_extend_target ();
5758 714 : sched_deps_init (false);
5759 :
5760 : /* Initialize INSN_CODE now. */
5761 714 : recog_memoized (insn_rtx);
5762 714 : return insn_rtx;
5763 : }
5764 :
5765 : /* Create a new vinsn for INSN_RTX. FORCE_UNIQUE_P is true when the vinsn
5766 : must not be clonable. */
5767 : vinsn_t
5768 661 : create_vinsn_from_insn_rtx (rtx_insn *insn_rtx, bool force_unique_p)
5769 : {
5770 1322 : gcc_assert (INSN_P (insn_rtx) && !INSN_IN_STREAM_P (insn_rtx));
5771 :
5772 : /* If VINSN_TYPE is not USE, retain its uniqueness. */
5773 661 : return vinsn_create (insn_rtx, force_unique_p);
5774 : }
5775 :
5776 : /* Create a copy of INSN_RTX. */
5777 : rtx_insn *
5778 475 : create_copy_of_insn_rtx (rtx insn_rtx)
5779 : {
5780 475 : rtx_insn *res;
5781 475 : rtx link;
5782 :
5783 475 : if (DEBUG_INSN_P (insn_rtx))
5784 4 : return create_insn_rtx_from_pattern (copy_rtx (PATTERN (insn_rtx)),
5785 4 : insn_rtx);
5786 :
5787 471 : gcc_assert (NONJUMP_INSN_P (insn_rtx));
5788 :
5789 471 : res = create_insn_rtx_from_pattern (copy_rtx (PATTERN (insn_rtx)),
5790 : NULL_RTX);
5791 :
5792 : /* Locate the end of existing REG_NOTES in NEW_RTX. */
5793 471 : rtx *ptail = ®_NOTES (res);
5794 471 : while (*ptail != NULL_RTX)
5795 0 : ptail = &XEXP (*ptail, 1);
5796 :
5797 : /* Copy all REG_NOTES except REG_EQUAL/REG_EQUIV and REG_LABEL_OPERAND
5798 : since mark_jump_label will make them. REG_LABEL_TARGETs are created
5799 : there too, but are supposed to be sticky, so we copy them. */
5800 827 : for (link = REG_NOTES (insn_rtx); link; link = XEXP (link, 1))
5801 356 : if (REG_NOTE_KIND (link) != REG_LABEL_OPERAND
5802 : && REG_NOTE_KIND (link) != REG_EQUAL
5803 : && REG_NOTE_KIND (link) != REG_EQUIV)
5804 : {
5805 346 : *ptail = duplicate_reg_note (link);
5806 346 : ptail = &XEXP (*ptail, 1);
5807 : }
5808 :
5809 : return res;
5810 : }
5811 :
5812 : /* Change vinsn field of EXPR to hold NEW_VINSN. */
5813 : void
5814 3199 : change_vinsn_in_expr (expr_t expr, vinsn_t new_vinsn)
5815 : {
5816 3199 : vinsn_detach (EXPR_VINSN (expr));
5817 :
5818 3199 : EXPR_VINSN (expr) = new_vinsn;
5819 3199 : vinsn_attach (new_vinsn);
5820 3199 : }
5821 :
5822 : /* Helpers for global init. */
5823 : /* This structure is used to be able to call existing bundling mechanism
5824 : and calculate insn priorities. */
5825 : static struct haifa_sched_info sched_sel_haifa_sched_info =
5826 : {
5827 : NULL, /* init_ready_list */
5828 : NULL, /* can_schedule_ready_p */
5829 : NULL, /* schedule_more_p */
5830 : NULL, /* new_ready */
5831 : NULL, /* rgn_rank */
5832 : sel_print_insn, /* rgn_print_insn */
5833 : contributes_to_priority,
5834 : NULL, /* insn_finishes_block_p */
5835 :
5836 : NULL, NULL,
5837 : NULL, NULL,
5838 : 0, 0,
5839 :
5840 : NULL, /* add_remove_insn */
5841 : NULL, /* begin_schedule_ready */
5842 : NULL, /* begin_move_insn */
5843 : NULL, /* advance_target_bb */
5844 :
5845 : NULL,
5846 : NULL,
5847 :
5848 : SEL_SCHED | NEW_BBS
5849 : };
5850 :
5851 : /* Setup special insns used in the scheduler. */
5852 : void
5853 131 : setup_nop_and_exit_insns (void)
5854 : {
5855 131 : gcc_assert (nop_pattern == NULL_RTX
5856 : && exit_insn == NULL_RTX);
5857 :
5858 131 : nop_pattern = constm1_rtx;
5859 :
5860 131 : start_sequence ();
5861 131 : emit_insn (nop_pattern);
5862 131 : exit_insn = end_sequence ();
5863 131 : set_block_for_insn (exit_insn, EXIT_BLOCK_PTR_FOR_FN (cfun));
5864 131 : }
5865 :
5866 : /* Free special insns used in the scheduler. */
5867 : void
5868 131 : free_nop_and_exit_insns (void)
5869 : {
5870 131 : exit_insn = NULL;
5871 131 : nop_pattern = NULL_RTX;
5872 131 : }
5873 :
5874 : /* Setup a special vinsn used in new insns initialization. */
5875 : void
5876 733 : setup_nop_vinsn (void)
5877 : {
5878 733 : nop_vinsn = vinsn_create (exit_insn, false);
5879 733 : vinsn_attach (nop_vinsn);
5880 733 : }
5881 :
5882 : /* Free a special vinsn used in new insns initialization. */
5883 : void
5884 733 : free_nop_vinsn (void)
5885 : {
5886 733 : gcc_assert (VINSN_COUNT (nop_vinsn) == 1);
5887 733 : vinsn_detach (nop_vinsn);
5888 733 : nop_vinsn = NULL;
5889 733 : }
5890 :
5891 : /* Call a set_sched_flags hook. */
5892 : void
5893 1597 : sel_set_sched_flags (void)
5894 : {
5895 : /* ??? This means that set_sched_flags were called, and we decided to
5896 : support speculation. However, set_sched_flags also modifies flags
5897 : on current_sched_info, doing this only at global init. And we
5898 : sometimes change c_s_i later. So put the correct flags again. */
5899 1597 : if (spec_info && targetm.sched.set_sched_flags)
5900 0 : targetm.sched.set_sched_flags (spec_info);
5901 1597 : }
5902 :
5903 : /* Setup pointers to global sched info structures. */
5904 : void
5905 864 : sel_setup_sched_infos (void)
5906 : {
5907 864 : rgn_setup_common_sched_info ();
5908 :
5909 864 : memcpy (&sel_common_sched_info, common_sched_info,
5910 : sizeof (sel_common_sched_info));
5911 :
5912 864 : sel_common_sched_info.fix_recovery_cfg = NULL;
5913 864 : sel_common_sched_info.add_block = NULL;
5914 864 : sel_common_sched_info.estimate_number_of_insns
5915 864 : = sel_estimate_number_of_insns;
5916 864 : sel_common_sched_info.luid_for_non_insn = sel_luid_for_non_insn;
5917 864 : sel_common_sched_info.sched_pass_id = SCHED_SEL_PASS;
5918 :
5919 864 : common_sched_info = &sel_common_sched_info;
5920 :
5921 864 : current_sched_info = &sched_sel_haifa_sched_info;
5922 1728 : current_sched_info->sched_max_insns_priority =
5923 864 : get_rgn_sched_max_insns_priority ();
5924 :
5925 864 : sel_set_sched_flags ();
5926 864 : }
5927 :
5928 :
5929 : /* Adds basic block BB to region RGN at the position *BB_ORD_INDEX,
5930 : *BB_ORD_INDEX after that is increased. */
5931 : static void
5932 300 : sel_add_block_to_region (basic_block bb, int *bb_ord_index, int rgn)
5933 : {
5934 300 : RGN_NR_BLOCKS (rgn) += 1;
5935 300 : RGN_DONT_CALC_DEPS (rgn) = 0;
5936 300 : RGN_HAS_REAL_EBB (rgn) = 0;
5937 300 : CONTAINING_RGN (bb->index) = rgn;
5938 300 : BLOCK_TO_BB (bb->index) = *bb_ord_index;
5939 300 : rgn_bb_table[RGN_BLOCKS (rgn) + *bb_ord_index] = bb->index;
5940 300 : (*bb_ord_index)++;
5941 :
5942 : /* FIXME: it is true only when not scheduling ebbs. */
5943 300 : RGN_BLOCKS (rgn + 1) = RGN_BLOCKS (rgn) + RGN_NR_BLOCKS (rgn);
5944 300 : }
5945 :
5946 : /* Functions to support pipelining of outer loops. */
5947 :
5948 : /* Creates a new empty region and returns it's number. */
5949 : static int
5950 93 : sel_create_new_region (void)
5951 : {
5952 93 : int new_rgn_number = nr_regions;
5953 :
5954 93 : RGN_NR_BLOCKS (new_rgn_number) = 0;
5955 :
5956 : /* FIXME: This will work only when EBBs are not created. */
5957 93 : if (new_rgn_number != 0)
5958 55 : RGN_BLOCKS (new_rgn_number) = RGN_BLOCKS (new_rgn_number - 1) +
5959 55 : RGN_NR_BLOCKS (new_rgn_number - 1);
5960 : else
5961 38 : RGN_BLOCKS (new_rgn_number) = 0;
5962 :
5963 : /* Set the blocks of the next region so the other functions may
5964 : calculate the number of blocks in the region. */
5965 93 : RGN_BLOCKS (new_rgn_number + 1) = RGN_BLOCKS (new_rgn_number) +
5966 : RGN_NR_BLOCKS (new_rgn_number);
5967 :
5968 93 : nr_regions++;
5969 :
5970 93 : return new_rgn_number;
5971 : }
5972 :
5973 : /* If X has a smaller topological sort number than Y, returns -1;
5974 : if greater, returns 1. */
5975 : static int
5976 2050 : bb_top_order_comparator (const void *x, const void *y)
5977 : {
5978 2050 : basic_block bb1 = *(const basic_block *) x;
5979 2050 : basic_block bb2 = *(const basic_block *) y;
5980 :
5981 2050 : gcc_assert (bb1 == bb2
5982 : || rev_top_order_index[bb1->index]
5983 : != rev_top_order_index[bb2->index]);
5984 :
5985 : /* It's a reverse topological order in REV_TOP_ORDER_INDEX, so
5986 : bbs with greater number should go earlier. */
5987 2050 : if (rev_top_order_index[bb1->index] > rev_top_order_index[bb2->index])
5988 : return -1;
5989 : else
5990 878 : return 1;
5991 : }
5992 :
5993 : /* Create a region for LOOP and return its number. If we don't want
5994 : to pipeline LOOP, return -1. */
5995 : static int
5996 58 : make_region_from_loop (class loop *loop)
5997 : {
5998 58 : unsigned int i;
5999 58 : int new_rgn_number = -1;
6000 58 : class loop *inner;
6001 :
6002 : /* Basic block index, to be assigned to BLOCK_TO_BB. */
6003 58 : int bb_ord_index = 0;
6004 58 : basic_block *loop_blocks;
6005 58 : basic_block preheader_block;
6006 :
6007 58 : if (loop->num_nodes
6008 58 : > (unsigned) param_max_pipeline_region_blocks)
6009 : return -1;
6010 :
6011 : /* Don't pipeline loops whose latch belongs to some of its inner loops. */
6012 61 : for (inner = loop->inner; inner; inner = inner->inner)
6013 6 : if (flow_bb_inside_loop_p (inner, loop->latch))
6014 : return -1;
6015 :
6016 55 : loop->ninsns = num_loop_insns (loop);
6017 55 : if ((int) loop->ninsns > param_max_pipeline_region_insns)
6018 : return -1;
6019 :
6020 55 : loop_blocks = get_loop_body_in_custom_order (loop, bb_top_order_comparator);
6021 :
6022 343 : for (i = 0; i < loop->num_nodes; i++)
6023 233 : if (loop_blocks[i]->flags & BB_IRREDUCIBLE_LOOP)
6024 : {
6025 0 : free (loop_blocks);
6026 0 : return -1;
6027 : }
6028 :
6029 55 : preheader_block = loop_preheader_edge (loop)->src;
6030 55 : gcc_assert (preheader_block);
6031 55 : gcc_assert (loop_blocks[0] == loop->header);
6032 :
6033 55 : new_rgn_number = sel_create_new_region ();
6034 :
6035 55 : sel_add_block_to_region (preheader_block, &bb_ord_index, new_rgn_number);
6036 55 : bitmap_set_bit (bbs_in_loop_rgns, preheader_block->index);
6037 :
6038 343 : for (i = 0; i < loop->num_nodes; i++)
6039 : {
6040 : /* Add only those blocks that haven't been scheduled in the inner loop.
6041 : The exception is the basic blocks with bookkeeping code - they should
6042 : be added to the region (and they actually don't belong to the loop
6043 : body, but to the region containing that loop body). */
6044 :
6045 233 : gcc_assert (new_rgn_number >= 0);
6046 :
6047 233 : if (! bitmap_bit_p (bbs_in_loop_rgns, loop_blocks[i]->index))
6048 : {
6049 207 : sel_add_block_to_region (loop_blocks[i], &bb_ord_index,
6050 : new_rgn_number);
6051 207 : bitmap_set_bit (bbs_in_loop_rgns, loop_blocks[i]->index);
6052 : }
6053 : }
6054 :
6055 55 : free (loop_blocks);
6056 55 : MARK_LOOP_FOR_PIPELINING (loop);
6057 :
6058 55 : return new_rgn_number;
6059 : }
6060 :
6061 : /* Create a new region from preheader blocks LOOP_BLOCKS. */
6062 : void
6063 38 : make_region_from_loop_preheader (vec<basic_block> *&loop_blocks)
6064 : {
6065 38 : unsigned int i;
6066 38 : int new_rgn_number = -1;
6067 38 : basic_block bb;
6068 :
6069 : /* Basic block index, to be assigned to BLOCK_TO_BB. */
6070 38 : int bb_ord_index = 0;
6071 :
6072 38 : new_rgn_number = sel_create_new_region ();
6073 :
6074 114 : FOR_EACH_VEC_ELT (*loop_blocks, i, bb)
6075 : {
6076 38 : gcc_assert (new_rgn_number >= 0);
6077 :
6078 38 : sel_add_block_to_region (bb, &bb_ord_index, new_rgn_number);
6079 : }
6080 :
6081 38 : vec_free (loop_blocks);
6082 38 : }
6083 :
6084 :
6085 : /* Create region(s) from loop nest LOOP, such that inner loops will be
6086 : pipelined before outer loops. Returns true when a region for LOOP
6087 : is created. */
6088 : static bool
6089 58 : make_regions_from_loop_nest (class loop *loop)
6090 : {
6091 58 : class loop *cur_loop;
6092 58 : int rgn_number;
6093 :
6094 : /* Traverse all inner nodes of the loop. */
6095 66 : for (cur_loop = loop->inner; cur_loop; cur_loop = cur_loop->next)
6096 8 : if (! bitmap_bit_p (bbs_in_loop_rgns, cur_loop->header->index))
6097 : return false;
6098 :
6099 : /* At this moment all regular inner loops should have been pipelined.
6100 : Try to create a region from this loop. */
6101 58 : rgn_number = make_region_from_loop (loop);
6102 :
6103 58 : if (rgn_number < 0)
6104 : return false;
6105 :
6106 55 : loop_nests.safe_push (loop);
6107 55 : return true;
6108 : }
6109 :
6110 : /* Initialize data structures needed. */
6111 : void
6112 43 : sel_init_pipelining (void)
6113 : {
6114 : /* Collect loop information to be used in outer loops pipelining. */
6115 43 : loop_optimizer_init (LOOPS_HAVE_PREHEADERS
6116 : | LOOPS_HAVE_FALLTHRU_PREHEADERS
6117 : | LOOPS_HAVE_RECORDED_EXITS
6118 : | LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS);
6119 43 : current_loop_nest = NULL;
6120 :
6121 43 : bbs_in_loop_rgns = sbitmap_alloc (last_basic_block_for_fn (cfun));
6122 43 : bitmap_clear (bbs_in_loop_rgns);
6123 :
6124 43 : recompute_rev_top_order ();
6125 43 : }
6126 :
6127 : /* Returns a class loop for region RGN. */
6128 : loop_p
6129 365 : get_loop_nest_for_rgn (unsigned int rgn)
6130 : {
6131 : /* Regions created with extend_rgns don't have corresponding loop nests,
6132 : because they don't represent loops. */
6133 365 : if (rgn < loop_nests.length ())
6134 55 : return loop_nests[rgn];
6135 : else
6136 : return NULL;
6137 : }
6138 :
6139 : /* True when LOOP was included into pipelining regions. */
6140 : bool
6141 945 : considered_for_pipelining_p (class loop *loop)
6142 : {
6143 945 : if (loop_depth (loop) == 0)
6144 : return false;
6145 :
6146 : /* Now, the loop could be too large or irreducible. Check whether its
6147 : region is in LOOP_NESTS.
6148 : We determine the region number of LOOP as the region number of its
6149 : latch. We can't use header here, because this header could be
6150 : just removed preheader and it will give us the wrong region number.
6151 : Latch can't be used because it could be in the inner loop too. */
6152 211 : if (LOOP_MARKED_FOR_PIPELINING_P (loop))
6153 : {
6154 163 : int rgn = CONTAINING_RGN (loop->latch->index);
6155 :
6156 163 : gcc_assert ((unsigned) rgn < loop_nests.length ());
6157 : return true;
6158 : }
6159 :
6160 : return false;
6161 : }
6162 :
6163 : /* Makes regions from the rest of the blocks, after loops are chosen
6164 : for pipelining. */
6165 : static void
6166 43 : make_regions_from_the_rest (void)
6167 : {
6168 43 : int cur_rgn_blocks;
6169 43 : int *loop_hdr;
6170 43 : int i;
6171 :
6172 43 : basic_block bb;
6173 43 : edge e;
6174 43 : edge_iterator ei;
6175 43 : int *degree;
6176 :
6177 : /* Index in rgn_bb_table where to start allocating new regions. */
6178 43 : cur_rgn_blocks = nr_regions ? RGN_BLOCKS (nr_regions) : 0;
6179 :
6180 : /* Make regions from all the rest basic blocks - those that don't belong to
6181 : any loop or belong to irreducible loops. Prepare the data structures
6182 : for extend_rgns. */
6183 :
6184 : /* LOOP_HDR[I] == -1 if I-th bb doesn't belong to any loop,
6185 : LOOP_HDR[I] == LOOP_HDR[J] iff basic blocks I and J reside within the same
6186 : loop. */
6187 43 : loop_hdr = XNEWVEC (int, last_basic_block_for_fn (cfun));
6188 43 : degree = XCNEWVEC (int, last_basic_block_for_fn (cfun));
6189 :
6190 :
6191 : /* For each basic block that belongs to some loop assign the number
6192 : of innermost loop it belongs to. */
6193 693 : for (i = 0; i < last_basic_block_for_fn (cfun); i++)
6194 607 : loop_hdr[i] = -1;
6195 :
6196 563 : FOR_EACH_BB_FN (bb, cfun)
6197 : {
6198 520 : if (bb->loop_father && bb->loop_father->num != 0
6199 298 : && !(bb->flags & BB_IRREDUCIBLE_LOOP))
6200 298 : loop_hdr[bb->index] = bb->loop_father->num;
6201 : }
6202 :
6203 : /* For each basic block degree is calculated as the number of incoming
6204 : edges, that are going out of bbs that are not yet scheduled.
6205 : The basic blocks that are scheduled have degree value of zero. */
6206 563 : FOR_EACH_BB_FN (bb, cfun)
6207 : {
6208 520 : degree[bb->index] = 0;
6209 :
6210 520 : if (!bitmap_bit_p (bbs_in_loop_rgns, bb->index))
6211 : {
6212 633 : FOR_EACH_EDGE (e, ei, bb->preds)
6213 375 : if (!bitmap_bit_p (bbs_in_loop_rgns, e->src->index))
6214 290 : degree[bb->index]++;
6215 : }
6216 : else
6217 262 : degree[bb->index] = -1;
6218 : }
6219 :
6220 43 : extend_rgns (degree, &cur_rgn_blocks, bbs_in_loop_rgns, loop_hdr);
6221 :
6222 : /* Any block that did not end up in a region is placed into a region
6223 : by itself. */
6224 563 : FOR_EACH_BB_FN (bb, cfun)
6225 520 : if (degree[bb->index] >= 0)
6226 : {
6227 258 : rgn_bb_table[cur_rgn_blocks] = bb->index;
6228 258 : RGN_NR_BLOCKS (nr_regions) = 1;
6229 258 : RGN_BLOCKS (nr_regions) = cur_rgn_blocks++;
6230 258 : RGN_DONT_CALC_DEPS (nr_regions) = 0;
6231 258 : RGN_HAS_REAL_EBB (nr_regions) = 0;
6232 258 : CONTAINING_RGN (bb->index) = nr_regions++;
6233 258 : BLOCK_TO_BB (bb->index) = 0;
6234 : }
6235 :
6236 43 : free (degree);
6237 43 : free (loop_hdr);
6238 43 : }
6239 :
6240 : /* Free data structures used in pipelining of loops. */
6241 43 : void sel_finish_pipelining (void)
6242 : {
6243 : /* Release aux fields so we don't free them later by mistake. */
6244 193 : for (auto loop : loops_list (cfun, 0))
6245 64 : loop->aux = NULL;
6246 :
6247 43 : loop_optimizer_finalize ();
6248 :
6249 43 : loop_nests.release ();
6250 :
6251 43 : free (rev_top_order_index);
6252 43 : rev_top_order_index = NULL;
6253 43 : }
6254 :
6255 : /* This function replaces the find_rgns when
6256 : FLAG_SEL_SCHED_PIPELINING_OUTER_LOOPS is set. */
6257 : void
6258 43 : sel_find_rgns (void)
6259 : {
6260 43 : sel_init_pipelining ();
6261 43 : extend_regions ();
6262 :
6263 43 : if (current_loops)
6264 : {
6265 36 : unsigned flags = flag_sel_sched_pipelining_outer_loops
6266 43 : ? LI_FROM_INNERMOST
6267 : : LI_ONLY_INNERMOST;
6268 :
6269 187 : for (auto loop : loops_list (cfun, flags))
6270 101 : make_regions_from_loop_nest (loop);
6271 : }
6272 :
6273 : /* Make regions from all the rest basic blocks and schedule them.
6274 : These blocks include blocks that don't belong to any loop or belong
6275 : to irreducible loops. */
6276 43 : make_regions_from_the_rest ();
6277 :
6278 : /* We don't need bbs_in_loop_rgns anymore. */
6279 43 : sbitmap_free (bbs_in_loop_rgns);
6280 43 : bbs_in_loop_rgns = NULL;
6281 43 : }
6282 :
6283 : /* Add the preheader blocks from previous loop to current region taking
6284 : it from LOOP_PREHEADER_BLOCKS (current_loop_nest) and record them in *BBS.
6285 : This function is only used with -fsel-sched-pipelining-outer-loops. */
6286 : void
6287 55 : sel_add_loop_preheaders (bb_vec_t *bbs)
6288 : {
6289 55 : int i;
6290 55 : basic_block bb;
6291 110 : vec<basic_block> *preheader_blocks
6292 55 : = LOOP_PREHEADER_BLOCKS (current_loop_nest);
6293 :
6294 55 : if (!preheader_blocks)
6295 49 : return;
6296 :
6297 13 : for (i = 0; preheader_blocks->iterate (i, &bb); i++)
6298 : {
6299 7 : bbs->safe_push (bb);
6300 7 : last_added_blocks.safe_push (bb);
6301 7 : sel_add_bb (bb);
6302 : }
6303 :
6304 6 : vec_free (preheader_blocks);
6305 : }
6306 :
6307 : /* While pipelining outer loops, returns TRUE if BB is a loop preheader.
6308 : Please note that the function should also work when pipelining_p is
6309 : false, because it is used when deciding whether we should or should
6310 : not reschedule pipelined code. */
6311 : bool
6312 1293 : sel_is_loop_preheader_p (basic_block bb)
6313 : {
6314 1293 : if (current_loop_nest)
6315 : {
6316 816 : class loop *outer;
6317 :
6318 816 : if (preheader_removed)
6319 : return false;
6320 :
6321 : /* Preheader is the first block in the region. */
6322 816 : if (BLOCK_TO_BB (bb->index) == 0)
6323 : return true;
6324 :
6325 : /* We used to find a preheader with the topological information.
6326 : Check that the above code is equivalent to what we did before. */
6327 :
6328 584 : if (in_current_region_p (current_loop_nest->header))
6329 584 : gcc_assert (!(BLOCK_TO_BB (bb->index)
6330 : < BLOCK_TO_BB (current_loop_nest->header->index)));
6331 :
6332 : /* Support the situation when the latch block of outer loop
6333 : could be from here. */
6334 584 : for (outer = loop_outer (current_loop_nest);
6335 1260 : outer;
6336 676 : outer = loop_outer (outer))
6337 676 : if (considered_for_pipelining_p (outer) && outer->latch == bb)
6338 0 : gcc_unreachable ();
6339 : }
6340 :
6341 : return false;
6342 : }
6343 :
6344 : /* Check whether JUMP_BB ends with a jump insn that leads only to DEST_BB and
6345 : can be removed, making the corresponding edge fallthrough (assuming that
6346 : all basic blocks between JUMP_BB and DEST_BB are empty). */
6347 : static bool
6348 2816 : bb_has_removable_jump_to_p (basic_block jump_bb, basic_block dest_bb)
6349 : {
6350 2816 : if (!onlyjump_p (BB_END (jump_bb))
6351 2816 : || tablejump_p (BB_END (jump_bb), NULL, NULL))
6352 865 : return false;
6353 :
6354 : /* Several outgoing edges, abnormal edge or destination of jump is
6355 : not DEST_BB. */
6356 4750 : if (EDGE_COUNT (jump_bb->succs) != 1
6357 438 : || EDGE_SUCC (jump_bb, 0)->flags & (EDGE_ABNORMAL | EDGE_CROSSING)
6358 2383 : || EDGE_SUCC (jump_bb, 0)->dest != dest_bb)
6359 : return false;
6360 :
6361 : /* If not anything of the upper. */
6362 : return true;
6363 : }
6364 :
6365 : /* Removes the loop preheader from the current region and saves it in
6366 : PREHEADER_BLOCKS of the father loop, so they will be added later to
6367 : region that represents an outer loop. */
6368 : static void
6369 55 : sel_remove_loop_preheader (void)
6370 : {
6371 55 : int i, old_len;
6372 55 : int cur_rgn = CONTAINING_RGN (BB_TO_BLOCK (0));
6373 55 : basic_block bb;
6374 55 : bool all_empty_p = true;
6375 55 : vec<basic_block> *preheader_blocks
6376 55 : = LOOP_PREHEADER_BLOCKS (loop_outer (current_loop_nest));
6377 :
6378 55 : vec_check_alloc (preheader_blocks, 0);
6379 :
6380 55 : gcc_assert (current_loop_nest);
6381 55 : old_len = preheader_blocks->length ();
6382 :
6383 : /* Add blocks that aren't within the current loop to PREHEADER_BLOCKS. */
6384 328 : for (i = 0; i < RGN_NR_BLOCKS (cur_rgn); i++)
6385 : {
6386 273 : bb = BASIC_BLOCK_FOR_FN (cfun, BB_TO_BLOCK (i));
6387 :
6388 : /* If the basic block belongs to region, but doesn't belong to
6389 : corresponding loop, then it should be a preheader. */
6390 273 : if (sel_is_loop_preheader_p (bb))
6391 : {
6392 55 : preheader_blocks->safe_push (bb);
6393 55 : if (BB_END (bb) != bb_note (bb))
6394 273 : all_empty_p = false;
6395 : }
6396 : }
6397 :
6398 : /* Remove these blocks only after iterating over the whole region. */
6399 165 : for (i = preheader_blocks->length () - 1; i >= old_len; i--)
6400 : {
6401 55 : bb = (*preheader_blocks)[i];
6402 55 : sel_remove_bb (bb, false);
6403 : }
6404 :
6405 55 : if (!considered_for_pipelining_p (loop_outer (current_loop_nest)))
6406 : {
6407 48 : if (!all_empty_p)
6408 : /* Immediately create new region from preheader. */
6409 38 : make_region_from_loop_preheader (preheader_blocks);
6410 : else
6411 : {
6412 : /* If all preheader blocks are empty - dont create new empty region.
6413 : Instead, remove them completely. */
6414 20 : FOR_EACH_VEC_ELT (*preheader_blocks, i, bb)
6415 : {
6416 10 : edge e;
6417 10 : edge_iterator ei;
6418 10 : basic_block prev_bb = bb->prev_bb, next_bb = bb->next_bb;
6419 :
6420 : /* Redirect all incoming edges to next basic block. */
6421 21 : for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
6422 : {
6423 11 : if (! (e->flags & EDGE_FALLTHRU))
6424 8 : redirect_edge_and_branch (e, bb->next_bb);
6425 : else
6426 3 : redirect_edge_succ (e, bb->next_bb);
6427 : }
6428 10 : gcc_assert (BB_NOTE_LIST (bb) == NULL);
6429 10 : delete_and_free_basic_block (bb);
6430 :
6431 : /* Check if after deleting preheader there is a nonconditional
6432 : jump in PREV_BB that leads to the next basic block NEXT_BB.
6433 : If it is so - delete this jump and clear data sets of its
6434 : basic block if it becomes empty. */
6435 10 : if (next_bb->prev_bb == prev_bb
6436 10 : && prev_bb != ENTRY_BLOCK_PTR_FOR_FN (cfun)
6437 20 : && bb_has_removable_jump_to_p (prev_bb, next_bb))
6438 : {
6439 5 : redirect_edge_and_branch (EDGE_SUCC (prev_bb, 0), next_bb);
6440 5 : if (BB_END (prev_bb) == bb_note (prev_bb))
6441 0 : free_data_sets (prev_bb);
6442 : }
6443 :
6444 10 : set_immediate_dominator (CDI_DOMINATORS, next_bb,
6445 : recompute_dominator (CDI_DOMINATORS,
6446 : next_bb));
6447 : }
6448 : }
6449 48 : vec_free (preheader_blocks);
6450 : }
6451 : else
6452 : /* Store preheader within the father's loop structure. */
6453 7 : SET_LOOP_PREHEADER_BLOCKS (loop_outer (current_loop_nest),
6454 : preheader_blocks);
6455 55 : }
6456 :
6457 : #endif
|
