1 /* DDG - Data Dependence Graph implementation.
2 Copyright (C) 2004-2020 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"
28 #include "insn-attr.h"
29 #include "sched-int.h"
33 #ifdef INSN_SCHEDULING
35 /* Forward declarations. */
36 static void add_backarc_to_ddg (ddg_ptr
, ddg_edge_ptr
);
37 static void add_backarc_to_scc (ddg_scc_ptr
, ddg_edge_ptr
);
38 static void add_scc_to_ddg (ddg_all_sccs_ptr
, ddg_scc_ptr
);
39 static void create_ddg_dep_from_intra_loop_link (ddg_ptr
, ddg_node_ptr
,
41 static void create_ddg_dep_no_link (ddg_ptr
, ddg_node_ptr
, ddg_node_ptr
,
42 dep_type
, dep_data_type
, int);
43 static ddg_edge_ptr
create_ddg_edge (ddg_node_ptr
, ddg_node_ptr
, dep_type
,
44 dep_data_type
, int, int);
45 static void add_edge_to_ddg (ddg_ptr g
, ddg_edge_ptr
);
47 /* Auxiliary variable for mem_read_insn_p/mem_write_insn_p. */
48 static bool mem_ref_p
;
50 /* Auxiliary function for mem_read_insn_p. */
52 mark_mem_use (rtx
*x
, void *)
54 subrtx_iterator::array_type array
;
55 FOR_EACH_SUBRTX (iter
, array
, *x
, NONCONST
)
63 /* Returns nonzero if INSN reads from memory. */
65 mem_read_insn_p (rtx_insn
*insn
)
68 note_uses (&PATTERN (insn
), mark_mem_use
, NULL
);
73 mark_mem_store (rtx loc
, const_rtx setter ATTRIBUTE_UNUSED
, void *data ATTRIBUTE_UNUSED
)
79 /* Returns nonzero if INSN writes to memory. */
81 mem_write_insn_p (rtx_insn
*insn
)
84 note_stores (insn
, mark_mem_store
, NULL
);
88 /* Returns nonzero if X has access to memory. */
90 rtx_mem_access_p (rtx x
)
103 fmt
= GET_RTX_FORMAT (code
);
104 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
108 if (rtx_mem_access_p (XEXP (x
, i
)))
111 else if (fmt
[i
] == 'E')
112 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
114 if (rtx_mem_access_p (XVECEXP (x
, i
, j
)))
121 /* Returns nonzero if INSN reads to or writes from memory. */
123 mem_access_insn_p (rtx_insn
*insn
)
125 return rtx_mem_access_p (PATTERN (insn
));
128 /* Return true if DEF_INSN contains address being auto-inc or auto-dec
129 which is used in USE_INSN. Otherwise return false. The result is
130 being used to decide whether to remove the edge between def_insn and
131 use_insn when -fmodulo-sched-allow-regmoves is set. This function
132 doesn't need to consider the specific address register; no reg_moves
133 will be allowed for any life range defined by def_insn and used
134 by use_insn, if use_insn uses an address register auto-inc'ed by
137 autoinc_var_is_used_p (rtx_insn
*def_insn
, rtx_insn
*use_insn
)
141 for (note
= REG_NOTES (def_insn
); note
; note
= XEXP (note
, 1))
142 if (REG_NOTE_KIND (note
) == REG_INC
143 && reg_referenced_p (XEXP (note
, 0), PATTERN (use_insn
)))
149 /* Return true if one of the definitions in INSN has MODE_CC. Otherwise
152 def_has_ccmode_p (rtx_insn
*insn
)
156 FOR_EACH_INSN_DEF (def
, insn
)
158 machine_mode mode
= GET_MODE (DF_REF_REG (def
));
160 if (GET_MODE_CLASS (mode
) == MODE_CC
)
167 /* Computes the dependence parameters (latency, distance etc.), creates
168 a ddg_edge and adds it to the given DDG. */
170 create_ddg_dep_from_intra_loop_link (ddg_ptr g
, ddg_node_ptr src_node
,
171 ddg_node_ptr dest_node
, dep_t link
)
174 int latency
, distance
= 0;
175 dep_type t
= TRUE_DEP
;
176 dep_data_type dt
= (mem_access_insn_p (src_node
->insn
)
177 && mem_access_insn_p (dest_node
->insn
) ? MEM_DEP
179 gcc_assert (src_node
->cuid
< dest_node
->cuid
);
182 /* Note: REG_DEP_ANTI applies to MEM ANTI_DEP as well!! */
183 if (DEP_TYPE (link
) == REG_DEP_ANTI
)
185 else if (DEP_TYPE (link
) == REG_DEP_OUTPUT
)
188 gcc_assert (!DEBUG_INSN_P (dest_node
->insn
) || t
== ANTI_DEP
);
189 gcc_assert (!DEBUG_INSN_P (src_node
->insn
) || t
== ANTI_DEP
);
191 /* We currently choose not to create certain anti-deps edges and
192 compensate for that by generating reg-moves based on the life-range
193 analysis. The anti-deps that will be deleted are the ones which
194 have true-deps edges in the opposite direction (in other words
195 the kernel has only one def of the relevant register).
196 If the address that is being auto-inc or auto-dec in DEST_NODE
197 is used in SRC_NODE then do not remove the edge to make sure
198 reg-moves will not be created for this address.
199 TODO: support the removal of all anti-deps edges, i.e. including those
200 whose register has multiple defs in the loop. */
201 if (flag_modulo_sched_allow_regmoves
202 && (t
== ANTI_DEP
&& dt
== REG_DEP
)
203 && !def_has_ccmode_p (dest_node
->insn
)
204 && !autoinc_var_is_used_p (dest_node
->insn
, src_node
->insn
))
208 set
= single_set (dest_node
->insn
);
209 /* TODO: Handle registers that REG_P is not true for them, i.e.
210 subregs and special registers. */
211 if (set
&& REG_P (SET_DEST (set
)))
213 int regno
= REGNO (SET_DEST (set
));
215 class df_rd_bb_info
*bb_info
= DF_RD_BB_INFO (g
->bb
);
217 first_def
= df_bb_regno_first_def_find (g
->bb
, regno
);
218 gcc_assert (first_def
);
220 if (bitmap_bit_p (&bb_info
->gen
, DF_REF_ID (first_def
)))
225 latency
= dep_cost (link
);
226 e
= create_ddg_edge (src_node
, dest_node
, t
, dt
, latency
, distance
);
227 add_edge_to_ddg (g
, e
);
230 /* The same as the above function, but it doesn't require a link parameter. */
232 create_ddg_dep_no_link (ddg_ptr g
, ddg_node_ptr from
, ddg_node_ptr to
,
233 dep_type d_t
, dep_data_type d_dt
, int distance
)
237 enum reg_note dep_kind
;
238 struct _dep _dep
, *dep
= &_dep
;
240 gcc_assert (!DEBUG_INSN_P (to
->insn
) || d_t
== ANTI_DEP
);
241 gcc_assert (!DEBUG_INSN_P (from
->insn
) || d_t
== ANTI_DEP
);
244 dep_kind
= REG_DEP_ANTI
;
245 else if (d_t
== OUTPUT_DEP
)
246 dep_kind
= REG_DEP_OUTPUT
;
249 gcc_assert (d_t
== TRUE_DEP
);
251 dep_kind
= REG_DEP_TRUE
;
254 init_dep (dep
, from
->insn
, to
->insn
, dep_kind
);
258 e
= create_ddg_edge (from
, to
, d_t
, d_dt
, l
, distance
);
260 add_backarc_to_ddg (g
, e
);
262 add_edge_to_ddg (g
, e
);
266 /* Given a downwards exposed register def LAST_DEF (which is the last
267 definition of that register in the bb), add inter-loop true dependences
268 to all its uses in the next iteration, an output dependence to the
269 first def of the same register (possibly itself) in the next iteration
270 and anti-dependences from its uses in the current iteration to the
271 first definition in the next iteration. */
273 add_cross_iteration_register_deps (ddg_ptr g
, df_ref last_def
)
275 int regno
= DF_REF_REGNO (last_def
);
276 struct df_link
*r_use
;
277 int has_use_in_bb_p
= false;
278 rtx_insn
*def_insn
= DF_REF_INSN (last_def
);
279 ddg_node_ptr last_def_node
= get_node_of_insn (g
, def_insn
);
280 ddg_node_ptr use_node
;
281 df_ref first_def
= df_bb_regno_first_def_find (g
->bb
, regno
);
283 gcc_assert (last_def_node
);
284 gcc_assert (first_def
);
286 if (flag_checking
&& DF_REF_ID (last_def
) != DF_REF_ID (first_def
))
288 class df_rd_bb_info
*bb_info
= DF_RD_BB_INFO (g
->bb
);
289 gcc_assert (!bitmap_bit_p (&bb_info
->gen
, DF_REF_ID (first_def
)));
292 /* Create inter-loop true dependences and anti dependences. */
293 for (r_use
= DF_REF_CHAIN (last_def
); r_use
!= NULL
; r_use
= r_use
->next
)
295 if (DF_REF_BB (r_use
->ref
) != g
->bb
)
298 gcc_assert (!DF_REF_IS_ARTIFICIAL (r_use
->ref
)
299 && DF_REF_INSN_INFO (r_use
->ref
) != NULL
);
301 rtx_insn
*use_insn
= DF_REF_INSN (r_use
->ref
);
303 /* ??? Do not handle uses with DF_REF_IN_NOTE notes. */
304 use_node
= get_node_of_insn (g
, use_insn
);
305 gcc_assert (use_node
);
306 has_use_in_bb_p
= true;
307 if (use_node
->cuid
<= last_def_node
->cuid
)
309 /* Add true deps from last_def to it's uses in the next
310 iteration. Any such upwards exposed use appears before
312 create_ddg_dep_no_link (g
, last_def_node
, use_node
,
313 DEBUG_INSN_P (use_insn
) ? ANTI_DEP
: TRUE_DEP
,
316 else if (!DEBUG_INSN_P (use_insn
))
318 /* Add anti deps from last_def's uses in the current iteration
319 to the first def in the next iteration. We do not add ANTI
320 dep when there is an intra-loop TRUE dep in the opposite
321 direction, but use regmoves to fix such disregarded ANTI
322 deps when broken. If the first_def reaches the USE then
323 there is such a dep. */
324 ddg_node_ptr first_def_node
= get_node_of_insn (g
,
325 DF_REF_INSN (first_def
));
327 gcc_assert (first_def_node
);
329 /* Always create the edge if the use node is a branch in
330 order to prevent the creation of reg-moves.
331 If the address that is being auto-inc or auto-dec in LAST_DEF
332 is used in USE_INSN then do not remove the edge to make sure
333 reg-moves will not be created for that address. */
334 if (DF_REF_ID (last_def
) != DF_REF_ID (first_def
)
335 || !flag_modulo_sched_allow_regmoves
336 || JUMP_P (use_node
->insn
)
337 || autoinc_var_is_used_p (DF_REF_INSN (last_def
), use_insn
)
338 || def_has_ccmode_p (DF_REF_INSN (last_def
)))
339 create_ddg_dep_no_link (g
, use_node
, first_def_node
, ANTI_DEP
,
344 /* Create an inter-loop output dependence between LAST_DEF (which is the
345 last def in its block, being downwards exposed) and the first def in
346 its block. Avoid creating a self output dependence. Avoid creating
347 an output dependence if there is a dependence path between the two
348 defs starting with a true dependence to a use which can be in the
349 next iteration; followed by an anti dependence of that use to the
350 first def (i.e. if there is a use between the two defs.) */
351 if (!has_use_in_bb_p
)
353 ddg_node_ptr dest_node
;
355 if (DF_REF_ID (last_def
) == DF_REF_ID (first_def
))
358 dest_node
= get_node_of_insn (g
, DF_REF_INSN (first_def
));
359 gcc_assert (dest_node
);
360 create_ddg_dep_no_link (g
, last_def_node
, dest_node
,
361 OUTPUT_DEP
, REG_DEP
, 1);
364 /* Build inter-loop dependencies, by looking at DF analysis backwards. */
366 build_inter_loop_deps (ddg_ptr g
)
369 class df_rd_bb_info
*rd_bb_info
;
372 rd_bb_info
= DF_RD_BB_INFO (g
->bb
);
374 /* Find inter-loop register output, true and anti deps. */
375 EXECUTE_IF_SET_IN_BITMAP (&rd_bb_info
->gen
, 0, rd_num
, bi
)
377 df_ref rd
= DF_DEFS_GET (rd_num
);
379 add_cross_iteration_register_deps (g
, rd
);
384 /* Return true if two specified instructions have mem expr with conflict
387 insns_may_alias_p (rtx_insn
*insn1
, rtx_insn
*insn2
)
389 subrtx_iterator::array_type array1
;
390 subrtx_iterator::array_type array2
;
391 FOR_EACH_SUBRTX (iter1
, array1
, PATTERN (insn1
), NONCONST
)
393 const_rtx x1
= *iter1
;
395 FOR_EACH_SUBRTX (iter2
, array2
, PATTERN (insn2
), NONCONST
)
397 const_rtx x2
= *iter2
;
398 if (MEM_P (x2
) && may_alias_p (x2
, x1
))
405 /* Given two nodes, analyze their RTL insns and add intra-loop mem deps
408 add_intra_loop_mem_dep (ddg_ptr g
, ddg_node_ptr from
, ddg_node_ptr to
)
411 if ((from
->cuid
== to
->cuid
)
412 || !insns_may_alias_p (from
->insn
, to
->insn
))
413 /* Do not create edge if memory references have disjoint alias sets
414 or 'to' and 'from' are the same instruction. */
417 if (mem_write_insn_p (from
->insn
))
419 if (mem_read_insn_p (to
->insn
))
420 create_ddg_dep_no_link (g
, from
, to
,
421 DEBUG_INSN_P (to
->insn
)
422 ? ANTI_DEP
: TRUE_DEP
, MEM_DEP
, 0);
424 create_ddg_dep_no_link (g
, from
, to
,
425 DEBUG_INSN_P (to
->insn
)
426 ? ANTI_DEP
: OUTPUT_DEP
, MEM_DEP
, 0);
428 else if (!mem_read_insn_p (to
->insn
))
429 create_ddg_dep_no_link (g
, from
, to
, ANTI_DEP
, MEM_DEP
, 0);
432 /* Given two nodes, analyze their RTL insns and add inter-loop mem deps
435 add_inter_loop_mem_dep (ddg_ptr g
, ddg_node_ptr from
, ddg_node_ptr to
)
437 if (!insns_may_alias_p (from
->insn
, to
->insn
))
438 /* Do not create edge if memory references have disjoint alias sets. */
441 if (mem_write_insn_p (from
->insn
))
443 if (mem_read_insn_p (to
->insn
))
444 create_ddg_dep_no_link (g
, from
, to
,
445 DEBUG_INSN_P (to
->insn
)
446 ? ANTI_DEP
: TRUE_DEP
, MEM_DEP
, 1);
447 else if (from
->cuid
!= to
->cuid
)
448 create_ddg_dep_no_link (g
, from
, to
,
449 DEBUG_INSN_P (to
->insn
)
450 ? ANTI_DEP
: OUTPUT_DEP
, MEM_DEP
, 1);
454 if (mem_read_insn_p (to
->insn
))
456 else if (from
->cuid
!= to
->cuid
)
458 create_ddg_dep_no_link (g
, from
, to
, ANTI_DEP
, MEM_DEP
, 1);
459 if (DEBUG_INSN_P (from
->insn
) || DEBUG_INSN_P (to
->insn
))
460 create_ddg_dep_no_link (g
, to
, from
, ANTI_DEP
, MEM_DEP
, 1);
462 create_ddg_dep_no_link (g
, to
, from
, TRUE_DEP
, MEM_DEP
, 1);
468 /* Perform intra-block Data Dependency analysis and connect the nodes in
469 the DDG. We assume the loop has a single basic block. */
471 build_intra_loop_deps (ddg_ptr g
)
474 /* Hold the dependency analysis state during dependency calculations. */
475 class deps_desc tmp_deps
;
476 rtx_insn
*head
, *tail
;
478 /* Build the dependence information, using the sched_analyze function. */
480 init_deps (&tmp_deps
, false);
482 /* Do the intra-block data dependence analysis for the given block. */
483 get_ebb_head_tail (g
->bb
, g
->bb
, &head
, &tail
);
484 sched_analyze (&tmp_deps
, head
, tail
);
486 /* Build intra-loop data dependencies using the scheduler dependency
488 for (i
= 0; i
< g
->num_nodes
; i
++)
490 ddg_node_ptr dest_node
= &g
->nodes
[i
];
491 sd_iterator_def sd_it
;
494 if (! INSN_P (dest_node
->insn
))
497 FOR_EACH_DEP (dest_node
->insn
, SD_LIST_BACK
, sd_it
, dep
)
499 rtx_insn
*src_insn
= DEP_PRO (dep
);
500 ddg_node_ptr src_node
;
502 /* Don't add dependencies on debug insns to non-debug insns
503 to avoid codegen differences between -g and -g0. */
504 if (DEBUG_INSN_P (src_insn
) && !DEBUG_INSN_P (dest_node
->insn
))
507 src_node
= get_node_of_insn (g
, src_insn
);
512 create_ddg_dep_from_intra_loop_link (g
, src_node
, dest_node
, dep
);
515 /* If this insn modifies memory, add an edge to all insns that access
517 if (mem_access_insn_p (dest_node
->insn
))
521 for (j
= 0; j
<= i
; j
++)
523 ddg_node_ptr j_node
= &g
->nodes
[j
];
524 if (DEBUG_INSN_P (j_node
->insn
))
526 if (mem_access_insn_p (j_node
->insn
))
528 /* Don't bother calculating inter-loop dep if an intra-loop dep
530 if (! bitmap_bit_p (dest_node
->successors
, j
))
531 add_inter_loop_mem_dep (g
, dest_node
, j_node
);
532 /* If -fmodulo-sched-allow-regmoves
533 is set certain anti-dep edges are not created.
534 It might be that these anti-dep edges are on the
535 path from one memory instruction to another such that
536 removing these edges could cause a violation of the
537 memory dependencies. Thus we add intra edges between
538 every two memory instructions in this case. */
539 if (flag_modulo_sched_allow_regmoves
540 && !bitmap_bit_p (dest_node
->predecessors
, j
))
541 add_intra_loop_mem_dep (g
, j_node
, dest_node
);
547 /* Free the INSN_LISTs. */
548 finish_deps_global ();
549 free_deps (&tmp_deps
);
551 /* Free dependencies. */
552 sched_free_deps (head
, tail
, false);
556 /* Given a basic block, create its DDG and return a pointer to a variable
557 of ddg type that represents it.
558 Initialize the ddg structure fields to the appropriate values. */
560 create_ddg (basic_block bb
, int closing_branch_deps
)
563 rtx_insn
*insn
, *first_note
;
567 g
= (ddg_ptr
) xcalloc (1, sizeof (struct ddg
));
570 g
->closing_branch_deps
= closing_branch_deps
;
572 /* Count the number of insns in the BB. */
573 for (insn
= BB_HEAD (bb
); insn
!= NEXT_INSN (BB_END (bb
));
574 insn
= NEXT_INSN (insn
))
576 if (! INSN_P (insn
) || GET_CODE (PATTERN (insn
)) == USE
)
579 if (DEBUG_INSN_P (insn
))
583 if (mem_read_insn_p (insn
))
585 if (mem_write_insn_p (insn
))
591 /* There is nothing to do for this BB. */
592 if ((num_nodes
- g
->num_debug
) <= 1)
598 /* Allocate the nodes array, and initialize the nodes. */
599 g
->num_nodes
= num_nodes
;
600 g
->nodes
= (ddg_node_ptr
) xcalloc (num_nodes
, sizeof (struct ddg_node
));
601 g
->closing_branch
= NULL
;
604 for (insn
= BB_HEAD (bb
); insn
!= NEXT_INSN (BB_END (bb
));
605 insn
= NEXT_INSN (insn
))
609 if (! first_note
&& NOTE_P (insn
)
610 && NOTE_KIND (insn
) != NOTE_INSN_BASIC_BLOCK
)
616 gcc_assert (!g
->closing_branch
);
617 g
->closing_branch
= &g
->nodes
[i
];
619 else if (GET_CODE (PATTERN (insn
)) == USE
)
626 g
->nodes
[i
].cuid
= i
;
627 g
->nodes
[i
].successors
= sbitmap_alloc (num_nodes
);
628 bitmap_clear (g
->nodes
[i
].successors
);
629 g
->nodes
[i
].predecessors
= sbitmap_alloc (num_nodes
);
630 bitmap_clear (g
->nodes
[i
].predecessors
);
631 g
->nodes
[i
].first_note
= (first_note
? first_note
: insn
);
633 g
->nodes
[i
].aux
.count
= -1;
634 g
->nodes
[i
].max_dist
= XCNEWVEC (int, num_nodes
);
635 for (j
= 0; j
< num_nodes
; j
++)
636 g
->nodes
[i
].max_dist
[j
] = -1;
638 g
->nodes
[i
++].insn
= insn
;
642 /* We must have found a branch in DDG. */
643 gcc_assert (g
->closing_branch
);
646 /* Build the data dependency graph. */
647 build_intra_loop_deps (g
);
648 build_inter_loop_deps (g
);
652 /* Free all the memory allocated for the DDG. */
661 for (i
= 0; i
< g
->num_nodes
; i
++)
663 ddg_edge_ptr e
= g
->nodes
[i
].out
;
667 ddg_edge_ptr next
= e
->next_out
;
672 sbitmap_free (g
->nodes
[i
].successors
);
673 sbitmap_free (g
->nodes
[i
].predecessors
);
674 free (g
->nodes
[i
].max_dist
);
676 if (g
->num_backarcs
> 0)
683 print_ddg_edge (FILE *file
, ddg_edge_ptr e
)
699 fprintf (file
, " [%d -(%c,%d,%d)-> %d] ", INSN_UID (e
->src
->insn
),
700 dep_c
, e
->latency
, e
->distance
, INSN_UID (e
->dest
->insn
));
703 /* Print the DDG nodes with there in/out edges to the dump file. */
705 print_ddg (FILE *file
, ddg_ptr g
)
709 for (i
= 0; i
< g
->num_nodes
; i
++)
713 fprintf (file
, "Node num: %d\n", g
->nodes
[i
].cuid
);
714 print_rtl_single (file
, g
->nodes
[i
].insn
);
715 fprintf (file
, "OUT ARCS: ");
716 for (e
= g
->nodes
[i
].out
; e
; e
= e
->next_out
)
717 print_ddg_edge (file
, e
);
719 fprintf (file
, "\nIN ARCS: ");
720 for (e
= g
->nodes
[i
].in
; e
; e
= e
->next_in
)
721 print_ddg_edge (file
, e
);
723 fprintf (file
, "\n");
727 /* Print the given DDG in VCG format. */
729 vcg_print_ddg (FILE *file
, ddg_ptr g
)
733 fprintf (file
, "graph: {\n");
734 for (src_cuid
= 0; src_cuid
< g
->num_nodes
; src_cuid
++)
737 int src_uid
= INSN_UID (g
->nodes
[src_cuid
].insn
);
739 fprintf (file
, "node: {title: \"%d_%d\" info1: \"", src_cuid
, src_uid
);
740 print_rtl_single (file
, g
->nodes
[src_cuid
].insn
);
741 fprintf (file
, "\"}\n");
742 for (e
= g
->nodes
[src_cuid
].out
; e
; e
= e
->next_out
)
744 int dst_uid
= INSN_UID (e
->dest
->insn
);
745 int dst_cuid
= e
->dest
->cuid
;
747 /* Give the backarcs a different color. */
749 fprintf (file
, "backedge: {color: red ");
751 fprintf (file
, "edge: { ");
753 fprintf (file
, "sourcename: \"%d_%d\" ", src_cuid
, src_uid
);
754 fprintf (file
, "targetname: \"%d_%d\" ", dst_cuid
, dst_uid
);
755 fprintf (file
, "label: \"%d_%d\"}\n", e
->latency
, e
->distance
);
758 fprintf (file
, "}\n");
761 /* Dump the sccs in SCCS. */
763 print_sccs (FILE *file
, ddg_all_sccs_ptr sccs
, ddg_ptr g
)
766 sbitmap_iterator sbi
;
772 fprintf (file
, "\n;; Number of SCC nodes - %d\n", sccs
->num_sccs
);
773 for (i
= 0; i
< sccs
->num_sccs
; i
++)
775 fprintf (file
, "SCC number: %d\n", i
);
776 EXECUTE_IF_SET_IN_BITMAP (sccs
->sccs
[i
]->nodes
, 0, u
, sbi
)
778 fprintf (file
, "insn num %d\n", u
);
779 print_rtl_single (file
, g
->nodes
[u
].insn
);
782 fprintf (file
, "\n");
785 /* Create an edge and initialize it with given values. */
787 create_ddg_edge (ddg_node_ptr src
, ddg_node_ptr dest
,
788 dep_type t
, dep_data_type dt
, int l
, int d
)
790 ddg_edge_ptr e
= (ddg_edge_ptr
) xmalloc (sizeof (struct ddg_edge
));
798 e
->next_in
= e
->next_out
= NULL
;
803 /* Add the given edge to the in/out linked lists of the DDG nodes. */
805 add_edge_to_ddg (ddg_ptr g ATTRIBUTE_UNUSED
, ddg_edge_ptr e
)
807 ddg_node_ptr src
= e
->src
;
808 ddg_node_ptr dest
= e
->dest
;
810 /* Should have allocated the sbitmaps. */
811 gcc_assert (src
->successors
&& dest
->predecessors
);
813 bitmap_set_bit (src
->successors
, dest
->cuid
);
814 bitmap_set_bit (dest
->predecessors
, src
->cuid
);
815 e
->next_in
= dest
->in
;
817 e
->next_out
= src
->out
;
823 /* Algorithm for computing the recurrence_length of an scc. We assume at
824 for now that cycles in the data dependence graph contain a single backarc.
825 This simplifies the algorithm, and can be generalized later. */
827 set_recurrence_length (ddg_scc_ptr scc
)
832 for (j
= 0; j
< scc
->num_backarcs
; j
++)
834 ddg_edge_ptr backarc
= scc
->backarcs
[j
];
835 int distance
= backarc
->distance
;
836 ddg_node_ptr src
= backarc
->dest
;
837 ddg_node_ptr dest
= backarc
->src
;
838 int length
= src
->max_dist
[dest
->cuid
];
843 length
+= backarc
->latency
;
844 result
= MAX (result
, (length
/ distance
));
846 scc
->recurrence_length
= result
;
849 /* Create a new SCC given the set of its nodes. Compute its recurrence_length
850 and mark edges that belong to this scc. */
852 create_scc (ddg_ptr g
, sbitmap nodes
, int id
)
856 sbitmap_iterator sbi
;
858 scc
= (ddg_scc_ptr
) xmalloc (sizeof (struct ddg_scc
));
859 scc
->backarcs
= NULL
;
860 scc
->num_backarcs
= 0;
861 scc
->nodes
= sbitmap_alloc (g
->num_nodes
);
862 bitmap_copy (scc
->nodes
, nodes
);
864 /* Mark the backarcs that belong to this SCC. */
865 EXECUTE_IF_SET_IN_BITMAP (nodes
, 0, u
, sbi
)
868 ddg_node_ptr n
= &g
->nodes
[u
];
870 gcc_assert (n
->aux
.count
== -1);
873 for (e
= n
->out
; e
; e
= e
->next_out
)
874 if (bitmap_bit_p (nodes
, e
->dest
->cuid
))
878 add_backarc_to_scc (scc
, e
);
885 /* Cleans the memory allocation of a given SCC. */
887 free_scc (ddg_scc_ptr scc
)
892 sbitmap_free (scc
->nodes
);
893 if (scc
->num_backarcs
> 0)
894 free (scc
->backarcs
);
899 /* Add a given edge known to be a backarc to the given DDG. */
901 add_backarc_to_ddg (ddg_ptr g
, ddg_edge_ptr e
)
903 int size
= (g
->num_backarcs
+ 1) * sizeof (ddg_edge_ptr
);
905 add_edge_to_ddg (g
, e
);
906 g
->backarcs
= (ddg_edge_ptr
*) xrealloc (g
->backarcs
, size
);
907 g
->backarcs
[g
->num_backarcs
++] = e
;
910 /* Add backarc to an SCC. */
912 add_backarc_to_scc (ddg_scc_ptr scc
, ddg_edge_ptr e
)
914 int size
= (scc
->num_backarcs
+ 1) * sizeof (ddg_edge_ptr
);
916 scc
->backarcs
= (ddg_edge_ptr
*) xrealloc (scc
->backarcs
, size
);
917 scc
->backarcs
[scc
->num_backarcs
++] = e
;
920 /* Add the given SCC to the DDG. */
922 add_scc_to_ddg (ddg_all_sccs_ptr g
, ddg_scc_ptr scc
)
924 int size
= (g
->num_sccs
+ 1) * sizeof (ddg_scc_ptr
);
926 g
->sccs
= (ddg_scc_ptr
*) xrealloc (g
->sccs
, size
);
927 g
->sccs
[g
->num_sccs
++] = scc
;
930 /* Given the instruction INSN return the node that represents it. */
932 get_node_of_insn (ddg_ptr g
, rtx_insn
*insn
)
936 for (i
= 0; i
< g
->num_nodes
; i
++)
937 if (insn
== g
->nodes
[i
].insn
)
942 /* Given a set OPS of nodes in the DDG, find the set of their successors
943 which are not in OPS, and set their bits in SUCC. Bits corresponding to
944 OPS are cleared from SUCC. Leaves the other bits in SUCC unchanged. */
946 find_successors (sbitmap succ
, ddg_ptr g
, sbitmap ops
)
949 sbitmap_iterator sbi
;
951 EXECUTE_IF_SET_IN_BITMAP (ops
, 0, i
, sbi
)
953 const sbitmap node_succ
= NODE_SUCCESSORS (&g
->nodes
[i
]);
954 bitmap_ior (succ
, succ
, node_succ
);
957 /* We want those that are not in ops. */
958 bitmap_and_compl (succ
, succ
, ops
);
961 /* Given a set OPS of nodes in the DDG, find the set of their predecessors
962 which are not in OPS, and set their bits in PREDS. Bits corresponding to
963 OPS are cleared from PREDS. Leaves the other bits in PREDS unchanged. */
965 find_predecessors (sbitmap preds
, ddg_ptr g
, sbitmap ops
)
968 sbitmap_iterator sbi
;
970 EXECUTE_IF_SET_IN_BITMAP (ops
, 0, i
, sbi
)
972 const sbitmap node_preds
= NODE_PREDECESSORS (&g
->nodes
[i
]);
973 bitmap_ior (preds
, preds
, node_preds
);
976 /* We want those that are not in ops. */
977 bitmap_and_compl (preds
, preds
, ops
);
981 /* Compare function to be passed to qsort to order the backarcs in descending
984 compare_sccs (const void *s1
, const void *s2
)
986 const int rec_l1
= (*(const ddg_scc_ptr
*)s1
)->recurrence_length
;
987 const int rec_l2
= (*(const ddg_scc_ptr
*)s2
)->recurrence_length
;
988 return ((rec_l2
> rec_l1
) - (rec_l2
< rec_l1
));
992 /* Order the backarcs in descending recMII order using compare_sccs. */
994 order_sccs (ddg_all_sccs_ptr g
)
996 qsort (g
->sccs
, g
->num_sccs
, sizeof (ddg_scc_ptr
),
997 (int (*) (const void *, const void *)) compare_sccs
);
1000 /* Check that every node in SCCS belongs to exactly one strongly connected
1001 component and that no element of SCCS is empty. */
1003 check_sccs (ddg_all_sccs_ptr sccs
, int num_nodes
)
1006 auto_sbitmap
tmp (num_nodes
);
1009 for (i
= 0; i
< sccs
->num_sccs
; i
++)
1011 gcc_assert (!bitmap_empty_p (sccs
->sccs
[i
]->nodes
));
1012 /* Verify that every node in sccs is in exactly one strongly
1013 connected component. */
1014 gcc_assert (!bitmap_intersect_p (tmp
, sccs
->sccs
[i
]->nodes
));
1015 bitmap_ior (tmp
, tmp
, sccs
->sccs
[i
]->nodes
);
1019 /* Perform the Strongly Connected Components decomposing algorithm on the
1020 DDG and return DDG_ALL_SCCS structure that contains them. */
1022 create_ddg_all_sccs (ddg_ptr g
)
1024 int i
, j
, k
, scc
, way
;
1025 int num_nodes
= g
->num_nodes
;
1026 auto_sbitmap
from (num_nodes
);
1027 auto_sbitmap
to (num_nodes
);
1028 auto_sbitmap
scc_nodes (num_nodes
);
1029 ddg_all_sccs_ptr sccs
= (ddg_all_sccs_ptr
)
1030 xmalloc (sizeof (struct ddg_all_sccs
));
1036 for (i
= 0; i
< g
->num_backarcs
; i
++)
1039 ddg_edge_ptr backarc
= g
->backarcs
[i
];
1040 ddg_node_ptr src
= backarc
->src
;
1041 ddg_node_ptr dest
= backarc
->dest
;
1043 /* If the backarc already belongs to an SCC, continue. */
1044 if (backarc
->in_scc
)
1047 bitmap_clear (scc_nodes
);
1048 bitmap_clear (from
);
1050 bitmap_set_bit (from
, dest
->cuid
);
1051 bitmap_set_bit (to
, src
->cuid
);
1053 if (find_nodes_on_paths (scc_nodes
, g
, from
, to
))
1055 scc
= create_scc (g
, scc_nodes
, sccs
->num_sccs
);
1056 add_scc_to_ddg (sccs
, scc
);
1060 /* Init max_dist arrays for Floyd–Warshall-like
1061 longest patch calculation algorithm. */
1062 for (k
= 0; k
< num_nodes
; k
++)
1065 ddg_node_ptr n
= &g
->nodes
[k
];
1067 if (n
->aux
.count
== -1)
1071 for (e
= n
->out
; e
; e
= e
->next_out
)
1072 if (e
->distance
== 0 && g
->nodes
[e
->dest
->cuid
].aux
.count
== n
->aux
.count
)
1073 n
->max_dist
[e
->dest
->cuid
] = e
->latency
;
1076 /* Run main Floid-Warshall loop. We use only non-backarc edges
1078 for (k
= 0; k
< num_nodes
; k
++)
1080 scc
= g
->nodes
[k
].aux
.count
;
1083 for (i
= 0; i
< num_nodes
; i
++)
1084 if (g
->nodes
[i
].aux
.count
== scc
)
1085 for (j
= 0; j
< num_nodes
; j
++)
1086 if (g
->nodes
[j
].aux
.count
== scc
1087 && g
->nodes
[i
].max_dist
[k
] >= 0
1088 && g
->nodes
[k
].max_dist
[j
] >= 0)
1090 way
= g
->nodes
[i
].max_dist
[k
] + g
->nodes
[k
].max_dist
[j
];
1091 if (g
->nodes
[i
].max_dist
[j
] < way
)
1092 g
->nodes
[i
].max_dist
[j
] = way
;
1097 /* Calculate recurrence_length using max_dist info. */
1098 for (i
= 0; i
< sccs
->num_sccs
; i
++)
1099 set_recurrence_length (sccs
->sccs
[i
]);
1104 check_sccs (sccs
, num_nodes
);
1109 /* Frees the memory allocated for all SCCs of the DDG, but keeps the DDG. */
1111 free_ddg_all_sccs (ddg_all_sccs_ptr all_sccs
)
1118 for (i
= 0; i
< all_sccs
->num_sccs
; i
++)
1119 free_scc (all_sccs
->sccs
[i
]);
1121 free (all_sccs
->sccs
);
1126 /* Given FROM - a bitmap of source nodes - and TO - a bitmap of destination
1127 nodes - find all nodes that lie on paths from FROM to TO (not excluding
1128 nodes from FROM and TO). Return nonzero if nodes exist. */
1130 find_nodes_on_paths (sbitmap result
, ddg_ptr g
, sbitmap from
, sbitmap to
)
1134 int num_nodes
= g
->num_nodes
;
1135 sbitmap_iterator sbi
;
1137 auto_sbitmap
workset (num_nodes
);
1138 auto_sbitmap
reachable_from (num_nodes
);
1139 auto_sbitmap
reach_to (num_nodes
);
1140 auto_sbitmap
tmp (num_nodes
);
1142 bitmap_copy (reachable_from
, from
);
1143 bitmap_copy (tmp
, from
);
1149 bitmap_copy (workset
, tmp
);
1151 EXECUTE_IF_SET_IN_BITMAP (workset
, 0, u
, sbi
)
1154 ddg_node_ptr u_node
= &g
->nodes
[u
];
1156 for (e
= u_node
->out
; e
!= (ddg_edge_ptr
) 0; e
= e
->next_out
)
1158 ddg_node_ptr v_node
= e
->dest
;
1159 int v
= v_node
->cuid
;
1161 if (!bitmap_bit_p (reachable_from
, v
))
1163 bitmap_set_bit (reachable_from
, v
);
1164 bitmap_set_bit (tmp
, v
);
1171 bitmap_copy (reach_to
, to
);
1172 bitmap_copy (tmp
, to
);
1178 bitmap_copy (workset
, tmp
);
1180 EXECUTE_IF_SET_IN_BITMAP (workset
, 0, u
, sbi
)
1183 ddg_node_ptr u_node
= &g
->nodes
[u
];
1185 for (e
= u_node
->in
; e
!= (ddg_edge_ptr
) 0; e
= e
->next_in
)
1187 ddg_node_ptr v_node
= e
->src
;
1188 int v
= v_node
->cuid
;
1190 if (!bitmap_bit_p (reach_to
, v
))
1192 bitmap_set_bit (reach_to
, v
);
1193 bitmap_set_bit (tmp
, v
);
1200 return bitmap_and (result
, reachable_from
, reach_to
);
1203 #endif /* INSN_SCHEDULING */