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 2, 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 COPYING. If not, write to the Free
20 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
26 #include "coretypes.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 /* A flag indicating that a ddg edge belongs to an SCC or not. */
49 enum edge_flag
{NOT_IN_SCC
= 0, IN_SCC
};
51 /* Forward declarations. */
52 static void add_backarc_to_ddg (ddg_ptr
, ddg_edge_ptr
);
53 static void add_backarc_to_scc (ddg_scc_ptr
, ddg_edge_ptr
);
54 static void add_scc_to_ddg (ddg_all_sccs_ptr
, ddg_scc_ptr
);
55 static void create_ddg_dependence (ddg_ptr
, ddg_node_ptr
, ddg_node_ptr
, dep_t
);
56 static void create_ddg_dep_no_link (ddg_ptr
, ddg_node_ptr
, ddg_node_ptr
,
57 dep_type
, dep_data_type
, int);
58 static ddg_edge_ptr
create_ddg_edge (ddg_node_ptr
, ddg_node_ptr
, dep_type
,
59 dep_data_type
, int, int);
60 static void add_edge_to_ddg (ddg_ptr g
, ddg_edge_ptr
);
62 /* Auxiliary variable for mem_read_insn_p/mem_write_insn_p. */
63 static bool mem_ref_p
;
65 /* Auxiliary function for mem_read_insn_p. */
67 mark_mem_use (rtx
*x
, void *data ATTRIBUTE_UNUSED
)
74 /* Auxiliary function for mem_read_insn_p. */
76 mark_mem_use_1 (rtx
*x
, void *data
)
78 for_each_rtx (x
, mark_mem_use
, data
);
81 /* Returns nonzero if INSN reads from memory. */
83 mem_read_insn_p (rtx insn
)
86 note_uses (&PATTERN (insn
), mark_mem_use_1
, NULL
);
91 mark_mem_store (rtx loc
, rtx setter ATTRIBUTE_UNUSED
, void *data ATTRIBUTE_UNUSED
)
97 /* Returns nonzero if INSN writes to memory. */
99 mem_write_insn_p (rtx insn
)
102 note_stores (PATTERN (insn
), mark_mem_store
, NULL
);
106 /* Returns nonzero if X has access to memory. */
108 rtx_mem_access_p (rtx x
)
121 fmt
= GET_RTX_FORMAT (code
);
122 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
126 if (rtx_mem_access_p (XEXP (x
, i
)))
129 else if (fmt
[i
] == 'E')
130 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
132 if (rtx_mem_access_p (XVECEXP (x
, i
, j
)))
139 /* Returns nonzero if INSN reads to or writes from memory. */
141 mem_access_insn_p (rtx insn
)
143 return rtx_mem_access_p (PATTERN (insn
));
146 /* Computes the dependence parameters (latency, distance etc.), creates
147 a ddg_edge and adds it to the given DDG. */
149 create_ddg_dependence (ddg_ptr g
, ddg_node_ptr src_node
,
150 ddg_node_ptr dest_node
, dep_t link
)
153 int latency
, distance
= 0;
154 int interloop
= (src_node
->cuid
>= dest_node
->cuid
);
155 dep_type t
= TRUE_DEP
;
156 dep_data_type dt
= (mem_access_insn_p (src_node
->insn
)
157 && mem_access_insn_p (dest_node
->insn
) ? MEM_DEP
160 /* For now we don't have an exact calculation of the distance,
161 so assume 1 conservatively. */
167 /* Note: REG_DEP_ANTI applies to MEM ANTI_DEP as well!! */
168 if (DEP_KIND (link
) == REG_DEP_ANTI
)
170 else if (DEP_KIND (link
) == REG_DEP_OUTPUT
)
172 latency
= dep_cost (link
);
174 e
= create_ddg_edge (src_node
, dest_node
, t
, dt
, latency
, distance
);
178 /* Some interloop dependencies are relaxed:
179 1. Every insn is output dependent on itself; ignore such deps.
180 2. Every true/flow dependence is an anti dependence in the
181 opposite direction with distance 1; such register deps
182 will be removed by renaming if broken --- ignore them. */
183 if (!(t
== OUTPUT_DEP
&& src_node
== dest_node
)
184 && !(t
== ANTI_DEP
&& dt
== REG_DEP
))
185 add_backarc_to_ddg (g
, e
);
189 else if (t
== ANTI_DEP
&& dt
== REG_DEP
)
190 free (e
); /* We can fix broken anti register deps using reg-moves. */
192 add_edge_to_ddg (g
, e
);
195 /* The same as the above function, but it doesn't require a link parameter. */
197 create_ddg_dep_no_link (ddg_ptr g
, ddg_node_ptr from
, ddg_node_ptr to
,
198 dep_type d_t
, dep_data_type d_dt
, int distance
)
202 enum reg_note dep_kind
;
203 struct _dep _dep
, *dep
= &_dep
;
206 dep_kind
= REG_DEP_ANTI
;
207 else if (d_t
== OUTPUT_DEP
)
208 dep_kind
= REG_DEP_OUTPUT
;
211 gcc_assert (d_t
== TRUE_DEP
);
213 dep_kind
= REG_DEP_TRUE
;
216 init_dep (dep
, from
->insn
, to
->insn
, dep_kind
);
220 e
= create_ddg_edge (from
, to
, d_t
, d_dt
, l
, distance
);
222 add_backarc_to_ddg (g
, e
);
224 add_edge_to_ddg (g
, e
);
228 /* Given a downwards exposed register def RD, add inter-loop true dependences
229 for all its uses in the next iteration, and an output dependence to the
230 first def of the next iteration. */
232 add_deps_for_def (ddg_ptr g
, struct df_ref
*rd
)
234 int regno
= DF_REF_REGNO (rd
);
235 struct df_ru_bb_info
*bb_info
= DF_RU_BB_INFO (g
->bb
);
236 struct df_link
*r_use
;
237 int use_before_def
= false;
238 rtx def_insn
= DF_REF_INSN (rd
);
239 ddg_node_ptr src_node
= get_node_of_insn (g
, def_insn
);
241 /* Create and inter-loop true dependence between RD and each of its uses
242 that is upwards exposed in RD's block. */
243 for (r_use
= DF_REF_CHAIN (rd
); r_use
!= NULL
; r_use
= r_use
->next
)
245 if (bitmap_bit_p (bb_info
->gen
, r_use
->ref
->id
))
247 rtx use_insn
= DF_REF_INSN (r_use
->ref
);
248 ddg_node_ptr dest_node
= get_node_of_insn (g
, use_insn
);
250 gcc_assert (src_node
&& dest_node
);
252 /* Any such upwards exposed use appears before the rd def. */
253 use_before_def
= true;
254 create_ddg_dep_no_link (g
, src_node
, dest_node
, TRUE_DEP
,
259 /* Create an inter-loop output dependence between RD (which is the
260 last def in its block, being downwards exposed) and the first def
261 in its block. Avoid creating a self output dependence. Avoid creating
262 an output dependence if there is a dependence path between the two defs
263 starting with a true dependence followed by an anti dependence (i.e. if
264 there is a use between the two defs. */
265 if (! use_before_def
)
267 struct df_ref
*def
= df_bb_regno_first_def_find (g
->bb
, regno
);
269 ddg_node_ptr dest_node
;
271 if (!def
|| rd
->id
== def
->id
)
274 /* Check if there are uses after RD. */
275 for (i
= src_node
->cuid
+ 1; i
< g
->num_nodes
; i
++)
276 if (df_find_use (g
->nodes
[i
].insn
, DF_REF_REG (rd
)))
279 dest_node
= get_node_of_insn (g
, def
->insn
);
280 create_ddg_dep_no_link (g
, src_node
, dest_node
, OUTPUT_DEP
, REG_DEP
, 1);
284 /* Given a register USE, add an inter-loop anti dependence to the first
285 (nearest BLOCK_BEGIN) def of the next iteration, unless USE is followed
286 by a def in the block. */
288 add_deps_for_use (ddg_ptr g
, struct df_ref
*use
)
291 int regno
= DF_REF_REGNO (use
);
292 struct df_ref
*first_def
= df_bb_regno_first_def_find (g
->bb
, regno
);
293 ddg_node_ptr use_node
;
294 ddg_node_ptr def_node
;
295 struct df_rd_bb_info
*bb_info
;
297 bb_info
= DF_RD_BB_INFO (g
->bb
);
302 use_node
= get_node_of_insn (g
, use
->insn
);
303 def_node
= get_node_of_insn (g
, first_def
->insn
);
305 gcc_assert (use_node
&& def_node
);
307 /* Make sure there are no defs after USE. */
308 for (i
= use_node
->cuid
+ 1; i
< g
->num_nodes
; i
++)
309 if (df_find_def (g
->nodes
[i
].insn
, DF_REF_REG (use
)))
311 /* We must not add ANTI dep when there is an intra-loop TRUE dep in
312 the opposite direction. If the first_def reaches the USE then there is
314 if (! bitmap_bit_p (bb_info
->gen
, first_def
->id
))
315 create_ddg_dep_no_link (g
, use_node
, def_node
, ANTI_DEP
, REG_DEP
, 1);
318 /* Build inter-loop dependencies, by looking at DF analysis backwards. */
320 build_inter_loop_deps (ddg_ptr g
)
322 unsigned rd_num
, u_num
;
323 struct df_rd_bb_info
*rd_bb_info
;
324 struct df_ru_bb_info
*ru_bb_info
;
327 rd_bb_info
= DF_RD_BB_INFO (g
->bb
);
329 /* Find inter-loop output and true deps by connecting downward exposed defs
330 to the first def of the BB and to upwards exposed uses. */
331 EXECUTE_IF_SET_IN_BITMAP (rd_bb_info
->gen
, 0, rd_num
, bi
)
333 struct df_ref
*rd
= DF_DEFS_GET (rd_num
);
335 add_deps_for_def (g
, rd
);
338 ru_bb_info
= DF_RU_BB_INFO (g
->bb
);
340 /* Find inter-loop anti deps. We are interested in uses of the block that
341 appear below all defs; this implies that these uses are killed. */
342 EXECUTE_IF_SET_IN_BITMAP (ru_bb_info
->kill
, 0, u_num
, bi
)
344 struct df_ref
*use
= DF_USES_GET (u_num
);
345 if (!(DF_REF_FLAGS (use
) & DF_REF_IN_NOTE
))
346 /* We are interested in uses of this BB. */
347 if (BLOCK_FOR_INSN (use
->insn
) == g
->bb
)
348 add_deps_for_use (g
, use
);
352 /* Given two nodes, analyze their RTL insns and add inter-loop mem deps
355 add_inter_loop_mem_dep (ddg_ptr g
, ddg_node_ptr from
, ddg_node_ptr to
)
357 if (mem_write_insn_p (from
->insn
))
359 if (mem_read_insn_p (to
->insn
))
360 create_ddg_dep_no_link (g
, from
, to
, TRUE_DEP
, MEM_DEP
, 1);
361 else if (from
->cuid
!= to
->cuid
)
362 create_ddg_dep_no_link (g
, from
, to
, OUTPUT_DEP
, MEM_DEP
, 1);
366 if (mem_read_insn_p (to
->insn
))
368 else if (from
->cuid
!= to
->cuid
)
370 create_ddg_dep_no_link (g
, from
, to
, ANTI_DEP
, MEM_DEP
, 1);
371 create_ddg_dep_no_link (g
, to
, from
, TRUE_DEP
, MEM_DEP
, 1);
377 /* Perform intra-block Data Dependency analysis and connect the nodes in
378 the DDG. We assume the loop has a single basic block. */
380 build_intra_loop_deps (ddg_ptr g
)
383 /* Hold the dependency analysis state during dependency calculations. */
384 struct deps tmp_deps
;
388 /* Build the dependence information, using the sched_analyze function. */
390 init_deps (&tmp_deps
);
392 /* Do the intra-block data dependence analysis for the given block. */
393 get_ebb_head_tail (g
->bb
, g
->bb
, &head
, &tail
);
394 sched_analyze (&tmp_deps
, head
, tail
);
396 /* Build intra-loop data dependencies using the scheduler dependency
398 for (i
= 0; i
< g
->num_nodes
; i
++)
400 ddg_node_ptr dest_node
= &g
->nodes
[i
];
402 if (! INSN_P (dest_node
->insn
))
405 FOR_EACH_DEP_LINK (link
, INSN_BACK_DEPS (dest_node
->insn
))
407 dep_t dep
= DEP_LINK_DEP (link
);
408 ddg_node_ptr src_node
= get_node_of_insn (g
, DEP_PRO (dep
));
414 create_ddg_dependence (g
, src_node
, dest_node
, dep
);
417 /* If this insn modifies memory, add an edge to all insns that access
419 if (mem_access_insn_p (dest_node
->insn
))
423 for (j
= 0; j
<= i
; j
++)
425 ddg_node_ptr j_node
= &g
->nodes
[j
];
426 if (mem_access_insn_p (j_node
->insn
))
427 /* Don't bother calculating inter-loop dep if an intra-loop dep
429 if (! TEST_BIT (dest_node
->successors
, j
))
430 add_inter_loop_mem_dep (g
, dest_node
, j_node
);
435 /* Free the INSN_LISTs. */
436 finish_deps_global ();
437 free_deps (&tmp_deps
);
441 /* Given a basic block, create its DDG and return a pointer to a variable
442 of ddg type that represents it.
443 Initialize the ddg structure fields to the appropriate values. */
445 create_ddg (basic_block bb
, int closing_branch_deps
)
448 rtx insn
, first_note
;
452 g
= (ddg_ptr
) xcalloc (1, sizeof (struct ddg
));
455 g
->closing_branch_deps
= closing_branch_deps
;
457 /* Count the number of insns in the BB. */
458 for (insn
= BB_HEAD (bb
); insn
!= NEXT_INSN (BB_END (bb
));
459 insn
= NEXT_INSN (insn
))
461 if (! INSN_P (insn
) || GET_CODE (PATTERN (insn
)) == USE
)
464 if (mem_read_insn_p (insn
))
466 if (mem_write_insn_p (insn
))
471 /* There is nothing to do for this BB. */
478 /* Allocate the nodes array, and initialize the nodes. */
479 g
->num_nodes
= num_nodes
;
480 g
->nodes
= (ddg_node_ptr
) xcalloc (num_nodes
, sizeof (struct ddg_node
));
481 g
->closing_branch
= NULL
;
483 first_note
= NULL_RTX
;
484 for (insn
= BB_HEAD (bb
); insn
!= NEXT_INSN (BB_END (bb
));
485 insn
= NEXT_INSN (insn
))
489 if (! first_note
&& NOTE_P (insn
)
490 && NOTE_KIND (insn
) != NOTE_INSN_BASIC_BLOCK
)
496 gcc_assert (!g
->closing_branch
);
497 g
->closing_branch
= &g
->nodes
[i
];
499 else if (GET_CODE (PATTERN (insn
)) == USE
)
506 g
->nodes
[i
].cuid
= i
;
507 g
->nodes
[i
].successors
= sbitmap_alloc (num_nodes
);
508 sbitmap_zero (g
->nodes
[i
].successors
);
509 g
->nodes
[i
].predecessors
= sbitmap_alloc (num_nodes
);
510 sbitmap_zero (g
->nodes
[i
].predecessors
);
511 g
->nodes
[i
].first_note
= (first_note
? first_note
: insn
);
512 g
->nodes
[i
++].insn
= insn
;
513 first_note
= NULL_RTX
;
516 /* We must have found a branch in DDG. */
517 gcc_assert (g
->closing_branch
);
520 /* Build the data dependency graph. */
521 build_intra_loop_deps (g
);
522 build_inter_loop_deps (g
);
526 /* Free all the memory allocated for the DDG. */
535 for (i
= 0; i
< g
->num_nodes
; i
++)
537 ddg_edge_ptr e
= g
->nodes
[i
].out
;
541 ddg_edge_ptr next
= e
->next_out
;
546 sbitmap_free (g
->nodes
[i
].successors
);
547 sbitmap_free (g
->nodes
[i
].predecessors
);
549 if (g
->num_backarcs
> 0)
556 print_ddg_edge (FILE *file
, ddg_edge_ptr e
)
572 fprintf (file
, " [%d -(%c,%d,%d)-> %d] ", INSN_UID (e
->src
->insn
),
573 dep_c
, e
->latency
, e
->distance
, INSN_UID (e
->dest
->insn
));
576 /* Print the DDG nodes with there in/out edges to the dump file. */
578 print_ddg (FILE *file
, ddg_ptr g
)
582 for (i
= 0; i
< g
->num_nodes
; i
++)
586 print_rtl_single (file
, g
->nodes
[i
].insn
);
587 fprintf (file
, "OUT ARCS: ");
588 for (e
= g
->nodes
[i
].out
; e
; e
= e
->next_out
)
589 print_ddg_edge (file
, e
);
591 fprintf (file
, "\nIN ARCS: ");
592 for (e
= g
->nodes
[i
].in
; e
; e
= e
->next_in
)
593 print_ddg_edge (file
, e
);
595 fprintf (file
, "\n");
599 /* Print the given DDG in VCG format. */
601 vcg_print_ddg (FILE *file
, ddg_ptr g
)
605 fprintf (file
, "graph: {\n");
606 for (src_cuid
= 0; src_cuid
< g
->num_nodes
; src_cuid
++)
609 int src_uid
= INSN_UID (g
->nodes
[src_cuid
].insn
);
611 fprintf (file
, "node: {title: \"%d_%d\" info1: \"", src_cuid
, src_uid
);
612 print_rtl_single (file
, g
->nodes
[src_cuid
].insn
);
613 fprintf (file
, "\"}\n");
614 for (e
= g
->nodes
[src_cuid
].out
; e
; e
= e
->next_out
)
616 int dst_uid
= INSN_UID (e
->dest
->insn
);
617 int dst_cuid
= e
->dest
->cuid
;
619 /* Give the backarcs a different color. */
621 fprintf (file
, "backedge: {color: red ");
623 fprintf (file
, "edge: { ");
625 fprintf (file
, "sourcename: \"%d_%d\" ", src_cuid
, src_uid
);
626 fprintf (file
, "targetname: \"%d_%d\" ", dst_cuid
, dst_uid
);
627 fprintf (file
, "label: \"%d_%d\"}\n", e
->latency
, e
->distance
);
630 fprintf (file
, "}\n");
633 /* Create an edge and initialize it with given values. */
635 create_ddg_edge (ddg_node_ptr src
, ddg_node_ptr dest
,
636 dep_type t
, dep_data_type dt
, int l
, int d
)
638 ddg_edge_ptr e
= (ddg_edge_ptr
) xmalloc (sizeof (struct ddg_edge
));
646 e
->next_in
= e
->next_out
= NULL
;
651 /* Add the given edge to the in/out linked lists of the DDG nodes. */
653 add_edge_to_ddg (ddg_ptr g ATTRIBUTE_UNUSED
, ddg_edge_ptr e
)
655 ddg_node_ptr src
= e
->src
;
656 ddg_node_ptr dest
= e
->dest
;
658 /* Should have allocated the sbitmaps. */
659 gcc_assert (src
->successors
&& dest
->predecessors
);
661 SET_BIT (src
->successors
, dest
->cuid
);
662 SET_BIT (dest
->predecessors
, src
->cuid
);
663 e
->next_in
= dest
->in
;
665 e
->next_out
= src
->out
;
671 /* Algorithm for computing the recurrence_length of an scc. We assume at
672 for now that cycles in the data dependence graph contain a single backarc.
673 This simplifies the algorithm, and can be generalized later. */
675 set_recurrence_length (ddg_scc_ptr scc
, ddg_ptr g
)
680 for (j
= 0; j
< scc
->num_backarcs
; j
++)
682 ddg_edge_ptr backarc
= scc
->backarcs
[j
];
684 int distance
= backarc
->distance
;
685 ddg_node_ptr src
= backarc
->dest
;
686 ddg_node_ptr dest
= backarc
->src
;
688 length
= longest_simple_path (g
, src
->cuid
, dest
->cuid
, scc
->nodes
);
691 /* fprintf (stderr, "Backarc not on simple cycle in SCC.\n"); */
694 length
+= backarc
->latency
;
695 result
= MAX (result
, (length
/ distance
));
697 scc
->recurrence_length
= result
;
700 /* Create a new SCC given the set of its nodes. Compute its recurrence_length
701 and mark edges that belong to this scc as IN_SCC. */
703 create_scc (ddg_ptr g
, sbitmap nodes
)
707 sbitmap_iterator sbi
;
709 scc
= (ddg_scc_ptr
) xmalloc (sizeof (struct ddg_scc
));
710 scc
->backarcs
= NULL
;
711 scc
->num_backarcs
= 0;
712 scc
->nodes
= sbitmap_alloc (g
->num_nodes
);
713 sbitmap_copy (scc
->nodes
, nodes
);
715 /* Mark the backarcs that belong to this SCC. */
716 EXECUTE_IF_SET_IN_SBITMAP (nodes
, 0, u
, sbi
)
719 ddg_node_ptr n
= &g
->nodes
[u
];
721 for (e
= n
->out
; e
; e
= e
->next_out
)
722 if (TEST_BIT (nodes
, e
->dest
->cuid
))
724 e
->aux
.count
= IN_SCC
;
726 add_backarc_to_scc (scc
, e
);
730 set_recurrence_length (scc
, g
);
734 /* Cleans the memory allocation of a given SCC. */
736 free_scc (ddg_scc_ptr scc
)
741 sbitmap_free (scc
->nodes
);
742 if (scc
->num_backarcs
> 0)
743 free (scc
->backarcs
);
748 /* Add a given edge known to be a backarc to the given DDG. */
750 add_backarc_to_ddg (ddg_ptr g
, ddg_edge_ptr e
)
752 int size
= (g
->num_backarcs
+ 1) * sizeof (ddg_edge_ptr
);
754 add_edge_to_ddg (g
, e
);
755 g
->backarcs
= (ddg_edge_ptr
*) xrealloc (g
->backarcs
, size
);
756 g
->backarcs
[g
->num_backarcs
++] = e
;
759 /* Add backarc to an SCC. */
761 add_backarc_to_scc (ddg_scc_ptr scc
, ddg_edge_ptr e
)
763 int size
= (scc
->num_backarcs
+ 1) * sizeof (ddg_edge_ptr
);
765 scc
->backarcs
= (ddg_edge_ptr
*) xrealloc (scc
->backarcs
, size
);
766 scc
->backarcs
[scc
->num_backarcs
++] = e
;
769 /* Add the given SCC to the DDG. */
771 add_scc_to_ddg (ddg_all_sccs_ptr g
, ddg_scc_ptr scc
)
773 int size
= (g
->num_sccs
+ 1) * sizeof (ddg_scc_ptr
);
775 g
->sccs
= (ddg_scc_ptr
*) xrealloc (g
->sccs
, size
);
776 g
->sccs
[g
->num_sccs
++] = scc
;
779 /* Given the instruction INSN return the node that represents it. */
781 get_node_of_insn (ddg_ptr g
, rtx insn
)
785 for (i
= 0; i
< g
->num_nodes
; i
++)
786 if (insn
== g
->nodes
[i
].insn
)
791 /* Given a set OPS of nodes in the DDG, find the set of their successors
792 which are not in OPS, and set their bits in SUCC. Bits corresponding to
793 OPS are cleared from SUCC. Leaves the other bits in SUCC unchanged. */
795 find_successors (sbitmap succ
, ddg_ptr g
, sbitmap ops
)
798 sbitmap_iterator sbi
;
800 EXECUTE_IF_SET_IN_SBITMAP (ops
, 0, i
, sbi
)
802 const sbitmap node_succ
= NODE_SUCCESSORS (&g
->nodes
[i
]);
803 sbitmap_a_or_b (succ
, succ
, node_succ
);
806 /* We want those that are not in ops. */
807 sbitmap_difference (succ
, succ
, ops
);
810 /* Given a set OPS of nodes in the DDG, find the set of their predecessors
811 which are not in OPS, and set their bits in PREDS. Bits corresponding to
812 OPS are cleared from PREDS. Leaves the other bits in PREDS unchanged. */
814 find_predecessors (sbitmap preds
, ddg_ptr g
, sbitmap ops
)
817 sbitmap_iterator sbi
;
819 EXECUTE_IF_SET_IN_SBITMAP (ops
, 0, i
, sbi
)
821 const sbitmap node_preds
= NODE_PREDECESSORS (&g
->nodes
[i
]);
822 sbitmap_a_or_b (preds
, preds
, node_preds
);
825 /* We want those that are not in ops. */
826 sbitmap_difference (preds
, preds
, ops
);
830 /* Compare function to be passed to qsort to order the backarcs in descending
833 compare_sccs (const void *s1
, const void *s2
)
835 int rec_l1
= (*(ddg_scc_ptr
*)s1
)->recurrence_length
;
836 int rec_l2
= (*(ddg_scc_ptr
*)s2
)->recurrence_length
;
837 return ((rec_l2
> rec_l1
) - (rec_l2
< rec_l1
));
841 /* Order the backarcs in descending recMII order using compare_sccs. */
843 order_sccs (ddg_all_sccs_ptr g
)
845 qsort (g
->sccs
, g
->num_sccs
, sizeof (ddg_scc_ptr
),
846 (int (*) (const void *, const void *)) compare_sccs
);
849 /* Perform the Strongly Connected Components decomposing algorithm on the
850 DDG and return DDG_ALL_SCCS structure that contains them. */
852 create_ddg_all_sccs (ddg_ptr g
)
855 int num_nodes
= g
->num_nodes
;
856 sbitmap from
= sbitmap_alloc (num_nodes
);
857 sbitmap to
= sbitmap_alloc (num_nodes
);
858 sbitmap scc_nodes
= sbitmap_alloc (num_nodes
);
859 ddg_all_sccs_ptr sccs
= (ddg_all_sccs_ptr
)
860 xmalloc (sizeof (struct ddg_all_sccs
));
866 for (i
= 0; i
< g
->num_backarcs
; i
++)
869 ddg_edge_ptr backarc
= g
->backarcs
[i
];
870 ddg_node_ptr src
= backarc
->src
;
871 ddg_node_ptr dest
= backarc
->dest
;
873 /* If the backarc already belongs to an SCC, continue. */
874 if (backarc
->aux
.count
== IN_SCC
)
879 SET_BIT (from
, dest
->cuid
);
880 SET_BIT (to
, src
->cuid
);
882 if (find_nodes_on_paths (scc_nodes
, g
, from
, to
))
884 scc
= create_scc (g
, scc_nodes
);
885 add_scc_to_ddg (sccs
, scc
);
891 sbitmap_free (scc_nodes
);
895 /* Frees the memory allocated for all SCCs of the DDG, but keeps the DDG. */
897 free_ddg_all_sccs (ddg_all_sccs_ptr all_sccs
)
904 for (i
= 0; i
< all_sccs
->num_sccs
; i
++)
905 free_scc (all_sccs
->sccs
[i
]);
911 /* Given FROM - a bitmap of source nodes - and TO - a bitmap of destination
912 nodes - find all nodes that lie on paths from FROM to TO (not excluding
913 nodes from FROM and TO). Return nonzero if nodes exist. */
915 find_nodes_on_paths (sbitmap result
, ddg_ptr g
, sbitmap from
, sbitmap to
)
920 int num_nodes
= g
->num_nodes
;
921 sbitmap_iterator sbi
;
923 sbitmap workset
= sbitmap_alloc (num_nodes
);
924 sbitmap reachable_from
= sbitmap_alloc (num_nodes
);
925 sbitmap reach_to
= sbitmap_alloc (num_nodes
);
926 sbitmap tmp
= sbitmap_alloc (num_nodes
);
928 sbitmap_copy (reachable_from
, from
);
929 sbitmap_copy (tmp
, from
);
935 sbitmap_copy (workset
, tmp
);
937 EXECUTE_IF_SET_IN_SBITMAP (workset
, 0, u
, sbi
)
940 ddg_node_ptr u_node
= &g
->nodes
[u
];
942 for (e
= u_node
->out
; e
!= (ddg_edge_ptr
) 0; e
= e
->next_out
)
944 ddg_node_ptr v_node
= e
->dest
;
945 int v
= v_node
->cuid
;
947 if (!TEST_BIT (reachable_from
, v
))
949 SET_BIT (reachable_from
, v
);
957 sbitmap_copy (reach_to
, to
);
958 sbitmap_copy (tmp
, to
);
964 sbitmap_copy (workset
, tmp
);
966 EXECUTE_IF_SET_IN_SBITMAP (workset
, 0, u
, sbi
)
969 ddg_node_ptr u_node
= &g
->nodes
[u
];
971 for (e
= u_node
->in
; e
!= (ddg_edge_ptr
) 0; e
= e
->next_in
)
973 ddg_node_ptr v_node
= e
->src
;
974 int v
= v_node
->cuid
;
976 if (!TEST_BIT (reach_to
, v
))
978 SET_BIT (reach_to
, v
);
986 answer
= sbitmap_a_and_b_cg (result
, reachable_from
, reach_to
);
987 sbitmap_free (workset
);
988 sbitmap_free (reachable_from
);
989 sbitmap_free (reach_to
);
995 /* Updates the counts of U_NODE's successors (that belong to NODES) to be
996 at-least as large as the count of U_NODE plus the latency between them.
997 Sets a bit in TMP for each successor whose count was changed (increased).
998 Returns nonzero if any count was changed. */
1000 update_dist_to_successors (ddg_node_ptr u_node
, sbitmap nodes
, sbitmap tmp
)
1005 for (e
= u_node
->out
; e
; e
= e
->next_out
)
1007 ddg_node_ptr v_node
= e
->dest
;
1008 int v
= v_node
->cuid
;
1010 if (TEST_BIT (nodes
, v
)
1011 && (e
->distance
== 0)
1012 && (v_node
->aux
.count
< u_node
->aux
.count
+ e
->latency
))
1014 v_node
->aux
.count
= u_node
->aux
.count
+ e
->latency
;
1023 /* Find the length of a longest path from SRC to DEST in G,
1024 going only through NODES, and disregarding backarcs. */
1026 longest_simple_path (struct ddg
* g
, int src
, int dest
, sbitmap nodes
)
1032 int num_nodes
= g
->num_nodes
;
1033 sbitmap workset
= sbitmap_alloc (num_nodes
);
1034 sbitmap tmp
= sbitmap_alloc (num_nodes
);
1037 /* Data will hold the distance of the longest path found so far from
1038 src to each node. Initialize to -1 = less than minimum. */
1039 for (i
= 0; i
< g
->num_nodes
; i
++)
1040 g
->nodes
[i
].aux
.count
= -1;
1041 g
->nodes
[src
].aux
.count
= 0;
1048 sbitmap_iterator sbi
;
1051 sbitmap_copy (workset
, tmp
);
1053 EXECUTE_IF_SET_IN_SBITMAP (workset
, 0, u
, sbi
)
1055 ddg_node_ptr u_node
= &g
->nodes
[u
];
1057 change
|= update_dist_to_successors (u_node
, nodes
, tmp
);
1060 result
= g
->nodes
[dest
].aux
.count
;
1061 sbitmap_free (workset
);