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"
46 #ifdef INSN_SCHEDULING
48 /* A flag indicating that a ddg edge belongs to an SCC or not. */
49 enum edge_flag
{NOT_IN_SCC
= 0, IN_SCC
};
51 /* Forward declarations. */
52 static void add_backarc_to_ddg (ddg_ptr
, ddg_edge_ptr
);
53 static void add_backarc_to_scc (ddg_scc_ptr
, ddg_edge_ptr
);
54 static void add_scc_to_ddg (ddg_all_sccs_ptr
, ddg_scc_ptr
);
55 static void create_ddg_dep_from_intra_loop_link (ddg_ptr
, ddg_node_ptr
,
57 static void create_ddg_dep_no_link (ddg_ptr
, ddg_node_ptr
, ddg_node_ptr
,
58 dep_type
, dep_data_type
, int);
59 static ddg_edge_ptr
create_ddg_edge (ddg_node_ptr
, ddg_node_ptr
, dep_type
,
60 dep_data_type
, int, int);
61 static void add_edge_to_ddg (ddg_ptr g
, ddg_edge_ptr
);
63 /* Auxiliary variable for mem_read_insn_p/mem_write_insn_p. */
64 static bool mem_ref_p
;
66 /* Auxiliary function for mem_read_insn_p. */
68 mark_mem_use (rtx
*x
, void *)
70 subrtx_iterator::array_type array
;
71 FOR_EACH_SUBRTX (iter
, array
, *x
, NONCONST
)
79 /* Returns nonzero if INSN reads from memory. */
81 mem_read_insn_p (rtx_insn
*insn
)
84 note_uses (&PATTERN (insn
), mark_mem_use
, NULL
);
89 mark_mem_store (rtx loc
, const_rtx setter ATTRIBUTE_UNUSED
, void *data ATTRIBUTE_UNUSED
)
95 /* Returns nonzero if INSN writes to memory. */
97 mem_write_insn_p (rtx_insn
*insn
)
100 note_stores (PATTERN (insn
), mark_mem_store
, NULL
);
104 /* Returns nonzero if X has access to memory. */
106 rtx_mem_access_p (rtx x
)
119 fmt
= GET_RTX_FORMAT (code
);
120 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
124 if (rtx_mem_access_p (XEXP (x
, i
)))
127 else if (fmt
[i
] == 'E')
128 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
130 if (rtx_mem_access_p (XVECEXP (x
, i
, j
)))
137 /* Returns nonzero if INSN reads to or writes from memory. */
139 mem_access_insn_p (rtx_insn
*insn
)
141 return rtx_mem_access_p (PATTERN (insn
));
144 /* Return true if DEF_INSN contains address being auto-inc or auto-dec
145 which is used in USE_INSN. Otherwise return false. The result is
146 being used to decide whether to remove the edge between def_insn and
147 use_insn when -fmodulo-sched-allow-regmoves is set. This function
148 doesn't need to consider the specific address register; no reg_moves
149 will be allowed for any life range defined by def_insn and used
150 by use_insn, if use_insn uses an address register auto-inc'ed by
153 autoinc_var_is_used_p (rtx_insn
*def_insn
, rtx_insn
*use_insn
)
157 for (note
= REG_NOTES (def_insn
); note
; note
= XEXP (note
, 1))
158 if (REG_NOTE_KIND (note
) == REG_INC
159 && reg_referenced_p (XEXP (note
, 0), PATTERN (use_insn
)))
165 /* Return true if one of the definitions in INSN has MODE_CC. Otherwise
168 def_has_ccmode_p (rtx_insn
*insn
)
172 FOR_EACH_INSN_DEF (def
, insn
)
174 enum machine_mode mode
= GET_MODE (DF_REF_REG (def
));
176 if (GET_MODE_CLASS (mode
) == MODE_CC
)
183 /* Computes the dependence parameters (latency, distance etc.), creates
184 a ddg_edge and adds it to the given DDG. */
186 create_ddg_dep_from_intra_loop_link (ddg_ptr g
, ddg_node_ptr src_node
,
187 ddg_node_ptr dest_node
, dep_t link
)
190 int latency
, distance
= 0;
191 dep_type t
= TRUE_DEP
;
192 dep_data_type dt
= (mem_access_insn_p (src_node
->insn
)
193 && mem_access_insn_p (dest_node
->insn
) ? MEM_DEP
195 gcc_assert (src_node
->cuid
< dest_node
->cuid
);
198 /* Note: REG_DEP_ANTI applies to MEM ANTI_DEP as well!! */
199 if (DEP_TYPE (link
) == REG_DEP_ANTI
)
201 else if (DEP_TYPE (link
) == REG_DEP_OUTPUT
)
204 gcc_assert (!DEBUG_INSN_P (dest_node
->insn
) || t
== ANTI_DEP
);
205 gcc_assert (!DEBUG_INSN_P (src_node
->insn
) || t
== ANTI_DEP
);
207 /* We currently choose not to create certain anti-deps edges and
208 compensate for that by generating reg-moves based on the life-range
209 analysis. The anti-deps that will be deleted are the ones which
210 have true-deps edges in the opposite direction (in other words
211 the kernel has only one def of the relevant register).
212 If the address that is being auto-inc or auto-dec in DEST_NODE
213 is used in SRC_NODE then do not remove the edge to make sure
214 reg-moves will not be created for this address.
215 TODO: support the removal of all anti-deps edges, i.e. including those
216 whose register has multiple defs in the loop. */
217 if (flag_modulo_sched_allow_regmoves
218 && (t
== ANTI_DEP
&& dt
== REG_DEP
)
219 && !def_has_ccmode_p (dest_node
->insn
)
220 && !autoinc_var_is_used_p (dest_node
->insn
, src_node
->insn
))
224 set
= single_set (dest_node
->insn
);
225 /* TODO: Handle registers that REG_P is not true for them, i.e.
226 subregs and special registers. */
227 if (set
&& REG_P (SET_DEST (set
)))
229 int regno
= REGNO (SET_DEST (set
));
231 struct df_rd_bb_info
*bb_info
= DF_RD_BB_INFO (g
->bb
);
233 first_def
= df_bb_regno_first_def_find (g
->bb
, regno
);
234 gcc_assert (first_def
);
236 if (bitmap_bit_p (&bb_info
->gen
, DF_REF_ID (first_def
)))
241 latency
= dep_cost (link
);
242 e
= create_ddg_edge (src_node
, dest_node
, t
, dt
, latency
, distance
);
243 add_edge_to_ddg (g
, e
);
246 /* The same as the above function, but it doesn't require a link parameter. */
248 create_ddg_dep_no_link (ddg_ptr g
, ddg_node_ptr from
, ddg_node_ptr to
,
249 dep_type d_t
, dep_data_type d_dt
, int distance
)
253 enum reg_note dep_kind
;
254 struct _dep _dep
, *dep
= &_dep
;
256 gcc_assert (!DEBUG_INSN_P (to
->insn
) || d_t
== ANTI_DEP
);
257 gcc_assert (!DEBUG_INSN_P (from
->insn
) || d_t
== ANTI_DEP
);
260 dep_kind
= REG_DEP_ANTI
;
261 else if (d_t
== OUTPUT_DEP
)
262 dep_kind
= REG_DEP_OUTPUT
;
265 gcc_assert (d_t
== TRUE_DEP
);
267 dep_kind
= REG_DEP_TRUE
;
270 init_dep (dep
, from
->insn
, to
->insn
, dep_kind
);
274 e
= create_ddg_edge (from
, to
, d_t
, d_dt
, l
, distance
);
276 add_backarc_to_ddg (g
, e
);
278 add_edge_to_ddg (g
, e
);
282 /* Given a downwards exposed register def LAST_DEF (which is the last
283 definition of that register in the bb), add inter-loop true dependences
284 to all its uses in the next iteration, an output dependence to the
285 first def of the same register (possibly itself) in the next iteration
286 and anti-dependences from its uses in the current iteration to the
287 first definition in the next iteration. */
289 add_cross_iteration_register_deps (ddg_ptr g
, df_ref last_def
)
291 int regno
= DF_REF_REGNO (last_def
);
292 struct df_link
*r_use
;
293 int has_use_in_bb_p
= false;
294 rtx_insn
*def_insn
= DF_REF_INSN (last_def
);
295 ddg_node_ptr last_def_node
= get_node_of_insn (g
, def_insn
);
296 ddg_node_ptr use_node
;
297 #ifdef ENABLE_CHECKING
298 struct df_rd_bb_info
*bb_info
= DF_RD_BB_INFO (g
->bb
);
300 df_ref first_def
= df_bb_regno_first_def_find (g
->bb
, regno
);
302 gcc_assert (last_def_node
);
303 gcc_assert (first_def
);
305 #ifdef ENABLE_CHECKING
306 if (DF_REF_ID (last_def
) != DF_REF_ID (first_def
))
307 gcc_assert (!bitmap_bit_p (&bb_info
->gen
,
308 DF_REF_ID (first_def
)));
311 /* Create inter-loop true dependences and anti dependences. */
312 for (r_use
= DF_REF_CHAIN (last_def
); r_use
!= NULL
; r_use
= r_use
->next
)
314 rtx_insn
*use_insn
= DF_REF_INSN (r_use
->ref
);
316 if (BLOCK_FOR_INSN (use_insn
) != g
->bb
)
319 /* ??? Do not handle uses with DF_REF_IN_NOTE notes. */
320 use_node
= get_node_of_insn (g
, use_insn
);
321 gcc_assert (use_node
);
322 has_use_in_bb_p
= true;
323 if (use_node
->cuid
<= last_def_node
->cuid
)
325 /* Add true deps from last_def to it's uses in the next
326 iteration. Any such upwards exposed use appears before
328 create_ddg_dep_no_link (g
, last_def_node
, use_node
,
329 DEBUG_INSN_P (use_insn
) ? ANTI_DEP
: TRUE_DEP
,
332 else if (!DEBUG_INSN_P (use_insn
))
334 /* Add anti deps from last_def's uses in the current iteration
335 to the first def in the next iteration. We do not add ANTI
336 dep when there is an intra-loop TRUE dep in the opposite
337 direction, but use regmoves to fix such disregarded ANTI
338 deps when broken. If the first_def reaches the USE then
339 there is such a dep. */
340 ddg_node_ptr first_def_node
= get_node_of_insn (g
,
341 DF_REF_INSN (first_def
));
343 gcc_assert (first_def_node
);
345 /* Always create the edge if the use node is a branch in
346 order to prevent the creation of reg-moves.
347 If the address that is being auto-inc or auto-dec in LAST_DEF
348 is used in USE_INSN then do not remove the edge to make sure
349 reg-moves will not be created for that address. */
350 if (DF_REF_ID (last_def
) != DF_REF_ID (first_def
)
351 || !flag_modulo_sched_allow_regmoves
352 || JUMP_P (use_node
->insn
)
353 || autoinc_var_is_used_p (DF_REF_INSN (last_def
), use_insn
)
354 || def_has_ccmode_p (DF_REF_INSN (last_def
)))
355 create_ddg_dep_no_link (g
, use_node
, first_def_node
, ANTI_DEP
,
360 /* Create an inter-loop output dependence between LAST_DEF (which is the
361 last def in its block, being downwards exposed) and the first def in
362 its block. Avoid creating a self output dependence. Avoid creating
363 an output dependence if there is a dependence path between the two
364 defs starting with a true dependence to a use which can be in the
365 next iteration; followed by an anti dependence of that use to the
366 first def (i.e. if there is a use between the two defs.) */
367 if (!has_use_in_bb_p
)
369 ddg_node_ptr dest_node
;
371 if (DF_REF_ID (last_def
) == DF_REF_ID (first_def
))
374 dest_node
= get_node_of_insn (g
, DF_REF_INSN (first_def
));
375 gcc_assert (dest_node
);
376 create_ddg_dep_no_link (g
, last_def_node
, dest_node
,
377 OUTPUT_DEP
, REG_DEP
, 1);
380 /* Build inter-loop dependencies, by looking at DF analysis backwards. */
382 build_inter_loop_deps (ddg_ptr g
)
385 struct df_rd_bb_info
*rd_bb_info
;
388 rd_bb_info
= DF_RD_BB_INFO (g
->bb
);
390 /* Find inter-loop register output, true and anti deps. */
391 EXECUTE_IF_SET_IN_BITMAP (&rd_bb_info
->gen
, 0, rd_num
, bi
)
393 df_ref rd
= DF_DEFS_GET (rd_num
);
395 add_cross_iteration_register_deps (g
, rd
);
401 walk_mems_2 (rtx
*x
, rtx mem
)
405 if (may_alias_p (*x
, mem
))
414 walk_mems_1 (rtx
*x
, rtx
*pat
)
418 /* Visit all MEMs in *PAT and check independence. */
419 if (for_each_rtx (pat
, (rtx_function
) walk_mems_2
, *x
))
420 /* Indicate that dependence was determined and stop traversal. */
428 /* Return 1 if two specified instructions have mem expr with conflict alias sets*/
430 insns_may_alias_p (rtx_insn
*insn1
, rtx_insn
*insn2
)
432 /* For each pair of MEMs in INSN1 and INSN2 check their independence. */
433 return for_each_rtx (&PATTERN (insn1
), (rtx_function
) walk_mems_1
,
437 /* Given two nodes, analyze their RTL insns and add intra-loop mem deps
440 add_intra_loop_mem_dep (ddg_ptr g
, ddg_node_ptr from
, ddg_node_ptr to
)
443 if ((from
->cuid
== to
->cuid
)
444 || !insns_may_alias_p (from
->insn
, to
->insn
))
445 /* Do not create edge if memory references have disjoint alias sets
446 or 'to' and 'from' are the same instruction. */
449 if (mem_write_insn_p (from
->insn
))
451 if (mem_read_insn_p (to
->insn
))
452 create_ddg_dep_no_link (g
, from
, to
,
453 DEBUG_INSN_P (to
->insn
)
454 ? ANTI_DEP
: TRUE_DEP
, MEM_DEP
, 0);
456 create_ddg_dep_no_link (g
, from
, to
,
457 DEBUG_INSN_P (to
->insn
)
458 ? ANTI_DEP
: OUTPUT_DEP
, MEM_DEP
, 0);
460 else if (!mem_read_insn_p (to
->insn
))
461 create_ddg_dep_no_link (g
, from
, to
, ANTI_DEP
, MEM_DEP
, 0);
464 /* Given two nodes, analyze their RTL insns and add inter-loop mem deps
467 add_inter_loop_mem_dep (ddg_ptr g
, ddg_node_ptr from
, ddg_node_ptr to
)
469 if (!insns_may_alias_p (from
->insn
, to
->insn
))
470 /* Do not create edge if memory references have disjoint alias sets. */
473 if (mem_write_insn_p (from
->insn
))
475 if (mem_read_insn_p (to
->insn
))
476 create_ddg_dep_no_link (g
, from
, to
,
477 DEBUG_INSN_P (to
->insn
)
478 ? ANTI_DEP
: TRUE_DEP
, MEM_DEP
, 1);
479 else if (from
->cuid
!= to
->cuid
)
480 create_ddg_dep_no_link (g
, from
, to
,
481 DEBUG_INSN_P (to
->insn
)
482 ? ANTI_DEP
: OUTPUT_DEP
, MEM_DEP
, 1);
486 if (mem_read_insn_p (to
->insn
))
488 else if (from
->cuid
!= to
->cuid
)
490 create_ddg_dep_no_link (g
, from
, to
, ANTI_DEP
, MEM_DEP
, 1);
491 if (DEBUG_INSN_P (from
->insn
) || DEBUG_INSN_P (to
->insn
))
492 create_ddg_dep_no_link (g
, to
, from
, ANTI_DEP
, MEM_DEP
, 1);
494 create_ddg_dep_no_link (g
, to
, from
, TRUE_DEP
, MEM_DEP
, 1);
500 /* Perform intra-block Data Dependency analysis and connect the nodes in
501 the DDG. We assume the loop has a single basic block. */
503 build_intra_loop_deps (ddg_ptr g
)
506 /* Hold the dependency analysis state during dependency calculations. */
507 struct deps_desc tmp_deps
;
508 rtx_insn
*head
, *tail
;
510 /* Build the dependence information, using the sched_analyze function. */
512 init_deps (&tmp_deps
, false);
514 /* Do the intra-block data dependence analysis for the given block. */
515 get_ebb_head_tail (g
->bb
, g
->bb
, &head
, &tail
);
516 sched_analyze (&tmp_deps
, head
, tail
);
518 /* Build intra-loop data dependencies using the scheduler dependency
520 for (i
= 0; i
< g
->num_nodes
; i
++)
522 ddg_node_ptr dest_node
= &g
->nodes
[i
];
523 sd_iterator_def sd_it
;
526 if (! INSN_P (dest_node
->insn
))
529 FOR_EACH_DEP (dest_node
->insn
, SD_LIST_BACK
, sd_it
, dep
)
531 rtx_insn
*src_insn
= DEP_PRO (dep
);
532 ddg_node_ptr src_node
;
534 /* Don't add dependencies on debug insns to non-debug insns
535 to avoid codegen differences between -g and -g0. */
536 if (DEBUG_INSN_P (src_insn
) && !DEBUG_INSN_P (dest_node
->insn
))
539 src_node
= get_node_of_insn (g
, src_insn
);
544 create_ddg_dep_from_intra_loop_link (g
, src_node
, dest_node
, dep
);
547 /* If this insn modifies memory, add an edge to all insns that access
549 if (mem_access_insn_p (dest_node
->insn
))
553 for (j
= 0; j
<= i
; j
++)
555 ddg_node_ptr j_node
= &g
->nodes
[j
];
556 if (DEBUG_INSN_P (j_node
->insn
))
558 if (mem_access_insn_p (j_node
->insn
))
560 /* Don't bother calculating inter-loop dep if an intra-loop dep
562 if (! bitmap_bit_p (dest_node
->successors
, j
))
563 add_inter_loop_mem_dep (g
, dest_node
, j_node
);
564 /* If -fmodulo-sched-allow-regmoves
565 is set certain anti-dep edges are not created.
566 It might be that these anti-dep edges are on the
567 path from one memory instruction to another such that
568 removing these edges could cause a violation of the
569 memory dependencies. Thus we add intra edges between
570 every two memory instructions in this case. */
571 if (flag_modulo_sched_allow_regmoves
572 && !bitmap_bit_p (dest_node
->predecessors
, j
))
573 add_intra_loop_mem_dep (g
, j_node
, dest_node
);
579 /* Free the INSN_LISTs. */
580 finish_deps_global ();
581 free_deps (&tmp_deps
);
583 /* Free dependencies. */
584 sched_free_deps (head
, tail
, false);
588 /* Given a basic block, create its DDG and return a pointer to a variable
589 of ddg type that represents it.
590 Initialize the ddg structure fields to the appropriate values. */
592 create_ddg (basic_block bb
, int closing_branch_deps
)
595 rtx_insn
*insn
, *first_note
;
599 g
= (ddg_ptr
) xcalloc (1, sizeof (struct ddg
));
602 g
->closing_branch_deps
= closing_branch_deps
;
604 /* Count the number of insns in the BB. */
605 for (insn
= BB_HEAD (bb
); insn
!= NEXT_INSN (BB_END (bb
));
606 insn
= NEXT_INSN (insn
))
608 if (! INSN_P (insn
) || GET_CODE (PATTERN (insn
)) == USE
)
611 if (DEBUG_INSN_P (insn
))
615 if (mem_read_insn_p (insn
))
617 if (mem_write_insn_p (insn
))
623 /* There is nothing to do for this BB. */
624 if ((num_nodes
- g
->num_debug
) <= 1)
630 /* Allocate the nodes array, and initialize the nodes. */
631 g
->num_nodes
= num_nodes
;
632 g
->nodes
= (ddg_node_ptr
) xcalloc (num_nodes
, sizeof (struct ddg_node
));
633 g
->closing_branch
= NULL
;
636 for (insn
= BB_HEAD (bb
); insn
!= NEXT_INSN (BB_END (bb
));
637 insn
= NEXT_INSN (insn
))
641 if (! first_note
&& NOTE_P (insn
)
642 && NOTE_KIND (insn
) != NOTE_INSN_BASIC_BLOCK
)
648 gcc_assert (!g
->closing_branch
);
649 g
->closing_branch
= &g
->nodes
[i
];
651 else if (GET_CODE (PATTERN (insn
)) == USE
)
658 g
->nodes
[i
].cuid
= i
;
659 g
->nodes
[i
].successors
= sbitmap_alloc (num_nodes
);
660 bitmap_clear (g
->nodes
[i
].successors
);
661 g
->nodes
[i
].predecessors
= sbitmap_alloc (num_nodes
);
662 bitmap_clear (g
->nodes
[i
].predecessors
);
663 g
->nodes
[i
].first_note
= (first_note
? first_note
: insn
);
664 g
->nodes
[i
++].insn
= insn
;
668 /* We must have found a branch in DDG. */
669 gcc_assert (g
->closing_branch
);
672 /* Build the data dependency graph. */
673 build_intra_loop_deps (g
);
674 build_inter_loop_deps (g
);
678 /* Free all the memory allocated for the DDG. */
687 for (i
= 0; i
< g
->num_nodes
; i
++)
689 ddg_edge_ptr e
= g
->nodes
[i
].out
;
693 ddg_edge_ptr next
= e
->next_out
;
698 sbitmap_free (g
->nodes
[i
].successors
);
699 sbitmap_free (g
->nodes
[i
].predecessors
);
701 if (g
->num_backarcs
> 0)
708 print_ddg_edge (FILE *file
, ddg_edge_ptr e
)
724 fprintf (file
, " [%d -(%c,%d,%d)-> %d] ", INSN_UID (e
->src
->insn
),
725 dep_c
, e
->latency
, e
->distance
, INSN_UID (e
->dest
->insn
));
728 /* Print the DDG nodes with there in/out edges to the dump file. */
730 print_ddg (FILE *file
, ddg_ptr g
)
734 for (i
= 0; i
< g
->num_nodes
; i
++)
738 fprintf (file
, "Node num: %d\n", g
->nodes
[i
].cuid
);
739 print_rtl_single (file
, g
->nodes
[i
].insn
);
740 fprintf (file
, "OUT ARCS: ");
741 for (e
= g
->nodes
[i
].out
; e
; e
= e
->next_out
)
742 print_ddg_edge (file
, e
);
744 fprintf (file
, "\nIN ARCS: ");
745 for (e
= g
->nodes
[i
].in
; e
; e
= e
->next_in
)
746 print_ddg_edge (file
, e
);
748 fprintf (file
, "\n");
752 /* Print the given DDG in VCG format. */
754 vcg_print_ddg (FILE *file
, ddg_ptr g
)
758 fprintf (file
, "graph: {\n");
759 for (src_cuid
= 0; src_cuid
< g
->num_nodes
; src_cuid
++)
762 int src_uid
= INSN_UID (g
->nodes
[src_cuid
].insn
);
764 fprintf (file
, "node: {title: \"%d_%d\" info1: \"", src_cuid
, src_uid
);
765 print_rtl_single (file
, g
->nodes
[src_cuid
].insn
);
766 fprintf (file
, "\"}\n");
767 for (e
= g
->nodes
[src_cuid
].out
; e
; e
= e
->next_out
)
769 int dst_uid
= INSN_UID (e
->dest
->insn
);
770 int dst_cuid
= e
->dest
->cuid
;
772 /* Give the backarcs a different color. */
774 fprintf (file
, "backedge: {color: red ");
776 fprintf (file
, "edge: { ");
778 fprintf (file
, "sourcename: \"%d_%d\" ", src_cuid
, src_uid
);
779 fprintf (file
, "targetname: \"%d_%d\" ", dst_cuid
, dst_uid
);
780 fprintf (file
, "label: \"%d_%d\"}\n", e
->latency
, e
->distance
);
783 fprintf (file
, "}\n");
786 /* Dump the sccs in SCCS. */
788 print_sccs (FILE *file
, ddg_all_sccs_ptr sccs
, ddg_ptr g
)
791 sbitmap_iterator sbi
;
797 fprintf (file
, "\n;; Number of SCC nodes - %d\n", sccs
->num_sccs
);
798 for (i
= 0; i
< sccs
->num_sccs
; i
++)
800 fprintf (file
, "SCC number: %d\n", i
);
801 EXECUTE_IF_SET_IN_BITMAP (sccs
->sccs
[i
]->nodes
, 0, u
, sbi
)
803 fprintf (file
, "insn num %d\n", u
);
804 print_rtl_single (file
, g
->nodes
[u
].insn
);
807 fprintf (file
, "\n");
810 /* Create an edge and initialize it with given values. */
812 create_ddg_edge (ddg_node_ptr src
, ddg_node_ptr dest
,
813 dep_type t
, dep_data_type dt
, int l
, int d
)
815 ddg_edge_ptr e
= (ddg_edge_ptr
) xmalloc (sizeof (struct ddg_edge
));
823 e
->next_in
= e
->next_out
= NULL
;
828 /* Add the given edge to the in/out linked lists of the DDG nodes. */
830 add_edge_to_ddg (ddg_ptr g ATTRIBUTE_UNUSED
, ddg_edge_ptr e
)
832 ddg_node_ptr src
= e
->src
;
833 ddg_node_ptr dest
= e
->dest
;
835 /* Should have allocated the sbitmaps. */
836 gcc_assert (src
->successors
&& dest
->predecessors
);
838 bitmap_set_bit (src
->successors
, dest
->cuid
);
839 bitmap_set_bit (dest
->predecessors
, src
->cuid
);
840 e
->next_in
= dest
->in
;
842 e
->next_out
= src
->out
;
848 /* Algorithm for computing the recurrence_length of an scc. We assume at
849 for now that cycles in the data dependence graph contain a single backarc.
850 This simplifies the algorithm, and can be generalized later. */
852 set_recurrence_length (ddg_scc_ptr scc
, ddg_ptr g
)
857 for (j
= 0; j
< scc
->num_backarcs
; j
++)
859 ddg_edge_ptr backarc
= scc
->backarcs
[j
];
861 int distance
= backarc
->distance
;
862 ddg_node_ptr src
= backarc
->dest
;
863 ddg_node_ptr dest
= backarc
->src
;
865 length
= longest_simple_path (g
, src
->cuid
, dest
->cuid
, scc
->nodes
);
868 /* fprintf (stderr, "Backarc not on simple cycle in SCC.\n"); */
871 length
+= backarc
->latency
;
872 result
= MAX (result
, (length
/ distance
));
874 scc
->recurrence_length
= result
;
877 /* Create a new SCC given the set of its nodes. Compute its recurrence_length
878 and mark edges that belong to this scc as IN_SCC. */
880 create_scc (ddg_ptr g
, sbitmap nodes
)
884 sbitmap_iterator sbi
;
886 scc
= (ddg_scc_ptr
) xmalloc (sizeof (struct ddg_scc
));
887 scc
->backarcs
= NULL
;
888 scc
->num_backarcs
= 0;
889 scc
->nodes
= sbitmap_alloc (g
->num_nodes
);
890 bitmap_copy (scc
->nodes
, nodes
);
892 /* Mark the backarcs that belong to this SCC. */
893 EXECUTE_IF_SET_IN_BITMAP (nodes
, 0, u
, sbi
)
896 ddg_node_ptr n
= &g
->nodes
[u
];
898 for (e
= n
->out
; e
; e
= e
->next_out
)
899 if (bitmap_bit_p (nodes
, e
->dest
->cuid
))
901 e
->aux
.count
= IN_SCC
;
903 add_backarc_to_scc (scc
, e
);
907 set_recurrence_length (scc
, g
);
911 /* Cleans the memory allocation of a given SCC. */
913 free_scc (ddg_scc_ptr scc
)
918 sbitmap_free (scc
->nodes
);
919 if (scc
->num_backarcs
> 0)
920 free (scc
->backarcs
);
925 /* Add a given edge known to be a backarc to the given DDG. */
927 add_backarc_to_ddg (ddg_ptr g
, ddg_edge_ptr e
)
929 int size
= (g
->num_backarcs
+ 1) * sizeof (ddg_edge_ptr
);
931 add_edge_to_ddg (g
, e
);
932 g
->backarcs
= (ddg_edge_ptr
*) xrealloc (g
->backarcs
, size
);
933 g
->backarcs
[g
->num_backarcs
++] = e
;
936 /* Add backarc to an SCC. */
938 add_backarc_to_scc (ddg_scc_ptr scc
, ddg_edge_ptr e
)
940 int size
= (scc
->num_backarcs
+ 1) * sizeof (ddg_edge_ptr
);
942 scc
->backarcs
= (ddg_edge_ptr
*) xrealloc (scc
->backarcs
, size
);
943 scc
->backarcs
[scc
->num_backarcs
++] = e
;
946 /* Add the given SCC to the DDG. */
948 add_scc_to_ddg (ddg_all_sccs_ptr g
, ddg_scc_ptr scc
)
950 int size
= (g
->num_sccs
+ 1) * sizeof (ddg_scc_ptr
);
952 g
->sccs
= (ddg_scc_ptr
*) xrealloc (g
->sccs
, size
);
953 g
->sccs
[g
->num_sccs
++] = scc
;
956 /* Given the instruction INSN return the node that represents it. */
958 get_node_of_insn (ddg_ptr g
, rtx_insn
*insn
)
962 for (i
= 0; i
< g
->num_nodes
; i
++)
963 if (insn
== g
->nodes
[i
].insn
)
968 /* Given a set OPS of nodes in the DDG, find the set of their successors
969 which are not in OPS, and set their bits in SUCC. Bits corresponding to
970 OPS are cleared from SUCC. Leaves the other bits in SUCC unchanged. */
972 find_successors (sbitmap succ
, ddg_ptr g
, sbitmap ops
)
975 sbitmap_iterator sbi
;
977 EXECUTE_IF_SET_IN_BITMAP (ops
, 0, i
, sbi
)
979 const sbitmap node_succ
= NODE_SUCCESSORS (&g
->nodes
[i
]);
980 bitmap_ior (succ
, succ
, node_succ
);
983 /* We want those that are not in ops. */
984 bitmap_and_compl (succ
, succ
, ops
);
987 /* Given a set OPS of nodes in the DDG, find the set of their predecessors
988 which are not in OPS, and set their bits in PREDS. Bits corresponding to
989 OPS are cleared from PREDS. Leaves the other bits in PREDS unchanged. */
991 find_predecessors (sbitmap preds
, ddg_ptr g
, sbitmap ops
)
994 sbitmap_iterator sbi
;
996 EXECUTE_IF_SET_IN_BITMAP (ops
, 0, i
, sbi
)
998 const sbitmap node_preds
= NODE_PREDECESSORS (&g
->nodes
[i
]);
999 bitmap_ior (preds
, preds
, node_preds
);
1002 /* We want those that are not in ops. */
1003 bitmap_and_compl (preds
, preds
, ops
);
1007 /* Compare function to be passed to qsort to order the backarcs in descending
1010 compare_sccs (const void *s1
, const void *s2
)
1012 const int rec_l1
= (*(const ddg_scc_ptr
*)s1
)->recurrence_length
;
1013 const int rec_l2
= (*(const ddg_scc_ptr
*)s2
)->recurrence_length
;
1014 return ((rec_l2
> rec_l1
) - (rec_l2
< rec_l1
));
1018 /* Order the backarcs in descending recMII order using compare_sccs. */
1020 order_sccs (ddg_all_sccs_ptr g
)
1022 qsort (g
->sccs
, g
->num_sccs
, sizeof (ddg_scc_ptr
),
1023 (int (*) (const void *, const void *)) compare_sccs
);
1026 #ifdef ENABLE_CHECKING
1027 /* Check that every node in SCCS belongs to exactly one strongly connected
1028 component and that no element of SCCS is empty. */
1030 check_sccs (ddg_all_sccs_ptr sccs
, int num_nodes
)
1033 sbitmap tmp
= sbitmap_alloc (num_nodes
);
1036 for (i
= 0; i
< sccs
->num_sccs
; i
++)
1038 gcc_assert (!bitmap_empty_p (sccs
->sccs
[i
]->nodes
));
1039 /* Verify that every node in sccs is in exactly one strongly
1040 connected component. */
1041 gcc_assert (!bitmap_intersect_p (tmp
, sccs
->sccs
[i
]->nodes
));
1042 bitmap_ior (tmp
, tmp
, sccs
->sccs
[i
]->nodes
);
1048 /* Perform the Strongly Connected Components decomposing algorithm on the
1049 DDG and return DDG_ALL_SCCS structure that contains them. */
1051 create_ddg_all_sccs (ddg_ptr g
)
1054 int num_nodes
= g
->num_nodes
;
1055 sbitmap from
= sbitmap_alloc (num_nodes
);
1056 sbitmap to
= sbitmap_alloc (num_nodes
);
1057 sbitmap scc_nodes
= sbitmap_alloc (num_nodes
);
1058 ddg_all_sccs_ptr sccs
= (ddg_all_sccs_ptr
)
1059 xmalloc (sizeof (struct ddg_all_sccs
));
1065 for (i
= 0; i
< g
->num_backarcs
; i
++)
1068 ddg_edge_ptr backarc
= g
->backarcs
[i
];
1069 ddg_node_ptr src
= backarc
->src
;
1070 ddg_node_ptr dest
= backarc
->dest
;
1072 /* If the backarc already belongs to an SCC, continue. */
1073 if (backarc
->aux
.count
== IN_SCC
)
1076 bitmap_clear (scc_nodes
);
1077 bitmap_clear (from
);
1079 bitmap_set_bit (from
, dest
->cuid
);
1080 bitmap_set_bit (to
, src
->cuid
);
1082 if (find_nodes_on_paths (scc_nodes
, g
, from
, to
))
1084 scc
= create_scc (g
, scc_nodes
);
1085 add_scc_to_ddg (sccs
, scc
);
1089 sbitmap_free (from
);
1091 sbitmap_free (scc_nodes
);
1092 #ifdef ENABLE_CHECKING
1093 check_sccs (sccs
, num_nodes
);
1098 /* Frees the memory allocated for all SCCs of the DDG, but keeps the DDG. */
1100 free_ddg_all_sccs (ddg_all_sccs_ptr all_sccs
)
1107 for (i
= 0; i
< all_sccs
->num_sccs
; i
++)
1108 free_scc (all_sccs
->sccs
[i
]);
1110 free (all_sccs
->sccs
);
1115 /* Given FROM - a bitmap of source nodes - and TO - a bitmap of destination
1116 nodes - find all nodes that lie on paths from FROM to TO (not excluding
1117 nodes from FROM and TO). Return nonzero if nodes exist. */
1119 find_nodes_on_paths (sbitmap result
, ddg_ptr g
, sbitmap from
, sbitmap to
)
1124 int num_nodes
= g
->num_nodes
;
1125 sbitmap_iterator sbi
;
1127 sbitmap workset
= sbitmap_alloc (num_nodes
);
1128 sbitmap reachable_from
= sbitmap_alloc (num_nodes
);
1129 sbitmap reach_to
= sbitmap_alloc (num_nodes
);
1130 sbitmap tmp
= sbitmap_alloc (num_nodes
);
1132 bitmap_copy (reachable_from
, from
);
1133 bitmap_copy (tmp
, from
);
1139 bitmap_copy (workset
, tmp
);
1141 EXECUTE_IF_SET_IN_BITMAP (workset
, 0, u
, sbi
)
1144 ddg_node_ptr u_node
= &g
->nodes
[u
];
1146 for (e
= u_node
->out
; e
!= (ddg_edge_ptr
) 0; e
= e
->next_out
)
1148 ddg_node_ptr v_node
= e
->dest
;
1149 int v
= v_node
->cuid
;
1151 if (!bitmap_bit_p (reachable_from
, v
))
1153 bitmap_set_bit (reachable_from
, v
);
1154 bitmap_set_bit (tmp
, v
);
1161 bitmap_copy (reach_to
, to
);
1162 bitmap_copy (tmp
, to
);
1168 bitmap_copy (workset
, tmp
);
1170 EXECUTE_IF_SET_IN_BITMAP (workset
, 0, u
, sbi
)
1173 ddg_node_ptr u_node
= &g
->nodes
[u
];
1175 for (e
= u_node
->in
; e
!= (ddg_edge_ptr
) 0; e
= e
->next_in
)
1177 ddg_node_ptr v_node
= e
->src
;
1178 int v
= v_node
->cuid
;
1180 if (!bitmap_bit_p (reach_to
, v
))
1182 bitmap_set_bit (reach_to
, v
);
1183 bitmap_set_bit (tmp
, v
);
1190 answer
= bitmap_and (result
, reachable_from
, reach_to
);
1191 sbitmap_free (workset
);
1192 sbitmap_free (reachable_from
);
1193 sbitmap_free (reach_to
);
1199 /* Updates the counts of U_NODE's successors (that belong to NODES) to be
1200 at-least as large as the count of U_NODE plus the latency between them.
1201 Sets a bit in TMP for each successor whose count was changed (increased).
1202 Returns nonzero if any count was changed. */
1204 update_dist_to_successors (ddg_node_ptr u_node
, sbitmap nodes
, sbitmap tmp
)
1209 for (e
= u_node
->out
; e
; e
= e
->next_out
)
1211 ddg_node_ptr v_node
= e
->dest
;
1212 int v
= v_node
->cuid
;
1214 if (bitmap_bit_p (nodes
, v
)
1215 && (e
->distance
== 0)
1216 && (v_node
->aux
.count
< u_node
->aux
.count
+ e
->latency
))
1218 v_node
->aux
.count
= u_node
->aux
.count
+ e
->latency
;
1219 bitmap_set_bit (tmp
, v
);
1227 /* Find the length of a longest path from SRC to DEST in G,
1228 going only through NODES, and disregarding backarcs. */
1230 longest_simple_path (struct ddg
* g
, int src
, int dest
, sbitmap nodes
)
1236 int num_nodes
= g
->num_nodes
;
1237 sbitmap workset
= sbitmap_alloc (num_nodes
);
1238 sbitmap tmp
= sbitmap_alloc (num_nodes
);
1241 /* Data will hold the distance of the longest path found so far from
1242 src to each node. Initialize to -1 = less than minimum. */
1243 for (i
= 0; i
< g
->num_nodes
; i
++)
1244 g
->nodes
[i
].aux
.count
= -1;
1245 g
->nodes
[src
].aux
.count
= 0;
1248 bitmap_set_bit (tmp
, src
);
1252 sbitmap_iterator sbi
;
1255 bitmap_copy (workset
, tmp
);
1257 EXECUTE_IF_SET_IN_BITMAP (workset
, 0, u
, sbi
)
1259 ddg_node_ptr u_node
= &g
->nodes
[u
];
1261 change
|= update_dist_to_successors (u_node
, nodes
, tmp
);
1264 result
= g
->nodes
[dest
].aux
.count
;
1265 sbitmap_free (workset
);
1270 #endif /* INSN_SCHEDULING */