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"
26 #include "diagnostic-core.h"
29 #include "hard-reg-set.h"
38 #include "insn-config.h"
39 #include "insn-attr.h"
43 #include "basic-block.h"
44 #include "sched-int.h"
55 #ifdef INSN_SCHEDULING
57 /* A flag indicating that a ddg edge belongs to an SCC or not. */
58 enum edge_flag
{NOT_IN_SCC
= 0, IN_SCC
};
60 /* Forward declarations. */
61 static void add_backarc_to_ddg (ddg_ptr
, ddg_edge_ptr
);
62 static void add_backarc_to_scc (ddg_scc_ptr
, ddg_edge_ptr
);
63 static void add_scc_to_ddg (ddg_all_sccs_ptr
, ddg_scc_ptr
);
64 static void create_ddg_dep_from_intra_loop_link (ddg_ptr
, ddg_node_ptr
,
66 static void create_ddg_dep_no_link (ddg_ptr
, ddg_node_ptr
, ddg_node_ptr
,
67 dep_type
, dep_data_type
, int);
68 static ddg_edge_ptr
create_ddg_edge (ddg_node_ptr
, ddg_node_ptr
, dep_type
,
69 dep_data_type
, int, int);
70 static void add_edge_to_ddg (ddg_ptr g
, ddg_edge_ptr
);
72 /* Auxiliary variable for mem_read_insn_p/mem_write_insn_p. */
73 static bool mem_ref_p
;
75 /* Auxiliary function for mem_read_insn_p. */
77 mark_mem_use (rtx
*x
, void *)
79 subrtx_iterator::array_type array
;
80 FOR_EACH_SUBRTX (iter
, array
, *x
, NONCONST
)
88 /* Returns nonzero if INSN reads from memory. */
90 mem_read_insn_p (rtx_insn
*insn
)
93 note_uses (&PATTERN (insn
), mark_mem_use
, NULL
);
98 mark_mem_store (rtx loc
, const_rtx setter ATTRIBUTE_UNUSED
, void *data ATTRIBUTE_UNUSED
)
104 /* Returns nonzero if INSN writes to memory. */
106 mem_write_insn_p (rtx_insn
*insn
)
109 note_stores (PATTERN (insn
), mark_mem_store
, NULL
);
113 /* Returns nonzero if X has access to memory. */
115 rtx_mem_access_p (rtx x
)
128 fmt
= GET_RTX_FORMAT (code
);
129 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
133 if (rtx_mem_access_p (XEXP (x
, i
)))
136 else if (fmt
[i
] == 'E')
137 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
139 if (rtx_mem_access_p (XVECEXP (x
, i
, j
)))
146 /* Returns nonzero if INSN reads to or writes from memory. */
148 mem_access_insn_p (rtx_insn
*insn
)
150 return rtx_mem_access_p (PATTERN (insn
));
153 /* Return true if DEF_INSN contains address being auto-inc or auto-dec
154 which is used in USE_INSN. Otherwise return false. The result is
155 being used to decide whether to remove the edge between def_insn and
156 use_insn when -fmodulo-sched-allow-regmoves is set. This function
157 doesn't need to consider the specific address register; no reg_moves
158 will be allowed for any life range defined by def_insn and used
159 by use_insn, if use_insn uses an address register auto-inc'ed by
162 autoinc_var_is_used_p (rtx_insn
*def_insn
, rtx_insn
*use_insn
)
166 for (note
= REG_NOTES (def_insn
); note
; note
= XEXP (note
, 1))
167 if (REG_NOTE_KIND (note
) == REG_INC
168 && reg_referenced_p (XEXP (note
, 0), PATTERN (use_insn
)))
174 /* Return true if one of the definitions in INSN has MODE_CC. Otherwise
177 def_has_ccmode_p (rtx_insn
*insn
)
181 FOR_EACH_INSN_DEF (def
, insn
)
183 machine_mode mode
= GET_MODE (DF_REF_REG (def
));
185 if (GET_MODE_CLASS (mode
) == MODE_CC
)
192 /* Computes the dependence parameters (latency, distance etc.), creates
193 a ddg_edge and adds it to the given DDG. */
195 create_ddg_dep_from_intra_loop_link (ddg_ptr g
, ddg_node_ptr src_node
,
196 ddg_node_ptr dest_node
, dep_t link
)
199 int latency
, distance
= 0;
200 dep_type t
= TRUE_DEP
;
201 dep_data_type dt
= (mem_access_insn_p (src_node
->insn
)
202 && mem_access_insn_p (dest_node
->insn
) ? MEM_DEP
204 gcc_assert (src_node
->cuid
< dest_node
->cuid
);
207 /* Note: REG_DEP_ANTI applies to MEM ANTI_DEP as well!! */
208 if (DEP_TYPE (link
) == REG_DEP_ANTI
)
210 else if (DEP_TYPE (link
) == REG_DEP_OUTPUT
)
213 gcc_assert (!DEBUG_INSN_P (dest_node
->insn
) || t
== ANTI_DEP
);
214 gcc_assert (!DEBUG_INSN_P (src_node
->insn
) || t
== ANTI_DEP
);
216 /* We currently choose not to create certain anti-deps edges and
217 compensate for that by generating reg-moves based on the life-range
218 analysis. The anti-deps that will be deleted are the ones which
219 have true-deps edges in the opposite direction (in other words
220 the kernel has only one def of the relevant register).
221 If the address that is being auto-inc or auto-dec in DEST_NODE
222 is used in SRC_NODE then do not remove the edge to make sure
223 reg-moves will not be created for this address.
224 TODO: support the removal of all anti-deps edges, i.e. including those
225 whose register has multiple defs in the loop. */
226 if (flag_modulo_sched_allow_regmoves
227 && (t
== ANTI_DEP
&& dt
== REG_DEP
)
228 && !def_has_ccmode_p (dest_node
->insn
)
229 && !autoinc_var_is_used_p (dest_node
->insn
, src_node
->insn
))
233 set
= single_set (dest_node
->insn
);
234 /* TODO: Handle registers that REG_P is not true for them, i.e.
235 subregs and special registers. */
236 if (set
&& REG_P (SET_DEST (set
)))
238 int regno
= REGNO (SET_DEST (set
));
240 struct df_rd_bb_info
*bb_info
= DF_RD_BB_INFO (g
->bb
);
242 first_def
= df_bb_regno_first_def_find (g
->bb
, regno
);
243 gcc_assert (first_def
);
245 if (bitmap_bit_p (&bb_info
->gen
, DF_REF_ID (first_def
)))
250 latency
= dep_cost (link
);
251 e
= create_ddg_edge (src_node
, dest_node
, t
, dt
, latency
, distance
);
252 add_edge_to_ddg (g
, e
);
255 /* The same as the above function, but it doesn't require a link parameter. */
257 create_ddg_dep_no_link (ddg_ptr g
, ddg_node_ptr from
, ddg_node_ptr to
,
258 dep_type d_t
, dep_data_type d_dt
, int distance
)
262 enum reg_note dep_kind
;
263 struct _dep _dep
, *dep
= &_dep
;
265 gcc_assert (!DEBUG_INSN_P (to
->insn
) || d_t
== ANTI_DEP
);
266 gcc_assert (!DEBUG_INSN_P (from
->insn
) || d_t
== ANTI_DEP
);
269 dep_kind
= REG_DEP_ANTI
;
270 else if (d_t
== OUTPUT_DEP
)
271 dep_kind
= REG_DEP_OUTPUT
;
274 gcc_assert (d_t
== TRUE_DEP
);
276 dep_kind
= REG_DEP_TRUE
;
279 init_dep (dep
, from
->insn
, to
->insn
, dep_kind
);
283 e
= create_ddg_edge (from
, to
, d_t
, d_dt
, l
, distance
);
285 add_backarc_to_ddg (g
, e
);
287 add_edge_to_ddg (g
, e
);
291 /* Given a downwards exposed register def LAST_DEF (which is the last
292 definition of that register in the bb), add inter-loop true dependences
293 to all its uses in the next iteration, an output dependence to the
294 first def of the same register (possibly itself) in the next iteration
295 and anti-dependences from its uses in the current iteration to the
296 first definition in the next iteration. */
298 add_cross_iteration_register_deps (ddg_ptr g
, df_ref last_def
)
300 int regno
= DF_REF_REGNO (last_def
);
301 struct df_link
*r_use
;
302 int has_use_in_bb_p
= false;
303 rtx_insn
*def_insn
= DF_REF_INSN (last_def
);
304 ddg_node_ptr last_def_node
= get_node_of_insn (g
, def_insn
);
305 ddg_node_ptr use_node
;
306 #ifdef ENABLE_CHECKING
307 struct df_rd_bb_info
*bb_info
= DF_RD_BB_INFO (g
->bb
);
309 df_ref first_def
= df_bb_regno_first_def_find (g
->bb
, regno
);
311 gcc_assert (last_def_node
);
312 gcc_assert (first_def
);
314 #ifdef ENABLE_CHECKING
315 if (DF_REF_ID (last_def
) != DF_REF_ID (first_def
))
316 gcc_assert (!bitmap_bit_p (&bb_info
->gen
,
317 DF_REF_ID (first_def
)));
320 /* Create inter-loop true dependences and anti dependences. */
321 for (r_use
= DF_REF_CHAIN (last_def
); r_use
!= NULL
; r_use
= r_use
->next
)
323 rtx_insn
*use_insn
= DF_REF_INSN (r_use
->ref
);
325 if (BLOCK_FOR_INSN (use_insn
) != g
->bb
)
328 /* ??? Do not handle uses with DF_REF_IN_NOTE notes. */
329 use_node
= get_node_of_insn (g
, use_insn
);
330 gcc_assert (use_node
);
331 has_use_in_bb_p
= true;
332 if (use_node
->cuid
<= last_def_node
->cuid
)
334 /* Add true deps from last_def to it's uses in the next
335 iteration. Any such upwards exposed use appears before
337 create_ddg_dep_no_link (g
, last_def_node
, use_node
,
338 DEBUG_INSN_P (use_insn
) ? ANTI_DEP
: TRUE_DEP
,
341 else if (!DEBUG_INSN_P (use_insn
))
343 /* Add anti deps from last_def's uses in the current iteration
344 to the first def in the next iteration. We do not add ANTI
345 dep when there is an intra-loop TRUE dep in the opposite
346 direction, but use regmoves to fix such disregarded ANTI
347 deps when broken. If the first_def reaches the USE then
348 there is such a dep. */
349 ddg_node_ptr first_def_node
= get_node_of_insn (g
,
350 DF_REF_INSN (first_def
));
352 gcc_assert (first_def_node
);
354 /* Always create the edge if the use node is a branch in
355 order to prevent the creation of reg-moves.
356 If the address that is being auto-inc or auto-dec in LAST_DEF
357 is used in USE_INSN then do not remove the edge to make sure
358 reg-moves will not be created for that address. */
359 if (DF_REF_ID (last_def
) != DF_REF_ID (first_def
)
360 || !flag_modulo_sched_allow_regmoves
361 || JUMP_P (use_node
->insn
)
362 || autoinc_var_is_used_p (DF_REF_INSN (last_def
), use_insn
)
363 || def_has_ccmode_p (DF_REF_INSN (last_def
)))
364 create_ddg_dep_no_link (g
, use_node
, first_def_node
, ANTI_DEP
,
369 /* Create an inter-loop output dependence between LAST_DEF (which is the
370 last def in its block, being downwards exposed) and the first def in
371 its block. Avoid creating a self output dependence. Avoid creating
372 an output dependence if there is a dependence path between the two
373 defs starting with a true dependence to a use which can be in the
374 next iteration; followed by an anti dependence of that use to the
375 first def (i.e. if there is a use between the two defs.) */
376 if (!has_use_in_bb_p
)
378 ddg_node_ptr dest_node
;
380 if (DF_REF_ID (last_def
) == DF_REF_ID (first_def
))
383 dest_node
= get_node_of_insn (g
, DF_REF_INSN (first_def
));
384 gcc_assert (dest_node
);
385 create_ddg_dep_no_link (g
, last_def_node
, dest_node
,
386 OUTPUT_DEP
, REG_DEP
, 1);
389 /* Build inter-loop dependencies, by looking at DF analysis backwards. */
391 build_inter_loop_deps (ddg_ptr g
)
394 struct df_rd_bb_info
*rd_bb_info
;
397 rd_bb_info
= DF_RD_BB_INFO (g
->bb
);
399 /* Find inter-loop register output, true and anti deps. */
400 EXECUTE_IF_SET_IN_BITMAP (&rd_bb_info
->gen
, 0, rd_num
, bi
)
402 df_ref rd
= DF_DEFS_GET (rd_num
);
404 add_cross_iteration_register_deps (g
, rd
);
409 /* Return true if two specified instructions have mem expr with conflict
412 insns_may_alias_p (rtx_insn
*insn1
, rtx_insn
*insn2
)
414 subrtx_iterator::array_type array1
;
415 subrtx_iterator::array_type array2
;
416 FOR_EACH_SUBRTX (iter1
, array1
, PATTERN (insn1
), NONCONST
)
418 const_rtx x1
= *iter1
;
420 FOR_EACH_SUBRTX (iter2
, array2
, PATTERN (insn2
), NONCONST
)
422 const_rtx x2
= *iter2
;
423 if (MEM_P (x2
) && may_alias_p (x2
, x1
))
430 /* Given two nodes, analyze their RTL insns and add intra-loop mem deps
433 add_intra_loop_mem_dep (ddg_ptr g
, ddg_node_ptr from
, ddg_node_ptr to
)
436 if ((from
->cuid
== to
->cuid
)
437 || !insns_may_alias_p (from
->insn
, to
->insn
))
438 /* Do not create edge if memory references have disjoint alias sets
439 or 'to' and 'from' are the same instruction. */
442 if (mem_write_insn_p (from
->insn
))
444 if (mem_read_insn_p (to
->insn
))
445 create_ddg_dep_no_link (g
, from
, to
,
446 DEBUG_INSN_P (to
->insn
)
447 ? ANTI_DEP
: TRUE_DEP
, MEM_DEP
, 0);
449 create_ddg_dep_no_link (g
, from
, to
,
450 DEBUG_INSN_P (to
->insn
)
451 ? ANTI_DEP
: OUTPUT_DEP
, MEM_DEP
, 0);
453 else if (!mem_read_insn_p (to
->insn
))
454 create_ddg_dep_no_link (g
, from
, to
, ANTI_DEP
, MEM_DEP
, 0);
457 /* Given two nodes, analyze their RTL insns and add inter-loop mem deps
460 add_inter_loop_mem_dep (ddg_ptr g
, ddg_node_ptr from
, ddg_node_ptr to
)
462 if (!insns_may_alias_p (from
->insn
, to
->insn
))
463 /* Do not create edge if memory references have disjoint alias sets. */
466 if (mem_write_insn_p (from
->insn
))
468 if (mem_read_insn_p (to
->insn
))
469 create_ddg_dep_no_link (g
, from
, to
,
470 DEBUG_INSN_P (to
->insn
)
471 ? ANTI_DEP
: TRUE_DEP
, MEM_DEP
, 1);
472 else if (from
->cuid
!= to
->cuid
)
473 create_ddg_dep_no_link (g
, from
, to
,
474 DEBUG_INSN_P (to
->insn
)
475 ? ANTI_DEP
: OUTPUT_DEP
, MEM_DEP
, 1);
479 if (mem_read_insn_p (to
->insn
))
481 else if (from
->cuid
!= to
->cuid
)
483 create_ddg_dep_no_link (g
, from
, to
, ANTI_DEP
, MEM_DEP
, 1);
484 if (DEBUG_INSN_P (from
->insn
) || DEBUG_INSN_P (to
->insn
))
485 create_ddg_dep_no_link (g
, to
, from
, ANTI_DEP
, MEM_DEP
, 1);
487 create_ddg_dep_no_link (g
, to
, from
, TRUE_DEP
, MEM_DEP
, 1);
493 /* Perform intra-block Data Dependency analysis and connect the nodes in
494 the DDG. We assume the loop has a single basic block. */
496 build_intra_loop_deps (ddg_ptr g
)
499 /* Hold the dependency analysis state during dependency calculations. */
500 struct deps_desc tmp_deps
;
501 rtx_insn
*head
, *tail
;
503 /* Build the dependence information, using the sched_analyze function. */
505 init_deps (&tmp_deps
, false);
507 /* Do the intra-block data dependence analysis for the given block. */
508 get_ebb_head_tail (g
->bb
, g
->bb
, &head
, &tail
);
509 sched_analyze (&tmp_deps
, head
, tail
);
511 /* Build intra-loop data dependencies using the scheduler dependency
513 for (i
= 0; i
< g
->num_nodes
; i
++)
515 ddg_node_ptr dest_node
= &g
->nodes
[i
];
516 sd_iterator_def sd_it
;
519 if (! INSN_P (dest_node
->insn
))
522 FOR_EACH_DEP (dest_node
->insn
, SD_LIST_BACK
, sd_it
, dep
)
524 rtx_insn
*src_insn
= DEP_PRO (dep
);
525 ddg_node_ptr src_node
;
527 /* Don't add dependencies on debug insns to non-debug insns
528 to avoid codegen differences between -g and -g0. */
529 if (DEBUG_INSN_P (src_insn
) && !DEBUG_INSN_P (dest_node
->insn
))
532 src_node
= get_node_of_insn (g
, src_insn
);
537 create_ddg_dep_from_intra_loop_link (g
, src_node
, dest_node
, dep
);
540 /* If this insn modifies memory, add an edge to all insns that access
542 if (mem_access_insn_p (dest_node
->insn
))
546 for (j
= 0; j
<= i
; j
++)
548 ddg_node_ptr j_node
= &g
->nodes
[j
];
549 if (DEBUG_INSN_P (j_node
->insn
))
551 if (mem_access_insn_p (j_node
->insn
))
553 /* Don't bother calculating inter-loop dep if an intra-loop dep
555 if (! bitmap_bit_p (dest_node
->successors
, j
))
556 add_inter_loop_mem_dep (g
, dest_node
, j_node
);
557 /* If -fmodulo-sched-allow-regmoves
558 is set certain anti-dep edges are not created.
559 It might be that these anti-dep edges are on the
560 path from one memory instruction to another such that
561 removing these edges could cause a violation of the
562 memory dependencies. Thus we add intra edges between
563 every two memory instructions in this case. */
564 if (flag_modulo_sched_allow_regmoves
565 && !bitmap_bit_p (dest_node
->predecessors
, j
))
566 add_intra_loop_mem_dep (g
, j_node
, dest_node
);
572 /* Free the INSN_LISTs. */
573 finish_deps_global ();
574 free_deps (&tmp_deps
);
576 /* Free dependencies. */
577 sched_free_deps (head
, tail
, false);
581 /* Given a basic block, create its DDG and return a pointer to a variable
582 of ddg type that represents it.
583 Initialize the ddg structure fields to the appropriate values. */
585 create_ddg (basic_block bb
, int closing_branch_deps
)
588 rtx_insn
*insn
, *first_note
;
592 g
= (ddg_ptr
) xcalloc (1, sizeof (struct ddg
));
595 g
->closing_branch_deps
= closing_branch_deps
;
597 /* Count the number of insns in the BB. */
598 for (insn
= BB_HEAD (bb
); insn
!= NEXT_INSN (BB_END (bb
));
599 insn
= NEXT_INSN (insn
))
601 if (! INSN_P (insn
) || GET_CODE (PATTERN (insn
)) == USE
)
604 if (DEBUG_INSN_P (insn
))
608 if (mem_read_insn_p (insn
))
610 if (mem_write_insn_p (insn
))
616 /* There is nothing to do for this BB. */
617 if ((num_nodes
- g
->num_debug
) <= 1)
623 /* Allocate the nodes array, and initialize the nodes. */
624 g
->num_nodes
= num_nodes
;
625 g
->nodes
= (ddg_node_ptr
) xcalloc (num_nodes
, sizeof (struct ddg_node
));
626 g
->closing_branch
= NULL
;
629 for (insn
= BB_HEAD (bb
); insn
!= NEXT_INSN (BB_END (bb
));
630 insn
= NEXT_INSN (insn
))
634 if (! first_note
&& NOTE_P (insn
)
635 && NOTE_KIND (insn
) != NOTE_INSN_BASIC_BLOCK
)
641 gcc_assert (!g
->closing_branch
);
642 g
->closing_branch
= &g
->nodes
[i
];
644 else if (GET_CODE (PATTERN (insn
)) == USE
)
651 g
->nodes
[i
].cuid
= i
;
652 g
->nodes
[i
].successors
= sbitmap_alloc (num_nodes
);
653 bitmap_clear (g
->nodes
[i
].successors
);
654 g
->nodes
[i
].predecessors
= sbitmap_alloc (num_nodes
);
655 bitmap_clear (g
->nodes
[i
].predecessors
);
656 g
->nodes
[i
].first_note
= (first_note
? first_note
: insn
);
657 g
->nodes
[i
++].insn
= insn
;
661 /* We must have found a branch in DDG. */
662 gcc_assert (g
->closing_branch
);
665 /* Build the data dependency graph. */
666 build_intra_loop_deps (g
);
667 build_inter_loop_deps (g
);
671 /* Free all the memory allocated for the DDG. */
680 for (i
= 0; i
< g
->num_nodes
; i
++)
682 ddg_edge_ptr e
= g
->nodes
[i
].out
;
686 ddg_edge_ptr next
= e
->next_out
;
691 sbitmap_free (g
->nodes
[i
].successors
);
692 sbitmap_free (g
->nodes
[i
].predecessors
);
694 if (g
->num_backarcs
> 0)
701 print_ddg_edge (FILE *file
, ddg_edge_ptr e
)
717 fprintf (file
, " [%d -(%c,%d,%d)-> %d] ", INSN_UID (e
->src
->insn
),
718 dep_c
, e
->latency
, e
->distance
, INSN_UID (e
->dest
->insn
));
721 /* Print the DDG nodes with there in/out edges to the dump file. */
723 print_ddg (FILE *file
, ddg_ptr g
)
727 for (i
= 0; i
< g
->num_nodes
; i
++)
731 fprintf (file
, "Node num: %d\n", g
->nodes
[i
].cuid
);
732 print_rtl_single (file
, g
->nodes
[i
].insn
);
733 fprintf (file
, "OUT ARCS: ");
734 for (e
= g
->nodes
[i
].out
; e
; e
= e
->next_out
)
735 print_ddg_edge (file
, e
);
737 fprintf (file
, "\nIN ARCS: ");
738 for (e
= g
->nodes
[i
].in
; e
; e
= e
->next_in
)
739 print_ddg_edge (file
, e
);
741 fprintf (file
, "\n");
745 /* Print the given DDG in VCG format. */
747 vcg_print_ddg (FILE *file
, ddg_ptr g
)
751 fprintf (file
, "graph: {\n");
752 for (src_cuid
= 0; src_cuid
< g
->num_nodes
; src_cuid
++)
755 int src_uid
= INSN_UID (g
->nodes
[src_cuid
].insn
);
757 fprintf (file
, "node: {title: \"%d_%d\" info1: \"", src_cuid
, src_uid
);
758 print_rtl_single (file
, g
->nodes
[src_cuid
].insn
);
759 fprintf (file
, "\"}\n");
760 for (e
= g
->nodes
[src_cuid
].out
; e
; e
= e
->next_out
)
762 int dst_uid
= INSN_UID (e
->dest
->insn
);
763 int dst_cuid
= e
->dest
->cuid
;
765 /* Give the backarcs a different color. */
767 fprintf (file
, "backedge: {color: red ");
769 fprintf (file
, "edge: { ");
771 fprintf (file
, "sourcename: \"%d_%d\" ", src_cuid
, src_uid
);
772 fprintf (file
, "targetname: \"%d_%d\" ", dst_cuid
, dst_uid
);
773 fprintf (file
, "label: \"%d_%d\"}\n", e
->latency
, e
->distance
);
776 fprintf (file
, "}\n");
779 /* Dump the sccs in SCCS. */
781 print_sccs (FILE *file
, ddg_all_sccs_ptr sccs
, ddg_ptr g
)
784 sbitmap_iterator sbi
;
790 fprintf (file
, "\n;; Number of SCC nodes - %d\n", sccs
->num_sccs
);
791 for (i
= 0; i
< sccs
->num_sccs
; i
++)
793 fprintf (file
, "SCC number: %d\n", i
);
794 EXECUTE_IF_SET_IN_BITMAP (sccs
->sccs
[i
]->nodes
, 0, u
, sbi
)
796 fprintf (file
, "insn num %d\n", u
);
797 print_rtl_single (file
, g
->nodes
[u
].insn
);
800 fprintf (file
, "\n");
803 /* Create an edge and initialize it with given values. */
805 create_ddg_edge (ddg_node_ptr src
, ddg_node_ptr dest
,
806 dep_type t
, dep_data_type dt
, int l
, int d
)
808 ddg_edge_ptr e
= (ddg_edge_ptr
) xmalloc (sizeof (struct ddg_edge
));
816 e
->next_in
= e
->next_out
= NULL
;
821 /* Add the given edge to the in/out linked lists of the DDG nodes. */
823 add_edge_to_ddg (ddg_ptr g ATTRIBUTE_UNUSED
, ddg_edge_ptr e
)
825 ddg_node_ptr src
= e
->src
;
826 ddg_node_ptr dest
= e
->dest
;
828 /* Should have allocated the sbitmaps. */
829 gcc_assert (src
->successors
&& dest
->predecessors
);
831 bitmap_set_bit (src
->successors
, dest
->cuid
);
832 bitmap_set_bit (dest
->predecessors
, src
->cuid
);
833 e
->next_in
= dest
->in
;
835 e
->next_out
= src
->out
;
841 /* Algorithm for computing the recurrence_length of an scc. We assume at
842 for now that cycles in the data dependence graph contain a single backarc.
843 This simplifies the algorithm, and can be generalized later. */
845 set_recurrence_length (ddg_scc_ptr scc
, ddg_ptr g
)
850 for (j
= 0; j
< scc
->num_backarcs
; j
++)
852 ddg_edge_ptr backarc
= scc
->backarcs
[j
];
854 int distance
= backarc
->distance
;
855 ddg_node_ptr src
= backarc
->dest
;
856 ddg_node_ptr dest
= backarc
->src
;
858 length
= longest_simple_path (g
, src
->cuid
, dest
->cuid
, scc
->nodes
);
861 /* fprintf (stderr, "Backarc not on simple cycle in SCC.\n"); */
864 length
+= backarc
->latency
;
865 result
= MAX (result
, (length
/ distance
));
867 scc
->recurrence_length
= result
;
870 /* Create a new SCC given the set of its nodes. Compute its recurrence_length
871 and mark edges that belong to this scc as IN_SCC. */
873 create_scc (ddg_ptr g
, sbitmap nodes
)
877 sbitmap_iterator sbi
;
879 scc
= (ddg_scc_ptr
) xmalloc (sizeof (struct ddg_scc
));
880 scc
->backarcs
= NULL
;
881 scc
->num_backarcs
= 0;
882 scc
->nodes
= sbitmap_alloc (g
->num_nodes
);
883 bitmap_copy (scc
->nodes
, nodes
);
885 /* Mark the backarcs that belong to this SCC. */
886 EXECUTE_IF_SET_IN_BITMAP (nodes
, 0, u
, sbi
)
889 ddg_node_ptr n
= &g
->nodes
[u
];
891 for (e
= n
->out
; e
; e
= e
->next_out
)
892 if (bitmap_bit_p (nodes
, e
->dest
->cuid
))
894 e
->aux
.count
= IN_SCC
;
896 add_backarc_to_scc (scc
, e
);
900 set_recurrence_length (scc
, g
);
904 /* Cleans the memory allocation of a given SCC. */
906 free_scc (ddg_scc_ptr scc
)
911 sbitmap_free (scc
->nodes
);
912 if (scc
->num_backarcs
> 0)
913 free (scc
->backarcs
);
918 /* Add a given edge known to be a backarc to the given DDG. */
920 add_backarc_to_ddg (ddg_ptr g
, ddg_edge_ptr e
)
922 int size
= (g
->num_backarcs
+ 1) * sizeof (ddg_edge_ptr
);
924 add_edge_to_ddg (g
, e
);
925 g
->backarcs
= (ddg_edge_ptr
*) xrealloc (g
->backarcs
, size
);
926 g
->backarcs
[g
->num_backarcs
++] = e
;
929 /* Add backarc to an SCC. */
931 add_backarc_to_scc (ddg_scc_ptr scc
, ddg_edge_ptr e
)
933 int size
= (scc
->num_backarcs
+ 1) * sizeof (ddg_edge_ptr
);
935 scc
->backarcs
= (ddg_edge_ptr
*) xrealloc (scc
->backarcs
, size
);
936 scc
->backarcs
[scc
->num_backarcs
++] = e
;
939 /* Add the given SCC to the DDG. */
941 add_scc_to_ddg (ddg_all_sccs_ptr g
, ddg_scc_ptr scc
)
943 int size
= (g
->num_sccs
+ 1) * sizeof (ddg_scc_ptr
);
945 g
->sccs
= (ddg_scc_ptr
*) xrealloc (g
->sccs
, size
);
946 g
->sccs
[g
->num_sccs
++] = scc
;
949 /* Given the instruction INSN return the node that represents it. */
951 get_node_of_insn (ddg_ptr g
, rtx_insn
*insn
)
955 for (i
= 0; i
< g
->num_nodes
; i
++)
956 if (insn
== g
->nodes
[i
].insn
)
961 /* Given a set OPS of nodes in the DDG, find the set of their successors
962 which are not in OPS, and set their bits in SUCC. Bits corresponding to
963 OPS are cleared from SUCC. Leaves the other bits in SUCC unchanged. */
965 find_successors (sbitmap succ
, ddg_ptr g
, sbitmap ops
)
968 sbitmap_iterator sbi
;
970 EXECUTE_IF_SET_IN_BITMAP (ops
, 0, i
, sbi
)
972 const sbitmap node_succ
= NODE_SUCCESSORS (&g
->nodes
[i
]);
973 bitmap_ior (succ
, succ
, node_succ
);
976 /* We want those that are not in ops. */
977 bitmap_and_compl (succ
, succ
, ops
);
980 /* Given a set OPS of nodes in the DDG, find the set of their predecessors
981 which are not in OPS, and set their bits in PREDS. Bits corresponding to
982 OPS are cleared from PREDS. Leaves the other bits in PREDS unchanged. */
984 find_predecessors (sbitmap preds
, ddg_ptr g
, sbitmap ops
)
987 sbitmap_iterator sbi
;
989 EXECUTE_IF_SET_IN_BITMAP (ops
, 0, i
, sbi
)
991 const sbitmap node_preds
= NODE_PREDECESSORS (&g
->nodes
[i
]);
992 bitmap_ior (preds
, preds
, node_preds
);
995 /* We want those that are not in ops. */
996 bitmap_and_compl (preds
, preds
, ops
);
1000 /* Compare function to be passed to qsort to order the backarcs in descending
1003 compare_sccs (const void *s1
, const void *s2
)
1005 const int rec_l1
= (*(const ddg_scc_ptr
*)s1
)->recurrence_length
;
1006 const int rec_l2
= (*(const ddg_scc_ptr
*)s2
)->recurrence_length
;
1007 return ((rec_l2
> rec_l1
) - (rec_l2
< rec_l1
));
1011 /* Order the backarcs in descending recMII order using compare_sccs. */
1013 order_sccs (ddg_all_sccs_ptr g
)
1015 qsort (g
->sccs
, g
->num_sccs
, sizeof (ddg_scc_ptr
),
1016 (int (*) (const void *, const void *)) compare_sccs
);
1019 #ifdef ENABLE_CHECKING
1020 /* Check that every node in SCCS belongs to exactly one strongly connected
1021 component and that no element of SCCS is empty. */
1023 check_sccs (ddg_all_sccs_ptr sccs
, int num_nodes
)
1026 sbitmap tmp
= sbitmap_alloc (num_nodes
);
1029 for (i
= 0; i
< sccs
->num_sccs
; i
++)
1031 gcc_assert (!bitmap_empty_p (sccs
->sccs
[i
]->nodes
));
1032 /* Verify that every node in sccs is in exactly one strongly
1033 connected component. */
1034 gcc_assert (!bitmap_intersect_p (tmp
, sccs
->sccs
[i
]->nodes
));
1035 bitmap_ior (tmp
, tmp
, sccs
->sccs
[i
]->nodes
);
1041 /* Perform the Strongly Connected Components decomposing algorithm on the
1042 DDG and return DDG_ALL_SCCS structure that contains them. */
1044 create_ddg_all_sccs (ddg_ptr g
)
1047 int num_nodes
= g
->num_nodes
;
1048 sbitmap from
= sbitmap_alloc (num_nodes
);
1049 sbitmap to
= sbitmap_alloc (num_nodes
);
1050 sbitmap scc_nodes
= sbitmap_alloc (num_nodes
);
1051 ddg_all_sccs_ptr sccs
= (ddg_all_sccs_ptr
)
1052 xmalloc (sizeof (struct ddg_all_sccs
));
1058 for (i
= 0; i
< g
->num_backarcs
; i
++)
1061 ddg_edge_ptr backarc
= g
->backarcs
[i
];
1062 ddg_node_ptr src
= backarc
->src
;
1063 ddg_node_ptr dest
= backarc
->dest
;
1065 /* If the backarc already belongs to an SCC, continue. */
1066 if (backarc
->aux
.count
== IN_SCC
)
1069 bitmap_clear (scc_nodes
);
1070 bitmap_clear (from
);
1072 bitmap_set_bit (from
, dest
->cuid
);
1073 bitmap_set_bit (to
, src
->cuid
);
1075 if (find_nodes_on_paths (scc_nodes
, g
, from
, to
))
1077 scc
= create_scc (g
, scc_nodes
);
1078 add_scc_to_ddg (sccs
, scc
);
1082 sbitmap_free (from
);
1084 sbitmap_free (scc_nodes
);
1085 #ifdef ENABLE_CHECKING
1086 check_sccs (sccs
, num_nodes
);
1091 /* Frees the memory allocated for all SCCs of the DDG, but keeps the DDG. */
1093 free_ddg_all_sccs (ddg_all_sccs_ptr all_sccs
)
1100 for (i
= 0; i
< all_sccs
->num_sccs
; i
++)
1101 free_scc (all_sccs
->sccs
[i
]);
1103 free (all_sccs
->sccs
);
1108 /* Given FROM - a bitmap of source nodes - and TO - a bitmap of destination
1109 nodes - find all nodes that lie on paths from FROM to TO (not excluding
1110 nodes from FROM and TO). Return nonzero if nodes exist. */
1112 find_nodes_on_paths (sbitmap result
, ddg_ptr g
, sbitmap from
, sbitmap to
)
1117 int num_nodes
= g
->num_nodes
;
1118 sbitmap_iterator sbi
;
1120 sbitmap workset
= sbitmap_alloc (num_nodes
);
1121 sbitmap reachable_from
= sbitmap_alloc (num_nodes
);
1122 sbitmap reach_to
= sbitmap_alloc (num_nodes
);
1123 sbitmap tmp
= sbitmap_alloc (num_nodes
);
1125 bitmap_copy (reachable_from
, from
);
1126 bitmap_copy (tmp
, from
);
1132 bitmap_copy (workset
, tmp
);
1134 EXECUTE_IF_SET_IN_BITMAP (workset
, 0, u
, sbi
)
1137 ddg_node_ptr u_node
= &g
->nodes
[u
];
1139 for (e
= u_node
->out
; e
!= (ddg_edge_ptr
) 0; e
= e
->next_out
)
1141 ddg_node_ptr v_node
= e
->dest
;
1142 int v
= v_node
->cuid
;
1144 if (!bitmap_bit_p (reachable_from
, v
))
1146 bitmap_set_bit (reachable_from
, v
);
1147 bitmap_set_bit (tmp
, v
);
1154 bitmap_copy (reach_to
, to
);
1155 bitmap_copy (tmp
, to
);
1161 bitmap_copy (workset
, tmp
);
1163 EXECUTE_IF_SET_IN_BITMAP (workset
, 0, u
, sbi
)
1166 ddg_node_ptr u_node
= &g
->nodes
[u
];
1168 for (e
= u_node
->in
; e
!= (ddg_edge_ptr
) 0; e
= e
->next_in
)
1170 ddg_node_ptr v_node
= e
->src
;
1171 int v
= v_node
->cuid
;
1173 if (!bitmap_bit_p (reach_to
, v
))
1175 bitmap_set_bit (reach_to
, v
);
1176 bitmap_set_bit (tmp
, v
);
1183 answer
= bitmap_and (result
, reachable_from
, reach_to
);
1184 sbitmap_free (workset
);
1185 sbitmap_free (reachable_from
);
1186 sbitmap_free (reach_to
);
1192 /* Updates the counts of U_NODE's successors (that belong to NODES) to be
1193 at-least as large as the count of U_NODE plus the latency between them.
1194 Sets a bit in TMP for each successor whose count was changed (increased).
1195 Returns nonzero if any count was changed. */
1197 update_dist_to_successors (ddg_node_ptr u_node
, sbitmap nodes
, sbitmap tmp
)
1202 for (e
= u_node
->out
; e
; e
= e
->next_out
)
1204 ddg_node_ptr v_node
= e
->dest
;
1205 int v
= v_node
->cuid
;
1207 if (bitmap_bit_p (nodes
, v
)
1208 && (e
->distance
== 0)
1209 && (v_node
->aux
.count
< u_node
->aux
.count
+ e
->latency
))
1211 v_node
->aux
.count
= u_node
->aux
.count
+ e
->latency
;
1212 bitmap_set_bit (tmp
, v
);
1220 /* Find the length of a longest path from SRC to DEST in G,
1221 going only through NODES, and disregarding backarcs. */
1223 longest_simple_path (struct ddg
* g
, int src
, int dest
, sbitmap nodes
)
1229 int num_nodes
= g
->num_nodes
;
1230 sbitmap workset
= sbitmap_alloc (num_nodes
);
1231 sbitmap tmp
= sbitmap_alloc (num_nodes
);
1234 /* Data will hold the distance of the longest path found so far from
1235 src to each node. Initialize to -1 = less than minimum. */
1236 for (i
= 0; i
< g
->num_nodes
; i
++)
1237 g
->nodes
[i
].aux
.count
= -1;
1238 g
->nodes
[src
].aux
.count
= 0;
1241 bitmap_set_bit (tmp
, src
);
1245 sbitmap_iterator sbi
;
1248 bitmap_copy (workset
, tmp
);
1250 EXECUTE_IF_SET_IN_BITMAP (workset
, 0, u
, sbi
)
1252 ddg_node_ptr u_node
= &g
->nodes
[u
];
1254 change
|= update_dist_to_successors (u_node
, nodes
, tmp
);
1257 result
= g
->nodes
[dest
].aux
.count
;
1258 sbitmap_free (workset
);
1263 #endif /* INSN_SCHEDULING */