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 4130 : ilist_copy (ilist_t l)
165 : {
166 4130 : ilist_t head = NULL, *tailp = &head;
167 :
168 18523 : while (l)
169 : {
170 14393 : ilist_add (tailp, ILIST_INSN (l));
171 14393 : tailp = &ILIST_NEXT (*tailp);
172 14393 : l = ILIST_NEXT (l);
173 : }
174 :
175 4130 : 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 5942 : blist_add (blist_t *lp, insn_t to, ilist_t ptr, deps_t dc)
196 : {
197 5942 : bnd_t bnd;
198 :
199 5942 : _list_add (lp);
200 5942 : bnd = BLIST_BND (*lp);
201 :
202 5942 : BND_TO (bnd) = to;
203 5942 : BND_PTR (bnd) = ptr;
204 5942 : BND_AV (bnd) = NULL;
205 5942 : BND_AV1 (bnd) = NULL;
206 5942 : BND_DC (bnd) = dc;
207 5942 : }
208 :
209 : /* Remove the list note pointed to by LP. */
210 : void
211 5942 : blist_remove (blist_t *lp)
212 : {
213 5942 : bnd_t b = BLIST_BND (*lp);
214 :
215 5942 : av_set_clear (&BND_AV (b));
216 5942 : av_set_clear (&BND_AV1 (b));
217 5942 : ilist_clear (&BND_PTR (b));
218 :
219 5942 : _list_remove (lp);
220 5942 : }
221 :
222 : /* Init a fence tail L. */
223 : void
224 1685 : flist_tail_init (flist_tail_t l)
225 : {
226 1685 : FLIST_TAIL_HEAD (l) = NULL;
227 1685 : FLIST_TAIL_TAILP (l) = &FLIST_TAIL_HEAD (l);
228 1685 : }
229 :
230 : /* Try to find fence corresponding to INSN in L. */
231 : fence_t
232 64458 : flist_lookup (flist_t l, insn_t insn)
233 : {
234 136017 : while (l)
235 : {
236 71577 : if (FENCE_INSN (FLIST_FENCE (l)) == insn)
237 18 : return FLIST_FENCE (l);
238 :
239 71559 : 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 1812 : init_fence_for_scheduling (fence_t f)
248 : {
249 1812 : FENCE_BNDS (f) = NULL;
250 1812 : FENCE_PROCESSED_P (f) = false;
251 1812 : FENCE_SCHEDULED_P (f) = false;
252 0 : }
253 :
254 : /* Add new fence consisting of INSN and STATE to the list pointed to by LP. */
255 : static void
256 999 : 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 999 : fence_t f;
263 :
264 999 : _list_add (lp);
265 999 : f = FLIST_FENCE (*lp);
266 :
267 999 : FENCE_INSN (f) = insn;
268 :
269 999 : gcc_assert (state != NULL);
270 999 : FENCE_STATE (f) = state;
271 :
272 999 : FENCE_CYCLE (f) = cycle;
273 999 : FENCE_ISSUED_INSNS (f) = cycle_issued_insns;
274 999 : FENCE_STARTS_CYCLE_P (f) = starts_cycle_p;
275 999 : FENCE_AFTER_STALL_P (f) = after_stall_p;
276 :
277 999 : gcc_assert (dc != NULL);
278 999 : FENCE_DC (f) = dc;
279 :
280 999 : gcc_assert (tc != NULL || targetm.sched.alloc_sched_context == NULL);
281 999 : FENCE_TC (f) = tc;
282 :
283 999 : FENCE_LAST_SCHEDULED_INSN (f) = last_scheduled_insn;
284 999 : FENCE_ISSUE_MORE (f) = issue_more;
285 999 : FENCE_EXECUTING_INSNS (f) = executing_insns;
286 999 : FENCE_READY_TICKS (f) = ready_ticks;
287 999 : FENCE_READY_TICKS_SIZE (f) = ready_ticks_size;
288 999 : FENCE_SCHED_NEXT (f) = sched_next;
289 :
290 999 : init_fence_for_scheduling (f);
291 999 : }
292 :
293 : /* Remove the head node of the list pointed to by LP. */
294 : static void
295 1812 : flist_remove (flist_t *lp)
296 : {
297 1812 : if (FENCE_INSN (FLIST_FENCE (*lp)))
298 998 : fence_clear (FLIST_FENCE (*lp));
299 1812 : _list_remove (lp);
300 1812 : }
301 :
302 : /* Clear the fence list pointed to by LP. */
303 : void
304 1666 : flist_clear (flist_t *lp)
305 : {
306 3478 : while (*lp)
307 1812 : flist_remove (lp);
308 1666 : }
309 :
310 : /* Add ORIGINAL_INSN the def list DL honoring CROSSED_CALL_ABIS. */
311 : void
312 3893 : def_list_add (def_list_t *dl, insn_t original_insn,
313 : unsigned int crossed_call_abis)
314 : {
315 3893 : def_t d;
316 :
317 3893 : _list_add (dl);
318 3893 : d = DEF_LIST_DEF (*dl);
319 :
320 3893 : d->orig_insn = original_insn;
321 3893 : d->crossed_call_abis = crossed_call_abis;
322 3893 : }
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 1170 : alloc_target_context (void)
337 : {
338 1170 : return (targetm.sched.alloc_sched_context
339 1170 : ? 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 2994 : 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 1010 : create_target_context (bool clean_p)
356 : {
357 1010 : tc_t tc = alloc_target_context ();
358 :
359 1010 : init_target_context (tc, clean_p);
360 1010 : return tc;
361 : }
362 :
363 : /* Copy TC to the current backend context. */
364 : void
365 2132 : set_target_context (tc_t tc)
366 : {
367 2132 : if (targetm.sched.set_sched_context)
368 0 : targetm.sched.set_sched_context (tc);
369 2132 : }
370 :
371 : /* TC is about to be destroyed. Free any internal data. */
372 : static void
373 2994 : 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 1170 : delete_target_context (tc_t tc)
382 : {
383 1170 : clear_target_context (tc);
384 :
385 1170 : if (targetm.sched.free_sched_context)
386 0 : targetm.sched.free_sched_context (tc);
387 1170 : }
388 :
389 : /* Make a copy of FROM in TO.
390 : NB: May be this should be a hook. */
391 : static void
392 160 : copy_target_context (tc_t to, tc_t from)
393 : {
394 160 : tc_t tmp = create_target_context (false);
395 :
396 160 : set_target_context (from);
397 160 : init_target_context (to, false);
398 :
399 160 : set_target_context (tmp);
400 160 : delete_target_context (tmp);
401 160 : }
402 :
403 : /* Create a copy of TC. */
404 : static tc_t
405 160 : create_copy_of_target_context (tc_t tc)
406 : {
407 160 : tc_t copy = alloc_target_context ();
408 :
409 160 : copy_target_context (copy, tc);
410 :
411 160 : 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 1824 : reset_target_context (tc_t tc, bool clean_p)
418 : {
419 1824 : clear_target_context (tc);
420 1824 : init_target_context (tc, clean_p);
421 1824 : }
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 160 : copy_deps_context (deps_t to, deps_t from)
431 : {
432 160 : init_deps (to, false);
433 160 : deps_join (to, from);
434 160 : }
435 :
436 : /* Allocate store for dep context. */
437 : static deps_t
438 1010 : 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 850 : create_deps_context (void)
446 : {
447 850 : deps_t dc = alloc_deps_context ();
448 :
449 850 : init_deps (dc, false);
450 850 : return dc;
451 : }
452 :
453 : /* Create a copy of FROM. */
454 : static deps_t
455 160 : create_copy_of_deps_context (deps_t from)
456 : {
457 160 : deps_t to = alloc_deps_context ();
458 :
459 160 : copy_deps_context (to, from);
460 160 : return to;
461 : }
462 :
463 : /* Clean up internal data of DC. */
464 : static void
465 1022 : clear_deps_context (deps_t dc)
466 : {
467 0 : free_deps (dc);
468 0 : }
469 :
470 : /* Clear and free DC. */
471 : static void
472 1010 : delete_deps_context (deps_t dc)
473 : {
474 0 : clear_deps_context (dc);
475 1010 : free (dc);
476 0 : }
477 :
478 : /* Clear and init DC. */
479 : static void
480 12 : reset_deps_context (deps_t dc)
481 : {
482 12 : clear_deps_context (dc);
483 12 : init_deps (dc, false);
484 12 : }
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 8064 : advance_deps_context (deps_t dc, insn_t insn)
510 : {
511 8064 : sched_deps_info = &advance_deps_context_sched_deps_info;
512 8064 : deps_analyze_insn (dc, insn);
513 8064 : }
514 :
515 :
516 : /* Functions to work with DFA states. */
517 :
518 : /* Allocate store for a DFA state. */
519 : static state_t
520 1010 : state_alloc (void)
521 : {
522 0 : return xmalloc (dfa_state_size);
523 : }
524 :
525 : /* Allocate and initialize DFA state. */
526 : static state_t
527 850 : state_create (void)
528 : {
529 850 : state_t state = state_alloc ();
530 :
531 850 : state_reset (state);
532 850 : advance_state (state);
533 850 : return state;
534 : }
535 :
536 : /* Free DFA state. */
537 : static void
538 12 : state_free (state_t state)
539 : {
540 12 : free (state);
541 0 : }
542 :
543 : /* Make a copy of FROM in TO. */
544 : static void
545 160 : state_copy (state_t to, state_t from)
546 : {
547 160 : memcpy (to, from, dfa_state_size);
548 0 : }
549 :
550 : /* Create a copy of FROM. */
551 : static state_t
552 160 : state_create_copy (state_t from)
553 : {
554 160 : state_t to = state_alloc ();
555 :
556 160 : state_copy (to, from);
557 160 : return to;
558 : }
559 :
560 :
561 : /* Functions to work with fences. */
562 :
563 : /* Clear the fence. */
564 : static void
565 998 : fence_clear (fence_t f)
566 : {
567 998 : state_t s = FENCE_STATE (f);
568 998 : deps_t dc = FENCE_DC (f);
569 998 : void *tc = FENCE_TC (f);
570 :
571 998 : ilist_clear (&FENCE_BNDS (f));
572 :
573 998 : gcc_assert ((s != NULL && dc != NULL && tc != NULL)
574 : || (s == NULL && dc == NULL && tc == NULL));
575 :
576 998 : free (s);
577 :
578 998 : if (dc != NULL)
579 998 : delete_deps_context (dc);
580 :
581 998 : if (tc != NULL)
582 998 : delete_target_context (tc);
583 998 : vec_free (FENCE_EXECUTING_INSNS (f));
584 998 : free (FENCE_READY_TICKS (f));
585 998 : FENCE_READY_TICKS (f) = NULL;
586 998 : }
587 :
588 : /* Init a list of fences with successors of OLD_FENCE. */
589 : void
590 758 : init_fences (insn_t old_fence)
591 : {
592 758 : insn_t succ;
593 758 : succ_iterator si;
594 758 : bool first = true;
595 758 : int ready_ticks_size = get_max_uid () + 1;
596 :
597 1516 : FOR_EACH_SUCC_1 (succ, si, old_fence,
598 : SUCCS_NORMAL | SUCCS_SKIP_TO_LOOP_EXITS)
599 : {
600 :
601 758 : if (first)
602 : first = false;
603 : else
604 0 : gcc_assert (flag_sel_sched_pipelining_outer_loops);
605 :
606 758 : 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 758 : 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 758 : }
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 12 : 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 12 : insn_t last_scheduled_insn_old = FENCE_LAST_SCHEDULED_INSN (f);
639 :
640 12 : 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 12 : if (last_scheduled_insn == NULL
646 12 : || 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 12 : state_reset (FENCE_STATE (f));
654 12 : state_free (state);
655 :
656 12 : reset_deps_context (FENCE_DC (f));
657 12 : delete_deps_context (dc);
658 :
659 12 : reset_target_context (FENCE_TC (f), true);
660 12 : delete_target_context (tc);
661 :
662 12 : if (cycle > FENCE_CYCLE (f))
663 1 : FENCE_CYCLE (f) = cycle;
664 :
665 12 : FENCE_LAST_SCHEDULED_INSN (f) = NULL;
666 12 : FENCE_ISSUE_MORE (f) = issue_rate;
667 12 : vec_free (executing_insns);
668 12 : free (ready_ticks);
669 12 : if (FENCE_EXECUTING_INSNS (f))
670 3 : FENCE_EXECUTING_INSNS (f)->block_remove (0,
671 3 : FENCE_EXECUTING_INSNS (f)->length ());
672 12 : if (FENCE_READY_TICKS (f))
673 12 : 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 12 : if (after_stall_p)
783 1 : FENCE_AFTER_STALL_P (f) = 1;
784 :
785 12 : FENCE_ISSUED_INSNS (f) = 0;
786 12 : FENCE_STARTS_CYCLE_P (f) = 1;
787 12 : FENCE_SCHED_NEXT (f) = NULL;
788 12 : }
789 :
790 : /* Add a new fence to NEW_FENCES list, initializing it from all
791 : other parameters. */
792 : static void
793 252 : 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 252 : fence_t f = flist_lookup (FLIST_TAIL_HEAD (new_fences), insn);
802 :
803 252 : if (! f)
804 : {
805 241 : 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 241 : FLIST_TAIL_TAILP (new_fences)
811 241 : = &FLIST_NEXT (*FLIST_TAIL_TAILP (new_fences));
812 : }
813 : else
814 : {
815 11 : 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 252 : }
820 :
821 : /* Move the first fence in the OLD_FENCES list to NEW_FENCES. */
822 : void
823 814 : move_fence_to_fences (flist_t old_fences, flist_tail_t new_fences)
824 : {
825 814 : fence_t f, old;
826 814 : flist_t *tailp = FLIST_TAIL_TAILP (new_fences);
827 :
828 814 : old = FLIST_FENCE (old_fences);
829 814 : f = flist_lookup (FLIST_TAIL_HEAD (new_fences),
830 : FENCE_INSN (FLIST_FENCE (old_fences)));
831 814 : 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 : old->after_stall_p);
838 : }
839 : else
840 : {
841 813 : _list_add (tailp);
842 813 : FLIST_TAIL_TAILP (new_fences) = &FLIST_NEXT (*tailp);
843 813 : *FLIST_FENCE (*tailp) = *old;
844 813 : init_fence_for_scheduling (FLIST_FENCE (*tailp));
845 : }
846 814 : FENCE_INSN (old) = NULL;
847 814 : }
848 :
849 : /* Add a new fence to NEW_FENCES list and initialize most of its data
850 : as a clean one. */
851 : void
852 92 : add_clean_fence_to_fences (flist_tail_t new_fences, insn_t succ, fence_t fence)
853 : {
854 92 : int ready_ticks_size = get_max_uid () + 1;
855 :
856 92 : add_to_fences (new_fences,
857 : succ, state_create (), create_deps_context (),
858 : create_target_context (true),
859 : NULL, NULL,
860 92 : XCNEWVEC (int, ready_ticks_size), ready_ticks_size,
861 92 : NULL, FENCE_CYCLE (fence) + 1,
862 : 0, issue_rate, 1, FENCE_AFTER_STALL_P (fence));
863 92 : }
864 :
865 : /* Add a new fence to NEW_FENCES list and initialize all of its data
866 : from FENCE and SUCC. */
867 : void
868 160 : add_dirty_fence_to_fences (flist_tail_t new_fences, insn_t succ, fence_t fence)
869 : {
870 160 : int * new_ready_ticks
871 160 : = XNEWVEC (int, FENCE_READY_TICKS_SIZE (fence));
872 :
873 160 : memcpy (new_ready_ticks, FENCE_READY_TICKS (fence),
874 160 : FENCE_READY_TICKS_SIZE (fence) * sizeof (int));
875 320 : 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 : FENCE_STARTS_CYCLE_P (fence),
888 : FENCE_AFTER_STALL_P (fence));
889 160 : }
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 50607 : get_regset_from_pool (void)
898 : {
899 50607 : regset rs;
900 :
901 50607 : if (regset_pool.n != 0)
902 39924 : rs = regset_pool.v[--regset_pool.n];
903 : else
904 : /* We need to create the regset. */
905 : {
906 10683 : rs = ALLOC_REG_SET (®_obstack);
907 :
908 10683 : 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 10683 : regset_pool.vv[regset_pool.nn++] = rs;
912 : }
913 :
914 50607 : regset_pool.diff++;
915 :
916 50607 : return rs;
917 : }
918 :
919 : /* Same as above, but returns the empty regset. */
920 : regset
921 27967 : get_clear_regset_from_pool (void)
922 : {
923 27967 : regset rs = get_regset_from_pool ();
924 :
925 27967 : CLEAR_REG_SET (rs);
926 27967 : return rs;
927 : }
928 :
929 : /* Return regset RS to the pool for future use. */
930 : void
931 50607 : return_regset_to_pool (regset rs)
932 : {
933 50607 : gcc_assert (rs);
934 50607 : regset_pool.diff--;
935 :
936 50607 : 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 50607 : regset_pool.v[regset_pool.n++] = rs;
940 50607 : }
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 775147 : cmp_v_in_regset_pool (const void *x, const void *xx)
946 : {
947 775147 : uintptr_t r1 = (uintptr_t) *((const regset *) x);
948 775147 : uintptr_t r2 = (uintptr_t) *((const regset *) xx);
949 775147 : if (r1 > r2)
950 : return 1;
951 391051 : 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 10945 : while (ii < nn)
979 : {
980 10683 : if (v[i] == vv[ii])
981 10683 : i++;
982 : else
983 : /* VV[II] was lost. */
984 0 : diff++;
985 :
986 10683 : 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 10814 : while (regset_pool.n)
996 : {
997 10683 : --regset_pool.n;
998 10683 : 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 1984 : get_nop_from_pool (insn_t insn)
1025 : {
1026 1984 : rtx nop_pat;
1027 1984 : insn_t nop;
1028 1984 : bool old_p = nop_pool.n != 0;
1029 1984 : int flags;
1030 :
1031 1984 : if (old_p)
1032 1156 : nop_pat = nop_pool.v[--nop_pool.n];
1033 : else
1034 828 : nop_pat = nop_pattern;
1035 :
1036 1984 : nop = emit_insn_before (nop_pat, insn);
1037 :
1038 1984 : if (old_p)
1039 : flags = INSN_INIT_TODO_SSID;
1040 : else
1041 828 : flags = INSN_INIT_TODO_LUID | INSN_INIT_TODO_SSID;
1042 :
1043 1984 : set_insn_init (INSN_EXPR (insn), nop_vinsn, INSN_SEQNO (insn));
1044 1984 : sel_init_new_insn (nop, flags);
1045 :
1046 1984 : return nop;
1047 : }
1048 :
1049 : /* Remove NOP from the instruction stream and return it to the pool. */
1050 : void
1051 1984 : return_nop_to_pool (insn_t nop, bool full_tidying)
1052 : {
1053 3968 : gcc_assert (INSN_IN_STREAM_P (nop));
1054 1984 : sel_remove_insn (nop, false, full_tidying);
1055 :
1056 : /* We'll recycle this nop. */
1057 1984 : nop->set_undeleted ();
1058 :
1059 1984 : if (nop_pool.n == nop_pool.s)
1060 825 : nop_pool.v = XRESIZEVEC (rtx_insn *, nop_pool.v,
1061 : (nop_pool.s = 2 * nop_pool.s + 1));
1062 1984 : nop_pool.v[nop_pool.n++] = nop;
1063 1984 : }
1064 :
1065 : /* Free the nop pool. */
1066 : void
1067 739 : free_nop_pool (void)
1068 : {
1069 739 : nop_pool.n = 0;
1070 739 : nop_pool.s = 0;
1071 739 : free (nop_pool.v);
1072 739 : nop_pool.v = NULL;
1073 739 : }
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 2742 : lhs_and_rhs_separable_p (rtx lhs, rtx rhs)
1128 : {
1129 2742 : 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 2742 : if (CONSTANT_P (rhs))
1137 : return false;
1138 :
1139 : /* ??? Do not rename predicate registers to avoid ICEs in bundling. */
1140 2367 : if (COMPARISON_P (rhs))
1141 : return false;
1142 :
1143 : /* Do not allow single REG to be an rhs. */
1144 2341 : 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 1409 : 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 1377 : 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 5801 : vinsn_init (vinsn_t vi, insn_t insn, bool force_unique_p)
1166 : {
1167 5801 : hash_rtx_callback_function hrcf;
1168 5801 : int insn_class;
1169 :
1170 5801 : VINSN_INSN_RTX (vi) = insn;
1171 5801 : VINSN_COUNT (vi) = 0;
1172 5801 : vi->cost = -1;
1173 :
1174 5801 : if (INSN_NOP_P (insn))
1175 : return;
1176 :
1177 5062 : if (DF_INSN_UID_SAFE_GET (INSN_UID (insn)) != NULL)
1178 4402 : init_id_from_df (VINSN_ID (vi), insn, force_unique_p);
1179 : else
1180 660 : deps_init_id (VINSN_ID (vi), insn, force_unique_p);
1181 :
1182 : /* Hash vinsn depending on whether it is separable or not. */
1183 5062 : hrcf = targetm.sched.skip_rtx_p ? hash_with_unspec_callback : NULL;
1184 5062 : if (VINSN_SEPARABLE_P (vi))
1185 : {
1186 1373 : rtx rhs = VINSN_RHS (vi);
1187 :
1188 1373 : VINSN_HASH (vi) = hash_rtx (rhs, GET_MODE (rhs),
1189 : NULL, NULL, false, hrcf);
1190 1373 : VINSN_HASH_RTX (vi) = hash_rtx (VINSN_PATTERN (vi),
1191 : VOIDmode, NULL, NULL,
1192 : false, hrcf);
1193 : }
1194 : else
1195 : {
1196 3689 : VINSN_HASH (vi) = hash_rtx (VINSN_PATTERN (vi), VOIDmode,
1197 : NULL, NULL, false, hrcf);
1198 3689 : VINSN_HASH_RTX (vi) = VINSN_HASH (vi);
1199 : }
1200 :
1201 5062 : insn_class = haifa_classify_insn (insn);
1202 5062 : if (insn_class >= 2
1203 5062 : && (!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 4351 : VINSN_MAY_TRAP_P (vi) = false;
1209 : }
1210 :
1211 : /* Indicate that VI has become the part of an rtx object. */
1212 : void
1213 195399 : vinsn_attach (vinsn_t vi)
1214 : {
1215 : /* Assert that VI is not pending for deletion. */
1216 195399 : gcc_assert (VINSN_INSN_RTX (vi));
1217 :
1218 195399 : VINSN_COUNT (vi)++;
1219 195399 : }
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 5801 : vinsn_create (insn_t insn, bool force_unique_p)
1225 : {
1226 5801 : vinsn_t vi = XCNEW (struct vinsn_def);
1227 :
1228 5801 : vinsn_init (vi, insn, force_unique_p);
1229 5801 : 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 5801 : vinsn_delete (vinsn_t vi)
1255 : {
1256 5801 : gcc_assert (VINSN_COUNT (vi) == 0);
1257 :
1258 5801 : if (!INSN_NOP_P (VINSN_INSN_RTX (vi)))
1259 : {
1260 5062 : return_regset_to_pool (VINSN_REG_SETS (vi));
1261 5062 : return_regset_to_pool (VINSN_REG_USES (vi));
1262 5062 : return_regset_to_pool (VINSN_REG_CLOBBERS (vi));
1263 : }
1264 :
1265 5801 : free (vi);
1266 5801 : }
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 195399 : vinsn_detach (vinsn_t vi)
1272 : {
1273 195399 : gcc_assert (VINSN_COUNT (vi) > 0);
1274 :
1275 195399 : if (--VINSN_COUNT (vi) == 0)
1276 5801 : vinsn_delete (vi);
1277 195399 : }
1278 :
1279 : /* Returns TRUE if VI is a branch. */
1280 : bool
1281 17052 : vinsn_cond_branch_p (vinsn_t vi)
1282 : {
1283 17052 : insn_t insn;
1284 :
1285 17052 : if (!VINSN_UNIQUE_P (vi))
1286 : return false;
1287 :
1288 2418 : insn = VINSN_INSN_RTX (vi);
1289 2418 : if (BB_END (BLOCK_FOR_INSN (insn)) != insn)
1290 : return false;
1291 :
1292 1247 : return control_flow_insn_p (insn);
1293 : }
1294 :
1295 : /* Return latency of INSN. */
1296 : static int
1297 200 : sel_insn_rtx_cost (rtx_insn *insn)
1298 : {
1299 200 : 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 200 : if (recog_memoized (insn) < 0)
1306 : cost = 0;
1307 : else
1308 : {
1309 200 : cost = insn_default_latency (insn);
1310 :
1311 200 : if (cost < 0)
1312 0 : cost = 0;
1313 : }
1314 :
1315 200 : return cost;
1316 : }
1317 :
1318 : /* Return the cost of the VI.
1319 : !!! FIXME: Unify with haifa-sched.cc: insn_sched_cost (). */
1320 : int
1321 987 : sel_vinsn_cost (vinsn_t vi)
1322 : {
1323 987 : int cost = vi->cost;
1324 :
1325 987 : if (cost < 0)
1326 : {
1327 200 : cost = sel_insn_rtx_cost (VINSN_INSN_RTX (vi));
1328 200 : vi->cost = cost;
1329 : }
1330 :
1331 987 : 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 4723 : sel_move_insn (expr_t expr, int seqno, insn_t after)
1407 : {
1408 4723 : insn_t insn = EXPR_INSN_RTX (expr);
1409 4723 : basic_block bb = BLOCK_FOR_INSN (after);
1410 4723 : insn_t next = NEXT_INSN (after);
1411 :
1412 : /* Assert that in move_op we disconnected this insn properly. */
1413 4723 : gcc_assert (EXPR_VINSN (INSN_EXPR (insn)) != NULL);
1414 4723 : SET_PREV_INSN (insn) = after;
1415 4723 : SET_NEXT_INSN (insn) = next;
1416 :
1417 4723 : SET_NEXT_INSN (after) = insn;
1418 4723 : SET_PREV_INSN (next) = insn;
1419 :
1420 : /* Update links from insn to bb and vice versa. */
1421 4723 : df_insn_change_bb (insn, bb);
1422 4723 : if (BB_END (bb) == after)
1423 739 : BB_END (bb) = insn;
1424 :
1425 4723 : prepare_insn_expr (insn, seqno);
1426 4723 : 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 93406 : 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 93406 : expr_history_def *arr;
1443 93406 : int i, j, len = vect.length ();
1444 :
1445 2289 : if (len == 0)
1446 : {
1447 91117 : *indp = 0;
1448 91117 : 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 48810 : find_in_history_vect (vec<expr_history_def> vect, rtx insn,
1484 : vinsn_t new_vinsn, bool originators_p)
1485 : {
1486 48810 : int ind;
1487 :
1488 48810 : if (find_in_history_vect_1 (vect, INSN_UID (insn), new_vinsn,
1489 : false, &ind))
1490 162 : return ind;
1491 :
1492 48648 : 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 635 : 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 635 : vec<expr_history_def> vect = *pvect;
1516 635 : expr_history_def temp;
1517 635 : bool res;
1518 635 : int ind;
1519 :
1520 635 : res = find_in_history_vect_1 (vect, uid, new_expr_vinsn, true, &ind);
1521 :
1522 635 : 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 397 : temp.uid = uid;
1535 397 : temp.old_expr_vinsn = old_expr_vinsn;
1536 397 : temp.new_expr_vinsn = new_expr_vinsn;
1537 397 : temp.spec_ds = spec_ds;
1538 397 : temp.type = type;
1539 :
1540 397 : vinsn_attach (old_expr_vinsn);
1541 397 : vinsn_attach (new_expr_vinsn);
1542 397 : vect.safe_insert (ind, temp);
1543 397 : *pvect = vect;
1544 : }
1545 :
1546 : /* Free history vector PVECT. */
1547 : static void
1548 174450 : free_history_vect (vec<expr_history_def> &pvect)
1549 : {
1550 174450 : unsigned i;
1551 174450 : expr_history_def *phist;
1552 :
1553 174450 : if (! pvect.exists ())
1554 174450 : return;
1555 :
1556 4602 : for (i = 0; pvect.iterate (i, &phist); i++)
1557 : {
1558 2504 : vinsn_detach (phist->old_expr_vinsn);
1559 2504 : vinsn_detach (phist->new_expr_vinsn);
1560 : }
1561 :
1562 2098 : pvect.release ();
1563 : }
1564 :
1565 : /* Merge vector FROM to PVECT. */
1566 : static void
1567 9817 : merge_history_vect (vec<expr_history_def> *pvect,
1568 : vec<expr_history_def> from)
1569 : {
1570 9817 : expr_history_def *phist;
1571 9817 : int i;
1572 :
1573 : /* We keep this vector sorted. */
1574 10061 : 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 9817 : }
1579 :
1580 : /* Compare two vinsns as rhses if possible and as vinsns otherwise. */
1581 : bool
1582 297814 : vinsn_equal_p (vinsn_t x, vinsn_t y)
1583 : {
1584 297814 : rtx_equal_p_callback_function repcf;
1585 :
1586 297814 : if (x == y)
1587 : return true;
1588 :
1589 266747 : if (VINSN_TYPE (x) != VINSN_TYPE (y))
1590 : return false;
1591 :
1592 124449 : 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 167302 : 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 167302 : EXPR_VINSN (expr) = vi;
1624 167302 : EXPR_SPEC (expr) = spec;
1625 167302 : EXPR_USEFULNESS (expr) = use;
1626 167302 : EXPR_PRIORITY (expr) = priority;
1627 167302 : EXPR_PRIORITY_ADJ (expr) = 0;
1628 167302 : EXPR_SCHED_TIMES (expr) = sched_times;
1629 167302 : EXPR_ORIG_BB_INDEX (expr) = orig_bb_index;
1630 167302 : EXPR_ORIG_SCHED_CYCLE (expr) = orig_sched_cycle;
1631 167302 : EXPR_SPEC_DONE_DS (expr) = spec_done_ds;
1632 167302 : EXPR_SPEC_TO_CHECK_DS (expr) = spec_to_check_ds;
1633 :
1634 137870 : if (history.exists ())
1635 1722 : EXPR_HISTORY_OF_CHANGES (expr) = history;
1636 : else
1637 140521 : EXPR_HISTORY_OF_CHANGES (expr).create (0);
1638 :
1639 167302 : EXPR_TARGET_AVAILABLE (expr) = target_available;
1640 167302 : EXPR_WAS_SUBSTITUTED (expr) = was_substituted;
1641 167302 : EXPR_WAS_RENAMED (expr) = was_renamed;
1642 167302 : EXPR_NEEDS_SPEC_CHECK_P (expr) = needs_spec_check_p;
1643 167302 : EXPR_CANT_MOVE (expr) = cant_move;
1644 0 : }
1645 :
1646 : /* Make a copy of the expr FROM into the expr TO. */
1647 : void
1648 137870 : copy_expr (expr_t to, expr_t from)
1649 : {
1650 137870 : vec<expr_history_def> temp = vNULL;
1651 :
1652 137870 : if (EXPR_HISTORY_OF_CHANGES (from).exists ())
1653 : {
1654 1722 : unsigned i;
1655 1722 : expr_history_def *phist;
1656 :
1657 1722 : temp = EXPR_HISTORY_OF_CHANGES (from).copy ();
1658 3829 : for (i = 0;
1659 3829 : temp.iterate (i, &phist);
1660 : i++)
1661 : {
1662 2107 : vinsn_attach (phist->old_expr_vinsn);
1663 2107 : vinsn_attach (phist->new_expr_vinsn);
1664 : }
1665 : }
1666 :
1667 137870 : 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 : EXPR_TARGET_AVAILABLE (from), EXPR_WAS_SUBSTITUTED (from),
1673 : EXPR_WAS_RENAMED (from), EXPR_NEEDS_SPEC_CHECK_P (from),
1674 : EXPR_CANT_MOVE (from));
1675 137870 : }
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 25059 : copy_expr_onside (expr_t to, expr_t from)
1681 : {
1682 25059 : 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 25059 : vNULL,
1686 : EXPR_TARGET_AVAILABLE (from), EXPR_WAS_SUBSTITUTED (from),
1687 : EXPR_WAS_RENAMED (from), EXPR_NEEDS_SPEC_CHECK_P (from),
1688 : EXPR_CANT_MOVE (from));
1689 25059 : }
1690 :
1691 : /* Prepare the expr of INSN for scheduling. Used when moving insn and when
1692 : initializing new insns. */
1693 : static void
1694 7148 : prepare_insn_expr (insn_t insn, int seqno)
1695 : {
1696 7148 : expr_t expr = INSN_EXPR (insn);
1697 7148 : ds_t ds;
1698 :
1699 7148 : INSN_SEQNO (insn) = seqno;
1700 7148 : EXPR_ORIG_BB_INDEX (expr) = BLOCK_NUM (insn);
1701 7148 : EXPR_SPEC (expr) = 0;
1702 7148 : EXPR_ORIG_SCHED_CYCLE (expr) = 0;
1703 7148 : EXPR_WAS_SUBSTITUTED (expr) = 0;
1704 7148 : EXPR_WAS_RENAMED (expr) = 0;
1705 7148 : EXPR_TARGET_AVAILABLE (expr) = 1;
1706 7148 : 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 7148 : ds = EXPR_SPEC_DONE_DS (expr);
1714 7148 : if (ds)
1715 0 : EXPR_SPEC_DONE_DS (expr) = ds_get_max_dep_weak (ds);
1716 :
1717 7148 : free_history_vect (EXPR_HISTORY_OF_CHANGES (expr));
1718 7148 : }
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 167302 : clear_expr (expr_t expr)
1888 : {
1889 :
1890 167302 : vinsn_detach (EXPR_VINSN (expr));
1891 167302 : EXPR_VINSN (expr) = NULL;
1892 :
1893 167302 : free_history_vect (EXPR_HISTORY_OF_CHANGES (expr));
1894 167302 : }
1895 :
1896 : /* For a given LV_SET, mark EXPR having unavailable target register. */
1897 : static void
1898 10383 : set_unavailable_target_for_expr (expr_t expr, regset lv_set)
1899 : {
1900 10383 : if (EXPR_SEPARABLE_P (expr))
1901 : {
1902 5733 : if (REG_P (EXPR_LHS (expr))
1903 5733 : && 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 4650 : unsigned regno;
1934 4650 : reg_set_iterator rsi;
1935 :
1936 6644 : EXECUTE_IF_SET_IN_REG_SET (VINSN_REG_SETS (EXPR_VINSN (expr)),
1937 : 0, regno, rsi)
1938 3949 : if (bitmap_bit_p (lv_set, regno))
1939 : {
1940 1955 : EXPR_TARGET_AVAILABLE (expr) = false;
1941 1955 : break;
1942 : }
1943 :
1944 6337 : EXECUTE_IF_SET_IN_REG_SET (VINSN_REG_CLOBBERS (EXPR_VINSN (expr)),
1945 : 0, regno, rsi)
1946 1704 : if (bitmap_bit_p (lv_set, regno))
1947 : {
1948 17 : EXPR_TARGET_AVAILABLE (expr) = false;
1949 17 : break;
1950 : }
1951 : }
1952 10383 : }
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 8339 : expr_dest_reg (expr_t expr)
2014 : {
2015 8339 : rtx dest = VINSN_LHS (EXPR_VINSN (expr));
2016 :
2017 8339 : if (dest != NULL_RTX && REG_P (dest))
2018 8339 : return dest;
2019 :
2020 : return NULL_RTX;
2021 : }
2022 :
2023 : /* Returns the REGNO of the R's destination. */
2024 : unsigned
2025 7073 : expr_dest_regno (expr_t expr)
2026 : {
2027 7073 : rtx dest = expr_dest_reg (expr);
2028 :
2029 7073 : gcc_assert (dest != NULL_RTX);
2030 7073 : 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 6899 : mark_unavailable_targets (av_set_t join_set, av_set_t av_set, regset lv_set)
2037 : {
2038 6899 : expr_t expr;
2039 6899 : av_set_iterator avi;
2040 :
2041 13933 : FOR_EACH_EXPR (expr, avi, join_set)
2042 7034 : if (av_set_lookup (av_set, EXPR_VINSN (expr)) == NULL)
2043 7034 : set_unavailable_target_for_expr (expr, lv_set);
2044 6899 : }
2045 :
2046 :
2047 : /* Returns true if REG (at least partially) is present in REGS. */
2048 : bool
2049 7153 : register_unavailable_p (regset regs, rtx reg)
2050 : {
2051 7153 : unsigned regno, end_regno;
2052 :
2053 7153 : regno = REGNO (reg);
2054 7153 : if (bitmap_bit_p (regs, regno))
2055 : return true;
2056 :
2057 5548 : end_regno = END_REGNO (reg);
2058 :
2059 5548 : 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 136563 : av_set_add_element (av_set_t *setp)
2072 : {
2073 : /* Insert at the beginning of the list. */
2074 0 : _list_add (setp);
2075 136563 : return *setp;
2076 : }
2077 :
2078 : /* Add EXPR to SETP. */
2079 : void
2080 134645 : av_set_add (av_set_t *setp, expr_t expr)
2081 : {
2082 134645 : av_set_t elem;
2083 :
2084 134645 : gcc_assert (!INSN_NOP_P (EXPR_INSN_RTX (expr)));
2085 134645 : elem = av_set_add_element (setp);
2086 134645 : copy_expr (_AV_SET_EXPR (elem), expr);
2087 134645 : }
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 134645 : av_set_iter_remove (av_set_iterator *ip)
2102 : {
2103 134645 : clear_expr (_AV_SET_EXPR (*ip->lp));
2104 134645 : _list_iter_remove (ip);
2105 134645 : }
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 203866 : av_set_lookup (av_set_t set, vinsn_t sought_vinsn)
2112 : {
2113 203866 : expr_t expr;
2114 203866 : av_set_iterator i;
2115 :
2116 440101 : FOR_EACH_EXPR (expr, i, set)
2117 272926 : 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 3787 : av_set_lookup_and_remove (av_set_t *setp, vinsn_t sought_vinsn)
2125 : {
2126 3787 : expr_t expr;
2127 3787 : av_set_iterator i;
2128 :
2129 10676 : FOR_EACH_EXPR_1 (expr, i, setp)
2130 8807 : 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 389 : av_set_lookup_other_equiv_expr (av_set_t set, expr_t expr)
2143 : {
2144 389 : expr_t cur_expr;
2145 389 : av_set_iterator i;
2146 :
2147 2112 : FOR_EACH_EXPR (cur_expr, i, set)
2148 : {
2149 1727 : if (cur_expr == expr)
2150 385 : continue;
2151 1342 : 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 389 : merge_with_other_exprs (av_set_t *avp, av_set_iterator *ip, expr_t expr)
2161 : {
2162 389 : expr_t expr2;
2163 :
2164 389 : expr2 = av_set_lookup_other_equiv_expr (*avp, expr);
2165 389 : 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 27758 : av_set_is_in_p (av_set_t set, vinsn_t vi)
2187 : {
2188 27758 : return av_set_lookup (set, vi) != NULL;
2189 : }
2190 :
2191 : /* Return a copy of SET. */
2192 : av_set_t
2193 35969 : av_set_copy (av_set_t set)
2194 : {
2195 35969 : expr_t expr;
2196 35969 : av_set_iterator i;
2197 35969 : av_set_t res = NULL;
2198 :
2199 110326 : FOR_EACH_EXPR (expr, i, set)
2200 74357 : av_set_add (&res, expr);
2201 :
2202 35969 : 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 60723 : join_distinct_sets (av_set_t *to_tailp, av_set_t *fromp)
2210 : {
2211 60723 : gcc_assert (*to_tailp == NULL);
2212 60723 : *to_tailp = *fromp;
2213 60723 : *fromp = NULL;
2214 60723 : }
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 58509 : av_set_union_and_clear (av_set_t *top, av_set_t *fromp, insn_t insn)
2220 : {
2221 58509 : expr_t expr1;
2222 58509 : av_set_iterator i;
2223 :
2224 : /* Delete from TOP all exprs, that present in FROMP. */
2225 156129 : FOR_EACH_EXPR_1 (expr1, i, top)
2226 : {
2227 48810 : expr_t expr2 = av_set_lookup (*fromp, EXPR_VINSN (expr1));
2228 :
2229 48810 : if (expr2)
2230 : {
2231 0 : merge_expr (expr2, expr1, insn);
2232 0 : av_set_iter_remove (&i);
2233 : }
2234 : }
2235 :
2236 58509 : join_distinct_sets (i.lp, fromp);
2237 58509 : }
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 1107 : 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 1107 : expr_t expr1;
2246 1107 : av_set_iterator i;
2247 1107 : av_set_t *to_tailp, in_both_set = NULL;
2248 :
2249 : /* Delete from TOP all exprs, that present in FROMP. */
2250 8681 : FOR_EACH_EXPR_1 (expr1, i, top)
2251 : {
2252 3787 : expr_t expr2 = av_set_lookup_and_remove (fromp, EXPR_VINSN (expr1));
2253 :
2254 3787 : 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 1869 : set_unavailable_target_for_expr (expr1, from_lv_set);
2282 : }
2283 1107 : to_tailp = i.lp;
2284 :
2285 : /* These expressions are not present in TOP. Check liveness
2286 : restrictions on TO_LV_SET. */
2287 4067 : FOR_EACH_EXPR (expr1, i, *fromp)
2288 1480 : set_unavailable_target_for_expr (expr1, to_lv_set);
2289 :
2290 1107 : join_distinct_sets (i.lp, &in_both_set);
2291 1107 : join_distinct_sets (to_tailp, fromp);
2292 1107 : }
2293 :
2294 : /* Clear av_set pointed to by SETP. */
2295 : void
2296 60629 : av_set_clear (av_set_t *setp)
2297 : {
2298 60629 : expr_t expr;
2299 60629 : av_set_iterator i;
2300 :
2301 232371 : FOR_EACH_EXPR_1 (expr, i, setp)
2302 85871 : av_set_iter_remove (&i);
2303 :
2304 60629 : gcc_assert (*setp == NULL);
2305 60629 : }
2306 :
2307 : /* Leave only one non-speculative element in the SETP. */
2308 : void
2309 15010 : av_set_leave_one_nonspec (av_set_t *setp)
2310 : {
2311 15010 : expr_t expr;
2312 15010 : av_set_iterator i;
2313 15010 : bool has_one_nonspec = false;
2314 :
2315 : /* Keep all speculative exprs, and leave one non-speculative
2316 : (the first one). */
2317 45030 : FOR_EACH_EXPR_1 (expr, i, setp)
2318 : {
2319 15010 : if (!EXPR_SPEC_DONE_DS (expr))
2320 : {
2321 15010 : if (has_one_nonspec)
2322 0 : av_set_iter_remove (&i);
2323 : else
2324 : has_one_nonspec = true;
2325 : }
2326 : }
2327 15010 : }
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 4602 : av_set_substract_cond_branches (av_set_t *avp)
2347 : {
2348 4602 : av_set_iterator i;
2349 4602 : expr_t expr;
2350 :
2351 29204 : FOR_EACH_EXPR_1 (expr, i, avp)
2352 12301 : if (vinsn_cond_branch_p (EXPR_VINSN (expr)))
2353 422 : av_set_iter_remove (&i);
2354 4602 : }
2355 :
2356 : /* Multiplies usefulness attribute of each member of av-set *AVP by
2357 : value PROB / ALL_PROB. */
2358 : void
2359 6061 : av_set_split_usefulness (av_set_t av, int prob, int all_prob)
2360 : {
2361 6061 : av_set_iterator i;
2362 6061 : expr_t expr;
2363 :
2364 25903 : FOR_EACH_EXPR (expr, i, av)
2365 19842 : EXPR_USEFULNESS (expr) = (all_prob
2366 18393 : ? (EXPR_USEFULNESS (expr) * prob) / all_prob
2367 : : 0);
2368 6061 : }
2369 :
2370 : /* Leave in AVP only those expressions, which are present in AV,
2371 : and return it, merging history expressions. */
2372 : void
2373 8408 : av_set_code_motion_filter (av_set_t *avp, av_set_t av)
2374 : {
2375 8408 : av_set_iterator i;
2376 8408 : expr_t expr, expr2;
2377 :
2378 25438 : FOR_EACH_EXPR_1 (expr, i, avp)
2379 8515 : 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 7641 : merge_history_vect (&EXPR_HISTORY_OF_CHANGES (expr),
2388 : EXPR_HISTORY_OF_CHANGES (expr2));
2389 8408 : }
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 5062 : setup_id_for_insn (idata_t id, insn_t insn, bool force_unique_p)
2417 : {
2418 5062 : 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 5062 : type = GET_CODE (insn);
2424 :
2425 : /* Only regular insns could be cloned. */
2426 5062 : if (type == INSN && !force_unique_p)
2427 : type = SET;
2428 1668 : else if (type == JUMP_INSN && simplejump_p (insn))
2429 : type = PC;
2430 1472 : else if (type == DEBUG_INSN)
2431 44 : type = !force_unique_p ? USE : INSN;
2432 :
2433 5062 : IDATA_TYPE (id) = type;
2434 5062 : IDATA_REG_SETS (id) = get_clear_regset_from_pool ();
2435 5062 : IDATA_REG_USES (id) = get_clear_regset_from_pool ();
2436 5062 : IDATA_REG_CLOBBERS (id) = get_clear_regset_from_pool ();
2437 5062 : }
2438 :
2439 : /* Start initializing insn data. */
2440 : static void
2441 660 : deps_init_id_start_insn (insn_t insn)
2442 : {
2443 660 : gcc_assert (deps_init_id_data.where == DEPS_IN_NOWHERE);
2444 :
2445 660 : setup_id_for_insn (deps_init_id_data.id, insn,
2446 : deps_init_id_data.force_unique_p);
2447 660 : deps_init_id_data.where = DEPS_IN_INSN;
2448 660 : }
2449 :
2450 : /* Start initializing lhs data. */
2451 : static void
2452 647 : deps_init_id_start_lhs (rtx lhs)
2453 : {
2454 647 : gcc_assert (deps_init_id_data.where == DEPS_IN_INSN);
2455 647 : gcc_assert (IDATA_LHS (deps_init_id_data.id) == NULL);
2456 :
2457 647 : if (IDATA_TYPE (deps_init_id_data.id) == SET)
2458 : {
2459 647 : IDATA_LHS (deps_init_id_data.id) = lhs;
2460 647 : deps_init_id_data.where = DEPS_IN_LHS;
2461 : }
2462 647 : }
2463 :
2464 : /* Finish initializing lhs data. */
2465 : static void
2466 647 : deps_init_id_finish_lhs (void)
2467 : {
2468 647 : deps_init_id_data.where = DEPS_IN_INSN;
2469 647 : }
2470 :
2471 : /* Note a set of REGNO. */
2472 : static void
2473 652 : deps_init_id_note_reg_set (int regno)
2474 : {
2475 652 : haifa_note_reg_set (regno);
2476 :
2477 652 : if (deps_init_id_data.where == DEPS_IN_RHS)
2478 0 : deps_init_id_data.force_use_p = true;
2479 :
2480 652 : if (IDATA_TYPE (deps_init_id_data.id) != PC)
2481 652 : 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 652 : if (IN_RANGE (regno, FIRST_STACK_REG, LAST_STACK_REG))
2487 0 : deps_init_id_data.force_use_p = true;
2488 : #endif
2489 652 : }
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 654 : deps_init_id_note_reg_use (int regno)
2507 : {
2508 654 : haifa_note_reg_use (regno);
2509 :
2510 654 : if (IDATA_TYPE (deps_init_id_data.id) != PC)
2511 654 : SET_REGNO_REG_SET (IDATA_REG_USES (deps_init_id_data.id), regno);
2512 654 : }
2513 :
2514 : /* Start initializing rhs data. */
2515 : static void
2516 647 : deps_init_id_start_rhs (rtx rhs)
2517 : {
2518 647 : gcc_assert (deps_init_id_data.where == DEPS_IN_INSN);
2519 :
2520 : /* And there was no sel_deps_reset_to_insn (). */
2521 647 : if (IDATA_LHS (deps_init_id_data.id) != NULL)
2522 : {
2523 647 : IDATA_RHS (deps_init_id_data.id) = rhs;
2524 647 : deps_init_id_data.where = DEPS_IN_RHS;
2525 : }
2526 647 : }
2527 :
2528 : /* Finish initializing rhs data. */
2529 : static void
2530 647 : deps_init_id_finish_rhs (void)
2531 : {
2532 647 : gcc_assert (deps_init_id_data.where == DEPS_IN_RHS
2533 : || deps_init_id_data.where == DEPS_IN_INSN);
2534 647 : deps_init_id_data.where = DEPS_IN_INSN;
2535 647 : }
2536 :
2537 : /* Finish initializing insn data. */
2538 : static void
2539 660 : deps_init_id_finish_insn (void)
2540 : {
2541 660 : gcc_assert (deps_init_id_data.where == DEPS_IN_INSN);
2542 :
2543 660 : if (IDATA_TYPE (deps_init_id_data.id) == SET)
2544 : {
2545 656 : rtx lhs = IDATA_LHS (deps_init_id_data.id);
2546 656 : rtx rhs = IDATA_RHS (deps_init_id_data.id);
2547 :
2548 647 : if (lhs == NULL || rhs == NULL || !lhs_and_rhs_separable_p (lhs, rhs)
2549 986 : || 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 326 : gcc_assert (IDATA_TYPE (deps_init_id_data.id) == SET);
2556 326 : gcc_assert (!lhs == !rhs);
2557 :
2558 326 : IDATA_TYPE (deps_init_id_data.id) = USE;
2559 : }
2560 : }
2561 :
2562 660 : deps_init_id_data.where = DEPS_IN_NOWHERE;
2563 660 : }
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 4402 : setup_id_lhs_rhs (idata_t id, insn_t insn, bool force_unique_p)
2594 : {
2595 4402 : rtx pat = PATTERN (insn);
2596 :
2597 4402 : if (NONJUMP_INSN_P (insn)
2598 3473 : && GET_CODE (pat) == SET
2599 2668 : && !force_unique_p)
2600 : {
2601 2095 : IDATA_RHS (id) = SET_SRC (pat);
2602 2095 : IDATA_LHS (id) = SET_DEST (pat);
2603 : }
2604 : else
2605 2307 : IDATA_LHS (id) = IDATA_RHS (id) = NULL;
2606 4402 : }
2607 :
2608 : /* Possibly downgrade INSN to USE. */
2609 : static void
2610 4402 : maybe_downgrade_id_to_use (idata_t id, insn_t insn)
2611 : {
2612 4402 : bool must_be_use = false;
2613 4402 : df_ref def;
2614 4402 : rtx lhs = IDATA_LHS (id);
2615 4402 : rtx rhs = IDATA_RHS (id);
2616 :
2617 : /* We downgrade only SETs. */
2618 4402 : if (IDATA_TYPE (id) != SET)
2619 : return;
2620 :
2621 2738 : if (!lhs || !lhs_and_rhs_separable_p (lhs, rhs))
2622 : {
2623 1692 : IDATA_TYPE (id) = USE;
2624 1692 : return;
2625 : }
2626 :
2627 2091 : FOR_EACH_INSN_DEF (def, insn)
2628 : {
2629 1048 : if (DF_REF_INSN (def)
2630 1048 : && DF_REF_FLAGS_IS_SET (def, DF_REF_PRE_POST_MODIFY)
2631 1050 : && 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 1046 : 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 1046 : 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 5062 : setup_id_implicit_regs (idata_t id, insn_t insn)
2656 : {
2657 5062 : if (reload_completed)
2658 : return;
2659 :
2660 1643 : HARD_REG_SET temp;
2661 :
2662 1643 : get_implicit_reg_pending_clobbers (&temp, insn);
2663 1643 : IOR_REG_SET_HRS (IDATA_REG_SETS (id), temp);
2664 : }
2665 :
2666 : /* Setup register sets describing INSN in ID. */
2667 : static void
2668 4402 : setup_id_reg_sets (idata_t id, insn_t insn)
2669 : {
2670 4402 : struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
2671 4402 : df_ref def, use;
2672 4402 : regset tmp = get_clear_regset_from_pool ();
2673 :
2674 22144 : FOR_EACH_INSN_INFO_DEF (def, insn_info)
2675 : {
2676 17742 : unsigned int regno = DF_REF_REGNO (def);
2677 :
2678 : /* Post modifies are treated like clobbers by sched-deps.cc. */
2679 17742 : 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 16886 : else if (! DF_REF_FLAGS_IS_SET (def, DF_REF_MAY_CLOBBER))
2683 : {
2684 3046 : 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 3046 : 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 17742 : if (DF_REF_FLAGS_IS_SET (def, DF_REF_CONDITIONAL)
2695 17742 : || regno == STACK_POINTER_REGNUM)
2696 283 : bitmap_set_bit (tmp, regno);
2697 : }
2698 :
2699 9394 : FOR_EACH_INSN_INFO_USE (use, insn_info)
2700 : {
2701 4992 : 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 4992 : if (bitmap_bit_p (tmp, regno))
2706 283 : bitmap_clear_bit (tmp, regno);
2707 4709 : else if (! DF_REF_FLAGS_IS_SET (use, DF_REF_CALL_STACK_USAGE))
2708 : {
2709 4541 : 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 4541 : 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 4402 : setup_id_implicit_regs (id, insn);
2722 :
2723 4402 : return_regset_to_pool (tmp);
2724 4402 : }
2725 :
2726 : /* Initialize instruction data for INSN in ID using DF's data. */
2727 : static void
2728 4402 : init_id_from_df (idata_t id, insn_t insn, bool force_unique_p)
2729 : {
2730 4402 : gcc_assert (DF_INSN_UID_SAFE_GET (INSN_UID (insn)) != NULL);
2731 :
2732 4402 : setup_id_for_insn (id, insn, force_unique_p);
2733 4402 : setup_id_lhs_rhs (id, insn, force_unique_p);
2734 :
2735 4402 : if (INSN_NOP_P (insn))
2736 : return;
2737 :
2738 4402 : maybe_downgrade_id_to_use (id, insn);
2739 4402 : setup_id_reg_sets (id, insn);
2740 : }
2741 :
2742 : /* Initialize instruction data for INSN in ID. */
2743 : static void
2744 660 : deps_init_id (idata_t id, insn_t insn, bool force_unique_p)
2745 : {
2746 660 : class deps_desc _dc, *dc = &_dc;
2747 :
2748 660 : deps_init_id_data.where = DEPS_IN_NOWHERE;
2749 660 : deps_init_id_data.id = id;
2750 660 : deps_init_id_data.force_unique_p = force_unique_p;
2751 660 : deps_init_id_data.force_use_p = false;
2752 :
2753 660 : init_deps (dc, false);
2754 660 : memcpy (&deps_init_id_sched_deps_info,
2755 : &const_deps_init_id_sched_deps_info,
2756 : sizeof (deps_init_id_sched_deps_info));
2757 660 : if (spec_info != NULL)
2758 0 : deps_init_id_sched_deps_info.generate_spec_deps = 1;
2759 660 : sched_deps_info = &deps_init_id_sched_deps_info;
2760 :
2761 660 : deps_analyze_insn (dc, insn);
2762 : /* Implicit reg clobbers received from sched-deps separately. */
2763 660 : setup_id_implicit_regs (id, insn);
2764 :
2765 660 : free_deps (dc);
2766 660 : deps_init_id_data.id = NULL;
2767 660 : }
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 2288 : sched_scan (const struct sched_scan_info_def *ssi, bb_vec_t bbs)
2795 : {
2796 2288 : unsigned i;
2797 2288 : basic_block bb;
2798 :
2799 2288 : if (ssi->extend_bb)
2800 810 : ssi->extend_bb ();
2801 :
2802 2288 : if (ssi->init_bb)
2803 5386 : FOR_EACH_VEC_ELT (bbs, i, bb)
2804 3098 : ssi->init_bb (bb);
2805 :
2806 2288 : if (ssi->extend_insn)
2807 739 : ssi->extend_insn ();
2808 :
2809 2288 : if (ssi->init_insn)
2810 3502 : FOR_EACH_VEC_ELT (bbs, i, bb)
2811 : {
2812 2024 : rtx_insn *insn;
2813 :
2814 13910 : FOR_BB_INSNS (bb, insn)
2815 11886 : ssi->init_insn (insn);
2816 : }
2817 2288 : }
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 20633 : first_time_insn_init (insn_t insn)
2825 : {
2826 20633 : 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 337 : eq_transformed_insns (const void *p, const void *q)
2839 : {
2840 337 : rtx_insn *i1 =
2841 337 : VINSN_INSN_RTX (((const struct transformed_insns *) p)->vinsn_old);
2842 337 : rtx_insn *i2 =
2843 337 : VINSN_INSN_RTX (((const struct transformed_insns *) q)->vinsn_old);
2844 :
2845 337 : 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 64 : free_transformed_insns (void *p)
2853 : {
2854 64 : struct transformed_insns *pti = (struct transformed_insns *) p;
2855 :
2856 64 : vinsn_detach (pti->vinsn_old);
2857 64 : vinsn_detach (pti->vinsn_new);
2858 64 : free (pti);
2859 64 : }
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 5642 : 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 5642 : gcc_assert (first_time_insn_init (insn));
2869 :
2870 : /* These are needed for nops too. */
2871 5642 : INSN_LIVE (insn) = get_regset_from_pool ();
2872 5642 : INSN_LIVE_VALID_P (insn) = false;
2873 :
2874 5642 : if (!INSN_NOP_P (insn))
2875 : {
2876 4814 : INSN_ANALYZED_DEPS (insn) = BITMAP_ALLOC (NULL);
2877 4814 : INSN_FOUND_DEPS (insn) = BITMAP_ALLOC (NULL);
2878 4814 : INSN_TRANSFORMED_INSNS (insn)
2879 4814 : = htab_create (16, hash_transformed_insns,
2880 : eq_transformed_insns, free_transformed_insns);
2881 4814 : init_deps (&INSN_DEPS_CONTEXT (insn), true);
2882 : }
2883 5642 : }
2884 :
2885 : /* Free almost all above data for INSN that is scheduled already.
2886 : Used for extra-large basic blocks. */
2887 : void
2888 8046 : free_data_for_scheduled_insn (insn_t insn)
2889 : {
2890 8046 : gcc_assert (! first_time_insn_init (insn));
2891 :
2892 8046 : if (! INSN_ANALYZED_DEPS (insn))
2893 : return;
2894 :
2895 4520 : BITMAP_FREE (INSN_ANALYZED_DEPS (insn));
2896 4520 : BITMAP_FREE (INSN_FOUND_DEPS (insn));
2897 4520 : htab_delete (INSN_TRANSFORMED_INSNS (insn));
2898 :
2899 : /* This is allocated only for bookkeeping insns. */
2900 4520 : if (INSN_ORIGINATORS (insn))
2901 152 : BITMAP_FREE (INSN_ORIGINATORS (insn));
2902 4520 : free_deps (&INSN_DEPS_CONTEXT (insn));
2903 :
2904 4520 : 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 4520 : (&INSN_DEPS_CONTEXT (insn))->readonly = 0;
2909 : }
2910 :
2911 : /* Free the same data as above for INSN. */
2912 : static void
2913 4520 : free_first_time_insn_data (insn_t insn)
2914 : {
2915 4520 : gcc_assert (! first_time_insn_init (insn));
2916 :
2917 4520 : free_data_for_scheduled_insn (insn);
2918 4520 : return_regset_to_pool (INSN_LIVE (insn));
2919 4520 : INSN_LIVE (insn) = NULL;
2920 4520 : INSN_LIVE_VALID_P (insn) = false;
2921 4520 : }
2922 :
2923 : /* Initialize region-scope data structures for basic blocks. */
2924 : static void
2925 1010 : init_global_and_expr_for_bb (basic_block bb)
2926 : {
2927 1010 : if (sel_bb_empty_p (bb))
2928 : return;
2929 :
2930 981 : 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 5859 : init_global_and_expr_for_insn (insn_t insn)
2945 : {
2946 5859 : if (LABEL_P (insn))
2947 : return;
2948 :
2949 5371 : if (NOTE_INSN_BASIC_BLOCK_P (insn))
2950 : {
2951 1010 : init_global_data.prev_insn = NULL;
2952 1010 : return;
2953 : }
2954 :
2955 4361 : gcc_assert (INSN_P (insn));
2956 :
2957 4361 : if (SCHED_GROUP_P (insn))
2958 : /* Setup a sched_group. */
2959 : {
2960 333 : insn_t prev_insn = init_global_data.prev_insn;
2961 :
2962 333 : if (prev_insn)
2963 0 : INSN_SCHED_NEXT (prev_insn) = insn;
2964 :
2965 333 : init_global_data.prev_insn = insn;
2966 : }
2967 : else
2968 4028 : init_global_data.prev_insn = NULL;
2969 :
2970 4361 : if (GET_CODE (PATTERN (insn)) == ASM_INPUT
2971 4361 : || asm_noperands (PATTERN (insn)) >= 0)
2972 : /* Mark INSN as an asm. */
2973 10 : INSN_ASM_P (insn) = true;
2974 :
2975 4361 : {
2976 4361 : bool force_unique_p;
2977 4361 : 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 4361 : 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 3979 : if (CANT_MOVE (insn)
3002 2769 : || INSN_ASM_P (insn)
3003 2761 : || SCHED_GROUP_P (insn)
3004 2761 : || CALL_P (insn)
3005 : /* Exception handling insns are always unique. */
3006 2761 : || (cfun->can_throw_non_call_exceptions && can_throw_internal (insn))
3007 : /* TRAP_IF though have an INSN code is control_flow_insn_p (). */
3008 2761 : || control_flow_insn_p (insn)
3009 2750 : || volatile_insn_p (PATTERN (insn))
3010 6728 : || (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 4361 : 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 4361 : init_expr (INSN_EXPR (insn), vinsn_create (insn, force_unique_p), 0,
3026 4361 : REG_BR_PROB_BASE, INSN_PRIORITY (insn), 0, BLOCK_NUM (insn),
3027 4361 : spec_done_ds, 0, 0, vNULL, true,
3028 4361 : false, false, false, CANT_MOVE (insn));
3029 : }
3030 :
3031 4361 : init_first_time_insn_data (insn);
3032 : }
3033 :
3034 : /* Scan the region and initialize instruction data for basic blocks BBS. */
3035 : void
3036 739 : sel_init_global_and_expr (bb_vec_t bbs)
3037 : {
3038 : /* ??? It would be nice to implement push / pop scheme for sched_infos. */
3039 739 : 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 739 : sched_scan (&ssi, bbs);
3048 739 : }
3049 :
3050 : /* Finalize region-scope data structures for basic blocks. */
3051 : static void
3052 1014 : finish_global_and_expr_for_bb (basic_block bb)
3053 : {
3054 1014 : av_set_clear (&BB_AV_SET (bb));
3055 1014 : BB_AV_LEVEL (bb) = 0;
3056 1014 : }
3057 :
3058 : /* Finalize INSN's data. */
3059 : static void
3060 6027 : finish_global_and_expr_insn (insn_t insn)
3061 : {
3062 6027 : if (LABEL_P (insn) || NOTE_INSN_BASIC_BLOCK_P (insn))
3063 : return;
3064 :
3065 4520 : gcc_assert (INSN_P (insn));
3066 :
3067 4520 : if (INSN_LUID (insn) > 0)
3068 : {
3069 4520 : free_first_time_insn_data (insn);
3070 4520 : INSN_WS_LEVEL (insn) = 0;
3071 4520 : 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 4520 : gcc_assert (true || VINSN_COUNT (INSN_VINSN (insn)) == 1);
3077 4520 : clear_expr (INSN_EXPR (insn));
3078 : }
3079 : }
3080 :
3081 : /* Finalize per instruction data for the whole region. */
3082 : void
3083 739 : sel_finish_global_and_expr (void)
3084 : {
3085 739 : {
3086 739 : bb_vec_t bbs;
3087 739 : int i;
3088 :
3089 739 : bbs.create (current_nr_blocks);
3090 :
3091 2492 : for (i = 0; i < current_nr_blocks; i++)
3092 1014 : bbs.quick_push (BASIC_BLOCK_FOR_FN (cfun, BB_TO_BLOCK (i)));
3093 :
3094 : /* Clear AV_SETs and INSN_EXPRs. */
3095 739 : {
3096 739 : 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 739 : sched_scan (&ssi, bbs);
3105 : }
3106 :
3107 739 : bbs.release ();
3108 : }
3109 :
3110 739 : finish_insns ();
3111 739 : }
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 17782 : has_dependence_start_insn (insn_t insn ATTRIBUTE_UNUSED)
3141 : {
3142 17782 : gcc_assert (has_dependence_data.where == DEPS_IN_NOWHERE);
3143 :
3144 17782 : has_dependence_data.where = DEPS_IN_INSN;
3145 17782 : }
3146 :
3147 : /* Finish analyzing dependencies of an insn. */
3148 : static void
3149 17782 : has_dependence_finish_insn (void)
3150 : {
3151 17782 : gcc_assert (has_dependence_data.where == DEPS_IN_INSN);
3152 :
3153 17782 : has_dependence_data.where = DEPS_IN_NOWHERE;
3154 17782 : }
3155 :
3156 : /* Start analyzing dependencies of LHS. */
3157 : static void
3158 15642 : has_dependence_start_lhs (rtx lhs ATTRIBUTE_UNUSED)
3159 : {
3160 15642 : gcc_assert (has_dependence_data.where == DEPS_IN_INSN);
3161 :
3162 15642 : if (VINSN_LHS (has_dependence_data.con) != NULL)
3163 15064 : has_dependence_data.where = DEPS_IN_LHS;
3164 15642 : }
3165 :
3166 : /* Finish analyzing dependencies of an lhs. */
3167 : static void
3168 15642 : has_dependence_finish_lhs (void)
3169 : {
3170 15642 : has_dependence_data.where = DEPS_IN_INSN;
3171 15642 : }
3172 :
3173 : /* Start analyzing dependencies of RHS. */
3174 : static void
3175 15642 : has_dependence_start_rhs (rtx rhs ATTRIBUTE_UNUSED)
3176 : {
3177 15642 : gcc_assert (has_dependence_data.where == DEPS_IN_INSN);
3178 :
3179 15642 : if (VINSN_RHS (has_dependence_data.con) != NULL)
3180 15064 : has_dependence_data.where = DEPS_IN_RHS;
3181 15642 : }
3182 :
3183 : /* Start analyzing dependencies of an rhs. */
3184 : static void
3185 15642 : has_dependence_finish_rhs (void)
3186 : {
3187 15642 : gcc_assert (has_dependence_data.where == DEPS_IN_RHS
3188 : || has_dependence_data.where == DEPS_IN_INSN);
3189 :
3190 15642 : has_dependence_data.where = DEPS_IN_INSN;
3191 15642 : }
3192 :
3193 : /* Note a set of REGNO. */
3194 : static void
3195 16895 : has_dependence_note_reg_set (int regno)
3196 : {
3197 16895 : struct deps_reg *reg_last = &has_dependence_data.dc->reg_last[regno];
3198 :
3199 16895 : if (!sched_insns_conditions_mutex_p (has_dependence_data.pro,
3200 16895 : VINSN_INSN_RTX
3201 : (has_dependence_data.con)))
3202 : {
3203 16895 : ds_t *dsp = &has_dependence_data.has_dep_p[has_dependence_data.where];
3204 :
3205 16895 : if (reg_last->sets != NULL
3206 15785 : || reg_last->clobbers != NULL)
3207 1612 : *dsp = (*dsp & ~SPECULATIVE) | DEP_OUTPUT;
3208 :
3209 16895 : if (reg_last->uses || reg_last->implicit_sets)
3210 876 : *dsp = (*dsp & ~SPECULATIVE) | DEP_ANTI;
3211 : }
3212 16895 : }
3213 :
3214 : /* Note a clobber of REGNO. */
3215 : static void
3216 1585 : has_dependence_note_reg_clobber (int regno)
3217 : {
3218 1585 : struct deps_reg *reg_last = &has_dependence_data.dc->reg_last[regno];
3219 :
3220 1585 : if (!sched_insns_conditions_mutex_p (has_dependence_data.pro,
3221 1585 : VINSN_INSN_RTX
3222 : (has_dependence_data.con)))
3223 : {
3224 1585 : ds_t *dsp = &has_dependence_data.has_dep_p[has_dependence_data.where];
3225 :
3226 1585 : if (reg_last->sets)
3227 39 : *dsp = (*dsp & ~SPECULATIVE) | DEP_OUTPUT;
3228 :
3229 1585 : if (reg_last->uses || reg_last->implicit_sets)
3230 247 : *dsp = (*dsp & ~SPECULATIVE) | DEP_ANTI;
3231 : }
3232 1585 : }
3233 :
3234 : /* Note a use of REGNO. */
3235 : static void
3236 19790 : has_dependence_note_reg_use (int regno)
3237 : {
3238 19790 : struct deps_reg *reg_last = &has_dependence_data.dc->reg_last[regno];
3239 :
3240 19790 : if (!sched_insns_conditions_mutex_p (has_dependence_data.pro,
3241 19790 : VINSN_INSN_RTX
3242 : (has_dependence_data.con)))
3243 : {
3244 19790 : ds_t *dsp = &has_dependence_data.has_dep_p[has_dependence_data.where];
3245 :
3246 19790 : if (reg_last->sets)
3247 1851 : *dsp = (*dsp & ~SPECULATIVE) | DEP_TRUE;
3248 :
3249 19790 : 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 19790 : if (reg_last->uses)
3258 : {
3259 2727 : ds_t pro_spec_checked_ds;
3260 :
3261 2727 : pro_spec_checked_ds = INSN_SPEC_CHECKED_DS (has_dependence_data.pro);
3262 2727 : pro_spec_checked_ds = ds_get_max_dep_weak (pro_spec_checked_ds);
3263 :
3264 2727 : 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 19790 : }
3270 :
3271 : /* Note a memory dependence. */
3272 : static void
3273 443 : 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 443 : if (!sched_insns_conditions_mutex_p (has_dependence_data.pro,
3279 443 : VINSN_INSN_RTX (has_dependence_data.con)))
3280 : {
3281 443 : ds_t *dsp = &has_dependence_data.has_dep_p[has_dependence_data.where];
3282 :
3283 443 : *dsp = ds_full_merge (ds, *dsp, pending_mem, mem);
3284 : }
3285 443 : }
3286 :
3287 : /* Note a dependence. */
3288 : static void
3289 848 : has_dependence_note_dep (insn_t pro, ds_t ds ATTRIBUTE_UNUSED)
3290 : {
3291 848 : insn_t real_pro = has_dependence_data.pro;
3292 848 : 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 888 : && INSN_UID (NEXT_INSN (pro)) == INSN_UID (real_con))
3302 : return;
3303 :
3304 808 : if (!sched_insns_conditions_mutex_p (real_pro, real_con))
3305 : {
3306 808 : ds_t *dsp = &has_dependence_data.has_dep_p[has_dependence_data.where];
3307 :
3308 808 : *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 17782 : setup_has_dependence_sched_deps_info (void)
3359 : {
3360 17782 : memcpy (&has_dependence_sched_deps_info,
3361 : &const_has_dependence_sched_deps_info,
3362 : sizeof (has_dependence_sched_deps_info));
3363 :
3364 17782 : if (spec_info != NULL)
3365 0 : has_dependence_sched_deps_info.generate_spec_deps = 1;
3366 :
3367 17782 : sched_deps_info = &has_dependence_sched_deps_info;
3368 17782 : }
3369 :
3370 : /* Remove all dependences found and recorded in has_dependence_data array. */
3371 : void
3372 17782 : sel_clear_has_dependence (void)
3373 : {
3374 17782 : int i;
3375 :
3376 71128 : for (i = 0; i < DEPS_IN_NOWHERE; i++)
3377 53346 : has_dependence_data.has_dep_p[i] = 0;
3378 17782 : }
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 17972 : has_dependence_p (expr_t expr, insn_t pred, ds_t **has_dep_pp)
3384 : {
3385 17972 : int i;
3386 17972 : ds_t ds;
3387 17972 : class deps_desc *dc;
3388 :
3389 17972 : if (INSN_SIMPLEJUMP_P (pred))
3390 : /* Unconditional jump is just a transfer of control flow.
3391 : Ignore it. */
3392 : return false;
3393 :
3394 17782 : dc = &INSN_DEPS_CONTEXT (pred);
3395 :
3396 : /* Selective scheduling keeps the eager barrier form, so the reg_last entries
3397 : the callbacks below read are always materialised. */
3398 17782 : gcc_checking_assert (!dc->pending_barriers);
3399 :
3400 : /* We init this field lazily. */
3401 17782 : if (dc->reg_last == NULL)
3402 3313 : init_deps_reg_last (dc);
3403 :
3404 17782 : if (!dc->readonly)
3405 : {
3406 3313 : has_dependence_data.pro = NULL;
3407 : /* Initialize empty dep context with information about PRED. */
3408 3313 : advance_deps_context (dc, pred);
3409 3313 : dc->readonly = 1;
3410 : }
3411 :
3412 17782 : has_dependence_data.where = DEPS_IN_NOWHERE;
3413 17782 : has_dependence_data.pro = pred;
3414 17782 : has_dependence_data.con = EXPR_VINSN (expr);
3415 17782 : has_dependence_data.dc = dc;
3416 :
3417 17782 : sel_clear_has_dependence ();
3418 :
3419 : /* Now catch all dependencies that would be generated between PRED and
3420 : INSN. */
3421 17782 : setup_has_dependence_sched_deps_info ();
3422 17782 : deps_analyze_insn (dc, EXPR_INSN_RTX (expr));
3423 17782 : has_dependence_data.dc = NULL;
3424 :
3425 : /* When a barrier was found, set DEPS_IN_INSN bits. */
3426 17782 : if (dc->last_reg_pending_barrier == TRUE_BARRIER)
3427 10 : has_dependence_data.has_dep_p[DEPS_IN_INSN] = DEP_TRUE;
3428 17772 : else if (dc->last_reg_pending_barrier == MOVE_BARRIER)
3429 65 : has_dependence_data.has_dep_p[DEPS_IN_INSN] = DEP_ANTI;
3430 :
3431 : /* Do not allow stores to memory to move through checks. Currently
3432 : we don't move this to sched-deps.cc as the check doesn't have
3433 : obvious places to which this dependence can be attached.
3434 : FIMXE: this should go to a hook. */
3435 17782 : if (EXPR_LHS (expr)
3436 15064 : && MEM_P (EXPR_LHS (expr))
3437 18531 : && sel_insn_is_speculation_check (pred))
3438 0 : has_dependence_data.has_dep_p[DEPS_IN_INSN] = DEP_ANTI;
3439 :
3440 17782 : *has_dep_pp = has_dependence_data.has_dep_p;
3441 17782 : ds = 0;
3442 71128 : for (i = 0; i < DEPS_IN_NOWHERE; i++)
3443 53346 : ds = ds_full_merge (ds, has_dependence_data.has_dep_p[i],
3444 : NULL_RTX, NULL_RTX);
3445 :
3446 : return ds;
3447 : }
3448 :
3449 :
3450 : /* Dependence hooks implementation that checks dependence latency constraints
3451 : on the insns being scheduled. The entry point for these routines is
3452 : tick_check_p predicate. */
3453 :
3454 : static struct
3455 : {
3456 : /* An expr we are currently checking. */
3457 : expr_t expr;
3458 :
3459 : /* A minimal cycle for its scheduling. */
3460 : int cycle;
3461 :
3462 : /* Whether we have seen a true dependence while checking. */
3463 : bool seen_true_dep_p;
3464 : } tick_check_data;
3465 :
3466 : /* Update minimal scheduling cycle for tick_check_insn given that it depends
3467 : on PRO with status DS and weight DW. */
3468 : static void
3469 28440 : tick_check_dep_with_dw (insn_t pro_insn, ds_t ds, dw_t dw)
3470 : {
3471 28440 : expr_t con_expr = tick_check_data.expr;
3472 28440 : insn_t con_insn = EXPR_INSN_RTX (con_expr);
3473 :
3474 28440 : if (con_insn != pro_insn)
3475 : {
3476 28436 : enum reg_note dt;
3477 28436 : int tick;
3478 :
3479 28436 : if (/* PROducer was removed from above due to pipelining. */
3480 28428 : !INSN_IN_STREAM_P (pro_insn)
3481 : /* Or PROducer was originally on the next iteration regarding the
3482 : CONsumer. */
3483 56864 : || (INSN_SCHED_TIMES (pro_insn)
3484 28428 : - EXPR_SCHED_TIMES (con_expr)) > 1)
3485 : /* Don't count this dependence. */
3486 : return;
3487 :
3488 28376 : dt = ds_to_dt (ds);
3489 28376 : if (dt == REG_DEP_TRUE)
3490 6812 : tick_check_data.seen_true_dep_p = true;
3491 :
3492 28376 : gcc_assert (INSN_SCHED_CYCLE (pro_insn) > 0);
3493 :
3494 28376 : {
3495 28376 : dep_def _dep, *dep = &_dep;
3496 :
3497 28376 : init_dep (dep, pro_insn, con_insn, dt);
3498 :
3499 28376 : tick = INSN_SCHED_CYCLE (pro_insn) + dep_cost_1 (dep, dw);
3500 : }
3501 :
3502 : /* When there are several kinds of dependencies between pro and con,
3503 : only REG_DEP_TRUE should be taken into account. */
3504 28376 : if (tick > tick_check_data.cycle
3505 10010 : && (dt == REG_DEP_TRUE || !tick_check_data.seen_true_dep_p))
3506 9859 : tick_check_data.cycle = tick;
3507 : }
3508 : }
3509 :
3510 : /* An implementation of note_dep hook. */
3511 : static void
3512 25393 : tick_check_note_dep (insn_t pro, ds_t ds)
3513 : {
3514 25393 : tick_check_dep_with_dw (pro, ds, 0);
3515 25393 : }
3516 :
3517 : /* An implementation of note_mem_dep hook. */
3518 : static void
3519 3047 : tick_check_note_mem_dep (rtx mem1, rtx mem2, insn_t pro, ds_t ds)
3520 : {
3521 3047 : dw_t dw;
3522 :
3523 3047 : dw = (ds_to_dt (ds) == REG_DEP_TRUE
3524 3047 : ? estimate_dep_weak (mem1, mem2)
3525 : : 0);
3526 :
3527 3047 : tick_check_dep_with_dw (pro, ds, dw);
3528 3047 : }
3529 :
3530 : /* This structure contains hooks for dependence analysis used when determining
3531 : whether an insn is ready for scheduling. */
3532 : static struct sched_deps_info_def tick_check_sched_deps_info =
3533 : {
3534 : NULL,
3535 :
3536 : NULL,
3537 : NULL,
3538 : NULL,
3539 : NULL,
3540 : NULL,
3541 : NULL,
3542 : haifa_note_reg_set,
3543 : haifa_note_reg_clobber,
3544 : haifa_note_reg_use,
3545 : tick_check_note_mem_dep,
3546 : tick_check_note_dep,
3547 :
3548 : 0, 0, 0
3549 : };
3550 :
3551 : /* Estimate number of cycles from the current cycle of FENCE until EXPR can be
3552 : scheduled. Return 0 if all data from producers in DC is ready. */
3553 : int
3554 11674 : tick_check_p (expr_t expr, deps_t dc, fence_t fence)
3555 : {
3556 11674 : int cycles_left;
3557 : /* Initialize variables. */
3558 11674 : tick_check_data.expr = expr;
3559 11674 : tick_check_data.cycle = 0;
3560 11674 : tick_check_data.seen_true_dep_p = false;
3561 11674 : sched_deps_info = &tick_check_sched_deps_info;
3562 :
3563 11674 : gcc_assert (!dc->readonly);
3564 11674 : dc->readonly = 1;
3565 11674 : deps_analyze_insn (dc, EXPR_INSN_RTX (expr));
3566 11674 : dc->readonly = 0;
3567 :
3568 11674 : cycles_left = tick_check_data.cycle - FENCE_CYCLE (fence);
3569 :
3570 11674 : return cycles_left >= 0 ? cycles_left : 0;
3571 : }
3572 :
3573 :
3574 : /* Functions to work with insns. */
3575 :
3576 : /* Returns true if LHS of INSN is the same as DEST of an insn
3577 : being moved. */
3578 : bool
3579 6583 : lhs_of_insn_equals_to_dest_p (insn_t insn, rtx dest)
3580 : {
3581 6583 : rtx lhs = INSN_LHS (insn);
3582 :
3583 6583 : if (lhs == NULL || dest == NULL)
3584 : return false;
3585 :
3586 3812 : return rtx_equal_p (lhs, dest);
3587 : }
3588 :
3589 : /* Return s_i_d entry of INSN. Callable from debugger. */
3590 : sel_insn_data_def
3591 0 : insn_sid (insn_t insn)
3592 : {
3593 0 : return *SID (insn);
3594 : }
3595 :
3596 : /* True when INSN is a speculative check. We can tell this by looking
3597 : at the data structures of the selective scheduler, not by examining
3598 : the pattern. */
3599 : bool
3600 256727 : sel_insn_is_speculation_check (rtx insn)
3601 : {
3602 256727 : return s_i_d.exists () && !! INSN_SPEC_CHECKED_DS (insn);
3603 : }
3604 :
3605 : /* Extracts machine mode MODE and destination location DST_LOC
3606 : for given INSN. */
3607 : void
3608 166 : get_dest_and_mode (rtx insn, rtx *dst_loc, machine_mode *mode)
3609 : {
3610 166 : rtx pat = PATTERN (insn);
3611 :
3612 166 : gcc_assert (dst_loc);
3613 166 : gcc_assert (GET_CODE (pat) == SET);
3614 :
3615 166 : *dst_loc = SET_DEST (pat);
3616 :
3617 166 : gcc_assert (*dst_loc);
3618 166 : gcc_assert (MEM_P (*dst_loc) || REG_P (*dst_loc));
3619 :
3620 166 : if (mode)
3621 166 : *mode = GET_MODE (*dst_loc);
3622 166 : }
3623 :
3624 : /* Returns true when moving through JUMP will result in bookkeeping
3625 : creation. */
3626 : bool
3627 858 : bookkeeping_can_be_created_if_moved_through_p (insn_t jump)
3628 : {
3629 858 : insn_t succ;
3630 858 : succ_iterator si;
3631 :
3632 1705 : FOR_EACH_SUCC (succ, si, jump)
3633 873 : if (sel_num_cfg_preds_gt_1 (succ))
3634 : return true;
3635 :
3636 : return false;
3637 : }
3638 :
3639 : /* Return 'true' if INSN is the only one in its basic block. */
3640 : static bool
3641 2437 : insn_is_the_only_one_in_bb_p (insn_t insn)
3642 : {
3643 2437 : return sel_bb_head_p (insn) && sel_bb_end_p (insn);
3644 : }
3645 :
3646 : /* Check that the region we're scheduling still has at most one
3647 : backedge. */
3648 : static void
3649 2764 : verify_backedges (void)
3650 : {
3651 2764 : if (pipelining_p)
3652 : {
3653 : int i, n = 0;
3654 : edge e;
3655 : edge_iterator ei;
3656 :
3657 18552 : for (i = 0; i < current_nr_blocks; i++)
3658 42575 : FOR_EACH_EDGE (e, ei, BASIC_BLOCK_FOR_FN (cfun, BB_TO_BLOCK (i))->succs)
3659 25624 : if (in_current_region_p (e->dest)
3660 25624 : && BLOCK_TO_BB (e->dest->index) < i)
3661 1387 : n++;
3662 :
3663 1601 : gcc_assert (n <= 1);
3664 : }
3665 2764 : }
3666 :
3667 :
3668 : /* Functions to work with control flow. */
3669 :
3670 : /* Recompute BLOCK_TO_BB and BB_FOR_BLOCK for current region so that blocks
3671 : are sorted in topological order (it might have been invalidated by
3672 : redirecting an edge). */
3673 : static void
3674 0 : sel_recompute_toporder (void)
3675 : {
3676 0 : int i, n, rgn;
3677 0 : int *postorder, n_blocks;
3678 :
3679 0 : postorder = XALLOCAVEC (int, n_basic_blocks_for_fn (cfun));
3680 0 : n_blocks = post_order_compute (postorder, false, false);
3681 :
3682 0 : rgn = CONTAINING_RGN (BB_TO_BLOCK (0));
3683 0 : for (n = 0, i = n_blocks - 1; i >= 0; i--)
3684 0 : if (CONTAINING_RGN (postorder[i]) == rgn)
3685 : {
3686 0 : BLOCK_TO_BB (postorder[i]) = n;
3687 0 : BB_TO_BLOCK (n) = postorder[i];
3688 0 : n++;
3689 : }
3690 :
3691 : /* Assert that we updated info for all blocks. We may miss some blocks if
3692 : this function is called when redirecting an edge made a block
3693 : unreachable, but that block is not deleted yet. */
3694 0 : gcc_assert (n == RGN_NR_BLOCKS (rgn));
3695 0 : }
3696 :
3697 : /* Tidy the possibly empty block BB. */
3698 : static bool
3699 8139 : maybe_tidy_empty_bb (basic_block bb)
3700 : {
3701 8139 : basic_block succ_bb, pred_bb, note_bb;
3702 8139 : vec<basic_block> dom_bbs;
3703 8139 : edge e;
3704 8139 : edge_iterator ei;
3705 8139 : bool rescan_p;
3706 :
3707 : /* Keep empty bb only if this block immediately precedes EXIT and
3708 : has incoming non-fallthrough edge, or it has no predecessors or
3709 : successors. Otherwise remove it. */
3710 8139 : if (!sel_bb_empty_p (bb)
3711 61 : || (single_succ_p (bb)
3712 61 : && single_succ (bb) == EXIT_BLOCK_PTR_FOR_FN (cfun)
3713 1 : && (!single_pred_p (bb)
3714 1 : || !(single_pred_edge (bb)->flags & EDGE_FALLTHRU)))
3715 61 : || EDGE_COUNT (bb->preds) == 0
3716 8200 : || EDGE_COUNT (bb->succs) == 0)
3717 : return false;
3718 :
3719 : /* Do not attempt to redirect complex edges. */
3720 141 : FOR_EACH_EDGE (e, ei, bb->preds)
3721 81 : if (e->flags & EDGE_COMPLEX)
3722 : return false;
3723 81 : else if (e->flags & EDGE_FALLTHRU)
3724 : {
3725 51 : rtx note;
3726 : /* If prev bb ends with asm goto, see if any of the
3727 : ASM_OPERANDS_LABELs don't point to the fallthru
3728 : label. Do not attempt to redirect it in that case. */
3729 51 : if (JUMP_P (BB_END (e->src))
3730 51 : && (note = extract_asm_operands (PATTERN (BB_END (e->src)))))
3731 : {
3732 1 : int i, n = ASM_OPERANDS_LABEL_LENGTH (note);
3733 :
3734 1 : for (i = 0; i < n; ++i)
3735 1 : if (XEXP (ASM_OPERANDS_LABEL (note, i), 0) == BB_HEAD (bb))
3736 : return false;
3737 : }
3738 : }
3739 :
3740 60 : free_data_sets (bb);
3741 :
3742 : /* Do not delete BB if it has more than one successor.
3743 : That can occur when we moving a jump. */
3744 60 : if (!single_succ_p (bb))
3745 : {
3746 0 : gcc_assert (can_merge_blocks_p (bb->prev_bb, bb));
3747 0 : sel_merge_blocks (bb->prev_bb, bb);
3748 0 : return true;
3749 : }
3750 :
3751 60 : succ_bb = single_succ (bb);
3752 60 : rescan_p = true;
3753 60 : pred_bb = NULL;
3754 60 : dom_bbs.create (0);
3755 :
3756 : /* Save a pred/succ from the current region to attach the notes to. */
3757 60 : note_bb = NULL;
3758 60 : FOR_EACH_EDGE (e, ei, bb->preds)
3759 60 : if (in_current_region_p (e->src))
3760 : {
3761 60 : note_bb = e->src;
3762 60 : break;
3763 : }
3764 60 : if (note_bb == NULL)
3765 0 : note_bb = succ_bb;
3766 :
3767 : /* Redirect all non-fallthru edges to the next bb. */
3768 150 : while (rescan_p)
3769 : {
3770 90 : rescan_p = false;
3771 :
3772 150 : FOR_EACH_EDGE (e, ei, bb->preds)
3773 : {
3774 90 : pred_bb = e->src;
3775 :
3776 90 : if (!(e->flags & EDGE_FALLTHRU))
3777 : {
3778 : /* We cannot invalidate computed topological order by moving
3779 : the edge destination block (E->SUCC) along a fallthru edge.
3780 :
3781 : We will update dominators here only when we'll get
3782 : an unreachable block when redirecting, otherwise
3783 : sel_redirect_edge_and_branch will take care of it. */
3784 30 : if (e->dest != bb
3785 30 : && single_pred_p (e->dest))
3786 0 : dom_bbs.safe_push (e->dest);
3787 30 : sel_redirect_edge_and_branch (e, succ_bb);
3788 30 : rescan_p = true;
3789 30 : break;
3790 : }
3791 : /* If the edge is fallthru, but PRED_BB ends in a conditional jump
3792 : to BB (so there is no non-fallthru edge from PRED_BB to BB), we
3793 : still have to adjust it. */
3794 60 : else if (single_succ_p (pred_bb) && any_condjump_p (BB_END (pred_bb)))
3795 : {
3796 : /* If possible, try to remove the unneeded conditional jump. */
3797 0 : if (onlyjump_p (BB_END (pred_bb))
3798 0 : && INSN_SCHED_TIMES (BB_END (pred_bb)) == 0
3799 0 : && !IN_CURRENT_FENCE_P (BB_END (pred_bb)))
3800 : {
3801 0 : if (!sel_remove_insn (BB_END (pred_bb), false, false))
3802 0 : tidy_fallthru_edge (e);
3803 : }
3804 : else
3805 0 : sel_redirect_edge_and_branch (e, succ_bb);
3806 30 : rescan_p = true;
3807 : break;
3808 : }
3809 : }
3810 : }
3811 :
3812 60 : if (can_merge_blocks_p (bb->prev_bb, bb))
3813 48 : sel_merge_blocks (bb->prev_bb, bb);
3814 : else
3815 : {
3816 : /* This is a block without fallthru predecessor. Just delete it. */
3817 12 : gcc_assert (note_bb);
3818 12 : move_bb_info (note_bb, bb);
3819 12 : remove_empty_bb (bb, true);
3820 : }
3821 :
3822 60 : if (!dom_bbs.is_empty ())
3823 : {
3824 0 : dom_bbs.safe_push (succ_bb);
3825 0 : iterate_fix_dominators (CDI_DOMINATORS, dom_bbs, false);
3826 0 : dom_bbs.release ();
3827 : }
3828 :
3829 : return true;
3830 : }
3831 :
3832 : /* Tidy the control flow after we have removed original insn from
3833 : XBB. Return true if we have removed some blocks. When FULL_TIDYING
3834 : is true, also try to optimize control flow on non-empty blocks. */
3835 : bool
3836 7868 : tidy_control_flow (basic_block xbb, bool full_tidying)
3837 : {
3838 7868 : bool changed = true;
3839 7868 : insn_t first, last;
3840 :
3841 : /* First check whether XBB is empty. */
3842 7868 : changed = maybe_tidy_empty_bb (xbb);
3843 7868 : if (changed || !full_tidying)
3844 : return changed;
3845 :
3846 : /* Check if there is a unnecessary jump after insn left. */
3847 2764 : if (bb_has_removable_jump_to_p (xbb, xbb->next_bb)
3848 2 : && INSN_SCHED_TIMES (BB_END (xbb)) == 0
3849 2766 : && !IN_CURRENT_FENCE_P (BB_END (xbb)))
3850 : {
3851 : /* We used to call sel_remove_insn here that can trigger tidy_control_flow
3852 : before we fix up the fallthru edge. Correct that ordering by
3853 : explicitly doing the latter before the former. */
3854 2 : clear_expr (INSN_EXPR (BB_END (xbb)));
3855 2 : tidy_fallthru_edge (EDGE_SUCC (xbb, 0));
3856 2 : if (tidy_control_flow (xbb, false))
3857 : return true;
3858 : }
3859 :
3860 2764 : first = sel_bb_head (xbb);
3861 2764 : last = sel_bb_end (xbb);
3862 2764 : if (MAY_HAVE_DEBUG_INSNS)
3863 : {
3864 79 : if (first != last && DEBUG_INSN_P (first))
3865 59 : do
3866 59 : first = NEXT_INSN (first);
3867 59 : while (first != last && (DEBUG_INSN_P (first) || NOTE_P (first)));
3868 :
3869 79 : if (first != last && DEBUG_INSN_P (last))
3870 1 : do
3871 1 : last = PREV_INSN (last);
3872 1 : while (first != last && (DEBUG_INSN_P (last) || NOTE_P (last)));
3873 : }
3874 : /* Check if there is an unnecessary jump in previous basic block leading
3875 : to next basic block left after removing INSN from stream.
3876 : If it is so, remove that jump and redirect edge to current
3877 : basic block (where there was INSN before deletion). This way
3878 : when NOP will be deleted several instructions later with its
3879 : basic block we will not get a jump to next instruction, which
3880 : can be harmful. */
3881 2764 : if (first == last
3882 319 : && !sel_bb_empty_p (xbb)
3883 319 : && INSN_NOP_P (last)
3884 : /* Flow goes fallthru from current block to the next. */
3885 55 : && EDGE_COUNT (xbb->succs) == 1
3886 55 : && (EDGE_SUCC (xbb, 0)->flags & EDGE_FALLTHRU)
3887 : /* When successor is an EXIT block, it may not be the next block. */
3888 55 : && single_succ (xbb) != EXIT_BLOCK_PTR_FOR_FN (cfun)
3889 : /* And unconditional jump in previous basic block leads to
3890 : next basic block of XBB and this jump can be safely removed. */
3891 55 : && in_current_region_p (xbb->prev_bb)
3892 49 : && bb_has_removable_jump_to_p (xbb->prev_bb, xbb->next_bb)
3893 10 : && INSN_SCHED_TIMES (BB_END (xbb->prev_bb)) == 0
3894 : /* Also this jump is not at the scheduling boundary. */
3895 2774 : && !IN_CURRENT_FENCE_P (BB_END (xbb->prev_bb)))
3896 : {
3897 10 : bool recompute_toporder_p;
3898 : /* Clear data structures of jump - jump itself will be removed
3899 : by sel_redirect_edge_and_branch. */
3900 10 : clear_expr (INSN_EXPR (BB_END (xbb->prev_bb)));
3901 10 : recompute_toporder_p
3902 10 : = sel_redirect_edge_and_branch (EDGE_SUCC (xbb->prev_bb, 0), xbb);
3903 :
3904 10 : gcc_assert (EDGE_SUCC (xbb->prev_bb, 0)->flags & EDGE_FALLTHRU);
3905 :
3906 : /* We could have skipped some debug insns which did not get removed with the block,
3907 : and the seqnos could become incorrect. Fix them up here. */
3908 10 : if (MAY_HAVE_DEBUG_INSNS && (sel_bb_head (xbb) != first || sel_bb_end (xbb) != last))
3909 : {
3910 0 : if (!sel_bb_empty_p (xbb->prev_bb))
3911 : {
3912 0 : int prev_seqno = INSN_SEQNO (sel_bb_end (xbb->prev_bb));
3913 0 : if (prev_seqno > INSN_SEQNO (sel_bb_head (xbb)))
3914 0 : for (insn_t insn = sel_bb_head (xbb); insn != first; insn = NEXT_INSN (insn))
3915 0 : INSN_SEQNO (insn) = prev_seqno + 1;
3916 : }
3917 : }
3918 :
3919 : /* It can turn out that after removing unused jump, basic block
3920 : that contained that jump, becomes empty too. In such case
3921 : remove it too. */
3922 10 : if (sel_bb_empty_p (xbb->prev_bb))
3923 0 : changed = maybe_tidy_empty_bb (xbb->prev_bb);
3924 10 : if (recompute_toporder_p)
3925 0 : sel_recompute_toporder ();
3926 : }
3927 :
3928 : /* TODO: use separate flag for CFG checking. */
3929 2764 : if (flag_checking)
3930 : {
3931 2764 : verify_backedges ();
3932 2764 : verify_dominators (CDI_DOMINATORS);
3933 : }
3934 :
3935 : return changed;
3936 : }
3937 :
3938 : /* Purge meaningless empty blocks in the middle of a region. */
3939 : void
3940 739 : purge_empty_blocks (void)
3941 : {
3942 739 : int i;
3943 :
3944 : /* Do not attempt to delete the first basic block in the region. */
3945 1010 : for (i = 1; i < current_nr_blocks; )
3946 : {
3947 271 : basic_block b = BASIC_BLOCK_FOR_FN (cfun, BB_TO_BLOCK (i));
3948 :
3949 271 : if (maybe_tidy_empty_bb (b))
3950 5 : continue;
3951 :
3952 266 : i++;
3953 : }
3954 739 : }
3955 :
3956 : /* Rip-off INSN from the insn stream. When ONLY_DISCONNECT is true,
3957 : do not delete insn's data, because it will be later re-emitted.
3958 : Return true if we have removed some blocks afterwards. */
3959 : bool
3960 6989 : sel_remove_insn (insn_t insn, bool only_disconnect, bool full_tidying)
3961 : {
3962 6989 : basic_block bb = BLOCK_FOR_INSN (insn);
3963 :
3964 13978 : gcc_assert (INSN_IN_STREAM_P (insn));
3965 :
3966 6989 : if (DEBUG_INSN_P (insn) && BB_AV_SET_VALID_P (bb))
3967 : {
3968 43 : expr_t expr;
3969 43 : av_set_iterator i;
3970 :
3971 : /* When we remove a debug insn that is head of a BB, it remains
3972 : in the AV_SET of the block, but it shouldn't. */
3973 128 : FOR_EACH_EXPR_1 (expr, i, &BB_AV_SET (bb))
3974 85 : if (EXPR_INSN_RTX (expr) == insn)
3975 : {
3976 28 : av_set_iter_remove (&i);
3977 28 : break;
3978 : }
3979 : }
3980 :
3981 6989 : if (only_disconnect)
3982 4723 : remove_insn (insn);
3983 : else
3984 : {
3985 2266 : delete_insn (insn);
3986 2266 : clear_expr (INSN_EXPR (insn));
3987 : }
3988 :
3989 : /* It is necessary to NULL these fields in case we are going to re-insert
3990 : INSN into the insns stream, as will usually happen in the ONLY_DISCONNECT
3991 : case, but also for NOPs that we will return to the nop pool. */
3992 6989 : SET_PREV_INSN (insn) = NULL_RTX;
3993 6989 : SET_NEXT_INSN (insn) = NULL_RTX;
3994 6989 : set_block_for_insn (insn, NULL);
3995 :
3996 6989 : return tidy_control_flow (bb, full_tidying);
3997 : }
3998 :
3999 : /* Estimate number of the insns in BB. */
4000 : static int
4001 95 : sel_estimate_number_of_insns (basic_block bb)
4002 : {
4003 95 : int res = 0;
4004 95 : insn_t insn = NEXT_INSN (BB_HEAD (bb)), next_tail = NEXT_INSN (BB_END (bb));
4005 :
4006 871 : for (; insn != next_tail; insn = NEXT_INSN (insn))
4007 681 : if (NONDEBUG_INSN_P (insn))
4008 544 : res++;
4009 :
4010 95 : return res;
4011 : }
4012 :
4013 : /* We don't need separate luids for notes or labels. */
4014 : static int
4015 1498 : sel_luid_for_non_insn (rtx x)
4016 : {
4017 1498 : gcc_assert (NOTE_P (x) || LABEL_P (x));
4018 :
4019 1498 : return -1;
4020 : }
4021 :
4022 : /* Find the proper seqno for inserting at INSN by successors.
4023 : Return -1 if no successors with positive seqno exist. */
4024 : static int
4025 0 : get_seqno_by_succs (rtx_insn *insn)
4026 : {
4027 0 : basic_block bb = BLOCK_FOR_INSN (insn);
4028 0 : rtx_insn *tmp = insn, *end = BB_END (bb);
4029 0 : int seqno;
4030 0 : insn_t succ = NULL;
4031 0 : succ_iterator si;
4032 :
4033 0 : while (tmp != end)
4034 : {
4035 0 : tmp = NEXT_INSN (tmp);
4036 0 : if (INSN_P (tmp))
4037 0 : return INSN_SEQNO (tmp);
4038 : }
4039 :
4040 0 : seqno = INT_MAX;
4041 :
4042 0 : FOR_EACH_SUCC_1 (succ, si, end, SUCCS_NORMAL)
4043 0 : if (INSN_SEQNO (succ) > 0)
4044 0 : seqno = MIN (seqno, INSN_SEQNO (succ));
4045 :
4046 0 : if (seqno == INT_MAX)
4047 0 : return -1;
4048 :
4049 : return seqno;
4050 : }
4051 :
4052 : /* Compute seqno for INSN by its preds or succs. Use OLD_SEQNO to compute
4053 : seqno in corner cases. */
4054 : static int
4055 12 : get_seqno_for_a_jump (insn_t insn, int old_seqno)
4056 : {
4057 12 : int seqno;
4058 :
4059 12 : gcc_assert (INSN_SIMPLEJUMP_P (insn));
4060 :
4061 12 : if (!sel_bb_head_p (insn))
4062 11 : seqno = INSN_SEQNO (PREV_INSN (insn));
4063 : else
4064 : {
4065 1 : basic_block bb = BLOCK_FOR_INSN (insn);
4066 :
4067 1 : if (single_pred_p (bb)
4068 2 : && !in_current_region_p (single_pred (bb)))
4069 : {
4070 : /* We can have preds outside a region when splitting edges
4071 : for pipelining of an outer loop. Use succ instead.
4072 : There should be only one of them. */
4073 0 : insn_t succ = NULL;
4074 0 : succ_iterator si;
4075 0 : bool first = true;
4076 :
4077 0 : gcc_assert (flag_sel_sched_pipelining_outer_loops
4078 : && current_loop_nest);
4079 0 : FOR_EACH_SUCC_1 (succ, si, insn,
4080 : SUCCS_NORMAL | SUCCS_SKIP_TO_LOOP_EXITS)
4081 : {
4082 0 : gcc_assert (first);
4083 0 : first = false;
4084 : }
4085 :
4086 0 : gcc_assert (succ != NULL);
4087 0 : seqno = INSN_SEQNO (succ);
4088 : }
4089 : else
4090 : {
4091 1 : insn_t *preds;
4092 1 : int n;
4093 :
4094 2 : cfg_preds (BLOCK_FOR_INSN (insn), &preds, &n);
4095 :
4096 1 : gcc_assert (n > 0);
4097 : /* For one predecessor, use simple method. */
4098 1 : if (n == 1)
4099 1 : seqno = INSN_SEQNO (preds[0]);
4100 : else
4101 0 : seqno = get_seqno_by_preds (insn);
4102 :
4103 1 : free (preds);
4104 : }
4105 : }
4106 :
4107 : /* We were unable to find a good seqno among preds. */
4108 12 : if (seqno < 0)
4109 0 : seqno = get_seqno_by_succs (insn);
4110 :
4111 0 : if (seqno < 0)
4112 : {
4113 : /* The only case where this could be here legally is that the only
4114 : unscheduled insn was a conditional jump that got removed and turned
4115 : into this unconditional one. Initialize from the old seqno
4116 : of that jump passed down to here. */
4117 0 : seqno = old_seqno;
4118 : }
4119 :
4120 0 : gcc_assert (seqno >= 0);
4121 12 : return seqno;
4122 : }
4123 :
4124 : /* Find the proper seqno for inserting at INSN. Returns -1 if no predecessors
4125 : with positive seqno exist. */
4126 : int
4127 0 : get_seqno_by_preds (rtx_insn *insn)
4128 : {
4129 0 : basic_block bb = BLOCK_FOR_INSN (insn);
4130 0 : rtx_insn *tmp = insn, *head = BB_HEAD (bb);
4131 0 : insn_t *preds;
4132 0 : int n, i, seqno;
4133 :
4134 : /* Loop backwards from INSN to HEAD including both. */
4135 0 : while (1)
4136 : {
4137 0 : if (INSN_P (tmp))
4138 0 : return INSN_SEQNO (tmp);
4139 0 : if (tmp == head)
4140 : break;
4141 0 : tmp = PREV_INSN (tmp);
4142 : }
4143 :
4144 0 : cfg_preds (bb, &preds, &n);
4145 0 : for (i = 0, seqno = -1; i < n; i++)
4146 0 : seqno = MAX (seqno, INSN_SEQNO (preds[i]));
4147 :
4148 : return seqno;
4149 : }
4150 :
4151 :
4152 :
4153 : /* Extend pass-scope data structures for basic blocks. */
4154 : void
4155 1013 : sel_extend_global_bb_info (void)
4156 : {
4157 1013 : sel_global_bb_info.safe_grow_cleared (last_basic_block_for_fn (cfun), true);
4158 1013 : }
4159 :
4160 : /* Extend region-scope data structures for basic blocks. */
4161 : static void
4162 882 : extend_region_bb_info (void)
4163 : {
4164 882 : sel_region_bb_info.safe_grow_cleared (last_basic_block_for_fn (cfun), true);
4165 882 : }
4166 :
4167 : /* Extend all data structures to fit for all basic blocks. */
4168 : static void
4169 882 : extend_bb_info (void)
4170 : {
4171 810 : sel_extend_global_bb_info ();
4172 882 : extend_region_bb_info ();
4173 810 : }
4174 :
4175 : /* Finalize pass-scope data structures for basic blocks. */
4176 : void
4177 131 : sel_finish_global_bb_info (void)
4178 : {
4179 131 : sel_global_bb_info.release ();
4180 131 : }
4181 :
4182 : /* Finalize region-scope data structures for basic blocks. */
4183 : static void
4184 739 : finish_region_bb_info (void)
4185 : {
4186 0 : sel_region_bb_info.release ();
4187 0 : }
4188 :
4189 :
4190 : /* Data for each insn in current region. */
4191 : vec<sel_insn_data_def> s_i_d;
4192 :
4193 : /* Extend data structures for insns from current region. */
4194 : static void
4195 3176 : extend_insn_data (void)
4196 : {
4197 3176 : int reserve;
4198 :
4199 3176 : sched_extend_target ();
4200 3176 : sched_deps_init (false);
4201 :
4202 : /* Extend data structures for insns from current region. */
4203 3176 : reserve = (sched_max_luid + 1 - s_i_d.length ());
4204 4291 : if (reserve > 0 && ! s_i_d.space (reserve))
4205 : {
4206 1115 : int size;
4207 :
4208 1115 : if (sched_max_luid / 2 > 1024)
4209 0 : size = sched_max_luid + 1024;
4210 : else
4211 1115 : size = 3 * sched_max_luid / 2;
4212 :
4213 :
4214 1115 : s_i_d.safe_grow_cleared (size, true);
4215 : }
4216 3176 : }
4217 :
4218 : /* Finalize data structures for insns from current region. */
4219 : static void
4220 739 : finish_insns (void)
4221 : {
4222 739 : unsigned i;
4223 :
4224 : /* Clear here all dependence contexts that may have left from insns that were
4225 : removed during the scheduling. */
4226 9254 : for (i = 0; i < s_i_d.length (); i++)
4227 : {
4228 8515 : sel_insn_data_def *sid_entry = &s_i_d[i];
4229 :
4230 8515 : if (sid_entry->live)
4231 1122 : return_regset_to_pool (sid_entry->live);
4232 8515 : if (sid_entry->analyzed_deps)
4233 : {
4234 294 : BITMAP_FREE (sid_entry->analyzed_deps);
4235 294 : BITMAP_FREE (sid_entry->found_deps);
4236 294 : htab_delete (sid_entry->transformed_insns);
4237 294 : free_deps (&sid_entry->deps_context);
4238 : }
4239 8515 : if (EXPR_VINSN (&sid_entry->expr))
4240 : {
4241 0 : clear_expr (&sid_entry->expr);
4242 :
4243 : /* Also, clear CANT_MOVE bit here, because we really don't want it
4244 : to be passed to the next region. */
4245 0 : CANT_MOVE_BY_LUID (i) = 0;
4246 : }
4247 : }
4248 :
4249 739 : s_i_d.release ();
4250 739 : }
4251 :
4252 : /* A proxy to pass initialization data to init_insn (). */
4253 : static sel_insn_data_def _insn_init_ssid;
4254 : static sel_insn_data_t insn_init_ssid = &_insn_init_ssid;
4255 :
4256 : /* If true create a new vinsn. Otherwise use the one from EXPR. */
4257 : static bool insn_init_create_new_vinsn_p;
4258 :
4259 : /* Set all necessary data for initialization of the new insn[s]. */
4260 : static expr_t
4261 2425 : set_insn_init (expr_t expr, vinsn_t vi, int seqno)
4262 : {
4263 2425 : expr_t x = &insn_init_ssid->expr;
4264 :
4265 2425 : copy_expr_onside (x, expr);
4266 2425 : if (vi != NULL)
4267 : {
4268 2396 : insn_init_create_new_vinsn_p = false;
4269 2396 : change_vinsn_in_expr (x, vi);
4270 : }
4271 : else
4272 29 : insn_init_create_new_vinsn_p = true;
4273 :
4274 2425 : insn_init_ssid->seqno = seqno;
4275 2425 : return x;
4276 : }
4277 :
4278 : /* Init data for INSN. */
4279 : static void
4280 2425 : init_insn_data (insn_t insn)
4281 : {
4282 2425 : expr_t expr;
4283 2425 : sel_insn_data_t ssid = insn_init_ssid;
4284 :
4285 : /* The fields mentioned below are special and hence are not being
4286 : propagated to the new insns. */
4287 2425 : gcc_assert (!ssid->asm_p && ssid->sched_next == NULL
4288 : && !ssid->after_stall_p && ssid->sched_cycle == 0);
4289 2425 : gcc_assert (INSN_P (insn) && INSN_LUID (insn) > 0);
4290 :
4291 2425 : expr = INSN_EXPR (insn);
4292 2425 : copy_expr (expr, &ssid->expr);
4293 2425 : prepare_insn_expr (insn, ssid->seqno);
4294 :
4295 2425 : if (insn_init_create_new_vinsn_p)
4296 29 : change_vinsn_in_expr (expr, vinsn_create (insn, init_insn_force_unique_p));
4297 :
4298 2425 : if (first_time_insn_init (insn))
4299 1269 : init_first_time_insn_data (insn);
4300 2425 : }
4301 :
4302 : /* This is used to initialize spurious jumps generated by
4303 : sel_redirect_edge (). OLD_SEQNO is used for initializing seqnos
4304 : in corner cases within get_seqno_for_a_jump. */
4305 : static void
4306 12 : init_simplejump_data (insn_t insn, int old_seqno)
4307 : {
4308 12 : init_expr (INSN_EXPR (insn), vinsn_create (insn, false), 0,
4309 : REG_BR_PROB_BASE, 0, 0, 0, 0, 0, 0,
4310 12 : vNULL, true, false, false,
4311 : false, true);
4312 12 : INSN_SEQNO (insn) = get_seqno_for_a_jump (insn, old_seqno);
4313 12 : init_first_time_insn_data (insn);
4314 12 : }
4315 :
4316 : /* Perform deferred initialization of insns. This is used to process
4317 : a new jump that may be created by redirect_edge. OLD_SEQNO is used
4318 : for initializing simplejumps in init_simplejump_data. */
4319 : static void
4320 2437 : sel_init_new_insn (insn_t insn, int flags, int old_seqno)
4321 : {
4322 : /* We create data structures for bb when the first insn is emitted in it. */
4323 2437 : if (INSN_P (insn)
4324 4874 : && INSN_IN_STREAM_P (insn)
4325 4874 : && insn_is_the_only_one_in_bb_p (insn))
4326 : {
4327 72 : extend_bb_info ();
4328 72 : create_initial_data_sets (BLOCK_FOR_INSN (insn));
4329 : }
4330 :
4331 2437 : if (flags & INSN_INIT_TODO_LUID)
4332 : {
4333 1281 : sched_extend_luids ();
4334 1281 : sched_init_insn_luid (insn);
4335 : }
4336 :
4337 2437 : if (flags & INSN_INIT_TODO_SSID)
4338 : {
4339 2425 : extend_insn_data ();
4340 2425 : init_insn_data (insn);
4341 2425 : clear_expr (&insn_init_ssid->expr);
4342 : }
4343 :
4344 2437 : if (flags & INSN_INIT_TODO_SIMPLEJUMP)
4345 : {
4346 12 : extend_insn_data ();
4347 12 : init_simplejump_data (insn, old_seqno);
4348 : }
4349 :
4350 2437 : gcc_assert (CONTAINING_RGN (BLOCK_NUM (insn))
4351 : == CONTAINING_RGN (BB_TO_BLOCK (0)));
4352 2437 : }
4353 :
4354 :
4355 : /* Functions to init/finish work with lv sets. */
4356 :
4357 : /* Init BB_LV_SET of BB from DF_LR_IN set of BB. */
4358 : static void
4359 1108 : init_lv_set (basic_block bb)
4360 : {
4361 1108 : gcc_assert (!BB_LV_SET_VALID_P (bb));
4362 :
4363 1108 : BB_LV_SET (bb) = get_regset_from_pool ();
4364 2216 : COPY_REG_SET (BB_LV_SET (bb), DF_LR_IN (bb));
4365 1108 : BB_LV_SET_VALID_P (bb) = true;
4366 1108 : }
4367 :
4368 : /* Copy liveness information to BB from FROM_BB. */
4369 : static void
4370 0 : copy_lv_set_from (basic_block bb, basic_block from_bb)
4371 : {
4372 0 : gcc_assert (!BB_LV_SET_VALID_P (bb));
4373 :
4374 0 : COPY_REG_SET (BB_LV_SET (bb), BB_LV_SET (from_bb));
4375 0 : BB_LV_SET_VALID_P (bb) = true;
4376 0 : }
4377 :
4378 : /* Initialize lv set of all bb headers. */
4379 : void
4380 131 : init_lv_sets (void)
4381 : {
4382 131 : basic_block bb;
4383 :
4384 : /* Initialize of LV sets. */
4385 1108 : FOR_EACH_BB_FN (bb, cfun)
4386 977 : init_lv_set (bb);
4387 :
4388 : /* Don't forget EXIT_BLOCK. */
4389 131 : init_lv_set (EXIT_BLOCK_PTR_FOR_FN (cfun));
4390 131 : }
4391 :
4392 : /* Release lv set of HEAD. */
4393 : static void
4394 1235 : free_lv_set (basic_block bb)
4395 : {
4396 1235 : gcc_assert (BB_LV_SET (bb) != NULL);
4397 :
4398 1235 : return_regset_to_pool (BB_LV_SET (bb));
4399 1235 : BB_LV_SET (bb) = NULL;
4400 1235 : BB_LV_SET_VALID_P (bb) = false;
4401 1235 : }
4402 :
4403 : /* Finalize lv sets of all bb headers. */
4404 : void
4405 131 : free_lv_sets (void)
4406 : {
4407 131 : basic_block bb;
4408 :
4409 : /* Don't forget EXIT_BLOCK. */
4410 131 : free_lv_set (EXIT_BLOCK_PTR_FOR_FN (cfun));
4411 :
4412 : /* Free LV sets. */
4413 1102 : FOR_EACH_BB_FN (bb, cfun)
4414 971 : if (BB_LV_SET (bb))
4415 971 : free_lv_set (bb);
4416 131 : }
4417 :
4418 : /* Mark AV_SET for BB as invalid, so this set will be updated the next time
4419 : compute_av() processes BB. This function is called when creating new basic
4420 : blocks, as well as for blocks (either new or existing) where new jumps are
4421 : created when the control flow is being updated. */
4422 : static void
4423 1117 : invalidate_av_set (basic_block bb)
4424 : {
4425 1117 : BB_AV_LEVEL (bb) = -1;
4426 1117 : }
4427 :
4428 : /* Create initial data sets for BB (they will be invalid). */
4429 : static void
4430 136 : create_initial_data_sets (basic_block bb)
4431 : {
4432 136 : if (BB_LV_SET (bb))
4433 9 : BB_LV_SET_VALID_P (bb) = false;
4434 : else
4435 127 : BB_LV_SET (bb) = get_regset_from_pool ();
4436 136 : invalidate_av_set (bb);
4437 136 : }
4438 :
4439 : /* Free av set of BB. */
4440 : static void
4441 123 : free_av_set (basic_block bb)
4442 : {
4443 123 : av_set_clear (&BB_AV_SET (bb));
4444 123 : BB_AV_LEVEL (bb) = 0;
4445 123 : }
4446 :
4447 : /* Free data sets of BB. */
4448 : void
4449 123 : free_data_sets (basic_block bb)
4450 : {
4451 123 : free_lv_set (bb);
4452 123 : free_av_set (bb);
4453 123 : }
4454 :
4455 : /* Exchange data sets of TO and FROM. */
4456 : void
4457 134 : exchange_data_sets (basic_block to, basic_block from)
4458 : {
4459 : /* Exchange lv sets of TO and FROM. */
4460 134 : std::swap (BB_LV_SET (from), BB_LV_SET (to));
4461 134 : std::swap (BB_LV_SET_VALID_P (from), BB_LV_SET_VALID_P (to));
4462 :
4463 : /* Exchange av sets of TO and FROM. */
4464 134 : std::swap (BB_AV_SET (from), BB_AV_SET (to));
4465 134 : std::swap (BB_AV_LEVEL (from), BB_AV_LEVEL (to));
4466 134 : }
4467 :
4468 : /* Return an av set for INSN, if any. */
4469 : av_set_t
4470 8408 : get_av_set (insn_t insn)
4471 : {
4472 8408 : av_set_t av_set;
4473 :
4474 8408 : gcc_assert (AV_SET_VALID_P (insn));
4475 :
4476 8408 : if (sel_bb_head_p (insn))
4477 8408 : av_set = BB_AV_SET (BLOCK_FOR_INSN (insn));
4478 : else
4479 : av_set = NULL;
4480 :
4481 8408 : return av_set;
4482 : }
4483 :
4484 : /* Implementation of AV_LEVEL () macro. Return AV_LEVEL () of INSN. */
4485 : int
4486 107358 : get_av_level (insn_t insn)
4487 : {
4488 107358 : int av_level;
4489 :
4490 107358 : gcc_assert (INSN_P (insn));
4491 :
4492 107358 : if (sel_bb_head_p (insn))
4493 46914 : av_level = BB_AV_LEVEL (BLOCK_FOR_INSN (insn));
4494 : else
4495 60444 : av_level = INSN_WS_LEVEL (insn);
4496 :
4497 107358 : return av_level;
4498 : }
4499 :
4500 :
4501 :
4502 : /* Variables to work with control-flow graph. */
4503 :
4504 : /* The basic block that already has been processed by the sched_data_update (),
4505 : but hasn't been in sel_add_bb () yet. */
4506 : static vec<basic_block> last_added_blocks;
4507 :
4508 : /* A pool for allocating successor infos. */
4509 : static struct
4510 : {
4511 : /* A stack for saving succs_info structures. */
4512 : struct succs_info *stack;
4513 :
4514 : /* Its size. */
4515 : int size;
4516 :
4517 : /* Top of the stack. */
4518 : int top;
4519 :
4520 : /* Maximal value of the top. */
4521 : int max_top;
4522 : } succs_info_pool;
4523 :
4524 : /* Functions to work with control-flow graph. */
4525 :
4526 : /* Return basic block note of BB. */
4527 : rtx_insn *
4528 364042 : sel_bb_head (basic_block bb)
4529 : {
4530 364042 : rtx_insn *head;
4531 :
4532 364042 : if (bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
4533 : {
4534 2234 : gcc_assert (exit_insn != NULL_RTX);
4535 : head = exit_insn;
4536 : }
4537 : else
4538 : {
4539 361808 : rtx_note *note = bb_note (bb);
4540 361808 : head = next_nonnote_insn (note);
4541 :
4542 361808 : if (head && (BARRIER_P (head) || BLOCK_FOR_INSN (head) != bb))
4543 : head = NULL;
4544 : }
4545 :
4546 364042 : return head;
4547 : }
4548 :
4549 : /* Return true if INSN is a basic block header. */
4550 : bool
4551 191278 : sel_bb_head_p (insn_t insn)
4552 : {
4553 191278 : return sel_bb_head (BLOCK_FOR_INSN (insn)) == insn;
4554 : }
4555 :
4556 : /* Return last insn of BB. */
4557 : rtx_insn *
4558 64843 : sel_bb_end (basic_block bb)
4559 : {
4560 64843 : if (sel_bb_empty_p (bb))
4561 : return NULL;
4562 :
4563 64843 : gcc_assert (bb != EXIT_BLOCK_PTR_FOR_FN (cfun));
4564 :
4565 64843 : return BB_END (bb);
4566 : }
4567 :
4568 : /* Return true if INSN is the last insn in its basic block. */
4569 : bool
4570 23121 : sel_bb_end_p (insn_t insn)
4571 : {
4572 23121 : return insn == sel_bb_end (BLOCK_FOR_INSN (insn));
4573 : }
4574 :
4575 : /* Return true if BB consist of single NOTE_INSN_BASIC_BLOCK. */
4576 : bool
4577 107573 : sel_bb_empty_p (basic_block bb)
4578 : {
4579 107573 : return sel_bb_head (bb) == NULL;
4580 : }
4581 :
4582 : /* True when BB belongs to the current scheduling region. */
4583 : bool
4584 97032 : in_current_region_p (basic_block bb)
4585 : {
4586 97032 : if (bb->index < NUM_FIXED_BLOCKS)
4587 : return false;
4588 :
4589 95931 : return CONTAINING_RGN (bb->index) == CONTAINING_RGN (BB_TO_BLOCK (0));
4590 : }
4591 :
4592 : /* Return the block which is a fallthru bb of a conditional jump JUMP. */
4593 : basic_block
4594 773 : fallthru_bb_of_jump (const rtx_insn *jump)
4595 : {
4596 773 : if (!JUMP_P (jump))
4597 : return NULL;
4598 :
4599 756 : if (!any_condjump_p (jump))
4600 : return NULL;
4601 :
4602 : /* A basic block that ends with a conditional jump may still have one successor
4603 : (and be followed by a barrier), we are not interested. */
4604 506 : if (single_succ_p (BLOCK_FOR_INSN (jump)))
4605 : return NULL;
4606 :
4607 506 : return FALLTHRU_EDGE (BLOCK_FOR_INSN (jump))->dest;
4608 : }
4609 :
4610 : /* Remove all notes from BB. */
4611 : static void
4612 1074 : init_bb (basic_block bb)
4613 : {
4614 1074 : remove_notes (bb_note (bb), BB_END (bb));
4615 1074 : BB_NOTE_LIST (bb) = note_list;
4616 1074 : }
4617 :
4618 : void
4619 810 : sel_init_bbs (bb_vec_t bbs)
4620 : {
4621 810 : const struct sched_scan_info_def ssi =
4622 : {
4623 : extend_bb_info, /* extend_bb */
4624 : init_bb, /* init_bb */
4625 : NULL, /* extend_insn */
4626 : NULL /* init_insn */
4627 : };
4628 :
4629 810 : sched_scan (&ssi, bbs);
4630 810 : }
4631 :
4632 : /* Restore notes for the whole region. */
4633 : static void
4634 739 : sel_restore_notes (void)
4635 : {
4636 739 : int bb;
4637 739 : insn_t insn;
4638 :
4639 1753 : for (bb = 0; bb < current_nr_blocks; bb++)
4640 : {
4641 1014 : basic_block first, last;
4642 :
4643 1014 : first = EBB_FIRST_BB (bb);
4644 1014 : last = EBB_LAST_BB (bb)->next_bb;
4645 :
4646 1014 : do
4647 : {
4648 1014 : note_list = BB_NOTE_LIST (first);
4649 1014 : restore_other_notes (NULL, first);
4650 1014 : BB_NOTE_LIST (first) = NULL;
4651 :
4652 7769 : FOR_BB_INSNS (first, insn)
4653 6755 : if (NONDEBUG_INSN_P (insn))
4654 4476 : reemit_notes (insn);
4655 :
4656 1014 : first = first->next_bb;
4657 : }
4658 1014 : while (first != last);
4659 : }
4660 739 : }
4661 :
4662 : /* Free per-bb data structures. */
4663 : void
4664 739 : sel_finish_bbs (void)
4665 : {
4666 739 : sel_restore_notes ();
4667 :
4668 : /* Remove current loop preheader from this loop. */
4669 739 : if (current_loop_nest)
4670 54 : sel_remove_loop_preheader ();
4671 :
4672 739 : finish_region_bb_info ();
4673 739 : }
4674 :
4675 : /* Return true if INSN has a single successor of type FLAGS. */
4676 : bool
4677 1441 : sel_insn_has_single_succ_p (insn_t insn, int flags)
4678 : {
4679 1441 : insn_t succ;
4680 1441 : succ_iterator si;
4681 1441 : bool first_p = true;
4682 :
4683 2882 : FOR_EACH_SUCC_1 (succ, si, insn, flags)
4684 : {
4685 1444 : if (first_p)
4686 1441 : first_p = false;
4687 : else
4688 : return false;
4689 : }
4690 :
4691 : return true;
4692 : }
4693 :
4694 : /* Allocate successor's info. */
4695 : static struct succs_info *
4696 8213 : alloc_succs_info (void)
4697 : {
4698 8213 : if (succs_info_pool.top == succs_info_pool.max_top)
4699 : {
4700 293 : int i;
4701 :
4702 293 : if (++succs_info_pool.max_top >= succs_info_pool.size)
4703 0 : gcc_unreachable ();
4704 :
4705 293 : i = ++succs_info_pool.top;
4706 293 : succs_info_pool.stack[i].succs_ok.create (10);
4707 293 : succs_info_pool.stack[i].succs_other.create (10);
4708 293 : succs_info_pool.stack[i].probs_ok.create (10);
4709 : }
4710 : else
4711 7920 : succs_info_pool.top++;
4712 :
4713 8213 : return &succs_info_pool.stack[succs_info_pool.top];
4714 : }
4715 :
4716 : /* Free successor's info. */
4717 : void
4718 8213 : free_succs_info (struct succs_info * sinfo)
4719 : {
4720 8213 : gcc_assert (succs_info_pool.top >= 0
4721 : && &succs_info_pool.stack[succs_info_pool.top] == sinfo);
4722 8213 : succs_info_pool.top--;
4723 :
4724 : /* Clear stale info. */
4725 16426 : sinfo->succs_ok.block_remove (0, sinfo->succs_ok.length ());
4726 16426 : sinfo->succs_other.block_remove (0, sinfo->succs_other.length ());
4727 16426 : sinfo->probs_ok.block_remove (0, sinfo->probs_ok.length ());
4728 8213 : sinfo->all_prob = 0;
4729 8213 : sinfo->succs_ok_n = 0;
4730 8213 : sinfo->all_succs_n = 0;
4731 8213 : }
4732 :
4733 : /* Compute successor info for INSN. FLAGS are the flags passed
4734 : to the FOR_EACH_SUCC_1 iterator. */
4735 : struct succs_info *
4736 8213 : compute_succs_info (insn_t insn, short flags)
4737 : {
4738 8213 : succ_iterator si;
4739 8213 : insn_t succ;
4740 8213 : struct succs_info *sinfo = alloc_succs_info ();
4741 :
4742 : /* Traverse *all* successors and decide what to do with each. */
4743 21173 : FOR_EACH_SUCC_1 (succ, si, insn, SUCCS_ALL)
4744 : {
4745 : /* FIXME: this doesn't work for skipping to loop exits, as we don't
4746 : perform code motion through inner loops. */
4747 12960 : short current_flags = si.current_flags & ~SUCCS_SKIP_TO_LOOP_EXITS;
4748 :
4749 12960 : if (current_flags & flags)
4750 : {
4751 6061 : sinfo->succs_ok.safe_push (succ);
4752 12122 : sinfo->probs_ok.safe_push (
4753 : /* FIXME: Improve calculation when skipping
4754 : inner loop to exits. */
4755 6061 : si.bb_end
4756 11508 : ? (si.e1->probability.initialized_p ()
4757 6061 : ? si.e1->probability.to_reg_br_prob_base ()
4758 : : 0)
4759 : : REG_BR_PROB_BASE);
4760 6061 : sinfo->succs_ok_n++;
4761 : }
4762 : else
4763 6899 : sinfo->succs_other.safe_push (succ);
4764 :
4765 : /* Compute all_prob. */
4766 12960 : if (!si.bb_end)
4767 0 : sinfo->all_prob = REG_BR_PROB_BASE;
4768 12960 : else if (si.e1->probability.initialized_p ())
4769 12132 : sinfo->all_prob += si.e1->probability.to_reg_br_prob_base ();
4770 :
4771 12960 : sinfo->all_succs_n++;
4772 : }
4773 :
4774 8213 : return sinfo;
4775 : }
4776 :
4777 : /* Return the predecessors of BB in PREDS and their number in N.
4778 : Empty blocks are skipped. SIZE is used to allocate PREDS. */
4779 : static void
4780 1 : cfg_preds_1 (basic_block bb, insn_t **preds, int *n, int *size)
4781 : {
4782 1 : edge e;
4783 1 : edge_iterator ei;
4784 :
4785 1 : gcc_assert (BLOCK_TO_BB (bb->index) != 0);
4786 :
4787 2 : FOR_EACH_EDGE (e, ei, bb->preds)
4788 : {
4789 1 : basic_block pred_bb = e->src;
4790 1 : insn_t bb_end = BB_END (pred_bb);
4791 :
4792 1 : if (!in_current_region_p (pred_bb))
4793 : {
4794 0 : gcc_assert (flag_sel_sched_pipelining_outer_loops
4795 : && current_loop_nest);
4796 0 : continue;
4797 : }
4798 :
4799 1 : if (sel_bb_empty_p (pred_bb))
4800 0 : cfg_preds_1 (pred_bb, preds, n, size);
4801 : else
4802 : {
4803 1 : if (*n == *size)
4804 1 : *preds = XRESIZEVEC (insn_t, *preds,
4805 : (*size = 2 * *size + 1));
4806 1 : (*preds)[(*n)++] = bb_end;
4807 : }
4808 : }
4809 :
4810 1 : gcc_assert (*n != 0
4811 : || (flag_sel_sched_pipelining_outer_loops
4812 : && current_loop_nest));
4813 1 : }
4814 :
4815 : /* Find all predecessors of BB and record them in PREDS and their number
4816 : in N. Empty blocks are skipped, and only normal (forward in-region)
4817 : edges are processed. */
4818 : static void
4819 1 : cfg_preds (basic_block bb, insn_t **preds, int *n)
4820 : {
4821 1 : int size = 0;
4822 :
4823 1 : *preds = NULL;
4824 1 : *n = 0;
4825 1 : cfg_preds_1 (bb, preds, n, &size);
4826 0 : }
4827 :
4828 : /* Returns true if we are moving INSN through join point. */
4829 : bool
4830 1750 : sel_num_cfg_preds_gt_1 (insn_t insn)
4831 : {
4832 1750 : basic_block bb;
4833 :
4834 1750 : if (!sel_bb_head_p (insn) || INSN_BB (insn) == 0)
4835 : return false;
4836 :
4837 935 : bb = BLOCK_FOR_INSN (insn);
4838 :
4839 935 : while (1)
4840 : {
4841 935 : if (EDGE_COUNT (bb->preds) > 1)
4842 : return true;
4843 :
4844 525 : gcc_assert (EDGE_PRED (bb, 0)->dest == bb);
4845 525 : bb = EDGE_PRED (bb, 0)->src;
4846 :
4847 525 : if (!sel_bb_empty_p (bb))
4848 : break;
4849 : }
4850 :
4851 : return false;
4852 : }
4853 :
4854 : /* Returns true when BB should be the end of an ebb. Adapted from the
4855 : code in sched-ebb.cc. */
4856 : bool
4857 1103 : bb_ends_ebb_p (basic_block bb)
4858 : {
4859 1103 : basic_block next_bb = bb_next_bb (bb);
4860 1103 : edge e;
4861 :
4862 1103 : if (next_bb == EXIT_BLOCK_PTR_FOR_FN (cfun)
4863 990 : || bitmap_bit_p (forced_ebb_heads, next_bb->index)
4864 2007 : || (LABEL_P (BB_HEAD (next_bb))
4865 : /* NB: LABEL_NUSES () is not maintained outside of jump.cc.
4866 : Work around that. */
4867 363 : && !single_pred_p (next_bb)))
4868 : return true;
4869 :
4870 565 : if (!in_current_region_p (next_bb))
4871 : return true;
4872 :
4873 368 : e = find_fallthru_edge (bb->succs);
4874 368 : if (e)
4875 : {
4876 366 : gcc_assert (e->dest == next_bb);
4877 :
4878 : return false;
4879 : }
4880 :
4881 : return true;
4882 : }
4883 :
4884 : /* Returns true when INSN and SUCC are in the same EBB, given that SUCC is a
4885 : successor of INSN. */
4886 : bool
4887 252 : in_same_ebb_p (insn_t insn, insn_t succ)
4888 : {
4889 252 : basic_block ptr = BLOCK_FOR_INSN (insn);
4890 :
4891 720 : for (;;)
4892 : {
4893 486 : if (ptr == BLOCK_FOR_INSN (succ))
4894 : return true;
4895 :
4896 342 : if (bb_ends_ebb_p (ptr))
4897 : return false;
4898 :
4899 234 : ptr = bb_next_bb (ptr);
4900 : }
4901 : }
4902 :
4903 : /* Recomputes the reverse topological order for the function and
4904 : saves it in REV_TOP_ORDER_INDEX. REV_TOP_ORDER_INDEX_LEN is also
4905 : modified appropriately. */
4906 : static void
4907 44 : recompute_rev_top_order (void)
4908 : {
4909 44 : int *postorder;
4910 44 : int n_blocks, i;
4911 :
4912 44 : if (!rev_top_order_index
4913 1 : || rev_top_order_index_len < last_basic_block_for_fn (cfun))
4914 : {
4915 43 : rev_top_order_index_len = last_basic_block_for_fn (cfun);
4916 43 : rev_top_order_index = XRESIZEVEC (int, rev_top_order_index,
4917 : rev_top_order_index_len);
4918 : }
4919 :
4920 44 : postorder = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
4921 :
4922 44 : n_blocks = post_order_compute (postorder, true, false);
4923 44 : gcc_assert (n_basic_blocks_for_fn (cfun) == n_blocks);
4924 :
4925 : /* Build reverse function: for each basic block with BB->INDEX == K
4926 : rev_top_order_index[K] is it's reverse topological sort number. */
4927 660 : for (i = 0; i < n_blocks; i++)
4928 : {
4929 616 : gcc_assert (postorder[i] < rev_top_order_index_len);
4930 616 : rev_top_order_index[postorder[i]] = i;
4931 : }
4932 :
4933 44 : free (postorder);
4934 44 : }
4935 :
4936 : /* Clear all flags from insns in BB that could spoil its rescheduling. */
4937 : void
4938 136 : clear_outdated_rtx_info (basic_block bb)
4939 : {
4940 136 : rtx_insn *insn;
4941 :
4942 1131 : FOR_BB_INSNS (bb, insn)
4943 995 : if (INSN_P (insn))
4944 : {
4945 789 : SCHED_GROUP_P (insn) = 0;
4946 789 : INSN_AFTER_STALL_P (insn) = 0;
4947 789 : INSN_SCHED_TIMES (insn) = 0;
4948 789 : EXPR_PRIORITY_ADJ (INSN_EXPR (insn)) = 0;
4949 :
4950 : /* We cannot use the changed caches, as previously we could ignore
4951 : the LHS dependence due to enabled renaming and transform
4952 : the expression, and currently we'll be unable to do this. */
4953 789 : htab_empty (INSN_TRANSFORMED_INSNS (insn));
4954 : }
4955 136 : }
4956 :
4957 : /* Add BB_NOTE to the pool of available basic block notes. */
4958 : static void
4959 114 : return_bb_to_pool (basic_block bb)
4960 : {
4961 114 : rtx_note *note = bb_note (bb);
4962 :
4963 114 : gcc_assert (NOTE_BASIC_BLOCK (note) == bb
4964 : && bb->aux == NULL);
4965 :
4966 : /* It turns out that current cfg infrastructure does not support
4967 : reuse of basic blocks. Don't bother for now. */
4968 : /*bb_note_pool.safe_push (note);*/
4969 114 : }
4970 :
4971 : /* Get a bb_note from pool or return NULL_RTX if pool is empty. */
4972 : static rtx_note *
4973 64 : get_bb_note_from_pool (void)
4974 : {
4975 64 : if (bb_note_pool.is_empty ())
4976 : return NULL;
4977 : else
4978 : {
4979 0 : rtx_note *note = bb_note_pool.pop ();
4980 :
4981 0 : SET_PREV_INSN (note) = NULL_RTX;
4982 0 : SET_NEXT_INSN (note) = NULL_RTX;
4983 :
4984 0 : return note;
4985 : }
4986 : }
4987 :
4988 : /* Free bb_note_pool. */
4989 : void
4990 131 : free_bb_note_pool (void)
4991 : {
4992 131 : bb_note_pool.release ();
4993 131 : }
4994 :
4995 : /* Setup scheduler pool and successor structure. */
4996 : void
4997 131 : alloc_sched_pools (void)
4998 : {
4999 131 : int succs_size;
5000 :
5001 131 : succs_size = MAX_WS + 1;
5002 131 : succs_info_pool.stack = XCNEWVEC (struct succs_info, succs_size);
5003 131 : succs_info_pool.size = succs_size;
5004 131 : succs_info_pool.top = -1;
5005 131 : succs_info_pool.max_top = -1;
5006 131 : }
5007 :
5008 : /* Free the pools. */
5009 : void
5010 131 : free_sched_pools (void)
5011 : {
5012 131 : int i;
5013 :
5014 131 : sched_lists_pool.release ();
5015 131 : gcc_assert (succs_info_pool.top == -1);
5016 424 : for (i = 0; i <= succs_info_pool.max_top; i++)
5017 : {
5018 293 : succs_info_pool.stack[i].succs_ok.release ();
5019 293 : succs_info_pool.stack[i].succs_other.release ();
5020 293 : succs_info_pool.stack[i].probs_ok.release ();
5021 : }
5022 131 : free (succs_info_pool.stack);
5023 131 : }
5024 :
5025 :
5026 : /* Returns a position in RGN where BB can be inserted retaining
5027 : topological order. */
5028 : static int
5029 71 : find_place_to_insert_bb (basic_block bb, int rgn)
5030 : {
5031 71 : bool has_preds_outside_rgn = false;
5032 71 : edge e;
5033 71 : edge_iterator ei;
5034 :
5035 : /* Find whether we have preds outside the region. */
5036 143 : FOR_EACH_EDGE (e, ei, bb->preds)
5037 72 : if (!in_current_region_p (e->src))
5038 : {
5039 : has_preds_outside_rgn = true;
5040 : break;
5041 : }
5042 :
5043 : /* Recompute the top order -- needed when we have > 1 pred
5044 : and in case we don't have preds outside. */
5045 71 : if (flag_sel_sched_pipelining_outer_loops
5046 71 : && (has_preds_outside_rgn || EDGE_COUNT (bb->preds) > 1))
5047 : {
5048 1 : int i, bbi = bb->index, cur_bbi;
5049 :
5050 1 : recompute_rev_top_order ();
5051 2 : for (i = RGN_NR_BLOCKS (rgn) - 1; i >= 0; i--)
5052 : {
5053 2 : cur_bbi = BB_TO_BLOCK (i);
5054 2 : if (rev_top_order_index[bbi]
5055 2 : < rev_top_order_index[cur_bbi])
5056 : break;
5057 : }
5058 :
5059 : /* We skipped the right block, so we increase i. We accommodate
5060 : it for increasing by step later, so we decrease i. */
5061 : return (i + 1) - 1;
5062 : }
5063 70 : else if (has_preds_outside_rgn)
5064 : {
5065 : /* This is the case when we generate an extra empty block
5066 : to serve as region head during pipelining. */
5067 0 : e = EDGE_SUCC (bb, 0);
5068 0 : gcc_assert (EDGE_COUNT (bb->succs) == 1
5069 : && in_current_region_p (EDGE_SUCC (bb, 0)->dest)
5070 : && (BLOCK_TO_BB (e->dest->index) == 0));
5071 : return -1;
5072 : }
5073 :
5074 : /* We don't have preds outside the region. We should have
5075 : the only pred, because the multiple preds case comes from
5076 : the pipelining of outer loops, and that is handled above.
5077 : Just take the bbi of this single pred. */
5078 70 : if (EDGE_COUNT (bb->succs) > 0)
5079 : {
5080 70 : int pred_bbi;
5081 :
5082 70 : gcc_assert (EDGE_COUNT (bb->preds) == 1);
5083 :
5084 70 : pred_bbi = EDGE_PRED (bb, 0)->src->index;
5085 70 : return BLOCK_TO_BB (pred_bbi);
5086 : }
5087 : else
5088 : /* BB has no successors. It is safe to put it in the end. */
5089 0 : return current_nr_blocks - 1;
5090 : }
5091 :
5092 : /* Deletes an empty basic block freeing its data. */
5093 : static void
5094 22 : delete_and_free_basic_block (basic_block bb)
5095 : {
5096 22 : gcc_assert (sel_bb_empty_p (bb));
5097 :
5098 22 : if (BB_LV_SET (bb))
5099 10 : free_lv_set (bb);
5100 :
5101 22 : bitmap_clear_bit (blocks_to_reschedule, bb->index);
5102 :
5103 : /* Can't assert av_set properties because we use sel_aremove_bb
5104 : when removing loop preheader from the region. At the point of
5105 : removing the preheader we already have deallocated sel_region_bb_info. */
5106 22 : gcc_assert (BB_LV_SET (bb) == NULL
5107 : && !BB_LV_SET_VALID_P (bb)
5108 : && BB_AV_LEVEL (bb) == 0
5109 : && BB_AV_SET (bb) == NULL);
5110 :
5111 22 : delete_basic_block (bb);
5112 22 : }
5113 :
5114 : /* Add BB to the current region and update the region data. */
5115 : static void
5116 71 : add_block_to_current_region (basic_block bb)
5117 : {
5118 71 : int i, pos, bbi = -2, rgn;
5119 :
5120 71 : rgn = CONTAINING_RGN (BB_TO_BLOCK (0));
5121 71 : bbi = find_place_to_insert_bb (bb, rgn);
5122 71 : bbi += 1;
5123 71 : pos = RGN_BLOCKS (rgn) + bbi;
5124 :
5125 71 : gcc_assert (RGN_HAS_REAL_EBB (rgn) == 0
5126 : && ebb_head[bbi] == pos);
5127 :
5128 : /* Make a place for the new block. */
5129 71 : extend_regions ();
5130 :
5131 454 : for (i = RGN_BLOCKS (rgn + 1) - 1; i >= pos; i--)
5132 383 : BLOCK_TO_BB (rgn_bb_table[i])++;
5133 :
5134 71 : memmove (rgn_bb_table + pos + 1,
5135 71 : rgn_bb_table + pos,
5136 71 : (RGN_BLOCKS (nr_regions) - pos) * sizeof (*rgn_bb_table));
5137 :
5138 : /* Initialize data for BB. */
5139 71 : rgn_bb_table[pos] = bb->index;
5140 71 : BLOCK_TO_BB (bb->index) = bbi;
5141 71 : CONTAINING_RGN (bb->index) = rgn;
5142 :
5143 71 : RGN_NR_BLOCKS (rgn)++;
5144 :
5145 424 : for (i = rgn + 1; i <= nr_regions; i++)
5146 353 : RGN_BLOCKS (i)++;
5147 71 : }
5148 :
5149 : /* Remove BB from the current region and update the region data. */
5150 : static void
5151 114 : remove_bb_from_region (basic_block bb)
5152 : {
5153 114 : int i, pos, bbi = -2, rgn;
5154 :
5155 114 : rgn = CONTAINING_RGN (BB_TO_BLOCK (0));
5156 114 : bbi = BLOCK_TO_BB (bb->index);
5157 114 : pos = RGN_BLOCKS (rgn) + bbi;
5158 :
5159 114 : gcc_assert (RGN_HAS_REAL_EBB (rgn) == 0
5160 : && ebb_head[bbi] == pos);
5161 :
5162 847 : for (i = RGN_BLOCKS (rgn + 1) - 1; i >= pos; i--)
5163 733 : BLOCK_TO_BB (rgn_bb_table[i])--;
5164 :
5165 114 : memmove (rgn_bb_table + pos,
5166 114 : rgn_bb_table + pos + 1,
5167 114 : (RGN_BLOCKS (nr_regions) - pos) * sizeof (*rgn_bb_table));
5168 :
5169 114 : RGN_NR_BLOCKS (rgn)--;
5170 795 : for (i = rgn + 1; i <= nr_regions; i++)
5171 681 : RGN_BLOCKS (i)--;
5172 114 : }
5173 :
5174 : /* Add BB to the current region and update all data. If BB is NULL, add all
5175 : blocks from last_added_blocks vector. */
5176 : static void
5177 71 : sel_add_bb (basic_block bb)
5178 : {
5179 : /* Extend luids so that new notes will receive zero luids. */
5180 71 : sched_extend_luids ();
5181 71 : sched_init_bbs ();
5182 71 : sel_init_bbs (last_added_blocks);
5183 :
5184 : /* When bb is passed explicitly, the vector should contain
5185 : the only element that equals to bb; otherwise, the vector
5186 : should not be NULL. */
5187 71 : gcc_assert (last_added_blocks.exists ());
5188 :
5189 71 : if (bb != NULL)
5190 : {
5191 142 : gcc_assert (last_added_blocks.length () == 1
5192 : && last_added_blocks[0] == bb);
5193 71 : add_block_to_current_region (bb);
5194 :
5195 : /* We associate creating/deleting data sets with the first insn
5196 : appearing / disappearing in the bb. */
5197 71 : if (!sel_bb_empty_p (bb) && BB_LV_SET (bb) == NULL)
5198 64 : create_initial_data_sets (bb);
5199 :
5200 71 : last_added_blocks.release ();
5201 : }
5202 : else
5203 : /* BB is NULL - process LAST_ADDED_BLOCKS instead. */
5204 : {
5205 : int i;
5206 : basic_block temp_bb = NULL;
5207 :
5208 0 : for (i = 0;
5209 0 : last_added_blocks.iterate (i, &bb); i++)
5210 : {
5211 0 : add_block_to_current_region (bb);
5212 0 : temp_bb = bb;
5213 : }
5214 :
5215 : /* We need to fetch at least one bb so we know the region
5216 : to update. */
5217 0 : gcc_assert (temp_bb != NULL);
5218 0 : bb = temp_bb;
5219 :
5220 0 : last_added_blocks.release ();
5221 : }
5222 :
5223 71 : rgn_setup_region (CONTAINING_RGN (bb->index));
5224 71 : }
5225 :
5226 : /* Remove BB from the current region and update all data.
5227 : If REMOVE_FROM_CFG_PBB is true, also remove the block cfom cfg. */
5228 : static void
5229 114 : sel_remove_bb (basic_block bb, bool remove_from_cfg_p)
5230 : {
5231 114 : unsigned idx = bb->index;
5232 :
5233 114 : gcc_assert (bb != NULL && BB_NOTE_LIST (bb) == NULL_RTX);
5234 :
5235 114 : remove_bb_from_region (bb);
5236 114 : return_bb_to_pool (bb);
5237 114 : bitmap_clear_bit (blocks_to_reschedule, idx);
5238 :
5239 114 : if (remove_from_cfg_p)
5240 : {
5241 12 : basic_block succ = single_succ (bb);
5242 12 : delete_and_free_basic_block (bb);
5243 12 : set_immediate_dominator (CDI_DOMINATORS, succ,
5244 : recompute_dominator (CDI_DOMINATORS, succ));
5245 : }
5246 :
5247 114 : rgn_setup_region (CONTAINING_RGN (idx));
5248 114 : }
5249 :
5250 : /* Concatenate info of EMPTY_BB to info of MERGE_BB. */
5251 : static void
5252 60 : move_bb_info (basic_block merge_bb, basic_block empty_bb)
5253 : {
5254 60 : if (in_current_region_p (merge_bb))
5255 60 : concat_note_lists (BB_NOTE_LIST (empty_bb),
5256 60 : &BB_NOTE_LIST (merge_bb));
5257 60 : BB_NOTE_LIST (empty_bb) = NULL;
5258 :
5259 60 : }
5260 :
5261 : /* Remove EMPTY_BB. If REMOVE_FROM_CFG_P is false, remove EMPTY_BB from
5262 : region, but keep it in CFG. */
5263 : static void
5264 60 : remove_empty_bb (basic_block empty_bb, bool remove_from_cfg_p)
5265 : {
5266 : /* The block should contain just a note or a label.
5267 : We try to check whether it is unused below. */
5268 60 : gcc_assert (BB_HEAD (empty_bb) == BB_END (empty_bb)
5269 : || LABEL_P (BB_HEAD (empty_bb)));
5270 :
5271 : /* If basic block has predecessors or successors, redirect them. */
5272 60 : if (remove_from_cfg_p
5273 60 : && (EDGE_COUNT (empty_bb->preds) > 0
5274 10 : || EDGE_COUNT (empty_bb->succs) > 0))
5275 : {
5276 12 : basic_block pred;
5277 12 : basic_block succ;
5278 :
5279 : /* We need to init PRED and SUCC before redirecting edges. */
5280 12 : if (EDGE_COUNT (empty_bb->preds) > 0)
5281 : {
5282 2 : edge e;
5283 :
5284 2 : gcc_assert (EDGE_COUNT (empty_bb->preds) == 1);
5285 :
5286 2 : e = EDGE_PRED (empty_bb, 0);
5287 2 : gcc_assert (e->src == empty_bb->prev_bb
5288 : && (e->flags & EDGE_FALLTHRU));
5289 :
5290 : pred = empty_bb->prev_bb;
5291 : }
5292 : else
5293 : pred = NULL;
5294 :
5295 12 : if (EDGE_COUNT (empty_bb->succs) > 0)
5296 : {
5297 : /* We do not check fallthruness here as above, because
5298 : after removing a jump the edge may actually be not fallthru. */
5299 12 : gcc_assert (EDGE_COUNT (empty_bb->succs) == 1);
5300 12 : succ = EDGE_SUCC (empty_bb, 0)->dest;
5301 : }
5302 : else
5303 : succ = NULL;
5304 :
5305 12 : if (EDGE_COUNT (empty_bb->preds) > 0 && succ != NULL)
5306 : {
5307 2 : edge e = EDGE_PRED (empty_bb, 0);
5308 :
5309 2 : if (e->flags & EDGE_FALLTHRU)
5310 2 : redirect_edge_succ_nodup (e, succ);
5311 : else
5312 0 : sel_redirect_edge_and_branch (EDGE_PRED (empty_bb, 0), succ);
5313 : }
5314 :
5315 12 : if (EDGE_COUNT (empty_bb->succs) > 0 && pred != NULL)
5316 : {
5317 2 : edge e = EDGE_SUCC (empty_bb, 0);
5318 :
5319 2 : if (find_edge (pred, e->dest) == NULL)
5320 0 : redirect_edge_pred (e, pred);
5321 : }
5322 : }
5323 :
5324 : /* Finish removing. */
5325 60 : sel_remove_bb (empty_bb, remove_from_cfg_p);
5326 60 : }
5327 :
5328 : /* An implementation of create_basic_block hook, which additionally updates
5329 : per-bb data structures. */
5330 : static basic_block
5331 64 : sel_create_basic_block (void *headp, void *endp, basic_block after)
5332 : {
5333 64 : basic_block new_bb;
5334 64 : rtx_note *new_bb_note;
5335 :
5336 64 : gcc_assert (flag_sel_sched_pipelining_outer_loops
5337 : || !last_added_blocks.exists ());
5338 :
5339 64 : new_bb_note = get_bb_note_from_pool ();
5340 :
5341 64 : if (new_bb_note == NULL_RTX)
5342 64 : new_bb = orig_cfg_hooks->create_basic_block (headp, endp, after);
5343 : else
5344 : {
5345 0 : new_bb = create_basic_block_structure ((rtx_insn *) headp,
5346 : (rtx_insn *) endp,
5347 : new_bb_note, after);
5348 0 : new_bb->aux = NULL;
5349 : }
5350 :
5351 64 : last_added_blocks.safe_push (new_bb);
5352 :
5353 64 : return new_bb;
5354 : }
5355 :
5356 : /* Implement sched_init_only_bb (). */
5357 : static void
5358 0 : sel_init_only_bb (basic_block bb, basic_block after)
5359 : {
5360 0 : gcc_assert (after == NULL);
5361 :
5362 0 : extend_regions ();
5363 0 : rgn_make_new_region_out_of_new_block (bb);
5364 0 : }
5365 :
5366 : /* Update the latch when we've splitted or merged it from FROM block to TO.
5367 : This should be checked for all outer loops, too. */
5368 : static void
5369 111 : change_loops_latches (basic_block from, basic_block to)
5370 : {
5371 111 : gcc_assert (from != to);
5372 :
5373 111 : if (current_loop_nest)
5374 : {
5375 : class loop *loop;
5376 :
5377 321 : for (loop = current_loop_nest; loop; loop = loop_outer (loop))
5378 214 : if (considered_for_pipelining_p (loop) && loop->latch == from)
5379 : {
5380 0 : gcc_assert (loop == current_loop_nest);
5381 0 : loop->latch = to;
5382 0 : gcc_assert (loop_latch_edge (loop));
5383 : }
5384 : }
5385 111 : }
5386 :
5387 : /* Splits BB on two basic blocks, adding it to the region and extending
5388 : per-bb data structures. Returns the newly created bb. */
5389 : static basic_block
5390 63 : sel_split_block (basic_block bb, rtx after)
5391 : {
5392 63 : basic_block new_bb;
5393 63 : insn_t insn;
5394 :
5395 63 : new_bb = sched_split_block_1 (bb, after);
5396 63 : sel_add_bb (new_bb);
5397 :
5398 : /* This should be called after sel_add_bb, because this uses
5399 : CONTAINING_RGN for the new block, which is not yet initialized.
5400 : FIXME: this function may be a no-op now. */
5401 63 : change_loops_latches (bb, new_bb);
5402 :
5403 : /* Update ORIG_BB_INDEX for insns moved into the new block. */
5404 456 : FOR_BB_INSNS (new_bb, insn)
5405 393 : if (INSN_P (insn))
5406 330 : EXPR_ORIG_BB_INDEX (INSN_EXPR (insn)) = new_bb->index;
5407 :
5408 63 : if (sel_bb_empty_p (bb))
5409 : {
5410 63 : gcc_assert (!sel_bb_empty_p (new_bb));
5411 :
5412 : /* NEW_BB has data sets that need to be updated and BB holds
5413 : data sets that should be removed. Exchange these data sets
5414 : so that we won't lose BB's valid data sets. */
5415 63 : exchange_data_sets (new_bb, bb);
5416 63 : free_data_sets (bb);
5417 : }
5418 :
5419 63 : if (!sel_bb_empty_p (new_bb)
5420 63 : && bitmap_bit_p (blocks_to_reschedule, bb->index))
5421 31 : bitmap_set_bit (blocks_to_reschedule, new_bb->index);
5422 :
5423 63 : return new_bb;
5424 : }
5425 :
5426 : /* If BB ends with a jump insn whose ID is bigger then PREV_MAX_UID, return it.
5427 : Otherwise returns NULL. */
5428 : static rtx_insn *
5429 64 : check_for_new_jump (basic_block bb, int prev_max_uid)
5430 : {
5431 64 : rtx_insn *end;
5432 :
5433 64 : end = sel_bb_end (bb);
5434 64 : if (end && INSN_UID (end) >= prev_max_uid)
5435 12 : return end;
5436 : return NULL;
5437 : }
5438 :
5439 : /* Look for a new jump either in FROM_BB block or in newly created JUMP_BB block.
5440 : New means having UID at least equal to PREV_MAX_UID. */
5441 : static rtx_insn *
5442 103 : find_new_jump (basic_block from, basic_block jump_bb, int prev_max_uid)
5443 : {
5444 103 : rtx_insn *jump;
5445 :
5446 : /* Return immediately if no new insns were emitted. */
5447 103 : if (get_max_uid () == prev_max_uid)
5448 : return NULL;
5449 :
5450 : /* Now check both blocks for new jumps. It will ever be only one. */
5451 63 : if ((jump = check_for_new_jump (from, prev_max_uid)))
5452 : return jump;
5453 :
5454 52 : if (jump_bb != NULL
5455 52 : && (jump = check_for_new_jump (jump_bb, prev_max_uid)))
5456 : return jump;
5457 : return NULL;
5458 : }
5459 :
5460 : /* Splits E and adds the newly created basic block to the current region.
5461 : Returns this basic block. */
5462 : basic_block
5463 0 : sel_split_edge (edge e)
5464 : {
5465 0 : basic_block new_bb, src, other_bb = NULL;
5466 0 : int prev_max_uid;
5467 0 : rtx_insn *jump;
5468 :
5469 0 : src = e->src;
5470 0 : prev_max_uid = get_max_uid ();
5471 0 : new_bb = split_edge (e);
5472 :
5473 0 : if (flag_sel_sched_pipelining_outer_loops
5474 0 : && current_loop_nest)
5475 : {
5476 : int i;
5477 : basic_block bb;
5478 :
5479 : /* Some of the basic blocks might not have been added to the loop.
5480 : Add them here, until this is fixed in force_fallthru. */
5481 0 : for (i = 0;
5482 0 : last_added_blocks.iterate (i, &bb); i++)
5483 0 : if (!bb->loop_father)
5484 : {
5485 0 : add_bb_to_loop (bb, e->dest->loop_father);
5486 :
5487 0 : gcc_assert (!other_bb && (new_bb->index != bb->index));
5488 : other_bb = bb;
5489 : }
5490 : }
5491 :
5492 : /* Add all last_added_blocks to the region. */
5493 0 : sel_add_bb (NULL);
5494 :
5495 0 : jump = find_new_jump (src, new_bb, prev_max_uid);
5496 0 : if (jump)
5497 0 : sel_init_new_insn (jump, INSN_INIT_TODO_LUID | INSN_INIT_TODO_SIMPLEJUMP);
5498 :
5499 : /* Put the correct lv set on this block. */
5500 0 : if (other_bb && !sel_bb_empty_p (other_bb))
5501 0 : compute_live (sel_bb_head (other_bb));
5502 :
5503 0 : return new_bb;
5504 : }
5505 :
5506 : /* Implement sched_create_empty_bb (). */
5507 : static basic_block
5508 0 : sel_create_empty_bb (basic_block after)
5509 : {
5510 0 : basic_block new_bb;
5511 :
5512 0 : new_bb = sched_create_empty_bb_1 (after);
5513 :
5514 : /* We'll explicitly initialize NEW_BB via sel_init_only_bb () a bit
5515 : later. */
5516 0 : gcc_assert (last_added_blocks.length () == 1
5517 : && last_added_blocks[0] == new_bb);
5518 :
5519 0 : last_added_blocks.release ();
5520 0 : return new_bb;
5521 : }
5522 :
5523 : /* Implement sched_create_recovery_block. ORIG_INSN is where block
5524 : will be splitted to insert a check. */
5525 : basic_block
5526 0 : sel_create_recovery_block (insn_t orig_insn)
5527 : {
5528 0 : basic_block first_bb, second_bb, recovery_block;
5529 0 : basic_block before_recovery = NULL;
5530 0 : rtx_insn *jump;
5531 :
5532 0 : first_bb = BLOCK_FOR_INSN (orig_insn);
5533 0 : if (sel_bb_end_p (orig_insn))
5534 : {
5535 : /* Avoid introducing an empty block while splitting. */
5536 0 : gcc_assert (single_succ_p (first_bb));
5537 0 : second_bb = single_succ (first_bb);
5538 : }
5539 : else
5540 0 : second_bb = sched_split_block (first_bb, orig_insn);
5541 :
5542 0 : recovery_block = sched_create_recovery_block (&before_recovery);
5543 0 : if (before_recovery)
5544 0 : copy_lv_set_from (before_recovery, EXIT_BLOCK_PTR_FOR_FN (cfun));
5545 :
5546 0 : gcc_assert (sel_bb_empty_p (recovery_block));
5547 0 : sched_create_recovery_edges (first_bb, recovery_block, second_bb);
5548 0 : if (current_loops != NULL)
5549 0 : add_bb_to_loop (recovery_block, first_bb->loop_father);
5550 :
5551 0 : sel_add_bb (recovery_block);
5552 :
5553 0 : jump = BB_END (recovery_block);
5554 0 : gcc_assert (sel_bb_head (recovery_block) == jump);
5555 0 : sel_init_new_insn (jump, INSN_INIT_TODO_LUID | INSN_INIT_TODO_SIMPLEJUMP);
5556 :
5557 0 : return recovery_block;
5558 : }
5559 :
5560 : /* Merge basic block B into basic block A. */
5561 : static void
5562 48 : sel_merge_blocks (basic_block a, basic_block b)
5563 : {
5564 48 : gcc_assert (sel_bb_empty_p (b)
5565 : && EDGE_COUNT (b->preds) == 1
5566 : && EDGE_PRED (b, 0)->src == b->prev_bb);
5567 :
5568 48 : move_bb_info (b->prev_bb, b);
5569 48 : remove_empty_bb (b, false);
5570 48 : merge_blocks (a, b);
5571 48 : change_loops_latches (b, a);
5572 48 : }
5573 :
5574 : /* A wrapper for redirect_edge_and_branch_force, which also initializes
5575 : data structures for possibly created bb and insns. */
5576 : void
5577 12 : sel_redirect_edge_and_branch_force (edge e, basic_block to)
5578 : {
5579 12 : basic_block jump_bb, src, orig_dest = e->dest;
5580 12 : int prev_max_uid;
5581 12 : rtx_insn *jump;
5582 12 : int old_seqno = -1;
5583 :
5584 : /* This function is now used only for bookkeeping code creation, where
5585 : we'll never get the single pred of orig_dest block and thus will not
5586 : hit unreachable blocks when updating dominator info. */
5587 24 : gcc_assert (!sel_bb_empty_p (e->src)
5588 : && !single_pred_p (orig_dest));
5589 12 : src = e->src;
5590 12 : prev_max_uid = get_max_uid ();
5591 : /* Compute and pass old_seqno down to sel_init_new_insn only for the case
5592 : when the conditional jump being redirected may become unconditional. */
5593 12 : if (any_condjump_p (BB_END (src))
5594 12 : && INSN_SEQNO (BB_END (src)) >= 0)
5595 : old_seqno = INSN_SEQNO (BB_END (src));
5596 :
5597 12 : jump_bb = redirect_edge_and_branch_force (e, to);
5598 12 : if (jump_bb != NULL)
5599 1 : sel_add_bb (jump_bb);
5600 :
5601 : /* This function could not be used to spoil the loop structure by now,
5602 : thus we don't care to update anything. But check it to be sure. */
5603 12 : if (current_loop_nest
5604 11 : && pipelining_p)
5605 11 : gcc_assert (loop_latch_edge (current_loop_nest));
5606 :
5607 12 : jump = find_new_jump (src, jump_bb, prev_max_uid);
5608 12 : if (jump)
5609 12 : sel_init_new_insn (jump, INSN_INIT_TODO_LUID | INSN_INIT_TODO_SIMPLEJUMP,
5610 : old_seqno);
5611 12 : set_immediate_dominator (CDI_DOMINATORS, to,
5612 : recompute_dominator (CDI_DOMINATORS, to));
5613 12 : set_immediate_dominator (CDI_DOMINATORS, orig_dest,
5614 : recompute_dominator (CDI_DOMINATORS, orig_dest));
5615 12 : if (jump && sel_bb_head_p (jump))
5616 1 : compute_live (jump);
5617 12 : }
5618 :
5619 : /* A wrapper for redirect_edge_and_branch. Return TRUE if blocks connected by
5620 : redirected edge are in reverse topological order. */
5621 : bool
5622 91 : sel_redirect_edge_and_branch (edge e, basic_block to)
5623 : {
5624 91 : bool latch_edge_p;
5625 91 : basic_block src, orig_dest = e->dest;
5626 91 : int prev_max_uid;
5627 91 : rtx_insn *jump;
5628 91 : edge redirected;
5629 91 : bool recompute_toporder_p = false;
5630 91 : bool maybe_unreachable = single_pred_p (orig_dest);
5631 91 : int old_seqno = -1;
5632 :
5633 182 : latch_edge_p = (pipelining_p
5634 85 : && current_loop_nest
5635 176 : && e == loop_latch_edge (current_loop_nest));
5636 :
5637 91 : src = e->src;
5638 91 : prev_max_uid = get_max_uid ();
5639 :
5640 : /* Compute and pass old_seqno down to sel_init_new_insn only for the case
5641 : when the conditional jump being redirected may become unconditional. */
5642 91 : if (any_condjump_p (BB_END (src))
5643 91 : && INSN_SEQNO (BB_END (src)) >= 0)
5644 : old_seqno = INSN_SEQNO (BB_END (src));
5645 :
5646 91 : redirected = redirect_edge_and_branch (e, to);
5647 :
5648 91 : gcc_assert (redirected && !last_added_blocks.exists ());
5649 :
5650 : /* When we've redirected a latch edge, update the header. */
5651 91 : if (latch_edge_p)
5652 : {
5653 0 : current_loop_nest->header = to;
5654 0 : gcc_assert (loop_latch_edge (current_loop_nest));
5655 : }
5656 :
5657 : /* In rare situations, the topological relation between the blocks connected
5658 : by the redirected edge can change (see PR42245 for an example). Update
5659 : block_to_bb/bb_to_block. */
5660 91 : if (CONTAINING_RGN (e->src->index) == CONTAINING_RGN (to->index)
5661 88 : && BLOCK_TO_BB (e->src->index) > BLOCK_TO_BB (to->index))
5662 91 : recompute_toporder_p = true;
5663 :
5664 91 : jump = find_new_jump (src, NULL, prev_max_uid);
5665 91 : if (jump)
5666 0 : sel_init_new_insn (jump, INSN_INIT_TODO_LUID | INSN_INIT_TODO_SIMPLEJUMP, old_seqno);
5667 :
5668 : /* Only update dominator info when we don't have unreachable blocks.
5669 : Otherwise we'll update in maybe_tidy_empty_bb. */
5670 91 : if (!maybe_unreachable)
5671 : {
5672 81 : set_immediate_dominator (CDI_DOMINATORS, to,
5673 : recompute_dominator (CDI_DOMINATORS, to));
5674 81 : set_immediate_dominator (CDI_DOMINATORS, orig_dest,
5675 : recompute_dominator (CDI_DOMINATORS, orig_dest));
5676 : }
5677 91 : if (jump && sel_bb_head_p (jump))
5678 0 : compute_live (jump);
5679 91 : return recompute_toporder_p;
5680 : }
5681 :
5682 : /* This variable holds the cfg hooks used by the selective scheduler. */
5683 : static struct cfg_hooks sel_cfg_hooks;
5684 :
5685 : /* Register sel-sched cfg hooks. */
5686 : void
5687 739 : sel_register_cfg_hooks (void)
5688 : {
5689 739 : sched_split_block = sel_split_block;
5690 :
5691 739 : orig_cfg_hooks = get_cfg_hooks ();
5692 739 : sel_cfg_hooks = *orig_cfg_hooks;
5693 :
5694 739 : sel_cfg_hooks.create_basic_block = sel_create_basic_block;
5695 :
5696 739 : set_cfg_hooks (&sel_cfg_hooks);
5697 :
5698 739 : sched_init_only_bb = sel_init_only_bb;
5699 739 : sched_split_block = sel_split_block;
5700 739 : sched_create_empty_bb = sel_create_empty_bb;
5701 739 : }
5702 :
5703 : /* Unregister sel-sched cfg hooks. */
5704 : void
5705 739 : sel_unregister_cfg_hooks (void)
5706 : {
5707 739 : sched_create_empty_bb = NULL;
5708 739 : sched_split_block = NULL;
5709 739 : sched_init_only_bb = NULL;
5710 :
5711 739 : set_cfg_hooks (orig_cfg_hooks);
5712 739 : }
5713 :
5714 :
5715 : /* Emit an insn rtx based on PATTERN. If a jump insn is wanted,
5716 : LABEL is where this jump should be directed. */
5717 : rtx_insn *
5718 713 : create_insn_rtx_from_pattern (rtx pattern, rtx label)
5719 : {
5720 713 : rtx_insn *insn_rtx;
5721 :
5722 713 : gcc_assert (!INSN_P (pattern));
5723 :
5724 713 : start_sequence ();
5725 :
5726 713 : if (label == NULL_RTX)
5727 709 : insn_rtx = emit_insn (pattern);
5728 4 : else if (DEBUG_INSN_P (label))
5729 4 : insn_rtx = emit_debug_insn (pattern);
5730 : else
5731 : {
5732 0 : insn_rtx = emit_jump_insn (pattern);
5733 0 : JUMP_LABEL (insn_rtx) = label;
5734 0 : ++LABEL_NUSES (label);
5735 : }
5736 :
5737 713 : end_sequence ();
5738 :
5739 713 : sched_extend_luids ();
5740 713 : sched_extend_target ();
5741 713 : sched_deps_init (false);
5742 :
5743 : /* Initialize INSN_CODE now. */
5744 713 : recog_memoized (insn_rtx);
5745 713 : return insn_rtx;
5746 : }
5747 :
5748 : /* Create a new vinsn for INSN_RTX. FORCE_UNIQUE_P is true when the vinsn
5749 : must not be clonable. */
5750 : vinsn_t
5751 660 : create_vinsn_from_insn_rtx (rtx_insn *insn_rtx, bool force_unique_p)
5752 : {
5753 1320 : gcc_assert (INSN_P (insn_rtx) && !INSN_IN_STREAM_P (insn_rtx));
5754 :
5755 : /* If VINSN_TYPE is not USE, retain its uniqueness. */
5756 660 : return vinsn_create (insn_rtx, force_unique_p);
5757 : }
5758 :
5759 : /* Create a copy of INSN_RTX. */
5760 : rtx_insn *
5761 474 : create_copy_of_insn_rtx (rtx insn_rtx)
5762 : {
5763 474 : rtx_insn *res;
5764 474 : rtx link;
5765 :
5766 474 : if (DEBUG_INSN_P (insn_rtx))
5767 4 : return create_insn_rtx_from_pattern (copy_rtx (PATTERN (insn_rtx)),
5768 4 : insn_rtx);
5769 :
5770 470 : gcc_assert (NONJUMP_INSN_P (insn_rtx));
5771 :
5772 470 : res = create_insn_rtx_from_pattern (copy_rtx (PATTERN (insn_rtx)),
5773 : NULL_RTX);
5774 :
5775 : /* Locate the end of existing REG_NOTES in NEW_RTX. */
5776 470 : rtx *ptail = ®_NOTES (res);
5777 470 : while (*ptail != NULL_RTX)
5778 0 : ptail = &XEXP (*ptail, 1);
5779 :
5780 : /* Copy all REG_NOTES except REG_EQUAL/REG_EQUIV and REG_LABEL_OPERAND
5781 : since mark_jump_label will make them. REG_LABEL_TARGETs are created
5782 : there too, but are supposed to be sticky, so we copy them. */
5783 826 : for (link = REG_NOTES (insn_rtx); link; link = XEXP (link, 1))
5784 356 : if (REG_NOTE_KIND (link) != REG_LABEL_OPERAND
5785 : && REG_NOTE_KIND (link) != REG_EQUAL
5786 : && REG_NOTE_KIND (link) != REG_EQUIV)
5787 : {
5788 346 : *ptail = duplicate_reg_note (link);
5789 346 : ptail = &XEXP (*ptail, 1);
5790 : }
5791 :
5792 : return res;
5793 : }
5794 :
5795 : /* Change vinsn field of EXPR to hold NEW_VINSN. */
5796 : void
5797 3188 : change_vinsn_in_expr (expr_t expr, vinsn_t new_vinsn)
5798 : {
5799 3188 : vinsn_detach (EXPR_VINSN (expr));
5800 :
5801 3188 : EXPR_VINSN (expr) = new_vinsn;
5802 3188 : vinsn_attach (new_vinsn);
5803 3188 : }
5804 :
5805 : /* Helpers for global init. */
5806 : /* This structure is used to be able to call existing bundling mechanism
5807 : and calculate insn priorities. */
5808 : static struct haifa_sched_info sched_sel_haifa_sched_info =
5809 : {
5810 : NULL, /* init_ready_list */
5811 : NULL, /* can_schedule_ready_p */
5812 : NULL, /* schedule_more_p */
5813 : NULL, /* new_ready */
5814 : NULL, /* rgn_rank */
5815 : sel_print_insn, /* rgn_print_insn */
5816 : contributes_to_priority,
5817 : NULL, /* insn_finishes_block_p */
5818 :
5819 : NULL, NULL,
5820 : NULL, NULL,
5821 : 0, 0,
5822 :
5823 : NULL, /* add_remove_insn */
5824 : NULL, /* begin_schedule_ready */
5825 : NULL, /* begin_move_insn */
5826 : NULL, /* advance_target_bb */
5827 :
5828 : NULL,
5829 : NULL,
5830 :
5831 : SEL_SCHED | NEW_BBS
5832 : };
5833 :
5834 : /* Setup special insns used in the scheduler. */
5835 : void
5836 131 : setup_nop_and_exit_insns (void)
5837 : {
5838 131 : gcc_assert (nop_pattern == NULL_RTX
5839 : && exit_insn == NULL_RTX);
5840 :
5841 131 : nop_pattern = constm1_rtx;
5842 :
5843 131 : start_sequence ();
5844 131 : emit_insn (nop_pattern);
5845 131 : exit_insn = end_sequence ();
5846 131 : set_block_for_insn (exit_insn, EXIT_BLOCK_PTR_FOR_FN (cfun));
5847 131 : }
5848 :
5849 : /* Free special insns used in the scheduler. */
5850 : void
5851 131 : free_nop_and_exit_insns (void)
5852 : {
5853 131 : exit_insn = NULL;
5854 131 : nop_pattern = NULL_RTX;
5855 131 : }
5856 :
5857 : /* Setup a special vinsn used in new insns initialization. */
5858 : void
5859 739 : setup_nop_vinsn (void)
5860 : {
5861 739 : nop_vinsn = vinsn_create (exit_insn, false);
5862 739 : vinsn_attach (nop_vinsn);
5863 739 : }
5864 :
5865 : /* Free a special vinsn used in new insns initialization. */
5866 : void
5867 739 : free_nop_vinsn (void)
5868 : {
5869 739 : gcc_assert (VINSN_COUNT (nop_vinsn) == 1);
5870 739 : vinsn_detach (nop_vinsn);
5871 739 : nop_vinsn = NULL;
5872 739 : }
5873 :
5874 : /* Call a set_sched_flags hook. */
5875 : void
5876 1609 : sel_set_sched_flags (void)
5877 : {
5878 : /* ??? This means that set_sched_flags were called, and we decided to
5879 : support speculation. However, set_sched_flags also modifies flags
5880 : on current_sched_info, doing this only at global init. And we
5881 : sometimes change c_s_i later. So put the correct flags again. */
5882 1609 : if (spec_info && targetm.sched.set_sched_flags)
5883 0 : targetm.sched.set_sched_flags (spec_info);
5884 1609 : }
5885 :
5886 : /* Setup pointers to global sched info structures. */
5887 : void
5888 870 : sel_setup_sched_infos (void)
5889 : {
5890 870 : rgn_setup_common_sched_info ();
5891 :
5892 870 : memcpy (&sel_common_sched_info, common_sched_info,
5893 : sizeof (sel_common_sched_info));
5894 :
5895 870 : sel_common_sched_info.fix_recovery_cfg = NULL;
5896 870 : sel_common_sched_info.add_block = NULL;
5897 870 : sel_common_sched_info.estimate_number_of_insns
5898 870 : = sel_estimate_number_of_insns;
5899 870 : sel_common_sched_info.luid_for_non_insn = sel_luid_for_non_insn;
5900 870 : sel_common_sched_info.sched_pass_id = SCHED_SEL_PASS;
5901 :
5902 870 : common_sched_info = &sel_common_sched_info;
5903 :
5904 870 : current_sched_info = &sched_sel_haifa_sched_info;
5905 1740 : current_sched_info->sched_max_insns_priority =
5906 870 : get_rgn_sched_max_insns_priority ();
5907 :
5908 870 : sel_set_sched_flags ();
5909 870 : }
5910 :
5911 :
5912 : /* Adds basic block BB to region RGN at the position *BB_ORD_INDEX,
5913 : *BB_ORD_INDEX after that is increased. */
5914 : static void
5915 295 : sel_add_block_to_region (basic_block bb, int *bb_ord_index, int rgn)
5916 : {
5917 295 : RGN_NR_BLOCKS (rgn) += 1;
5918 295 : RGN_DONT_CALC_DEPS (rgn) = 0;
5919 295 : RGN_HAS_REAL_EBB (rgn) = 0;
5920 295 : CONTAINING_RGN (bb->index) = rgn;
5921 295 : BLOCK_TO_BB (bb->index) = *bb_ord_index;
5922 295 : rgn_bb_table[RGN_BLOCKS (rgn) + *bb_ord_index] = bb->index;
5923 295 : (*bb_ord_index)++;
5924 :
5925 : /* FIXME: it is true only when not scheduling ebbs. */
5926 295 : RGN_BLOCKS (rgn + 1) = RGN_BLOCKS (rgn) + RGN_NR_BLOCKS (rgn);
5927 295 : }
5928 :
5929 : /* Functions to support pipelining of outer loops. */
5930 :
5931 : /* Creates a new empty region and returns it's number. */
5932 : static int
5933 91 : sel_create_new_region (void)
5934 : {
5935 91 : int new_rgn_number = nr_regions;
5936 :
5937 91 : RGN_NR_BLOCKS (new_rgn_number) = 0;
5938 :
5939 : /* FIXME: This will work only when EBBs are not created. */
5940 91 : if (new_rgn_number != 0)
5941 53 : RGN_BLOCKS (new_rgn_number) = RGN_BLOCKS (new_rgn_number - 1) +
5942 53 : RGN_NR_BLOCKS (new_rgn_number - 1);
5943 : else
5944 : RGN_BLOCKS (new_rgn_number) = 0;
5945 :
5946 : /* Set the blocks of the next region so the other functions may
5947 : calculate the number of blocks in the region. */
5948 91 : RGN_BLOCKS (new_rgn_number + 1) = RGN_BLOCKS (new_rgn_number) +
5949 : RGN_NR_BLOCKS (new_rgn_number);
5950 :
5951 91 : nr_regions++;
5952 :
5953 91 : return new_rgn_number;
5954 : }
5955 :
5956 : /* If X has a smaller topological sort number than Y, returns -1;
5957 : if greater, returns 1. */
5958 : static int
5959 2001 : bb_top_order_comparator (const void *x, const void *y)
5960 : {
5961 2001 : basic_block bb1 = *(const basic_block *) x;
5962 2001 : basic_block bb2 = *(const basic_block *) y;
5963 :
5964 2001 : gcc_assert (bb1 == bb2
5965 : || rev_top_order_index[bb1->index]
5966 : != rev_top_order_index[bb2->index]);
5967 :
5968 : /* It's a reverse topological order in REV_TOP_ORDER_INDEX, so
5969 : bbs with greater number should go earlier. */
5970 2001 : if (rev_top_order_index[bb1->index] > rev_top_order_index[bb2->index])
5971 : return -1;
5972 : else
5973 858 : return 1;
5974 : }
5975 :
5976 : /* Create a region for LOOP and return its number. If we don't want
5977 : to pipeline LOOP, return -1. */
5978 : static int
5979 57 : make_region_from_loop (class loop *loop)
5980 : {
5981 57 : unsigned int i;
5982 57 : int new_rgn_number = -1;
5983 57 : class loop *inner;
5984 :
5985 : /* Basic block index, to be assigned to BLOCK_TO_BB. */
5986 57 : int bb_ord_index = 0;
5987 57 : basic_block *loop_blocks;
5988 57 : basic_block preheader_block;
5989 :
5990 57 : if (loop->num_nodes
5991 57 : > (unsigned) param_max_pipeline_region_blocks)
5992 : return -1;
5993 :
5994 : /* Don't pipeline loops whose latch belongs to some of its inner loops. */
5995 62 : for (inner = loop->inner; inner; inner = inner->inner)
5996 8 : if (flow_bb_inside_loop_p (inner, loop->latch))
5997 : return -1;
5998 :
5999 54 : loop->ninsns = num_loop_insns (loop);
6000 54 : if ((int) loop->ninsns > param_max_pipeline_region_insns)
6001 : return -1;
6002 :
6003 54 : loop_blocks = get_loop_body_in_custom_order (loop, bb_top_order_comparator);
6004 :
6005 337 : for (i = 0; i < loop->num_nodes; i++)
6006 229 : if (loop_blocks[i]->flags & BB_IRREDUCIBLE_LOOP)
6007 : {
6008 0 : free (loop_blocks);
6009 0 : return -1;
6010 : }
6011 :
6012 54 : preheader_block = loop_preheader_edge (loop)->src;
6013 54 : gcc_assert (preheader_block);
6014 54 : gcc_assert (loop_blocks[0] == loop->header);
6015 :
6016 54 : new_rgn_number = sel_create_new_region ();
6017 :
6018 54 : sel_add_block_to_region (preheader_block, &bb_ord_index, new_rgn_number);
6019 54 : bitmap_set_bit (bbs_in_loop_rgns, preheader_block->index);
6020 :
6021 337 : for (i = 0; i < loop->num_nodes; i++)
6022 : {
6023 : /* Add only those blocks that haven't been scheduled in the inner loop.
6024 : The exception is the basic blocks with bookkeeping code - they should
6025 : be added to the region (and they actually don't belong to the loop
6026 : body, but to the region containing that loop body). */
6027 :
6028 229 : gcc_assert (new_rgn_number >= 0);
6029 :
6030 229 : if (! bitmap_bit_p (bbs_in_loop_rgns, loop_blocks[i]->index))
6031 : {
6032 204 : sel_add_block_to_region (loop_blocks[i], &bb_ord_index,
6033 : new_rgn_number);
6034 204 : bitmap_set_bit (bbs_in_loop_rgns, loop_blocks[i]->index);
6035 : }
6036 : }
6037 :
6038 54 : free (loop_blocks);
6039 54 : MARK_LOOP_FOR_PIPELINING (loop);
6040 :
6041 54 : return new_rgn_number;
6042 : }
6043 :
6044 : /* Create a new region from preheader blocks LOOP_BLOCKS. */
6045 : void
6046 37 : make_region_from_loop_preheader (vec<basic_block> *&loop_blocks)
6047 : {
6048 37 : unsigned int i;
6049 37 : int new_rgn_number = -1;
6050 37 : basic_block bb;
6051 :
6052 : /* Basic block index, to be assigned to BLOCK_TO_BB. */
6053 37 : int bb_ord_index = 0;
6054 :
6055 37 : new_rgn_number = sel_create_new_region ();
6056 :
6057 111 : FOR_EACH_VEC_ELT (*loop_blocks, i, bb)
6058 : {
6059 37 : gcc_assert (new_rgn_number >= 0);
6060 :
6061 37 : sel_add_block_to_region (bb, &bb_ord_index, new_rgn_number);
6062 : }
6063 :
6064 37 : vec_free (loop_blocks);
6065 37 : }
6066 :
6067 :
6068 : /* Create region(s) from loop nest LOOP, such that inner loops will be
6069 : pipelined before outer loops. Returns true when a region for LOOP
6070 : is created. */
6071 : static bool
6072 57 : make_regions_from_loop_nest (class loop *loop)
6073 : {
6074 57 : class loop *cur_loop;
6075 57 : int rgn_number;
6076 :
6077 : /* Traverse all inner nodes of the loop. */
6078 65 : for (cur_loop = loop->inner; cur_loop; cur_loop = cur_loop->next)
6079 8 : if (! bitmap_bit_p (bbs_in_loop_rgns, cur_loop->header->index))
6080 : return false;
6081 :
6082 : /* At this moment all regular inner loops should have been pipelined.
6083 : Try to create a region from this loop. */
6084 57 : rgn_number = make_region_from_loop (loop);
6085 :
6086 57 : if (rgn_number < 0)
6087 : return false;
6088 :
6089 54 : loop_nests.safe_push (loop);
6090 54 : return true;
6091 : }
6092 :
6093 : /* Initialize data structures needed. */
6094 : void
6095 43 : sel_init_pipelining (void)
6096 : {
6097 : /* Collect loop information to be used in outer loops pipelining. */
6098 43 : loop_optimizer_init (LOOPS_HAVE_PREHEADERS
6099 : | LOOPS_HAVE_FALLTHRU_PREHEADERS
6100 : | LOOPS_HAVE_RECORDED_EXITS
6101 : | LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS);
6102 43 : current_loop_nest = NULL;
6103 :
6104 43 : bbs_in_loop_rgns = sbitmap_alloc (last_basic_block_for_fn (cfun));
6105 43 : bitmap_clear (bbs_in_loop_rgns);
6106 :
6107 43 : recompute_rev_top_order ();
6108 43 : }
6109 :
6110 : /* Returns a class loop for region RGN. */
6111 : loop_p
6112 369 : get_loop_nest_for_rgn (unsigned int rgn)
6113 : {
6114 : /* Regions created with extend_rgns don't have corresponding loop nests,
6115 : because they don't represent loops. */
6116 369 : if (rgn < loop_nests.length ())
6117 54 : return loop_nests[rgn];
6118 : else
6119 : return NULL;
6120 : }
6121 :
6122 : /* True when LOOP was included into pipelining regions. */
6123 : bool
6124 938 : considered_for_pipelining_p (class loop *loop)
6125 : {
6126 938 : if (loop_depth (loop) == 0)
6127 : return false;
6128 :
6129 : /* Now, the loop could be too large or irreducible. Check whether its
6130 : region is in LOOP_NESTS.
6131 : We determine the region number of LOOP as the region number of its
6132 : latch. We can't use header here, because this header could be
6133 : just removed preheader and it will give us the wrong region number.
6134 : Latch can't be used because it could be in the inner loop too. */
6135 213 : if (LOOP_MARKED_FOR_PIPELINING_P (loop))
6136 : {
6137 159 : int rgn = CONTAINING_RGN (loop->latch->index);
6138 :
6139 159 : gcc_assert ((unsigned) rgn < loop_nests.length ());
6140 : return true;
6141 : }
6142 :
6143 : return false;
6144 : }
6145 :
6146 : /* Makes regions from the rest of the blocks, after loops are chosen
6147 : for pipelining. */
6148 : static void
6149 43 : make_regions_from_the_rest (void)
6150 : {
6151 43 : int cur_rgn_blocks;
6152 43 : int *loop_hdr;
6153 43 : int i;
6154 :
6155 43 : basic_block bb;
6156 43 : edge e;
6157 43 : edge_iterator ei;
6158 43 : int *degree;
6159 :
6160 : /* Index in rgn_bb_table where to start allocating new regions. */
6161 43 : cur_rgn_blocks = nr_regions ? RGN_BLOCKS (nr_regions) : 0;
6162 :
6163 : /* Make regions from all the rest basic blocks - those that don't belong to
6164 : any loop or belong to irreducible loops. Prepare the data structures
6165 : for extend_rgns. */
6166 :
6167 : /* LOOP_HDR[I] == -1 if I-th bb doesn't belong to any loop,
6168 : LOOP_HDR[I] == LOOP_HDR[J] iff basic blocks I and J reside within the same
6169 : loop. */
6170 43 : loop_hdr = XNEWVEC (int, last_basic_block_for_fn (cfun));
6171 43 : degree = XCNEWVEC (int, last_basic_block_for_fn (cfun));
6172 :
6173 :
6174 : /* For each basic block that belongs to some loop assign the number
6175 : of innermost loop it belongs to. */
6176 695 : for (i = 0; i < last_basic_block_for_fn (cfun); i++)
6177 609 : loop_hdr[i] = -1;
6178 :
6179 565 : FOR_EACH_BB_FN (bb, cfun)
6180 : {
6181 522 : if (bb->loop_father && bb->loop_father->num != 0
6182 298 : && !(bb->flags & BB_IRREDUCIBLE_LOOP))
6183 298 : loop_hdr[bb->index] = bb->loop_father->num;
6184 : }
6185 :
6186 : /* For each basic block degree is calculated as the number of incoming
6187 : edges, that are going out of bbs that are not yet scheduled.
6188 : The basic blocks that are scheduled have degree value of zero. */
6189 565 : FOR_EACH_BB_FN (bb, cfun)
6190 : {
6191 522 : degree[bb->index] = 0;
6192 :
6193 522 : if (!bitmap_bit_p (bbs_in_loop_rgns, bb->index))
6194 : {
6195 650 : FOR_EACH_EDGE (e, ei, bb->preds)
6196 386 : if (!bitmap_bit_p (bbs_in_loop_rgns, e->src->index))
6197 299 : degree[bb->index]++;
6198 : }
6199 : else
6200 258 : degree[bb->index] = -1;
6201 : }
6202 :
6203 43 : extend_rgns (degree, &cur_rgn_blocks, bbs_in_loop_rgns, loop_hdr);
6204 :
6205 : /* Any block that did not end up in a region is placed into a region
6206 : by itself. */
6207 565 : FOR_EACH_BB_FN (bb, cfun)
6208 522 : if (degree[bb->index] >= 0)
6209 : {
6210 264 : rgn_bb_table[cur_rgn_blocks] = bb->index;
6211 264 : RGN_NR_BLOCKS (nr_regions) = 1;
6212 264 : RGN_BLOCKS (nr_regions) = cur_rgn_blocks++;
6213 264 : RGN_DONT_CALC_DEPS (nr_regions) = 0;
6214 264 : RGN_HAS_REAL_EBB (nr_regions) = 0;
6215 264 : CONTAINING_RGN (bb->index) = nr_regions++;
6216 264 : BLOCK_TO_BB (bb->index) = 0;
6217 : }
6218 :
6219 43 : free (degree);
6220 43 : free (loop_hdr);
6221 43 : }
6222 :
6223 : /* Free data structures used in pipelining of loops. */
6224 43 : void sel_finish_pipelining (void)
6225 : {
6226 : /* Release aux fields so we don't free them later by mistake. */
6227 193 : for (auto loop : loops_list (cfun, 0))
6228 64 : loop->aux = NULL;
6229 :
6230 43 : loop_optimizer_finalize ();
6231 :
6232 43 : loop_nests.release ();
6233 :
6234 43 : free (rev_top_order_index);
6235 43 : rev_top_order_index = NULL;
6236 43 : }
6237 :
6238 : /* This function replaces the find_rgns when
6239 : FLAG_SEL_SCHED_PIPELINING_OUTER_LOOPS is set. */
6240 : void
6241 43 : sel_find_rgns (void)
6242 : {
6243 43 : sel_init_pipelining ();
6244 43 : extend_regions ();
6245 :
6246 43 : if (current_loops)
6247 : {
6248 36 : unsigned flags = flag_sel_sched_pipelining_outer_loops
6249 43 : ? LI_FROM_INNERMOST
6250 : : LI_ONLY_INNERMOST;
6251 :
6252 186 : for (auto loop : loops_list (cfun, flags))
6253 100 : make_regions_from_loop_nest (loop);
6254 : }
6255 :
6256 : /* Make regions from all the rest basic blocks and schedule them.
6257 : These blocks include blocks that don't belong to any loop or belong
6258 : to irreducible loops. */
6259 43 : make_regions_from_the_rest ();
6260 :
6261 : /* We don't need bbs_in_loop_rgns anymore. */
6262 43 : sbitmap_free (bbs_in_loop_rgns);
6263 43 : bbs_in_loop_rgns = NULL;
6264 43 : }
6265 :
6266 : /* Add the preheader blocks from previous loop to current region taking
6267 : it from LOOP_PREHEADER_BLOCKS (current_loop_nest) and record them in *BBS.
6268 : This function is only used with -fsel-sched-pipelining-outer-loops. */
6269 : void
6270 54 : sel_add_loop_preheaders (bb_vec_t *bbs)
6271 : {
6272 54 : int i;
6273 54 : basic_block bb;
6274 108 : vec<basic_block> *preheader_blocks
6275 54 : = LOOP_PREHEADER_BLOCKS (current_loop_nest);
6276 :
6277 54 : if (!preheader_blocks)
6278 47 : return;
6279 :
6280 21 : for (i = 0; preheader_blocks->iterate (i, &bb); i++)
6281 : {
6282 7 : bbs->safe_push (bb);
6283 7 : last_added_blocks.safe_push (bb);
6284 7 : sel_add_bb (bb);
6285 : }
6286 :
6287 7 : vec_free (preheader_blocks);
6288 : }
6289 :
6290 : /* While pipelining outer loops, returns TRUE if BB is a loop preheader.
6291 : Please note that the function should also work when pipelining_p is
6292 : false, because it is used when deciding whether we should or should
6293 : not reschedule pipelined code. */
6294 : bool
6295 1288 : sel_is_loop_preheader_p (basic_block bb)
6296 : {
6297 1288 : if (current_loop_nest)
6298 : {
6299 806 : class loop *outer;
6300 :
6301 806 : if (preheader_removed)
6302 : return false;
6303 :
6304 : /* Preheader is the first block in the region. */
6305 806 : if (BLOCK_TO_BB (bb->index) == 0)
6306 : return true;
6307 :
6308 : /* We used to find a preheader with the topological information.
6309 : Check that the above code is equivalent to what we did before. */
6310 :
6311 577 : if (in_current_region_p (current_loop_nest->header))
6312 577 : gcc_assert (!(BLOCK_TO_BB (bb->index)
6313 : < BLOCK_TO_BB (current_loop_nest->header->index)));
6314 :
6315 : /* Support the situation when the latch block of outer loop
6316 : could be from here. */
6317 577 : for (outer = loop_outer (current_loop_nest);
6318 1247 : outer;
6319 670 : outer = loop_outer (outer))
6320 670 : if (considered_for_pipelining_p (outer) && outer->latch == bb)
6321 0 : gcc_unreachable ();
6322 : }
6323 :
6324 : return false;
6325 : }
6326 :
6327 : /* Check whether JUMP_BB ends with a jump insn that leads only to DEST_BB and
6328 : can be removed, making the corresponding edge fallthrough (assuming that
6329 : all basic blocks between JUMP_BB and DEST_BB are empty). */
6330 : static bool
6331 2823 : bb_has_removable_jump_to_p (basic_block jump_bb, basic_block dest_bb)
6332 : {
6333 2823 : if (!onlyjump_p (BB_END (jump_bb))
6334 2823 : || tablejump_p (BB_END (jump_bb), NULL, NULL))
6335 : return false;
6336 :
6337 : /* Several outgoing edges, abnormal edge or destination of jump is
6338 : not DEST_BB. */
6339 1958 : if (EDGE_COUNT (jump_bb->succs) != 1
6340 433 : || EDGE_SUCC (jump_bb, 0)->flags & (EDGE_ABNORMAL | EDGE_CROSSING)
6341 2385 : || EDGE_SUCC (jump_bb, 0)->dest != dest_bb)
6342 1940 : return false;
6343 :
6344 : /* If not anything of the upper. */
6345 : return true;
6346 : }
6347 :
6348 : /* Removes the loop preheader from the current region and saves it in
6349 : PREHEADER_BLOCKS of the father loop, so they will be added later to
6350 : region that represents an outer loop. */
6351 : static void
6352 54 : sel_remove_loop_preheader (void)
6353 : {
6354 54 : int i, old_len;
6355 54 : int cur_rgn = CONTAINING_RGN (BB_TO_BLOCK (0));
6356 54 : basic_block bb;
6357 54 : bool all_empty_p = true;
6358 54 : vec<basic_block> *preheader_blocks
6359 54 : = LOOP_PREHEADER_BLOCKS (loop_outer (current_loop_nest));
6360 :
6361 54 : vec_check_alloc (preheader_blocks, 0);
6362 :
6363 54 : gcc_assert (current_loop_nest);
6364 54 : old_len = preheader_blocks->length ();
6365 :
6366 : /* Add blocks that aren't within the current loop to PREHEADER_BLOCKS. */
6367 323 : for (i = 0; i < RGN_NR_BLOCKS (cur_rgn); i++)
6368 : {
6369 269 : bb = BASIC_BLOCK_FOR_FN (cfun, BB_TO_BLOCK (i));
6370 :
6371 : /* If the basic block belongs to region, but doesn't belong to
6372 : corresponding loop, then it should be a preheader. */
6373 269 : if (sel_is_loop_preheader_p (bb))
6374 : {
6375 54 : preheader_blocks->safe_push (bb);
6376 54 : if (BB_END (bb) != bb_note (bb))
6377 269 : all_empty_p = false;
6378 : }
6379 : }
6380 :
6381 : /* Remove these blocks only after iterating over the whole region. */
6382 162 : for (i = preheader_blocks->length () - 1; i >= old_len; i--)
6383 : {
6384 54 : bb = (*preheader_blocks)[i];
6385 54 : sel_remove_bb (bb, false);
6386 : }
6387 :
6388 54 : if (!considered_for_pipelining_p (loop_outer (current_loop_nest)))
6389 : {
6390 47 : if (!all_empty_p)
6391 : /* Immediately create new region from preheader. */
6392 37 : make_region_from_loop_preheader (preheader_blocks);
6393 : else
6394 : {
6395 : /* If all preheader blocks are empty - dont create new empty region.
6396 : Instead, remove them completely. */
6397 67 : FOR_EACH_VEC_ELT (*preheader_blocks, i, bb)
6398 : {
6399 10 : edge e;
6400 10 : edge_iterator ei;
6401 10 : basic_block prev_bb = bb->prev_bb, next_bb = bb->next_bb;
6402 :
6403 : /* Redirect all incoming edges to next basic block. */
6404 21 : for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
6405 : {
6406 11 : if (! (e->flags & EDGE_FALLTHRU))
6407 8 : redirect_edge_and_branch (e, bb->next_bb);
6408 : else
6409 3 : redirect_edge_succ (e, bb->next_bb);
6410 : }
6411 10 : gcc_assert (BB_NOTE_LIST (bb) == NULL);
6412 10 : delete_and_free_basic_block (bb);
6413 :
6414 : /* Check if after deleting preheader there is a nonconditional
6415 : jump in PREV_BB that leads to the next basic block NEXT_BB.
6416 : If it is so - delete this jump and clear data sets of its
6417 : basic block if it becomes empty. */
6418 10 : if (next_bb->prev_bb == prev_bb
6419 10 : && prev_bb != ENTRY_BLOCK_PTR_FOR_FN (cfun)
6420 20 : && bb_has_removable_jump_to_p (prev_bb, next_bb))
6421 : {
6422 6 : redirect_edge_and_branch (EDGE_SUCC (prev_bb, 0), next_bb);
6423 6 : if (BB_END (prev_bb) == bb_note (prev_bb))
6424 0 : free_data_sets (prev_bb);
6425 : }
6426 :
6427 10 : set_immediate_dominator (CDI_DOMINATORS, next_bb,
6428 : recompute_dominator (CDI_DOMINATORS,
6429 : next_bb));
6430 : }
6431 : }
6432 47 : vec_free (preheader_blocks);
6433 : }
6434 : else
6435 : /* Store preheader within the father's loop structure. */
6436 7 : SET_LOOP_PREHEADER_BLOCKS (loop_outer (current_loop_nest),
6437 : preheader_blocks);
6438 54 : }
6439 :
6440 : #endif
|
