1 /* Instruction scheduling pass. This file computes dependencies between
2 instructions.
3 Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998,
4 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006
5 Free Software Foundation, Inc.
6 Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,
7 and currently maintained by, Jim Wilson (wilson@cygnus.com)
8
9 This file is part of GCC.
10
11 GCC is free software; you can redistribute it and/or modify it under
12 the terms of the GNU General Public License as published by the Free
13 Software Foundation; either version 2, or (at your option) any later
14 version.
15
16 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
17 WARRANTY; without even the implied warranty of MERCHANTABILITY or
18 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
19 for more details.
20
21 You should have received a copy of the GNU General Public License
22 along with GCC; see the file COPYING. If not, write to the Free
23 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
24 02110-1301, USA. */
25
26 #include "config.h"
27 #include "system.h"
28 #include "coretypes.h"
29 #include "tm.h"
30 #include "toplev.h"
31 #include "rtl.h"
32 #include "tm_p.h"
33 #include "hard-reg-set.h"
34 #include "regs.h"
35 #include "function.h"
36 #include "flags.h"
37 #include "insn-config.h"
38 #include "insn-attr.h"
39 #include "except.h"
40 #include "toplev.h"
41 #include "recog.h"
42 #include "sched-int.h"
43 #include "params.h"
44 #include "cselib.h"
45 #include "df.h"
46
47
48 static regset reg_pending_sets;
49 static regset reg_pending_clobbers;
50 static regset reg_pending_uses;
51
52 /* The following enumeration values tell us what dependencies we
53 should use to implement the barrier. We use true-dependencies for
54 TRUE_BARRIER and anti-dependencies for MOVE_BARRIER. */
55 enum reg_pending_barrier_mode
56 {
57 NOT_A_BARRIER = 0,
58 MOVE_BARRIER,
59 TRUE_BARRIER
60 };
61
62 static enum reg_pending_barrier_mode reg_pending_barrier;
63
64 /* To speed up the test for duplicate dependency links we keep a
65 record of dependencies created by add_dependence when the average
66 number of instructions in a basic block is very large.
67
68 Studies have shown that there is typically around 5 instructions between
69 branches for typical C code. So we can make a guess that the average
70 basic block is approximately 5 instructions long; we will choose 100X
71 the average size as a very large basic block.
72
73 Each insn has associated bitmaps for its dependencies. Each bitmap
74 has enough entries to represent a dependency on any other insn in
75 the insn chain. All bitmap for true dependencies cache is
76 allocated then the rest two ones are also allocated. */
77 static bitmap_head *true_dependency_cache;
78 static bitmap_head *output_dependency_cache;
79 static bitmap_head *anti_dependency_cache;
80 static bitmap_head *spec_dependency_cache;
81 static int cache_size;
82
83 /* To speed up checking consistency of formed forward insn
84 dependencies we use the following cache. Another possible solution
85 could be switching off checking duplication of insns in forward
86 dependencies. */
87 #ifdef ENABLE_CHECKING
88 static bitmap_head *forward_dependency_cache;
89 #endif
90
91 static int deps_may_trap_p (rtx);
92 static void add_dependence_list (rtx, rtx, int, enum reg_note);
93 static void add_dependence_list_and_free (rtx, rtx *, int, enum reg_note);
94 static void delete_all_dependences (rtx);
95 static void fixup_sched_groups (rtx);
96
97 static void flush_pending_lists (struct deps *, rtx, int, int);
98 static void sched_analyze_1 (struct deps *, rtx, rtx);
99 static void sched_analyze_2 (struct deps *, rtx, rtx);
100 static void sched_analyze_insn (struct deps *, rtx, rtx);
101
102 static rtx sched_get_condition (rtx);
103 static int conditions_mutex_p (rtx, rtx);
104
105 static enum DEPS_ADJUST_RESULT maybe_add_or_update_back_dep_1 (rtx, rtx,
106 enum reg_note, ds_t, rtx, rtx, rtx **);
107 static enum DEPS_ADJUST_RESULT add_or_update_back_dep_1 (rtx, rtx,
108 enum reg_note, ds_t, rtx, rtx, rtx **);
109 static void add_back_dep (rtx, rtx, enum reg_note, ds_t);
110
111 static void adjust_add_sorted_back_dep (rtx, rtx, rtx *);
112 static void adjust_back_add_forw_dep (rtx, rtx *);
113 static void delete_forw_dep (rtx, rtx);
114 static dw_t estimate_dep_weak (rtx, rtx);
115 #ifdef INSN_SCHEDULING
116 #ifdef ENABLE_CHECKING
117 static void check_dep_status (enum reg_note, ds_t, bool);
118 #endif
119 #endif
120
121 /* Return nonzero if a load of the memory reference MEM can cause a trap. */
122
123 static int
deps_may_trap_p(rtx mem)124 deps_may_trap_p (rtx mem)
125 {
126 rtx addr = XEXP (mem, 0);
127
128 if (REG_P (addr) && REGNO (addr) >= FIRST_PSEUDO_REGISTER)
129 {
130 rtx t = get_reg_known_value (REGNO (addr));
131 if (t)
132 addr = t;
133 }
134 return rtx_addr_can_trap_p (addr);
135 }
136
137 /* Return the INSN_LIST containing INSN in LIST, or NULL
138 if LIST does not contain INSN. */
139
140 rtx
find_insn_list(rtx insn,rtx list)141 find_insn_list (rtx insn, rtx list)
142 {
143 while (list)
144 {
145 if (XEXP (list, 0) == insn)
146 return list;
147 list = XEXP (list, 1);
148 }
149 return 0;
150 }
151
152 /* Find the condition under which INSN is executed. */
153
154 static rtx
sched_get_condition(rtx insn)155 sched_get_condition (rtx insn)
156 {
157 rtx pat = PATTERN (insn);
158 rtx src;
159
160 if (pat == 0)
161 return 0;
162
163 if (GET_CODE (pat) == COND_EXEC)
164 return COND_EXEC_TEST (pat);
165
166 if (!any_condjump_p (insn) || !onlyjump_p (insn))
167 return 0;
168
169 src = SET_SRC (pc_set (insn));
170
171 if (XEXP (src, 2) == pc_rtx)
172 return XEXP (src, 0);
173 else if (XEXP (src, 1) == pc_rtx)
174 {
175 rtx cond = XEXP (src, 0);
176 enum rtx_code revcode = reversed_comparison_code (cond, insn);
177
178 if (revcode == UNKNOWN)
179 return 0;
180 return gen_rtx_fmt_ee (revcode, GET_MODE (cond), XEXP (cond, 0),
181 XEXP (cond, 1));
182 }
183
184 return 0;
185 }
186
187
188 /* Return nonzero if conditions COND1 and COND2 can never be both true. */
189
190 static int
conditions_mutex_p(rtx cond1,rtx cond2)191 conditions_mutex_p (rtx cond1, rtx cond2)
192 {
193 if (COMPARISON_P (cond1)
194 && COMPARISON_P (cond2)
195 && GET_CODE (cond1) == reversed_comparison_code (cond2, NULL)
196 && XEXP (cond1, 0) == XEXP (cond2, 0)
197 && XEXP (cond1, 1) == XEXP (cond2, 1))
198 return 1;
199 return 0;
200 }
201
202 /* Return true if insn1 and insn2 can never depend on one another because
203 the conditions under which they are executed are mutually exclusive. */
204 bool
sched_insns_conditions_mutex_p(rtx insn1,rtx insn2)205 sched_insns_conditions_mutex_p (rtx insn1, rtx insn2)
206 {
207 rtx cond1, cond2;
208
209 /* flow.c doesn't handle conditional lifetimes entirely correctly;
210 calls mess up the conditional lifetimes. */
211 if (!CALL_P (insn1) && !CALL_P (insn2))
212 {
213 cond1 = sched_get_condition (insn1);
214 cond2 = sched_get_condition (insn2);
215 if (cond1 && cond2
216 && conditions_mutex_p (cond1, cond2)
217 /* Make sure first instruction doesn't affect condition of second
218 instruction if switched. */
219 && !modified_in_p (cond1, insn2)
220 /* Make sure second instruction doesn't affect condition of first
221 instruction if switched. */
222 && !modified_in_p (cond2, insn1))
223 return true;
224 }
225 return false;
226 }
227
228 /* Add ELEM wrapped in an INSN_LIST with reg note kind DEP_TYPE to the
229 LOG_LINKS of INSN, if it is not already there. DEP_TYPE indicates the
230 type of dependence that this link represents. DS, if nonzero,
231 indicates speculations, through which this dependence can be overcome.
232 MEM1 and MEM2, if non-null, corresponds to memory locations in case of
233 data speculation. The function returns a value indicating if an old entry
234 has been changed or a new entry has been added to insn's LOG_LINK.
235 In case of changed entry CHANGED_LINKPP sets to its address.
236 See also the definition of enum DEPS_ADJUST_RESULT in sched-int.h.
237 Actual manipulation of dependence data structures is performed in
238 add_or_update_back_dep_1. */
239
240 static enum DEPS_ADJUST_RESULT
maybe_add_or_update_back_dep_1(rtx insn,rtx elem,enum reg_note dep_type,ds_t ds,rtx mem1,rtx mem2,rtx ** changed_linkpp)241 maybe_add_or_update_back_dep_1 (rtx insn, rtx elem, enum reg_note dep_type,
242 ds_t ds, rtx mem1, rtx mem2,
243 rtx **changed_linkpp)
244 {
245 gcc_assert (INSN_P (insn) && INSN_P (elem));
246
247 /* Don't depend an insn on itself. */
248 if (insn == elem)
249 {
250 #ifdef INSN_SCHEDULING
251 if (current_sched_info->flags & DO_SPECULATION)
252 /* INSN has an internal dependence, which we can't overcome. */
253 HAS_INTERNAL_DEP (insn) = 1;
254 #endif
255 return 0;
256 }
257
258 return add_or_update_back_dep_1 (insn, elem, dep_type,
259 ds, mem1, mem2, changed_linkpp);
260 }
261
262 /* This function has the same meaning of parameters and return values
263 as maybe_add_or_update_back_dep_1. The only difference between these
264 two functions is that INSN and ELEM are guaranteed not to be the same
265 in this one. */
266 static enum DEPS_ADJUST_RESULT
add_or_update_back_dep_1(rtx insn,rtx elem,enum reg_note dep_type,ds_t ds ATTRIBUTE_UNUSED,rtx mem1 ATTRIBUTE_UNUSED,rtx mem2 ATTRIBUTE_UNUSED,rtx ** changed_linkpp ATTRIBUTE_UNUSED)267 add_or_update_back_dep_1 (rtx insn, rtx elem, enum reg_note dep_type,
268 ds_t ds ATTRIBUTE_UNUSED,
269 rtx mem1 ATTRIBUTE_UNUSED, rtx mem2 ATTRIBUTE_UNUSED,
270 rtx **changed_linkpp ATTRIBUTE_UNUSED)
271 {
272 bool maybe_present_p = true, present_p = false;
273
274 gcc_assert (INSN_P (insn) && INSN_P (elem) && insn != elem);
275
276 #ifdef INSN_SCHEDULING
277
278 #ifdef ENABLE_CHECKING
279 check_dep_status (dep_type, ds, mem1 != NULL);
280 #endif
281
282 /* If we already have a dependency for ELEM, then we do not need to
283 do anything. Avoiding the list walk below can cut compile times
284 dramatically for some code. */
285 if (true_dependency_cache != NULL)
286 {
287 enum reg_note present_dep_type;
288
289 gcc_assert (output_dependency_cache);
290 gcc_assert (anti_dependency_cache);
291 if (!(current_sched_info->flags & USE_DEPS_LIST))
292 {
293 if (bitmap_bit_p (&true_dependency_cache[INSN_LUID (insn)],
294 INSN_LUID (elem)))
295 present_dep_type = REG_DEP_TRUE;
296 else if (bitmap_bit_p (&output_dependency_cache[INSN_LUID (insn)],
297 INSN_LUID (elem)))
298 present_dep_type = REG_DEP_OUTPUT;
299 else if (bitmap_bit_p (&anti_dependency_cache[INSN_LUID (insn)],
300 INSN_LUID (elem)))
301 present_dep_type = REG_DEP_ANTI;
302 else
303 maybe_present_p = false;
304
305 if (maybe_present_p)
306 {
307 if ((int) dep_type >= (int) present_dep_type)
308 return DEP_PRESENT;
309
310 present_p = true;
311 }
312 }
313 else
314 {
315 ds_t present_dep_types = 0;
316
317 if (bitmap_bit_p (&true_dependency_cache[INSN_LUID (insn)],
318 INSN_LUID (elem)))
319 present_dep_types |= DEP_TRUE;
320 if (bitmap_bit_p (&output_dependency_cache[INSN_LUID (insn)],
321 INSN_LUID (elem)))
322 present_dep_types |= DEP_OUTPUT;
323 if (bitmap_bit_p (&anti_dependency_cache[INSN_LUID (insn)],
324 INSN_LUID (elem)))
325 present_dep_types |= DEP_ANTI;
326
327 if (present_dep_types)
328 {
329 if (!(current_sched_info->flags & DO_SPECULATION)
330 || !bitmap_bit_p (&spec_dependency_cache[INSN_LUID (insn)],
331 INSN_LUID (elem)))
332 {
333 if ((present_dep_types | (ds & DEP_TYPES))
334 == present_dep_types)
335 /* We already have all these bits. */
336 return DEP_PRESENT;
337 }
338 else
339 {
340 /* Only true dependencies can be data speculative and
341 only anti dependencies can be control speculative. */
342 gcc_assert ((present_dep_types & (DEP_TRUE | DEP_ANTI))
343 == present_dep_types);
344
345 /* if (additional dep is SPECULATIVE) then
346 we should update DEP_STATUS
347 else
348 we should reset existing dep to non-speculative. */
349 }
350
351 present_p = true;
352 }
353 else
354 maybe_present_p = false;
355 }
356 }
357 #endif
358
359 /* Check that we don't already have this dependence. */
360 if (maybe_present_p)
361 {
362 rtx *linkp;
363
364 for (linkp = &LOG_LINKS (insn); *linkp; linkp = &XEXP (*linkp, 1))
365 {
366 rtx link = *linkp;
367
368 gcc_assert (true_dependency_cache == 0 || present_p);
369
370 if (XEXP (link, 0) == elem)
371 {
372 enum DEPS_ADJUST_RESULT changed_p = DEP_PRESENT;
373
374 #ifdef INSN_SCHEDULING
375 if (current_sched_info->flags & USE_DEPS_LIST)
376 {
377 ds_t new_status = ds | DEP_STATUS (link);
378
379 if (new_status & SPECULATIVE)
380 {
381 if (!(ds & SPECULATIVE)
382 || !(DEP_STATUS (link) & SPECULATIVE))
383 /* Then this dep can't be speculative. */
384 {
385 new_status &= ~SPECULATIVE;
386 if (true_dependency_cache
387 && (DEP_STATUS (link) & SPECULATIVE))
388 bitmap_clear_bit (&spec_dependency_cache
389 [INSN_LUID (insn)],
390 INSN_LUID (elem));
391 }
392 else
393 {
394 /* Both are speculative. Merging probabilities. */
395 if (mem1)
396 {
397 dw_t dw;
398
399 dw = estimate_dep_weak (mem1, mem2);
400 ds = set_dep_weak (ds, BEGIN_DATA, dw);
401 }
402
403 new_status = ds_merge (DEP_STATUS (link), ds);
404 }
405 }
406
407 ds = new_status;
408 }
409
410 /* Clear corresponding cache entry because type of the link
411 may have changed. Keep them if we use_deps_list. */
412 if (true_dependency_cache != NULL
413 && !(current_sched_info->flags & USE_DEPS_LIST))
414 {
415 enum reg_note kind = REG_NOTE_KIND (link);
416
417 switch (kind)
418 {
419 case REG_DEP_OUTPUT:
420 bitmap_clear_bit (&output_dependency_cache
421 [INSN_LUID (insn)], INSN_LUID (elem));
422 break;
423 case REG_DEP_ANTI:
424 bitmap_clear_bit (&anti_dependency_cache
425 [INSN_LUID (insn)], INSN_LUID (elem));
426 break;
427 default:
428 gcc_unreachable ();
429 }
430 }
431
432 if ((current_sched_info->flags & USE_DEPS_LIST)
433 && DEP_STATUS (link) != ds)
434 {
435 DEP_STATUS (link) = ds;
436 changed_p = DEP_CHANGED;
437 }
438 #endif
439
440 /* If this is a more restrictive type of dependence than the
441 existing one, then change the existing dependence to this
442 type. */
443 if ((int) dep_type < (int) REG_NOTE_KIND (link))
444 {
445 PUT_REG_NOTE_KIND (link, dep_type);
446 changed_p = DEP_CHANGED;
447 }
448
449 #ifdef INSN_SCHEDULING
450 /* If we are adding a dependency to INSN's LOG_LINKs, then
451 note that in the bitmap caches of dependency information. */
452 if (true_dependency_cache != NULL)
453 {
454 if (!(current_sched_info->flags & USE_DEPS_LIST))
455 {
456 if (REG_NOTE_KIND (link) == REG_DEP_TRUE)
457 bitmap_set_bit (&true_dependency_cache
458 [INSN_LUID (insn)], INSN_LUID (elem));
459 else if (REG_NOTE_KIND (link) == REG_DEP_OUTPUT)
460 bitmap_set_bit (&output_dependency_cache
461 [INSN_LUID (insn)], INSN_LUID (elem));
462 else if (REG_NOTE_KIND (link) == REG_DEP_ANTI)
463 bitmap_set_bit (&anti_dependency_cache
464 [INSN_LUID (insn)], INSN_LUID (elem));
465 }
466 else
467 {
468 if (ds & DEP_TRUE)
469 bitmap_set_bit (&true_dependency_cache
470 [INSN_LUID (insn)], INSN_LUID (elem));
471 if (ds & DEP_OUTPUT)
472 bitmap_set_bit (&output_dependency_cache
473 [INSN_LUID (insn)], INSN_LUID (elem));
474 if (ds & DEP_ANTI)
475 bitmap_set_bit (&anti_dependency_cache
476 [INSN_LUID (insn)], INSN_LUID (elem));
477 /* Note, that dep can become speculative only
478 at the moment of creation. Thus, we don't need to
479 check for it here. */
480 }
481 }
482
483 if (changed_linkpp && changed_p == DEP_CHANGED)
484 *changed_linkpp = linkp;
485 #endif
486 return changed_p;
487 }
488 }
489 /* We didn't find a dep. It shouldn't be present in the cache. */
490 gcc_assert (!present_p);
491 }
492
493 /* Might want to check one level of transitivity to save conses.
494 This check should be done in maybe_add_or_update_back_dep_1.
495 Since we made it to add_or_update_back_dep_1, we must create
496 (or update) a link. */
497
498 if (mem1)
499 {
500 gcc_assert (current_sched_info->flags & DO_SPECULATION);
501 ds = set_dep_weak (ds, BEGIN_DATA, estimate_dep_weak (mem1, mem2));
502 }
503
504 add_back_dep (insn, elem, dep_type, ds);
505
506 return DEP_CREATED;
507 }
508
509 /* This function creates a link between INSN and ELEM under any
510 conditions. DS describes speculative status of the link. */
511 static void
add_back_dep(rtx insn,rtx elem,enum reg_note dep_type,ds_t ds)512 add_back_dep (rtx insn, rtx elem, enum reg_note dep_type, ds_t ds)
513 {
514 gcc_assert (INSN_P (insn) && INSN_P (elem) && insn != elem);
515
516 if (current_sched_info->flags & USE_DEPS_LIST)
517 LOG_LINKS (insn) = alloc_DEPS_LIST (elem, LOG_LINKS (insn), ds);
518 else
519 LOG_LINKS (insn) = alloc_INSN_LIST (elem, LOG_LINKS (insn));
520
521 /* Insn dependency, not data dependency. */
522 PUT_REG_NOTE_KIND (LOG_LINKS (insn), dep_type);
523
524 #ifdef INSN_SCHEDULING
525 #ifdef ENABLE_CHECKING
526 check_dep_status (dep_type, ds, false);
527 #endif
528
529 /* If we are adding a dependency to INSN's LOG_LINKs, then note that
530 in the bitmap caches of dependency information. */
531 if (true_dependency_cache != NULL)
532 {
533 if (!(current_sched_info->flags & USE_DEPS_LIST))
534 {
535 if (dep_type == REG_DEP_TRUE)
536 bitmap_set_bit (&true_dependency_cache[INSN_LUID (insn)],
537 INSN_LUID (elem));
538 else if (dep_type == REG_DEP_OUTPUT)
539 bitmap_set_bit (&output_dependency_cache[INSN_LUID (insn)],
540 INSN_LUID (elem));
541 else if (dep_type == REG_DEP_ANTI)
542 bitmap_set_bit (&anti_dependency_cache[INSN_LUID (insn)],
543 INSN_LUID (elem));
544 }
545 else
546 {
547 if (ds & DEP_TRUE)
548 bitmap_set_bit (&true_dependency_cache[INSN_LUID (insn)],
549 INSN_LUID (elem));
550 if (ds & DEP_OUTPUT)
551 bitmap_set_bit (&output_dependency_cache[INSN_LUID (insn)],
552 INSN_LUID (elem));
553 if (ds & DEP_ANTI)
554 bitmap_set_bit (&anti_dependency_cache[INSN_LUID (insn)],
555 INSN_LUID (elem));
556 if (ds & SPECULATIVE)
557 {
558 gcc_assert (current_sched_info->flags & DO_SPECULATION);
559 bitmap_set_bit (&spec_dependency_cache[INSN_LUID (insn)],
560 INSN_LUID (elem));
561 }
562 }
563 }
564 #endif
565 }
566
567 /* A convenience wrapper to operate on an entire list. */
568
569 static void
add_dependence_list(rtx insn,rtx list,int uncond,enum reg_note dep_type)570 add_dependence_list (rtx insn, rtx list, int uncond, enum reg_note dep_type)
571 {
572 for (; list; list = XEXP (list, 1))
573 {
574 if (uncond || ! sched_insns_conditions_mutex_p (insn, XEXP (list, 0)))
575 add_dependence (insn, XEXP (list, 0), dep_type);
576 }
577 }
578
579 /* Similar, but free *LISTP at the same time. */
580
581 static void
add_dependence_list_and_free(rtx insn,rtx * listp,int uncond,enum reg_note dep_type)582 add_dependence_list_and_free (rtx insn, rtx *listp, int uncond,
583 enum reg_note dep_type)
584 {
585 rtx list, next;
586 for (list = *listp, *listp = NULL; list ; list = next)
587 {
588 next = XEXP (list, 1);
589 if (uncond || ! sched_insns_conditions_mutex_p (insn, XEXP (list, 0)))
590 add_dependence (insn, XEXP (list, 0), dep_type);
591 free_INSN_LIST_node (list);
592 }
593 }
594
595 /* Clear all dependencies for an insn. */
596
597 static void
delete_all_dependences(rtx insn)598 delete_all_dependences (rtx insn)
599 {
600 /* Clear caches, if they exist, as well as free the dependence. */
601
602 #ifdef INSN_SCHEDULING
603 if (true_dependency_cache != NULL)
604 {
605 bitmap_clear (&true_dependency_cache[INSN_LUID (insn)]);
606 bitmap_clear (&output_dependency_cache[INSN_LUID (insn)]);
607 bitmap_clear (&anti_dependency_cache[INSN_LUID (insn)]);
608 /* We don't have to clear forward_dependency_cache here,
609 because it is formed later. */
610 if (current_sched_info->flags & DO_SPECULATION)
611 bitmap_clear (&spec_dependency_cache[INSN_LUID (insn)]);
612 }
613 #endif
614
615 if (!(current_sched_info->flags & USE_DEPS_LIST))
616 /* In this case LOG_LINKS are formed from the DEPS_LISTs,
617 not the INSN_LISTs. */
618 free_INSN_LIST_list (&LOG_LINKS (insn));
619 else
620 free_DEPS_LIST_list (&LOG_LINKS (insn));
621 }
622
623 /* All insns in a scheduling group except the first should only have
624 dependencies on the previous insn in the group. So we find the
625 first instruction in the scheduling group by walking the dependence
626 chains backwards. Then we add the dependencies for the group to
627 the previous nonnote insn. */
628
629 static void
fixup_sched_groups(rtx insn)630 fixup_sched_groups (rtx insn)
631 {
632 rtx link, prev_nonnote;
633
634 for (link = LOG_LINKS (insn); link ; link = XEXP (link, 1))
635 {
636 rtx i = insn;
637 do
638 {
639 i = prev_nonnote_insn (i);
640
641 if (XEXP (link, 0) == i)
642 goto next_link;
643 } while (SCHED_GROUP_P (i));
644 if (! sched_insns_conditions_mutex_p (i, XEXP (link, 0)))
645 add_dependence (i, XEXP (link, 0), REG_NOTE_KIND (link));
646 next_link:;
647 }
648
649 delete_all_dependences (insn);
650
651 prev_nonnote = prev_nonnote_insn (insn);
652 if (BLOCK_FOR_INSN (insn) == BLOCK_FOR_INSN (prev_nonnote)
653 && ! sched_insns_conditions_mutex_p (insn, prev_nonnote))
654 add_dependence (insn, prev_nonnote, REG_DEP_ANTI);
655 }
656
657 /* Process an insn's memory dependencies. There are four kinds of
658 dependencies:
659
660 (0) read dependence: read follows read
661 (1) true dependence: read follows write
662 (2) output dependence: write follows write
663 (3) anti dependence: write follows read
664
665 We are careful to build only dependencies which actually exist, and
666 use transitivity to avoid building too many links. */
667
668 /* Add an INSN and MEM reference pair to a pending INSN_LIST and MEM_LIST.
669 The MEM is a memory reference contained within INSN, which we are saving
670 so that we can do memory aliasing on it. */
671
672 static void
add_insn_mem_dependence(struct deps * deps,rtx * insn_list,rtx * mem_list,rtx insn,rtx mem)673 add_insn_mem_dependence (struct deps *deps, rtx *insn_list, rtx *mem_list,
674 rtx insn, rtx mem)
675 {
676 rtx link;
677
678 link = alloc_INSN_LIST (insn, *insn_list);
679 *insn_list = link;
680
681 if (current_sched_info->use_cselib)
682 {
683 mem = shallow_copy_rtx (mem);
684 XEXP (mem, 0) = cselib_subst_to_values (XEXP (mem, 0));
685 }
686 link = alloc_EXPR_LIST (VOIDmode, canon_rtx (mem), *mem_list);
687 *mem_list = link;
688
689 deps->pending_lists_length++;
690 }
691
692 /* Make a dependency between every memory reference on the pending lists
693 and INSN, thus flushing the pending lists. FOR_READ is true if emitting
694 dependencies for a read operation, similarly with FOR_WRITE. */
695
696 static void
flush_pending_lists(struct deps * deps,rtx insn,int for_read,int for_write)697 flush_pending_lists (struct deps *deps, rtx insn, int for_read,
698 int for_write)
699 {
700 if (for_write)
701 {
702 add_dependence_list_and_free (insn, &deps->pending_read_insns, 1,
703 REG_DEP_ANTI);
704 free_EXPR_LIST_list (&deps->pending_read_mems);
705 }
706
707 add_dependence_list_and_free (insn, &deps->pending_write_insns, 1,
708 for_read ? REG_DEP_ANTI : REG_DEP_OUTPUT);
709 free_EXPR_LIST_list (&deps->pending_write_mems);
710 deps->pending_lists_length = 0;
711
712 add_dependence_list_and_free (insn, &deps->last_pending_memory_flush, 1,
713 for_read ? REG_DEP_ANTI : REG_DEP_OUTPUT);
714 deps->last_pending_memory_flush = alloc_INSN_LIST (insn, NULL_RTX);
715 deps->pending_flush_length = 1;
716 }
717
718 /* Analyze a single reference to register (reg:MODE REGNO) in INSN.
719 The type of the reference is specified by REF and can be SET,
720 CLOBBER, PRE_DEC, POST_DEC, PRE_INC, POST_INC or USE. */
721
722 static void
sched_analyze_reg(struct deps * deps,int regno,enum machine_mode mode,enum rtx_code ref,rtx insn)723 sched_analyze_reg (struct deps *deps, int regno, enum machine_mode mode,
724 enum rtx_code ref, rtx insn)
725 {
726 /* A hard reg in a wide mode may really be multiple registers.
727 If so, mark all of them just like the first. */
728 if (regno < FIRST_PSEUDO_REGISTER)
729 {
730 int i = hard_regno_nregs[regno][mode];
731 if (ref == SET)
732 {
733 while (--i >= 0)
734 SET_REGNO_REG_SET (reg_pending_sets, regno + i);
735 }
736 else if (ref == USE)
737 {
738 while (--i >= 0)
739 SET_REGNO_REG_SET (reg_pending_uses, regno + i);
740 }
741 else
742 {
743 while (--i >= 0)
744 SET_REGNO_REG_SET (reg_pending_clobbers, regno + i);
745 }
746 }
747
748 /* ??? Reload sometimes emits USEs and CLOBBERs of pseudos that
749 it does not reload. Ignore these as they have served their
750 purpose already. */
751 else if (regno >= deps->max_reg)
752 {
753 enum rtx_code code = GET_CODE (PATTERN (insn));
754 gcc_assert (code == USE || code == CLOBBER);
755 }
756
757 else
758 {
759 if (ref == SET)
760 SET_REGNO_REG_SET (reg_pending_sets, regno);
761 else if (ref == USE)
762 SET_REGNO_REG_SET (reg_pending_uses, regno);
763 else
764 SET_REGNO_REG_SET (reg_pending_clobbers, regno);
765
766 /* Pseudos that are REG_EQUIV to something may be replaced
767 by that during reloading. We need only add dependencies for
768 the address in the REG_EQUIV note. */
769 if (!reload_completed && get_reg_known_equiv_p (regno))
770 {
771 rtx t = get_reg_known_value (regno);
772 if (MEM_P (t))
773 sched_analyze_2 (deps, XEXP (t, 0), insn);
774 }
775
776 /* Don't let it cross a call after scheduling if it doesn't
777 already cross one. */
778 if (REG_N_CALLS_CROSSED (regno) == 0)
779 {
780 if (ref == USE)
781 deps->sched_before_next_call
782 = alloc_INSN_LIST (insn, deps->sched_before_next_call);
783 else
784 add_dependence_list (insn, deps->last_function_call, 1,
785 REG_DEP_ANTI);
786 }
787 }
788 }
789
790 /* Analyze a single SET, CLOBBER, PRE_DEC, POST_DEC, PRE_INC or POST_INC
791 rtx, X, creating all dependencies generated by the write to the
792 destination of X, and reads of everything mentioned. */
793
794 static void
sched_analyze_1(struct deps * deps,rtx x,rtx insn)795 sched_analyze_1 (struct deps *deps, rtx x, rtx insn)
796 {
797 rtx dest = XEXP (x, 0);
798 enum rtx_code code = GET_CODE (x);
799
800 if (dest == 0)
801 return;
802
803 if (GET_CODE (dest) == PARALLEL)
804 {
805 int i;
806
807 for (i = XVECLEN (dest, 0) - 1; i >= 0; i--)
808 if (XEXP (XVECEXP (dest, 0, i), 0) != 0)
809 sched_analyze_1 (deps,
810 gen_rtx_CLOBBER (VOIDmode,
811 XEXP (XVECEXP (dest, 0, i), 0)),
812 insn);
813
814 if (GET_CODE (x) == SET)
815 sched_analyze_2 (deps, SET_SRC (x), insn);
816 return;
817 }
818
819 while (GET_CODE (dest) == STRICT_LOW_PART || GET_CODE (dest) == SUBREG
820 || GET_CODE (dest) == ZERO_EXTRACT)
821 {
822 if (GET_CODE (dest) == STRICT_LOW_PART
823 || GET_CODE (dest) == ZERO_EXTRACT
824 || df_read_modify_subreg_p (dest))
825 {
826 /* These both read and modify the result. We must handle
827 them as writes to get proper dependencies for following
828 instructions. We must handle them as reads to get proper
829 dependencies from this to previous instructions.
830 Thus we need to call sched_analyze_2. */
831
832 sched_analyze_2 (deps, XEXP (dest, 0), insn);
833 }
834 if (GET_CODE (dest) == ZERO_EXTRACT)
835 {
836 /* The second and third arguments are values read by this insn. */
837 sched_analyze_2 (deps, XEXP (dest, 1), insn);
838 sched_analyze_2 (deps, XEXP (dest, 2), insn);
839 }
840 dest = XEXP (dest, 0);
841 }
842
843 if (REG_P (dest))
844 {
845 int regno = REGNO (dest);
846 enum machine_mode mode = GET_MODE (dest);
847
848 sched_analyze_reg (deps, regno, mode, code, insn);
849
850 #ifdef STACK_REGS
851 /* Treat all writes to a stack register as modifying the TOS. */
852 if (regno >= FIRST_STACK_REG && regno <= LAST_STACK_REG)
853 {
854 /* Avoid analyzing the same register twice. */
855 if (regno != FIRST_STACK_REG)
856 sched_analyze_reg (deps, FIRST_STACK_REG, mode, code, insn);
857 sched_analyze_reg (deps, FIRST_STACK_REG, mode, USE, insn);
858 }
859 #endif
860 }
861 else if (MEM_P (dest))
862 {
863 /* Writing memory. */
864 rtx t = dest;
865
866 if (current_sched_info->use_cselib)
867 {
868 t = shallow_copy_rtx (dest);
869 cselib_lookup (XEXP (t, 0), Pmode, 1);
870 XEXP (t, 0) = cselib_subst_to_values (XEXP (t, 0));
871 }
872 t = canon_rtx (t);
873
874 if (deps->pending_lists_length > MAX_PENDING_LIST_LENGTH)
875 {
876 /* Flush all pending reads and writes to prevent the pending lists
877 from getting any larger. Insn scheduling runs too slowly when
878 these lists get long. When compiling GCC with itself,
879 this flush occurs 8 times for sparc, and 10 times for m88k using
880 the default value of 32. */
881 flush_pending_lists (deps, insn, false, true);
882 }
883 else
884 {
885 rtx pending, pending_mem;
886
887 pending = deps->pending_read_insns;
888 pending_mem = deps->pending_read_mems;
889 while (pending)
890 {
891 if (anti_dependence (XEXP (pending_mem, 0), t)
892 && ! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
893 add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI);
894
895 pending = XEXP (pending, 1);
896 pending_mem = XEXP (pending_mem, 1);
897 }
898
899 pending = deps->pending_write_insns;
900 pending_mem = deps->pending_write_mems;
901 while (pending)
902 {
903 if (output_dependence (XEXP (pending_mem, 0), t)
904 && ! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
905 add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT);
906
907 pending = XEXP (pending, 1);
908 pending_mem = XEXP (pending_mem, 1);
909 }
910
911 add_dependence_list (insn, deps->last_pending_memory_flush, 1,
912 REG_DEP_ANTI);
913
914 add_insn_mem_dependence (deps, &deps->pending_write_insns,
915 &deps->pending_write_mems, insn, dest);
916 }
917 sched_analyze_2 (deps, XEXP (dest, 0), insn);
918 }
919
920 /* Analyze reads. */
921 if (GET_CODE (x) == SET)
922 sched_analyze_2 (deps, SET_SRC (x), insn);
923 }
924
925 /* Analyze the uses of memory and registers in rtx X in INSN. */
926
927 static void
sched_analyze_2(struct deps * deps,rtx x,rtx insn)928 sched_analyze_2 (struct deps *deps, rtx x, rtx insn)
929 {
930 int i;
931 int j;
932 enum rtx_code code;
933 const char *fmt;
934
935 if (x == 0)
936 return;
937
938 code = GET_CODE (x);
939
940 switch (code)
941 {
942 case CONST_INT:
943 case CONST_DOUBLE:
944 case CONST_VECTOR:
945 case SYMBOL_REF:
946 case CONST:
947 case LABEL_REF:
948 /* Ignore constants. Note that we must handle CONST_DOUBLE here
949 because it may have a cc0_rtx in its CONST_DOUBLE_CHAIN field, but
950 this does not mean that this insn is using cc0. */
951 return;
952
953 #ifdef HAVE_cc0
954 case CC0:
955 /* User of CC0 depends on immediately preceding insn. */
956 SCHED_GROUP_P (insn) = 1;
957 /* Don't move CC0 setter to another block (it can set up the
958 same flag for previous CC0 users which is safe). */
959 CANT_MOVE (prev_nonnote_insn (insn)) = 1;
960 return;
961 #endif
962
963 case REG:
964 {
965 int regno = REGNO (x);
966 enum machine_mode mode = GET_MODE (x);
967
968 sched_analyze_reg (deps, regno, mode, USE, insn);
969
970 #ifdef STACK_REGS
971 /* Treat all reads of a stack register as modifying the TOS. */
972 if (regno >= FIRST_STACK_REG && regno <= LAST_STACK_REG)
973 {
974 /* Avoid analyzing the same register twice. */
975 if (regno != FIRST_STACK_REG)
976 sched_analyze_reg (deps, FIRST_STACK_REG, mode, USE, insn);
977 sched_analyze_reg (deps, FIRST_STACK_REG, mode, SET, insn);
978 }
979 #endif
980 return;
981 }
982
983 case MEM:
984 {
985 /* Reading memory. */
986 rtx u;
987 rtx pending, pending_mem;
988 rtx t = x;
989
990 if (current_sched_info->use_cselib)
991 {
992 t = shallow_copy_rtx (t);
993 cselib_lookup (XEXP (t, 0), Pmode, 1);
994 XEXP (t, 0) = cselib_subst_to_values (XEXP (t, 0));
995 }
996 t = canon_rtx (t);
997 pending = deps->pending_read_insns;
998 pending_mem = deps->pending_read_mems;
999 while (pending)
1000 {
1001 if (read_dependence (XEXP (pending_mem, 0), t)
1002 && ! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
1003 add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI);
1004
1005 pending = XEXP (pending, 1);
1006 pending_mem = XEXP (pending_mem, 1);
1007 }
1008
1009 pending = deps->pending_write_insns;
1010 pending_mem = deps->pending_write_mems;
1011 while (pending)
1012 {
1013 if (true_dependence (XEXP (pending_mem, 0), VOIDmode,
1014 t, rtx_varies_p)
1015 && ! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
1016 {
1017 if (current_sched_info->flags & DO_SPECULATION)
1018 maybe_add_or_update_back_dep_1 (insn, XEXP (pending, 0),
1019 REG_DEP_TRUE,
1020 BEGIN_DATA | DEP_TRUE,
1021 XEXP (pending_mem, 0), t, 0);
1022 else
1023 add_dependence (insn, XEXP (pending, 0), REG_DEP_TRUE);
1024 }
1025
1026 pending = XEXP (pending, 1);
1027 pending_mem = XEXP (pending_mem, 1);
1028 }
1029
1030 for (u = deps->last_pending_memory_flush; u; u = XEXP (u, 1))
1031 if (! JUMP_P (XEXP (u, 0)) || deps_may_trap_p (x))
1032 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
1033
1034 /* Always add these dependencies to pending_reads, since
1035 this insn may be followed by a write. */
1036 add_insn_mem_dependence (deps, &deps->pending_read_insns,
1037 &deps->pending_read_mems, insn, x);
1038
1039 /* Take advantage of tail recursion here. */
1040 sched_analyze_2 (deps, XEXP (x, 0), insn);
1041 return;
1042 }
1043
1044 /* Force pending stores to memory in case a trap handler needs them. */
1045 case TRAP_IF:
1046 flush_pending_lists (deps, insn, true, false);
1047 break;
1048
1049 case ASM_OPERANDS:
1050 case ASM_INPUT:
1051 case UNSPEC_VOLATILE:
1052 {
1053 /* Traditional and volatile asm instructions must be considered to use
1054 and clobber all hard registers, all pseudo-registers and all of
1055 memory. So must TRAP_IF and UNSPEC_VOLATILE operations.
1056
1057 Consider for instance a volatile asm that changes the fpu rounding
1058 mode. An insn should not be moved across this even if it only uses
1059 pseudo-regs because it might give an incorrectly rounded result. */
1060 if (code != ASM_OPERANDS || MEM_VOLATILE_P (x))
1061 reg_pending_barrier = TRUE_BARRIER;
1062
1063 /* For all ASM_OPERANDS, we must traverse the vector of input operands.
1064 We can not just fall through here since then we would be confused
1065 by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
1066 traditional asms unlike their normal usage. */
1067
1068 if (code == ASM_OPERANDS)
1069 {
1070 for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++)
1071 sched_analyze_2 (deps, ASM_OPERANDS_INPUT (x, j), insn);
1072 return;
1073 }
1074 break;
1075 }
1076
1077 case PRE_DEC:
1078 case POST_DEC:
1079 case PRE_INC:
1080 case POST_INC:
1081 /* These both read and modify the result. We must handle them as writes
1082 to get proper dependencies for following instructions. We must handle
1083 them as reads to get proper dependencies from this to previous
1084 instructions. Thus we need to pass them to both sched_analyze_1
1085 and sched_analyze_2. We must call sched_analyze_2 first in order
1086 to get the proper antecedent for the read. */
1087 sched_analyze_2 (deps, XEXP (x, 0), insn);
1088 sched_analyze_1 (deps, x, insn);
1089 return;
1090
1091 case POST_MODIFY:
1092 case PRE_MODIFY:
1093 /* op0 = op0 + op1 */
1094 sched_analyze_2 (deps, XEXP (x, 0), insn);
1095 sched_analyze_2 (deps, XEXP (x, 1), insn);
1096 sched_analyze_1 (deps, x, insn);
1097 return;
1098
1099 default:
1100 break;
1101 }
1102
1103 /* Other cases: walk the insn. */
1104 fmt = GET_RTX_FORMAT (code);
1105 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1106 {
1107 if (fmt[i] == 'e')
1108 sched_analyze_2 (deps, XEXP (x, i), insn);
1109 else if (fmt[i] == 'E')
1110 for (j = 0; j < XVECLEN (x, i); j++)
1111 sched_analyze_2 (deps, XVECEXP (x, i, j), insn);
1112 }
1113 }
1114
1115 /* Analyze an INSN with pattern X to find all dependencies. */
1116
1117 static void
sched_analyze_insn(struct deps * deps,rtx x,rtx insn)1118 sched_analyze_insn (struct deps *deps, rtx x, rtx insn)
1119 {
1120 RTX_CODE code = GET_CODE (x);
1121 rtx link;
1122 unsigned i;
1123 reg_set_iterator rsi;
1124
1125 if (code == COND_EXEC)
1126 {
1127 sched_analyze_2 (deps, COND_EXEC_TEST (x), insn);
1128
1129 /* ??? Should be recording conditions so we reduce the number of
1130 false dependencies. */
1131 x = COND_EXEC_CODE (x);
1132 code = GET_CODE (x);
1133 }
1134 if (code == SET || code == CLOBBER)
1135 {
1136 sched_analyze_1 (deps, x, insn);
1137
1138 /* Bare clobber insns are used for letting life analysis, reg-stack
1139 and others know that a value is dead. Depend on the last call
1140 instruction so that reg-stack won't get confused. */
1141 if (code == CLOBBER)
1142 add_dependence_list (insn, deps->last_function_call, 1, REG_DEP_OUTPUT);
1143 }
1144 else if (code == PARALLEL)
1145 {
1146 for (i = XVECLEN (x, 0); i--;)
1147 {
1148 rtx sub = XVECEXP (x, 0, i);
1149 code = GET_CODE (sub);
1150
1151 if (code == COND_EXEC)
1152 {
1153 sched_analyze_2 (deps, COND_EXEC_TEST (sub), insn);
1154 sub = COND_EXEC_CODE (sub);
1155 code = GET_CODE (sub);
1156 }
1157 if (code == SET || code == CLOBBER)
1158 sched_analyze_1 (deps, sub, insn);
1159 else
1160 sched_analyze_2 (deps, sub, insn);
1161 }
1162 }
1163 else
1164 sched_analyze_2 (deps, x, insn);
1165
1166 /* Mark registers CLOBBERED or used by called function. */
1167 if (CALL_P (insn))
1168 {
1169 for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1))
1170 {
1171 if (GET_CODE (XEXP (link, 0)) == CLOBBER)
1172 sched_analyze_1 (deps, XEXP (link, 0), insn);
1173 else
1174 sched_analyze_2 (deps, XEXP (link, 0), insn);
1175 }
1176 if (find_reg_note (insn, REG_SETJMP, NULL))
1177 reg_pending_barrier = MOVE_BARRIER;
1178 }
1179
1180 if (JUMP_P (insn))
1181 {
1182 rtx next;
1183 next = next_nonnote_insn (insn);
1184 if (next && BARRIER_P (next))
1185 reg_pending_barrier = TRUE_BARRIER;
1186 else
1187 {
1188 rtx pending, pending_mem;
1189 regset_head tmp_uses, tmp_sets;
1190 INIT_REG_SET (&tmp_uses);
1191 INIT_REG_SET (&tmp_sets);
1192
1193 (*current_sched_info->compute_jump_reg_dependencies)
1194 (insn, &deps->reg_conditional_sets, &tmp_uses, &tmp_sets);
1195 /* Make latency of jump equal to 0 by using anti-dependence. */
1196 EXECUTE_IF_SET_IN_REG_SET (&tmp_uses, 0, i, rsi)
1197 {
1198 struct deps_reg *reg_last = &deps->reg_last[i];
1199 add_dependence_list (insn, reg_last->sets, 0, REG_DEP_ANTI);
1200 add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_ANTI);
1201 reg_last->uses_length++;
1202 reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
1203 }
1204 IOR_REG_SET (reg_pending_sets, &tmp_sets);
1205
1206 CLEAR_REG_SET (&tmp_uses);
1207 CLEAR_REG_SET (&tmp_sets);
1208
1209 /* All memory writes and volatile reads must happen before the
1210 jump. Non-volatile reads must happen before the jump iff
1211 the result is needed by the above register used mask. */
1212
1213 pending = deps->pending_write_insns;
1214 pending_mem = deps->pending_write_mems;
1215 while (pending)
1216 {
1217 if (! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
1218 add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT);
1219 pending = XEXP (pending, 1);
1220 pending_mem = XEXP (pending_mem, 1);
1221 }
1222
1223 pending = deps->pending_read_insns;
1224 pending_mem = deps->pending_read_mems;
1225 while (pending)
1226 {
1227 if (MEM_VOLATILE_P (XEXP (pending_mem, 0))
1228 && ! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
1229 add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT);
1230 pending = XEXP (pending, 1);
1231 pending_mem = XEXP (pending_mem, 1);
1232 }
1233
1234 add_dependence_list (insn, deps->last_pending_memory_flush, 1,
1235 REG_DEP_ANTI);
1236 }
1237 }
1238
1239 /* If this instruction can throw an exception, then moving it changes
1240 where block boundaries fall. This is mighty confusing elsewhere.
1241 Therefore, prevent such an instruction from being moved. Same for
1242 non-jump instructions that define block boundaries.
1243 ??? Unclear whether this is still necessary in EBB mode. If not,
1244 add_branch_dependences should be adjusted for RGN mode instead. */
1245 if (((CALL_P (insn) || JUMP_P (insn)) && can_throw_internal (insn))
1246 || (NONJUMP_INSN_P (insn) && control_flow_insn_p (insn)))
1247 reg_pending_barrier = MOVE_BARRIER;
1248
1249 /* Add dependencies if a scheduling barrier was found. */
1250 if (reg_pending_barrier)
1251 {
1252 /* In the case of barrier the most added dependencies are not
1253 real, so we use anti-dependence here. */
1254 if (sched_get_condition (insn))
1255 {
1256 EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
1257 {
1258 struct deps_reg *reg_last = &deps->reg_last[i];
1259 add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI);
1260 add_dependence_list
1261 (insn, reg_last->sets, 0,
1262 reg_pending_barrier == TRUE_BARRIER ? REG_DEP_TRUE : REG_DEP_ANTI);
1263 add_dependence_list
1264 (insn, reg_last->clobbers, 0,
1265 reg_pending_barrier == TRUE_BARRIER ? REG_DEP_TRUE : REG_DEP_ANTI);
1266 }
1267 }
1268 else
1269 {
1270 EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
1271 {
1272 struct deps_reg *reg_last = &deps->reg_last[i];
1273 add_dependence_list_and_free (insn, ®_last->uses, 0,
1274 REG_DEP_ANTI);
1275 add_dependence_list_and_free
1276 (insn, ®_last->sets, 0,
1277 reg_pending_barrier == TRUE_BARRIER ? REG_DEP_TRUE : REG_DEP_ANTI);
1278 add_dependence_list_and_free
1279 (insn, ®_last->clobbers, 0,
1280 reg_pending_barrier == TRUE_BARRIER ? REG_DEP_TRUE : REG_DEP_ANTI);
1281 reg_last->uses_length = 0;
1282 reg_last->clobbers_length = 0;
1283 }
1284 }
1285
1286 for (i = 0; i < (unsigned)deps->max_reg; i++)
1287 {
1288 struct deps_reg *reg_last = &deps->reg_last[i];
1289 reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
1290 SET_REGNO_REG_SET (&deps->reg_last_in_use, i);
1291 }
1292
1293 flush_pending_lists (deps, insn, true, true);
1294 CLEAR_REG_SET (&deps->reg_conditional_sets);
1295 reg_pending_barrier = NOT_A_BARRIER;
1296 }
1297 else
1298 {
1299 /* If the current insn is conditional, we can't free any
1300 of the lists. */
1301 if (sched_get_condition (insn))
1302 {
1303 EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i, rsi)
1304 {
1305 struct deps_reg *reg_last = &deps->reg_last[i];
1306 add_dependence_list (insn, reg_last->sets, 0, REG_DEP_TRUE);
1307 add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_TRUE);
1308 reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
1309 reg_last->uses_length++;
1310 }
1311 EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers, 0, i, rsi)
1312 {
1313 struct deps_reg *reg_last = &deps->reg_last[i];
1314 add_dependence_list (insn, reg_last->sets, 0, REG_DEP_OUTPUT);
1315 add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI);
1316 reg_last->clobbers = alloc_INSN_LIST (insn, reg_last->clobbers);
1317 reg_last->clobbers_length++;
1318 }
1319 EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets, 0, i, rsi)
1320 {
1321 struct deps_reg *reg_last = &deps->reg_last[i];
1322 add_dependence_list (insn, reg_last->sets, 0, REG_DEP_OUTPUT);
1323 add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_OUTPUT);
1324 add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI);
1325 reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
1326 SET_REGNO_REG_SET (&deps->reg_conditional_sets, i);
1327 }
1328 }
1329 else
1330 {
1331 EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i, rsi)
1332 {
1333 struct deps_reg *reg_last = &deps->reg_last[i];
1334 add_dependence_list (insn, reg_last->sets, 0, REG_DEP_TRUE);
1335 add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_TRUE);
1336 reg_last->uses_length++;
1337 reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
1338 }
1339 EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers, 0, i, rsi)
1340 {
1341 struct deps_reg *reg_last = &deps->reg_last[i];
1342 if (reg_last->uses_length > MAX_PENDING_LIST_LENGTH
1343 || reg_last->clobbers_length > MAX_PENDING_LIST_LENGTH)
1344 {
1345 add_dependence_list_and_free (insn, ®_last->sets, 0,
1346 REG_DEP_OUTPUT);
1347 add_dependence_list_and_free (insn, ®_last->uses, 0,
1348 REG_DEP_ANTI);
1349 add_dependence_list_and_free (insn, ®_last->clobbers, 0,
1350 REG_DEP_OUTPUT);
1351 reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
1352 reg_last->clobbers_length = 0;
1353 reg_last->uses_length = 0;
1354 }
1355 else
1356 {
1357 add_dependence_list (insn, reg_last->sets, 0, REG_DEP_OUTPUT);
1358 add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI);
1359 }
1360 reg_last->clobbers_length++;
1361 reg_last->clobbers = alloc_INSN_LIST (insn, reg_last->clobbers);
1362 }
1363 EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets, 0, i, rsi)
1364 {
1365 struct deps_reg *reg_last = &deps->reg_last[i];
1366 add_dependence_list_and_free (insn, ®_last->sets, 0,
1367 REG_DEP_OUTPUT);
1368 add_dependence_list_and_free (insn, ®_last->clobbers, 0,
1369 REG_DEP_OUTPUT);
1370 add_dependence_list_and_free (insn, ®_last->uses, 0,
1371 REG_DEP_ANTI);
1372 reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
1373 reg_last->uses_length = 0;
1374 reg_last->clobbers_length = 0;
1375 CLEAR_REGNO_REG_SET (&deps->reg_conditional_sets, i);
1376 }
1377 }
1378
1379 IOR_REG_SET (&deps->reg_last_in_use, reg_pending_uses);
1380 IOR_REG_SET (&deps->reg_last_in_use, reg_pending_clobbers);
1381 IOR_REG_SET (&deps->reg_last_in_use, reg_pending_sets);
1382 }
1383 CLEAR_REG_SET (reg_pending_uses);
1384 CLEAR_REG_SET (reg_pending_clobbers);
1385 CLEAR_REG_SET (reg_pending_sets);
1386
1387 /* If we are currently in a libcall scheduling group, then mark the
1388 current insn as being in a scheduling group and that it can not
1389 be moved into a different basic block. */
1390
1391 if (deps->libcall_block_tail_insn)
1392 {
1393 SCHED_GROUP_P (insn) = 1;
1394 CANT_MOVE (insn) = 1;
1395 }
1396
1397 /* If a post-call group is still open, see if it should remain so.
1398 This insn must be a simple move of a hard reg to a pseudo or
1399 vice-versa.
1400
1401 We must avoid moving these insns for correctness on
1402 SMALL_REGISTER_CLASS machines, and for special registers like
1403 PIC_OFFSET_TABLE_REGNUM. For simplicity, extend this to all
1404 hard regs for all targets. */
1405
1406 if (deps->in_post_call_group_p)
1407 {
1408 rtx tmp, set = single_set (insn);
1409 int src_regno, dest_regno;
1410
1411 if (set == NULL)
1412 goto end_call_group;
1413
1414 tmp = SET_DEST (set);
1415 if (GET_CODE (tmp) == SUBREG)
1416 tmp = SUBREG_REG (tmp);
1417 if (REG_P (tmp))
1418 dest_regno = REGNO (tmp);
1419 else
1420 goto end_call_group;
1421
1422 tmp = SET_SRC (set);
1423 if (GET_CODE (tmp) == SUBREG)
1424 tmp = SUBREG_REG (tmp);
1425 if ((GET_CODE (tmp) == PLUS
1426 || GET_CODE (tmp) == MINUS)
1427 && REG_P (XEXP (tmp, 0))
1428 && REGNO (XEXP (tmp, 0)) == STACK_POINTER_REGNUM
1429 && dest_regno == STACK_POINTER_REGNUM)
1430 src_regno = STACK_POINTER_REGNUM;
1431 else if (REG_P (tmp))
1432 src_regno = REGNO (tmp);
1433 else
1434 goto end_call_group;
1435
1436 if (src_regno < FIRST_PSEUDO_REGISTER
1437 || dest_regno < FIRST_PSEUDO_REGISTER)
1438 {
1439 if (deps->in_post_call_group_p == post_call_initial)
1440 deps->in_post_call_group_p = post_call;
1441
1442 SCHED_GROUP_P (insn) = 1;
1443 CANT_MOVE (insn) = 1;
1444 }
1445 else
1446 {
1447 end_call_group:
1448 deps->in_post_call_group_p = not_post_call;
1449 }
1450 }
1451
1452 /* Fixup the dependencies in the sched group. */
1453 if (SCHED_GROUP_P (insn))
1454 fixup_sched_groups (insn);
1455 }
1456
1457 /* Analyze every insn between HEAD and TAIL inclusive, creating LOG_LINKS
1458 for every dependency. */
1459
1460 void
sched_analyze(struct deps * deps,rtx head,rtx tail)1461 sched_analyze (struct deps *deps, rtx head, rtx tail)
1462 {
1463 rtx insn;
1464
1465 if (current_sched_info->use_cselib)
1466 cselib_init (true);
1467
1468 /* Before reload, if the previous block ended in a call, show that
1469 we are inside a post-call group, so as to keep the lifetimes of
1470 hard registers correct. */
1471 if (! reload_completed && !LABEL_P (head))
1472 {
1473 insn = prev_nonnote_insn (head);
1474 if (insn && CALL_P (insn))
1475 deps->in_post_call_group_p = post_call_initial;
1476 }
1477 for (insn = head;; insn = NEXT_INSN (insn))
1478 {
1479 rtx link, end_seq, r0, set;
1480
1481 if (NONJUMP_INSN_P (insn) || JUMP_P (insn))
1482 {
1483 /* Clear out the stale LOG_LINKS from flow. */
1484 free_INSN_LIST_list (&LOG_LINKS (insn));
1485
1486 /* Make each JUMP_INSN a scheduling barrier for memory
1487 references. */
1488 if (JUMP_P (insn))
1489 {
1490 /* Keep the list a reasonable size. */
1491 if (deps->pending_flush_length++ > MAX_PENDING_LIST_LENGTH)
1492 flush_pending_lists (deps, insn, true, true);
1493 else
1494 deps->last_pending_memory_flush
1495 = alloc_INSN_LIST (insn, deps->last_pending_memory_flush);
1496 }
1497 sched_analyze_insn (deps, PATTERN (insn), insn);
1498 }
1499 else if (CALL_P (insn))
1500 {
1501 int i;
1502
1503 CANT_MOVE (insn) = 1;
1504
1505 /* Clear out the stale LOG_LINKS from flow. */
1506 free_INSN_LIST_list (&LOG_LINKS (insn));
1507
1508 if (find_reg_note (insn, REG_SETJMP, NULL))
1509 {
1510 /* This is setjmp. Assume that all registers, not just
1511 hard registers, may be clobbered by this call. */
1512 reg_pending_barrier = MOVE_BARRIER;
1513 }
1514 else
1515 {
1516 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1517 /* A call may read and modify global register variables. */
1518 if (global_regs[i])
1519 {
1520 SET_REGNO_REG_SET (reg_pending_sets, i);
1521 SET_REGNO_REG_SET (reg_pending_uses, i);
1522 }
1523 /* Other call-clobbered hard regs may be clobbered.
1524 Since we only have a choice between 'might be clobbered'
1525 and 'definitely not clobbered', we must include all
1526 partly call-clobbered registers here. */
1527 else if (HARD_REGNO_CALL_PART_CLOBBERED (i, reg_raw_mode[i])
1528 || TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
1529 SET_REGNO_REG_SET (reg_pending_clobbers, i);
1530 /* We don't know what set of fixed registers might be used
1531 by the function, but it is certain that the stack pointer
1532 is among them, but be conservative. */
1533 else if (fixed_regs[i])
1534 SET_REGNO_REG_SET (reg_pending_uses, i);
1535 /* The frame pointer is normally not used by the function
1536 itself, but by the debugger. */
1537 /* ??? MIPS o32 is an exception. It uses the frame pointer
1538 in the macro expansion of jal but does not represent this
1539 fact in the call_insn rtl. */
1540 else if (i == FRAME_POINTER_REGNUM
1541 || (i == HARD_FRAME_POINTER_REGNUM
1542 && (! reload_completed || frame_pointer_needed)))
1543 SET_REGNO_REG_SET (reg_pending_uses, i);
1544 }
1545
1546 /* For each insn which shouldn't cross a call, add a dependence
1547 between that insn and this call insn. */
1548 add_dependence_list_and_free (insn, &deps->sched_before_next_call, 1,
1549 REG_DEP_ANTI);
1550
1551 sched_analyze_insn (deps, PATTERN (insn), insn);
1552
1553 /* In the absence of interprocedural alias analysis, we must flush
1554 all pending reads and writes, and start new dependencies starting
1555 from here. But only flush writes for constant calls (which may
1556 be passed a pointer to something we haven't written yet). */
1557 flush_pending_lists (deps, insn, true, !CONST_OR_PURE_CALL_P (insn));
1558
1559 /* Remember the last function call for limiting lifetimes. */
1560 free_INSN_LIST_list (&deps->last_function_call);
1561 deps->last_function_call = alloc_INSN_LIST (insn, NULL_RTX);
1562
1563 /* Before reload, begin a post-call group, so as to keep the
1564 lifetimes of hard registers correct. */
1565 if (! reload_completed)
1566 deps->in_post_call_group_p = post_call;
1567 }
1568
1569 /* EH_REGION insn notes can not appear until well after we complete
1570 scheduling. */
1571 if (NOTE_P (insn))
1572 gcc_assert (NOTE_LINE_NUMBER (insn) != NOTE_INSN_EH_REGION_BEG
1573 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_EH_REGION_END);
1574
1575 if (current_sched_info->use_cselib)
1576 cselib_process_insn (insn);
1577
1578 /* Now that we have completed handling INSN, check and see if it is
1579 a CLOBBER beginning a libcall block. If it is, record the
1580 end of the libcall sequence.
1581
1582 We want to schedule libcall blocks as a unit before reload. While
1583 this restricts scheduling, it preserves the meaning of a libcall
1584 block.
1585
1586 As a side effect, we may get better code due to decreased register
1587 pressure as well as less chance of a foreign insn appearing in
1588 a libcall block. */
1589 if (!reload_completed
1590 /* Note we may have nested libcall sequences. We only care about
1591 the outermost libcall sequence. */
1592 && deps->libcall_block_tail_insn == 0
1593 /* The sequence must start with a clobber of a register. */
1594 && NONJUMP_INSN_P (insn)
1595 && GET_CODE (PATTERN (insn)) == CLOBBER
1596 && (r0 = XEXP (PATTERN (insn), 0), REG_P (r0))
1597 && REG_P (XEXP (PATTERN (insn), 0))
1598 /* The CLOBBER must also have a REG_LIBCALL note attached. */
1599 && (link = find_reg_note (insn, REG_LIBCALL, NULL_RTX)) != 0
1600 && (end_seq = XEXP (link, 0)) != 0
1601 /* The insn referenced by the REG_LIBCALL note must be a
1602 simple nop copy with the same destination as the register
1603 mentioned in the clobber. */
1604 && (set = single_set (end_seq)) != 0
1605 && SET_DEST (set) == r0 && SET_SRC (set) == r0
1606 /* And finally the insn referenced by the REG_LIBCALL must
1607 also contain a REG_EQUAL note and a REG_RETVAL note. */
1608 && find_reg_note (end_seq, REG_EQUAL, NULL_RTX) != 0
1609 && find_reg_note (end_seq, REG_RETVAL, NULL_RTX) != 0)
1610 deps->libcall_block_tail_insn = XEXP (link, 0);
1611
1612 /* If we have reached the end of a libcall block, then close the
1613 block. */
1614 if (deps->libcall_block_tail_insn == insn)
1615 deps->libcall_block_tail_insn = 0;
1616
1617 if (insn == tail)
1618 {
1619 if (current_sched_info->use_cselib)
1620 cselib_finish ();
1621 return;
1622 }
1623 }
1624 gcc_unreachable ();
1625 }
1626
1627
1628 /* The following function adds forward dependence (FROM, TO) with
1629 given DEP_TYPE. The forward dependence should be not exist before. */
1630
1631 void
add_forw_dep(rtx to,rtx link)1632 add_forw_dep (rtx to, rtx link)
1633 {
1634 rtx new_link, from;
1635
1636 from = XEXP (link, 0);
1637
1638 #ifdef ENABLE_CHECKING
1639 /* If add_dependence is working properly there should never
1640 be notes, deleted insns or duplicates in the backward
1641 links. Thus we need not check for them here.
1642
1643 However, if we have enabled checking we might as well go
1644 ahead and verify that add_dependence worked properly. */
1645 gcc_assert (INSN_P (from));
1646 gcc_assert (!INSN_DELETED_P (from));
1647 if (true_dependency_cache)
1648 {
1649 gcc_assert (!bitmap_bit_p (&forward_dependency_cache[INSN_LUID (from)],
1650 INSN_LUID (to)));
1651 bitmap_set_bit (&forward_dependency_cache[INSN_LUID (from)],
1652 INSN_LUID (to));
1653 }
1654 else
1655 gcc_assert (!find_insn_list (to, INSN_DEPEND (from)));
1656 #endif
1657
1658 if (!(current_sched_info->flags & USE_DEPS_LIST))
1659 new_link = alloc_INSN_LIST (to, INSN_DEPEND (from));
1660 else
1661 new_link = alloc_DEPS_LIST (to, INSN_DEPEND (from), DEP_STATUS (link));
1662
1663 PUT_REG_NOTE_KIND (new_link, REG_NOTE_KIND (link));
1664
1665 INSN_DEPEND (from) = new_link;
1666 INSN_DEP_COUNT (to) += 1;
1667 }
1668
1669 /* Examine insns in the range [ HEAD, TAIL ] and Use the backward
1670 dependences from LOG_LINKS to build forward dependences in
1671 INSN_DEPEND. */
1672
1673 void
compute_forward_dependences(rtx head,rtx tail)1674 compute_forward_dependences (rtx head, rtx tail)
1675 {
1676 rtx insn;
1677 rtx next_tail;
1678
1679 next_tail = NEXT_INSN (tail);
1680 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
1681 {
1682 rtx link;
1683
1684 if (! INSN_P (insn))
1685 continue;
1686
1687 if (current_sched_info->flags & DO_SPECULATION)
1688 {
1689 rtx new = 0, link, next;
1690
1691 for (link = LOG_LINKS (insn); link; link = next)
1692 {
1693 next = XEXP (link, 1);
1694 adjust_add_sorted_back_dep (insn, link, &new);
1695 }
1696
1697 LOG_LINKS (insn) = new;
1698 }
1699
1700 for (link = LOG_LINKS (insn); link; link = XEXP (link, 1))
1701 add_forw_dep (insn, link);
1702 }
1703 }
1704
1705 /* Initialize variables for region data dependence analysis.
1706 n_bbs is the number of region blocks. */
1707
1708 void
init_deps(struct deps * deps)1709 init_deps (struct deps *deps)
1710 {
1711 int max_reg = (reload_completed ? FIRST_PSEUDO_REGISTER : max_reg_num ());
1712
1713 deps->max_reg = max_reg;
1714 deps->reg_last = XCNEWVEC (struct deps_reg, max_reg);
1715 INIT_REG_SET (&deps->reg_last_in_use);
1716 INIT_REG_SET (&deps->reg_conditional_sets);
1717
1718 deps->pending_read_insns = 0;
1719 deps->pending_read_mems = 0;
1720 deps->pending_write_insns = 0;
1721 deps->pending_write_mems = 0;
1722 deps->pending_lists_length = 0;
1723 deps->pending_flush_length = 0;
1724 deps->last_pending_memory_flush = 0;
1725 deps->last_function_call = 0;
1726 deps->sched_before_next_call = 0;
1727 deps->in_post_call_group_p = not_post_call;
1728 deps->libcall_block_tail_insn = 0;
1729 }
1730
1731 /* Free insn lists found in DEPS. */
1732
1733 void
free_deps(struct deps * deps)1734 free_deps (struct deps *deps)
1735 {
1736 unsigned i;
1737 reg_set_iterator rsi;
1738
1739 free_INSN_LIST_list (&deps->pending_read_insns);
1740 free_EXPR_LIST_list (&deps->pending_read_mems);
1741 free_INSN_LIST_list (&deps->pending_write_insns);
1742 free_EXPR_LIST_list (&deps->pending_write_mems);
1743 free_INSN_LIST_list (&deps->last_pending_memory_flush);
1744
1745 /* Without the EXECUTE_IF_SET, this loop is executed max_reg * nr_regions
1746 times. For a testcase with 42000 regs and 8000 small basic blocks,
1747 this loop accounted for nearly 60% (84 sec) of the total -O2 runtime. */
1748 EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
1749 {
1750 struct deps_reg *reg_last = &deps->reg_last[i];
1751 if (reg_last->uses)
1752 free_INSN_LIST_list (®_last->uses);
1753 if (reg_last->sets)
1754 free_INSN_LIST_list (®_last->sets);
1755 if (reg_last->clobbers)
1756 free_INSN_LIST_list (®_last->clobbers);
1757 }
1758 CLEAR_REG_SET (&deps->reg_last_in_use);
1759 CLEAR_REG_SET (&deps->reg_conditional_sets);
1760
1761 free (deps->reg_last);
1762 }
1763
1764 /* If it is profitable to use them, initialize caches for tracking
1765 dependency information. LUID is the number of insns to be scheduled,
1766 it is used in the estimate of profitability. */
1767
1768 void
init_dependency_caches(int luid)1769 init_dependency_caches (int luid)
1770 {
1771 /* ?!? We could save some memory by computing a per-region luid mapping
1772 which could reduce both the number of vectors in the cache and the size
1773 of each vector. Instead we just avoid the cache entirely unless the
1774 average number of instructions in a basic block is very high. See
1775 the comment before the declaration of true_dependency_cache for
1776 what we consider "very high". */
1777 if (luid / n_basic_blocks > 100 * 5)
1778 {
1779 cache_size = 0;
1780 extend_dependency_caches (luid, true);
1781 }
1782 }
1783
1784 /* Create or extend (depending on CREATE_P) dependency caches to
1785 size N. */
1786 void
extend_dependency_caches(int n,bool create_p)1787 extend_dependency_caches (int n, bool create_p)
1788 {
1789 if (create_p || true_dependency_cache)
1790 {
1791 int i, luid = cache_size + n;
1792
1793 true_dependency_cache = XRESIZEVEC (bitmap_head, true_dependency_cache,
1794 luid);
1795 output_dependency_cache = XRESIZEVEC (bitmap_head,
1796 output_dependency_cache, luid);
1797 anti_dependency_cache = XRESIZEVEC (bitmap_head, anti_dependency_cache,
1798 luid);
1799 #ifdef ENABLE_CHECKING
1800 forward_dependency_cache = XRESIZEVEC (bitmap_head,
1801 forward_dependency_cache, luid);
1802 #endif
1803 if (current_sched_info->flags & DO_SPECULATION)
1804 spec_dependency_cache = XRESIZEVEC (bitmap_head, spec_dependency_cache,
1805 luid);
1806
1807 for (i = cache_size; i < luid; i++)
1808 {
1809 bitmap_initialize (&true_dependency_cache[i], 0);
1810 bitmap_initialize (&output_dependency_cache[i], 0);
1811 bitmap_initialize (&anti_dependency_cache[i], 0);
1812 #ifdef ENABLE_CHECKING
1813 bitmap_initialize (&forward_dependency_cache[i], 0);
1814 #endif
1815 if (current_sched_info->flags & DO_SPECULATION)
1816 bitmap_initialize (&spec_dependency_cache[i], 0);
1817 }
1818 cache_size = luid;
1819 }
1820 }
1821
1822 /* Free the caches allocated in init_dependency_caches. */
1823
1824 void
free_dependency_caches(void)1825 free_dependency_caches (void)
1826 {
1827 if (true_dependency_cache)
1828 {
1829 int i;
1830
1831 for (i = 0; i < cache_size; i++)
1832 {
1833 bitmap_clear (&true_dependency_cache[i]);
1834 bitmap_clear (&output_dependency_cache[i]);
1835 bitmap_clear (&anti_dependency_cache[i]);
1836 #ifdef ENABLE_CHECKING
1837 bitmap_clear (&forward_dependency_cache[i]);
1838 #endif
1839 if (current_sched_info->flags & DO_SPECULATION)
1840 bitmap_clear (&spec_dependency_cache[i]);
1841 }
1842 free (true_dependency_cache);
1843 true_dependency_cache = NULL;
1844 free (output_dependency_cache);
1845 output_dependency_cache = NULL;
1846 free (anti_dependency_cache);
1847 anti_dependency_cache = NULL;
1848 #ifdef ENABLE_CHECKING
1849 free (forward_dependency_cache);
1850 forward_dependency_cache = NULL;
1851 #endif
1852 if (current_sched_info->flags & DO_SPECULATION)
1853 {
1854 free (spec_dependency_cache);
1855 spec_dependency_cache = NULL;
1856 }
1857 }
1858 }
1859
1860 /* Initialize some global variables needed by the dependency analysis
1861 code. */
1862
1863 void
init_deps_global(void)1864 init_deps_global (void)
1865 {
1866 reg_pending_sets = ALLOC_REG_SET (®_obstack);
1867 reg_pending_clobbers = ALLOC_REG_SET (®_obstack);
1868 reg_pending_uses = ALLOC_REG_SET (®_obstack);
1869 reg_pending_barrier = NOT_A_BARRIER;
1870 }
1871
1872 /* Free everything used by the dependency analysis code. */
1873
1874 void
finish_deps_global(void)1875 finish_deps_global (void)
1876 {
1877 FREE_REG_SET (reg_pending_sets);
1878 FREE_REG_SET (reg_pending_clobbers);
1879 FREE_REG_SET (reg_pending_uses);
1880 }
1881
1882 /* Insert LINK into the dependence chain pointed to by LINKP and
1883 maintain the sort order. */
1884 static void
adjust_add_sorted_back_dep(rtx insn,rtx link,rtx * linkp)1885 adjust_add_sorted_back_dep (rtx insn, rtx link, rtx *linkp)
1886 {
1887 gcc_assert (current_sched_info->flags & DO_SPECULATION);
1888
1889 /* If the insn cannot move speculatively, but the link is speculative,
1890 make it hard dependence. */
1891 if (HAS_INTERNAL_DEP (insn)
1892 && (DEP_STATUS (link) & SPECULATIVE))
1893 {
1894 DEP_STATUS (link) &= ~SPECULATIVE;
1895
1896 if (true_dependency_cache)
1897 bitmap_clear_bit (&spec_dependency_cache[INSN_LUID (insn)],
1898 INSN_LUID (XEXP (link, 0)));
1899 }
1900
1901 /* Non-speculative links go at the head of LOG_LINKS, followed by
1902 speculative links. */
1903 if (DEP_STATUS (link) & SPECULATIVE)
1904 while (*linkp && !(DEP_STATUS (*linkp) & SPECULATIVE))
1905 linkp = &XEXP (*linkp, 1);
1906
1907 XEXP (link, 1) = *linkp;
1908 *linkp = link;
1909 }
1910
1911 /* Move the dependence pointed to by LINKP to the back dependencies
1912 of INSN, and also add this dependence to the forward ones. All LOG_LINKS,
1913 except one pointed to by LINKP, must be sorted. */
1914 static void
adjust_back_add_forw_dep(rtx insn,rtx * linkp)1915 adjust_back_add_forw_dep (rtx insn, rtx *linkp)
1916 {
1917 rtx link;
1918
1919 gcc_assert (current_sched_info->flags & DO_SPECULATION);
1920
1921 link = *linkp;
1922 *linkp = XEXP (*linkp, 1);
1923
1924 adjust_add_sorted_back_dep (insn, link, &LOG_LINKS (insn));
1925 add_forw_dep (insn, link);
1926 }
1927
1928 /* Remove forward dependence ELEM from the DEPS_LIST of INSN. */
1929 static void
delete_forw_dep(rtx insn,rtx elem)1930 delete_forw_dep (rtx insn, rtx elem)
1931 {
1932 gcc_assert (current_sched_info->flags & DO_SPECULATION);
1933
1934 #ifdef ENABLE_CHECKING
1935 if (true_dependency_cache)
1936 bitmap_clear_bit (&forward_dependency_cache[INSN_LUID (elem)],
1937 INSN_LUID (insn));
1938 #endif
1939
1940 remove_free_DEPS_LIST_elem (insn, &INSN_DEPEND (elem));
1941 INSN_DEP_COUNT (insn)--;
1942 }
1943
1944 /* Estimate the weakness of dependence between MEM1 and MEM2. */
1945 static dw_t
estimate_dep_weak(rtx mem1,rtx mem2)1946 estimate_dep_weak (rtx mem1, rtx mem2)
1947 {
1948 rtx r1, r2;
1949
1950 if (mem1 == mem2)
1951 /* MEMs are the same - don't speculate. */
1952 return MIN_DEP_WEAK;
1953
1954 r1 = XEXP (mem1, 0);
1955 r2 = XEXP (mem2, 0);
1956
1957 if (r1 == r2
1958 || (REG_P (r1) && REG_P (r2)
1959 && REGNO (r1) == REGNO (r2)))
1960 /* Again, MEMs are the same. */
1961 return MIN_DEP_WEAK;
1962 else if ((REG_P (r1) && !REG_P (r2))
1963 || (!REG_P (r1) && REG_P (r2)))
1964 /* Different addressing modes - reason to be more speculative,
1965 than usual. */
1966 return NO_DEP_WEAK - (NO_DEP_WEAK - UNCERTAIN_DEP_WEAK) / 2;
1967 else
1968 /* We can't say anything about the dependence. */
1969 return UNCERTAIN_DEP_WEAK;
1970 }
1971
1972 /* Add or update backward dependence between INSN and ELEM with type DEP_TYPE.
1973 This function can handle same INSN and ELEM (INSN == ELEM).
1974 It is a convenience wrapper. */
1975 void
add_dependence(rtx insn,rtx elem,enum reg_note dep_type)1976 add_dependence (rtx insn, rtx elem, enum reg_note dep_type)
1977 {
1978 ds_t ds;
1979
1980 if (dep_type == REG_DEP_TRUE)
1981 ds = DEP_TRUE;
1982 else if (dep_type == REG_DEP_OUTPUT)
1983 ds = DEP_OUTPUT;
1984 else if (dep_type == REG_DEP_ANTI)
1985 ds = DEP_ANTI;
1986 else
1987 gcc_unreachable ();
1988
1989 maybe_add_or_update_back_dep_1 (insn, elem, dep_type, ds, 0, 0, 0);
1990 }
1991
1992 /* Add or update backward dependence between INSN and ELEM
1993 with given type DEP_TYPE and dep_status DS.
1994 This function is a convenience wrapper. */
1995 enum DEPS_ADJUST_RESULT
add_or_update_back_dep(rtx insn,rtx elem,enum reg_note dep_type,ds_t ds)1996 add_or_update_back_dep (rtx insn, rtx elem, enum reg_note dep_type, ds_t ds)
1997 {
1998 return add_or_update_back_dep_1 (insn, elem, dep_type, ds, 0, 0, 0);
1999 }
2000
2001 /* Add or update both backward and forward dependencies between INSN and ELEM
2002 with given type DEP_TYPE and dep_status DS. */
2003 void
add_or_update_back_forw_dep(rtx insn,rtx elem,enum reg_note dep_type,ds_t ds)2004 add_or_update_back_forw_dep (rtx insn, rtx elem, enum reg_note dep_type,
2005 ds_t ds)
2006 {
2007 enum DEPS_ADJUST_RESULT res;
2008 rtx *linkp;
2009
2010 res = add_or_update_back_dep_1 (insn, elem, dep_type, ds, 0, 0, &linkp);
2011
2012 if (res == DEP_CHANGED || res == DEP_CREATED)
2013 {
2014 if (res == DEP_CHANGED)
2015 delete_forw_dep (insn, elem);
2016 else if (res == DEP_CREATED)
2017 linkp = &LOG_LINKS (insn);
2018
2019 adjust_back_add_forw_dep (insn, linkp);
2020 }
2021 }
2022
2023 /* Add both backward and forward dependencies between INSN and ELEM
2024 with given type DEP_TYPE and dep_status DS. */
2025 void
add_back_forw_dep(rtx insn,rtx elem,enum reg_note dep_type,ds_t ds)2026 add_back_forw_dep (rtx insn, rtx elem, enum reg_note dep_type, ds_t ds)
2027 {
2028 add_back_dep (insn, elem, dep_type, ds);
2029 adjust_back_add_forw_dep (insn, &LOG_LINKS (insn));
2030 }
2031
2032 /* Remove both backward and forward dependencies between INSN and ELEM. */
2033 void
delete_back_forw_dep(rtx insn,rtx elem)2034 delete_back_forw_dep (rtx insn, rtx elem)
2035 {
2036 gcc_assert (current_sched_info->flags & DO_SPECULATION);
2037
2038 if (true_dependency_cache != NULL)
2039 {
2040 bitmap_clear_bit (&true_dependency_cache[INSN_LUID (insn)],
2041 INSN_LUID (elem));
2042 bitmap_clear_bit (&anti_dependency_cache[INSN_LUID (insn)],
2043 INSN_LUID (elem));
2044 bitmap_clear_bit (&output_dependency_cache[INSN_LUID (insn)],
2045 INSN_LUID (elem));
2046 bitmap_clear_bit (&spec_dependency_cache[INSN_LUID (insn)],
2047 INSN_LUID (elem));
2048 }
2049
2050 remove_free_DEPS_LIST_elem (elem, &LOG_LINKS (insn));
2051 delete_forw_dep (insn, elem);
2052 }
2053
2054 /* Return weakness of speculative type TYPE in the dep_status DS. */
2055 dw_t
get_dep_weak(ds_t ds,ds_t type)2056 get_dep_weak (ds_t ds, ds_t type)
2057 {
2058 ds = ds & type;
2059 switch (type)
2060 {
2061 case BEGIN_DATA: ds >>= BEGIN_DATA_BITS_OFFSET; break;
2062 case BE_IN_DATA: ds >>= BE_IN_DATA_BITS_OFFSET; break;
2063 case BEGIN_CONTROL: ds >>= BEGIN_CONTROL_BITS_OFFSET; break;
2064 case BE_IN_CONTROL: ds >>= BE_IN_CONTROL_BITS_OFFSET; break;
2065 default: gcc_unreachable ();
2066 }
2067
2068 gcc_assert (MIN_DEP_WEAK <= ds && ds <= MAX_DEP_WEAK);
2069 return (dw_t) ds;
2070 }
2071
2072 /* Return the dep_status, which has the same parameters as DS, except for
2073 speculative type TYPE, that will have weakness DW. */
2074 ds_t
set_dep_weak(ds_t ds,ds_t type,dw_t dw)2075 set_dep_weak (ds_t ds, ds_t type, dw_t dw)
2076 {
2077 gcc_assert (MIN_DEP_WEAK <= dw && dw <= MAX_DEP_WEAK);
2078
2079 ds &= ~type;
2080 switch (type)
2081 {
2082 case BEGIN_DATA: ds |= ((ds_t) dw) << BEGIN_DATA_BITS_OFFSET; break;
2083 case BE_IN_DATA: ds |= ((ds_t) dw) << BE_IN_DATA_BITS_OFFSET; break;
2084 case BEGIN_CONTROL: ds |= ((ds_t) dw) << BEGIN_CONTROL_BITS_OFFSET; break;
2085 case BE_IN_CONTROL: ds |= ((ds_t) dw) << BE_IN_CONTROL_BITS_OFFSET; break;
2086 default: gcc_unreachable ();
2087 }
2088 return ds;
2089 }
2090
2091 /* Return the join of two dep_statuses DS1 and DS2. */
2092 ds_t
ds_merge(ds_t ds1,ds_t ds2)2093 ds_merge (ds_t ds1, ds_t ds2)
2094 {
2095 ds_t ds, t;
2096
2097 gcc_assert ((ds1 & SPECULATIVE) && (ds2 & SPECULATIVE));
2098
2099 ds = (ds1 & DEP_TYPES) | (ds2 & DEP_TYPES);
2100
2101 t = FIRST_SPEC_TYPE;
2102 do
2103 {
2104 if ((ds1 & t) && !(ds2 & t))
2105 ds |= ds1 & t;
2106 else if (!(ds1 & t) && (ds2 & t))
2107 ds |= ds2 & t;
2108 else if ((ds1 & t) && (ds2 & t))
2109 {
2110 ds_t dw;
2111
2112 dw = ((ds_t) get_dep_weak (ds1, t)) * ((ds_t) get_dep_weak (ds2, t));
2113 dw /= MAX_DEP_WEAK;
2114 if (dw < MIN_DEP_WEAK)
2115 dw = MIN_DEP_WEAK;
2116
2117 ds = set_dep_weak (ds, t, (dw_t) dw);
2118 }
2119
2120 if (t == LAST_SPEC_TYPE)
2121 break;
2122 t <<= SPEC_TYPE_SHIFT;
2123 }
2124 while (1);
2125
2126 return ds;
2127 }
2128
2129 #ifdef INSN_SCHEDULING
2130 #ifdef ENABLE_CHECKING
2131 /* Verify that dependence type and status are consistent.
2132 If RELAXED_P is true, then skip dep_weakness checks. */
2133 static void
check_dep_status(enum reg_note dt,ds_t ds,bool relaxed_p)2134 check_dep_status (enum reg_note dt, ds_t ds, bool relaxed_p)
2135 {
2136 /* Check that dependence type contains the same bits as the status. */
2137 if (dt == REG_DEP_TRUE)
2138 gcc_assert (ds & DEP_TRUE);
2139 else if (dt == REG_DEP_OUTPUT)
2140 gcc_assert ((ds & DEP_OUTPUT)
2141 && !(ds & DEP_TRUE));
2142 else
2143 gcc_assert ((dt == REG_DEP_ANTI)
2144 && (ds & DEP_ANTI)
2145 && !(ds & (DEP_OUTPUT | DEP_TRUE)));
2146
2147 /* HARD_DEP can not appear in dep_status of a link. */
2148 gcc_assert (!(ds & HARD_DEP));
2149
2150 /* Check that dependence status is set correctly when speculation is not
2151 supported. */
2152 if (!(current_sched_info->flags & DO_SPECULATION))
2153 gcc_assert (!(ds & SPECULATIVE));
2154 else if (ds & SPECULATIVE)
2155 {
2156 if (!relaxed_p)
2157 {
2158 ds_t type = FIRST_SPEC_TYPE;
2159
2160 /* Check that dependence weakness is in proper range. */
2161 do
2162 {
2163 if (ds & type)
2164 get_dep_weak (ds, type);
2165
2166 if (type == LAST_SPEC_TYPE)
2167 break;
2168 type <<= SPEC_TYPE_SHIFT;
2169 }
2170 while (1);
2171 }
2172
2173 if (ds & BEGIN_SPEC)
2174 {
2175 /* Only true dependence can be data speculative. */
2176 if (ds & BEGIN_DATA)
2177 gcc_assert (ds & DEP_TRUE);
2178
2179 /* Control dependencies in the insn scheduler are represented by
2180 anti-dependencies, therefore only anti dependence can be
2181 control speculative. */
2182 if (ds & BEGIN_CONTROL)
2183 gcc_assert (ds & DEP_ANTI);
2184 }
2185 else
2186 {
2187 /* Subsequent speculations should resolve true dependencies. */
2188 gcc_assert ((ds & DEP_TYPES) == DEP_TRUE);
2189 }
2190
2191 /* Check that true and anti dependencies can't have other speculative
2192 statuses. */
2193 if (ds & DEP_TRUE)
2194 gcc_assert (ds & (BEGIN_DATA | BE_IN_SPEC));
2195 /* An output dependence can't be speculative at all. */
2196 gcc_assert (!(ds & DEP_OUTPUT));
2197 if (ds & DEP_ANTI)
2198 gcc_assert (ds & BEGIN_CONTROL);
2199 }
2200 }
2201 #endif
2202 #endif
2203