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 RD, add inter-loop true dependences
228 for all its uses in the next iteration, and an output dependence to the
229 first def of the next iteration. */
231 add_deps_for_def (ddg_ptr g, struct df_ref *rd)
233 int regno = DF_REF_REGNO (rd);
234 struct df_ru_bb_info *bb_info = DF_RU_BB_INFO (g->bb);
235 struct df_link *r_use;
236 int use_before_def = false;
237 rtx def_insn = DF_REF_INSN (rd);
238 ddg_node_ptr src_node = get_node_of_insn (g, def_insn);
240 /* Create and inter-loop true dependence between RD and each of its uses
241 that is upwards exposed in RD's block. */
242 for (r_use = DF_REF_CHAIN (rd); r_use != NULL; r_use = r_use->next)
244 if (bitmap_bit_p (bb_info->gen, r_use->ref->id))
246 rtx use_insn = DF_REF_INSN (r_use->ref);
247 ddg_node_ptr dest_node = get_node_of_insn (g, use_insn);
249 gcc_assert (src_node && dest_node);
251 /* Any such upwards exposed use appears before the rd def. */
252 use_before_def = true;
253 create_ddg_dep_no_link (g, src_node, dest_node, TRUE_DEP,
258 /* Create an inter-loop output dependence between RD (which is the
259 last def in its block, being downwards exposed) and the first def
260 in its block. Avoid creating a self output dependence. Avoid creating
261 an output dependence if there is a dependence path between the two defs
262 starting with a true dependence followed by an anti dependence (i.e. if
263 there is a use between the two defs. */
264 if (! use_before_def)
266 struct df_ref *def = df_bb_regno_first_def_find (g->bb, regno);
268 ddg_node_ptr dest_node;
270 if (!def || rd->id == def->id)
273 /* Check if there are uses after RD. */
274 for (i = src_node->cuid + 1; i < g->num_nodes; i++)
275 if (df_find_use (g->nodes[i].insn, DF_REF_REG (rd)))
278 dest_node = get_node_of_insn (g, def->insn);
279 create_ddg_dep_no_link (g, src_node, dest_node, OUTPUT_DEP, REG_DEP, 1);
283 /* Given a register USE, add an inter-loop anti dependence to the first
284 (nearest BLOCK_BEGIN) def of the next iteration, unless USE is followed
285 by a def in the block. */
287 add_deps_for_use (ddg_ptr g, struct df_ref *use)
290 int regno = DF_REF_REGNO (use);
291 struct df_ref *first_def = df_bb_regno_first_def_find (g->bb, regno);
292 ddg_node_ptr use_node;
293 ddg_node_ptr def_node;
294 struct df_rd_bb_info *bb_info;
296 bb_info = DF_RD_BB_INFO (g->bb);
301 use_node = get_node_of_insn (g, use->insn);
302 def_node = get_node_of_insn (g, first_def->insn);
304 gcc_assert (use_node && def_node);
306 /* Make sure there are no defs after USE. */
307 for (i = use_node->cuid + 1; i < g->num_nodes; i++)
308 if (df_find_def (g->nodes[i].insn, DF_REF_REG (use)))
310 /* We must not add ANTI dep when there is an intra-loop TRUE dep in
311 the opposite direction. If the first_def reaches the USE then there is
313 if (! bitmap_bit_p (bb_info->gen, first_def->id))
314 create_ddg_dep_no_link (g, use_node, def_node, ANTI_DEP, REG_DEP, 1);
317 /* Build inter-loop dependencies, by looking at DF analysis backwards. */
319 build_inter_loop_deps (ddg_ptr g)
321 unsigned rd_num, u_num;
322 struct df_rd_bb_info *rd_bb_info;
323 struct df_ru_bb_info *ru_bb_info;
326 rd_bb_info = DF_RD_BB_INFO (g->bb);
328 /* Find inter-loop output and true deps by connecting downward exposed defs
329 to the first def of the BB and to upwards exposed uses. */
330 EXECUTE_IF_SET_IN_BITMAP (rd_bb_info->gen, 0, rd_num, bi)
332 struct df_ref *rd = DF_DEFS_GET (rd_num);
334 add_deps_for_def (g, rd);
337 ru_bb_info = DF_RU_BB_INFO (g->bb);
339 /* Find inter-loop anti deps. We are interested in uses of the block that
340 appear below all defs; this implies that these uses are killed. */
341 EXECUTE_IF_SET_IN_BITMAP (ru_bb_info->kill, 0, u_num, bi)
343 struct df_ref *use = DF_USES_GET (u_num);
344 if (!(DF_REF_FLAGS (use) & DF_REF_IN_NOTE))
345 /* We are interested in uses of this BB. */
346 if (BLOCK_FOR_INSN (use->insn) == g->bb)
347 add_deps_for_use (g, use);
351 /* Given two nodes, analyze their RTL insns and add inter-loop mem deps
354 add_inter_loop_mem_dep (ddg_ptr g, ddg_node_ptr from, ddg_node_ptr to)
356 if (mem_write_insn_p (from->insn))
358 if (mem_read_insn_p (to->insn))
359 create_ddg_dep_no_link (g, from, to, TRUE_DEP, MEM_DEP, 1);
360 else if (from->cuid != to->cuid)
361 create_ddg_dep_no_link (g, from, to, OUTPUT_DEP, MEM_DEP, 1);
365 if (mem_read_insn_p (to->insn))
367 else if (from->cuid != to->cuid)
369 create_ddg_dep_no_link (g, from, to, ANTI_DEP, MEM_DEP, 1);
370 create_ddg_dep_no_link (g, to, from, TRUE_DEP, MEM_DEP, 1);
376 /* Perform intra-block Data Dependency analysis and connect the nodes in
377 the DDG. We assume the loop has a single basic block. */
379 build_intra_loop_deps (ddg_ptr g)
382 /* Hold the dependency analysis state during dependency calculations. */
383 struct deps tmp_deps;
387 /* Build the dependence information, using the sched_analyze function. */
389 init_deps (&tmp_deps);
391 /* Do the intra-block data dependence analysis for the given block. */
392 get_ebb_head_tail (g->bb, g->bb, &head, &tail);
393 sched_analyze (&tmp_deps, head, tail);
395 /* Build intra-loop data dependencies using the scheduler dependency
397 for (i = 0; i < g->num_nodes; i++)
399 ddg_node_ptr dest_node = &g->nodes[i];
401 if (! INSN_P (dest_node->insn))
404 FOR_EACH_DEP_LINK (link, INSN_BACK_DEPS (dest_node->insn))
406 dep_t dep = DEP_LINK_DEP (link);
407 ddg_node_ptr src_node = get_node_of_insn (g, DEP_PRO (dep));
413 create_ddg_dependence (g, src_node, dest_node, dep);
416 /* If this insn modifies memory, add an edge to all insns that access
418 if (mem_access_insn_p (dest_node->insn))
422 for (j = 0; j <= i; j++)
424 ddg_node_ptr j_node = &g->nodes[j];
425 if (mem_access_insn_p (j_node->insn))
426 /* Don't bother calculating inter-loop dep if an intra-loop dep
428 if (! TEST_BIT (dest_node->successors, j))
429 add_inter_loop_mem_dep (g, dest_node, j_node);
434 /* Free the INSN_LISTs. */
435 finish_deps_global ();
436 free_deps (&tmp_deps);
440 /* Given a basic block, create its DDG and return a pointer to a variable
441 of ddg type that represents it.
442 Initialize the ddg structure fields to the appropriate values. */
444 create_ddg (basic_block bb, int closing_branch_deps)
447 rtx insn, first_note;
451 g = (ddg_ptr) xcalloc (1, sizeof (struct ddg));
454 g->closing_branch_deps = closing_branch_deps;
456 /* Count the number of insns in the BB. */
457 for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb));
458 insn = NEXT_INSN (insn))
460 if (! INSN_P (insn) || GET_CODE (PATTERN (insn)) == USE)
463 if (mem_read_insn_p (insn))
465 if (mem_write_insn_p (insn))
470 /* There is nothing to do for this BB. */
477 /* Allocate the nodes array, and initialize the nodes. */
478 g->num_nodes = num_nodes;
479 g->nodes = (ddg_node_ptr) xcalloc (num_nodes, sizeof (struct ddg_node));
480 g->closing_branch = NULL;
482 first_note = NULL_RTX;
483 for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb));
484 insn = NEXT_INSN (insn))
488 if (! first_note && NOTE_P (insn)
489 && NOTE_KIND (insn) != NOTE_INSN_BASIC_BLOCK)
495 gcc_assert (!g->closing_branch);
496 g->closing_branch = &g->nodes[i];
498 else if (GET_CODE (PATTERN (insn)) == USE)
505 g->nodes[i].cuid = i;
506 g->nodes[i].successors = sbitmap_alloc (num_nodes);
507 sbitmap_zero (g->nodes[i].successors);
508 g->nodes[i].predecessors = sbitmap_alloc (num_nodes);
509 sbitmap_zero (g->nodes[i].predecessors);
510 g->nodes[i].first_note = (first_note ? first_note : insn);
511 g->nodes[i++].insn = insn;
512 first_note = NULL_RTX;
515 /* We must have found a branch in DDG. */
516 gcc_assert (g->closing_branch);
519 /* Build the data dependency graph. */
520 build_intra_loop_deps (g);
521 build_inter_loop_deps (g);
525 /* Free all the memory allocated for the DDG. */
534 for (i = 0; i < g->num_nodes; i++)
536 ddg_edge_ptr e = g->nodes[i].out;
540 ddg_edge_ptr next = e->next_out;
545 sbitmap_free (g->nodes[i].successors);
546 sbitmap_free (g->nodes[i].predecessors);
548 if (g->num_backarcs > 0)
555 print_ddg_edge (FILE *file, ddg_edge_ptr e)
571 fprintf (file, " [%d -(%c,%d,%d)-> %d] ", INSN_UID (e->src->insn),
572 dep_c, e->latency, e->distance, INSN_UID (e->dest->insn));
575 /* Print the DDG nodes with there in/out edges to the dump file. */
577 print_ddg (FILE *file, ddg_ptr g)
581 for (i = 0; i < g->num_nodes; i++)
585 print_rtl_single (file, g->nodes[i].insn);
586 fprintf (file, "OUT ARCS: ");
587 for (e = g->nodes[i].out; e; e = e->next_out)
588 print_ddg_edge (file, e);
590 fprintf (file, "\nIN ARCS: ");
591 for (e = g->nodes[i].in; e; e = e->next_in)
592 print_ddg_edge (file, e);
594 fprintf (file, "\n");
598 /* Print the given DDG in VCG format. */
600 vcg_print_ddg (FILE *file, ddg_ptr g)
604 fprintf (file, "graph: {\n");
605 for (src_cuid = 0; src_cuid < g->num_nodes; src_cuid++)
608 int src_uid = INSN_UID (g->nodes[src_cuid].insn);
610 fprintf (file, "node: {title: \"%d_%d\" info1: \"", src_cuid, src_uid);
611 print_rtl_single (file, g->nodes[src_cuid].insn);
612 fprintf (file, "\"}\n");
613 for (e = g->nodes[src_cuid].out; e; e = e->next_out)
615 int dst_uid = INSN_UID (e->dest->insn);
616 int dst_cuid = e->dest->cuid;
618 /* Give the backarcs a different color. */
620 fprintf (file, "backedge: {color: red ");
622 fprintf (file, "edge: { ");
624 fprintf (file, "sourcename: \"%d_%d\" ", src_cuid, src_uid);
625 fprintf (file, "targetname: \"%d_%d\" ", dst_cuid, dst_uid);
626 fprintf (file, "label: \"%d_%d\"}\n", e->latency, e->distance);
629 fprintf (file, "}\n");
632 /* Dump the sccs in SCCS. */
634 print_sccs (FILE *file, ddg_all_sccs_ptr sccs, ddg_ptr g)
637 sbitmap_iterator sbi;
643 fprintf (file, "\n;; Number of SCC nodes - %d\n", sccs->num_sccs);
644 for (i = 0; i < sccs->num_sccs; i++)
646 fprintf (file, "SCC number: %d\n", i);
647 EXECUTE_IF_SET_IN_SBITMAP (sccs->sccs[i]->nodes, 0, u, sbi)
649 fprintf (file, "insn num %d\n", u);
650 print_rtl_single (file, g->nodes[u].insn);
653 fprintf (file, "\n");
656 /* Create an edge and initialize it with given values. */
658 create_ddg_edge (ddg_node_ptr src, ddg_node_ptr dest,
659 dep_type t, dep_data_type dt, int l, int d)
661 ddg_edge_ptr e = (ddg_edge_ptr) xmalloc (sizeof (struct ddg_edge));
669 e->next_in = e->next_out = NULL;
674 /* Add the given edge to the in/out linked lists of the DDG nodes. */
676 add_edge_to_ddg (ddg_ptr g ATTRIBUTE_UNUSED, ddg_edge_ptr e)
678 ddg_node_ptr src = e->src;
679 ddg_node_ptr dest = e->dest;
681 /* Should have allocated the sbitmaps. */
682 gcc_assert (src->successors && dest->predecessors);
684 SET_BIT (src->successors, dest->cuid);
685 SET_BIT (dest->predecessors, src->cuid);
686 e->next_in = dest->in;
688 e->next_out = src->out;
694 /* Algorithm for computing the recurrence_length of an scc. We assume at
695 for now that cycles in the data dependence graph contain a single backarc.
696 This simplifies the algorithm, and can be generalized later. */
698 set_recurrence_length (ddg_scc_ptr scc, ddg_ptr g)
703 for (j = 0; j < scc->num_backarcs; j++)
705 ddg_edge_ptr backarc = scc->backarcs[j];
707 int distance = backarc->distance;
708 ddg_node_ptr src = backarc->dest;
709 ddg_node_ptr dest = backarc->src;
711 length = longest_simple_path (g, src->cuid, dest->cuid, scc->nodes);
714 /* fprintf (stderr, "Backarc not on simple cycle in SCC.\n"); */
717 length += backarc->latency;
718 result = MAX (result, (length / distance));
720 scc->recurrence_length = result;
723 /* Create a new SCC given the set of its nodes. Compute its recurrence_length
724 and mark edges that belong to this scc as IN_SCC. */
726 create_scc (ddg_ptr g, sbitmap nodes)
730 sbitmap_iterator sbi;
732 scc = (ddg_scc_ptr) xmalloc (sizeof (struct ddg_scc));
733 scc->backarcs = NULL;
734 scc->num_backarcs = 0;
735 scc->nodes = sbitmap_alloc (g->num_nodes);
736 sbitmap_copy (scc->nodes, nodes);
738 /* Mark the backarcs that belong to this SCC. */
739 EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, u, sbi)
742 ddg_node_ptr n = &g->nodes[u];
744 for (e = n->out; e; e = e->next_out)
745 if (TEST_BIT (nodes, e->dest->cuid))
747 e->aux.count = IN_SCC;
749 add_backarc_to_scc (scc, e);
753 set_recurrence_length (scc, g);
757 /* Cleans the memory allocation of a given SCC. */
759 free_scc (ddg_scc_ptr scc)
764 sbitmap_free (scc->nodes);
765 if (scc->num_backarcs > 0)
766 free (scc->backarcs);
771 /* Add a given edge known to be a backarc to the given DDG. */
773 add_backarc_to_ddg (ddg_ptr g, ddg_edge_ptr e)
775 int size = (g->num_backarcs + 1) * sizeof (ddg_edge_ptr);
777 add_edge_to_ddg (g, e);
778 g->backarcs = (ddg_edge_ptr *) xrealloc (g->backarcs, size);
779 g->backarcs[g->num_backarcs++] = e;
782 /* Add backarc to an SCC. */
784 add_backarc_to_scc (ddg_scc_ptr scc, ddg_edge_ptr e)
786 int size = (scc->num_backarcs + 1) * sizeof (ddg_edge_ptr);
788 scc->backarcs = (ddg_edge_ptr *) xrealloc (scc->backarcs, size);
789 scc->backarcs[scc->num_backarcs++] = e;
792 /* Add the given SCC to the DDG. */
794 add_scc_to_ddg (ddg_all_sccs_ptr g, ddg_scc_ptr scc)
796 int size = (g->num_sccs + 1) * sizeof (ddg_scc_ptr);
798 g->sccs = (ddg_scc_ptr *) xrealloc (g->sccs, size);
799 g->sccs[g->num_sccs++] = scc;
802 /* Given the instruction INSN return the node that represents it. */
804 get_node_of_insn (ddg_ptr g, rtx insn)
808 for (i = 0; i < g->num_nodes; i++)
809 if (insn == g->nodes[i].insn)
814 /* Given a set OPS of nodes in the DDG, find the set of their successors
815 which are not in OPS, and set their bits in SUCC. Bits corresponding to
816 OPS are cleared from SUCC. Leaves the other bits in SUCC unchanged. */
818 find_successors (sbitmap succ, ddg_ptr g, sbitmap ops)
821 sbitmap_iterator sbi;
823 EXECUTE_IF_SET_IN_SBITMAP (ops, 0, i, sbi)
825 const sbitmap node_succ = NODE_SUCCESSORS (&g->nodes[i]);
826 sbitmap_a_or_b (succ, succ, node_succ);
829 /* We want those that are not in ops. */
830 sbitmap_difference (succ, succ, ops);
833 /* Given a set OPS of nodes in the DDG, find the set of their predecessors
834 which are not in OPS, and set their bits in PREDS. Bits corresponding to
835 OPS are cleared from PREDS. Leaves the other bits in PREDS unchanged. */
837 find_predecessors (sbitmap preds, ddg_ptr g, sbitmap ops)
840 sbitmap_iterator sbi;
842 EXECUTE_IF_SET_IN_SBITMAP (ops, 0, i, sbi)
844 const sbitmap node_preds = NODE_PREDECESSORS (&g->nodes[i]);
845 sbitmap_a_or_b (preds, preds, node_preds);
848 /* We want those that are not in ops. */
849 sbitmap_difference (preds, preds, ops);
853 /* Compare function to be passed to qsort to order the backarcs in descending
856 compare_sccs (const void *s1, const void *s2)
858 const int rec_l1 = (*(const ddg_scc_ptr *)s1)->recurrence_length;
859 const int rec_l2 = (*(const ddg_scc_ptr *)s2)->recurrence_length;
860 return ((rec_l2 > rec_l1) - (rec_l2 < rec_l1));
864 /* Order the backarcs in descending recMII order using compare_sccs. */
866 order_sccs (ddg_all_sccs_ptr g)
868 qsort (g->sccs, g->num_sccs, sizeof (ddg_scc_ptr),
869 (int (*) (const void *, const void *)) compare_sccs);
872 #ifdef ENABLE_CHECKING
873 /* Check that every node in SCCS belongs to exactly one strongly connected
874 component and that no element of SCCS is empty. */
876 check_sccs (ddg_all_sccs_ptr sccs, int num_nodes)
879 sbitmap tmp = sbitmap_alloc (num_nodes);
882 for (i = 0; i < sccs->num_sccs; i++)
884 gcc_assert (!sbitmap_empty_p (sccs->sccs[i]->nodes));
885 /* Verify that every node in sccs is in exactly one strongly
886 connected component. */
887 gcc_assert (!sbitmap_any_common_bits (tmp, sccs->sccs[i]->nodes));
888 sbitmap_a_or_b (tmp, tmp, sccs->sccs[i]->nodes);
894 /* Perform the Strongly Connected Components decomposing algorithm on the
895 DDG and return DDG_ALL_SCCS structure that contains them. */
897 create_ddg_all_sccs (ddg_ptr g)
900 int num_nodes = g->num_nodes;
901 sbitmap from = sbitmap_alloc (num_nodes);
902 sbitmap to = sbitmap_alloc (num_nodes);
903 sbitmap scc_nodes = sbitmap_alloc (num_nodes);
904 ddg_all_sccs_ptr sccs = (ddg_all_sccs_ptr)
905 xmalloc (sizeof (struct ddg_all_sccs));
911 for (i = 0; i < g->num_backarcs; i++)
914 ddg_edge_ptr backarc = g->backarcs[i];
915 ddg_node_ptr src = backarc->src;
916 ddg_node_ptr dest = backarc->dest;
918 /* If the backarc already belongs to an SCC, continue. */
919 if (backarc->aux.count == IN_SCC)
922 sbitmap_zero (scc_nodes);
925 SET_BIT (from, dest->cuid);
926 SET_BIT (to, src->cuid);
928 if (find_nodes_on_paths (scc_nodes, g, from, to))
930 scc = create_scc (g, scc_nodes);
931 add_scc_to_ddg (sccs, scc);
937 sbitmap_free (scc_nodes);
938 #ifdef ENABLE_CHECKING
939 check_sccs (sccs, num_nodes);
944 /* Frees the memory allocated for all SCCs of the DDG, but keeps the DDG. */
946 free_ddg_all_sccs (ddg_all_sccs_ptr all_sccs)
953 for (i = 0; i < all_sccs->num_sccs; i++)
954 free_scc (all_sccs->sccs[i]);
960 /* Given FROM - a bitmap of source nodes - and TO - a bitmap of destination
961 nodes - find all nodes that lie on paths from FROM to TO (not excluding
962 nodes from FROM and TO). Return nonzero if nodes exist. */
964 find_nodes_on_paths (sbitmap result, ddg_ptr g, sbitmap from, sbitmap to)
969 int num_nodes = g->num_nodes;
970 sbitmap_iterator sbi;
972 sbitmap workset = sbitmap_alloc (num_nodes);
973 sbitmap reachable_from = sbitmap_alloc (num_nodes);
974 sbitmap reach_to = sbitmap_alloc (num_nodes);
975 sbitmap tmp = sbitmap_alloc (num_nodes);
977 sbitmap_copy (reachable_from, from);
978 sbitmap_copy (tmp, from);
984 sbitmap_copy (workset, tmp);
986 EXECUTE_IF_SET_IN_SBITMAP (workset, 0, u, sbi)
989 ddg_node_ptr u_node = &g->nodes[u];
991 for (e = u_node->out; e != (ddg_edge_ptr) 0; e = e->next_out)
993 ddg_node_ptr v_node = e->dest;
994 int v = v_node->cuid;
996 if (!TEST_BIT (reachable_from, v))
998 SET_BIT (reachable_from, v);
1006 sbitmap_copy (reach_to, to);
1007 sbitmap_copy (tmp, to);
1013 sbitmap_copy (workset, tmp);
1015 EXECUTE_IF_SET_IN_SBITMAP (workset, 0, u, sbi)
1018 ddg_node_ptr u_node = &g->nodes[u];
1020 for (e = u_node->in; e != (ddg_edge_ptr) 0; e = e->next_in)
1022 ddg_node_ptr v_node = e->src;
1023 int v = v_node->cuid;
1025 if (!TEST_BIT (reach_to, v))
1027 SET_BIT (reach_to, v);
1035 answer = sbitmap_a_and_b_cg (result, reachable_from, reach_to);
1036 sbitmap_free (workset);
1037 sbitmap_free (reachable_from);
1038 sbitmap_free (reach_to);
1044 /* Updates the counts of U_NODE's successors (that belong to NODES) to be
1045 at-least as large as the count of U_NODE plus the latency between them.
1046 Sets a bit in TMP for each successor whose count was changed (increased).
1047 Returns nonzero if any count was changed. */
1049 update_dist_to_successors (ddg_node_ptr u_node, sbitmap nodes, sbitmap tmp)
1054 for (e = u_node->out; e; e = e->next_out)
1056 ddg_node_ptr v_node = e->dest;
1057 int v = v_node->cuid;
1059 if (TEST_BIT (nodes, v)
1060 && (e->distance == 0)
1061 && (v_node->aux.count < u_node->aux.count + e->latency))
1063 v_node->aux.count = u_node->aux.count + e->latency;
1072 /* Find the length of a longest path from SRC to DEST in G,
1073 going only through NODES, and disregarding backarcs. */
1075 longest_simple_path (struct ddg * g, int src, int dest, sbitmap nodes)
1081 int num_nodes = g->num_nodes;
1082 sbitmap workset = sbitmap_alloc (num_nodes);
1083 sbitmap tmp = sbitmap_alloc (num_nodes);
1086 /* Data will hold the distance of the longest path found so far from
1087 src to each node. Initialize to -1 = less than minimum. */
1088 for (i = 0; i < g->num_nodes; i++)
1089 g->nodes[i].aux.count = -1;
1090 g->nodes[src].aux.count = 0;
1097 sbitmap_iterator sbi;
1100 sbitmap_copy (workset, tmp);
1102 EXECUTE_IF_SET_IN_SBITMAP (workset, 0, u, sbi)
1104 ddg_node_ptr u_node = &g->nodes[u];
1106 change |= update_dist_to_successors (u_node, nodes, tmp);
1109 result = g->nodes[dest].aux.count;
1110 sbitmap_free (workset);