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 670813839 : init_dep_1 (dep_t dep, rtx_insn *pro, rtx_insn *con, enum reg_note type, ds_t ds)
97 : {
98 670813839 : DEP_PRO (dep) = pro;
99 670813839 : DEP_CON (dep) = con;
100 670813839 : DEP_TYPE (dep) = type;
101 670813839 : DEP_STATUS (dep) = ds;
102 670813839 : DEP_COST (dep) = UNKNOWN_DEP_COST;
103 670813839 : DEP_NONREG (dep) = 0;
104 670813839 : DEP_MULTIPLE (dep) = 0;
105 670813839 : DEP_REPLACE (dep) = NULL;
106 670813839 : dep->unused = 0;
107 670813839 : }
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 638390609 : init_dep (dep_t dep, rtx_insn *pro, rtx_insn *con, enum reg_note kind)
114 : {
115 638390609 : ds_t ds;
116 :
117 638390609 : if ((current_sched_info->flags & USE_DEPS_LIST))
118 0 : ds = dk_to_ds (kind);
119 : else
120 : ds = 0;
121 :
122 638390609 : init_dep_1 (dep, pro, con, kind, ds);
123 638390609 : }
124 :
125 : /* Make a copy of FROM in TO. */
126 : static void
127 226879841 : copy_dep (dep_t to, dep_t from)
128 : {
129 226879841 : 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 1785354348 : depl_on_debug_p (dep_link_t dep)
227 : {
228 1785354348 : return (DEBUG_INSN_P (DEP_LINK_PRO (dep))
229 446032036 : && !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 892677174 : attach_dep_link (dep_link_t l, dep_link_t *prev_nextp)
239 : {
240 892677174 : dep_link_t next = *prev_nextp;
241 :
242 892677174 : gcc_assert (DEP_LINK_PREV_NEXTP (l) == NULL
243 : && DEP_LINK_NEXT (l) == NULL);
244 :
245 : /* Init node being inserted. */
246 892677174 : DEP_LINK_PREV_NEXTP (l) = prev_nextp;
247 892677174 : DEP_LINK_NEXT (l) = next;
248 :
249 : /* Fix next node. */
250 892677174 : if (next != NULL)
251 : {
252 491669950 : gcc_assert (DEP_LINK_PREV_NEXTP (next) == prev_nextp);
253 :
254 491669950 : DEP_LINK_PREV_NEXTP (next) = &DEP_LINK_NEXT (l);
255 : }
256 :
257 : /* Fix prev node. */
258 892677174 : *prev_nextp = l;
259 892677174 : }
260 :
261 : /* Add dep_link LINK to deps_list L. */
262 : static void
263 892677174 : add_to_deps_list (dep_link_t link, deps_list_t l)
264 : {
265 892677174 : attach_dep_link (link, &DEPS_LIST_FIRST (l));
266 :
267 : /* Don't count debug deps. */
268 892677174 : if (!depl_on_debug_p (link))
269 871515584 : ++DEPS_LIST_N_LINKS (l);
270 892677174 : }
271 :
272 : /* Detach dep_link L from the list. */
273 : static void
274 892677174 : detach_dep_link (dep_link_t l)
275 : {
276 892677174 : dep_link_t *prev_nextp = DEP_LINK_PREV_NEXTP (l);
277 892677174 : dep_link_t next = DEP_LINK_NEXT (l);
278 :
279 892677174 : *prev_nextp = next;
280 :
281 0 : if (next != NULL)
282 467138068 : DEP_LINK_PREV_NEXTP (next) = prev_nextp;
283 :
284 892677174 : DEP_LINK_PREV_NEXTP (l) = NULL;
285 892677174 : DEP_LINK_NEXT (l) = NULL;
286 0 : }
287 :
288 : /* Remove link LINK from list LIST. */
289 : static void
290 892677174 : remove_from_deps_list (dep_link_t link, deps_list_t list)
291 : {
292 892677174 : detach_dep_link (link);
293 :
294 : /* Don't count debug deps. */
295 892677174 : if (!depl_on_debug_p (link))
296 871515584 : --DEPS_LIST_N_LINKS (list);
297 892677174 : }
298 :
299 : /* Move link LINK from list FROM to list TO. */
300 : static void
301 438917492 : 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 220026766 : add_to_deps_list (link, to);
305 0 : }
306 :
307 : /* Return true of LINK is not attached to any list. */
308 : static bool
309 453759682 : dep_link_is_detached_p (dep_link_t link)
310 : {
311 453759682 : 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 226879841 : create_dep_node (void)
323 : {
324 226879841 : dep_node_t n = dn_pool->allocate ();
325 226879841 : dep_link_t back = DEP_NODE_BACK (n);
326 226879841 : dep_link_t forw = DEP_NODE_FORW (n);
327 :
328 226879841 : DEP_LINK_NODE (back) = n;
329 226879841 : DEP_LINK_NEXT (back) = NULL;
330 226879841 : DEP_LINK_PREV_NEXTP (back) = NULL;
331 :
332 226879841 : DEP_LINK_NODE (forw) = n;
333 226879841 : DEP_LINK_NEXT (forw) = NULL;
334 226879841 : DEP_LINK_PREV_NEXTP (forw) = NULL;
335 :
336 226879841 : ++dn_pool_diff;
337 :
338 226879841 : return n;
339 : }
340 :
341 : /* Delete dep_node N. N must not be connected to any deps_list. */
342 : static void
343 226879841 : delete_dep_node (dep_node_t n)
344 : {
345 226879841 : gcc_assert (dep_link_is_detached_p (DEP_NODE_BACK (n))
346 : && dep_link_is_detached_p (DEP_NODE_FORW (n)));
347 :
348 226879841 : XDELETE (DEP_REPLACE (DEP_NODE_DEP (n)));
349 :
350 226879841 : --dn_pool_diff;
351 :
352 226879841 : dn_pool->remove (n);
353 226879841 : }
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 1417311835 : deps_list_empty_p (deps_list_t l)
366 : {
367 1417311835 : return DEPS_LIST_N_LINKS (l) == 0;
368 : }
369 :
370 : /* Create a new deps_list. */
371 : static deps_list_t
372 580564170 : create_deps_list (void)
373 : {
374 580564170 : deps_list_t l = dl_pool->allocate ();
375 :
376 580564170 : DEPS_LIST_FIRST (l) = NULL;
377 580564170 : DEPS_LIST_N_LINKS (l) = 0;
378 :
379 580564170 : ++dl_pool_diff;
380 580564170 : return l;
381 : }
382 :
383 : /* Free deps_list L. */
384 : static void
385 580564170 : free_deps_list (deps_list_t l)
386 : {
387 580564170 : gcc_assert (deps_list_empty_p (l));
388 :
389 580564170 : --dl_pool_diff;
390 :
391 580564170 : dl_pool->remove (l);
392 580564170 : }
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 11619415 : deps_pools_are_empty_p (void)
399 : {
400 11619415 : return dn_pool_diff == 0 && dl_pool_diff == 0;
401 : }
402 :
403 : /* Remove all elements from L. */
404 : static void
405 116112834 : clear_deps_list (deps_list_t l)
406 : {
407 553913688 : do
408 : {
409 335013261 : dep_link_t link = DEPS_LIST_FIRST (l);
410 :
411 335013261 : if (link == NULL)
412 : break;
413 :
414 218900427 : remove_from_deps_list (link, l);
415 218900427 : }
416 : while (1);
417 116112834 : }
418 :
419 : /* Decide whether a dependency should be treated as a hard or a speculative
420 : dependency. */
421 : static bool
422 794533386 : dep_spec_p (dep_t dep)
423 : {
424 794533386 : if (current_sched_info->flags & DO_SPECULATION)
425 : {
426 0 : if (DEP_STATUS (dep) & SPECULATIVE)
427 : return true;
428 : }
429 794533386 : if (current_sched_info->flags & DO_PREDICATION)
430 : {
431 0 : if (DEP_TYPE (dep) == REG_DEP_CONTROL)
432 : return true;
433 : }
434 794533386 : if (DEP_REPLACE (dep) != NULL)
435 1136040 : 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 15773 : deps_may_trap_p (const_rtx mem)
506 : {
507 15773 : const_rtx addr = XEXP (mem, 0);
508 :
509 15773 : 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 15773 : addr = t;
514 : }
515 15773 : 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 64461867 : sched_get_condition_with_rev_uncached (const rtx_insn *insn, bool *rev)
524 : {
525 64461867 : rtx pat = PATTERN (insn);
526 64461867 : rtx src;
527 :
528 64461867 : if (rev)
529 64459355 : *rev = false;
530 :
531 64461867 : if (GET_CODE (pat) == COND_EXEC)
532 0 : return COND_EXEC_TEST (pat);
533 :
534 64461867 : if (!any_condjump_p (insn) || !onlyjump_p (insn))
535 : return 0;
536 :
537 4929093 : src = SET_SRC (pc_set (insn));
538 :
539 4929093 : if (XEXP (src, 2) == pc_rtx)
540 4929093 : 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 583869819 : sched_get_condition_with_rev (const rtx_insn *insn, bool *rev)
583 : {
584 583869819 : bool tmp;
585 :
586 583869819 : if (INSN_LUID (insn) == 0)
587 5504 : return sched_get_condition_with_rev_uncached (insn, rev);
588 :
589 583864315 : if (INSN_CACHED_COND (insn) == const_true_rtx)
590 : return NULL_RTX;
591 :
592 84985690 : if (INSN_CACHED_COND (insn) != NULL_RTX)
593 : {
594 20529327 : if (rev)
595 15597220 : *rev = INSN_REVERSE_COND (insn);
596 20529327 : return INSN_CACHED_COND (insn);
597 : }
598 :
599 64456363 : INSN_CACHED_COND (insn) = sched_get_condition_with_rev_uncached (insn, &tmp);
600 64456363 : INSN_REVERSE_COND (insn) = tmp;
601 :
602 64456363 : if (INSN_CACHED_COND (insn) == NULL_RTX)
603 : {
604 59527270 : INSN_CACHED_COND (insn) = const_true_rtx;
605 59527270 : return NULL_RTX;
606 : }
607 :
608 4929093 : if (rev)
609 0 : *rev = INSN_REVERSE_COND (insn);
610 4929093 : return INSN_CACHED_COND (insn);
611 : }
612 :
613 : /* True when we can find a condition under which INSN is executed. */
614 : static bool
615 66384402 : 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 4 : conditions_mutex_p (const_rtx cond1, const_rtx cond2, bool rev1, bool rev2)
625 : {
626 4 : if (COMPARISON_P (cond1)
627 4 : && COMPARISON_P (cond2)
628 4 : && GET_CODE (cond1) ==
629 : (rev1==rev2
630 4 : ? reversed_comparison_code (cond2, NULL)
631 : : GET_CODE (cond2))
632 0 : && rtx_equal_p (XEXP (cond1, 0), XEXP (cond2, 0))
633 4 : && 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 514980818 : sched_insns_conditions_mutex_p (const rtx_insn *insn1, const rtx_insn *insn2)
642 : {
643 514980818 : rtx cond1, cond2;
644 514980818 : bool rev1 = false, rev2 = false;
645 :
646 : /* df doesn't handle conditional lifetimes entirely correctly;
647 : calls mess up the conditional lifetimes. */
648 514980818 : if (!CALL_P (insn1) && !CALL_P (insn2))
649 : {
650 227754984 : cond1 = sched_get_condition_with_rev (insn1, &rev1);
651 227754984 : cond2 = sched_get_condition_with_rev (insn2, &rev2);
652 227754984 : if (cond1 && cond2
653 4 : && 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 227754984 : && !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 6195129402 : sd_next_list (const rtx_insn *insn, sd_list_types_def *types_ptr,
713 : deps_list_t *list_ptr, bool *resolved_p_ptr)
714 : {
715 6195129402 : sd_list_types_def types = *types_ptr;
716 :
717 6195129402 : if (types & SD_LIST_HARD_BACK)
718 : {
719 1456653155 : *list_ptr = INSN_HARD_BACK_DEPS (insn);
720 1456653155 : *resolved_p_ptr = false;
721 1456653155 : *types_ptr = types & ~SD_LIST_HARD_BACK;
722 : }
723 4738476247 : else if (types & SD_LIST_SPEC_BACK)
724 : {
725 938557724 : *list_ptr = INSN_SPEC_BACK_DEPS (insn);
726 938557724 : *resolved_p_ptr = false;
727 938557724 : *types_ptr = types & ~SD_LIST_SPEC_BACK;
728 : }
729 3799918523 : else if (types & SD_LIST_FORW)
730 : {
731 2244997913 : *list_ptr = INSN_FORW_DEPS (insn);
732 2244997913 : *resolved_p_ptr = false;
733 2244997913 : *types_ptr = types & ~SD_LIST_FORW;
734 : }
735 1554920610 : else if (types & SD_LIST_RES_BACK)
736 : {
737 978470250 : *list_ptr = INSN_RESOLVED_BACK_DEPS (insn);
738 978470250 : *resolved_p_ptr = true;
739 978470250 : *types_ptr = types & ~SD_LIST_RES_BACK;
740 : }
741 576450360 : else if (types & SD_LIST_RES_FORW)
742 : {
743 576450360 : *list_ptr = INSN_RESOLVED_FORW_DEPS (insn);
744 576450360 : *resolved_p_ptr = true;
745 576450360 : *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 6195129402 : }
754 :
755 : /* Return the summary size of INSN's lists defined by LIST_TYPES. */
756 : int
757 2713182684 : sd_lists_size (const rtx_insn *insn, sd_list_types_def list_types)
758 : {
759 2713182684 : int size = 0;
760 :
761 6015055532 : while (list_types != SD_LIST_NONE)
762 : {
763 3301872848 : deps_list_t list;
764 3301872848 : bool resolved_p;
765 :
766 3301872848 : sd_next_list (insn, &list_types, &list, &resolved_p);
767 3301872848 : if (list)
768 3301872848 : size += DEPS_LIST_N_LINKS (list);
769 : }
770 :
771 2713182684 : return size;
772 : }
773 :
774 : /* Return true if INSN's lists defined by LIST_TYPES are all empty. */
775 :
776 : bool
777 720577887 : sd_lists_empty_p (const rtx_insn *insn, sd_list_types_def list_types)
778 : {
779 1088010298 : while (list_types != SD_LIST_NONE)
780 : {
781 836747665 : deps_list_t list;
782 836747665 : bool resolved_p;
783 :
784 836747665 : sd_next_list (insn, &list_types, &list, &resolved_p);
785 836747665 : if (!deps_list_empty_p (list))
786 469315254 : return false;
787 : }
788 :
789 : return true;
790 : }
791 :
792 : /* Initialize data for INSN. */
793 : void
794 116112834 : sd_init_insn (rtx_insn *insn)
795 : {
796 116112834 : INSN_HARD_BACK_DEPS (insn) = create_deps_list ();
797 116112834 : INSN_SPEC_BACK_DEPS (insn) = create_deps_list ();
798 116112834 : INSN_RESOLVED_BACK_DEPS (insn) = create_deps_list ();
799 116112834 : INSN_FORW_DEPS (insn) = create_deps_list ();
800 116112834 : INSN_RESOLVED_FORW_DEPS (insn) = create_deps_list ();
801 :
802 : /* ??? It would be nice to allocate dependency caches here. */
803 116112834 : }
804 :
805 : /* Free data for INSN. */
806 : void
807 116112834 : sd_finish_insn (rtx_insn *insn)
808 : {
809 : /* ??? It would be nice to deallocate dependency caches here. */
810 :
811 116112834 : free_deps_list (INSN_HARD_BACK_DEPS (insn));
812 116112834 : INSN_HARD_BACK_DEPS (insn) = NULL;
813 :
814 116112834 : free_deps_list (INSN_SPEC_BACK_DEPS (insn));
815 116112834 : INSN_SPEC_BACK_DEPS (insn) = NULL;
816 :
817 116112834 : free_deps_list (INSN_RESOLVED_BACK_DEPS (insn));
818 116112834 : INSN_RESOLVED_BACK_DEPS (insn) = NULL;
819 :
820 116112834 : free_deps_list (INSN_FORW_DEPS (insn));
821 116112834 : INSN_FORW_DEPS (insn) = NULL;
822 :
823 116112834 : free_deps_list (INSN_RESOLVED_FORW_DEPS (insn));
824 116112834 : INSN_RESOLVED_FORW_DEPS (insn) = NULL;
825 116112834 : }
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 1018027094 : sd_find_dep_between_no_cache (rtx_insn *pro, rtx_insn *con, bool resolved_p,
834 : sd_iterator_def *sd_it_ptr)
835 : {
836 1018027094 : sd_list_types_def pro_list_type;
837 1018027094 : sd_list_types_def con_list_type;
838 1018027094 : sd_iterator_def sd_it;
839 1018027094 : dep_t dep;
840 1018027094 : bool found_p = false;
841 :
842 1018027094 : 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 573818020 : pro_list_type = SD_LIST_FORW;
850 573818020 : 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 1018027094 : 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 927609197 : FOR_EACH_DEP (con, con_list_type, sd_it, dep)
859 595539547 : 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 1066182731 : FOR_EACH_DEP (pro, pro_list_type, sd_it, dep)
869 768616565 : if (DEP_CON (dep) == con)
870 : {
871 : found_p = true;
872 : break;
873 : }
874 : }
875 :
876 1018027094 : if (found_p)
877 : {
878 388391278 : if (sd_it_ptr != NULL)
879 343793927 : *sd_it_ptr = sd_it;
880 :
881 388391278 : 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 449686529 : sd_find_dep_between (rtx_insn *pro, rtx_insn *con, bool resolved_p)
893 : {
894 449686529 : if (true_dependency_cache != NULL)
895 : /* Avoiding the list walk below can cut compile times dramatically
896 : for some code. */
897 : {
898 537657 : int elem_luid = INSN_LUID (pro);
899 537657 : int insn_luid = INSN_LUID (con);
900 :
901 537657 : if (!bitmap_bit_p (&true_dependency_cache[insn_luid], elem_luid)
902 521455 : && !bitmap_bit_p (&output_dependency_cache[insn_luid], elem_luid)
903 323276 : && !bitmap_bit_p (&anti_dependency_cache[insn_luid], elem_luid)
904 841331 : && !bitmap_bit_p (&control_dependency_cache[insn_luid], elem_luid))
905 : return NULL;
906 : }
907 :
908 449382855 : 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 670784696 : maybe_add_or_update_dep_1 (dep_t dep, bool resolved_p, rtx mem1, rtx mem2)
923 : {
924 670784696 : rtx_insn *elem = DEP_PRO (dep);
925 670784696 : rtx_insn *insn = DEP_CON (dep);
926 :
927 670784696 : gcc_assert (INSN_P (insn) && INSN_P (elem));
928 :
929 : /* Don't depend an insn on itself. */
930 670784696 : if (insn == elem)
931 : {
932 100110928 : 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 570673768 : 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 5084218 : ask_dependency_caches (dep_t dep)
951 : {
952 5084218 : int elem_luid = INSN_LUID (DEP_PRO (dep));
953 5084218 : int insn_luid = INSN_LUID (DEP_CON (dep));
954 :
955 5084218 : gcc_assert (true_dependency_cache != NULL
956 : && output_dependency_cache != NULL
957 : && anti_dependency_cache != NULL
958 : && control_dependency_cache != NULL);
959 :
960 5084218 : if (!(current_sched_info->flags & USE_DEPS_LIST))
961 : {
962 5084218 : enum reg_note present_dep_type;
963 :
964 5084218 : if (bitmap_bit_p (&true_dependency_cache[insn_luid], elem_luid))
965 : present_dep_type = REG_DEP_TRUE;
966 4850754 : else if (bitmap_bit_p (&output_dependency_cache[insn_luid], elem_luid))
967 : present_dep_type = REG_DEP_OUTPUT;
968 2246876 : else if (bitmap_bit_p (&anti_dependency_cache[insn_luid], elem_luid))
969 : present_dep_type = REG_DEP_ANTI;
970 2029529 : 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 2821225 : if ((int) DEP_TYPE (dep) >= (int) present_dep_type)
977 : /* DEP does not add anything to the existing dependence. */
978 3020223 : 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 2063995 : set_dependency_caches (dep_t dep)
1025 : {
1026 2063995 : int elem_luid = INSN_LUID (DEP_PRO (dep));
1027 2063995 : int insn_luid = INSN_LUID (DEP_CON (dep));
1028 :
1029 2063995 : if (!(current_sched_info->flags & USE_DEPS_LIST))
1030 : {
1031 2063995 : switch (DEP_TYPE (dep))
1032 : {
1033 327301 : case REG_DEP_TRUE:
1034 327301 : bitmap_set_bit (&true_dependency_cache[insn_luid], elem_luid);
1035 327301 : break;
1036 :
1037 380692 : case REG_DEP_OUTPUT:
1038 380692 : bitmap_set_bit (&output_dependency_cache[insn_luid], elem_luid);
1039 380692 : break;
1040 :
1041 1356002 : case REG_DEP_ANTI:
1042 1356002 : bitmap_set_bit (&anti_dependency_cache[insn_luid], elem_luid);
1043 1356002 : 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 2063995 : }
1073 :
1074 : /* Type of dependence DEP have changed from OLD_TYPE. Update dependency
1075 : caches accordingly. */
1076 : static void
1077 34466 : update_dependency_caches (dep_t dep, enum reg_note old_type)
1078 : {
1079 34466 : int elem_luid = INSN_LUID (DEP_PRO (dep));
1080 34466 : 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 34466 : if (!(current_sched_info->flags & USE_DEPS_LIST))
1085 : {
1086 34466 : switch (old_type)
1087 : {
1088 3125 : case REG_DEP_OUTPUT:
1089 3125 : bitmap_clear_bit (&output_dependency_cache[insn_luid], elem_luid);
1090 3125 : break;
1091 :
1092 31341 : case REG_DEP_ANTI:
1093 31341 : bitmap_clear_bit (&anti_dependency_cache[insn_luid], elem_luid);
1094 31341 : 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 34466 : set_dependency_caches (dep);
1106 34466 : }
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 340773704 : 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 340773704 : enum DEPS_ADJUST_RESULT res = DEP_PRESENT;
1139 340773704 : enum reg_note old_type = DEP_TYPE (dep);
1140 340773704 : bool was_spec = dep_spec_p (dep);
1141 :
1142 340773704 : DEP_NONREG (dep) |= DEP_NONREG (new_dep);
1143 340773704 : 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 340773704 : if ((int) DEP_TYPE (new_dep) < (int) old_type)
1149 : {
1150 19697696 : DEP_TYPE (dep) = DEP_TYPE (new_dep);
1151 19697696 : res = DEP_CHANGED;
1152 : }
1153 :
1154 340773704 : 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 340773704 : 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 340773704 : if (true_dependency_cache != NULL
1198 34466 : && res == DEP_CHANGED)
1199 34466 : update_dependency_caches (dep, old_type);
1200 :
1201 340773704 : 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 570673768 : add_or_update_dep_1 (dep_t new_dep, bool resolved_p,
1213 : rtx mem1 ATTRIBUTE_UNUSED, rtx mem2 ATTRIBUTE_UNUSED)
1214 : {
1215 570673768 : bool maybe_present_p = true;
1216 570673768 : bool present_p = false;
1217 :
1218 570673768 : 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 570673768 : if (flag_checking)
1222 570671809 : check_dep (new_dep, mem1 != NULL);
1223 :
1224 570673768 : if (true_dependency_cache != NULL)
1225 : {
1226 5084218 : switch (ask_dependency_caches (new_dep))
1227 : {
1228 3020223 : case DEP_PRESENT:
1229 3020223 : dep_t present_dep;
1230 3020223 : sd_iterator_def sd_it;
1231 :
1232 3020223 : present_dep = sd_find_dep_between_no_cache (DEP_PRO (new_dep),
1233 : DEP_CON (new_dep),
1234 : resolved_p, &sd_it);
1235 3020223 : DEP_MULTIPLE (present_dep) = 1;
1236 3020223 : return DEP_PRESENT;
1237 :
1238 : case DEP_CHANGED:
1239 : maybe_present_p = true;
1240 : present_p = true;
1241 2063995 : break;
1242 :
1243 2029529 : case DEP_CREATED:
1244 2029529 : maybe_present_p = false;
1245 2029529 : present_p = false;
1246 2029529 : break;
1247 :
1248 : default:
1249 : gcc_unreachable ();
1250 3020223 : break;
1251 : }
1252 : }
1253 :
1254 : /* Check that we don't already have this dependence. */
1255 2063995 : if (maybe_present_p)
1256 : {
1257 565624016 : dep_t present_dep;
1258 565624016 : sd_iterator_def sd_it;
1259 :
1260 565624016 : gcc_assert (true_dependency_cache == NULL || present_p);
1261 :
1262 565624016 : present_dep = sd_find_dep_between_no_cache (DEP_PRO (new_dep),
1263 : DEP_CON (new_dep),
1264 : resolved_p, &sd_it);
1265 :
1266 565624016 : if (present_dep != NULL)
1267 : /* We found an existing dependency between ELEM and INSN. */
1268 340773704 : 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 224850312 : 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 226879841 : 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 226879841 : sd_add_dep (new_dep, resolved_p);
1287 :
1288 226879841 : 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 453759682 : 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 453759682 : rtx_insn *con = DEP_CON (dep);
1300 :
1301 453759682 : if (!resolved_p)
1302 : {
1303 234868956 : if (dep_spec_p (dep))
1304 0 : *back_list_ptr = INSN_SPEC_BACK_DEPS (con);
1305 : else
1306 234868956 : *back_list_ptr = INSN_HARD_BACK_DEPS (con);
1307 :
1308 234868956 : *forw_list_ptr = INSN_FORW_DEPS (DEP_PRO (dep));
1309 : }
1310 : else
1311 : {
1312 218890726 : *back_list_ptr = INSN_RESOLVED_BACK_DEPS (con);
1313 218890726 : *forw_list_ptr = INSN_RESOLVED_FORW_DEPS (DEP_PRO (dep));
1314 : }
1315 453759682 : }
1316 :
1317 : /* Add dependence described by DEP.
1318 : If RESOLVED_P is true treat the dependence as a resolved one. */
1319 : void
1320 226879841 : sd_add_dep (dep_t dep, bool resolved_p)
1321 : {
1322 226879841 : dep_node_t n = create_dep_node ();
1323 226879841 : deps_list_t con_back_deps;
1324 226879841 : deps_list_t pro_forw_deps;
1325 226879841 : rtx_insn *elem = DEP_PRO (dep);
1326 226879841 : rtx_insn *insn = DEP_CON (dep);
1327 :
1328 226879841 : gcc_assert (INSN_P (insn) && INSN_P (elem) && insn != elem);
1329 :
1330 226879841 : if ((current_sched_info->flags & DO_SPECULATION) == 0
1331 226879841 : || !sched_insn_is_legitimate_for_speculation_p (insn, DEP_STATUS (dep)))
1332 226879841 : DEP_STATUS (dep) &= ~SPECULATIVE;
1333 :
1334 226879841 : copy_dep (DEP_NODE_DEP (n), dep);
1335 :
1336 226879841 : get_back_and_forw_lists (dep, resolved_p, &con_back_deps, &pro_forw_deps);
1337 :
1338 226879841 : add_to_deps_list (DEP_NODE_BACK (n), con_back_deps);
1339 :
1340 226879841 : if (flag_checking)
1341 226879518 : check_dep (dep, false);
1342 :
1343 226879841 : 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 226879841 : if (true_dependency_cache != NULL)
1348 2029529 : set_dependency_caches (dep);
1349 226879841 : }
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 218890726 : sd_resolve_dep (sd_iterator_def sd_it)
1364 : {
1365 218890726 : dep_node_t node = DEP_LINK_NODE (*sd_it.linkp);
1366 218890726 : dep_t dep = DEP_NODE_DEP (node);
1367 218890726 : rtx_insn *pro = DEP_PRO (dep);
1368 218890726 : rtx_insn *con = DEP_CON (dep);
1369 :
1370 218890726 : if (dep_spec_p (dep))
1371 1136040 : move_dep_link (DEP_NODE_BACK (node), INSN_SPEC_BACK_DEPS (con),
1372 1136040 : INSN_RESOLVED_BACK_DEPS (con));
1373 : else
1374 217754686 : move_dep_link (DEP_NODE_BACK (node), INSN_HARD_BACK_DEPS (con),
1375 217754686 : INSN_RESOLVED_BACK_DEPS (con));
1376 :
1377 656672178 : move_dep_link (DEP_NODE_FORW (node), INSN_FORW_DEPS (pro),
1378 218890726 : INSN_RESOLVED_FORW_DEPS (pro));
1379 218890726 : }
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 7979414 : sd_delete_dep (sd_iterator_def sd_it)
1427 : {
1428 7979414 : dep_node_t n = DEP_LINK_NODE (*sd_it.linkp);
1429 7979414 : dep_t dep = DEP_NODE_DEP (n);
1430 7979414 : rtx_insn *pro = DEP_PRO (dep);
1431 7979414 : rtx_insn *con = DEP_CON (dep);
1432 7979414 : deps_list_t con_back_deps;
1433 7979414 : deps_list_t pro_forw_deps;
1434 :
1435 7979414 : if (true_dependency_cache != NULL)
1436 : {
1437 3158 : int elem_luid = INSN_LUID (pro);
1438 3158 : int insn_luid = INSN_LUID (con);
1439 :
1440 3158 : bitmap_clear_bit (&true_dependency_cache[insn_luid], elem_luid);
1441 3158 : bitmap_clear_bit (&anti_dependency_cache[insn_luid], elem_luid);
1442 3158 : bitmap_clear_bit (&control_dependency_cache[insn_luid], elem_luid);
1443 3158 : bitmap_clear_bit (&output_dependency_cache[insn_luid], elem_luid);
1444 :
1445 3158 : if (current_sched_info->flags & DO_SPECULATION)
1446 0 : bitmap_clear_bit (&spec_dependency_cache[insn_luid], elem_luid);
1447 : }
1448 :
1449 7979414 : get_back_and_forw_lists (dep, sd_it.resolved_p,
1450 : &con_back_deps, &pro_forw_deps);
1451 :
1452 7979414 : remove_from_deps_list (DEP_NODE_BACK (n), con_back_deps);
1453 7979414 : remove_from_deps_list (DEP_NODE_FORW (n), pro_forw_deps);
1454 :
1455 7979414 : delete_dep_node (n);
1456 7979414 : }
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 *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 *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 630593562 : add_dependence (rtx_insn *con, rtx_insn *pro, enum reg_note dep_type)
1516 : {
1517 630593562 : if (dep_type == REG_DEP_CONTROL
1518 16469 : && !(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 630593562 : add_dependence_1 (con, pro, dep_type);
1557 630593562 : }
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 3298739295 : add_dependence_list (rtx_insn *insn, rtx_insn_list *list, int uncond,
1564 : enum reg_note dep_type, bool hard)
1565 : {
1566 3298739295 : mark_as_hard = hard;
1567 3804998589 : for (; list; list = list->next ())
1568 : {
1569 946690080 : if (uncond || ! sched_insns_conditions_mutex_p (insn, list->insn ()))
1570 506259294 : add_dependence (insn, list->insn (), dep_type);
1571 : }
1572 3298739295 : mark_as_hard = false;
1573 3298739295 : }
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 1260213158 : 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 1260213158 : 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 1260213158 : if (deps->readonly || DEBUG_INSN_P (insn))
1590 : return;
1591 :
1592 1260130077 : 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 63246 : remove_from_dependence_list (rtx_insn *insn, rtx_insn_list **listp)
1600 : {
1601 63246 : int removed = 0;
1602 :
1603 129450 : while (*listp)
1604 : {
1605 66204 : if ((*listp)->insn () == insn)
1606 : {
1607 13283 : remove_free_INSN_LIST_node (listp);
1608 13283 : removed++;
1609 13283 : continue;
1610 : }
1611 :
1612 52921 : listp = (rtx_insn_list **)&XEXP (*listp, 1);
1613 : }
1614 :
1615 63246 : return removed;
1616 : }
1617 :
1618 : /* Same as above, but process two lists at once. */
1619 : static int
1620 4586 : remove_from_both_dependence_lists (rtx_insn *insn,
1621 : rtx_insn_list **listp,
1622 : rtx_expr_list **exprp)
1623 : {
1624 4586 : int removed = 0;
1625 :
1626 8898 : while (*listp)
1627 : {
1628 4312 : if (XEXP (*listp, 0) == insn)
1629 : {
1630 664 : remove_free_INSN_LIST_node (listp);
1631 664 : remove_free_EXPR_LIST_node (exprp);
1632 664 : removed++;
1633 664 : continue;
1634 : }
1635 :
1636 3648 : listp = (rtx_insn_list **)&XEXP (*listp, 1);
1637 3648 : exprp = (rtx_expr_list **)&XEXP (*exprp, 1);
1638 : }
1639 :
1640 4586 : return removed;
1641 : }
1642 :
1643 : /* Clear all dependencies for an insn. */
1644 : static void
1645 4250569 : delete_all_dependences (rtx_insn *insn)
1646 : {
1647 4250569 : sd_iterator_def sd_it;
1648 4250569 : 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 4250569 : for (sd_it = sd_iterator_start (insn, SD_LIST_BACK);
1655 12080202 : sd_iterator_cond (&sd_it, &dep);)
1656 7829633 : sd_delete_dep (sd_it);
1657 4250569 : }
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 4250569 : chain_to_prev_insn (rtx_insn *insn)
1667 : {
1668 4250569 : sd_iterator_def sd_it;
1669 4250569 : dep_t dep;
1670 4250569 : rtx_insn *prev_nonnote;
1671 :
1672 12080202 : FOR_EACH_DEP (insn, SD_LIST_BACK, sd_it, dep)
1673 : {
1674 7829633 : rtx_insn *i = insn;
1675 7829633 : rtx_insn *pro = DEP_PRO (dep);
1676 :
1677 7832015 : do
1678 : {
1679 7832015 : i = prev_nonnote_insn (i);
1680 :
1681 7832015 : if (pro == i)
1682 4250541 : goto next_link;
1683 3583856 : } while (SCHED_GROUP_P (i) || DEBUG_INSN_P (i));
1684 :
1685 3579092 : if (! sched_insns_conditions_mutex_p (i, pro))
1686 3579092 : add_dependence (i, pro, DEP_TYPE (dep));
1687 7829633 : next_link:;
1688 : }
1689 :
1690 4250569 : delete_all_dependences (insn);
1691 :
1692 4250569 : prev_nonnote = prev_nonnote_nondebug_insn (insn);
1693 4250569 : if (BLOCK_FOR_INSN (insn) == BLOCK_FOR_INSN (prev_nonnote)
1694 4250569 : && ! sched_insns_conditions_mutex_p (insn, prev_nonnote))
1695 4250569 : add_dependence (insn, prev_nonnote, REG_DEP_ANTI);
1696 4250569 : }
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 39155915 : add_insn_mem_dependence (class deps_desc *deps, bool read_p,
1715 : rtx_insn *insn, rtx mem)
1716 : {
1717 39155915 : rtx_insn_list **insn_list;
1718 39155915 : rtx_insn_list *insn_node;
1719 39155915 : rtx_expr_list **mem_list;
1720 39155915 : rtx_expr_list *mem_node;
1721 :
1722 39155915 : gcc_assert (!deps->readonly);
1723 39155915 : if (read_p)
1724 : {
1725 1741190 : insn_list = &deps->pending_read_insns;
1726 26422048 : mem_list = &deps->pending_read_mems;
1727 26422048 : if (!DEBUG_INSN_P (insn))
1728 24680858 : deps->pending_read_list_length++;
1729 : }
1730 : else
1731 : {
1732 12733867 : insn_list = &deps->pending_write_insns;
1733 12733867 : mem_list = &deps->pending_write_mems;
1734 12733867 : deps->pending_write_list_length++;
1735 : }
1736 :
1737 39155915 : insn_node = alloc_INSN_LIST (insn, *insn_list);
1738 39155915 : *insn_list = insn_node;
1739 :
1740 39155915 : 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 39155915 : mem_node = alloc_EXPR_LIST (VOIDmode, canon_rtx (mem), *mem_list);
1747 39155915 : *mem_list = mem_node;
1748 39155915 : }
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 9819155 : flush_pending_lists (class deps_desc *deps, rtx_insn *insn, int for_read,
1756 : int for_write)
1757 : {
1758 9819155 : if (for_write)
1759 : {
1760 9399937 : add_dependence_list_and_free (deps, insn, &deps->pending_read_insns,
1761 : 1, REG_DEP_ANTI, true);
1762 9399937 : if (!deps->readonly)
1763 : {
1764 9398801 : free_EXPR_LIST_list (&deps->pending_read_mems);
1765 9398801 : deps->pending_read_list_length = 0;
1766 : }
1767 : }
1768 :
1769 9839281 : 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 9819155 : 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 9819155 : add_dependence_list_and_free (deps, insn, &deps->pending_jump_insns, 1,
1779 : REG_DEP_ANTI, true);
1780 :
1781 9819155 : 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 9819155 : if (!deps->readonly)
1791 : {
1792 9817980 : free_EXPR_LIST_list (&deps->pending_write_mems);
1793 9817980 : deps->pending_write_list_length = 0;
1794 :
1795 9817980 : deps->last_pending_memory_flush = alloc_INSN_LIST (insn, NULL_RTX);
1796 9817980 : deps->pending_flush_length = 1;
1797 : }
1798 9819155 : mark_as_hard = false;
1799 9819155 : }
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 122074366 : haifa_start_insn (rtx_insn *insn)
1808 : {
1809 122074366 : gcc_assert (insn && !cur_insn);
1810 :
1811 122074366 : cur_insn = insn;
1812 122074366 : }
1813 :
1814 : static void
1815 122074366 : haifa_finish_insn (void)
1816 : {
1817 122074366 : cur_insn = NULL;
1818 122074366 : }
1819 :
1820 : void
1821 39804473 : haifa_note_reg_set (int regno)
1822 : {
1823 39804473 : SET_REGNO_REG_SET (reg_pending_sets, regno);
1824 39804473 : }
1825 :
1826 : void
1827 11569748 : haifa_note_reg_clobber (int regno)
1828 : {
1829 11569748 : SET_REGNO_REG_SET (reg_pending_clobbers, regno);
1830 11569748 : }
1831 :
1832 : void
1833 83367524 : haifa_note_reg_use (int regno)
1834 : {
1835 83367524 : SET_REGNO_REG_SET (reg_pending_uses, regno);
1836 83367524 : }
1837 :
1838 : static void
1839 32423230 : haifa_note_mem_dep (rtx mem, rtx pending_mem, rtx_insn *pending_insn, ds_t ds)
1840 : {
1841 32423230 : 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 32423230 : {
1850 32423230 : dep_def _dep, *dep = &_dep;
1851 :
1852 32423230 : init_dep_1 (dep, pending_insn, cur_insn, ds_to_dt (ds),
1853 32423230 : current_sched_info->flags & USE_DEPS_LIST ? ds : 0);
1854 32423230 : DEP_NONREG (dep) = 1;
1855 32423230 : maybe_add_or_update_dep_1 (dep, false, pending_mem, mem);
1856 : }
1857 :
1858 32423230 : }
1859 :
1860 : static void
1861 638361466 : haifa_note_dep (rtx_insn *elem, ds_t ds)
1862 : {
1863 638361466 : dep_def _dep;
1864 638361466 : dep_t dep = &_dep;
1865 :
1866 638361466 : init_dep (dep, elem, cur_insn, ds_to_dt (ds));
1867 638361466 : if (mark_as_hard)
1868 317690218 : DEP_NONREG (dep) = 1;
1869 638361466 : maybe_add_or_update_dep_1 (dep, false, NULL_RTX, NULL_RTX);
1870 638361466 : }
1871 :
1872 : static void
1873 83386964 : note_reg_use (int r)
1874 : {
1875 0 : if (sched_deps_info->note_reg_use)
1876 83386964 : sched_deps_info->note_reg_use (r);
1877 0 : }
1878 :
1879 : static void
1880 39821939 : note_reg_set (int r)
1881 : {
1882 0 : if (sched_deps_info->note_reg_set)
1883 39821939 : sched_deps_info->note_reg_set (r);
1884 0 : }
1885 :
1886 : static void
1887 11571353 : note_reg_clobber (int r)
1888 : {
1889 0 : if (sched_deps_info->note_reg_clobber)
1890 11571353 : sched_deps_info->note_reg_clobber (r);
1891 0 : }
1892 :
1893 : static void
1894 32427985 : note_mem_dep (rtx m1, rtx m2, rtx_insn *e, ds_t ds)
1895 : {
1896 17512377 : if (sched_deps_info->note_mem_dep)
1897 32426682 : sched_deps_info->note_mem_dep (m1, m2, e, ds);
1898 0 : }
1899 :
1900 : static void
1901 638402782 : note_dep (rtx_insn *e, ds_t ds)
1902 : {
1903 0 : if (sched_deps_info->note_dep)
1904 638388893 : sched_deps_info->note_dep (e, ds);
1905 0 : }
1906 :
1907 : /* Return corresponding to DS reg_note. */
1908 : enum reg_note
1909 670816854 : ds_to_dt (ds_t ds)
1910 : {
1911 670816854 : if (ds & DEP_TRUE)
1912 : return REG_DEP_TRUE;
1913 545962645 : else if (ds & DEP_OUTPUT)
1914 : return REG_DEP_OUTPUT;
1915 464751282 : 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 2489 : create_insn_reg_use (int regno, rtx_insn *insn)
1933 : {
1934 2489 : struct reg_use_data *use;
1935 :
1936 2489 : use = (struct reg_use_data *) xmalloc (sizeof (struct reg_use_data));
1937 2489 : use->regno = regno;
1938 2489 : use->insn = insn;
1939 2489 : use->next_insn_use = INSN_REG_USE_LIST (insn);
1940 2489 : INSN_REG_USE_LIST (insn) = use;
1941 2489 : return use;
1942 : }
1943 :
1944 : /* Allocate reg_set_data structure for REGNO and INSN. */
1945 : static void
1946 2323 : create_insn_reg_set (int regno, rtx_insn *insn)
1947 : {
1948 2323 : struct reg_set_data *set;
1949 :
1950 2323 : set = (struct reg_set_data *) xmalloc (sizeof (struct reg_set_data));
1951 2323 : set->regno = regno;
1952 2323 : set->insn = insn;
1953 2323 : set->next_insn_set = INSN_REG_SET_LIST (insn);
1954 2323 : INSN_REG_SET_LIST (insn) = set;
1955 2323 : }
1956 :
1957 : /* Set up insn register uses for INSN and dependency context DEPS. */
1958 : static void
1959 5262 : setup_insn_reg_uses (class deps_desc *deps, rtx_insn *insn)
1960 : {
1961 5262 : unsigned i;
1962 5262 : reg_set_iterator rsi;
1963 5262 : struct reg_use_data *use, *use2, *next;
1964 5262 : struct deps_reg *reg_last;
1965 :
1966 9929 : EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i, rsi)
1967 : {
1968 5682 : if (i < FIRST_PSEUDO_REGISTER
1969 4667 : && TEST_HARD_REG_BIT (ira_no_alloc_regs, i))
1970 1015 : continue;
1971 :
1972 3652 : if (find_regno_note (insn, REG_DEAD, i) == NULL_RTX
1973 1768 : && ! REGNO_REG_SET_P (reg_pending_sets, i)
1974 5137 : && ! REGNO_REG_SET_P (reg_pending_clobbers, i))
1975 : /* Ignore use which is not dying. */
1976 1485 : continue;
1977 :
1978 2167 : use = create_insn_reg_use (i, insn);
1979 2167 : use->next_regno_use = use;
1980 2167 : reg_last = &deps->reg_last[i];
1981 :
1982 : /* Create the cycle list of uses. */
1983 2489 : 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 5262 : }
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 2323 : insn_use_p (rtx_insn *insn, int regno)
1999 : {
2000 2323 : struct reg_use_data *use;
2001 :
2002 3362 : for (use = INSN_REG_USE_LIST (insn); use != NULL; use = use->next_insn_use)
2003 1287 : 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 1713 : mark_insn_pseudo_birth (rtx_insn *insn, int regno, bool clobber_p,
2013 : bool unused_p)
2014 : {
2015 1713 : int incr, new_incr;
2016 1713 : enum reg_class cl;
2017 :
2018 1713 : gcc_assert (regno >= FIRST_PSEUDO_REGISTER);
2019 1713 : cl = sched_regno_pressure_class[regno];
2020 1713 : if (cl != NO_REGS)
2021 : {
2022 1706 : incr = ira_reg_class_max_nregs[cl][PSEUDO_REGNO_MODE (regno)];
2023 1706 : if (clobber_p)
2024 : {
2025 3 : new_incr = reg_pressure_info[cl].clobber_increase + incr;
2026 3 : reg_pressure_info[cl].clobber_increase = new_incr;
2027 : }
2028 1703 : else if (unused_p)
2029 : {
2030 67 : new_incr = reg_pressure_info[cl].unused_set_increase + incr;
2031 67 : reg_pressure_info[cl].unused_set_increase = new_incr;
2032 : }
2033 : else
2034 : {
2035 1636 : new_incr = reg_pressure_info[cl].set_increase + incr;
2036 1636 : reg_pressure_info[cl].set_increase = new_incr;
2037 1636 : if (! insn_use_p (insn, regno))
2038 1432 : reg_pressure_info[cl].change += incr;
2039 1636 : create_insn_reg_set (regno, insn);
2040 : }
2041 1706 : gcc_assert (new_incr < (1 << INCREASE_BITS));
2042 : }
2043 1713 : }
2044 :
2045 : /* Like mark_insn_pseudo_regno_birth except that NREGS saying how many
2046 : hard registers involved in the birth. */
2047 : static void
2048 1628 : mark_insn_hard_regno_birth (rtx_insn *insn, int regno, int nregs,
2049 : bool clobber_p, bool unused_p)
2050 : {
2051 1628 : enum reg_class cl;
2052 1628 : int new_incr, last = regno + nregs;
2053 :
2054 3258 : while (regno < last)
2055 : {
2056 1630 : gcc_assert (regno < FIRST_PSEUDO_REGISTER);
2057 1630 : if (! TEST_HARD_REG_BIT (ira_no_alloc_regs, regno))
2058 : {
2059 749 : cl = sched_regno_pressure_class[regno];
2060 749 : if (cl != NO_REGS)
2061 : {
2062 749 : if (clobber_p)
2063 : {
2064 1 : new_incr = reg_pressure_info[cl].clobber_increase + 1;
2065 1 : reg_pressure_info[cl].clobber_increase = new_incr;
2066 : }
2067 748 : else if (unused_p)
2068 : {
2069 61 : new_incr = reg_pressure_info[cl].unused_set_increase + 1;
2070 61 : reg_pressure_info[cl].unused_set_increase = new_incr;
2071 : }
2072 : else
2073 : {
2074 687 : new_incr = reg_pressure_info[cl].set_increase + 1;
2075 687 : reg_pressure_info[cl].set_increase = new_incr;
2076 687 : if (! insn_use_p (insn, regno))
2077 643 : reg_pressure_info[cl].change += 1;
2078 687 : create_insn_reg_set (regno, insn);
2079 : }
2080 749 : gcc_assert (new_incr < (1 << INCREASE_BITS));
2081 : }
2082 : }
2083 1630 : regno++;
2084 : }
2085 1628 : }
2086 :
2087 : /* Update the register pressure info after birth of pseudo or hard
2088 : register REG in INSN. Arguments CLOBBER_P and UNUSED_P say
2089 : correspondingly that the register is in clobber or unused after the
2090 : insn. */
2091 : static void
2092 4196 : mark_insn_reg_birth (rtx_insn *insn, rtx reg, bool clobber_p, bool unused_p)
2093 : {
2094 4196 : int regno;
2095 :
2096 4196 : if (GET_CODE (reg) == SUBREG)
2097 0 : reg = SUBREG_REG (reg);
2098 :
2099 4196 : if (! REG_P (reg))
2100 : return;
2101 :
2102 3341 : regno = REGNO (reg);
2103 3341 : if (regno < FIRST_PSEUDO_REGISTER)
2104 1628 : mark_insn_hard_regno_birth (insn, regno, REG_NREGS (reg),
2105 : clobber_p, unused_p);
2106 : else
2107 1713 : mark_insn_pseudo_birth (insn, regno, clobber_p, unused_p);
2108 : }
2109 :
2110 : /* Update the register pressure info after death of pseudo register
2111 : REGNO. */
2112 : static void
2113 1207 : mark_pseudo_death (int regno)
2114 : {
2115 1207 : int incr;
2116 1207 : enum reg_class cl;
2117 :
2118 1207 : gcc_assert (regno >= FIRST_PSEUDO_REGISTER);
2119 1207 : cl = sched_regno_pressure_class[regno];
2120 1207 : if (cl != NO_REGS)
2121 : {
2122 1203 : incr = ira_reg_class_max_nregs[cl][PSEUDO_REGNO_MODE (regno)];
2123 1203 : reg_pressure_info[cl].change -= incr;
2124 : }
2125 1207 : }
2126 :
2127 : /* Like mark_pseudo_death except that NREGS saying how many hard
2128 : registers involved in the death. */
2129 : static void
2130 1082 : mark_hard_regno_death (int regno, int nregs)
2131 : {
2132 1082 : enum reg_class cl;
2133 1082 : int last = regno + nregs;
2134 :
2135 2164 : while (regno < last)
2136 : {
2137 1082 : gcc_assert (regno < FIRST_PSEUDO_REGISTER);
2138 1082 : if (! TEST_HARD_REG_BIT (ira_no_alloc_regs, regno))
2139 : {
2140 677 : cl = sched_regno_pressure_class[regno];
2141 677 : if (cl != NO_REGS)
2142 677 : reg_pressure_info[cl].change -= 1;
2143 : }
2144 1082 : regno++;
2145 : }
2146 1082 : }
2147 :
2148 : /* Update the register pressure info after death of pseudo or hard
2149 : register REG. */
2150 : static void
2151 2289 : mark_reg_death (rtx reg)
2152 : {
2153 2289 : int regno;
2154 :
2155 2289 : if (GET_CODE (reg) == SUBREG)
2156 0 : reg = SUBREG_REG (reg);
2157 :
2158 2289 : if (! REG_P (reg))
2159 : return;
2160 :
2161 2289 : regno = REGNO (reg);
2162 2289 : if (regno < FIRST_PSEUDO_REGISTER)
2163 1082 : mark_hard_regno_death (regno, REG_NREGS (reg));
2164 : else
2165 1207 : mark_pseudo_death (regno);
2166 : }
2167 :
2168 : /* Process SETTER of REG. DATA is an insn containing the setter. */
2169 : static void
2170 4196 : mark_insn_reg_store (rtx reg, const_rtx setter, void *data)
2171 : {
2172 4196 : if (setter != NULL_RTX && GET_CODE (setter) != SET)
2173 : return;
2174 3718 : mark_insn_reg_birth
2175 3718 : ((rtx_insn *) data, reg, false,
2176 3718 : find_reg_note ((const_rtx) data, REG_UNUSED, reg) != NULL_RTX);
2177 : }
2178 :
2179 : /* Like mark_insn_reg_store except notice just CLOBBERs; ignore SETs. */
2180 : static void
2181 4196 : mark_insn_reg_clobber (rtx reg, const_rtx setter, void *data)
2182 : {
2183 4196 : if (GET_CODE (setter) == CLOBBER)
2184 478 : mark_insn_reg_birth ((rtx_insn *) data, reg, true, false);
2185 4196 : }
2186 :
2187 : /* Set up reg pressure info related to INSN. */
2188 : void
2189 5262 : init_insn_reg_pressure_info (rtx_insn *insn)
2190 : {
2191 5262 : int i, len;
2192 5262 : enum reg_class cl;
2193 5262 : static struct reg_pressure_data *pressure_info;
2194 5262 : rtx link;
2195 :
2196 5262 : gcc_assert (sched_pressure != SCHED_PRESSURE_NONE);
2197 :
2198 5262 : if (! INSN_P (insn))
2199 : return;
2200 :
2201 26586 : for (i = 0; i < ira_pressure_classes_num; i++)
2202 : {
2203 21324 : cl = ira_pressure_classes[i];
2204 21324 : reg_pressure_info[cl].clobber_increase = 0;
2205 21324 : reg_pressure_info[cl].set_increase = 0;
2206 21324 : reg_pressure_info[cl].unused_set_increase = 0;
2207 21324 : reg_pressure_info[cl].change = 0;
2208 : }
2209 :
2210 5262 : note_stores (insn, mark_insn_reg_clobber, insn);
2211 :
2212 5262 : note_stores (insn, mark_insn_reg_store, insn);
2213 :
2214 5262 : if (AUTO_INC_DEC)
2215 : for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
2216 : if (REG_NOTE_KIND (link) == REG_INC)
2217 : mark_insn_reg_store (XEXP (link, 0), NULL_RTX, insn);
2218 :
2219 9222 : for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
2220 3960 : if (REG_NOTE_KIND (link) == REG_DEAD)
2221 2289 : mark_reg_death (XEXP (link, 0));
2222 :
2223 5262 : len = sizeof (struct reg_pressure_data) * ira_pressure_classes_num;
2224 5262 : pressure_info
2225 5262 : = INSN_REG_PRESSURE (insn) = (struct reg_pressure_data *) xmalloc (len);
2226 5262 : if (sched_pressure == SCHED_PRESSURE_WEIGHTED)
2227 5262 : INSN_MAX_REG_PRESSURE (insn) = (int *) xcalloc (ira_pressure_classes_num
2228 : * sizeof (int), 1);
2229 26586 : for (i = 0; i < ira_pressure_classes_num; i++)
2230 : {
2231 21324 : cl = ira_pressure_classes[i];
2232 21324 : pressure_info[i].clobber_increase
2233 21324 : = reg_pressure_info[cl].clobber_increase;
2234 21324 : pressure_info[i].set_increase = reg_pressure_info[cl].set_increase;
2235 21324 : pressure_info[i].unused_set_increase
2236 21324 : = reg_pressure_info[cl].unused_set_increase;
2237 21324 : pressure_info[i].change = reg_pressure_info[cl].change;
2238 : }
2239 : }
2240 :
2241 :
2242 :
2243 :
2244 : /* Internal variable for sched_analyze_[12] () functions.
2245 : If it is nonzero, this means that sched_analyze_[12] looks
2246 : at the most toplevel SET. */
2247 : static bool can_start_lhs_rhs_p;
2248 :
2249 : /* Extend reg info for the deps context DEPS given that
2250 : we have just generated a register numbered REGNO. */
2251 : static void
2252 802 : extend_deps_reg_info (class deps_desc *deps, int regno)
2253 : {
2254 802 : int max_regno = regno + 1;
2255 :
2256 802 : gcc_assert (!reload_completed);
2257 :
2258 : /* In a readonly context, it would not hurt to extend info,
2259 : but it should not be needed. */
2260 802 : if (reload_completed && deps->readonly)
2261 : {
2262 : deps->max_reg = max_regno;
2263 : return;
2264 : }
2265 :
2266 802 : if (max_regno > deps->max_reg)
2267 : {
2268 183 : deps->reg_last = XRESIZEVEC (struct deps_reg, deps->reg_last,
2269 : max_regno);
2270 183 : memset (&deps->reg_last[deps->max_reg],
2271 183 : 0, (max_regno - deps->max_reg)
2272 : * sizeof (struct deps_reg));
2273 183 : deps->max_reg = max_regno;
2274 : }
2275 : }
2276 :
2277 : /* Extends REG_INFO_P if needed. */
2278 : void
2279 134519107 : maybe_extend_reg_info_p (void)
2280 : {
2281 : /* Extend REG_INFO_P, if needed. */
2282 134519107 : if ((unsigned int)max_regno - 1 >= reg_info_p_size)
2283 : {
2284 16 : size_t new_reg_info_p_size = max_regno + 128;
2285 :
2286 16 : gcc_assert (!reload_completed && sel_sched_p ());
2287 :
2288 16 : reg_info_p = (struct reg_info_t *) xrecalloc (reg_info_p,
2289 : new_reg_info_p_size,
2290 : reg_info_p_size,
2291 : sizeof (*reg_info_p));
2292 16 : reg_info_p_size = new_reg_info_p_size;
2293 : }
2294 134519107 : }
2295 :
2296 : /* Analyze a single reference to register (reg:MODE REGNO) in INSN.
2297 : The type of the reference is specified by REF and can be SET,
2298 : CLOBBER, PRE_DEC, POST_DEC, PRE_INC, POST_INC or USE. */
2299 :
2300 : static void
2301 134518751 : sched_analyze_reg (class deps_desc *deps, int regno, machine_mode mode,
2302 : enum rtx_code ref, rtx_insn *insn)
2303 : {
2304 : /* We could emit new pseudos in renaming. Extend the reg structures. */
2305 52415 : if (!reload_completed && sel_sched_p ()
2306 134552684 : && (regno >= max_reg_num () - 1 || regno >= deps->max_reg))
2307 802 : extend_deps_reg_info (deps, regno);
2308 :
2309 134518751 : maybe_extend_reg_info_p ();
2310 :
2311 : /* A hard reg in a wide mode may really be multiple registers.
2312 : If so, mark all of them just like the first. */
2313 134518751 : if (regno < FIRST_PSEUDO_REGISTER)
2314 : {
2315 134478445 : int i = hard_regno_nregs (regno, mode);
2316 134478445 : if (ref == SET)
2317 : {
2318 79475191 : while (--i >= 0)
2319 79607146 : note_reg_set (regno + i);
2320 : }
2321 94806827 : else if (ref == USE)
2322 : {
2323 166601630 : while (--i >= 0)
2324 166730114 : note_reg_use (regno + i);
2325 : }
2326 : else
2327 : {
2328 23141574 : while (--i >= 0)
2329 23142640 : note_reg_clobber (regno + i);
2330 : }
2331 : }
2332 :
2333 : /* ??? Reload sometimes emits USEs and CLOBBERs of pseudos that
2334 : it does not reload. Ignore these as they have served their
2335 : purpose already. */
2336 40306 : else if (regno >= deps->max_reg)
2337 : {
2338 0 : enum rtx_code code = GET_CODE (PATTERN (insn));
2339 0 : gcc_assert (code == USE || code == CLOBBER);
2340 : }
2341 :
2342 : else
2343 : {
2344 40306 : if (ref == SET)
2345 18366 : note_reg_set (regno);
2346 21940 : else if (ref == USE)
2347 21907 : note_reg_use (regno);
2348 : else
2349 33 : note_reg_clobber (regno);
2350 :
2351 : /* Pseudos that are REG_EQUIV to something may be replaced
2352 : by that during reloading. We need only add dependencies for
2353 : the address in the REG_EQUIV note. */
2354 40306 : if (!reload_completed && get_reg_known_equiv_p (regno))
2355 : {
2356 0 : rtx t = get_reg_known_value (regno);
2357 0 : if (MEM_P (t))
2358 0 : sched_analyze_2 (deps, XEXP (t, 0), insn);
2359 : }
2360 :
2361 : /* Don't let it cross a call after scheduling if it doesn't
2362 : already cross one. */
2363 40306 : if (REG_N_CALLS_CROSSED (regno) == 0)
2364 : {
2365 36738 : if (!deps->readonly && ref == USE && !DEBUG_INSN_P (insn))
2366 8778 : deps->sched_before_next_call
2367 8778 : = alloc_INSN_LIST (insn, deps->sched_before_next_call);
2368 : else
2369 27960 : add_dependence_list (insn, deps->last_function_call, 1,
2370 : REG_DEP_ANTI, false);
2371 : }
2372 : }
2373 134518751 : }
2374 :
2375 : /* Analyze a single SET, CLOBBER, PRE_DEC, POST_DEC, PRE_INC or POST_INC
2376 : rtx, X, creating all dependencies generated by the write to the
2377 : destination of X, and reads of everything mentioned. */
2378 :
2379 : static void
2380 70185034 : sched_analyze_1 (class deps_desc *deps, rtx x, rtx_insn *insn)
2381 : {
2382 70185034 : rtx dest = XEXP (x, 0);
2383 70185034 : enum rtx_code code = GET_CODE (x);
2384 70185034 : bool cslr_p = can_start_lhs_rhs_p;
2385 :
2386 70185034 : can_start_lhs_rhs_p = false;
2387 :
2388 70185034 : gcc_assert (dest);
2389 70185034 : if (dest == 0)
2390 : return;
2391 :
2392 70185034 : if (cslr_p && sched_deps_info->start_lhs)
2393 16856 : sched_deps_info->start_lhs (dest);
2394 :
2395 70185034 : if (GET_CODE (dest) == PARALLEL)
2396 : {
2397 7936 : int i;
2398 :
2399 21531 : for (i = XVECLEN (dest, 0) - 1; i >= 0; i--)
2400 13595 : if (XEXP (XVECEXP (dest, 0, i), 0) != 0)
2401 13595 : sched_analyze_1 (deps,
2402 : gen_rtx_CLOBBER (VOIDmode,
2403 : XEXP (XVECEXP (dest, 0, i), 0)),
2404 : insn);
2405 :
2406 7936 : if (cslr_p && sched_deps_info->finish_lhs)
2407 0 : sched_deps_info->finish_lhs ();
2408 :
2409 7936 : if (code == SET)
2410 : {
2411 7936 : can_start_lhs_rhs_p = cslr_p;
2412 :
2413 7936 : sched_analyze_2 (deps, SET_SRC (x), insn);
2414 :
2415 7936 : can_start_lhs_rhs_p = false;
2416 : }
2417 :
2418 : return;
2419 : }
2420 :
2421 70224731 : while (GET_CODE (dest) == STRICT_LOW_PART || GET_CODE (dest) == SUBREG
2422 70224731 : || GET_CODE (dest) == ZERO_EXTRACT)
2423 : {
2424 47633 : if (GET_CODE (dest) == STRICT_LOW_PART
2425 10844 : || GET_CODE (dest) == ZERO_EXTRACT
2426 47707 : || read_modify_subreg_p (dest))
2427 : {
2428 : /* These both read and modify the result. We must handle
2429 : them as writes to get proper dependencies for following
2430 : instructions. We must handle them as reads to get proper
2431 : dependencies from this to previous instructions.
2432 : Thus we need to call sched_analyze_2. */
2433 :
2434 47559 : sched_analyze_2 (deps, XEXP (dest, 0), insn);
2435 : }
2436 47633 : if (GET_CODE (dest) == ZERO_EXTRACT)
2437 : {
2438 : /* The second and third arguments are values read by this insn. */
2439 10770 : sched_analyze_2 (deps, XEXP (dest, 1), insn);
2440 10770 : sched_analyze_2 (deps, XEXP (dest, 2), insn);
2441 : }
2442 47633 : dest = XEXP (dest, 0);
2443 : }
2444 :
2445 70177098 : if (REG_P (dest))
2446 : {
2447 50676205 : int regno = REGNO (dest);
2448 50676205 : machine_mode mode = GET_MODE (dest);
2449 :
2450 50676205 : sched_analyze_reg (deps, regno, mode, code, insn);
2451 :
2452 : #ifdef STACK_REGS
2453 : /* Treat all writes to a stack register as modifying the TOS. */
2454 50676205 : if (regno >= FIRST_STACK_REG && regno <= LAST_STACK_REG)
2455 : {
2456 : /* Avoid analyzing the same register twice. */
2457 320191 : if (regno != FIRST_STACK_REG)
2458 237714 : sched_analyze_reg (deps, FIRST_STACK_REG, mode, code, insn);
2459 :
2460 320191 : add_to_hard_reg_set (&implicit_reg_pending_uses, mode,
2461 : FIRST_STACK_REG);
2462 : }
2463 : #endif
2464 50676205 : if (!deps->readonly && regno == STACK_POINTER_REGNUM)
2465 : {
2466 : /* Please see PR114115. We have insn modifying memory on the stack
2467 : and not addressed by stack pointer and we have insn reserving the
2468 : stack space. If we move the insn modifying memory before insn
2469 : reserving the stack space, we can change memory out of the red
2470 : zone. Even worse, some optimizations (e.g. peephole) can add
2471 : insns using temporary stack slots before insn reserving the stack
2472 : space but after the insn modifying memory. This will corrupt the
2473 : modified memory. Therefore we treat insn changing the stack as
2474 : reading unknown memory. This will create anti-dependence. We
2475 : don't need to treat the insn as writing memory because GCC by
2476 : itself does not generate code reading undefined stack memory. */
2477 6492549 : if ((deps->pending_read_list_length + deps->pending_write_list_length)
2478 6492549 : >= param_max_pending_list_length
2479 2077 : && !DEBUG_INSN_P (insn))
2480 2077 : flush_pending_lists (deps, insn, true, true);
2481 6492549 : add_insn_mem_dependence (deps, true, insn, dest);
2482 : }
2483 : }
2484 19500893 : else if (MEM_P (dest))
2485 : {
2486 : /* Writing memory. */
2487 12756939 : rtx t = dest;
2488 :
2489 12756939 : if (sched_deps_info->use_cselib)
2490 : {
2491 370 : machine_mode address_mode = get_address_mode (dest);
2492 :
2493 370 : t = shallow_copy_rtx (dest);
2494 370 : cselib_lookup_from_insn (XEXP (t, 0), address_mode, 1,
2495 370 : GET_MODE (t), insn);
2496 370 : XEXP (t, 0)
2497 370 : = cselib_subst_to_values_from_insn (XEXP (t, 0), GET_MODE (t),
2498 : insn);
2499 : }
2500 12756939 : t = canon_rtx (t);
2501 :
2502 : /* Pending lists can't get larger with a readonly context. */
2503 12756939 : if (!deps->readonly
2504 12753993 : && ((deps->pending_read_list_length + deps->pending_write_list_length)
2505 12753993 : >= param_max_pending_list_length))
2506 : {
2507 : /* Flush all pending reads and writes to prevent the pending lists
2508 : from getting any larger. Insn scheduling runs too slowly when
2509 : these lists get long. When compiling GCC with itself,
2510 : this flush occurs 8 times for sparc, and 10 times for m88k using
2511 : the default value of 32. */
2512 20126 : flush_pending_lists (deps, insn, false, true);
2513 : }
2514 : else
2515 : {
2516 12736813 : rtx_insn_list *pending;
2517 12736813 : rtx_expr_list *pending_mem;
2518 :
2519 12736813 : pending = deps->pending_read_insns;
2520 12736813 : pending_mem = deps->pending_read_mems;
2521 40109317 : while (pending)
2522 : {
2523 27372504 : rtx mem = pending_mem->element ();
2524 27372504 : if (REG_P (mem)
2525 27372504 : || (anti_dependence (mem, t)
2526 4575024 : && ! sched_insns_conditions_mutex_p (insn, pending->insn ())))
2527 14379609 : note_mem_dep (t, mem, pending->insn (), DEP_ANTI);
2528 :
2529 27372504 : pending = pending->next ();
2530 27372504 : pending_mem = pending_mem->next ();
2531 : }
2532 :
2533 12736813 : pending = deps->pending_write_insns;
2534 12736813 : pending_mem = deps->pending_write_mems;
2535 43213547 : while (pending)
2536 : {
2537 30476734 : if (output_dependence (pending_mem->element (), t)
2538 38794364 : && ! sched_insns_conditions_mutex_p (insn, pending->insn ()))
2539 8317630 : note_mem_dep (t, pending_mem->element (),
2540 : pending->insn (),
2541 : DEP_OUTPUT);
2542 :
2543 30476734 : pending = pending->next ();
2544 30476734 : pending_mem = pending_mem-> next ();
2545 : }
2546 :
2547 12736813 : add_dependence_list (insn, deps->last_pending_memory_flush, 1,
2548 : REG_DEP_ANTI, true);
2549 12736813 : add_dependence_list (insn, deps->pending_jump_insns, 1,
2550 : REG_DEP_CONTROL, true);
2551 :
2552 12736813 : if (!deps->readonly)
2553 12733867 : add_insn_mem_dependence (deps, false, insn, dest);
2554 : }
2555 12756939 : sched_analyze_2 (deps, XEXP (dest, 0), insn);
2556 : }
2557 :
2558 70177098 : if (cslr_p && sched_deps_info->finish_lhs)
2559 16856 : sched_deps_info->finish_lhs ();
2560 :
2561 : /* Analyze reads. */
2562 70177098 : if (GET_CODE (x) == SET)
2563 : {
2564 57501185 : can_start_lhs_rhs_p = cslr_p;
2565 :
2566 57501185 : sched_analyze_2 (deps, SET_SRC (x), insn);
2567 :
2568 57501185 : can_start_lhs_rhs_p = false;
2569 : }
2570 : }
2571 :
2572 : /* Analyze the uses of memory and registers in rtx X in INSN. */
2573 : static void
2574 352847162 : sched_analyze_2 (class deps_desc *deps, rtx x, rtx_insn *insn)
2575 : {
2576 352847162 : int i;
2577 352847162 : int j;
2578 352847162 : enum rtx_code code;
2579 352847162 : const char *fmt;
2580 352847162 : bool cslr_p = can_start_lhs_rhs_p;
2581 :
2582 352847162 : can_start_lhs_rhs_p = false;
2583 :
2584 352847162 : gcc_assert (x);
2585 352847162 : if (x == 0)
2586 : return;
2587 :
2588 352847162 : if (cslr_p && sched_deps_info->start_rhs)
2589 16856 : sched_deps_info->start_rhs (x);
2590 :
2591 352847162 : code = GET_CODE (x);
2592 :
2593 352847162 : switch (code)
2594 : {
2595 88497538 : CASE_CONST_ANY:
2596 88497538 : case SYMBOL_REF:
2597 88497538 : case CONST:
2598 88497538 : case LABEL_REF:
2599 : /* Ignore constants. */
2600 88497538 : if (cslr_p && sched_deps_info->finish_rhs)
2601 2398 : sched_deps_info->finish_rhs ();
2602 :
2603 : return;
2604 :
2605 83016382 : case REG:
2606 83016382 : {
2607 83016382 : int regno = REGNO (x);
2608 83016382 : machine_mode mode = GET_MODE (x);
2609 :
2610 83016382 : sched_analyze_reg (deps, regno, mode, USE, insn);
2611 :
2612 : #ifdef STACK_REGS
2613 : /* Treat all reads of a stack register as modifying the TOS. */
2614 83016382 : if (regno >= FIRST_STACK_REG && regno <= LAST_STACK_REG)
2615 : {
2616 : /* Avoid analyzing the same register twice. */
2617 346352 : if (regno != FIRST_STACK_REG)
2618 242098 : sched_analyze_reg (deps, FIRST_STACK_REG, mode, USE, insn);
2619 346352 : sched_analyze_reg (deps, FIRST_STACK_REG, mode, SET, insn);
2620 : }
2621 : #endif
2622 :
2623 83016382 : if (cslr_p && sched_deps_info->finish_rhs)
2624 6426 : sched_deps_info->finish_rhs ();
2625 :
2626 : return;
2627 : }
2628 :
2629 19932414 : case MEM:
2630 19932414 : {
2631 19932414 : if (DEBUG_INSN_P (insn) && sched_deps_info->use_cselib)
2632 : {
2633 5 : machine_mode address_mode = get_address_mode (x);
2634 :
2635 5 : cselib_lookup_from_insn (XEXP (x, 0), address_mode, 1,
2636 5 : GET_MODE (x), insn);
2637 5 : }
2638 19932409 : else if (!DEBUG_INSN_P (insn))
2639 : {
2640 : /* Reading memory. */
2641 18191224 : rtx_insn_list *u;
2642 18191224 : rtx_insn_list *pending;
2643 18191224 : rtx_expr_list *pending_mem;
2644 18191224 : rtx t = x;
2645 :
2646 18191224 : if (sched_deps_info->use_cselib)
2647 : {
2648 362 : machine_mode address_mode = get_address_mode (t);
2649 :
2650 362 : t = shallow_copy_rtx (t);
2651 362 : cselib_lookup_from_insn (XEXP (t, 0), address_mode, 1,
2652 362 : GET_MODE (t), insn);
2653 362 : XEXP (t, 0)
2654 362 : = cselib_subst_to_values_from_insn (XEXP (t, 0), GET_MODE (t),
2655 : insn);
2656 : }
2657 :
2658 18191224 : t = canon_rtx (t);
2659 18191224 : pending = deps->pending_read_insns;
2660 18191224 : pending_mem = deps->pending_read_mems;
2661 64030958 : while (pending)
2662 : {
2663 45839734 : rtx mem = pending_mem->element ();
2664 32658933 : if (MEM_P (mem) && read_dependence (mem, t)
2665 46375733 : && ! sched_insns_conditions_mutex_p (insn, pending->insn ()))
2666 535999 : note_mem_dep (t, mem, pending->insn (), DEP_ANTI);
2667 :
2668 45839734 : pending = pending->next ();
2669 45839734 : pending_mem = pending_mem->next ();
2670 : }
2671 :
2672 18191224 : pending = deps->pending_write_insns;
2673 18191224 : pending_mem = deps->pending_write_mems;
2674 44437787 : while (pending)
2675 : {
2676 26246563 : if (true_dependence (pending_mem->element (), VOIDmode, t)
2677 35441310 : && ! sched_insns_conditions_mutex_p (insn,
2678 9194747 : pending->insn ()))
2679 9194747 : note_mem_dep (t, pending_mem->element (),
2680 : pending->insn (),
2681 9194747 : sched_deps_info->generate_spec_deps
2682 : ? BEGIN_DATA | DEP_TRUE : DEP_TRUE);
2683 :
2684 26246563 : pending = pending->next ();
2685 26246563 : pending_mem = pending_mem->next ();
2686 : }
2687 :
2688 23460033 : for (u = deps->last_pending_memory_flush; u; u = u->next ())
2689 5268809 : add_dependence (insn, u->insn (), REG_DEP_ANTI);
2690 :
2691 18206997 : for (u = deps->pending_jump_insns; u; u = u->next ())
2692 15773 : if (deps_may_trap_p (x))
2693 : {
2694 15428 : if ((sched_deps_info->generate_spec_deps)
2695 15428 : && sel_sched_p () && (spec_info->mask & BEGIN_CONTROL))
2696 : {
2697 0 : ds_t ds = set_dep_weak (DEP_ANTI, BEGIN_CONTROL,
2698 : MAX_DEP_WEAK);
2699 :
2700 15773 : note_dep (u->insn (), ds);
2701 : }
2702 : else
2703 15428 : add_dependence (insn, u->insn (), REG_DEP_CONTROL);
2704 : }
2705 : }
2706 :
2707 : /* Always add these dependencies to pending_reads, since
2708 : this insn may be followed by a write. */
2709 19932414 : if (!deps->readonly)
2710 : {
2711 19927709 : if ((deps->pending_read_list_length
2712 19927709 : + deps->pending_write_list_length)
2713 19927709 : >= param_max_pending_list_length
2714 27641 : && !DEBUG_INSN_P (insn))
2715 24548 : flush_pending_lists (deps, insn, true, true);
2716 19927709 : add_insn_mem_dependence (deps, true, insn, x);
2717 : }
2718 :
2719 19932414 : sched_analyze_2 (deps, XEXP (x, 0), insn);
2720 :
2721 19932414 : if (cslr_p && sched_deps_info->finish_rhs)
2722 1656 : sched_deps_info->finish_rhs ();
2723 :
2724 : return;
2725 : }
2726 :
2727 : /* Force pending stores to memory in case a trap handler needs them.
2728 : Also force pending loads from memory; loads and stores can segfault
2729 : and the signal handler won't be triggered if the trap insn was moved
2730 : above load or store insn. */
2731 5340 : case TRAP_IF:
2732 5340 : flush_pending_lists (deps, insn, true, true);
2733 5340 : break;
2734 :
2735 1825 : case PREFETCH:
2736 1825 : if (PREFETCH_SCHEDULE_BARRIER_P (x))
2737 0 : reg_pending_barrier = TRUE_BARRIER;
2738 : /* Prefetch insn contains addresses only. So if the prefetch
2739 : address has no registers, there will be no dependencies on
2740 : the prefetch insn. This is wrong with result code
2741 : correctness point of view as such prefetch can be moved below
2742 : a jump insn which usually generates MOVE_BARRIER preventing
2743 : to move insns containing registers or memories through the
2744 : barrier. It is also wrong with generated code performance
2745 : point of view as prefetch without dependencies will have a
2746 : tendency to be issued later instead of earlier. It is hard
2747 : to generate accurate dependencies for prefetch insns as
2748 : prefetch has only the start address but it is better to have
2749 : something than nothing. */
2750 1825 : if (!deps->readonly)
2751 : {
2752 1886 : rtx x = gen_rtx_MEM (Pmode, XEXP (PATTERN (insn), 0));
2753 1790 : if (sched_deps_info->use_cselib)
2754 2 : cselib_lookup_from_insn (x, Pmode, true, VOIDmode, insn);
2755 1790 : add_insn_mem_dependence (deps, true, insn, x);
2756 : }
2757 : break;
2758 :
2759 677421 : case UNSPEC_VOLATILE:
2760 677421 : flush_pending_lists (deps, insn, true, true);
2761 : /* FALLTHRU */
2762 :
2763 767847 : case ASM_OPERANDS:
2764 767847 : case ASM_INPUT:
2765 767847 : {
2766 : /* Traditional and volatile asm instructions must be considered to use
2767 : and clobber all hard registers, all pseudo-registers and all of
2768 : memory. So must TRAP_IF and UNSPEC_VOLATILE operations.
2769 :
2770 : Consider for instance a volatile asm that changes the fpu rounding
2771 : mode. An insn should not be moved across this even if it only uses
2772 : pseudo-regs because it might give an incorrectly rounded result. */
2773 87980 : if ((code != ASM_OPERANDS || MEM_VOLATILE_P (x))
2774 844406 : && !DEBUG_INSN_P (insn))
2775 756426 : reg_pending_barrier = TRUE_BARRIER;
2776 :
2777 : /* For all ASM_OPERANDS, we must traverse the vector of input operands.
2778 : We cannot just fall through here since then we would be confused
2779 : by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
2780 : traditional asms unlike their normal usage. */
2781 :
2782 767847 : if (code == ASM_OPERANDS)
2783 : {
2784 194986 : for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++)
2785 107006 : sched_analyze_2 (deps, ASM_OPERANDS_INPUT (x, j), insn);
2786 :
2787 87980 : if (cslr_p && sched_deps_info->finish_rhs)
2788 0 : sched_deps_info->finish_rhs ();
2789 :
2790 : return;
2791 : }
2792 : break;
2793 : }
2794 :
2795 3982138 : case PRE_DEC:
2796 3982138 : case POST_DEC:
2797 3982138 : case PRE_INC:
2798 3982138 : case POST_INC:
2799 : /* These both read and modify the result. We must handle them as writes
2800 : to get proper dependencies for following instructions. We must handle
2801 : them as reads to get proper dependencies from this to previous
2802 : instructions. Thus we need to pass them to both sched_analyze_1
2803 : and sched_analyze_2. We must call sched_analyze_2 first in order
2804 : to get the proper antecedent for the read. */
2805 3982138 : sched_analyze_2 (deps, XEXP (x, 0), insn);
2806 3982138 : sched_analyze_1 (deps, x, insn);
2807 :
2808 3982138 : if (cslr_p && sched_deps_info->finish_rhs)
2809 0 : sched_deps_info->finish_rhs ();
2810 :
2811 : return;
2812 :
2813 54710 : case POST_MODIFY:
2814 54710 : case PRE_MODIFY:
2815 : /* op0 = op0 + op1 */
2816 54710 : sched_analyze_2 (deps, XEXP (x, 0), insn);
2817 54710 : sched_analyze_2 (deps, XEXP (x, 1), insn);
2818 54710 : sched_analyze_1 (deps, x, insn);
2819 :
2820 54710 : if (cslr_p && sched_deps_info->finish_rhs)
2821 0 : sched_deps_info->finish_rhs ();
2822 :
2823 : return;
2824 :
2825 : default:
2826 : break;
2827 : }
2828 :
2829 : /* Other cases: walk the insn. */
2830 157276000 : fmt = GET_RTX_FORMAT (code);
2831 398457535 : for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2832 : {
2833 241181535 : if (fmt[i] == 'e')
2834 187422158 : sched_analyze_2 (deps, XEXP (x, i), insn);
2835 53759377 : else if (fmt[i] == 'E')
2836 3889691 : for (j = 0; j < XVECLEN (x, i); j++)
2837 2495258 : sched_analyze_2 (deps, XVECEXP (x, i, j), insn);
2838 : }
2839 :
2840 157276000 : if (cslr_p && sched_deps_info->finish_rhs)
2841 6376 : sched_deps_info->finish_rhs ();
2842 : }
2843 :
2844 : /* Try to group two fusible insns together to prevent scheduler
2845 : from scheduling them apart. */
2846 :
2847 : static void
2848 115905631 : sched_macro_fuse_insns (rtx_insn *insn)
2849 : {
2850 115905631 : rtx_insn *prev;
2851 : /* No target hook would return true for debug insn as any of the
2852 : hook operand, and with very large sequences of only debug insns
2853 : where on each we call sched_macro_fuse_insns it has quadratic
2854 : compile time complexity. */
2855 115905631 : if (DEBUG_INSN_P (insn))
2856 : return;
2857 61730554 : prev = prev_nonnote_nondebug_insn_bb (insn);
2858 61730554 : if (!prev)
2859 : return;
2860 :
2861 51168420 : if (any_condjump_p (insn))
2862 : {
2863 4810933 : unsigned int condreg1, condreg2;
2864 4810933 : rtx cc_reg_1;
2865 4810933 : if (targetm.fixed_condition_code_regs (&condreg1, &condreg2))
2866 : {
2867 4810933 : cc_reg_1 = gen_rtx_REG (CCmode, condreg1);
2868 4810933 : if (reg_referenced_p (cc_reg_1, PATTERN (insn))
2869 4810933 : && modified_in_p (cc_reg_1, prev))
2870 : {
2871 4687766 : if (targetm.sched.macro_fusion_pair_p (prev, insn))
2872 4250652 : SCHED_GROUP_P (insn) = 1;
2873 4687766 : return;
2874 : }
2875 : }
2876 : }
2877 :
2878 46480654 : if (single_set (insn) && single_set (prev))
2879 : {
2880 39124094 : if (targetm.sched.macro_fusion_pair_p (prev, insn))
2881 12 : SCHED_GROUP_P (insn) = 1;
2882 : }
2883 : }
2884 :
2885 : /* Get the implicit reg pending clobbers for INSN and save them in TEMP. */
2886 : void
2887 28567 : get_implicit_reg_pending_clobbers (HARD_REG_SET *temp, rtx_insn *insn)
2888 : {
2889 28567 : extract_insn (insn);
2890 28567 : preprocess_constraints (insn);
2891 28567 : alternative_mask preferred = get_preferred_alternatives (insn);
2892 28567 : ira_implicitly_set_insn_hard_regs (temp, preferred);
2893 28567 : *temp &= ~ira_no_alloc_regs;
2894 28567 : }
2895 :
2896 : /* Write DEPS' pending barriers into register I and return its entry, so that
2897 : callers can read and write it literally. A register outside reg_last_in_use
2898 : carries pending_barriers as the logical value of its sets list; see the
2899 : comment on the field. */
2900 :
2901 : struct deps_reg *
2902 538573515 : deps_reg_last (class deps_desc *deps, unsigned int i)
2903 : {
2904 538573515 : struct deps_reg *reg_last = &deps->reg_last[i];
2905 :
2906 538573515 : if (deps->pending_barriers
2907 538573515 : && !REGNO_REG_SET_P (&deps->reg_last_in_use, i))
2908 : {
2909 2312 : gcc_checking_assert (!deps->readonly);
2910 : /* Outside reg_last_in_use the entry must be empty: a barrier makes every
2911 : reg_last_dirty entry that still holds a list literal before pushing
2912 : itself onto pending_barriers. A live list here means a debug use or
2913 : control use escaped a barrier that the eager form would have
2914 : consumed. */
2915 2312 : gcc_checking_assert (!reg_last->sets && !reg_last->uses
2916 : && !reg_last->clobbers && !reg_last->implicit_sets
2917 : && !reg_last->control_uses
2918 : && reg_last->uses_length == 0
2919 : && reg_last->clobbers_length == 0);
2920 2312 : reg_last->sets = copy_INSN_LIST (deps->pending_barriers);
2921 2312 : SET_REGNO_REG_SET (&deps->reg_last_in_use, i);
2922 : }
2923 :
2924 538573515 : return reg_last;
2925 : }
2926 :
2927 : /* Analyze an INSN with pattern X to find all dependencies. */
2928 : static void
2929 116151459 : sched_analyze_insn (class deps_desc *deps, rtx x, rtx_insn *insn)
2930 : {
2931 116151459 : RTX_CODE code = GET_CODE (x);
2932 116151459 : rtx link;
2933 116151459 : unsigned i;
2934 116151459 : reg_set_iterator rsi;
2935 :
2936 116151459 : if (! reload_completed)
2937 : {
2938 26871 : HARD_REG_SET temp;
2939 26871 : get_implicit_reg_pending_clobbers (&temp, insn);
2940 53742 : implicit_reg_pending_clobbers |= temp;
2941 : }
2942 :
2943 232302918 : can_start_lhs_rhs_p = (NONJUMP_INSN_P (insn)
2944 116151459 : && code == SET);
2945 :
2946 : /* Group compare and branch insns for macro-fusion. */
2947 116151459 : if (!deps->readonly
2948 116121691 : && (!sel_sched_p () || sched_emulate_haifa_p)
2949 116112842 : && targetm.sched.macro_fusion_p
2950 232264301 : && targetm.sched.macro_fusion_p ())
2951 115905631 : sched_macro_fuse_insns (insn);
2952 :
2953 116151459 : if (may_trap_p (x))
2954 : /* Avoid moving trapping instructions across function calls that might
2955 : not always return. */
2956 8999890 : add_dependence_list (insn, deps->last_function_call_may_noreturn,
2957 : 1, REG_DEP_ANTI, true);
2958 :
2959 : /* We must avoid creating a situation in which two successors of the
2960 : current block have different unwind info after scheduling. If at any
2961 : point the two paths re-join this leads to incorrect unwind info. */
2962 : /* ??? There are certain situations involving a forced frame pointer in
2963 : which, with extra effort, we could fix up the unwind info at a later
2964 : CFG join. However, it seems better to notice these cases earlier
2965 : during prologue generation and avoid marking the frame pointer setup
2966 : as frame-related at all. */
2967 116151459 : if (RTX_FRAME_RELATED_P (insn))
2968 : {
2969 : /* Make sure prologue insn is scheduled before next jump. */
2970 3727509 : deps->sched_before_next_jump
2971 3727509 : = alloc_INSN_LIST (insn, deps->sched_before_next_jump);
2972 :
2973 : /* Make sure epilogue insn is scheduled after preceding jumps. */
2974 3727509 : add_dependence_list (insn, deps->last_pending_memory_flush, 1,
2975 : REG_DEP_ANTI, true);
2976 3727509 : add_dependence_list (insn, deps->pending_jump_insns, 1, REG_DEP_ANTI,
2977 : true);
2978 : }
2979 :
2980 116151459 : if (code == COND_EXEC)
2981 : {
2982 0 : sched_analyze_2 (deps, COND_EXEC_TEST (x), insn);
2983 :
2984 : /* ??? Should be recording conditions so we reduce the number of
2985 : false dependencies. */
2986 0 : x = COND_EXEC_CODE (x);
2987 0 : code = GET_CODE (x);
2988 : }
2989 116151459 : if (code == SET || code == CLOBBER)
2990 : {
2991 49095605 : sched_analyze_1 (deps, x, insn);
2992 :
2993 : /* Bare clobber insns are used for letting life analysis, reg-stack
2994 : and others know that a value is dead. Depend on the last call
2995 : instruction so that reg-stack won't get confused. */
2996 49095605 : if (code == CLOBBER)
2997 83477 : add_dependence_list (insn, deps->last_function_call, 1,
2998 : REG_DEP_OUTPUT, true);
2999 : }
3000 67055854 : else if (code == PARALLEL)
3001 : {
3002 25470170 : for (i = XVECLEN (x, 0); i--;)
3003 : {
3004 17521866 : rtx sub = XVECEXP (x, 0, i);
3005 17521866 : code = GET_CODE (sub);
3006 :
3007 17521866 : if (code == COND_EXEC)
3008 : {
3009 0 : sched_analyze_2 (deps, COND_EXEC_TEST (sub), insn);
3010 0 : sub = COND_EXEC_CODE (sub);
3011 0 : code = GET_CODE (sub);
3012 : }
3013 17521866 : else if (code == SET || code == CLOBBER)
3014 17038986 : sched_analyze_1 (deps, sub, insn);
3015 : else
3016 482880 : sched_analyze_2 (deps, sub, insn);
3017 : }
3018 : }
3019 : else
3020 59107550 : sched_analyze_2 (deps, x, insn);
3021 :
3022 : /* Mark registers CLOBBERED or used by called function. */
3023 116151459 : if (CALL_P (insn))
3024 : {
3025 13623715 : for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1))
3026 : {
3027 8943019 : if (GET_CODE (XEXP (link, 0)) == CLOBBER)
3028 0 : sched_analyze_1 (deps, XEXP (link, 0), insn);
3029 8943019 : else if (GET_CODE (XEXP (link, 0)) != SET)
3030 8873179 : sched_analyze_2 (deps, XEXP (link, 0), insn);
3031 : }
3032 : /* Don't schedule anything after a tail call, tail call needs
3033 : to use at least all call-saved registers. */
3034 4680696 : if (SIBLING_CALL_P (insn))
3035 131198 : reg_pending_barrier = TRUE_BARRIER;
3036 4549498 : else if (find_reg_note (insn, REG_SETJMP, NULL))
3037 757 : reg_pending_barrier = MOVE_BARRIER;
3038 : }
3039 :
3040 116151459 : if (JUMP_P (insn))
3041 : {
3042 7867782 : rtx_insn *next = next_nonnote_nondebug_insn (insn);
3043 : /* ??? For tablejumps, the barrier may appear not immediately after
3044 : the jump, but after a label and a jump_table_data insn. */
3045 8914729 : if (next && LABEL_P (next) && NEXT_INSN (next)
3046 8914744 : && JUMP_TABLE_DATA_P (NEXT_INSN (next)))
3047 1196 : next = NEXT_INSN (NEXT_INSN (next));
3048 7867782 : if (next && BARRIER_P (next))
3049 2936701 : reg_pending_barrier = MOVE_BARRIER;
3050 : else
3051 : {
3052 4931081 : rtx_insn_list *pending;
3053 4931081 : rtx_expr_list *pending_mem;
3054 :
3055 4931081 : if (sched_deps_info->compute_jump_reg_dependencies)
3056 : {
3057 4929574 : (*sched_deps_info->compute_jump_reg_dependencies)
3058 4929574 : (insn, reg_pending_control_uses);
3059 :
3060 : /* Make latency of jump equal to 0 by using anti-dependence. */
3061 4929735 : EXECUTE_IF_SET_IN_REG_SET (reg_pending_control_uses, 0, i, rsi)
3062 : {
3063 161 : struct deps_reg *reg_last = deps_reg_last (deps, i);
3064 161 : add_dependence_list (insn, reg_last->sets, 0, REG_DEP_ANTI,
3065 : false);
3066 161 : add_dependence_list (insn, reg_last->implicit_sets,
3067 : 0, REG_DEP_ANTI, false);
3068 161 : add_dependence_list (insn, reg_last->clobbers, 0,
3069 : REG_DEP_ANTI, false);
3070 : }
3071 : }
3072 :
3073 : /* All memory writes and volatile reads must happen before the
3074 : jump. Non-volatile reads must happen before the jump iff
3075 : the result is needed by the above register used mask. */
3076 :
3077 4931081 : pending = deps->pending_write_insns;
3078 4931081 : pending_mem = deps->pending_write_mems;
3079 7351004 : while (pending)
3080 : {
3081 2419923 : if (! sched_insns_conditions_mutex_p (insn, pending->insn ()))
3082 2419923 : add_dependence (insn, pending->insn (), REG_DEP_OUTPUT);
3083 2419923 : pending = pending->next ();
3084 2419923 : pending_mem = pending_mem->next ();
3085 : }
3086 :
3087 4931081 : pending = deps->pending_read_insns;
3088 4931081 : pending_mem = deps->pending_read_mems;
3089 11914942 : while (pending)
3090 : {
3091 6983861 : rtx mem = pending_mem->element ();
3092 6220153 : if (MEM_P (mem) && MEM_VOLATILE_P (mem)
3093 7309006 : && ! sched_insns_conditions_mutex_p (insn, pending->insn ()))
3094 325145 : add_dependence (insn, pending->insn (), REG_DEP_OUTPUT);
3095 6983861 : pending = pending->next ();
3096 6983861 : pending_mem = pending_mem->next ();
3097 : }
3098 :
3099 4931081 : add_dependence_list (insn, deps->last_pending_memory_flush, 1,
3100 : REG_DEP_ANTI, true);
3101 4931081 : add_dependence_list (insn, deps->pending_jump_insns, 1,
3102 : REG_DEP_ANTI, true);
3103 : }
3104 : }
3105 :
3106 : /* If this instruction can throw an exception, then moving it changes
3107 : where block boundaries fall. This is mighty confusing elsewhere.
3108 : Therefore, prevent such an instruction from being moved. Same for
3109 : non-jump instructions that define block boundaries.
3110 : ??? Unclear whether this is still necessary in EBB mode. If not,
3111 : add_branch_dependences should be adjusted for RGN mode instead. */
3112 12548478 : if (((CALL_P (insn) || JUMP_P (insn)) && can_throw_internal (insn))
3113 128155801 : || (NONJUMP_INSN_P (insn) && control_flow_insn_p (insn)))
3114 656855 : reg_pending_barrier = MOVE_BARRIER;
3115 :
3116 116151459 : if (sched_pressure != SCHED_PRESSURE_NONE)
3117 : {
3118 5262 : setup_insn_reg_uses (deps, insn);
3119 5262 : init_insn_reg_pressure_info (insn);
3120 : }
3121 :
3122 : /* Add register dependencies for insn. */
3123 116151459 : if (DEBUG_INSN_P (insn))
3124 : {
3125 54176002 : rtx_insn *prev = deps->last_debug_insn;
3126 54176002 : rtx_insn_list *u;
3127 :
3128 54176002 : if (!deps->readonly)
3129 54175881 : deps->last_debug_insn = insn;
3130 :
3131 54176002 : if (prev)
3132 50463658 : add_dependence (insn, prev, REG_DEP_ANTI);
3133 :
3134 54176002 : add_dependence_list (insn, deps->last_function_call, 1,
3135 : REG_DEP_ANTI, false);
3136 :
3137 54176002 : if (!sel_sched_p ())
3138 64115587 : for (u = deps->last_pending_memory_flush; u; u = u->next ())
3139 9939810 : add_dependence (insn, u->insn (), REG_DEP_ANTI);
3140 :
3141 65281291 : EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i, rsi)
3142 : {
3143 11105289 : struct deps_reg *reg_last = deps_reg_last (deps, i);
3144 11105289 : add_dependence_list (insn, reg_last->sets, 1, REG_DEP_ANTI, false);
3145 : /* There's no point in making REG_DEP_CONTROL dependencies for
3146 : debug insns. */
3147 11105289 : add_dependence_list (insn, reg_last->clobbers, 1, REG_DEP_ANTI,
3148 : false);
3149 :
3150 11105289 : if (!deps->readonly)
3151 11105289 : reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
3152 : }
3153 54176002 : if (!deps->readonly)
3154 54175881 : IOR_REG_SET (&deps->reg_last_dirty, reg_pending_uses);
3155 54176002 : CLEAR_REG_SET (reg_pending_uses);
3156 :
3157 : /* Quite often, a debug insn will refer to stuff in the
3158 : previous instruction, but the reason we want this
3159 : dependency here is to make sure the scheduler doesn't
3160 : gratuitously move a debug insn ahead. This could dirty
3161 : DF flags and cause additional analysis that wouldn't have
3162 : occurred in compilation without debug insns, and such
3163 : additional analysis can modify the generated code. */
3164 54176002 : prev = PREV_INSN (insn);
3165 :
3166 54176002 : if (prev && NONDEBUG_INSN_P (prev))
3167 4102078 : add_dependence (insn, prev, REG_DEP_ANTI);
3168 : }
3169 : else
3170 : {
3171 61975457 : regset_head set_or_clobbered;
3172 :
3173 132413040 : EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i, rsi)
3174 : {
3175 70437583 : struct deps_reg *reg_last = deps_reg_last (deps, i);
3176 70437583 : add_dependence_list (insn, reg_last->sets, 0, REG_DEP_TRUE, false);
3177 70437583 : add_dependence_list (insn, reg_last->implicit_sets, 0, REG_DEP_ANTI,
3178 : false);
3179 70437583 : add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_TRUE,
3180 : false);
3181 :
3182 70437583 : if (!deps->readonly)
3183 : {
3184 70424720 : reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
3185 70424720 : reg_last->uses_length++;
3186 : }
3187 : }
3188 :
3189 61975457 : hard_reg_set_iterator hrsi;
3190 77221489 : EXECUTE_IF_SET_IN_HARD_REG_SET (implicit_reg_pending_uses, 0, i, hrsi)
3191 : {
3192 15246032 : struct deps_reg *reg_last = deps_reg_last (deps, i);
3193 15246032 : add_dependence_list (insn, reg_last->sets, 0, REG_DEP_TRUE, false);
3194 15246032 : add_dependence_list (insn, reg_last->implicit_sets, 0,
3195 : REG_DEP_ANTI, false);
3196 15246032 : add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_TRUE,
3197 : false);
3198 :
3199 15246032 : if (!deps->readonly)
3200 : {
3201 15244838 : reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
3202 15244838 : reg_last->uses_length++;
3203 : }
3204 : }
3205 :
3206 61975457 : if (targetm.sched.exposed_pipeline)
3207 : {
3208 0 : INIT_REG_SET (&set_or_clobbered);
3209 0 : bitmap_ior (&set_or_clobbered, reg_pending_clobbers,
3210 : reg_pending_sets);
3211 0 : EXECUTE_IF_SET_IN_REG_SET (&set_or_clobbered, 0, i, rsi)
3212 : {
3213 0 : struct deps_reg *reg_last = &deps->reg_last[i];
3214 0 : for (rtx_insn_list *list = reg_last->uses;
3215 0 : list; list = list->next ())
3216 : {
3217 0 : rtx_insn *other = list->insn ();
3218 0 : if (INSN_CACHED_COND (other) != const_true_rtx
3219 0 : && refers_to_regno_p (i, INSN_CACHED_COND (other)))
3220 0 : INSN_CACHED_COND (other) = const_true_rtx;
3221 : }
3222 : }
3223 : }
3224 :
3225 : /* If the current insn is conditional, we can't free any
3226 : of the lists. */
3227 61975457 : if (sched_has_condition_p (insn))
3228 : {
3229 4930598 : EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers, 0, i, rsi)
3230 : {
3231 0 : struct deps_reg *reg_last = deps_reg_last (deps, i);
3232 0 : add_dependence_list (insn, reg_last->sets, 0, REG_DEP_OUTPUT,
3233 : false);
3234 0 : add_dependence_list (insn, reg_last->implicit_sets, 0,
3235 : REG_DEP_ANTI, false);
3236 0 : add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI,
3237 : false);
3238 0 : add_dependence_list (insn, reg_last->control_uses, 0,
3239 : REG_DEP_CONTROL, false);
3240 :
3241 0 : if (!deps->readonly)
3242 : {
3243 0 : reg_last->clobbers
3244 0 : = alloc_INSN_LIST (insn, reg_last->clobbers);
3245 0 : reg_last->clobbers_length++;
3246 : }
3247 : }
3248 4930598 : EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets, 0, i, rsi)
3249 : {
3250 0 : struct deps_reg *reg_last = deps_reg_last (deps, i);
3251 0 : add_dependence_list (insn, reg_last->sets, 0, REG_DEP_OUTPUT,
3252 : false);
3253 0 : add_dependence_list (insn, reg_last->implicit_sets, 0,
3254 : REG_DEP_ANTI, false);
3255 0 : add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_OUTPUT,
3256 : false);
3257 0 : add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI,
3258 : false);
3259 0 : add_dependence_list (insn, reg_last->control_uses, 0,
3260 : REG_DEP_CONTROL, false);
3261 :
3262 0 : if (!deps->readonly)
3263 0 : reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
3264 : }
3265 : }
3266 : else
3267 : {
3268 459219044 : EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers, 0, i, rsi)
3269 : {
3270 402174185 : struct deps_reg *reg_last = deps_reg_last (deps, i);
3271 402174185 : if (reg_last->uses_length >= param_max_pending_list_length
3272 402171426 : || reg_last->clobbers_length >= param_max_pending_list_length)
3273 : {
3274 382148 : add_dependence_list_and_free (deps, insn, ®_last->sets, 0,
3275 : REG_DEP_OUTPUT, false);
3276 382148 : add_dependence_list_and_free (deps, insn,
3277 : ®_last->implicit_sets, 0,
3278 : REG_DEP_ANTI, false);
3279 382148 : add_dependence_list_and_free (deps, insn, ®_last->uses, 0,
3280 : REG_DEP_ANTI, false);
3281 382148 : add_dependence_list_and_free (deps, insn,
3282 : ®_last->control_uses, 0,
3283 : REG_DEP_ANTI, false);
3284 382148 : add_dependence_list_and_free (deps, insn,
3285 : ®_last->clobbers, 0,
3286 : REG_DEP_OUTPUT, false);
3287 :
3288 382148 : if (!deps->readonly)
3289 : {
3290 382147 : reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
3291 382147 : reg_last->clobbers_length = 0;
3292 382147 : reg_last->uses_length = 0;
3293 : }
3294 : }
3295 : else
3296 : {
3297 401792037 : add_dependence_list (insn, reg_last->sets, 0, REG_DEP_OUTPUT,
3298 : false);
3299 401792037 : add_dependence_list (insn, reg_last->implicit_sets, 0,
3300 : REG_DEP_ANTI, false);
3301 401792037 : add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI,
3302 : false);
3303 401792037 : add_dependence_list (insn, reg_last->control_uses, 0,
3304 : REG_DEP_CONTROL, false);
3305 : }
3306 :
3307 402174185 : if (!deps->readonly)
3308 : {
3309 402143809 : reg_last->clobbers_length++;
3310 402143809 : reg_last->clobbers
3311 402143809 : = alloc_INSN_LIST (insn, reg_last->clobbers);
3312 : }
3313 : }
3314 96633433 : EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets, 0, i, rsi)
3315 : {
3316 39588574 : struct deps_reg *reg_last = deps_reg_last (deps, i);
3317 :
3318 39588574 : add_dependence_list_and_free (deps, insn, ®_last->sets, 0,
3319 : REG_DEP_OUTPUT, false);
3320 39588574 : add_dependence_list_and_free (deps, insn,
3321 : ®_last->implicit_sets,
3322 : 0, REG_DEP_ANTI, false);
3323 39588574 : add_dependence_list_and_free (deps, insn, ®_last->clobbers, 0,
3324 : REG_DEP_OUTPUT, false);
3325 39588574 : add_dependence_list_and_free (deps, insn, ®_last->uses, 0,
3326 : REG_DEP_ANTI, false);
3327 39588574 : add_dependence_list (insn, reg_last->control_uses, 0,
3328 : REG_DEP_CONTROL, false);
3329 :
3330 39588574 : if (!deps->readonly)
3331 : {
3332 39580183 : reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
3333 39580183 : reg_last->uses_length = 0;
3334 39580183 : reg_last->clobbers_length = 0;
3335 : }
3336 : }
3337 : }
3338 61975457 : if (!deps->readonly)
3339 : {
3340 61945971 : EXECUTE_IF_SET_IN_REG_SET (reg_pending_control_uses, 0, i, rsi)
3341 : {
3342 161 : struct deps_reg *reg_last = &deps->reg_last[i];
3343 161 : reg_last->control_uses
3344 161 : = alloc_INSN_LIST (insn, reg_last->control_uses);
3345 : }
3346 61945810 : IOR_REG_SET (&deps->reg_last_dirty, reg_pending_control_uses);
3347 : }
3348 : }
3349 :
3350 116151459 : hard_reg_set_iterator hrsi;
3351 116152987 : EXECUTE_IF_SET_IN_HARD_REG_SET (implicit_reg_pending_clobbers, 0, i, hrsi)
3352 : {
3353 1528 : struct deps_reg *reg_last = deps_reg_last (deps, i);
3354 1528 : add_dependence_list (insn, reg_last->sets, 0, REG_DEP_ANTI, false);
3355 1528 : add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_ANTI, false);
3356 1528 : add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI, false);
3357 1528 : add_dependence_list (insn, reg_last->control_uses, 0, REG_DEP_ANTI,
3358 : false);
3359 :
3360 1528 : if (!deps->readonly)
3361 790 : reg_last->implicit_sets
3362 790 : = alloc_INSN_LIST (insn, reg_last->implicit_sets);
3363 : }
3364 :
3365 116151459 : if (!deps->readonly)
3366 : {
3367 116121691 : IOR_REG_SET (&deps->reg_last_in_use, reg_pending_uses);
3368 116121691 : IOR_REG_SET (&deps->reg_last_in_use, reg_pending_clobbers);
3369 116121691 : IOR_REG_SET (&deps->reg_last_in_use, reg_pending_sets);
3370 116121691 : IOR_REG_SET_HRS (&deps->reg_last_in_use,
3371 : implicit_reg_pending_uses
3372 : | implicit_reg_pending_clobbers);
3373 :
3374 : /* Set up the pending barrier found. */
3375 116121691 : deps->last_reg_pending_barrier = reg_pending_barrier;
3376 : }
3377 :
3378 116151459 : CLEAR_REG_SET (reg_pending_uses);
3379 116151459 : CLEAR_REG_SET (reg_pending_clobbers);
3380 116151459 : CLEAR_REG_SET (reg_pending_sets);
3381 116151459 : CLEAR_REG_SET (reg_pending_control_uses);
3382 464605836 : CLEAR_HARD_REG_SET (implicit_reg_pending_clobbers);
3383 116151459 : CLEAR_HARD_REG_SET (implicit_reg_pending_uses);
3384 :
3385 : /* Add dependencies if a scheduling barrier was found. */
3386 116151459 : if (reg_pending_barrier)
3387 : {
3388 : /* In the case of barrier the most added dependencies are not
3389 : real, so we use anti-dependence here. */
3390 3594985 : enum reg_note barrier_dep = (reg_pending_barrier == TRUE_BARRIER
3391 4408945 : ? REG_DEP_TRUE : REG_DEP_ANTI);
3392 4408945 : bool cond_p = sched_has_condition_p (insn);
3393 : /* Recording the barrier once pays for itself when max_reg is
3394 : max_reg_num (), which init_deps uses before reload. After reload
3395 : max_reg is FIRST_PSEUDO_REGISTER and most entries are touched again
3396 : before the next barrier, so materialising on demand costs more than
3397 : writing them out. Selective scheduling re-analyses insns against a
3398 : readonly context that must not allocate, so it cannot materialise on
3399 : demand at all. Keep the eager form for both. */
3400 4408945 : bool eager_p = sel_sched_p () || reload_completed;
3401 : /* The pending barriers are the sets list of every register the loops
3402 : below skip, so their dependence belongs where the first skipped
3403 : register would have emitted it. Find that position while visiting
3404 : the materialised registers. */
3405 4408945 : unsigned next_reg = 0;
3406 4408945 : bool emitted = deps->pending_barriers == NULL;
3407 :
3408 4408945 : if (cond_p)
3409 : {
3410 24 : EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
3411 : {
3412 20 : struct deps_reg *reg_last;
3413 :
3414 20 : if (!emitted && i != next_reg)
3415 : {
3416 0 : add_dependence_list (insn, deps->pending_barriers, 0,
3417 : barrier_dep, true);
3418 0 : emitted = true;
3419 : }
3420 0 : if (!emitted)
3421 0 : next_reg = i + 1;
3422 :
3423 20 : reg_last = &deps->reg_last[i];
3424 20 : add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI,
3425 : true);
3426 20 : add_dependence_list (insn, reg_last->sets, 0, barrier_dep, true);
3427 20 : add_dependence_list (insn, reg_last->implicit_sets, 0,
3428 : REG_DEP_ANTI, true);
3429 20 : add_dependence_list (insn, reg_last->clobbers, 0, barrier_dep,
3430 : true);
3431 :
3432 20 : if (!deps->readonly && !eager_p)
3433 0 : reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
3434 : }
3435 4 : if (!emitted && next_reg < (unsigned) deps->max_reg)
3436 0 : add_dependence_list (insn, deps->pending_barriers, 0, barrier_dep,
3437 : true);
3438 : }
3439 : else
3440 : {
3441 214117345 : EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
3442 : {
3443 209708404 : struct deps_reg *reg_last;
3444 :
3445 209708404 : if (!emitted && i != next_reg)
3446 : {
3447 207 : add_dependence_list_and_free (deps, insn,
3448 : &deps->pending_barriers, 0,
3449 : barrier_dep, true);
3450 207 : emitted = true;
3451 : }
3452 207 : if (!emitted)
3453 488 : next_reg = i + 1;
3454 :
3455 209708404 : reg_last = &deps->reg_last[i];
3456 209708404 : add_dependence_list_and_free (deps, insn, ®_last->uses, 0,
3457 : REG_DEP_ANTI, true);
3458 209708404 : add_dependence_list_and_free (deps, insn,
3459 : ®_last->control_uses, 0,
3460 : REG_DEP_CONTROL, true);
3461 209708404 : add_dependence_list_and_free (deps, insn, ®_last->sets, 0,
3462 : barrier_dep, true);
3463 209708404 : add_dependence_list_and_free (deps, insn,
3464 : ®_last->implicit_sets, 0,
3465 : REG_DEP_ANTI, true);
3466 209708404 : add_dependence_list_and_free (deps, insn, ®_last->clobbers, 0,
3467 : barrier_dep, true);
3468 :
3469 209708404 : if (!deps->readonly)
3470 : {
3471 209699804 : reg_last->uses_length = 0;
3472 209699804 : reg_last->clobbers_length = 0;
3473 : }
3474 : }
3475 4408941 : if (!emitted)
3476 : {
3477 19 : if (next_reg < (unsigned) deps->max_reg)
3478 15 : add_dependence_list_and_free (deps, insn,
3479 : &deps->pending_barriers, 0,
3480 : barrier_dep, true);
3481 : else
3482 : /* Every register has its own state, so no register carries the
3483 : global list. */
3484 4 : free_INSN_LIST_list (&deps->pending_barriers);
3485 : }
3486 : }
3487 :
3488 4408945 : if (!deps->readonly)
3489 : {
3490 4408283 : if (eager_p)
3491 : {
3492 : /* Write the barrier into every entry. pending_barriers then
3493 : stays empty and deps_reg_last never writes anything, so the
3494 : rest of this file behaves exactly as it did before. */
3495 418741319 : for (i = 0; i < (unsigned) deps->max_reg; i++)
3496 : {
3497 414333693 : struct deps_reg *reg_last = &deps->reg_last[i];
3498 414333693 : reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
3499 414333693 : SET_REGNO_REG_SET (&deps->reg_last_in_use, i);
3500 : }
3501 : }
3502 : else
3503 : {
3504 : /* Record the barrier once instead of writing it into every one
3505 : of the max_reg entries. deps_reg_last materialises it per
3506 : register on first touch. The loop above emptied every in-use
3507 : entry in the non-conditional case, so they can all go back to
3508 : carrying the pending list. */
3509 657 : if (!cond_p)
3510 657 : CLEAR_REG_SET (&deps->reg_last_in_use);
3511 :
3512 : /* An entry recorded only in reg_last_dirty holds a debug use or
3513 : a control use that nothing has consumed. The eager form
3514 : folded it into reg_last_in_use here so that the next barrier
3515 : consumed it, so give it this barrier and make it literal.
3516 : Otherwise the use survives into a later insn and depends on
3517 : that insn instead. An entry with no list left needs nothing:
3518 : carrying the pending list is what the eager form would have
3519 : written into it. */
3520 726 : EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_dirty, 0, i, rsi)
3521 : {
3522 69 : struct deps_reg *reg_last = &deps->reg_last[i];
3523 69 : if ((reg_last->uses || reg_last->control_uses)
3524 69 : && !REGNO_REG_SET_P (&deps->reg_last_in_use, i))
3525 : {
3526 0 : reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
3527 0 : SET_REGNO_REG_SET (&deps->reg_last_in_use, i);
3528 : }
3529 : }
3530 657 : CLEAR_REG_SET (&deps->reg_last_dirty);
3531 :
3532 657 : deps->pending_barriers
3533 657 : = alloc_INSN_LIST (insn, deps->pending_barriers);
3534 : }
3535 : }
3536 :
3537 : /* Don't flush pending lists on speculative checks for
3538 : selective scheduling. */
3539 4408945 : if (!sel_sched_p () || !sel_insn_is_speculation_check (insn))
3540 4408945 : flush_pending_lists (deps, insn, true, true);
3541 :
3542 4408945 : reg_pending_barrier = NOT_A_BARRIER;
3543 : }
3544 :
3545 : /* If a post-call group is still open, see if it should remain so.
3546 : This insn must be a simple move of a hard reg to a pseudo or
3547 : vice-versa.
3548 :
3549 : We must avoid moving these insns for correctness on targets
3550 : with small register classes, and for special registers like
3551 : PIC_OFFSET_TABLE_REGNUM. For simplicity, extend this to all
3552 : hard regs for all targets. */
3553 :
3554 116151459 : if (deps->in_post_call_group_p)
3555 : {
3556 1162 : rtx tmp, set = single_set (insn);
3557 1162 : int src_regno, dest_regno;
3558 :
3559 1162 : if (set == NULL)
3560 : {
3561 397 : if (DEBUG_INSN_P (insn))
3562 : /* We don't want to mark debug insns as part of the same
3563 : sched group. We know they really aren't, but if we use
3564 : debug insns to tell that a call group is over, we'll
3565 : get different code if debug insns are not there and
3566 : instructions that follow seem like they should be part
3567 : of the call group.
3568 :
3569 : Also, if we did, chain_to_prev_insn would move the
3570 : deps of the debug insn to the call insn, modifying
3571 : non-debug post-dependency counts of the debug insn
3572 : dependencies and otherwise messing with the scheduling
3573 : order.
3574 :
3575 : Instead, let such debug insns be scheduled freely, but
3576 : keep the call group open in case there are insns that
3577 : should be part of it afterwards. Since we grant debug
3578 : insns higher priority than even sched group insns, it
3579 : will all turn out all right. */
3580 332 : goto debug_dont_end_call_group;
3581 : else
3582 65 : goto end_call_group;
3583 : }
3584 :
3585 765 : tmp = SET_DEST (set);
3586 765 : if (GET_CODE (tmp) == SUBREG)
3587 0 : tmp = SUBREG_REG (tmp);
3588 765 : if (REG_P (tmp))
3589 702 : dest_regno = REGNO (tmp);
3590 : else
3591 63 : goto end_call_group;
3592 :
3593 702 : tmp = SET_SRC (set);
3594 702 : if (GET_CODE (tmp) == SUBREG)
3595 26 : tmp = SUBREG_REG (tmp);
3596 702 : if ((GET_CODE (tmp) == PLUS
3597 702 : || GET_CODE (tmp) == MINUS)
3598 94 : && REG_P (XEXP (tmp, 0))
3599 81 : && REGNO (XEXP (tmp, 0)) == STACK_POINTER_REGNUM
3600 724 : && dest_regno == STACK_POINTER_REGNUM)
3601 : src_regno = STACK_POINTER_REGNUM;
3602 680 : else if (REG_P (tmp))
3603 288 : src_regno = REGNO (tmp);
3604 : else
3605 392 : goto end_call_group;
3606 :
3607 310 : if (src_regno < FIRST_PSEUDO_REGISTER
3608 310 : || dest_regno < FIRST_PSEUDO_REGISTER)
3609 : {
3610 253 : if (!deps->readonly
3611 211 : && deps->in_post_call_group_p == post_call_initial)
3612 0 : deps->in_post_call_group_p = post_call;
3613 :
3614 253 : if (!sel_sched_p () || sched_emulate_haifa_p)
3615 : {
3616 197 : SCHED_GROUP_P (insn) = 1;
3617 197 : CANT_MOVE (insn) = 1;
3618 : }
3619 : }
3620 : else
3621 : {
3622 57 : end_call_group:
3623 577 : if (!deps->readonly)
3624 429 : deps->in_post_call_group_p = not_post_call;
3625 : }
3626 : }
3627 :
3628 116150297 : debug_dont_end_call_group:
3629 116151459 : if ((current_sched_info->flags & DO_SPECULATION)
3630 116151459 : && !sched_insn_is_legitimate_for_speculation_p (insn, 0))
3631 : /* INSN has an internal dependency (e.g. r14 = [r14]) and thus cannot
3632 : be speculated. */
3633 : {
3634 0 : if (sel_sched_p ())
3635 0 : sel_mark_hard_insn (insn);
3636 : else
3637 : {
3638 0 : sd_iterator_def sd_it;
3639 0 : dep_t dep;
3640 :
3641 0 : for (sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK);
3642 0 : sd_iterator_cond (&sd_it, &dep);)
3643 0 : change_spec_dep_to_hard (sd_it);
3644 : }
3645 : }
3646 :
3647 : /* We do not yet have code to adjust REG_ARGS_SIZE, therefore we must
3648 : honor their original ordering. */
3649 116151459 : if (find_reg_note (insn, REG_ARGS_SIZE, NULL))
3650 : {
3651 4042892 : if (deps->last_args_size)
3652 2744103 : add_dependence (insn, deps->last_args_size, REG_DEP_OUTPUT);
3653 4042892 : if (!deps->readonly)
3654 4042731 : deps->last_args_size = insn;
3655 : }
3656 :
3657 : /* We must not mix prologue and epilogue insns. See PR78029. */
3658 116151459 : if (prologue_contains (insn))
3659 : {
3660 3256548 : add_dependence_list (insn, deps->last_epilogue, true, REG_DEP_ANTI, true);
3661 3256548 : if (!deps->readonly)
3662 : {
3663 3256104 : if (deps->last_logue_was_epilogue)
3664 3 : free_INSN_LIST_list (&deps->last_prologue);
3665 3256104 : deps->last_prologue = alloc_INSN_LIST (insn, deps->last_prologue);
3666 3256104 : deps->last_logue_was_epilogue = false;
3667 : }
3668 : }
3669 :
3670 116151459 : if (epilogue_contains (insn))
3671 : {
3672 3166634 : add_dependence_list (insn, deps->last_prologue, true, REG_DEP_ANTI, true);
3673 3166634 : if (!deps->readonly)
3674 : {
3675 3166119 : if (!deps->last_logue_was_epilogue)
3676 1169657 : free_INSN_LIST_list (&deps->last_epilogue);
3677 3166119 : deps->last_epilogue = alloc_INSN_LIST (insn, deps->last_epilogue);
3678 3166119 : deps->last_logue_was_epilogue = true;
3679 : }
3680 : }
3681 116151459 : }
3682 :
3683 : /* Return TRUE if INSN might not always return normally (e.g. call exit,
3684 : longjmp, loop forever, ...). */
3685 : /* FIXME: Why can't this function just use flags_from_decl_or_type and
3686 : test for ECF_NORETURN? */
3687 : static bool
3688 4680201 : call_may_noreturn_p (rtx_insn *insn)
3689 : {
3690 4680201 : rtx call;
3691 :
3692 : /* const or pure calls that aren't looping will always return. */
3693 9222792 : if (RTL_CONST_OR_PURE_CALL_P (insn)
3694 4961770 : && !RTL_LOOPING_CONST_OR_PURE_CALL_P (insn))
3695 : return false;
3696 :
3697 4293230 : call = get_call_rtx_from (insn);
3698 4293230 : if (call && GET_CODE (XEXP (XEXP (call, 0), 0)) == SYMBOL_REF)
3699 : {
3700 4118089 : rtx symbol = XEXP (XEXP (call, 0), 0);
3701 4118089 : if (SYMBOL_REF_DECL (symbol)
3702 4118089 : && TREE_CODE (SYMBOL_REF_DECL (symbol)) == FUNCTION_DECL)
3703 : {
3704 3879872 : if (DECL_BUILT_IN_CLASS (SYMBOL_REF_DECL (symbol))
3705 3879872 : == BUILT_IN_NORMAL)
3706 559034 : switch (DECL_FUNCTION_CODE (SYMBOL_REF_DECL (symbol)))
3707 : {
3708 84628 : case BUILT_IN_BCMP:
3709 84628 : case BUILT_IN_BCOPY:
3710 84628 : case BUILT_IN_BZERO:
3711 84628 : case BUILT_IN_INDEX:
3712 84628 : case BUILT_IN_MEMCHR:
3713 84628 : case BUILT_IN_MEMCMP:
3714 84628 : case BUILT_IN_MEMCPY:
3715 84628 : case BUILT_IN_MEMMOVE:
3716 84628 : case BUILT_IN_MEMPCPY:
3717 84628 : case BUILT_IN_MEMSET:
3718 84628 : case BUILT_IN_RINDEX:
3719 84628 : case BUILT_IN_STPCPY:
3720 84628 : case BUILT_IN_STPNCPY:
3721 84628 : case BUILT_IN_STRCAT:
3722 84628 : case BUILT_IN_STRCHR:
3723 84628 : case BUILT_IN_STRCMP:
3724 84628 : case BUILT_IN_STRCPY:
3725 84628 : case BUILT_IN_STRCSPN:
3726 84628 : case BUILT_IN_STRLEN:
3727 84628 : case BUILT_IN_STRNCAT:
3728 84628 : case BUILT_IN_STRNCMP:
3729 84628 : case BUILT_IN_STRNCPY:
3730 84628 : case BUILT_IN_STRPBRK:
3731 84628 : case BUILT_IN_STRRCHR:
3732 84628 : case BUILT_IN_STRSPN:
3733 84628 : case BUILT_IN_STRSTR:
3734 : /* Assume certain string/memory builtins always return. */
3735 84628 : return false;
3736 : default:
3737 : break;
3738 : }
3739 : }
3740 : }
3741 :
3742 : /* For all other calls assume that they might not always return. */
3743 : return true;
3744 : }
3745 :
3746 : /* Return true if INSN should be made dependent on the previous instruction
3747 : group, and if all INSN's dependencies should be moved to the first
3748 : instruction of that group. */
3749 :
3750 : static bool
3751 57294753 : chain_to_prev_insn_p (rtx_insn *insn)
3752 : {
3753 : /* INSN forms a group with the previous instruction. */
3754 57294753 : if (SCHED_GROUP_P (insn))
3755 : return true;
3756 :
3757 : /* If the previous instruction clobbers a register R and this one sets
3758 : part of R, the clobber was added specifically to help us track the
3759 : liveness of R. There's no point scheduling the clobber and leaving
3760 : INSN behind, especially if we move the clobber to another block. */
3761 53043082 : rtx_insn *prev = prev_nonnote_nondebug_insn (insn);
3762 53043082 : if (prev
3763 52066056 : && INSN_P (prev)
3764 47115128 : && BLOCK_FOR_INSN (prev) == BLOCK_FOR_INSN (insn)
3765 95786060 : && GET_CODE (PATTERN (prev)) == CLOBBER)
3766 : {
3767 83349 : rtx x = XEXP (PATTERN (prev), 0);
3768 83349 : if (set_of (x, insn))
3769 42 : return true;
3770 : }
3771 :
3772 : return false;
3773 : }
3774 :
3775 : /* Analyze INSN with DEPS as a context. */
3776 : void
3777 122112983 : deps_analyze_insn (class deps_desc *deps, rtx_insn *insn)
3778 : {
3779 122112983 : if (sched_deps_info->start_insn)
3780 122093411 : sched_deps_info->start_insn (insn);
3781 :
3782 : /* Record the condition for this insn. */
3783 122112983 : if (NONDEBUG_INSN_P (insn))
3784 : {
3785 61975449 : rtx t;
3786 61975449 : sched_get_condition_with_rev (insn, NULL);
3787 61975449 : t = INSN_CACHED_COND (insn);
3788 61975449 : INSN_COND_DEPS (insn) = NULL;
3789 61975449 : if (reload_completed
3790 61950671 : && (current_sched_info->flags & DO_PREDICATION)
3791 0 : && COMPARISON_P (t)
3792 0 : && REG_P (XEXP (t, 0))
3793 0 : && CONSTANT_P (XEXP (t, 1)))
3794 : {
3795 0 : unsigned int regno;
3796 0 : int nregs;
3797 0 : rtx_insn_list *cond_deps = NULL;
3798 0 : t = XEXP (t, 0);
3799 0 : regno = REGNO (t);
3800 0 : nregs = REG_NREGS (t);
3801 0 : while (nregs-- > 0)
3802 : {
3803 0 : struct deps_reg *reg_last = &deps->reg_last[regno + nregs];
3804 0 : cond_deps = concat_INSN_LIST (reg_last->sets, cond_deps);
3805 0 : cond_deps = concat_INSN_LIST (reg_last->clobbers, cond_deps);
3806 0 : cond_deps = concat_INSN_LIST (reg_last->implicit_sets, cond_deps);
3807 : }
3808 0 : INSN_COND_DEPS (insn) = cond_deps;
3809 : }
3810 : }
3811 :
3812 122112983 : if (JUMP_P (insn))
3813 : {
3814 : /* Make each JUMP_INSN (but not a speculative check)
3815 : a scheduling barrier for memory references. */
3816 7867782 : if (!deps->readonly
3817 7869388 : && !(sel_sched_p ()
3818 1606 : && sel_insn_is_speculation_check (insn)))
3819 : {
3820 : /* Keep the list a reasonable size. */
3821 7866426 : if (deps->pending_flush_length++ >= param_max_pending_list_length)
3822 2 : flush_pending_lists (deps, insn, true, true);
3823 : else
3824 7866424 : deps->pending_jump_insns
3825 7866424 : = alloc_INSN_LIST (insn, deps->pending_jump_insns);
3826 : }
3827 :
3828 : /* For each insn which shouldn't cross a jump, add a dependence. */
3829 7867782 : add_dependence_list_and_free (deps, insn,
3830 : &deps->sched_before_next_jump, 1,
3831 : REG_DEP_ANTI, true);
3832 :
3833 7867782 : sched_analyze_insn (deps, PATTERN (insn), insn);
3834 : }
3835 114245201 : else if (NONJUMP_INSN_P (insn) || DEBUG_INSN_P (insn))
3836 : {
3837 103602973 : sched_analyze_insn (deps, PATTERN (insn), insn);
3838 : }
3839 10642228 : else if (CALL_P (insn))
3840 : {
3841 4680696 : int i;
3842 :
3843 4680696 : CANT_MOVE (insn) = 1;
3844 :
3845 4680696 : if (!reload_completed)
3846 : {
3847 : /* Scheduling across calls may increase register pressure by extending
3848 : live ranges of pseudos over the call. Worse, in presence of setjmp
3849 : it may incorrectly move up an assignment over a longjmp. */
3850 714 : reg_pending_barrier = MOVE_BARRIER;
3851 : }
3852 4679982 : else if (find_reg_note (insn, REG_SETJMP, NULL))
3853 : {
3854 : /* This is setjmp. Assume that all registers, not just
3855 : hard registers, may be clobbered by this call. */
3856 756 : reg_pending_barrier = MOVE_BARRIER;
3857 : }
3858 : else
3859 : {
3860 4679226 : function_abi callee_abi = insn_callee_abi (insn);
3861 449205696 : for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3862 : /* A call may read and modify global register variables. */
3863 439847244 : if (global_regs[i])
3864 : {
3865 120 : SET_REGNO_REG_SET (reg_pending_sets, i);
3866 120 : SET_HARD_REG_BIT (implicit_reg_pending_uses, i);
3867 : }
3868 : /* Other call-clobbered hard regs may be clobbered.
3869 : Since we only have a choice between 'might be clobbered'
3870 : and 'definitely not clobbered', we must include all
3871 : partly call-clobbered registers here. */
3872 439847124 : else if (callee_abi.clobbers_at_least_part_of_reg_p (i))
3873 390683151 : SET_REGNO_REG_SET (reg_pending_clobbers, i);
3874 : /* We don't know what set of fixed registers might be used
3875 : by the function, but it is certain that the stack pointer
3876 : is among them, but be conservative. */
3877 49163973 : else if (fixed_regs[i])
3878 14520442 : SET_HARD_REG_BIT (implicit_reg_pending_uses, i);
3879 : /* The frame pointer is normally not used by the function
3880 : itself, but by the debugger. */
3881 : /* ??? MIPS o32 is an exception. It uses the frame pointer
3882 : in the macro expansion of jal but does not represent this
3883 : fact in the call_insn rtl. */
3884 34643531 : else if (i == FRAME_POINTER_REGNUM
3885 34643531 : || (i == HARD_FRAME_POINTER_REGNUM
3886 4679212 : && (! reload_completed || frame_pointer_needed)))
3887 467551 : SET_HARD_REG_BIT (implicit_reg_pending_uses, i);
3888 : }
3889 :
3890 : /* For each insn which shouldn't cross a call, add a dependence
3891 : between that insn and this call insn. */
3892 4680696 : add_dependence_list_and_free (deps, insn,
3893 : &deps->sched_before_next_call, 1,
3894 : REG_DEP_ANTI, true);
3895 :
3896 4680696 : sched_analyze_insn (deps, PATTERN (insn), insn);
3897 :
3898 : /* If CALL would be in a sched group, then this will violate
3899 : convention that sched group insns have dependencies only on the
3900 : previous instruction.
3901 :
3902 : Of course one can say: "Hey! What about head of the sched group?"
3903 : And I will answer: "Basic principles (one dep per insn) are always
3904 : the same." */
3905 4680696 : gcc_assert (!SCHED_GROUP_P (insn));
3906 :
3907 : /* In the absence of interprocedural alias analysis, we must flush
3908 : all pending reads and writes, and start new dependencies starting
3909 : from here. But only flush writes for constant calls (which may
3910 : be passed a pointer to something we haven't written yet). */
3911 5099914 : flush_pending_lists (deps, insn, true, ! RTL_CONST_OR_PURE_CALL_P (insn));
3912 :
3913 4680696 : if (!deps->readonly)
3914 : {
3915 : /* Remember the last function call for limiting lifetimes. */
3916 4680201 : free_INSN_LIST_list (&deps->last_function_call);
3917 4680201 : deps->last_function_call = alloc_INSN_LIST (insn, NULL_RTX);
3918 :
3919 4680201 : if (call_may_noreturn_p (insn))
3920 : {
3921 : /* Remember the last function call that might not always return
3922 : normally for limiting moves of trapping insns. */
3923 4208602 : free_INSN_LIST_list (&deps->last_function_call_may_noreturn);
3924 4208602 : deps->last_function_call_may_noreturn
3925 4208602 : = alloc_INSN_LIST (insn, NULL_RTX);
3926 : }
3927 :
3928 : /* Before reload, begin a post-call group, so as to keep the
3929 : lifetimes of hard registers correct. */
3930 4680201 : if (! reload_completed)
3931 558 : deps->in_post_call_group_p = post_call;
3932 : }
3933 : }
3934 :
3935 122112983 : if (sched_deps_info->use_cselib)
3936 1535 : cselib_process_insn (insn);
3937 :
3938 122112983 : if (sched_deps_info->finish_insn)
3939 122093411 : sched_deps_info->finish_insn ();
3940 :
3941 : /* Fixup the dependencies in the sched group. */
3942 122112983 : if ((NONJUMP_INSN_P (insn) || JUMP_P (insn))
3943 57294753 : && chain_to_prev_insn_p (insn)
3944 126364696 : && !sel_sched_p ())
3945 4250569 : chain_to_prev_insn (insn);
3946 122112983 : }
3947 :
3948 : /* Initialize DEPS for the new block beginning with HEAD. */
3949 : void
3950 10631423 : deps_start_bb (class deps_desc *deps, rtx_insn *head)
3951 : {
3952 10631423 : gcc_assert (!deps->readonly);
3953 :
3954 : /* Before reload, if the previous block ended in a call, show that
3955 : we are inside a post-call group, so as to keep the lifetimes of
3956 : hard registers correct. */
3957 10631423 : if (! reload_completed && !LABEL_P (head))
3958 : {
3959 1495 : rtx_insn *insn = prev_nonnote_nondebug_insn (head);
3960 :
3961 1495 : if (insn && CALL_P (insn))
3962 5 : deps->in_post_call_group_p = post_call_initial;
3963 : }
3964 10631423 : }
3965 :
3966 : /* Analyze every insn between HEAD and TAIL inclusive, creating backward
3967 : dependencies for each insn. */
3968 : void
3969 10631423 : sched_analyze (class deps_desc *deps, rtx_insn *head, rtx_insn *tail)
3970 : {
3971 10631423 : rtx_insn *insn;
3972 :
3973 10631423 : if (sched_deps_info->use_cselib)
3974 173 : cselib_init (CSELIB_RECORD_MEMORY);
3975 :
3976 10631423 : deps_start_bb (deps, head);
3977 :
3978 122074366 : for (insn = head;; insn = NEXT_INSN (insn))
3979 : {
3980 122074366 : if (INSN_P (insn))
3981 : {
3982 : /* And initialize deps_lists. */
3983 116112834 : sd_init_insn (insn);
3984 : /* Clean up SCHED_GROUP_P which may be set by last
3985 : scheduler pass. */
3986 116112834 : if (SCHED_GROUP_P (insn))
3987 4232832 : SCHED_GROUP_P (insn) = 0;
3988 : }
3989 :
3990 122074366 : deps_analyze_insn (deps, insn);
3991 :
3992 122074366 : if (insn == tail)
3993 : {
3994 10631423 : if (sched_deps_info->use_cselib)
3995 173 : cselib_finish ();
3996 10631423 : return;
3997 : }
3998 111442943 : }
3999 : }
4000 :
4001 : /* Helper for sched_free_deps ().
4002 : Delete INSN's (RESOLVED_P) backward dependencies. */
4003 : static void
4004 116112834 : delete_dep_nodes_in_back_deps (rtx_insn *insn, bool resolved_p)
4005 : {
4006 116112834 : sd_iterator_def sd_it;
4007 116112834 : dep_t dep;
4008 116112834 : sd_list_types_def types;
4009 :
4010 116112834 : if (resolved_p)
4011 : types = SD_LIST_RES_BACK;
4012 : else
4013 4355 : types = SD_LIST_BACK;
4014 :
4015 116112834 : for (sd_it = sd_iterator_start (insn, types);
4016 335013261 : sd_iterator_cond (&sd_it, &dep);)
4017 : {
4018 218900427 : dep_link_t link = *sd_it.linkp;
4019 218900427 : dep_node_t node = DEP_LINK_NODE (link);
4020 218900427 : deps_list_t back_list;
4021 218900427 : deps_list_t forw_list;
4022 :
4023 218900427 : get_back_and_forw_lists (dep, resolved_p, &back_list, &forw_list);
4024 218900427 : remove_from_deps_list (link, back_list);
4025 218900427 : delete_dep_node (node);
4026 : }
4027 116112834 : }
4028 :
4029 : /* Delete (RESOLVED_P) dependencies between HEAD and TAIL together with
4030 : deps_lists. */
4031 : void
4032 10611726 : sched_free_deps (rtx_insn *head, rtx_insn *tail, bool resolved_p)
4033 : {
4034 10611726 : rtx_insn *insn;
4035 10611726 : rtx_insn *next_tail = NEXT_INSN (tail);
4036 :
4037 : /* We make two passes since some insns may be scheduled before their
4038 : dependencies are resolved. */
4039 138198559 : for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
4040 116975107 : if (INSN_P (insn) && INSN_LUID (insn) > 0)
4041 : {
4042 : /* Clear forward deps and leave the dep_nodes to the
4043 : corresponding back_deps list. */
4044 116112834 : if (resolved_p)
4045 116108479 : clear_deps_list (INSN_RESOLVED_FORW_DEPS (insn));
4046 : else
4047 4355 : clear_deps_list (INSN_FORW_DEPS (insn));
4048 : }
4049 127586833 : for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
4050 116975107 : if (INSN_P (insn) && INSN_LUID (insn) > 0)
4051 : {
4052 : /* Clear resolved back deps together with its dep_nodes. */
4053 116112834 : delete_dep_nodes_in_back_deps (insn, resolved_p);
4054 :
4055 116112834 : sd_finish_insn (insn);
4056 : }
4057 10611726 : }
4058 :
4059 : /* Pool of all-zero reg_last arrays. init_deps takes one and free_deps
4060 : returns it, so the O (MAX_REG) zeroing is paid once per pooled array rather
4061 : than once per basic block of every region. free_deps empties every entry
4062 : that was written, so an array coming back is already zero. Selective
4063 : scheduling is excluded: its remove_from_deps can drop a reg_last_in_use bit
4064 : while control_uses is still live, which would return a dirty array. */
4065 : static vec<struct deps_reg *> reg_last_pool;
4066 : static int reg_last_pool_max_reg;
4067 :
4068 : /* Return an all-zero array of MAX_REG deps_reg, from the pool if one of the
4069 : right size is available. */
4070 :
4071 : static struct deps_reg *
4072 10636536 : alloc_reg_last (int max_reg)
4073 : {
4074 10636536 : if (max_reg != reg_last_pool_max_reg)
4075 : {
4076 988959 : while (!reg_last_pool.is_empty ())
4077 4 : free (reg_last_pool.pop ());
4078 988955 : reg_last_pool_max_reg = max_reg;
4079 : }
4080 9647581 : else if (!reg_last_pool.is_empty ())
4081 9641766 : return reg_last_pool.pop ();
4082 :
4083 994770 : return XCNEWVEC (struct deps_reg, max_reg);
4084 : }
4085 :
4086 : /* Give REG_LAST, an array of MAX_REG deps_reg that free_deps has just
4087 : emptied, back to the pool. */
4088 :
4089 : static void
4090 10638002 : release_reg_last (struct deps_reg *reg_last, int max_reg)
4091 : {
4092 10638002 : if (reg_last == NULL)
4093 : return;
4094 :
4095 10636536 : if (sel_sched_p () || max_reg != reg_last_pool_max_reg)
4096 : {
4097 6098 : free (reg_last);
4098 6098 : return;
4099 : }
4100 :
4101 10630438 : if (flag_checking > 1)
4102 1009976238 : for (int i = 0; i < max_reg; i++)
4103 999345917 : gcc_assert (reg_last[i].uses == NULL
4104 : && reg_last[i].sets == NULL
4105 : && reg_last[i].implicit_sets == NULL
4106 : && reg_last[i].control_uses == NULL
4107 : && reg_last[i].clobbers == NULL
4108 : && reg_last[i].uses_length == 0
4109 : && reg_last[i].clobbers_length == 0);
4110 :
4111 10630438 : reg_last_pool.safe_push (reg_last);
4112 : }
4113 :
4114 : /* Initialize variables for region data dependence analysis.
4115 : When LAZY_REG_LAST is true, do not allocate reg_last array
4116 : of class deps_desc immediately. */
4117 :
4118 : void
4119 10637978 : init_deps (class deps_desc *deps, bool lazy_reg_last)
4120 : {
4121 10637978 : int max_reg = (reload_completed ? FIRST_PSEUDO_REGISTER : max_reg_num ());
4122 :
4123 10637978 : deps->max_reg = max_reg;
4124 10637978 : if (lazy_reg_last)
4125 4848 : deps->reg_last = NULL;
4126 : else
4127 10633130 : deps->reg_last = alloc_reg_last (max_reg);
4128 10637978 : INIT_REG_SET (&deps->reg_last_in_use);
4129 10637978 : INIT_REG_SET (&deps->reg_last_dirty);
4130 :
4131 10637978 : deps->pending_read_insns = 0;
4132 10637978 : deps->pending_read_mems = 0;
4133 10637978 : deps->pending_write_insns = 0;
4134 10637978 : deps->pending_write_mems = 0;
4135 10637978 : deps->pending_jump_insns = 0;
4136 10637978 : deps->pending_read_list_length = 0;
4137 10637978 : deps->pending_write_list_length = 0;
4138 10637978 : deps->pending_flush_length = 0;
4139 10637978 : deps->last_pending_memory_flush = 0;
4140 10637978 : deps->last_function_call = 0;
4141 10637978 : deps->last_function_call_may_noreturn = 0;
4142 10637978 : deps->sched_before_next_call = 0;
4143 10637978 : deps->sched_before_next_jump = 0;
4144 10637978 : deps->in_post_call_group_p = not_post_call;
4145 10637978 : deps->last_debug_insn = 0;
4146 10637978 : deps->last_args_size = 0;
4147 10637978 : deps->last_prologue = 0;
4148 10637978 : deps->last_epilogue = 0;
4149 10637978 : deps->last_logue_was_epilogue = false;
4150 10637978 : deps->last_reg_pending_barrier = NOT_A_BARRIER;
4151 10637978 : deps->pending_barriers = 0;
4152 10637978 : deps->readonly = 0;
4153 10637978 : }
4154 :
4155 : /* Init only reg_last field of DEPS, which was not allocated before as
4156 : we inited DEPS lazily. */
4157 : void
4158 3382 : init_deps_reg_last (class deps_desc *deps)
4159 : {
4160 3382 : gcc_assert (deps && deps->max_reg > 0);
4161 3382 : gcc_assert (deps->reg_last == NULL);
4162 :
4163 3382 : deps->reg_last = alloc_reg_last (deps->max_reg);
4164 3382 : }
4165 :
4166 :
4167 : /* Free insn lists found in DEPS. */
4168 :
4169 : void
4170 10638002 : free_deps (class deps_desc *deps)
4171 : {
4172 10638002 : unsigned i;
4173 10638002 : reg_set_iterator rsi;
4174 :
4175 : /* We set max_reg to 0 when this context was already freed. */
4176 10638002 : if (deps->max_reg == 0)
4177 : {
4178 0 : gcc_assert (deps->reg_last == NULL);
4179 0 : return;
4180 : }
4181 10638002 : int max_reg = deps->max_reg;
4182 10638002 : deps->max_reg = 0;
4183 :
4184 10638002 : free_INSN_LIST_list (&deps->pending_read_insns);
4185 10638002 : free_EXPR_LIST_list (&deps->pending_read_mems);
4186 10638002 : free_INSN_LIST_list (&deps->pending_write_insns);
4187 10638002 : free_EXPR_LIST_list (&deps->pending_write_mems);
4188 10638002 : free_INSN_LIST_list (&deps->last_pending_memory_flush);
4189 10638002 : free_INSN_LIST_list (&deps->pending_barriers);
4190 :
4191 : /* Teardown only: fold the entries recorded solely in reg_last_dirty into the
4192 : live set, so that one loop releases everything. free_deps creates no
4193 : dependences, so this merge cannot add one. */
4194 10638002 : IOR_REG_SET (&deps->reg_last_in_use, &deps->reg_last_dirty);
4195 :
4196 : /* Without the EXECUTE_IF_SET, this loop is executed max_reg * nr_regions
4197 : times. For a testcase with 42000 regs and 8000 small basic blocks,
4198 : this loop accounted for nearly 60% (84 sec) of the total -O2 runtime. */
4199 547026990 : EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
4200 : {
4201 536388988 : struct deps_reg *reg_last = &deps->reg_last[i];
4202 536388988 : if (reg_last->uses)
4203 29636409 : free_INSN_LIST_list (®_last->uses);
4204 536388988 : if (reg_last->sets)
4205 376627021 : free_INSN_LIST_list (®_last->sets);
4206 536388988 : if (reg_last->implicit_sets)
4207 296 : free_INSN_LIST_list (®_last->implicit_sets);
4208 536388988 : if (reg_last->control_uses)
4209 118 : free_INSN_LIST_list (®_last->control_uses);
4210 536388988 : if (reg_last->clobbers)
4211 149908737 : free_INSN_LIST_list (®_last->clobbers);
4212 536388988 : reg_last->uses_length = 0;
4213 536388988 : reg_last->clobbers_length = 0;
4214 : }
4215 10638002 : CLEAR_REG_SET (&deps->reg_last_in_use);
4216 10638002 : CLEAR_REG_SET (&deps->reg_last_dirty);
4217 :
4218 : /* As we initialize reg_last lazily, it is possible that we didn't allocate
4219 : it at all. */
4220 10638002 : release_reg_last (deps->reg_last, max_reg);
4221 10638002 : deps->reg_last = NULL;
4222 :
4223 10638002 : deps = NULL;
4224 : }
4225 :
4226 : /* Remove INSN from dependence contexts DEPS. */
4227 : void
4228 2293 : remove_from_deps (class deps_desc *deps, rtx_insn *insn)
4229 : {
4230 2293 : int removed;
4231 2293 : unsigned i;
4232 2293 : reg_set_iterator rsi;
4233 :
4234 2293 : removed = remove_from_both_dependence_lists (insn, &deps->pending_read_insns,
4235 : &deps->pending_read_mems);
4236 2293 : if (!DEBUG_INSN_P (insn))
4237 2268 : deps->pending_read_list_length -= removed;
4238 2293 : removed = remove_from_both_dependence_lists (insn, &deps->pending_write_insns,
4239 : &deps->pending_write_mems);
4240 2293 : deps->pending_write_list_length -= removed;
4241 :
4242 2293 : removed = remove_from_dependence_list (insn, &deps->pending_jump_insns);
4243 2293 : deps->pending_flush_length -= removed;
4244 2293 : removed = remove_from_dependence_list (insn, &deps->last_pending_memory_flush);
4245 2293 : deps->pending_flush_length -= removed;
4246 :
4247 2293 : unsigned to_clear = -1U;
4248 55361 : EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
4249 : {
4250 53068 : if (to_clear != -1U)
4251 : {
4252 9763 : CLEAR_REGNO_REG_SET (&deps->reg_last_in_use, to_clear);
4253 9763 : to_clear = -1U;
4254 : }
4255 53068 : struct deps_reg *reg_last = &deps->reg_last[i];
4256 53068 : if (reg_last->uses)
4257 8449 : remove_from_dependence_list (insn, ®_last->uses);
4258 53068 : if (reg_last->sets)
4259 29535 : remove_from_dependence_list (insn, ®_last->sets);
4260 53068 : if (reg_last->implicit_sets)
4261 358 : remove_from_dependence_list (insn, ®_last->implicit_sets);
4262 53068 : if (reg_last->clobbers)
4263 17881 : remove_from_dependence_list (insn, ®_last->clobbers);
4264 53068 : if (!reg_last->uses && !reg_last->sets && !reg_last->implicit_sets
4265 24043 : && !reg_last->clobbers)
4266 53068 : to_clear = i;
4267 : }
4268 2293 : if (to_clear != -1U)
4269 345 : CLEAR_REGNO_REG_SET (&deps->reg_last_in_use, to_clear);
4270 :
4271 2293 : if (CALL_P (insn))
4272 : {
4273 72 : remove_from_dependence_list (insn, &deps->last_function_call);
4274 72 : remove_from_dependence_list (insn,
4275 : &deps->last_function_call_may_noreturn);
4276 : }
4277 2293 : remove_from_dependence_list (insn, &deps->sched_before_next_call);
4278 2293 : }
4279 :
4280 : /* Init deps data vector. */
4281 : static void
4282 993698 : init_deps_data_vector (void)
4283 : {
4284 993698 : int reserve = (sched_max_luid + 1 - h_d_i_d.length ());
4285 1983811 : if (reserve > 0 && ! h_d_i_d.space (reserve))
4286 990113 : h_d_i_d.safe_grow_cleared (3 * sched_max_luid / 2, true);
4287 993698 : }
4288 :
4289 : /* If it is profitable to use them, initialize or extend (depending on
4290 : GLOBAL_P) dependency data. */
4291 : void
4292 993698 : sched_deps_init (bool global_p)
4293 : {
4294 : /* Average number of insns in the basic block.
4295 : '+ 1' is used to make it nonzero. */
4296 993698 : int insns_in_block = sched_max_luid / n_basic_blocks_for_fn (cfun) + 1;
4297 :
4298 993698 : init_deps_data_vector ();
4299 :
4300 : /* We use another caching mechanism for selective scheduling, so
4301 : we don't use this one. */
4302 993698 : if (!sel_sched_p () && global_p && insns_in_block > 100 * 5)
4303 : {
4304 : /* ?!? We could save some memory by computing a per-region luid mapping
4305 : which could reduce both the number of vectors in the cache and the
4306 : size of each vector. Instead we just avoid the cache entirely unless
4307 : the average number of instructions in a basic block is very high. See
4308 : the comment before the declaration of true_dependency_cache for
4309 : what we consider "very high". */
4310 91 : cache_size = 0;
4311 91 : extend_dependency_caches (sched_max_luid, true);
4312 : }
4313 :
4314 993698 : if (global_p)
4315 : {
4316 989027 : dl_pool = new object_allocator<_deps_list> ("deps_list");
4317 : /* Allocate lists for one block at a time. */
4318 989027 : dn_pool = new object_allocator<_dep_node> ("dep_node");
4319 : /* Allocate nodes for one block at a time. */
4320 : }
4321 993698 : }
4322 :
4323 :
4324 : /* Create or extend (depending on CREATE_P) dependency caches to
4325 : size N. */
4326 : void
4327 91 : extend_dependency_caches (int n, bool create_p)
4328 : {
4329 91 : if (create_p || true_dependency_cache)
4330 : {
4331 91 : int i, luid = cache_size + n;
4332 :
4333 91 : true_dependency_cache = XRESIZEVEC (bitmap_head, true_dependency_cache,
4334 : luid);
4335 91 : output_dependency_cache = XRESIZEVEC (bitmap_head,
4336 : output_dependency_cache, luid);
4337 91 : anti_dependency_cache = XRESIZEVEC (bitmap_head, anti_dependency_cache,
4338 : luid);
4339 91 : control_dependency_cache = XRESIZEVEC (bitmap_head, control_dependency_cache,
4340 : luid);
4341 :
4342 91 : if (current_sched_info->flags & DO_SPECULATION)
4343 0 : spec_dependency_cache = XRESIZEVEC (bitmap_head, spec_dependency_cache,
4344 : luid);
4345 :
4346 629957 : for (i = cache_size; i < luid; i++)
4347 : {
4348 629866 : bitmap_initialize (&true_dependency_cache[i], 0);
4349 629866 : bitmap_initialize (&output_dependency_cache[i], 0);
4350 629866 : bitmap_initialize (&anti_dependency_cache[i], 0);
4351 629866 : bitmap_initialize (&control_dependency_cache[i], 0);
4352 :
4353 629866 : if (current_sched_info->flags & DO_SPECULATION)
4354 0 : bitmap_initialize (&spec_dependency_cache[i], 0);
4355 : }
4356 91 : cache_size = luid;
4357 : }
4358 91 : }
4359 :
4360 : /* Finalize dependency information for the whole function. */
4361 : void
4362 989039 : sched_deps_finish (void)
4363 : {
4364 989039 : gcc_assert (deps_pools_are_empty_p ());
4365 1978066 : delete dn_pool;
4366 1978066 : delete dl_pool;
4367 989039 : dn_pool = NULL;
4368 989039 : dl_pool = NULL;
4369 :
4370 989039 : h_d_i_d.release ();
4371 :
4372 2966746 : while (!reg_last_pool.is_empty ())
4373 988668 : free (reg_last_pool.pop ());
4374 989039 : reg_last_pool.release ();
4375 989039 : reg_last_pool_max_reg = 0;
4376 :
4377 989039 : if (true_dependency_cache)
4378 : {
4379 : int i;
4380 :
4381 629957 : for (i = 0; i < cache_size; i++)
4382 : {
4383 629866 : bitmap_clear (&true_dependency_cache[i]);
4384 629866 : bitmap_clear (&output_dependency_cache[i]);
4385 629866 : bitmap_clear (&anti_dependency_cache[i]);
4386 629866 : bitmap_clear (&control_dependency_cache[i]);
4387 :
4388 629866 : if (sched_deps_info->generate_spec_deps)
4389 0 : bitmap_clear (&spec_dependency_cache[i]);
4390 : }
4391 91 : free (true_dependency_cache);
4392 91 : true_dependency_cache = NULL;
4393 91 : free (output_dependency_cache);
4394 91 : output_dependency_cache = NULL;
4395 91 : free (anti_dependency_cache);
4396 91 : anti_dependency_cache = NULL;
4397 91 : free (control_dependency_cache);
4398 91 : control_dependency_cache = NULL;
4399 :
4400 91 : if (sched_deps_info->generate_spec_deps)
4401 : {
4402 0 : free (spec_dependency_cache);
4403 0 : spec_dependency_cache = NULL;
4404 : }
4405 :
4406 : }
4407 :
4408 989039 : cache_size = 0;
4409 989039 : }
4410 :
4411 : /* Initialize some global variables needed by the dependency analysis
4412 : code. */
4413 :
4414 : void
4415 10631802 : init_deps_global (void)
4416 : {
4417 42527208 : CLEAR_HARD_REG_SET (implicit_reg_pending_clobbers);
4418 10631802 : CLEAR_HARD_REG_SET (implicit_reg_pending_uses);
4419 10631802 : reg_pending_sets = ALLOC_REG_SET (®_obstack);
4420 10631802 : reg_pending_clobbers = ALLOC_REG_SET (®_obstack);
4421 10631802 : reg_pending_uses = ALLOC_REG_SET (®_obstack);
4422 10631802 : reg_pending_control_uses = ALLOC_REG_SET (®_obstack);
4423 10631802 : reg_pending_barrier = NOT_A_BARRIER;
4424 :
4425 10631802 : if (!sel_sched_p () || sched_emulate_haifa_p)
4426 : {
4427 10631087 : sched_deps_info->start_insn = haifa_start_insn;
4428 10631087 : sched_deps_info->finish_insn = haifa_finish_insn;
4429 :
4430 10631087 : sched_deps_info->note_reg_set = haifa_note_reg_set;
4431 10631087 : sched_deps_info->note_reg_clobber = haifa_note_reg_clobber;
4432 10631087 : sched_deps_info->note_reg_use = haifa_note_reg_use;
4433 :
4434 10631087 : sched_deps_info->note_mem_dep = haifa_note_mem_dep;
4435 10631087 : sched_deps_info->note_dep = haifa_note_dep;
4436 : }
4437 10631802 : }
4438 :
4439 : /* Free everything used by the dependency analysis code. */
4440 :
4441 : void
4442 10631802 : finish_deps_global (void)
4443 : {
4444 10631802 : FREE_REG_SET (reg_pending_sets);
4445 10631802 : FREE_REG_SET (reg_pending_clobbers);
4446 10631802 : FREE_REG_SET (reg_pending_uses);
4447 10631802 : FREE_REG_SET (reg_pending_control_uses);
4448 10631802 : }
4449 :
4450 : /* Estimate the weakness of dependence between MEM1 and MEM2. */
4451 : dw_t
4452 518 : estimate_dep_weak (rtx mem1, rtx mem2)
4453 : {
4454 518 : if (mem1 == mem2)
4455 : /* MEMs are the same - don't speculate. */
4456 : return MIN_DEP_WEAK;
4457 :
4458 518 : rtx r1 = XEXP (mem1, 0);
4459 518 : rtx r2 = XEXP (mem2, 0);
4460 :
4461 518 : if (sched_deps_info->use_cselib)
4462 : {
4463 : /* We cannot call rtx_equal_for_cselib_p because the VALUEs might be
4464 : dangling at this point, since we never preserve them. Instead we
4465 : canonicalize manually to get stable VALUEs out of hashing. */
4466 0 : if (GET_CODE (r1) == VALUE && CSELIB_VAL_PTR (r1))
4467 0 : r1 = canonical_cselib_val (CSELIB_VAL_PTR (r1))->val_rtx;
4468 0 : if (GET_CODE (r2) == VALUE && CSELIB_VAL_PTR (r2))
4469 0 : r2 = canonical_cselib_val (CSELIB_VAL_PTR (r2))->val_rtx;
4470 : }
4471 :
4472 518 : if (r1 == r2
4473 518 : || (REG_P (r1) && REG_P (r2) && REGNO (r1) == REGNO (r2)))
4474 : /* Again, MEMs are the same. */
4475 : return MIN_DEP_WEAK;
4476 497 : else if ((REG_P (r1) && !REG_P (r2)) || (!REG_P (r1) && REG_P (r2)))
4477 : /* Different addressing modes - reason to be more speculative,
4478 : than usual. */
4479 : return NO_DEP_WEAK - (NO_DEP_WEAK - UNCERTAIN_DEP_WEAK) / 2;
4480 : else
4481 : /* We can't say anything about the dependence. */
4482 448 : return UNCERTAIN_DEP_WEAK;
4483 : }
4484 :
4485 : /* Add or update backward dependence between INSN and ELEM with type DEP_TYPE.
4486 : This function can handle same INSN and ELEM (INSN == ELEM).
4487 : It is a convenience wrapper. */
4488 : static void
4489 638402782 : add_dependence_1 (rtx_insn *insn, rtx_insn *elem, enum reg_note dep_type)
4490 : {
4491 638402782 : ds_t ds;
4492 638402782 : bool internal;
4493 :
4494 638402782 : if (dep_type == REG_DEP_TRUE)
4495 : ds = DEP_TRUE;
4496 : else if (dep_type == REG_DEP_OUTPUT)
4497 : ds = DEP_OUTPUT;
4498 : else if (dep_type == REG_DEP_CONTROL)
4499 : ds = DEP_CONTROL;
4500 : else
4501 : {
4502 0 : gcc_assert (dep_type == REG_DEP_ANTI);
4503 : ds = DEP_ANTI;
4504 : }
4505 :
4506 : /* When add_dependence is called from inside sched-deps.cc, we expect
4507 : cur_insn to be non-null. */
4508 638402782 : internal = cur_insn != NULL;
4509 638402782 : if (internal)
4510 581496932 : gcc_assert (insn == cur_insn);
4511 : else
4512 56905850 : cur_insn = insn;
4513 :
4514 638402782 : note_dep (elem, ds);
4515 638402782 : if (!internal)
4516 56905850 : cur_insn = NULL;
4517 638402782 : }
4518 :
4519 : /* Return weakness of speculative type TYPE in the dep_status DS,
4520 : without checking to prevent ICEs on malformed input. */
4521 : static dw_t
4522 0 : get_dep_weak_1 (ds_t ds, ds_t type)
4523 : {
4524 0 : ds = ds & type;
4525 :
4526 0 : switch (type)
4527 : {
4528 : case BEGIN_DATA: ds >>= BEGIN_DATA_BITS_OFFSET; break;
4529 0 : case BE_IN_DATA: ds >>= BE_IN_DATA_BITS_OFFSET; break;
4530 0 : case BEGIN_CONTROL: ds >>= BEGIN_CONTROL_BITS_OFFSET; break;
4531 0 : case BE_IN_CONTROL: ds >>= BE_IN_CONTROL_BITS_OFFSET; break;
4532 0 : default: gcc_unreachable ();
4533 : }
4534 :
4535 0 : return (dw_t) ds;
4536 : }
4537 :
4538 : /* Return weakness of speculative type TYPE in the dep_status DS. */
4539 : dw_t
4540 0 : get_dep_weak (ds_t ds, ds_t type)
4541 : {
4542 0 : dw_t dw = get_dep_weak_1 (ds, type);
4543 :
4544 0 : gcc_assert (MIN_DEP_WEAK <= dw && dw <= MAX_DEP_WEAK);
4545 0 : return dw;
4546 : }
4547 :
4548 : /* Return the dep_status, which has the same parameters as DS, except for
4549 : speculative type TYPE, that will have weakness DW. */
4550 : ds_t
4551 0 : set_dep_weak (ds_t ds, ds_t type, dw_t dw)
4552 : {
4553 0 : gcc_assert (MIN_DEP_WEAK <= dw && dw <= MAX_DEP_WEAK);
4554 :
4555 0 : ds &= ~type;
4556 0 : switch (type)
4557 : {
4558 0 : case BEGIN_DATA: ds |= ((ds_t) dw) << BEGIN_DATA_BITS_OFFSET; break;
4559 0 : case BE_IN_DATA: ds |= ((ds_t) dw) << BE_IN_DATA_BITS_OFFSET; break;
4560 0 : case BEGIN_CONTROL: ds |= ((ds_t) dw) << BEGIN_CONTROL_BITS_OFFSET; break;
4561 0 : case BE_IN_CONTROL: ds |= ((ds_t) dw) << BE_IN_CONTROL_BITS_OFFSET; break;
4562 0 : default: gcc_unreachable ();
4563 : }
4564 0 : return ds;
4565 : }
4566 :
4567 : /* Return the join of two dep_statuses DS1 and DS2.
4568 : If MAX_P is true then choose the greater probability,
4569 : otherwise multiply probabilities.
4570 : This function assumes that both DS1 and DS2 contain speculative bits. */
4571 : static ds_t
4572 0 : ds_merge_1 (ds_t ds1, ds_t ds2, bool max_p)
4573 : {
4574 0 : ds_t ds, t;
4575 :
4576 0 : gcc_assert ((ds1 & SPECULATIVE) && (ds2 & SPECULATIVE));
4577 :
4578 0 : ds = (ds1 & DEP_TYPES) | (ds2 & DEP_TYPES);
4579 :
4580 0 : t = FIRST_SPEC_TYPE;
4581 0 : do
4582 : {
4583 0 : if ((ds1 & t) && !(ds2 & t))
4584 0 : ds |= ds1 & t;
4585 0 : else if (!(ds1 & t) && (ds2 & t))
4586 0 : ds |= ds2 & t;
4587 0 : else if ((ds1 & t) && (ds2 & t))
4588 : {
4589 0 : dw_t dw1 = get_dep_weak (ds1, t);
4590 0 : dw_t dw2 = get_dep_weak (ds2, t);
4591 0 : ds_t dw;
4592 :
4593 0 : if (!max_p)
4594 : {
4595 0 : dw = ((ds_t) dw1) * ((ds_t) dw2);
4596 0 : dw /= MAX_DEP_WEAK;
4597 0 : if (dw < MIN_DEP_WEAK)
4598 0 : dw = MIN_DEP_WEAK;
4599 : }
4600 : else
4601 : {
4602 0 : if (dw1 >= dw2)
4603 : dw = dw1;
4604 : else
4605 : dw = dw2;
4606 : }
4607 :
4608 0 : ds = set_dep_weak (ds, t, (dw_t) dw);
4609 : }
4610 :
4611 0 : if (t == LAST_SPEC_TYPE)
4612 : break;
4613 0 : t <<= SPEC_TYPE_SHIFT;
4614 0 : }
4615 : while (1);
4616 :
4617 0 : return ds;
4618 : }
4619 :
4620 : /* Return the join of two dep_statuses DS1 and DS2.
4621 : This function assumes that both DS1 and DS2 contain speculative bits. */
4622 : ds_t
4623 0 : ds_merge (ds_t ds1, ds_t ds2)
4624 : {
4625 0 : return ds_merge_1 (ds1, ds2, false);
4626 : }
4627 :
4628 : /* Return the join of two dep_statuses DS1 and DS2. */
4629 : ds_t
4630 56306 : ds_full_merge (ds_t ds, ds_t ds2, rtx mem1, rtx mem2)
4631 : {
4632 56306 : ds_t new_status = ds | ds2;
4633 :
4634 56306 : if (new_status & SPECULATIVE)
4635 : {
4636 0 : if ((ds && !(ds & SPECULATIVE))
4637 0 : || (ds2 && !(ds2 & SPECULATIVE)))
4638 : /* Then this dep can't be speculative. */
4639 0 : new_status &= ~SPECULATIVE;
4640 : else
4641 : {
4642 : /* Both are speculative. Merging probabilities. */
4643 0 : if (mem1)
4644 : {
4645 0 : dw_t dw;
4646 :
4647 0 : dw = estimate_dep_weak (mem1, mem2);
4648 0 : ds = set_dep_weak (ds, BEGIN_DATA, dw);
4649 : }
4650 :
4651 0 : if (!ds)
4652 : new_status = ds2;
4653 0 : else if (!ds2)
4654 : new_status = ds;
4655 : else
4656 0 : new_status = ds_merge (ds2, ds);
4657 : }
4658 : }
4659 :
4660 56306 : return new_status;
4661 : }
4662 :
4663 : /* Return the join of DS1 and DS2. Use maximum instead of multiplying
4664 : probabilities. */
4665 : ds_t
4666 2270 : ds_max_merge (ds_t ds1, ds_t ds2)
4667 : {
4668 2270 : if (ds1 == 0 && ds2 == 0)
4669 : return 0;
4670 :
4671 0 : if (ds1 == 0 && ds2 != 0)
4672 : return ds2;
4673 :
4674 0 : if (ds1 != 0 && ds2 == 0)
4675 : return ds1;
4676 :
4677 0 : return ds_merge_1 (ds1, ds2, true);
4678 : }
4679 :
4680 : /* Return the probability of speculation success for the speculation
4681 : status DS. */
4682 : dw_t
4683 0 : ds_weak (ds_t ds)
4684 : {
4685 0 : ds_t res = 1, dt;
4686 0 : int n = 0;
4687 :
4688 0 : dt = FIRST_SPEC_TYPE;
4689 0 : do
4690 : {
4691 0 : if (ds & dt)
4692 : {
4693 0 : res *= (ds_t) get_dep_weak (ds, dt);
4694 0 : n++;
4695 : }
4696 :
4697 0 : if (dt == LAST_SPEC_TYPE)
4698 : break;
4699 0 : dt <<= SPEC_TYPE_SHIFT;
4700 : }
4701 : while (1);
4702 :
4703 0 : gcc_assert (n);
4704 0 : while (--n)
4705 0 : res /= MAX_DEP_WEAK;
4706 :
4707 0 : if (res < MIN_DEP_WEAK)
4708 : res = MIN_DEP_WEAK;
4709 :
4710 0 : gcc_assert (res <= MAX_DEP_WEAK);
4711 :
4712 0 : return (dw_t) res;
4713 : }
4714 :
4715 : /* Return a dep status that contains all speculation types of DS. */
4716 : ds_t
4717 5048 : ds_get_speculation_types (ds_t ds)
4718 : {
4719 5048 : if (ds & BEGIN_DATA)
4720 0 : ds |= BEGIN_DATA;
4721 5048 : if (ds & BE_IN_DATA)
4722 0 : ds |= BE_IN_DATA;
4723 5048 : if (ds & BEGIN_CONTROL)
4724 0 : ds |= BEGIN_CONTROL;
4725 5048 : if (ds & BE_IN_CONTROL)
4726 0 : ds |= BE_IN_CONTROL;
4727 :
4728 5048 : return ds & SPECULATIVE;
4729 : }
4730 :
4731 : /* Return a dep status that contains maximal weakness for each speculation
4732 : type present in DS. */
4733 : ds_t
4734 2713 : ds_get_max_dep_weak (ds_t ds)
4735 : {
4736 2713 : if (ds & BEGIN_DATA)
4737 0 : ds = set_dep_weak (ds, BEGIN_DATA, MAX_DEP_WEAK);
4738 2713 : if (ds & BE_IN_DATA)
4739 0 : ds = set_dep_weak (ds, BE_IN_DATA, MAX_DEP_WEAK);
4740 2713 : if (ds & BEGIN_CONTROL)
4741 0 : ds = set_dep_weak (ds, BEGIN_CONTROL, MAX_DEP_WEAK);
4742 2713 : if (ds & BE_IN_CONTROL)
4743 0 : ds = set_dep_weak (ds, BE_IN_CONTROL, MAX_DEP_WEAK);
4744 :
4745 2713 : return ds;
4746 : }
4747 :
4748 : /* Dump information about the dependence status S. */
4749 : static void
4750 0 : dump_ds (FILE *f, ds_t s)
4751 : {
4752 0 : fprintf (f, "{");
4753 :
4754 0 : if (s & BEGIN_DATA)
4755 0 : fprintf (f, "BEGIN_DATA: %d; ", get_dep_weak_1 (s, BEGIN_DATA));
4756 0 : if (s & BE_IN_DATA)
4757 0 : fprintf (f, "BE_IN_DATA: %d; ", get_dep_weak_1 (s, BE_IN_DATA));
4758 0 : if (s & BEGIN_CONTROL)
4759 0 : fprintf (f, "BEGIN_CONTROL: %d; ", get_dep_weak_1 (s, BEGIN_CONTROL));
4760 0 : if (s & BE_IN_CONTROL)
4761 0 : fprintf (f, "BE_IN_CONTROL: %d; ", get_dep_weak_1 (s, BE_IN_CONTROL));
4762 :
4763 0 : if (s & HARD_DEP)
4764 0 : fprintf (f, "HARD_DEP; ");
4765 :
4766 0 : if (s & DEP_TRUE)
4767 0 : fprintf (f, "DEP_TRUE; ");
4768 0 : if (s & DEP_OUTPUT)
4769 0 : fprintf (f, "DEP_OUTPUT; ");
4770 0 : if (s & DEP_ANTI)
4771 0 : fprintf (f, "DEP_ANTI; ");
4772 0 : if (s & DEP_CONTROL)
4773 0 : fprintf (f, "DEP_CONTROL; ");
4774 :
4775 0 : fprintf (f, "}");
4776 0 : }
4777 :
4778 : DEBUG_FUNCTION void
4779 0 : debug_ds (ds_t s)
4780 : {
4781 0 : dump_ds (stderr, s);
4782 0 : fprintf (stderr, "\n");
4783 0 : }
4784 :
4785 : /* Verify that dependence type and status are consistent.
4786 : If RELAXED_P is true, then skip dep_weakness checks. */
4787 : static void
4788 797551327 : check_dep (dep_t dep, bool relaxed_p)
4789 : {
4790 797551327 : enum reg_note dt = DEP_TYPE (dep);
4791 797551327 : ds_t ds = DEP_STATUS (dep);
4792 :
4793 797551327 : gcc_assert (DEP_PRO (dep) != DEP_CON (dep));
4794 :
4795 797551327 : if (!(current_sched_info->flags & USE_DEPS_LIST))
4796 : {
4797 797551327 : gcc_assert (ds == 0);
4798 : return;
4799 : }
4800 :
4801 : /* Check that dependence type contains the same bits as the status. */
4802 0 : if (dt == REG_DEP_TRUE)
4803 0 : gcc_assert (ds & DEP_TRUE);
4804 0 : else if (dt == REG_DEP_OUTPUT)
4805 0 : gcc_assert ((ds & DEP_OUTPUT)
4806 : && !(ds & DEP_TRUE));
4807 0 : else if (dt == REG_DEP_ANTI)
4808 0 : gcc_assert ((ds & DEP_ANTI)
4809 : && !(ds & (DEP_OUTPUT | DEP_TRUE)));
4810 : else
4811 0 : gcc_assert (dt == REG_DEP_CONTROL
4812 : && (ds & DEP_CONTROL)
4813 : && !(ds & (DEP_OUTPUT | DEP_ANTI | DEP_TRUE)));
4814 :
4815 : /* HARD_DEP cannot appear in dep_status of a link. */
4816 0 : gcc_assert (!(ds & HARD_DEP));
4817 :
4818 : /* Check that dependence status is set correctly when speculation is not
4819 : supported. */
4820 0 : if (!sched_deps_info->generate_spec_deps)
4821 0 : gcc_assert (!(ds & SPECULATIVE));
4822 0 : else if (ds & SPECULATIVE)
4823 : {
4824 0 : if (!relaxed_p)
4825 : {
4826 : ds_t type = FIRST_SPEC_TYPE;
4827 :
4828 : /* Check that dependence weakness is in proper range. */
4829 0 : do
4830 : {
4831 0 : if (ds & type)
4832 0 : get_dep_weak (ds, type);
4833 :
4834 0 : if (type == LAST_SPEC_TYPE)
4835 : break;
4836 0 : type <<= SPEC_TYPE_SHIFT;
4837 : }
4838 : while (1);
4839 : }
4840 :
4841 0 : if (ds & BEGIN_SPEC)
4842 : {
4843 : /* Only true dependence can be data speculative. */
4844 0 : if (ds & BEGIN_DATA)
4845 0 : gcc_assert (ds & DEP_TRUE);
4846 :
4847 : /* Control dependencies in the insn scheduler are represented by
4848 : anti-dependencies, therefore only anti dependence can be
4849 : control speculative. */
4850 0 : if (ds & BEGIN_CONTROL)
4851 0 : gcc_assert (ds & DEP_ANTI);
4852 : }
4853 : else
4854 : {
4855 : /* Subsequent speculations should resolve true dependencies. */
4856 0 : gcc_assert ((ds & DEP_TYPES) == DEP_TRUE);
4857 : }
4858 :
4859 : /* Check that true and anti dependencies can't have other speculative
4860 : statuses. */
4861 0 : if (ds & DEP_TRUE)
4862 0 : gcc_assert (ds & (BEGIN_DATA | BE_IN_SPEC));
4863 : /* An output dependence can't be speculative at all. */
4864 0 : gcc_assert (!(ds & DEP_OUTPUT));
4865 0 : if (ds & DEP_ANTI)
4866 0 : gcc_assert (ds & BEGIN_CONTROL);
4867 : }
4868 : }
4869 :
4870 : /* The following code discovers opportunities to switch a memory reference
4871 : and an increment by modifying the address. We ensure that this is done
4872 : only for dependencies that are only used to show a single register
4873 : dependence (using DEP_NONREG and DEP_MULTIPLE), and so that every memory
4874 : instruction involved is subject to only one dep that can cause a pattern
4875 : change.
4876 :
4877 : When we discover a suitable dependency, we fill in the dep_replacement
4878 : structure to show how to modify the memory reference. */
4879 :
4880 : /* Holds information about a pair of memory reference and register increment
4881 : insns which depend on each other, but could possibly be interchanged. */
4882 : struct mem_inc_info
4883 : {
4884 : rtx_insn *inc_insn;
4885 : rtx_insn *mem_insn;
4886 :
4887 : rtx *mem_loc;
4888 : /* A register occurring in the memory address for which we wish to break
4889 : the dependence. This must be identical to the destination register of
4890 : the increment. */
4891 : rtx mem_reg0;
4892 : /* Any kind of index that is added to that register. */
4893 : rtx mem_index;
4894 : /* The constant offset used in the memory address. */
4895 : HOST_WIDE_INT mem_constant;
4896 : /* The constant added in the increment insn. Negated if the increment is
4897 : after the memory address. */
4898 : HOST_WIDE_INT inc_constant;
4899 : /* The source register used in the increment. May be different from mem_reg0
4900 : if the increment occurs before the memory address. */
4901 : rtx inc_input;
4902 : };
4903 :
4904 : /* Verify that the memory location described in MII can be replaced with
4905 : one using NEW_ADDR. Return the new memory reference or NULL_RTX. The
4906 : insn remains unchanged by this function. */
4907 :
4908 : static rtx
4909 1136041 : attempt_change (struct mem_inc_info *mii, rtx new_addr)
4910 : {
4911 1136041 : rtx mem = *mii->mem_loc;
4912 1136041 : rtx new_mem;
4913 :
4914 1136041 : if (!targetm.new_address_profitable_p (mem, mii->mem_insn, new_addr))
4915 : return NULL_RTX;
4916 :
4917 : /* Jump through a lot of hoops to keep the attributes up to date. We
4918 : do not want to call one of the change address variants that take
4919 : an offset even though we know the offset in many cases. These
4920 : assume you are changing where the address is pointing by the
4921 : offset. */
4922 1136041 : new_mem = replace_equiv_address_nv (mem, new_addr);
4923 1136041 : if (! validate_change (mii->mem_insn, mii->mem_loc, new_mem, 0))
4924 : {
4925 1 : if (sched_verbose >= 5)
4926 0 : fprintf (sched_dump, "validation failure\n");
4927 : return NULL_RTX;
4928 : }
4929 :
4930 : /* Put back the old one. */
4931 1136040 : validate_change (mii->mem_insn, mii->mem_loc, mem, 0);
4932 :
4933 1136040 : return new_mem;
4934 : }
4935 :
4936 : /* Return true if INSN is of a form "a = b op c" where a and b are
4937 : regs. op is + if c is a reg and +|- if c is a const. Fill in
4938 : informantion in MII about what is found.
4939 : BEFORE_MEM indicates whether the increment is found before or after
4940 : a corresponding memory reference. */
4941 :
4942 : static bool
4943 35611867 : parse_add_or_inc (struct mem_inc_info *mii, rtx_insn *insn, bool before_mem)
4944 : {
4945 35611867 : rtx pat = single_set (insn);
4946 35611867 : rtx src, cst;
4947 35611867 : bool regs_equal;
4948 :
4949 35611867 : if (RTX_FRAME_RELATED_P (insn) || !pat)
4950 : return false;
4951 :
4952 : /* Do not allow breaking data dependencies for insns that are marked
4953 : with REG_STACK_CHECK. */
4954 29258865 : if (find_reg_note (insn, REG_STACK_CHECK, NULL))
4955 : return false;
4956 :
4957 : /* Result must be single reg. */
4958 29258865 : if (!REG_P (SET_DEST (pat)))
4959 : return false;
4960 :
4961 20690201 : if (GET_CODE (SET_SRC (pat)) != PLUS)
4962 : return false;
4963 :
4964 4816003 : mii->inc_insn = insn;
4965 4816003 : src = SET_SRC (pat);
4966 4816003 : mii->inc_input = XEXP (src, 0);
4967 :
4968 4816003 : if (!REG_P (XEXP (src, 0)))
4969 : return false;
4970 :
4971 4593024 : if (!rtx_equal_p (SET_DEST (pat), mii->mem_reg0))
4972 : return false;
4973 :
4974 2939938 : cst = XEXP (src, 1);
4975 2939938 : if (!CONST_INT_P (cst))
4976 : return false;
4977 2801962 : mii->inc_constant = INTVAL (cst);
4978 :
4979 2801962 : regs_equal = rtx_equal_p (mii->inc_input, mii->mem_reg0);
4980 :
4981 2801962 : if (!before_mem)
4982 : {
4983 2010842 : mii->inc_constant = -mii->inc_constant;
4984 2010842 : if (!regs_equal)
4985 : return false;
4986 : }
4987 :
4988 2752988 : if (regs_equal && REGNO (SET_DEST (pat)) == STACK_POINTER_REGNUM)
4989 : {
4990 : /* Note that the sign has already been reversed for !before_mem. */
4991 2345110 : if (STACK_GROWS_DOWNWARD)
4992 2345110 : return mii->inc_constant > 0;
4993 : else
4994 : return mii->inc_constant < 0;
4995 : }
4996 : return true;
4997 : }
4998 :
4999 : /* Once a suitable mem reference has been found and the corresponding data
5000 : in MII has been filled in, this function is called to find a suitable
5001 : add or inc insn involving the register we found in the memory
5002 : reference.
5003 : If successful, this function will create additional dependencies between
5004 : - mii->inc_insn's producers and mii->mem_insn as a consumer (if backwards)
5005 : - mii->inc_insn's consumers and mii->mem_insn as a producer (if !backwards).
5006 : */
5007 :
5008 : static bool
5009 31384813 : find_inc (struct mem_inc_info *mii, bool backwards)
5010 : {
5011 31384813 : sd_iterator_def sd_it;
5012 31384813 : dep_t dep;
5013 31384813 : sd_list_types_def mem_deps = backwards ? SD_LIST_HARD_BACK : SD_LIST_FORW;
5014 31384813 : int n_mem_deps = dep_list_size (mii->mem_insn, mem_deps);
5015 :
5016 31384813 : sd_it = sd_iterator_start (mii->mem_insn, mem_deps);
5017 104996440 : while (sd_iterator_cond (&sd_it, &dep))
5018 : {
5019 74747667 : dep_node_t node = DEP_LINK_NODE (*sd_it.linkp);
5020 74747667 : rtx_insn *pro = DEP_PRO (dep);
5021 74747667 : rtx_insn *con = DEP_CON (dep);
5022 74747667 : rtx_insn *inc_cand;
5023 74747667 : int n_inc_deps;
5024 :
5025 74747667 : if (DEP_NONREG (dep) || DEP_MULTIPLE (dep))
5026 39041647 : goto next;
5027 :
5028 35706020 : if (backwards)
5029 : {
5030 14872144 : inc_cand = pro;
5031 14872144 : n_inc_deps = dep_list_size (inc_cand, SD_LIST_BACK);
5032 : }
5033 : else
5034 : {
5035 20833876 : inc_cand = con;
5036 20833876 : n_inc_deps = dep_list_size (inc_cand, SD_LIST_FORW);
5037 : }
5038 :
5039 : /* In the FOR_EACH_DEP loop below we will create additional n_inc_deps
5040 : for mem_insn. This by itself is not a problem, since each mem_insn
5041 : will have only a few inc_insns associated with it. However, if
5042 : we consider that a single inc_insn may have a lot of mem_insns, AND,
5043 : on top of that, a few other inc_insns associated with it --
5044 : those _other inc_insns_ will get (n_mem_deps * number of MEM insns)
5045 : dependencies created for them. This may cause an exponential
5046 : growth of memory usage and scheduling time.
5047 : See PR96388 for details.
5048 : We [heuristically] use n_inc_deps as a proxy for the number of MEM
5049 : insns, and drop opportunities for breaking modifiable_mem dependencies
5050 : when dependency lists grow beyond reasonable size. */
5051 35706020 : if (n_mem_deps * n_inc_deps
5052 35706020 : >= param_max_pending_list_length * param_max_pending_list_length)
5053 94153 : goto next;
5054 :
5055 35611867 : if (parse_add_or_inc (mii, inc_cand, backwards))
5056 : {
5057 1137251 : struct dep_replacement *desc;
5058 1137251 : df_ref def;
5059 1137251 : rtx newaddr, newmem;
5060 :
5061 1137251 : if (sched_verbose >= 5)
5062 0 : fprintf (sched_dump, "candidate mem/inc pair: %d %d\n",
5063 0 : INSN_UID (mii->mem_insn), INSN_UID (inc_cand));
5064 :
5065 : /* Need to assure that none of the operands of the inc
5066 : instruction are assigned to by the mem insn. */
5067 1618747 : FOR_EACH_INSN_DEF (def, mii->mem_insn)
5068 482706 : if (reg_overlap_mentioned_p (DF_REF_REG (def), mii->inc_input)
5069 482706 : || reg_overlap_mentioned_p (DF_REF_REG (def), mii->mem_reg0))
5070 : {
5071 1210 : if (sched_verbose >= 5)
5072 0 : fprintf (sched_dump,
5073 : "inc conflicts with store failure.\n");
5074 1210 : goto next;
5075 : }
5076 :
5077 1136041 : newaddr = mii->inc_input;
5078 1136041 : if (mii->mem_index != NULL_RTX)
5079 21799 : newaddr = gen_rtx_PLUS (GET_MODE (newaddr), newaddr,
5080 : mii->mem_index);
5081 2272082 : newaddr = plus_constant (GET_MODE (newaddr), newaddr,
5082 1136041 : mii->mem_constant + mii->inc_constant);
5083 1136041 : newmem = attempt_change (mii, newaddr);
5084 1136041 : if (newmem == NULL_RTX)
5085 1 : goto next;
5086 1136040 : if (sched_verbose >= 5)
5087 0 : fprintf (sched_dump, "successful address replacement\n");
5088 1136040 : desc = XCNEW (struct dep_replacement);
5089 1136040 : DEP_REPLACE (dep) = desc;
5090 1136040 : desc->loc = mii->mem_loc;
5091 1136040 : desc->newval = newmem;
5092 1136040 : desc->orig = *desc->loc;
5093 1136040 : desc->insn = mii->mem_insn;
5094 3408120 : move_dep_link (DEP_NODE_BACK (node), INSN_HARD_BACK_DEPS (con),
5095 1136040 : INSN_SPEC_BACK_DEPS (con));
5096 :
5097 : /* Make sure that n_inc_deps above is consistent with dependencies
5098 : we create. */
5099 1136040 : gcc_assert (mii->inc_insn == inc_cand);
5100 :
5101 1136040 : if (backwards)
5102 : {
5103 2031020 : FOR_EACH_DEP (mii->inc_insn, SD_LIST_BACK, sd_it, dep)
5104 1838947 : add_dependence_1 (mii->mem_insn, DEP_PRO (dep),
5105 : REG_DEP_TRUE);
5106 : }
5107 : else
5108 : {
5109 6914240 : FOR_EACH_DEP (mii->inc_insn, SD_LIST_FORW, sd_it, dep)
5110 5970273 : add_dependence_1 (DEP_CON (dep), mii->mem_insn,
5111 : REG_DEP_ANTI);
5112 : }
5113 : return true;
5114 : }
5115 34474616 : next:
5116 73611627 : sd_iterator_next (&sd_it);
5117 : }
5118 : return false;
5119 : }
5120 :
5121 : /* A recursive function that walks ADDRESS_OF_X to find memory references
5122 : which could be modified during scheduling. We call find_inc for each
5123 : one we find that has a recognizable form. MII holds information about
5124 : the pair of memory/increment instructions.
5125 : We ensure that every instruction with a memory reference (which will be
5126 : the location of the replacement) is assigned at most one breakable
5127 : dependency. */
5128 :
5129 : static bool
5130 260413375 : find_mem (struct mem_inc_info *mii, rtx *address_of_x)
5131 : {
5132 260413375 : rtx x = *address_of_x;
5133 260413375 : enum rtx_code code = GET_CODE (x);
5134 260413375 : const char *const fmt = GET_RTX_FORMAT (code);
5135 260413375 : int i;
5136 :
5137 260413375 : if (code == MEM)
5138 : {
5139 26181653 : rtx reg0 = XEXP (x, 0);
5140 :
5141 26181653 : mii->mem_loc = address_of_x;
5142 26181653 : mii->mem_index = NULL_RTX;
5143 26181653 : mii->mem_constant = 0;
5144 26181653 : if (GET_CODE (reg0) == PLUS && CONST_INT_P (XEXP (reg0, 1)))
5145 : {
5146 13359453 : mii->mem_constant = INTVAL (XEXP (reg0, 1));
5147 13359453 : reg0 = XEXP (reg0, 0);
5148 : }
5149 26181653 : if (GET_CODE (reg0) == PLUS)
5150 : {
5151 1127541 : mii->mem_index = XEXP (reg0, 1);
5152 1127541 : reg0 = XEXP (reg0, 0);
5153 : }
5154 26181653 : if (REG_P (reg0))
5155 : {
5156 16427325 : df_ref use;
5157 16427325 : int occurrences = 0;
5158 :
5159 : /* Make sure this reg appears only once in this insn. Can't use
5160 : count_occurrences since that only works for pseudos. */
5161 40890242 : FOR_EACH_INSN_USE (use, mii->mem_insn)
5162 25101799 : if (reg_overlap_mentioned_p (reg0, DF_REF_REG (use)))
5163 17066207 : if (++occurrences > 1)
5164 : {
5165 638882 : if (sched_verbose >= 5)
5166 0 : fprintf (sched_dump, "mem count failure\n");
5167 : return false;
5168 : }
5169 :
5170 15788443 : mii->mem_reg0 = reg0;
5171 15788443 : return find_inc (mii, true) || find_inc (mii, false);
5172 : }
5173 : return false;
5174 : }
5175 :
5176 234231722 : if (code == SIGN_EXTRACT || code == ZERO_EXTRACT)
5177 : {
5178 : /* If REG occurs inside a MEM used in a bit-field reference,
5179 : that is unacceptable. */
5180 : return false;
5181 : }
5182 :
5183 : /* Time for some deep diving. */
5184 550180295 : for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
5185 : {
5186 317236024 : if (fmt[i] == 'e')
5187 : {
5188 183901621 : if (find_mem (mii, &XEXP (x, i)))
5189 : return true;
5190 : }
5191 133334403 : else if (fmt[i] == 'E')
5192 : {
5193 8694019 : int j;
5194 26974939 : for (j = XVECLEN (x, i) - 1; j >= 0; j--)
5195 18305104 : if (find_mem (mii, &XVECEXP (x, i, j)))
5196 : return true;
5197 : }
5198 : }
5199 : return false;
5200 : }
5201 :
5202 :
5203 : /* Examine the instructions between HEAD and TAIL and try to find
5204 : dependencies that can be broken by modifying one of the patterns. */
5205 :
5206 : void
5207 10610721 : find_modifiable_mems (rtx_insn *head, rtx_insn *tail)
5208 : {
5209 10610721 : rtx_insn *insn, *next_tail = NEXT_INSN (tail);
5210 10610721 : int success_in_block = 0;
5211 :
5212 137329913 : for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
5213 : {
5214 116108471 : struct mem_inc_info mii;
5215 :
5216 116108471 : if (!NONDEBUG_INSN_P (insn) || RTX_FRAME_RELATED_P (insn))
5217 57901821 : continue;
5218 :
5219 58206650 : mii.mem_insn = insn;
5220 58206650 : if (find_mem (&mii, &PATTERN (insn)))
5221 1136040 : success_in_block++;
5222 : }
5223 10610721 : if (success_in_block && sched_verbose >= 5)
5224 0 : fprintf (sched_dump, "%d candidates for address modification found.\n",
5225 : success_in_block);
5226 10610721 : }
5227 :
5228 : #if CHECKING_P
5229 :
5230 : namespace selftest {
5231 :
5232 : /* Verify that free_deps releases entries recorded only in reg_last_dirty. */
5233 :
5234 : static void
5235 4 : test_dirty_reg_last_release ()
5236 : {
5237 4 : bitmap_obstack test_obstack;
5238 4 : bitmap_obstack_initialize (&test_obstack);
5239 :
5240 4 : deps_desc deps = {};
5241 4 : deps.max_reg = 2;
5242 4 : deps.reg_last = XCNEWVEC (deps_reg, deps.max_reg);
5243 4 : bitmap_initialize (&deps.reg_last_in_use, &test_obstack);
5244 4 : bitmap_initialize (&deps.reg_last_dirty, &test_obstack);
5245 :
5246 4 : rtx_insn_list *uses = alloc_INSN_LIST (NULL_RTX, NULL_RTX);
5247 4 : rtx_insn_list *control_uses = alloc_INSN_LIST (NULL_RTX, NULL_RTX);
5248 4 : deps.reg_last[1].uses = uses;
5249 4 : deps.reg_last[1].control_uses = control_uses;
5250 4 : SET_REGNO_REG_SET (&deps.reg_last_dirty, 1);
5251 :
5252 4 : common_sched_info_def sched_info = {};
5253 4 : sched_info.sched_pass_id = SCHED_RGN_PASS;
5254 4 : common_sched_info_def *saved_common_sched_info = common_sched_info;
5255 4 : common_sched_info = &sched_info;
5256 4 : free_deps (&deps);
5257 4 : common_sched_info = saved_common_sched_info;
5258 :
5259 4 : ASSERT_EQ (0, deps.max_reg);
5260 4 : ASSERT_EQ (NULL, deps.reg_last);
5261 :
5262 4 : rtx_insn_list *first = alloc_INSN_LIST (NULL_RTX, NULL_RTX);
5263 4 : rtx_insn_list *second = alloc_INSN_LIST (NULL_RTX, NULL_RTX);
5264 4 : ASSERT_TRUE ((first == control_uses && second == uses)
5265 : || (first == uses && second == control_uses));
5266 4 : free_INSN_LIST_list (&first);
5267 4 : free_INSN_LIST_list (&second);
5268 :
5269 4 : sched_deps_finish ();
5270 4 : bitmap_obstack_release (&test_obstack);
5271 4 : }
5272 :
5273 : /* Verify that a pooled reg_last array is empty when it is reused. */
5274 :
5275 : static void
5276 4 : test_reg_last_pool ()
5277 : {
5278 4 : const int max_reg = 3;
5279 4 : ASSERT_TRUE (reg_last_pool.is_empty ());
5280 :
5281 4 : bitmap_obstack test_obstack;
5282 4 : bitmap_obstack_initialize (&test_obstack);
5283 :
5284 4 : deps_desc deps = {};
5285 4 : deps.max_reg = max_reg;
5286 4 : deps.reg_last = alloc_reg_last (max_reg);
5287 4 : struct deps_reg *saved_reg_last = deps.reg_last;
5288 4 : bitmap_initialize (&deps.reg_last_in_use, &test_obstack);
5289 4 : bitmap_initialize (&deps.reg_last_dirty, &test_obstack);
5290 :
5291 4 : deps.reg_last[0].uses = alloc_INSN_LIST (NULL_RTX, NULL_RTX);
5292 4 : deps.reg_last[0].sets = alloc_INSN_LIST (NULL_RTX, NULL_RTX);
5293 4 : deps.reg_last[0].implicit_sets = alloc_INSN_LIST (NULL_RTX, NULL_RTX);
5294 4 : deps.reg_last[0].clobbers = alloc_INSN_LIST (NULL_RTX, NULL_RTX);
5295 4 : deps.reg_last[0].uses_length = 2;
5296 4 : deps.reg_last[0].clobbers_length = 3;
5297 4 : SET_REGNO_REG_SET (&deps.reg_last_in_use, 0);
5298 :
5299 4 : deps.reg_last[1].control_uses = alloc_INSN_LIST (NULL_RTX, NULL_RTX);
5300 4 : SET_REGNO_REG_SET (&deps.reg_last_dirty, 1);
5301 :
5302 4 : common_sched_info_def sched_info = {};
5303 4 : sched_info.sched_pass_id = SCHED_RGN_PASS;
5304 4 : common_sched_info_def *saved_common_sched_info = common_sched_info;
5305 4 : common_sched_info = &sched_info;
5306 4 : free_deps (&deps);
5307 :
5308 4 : ASSERT_EQ (0, deps.max_reg);
5309 4 : ASSERT_EQ (NULL, deps.reg_last);
5310 4 : ASSERT_EQ (1, reg_last_pool.length ());
5311 :
5312 4 : struct deps_reg *reused_reg_last = alloc_reg_last (max_reg);
5313 4 : ASSERT_EQ (saved_reg_last, reused_reg_last);
5314 8 : ASSERT_TRUE (reg_last_pool.is_empty ());
5315 16 : for (int i = 0; i < max_reg; ++i)
5316 : {
5317 12 : ASSERT_EQ (NULL, reused_reg_last[i].uses);
5318 12 : ASSERT_EQ (NULL, reused_reg_last[i].sets);
5319 12 : ASSERT_EQ (NULL, reused_reg_last[i].implicit_sets);
5320 12 : ASSERT_EQ (NULL, reused_reg_last[i].control_uses);
5321 12 : ASSERT_EQ (NULL, reused_reg_last[i].clobbers);
5322 12 : ASSERT_EQ (0, reused_reg_last[i].uses_length);
5323 12 : ASSERT_EQ (0, reused_reg_last[i].clobbers_length);
5324 : }
5325 :
5326 4 : free (reused_reg_last);
5327 4 : sched_deps_finish ();
5328 4 : common_sched_info = saved_common_sched_info;
5329 4 : bitmap_obstack_release (&test_obstack);
5330 4 : }
5331 :
5332 : /* Dependence producers recorded by observe_barrier_dependence. */
5333 :
5334 : static auto_vec<rtx_insn *> *observed_barrier_deps;
5335 :
5336 : /* Record a barrier dependence on PRODUCER. */
5337 :
5338 : static void
5339 388 : observe_barrier_dependence (rtx_insn *producer, ds_t)
5340 : {
5341 388 : gcc_assert (observed_barrier_deps);
5342 388 : observed_barrier_deps->safe_push (producer);
5343 388 : }
5344 :
5345 : /* Assert that LIST contains FIRST followed by SECOND and nothing else. */
5346 :
5347 : static void
5348 20 : assert_insn_list (rtx_insn_list *list, rtx_insn *first, rtx_insn *second)
5349 : {
5350 20 : ASSERT_TRUE (list);
5351 20 : ASSERT_EQ (first, list->insn ());
5352 20 : list = list->next ();
5353 20 : ASSERT_TRUE (list);
5354 20 : ASSERT_EQ (second, list->insn ());
5355 20 : ASSERT_EQ (NULL, list->next ());
5356 20 : }
5357 :
5358 : /* Verify that a full materialisation bitmap does not emit an inert pending
5359 : barrier. OBSTACK owns the context bitmaps. BARRIER is the current
5360 : barrier, OLD_BARRIER is pending, and SETTER is in every literal entry. */
5361 :
5362 : static void
5363 4 : test_full_lazy_barrier (bitmap_obstack *obstack, rtx_insn *barrier,
5364 : rtx_insn *old_barrier, rtx_insn *setter)
5365 : {
5366 4 : deps_desc deps = {};
5367 4 : deps.max_reg = FIRST_PSEUDO_REGISTER;
5368 4 : deps.reg_last = alloc_reg_last (deps.max_reg);
5369 4 : bitmap_initialize (&deps.reg_last_in_use, obstack);
5370 4 : bitmap_initialize (&deps.reg_last_dirty, obstack);
5371 4 : bitmap_set_range (&deps.reg_last_in_use, 0, deps.max_reg);
5372 :
5373 384 : for (int i = 0; i < deps.max_reg; ++i)
5374 376 : deps.reg_last[i].sets = alloc_INSN_LIST (setter, NULL_RTX);
5375 4 : deps.pending_barriers = alloc_INSN_LIST (old_barrier, NULL_RTX);
5376 :
5377 4 : auto_vec<rtx_insn *> observed;
5378 4 : gcc_assert (!observed_barrier_deps);
5379 4 : observed_barrier_deps = &observed;
5380 4 : sched_analyze_insn (&deps, PATTERN (barrier), barrier);
5381 4 : observed_barrier_deps = NULL;
5382 :
5383 8 : ASSERT_EQ ((unsigned) deps.max_reg, observed.length ());
5384 380 : for (int i = 0; i < deps.max_reg; ++i)
5385 376 : ASSERT_EQ (setter, observed[i]);
5386 4 : ASSERT_TRUE (deps.pending_barriers);
5387 4 : ASSERT_EQ (barrier, deps.pending_barriers->insn ());
5388 4 : ASSERT_EQ (NULL, deps.pending_barriers->next ());
5389 :
5390 4 : free_deps (&deps);
5391 4 : }
5392 :
5393 : /* Verify that a pending barrier is emitted at the first gap in the
5394 : materialisation bitmap. OBSTACK owns the context bitmaps. BARRIER is the
5395 : current barrier, OLD_BARRIER is pending, and SETTER0 and SETTER2 are the
5396 : literal entries. */
5397 :
5398 : static void
5399 4 : test_sparse_lazy_barrier (bitmap_obstack *obstack, rtx_insn *barrier,
5400 : rtx_insn *old_barrier, rtx_insn *setter0,
5401 : rtx_insn *setter2)
5402 : {
5403 4 : deps_desc deps = {};
5404 4 : deps.max_reg = 4;
5405 4 : deps.reg_last = alloc_reg_last (deps.max_reg);
5406 4 : bitmap_initialize (&deps.reg_last_in_use, obstack);
5407 4 : bitmap_initialize (&deps.reg_last_dirty, obstack);
5408 4 : SET_REGNO_REG_SET (&deps.reg_last_in_use, 0);
5409 4 : SET_REGNO_REG_SET (&deps.reg_last_in_use, 2);
5410 4 : deps.reg_last[0].sets = alloc_INSN_LIST (setter0, NULL_RTX);
5411 4 : deps.reg_last[2].sets = alloc_INSN_LIST (setter2, NULL_RTX);
5412 4 : deps.pending_barriers = alloc_INSN_LIST (old_barrier, NULL_RTX);
5413 :
5414 4 : auto_vec<rtx_insn *> observed;
5415 4 : gcc_assert (!observed_barrier_deps);
5416 4 : observed_barrier_deps = &observed;
5417 4 : sched_analyze_insn (&deps, PATTERN (barrier), barrier);
5418 4 : observed_barrier_deps = NULL;
5419 :
5420 4 : ASSERT_EQ (3, observed.length ());
5421 4 : ASSERT_EQ (setter0, observed[0]);
5422 4 : ASSERT_EQ (old_barrier, observed[1]);
5423 4 : ASSERT_EQ (setter2, observed[2]);
5424 4 : ASSERT_TRUE (deps.pending_barriers);
5425 4 : ASSERT_EQ (barrier, deps.pending_barriers->insn ());
5426 4 : ASSERT_EQ (NULL, deps.pending_barriers->next ());
5427 :
5428 4 : free_deps (&deps);
5429 4 : }
5430 :
5431 : /* Verify all combinations of literal and lazy entries in deps_join.
5432 : OBSTACK owns both contexts' bitmaps. */
5433 :
5434 : static void
5435 4 : test_lazy_barrier_join (bitmap_obstack *obstack)
5436 : {
5437 4 : const int max_reg = 4;
5438 4 : deps_desc succ = {};
5439 4 : deps_desc pred = {};
5440 4 : succ.max_reg = max_reg;
5441 4 : pred.max_reg = max_reg;
5442 4 : succ.reg_last = alloc_reg_last (max_reg);
5443 4 : pred.reg_last = alloc_reg_last (max_reg);
5444 4 : bitmap_initialize (&succ.reg_last_in_use, obstack);
5445 4 : bitmap_initialize (&succ.reg_last_dirty, obstack);
5446 4 : bitmap_initialize (&pred.reg_last_in_use, obstack);
5447 4 : bitmap_initialize (&pred.reg_last_dirty, obstack);
5448 :
5449 4 : rtx_insn *p = make_insn_raw (gen_rtx_USE (VOIDmode, const0_rtx));
5450 4 : rtx_insn *q = make_insn_raw (gen_rtx_USE (VOIDmode, const0_rtx));
5451 4 : rtx_insn *a1 = make_insn_raw (gen_rtx_USE (VOIDmode, const0_rtx));
5452 4 : rtx_insn *p2 = make_insn_raw (gen_rtx_USE (VOIDmode, const0_rtx));
5453 4 : rtx_insn *a3 = make_insn_raw (gen_rtx_USE (VOIDmode, const0_rtx));
5454 4 : rtx_insn *p3 = make_insn_raw (gen_rtx_USE (VOIDmode, const0_rtx));
5455 :
5456 4 : succ.pending_barriers = alloc_INSN_LIST (q, NULL_RTX);
5457 4 : pred.pending_barriers = alloc_INSN_LIST (p, NULL_RTX);
5458 :
5459 4 : succ.reg_last[1].sets = alloc_INSN_LIST (a1, NULL_RTX);
5460 4 : SET_REGNO_REG_SET (&succ.reg_last_in_use, 1);
5461 4 : pred.reg_last[2].sets = alloc_INSN_LIST (p2, NULL_RTX);
5462 4 : SET_REGNO_REG_SET (&pred.reg_last_in_use, 2);
5463 4 : succ.reg_last[3].sets = alloc_INSN_LIST (a3, NULL_RTX);
5464 4 : pred.reg_last[3].sets = alloc_INSN_LIST (p3, NULL_RTX);
5465 4 : SET_REGNO_REG_SET (&succ.reg_last_in_use, 3);
5466 4 : SET_REGNO_REG_SET (&pred.reg_last_in_use, 3);
5467 :
5468 4 : deps_join (&succ, &pred);
5469 :
5470 4 : ASSERT_FALSE (REGNO_REG_SET_P (&succ.reg_last_in_use, 0));
5471 4 : ASSERT_TRUE (REGNO_REG_SET_P (&succ.reg_last_in_use, 1));
5472 4 : ASSERT_TRUE (REGNO_REG_SET_P (&succ.reg_last_in_use, 2));
5473 4 : ASSERT_TRUE (REGNO_REG_SET_P (&succ.reg_last_in_use, 3));
5474 4 : assert_insn_list (succ.pending_barriers, p, q);
5475 :
5476 4 : struct deps_reg *reg0 = deps_reg_last (&succ, 0);
5477 4 : assert_insn_list (reg0->sets, p, q);
5478 4 : assert_insn_list (succ.reg_last[1].sets, p, a1);
5479 4 : assert_insn_list (succ.reg_last[2].sets, p2, q);
5480 4 : assert_insn_list (succ.reg_last[3].sets, p3, a3);
5481 :
5482 4 : free_deps (&succ);
5483 4 : free_deps (&pred);
5484 4 : }
5485 :
5486 : /* Exercise lazy barriers with target-neutral raw insns. */
5487 :
5488 : static void
5489 4 : test_lazy_barriers ()
5490 : {
5491 4 : rtl_dump_test rtl_test (SELFTEST_LOCATION, locate_file ("cfg-test.rtl"));
5492 :
5493 4 : ASSERT_TRUE (sched_luids.is_empty ());
5494 4 : ASSERT_TRUE (h_d_i_d.is_empty ());
5495 4 : ASSERT_TRUE (reg_last_pool.is_empty ());
5496 4 : ASSERT_EQ (0, reg_last_pool_max_reg);
5497 4 : ASSERT_EQ (0, cache_size);
5498 4 : ASSERT_EQ (NULL, true_dependency_cache);
5499 4 : ASSERT_EQ (NULL, dn_pool);
5500 4 : ASSERT_EQ (NULL, dl_pool);
5501 :
5502 4 : rtx_insn *old_barrier
5503 4 : = make_insn_raw (gen_rtx_USE (VOIDmode, const0_rtx));
5504 4 : rtx_insn *setter = make_insn_raw (gen_rtx_USE (VOIDmode, const0_rtx));
5505 4 : start_sequence ();
5506 4 : rtx_insn *full_barrier
5507 4 : = emit_insn (gen_rtx_ASM_INPUT (VOIDmode, ""));
5508 4 : rtx_insn *sparse_old_barrier
5509 4 : = make_insn_raw (gen_rtx_USE (VOIDmode, const0_rtx));
5510 4 : rtx_insn *setter0 = make_insn_raw (gen_rtx_USE (VOIDmode, const0_rtx));
5511 4 : rtx_insn *setter2 = make_insn_raw (gen_rtx_USE (VOIDmode, const0_rtx));
5512 4 : rtx_insn *sparse_barrier
5513 4 : = emit_insn (gen_rtx_ASM_INPUT (VOIDmode, ""));
5514 4 : end_sequence ();
5515 4 : sched_luids.safe_grow_cleared (get_max_uid () + 1, true);
5516 :
5517 4 : bitmap_obstack test_obstack;
5518 4 : bitmap_obstack_initialize (&test_obstack);
5519 4 : bitmap_head pending_sets;
5520 4 : bitmap_head pending_clobbers;
5521 4 : bitmap_head pending_uses;
5522 4 : bitmap_head pending_control_uses;
5523 4 : bitmap_initialize (&pending_sets, &test_obstack);
5524 4 : bitmap_initialize (&pending_clobbers, &test_obstack);
5525 4 : bitmap_initialize (&pending_uses, &test_obstack);
5526 4 : bitmap_initialize (&pending_control_uses, &test_obstack);
5527 :
5528 4 : regset saved_pending_sets = reg_pending_sets;
5529 4 : regset saved_pending_clobbers = reg_pending_clobbers;
5530 4 : regset saved_pending_uses = reg_pending_uses;
5531 4 : regset saved_pending_control_uses = reg_pending_control_uses;
5532 4 : HARD_REG_SET saved_implicit_clobbers = implicit_reg_pending_clobbers;
5533 4 : HARD_REG_SET saved_implicit_uses = implicit_reg_pending_uses;
5534 4 : enum reg_pending_barrier_mode saved_pending_barrier = reg_pending_barrier;
5535 4 : sched_deps_info_def *saved_sched_deps_info = sched_deps_info;
5536 4 : haifa_sched_info *saved_current_sched_info = current_sched_info;
5537 4 : common_sched_info_def *saved_common_sched_info = common_sched_info;
5538 4 : int saved_reload_completed = reload_completed;
5539 4 : enum sched_pressure_algorithm saved_sched_pressure = sched_pressure;
5540 4 : bool saved_exposed_pipeline = targetm.sched.exposed_pipeline;
5541 :
5542 4 : reg_pending_sets = &pending_sets;
5543 4 : reg_pending_clobbers = &pending_clobbers;
5544 4 : reg_pending_uses = &pending_uses;
5545 4 : reg_pending_control_uses = &pending_control_uses;
5546 16 : CLEAR_HARD_REG_SET (implicit_reg_pending_clobbers);
5547 4 : CLEAR_HARD_REG_SET (implicit_reg_pending_uses);
5548 4 : reg_pending_barrier = NOT_A_BARRIER;
5549 :
5550 4 : sched_deps_info_def deps_info = {};
5551 4 : deps_info.note_dep = observe_barrier_dependence;
5552 4 : sched_deps_info = &deps_info;
5553 4 : haifa_sched_info sched_info = {};
5554 4 : current_sched_info = &sched_info;
5555 4 : common_sched_info_def common_info = haifa_common_sched_info;
5556 4 : common_sched_info = &common_info;
5557 4 : reload_completed = 0;
5558 4 : sched_pressure = SCHED_PRESSURE_NONE;
5559 4 : targetm.sched.exposed_pipeline = false;
5560 :
5561 4 : test_full_lazy_barrier (&test_obstack, full_barrier, old_barrier, setter);
5562 4 : test_sparse_lazy_barrier (&test_obstack, sparse_barrier,
5563 : sparse_old_barrier, setter0, setter2);
5564 4 : test_lazy_barrier_join (&test_obstack);
5565 :
5566 4 : ASSERT_TRUE (!observed_barrier_deps);
5567 4 : ASSERT_TRUE (deps_pools_are_empty_p ());
5568 4 : sched_deps_finish ();
5569 4 : sched_luids.release ();
5570 :
5571 4 : targetm.sched.exposed_pipeline = saved_exposed_pipeline;
5572 4 : sched_pressure = saved_sched_pressure;
5573 4 : reload_completed = saved_reload_completed;
5574 4 : common_sched_info = saved_common_sched_info;
5575 4 : current_sched_info = saved_current_sched_info;
5576 4 : sched_deps_info = saved_sched_deps_info;
5577 4 : reg_pending_barrier = saved_pending_barrier;
5578 4 : implicit_reg_pending_clobbers = saved_implicit_clobbers;
5579 4 : implicit_reg_pending_uses = saved_implicit_uses;
5580 4 : reg_pending_sets = saved_pending_sets;
5581 4 : reg_pending_clobbers = saved_pending_clobbers;
5582 4 : reg_pending_uses = saved_pending_uses;
5583 4 : reg_pending_control_uses = saved_pending_control_uses;
5584 4 : bitmap_obstack_release (&test_obstack);
5585 4 : }
5586 :
5587 : /* Run the sched-deps.cc selftests. */
5588 :
5589 : void
5590 4 : sched_deps_cc_tests ()
5591 : {
5592 4 : test_dirty_reg_last_release ();
5593 4 : test_reg_last_pool ();
5594 4 : test_lazy_barriers ();
5595 4 : }
5596 :
5597 : } // namespace selftest
5598 :
5599 : #endif
5600 :
5601 : #endif /* INSN_SCHEDULING */
5602 :
5603 : #if CHECKING_P && !defined (INSN_SCHEDULING)
5604 :
5605 : namespace selftest {
5606 :
5607 : void
5608 : sched_deps_cc_tests ()
5609 : {
5610 : }
5611 :
5612 : } // namespace selftest
5613 :
5614 : #endif
|
