1 /* DDG - Data Dependence Graph implementation.
2 Copyright (C) 2004, 2005, 2006, 2007
3 Free Software Foundation, Inc.
4 Contributed by Ayal Zaks and Mustafa Hagog <zaks,mustafa@il.ibm.com>
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
25 #include "coretypes.h"
30 #include "hard-reg-set.h"
34 #include "insn-config.h"
35 #include "insn-attr.h"
38 #include "sched-int.h"
40 #include "cfglayout.h"
47 /* A flag indicating that a ddg edge belongs to an SCC or not. */
48 enum edge_flag
{NOT_IN_SCC
= 0, IN_SCC
};
50 /* Forward declarations. */
51 static void add_backarc_to_ddg (ddg_ptr
, ddg_edge_ptr
);
52 static void add_backarc_to_scc (ddg_scc_ptr
, ddg_edge_ptr
);
53 static void add_scc_to_ddg (ddg_all_sccs_ptr
, ddg_scc_ptr
);
54 static void create_ddg_dep_from_intra_loop_link (ddg_ptr
, ddg_node_ptr
,
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
, const_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_dep_from_intra_loop_link (ddg_ptr g
, ddg_node_ptr src_node
,
150 ddg_node_ptr dest_node
, dep_t link
)
153 int latency
, distance
= 0;
154 dep_type t
= TRUE_DEP
;
155 dep_data_type dt
= (mem_access_insn_p (src_node
->insn
)
156 && mem_access_insn_p (dest_node
->insn
) ? MEM_DEP
158 gcc_assert (src_node
->cuid
< dest_node
->cuid
);
161 /* Note: REG_DEP_ANTI applies to MEM ANTI_DEP as well!! */
162 if (DEP_KIND (link
) == REG_DEP_ANTI
)
164 else if (DEP_KIND (link
) == REG_DEP_OUTPUT
)
167 /* We currently choose not to create certain anti-deps edges and
168 compensate for that by generating reg-moves based on the life-range
169 analysis. The anti-deps that will be deleted are the ones which
170 have true-deps edges in the opposite direction (in other words
171 the kernel has only one def of the relevant register). TODO:
172 support the removal of all anti-deps edges, i.e. including those
173 whose register has multiple defs in the loop. */
174 if (flag_modulo_sched_allow_regmoves
&& (t
== ANTI_DEP
&& dt
== REG_DEP
))
178 set
= single_set (dest_node
->insn
);
181 int regno
= REGNO (SET_DEST (set
));
182 struct df_ref
*first_def
=
183 df_bb_regno_first_def_find (g
->bb
, regno
);
184 struct df_rd_bb_info
*bb_info
= DF_RD_BB_INFO (g
->bb
);
186 if (bitmap_bit_p (bb_info
->gen
, first_def
->id
))
191 latency
= dep_cost (link
);
192 e
= create_ddg_edge (src_node
, dest_node
, t
, dt
, latency
, distance
);
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 enum reg_note dep_kind
;
204 struct _dep _dep
, *dep
= &_dep
;
207 dep_kind
= REG_DEP_ANTI
;
208 else if (d_t
== OUTPUT_DEP
)
209 dep_kind
= REG_DEP_OUTPUT
;
212 gcc_assert (d_t
== TRUE_DEP
);
214 dep_kind
= REG_DEP_TRUE
;
217 init_dep (dep
, from
->insn
, to
->insn
, dep_kind
);
221 e
= create_ddg_edge (from
, to
, d_t
, d_dt
, l
, distance
);
223 add_backarc_to_ddg (g
, e
);
225 add_edge_to_ddg (g
, e
);
229 /* Given a downwards exposed register def LAST_DEF (which is the last
230 definition of that register in the bb), add inter-loop true dependences
231 to all its uses in the next iteration, an output dependence to the
232 first def of the same register (possibly itself) in the next iteration
233 and anti-dependences from its uses in the current iteration to the
234 first definition in the next iteration. */
236 add_cross_iteration_register_deps (ddg_ptr g
, struct df_ref
*last_def
)
238 int regno
= DF_REF_REGNO (last_def
);
239 struct df_link
*r_use
;
240 int has_use_in_bb_p
= false;
241 rtx def_insn
= DF_REF_INSN (last_def
);
242 ddg_node_ptr last_def_node
= get_node_of_insn (g
, def_insn
);
243 ddg_node_ptr use_node
;
244 #ifdef ENABLE_CHECKING
245 struct df_rd_bb_info
*bb_info
= DF_RD_BB_INFO (g
->bb
);
247 struct df_ref
*first_def
= df_bb_regno_first_def_find (g
->bb
, regno
);
249 gcc_assert (last_def_node
);
250 gcc_assert (first_def
);
252 #ifdef ENABLE_CHECKING
253 if (last_def
->id
!= first_def
->id
)
254 gcc_assert (!bitmap_bit_p (bb_info
->gen
, first_def
->id
));
257 /* Create inter-loop true dependences and anti dependences. */
258 for (r_use
= DF_REF_CHAIN (last_def
); r_use
!= NULL
; r_use
= r_use
->next
)
260 rtx use_insn
= DF_REF_INSN (r_use
->ref
);
262 if (BLOCK_FOR_INSN (use_insn
) != g
->bb
)
265 /* ??? Do not handle uses with DF_REF_IN_NOTE notes. */
266 use_node
= get_node_of_insn (g
, use_insn
);
267 gcc_assert (use_node
);
268 has_use_in_bb_p
= true;
269 if (use_node
->cuid
<= last_def_node
->cuid
)
271 /* Add true deps from last_def to it's uses in the next
272 iteration. Any such upwards exposed use appears before
274 create_ddg_dep_no_link (g
, last_def_node
, use_node
, TRUE_DEP
,
279 /* Add anti deps from last_def's uses in the current iteration
280 to the first def in the next iteration. We do not add ANTI
281 dep when there is an intra-loop TRUE dep in the opposite
282 direction, but use regmoves to fix such disregarded ANTI
283 deps when broken. If the first_def reaches the USE then
284 there is such a dep. */
285 ddg_node_ptr first_def_node
= get_node_of_insn (g
,
288 gcc_assert (first_def_node
);
290 if (last_def
->id
!= first_def
->id
291 || !flag_modulo_sched_allow_regmoves
)
292 create_ddg_dep_no_link (g
, use_node
, first_def_node
, ANTI_DEP
,
297 /* Create an inter-loop output dependence between LAST_DEF (which is the
298 last def in its block, being downwards exposed) and the first def in
299 its block. Avoid creating a self output dependence. Avoid creating
300 an output dependence if there is a dependence path between the two
301 defs starting with a true dependence to a use which can be in the
302 next iteration; followed by an anti dependence of that use to the
303 first def (i.e. if there is a use between the two defs.) */
304 if (!has_use_in_bb_p
)
306 ddg_node_ptr dest_node
;
308 if (last_def
->id
== first_def
->id
)
311 dest_node
= get_node_of_insn (g
, first_def
->insn
);
312 gcc_assert (dest_node
);
313 create_ddg_dep_no_link (g
, last_def_node
, dest_node
,
314 OUTPUT_DEP
, REG_DEP
, 1);
317 /* Build inter-loop dependencies, by looking at DF analysis backwards. */
319 build_inter_loop_deps (ddg_ptr g
)
322 struct df_rd_bb_info
*rd_bb_info
;
325 rd_bb_info
= DF_RD_BB_INFO (g
->bb
);
327 /* Find inter-loop register output, true and anti deps. */
328 EXECUTE_IF_SET_IN_BITMAP (rd_bb_info
->gen
, 0, rd_num
, bi
)
330 struct df_ref
*rd
= DF_DEFS_GET (rd_num
);
332 add_cross_iteration_register_deps (g
, rd
);
337 /* Given two nodes, analyze their RTL insns and add inter-loop mem deps
340 add_inter_loop_mem_dep (ddg_ptr g
, ddg_node_ptr from
, ddg_node_ptr to
)
342 if (mem_write_insn_p (from
->insn
))
344 if (mem_read_insn_p (to
->insn
))
345 create_ddg_dep_no_link (g
, from
, to
, TRUE_DEP
, MEM_DEP
, 1);
346 else if (from
->cuid
!= to
->cuid
)
347 create_ddg_dep_no_link (g
, from
, to
, OUTPUT_DEP
, MEM_DEP
, 1);
351 if (mem_read_insn_p (to
->insn
))
353 else if (from
->cuid
!= to
->cuid
)
355 create_ddg_dep_no_link (g
, from
, to
, ANTI_DEP
, MEM_DEP
, 1);
356 create_ddg_dep_no_link (g
, to
, from
, TRUE_DEP
, MEM_DEP
, 1);
362 /* Perform intra-block Data Dependency analysis and connect the nodes in
363 the DDG. We assume the loop has a single basic block. */
365 build_intra_loop_deps (ddg_ptr g
)
368 /* Hold the dependency analysis state during dependency calculations. */
369 struct deps tmp_deps
;
373 /* Build the dependence information, using the sched_analyze function. */
375 init_deps (&tmp_deps
);
377 /* Do the intra-block data dependence analysis for the given block. */
378 get_ebb_head_tail (g
->bb
, g
->bb
, &head
, &tail
);
379 sched_analyze (&tmp_deps
, head
, tail
);
381 /* Build intra-loop data dependencies using the scheduler dependency
383 for (i
= 0; i
< g
->num_nodes
; i
++)
385 ddg_node_ptr dest_node
= &g
->nodes
[i
];
387 if (! INSN_P (dest_node
->insn
))
390 FOR_EACH_DEP_LINK (link
, INSN_BACK_DEPS (dest_node
->insn
))
392 dep_t dep
= DEP_LINK_DEP (link
);
393 ddg_node_ptr src_node
= get_node_of_insn (g
, DEP_PRO (dep
));
399 create_ddg_dep_from_intra_loop_link (g
, src_node
, dest_node
, dep
);
402 /* If this insn modifies memory, add an edge to all insns that access
404 if (mem_access_insn_p (dest_node
->insn
))
408 for (j
= 0; j
<= i
; j
++)
410 ddg_node_ptr j_node
= &g
->nodes
[j
];
411 if (mem_access_insn_p (j_node
->insn
))
412 /* Don't bother calculating inter-loop dep if an intra-loop dep
414 if (! TEST_BIT (dest_node
->successors
, j
))
415 add_inter_loop_mem_dep (g
, dest_node
, j_node
);
420 /* Free the INSN_LISTs. */
421 finish_deps_global ();
422 free_deps (&tmp_deps
);
426 /* Given a basic block, create its DDG and return a pointer to a variable
427 of ddg type that represents it.
428 Initialize the ddg structure fields to the appropriate values. */
430 create_ddg (basic_block bb
, int closing_branch_deps
)
433 rtx insn
, first_note
;
437 g
= (ddg_ptr
) xcalloc (1, sizeof (struct ddg
));
440 g
->closing_branch_deps
= closing_branch_deps
;
442 /* Count the number of insns in the BB. */
443 for (insn
= BB_HEAD (bb
); insn
!= NEXT_INSN (BB_END (bb
));
444 insn
= NEXT_INSN (insn
))
446 if (! INSN_P (insn
) || GET_CODE (PATTERN (insn
)) == USE
)
449 if (mem_read_insn_p (insn
))
451 if (mem_write_insn_p (insn
))
456 /* There is nothing to do for this BB. */
463 /* Allocate the nodes array, and initialize the nodes. */
464 g
->num_nodes
= num_nodes
;
465 g
->nodes
= (ddg_node_ptr
) xcalloc (num_nodes
, sizeof (struct ddg_node
));
466 g
->closing_branch
= NULL
;
468 first_note
= NULL_RTX
;
469 for (insn
= BB_HEAD (bb
); insn
!= NEXT_INSN (BB_END (bb
));
470 insn
= NEXT_INSN (insn
))
474 if (! first_note
&& NOTE_P (insn
)
475 && NOTE_KIND (insn
) != NOTE_INSN_BASIC_BLOCK
)
481 gcc_assert (!g
->closing_branch
);
482 g
->closing_branch
= &g
->nodes
[i
];
484 else if (GET_CODE (PATTERN (insn
)) == USE
)
491 g
->nodes
[i
].cuid
= i
;
492 g
->nodes
[i
].successors
= sbitmap_alloc (num_nodes
);
493 sbitmap_zero (g
->nodes
[i
].successors
);
494 g
->nodes
[i
].predecessors
= sbitmap_alloc (num_nodes
);
495 sbitmap_zero (g
->nodes
[i
].predecessors
);
496 g
->nodes
[i
].first_note
= (first_note
? first_note
: insn
);
497 g
->nodes
[i
++].insn
= insn
;
498 first_note
= NULL_RTX
;
501 /* We must have found a branch in DDG. */
502 gcc_assert (g
->closing_branch
);
505 /* Build the data dependency graph. */
506 build_intra_loop_deps (g
);
507 build_inter_loop_deps (g
);
511 /* Free all the memory allocated for the DDG. */
520 for (i
= 0; i
< g
->num_nodes
; i
++)
522 ddg_edge_ptr e
= g
->nodes
[i
].out
;
526 ddg_edge_ptr next
= e
->next_out
;
531 sbitmap_free (g
->nodes
[i
].successors
);
532 sbitmap_free (g
->nodes
[i
].predecessors
);
534 if (g
->num_backarcs
> 0)
541 print_ddg_edge (FILE *file
, ddg_edge_ptr e
)
557 fprintf (file
, " [%d -(%c,%d,%d)-> %d] ", INSN_UID (e
->src
->insn
),
558 dep_c
, e
->latency
, e
->distance
, INSN_UID (e
->dest
->insn
));
561 /* Print the DDG nodes with there in/out edges to the dump file. */
563 print_ddg (FILE *file
, ddg_ptr g
)
567 for (i
= 0; i
< g
->num_nodes
; i
++)
571 print_rtl_single (file
, g
->nodes
[i
].insn
);
572 fprintf (file
, "OUT ARCS: ");
573 for (e
= g
->nodes
[i
].out
; e
; e
= e
->next_out
)
574 print_ddg_edge (file
, e
);
576 fprintf (file
, "\nIN ARCS: ");
577 for (e
= g
->nodes
[i
].in
; e
; e
= e
->next_in
)
578 print_ddg_edge (file
, e
);
580 fprintf (file
, "\n");
584 /* Print the given DDG in VCG format. */
586 vcg_print_ddg (FILE *file
, ddg_ptr g
)
590 fprintf (file
, "graph: {\n");
591 for (src_cuid
= 0; src_cuid
< g
->num_nodes
; src_cuid
++)
594 int src_uid
= INSN_UID (g
->nodes
[src_cuid
].insn
);
596 fprintf (file
, "node: {title: \"%d_%d\" info1: \"", src_cuid
, src_uid
);
597 print_rtl_single (file
, g
->nodes
[src_cuid
].insn
);
598 fprintf (file
, "\"}\n");
599 for (e
= g
->nodes
[src_cuid
].out
; e
; e
= e
->next_out
)
601 int dst_uid
= INSN_UID (e
->dest
->insn
);
602 int dst_cuid
= e
->dest
->cuid
;
604 /* Give the backarcs a different color. */
606 fprintf (file
, "backedge: {color: red ");
608 fprintf (file
, "edge: { ");
610 fprintf (file
, "sourcename: \"%d_%d\" ", src_cuid
, src_uid
);
611 fprintf (file
, "targetname: \"%d_%d\" ", dst_cuid
, dst_uid
);
612 fprintf (file
, "label: \"%d_%d\"}\n", e
->latency
, e
->distance
);
615 fprintf (file
, "}\n");
618 /* Dump the sccs in SCCS. */
620 print_sccs (FILE *file
, ddg_all_sccs_ptr sccs
, ddg_ptr g
)
623 sbitmap_iterator sbi
;
629 fprintf (file
, "\n;; Number of SCC nodes - %d\n", sccs
->num_sccs
);
630 for (i
= 0; i
< sccs
->num_sccs
; i
++)
632 fprintf (file
, "SCC number: %d\n", i
);
633 EXECUTE_IF_SET_IN_SBITMAP (sccs
->sccs
[i
]->nodes
, 0, u
, sbi
)
635 fprintf (file
, "insn num %d\n", u
);
636 print_rtl_single (file
, g
->nodes
[u
].insn
);
639 fprintf (file
, "\n");
642 /* Create an edge and initialize it with given values. */
644 create_ddg_edge (ddg_node_ptr src
, ddg_node_ptr dest
,
645 dep_type t
, dep_data_type dt
, int l
, int d
)
647 ddg_edge_ptr e
= (ddg_edge_ptr
) xmalloc (sizeof (struct ddg_edge
));
655 e
->next_in
= e
->next_out
= NULL
;
660 /* Add the given edge to the in/out linked lists of the DDG nodes. */
662 add_edge_to_ddg (ddg_ptr g ATTRIBUTE_UNUSED
, ddg_edge_ptr e
)
664 ddg_node_ptr src
= e
->src
;
665 ddg_node_ptr dest
= e
->dest
;
667 /* Should have allocated the sbitmaps. */
668 gcc_assert (src
->successors
&& dest
->predecessors
);
670 SET_BIT (src
->successors
, dest
->cuid
);
671 SET_BIT (dest
->predecessors
, src
->cuid
);
672 e
->next_in
= dest
->in
;
674 e
->next_out
= src
->out
;
680 /* Algorithm for computing the recurrence_length of an scc. We assume at
681 for now that cycles in the data dependence graph contain a single backarc.
682 This simplifies the algorithm, and can be generalized later. */
684 set_recurrence_length (ddg_scc_ptr scc
, ddg_ptr g
)
689 for (j
= 0; j
< scc
->num_backarcs
; j
++)
691 ddg_edge_ptr backarc
= scc
->backarcs
[j
];
693 int distance
= backarc
->distance
;
694 ddg_node_ptr src
= backarc
->dest
;
695 ddg_node_ptr dest
= backarc
->src
;
697 length
= longest_simple_path (g
, src
->cuid
, dest
->cuid
, scc
->nodes
);
700 /* fprintf (stderr, "Backarc not on simple cycle in SCC.\n"); */
703 length
+= backarc
->latency
;
704 result
= MAX (result
, (length
/ distance
));
706 scc
->recurrence_length
= result
;
709 /* Create a new SCC given the set of its nodes. Compute its recurrence_length
710 and mark edges that belong to this scc as IN_SCC. */
712 create_scc (ddg_ptr g
, sbitmap nodes
)
716 sbitmap_iterator sbi
;
718 scc
= (ddg_scc_ptr
) xmalloc (sizeof (struct ddg_scc
));
719 scc
->backarcs
= NULL
;
720 scc
->num_backarcs
= 0;
721 scc
->nodes
= sbitmap_alloc (g
->num_nodes
);
722 sbitmap_copy (scc
->nodes
, nodes
);
724 /* Mark the backarcs that belong to this SCC. */
725 EXECUTE_IF_SET_IN_SBITMAP (nodes
, 0, u
, sbi
)
728 ddg_node_ptr n
= &g
->nodes
[u
];
730 for (e
= n
->out
; e
; e
= e
->next_out
)
731 if (TEST_BIT (nodes
, e
->dest
->cuid
))
733 e
->aux
.count
= IN_SCC
;
735 add_backarc_to_scc (scc
, e
);
739 set_recurrence_length (scc
, g
);
743 /* Cleans the memory allocation of a given SCC. */
745 free_scc (ddg_scc_ptr scc
)
750 sbitmap_free (scc
->nodes
);
751 if (scc
->num_backarcs
> 0)
752 free (scc
->backarcs
);
757 /* Add a given edge known to be a backarc to the given DDG. */
759 add_backarc_to_ddg (ddg_ptr g
, ddg_edge_ptr e
)
761 int size
= (g
->num_backarcs
+ 1) * sizeof (ddg_edge_ptr
);
763 add_edge_to_ddg (g
, e
);
764 g
->backarcs
= (ddg_edge_ptr
*) xrealloc (g
->backarcs
, size
);
765 g
->backarcs
[g
->num_backarcs
++] = e
;
768 /* Add backarc to an SCC. */
770 add_backarc_to_scc (ddg_scc_ptr scc
, ddg_edge_ptr e
)
772 int size
= (scc
->num_backarcs
+ 1) * sizeof (ddg_edge_ptr
);
774 scc
->backarcs
= (ddg_edge_ptr
*) xrealloc (scc
->backarcs
, size
);
775 scc
->backarcs
[scc
->num_backarcs
++] = e
;
778 /* Add the given SCC to the DDG. */
780 add_scc_to_ddg (ddg_all_sccs_ptr g
, ddg_scc_ptr scc
)
782 int size
= (g
->num_sccs
+ 1) * sizeof (ddg_scc_ptr
);
784 g
->sccs
= (ddg_scc_ptr
*) xrealloc (g
->sccs
, size
);
785 g
->sccs
[g
->num_sccs
++] = scc
;
788 /* Given the instruction INSN return the node that represents it. */
790 get_node_of_insn (ddg_ptr g
, rtx insn
)
794 for (i
= 0; i
< g
->num_nodes
; i
++)
795 if (insn
== g
->nodes
[i
].insn
)
800 /* Given a set OPS of nodes in the DDG, find the set of their successors
801 which are not in OPS, and set their bits in SUCC. Bits corresponding to
802 OPS are cleared from SUCC. Leaves the other bits in SUCC unchanged. */
804 find_successors (sbitmap succ
, ddg_ptr g
, sbitmap ops
)
807 sbitmap_iterator sbi
;
809 EXECUTE_IF_SET_IN_SBITMAP (ops
, 0, i
, sbi
)
811 const sbitmap node_succ
= NODE_SUCCESSORS (&g
->nodes
[i
]);
812 sbitmap_a_or_b (succ
, succ
, node_succ
);
815 /* We want those that are not in ops. */
816 sbitmap_difference (succ
, succ
, ops
);
819 /* Given a set OPS of nodes in the DDG, find the set of their predecessors
820 which are not in OPS, and set their bits in PREDS. Bits corresponding to
821 OPS are cleared from PREDS. Leaves the other bits in PREDS unchanged. */
823 find_predecessors (sbitmap preds
, ddg_ptr g
, sbitmap ops
)
826 sbitmap_iterator sbi
;
828 EXECUTE_IF_SET_IN_SBITMAP (ops
, 0, i
, sbi
)
830 const sbitmap node_preds
= NODE_PREDECESSORS (&g
->nodes
[i
]);
831 sbitmap_a_or_b (preds
, preds
, node_preds
);
834 /* We want those that are not in ops. */
835 sbitmap_difference (preds
, preds
, ops
);
839 /* Compare function to be passed to qsort to order the backarcs in descending
842 compare_sccs (const void *s1
, const void *s2
)
844 const int rec_l1
= (*(const ddg_scc_ptr
*)s1
)->recurrence_length
;
845 const int rec_l2
= (*(const ddg_scc_ptr
*)s2
)->recurrence_length
;
846 return ((rec_l2
> rec_l1
) - (rec_l2
< rec_l1
));
850 /* Order the backarcs in descending recMII order using compare_sccs. */
852 order_sccs (ddg_all_sccs_ptr g
)
854 qsort (g
->sccs
, g
->num_sccs
, sizeof (ddg_scc_ptr
),
855 (int (*) (const void *, const void *)) compare_sccs
);
858 #ifdef ENABLE_CHECKING
859 /* Check that every node in SCCS belongs to exactly one strongly connected
860 component and that no element of SCCS is empty. */
862 check_sccs (ddg_all_sccs_ptr sccs
, int num_nodes
)
865 sbitmap tmp
= sbitmap_alloc (num_nodes
);
868 for (i
= 0; i
< sccs
->num_sccs
; i
++)
870 gcc_assert (!sbitmap_empty_p (sccs
->sccs
[i
]->nodes
));
871 /* Verify that every node in sccs is in exactly one strongly
872 connected component. */
873 gcc_assert (!sbitmap_any_common_bits (tmp
, sccs
->sccs
[i
]->nodes
));
874 sbitmap_a_or_b (tmp
, tmp
, sccs
->sccs
[i
]->nodes
);
880 /* Perform the Strongly Connected Components decomposing algorithm on the
881 DDG and return DDG_ALL_SCCS structure that contains them. */
883 create_ddg_all_sccs (ddg_ptr g
)
886 int num_nodes
= g
->num_nodes
;
887 sbitmap from
= sbitmap_alloc (num_nodes
);
888 sbitmap to
= sbitmap_alloc (num_nodes
);
889 sbitmap scc_nodes
= sbitmap_alloc (num_nodes
);
890 ddg_all_sccs_ptr sccs
= (ddg_all_sccs_ptr
)
891 xmalloc (sizeof (struct ddg_all_sccs
));
897 for (i
= 0; i
< g
->num_backarcs
; i
++)
900 ddg_edge_ptr backarc
= g
->backarcs
[i
];
901 ddg_node_ptr src
= backarc
->src
;
902 ddg_node_ptr dest
= backarc
->dest
;
904 /* If the backarc already belongs to an SCC, continue. */
905 if (backarc
->aux
.count
== IN_SCC
)
908 sbitmap_zero (scc_nodes
);
911 SET_BIT (from
, dest
->cuid
);
912 SET_BIT (to
, src
->cuid
);
914 if (find_nodes_on_paths (scc_nodes
, g
, from
, to
))
916 scc
= create_scc (g
, scc_nodes
);
917 add_scc_to_ddg (sccs
, scc
);
923 sbitmap_free (scc_nodes
);
924 #ifdef ENABLE_CHECKING
925 check_sccs (sccs
, num_nodes
);
930 /* Frees the memory allocated for all SCCs of the DDG, but keeps the DDG. */
932 free_ddg_all_sccs (ddg_all_sccs_ptr all_sccs
)
939 for (i
= 0; i
< all_sccs
->num_sccs
; i
++)
940 free_scc (all_sccs
->sccs
[i
]);
946 /* Given FROM - a bitmap of source nodes - and TO - a bitmap of destination
947 nodes - find all nodes that lie on paths from FROM to TO (not excluding
948 nodes from FROM and TO). Return nonzero if nodes exist. */
950 find_nodes_on_paths (sbitmap result
, ddg_ptr g
, sbitmap from
, sbitmap to
)
955 int num_nodes
= g
->num_nodes
;
956 sbitmap_iterator sbi
;
958 sbitmap workset
= sbitmap_alloc (num_nodes
);
959 sbitmap reachable_from
= sbitmap_alloc (num_nodes
);
960 sbitmap reach_to
= sbitmap_alloc (num_nodes
);
961 sbitmap tmp
= sbitmap_alloc (num_nodes
);
963 sbitmap_copy (reachable_from
, from
);
964 sbitmap_copy (tmp
, from
);
970 sbitmap_copy (workset
, tmp
);
972 EXECUTE_IF_SET_IN_SBITMAP (workset
, 0, u
, sbi
)
975 ddg_node_ptr u_node
= &g
->nodes
[u
];
977 for (e
= u_node
->out
; e
!= (ddg_edge_ptr
) 0; e
= e
->next_out
)
979 ddg_node_ptr v_node
= e
->dest
;
980 int v
= v_node
->cuid
;
982 if (!TEST_BIT (reachable_from
, v
))
984 SET_BIT (reachable_from
, v
);
992 sbitmap_copy (reach_to
, to
);
993 sbitmap_copy (tmp
, to
);
999 sbitmap_copy (workset
, tmp
);
1001 EXECUTE_IF_SET_IN_SBITMAP (workset
, 0, u
, sbi
)
1004 ddg_node_ptr u_node
= &g
->nodes
[u
];
1006 for (e
= u_node
->in
; e
!= (ddg_edge_ptr
) 0; e
= e
->next_in
)
1008 ddg_node_ptr v_node
= e
->src
;
1009 int v
= v_node
->cuid
;
1011 if (!TEST_BIT (reach_to
, v
))
1013 SET_BIT (reach_to
, v
);
1021 answer
= sbitmap_a_and_b_cg (result
, reachable_from
, reach_to
);
1022 sbitmap_free (workset
);
1023 sbitmap_free (reachable_from
);
1024 sbitmap_free (reach_to
);
1030 /* Updates the counts of U_NODE's successors (that belong to NODES) to be
1031 at-least as large as the count of U_NODE plus the latency between them.
1032 Sets a bit in TMP for each successor whose count was changed (increased).
1033 Returns nonzero if any count was changed. */
1035 update_dist_to_successors (ddg_node_ptr u_node
, sbitmap nodes
, sbitmap tmp
)
1040 for (e
= u_node
->out
; e
; e
= e
->next_out
)
1042 ddg_node_ptr v_node
= e
->dest
;
1043 int v
= v_node
->cuid
;
1045 if (TEST_BIT (nodes
, v
)
1046 && (e
->distance
== 0)
1047 && (v_node
->aux
.count
< u_node
->aux
.count
+ e
->latency
))
1049 v_node
->aux
.count
= u_node
->aux
.count
+ e
->latency
;
1058 /* Find the length of a longest path from SRC to DEST in G,
1059 going only through NODES, and disregarding backarcs. */
1061 longest_simple_path (struct ddg
* g
, int src
, int dest
, sbitmap nodes
)
1067 int num_nodes
= g
->num_nodes
;
1068 sbitmap workset
= sbitmap_alloc (num_nodes
);
1069 sbitmap tmp
= sbitmap_alloc (num_nodes
);
1072 /* Data will hold the distance of the longest path found so far from
1073 src to each node. Initialize to -1 = less than minimum. */
1074 for (i
= 0; i
< g
->num_nodes
; i
++)
1075 g
->nodes
[i
].aux
.count
= -1;
1076 g
->nodes
[src
].aux
.count
= 0;
1083 sbitmap_iterator sbi
;
1086 sbitmap_copy (workset
, tmp
);
1088 EXECUTE_IF_SET_IN_SBITMAP (workset
, 0, u
, sbi
)
1090 ddg_node_ptr u_node
= &g
->nodes
[u
];
1092 change
|= update_dist_to_successors (u_node
, nodes
, tmp
);
1095 result
= g
->nodes
[dest
].aux
.count
;
1096 sbitmap_free (workset
);