1/* Instruction scheduling pass. This file computes dependencies between
2 instructions.
3 Copyright (C) 1992-2017 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
7This file is part of GCC.
8
9GCC is free software; you can redistribute it and/or modify it under
10the terms of the GNU General Public License as published by the Free
11Software Foundation; either version 3, or (at your option) any later
12version.
13
14GCC is distributed in the hope that it will be useful, but WITHOUT ANY
15WARRANTY; without even the implied warranty of MERCHANTABILITY or
16FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17for more details.
18
19You should have received a copy of the GNU General Public License
20along 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 "params.h"
40#include "cselib.h"
41
42#ifdef INSN_SCHEDULING
43
44/* Holds current parameters for the dependency analyzer. */
45struct sched_deps_info_def *sched_deps_info;
46
47/* The data is specific to the Haifa scheduler. */
48vec<haifa_deps_insn_data_def>
49 h_d_i_d = vNULL;
50
51/* Return the major type present in the DS. */
52enum reg_note
53ds_to_dk (ds_t ds)
54{
55 if (ds & DEP_TRUE)
56 return REG_DEP_TRUE;
57
58 if (ds & DEP_OUTPUT)
59 return REG_DEP_OUTPUT;
60
61 if (ds & DEP_CONTROL)
62 return REG_DEP_CONTROL;
63
64 gcc_assert (ds & DEP_ANTI);
65
66 return REG_DEP_ANTI;
67}
68
69/* Return equivalent dep_status. */
70ds_t
71dk_to_ds (enum reg_note dk)
72{
73 switch (dk)
74 {
75 case REG_DEP_TRUE:
76 return DEP_TRUE;
77
78 case REG_DEP_OUTPUT:
79 return DEP_OUTPUT;
80
81 case REG_DEP_CONTROL:
82 return DEP_CONTROL;
83
84 default:
85 gcc_assert (dk == REG_DEP_ANTI);
86 return DEP_ANTI;
87 }
88}
89
90/* Functions to operate with dependence information container - dep_t. */
91
92/* Init DEP with the arguments. */
93void
94init_dep_1 (dep_t dep, rtx_insn *pro, rtx_insn *con, enum reg_note type, ds_t ds)
95{
96 DEP_PRO (dep) = pro;
97 DEP_CON (dep) = con;
98 DEP_TYPE (dep) = type;
99 DEP_STATUS (dep) = ds;
100 DEP_COST (dep) = UNKNOWN_DEP_COST;
101 DEP_NONREG (dep) = 0;
102 DEP_MULTIPLE (dep) = 0;
103 DEP_REPLACE (dep) = NULL;
104}
105
106/* Init DEP with the arguments.
107 While most of the scheduler (including targets) only need the major type
108 of the dependency, it is convenient to hide full dep_status from them. */
109void
110init_dep (dep_t dep, rtx_insn *pro, rtx_insn *con, enum reg_note kind)
111{
112 ds_t ds;
113
114 if ((current_sched_info->flags & USE_DEPS_LIST))
115 ds = dk_to_ds (kind);
116 else
117 ds = 0;
118
119 init_dep_1 (dep, pro, con, kind, ds);
120}
121
122/* Make a copy of FROM in TO. */
123static void
124copy_dep (dep_t to, dep_t from)
125{
126 memcpy (to, from, sizeof (*to));
127}
128
129static void dump_ds (FILE *, ds_t);
130
131/* Define flags for dump_dep (). */
132
133/* Dump producer of the dependence. */
134#define DUMP_DEP_PRO (2)
135
136/* Dump consumer of the dependence. */
137#define DUMP_DEP_CON (4)
138
139/* Dump type of the dependence. */
140#define DUMP_DEP_TYPE (8)
141
142/* Dump status of the dependence. */
143#define DUMP_DEP_STATUS (16)
144
145/* Dump all information about the dependence. */
146#define DUMP_DEP_ALL (DUMP_DEP_PRO | DUMP_DEP_CON | DUMP_DEP_TYPE \
147 |DUMP_DEP_STATUS)
148
149/* Dump DEP to DUMP.
150 FLAGS is a bit mask specifying what information about DEP needs
151 to be printed.
152 If FLAGS has the very first bit set, then dump all information about DEP
153 and propagate this bit into the callee dump functions. */
154static void
155dump_dep (FILE *dump, dep_t dep, int flags)
156{
157 if (flags & 1)
158 flags |= DUMP_DEP_ALL;
159
160 fprintf (dump, "<");
161
162 if (flags & DUMP_DEP_PRO)
163 fprintf (dump, "%d; ", INSN_UID (DEP_PRO (dep)));
164
165 if (flags & DUMP_DEP_CON)
166 fprintf (dump, "%d; ", INSN_UID (DEP_CON (dep)));
167
168 if (flags & DUMP_DEP_TYPE)
169 {
170 char t;
171 enum reg_note type = DEP_TYPE (dep);
172
173 switch (type)
174 {
175 case REG_DEP_TRUE:
176 t = 't';
177 break;
178
179 case REG_DEP_OUTPUT:
180 t = 'o';
181 break;
182
183 case REG_DEP_CONTROL:
184 t = 'c';
185 break;
186
187 case REG_DEP_ANTI:
188 t = 'a';
189 break;
190
191 default:
192 gcc_unreachable ();
193 break;
194 }
195
196 fprintf (dump, "%c; ", t);
197 }
198
199 if (flags & DUMP_DEP_STATUS)
200 {
201 if (current_sched_info->flags & USE_DEPS_LIST)
202 dump_ds (dump, DEP_STATUS (dep));
203 }
204
205 fprintf (dump, ">");
206}
207
208/* Default flags for dump_dep (). */
209static int dump_dep_flags = (DUMP_DEP_PRO | DUMP_DEP_CON);
210
211/* Dump all fields of DEP to STDERR. */
212void
213sd_debug_dep (dep_t dep)
214{
215 dump_dep (stderr, dep, 1);
216 fprintf (stderr, "\n");
217}
218
219/* Determine whether DEP is a dependency link of a non-debug insn on a
220 debug insn. */
221
222static inline bool
223depl_on_debug_p (dep_link_t dep)
224{
225 return (DEBUG_INSN_P (DEP_LINK_PRO (dep))
226 && !DEBUG_INSN_P (DEP_LINK_CON (dep)));
227}
228
229/* Functions to operate with a single link from the dependencies lists -
230 dep_link_t. */
231
232/* Attach L to appear after link X whose &DEP_LINK_NEXT (X) is given by
233 PREV_NEXT_P. */
234static void
235attach_dep_link (dep_link_t l, dep_link_t *prev_nextp)
236{
237 dep_link_t next = *prev_nextp;
238
239 gcc_assert (DEP_LINK_PREV_NEXTP (l) == NULL
240 && DEP_LINK_NEXT (l) == NULL);
241
242 /* Init node being inserted. */
243 DEP_LINK_PREV_NEXTP (l) = prev_nextp;
244 DEP_LINK_NEXT (l) = next;
245
246 /* Fix next node. */
247 if (next != NULL)
248 {
249 gcc_assert (DEP_LINK_PREV_NEXTP (next) == prev_nextp);
250
251 DEP_LINK_PREV_NEXTP (next) = &DEP_LINK_NEXT (l);
252 }
253
254 /* Fix prev node. */
255 *prev_nextp = l;
256}
257
258/* Add dep_link LINK to deps_list L. */
259static void
260add_to_deps_list (dep_link_t link, deps_list_t l)
261{
262 attach_dep_link (link, &DEPS_LIST_FIRST (l));
263
264 /* Don't count debug deps. */
265 if (!depl_on_debug_p (link))
266 ++DEPS_LIST_N_LINKS (l);
267}
268
269/* Detach dep_link L from the list. */
270static void
271detach_dep_link (dep_link_t l)
272{
273 dep_link_t *prev_nextp = DEP_LINK_PREV_NEXTP (l);
274 dep_link_t next = DEP_LINK_NEXT (l);
275
276 *prev_nextp = next;
277
278 if (next != NULL)
279 DEP_LINK_PREV_NEXTP (next) = prev_nextp;
280
281 DEP_LINK_PREV_NEXTP (l) = NULL;
282 DEP_LINK_NEXT (l) = NULL;
283}
284
285/* Remove link LINK from list LIST. */
286static void
287remove_from_deps_list (dep_link_t link, deps_list_t list)
288{
289 detach_dep_link (link);
290
291 /* Don't count debug deps. */
292 if (!depl_on_debug_p (link))
293 --DEPS_LIST_N_LINKS (list);
294}
295
296/* Move link LINK from list FROM to list TO. */
297static void
298move_dep_link (dep_link_t link, deps_list_t from, deps_list_t to)
299{
300 remove_from_deps_list (link, from);
301 add_to_deps_list (link, to);
302}
303
304/* Return true of LINK is not attached to any list. */
305static bool
306dep_link_is_detached_p (dep_link_t link)
307{
308 return DEP_LINK_PREV_NEXTP (link) == NULL;
309}
310
311/* Pool to hold all dependency nodes (dep_node_t). */
312static object_allocator<_dep_node> *dn_pool;
313
314/* Number of dep_nodes out there. */
315static int dn_pool_diff = 0;
316
317/* Create a dep_node. */
318static dep_node_t
319create_dep_node (void)
320{
321 dep_node_t n = dn_pool->allocate ();
322 dep_link_t back = DEP_NODE_BACK (n);
323 dep_link_t forw = DEP_NODE_FORW (n);
324
325 DEP_LINK_NODE (back) = n;
326 DEP_LINK_NEXT (back) = NULL;
327 DEP_LINK_PREV_NEXTP (back) = NULL;
328
329 DEP_LINK_NODE (forw) = n;
330 DEP_LINK_NEXT (forw) = NULL;
331 DEP_LINK_PREV_NEXTP (forw) = NULL;
332
333 ++dn_pool_diff;
334
335 return n;
336}
337
338/* Delete dep_node N. N must not be connected to any deps_list. */
339static void
340delete_dep_node (dep_node_t n)
341{
342 gcc_assert (dep_link_is_detached_p (DEP_NODE_BACK (n))
343 && dep_link_is_detached_p (DEP_NODE_FORW (n)));
344
345 XDELETE (DEP_REPLACE (DEP_NODE_DEP (n)));
346
347 --dn_pool_diff;
348
349 dn_pool->remove (n);
350}
351
352/* Pool to hold dependencies lists (deps_list_t). */
353static object_allocator<_deps_list> *dl_pool;
354
355/* Number of deps_lists out there. */
356static int dl_pool_diff = 0;
357
358/* Functions to operate with dependences lists - deps_list_t. */
359
360/* Return true if list L is empty. */
361static bool
362deps_list_empty_p (deps_list_t l)
363{
364 return DEPS_LIST_N_LINKS (l) == 0;
365}
366
367/* Create a new deps_list. */
368static deps_list_t
369create_deps_list (void)
370{
371 deps_list_t l = dl_pool->allocate ();
372
373 DEPS_LIST_FIRST (l) = NULL;
374 DEPS_LIST_N_LINKS (l) = 0;
375
376 ++dl_pool_diff;
377 return l;
378}
379
380/* Free deps_list L. */
381static void
382free_deps_list (deps_list_t l)
383{
384 gcc_assert (deps_list_empty_p (l));
385
386 --dl_pool_diff;
387
388 dl_pool->remove (l);
389}
390
391/* Return true if there is no dep_nodes and deps_lists out there.
392 After the region is scheduled all the dependency nodes and lists
393 should [generally] be returned to pool. */
394bool
395deps_pools_are_empty_p (void)
396{
397 return dn_pool_diff == 0 && dl_pool_diff == 0;
398}
399
400/* Remove all elements from L. */
401static void
402clear_deps_list (deps_list_t l)
403{
404 do
405 {
406 dep_link_t link = DEPS_LIST_FIRST (l);
407
408 if (link == NULL)
409 break;
410
411 remove_from_deps_list (link, l);
412 }
413 while (1);
414}
415
416/* Decide whether a dependency should be treated as a hard or a speculative
417 dependency. */
418static bool
419dep_spec_p (dep_t dep)
420{
421 if (current_sched_info->flags & DO_SPECULATION)
422 {
423 if (DEP_STATUS (dep) & SPECULATIVE)
424 return true;
425 }
426 if (current_sched_info->flags & DO_PREDICATION)
427 {
428 if (DEP_TYPE (dep) == REG_DEP_CONTROL)
429 return true;
430 }
431 if (DEP_REPLACE (dep) != NULL)
432 return true;
433 return false;
434}
435
436static regset reg_pending_sets;
437static regset reg_pending_clobbers;
438static regset reg_pending_uses;
439static regset reg_pending_control_uses;
440static enum reg_pending_barrier_mode reg_pending_barrier;
441
442/* Hard registers implicitly clobbered or used (or may be implicitly
443 clobbered or used) by the currently analyzed insn. For example,
444 insn in its constraint has one register class. Even if there is
445 currently no hard register in the insn, the particular hard
446 register will be in the insn after reload pass because the
447 constraint requires it. */
448static HARD_REG_SET implicit_reg_pending_clobbers;
449static HARD_REG_SET implicit_reg_pending_uses;
450
451/* To speed up the test for duplicate dependency links we keep a
452 record of dependencies created by add_dependence when the average
453 number of instructions in a basic block is very large.
454
455 Studies have shown that there is typically around 5 instructions between
456 branches for typical C code. So we can make a guess that the average
457 basic block is approximately 5 instructions long; we will choose 100X
458 the average size as a very large basic block.
459
460 Each insn has associated bitmaps for its dependencies. Each bitmap
461 has enough entries to represent a dependency on any other insn in
462 the insn chain. All bitmap for true dependencies cache is
463 allocated then the rest two ones are also allocated. */
464static bitmap_head *true_dependency_cache = NULL;
465static bitmap_head *output_dependency_cache = NULL;
466static bitmap_head *anti_dependency_cache = NULL;
467static bitmap_head *control_dependency_cache = NULL;
468static bitmap_head *spec_dependency_cache = NULL;
469static int cache_size;
470
471/* True if we should mark added dependencies as a non-register deps. */
472static bool mark_as_hard;
473
474static int deps_may_trap_p (const_rtx);
475static void add_dependence_1 (rtx_insn *, rtx_insn *, enum reg_note);
476static void add_dependence_list (rtx_insn *, rtx_insn_list *, int,
477 enum reg_note, bool);
478static void add_dependence_list_and_free (struct deps_desc *, rtx_insn *,
479 rtx_insn_list **, int, enum reg_note,
480 bool);
481static void delete_all_dependences (rtx_insn *);
482static void chain_to_prev_insn (rtx_insn *);
483
484static void flush_pending_lists (struct deps_desc *, rtx_insn *, int, int);
485static void sched_analyze_1 (struct deps_desc *, rtx, rtx_insn *);
486static void sched_analyze_2 (struct deps_desc *, rtx, rtx_insn *);
487static void sched_analyze_insn (struct deps_desc *, rtx, rtx_insn *);
488
489static bool sched_has_condition_p (const rtx_insn *);
490static int conditions_mutex_p (const_rtx, const_rtx, bool, bool);
491
492static enum DEPS_ADJUST_RESULT maybe_add_or_update_dep_1 (dep_t, bool,
493 rtx, rtx);
494static enum DEPS_ADJUST_RESULT add_or_update_dep_1 (dep_t, bool, rtx, rtx);
495
496static void check_dep (dep_t, bool);
497
498
499/* Return nonzero if a load of the memory reference MEM can cause a trap. */
500
501static int
502deps_may_trap_p (const_rtx mem)
503{
504 const_rtx addr = XEXP (mem, 0);
505
506 if (REG_P (addr) && REGNO (addr) >= FIRST_PSEUDO_REGISTER)
507 {
508 const_rtx t = get_reg_known_value (REGNO (addr));
509 if (t)
510 addr = t;
511 }
512 return rtx_addr_can_trap_p (addr);
513}
514
515
516/* Find the condition under which INSN is executed. If REV is not NULL,
517 it is set to TRUE when the returned comparison should be reversed
518 to get the actual condition. */
519static rtx
520sched_get_condition_with_rev_uncached (const rtx_insn *insn, bool *rev)
521{
522 rtx pat = PATTERN (insn);
523 rtx src;
524
525 if (rev)
526 *rev = false;
527
528 if (GET_CODE (pat) == COND_EXEC)
529 return COND_EXEC_TEST (pat);
530
531 if (!any_condjump_p (insn) || !onlyjump_p (insn))
532 return 0;
533
534 src = SET_SRC (pc_set (insn));
535
536 if (XEXP (src, 2) == pc_rtx)
537 return XEXP (src, 0);
538 else if (XEXP (src, 1) == pc_rtx)
539 {
540 rtx cond = XEXP (src, 0);
541 enum rtx_code revcode = reversed_comparison_code (cond, insn);
542
543 if (revcode == UNKNOWN)
544 return 0;
545
546 if (rev)
547 *rev = true;
548 return cond;
549 }
550
551 return 0;
552}
553
554/* Return the condition under which INSN does not execute (i.e. the
555 not-taken condition for a conditional branch), or NULL if we cannot
556 find such a condition. The caller should make a copy of the condition
557 before using it. */
558rtx
559sched_get_reverse_condition_uncached (const rtx_insn *insn)
560{
561 bool rev;
562 rtx cond = sched_get_condition_with_rev_uncached (insn, &rev);
563 if (cond == NULL_RTX)
564 return cond;
565 if (!rev)
566 {
567 enum rtx_code revcode = reversed_comparison_code (cond, insn);
568 cond = gen_rtx_fmt_ee (revcode, GET_MODE (cond),
569 XEXP (cond, 0),
570 XEXP (cond, 1));
571 }
572 return cond;
573}
574
575/* Caching variant of sched_get_condition_with_rev_uncached.
576 We only do actual work the first time we come here for an insn; the
577 results are cached in INSN_CACHED_COND and INSN_REVERSE_COND. */
578static rtx
579sched_get_condition_with_rev (const rtx_insn *insn, bool *rev)
580{
581 bool tmp;
582
583 if (INSN_LUID (insn) == 0)
584 return sched_get_condition_with_rev_uncached (insn, rev);
585
586 if (INSN_CACHED_COND (insn) == const_true_rtx)
587 return NULL_RTX;
588
589 if (INSN_CACHED_COND (insn) != NULL_RTX)
590 {
591 if (rev)
592 *rev = INSN_REVERSE_COND (insn);
593 return INSN_CACHED_COND (insn);
594 }
595
596 INSN_CACHED_COND (insn) = sched_get_condition_with_rev_uncached (insn, &tmp);
597 INSN_REVERSE_COND (insn) = tmp;
598
599 if (INSN_CACHED_COND (insn) == NULL_RTX)
600 {
601 INSN_CACHED_COND (insn) = const_true_rtx;
602 return NULL_RTX;
603 }
604
605 if (rev)
606 *rev = INSN_REVERSE_COND (insn);
607 return INSN_CACHED_COND (insn);
608}
609
610/* True when we can find a condition under which INSN is executed. */
611static bool
612sched_has_condition_p (const rtx_insn *insn)
613{
614 return !! sched_get_condition_with_rev (insn, NULL);
615}
616
617
618
619/* Return nonzero if conditions COND1 and COND2 can never be both true. */
620static int
621conditions_mutex_p (const_rtx cond1, const_rtx cond2, bool rev1, bool rev2)
622{
623 if (COMPARISON_P (cond1)
624 && COMPARISON_P (cond2)
625 && GET_CODE (cond1) ==
626 (rev1==rev2
627 ? reversed_comparison_code (cond2, NULL)
628 : GET_CODE (cond2))
629 && rtx_equal_p (XEXP (cond1, 0), XEXP (cond2, 0))
630 && XEXP (cond1, 1) == XEXP (cond2, 1))
631 return 1;
632 return 0;
633}
634
635/* Return true if insn1 and insn2 can never depend on one another because
636 the conditions under which they are executed are mutually exclusive. */
637bool
638sched_insns_conditions_mutex_p (const rtx_insn *insn1, const rtx_insn *insn2)
639{
640 rtx cond1, cond2;
641 bool rev1 = false, rev2 = false;
642
643 /* df doesn't handle conditional lifetimes entirely correctly;
644 calls mess up the conditional lifetimes. */
645 if (!CALL_P (insn1) && !CALL_P (insn2))
646 {
647 cond1 = sched_get_condition_with_rev (insn1, &rev1);
648 cond2 = sched_get_condition_with_rev (insn2, &rev2);
649 if (cond1 && cond2
650 && conditions_mutex_p (cond1, cond2, rev1, rev2)
651 /* Make sure first instruction doesn't affect condition of second
652 instruction if switched. */
653 && !modified_in_p (cond1, insn2)
654 /* Make sure second instruction doesn't affect condition of first
655 instruction if switched. */
656 && !modified_in_p (cond2, insn1))
657 return true;
658 }
659 return false;
660}
661
662
663/* Return true if INSN can potentially be speculated with type DS. */
664bool
665sched_insn_is_legitimate_for_speculation_p (const rtx_insn *insn, ds_t ds)
666{
667 if (HAS_INTERNAL_DEP (insn))
668 return false;
669
670 if (!NONJUMP_INSN_P (insn))
671 return false;
672
673 if (SCHED_GROUP_P (insn))
674 return false;
675
676 if (IS_SPECULATION_CHECK_P (CONST_CAST_RTX_INSN (insn)))
677 return false;
678
679 if (side_effects_p (PATTERN (insn)))
680 return false;
681
682 if (ds & BE_IN_SPEC)
683 /* The following instructions, which depend on a speculatively scheduled
684 instruction, cannot be speculatively scheduled along. */
685 {
686 if (may_trap_or_fault_p (PATTERN (insn)))
687 /* If instruction might fault, it cannot be speculatively scheduled.
688 For control speculation it's obvious why and for data speculation
689 it's because the insn might get wrong input if speculation
690 wasn't successful. */
691 return false;
692
693 if ((ds & BE_IN_DATA)
694 && sched_has_condition_p (insn))
695 /* If this is a predicated instruction, then it cannot be
696 speculatively scheduled. See PR35659. */
697 return false;
698 }
699
700 return true;
701}
702
703/* Initialize LIST_PTR to point to one of the lists present in TYPES_PTR,
704 initialize RESOLVED_P_PTR with true if that list consists of resolved deps,
705 and remove the type of returned [through LIST_PTR] list from TYPES_PTR.
706 This function is used to switch sd_iterator to the next list.
707 !!! For internal use only. Might consider moving it to sched-int.h. */
708void
709sd_next_list (const_rtx insn, sd_list_types_def *types_ptr,
710 deps_list_t *list_ptr, bool *resolved_p_ptr)
711{
712 sd_list_types_def types = *types_ptr;
713
714 if (types & SD_LIST_HARD_BACK)
715 {
716 *list_ptr = INSN_HARD_BACK_DEPS (insn);
717 *resolved_p_ptr = false;
718 *types_ptr = types & ~SD_LIST_HARD_BACK;
719 }
720 else if (types & SD_LIST_SPEC_BACK)
721 {
722 *list_ptr = INSN_SPEC_BACK_DEPS (insn);
723 *resolved_p_ptr = false;
724 *types_ptr = types & ~SD_LIST_SPEC_BACK;
725 }
726 else if (types & SD_LIST_FORW)
727 {
728 *list_ptr = INSN_FORW_DEPS (insn);
729 *resolved_p_ptr = false;
730 *types_ptr = types & ~SD_LIST_FORW;
731 }
732 else if (types & SD_LIST_RES_BACK)
733 {
734 *list_ptr = INSN_RESOLVED_BACK_DEPS (insn);
735 *resolved_p_ptr = true;
736 *types_ptr = types & ~SD_LIST_RES_BACK;
737 }
738 else if (types & SD_LIST_RES_FORW)
739 {
740 *list_ptr = INSN_RESOLVED_FORW_DEPS (insn);
741 *resolved_p_ptr = true;
742 *types_ptr = types & ~SD_LIST_RES_FORW;
743 }
744 else
745 {
746 *list_ptr = NULL;
747 *resolved_p_ptr = false;
748 *types_ptr = SD_LIST_NONE;
749 }
750}
751
752/* Return the summary size of INSN's lists defined by LIST_TYPES. */
753int
754sd_lists_size (const_rtx insn, sd_list_types_def list_types)
755{
756 int size = 0;
757
758 while (list_types != SD_LIST_NONE)
759 {
760 deps_list_t list;
761 bool resolved_p;
762
763 sd_next_list (insn, &list_types, &list, &resolved_p);
764 if (list)
765 size += DEPS_LIST_N_LINKS (list);
766 }
767
768 return size;
769}
770
771/* Return true if INSN's lists defined by LIST_TYPES are all empty. */
772
773bool
774sd_lists_empty_p (const_rtx insn, sd_list_types_def list_types)
775{
776 while (list_types != SD_LIST_NONE)
777 {
778 deps_list_t list;
779 bool resolved_p;
780
781 sd_next_list (insn, &list_types, &list, &resolved_p);
782 if (!deps_list_empty_p (list))
783 return false;
784 }
785
786 return true;
787}
788
789/* Initialize data for INSN. */
790void
791sd_init_insn (rtx_insn *insn)
792{
793 INSN_HARD_BACK_DEPS (insn) = create_deps_list ();
794 INSN_SPEC_BACK_DEPS (insn) = create_deps_list ();
795 INSN_RESOLVED_BACK_DEPS (insn) = create_deps_list ();
796 INSN_FORW_DEPS (insn) = create_deps_list ();
797 INSN_RESOLVED_FORW_DEPS (insn) = create_deps_list ();
798
799 /* ??? It would be nice to allocate dependency caches here. */
800}
801
802/* Free data for INSN. */
803void
804sd_finish_insn (rtx_insn *insn)
805{
806 /* ??? It would be nice to deallocate dependency caches here. */
807
808 free_deps_list (INSN_HARD_BACK_DEPS (insn));
809 INSN_HARD_BACK_DEPS (insn) = NULL;
810
811 free_deps_list (INSN_SPEC_BACK_DEPS (insn));
812 INSN_SPEC_BACK_DEPS (insn) = NULL;
813
814 free_deps_list (INSN_RESOLVED_BACK_DEPS (insn));
815 INSN_RESOLVED_BACK_DEPS (insn) = NULL;
816
817 free_deps_list (INSN_FORW_DEPS (insn));
818 INSN_FORW_DEPS (insn) = NULL;
819
820 free_deps_list (INSN_RESOLVED_FORW_DEPS (insn));
821 INSN_RESOLVED_FORW_DEPS (insn) = NULL;
822}
823
824/* Find a dependency between producer PRO and consumer CON.
825 Search through resolved dependency lists if RESOLVED_P is true.
826 If no such dependency is found return NULL,
827 otherwise return the dependency and initialize SD_IT_PTR [if it is nonnull]
828 with an iterator pointing to it. */
829static dep_t
830sd_find_dep_between_no_cache (rtx pro, rtx con, bool resolved_p,
831 sd_iterator_def *sd_it_ptr)
832{
833 sd_list_types_def pro_list_type;
834 sd_list_types_def con_list_type;
835 sd_iterator_def sd_it;
836 dep_t dep;
837 bool found_p = false;
838
839 if (resolved_p)
840 {
841 pro_list_type = SD_LIST_RES_FORW;
842 con_list_type = SD_LIST_RES_BACK;
843 }
844 else
845 {
846 pro_list_type = SD_LIST_FORW;
847 con_list_type = SD_LIST_BACK;
848 }
849
850 /* Walk through either back list of INSN or forw list of ELEM
851 depending on which one is shorter. */
852 if (sd_lists_size (con, con_list_type) < sd_lists_size (pro, pro_list_type))
853 {
854 /* Find the dep_link with producer PRO in consumer's back_deps. */
855 FOR_EACH_DEP (con, con_list_type, sd_it, dep)
856 if (DEP_PRO (dep) == pro)
857 {
858 found_p = true;
859 break;
860 }
861 }
862 else
863 {
864 /* Find the dep_link with consumer CON in producer's forw_deps. */
865 FOR_EACH_DEP (pro, pro_list_type, sd_it, dep)
866 if (DEP_CON (dep) == con)
867 {
868 found_p = true;
869 break;
870 }
871 }
872
873 if (found_p)
874 {
875 if (sd_it_ptr != NULL)
876 *sd_it_ptr = sd_it;
877
878 return dep;
879 }
880
881 return NULL;
882}
883
884/* Find a dependency between producer PRO and consumer CON.
885 Use dependency [if available] to check if dependency is present at all.
886 Search through resolved dependency lists if RESOLVED_P is true.
887 If the dependency or NULL if none found. */
888dep_t
889sd_find_dep_between (rtx pro, rtx con, bool resolved_p)
890{
891 if (true_dependency_cache != NULL)
892 /* Avoiding the list walk below can cut compile times dramatically
893 for some code. */
894 {
895 int elem_luid = INSN_LUID (pro);
896 int insn_luid = INSN_LUID (con);
897
898 if (!bitmap_bit_p (&true_dependency_cache[insn_luid], elem_luid)
899 && !bitmap_bit_p (&output_dependency_cache[insn_luid], elem_luid)
900 && !bitmap_bit_p (&anti_dependency_cache[insn_luid], elem_luid)
901 && !bitmap_bit_p (&control_dependency_cache[insn_luid], elem_luid))
902 return NULL;
903 }
904
905 return sd_find_dep_between_no_cache (pro, con, resolved_p, NULL);
906}
907
908/* Add or update a dependence described by DEP.
909 MEM1 and MEM2, if non-null, correspond to memory locations in case of
910 data speculation.
911
912 The function returns a value indicating if an old entry has been changed
913 or a new entry has been added to insn's backward deps.
914
915 This function merely checks if producer and consumer is the same insn
916 and doesn't create a dep in this case. Actual manipulation of
917 dependence data structures is performed in add_or_update_dep_1. */
918static enum DEPS_ADJUST_RESULT
919maybe_add_or_update_dep_1 (dep_t dep, bool resolved_p, rtx mem1, rtx mem2)
920{
921 rtx_insn *elem = DEP_PRO (dep);
922 rtx_insn *insn = DEP_CON (dep);
923
924 gcc_assert (INSN_P (insn) && INSN_P (elem));
925
926 /* Don't depend an insn on itself. */
927 if (insn == elem)
928 {
929 if (sched_deps_info->generate_spec_deps)
930 /* INSN has an internal dependence, which we can't overcome. */
931 HAS_INTERNAL_DEP (insn) = 1;
932
933 return DEP_NODEP;
934 }
935
936 return add_or_update_dep_1 (dep, resolved_p, mem1, mem2);
937}
938
939/* Ask dependency caches what needs to be done for dependence DEP.
940 Return DEP_CREATED if new dependence should be created and there is no
941 need to try to find one searching the dependencies lists.
942 Return DEP_PRESENT if there already is a dependence described by DEP and
943 hence nothing is to be done.
944 Return DEP_CHANGED if there already is a dependence, but it should be
945 updated to incorporate additional information from DEP. */
946static enum DEPS_ADJUST_RESULT
947ask_dependency_caches (dep_t dep)
948{
949 int elem_luid = INSN_LUID (DEP_PRO (dep));
950 int insn_luid = INSN_LUID (DEP_CON (dep));
951
952 gcc_assert (true_dependency_cache != NULL
953 && output_dependency_cache != NULL
954 && anti_dependency_cache != NULL
955 && control_dependency_cache != NULL);
956
957 if (!(current_sched_info->flags & USE_DEPS_LIST))
958 {
959 enum reg_note present_dep_type;
960
961 if (bitmap_bit_p (&true_dependency_cache[insn_luid], elem_luid))
962 present_dep_type = REG_DEP_TRUE;
963 else if (bitmap_bit_p (&output_dependency_cache[insn_luid], elem_luid))
964 present_dep_type = REG_DEP_OUTPUT;
965 else if (bitmap_bit_p (&anti_dependency_cache[insn_luid], elem_luid))
966 present_dep_type = REG_DEP_ANTI;
967 else if (bitmap_bit_p (&control_dependency_cache[insn_luid], elem_luid))
968 present_dep_type = REG_DEP_CONTROL;
969 else
970 /* There is no existing dep so it should be created. */
971 return DEP_CREATED;
972
973 if ((int) DEP_TYPE (dep) >= (int) present_dep_type)
974 /* DEP does not add anything to the existing dependence. */
975 return DEP_PRESENT;
976 }
977 else
978 {
979 ds_t present_dep_types = 0;
980
981 if (bitmap_bit_p (&true_dependency_cache[insn_luid], elem_luid))
982 present_dep_types |= DEP_TRUE;
983 if (bitmap_bit_p (&output_dependency_cache[insn_luid], elem_luid))
984 present_dep_types |= DEP_OUTPUT;
985 if (bitmap_bit_p (&anti_dependency_cache[insn_luid], elem_luid))
986 present_dep_types |= DEP_ANTI;
987 if (bitmap_bit_p (&control_dependency_cache[insn_luid], elem_luid))
988 present_dep_types |= DEP_CONTROL;
989
990 if (present_dep_types == 0)
991 /* There is no existing dep so it should be created. */
992 return DEP_CREATED;
993
994 if (!(current_sched_info->flags & DO_SPECULATION)
995 || !bitmap_bit_p (&spec_dependency_cache[insn_luid], elem_luid))
996 {
997 if ((present_dep_types | (DEP_STATUS (dep) & DEP_TYPES))
998 == present_dep_types)
999 /* DEP does not add anything to the existing dependence. */
1000 return DEP_PRESENT;
1001 }
1002 else
1003 {
1004 /* Only true dependencies can be data speculative and
1005 only anti dependencies can be control speculative. */
1006 gcc_assert ((present_dep_types & (DEP_TRUE | DEP_ANTI))
1007 == present_dep_types);
1008
1009 /* if (DEP is SPECULATIVE) then
1010 ..we should update DEP_STATUS
1011 else
1012 ..we should reset existing dep to non-speculative. */
1013 }
1014 }
1015
1016 return DEP_CHANGED;
1017}
1018
1019/* Set dependency caches according to DEP. */
1020static void
1021set_dependency_caches (dep_t dep)
1022{
1023 int elem_luid = INSN_LUID (DEP_PRO (dep));
1024 int insn_luid = INSN_LUID (DEP_CON (dep));
1025
1026 if (!(current_sched_info->flags & USE_DEPS_LIST))
1027 {
1028 switch (DEP_TYPE (dep))
1029 {
1030 case REG_DEP_TRUE:
1031 bitmap_set_bit (&true_dependency_cache[insn_luid], elem_luid);
1032 break;
1033
1034 case REG_DEP_OUTPUT:
1035 bitmap_set_bit (&output_dependency_cache[insn_luid], elem_luid);
1036 break;
1037
1038 case REG_DEP_ANTI:
1039 bitmap_set_bit (&anti_dependency_cache[insn_luid], elem_luid);
1040 break;
1041
1042 case REG_DEP_CONTROL:
1043 bitmap_set_bit (&control_dependency_cache[insn_luid], elem_luid);
1044 break;
1045
1046 default:
1047 gcc_unreachable ();
1048 }
1049 }
1050 else
1051 {
1052 ds_t ds = DEP_STATUS (dep);
1053
1054 if (ds & DEP_TRUE)
1055 bitmap_set_bit (&true_dependency_cache[insn_luid], elem_luid);
1056 if (ds & DEP_OUTPUT)
1057 bitmap_set_bit (&output_dependency_cache[insn_luid], elem_luid);
1058 if (ds & DEP_ANTI)
1059 bitmap_set_bit (&anti_dependency_cache[insn_luid], elem_luid);
1060 if (ds & DEP_CONTROL)
1061 bitmap_set_bit (&control_dependency_cache[insn_luid], elem_luid);
1062
1063 if (ds & SPECULATIVE)
1064 {
1065 gcc_assert (current_sched_info->flags & DO_SPECULATION);
1066 bitmap_set_bit (&spec_dependency_cache[insn_luid], elem_luid);
1067 }
1068 }
1069}
1070
1071/* Type of dependence DEP have changed from OLD_TYPE. Update dependency
1072 caches accordingly. */
1073static void
1074update_dependency_caches (dep_t dep, enum reg_note old_type)
1075{
1076 int elem_luid = INSN_LUID (DEP_PRO (dep));
1077 int insn_luid = INSN_LUID (DEP_CON (dep));
1078
1079 /* Clear corresponding cache entry because type of the link
1080 may have changed. Keep them if we use_deps_list. */
1081 if (!(current_sched_info->flags & USE_DEPS_LIST))
1082 {
1083 switch (old_type)
1084 {
1085 case REG_DEP_OUTPUT:
1086 bitmap_clear_bit (&output_dependency_cache[insn_luid], elem_luid);
1087 break;
1088
1089 case REG_DEP_ANTI:
1090 bitmap_clear_bit (&anti_dependency_cache[insn_luid], elem_luid);
1091 break;
1092
1093 case REG_DEP_CONTROL:
1094 bitmap_clear_bit (&control_dependency_cache[insn_luid], elem_luid);
1095 break;
1096
1097 default:
1098 gcc_unreachable ();
1099 }
1100 }
1101
1102 set_dependency_caches (dep);
1103}
1104
1105/* Convert a dependence pointed to by SD_IT to be non-speculative. */
1106static void
1107change_spec_dep_to_hard (sd_iterator_def sd_it)
1108{
1109 dep_node_t node = DEP_LINK_NODE (*sd_it.linkp);
1110 dep_link_t link = DEP_NODE_BACK (node);
1111 dep_t dep = DEP_NODE_DEP (node);
1112 rtx_insn *elem = DEP_PRO (dep);
1113 rtx_insn *insn = DEP_CON (dep);
1114
1115 move_dep_link (link, INSN_SPEC_BACK_DEPS (insn), INSN_HARD_BACK_DEPS (insn));
1116
1117 DEP_STATUS (dep) &= ~SPECULATIVE;
1118
1119 if (true_dependency_cache != NULL)
1120 /* Clear the cache entry. */
1121 bitmap_clear_bit (&spec_dependency_cache[INSN_LUID (insn)],
1122 INSN_LUID (elem));
1123}
1124
1125/* Update DEP to incorporate information from NEW_DEP.
1126 SD_IT points to DEP in case it should be moved to another list.
1127 MEM1 and MEM2, if nonnull, correspond to memory locations in case if
1128 data-speculative dependence should be updated. */
1129static enum DEPS_ADJUST_RESULT
1130update_dep (dep_t dep, dep_t new_dep,
1131 sd_iterator_def sd_it ATTRIBUTE_UNUSED,
1132 rtx mem1 ATTRIBUTE_UNUSED,
1133 rtx mem2 ATTRIBUTE_UNUSED)
1134{
1135 enum DEPS_ADJUST_RESULT res = DEP_PRESENT;
1136 enum reg_note old_type = DEP_TYPE (dep);
1137 bool was_spec = dep_spec_p (dep);
1138
1139 DEP_NONREG (dep) |= DEP_NONREG (new_dep);
1140 DEP_MULTIPLE (dep) = 1;
1141
1142 /* If this is a more restrictive type of dependence than the
1143 existing one, then change the existing dependence to this
1144 type. */
1145 if ((int) DEP_TYPE (new_dep) < (int) old_type)
1146 {
1147 DEP_TYPE (dep) = DEP_TYPE (new_dep);
1148 res = DEP_CHANGED;
1149 }
1150
1151 if (current_sched_info->flags & USE_DEPS_LIST)
1152 /* Update DEP_STATUS. */
1153 {
1154 ds_t dep_status = DEP_STATUS (dep);
1155 ds_t ds = DEP_STATUS (new_dep);
1156 ds_t new_status = ds | dep_status;
1157
1158 if (new_status & SPECULATIVE)
1159 {
1160 /* Either existing dep or a dep we're adding or both are
1161 speculative. */
1162 if (!(ds & SPECULATIVE)
1163 || !(dep_status & SPECULATIVE))
1164 /* The new dep can't be speculative. */
1165 new_status &= ~SPECULATIVE;
1166 else
1167 {
1168 /* Both are speculative. Merge probabilities. */
1169 if (mem1 != NULL)
1170 {
1171 dw_t dw;
1172
1173 dw = estimate_dep_weak (mem1, mem2);
1174 ds = set_dep_weak (ds, BEGIN_DATA, dw);
1175 }
1176
1177 new_status = ds_merge (dep_status, ds);
1178 }
1179 }
1180
1181 ds = new_status;
1182
1183 if (dep_status != ds)
1184 {
1185 DEP_STATUS (dep) = ds;
1186 res = DEP_CHANGED;
1187 }
1188 }
1189
1190 if (was_spec && !dep_spec_p (dep))
1191 /* The old dep was speculative, but now it isn't. */
1192 change_spec_dep_to_hard (sd_it);
1193
1194 if (true_dependency_cache != NULL
1195 && res == DEP_CHANGED)
1196 update_dependency_caches (dep, old_type);
1197
1198 return res;
1199}
1200
1201/* Add or update a dependence described by DEP.
1202 MEM1 and MEM2, if non-null, correspond to memory locations in case of
1203 data speculation.
1204
1205 The function returns a value indicating if an old entry has been changed
1206 or a new entry has been added to insn's backward deps or nothing has
1207 been updated at all. */
1208static enum DEPS_ADJUST_RESULT
1209add_or_update_dep_1 (dep_t new_dep, bool resolved_p,
1210 rtx mem1 ATTRIBUTE_UNUSED, rtx mem2 ATTRIBUTE_UNUSED)
1211{
1212 bool maybe_present_p = true;
1213 bool present_p = false;
1214
1215 gcc_assert (INSN_P (DEP_PRO (new_dep)) && INSN_P (DEP_CON (new_dep))
1216 && DEP_PRO (new_dep) != DEP_CON (new_dep));
1217
1218 if (flag_checking)
1219 check_dep (new_dep, mem1 != NULL);
1220
1221 if (true_dependency_cache != NULL)
1222 {
1223 switch (ask_dependency_caches (new_dep))
1224 {
1225 case DEP_PRESENT:
1226 dep_t present_dep;
1227 sd_iterator_def sd_it;
1228
1229 present_dep = sd_find_dep_between_no_cache (DEP_PRO (new_dep),
1230 DEP_CON (new_dep),
1231 resolved_p, &sd_it);
1232 DEP_MULTIPLE (present_dep) = 1;
1233 return DEP_PRESENT;
1234
1235 case DEP_CHANGED:
1236 maybe_present_p = true;
1237 present_p = true;
1238 break;
1239
1240 case DEP_CREATED:
1241 maybe_present_p = false;
1242 present_p = false;
1243 break;
1244
1245 default:
1246 gcc_unreachable ();
1247 break;
1248 }
1249 }
1250
1251 /* Check that we don't already have this dependence. */
1252 if (maybe_present_p)
1253 {
1254 dep_t present_dep;
1255 sd_iterator_def sd_it;
1256
1257 gcc_assert (true_dependency_cache == NULL || present_p);
1258
1259 present_dep = sd_find_dep_between_no_cache (DEP_PRO (new_dep),
1260 DEP_CON (new_dep),
1261 resolved_p, &sd_it);
1262
1263 if (present_dep != NULL)
1264 /* We found an existing dependency between ELEM and INSN. */
1265 return update_dep (present_dep, new_dep, sd_it, mem1, mem2);
1266 else
1267 /* We didn't find a dep, it shouldn't present in the cache. */
1268 gcc_assert (!present_p);
1269 }
1270
1271 /* Might want to check one level of transitivity to save conses.
1272 This check should be done in maybe_add_or_update_dep_1.
1273 Since we made it to add_or_update_dep_1, we must create
1274 (or update) a link. */
1275
1276 if (mem1 != NULL_RTX)
1277 {
1278 gcc_assert (sched_deps_info->generate_spec_deps);
1279 DEP_STATUS (new_dep) = set_dep_weak (DEP_STATUS (new_dep), BEGIN_DATA,
1280 estimate_dep_weak (mem1, mem2));
1281 }
1282
1283 sd_add_dep (new_dep, resolved_p);
1284
1285 return DEP_CREATED;
1286}
1287
1288/* Initialize BACK_LIST_PTR with consumer's backward list and
1289 FORW_LIST_PTR with producer's forward list. If RESOLVED_P is true
1290 initialize with lists that hold resolved deps. */
1291static void
1292get_back_and_forw_lists (dep_t dep, bool resolved_p,
1293 deps_list_t *back_list_ptr,
1294 deps_list_t *forw_list_ptr)
1295{
1296 rtx_insn *con = DEP_CON (dep);
1297
1298 if (!resolved_p)
1299 {
1300 if (dep_spec_p (dep))
1301 *back_list_ptr = INSN_SPEC_BACK_DEPS (con);
1302 else
1303 *back_list_ptr = INSN_HARD_BACK_DEPS (con);
1304
1305 *forw_list_ptr = INSN_FORW_DEPS (DEP_PRO (dep));
1306 }
1307 else
1308 {
1309 *back_list_ptr = INSN_RESOLVED_BACK_DEPS (con);
1310 *forw_list_ptr = INSN_RESOLVED_FORW_DEPS (DEP_PRO (dep));
1311 }
1312}
1313
1314/* Add dependence described by DEP.
1315 If RESOLVED_P is true treat the dependence as a resolved one. */
1316void
1317sd_add_dep (dep_t dep, bool resolved_p)
1318{
1319 dep_node_t n = create_dep_node ();
1320 deps_list_t con_back_deps;
1321 deps_list_t pro_forw_deps;
1322 rtx_insn *elem = DEP_PRO (dep);
1323 rtx_insn *insn = DEP_CON (dep);
1324
1325 gcc_assert (INSN_P (insn) && INSN_P (elem) && insn != elem);
1326
1327 if ((current_sched_info->flags & DO_SPECULATION) == 0
1328 || !sched_insn_is_legitimate_for_speculation_p (insn, DEP_STATUS (dep)))
1329 DEP_STATUS (dep) &= ~SPECULATIVE;
1330
1331 copy_dep (DEP_NODE_DEP (n), dep);
1332
1333 get_back_and_forw_lists (dep, resolved_p, &con_back_deps, &pro_forw_deps);
1334
1335 add_to_deps_list (DEP_NODE_BACK (n), con_back_deps);
1336
1337 if (flag_checking)
1338 check_dep (dep, false);
1339
1340 add_to_deps_list (DEP_NODE_FORW (n), pro_forw_deps);
1341
1342 /* If we are adding a dependency to INSN's LOG_LINKs, then note that
1343 in the bitmap caches of dependency information. */
1344 if (true_dependency_cache != NULL)
1345 set_dependency_caches (dep);
1346}
1347
1348/* Add or update backward dependence between INSN and ELEM
1349 with given type DEP_TYPE and dep_status DS.
1350 This function is a convenience wrapper. */
1351enum DEPS_ADJUST_RESULT
1352sd_add_or_update_dep (dep_t dep, bool resolved_p)
1353{
1354 return add_or_update_dep_1 (dep, resolved_p, NULL_RTX, NULL_RTX);
1355}
1356
1357/* Resolved dependence pointed to by SD_IT.
1358 SD_IT will advance to the next element. */
1359void
1360sd_resolve_dep (sd_iterator_def sd_it)
1361{
1362 dep_node_t node = DEP_LINK_NODE (*sd_it.linkp);
1363 dep_t dep = DEP_NODE_DEP (node);
1364 rtx_insn *pro = DEP_PRO (dep);
1365 rtx_insn *con = DEP_CON (dep);
1366
1367 if (dep_spec_p (dep))
1368 move_dep_link (DEP_NODE_BACK (node), INSN_SPEC_BACK_DEPS (con),
1369 INSN_RESOLVED_BACK_DEPS (con));
1370 else
1371 move_dep_link (DEP_NODE_BACK (node), INSN_HARD_BACK_DEPS (con),
1372 INSN_RESOLVED_BACK_DEPS (con));
1373
1374 move_dep_link (DEP_NODE_FORW (node), INSN_FORW_DEPS (pro),
1375 INSN_RESOLVED_FORW_DEPS (pro));
1376}
1377
1378/* Perform the inverse operation of sd_resolve_dep. Restore the dependence
1379 pointed to by SD_IT to unresolved state. */
1380void
1381sd_unresolve_dep (sd_iterator_def sd_it)
1382{
1383 dep_node_t node = DEP_LINK_NODE (*sd_it.linkp);
1384 dep_t dep = DEP_NODE_DEP (node);
1385 rtx_insn *pro = DEP_PRO (dep);
1386 rtx_insn *con = DEP_CON (dep);
1387
1388 if (dep_spec_p (dep))
1389 move_dep_link (DEP_NODE_BACK (node), INSN_RESOLVED_BACK_DEPS (con),
1390 INSN_SPEC_BACK_DEPS (con));
1391 else
1392 move_dep_link (DEP_NODE_BACK (node), INSN_RESOLVED_BACK_DEPS (con),
1393 INSN_HARD_BACK_DEPS (con));
1394
1395 move_dep_link (DEP_NODE_FORW (node), INSN_RESOLVED_FORW_DEPS (pro),
1396 INSN_FORW_DEPS (pro));
1397}
1398
1399/* Make TO depend on all the FROM's producers.
1400 If RESOLVED_P is true add dependencies to the resolved lists. */
1401void
1402sd_copy_back_deps (rtx_insn *to, rtx_insn *from, bool resolved_p)
1403{
1404 sd_list_types_def list_type;
1405 sd_iterator_def sd_it;
1406 dep_t dep;
1407
1408 list_type = resolved_p ? SD_LIST_RES_BACK : SD_LIST_BACK;
1409
1410 FOR_EACH_DEP (from, list_type, sd_it, dep)
1411 {
1412 dep_def _new_dep, *new_dep = &_new_dep;
1413
1414 copy_dep (new_dep, dep);
1415 DEP_CON (new_dep) = to;
1416 sd_add_dep (new_dep, resolved_p);
1417 }
1418}
1419
1420/* Remove a dependency referred to by SD_IT.
1421 SD_IT will point to the next dependence after removal. */
1422void
1423sd_delete_dep (sd_iterator_def sd_it)
1424{
1425 dep_node_t n = DEP_LINK_NODE (*sd_it.linkp);
1426 dep_t dep = DEP_NODE_DEP (n);
1427 rtx_insn *pro = DEP_PRO (dep);
1428 rtx_insn *con = DEP_CON (dep);
1429 deps_list_t con_back_deps;
1430 deps_list_t pro_forw_deps;
1431
1432 if (true_dependency_cache != NULL)
1433 {
1434 int elem_luid = INSN_LUID (pro);
1435 int insn_luid = INSN_LUID (con);
1436
1437 bitmap_clear_bit (&true_dependency_cache[insn_luid], elem_luid);
1438 bitmap_clear_bit (&anti_dependency_cache[insn_luid], elem_luid);
1439 bitmap_clear_bit (&control_dependency_cache[insn_luid], elem_luid);
1440 bitmap_clear_bit (&output_dependency_cache[insn_luid], elem_luid);
1441
1442 if (current_sched_info->flags & DO_SPECULATION)
1443 bitmap_clear_bit (&spec_dependency_cache[insn_luid], elem_luid);
1444 }
1445
1446 get_back_and_forw_lists (dep, sd_it.resolved_p,
1447 &con_back_deps, &pro_forw_deps);
1448
1449 remove_from_deps_list (DEP_NODE_BACK (n), con_back_deps);
1450 remove_from_deps_list (DEP_NODE_FORW (n), pro_forw_deps);
1451
1452 delete_dep_node (n);
1453}
1454
1455/* Dump size of the lists. */
1456#define DUMP_LISTS_SIZE (2)
1457
1458/* Dump dependencies of the lists. */
1459#define DUMP_LISTS_DEPS (4)
1460
1461/* Dump all information about the lists. */
1462#define DUMP_LISTS_ALL (DUMP_LISTS_SIZE | DUMP_LISTS_DEPS)
1463
1464/* Dump deps_lists of INSN specified by TYPES to DUMP.
1465 FLAGS is a bit mask specifying what information about the lists needs
1466 to be printed.
1467 If FLAGS has the very first bit set, then dump all information about
1468 the lists and propagate this bit into the callee dump functions. */
1469static void
1470dump_lists (FILE *dump, rtx insn, sd_list_types_def types, int flags)
1471{
1472 sd_iterator_def sd_it;
1473 dep_t dep;
1474 int all;
1475
1476 all = (flags & 1);
1477
1478 if (all)
1479 flags |= DUMP_LISTS_ALL;
1480
1481 fprintf (dump, "[");
1482
1483 if (flags & DUMP_LISTS_SIZE)
1484 fprintf (dump, "%d; ", sd_lists_size (insn, types));
1485
1486 if (flags & DUMP_LISTS_DEPS)
1487 {
1488 FOR_EACH_DEP (insn, types, sd_it, dep)
1489 {
1490 dump_dep (dump, dep, dump_dep_flags | all);
1491 fprintf (dump, " ");
1492 }
1493 }
1494}
1495
1496/* Dump all information about deps_lists of INSN specified by TYPES
1497 to STDERR. */
1498void
1499sd_debug_lists (rtx insn, sd_list_types_def types)
1500{
1501 dump_lists (stderr, insn, types, 1);
1502 fprintf (stderr, "\n");
1503}
1504
1505/* A wrapper around add_dependence_1, to add a dependence of CON on
1506 PRO, with type DEP_TYPE. This function implements special handling
1507 for REG_DEP_CONTROL dependencies. For these, we optionally promote
1508 the type to REG_DEP_ANTI if we can determine that predication is
1509 impossible; otherwise we add additional true dependencies on the
1510 INSN_COND_DEPS list of the jump (which PRO must be). */
1511void
1512add_dependence (rtx_insn *con, rtx_insn *pro, enum reg_note dep_type)
1513{
1514 if (dep_type == REG_DEP_CONTROL
1515 && !(current_sched_info->flags & DO_PREDICATION))
1516 dep_type = REG_DEP_ANTI;
1517
1518 /* A REG_DEP_CONTROL dependence may be eliminated through predication,
1519 so we must also make the insn dependent on the setter of the
1520 condition. */
1521 if (dep_type == REG_DEP_CONTROL)
1522 {
1523 rtx_insn *real_pro = pro;
1524 rtx_insn *other = real_insn_for_shadow (real_pro);
1525 rtx cond;
1526
1527 if (other != NULL_RTX)
1528 real_pro = other;
1529 cond = sched_get_reverse_condition_uncached (real_pro);
1530 /* Verify that the insn does not use a different value in
1531 the condition register than the one that was present at
1532 the jump. */
1533 if (cond == NULL_RTX)
1534 dep_type = REG_DEP_ANTI;
1535 else if (INSN_CACHED_COND (real_pro) == const_true_rtx)
1536 {
1537 HARD_REG_SET uses;
1538 CLEAR_HARD_REG_SET (uses);
1539 note_uses (&PATTERN (con), record_hard_reg_uses, &uses);
1540 if (TEST_HARD_REG_BIT (uses, REGNO (XEXP (cond, 0))))
1541 dep_type = REG_DEP_ANTI;
1542 }
1543 if (dep_type == REG_DEP_CONTROL)
1544 {
1545 if (sched_verbose >= 5)
1546 fprintf (sched_dump, "making DEP_CONTROL for %d\n",
1547 INSN_UID (real_pro));
1548 add_dependence_list (con, INSN_COND_DEPS (real_pro), 0,
1549 REG_DEP_TRUE, false);
1550 }
1551 }
1552
1553 add_dependence_1 (con, pro, dep_type);
1554}
1555
1556/* A convenience wrapper to operate on an entire list. HARD should be
1557 true if DEP_NONREG should be set on newly created dependencies. */
1558
1559static void
1560add_dependence_list (rtx_insn *insn, rtx_insn_list *list, int uncond,
1561 enum reg_note dep_type, bool hard)
1562{
1563 mark_as_hard = hard;
1564 for (; list; list = list->next ())
1565 {
1566 if (uncond || ! sched_insns_conditions_mutex_p (insn, list->insn ()))
1567 add_dependence (insn, list->insn (), dep_type);
1568 }
1569 mark_as_hard = false;
1570}
1571
1572/* Similar, but free *LISTP at the same time, when the context
1573 is not readonly. HARD should be true if DEP_NONREG should be set on
1574 newly created dependencies. */
1575
1576static void
1577add_dependence_list_and_free (struct deps_desc *deps, rtx_insn *insn,
1578 rtx_insn_list **listp,
1579 int uncond, enum reg_note dep_type, bool hard)
1580{
1581 add_dependence_list (insn, *listp, uncond, dep_type, hard);
1582
1583 /* We don't want to short-circuit dependencies involving debug
1584 insns, because they may cause actual dependencies to be
1585 disregarded. */
1586 if (deps->readonly || DEBUG_INSN_P (insn))
1587 return;
1588
1589 free_INSN_LIST_list (listp);
1590}
1591
1592/* Remove all occurrences of INSN from LIST. Return the number of
1593 occurrences removed. */
1594
1595static int
1596remove_from_dependence_list (rtx_insn *insn, rtx_insn_list **listp)
1597{
1598 int removed = 0;
1599
1600 while (*listp)
1601 {
1602 if ((*listp)->insn () == insn)
1603 {
1604 remove_free_INSN_LIST_node (listp);
1605 removed++;
1606 continue;
1607 }
1608
1609 listp = (rtx_insn_list **)&XEXP (*listp, 1);
1610 }
1611
1612 return removed;
1613}
1614
1615/* Same as above, but process two lists at once. */
1616static int
1617remove_from_both_dependence_lists (rtx_insn *insn,
1618 rtx_insn_list **listp,
1619 rtx_expr_list **exprp)
1620{
1621 int removed = 0;
1622
1623 while (*listp)
1624 {
1625 if (XEXP (*listp, 0) == insn)
1626 {
1627 remove_free_INSN_LIST_node (listp);
1628 remove_free_EXPR_LIST_node (exprp);
1629 removed++;
1630 continue;
1631 }
1632
1633 listp = (rtx_insn_list **)&XEXP (*listp, 1);
1634 exprp = (rtx_expr_list **)&XEXP (*exprp, 1);
1635 }
1636
1637 return removed;
1638}
1639
1640/* Clear all dependencies for an insn. */
1641static void
1642delete_all_dependences (rtx_insn *insn)
1643{
1644 sd_iterator_def sd_it;
1645 dep_t dep;
1646
1647 /* The below cycle can be optimized to clear the caches and back_deps
1648 in one call but that would provoke duplication of code from
1649 delete_dep (). */
1650
1651 for (sd_it = sd_iterator_start (insn, SD_LIST_BACK);
1652 sd_iterator_cond (&sd_it, &dep);)
1653 sd_delete_dep (sd_it);
1654}
1655
1656/* All insns in a scheduling group except the first should only have
1657 dependencies on the previous insn in the group. So we find the
1658 first instruction in the scheduling group by walking the dependence
1659 chains backwards. Then we add the dependencies for the group to
1660 the previous nonnote insn. */
1661
1662static void
1663chain_to_prev_insn (rtx_insn *insn)
1664{
1665 sd_iterator_def sd_it;
1666 dep_t dep;
1667 rtx_insn *prev_nonnote;
1668
1669 FOR_EACH_DEP (insn, SD_LIST_BACK, sd_it, dep)
1670 {
1671 rtx_insn *i = insn;
1672 rtx_insn *pro = DEP_PRO (dep);
1673
1674 do
1675 {
1676 i = prev_nonnote_insn (i);
1677
1678 if (pro == i)
1679 goto next_link;
1680 } while (SCHED_GROUP_P (i) || DEBUG_INSN_P (i));
1681
1682 if (! sched_insns_conditions_mutex_p (i, pro))
1683 add_dependence (i, pro, DEP_TYPE (dep));
1684 next_link:;
1685 }
1686
1687 delete_all_dependences (insn);
1688
1689 prev_nonnote = prev_nonnote_nondebug_insn (insn);
1690 if (BLOCK_FOR_INSN (insn) == BLOCK_FOR_INSN (prev_nonnote)
1691 && ! sched_insns_conditions_mutex_p (insn, prev_nonnote))
1692 add_dependence (insn, prev_nonnote, REG_DEP_ANTI);
1693}
1694
1695/* Process an insn's memory dependencies. There are four kinds of
1696 dependencies:
1697
1698 (0) read dependence: read follows read
1699 (1) true dependence: read follows write
1700 (2) output dependence: write follows write
1701 (3) anti dependence: write follows read
1702
1703 We are careful to build only dependencies which actually exist, and
1704 use transitivity to avoid building too many links. */
1705
1706/* Add an INSN and MEM reference pair to a pending INSN_LIST and MEM_LIST.
1707 The MEM is a memory reference contained within INSN, which we are saving
1708 so that we can do memory aliasing on it. */
1709
1710static void
1711add_insn_mem_dependence (struct deps_desc *deps, bool read_p,
1712 rtx_insn *insn, rtx mem)
1713{
1714 rtx_insn_list **insn_list;
1715 rtx_insn_list *insn_node;
1716 rtx_expr_list **mem_list;
1717 rtx_expr_list *mem_node;
1718
1719 gcc_assert (!deps->readonly);
1720 if (read_p)
1721 {
1722 insn_list = &deps->pending_read_insns;
1723 mem_list = &deps->pending_read_mems;
1724 if (!DEBUG_INSN_P (insn))
1725 deps->pending_read_list_length++;
1726 }
1727 else
1728 {
1729 insn_list = &deps->pending_write_insns;
1730 mem_list = &deps->pending_write_mems;
1731 deps->pending_write_list_length++;
1732 }
1733
1734 insn_node = alloc_INSN_LIST (insn, *insn_list);
1735 *insn_list = insn_node;
1736
1737 if (sched_deps_info->use_cselib)
1738 {
1739 mem = shallow_copy_rtx (mem);
1740 XEXP (mem, 0) = cselib_subst_to_values_from_insn (XEXP (mem, 0),
1741 GET_MODE (mem), insn);
1742 }
1743 mem_node = alloc_EXPR_LIST (VOIDmode, canon_rtx (mem), *mem_list);
1744 *mem_list = mem_node;
1745}
1746
1747/* Make a dependency between every memory reference on the pending lists
1748 and INSN, thus flushing the pending lists. FOR_READ is true if emitting
1749 dependencies for a read operation, similarly with FOR_WRITE. */
1750
1751static void
1752flush_pending_lists (struct deps_desc *deps, rtx_insn *insn, int for_read,
1753 int for_write)
1754{
1755 if (for_write)
1756 {
1757 add_dependence_list_and_free (deps, insn, &deps->pending_read_insns,
1758 1, REG_DEP_ANTI, true);
1759 if (!deps->readonly)
1760 {
1761 free_EXPR_LIST_list (&deps->pending_read_mems);
1762 deps->pending_read_list_length = 0;
1763 }
1764 }
1765
1766 add_dependence_list_and_free (deps, insn, &deps->pending_write_insns, 1,
1767 for_read ? REG_DEP_ANTI : REG_DEP_OUTPUT,
1768 true);
1769
1770 add_dependence_list_and_free (deps, insn,
1771 &deps->last_pending_memory_flush, 1,
1772 for_read ? REG_DEP_ANTI : REG_DEP_OUTPUT,
1773 true);
1774
1775 add_dependence_list_and_free (deps, insn, &deps->pending_jump_insns, 1,
1776 REG_DEP_ANTI, true);
1777
1778 if (DEBUG_INSN_P (insn))
1779 {
1780 if (for_write)
1781 free_INSN_LIST_list (&deps->pending_read_insns);
1782 free_INSN_LIST_list (&deps->pending_write_insns);
1783 free_INSN_LIST_list (&deps->last_pending_memory_flush);
1784 free_INSN_LIST_list (&deps->pending_jump_insns);
1785 }
1786
1787 if (!deps->readonly)
1788 {
1789 free_EXPR_LIST_list (&deps->pending_write_mems);
1790 deps->pending_write_list_length = 0;
1791
1792 deps->last_pending_memory_flush = alloc_INSN_LIST (insn, NULL_RTX);
1793 deps->pending_flush_length = 1;
1794 }
1795 mark_as_hard = false;
1796}
1797
1798/* Instruction which dependencies we are analyzing. */
1799static rtx_insn *cur_insn = NULL;
1800
1801/* Implement hooks for haifa scheduler. */
1802
1803static void
1804haifa_start_insn (rtx_insn *insn)
1805{
1806 gcc_assert (insn && !cur_insn);
1807
1808 cur_insn = insn;
1809}
1810
1811static void
1812haifa_finish_insn (void)
1813{
1814 cur_insn = NULL;
1815}
1816
1817void
1818haifa_note_reg_set (int regno)
1819{
1820 SET_REGNO_REG_SET (reg_pending_sets, regno);
1821}
1822
1823void
1824haifa_note_reg_clobber (int regno)
1825{
1826 SET_REGNO_REG_SET (reg_pending_clobbers, regno);
1827}
1828
1829void
1830haifa_note_reg_use (int regno)
1831{
1832 SET_REGNO_REG_SET (reg_pending_uses, regno);
1833}
1834
1835static void
1836haifa_note_mem_dep (rtx mem, rtx pending_mem, rtx_insn *pending_insn, ds_t ds)
1837{
1838 if (!(ds & SPECULATIVE))
1839 {
1840 mem = NULL_RTX;
1841 pending_mem = NULL_RTX;
1842 }
1843 else
1844 gcc_assert (ds & BEGIN_DATA);
1845
1846 {
1847 dep_def _dep, *dep = &_dep;
1848
1849 init_dep_1 (dep, pending_insn, cur_insn, ds_to_dt (ds),
1850 current_sched_info->flags & USE_DEPS_LIST ? ds : 0);
1851 DEP_NONREG (dep) = 1;
1852 maybe_add_or_update_dep_1 (dep, false, pending_mem, mem);
1853 }
1854
1855}
1856
1857static void
1858haifa_note_dep (rtx_insn *elem, ds_t ds)
1859{
1860 dep_def _dep;
1861 dep_t dep = &_dep;
1862
1863 init_dep (dep, elem, cur_insn, ds_to_dt (ds));
1864 if (mark_as_hard)
1865 DEP_NONREG (dep) = 1;
1866 maybe_add_or_update_dep_1 (dep, false, NULL_RTX, NULL_RTX);
1867}
1868
1869static void
1870note_reg_use (int r)
1871{
1872 if (sched_deps_info->note_reg_use)
1873 sched_deps_info->note_reg_use (r);
1874}
1875
1876static void
1877note_reg_set (int r)
1878{
1879 if (sched_deps_info->note_reg_set)
1880 sched_deps_info->note_reg_set (r);
1881}
1882
1883static void
1884note_reg_clobber (int r)
1885{
1886 if (sched_deps_info->note_reg_clobber)
1887 sched_deps_info->note_reg_clobber (r);
1888}
1889
1890static void
1891note_mem_dep (rtx m1, rtx m2, rtx_insn *e, ds_t ds)
1892{
1893 if (sched_deps_info->note_mem_dep)
1894 sched_deps_info->note_mem_dep (m1, m2, e, ds);
1895}
1896
1897static void
1898note_dep (rtx_insn *e, ds_t ds)
1899{
1900 if (sched_deps_info->note_dep)
1901 sched_deps_info->note_dep (e, ds);
1902}
1903
1904/* Return corresponding to DS reg_note. */
1905enum reg_note
1906ds_to_dt (ds_t ds)
1907{
1908 if (ds & DEP_TRUE)
1909 return REG_DEP_TRUE;
1910 else if (ds & DEP_OUTPUT)
1911 return REG_DEP_OUTPUT;
1912 else if (ds & DEP_ANTI)
1913 return REG_DEP_ANTI;
1914 else
1915 {
1916 gcc_assert (ds & DEP_CONTROL);
1917 return REG_DEP_CONTROL;
1918 }
1919}
1920
1921
1922
1923/* Functions for computation of info needed for register pressure
1924 sensitive insn scheduling. */
1925
1926
1927/* Allocate and return reg_use_data structure for REGNO and INSN. */
1928static struct reg_use_data *
1929create_insn_reg_use (int regno, rtx_insn *insn)
1930{
1931 struct reg_use_data *use;
1932
1933 use = (struct reg_use_data *) xmalloc (sizeof (struct reg_use_data));
1934 use->regno = regno;
1935 use->insn = insn;
1936 use->next_insn_use = INSN_REG_USE_LIST (insn);
1937 INSN_REG_USE_LIST (insn) = use;
1938 return use;
1939}
1940
1941/* Allocate reg_set_data structure for REGNO and INSN. */
1942static void
1943create_insn_reg_set (int regno, rtx insn)
1944{
1945 struct reg_set_data *set;
1946
1947 set = (struct reg_set_data *) xmalloc (sizeof (struct reg_set_data));
1948 set->regno = regno;
1949 set->insn = insn;
1950 set->next_insn_set = INSN_REG_SET_LIST (insn);
1951 INSN_REG_SET_LIST (insn) = set;
1952}
1953
1954/* Set up insn register uses for INSN and dependency context DEPS. */
1955static void
1956setup_insn_reg_uses (struct deps_desc *deps, rtx_insn *insn)
1957{
1958 unsigned i;
1959 reg_set_iterator rsi;
1960 struct reg_use_data *use, *use2, *next;
1961 struct deps_reg *reg_last;
1962
1963 EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i, rsi)
1964 {
1965 if (i < FIRST_PSEUDO_REGISTER
1966 && TEST_HARD_REG_BIT (ira_no_alloc_regs, i))
1967 continue;
1968
1969 if (find_regno_note (insn, REG_DEAD, i) == NULL_RTX
1970 && ! REGNO_REG_SET_P (reg_pending_sets, i)
1971 && ! REGNO_REG_SET_P (reg_pending_clobbers, i))
1972 /* Ignore use which is not dying. */
1973 continue;
1974
1975 use = create_insn_reg_use (i, insn);
1976 use->next_regno_use = use;
1977 reg_last = &deps->reg_last[i];
1978
1979 /* Create the cycle list of uses. */
1980 for (rtx_insn_list *list = reg_last->uses; list; list = list->next ())
1981 {
1982 use2 = create_insn_reg_use (i, list->insn ());
1983 next = use->next_regno_use;
1984 use->next_regno_use = use2;
1985 use2->next_regno_use = next;
1986 }
1987 }
1988}
1989
1990/* Register pressure info for the currently processed insn. */
1991static struct reg_pressure_data reg_pressure_info[N_REG_CLASSES];
1992
1993/* Return TRUE if INSN has the use structure for REGNO. */
1994static bool
1995insn_use_p (rtx insn, int regno)
1996{
1997 struct reg_use_data *use;
1998
1999 for (use = INSN_REG_USE_LIST (insn); use != NULL; use = use->next_insn_use)
2000 if (use->regno == regno)
2001 return true;
2002 return false;
2003}
2004
2005/* Update the register pressure info after birth of pseudo register REGNO
2006 in INSN. Arguments CLOBBER_P and UNUSED_P say correspondingly that
2007 the register is in clobber or unused after the insn. */
2008static void
2009mark_insn_pseudo_birth (rtx insn, int regno, bool clobber_p, bool unused_p)
2010{
2011 int incr, new_incr;
2012 enum reg_class cl;
2013
2014 gcc_assert (regno >= FIRST_PSEUDO_REGISTER);
2015 cl = sched_regno_pressure_class[regno];
2016 if (cl != NO_REGS)
2017 {
2018 incr = ira_reg_class_max_nregs[cl][PSEUDO_REGNO_MODE (regno)];
2019 if (clobber_p)
2020 {
2021 new_incr = reg_pressure_info[cl].clobber_increase + incr;
2022 reg_pressure_info[cl].clobber_increase = new_incr;
2023 }
2024 else if (unused_p)
2025 {
2026 new_incr = reg_pressure_info[cl].unused_set_increase + incr;
2027 reg_pressure_info[cl].unused_set_increase = new_incr;
2028 }
2029 else
2030 {
2031 new_incr = reg_pressure_info[cl].set_increase + incr;
2032 reg_pressure_info[cl].set_increase = new_incr;
2033 if (! insn_use_p (insn, regno))
2034 reg_pressure_info[cl].change += incr;
2035 create_insn_reg_set (regno, insn);
2036 }
2037 gcc_assert (new_incr < (1 << INCREASE_BITS));
2038 }
2039}
2040
2041/* Like mark_insn_pseudo_regno_birth except that NREGS saying how many
2042 hard registers involved in the birth. */
2043static void
2044mark_insn_hard_regno_birth (rtx insn, int regno, int nregs,
2045 bool clobber_p, bool unused_p)
2046{
2047 enum reg_class cl;
2048 int new_incr, last = regno + nregs;
2049
2050 while (regno < last)
2051 {
2052 gcc_assert (regno < FIRST_PSEUDO_REGISTER);
2053 if (! TEST_HARD_REG_BIT (ira_no_alloc_regs, regno))
2054 {
2055 cl = sched_regno_pressure_class[regno];
2056 if (cl != NO_REGS)
2057 {
2058 if (clobber_p)
2059 {
2060 new_incr = reg_pressure_info[cl].clobber_increase + 1;
2061 reg_pressure_info[cl].clobber_increase = new_incr;
2062 }
2063 else if (unused_p)
2064 {
2065 new_incr = reg_pressure_info[cl].unused_set_increase + 1;
2066 reg_pressure_info[cl].unused_set_increase = new_incr;
2067 }
2068 else
2069 {
2070 new_incr = reg_pressure_info[cl].set_increase + 1;
2071 reg_pressure_info[cl].set_increase = new_incr;
2072 if (! insn_use_p (insn, regno))
2073 reg_pressure_info[cl].change += 1;
2074 create_insn_reg_set (regno, insn);
2075 }
2076 gcc_assert (new_incr < (1 << INCREASE_BITS));
2077 }
2078 }
2079 regno++;
2080 }
2081}
2082
2083/* Update the register pressure info after birth of pseudo or hard
2084 register REG in INSN. Arguments CLOBBER_P and UNUSED_P say
2085 correspondingly that the register is in clobber or unused after the
2086 insn. */
2087static void
2088mark_insn_reg_birth (rtx insn, rtx reg, bool clobber_p, bool unused_p)
2089{
2090 int regno;
2091
2092 if (GET_CODE (reg) == SUBREG)
2093 reg = SUBREG_REG (reg);
2094
2095 if (! REG_P (reg))
2096 return;
2097
2098 regno = REGNO (reg);
2099 if (regno < FIRST_PSEUDO_REGISTER)
2100 mark_insn_hard_regno_birth (insn, regno, REG_NREGS (reg),
2101 clobber_p, unused_p);
2102 else
2103 mark_insn_pseudo_birth (insn, regno, clobber_p, unused_p);
2104}
2105
2106/* Update the register pressure info after death of pseudo register
2107 REGNO. */
2108static void
2109mark_pseudo_death (int regno)
2110{
2111 int incr;
2112 enum reg_class cl;
2113
2114 gcc_assert (regno >= FIRST_PSEUDO_REGISTER);
2115 cl = sched_regno_pressure_class[regno];
2116 if (cl != NO_REGS)
2117 {
2118 incr = ira_reg_class_max_nregs[cl][PSEUDO_REGNO_MODE (regno)];
2119 reg_pressure_info[cl].change -= incr;
2120 }
2121}
2122
2123/* Like mark_pseudo_death except that NREGS saying how many hard
2124 registers involved in the death. */
2125static void
2126mark_hard_regno_death (int regno, int nregs)
2127{
2128 enum reg_class cl;
2129 int last = regno + nregs;
2130
2131 while (regno < last)
2132 {
2133 gcc_assert (regno < FIRST_PSEUDO_REGISTER);
2134 if (! TEST_HARD_REG_BIT (ira_no_alloc_regs, regno))
2135 {
2136 cl = sched_regno_pressure_class[regno];
2137 if (cl != NO_REGS)
2138 reg_pressure_info[cl].change -= 1;
2139 }
2140 regno++;
2141 }
2142}
2143
2144/* Update the register pressure info after death of pseudo or hard
2145 register REG. */
2146static void
2147mark_reg_death (rtx reg)
2148{
2149 int regno;
2150
2151 if (GET_CODE (reg) == SUBREG)
2152 reg = SUBREG_REG (reg);
2153
2154 if (! REG_P (reg))
2155 return;
2156
2157 regno = REGNO (reg);
2158 if (regno < FIRST_PSEUDO_REGISTER)
2159 mark_hard_regno_death (regno, REG_NREGS (reg));
2160 else
2161 mark_pseudo_death (regno);
2162}
2163
2164/* Process SETTER of REG. DATA is an insn containing the setter. */
2165static void
2166mark_insn_reg_store (rtx reg, const_rtx setter, void *data)
2167{
2168 if (setter != NULL_RTX && GET_CODE (setter) != SET)
2169 return;
2170 mark_insn_reg_birth
2171 ((rtx) data, reg, false,
2172 find_reg_note ((const_rtx) data, REG_UNUSED, reg) != NULL_RTX);
2173}
2174
2175/* Like mark_insn_reg_store except notice just CLOBBERs; ignore SETs. */
2176static void
2177mark_insn_reg_clobber (rtx reg, const_rtx setter, void *data)
2178{
2179 if (GET_CODE (setter) == CLOBBER)
2180 mark_insn_reg_birth ((rtx) data, reg, true, false);
2181}
2182
2183/* Set up reg pressure info related to INSN. */
2184void
2185init_insn_reg_pressure_info (rtx_insn *insn)
2186{
2187 int i, len;
2188 enum reg_class cl;
2189 static struct reg_pressure_data *pressure_info;
2190 rtx link;
2191
2192 gcc_assert (sched_pressure != SCHED_PRESSURE_NONE);
2193
2194 if (! INSN_P (insn))
2195 return;
2196
2197 for (i = 0; i < ira_pressure_classes_num; i++)
2198 {
2199 cl = ira_pressure_classes[i];
2200 reg_pressure_info[cl].clobber_increase = 0;
2201 reg_pressure_info[cl].set_increase = 0;
2202 reg_pressure_info[cl].unused_set_increase = 0;
2203 reg_pressure_info[cl].change = 0;
2204 }
2205
2206 note_stores (PATTERN (insn), mark_insn_reg_clobber, insn);
2207
2208 note_stores (PATTERN (insn), mark_insn_reg_store, insn);
2209
2210 if (AUTO_INC_DEC)
2211 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
2212 if (REG_NOTE_KIND (link) == REG_INC)
2213 mark_insn_reg_store (XEXP (link, 0), NULL_RTX, insn);
2214
2215 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
2216 if (REG_NOTE_KIND (link) == REG_DEAD)
2217 mark_reg_death (XEXP (link, 0));
2218
2219 len = sizeof (struct reg_pressure_data) * ira_pressure_classes_num;
2220 pressure_info
2221 = INSN_REG_PRESSURE (insn) = (struct reg_pressure_data *) xmalloc (len);
2222 if (sched_pressure == SCHED_PRESSURE_WEIGHTED)
2223 INSN_MAX_REG_PRESSURE (insn) = (int *) xcalloc (ira_pressure_classes_num
2224 * sizeof (int), 1);
2225 for (i = 0; i < ira_pressure_classes_num; i++)
2226 {
2227 cl = ira_pressure_classes[i];
2228 pressure_info[i].clobber_increase
2229 = reg_pressure_info[cl].clobber_increase;
2230 pressure_info[i].set_increase = reg_pressure_info[cl].set_increase;
2231 pressure_info[i].unused_set_increase
2232 = reg_pressure_info[cl].unused_set_increase;
2233 pressure_info[i].change = reg_pressure_info[cl].change;
2234 }
2235}
2236
2237
2238
2239
2240/* Internal variable for sched_analyze_[12] () functions.
2241 If it is nonzero, this means that sched_analyze_[12] looks
2242 at the most toplevel SET. */
2243static bool can_start_lhs_rhs_p;
2244
2245/* Extend reg info for the deps context DEPS given that
2246 we have just generated a register numbered REGNO. */
2247static void
2248extend_deps_reg_info (struct deps_desc *deps, int regno)
2249{
2250 int max_regno = regno + 1;
2251
2252 gcc_assert (!reload_completed);
2253
2254 /* In a readonly context, it would not hurt to extend info,
2255 but it should not be needed. */
2256 if (reload_completed && deps->readonly)
2257 {
2258 deps->max_reg = max_regno;
2259 return;
2260 }
2261
2262 if (max_regno > deps->max_reg)
2263 {
2264 deps->reg_last = XRESIZEVEC (struct deps_reg, deps->reg_last,
2265 max_regno);
2266 memset (&deps->reg_last[deps->max_reg],
2267 0, (max_regno - deps->max_reg)
2268 * sizeof (struct deps_reg));
2269 deps->max_reg = max_regno;
2270 }
2271}
2272
2273/* Extends REG_INFO_P if needed. */
2274void
2275maybe_extend_reg_info_p (void)
2276{
2277 /* Extend REG_INFO_P, if needed. */
2278 if ((unsigned int)max_regno - 1 >= reg_info_p_size)
2279 {
2280 size_t new_reg_info_p_size = max_regno + 128;
2281
2282 gcc_assert (!reload_completed && sel_sched_p ());
2283
2284 reg_info_p = (struct reg_info_t *) xrecalloc (reg_info_p,
2285 new_reg_info_p_size,
2286 reg_info_p_size,
2287 sizeof (*reg_info_p));
2288 reg_info_p_size = new_reg_info_p_size;
2289 }
2290}
2291
2292/* Analyze a single reference to register (reg:MODE REGNO) in INSN.
2293 The type of the reference is specified by REF and can be SET,
2294 CLOBBER, PRE_DEC, POST_DEC, PRE_INC, POST_INC or USE. */
2295
2296static void
2297sched_analyze_reg (struct deps_desc *deps, int regno, machine_mode mode,
2298 enum rtx_code ref, rtx_insn *insn)
2299{
2300 /* We could emit new pseudos in renaming. Extend the reg structures. */
2301 if (!reload_completed && sel_sched_p ()
2302 && (regno >= max_reg_num () - 1 || regno >= deps->max_reg))
2303 extend_deps_reg_info (deps, regno);
2304
2305 maybe_extend_reg_info_p ();
2306
2307 /* A hard reg in a wide mode may really be multiple registers.
2308 If so, mark all of them just like the first. */
2309 if (regno < FIRST_PSEUDO_REGISTER)
2310 {
2311 int i = hard_regno_nregs (regno, mode);
2312 if (ref == SET)
2313 {
2314 while (--i >= 0)
2315 note_reg_set (regno + i);
2316 }
2317 else if (ref == USE)
2318 {
2319 while (--i >= 0)
2320 note_reg_use (regno + i);
2321 }
2322 else
2323 {
2324 while (--i >= 0)
2325 note_reg_clobber (regno + i);
2326 }
2327 }
2328
2329 /* ??? Reload sometimes emits USEs and CLOBBERs of pseudos that
2330 it does not reload. Ignore these as they have served their
2331 purpose already. */
2332 else if (regno >= deps->max_reg)
2333 {
2334 enum rtx_code code = GET_CODE (PATTERN (insn));
2335 gcc_assert (code == USE || code == CLOBBER);
2336 }
2337
2338 else
2339 {
2340 if (ref == SET)
2341 note_reg_set (regno);
2342 else if (ref == USE)
2343 note_reg_use (regno);
2344 else
2345 note_reg_clobber (regno);
2346
2347 /* Pseudos that are REG_EQUIV to something may be replaced
2348 by that during reloading. We need only add dependencies for
2349 the address in the REG_EQUIV note. */
2350 if (!reload_completed && get_reg_known_equiv_p (regno))
2351 {
2352 rtx t = get_reg_known_value (regno);
2353 if (MEM_P (t))
2354 sched_analyze_2 (deps, XEXP (t, 0), insn);
2355 }
2356
2357 /* Don't let it cross a call after scheduling if it doesn't
2358 already cross one. */
2359 if (REG_N_CALLS_CROSSED (regno) == 0)
2360 {
2361 if (!deps->readonly && ref == USE && !DEBUG_INSN_P (insn))
2362 deps->sched_before_next_call
2363 = alloc_INSN_LIST (insn, deps->sched_before_next_call);
2364 else
2365 add_dependence_list (insn, deps->last_function_call, 1,
2366 REG_DEP_ANTI, false);
2367 }
2368 }
2369}
2370
2371/* Analyze a single SET, CLOBBER, PRE_DEC, POST_DEC, PRE_INC or POST_INC
2372 rtx, X, creating all dependencies generated by the write to the
2373 destination of X, and reads of everything mentioned. */
2374
2375static void
2376sched_analyze_1 (struct deps_desc *deps, rtx x, rtx_insn *insn)
2377{
2378 rtx dest = XEXP (x, 0);
2379 enum rtx_code code = GET_CODE (x);
2380 bool cslr_p = can_start_lhs_rhs_p;
2381
2382 can_start_lhs_rhs_p = false;
2383
2384 gcc_assert (dest);
2385 if (dest == 0)
2386 return;
2387
2388 if (cslr_p && sched_deps_info->start_lhs)
2389 sched_deps_info->start_lhs (dest);
2390
2391 if (GET_CODE (dest) == PARALLEL)
2392 {
2393 int i;
2394
2395 for (i = XVECLEN (dest, 0) - 1; i >= 0; i--)
2396 if (XEXP (XVECEXP (dest, 0, i), 0) != 0)
2397 sched_analyze_1 (deps,
2398 gen_rtx_CLOBBER (VOIDmode,
2399 XEXP (XVECEXP (dest, 0, i), 0)),
2400 insn);
2401
2402 if (cslr_p && sched_deps_info->finish_lhs)
2403 sched_deps_info->finish_lhs ();
2404
2405 if (code == SET)
2406 {
2407 can_start_lhs_rhs_p = cslr_p;
2408
2409 sched_analyze_2 (deps, SET_SRC (x), insn);
2410
2411 can_start_lhs_rhs_p = false;
2412 }
2413
2414 return;
2415 }
2416
2417 while (GET_CODE (dest) == STRICT_LOW_PART || GET_CODE (dest) == SUBREG
2418 || GET_CODE (dest) == ZERO_EXTRACT)
2419 {
2420 if (GET_CODE (dest) == STRICT_LOW_PART
2421 || GET_CODE (dest) == ZERO_EXTRACT
2422 || read_modify_subreg_p (dest))
2423 {
2424 /* These both read and modify the result. We must handle
2425 them as writes to get proper dependencies for following
2426 instructions. We must handle them as reads to get proper
2427 dependencies from this to previous instructions.
2428 Thus we need to call sched_analyze_2. */
2429
2430 sched_analyze_2 (deps, XEXP (dest, 0), insn);
2431 }
2432 if (GET_CODE (dest) == ZERO_EXTRACT)
2433 {
2434 /* The second and third arguments are values read by this insn. */
2435 sched_analyze_2 (deps, XEXP (dest, 1), insn);
2436 sched_analyze_2 (deps, XEXP (dest, 2), insn);
2437 }
2438 dest = XEXP (dest, 0);
2439 }
2440
2441 if (REG_P (dest))
2442 {
2443 int regno = REGNO (dest);
2444 machine_mode mode = GET_MODE (dest);
2445
2446 sched_analyze_reg (deps, regno, mode, code, insn);
2447
2448#ifdef STACK_REGS
2449 /* Treat all writes to a stack register as modifying the TOS. */
2450 if (regno >= FIRST_STACK_REG && regno <= LAST_STACK_REG)
2451 {
2452 /* Avoid analyzing the same register twice. */
2453 if (regno != FIRST_STACK_REG)
2454 sched_analyze_reg (deps, FIRST_STACK_REG, mode, code, insn);
2455
2456 add_to_hard_reg_set (&implicit_reg_pending_uses, mode,
2457 FIRST_STACK_REG);
2458 }
2459#endif
2460 }
2461 else if (MEM_P (dest))
2462 {
2463 /* Writing memory. */
2464 rtx t = dest;
2465
2466 if (sched_deps_info->use_cselib)
2467 {
2468 machine_mode address_mode = get_address_mode (dest);
2469
2470 t = shallow_copy_rtx (dest);
2471 cselib_lookup_from_insn (XEXP (t, 0), address_mode, 1,
2472 GET_MODE (t), insn);
2473 XEXP (t, 0)
2474 = cselib_subst_to_values_from_insn (XEXP (t, 0), GET_MODE (t),
2475 insn);
2476 }
2477 t = canon_rtx (t);
2478
2479 /* Pending lists can't get larger with a readonly context. */
2480 if (!deps->readonly
2481 && ((deps->pending_read_list_length + deps->pending_write_list_length)
2482 >= MAX_PENDING_LIST_LENGTH))
2483 {
2484 /* Flush all pending reads and writes to prevent the pending lists
2485 from getting any larger. Insn scheduling runs too slowly when
2486 these lists get long. When compiling GCC with itself,
2487 this flush occurs 8 times for sparc, and 10 times for m88k using
2488 the default value of 32. */
2489 flush_pending_lists (deps, insn, false, true);
2490 }
2491 else
2492 {
2493 rtx_insn_list *pending;
2494 rtx_expr_list *pending_mem;
2495
2496 pending = deps->pending_read_insns;
2497 pending_mem = deps->pending_read_mems;
2498 while (pending)
2499 {
2500 if (anti_dependence (pending_mem->element (), t)
2501 && ! sched_insns_conditions_mutex_p (insn, pending->insn ()))
2502 note_mem_dep (t, pending_mem->element (), pending->insn (),
2503 DEP_ANTI);
2504
2505 pending = pending->next ();
2506 pending_mem = pending_mem->next ();
2507 }
2508
2509 pending = deps->pending_write_insns;
2510 pending_mem = deps->pending_write_mems;
2511 while (pending)
2512 {
2513 if (output_dependence (pending_mem->element (), t)
2514 && ! sched_insns_conditions_mutex_p (insn, pending->insn ()))
2515 note_mem_dep (t, pending_mem->element (),
2516 pending->insn (),
2517 DEP_OUTPUT);
2518
2519 pending = pending->next ();
2520 pending_mem = pending_mem-> next ();
2521 }
2522
2523 add_dependence_list (insn, deps->last_pending_memory_flush, 1,
2524 REG_DEP_ANTI, true);
2525 add_dependence_list (insn, deps->pending_jump_insns, 1,
2526 REG_DEP_CONTROL, true);
2527
2528 if (!deps->readonly)
2529 add_insn_mem_dependence (deps, false, insn, dest);
2530 }
2531 sched_analyze_2 (deps, XEXP (dest, 0), insn);
2532 }
2533
2534 if (cslr_p && sched_deps_info->finish_lhs)
2535 sched_deps_info->finish_lhs ();
2536
2537 /* Analyze reads. */
2538 if (GET_CODE (x) == SET)
2539 {
2540 can_start_lhs_rhs_p = cslr_p;
2541
2542 sched_analyze_2 (deps, SET_SRC (x), insn);
2543
2544 can_start_lhs_rhs_p = false;
2545 }
2546}
2547
2548/* Analyze the uses of memory and registers in rtx X in INSN. */
2549static void
2550sched_analyze_2 (struct deps_desc *deps, rtx x, rtx_insn *insn)
2551{
2552 int i;
2553 int j;
2554 enum rtx_code code;
2555 const char *fmt;
2556 bool cslr_p = can_start_lhs_rhs_p;
2557
2558 can_start_lhs_rhs_p = false;
2559
2560 gcc_assert (x);
2561 if (x == 0)
2562 return;
2563
2564 if (cslr_p && sched_deps_info->start_rhs)
2565 sched_deps_info->start_rhs (x);
2566
2567 code = GET_CODE (x);
2568
2569 switch (code)
2570 {
2571 CASE_CONST_ANY:
2572 case SYMBOL_REF:
2573 case CONST:
2574 case LABEL_REF:
2575 /* Ignore constants. */
2576 if (cslr_p && sched_deps_info->finish_rhs)
2577 sched_deps_info->finish_rhs ();
2578
2579 return;
2580
2581 case CC0:
2582 if (!HAVE_cc0)
2583 gcc_unreachable ();
2584
2585 /* User of CC0 depends on immediately preceding insn. */
2586 SCHED_GROUP_P (insn) = 1;
2587 /* Don't move CC0 setter to another block (it can set up the
2588 same flag for previous CC0 users which is safe). */
2589 CANT_MOVE (prev_nonnote_insn (insn)) = 1;
2590
2591 if (cslr_p && sched_deps_info->finish_rhs)
2592 sched_deps_info->finish_rhs ();
2593
2594 return;
2595
2596 case REG:
2597 {
2598 int regno = REGNO (x);
2599 machine_mode mode = GET_MODE (x);
2600
2601 sched_analyze_reg (deps, regno, mode, USE, insn);
2602
2603#ifdef STACK_REGS
2604 /* Treat all reads of a stack register as modifying the TOS. */
2605 if (regno >= FIRST_STACK_REG && regno <= LAST_STACK_REG)
2606 {
2607 /* Avoid analyzing the same register twice. */
2608 if (regno != FIRST_STACK_REG)
2609 sched_analyze_reg (deps, FIRST_STACK_REG, mode, USE, insn);
2610 sched_analyze_reg (deps, FIRST_STACK_REG, mode, SET, insn);
2611 }
2612#endif
2613
2614 if (cslr_p && sched_deps_info->finish_rhs)
2615 sched_deps_info->finish_rhs ();
2616
2617 return;
2618 }
2619
2620 case MEM:
2621 {
2622 /* Reading memory. */
2623 rtx_insn_list *u;
2624 rtx_insn_list *pending;
2625 rtx_expr_list *pending_mem;
2626 rtx t = x;
2627
2628 if (sched_deps_info->use_cselib)
2629 {
2630 machine_mode address_mode = get_address_mode (t);
2631
2632 t = shallow_copy_rtx (t);
2633 cselib_lookup_from_insn (XEXP (t, 0), address_mode, 1,
2634 GET_MODE (t), insn);
2635 XEXP (t, 0)
2636 = cselib_subst_to_values_from_insn (XEXP (t, 0), GET_MODE (t),
2637 insn);
2638 }
2639
2640 if (!DEBUG_INSN_P (insn))
2641 {
2642 t = canon_rtx (t);
2643 pending = deps->pending_read_insns;
2644 pending_mem = deps->pending_read_mems;
2645 while (pending)
2646 {
2647 if (read_dependence (pending_mem->element (), t)
2648 && ! sched_insns_conditions_mutex_p (insn,
2649 pending->insn ()))
2650 note_mem_dep (t, pending_mem->element (),
2651 pending->insn (),
2652 DEP_ANTI);
2653
2654 pending = pending->next ();
2655 pending_mem = pending_mem->next ();
2656 }
2657
2658 pending = deps->pending_write_insns;
2659 pending_mem = deps->pending_write_mems;
2660 while (pending)
2661 {
2662 if (true_dependence (pending_mem->element (), VOIDmode, t)
2663 && ! sched_insns_conditions_mutex_p (insn,
2664 pending->insn ()))
2665 note_mem_dep (t, pending_mem->element (),
2666 pending->insn (),
2667 sched_deps_info->generate_spec_deps
2668 ? BEGIN_DATA | DEP_TRUE : DEP_TRUE);
2669
2670 pending = pending->next ();
2671 pending_mem = pending_mem->next ();
2672 }
2673
2674 for (u = deps->last_pending_memory_flush; u; u = u->next ())
2675 add_dependence (insn, u->insn (), REG_DEP_ANTI);
2676
2677 for (u = deps->pending_jump_insns; u; u = u->next ())
2678 if (deps_may_trap_p (x))
2679 {
2680 if ((sched_deps_info->generate_spec_deps)
2681 && sel_sched_p () && (spec_info->mask & BEGIN_CONTROL))
2682 {
2683 ds_t ds = set_dep_weak (DEP_ANTI, BEGIN_CONTROL,
2684 MAX_DEP_WEAK);
2685
2686 note_dep (u->insn (), ds);
2687 }
2688 else
2689 add_dependence (insn, u->insn (), REG_DEP_CONTROL);
2690 }
2691 }
2692
2693 /* Always add these dependencies to pending_reads, since
2694 this insn may be followed by a write. */
2695 if (!deps->readonly)
2696 {
2697 if ((deps->pending_read_list_length
2698 + deps->pending_write_list_length)
2699 >= MAX_PENDING_LIST_LENGTH
2700 && !DEBUG_INSN_P (insn))
2701 flush_pending_lists (deps, insn, true, true);
2702 add_insn_mem_dependence (deps, true, insn, x);
2703 }
2704
2705 sched_analyze_2 (deps, XEXP (x, 0), insn);
2706
2707 if (cslr_p && sched_deps_info->finish_rhs)
2708 sched_deps_info->finish_rhs ();
2709
2710 return;
2711 }
2712
2713 /* Force pending stores to memory in case a trap handler needs them.
2714 Also force pending loads from memory; loads and stores can segfault
2715 and the signal handler won't be triggered if the trap insn was moved
2716 above load or store insn. */
2717 case TRAP_IF:
2718 flush_pending_lists (deps, insn, true, true);
2719 break;
2720
2721 case PREFETCH:
2722 if (PREFETCH_SCHEDULE_BARRIER_P (x))
2723 reg_pending_barrier = TRUE_BARRIER;
2724 /* Prefetch insn contains addresses only. So if the prefetch
2725 address has no registers, there will be no dependencies on
2726 the prefetch insn. This is wrong with result code
2727 correctness point of view as such prefetch can be moved below
2728 a jump insn which usually generates MOVE_BARRIER preventing
2729 to move insns containing registers or memories through the
2730 barrier. It is also wrong with generated code performance
2731 point of view as prefetch withouth dependecies will have a
2732 tendency to be issued later instead of earlier. It is hard
2733 to generate accurate dependencies for prefetch insns as
2734 prefetch has only the start address but it is better to have
2735 something than nothing. */
2736 if (!deps->readonly)
2737 {
2738 rtx x = gen_rtx_MEM (Pmode, XEXP (PATTERN (insn), 0));
2739 if (sched_deps_info->use_cselib)
2740 cselib_lookup_from_insn (x, Pmode, true, VOIDmode, insn);
2741 add_insn_mem_dependence (deps, true, insn, x);
2742 }
2743 break;
2744
2745 case UNSPEC_VOLATILE:
2746 flush_pending_lists (deps, insn, true, true);
2747 /* FALLTHRU */
2748
2749 case ASM_OPERANDS:
2750 case ASM_INPUT:
2751 {
2752 /* Traditional and volatile asm instructions must be considered to use
2753 and clobber all hard registers, all pseudo-registers and all of
2754 memory. So must TRAP_IF and UNSPEC_VOLATILE operations.
2755
2756 Consider for instance a volatile asm that changes the fpu rounding
2757 mode. An insn should not be moved across this even if it only uses
2758 pseudo-regs because it might give an incorrectly rounded result. */
2759 if ((code != ASM_OPERANDS || MEM_VOLATILE_P (x))
2760 && !DEBUG_INSN_P (insn))
2761 reg_pending_barrier = TRUE_BARRIER;
2762
2763 /* For all ASM_OPERANDS, we must traverse the vector of input operands.
2764 We can not just fall through here since then we would be confused
2765 by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
2766 traditional asms unlike their normal usage. */
2767
2768 if (code == ASM_OPERANDS)
2769 {
2770 for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++)
2771 sched_analyze_2 (deps, ASM_OPERANDS_INPUT (x, j), insn);
2772
2773 if (cslr_p && sched_deps_info->finish_rhs)
2774 sched_deps_info->finish_rhs ();
2775
2776 return;
2777 }
2778 break;
2779 }
2780
2781 case PRE_DEC:
2782 case POST_DEC:
2783 case PRE_INC:
2784 case POST_INC:
2785 /* These both read and modify the result. We must handle them as writes
2786 to get proper dependencies for following instructions. We must handle
2787 them as reads to get proper dependencies from this to previous
2788 instructions. Thus we need to pass them to both sched_analyze_1
2789 and sched_analyze_2. We must call sched_analyze_2 first in order
2790 to get the proper antecedent for the read. */
2791 sched_analyze_2 (deps, XEXP (x, 0), insn);
2792 sched_analyze_1 (deps, x, insn);
2793
2794 if (cslr_p && sched_deps_info->finish_rhs)
2795 sched_deps_info->finish_rhs ();
2796
2797 return;
2798
2799 case POST_MODIFY:
2800 case PRE_MODIFY:
2801 /* op0 = op0 + op1 */
2802 sched_analyze_2 (deps, XEXP (x, 0), insn);
2803 sched_analyze_2 (deps, XEXP (x, 1), insn);
2804 sched_analyze_1 (deps, x, insn);
2805
2806 if (cslr_p && sched_deps_info->finish_rhs)
2807 sched_deps_info->finish_rhs ();
2808
2809 return;
2810
2811 default:
2812 break;
2813 }
2814
2815 /* Other cases: walk the insn. */
2816 fmt = GET_RTX_FORMAT (code);
2817 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2818 {
2819 if (fmt[i] == 'e')
2820 sched_analyze_2 (deps, XEXP (x, i), insn);
2821 else if (fmt[i] == 'E')
2822 for (j = 0; j < XVECLEN (x, i); j++)
2823 sched_analyze_2 (deps, XVECEXP (x, i, j), insn);
2824 }
2825
2826 if (cslr_p && sched_deps_info->finish_rhs)
2827 sched_deps_info->finish_rhs ();
2828}
2829
2830/* Try to group two fusible insns together to prevent scheduler
2831 from scheduling them apart. */
2832
2833static void
2834sched_macro_fuse_insns (rtx_insn *insn)
2835{
2836 rtx_insn *prev;
2837 prev = prev_nonnote_nondebug_insn (insn);
2838 if (!prev)
2839 return;
2840
2841 if (any_condjump_p (insn))
2842 {
2843 unsigned int condreg1, condreg2;
2844 rtx cc_reg_1;
2845 targetm.fixed_condition_code_regs (&condreg1, &condreg2);
2846 cc_reg_1 = gen_rtx_REG (CCmode, condreg1);
2847 if (reg_referenced_p (cc_reg_1, PATTERN (insn))
2848 && modified_in_p (cc_reg_1, prev))
2849 {
2850 if (targetm.sched.macro_fusion_pair_p (prev, insn))
2851 SCHED_GROUP_P (insn) = 1;
2852 return;
2853 }
2854 }
2855
2856 if (single_set (insn) && single_set (prev))
2857 {
2858 if (targetm.sched.macro_fusion_pair_p (prev, insn))
2859 SCHED_GROUP_P (insn) = 1;
2860 }
2861}
2862
2863/* Get the implicit reg pending clobbers for INSN and save them in TEMP. */
2864void
2865get_implicit_reg_pending_clobbers (HARD_REG_SET *temp, rtx_insn *insn)
2866{
2867 extract_insn (insn);
2868 preprocess_constraints (insn);
2869 alternative_mask preferred = get_preferred_alternatives (insn);
2870 ira_implicitly_set_insn_hard_regs (temp, preferred);
2871 AND_COMPL_HARD_REG_SET (*temp, ira_no_alloc_regs);
2872}
2873
2874/* Analyze an INSN with pattern X to find all dependencies. */
2875static void
2876sched_analyze_insn (struct deps_desc *deps, rtx x, rtx_insn *insn)
2877{
2878 RTX_CODE code = GET_CODE (x);
2879 rtx link;
2880 unsigned i;
2881 reg_set_iterator rsi;
2882
2883 if (! reload_completed)
2884 {
2885 HARD_REG_SET temp;
2886 get_implicit_reg_pending_clobbers (&temp, insn);
2887 IOR_HARD_REG_SET (implicit_reg_pending_clobbers, temp);
2888 }
2889
2890 can_start_lhs_rhs_p = (NONJUMP_INSN_P (insn)
2891 && code == SET);
2892
2893 /* Group compare and branch insns for macro-fusion. */
2894 if (targetm.sched.macro_fusion_p
2895 && targetm.sched.macro_fusion_p ())
2896 sched_macro_fuse_insns (insn);
2897
2898 if (may_trap_p (x))
2899 /* Avoid moving trapping instructions across function calls that might
2900 not always return. */
2901 add_dependence_list (insn, deps->last_function_call_may_noreturn,
2902 1, REG_DEP_ANTI, true);
2903
2904 /* We must avoid creating a situation in which two successors of the
2905 current block have different unwind info after scheduling. If at any
2906 point the two paths re-join this leads to incorrect unwind info. */
2907 /* ??? There are certain situations involving a forced frame pointer in
2908 which, with extra effort, we could fix up the unwind info at a later
2909 CFG join. However, it seems better to notice these cases earlier
2910 during prologue generation and avoid marking the frame pointer setup
2911 as frame-related at all. */
2912 if (RTX_FRAME_RELATED_P (insn))
2913 {
2914 /* Make sure prologue insn is scheduled before next jump. */
2915 deps->sched_before_next_jump
2916 = alloc_INSN_LIST (insn, deps->sched_before_next_jump);
2917
2918 /* Make sure epilogue insn is scheduled after preceding jumps. */
2919 add_dependence_list (insn, deps->pending_jump_insns, 1, REG_DEP_ANTI,
2920 true);
2921 }
2922
2923 if (code == COND_EXEC)
2924 {
2925 sched_analyze_2 (deps, COND_EXEC_TEST (x), insn);
2926
2927 /* ??? Should be recording conditions so we reduce the number of
2928 false dependencies. */
2929 x = COND_EXEC_CODE (x);
2930 code = GET_CODE (x);
2931 }
2932 if (code == SET || code == CLOBBER)
2933 {
2934 sched_analyze_1 (deps, x, insn);
2935
2936 /* Bare clobber insns are used for letting life analysis, reg-stack
2937 and others know that a value is dead. Depend on the last call
2938 instruction so that reg-stack won't get confused. */
2939 if (code == CLOBBER)
2940 add_dependence_list (insn, deps->last_function_call, 1,
2941 REG_DEP_OUTPUT, true);
2942 }
2943 else if (code == PARALLEL)
2944 {
2945 for (i = XVECLEN (x, 0); i--;)
2946 {
2947 rtx sub = XVECEXP (x, 0, i);
2948 code = GET_CODE (sub);
2949
2950 if (code == COND_EXEC)
2951 {
2952 sched_analyze_2 (deps, COND_EXEC_TEST (sub), insn);
2953 sub = COND_EXEC_CODE (sub);
2954 code = GET_CODE (sub);
2955 }
2956 if (code == SET || code == CLOBBER)
2957 sched_analyze_1 (deps, sub, insn);
2958 else
2959 sched_analyze_2 (deps, sub, insn);
2960 }
2961 }
2962 else
2963 sched_analyze_2 (deps, x, insn);
2964
2965 /* Mark registers CLOBBERED or used by called function. */
2966 if (CALL_P (insn))
2967 {
2968 for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1))
2969 {
2970 if (GET_CODE (XEXP (link, 0)) == CLOBBER)
2971 sched_analyze_1 (deps, XEXP (link, 0), insn);
2972 else if (GET_CODE (XEXP (link, 0)) != SET)
2973 sched_analyze_2 (deps, XEXP (link, 0), insn);
2974 }
2975 /* Don't schedule anything after a tail call, tail call needs
2976 to use at least all call-saved registers. */
2977 if (SIBLING_CALL_P (insn))
2978 reg_pending_barrier = TRUE_BARRIER;
2979 else if (find_reg_note (insn, REG_SETJMP, NULL))
2980 reg_pending_barrier = MOVE_BARRIER;
2981 }
2982
2983 if (JUMP_P (insn))
2984 {
2985 rtx_insn *next = next_nonnote_nondebug_insn (insn);
2986 if (next && BARRIER_P (next))
2987 reg_pending_barrier = MOVE_BARRIER;
2988 else
2989 {
2990 rtx_insn_list *pending;
2991 rtx_expr_list *pending_mem;
2992
2993 if (sched_deps_info->compute_jump_reg_dependencies)
2994 {
2995 (*sched_deps_info->compute_jump_reg_dependencies)
2996 (insn, reg_pending_control_uses);
2997
2998 /* Make latency of jump equal to 0 by using anti-dependence. */
2999 EXECUTE_IF_SET_IN_REG_SET (reg_pending_control_uses, 0, i, rsi)
3000 {
3001 struct deps_reg *reg_last = &deps->reg_last[i];
3002 add_dependence_list (insn, reg_last->sets, 0, REG_DEP_ANTI,
3003 false);
3004 add_dependence_list (insn, reg_last->implicit_sets,
3005 0, REG_DEP_ANTI, false);
3006 add_dependence_list (insn, reg_last->clobbers, 0,
3007 REG_DEP_ANTI, false);
3008 }
3009 }
3010
3011 /* All memory writes and volatile reads must happen before the
3012 jump. Non-volatile reads must happen before the jump iff
3013 the result is needed by the above register used mask. */
3014
3015 pending = deps->pending_write_insns;
3016 pending_mem = deps->pending_write_mems;
3017 while (pending)
3018 {
3019 if (! sched_insns_conditions_mutex_p (insn, pending->insn ()))
3020 add_dependence (insn, pending->insn (),
3021 REG_DEP_OUTPUT);
3022 pending = pending->next ();
3023 pending_mem = pending_mem->next ();
3024 }
3025
3026 pending = deps->pending_read_insns;
3027 pending_mem = deps->pending_read_mems;
3028 while (pending)
3029 {
3030 if (MEM_VOLATILE_P (pending_mem->element ())
3031 && ! sched_insns_conditions_mutex_p (insn, pending->insn ()))
3032 add_dependence (insn, pending->insn (),
3033 REG_DEP_OUTPUT);
3034 pending = pending->next ();
3035 pending_mem = pending_mem->next ();
3036 }
3037
3038 add_dependence_list (insn, deps->last_pending_memory_flush, 1,
3039 REG_DEP_ANTI, true);
3040 add_dependence_list (insn, deps->pending_jump_insns, 1,
3041 REG_DEP_ANTI, true);
3042 }
3043 }
3044
3045 /* If this instruction can throw an exception, then moving it changes
3046 where block boundaries fall. This is mighty confusing elsewhere.
3047 Therefore, prevent such an instruction from being moved. Same for
3048 non-jump instructions that define block boundaries.
3049 ??? Unclear whether this is still necessary in EBB mode. If not,
3050 add_branch_dependences should be adjusted for RGN mode instead. */
3051 if (((CALL_P (insn) || JUMP_P (insn)) && can_throw_internal (insn))
3052 || (NONJUMP_INSN_P (insn) && control_flow_insn_p (insn)))
3053 reg_pending_barrier = MOVE_BARRIER;
3054
3055 if (sched_pressure != SCHED_PRESSURE_NONE)
3056 {
3057 setup_insn_reg_uses (deps, insn);
3058 init_insn_reg_pressure_info (insn);
3059 }
3060
3061 /* Add register dependencies for insn. */
3062 if (DEBUG_INSN_P (insn))
3063 {
3064 rtx_insn *prev = deps->last_debug_insn;
3065 rtx_insn_list *u;
3066
3067 if (!deps->readonly)
3068 deps->last_debug_insn = insn;
3069
3070 if (prev)
3071 add_dependence (insn, prev, REG_DEP_ANTI);
3072
3073 add_dependence_list (insn, deps->last_function_call, 1,
3074 REG_DEP_ANTI, false);
3075
3076 if (!sel_sched_p ())
3077 for (u = deps->last_pending_memory_flush; u; u = u->next ())
3078 add_dependence (insn, u->insn (), REG_DEP_ANTI);
3079
3080 EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i, rsi)
3081 {
3082 struct deps_reg *reg_last = &deps->reg_last[i];
3083 add_dependence_list (insn, reg_last->sets, 1, REG_DEP_ANTI, false);
3084 /* There's no point in making REG_DEP_CONTROL dependencies for
3085 debug insns. */
3086 add_dependence_list (insn, reg_last->clobbers, 1, REG_DEP_ANTI,
3087 false);
3088
3089 if (!deps->readonly)
3090 reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
3091 }
3092 CLEAR_REG_SET (reg_pending_uses);
3093
3094 /* Quite often, a debug insn will refer to stuff in the
3095 previous instruction, but the reason we want this
3096 dependency here is to make sure the scheduler doesn't
3097 gratuitously move a debug insn ahead. This could dirty
3098 DF flags and cause additional analysis that wouldn't have
3099 occurred in compilation without debug insns, and such
3100 additional analysis can modify the generated code. */
3101 prev = PREV_INSN (insn);
3102
3103 if (prev && NONDEBUG_INSN_P (prev))
3104 add_dependence (insn, prev, REG_DEP_ANTI);
3105 }
3106 else
3107 {
3108 regset_head set_or_clobbered;
3109
3110 EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i, rsi)
3111 {
3112 struct deps_reg *reg_last = &deps->reg_last[i];
3113 add_dependence_list (insn, reg_last->sets, 0, REG_DEP_TRUE, false);
3114 add_dependence_list (insn, reg_last->implicit_sets, 0, REG_DEP_ANTI,
3115 false);
3116 add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_TRUE,
3117 false);
3118
3119 if (!deps->readonly)
3120 {
3121 reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
3122 reg_last->uses_length++;
3123 }
3124 }
3125
3126 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3127 if (TEST_HARD_REG_BIT (implicit_reg_pending_uses, i))
3128 {
3129 struct deps_reg *reg_last = &deps->reg_last[i];
3130 add_dependence_list (insn, reg_last->sets, 0, REG_DEP_TRUE, false);
3131 add_dependence_list (insn, reg_last->implicit_sets, 0,
3132 REG_DEP_ANTI, false);
3133 add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_TRUE,
3134 false);
3135
3136 if (!deps->readonly)
3137 {
3138 reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
3139 reg_last->uses_length++;
3140 }
3141 }
3142
3143 if (targetm.sched.exposed_pipeline)
3144 {
3145 INIT_REG_SET (&set_or_clobbered);
3146 bitmap_ior (&set_or_clobbered, reg_pending_clobbers,
3147 reg_pending_sets);
3148 EXECUTE_IF_SET_IN_REG_SET (&set_or_clobbered, 0, i, rsi)
3149 {
3150 struct deps_reg *reg_last = &deps->reg_last[i];
3151 rtx list;
3152 for (list = reg_last->uses; list; list = XEXP (list, 1))
3153 {
3154 rtx other = XEXP (list, 0);
3155 if (INSN_CACHED_COND (other) != const_true_rtx
3156 && refers_to_regno_p (i, INSN_CACHED_COND (other)))
3157 INSN_CACHED_COND (other) = const_true_rtx;
3158 }
3159 }
3160 }
3161
3162 /* If the current insn is conditional, we can't free any
3163 of the lists. */
3164 if (sched_has_condition_p (insn))
3165 {
3166 EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers, 0, i, rsi)
3167 {
3168 struct deps_reg *reg_last = &deps->reg_last[i];
3169 add_dependence_list (insn, reg_last->sets, 0, REG_DEP_OUTPUT,
3170 false);
3171 add_dependence_list (insn, reg_last->implicit_sets, 0,
3172 REG_DEP_ANTI, false);
3173 add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI,
3174 false);
3175 add_dependence_list (insn, reg_last->control_uses, 0,
3176 REG_DEP_CONTROL, false);
3177
3178 if (!deps->readonly)
3179 {
3180 reg_last->clobbers
3181 = alloc_INSN_LIST (insn, reg_last->clobbers);
3182 reg_last->clobbers_length++;
3183 }
3184 }
3185 EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets, 0, i, rsi)
3186 {
3187 struct deps_reg *reg_last = &deps->reg_last[i];
3188 add_dependence_list (insn, reg_last->sets, 0, REG_DEP_OUTPUT,
3189 false);
3190 add_dependence_list (insn, reg_last->implicit_sets, 0,
3191 REG_DEP_ANTI, false);
3192 add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_OUTPUT,
3193 false);
3194 add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI,
3195 false);
3196 add_dependence_list (insn, reg_last->control_uses, 0,
3197 REG_DEP_CONTROL, false);
3198
3199 if (!deps->readonly)
3200 reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
3201 }
3202 }
3203 else
3204 {
3205 EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers, 0, i, rsi)
3206 {
3207 struct deps_reg *reg_last = &deps->reg_last[i];
3208 if (reg_last->uses_length >= MAX_PENDING_LIST_LENGTH
3209 || reg_last->clobbers_length >= MAX_PENDING_LIST_LENGTH)
3210 {
3211 add_dependence_list_and_free (deps, insn, &reg_last->sets, 0,
3212 REG_DEP_OUTPUT, false);
3213 add_dependence_list_and_free (deps, insn,
3214 &reg_last->implicit_sets, 0,
3215 REG_DEP_ANTI, false);
3216 add_dependence_list_and_free (deps, insn, &reg_last->uses, 0,
3217 REG_DEP_ANTI, false);
3218 add_dependence_list_and_free (deps, insn,
3219 &reg_last->control_uses, 0,
3220 REG_DEP_ANTI, false);
3221 add_dependence_list_and_free (deps, insn,
3222 &reg_last->clobbers, 0,
3223 REG_DEP_OUTPUT, false);
3224
3225 if (!deps->readonly)
3226 {
3227 reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
3228 reg_last->clobbers_length = 0;
3229 reg_last->uses_length = 0;
3230 }
3231 }
3232 else
3233 {
3234 add_dependence_list (insn, reg_last->sets, 0, REG_DEP_OUTPUT,
3235 false);
3236 add_dependence_list (insn, reg_last->implicit_sets, 0,
3237 REG_DEP_ANTI, false);
3238 add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI,
3239 false);
3240 add_dependence_list (insn, reg_last->control_uses, 0,
3241 REG_DEP_CONTROL, false);
3242 }
3243
3244 if (!deps->readonly)
3245 {
3246 reg_last->clobbers_length++;
3247 reg_last->clobbers
3248 = alloc_INSN_LIST (insn, reg_last->clobbers);
3249 }
3250 }
3251 EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets, 0, i, rsi)
3252 {
3253 struct deps_reg *reg_last = &deps->reg_last[i];
3254
3255 add_dependence_list_and_free (deps, insn, &reg_last->sets, 0,
3256 REG_DEP_OUTPUT, false);
3257 add_dependence_list_and_free (deps, insn,
3258 &reg_last->implicit_sets,
3259 0, REG_DEP_ANTI, false);
3260 add_dependence_list_and_free (deps, insn, &reg_last->clobbers, 0,
3261 REG_DEP_OUTPUT, false);
3262 add_dependence_list_and_free (deps, insn, &reg_last->uses, 0,
3263 REG_DEP_ANTI, false);
3264 add_dependence_list (insn, reg_last->control_uses, 0,
3265 REG_DEP_CONTROL, false);
3266
3267 if (!deps->readonly)
3268 {
3269 reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
3270 reg_last->uses_length = 0;
3271 reg_last->clobbers_length = 0;
3272 }
3273 }
3274 }
3275 if (!deps->readonly)
3276 {
3277 EXECUTE_IF_SET_IN_REG_SET (reg_pending_control_uses, 0, i, rsi)
3278 {
3279 struct deps_reg *reg_last = &deps->reg_last[i];
3280 reg_last->control_uses
3281 = alloc_INSN_LIST (insn, reg_last->control_uses);
3282 }
3283 }
3284 }
3285
3286 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3287 if (TEST_HARD_REG_BIT (implicit_reg_pending_clobbers, i))
3288 {
3289 struct deps_reg *reg_last = &deps->reg_last[i];
3290 add_dependence_list (insn, reg_last->sets, 0, REG_DEP_ANTI, false);
3291 add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_ANTI, false);
3292 add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI, false);
3293 add_dependence_list (insn, reg_last->control_uses, 0, REG_DEP_ANTI,
3294 false);
3295
3296 if (!deps->readonly)
3297 reg_last->implicit_sets
3298 = alloc_INSN_LIST (insn, reg_last->implicit_sets);
3299 }
3300
3301 if (!deps->readonly)
3302 {
3303 IOR_REG_SET (&deps->reg_last_in_use, reg_pending_uses);
3304 IOR_REG_SET (&deps->reg_last_in_use, reg_pending_clobbers);
3305 IOR_REG_SET (&deps->reg_last_in_use, reg_pending_sets);
3306 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3307 if (TEST_HARD_REG_BIT (implicit_reg_pending_uses, i)
3308 || TEST_HARD_REG_BIT (implicit_reg_pending_clobbers, i))
3309 SET_REGNO_REG_SET (&deps->reg_last_in_use, i);
3310
3311 /* Set up the pending barrier found. */
3312 deps->last_reg_pending_barrier = reg_pending_barrier;
3313 }
3314
3315 CLEAR_REG_SET (reg_pending_uses);
3316 CLEAR_REG_SET (reg_pending_clobbers);
3317 CLEAR_REG_SET (reg_pending_sets);
3318 CLEAR_REG_SET (reg_pending_control_uses);
3319 CLEAR_HARD_REG_SET (implicit_reg_pending_clobbers);
3320 CLEAR_HARD_REG_SET (implicit_reg_pending_uses);
3321
3322 /* Add dependencies if a scheduling barrier was found. */
3323 if (reg_pending_barrier)
3324 {
3325 /* In the case of barrier the most added dependencies are not
3326 real, so we use anti-dependence here. */
3327 if (sched_has_condition_p (insn))
3328 {
3329 EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
3330 {
3331 struct deps_reg *reg_last = &deps->reg_last[i];
3332 add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI,
3333 true);
3334 add_dependence_list (insn, reg_last->sets, 0,
3335 reg_pending_barrier == TRUE_BARRIER
3336 ? REG_DEP_TRUE : REG_DEP_ANTI, true);
3337 add_dependence_list (insn, reg_last->implicit_sets, 0,
3338 REG_DEP_ANTI, true);
3339 add_dependence_list (insn, reg_last->clobbers, 0,
3340 reg_pending_barrier == TRUE_BARRIER
3341 ? REG_DEP_TRUE : REG_DEP_ANTI, true);
3342 }
3343 }
3344 else
3345 {
3346 EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
3347 {
3348 struct deps_reg *reg_last = &deps->reg_last[i];
3349 add_dependence_list_and_free (deps, insn, &reg_last->uses, 0,
3350 REG_DEP_ANTI, true);
3351 add_dependence_list_and_free (deps, insn,
3352 &reg_last->control_uses, 0,
3353 REG_DEP_CONTROL, true);
3354 add_dependence_list_and_free (deps, insn, &reg_last->sets, 0,
3355 reg_pending_barrier == TRUE_BARRIER
3356 ? REG_DEP_TRUE : REG_DEP_ANTI,
3357 true);
3358 add_dependence_list_and_free (deps, insn,
3359 &reg_last->implicit_sets, 0,
3360 REG_DEP_ANTI, true);
3361 add_dependence_list_and_free (deps, insn, &reg_last->clobbers, 0,
3362 reg_pending_barrier == TRUE_BARRIER
3363 ? REG_DEP_TRUE : REG_DEP_ANTI,
3364 true);
3365
3366 if (!deps->readonly)
3367 {
3368 reg_last->uses_length = 0;
3369 reg_last->clobbers_length = 0;
3370 }
3371 }
3372 }
3373
3374 if (!deps->readonly)
3375 for (i = 0; i < (unsigned)deps->max_reg; i++)
3376 {
3377 struct deps_reg *reg_last = &deps->reg_last[i];
3378 reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
3379 SET_REGNO_REG_SET (&deps->reg_last_in_use, i);
3380 }
3381
3382 /* Don't flush pending lists on speculative checks for
3383 selective scheduling. */
3384 if (!sel_sched_p () || !sel_insn_is_speculation_check (insn))
3385 flush_pending_lists (deps, insn, true, true);
3386
3387 reg_pending_barrier = NOT_A_BARRIER;
3388 }
3389
3390 /* If a post-call group is still open, see if it should remain so.
3391 This insn must be a simple move of a hard reg to a pseudo or
3392 vice-versa.
3393
3394 We must avoid moving these insns for correctness on targets
3395 with small register classes, and for special registers like
3396 PIC_OFFSET_TABLE_REGNUM. For simplicity, extend this to all
3397 hard regs for all targets. */
3398
3399 if (deps->in_post_call_group_p)
3400 {
3401 rtx tmp, set = single_set (insn);
3402 int src_regno, dest_regno;
3403
3404 if (set == NULL)
3405 {
3406 if (DEBUG_INSN_P (insn))
3407 /* We don't want to mark debug insns as part of the same
3408 sched group. We know they really aren't, but if we use
3409 debug insns to tell that a call group is over, we'll
3410 get different code if debug insns are not there and
3411 instructions that follow seem like they should be part
3412 of the call group.
3413
3414 Also, if we did, chain_to_prev_insn would move the
3415 deps of the debug insn to the call insn, modifying
3416 non-debug post-dependency counts of the debug insn
3417 dependencies and otherwise messing with the scheduling
3418 order.
3419
3420 Instead, let such debug insns be scheduled freely, but
3421 keep the call group open in case there are insns that
3422 should be part of it afterwards. Since we grant debug
3423 insns higher priority than even sched group insns, it
3424 will all turn out all right. */
3425 goto debug_dont_end_call_group;
3426 else
3427 goto end_call_group;
3428 }
3429
3430 tmp = SET_DEST (set);
3431 if (GET_CODE (tmp) == SUBREG)
3432 tmp = SUBREG_REG (tmp);
3433 if (REG_P (tmp))
3434 dest_regno = REGNO (tmp);
3435 else
3436 goto end_call_group;
3437
3438 tmp = SET_SRC (set);
3439 if (GET_CODE (tmp) == SUBREG)
3440 tmp = SUBREG_REG (tmp);
3441 if ((GET_CODE (tmp) == PLUS
3442 || GET_CODE (tmp) == MINUS)
3443 && REG_P (XEXP (tmp, 0))
3444 && REGNO (XEXP (tmp, 0)) == STACK_POINTER_REGNUM
3445 && dest_regno == STACK_POINTER_REGNUM)
3446 src_regno = STACK_POINTER_REGNUM;
3447 else if (REG_P (tmp))
3448 src_regno = REGNO (tmp);
3449 else
3450 goto end_call_group;
3451
3452 if (src_regno < FIRST_PSEUDO_REGISTER
3453 || dest_regno < FIRST_PSEUDO_REGISTER)
3454 {
3455 if (!deps->readonly
3456 && deps->in_post_call_group_p == post_call_initial)
3457 deps->in_post_call_group_p = post_call;
3458
3459 if (!sel_sched_p () || sched_emulate_haifa_p)
3460 {
3461 SCHED_GROUP_P (insn) = 1;
3462 CANT_MOVE (insn) = 1;
3463 }
3464 }
3465 else
3466 {
3467 end_call_group:
3468 if (!deps->readonly)
3469 deps->in_post_call_group_p = not_post_call;
3470 }
3471 }
3472
3473 debug_dont_end_call_group:
3474 if ((current_sched_info->flags & DO_SPECULATION)
3475 && !sched_insn_is_legitimate_for_speculation_p (insn, 0))
3476 /* INSN has an internal dependency (e.g. r14 = [r14]) and thus cannot
3477 be speculated. */
3478 {
3479 if (sel_sched_p ())
3480 sel_mark_hard_insn (insn);
3481 else
3482 {
3483 sd_iterator_def sd_it;
3484 dep_t dep;
3485
3486 for (sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK);
3487 sd_iterator_cond (&sd_it, &dep);)
3488 change_spec_dep_to_hard (sd_it);
3489 }
3490 }
3491
3492 /* We do not yet have code to adjust REG_ARGS_SIZE, therefore we must
3493 honor their original ordering. */
3494 if (find_reg_note (insn, REG_ARGS_SIZE, NULL))
3495 {
3496 if (deps->last_args_size)
3497 add_dependence (insn, deps->last_args_size, REG_DEP_OUTPUT);
3498 if (!deps->readonly)
3499 deps->last_args_size = insn;
3500 }
3501
3502 /* We must not mix prologue and epilogue insns. See PR78029. */
3503 if (prologue_contains (insn))
3504 {
3505 add_dependence_list (insn, deps->last_epilogue, true, REG_DEP_ANTI, true);
3506 if (!deps->readonly)
3507 {
3508 if (deps->last_logue_was_epilogue)
3509 free_INSN_LIST_list (&deps->last_prologue);
3510 deps->last_prologue = alloc_INSN_LIST (insn, deps->last_prologue);
3511 deps->last_logue_was_epilogue = false;
3512 }
3513 }
3514
3515 if (epilogue_contains (insn))
3516 {
3517 add_dependence_list (insn, deps->last_prologue, true, REG_DEP_ANTI, true);
3518 if (!deps->readonly)
3519 {
3520 if (!deps->last_logue_was_epilogue)
3521 free_INSN_LIST_list (&deps->last_epilogue);
3522 deps->last_epilogue = alloc_INSN_LIST (insn, deps->last_epilogue);
3523 deps->last_logue_was_epilogue = true;
3524 }
3525 }
3526}
3527
3528/* Return TRUE if INSN might not always return normally (e.g. call exit,
3529 longjmp, loop forever, ...). */
3530/* FIXME: Why can't this function just use flags_from_decl_or_type and
3531 test for ECF_NORETURN? */
3532static bool
3533call_may_noreturn_p (rtx_insn *insn)
3534{
3535 rtx call;
3536
3537 /* const or pure calls that aren't looping will always return. */
3538 if (RTL_CONST_OR_PURE_CALL_P (insn)
3539 && !RTL_LOOPING_CONST_OR_PURE_CALL_P (insn))
3540 return false;
3541
3542 call = get_call_rtx_from (insn);
3543 if (call && GET_CODE (XEXP (XEXP (call, 0), 0)) == SYMBOL_REF)
3544 {
3545 rtx symbol = XEXP (XEXP (call, 0), 0);
3546 if (SYMBOL_REF_DECL (symbol)
3547 && TREE_CODE (SYMBOL_REF_DECL (symbol)) == FUNCTION_DECL)
3548 {
3549 if (DECL_BUILT_IN_CLASS (SYMBOL_REF_DECL (symbol))
3550 == BUILT_IN_NORMAL)
3551 switch (DECL_FUNCTION_CODE (SYMBOL_REF_DECL (symbol)))
3552 {
3553 case BUILT_IN_BCMP:
3554 case BUILT_IN_BCOPY:
3555 case BUILT_IN_BZERO:
3556 case BUILT_IN_INDEX:
3557 case BUILT_IN_MEMCHR:
3558 case BUILT_IN_MEMCMP:
3559 case BUILT_IN_MEMCPY:
3560 case BUILT_IN_MEMMOVE:
3561 case BUILT_IN_MEMPCPY:
3562 case BUILT_IN_MEMSET:
3563 case BUILT_IN_RINDEX:
3564 case BUILT_IN_STPCPY:
3565 case BUILT_IN_STPNCPY:
3566 case BUILT_IN_STRCAT:
3567 case BUILT_IN_STRCHR:
3568 case BUILT_IN_STRCMP:
3569 case BUILT_IN_STRCPY:
3570 case BUILT_IN_STRCSPN:
3571 case BUILT_IN_STRLEN:
3572 case BUILT_IN_STRNCAT:
3573 case BUILT_IN_STRNCMP:
3574 case BUILT_IN_STRNCPY:
3575 case BUILT_IN_STRPBRK:
3576 case BUILT_IN_STRRCHR:
3577 case BUILT_IN_STRSPN:
3578 case BUILT_IN_STRSTR:
3579 /* Assume certain string/memory builtins always return. */
3580 return false;
3581 default:
3582 break;
3583 }
3584 }
3585 }
3586
3587 /* For all other calls assume that they might not always return. */
3588 return true;
3589}
3590
3591/* Return true if INSN should be made dependent on the previous instruction
3592 group, and if all INSN's dependencies should be moved to the first
3593 instruction of that group. */
3594
3595static bool
3596chain_to_prev_insn_p (rtx_insn *insn)
3597{
3598 /* INSN forms a group with the previous instruction. */
3599 if (SCHED_GROUP_P (insn))
3600 return true;
3601
3602 /* If the previous instruction clobbers a register R and this one sets
3603 part of R, the clobber was added specifically to help us track the
3604 liveness of R. There's no point scheduling the clobber and leaving
3605 INSN behind, especially if we move the clobber to another block. */
3606 rtx_insn *prev = prev_nonnote_nondebug_insn (insn);
3607 if (prev
3608 && INSN_P (prev)
3609 && BLOCK_FOR_INSN (prev) == BLOCK_FOR_INSN (insn)
3610 && GET_CODE (PATTERN (prev)) == CLOBBER)
3611 {
3612 rtx x = XEXP (PATTERN (prev), 0);
3613 if (set_of (x, insn))
3614 return true;
3615 }
3616
3617 return false;
3618}
3619
3620/* Analyze INSN with DEPS as a context. */
3621void
3622deps_analyze_insn (struct deps_desc *deps, rtx_insn *insn)
3623{
3624 if (sched_deps_info->start_insn)
3625 sched_deps_info->start_insn (insn);
3626
3627 /* Record the condition for this insn. */
3628 if (NONDEBUG_INSN_P (insn))
3629 {
3630 rtx t;
3631 sched_get_condition_with_rev (insn, NULL);
3632 t = INSN_CACHED_COND (insn);
3633 INSN_COND_DEPS (insn) = NULL;
3634 if (reload_completed
3635 && (current_sched_info->flags & DO_PREDICATION)
3636 && COMPARISON_P (t)
3637 && REG_P (XEXP (t, 0))
3638 && CONSTANT_P (XEXP (t, 1)))
3639 {
3640 unsigned int regno;
3641 int nregs;
3642 rtx_insn_list *cond_deps = NULL;
3643 t = XEXP (t, 0);
3644 regno = REGNO (t);
3645 nregs = REG_NREGS (t);
3646 while (nregs-- > 0)
3647 {
3648 struct deps_reg *reg_last = &deps->reg_last[regno + nregs];
3649 cond_deps = concat_INSN_LIST (reg_last->sets, cond_deps);
3650 cond_deps = concat_INSN_LIST (reg_last->clobbers, cond_deps);
3651 cond_deps = concat_INSN_LIST (reg_last->implicit_sets, cond_deps);
3652 }
3653 INSN_COND_DEPS (insn) = cond_deps;
3654 }
3655 }
3656
3657 if (JUMP_P (insn))
3658 {
3659 /* Make each JUMP_INSN (but not a speculative check)
3660 a scheduling barrier for memory references. */
3661 if (!deps->readonly
3662 && !(sel_sched_p ()
3663 && sel_insn_is_speculation_check (insn)))
3664 {
3665 /* Keep the list a reasonable size. */
3666 if (deps->pending_flush_length++ >= MAX_PENDING_LIST_LENGTH)
3667 flush_pending_lists (deps, insn, true, true);
3668 else
3669 deps->pending_jump_insns
3670 = alloc_INSN_LIST (insn, deps->pending_jump_insns);
3671 }
3672
3673 /* For each insn which shouldn't cross a jump, add a dependence. */
3674 add_dependence_list_and_free (deps, insn,
3675 &deps->sched_before_next_jump, 1,
3676 REG_DEP_ANTI, true);
3677
3678 sched_analyze_insn (deps, PATTERN (insn), insn);
3679 }
3680 else if (NONJUMP_INSN_P (insn) || DEBUG_INSN_P (insn))
3681 {
3682 sched_analyze_insn (deps, PATTERN (insn), insn);
3683 }
3684 else if (CALL_P (insn))
3685 {
3686 int i;
3687
3688 CANT_MOVE (insn) = 1;
3689
3690 if (find_reg_note (insn, REG_SETJMP, NULL))
3691 {
3692 /* This is setjmp. Assume that all registers, not just
3693 hard registers, may be clobbered by this call. */
3694 reg_pending_barrier = MOVE_BARRIER;
3695 }
3696 else
3697 {
3698 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3699 /* A call may read and modify global register variables. */
3700 if (global_regs[i])
3701 {
3702 SET_REGNO_REG_SET (reg_pending_sets, i);
3703 SET_HARD_REG_BIT (implicit_reg_pending_uses, i);
3704 }
3705 /* Other call-clobbered hard regs may be clobbered.
3706 Since we only have a choice between 'might be clobbered'
3707 and 'definitely not clobbered', we must include all
3708 partly call-clobbered registers here. */
3709 else if (targetm.hard_regno_call_part_clobbered (i,
3710 reg_raw_mode[i])
3711 || TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
3712 SET_REGNO_REG_SET (reg_pending_clobbers, i);
3713 /* We don't know what set of fixed registers might be used
3714 by the function, but it is certain that the stack pointer
3715 is among them, but be conservative. */
3716 else if (fixed_regs[i])
3717 SET_HARD_REG_BIT (implicit_reg_pending_uses, i);
3718 /* The frame pointer is normally not used by the function
3719 itself, but by the debugger. */
3720 /* ??? MIPS o32 is an exception. It uses the frame pointer
3721 in the macro expansion of jal but does not represent this
3722 fact in the call_insn rtl. */
3723 else if (i == FRAME_POINTER_REGNUM
3724 || (i == HARD_FRAME_POINTER_REGNUM
3725 && (! reload_completed || frame_pointer_needed)))
3726 SET_HARD_REG_BIT (implicit_reg_pending_uses, i);
3727 }
3728
3729 /* For each insn which shouldn't cross a call, add a dependence
3730 between that insn and this call insn. */
3731 add_dependence_list_and_free (deps, insn,
3732 &deps->sched_before_next_call, 1,
3733 REG_DEP_ANTI, true);
3734
3735 sched_analyze_insn (deps, PATTERN (insn), insn);
3736
3737 /* If CALL would be in a sched group, then this will violate
3738 convention that sched group insns have dependencies only on the
3739 previous instruction.
3740
3741 Of course one can say: "Hey! What about head of the sched group?"
3742 And I will answer: "Basic principles (one dep per insn) are always
3743 the same." */
3744 gcc_assert (!SCHED_GROUP_P (insn));
3745
3746 /* In the absence of interprocedural alias analysis, we must flush
3747 all pending reads and writes, and start new dependencies starting
3748 from here. But only flush writes for constant calls (which may
3749 be passed a pointer to something we haven't written yet). */
3750 flush_pending_lists (deps, insn, true, ! RTL_CONST_OR_PURE_CALL_P (insn));
3751
3752 if (!deps->readonly)
3753 {
3754 /* Remember the last function call for limiting lifetimes. */
3755 free_INSN_LIST_list (&deps->last_function_call);
3756 deps->last_function_call = alloc_INSN_LIST (insn, NULL_RTX);
3757
3758 if (call_may_noreturn_p (insn))
3759 {
3760 /* Remember the last function call that might not always return
3761 normally for limiting moves of trapping insns. */
3762 free_INSN_LIST_list (&deps->last_function_call_may_noreturn);
3763 deps->last_function_call_may_noreturn
3764 = alloc_INSN_LIST (insn, NULL_RTX);
3765 }
3766
3767 /* Before reload, begin a post-call group, so as to keep the
3768 lifetimes of hard registers correct. */
3769 if (! reload_completed)
3770 deps->in_post_call_group_p = post_call;
3771 }
3772 }
3773
3774 if (sched_deps_info->use_cselib)
3775 cselib_process_insn (insn);
3776
3777 if (sched_deps_info->finish_insn)
3778 sched_deps_info->finish_insn ();
3779
3780 /* Fixup the dependencies in the sched group. */
3781 if ((NONJUMP_INSN_P (insn) || JUMP_P (insn))
3782 && chain_to_prev_insn_p (insn)
3783 && !sel_sched_p ())
3784 chain_to_prev_insn (insn);
3785}
3786
3787/* Initialize DEPS for the new block beginning with HEAD. */
3788void
3789deps_start_bb (struct deps_desc *deps, rtx_insn *head)
3790{
3791 gcc_assert (!deps->readonly);
3792
3793 /* Before reload, if the previous block ended in a call, show that
3794 we are inside a post-call group, so as to keep the lifetimes of
3795 hard registers correct. */
3796 if (! reload_completed && !LABEL_P (head))
3797 {
3798 rtx_insn *insn = prev_nonnote_nondebug_insn (head);
3799
3800 if (insn && CALL_P (insn))
3801 deps->in_post_call_group_p = post_call_initial;
3802 }
3803}
3804
3805/* Analyze every insn between HEAD and TAIL inclusive, creating backward
3806 dependencies for each insn. */
3807void
3808sched_analyze (struct deps_desc *deps, rtx_insn *head, rtx_insn *tail)
3809{
3810 rtx_insn *insn;
3811
3812 if (sched_deps_info->use_cselib)
3813 cselib_init (CSELIB_RECORD_MEMORY);
3814
3815 deps_start_bb (deps, head);
3816
3817 for (insn = head;; insn = NEXT_INSN (insn))
3818 {
3819
3820 if (INSN_P (insn))
3821 {
3822 /* And initialize deps_lists. */
3823 sd_init_insn (insn);
3824 /* Clean up SCHED_GROUP_P which may be set by last
3825 scheduler pass. */
3826 if (SCHED_GROUP_P (insn))
3827 SCHED_GROUP_P (insn) = 0;
3828 }
3829
3830 deps_analyze_insn (deps, insn);
3831
3832 if (insn == tail)
3833 {
3834 if (sched_deps_info->use_cselib)
3835 cselib_finish ();
3836 return;
3837 }
3838 }
3839 gcc_unreachable ();
3840}
3841
3842/* Helper for sched_free_deps ().
3843 Delete INSN's (RESOLVED_P) backward dependencies. */
3844static void
3845delete_dep_nodes_in_back_deps (rtx_insn *insn, bool resolved_p)
3846{
3847 sd_iterator_def sd_it;
3848 dep_t dep;
3849 sd_list_types_def types;
3850
3851 if (resolved_p)
3852 types = SD_LIST_RES_BACK;
3853 else
3854 types = SD_LIST_BACK;
3855
3856 for (sd_it = sd_iterator_start (insn, types);
3857 sd_iterator_cond (&sd_it, &dep);)
3858 {
3859 dep_link_t link = *sd_it.linkp;
3860 dep_node_t node = DEP_LINK_NODE (link);
3861 deps_list_t back_list;
3862 deps_list_t forw_list;
3863
3864 get_back_and_forw_lists (dep, resolved_p, &back_list, &forw_list);
3865 remove_from_deps_list (link, back_list);
3866 delete_dep_node (node);
3867 }
3868}
3869
3870/* Delete (RESOLVED_P) dependencies between HEAD and TAIL together with
3871 deps_lists. */
3872void
3873sched_free_deps (rtx_insn *head, rtx_insn *tail, bool resolved_p)
3874{
3875 rtx_insn *insn;
3876 rtx_insn *next_tail = NEXT_INSN (tail);
3877
3878 /* We make two passes since some insns may be scheduled before their
3879 dependencies are resolved. */
3880 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
3881 if (INSN_P (insn) && INSN_LUID (insn) > 0)
3882 {
3883 /* Clear forward deps and leave the dep_nodes to the
3884 corresponding back_deps list. */
3885 if (resolved_p)
3886 clear_deps_list (INSN_RESOLVED_FORW_DEPS (insn));
3887 else
3888 clear_deps_list (INSN_FORW_DEPS (insn));
3889 }
3890 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
3891 if (INSN_P (insn) && INSN_LUID (insn) > 0)
3892 {
3893 /* Clear resolved back deps together with its dep_nodes. */
3894 delete_dep_nodes_in_back_deps (insn, resolved_p);
3895
3896 sd_finish_insn (insn);
3897 }
3898}
3899
3900/* Initialize variables for region data dependence analysis.
3901 When LAZY_REG_LAST is true, do not allocate reg_last array
3902 of struct deps_desc immediately. */
3903
3904void
3905init_deps (struct deps_desc *deps, bool lazy_reg_last)
3906{
3907 int max_reg = (reload_completed ? FIRST_PSEUDO_REGISTER : max_reg_num ());
3908
3909 deps->max_reg = max_reg;
3910 if (lazy_reg_last)
3911 deps->reg_last = NULL;
3912 else
3913 deps->reg_last = XCNEWVEC (struct deps_reg, max_reg);
3914 INIT_REG_SET (&deps->reg_last_in_use);
3915
3916 deps->pending_read_insns = 0;
3917 deps->pending_read_mems = 0;
3918 deps->pending_write_insns = 0;
3919 deps->pending_write_mems = 0;
3920 deps->pending_jump_insns = 0;
3921 deps->pending_read_list_length = 0;
3922 deps->pending_write_list_length = 0;
3923 deps->pending_flush_length = 0;
3924 deps->last_pending_memory_flush = 0;
3925 deps->last_function_call = 0;
3926 deps->last_function_call_may_noreturn = 0;
3927 deps->sched_before_next_call = 0;
3928 deps->sched_before_next_jump = 0;
3929 deps->in_post_call_group_p = not_post_call;
3930 deps->last_debug_insn = 0;
3931 deps->last_args_size = 0;
3932 deps->last_prologue = 0;
3933 deps->last_epilogue = 0;
3934 deps->last_logue_was_epilogue = false;
3935 deps->last_reg_pending_barrier = NOT_A_BARRIER;
3936 deps->readonly = 0;
3937}
3938
3939/* Init only reg_last field of DEPS, which was not allocated before as
3940 we inited DEPS lazily. */
3941void
3942init_deps_reg_last (struct deps_desc *deps)
3943{
3944 gcc_assert (deps && deps->max_reg > 0);
3945 gcc_assert (deps->reg_last == NULL);
3946
3947 deps->reg_last = XCNEWVEC (struct deps_reg, deps->max_reg);
3948}
3949
3950
3951/* Free insn lists found in DEPS. */
3952
3953void
3954free_deps (struct deps_desc *deps)
3955{
3956 unsigned i;
3957 reg_set_iterator rsi;
3958
3959 /* We set max_reg to 0 when this context was already freed. */
3960 if (deps->max_reg == 0)
3961 {
3962 gcc_assert (deps->reg_last == NULL);
3963 return;
3964 }
3965 deps->max_reg = 0;
3966
3967 free_INSN_LIST_list (&deps->pending_read_insns);
3968 free_EXPR_LIST_list (&deps->pending_read_mems);
3969 free_INSN_LIST_list (&deps->pending_write_insns);
3970 free_EXPR_LIST_list (&deps->pending_write_mems);
3971 free_INSN_LIST_list (&deps->last_pending_memory_flush);
3972
3973 /* Without the EXECUTE_IF_SET, this loop is executed max_reg * nr_regions
3974 times. For a testcase with 42000 regs and 8000 small basic blocks,
3975 this loop accounted for nearly 60% (84 sec) of the total -O2 runtime. */
3976 EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
3977 {
3978 struct deps_reg *reg_last = &deps->reg_last[i];
3979 if (reg_last->uses)
3980 free_INSN_LIST_list (&reg_last->uses);
3981 if (reg_last->sets)
3982 free_INSN_LIST_list (&reg_last->sets);
3983 if (reg_last->implicit_sets)
3984 free_INSN_LIST_list (&reg_last->implicit_sets);
3985 if (reg_last->control_uses)
3986 free_INSN_LIST_list (&reg_last->control_uses);
3987 if (reg_last->clobbers)
3988 free_INSN_LIST_list (&reg_last->clobbers);
3989 }
3990 CLEAR_REG_SET (&deps->reg_last_in_use);
3991
3992 /* As we initialize reg_last lazily, it is possible that we didn't allocate
3993 it at all. */
3994 free (deps->reg_last);
3995 deps->reg_last = NULL;
3996
3997 deps = NULL;
3998}
3999
4000/* Remove INSN from dependence contexts DEPS. */
4001void
4002remove_from_deps (struct deps_desc *deps, rtx_insn *insn)
4003{
4004 int removed;
4005 unsigned i;
4006 reg_set_iterator rsi;
4007
4008 removed = remove_from_both_dependence_lists (insn, &deps->pending_read_insns,
4009 &deps->pending_read_mems);
4010 if (!DEBUG_INSN_P (insn))
4011 deps->pending_read_list_length -= removed;
4012 removed = remove_from_both_dependence_lists (insn, &deps->pending_write_insns,
4013 &deps->pending_write_mems);
4014 deps->pending_write_list_length -= removed;
4015
4016 removed = remove_from_dependence_list (insn, &deps->pending_jump_insns);
4017 deps->pending_flush_length -= removed;
4018 removed = remove_from_dependence_list (insn, &deps->last_pending_memory_flush);
4019 deps->pending_flush_length -= removed;
4020
4021 unsigned to_clear = -1U;
4022 EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
4023 {
4024 if (to_clear != -1U)
4025 {
4026 CLEAR_REGNO_REG_SET (&deps->reg_last_in_use, to_clear);
4027 to_clear = -1U;
4028 }
4029 struct deps_reg *reg_last = &deps->reg_last[i];
4030 if (reg_last->uses)
4031 remove_from_dependence_list (insn, &reg_last->uses);
4032 if (reg_last->sets)
4033 remove_from_dependence_list (insn, &reg_last->sets);
4034 if (reg_last->implicit_sets)
4035 remove_from_dependence_list (insn, &reg_last->implicit_sets);
4036 if (reg_last->clobbers)
4037 remove_from_dependence_list (insn, &reg_last->clobbers);
4038 if (!reg_last->uses && !reg_last->sets && !reg_last->implicit_sets
4039 && !reg_last->clobbers)
4040 to_clear = i;
4041 }
4042 if (to_clear != -1U)
4043 CLEAR_REGNO_REG_SET (&deps->reg_last_in_use, to_clear);
4044
4045 if (CALL_P (insn))
4046 {
4047 remove_from_dependence_list (insn, &deps->last_function_call);
4048 remove_from_dependence_list (insn,
4049 &deps->last_function_call_may_noreturn);
4050 }
4051 remove_from_dependence_list (insn, &deps->sched_before_next_call);
4052}
4053
4054/* Init deps data vector. */
4055static void
4056init_deps_data_vector (void)
4057{
4058 int reserve = (sched_max_luid + 1 - h_d_i_d.length ());
4059 if (reserve > 0 && ! h_d_i_d.space (reserve))
4060 h_d_i_d.safe_grow_cleared (3 * sched_max_luid / 2);
4061}
4062
4063/* If it is profitable to use them, initialize or extend (depending on
4064 GLOBAL_P) dependency data. */
4065void
4066sched_deps_init (bool global_p)
4067{
4068 /* Average number of insns in the basic block.
4069 '+ 1' is used to make it nonzero. */
4070 int insns_in_block = sched_max_luid / n_basic_blocks_for_fn (cfun) + 1;
4071
4072 init_deps_data_vector ();
4073
4074 /* We use another caching mechanism for selective scheduling, so
4075 we don't use this one. */
4076 if (!sel_sched_p () && global_p && insns_in_block > 100 * 5)
4077 {
4078 /* ?!? We could save some memory by computing a per-region luid mapping
4079 which could reduce both the number of vectors in the cache and the
4080 size of each vector. Instead we just avoid the cache entirely unless
4081 the average number of instructions in a basic block is very high. See
4082 the comment before the declaration of true_dependency_cache for
4083 what we consider "very high". */
4084 cache_size = 0;
4085 extend_dependency_caches (sched_max_luid, true);
4086 }
4087
4088 if (global_p)
4089 {
4090 dl_pool = new object_allocator<_deps_list> ("deps_list");
4091 /* Allocate lists for one block at a time. */
4092 dn_pool = new object_allocator<_dep_node> ("dep_node");
4093 /* Allocate nodes for one block at a time. */
4094 }
4095}
4096
4097
4098/* Create or extend (depending on CREATE_P) dependency caches to
4099 size N. */
4100void
4101extend_dependency_caches (int n, bool create_p)
4102{
4103 if (create_p || true_dependency_cache)
4104 {
4105 int i, luid = cache_size + n;
4106
4107 true_dependency_cache = XRESIZEVEC (bitmap_head, true_dependency_cache,
4108 luid);
4109 output_dependency_cache = XRESIZEVEC (bitmap_head,
4110 output_dependency_cache, luid);
4111 anti_dependency_cache = XRESIZEVEC (bitmap_head, anti_dependency_cache,
4112 luid);
4113 control_dependency_cache = XRESIZEVEC (bitmap_head, control_dependency_cache,
4114 luid);
4115
4116 if (current_sched_info->flags & DO_SPECULATION)
4117 spec_dependency_cache = XRESIZEVEC (bitmap_head, spec_dependency_cache,
4118 luid);
4119
4120 for (i = cache_size; i < luid; i++)
4121 {
4122 bitmap_initialize (&true_dependency_cache[i], 0);
4123 bitmap_initialize (&output_dependency_cache[i], 0);
4124 bitmap_initialize (&anti_dependency_cache[i], 0);
4125 bitmap_initialize (&control_dependency_cache[i], 0);
4126
4127 if (current_sched_info->flags & DO_SPECULATION)
4128 bitmap_initialize (&spec_dependency_cache[i], 0);
4129 }
4130 cache_size = luid;
4131 }
4132}
4133
4134/* Finalize dependency information for the whole function. */
4135void
4136sched_deps_finish (void)
4137{
4138 gcc_assert (deps_pools_are_empty_p ());
4139 delete dn_pool;
4140 delete dl_pool;
4141 dn_pool = NULL;
4142 dl_pool = NULL;
4143
4144 h_d_i_d.release ();
4145 cache_size = 0;
4146
4147 if (true_dependency_cache)
4148 {
4149 int i;
4150
4151 for (i = 0; i < cache_size; i++)
4152 {
4153 bitmap_clear (&true_dependency_cache[i]);
4154 bitmap_clear (&output_dependency_cache[i]);
4155 bitmap_clear (&anti_dependency_cache[i]);
4156 bitmap_clear (&control_dependency_cache[i]);
4157
4158 if (sched_deps_info->generate_spec_deps)
4159 bitmap_clear (&spec_dependency_cache[i]);
4160 }
4161 free (true_dependency_cache);
4162 true_dependency_cache = NULL;
4163 free (output_dependency_cache);
4164 output_dependency_cache = NULL;
4165 free (anti_dependency_cache);
4166 anti_dependency_cache = NULL;
4167 free (control_dependency_cache);
4168 control_dependency_cache = NULL;
4169
4170 if (sched_deps_info->generate_spec_deps)
4171 {
4172 free (spec_dependency_cache);
4173 spec_dependency_cache = NULL;
4174 }
4175
4176 }
4177}
4178
4179/* Initialize some global variables needed by the dependency analysis
4180 code. */
4181
4182void
4183init_deps_global (void)
4184{
4185 CLEAR_HARD_REG_SET (implicit_reg_pending_clobbers);
4186 CLEAR_HARD_REG_SET (implicit_reg_pending_uses);
4187 reg_pending_sets = ALLOC_REG_SET (&reg_obstack);
4188 reg_pending_clobbers = ALLOC_REG_SET (&reg_obstack);
4189 reg_pending_uses = ALLOC_REG_SET (&reg_obstack);
4190 reg_pending_control_uses = ALLOC_REG_SET (&reg_obstack);
4191 reg_pending_barrier = NOT_A_BARRIER;
4192
4193 if (!sel_sched_p () || sched_emulate_haifa_p)
4194 {
4195 sched_deps_info->start_insn = haifa_start_insn;
4196 sched_deps_info->finish_insn = haifa_finish_insn;
4197
4198 sched_deps_info->note_reg_set = haifa_note_reg_set;
4199 sched_deps_info->note_reg_clobber = haifa_note_reg_clobber;
4200 sched_deps_info->note_reg_use = haifa_note_reg_use;
4201
4202 sched_deps_info->note_mem_dep = haifa_note_mem_dep;
4203 sched_deps_info->note_dep = haifa_note_dep;
4204 }
4205}
4206
4207/* Free everything used by the dependency analysis code. */
4208
4209void
4210finish_deps_global (void)
4211{
4212 FREE_REG_SET (reg_pending_sets);
4213 FREE_REG_SET (reg_pending_clobbers);
4214 FREE_REG_SET (reg_pending_uses);
4215 FREE_REG_SET (reg_pending_control_uses);
4216}
4217
4218/* Estimate the weakness of dependence between MEM1 and MEM2. */
4219dw_t
4220estimate_dep_weak (rtx mem1, rtx mem2)
4221{
4222 if (mem1 == mem2)
4223 /* MEMs are the same - don't speculate. */
4224 return MIN_DEP_WEAK;
4225
4226 rtx r1 = XEXP (mem1, 0);
4227 rtx r2 = XEXP (mem2, 0);
4228
4229 if (sched_deps_info->use_cselib)
4230 {
4231 /* We cannot call rtx_equal_for_cselib_p because the VALUEs might be
4232 dangling at this point, since we never preserve them. Instead we
4233 canonicalize manually to get stable VALUEs out of hashing. */
4234 if (GET_CODE (r1) == VALUE && CSELIB_VAL_PTR (r1))
4235 r1 = canonical_cselib_val (CSELIB_VAL_PTR (r1))->val_rtx;
4236 if (GET_CODE (r2) == VALUE && CSELIB_VAL_PTR (r2))
4237 r2 = canonical_cselib_val (CSELIB_VAL_PTR (r2))->val_rtx;
4238 }
4239
4240 if (r1 == r2
4241 || (REG_P (r1) && REG_P (r2) && REGNO (r1) == REGNO (r2)))
4242 /* Again, MEMs are the same. */
4243 return MIN_DEP_WEAK;
4244 else if ((REG_P (r1) && !REG_P (r2)) || (!REG_P (r1) && REG_P (r2)))
4245 /* Different addressing modes - reason to be more speculative,
4246 than usual. */
4247 return NO_DEP_WEAK - (NO_DEP_WEAK - UNCERTAIN_DEP_WEAK) / 2;
4248 else
4249 /* We can't say anything about the dependence. */
4250 return UNCERTAIN_DEP_WEAK;
4251}
4252
4253/* Add or update backward dependence between INSN and ELEM with type DEP_TYPE.
4254 This function can handle same INSN and ELEM (INSN == ELEM).
4255 It is a convenience wrapper. */
4256static void
4257add_dependence_1 (rtx_insn *insn, rtx_insn *elem, enum reg_note dep_type)
4258{
4259 ds_t ds;
4260 bool internal;
4261
4262 if (dep_type == REG_DEP_TRUE)
4263 ds = DEP_TRUE;
4264 else if (dep_type == REG_DEP_OUTPUT)
4265 ds = DEP_OUTPUT;
4266 else if (dep_type == REG_DEP_CONTROL)
4267 ds = DEP_CONTROL;
4268 else
4269 {
4270 gcc_assert (dep_type == REG_DEP_ANTI);
4271 ds = DEP_ANTI;
4272 }
4273
4274 /* When add_dependence is called from inside sched-deps.c, we expect
4275 cur_insn to be non-null. */
4276 internal = cur_insn != NULL;
4277 if (internal)
4278 gcc_assert (insn == cur_insn);
4279 else
4280 cur_insn = insn;
4281
4282 note_dep (elem, ds);
4283 if (!internal)
4284 cur_insn = NULL;
4285}
4286
4287/* Return weakness of speculative type TYPE in the dep_status DS,
4288 without checking to prevent ICEs on malformed input. */
4289static dw_t
4290get_dep_weak_1 (ds_t ds, ds_t type)
4291{
4292 ds = ds & type;
4293
4294 switch (type)
4295 {
4296 case BEGIN_DATA: ds >>= BEGIN_DATA_BITS_OFFSET; break;
4297 case BE_IN_DATA: ds >>= BE_IN_DATA_BITS_OFFSET; break;
4298 case BEGIN_CONTROL: ds >>= BEGIN_CONTROL_BITS_OFFSET; break;
4299 case BE_IN_CONTROL: ds >>= BE_IN_CONTROL_BITS_OFFSET; break;
4300 default: gcc_unreachable ();
4301 }
4302
4303 return (dw_t) ds;
4304}
4305
4306/* Return weakness of speculative type TYPE in the dep_status DS. */
4307dw_t
4308get_dep_weak (ds_t ds, ds_t type)
4309{
4310 dw_t dw = get_dep_weak_1 (ds, type);
4311
4312 gcc_assert (MIN_DEP_WEAK <= dw && dw <= MAX_DEP_WEAK);
4313 return dw;
4314}
4315
4316/* Return the dep_status, which has the same parameters as DS, except for
4317 speculative type TYPE, that will have weakness DW. */
4318ds_t
4319set_dep_weak (ds_t ds, ds_t type, dw_t dw)
4320{
4321 gcc_assert (MIN_DEP_WEAK <= dw && dw <= MAX_DEP_WEAK);
4322
4323 ds &= ~type;
4324 switch (type)
4325 {
4326 case BEGIN_DATA: ds |= ((ds_t) dw) << BEGIN_DATA_BITS_OFFSET; break;
4327 case BE_IN_DATA: ds |= ((ds_t) dw) << BE_IN_DATA_BITS_OFFSET; break;
4328 case BEGIN_CONTROL: ds |= ((ds_t) dw) << BEGIN_CONTROL_BITS_OFFSET; break;
4329 case BE_IN_CONTROL: ds |= ((ds_t) dw) << BE_IN_CONTROL_BITS_OFFSET; break;
4330 default: gcc_unreachable ();
4331 }
4332 return ds;
4333}
4334
4335/* Return the join of two dep_statuses DS1 and DS2.
4336 If MAX_P is true then choose the greater probability,
4337 otherwise multiply probabilities.
4338 This function assumes that both DS1 and DS2 contain speculative bits. */
4339static ds_t
4340ds_merge_1 (ds_t ds1, ds_t ds2, bool max_p)
4341{
4342 ds_t ds, t;
4343
4344 gcc_assert ((ds1 & SPECULATIVE) && (ds2 & SPECULATIVE));
4345
4346 ds = (ds1 & DEP_TYPES) | (ds2 & DEP_TYPES);
4347
4348 t = FIRST_SPEC_TYPE;
4349 do
4350 {
4351 if ((ds1 & t) && !(ds2 & t))
4352 ds |= ds1 & t;
4353 else if (!(ds1 & t) && (ds2 & t))
4354 ds |= ds2 & t;
4355 else if ((ds1 & t) && (ds2 & t))
4356 {
4357 dw_t dw1 = get_dep_weak (ds1, t);
4358 dw_t dw2 = get_dep_weak (ds2, t);
4359 ds_t dw;
4360
4361 if (!max_p)
4362 {
4363 dw = ((ds_t) dw1) * ((ds_t) dw2);
4364 dw /= MAX_DEP_WEAK;
4365 if (dw < MIN_DEP_WEAK)
4366 dw = MIN_DEP_WEAK;
4367 }
4368 else
4369 {
4370 if (dw1 >= dw2)
4371 dw = dw1;
4372 else
4373 dw = dw2;
4374 }
4375
4376 ds = set_dep_weak (ds, t, (dw_t) dw);
4377 }
4378
4379 if (t == LAST_SPEC_TYPE)
4380 break;
4381 t <<= SPEC_TYPE_SHIFT;
4382 }
4383 while (1);
4384
4385 return ds;
4386}
4387
4388/* Return the join of two dep_statuses DS1 and DS2.
4389 This function assumes that both DS1 and DS2 contain speculative bits. */
4390ds_t
4391ds_merge (ds_t ds1, ds_t ds2)
4392{
4393 return ds_merge_1 (ds1, ds2, false);
4394}
4395
4396/* Return the join of two dep_statuses DS1 and DS2. */
4397ds_t
4398ds_full_merge (ds_t ds, ds_t ds2, rtx mem1, rtx mem2)
4399{
4400 ds_t new_status = ds | ds2;
4401
4402 if (new_status & SPECULATIVE)
4403 {
4404 if ((ds && !(ds & SPECULATIVE))
4405 || (ds2 && !(ds2 & SPECULATIVE)))
4406 /* Then this dep can't be speculative. */
4407 new_status &= ~SPECULATIVE;
4408 else
4409 {
4410 /* Both are speculative. Merging probabilities. */
4411 if (mem1)
4412 {
4413 dw_t dw;
4414
4415 dw = estimate_dep_weak (mem1, mem2);
4416 ds = set_dep_weak (ds, BEGIN_DATA, dw);
4417 }
4418
4419 if (!ds)
4420 new_status = ds2;
4421 else if (!ds2)
4422 new_status = ds;
4423 else
4424 new_status = ds_merge (ds2, ds);
4425 }
4426 }
4427
4428 return new_status;
4429}
4430
4431/* Return the join of DS1 and DS2. Use maximum instead of multiplying
4432 probabilities. */
4433ds_t
4434ds_max_merge (ds_t ds1, ds_t ds2)
4435{
4436 if (ds1 == 0 && ds2 == 0)
4437 return 0;
4438
4439 if (ds1 == 0 && ds2 != 0)
4440 return ds2;
4441
4442 if (ds1 != 0 && ds2 == 0)
4443 return ds1;
4444
4445 return ds_merge_1 (ds1, ds2, true);
4446}
4447
4448/* Return the probability of speculation success for the speculation
4449 status DS. */
4450dw_t
4451ds_weak (ds_t ds)
4452{
4453 ds_t