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_dependence (ddg_ptr
, ddg_node_ptr
, ddg_node_ptr
, dep_t
);
55 static void create_ddg_dep_no_link (ddg_ptr
, ddg_node_ptr
, ddg_node_ptr
,
56 dep_type
, dep_data_type
, int);
57 static ddg_edge_ptr
create_ddg_edge (ddg_node_ptr
, ddg_node_ptr
, dep_type
,
58 dep_data_type
, int, int);
59 static void add_edge_to_ddg (ddg_ptr g
, ddg_edge_ptr
);
61 /* Auxiliary variable for mem_read_insn_p/mem_write_insn_p. */
62 static bool mem_ref_p
;
64 /* Auxiliary function for mem_read_insn_p. */
66 mark_mem_use (rtx
*x
, void *data ATTRIBUTE_UNUSED
)
73 /* Auxiliary function for mem_read_insn_p. */
75 mark_mem_use_1 (rtx
*x
, void *data
)
77 for_each_rtx (x
, mark_mem_use
, data
);
80 /* Returns nonzero if INSN reads from memory. */
82 mem_read_insn_p (rtx insn
)
85 note_uses (&PATTERN (insn
), mark_mem_use_1
, NULL
);
90 mark_mem_store (rtx loc
, const_rtx setter ATTRIBUTE_UNUSED
, void *data ATTRIBUTE_UNUSED
)
96 /* Returns nonzero if INSN writes to memory. */
98 mem_write_insn_p (rtx insn
)
101 note_stores (PATTERN (insn
), mark_mem_store
, NULL
);
105 /* Returns nonzero if X has access to memory. */
107 rtx_mem_access_p (rtx x
)
120 fmt
= GET_RTX_FORMAT (code
);
121 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
125 if (rtx_mem_access_p (XEXP (x
, i
)))
128 else if (fmt
[i
] == 'E')
129 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
131 if (rtx_mem_access_p (XVECEXP (x
, i
, j
)))
138 /* Returns nonzero if INSN reads to or writes from memory. */
140 mem_access_insn_p (rtx insn
)
142 return rtx_mem_access_p (PATTERN (insn
));
145 /* Computes the dependence parameters (latency, distance etc.), creates
146 a ddg_edge and adds it to the given DDG. */
148 create_ddg_dependence (ddg_ptr g
, ddg_node_ptr src_node
,
149 ddg_node_ptr dest_node
, dep_t link
)
152 int latency
, distance
= 0;
153 int interloop
= (src_node
->cuid
>= dest_node
->cuid
);
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
159 /* For now we don't have an exact calculation of the distance,
160 so assume 1 conservatively. */
166 /* Note: REG_DEP_ANTI applies to MEM ANTI_DEP as well!! */
167 if (DEP_KIND (link
) == REG_DEP_ANTI
)
169 else if (DEP_KIND (link
) == REG_DEP_OUTPUT
)
171 latency
= dep_cost (link
);
173 e
= create_ddg_edge (src_node
, dest_node
, t
, dt
, latency
, distance
);
177 /* Some interloop dependencies are relaxed:
178 1. Every insn is output dependent on itself; ignore such deps.
179 2. Every true/flow dependence is an anti dependence in the
180 opposite direction with distance 1; such register deps
181 will be removed by renaming if broken --- ignore them. */
182 if (!(t
== OUTPUT_DEP
&& src_node
== dest_node
)
183 && !(t
== ANTI_DEP
&& dt
== REG_DEP
))
184 add_backarc_to_ddg (g
, e
);
188 else if (t
== ANTI_DEP
&& dt
== REG_DEP
)
189 free (e
); /* We can fix broken anti register deps using reg-moves. */
191 add_edge_to_ddg (g
, e
);
194 /* The same as the above function, but it doesn't require a link parameter. */
196 create_ddg_dep_no_link (ddg_ptr g
, ddg_node_ptr from
, ddg_node_ptr to
,
197 dep_type d_t
, dep_data_type d_dt
, int distance
)
201 enum reg_note dep_kind
;
202 struct _dep _dep
, *dep
= &_dep
;
205 dep_kind
= REG_DEP_ANTI
;
206 else if (d_t
== OUTPUT_DEP
)
207 dep_kind
= REG_DEP_OUTPUT
;
210 gcc_assert (d_t
== TRUE_DEP
);
212 dep_kind
= REG_DEP_TRUE
;
215 init_dep (dep
, from
->insn
, to
->insn
, dep_kind
);
219 e
= create_ddg_edge (from
, to
, d_t
, d_dt
, l
, distance
);
221 add_backarc_to_ddg (g
, e
);
223 add_edge_to_ddg (g
, e
);
227 /* Given a downwards exposed register def LAST_DEF (which is the last
228 definition of that register in the bb), add inter-loop true dependences
229 to all its uses in the next iteration, an output dependence to the
230 first def of the same register (possibly itself) in the next iteration
231 and anti-dependences from its uses in the current iteration to the
232 first definition in the next iteration. */
234 add_cross_iteration_register_deps (ddg_ptr g
, struct df_ref
*last_def
)
236 int regno
= DF_REF_REGNO (last_def
);
237 struct df_link
*r_use
;
238 int has_use_in_bb_p
= false;
239 rtx def_insn
= DF_REF_INSN (last_def
);
240 ddg_node_ptr last_def_node
= get_node_of_insn (g
, def_insn
);
241 ddg_node_ptr use_node
;
242 #ifdef ENABLE_CHECKING
243 struct df_rd_bb_info
*bb_info
= DF_RD_BB_INFO (g
->bb
);
245 struct df_ref
*first_def
= df_bb_regno_first_def_find (g
->bb
, regno
);
247 gcc_assert (last_def_node
);
248 gcc_assert (first_def
);
250 /* Create inter-loop true dependences and anti dependences. */
251 for (r_use
= DF_REF_CHAIN (last_def
); r_use
!= NULL
; r_use
= r_use
->next
)
253 rtx use_insn
= DF_REF_INSN (r_use
->ref
);
255 if (BLOCK_FOR_INSN (use_insn
) != g
->bb
)
258 /* ??? Do not handle uses with DF_REF_IN_NOTE notes. */
259 use_node
= get_node_of_insn (g
, use_insn
);
260 gcc_assert (use_node
);
261 has_use_in_bb_p
= true;
262 if (use_node
->cuid
<= last_def_node
->cuid
)
264 /* Add true deps from last_def to it's uses in the next
265 iteration. Any such upwards exposed use appears before
267 create_ddg_dep_no_link (g
, last_def_node
, use_node
, TRUE_DEP
,
272 /* Add anti deps from last_def's uses in the current iteration
273 to the first def in the next iteration. We do not add ANTI
274 dep when there is an intra-loop TRUE dep in the opposite
275 direction, but use regmoves to fix such disregarded ANTI
276 deps when broken. If the first_def reaches the USE then
277 there is such a dep. */
278 ddg_node_ptr first_def_node
= get_node_of_insn (g
,
281 gcc_assert (first_def_node
);
283 if (last_def
->id
!= first_def
->id
)
285 #ifdef ENABLE_CHECKING
286 gcc_assert (!bitmap_bit_p (bb_info
->gen
, first_def
->id
));
288 create_ddg_dep_no_link (g
, use_node
, first_def_node
, ANTI_DEP
,
293 /* Create an inter-loop output dependence between LAST_DEF (which is the
294 last def in its block, being downwards exposed) and the first def in
295 its block. Avoid creating a self output dependence. Avoid creating
296 an output dependence if there is a dependence path between the two
297 defs starting with a true dependence to a use which can be in the
298 next iteration; followed by an anti dependence of that use to the
299 first def (i.e. if there is a use between the two defs.) */
300 if (!has_use_in_bb_p
)
302 ddg_node_ptr dest_node
;
304 if (last_def
->id
== first_def
->id
)
307 dest_node
= get_node_of_insn (g
, first_def
->insn
);
308 gcc_assert (dest_node
);
309 create_ddg_dep_no_link (g
, last_def_node
, dest_node
,
310 OUTPUT_DEP
, REG_DEP
, 1);
313 /* Build inter-loop dependencies, by looking at DF analysis backwards. */
315 build_inter_loop_deps (ddg_ptr g
)
318 struct df_rd_bb_info
*rd_bb_info
;
321 rd_bb_info
= DF_RD_BB_INFO (g
->bb
);
323 /* Find inter-loop register output, true and anti deps. */
324 EXECUTE_IF_SET_IN_BITMAP (rd_bb_info
->gen
, 0, rd_num
, bi
)
326 struct df_ref
*rd
= DF_DEFS_GET (rd_num
);
328 add_cross_iteration_register_deps (g
, rd
);
333 /* Given two nodes, analyze their RTL insns and add inter-loop mem deps
336 add_inter_loop_mem_dep (ddg_ptr g
, ddg_node_ptr from
, ddg_node_ptr to
)
338 if (mem_write_insn_p (from
->insn
))
340 if (mem_read_insn_p (to
->insn
))
341 create_ddg_dep_no_link (g
, from
, to
, TRUE_DEP
, MEM_DEP
, 1);
342 else if (from
->cuid
!= to
->cuid
)
343 create_ddg_dep_no_link (g
, from
, to
, OUTPUT_DEP
, MEM_DEP
, 1);
347 if (mem_read_insn_p (to
->insn
))
349 else if (from
->cuid
!= to
->cuid
)
351 create_ddg_dep_no_link (g
, from
, to
, ANTI_DEP
, MEM_DEP
, 1);
352 create_ddg_dep_no_link (g
, to
, from
, TRUE_DEP
, MEM_DEP
, 1);
358 /* Perform intra-block Data Dependency analysis and connect the nodes in
359 the DDG. We assume the loop has a single basic block. */
361 build_intra_loop_deps (ddg_ptr g
)
364 /* Hold the dependency analysis state during dependency calculations. */
365 struct deps tmp_deps
;
369 /* Build the dependence information, using the sched_analyze function. */
371 init_deps (&tmp_deps
);
373 /* Do the intra-block data dependence analysis for the given block. */
374 get_ebb_head_tail (g
->bb
, g
->bb
, &head
, &tail
);
375 sched_analyze (&tmp_deps
, head
, tail
);
377 /* Build intra-loop data dependencies using the scheduler dependency
379 for (i
= 0; i
< g
->num_nodes
; i
++)
381 ddg_node_ptr dest_node
= &g
->nodes
[i
];
383 if (! INSN_P (dest_node
->insn
))
386 FOR_EACH_DEP_LINK (link
, INSN_BACK_DEPS (dest_node
->insn
))
388 dep_t dep
= DEP_LINK_DEP (link
);
389 ddg_node_ptr src_node
= get_node_of_insn (g
, DEP_PRO (dep
));
395 create_ddg_dependence (g
, src_node
, dest_node
, dep
);
398 /* If this insn modifies memory, add an edge to all insns that access
400 if (mem_access_insn_p (dest_node
->insn
))
404 for (j
= 0; j
<= i
; j
++)
406 ddg_node_ptr j_node
= &g
->nodes
[j
];
407 if (mem_access_insn_p (j_node
->insn
))
408 /* Don't bother calculating inter-loop dep if an intra-loop dep
410 if (! TEST_BIT (dest_node
->successors
, j
))
411 add_inter_loop_mem_dep (g
, dest_node
, j_node
);
416 /* Free the INSN_LISTs. */
417 finish_deps_global ();
418 free_deps (&tmp_deps
);
422 /* Given a basic block, create its DDG and return a pointer to a variable
423 of ddg type that represents it.
424 Initialize the ddg structure fields to the appropriate values. */
426 create_ddg (basic_block bb
, int closing_branch_deps
)
429 rtx insn
, first_note
;
433 g
= (ddg_ptr
) xcalloc (1, sizeof (struct ddg
));
436 g
->closing_branch_deps
= closing_branch_deps
;
438 /* Count the number of insns in the BB. */
439 for (insn
= BB_HEAD (bb
); insn
!= NEXT_INSN (BB_END (bb
));
440 insn
= NEXT_INSN (insn
))
442 if (! INSN_P (insn
) || GET_CODE (PATTERN (insn
)) == USE
)
445 if (mem_read_insn_p (insn
))
447 if (mem_write_insn_p (insn
))
452 /* There is nothing to do for this BB. */
459 /* Allocate the nodes array, and initialize the nodes. */
460 g
->num_nodes
= num_nodes
;
461 g
->nodes
= (ddg_node_ptr
) xcalloc (num_nodes
, sizeof (struct ddg_node
));
462 g
->closing_branch
= NULL
;
464 first_note
= NULL_RTX
;
465 for (insn
= BB_HEAD (bb
); insn
!= NEXT_INSN (BB_END (bb
));
466 insn
= NEXT_INSN (insn
))
470 if (! first_note
&& NOTE_P (insn
)
471 && NOTE_KIND (insn
) != NOTE_INSN_BASIC_BLOCK
)
477 gcc_assert (!g
->closing_branch
);
478 g
->closing_branch
= &g
->nodes
[i
];
480 else if (GET_CODE (PATTERN (insn
)) == USE
)
487 g
->nodes
[i
].cuid
= i
;
488 g
->nodes
[i
].successors
= sbitmap_alloc (num_nodes
);
489 sbitmap_zero (g
->nodes
[i
].successors
);
490 g
->nodes
[i
].predecessors
= sbitmap_alloc (num_nodes
);
491 sbitmap_zero (g
->nodes
[i
].predecessors
);
492 g
->nodes
[i
].first_note
= (first_note
? first_note
: insn
);
493 g
->nodes
[i
++].insn
= insn
;
494 first_note
= NULL_RTX
;
497 /* We must have found a branch in DDG. */
498 gcc_assert (g
->closing_branch
);
501 /* Build the data dependency graph. */
502 build_intra_loop_deps (g
);
503 build_inter_loop_deps (g
);
507 /* Free all the memory allocated for the DDG. */
516 for (i
= 0; i
< g
->num_nodes
; i
++)
518 ddg_edge_ptr e
= g
->nodes
[i
].out
;
522 ddg_edge_ptr next
= e
->next_out
;
527 sbitmap_free (g
->nodes
[i
].successors
);
528 sbitmap_free (g
->nodes
[i
].predecessors
);
530 if (g
->num_backarcs
> 0)
537 print_ddg_edge (FILE *file
, ddg_edge_ptr e
)
553 fprintf (file
, " [%d -(%c,%d,%d)-> %d] ", INSN_UID (e
->src
->insn
),
554 dep_c
, e
->latency
, e
->distance
, INSN_UID (e
->dest
->insn
));
557 /* Print the DDG nodes with there in/out edges to the dump file. */
559 print_ddg (FILE *file
, ddg_ptr g
)
563 for (i
= 0; i
< g
->num_nodes
; i
++)
567 print_rtl_single (file
, g
->nodes
[i
].insn
);
568 fprintf (file
, "OUT ARCS: ");
569 for (e
= g
->nodes
[i
].out
; e
; e
= e
->next_out
)
570 print_ddg_edge (file
, e
);
572 fprintf (file
, "\nIN ARCS: ");
573 for (e
= g
->nodes
[i
].in
; e
; e
= e
->next_in
)
574 print_ddg_edge (file
, e
);
576 fprintf (file
, "\n");
580 /* Print the given DDG in VCG format. */
582 vcg_print_ddg (FILE *file
, ddg_ptr g
)
586 fprintf (file
, "graph: {\n");
587 for (src_cuid
= 0; src_cuid
< g
->num_nodes
; src_cuid
++)
590 int src_uid
= INSN_UID (g
->nodes
[src_cuid
].insn
);
592 fprintf (file
, "node: {title: \"%d_%d\" info1: \"", src_cuid
, src_uid
);
593 print_rtl_single (file
, g
->nodes
[src_cuid
].insn
);
594 fprintf (file
, "\"}\n");
595 for (e
= g
->nodes
[src_cuid
].out
; e
; e
= e
->next_out
)
597 int dst_uid
= INSN_UID (e
->dest
->insn
);
598 int dst_cuid
= e
->dest
->cuid
;
600 /* Give the backarcs a different color. */
602 fprintf (file
, "backedge: {color: red ");
604 fprintf (file
, "edge: { ");
606 fprintf (file
, "sourcename: \"%d_%d\" ", src_cuid
, src_uid
);
607 fprintf (file
, "targetname: \"%d_%d\" ", dst_cuid
, dst_uid
);
608 fprintf (file
, "label: \"%d_%d\"}\n", e
->latency
, e
->distance
);
611 fprintf (file
, "}\n");
614 /* Dump the sccs in SCCS. */
616 print_sccs (FILE *file
, ddg_all_sccs_ptr sccs
, ddg_ptr g
)
619 sbitmap_iterator sbi
;
625 fprintf (file
, "\n;; Number of SCC nodes - %d\n", sccs
->num_sccs
);
626 for (i
= 0; i
< sccs
->num_sccs
; i
++)
628 fprintf (file
, "SCC number: %d\n", i
);
629 EXECUTE_IF_SET_IN_SBITMAP (sccs
->sccs
[i
]->nodes
, 0, u
, sbi
)
631 fprintf (file
, "insn num %d\n", u
);
632 print_rtl_single (file
, g
->nodes
[u
].insn
);
635 fprintf (file
, "\n");
638 /* Create an edge and initialize it with given values. */
640 create_ddg_edge (ddg_node_ptr src
, ddg_node_ptr dest
,
641 dep_type t
, dep_data_type dt
, int l
, int d
)
643 ddg_edge_ptr e
= (ddg_edge_ptr
) xmalloc (sizeof (struct ddg_edge
));
651 e
->next_in
= e
->next_out
= NULL
;
656 /* Add the given edge to the in/out linked lists of the DDG nodes. */
658 add_edge_to_ddg (ddg_ptr g ATTRIBUTE_UNUSED
, ddg_edge_ptr e
)
660 ddg_node_ptr src
= e
->src
;
661 ddg_node_ptr dest
= e
->dest
;
663 /* Should have allocated the sbitmaps. */
664 gcc_assert (src
->successors
&& dest
->predecessors
);
666 SET_BIT (src
->successors
, dest
->cuid
);
667 SET_BIT (dest
->predecessors
, src
->cuid
);
668 e
->next_in
= dest
->in
;
670 e
->next_out
= src
->out
;
676 /* Algorithm for computing the recurrence_length of an scc. We assume at
677 for now that cycles in the data dependence graph contain a single backarc.
678 This simplifies the algorithm, and can be generalized later. */
680 set_recurrence_length (ddg_scc_ptr scc
, ddg_ptr g
)
685 for (j
= 0; j
< scc
->num_backarcs
; j
++)
687 ddg_edge_ptr backarc
= scc
->backarcs
[j
];
689 int distance
= backarc
->distance
;
690 ddg_node_ptr src
= backarc
->dest
;
691 ddg_node_ptr dest
= backarc
->src
;
693 length
= longest_simple_path (g
, src
->cuid
, dest
->cuid
, scc
->nodes
);
696 /* fprintf (stderr, "Backarc not on simple cycle in SCC.\n"); */
699 length
+= backarc
->latency
;
700 result
= MAX (result
, (length
/ distance
));
702 scc
->recurrence_length
= result
;
705 /* Create a new SCC given the set of its nodes. Compute its recurrence_length
706 and mark edges that belong to this scc as IN_SCC. */
708 create_scc (ddg_ptr g
, sbitmap nodes
)
712 sbitmap_iterator sbi
;
714 scc
= (ddg_scc_ptr
) xmalloc (sizeof (struct ddg_scc
));
715 scc
->backarcs
= NULL
;
716 scc
->num_backarcs
= 0;
717 scc
->nodes
= sbitmap_alloc (g
->num_nodes
);
718 sbitmap_copy (scc
->nodes
, nodes
);
720 /* Mark the backarcs that belong to this SCC. */
721 EXECUTE_IF_SET_IN_SBITMAP (nodes
, 0, u
, sbi
)
724 ddg_node_ptr n
= &g
->nodes
[u
];
726 for (e
= n
->out
; e
; e
= e
->next_out
)
727 if (TEST_BIT (nodes
, e
->dest
->cuid
))
729 e
->aux
.count
= IN_SCC
;
731 add_backarc_to_scc (scc
, e
);
735 set_recurrence_length (scc
, g
);
739 /* Cleans the memory allocation of a given SCC. */
741 free_scc (ddg_scc_ptr scc
)
746 sbitmap_free (scc
->nodes
);
747 if (scc
->num_backarcs
> 0)
748 free (scc
->backarcs
);
753 /* Add a given edge known to be a backarc to the given DDG. */
755 add_backarc_to_ddg (ddg_ptr g
, ddg_edge_ptr e
)
757 int size
= (g
->num_backarcs
+ 1) * sizeof (ddg_edge_ptr
);
759 add_edge_to_ddg (g
, e
);
760 g
->backarcs
= (ddg_edge_ptr
*) xrealloc (g
->backarcs
, size
);
761 g
->backarcs
[g
->num_backarcs
++] = e
;
764 /* Add backarc to an SCC. */
766 add_backarc_to_scc (ddg_scc_ptr scc
, ddg_edge_ptr e
)
768 int size
= (scc
->num_backarcs
+ 1) * sizeof (ddg_edge_ptr
);
770 scc
->backarcs
= (ddg_edge_ptr
*) xrealloc (scc
->backarcs
, size
);
771 scc
->backarcs
[scc
->num_backarcs
++] = e
;
774 /* Add the given SCC to the DDG. */
776 add_scc_to_ddg (ddg_all_sccs_ptr g
, ddg_scc_ptr scc
)
778 int size
= (g
->num_sccs
+ 1) * sizeof (ddg_scc_ptr
);
780 g
->sccs
= (ddg_scc_ptr
*) xrealloc (g
->sccs
, size
);
781 g
->sccs
[g
->num_sccs
++] = scc
;
784 /* Given the instruction INSN return the node that represents it. */
786 get_node_of_insn (ddg_ptr g
, rtx insn
)
790 for (i
= 0; i
< g
->num_nodes
; i
++)
791 if (insn
== g
->nodes
[i
].insn
)
796 /* Given a set OPS of nodes in the DDG, find the set of their successors
797 which are not in OPS, and set their bits in SUCC. Bits corresponding to
798 OPS are cleared from SUCC. Leaves the other bits in SUCC unchanged. */
800 find_successors (sbitmap succ
, ddg_ptr g
, sbitmap ops
)
803 sbitmap_iterator sbi
;
805 EXECUTE_IF_SET_IN_SBITMAP (ops
, 0, i
, sbi
)
807 const sbitmap node_succ
= NODE_SUCCESSORS (&g
->nodes
[i
]);
808 sbitmap_a_or_b (succ
, succ
, node_succ
);
811 /* We want those that are not in ops. */
812 sbitmap_difference (succ
, succ
, ops
);
815 /* Given a set OPS of nodes in the DDG, find the set of their predecessors
816 which are not in OPS, and set their bits in PREDS. Bits corresponding to
817 OPS are cleared from PREDS. Leaves the other bits in PREDS unchanged. */
819 find_predecessors (sbitmap preds
, ddg_ptr g
, sbitmap ops
)
822 sbitmap_iterator sbi
;
824 EXECUTE_IF_SET_IN_SBITMAP (ops
, 0, i
, sbi
)
826 const sbitmap node_preds
= NODE_PREDECESSORS (&g
->nodes
[i
]);
827 sbitmap_a_or_b (preds
, preds
, node_preds
);
830 /* We want those that are not in ops. */
831 sbitmap_difference (preds
, preds
, ops
);
835 /* Compare function to be passed to qsort to order the backarcs in descending
838 compare_sccs (const void *s1
, const void *s2
)
840 const int rec_l1
= (*(const ddg_scc_ptr
*)s1
)->recurrence_length
;
841 const int rec_l2
= (*(const ddg_scc_ptr
*)s2
)->recurrence_length
;
842 return ((rec_l2
> rec_l1
) - (rec_l2
< rec_l1
));
846 /* Order the backarcs in descending recMII order using compare_sccs. */
848 order_sccs (ddg_all_sccs_ptr g
)
850 qsort (g
->sccs
, g
->num_sccs
, sizeof (ddg_scc_ptr
),
851 (int (*) (const void *, const void *)) compare_sccs
);
854 #ifdef ENABLE_CHECKING
855 /* Check that every node in SCCS belongs to exactly one strongly connected
856 component and that no element of SCCS is empty. */
858 check_sccs (ddg_all_sccs_ptr sccs
, int num_nodes
)
861 sbitmap tmp
= sbitmap_alloc (num_nodes
);
864 for (i
= 0; i
< sccs
->num_sccs
; i
++)
866 gcc_assert (!sbitmap_empty_p (sccs
->sccs
[i
]->nodes
));
867 /* Verify that every node in sccs is in exactly one strongly
868 connected component. */
869 gcc_assert (!sbitmap_any_common_bits (tmp
, sccs
->sccs
[i
]->nodes
));
870 sbitmap_a_or_b (tmp
, tmp
, sccs
->sccs
[i
]->nodes
);
876 /* Perform the Strongly Connected Components decomposing algorithm on the
877 DDG and return DDG_ALL_SCCS structure that contains them. */
879 create_ddg_all_sccs (ddg_ptr g
)
882 int num_nodes
= g
->num_nodes
;
883 sbitmap from
= sbitmap_alloc (num_nodes
);
884 sbitmap to
= sbitmap_alloc (num_nodes
);
885 sbitmap scc_nodes
= sbitmap_alloc (num_nodes
);
886 ddg_all_sccs_ptr sccs
= (ddg_all_sccs_ptr
)
887 xmalloc (sizeof (struct ddg_all_sccs
));
893 for (i
= 0; i
< g
->num_backarcs
; i
++)
896 ddg_edge_ptr backarc
= g
->backarcs
[i
];
897 ddg_node_ptr src
= backarc
->src
;
898 ddg_node_ptr dest
= backarc
->dest
;
900 /* If the backarc already belongs to an SCC, continue. */
901 if (backarc
->aux
.count
== IN_SCC
)
904 sbitmap_zero (scc_nodes
);
907 SET_BIT (from
, dest
->cuid
);
908 SET_BIT (to
, src
->cuid
);
910 if (find_nodes_on_paths (scc_nodes
, g
, from
, to
))
912 scc
= create_scc (g
, scc_nodes
);
913 add_scc_to_ddg (sccs
, scc
);
919 sbitmap_free (scc_nodes
);
920 #ifdef ENABLE_CHECKING
921 check_sccs (sccs
, num_nodes
);
926 /* Frees the memory allocated for all SCCs of the DDG, but keeps the DDG. */
928 free_ddg_all_sccs (ddg_all_sccs_ptr all_sccs
)
935 for (i
= 0; i
< all_sccs
->num_sccs
; i
++)
936 free_scc (all_sccs
->sccs
[i
]);
942 /* Given FROM - a bitmap of source nodes - and TO - a bitmap of destination
943 nodes - find all nodes that lie on paths from FROM to TO (not excluding
944 nodes from FROM and TO). Return nonzero if nodes exist. */
946 find_nodes_on_paths (sbitmap result
, ddg_ptr g
, sbitmap from
, sbitmap to
)
951 int num_nodes
= g
->num_nodes
;
952 sbitmap_iterator sbi
;
954 sbitmap workset
= sbitmap_alloc (num_nodes
);
955 sbitmap reachable_from
= sbitmap_alloc (num_nodes
);
956 sbitmap reach_to
= sbitmap_alloc (num_nodes
);
957 sbitmap tmp
= sbitmap_alloc (num_nodes
);
959 sbitmap_copy (reachable_from
, from
);
960 sbitmap_copy (tmp
, from
);
966 sbitmap_copy (workset
, tmp
);
968 EXECUTE_IF_SET_IN_SBITMAP (workset
, 0, u
, sbi
)
971 ddg_node_ptr u_node
= &g
->nodes
[u
];
973 for (e
= u_node
->out
; e
!= (ddg_edge_ptr
) 0; e
= e
->next_out
)
975 ddg_node_ptr v_node
= e
->dest
;
976 int v
= v_node
->cuid
;
978 if (!TEST_BIT (reachable_from
, v
))
980 SET_BIT (reachable_from
, v
);
988 sbitmap_copy (reach_to
, to
);
989 sbitmap_copy (tmp
, to
);
995 sbitmap_copy (workset
, tmp
);
997 EXECUTE_IF_SET_IN_SBITMAP (workset
, 0, u
, sbi
)
1000 ddg_node_ptr u_node
= &g
->nodes
[u
];
1002 for (e
= u_node
->in
; e
!= (ddg_edge_ptr
) 0; e
= e
->next_in
)
1004 ddg_node_ptr v_node
= e
->src
;
1005 int v
= v_node
->cuid
;
1007 if (!TEST_BIT (reach_to
, v
))
1009 SET_BIT (reach_to
, v
);
1017 answer
= sbitmap_a_and_b_cg (result
, reachable_from
, reach_to
);
1018 sbitmap_free (workset
);
1019 sbitmap_free (reachable_from
);
1020 sbitmap_free (reach_to
);
1026 /* Updates the counts of U_NODE's successors (that belong to NODES) to be
1027 at-least as large as the count of U_NODE plus the latency between them.
1028 Sets a bit in TMP for each successor whose count was changed (increased).
1029 Returns nonzero if any count was changed. */
1031 update_dist_to_successors (ddg_node_ptr u_node
, sbitmap nodes
, sbitmap tmp
)
1036 for (e
= u_node
->out
; e
; e
= e
->next_out
)
1038 ddg_node_ptr v_node
= e
->dest
;
1039 int v
= v_node
->cuid
;
1041 if (TEST_BIT (nodes
, v
)
1042 && (e
->distance
== 0)
1043 && (v_node
->aux
.count
< u_node
->aux
.count
+ e
->latency
))
1045 v_node
->aux
.count
= u_node
->aux
.count
+ e
->latency
;
1054 /* Find the length of a longest path from SRC to DEST in G,
1055 going only through NODES, and disregarding backarcs. */
1057 longest_simple_path (struct ddg
* g
, int src
, int dest
, sbitmap nodes
)
1063 int num_nodes
= g
->num_nodes
;
1064 sbitmap workset
= sbitmap_alloc (num_nodes
);
1065 sbitmap tmp
= sbitmap_alloc (num_nodes
);
1068 /* Data will hold the distance of the longest path found so far from
1069 src to each node. Initialize to -1 = less than minimum. */
1070 for (i
= 0; i
< g
->num_nodes
; i
++)
1071 g
->nodes
[i
].aux
.count
= -1;
1072 g
->nodes
[src
].aux
.count
= 0;
1079 sbitmap_iterator sbi
;
1082 sbitmap_copy (workset
, tmp
);
1084 EXECUTE_IF_SET_IN_SBITMAP (workset
, 0, u
, sbi
)
1086 ddg_node_ptr u_node
= &g
->nodes
[u
];
1088 change
|= update_dist_to_successors (u_node
, nodes
, tmp
);
1091 result
= g
->nodes
[dest
].aux
.count
;
1092 sbitmap_free (workset
);