1 /* DDG - Data Dependence Graph implementation.
2 Copyright (C) 2004-2021 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 /* We currently choose not to create certain anti-deps edges and
189 compensate for that by generating reg-moves based on the life-range
190 analysis. The anti-deps that will be deleted are the ones which
191 have true-deps edges in the opposite direction (in other words
192 the kernel has only one def of the relevant register).
193 If the address that is being auto-inc or auto-dec in DEST_NODE
194 is used in SRC_NODE then do not remove the edge to make sure
195 reg-moves will not be created for this address.
196 TODO: support the removal of all anti-deps edges, i.e. including those
197 whose register has multiple defs in the loop. */
198 if (flag_modulo_sched_allow_regmoves
199 && (t
== ANTI_DEP
&& dt
== REG_DEP
)
200 && !def_has_ccmode_p (dest_node
->insn
)
201 && !autoinc_var_is_used_p (dest_node
->insn
, src_node
->insn
))
205 set
= single_set (dest_node
->insn
);
206 /* TODO: Handle registers that REG_P is not true for them, i.e.
207 subregs and special registers. */
208 if (set
&& REG_P (SET_DEST (set
)))
210 int regno
= REGNO (SET_DEST (set
));
212 class df_rd_bb_info
*bb_info
= DF_RD_BB_INFO (g
->bb
);
214 first_def
= df_bb_regno_first_def_find (g
->bb
, regno
);
215 gcc_assert (first_def
);
217 if (bitmap_bit_p (&bb_info
->gen
, DF_REF_ID (first_def
)))
222 latency
= dep_cost (link
);
223 e
= create_ddg_edge (src_node
, dest_node
, t
, dt
, latency
, distance
);
224 add_edge_to_ddg (g
, e
);
227 /* The same as the above function, but it doesn't require a link parameter. */
229 create_ddg_dep_no_link (ddg_ptr g
, ddg_node_ptr from
, ddg_node_ptr to
,
230 dep_type d_t
, dep_data_type d_dt
, int distance
)
234 enum reg_note dep_kind
;
235 struct _dep _dep
, *dep
= &_dep
;
238 dep_kind
= REG_DEP_ANTI
;
239 else if (d_t
== OUTPUT_DEP
)
240 dep_kind
= REG_DEP_OUTPUT
;
243 gcc_assert (d_t
== TRUE_DEP
);
245 dep_kind
= REG_DEP_TRUE
;
248 init_dep (dep
, from
->insn
, to
->insn
, dep_kind
);
252 e
= create_ddg_edge (from
, to
, d_t
, d_dt
, l
, distance
);
254 add_backarc_to_ddg (g
, e
);
256 add_edge_to_ddg (g
, e
);
260 /* Given a downwards exposed register def LAST_DEF (which is the last
261 definition of that register in the bb), add inter-loop true dependences
262 to all its uses in the next iteration, an output dependence to the
263 first def of the same register (possibly itself) in the next iteration
264 and anti-dependences from its uses in the current iteration to the
265 first definition in the next iteration. */
267 add_cross_iteration_register_deps (ddg_ptr g
, df_ref last_def
)
269 struct df_link
*r_use
;
270 int has_use_in_bb_p
= false;
271 int regno
= DF_REF_REGNO (last_def
);
272 ddg_node_ptr last_def_node
= get_node_of_insn (g
, DF_REF_INSN (last_def
));
273 df_ref first_def
= df_bb_regno_first_def_find (g
->bb
, regno
);
274 ddg_node_ptr first_def_node
= get_node_of_insn (g
, DF_REF_INSN (first_def
));
275 ddg_node_ptr use_node
;
277 gcc_assert (last_def_node
&& first_def
&& first_def_node
);
279 if (flag_checking
&& DF_REF_ID (last_def
) != DF_REF_ID (first_def
))
281 class df_rd_bb_info
*bb_info
= DF_RD_BB_INFO (g
->bb
);
282 gcc_assert (!bitmap_bit_p (&bb_info
->gen
, DF_REF_ID (first_def
)));
285 /* Create inter-loop true dependences and anti dependences. */
286 for (r_use
= DF_REF_CHAIN (last_def
); r_use
!= NULL
; r_use
= r_use
->next
)
288 if (DF_REF_BB (r_use
->ref
) != g
->bb
)
291 gcc_assert (!DF_REF_IS_ARTIFICIAL (r_use
->ref
)
292 && DF_REF_INSN_INFO (r_use
->ref
) != NULL
);
294 rtx_insn
*use_insn
= DF_REF_INSN (r_use
->ref
);
296 if (DEBUG_INSN_P (use_insn
))
299 /* ??? Do not handle uses with DF_REF_IN_NOTE notes. */
300 use_node
= get_node_of_insn (g
, use_insn
);
301 gcc_assert (use_node
);
302 has_use_in_bb_p
= true;
303 if (use_node
->cuid
<= last_def_node
->cuid
)
305 /* Add true deps from last_def to it's uses in the next
306 iteration. Any such upwards exposed use appears before
308 create_ddg_dep_no_link (g
, last_def_node
, use_node
,
309 TRUE_DEP
, REG_DEP
, 1);
313 /* Add anti deps from last_def's uses in the current iteration
314 to the first def in the next iteration. We do not add ANTI
315 dep when there is an intra-loop TRUE dep in the opposite
316 direction, but use regmoves to fix such disregarded ANTI
317 deps when broken. If the first_def reaches the USE then
319 Always create the edge if the use node is a branch in
320 order to prevent the creation of reg-moves.
321 If the address that is being auto-inc or auto-dec in LAST_DEF
322 is used in USE_INSN then do not remove the edge to make sure
323 reg-moves will not be created for that address. */
324 if (DF_REF_ID (last_def
) != DF_REF_ID (first_def
)
325 || !flag_modulo_sched_allow_regmoves
326 || JUMP_P (use_node
->insn
)
327 || autoinc_var_is_used_p (DF_REF_INSN (last_def
), use_insn
)
328 || def_has_ccmode_p (DF_REF_INSN (last_def
)))
329 create_ddg_dep_no_link (g
, use_node
, first_def_node
, ANTI_DEP
,
333 /* Create an inter-loop output dependence between LAST_DEF (which is the
334 last def in its block, being downwards exposed) and the first def in
335 its block. Avoid creating a self output dependence. Avoid creating
336 an output dependence if there is a dependence path between the two
337 defs starting with a true dependence to a use which can be in the
338 next iteration; followed by an anti dependence of that use to the
339 first def (i.e. if there is a use between the two defs.) */
340 if (!has_use_in_bb_p
&& DF_REF_ID (last_def
) != DF_REF_ID (first_def
))
341 create_ddg_dep_no_link (g
, last_def_node
, first_def_node
,
342 OUTPUT_DEP
, REG_DEP
, 1);
345 /* Build inter-loop dependencies, by looking at DF analysis backwards. */
347 build_inter_loop_deps (ddg_ptr g
)
350 class df_rd_bb_info
*rd_bb_info
;
353 rd_bb_info
= DF_RD_BB_INFO (g
->bb
);
355 /* Find inter-loop register output, true and anti deps. */
356 EXECUTE_IF_SET_IN_BITMAP (&rd_bb_info
->gen
, 0, rd_num
, bi
)
358 df_ref rd
= DF_DEFS_GET (rd_num
);
360 add_cross_iteration_register_deps (g
, rd
);
365 /* Return true if two specified instructions have mem expr with conflict
368 insns_may_alias_p (rtx_insn
*insn1
, rtx_insn
*insn2
)
370 subrtx_iterator::array_type array1
;
371 subrtx_iterator::array_type array2
;
372 FOR_EACH_SUBRTX (iter1
, array1
, PATTERN (insn1
), NONCONST
)
374 const_rtx x1
= *iter1
;
376 FOR_EACH_SUBRTX (iter2
, array2
, PATTERN (insn2
), NONCONST
)
378 const_rtx x2
= *iter2
;
379 if (MEM_P (x2
) && may_alias_p (x2
, x1
))
386 /* Given two nodes, analyze their RTL insns and add intra-loop mem deps
389 add_intra_loop_mem_dep (ddg_ptr g
, ddg_node_ptr from
, ddg_node_ptr to
)
392 if ((from
->cuid
== to
->cuid
)
393 || !insns_may_alias_p (from
->insn
, to
->insn
))
394 /* Do not create edge if memory references have disjoint alias sets
395 or 'to' and 'from' are the same instruction. */
398 if (mem_write_insn_p (from
->insn
))
400 if (mem_read_insn_p (to
->insn
))
401 create_ddg_dep_no_link (g
, from
, to
, TRUE_DEP
, MEM_DEP
, 0);
403 create_ddg_dep_no_link (g
, from
, to
, OUTPUT_DEP
, MEM_DEP
, 0);
405 else if (!mem_read_insn_p (to
->insn
))
406 create_ddg_dep_no_link (g
, from
, to
, ANTI_DEP
, MEM_DEP
, 0);
409 /* Given two nodes, analyze their RTL insns and add inter-loop mem deps
412 add_inter_loop_mem_dep (ddg_ptr g
, ddg_node_ptr from
, ddg_node_ptr to
)
414 if (!insns_may_alias_p (from
->insn
, to
->insn
))
415 /* Do not create edge if memory references have disjoint alias sets. */
418 if (mem_write_insn_p (from
->insn
))
420 if (mem_read_insn_p (to
->insn
))
421 create_ddg_dep_no_link (g
, from
, to
, TRUE_DEP
, MEM_DEP
, 1);
422 else if (from
->cuid
!= to
->cuid
)
423 create_ddg_dep_no_link (g
, from
, to
, OUTPUT_DEP
, MEM_DEP
, 1);
427 if (mem_read_insn_p (to
->insn
))
429 else if (from
->cuid
!= to
->cuid
)
431 create_ddg_dep_no_link (g
, from
, to
, ANTI_DEP
, MEM_DEP
, 1);
432 create_ddg_dep_no_link (g
, to
, from
, TRUE_DEP
, MEM_DEP
, 1);
437 /* Perform intra-block Data Dependency analysis and connect the nodes in
438 the DDG. We assume the loop has a single basic block. */
440 build_intra_loop_deps (ddg_ptr g
)
443 /* Hold the dependency analysis state during dependency calculations. */
444 class deps_desc tmp_deps
;
445 rtx_insn
*head
, *tail
;
447 /* Build the dependence information, using the sched_analyze function. */
449 init_deps (&tmp_deps
, false);
451 /* Do the intra-block data dependence analysis for the given block. */
452 get_ebb_head_tail (g
->bb
, g
->bb
, &head
, &tail
);
453 sched_analyze (&tmp_deps
, head
, tail
);
455 /* Build intra-loop data dependencies using the scheduler dependency
457 for (i
= 0; i
< g
->num_nodes
; i
++)
459 ddg_node_ptr dest_node
= &g
->nodes
[i
];
460 sd_iterator_def sd_it
;
463 FOR_EACH_DEP (dest_node
->insn
, SD_LIST_BACK
, sd_it
, dep
)
465 rtx_insn
*src_insn
= DEP_PRO (dep
);
466 ddg_node_ptr src_node
= get_node_of_insn (g
, src_insn
);
471 create_ddg_dep_from_intra_loop_link (g
, src_node
, dest_node
, dep
);
474 /* If this insn modifies memory, add an edge to all insns that access
476 if (mem_access_insn_p (dest_node
->insn
))
480 for (j
= 0; j
<= i
; j
++)
482 ddg_node_ptr j_node
= &g
->nodes
[j
];
484 if (mem_access_insn_p (j_node
->insn
))
486 /* Don't bother calculating inter-loop dep if an intra-loop dep
488 if (! bitmap_bit_p (dest_node
->successors
, j
))
489 add_inter_loop_mem_dep (g
, dest_node
, j_node
);
490 /* If -fmodulo-sched-allow-regmoves
491 is set certain anti-dep edges are not created.
492 It might be that these anti-dep edges are on the
493 path from one memory instruction to another such that
494 removing these edges could cause a violation of the
495 memory dependencies. Thus we add intra edges between
496 every two memory instructions in this case. */
497 if (flag_modulo_sched_allow_regmoves
498 && !bitmap_bit_p (dest_node
->predecessors
, j
))
499 add_intra_loop_mem_dep (g
, j_node
, dest_node
);
505 /* Free the INSN_LISTs. */
506 finish_deps_global ();
507 free_deps (&tmp_deps
);
509 /* Free dependencies. */
510 sched_free_deps (head
, tail
, false);
514 /* Given a basic block, create its DDG and return a pointer to a variable
515 of ddg type that represents it.
516 Initialize the ddg structure fields to the appropriate values. */
518 create_ddg (basic_block bb
, int closing_branch_deps
)
521 rtx_insn
*insn
, *first_note
;
525 g
= (ddg_ptr
) xcalloc (1, sizeof (struct ddg
));
528 g
->closing_branch_deps
= closing_branch_deps
;
530 /* Count the number of insns in the BB. */
531 for (insn
= BB_HEAD (bb
); insn
!= NEXT_INSN (BB_END (bb
));
532 insn
= NEXT_INSN (insn
))
534 if (!INSN_P (insn
) || GET_CODE (PATTERN (insn
)) == USE
)
537 if (NONDEBUG_INSN_P (insn
))
539 if (mem_read_insn_p (insn
))
541 if (mem_write_insn_p (insn
))
547 /* There is nothing to do for this BB. */
554 /* Allocate the nodes array, and initialize the nodes. */
555 g
->num_nodes
= num_nodes
;
556 g
->nodes
= (ddg_node_ptr
) xcalloc (num_nodes
, sizeof (struct ddg_node
));
557 g
->closing_branch
= NULL
;
560 for (insn
= BB_HEAD (bb
); insn
!= NEXT_INSN (BB_END (bb
));
561 insn
= NEXT_INSN (insn
))
563 if (LABEL_P (insn
) || NOTE_INSN_BASIC_BLOCK_P (insn
))
566 if (!first_note
&& (INSN_P (insn
) || NOTE_P (insn
)))
569 if (!INSN_P (insn
) || GET_CODE (PATTERN (insn
)) == USE
)
574 gcc_assert (!g
->closing_branch
);
575 g
->closing_branch
= &g
->nodes
[i
];
578 if (NONDEBUG_INSN_P (insn
))
580 g
->nodes
[i
].cuid
= i
;
581 g
->nodes
[i
].successors
= sbitmap_alloc (num_nodes
);
582 bitmap_clear (g
->nodes
[i
].successors
);
583 g
->nodes
[i
].predecessors
= sbitmap_alloc (num_nodes
);
584 bitmap_clear (g
->nodes
[i
].predecessors
);
586 gcc_checking_assert (first_note
);
587 g
->nodes
[i
].first_note
= first_note
;
589 g
->nodes
[i
].aux
.count
= -1;
590 g
->nodes
[i
].max_dist
= XCNEWVEC (int, num_nodes
);
591 for (j
= 0; j
< num_nodes
; j
++)
592 g
->nodes
[i
].max_dist
[j
] = -1;
594 g
->nodes
[i
++].insn
= insn
;
599 /* We must have found a branch in DDG. */
600 gcc_assert (g
->closing_branch
);
603 /* Build the data dependency graph. */
604 build_intra_loop_deps (g
);
605 build_inter_loop_deps (g
);
609 /* Free all the memory allocated for the DDG. */
618 for (i
= 0; i
< g
->num_nodes
; i
++)
620 ddg_edge_ptr e
= g
->nodes
[i
].out
;
624 ddg_edge_ptr next
= e
->next_out
;
629 sbitmap_free (g
->nodes
[i
].successors
);
630 sbitmap_free (g
->nodes
[i
].predecessors
);
631 free (g
->nodes
[i
].max_dist
);
633 if (g
->num_backarcs
> 0)
640 print_ddg_edge (FILE *file
, ddg_edge_ptr e
)
656 fprintf (file
, " [%d -(%c,%d,%d)-> %d] ", INSN_UID (e
->src
->insn
),
657 dep_c
, e
->latency
, e
->distance
, INSN_UID (e
->dest
->insn
));
660 /* Print the DDG nodes with there in/out edges to the dump file. */
662 print_ddg (FILE *file
, ddg_ptr g
)
666 for (i
= 0; i
< g
->num_nodes
; i
++)
670 fprintf (file
, "Node num: %d\n", g
->nodes
[i
].cuid
);
671 print_rtl_single (file
, g
->nodes
[i
].insn
);
672 fprintf (file
, "OUT ARCS: ");
673 for (e
= g
->nodes
[i
].out
; e
; e
= e
->next_out
)
674 print_ddg_edge (file
, e
);
676 fprintf (file
, "\nIN ARCS: ");
677 for (e
= g
->nodes
[i
].in
; e
; e
= e
->next_in
)
678 print_ddg_edge (file
, e
);
680 fprintf (file
, "\n");
684 /* Print the given DDG in VCG format. */
686 vcg_print_ddg (FILE *file
, ddg_ptr g
)
690 fprintf (file
, "graph: {\n");
691 for (src_cuid
= 0; src_cuid
< g
->num_nodes
; src_cuid
++)
694 int src_uid
= INSN_UID (g
->nodes
[src_cuid
].insn
);
696 fprintf (file
, "node: {title: \"%d_%d\" info1: \"", src_cuid
, src_uid
);
697 print_rtl_single (file
, g
->nodes
[src_cuid
].insn
);
698 fprintf (file
, "\"}\n");
699 for (e
= g
->nodes
[src_cuid
].out
; e
; e
= e
->next_out
)
701 int dst_uid
= INSN_UID (e
->dest
->insn
);
702 int dst_cuid
= e
->dest
->cuid
;
704 /* Give the backarcs a different color. */
706 fprintf (file
, "backedge: {color: red ");
708 fprintf (file
, "edge: { ");
710 fprintf (file
, "sourcename: \"%d_%d\" ", src_cuid
, src_uid
);
711 fprintf (file
, "targetname: \"%d_%d\" ", dst_cuid
, dst_uid
);
712 fprintf (file
, "label: \"%d_%d\"}\n", e
->latency
, e
->distance
);
715 fprintf (file
, "}\n");
718 /* Dump the sccs in SCCS. */
720 print_sccs (FILE *file
, ddg_all_sccs_ptr sccs
, ddg_ptr g
)
723 sbitmap_iterator sbi
;
729 fprintf (file
, "\n;; Number of SCC nodes - %d\n", sccs
->num_sccs
);
730 for (i
= 0; i
< sccs
->num_sccs
; i
++)
732 fprintf (file
, "SCC number: %d\n", i
);
733 EXECUTE_IF_SET_IN_BITMAP (sccs
->sccs
[i
]->nodes
, 0, u
, sbi
)
735 fprintf (file
, "insn num %d\n", u
);
736 print_rtl_single (file
, g
->nodes
[u
].insn
);
739 fprintf (file
, "\n");
742 /* Create an edge and initialize it with given values. */
744 create_ddg_edge (ddg_node_ptr src
, ddg_node_ptr dest
,
745 dep_type t
, dep_data_type dt
, int l
, int d
)
747 ddg_edge_ptr e
= (ddg_edge_ptr
) xmalloc (sizeof (struct ddg_edge
));
755 e
->next_in
= e
->next_out
= NULL
;
760 /* Add the given edge to the in/out linked lists of the DDG nodes. */
762 add_edge_to_ddg (ddg_ptr g ATTRIBUTE_UNUSED
, ddg_edge_ptr e
)
764 ddg_node_ptr src
= e
->src
;
765 ddg_node_ptr dest
= e
->dest
;
767 /* Should have allocated the sbitmaps. */
768 gcc_assert (src
->successors
&& dest
->predecessors
);
770 bitmap_set_bit (src
->successors
, dest
->cuid
);
771 bitmap_set_bit (dest
->predecessors
, src
->cuid
);
772 e
->next_in
= dest
->in
;
774 e
->next_out
= src
->out
;
780 /* Algorithm for computing the recurrence_length of an scc. We assume at
781 for now that cycles in the data dependence graph contain a single backarc.
782 This simplifies the algorithm, and can be generalized later. */
784 set_recurrence_length (ddg_scc_ptr scc
)
789 for (j
= 0; j
< scc
->num_backarcs
; j
++)
791 ddg_edge_ptr backarc
= scc
->backarcs
[j
];
792 int distance
= backarc
->distance
;
793 ddg_node_ptr src
= backarc
->dest
;
794 ddg_node_ptr dest
= backarc
->src
;
795 int length
= src
->max_dist
[dest
->cuid
];
800 length
+= backarc
->latency
;
801 result
= MAX (result
, (length
/ distance
));
803 scc
->recurrence_length
= result
;
806 /* Create a new SCC given the set of its nodes. Compute its recurrence_length
807 and mark edges that belong to this scc. */
809 create_scc (ddg_ptr g
, sbitmap nodes
, int id
)
813 sbitmap_iterator sbi
;
815 scc
= (ddg_scc_ptr
) xmalloc (sizeof (struct ddg_scc
));
816 scc
->backarcs
= NULL
;
817 scc
->num_backarcs
= 0;
818 scc
->nodes
= sbitmap_alloc (g
->num_nodes
);
819 bitmap_copy (scc
->nodes
, nodes
);
821 /* Mark the backarcs that belong to this SCC. */
822 EXECUTE_IF_SET_IN_BITMAP (nodes
, 0, u
, sbi
)
825 ddg_node_ptr n
= &g
->nodes
[u
];
827 gcc_assert (n
->aux
.count
== -1);
830 for (e
= n
->out
; e
; e
= e
->next_out
)
831 if (bitmap_bit_p (nodes
, e
->dest
->cuid
))
835 add_backarc_to_scc (scc
, e
);
842 /* Cleans the memory allocation of a given SCC. */
844 free_scc (ddg_scc_ptr scc
)
849 sbitmap_free (scc
->nodes
);
850 if (scc
->num_backarcs
> 0)
851 free (scc
->backarcs
);
856 /* Add a given edge known to be a backarc to the given DDG. */
858 add_backarc_to_ddg (ddg_ptr g
, ddg_edge_ptr e
)
860 int size
= (g
->num_backarcs
+ 1) * sizeof (ddg_edge_ptr
);
862 add_edge_to_ddg (g
, e
);
863 g
->backarcs
= (ddg_edge_ptr
*) xrealloc (g
->backarcs
, size
);
864 g
->backarcs
[g
->num_backarcs
++] = e
;
867 /* Add backarc to an SCC. */
869 add_backarc_to_scc (ddg_scc_ptr scc
, ddg_edge_ptr e
)
871 int size
= (scc
->num_backarcs
+ 1) * sizeof (ddg_edge_ptr
);
873 scc
->backarcs
= (ddg_edge_ptr
*) xrealloc (scc
->backarcs
, size
);
874 scc
->backarcs
[scc
->num_backarcs
++] = e
;
877 /* Add the given SCC to the DDG. */
879 add_scc_to_ddg (ddg_all_sccs_ptr g
, ddg_scc_ptr scc
)
881 int size
= (g
->num_sccs
+ 1) * sizeof (ddg_scc_ptr
);
883 g
->sccs
= (ddg_scc_ptr
*) xrealloc (g
->sccs
, size
);
884 g
->sccs
[g
->num_sccs
++] = scc
;
887 /* Given the instruction INSN return the node that represents it. */
889 get_node_of_insn (ddg_ptr g
, rtx_insn
*insn
)
893 for (i
= 0; i
< g
->num_nodes
; i
++)
894 if (insn
== g
->nodes
[i
].insn
)
899 /* Given a set OPS of nodes in the DDG, find the set of their successors
900 which are not in OPS, and set their bits in SUCC. Bits corresponding to
901 OPS are cleared from SUCC. Leaves the other bits in SUCC unchanged. */
903 find_successors (sbitmap succ
, ddg_ptr g
, sbitmap ops
)
906 sbitmap_iterator sbi
;
908 EXECUTE_IF_SET_IN_BITMAP (ops
, 0, i
, sbi
)
910 const sbitmap node_succ
= NODE_SUCCESSORS (&g
->nodes
[i
]);
911 bitmap_ior (succ
, succ
, node_succ
);
914 /* We want those that are not in ops. */
915 bitmap_and_compl (succ
, succ
, ops
);
918 /* Given a set OPS of nodes in the DDG, find the set of their predecessors
919 which are not in OPS, and set their bits in PREDS. Bits corresponding to
920 OPS are cleared from PREDS. Leaves the other bits in PREDS unchanged. */
922 find_predecessors (sbitmap preds
, ddg_ptr g
, sbitmap ops
)
925 sbitmap_iterator sbi
;
927 EXECUTE_IF_SET_IN_BITMAP (ops
, 0, i
, sbi
)
929 const sbitmap node_preds
= NODE_PREDECESSORS (&g
->nodes
[i
]);
930 bitmap_ior (preds
, preds
, node_preds
);
933 /* We want those that are not in ops. */
934 bitmap_and_compl (preds
, preds
, ops
);
938 /* Compare function to be passed to qsort to order the backarcs in descending
941 compare_sccs (const void *s1
, const void *s2
)
943 const int rec_l1
= (*(const ddg_scc_ptr
*)s1
)->recurrence_length
;
944 const int rec_l2
= (*(const ddg_scc_ptr
*)s2
)->recurrence_length
;
945 return ((rec_l2
> rec_l1
) - (rec_l2
< rec_l1
));
949 /* Order the backarcs in descending recMII order using compare_sccs. */
951 order_sccs (ddg_all_sccs_ptr g
)
953 qsort (g
->sccs
, g
->num_sccs
, sizeof (ddg_scc_ptr
),
954 (int (*) (const void *, const void *)) compare_sccs
);
957 /* Check that every node in SCCS belongs to exactly one strongly connected
958 component and that no element of SCCS is empty. */
960 check_sccs (ddg_all_sccs_ptr sccs
, int num_nodes
)
963 auto_sbitmap
tmp (num_nodes
);
966 for (i
= 0; i
< sccs
->num_sccs
; i
++)
968 gcc_assert (!bitmap_empty_p (sccs
->sccs
[i
]->nodes
));
969 /* Verify that every node in sccs is in exactly one strongly
970 connected component. */
971 gcc_assert (!bitmap_intersect_p (tmp
, sccs
->sccs
[i
]->nodes
));
972 bitmap_ior (tmp
, tmp
, sccs
->sccs
[i
]->nodes
);
976 /* Perform the Strongly Connected Components decomposing algorithm on the
977 DDG and return DDG_ALL_SCCS structure that contains them. */
979 create_ddg_all_sccs (ddg_ptr g
)
981 int i
, j
, k
, scc
, way
;
982 int num_nodes
= g
->num_nodes
;
983 auto_sbitmap
from (num_nodes
);
984 auto_sbitmap
to (num_nodes
);
985 auto_sbitmap
scc_nodes (num_nodes
);
986 ddg_all_sccs_ptr sccs
= (ddg_all_sccs_ptr
)
987 xmalloc (sizeof (struct ddg_all_sccs
));
993 for (i
= 0; i
< g
->num_backarcs
; i
++)
996 ddg_edge_ptr backarc
= g
->backarcs
[i
];
997 ddg_node_ptr src
= backarc
->src
;
998 ddg_node_ptr dest
= backarc
->dest
;
1000 /* If the backarc already belongs to an SCC, continue. */
1001 if (backarc
->in_scc
)
1004 bitmap_clear (scc_nodes
);
1005 bitmap_clear (from
);
1007 bitmap_set_bit (from
, dest
->cuid
);
1008 bitmap_set_bit (to
, src
->cuid
);
1010 if (find_nodes_on_paths (scc_nodes
, g
, from
, to
))
1012 scc
= create_scc (g
, scc_nodes
, sccs
->num_sccs
);
1013 add_scc_to_ddg (sccs
, scc
);
1017 /* Init max_dist arrays for Floyd–Warshall-like
1018 longest patch calculation algorithm. */
1019 for (k
= 0; k
< num_nodes
; k
++)
1022 ddg_node_ptr n
= &g
->nodes
[k
];
1024 if (n
->aux
.count
== -1)
1028 for (e
= n
->out
; e
; e
= e
->next_out
)
1029 if (e
->distance
== 0 && g
->nodes
[e
->dest
->cuid
].aux
.count
== n
->aux
.count
)
1030 n
->max_dist
[e
->dest
->cuid
] = e
->latency
;
1033 /* Run main Floid-Warshall loop. We use only non-backarc edges
1035 for (k
= 0; k
< num_nodes
; k
++)
1037 scc
= g
->nodes
[k
].aux
.count
;
1040 for (i
= 0; i
< num_nodes
; i
++)
1041 if (g
->nodes
[i
].aux
.count
== scc
)
1042 for (j
= 0; j
< num_nodes
; j
++)
1043 if (g
->nodes
[j
].aux
.count
== scc
1044 && g
->nodes
[i
].max_dist
[k
] >= 0
1045 && g
->nodes
[k
].max_dist
[j
] >= 0)
1047 way
= g
->nodes
[i
].max_dist
[k
] + g
->nodes
[k
].max_dist
[j
];
1048 if (g
->nodes
[i
].max_dist
[j
] < way
)
1049 g
->nodes
[i
].max_dist
[j
] = way
;
1054 /* Calculate recurrence_length using max_dist info. */
1055 for (i
= 0; i
< sccs
->num_sccs
; i
++)
1056 set_recurrence_length (sccs
->sccs
[i
]);
1061 check_sccs (sccs
, num_nodes
);
1066 /* Frees the memory allocated for all SCCs of the DDG, but keeps the DDG. */
1068 free_ddg_all_sccs (ddg_all_sccs_ptr all_sccs
)
1075 for (i
= 0; i
< all_sccs
->num_sccs
; i
++)
1076 free_scc (all_sccs
->sccs
[i
]);
1078 free (all_sccs
->sccs
);
1083 /* Given FROM - a bitmap of source nodes - and TO - a bitmap of destination
1084 nodes - find all nodes that lie on paths from FROM to TO (not excluding
1085 nodes from FROM and TO). Return nonzero if nodes exist. */
1087 find_nodes_on_paths (sbitmap result
, ddg_ptr g
, sbitmap from
, sbitmap to
)
1091 int num_nodes
= g
->num_nodes
;
1092 sbitmap_iterator sbi
;
1094 auto_sbitmap
workset (num_nodes
);
1095 auto_sbitmap
reachable_from (num_nodes
);
1096 auto_sbitmap
reach_to (num_nodes
);
1097 auto_sbitmap
tmp (num_nodes
);
1099 bitmap_copy (reachable_from
, from
);
1100 bitmap_copy (tmp
, from
);
1106 bitmap_copy (workset
, tmp
);
1108 EXECUTE_IF_SET_IN_BITMAP (workset
, 0, u
, sbi
)
1111 ddg_node_ptr u_node
= &g
->nodes
[u
];
1113 for (e
= u_node
->out
; e
!= (ddg_edge_ptr
) 0; e
= e
->next_out
)
1115 ddg_node_ptr v_node
= e
->dest
;
1116 int v
= v_node
->cuid
;
1118 if (!bitmap_bit_p (reachable_from
, v
))
1120 bitmap_set_bit (reachable_from
, v
);
1121 bitmap_set_bit (tmp
, v
);
1128 bitmap_copy (reach_to
, to
);
1129 bitmap_copy (tmp
, to
);
1135 bitmap_copy (workset
, tmp
);
1137 EXECUTE_IF_SET_IN_BITMAP (workset
, 0, u
, sbi
)
1140 ddg_node_ptr u_node
= &g
->nodes
[u
];
1142 for (e
= u_node
->in
; e
!= (ddg_edge_ptr
) 0; e
= e
->next_in
)
1144 ddg_node_ptr v_node
= e
->src
;
1145 int v
= v_node
->cuid
;
1147 if (!bitmap_bit_p (reach_to
, v
))
1149 bitmap_set_bit (reach_to
, v
);
1150 bitmap_set_bit (tmp
, v
);
1157 return bitmap_and (result
, reachable_from
, reach_to
);
1160 #endif /* INSN_SCHEDULING */