Line data Source code
1 : /* Instruction scheduling pass. This file computes dependencies between
2 : instructions.
3 : Copyright (C) 1992-2026 Free Software Foundation, Inc.
4 : Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,
5 : and currently maintained by, Jim Wilson (wilson@cygnus.com)
6 :
7 : This file is part of GCC.
8 :
9 : GCC is free software; you can redistribute it and/or modify it under
10 : the terms of the GNU General Public License as published by the Free
11 : Software Foundation; either version 3, or (at your option) any later
12 : version.
13 :
14 : GCC is distributed in the hope that it will be useful, but WITHOUT ANY
15 : WARRANTY; without even the implied warranty of MERCHANTABILITY or
16 : FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 : for more details.
18 :
19 : You should have received a copy of the GNU General Public License
20 : along with GCC; see the file COPYING3. If not see
21 : <http://www.gnu.org/licenses/>. */
22 :
23 : #include "config.h"
24 : #include "system.h"
25 : #include "coretypes.h"
26 : #include "backend.h"
27 : #include "target.h"
28 : #include "rtl.h"
29 : #include "tree.h"
30 : #include "df.h"
31 : #include "insn-config.h"
32 : #include "regs.h"
33 : #include "memmodel.h"
34 : #include "ira.h"
35 : #include "ira-int.h"
36 : #include "insn-attr.h"
37 : #include "cfgbuild.h"
38 : #include "sched-int.h"
39 : #include "cselib.h"
40 : #include "function-abi.h"
41 : #include "selftest.h"
42 : #include "selftest-rtl.h"
43 :
44 : #ifdef INSN_SCHEDULING
45 :
46 : /* Holds current parameters for the dependency analyzer. */
47 : struct sched_deps_info_def *sched_deps_info;
48 :
49 : /* The data is specific to the Haifa scheduler. */
50 : vec<haifa_deps_insn_data_def>
51 : h_d_i_d = vNULL;
52 :
53 : /* Return the major type present in the DS. */
54 : enum reg_note
55 0 : ds_to_dk (ds_t ds)
56 : {
57 0 : if (ds & DEP_TRUE)
58 : return REG_DEP_TRUE;
59 :
60 0 : if (ds & DEP_OUTPUT)
61 : return REG_DEP_OUTPUT;
62 :
63 0 : if (ds & DEP_CONTROL)
64 : return REG_DEP_CONTROL;
65 :
66 0 : gcc_assert (ds & DEP_ANTI);
67 :
68 : return REG_DEP_ANTI;
69 : }
70 :
71 : /* Return equivalent dep_status. */
72 : ds_t
73 0 : dk_to_ds (enum reg_note dk)
74 : {
75 0 : switch (dk)
76 : {
77 : case REG_DEP_TRUE:
78 : return DEP_TRUE;
79 :
80 0 : case REG_DEP_OUTPUT:
81 0 : return DEP_OUTPUT;
82 :
83 0 : case REG_DEP_CONTROL:
84 0 : return DEP_CONTROL;
85 :
86 0 : default:
87 0 : gcc_assert (dk == REG_DEP_ANTI);
88 : return DEP_ANTI;
89 : }
90 : }
91 :
92 : /* Functions to operate with dependence information container - dep_t. */
93 :
94 : /* Init DEP with the arguments. */
95 : void
96 656444251 : init_dep_1 (dep_t dep, rtx_insn *pro, rtx_insn *con, enum reg_note type, ds_t ds)
97 : {
98 656444251 : DEP_PRO (dep) = pro;
99 656444251 : DEP_CON (dep) = con;
100 656444251 : DEP_TYPE (dep) = type;
101 656444251 : DEP_STATUS (dep) = ds;
102 656444251 : DEP_COST (dep) = UNKNOWN_DEP_COST;
103 656444251 : DEP_NONREG (dep) = 0;
104 656444251 : DEP_MULTIPLE (dep) = 0;
105 656444251 : DEP_REPLACE (dep) = NULL;
106 656444251 : dep->unused = 0;
107 656444251 : }
108 :
109 : /* Init DEP with the arguments.
110 : While most of the scheduler (including targets) only need the major type
111 : of the dependency, it is convenient to hide full dep_status from them. */
112 : void
113 624010877 : init_dep (dep_t dep, rtx_insn *pro, rtx_insn *con, enum reg_note kind)
114 : {
115 624010877 : ds_t ds;
116 :
117 624010877 : if ((current_sched_info->flags & USE_DEPS_LIST))
118 0 : ds = dk_to_ds (kind);
119 : else
120 : ds = 0;
121 :
122 624010877 : init_dep_1 (dep, pro, con, kind, ds);
123 624010877 : }
124 :
125 : /* Make a copy of FROM in TO. */
126 : static void
127 224585809 : copy_dep (dep_t to, dep_t from)
128 : {
129 224585809 : memcpy (to, from, sizeof (*to));
130 0 : }
131 :
132 : static void dump_ds (FILE *, ds_t);
133 :
134 : /* Define flags for dump_dep (). */
135 :
136 : /* Dump producer of the dependence. */
137 : #define DUMP_DEP_PRO (2)
138 :
139 : /* Dump consumer of the dependence. */
140 : #define DUMP_DEP_CON (4)
141 :
142 : /* Dump type of the dependence. */
143 : #define DUMP_DEP_TYPE (8)
144 :
145 : /* Dump status of the dependence. */
146 : #define DUMP_DEP_STATUS (16)
147 :
148 : /* Dump all information about the dependence. */
149 : #define DUMP_DEP_ALL (DUMP_DEP_PRO | DUMP_DEP_CON | DUMP_DEP_TYPE \
150 : |DUMP_DEP_STATUS)
151 :
152 : /* Dump DEP to DUMP.
153 : FLAGS is a bit mask specifying what information about DEP needs
154 : to be printed.
155 : If FLAGS has the very first bit set, then dump all information about DEP
156 : and propagate this bit into the callee dump functions. */
157 : static void
158 0 : dump_dep (FILE *dump, dep_t dep, int flags)
159 : {
160 0 : if (flags & 1)
161 0 : flags |= DUMP_DEP_ALL;
162 :
163 0 : fprintf (dump, "<");
164 :
165 0 : if (flags & DUMP_DEP_PRO)
166 0 : fprintf (dump, "%d; ", INSN_UID (DEP_PRO (dep)));
167 :
168 0 : if (flags & DUMP_DEP_CON)
169 0 : fprintf (dump, "%d; ", INSN_UID (DEP_CON (dep)));
170 :
171 0 : if (flags & DUMP_DEP_TYPE)
172 : {
173 0 : char t;
174 0 : enum reg_note type = DEP_TYPE (dep);
175 :
176 0 : switch (type)
177 : {
178 : case REG_DEP_TRUE:
179 : t = 't';
180 : break;
181 :
182 0 : case REG_DEP_OUTPUT:
183 0 : t = 'o';
184 0 : break;
185 :
186 0 : case REG_DEP_CONTROL:
187 0 : t = 'c';
188 0 : break;
189 :
190 0 : case REG_DEP_ANTI:
191 0 : t = 'a';
192 0 : break;
193 :
194 0 : default:
195 0 : gcc_unreachable ();
196 0 : break;
197 : }
198 :
199 0 : fprintf (dump, "%c; ", t);
200 : }
201 :
202 0 : if (flags & DUMP_DEP_STATUS)
203 : {
204 0 : if (current_sched_info->flags & USE_DEPS_LIST)
205 0 : dump_ds (dump, DEP_STATUS (dep));
206 : }
207 :
208 0 : fprintf (dump, ">");
209 0 : }
210 :
211 : /* Default flags for dump_dep (). */
212 : static int dump_dep_flags = (DUMP_DEP_PRO | DUMP_DEP_CON);
213 :
214 : /* Dump all fields of DEP to STDERR. */
215 : void
216 0 : sd_debug_dep (dep_t dep)
217 : {
218 0 : dump_dep (stderr, dep, 1);
219 0 : fprintf (stderr, "\n");
220 0 : }
221 :
222 : /* Determine whether DEP is a dependency link of a non-debug insn on a
223 : debug insn. */
224 :
225 : static inline bool
226 1767273198 : depl_on_debug_p (dep_link_t dep)
227 : {
228 1767273198 : return (DEBUG_INSN_P (DEP_LINK_PRO (dep))
229 436086708 : && !DEBUG_INSN_P (DEP_LINK_CON (dep)));
230 : }
231 :
232 : /* Functions to operate with a single link from the dependencies lists -
233 : dep_link_t. */
234 :
235 : /* Attach L to appear after link X whose &DEP_LINK_NEXT (X) is given by
236 : PREV_NEXT_P. */
237 : static void
238 883636599 : attach_dep_link (dep_link_t l, dep_link_t *prev_nextp)
239 : {
240 883636599 : dep_link_t next = *prev_nextp;
241 :
242 883636599 : gcc_assert (DEP_LINK_PREV_NEXTP (l) == NULL
243 : && DEP_LINK_NEXT (l) == NULL);
244 :
245 : /* Init node being inserted. */
246 883636599 : DEP_LINK_PREV_NEXTP (l) = prev_nextp;
247 883636599 : DEP_LINK_NEXT (l) = next;
248 :
249 : /* Fix next node. */
250 883636599 : if (next != NULL)
251 : {
252 488393694 : gcc_assert (DEP_LINK_PREV_NEXTP (next) == prev_nextp);
253 :
254 488393694 : DEP_LINK_PREV_NEXTP (next) = &DEP_LINK_NEXT (l);
255 : }
256 :
257 : /* Fix prev node. */
258 883636599 : *prev_nextp = l;
259 883636599 : }
260 :
261 : /* Add dep_link LINK to deps_list L. */
262 : static void
263 883636599 : add_to_deps_list (dep_link_t link, deps_list_t l)
264 : {
265 883636599 : attach_dep_link (link, &DEPS_LIST_FIRST (l));
266 :
267 : /* Don't count debug deps. */
268 883636599 : if (!depl_on_debug_p (link))
269 863168433 : ++DEPS_LIST_N_LINKS (l);
270 883636599 : }
271 :
272 : /* Detach dep_link L from the list. */
273 : static void
274 883636599 : detach_dep_link (dep_link_t l)
275 : {
276 883636599 : dep_link_t *prev_nextp = DEP_LINK_PREV_NEXTP (l);
277 883636599 : dep_link_t next = DEP_LINK_NEXT (l);
278 :
279 883636599 : *prev_nextp = next;
280 :
281 0 : if (next != NULL)
282 464150994 : DEP_LINK_PREV_NEXTP (next) = prev_nextp;
283 :
284 883636599 : DEP_LINK_PREV_NEXTP (l) = NULL;
285 883636599 : DEP_LINK_NEXT (l) = NULL;
286 0 : }
287 :
288 : /* Remove link LINK from list LIST. */
289 : static void
290 883636599 : remove_from_deps_list (dep_link_t link, deps_list_t list)
291 : {
292 883636599 : detach_dep_link (link);
293 :
294 : /* Don't count debug deps. */
295 883636599 : if (!depl_on_debug_p (link))
296 863168433 : --DEPS_LIST_N_LINKS (list);
297 883636599 : }
298 :
299 : /* Move link LINK from list FROM to list TO. */
300 : static void
301 434464981 : move_dep_link (dep_link_t link, deps_list_t from, deps_list_t to)
302 : {
303 0 : remove_from_deps_list (link, from);
304 217799111 : add_to_deps_list (link, to);
305 0 : }
306 :
307 : /* Return true of LINK is not attached to any list. */
308 : static bool
309 449171618 : dep_link_is_detached_p (dep_link_t link)
310 : {
311 449171618 : return DEP_LINK_PREV_NEXTP (link) == NULL;
312 : }
313 :
314 : /* Pool to hold all dependency nodes (dep_node_t). */
315 : static object_allocator<_dep_node> *dn_pool;
316 :
317 : /* Number of dep_nodes out there. */
318 : static int dn_pool_diff = 0;
319 :
320 : /* Create a dep_node. */
321 : static dep_node_t
322 224585809 : create_dep_node (void)
323 : {
324 224585809 : dep_node_t n = dn_pool->allocate ();
325 224585809 : dep_link_t back = DEP_NODE_BACK (n);
326 224585809 : dep_link_t forw = DEP_NODE_FORW (n);
327 :
328 224585809 : DEP_LINK_NODE (back) = n;
329 224585809 : DEP_LINK_NEXT (back) = NULL;
330 224585809 : DEP_LINK_PREV_NEXTP (back) = NULL;
331 :
332 224585809 : DEP_LINK_NODE (forw) = n;
333 224585809 : DEP_LINK_NEXT (forw) = NULL;
334 224585809 : DEP_LINK_PREV_NEXTP (forw) = NULL;
335 :
336 224585809 : ++dn_pool_diff;
337 :
338 224585809 : return n;
339 : }
340 :
341 : /* Delete dep_node N. N must not be connected to any deps_list. */
342 : static void
343 224585809 : delete_dep_node (dep_node_t n)
344 : {
345 224585809 : gcc_assert (dep_link_is_detached_p (DEP_NODE_BACK (n))
346 : && dep_link_is_detached_p (DEP_NODE_FORW (n)));
347 :
348 224585809 : XDELETE (DEP_REPLACE (DEP_NODE_DEP (n)));
349 :
350 224585809 : --dn_pool_diff;
351 :
352 224585809 : dn_pool->remove (n);
353 224585809 : }
354 :
355 : /* Pool to hold dependencies lists (deps_list_t). */
356 : static object_allocator<_deps_list> *dl_pool;
357 :
358 : /* Number of deps_lists out there. */
359 : static int dl_pool_diff = 0;
360 :
361 : /* Functions to operate with dependences lists - deps_list_t. */
362 :
363 : /* Return true if list L is empty. */
364 : static bool
365 1399470087 : deps_list_empty_p (deps_list_t l)
366 : {
367 1399470087 : return DEPS_LIST_N_LINKS (l) == 0;
368 : }
369 :
370 : /* Create a new deps_list. */
371 : static deps_list_t
372 572308115 : create_deps_list (void)
373 : {
374 572308115 : deps_list_t l = dl_pool->allocate ();
375 :
376 572308115 : DEPS_LIST_FIRST (l) = NULL;
377 572308115 : DEPS_LIST_N_LINKS (l) = 0;
378 :
379 572308115 : ++dl_pool_diff;
380 572308115 : return l;
381 : }
382 :
383 : /* Free deps_list L. */
384 : static void
385 572308115 : free_deps_list (deps_list_t l)
386 : {
387 572308115 : gcc_assert (deps_list_empty_p (l));
388 :
389 572308115 : --dl_pool_diff;
390 :
391 572308115 : dl_pool->remove (l);
392 572308115 : }
393 :
394 : /* Return true if there is no dep_nodes and deps_lists out there.
395 : After the region is scheduled all the dependency nodes and lists
396 : should [generally] be returned to pool. */
397 : bool
398 11504993 : deps_pools_are_empty_p (void)
399 : {
400 11504993 : return dn_pool_diff == 0 && dl_pool_diff == 0;
401 : }
402 :
403 : /* Remove all elements from L. */
404 : static void
405 114461623 : clear_deps_list (deps_list_t l)
406 : {
407 547812253 : do
408 : {
409 331136938 : dep_link_t link = DEPS_LIST_FIRST (l);
410 :
411 331136938 : if (link == NULL)
412 : break;
413 :
414 216675315 : remove_from_deps_list (link, l);
415 216675315 : }
416 : while (1);
417 114461623 : }
418 :
419 : /* Decide whether a dependency should be treated as a hard or a speculative
420 : dependency. */
421 : static bool
422 782781342 : dep_spec_p (dep_t dep)
423 : {
424 782781342 : if (current_sched_info->flags & DO_SPECULATION)
425 : {
426 0 : if (DEP_STATUS (dep) & SPECULATIVE)
427 : return true;
428 : }
429 782781342 : if (current_sched_info->flags & DO_PREDICATION)
430 : {
431 0 : if (DEP_TYPE (dep) == REG_DEP_CONTROL)
432 : return true;
433 : }
434 782781342 : if (DEP_REPLACE (dep) != NULL)
435 1133241 : return true;
436 : return false;
437 : }
438 :
439 : static regset reg_pending_sets;
440 : static regset reg_pending_clobbers;
441 : static regset reg_pending_uses;
442 : static regset reg_pending_control_uses;
443 : static enum reg_pending_barrier_mode reg_pending_barrier;
444 :
445 : /* Hard registers implicitly clobbered or used (or may be implicitly
446 : clobbered or used) by the currently analyzed insn. For example,
447 : insn in its constraint has one register class. Even if there is
448 : currently no hard register in the insn, the particular hard
449 : register will be in the insn after reload pass because the
450 : constraint requires it. */
451 : static HARD_REG_SET implicit_reg_pending_clobbers;
452 : static HARD_REG_SET implicit_reg_pending_uses;
453 :
454 : /* To speed up the test for duplicate dependency links we keep a
455 : record of dependencies created by add_dependence when the average
456 : number of instructions in a basic block is very large.
457 :
458 : Studies have shown that there is typically around 5 instructions between
459 : branches for typical C code. So we can make a guess that the average
460 : basic block is approximately 5 instructions long; we will choose 100X
461 : the average size as a very large basic block.
462 :
463 : Each insn has associated bitmaps for its dependencies. Each bitmap
464 : has enough entries to represent a dependency on any other insn in
465 : the insn chain. All bitmap for true dependencies cache is
466 : allocated then the rest two ones are also allocated. */
467 : static bitmap true_dependency_cache = NULL;
468 : static bitmap output_dependency_cache = NULL;
469 : static bitmap anti_dependency_cache = NULL;
470 : static bitmap control_dependency_cache = NULL;
471 : static bitmap spec_dependency_cache = NULL;
472 : static int cache_size;
473 :
474 : /* True if we should mark added dependencies as a non-register deps. */
475 : static bool mark_as_hard;
476 :
477 : static bool deps_may_trap_p (const_rtx);
478 : static void add_dependence_1 (rtx_insn *, rtx_insn *, enum reg_note);
479 : static void add_dependence_list (rtx_insn *, rtx_insn_list *, int,
480 : enum reg_note, bool);
481 : static void add_dependence_list_and_free (class deps_desc *, rtx_insn *,
482 : rtx_insn_list **, int, enum reg_note,
483 : bool);
484 : static void delete_all_dependences (rtx_insn *);
485 : static void chain_to_prev_insn (rtx_insn *);
486 :
487 : static void flush_pending_lists (class deps_desc *, rtx_insn *, int, int);
488 : static void sched_analyze_1 (class deps_desc *, rtx, rtx_insn *);
489 : static void sched_analyze_2 (class deps_desc *, rtx, rtx_insn *);
490 : static void sched_analyze_insn (class deps_desc *, rtx, rtx_insn *);
491 :
492 : static bool sched_has_condition_p (const rtx_insn *);
493 : static bool conditions_mutex_p (const_rtx, const_rtx, bool, bool);
494 :
495 : static enum DEPS_ADJUST_RESULT maybe_add_or_update_dep_1 (dep_t, bool,
496 : rtx, rtx);
497 : static enum DEPS_ADJUST_RESULT add_or_update_dep_1 (dep_t, bool, rtx, rtx);
498 :
499 : static void check_dep (dep_t, bool);
500 :
501 :
502 : /* Return true if a load of the memory reference MEM can cause a trap. */
503 :
504 : static bool
505 15383 : deps_may_trap_p (const_rtx mem)
506 : {
507 15383 : const_rtx addr = XEXP (mem, 0);
508 :
509 15383 : if (REG_P (addr) && REGNO (addr) >= FIRST_PSEUDO_REGISTER)
510 : {
511 6 : const_rtx t = get_reg_known_value (REGNO (addr));
512 6 : if (t)
513 15383 : addr = t;
514 : }
515 15383 : return rtx_addr_can_trap_p (addr);
516 : }
517 :
518 :
519 : /* Find the condition under which INSN is executed. If REV is not NULL,
520 : it is set to TRUE when the returned comparison should be reversed
521 : to get the actual condition. */
522 : static rtx
523 63869043 : sched_get_condition_with_rev_uncached (const rtx_insn *insn, bool *rev)
524 : {
525 63869043 : rtx pat = PATTERN (insn);
526 63869043 : rtx src;
527 :
528 63869043 : if (rev)
529 63866517 : *rev = false;
530 :
531 63869043 : if (GET_CODE (pat) == COND_EXEC)
532 0 : return COND_EXEC_TEST (pat);
533 :
534 63869043 : if (!any_condjump_p (insn) || !onlyjump_p (insn))
535 : return 0;
536 :
537 4902677 : src = SET_SRC (pc_set (insn));
538 :
539 4902677 : if (XEXP (src, 2) == pc_rtx)
540 4902677 : return XEXP (src, 0);
541 0 : else if (XEXP (src, 1) == pc_rtx)
542 : {
543 0 : rtx cond = XEXP (src, 0);
544 0 : enum rtx_code revcode = reversed_comparison_code (cond, insn);
545 :
546 0 : if (revcode == UNKNOWN)
547 : return 0;
548 :
549 0 : if (rev)
550 0 : *rev = true;
551 : return cond;
552 : }
553 :
554 : return 0;
555 : }
556 :
557 : /* Return the condition under which INSN does not execute (i.e. the
558 : not-taken condition for a conditional branch), or NULL if we cannot
559 : find such a condition. The caller should make a copy of the condition
560 : before using it. */
561 : rtx
562 0 : sched_get_reverse_condition_uncached (const rtx_insn *insn)
563 : {
564 0 : bool rev;
565 0 : rtx cond = sched_get_condition_with_rev_uncached (insn, &rev);
566 0 : if (cond == NULL_RTX)
567 : return cond;
568 0 : if (!rev)
569 : {
570 0 : enum rtx_code revcode = reversed_comparison_code (cond, insn);
571 0 : cond = gen_rtx_fmt_ee (revcode, GET_MODE (cond),
572 : XEXP (cond, 0),
573 : XEXP (cond, 1));
574 : }
575 : return cond;
576 : }
577 :
578 : /* Caching variant of sched_get_condition_with_rev_uncached.
579 : We only do actual work the first time we come here for an insn; the
580 : results are cached in INSN_CACHED_COND and INSN_REVERSE_COND. */
581 : static rtx
582 578851687 : sched_get_condition_with_rev (const rtx_insn *insn, bool *rev)
583 : {
584 578851687 : bool tmp;
585 :
586 578851687 : if (INSN_LUID (insn) == 0)
587 6218 : return sched_get_condition_with_rev_uncached (insn, rev);
588 :
589 578845469 : if (INSN_CACHED_COND (insn) == const_true_rtx)
590 : return NULL_RTX;
591 :
592 84296360 : if (INSN_CACHED_COND (insn) != NULL_RTX)
593 : {
594 20433535 : if (rev)
595 15527826 : *rev = INSN_REVERSE_COND (insn);
596 20433535 : return INSN_CACHED_COND (insn);
597 : }
598 :
599 63862825 : INSN_CACHED_COND (insn) = sched_get_condition_with_rev_uncached (insn, &tmp);
600 63862825 : INSN_REVERSE_COND (insn) = tmp;
601 :
602 63862825 : if (INSN_CACHED_COND (insn) == NULL_RTX)
603 : {
604 58960148 : INSN_CACHED_COND (insn) = const_true_rtx;
605 58960148 : return NULL_RTX;
606 : }
607 :
608 4902677 : if (rev)
609 0 : *rev = INSN_REVERSE_COND (insn);
610 4902677 : return INSN_CACHED_COND (insn);
611 : }
612 :
613 : /* True when we can find a condition under which INSN is executed. */
614 : static bool
615 65808532 : sched_has_condition_p (const rtx_insn *insn)
616 : {
617 0 : return !! sched_get_condition_with_rev (insn, NULL);
618 : }
619 :
620 :
621 :
622 : /* Return true if conditions COND1 and COND2 can never be both true. */
623 : static bool
624 0 : conditions_mutex_p (const_rtx cond1, const_rtx cond2, bool rev1, bool rev2)
625 : {
626 0 : if (COMPARISON_P (cond1)
627 0 : && COMPARISON_P (cond2)
628 0 : && GET_CODE (cond1) ==
629 : (rev1==rev2
630 0 : ? reversed_comparison_code (cond2, NULL)
631 : : GET_CODE (cond2))
632 0 : && rtx_equal_p (XEXP (cond1, 0), XEXP (cond2, 0))
633 0 : && XEXP (cond1, 1) == XEXP (cond2, 1))
634 0 : return true;
635 : return false;
636 : }
637 :
638 : /* Return true if insn1 and insn2 can never depend on one another because
639 : the conditions under which they are executed are mutually exclusive. */
640 : bool
641 502638181 : sched_insns_conditions_mutex_p (const rtx_insn *insn1, const rtx_insn *insn2)
642 : {
643 502638181 : rtx cond1, cond2;
644 502638181 : bool rev1 = false, rev2 = false;
645 :
646 : /* df doesn't handle conditional lifetimes entirely correctly;
647 : calls mess up the conditional lifetimes. */
648 502638181 : if (!CALL_P (insn1) && !CALL_P (insn2))
649 : {
650 225791372 : cond1 = sched_get_condition_with_rev (insn1, &rev1);
651 225791372 : cond2 = sched_get_condition_with_rev (insn2, &rev2);
652 225791372 : if (cond1 && cond2
653 0 : && conditions_mutex_p (cond1, cond2, rev1, rev2)
654 : /* Make sure first instruction doesn't affect condition of second
655 : instruction if switched. */
656 0 : && !modified_in_p (cond1, insn2)
657 : /* Make sure second instruction doesn't affect condition of first
658 : instruction if switched. */
659 225791372 : && !modified_in_p (cond2, insn1))
660 0 : return true;
661 : }
662 : return false;
663 : }
664 :
665 :
666 : /* Return true if INSN can potentially be speculated with type DS. */
667 : bool
668 0 : sched_insn_is_legitimate_for_speculation_p (const rtx_insn *insn, ds_t ds)
669 : {
670 0 : if (HAS_INTERNAL_DEP (insn))
671 : return false;
672 :
673 0 : if (!NONJUMP_INSN_P (insn))
674 : return false;
675 :
676 0 : if (SCHED_GROUP_P (insn))
677 : return false;
678 :
679 0 : if (IS_SPECULATION_CHECK_P (const_cast<struct rtx_insn *> (insn)))
680 : return false;
681 :
682 0 : if (side_effects_p (PATTERN (insn)))
683 : return false;
684 :
685 0 : if (ds & BE_IN_SPEC)
686 : /* The following instructions, which depend on a speculatively scheduled
687 : instruction, cannot be speculatively scheduled along. */
688 : {
689 0 : if (may_trap_or_fault_p (PATTERN (insn)))
690 : /* If instruction might fault, it cannot be speculatively scheduled.
691 : For control speculation it's obvious why and for data speculation
692 : it's because the insn might get wrong input if speculation
693 : wasn't successful. */
694 : return false;
695 :
696 0 : if ((ds & BE_IN_DATA)
697 0 : && sched_has_condition_p (insn))
698 : /* If this is a predicated instruction, then it cannot be
699 : speculatively scheduled. See PR35659. */
700 0 : return false;
701 : }
702 :
703 : return true;
704 : }
705 :
706 : /* Initialize LIST_PTR to point to one of the lists present in TYPES_PTR,
707 : initialize RESOLVED_P_PTR with true if that list consists of resolved deps,
708 : and remove the type of returned [through LIST_PTR] list from TYPES_PTR.
709 : This function is used to switch sd_iterator to the next list.
710 : !!! For internal use only. Might consider moving it to sched-int.h. */
711 : void
712 6124339825 : sd_next_list (const_rtx insn, sd_list_types_def *types_ptr,
713 : deps_list_t *list_ptr, bool *resolved_p_ptr)
714 : {
715 6124339825 : sd_list_types_def types = *types_ptr;
716 :
717 6124339825 : if (types & SD_LIST_HARD_BACK)
718 : {
719 1436559135 : *list_ptr = INSN_HARD_BACK_DEPS (insn);
720 1436559135 : *resolved_p_ptr = false;
721 1436559135 : *types_ptr = types & ~SD_LIST_HARD_BACK;
722 : }
723 4687780690 : else if (types & SD_LIST_SPEC_BACK)
724 : {
725 924584281 : *list_ptr = INSN_SPEC_BACK_DEPS (insn);
726 924584281 : *resolved_p_ptr = false;
727 924584281 : *types_ptr = types & ~SD_LIST_SPEC_BACK;
728 : }
729 3763196409 : else if (types & SD_LIST_FORW)
730 : {
731 2217127010 : *list_ptr = INSN_FORW_DEPS (insn);
732 2217127010 : *resolved_p_ptr = false;
733 2217127010 : *types_ptr = types & ~SD_LIST_FORW;
734 : }
735 1546069399 : else if (types & SD_LIST_RES_BACK)
736 : {
737 972528551 : *list_ptr = INSN_RESOLVED_BACK_DEPS (insn);
738 972528551 : *resolved_p_ptr = true;
739 972528551 : *types_ptr = types & ~SD_LIST_RES_BACK;
740 : }
741 573540848 : else if (types & SD_LIST_RES_FORW)
742 : {
743 573540848 : *list_ptr = INSN_RESOLVED_FORW_DEPS (insn);
744 573540848 : *resolved_p_ptr = true;
745 573540848 : *types_ptr = types & ~SD_LIST_RES_FORW;
746 : }
747 : else
748 : {
749 0 : *list_ptr = NULL;
750 0 : *resolved_p_ptr = false;
751 0 : *types_ptr = SD_LIST_NONE;
752 : }
753 6124339825 : }
754 :
755 : /* Return the summary size of INSN's lists defined by LIST_TYPES. */
756 : int
757 2684910164 : sd_lists_size (const_rtx insn, sd_list_types_def list_types)
758 : {
759 2684910164 : int size = 0;
760 :
761 5948881912 : while (list_types != SD_LIST_NONE)
762 : {
763 3263971748 : deps_list_t list;
764 3263971748 : bool resolved_p;
765 :
766 3263971748 : sd_next_list (insn, &list_types, &list, &resolved_p);
767 3263971748 : if (list)
768 3263971748 : size += DEPS_LIST_N_LINKS (list);
769 : }
770 :
771 2684910164 : return size;
772 : }
773 :
774 : /* Return true if INSN's lists defined by LIST_TYPES are all empty. */
775 :
776 : bool
777 712643103 : sd_lists_empty_p (const_rtx insn, sd_list_types_def list_types)
778 : {
779 1074906836 : while (list_types != SD_LIST_NONE)
780 : {
781 827161972 : deps_list_t list;
782 827161972 : bool resolved_p;
783 :
784 827161972 : sd_next_list (insn, &list_types, &list, &resolved_p);
785 827161972 : if (!deps_list_empty_p (list))
786 464898239 : return false;
787 : }
788 :
789 : return true;
790 : }
791 :
792 : /* Initialize data for INSN. */
793 : void
794 114461623 : sd_init_insn (rtx_insn *insn)
795 : {
796 114461623 : INSN_HARD_BACK_DEPS (insn) = create_deps_list ();
797 114461623 : INSN_SPEC_BACK_DEPS (insn) = create_deps_list ();
798 114461623 : INSN_RESOLVED_BACK_DEPS (insn) = create_deps_list ();
799 114461623 : INSN_FORW_DEPS (insn) = create_deps_list ();
800 114461623 : INSN_RESOLVED_FORW_DEPS (insn) = create_deps_list ();
801 :
802 : /* ??? It would be nice to allocate dependency caches here. */
803 114461623 : }
804 :
805 : /* Free data for INSN. */
806 : void
807 114461623 : sd_finish_insn (rtx_insn *insn)
808 : {
809 : /* ??? It would be nice to deallocate dependency caches here. */
810 :
811 114461623 : free_deps_list (INSN_HARD_BACK_DEPS (insn));
812 114461623 : INSN_HARD_BACK_DEPS (insn) = NULL;
813 :
814 114461623 : free_deps_list (INSN_SPEC_BACK_DEPS (insn));
815 114461623 : INSN_SPEC_BACK_DEPS (insn) = NULL;
816 :
817 114461623 : free_deps_list (INSN_RESOLVED_BACK_DEPS (insn));
818 114461623 : INSN_RESOLVED_BACK_DEPS (insn) = NULL;
819 :
820 114461623 : free_deps_list (INSN_FORW_DEPS (insn));
821 114461623 : INSN_FORW_DEPS (insn) = NULL;
822 :
823 114461623 : free_deps_list (INSN_RESOLVED_FORW_DEPS (insn));
824 114461623 : INSN_RESOLVED_FORW_DEPS (insn) = NULL;
825 114461623 : }
826 :
827 : /* Find a dependency between producer PRO and consumer CON.
828 : Search through resolved dependency lists if RESOLVED_P is true.
829 : If no such dependency is found return NULL,
830 : otherwise return the dependency and initialize SD_IT_PTR [if it is nonnull]
831 : with an iterator pointing to it. */
832 : static dep_t
833 1006343151 : sd_find_dep_between_no_cache (rtx pro, rtx con, bool resolved_p,
834 : sd_iterator_def *sd_it_ptr)
835 : {
836 1006343151 : sd_list_types_def pro_list_type;
837 1006343151 : sd_list_types_def con_list_type;
838 1006343151 : sd_iterator_def sd_it;
839 1006343151 : dep_t dep;
840 1006343151 : bool found_p = false;
841 :
842 1006343151 : if (resolved_p)
843 : {
844 : pro_list_type = SD_LIST_RES_FORW;
845 : con_list_type = SD_LIST_RES_BACK;
846 : }
847 : else
848 : {
849 564261924 : pro_list_type = SD_LIST_FORW;
850 564261924 : con_list_type = SD_LIST_BACK;
851 : }
852 :
853 : /* Walk through either back list of INSN or forw list of ELEM
854 : depending on which one is shorter. */
855 1006343151 : if (sd_lists_size (con, con_list_type) < sd_lists_size (pro, pro_list_type))
856 : {
857 : /* Find the dep_link with producer PRO in consumer's back_deps. */
858 920190927 : FOR_EACH_DEP (con, con_list_type, sd_it, dep)
859 589901121 : if (DEP_PRO (dep) == pro)
860 : {
861 : found_p = true;
862 : break;
863 : }
864 : }
865 : else
866 : {
867 : /* Find the dep_link with consumer CON in producer's forw_deps. */
868 1056618814 : FOR_EACH_DEP (pro, pro_list_type, sd_it, dep)
869 761434110 : if (DEP_CON (dep) == con)
870 : {
871 : found_p = true;
872 : break;
873 : }
874 : }
875 :
876 1006343151 : if (found_p)
877 : {
878 380868641 : if (sd_it_ptr != NULL)
879 336561201 : *sd_it_ptr = sd_it;
880 :
881 380868641 : return dep;
882 : }
883 :
884 : return NULL;
885 : }
886 :
887 : /* Find a dependency between producer PRO and consumer CON.
888 : Use dependency [if available] to check if dependency is present at all.
889 : Search through resolved dependency lists if RESOLVED_P is true.
890 : If the dependency or NULL if none found. */
891 : dep_t
892 447527479 : sd_find_dep_between (rtx pro, rtx con, bool resolved_p)
893 : {
894 447527479 : if (true_dependency_cache != NULL)
895 : /* Avoiding the list walk below can cut compile times dramatically
896 : for some code. */
897 : {
898 535137 : int elem_luid = INSN_LUID (pro);
899 535137 : int insn_luid = INSN_LUID (con);
900 :
901 535137 : if (!bitmap_bit_p (&true_dependency_cache[insn_luid], elem_luid)
902 518632 : && !bitmap_bit_p (&output_dependency_cache[insn_luid], elem_luid)
903 320011 : && !bitmap_bit_p (&anti_dependency_cache[insn_luid], elem_luid)
904 835080 : && !bitmap_bit_p (&control_dependency_cache[insn_luid], elem_luid))
905 : return NULL;
906 : }
907 :
908 447227536 : return sd_find_dep_between_no_cache (pro, con, resolved_p, NULL);
909 : }
910 :
911 : /* Add or update a dependence described by DEP.
912 : MEM1 and MEM2, if non-null, correspond to memory locations in case of
913 : data speculation.
914 :
915 : The function returns a value indicating if an old entry has been changed
916 : or a new entry has been added to insn's backward deps.
917 :
918 : This function merely checks if producer and consumer is the same insn
919 : and doesn't create a dep in this case. Actual manipulation of
920 : dependence data structures is performed in add_or_update_dep_1. */
921 : static enum DEPS_ADJUST_RESULT
922 656415875 : maybe_add_or_update_dep_1 (dep_t dep, bool resolved_p, rtx mem1, rtx mem2)
923 : {
924 656415875 : rtx_insn *elem = DEP_PRO (dep);
925 656415875 : rtx_insn *insn = DEP_CON (dep);
926 :
927 656415875 : gcc_assert (INSN_P (insn) && INSN_P (elem));
928 :
929 : /* Don't depend an insn on itself. */
930 656415875 : if (insn == elem)
931 : {
932 95268865 : if (sched_deps_info->generate_spec_deps)
933 : /* INSN has an internal dependence, which we can't overcome. */
934 0 : HAS_INTERNAL_DEP (insn) = 1;
935 :
936 : return DEP_NODEP;
937 : }
938 :
939 561147010 : return add_or_update_dep_1 (dep, resolved_p, mem1, mem2);
940 : }
941 :
942 : /* Ask dependency caches what needs to be done for dependence DEP.
943 : Return DEP_CREATED if new dependence should be created and there is no
944 : need to try to find one searching the dependencies lists.
945 : Return DEP_PRESENT if there already is a dependence described by DEP and
946 : hence nothing is to be done.
947 : Return DEP_CHANGED if there already is a dependence, but it should be
948 : updated to incorporate additional information from DEP. */
949 : static enum DEPS_ADJUST_RESULT
950 5016934 : ask_dependency_caches (dep_t dep)
951 : {
952 5016934 : int elem_luid = INSN_LUID (DEP_PRO (dep));
953 5016934 : int insn_luid = INSN_LUID (DEP_CON (dep));
954 :
955 5016934 : gcc_assert (true_dependency_cache != NULL
956 : && output_dependency_cache != NULL
957 : && anti_dependency_cache != NULL
958 : && control_dependency_cache != NULL);
959 :
960 5016934 : if (!(current_sched_info->flags & USE_DEPS_LIST))
961 : {
962 5016934 : enum reg_note present_dep_type;
963 :
964 5016934 : if (bitmap_bit_p (&true_dependency_cache[insn_luid], elem_luid))
965 : present_dep_type = REG_DEP_TRUE;
966 4786428 : else if (bitmap_bit_p (&output_dependency_cache[insn_luid], elem_luid))
967 : present_dep_type = REG_DEP_OUTPUT;
968 2247803 : else if (bitmap_bit_p (&anti_dependency_cache[insn_luid], elem_luid))
969 : present_dep_type = REG_DEP_ANTI;
970 2031395 : else if (bitmap_bit_p (&control_dependency_cache[insn_luid], elem_luid))
971 : present_dep_type = REG_DEP_CONTROL;
972 : else
973 : /* There is no existing dep so it should be created. */
974 : return DEP_CREATED;
975 :
976 2755033 : if ((int) DEP_TYPE (dep) >= (int) present_dep_type)
977 : /* DEP does not add anything to the existing dependence. */
978 2951477 : return DEP_PRESENT;
979 : }
980 : else
981 : {
982 0 : ds_t present_dep_types = 0;
983 :
984 0 : if (bitmap_bit_p (&true_dependency_cache[insn_luid], elem_luid))
985 0 : present_dep_types |= DEP_TRUE;
986 0 : if (bitmap_bit_p (&output_dependency_cache[insn_luid], elem_luid))
987 0 : present_dep_types |= DEP_OUTPUT;
988 0 : if (bitmap_bit_p (&anti_dependency_cache[insn_luid], elem_luid))
989 0 : present_dep_types |= DEP_ANTI;
990 0 : if (bitmap_bit_p (&control_dependency_cache[insn_luid], elem_luid))
991 0 : present_dep_types |= DEP_CONTROL;
992 :
993 0 : if (present_dep_types == 0)
994 : /* There is no existing dep so it should be created. */
995 : return DEP_CREATED;
996 :
997 0 : if (!(current_sched_info->flags & DO_SPECULATION)
998 0 : || !bitmap_bit_p (&spec_dependency_cache[insn_luid], elem_luid))
999 : {
1000 0 : if ((present_dep_types | (DEP_STATUS (dep) & DEP_TYPES))
1001 : == present_dep_types)
1002 : /* DEP does not add anything to the existing dependence. */
1003 0 : return DEP_PRESENT;
1004 : }
1005 : else
1006 : {
1007 : /* Only true dependencies can be data speculative and
1008 : only anti dependencies can be control speculative. */
1009 0 : gcc_assert ((present_dep_types & (DEP_TRUE | DEP_ANTI))
1010 : == present_dep_types);
1011 :
1012 : /* if (DEP is SPECULATIVE) then
1013 : ..we should update DEP_STATUS
1014 : else
1015 : ..we should reset existing dep to non-speculative. */
1016 : }
1017 : }
1018 :
1019 : return DEP_CHANGED;
1020 : }
1021 :
1022 : /* Set dependency caches according to DEP. */
1023 : static void
1024 2065457 : set_dependency_caches (dep_t dep)
1025 : {
1026 2065457 : int elem_luid = INSN_LUID (DEP_PRO (dep));
1027 2065457 : int insn_luid = INSN_LUID (DEP_CON (dep));
1028 :
1029 2065457 : if (!(current_sched_info->flags & USE_DEPS_LIST))
1030 : {
1031 2065457 : switch (DEP_TYPE (dep))
1032 : {
1033 328746 : case REG_DEP_TRUE:
1034 328746 : bitmap_set_bit (&true_dependency_cache[insn_luid], elem_luid);
1035 328746 : break;
1036 :
1037 381719 : case REG_DEP_OUTPUT:
1038 381719 : bitmap_set_bit (&output_dependency_cache[insn_luid], elem_luid);
1039 381719 : break;
1040 :
1041 1354992 : case REG_DEP_ANTI:
1042 1354992 : bitmap_set_bit (&anti_dependency_cache[insn_luid], elem_luid);
1043 1354992 : break;
1044 :
1045 0 : case REG_DEP_CONTROL:
1046 0 : bitmap_set_bit (&control_dependency_cache[insn_luid], elem_luid);
1047 0 : break;
1048 :
1049 0 : default:
1050 0 : gcc_unreachable ();
1051 : }
1052 : }
1053 : else
1054 : {
1055 0 : ds_t ds = DEP_STATUS (dep);
1056 :
1057 0 : if (ds & DEP_TRUE)
1058 0 : bitmap_set_bit (&true_dependency_cache[insn_luid], elem_luid);
1059 0 : if (ds & DEP_OUTPUT)
1060 0 : bitmap_set_bit (&output_dependency_cache[insn_luid], elem_luid);
1061 0 : if (ds & DEP_ANTI)
1062 0 : bitmap_set_bit (&anti_dependency_cache[insn_luid], elem_luid);
1063 0 : if (ds & DEP_CONTROL)
1064 0 : bitmap_set_bit (&control_dependency_cache[insn_luid], elem_luid);
1065 :
1066 0 : if (ds & SPECULATIVE)
1067 : {
1068 0 : gcc_assert (current_sched_info->flags & DO_SPECULATION);
1069 0 : bitmap_set_bit (&spec_dependency_cache[insn_luid], elem_luid);
1070 : }
1071 : }
1072 2065457 : }
1073 :
1074 : /* Type of dependence DEP have changed from OLD_TYPE. Update dependency
1075 : caches accordingly. */
1076 : static void
1077 34062 : update_dependency_caches (dep_t dep, enum reg_note old_type)
1078 : {
1079 34062 : int elem_luid = INSN_LUID (DEP_PRO (dep));
1080 34062 : int insn_luid = INSN_LUID (DEP_CON (dep));
1081 :
1082 : /* Clear corresponding cache entry because type of the link
1083 : may have changed. Keep them if we use_deps_list. */
1084 34062 : if (!(current_sched_info->flags & USE_DEPS_LIST))
1085 : {
1086 34062 : switch (old_type)
1087 : {
1088 3095 : case REG_DEP_OUTPUT:
1089 3095 : bitmap_clear_bit (&output_dependency_cache[insn_luid], elem_luid);
1090 3095 : break;
1091 :
1092 30967 : case REG_DEP_ANTI:
1093 30967 : bitmap_clear_bit (&anti_dependency_cache[insn_luid], elem_luid);
1094 30967 : break;
1095 :
1096 0 : case REG_DEP_CONTROL:
1097 0 : bitmap_clear_bit (&control_dependency_cache[insn_luid], elem_luid);
1098 0 : break;
1099 :
1100 0 : default:
1101 0 : gcc_unreachable ();
1102 : }
1103 : }
1104 :
1105 34062 : set_dependency_caches (dep);
1106 34062 : }
1107 :
1108 : /* Convert a dependence pointed to by SD_IT to be non-speculative. */
1109 : static void
1110 0 : change_spec_dep_to_hard (sd_iterator_def sd_it)
1111 : {
1112 0 : dep_node_t node = DEP_LINK_NODE (*sd_it.linkp);
1113 0 : dep_link_t link = DEP_NODE_BACK (node);
1114 0 : dep_t dep = DEP_NODE_DEP (node);
1115 0 : rtx_insn *elem = DEP_PRO (dep);
1116 0 : rtx_insn *insn = DEP_CON (dep);
1117 :
1118 0 : move_dep_link (link, INSN_SPEC_BACK_DEPS (insn), INSN_HARD_BACK_DEPS (insn));
1119 :
1120 0 : DEP_STATUS (dep) &= ~SPECULATIVE;
1121 :
1122 0 : if (true_dependency_cache != NULL)
1123 : /* Clear the cache entry. */
1124 0 : bitmap_clear_bit (&spec_dependency_cache[INSN_LUID (insn)],
1125 0 : INSN_LUID (elem));
1126 0 : }
1127 :
1128 : /* Update DEP to incorporate information from NEW_DEP.
1129 : SD_IT points to DEP in case it should be moved to another list.
1130 : MEM1 and MEM2, if nonnull, correspond to memory locations in case if
1131 : data-speculative dependence should be updated. */
1132 : static enum DEPS_ADJUST_RESULT
1133 333609724 : update_dep (dep_t dep, dep_t new_dep,
1134 : sd_iterator_def sd_it ATTRIBUTE_UNUSED,
1135 : rtx mem1 ATTRIBUTE_UNUSED,
1136 : rtx mem2 ATTRIBUTE_UNUSED)
1137 : {
1138 333609724 : enum DEPS_ADJUST_RESULT res = DEP_PRESENT;
1139 333609724 : enum reg_note old_type = DEP_TYPE (dep);
1140 333609724 : bool was_spec = dep_spec_p (dep);
1141 :
1142 333609724 : DEP_NONREG (dep) |= DEP_NONREG (new_dep);
1143 333609724 : DEP_MULTIPLE (dep) = 1;
1144 :
1145 : /* If this is a more restrictive type of dependence than the
1146 : existing one, then change the existing dependence to this
1147 : type. */
1148 333609724 : if ((int) DEP_TYPE (new_dep) < (int) old_type)
1149 : {
1150 19650813 : DEP_TYPE (dep) = DEP_TYPE (new_dep);
1151 19650813 : res = DEP_CHANGED;
1152 : }
1153 :
1154 333609724 : if (current_sched_info->flags & USE_DEPS_LIST)
1155 : /* Update DEP_STATUS. */
1156 : {
1157 0 : ds_t dep_status = DEP_STATUS (dep);
1158 0 : ds_t ds = DEP_STATUS (new_dep);
1159 0 : ds_t new_status = ds | dep_status;
1160 :
1161 0 : if (new_status & SPECULATIVE)
1162 : {
1163 : /* Either existing dep or a dep we're adding or both are
1164 : speculative. */
1165 0 : if (!(ds & SPECULATIVE)
1166 0 : || !(dep_status & SPECULATIVE))
1167 : /* The new dep can't be speculative. */
1168 0 : new_status &= ~SPECULATIVE;
1169 : else
1170 : {
1171 : /* Both are speculative. Merge probabilities. */
1172 0 : if (mem1 != NULL)
1173 : {
1174 0 : dw_t dw;
1175 :
1176 0 : dw = estimate_dep_weak (mem1, mem2);
1177 0 : ds = set_dep_weak (ds, BEGIN_DATA, dw);
1178 : }
1179 :
1180 0 : new_status = ds_merge (dep_status, ds);
1181 : }
1182 : }
1183 :
1184 0 : ds = new_status;
1185 :
1186 0 : if (dep_status != ds)
1187 : {
1188 0 : DEP_STATUS (dep) = ds;
1189 0 : res = DEP_CHANGED;
1190 : }
1191 : }
1192 :
1193 333609724 : if (was_spec && !dep_spec_p (dep))
1194 : /* The old dep was speculative, but now it isn't. */
1195 0 : change_spec_dep_to_hard (sd_it);
1196 :
1197 333609724 : if (true_dependency_cache != NULL
1198 34062 : && res == DEP_CHANGED)
1199 34062 : update_dependency_caches (dep, old_type);
1200 :
1201 333609724 : return res;
1202 : }
1203 :
1204 : /* Add or update a dependence described by DEP.
1205 : MEM1 and MEM2, if non-null, correspond to memory locations in case of
1206 : data speculation.
1207 :
1208 : The function returns a value indicating if an old entry has been changed
1209 : or a new entry has been added to insn's backward deps or nothing has
1210 : been updated at all. */
1211 : static enum DEPS_ADJUST_RESULT
1212 561147010 : add_or_update_dep_1 (dep_t new_dep, bool resolved_p,
1213 : rtx mem1 ATTRIBUTE_UNUSED, rtx mem2 ATTRIBUTE_UNUSED)
1214 : {
1215 561147010 : bool maybe_present_p = true;
1216 561147010 : bool present_p = false;
1217 :
1218 561147010 : gcc_assert (INSN_P (DEP_PRO (new_dep)) && INSN_P (DEP_CON (new_dep))
1219 : && DEP_PRO (new_dep) != DEP_CON (new_dep));
1220 :
1221 561147010 : if (flag_checking)
1222 561145081 : check_dep (new_dep, mem1 != NULL);
1223 :
1224 561147010 : if (true_dependency_cache != NULL)
1225 : {
1226 5016934 : switch (ask_dependency_caches (new_dep))
1227 : {
1228 2951477 : case DEP_PRESENT:
1229 2951477 : dep_t present_dep;
1230 2951477 : sd_iterator_def sd_it;
1231 :
1232 5902954 : present_dep = sd_find_dep_between_no_cache (DEP_PRO (new_dep),
1233 2951477 : DEP_CON (new_dep),
1234 : resolved_p, &sd_it);
1235 2951477 : DEP_MULTIPLE (present_dep) = 1;
1236 2951477 : return DEP_PRESENT;
1237 :
1238 : case DEP_CHANGED:
1239 : maybe_present_p = true;
1240 : present_p = true;
1241 2065457 : break;
1242 :
1243 2031395 : case DEP_CREATED:
1244 2031395 : maybe_present_p = false;
1245 2031395 : present_p = false;
1246 2031395 : break;
1247 :
1248 : default:
1249 : gcc_unreachable ();
1250 2951477 : break;
1251 : }
1252 : }
1253 :
1254 : /* Check that we don't already have this dependence. */
1255 2065457 : if (maybe_present_p)
1256 : {
1257 556164138 : dep_t present_dep;
1258 556164138 : sd_iterator_def sd_it;
1259 :
1260 556164138 : gcc_assert (true_dependency_cache == NULL || present_p);
1261 :
1262 1112328276 : present_dep = sd_find_dep_between_no_cache (DEP_PRO (new_dep),
1263 556164138 : DEP_CON (new_dep),
1264 : resolved_p, &sd_it);
1265 :
1266 556164138 : if (present_dep != NULL)
1267 : /* We found an existing dependency between ELEM and INSN. */
1268 333609724 : return update_dep (present_dep, new_dep, sd_it, mem1, mem2);
1269 : else
1270 : /* We didn't find a dep, it shouldn't present in the cache. */
1271 222554414 : gcc_assert (!present_p);
1272 : }
1273 :
1274 : /* Might want to check one level of transitivity to save conses.
1275 : This check should be done in maybe_add_or_update_dep_1.
1276 : Since we made it to add_or_update_dep_1, we must create
1277 : (or update) a link. */
1278 :
1279 224585809 : if (mem1 != NULL_RTX)
1280 : {
1281 0 : gcc_assert (sched_deps_info->generate_spec_deps);
1282 0 : DEP_STATUS (new_dep) = set_dep_weak (DEP_STATUS (new_dep), BEGIN_DATA,
1283 : estimate_dep_weak (mem1, mem2));
1284 : }
1285 :
1286 224585809 : sd_add_dep (new_dep, resolved_p);
1287 :
1288 224585809 : return DEP_CREATED;
1289 : }
1290 :
1291 : /* Initialize BACK_LIST_PTR with consumer's backward list and
1292 : FORW_LIST_PTR with producer's forward list. If RESOLVED_P is true
1293 : initialize with lists that hold resolved deps. */
1294 : static void
1295 449171618 : get_back_and_forw_lists (dep_t dep, bool resolved_p,
1296 : deps_list_t *back_list_ptr,
1297 : deps_list_t *forw_list_ptr)
1298 : {
1299 449171618 : rtx_insn *con = DEP_CON (dep);
1300 :
1301 449171618 : if (!resolved_p)
1302 : {
1303 232505748 : if (dep_spec_p (dep))
1304 0 : *back_list_ptr = INSN_SPEC_BACK_DEPS (con);
1305 : else
1306 232505748 : *back_list_ptr = INSN_HARD_BACK_DEPS (con);
1307 :
1308 232505748 : *forw_list_ptr = INSN_FORW_DEPS (DEP_PRO (dep));
1309 : }
1310 : else
1311 : {
1312 216665870 : *back_list_ptr = INSN_RESOLVED_BACK_DEPS (con);
1313 216665870 : *forw_list_ptr = INSN_RESOLVED_FORW_DEPS (DEP_PRO (dep));
1314 : }
1315 449171618 : }
1316 :
1317 : /* Add dependence described by DEP.
1318 : If RESOLVED_P is true treat the dependence as a resolved one. */
1319 : void
1320 224585809 : sd_add_dep (dep_t dep, bool resolved_p)
1321 : {
1322 224585809 : dep_node_t n = create_dep_node ();
1323 224585809 : deps_list_t con_back_deps;
1324 224585809 : deps_list_t pro_forw_deps;
1325 224585809 : rtx_insn *elem = DEP_PRO (dep);
1326 224585809 : rtx_insn *insn = DEP_CON (dep);
1327 :
1328 224585809 : gcc_assert (INSN_P (insn) && INSN_P (elem) && insn != elem);
1329 :
1330 224585809 : if ((current_sched_info->flags & DO_SPECULATION) == 0
1331 224585809 : || !sched_insn_is_legitimate_for_speculation_p (insn, DEP_STATUS (dep)))
1332 224585809 : DEP_STATUS (dep) &= ~SPECULATIVE;
1333 :
1334 224585809 : copy_dep (DEP_NODE_DEP (n), dep);
1335 :
1336 224585809 : get_back_and_forw_lists (dep, resolved_p, &con_back_deps, &pro_forw_deps);
1337 :
1338 224585809 : add_to_deps_list (DEP_NODE_BACK (n), con_back_deps);
1339 :
1340 224585809 : if (flag_checking)
1341 224585486 : check_dep (dep, false);
1342 :
1343 224585809 : add_to_deps_list (DEP_NODE_FORW (n), pro_forw_deps);
1344 :
1345 : /* If we are adding a dependency to INSN's LOG_LINKs, then note that
1346 : in the bitmap caches of dependency information. */
1347 224585809 : if (true_dependency_cache != NULL)
1348 2031395 : set_dependency_caches (dep);
1349 224585809 : }
1350 :
1351 : /* Add or update backward dependence between INSN and ELEM
1352 : with given type DEP_TYPE and dep_status DS.
1353 : This function is a convenience wrapper. */
1354 : enum DEPS_ADJUST_RESULT
1355 0 : sd_add_or_update_dep (dep_t dep, bool resolved_p)
1356 : {
1357 0 : return add_or_update_dep_1 (dep, resolved_p, NULL_RTX, NULL_RTX);
1358 : }
1359 :
1360 : /* Resolved dependence pointed to by SD_IT.
1361 : SD_IT will advance to the next element. */
1362 : void
1363 216665870 : sd_resolve_dep (sd_iterator_def sd_it)
1364 : {
1365 216665870 : dep_node_t node = DEP_LINK_NODE (*sd_it.linkp);
1366 216665870 : dep_t dep = DEP_NODE_DEP (node);
1367 216665870 : rtx_insn *pro = DEP_PRO (dep);
1368 216665870 : rtx_insn *con = DEP_CON (dep);
1369 :
1370 216665870 : if (dep_spec_p (dep))
1371 1133241 : move_dep_link (DEP_NODE_BACK (node), INSN_SPEC_BACK_DEPS (con),
1372 1133241 : INSN_RESOLVED_BACK_DEPS (con));
1373 : else
1374 215532629 : move_dep_link (DEP_NODE_BACK (node), INSN_HARD_BACK_DEPS (con),
1375 215532629 : INSN_RESOLVED_BACK_DEPS (con));
1376 :
1377 649997610 : move_dep_link (DEP_NODE_FORW (node), INSN_FORW_DEPS (pro),
1378 216665870 : INSN_RESOLVED_FORW_DEPS (pro));
1379 216665870 : }
1380 :
1381 : /* Perform the inverse operation of sd_resolve_dep. Restore the dependence
1382 : pointed to by SD_IT to unresolved state. */
1383 : void
1384 0 : sd_unresolve_dep (sd_iterator_def sd_it)
1385 : {
1386 0 : dep_node_t node = DEP_LINK_NODE (*sd_it.linkp);
1387 0 : dep_t dep = DEP_NODE_DEP (node);
1388 0 : rtx_insn *pro = DEP_PRO (dep);
1389 0 : rtx_insn *con = DEP_CON (dep);
1390 :
1391 0 : if (dep_spec_p (dep))
1392 0 : move_dep_link (DEP_NODE_BACK (node), INSN_RESOLVED_BACK_DEPS (con),
1393 0 : INSN_SPEC_BACK_DEPS (con));
1394 : else
1395 0 : move_dep_link (DEP_NODE_BACK (node), INSN_RESOLVED_BACK_DEPS (con),
1396 0 : INSN_HARD_BACK_DEPS (con));
1397 :
1398 0 : move_dep_link (DEP_NODE_FORW (node), INSN_RESOLVED_FORW_DEPS (pro),
1399 0 : INSN_FORW_DEPS (pro));
1400 0 : }
1401 :
1402 : /* Make TO depend on all the FROM's producers.
1403 : If RESOLVED_P is true add dependencies to the resolved lists. */
1404 : void
1405 0 : sd_copy_back_deps (rtx_insn *to, rtx_insn *from, bool resolved_p)
1406 : {
1407 0 : sd_list_types_def list_type;
1408 0 : sd_iterator_def sd_it;
1409 0 : dep_t dep;
1410 :
1411 0 : list_type = resolved_p ? SD_LIST_RES_BACK : SD_LIST_BACK;
1412 :
1413 0 : FOR_EACH_DEP (from, list_type, sd_it, dep)
1414 : {
1415 0 : dep_def _new_dep, *new_dep = &_new_dep;
1416 :
1417 0 : copy_dep (new_dep, dep);
1418 0 : DEP_CON (new_dep) = to;
1419 0 : sd_add_dep (new_dep, resolved_p);
1420 : }
1421 0 : }
1422 :
1423 : /* Remove a dependency referred to by SD_IT.
1424 : SD_IT will point to the next dependence after removal. */
1425 : void
1426 7910494 : sd_delete_dep (sd_iterator_def sd_it)
1427 : {
1428 7910494 : dep_node_t n = DEP_LINK_NODE (*sd_it.linkp);
1429 7910494 : dep_t dep = DEP_NODE_DEP (n);
1430 7910494 : rtx_insn *pro = DEP_PRO (dep);
1431 7910494 : rtx_insn *con = DEP_CON (dep);
1432 7910494 : deps_list_t con_back_deps;
1433 7910494 : deps_list_t pro_forw_deps;
1434 :
1435 7910494 : if (true_dependency_cache != NULL)
1436 : {
1437 2991 : int elem_luid = INSN_LUID (pro);
1438 2991 : int insn_luid = INSN_LUID (con);
1439 :
1440 2991 : bitmap_clear_bit (&true_dependency_cache[insn_luid], elem_luid);
1441 2991 : bitmap_clear_bit (&anti_dependency_cache[insn_luid], elem_luid);
1442 2991 : bitmap_clear_bit (&control_dependency_cache[insn_luid], elem_luid);
1443 2991 : bitmap_clear_bit (&output_dependency_cache[insn_luid], elem_luid);
1444 :
1445 2991 : if (current_sched_info->flags & DO_SPECULATION)
1446 0 : bitmap_clear_bit (&spec_dependency_cache[insn_luid], elem_luid);
1447 : }
1448 :
1449 7910494 : get_back_and_forw_lists (dep, sd_it.resolved_p,
1450 : &con_back_deps, &pro_forw_deps);
1451 :
1452 7910494 : remove_from_deps_list (DEP_NODE_BACK (n), con_back_deps);
1453 7910494 : remove_from_deps_list (DEP_NODE_FORW (n), pro_forw_deps);
1454 :
1455 7910494 : delete_dep_node (n);
1456 7910494 : }
1457 :
1458 : /* Dump size of the lists. */
1459 : #define DUMP_LISTS_SIZE (2)
1460 :
1461 : /* Dump dependencies of the lists. */
1462 : #define DUMP_LISTS_DEPS (4)
1463 :
1464 : /* Dump all information about the lists. */
1465 : #define DUMP_LISTS_ALL (DUMP_LISTS_SIZE | DUMP_LISTS_DEPS)
1466 :
1467 : /* Dump deps_lists of INSN specified by TYPES to DUMP.
1468 : FLAGS is a bit mask specifying what information about the lists needs
1469 : to be printed.
1470 : If FLAGS has the very first bit set, then dump all information about
1471 : the lists and propagate this bit into the callee dump functions. */
1472 : static void
1473 0 : dump_lists (FILE *dump, rtx insn, sd_list_types_def types, int flags)
1474 : {
1475 0 : sd_iterator_def sd_it;
1476 0 : dep_t dep;
1477 0 : int all;
1478 :
1479 0 : all = (flags & 1);
1480 :
1481 0 : if (all)
1482 0 : flags |= DUMP_LISTS_ALL;
1483 :
1484 0 : fprintf (dump, "[");
1485 :
1486 0 : if (flags & DUMP_LISTS_SIZE)
1487 0 : fprintf (dump, "%d; ", sd_lists_size (insn, types));
1488 :
1489 0 : if (flags & DUMP_LISTS_DEPS)
1490 : {
1491 0 : FOR_EACH_DEP (insn, types, sd_it, dep)
1492 : {
1493 0 : dump_dep (dump, dep, dump_dep_flags | all);
1494 0 : fprintf (dump, " ");
1495 : }
1496 : }
1497 0 : }
1498 :
1499 : /* Dump all information about deps_lists of INSN specified by TYPES
1500 : to STDERR. */
1501 : void
1502 0 : sd_debug_lists (rtx insn, sd_list_types_def types)
1503 : {
1504 0 : dump_lists (stderr, insn, types, 1);
1505 0 : fprintf (stderr, "\n");
1506 0 : }
1507 :
1508 : /* A wrapper around add_dependence_1, to add a dependence of CON on
1509 : PRO, with type DEP_TYPE. This function implements special handling
1510 : for REG_DEP_CONTROL dependencies. For these, we optionally promote
1511 : the type to REG_DEP_ANTI if we can determine that predication is
1512 : impossible; otherwise we add additional true dependencies on the
1513 : INSN_COND_DEPS list of the jump (which PRO must be). */
1514 : void
1515 616175115 : add_dependence (rtx_insn *con, rtx_insn *pro, enum reg_note dep_type)
1516 : {
1517 616175115 : if (dep_type == REG_DEP_CONTROL
1518 16081 : && !(current_sched_info->flags & DO_PREDICATION))
1519 : dep_type = REG_DEP_ANTI;
1520 :
1521 : /* A REG_DEP_CONTROL dependence may be eliminated through predication,
1522 : so we must also make the insn dependent on the setter of the
1523 : condition. */
1524 0 : if (dep_type == REG_DEP_CONTROL)
1525 : {
1526 0 : rtx_insn *real_pro = pro;
1527 0 : rtx_insn *other = real_insn_for_shadow (real_pro);
1528 0 : rtx cond;
1529 :
1530 0 : if (other != NULL_RTX)
1531 0 : real_pro = other;
1532 0 : cond = sched_get_reverse_condition_uncached (real_pro);
1533 : /* Verify that the insn does not use a different value in
1534 : the condition register than the one that was present at
1535 : the jump. */
1536 0 : if (cond == NULL_RTX)
1537 : dep_type = REG_DEP_ANTI;
1538 0 : else if (INSN_CACHED_COND (real_pro) == const_true_rtx)
1539 : {
1540 : HARD_REG_SET uses;
1541 0 : CLEAR_HARD_REG_SET (uses);
1542 0 : note_uses (&PATTERN (con), record_hard_reg_uses, &uses);
1543 0 : if (TEST_HARD_REG_BIT (uses, REGNO (XEXP (cond, 0))))
1544 0 : dep_type = REG_DEP_ANTI;
1545 : }
1546 0 : if (dep_type == REG_DEP_CONTROL)
1547 : {
1548 0 : if (sched_verbose >= 5)
1549 0 : fprintf (sched_dump, "making DEP_CONTROL for %d\n",
1550 0 : INSN_UID (real_pro));
1551 0 : add_dependence_list (con, INSN_COND_DEPS (real_pro), 0,
1552 : REG_DEP_TRUE, false);
1553 : }
1554 : }
1555 :
1556 616175115 : add_dependence_1 (con, pro, dep_type);
1557 616175115 : }
1558 :
1559 : /* A convenience wrapper to operate on an entire list. HARD should be
1560 : true if DEP_NONREG should be set on newly created dependencies. */
1561 :
1562 : static void
1563 3188492790 : add_dependence_list (rtx_insn *insn, rtx_insn_list *list, int uncond,
1564 : enum reg_note dep_type, bool hard)
1565 : {
1566 3188492790 : mark_as_hard = hard;
1567 3682161670 : for (; list; list = list->next ())
1568 : {
1569 922134280 : if (uncond || ! sched_insns_conditions_mutex_p (insn, list->insn ()))
1570 493668880 : add_dependence (insn, list->insn (), dep_type);
1571 : }
1572 3188492790 : mark_as_hard = false;
1573 3188492790 : }
1574 :
1575 : /* Similar, but free *LISTP at the same time, when the context
1576 : is not readonly. HARD should be true if DEP_NONREG should be set on
1577 : newly created dependencies. */
1578 :
1579 : static void
1580 1217934992 : add_dependence_list_and_free (class deps_desc *deps, rtx_insn *insn,
1581 : rtx_insn_list **listp,
1582 : int uncond, enum reg_note dep_type, bool hard)
1583 : {
1584 1217934992 : add_dependence_list (insn, *listp, uncond, dep_type, hard);
1585 :
1586 : /* We don't want to short-circuit dependencies involving debug
1587 : insns, because they may cause actual dependencies to be
1588 : disregarded. */
1589 1217934992 : if (deps->readonly || DEBUG_INSN_P (insn))
1590 : return;
1591 :
1592 1217855361 : free_INSN_LIST_list (listp);
1593 : }
1594 :
1595 : /* Remove all occurrences of INSN from LIST. Return the number of
1596 : occurrences removed. */
1597 :
1598 : static int
1599 60390 : remove_from_dependence_list (rtx_insn *insn, rtx_insn_list **listp)
1600 : {
1601 60390 : int removed = 0;
1602 :
1603 122842 : while (*listp)
1604 : {
1605 62452 : if ((*listp)->insn () == insn)
1606 : {
1607 12592 : remove_free_INSN_LIST_node (listp);
1608 12592 : removed++;
1609 12592 : continue;
1610 : }
1611 :
1612 49860 : listp = (rtx_insn_list **)&XEXP (*listp, 1);
1613 : }
1614 :
1615 60390 : return removed;
1616 : }
1617 :
1618 : /* Same as above, but process two lists at once. */
1619 : static int
1620 4552 : remove_from_both_dependence_lists (rtx_insn *insn,
1621 : rtx_insn_list **listp,
1622 : rtx_expr_list **exprp)
1623 : {
1624 4552 : int removed = 0;
1625 :
1626 8836 : while (*listp)
1627 : {
1628 4284 : if (XEXP (*listp, 0) == insn)
1629 : {
1630 676 : remove_free_INSN_LIST_node (listp);
1631 676 : remove_free_EXPR_LIST_node (exprp);
1632 676 : removed++;
1633 676 : continue;
1634 : }
1635 :
1636 3608 : listp = (rtx_insn_list **)&XEXP (*listp, 1);
1637 3608 : exprp = (rtx_expr_list **)&XEXP (*exprp, 1);
1638 : }
1639 :
1640 4552 : return removed;
1641 : }
1642 :
1643 : /* Clear all dependencies for an insn. */
1644 : static void
1645 4229958 : delete_all_dependences (rtx_insn *insn)
1646 : {
1647 4229958 : sd_iterator_def sd_it;
1648 4229958 : dep_t dep;
1649 :
1650 : /* The below cycle can be optimized to clear the caches and back_deps
1651 : in one call but that would provoke duplication of code from
1652 : delete_dep (). */
1653 :
1654 4229958 : for (sd_it = sd_iterator_start (insn, SD_LIST_BACK);
1655 12018285 : sd_iterator_cond (&sd_it, &dep);)
1656 7788327 : sd_delete_dep (sd_it);
1657 4229958 : }
1658 :
1659 : /* All insns in a scheduling group except the first should only have
1660 : dependencies on the previous insn in the group. So we find the
1661 : first instruction in the scheduling group by walking the dependence
1662 : chains backwards. Then we add the dependencies for the group to
1663 : the previous nonnote insn. */
1664 :
1665 : static void
1666 4229958 : chain_to_prev_insn (rtx_insn *insn)
1667 : {
1668 4229958 : sd_iterator_def sd_it;
1669 4229958 : dep_t dep;
1670 4229958 : rtx_insn *prev_nonnote;
1671 :
1672 12018285 : FOR_EACH_DEP (insn, SD_LIST_BACK, sd_it, dep)
1673 : {
1674 7788327 : rtx_insn *i = insn;
1675 7788327 : rtx_insn *pro = DEP_PRO (dep);
1676 :
1677 7790729 : do
1678 : {
1679 7790729 : i = prev_nonnote_insn (i);
1680 :
1681 7790729 : if (pro == i)
1682 4229930 : goto next_link;
1683 3563201 : } while (SCHED_GROUP_P (i) || DEBUG_INSN_P (i));
1684 :
1685 3558397 : if (! sched_insns_conditions_mutex_p (i, pro))
1686 3558397 : add_dependence (i, pro, DEP_TYPE (dep));
1687 7788327 : next_link:;
1688 : }
1689 :
1690 4229958 : delete_all_dependences (insn);
1691 :
1692 4229958 : prev_nonnote = prev_nonnote_nondebug_insn (insn);
1693 4229958 : if (BLOCK_FOR_INSN (insn) == BLOCK_FOR_INSN (prev_nonnote)
1694 4229958 : && ! sched_insns_conditions_mutex_p (insn, prev_nonnote))
1695 4229958 : add_dependence (insn, prev_nonnote, REG_DEP_ANTI);
1696 4229958 : }
1697 :
1698 : /* Process an insn's memory dependencies. There are four kinds of
1699 : dependencies:
1700 :
1701 : (0) read dependence: read follows read
1702 : (1) true dependence: read follows write
1703 : (2) output dependence: write follows write
1704 : (3) anti dependence: write follows read
1705 :
1706 : We are careful to build only dependencies which actually exist, and
1707 : use transitivity to avoid building too many links. */
1708 :
1709 : /* Add an INSN and MEM reference pair to a pending INSN_LIST and MEM_LIST.
1710 : The MEM is a memory reference contained within INSN, which we are saving
1711 : so that we can do memory aliasing on it. */
1712 :
1713 : static void
1714 38889786 : add_insn_mem_dependence (class deps_desc *deps, bool read_p,
1715 : rtx_insn *insn, rtx mem)
1716 : {
1717 38889786 : rtx_insn_list **insn_list;
1718 38889786 : rtx_insn_list *insn_node;
1719 38889786 : rtx_expr_list **mem_list;
1720 38889786 : rtx_expr_list *mem_node;
1721 :
1722 38889786 : gcc_assert (!deps->readonly);
1723 38889786 : if (read_p)
1724 : {
1725 1711411 : insn_list = &deps->pending_read_insns;
1726 26229157 : mem_list = &deps->pending_read_mems;
1727 26229157 : if (!DEBUG_INSN_P (insn))
1728 24517746 : deps->pending_read_list_length++;
1729 : }
1730 : else
1731 : {
1732 12660629 : insn_list = &deps->pending_write_insns;
1733 12660629 : mem_list = &deps->pending_write_mems;
1734 12660629 : deps->pending_write_list_length++;
1735 : }
1736 :
1737 38889786 : insn_node = alloc_INSN_LIST (insn, *insn_list);
1738 38889786 : *insn_list = insn_node;
1739 :
1740 38889786 : if (sched_deps_info->use_cselib && MEM_P (mem))
1741 : {
1742 731 : mem = shallow_copy_rtx (mem);
1743 731 : XEXP (mem, 0) = cselib_subst_to_values_from_insn (XEXP (mem, 0),
1744 731 : GET_MODE (mem), insn);
1745 : }
1746 38889786 : mem_node = alloc_EXPR_LIST (VOIDmode, canon_rtx (mem), *mem_list);
1747 38889786 : *mem_list = mem_node;
1748 38889786 : }
1749 :
1750 : /* Make a dependency between every memory reference on the pending lists
1751 : and INSN, thus flushing the pending lists. FOR_READ is true if emitting
1752 : dependencies for a read operation, similarly with FOR_WRITE. */
1753 :
1754 : static void
1755 9682174 : flush_pending_lists (class deps_desc *deps, rtx_insn *insn, int for_read,
1756 : int for_write)
1757 : {
1758 9682174 : if (for_write)
1759 : {
1760 9264365 : add_dependence_list_and_free (deps, insn, &deps->pending_read_insns,
1761 : 1, REG_DEP_ANTI, true);
1762 9264365 : if (!deps->readonly)
1763 : {
1764 9263235 : free_EXPR_LIST_list (&deps->pending_read_mems);
1765 9263235 : deps->pending_read_list_length = 0;
1766 : }
1767 : }
1768 :
1769 9702313 : add_dependence_list_and_free (deps, insn, &deps->pending_write_insns, 1,
1770 : for_read ? REG_DEP_ANTI : REG_DEP_OUTPUT,
1771 : true);
1772 :
1773 9682174 : add_dependence_list_and_free (deps, insn,
1774 : &deps->last_pending_memory_flush, 1,
1775 : for_read ? REG_DEP_ANTI : REG_DEP_OUTPUT,
1776 : true);
1777 :
1778 9682174 : add_dependence_list_and_free (deps, insn, &deps->pending_jump_insns, 1,
1779 : REG_DEP_ANTI, true);
1780 :
1781 9682174 : if (DEBUG_INSN_P (insn))
1782 : {
1783 0 : if (for_write)
1784 0 : free_INSN_LIST_list (&deps->pending_read_insns);
1785 0 : free_INSN_LIST_list (&deps->pending_write_insns);
1786 0 : free_INSN_LIST_list (&deps->last_pending_memory_flush);
1787 0 : free_INSN_LIST_list (&deps->pending_jump_insns);
1788 : }
1789 :
1790 9682174 : if (!deps->readonly)
1791 : {
1792 9681001 : free_EXPR_LIST_list (&deps->pending_write_mems);
1793 9681001 : deps->pending_write_list_length = 0;
1794 :
1795 9681001 : deps->last_pending_memory_flush = alloc_INSN_LIST (insn, NULL_RTX);
1796 9681001 : deps->pending_flush_length = 1;
1797 : }
1798 9682174 : mark_as_hard = false;
1799 9682174 : }
1800 :
1801 : /* Instruction which dependencies we are analyzing. */
1802 : static rtx_insn *cur_insn = NULL;
1803 :
1804 : /* Implement hooks for haifa scheduler. */
1805 :
1806 : static void
1807 120406897 : haifa_start_insn (rtx_insn *insn)
1808 : {
1809 120406897 : gcc_assert (insn && !cur_insn);
1810 :
1811 120406897 : cur_insn = insn;
1812 120406897 : }
1813 :
1814 : static void
1815 120406897 : haifa_finish_insn (void)
1816 : {
1817 120406897 : cur_insn = NULL;
1818 120406897 : }
1819 :
1820 : void
1821 39447762 : haifa_note_reg_set (int regno)
1822 : {
1823 39447762 : SET_REGNO_REG_SET (reg_pending_sets, regno);
1824 39447762 : }
1825 :
1826 : void
1827 11528978 : haifa_note_reg_clobber (int regno)
1828 : {
1829 11528978 : SET_REGNO_REG_SET (reg_pending_clobbers, regno);
1830 11528978 : }
1831 :
1832 : void
1833 82527274 : haifa_note_reg_use (int regno)
1834 : {
1835 82527274 : SET_REGNO_REG_SET (reg_pending_uses, regno);
1836 82527274 : }
1837 :
1838 : static void
1839 32433374 : haifa_note_mem_dep (rtx mem, rtx pending_mem, rtx_insn *pending_insn, ds_t ds)
1840 : {
1841 32433374 : if (!(ds & SPECULATIVE))
1842 : {
1843 : mem = NULL_RTX;
1844 : pending_mem = NULL_RTX;
1845 : }
1846 : else
1847 0 : gcc_assert (ds & BEGIN_DATA);
1848 :
1849 32433374 : {
1850 32433374 : dep_def _dep, *dep = &_dep;
1851 :
1852 32433374 : init_dep_1 (dep, pending_insn, cur_insn, ds_to_dt (ds),
1853 32433374 : current_sched_info->flags & USE_DEPS_LIST ? ds : 0);
1854 32433374 : DEP_NONREG (dep) = 1;
1855 32433374 : maybe_add_or_update_dep_1 (dep, false, pending_mem, mem);
1856 : }
1857 :
1858 32433374 : }
1859 :
1860 : static void
1861 623982501 : haifa_note_dep (rtx_insn *elem, ds_t ds)
1862 : {
1863 623982501 : dep_def _dep;
1864 623982501 : dep_t dep = &_dep;
1865 :
1866 623982501 : init_dep (dep, elem, cur_insn, ds_to_dt (ds));
1867 623982501 : if (mark_as_hard)
1868 307339896 : DEP_NONREG (dep) = 1;
1869 623982501 : maybe_add_or_update_dep_1 (dep, false, NULL_RTX, NULL_RTX);
1870 623982501 : }
1871 :
1872 : static void
1873 82547064 : note_reg_use (int r)
1874 : {
1875 0 : if (sched_deps_info->note_reg_use)
1876 82547064 : sched_deps_info->note_reg_use (r);
1877 0 : }
1878 :
1879 : static void
1880 39464657 : note_reg_set (int r)
1881 : {
1882 0 : if (sched_deps_info->note_reg_set)
1883 39464657 : sched_deps_info->note_reg_set (r);
1884 0 : }
1885 :
1886 : static void
1887 11530563 : note_reg_clobber (int r)
1888 : {
1889 0 : if (sched_deps_info->note_reg_clobber)
1890 11530563 : sched_deps_info->note_reg_clobber (r);
1891 0 : }
1892 :
1893 : static void
1894 32438179 : note_mem_dep (rtx m1, rtx m2, rtx_insn *e, ds_t ds)
1895 : {
1896 17512820 : if (sched_deps_info->note_mem_dep)
1897 32436864 : sched_deps_info->note_mem_dep (m1, m2, e, ds);
1898 0 : }
1899 :
1900 : static void
1901 624022891 : note_dep (rtx_insn *e, ds_t ds)
1902 : {
1903 0 : if (sched_deps_info->note_dep)
1904 624009122 : sched_deps_info->note_dep (e, ds);
1905 0 : }
1906 :
1907 : /* Return corresponding to DS reg_note. */
1908 : enum reg_note
1909 656447298 : ds_to_dt (ds_t ds)
1910 : {
1911 656447298 : if (ds & DEP_TRUE)
1912 : return REG_DEP_TRUE;
1913 533438590 : else if (ds & DEP_OUTPUT)
1914 : return REG_DEP_OUTPUT;
1915 453197167 : else if (ds & DEP_ANTI)
1916 : return REG_DEP_ANTI;
1917 : else
1918 : {
1919 0 : gcc_assert (ds & DEP_CONTROL);
1920 : return REG_DEP_CONTROL;
1921 : }
1922 : }
1923 :
1924 :
1925 :
1926 : /* Functions for computation of info needed for register pressure
1927 : sensitive insn scheduling. */
1928 :
1929 :
1930 : /* Allocate and return reg_use_data structure for REGNO and INSN. */
1931 : static struct reg_use_data *
1932 2490 : create_insn_reg_use (int regno, rtx_insn *insn)
1933 : {
1934 2490 : struct reg_use_data *use;
1935 :
1936 2490 : use = (struct reg_use_data *) xmalloc (sizeof (struct reg_use_data));
1937 2490 : use->regno = regno;
1938 2490 : use->insn = insn;
1939 2490 : use->next_insn_use = INSN_REG_USE_LIST (insn);
1940 2490 : INSN_REG_USE_LIST (insn) = use;
1941 2490 : return use;
1942 : }
1943 :
1944 : /* Allocate reg_set_data structure for REGNO and INSN. */
1945 : static void
1946 2324 : create_insn_reg_set (int regno, rtx insn)
1947 : {
1948 2324 : struct reg_set_data *set;
1949 :
1950 2324 : set = (struct reg_set_data *) xmalloc (sizeof (struct reg_set_data));
1951 2324 : set->regno = regno;
1952 2324 : set->insn = insn;
1953 2324 : set->next_insn_set = INSN_REG_SET_LIST (insn);
1954 2324 : INSN_REG_SET_LIST (insn) = set;
1955 2324 : }
1956 :
1957 : /* Set up insn register uses for INSN and dependency context DEPS. */
1958 : static void
1959 5263 : setup_insn_reg_uses (class deps_desc *deps, rtx_insn *insn)
1960 : {
1961 5263 : unsigned i;
1962 5263 : reg_set_iterator rsi;
1963 5263 : struct reg_use_data *use, *use2, *next;
1964 5263 : struct deps_reg *reg_last;
1965 :
1966 9931 : EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i, rsi)
1967 : {
1968 5683 : if (i < FIRST_PSEUDO_REGISTER
1969 4668 : && TEST_HARD_REG_BIT (ira_no_alloc_regs, i))
1970 1015 : continue;
1971 :
1972 3653 : if (find_regno_note (insn, REG_DEAD, i) == NULL_RTX
1973 1768 : && ! REGNO_REG_SET_P (reg_pending_sets, i)
1974 5138 : && ! REGNO_REG_SET_P (reg_pending_clobbers, i))
1975 : /* Ignore use which is not dying. */
1976 1485 : continue;
1977 :
1978 2168 : use = create_insn_reg_use (i, insn);
1979 2168 : use->next_regno_use = use;
1980 2168 : reg_last = &deps->reg_last[i];
1981 :
1982 : /* Create the cycle list of uses. */
1983 2490 : for (rtx_insn_list *list = reg_last->uses; list; list = list->next ())
1984 : {
1985 322 : use2 = create_insn_reg_use (i, list->insn ());
1986 322 : next = use->next_regno_use;
1987 322 : use->next_regno_use = use2;
1988 322 : use2->next_regno_use = next;
1989 : }
1990 : }
1991 5263 : }
1992 :
1993 : /* Register pressure info for the currently processed insn. */
1994 : static struct reg_pressure_data reg_pressure_info[N_REG_CLASSES];
1995 :
1996 : /* Return TRUE if INSN has the use structure for REGNO. */
1997 : static bool
1998 2324 : insn_use_p (rtx insn, int regno)
1999 : {
2000 2324 : struct reg_use_data *use;
2001 :
2002 3364 : for (use = INSN_REG_USE_LIST (insn); use != NULL; use = use->next_insn_use)
2003 1288 : if (use->regno == regno)
2004 : return true;
2005 : return false;
2006 : }
2007 :
2008 : /* Update the register pressure info after birth of pseudo register REGNO
2009 : in INSN. Arguments CLOBBER_P and UNUSED_P say correspondingly that
2010 : the register is in clobber or unused after the insn. */
2011 : static void
2012 1714 : mark_insn_pseudo_birth (rtx insn, int regno, bool clobber_p, bool unused_p)
2013 : {
2014 1714 : int incr, new_incr;
2015 1714 : enum reg_class cl;
2016 :
2017 1714 : gcc_assert (regno >= FIRST_PSEUDO_REGISTER);
2018 1714 : cl = sched_regno_pressure_class[regno];
2019 1714 : if (cl != NO_REGS)
2020 : {
2021 1707 : incr = ira_reg_class_max_nregs[cl][PSEUDO_REGNO_MODE (regno)];
2022 1707 : if (clobber_p)
2023 : {
2024 3 : new_incr = reg_pressure_info[cl].clobber_increase + incr;
2025 3 : reg_pressure_info[cl].clobber_increase = new_incr;
2026 : }
2027 1704 : else if (unused_p)
2028 : {
2029 67 : new_incr = reg_pressure_info[cl].unused_set_increase + incr;
2030 67 : reg_pressure_info[cl].unused_set_increase = new_incr;
2031 : }
2032 : else
2033 : {
2034 1637 : new_incr = reg_pressure_info[cl].set_increase + incr;
2035 1637 : reg_pressure_info[cl].set_increase = new_incr;
2036 1637 : if (! insn_use_p (insn, regno))
2037 1433 : reg_pressure_info[cl].change += incr;
2038 1637 : create_insn_reg_set (regno, insn);
2039 : }
2040 1707 : gcc_assert (new_incr < (1 << INCREASE_BITS));
2041 : }
2042 1714 : }
2043 :
2044 : /* Like mark_insn_pseudo_regno_birth except that NREGS saying how many
2045 : hard registers involved in the birth. */
2046 : static void
2047 1628 : mark_insn_hard_regno_birth (rtx insn, int regno, int nregs,
2048 : bool clobber_p, bool unused_p)
2049 : {
2050 1628 : enum reg_class cl;
2051 1628 : int new_incr, last = regno + nregs;
2052 :
2053 3258 : while (regno < last)
2054 : {
2055 1630 : gcc_assert (regno < FIRST_PSEUDO_REGISTER);
2056 1630 : if (! TEST_HARD_REG_BIT (ira_no_alloc_regs, regno))
2057 : {
2058 749 : cl = sched_regno_pressure_class[regno];
2059 749 : if (cl != NO_REGS)
2060 : {
2061 749 : if (clobber_p)
2062 : {
2063 1 : new_incr = reg_pressure_info[cl].clobber_increase + 1;
2064 1 : reg_pressure_info[cl].clobber_increase = new_incr;
2065 : }
2066 748 : else if (unused_p)
2067 : {
2068 61 : new_incr = reg_pressure_info[cl].unused_set_increase + 1;
2069 61 : reg_pressure_info[cl].unused_set_increase = new_incr;
2070 : }
2071 : else
2072 : {
2073 687 : new_incr = reg_pressure_info[cl].set_increase + 1;
2074 687 : reg_pressure_info[cl].set_increase = new_incr;
2075 687 : if (! insn_use_p (insn, regno))
2076 643 : reg_pressure_info[cl].change += 1;
2077 687 : create_insn_reg_set (regno, insn);
2078 : }
2079 749 : gcc_assert (new_incr < (1 << INCREASE_BITS));
2080 : }
2081 : }
2082 1630 : regno++;
2083 : }
2084 1628 : }
2085 :
2086 : /* Update the register pressure info after birth of pseudo or hard
2087 : register REG in INSN. Arguments CLOBBER_P and UNUSED_P say
2088 : correspondingly that the register is in clobber or unused after the
2089 : insn. */
2090 : static void
2091 4197 : mark_insn_reg_birth (rtx insn, rtx reg, bool clobber_p, bool unused_p)
2092 : {
2093 4197 : int regno;
2094 :
2095 4197 : if (GET_CODE (reg) == SUBREG)
2096 0 : reg = SUBREG_REG (reg);
2097 :
2098 4197 : if (! REG_P (reg))
2099 : return;
2100 :
2101 3342 : regno = REGNO (reg);
2102 3342 : if (regno < FIRST_PSEUDO_REGISTER)
2103 1628 : mark_insn_hard_regno_birth (insn, regno, REG_NREGS (reg),
2104 : clobber_p, unused_p);
2105 : else
2106 1714 : mark_insn_pseudo_birth (insn, regno, clobber_p, unused_p);
2107 : }
2108 :
2109 : /* Update the register pressure info after death of pseudo register
2110 : REGNO. */
2111 : static void
2112 1208 : mark_pseudo_death (int regno)
2113 : {
2114 1208 : int incr;
2115 1208 : enum reg_class cl;
2116 :
2117 1208 : gcc_assert (regno >= FIRST_PSEUDO_REGISTER);
2118 1208 : cl = sched_regno_pressure_class[regno];
2119 1208 : if (cl != NO_REGS)
2120 : {
2121 1204 : incr = ira_reg_class_max_nregs[cl][PSEUDO_REGNO_MODE (regno)];
2122 1204 : reg_pressure_info[cl].change -= incr;
2123 : }
2124 1208 : }
2125 :
2126 : /* Like mark_pseudo_death except that NREGS saying how many hard
2127 : registers involved in the death. */
2128 : static void
2129 1082 : mark_hard_regno_death (int regno, int nregs)
2130 : {
2131 1082 : enum reg_class cl;
2132 1082 : int last = regno + nregs;
2133 :
2134 2164 : while (regno < last)
2135 : {
2136 1082 : gcc_assert (regno < FIRST_PSEUDO_REGISTER);
2137 1082 : if (! TEST_HARD_REG_BIT (ira_no_alloc_regs, regno))
2138 : {
2139 677 : cl = sched_regno_pressure_class[regno];
2140 677 : if (cl != NO_REGS)
2141 677 : reg_pressure_info[cl].change -= 1;
2142 : }
2143 1082 : regno++;
2144 : }
2145 1082 : }
2146 :
2147 : /* Update the register pressure info after death of pseudo or hard
2148 : register REG. */
2149 : static void
2150 2290 : mark_reg_death (rtx reg)
2151 : {
2152 2290 : int regno;
2153 :
2154 2290 : if (GET_CODE (reg) == SUBREG)
2155 0 : reg = SUBREG_REG (reg);
2156 :
2157 2290 : if (! REG_P (reg))
2158 : return;
2159 :
2160 2290 : regno = REGNO (reg);
2161 2290 : if (regno < FIRST_PSEUDO_REGISTER)
2162 1082 : mark_hard_regno_death (regno, REG_NREGS (reg));
2163 : else
2164 1208 : mark_pseudo_death (regno);
2165 : }
2166 :
2167 : /* Process SETTER of REG. DATA is an insn containing the setter. */
2168 : static void
2169 4197 : mark_insn_reg_store (rtx reg, const_rtx setter, void *data)
2170 : {
2171 4197 : if (setter != NULL_RTX && GET_CODE (setter) != SET)
2172 : return;
2173 3719 : mark_insn_reg_birth
2174 3719 : ((rtx) data, reg, false,
2175 3719 : find_reg_note ((const_rtx) data, REG_UNUSED, reg) != NULL_RTX);
2176 : }
2177 :
2178 : /* Like mark_insn_reg_store except notice just CLOBBERs; ignore SETs. */
2179 : static void
2180 4197 : mark_insn_reg_clobber (rtx reg, const_rtx setter, void *data)
2181 : {
2182 4197 : if (GET_CODE (setter) == CLOBBER)
2183 478 : mark_insn_reg_birth ((rtx) data, reg, true, false);
2184 4197 : }
2185 :
2186 : /* Set up reg pressure info related to INSN. */
2187 : void
2188 5263 : init_insn_reg_pressure_info (rtx_insn *insn)
2189 : {
2190 5263 : int i, len;
2191 5263 : enum reg_class cl;
2192 5263 : static struct reg_pressure_data *pressure_info;
2193 5263 : rtx link;
2194 :
2195 5263 : gcc_assert (sched_pressure != SCHED_PRESSURE_NONE);
2196 :
2197 5263 : if (! INSN_P (insn))
2198 : return;
2199 :
2200 26592 : for (i = 0; i < ira_pressure_classes_num; i++)
2201 : {
2202 21329 : cl = ira_pressure_classes[i];
2203 21329 : reg_pressure_info[cl].clobber_increase = 0;
2204 21329 : reg_pressure_info[cl].set_increase = 0;
2205 21329 : reg_pressure_info[cl].unused_set_increase = 0;
2206 21329 : reg_pressure_info[cl].change = 0;
2207 : }
2208 :
2209 5263 : note_stores (insn, mark_insn_reg_clobber, insn);
2210 :
2211 5263 : note_stores (insn, mark_insn_reg_store, insn);
2212 :
2213 5263 : if (AUTO_INC_DEC)
2214 : for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
2215 : if (REG_NOTE_KIND (link) == REG_INC)
2216 : mark_insn_reg_store (XEXP (link, 0), NULL_RTX, insn);
2217 :
2218 9224 : for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
2219 3961 : if (REG_NOTE_KIND (link) == REG_DEAD)
2220 2290 : mark_reg_death (XEXP (link, 0));
2221 :
2222 5263 : len = sizeof (struct reg_pressure_data) * ira_pressure_classes_num;
2223 5263 : pressure_info
2224 5263 : = INSN_REG_PRESSURE (insn) = (struct reg_pressure_data *) xmalloc (len);
2225 5263 : if (sched_pressure == SCHED_PRESSURE_WEIGHTED)
2226 5263 : INSN_MAX_REG_PRESSURE (insn) = (int *) xcalloc (ira_pressure_classes_num
2227 : * sizeof (int), 1);
2228 26592 : for (i = 0; i < ira_pressure_classes_num; i++)
2229 : {
2230 21329 : cl = ira_pressure_classes[i];
2231 21329 : pressure_info[i].clobber_increase
2232 21329 : = reg_pressure_info[cl].clobber_increase;
2233 21329 : pressure_info[i].set_increase = reg_pressure_info[cl].set_increase;
2234 21329 : pressure_info[i].unused_set_increase
2235 21329 : = reg_pressure_info[cl].unused_set_increase;
2236 21329 : pressure_info[i].change = reg_pressure_info[cl].change;
2237 : }
2238 : }
2239 :
2240 :
2241 :
2242 :
2243 : /* Internal variable for sched_analyze_[12] () functions.
2244 : If it is nonzero, this means that sched_analyze_[12] looks
2245 : at the most toplevel SET. */
2246 : static bool can_start_lhs_rhs_p;
2247 :
2248 : /* Extend reg info for the deps context DEPS given that
2249 : we have just generated a register numbered REGNO. */
2250 : static void
2251 921 : extend_deps_reg_info (class deps_desc *deps, int regno)
2252 : {
2253 921 : int max_regno = regno + 1;
2254 :
2255 921 : gcc_assert (!reload_completed);
2256 :
2257 : /* In a readonly context, it would not hurt to extend info,
2258 : but it should not be needed. */
2259 921 : if (reload_completed && deps->readonly)
2260 : {
2261 : deps->max_reg = max_regno;
2262 : return;
2263 : }
2264 :
2265 921 : if (max_regno > deps->max_reg)
2266 : {
2267 183 : deps->reg_last = XRESIZEVEC (struct deps_reg, deps->reg_last,
2268 : max_regno);
2269 183 : memset (&deps->reg_last[deps->max_reg],
2270 183 : 0, (max_regno - deps->max_reg)
2271 : * sizeof (struct deps_reg));
2272 183 : deps->max_reg = max_regno;
2273 : }
2274 : }
2275 :
2276 : /* Extends REG_INFO_P if needed. */
2277 : void
2278 133281500 : maybe_extend_reg_info_p (void)
2279 : {
2280 : /* Extend REG_INFO_P, if needed. */
2281 133281500 : if ((unsigned int)max_regno - 1 >= reg_info_p_size)
2282 : {
2283 15 : size_t new_reg_info_p_size = max_regno + 128;
2284 :
2285 15 : gcc_assert (!reload_completed && sel_sched_p ());
2286 :
2287 15 : reg_info_p = (struct reg_info_t *) xrecalloc (reg_info_p,
2288 : new_reg_info_p_size,
2289 : reg_info_p_size,
2290 : sizeof (*reg_info_p));
2291 15 : reg_info_p_size = new_reg_info_p_size;
2292 : }
2293 133281500 : }
2294 :
2295 : /* Analyze a single reference to register (reg:MODE REGNO) in INSN.
2296 : The type of the reference is specified by REF and can be SET,
2297 : CLOBBER, PRE_DEC, POST_DEC, PRE_INC, POST_INC or USE. */
2298 :
2299 : static void
2300 133281170 : sched_analyze_reg (class deps_desc *deps, int regno, machine_mode mode,
2301 : enum rtx_code ref, rtx_insn *insn)
2302 : {
2303 : /* We could emit new pseudos in renaming. Extend the reg structures. */
2304 51861 : if (!reload_completed && sel_sched_p ()
2305 133314186 : && (regno >= max_reg_num () - 1 || regno >= deps->max_reg))
2306 921 : extend_deps_reg_info (deps, regno);
2307 :
2308 133281170 : maybe_extend_reg_info_p ();
2309 :
2310 : /* A hard reg in a wide mode may really be multiple registers.
2311 : If so, mark all of them just like the first. */
2312 133281170 : if (regno < FIRST_PSEUDO_REGISTER)
2313 : {
2314 133241125 : int i = hard_regno_nregs (regno, mode);
2315 133241125 : if (ref == SET)
2316 : {
2317 78762434 : while (--i >= 0)
2318 78894058 : note_reg_set (regno + i);
2319 : }
2320 93925720 : else if (ref == USE)
2321 : {
2322 164920944 : while (--i >= 0)
2323 165049360 : note_reg_use (regno + i);
2324 : }
2325 : else
2326 : {
2327 23059986 : while (--i >= 0)
2328 23061060 : note_reg_clobber (regno + i);
2329 : }
2330 : }
2331 :
2332 : /* ??? Reload sometimes emits USEs and CLOBBERs of pseudos that
2333 : it does not reload. Ignore these as they have served their
2334 : purpose already. */
2335 40045 : else if (regno >= deps->max_reg)
2336 : {
2337 0 : enum rtx_code code = GET_CODE (PATTERN (insn));
2338 0 : gcc_assert (code == USE || code == CLOBBER);
2339 : }
2340 :
2341 : else
2342 : {
2343 40045 : if (ref == SET)
2344 17628 : note_reg_set (regno);
2345 22417 : else if (ref == USE)
2346 22384 : note_reg_use (regno);
2347 : else
2348 33 : note_reg_clobber (regno);
2349 :
2350 : /* Pseudos that are REG_EQUIV to something may be replaced
2351 : by that during reloading. We need only add dependencies for
2352 : the address in the REG_EQUIV note. */
2353 40045 : if (!reload_completed && get_reg_known_equiv_p (regno))
2354 : {
2355 0 : rtx t = get_reg_known_value (regno);
2356 0 : if (MEM_P (t))
2357 0 : sched_analyze_2 (deps, XEXP (t, 0), insn);
2358 : }
2359 :
2360 : /* Don't let it cross a call after scheduling if it doesn't
2361 : already cross one. */
2362 40045 : if (REG_N_CALLS_CROSSED (regno) == 0)
2363 : {
2364 36477 : if (!deps->readonly && ref == USE && !DEBUG_INSN_P (insn))
2365 8717 : deps->sched_before_next_call
2366 8717 : = alloc_INSN_LIST (insn, deps->sched_before_next_call);
2367 : else
2368 27760 : add_dependence_list (insn, deps->last_function_call, 1,
2369 : REG_DEP_ANTI, false);
2370 : }
2371 : }
2372 133281170 : }
2373 :
2374 : /* Analyze a single SET, CLOBBER, PRE_DEC, POST_DEC, PRE_INC or POST_INC
2375 : rtx, X, creating all dependencies generated by the write to the
2376 : destination of X, and reads of everything mentioned. */
2377 :
2378 : static void
2379 69666528 : sched_analyze_1 (class deps_desc *deps, rtx x, rtx_insn *insn)
2380 : {
2381 69666528 : rtx dest = XEXP (x, 0);
2382 69666528 : enum rtx_code code = GET_CODE (x);
2383 69666528 : bool cslr_p = can_start_lhs_rhs_p;
2384 :
2385 69666528 : can_start_lhs_rhs_p = false;
2386 :
2387 69666528 : gcc_assert (dest);
2388 69666528 : if (dest == 0)
2389 : return;
2390 :
2391 69666528 : if (cslr_p && sched_deps_info->start_lhs)
2392 16289 : sched_deps_info->start_lhs (dest);
2393 :
2394 69666528 : if (GET_CODE (dest) == PARALLEL)
2395 : {
2396 8010 : int i;
2397 :
2398 21720 : for (i = XVECLEN (dest, 0) - 1; i >= 0; i--)
2399 13710 : if (XEXP (XVECEXP (dest, 0, i), 0) != 0)
2400 13710 : sched_analyze_1 (deps,
2401 : gen_rtx_CLOBBER (VOIDmode,
2402 : XEXP (XVECEXP (dest, 0, i), 0)),
2403 : insn);
2404 :
2405 8010 : if (cslr_p && sched_deps_info->finish_lhs)
2406 0 : sched_deps_info->finish_lhs ();
2407 :
2408 8010 : if (code == SET)
2409 : {
2410 8010 : can_start_lhs_rhs_p = cslr_p;
2411 :
2412 8010 : sched_analyze_2 (deps, SET_SRC (x), insn);
2413 :
2414 8010 : can_start_lhs_rhs_p = false;
2415 : }
2416 :
2417 : return;
2418 : }
2419 :
2420 69706215 : while (GET_CODE (dest) == STRICT_LOW_PART || GET_CODE (dest) == SUBREG
2421 69706215 : || GET_CODE (dest) == ZERO_EXTRACT)
2422 : {
2423 47697 : if (GET_CODE (dest) == STRICT_LOW_PART
2424 11411 : || GET_CODE (dest) == ZERO_EXTRACT
2425 47726 : || read_modify_subreg_p (dest))
2426 : {
2427 : /* These both read and modify the result. We must handle
2428 : them as writes to get proper dependencies for following
2429 : instructions. We must handle them as reads to get proper
2430 : dependencies from this to previous instructions.
2431 : Thus we need to call sched_analyze_2. */
2432 :
2433 47668 : sched_analyze_2 (deps, XEXP (dest, 0), insn);
2434 : }
2435 47697 : if (GET_CODE (dest) == ZERO_EXTRACT)
2436 : {
2437 : /* The second and third arguments are values read by this insn. */
2438 11382 : sched_analyze_2 (deps, XEXP (dest, 1), insn);
2439 11382 : sched_analyze_2 (deps, XEXP (dest, 2), insn);
2440 : }
2441 47697 : dest = XEXP (dest, 0);
2442 : }
2443 :
2444 69658518 : if (REG_P (dest))
2445 : {
2446 50277751 : int regno = REGNO (dest);
2447 50277751 : machine_mode mode = GET_MODE (dest);
2448 :
2449 50277751 : sched_analyze_reg (deps, regno, mode, code, insn);
2450 :
2451 : #ifdef STACK_REGS
2452 : /* Treat all writes to a stack register as modifying the TOS. */
2453 50277751 : if (regno >= FIRST_STACK_REG && regno <= LAST_STACK_REG)
2454 : {
2455 : /* Avoid analyzing the same register twice. */
2456 320200 : if (regno != FIRST_STACK_REG)
2457 237645 : sched_analyze_reg (deps, FIRST_STACK_REG, mode, code, insn);
2458 :
2459 320200 : add_to_hard_reg_set (&implicit_reg_pending_uses, mode,
2460 : FIRST_STACK_REG);
2461 : }
2462 : #endif
2463 50277751 : if (!deps->readonly && regno == STACK_POINTER_REGNUM)
2464 : {
2465 : /* Please see PR114115. We have insn modifying memory on the stack
2466 : and not addressed by stack pointer and we have insn reserving the
2467 : stack space. If we move the insn modifying memory before insn
2468 : reserving the stack space, we can change memory out of the red
2469 : zone. Even worse, some optimizations (e.g. peephole) can add
2470 : insns using temporary stack slots before insn reserving the stack
2471 : space but after the insn modifying memory. This will corrupt the
2472 : modified memory. Therefore we treat insn changing the stack as
2473 : reading unknown memory. This will create anti-dependence. We
2474 : don't need to treat the insn as writing memory because GCC by
2475 : itself does not generate code reading undefined stack memory. */
2476 6477615 : if ((deps->pending_read_list_length + deps->pending_write_list_length)
2477 6477615 : >= param_max_pending_list_length
2478 2257 : && !DEBUG_INSN_P (insn))
2479 2257 : flush_pending_lists (deps, insn, true, true);
2480 6477615 : add_insn_mem_dependence (deps, true, insn, dest);
2481 : }
2482 : }
2483 19380767 : else if (MEM_P (dest))
2484 : {
2485 : /* Writing memory. */
2486 12683799 : rtx t = dest;
2487 :
2488 12683799 : if (sched_deps_info->use_cselib)
2489 : {
2490 370 : machine_mode address_mode = get_address_mode (dest);
2491 :
2492 370 : t = shallow_copy_rtx (dest);
2493 370 : cselib_lookup_from_insn (XEXP (t, 0), address_mode, 1,
2494 370 : GET_MODE (t), insn);
2495 370 : XEXP (t, 0)
2496 370 : = cselib_subst_to_values_from_insn (XEXP (t, 0), GET_MODE (t),
2497 : insn);
2498 : }
2499 12683799 : t = canon_rtx (t);
2500 :
2501 : /* Pending lists can't get larger with a readonly context. */
2502 12683799 : if (!deps->readonly
2503 12680768 : && ((deps->pending_read_list_length + deps->pending_write_list_length)
2504 12680768 : >= param_max_pending_list_length))
2505 : {
2506 : /* Flush all pending reads and writes to prevent the pending lists
2507 : from getting any larger. Insn scheduling runs too slowly when
2508 : these lists get long. When compiling GCC with itself,
2509 : this flush occurs 8 times for sparc, and 10 times for m88k using
2510 : the default value of 32. */
2511 20139 : flush_pending_lists (deps, insn, false, true);
2512 : }
2513 : else
2514 : {
2515 12663660 : rtx_insn_list *pending;
2516 12663660 : rtx_expr_list *pending_mem;
2517 :
2518 12663660 : pending = deps->pending_read_insns;
2519 12663660 : pending_mem = deps->pending_read_mems;
2520 39966282 : while (pending)
2521 : {
2522 27302622 : rtx mem = pending_mem->element ();
2523 27302622 : if (REG_P (mem)
2524 27302622 : || (anti_dependence (mem, t)
2525 4543263 : && ! sched_insns_conditions_mutex_p (insn, pending->insn ())))
2526 14390687 : note_mem_dep (t, mem, pending->insn (), DEP_ANTI);
2527 :
2528 27302622 : pending = pending->next ();
2529 27302622 : pending_mem = pending_mem->next ();
2530 : }
2531 :
2532 12663660 : pending = deps->pending_write_insns;
2533 12663660 : pending_mem = deps->pending_write_mems;
2534 43055153 : while (pending)
2535 : {
2536 30391493 : if (output_dependence (pending_mem->element (), t)
2537 38705337 : && ! sched_insns_conditions_mutex_p (insn, pending->insn ()))
2538 8313844 : note_mem_dep (t, pending_mem->element (),
2539 : pending->insn (),
2540 : DEP_OUTPUT);
2541 :
2542 30391493 : pending = pending->next ();
2543 30391493 : pending_mem = pending_mem-> next ();
2544 : }
2545 :
2546 12663660 : add_dependence_list (insn, deps->last_pending_memory_flush, 1,
2547 : REG_DEP_ANTI, true);
2548 12663660 : add_dependence_list (insn, deps->pending_jump_insns, 1,
2549 : REG_DEP_CONTROL, true);
2550 :
2551 12663660 : if (!deps->readonly)
2552 12660629 : add_insn_mem_dependence (deps, false, insn, dest);
2553 : }
2554 12683799 : sched_analyze_2 (deps, XEXP (dest, 0), insn);
2555 : }
2556 :
2557 69658518 : if (cslr_p && sched_deps_info->finish_lhs)
2558 16289 : sched_deps_info->finish_lhs ();
2559 :
2560 : /* Analyze reads. */
2561 69658518 : if (GET_CODE (x) == SET)
2562 : {
2563 57028669 : can_start_lhs_rhs_p = cslr_p;
2564 :
2565 57028669 : sched_analyze_2 (deps, SET_SRC (x), insn);
2566 :
2567 57028669 : can_start_lhs_rhs_p = false;
2568 : }
2569 : }
2570 :
2571 : /* Analyze the uses of memory and registers in rtx X in INSN. */
2572 : static void
2573 348115709 : sched_analyze_2 (class deps_desc *deps, rtx x, rtx_insn *insn)
2574 : {
2575 348115709 : int i;
2576 348115709 : int j;
2577 348115709 : enum rtx_code code;
2578 348115709 : const char *fmt;
2579 348115709 : bool cslr_p = can_start_lhs_rhs_p;
2580 :
2581 348115709 : can_start_lhs_rhs_p = false;
2582 :
2583 348115709 : gcc_assert (x);
2584 348115709 : if (x == 0)
2585 : return;
2586 :
2587 348115709 : if (cslr_p && sched_deps_info->start_rhs)
2588 16289 : sched_deps_info->start_rhs (x);
2589 :
2590 348115709 : code = GET_CODE (x);
2591 :
2592 348115709 : switch (code)
2593 : {
2594 87243372 : CASE_CONST_ANY:
2595 87243372 : case SYMBOL_REF:
2596 87243372 : case CONST:
2597 87243372 : case LABEL_REF:
2598 : /* Ignore constants. */
2599 87243372 : if (cslr_p && sched_deps_info->finish_rhs)
2600 1576 : sched_deps_info->finish_rhs ();
2601 :
2602 : return;
2603 :
2604 82176457 : case REG:
2605 82176457 : {
2606 82176457 : int regno = REGNO (x);
2607 82176457 : machine_mode mode = GET_MODE (x);
2608 :
2609 82176457 : sched_analyze_reg (deps, regno, mode, USE, insn);
2610 :
2611 : #ifdef STACK_REGS
2612 : /* Treat all reads of a stack register as modifying the TOS. */
2613 82176457 : if (regno >= FIRST_STACK_REG && regno <= LAST_STACK_REG)
2614 : {
2615 : /* Avoid analyzing the same register twice. */
2616 347126 : if (regno != FIRST_STACK_REG)
2617 242191 : sched_analyze_reg (deps, FIRST_STACK_REG, mode, USE, insn);
2618 347126 : sched_analyze_reg (deps, FIRST_STACK_REG, mode, SET, insn);
2619 : }
2620 : #endif
2621 :
2622 82176457 : if (cslr_p && sched_deps_info->finish_rhs)
2623 6438 : sched_deps_info->finish_rhs ();
2624 :
2625 : return;
2626 : }
2627 :
2628 19754456 : case MEM:
2629 19754456 : {
2630 19754456 : if (DEBUG_INSN_P (insn) && sched_deps_info->use_cselib)
2631 : {
2632 5 : machine_mode address_mode = get_address_mode (x);
2633 :
2634 5 : cselib_lookup_from_insn (XEXP (x, 0), address_mode, 1,
2635 5 : GET_MODE (x), insn);
2636 5 : }
2637 19754451 : else if (!DEBUG_INSN_P (insn))
2638 : {
2639 : /* Reading memory. */
2640 18043045 : rtx_insn_list *u;
2641 18043045 : rtx_insn_list *pending;
2642 18043045 : rtx_expr_list *pending_mem;
2643 18043045 : rtx t = x;
2644 :
2645 18043045 : if (sched_deps_info->use_cselib)
2646 : {
2647 362 : machine_mode address_mode = get_address_mode (t);
2648 :
2649 362 : t = shallow_copy_rtx (t);
2650 362 : cselib_lookup_from_insn (XEXP (t, 0), address_mode, 1,
2651 362 : GET_MODE (t), insn);
2652 362 : XEXP (t, 0)
2653 362 : = cselib_subst_to_values_from_insn (XEXP (t, 0), GET_MODE (t),
2654 : insn);
2655 : }
2656 :
2657 18043045 : t = canon_rtx (t);
2658 18043045 : pending = deps->pending_read_insns;
2659 18043045 : pending_mem = deps->pending_read_mems;
2660 63747444 : while (pending)
2661 : {
2662 45704399 : rtx mem = pending_mem->element ();
2663 32561183 : if (MEM_P (mem) && read_dependence (mem, t)
2664 46239071 : && ! sched_insns_conditions_mutex_p (insn, pending->insn ()))
2665 534672 : note_mem_dep (t, mem, pending->insn (), DEP_ANTI);
2666 :
2667 45704399 : pending = pending->next ();
2668 45704399 : pending_mem = pending_mem->next ();
2669 : }
2670 :
2671 18043045 : pending = deps->pending_write_insns;
2672 18043045 : pending_mem = deps->pending_write_mems;
2673 44161032 : while (pending)
2674 : {
2675 26117987 : if (true_dependence (pending_mem->element (), VOIDmode, t)
2676 35316963 : && ! sched_insns_conditions_mutex_p (insn,
2677 9198976 : pending->insn ()))
2678 9198976 : note_mem_dep (t, pending_mem->element (),
2679 : pending->insn (),
2680 9198976 : sched_deps_info->generate_spec_deps
2681 : ? BEGIN_DATA | DEP_TRUE : DEP_TRUE);
2682 :
2683 26117987 : pending = pending->next ();
2684 26117987 : pending_mem = pending_mem->next ();
2685 : }
2686 :
2687 23290649 : for (u = deps->last_pending_memory_flush; u; u = u->next ())
2688 5247604 : add_dependence (insn, u->insn (), REG_DEP_ANTI);
2689 :
2690 18058428 : for (u = deps->pending_jump_insns; u; u = u->next ())
2691 15383 : if (deps_may_trap_p (x))
2692 : {
2693 15049 : if ((sched_deps_info->generate_spec_deps)
2694 15049 : && sel_sched_p () && (spec_info->mask & BEGIN_CONTROL))
2695 : {
2696 0 : ds_t ds = set_dep_weak (DEP_ANTI, BEGIN_CONTROL,
2697 : MAX_DEP_WEAK);
2698 :
2699 15383 : note_dep (u->insn (), ds);
2700 : }
2701 : else
2702 15049 : add_dependence (insn, u->insn (), REG_DEP_CONTROL);
2703 : }
2704 : }
2705 :
2706 : /* Always add these dependencies to pending_reads, since
2707 : this insn may be followed by a write. */
2708 19754456 : if (!deps->readonly)
2709 : {
2710 19749756 : if ((deps->pending_read_list_length
2711 19749756 : + deps->pending_write_list_length)
2712 19749756 : >= param_max_pending_list_length
2713 27621 : && !DEBUG_INSN_P (insn))
2714 24323 : flush_pending_lists (deps, insn, true, true);
2715 19749756 : add_insn_mem_dependence (deps, true, insn, x);
2716 : }
2717 :
2718 19754456 : sched_analyze_2 (deps, XEXP (x, 0), insn);
2719 :
2720 19754456 : if (cslr_p && sched_deps_info->finish_rhs)
2721 1651 : sched_deps_info->finish_rhs ();
2722 :
2723 : return;
2724 : }
2725 :
2726 : /* Force pending stores to memory in case a trap handler needs them.
2727 : Also force pending loads from memory; loads and stores can segfault
2728 : and the signal handler won't be triggered if the trap insn was moved
2729 : above load or store insn. */
2730 5265 : case TRAP_IF:
2731 5265 : flush_pending_lists (deps, insn, true, true);
2732 5265 : break;
2733 :
2734 1821 : case PREFETCH:
2735 1821 : if (PREFETCH_SCHEDULE_BARRIER_P (x))
2736 0 : reg_pending_barrier = TRUE_BARRIER;
2737 : /* Prefetch insn contains addresses only. So if the prefetch
2738 : address has no registers, there will be no dependencies on
2739 : the prefetch insn. This is wrong with result code
2740 : correctness point of view as such prefetch can be moved below
2741 : a jump insn which usually generates MOVE_BARRIER preventing
2742 : to move insns containing registers or memories through the
2743 : barrier. It is also wrong with generated code performance
2744 : point of view as prefetch without dependencies will have a
2745 : tendency to be issued later instead of earlier. It is hard
2746 : to generate accurate dependencies for prefetch insns as
2747 : prefetch has only the start address but it is better to have
2748 : something than nothing. */
2749 1821 : if (!deps->readonly)
2750 : {
2751 1882 : rtx x = gen_rtx_MEM (Pmode, XEXP (PATTERN (insn), 0));
2752 1786 : if (sched_deps_info->use_cselib)
2753 2 : cselib_lookup_from_insn (x, Pmode, true, VOIDmode, insn);
2754 1786 : add_insn_mem_dependence (deps, true, insn, x);
2755 : }
2756 : break;
2757 :
2758 678051 : case UNSPEC_VOLATILE:
2759 678051 : flush_pending_lists (deps, insn, true, true);
2760 : /* FALLTHRU */
2761 :
2762 768616 : case ASM_OPERANDS:
2763 768616 : case ASM_INPUT:
2764 768616 : {
2765 : /* Traditional and volatile asm instructions must be considered to use
2766 : and clobber all hard registers, all pseudo-registers and all of
2767 : memory. So must TRAP_IF and UNSPEC_VOLATILE operations.
2768 :
2769 : Consider for instance a volatile asm that changes the fpu rounding
2770 : mode. An insn should not be moved across this even if it only uses
2771 : pseudo-regs because it might give an incorrectly rounded result. */
2772 88099 : if ((code != ASM_OPERANDS || MEM_VOLATILE_P (x))
2773 845308 : && !DEBUG_INSN_P (insn))
2774 757209 : reg_pending_barrier = TRUE_BARRIER;
2775 :
2776 : /* For all ASM_OPERANDS, we must traverse the vector of input operands.
2777 : We cannot just fall through here since then we would be confused
2778 : by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
2779 : traditional asms unlike their normal usage. */
2780 :
2781 768616 : if (code == ASM_OPERANDS)
2782 : {
2783 196006 : for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++)
2784 107907 : sched_analyze_2 (deps, ASM_OPERANDS_INPUT (x, j), insn);
2785 :
2786 88099 : if (cslr_p && sched_deps_info->finish_rhs)
2787 0 : sched_deps_info->finish_rhs ();
2788 :
2789 : return;
2790 : }
2791 : break;
2792 : }
2793 :
2794 3969732 : case PRE_DEC:
2795 3969732 : case POST_DEC:
2796 3969732 : case PRE_INC:
2797 3969732 : case POST_INC:
2798 : /* These both read and modify the result. We must handle them as writes
2799 : to get proper dependencies for following instructions. We must handle
2800 : them as reads to get proper dependencies from this to previous
2801 : instructions. Thus we need to pass them to both sched_analyze_1
2802 : and sched_analyze_2. We must call sched_analyze_2 first in order
2803 : to get the proper antecedent for the read. */
2804 3969732 : sched_analyze_2 (deps, XEXP (x, 0), insn);
2805 3969732 : sched_analyze_1 (deps, x, insn);
2806 :
2807 3969732 : if (cslr_p && sched_deps_info->finish_rhs)
2808 0 : sched_deps_info->finish_rhs ();
2809 :
2810 : return;
2811 :
2812 54475 : case POST_MODIFY:
2813 54475 : case PRE_MODIFY:
2814 : /* op0 = op0 + op1 */
2815 54475 : sched_analyze_2 (deps, XEXP (x, 0), insn);
2816 54475 : sched_analyze_2 (deps, XEXP (x, 1), insn);
2817 54475 : sched_analyze_1 (deps, x, insn);
2818 :
2819 54475 : if (cslr_p && sched_deps_info->finish_rhs)
2820 0 : sched_deps_info->finish_rhs ();
2821 :
2822 : return;
2823 :
2824 : default:
2825 : break;
2826 : }
2827 :
2828 : /* Other cases: walk the insn. */
2829 154829118 : fmt = GET_RTX_FORMAT (code);
2830 392367366 : for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2831 : {
2832 237538248 : if (fmt[i] == 'e')
2833 184746280 : sched_analyze_2 (deps, XEXP (x, i), insn);
2834 52791968 : else if (fmt[i] == 'E')
2835 3896444 : for (j = 0; j < XVECLEN (x, i); j++)
2836 2497347 : sched_analyze_2 (deps, XVECEXP (x, i, j), insn);
2837 : }
2838 :
2839 154829118 : if (cslr_p && sched_deps_info->finish_rhs)
2840 6624 : sched_deps_info->finish_rhs ();
2841 : }
2842 :
2843 : /* Try to group two fusible insns together to prevent scheduler
2844 : from scheduling them apart. */
2845 :
2846 : static void
2847 114261604 : sched_macro_fuse_insns (rtx_insn *insn)
2848 : {
2849 114261604 : rtx_insn *prev;
2850 : /* No target hook would return true for debug insn as any of the
2851 : hook operand, and with very large sequences of only debug insns
2852 : where on each we call sched_macro_fuse_insns it has quadratic
2853 : compile time complexity. */
2854 114261604 : if (DEBUG_INSN_P (insn))
2855 : return;
2856 61223058 : prev = prev_nonnote_nondebug_insn_bb (insn);
2857 61223058 : if (!prev)
2858 : return;
2859 :
2860 50765013 : if (any_condjump_p (insn))
2861 : {
2862 4785018 : unsigned int condreg1, condreg2;
2863 4785018 : rtx cc_reg_1;
2864 4785018 : if (targetm.fixed_condition_code_regs (&condreg1, &condreg2))
2865 : {
2866 4785018 : cc_reg_1 = gen_rtx_REG (CCmode, condreg1);
2867 4785018 : if (reg_referenced_p (cc_reg_1, PATTERN (insn))
2868 4785018 : && modified_in_p (cc_reg_1, prev))
2869 : {
2870 4661867 : if (targetm.sched.macro_fusion_pair_p (prev, insn))
2871 4230388 : SCHED_GROUP_P (insn) = 1;
2872 4661867 : return;
2873 : }
2874 : }
2875 : }
2876 :
2877 46103146 : if (single_set (insn) && single_set (prev))
2878 : {
2879 38825924 : if (targetm.sched.macro_fusion_pair_p (prev, insn))
2880 13 : SCHED_GROUP_P (insn) = 1;
2881 : }
2882 : }
2883 :
2884 : /* Get the implicit reg pending clobbers for INSN and save them in TEMP. */
2885 : void
2886 27776 : get_implicit_reg_pending_clobbers (HARD_REG_SET *temp, rtx_insn *insn)
2887 : {
2888 27776 : extract_insn (insn);
2889 27776 : preprocess_constraints (insn);
2890 27776 : alternative_mask preferred = get_preferred_alternatives (insn);
2891 27776 : ira_implicitly_set_insn_hard_regs (temp, preferred);
2892 27776 : *temp &= ~ira_no_alloc_regs;
2893 27776 : }
2894 :
2895 : /* Write DEPS' pending barriers into register I and return its entry, so that
2896 : callers can read and write it literally. A register outside reg_last_in_use
2897 : carries pending_barriers as the logical value of its sets list; see the
2898 : comment on the field. */
2899 :
2900 : struct deps_reg *
2901 521334027 : deps_reg_last (class deps_desc *deps, unsigned int i)
2902 : {
2903 521334027 : struct deps_reg *reg_last = &deps->reg_last[i];
2904 :
2905 521334027 : if (deps->pending_barriers
2906 521334027 : && !REGNO_REG_SET_P (&deps->reg_last_in_use, i))
2907 : {
2908 2312 : gcc_checking_assert (!deps->readonly);
2909 : /* Outside reg_last_in_use the entry must be empty: a barrier makes every
2910 : reg_last_dirty entry that still holds a list literal before pushing
2911 : itself onto pending_barriers. A live list here means a debug use or
2912 : control use escaped a barrier that the eager form would have
2913 : consumed. */
2914 2312 : gcc_checking_assert (!reg_last->sets && !reg_last->uses
2915 : && !reg_last->clobbers && !reg_last->implicit_sets
2916 : && !reg_last->control_uses
2917 : && reg_last->uses_length == 0
2918 : && reg_last->clobbers_length == 0);
2919 2312 : reg_last->sets = copy_INSN_LIST (deps->pending_barriers);
2920 2312 : SET_REGNO_REG_SET (&deps->reg_last_in_use, i);
2921 : }
2922 :
2923 521334027 : return reg_last;
2924 : }
2925 :
2926 : /* Analyze an INSN with pattern X to find all dependencies. */
2927 : static void
2928 114499811 : sched_analyze_insn (class deps_desc *deps, rtx x, rtx_insn *insn)
2929 : {
2930 114499811 : RTX_CODE code = GET_CODE (x);
2931 114499811 : rtx link;
2932 114499811 : unsigned i;
2933 114499811 : reg_set_iterator rsi;
2934 :
2935 114499811 : if (! reload_completed)
2936 : {
2937 26133 : HARD_REG_SET temp;
2938 26133 : get_implicit_reg_pending_clobbers (&temp, insn);
2939 52266 : implicit_reg_pending_clobbers |= temp;
2940 : }
2941 :
2942 228999622 : can_start_lhs_rhs_p = (NONJUMP_INSN_P (insn)
2943 114499811 : && code == SET);
2944 :
2945 : /* Group compare and branch insns for macro-fusion. */
2946 114499811 : if (!deps->readonly
2947 114470355 : && targetm.sched.macro_fusion_p
2948 228970166 : && targetm.sched.macro_fusion_p ())
2949 114261604 : sched_macro_fuse_insns (insn);
2950 :
2951 114499811 : if (may_trap_p (x))
2952 : /* Avoid moving trapping instructions across function calls that might
2953 : not always return. */
2954 8867951 : add_dependence_list (insn, deps->last_function_call_may_noreturn,
2955 : 1, REG_DEP_ANTI, true);
2956 :
2957 : /* We must avoid creating a situation in which two successors of the
2958 : current block have different unwind info after scheduling. If at any
2959 : point the two paths re-join this leads to incorrect unwind info. */
2960 : /* ??? There are certain situations involving a forced frame pointer in
2961 : which, with extra effort, we could fix up the unwind info at a later
2962 : CFG join. However, it seems better to notice these cases earlier
2963 : during prologue generation and avoid marking the frame pointer setup
2964 : as frame-related at all. */
2965 114499811 : if (RTX_FRAME_RELATED_P (insn))
2966 : {
2967 : /* Make sure prologue insn is scheduled before next jump. */
2968 3723763 : deps->sched_before_next_jump
2969 3723763 : = alloc_INSN_LIST (insn, deps->sched_before_next_jump);
2970 :
2971 : /* Make sure epilogue insn is scheduled after preceding jumps. */
2972 3723763 : add_dependence_list (insn, deps->last_pending_memory_flush, 1,
2973 : REG_DEP_ANTI, true);
2974 3723763 : add_dependence_list (insn, deps->pending_jump_insns, 1, REG_DEP_ANTI,
2975 : true);
2976 : }
2977 :
2978 114499811 : if (code == COND_EXEC)
2979 : {
2980 0 : sched_analyze_2 (deps, COND_EXEC_TEST (x), insn);
2981 :
2982 : /* ??? Should be recording conditions so we reduce the number of
2983 : false dependencies. */
2984 0 : x = COND_EXEC_CODE (x);
2985 0 : code = GET_CODE (x);
2986 : }
2987 114499811 : if (code == SET || code == CLOBBER)
2988 : {
2989 48665995 : sched_analyze_1 (deps, x, insn);
2990 :
2991 : /* Bare clobber insns are used for letting life analysis, reg-stack
2992 : and others know that a value is dead. Depend on the last call
2993 : instruction so that reg-stack won't get confused. */
2994 48665995 : if (code == CLOBBER)
2995 82416 : add_dependence_list (insn, deps->last_function_call, 1,
2996 : REG_DEP_OUTPUT, true);
2997 : }
2998 65833816 : else if (code == PARALLEL)
2999 : {
3000 25360860 : for (i = XVECLEN (x, 0); i--;)
3001 : {
3002 17446920 : rtx sub = XVECEXP (x, 0, i);
3003 17446920 : code = GET_CODE (sub);
3004 :
3005 17446920 : if (code == COND_EXEC)
3006 : {
3007 0 : sched_analyze_2 (deps, COND_EXEC_TEST (sub), insn);
3008 0 : sub = COND_EXEC_CODE (sub);
3009 0 : code = GET_CODE (sub);
3010 : }
3011 17446920 : else if (code == SET || code == CLOBBER)
3012 16962616 : sched_analyze_1 (deps, sub, insn);
3013 : else
3014 484304 : sched_analyze_2 (deps, sub, insn);
3015 : }
3016 : }
3017 : else
3018 57919876 : sched_analyze_2 (deps, x, insn);
3019 :
3020 : /* Mark registers CLOBBERED or used by called function. */
3021 114499811 : if (CALL_P (insn))
3022 : {
3023 13408921 : for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1))
3024 : {
3025 8804897 : if (GET_CODE (XEXP (link, 0)) == CLOBBER)
3026 0 : sched_analyze_1 (deps, XEXP (link, 0), insn);
3027 8804897 : else if (GET_CODE (XEXP (link, 0)) != SET)
3028 8735947 : sched_analyze_2 (deps, XEXP (link, 0), insn);
3029 : }
3030 : /* Don't schedule anything after a tail call, tail call needs
3031 : to use at least all call-saved registers. */
3032 4604024 : if (SIBLING_CALL_P (insn))
3033 129943 : reg_pending_barrier = TRUE_BARRIER;
3034 4474081 : else if (find_reg_note (insn, REG_SETJMP, NULL))
3035 757 : reg_pending_barrier = MOVE_BARRIER;
3036 : }
3037 :
3038 114499811 : if (JUMP_P (insn))
3039 : {
3040 7814709 : rtx_insn *next = next_nonnote_nondebug_insn (insn);
3041 : /* ??? For tablejumps, the barrier may appear not immediately after
3042 : the jump, but after a label and a jump_table_data insn. */
3043 8852141 : if (next && LABEL_P (next) && NEXT_INSN (next)
3044 8852156 : && JUMP_TABLE_DATA_P (NEXT_INSN (next)))
3045 1195 : next = NEXT_INSN (NEXT_INSN (next));
3046 7814709 : if (next && BARRIER_P (next))
3047 2910027 : reg_pending_barrier = MOVE_BARRIER;
3048 : else
3049 : {
3050 4904682 : rtx_insn_list *pending;
3051 4904682 : rtx_expr_list *pending_mem;
3052 :
3053 4904682 : if (sched_deps_info->compute_jump_reg_dependencies)
3054 : {
3055 4903164 : (*sched_deps_info->compute_jump_reg_dependencies)
3056 4903164 : (insn, reg_pending_control_uses);
3057 :
3058 : /* Make latency of jump equal to 0 by using anti-dependence. */
3059 4903325 : EXECUTE_IF_SET_IN_REG_SET (reg_pending_control_uses, 0, i, rsi)
3060 : {
3061 161 : struct deps_reg *reg_last = deps_reg_last (deps, i);
3062 161 : add_dependence_list (insn, reg_last->sets, 0, REG_DEP_ANTI,
3063 : false);
3064 161 : add_dependence_list (insn, reg_last->implicit_sets,
3065 : 0, REG_DEP_ANTI, false);
3066 161 : add_dependence_list (insn, reg_last->clobbers, 0,
3067 : REG_DEP_ANTI, false);
3068 : }
3069 : }
3070 :
3071 : /* All memory writes and volatile reads must happen before the
3072 : jump. Non-volatile reads must happen before the jump iff
3073 : the result is needed by the above register used mask. */
3074 :
3075 4904682 : pending = deps->pending_write_insns;
3076 4904682 : pending_mem = deps->pending_write_mems;
3077 7315611 : while (pending)
3078 : {
3079 2410929 : if (! sched_insns_conditions_mutex_p (insn, pending->insn ()))
3080 2410929 : add_dependence (insn, pending->insn (), REG_DEP_OUTPUT);
3081 2410929 : pending = pending->next ();
3082 2410929 : pending_mem = pending_mem->next ();
3083 : }
3084 :
3085 4904682 : pending = deps->pending_read_insns;
3086 4904682 : pending_mem = deps->pending_read_mems;
3087 11853083 : while (pending)
3088 : {
3089 6948401 : rtx mem = pending_mem->element ();
3090 6187074 : if (MEM_P (mem) && MEM_VOLATILE_P (mem)
3091 7272610 : && ! sched_insns_conditions_mutex_p (insn, pending->insn ()))
3092 324209 : add_dependence (insn, pending->insn (), REG_DEP_OUTPUT);
3093 6948401 : pending = pending->next ();
3094 6948401 : pending_mem = pending_mem->next ();
3095 : }
3096 :
3097 4904682 : add_dependence_list (insn, deps->last_pending_memory_flush, 1,
3098 : REG_DEP_ANTI, true);
3099 4904682 : add_dependence_list (insn, deps->pending_jump_insns, 1,
3100 : REG_DEP_ANTI, true);
3101 : }
3102 : }
3103 :
3104 : /* If this instruction can throw an exception, then moving it changes
3105 : where block boundaries fall. This is mighty confusing elsewhere.
3106 : Therefore, prevent such an instruction from being moved. Same for
3107 : non-jump instructions that define block boundaries.
3108 : ??? Unclear whether this is still necessary in EBB mode. If not,
3109 : add_branch_dependences should be adjusted for RGN mode instead. */
3110 12418733 : if (((CALL_P (insn) || JUMP_P (insn)) && can_throw_internal (insn))
3111 126408004 : || (NONJUMP_INSN_P (insn) && control_flow_insn_p (insn)))
3112 623124 : reg_pending_barrier = MOVE_BARRIER;
3113 :
3114 114499811 : if (sched_pressure != SCHED_PRESSURE_NONE)
3115 : {
3116 5263 : setup_insn_reg_uses (deps, insn);
3117 5263 : init_insn_reg_pressure_info (insn);
3118 : }
3119 :
3120 : /* Add register dependencies for insn. */
3121 114499811 : if (DEBUG_INSN_P (insn))
3122 : {
3123 53039392 : rtx_insn *prev = deps->last_debug_insn;
3124 53039392 : rtx_insn_list *u;
3125 :
3126 53039392 : if (!deps->readonly)
3127 53039283 : deps->last_debug_insn = insn;
3128 :
3129 53039392 : if (prev)
3130 49393850 : add_dependence (insn, prev, REG_DEP_ANTI);
3131 :
3132 53039392 : add_dependence_list (insn, deps->last_function_call, 1,
3133 : REG_DEP_ANTI, false);
3134 :
3135 53039392 : if (!sel_sched_p ())
3136 62669427 : for (u = deps->last_pending_memory_flush; u; u = u->next ())
3137 9630252 : add_dependence (insn, u->insn (), REG_DEP_ANTI);
3138 :
3139 63869616 : EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i, rsi)
3140 : {
3141 10830224 : struct deps_reg *reg_last = deps_reg_last (deps, i);
3142 10830224 : add_dependence_list (insn, reg_last->sets, 1, REG_DEP_ANTI, false);
3143 : /* There's no point in making REG_DEP_CONTROL dependencies for
3144 : debug insns. */
3145 10830224 : add_dependence_list (insn, reg_last->clobbers, 1, REG_DEP_ANTI,
3146 : false);
3147 :
3148 10830224 : if (!deps->readonly)
3149 10830224 : reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
3150 : }
3151 53039392 : if (!deps->readonly)
3152 53039283 : IOR_REG_SET (&deps->reg_last_dirty, reg_pending_uses);
3153 53039392 : CLEAR_REG_SET (reg_pending_uses);
3154 :
3155 : /* Quite often, a debug insn will refer to stuff in the
3156 : previous instruction, but the reason we want this
3157 : dependency here is to make sure the scheduler doesn't
3158 : gratuitously move a debug insn ahead. This could dirty
3159 : DF flags and cause additional analysis that wouldn't have
3160 : occurred in compilation without debug insns, and such
3161 : additional analysis can modify the generated code. */
3162 53039392 : prev = PREV_INSN (insn);
3163 :
3164 53039392 : if (prev && NONDEBUG_INSN_P (prev))
3165 4024933 : add_dependence (insn, prev, REG_DEP_ANTI);
3166 : }
3167 : else
3168 : {
3169 61460419 : regset_head set_or_clobbered;
3170 :
3171 131336327 : EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i, rsi)
3172 : {
3173 69875908 : struct deps_reg *reg_last = deps_reg_last (deps, i);
3174 69875908 : add_dependence_list (insn, reg_last->sets, 0, REG_DEP_TRUE, false);
3175 69875908 : add_dependence_list (insn, reg_last->implicit_sets, 0, REG_DEP_ANTI,
3176 : false);
3177 69875908 : add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_TRUE,
3178 : false);
3179 :
3180 69875908 : if (!deps->readonly)
3181 : {
3182 69862564 : reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
3183 69862564 : reg_last->uses_length++;
3184 : }
3185 : }
3186 :
3187 61460419 : hard_reg_set_iterator hrsi;
3188 76465073 : EXECUTE_IF_SET_IN_HARD_REG_SET (implicit_reg_pending_uses, 0, i, hrsi)
3189 : {
3190 15004654 : struct deps_reg *reg_last = deps_reg_last (deps, i);
3191 15004654 : add_dependence_list (insn, reg_last->sets, 0, REG_DEP_TRUE, false);
3192 15004654 : add_dependence_list (insn, reg_last->implicit_sets, 0,
3193 : REG_DEP_ANTI, false);
3194 15004654 : add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_TRUE,
3195 : false);
3196 :
3197 15004654 : if (!deps->readonly)
3198 : {
3199 15003469 : reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
3200 15003469 : reg_last->uses_length++;
3201 : }
3202 : }
3203 :
3204 61460419 : if (targetm.sched.exposed_pipeline)
3205 : {
3206 0 : INIT_REG_SET (&set_or_clobbered);
3207 0 : bitmap_ior (&set_or_clobbered, reg_pending_clobbers,
3208 : reg_pending_sets);
3209 0 : EXECUTE_IF_SET_IN_REG_SET (&set_or_clobbered, 0, i, rsi)
3210 : {
3211 0 : struct deps_reg *reg_last = &deps->reg_last[i];
3212 0 : rtx list;
3213 0 : for (list = reg_last->uses; list; list = XEXP (list, 1))
3214 : {
3215 0 : rtx other = XEXP (list, 0);
3216 0 : if (INSN_CACHED_COND (other) != const_true_rtx
3217 0 : && refers_to_regno_p (i, INSN_CACHED_COND (other)))
3218 0 : INSN_CACHED_COND (other) = const_true_rtx;
3219 : }
3220 : }
3221 : }
3222 :
3223 : /* If the current insn is conditional, we can't free any
3224 : of the lists. */
3225 61460419 : if (sched_has_condition_p (insn))
3226 : {
3227 4904193 : EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers, 0, i, rsi)
3228 : {
3229 0 : struct deps_reg *reg_last = deps_reg_last (deps, i);
3230 0 : add_dependence_list (insn, reg_last->sets, 0, REG_DEP_OUTPUT,
3231 : false);
3232 0 : add_dependence_list (insn, reg_last->implicit_sets, 0,
3233 : REG_DEP_ANTI, false);
3234 0 : add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI,
3235 : false);
3236 0 : add_dependence_list (insn, reg_last->control_uses, 0,
3237 : REG_DEP_CONTROL, false);
3238 :
3239 0 : if (!deps->readonly)
3240 : {
3241 0 : reg_last->clobbers
3242 0 : = alloc_INSN_LIST (insn, reg_last->clobbers);
3243 0 : reg_last->clobbers_length++;
3244 : }
3245 : }
3246 4904193 : EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets, 0, i, rsi)
3247 : {
3248 0 : struct deps_reg *reg_last = deps_reg_last (deps, i);
3249 0 : add_dependence_list (insn, reg_last->sets, 0, REG_DEP_OUTPUT,
3250 : false);
3251 0 : add_dependence_list (insn, reg_last->implicit_sets, 0,
3252 : REG_DEP_ANTI, false);
3253 0 : add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_OUTPUT,
3254 : false);
3255 0 : add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI,
3256 : false);
3257 0 : add_dependence_list (insn, reg_last->control_uses, 0,
3258 : REG_DEP_CONTROL, false);
3259 :
3260 0 : if (!deps->readonly)
3261 0 : reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
3262 : }
3263 : }
3264 : else
3265 : {
3266 442929816 : EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers, 0, i, rsi)
3267 : {
3268 386373590 : struct deps_reg *reg_last = deps_reg_last (deps, i);
3269 386373590 : if (reg_last->uses_length >= param_max_pending_list_length
3270 386370838 : || reg_last->clobbers_length >= param_max_pending_list_length)
3271 : {
3272 372369 : add_dependence_list_and_free (deps, insn, ®_last->sets, 0,
3273 : REG_DEP_OUTPUT, false);
3274 372369 : add_dependence_list_and_free (deps, insn,
3275 : ®_last->implicit_sets, 0,
3276 : REG_DEP_ANTI, false);
3277 372369 : add_dependence_list_and_free (deps, insn, ®_last->uses, 0,
3278 : REG_DEP_ANTI, false);
3279 372369 : add_dependence_list_and_free (deps, insn,
3280 : ®_last->control_uses, 0,
3281 : REG_DEP_ANTI, false);
3282 372369 : add_dependence_list_and_free (deps, insn,
3283 : ®_last->clobbers, 0,
3284 : REG_DEP_OUTPUT, false);
3285 :
3286 372369 : if (!deps->readonly)
3287 : {
3288 372368 : reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
3289 372368 : reg_last->clobbers_length = 0;
3290 372368 : reg_last->uses_length = 0;
3291 : }
3292 : }
3293 : else
3294 : {
3295 386001221 : add_dependence_list (insn, reg_last->sets, 0, REG_DEP_OUTPUT,
3296 : false);
3297 386001221 : add_dependence_list (insn, reg_last->implicit_sets, 0,
3298 : REG_DEP_ANTI, false);
3299 386001221 : add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI,
3300 : false);
3301 386001221 : add_dependence_list (insn, reg_last->control_uses, 0,
3302 : REG_DEP_CONTROL, false);
3303 : }
3304 :
3305 386373590 : if (!deps->readonly)
3306 : {
3307 386343943 : reg_last->clobbers_length++;
3308 386343943 : reg_last->clobbers
3309 386343943 : = alloc_INSN_LIST (insn, reg_last->clobbers);
3310 : }
3311 : }
3312 95788001 : EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets, 0, i, rsi)
3313 : {
3314 39231775 : struct deps_reg *reg_last = deps_reg_last (deps, i);
3315 :
3316 39231775 : add_dependence_list_and_free (deps, insn, ®_last->sets, 0,
3317 : REG_DEP_OUTPUT, false);
3318 39231775 : add_dependence_list_and_free (deps, insn,
3319 : ®_last->implicit_sets,
3320 : 0, REG_DEP_ANTI, false);
3321 39231775 : add_dependence_list_and_free (deps, insn, ®_last->clobbers, 0,
3322 : REG_DEP_OUTPUT, false);
3323 39231775 : add_dependence_list_and_free (deps, insn, ®_last->uses, 0,
3324 : REG_DEP_ANTI, false);
3325 39231775 : add_dependence_list (insn, reg_last->control_uses, 0,
3326 : REG_DEP_CONTROL, false);
3327 :
3328 39231775 : if (!deps->readonly)
3329 : {
3330 39223211 : reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
3331 39223211 : reg_last->uses_length = 0;
3332 39223211 : reg_last->clobbers_length = 0;
3333 : }
3334 : }
3335 : }
3336 61460419 : if (!deps->readonly)
3337 : {
3338 61431233 : EXECUTE_IF_SET_IN_REG_SET (reg_pending_control_uses, 0, i, rsi)
3339 : {
3340 161 : struct deps_reg *reg_last = &deps->reg_last[i];
3341 161 : reg_last->control_uses
3342 161 : = alloc_INSN_LIST (insn, reg_last->control_uses);
3343 : }
3344 61431072 : IOR_REG_SET (&deps->reg_last_dirty, reg_pending_control_uses);
3345 : }
3346 : }
3347 :
3348 114499811 : hard_reg_set_iterator hrsi;
3349 114501383 : EXECUTE_IF_SET_IN_HARD_REG_SET (implicit_reg_pending_clobbers, 0, i, hrsi)
3350 : {
3351 1572 : struct deps_reg *reg_last = deps_reg_last (deps, i);
3352 1572 : add_dependence_list (insn, reg_last->sets, 0, REG_DEP_ANTI, false);
3353 1572 : add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_ANTI, false);
3354 1572 : add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI, false);
3355 1572 : add_dependence_list (insn, reg_last->control_uses, 0, REG_DEP_ANTI,
3356 : false);
3357 :
3358 1572 : if (!deps->readonly)
3359 834 : reg_last->implicit_sets
3360 834 : = alloc_INSN_LIST (insn, reg_last->implicit_sets);
3361 : }
3362 :
3363 114499811 : if (!deps->readonly)
3364 : {
3365 114470355 : IOR_REG_SET (&deps->reg_last_in_use, reg_pending_uses);
3366 114470355 : IOR_REG_SET (&deps->reg_last_in_use, reg_pending_clobbers);
3367 114470355 : IOR_REG_SET (&deps->reg_last_in_use, reg_pending_sets);
3368 114470355 : IOR_REG_SET_HRS (&deps->reg_last_in_use,
3369 : implicit_reg_pending_uses
3370 : | implicit_reg_pending_clobbers);
3371 :
3372 : /* Set up the pending barrier found. */
3373 114470355 : deps->last_reg_pending_barrier = reg_pending_barrier;
3374 : }
3375 :
3376 114499811 : CLEAR_REG_SET (reg_pending_uses);
3377 114499811 : CLEAR_REG_SET (reg_pending_clobbers);
3378 114499811 : CLEAR_REG_SET (reg_pending_sets);
3379 114499811 : CLEAR_REG_SET (reg_pending_control_uses);
3380 457999244 : CLEAR_HARD_REG_SET (implicit_reg_pending_clobbers);
3381 114499811 : CLEAR_HARD_REG_SET (implicit_reg_pending_uses);
3382 :
3383 : /* Add dependencies if a scheduling barrier was found. */
3384 114499811 : if (reg_pending_barrier)
3385 : {
3386 : /* In the case of barrier the most added dependencies are not
3387 : real, so we use anti-dependence here. */
3388 3534586 : enum reg_note barrier_dep = (reg_pending_barrier == TRUE_BARRIER
3389 4348113 : ? REG_DEP_TRUE : REG_DEP_ANTI);
3390 4348113 : bool cond_p = sched_has_condition_p (insn);
3391 : /* Recording the barrier once pays for itself when max_reg is
3392 : max_reg_num (), which init_deps uses before reload. After reload
3393 : max_reg is FIRST_PSEUDO_REGISTER and most entries are touched again
3394 : before the next barrier, so materialising on demand costs more than
3395 : writing them out. Selective scheduling re-analyses insns against a
3396 : readonly context that must not allocate, so it cannot materialise on
3397 : demand at all. Keep the eager form for both. */
3398 4348113 : bool eager_p = sel_sched_p () || reload_completed;
3399 : /* The pending barriers are the sets list of every register the loops
3400 : below skip, so their dependence belongs where the first skipped
3401 : register would have emitted it. Find that position while visiting
3402 : the materialised registers. */
3403 4348113 : unsigned next_reg = 0;
3404 4348113 : bool emitted = deps->pending_barriers == NULL;
3405 :
3406 4348113 : if (cond_p)
3407 : {
3408 0 : EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
3409 : {
3410 0 : struct deps_reg *reg_last;
3411 :
3412 0 : if (!emitted && i != next_reg)
3413 : {
3414 0 : add_dependence_list (insn, deps->pending_barriers, 0,
3415 : barrier_dep, true);
3416 0 : emitted = true;
3417 : }
3418 0 : if (!emitted)
3419 0 : next_reg = i + 1;
3420 :
3421 0 : reg_last = &deps->reg_last[i];
3422 0 : add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI,
3423 : true);
3424 0 : add_dependence_list (insn, reg_last->sets, 0, barrier_dep, true);
3425 0 : add_dependence_list (insn, reg_last->implicit_sets, 0,
3426 : REG_DEP_ANTI, true);
3427 0 : add_dependence_list (insn, reg_last->clobbers, 0, barrier_dep,
3428 : true);
3429 :
3430 0 : if (!deps->readonly && !eager_p)
3431 0 : reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
3432 : }
3433 0 : if (!emitted && next_reg < (unsigned) deps->max_reg)
3434 0 : add_dependence_list (insn, deps->pending_barriers, 0, barrier_dep,
3435 : true);
3436 : }
3437 : else
3438 : {
3439 206031354 : EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
3440 : {
3441 201683241 : struct deps_reg *reg_last;
3442 :
3443 201683241 : if (!emitted && i != next_reg)
3444 : {
3445 207 : add_dependence_list_and_free (deps, insn,
3446 : &deps->pending_barriers, 0,
3447 : barrier_dep, true);
3448 207 : emitted = true;
3449 : }
3450 207 : if (!emitted)
3451 480 : next_reg = i + 1;
3452 :
3453 201683241 : reg_last = &deps->reg_last[i];
3454 201683241 : add_dependence_list_and_free (deps, insn, ®_last->uses, 0,
3455 : REG_DEP_ANTI, true);
3456 201683241 : add_dependence_list_and_free (deps, insn,
3457 : ®_last->control_uses, 0,
3458 : REG_DEP_CONTROL, true);
3459 201683241 : add_dependence_list_and_free (deps, insn, ®_last->sets, 0,
3460 : barrier_dep, true);
3461 201683241 : add_dependence_list_and_free (deps, insn,
3462 : ®_last->implicit_sets, 0,
3463 : REG_DEP_ANTI, true);
3464 201683241 : add_dependence_list_and_free (deps, insn, ®_last->clobbers, 0,
3465 : barrier_dep, true);
3466 :
3467 201683241 : if (!deps->readonly)
3468 : {
3469 201675468 : reg_last->uses_length = 0;
3470 201675468 : reg_last->clobbers_length = 0;
3471 : }
3472 : }
3473 4348113 : if (!emitted)
3474 : {
3475 19 : if (next_reg < (unsigned) deps->max_reg)
3476 15 : add_dependence_list_and_free (deps, insn,
3477 : &deps->pending_barriers, 0,
3478 : barrier_dep, true);
3479 : else
3480 : /* Every register has its own state, so no register carries the
3481 : global list. */
3482 4 : free_INSN_LIST_list (&deps->pending_barriers);
3483 : }
3484 : }
3485 :
3486 4348113 : if (!deps->readonly)
3487 : {
3488 4347456 : if (eager_p)
3489 : {
3490 : /* Write the barrier into every entry. pending_barriers then
3491 : stays empty and deps_reg_last never writes anything, so the
3492 : rest of this file behaves exactly as it did before. */
3493 404268511 : for (i = 0; i < (unsigned) deps->max_reg; i++)
3494 : {
3495 399921712 : struct deps_reg *reg_last = &deps->reg_last[i];
3496 399921712 : reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
3497 399921712 : SET_REGNO_REG_SET (&deps->reg_last_in_use, i);
3498 : }
3499 : }
3500 : else
3501 : {
3502 : /* Record the barrier once instead of writing it into every one
3503 : of the max_reg entries. deps_reg_last materialises it per
3504 : register on first touch. The loop above emptied every in-use
3505 : entry in the non-conditional case, so they can all go back to
3506 : carrying the pending list. */
3507 657 : if (!cond_p)
3508 657 : CLEAR_REG_SET (&deps->reg_last_in_use);
3509 :
3510 : /* An entry recorded only in reg_last_dirty holds a debug use or
3511 : a control use that nothing has consumed. The eager form
3512 : folded it into reg_last_in_use here so that the next barrier
3513 : consumed it, so give it this barrier and make it literal.
3514 : Otherwise the use survives into a later insn and depends on
3515 : that insn instead. An entry with no list left needs nothing:
3516 : carrying the pending list is what the eager form would have
3517 : written into it. */
3518 726 : EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_dirty, 0, i, rsi)
3519 : {
3520 69 : struct deps_reg *reg_last = &deps->reg_last[i];
3521 69 : if ((reg_last->uses || reg_last->control_uses)
3522 69 : && !REGNO_REG_SET_P (&deps->reg_last_in_use, i))
3523 : {
3524 0 : reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
3525 0 : SET_REGNO_REG_SET (&deps->reg_last_in_use, i);
3526 : }
3527 : }
3528 657 : CLEAR_REG_SET (&deps->reg_last_dirty);
3529 :
3530 657 : deps->pending_barriers
3531 657 : = alloc_INSN_LIST (insn, deps->pending_barriers);
3532 : }
3533 : }
3534 :
3535 : /* Don't flush pending lists on speculative checks for
3536 : selective scheduling. */
3537 4348113 : if (!sel_sched_p () || !sel_insn_is_speculation_check (insn))
3538 4348113 : flush_pending_lists (deps, insn, true, true);
3539 :
3540 4348113 : reg_pending_barrier = NOT_A_BARRIER;
3541 : }
3542 :
3543 : /* If a post-call group is still open, see if it should remain so.
3544 : This insn must be a simple move of a hard reg to a pseudo or
3545 : vice-versa.
3546 :
3547 : We must avoid moving these insns for correctness on targets
3548 : with small register classes, and for special registers like
3549 : PIC_OFFSET_TABLE_REGNUM. For simplicity, extend this to all
3550 : hard regs for all targets. */
3551 :
3552 114499811 : if (deps->in_post_call_group_p)
3553 : {
3554 1159 : rtx tmp, set = single_set (insn);
3555 1159 : int src_regno, dest_regno;
3556 :
3557 1159 : if (set == NULL)
3558 : {
3559 397 : if (DEBUG_INSN_P (insn))
3560 : /* We don't want to mark debug insns as part of the same
3561 : sched group. We know they really aren't, but if we use
3562 : debug insns to tell that a call group is over, we'll
3563 : get different code if debug insns are not there and
3564 : instructions that follow seem like they should be part
3565 : of the call group.
3566 :
3567 : Also, if we did, chain_to_prev_insn would move the
3568 : deps of the debug insn to the call insn, modifying
3569 : non-debug post-dependency counts of the debug insn
3570 : dependencies and otherwise messing with the scheduling
3571 : order.
3572 :
3573 : Instead, let such debug insns be scheduled freely, but
3574 : keep the call group open in case there are insns that
3575 : should be part of it afterwards. Since we grant debug
3576 : insns higher priority than even sched group insns, it
3577 : will all turn out all right. */
3578 332 : goto debug_dont_end_call_group;
3579 : else
3580 65 : goto end_call_group;
3581 : }
3582 :
3583 762 : tmp = SET_DEST (set);
3584 762 : if (GET_CODE (tmp) == SUBREG)
3585 0 : tmp = SUBREG_REG (tmp);
3586 762 : if (REG_P (tmp))
3587 699 : dest_regno = REGNO (tmp);
3588 : else
3589 63 : goto end_call_group;
3590 :
3591 699 : tmp = SET_SRC (set);
3592 699 : if (GET_CODE (tmp) == SUBREG)
3593 26 : tmp = SUBREG_REG (tmp);
3594 699 : if ((GET_CODE (tmp) == PLUS
3595 699 : || GET_CODE (tmp) == MINUS)
3596 89 : && REG_P (XEXP (tmp, 0))
3597 79 : && REGNO (XEXP (tmp, 0)) == STACK_POINTER_REGNUM
3598 721 : && dest_regno == STACK_POINTER_REGNUM)
3599 : src_regno = STACK_POINTER_REGNUM;
3600 677 : else if (REG_P (tmp))
3601 284 : src_regno = REGNO (tmp);
3602 : else
3603 393 : goto end_call_group;
3604 :
3605 306 : if (src_regno < FIRST_PSEUDO_REGISTER
3606 306 : || dest_regno < FIRST_PSEUDO_REGISTER)
3607 : {
3608 249 : if (!deps->readonly
3609 209 : && deps->in_post_call_group_p == post_call_initial)
3610 0 : deps->in_post_call_group_p = post_call;
3611 :
3612 249 : if (!sel_sched_p () || sched_emulate_haifa_p)
3613 : {
3614 197 : SCHED_GROUP_P (insn) = 1;
3615 197 : CANT_MOVE (insn) = 1;
3616 : }
3617 : }
3618 : else
3619 : {
3620 57 : end_call_group:
3621 578 : if (!deps->readonly)
3622 429 : deps->in_post_call_group_p = not_post_call;
3623 : }
3624 : }
3625 :
3626 114498652 : debug_dont_end_call_group:
3627 114499811 : if ((current_sched_info->flags & DO_SPECULATION)
3628 114499811 : && !sched_insn_is_legitimate_for_speculation_p (insn, 0))
3629 : /* INSN has an internal dependency (e.g. r14 = [r14]) and thus cannot
3630 : be speculated. */
3631 : {
3632 0 : if (sel_sched_p ())
3633 0 : sel_mark_hard_insn (insn);
3634 : else
3635 : {
3636 0 : sd_iterator_def sd_it;
3637 0 : dep_t dep;
3638 :
3639 0 : for (sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK);
3640 0 : sd_iterator_cond (&sd_it, &dep);)
3641 0 : change_spec_dep_to_hard (sd_it);
3642 : }
3643 : }
3644 :
3645 : /* We do not yet have code to adjust REG_ARGS_SIZE, therefore we must
3646 : honor their original ordering. */
3647 114499811 : if (find_reg_note (insn, REG_ARGS_SIZE, NULL))
3648 : {
3649 4035705 : if (deps->last_args_size)
3650 2741011 : add_dependence (insn, deps->last_args_size, REG_DEP_OUTPUT);
3651 4035705 : if (!deps->readonly)
3652 4035544 : deps->last_args_size = insn;
3653 : }
3654 :
3655 : /* We must not mix prologue and epilogue insns. See PR78029. */
3656 114499811 : if (prologue_contains (insn))
3657 : {
3658 3245390 : add_dependence_list (insn, deps->last_epilogue, true, REG_DEP_ANTI, true);
3659 3245390 : if (!deps->readonly)
3660 : {
3661 3244926 : if (deps->last_logue_was_epilogue)
3662 3 : free_INSN_LIST_list (&deps->last_prologue);
3663 3244926 : deps->last_prologue = alloc_INSN_LIST (insn, deps->last_prologue);
3664 3244926 : deps->last_logue_was_epilogue = false;
3665 : }
3666 : }
3667 :
3668 114499811 : if (epilogue_contains (insn))
3669 : {
3670 3165115 : add_dependence_list (insn, deps->last_prologue, true, REG_DEP_ANTI, true);
3671 3165115 : if (!deps->readonly)
3672 : {
3673 3164592 : if (!deps->last_logue_was_epilogue)
3674 1164437 : free_INSN_LIST_list (&deps->last_epilogue);
3675 3164592 : deps->last_epilogue = alloc_INSN_LIST (insn, deps->last_epilogue);
3676 3164592 : deps->last_logue_was_epilogue = true;
3677 : }
3678 : }
3679 114499811 : }
3680 :
3681 : /* Return TRUE if INSN might not always return normally (e.g. call exit,
3682 : longjmp, loop forever, ...). */
3683 : /* FIXME: Why can't this function just use flags_from_decl_or_type and
3684 : test for ECF_NORETURN? */
3685 : static bool
3686 4603526 : call_may_noreturn_p (rtx_insn *insn)
3687 : {
3688 4603526 : rtx call;
3689 :
3690 : /* const or pure calls that aren't looping will always return. */
3691 9069763 : if (RTL_CONST_OR_PURE_CALL_P (insn)
3692 4884003 : && !RTL_LOOPING_CONST_OR_PURE_CALL_P (insn))
3693 : return false;
3694 :
3695 4217908 : call = get_call_rtx_from (insn);
3696 4217908 : if (call && GET_CODE (XEXP (XEXP (call, 0), 0)) == SYMBOL_REF)
3697 : {
3698 4042840 : rtx symbol = XEXP (XEXP (call, 0), 0);
3699 4042840 : if (SYMBOL_REF_DECL (symbol)
3700 4042840 : && TREE_CODE (SYMBOL_REF_DECL (symbol)) == FUNCTION_DECL)
3701 : {
3702 3804635 : if (DECL_BUILT_IN_CLASS (SYMBOL_REF_DECL (symbol))
3703 3804635 : == BUILT_IN_NORMAL)
3704 554367 : switch (DECL_FUNCTION_CODE (SYMBOL_REF_DECL (symbol)))
3705 : {
3706 83706 : case BUILT_IN_BCMP:
3707 83706 : case BUILT_IN_BCOPY:
3708 83706 : case BUILT_IN_BZERO:
3709 83706 : case BUILT_IN_INDEX:
3710 83706 : case BUILT_IN_MEMCHR:
3711 83706 : case BUILT_IN_MEMCMP:
3712 83706 : case BUILT_IN_MEMCPY:
3713 83706 : case BUILT_IN_MEMMOVE:
3714 83706 : case BUILT_IN_MEMPCPY:
3715 83706 : case BUILT_IN_MEMSET:
3716 83706 : case BUILT_IN_RINDEX:
3717 83706 : case BUILT_IN_STPCPY:
3718 83706 : case BUILT_IN_STPNCPY:
3719 83706 : case BUILT_IN_STRCAT:
3720 83706 : case BUILT_IN_STRCHR:
3721 83706 : case BUILT_IN_STRCMP:
3722 83706 : case BUILT_IN_STRCPY:
3723 83706 : case BUILT_IN_STRCSPN:
3724 83706 : case BUILT_IN_STRLEN:
3725 83706 : case BUILT_IN_STRNCAT:
3726 83706 : case BUILT_IN_STRNCMP:
3727 83706 : case BUILT_IN_STRNCPY:
3728 83706 : case BUILT_IN_STRPBRK:
3729 83706 : case BUILT_IN_STRRCHR:
3730 83706 : case BUILT_IN_STRSPN:
3731 83706 : case BUILT_IN_STRSTR:
3732 : /* Assume certain string/memory builtins always return. */
3733 83706 : return false;
3734 : default:
3735 : break;
3736 : }
3737 : }
3738 : }
3739 :
3740 : /* For all other calls assume that they might not always return. */
3741 : return true;
3742 : }
3743 :
3744 : /* Return true if INSN should be made dependent on the previous instruction
3745 : group, and if all INSN's dependencies should be moved to the first
3746 : instruction of that group. */
3747 :
3748 : static bool
3749 56856387 : chain_to_prev_insn_p (rtx_insn *insn)
3750 : {
3751 : /* INSN forms a group with the previous instruction. */
3752 56856387 : if (SCHED_GROUP_P (insn))
3753 : return true;
3754 :
3755 : /* If the previous instruction clobbers a register R and this one sets
3756 : part of R, the clobber was added specifically to help us track the
3757 : liveness of R. There's no point scheduling the clobber and leaving
3758 : INSN behind, especially if we move the clobber to another block. */
3759 52625100 : rtx_insn *prev = prev_nonnote_nondebug_insn (insn);
3760 52625100 : if (prev
3761 51655430 : && INSN_P (prev)
3762 46756638 : && BLOCK_FOR_INSN (prev) == BLOCK_FOR_INSN (insn)
3763 95058026 : && GET_CODE (PATTERN (prev)) == CLOBBER)
3764 : {
3765 82288 : rtx x = XEXP (PATTERN (prev), 0);
3766 82288 : if (set_of (x, insn))
3767 42 : return true;
3768 : }
3769 :
3770 : return false;
3771 : }
3772 :
3773 : /* Analyze INSN with DEPS as a context. */
3774 : void
3775 120445077 : deps_analyze_insn (class deps_desc *deps, rtx_insn *insn)
3776 : {
3777 120445077 : if (sched_deps_info->start_insn)
3778 120425339 : sched_deps_info->start_insn (insn);
3779 :
3780 : /* Record the condition for this insn. */
3781 120445077 : if (NONDEBUG_INSN_P (insn))
3782 : {
3783 61460411 : rtx t;
3784 61460411 : sched_get_condition_with_rev (insn, NULL);
3785 61460411 : t = INSN_CACHED_COND (insn);
3786 61460411 : INSN_COND_DEPS (insn) = NULL;
3787 61460411 : if (reload_completed
3788 61436371 : && (current_sched_info->flags & DO_PREDICATION)
3789 0 : && COMPARISON_P (t)
3790 0 : && REG_P (XEXP (t, 0))
3791 0 : && CONSTANT_P (XEXP (t, 1)))
3792 : {
3793 0 : unsigned int regno;
3794 0 : int nregs;
3795 0 : rtx_insn_list *cond_deps = NULL;
3796 0 : t = XEXP (t, 0);
3797 0 : regno = REGNO (t);
3798 0 : nregs = REG_NREGS (t);
3799 0 : while (nregs-- > 0)
3800 : {
3801 0 : struct deps_reg *reg_last = &deps->reg_last[regno + nregs];
3802 0 : cond_deps = concat_INSN_LIST (reg_last->sets, cond_deps);
3803 0 : cond_deps = concat_INSN_LIST (reg_last->clobbers, cond_deps);
3804 0 : cond_deps = concat_INSN_LIST (reg_last->implicit_sets, cond_deps);
3805 : }
3806 0 : INSN_COND_DEPS (insn) = cond_deps;
3807 : }
3808 : }
3809 :
3810 120445077 : if (JUMP_P (insn))
3811 : {
3812 : /* Make each JUMP_INSN (but not a speculative check)
3813 : a scheduling barrier for memory references. */
3814 7814709 : if (!deps->readonly
3815 7816328 : && !(sel_sched_p ()
3816 1619 : && sel_insn_is_speculation_check (insn)))
3817 : {
3818 : /* Keep the list a reasonable size. */
3819 7813351 : if (deps->pending_flush_length++ >= param_max_pending_list_length)
3820 2 : flush_pending_lists (deps, insn, true, true);
3821 : else
3822 7813349 : deps->pending_jump_insns
3823 7813349 : = alloc_INSN_LIST (insn, deps->pending_jump_insns);
3824 : }
3825 :
3826 : /* For each insn which shouldn't cross a jump, add a dependence. */
3827 7814709 : add_dependence_list_and_free (deps, insn,
3828 : &deps->sched_before_next_jump, 1,
3829 : REG_DEP_ANTI, true);
3830 :
3831 7814709 : sched_analyze_insn (deps, PATTERN (insn), insn);
3832 : }
3833 112630368 : else if (NONJUMP_INSN_P (insn) || DEBUG_INSN_P (insn))
3834 : {
3835 102081070 : sched_analyze_insn (deps, PATTERN (insn), insn);
3836 : }
3837 10549298 : else if (CALL_P (insn))
3838 : {
3839 4604024 : int i;
3840 :
3841 4604024 : CANT_MOVE (insn) = 1;
3842 :
3843 4604024 : if (!reload_completed)
3844 : {
3845 : /* Scheduling across calls may increase register pressure by extending
3846 : live ranges of pseudos over the call. Worse, in presence of setjmp
3847 : it may incorrectly move up an assignment over a longjmp. */
3848 720 : reg_pending_barrier = MOVE_BARRIER;
3849 : }
3850 4603304 : else if (find_reg_note (insn, REG_SETJMP, NULL))
3851 : {
3852 : /* This is setjmp. Assume that all registers, not just
3853 : hard registers, may be clobbered by this call. */
3854 756 : reg_pending_barrier = MOVE_BARRIER;
3855 : }
3856 : else
3857 : {
3858 4602548 : function_abi callee_abi = insn_callee_abi (insn);
3859 432639512 : for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3860 : /* A call may read and modify global register variables. */
3861 423434416 : if (global_regs[i])
3862 : {
3863 118 : SET_REGNO_REG_SET (reg_pending_sets, i);
3864 118 : SET_HARD_REG_BIT (implicit_reg_pending_uses, i);
3865 : }
3866 : /* Other call-clobbered hard regs may be clobbered.
3867 : Since we only have a choice between 'might be clobbered'
3868 : and 'definitely not clobbered', we must include all
3869 : partly call-clobbered registers here. */
3870 423434298 : else if (callee_abi.clobbers_at_least_part_of_reg_p (i))
3871 374923413 : SET_REGNO_REG_SET (reg_pending_clobbers, i);
3872 : /* We don't know what set of fixed registers might be used
3873 : by the function, but it is certain that the stack pointer
3874 : is among them, but be conservative. */
3875 48510885 : else if (fixed_regs[i])
3876 14279795 : SET_HARD_REG_BIT (implicit_reg_pending_uses, i);
3877 : /* The frame pointer is normally not used by the function
3878 : itself, but by the debugger. */
3879 : /* ??? MIPS o32 is an exception. It uses the frame pointer
3880 : in the macro expansion of jal but does not represent this
3881 : fact in the call_insn rtl. */
3882 34231090 : else if (i == FRAME_POINTER_REGNUM
3883 34231090 : || (i == HARD_FRAME_POINTER_REGNUM
3884 4602534 : && (! reload_completed || frame_pointer_needed)))
3885 466738 : SET_HARD_REG_BIT (implicit_reg_pending_uses, i);
3886 : }
3887 :
3888 : /* For each insn which shouldn't cross a call, add a dependence
3889 : between that insn and this call insn. */
3890 4604024 : add_dependence_list_and_free (deps, insn,
3891 : &deps->sched_before_next_call, 1,
3892 : REG_DEP_ANTI, true);
3893 :
3894 4604024 : sched_analyze_insn (deps, PATTERN (insn), insn);
3895 :
3896 : /* If CALL would be in a sched group, then this will violate
3897 : convention that sched group insns have dependencies only on the
3898 : previous instruction.
3899 :
3900 : Of course one can say: "Hey! What about head of the sched group?"
3901 : And I will answer: "Basic principles (one dep per insn) are always
3902 : the same." */
3903 4604024 : gcc_assert (!SCHED_GROUP_P (insn));
3904 :
3905 : /* In the absence of interprocedural alias analysis, we must flush
3906 : all pending reads and writes, and start new dependencies starting
3907 : from here. But only flush writes for constant calls (which may
3908 : be passed a pointer to something we haven't written yet). */
3909 5021833 : flush_pending_lists (deps, insn, true, ! RTL_CONST_OR_PURE_CALL_P (insn));
3910 :
3911 4604024 : if (!deps->readonly)
3912 : {
3913 : /* Remember the last function call for limiting lifetimes. */
3914 4603526 : free_INSN_LIST_list (&deps->last_function_call);
3915 4603526 : deps->last_function_call = alloc_INSN_LIST (insn, NULL_RTX);
3916 :
3917 4603526 : if (call_may_noreturn_p (insn))
3918 : {
3919 : /* Remember the last function call that might not always return
3920 : normally for limiting moves of trapping insns. */
3921 4134202 : free_INSN_LIST_list (&deps->last_function_call_may_noreturn);
3922 4134202 : deps->last_function_call_may_noreturn
3923 4134202 : = alloc_INSN_LIST (insn, NULL_RTX);
3924 : }
3925 :
3926 : /* Before reload, begin a post-call group, so as to keep the
3927 : lifetimes of hard registers correct. */
3928 4603526 : if (! reload_completed)
3929 560 : deps->in_post_call_group_p = post_call;
3930 : }
3931 : }
3932 :
3933 120445077 : if (sched_deps_info->use_cselib)
3934 1535 : cselib_process_insn (insn);
3935 :
3936 120445077 : if (sched_deps_info->finish_insn)
3937 120425339 : sched_deps_info->finish_insn ();
3938 :
3939 : /* Fixup the dependencies in the sched group. */
3940 120445077 : if ((NONJUMP_INSN_P (insn) || JUMP_P (insn))
3941 56856387 : && chain_to_prev_insn_p (insn)
3942 124676406 : && !sel_sched_p ())
3943 4229958 : chain_to_prev_insn (insn);
3944 120445077 : }
3945 :
3946 : /* Initialize DEPS for the new block beginning with HEAD. */
3947 : void
3948 10524234 : deps_start_bb (class deps_desc *deps, rtx_insn *head)
3949 : {
3950 10524234 : gcc_assert (!deps->readonly);
3951 :
3952 : /* Before reload, if the previous block ended in a call, show that
3953 : we are inside a post-call group, so as to keep the lifetimes of
3954 : hard registers correct. */
3955 10524234 : if (! reload_completed && !LABEL_P (head))
3956 : {
3957 1502 : rtx_insn *insn = prev_nonnote_nondebug_insn (head);
3958 :
3959 1502 : if (insn && CALL_P (insn))
3960 5 : deps->in_post_call_group_p = post_call_initial;
3961 : }
3962 10524234 : }
3963 :
3964 : /* Analyze every insn between HEAD and TAIL inclusive, creating backward
3965 : dependencies for each insn. */
3966 : void
3967 10524234 : sched_analyze (class deps_desc *deps, rtx_insn *head, rtx_insn *tail)
3968 : {
3969 10524234 : rtx_insn *insn;
3970 :
3971 10524234 : if (sched_deps_info->use_cselib)
3972 173 : cselib_init (CSELIB_RECORD_MEMORY);
3973 :
3974 10524234 : deps_start_bb (deps, head);
3975 :
3976 120406897 : for (insn = head;; insn = NEXT_INSN (insn))
3977 : {
3978 120406897 : if (INSN_P (insn))
3979 : {
3980 : /* And initialize deps_lists. */
3981 114461623 : sd_init_insn (insn);
3982 : /* Clean up SCHED_GROUP_P which may be set by last
3983 : scheduler pass. */
3984 114461623 : if (SCHED_GROUP_P (insn))
3985 4210968 : SCHED_GROUP_P (insn) = 0;
3986 : }
3987 :
3988 120406897 : deps_analyze_insn (deps, insn);
3989 :
3990 120406897 : if (insn == tail)
3991 : {
3992 10524234 : if (sched_deps_info->use_cselib)
3993 173 : cselib_finish ();
3994 10524234 : return;
3995 : }
3996 109882663 : }
3997 : }
3998 :
3999 : /* Helper for sched_free_deps ().
4000 : Delete INSN's (RESOLVED_P) backward dependencies. */
4001 : static void
4002 114461623 : delete_dep_nodes_in_back_deps (rtx_insn *insn, bool resolved_p)
4003 : {
4004 114461623 : sd_iterator_def sd_it;
4005 114461623 : dep_t dep;
4006 114461623 : sd_list_types_def types;
4007 :
4008 114461623 : if (resolved_p)
4009 : types = SD_LIST_RES_BACK;
4010 : else
4011 4361 : types = SD_LIST_BACK;
4012 :
4013 114461623 : for (sd_it = sd_iterator_start (insn, types);
4014 331136938 : sd_iterator_cond (&sd_it, &dep);)
4015 : {
4016 216675315 : dep_link_t link = *sd_it.linkp;
4017 216675315 : dep_node_t node = DEP_LINK_NODE (link);
4018 216675315 : deps_list_t back_list;
4019 216675315 : deps_list_t forw_list;
4020 :
4021 216675315 : get_back_and_forw_lists (dep, resolved_p, &back_list, &forw_list);
4022 216675315 : remove_from_deps_list (link, back_list);
4023 216675315 : delete_dep_node (node);
4024 : }
4025 114461623 : }
4026 :
4027 : /* Delete (RESOLVED_P) dependencies between HEAD and TAIL together with
4028 : deps_lists. */
4029 : void
4030 10505436 : sched_free_deps (rtx_insn *head, rtx_insn *tail, bool resolved_p)
4031 : {
4032 10505436 : rtx_insn *insn;
4033 10505436 : rtx_insn *next_tail = NEXT_INSN (tail);
4034 :
4035 : /* We make two passes since some insns may be scheduled before their
4036 : dependencies are resolved. */
4037 136331412 : for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
4038 115320540 : if (INSN_P (insn) && INSN_LUID (insn) > 0)
4039 : {
4040 : /* Clear forward deps and leave the dep_nodes to the
4041 : corresponding back_deps list. */
4042 114461623 : if (resolved_p)
4043 114457262 : clear_deps_list (INSN_RESOLVED_FORW_DEPS (insn));
4044 : else
4045 4361 : clear_deps_list (INSN_FORW_DEPS (insn));
4046 : }
4047 125825976 : for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
4048 115320540 : if (INSN_P (insn) && INSN_LUID (insn) > 0)
4049 : {
4050 : /* Clear resolved back deps together with its dep_nodes. */
4051 114461623 : delete_dep_nodes_in_back_deps (insn, resolved_p);
4052 :
4053 114461623 : sd_finish_insn (insn);
4054 : }
4055 10505436 : }
4056 :
4057 : /* Pool of all-zero reg_last arrays. init_deps takes one and free_deps
4058 : returns it, so the O (MAX_REG) zeroing is paid once per pooled array rather
4059 : than once per basic block of every region. free_deps empties every entry
4060 : that was written, so an array coming back is already zero. Selective
4061 : scheduling is excluded: its remove_from_deps can drop a reg_last_in_use bit
4062 : while control_uses is still live, which would return a dirty array. */
4063 : static vec<struct deps_reg *> reg_last_pool;
4064 : static int reg_last_pool_max_reg;
4065 :
4066 : /* Return an all-zero array of MAX_REG deps_reg, from the pool if one of the
4067 : right size is available. */
4068 :
4069 : static struct deps_reg *
4070 10529253 : alloc_reg_last (int max_reg)
4071 : {
4072 10529253 : if (max_reg != reg_last_pool_max_reg)
4073 : {
4074 981725 : while (!reg_last_pool.is_empty ())
4075 4 : free (reg_last_pool.pop ());
4076 981721 : reg_last_pool_max_reg = max_reg;
4077 : }
4078 9547532 : else if (!reg_last_pool.is_empty ())
4079 9541797 : return reg_last_pool.pop ();
4080 :
4081 987456 : return XCNEWVEC (struct deps_reg, max_reg);
4082 : }
4083 :
4084 : /* Give REG_LAST, an array of MAX_REG deps_reg that free_deps has just
4085 : emptied, back to the pool. */
4086 :
4087 : static void
4088 10530754 : release_reg_last (struct deps_reg *reg_last, int max_reg)
4089 : {
4090 10530754 : if (reg_last == NULL)
4091 : return;
4092 :
4093 10529253 : if (sel_sched_p () || max_reg != reg_last_pool_max_reg)
4094 : {
4095 6009 : free (reg_last);
4096 6009 : return;
4097 : }
4098 :
4099 10523244 : if (flag_checking > 1)
4100 978746872 : for (int i = 0; i < max_reg; i++)
4101 968223745 : gcc_assert (reg_last[i].uses == NULL
4102 : && reg_last[i].sets == NULL
4103 : && reg_last[i].implicit_sets == NULL
4104 : && reg_last[i].control_uses == NULL
4105 : && reg_last[i].clobbers == NULL
4106 : && reg_last[i].uses_length == 0
4107 : && reg_last[i].clobbers_length == 0);
4108 :
4109 10523244 : reg_last_pool.safe_push (reg_last);
4110 : }
4111 :
4112 : /* Initialize variables for region data dependence analysis.
4113 : When LAZY_REG_LAST is true, do not allocate reg_last array
4114 : of class deps_desc immediately. */
4115 :
4116 : void
4117 10530730 : init_deps (class deps_desc *deps, bool lazy_reg_last)
4118 : {
4119 10530730 : int max_reg = (reload_completed ? FIRST_PSEUDO_REGISTER : max_reg_num ());
4120 :
4121 10530730 : deps->max_reg = max_reg;
4122 10530730 : if (lazy_reg_last)
4123 4814 : deps->reg_last = NULL;
4124 : else
4125 10525916 : deps->reg_last = alloc_reg_last (max_reg);
4126 10530730 : INIT_REG_SET (&deps->reg_last_in_use);
4127 10530730 : INIT_REG_SET (&deps->reg_last_dirty);
4128 :
4129 10530730 : deps->pending_read_insns = 0;
4130 10530730 : deps->pending_read_mems = 0;
4131 10530730 : deps->pending_write_insns = 0;
4132 10530730 : deps->pending_write_mems = 0;
4133 10530730 : deps->pending_jump_insns = 0;
4134 10530730 : deps->pending_read_list_length = 0;
4135 10530730 : deps->pending_write_list_length = 0;
4136 10530730 : deps->pending_flush_length = 0;
4137 10530730 : deps->last_pending_memory_flush = 0;
4138 10530730 : deps->last_function_call = 0;
4139 10530730 : deps->last_function_call_may_noreturn = 0;
4140 10530730 : deps->sched_before_next_call = 0;
4141 10530730 : deps->sched_before_next_jump = 0;
4142 10530730 : deps->in_post_call_group_p = not_post_call;
4143 10530730 : deps->last_debug_insn = 0;
4144 10530730 : deps->last_args_size = 0;
4145 10530730 : deps->last_prologue = 0;
4146 10530730 : deps->last_epilogue = 0;
4147 10530730 : deps->last_logue_was_epilogue = false;
4148 10530730 : deps->last_reg_pending_barrier = NOT_A_BARRIER;
4149 10530730 : deps->pending_barriers = 0;
4150 10530730 : deps->readonly = 0;
4151 10530730 : }
4152 :
4153 : /* Init only reg_last field of DEPS, which was not allocated before as
4154 : we inited DEPS lazily. */
4155 : void
4156 3313 : init_deps_reg_last (class deps_desc *deps)
4157 : {
4158 3313 : gcc_assert (deps && deps->max_reg > 0);
4159 3313 : gcc_assert (deps->reg_last == NULL);
4160 :
4161 3313 : deps->reg_last = alloc_reg_last (deps->max_reg);
4162 3313 : }
4163 :
4164 :
4165 : /* Free insn lists found in DEPS. */
4166 :
4167 : void
4168 10530754 : free_deps (class deps_desc *deps)
4169 : {
4170 10530754 : unsigned i;
4171 10530754 : reg_set_iterator rsi;
4172 :
4173 : /* We set max_reg to 0 when this context was already freed. */
4174 10530754 : if (deps->max_reg == 0)
4175 : {
4176 0 : gcc_assert (deps->reg_last == NULL);
4177 0 : return;
4178 : }
4179 10530754 : int max_reg = deps->max_reg;
4180 10530754 : deps->max_reg = 0;
4181 :
4182 10530754 : free_INSN_LIST_list (&deps->pending_read_insns);
4183 10530754 : free_EXPR_LIST_list (&deps->pending_read_mems);
4184 10530754 : free_INSN_LIST_list (&deps->pending_write_insns);
4185 10530754 : free_EXPR_LIST_list (&deps->pending_write_mems);
4186 10530754 : free_INSN_LIST_list (&deps->last_pending_memory_flush);
4187 10530754 : free_INSN_LIST_list (&deps->pending_barriers);
4188 :
4189 : /* Teardown only: fold the entries recorded solely in reg_last_dirty into the
4190 : live set, so that one loop releases everything. free_deps creates no
4191 : dependences, so this merge cannot add one. */
4192 10530754 : IOR_REG_SET (&deps->reg_last_in_use, &deps->reg_last_dirty);
4193 :
4194 : /* Without the EXECUTE_IF_SET, this loop is executed max_reg * nr_regions
4195 : times. For a testcase with 42000 regs and 8000 small basic blocks,
4196 : this loop accounted for nearly 60% (84 sec) of the total -O2 runtime. */
4197 528333791 : EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
4198 : {
4199 517803037 : struct deps_reg *reg_last = &deps->reg_last[i];
4200 517803037 : if (reg_last->uses)
4201 29450210 : free_INSN_LIST_list (®_last->uses);
4202 517803037 : if (reg_last->sets)
4203 363202297 : free_INSN_LIST_list (®_last->sets);
4204 517803037 : if (reg_last->implicit_sets)
4205 296 : free_INSN_LIST_list (®_last->implicit_sets);
4206 517803037 : if (reg_last->control_uses)
4207 118 : free_INSN_LIST_list (®_last->control_uses);
4208 517803037 : if (reg_last->clobbers)
4209 144779492 : free_INSN_LIST_list (®_last->clobbers);
4210 517803037 : reg_last->uses_length = 0;
4211 517803037 : reg_last->clobbers_length = 0;
4212 : }
4213 10530754 : CLEAR_REG_SET (&deps->reg_last_in_use);
4214 10530754 : CLEAR_REG_SET (&deps->reg_last_dirty);
4215 :
4216 : /* As we initialize reg_last lazily, it is possible that we didn't allocate
4217 : it at all. */
4218 10530754 : release_reg_last (deps->reg_last, max_reg);
4219 10530754 : deps->reg_last = NULL;
4220 :
4221 10530754 : deps = NULL;
4222 : }
4223 :
4224 : /* Remove INSN from dependence contexts DEPS. */
4225 : void
4226 2276 : remove_from_deps (class deps_desc *deps, rtx_insn *insn)
4227 : {
4228 2276 : int removed;
4229 2276 : unsigned i;
4230 2276 : reg_set_iterator rsi;
4231 :
4232 2276 : removed = remove_from_both_dependence_lists (insn, &deps->pending_read_insns,
4233 : &deps->pending_read_mems);
4234 2276 : if (!DEBUG_INSN_P (insn))
4235 2247 : deps->pending_read_list_length -= removed;
4236 2276 : removed = remove_from_both_dependence_lists (insn, &deps->pending_write_insns,
4237 : &deps->pending_write_mems);
4238 2276 : deps->pending_write_list_length -= removed;
4239 :
4240 2276 : removed = remove_from_dependence_list (insn, &deps->pending_jump_insns);
4241 2276 : deps->pending_flush_length -= removed;
4242 2276 : removed = remove_from_dependence_list (insn, &deps->last_pending_memory_flush);
4243 2276 : deps->pending_flush_length -= removed;
4244 :
4245 2276 : unsigned to_clear = -1U;
4246 52659 : EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
4247 : {
4248 50383 : if (to_clear != -1U)
4249 : {
4250 9195 : CLEAR_REGNO_REG_SET (&deps->reg_last_in_use, to_clear);
4251 9195 : to_clear = -1U;
4252 : }
4253 50383 : struct deps_reg *reg_last = &deps->reg_last[i];
4254 50383 : if (reg_last->uses)
4255 8015 : remove_from_dependence_list (insn, ®_last->uses);
4256 50383 : if (reg_last->sets)
4257 27631 : remove_from_dependence_list (insn, ®_last->sets);
4258 50383 : if (reg_last->implicit_sets)
4259 358 : remove_from_dependence_list (insn, ®_last->implicit_sets);
4260 50383 : if (reg_last->clobbers)
4261 17414 : remove_from_dependence_list (insn, ®_last->clobbers);
4262 50383 : if (!reg_last->uses && !reg_last->sets && !reg_last->implicit_sets
4263 23080 : && !reg_last->clobbers)
4264 50383 : to_clear = i;
4265 : }
4266 2276 : if (to_clear != -1U)
4267 355 : CLEAR_REGNO_REG_SET (&deps->reg_last_in_use, to_clear);
4268 :
4269 2276 : if (CALL_P (insn))
4270 : {
4271 72 : remove_from_dependence_list (insn, &deps->last_function_call);
4272 72 : remove_from_dependence_list (insn,
4273 : &deps->last_function_call_may_noreturn);
4274 : }
4275 2276 : remove_from_dependence_list (insn, &deps->sched_before_next_call);
4276 2276 : }
4277 :
4278 : /* Init deps data vector. */
4279 : static void
4280 986427 : init_deps_data_vector (void)
4281 : {
4282 986427 : int reserve = (sched_max_luid + 1 - h_d_i_d.length ());
4283 1969341 : if (reserve > 0 && ! h_d_i_d.space (reserve))
4284 982914 : h_d_i_d.safe_grow_cleared (3 * sched_max_luid / 2, true);
4285 986427 : }
4286 :
4287 : /* If it is profitable to use them, initialize or extend (depending on
4288 : GLOBAL_P) dependency data. */
4289 : void
4290 986427 : sched_deps_init (bool global_p)
4291 : {
4292 : /* Average number of insns in the basic block.
4293 : '+ 1' is used to make it nonzero. */
4294 986427 : int insns_in_block = sched_max_luid / n_basic_blocks_for_fn (cfun) + 1;
4295 :
4296 986427 : init_deps_data_vector ();
4297 :
4298 : /* We use another caching mechanism for selective scheduling, so
4299 : we don't use this one. */
4300 986427 : if (!sel_sched_p () && global_p && insns_in_block > 100 * 5)
4301 : {
4302 : /* ?!? We could save some memory by computing a per-region luid mapping
4303 : which could reduce both the number of vectors in the cache and the
4304 : size of each vector. Instead we just avoid the cache entirely unless
4305 : the average number of instructions in a basic block is very high. See
4306 : the comment before the declaration of true_dependency_cache for
4307 : what we consider "very high". */
4308 92 : cache_size = 0;
4309 92 : extend_dependency_caches (sched_max_luid, true);
4310 : }
4311 :
4312 986427 : if (global_p)
4313 : {
4314 981799 : dl_pool = new object_allocator<_deps_list> ("deps_list");
4315 : /* Allocate lists for one block at a time. */
4316 981799 : dn_pool = new object_allocator<_dep_node> ("dep_node");
4317 : /* Allocate nodes for one block at a time. */
4318 : }
4319 986427 : }
4320 :
4321 :
4322 : /* Create or extend (depending on CREATE_P) dependency caches to
4323 : size N. */
4324 : void
4325 92 : extend_dependency_caches (int n, bool create_p)
4326 : {
4327 92 : if (create_p || true_dependency_cache)
4328 : {
4329 92 : int i, luid = cache_size + n;
4330 :
4331 92 : true_dependency_cache = XRESIZEVEC (bitmap_head, true_dependency_cache,
4332 : luid);
4333 92 : output_dependency_cache = XRESIZEVEC (bitmap_head,
4334 : output_dependency_cache, luid);
4335 92 : anti_dependency_cache = XRESIZEVEC (bitmap_head, anti_dependency_cache,
4336 : luid);
4337 92 : control_dependency_cache = XRESIZEVEC (bitmap_head, control_dependency_cache,
4338 : luid);
4339 :
4340 92 : if (current_sched_info->flags & DO_SPECULATION)
4341 0 : spec_dependency_cache = XRESIZEVEC (bitmap_head, spec_dependency_cache,
4342 : luid);
4343 :
4344 631975 : for (i = cache_size; i < luid; i++)
4345 : {
4346 631883 : bitmap_initialize (&true_dependency_cache[i], 0);
4347 631883 : bitmap_initialize (&output_dependency_cache[i], 0);
4348 631883 : bitmap_initialize (&anti_dependency_cache[i], 0);
4349 631883 : bitmap_initialize (&control_dependency_cache[i], 0);
4350 :
4351 631883 : if (current_sched_info->flags & DO_SPECULATION)
4352 0 : bitmap_initialize (&spec_dependency_cache[i], 0);
4353 : }
4354 92 : cache_size = luid;
4355 : }
4356 92 : }
4357 :
4358 : /* Finalize dependency information for the whole function. */
4359 : void
4360 981811 : sched_deps_finish (void)
4361 : {
4362 981811 : gcc_assert (deps_pools_are_empty_p ());
4363 1963610 : delete dn_pool;
4364 1963610 : delete dl_pool;
4365 981811 : dn_pool = NULL;
4366 981811 : dl_pool = NULL;
4367 :
4368 981811 : h_d_i_d.release ();
4369 :
4370 2945065 : while (!reg_last_pool.is_empty ())
4371 981443 : free (reg_last_pool.pop ());
4372 981811 : reg_last_pool.release ();
4373 981811 : reg_last_pool_max_reg = 0;
4374 :
4375 981811 : if (true_dependency_cache)
4376 : {
4377 : int i;
4378 :
4379 631975 : for (i = 0; i < cache_size; i++)
4380 : {
4381 631883 : bitmap_clear (&true_dependency_cache[i]);
4382 631883 : bitmap_clear (&output_dependency_cache[i]);
4383 631883 : bitmap_clear (&anti_dependency_cache[i]);
4384 631883 : bitmap_clear (&control_dependency_cache[i]);
4385 :
4386 631883 : if (sched_deps_info->generate_spec_deps)
4387 0 : bitmap_clear (&spec_dependency_cache[i]);
4388 : }
4389 92 : free (true_dependency_cache);
4390 92 : true_dependency_cache = NULL;
4391 92 : free (output_dependency_cache);
4392 92 : output_dependency_cache = NULL;
4393 92 : free (anti_dependency_cache);
4394 92 : anti_dependency_cache = NULL;
4395 92 : free (control_dependency_cache);
4396 92 : control_dependency_cache = NULL;
4397 :
4398 92 : if (sched_deps_info->generate_spec_deps)
4399 : {
4400 0 : free (spec_dependency_cache);
4401 0 : spec_dependency_cache = NULL;
4402 : }
4403 :
4404 : }
4405 :
4406 981811 : cache_size = 0;
4407 981811 : }
4408 :
4409 : /* Initialize some global variables needed by the dependency analysis
4410 : code. */
4411 :
4412 : void
4413 10524656 : init_deps_global (void)
4414 : {
4415 42098624 : CLEAR_HARD_REG_SET (implicit_reg_pending_clobbers);
4416 10524656 : CLEAR_HARD_REG_SET (implicit_reg_pending_uses);
4417 10524656 : reg_pending_sets = ALLOC_REG_SET (®_obstack);
4418 10524656 : reg_pending_clobbers = ALLOC_REG_SET (®_obstack);
4419 10524656 : reg_pending_uses = ALLOC_REG_SET (®_obstack);
4420 10524656 : reg_pending_control_uses = ALLOC_REG_SET (®_obstack);
4421 10524656 : reg_pending_barrier = NOT_A_BARRIER;
4422 :
4423 10524656 : if (!sel_sched_p () || sched_emulate_haifa_p)
4424 : {
4425 10523917 : sched_deps_info->start_insn = haifa_start_insn;
4426 10523917 : sched_deps_info->finish_insn = haifa_finish_insn;
4427 :
4428 10523917 : sched_deps_info->note_reg_set = haifa_note_reg_set;
4429 10523917 : sched_deps_info->note_reg_clobber = haifa_note_reg_clobber;
4430 10523917 : sched_deps_info->note_reg_use = haifa_note_reg_use;
4431 :
4432 10523917 : sched_deps_info->note_mem_dep = haifa_note_mem_dep;
4433 10523917 : sched_deps_info->note_dep = haifa_note_dep;
4434 : }
4435 10524656 : }
4436 :
4437 : /* Free everything used by the dependency analysis code. */
4438 :
4439 : void
4440 10524656 : finish_deps_global (void)
4441 : {
4442 10524656 : FREE_REG_SET (reg_pending_sets);
4443 10524656 : FREE_REG_SET (reg_pending_clobbers);
4444 10524656 : FREE_REG_SET (reg_pending_uses);
4445 10524656 : FREE_REG_SET (reg_pending_control_uses);
4446 10524656 : }
4447 :
4448 : /* Estimate the weakness of dependence between MEM1 and MEM2. */
4449 : dw_t
4450 524 : estimate_dep_weak (rtx mem1, rtx mem2)
4451 : {
4452 524 : if (mem1 == mem2)
4453 : /* MEMs are the same - don't speculate. */
4454 : return MIN_DEP_WEAK;
4455 :
4456 524 : rtx r1 = XEXP (mem1, 0);
4457 524 : rtx r2 = XEXP (mem2, 0);
4458 :
4459 524 : if (sched_deps_info->use_cselib)
4460 : {
4461 : /* We cannot call rtx_equal_for_cselib_p because the VALUEs might be
4462 : dangling at this point, since we never preserve them. Instead we
4463 : canonicalize manually to get stable VALUEs out of hashing. */
4464 0 : if (GET_CODE (r1) == VALUE && CSELIB_VAL_PTR (r1))
4465 0 : r1 = canonical_cselib_val (CSELIB_VAL_PTR (r1))->val_rtx;
4466 0 : if (GET_CODE (r2) == VALUE && CSELIB_VAL_PTR (r2))
4467 0 : r2 = canonical_cselib_val (CSELIB_VAL_PTR (r2))->val_rtx;
4468 : }
4469 :
4470 524 : if (r1 == r2
4471 524 : || (REG_P (r1) && REG_P (r2) && REGNO (r1) == REGNO (r2)))
4472 : /* Again, MEMs are the same. */
4473 : return MIN_DEP_WEAK;
4474 503 : else if ((REG_P (r1) && !REG_P (r2)) || (!REG_P (r1) && REG_P (r2)))
4475 : /* Different addressing modes - reason to be more speculative,
4476 : than usual. */
4477 : return NO_DEP_WEAK - (NO_DEP_WEAK - UNCERTAIN_DEP_WEAK) / 2;
4478 : else
4479 : /* We can't say anything about the dependence. */
4480 462 : return UNCERTAIN_DEP_WEAK;
4481 : }
4482 :
4483 : /* Add or update backward dependence between INSN and ELEM with type DEP_TYPE.
4484 : This function can handle same INSN and ELEM (INSN == ELEM).
4485 : It is a convenience wrapper. */
4486 : static void
4487 624022891 : add_dependence_1 (rtx_insn *insn, rtx_insn *elem, enum reg_note dep_type)
4488 : {
4489 624022891 : ds_t ds;
4490 624022891 : bool internal;
4491 :
4492 624022891 : if (dep_type == REG_DEP_TRUE)
4493 : ds = DEP_TRUE;
4494 : else if (dep_type == REG_DEP_OUTPUT)
4495 : ds = DEP_OUTPUT;
4496 : else if (dep_type == REG_DEP_CONTROL)
4497 : ds = DEP_CONTROL;
4498 : else
4499 : {
4500 0 : gcc_assert (dep_type == REG_DEP_ANTI);
4501 : ds = DEP_ANTI;
4502 : }
4503 :
4504 : /* When add_dependence is called from inside sched-deps.cc, we expect
4505 : cur_insn to be non-null. */
4506 624022891 : internal = cur_insn != NULL;
4507 624022891 : if (internal)
4508 567416327 : gcc_assert (insn == cur_insn);
4509 : else
4510 56606564 : cur_insn = insn;
4511 :
4512 624022891 : note_dep (elem, ds);
4513 624022891 : if (!internal)
4514 56606564 : cur_insn = NULL;
4515 624022891 : }
4516 :
4517 : /* Return weakness of speculative type TYPE in the dep_status DS,
4518 : without checking to prevent ICEs on malformed input. */
4519 : static dw_t
4520 0 : get_dep_weak_1 (ds_t ds, ds_t type)
4521 : {
4522 0 : ds = ds & type;
4523 :
4524 0 : switch (type)
4525 : {
4526 : case BEGIN_DATA: ds >>= BEGIN_DATA_BITS_OFFSET; break;
4527 0 : case BE_IN_DATA: ds >>= BE_IN_DATA_BITS_OFFSET; break;
4528 0 : case BEGIN_CONTROL: ds >>= BEGIN_CONTROL_BITS_OFFSET; break;
4529 0 : case BE_IN_CONTROL: ds >>= BE_IN_CONTROL_BITS_OFFSET; break;
4530 0 : default: gcc_unreachable ();
4531 : }
4532 :
4533 0 : return (dw_t) ds;
4534 : }
4535 :
4536 : /* Return weakness of speculative type TYPE in the dep_status DS. */
4537 : dw_t
4538 0 : get_dep_weak (ds_t ds, ds_t type)
4539 : {
4540 0 : dw_t dw = get_dep_weak_1 (ds, type);
4541 :
4542 0 : gcc_assert (MIN_DEP_WEAK <= dw && dw <= MAX_DEP_WEAK);
4543 0 : return dw;
4544 : }
4545 :
4546 : /* Return the dep_status, which has the same parameters as DS, except for
4547 : speculative type TYPE, that will have weakness DW. */
4548 : ds_t
4549 0 : set_dep_weak (ds_t ds, ds_t type, dw_t dw)
4550 : {
4551 0 : gcc_assert (MIN_DEP_WEAK <= dw && dw <= MAX_DEP_WEAK);
4552 :
4553 0 : ds &= ~type;
4554 0 : switch (type)
4555 : {
4556 0 : case BEGIN_DATA: ds |= ((ds_t) dw) << BEGIN_DATA_BITS_OFFSET; break;
4557 0 : case BE_IN_DATA: ds |= ((ds_t) dw) << BE_IN_DATA_BITS_OFFSET; break;
4558 0 : case BEGIN_CONTROL: ds |= ((ds_t) dw) << BEGIN_CONTROL_BITS_OFFSET; break;
4559 0 : case BE_IN_CONTROL: ds |= ((ds_t) dw) << BE_IN_CONTROL_BITS_OFFSET; break;
4560 0 : default: gcc_unreachable ();
4561 : }
4562 0 : return ds;
4563 : }
4564 :
4565 : /* Return the join of two dep_statuses DS1 and DS2.
4566 : If MAX_P is true then choose the greater probability,
4567 : otherwise multiply probabilities.
4568 : This function assumes that both DS1 and DS2 contain speculative bits. */
4569 : static ds_t
4570 0 : ds_merge_1 (ds_t ds1, ds_t ds2, bool max_p)
4571 : {
4572 0 : ds_t ds, t;
4573 :
4574 0 : gcc_assert ((ds1 & SPECULATIVE) && (ds2 & SPECULATIVE));
4575 :
4576 0 : ds = (ds1 & DEP_TYPES) | (ds2 & DEP_TYPES);
4577 :
4578 0 : t = FIRST_SPEC_TYPE;
4579 0 : do
4580 : {
4581 0 : if ((ds1 & t) && !(ds2 & t))
4582 0 : ds |= ds1 & t;
4583 0 : else if (!(ds1 & t) && (ds2 & t))
4584 0 : ds |= ds2 & t;
4585 0 : else if ((ds1 & t) && (ds2 & t))
4586 : {
4587 0 : dw_t dw1 = get_dep_weak (ds1, t);
4588 0 : dw_t dw2 = get_dep_weak (ds2, t);
4589 0 : ds_t dw;
4590 :
4591 0 : if (!max_p)
4592 : {
4593 0 : dw = ((ds_t) dw1) * ((ds_t) dw2);
4594 0 : dw /= MAX_DEP_WEAK;
4595 0 : if (dw < MIN_DEP_WEAK)
4596 0 : dw = MIN_DEP_WEAK;
4597 : }
4598 : else
4599 : {
4600 0 : if (dw1 >= dw2)
4601 : dw = dw1;
4602 : else
4603 : dw = dw2;
4604 : }
4605 :
4606 0 : ds = set_dep_weak (ds, t, (dw_t) dw);
4607 : }
4608 :
4609 0 : if (t == LAST_SPEC_TYPE)
4610 : break;
4611 0 : t <<= SPEC_TYPE_SHIFT;
4612 0 : }
4613 : while (1);
4614 :
4615 0 : return ds;
4616 : }
4617 :
4618 : /* Return the join of two dep_statuses DS1 and DS2.
4619 : This function assumes that both DS1 and DS2 contain speculative bits. */
4620 : ds_t
4621 0 : ds_merge (ds_t ds1, ds_t ds2)
4622 : {
4623 0 : return ds_merge_1 (ds1, ds2, false);
4624 : }
4625 :
4626 : /* Return the join of two dep_statuses DS1 and DS2. */
4627 : ds_t
4628 54597 : ds_full_merge (ds_t ds, ds_t ds2, rtx mem1, rtx mem2)
4629 : {
4630 54597 : ds_t new_status = ds | ds2;
4631 :
4632 54597 : if (new_status & SPECULATIVE)
4633 : {
4634 0 : if ((ds && !(ds & SPECULATIVE))
4635 0 : || (ds2 && !(ds2 & SPECULATIVE)))
4636 : /* Then this dep can't be speculative. */
4637 0 : new_status &= ~SPECULATIVE;
4638 : else
4639 : {
4640 : /* Both are speculative. Merging probabilities. */
4641 0 : if (mem1)
4642 : {
4643 0 : dw_t dw;
4644 :
4645 0 : dw = estimate_dep_weak (mem1, mem2);
4646 0 : ds = set_dep_weak (ds, BEGIN_DATA, dw);
4647 : }
4648 :
4649 0 : if (!ds)
4650 : new_status = ds2;
4651 0 : else if (!ds2)
4652 : new_status = ds;
4653 : else
4654 0 : new_status = ds_merge (ds2, ds);
4655 : }
4656 : }
4657 :
4658 54597 : return new_status;
4659 : }
4660 :
4661 : /* Return the join of DS1 and DS2. Use maximum instead of multiplying
4662 : probabilities. */
4663 : ds_t
4664 2176 : ds_max_merge (ds_t ds1, ds_t ds2)
4665 : {
4666 2176 : if (ds1 == 0 && ds2 == 0)
4667 : return 0;
4668 :
4669 0 : if (ds1 == 0 && ds2 != 0)
4670 : return ds2;
4671 :
4672 0 : if (ds1 != 0 && ds2 == 0)
4673 : return ds1;
4674 :
4675 0 : return ds_merge_1 (ds1, ds2, true);
4676 : }
4677 :
4678 : /* Return the probability of speculation success for the speculation
4679 : status DS. */
4680 : dw_t
4681 0 : ds_weak (ds_t ds)
4682 : {
4683 0 : ds_t res = 1, dt;
4684 0 : int n = 0;
4685 :
4686 0 : dt = FIRST_SPEC_TYPE;
4687 0 : do
4688 : {
4689 0 : if (ds & dt)
4690 : {
4691 0 : res *= (ds_t) get_dep_weak (ds, dt);
4692 0 : n++;
4693 : }
4694 :
4695 0 : if (dt == LAST_SPEC_TYPE)
4696 : break;
4697 0 : dt <<= SPEC_TYPE_SHIFT;
4698 : }
4699 : while (1);
4700 :
4701 0 : gcc_assert (n);
4702 0 : while (--n)
4703 0 : res /= MAX_DEP_WEAK;
4704 :
4705 0 : if (res < MIN_DEP_WEAK)
4706 : res = MIN_DEP_WEAK;
4707 :
4708 0 : gcc_assert (res <= MAX_DEP_WEAK);
4709 :
4710 0 : return (dw_t) res;
4711 : }
4712 :
4713 : /* Return a dep status that contains all speculation types of DS. */
4714 : ds_t
4715 5005 : ds_get_speculation_types (ds_t ds)
4716 : {
4717 5005 : if (ds & BEGIN_DATA)
4718 0 : ds |= BEGIN_DATA;
4719 5005 : if (ds & BE_IN_DATA)
4720 0 : ds |= BE_IN_DATA;
4721 5005 : if (ds & BEGIN_CONTROL)
4722 0 : ds |= BEGIN_CONTROL;
4723 5005 : if (ds & BE_IN_CONTROL)
4724 0 : ds |= BE_IN_CONTROL;
4725 :
4726 5005 : return ds & SPECULATIVE;
4727 : }
4728 :
4729 : /* Return a dep status that contains maximal weakness for each speculation
4730 : type present in DS. */
4731 : ds_t
4732 2727 : ds_get_max_dep_weak (ds_t ds)
4733 : {
4734 2727 : if (ds & BEGIN_DATA)
4735 0 : ds = set_dep_weak (ds, BEGIN_DATA, MAX_DEP_WEAK);
4736 2727 : if (ds & BE_IN_DATA)
4737 0 : ds = set_dep_weak (ds, BE_IN_DATA, MAX_DEP_WEAK);
4738 2727 : if (ds & BEGIN_CONTROL)
4739 0 : ds = set_dep_weak (ds, BEGIN_CONTROL, MAX_DEP_WEAK);
4740 2727 : if (ds & BE_IN_CONTROL)
4741 0 : ds = set_dep_weak (ds, BE_IN_CONTROL, MAX_DEP_WEAK);
4742 :
4743 2727 : return ds;
4744 : }
4745 :
4746 : /* Dump information about the dependence status S. */
4747 : static void
4748 0 : dump_ds (FILE *f, ds_t s)
4749 : {
4750 0 : fprintf (f, "{");
4751 :
4752 0 : if (s & BEGIN_DATA)
4753 0 : fprintf (f, "BEGIN_DATA: %d; ", get_dep_weak_1 (s, BEGIN_DATA));
4754 0 : if (s & BE_IN_DATA)
4755 0 : fprintf (f, "BE_IN_DATA: %d; ", get_dep_weak_1 (s, BE_IN_DATA));
4756 0 : if (s & BEGIN_CONTROL)
4757 0 : fprintf (f, "BEGIN_CONTROL: %d; ", get_dep_weak_1 (s, BEGIN_CONTROL));
4758 0 : if (s & BE_IN_CONTROL)
4759 0 : fprintf (f, "BE_IN_CONTROL: %d; ", get_dep_weak_1 (s, BE_IN_CONTROL));
4760 :
4761 0 : if (s & HARD_DEP)
4762 0 : fprintf (f, "HARD_DEP; ");
4763 :
4764 0 : if (s & DEP_TRUE)
4765 0 : fprintf (f, "DEP_TRUE; ");
4766 0 : if (s & DEP_OUTPUT)
4767 0 : fprintf (f, "DEP_OUTPUT; ");
4768 0 : if (s & DEP_ANTI)
4769 0 : fprintf (f, "DEP_ANTI; ");
4770 0 : if (s & DEP_CONTROL)
4771 0 : fprintf (f, "DEP_CONTROL; ");
4772 :
4773 0 : fprintf (f, "}");
4774 0 : }
4775 :
4776 : DEBUG_FUNCTION void
4777 0 : debug_ds (ds_t s)
4778 : {
4779 0 : dump_ds (stderr, s);
4780 0 : fprintf (stderr, "\n");
4781 0 : }
4782 :
4783 : /* Verify that dependence type and status are consistent.
4784 : If RELAXED_P is true, then skip dep_weakness checks. */
4785 : static void
4786 785730567 : check_dep (dep_t dep, bool relaxed_p)
4787 : {
4788 785730567 : enum reg_note dt = DEP_TYPE (dep);
4789 785730567 : ds_t ds = DEP_STATUS (dep);
4790 :
4791 785730567 : gcc_assert (DEP_PRO (dep) != DEP_CON (dep));
4792 :
4793 785730567 : if (!(current_sched_info->flags & USE_DEPS_LIST))
4794 : {
4795 785730567 : gcc_assert (ds == 0);
4796 : return;
4797 : }
4798 :
4799 : /* Check that dependence type contains the same bits as the status. */
4800 0 : if (dt == REG_DEP_TRUE)
4801 0 : gcc_assert (ds & DEP_TRUE);
4802 0 : else if (dt == REG_DEP_OUTPUT)
4803 0 : gcc_assert ((ds & DEP_OUTPUT)
4804 : && !(ds & DEP_TRUE));
4805 0 : else if (dt == REG_DEP_ANTI)
4806 0 : gcc_assert ((ds & DEP_ANTI)
4807 : && !(ds & (DEP_OUTPUT | DEP_TRUE)));
4808 : else
4809 0 : gcc_assert (dt == REG_DEP_CONTROL
4810 : && (ds & DEP_CONTROL)
4811 : && !(ds & (DEP_OUTPUT | DEP_ANTI | DEP_TRUE)));
4812 :
4813 : /* HARD_DEP cannot appear in dep_status of a link. */
4814 0 : gcc_assert (!(ds & HARD_DEP));
4815 :
4816 : /* Check that dependence status is set correctly when speculation is not
4817 : supported. */
4818 0 : if (!sched_deps_info->generate_spec_deps)
4819 0 : gcc_assert (!(ds & SPECULATIVE));
4820 0 : else if (ds & SPECULATIVE)
4821 : {
4822 0 : if (!relaxed_p)
4823 : {
4824 : ds_t type = FIRST_SPEC_TYPE;
4825 :
4826 : /* Check that dependence weakness is in proper range. */
4827 0 : do
4828 : {
4829 0 : if (ds & type)
4830 0 : get_dep_weak (ds, type);
4831 :
4832 0 : if (type == LAST_SPEC_TYPE)
4833 : break;
4834 0 : type <<= SPEC_TYPE_SHIFT;
4835 : }
4836 : while (1);
4837 : }
4838 :
4839 0 : if (ds & BEGIN_SPEC)
4840 : {
4841 : /* Only true dependence can be data speculative. */
4842 0 : if (ds & BEGIN_DATA)
4843 0 : gcc_assert (ds & DEP_TRUE);
4844 :
4845 : /* Control dependencies in the insn scheduler are represented by
4846 : anti-dependencies, therefore only anti dependence can be
4847 : control speculative. */
4848 0 : if (ds & BEGIN_CONTROL)
4849 0 : gcc_assert (ds & DEP_ANTI);
4850 : }
4851 : else
4852 : {
4853 : /* Subsequent speculations should resolve true dependencies. */
4854 0 : gcc_assert ((ds & DEP_TYPES) == DEP_TRUE);
4855 : }
4856 :
4857 : /* Check that true and anti dependencies can't have other speculative
4858 : statuses. */
4859 0 : if (ds & DEP_TRUE)
4860 0 : gcc_assert (ds & (BEGIN_DATA | BE_IN_SPEC));
4861 : /* An output dependence can't be speculative at all. */
4862 0 : gcc_assert (!(ds & DEP_OUTPUT));
4863 0 : if (ds & DEP_ANTI)
4864 0 : gcc_assert (ds & BEGIN_CONTROL);
4865 : }
4866 : }
4867 :
4868 : /* The following code discovers opportunities to switch a memory reference
4869 : and an increment by modifying the address. We ensure that this is done
4870 : only for dependencies that are only used to show a single register
4871 : dependence (using DEP_NONREG and DEP_MULTIPLE), and so that every memory
4872 : instruction involved is subject to only one dep that can cause a pattern
4873 : change.
4874 :
4875 : When we discover a suitable dependency, we fill in the dep_replacement
4876 : structure to show how to modify the memory reference. */
4877 :
4878 : /* Holds information about a pair of memory reference and register increment
4879 : insns which depend on each other, but could possibly be interchanged. */
4880 : struct mem_inc_info
4881 : {
4882 : rtx_insn *inc_insn;
4883 : rtx_insn *mem_insn;
4884 :
4885 : rtx *mem_loc;
4886 : /* A register occurring in the memory address for which we wish to break
4887 : the dependence. This must be identical to the destination register of
4888 : the increment. */
4889 : rtx mem_reg0;
4890 : /* Any kind of index that is added to that register. */
4891 : rtx mem_index;
4892 : /* The constant offset used in the memory address. */
4893 : HOST_WIDE_INT mem_constant;
4894 : /* The constant added in the increment insn. Negated if the increment is
4895 : after the memory address. */
4896 : HOST_WIDE_INT inc_constant;
4897 : /* The source register used in the increment. May be different from mem_reg0
4898 : if the increment occurs before the memory address. */
4899 : rtx inc_input;
4900 : };
4901 :
4902 : /* Verify that the memory location described in MII can be replaced with
4903 : one using NEW_ADDR. Return the new memory reference or NULL_RTX. The
4904 : insn remains unchanged by this function. */
4905 :
4906 : static rtx
4907 1133242 : attempt_change (struct mem_inc_info *mii, rtx new_addr)
4908 : {
4909 1133242 : rtx mem = *mii->mem_loc;
4910 1133242 : rtx new_mem;
4911 :
4912 1133242 : if (!targetm.new_address_profitable_p (mem, mii->mem_insn, new_addr))
4913 : return NULL_RTX;
4914 :
4915 : /* Jump through a lot of hoops to keep the attributes up to date. We
4916 : do not want to call one of the change address variants that take
4917 : an offset even though we know the offset in many cases. These
4918 : assume you are changing where the address is pointing by the
4919 : offset. */
4920 1133242 : new_mem = replace_equiv_address_nv (mem, new_addr);
4921 1133242 : if (! validate_change (mii->mem_insn, mii->mem_loc, new_mem, 0))
4922 : {
4923 1 : if (sched_verbose >= 5)
4924 0 : fprintf (sched_dump, "validation failure\n");
4925 : return NULL_RTX;
4926 : }
4927 :
4928 : /* Put back the old one. */
4929 1133241 : validate_change (mii->mem_insn, mii->mem_loc, mem, 0);
4930 :
4931 1133241 : return new_mem;
4932 : }
4933 :
4934 : /* Return true if INSN is of a form "a = b op c" where a and b are
4935 : regs. op is + if c is a reg and +|- if c is a const. Fill in
4936 : informantion in MII about what is found.
4937 : BEFORE_MEM indicates whether the increment is found before or after
4938 : a corresponding memory reference. */
4939 :
4940 : static bool
4941 35438684 : parse_add_or_inc (struct mem_inc_info *mii, rtx_insn *insn, bool before_mem)
4942 : {
4943 35438684 : rtx pat = single_set (insn);
4944 35438684 : rtx src, cst;
4945 35438684 : bool regs_equal;
4946 :
4947 35438684 : if (RTX_FRAME_RELATED_P (insn) || !pat)
4948 : return false;
4949 :
4950 : /* Do not allow breaking data dependencies for insns that are marked
4951 : with REG_STACK_CHECK. */
4952 29165691 : if (find_reg_note (insn, REG_STACK_CHECK, NULL))
4953 : return false;
4954 :
4955 : /* Result must be single reg. */
4956 29165691 : if (!REG_P (SET_DEST (pat)))
4957 : return false;
4958 :
4959 20613514 : if (GET_CODE (SET_SRC (pat)) != PLUS)
4960 : return false;
4961 :
4962 4756171 : mii->inc_insn = insn;
4963 4756171 : src = SET_SRC (pat);
4964 4756171 : mii->inc_input = XEXP (src, 0);
4965 :
4966 4756171 : if (!REG_P (XEXP (src, 0)))
4967 : return false;
4968 :
4969 4534703 : if (!rtx_equal_p (SET_DEST (pat), mii->mem_reg0))
4970 : return false;
4971 :
4972 2935333 : cst = XEXP (src, 1);
4973 2935333 : if (!CONST_INT_P (cst))
4974 : return false;
4975 2800893 : mii->inc_constant = INTVAL (cst);
4976 :
4977 2800893 : regs_equal = rtx_equal_p (mii->inc_input, mii->mem_reg0);
4978 :
4979 2800893 : if (!before_mem)
4980 : {
4981 2006991 : mii->inc_constant = -mii->inc_constant;
4982 2006991 : if (!regs_equal)
4983 : return false;
4984 : }
4985 :
4986 2752097 : if (regs_equal && REGNO (SET_DEST (pat)) == STACK_POINTER_REGNUM)
4987 : {
4988 : /* Note that the sign has already been reversed for !before_mem. */
4989 2352735 : if (STACK_GROWS_DOWNWARD)
4990 2352735 : return mii->inc_constant > 0;
4991 : else
4992 : return mii->inc_constant < 0;
4993 : }
4994 : return true;
4995 : }
4996 :
4997 : /* Once a suitable mem reference has been found and the corresponding data
4998 : in MII has been filled in, this function is called to find a suitable
4999 : add or inc insn involving the register we found in the memory
5000 : reference.
5001 : If successful, this function will create additional dependencies between
5002 : - mii->inc_insn's producers and mii->mem_insn as a consumer (if backwards)
5003 : - mii->inc_insn's consumers and mii->mem_insn as a producer (if !backwards).
5004 : */
5005 :
5006 : static bool
5007 31106498 : find_inc (struct mem_inc_info *mii, bool backwards)
5008 : {
5009 31106498 : sd_iterator_def sd_it;
5010 31106498 : dep_t dep;
5011 31106498 : sd_list_types_def mem_deps = backwards ? SD_LIST_HARD_BACK : SD_LIST_FORW;
5012 31106498 : int n_mem_deps = dep_list_size (mii->mem_insn, mem_deps);
5013 :
5014 31106498 : sd_it = sd_iterator_start (mii->mem_insn, mem_deps);
5015 104427899 : while (sd_iterator_cond (&sd_it, &dep))
5016 : {
5017 74454642 : dep_node_t node = DEP_LINK_NODE (*sd_it.linkp);
5018 74454642 : rtx_insn *pro = DEP_PRO (dep);
5019 74454642 : rtx_insn *con = DEP_CON (dep);
5020 74454642 : rtx_insn *inc_cand;
5021 74454642 : int n_inc_deps;
5022 :
5023 74454642 : if (DEP_NONREG (dep) || DEP_MULTIPLE (dep))
5024 38921507 : goto next;
5025 :
5026 35533135 : if (backwards)
5027 : {
5028 14799660 : inc_cand = pro;
5029 14799660 : n_inc_deps = dep_list_size (inc_cand, SD_LIST_BACK);
5030 : }
5031 : else
5032 : {
5033 20733475 : inc_cand = con;
5034 20733475 : n_inc_deps = dep_list_size (inc_cand, SD_LIST_FORW);
5035 : }
5036 :
5037 : /* In the FOR_EACH_DEP loop below we will create additional n_inc_deps
5038 : for mem_insn. This by itself is not a problem, since each mem_insn
5039 : will have only a few inc_insns associated with it. However, if
5040 : we consider that a single inc_insn may have a lot of mem_insns, AND,
5041 : on top of that, a few other inc_insns associated with it --
5042 : those _other inc_insns_ will get (n_mem_deps * number of MEM insns)
5043 : dependencies created for them. This may cause an exponential
5044 : growth of memory usage and scheduling time.
5045 : See PR96388 for details.
5046 : We [heuristically] use n_inc_deps as a proxy for the number of MEM
5047 : insns, and drop opportunities for breaking modifiable_mem dependencies
5048 : when dependency lists grow beyond reasonable size. */
5049 35533135 : if (n_mem_deps * n_inc_deps
5050 35533135 : >= param_max_pending_list_length * param_max_pending_list_length)
5051 94451 : goto next;
5052 :
5053 35438684 : if (parse_add_or_inc (mii, inc_cand, backwards))
5054 : {
5055 1134467 : struct dep_replacement *desc;
5056 1134467 : df_ref def;
5057 1134467 : rtx newaddr, newmem;
5058 :
5059 1134467 : if (sched_verbose >= 5)
5060 0 : fprintf (sched_dump, "candidate mem/inc pair: %d %d\n",
5061 0 : INSN_UID (mii->mem_insn), INSN_UID (inc_cand));
5062 :
5063 : /* Need to assure that none of the operands of the inc
5064 : instruction are assigned to by the mem insn. */
5065 1616265 : FOR_EACH_INSN_DEF (def, mii->mem_insn)
5066 483023 : if (reg_overlap_mentioned_p (DF_REF_REG (def), mii->inc_input)
5067 483023 : || reg_overlap_mentioned_p (DF_REF_REG (def), mii->mem_reg0))
5068 : {
5069 1225 : if (sched_verbose >= 5)
5070 0 : fprintf (sched_dump,
5071 : "inc conflicts with store failure.\n");
5072 1225 : goto next;
5073 : }
5074 :
5075 1133242 : newaddr = mii->inc_input;
5076 1133242 : if (mii->mem_index != NULL_RTX)
5077 19521 : newaddr = gen_rtx_PLUS (GET_MODE (newaddr), newaddr,
5078 : mii->mem_index);
5079 2266484 : newaddr = plus_constant (GET_MODE (newaddr), newaddr,
5080 1133242 : mii->mem_constant + mii->inc_constant);
5081 1133242 : newmem = attempt_change (mii, newaddr);
5082 1133242 : if (newmem == NULL_RTX)
5083 1 : goto next;
5084 1133241 : if (sched_verbose >= 5)
5085 0 : fprintf (sched_dump, "successful address replacement\n");
5086 1133241 : desc = XCNEW (struct dep_replacement);
5087 1133241 : DEP_REPLACE (dep) = desc;
5088 1133241 : desc->loc = mii->mem_loc;
5089 1133241 : desc->newval = newmem;
5090 1133241 : desc->orig = *desc->loc;
5091 1133241 : desc->insn = mii->mem_insn;
5092 3399723 : move_dep_link (DEP_NODE_BACK (node), INSN_HARD_BACK_DEPS (con),
5093 1133241 : INSN_SPEC_BACK_DEPS (con));
5094 :
5095 : /* Make sure that n_inc_deps above is consistent with dependencies
5096 : we create. */
5097 1133241 : gcc_assert (mii->inc_insn == inc_cand);
5098 :
5099 1133241 : if (backwards)
5100 : {
5101 2052909 : FOR_EACH_DEP (mii->inc_insn, SD_LIST_BACK, sd_it, dep)
5102 1858279 : add_dependence_1 (mii->mem_insn, DEP_PRO (dep),
5103 : REG_DEP_TRUE);
5104 : }
5105 : else
5106 : {
5107 6928108 : FOR_EACH_DEP (mii->inc_insn, SD_LIST_FORW, sd_it, dep)
5108 5989497 : add_dependence_1 (DEP_CON (dep), mii->mem_insn,
5109 : REG_DEP_ANTI);
5110 : }
5111 : return true;
5112 : }
5113 34304217 : next:
5114 73321401 : sd_iterator_next (&sd_it);
5115 : }
5116 : return false;
5117 : }
5118 :
5119 : /* A recursive function that walks ADDRESS_OF_X to find memory references
5120 : which could be modified during scheduling. We call find_inc for each
5121 : one we find that has a recognizable form. MII holds information about
5122 : the pair of memory/increment instructions.
5123 : We ensure that every instruction with a memory reference (which will be
5124 : the location of the replacement) is assigned at most one breakable
5125 : dependency. */
5126 :
5127 : static bool
5128 258277745 : find_mem (struct mem_inc_info *mii, rtx *address_of_x)
5129 : {
5130 258277745 : rtx x = *address_of_x;
5131 258277745 : enum rtx_code code = GET_CODE (x);
5132 258277745 : const char *const fmt = GET_RTX_FORMAT (code);
5133 258277745 : int i;
5134 :
5135 258277745 : if (code == MEM)
5136 : {
5137 25965789 : rtx reg0 = XEXP (x, 0);
5138 :
5139 25965789 : mii->mem_loc = address_of_x;
5140 25965789 : mii->mem_index = NULL_RTX;
5141 25965789 : mii->mem_constant = 0;
5142 25965789 : if (GET_CODE (reg0) == PLUS && CONST_INT_P (XEXP (reg0, 1)))
5143 : {
5144 13250904 : mii->mem_constant = INTVAL (XEXP (reg0, 1));
5145 13250904 : reg0 = XEXP (reg0, 0);
5146 : }
5147 25965789 : if (GET_CODE (reg0) == PLUS)
5148 : {
5149 1135234 : mii->mem_index = XEXP (reg0, 1);
5150 1135234 : reg0 = XEXP (reg0, 0);
5151 : }
5152 25965789 : if (REG_P (reg0))
5153 : {
5154 16305833 : df_ref use;
5155 16305833 : int occurrences = 0;
5156 :
5157 : /* Make sure this reg appears only once in this insn. Can't use
5158 : count_occurrences since that only works for pseudos. */
5159 40596523 : FOR_EACH_INSN_USE (use, mii->mem_insn)
5160 24945959 : if (reg_overlap_mentioned_p (reg0, DF_REF_REG (use)))
5161 16961102 : if (++occurrences > 1)
5162 : {
5163 655269 : if (sched_verbose >= 5)
5164 0 : fprintf (sched_dump, "mem count failure\n");
5165 : return false;
5166 : }
5167 :
5168 15650564 : mii->mem_reg0 = reg0;
5169 15650564 : return find_inc (mii, true) || find_inc (mii, false);
5170 : }
5171 : return false;
5172 : }
5173 :
5174 232311956 : if (code == SIGN_EXTRACT || code == ZERO_EXTRACT)
5175 : {
5176 : /* If REG occurs inside a MEM used in a bit-field reference,
5177 : that is unacceptable. */
5178 : return false;
5179 : }
5180 :
5181 : /* Time for some deep diving. */
5182 545631859 : for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
5183 : {
5184 314604815 : if (fmt[i] == 'e')
5185 : {
5186 182339488 : if (find_mem (mii, &XEXP (x, i)))
5187 : return true;
5188 : }
5189 132265327 : else if (fmt[i] == 'E')
5190 : {
5191 8671491 : int j;
5192 26890350 : for (j = XVECLEN (x, i) - 1; j >= 0; j--)
5193 18242426 : if (find_mem (mii, &XVECEXP (x, i, j)))
5194 : return true;
5195 : }
5196 : }
5197 : return false;
5198 : }
5199 :
5200 :
5201 : /* Examine the instructions between HEAD and TAIL and try to find
5202 : dependencies that can be broken by modifying one of the patterns. */
5203 :
5204 : void
5205 10504426 : find_modifiable_mems (rtx_insn *head, rtx_insn *tail)
5206 : {
5207 10504426 : rtx_insn *insn, *next_tail = NEXT_INSN (tail);
5208 10504426 : int success_in_block = 0;
5209 :
5210 135466106 : for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
5211 : {
5212 114457254 : struct mem_inc_info mii;
5213 :
5214 114457254 : if (!NONDEBUG_INSN_P (insn) || RTX_FRAME_RELATED_P (insn))
5215 56761423 : continue;
5216 :
5217 57695831 : mii.mem_insn = insn;
5218 57695831 : if (find_mem (&mii, &PATTERN (insn)))
5219 1133241 : success_in_block++;
5220 : }
5221 10504426 : if (success_in_block && sched_verbose >= 5)
5222 0 : fprintf (sched_dump, "%d candidates for address modification found.\n",
5223 : success_in_block);
5224 10504426 : }
5225 :
5226 : #if CHECKING_P
5227 :
5228 : namespace selftest {
5229 :
5230 : /* Verify that free_deps releases entries recorded only in reg_last_dirty. */
5231 :
5232 : static void
5233 4 : test_dirty_reg_last_release ()
5234 : {
5235 4 : bitmap_obstack test_obstack;
5236 4 : bitmap_obstack_initialize (&test_obstack);
5237 :
5238 4 : deps_desc deps = {};
5239 4 : deps.max_reg = 2;
5240 4 : deps.reg_last = XCNEWVEC (deps_reg, deps.max_reg);
5241 4 : bitmap_initialize (&deps.reg_last_in_use, &test_obstack);
5242 4 : bitmap_initialize (&deps.reg_last_dirty, &test_obstack);
5243 :
5244 4 : rtx_insn_list *uses = alloc_INSN_LIST (NULL_RTX, NULL_RTX);
5245 4 : rtx_insn_list *control_uses = alloc_INSN_LIST (NULL_RTX, NULL_RTX);
5246 4 : deps.reg_last[1].uses = uses;
5247 4 : deps.reg_last[1].control_uses = control_uses;
5248 4 : SET_REGNO_REG_SET (&deps.reg_last_dirty, 1);
5249 :
5250 4 : common_sched_info_def sched_info = {};
5251 4 : sched_info.sched_pass_id = SCHED_RGN_PASS;
5252 4 : common_sched_info_def *saved_common_sched_info = common_sched_info;
5253 4 : common_sched_info = &sched_info;
5254 4 : free_deps (&deps);
5255 4 : common_sched_info = saved_common_sched_info;
5256 :
5257 4 : ASSERT_EQ (0, deps.max_reg);
5258 4 : ASSERT_EQ (NULL, deps.reg_last);
5259 :
5260 4 : rtx_insn_list *first = alloc_INSN_LIST (NULL_RTX, NULL_RTX);
5261 4 : rtx_insn_list *second = alloc_INSN_LIST (NULL_RTX, NULL_RTX);
5262 4 : ASSERT_TRUE ((first == control_uses && second == uses)
5263 : || (first == uses && second == control_uses));
5264 4 : free_INSN_LIST_list (&first);
5265 4 : free_INSN_LIST_list (&second);
5266 :
5267 4 : sched_deps_finish ();
5268 4 : bitmap_obstack_release (&test_obstack);
5269 4 : }
5270 :
5271 : /* Verify that a pooled reg_last array is empty when it is reused. */
5272 :
5273 : static void
5274 4 : test_reg_last_pool ()
5275 : {
5276 4 : const int max_reg = 3;
5277 4 : ASSERT_TRUE (reg_last_pool.is_empty ());
5278 :
5279 4 : bitmap_obstack test_obstack;
5280 4 : bitmap_obstack_initialize (&test_obstack);
5281 :
5282 4 : deps_desc deps = {};
5283 4 : deps.max_reg = max_reg;
5284 4 : deps.reg_last = alloc_reg_last (max_reg);
5285 4 : struct deps_reg *saved_reg_last = deps.reg_last;
5286 4 : bitmap_initialize (&deps.reg_last_in_use, &test_obstack);
5287 4 : bitmap_initialize (&deps.reg_last_dirty, &test_obstack);
5288 :
5289 4 : deps.reg_last[0].uses = alloc_INSN_LIST (NULL_RTX, NULL_RTX);
5290 4 : deps.reg_last[0].sets = alloc_INSN_LIST (NULL_RTX, NULL_RTX);
5291 4 : deps.reg_last[0].implicit_sets = alloc_INSN_LIST (NULL_RTX, NULL_RTX);
5292 4 : deps.reg_last[0].clobbers = alloc_INSN_LIST (NULL_RTX, NULL_RTX);
5293 4 : deps.reg_last[0].uses_length = 2;
5294 4 : deps.reg_last[0].clobbers_length = 3;
5295 4 : SET_REGNO_REG_SET (&deps.reg_last_in_use, 0);
5296 :
5297 4 : deps.reg_last[1].control_uses = alloc_INSN_LIST (NULL_RTX, NULL_RTX);
5298 4 : SET_REGNO_REG_SET (&deps.reg_last_dirty, 1);
5299 :
5300 4 : common_sched_info_def sched_info = {};
5301 4 : sched_info.sched_pass_id = SCHED_RGN_PASS;
5302 4 : common_sched_info_def *saved_common_sched_info = common_sched_info;
5303 4 : common_sched_info = &sched_info;
5304 4 : free_deps (&deps);
5305 :
5306 4 : ASSERT_EQ (0, deps.max_reg);
5307 4 : ASSERT_EQ (NULL, deps.reg_last);
5308 4 : ASSERT_EQ (1, reg_last_pool.length ());
5309 :
5310 4 : struct deps_reg *reused_reg_last = alloc_reg_last (max_reg);
5311 4 : ASSERT_EQ (saved_reg_last, reused_reg_last);
5312 8 : ASSERT_TRUE (reg_last_pool.is_empty ());
5313 16 : for (int i = 0; i < max_reg; ++i)
5314 : {
5315 12 : ASSERT_EQ (NULL, reused_reg_last[i].uses);
5316 12 : ASSERT_EQ (NULL, reused_reg_last[i].sets);
5317 12 : ASSERT_EQ (NULL, reused_reg_last[i].implicit_sets);
5318 12 : ASSERT_EQ (NULL, reused_reg_last[i].control_uses);
5319 12 : ASSERT_EQ (NULL, reused_reg_last[i].clobbers);
5320 12 : ASSERT_EQ (0, reused_reg_last[i].uses_length);
5321 12 : ASSERT_EQ (0, reused_reg_last[i].clobbers_length);
5322 : }
5323 :
5324 4 : free (reused_reg_last);
5325 4 : sched_deps_finish ();
5326 4 : common_sched_info = saved_common_sched_info;
5327 4 : bitmap_obstack_release (&test_obstack);
5328 4 : }
5329 :
5330 : /* Dependence producers recorded by observe_barrier_dependence. */
5331 :
5332 : static auto_vec<rtx_insn *> *observed_barrier_deps;
5333 :
5334 : /* Record a barrier dependence on PRODUCER. */
5335 :
5336 : static void
5337 380 : observe_barrier_dependence (rtx_insn *producer, ds_t)
5338 : {
5339 380 : gcc_assert (observed_barrier_deps);
5340 380 : observed_barrier_deps->safe_push (producer);
5341 380 : }
5342 :
5343 : /* Assert that LIST contains FIRST followed by SECOND and nothing else. */
5344 :
5345 : static void
5346 20 : assert_insn_list (rtx_insn_list *list, rtx_insn *first, rtx_insn *second)
5347 : {
5348 20 : ASSERT_TRUE (list);
5349 20 : ASSERT_EQ (first, list->insn ());
5350 20 : list = list->next ();
5351 20 : ASSERT_TRUE (list);
5352 20 : ASSERT_EQ (second, list->insn ());
5353 20 : ASSERT_EQ (NULL, list->next ());
5354 20 : }
5355 :
5356 : /* Verify that a full materialisation bitmap does not emit an inert pending
5357 : barrier. OBSTACK owns the context bitmaps. BARRIER is the current
5358 : barrier, OLD_BARRIER is pending, and SETTER is in every literal entry. */
5359 :
5360 : static void
5361 4 : test_full_lazy_barrier (bitmap_obstack *obstack, rtx_insn *barrier,
5362 : rtx_insn *old_barrier, rtx_insn *setter)
5363 : {
5364 4 : deps_desc deps = {};
5365 4 : deps.max_reg = FIRST_PSEUDO_REGISTER;
5366 4 : deps.reg_last = alloc_reg_last (deps.max_reg);
5367 4 : bitmap_initialize (&deps.reg_last_in_use, obstack);
5368 4 : bitmap_initialize (&deps.reg_last_dirty, obstack);
5369 4 : bitmap_set_range (&deps.reg_last_in_use, 0, deps.max_reg);
5370 :
5371 376 : for (int i = 0; i < deps.max_reg; ++i)
5372 368 : deps.reg_last[i].sets = alloc_INSN_LIST (setter, NULL_RTX);
5373 4 : deps.pending_barriers = alloc_INSN_LIST (old_barrier, NULL_RTX);
5374 :
5375 4 : auto_vec<rtx_insn *> observed;
5376 4 : gcc_assert (!observed_barrier_deps);
5377 4 : observed_barrier_deps = &observed;
5378 4 : sched_analyze_insn (&deps, PATTERN (barrier), barrier);
5379 4 : observed_barrier_deps = NULL;
5380 :
5381 8 : ASSERT_EQ ((unsigned) deps.max_reg, observed.length ());
5382 372 : for (int i = 0; i < deps.max_reg; ++i)
5383 368 : ASSERT_EQ (setter, observed[i]);
5384 4 : ASSERT_TRUE (deps.pending_barriers);
5385 4 : ASSERT_EQ (barrier, deps.pending_barriers->insn ());
5386 4 : ASSERT_EQ (NULL, deps.pending_barriers->next ());
5387 :
5388 4 : free_deps (&deps);
5389 4 : }
5390 :
5391 : /* Verify that a pending barrier is emitted at the first gap in the
5392 : materialisation bitmap. OBSTACK owns the context bitmaps. BARRIER is the
5393 : current barrier, OLD_BARRIER is pending, and SETTER0 and SETTER2 are the
5394 : literal entries. */
5395 :
5396 : static void
5397 4 : test_sparse_lazy_barrier (bitmap_obstack *obstack, rtx_insn *barrier,
5398 : rtx_insn *old_barrier, rtx_insn *setter0,
5399 : rtx_insn *setter2)
5400 : {
5401 4 : deps_desc deps = {};
5402 4 : deps.max_reg = 4;
5403 4 : deps.reg_last = alloc_reg_last (deps.max_reg);
5404 4 : bitmap_initialize (&deps.reg_last_in_use, obstack);
5405 4 : bitmap_initialize (&deps.reg_last_dirty, obstack);
5406 4 : SET_REGNO_REG_SET (&deps.reg_last_in_use, 0);
5407 4 : SET_REGNO_REG_SET (&deps.reg_last_in_use, 2);
5408 4 : deps.reg_last[0].sets = alloc_INSN_LIST (setter0, NULL_RTX);
5409 4 : deps.reg_last[2].sets = alloc_INSN_LIST (setter2, NULL_RTX);
5410 4 : deps.pending_barriers = alloc_INSN_LIST (old_barrier, NULL_RTX);
5411 :
5412 4 : auto_vec<rtx_insn *> observed;
5413 4 : gcc_assert (!observed_barrier_deps);
5414 4 : observed_barrier_deps = &observed;
5415 4 : sched_analyze_insn (&deps, PATTERN (barrier), barrier);
5416 4 : observed_barrier_deps = NULL;
5417 :
5418 4 : ASSERT_EQ (3, observed.length ());
5419 4 : ASSERT_EQ (setter0, observed[0]);
5420 4 : ASSERT_EQ (old_barrier, observed[1]);
5421 4 : ASSERT_EQ (setter2, observed[2]);
5422 4 : ASSERT_TRUE (deps.pending_barriers);
5423 4 : ASSERT_EQ (barrier, deps.pending_barriers->insn ());
5424 4 : ASSERT_EQ (NULL, deps.pending_barriers->next ());
5425 :
5426 4 : free_deps (&deps);
5427 4 : }
5428 :
5429 : /* Verify all combinations of literal and lazy entries in deps_join.
5430 : OBSTACK owns both contexts' bitmaps. */
5431 :
5432 : static void
5433 4 : test_lazy_barrier_join (bitmap_obstack *obstack)
5434 : {
5435 4 : const int max_reg = 4;
5436 4 : deps_desc succ = {};
5437 4 : deps_desc pred = {};
5438 4 : succ.max_reg = max_reg;
5439 4 : pred.max_reg = max_reg;
5440 4 : succ.reg_last = alloc_reg_last (max_reg);
5441 4 : pred.reg_last = alloc_reg_last (max_reg);
5442 4 : bitmap_initialize (&succ.reg_last_in_use, obstack);
5443 4 : bitmap_initialize (&succ.reg_last_dirty, obstack);
5444 4 : bitmap_initialize (&pred.reg_last_in_use, obstack);
5445 4 : bitmap_initialize (&pred.reg_last_dirty, obstack);
5446 :
5447 4 : rtx_insn *p = make_insn_raw (gen_rtx_USE (VOIDmode, const0_rtx));
5448 4 : rtx_insn *q = make_insn_raw (gen_rtx_USE (VOIDmode, const0_rtx));
5449 4 : rtx_insn *a1 = make_insn_raw (gen_rtx_USE (VOIDmode, const0_rtx));
5450 4 : rtx_insn *p2 = make_insn_raw (gen_rtx_USE (VOIDmode, const0_rtx));
5451 4 : rtx_insn *a3 = make_insn_raw (gen_rtx_USE (VOIDmode, const0_rtx));
5452 4 : rtx_insn *p3 = make_insn_raw (gen_rtx_USE (VOIDmode, const0_rtx));
5453 :
5454 4 : succ.pending_barriers = alloc_INSN_LIST (q, NULL_RTX);
5455 4 : pred.pending_barriers = alloc_INSN_LIST (p, NULL_RTX);
5456 :
5457 4 : succ.reg_last[1].sets = alloc_INSN_LIST (a1, NULL_RTX);
5458 4 : SET_REGNO_REG_SET (&succ.reg_last_in_use, 1);
5459 4 : pred.reg_last[2].sets = alloc_INSN_LIST (p2, NULL_RTX);
5460 4 : SET_REGNO_REG_SET (&pred.reg_last_in_use, 2);
5461 4 : succ.reg_last[3].sets = alloc_INSN_LIST (a3, NULL_RTX);
5462 4 : pred.reg_last[3].sets = alloc_INSN_LIST (p3, NULL_RTX);
5463 4 : SET_REGNO_REG_SET (&succ.reg_last_in_use, 3);
5464 4 : SET_REGNO_REG_SET (&pred.reg_last_in_use, 3);
5465 :
5466 4 : deps_join (&succ, &pred);
5467 :
5468 4 : ASSERT_FALSE (REGNO_REG_SET_P (&succ.reg_last_in_use, 0));
5469 4 : ASSERT_TRUE (REGNO_REG_SET_P (&succ.reg_last_in_use, 1));
5470 4 : ASSERT_TRUE (REGNO_REG_SET_P (&succ.reg_last_in_use, 2));
5471 4 : ASSERT_TRUE (REGNO_REG_SET_P (&succ.reg_last_in_use, 3));
5472 4 : assert_insn_list (succ.pending_barriers, p, q);
5473 :
5474 4 : struct deps_reg *reg0 = deps_reg_last (&succ, 0);
5475 4 : assert_insn_list (reg0->sets, p, q);
5476 4 : assert_insn_list (succ.reg_last[1].sets, p, a1);
5477 4 : assert_insn_list (succ.reg_last[2].sets, p2, q);
5478 4 : assert_insn_list (succ.reg_last[3].sets, p3, a3);
5479 :
5480 4 : free_deps (&succ);
5481 4 : free_deps (&pred);
5482 4 : }
5483 :
5484 : /* Exercise lazy barriers with target-neutral raw insns. */
5485 :
5486 : static void
5487 4 : test_lazy_barriers ()
5488 : {
5489 4 : rtl_dump_test rtl_test (SELFTEST_LOCATION, locate_file ("cfg-test.rtl"));
5490 :
5491 4 : ASSERT_TRUE (sched_luids.is_empty ());
5492 4 : ASSERT_TRUE (h_d_i_d.is_empty ());
5493 4 : ASSERT_TRUE (reg_last_pool.is_empty ());
5494 4 : ASSERT_EQ (0, reg_last_pool_max_reg);
5495 4 : ASSERT_EQ (0, cache_size);
5496 4 : ASSERT_EQ (NULL, true_dependency_cache);
5497 4 : ASSERT_EQ (NULL, dn_pool);
5498 4 : ASSERT_EQ (NULL, dl_pool);
5499 :
5500 4 : rtx_insn *old_barrier
5501 4 : = make_insn_raw (gen_rtx_USE (VOIDmode, const0_rtx));
5502 4 : rtx_insn *setter = make_insn_raw (gen_rtx_USE (VOIDmode, const0_rtx));
5503 4 : start_sequence ();
5504 4 : rtx_insn *full_barrier
5505 4 : = emit_insn (gen_rtx_ASM_INPUT (VOIDmode, ""));
5506 4 : rtx_insn *sparse_old_barrier
5507 4 : = make_insn_raw (gen_rtx_USE (VOIDmode, const0_rtx));
5508 4 : rtx_insn *setter0 = make_insn_raw (gen_rtx_USE (VOIDmode, const0_rtx));
5509 4 : rtx_insn *setter2 = make_insn_raw (gen_rtx_USE (VOIDmode, const0_rtx));
5510 4 : rtx_insn *sparse_barrier
5511 4 : = emit_insn (gen_rtx_ASM_INPUT (VOIDmode, ""));
5512 4 : end_sequence ();
5513 4 : sched_luids.safe_grow_cleared (get_max_uid () + 1, true);
5514 :
5515 4 : bitmap_obstack test_obstack;
5516 4 : bitmap_obstack_initialize (&test_obstack);
5517 4 : bitmap_head pending_sets;
5518 4 : bitmap_head pending_clobbers;
5519 4 : bitmap_head pending_uses;
5520 4 : bitmap_head pending_control_uses;
5521 4 : bitmap_initialize (&pending_sets, &test_obstack);
5522 4 : bitmap_initialize (&pending_clobbers, &test_obstack);
5523 4 : bitmap_initialize (&pending_uses, &test_obstack);
5524 4 : bitmap_initialize (&pending_control_uses, &test_obstack);
5525 :
5526 4 : regset saved_pending_sets = reg_pending_sets;
5527 4 : regset saved_pending_clobbers = reg_pending_clobbers;
5528 4 : regset saved_pending_uses = reg_pending_uses;
5529 4 : regset saved_pending_control_uses = reg_pending_control_uses;
5530 4 : HARD_REG_SET saved_implicit_clobbers = implicit_reg_pending_clobbers;
5531 4 : HARD_REG_SET saved_implicit_uses = implicit_reg_pending_uses;
5532 4 : enum reg_pending_barrier_mode saved_pending_barrier = reg_pending_barrier;
5533 4 : sched_deps_info_def *saved_sched_deps_info = sched_deps_info;
5534 4 : haifa_sched_info *saved_current_sched_info = current_sched_info;
5535 4 : common_sched_info_def *saved_common_sched_info = common_sched_info;
5536 4 : int saved_reload_completed = reload_completed;
5537 4 : enum sched_pressure_algorithm saved_sched_pressure = sched_pressure;
5538 4 : bool saved_exposed_pipeline = targetm.sched.exposed_pipeline;
5539 :
5540 4 : reg_pending_sets = &pending_sets;
5541 4 : reg_pending_clobbers = &pending_clobbers;
5542 4 : reg_pending_uses = &pending_uses;
5543 4 : reg_pending_control_uses = &pending_control_uses;
5544 16 : CLEAR_HARD_REG_SET (implicit_reg_pending_clobbers);
5545 4 : CLEAR_HARD_REG_SET (implicit_reg_pending_uses);
5546 4 : reg_pending_barrier = NOT_A_BARRIER;
5547 :
5548 4 : sched_deps_info_def deps_info = {};
5549 4 : deps_info.note_dep = observe_barrier_dependence;
5550 4 : sched_deps_info = &deps_info;
5551 4 : haifa_sched_info sched_info = {};
5552 4 : current_sched_info = &sched_info;
5553 4 : common_sched_info_def common_info = haifa_common_sched_info;
5554 4 : common_sched_info = &common_info;
5555 4 : reload_completed = 0;
5556 4 : sched_pressure = SCHED_PRESSURE_NONE;
5557 4 : targetm.sched.exposed_pipeline = false;
5558 :
5559 4 : test_full_lazy_barrier (&test_obstack, full_barrier, old_barrier, setter);
5560 4 : test_sparse_lazy_barrier (&test_obstack, sparse_barrier,
5561 : sparse_old_barrier, setter0, setter2);
5562 4 : test_lazy_barrier_join (&test_obstack);
5563 :
5564 4 : ASSERT_TRUE (!observed_barrier_deps);
5565 4 : ASSERT_TRUE (deps_pools_are_empty_p ());
5566 4 : sched_deps_finish ();
5567 4 : sched_luids.release ();
5568 :
5569 4 : targetm.sched.exposed_pipeline = saved_exposed_pipeline;
5570 4 : sched_pressure = saved_sched_pressure;
5571 4 : reload_completed = saved_reload_completed;
5572 4 : common_sched_info = saved_common_sched_info;
5573 4 : current_sched_info = saved_current_sched_info;
5574 4 : sched_deps_info = saved_sched_deps_info;
5575 4 : reg_pending_barrier = saved_pending_barrier;
5576 4 : implicit_reg_pending_clobbers = saved_implicit_clobbers;
5577 4 : implicit_reg_pending_uses = saved_implicit_uses;
5578 4 : reg_pending_sets = saved_pending_sets;
5579 4 : reg_pending_clobbers = saved_pending_clobbers;
5580 4 : reg_pending_uses = saved_pending_uses;
5581 4 : reg_pending_control_uses = saved_pending_control_uses;
5582 4 : bitmap_obstack_release (&test_obstack);
5583 4 : }
5584 :
5585 : /* Run the sched-deps.cc selftests. */
5586 :
5587 : void
5588 4 : sched_deps_cc_tests ()
5589 : {
5590 4 : test_dirty_reg_last_release ();
5591 4 : test_reg_last_pool ();
5592 4 : test_lazy_barriers ();
5593 4 : }
5594 :
5595 : } // namespace selftest
5596 :
5597 : #endif
5598 :
5599 : #endif /* INSN_SCHEDULING */
5600 :
5601 : #if CHECKING_P && !defined (INSN_SCHEDULING)
5602 :
5603 : namespace selftest {
5604 :
5605 : void
5606 : sched_deps_cc_tests ()
5607 : {
5608 : }
5609 :
5610 : } // namespace selftest
5611 :
5612 : #endif
|
