1 /* DDG - Data Dependence Graph implementation.
2 Copyright (C) 2004, 2005, 2006, 2007
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"
30 #include "hard-reg-set.h"
34 #include "insn-config.h"
35 #include "insn-attr.h"
38 #include "sched-int.h"
40 #include "cfglayout.h"
47 /* A flag indicating that a ddg edge belongs to an SCC or not. */
48 enum edge_flag
{NOT_IN_SCC
= 0, IN_SCC
};
50 /* Forward declarations. */
51 static void add_backarc_to_ddg (ddg_ptr
, ddg_edge_ptr
);
52 static void add_backarc_to_scc (ddg_scc_ptr
, ddg_edge_ptr
);
53 static void add_scc_to_ddg (ddg_all_sccs_ptr
, ddg_scc_ptr
);
54 static void create_ddg_dep_from_intra_loop_link (ddg_ptr
, ddg_node_ptr
,
56 static void create_ddg_dep_no_link (ddg_ptr
, ddg_node_ptr
, ddg_node_ptr
,
57 dep_type
, dep_data_type
, int);
58 static ddg_edge_ptr
create_ddg_edge (ddg_node_ptr
, ddg_node_ptr
, dep_type
,
59 dep_data_type
, int, int);
60 static void add_edge_to_ddg (ddg_ptr g
, ddg_edge_ptr
);
62 /* Auxiliary variable for mem_read_insn_p/mem_write_insn_p. */
63 static bool mem_ref_p
;
65 /* Auxiliary function for mem_read_insn_p. */
67 mark_mem_use (rtx
*x
, void *data ATTRIBUTE_UNUSED
)
74 /* Auxiliary function for mem_read_insn_p. */
76 mark_mem_use_1 (rtx
*x
, void *data
)
78 for_each_rtx (x
, mark_mem_use
, data
);
81 /* Returns nonzero if INSN reads from memory. */
83 mem_read_insn_p (rtx insn
)
86 note_uses (&PATTERN (insn
), mark_mem_use_1
, NULL
);
91 mark_mem_store (rtx loc
, const_rtx setter ATTRIBUTE_UNUSED
, void *data ATTRIBUTE_UNUSED
)
97 /* Returns nonzero if INSN writes to memory. */
99 mem_write_insn_p (rtx insn
)
102 note_stores (PATTERN (insn
), mark_mem_store
, NULL
);
106 /* Returns nonzero if X has access to memory. */
108 rtx_mem_access_p (rtx x
)
121 fmt
= GET_RTX_FORMAT (code
);
122 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
126 if (rtx_mem_access_p (XEXP (x
, i
)))
129 else if (fmt
[i
] == 'E')
130 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
132 if (rtx_mem_access_p (XVECEXP (x
, i
, j
)))
139 /* Returns nonzero if INSN reads to or writes from memory. */
141 mem_access_insn_p (rtx insn
)
143 return rtx_mem_access_p (PATTERN (insn
));
146 /* Computes the dependence parameters (latency, distance etc.), creates
147 a ddg_edge and adds it to the given DDG. */
149 create_ddg_dep_from_intra_loop_link (ddg_ptr g
, ddg_node_ptr src_node
,
150 ddg_node_ptr dest_node
, dep_t link
)
153 int latency
, distance
= 0;
154 dep_type t
= TRUE_DEP
;
155 dep_data_type dt
= (mem_access_insn_p (src_node
->insn
)
156 && mem_access_insn_p (dest_node
->insn
) ? MEM_DEP
158 gcc_assert (src_node
->cuid
< dest_node
->cuid
);
161 /* Note: REG_DEP_ANTI applies to MEM ANTI_DEP as well!! */
162 if (DEP_TYPE (link
) == REG_DEP_ANTI
)
164 else if (DEP_TYPE (link
) == REG_DEP_OUTPUT
)
167 /* We currently choose not to create certain anti-deps edges and
168 compensate for that by generating reg-moves based on the life-range
169 analysis. The anti-deps that will be deleted are the ones which
170 have true-deps edges in the opposite direction (in other words
171 the kernel has only one def of the relevant register). TODO:
172 support the removal of all anti-deps edges, i.e. including those
173 whose register has multiple defs in the loop. */
174 if (flag_modulo_sched_allow_regmoves
&& (t
== ANTI_DEP
&& dt
== REG_DEP
))
178 set
= single_set (dest_node
->insn
);
179 /* TODO: Handle registers that REG_P is not true for them, i.e.
180 subregs and special registers. */
181 if (set
&& REG_P (SET_DEST (set
)))
183 int regno
= REGNO (SET_DEST (set
));
184 struct df_ref
*first_def
;
185 struct df_rd_bb_info
*bb_info
= DF_RD_BB_INFO (g
->bb
);
187 first_def
= df_bb_regno_first_def_find (g
->bb
, regno
);
188 gcc_assert (first_def
);
190 if (bitmap_bit_p (bb_info
->gen
, first_def
->id
))
195 latency
= dep_cost (link
);
196 e
= create_ddg_edge (src_node
, dest_node
, t
, dt
, latency
, distance
);
197 add_edge_to_ddg (g
, e
);
200 /* The same as the above function, but it doesn't require a link parameter. */
202 create_ddg_dep_no_link (ddg_ptr g
, ddg_node_ptr from
, ddg_node_ptr to
,
203 dep_type d_t
, dep_data_type d_dt
, int distance
)
207 enum reg_note dep_kind
;
208 struct _dep _dep
, *dep
= &_dep
;
211 dep_kind
= REG_DEP_ANTI
;
212 else if (d_t
== OUTPUT_DEP
)
213 dep_kind
= REG_DEP_OUTPUT
;
216 gcc_assert (d_t
== TRUE_DEP
);
218 dep_kind
= REG_DEP_TRUE
;
221 init_dep (dep
, from
->insn
, to
->insn
, dep_kind
);
225 e
= create_ddg_edge (from
, to
, d_t
, d_dt
, l
, distance
);
227 add_backarc_to_ddg (g
, e
);
229 add_edge_to_ddg (g
, e
);
233 /* Given a downwards exposed register def LAST_DEF (which is the last
234 definition of that register in the bb), add inter-loop true dependences
235 to all its uses in the next iteration, an output dependence to the
236 first def of the same register (possibly itself) in the next iteration
237 and anti-dependences from its uses in the current iteration to the
238 first definition in the next iteration. */
240 add_cross_iteration_register_deps (ddg_ptr g
, struct df_ref
*last_def
)
242 int regno
= DF_REF_REGNO (last_def
);
243 struct df_link
*r_use
;
244 int has_use_in_bb_p
= false;
245 rtx def_insn
= DF_REF_INSN (last_def
);
246 ddg_node_ptr last_def_node
= get_node_of_insn (g
, def_insn
);
247 ddg_node_ptr use_node
;
248 #ifdef ENABLE_CHECKING
249 struct df_rd_bb_info
*bb_info
= DF_RD_BB_INFO (g
->bb
);
251 struct df_ref
*first_def
= df_bb_regno_first_def_find (g
->bb
, regno
);
253 gcc_assert (last_def_node
);
254 gcc_assert (first_def
);
256 #ifdef ENABLE_CHECKING
257 if (last_def
->id
!= first_def
->id
)
258 gcc_assert (!bitmap_bit_p (bb_info
->gen
, first_def
->id
));
261 /* Create inter-loop true dependences and anti dependences. */
262 for (r_use
= DF_REF_CHAIN (last_def
); r_use
!= NULL
; r_use
= r_use
->next
)
264 rtx use_insn
= DF_REF_INSN (r_use
->ref
);
266 if (BLOCK_FOR_INSN (use_insn
) != g
->bb
)
269 /* ??? Do not handle uses with DF_REF_IN_NOTE notes. */
270 use_node
= get_node_of_insn (g
, use_insn
);
271 gcc_assert (use_node
);
272 has_use_in_bb_p
= true;
273 if (use_node
->cuid
<= last_def_node
->cuid
)
275 /* Add true deps from last_def to it's uses in the next
276 iteration. Any such upwards exposed use appears before
278 create_ddg_dep_no_link (g
, last_def_node
, use_node
, TRUE_DEP
,
283 /* Add anti deps from last_def's uses in the current iteration
284 to the first def in the next iteration. We do not add ANTI
285 dep when there is an intra-loop TRUE dep in the opposite
286 direction, but use regmoves to fix such disregarded ANTI
287 deps when broken. If the first_def reaches the USE then
288 there is such a dep. */
289 ddg_node_ptr first_def_node
= get_node_of_insn (g
,
292 gcc_assert (first_def_node
);
294 if (last_def
->id
!= first_def
->id
295 || !flag_modulo_sched_allow_regmoves
)
296 create_ddg_dep_no_link (g
, use_node
, first_def_node
, ANTI_DEP
,
301 /* Create an inter-loop output dependence between LAST_DEF (which is the
302 last def in its block, being downwards exposed) and the first def in
303 its block. Avoid creating a self output dependence. Avoid creating
304 an output dependence if there is a dependence path between the two
305 defs starting with a true dependence to a use which can be in the
306 next iteration; followed by an anti dependence of that use to the
307 first def (i.e. if there is a use between the two defs.) */
308 if (!has_use_in_bb_p
)
310 ddg_node_ptr dest_node
;
312 if (last_def
->id
== first_def
->id
)
315 dest_node
= get_node_of_insn (g
, first_def
->insn
);
316 gcc_assert (dest_node
);
317 create_ddg_dep_no_link (g
, last_def_node
, dest_node
,
318 OUTPUT_DEP
, REG_DEP
, 1);
321 /* Build inter-loop dependencies, by looking at DF analysis backwards. */
323 build_inter_loop_deps (ddg_ptr g
)
326 struct df_rd_bb_info
*rd_bb_info
;
329 rd_bb_info
= DF_RD_BB_INFO (g
->bb
);
331 /* Find inter-loop register output, true and anti deps. */
332 EXECUTE_IF_SET_IN_BITMAP (rd_bb_info
->gen
, 0, rd_num
, bi
)
334 struct df_ref
*rd
= DF_DEFS_GET (rd_num
);
336 add_cross_iteration_register_deps (g
, rd
);
341 /* Given two nodes, analyze their RTL insns and add inter-loop mem deps
344 add_inter_loop_mem_dep (ddg_ptr g
, ddg_node_ptr from
, ddg_node_ptr to
)
346 if (mem_write_insn_p (from
->insn
))
348 if (mem_read_insn_p (to
->insn
))
349 create_ddg_dep_no_link (g
, from
, to
, TRUE_DEP
, MEM_DEP
, 1);
350 else if (from
->cuid
!= to
->cuid
)
351 create_ddg_dep_no_link (g
, from
, to
, OUTPUT_DEP
, MEM_DEP
, 1);
355 if (mem_read_insn_p (to
->insn
))
357 else if (from
->cuid
!= to
->cuid
)
359 create_ddg_dep_no_link (g
, from
, to
, ANTI_DEP
, MEM_DEP
, 1);
360 create_ddg_dep_no_link (g
, to
, from
, TRUE_DEP
, MEM_DEP
, 1);
366 /* Perform intra-block Data Dependency analysis and connect the nodes in
367 the DDG. We assume the loop has a single basic block. */
369 build_intra_loop_deps (ddg_ptr g
)
372 /* Hold the dependency analysis state during dependency calculations. */
373 struct deps tmp_deps
;
376 /* Build the dependence information, using the sched_analyze function. */
378 init_deps (&tmp_deps
);
380 /* Do the intra-block data dependence analysis for the given block. */
381 get_ebb_head_tail (g
->bb
, g
->bb
, &head
, &tail
);
382 sched_analyze (&tmp_deps
, head
, tail
);
384 /* Build intra-loop data dependencies using the scheduler dependency
386 for (i
= 0; i
< g
->num_nodes
; i
++)
388 ddg_node_ptr dest_node
= &g
->nodes
[i
];
389 sd_iterator_def sd_it
;
392 if (! INSN_P (dest_node
->insn
))
395 FOR_EACH_DEP (dest_node
->insn
, SD_LIST_BACK
, sd_it
, dep
)
397 ddg_node_ptr src_node
= get_node_of_insn (g
, DEP_PRO (dep
));
402 create_ddg_dep_from_intra_loop_link (g
, src_node
, dest_node
, dep
);
405 /* If this insn modifies memory, add an edge to all insns that access
407 if (mem_access_insn_p (dest_node
->insn
))
411 for (j
= 0; j
<= i
; j
++)
413 ddg_node_ptr j_node
= &g
->nodes
[j
];
414 if (mem_access_insn_p (j_node
->insn
))
415 /* Don't bother calculating inter-loop dep if an intra-loop dep
417 if (! TEST_BIT (dest_node
->successors
, j
))
418 add_inter_loop_mem_dep (g
, dest_node
, j_node
);
423 /* Free the INSN_LISTs. */
424 finish_deps_global ();
425 free_deps (&tmp_deps
);
427 /* Free dependencies. */
428 sched_free_deps (head
, tail
, false);
432 /* Given a basic block, create its DDG and return a pointer to a variable
433 of ddg type that represents it.
434 Initialize the ddg structure fields to the appropriate values. */
436 create_ddg (basic_block bb
, int closing_branch_deps
)
439 rtx insn
, first_note
;
443 g
= (ddg_ptr
) xcalloc (1, sizeof (struct ddg
));
446 g
->closing_branch_deps
= closing_branch_deps
;
448 /* Count the number of insns in the BB. */
449 for (insn
= BB_HEAD (bb
); insn
!= NEXT_INSN (BB_END (bb
));
450 insn
= NEXT_INSN (insn
))
452 if (! INSN_P (insn
) || GET_CODE (PATTERN (insn
)) == USE
)
455 if (mem_read_insn_p (insn
))
457 if (mem_write_insn_p (insn
))
462 /* There is nothing to do for this BB. */
469 /* Allocate the nodes array, and initialize the nodes. */
470 g
->num_nodes
= num_nodes
;
471 g
->nodes
= (ddg_node_ptr
) xcalloc (num_nodes
, sizeof (struct ddg_node
));
472 g
->closing_branch
= NULL
;
474 first_note
= NULL_RTX
;
475 for (insn
= BB_HEAD (bb
); insn
!= NEXT_INSN (BB_END (bb
));
476 insn
= NEXT_INSN (insn
))
480 if (! first_note
&& NOTE_P (insn
)
481 && NOTE_KIND (insn
) != NOTE_INSN_BASIC_BLOCK
)
487 gcc_assert (!g
->closing_branch
);
488 g
->closing_branch
= &g
->nodes
[i
];
490 else if (GET_CODE (PATTERN (insn
)) == USE
)
497 g
->nodes
[i
].cuid
= i
;
498 g
->nodes
[i
].successors
= sbitmap_alloc (num_nodes
);
499 sbitmap_zero (g
->nodes
[i
].successors
);
500 g
->nodes
[i
].predecessors
= sbitmap_alloc (num_nodes
);
501 sbitmap_zero (g
->nodes
[i
].predecessors
);
502 g
->nodes
[i
].first_note
= (first_note
? first_note
: insn
);
503 g
->nodes
[i
++].insn
= insn
;
504 first_note
= NULL_RTX
;
507 /* We must have found a branch in DDG. */
508 gcc_assert (g
->closing_branch
);
511 /* Build the data dependency graph. */
512 build_intra_loop_deps (g
);
513 build_inter_loop_deps (g
);
517 /* Free all the memory allocated for the DDG. */
526 for (i
= 0; i
< g
->num_nodes
; i
++)
528 ddg_edge_ptr e
= g
->nodes
[i
].out
;
532 ddg_edge_ptr next
= e
->next_out
;
537 sbitmap_free (g
->nodes
[i
].successors
);
538 sbitmap_free (g
->nodes
[i
].predecessors
);
540 if (g
->num_backarcs
> 0)
547 print_ddg_edge (FILE *file
, ddg_edge_ptr e
)
563 fprintf (file
, " [%d -(%c,%d,%d)-> %d] ", INSN_UID (e
->src
->insn
),
564 dep_c
, e
->latency
, e
->distance
, INSN_UID (e
->dest
->insn
));
567 /* Print the DDG nodes with there in/out edges to the dump file. */
569 print_ddg (FILE *file
, ddg_ptr g
)
573 for (i
= 0; i
< g
->num_nodes
; i
++)
577 fprintf (file
, "Node num: %d\n", g
->nodes
[i
].cuid
);
578 print_rtl_single (file
, g
->nodes
[i
].insn
);
579 fprintf (file
, "OUT ARCS: ");
580 for (e
= g
->nodes
[i
].out
; e
; e
= e
->next_out
)
581 print_ddg_edge (file
, e
);
583 fprintf (file
, "\nIN ARCS: ");
584 for (e
= g
->nodes
[i
].in
; e
; e
= e
->next_in
)
585 print_ddg_edge (file
, e
);
587 fprintf (file
, "\n");
591 /* Print the given DDG in VCG format. */
593 vcg_print_ddg (FILE *file
, ddg_ptr g
)
597 fprintf (file
, "graph: {\n");
598 for (src_cuid
= 0; src_cuid
< g
->num_nodes
; src_cuid
++)
601 int src_uid
= INSN_UID (g
->nodes
[src_cuid
].insn
);
603 fprintf (file
, "node: {title: \"%d_%d\" info1: \"", src_cuid
, src_uid
);
604 print_rtl_single (file
, g
->nodes
[src_cuid
].insn
);
605 fprintf (file
, "\"}\n");
606 for (e
= g
->nodes
[src_cuid
].out
; e
; e
= e
->next_out
)
608 int dst_uid
= INSN_UID (e
->dest
->insn
);
609 int dst_cuid
= e
->dest
->cuid
;
611 /* Give the backarcs a different color. */
613 fprintf (file
, "backedge: {color: red ");
615 fprintf (file
, "edge: { ");
617 fprintf (file
, "sourcename: \"%d_%d\" ", src_cuid
, src_uid
);
618 fprintf (file
, "targetname: \"%d_%d\" ", dst_cuid
, dst_uid
);
619 fprintf (file
, "label: \"%d_%d\"}\n", e
->latency
, e
->distance
);
622 fprintf (file
, "}\n");
625 /* Dump the sccs in SCCS. */
627 print_sccs (FILE *file
, ddg_all_sccs_ptr sccs
, ddg_ptr g
)
630 sbitmap_iterator sbi
;
636 fprintf (file
, "\n;; Number of SCC nodes - %d\n", sccs
->num_sccs
);
637 for (i
= 0; i
< sccs
->num_sccs
; i
++)
639 fprintf (file
, "SCC number: %d\n", i
);
640 EXECUTE_IF_SET_IN_SBITMAP (sccs
->sccs
[i
]->nodes
, 0, u
, sbi
)
642 fprintf (file
, "insn num %d\n", u
);
643 print_rtl_single (file
, g
->nodes
[u
].insn
);
646 fprintf (file
, "\n");
649 /* Create an edge and initialize it with given values. */
651 create_ddg_edge (ddg_node_ptr src
, ddg_node_ptr dest
,
652 dep_type t
, dep_data_type dt
, int l
, int d
)
654 ddg_edge_ptr e
= (ddg_edge_ptr
) xmalloc (sizeof (struct ddg_edge
));
662 e
->next_in
= e
->next_out
= NULL
;
667 /* Add the given edge to the in/out linked lists of the DDG nodes. */
669 add_edge_to_ddg (ddg_ptr g ATTRIBUTE_UNUSED
, ddg_edge_ptr e
)
671 ddg_node_ptr src
= e
->src
;
672 ddg_node_ptr dest
= e
->dest
;
674 /* Should have allocated the sbitmaps. */
675 gcc_assert (src
->successors
&& dest
->predecessors
);
677 SET_BIT (src
->successors
, dest
->cuid
);
678 SET_BIT (dest
->predecessors
, src
->cuid
);
679 e
->next_in
= dest
->in
;
681 e
->next_out
= src
->out
;
687 /* Algorithm for computing the recurrence_length of an scc. We assume at
688 for now that cycles in the data dependence graph contain a single backarc.
689 This simplifies the algorithm, and can be generalized later. */
691 set_recurrence_length (ddg_scc_ptr scc
, ddg_ptr g
)
696 for (j
= 0; j
< scc
->num_backarcs
; j
++)
698 ddg_edge_ptr backarc
= scc
->backarcs
[j
];
700 int distance
= backarc
->distance
;
701 ddg_node_ptr src
= backarc
->dest
;
702 ddg_node_ptr dest
= backarc
->src
;
704 length
= longest_simple_path (g
, src
->cuid
, dest
->cuid
, scc
->nodes
);
707 /* fprintf (stderr, "Backarc not on simple cycle in SCC.\n"); */
710 length
+= backarc
->latency
;
711 result
= MAX (result
, (length
/ distance
));
713 scc
->recurrence_length
= result
;
716 /* Create a new SCC given the set of its nodes. Compute its recurrence_length
717 and mark edges that belong to this scc as IN_SCC. */
719 create_scc (ddg_ptr g
, sbitmap nodes
)
723 sbitmap_iterator sbi
;
725 scc
= (ddg_scc_ptr
) xmalloc (sizeof (struct ddg_scc
));
726 scc
->backarcs
= NULL
;
727 scc
->num_backarcs
= 0;
728 scc
->nodes
= sbitmap_alloc (g
->num_nodes
);
729 sbitmap_copy (scc
->nodes
, nodes
);
731 /* Mark the backarcs that belong to this SCC. */
732 EXECUTE_IF_SET_IN_SBITMAP (nodes
, 0, u
, sbi
)
735 ddg_node_ptr n
= &g
->nodes
[u
];
737 for (e
= n
->out
; e
; e
= e
->next_out
)
738 if (TEST_BIT (nodes
, e
->dest
->cuid
))
740 e
->aux
.count
= IN_SCC
;
742 add_backarc_to_scc (scc
, e
);
746 set_recurrence_length (scc
, g
);
750 /* Cleans the memory allocation of a given SCC. */
752 free_scc (ddg_scc_ptr scc
)
757 sbitmap_free (scc
->nodes
);
758 if (scc
->num_backarcs
> 0)
759 free (scc
->backarcs
);
764 /* Add a given edge known to be a backarc to the given DDG. */
766 add_backarc_to_ddg (ddg_ptr g
, ddg_edge_ptr e
)
768 int size
= (g
->num_backarcs
+ 1) * sizeof (ddg_edge_ptr
);
770 add_edge_to_ddg (g
, e
);
771 g
->backarcs
= (ddg_edge_ptr
*) xrealloc (g
->backarcs
, size
);
772 g
->backarcs
[g
->num_backarcs
++] = e
;
775 /* Add backarc to an SCC. */
777 add_backarc_to_scc (ddg_scc_ptr scc
, ddg_edge_ptr e
)
779 int size
= (scc
->num_backarcs
+ 1) * sizeof (ddg_edge_ptr
);
781 scc
->backarcs
= (ddg_edge_ptr
*) xrealloc (scc
->backarcs
, size
);
782 scc
->backarcs
[scc
->num_backarcs
++] = e
;
785 /* Add the given SCC to the DDG. */
787 add_scc_to_ddg (ddg_all_sccs_ptr g
, ddg_scc_ptr scc
)
789 int size
= (g
->num_sccs
+ 1) * sizeof (ddg_scc_ptr
);
791 g
->sccs
= (ddg_scc_ptr
*) xrealloc (g
->sccs
, size
);
792 g
->sccs
[g
->num_sccs
++] = scc
;
795 /* Given the instruction INSN return the node that represents it. */
797 get_node_of_insn (ddg_ptr g
, rtx insn
)
801 for (i
= 0; i
< g
->num_nodes
; i
++)
802 if (insn
== g
->nodes
[i
].insn
)
807 /* Given a set OPS of nodes in the DDG, find the set of their successors
808 which are not in OPS, and set their bits in SUCC. Bits corresponding to
809 OPS are cleared from SUCC. Leaves the other bits in SUCC unchanged. */
811 find_successors (sbitmap succ
, ddg_ptr g
, sbitmap ops
)
814 sbitmap_iterator sbi
;
816 EXECUTE_IF_SET_IN_SBITMAP (ops
, 0, i
, sbi
)
818 const sbitmap node_succ
= NODE_SUCCESSORS (&g
->nodes
[i
]);
819 sbitmap_a_or_b (succ
, succ
, node_succ
);
822 /* We want those that are not in ops. */
823 sbitmap_difference (succ
, succ
, ops
);
826 /* Given a set OPS of nodes in the DDG, find the set of their predecessors
827 which are not in OPS, and set their bits in PREDS. Bits corresponding to
828 OPS are cleared from PREDS. Leaves the other bits in PREDS unchanged. */
830 find_predecessors (sbitmap preds
, ddg_ptr g
, sbitmap ops
)
833 sbitmap_iterator sbi
;
835 EXECUTE_IF_SET_IN_SBITMAP (ops
, 0, i
, sbi
)
837 const sbitmap node_preds
= NODE_PREDECESSORS (&g
->nodes
[i
]);
838 sbitmap_a_or_b (preds
, preds
, node_preds
);
841 /* We want those that are not in ops. */
842 sbitmap_difference (preds
, preds
, ops
);
846 /* Compare function to be passed to qsort to order the backarcs in descending
849 compare_sccs (const void *s1
, const void *s2
)
851 const int rec_l1
= (*(const ddg_scc_ptr
*)s1
)->recurrence_length
;
852 const int rec_l2
= (*(const ddg_scc_ptr
*)s2
)->recurrence_length
;
853 return ((rec_l2
> rec_l1
) - (rec_l2
< rec_l1
));
857 /* Order the backarcs in descending recMII order using compare_sccs. */
859 order_sccs (ddg_all_sccs_ptr g
)
861 qsort (g
->sccs
, g
->num_sccs
, sizeof (ddg_scc_ptr
),
862 (int (*) (const void *, const void *)) compare_sccs
);
865 #ifdef ENABLE_CHECKING
866 /* Check that every node in SCCS belongs to exactly one strongly connected
867 component and that no element of SCCS is empty. */
869 check_sccs (ddg_all_sccs_ptr sccs
, int num_nodes
)
872 sbitmap tmp
= sbitmap_alloc (num_nodes
);
875 for (i
= 0; i
< sccs
->num_sccs
; i
++)
877 gcc_assert (!sbitmap_empty_p (sccs
->sccs
[i
]->nodes
));
878 /* Verify that every node in sccs is in exactly one strongly
879 connected component. */
880 gcc_assert (!sbitmap_any_common_bits (tmp
, sccs
->sccs
[i
]->nodes
));
881 sbitmap_a_or_b (tmp
, tmp
, sccs
->sccs
[i
]->nodes
);
887 /* Perform the Strongly Connected Components decomposing algorithm on the
888 DDG and return DDG_ALL_SCCS structure that contains them. */
890 create_ddg_all_sccs (ddg_ptr g
)
893 int num_nodes
= g
->num_nodes
;
894 sbitmap from
= sbitmap_alloc (num_nodes
);
895 sbitmap to
= sbitmap_alloc (num_nodes
);
896 sbitmap scc_nodes
= sbitmap_alloc (num_nodes
);
897 ddg_all_sccs_ptr sccs
= (ddg_all_sccs_ptr
)
898 xmalloc (sizeof (struct ddg_all_sccs
));
904 for (i
= 0; i
< g
->num_backarcs
; i
++)
907 ddg_edge_ptr backarc
= g
->backarcs
[i
];
908 ddg_node_ptr src
= backarc
->src
;
909 ddg_node_ptr dest
= backarc
->dest
;
911 /* If the backarc already belongs to an SCC, continue. */
912 if (backarc
->aux
.count
== IN_SCC
)
915 sbitmap_zero (scc_nodes
);
918 SET_BIT (from
, dest
->cuid
);
919 SET_BIT (to
, src
->cuid
);
921 if (find_nodes_on_paths (scc_nodes
, g
, from
, to
))
923 scc
= create_scc (g
, scc_nodes
);
924 add_scc_to_ddg (sccs
, scc
);
930 sbitmap_free (scc_nodes
);
931 #ifdef ENABLE_CHECKING
932 check_sccs (sccs
, num_nodes
);
937 /* Frees the memory allocated for all SCCs of the DDG, but keeps the DDG. */
939 free_ddg_all_sccs (ddg_all_sccs_ptr all_sccs
)
946 for (i
= 0; i
< all_sccs
->num_sccs
; i
++)
947 free_scc (all_sccs
->sccs
[i
]);
953 /* Given FROM - a bitmap of source nodes - and TO - a bitmap of destination
954 nodes - find all nodes that lie on paths from FROM to TO (not excluding
955 nodes from FROM and TO). Return nonzero if nodes exist. */
957 find_nodes_on_paths (sbitmap result
, ddg_ptr g
, sbitmap from
, sbitmap to
)
962 int num_nodes
= g
->num_nodes
;
963 sbitmap_iterator sbi
;
965 sbitmap workset
= sbitmap_alloc (num_nodes
);
966 sbitmap reachable_from
= sbitmap_alloc (num_nodes
);
967 sbitmap reach_to
= sbitmap_alloc (num_nodes
);
968 sbitmap tmp
= sbitmap_alloc (num_nodes
);
970 sbitmap_copy (reachable_from
, from
);
971 sbitmap_copy (tmp
, from
);
977 sbitmap_copy (workset
, tmp
);
979 EXECUTE_IF_SET_IN_SBITMAP (workset
, 0, u
, sbi
)
982 ddg_node_ptr u_node
= &g
->nodes
[u
];
984 for (e
= u_node
->out
; e
!= (ddg_edge_ptr
) 0; e
= e
->next_out
)
986 ddg_node_ptr v_node
= e
->dest
;
987 int v
= v_node
->cuid
;
989 if (!TEST_BIT (reachable_from
, v
))
991 SET_BIT (reachable_from
, v
);
999 sbitmap_copy (reach_to
, to
);
1000 sbitmap_copy (tmp
, to
);
1006 sbitmap_copy (workset
, tmp
);
1008 EXECUTE_IF_SET_IN_SBITMAP (workset
, 0, u
, sbi
)
1011 ddg_node_ptr u_node
= &g
->nodes
[u
];
1013 for (e
= u_node
->in
; e
!= (ddg_edge_ptr
) 0; e
= e
->next_in
)
1015 ddg_node_ptr v_node
= e
->src
;
1016 int v
= v_node
->cuid
;
1018 if (!TEST_BIT (reach_to
, v
))
1020 SET_BIT (reach_to
, v
);
1028 answer
= sbitmap_a_and_b_cg (result
, reachable_from
, reach_to
);
1029 sbitmap_free (workset
);
1030 sbitmap_free (reachable_from
);
1031 sbitmap_free (reach_to
);
1037 /* Updates the counts of U_NODE's successors (that belong to NODES) to be
1038 at-least as large as the count of U_NODE plus the latency between them.
1039 Sets a bit in TMP for each successor whose count was changed (increased).
1040 Returns nonzero if any count was changed. */
1042 update_dist_to_successors (ddg_node_ptr u_node
, sbitmap nodes
, sbitmap tmp
)
1047 for (e
= u_node
->out
; e
; e
= e
->next_out
)
1049 ddg_node_ptr v_node
= e
->dest
;
1050 int v
= v_node
->cuid
;
1052 if (TEST_BIT (nodes
, v
)
1053 && (e
->distance
== 0)
1054 && (v_node
->aux
.count
< u_node
->aux
.count
+ e
->latency
))
1056 v_node
->aux
.count
= u_node
->aux
.count
+ e
->latency
;
1065 /* Find the length of a longest path from SRC to DEST in G,
1066 going only through NODES, and disregarding backarcs. */
1068 longest_simple_path (struct ddg
* g
, int src
, int dest
, sbitmap nodes
)
1074 int num_nodes
= g
->num_nodes
;
1075 sbitmap workset
= sbitmap_alloc (num_nodes
);
1076 sbitmap tmp
= sbitmap_alloc (num_nodes
);
1079 /* Data will hold the distance of the longest path found so far from
1080 src to each node. Initialize to -1 = less than minimum. */
1081 for (i
= 0; i
< g
->num_nodes
; i
++)
1082 g
->nodes
[i
].aux
.count
= -1;
1083 g
->nodes
[src
].aux
.count
= 0;
1090 sbitmap_iterator sbi
;
1093 sbitmap_copy (workset
, tmp
);
1095 EXECUTE_IF_SET_IN_SBITMAP (workset
, 0, u
, sbi
)
1097 ddg_node_ptr u_node
= &g
->nodes
[u
];
1099 change
|= update_dist_to_successors (u_node
, nodes
, tmp
);
1102 result
= g
->nodes
[dest
].aux
.count
;
1103 sbitmap_free (workset
);