1 /* DDG - Data Dependence Graph implementation.
2 Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010
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"
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 gcc_assert (!DEBUG_INSN_P (dest_node->insn) || t == ANTI_DEP);
170 gcc_assert (!DEBUG_INSN_P (src_node->insn) || t == ANTI_DEP);
172 /* We currently choose not to create certain anti-deps edges and
173 compensate for that by generating reg-moves based on the life-range
174 analysis. The anti-deps that will be deleted are the ones which
175 have true-deps edges in the opposite direction (in other words
176 the kernel has only one def of the relevant register). TODO:
177 support the removal of all anti-deps edges, i.e. including those
178 whose register has multiple defs in the loop. */
179 if (flag_modulo_sched_allow_regmoves && (t == ANTI_DEP && dt == REG_DEP))
183 set = single_set (dest_node->insn);
184 /* TODO: Handle registers that REG_P is not true for them, i.e.
185 subregs and special registers. */
186 if (set && REG_P (SET_DEST (set)))
188 int regno = REGNO (SET_DEST (set));
190 struct df_rd_bb_info *bb_info = DF_RD_BB_INFO (g->bb);
192 first_def = df_bb_regno_first_def_find (g->bb, regno);
193 gcc_assert (first_def);
195 if (bitmap_bit_p (&bb_info->gen, DF_REF_ID (first_def)))
200 latency = dep_cost (link);
201 e = create_ddg_edge (src_node, dest_node, t, dt, latency, distance);
202 add_edge_to_ddg (g, e);
205 /* The same as the above function, but it doesn't require a link parameter. */
207 create_ddg_dep_no_link (ddg_ptr g, ddg_node_ptr from, ddg_node_ptr to,
208 dep_type d_t, dep_data_type d_dt, int distance)
212 enum reg_note dep_kind;
213 struct _dep _dep, *dep = &_dep;
215 gcc_assert (!DEBUG_INSN_P (to->insn) || d_t == ANTI_DEP);
216 gcc_assert (!DEBUG_INSN_P (from->insn) || d_t == ANTI_DEP);
219 dep_kind = REG_DEP_ANTI;
220 else if (d_t == OUTPUT_DEP)
221 dep_kind = REG_DEP_OUTPUT;
224 gcc_assert (d_t == TRUE_DEP);
226 dep_kind = REG_DEP_TRUE;
229 init_dep (dep, from->insn, to->insn, dep_kind);
233 e = create_ddg_edge (from, to, d_t, d_dt, l, distance);
235 add_backarc_to_ddg (g, e);
237 add_edge_to_ddg (g, e);
241 /* Given a downwards exposed register def LAST_DEF (which is the last
242 definition of that register in the bb), add inter-loop true dependences
243 to all its uses in the next iteration, an output dependence to the
244 first def of the same register (possibly itself) in the next iteration
245 and anti-dependences from its uses in the current iteration to the
246 first definition in the next iteration. */
248 add_cross_iteration_register_deps (ddg_ptr g, df_ref last_def)
250 int regno = DF_REF_REGNO (last_def);
251 struct df_link *r_use;
252 int has_use_in_bb_p = false;
253 rtx def_insn = DF_REF_INSN (last_def);
254 ddg_node_ptr last_def_node = get_node_of_insn (g, def_insn);
255 ddg_node_ptr use_node;
256 #ifdef ENABLE_CHECKING
257 struct df_rd_bb_info *bb_info = DF_RD_BB_INFO (g->bb);
259 df_ref first_def = df_bb_regno_first_def_find (g->bb, regno);
261 gcc_assert (last_def_node);
262 gcc_assert (first_def);
264 #ifdef ENABLE_CHECKING
265 if (DF_REF_ID (last_def) != DF_REF_ID (first_def))
266 gcc_assert (!bitmap_bit_p (&bb_info->gen,
267 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 /* Always create the edge if the use node is a branch in
305 order to prevent the creation of reg-moves. */
306 if (DF_REF_ID (last_def) != DF_REF_ID (first_def)
307 || !flag_modulo_sched_allow_regmoves
308 || JUMP_P (use_node->insn))
309 create_ddg_dep_no_link (g, use_node, first_def_node, ANTI_DEP,
314 /* Create an inter-loop output dependence between LAST_DEF (which is the
315 last def in its block, being downwards exposed) and the first def in
316 its block. Avoid creating a self output dependence. Avoid creating
317 an output dependence if there is a dependence path between the two
318 defs starting with a true dependence to a use which can be in the
319 next iteration; followed by an anti dependence of that use to the
320 first def (i.e. if there is a use between the two defs.) */
321 if (!has_use_in_bb_p)
323 ddg_node_ptr dest_node;
325 if (DF_REF_ID (last_def) == DF_REF_ID (first_def))
328 dest_node = get_node_of_insn (g, DF_REF_INSN (first_def));
329 gcc_assert (dest_node);
330 create_ddg_dep_no_link (g, last_def_node, dest_node,
331 OUTPUT_DEP, REG_DEP, 1);
334 /* Build inter-loop dependencies, by looking at DF analysis backwards. */
336 build_inter_loop_deps (ddg_ptr g)
339 struct df_rd_bb_info *rd_bb_info;
342 rd_bb_info = DF_RD_BB_INFO (g->bb);
344 /* Find inter-loop register output, true and anti deps. */
345 EXECUTE_IF_SET_IN_BITMAP (&rd_bb_info->gen, 0, rd_num, bi)
347 df_ref rd = DF_DEFS_GET (rd_num);
349 add_cross_iteration_register_deps (g, rd);
355 walk_mems_2 (rtx *x, rtx mem)
359 if (may_alias_p (*x, mem))
368 walk_mems_1 (rtx *x, rtx *pat)
372 /* Visit all MEMs in *PAT and check indepedence. */
373 if (for_each_rtx (pat, (rtx_function) walk_mems_2, *x))
374 /* Indicate that dependence was determined and stop traversal. */
382 /* Return 1 if two specified instructions have mem expr with conflict alias sets*/
384 insns_may_alias_p (rtx insn1, rtx insn2)
386 /* For each pair of MEMs in INSN1 and INSN2 check their independence. */
387 return for_each_rtx (&PATTERN (insn1), (rtx_function) walk_mems_1,
391 /* Given two nodes, analyze their RTL insns and add intra-loop mem deps
394 add_intra_loop_mem_dep (ddg_ptr g, ddg_node_ptr from, ddg_node_ptr to)
397 if ((from->cuid == to->cuid)
398 || !insns_may_alias_p (from->insn, to->insn))
399 /* Do not create edge if memory references have disjoint alias sets
400 or 'to' and 'from' are the same instruction. */
403 if (mem_write_insn_p (from->insn))
405 if (mem_read_insn_p (to->insn))
406 create_ddg_dep_no_link (g, from, to,
407 DEBUG_INSN_P (to->insn)
408 ? ANTI_DEP : TRUE_DEP, MEM_DEP, 0);
410 create_ddg_dep_no_link (g, from, to,
411 DEBUG_INSN_P (to->insn)
412 ? ANTI_DEP : OUTPUT_DEP, MEM_DEP, 0);
414 else if (!mem_read_insn_p (to->insn))
415 create_ddg_dep_no_link (g, from, to, ANTI_DEP, MEM_DEP, 0);
418 /* Given two nodes, analyze their RTL insns and add inter-loop mem deps
421 add_inter_loop_mem_dep (ddg_ptr g, ddg_node_ptr from, ddg_node_ptr to)
423 if (!insns_may_alias_p (from->insn, to->insn))
424 /* Do not create edge if memory references have disjoint alias sets. */
427 if (mem_write_insn_p (from->insn))
429 if (mem_read_insn_p (to->insn))
430 create_ddg_dep_no_link (g, from, to,
431 DEBUG_INSN_P (to->insn)
432 ? ANTI_DEP : TRUE_DEP, MEM_DEP, 1);
433 else if (from->cuid != to->cuid)
434 create_ddg_dep_no_link (g, from, to,
435 DEBUG_INSN_P (to->insn)
436 ? ANTI_DEP : OUTPUT_DEP, MEM_DEP, 1);
440 if (mem_read_insn_p (to->insn))
442 else if (from->cuid != to->cuid)
444 create_ddg_dep_no_link (g, from, to, ANTI_DEP, MEM_DEP, 1);
445 if (DEBUG_INSN_P (from->insn) || DEBUG_INSN_P (to->insn))
446 create_ddg_dep_no_link (g, to, from, ANTI_DEP, MEM_DEP, 1);
448 create_ddg_dep_no_link (g, to, from, TRUE_DEP, MEM_DEP, 1);
454 /* Perform intra-block Data Dependency analysis and connect the nodes in
455 the DDG. We assume the loop has a single basic block. */
457 build_intra_loop_deps (ddg_ptr g)
460 /* Hold the dependency analysis state during dependency calculations. */
461 struct deps_desc tmp_deps;
464 /* Build the dependence information, using the sched_analyze function. */
466 init_deps (&tmp_deps, false);
468 /* Do the intra-block data dependence analysis for the given block. */
469 get_ebb_head_tail (g->bb, g->bb, &head, &tail);
470 sched_analyze (&tmp_deps, head, tail);
472 /* Build intra-loop data dependencies using the scheduler dependency
474 for (i = 0; i < g->num_nodes; i++)
476 ddg_node_ptr dest_node = &g->nodes[i];
477 sd_iterator_def sd_it;
480 if (! INSN_P (dest_node->insn))
483 FOR_EACH_DEP (dest_node->insn, SD_LIST_BACK, sd_it, dep)
485 ddg_node_ptr src_node = get_node_of_insn (g, DEP_PRO (dep));
490 create_ddg_dep_from_intra_loop_link (g, src_node, dest_node, dep);
493 /* If this insn modifies memory, add an edge to all insns that access
495 if (mem_access_insn_p (dest_node->insn))
499 for (j = 0; j <= i; j++)
501 ddg_node_ptr j_node = &g->nodes[j];
502 if (DEBUG_INSN_P (j_node->insn))
504 if (mem_access_insn_p (j_node->insn))
506 /* Don't bother calculating inter-loop dep if an intra-loop dep
508 if (! TEST_BIT (dest_node->successors, j))
509 add_inter_loop_mem_dep (g, dest_node, j_node);
510 /* If -fmodulo-sched-allow-regmoves
511 is set certain anti-dep edges are not created.
512 It might be that these anti-dep edges are on the
513 path from one memory instruction to another such that
514 removing these edges could cause a violation of the
515 memory dependencies. Thus we add intra edges between
516 every two memory instructions in this case. */
517 if (flag_modulo_sched_allow_regmoves
518 && !TEST_BIT (dest_node->predecessors, j))
519 add_intra_loop_mem_dep (g, j_node, dest_node);
525 /* Free the INSN_LISTs. */
526 finish_deps_global ();
527 free_deps (&tmp_deps);
529 /* Free dependencies. */
530 sched_free_deps (head, tail, false);
534 /* Given a basic block, create its DDG and return a pointer to a variable
535 of ddg type that represents it.
536 Initialize the ddg structure fields to the appropriate values. */
538 create_ddg (basic_block bb, int closing_branch_deps)
541 rtx insn, first_note;
545 g = (ddg_ptr) xcalloc (1, sizeof (struct ddg));
548 g->closing_branch_deps = closing_branch_deps;
550 /* Count the number of insns in the BB. */
551 for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb));
552 insn = NEXT_INSN (insn))
554 if (! INSN_P (insn) || GET_CODE (PATTERN (insn)) == USE)
557 if (DEBUG_INSN_P (insn))
561 if (mem_read_insn_p (insn))
563 if (mem_write_insn_p (insn))
569 /* There is nothing to do for this BB. */
570 if ((num_nodes - g->num_debug) <= 1)
576 /* Allocate the nodes array, and initialize the nodes. */
577 g->num_nodes = num_nodes;
578 g->nodes = (ddg_node_ptr) xcalloc (num_nodes, sizeof (struct ddg_node));
579 g->closing_branch = NULL;
581 first_note = NULL_RTX;
582 for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb));
583 insn = NEXT_INSN (insn))
587 if (! first_note && NOTE_P (insn)
588 && NOTE_KIND (insn) != NOTE_INSN_BASIC_BLOCK)
594 gcc_assert (!g->closing_branch);
595 g->closing_branch = &g->nodes[i];
597 else if (GET_CODE (PATTERN (insn)) == USE)
604 g->nodes[i].cuid = i;
605 g->nodes[i].successors = sbitmap_alloc (num_nodes);
606 sbitmap_zero (g->nodes[i].successors);
607 g->nodes[i].predecessors = sbitmap_alloc (num_nodes);
608 sbitmap_zero (g->nodes[i].predecessors);
609 g->nodes[i].first_note = (first_note ? first_note : insn);
610 g->nodes[i++].insn = insn;
611 first_note = NULL_RTX;
614 /* We must have found a branch in DDG. */
615 gcc_assert (g->closing_branch);
618 /* Build the data dependency graph. */
619 build_intra_loop_deps (g);
620 build_inter_loop_deps (g);
624 /* Free all the memory allocated for the DDG. */
633 for (i = 0; i < g->num_nodes; i++)
635 ddg_edge_ptr e = g->nodes[i].out;
639 ddg_edge_ptr next = e->next_out;
644 sbitmap_free (g->nodes[i].successors);
645 sbitmap_free (g->nodes[i].predecessors);
647 if (g->num_backarcs > 0)
654 print_ddg_edge (FILE *file, ddg_edge_ptr e)
670 fprintf (file, " [%d -(%c,%d,%d)-> %d] ", INSN_UID (e->src->insn),
671 dep_c, e->latency, e->distance, INSN_UID (e->dest->insn));
674 /* Print the DDG nodes with there in/out edges to the dump file. */
676 print_ddg (FILE *file, ddg_ptr g)
680 for (i = 0; i < g->num_nodes; i++)
684 fprintf (file, "Node num: %d\n", g->nodes[i].cuid);
685 print_rtl_single (file, g->nodes[i].insn);
686 fprintf (file, "OUT ARCS: ");
687 for (e = g->nodes[i].out; e; e = e->next_out)
688 print_ddg_edge (file, e);
690 fprintf (file, "\nIN ARCS: ");
691 for (e = g->nodes[i].in; e; e = e->next_in)
692 print_ddg_edge (file, e);
694 fprintf (file, "\n");
698 /* Print the given DDG in VCG format. */
700 vcg_print_ddg (FILE *file, ddg_ptr g)
704 fprintf (file, "graph: {\n");
705 for (src_cuid = 0; src_cuid < g->num_nodes; src_cuid++)
708 int src_uid = INSN_UID (g->nodes[src_cuid].insn);
710 fprintf (file, "node: {title: \"%d_%d\" info1: \"", src_cuid, src_uid);
711 print_rtl_single (file, g->nodes[src_cuid].insn);
712 fprintf (file, "\"}\n");
713 for (e = g->nodes[src_cuid].out; e; e = e->next_out)
715 int dst_uid = INSN_UID (e->dest->insn);
716 int dst_cuid = e->dest->cuid;
718 /* Give the backarcs a different color. */
720 fprintf (file, "backedge: {color: red ");
722 fprintf (file, "edge: { ");
724 fprintf (file, "sourcename: \"%d_%d\" ", src_cuid, src_uid);
725 fprintf (file, "targetname: \"%d_%d\" ", dst_cuid, dst_uid);
726 fprintf (file, "label: \"%d_%d\"}\n", e->latency, e->distance);
729 fprintf (file, "}\n");
732 /* Dump the sccs in SCCS. */
734 print_sccs (FILE *file, ddg_all_sccs_ptr sccs, ddg_ptr g)
737 sbitmap_iterator sbi;
743 fprintf (file, "\n;; Number of SCC nodes - %d\n", sccs->num_sccs);
744 for (i = 0; i < sccs->num_sccs; i++)
746 fprintf (file, "SCC number: %d\n", i);
747 EXECUTE_IF_SET_IN_SBITMAP (sccs->sccs[i]->nodes, 0, u, sbi)
749 fprintf (file, "insn num %d\n", u);
750 print_rtl_single (file, g->nodes[u].insn);
753 fprintf (file, "\n");
756 /* Create an edge and initialize it with given values. */
758 create_ddg_edge (ddg_node_ptr src, ddg_node_ptr dest,
759 dep_type t, dep_data_type dt, int l, int d)
761 ddg_edge_ptr e = (ddg_edge_ptr) xmalloc (sizeof (struct ddg_edge));
769 e->next_in = e->next_out = NULL;
774 /* Add the given edge to the in/out linked lists of the DDG nodes. */
776 add_edge_to_ddg (ddg_ptr g ATTRIBUTE_UNUSED, ddg_edge_ptr e)
778 ddg_node_ptr src = e->src;
779 ddg_node_ptr dest = e->dest;
781 /* Should have allocated the sbitmaps. */
782 gcc_assert (src->successors && dest->predecessors);
784 SET_BIT (src->successors, dest->cuid);
785 SET_BIT (dest->predecessors, src->cuid);
786 e->next_in = dest->in;
788 e->next_out = src->out;
794 /* Algorithm for computing the recurrence_length of an scc. We assume at
795 for now that cycles in the data dependence graph contain a single backarc.
796 This simplifies the algorithm, and can be generalized later. */
798 set_recurrence_length (ddg_scc_ptr scc, ddg_ptr g)
803 for (j = 0; j < scc->num_backarcs; j++)
805 ddg_edge_ptr backarc = scc->backarcs[j];
807 int distance = backarc->distance;
808 ddg_node_ptr src = backarc->dest;
809 ddg_node_ptr dest = backarc->src;
811 length = longest_simple_path (g, src->cuid, dest->cuid, scc->nodes);
814 /* fprintf (stderr, "Backarc not on simple cycle in SCC.\n"); */
817 length += backarc->latency;
818 result = MAX (result, (length / distance));
820 scc->recurrence_length = result;
823 /* Create a new SCC given the set of its nodes. Compute its recurrence_length
824 and mark edges that belong to this scc as IN_SCC. */
826 create_scc (ddg_ptr g, sbitmap nodes)
830 sbitmap_iterator sbi;
832 scc = (ddg_scc_ptr) xmalloc (sizeof (struct ddg_scc));
833 scc->backarcs = NULL;
834 scc->num_backarcs = 0;
835 scc->nodes = sbitmap_alloc (g->num_nodes);
836 sbitmap_copy (scc->nodes, nodes);
838 /* Mark the backarcs that belong to this SCC. */
839 EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, u, sbi)
842 ddg_node_ptr n = &g->nodes[u];
844 for (e = n->out; e; e = e->next_out)
845 if (TEST_BIT (nodes, e->dest->cuid))
847 e->aux.count = IN_SCC;
849 add_backarc_to_scc (scc, e);
853 set_recurrence_length (scc, g);
857 /* Cleans the memory allocation of a given SCC. */
859 free_scc (ddg_scc_ptr scc)
864 sbitmap_free (scc->nodes);
865 if (scc->num_backarcs > 0)
866 free (scc->backarcs);
871 /* Add a given edge known to be a backarc to the given DDG. */
873 add_backarc_to_ddg (ddg_ptr g, ddg_edge_ptr e)
875 int size = (g->num_backarcs + 1) * sizeof (ddg_edge_ptr);
877 add_edge_to_ddg (g, e);
878 g->backarcs = (ddg_edge_ptr *) xrealloc (g->backarcs, size);
879 g->backarcs[g->num_backarcs++] = e;
882 /* Add backarc to an SCC. */
884 add_backarc_to_scc (ddg_scc_ptr scc, ddg_edge_ptr e)
886 int size = (scc->num_backarcs + 1) * sizeof (ddg_edge_ptr);
888 scc->backarcs = (ddg_edge_ptr *) xrealloc (scc->backarcs, size);
889 scc->backarcs[scc->num_backarcs++] = e;
892 /* Add the given SCC to the DDG. */
894 add_scc_to_ddg (ddg_all_sccs_ptr g, ddg_scc_ptr scc)
896 int size = (g->num_sccs + 1) * sizeof (ddg_scc_ptr);
898 g->sccs = (ddg_scc_ptr *) xrealloc (g->sccs, size);
899 g->sccs[g->num_sccs++] = scc;
902 /* Given the instruction INSN return the node that represents it. */
904 get_node_of_insn (ddg_ptr g, rtx insn)
908 for (i = 0; i < g->num_nodes; i++)
909 if (insn == g->nodes[i].insn)
914 /* Given a set OPS of nodes in the DDG, find the set of their successors
915 which are not in OPS, and set their bits in SUCC. Bits corresponding to
916 OPS are cleared from SUCC. Leaves the other bits in SUCC unchanged. */
918 find_successors (sbitmap succ, ddg_ptr g, sbitmap ops)
921 sbitmap_iterator sbi;
923 EXECUTE_IF_SET_IN_SBITMAP (ops, 0, i, sbi)
925 const sbitmap node_succ = NODE_SUCCESSORS (&g->nodes[i]);
926 sbitmap_a_or_b (succ, succ, node_succ);
929 /* We want those that are not in ops. */
930 sbitmap_difference (succ, succ, ops);
933 /* Given a set OPS of nodes in the DDG, find the set of their predecessors
934 which are not in OPS, and set their bits in PREDS. Bits corresponding to
935 OPS are cleared from PREDS. Leaves the other bits in PREDS unchanged. */
937 find_predecessors (sbitmap preds, ddg_ptr g, sbitmap ops)
940 sbitmap_iterator sbi;
942 EXECUTE_IF_SET_IN_SBITMAP (ops, 0, i, sbi)
944 const sbitmap node_preds = NODE_PREDECESSORS (&g->nodes[i]);
945 sbitmap_a_or_b (preds, preds, node_preds);
948 /* We want those that are not in ops. */
949 sbitmap_difference (preds, preds, ops);
953 /* Compare function to be passed to qsort to order the backarcs in descending
956 compare_sccs (const void *s1, const void *s2)
958 const int rec_l1 = (*(const ddg_scc_ptr *)s1)->recurrence_length;
959 const int rec_l2 = (*(const ddg_scc_ptr *)s2)->recurrence_length;
960 return ((rec_l2 > rec_l1) - (rec_l2 < rec_l1));
964 /* Order the backarcs in descending recMII order using compare_sccs. */
966 order_sccs (ddg_all_sccs_ptr g)
968 qsort (g->sccs, g->num_sccs, sizeof (ddg_scc_ptr),
969 (int (*) (const void *, const void *)) compare_sccs);
972 #ifdef ENABLE_CHECKING
973 /* Check that every node in SCCS belongs to exactly one strongly connected
974 component and that no element of SCCS is empty. */
976 check_sccs (ddg_all_sccs_ptr sccs, int num_nodes)
979 sbitmap tmp = sbitmap_alloc (num_nodes);
982 for (i = 0; i < sccs->num_sccs; i++)
984 gcc_assert (!sbitmap_empty_p (sccs->sccs[i]->nodes));
985 /* Verify that every node in sccs is in exactly one strongly
986 connected component. */
987 gcc_assert (!sbitmap_any_common_bits (tmp, sccs->sccs[i]->nodes));
988 sbitmap_a_or_b (tmp, tmp, sccs->sccs[i]->nodes);
994 /* Perform the Strongly Connected Components decomposing algorithm on the
995 DDG and return DDG_ALL_SCCS structure that contains them. */
997 create_ddg_all_sccs (ddg_ptr g)
1000 int num_nodes = g->num_nodes;
1001 sbitmap from = sbitmap_alloc (num_nodes);
1002 sbitmap to = sbitmap_alloc (num_nodes);
1003 sbitmap scc_nodes = sbitmap_alloc (num_nodes);
1004 ddg_all_sccs_ptr sccs = (ddg_all_sccs_ptr)
1005 xmalloc (sizeof (struct ddg_all_sccs));
1011 for (i = 0; i < g->num_backarcs; i++)
1014 ddg_edge_ptr backarc = g->backarcs[i];
1015 ddg_node_ptr src = backarc->src;
1016 ddg_node_ptr dest = backarc->dest;
1018 /* If the backarc already belongs to an SCC, continue. */
1019 if (backarc->aux.count == IN_SCC)
1022 sbitmap_zero (scc_nodes);
1023 sbitmap_zero (from);
1025 SET_BIT (from, dest->cuid);
1026 SET_BIT (to, src->cuid);
1028 if (find_nodes_on_paths (scc_nodes, g, from, to))
1030 scc = create_scc (g, scc_nodes);
1031 add_scc_to_ddg (sccs, scc);
1035 sbitmap_free (from);
1037 sbitmap_free (scc_nodes);
1038 #ifdef ENABLE_CHECKING
1039 check_sccs (sccs, num_nodes);
1044 /* Frees the memory allocated for all SCCs of the DDG, but keeps the DDG. */
1046 free_ddg_all_sccs (ddg_all_sccs_ptr all_sccs)
1053 for (i = 0; i < all_sccs->num_sccs; i++)
1054 free_scc (all_sccs->sccs[i]);
1056 free (all_sccs->sccs);
1061 /* Given FROM - a bitmap of source nodes - and TO - a bitmap of destination
1062 nodes - find all nodes that lie on paths from FROM to TO (not excluding
1063 nodes from FROM and TO). Return nonzero if nodes exist. */
1065 find_nodes_on_paths (sbitmap result, ddg_ptr g, sbitmap from, sbitmap to)
1070 int num_nodes = g->num_nodes;
1071 sbitmap_iterator sbi;
1073 sbitmap workset = sbitmap_alloc (num_nodes);
1074 sbitmap reachable_from = sbitmap_alloc (num_nodes);
1075 sbitmap reach_to = sbitmap_alloc (num_nodes);
1076 sbitmap tmp = sbitmap_alloc (num_nodes);
1078 sbitmap_copy (reachable_from, from);
1079 sbitmap_copy (tmp, from);
1085 sbitmap_copy (workset, tmp);
1087 EXECUTE_IF_SET_IN_SBITMAP (workset, 0, u, sbi)
1090 ddg_node_ptr u_node = &g->nodes[u];
1092 for (e = u_node->out; e != (ddg_edge_ptr) 0; e = e->next_out)
1094 ddg_node_ptr v_node = e->dest;
1095 int v = v_node->cuid;
1097 if (!TEST_BIT (reachable_from, v))
1099 SET_BIT (reachable_from, v);
1107 sbitmap_copy (reach_to, to);
1108 sbitmap_copy (tmp, to);
1114 sbitmap_copy (workset, tmp);
1116 EXECUTE_IF_SET_IN_SBITMAP (workset, 0, u, sbi)
1119 ddg_node_ptr u_node = &g->nodes[u];
1121 for (e = u_node->in; e != (ddg_edge_ptr) 0; e = e->next_in)
1123 ddg_node_ptr v_node = e->src;
1124 int v = v_node->cuid;
1126 if (!TEST_BIT (reach_to, v))
1128 SET_BIT (reach_to, v);
1136 answer = sbitmap_a_and_b_cg (result, reachable_from, reach_to);
1137 sbitmap_free (workset);
1138 sbitmap_free (reachable_from);
1139 sbitmap_free (reach_to);
1145 /* Updates the counts of U_NODE's successors (that belong to NODES) to be
1146 at-least as large as the count of U_NODE plus the latency between them.
1147 Sets a bit in TMP for each successor whose count was changed (increased).
1148 Returns nonzero if any count was changed. */
1150 update_dist_to_successors (ddg_node_ptr u_node, sbitmap nodes, sbitmap tmp)
1155 for (e = u_node->out; e; e = e->next_out)
1157 ddg_node_ptr v_node = e->dest;
1158 int v = v_node->cuid;
1160 if (TEST_BIT (nodes, v)
1161 && (e->distance == 0)
1162 && (v_node->aux.count < u_node->aux.count + e->latency))
1164 v_node->aux.count = u_node->aux.count + e->latency;
1173 /* Find the length of a longest path from SRC to DEST in G,
1174 going only through NODES, and disregarding backarcs. */
1176 longest_simple_path (struct ddg * g, int src, int dest, sbitmap nodes)
1182 int num_nodes = g->num_nodes;
1183 sbitmap workset = sbitmap_alloc (num_nodes);
1184 sbitmap tmp = sbitmap_alloc (num_nodes);
1187 /* Data will hold the distance of the longest path found so far from
1188 src to each node. Initialize to -1 = less than minimum. */
1189 for (i = 0; i < g->num_nodes; i++)
1190 g->nodes[i].aux.count = -1;
1191 g->nodes[src].aux.count = 0;
1198 sbitmap_iterator sbi;
1201 sbitmap_copy (workset, tmp);
1203 EXECUTE_IF_SET_IN_SBITMAP (workset, 0, u, sbi)
1205 ddg_node_ptr u_node = &g->nodes[u];
1207 change |= update_dist_to_successors (u_node, nodes, tmp);
1210 result = g->nodes[dest].aux.count;
1211 sbitmap_free (workset);
1216 #endif /* INSN_SCHEDULING */