1 /* DDG - Data Dependence Graph implementation.
2 Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009
3 Free Software Foundation, Inc.
4 Contributed by Ayal Zaks and Mustafa Hagog <zaks,mustafa@il.ibm.com>
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
25 #include "coretypes.h"
27 #include "diagnostic-core.h"
31 #include "hard-reg-set.h"
35 #include "insn-config.h"
36 #include "insn-attr.h"
39 #include "sched-int.h"
41 #include "cfglayout.h"
48 #ifdef INSN_SCHEDULING
50 /* A flag indicating that a ddg edge belongs to an SCC or not. */
51 enum edge_flag {NOT_IN_SCC = 0, IN_SCC};
53 /* Forward declarations. */
54 static void add_backarc_to_ddg (ddg_ptr, ddg_edge_ptr);
55 static void add_backarc_to_scc (ddg_scc_ptr, ddg_edge_ptr);
56 static void add_scc_to_ddg (ddg_all_sccs_ptr, ddg_scc_ptr);
57 static void create_ddg_dep_from_intra_loop_link (ddg_ptr, ddg_node_ptr,
59 static void create_ddg_dep_no_link (ddg_ptr, ddg_node_ptr, ddg_node_ptr,
60 dep_type, dep_data_type, int);
61 static ddg_edge_ptr create_ddg_edge (ddg_node_ptr, ddg_node_ptr, dep_type,
62 dep_data_type, int, int);
63 static void add_edge_to_ddg (ddg_ptr g, ddg_edge_ptr);
65 /* Auxiliary variable for mem_read_insn_p/mem_write_insn_p. */
66 static bool mem_ref_p;
68 /* Auxiliary function for mem_read_insn_p. */
70 mark_mem_use (rtx *x, void *data ATTRIBUTE_UNUSED)
77 /* Auxiliary function for mem_read_insn_p. */
79 mark_mem_use_1 (rtx *x, void *data)
81 for_each_rtx (x, mark_mem_use, data);
84 /* Returns nonzero if INSN reads from memory. */
86 mem_read_insn_p (rtx insn)
89 note_uses (&PATTERN (insn), mark_mem_use_1, NULL);
94 mark_mem_store (rtx loc, const_rtx setter ATTRIBUTE_UNUSED, void *data ATTRIBUTE_UNUSED)
100 /* Returns nonzero if INSN writes to memory. */
102 mem_write_insn_p (rtx insn)
105 note_stores (PATTERN (insn), mark_mem_store, NULL);
109 /* Returns nonzero if X has access to memory. */
111 rtx_mem_access_p (rtx x)
124 fmt = GET_RTX_FORMAT (code);
125 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
129 if (rtx_mem_access_p (XEXP (x, i)))
132 else if (fmt[i] == 'E')
133 for (j = 0; j < XVECLEN (x, i); j++)
135 if (rtx_mem_access_p (XVECEXP (x, i, j)))
142 /* Returns nonzero if INSN reads to or writes from memory. */
144 mem_access_insn_p (rtx insn)
146 return rtx_mem_access_p (PATTERN (insn));
149 /* Computes the dependence parameters (latency, distance etc.), creates
150 a ddg_edge and adds it to the given DDG. */
152 create_ddg_dep_from_intra_loop_link (ddg_ptr g, ddg_node_ptr src_node,
153 ddg_node_ptr dest_node, dep_t link)
156 int latency, distance = 0;
157 dep_type t = TRUE_DEP;
158 dep_data_type dt = (mem_access_insn_p (src_node->insn)
159 && mem_access_insn_p (dest_node->insn) ? MEM_DEP
161 gcc_assert (src_node->cuid < dest_node->cuid);
164 /* Note: REG_DEP_ANTI applies to MEM ANTI_DEP as well!! */
165 if (DEP_TYPE (link) == REG_DEP_ANTI)
167 else if (DEP_TYPE (link) == REG_DEP_OUTPUT)
170 gcc_assert (!DEBUG_INSN_P (dest_node->insn) || t == ANTI_DEP);
171 gcc_assert (!DEBUG_INSN_P (src_node->insn) || t == ANTI_DEP);
173 /* We currently choose not to create certain anti-deps edges and
174 compensate for that by generating reg-moves based on the life-range
175 analysis. The anti-deps that will be deleted are the ones which
176 have true-deps edges in the opposite direction (in other words
177 the kernel has only one def of the relevant register). TODO:
178 support the removal of all anti-deps edges, i.e. including those
179 whose register has multiple defs in the loop. */
180 if (flag_modulo_sched_allow_regmoves && (t == ANTI_DEP && dt == REG_DEP))
184 set = single_set (dest_node->insn);
185 /* TODO: Handle registers that REG_P is not true for them, i.e.
186 subregs and special registers. */
187 if (set && REG_P (SET_DEST (set)))
189 int regno = REGNO (SET_DEST (set));
191 struct df_rd_bb_info *bb_info = DF_RD_BB_INFO (g->bb);
193 first_def = df_bb_regno_first_def_find (g->bb, regno);
194 gcc_assert (first_def);
196 if (bitmap_bit_p (&bb_info->gen, DF_REF_ID (first_def)))
201 latency = dep_cost (link);
202 e = create_ddg_edge (src_node, dest_node, t, dt, latency, distance);
203 add_edge_to_ddg (g, e);
206 /* The same as the above function, but it doesn't require a link parameter. */
208 create_ddg_dep_no_link (ddg_ptr g, ddg_node_ptr from, ddg_node_ptr to,
209 dep_type d_t, dep_data_type d_dt, int distance)
213 enum reg_note dep_kind;
214 struct _dep _dep, *dep = &_dep;
216 gcc_assert (!DEBUG_INSN_P (to->insn) || d_t == ANTI_DEP);
217 gcc_assert (!DEBUG_INSN_P (from->insn) || d_t == ANTI_DEP);
220 dep_kind = REG_DEP_ANTI;
221 else if (d_t == OUTPUT_DEP)
222 dep_kind = REG_DEP_OUTPUT;
225 gcc_assert (d_t == TRUE_DEP);
227 dep_kind = REG_DEP_TRUE;
230 init_dep (dep, from->insn, to->insn, dep_kind);
234 e = create_ddg_edge (from, to, d_t, d_dt, l, distance);
236 add_backarc_to_ddg (g, e);
238 add_edge_to_ddg (g, e);
242 /* Given a downwards exposed register def LAST_DEF (which is the last
243 definition of that register in the bb), add inter-loop true dependences
244 to all its uses in the next iteration, an output dependence to the
245 first def of the same register (possibly itself) in the next iteration
246 and anti-dependences from its uses in the current iteration to the
247 first definition in the next iteration. */
249 add_cross_iteration_register_deps (ddg_ptr g, df_ref last_def)
251 int regno = DF_REF_REGNO (last_def);
252 struct df_link *r_use;
253 int has_use_in_bb_p = false;
254 rtx def_insn = DF_REF_INSN (last_def);
255 ddg_node_ptr last_def_node = get_node_of_insn (g, def_insn);
256 ddg_node_ptr use_node;
257 #ifdef ENABLE_CHECKING
258 struct df_rd_bb_info *bb_info = DF_RD_BB_INFO (g->bb);
260 df_ref first_def = df_bb_regno_first_def_find (g->bb, regno);
262 gcc_assert (last_def_node);
263 gcc_assert (first_def);
265 #ifdef ENABLE_CHECKING
266 if (DF_REF_ID (last_def) != DF_REF_ID (first_def))
267 gcc_assert (!bitmap_bit_p (&bb_info->gen, DF_REF_ID (first_def)));
270 /* Create inter-loop true dependences and anti dependences. */
271 for (r_use = DF_REF_CHAIN (last_def); r_use != NULL; r_use = r_use->next)
273 rtx use_insn = DF_REF_INSN (r_use->ref);
275 if (BLOCK_FOR_INSN (use_insn) != g->bb)
278 /* ??? Do not handle uses with DF_REF_IN_NOTE notes. */
279 use_node = get_node_of_insn (g, use_insn);
280 gcc_assert (use_node);
281 has_use_in_bb_p = true;
282 if (use_node->cuid <= last_def_node->cuid)
284 /* Add true deps from last_def to it's uses in the next
285 iteration. Any such upwards exposed use appears before
287 create_ddg_dep_no_link (g, last_def_node, use_node,
288 DEBUG_INSN_P (use_insn) ? ANTI_DEP : TRUE_DEP,
291 else if (!DEBUG_INSN_P (use_insn))
293 /* Add anti deps from last_def's uses in the current iteration
294 to the first def in the next iteration. We do not add ANTI
295 dep when there is an intra-loop TRUE dep in the opposite
296 direction, but use regmoves to fix such disregarded ANTI
297 deps when broken. If the first_def reaches the USE then
298 there is such a dep. */
299 ddg_node_ptr first_def_node = get_node_of_insn (g,
300 DF_REF_INSN (first_def));
302 gcc_assert (first_def_node);
304 if (DF_REF_ID (last_def) != DF_REF_ID (first_def)
305 || !flag_modulo_sched_allow_regmoves)
306 create_ddg_dep_no_link (g, use_node, first_def_node, ANTI_DEP,
311 /* Create an inter-loop output dependence between LAST_DEF (which is the
312 last def in its block, being downwards exposed) and the first def in
313 its block. Avoid creating a self output dependence. Avoid creating
314 an output dependence if there is a dependence path between the two
315 defs starting with a true dependence to a use which can be in the
316 next iteration; followed by an anti dependence of that use to the
317 first def (i.e. if there is a use between the two defs.) */
318 if (!has_use_in_bb_p)
320 ddg_node_ptr dest_node;
322 if (DF_REF_ID (last_def) == DF_REF_ID (first_def))
325 dest_node = get_node_of_insn (g, DF_REF_INSN (first_def));
326 gcc_assert (dest_node);
327 create_ddg_dep_no_link (g, last_def_node, dest_node,
328 OUTPUT_DEP, REG_DEP, 1);
331 /* Build inter-loop dependencies, by looking at DF analysis backwards. */
333 build_inter_loop_deps (ddg_ptr g)
336 struct df_rd_bb_info *rd_bb_info;
339 rd_bb_info = DF_RD_BB_INFO (g->bb);
341 /* Find inter-loop register output, true and anti deps. */
342 EXECUTE_IF_SET_IN_BITMAP (&rd_bb_info->gen, 0, rd_num, bi)
344 df_ref rd = DF_DEFS_GET (rd_num);
346 add_cross_iteration_register_deps (g, rd);
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 (!insn_alias_sets_conflict_p (from->insn, to->insn))
357 /* Do not create edge if memory references have disjoint alias sets. */
360 if (mem_write_insn_p (from->insn))
362 if (mem_read_insn_p (to->insn))
363 create_ddg_dep_no_link (g, from, to,
364 DEBUG_INSN_P (to->insn)
365 ? ANTI_DEP : TRUE_DEP, MEM_DEP, 1);
366 else if (from->cuid != to->cuid)
367 create_ddg_dep_no_link (g, from, to,
368 DEBUG_INSN_P (to->insn)
369 ? ANTI_DEP : OUTPUT_DEP, MEM_DEP, 1);
373 if (mem_read_insn_p (to->insn))
375 else if (from->cuid != to->cuid)
377 create_ddg_dep_no_link (g, from, to, ANTI_DEP, MEM_DEP, 1);
378 if (DEBUG_INSN_P (from->insn) || DEBUG_INSN_P (to->insn))
379 create_ddg_dep_no_link (g, to, from, ANTI_DEP, MEM_DEP, 1);
381 create_ddg_dep_no_link (g, to, from, TRUE_DEP, MEM_DEP, 1);
387 /* Perform intra-block Data Dependency analysis and connect the nodes in
388 the DDG. We assume the loop has a single basic block. */
390 build_intra_loop_deps (ddg_ptr g)
393 /* Hold the dependency analysis state during dependency calculations. */
394 struct deps_desc tmp_deps;
397 /* Build the dependence information, using the sched_analyze function. */
399 init_deps (&tmp_deps, false);
401 /* Do the intra-block data dependence analysis for the given block. */
402 get_ebb_head_tail (g->bb, g->bb, &head, &tail);
403 sched_analyze (&tmp_deps, head, tail);
405 /* Build intra-loop data dependencies using the scheduler dependency
407 for (i = 0; i < g->num_nodes; i++)
409 ddg_node_ptr dest_node = &g->nodes[i];
410 sd_iterator_def sd_it;
413 if (! INSN_P (dest_node->insn))
416 FOR_EACH_DEP (dest_node->insn, SD_LIST_BACK, sd_it, dep)
418 ddg_node_ptr src_node = get_node_of_insn (g, DEP_PRO (dep));
423 create_ddg_dep_from_intra_loop_link (g, src_node, dest_node, dep);
426 /* If this insn modifies memory, add an edge to all insns that access
428 if (mem_access_insn_p (dest_node->insn))
432 for (j = 0; j <= i; j++)
434 ddg_node_ptr j_node = &g->nodes[j];
435 if (DEBUG_INSN_P (j_node->insn))
437 if (mem_access_insn_p (j_node->insn))
438 /* Don't bother calculating inter-loop dep if an intra-loop dep
440 if (! TEST_BIT (dest_node->successors, j))
441 add_inter_loop_mem_dep (g, dest_node, j_node);
446 /* Free the INSN_LISTs. */
447 finish_deps_global ();
448 free_deps (&tmp_deps);
450 /* Free dependencies. */
451 sched_free_deps (head, tail, false);
455 /* Given a basic block, create its DDG and return a pointer to a variable
456 of ddg type that represents it.
457 Initialize the ddg structure fields to the appropriate values. */
459 create_ddg (basic_block bb, int closing_branch_deps)
462 rtx insn, first_note;
466 g = (ddg_ptr) xcalloc (1, sizeof (struct ddg));
469 g->closing_branch_deps = closing_branch_deps;
471 /* Count the number of insns in the BB. */
472 for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb));
473 insn = NEXT_INSN (insn))
475 if (! INSN_P (insn) || GET_CODE (PATTERN (insn)) == USE)
478 if (DEBUG_INSN_P (insn))
482 if (mem_read_insn_p (insn))
484 if (mem_write_insn_p (insn))
490 /* There is nothing to do for this BB. */
497 /* Allocate the nodes array, and initialize the nodes. */
498 g->num_nodes = num_nodes;
499 g->nodes = (ddg_node_ptr) xcalloc (num_nodes, sizeof (struct ddg_node));
500 g->closing_branch = NULL;
502 first_note = NULL_RTX;
503 for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb));
504 insn = NEXT_INSN (insn))
508 if (! first_note && NOTE_P (insn)
509 && NOTE_KIND (insn) != NOTE_INSN_BASIC_BLOCK)
515 gcc_assert (!g->closing_branch);
516 g->closing_branch = &g->nodes[i];
518 else if (GET_CODE (PATTERN (insn)) == USE)
525 g->nodes[i].cuid = i;
526 g->nodes[i].successors = sbitmap_alloc (num_nodes);
527 sbitmap_zero (g->nodes[i].successors);
528 g->nodes[i].predecessors = sbitmap_alloc (num_nodes);
529 sbitmap_zero (g->nodes[i].predecessors);
530 g->nodes[i].first_note = (first_note ? first_note : insn);
531 g->nodes[i++].insn = insn;
532 first_note = NULL_RTX;
535 /* We must have found a branch in DDG. */
536 gcc_assert (g->closing_branch);
539 /* Build the data dependency graph. */
540 build_intra_loop_deps (g);
541 build_inter_loop_deps (g);
545 /* Free all the memory allocated for the DDG. */
554 for (i = 0; i < g->num_nodes; i++)
556 ddg_edge_ptr e = g->nodes[i].out;
560 ddg_edge_ptr next = e->next_out;
565 sbitmap_free (g->nodes[i].successors);
566 sbitmap_free (g->nodes[i].predecessors);
568 if (g->num_backarcs > 0)
575 print_ddg_edge (FILE *file, ddg_edge_ptr e)
591 fprintf (file, " [%d -(%c,%d,%d)-> %d] ", INSN_UID (e->src->insn),
592 dep_c, e->latency, e->distance, INSN_UID (e->dest->insn));
595 /* Print the DDG nodes with there in/out edges to the dump file. */
597 print_ddg (FILE *file, ddg_ptr g)
601 for (i = 0; i < g->num_nodes; i++)
605 fprintf (file, "Node num: %d\n", g->nodes[i].cuid);
606 print_rtl_single (file, g->nodes[i].insn);
607 fprintf (file, "OUT ARCS: ");
608 for (e = g->nodes[i].out; e; e = e->next_out)
609 print_ddg_edge (file, e);
611 fprintf (file, "\nIN ARCS: ");
612 for (e = g->nodes[i].in; e; e = e->next_in)
613 print_ddg_edge (file, e);
615 fprintf (file, "\n");
619 /* Print the given DDG in VCG format. */
621 vcg_print_ddg (FILE *file, ddg_ptr g)
625 fprintf (file, "graph: {\n");
626 for (src_cuid = 0; src_cuid < g->num_nodes; src_cuid++)
629 int src_uid = INSN_UID (g->nodes[src_cuid].insn);
631 fprintf (file, "node: {title: \"%d_%d\" info1: \"", src_cuid, src_uid);
632 print_rtl_single (file, g->nodes[src_cuid].insn);
633 fprintf (file, "\"}\n");
634 for (e = g->nodes[src_cuid].out; e; e = e->next_out)
636 int dst_uid = INSN_UID (e->dest->insn);
637 int dst_cuid = e->dest->cuid;
639 /* Give the backarcs a different color. */
641 fprintf (file, "backedge: {color: red ");
643 fprintf (file, "edge: { ");
645 fprintf (file, "sourcename: \"%d_%d\" ", src_cuid, src_uid);
646 fprintf (file, "targetname: \"%d_%d\" ", dst_cuid, dst_uid);
647 fprintf (file, "label: \"%d_%d\"}\n", e->latency, e->distance);
650 fprintf (file, "}\n");
653 /* Dump the sccs in SCCS. */
655 print_sccs (FILE *file, ddg_all_sccs_ptr sccs, ddg_ptr g)
658 sbitmap_iterator sbi;
664 fprintf (file, "\n;; Number of SCC nodes - %d\n", sccs->num_sccs);
665 for (i = 0; i < sccs->num_sccs; i++)
667 fprintf (file, "SCC number: %d\n", i);
668 EXECUTE_IF_SET_IN_SBITMAP (sccs->sccs[i]->nodes, 0, u, sbi)
670 fprintf (file, "insn num %d\n", u);
671 print_rtl_single (file, g->nodes[u].insn);
674 fprintf (file, "\n");
677 /* Create an edge and initialize it with given values. */
679 create_ddg_edge (ddg_node_ptr src, ddg_node_ptr dest,
680 dep_type t, dep_data_type dt, int l, int d)
682 ddg_edge_ptr e = (ddg_edge_ptr) xmalloc (sizeof (struct ddg_edge));
690 e->next_in = e->next_out = NULL;
695 /* Add the given edge to the in/out linked lists of the DDG nodes. */
697 add_edge_to_ddg (ddg_ptr g ATTRIBUTE_UNUSED, ddg_edge_ptr e)
699 ddg_node_ptr src = e->src;
700 ddg_node_ptr dest = e->dest;
702 /* Should have allocated the sbitmaps. */
703 gcc_assert (src->successors && dest->predecessors);
705 SET_BIT (src->successors, dest->cuid);
706 SET_BIT (dest->predecessors, src->cuid);
707 e->next_in = dest->in;
709 e->next_out = src->out;
715 /* Algorithm for computing the recurrence_length of an scc. We assume at
716 for now that cycles in the data dependence graph contain a single backarc.
717 This simplifies the algorithm, and can be generalized later. */
719 set_recurrence_length (ddg_scc_ptr scc, ddg_ptr g)
724 for (j = 0; j < scc->num_backarcs; j++)
726 ddg_edge_ptr backarc = scc->backarcs[j];
728 int distance = backarc->distance;
729 ddg_node_ptr src = backarc->dest;
730 ddg_node_ptr dest = backarc->src;
732 length = longest_simple_path (g, src->cuid, dest->cuid, scc->nodes);
735 /* fprintf (stderr, "Backarc not on simple cycle in SCC.\n"); */
738 length += backarc->latency;
739 result = MAX (result, (length / distance));
741 scc->recurrence_length = result;
744 /* Create a new SCC given the set of its nodes. Compute its recurrence_length
745 and mark edges that belong to this scc as IN_SCC. */
747 create_scc (ddg_ptr g, sbitmap nodes)
751 sbitmap_iterator sbi;
753 scc = (ddg_scc_ptr) xmalloc (sizeof (struct ddg_scc));
754 scc->backarcs = NULL;
755 scc->num_backarcs = 0;
756 scc->nodes = sbitmap_alloc (g->num_nodes);
757 sbitmap_copy (scc->nodes, nodes);
759 /* Mark the backarcs that belong to this SCC. */
760 EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, u, sbi)
763 ddg_node_ptr n = &g->nodes[u];
765 for (e = n->out; e; e = e->next_out)
766 if (TEST_BIT (nodes, e->dest->cuid))
768 e->aux.count = IN_SCC;
770 add_backarc_to_scc (scc, e);
774 set_recurrence_length (scc, g);
778 /* Cleans the memory allocation of a given SCC. */
780 free_scc (ddg_scc_ptr scc)
785 sbitmap_free (scc->nodes);
786 if (scc->num_backarcs > 0)
787 free (scc->backarcs);
792 /* Add a given edge known to be a backarc to the given DDG. */
794 add_backarc_to_ddg (ddg_ptr g, ddg_edge_ptr e)
796 int size = (g->num_backarcs + 1) * sizeof (ddg_edge_ptr);
798 add_edge_to_ddg (g, e);
799 g->backarcs = (ddg_edge_ptr *) xrealloc (g->backarcs, size);
800 g->backarcs[g->num_backarcs++] = e;
803 /* Add backarc to an SCC. */
805 add_backarc_to_scc (ddg_scc_ptr scc, ddg_edge_ptr e)
807 int size = (scc->num_backarcs + 1) * sizeof (ddg_edge_ptr);
809 scc->backarcs = (ddg_edge_ptr *) xrealloc (scc->backarcs, size);
810 scc->backarcs[scc->num_backarcs++] = e;
813 /* Add the given SCC to the DDG. */
815 add_scc_to_ddg (ddg_all_sccs_ptr g, ddg_scc_ptr scc)
817 int size = (g->num_sccs + 1) * sizeof (ddg_scc_ptr);
819 g->sccs = (ddg_scc_ptr *) xrealloc (g->sccs, size);
820 g->sccs[g->num_sccs++] = scc;
823 /* Given the instruction INSN return the node that represents it. */
825 get_node_of_insn (ddg_ptr g, rtx insn)
829 for (i = 0; i < g->num_nodes; i++)
830 if (insn == g->nodes[i].insn)
835 /* Given a set OPS of nodes in the DDG, find the set of their successors
836 which are not in OPS, and set their bits in SUCC. Bits corresponding to
837 OPS are cleared from SUCC. Leaves the other bits in SUCC unchanged. */
839 find_successors (sbitmap succ, ddg_ptr g, sbitmap ops)
842 sbitmap_iterator sbi;
844 EXECUTE_IF_SET_IN_SBITMAP (ops, 0, i, sbi)
846 const sbitmap node_succ = NODE_SUCCESSORS (&g->nodes[i]);
847 sbitmap_a_or_b (succ, succ, node_succ);
850 /* We want those that are not in ops. */
851 sbitmap_difference (succ, succ, ops);
854 /* Given a set OPS of nodes in the DDG, find the set of their predecessors
855 which are not in OPS, and set their bits in PREDS. Bits corresponding to
856 OPS are cleared from PREDS. Leaves the other bits in PREDS unchanged. */
858 find_predecessors (sbitmap preds, ddg_ptr g, sbitmap ops)
861 sbitmap_iterator sbi;
863 EXECUTE_IF_SET_IN_SBITMAP (ops, 0, i, sbi)
865 const sbitmap node_preds = NODE_PREDECESSORS (&g->nodes[i]);
866 sbitmap_a_or_b (preds, preds, node_preds);
869 /* We want those that are not in ops. */
870 sbitmap_difference (preds, preds, ops);
874 /* Compare function to be passed to qsort to order the backarcs in descending
877 compare_sccs (const void *s1, const void *s2)
879 const int rec_l1 = (*(const ddg_scc_ptr *)s1)->recurrence_length;
880 const int rec_l2 = (*(const ddg_scc_ptr *)s2)->recurrence_length;
881 return ((rec_l2 > rec_l1) - (rec_l2 < rec_l1));
885 /* Order the backarcs in descending recMII order using compare_sccs. */
887 order_sccs (ddg_all_sccs_ptr g)
889 qsort (g->sccs, g->num_sccs, sizeof (ddg_scc_ptr),
890 (int (*) (const void *, const void *)) compare_sccs);
893 #ifdef ENABLE_CHECKING
894 /* Check that every node in SCCS belongs to exactly one strongly connected
895 component and that no element of SCCS is empty. */
897 check_sccs (ddg_all_sccs_ptr sccs, int num_nodes)
900 sbitmap tmp = sbitmap_alloc (num_nodes);
903 for (i = 0; i < sccs->num_sccs; i++)
905 gcc_assert (!sbitmap_empty_p (sccs->sccs[i]->nodes));
906 /* Verify that every node in sccs is in exactly one strongly
907 connected component. */
908 gcc_assert (!sbitmap_any_common_bits (tmp, sccs->sccs[i]->nodes));
909 sbitmap_a_or_b (tmp, tmp, sccs->sccs[i]->nodes);
915 /* Perform the Strongly Connected Components decomposing algorithm on the
916 DDG and return DDG_ALL_SCCS structure that contains them. */
918 create_ddg_all_sccs (ddg_ptr g)
921 int num_nodes = g->num_nodes;
922 sbitmap from = sbitmap_alloc (num_nodes);
923 sbitmap to = sbitmap_alloc (num_nodes);
924 sbitmap scc_nodes = sbitmap_alloc (num_nodes);
925 ddg_all_sccs_ptr sccs = (ddg_all_sccs_ptr)
926 xmalloc (sizeof (struct ddg_all_sccs));
932 for (i = 0; i < g->num_backarcs; i++)
935 ddg_edge_ptr backarc = g->backarcs[i];
936 ddg_node_ptr src = backarc->src;
937 ddg_node_ptr dest = backarc->dest;
939 /* If the backarc already belongs to an SCC, continue. */
940 if (backarc->aux.count == IN_SCC)
943 sbitmap_zero (scc_nodes);
946 SET_BIT (from, dest->cuid);
947 SET_BIT (to, src->cuid);
949 if (find_nodes_on_paths (scc_nodes, g, from, to))
951 scc = create_scc (g, scc_nodes);
952 add_scc_to_ddg (sccs, scc);
958 sbitmap_free (scc_nodes);
959 #ifdef ENABLE_CHECKING
960 check_sccs (sccs, num_nodes);
965 /* Frees the memory allocated for all SCCs of the DDG, but keeps the DDG. */
967 free_ddg_all_sccs (ddg_all_sccs_ptr all_sccs)
974 for (i = 0; i < all_sccs->num_sccs; i++)
975 free_scc (all_sccs->sccs[i]);
981 /* Given FROM - a bitmap of source nodes - and TO - a bitmap of destination
982 nodes - find all nodes that lie on paths from FROM to TO (not excluding
983 nodes from FROM and TO). Return nonzero if nodes exist. */
985 find_nodes_on_paths (sbitmap result, ddg_ptr g, sbitmap from, sbitmap to)
990 int num_nodes = g->num_nodes;
991 sbitmap_iterator sbi;
993 sbitmap workset = sbitmap_alloc (num_nodes);
994 sbitmap reachable_from = sbitmap_alloc (num_nodes);
995 sbitmap reach_to = sbitmap_alloc (num_nodes);
996 sbitmap tmp = sbitmap_alloc (num_nodes);
998 sbitmap_copy (reachable_from, from);
999 sbitmap_copy (tmp, from);
1005 sbitmap_copy (workset, tmp);
1007 EXECUTE_IF_SET_IN_SBITMAP (workset, 0, u, sbi)
1010 ddg_node_ptr u_node = &g->nodes[u];
1012 for (e = u_node->out; e != (ddg_edge_ptr) 0; e = e->next_out)
1014 ddg_node_ptr v_node = e->dest;
1015 int v = v_node->cuid;
1017 if (!TEST_BIT (reachable_from, v))
1019 SET_BIT (reachable_from, v);
1027 sbitmap_copy (reach_to, to);
1028 sbitmap_copy (tmp, to);
1034 sbitmap_copy (workset, tmp);
1036 EXECUTE_IF_SET_IN_SBITMAP (workset, 0, u, sbi)
1039 ddg_node_ptr u_node = &g->nodes[u];
1041 for (e = u_node->in; e != (ddg_edge_ptr) 0; e = e->next_in)
1043 ddg_node_ptr v_node = e->src;
1044 int v = v_node->cuid;
1046 if (!TEST_BIT (reach_to, v))
1048 SET_BIT (reach_to, v);
1056 answer = sbitmap_a_and_b_cg (result, reachable_from, reach_to);
1057 sbitmap_free (workset);
1058 sbitmap_free (reachable_from);
1059 sbitmap_free (reach_to);
1065 /* Updates the counts of U_NODE's successors (that belong to NODES) to be
1066 at-least as large as the count of U_NODE plus the latency between them.
1067 Sets a bit in TMP for each successor whose count was changed (increased).
1068 Returns nonzero if any count was changed. */
1070 update_dist_to_successors (ddg_node_ptr u_node, sbitmap nodes, sbitmap tmp)
1075 for (e = u_node->out; e; e = e->next_out)
1077 ddg_node_ptr v_node = e->dest;
1078 int v = v_node->cuid;
1080 if (TEST_BIT (nodes, v)
1081 && (e->distance == 0)
1082 && (v_node->aux.count < u_node->aux.count + e->latency))
1084 v_node->aux.count = u_node->aux.count + e->latency;
1093 /* Find the length of a longest path from SRC to DEST in G,
1094 going only through NODES, and disregarding backarcs. */
1096 longest_simple_path (struct ddg * g, int src, int dest, sbitmap nodes)
1102 int num_nodes = g->num_nodes;
1103 sbitmap workset = sbitmap_alloc (num_nodes);
1104 sbitmap tmp = sbitmap_alloc (num_nodes);
1107 /* Data will hold the distance of the longest path found so far from
1108 src to each node. Initialize to -1 = less than minimum. */
1109 for (i = 0; i < g->num_nodes; i++)
1110 g->nodes[i].aux.count = -1;
1111 g->nodes[src].aux.count = 0;
1118 sbitmap_iterator sbi;
1121 sbitmap_copy (workset, tmp);
1123 EXECUTE_IF_SET_IN_SBITMAP (workset, 0, u, sbi)
1125 ddg_node_ptr u_node = &g->nodes[u];
1127 change |= update_dist_to_successors (u_node, nodes, tmp);
1130 result = g->nodes[dest].aux.count;
1131 sbitmap_free (workset);
1136 #endif /* INSN_SCHEDULING */