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"
34 #include "insn-config.h"
35 #include "insn-attr.h"
39 #include "basic-block.h"
40 #include "sched-int.h"
60 #ifdef INSN_SCHEDULING
62 /* A flag indicating that a ddg edge belongs to an SCC or not. */
63 enum edge_flag
{NOT_IN_SCC
= 0, IN_SCC
};
65 /* Forward declarations. */
66 static void add_backarc_to_ddg (ddg_ptr
, ddg_edge_ptr
);
67 static void add_backarc_to_scc (ddg_scc_ptr
, ddg_edge_ptr
);
68 static void add_scc_to_ddg (ddg_all_sccs_ptr
, ddg_scc_ptr
);
69 static void create_ddg_dep_from_intra_loop_link (ddg_ptr
, ddg_node_ptr
,
71 static void create_ddg_dep_no_link (ddg_ptr
, ddg_node_ptr
, ddg_node_ptr
,
72 dep_type
, dep_data_type
, int);
73 static ddg_edge_ptr
create_ddg_edge (ddg_node_ptr
, ddg_node_ptr
, dep_type
,
74 dep_data_type
, int, int);
75 static void add_edge_to_ddg (ddg_ptr g
, ddg_edge_ptr
);
77 /* Auxiliary variable for mem_read_insn_p/mem_write_insn_p. */
78 static bool mem_ref_p
;
80 /* Auxiliary function for mem_read_insn_p. */
82 mark_mem_use (rtx
*x
, void *)
84 subrtx_iterator::array_type array
;
85 FOR_EACH_SUBRTX (iter
, array
, *x
, NONCONST
)
93 /* Returns nonzero if INSN reads from memory. */
95 mem_read_insn_p (rtx_insn
*insn
)
98 note_uses (&PATTERN (insn
), mark_mem_use
, NULL
);
103 mark_mem_store (rtx loc
, const_rtx setter ATTRIBUTE_UNUSED
, void *data ATTRIBUTE_UNUSED
)
109 /* Returns nonzero if INSN writes to memory. */
111 mem_write_insn_p (rtx_insn
*insn
)
114 note_stores (PATTERN (insn
), mark_mem_store
, NULL
);
118 /* Returns nonzero if X has access to memory. */
120 rtx_mem_access_p (rtx x
)
133 fmt
= GET_RTX_FORMAT (code
);
134 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
138 if (rtx_mem_access_p (XEXP (x
, i
)))
141 else if (fmt
[i
] == 'E')
142 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
144 if (rtx_mem_access_p (XVECEXP (x
, i
, j
)))
151 /* Returns nonzero if INSN reads to or writes from memory. */
153 mem_access_insn_p (rtx_insn
*insn
)
155 return rtx_mem_access_p (PATTERN (insn
));
158 /* Return true if DEF_INSN contains address being auto-inc or auto-dec
159 which is used in USE_INSN. Otherwise return false. The result is
160 being used to decide whether to remove the edge between def_insn and
161 use_insn when -fmodulo-sched-allow-regmoves is set. This function
162 doesn't need to consider the specific address register; no reg_moves
163 will be allowed for any life range defined by def_insn and used
164 by use_insn, if use_insn uses an address register auto-inc'ed by
167 autoinc_var_is_used_p (rtx_insn
*def_insn
, rtx_insn
*use_insn
)
171 for (note
= REG_NOTES (def_insn
); note
; note
= XEXP (note
, 1))
172 if (REG_NOTE_KIND (note
) == REG_INC
173 && reg_referenced_p (XEXP (note
, 0), PATTERN (use_insn
)))
179 /* Return true if one of the definitions in INSN has MODE_CC. Otherwise
182 def_has_ccmode_p (rtx_insn
*insn
)
186 FOR_EACH_INSN_DEF (def
, insn
)
188 machine_mode mode
= GET_MODE (DF_REF_REG (def
));
190 if (GET_MODE_CLASS (mode
) == MODE_CC
)
197 /* Computes the dependence parameters (latency, distance etc.), creates
198 a ddg_edge and adds it to the given DDG. */
200 create_ddg_dep_from_intra_loop_link (ddg_ptr g
, ddg_node_ptr src_node
,
201 ddg_node_ptr dest_node
, dep_t link
)
204 int latency
, distance
= 0;
205 dep_type t
= TRUE_DEP
;
206 dep_data_type dt
= (mem_access_insn_p (src_node
->insn
)
207 && mem_access_insn_p (dest_node
->insn
) ? MEM_DEP
209 gcc_assert (src_node
->cuid
< dest_node
->cuid
);
212 /* Note: REG_DEP_ANTI applies to MEM ANTI_DEP as well!! */
213 if (DEP_TYPE (link
) == REG_DEP_ANTI
)
215 else if (DEP_TYPE (link
) == REG_DEP_OUTPUT
)
218 gcc_assert (!DEBUG_INSN_P (dest_node
->insn
) || t
== ANTI_DEP
);
219 gcc_assert (!DEBUG_INSN_P (src_node
->insn
) || t
== ANTI_DEP
);
221 /* We currently choose not to create certain anti-deps edges and
222 compensate for that by generating reg-moves based on the life-range
223 analysis. The anti-deps that will be deleted are the ones which
224 have true-deps edges in the opposite direction (in other words
225 the kernel has only one def of the relevant register).
226 If the address that is being auto-inc or auto-dec in DEST_NODE
227 is used in SRC_NODE then do not remove the edge to make sure
228 reg-moves will not be created for this address.
229 TODO: support the removal of all anti-deps edges, i.e. including those
230 whose register has multiple defs in the loop. */
231 if (flag_modulo_sched_allow_regmoves
232 && (t
== ANTI_DEP
&& dt
== REG_DEP
)
233 && !def_has_ccmode_p (dest_node
->insn
)
234 && !autoinc_var_is_used_p (dest_node
->insn
, src_node
->insn
))
238 set
= single_set (dest_node
->insn
);
239 /* TODO: Handle registers that REG_P is not true for them, i.e.
240 subregs and special registers. */
241 if (set
&& REG_P (SET_DEST (set
)))
243 int regno
= REGNO (SET_DEST (set
));
245 struct df_rd_bb_info
*bb_info
= DF_RD_BB_INFO (g
->bb
);
247 first_def
= df_bb_regno_first_def_find (g
->bb
, regno
);
248 gcc_assert (first_def
);
250 if (bitmap_bit_p (&bb_info
->gen
, DF_REF_ID (first_def
)))
255 latency
= dep_cost (link
);
256 e
= create_ddg_edge (src_node
, dest_node
, t
, dt
, latency
, distance
);
257 add_edge_to_ddg (g
, e
);
260 /* The same as the above function, but it doesn't require a link parameter. */
262 create_ddg_dep_no_link (ddg_ptr g
, ddg_node_ptr from
, ddg_node_ptr to
,
263 dep_type d_t
, dep_data_type d_dt
, int distance
)
267 enum reg_note dep_kind
;
268 struct _dep _dep
, *dep
= &_dep
;
270 gcc_assert (!DEBUG_INSN_P (to
->insn
) || d_t
== ANTI_DEP
);
271 gcc_assert (!DEBUG_INSN_P (from
->insn
) || d_t
== ANTI_DEP
);
274 dep_kind
= REG_DEP_ANTI
;
275 else if (d_t
== OUTPUT_DEP
)
276 dep_kind
= REG_DEP_OUTPUT
;
279 gcc_assert (d_t
== TRUE_DEP
);
281 dep_kind
= REG_DEP_TRUE
;
284 init_dep (dep
, from
->insn
, to
->insn
, dep_kind
);
288 e
= create_ddg_edge (from
, to
, d_t
, d_dt
, l
, distance
);
290 add_backarc_to_ddg (g
, e
);
292 add_edge_to_ddg (g
, e
);
296 /* Given a downwards exposed register def LAST_DEF (which is the last
297 definition of that register in the bb), add inter-loop true dependences
298 to all its uses in the next iteration, an output dependence to the
299 first def of the same register (possibly itself) in the next iteration
300 and anti-dependences from its uses in the current iteration to the
301 first definition in the next iteration. */
303 add_cross_iteration_register_deps (ddg_ptr g
, df_ref last_def
)
305 int regno
= DF_REF_REGNO (last_def
);
306 struct df_link
*r_use
;
307 int has_use_in_bb_p
= false;
308 rtx_insn
*def_insn
= DF_REF_INSN (last_def
);
309 ddg_node_ptr last_def_node
= get_node_of_insn (g
, def_insn
);
310 ddg_node_ptr use_node
;
311 #ifdef ENABLE_CHECKING
312 struct df_rd_bb_info
*bb_info
= DF_RD_BB_INFO (g
->bb
);
314 df_ref first_def
= df_bb_regno_first_def_find (g
->bb
, regno
);
316 gcc_assert (last_def_node
);
317 gcc_assert (first_def
);
319 #ifdef ENABLE_CHECKING
320 if (DF_REF_ID (last_def
) != DF_REF_ID (first_def
))
321 gcc_assert (!bitmap_bit_p (&bb_info
->gen
,
322 DF_REF_ID (first_def
)));
325 /* Create inter-loop true dependences and anti dependences. */
326 for (r_use
= DF_REF_CHAIN (last_def
); r_use
!= NULL
; r_use
= r_use
->next
)
328 rtx_insn
*use_insn
= DF_REF_INSN (r_use
->ref
);
330 if (BLOCK_FOR_INSN (use_insn
) != g
->bb
)
333 /* ??? Do not handle uses with DF_REF_IN_NOTE notes. */
334 use_node
= get_node_of_insn (g
, use_insn
);
335 gcc_assert (use_node
);
336 has_use_in_bb_p
= true;
337 if (use_node
->cuid
<= last_def_node
->cuid
)
339 /* Add true deps from last_def to it's uses in the next
340 iteration. Any such upwards exposed use appears before
342 create_ddg_dep_no_link (g
, last_def_node
, use_node
,
343 DEBUG_INSN_P (use_insn
) ? ANTI_DEP
: TRUE_DEP
,
346 else if (!DEBUG_INSN_P (use_insn
))
348 /* Add anti deps from last_def's uses in the current iteration
349 to the first def in the next iteration. We do not add ANTI
350 dep when there is an intra-loop TRUE dep in the opposite
351 direction, but use regmoves to fix such disregarded ANTI
352 deps when broken. If the first_def reaches the USE then
353 there is such a dep. */
354 ddg_node_ptr first_def_node
= get_node_of_insn (g
,
355 DF_REF_INSN (first_def
));
357 gcc_assert (first_def_node
);
359 /* Always create the edge if the use node is a branch in
360 order to prevent the creation of reg-moves.
361 If the address that is being auto-inc or auto-dec in LAST_DEF
362 is used in USE_INSN then do not remove the edge to make sure
363 reg-moves will not be created for that address. */
364 if (DF_REF_ID (last_def
) != DF_REF_ID (first_def
)
365 || !flag_modulo_sched_allow_regmoves
366 || JUMP_P (use_node
->insn
)
367 || autoinc_var_is_used_p (DF_REF_INSN (last_def
), use_insn
)
368 || def_has_ccmode_p (DF_REF_INSN (last_def
)))
369 create_ddg_dep_no_link (g
, use_node
, first_def_node
, ANTI_DEP
,
374 /* Create an inter-loop output dependence between LAST_DEF (which is the
375 last def in its block, being downwards exposed) and the first def in
376 its block. Avoid creating a self output dependence. Avoid creating
377 an output dependence if there is a dependence path between the two
378 defs starting with a true dependence to a use which can be in the
379 next iteration; followed by an anti dependence of that use to the
380 first def (i.e. if there is a use between the two defs.) */
381 if (!has_use_in_bb_p
)
383 ddg_node_ptr dest_node
;
385 if (DF_REF_ID (last_def
) == DF_REF_ID (first_def
))
388 dest_node
= get_node_of_insn (g
, DF_REF_INSN (first_def
));
389 gcc_assert (dest_node
);
390 create_ddg_dep_no_link (g
, last_def_node
, dest_node
,
391 OUTPUT_DEP
, REG_DEP
, 1);
394 /* Build inter-loop dependencies, by looking at DF analysis backwards. */
396 build_inter_loop_deps (ddg_ptr g
)
399 struct df_rd_bb_info
*rd_bb_info
;
402 rd_bb_info
= DF_RD_BB_INFO (g
->bb
);
404 /* Find inter-loop register output, true and anti deps. */
405 EXECUTE_IF_SET_IN_BITMAP (&rd_bb_info
->gen
, 0, rd_num
, bi
)
407 df_ref rd
= DF_DEFS_GET (rd_num
);
409 add_cross_iteration_register_deps (g
, rd
);
414 /* Return true if two specified instructions have mem expr with conflict
417 insns_may_alias_p (rtx_insn
*insn1
, rtx_insn
*insn2
)
419 subrtx_iterator::array_type array1
;
420 subrtx_iterator::array_type array2
;
421 FOR_EACH_SUBRTX (iter1
, array1
, PATTERN (insn1
), NONCONST
)
423 const_rtx x1
= *iter1
;
425 FOR_EACH_SUBRTX (iter2
, array2
, PATTERN (insn2
), NONCONST
)
427 const_rtx x2
= *iter2
;
428 if (MEM_P (x2
) && may_alias_p (x2
, x1
))
435 /* Given two nodes, analyze their RTL insns and add intra-loop mem deps
438 add_intra_loop_mem_dep (ddg_ptr g
, ddg_node_ptr from
, ddg_node_ptr to
)
441 if ((from
->cuid
== to
->cuid
)
442 || !insns_may_alias_p (from
->insn
, to
->insn
))
443 /* Do not create edge if memory references have disjoint alias sets
444 or 'to' and 'from' are the same instruction. */
447 if (mem_write_insn_p (from
->insn
))
449 if (mem_read_insn_p (to
->insn
))
450 create_ddg_dep_no_link (g
, from
, to
,
451 DEBUG_INSN_P (to
->insn
)
452 ? ANTI_DEP
: TRUE_DEP
, MEM_DEP
, 0);
454 create_ddg_dep_no_link (g
, from
, to
,
455 DEBUG_INSN_P (to
->insn
)
456 ? ANTI_DEP
: OUTPUT_DEP
, MEM_DEP
, 0);
458 else if (!mem_read_insn_p (to
->insn
))
459 create_ddg_dep_no_link (g
, from
, to
, ANTI_DEP
, MEM_DEP
, 0);
462 /* Given two nodes, analyze their RTL insns and add inter-loop mem deps
465 add_inter_loop_mem_dep (ddg_ptr g
, ddg_node_ptr from
, ddg_node_ptr to
)
467 if (!insns_may_alias_p (from
->insn
, to
->insn
))
468 /* Do not create edge if memory references have disjoint alias sets. */
471 if (mem_write_insn_p (from
->insn
))
473 if (mem_read_insn_p (to
->insn
))
474 create_ddg_dep_no_link (g
, from
, to
,
475 DEBUG_INSN_P (to
->insn
)
476 ? ANTI_DEP
: TRUE_DEP
, MEM_DEP
, 1);
477 else if (from
->cuid
!= to
->cuid
)
478 create_ddg_dep_no_link (g
, from
, to
,
479 DEBUG_INSN_P (to
->insn
)
480 ? ANTI_DEP
: OUTPUT_DEP
, MEM_DEP
, 1);
484 if (mem_read_insn_p (to
->insn
))
486 else if (from
->cuid
!= to
->cuid
)
488 create_ddg_dep_no_link (g
, from
, to
, ANTI_DEP
, MEM_DEP
, 1);
489 if (DEBUG_INSN_P (from
->insn
) || DEBUG_INSN_P (to
->insn
))
490 create_ddg_dep_no_link (g
, to
, from
, ANTI_DEP
, MEM_DEP
, 1);
492 create_ddg_dep_no_link (g
, to
, from
, TRUE_DEP
, MEM_DEP
, 1);
498 /* Perform intra-block Data Dependency analysis and connect the nodes in
499 the DDG. We assume the loop has a single basic block. */
501 build_intra_loop_deps (ddg_ptr g
)
504 /* Hold the dependency analysis state during dependency calculations. */
505 struct deps_desc tmp_deps
;
506 rtx_insn
*head
, *tail
;
508 /* Build the dependence information, using the sched_analyze function. */
510 init_deps (&tmp_deps
, false);
512 /* Do the intra-block data dependence analysis for the given block. */
513 get_ebb_head_tail (g
->bb
, g
->bb
, &head
, &tail
);
514 sched_analyze (&tmp_deps
, head
, tail
);
516 /* Build intra-loop data dependencies using the scheduler dependency
518 for (i
= 0; i
< g
->num_nodes
; i
++)
520 ddg_node_ptr dest_node
= &g
->nodes
[i
];
521 sd_iterator_def sd_it
;
524 if (! INSN_P (dest_node
->insn
))
527 FOR_EACH_DEP (dest_node
->insn
, SD_LIST_BACK
, sd_it
, dep
)
529 rtx_insn
*src_insn
= DEP_PRO (dep
);
530 ddg_node_ptr src_node
;
532 /* Don't add dependencies on debug insns to non-debug insns
533 to avoid codegen differences between -g and -g0. */
534 if (DEBUG_INSN_P (src_insn
) && !DEBUG_INSN_P (dest_node
->insn
))
537 src_node
= get_node_of_insn (g
, src_insn
);
542 create_ddg_dep_from_intra_loop_link (g
, src_node
, dest_node
, dep
);
545 /* If this insn modifies memory, add an edge to all insns that access
547 if (mem_access_insn_p (dest_node
->insn
))
551 for (j
= 0; j
<= i
; j
++)
553 ddg_node_ptr j_node
= &g
->nodes
[j
];
554 if (DEBUG_INSN_P (j_node
->insn
))
556 if (mem_access_insn_p (j_node
->insn
))
558 /* Don't bother calculating inter-loop dep if an intra-loop dep
560 if (! bitmap_bit_p (dest_node
->successors
, j
))
561 add_inter_loop_mem_dep (g
, dest_node
, j_node
);
562 /* If -fmodulo-sched-allow-regmoves
563 is set certain anti-dep edges are not created.
564 It might be that these anti-dep edges are on the
565 path from one memory instruction to another such that
566 removing these edges could cause a violation of the
567 memory dependencies. Thus we add intra edges between
568 every two memory instructions in this case. */
569 if (flag_modulo_sched_allow_regmoves
570 && !bitmap_bit_p (dest_node
->predecessors
, j
))
571 add_intra_loop_mem_dep (g
, j_node
, dest_node
);
577 /* Free the INSN_LISTs. */
578 finish_deps_global ();
579 free_deps (&tmp_deps
);
581 /* Free dependencies. */
582 sched_free_deps (head
, tail
, false);
586 /* Given a basic block, create its DDG and return a pointer to a variable
587 of ddg type that represents it.
588 Initialize the ddg structure fields to the appropriate values. */
590 create_ddg (basic_block bb
, int closing_branch_deps
)
593 rtx_insn
*insn
, *first_note
;
597 g
= (ddg_ptr
) xcalloc (1, sizeof (struct ddg
));
600 g
->closing_branch_deps
= closing_branch_deps
;
602 /* Count the number of insns in the BB. */
603 for (insn
= BB_HEAD (bb
); insn
!= NEXT_INSN (BB_END (bb
));
604 insn
= NEXT_INSN (insn
))
606 if (! INSN_P (insn
) || GET_CODE (PATTERN (insn
)) == USE
)
609 if (DEBUG_INSN_P (insn
))
613 if (mem_read_insn_p (insn
))
615 if (mem_write_insn_p (insn
))
621 /* There is nothing to do for this BB. */
622 if ((num_nodes
- g
->num_debug
) <= 1)
628 /* Allocate the nodes array, and initialize the nodes. */
629 g
->num_nodes
= num_nodes
;
630 g
->nodes
= (ddg_node_ptr
) xcalloc (num_nodes
, sizeof (struct ddg_node
));
631 g
->closing_branch
= NULL
;
634 for (insn
= BB_HEAD (bb
); insn
!= NEXT_INSN (BB_END (bb
));
635 insn
= NEXT_INSN (insn
))
639 if (! first_note
&& NOTE_P (insn
)
640 && NOTE_KIND (insn
) != NOTE_INSN_BASIC_BLOCK
)
646 gcc_assert (!g
->closing_branch
);
647 g
->closing_branch
= &g
->nodes
[i
];
649 else if (GET_CODE (PATTERN (insn
)) == USE
)
656 g
->nodes
[i
].cuid
= i
;
657 g
->nodes
[i
].successors
= sbitmap_alloc (num_nodes
);
658 bitmap_clear (g
->nodes
[i
].successors
);
659 g
->nodes
[i
].predecessors
= sbitmap_alloc (num_nodes
);
660 bitmap_clear (g
->nodes
[i
].predecessors
);
661 g
->nodes
[i
].first_note
= (first_note
? first_note
: insn
);
662 g
->nodes
[i
++].insn
= insn
;
666 /* We must have found a branch in DDG. */
667 gcc_assert (g
->closing_branch
);
670 /* Build the data dependency graph. */
671 build_intra_loop_deps (g
);
672 build_inter_loop_deps (g
);
676 /* Free all the memory allocated for the DDG. */
685 for (i
= 0; i
< g
->num_nodes
; i
++)
687 ddg_edge_ptr e
= g
->nodes
[i
].out
;
691 ddg_edge_ptr next
= e
->next_out
;
696 sbitmap_free (g
->nodes
[i
].successors
);
697 sbitmap_free (g
->nodes
[i
].predecessors
);
699 if (g
->num_backarcs
> 0)
706 print_ddg_edge (FILE *file
, ddg_edge_ptr e
)
722 fprintf (file
, " [%d -(%c,%d,%d)-> %d] ", INSN_UID (e
->src
->insn
),
723 dep_c
, e
->latency
, e
->distance
, INSN_UID (e
->dest
->insn
));
726 /* Print the DDG nodes with there in/out edges to the dump file. */
728 print_ddg (FILE *file
, ddg_ptr g
)
732 for (i
= 0; i
< g
->num_nodes
; i
++)
736 fprintf (file
, "Node num: %d\n", g
->nodes
[i
].cuid
);
737 print_rtl_single (file
, g
->nodes
[i
].insn
);
738 fprintf (file
, "OUT ARCS: ");
739 for (e
= g
->nodes
[i
].out
; e
; e
= e
->next_out
)
740 print_ddg_edge (file
, e
);
742 fprintf (file
, "\nIN ARCS: ");
743 for (e
= g
->nodes
[i
].in
; e
; e
= e
->next_in
)
744 print_ddg_edge (file
, e
);
746 fprintf (file
, "\n");
750 /* Print the given DDG in VCG format. */
752 vcg_print_ddg (FILE *file
, ddg_ptr g
)
756 fprintf (file
, "graph: {\n");
757 for (src_cuid
= 0; src_cuid
< g
->num_nodes
; src_cuid
++)
760 int src_uid
= INSN_UID (g
->nodes
[src_cuid
].insn
);
762 fprintf (file
, "node: {title: \"%d_%d\" info1: \"", src_cuid
, src_uid
);
763 print_rtl_single (file
, g
->nodes
[src_cuid
].insn
);
764 fprintf (file
, "\"}\n");
765 for (e
= g
->nodes
[src_cuid
].out
; e
; e
= e
->next_out
)
767 int dst_uid
= INSN_UID (e
->dest
->insn
);
768 int dst_cuid
= e
->dest
->cuid
;
770 /* Give the backarcs a different color. */
772 fprintf (file
, "backedge: {color: red ");
774 fprintf (file
, "edge: { ");
776 fprintf (file
, "sourcename: \"%d_%d\" ", src_cuid
, src_uid
);
777 fprintf (file
, "targetname: \"%d_%d\" ", dst_cuid
, dst_uid
);
778 fprintf (file
, "label: \"%d_%d\"}\n", e
->latency
, e
->distance
);
781 fprintf (file
, "}\n");
784 /* Dump the sccs in SCCS. */
786 print_sccs (FILE *file
, ddg_all_sccs_ptr sccs
, ddg_ptr g
)
789 sbitmap_iterator sbi
;
795 fprintf (file
, "\n;; Number of SCC nodes - %d\n", sccs
->num_sccs
);
796 for (i
= 0; i
< sccs
->num_sccs
; i
++)
798 fprintf (file
, "SCC number: %d\n", i
);
799 EXECUTE_IF_SET_IN_BITMAP (sccs
->sccs
[i
]->nodes
, 0, u
, sbi
)
801 fprintf (file
, "insn num %d\n", u
);
802 print_rtl_single (file
, g
->nodes
[u
].insn
);
805 fprintf (file
, "\n");
808 /* Create an edge and initialize it with given values. */
810 create_ddg_edge (ddg_node_ptr src
, ddg_node_ptr dest
,
811 dep_type t
, dep_data_type dt
, int l
, int d
)
813 ddg_edge_ptr e
= (ddg_edge_ptr
) xmalloc (sizeof (struct ddg_edge
));
821 e
->next_in
= e
->next_out
= NULL
;
826 /* Add the given edge to the in/out linked lists of the DDG nodes. */
828 add_edge_to_ddg (ddg_ptr g ATTRIBUTE_UNUSED
, ddg_edge_ptr e
)
830 ddg_node_ptr src
= e
->src
;
831 ddg_node_ptr dest
= e
->dest
;
833 /* Should have allocated the sbitmaps. */
834 gcc_assert (src
->successors
&& dest
->predecessors
);
836 bitmap_set_bit (src
->successors
, dest
->cuid
);
837 bitmap_set_bit (dest
->predecessors
, src
->cuid
);
838 e
->next_in
= dest
->in
;
840 e
->next_out
= src
->out
;
846 /* Algorithm for computing the recurrence_length of an scc. We assume at
847 for now that cycles in the data dependence graph contain a single backarc.
848 This simplifies the algorithm, and can be generalized later. */
850 set_recurrence_length (ddg_scc_ptr scc
, ddg_ptr g
)
855 for (j
= 0; j
< scc
->num_backarcs
; j
++)
857 ddg_edge_ptr backarc
= scc
->backarcs
[j
];
859 int distance
= backarc
->distance
;
860 ddg_node_ptr src
= backarc
->dest
;
861 ddg_node_ptr dest
= backarc
->src
;
863 length
= longest_simple_path (g
, src
->cuid
, dest
->cuid
, scc
->nodes
);
866 /* fprintf (stderr, "Backarc not on simple cycle in SCC.\n"); */
869 length
+= backarc
->latency
;
870 result
= MAX (result
, (length
/ distance
));
872 scc
->recurrence_length
= result
;
875 /* Create a new SCC given the set of its nodes. Compute its recurrence_length
876 and mark edges that belong to this scc as IN_SCC. */
878 create_scc (ddg_ptr g
, sbitmap nodes
)
882 sbitmap_iterator sbi
;
884 scc
= (ddg_scc_ptr
) xmalloc (sizeof (struct ddg_scc
));
885 scc
->backarcs
= NULL
;
886 scc
->num_backarcs
= 0;
887 scc
->nodes
= sbitmap_alloc (g
->num_nodes
);
888 bitmap_copy (scc
->nodes
, nodes
);
890 /* Mark the backarcs that belong to this SCC. */
891 EXECUTE_IF_SET_IN_BITMAP (nodes
, 0, u
, sbi
)
894 ddg_node_ptr n
= &g
->nodes
[u
];
896 for (e
= n
->out
; e
; e
= e
->next_out
)
897 if (bitmap_bit_p (nodes
, e
->dest
->cuid
))
899 e
->aux
.count
= IN_SCC
;
901 add_backarc_to_scc (scc
, e
);
905 set_recurrence_length (scc
, g
);
909 /* Cleans the memory allocation of a given SCC. */
911 free_scc (ddg_scc_ptr scc
)
916 sbitmap_free (scc
->nodes
);
917 if (scc
->num_backarcs
> 0)
918 free (scc
->backarcs
);
923 /* Add a given edge known to be a backarc to the given DDG. */
925 add_backarc_to_ddg (ddg_ptr g
, ddg_edge_ptr e
)
927 int size
= (g
->num_backarcs
+ 1) * sizeof (ddg_edge_ptr
);
929 add_edge_to_ddg (g
, e
);
930 g
->backarcs
= (ddg_edge_ptr
*) xrealloc (g
->backarcs
, size
);
931 g
->backarcs
[g
->num_backarcs
++] = e
;
934 /* Add backarc to an SCC. */
936 add_backarc_to_scc (ddg_scc_ptr scc
, ddg_edge_ptr e
)
938 int size
= (scc
->num_backarcs
+ 1) * sizeof (ddg_edge_ptr
);
940 scc
->backarcs
= (ddg_edge_ptr
*) xrealloc (scc
->backarcs
, size
);
941 scc
->backarcs
[scc
->num_backarcs
++] = e
;
944 /* Add the given SCC to the DDG. */
946 add_scc_to_ddg (ddg_all_sccs_ptr g
, ddg_scc_ptr scc
)
948 int size
= (g
->num_sccs
+ 1) * sizeof (ddg_scc_ptr
);
950 g
->sccs
= (ddg_scc_ptr
*) xrealloc (g
->sccs
, size
);
951 g
->sccs
[g
->num_sccs
++] = scc
;
954 /* Given the instruction INSN return the node that represents it. */
956 get_node_of_insn (ddg_ptr g
, rtx_insn
*insn
)
960 for (i
= 0; i
< g
->num_nodes
; i
++)
961 if (insn
== g
->nodes
[i
].insn
)
966 /* Given a set OPS of nodes in the DDG, find the set of their successors
967 which are not in OPS, and set their bits in SUCC. Bits corresponding to
968 OPS are cleared from SUCC. Leaves the other bits in SUCC unchanged. */
970 find_successors (sbitmap succ
, ddg_ptr g
, sbitmap ops
)
973 sbitmap_iterator sbi
;
975 EXECUTE_IF_SET_IN_BITMAP (ops
, 0, i
, sbi
)
977 const sbitmap node_succ
= NODE_SUCCESSORS (&g
->nodes
[i
]);
978 bitmap_ior (succ
, succ
, node_succ
);
981 /* We want those that are not in ops. */
982 bitmap_and_compl (succ
, succ
, ops
);
985 /* Given a set OPS of nodes in the DDG, find the set of their predecessors
986 which are not in OPS, and set their bits in PREDS. Bits corresponding to
987 OPS are cleared from PREDS. Leaves the other bits in PREDS unchanged. */
989 find_predecessors (sbitmap preds
, ddg_ptr g
, sbitmap ops
)
992 sbitmap_iterator sbi
;
994 EXECUTE_IF_SET_IN_BITMAP (ops
, 0, i
, sbi
)
996 const sbitmap node_preds
= NODE_PREDECESSORS (&g
->nodes
[i
]);
997 bitmap_ior (preds
, preds
, node_preds
);
1000 /* We want those that are not in ops. */
1001 bitmap_and_compl (preds
, preds
, ops
);
1005 /* Compare function to be passed to qsort to order the backarcs in descending
1008 compare_sccs (const void *s1
, const void *s2
)
1010 const int rec_l1
= (*(const ddg_scc_ptr
*)s1
)->recurrence_length
;
1011 const int rec_l2
= (*(const ddg_scc_ptr
*)s2
)->recurrence_length
;
1012 return ((rec_l2
> rec_l1
) - (rec_l2
< rec_l1
));
1016 /* Order the backarcs in descending recMII order using compare_sccs. */
1018 order_sccs (ddg_all_sccs_ptr g
)
1020 qsort (g
->sccs
, g
->num_sccs
, sizeof (ddg_scc_ptr
),
1021 (int (*) (const void *, const void *)) compare_sccs
);
1024 #ifdef ENABLE_CHECKING
1025 /* Check that every node in SCCS belongs to exactly one strongly connected
1026 component and that no element of SCCS is empty. */
1028 check_sccs (ddg_all_sccs_ptr sccs
, int num_nodes
)
1031 sbitmap tmp
= sbitmap_alloc (num_nodes
);
1034 for (i
= 0; i
< sccs
->num_sccs
; i
++)
1036 gcc_assert (!bitmap_empty_p (sccs
->sccs
[i
]->nodes
));
1037 /* Verify that every node in sccs is in exactly one strongly
1038 connected component. */
1039 gcc_assert (!bitmap_intersect_p (tmp
, sccs
->sccs
[i
]->nodes
));
1040 bitmap_ior (tmp
, tmp
, sccs
->sccs
[i
]->nodes
);
1046 /* Perform the Strongly Connected Components decomposing algorithm on the
1047 DDG and return DDG_ALL_SCCS structure that contains them. */
1049 create_ddg_all_sccs (ddg_ptr g
)
1052 int num_nodes
= g
->num_nodes
;
1053 sbitmap from
= sbitmap_alloc (num_nodes
);
1054 sbitmap to
= sbitmap_alloc (num_nodes
);
1055 sbitmap scc_nodes
= sbitmap_alloc (num_nodes
);
1056 ddg_all_sccs_ptr sccs
= (ddg_all_sccs_ptr
)
1057 xmalloc (sizeof (struct ddg_all_sccs
));
1063 for (i
= 0; i
< g
->num_backarcs
; i
++)
1066 ddg_edge_ptr backarc
= g
->backarcs
[i
];
1067 ddg_node_ptr src
= backarc
->src
;
1068 ddg_node_ptr dest
= backarc
->dest
;
1070 /* If the backarc already belongs to an SCC, continue. */
1071 if (backarc
->aux
.count
== IN_SCC
)
1074 bitmap_clear (scc_nodes
);
1075 bitmap_clear (from
);
1077 bitmap_set_bit (from
, dest
->cuid
);
1078 bitmap_set_bit (to
, src
->cuid
);
1080 if (find_nodes_on_paths (scc_nodes
, g
, from
, to
))
1082 scc
= create_scc (g
, scc_nodes
);
1083 add_scc_to_ddg (sccs
, scc
);
1087 sbitmap_free (from
);
1089 sbitmap_free (scc_nodes
);
1090 #ifdef ENABLE_CHECKING
1091 check_sccs (sccs
, num_nodes
);
1096 /* Frees the memory allocated for all SCCs of the DDG, but keeps the DDG. */
1098 free_ddg_all_sccs (ddg_all_sccs_ptr all_sccs
)
1105 for (i
= 0; i
< all_sccs
->num_sccs
; i
++)
1106 free_scc (all_sccs
->sccs
[i
]);
1108 free (all_sccs
->sccs
);
1113 /* Given FROM - a bitmap of source nodes - and TO - a bitmap of destination
1114 nodes - find all nodes that lie on paths from FROM to TO (not excluding
1115 nodes from FROM and TO). Return nonzero if nodes exist. */
1117 find_nodes_on_paths (sbitmap result
, ddg_ptr g
, sbitmap from
, sbitmap to
)
1122 int num_nodes
= g
->num_nodes
;
1123 sbitmap_iterator sbi
;
1125 sbitmap workset
= sbitmap_alloc (num_nodes
);
1126 sbitmap reachable_from
= sbitmap_alloc (num_nodes
);
1127 sbitmap reach_to
= sbitmap_alloc (num_nodes
);
1128 sbitmap tmp
= sbitmap_alloc (num_nodes
);
1130 bitmap_copy (reachable_from
, from
);
1131 bitmap_copy (tmp
, from
);
1137 bitmap_copy (workset
, tmp
);
1139 EXECUTE_IF_SET_IN_BITMAP (workset
, 0, u
, sbi
)
1142 ddg_node_ptr u_node
= &g
->nodes
[u
];
1144 for (e
= u_node
->out
; e
!= (ddg_edge_ptr
) 0; e
= e
->next_out
)
1146 ddg_node_ptr v_node
= e
->dest
;
1147 int v
= v_node
->cuid
;
1149 if (!bitmap_bit_p (reachable_from
, v
))
1151 bitmap_set_bit (reachable_from
, v
);
1152 bitmap_set_bit (tmp
, v
);
1159 bitmap_copy (reach_to
, to
);
1160 bitmap_copy (tmp
, to
);
1166 bitmap_copy (workset
, tmp
);
1168 EXECUTE_IF_SET_IN_BITMAP (workset
, 0, u
, sbi
)
1171 ddg_node_ptr u_node
= &g
->nodes
[u
];
1173 for (e
= u_node
->in
; e
!= (ddg_edge_ptr
) 0; e
= e
->next_in
)
1175 ddg_node_ptr v_node
= e
->src
;
1176 int v
= v_node
->cuid
;
1178 if (!bitmap_bit_p (reach_to
, v
))
1180 bitmap_set_bit (reach_to
, v
);
1181 bitmap_set_bit (tmp
, v
);
1188 answer
= bitmap_and (result
, reachable_from
, reach_to
);
1189 sbitmap_free (workset
);
1190 sbitmap_free (reachable_from
);
1191 sbitmap_free (reach_to
);
1197 /* Updates the counts of U_NODE's successors (that belong to NODES) to be
1198 at-least as large as the count of U_NODE plus the latency between them.
1199 Sets a bit in TMP for each successor whose count was changed (increased).
1200 Returns nonzero if any count was changed. */
1202 update_dist_to_successors (ddg_node_ptr u_node
, sbitmap nodes
, sbitmap tmp
)
1207 for (e
= u_node
->out
; e
; e
= e
->next_out
)
1209 ddg_node_ptr v_node
= e
->dest
;
1210 int v
= v_node
->cuid
;
1212 if (bitmap_bit_p (nodes
, v
)
1213 && (e
->distance
== 0)
1214 && (v_node
->aux
.count
< u_node
->aux
.count
+ e
->latency
))
1216 v_node
->aux
.count
= u_node
->aux
.count
+ e
->latency
;
1217 bitmap_set_bit (tmp
, v
);
1225 /* Find the length of a longest path from SRC to DEST in G,
1226 going only through NODES, and disregarding backarcs. */
1228 longest_simple_path (struct ddg
* g
, int src
, int dest
, sbitmap nodes
)
1234 int num_nodes
= g
->num_nodes
;
1235 sbitmap workset
= sbitmap_alloc (num_nodes
);
1236 sbitmap tmp
= sbitmap_alloc (num_nodes
);
1239 /* Data will hold the distance of the longest path found so far from
1240 src to each node. Initialize to -1 = less than minimum. */
1241 for (i
= 0; i
< g
->num_nodes
; i
++)
1242 g
->nodes
[i
].aux
.count
= -1;
1243 g
->nodes
[src
].aux
.count
= 0;
1246 bitmap_set_bit (tmp
, src
);
1250 sbitmap_iterator sbi
;
1253 bitmap_copy (workset
, tmp
);
1255 EXECUTE_IF_SET_IN_BITMAP (workset
, 0, u
, sbi
)
1257 ddg_node_ptr u_node
= &g
->nodes
[u
];
1259 change
|= update_dist_to_successors (u_node
, nodes
, tmp
);
1262 result
= g
->nodes
[dest
].aux
.count
;
1263 sbitmap_free (workset
);
1268 #endif /* INSN_SCHEDULING */