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 #ifdef INSN_SCHEDULING
49 /* A flag indicating that a ddg edge belongs to an SCC or not. */
50 enum edge_flag {NOT_IN_SCC = 0, IN_SCC};
52 /* Forward declarations. */
53 static void add_backarc_to_ddg (ddg_ptr, ddg_edge_ptr);
54 static void add_backarc_to_scc (ddg_scc_ptr, ddg_edge_ptr);
55 static void add_scc_to_ddg (ddg_all_sccs_ptr, ddg_scc_ptr);
56 static void create_ddg_dep_from_intra_loop_link (ddg_ptr, ddg_node_ptr,
58 static void create_ddg_dep_no_link (ddg_ptr, ddg_node_ptr, ddg_node_ptr,
59 dep_type, dep_data_type, int);
60 static ddg_edge_ptr create_ddg_edge (ddg_node_ptr, ddg_node_ptr, dep_type,
61 dep_data_type, int, int);
62 static void add_edge_to_ddg (ddg_ptr g, ddg_edge_ptr);
64 /* Auxiliary variable for mem_read_insn_p/mem_write_insn_p. */
65 static bool mem_ref_p;
67 /* Auxiliary function for mem_read_insn_p. */
69 mark_mem_use (rtx *x, void *data ATTRIBUTE_UNUSED)
76 /* Auxiliary function for mem_read_insn_p. */
78 mark_mem_use_1 (rtx *x, void *data)
80 for_each_rtx (x, mark_mem_use, data);
83 /* Returns nonzero if INSN reads from memory. */
85 mem_read_insn_p (rtx insn)
88 note_uses (&PATTERN (insn), mark_mem_use_1, NULL);
93 mark_mem_store (rtx loc, const_rtx setter ATTRIBUTE_UNUSED, void *data ATTRIBUTE_UNUSED)
99 /* Returns nonzero if INSN writes to memory. */
101 mem_write_insn_p (rtx insn)
104 note_stores (PATTERN (insn), mark_mem_store, NULL);
108 /* Returns nonzero if X has access to memory. */
110 rtx_mem_access_p (rtx x)
123 fmt = GET_RTX_FORMAT (code);
124 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
128 if (rtx_mem_access_p (XEXP (x, i)))
131 else if (fmt[i] == 'E')
132 for (j = 0; j < XVECLEN (x, i); j++)
134 if (rtx_mem_access_p (XVECEXP (x, i, j)))
141 /* Returns nonzero if INSN reads to or writes from memory. */
143 mem_access_insn_p (rtx insn)
145 return rtx_mem_access_p (PATTERN (insn));
148 /* Computes the dependence parameters (latency, distance etc.), creates
149 a ddg_edge and adds it to the given DDG. */
151 create_ddg_dep_from_intra_loop_link (ddg_ptr g, ddg_node_ptr src_node,
152 ddg_node_ptr dest_node, dep_t link)
155 int latency, distance = 0;
156 dep_type t = TRUE_DEP;
157 dep_data_type dt = (mem_access_insn_p (src_node->insn)
158 && mem_access_insn_p (dest_node->insn) ? MEM_DEP
160 gcc_assert (src_node->cuid < dest_node->cuid);
163 /* Note: REG_DEP_ANTI applies to MEM ANTI_DEP as well!! */
164 if (DEP_TYPE (link) == REG_DEP_ANTI)
166 else if (DEP_TYPE (link) == REG_DEP_OUTPUT)
169 /* We currently choose not to create certain anti-deps edges and
170 compensate for that by generating reg-moves based on the life-range
171 analysis. The anti-deps that will be deleted are the ones which
172 have true-deps edges in the opposite direction (in other words
173 the kernel has only one def of the relevant register). TODO:
174 support the removal of all anti-deps edges, i.e. including those
175 whose register has multiple defs in the loop. */
176 if (flag_modulo_sched_allow_regmoves && (t == ANTI_DEP && dt == REG_DEP))
180 set = single_set (dest_node->insn);
181 /* TODO: Handle registers that REG_P is not true for them, i.e.
182 subregs and special registers. */
183 if (set && REG_P (SET_DEST (set)))
185 int regno = REGNO (SET_DEST (set));
186 struct df_ref *first_def;
187 struct df_ref *last_def;
189 first_def = df_bb_regno_first_def_find (g->bb, regno);
190 gcc_assert (first_def);
192 last_def = df_bb_regno_last_def_find (g->bb, regno);
193 if (first_def == last_def)
198 latency = dep_cost (link);
199 e = create_ddg_edge (src_node, dest_node, t, dt, latency, distance);
200 add_edge_to_ddg (g, e);
203 /* The same as the above function, but it doesn't require a link parameter. */
205 create_ddg_dep_no_link (ddg_ptr g, ddg_node_ptr from, ddg_node_ptr to,
206 dep_type d_t, dep_data_type d_dt, int distance)
210 enum reg_note dep_kind;
211 struct _dep _dep, *dep = &_dep;
214 dep_kind = REG_DEP_ANTI;
215 else if (d_t == OUTPUT_DEP)
216 dep_kind = REG_DEP_OUTPUT;
219 gcc_assert (d_t == TRUE_DEP);
221 dep_kind = REG_DEP_TRUE;
224 init_dep (dep, from->insn, to->insn, dep_kind);
228 e = create_ddg_edge (from, to, d_t, d_dt, l, distance);
230 add_backarc_to_ddg (g, e);
232 add_edge_to_ddg (g, e);
236 /* Given a downwards exposed register def LAST_DEF (which is the last
237 definition of that register in the bb), add inter-loop true dependences
238 to all its uses in the next iteration, an output dependence to the
239 first def of the same register (possibly itself) in the next iteration
240 and anti-dependences from its uses in the current iteration to the
241 first definition in the next iteration. */
243 add_cross_iteration_register_deps (ddg_ptr g, struct df_ref *last_def)
245 int regno = DF_REF_REGNO (last_def);
246 struct df_link *r_use;
247 int has_use_in_bb_p = false;
248 rtx def_insn = DF_REF_INSN (last_def);
249 ddg_node_ptr last_def_node = get_node_of_insn (g, def_insn);
250 ddg_node_ptr use_node;
251 #ifdef ENABLE_CHECKING
252 struct df_rd_bb_info *bb_info = DF_RD_BB_INFO (g->bb);
254 struct df_ref *first_def = df_bb_regno_first_def_find (g->bb, regno);
256 gcc_assert (last_def_node);
257 gcc_assert (first_def);
259 #ifdef ENABLE_CHECKING
260 if (last_def->id != first_def->id)
261 gcc_assert (!bitmap_bit_p (bb_info->gen, first_def->id));
264 /* Create inter-loop true dependences and anti dependences. */
265 for (r_use = DF_REF_CHAIN (last_def); r_use != NULL; r_use = r_use->next)
267 rtx use_insn = DF_REF_INSN (r_use->ref);
269 if (BLOCK_FOR_INSN (use_insn) != g->bb)
272 /* ??? Do not handle uses with DF_REF_IN_NOTE notes. */
273 use_node = get_node_of_insn (g, use_insn);
274 gcc_assert (use_node);
275 has_use_in_bb_p = true;
276 if (use_node->cuid <= last_def_node->cuid)
278 /* Add true deps from last_def to it's uses in the next
279 iteration. Any such upwards exposed use appears before
281 create_ddg_dep_no_link (g, last_def_node, use_node, TRUE_DEP,
286 /* Add anti deps from last_def's uses in the current iteration
287 to the first def in the next iteration. We do not add ANTI
288 dep when there is an intra-loop TRUE dep in the opposite
289 direction, but use regmoves to fix such disregarded ANTI
290 deps when broken. If the first_def reaches the USE then
291 there is such a dep. */
292 ddg_node_ptr first_def_node = get_node_of_insn (g,
295 gcc_assert (first_def_node);
297 if (last_def->id != first_def->id
298 || !flag_modulo_sched_allow_regmoves)
299 create_ddg_dep_no_link (g, use_node, first_def_node, ANTI_DEP,
304 /* Create an inter-loop output dependence between LAST_DEF (which is the
305 last def in its block, being downwards exposed) and the first def in
306 its block. Avoid creating a self output dependence. Avoid creating
307 an output dependence if there is a dependence path between the two
308 defs starting with a true dependence to a use which can be in the
309 next iteration; followed by an anti dependence of that use to the
310 first def (i.e. if there is a use between the two defs.) */
311 if (!has_use_in_bb_p)
313 ddg_node_ptr dest_node;
315 if (last_def->id == first_def->id)
318 dest_node = get_node_of_insn (g, first_def->insn);
319 gcc_assert (dest_node);
320 create_ddg_dep_no_link (g, last_def_node, dest_node,
321 OUTPUT_DEP, REG_DEP, 1);
324 /* Build inter-loop dependencies, by looking at DF analysis backwards. */
326 build_inter_loop_deps (ddg_ptr g)
329 struct df_rd_bb_info *rd_bb_info;
332 rd_bb_info = DF_RD_BB_INFO (g->bb);
334 /* Find inter-loop register output, true and anti deps. */
335 EXECUTE_IF_SET_IN_BITMAP (rd_bb_info->gen, 0, rd_num, bi)
337 struct df_ref *rd = DF_DEFS_GET (rd_num);
339 add_cross_iteration_register_deps (g, rd);
344 /* Given two nodes, analyze their RTL insns and add inter-loop mem deps
347 add_inter_loop_mem_dep (ddg_ptr g, ddg_node_ptr from, ddg_node_ptr to)
349 if (mem_write_insn_p (from->insn))
351 if (mem_read_insn_p (to->insn))
352 create_ddg_dep_no_link (g, from, to, TRUE_DEP, MEM_DEP, 1);
353 else if (from->cuid != to->cuid)
354 create_ddg_dep_no_link (g, from, to, OUTPUT_DEP, MEM_DEP, 1);
358 if (mem_read_insn_p (to->insn))
360 else if (from->cuid != to->cuid)
362 create_ddg_dep_no_link (g, from, to, ANTI_DEP, MEM_DEP, 1);
363 create_ddg_dep_no_link (g, to, from, TRUE_DEP, MEM_DEP, 1);
369 /* Perform intra-block Data Dependency analysis and connect the nodes in
370 the DDG. We assume the loop has a single basic block. */
372 build_intra_loop_deps (ddg_ptr g)
375 /* Hold the dependency analysis state during dependency calculations. */
376 struct deps tmp_deps;
379 /* Build the dependence information, using the sched_analyze function. */
381 init_deps (&tmp_deps);
383 /* Do the intra-block data dependence analysis for the given block. */
384 get_ebb_head_tail (g->bb, g->bb, &head, &tail);
385 sched_analyze (&tmp_deps, head, tail);
387 /* Build intra-loop data dependencies using the scheduler dependency
389 for (i = 0; i < g->num_nodes; i++)
391 ddg_node_ptr dest_node = &g->nodes[i];
392 sd_iterator_def sd_it;
395 if (! INSN_P (dest_node->insn))
398 FOR_EACH_DEP (dest_node->insn, SD_LIST_BACK, sd_it, dep)
400 ddg_node_ptr src_node = get_node_of_insn (g, DEP_PRO (dep));
405 create_ddg_dep_from_intra_loop_link (g, src_node, dest_node, dep);
408 /* If this insn modifies memory, add an edge to all insns that access
410 if (mem_access_insn_p (dest_node->insn))
414 for (j = 0; j <= i; j++)
416 ddg_node_ptr j_node = &g->nodes[j];
417 if (mem_access_insn_p (j_node->insn))
418 /* Don't bother calculating inter-loop dep if an intra-loop dep
420 if (! TEST_BIT (dest_node->successors, j))
421 add_inter_loop_mem_dep (g, dest_node, j_node);
426 /* Free the INSN_LISTs. */
427 finish_deps_global ();
428 free_deps (&tmp_deps);
430 /* Free dependencies. */
431 sched_free_deps (head, tail, false);
435 /* Given a basic block, create its DDG and return a pointer to a variable
436 of ddg type that represents it.
437 Initialize the ddg structure fields to the appropriate values. */
439 create_ddg (basic_block bb, int closing_branch_deps)
442 rtx insn, first_note;
446 g = (ddg_ptr) xcalloc (1, sizeof (struct ddg));
449 g->closing_branch_deps = closing_branch_deps;
451 /* Count the number of insns in the BB. */
452 for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb));
453 insn = NEXT_INSN (insn))
455 if (! INSN_P (insn) || GET_CODE (PATTERN (insn)) == USE)
458 if (mem_read_insn_p (insn))
460 if (mem_write_insn_p (insn))
465 /* There is nothing to do for this BB. */
472 /* Allocate the nodes array, and initialize the nodes. */
473 g->num_nodes = num_nodes;
474 g->nodes = (ddg_node_ptr) xcalloc (num_nodes, sizeof (struct ddg_node));
475 g->closing_branch = NULL;
477 first_note = NULL_RTX;
478 for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb));
479 insn = NEXT_INSN (insn))
483 if (! first_note && NOTE_P (insn)
484 && NOTE_KIND (insn) != NOTE_INSN_BASIC_BLOCK)
490 gcc_assert (!g->closing_branch);
491 g->closing_branch = &g->nodes[i];
493 else if (GET_CODE (PATTERN (insn)) == USE)
500 g->nodes[i].cuid = i;
501 g->nodes[i].successors = sbitmap_alloc (num_nodes);
502 sbitmap_zero (g->nodes[i].successors);
503 g->nodes[i].predecessors = sbitmap_alloc (num_nodes);
504 sbitmap_zero (g->nodes[i].predecessors);
505 g->nodes[i].first_note = (first_note ? first_note : insn);
506 g->nodes[i++].insn = insn;
507 first_note = NULL_RTX;
510 /* We must have found a branch in DDG. */
511 gcc_assert (g->closing_branch);
514 /* Build the data dependency graph. */
515 build_intra_loop_deps (g);
516 build_inter_loop_deps (g);
520 /* Free all the memory allocated for the DDG. */
529 for (i = 0; i < g->num_nodes; i++)
531 ddg_edge_ptr e = g->nodes[i].out;
535 ddg_edge_ptr next = e->next_out;
540 sbitmap_free (g->nodes[i].successors);
541 sbitmap_free (g->nodes[i].predecessors);
543 if (g->num_backarcs > 0)
550 print_ddg_edge (FILE *file, ddg_edge_ptr e)
566 fprintf (file, " [%d -(%c,%d,%d)-> %d] ", INSN_UID (e->src->insn),
567 dep_c, e->latency, e->distance, INSN_UID (e->dest->insn));
570 /* Print the DDG nodes with there in/out edges to the dump file. */
572 print_ddg (FILE *file, ddg_ptr g)
576 for (i = 0; i < g->num_nodes; i++)
580 fprintf (file, "Node num: %d\n", g->nodes[i].cuid);
581 print_rtl_single (file, g->nodes[i].insn);
582 fprintf (file, "OUT ARCS: ");
583 for (e = g->nodes[i].out; e; e = e->next_out)
584 print_ddg_edge (file, e);
586 fprintf (file, "\nIN ARCS: ");
587 for (e = g->nodes[i].in; e; e = e->next_in)
588 print_ddg_edge (file, e);
590 fprintf (file, "\n");
594 /* Print the given DDG in VCG format. */
596 vcg_print_ddg (FILE *file, ddg_ptr g)
600 fprintf (file, "graph: {\n");
601 for (src_cuid = 0; src_cuid < g->num_nodes; src_cuid++)
604 int src_uid = INSN_UID (g->nodes[src_cuid].insn);
606 fprintf (file, "node: {title: \"%d_%d\" info1: \"", src_cuid, src_uid);
607 print_rtl_single (file, g->nodes[src_cuid].insn);
608 fprintf (file, "\"}\n");
609 for (e = g->nodes[src_cuid].out; e; e = e->next_out)
611 int dst_uid = INSN_UID (e->dest->insn);
612 int dst_cuid = e->dest->cuid;
614 /* Give the backarcs a different color. */
616 fprintf (file, "backedge: {color: red ");
618 fprintf (file, "edge: { ");
620 fprintf (file, "sourcename: \"%d_%d\" ", src_cuid, src_uid);
621 fprintf (file, "targetname: \"%d_%d\" ", dst_cuid, dst_uid);
622 fprintf (file, "label: \"%d_%d\"}\n", e->latency, e->distance);
625 fprintf (file, "}\n");
628 /* Dump the sccs in SCCS. */
630 print_sccs (FILE *file, ddg_all_sccs_ptr sccs, ddg_ptr g)
633 sbitmap_iterator sbi;
639 fprintf (file, "\n;; Number of SCC nodes - %d\n", sccs->num_sccs);
640 for (i = 0; i < sccs->num_sccs; i++)
642 fprintf (file, "SCC number: %d\n", i);
643 EXECUTE_IF_SET_IN_SBITMAP (sccs->sccs[i]->nodes, 0, u, sbi)
645 fprintf (file, "insn num %d\n", u);
646 print_rtl_single (file, g->nodes[u].insn);
649 fprintf (file, "\n");
652 /* Create an edge and initialize it with given values. */
654 create_ddg_edge (ddg_node_ptr src, ddg_node_ptr dest,
655 dep_type t, dep_data_type dt, int l, int d)
657 ddg_edge_ptr e = (ddg_edge_ptr) xmalloc (sizeof (struct ddg_edge));
665 e->next_in = e->next_out = NULL;
670 /* Add the given edge to the in/out linked lists of the DDG nodes. */
672 add_edge_to_ddg (ddg_ptr g ATTRIBUTE_UNUSED, ddg_edge_ptr e)
674 ddg_node_ptr src = e->src;
675 ddg_node_ptr dest = e->dest;
677 /* Should have allocated the sbitmaps. */
678 gcc_assert (src->successors && dest->predecessors);
680 SET_BIT (src->successors, dest->cuid);
681 SET_BIT (dest->predecessors, src->cuid);
682 e->next_in = dest->in;
684 e->next_out = src->out;
690 /* Algorithm for computing the recurrence_length of an scc. We assume at
691 for now that cycles in the data dependence graph contain a single backarc.
692 This simplifies the algorithm, and can be generalized later. */
694 set_recurrence_length (ddg_scc_ptr scc, ddg_ptr g)
699 for (j = 0; j < scc->num_backarcs; j++)
701 ddg_edge_ptr backarc = scc->backarcs[j];
703 int distance = backarc->distance;
704 ddg_node_ptr src = backarc->dest;
705 ddg_node_ptr dest = backarc->src;
707 length = longest_simple_path (g, src->cuid, dest->cuid, scc->nodes);
710 /* fprintf (stderr, "Backarc not on simple cycle in SCC.\n"); */
713 length += backarc->latency;
714 result = MAX (result, (length / distance));
716 scc->recurrence_length = result;
719 /* Create a new SCC given the set of its nodes. Compute its recurrence_length
720 and mark edges that belong to this scc as IN_SCC. */
722 create_scc (ddg_ptr g, sbitmap nodes)
726 sbitmap_iterator sbi;
728 scc = (ddg_scc_ptr) xmalloc (sizeof (struct ddg_scc));
729 scc->backarcs = NULL;
730 scc->num_backarcs = 0;
731 scc->nodes = sbitmap_alloc (g->num_nodes);
732 sbitmap_copy (scc->nodes, nodes);
734 /* Mark the backarcs that belong to this SCC. */
735 EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, u, sbi)
738 ddg_node_ptr n = &g->nodes[u];
740 for (e = n->out; e; e = e->next_out)
741 if (TEST_BIT (nodes, e->dest->cuid))
743 e->aux.count = IN_SCC;
745 add_backarc_to_scc (scc, e);
749 set_recurrence_length (scc, g);
753 /* Cleans the memory allocation of a given SCC. */
755 free_scc (ddg_scc_ptr scc)
760 sbitmap_free (scc->nodes);
761 if (scc->num_backarcs > 0)
762 free (scc->backarcs);
767 /* Add a given edge known to be a backarc to the given DDG. */
769 add_backarc_to_ddg (ddg_ptr g, ddg_edge_ptr e)
771 int size = (g->num_backarcs + 1) * sizeof (ddg_edge_ptr);
773 add_edge_to_ddg (g, e);
774 g->backarcs = (ddg_edge_ptr *) xrealloc (g->backarcs, size);
775 g->backarcs[g->num_backarcs++] = e;
778 /* Add backarc to an SCC. */
780 add_backarc_to_scc (ddg_scc_ptr scc, ddg_edge_ptr e)
782 int size = (scc->num_backarcs + 1) * sizeof (ddg_edge_ptr);
784 scc->backarcs = (ddg_edge_ptr *) xrealloc (scc->backarcs, size);
785 scc->backarcs[scc->num_backarcs++] = e;
788 /* Add the given SCC to the DDG. */
790 add_scc_to_ddg (ddg_all_sccs_ptr g, ddg_scc_ptr scc)
792 int size = (g->num_sccs + 1) * sizeof (ddg_scc_ptr);
794 g->sccs = (ddg_scc_ptr *) xrealloc (g->sccs, size);
795 g->sccs[g->num_sccs++] = scc;
798 /* Given the instruction INSN return the node that represents it. */
800 get_node_of_insn (ddg_ptr g, rtx insn)
804 for (i = 0; i < g->num_nodes; i++)
805 if (insn == g->nodes[i].insn)
810 /* Given a set OPS of nodes in the DDG, find the set of their successors
811 which are not in OPS, and set their bits in SUCC. Bits corresponding to
812 OPS are cleared from SUCC. Leaves the other bits in SUCC unchanged. */
814 find_successors (sbitmap succ, ddg_ptr g, sbitmap ops)
817 sbitmap_iterator sbi;
819 EXECUTE_IF_SET_IN_SBITMAP (ops, 0, i, sbi)
821 const sbitmap node_succ = NODE_SUCCESSORS (&g->nodes[i]);
822 sbitmap_a_or_b (succ, succ, node_succ);
825 /* We want those that are not in ops. */
826 sbitmap_difference (succ, succ, ops);
829 /* Given a set OPS of nodes in the DDG, find the set of their predecessors
830 which are not in OPS, and set their bits in PREDS. Bits corresponding to
831 OPS are cleared from PREDS. Leaves the other bits in PREDS unchanged. */
833 find_predecessors (sbitmap preds, ddg_ptr g, sbitmap ops)
836 sbitmap_iterator sbi;
838 EXECUTE_IF_SET_IN_SBITMAP (ops, 0, i, sbi)
840 const sbitmap node_preds = NODE_PREDECESSORS (&g->nodes[i]);
841 sbitmap_a_or_b (preds, preds, node_preds);
844 /* We want those that are not in ops. */
845 sbitmap_difference (preds, preds, ops);
849 /* Compare function to be passed to qsort to order the backarcs in descending
852 compare_sccs (const void *s1, const void *s2)
854 const int rec_l1 = (*(const ddg_scc_ptr *)s1)->recurrence_length;
855 const int rec_l2 = (*(const ddg_scc_ptr *)s2)->recurrence_length;
856 return ((rec_l2 > rec_l1) - (rec_l2 < rec_l1));
860 /* Order the backarcs in descending recMII order using compare_sccs. */
862 order_sccs (ddg_all_sccs_ptr g)
864 qsort (g->sccs, g->num_sccs, sizeof (ddg_scc_ptr),
865 (int (*) (const void *, const void *)) compare_sccs);
868 #ifdef ENABLE_CHECKING
869 /* Check that every node in SCCS belongs to exactly one strongly connected
870 component and that no element of SCCS is empty. */
872 check_sccs (ddg_all_sccs_ptr sccs, int num_nodes)
875 sbitmap tmp = sbitmap_alloc (num_nodes);
878 for (i = 0; i < sccs->num_sccs; i++)
880 gcc_assert (!sbitmap_empty_p (sccs->sccs[i]->nodes));
881 /* Verify that every node in sccs is in exactly one strongly
882 connected component. */
883 gcc_assert (!sbitmap_any_common_bits (tmp, sccs->sccs[i]->nodes));
884 sbitmap_a_or_b (tmp, tmp, sccs->sccs[i]->nodes);
890 /* Perform the Strongly Connected Components decomposing algorithm on the
891 DDG and return DDG_ALL_SCCS structure that contains them. */
893 create_ddg_all_sccs (ddg_ptr g)
896 int num_nodes = g->num_nodes;
897 sbitmap from = sbitmap_alloc (num_nodes);
898 sbitmap to = sbitmap_alloc (num_nodes);
899 sbitmap scc_nodes = sbitmap_alloc (num_nodes);
900 ddg_all_sccs_ptr sccs = (ddg_all_sccs_ptr)
901 xmalloc (sizeof (struct ddg_all_sccs));
907 for (i = 0; i < g->num_backarcs; i++)
910 ddg_edge_ptr backarc = g->backarcs[i];
911 ddg_node_ptr src = backarc->src;
912 ddg_node_ptr dest = backarc->dest;
914 /* If the backarc already belongs to an SCC, continue. */
915 if (backarc->aux.count == IN_SCC)
918 sbitmap_zero (scc_nodes);
921 SET_BIT (from, dest->cuid);
922 SET_BIT (to, src->cuid);
924 if (find_nodes_on_paths (scc_nodes, g, from, to))
926 scc = create_scc (g, scc_nodes);
927 add_scc_to_ddg (sccs, scc);
933 sbitmap_free (scc_nodes);
934 #ifdef ENABLE_CHECKING
935 check_sccs (sccs, num_nodes);
940 /* Frees the memory allocated for all SCCs of the DDG, but keeps the DDG. */
942 free_ddg_all_sccs (ddg_all_sccs_ptr all_sccs)
949 for (i = 0; i < all_sccs->num_sccs; i++)
950 free_scc (all_sccs->sccs[i]);
956 /* Given FROM - a bitmap of source nodes - and TO - a bitmap of destination
957 nodes - find all nodes that lie on paths from FROM to TO (not excluding
958 nodes from FROM and TO). Return nonzero if nodes exist. */
960 find_nodes_on_paths (sbitmap result, ddg_ptr g, sbitmap from, sbitmap to)
965 int num_nodes = g->num_nodes;
966 sbitmap_iterator sbi;
968 sbitmap workset = sbitmap_alloc (num_nodes);
969 sbitmap reachable_from = sbitmap_alloc (num_nodes);
970 sbitmap reach_to = sbitmap_alloc (num_nodes);
971 sbitmap tmp = sbitmap_alloc (num_nodes);
973 sbitmap_copy (reachable_from, from);
974 sbitmap_copy (tmp, from);
980 sbitmap_copy (workset, tmp);
982 EXECUTE_IF_SET_IN_SBITMAP (workset, 0, u, sbi)
985 ddg_node_ptr u_node = &g->nodes[u];
987 for (e = u_node->out; e != (ddg_edge_ptr) 0; e = e->next_out)
989 ddg_node_ptr v_node = e->dest;
990 int v = v_node->cuid;
992 if (!TEST_BIT (reachable_from, v))
994 SET_BIT (reachable_from, v);
1002 sbitmap_copy (reach_to, to);
1003 sbitmap_copy (tmp, to);
1009 sbitmap_copy (workset, tmp);
1011 EXECUTE_IF_SET_IN_SBITMAP (workset, 0, u, sbi)
1014 ddg_node_ptr u_node = &g->nodes[u];
1016 for (e = u_node->in; e != (ddg_edge_ptr) 0; e = e->next_in)
1018 ddg_node_ptr v_node = e->src;
1019 int v = v_node->cuid;
1021 if (!TEST_BIT (reach_to, v))
1023 SET_BIT (reach_to, v);
1031 answer = sbitmap_a_and_b_cg (result, reachable_from, reach_to);
1032 sbitmap_free (workset);
1033 sbitmap_free (reachable_from);
1034 sbitmap_free (reach_to);
1040 /* Updates the counts of U_NODE's successors (that belong to NODES) to be
1041 at-least as large as the count of U_NODE plus the latency between them.
1042 Sets a bit in TMP for each successor whose count was changed (increased).
1043 Returns nonzero if any count was changed. */
1045 update_dist_to_successors (ddg_node_ptr u_node, sbitmap nodes, sbitmap tmp)
1050 for (e = u_node->out; e; e = e->next_out)
1052 ddg_node_ptr v_node = e->dest;
1053 int v = v_node->cuid;
1055 if (TEST_BIT (nodes, v)
1056 && (e->distance == 0)
1057 && (v_node->aux.count < u_node->aux.count + e->latency))
1059 v_node->aux.count = u_node->aux.count + e->latency;
1068 /* Find the length of a longest path from SRC to DEST in G,
1069 going only through NODES, and disregarding backarcs. */
1071 longest_simple_path (struct ddg * g, int src, int dest, sbitmap nodes)
1077 int num_nodes = g->num_nodes;
1078 sbitmap workset = sbitmap_alloc (num_nodes);
1079 sbitmap tmp = sbitmap_alloc (num_nodes);
1082 /* Data will hold the distance of the longest path found so far from
1083 src to each node. Initialize to -1 = less than minimum. */
1084 for (i = 0; i < g->num_nodes; i++)
1085 g->nodes[i].aux.count = -1;
1086 g->nodes[src].aux.count = 0;
1093 sbitmap_iterator sbi;
1096 sbitmap_copy (workset, tmp);
1098 EXECUTE_IF_SET_IN_SBITMAP (workset, 0, u, sbi)
1100 ddg_node_ptr u_node = &g->nodes[u];
1102 change |= update_dist_to_successors (u_node, nodes, tmp);
1105 result = g->nodes[dest].aux.count;
1106 sbitmap_free (workset);
1111 #endif /* INSN_SCHEDULING */