1 /* DDG - Data Dependence Graph implementation.
2 Copyright (C) 2004-2015 Free Software Foundation, Inc.
3 Contributed by Ayal Zaks and Mustafa Hagog <zaks,mustafa@il.ibm.com>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
24 #include "coretypes.h"
29 #include "diagnostic-core.h"
33 #include "insn-config.h"
34 #include "insn-attr.h"
37 #include "sched-int.h"
52 #ifdef INSN_SCHEDULING
54 /* A flag indicating that a ddg edge belongs to an SCC or not. */
55 enum edge_flag
{NOT_IN_SCC
= 0, IN_SCC
};
57 /* Forward declarations. */
58 static void add_backarc_to_ddg (ddg_ptr
, ddg_edge_ptr
);
59 static void add_backarc_to_scc (ddg_scc_ptr
, ddg_edge_ptr
);
60 static void add_scc_to_ddg (ddg_all_sccs_ptr
, ddg_scc_ptr
);
61 static void create_ddg_dep_from_intra_loop_link (ddg_ptr
, ddg_node_ptr
,
63 static void create_ddg_dep_no_link (ddg_ptr
, ddg_node_ptr
, ddg_node_ptr
,
64 dep_type
, dep_data_type
, int);
65 static ddg_edge_ptr
create_ddg_edge (ddg_node_ptr
, ddg_node_ptr
, dep_type
,
66 dep_data_type
, int, int);
67 static void add_edge_to_ddg (ddg_ptr g
, ddg_edge_ptr
);
69 /* Auxiliary variable for mem_read_insn_p/mem_write_insn_p. */
70 static bool mem_ref_p
;
72 /* Auxiliary function for mem_read_insn_p. */
74 mark_mem_use (rtx
*x
, void *)
76 subrtx_iterator::array_type array
;
77 FOR_EACH_SUBRTX (iter
, array
, *x
, NONCONST
)
85 /* Returns nonzero if INSN reads from memory. */
87 mem_read_insn_p (rtx_insn
*insn
)
90 note_uses (&PATTERN (insn
), mark_mem_use
, NULL
);
95 mark_mem_store (rtx loc
, const_rtx setter ATTRIBUTE_UNUSED
, void *data ATTRIBUTE_UNUSED
)
101 /* Returns nonzero if INSN writes to memory. */
103 mem_write_insn_p (rtx_insn
*insn
)
106 note_stores (PATTERN (insn
), mark_mem_store
, NULL
);
110 /* Returns nonzero if X has access to memory. */
112 rtx_mem_access_p (rtx x
)
125 fmt
= GET_RTX_FORMAT (code
);
126 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
130 if (rtx_mem_access_p (XEXP (x
, i
)))
133 else if (fmt
[i
] == 'E')
134 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
136 if (rtx_mem_access_p (XVECEXP (x
, i
, j
)))
143 /* Returns nonzero if INSN reads to or writes from memory. */
145 mem_access_insn_p (rtx_insn
*insn
)
147 return rtx_mem_access_p (PATTERN (insn
));
150 /* Return true if DEF_INSN contains address being auto-inc or auto-dec
151 which is used in USE_INSN. Otherwise return false. The result is
152 being used to decide whether to remove the edge between def_insn and
153 use_insn when -fmodulo-sched-allow-regmoves is set. This function
154 doesn't need to consider the specific address register; no reg_moves
155 will be allowed for any life range defined by def_insn and used
156 by use_insn, if use_insn uses an address register auto-inc'ed by
159 autoinc_var_is_used_p (rtx_insn
*def_insn
, rtx_insn
*use_insn
)
163 for (note
= REG_NOTES (def_insn
); note
; note
= XEXP (note
, 1))
164 if (REG_NOTE_KIND (note
) == REG_INC
165 && reg_referenced_p (XEXP (note
, 0), PATTERN (use_insn
)))
171 /* Return true if one of the definitions in INSN has MODE_CC. Otherwise
174 def_has_ccmode_p (rtx_insn
*insn
)
178 FOR_EACH_INSN_DEF (def
, insn
)
180 machine_mode mode
= GET_MODE (DF_REF_REG (def
));
182 if (GET_MODE_CLASS (mode
) == MODE_CC
)
189 /* Computes the dependence parameters (latency, distance etc.), creates
190 a ddg_edge and adds it to the given DDG. */
192 create_ddg_dep_from_intra_loop_link (ddg_ptr g
, ddg_node_ptr src_node
,
193 ddg_node_ptr dest_node
, dep_t link
)
196 int latency
, distance
= 0;
197 dep_type t
= TRUE_DEP
;
198 dep_data_type dt
= (mem_access_insn_p (src_node
->insn
)
199 && mem_access_insn_p (dest_node
->insn
) ? MEM_DEP
201 gcc_assert (src_node
->cuid
< dest_node
->cuid
);
204 /* Note: REG_DEP_ANTI applies to MEM ANTI_DEP as well!! */
205 if (DEP_TYPE (link
) == REG_DEP_ANTI
)
207 else if (DEP_TYPE (link
) == REG_DEP_OUTPUT
)
210 gcc_assert (!DEBUG_INSN_P (dest_node
->insn
) || t
== ANTI_DEP
);
211 gcc_assert (!DEBUG_INSN_P (src_node
->insn
) || t
== ANTI_DEP
);
213 /* We currently choose not to create certain anti-deps edges and
214 compensate for that by generating reg-moves based on the life-range
215 analysis. The anti-deps that will be deleted are the ones which
216 have true-deps edges in the opposite direction (in other words
217 the kernel has only one def of the relevant register).
218 If the address that is being auto-inc or auto-dec in DEST_NODE
219 is used in SRC_NODE then do not remove the edge to make sure
220 reg-moves will not be created for this address.
221 TODO: support the removal of all anti-deps edges, i.e. including those
222 whose register has multiple defs in the loop. */
223 if (flag_modulo_sched_allow_regmoves
224 && (t
== ANTI_DEP
&& dt
== REG_DEP
)
225 && !def_has_ccmode_p (dest_node
->insn
)
226 && !autoinc_var_is_used_p (dest_node
->insn
, src_node
->insn
))
230 set
= single_set (dest_node
->insn
);
231 /* TODO: Handle registers that REG_P is not true for them, i.e.
232 subregs and special registers. */
233 if (set
&& REG_P (SET_DEST (set
)))
235 int regno
= REGNO (SET_DEST (set
));
237 struct df_rd_bb_info
*bb_info
= DF_RD_BB_INFO (g
->bb
);
239 first_def
= df_bb_regno_first_def_find (g
->bb
, regno
);
240 gcc_assert (first_def
);
242 if (bitmap_bit_p (&bb_info
->gen
, DF_REF_ID (first_def
)))
247 latency
= dep_cost (link
);
248 e
= create_ddg_edge (src_node
, dest_node
, t
, dt
, latency
, distance
);
249 add_edge_to_ddg (g
, e
);
252 /* The same as the above function, but it doesn't require a link parameter. */
254 create_ddg_dep_no_link (ddg_ptr g
, ddg_node_ptr from
, ddg_node_ptr to
,
255 dep_type d_t
, dep_data_type d_dt
, int distance
)
259 enum reg_note dep_kind
;
260 struct _dep _dep
, *dep
= &_dep
;
262 gcc_assert (!DEBUG_INSN_P (to
->insn
) || d_t
== ANTI_DEP
);
263 gcc_assert (!DEBUG_INSN_P (from
->insn
) || d_t
== ANTI_DEP
);
266 dep_kind
= REG_DEP_ANTI
;
267 else if (d_t
== OUTPUT_DEP
)
268 dep_kind
= REG_DEP_OUTPUT
;
271 gcc_assert (d_t
== TRUE_DEP
);
273 dep_kind
= REG_DEP_TRUE
;
276 init_dep (dep
, from
->insn
, to
->insn
, dep_kind
);
280 e
= create_ddg_edge (from
, to
, d_t
, d_dt
, l
, distance
);
282 add_backarc_to_ddg (g
, e
);
284 add_edge_to_ddg (g
, e
);
288 /* Given a downwards exposed register def LAST_DEF (which is the last
289 definition of that register in the bb), add inter-loop true dependences
290 to all its uses in the next iteration, an output dependence to the
291 first def of the same register (possibly itself) in the next iteration
292 and anti-dependences from its uses in the current iteration to the
293 first definition in the next iteration. */
295 add_cross_iteration_register_deps (ddg_ptr g
, df_ref last_def
)
297 int regno
= DF_REF_REGNO (last_def
);
298 struct df_link
*r_use
;
299 int has_use_in_bb_p
= false;
300 rtx_insn
*def_insn
= DF_REF_INSN (last_def
);
301 ddg_node_ptr last_def_node
= get_node_of_insn (g
, def_insn
);
302 ddg_node_ptr use_node
;
303 df_ref first_def
= df_bb_regno_first_def_find (g
->bb
, regno
);
305 gcc_assert (last_def_node
);
306 gcc_assert (first_def
);
308 if (flag_checking
&& DF_REF_ID (last_def
) != DF_REF_ID (first_def
))
310 struct df_rd_bb_info
*bb_info
= DF_RD_BB_INFO (g
->bb
);
311 gcc_assert (!bitmap_bit_p (&bb_info
->gen
, DF_REF_ID (first_def
)));
314 /* Create inter-loop true dependences and anti dependences. */
315 for (r_use
= DF_REF_CHAIN (last_def
); r_use
!= NULL
; r_use
= r_use
->next
)
317 rtx_insn
*use_insn
= DF_REF_INSN (r_use
->ref
);
319 if (BLOCK_FOR_INSN (use_insn
) != g
->bb
)
322 /* ??? Do not handle uses with DF_REF_IN_NOTE notes. */
323 use_node
= get_node_of_insn (g
, use_insn
);
324 gcc_assert (use_node
);
325 has_use_in_bb_p
= true;
326 if (use_node
->cuid
<= last_def_node
->cuid
)
328 /* Add true deps from last_def to it's uses in the next
329 iteration. Any such upwards exposed use appears before
331 create_ddg_dep_no_link (g
, last_def_node
, use_node
,
332 DEBUG_INSN_P (use_insn
) ? ANTI_DEP
: TRUE_DEP
,
335 else if (!DEBUG_INSN_P (use_insn
))
337 /* Add anti deps from last_def's uses in the current iteration
338 to the first def in the next iteration. We do not add ANTI
339 dep when there is an intra-loop TRUE dep in the opposite
340 direction, but use regmoves to fix such disregarded ANTI
341 deps when broken. If the first_def reaches the USE then
342 there is such a dep. */
343 ddg_node_ptr first_def_node
= get_node_of_insn (g
,
344 DF_REF_INSN (first_def
));
346 gcc_assert (first_def_node
);
348 /* Always create the edge if the use node is a branch in
349 order to prevent the creation of reg-moves.
350 If the address that is being auto-inc or auto-dec in LAST_DEF
351 is used in USE_INSN then do not remove the edge to make sure
352 reg-moves will not be created for that address. */
353 if (DF_REF_ID (last_def
) != DF_REF_ID (first_def
)
354 || !flag_modulo_sched_allow_regmoves
355 || JUMP_P (use_node
->insn
)
356 || autoinc_var_is_used_p (DF_REF_INSN (last_def
), use_insn
)
357 || def_has_ccmode_p (DF_REF_INSN (last_def
)))
358 create_ddg_dep_no_link (g
, use_node
, first_def_node
, ANTI_DEP
,
363 /* Create an inter-loop output dependence between LAST_DEF (which is the
364 last def in its block, being downwards exposed) and the first def in
365 its block. Avoid creating a self output dependence. Avoid creating
366 an output dependence if there is a dependence path between the two
367 defs starting with a true dependence to a use which can be in the
368 next iteration; followed by an anti dependence of that use to the
369 first def (i.e. if there is a use between the two defs.) */
370 if (!has_use_in_bb_p
)
372 ddg_node_ptr dest_node
;
374 if (DF_REF_ID (last_def
) == DF_REF_ID (first_def
))
377 dest_node
= get_node_of_insn (g
, DF_REF_INSN (first_def
));
378 gcc_assert (dest_node
);
379 create_ddg_dep_no_link (g
, last_def_node
, dest_node
,
380 OUTPUT_DEP
, REG_DEP
, 1);
383 /* Build inter-loop dependencies, by looking at DF analysis backwards. */
385 build_inter_loop_deps (ddg_ptr g
)
388 struct df_rd_bb_info
*rd_bb_info
;
391 rd_bb_info
= DF_RD_BB_INFO (g
->bb
);
393 /* Find inter-loop register output, true and anti deps. */
394 EXECUTE_IF_SET_IN_BITMAP (&rd_bb_info
->gen
, 0, rd_num
, bi
)
396 df_ref rd
= DF_DEFS_GET (rd_num
);
398 add_cross_iteration_register_deps (g
, rd
);
403 /* Return true if two specified instructions have mem expr with conflict
406 insns_may_alias_p (rtx_insn
*insn1
, rtx_insn
*insn2
)
408 subrtx_iterator::array_type array1
;
409 subrtx_iterator::array_type array2
;
410 FOR_EACH_SUBRTX (iter1
, array1
, PATTERN (insn1
), NONCONST
)
412 const_rtx x1
= *iter1
;
414 FOR_EACH_SUBRTX (iter2
, array2
, PATTERN (insn2
), NONCONST
)
416 const_rtx x2
= *iter2
;
417 if (MEM_P (x2
) && may_alias_p (x2
, x1
))
424 /* Given two nodes, analyze their RTL insns and add intra-loop mem deps
427 add_intra_loop_mem_dep (ddg_ptr g
, ddg_node_ptr from
, ddg_node_ptr to
)
430 if ((from
->cuid
== to
->cuid
)
431 || !insns_may_alias_p (from
->insn
, to
->insn
))
432 /* Do not create edge if memory references have disjoint alias sets
433 or 'to' and 'from' are the same instruction. */
436 if (mem_write_insn_p (from
->insn
))
438 if (mem_read_insn_p (to
->insn
))
439 create_ddg_dep_no_link (g
, from
, to
,
440 DEBUG_INSN_P (to
->insn
)
441 ? ANTI_DEP
: TRUE_DEP
, MEM_DEP
, 0);
443 create_ddg_dep_no_link (g
, from
, to
,
444 DEBUG_INSN_P (to
->insn
)
445 ? ANTI_DEP
: OUTPUT_DEP
, MEM_DEP
, 0);
447 else if (!mem_read_insn_p (to
->insn
))
448 create_ddg_dep_no_link (g
, from
, to
, ANTI_DEP
, MEM_DEP
, 0);
451 /* Given two nodes, analyze their RTL insns and add inter-loop mem deps
454 add_inter_loop_mem_dep (ddg_ptr g
, ddg_node_ptr from
, ddg_node_ptr to
)
456 if (!insns_may_alias_p (from
->insn
, to
->insn
))
457 /* Do not create edge if memory references have disjoint alias sets. */
460 if (mem_write_insn_p (from
->insn
))
462 if (mem_read_insn_p (to
->insn
))
463 create_ddg_dep_no_link (g
, from
, to
,
464 DEBUG_INSN_P (to
->insn
)
465 ? ANTI_DEP
: TRUE_DEP
, MEM_DEP
, 1);
466 else if (from
->cuid
!= to
->cuid
)
467 create_ddg_dep_no_link (g
, from
, to
,
468 DEBUG_INSN_P (to
->insn
)
469 ? ANTI_DEP
: OUTPUT_DEP
, MEM_DEP
, 1);
473 if (mem_read_insn_p (to
->insn
))
475 else if (from
->cuid
!= to
->cuid
)
477 create_ddg_dep_no_link (g
, from
, to
, ANTI_DEP
, MEM_DEP
, 1);
478 if (DEBUG_INSN_P (from
->insn
) || DEBUG_INSN_P (to
->insn
))
479 create_ddg_dep_no_link (g
, to
, from
, ANTI_DEP
, MEM_DEP
, 1);
481 create_ddg_dep_no_link (g
, to
, from
, TRUE_DEP
, MEM_DEP
, 1);
487 /* Perform intra-block Data Dependency analysis and connect the nodes in
488 the DDG. We assume the loop has a single basic block. */
490 build_intra_loop_deps (ddg_ptr g
)
493 /* Hold the dependency analysis state during dependency calculations. */
494 struct deps_desc tmp_deps
;
495 rtx_insn
*head
, *tail
;
497 /* Build the dependence information, using the sched_analyze function. */
499 init_deps (&tmp_deps
, false);
501 /* Do the intra-block data dependence analysis for the given block. */
502 get_ebb_head_tail (g
->bb
, g
->bb
, &head
, &tail
);
503 sched_analyze (&tmp_deps
, head
, tail
);
505 /* Build intra-loop data dependencies using the scheduler dependency
507 for (i
= 0; i
< g
->num_nodes
; i
++)
509 ddg_node_ptr dest_node
= &g
->nodes
[i
];
510 sd_iterator_def sd_it
;
513 if (! INSN_P (dest_node
->insn
))
516 FOR_EACH_DEP (dest_node
->insn
, SD_LIST_BACK
, sd_it
, dep
)
518 rtx_insn
*src_insn
= DEP_PRO (dep
);
519 ddg_node_ptr src_node
;
521 /* Don't add dependencies on debug insns to non-debug insns
522 to avoid codegen differences between -g and -g0. */
523 if (DEBUG_INSN_P (src_insn
) && !DEBUG_INSN_P (dest_node
->insn
))
526 src_node
= get_node_of_insn (g
, src_insn
);
531 create_ddg_dep_from_intra_loop_link (g
, src_node
, dest_node
, dep
);
534 /* If this insn modifies memory, add an edge to all insns that access
536 if (mem_access_insn_p (dest_node
->insn
))
540 for (j
= 0; j
<= i
; j
++)
542 ddg_node_ptr j_node
= &g
->nodes
[j
];
543 if (DEBUG_INSN_P (j_node
->insn
))
545 if (mem_access_insn_p (j_node
->insn
))
547 /* Don't bother calculating inter-loop dep if an intra-loop dep
549 if (! bitmap_bit_p (dest_node
->successors
, j
))
550 add_inter_loop_mem_dep (g
, dest_node
, j_node
);
551 /* If -fmodulo-sched-allow-regmoves
552 is set certain anti-dep edges are not created.
553 It might be that these anti-dep edges are on the
554 path from one memory instruction to another such that
555 removing these edges could cause a violation of the
556 memory dependencies. Thus we add intra edges between
557 every two memory instructions in this case. */
558 if (flag_modulo_sched_allow_regmoves
559 && !bitmap_bit_p (dest_node
->predecessors
, j
))
560 add_intra_loop_mem_dep (g
, j_node
, dest_node
);
566 /* Free the INSN_LISTs. */
567 finish_deps_global ();
568 free_deps (&tmp_deps
);
570 /* Free dependencies. */
571 sched_free_deps (head
, tail
, false);
575 /* Given a basic block, create its DDG and return a pointer to a variable
576 of ddg type that represents it.
577 Initialize the ddg structure fields to the appropriate values. */
579 create_ddg (basic_block bb
, int closing_branch_deps
)
582 rtx_insn
*insn
, *first_note
;
586 g
= (ddg_ptr
) xcalloc (1, sizeof (struct ddg
));
589 g
->closing_branch_deps
= closing_branch_deps
;
591 /* Count the number of insns in the BB. */
592 for (insn
= BB_HEAD (bb
); insn
!= NEXT_INSN (BB_END (bb
));
593 insn
= NEXT_INSN (insn
))
595 if (! INSN_P (insn
) || GET_CODE (PATTERN (insn
)) == USE
)
598 if (DEBUG_INSN_P (insn
))
602 if (mem_read_insn_p (insn
))
604 if (mem_write_insn_p (insn
))
610 /* There is nothing to do for this BB. */
611 if ((num_nodes
- g
->num_debug
) <= 1)
617 /* Allocate the nodes array, and initialize the nodes. */
618 g
->num_nodes
= num_nodes
;
619 g
->nodes
= (ddg_node_ptr
) xcalloc (num_nodes
, sizeof (struct ddg_node
));
620 g
->closing_branch
= NULL
;
623 for (insn
= BB_HEAD (bb
); insn
!= NEXT_INSN (BB_END (bb
));
624 insn
= NEXT_INSN (insn
))
628 if (! first_note
&& NOTE_P (insn
)
629 && NOTE_KIND (insn
) != NOTE_INSN_BASIC_BLOCK
)
635 gcc_assert (!g
->closing_branch
);
636 g
->closing_branch
= &g
->nodes
[i
];
638 else if (GET_CODE (PATTERN (insn
)) == USE
)
645 g
->nodes
[i
].cuid
= i
;
646 g
->nodes
[i
].successors
= sbitmap_alloc (num_nodes
);
647 bitmap_clear (g
->nodes
[i
].successors
);
648 g
->nodes
[i
].predecessors
= sbitmap_alloc (num_nodes
);
649 bitmap_clear (g
->nodes
[i
].predecessors
);
650 g
->nodes
[i
].first_note
= (first_note
? first_note
: insn
);
651 g
->nodes
[i
++].insn
= insn
;
655 /* We must have found a branch in DDG. */
656 gcc_assert (g
->closing_branch
);
659 /* Build the data dependency graph. */
660 build_intra_loop_deps (g
);
661 build_inter_loop_deps (g
);
665 /* Free all the memory allocated for the DDG. */
674 for (i
= 0; i
< g
->num_nodes
; i
++)
676 ddg_edge_ptr e
= g
->nodes
[i
].out
;
680 ddg_edge_ptr next
= e
->next_out
;
685 sbitmap_free (g
->nodes
[i
].successors
);
686 sbitmap_free (g
->nodes
[i
].predecessors
);
688 if (g
->num_backarcs
> 0)
695 print_ddg_edge (FILE *file
, ddg_edge_ptr e
)
711 fprintf (file
, " [%d -(%c,%d,%d)-> %d] ", INSN_UID (e
->src
->insn
),
712 dep_c
, e
->latency
, e
->distance
, INSN_UID (e
->dest
->insn
));
715 /* Print the DDG nodes with there in/out edges to the dump file. */
717 print_ddg (FILE *file
, ddg_ptr g
)
721 for (i
= 0; i
< g
->num_nodes
; i
++)
725 fprintf (file
, "Node num: %d\n", g
->nodes
[i
].cuid
);
726 print_rtl_single (file
, g
->nodes
[i
].insn
);
727 fprintf (file
, "OUT ARCS: ");
728 for (e
= g
->nodes
[i
].out
; e
; e
= e
->next_out
)
729 print_ddg_edge (file
, e
);
731 fprintf (file
, "\nIN ARCS: ");
732 for (e
= g
->nodes
[i
].in
; e
; e
= e
->next_in
)
733 print_ddg_edge (file
, e
);
735 fprintf (file
, "\n");
739 /* Print the given DDG in VCG format. */
741 vcg_print_ddg (FILE *file
, ddg_ptr g
)
745 fprintf (file
, "graph: {\n");
746 for (src_cuid
= 0; src_cuid
< g
->num_nodes
; src_cuid
++)
749 int src_uid
= INSN_UID (g
->nodes
[src_cuid
].insn
);
751 fprintf (file
, "node: {title: \"%d_%d\" info1: \"", src_cuid
, src_uid
);
752 print_rtl_single (file
, g
->nodes
[src_cuid
].insn
);
753 fprintf (file
, "\"}\n");
754 for (e
= g
->nodes
[src_cuid
].out
; e
; e
= e
->next_out
)
756 int dst_uid
= INSN_UID (e
->dest
->insn
);
757 int dst_cuid
= e
->dest
->cuid
;
759 /* Give the backarcs a different color. */
761 fprintf (file
, "backedge: {color: red ");
763 fprintf (file
, "edge: { ");
765 fprintf (file
, "sourcename: \"%d_%d\" ", src_cuid
, src_uid
);
766 fprintf (file
, "targetname: \"%d_%d\" ", dst_cuid
, dst_uid
);
767 fprintf (file
, "label: \"%d_%d\"}\n", e
->latency
, e
->distance
);
770 fprintf (file
, "}\n");
773 /* Dump the sccs in SCCS. */
775 print_sccs (FILE *file
, ddg_all_sccs_ptr sccs
, ddg_ptr g
)
778 sbitmap_iterator sbi
;
784 fprintf (file
, "\n;; Number of SCC nodes - %d\n", sccs
->num_sccs
);
785 for (i
= 0; i
< sccs
->num_sccs
; i
++)
787 fprintf (file
, "SCC number: %d\n", i
);
788 EXECUTE_IF_SET_IN_BITMAP (sccs
->sccs
[i
]->nodes
, 0, u
, sbi
)
790 fprintf (file
, "insn num %d\n", u
);
791 print_rtl_single (file
, g
->nodes
[u
].insn
);
794 fprintf (file
, "\n");
797 /* Create an edge and initialize it with given values. */
799 create_ddg_edge (ddg_node_ptr src
, ddg_node_ptr dest
,
800 dep_type t
, dep_data_type dt
, int l
, int d
)
802 ddg_edge_ptr e
= (ddg_edge_ptr
) xmalloc (sizeof (struct ddg_edge
));
810 e
->next_in
= e
->next_out
= NULL
;
815 /* Add the given edge to the in/out linked lists of the DDG nodes. */
817 add_edge_to_ddg (ddg_ptr g ATTRIBUTE_UNUSED
, ddg_edge_ptr e
)
819 ddg_node_ptr src
= e
->src
;
820 ddg_node_ptr dest
= e
->dest
;
822 /* Should have allocated the sbitmaps. */
823 gcc_assert (src
->successors
&& dest
->predecessors
);
825 bitmap_set_bit (src
->successors
, dest
->cuid
);
826 bitmap_set_bit (dest
->predecessors
, src
->cuid
);
827 e
->next_in
= dest
->in
;
829 e
->next_out
= src
->out
;
835 /* Algorithm for computing the recurrence_length of an scc. We assume at
836 for now that cycles in the data dependence graph contain a single backarc.
837 This simplifies the algorithm, and can be generalized later. */
839 set_recurrence_length (ddg_scc_ptr scc
, ddg_ptr g
)
844 for (j
= 0; j
< scc
->num_backarcs
; j
++)
846 ddg_edge_ptr backarc
= scc
->backarcs
[j
];
848 int distance
= backarc
->distance
;
849 ddg_node_ptr src
= backarc
->dest
;
850 ddg_node_ptr dest
= backarc
->src
;
852 length
= longest_simple_path (g
, src
->cuid
, dest
->cuid
, scc
->nodes
);
855 /* fprintf (stderr, "Backarc not on simple cycle in SCC.\n"); */
858 length
+= backarc
->latency
;
859 result
= MAX (result
, (length
/ distance
));
861 scc
->recurrence_length
= result
;
864 /* Create a new SCC given the set of its nodes. Compute its recurrence_length
865 and mark edges that belong to this scc as IN_SCC. */
867 create_scc (ddg_ptr g
, sbitmap nodes
)
871 sbitmap_iterator sbi
;
873 scc
= (ddg_scc_ptr
) xmalloc (sizeof (struct ddg_scc
));
874 scc
->backarcs
= NULL
;
875 scc
->num_backarcs
= 0;
876 scc
->nodes
= sbitmap_alloc (g
->num_nodes
);
877 bitmap_copy (scc
->nodes
, nodes
);
879 /* Mark the backarcs that belong to this SCC. */
880 EXECUTE_IF_SET_IN_BITMAP (nodes
, 0, u
, sbi
)
883 ddg_node_ptr n
= &g
->nodes
[u
];
885 for (e
= n
->out
; e
; e
= e
->next_out
)
886 if (bitmap_bit_p (nodes
, e
->dest
->cuid
))
888 e
->aux
.count
= IN_SCC
;
890 add_backarc_to_scc (scc
, e
);
894 set_recurrence_length (scc
, g
);
898 /* Cleans the memory allocation of a given SCC. */
900 free_scc (ddg_scc_ptr scc
)
905 sbitmap_free (scc
->nodes
);
906 if (scc
->num_backarcs
> 0)
907 free (scc
->backarcs
);
912 /* Add a given edge known to be a backarc to the given DDG. */
914 add_backarc_to_ddg (ddg_ptr g
, ddg_edge_ptr e
)
916 int size
= (g
->num_backarcs
+ 1) * sizeof (ddg_edge_ptr
);
918 add_edge_to_ddg (g
, e
);
919 g
->backarcs
= (ddg_edge_ptr
*) xrealloc (g
->backarcs
, size
);
920 g
->backarcs
[g
->num_backarcs
++] = e
;
923 /* Add backarc to an SCC. */
925 add_backarc_to_scc (ddg_scc_ptr scc
, ddg_edge_ptr e
)
927 int size
= (scc
->num_backarcs
+ 1) * sizeof (ddg_edge_ptr
);
929 scc
->backarcs
= (ddg_edge_ptr
*) xrealloc (scc
->backarcs
, size
);
930 scc
->backarcs
[scc
->num_backarcs
++] = e
;
933 /* Add the given SCC to the DDG. */
935 add_scc_to_ddg (ddg_all_sccs_ptr g
, ddg_scc_ptr scc
)
937 int size
= (g
->num_sccs
+ 1) * sizeof (ddg_scc_ptr
);
939 g
->sccs
= (ddg_scc_ptr
*) xrealloc (g
->sccs
, size
);
940 g
->sccs
[g
->num_sccs
++] = scc
;
943 /* Given the instruction INSN return the node that represents it. */
945 get_node_of_insn (ddg_ptr g
, rtx_insn
*insn
)
949 for (i
= 0; i
< g
->num_nodes
; i
++)
950 if (insn
== g
->nodes
[i
].insn
)
955 /* Given a set OPS of nodes in the DDG, find the set of their successors
956 which are not in OPS, and set their bits in SUCC. Bits corresponding to
957 OPS are cleared from SUCC. Leaves the other bits in SUCC unchanged. */
959 find_successors (sbitmap succ
, ddg_ptr g
, sbitmap ops
)
962 sbitmap_iterator sbi
;
964 EXECUTE_IF_SET_IN_BITMAP (ops
, 0, i
, sbi
)
966 const sbitmap node_succ
= NODE_SUCCESSORS (&g
->nodes
[i
]);
967 bitmap_ior (succ
, succ
, node_succ
);
970 /* We want those that are not in ops. */
971 bitmap_and_compl (succ
, succ
, ops
);
974 /* Given a set OPS of nodes in the DDG, find the set of their predecessors
975 which are not in OPS, and set their bits in PREDS. Bits corresponding to
976 OPS are cleared from PREDS. Leaves the other bits in PREDS unchanged. */
978 find_predecessors (sbitmap preds
, ddg_ptr g
, sbitmap ops
)
981 sbitmap_iterator sbi
;
983 EXECUTE_IF_SET_IN_BITMAP (ops
, 0, i
, sbi
)
985 const sbitmap node_preds
= NODE_PREDECESSORS (&g
->nodes
[i
]);
986 bitmap_ior (preds
, preds
, node_preds
);
989 /* We want those that are not in ops. */
990 bitmap_and_compl (preds
, preds
, ops
);
994 /* Compare function to be passed to qsort to order the backarcs in descending
997 compare_sccs (const void *s1
, const void *s2
)
999 const int rec_l1
= (*(const ddg_scc_ptr
*)s1
)->recurrence_length
;
1000 const int rec_l2
= (*(const ddg_scc_ptr
*)s2
)->recurrence_length
;
1001 return ((rec_l2
> rec_l1
) - (rec_l2
< rec_l1
));
1005 /* Order the backarcs in descending recMII order using compare_sccs. */
1007 order_sccs (ddg_all_sccs_ptr g
)
1009 qsort (g
->sccs
, g
->num_sccs
, sizeof (ddg_scc_ptr
),
1010 (int (*) (const void *, const void *)) compare_sccs
);
1013 /* Check that every node in SCCS belongs to exactly one strongly connected
1014 component and that no element of SCCS is empty. */
1016 check_sccs (ddg_all_sccs_ptr sccs
, int num_nodes
)
1019 sbitmap tmp
= sbitmap_alloc (num_nodes
);
1022 for (i
= 0; i
< sccs
->num_sccs
; i
++)
1024 gcc_assert (!bitmap_empty_p (sccs
->sccs
[i
]->nodes
));
1025 /* Verify that every node in sccs is in exactly one strongly
1026 connected component. */
1027 gcc_assert (!bitmap_intersect_p (tmp
, sccs
->sccs
[i
]->nodes
));
1028 bitmap_ior (tmp
, tmp
, sccs
->sccs
[i
]->nodes
);
1033 /* Perform the Strongly Connected Components decomposing algorithm on the
1034 DDG and return DDG_ALL_SCCS structure that contains them. */
1036 create_ddg_all_sccs (ddg_ptr g
)
1039 int num_nodes
= g
->num_nodes
;
1040 sbitmap from
= sbitmap_alloc (num_nodes
);
1041 sbitmap to
= sbitmap_alloc (num_nodes
);
1042 sbitmap scc_nodes
= sbitmap_alloc (num_nodes
);
1043 ddg_all_sccs_ptr sccs
= (ddg_all_sccs_ptr
)
1044 xmalloc (sizeof (struct ddg_all_sccs
));
1050 for (i
= 0; i
< g
->num_backarcs
; i
++)
1053 ddg_edge_ptr backarc
= g
->backarcs
[i
];
1054 ddg_node_ptr src
= backarc
->src
;
1055 ddg_node_ptr dest
= backarc
->dest
;
1057 /* If the backarc already belongs to an SCC, continue. */
1058 if (backarc
->aux
.count
== IN_SCC
)
1061 bitmap_clear (scc_nodes
);
1062 bitmap_clear (from
);
1064 bitmap_set_bit (from
, dest
->cuid
);
1065 bitmap_set_bit (to
, src
->cuid
);
1067 if (find_nodes_on_paths (scc_nodes
, g
, from
, to
))
1069 scc
= create_scc (g
, scc_nodes
);
1070 add_scc_to_ddg (sccs
, scc
);
1074 sbitmap_free (from
);
1076 sbitmap_free (scc_nodes
);
1079 check_sccs (sccs
, num_nodes
);
1084 /* Frees the memory allocated for all SCCs of the DDG, but keeps the DDG. */
1086 free_ddg_all_sccs (ddg_all_sccs_ptr all_sccs
)
1093 for (i
= 0; i
< all_sccs
->num_sccs
; i
++)
1094 free_scc (all_sccs
->sccs
[i
]);
1096 free (all_sccs
->sccs
);
1101 /* Given FROM - a bitmap of source nodes - and TO - a bitmap of destination
1102 nodes - find all nodes that lie on paths from FROM to TO (not excluding
1103 nodes from FROM and TO). Return nonzero if nodes exist. */
1105 find_nodes_on_paths (sbitmap result
, ddg_ptr g
, sbitmap from
, sbitmap to
)
1110 int num_nodes
= g
->num_nodes
;
1111 sbitmap_iterator sbi
;
1113 sbitmap workset
= sbitmap_alloc (num_nodes
);
1114 sbitmap reachable_from
= sbitmap_alloc (num_nodes
);
1115 sbitmap reach_to
= sbitmap_alloc (num_nodes
);
1116 sbitmap tmp
= sbitmap_alloc (num_nodes
);
1118 bitmap_copy (reachable_from
, from
);
1119 bitmap_copy (tmp
, from
);
1125 bitmap_copy (workset
, tmp
);
1127 EXECUTE_IF_SET_IN_BITMAP (workset
, 0, u
, sbi
)
1130 ddg_node_ptr u_node
= &g
->nodes
[u
];
1132 for (e
= u_node
->out
; e
!= (ddg_edge_ptr
) 0; e
= e
->next_out
)
1134 ddg_node_ptr v_node
= e
->dest
;
1135 int v
= v_node
->cuid
;
1137 if (!bitmap_bit_p (reachable_from
, v
))
1139 bitmap_set_bit (reachable_from
, v
);
1140 bitmap_set_bit (tmp
, v
);
1147 bitmap_copy (reach_to
, to
);
1148 bitmap_copy (tmp
, to
);
1154 bitmap_copy (workset
, tmp
);
1156 EXECUTE_IF_SET_IN_BITMAP (workset
, 0, u
, sbi
)
1159 ddg_node_ptr u_node
= &g
->nodes
[u
];
1161 for (e
= u_node
->in
; e
!= (ddg_edge_ptr
) 0; e
= e
->next_in
)
1163 ddg_node_ptr v_node
= e
->src
;
1164 int v
= v_node
->cuid
;
1166 if (!bitmap_bit_p (reach_to
, v
))
1168 bitmap_set_bit (reach_to
, v
);
1169 bitmap_set_bit (tmp
, v
);
1176 answer
= bitmap_and (result
, reachable_from
, reach_to
);
1177 sbitmap_free (workset
);
1178 sbitmap_free (reachable_from
);
1179 sbitmap_free (reach_to
);
1185 /* Updates the counts of U_NODE's successors (that belong to NODES) to be
1186 at-least as large as the count of U_NODE plus the latency between them.
1187 Sets a bit in TMP for each successor whose count was changed (increased).
1188 Returns nonzero if any count was changed. */
1190 update_dist_to_successors (ddg_node_ptr u_node
, sbitmap nodes
, sbitmap tmp
)
1195 for (e
= u_node
->out
; e
; e
= e
->next_out
)
1197 ddg_node_ptr v_node
= e
->dest
;
1198 int v
= v_node
->cuid
;
1200 if (bitmap_bit_p (nodes
, v
)
1201 && (e
->distance
== 0)
1202 && (v_node
->aux
.count
< u_node
->aux
.count
+ e
->latency
))
1204 v_node
->aux
.count
= u_node
->aux
.count
+ e
->latency
;
1205 bitmap_set_bit (tmp
, v
);
1213 /* Find the length of a longest path from SRC to DEST in G,
1214 going only through NODES, and disregarding backarcs. */
1216 longest_simple_path (struct ddg
* g
, int src
, int dest
, sbitmap nodes
)
1222 int num_nodes
= g
->num_nodes
;
1223 sbitmap workset
= sbitmap_alloc (num_nodes
);
1224 sbitmap tmp
= sbitmap_alloc (num_nodes
);
1227 /* Data will hold the distance of the longest path found so far from
1228 src to each node. Initialize to -1 = less than minimum. */
1229 for (i
= 0; i
< g
->num_nodes
; i
++)
1230 g
->nodes
[i
].aux
.count
= -1;
1231 g
->nodes
[src
].aux
.count
= 0;
1234 bitmap_set_bit (tmp
, src
);
1238 sbitmap_iterator sbi
;
1241 bitmap_copy (workset
, tmp
);
1243 EXECUTE_IF_SET_IN_BITMAP (workset
, 0, u
, sbi
)
1245 ddg_node_ptr u_node
= &g
->nodes
[u
];
1247 change
|= update_dist_to_successors (u_node
, nodes
, tmp
);
1250 result
= g
->nodes
[dest
].aux
.count
;
1251 sbitmap_free (workset
);
1256 #endif /* INSN_SCHEDULING */