1 /* DDG - Data Dependence Graph implementation.
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, 59 Temple Place - Suite 330, Boston, MA
26 #include "coretypes.h"
31 #include "hard-reg-set.h"
32 #include "basic-block.h"
36 #include "insn-config.h"
37 #include "insn-attr.h"
40 #include "sched-int.h"
42 #include "cfglayout.h"
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_dependence (ddg_ptr
, ddg_node_ptr
, ddg_node_ptr
, rtx
);
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
, 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_dependence (ddg_ptr g
, ddg_node_ptr src_node
,
152 ddg_node_ptr dest_node
, rtx link
)
155 int latency
, distance
= 0;
156 int interloop
= (src_node
->cuid
>= dest_node
->cuid
);
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
162 /* For now we don't have an exact calculation of the distance,
163 so assume 1 conservatively. */
170 /* Note: REG_DEP_ANTI applies to MEM ANTI_DEP as well!! */
171 if (REG_NOTE_KIND (link
) == REG_DEP_ANTI
)
173 else if (REG_NOTE_KIND (link
) == REG_DEP_OUTPUT
)
175 latency
= insn_cost (src_node
->insn
, link
, dest_node
->insn
);
177 e
= create_ddg_edge (src_node
, dest_node
, t
, dt
, latency
, distance
);
181 /* Some interloop dependencies are relaxed:
182 1. Every insn is output dependent on itself; ignore such deps.
183 2. Every true/flow dependence is an anti dependence in the
184 opposite direction with distance 1; such register deps
185 will be removed by renaming if broken --- ignore them. */
186 if (!(t
== OUTPUT_DEP
&& src_node
== dest_node
)
187 && !(t
== ANTI_DEP
&& dt
== REG_DEP
))
188 add_backarc_to_ddg (g
, e
);
193 add_edge_to_ddg (g
, e
);
196 /* The same as the above function, but it doesn't require a link parameter. */
198 create_ddg_dep_no_link (ddg_ptr g
, ddg_node_ptr from
, ddg_node_ptr to
,
199 dep_type d_t
, dep_data_type d_dt
, int distance
)
203 rtx link
= alloc_INSN_LIST (to
->insn
, NULL_RTX
);
206 PUT_REG_NOTE_KIND (link
, REG_DEP_ANTI
);
207 else if (d_t
== OUTPUT_DEP
)
208 PUT_REG_NOTE_KIND (link
, REG_DEP_OUTPUT
);
210 l
= insn_cost (from
->insn
, link
, to
->insn
);
211 free_INSN_LIST_node (link
);
213 e
= create_ddg_edge (from
, to
, d_t
, d_dt
, l
, distance
);
215 add_backarc_to_ddg (g
, e
);
217 add_edge_to_ddg (g
, e
);
221 /* Given a downwards exposed register def RD, add inter-loop true dependences
222 for all its uses in the next iteration, and an output dependence to the
223 first def of the next iteration. */
225 add_deps_for_def (ddg_ptr g
, struct df
*df
, struct ref
*rd
)
227 int regno
= DF_REF_REGNO (rd
);
228 struct bb_info
*bb_info
= DF_BB_INFO (df
, g
->bb
);
229 struct df_link
*r_use
;
230 int use_before_def
= false;
231 rtx def_insn
= DF_REF_INSN (rd
);
232 ddg_node_ptr src_node
= get_node_of_insn (g
, def_insn
);
234 /* Create and inter-loop true dependence between RD and each of its uses
235 that is upwards exposed in RD's block. */
236 for (r_use
= DF_REF_CHAIN (rd
); r_use
!= NULL
; r_use
= r_use
->next
)
238 if (bitmap_bit_p (bb_info
->ru_gen
, r_use
->ref
->id
))
240 rtx use_insn
= DF_REF_INSN (r_use
->ref
);
241 ddg_node_ptr dest_node
= get_node_of_insn (g
, use_insn
);
243 if (!src_node
|| !dest_node
)
246 /* Any such upwards exposed use appears before the rd def. */
247 use_before_def
= true;
248 create_ddg_dep_no_link (g
, src_node
, dest_node
, TRUE_DEP
,
253 /* Create an inter-loop output dependence between RD (which is the
254 last def in its block, being downwards exposed) and the first def
255 in its block. Avoid creating a self output dependence. Avoid creating
256 an output dependence if there is a dependence path between the two defs
257 starting with a true dependence followed by an anti dependence (i.e. if
258 there is a use between the two defs. */
259 if (! use_before_def
)
261 struct ref
*def
= df_bb_regno_first_def_find (df
, g
->bb
, regno
);
263 ddg_node_ptr dest_node
;
265 if (!def
|| rd
->id
== def
->id
)
268 /* Check if there are uses after RD. */
269 for (i
= src_node
->cuid
+ 1; i
< g
->num_nodes
; i
++)
270 if (df_reg_used (df
, g
->nodes
[i
].insn
, rd
->reg
))
273 dest_node
= get_node_of_insn (g
, def
->insn
);
274 create_ddg_dep_no_link (g
, src_node
, dest_node
, OUTPUT_DEP
, REG_DEP
, 1);
278 /* Given a register USE, add an inter-loop anti dependence to the first
279 (nearest BLOCK_BEGIN) def of the next iteration, unless USE is followed
280 by a def in the block. */
282 add_deps_for_use (ddg_ptr g
, struct df
*df
, struct ref
*use
)
285 int regno
= DF_REF_REGNO (use
);
286 struct ref
*first_def
= df_bb_regno_first_def_find (df
, g
->bb
, regno
);
287 ddg_node_ptr use_node
;
288 ddg_node_ptr def_node
;
289 struct bb_info
*bb_info
;
291 bb_info
= DF_BB_INFO (df
, g
->bb
);
296 use_node
= get_node_of_insn (g
, use
->insn
);
297 def_node
= get_node_of_insn (g
, first_def
->insn
);
299 if (!use_node
|| !def_node
)
302 /* Make sure there are no defs after USE. */
303 for (i
= use_node
->cuid
+ 1; i
< g
->num_nodes
; i
++)
304 if (df_find_def (df
, g
->nodes
[i
].insn
, use
->reg
))
306 /* We must not add ANTI dep when there is an intra-loop TRUE dep in
307 the opozite direction. If the first_def reaches the USE then there is
309 if (! bitmap_bit_p (bb_info
->rd_gen
, first_def
->id
))
310 create_ddg_dep_no_link (g
, use_node
, def_node
, ANTI_DEP
, REG_DEP
, 1);
313 /* Build inter-loop dependencies, by looking at DF analysis backwards. */
315 build_inter_loop_deps (ddg_ptr g
, struct df
*df
)
318 struct bb_info
*bb_info
;
320 bb_info
= DF_BB_INFO (df
, g
->bb
);
322 /* Find inter-loop output and true deps by connecting downward exposed defs
323 to the first def of the BB and to upwards exposed uses. */
324 EXECUTE_IF_SET_IN_BITMAP (bb_info
->rd_gen
, 0, rd_num
,
326 struct ref
*rd
= df
->defs
[rd_num
];
328 add_deps_for_def (g
, df
, rd
);
331 /* Find inter-loop anti deps. We are interested in uses of the block that
332 appear below all defs; this implies that these uses are killed. */
333 EXECUTE_IF_SET_IN_BITMAP (bb_info
->ru_kill
, 0, u_num
,
335 struct ref
*use
= df
->uses
[u_num
];
337 /* We are interested in uses of this BB. */
338 if (BLOCK_FOR_INSN (use
->insn
) == g
->bb
)
339 add_deps_for_use (g
, df
,use
);
343 /* Given two nodes, analyze their RTL insns and add inter-loop mem deps
346 add_inter_loop_mem_dep (ddg_ptr g
, ddg_node_ptr from
, ddg_node_ptr to
)
348 if (mem_write_insn_p (from
->insn
))
350 if (mem_read_insn_p (to
->insn
))
351 create_ddg_dep_no_link (g
, from
, to
, TRUE_DEP
, MEM_DEP
, 1);
352 else if (from
->cuid
!= to
->cuid
)
353 create_ddg_dep_no_link (g
, from
, to
, OUTPUT_DEP
, MEM_DEP
, 1);
357 if (mem_read_insn_p (to
->insn
))
359 else if (from
->cuid
!= to
->cuid
)
361 create_ddg_dep_no_link (g
, from
, to
, ANTI_DEP
, MEM_DEP
, 1);
362 create_ddg_dep_no_link (g
, to
, from
, TRUE_DEP
, MEM_DEP
, 1);
368 /* Perform intra-block Data Dependency analysis and connect the nodes in
369 the DDG. We assume the loop has a single basic block. */
371 build_intra_loop_deps (ddg_ptr g
)
374 /* Hold the dependency analysis state during dependency calculations. */
375 struct deps tmp_deps
;
376 rtx head
, tail
, link
;
378 /* Build the dependence information, using the sched_analyze function. */
380 init_deps (&tmp_deps
);
382 /* Do the intra-block data dependence analysis for the given block. */
383 get_block_head_tail (g
->bb
->index
, &head
, &tail
);
384 sched_analyze (&tmp_deps
, head
, tail
);
386 /* Build intra-loop data dependencies using the scheduler dependency
388 for (i
= 0; i
< g
->num_nodes
; i
++)
390 ddg_node_ptr dest_node
= &g
->nodes
[i
];
392 if (! INSN_P (dest_node
->insn
))
395 for (link
= LOG_LINKS (dest_node
->insn
); link
; link
= XEXP (link
, 1))
397 ddg_node_ptr src_node
= get_node_of_insn (g
, XEXP (link
, 0));
402 add_forward_dependence (XEXP (link
, 0), dest_node
->insn
,
403 REG_NOTE_KIND (link
));
404 create_ddg_dependence (g
, src_node
, dest_node
,
405 INSN_DEPEND (src_node
->insn
));
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
);
432 /* Given a basic block, create its DDG and return a pointer to a variable
433 of ddg type that represents it.
434 Initialize the ddg structure fields to the appropriate values. */
436 create_ddg (basic_block bb
, struct df
*df
, int closing_branch_deps
)
439 rtx insn
, first_note
;
443 g
= (ddg_ptr
) xcalloc (1, sizeof (struct ddg
));
446 g
->closing_branch_deps
= closing_branch_deps
;
448 /* Count the number of insns in the BB. */
449 for (insn
= BB_HEAD (bb
); insn
!= NEXT_INSN (BB_END (bb
));
450 insn
= NEXT_INSN (insn
))
452 if (! INSN_P (insn
) || GET_CODE (PATTERN (insn
)) == USE
)
455 if (mem_read_insn_p (insn
))
457 if (mem_write_insn_p (insn
))
462 /* There is nothing to do for this BB. */
469 /* Allocate the nodes array, and initialize the nodes. */
470 g
->num_nodes
= num_nodes
;
471 g
->nodes
= (ddg_node_ptr
) xcalloc (num_nodes
, sizeof (struct ddg_node
));
472 g
->closing_branch
= NULL
;
474 first_note
= NULL_RTX
;
475 for (insn
= BB_HEAD (bb
); insn
!= NEXT_INSN (BB_END (bb
));
476 insn
= NEXT_INSN (insn
))
480 if (! first_note
&& NOTE_P (insn
)
481 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_BASIC_BLOCK
)
487 if (g
->closing_branch
)
488 abort (); /* Found two branches in DDG. */
490 g
->closing_branch
= &g
->nodes
[i
];
492 else if (GET_CODE (PATTERN (insn
)) == USE
)
499 g
->nodes
[i
].cuid
= i
;
500 g
->nodes
[i
].successors
= sbitmap_alloc (num_nodes
);
501 sbitmap_zero (g
->nodes
[i
].successors
);
502 g
->nodes
[i
].predecessors
= sbitmap_alloc (num_nodes
);
503 sbitmap_zero (g
->nodes
[i
].predecessors
);
504 g
->nodes
[i
].first_note
= (first_note
? first_note
: insn
);
505 g
->nodes
[i
++].insn
= insn
;
506 first_note
= NULL_RTX
;
509 if (!g
->closing_branch
)
510 abort (); /* Found no branch in DDG. */
512 /* Build the data dependency graph. */
513 build_intra_loop_deps (g
);
514 build_inter_loop_deps (g
, df
);
518 /* Free all the memory allocated for the DDG. */
527 for (i
= 0; i
< g
->num_nodes
; i
++)
529 ddg_edge_ptr e
= g
->nodes
[i
].out
;
533 ddg_edge_ptr next
= e
->next_out
;
538 sbitmap_free (g
->nodes
[i
].successors
);
539 sbitmap_free (g
->nodes
[i
].predecessors
);
541 if (g
->num_backarcs
> 0)
548 print_ddg_edge (FILE *dump_file
, ddg_edge_ptr e
)
563 fprintf (dump_file
, " [%d -(%c,%d,%d)-> %d] ", INSN_UID (e
->src
->insn
),
564 dep_c
, e
->latency
, e
->distance
, INSN_UID (e
->dest
->insn
));
567 /* Print the DDG nodes with there in/out edges to the dump file. */
569 print_ddg (FILE *dump_file
, ddg_ptr g
)
573 for (i
= 0; i
< g
->num_nodes
; i
++)
577 print_rtl_single (dump_file
, g
->nodes
[i
].insn
);
578 fprintf (dump_file
, "OUT ARCS: ");
579 for (e
= g
->nodes
[i
].out
; e
; e
= e
->next_out
)
580 print_ddg_edge (dump_file
, e
);
582 fprintf (dump_file
, "\nIN ARCS: ");
583 for (e
= g
->nodes
[i
].in
; e
; e
= e
->next_in
)
584 print_ddg_edge (dump_file
, e
);
586 fprintf (dump_file
, "\n");
590 /* Print the given DDG in VCG format. */
592 vcg_print_ddg (FILE *dump_file
, ddg_ptr g
)
596 fprintf (dump_file
, "graph: {\n");
597 for (src_cuid
= 0; src_cuid
< g
->num_nodes
; src_cuid
++)
600 int src_uid
= INSN_UID (g
->nodes
[src_cuid
].insn
);
602 fprintf (dump_file
, "node: {title: \"%d_%d\" info1: \"", src_cuid
, src_uid
);
603 print_rtl_single (dump_file
, g
->nodes
[src_cuid
].insn
);
604 fprintf (dump_file
, "\"}\n");
605 for (e
= g
->nodes
[src_cuid
].out
; e
; e
= e
->next_out
)
607 int dst_uid
= INSN_UID (e
->dest
->insn
);
608 int dst_cuid
= e
->dest
->cuid
;
610 /* Give the backarcs a different color. */
612 fprintf (dump_file
, "backedge: {color: red ");
614 fprintf (dump_file
, "edge: { ");
616 fprintf (dump_file
, "sourcename: \"%d_%d\" ", src_cuid
, src_uid
);
617 fprintf (dump_file
, "targetname: \"%d_%d\" ", dst_cuid
, dst_uid
);
618 fprintf (dump_file
, "label: \"%d_%d\"}\n", e
->latency
, e
->distance
);
621 fprintf (dump_file
, "}\n");
624 /* Create an edge and initialize it with given values. */
626 create_ddg_edge (ddg_node_ptr src
, ddg_node_ptr dest
,
627 dep_type t
, dep_data_type dt
, int l
, int d
)
629 ddg_edge_ptr e
= (ddg_edge_ptr
) xmalloc (sizeof (struct ddg_edge
));
637 e
->next_in
= e
->next_out
= NULL
;
642 /* Add the given edge to the in/out linked lists of the DDG nodes. */
644 add_edge_to_ddg (ddg_ptr g ATTRIBUTE_UNUSED
, ddg_edge_ptr e
)
646 ddg_node_ptr src
= e
->src
;
647 ddg_node_ptr dest
= e
->dest
;
649 if (!src
->successors
|| !dest
->predecessors
)
650 abort (); /* Should have allocated the sbitmaps. */
652 SET_BIT (src
->successors
, dest
->cuid
);
653 SET_BIT (dest
->predecessors
, src
->cuid
);
654 e
->next_in
= dest
->in
;
656 e
->next_out
= src
->out
;
662 /* Algorithm for computing the recurrence_length of an scc. We assume at
663 for now that cycles in the data dependence graph contain a single backarc.
664 This simplifies the algorithm, and can be generalized later. */
666 set_recurrence_length (ddg_scc_ptr scc
, ddg_ptr g
)
671 for (j
= 0; j
< scc
->num_backarcs
; j
++)
673 ddg_edge_ptr backarc
= scc
->backarcs
[j
];
675 int distance
= backarc
->distance
;
676 ddg_node_ptr src
= backarc
->dest
;
677 ddg_node_ptr dest
= backarc
->src
;
679 length
= longest_simple_path (g
, src
->cuid
, dest
->cuid
, scc
->nodes
);
682 /* fprintf (stderr, "Backarc not on simple cycle in SCC.\n"); */
685 length
+= backarc
->latency
;
686 result
= MAX (result
, (length
/ distance
));
688 scc
->recurrence_length
= result
;
691 /* Create a new SCC given the set of its nodes. Compute its recurrence_length
692 and mark edges that belong to this scc as IN_SCC. */
694 create_scc (ddg_ptr g
, sbitmap nodes
)
699 scc
= (ddg_scc_ptr
) xmalloc (sizeof (struct ddg_scc
));
700 scc
->backarcs
= NULL
;
701 scc
->num_backarcs
= 0;
702 scc
->nodes
= sbitmap_alloc (g
->num_nodes
);
703 sbitmap_copy (scc
->nodes
, nodes
);
705 /* Mark the backarcs that belong to this SCC. */
706 EXECUTE_IF_SET_IN_SBITMAP (nodes
, 0, u
,
709 ddg_node_ptr n
= &g
->nodes
[u
];
711 for (e
= n
->out
; e
; e
= e
->next_out
)
712 if (TEST_BIT (nodes
, e
->dest
->cuid
))
714 e
->aux
.count
= IN_SCC
;
716 add_backarc_to_scc (scc
, e
);
720 set_recurrence_length (scc
, g
);
724 /* Cleans the memory allocation of a given SCC. */
726 free_scc (ddg_scc_ptr scc
)
731 sbitmap_free (scc
->nodes
);
732 if (scc
->num_backarcs
> 0)
733 free (scc
->backarcs
);
738 /* Add a given edge known to be a backarc to the given DDG. */
740 add_backarc_to_ddg (ddg_ptr g
, ddg_edge_ptr e
)
742 int size
= (g
->num_backarcs
+ 1) * sizeof (ddg_edge_ptr
);
744 add_edge_to_ddg (g
, e
);
745 g
->backarcs
= (ddg_edge_ptr
*) xrealloc (g
->backarcs
, size
);
746 g
->backarcs
[g
->num_backarcs
++] = e
;
749 /* Add backarc to an SCC. */
751 add_backarc_to_scc (ddg_scc_ptr scc
, ddg_edge_ptr e
)
753 int size
= (scc
->num_backarcs
+ 1) * sizeof (ddg_edge_ptr
);
755 scc
->backarcs
= (ddg_edge_ptr
*) xrealloc (scc
->backarcs
, size
);
756 scc
->backarcs
[scc
->num_backarcs
++] = e
;
759 /* Add the given SCC to the DDG. */
761 add_scc_to_ddg (ddg_all_sccs_ptr g
, ddg_scc_ptr scc
)
763 int size
= (g
->num_sccs
+ 1) * sizeof (ddg_scc_ptr
);
765 g
->sccs
= (ddg_scc_ptr
*) xrealloc (g
->sccs
, size
);
766 g
->sccs
[g
->num_sccs
++] = scc
;
769 /* Given the instruction INSN return the node that represents it. */
771 get_node_of_insn (ddg_ptr g
, rtx insn
)
775 for (i
= 0; i
< g
->num_nodes
; i
++)
776 if (insn
== g
->nodes
[i
].insn
)
781 /* Given a set OPS of nodes in the DDG, find the set of their successors
782 which are not in OPS, and set their bits in SUCC. Bits corresponding to
783 OPS are cleared from SUCC. Leaves the other bits in SUCC unchanged. */
785 find_successors (sbitmap succ
, ddg_ptr g
, sbitmap ops
)
789 EXECUTE_IF_SET_IN_SBITMAP (ops
, 0, i
,
791 const sbitmap node_succ
= NODE_SUCCESSORS (&g
->nodes
[i
]);
792 sbitmap_a_or_b (succ
, succ
, node_succ
);
795 /* We want those that are not in ops. */
796 sbitmap_difference (succ
, succ
, ops
);
799 /* Given a set OPS of nodes in the DDG, find the set of their predecessors
800 which are not in OPS, and set their bits in PREDS. Bits corresponding to
801 OPS are cleared from PREDS. Leaves the other bits in PREDS unchanged. */
803 find_predecessors (sbitmap preds
, ddg_ptr g
, sbitmap ops
)
807 EXECUTE_IF_SET_IN_SBITMAP (ops
, 0, i
,
809 const sbitmap node_preds
= NODE_PREDECESSORS (&g
->nodes
[i
]);
810 sbitmap_a_or_b (preds
, preds
, node_preds
);
813 /* We want those that are not in ops. */
814 sbitmap_difference (preds
, preds
, ops
);
818 /* Compare function to be passed to qsort to order the backarcs in descending
821 compare_sccs (const void *s1
, const void *s2
)
823 int rec_l1
= (*(ddg_scc_ptr
*)s1
)->recurrence_length
;
824 int rec_l2
= (*(ddg_scc_ptr
*)s2
)->recurrence_length
;
825 return ((rec_l2
> rec_l1
) - (rec_l2
< rec_l1
));
829 /* Order the backarcs in descending recMII order using compare_sccs. */
831 order_sccs (ddg_all_sccs_ptr g
)
833 qsort (g
->sccs
, g
->num_sccs
, sizeof (ddg_scc_ptr
),
834 (int (*) (const void *, const void *)) compare_sccs
);
837 /* Perform the Strongly Connected Components decomposing algorithm on the
838 DDG and return DDG_ALL_SCCS structure that contains them. */
840 create_ddg_all_sccs (ddg_ptr g
)
843 int num_nodes
= g
->num_nodes
;
844 sbitmap from
= sbitmap_alloc (num_nodes
);
845 sbitmap to
= sbitmap_alloc (num_nodes
);
846 sbitmap scc_nodes
= sbitmap_alloc (num_nodes
);
847 ddg_all_sccs_ptr sccs
= (ddg_all_sccs_ptr
)
848 xmalloc (sizeof (struct ddg_all_sccs
));
854 for (i
= 0; i
< g
->num_backarcs
; i
++)
857 ddg_edge_ptr backarc
= g
->backarcs
[i
];
858 ddg_node_ptr src
= backarc
->src
;
859 ddg_node_ptr dest
= backarc
->dest
;
861 /* If the backarc already belongs to an SCC, continue. */
862 if (backarc
->aux
.count
== IN_SCC
)
867 SET_BIT (from
, dest
->cuid
);
868 SET_BIT (to
, src
->cuid
);
870 if (find_nodes_on_paths (scc_nodes
, g
, from
, to
))
872 scc
= create_scc (g
, scc_nodes
);
873 add_scc_to_ddg (sccs
, scc
);
879 sbitmap_free (scc_nodes
);
883 /* Frees the memory allocated for all SCCs of the DDG, but keeps the DDG. */
885 free_ddg_all_sccs (ddg_all_sccs_ptr all_sccs
)
892 for (i
= 0; i
< all_sccs
->num_sccs
; i
++)
893 free_scc (all_sccs
->sccs
[i
]);
899 /* Given FROM - a bitmap of source nodes - and TO - a bitmap of destination
900 nodes - find all nodes that lie on paths from FROM to TO (not excluding
901 nodes from FROM and TO). Return non zero if nodes exist. */
903 find_nodes_on_paths (sbitmap result
, ddg_ptr g
, sbitmap from
, sbitmap to
)
907 int num_nodes
= g
->num_nodes
;
908 sbitmap workset
= sbitmap_alloc (num_nodes
);
909 sbitmap reachable_from
= sbitmap_alloc (num_nodes
);
910 sbitmap reach_to
= sbitmap_alloc (num_nodes
);
911 sbitmap tmp
= sbitmap_alloc (num_nodes
);
913 sbitmap_copy (reachable_from
, from
);
914 sbitmap_copy (tmp
, from
);
920 sbitmap_copy (workset
, tmp
);
922 EXECUTE_IF_SET_IN_SBITMAP (workset
, 0, u
,
925 ddg_node_ptr u_node
= &g
->nodes
[u
];
927 for (e
= u_node
->out
; e
!= (ddg_edge_ptr
) 0; e
= e
->next_out
)
929 ddg_node_ptr v_node
= e
->dest
;
930 int v
= v_node
->cuid
;
932 if (!TEST_BIT (reachable_from
, v
))
934 SET_BIT (reachable_from
, v
);
942 sbitmap_copy (reach_to
, to
);
943 sbitmap_copy (tmp
, to
);
949 sbitmap_copy (workset
, tmp
);
951 EXECUTE_IF_SET_IN_SBITMAP (workset
, 0, u
,
954 ddg_node_ptr u_node
= &g
->nodes
[u
];
956 for (e
= u_node
->in
; e
!= (ddg_edge_ptr
) 0; e
= e
->next_in
)
958 ddg_node_ptr v_node
= e
->src
;
959 int v
= v_node
->cuid
;
961 if (!TEST_BIT (reach_to
, v
))
963 SET_BIT (reach_to
, v
);
971 answer
= sbitmap_a_and_b_cg (result
, reachable_from
, reach_to
);
972 sbitmap_free (workset
);
973 sbitmap_free (reachable_from
);
974 sbitmap_free (reach_to
);
980 /* Updates the counts of U_NODE's successors (that belong to NODES) to be
981 at-least as large as the count of U_NODE plus the latency between them.
982 Sets a bit in TMP for each successor whose count was changed (increased).
983 Returns nonzero if any count was changed. */
985 update_dist_to_successors (ddg_node_ptr u_node
, sbitmap nodes
, sbitmap tmp
)
990 for (e
= u_node
->out
; e
; e
= e
->next_out
)
992 ddg_node_ptr v_node
= e
->dest
;
993 int v
= v_node
->cuid
;
995 if (TEST_BIT (nodes
, v
)
996 && (e
->distance
== 0)
997 && (v_node
->aux
.count
< u_node
->aux
.count
+ e
->latency
))
999 v_node
->aux
.count
= u_node
->aux
.count
+ e
->latency
;
1008 /* Find the length of a longest path from SRC to DEST in G,
1009 going only through NODES, and disregarding backarcs. */
1011 longest_simple_path (struct ddg
* g
, int src
, int dest
, sbitmap nodes
)
1016 int num_nodes
= g
->num_nodes
;
1017 sbitmap workset
= sbitmap_alloc (num_nodes
);
1018 sbitmap tmp
= sbitmap_alloc (num_nodes
);
1021 /* Data will hold the distance of the longest path found so far from
1022 src to each node. Initialize to -1 = less than minimum. */
1023 for (i
= 0; i
< g
->num_nodes
; i
++)
1024 g
->nodes
[i
].aux
.count
= -1;
1025 g
->nodes
[src
].aux
.count
= 0;
1033 sbitmap_copy (workset
, tmp
);
1035 EXECUTE_IF_SET_IN_SBITMAP (workset
, 0, u
,
1037 ddg_node_ptr u_node
= &g
->nodes
[u
];
1039 change
|= update_dist_to_successors (u_node
, nodes
, tmp
);
1042 result
= g
->nodes
[dest
].aux
.count
;
1043 sbitmap_free (workset
);