1 /* DDG - Data Dependence Graph implementation.
2 Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009
3 Free Software Foundation, Inc.
4 Contributed by Ayal Zaks and Mustafa Hagog <zaks,mustafa@il.ibm.com>
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
25 #include "coretypes.h"
27 #include "diagnostic-core.h"
31 #include "hard-reg-set.h"
35 #include "insn-config.h"
36 #include "insn-attr.h"
39 #include "sched-int.h"
41 #include "cfglayout.h"
48 #ifdef INSN_SCHEDULING
50 /* A flag indicating that a ddg edge belongs to an SCC or not. */
51 enum edge_flag
{NOT_IN_SCC
= 0, IN_SCC
};
53 /* Forward declarations. */
54 static void add_backarc_to_ddg (ddg_ptr
, ddg_edge_ptr
);
55 static void add_backarc_to_scc (ddg_scc_ptr
, ddg_edge_ptr
);
56 static void add_scc_to_ddg (ddg_all_sccs_ptr
, ddg_scc_ptr
);
57 static void create_ddg_dep_from_intra_loop_link (ddg_ptr
, ddg_node_ptr
,
59 static void create_ddg_dep_no_link (ddg_ptr
, ddg_node_ptr
, ddg_node_ptr
,
60 dep_type
, dep_data_type
, int);
61 static ddg_edge_ptr
create_ddg_edge (ddg_node_ptr
, ddg_node_ptr
, dep_type
,
62 dep_data_type
, int, int);
63 static void add_edge_to_ddg (ddg_ptr g
, ddg_edge_ptr
);
65 /* Auxiliary variable for mem_read_insn_p/mem_write_insn_p. */
66 static bool mem_ref_p
;
68 /* Auxiliary function for mem_read_insn_p. */
70 mark_mem_use (rtx
*x
, void *data ATTRIBUTE_UNUSED
)
77 /* Auxiliary function for mem_read_insn_p. */
79 mark_mem_use_1 (rtx
*x
, void *data
)
81 for_each_rtx (x
, mark_mem_use
, data
);
84 /* Returns nonzero if INSN reads from memory. */
86 mem_read_insn_p (rtx insn
)
89 note_uses (&PATTERN (insn
), mark_mem_use_1
, NULL
);
94 mark_mem_store (rtx loc
, const_rtx setter ATTRIBUTE_UNUSED
, void *data ATTRIBUTE_UNUSED
)
100 /* Returns nonzero if INSN writes to memory. */
102 mem_write_insn_p (rtx insn
)
105 note_stores (PATTERN (insn
), mark_mem_store
, NULL
);
109 /* Returns nonzero if X has access to memory. */
111 rtx_mem_access_p (rtx x
)
124 fmt
= GET_RTX_FORMAT (code
);
125 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
129 if (rtx_mem_access_p (XEXP (x
, i
)))
132 else if (fmt
[i
] == 'E')
133 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
135 if (rtx_mem_access_p (XVECEXP (x
, i
, j
)))
142 /* Returns nonzero if INSN reads to or writes from memory. */
144 mem_access_insn_p (rtx insn
)
146 return rtx_mem_access_p (PATTERN (insn
));
149 /* Computes the dependence parameters (latency, distance etc.), creates
150 a ddg_edge and adds it to the given DDG. */
152 create_ddg_dep_from_intra_loop_link (ddg_ptr g
, ddg_node_ptr src_node
,
153 ddg_node_ptr dest_node
, dep_t link
)
156 int latency
, distance
= 0;
157 dep_type t
= TRUE_DEP
;
158 dep_data_type dt
= (mem_access_insn_p (src_node
->insn
)
159 && mem_access_insn_p (dest_node
->insn
) ? MEM_DEP
161 gcc_assert (src_node
->cuid
< dest_node
->cuid
);
164 /* Note: REG_DEP_ANTI applies to MEM ANTI_DEP as well!! */
165 if (DEP_TYPE (link
) == REG_DEP_ANTI
)
167 else if (DEP_TYPE (link
) == REG_DEP_OUTPUT
)
170 gcc_assert (!DEBUG_INSN_P (dest_node
->insn
) || t
== ANTI_DEP
);
171 gcc_assert (!DEBUG_INSN_P (src_node
->insn
) || t
== ANTI_DEP
);
173 /* We currently choose not to create certain anti-deps edges and
174 compensate for that by generating reg-moves based on the life-range
175 analysis. The anti-deps that will be deleted are the ones which
176 have true-deps edges in the opposite direction (in other words
177 the kernel has only one def of the relevant register). TODO:
178 support the removal of all anti-deps edges, i.e. including those
179 whose register has multiple defs in the loop. */
180 if (flag_modulo_sched_allow_regmoves
&& (t
== ANTI_DEP
&& dt
== REG_DEP
))
184 set
= single_set (dest_node
->insn
);
185 /* TODO: Handle registers that REG_P is not true for them, i.e.
186 subregs and special registers. */
187 if (set
&& REG_P (SET_DEST (set
)))
189 int regno
= REGNO (SET_DEST (set
));
191 struct df_rd_bb_info
*bb_info
= DF_RD_BB_INFO (g
->bb
);
193 first_def
= df_bb_regno_first_def_find (g
->bb
, regno
);
194 gcc_assert (first_def
);
196 if (bitmap_bit_p (&bb_info
->gen
, DF_REF_ID (first_def
)))
201 latency
= dep_cost (link
);
202 e
= create_ddg_edge (src_node
, dest_node
, t
, dt
, latency
, distance
);
203 add_edge_to_ddg (g
, e
);
206 /* The same as the above function, but it doesn't require a link parameter. */
208 create_ddg_dep_no_link (ddg_ptr g
, ddg_node_ptr from
, ddg_node_ptr to
,
209 dep_type d_t
, dep_data_type d_dt
, int distance
)
213 enum reg_note dep_kind
;
214 struct _dep _dep
, *dep
= &_dep
;
216 gcc_assert (!DEBUG_INSN_P (to
->insn
) || d_t
== ANTI_DEP
);
217 gcc_assert (!DEBUG_INSN_P (from
->insn
) || d_t
== ANTI_DEP
);
220 dep_kind
= REG_DEP_ANTI
;
221 else if (d_t
== OUTPUT_DEP
)
222 dep_kind
= REG_DEP_OUTPUT
;
225 gcc_assert (d_t
== TRUE_DEP
);
227 dep_kind
= REG_DEP_TRUE
;
230 init_dep (dep
, from
->insn
, to
->insn
, dep_kind
);
234 e
= create_ddg_edge (from
, to
, d_t
, d_dt
, l
, distance
);
236 add_backarc_to_ddg (g
, e
);
238 add_edge_to_ddg (g
, e
);
242 /* Given a downwards exposed register def LAST_DEF (which is the last
243 definition of that register in the bb), add inter-loop true dependences
244 to all its uses in the next iteration, an output dependence to the
245 first def of the same register (possibly itself) in the next iteration
246 and anti-dependences from its uses in the current iteration to the
247 first definition in the next iteration. */
249 add_cross_iteration_register_deps (ddg_ptr g
, df_ref last_def
)
251 int regno
= DF_REF_REGNO (last_def
);
252 struct df_link
*r_use
;
253 int has_use_in_bb_p
= false;
254 rtx def_insn
= DF_REF_INSN (last_def
);
255 ddg_node_ptr last_def_node
= get_node_of_insn (g
, def_insn
);
256 ddg_node_ptr use_node
;
257 #ifdef ENABLE_CHECKING
258 struct df_rd_bb_info
*bb_info
= DF_RD_BB_INFO (g
->bb
);
260 df_ref first_def
= df_bb_regno_first_def_find (g
->bb
, regno
);
262 gcc_assert (last_def_node
);
263 gcc_assert (first_def
);
265 #ifdef ENABLE_CHECKING
266 if (DF_REF_ID (last_def
) != DF_REF_ID (first_def
))
267 gcc_assert (!bitmap_bit_p (&bb_info
->gen
,
268 DF_REF_ID (first_def
)));
271 /* Create inter-loop true dependences and anti dependences. */
272 for (r_use
= DF_REF_CHAIN (last_def
); r_use
!= NULL
; r_use
= r_use
->next
)
274 rtx use_insn
= DF_REF_INSN (r_use
->ref
);
276 if (BLOCK_FOR_INSN (use_insn
) != g
->bb
)
279 /* ??? Do not handle uses with DF_REF_IN_NOTE notes. */
280 use_node
= get_node_of_insn (g
, use_insn
);
281 gcc_assert (use_node
);
282 has_use_in_bb_p
= true;
283 if (use_node
->cuid
<= last_def_node
->cuid
)
285 /* Add true deps from last_def to it's uses in the next
286 iteration. Any such upwards exposed use appears before
288 create_ddg_dep_no_link (g
, last_def_node
, use_node
,
289 DEBUG_INSN_P (use_insn
) ? ANTI_DEP
: TRUE_DEP
,
292 else if (!DEBUG_INSN_P (use_insn
))
294 /* Add anti deps from last_def's uses in the current iteration
295 to the first def in the next iteration. We do not add ANTI
296 dep when there is an intra-loop TRUE dep in the opposite
297 direction, but use regmoves to fix such disregarded ANTI
298 deps when broken. If the first_def reaches the USE then
299 there is such a dep. */
300 ddg_node_ptr first_def_node
= get_node_of_insn (g
,
301 DF_REF_INSN (first_def
));
303 gcc_assert (first_def_node
);
305 if (DF_REF_ID (last_def
) != DF_REF_ID (first_def
)
306 || !flag_modulo_sched_allow_regmoves
)
307 create_ddg_dep_no_link (g
, use_node
, first_def_node
, ANTI_DEP
,
312 /* Create an inter-loop output dependence between LAST_DEF (which is the
313 last def in its block, being downwards exposed) and the first def in
314 its block. Avoid creating a self output dependence. Avoid creating
315 an output dependence if there is a dependence path between the two
316 defs starting with a true dependence to a use which can be in the
317 next iteration; followed by an anti dependence of that use to the
318 first def (i.e. if there is a use between the two defs.) */
319 if (!has_use_in_bb_p
)
321 ddg_node_ptr dest_node
;
323 if (DF_REF_ID (last_def
) == DF_REF_ID (first_def
))
326 dest_node
= get_node_of_insn (g
, DF_REF_INSN (first_def
));
327 gcc_assert (dest_node
);
328 create_ddg_dep_no_link (g
, last_def_node
, dest_node
,
329 OUTPUT_DEP
, REG_DEP
, 1);
332 /* Build inter-loop dependencies, by looking at DF analysis backwards. */
334 build_inter_loop_deps (ddg_ptr g
)
337 struct df_rd_bb_info
*rd_bb_info
;
340 rd_bb_info
= DF_RD_BB_INFO (g
->bb
);
342 /* Find inter-loop register output, true and anti deps. */
343 EXECUTE_IF_SET_IN_BITMAP (&rd_bb_info
->gen
, 0, rd_num
, bi
)
345 df_ref rd
= DF_DEFS_GET (rd_num
);
347 add_cross_iteration_register_deps (g
, rd
);
353 walk_mems_2 (rtx
*x
, rtx mem
)
357 if (may_alias_p (*x
, mem
))
366 walk_mems_1 (rtx
*x
, rtx
*pat
)
370 /* Visit all MEMs in *PAT and check indepedence. */
371 if (for_each_rtx (pat
, (rtx_function
) walk_mems_2
, *x
))
372 /* Indicate that dependence was determined and stop traversal. */
380 /* Return 1 if two specified instructions have mem expr with conflict alias sets*/
382 insns_may_alias_p (rtx insn1
, rtx insn2
)
384 /* For each pair of MEMs in INSN1 and INSN2 check their independence. */
385 return for_each_rtx (&PATTERN (insn1
), (rtx_function
) walk_mems_1
,
389 /* Given two nodes, analyze their RTL insns and add inter-loop mem deps
392 add_inter_loop_mem_dep (ddg_ptr g
, ddg_node_ptr from
, ddg_node_ptr to
)
394 if (!insns_may_alias_p (from
->insn
, to
->insn
))
395 /* Do not create edge if memory references have disjoint alias sets. */
398 if (mem_write_insn_p (from
->insn
))
400 if (mem_read_insn_p (to
->insn
))
401 create_ddg_dep_no_link (g
, from
, to
,
402 DEBUG_INSN_P (to
->insn
)
403 ? ANTI_DEP
: TRUE_DEP
, MEM_DEP
, 1);
404 else if (from
->cuid
!= to
->cuid
)
405 create_ddg_dep_no_link (g
, from
, to
,
406 DEBUG_INSN_P (to
->insn
)
407 ? ANTI_DEP
: OUTPUT_DEP
, MEM_DEP
, 1);
411 if (mem_read_insn_p (to
->insn
))
413 else if (from
->cuid
!= to
->cuid
)
415 create_ddg_dep_no_link (g
, from
, to
, ANTI_DEP
, MEM_DEP
, 1);
416 if (DEBUG_INSN_P (from
->insn
) || DEBUG_INSN_P (to
->insn
))
417 create_ddg_dep_no_link (g
, to
, from
, ANTI_DEP
, MEM_DEP
, 1);
419 create_ddg_dep_no_link (g
, to
, from
, TRUE_DEP
, MEM_DEP
, 1);
425 /* Perform intra-block Data Dependency analysis and connect the nodes in
426 the DDG. We assume the loop has a single basic block. */
428 build_intra_loop_deps (ddg_ptr g
)
431 /* Hold the dependency analysis state during dependency calculations. */
432 struct deps_desc tmp_deps
;
435 /* Build the dependence information, using the sched_analyze function. */
437 init_deps (&tmp_deps
, false);
439 /* Do the intra-block data dependence analysis for the given block. */
440 get_ebb_head_tail (g
->bb
, g
->bb
, &head
, &tail
);
441 sched_analyze (&tmp_deps
, head
, tail
);
443 /* Build intra-loop data dependencies using the scheduler dependency
445 for (i
= 0; i
< g
->num_nodes
; i
++)
447 ddg_node_ptr dest_node
= &g
->nodes
[i
];
448 sd_iterator_def sd_it
;
451 if (! INSN_P (dest_node
->insn
))
454 FOR_EACH_DEP (dest_node
->insn
, SD_LIST_BACK
, sd_it
, dep
)
456 ddg_node_ptr src_node
= get_node_of_insn (g
, DEP_PRO (dep
));
461 create_ddg_dep_from_intra_loop_link (g
, src_node
, dest_node
, dep
);
464 /* If this insn modifies memory, add an edge to all insns that access
466 if (mem_access_insn_p (dest_node
->insn
))
470 for (j
= 0; j
<= i
; j
++)
472 ddg_node_ptr j_node
= &g
->nodes
[j
];
473 if (DEBUG_INSN_P (j_node
->insn
))
475 if (mem_access_insn_p (j_node
->insn
))
476 /* Don't bother calculating inter-loop dep if an intra-loop dep
478 if (! TEST_BIT (dest_node
->successors
, j
))
479 add_inter_loop_mem_dep (g
, dest_node
, j_node
);
484 /* Free the INSN_LISTs. */
485 finish_deps_global ();
486 free_deps (&tmp_deps
);
488 /* Free dependencies. */
489 sched_free_deps (head
, tail
, false);
493 /* Given a basic block, create its DDG and return a pointer to a variable
494 of ddg type that represents it.
495 Initialize the ddg structure fields to the appropriate values. */
497 create_ddg (basic_block bb
, int closing_branch_deps
)
500 rtx insn
, first_note
;
504 g
= (ddg_ptr
) xcalloc (1, sizeof (struct ddg
));
507 g
->closing_branch_deps
= closing_branch_deps
;
509 /* Count the number of insns in the BB. */
510 for (insn
= BB_HEAD (bb
); insn
!= NEXT_INSN (BB_END (bb
));
511 insn
= NEXT_INSN (insn
))
513 if (! INSN_P (insn
) || GET_CODE (PATTERN (insn
)) == USE
)
516 if (DEBUG_INSN_P (insn
))
520 if (mem_read_insn_p (insn
))
522 if (mem_write_insn_p (insn
))
528 /* There is nothing to do for this BB. */
529 if ((num_nodes
- g
->num_debug
) <= 1)
535 /* Allocate the nodes array, and initialize the nodes. */
536 g
->num_nodes
= num_nodes
;
537 g
->nodes
= (ddg_node_ptr
) xcalloc (num_nodes
, sizeof (struct ddg_node
));
538 g
->closing_branch
= NULL
;
540 first_note
= NULL_RTX
;
541 for (insn
= BB_HEAD (bb
); insn
!= NEXT_INSN (BB_END (bb
));
542 insn
= NEXT_INSN (insn
))
546 if (! first_note
&& NOTE_P (insn
)
547 && NOTE_KIND (insn
) != NOTE_INSN_BASIC_BLOCK
)
553 gcc_assert (!g
->closing_branch
);
554 g
->closing_branch
= &g
->nodes
[i
];
556 else if (GET_CODE (PATTERN (insn
)) == USE
)
563 g
->nodes
[i
].cuid
= i
;
564 g
->nodes
[i
].successors
= sbitmap_alloc (num_nodes
);
565 sbitmap_zero (g
->nodes
[i
].successors
);
566 g
->nodes
[i
].predecessors
= sbitmap_alloc (num_nodes
);
567 sbitmap_zero (g
->nodes
[i
].predecessors
);
568 g
->nodes
[i
].first_note
= (first_note
? first_note
: insn
);
569 g
->nodes
[i
++].insn
= insn
;
570 first_note
= NULL_RTX
;
573 /* We must have found a branch in DDG. */
574 gcc_assert (g
->closing_branch
);
577 /* Build the data dependency graph. */
578 build_intra_loop_deps (g
);
579 build_inter_loop_deps (g
);
583 /* Free all the memory allocated for the DDG. */
592 for (i
= 0; i
< g
->num_nodes
; i
++)
594 ddg_edge_ptr e
= g
->nodes
[i
].out
;
598 ddg_edge_ptr next
= e
->next_out
;
603 sbitmap_free (g
->nodes
[i
].successors
);
604 sbitmap_free (g
->nodes
[i
].predecessors
);
606 if (g
->num_backarcs
> 0)
613 print_ddg_edge (FILE *file
, ddg_edge_ptr e
)
629 fprintf (file
, " [%d -(%c,%d,%d)-> %d] ", INSN_UID (e
->src
->insn
),
630 dep_c
, e
->latency
, e
->distance
, INSN_UID (e
->dest
->insn
));
633 /* Print the DDG nodes with there in/out edges to the dump file. */
635 print_ddg (FILE *file
, ddg_ptr g
)
639 for (i
= 0; i
< g
->num_nodes
; i
++)
643 fprintf (file
, "Node num: %d\n", g
->nodes
[i
].cuid
);
644 print_rtl_single (file
, g
->nodes
[i
].insn
);
645 fprintf (file
, "OUT ARCS: ");
646 for (e
= g
->nodes
[i
].out
; e
; e
= e
->next_out
)
647 print_ddg_edge (file
, e
);
649 fprintf (file
, "\nIN ARCS: ");
650 for (e
= g
->nodes
[i
].in
; e
; e
= e
->next_in
)
651 print_ddg_edge (file
, e
);
653 fprintf (file
, "\n");
657 /* Print the given DDG in VCG format. */
659 vcg_print_ddg (FILE *file
, ddg_ptr g
)
663 fprintf (file
, "graph: {\n");
664 for (src_cuid
= 0; src_cuid
< g
->num_nodes
; src_cuid
++)
667 int src_uid
= INSN_UID (g
->nodes
[src_cuid
].insn
);
669 fprintf (file
, "node: {title: \"%d_%d\" info1: \"", src_cuid
, src_uid
);
670 print_rtl_single (file
, g
->nodes
[src_cuid
].insn
);
671 fprintf (file
, "\"}\n");
672 for (e
= g
->nodes
[src_cuid
].out
; e
; e
= e
->next_out
)
674 int dst_uid
= INSN_UID (e
->dest
->insn
);
675 int dst_cuid
= e
->dest
->cuid
;
677 /* Give the backarcs a different color. */
679 fprintf (file
, "backedge: {color: red ");
681 fprintf (file
, "edge: { ");
683 fprintf (file
, "sourcename: \"%d_%d\" ", src_cuid
, src_uid
);
684 fprintf (file
, "targetname: \"%d_%d\" ", dst_cuid
, dst_uid
);
685 fprintf (file
, "label: \"%d_%d\"}\n", e
->latency
, e
->distance
);
688 fprintf (file
, "}\n");
691 /* Dump the sccs in SCCS. */
693 print_sccs (FILE *file
, ddg_all_sccs_ptr sccs
, ddg_ptr g
)
696 sbitmap_iterator sbi
;
702 fprintf (file
, "\n;; Number of SCC nodes - %d\n", sccs
->num_sccs
);
703 for (i
= 0; i
< sccs
->num_sccs
; i
++)
705 fprintf (file
, "SCC number: %d\n", i
);
706 EXECUTE_IF_SET_IN_SBITMAP (sccs
->sccs
[i
]->nodes
, 0, u
, sbi
)
708 fprintf (file
, "insn num %d\n", u
);
709 print_rtl_single (file
, g
->nodes
[u
].insn
);
712 fprintf (file
, "\n");
715 /* Create an edge and initialize it with given values. */
717 create_ddg_edge (ddg_node_ptr src
, ddg_node_ptr dest
,
718 dep_type t
, dep_data_type dt
, int l
, int d
)
720 ddg_edge_ptr e
= (ddg_edge_ptr
) xmalloc (sizeof (struct ddg_edge
));
728 e
->next_in
= e
->next_out
= NULL
;
733 /* Add the given edge to the in/out linked lists of the DDG nodes. */
735 add_edge_to_ddg (ddg_ptr g ATTRIBUTE_UNUSED
, ddg_edge_ptr e
)
737 ddg_node_ptr src
= e
->src
;
738 ddg_node_ptr dest
= e
->dest
;
740 /* Should have allocated the sbitmaps. */
741 gcc_assert (src
->successors
&& dest
->predecessors
);
743 SET_BIT (src
->successors
, dest
->cuid
);
744 SET_BIT (dest
->predecessors
, src
->cuid
);
745 e
->next_in
= dest
->in
;
747 e
->next_out
= src
->out
;
753 /* Algorithm for computing the recurrence_length of an scc. We assume at
754 for now that cycles in the data dependence graph contain a single backarc.
755 This simplifies the algorithm, and can be generalized later. */
757 set_recurrence_length (ddg_scc_ptr scc
, ddg_ptr g
)
762 for (j
= 0; j
< scc
->num_backarcs
; j
++)
764 ddg_edge_ptr backarc
= scc
->backarcs
[j
];
766 int distance
= backarc
->distance
;
767 ddg_node_ptr src
= backarc
->dest
;
768 ddg_node_ptr dest
= backarc
->src
;
770 length
= longest_simple_path (g
, src
->cuid
, dest
->cuid
, scc
->nodes
);
773 /* fprintf (stderr, "Backarc not on simple cycle in SCC.\n"); */
776 length
+= backarc
->latency
;
777 result
= MAX (result
, (length
/ distance
));
779 scc
->recurrence_length
= result
;
782 /* Create a new SCC given the set of its nodes. Compute its recurrence_length
783 and mark edges that belong to this scc as IN_SCC. */
785 create_scc (ddg_ptr g
, sbitmap nodes
)
789 sbitmap_iterator sbi
;
791 scc
= (ddg_scc_ptr
) xmalloc (sizeof (struct ddg_scc
));
792 scc
->backarcs
= NULL
;
793 scc
->num_backarcs
= 0;
794 scc
->nodes
= sbitmap_alloc (g
->num_nodes
);
795 sbitmap_copy (scc
->nodes
, nodes
);
797 /* Mark the backarcs that belong to this SCC. */
798 EXECUTE_IF_SET_IN_SBITMAP (nodes
, 0, u
, sbi
)
801 ddg_node_ptr n
= &g
->nodes
[u
];
803 for (e
= n
->out
; e
; e
= e
->next_out
)
804 if (TEST_BIT (nodes
, e
->dest
->cuid
))
806 e
->aux
.count
= IN_SCC
;
808 add_backarc_to_scc (scc
, e
);
812 set_recurrence_length (scc
, g
);
816 /* Cleans the memory allocation of a given SCC. */
818 free_scc (ddg_scc_ptr scc
)
823 sbitmap_free (scc
->nodes
);
824 if (scc
->num_backarcs
> 0)
825 free (scc
->backarcs
);
830 /* Add a given edge known to be a backarc to the given DDG. */
832 add_backarc_to_ddg (ddg_ptr g
, ddg_edge_ptr e
)
834 int size
= (g
->num_backarcs
+ 1) * sizeof (ddg_edge_ptr
);
836 add_edge_to_ddg (g
, e
);
837 g
->backarcs
= (ddg_edge_ptr
*) xrealloc (g
->backarcs
, size
);
838 g
->backarcs
[g
->num_backarcs
++] = e
;
841 /* Add backarc to an SCC. */
843 add_backarc_to_scc (ddg_scc_ptr scc
, ddg_edge_ptr e
)
845 int size
= (scc
->num_backarcs
+ 1) * sizeof (ddg_edge_ptr
);
847 scc
->backarcs
= (ddg_edge_ptr
*) xrealloc (scc
->backarcs
, size
);
848 scc
->backarcs
[scc
->num_backarcs
++] = e
;
851 /* Add the given SCC to the DDG. */
853 add_scc_to_ddg (ddg_all_sccs_ptr g
, ddg_scc_ptr scc
)
855 int size
= (g
->num_sccs
+ 1) * sizeof (ddg_scc_ptr
);
857 g
->sccs
= (ddg_scc_ptr
*) xrealloc (g
->sccs
, size
);
858 g
->sccs
[g
->num_sccs
++] = scc
;
861 /* Given the instruction INSN return the node that represents it. */
863 get_node_of_insn (ddg_ptr g
, rtx insn
)
867 for (i
= 0; i
< g
->num_nodes
; i
++)
868 if (insn
== g
->nodes
[i
].insn
)
873 /* Given a set OPS of nodes in the DDG, find the set of their successors
874 which are not in OPS, and set their bits in SUCC. Bits corresponding to
875 OPS are cleared from SUCC. Leaves the other bits in SUCC unchanged. */
877 find_successors (sbitmap succ
, ddg_ptr g
, sbitmap ops
)
880 sbitmap_iterator sbi
;
882 EXECUTE_IF_SET_IN_SBITMAP (ops
, 0, i
, sbi
)
884 const sbitmap node_succ
= NODE_SUCCESSORS (&g
->nodes
[i
]);
885 sbitmap_a_or_b (succ
, succ
, node_succ
);
888 /* We want those that are not in ops. */
889 sbitmap_difference (succ
, succ
, ops
);
892 /* Given a set OPS of nodes in the DDG, find the set of their predecessors
893 which are not in OPS, and set their bits in PREDS. Bits corresponding to
894 OPS are cleared from PREDS. Leaves the other bits in PREDS unchanged. */
896 find_predecessors (sbitmap preds
, ddg_ptr g
, sbitmap ops
)
899 sbitmap_iterator sbi
;
901 EXECUTE_IF_SET_IN_SBITMAP (ops
, 0, i
, sbi
)
903 const sbitmap node_preds
= NODE_PREDECESSORS (&g
->nodes
[i
]);
904 sbitmap_a_or_b (preds
, preds
, node_preds
);
907 /* We want those that are not in ops. */
908 sbitmap_difference (preds
, preds
, ops
);
912 /* Compare function to be passed to qsort to order the backarcs in descending
915 compare_sccs (const void *s1
, const void *s2
)
917 const int rec_l1
= (*(const ddg_scc_ptr
*)s1
)->recurrence_length
;
918 const int rec_l2
= (*(const ddg_scc_ptr
*)s2
)->recurrence_length
;
919 return ((rec_l2
> rec_l1
) - (rec_l2
< rec_l1
));
923 /* Order the backarcs in descending recMII order using compare_sccs. */
925 order_sccs (ddg_all_sccs_ptr g
)
927 qsort (g
->sccs
, g
->num_sccs
, sizeof (ddg_scc_ptr
),
928 (int (*) (const void *, const void *)) compare_sccs
);
931 #ifdef ENABLE_CHECKING
932 /* Check that every node in SCCS belongs to exactly one strongly connected
933 component and that no element of SCCS is empty. */
935 check_sccs (ddg_all_sccs_ptr sccs
, int num_nodes
)
938 sbitmap tmp
= sbitmap_alloc (num_nodes
);
941 for (i
= 0; i
< sccs
->num_sccs
; i
++)
943 gcc_assert (!sbitmap_empty_p (sccs
->sccs
[i
]->nodes
));
944 /* Verify that every node in sccs is in exactly one strongly
945 connected component. */
946 gcc_assert (!sbitmap_any_common_bits (tmp
, sccs
->sccs
[i
]->nodes
));
947 sbitmap_a_or_b (tmp
, tmp
, sccs
->sccs
[i
]->nodes
);
953 /* Perform the Strongly Connected Components decomposing algorithm on the
954 DDG and return DDG_ALL_SCCS structure that contains them. */
956 create_ddg_all_sccs (ddg_ptr g
)
959 int num_nodes
= g
->num_nodes
;
960 sbitmap from
= sbitmap_alloc (num_nodes
);
961 sbitmap to
= sbitmap_alloc (num_nodes
);
962 sbitmap scc_nodes
= sbitmap_alloc (num_nodes
);
963 ddg_all_sccs_ptr sccs
= (ddg_all_sccs_ptr
)
964 xmalloc (sizeof (struct ddg_all_sccs
));
970 for (i
= 0; i
< g
->num_backarcs
; i
++)
973 ddg_edge_ptr backarc
= g
->backarcs
[i
];
974 ddg_node_ptr src
= backarc
->src
;
975 ddg_node_ptr dest
= backarc
->dest
;
977 /* If the backarc already belongs to an SCC, continue. */
978 if (backarc
->aux
.count
== IN_SCC
)
981 sbitmap_zero (scc_nodes
);
984 SET_BIT (from
, dest
->cuid
);
985 SET_BIT (to
, src
->cuid
);
987 if (find_nodes_on_paths (scc_nodes
, g
, from
, to
))
989 scc
= create_scc (g
, scc_nodes
);
990 add_scc_to_ddg (sccs
, scc
);
996 sbitmap_free (scc_nodes
);
997 #ifdef ENABLE_CHECKING
998 check_sccs (sccs
, num_nodes
);
1003 /* Frees the memory allocated for all SCCs of the DDG, but keeps the DDG. */
1005 free_ddg_all_sccs (ddg_all_sccs_ptr all_sccs
)
1012 for (i
= 0; i
< all_sccs
->num_sccs
; i
++)
1013 free_scc (all_sccs
->sccs
[i
]);
1019 /* Given FROM - a bitmap of source nodes - and TO - a bitmap of destination
1020 nodes - find all nodes that lie on paths from FROM to TO (not excluding
1021 nodes from FROM and TO). Return nonzero if nodes exist. */
1023 find_nodes_on_paths (sbitmap result
, ddg_ptr g
, sbitmap from
, sbitmap to
)
1028 int num_nodes
= g
->num_nodes
;
1029 sbitmap_iterator sbi
;
1031 sbitmap workset
= sbitmap_alloc (num_nodes
);
1032 sbitmap reachable_from
= sbitmap_alloc (num_nodes
);
1033 sbitmap reach_to
= sbitmap_alloc (num_nodes
);
1034 sbitmap tmp
= sbitmap_alloc (num_nodes
);
1036 sbitmap_copy (reachable_from
, from
);
1037 sbitmap_copy (tmp
, from
);
1043 sbitmap_copy (workset
, tmp
);
1045 EXECUTE_IF_SET_IN_SBITMAP (workset
, 0, u
, sbi
)
1048 ddg_node_ptr u_node
= &g
->nodes
[u
];
1050 for (e
= u_node
->out
; e
!= (ddg_edge_ptr
) 0; e
= e
->next_out
)
1052 ddg_node_ptr v_node
= e
->dest
;
1053 int v
= v_node
->cuid
;
1055 if (!TEST_BIT (reachable_from
, v
))
1057 SET_BIT (reachable_from
, v
);
1065 sbitmap_copy (reach_to
, to
);
1066 sbitmap_copy (tmp
, to
);
1072 sbitmap_copy (workset
, tmp
);
1074 EXECUTE_IF_SET_IN_SBITMAP (workset
, 0, u
, sbi
)
1077 ddg_node_ptr u_node
= &g
->nodes
[u
];
1079 for (e
= u_node
->in
; e
!= (ddg_edge_ptr
) 0; e
= e
->next_in
)
1081 ddg_node_ptr v_node
= e
->src
;
1082 int v
= v_node
->cuid
;
1084 if (!TEST_BIT (reach_to
, v
))
1086 SET_BIT (reach_to
, v
);
1094 answer
= sbitmap_a_and_b_cg (result
, reachable_from
, reach_to
);
1095 sbitmap_free (workset
);
1096 sbitmap_free (reachable_from
);
1097 sbitmap_free (reach_to
);
1103 /* Updates the counts of U_NODE's successors (that belong to NODES) to be
1104 at-least as large as the count of U_NODE plus the latency between them.
1105 Sets a bit in TMP for each successor whose count was changed (increased).
1106 Returns nonzero if any count was changed. */
1108 update_dist_to_successors (ddg_node_ptr u_node
, sbitmap nodes
, sbitmap tmp
)
1113 for (e
= u_node
->out
; e
; e
= e
->next_out
)
1115 ddg_node_ptr v_node
= e
->dest
;
1116 int v
= v_node
->cuid
;
1118 if (TEST_BIT (nodes
, v
)
1119 && (e
->distance
== 0)
1120 && (v_node
->aux
.count
< u_node
->aux
.count
+ e
->latency
))
1122 v_node
->aux
.count
= u_node
->aux
.count
+ e
->latency
;
1131 /* Find the length of a longest path from SRC to DEST in G,
1132 going only through NODES, and disregarding backarcs. */
1134 longest_simple_path (struct ddg
* g
, int src
, int dest
, sbitmap nodes
)
1140 int num_nodes
= g
->num_nodes
;
1141 sbitmap workset
= sbitmap_alloc (num_nodes
);
1142 sbitmap tmp
= sbitmap_alloc (num_nodes
);
1145 /* Data will hold the distance of the longest path found so far from
1146 src to each node. Initialize to -1 = less than minimum. */
1147 for (i
= 0; i
< g
->num_nodes
; i
++)
1148 g
->nodes
[i
].aux
.count
= -1;
1149 g
->nodes
[src
].aux
.count
= 0;
1156 sbitmap_iterator sbi
;
1159 sbitmap_copy (workset
, tmp
);
1161 EXECUTE_IF_SET_IN_SBITMAP (workset
, 0, u
, sbi
)
1163 ddg_node_ptr u_node
= &g
->nodes
[u
];
1165 change
|= update_dist_to_successors (u_node
, nodes
, tmp
);
1168 result
= g
->nodes
[dest
].aux
.count
;
1169 sbitmap_free (workset
);
1174 #endif /* INSN_SCHEDULING */