1 /* DDG - Data Dependence Graph implementation.
2 Copyright (C) 2004-2014 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"
26 #include "diagnostic-core.h"
29 #include "hard-reg-set.h"
33 #include "insn-config.h"
34 #include "insn-attr.h"
37 #include "sched-int.h"
45 #ifdef INSN_SCHEDULING
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
*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
*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
*insn
)
143 return rtx_mem_access_p (PATTERN (insn
));
146 /* Return true if DEF_INSN contains address being auto-inc or auto-dec
147 which is used in USE_INSN. Otherwise return false. The result is
148 being used to decide whether to remove the edge between def_insn and
149 use_insn when -fmodulo-sched-allow-regmoves is set. This function
150 doesn't need to consider the specific address register; no reg_moves
151 will be allowed for any life range defined by def_insn and used
152 by use_insn, if use_insn uses an address register auto-inc'ed by
155 autoinc_var_is_used_p (rtx_insn
*def_insn
, rtx_insn
*use_insn
)
159 for (note
= REG_NOTES (def_insn
); note
; note
= XEXP (note
, 1))
160 if (REG_NOTE_KIND (note
) == REG_INC
161 && reg_referenced_p (XEXP (note
, 0), PATTERN (use_insn
)))
167 /* Return true if one of the definitions in INSN has MODE_CC. Otherwise
170 def_has_ccmode_p (rtx_insn
*insn
)
174 FOR_EACH_INSN_DEF (def
, insn
)
176 enum machine_mode mode
= GET_MODE (DF_REF_REG (def
));
178 if (GET_MODE_CLASS (mode
) == MODE_CC
)
185 /* Computes the dependence parameters (latency, distance etc.), creates
186 a ddg_edge and adds it to the given DDG. */
188 create_ddg_dep_from_intra_loop_link (ddg_ptr g
, ddg_node_ptr src_node
,
189 ddg_node_ptr dest_node
, dep_t link
)
192 int latency
, distance
= 0;
193 dep_type t
= TRUE_DEP
;
194 dep_data_type dt
= (mem_access_insn_p (src_node
->insn
)
195 && mem_access_insn_p (dest_node
->insn
) ? MEM_DEP
197 gcc_assert (src_node
->cuid
< dest_node
->cuid
);
200 /* Note: REG_DEP_ANTI applies to MEM ANTI_DEP as well!! */
201 if (DEP_TYPE (link
) == REG_DEP_ANTI
)
203 else if (DEP_TYPE (link
) == REG_DEP_OUTPUT
)
206 gcc_assert (!DEBUG_INSN_P (dest_node
->insn
) || t
== ANTI_DEP
);
207 gcc_assert (!DEBUG_INSN_P (src_node
->insn
) || t
== ANTI_DEP
);
209 /* We currently choose not to create certain anti-deps edges and
210 compensate for that by generating reg-moves based on the life-range
211 analysis. The anti-deps that will be deleted are the ones which
212 have true-deps edges in the opposite direction (in other words
213 the kernel has only one def of the relevant register).
214 If the address that is being auto-inc or auto-dec in DEST_NODE
215 is used in SRC_NODE then do not remove the edge to make sure
216 reg-moves will not be created for this address.
217 TODO: support the removal of all anti-deps edges, i.e. including those
218 whose register has multiple defs in the loop. */
219 if (flag_modulo_sched_allow_regmoves
220 && (t
== ANTI_DEP
&& dt
== REG_DEP
)
221 && !def_has_ccmode_p (dest_node
->insn
)
222 && !autoinc_var_is_used_p (dest_node
->insn
, src_node
->insn
))
226 set
= single_set (dest_node
->insn
);
227 /* TODO: Handle registers that REG_P is not true for them, i.e.
228 subregs and special registers. */
229 if (set
&& REG_P (SET_DEST (set
)))
231 int regno
= REGNO (SET_DEST (set
));
233 struct df_rd_bb_info
*bb_info
= DF_RD_BB_INFO (g
->bb
);
235 first_def
= df_bb_regno_first_def_find (g
->bb
, regno
);
236 gcc_assert (first_def
);
238 if (bitmap_bit_p (&bb_info
->gen
, DF_REF_ID (first_def
)))
243 latency
= dep_cost (link
);
244 e
= create_ddg_edge (src_node
, dest_node
, t
, dt
, latency
, distance
);
245 add_edge_to_ddg (g
, e
);
248 /* The same as the above function, but it doesn't require a link parameter. */
250 create_ddg_dep_no_link (ddg_ptr g
, ddg_node_ptr from
, ddg_node_ptr to
,
251 dep_type d_t
, dep_data_type d_dt
, int distance
)
255 enum reg_note dep_kind
;
256 struct _dep _dep
, *dep
= &_dep
;
258 gcc_assert (!DEBUG_INSN_P (to
->insn
) || d_t
== ANTI_DEP
);
259 gcc_assert (!DEBUG_INSN_P (from
->insn
) || d_t
== ANTI_DEP
);
262 dep_kind
= REG_DEP_ANTI
;
263 else if (d_t
== OUTPUT_DEP
)
264 dep_kind
= REG_DEP_OUTPUT
;
267 gcc_assert (d_t
== TRUE_DEP
);
269 dep_kind
= REG_DEP_TRUE
;
272 init_dep (dep
, from
->insn
, to
->insn
, dep_kind
);
276 e
= create_ddg_edge (from
, to
, d_t
, d_dt
, l
, distance
);
278 add_backarc_to_ddg (g
, e
);
280 add_edge_to_ddg (g
, e
);
284 /* Given a downwards exposed register def LAST_DEF (which is the last
285 definition of that register in the bb), add inter-loop true dependences
286 to all its uses in the next iteration, an output dependence to the
287 first def of the same register (possibly itself) in the next iteration
288 and anti-dependences from its uses in the current iteration to the
289 first definition in the next iteration. */
291 add_cross_iteration_register_deps (ddg_ptr g
, df_ref last_def
)
293 int regno
= DF_REF_REGNO (last_def
);
294 struct df_link
*r_use
;
295 int has_use_in_bb_p
= false;
296 rtx_insn
*def_insn
= DF_REF_INSN (last_def
);
297 ddg_node_ptr last_def_node
= get_node_of_insn (g
, def_insn
);
298 ddg_node_ptr use_node
;
299 #ifdef ENABLE_CHECKING
300 struct df_rd_bb_info
*bb_info
= DF_RD_BB_INFO (g
->bb
);
302 df_ref first_def
= df_bb_regno_first_def_find (g
->bb
, regno
);
304 gcc_assert (last_def_node
);
305 gcc_assert (first_def
);
307 #ifdef ENABLE_CHECKING
308 if (DF_REF_ID (last_def
) != DF_REF_ID (first_def
))
309 gcc_assert (!bitmap_bit_p (&bb_info
->gen
,
310 DF_REF_ID (first_def
)));
313 /* Create inter-loop true dependences and anti dependences. */
314 for (r_use
= DF_REF_CHAIN (last_def
); r_use
!= NULL
; r_use
= r_use
->next
)
316 rtx_insn
*use_insn
= DF_REF_INSN (r_use
->ref
);
318 if (BLOCK_FOR_INSN (use_insn
) != g
->bb
)
321 /* ??? Do not handle uses with DF_REF_IN_NOTE notes. */
322 use_node
= get_node_of_insn (g
, use_insn
);
323 gcc_assert (use_node
);
324 has_use_in_bb_p
= true;
325 if (use_node
->cuid
<= last_def_node
->cuid
)
327 /* Add true deps from last_def to it's uses in the next
328 iteration. Any such upwards exposed use appears before
330 create_ddg_dep_no_link (g
, last_def_node
, use_node
,
331 DEBUG_INSN_P (use_insn
) ? ANTI_DEP
: TRUE_DEP
,
334 else if (!DEBUG_INSN_P (use_insn
))
336 /* Add anti deps from last_def's uses in the current iteration
337 to the first def in the next iteration. We do not add ANTI
338 dep when there is an intra-loop TRUE dep in the opposite
339 direction, but use regmoves to fix such disregarded ANTI
340 deps when broken. If the first_def reaches the USE then
341 there is such a dep. */
342 ddg_node_ptr first_def_node
= get_node_of_insn (g
,
343 DF_REF_INSN (first_def
));
345 gcc_assert (first_def_node
);
347 /* Always create the edge if the use node is a branch in
348 order to prevent the creation of reg-moves.
349 If the address that is being auto-inc or auto-dec in LAST_DEF
350 is used in USE_INSN then do not remove the edge to make sure
351 reg-moves will not be created for that address. */
352 if (DF_REF_ID (last_def
) != DF_REF_ID (first_def
)
353 || !flag_modulo_sched_allow_regmoves
354 || JUMP_P (use_node
->insn
)
355 || autoinc_var_is_used_p (DF_REF_INSN (last_def
), use_insn
)
356 || def_has_ccmode_p (DF_REF_INSN (last_def
)))
357 create_ddg_dep_no_link (g
, use_node
, first_def_node
, ANTI_DEP
,
362 /* Create an inter-loop output dependence between LAST_DEF (which is the
363 last def in its block, being downwards exposed) and the first def in
364 its block. Avoid creating a self output dependence. Avoid creating
365 an output dependence if there is a dependence path between the two
366 defs starting with a true dependence to a use which can be in the
367 next iteration; followed by an anti dependence of that use to the
368 first def (i.e. if there is a use between the two defs.) */
369 if (!has_use_in_bb_p
)
371 ddg_node_ptr dest_node
;
373 if (DF_REF_ID (last_def
) == DF_REF_ID (first_def
))
376 dest_node
= get_node_of_insn (g
, DF_REF_INSN (first_def
));
377 gcc_assert (dest_node
);
378 create_ddg_dep_no_link (g
, last_def_node
, dest_node
,
379 OUTPUT_DEP
, REG_DEP
, 1);
382 /* Build inter-loop dependencies, by looking at DF analysis backwards. */
384 build_inter_loop_deps (ddg_ptr g
)
387 struct df_rd_bb_info
*rd_bb_info
;
390 rd_bb_info
= DF_RD_BB_INFO (g
->bb
);
392 /* Find inter-loop register output, true and anti deps. */
393 EXECUTE_IF_SET_IN_BITMAP (&rd_bb_info
->gen
, 0, rd_num
, bi
)
395 df_ref rd
= DF_DEFS_GET (rd_num
);
397 add_cross_iteration_register_deps (g
, rd
);
403 walk_mems_2 (rtx
*x
, rtx mem
)
407 if (may_alias_p (*x
, mem
))
416 walk_mems_1 (rtx
*x
, rtx
*pat
)
420 /* Visit all MEMs in *PAT and check independence. */
421 if (for_each_rtx (pat
, (rtx_function
) walk_mems_2
, *x
))
422 /* Indicate that dependence was determined and stop traversal. */
430 /* Return 1 if two specified instructions have mem expr with conflict alias sets*/
432 insns_may_alias_p (rtx_insn
*insn1
, rtx_insn
*insn2
)
434 /* For each pair of MEMs in INSN1 and INSN2 check their independence. */
435 return for_each_rtx (&PATTERN (insn1
), (rtx_function
) walk_mems_1
,
439 /* Given two nodes, analyze their RTL insns and add intra-loop mem deps
442 add_intra_loop_mem_dep (ddg_ptr g
, ddg_node_ptr from
, ddg_node_ptr to
)
445 if ((from
->cuid
== to
->cuid
)
446 || !insns_may_alias_p (from
->insn
, to
->insn
))
447 /* Do not create edge if memory references have disjoint alias sets
448 or 'to' and 'from' are the same instruction. */
451 if (mem_write_insn_p (from
->insn
))
453 if (mem_read_insn_p (to
->insn
))
454 create_ddg_dep_no_link (g
, from
, to
,
455 DEBUG_INSN_P (to
->insn
)
456 ? ANTI_DEP
: TRUE_DEP
, MEM_DEP
, 0);
458 create_ddg_dep_no_link (g
, from
, to
,
459 DEBUG_INSN_P (to
->insn
)
460 ? ANTI_DEP
: OUTPUT_DEP
, MEM_DEP
, 0);
462 else if (!mem_read_insn_p (to
->insn
))
463 create_ddg_dep_no_link (g
, from
, to
, ANTI_DEP
, MEM_DEP
, 0);
466 /* Given two nodes, analyze their RTL insns and add inter-loop mem deps
469 add_inter_loop_mem_dep (ddg_ptr g
, ddg_node_ptr from
, ddg_node_ptr to
)
471 if (!insns_may_alias_p (from
->insn
, to
->insn
))
472 /* Do not create edge if memory references have disjoint alias sets. */
475 if (mem_write_insn_p (from
->insn
))
477 if (mem_read_insn_p (to
->insn
))
478 create_ddg_dep_no_link (g
, from
, to
,
479 DEBUG_INSN_P (to
->insn
)
480 ? ANTI_DEP
: TRUE_DEP
, MEM_DEP
, 1);
481 else if (from
->cuid
!= to
->cuid
)
482 create_ddg_dep_no_link (g
, from
, to
,
483 DEBUG_INSN_P (to
->insn
)
484 ? ANTI_DEP
: OUTPUT_DEP
, MEM_DEP
, 1);
488 if (mem_read_insn_p (to
->insn
))
490 else if (from
->cuid
!= to
->cuid
)
492 create_ddg_dep_no_link (g
, from
, to
, ANTI_DEP
, MEM_DEP
, 1);
493 if (DEBUG_INSN_P (from
->insn
) || DEBUG_INSN_P (to
->insn
))
494 create_ddg_dep_no_link (g
, to
, from
, ANTI_DEP
, MEM_DEP
, 1);
496 create_ddg_dep_no_link (g
, to
, from
, TRUE_DEP
, MEM_DEP
, 1);
502 /* Perform intra-block Data Dependency analysis and connect the nodes in
503 the DDG. We assume the loop has a single basic block. */
505 build_intra_loop_deps (ddg_ptr g
)
508 /* Hold the dependency analysis state during dependency calculations. */
509 struct deps_desc tmp_deps
;
510 rtx_insn
*head
, *tail
;
512 /* Build the dependence information, using the sched_analyze function. */
514 init_deps (&tmp_deps
, false);
516 /* Do the intra-block data dependence analysis for the given block. */
517 get_ebb_head_tail (g
->bb
, g
->bb
, &head
, &tail
);
518 sched_analyze (&tmp_deps
, head
, tail
);
520 /* Build intra-loop data dependencies using the scheduler dependency
522 for (i
= 0; i
< g
->num_nodes
; i
++)
524 ddg_node_ptr dest_node
= &g
->nodes
[i
];
525 sd_iterator_def sd_it
;
528 if (! INSN_P (dest_node
->insn
))
531 FOR_EACH_DEP (dest_node
->insn
, SD_LIST_BACK
, sd_it
, dep
)
533 rtx_insn
*src_insn
= DEP_PRO (dep
);
534 ddg_node_ptr src_node
;
536 /* Don't add dependencies on debug insns to non-debug insns
537 to avoid codegen differences between -g and -g0. */
538 if (DEBUG_INSN_P (src_insn
) && !DEBUG_INSN_P (dest_node
->insn
))
541 src_node
= get_node_of_insn (g
, src_insn
);
546 create_ddg_dep_from_intra_loop_link (g
, src_node
, dest_node
, dep
);
549 /* If this insn modifies memory, add an edge to all insns that access
551 if (mem_access_insn_p (dest_node
->insn
))
555 for (j
= 0; j
<= i
; j
++)
557 ddg_node_ptr j_node
= &g
->nodes
[j
];
558 if (DEBUG_INSN_P (j_node
->insn
))
560 if (mem_access_insn_p (j_node
->insn
))
562 /* Don't bother calculating inter-loop dep if an intra-loop dep
564 if (! bitmap_bit_p (dest_node
->successors
, j
))
565 add_inter_loop_mem_dep (g
, dest_node
, j_node
);
566 /* If -fmodulo-sched-allow-regmoves
567 is set certain anti-dep edges are not created.
568 It might be that these anti-dep edges are on the
569 path from one memory instruction to another such that
570 removing these edges could cause a violation of the
571 memory dependencies. Thus we add intra edges between
572 every two memory instructions in this case. */
573 if (flag_modulo_sched_allow_regmoves
574 && !bitmap_bit_p (dest_node
->predecessors
, j
))
575 add_intra_loop_mem_dep (g
, j_node
, dest_node
);
581 /* Free the INSN_LISTs. */
582 finish_deps_global ();
583 free_deps (&tmp_deps
);
585 /* Free dependencies. */
586 sched_free_deps (head
, tail
, false);
590 /* Given a basic block, create its DDG and return a pointer to a variable
591 of ddg type that represents it.
592 Initialize the ddg structure fields to the appropriate values. */
594 create_ddg (basic_block bb
, int closing_branch_deps
)
597 rtx_insn
*insn
, *first_note
;
601 g
= (ddg_ptr
) xcalloc (1, sizeof (struct ddg
));
604 g
->closing_branch_deps
= closing_branch_deps
;
606 /* Count the number of insns in the BB. */
607 for (insn
= BB_HEAD (bb
); insn
!= NEXT_INSN (BB_END (bb
));
608 insn
= NEXT_INSN (insn
))
610 if (! INSN_P (insn
) || GET_CODE (PATTERN (insn
)) == USE
)
613 if (DEBUG_INSN_P (insn
))
617 if (mem_read_insn_p (insn
))
619 if (mem_write_insn_p (insn
))
625 /* There is nothing to do for this BB. */
626 if ((num_nodes
- g
->num_debug
) <= 1)
632 /* Allocate the nodes array, and initialize the nodes. */
633 g
->num_nodes
= num_nodes
;
634 g
->nodes
= (ddg_node_ptr
) xcalloc (num_nodes
, sizeof (struct ddg_node
));
635 g
->closing_branch
= NULL
;
638 for (insn
= BB_HEAD (bb
); insn
!= NEXT_INSN (BB_END (bb
));
639 insn
= NEXT_INSN (insn
))
643 if (! first_note
&& NOTE_P (insn
)
644 && NOTE_KIND (insn
) != NOTE_INSN_BASIC_BLOCK
)
650 gcc_assert (!g
->closing_branch
);
651 g
->closing_branch
= &g
->nodes
[i
];
653 else if (GET_CODE (PATTERN (insn
)) == USE
)
660 g
->nodes
[i
].cuid
= i
;
661 g
->nodes
[i
].successors
= sbitmap_alloc (num_nodes
);
662 bitmap_clear (g
->nodes
[i
].successors
);
663 g
->nodes
[i
].predecessors
= sbitmap_alloc (num_nodes
);
664 bitmap_clear (g
->nodes
[i
].predecessors
);
665 g
->nodes
[i
].first_note
= (first_note
? first_note
: insn
);
666 g
->nodes
[i
++].insn
= insn
;
670 /* We must have found a branch in DDG. */
671 gcc_assert (g
->closing_branch
);
674 /* Build the data dependency graph. */
675 build_intra_loop_deps (g
);
676 build_inter_loop_deps (g
);
680 /* Free all the memory allocated for the DDG. */
689 for (i
= 0; i
< g
->num_nodes
; i
++)
691 ddg_edge_ptr e
= g
->nodes
[i
].out
;
695 ddg_edge_ptr next
= e
->next_out
;
700 sbitmap_free (g
->nodes
[i
].successors
);
701 sbitmap_free (g
->nodes
[i
].predecessors
);
703 if (g
->num_backarcs
> 0)
710 print_ddg_edge (FILE *file
, ddg_edge_ptr e
)
726 fprintf (file
, " [%d -(%c,%d,%d)-> %d] ", INSN_UID (e
->src
->insn
),
727 dep_c
, e
->latency
, e
->distance
, INSN_UID (e
->dest
->insn
));
730 /* Print the DDG nodes with there in/out edges to the dump file. */
732 print_ddg (FILE *file
, ddg_ptr g
)
736 for (i
= 0; i
< g
->num_nodes
; i
++)
740 fprintf (file
, "Node num: %d\n", g
->nodes
[i
].cuid
);
741 print_rtl_single (file
, g
->nodes
[i
].insn
);
742 fprintf (file
, "OUT ARCS: ");
743 for (e
= g
->nodes
[i
].out
; e
; e
= e
->next_out
)
744 print_ddg_edge (file
, e
);
746 fprintf (file
, "\nIN ARCS: ");
747 for (e
= g
->nodes
[i
].in
; e
; e
= e
->next_in
)
748 print_ddg_edge (file
, e
);
750 fprintf (file
, "\n");
754 /* Print the given DDG in VCG format. */
756 vcg_print_ddg (FILE *file
, ddg_ptr g
)
760 fprintf (file
, "graph: {\n");
761 for (src_cuid
= 0; src_cuid
< g
->num_nodes
; src_cuid
++)
764 int src_uid
= INSN_UID (g
->nodes
[src_cuid
].insn
);
766 fprintf (file
, "node: {title: \"%d_%d\" info1: \"", src_cuid
, src_uid
);
767 print_rtl_single (file
, g
->nodes
[src_cuid
].insn
);
768 fprintf (file
, "\"}\n");
769 for (e
= g
->nodes
[src_cuid
].out
; e
; e
= e
->next_out
)
771 int dst_uid
= INSN_UID (e
->dest
->insn
);
772 int dst_cuid
= e
->dest
->cuid
;
774 /* Give the backarcs a different color. */
776 fprintf (file
, "backedge: {color: red ");
778 fprintf (file
, "edge: { ");
780 fprintf (file
, "sourcename: \"%d_%d\" ", src_cuid
, src_uid
);
781 fprintf (file
, "targetname: \"%d_%d\" ", dst_cuid
, dst_uid
);
782 fprintf (file
, "label: \"%d_%d\"}\n", e
->latency
, e
->distance
);
785 fprintf (file
, "}\n");
788 /* Dump the sccs in SCCS. */
790 print_sccs (FILE *file
, ddg_all_sccs_ptr sccs
, ddg_ptr g
)
793 sbitmap_iterator sbi
;
799 fprintf (file
, "\n;; Number of SCC nodes - %d\n", sccs
->num_sccs
);
800 for (i
= 0; i
< sccs
->num_sccs
; i
++)
802 fprintf (file
, "SCC number: %d\n", i
);
803 EXECUTE_IF_SET_IN_BITMAP (sccs
->sccs
[i
]->nodes
, 0, u
, sbi
)
805 fprintf (file
, "insn num %d\n", u
);
806 print_rtl_single (file
, g
->nodes
[u
].insn
);
809 fprintf (file
, "\n");
812 /* Create an edge and initialize it with given values. */
814 create_ddg_edge (ddg_node_ptr src
, ddg_node_ptr dest
,
815 dep_type t
, dep_data_type dt
, int l
, int d
)
817 ddg_edge_ptr e
= (ddg_edge_ptr
) xmalloc (sizeof (struct ddg_edge
));
825 e
->next_in
= e
->next_out
= NULL
;
830 /* Add the given edge to the in/out linked lists of the DDG nodes. */
832 add_edge_to_ddg (ddg_ptr g ATTRIBUTE_UNUSED
, ddg_edge_ptr e
)
834 ddg_node_ptr src
= e
->src
;
835 ddg_node_ptr dest
= e
->dest
;
837 /* Should have allocated the sbitmaps. */
838 gcc_assert (src
->successors
&& dest
->predecessors
);
840 bitmap_set_bit (src
->successors
, dest
->cuid
);
841 bitmap_set_bit (dest
->predecessors
, src
->cuid
);
842 e
->next_in
= dest
->in
;
844 e
->next_out
= src
->out
;
850 /* Algorithm for computing the recurrence_length of an scc. We assume at
851 for now that cycles in the data dependence graph contain a single backarc.
852 This simplifies the algorithm, and can be generalized later. */
854 set_recurrence_length (ddg_scc_ptr scc
, ddg_ptr g
)
859 for (j
= 0; j
< scc
->num_backarcs
; j
++)
861 ddg_edge_ptr backarc
= scc
->backarcs
[j
];
863 int distance
= backarc
->distance
;
864 ddg_node_ptr src
= backarc
->dest
;
865 ddg_node_ptr dest
= backarc
->src
;
867 length
= longest_simple_path (g
, src
->cuid
, dest
->cuid
, scc
->nodes
);
870 /* fprintf (stderr, "Backarc not on simple cycle in SCC.\n"); */
873 length
+= backarc
->latency
;
874 result
= MAX (result
, (length
/ distance
));
876 scc
->recurrence_length
= result
;
879 /* Create a new SCC given the set of its nodes. Compute its recurrence_length
880 and mark edges that belong to this scc as IN_SCC. */
882 create_scc (ddg_ptr g
, sbitmap nodes
)
886 sbitmap_iterator sbi
;
888 scc
= (ddg_scc_ptr
) xmalloc (sizeof (struct ddg_scc
));
889 scc
->backarcs
= NULL
;
890 scc
->num_backarcs
= 0;
891 scc
->nodes
= sbitmap_alloc (g
->num_nodes
);
892 bitmap_copy (scc
->nodes
, nodes
);
894 /* Mark the backarcs that belong to this SCC. */
895 EXECUTE_IF_SET_IN_BITMAP (nodes
, 0, u
, sbi
)
898 ddg_node_ptr n
= &g
->nodes
[u
];
900 for (e
= n
->out
; e
; e
= e
->next_out
)
901 if (bitmap_bit_p (nodes
, e
->dest
->cuid
))
903 e
->aux
.count
= IN_SCC
;
905 add_backarc_to_scc (scc
, e
);
909 set_recurrence_length (scc
, g
);
913 /* Cleans the memory allocation of a given SCC. */
915 free_scc (ddg_scc_ptr scc
)
920 sbitmap_free (scc
->nodes
);
921 if (scc
->num_backarcs
> 0)
922 free (scc
->backarcs
);
927 /* Add a given edge known to be a backarc to the given DDG. */
929 add_backarc_to_ddg (ddg_ptr g
, ddg_edge_ptr e
)
931 int size
= (g
->num_backarcs
+ 1) * sizeof (ddg_edge_ptr
);
933 add_edge_to_ddg (g
, e
);
934 g
->backarcs
= (ddg_edge_ptr
*) xrealloc (g
->backarcs
, size
);
935 g
->backarcs
[g
->num_backarcs
++] = e
;
938 /* Add backarc to an SCC. */
940 add_backarc_to_scc (ddg_scc_ptr scc
, ddg_edge_ptr e
)
942 int size
= (scc
->num_backarcs
+ 1) * sizeof (ddg_edge_ptr
);
944 scc
->backarcs
= (ddg_edge_ptr
*) xrealloc (scc
->backarcs
, size
);
945 scc
->backarcs
[scc
->num_backarcs
++] = e
;
948 /* Add the given SCC to the DDG. */
950 add_scc_to_ddg (ddg_all_sccs_ptr g
, ddg_scc_ptr scc
)
952 int size
= (g
->num_sccs
+ 1) * sizeof (ddg_scc_ptr
);
954 g
->sccs
= (ddg_scc_ptr
*) xrealloc (g
->sccs
, size
);
955 g
->sccs
[g
->num_sccs
++] = scc
;
958 /* Given the instruction INSN return the node that represents it. */
960 get_node_of_insn (ddg_ptr g
, rtx_insn
*insn
)
964 for (i
= 0; i
< g
->num_nodes
; i
++)
965 if (insn
== g
->nodes
[i
].insn
)
970 /* Given a set OPS of nodes in the DDG, find the set of their successors
971 which are not in OPS, and set their bits in SUCC. Bits corresponding to
972 OPS are cleared from SUCC. Leaves the other bits in SUCC unchanged. */
974 find_successors (sbitmap succ
, ddg_ptr g
, sbitmap ops
)
977 sbitmap_iterator sbi
;
979 EXECUTE_IF_SET_IN_BITMAP (ops
, 0, i
, sbi
)
981 const sbitmap node_succ
= NODE_SUCCESSORS (&g
->nodes
[i
]);
982 bitmap_ior (succ
, succ
, node_succ
);
985 /* We want those that are not in ops. */
986 bitmap_and_compl (succ
, succ
, ops
);
989 /* Given a set OPS of nodes in the DDG, find the set of their predecessors
990 which are not in OPS, and set their bits in PREDS. Bits corresponding to
991 OPS are cleared from PREDS. Leaves the other bits in PREDS unchanged. */
993 find_predecessors (sbitmap preds
, ddg_ptr g
, sbitmap ops
)
996 sbitmap_iterator sbi
;
998 EXECUTE_IF_SET_IN_BITMAP (ops
, 0, i
, sbi
)
1000 const sbitmap node_preds
= NODE_PREDECESSORS (&g
->nodes
[i
]);
1001 bitmap_ior (preds
, preds
, node_preds
);
1004 /* We want those that are not in ops. */
1005 bitmap_and_compl (preds
, preds
, ops
);
1009 /* Compare function to be passed to qsort to order the backarcs in descending
1012 compare_sccs (const void *s1
, const void *s2
)
1014 const int rec_l1
= (*(const ddg_scc_ptr
*)s1
)->recurrence_length
;
1015 const int rec_l2
= (*(const ddg_scc_ptr
*)s2
)->recurrence_length
;
1016 return ((rec_l2
> rec_l1
) - (rec_l2
< rec_l1
));
1020 /* Order the backarcs in descending recMII order using compare_sccs. */
1022 order_sccs (ddg_all_sccs_ptr g
)
1024 qsort (g
->sccs
, g
->num_sccs
, sizeof (ddg_scc_ptr
),
1025 (int (*) (const void *, const void *)) compare_sccs
);
1028 #ifdef ENABLE_CHECKING
1029 /* Check that every node in SCCS belongs to exactly one strongly connected
1030 component and that no element of SCCS is empty. */
1032 check_sccs (ddg_all_sccs_ptr sccs
, int num_nodes
)
1035 sbitmap tmp
= sbitmap_alloc (num_nodes
);
1038 for (i
= 0; i
< sccs
->num_sccs
; i
++)
1040 gcc_assert (!bitmap_empty_p (sccs
->sccs
[i
]->nodes
));
1041 /* Verify that every node in sccs is in exactly one strongly
1042 connected component. */
1043 gcc_assert (!bitmap_intersect_p (tmp
, sccs
->sccs
[i
]->nodes
));
1044 bitmap_ior (tmp
, tmp
, sccs
->sccs
[i
]->nodes
);
1050 /* Perform the Strongly Connected Components decomposing algorithm on the
1051 DDG and return DDG_ALL_SCCS structure that contains them. */
1053 create_ddg_all_sccs (ddg_ptr g
)
1056 int num_nodes
= g
->num_nodes
;
1057 sbitmap from
= sbitmap_alloc (num_nodes
);
1058 sbitmap to
= sbitmap_alloc (num_nodes
);
1059 sbitmap scc_nodes
= sbitmap_alloc (num_nodes
);
1060 ddg_all_sccs_ptr sccs
= (ddg_all_sccs_ptr
)
1061 xmalloc (sizeof (struct ddg_all_sccs
));
1067 for (i
= 0; i
< g
->num_backarcs
; i
++)
1070 ddg_edge_ptr backarc
= g
->backarcs
[i
];
1071 ddg_node_ptr src
= backarc
->src
;
1072 ddg_node_ptr dest
= backarc
->dest
;
1074 /* If the backarc already belongs to an SCC, continue. */
1075 if (backarc
->aux
.count
== IN_SCC
)
1078 bitmap_clear (scc_nodes
);
1079 bitmap_clear (from
);
1081 bitmap_set_bit (from
, dest
->cuid
);
1082 bitmap_set_bit (to
, src
->cuid
);
1084 if (find_nodes_on_paths (scc_nodes
, g
, from
, to
))
1086 scc
= create_scc (g
, scc_nodes
);
1087 add_scc_to_ddg (sccs
, scc
);
1091 sbitmap_free (from
);
1093 sbitmap_free (scc_nodes
);
1094 #ifdef ENABLE_CHECKING
1095 check_sccs (sccs
, num_nodes
);
1100 /* Frees the memory allocated for all SCCs of the DDG, but keeps the DDG. */
1102 free_ddg_all_sccs (ddg_all_sccs_ptr all_sccs
)
1109 for (i
= 0; i
< all_sccs
->num_sccs
; i
++)
1110 free_scc (all_sccs
->sccs
[i
]);
1112 free (all_sccs
->sccs
);
1117 /* Given FROM - a bitmap of source nodes - and TO - a bitmap of destination
1118 nodes - find all nodes that lie on paths from FROM to TO (not excluding
1119 nodes from FROM and TO). Return nonzero if nodes exist. */
1121 find_nodes_on_paths (sbitmap result
, ddg_ptr g
, sbitmap from
, sbitmap to
)
1126 int num_nodes
= g
->num_nodes
;
1127 sbitmap_iterator sbi
;
1129 sbitmap workset
= sbitmap_alloc (num_nodes
);
1130 sbitmap reachable_from
= sbitmap_alloc (num_nodes
);
1131 sbitmap reach_to
= sbitmap_alloc (num_nodes
);
1132 sbitmap tmp
= sbitmap_alloc (num_nodes
);
1134 bitmap_copy (reachable_from
, from
);
1135 bitmap_copy (tmp
, from
);
1141 bitmap_copy (workset
, tmp
);
1143 EXECUTE_IF_SET_IN_BITMAP (workset
, 0, u
, sbi
)
1146 ddg_node_ptr u_node
= &g
->nodes
[u
];
1148 for (e
= u_node
->out
; e
!= (ddg_edge_ptr
) 0; e
= e
->next_out
)
1150 ddg_node_ptr v_node
= e
->dest
;
1151 int v
= v_node
->cuid
;
1153 if (!bitmap_bit_p (reachable_from
, v
))
1155 bitmap_set_bit (reachable_from
, v
);
1156 bitmap_set_bit (tmp
, v
);
1163 bitmap_copy (reach_to
, to
);
1164 bitmap_copy (tmp
, to
);
1170 bitmap_copy (workset
, tmp
);
1172 EXECUTE_IF_SET_IN_BITMAP (workset
, 0, u
, sbi
)
1175 ddg_node_ptr u_node
= &g
->nodes
[u
];
1177 for (e
= u_node
->in
; e
!= (ddg_edge_ptr
) 0; e
= e
->next_in
)
1179 ddg_node_ptr v_node
= e
->src
;
1180 int v
= v_node
->cuid
;
1182 if (!bitmap_bit_p (reach_to
, v
))
1184 bitmap_set_bit (reach_to
, v
);
1185 bitmap_set_bit (tmp
, v
);
1192 answer
= bitmap_and (result
, reachable_from
, reach_to
);
1193 sbitmap_free (workset
);
1194 sbitmap_free (reachable_from
);
1195 sbitmap_free (reach_to
);
1201 /* Updates the counts of U_NODE's successors (that belong to NODES) to be
1202 at-least as large as the count of U_NODE plus the latency between them.
1203 Sets a bit in TMP for each successor whose count was changed (increased).
1204 Returns nonzero if any count was changed. */
1206 update_dist_to_successors (ddg_node_ptr u_node
, sbitmap nodes
, sbitmap tmp
)
1211 for (e
= u_node
->out
; e
; e
= e
->next_out
)
1213 ddg_node_ptr v_node
= e
->dest
;
1214 int v
= v_node
->cuid
;
1216 if (bitmap_bit_p (nodes
, v
)
1217 && (e
->distance
== 0)
1218 && (v_node
->aux
.count
< u_node
->aux
.count
+ e
->latency
))
1220 v_node
->aux
.count
= u_node
->aux
.count
+ e
->latency
;
1221 bitmap_set_bit (tmp
, v
);
1229 /* Find the length of a longest path from SRC to DEST in G,
1230 going only through NODES, and disregarding backarcs. */
1232 longest_simple_path (struct ddg
* g
, int src
, int dest
, sbitmap nodes
)
1238 int num_nodes
= g
->num_nodes
;
1239 sbitmap workset
= sbitmap_alloc (num_nodes
);
1240 sbitmap tmp
= sbitmap_alloc (num_nodes
);
1243 /* Data will hold the distance of the longest path found so far from
1244 src to each node. Initialize to -1 = less than minimum. */
1245 for (i
= 0; i
< g
->num_nodes
; i
++)
1246 g
->nodes
[i
].aux
.count
= -1;
1247 g
->nodes
[src
].aux
.count
= 0;
1250 bitmap_set_bit (tmp
, src
);
1254 sbitmap_iterator sbi
;
1257 bitmap_copy (workset
, tmp
);
1259 EXECUTE_IF_SET_IN_BITMAP (workset
, 0, u
, sbi
)
1261 ddg_node_ptr u_node
= &g
->nodes
[u
];
1263 change
|= update_dist_to_successors (u_node
, nodes
, tmp
);
1266 result
= g
->nodes
[dest
].aux
.count
;
1267 sbitmap_free (workset
);
1272 #endif /* INSN_SCHEDULING */