PR other/54324
[official-gcc.git] / gcc / ddg.c
blob28402e67c5ca74db048332a2c70236934bf9e292
1 /* DDG - Data Dependence Graph implementation.
2 Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010
3 Free Software Foundation, Inc.
4 Contributed by Ayal Zaks and Mustafa Hagog <zaks,mustafa@il.ibm.com>
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
11 version.
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 for more details.
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
23 #include "config.h"
24 #include "system.h"
25 #include "coretypes.h"
26 #include "tm.h"
27 #include "diagnostic-core.h"
28 #include "rtl.h"
29 #include "tm_p.h"
30 #include "hard-reg-set.h"
31 #include "regs.h"
32 #include "function.h"
33 #include "flags.h"
34 #include "insn-config.h"
35 #include "insn-attr.h"
36 #include "except.h"
37 #include "recog.h"
38 #include "sched-int.h"
39 #include "target.h"
40 #include "cfgloop.h"
41 #include "sbitmap.h"
42 #include "expr.h"
43 #include "bitmap.h"
44 #include "ddg.h"
46 #ifdef INSN_SCHEDULING
48 /* A flag indicating that a ddg edge belongs to an SCC or not. */
49 enum edge_flag {NOT_IN_SCC = 0, IN_SCC};
51 /* Forward declarations. */
52 static void add_backarc_to_ddg (ddg_ptr, ddg_edge_ptr);
53 static void add_backarc_to_scc (ddg_scc_ptr, ddg_edge_ptr);
54 static void add_scc_to_ddg (ddg_all_sccs_ptr, ddg_scc_ptr);
55 static void create_ddg_dep_from_intra_loop_link (ddg_ptr, ddg_node_ptr,
56 ddg_node_ptr, dep_t);
57 static void create_ddg_dep_no_link (ddg_ptr, ddg_node_ptr, ddg_node_ptr,
58 dep_type, dep_data_type, int);
59 static ddg_edge_ptr create_ddg_edge (ddg_node_ptr, ddg_node_ptr, dep_type,
60 dep_data_type, int, int);
61 static void add_edge_to_ddg (ddg_ptr g, ddg_edge_ptr);
63 /* Auxiliary variable for mem_read_insn_p/mem_write_insn_p. */
64 static bool mem_ref_p;
66 /* Auxiliary function for mem_read_insn_p. */
67 static int
68 mark_mem_use (rtx *x, void *data ATTRIBUTE_UNUSED)
70 if (MEM_P (*x))
71 mem_ref_p = true;
72 return 0;
75 /* Auxiliary function for mem_read_insn_p. */
76 static void
77 mark_mem_use_1 (rtx *x, void *data)
79 for_each_rtx (x, mark_mem_use, data);
82 /* Returns nonzero if INSN reads from memory. */
83 static bool
84 mem_read_insn_p (rtx insn)
86 mem_ref_p = false;
87 note_uses (&PATTERN (insn), mark_mem_use_1, NULL);
88 return mem_ref_p;
91 static void
92 mark_mem_store (rtx loc, const_rtx setter ATTRIBUTE_UNUSED, void *data ATTRIBUTE_UNUSED)
94 if (MEM_P (loc))
95 mem_ref_p = true;
98 /* Returns nonzero if INSN writes to memory. */
99 static bool
100 mem_write_insn_p (rtx insn)
102 mem_ref_p = false;
103 note_stores (PATTERN (insn), mark_mem_store, NULL);
104 return mem_ref_p;
107 /* Returns nonzero if X has access to memory. */
108 static bool
109 rtx_mem_access_p (rtx x)
111 int i, j;
112 const char *fmt;
113 enum rtx_code code;
115 if (x == 0)
116 return false;
118 if (MEM_P (x))
119 return true;
121 code = GET_CODE (x);
122 fmt = GET_RTX_FORMAT (code);
123 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
125 if (fmt[i] == 'e')
127 if (rtx_mem_access_p (XEXP (x, i)))
128 return true;
130 else if (fmt[i] == 'E')
131 for (j = 0; j < XVECLEN (x, i); j++)
133 if (rtx_mem_access_p (XVECEXP (x, i, j)))
134 return true;
137 return false;
140 /* Returns nonzero if INSN reads to or writes from memory. */
141 static bool
142 mem_access_insn_p (rtx insn)
144 return rtx_mem_access_p (PATTERN (insn));
147 /* Return true if DEF_INSN contains address being auto-inc or auto-dec
148 which is used in USE_INSN. Otherwise return false. The result is
149 being used to decide whether to remove the edge between def_insn and
150 use_insn when -fmodulo-sched-allow-regmoves is set. This function
151 doesn't need to consider the specific address register; no reg_moves
152 will be allowed for any life range defined by def_insn and used
153 by use_insn, if use_insn uses an address register auto-inc'ed by
154 def_insn. */
155 bool
156 autoinc_var_is_used_p (rtx def_insn, rtx use_insn)
158 rtx note;
160 for (note = REG_NOTES (def_insn); note; note = XEXP (note, 1))
161 if (REG_NOTE_KIND (note) == REG_INC
162 && reg_referenced_p (XEXP (note, 0), PATTERN (use_insn)))
163 return true;
165 return false;
168 /* Return true if one of the definitions in INSN has MODE_CC. Otherwise
169 return false. */
170 static bool
171 def_has_ccmode_p (rtx insn)
173 df_ref *def;
175 for (def = DF_INSN_DEFS (insn); *def; def++)
177 enum machine_mode mode = GET_MODE (DF_REF_REG (*def));
179 if (GET_MODE_CLASS (mode) == MODE_CC)
180 return true;
183 return false;
186 /* Computes the dependence parameters (latency, distance etc.), creates
187 a ddg_edge and adds it to the given DDG. */
188 static void
189 create_ddg_dep_from_intra_loop_link (ddg_ptr g, ddg_node_ptr src_node,
190 ddg_node_ptr dest_node, dep_t link)
192 ddg_edge_ptr e;
193 int latency, distance = 0;
194 dep_type t = TRUE_DEP;
195 dep_data_type dt = (mem_access_insn_p (src_node->insn)
196 && mem_access_insn_p (dest_node->insn) ? MEM_DEP
197 : REG_DEP);
198 gcc_assert (src_node->cuid < dest_node->cuid);
199 gcc_assert (link);
201 /* Note: REG_DEP_ANTI applies to MEM ANTI_DEP as well!! */
202 if (DEP_TYPE (link) == REG_DEP_ANTI)
203 t = ANTI_DEP;
204 else if (DEP_TYPE (link) == REG_DEP_OUTPUT)
205 t = OUTPUT_DEP;
207 gcc_assert (!DEBUG_INSN_P (dest_node->insn) || t == ANTI_DEP);
208 gcc_assert (!DEBUG_INSN_P (src_node->insn) || t == ANTI_DEP);
210 /* We currently choose not to create certain anti-deps edges and
211 compensate for that by generating reg-moves based on the life-range
212 analysis. The anti-deps that will be deleted are the ones which
213 have true-deps edges in the opposite direction (in other words
214 the kernel has only one def of the relevant register).
215 If the address that is being auto-inc or auto-dec in DEST_NODE
216 is used in SRC_NODE then do not remove the edge to make sure
217 reg-moves will not be created for this address.
218 TODO: support the removal of all anti-deps edges, i.e. including those
219 whose register has multiple defs in the loop. */
220 if (flag_modulo_sched_allow_regmoves
221 && (t == ANTI_DEP && dt == REG_DEP)
222 && !def_has_ccmode_p (dest_node->insn)
223 && !autoinc_var_is_used_p (dest_node->insn, src_node->insn))
225 rtx set;
227 set = single_set (dest_node->insn);
228 /* TODO: Handle registers that REG_P is not true for them, i.e.
229 subregs and special registers. */
230 if (set && REG_P (SET_DEST (set)))
232 int regno = REGNO (SET_DEST (set));
233 df_ref first_def;
234 struct df_rd_bb_info *bb_info = DF_RD_BB_INFO (g->bb);
236 first_def = df_bb_regno_first_def_find (g->bb, regno);
237 gcc_assert (first_def);
239 if (bitmap_bit_p (&bb_info->gen, DF_REF_ID (first_def)))
240 return;
244 latency = dep_cost (link);
245 e = create_ddg_edge (src_node, dest_node, t, dt, latency, distance);
246 add_edge_to_ddg (g, e);
249 /* The same as the above function, but it doesn't require a link parameter. */
250 static void
251 create_ddg_dep_no_link (ddg_ptr g, ddg_node_ptr from, ddg_node_ptr to,
252 dep_type d_t, dep_data_type d_dt, int distance)
254 ddg_edge_ptr e;
255 int l;
256 enum reg_note dep_kind;
257 struct _dep _dep, *dep = &_dep;
259 gcc_assert (!DEBUG_INSN_P (to->insn) || d_t == ANTI_DEP);
260 gcc_assert (!DEBUG_INSN_P (from->insn) || d_t == ANTI_DEP);
262 if (d_t == ANTI_DEP)
263 dep_kind = REG_DEP_ANTI;
264 else if (d_t == OUTPUT_DEP)
265 dep_kind = REG_DEP_OUTPUT;
266 else
268 gcc_assert (d_t == TRUE_DEP);
270 dep_kind = REG_DEP_TRUE;
273 init_dep (dep, from->insn, to->insn, dep_kind);
275 l = dep_cost (dep);
277 e = create_ddg_edge (from, to, d_t, d_dt, l, distance);
278 if (distance > 0)
279 add_backarc_to_ddg (g, e);
280 else
281 add_edge_to_ddg (g, e);
285 /* Given a downwards exposed register def LAST_DEF (which is the last
286 definition of that register in the bb), add inter-loop true dependences
287 to all its uses in the next iteration, an output dependence to the
288 first def of the same register (possibly itself) in the next iteration
289 and anti-dependences from its uses in the current iteration to the
290 first definition in the next iteration. */
291 static void
292 add_cross_iteration_register_deps (ddg_ptr g, df_ref last_def)
294 int regno = DF_REF_REGNO (last_def);
295 struct df_link *r_use;
296 int has_use_in_bb_p = false;
297 rtx def_insn = DF_REF_INSN (last_def);
298 ddg_node_ptr last_def_node = get_node_of_insn (g, def_insn);
299 ddg_node_ptr use_node;
300 #ifdef ENABLE_CHECKING
301 struct df_rd_bb_info *bb_info = DF_RD_BB_INFO (g->bb);
302 #endif
303 df_ref first_def = df_bb_regno_first_def_find (g->bb, regno);
305 gcc_assert (last_def_node);
306 gcc_assert (first_def);
308 #ifdef ENABLE_CHECKING
309 if (DF_REF_ID (last_def) != DF_REF_ID (first_def))
310 gcc_assert (!bitmap_bit_p (&bb_info->gen,
311 DF_REF_ID (first_def)));
312 #endif
314 /* Create inter-loop true dependences and anti dependences. */
315 for (r_use = DF_REF_CHAIN (last_def); r_use != NULL; r_use = r_use->next)
317 rtx use_insn = DF_REF_INSN (r_use->ref);
319 if (BLOCK_FOR_INSN (use_insn) != g->bb)
320 continue;
322 /* ??? Do not handle uses with DF_REF_IN_NOTE notes. */
323 use_node = get_node_of_insn (g, use_insn);
324 gcc_assert (use_node);
325 has_use_in_bb_p = true;
326 if (use_node->cuid <= last_def_node->cuid)
328 /* Add true deps from last_def to it's uses in the next
329 iteration. Any such upwards exposed use appears before
330 the last_def def. */
331 create_ddg_dep_no_link (g, last_def_node, use_node,
332 DEBUG_INSN_P (use_insn) ? ANTI_DEP : TRUE_DEP,
333 REG_DEP, 1);
335 else if (!DEBUG_INSN_P (use_insn))
337 /* Add anti deps from last_def's uses in the current iteration
338 to the first def in the next iteration. We do not add ANTI
339 dep when there is an intra-loop TRUE dep in the opposite
340 direction, but use regmoves to fix such disregarded ANTI
341 deps when broken. If the first_def reaches the USE then
342 there is such a dep. */
343 ddg_node_ptr first_def_node = get_node_of_insn (g,
344 DF_REF_INSN (first_def));
346 gcc_assert (first_def_node);
348 /* Always create the edge if the use node is a branch in
349 order to prevent the creation of reg-moves.
350 If the address that is being auto-inc or auto-dec in LAST_DEF
351 is used in USE_INSN then do not remove the edge to make sure
352 reg-moves will not be created for that address. */
353 if (DF_REF_ID (last_def) != DF_REF_ID (first_def)
354 || !flag_modulo_sched_allow_regmoves
355 || JUMP_P (use_node->insn)
356 || autoinc_var_is_used_p (DF_REF_INSN (last_def), use_insn)
357 || def_has_ccmode_p (DF_REF_INSN (last_def)))
358 create_ddg_dep_no_link (g, use_node, first_def_node, ANTI_DEP,
359 REG_DEP, 1);
363 /* Create an inter-loop output dependence between LAST_DEF (which is the
364 last def in its block, being downwards exposed) and the first def in
365 its block. Avoid creating a self output dependence. Avoid creating
366 an output dependence if there is a dependence path between the two
367 defs starting with a true dependence to a use which can be in the
368 next iteration; followed by an anti dependence of that use to the
369 first def (i.e. if there is a use between the two defs.) */
370 if (!has_use_in_bb_p)
372 ddg_node_ptr dest_node;
374 if (DF_REF_ID (last_def) == DF_REF_ID (first_def))
375 return;
377 dest_node = get_node_of_insn (g, DF_REF_INSN (first_def));
378 gcc_assert (dest_node);
379 create_ddg_dep_no_link (g, last_def_node, dest_node,
380 OUTPUT_DEP, REG_DEP, 1);
383 /* Build inter-loop dependencies, by looking at DF analysis backwards. */
384 static void
385 build_inter_loop_deps (ddg_ptr g)
387 unsigned rd_num;
388 struct df_rd_bb_info *rd_bb_info;
389 bitmap_iterator bi;
391 rd_bb_info = DF_RD_BB_INFO (g->bb);
393 /* Find inter-loop register output, true and anti deps. */
394 EXECUTE_IF_SET_IN_BITMAP (&rd_bb_info->gen, 0, rd_num, bi)
396 df_ref rd = DF_DEFS_GET (rd_num);
398 add_cross_iteration_register_deps (g, rd);
403 static int
404 walk_mems_2 (rtx *x, rtx mem)
406 if (MEM_P (*x))
408 if (may_alias_p (*x, mem))
409 return 1;
411 return -1;
413 return 0;
416 static int
417 walk_mems_1 (rtx *x, rtx *pat)
419 if (MEM_P (*x))
421 /* Visit all MEMs in *PAT and check indepedence. */
422 if (for_each_rtx (pat, (rtx_function) walk_mems_2, *x))
423 /* Indicate that dependence was determined and stop traversal. */
424 return 1;
426 return -1;
428 return 0;
431 /* Return 1 if two specified instructions have mem expr with conflict alias sets*/
432 static int
433 insns_may_alias_p (rtx insn1, rtx insn2)
435 /* For each pair of MEMs in INSN1 and INSN2 check their independence. */
436 return for_each_rtx (&PATTERN (insn1), (rtx_function) walk_mems_1,
437 &PATTERN (insn2));
440 /* Given two nodes, analyze their RTL insns and add intra-loop mem deps
441 to ddg G. */
442 static void
443 add_intra_loop_mem_dep (ddg_ptr g, ddg_node_ptr from, ddg_node_ptr to)
446 if ((from->cuid == to->cuid)
447 || !insns_may_alias_p (from->insn, to->insn))
448 /* Do not create edge if memory references have disjoint alias sets
449 or 'to' and 'from' are the same instruction. */
450 return;
452 if (mem_write_insn_p (from->insn))
454 if (mem_read_insn_p (to->insn))
455 create_ddg_dep_no_link (g, from, to,
456 DEBUG_INSN_P (to->insn)
457 ? ANTI_DEP : TRUE_DEP, MEM_DEP, 0);
458 else
459 create_ddg_dep_no_link (g, from, to,
460 DEBUG_INSN_P (to->insn)
461 ? ANTI_DEP : OUTPUT_DEP, MEM_DEP, 0);
463 else if (!mem_read_insn_p (to->insn))
464 create_ddg_dep_no_link (g, from, to, ANTI_DEP, MEM_DEP, 0);
467 /* Given two nodes, analyze their RTL insns and add inter-loop mem deps
468 to ddg G. */
469 static void
470 add_inter_loop_mem_dep (ddg_ptr g, ddg_node_ptr from, ddg_node_ptr to)
472 if (!insns_may_alias_p (from->insn, to->insn))
473 /* Do not create edge if memory references have disjoint alias sets. */
474 return;
476 if (mem_write_insn_p (from->insn))
478 if (mem_read_insn_p (to->insn))
479 create_ddg_dep_no_link (g, from, to,
480 DEBUG_INSN_P (to->insn)
481 ? ANTI_DEP : TRUE_DEP, MEM_DEP, 1);
482 else if (from->cuid != to->cuid)
483 create_ddg_dep_no_link (g, from, to,
484 DEBUG_INSN_P (to->insn)
485 ? ANTI_DEP : OUTPUT_DEP, MEM_DEP, 1);
487 else
489 if (mem_read_insn_p (to->insn))
490 return;
491 else if (from->cuid != to->cuid)
493 create_ddg_dep_no_link (g, from, to, ANTI_DEP, MEM_DEP, 1);
494 if (DEBUG_INSN_P (from->insn) || DEBUG_INSN_P (to->insn))
495 create_ddg_dep_no_link (g, to, from, ANTI_DEP, MEM_DEP, 1);
496 else
497 create_ddg_dep_no_link (g, to, from, TRUE_DEP, MEM_DEP, 1);
503 /* Perform intra-block Data Dependency analysis and connect the nodes in
504 the DDG. We assume the loop has a single basic block. */
505 static void
506 build_intra_loop_deps (ddg_ptr g)
508 int i;
509 /* Hold the dependency analysis state during dependency calculations. */
510 struct deps_desc tmp_deps;
511 rtx head, tail;
513 /* Build the dependence information, using the sched_analyze function. */
514 init_deps_global ();
515 init_deps (&tmp_deps, false);
517 /* Do the intra-block data dependence analysis for the given block. */
518 get_ebb_head_tail (g->bb, g->bb, &head, &tail);
519 sched_analyze (&tmp_deps, head, tail);
521 /* Build intra-loop data dependencies using the scheduler dependency
522 analysis. */
523 for (i = 0; i < g->num_nodes; i++)
525 ddg_node_ptr dest_node = &g->nodes[i];
526 sd_iterator_def sd_it;
527 dep_t dep;
529 if (! INSN_P (dest_node->insn))
530 continue;
532 FOR_EACH_DEP (dest_node->insn, SD_LIST_BACK, sd_it, dep)
534 rtx src_insn = DEP_PRO (dep);
535 ddg_node_ptr src_node;
537 /* Don't add dependencies on debug insns to non-debug insns
538 to avoid codegen differences between -g and -g0. */
539 if (DEBUG_INSN_P (src_insn) && !DEBUG_INSN_P (dest_node->insn))
540 continue;
542 src_node = get_node_of_insn (g, src_insn);
544 if (!src_node)
545 continue;
547 create_ddg_dep_from_intra_loop_link (g, src_node, dest_node, dep);
550 /* If this insn modifies memory, add an edge to all insns that access
551 memory. */
552 if (mem_access_insn_p (dest_node->insn))
554 int j;
556 for (j = 0; j <= i; j++)
558 ddg_node_ptr j_node = &g->nodes[j];
559 if (DEBUG_INSN_P (j_node->insn))
560 continue;
561 if (mem_access_insn_p (j_node->insn))
563 /* Don't bother calculating inter-loop dep if an intra-loop dep
564 already exists. */
565 if (! bitmap_bit_p (dest_node->successors, j))
566 add_inter_loop_mem_dep (g, dest_node, j_node);
567 /* If -fmodulo-sched-allow-regmoves
568 is set certain anti-dep edges are not created.
569 It might be that these anti-dep edges are on the
570 path from one memory instruction to another such that
571 removing these edges could cause a violation of the
572 memory dependencies. Thus we add intra edges between
573 every two memory instructions in this case. */
574 if (flag_modulo_sched_allow_regmoves
575 && !bitmap_bit_p (dest_node->predecessors, j))
576 add_intra_loop_mem_dep (g, j_node, dest_node);
582 /* Free the INSN_LISTs. */
583 finish_deps_global ();
584 free_deps (&tmp_deps);
586 /* Free dependencies. */
587 sched_free_deps (head, tail, false);
591 /* Given a basic block, create its DDG and return a pointer to a variable
592 of ddg type that represents it.
593 Initialize the ddg structure fields to the appropriate values. */
594 ddg_ptr
595 create_ddg (basic_block bb, int closing_branch_deps)
597 ddg_ptr g;
598 rtx insn, first_note;
599 int i;
600 int num_nodes = 0;
602 g = (ddg_ptr) xcalloc (1, sizeof (struct ddg));
604 g->bb = bb;
605 g->closing_branch_deps = closing_branch_deps;
607 /* Count the number of insns in the BB. */
608 for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb));
609 insn = NEXT_INSN (insn))
611 if (! INSN_P (insn) || GET_CODE (PATTERN (insn)) == USE)
612 continue;
614 if (DEBUG_INSN_P (insn))
615 g->num_debug++;
616 else
618 if (mem_read_insn_p (insn))
619 g->num_loads++;
620 if (mem_write_insn_p (insn))
621 g->num_stores++;
623 num_nodes++;
626 /* There is nothing to do for this BB. */
627 if ((num_nodes - g->num_debug) <= 1)
629 free (g);
630 return NULL;
633 /* Allocate the nodes array, and initialize the nodes. */
634 g->num_nodes = num_nodes;
635 g->nodes = (ddg_node_ptr) xcalloc (num_nodes, sizeof (struct ddg_node));
636 g->closing_branch = NULL;
637 i = 0;
638 first_note = NULL_RTX;
639 for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb));
640 insn = NEXT_INSN (insn))
642 if (! INSN_P (insn))
644 if (! first_note && NOTE_P (insn)
645 && NOTE_KIND (insn) != NOTE_INSN_BASIC_BLOCK)
646 first_note = insn;
647 continue;
649 if (JUMP_P (insn))
651 gcc_assert (!g->closing_branch);
652 g->closing_branch = &g->nodes[i];
654 else if (GET_CODE (PATTERN (insn)) == USE)
656 if (! first_note)
657 first_note = insn;
658 continue;
661 g->nodes[i].cuid = i;
662 g->nodes[i].successors = sbitmap_alloc (num_nodes);
663 bitmap_clear (g->nodes[i].successors);
664 g->nodes[i].predecessors = sbitmap_alloc (num_nodes);
665 bitmap_clear (g->nodes[i].predecessors);
666 g->nodes[i].first_note = (first_note ? first_note : insn);
667 g->nodes[i++].insn = insn;
668 first_note = NULL_RTX;
671 /* We must have found a branch in DDG. */
672 gcc_assert (g->closing_branch);
675 /* Build the data dependency graph. */
676 build_intra_loop_deps (g);
677 build_inter_loop_deps (g);
678 return g;
681 /* Free all the memory allocated for the DDG. */
682 void
683 free_ddg (ddg_ptr g)
685 int i;
687 if (!g)
688 return;
690 for (i = 0; i < g->num_nodes; i++)
692 ddg_edge_ptr e = g->nodes[i].out;
694 while (e)
696 ddg_edge_ptr next = e->next_out;
698 free (e);
699 e = next;
701 sbitmap_free (g->nodes[i].successors);
702 sbitmap_free (g->nodes[i].predecessors);
704 if (g->num_backarcs > 0)
705 free (g->backarcs);
706 free (g->nodes);
707 free (g);
710 void
711 print_ddg_edge (FILE *file, ddg_edge_ptr e)
713 char dep_c;
715 switch (e->type)
717 case OUTPUT_DEP :
718 dep_c = 'O';
719 break;
720 case ANTI_DEP :
721 dep_c = 'A';
722 break;
723 default:
724 dep_c = 'T';
727 fprintf (file, " [%d -(%c,%d,%d)-> %d] ", INSN_UID (e->src->insn),
728 dep_c, e->latency, e->distance, INSN_UID (e->dest->insn));
731 /* Print the DDG nodes with there in/out edges to the dump file. */
732 void
733 print_ddg (FILE *file, ddg_ptr g)
735 int i;
737 for (i = 0; i < g->num_nodes; i++)
739 ddg_edge_ptr e;
741 fprintf (file, "Node num: %d\n", g->nodes[i].cuid);
742 print_rtl_single (file, g->nodes[i].insn);
743 fprintf (file, "OUT ARCS: ");
744 for (e = g->nodes[i].out; e; e = e->next_out)
745 print_ddg_edge (file, e);
747 fprintf (file, "\nIN ARCS: ");
748 for (e = g->nodes[i].in; e; e = e->next_in)
749 print_ddg_edge (file, e);
751 fprintf (file, "\n");
755 /* Print the given DDG in VCG format. */
756 DEBUG_FUNCTION void
757 vcg_print_ddg (FILE *file, ddg_ptr g)
759 int src_cuid;
761 fprintf (file, "graph: {\n");
762 for (src_cuid = 0; src_cuid < g->num_nodes; src_cuid++)
764 ddg_edge_ptr e;
765 int src_uid = INSN_UID (g->nodes[src_cuid].insn);
767 fprintf (file, "node: {title: \"%d_%d\" info1: \"", src_cuid, src_uid);
768 print_rtl_single (file, g->nodes[src_cuid].insn);
769 fprintf (file, "\"}\n");
770 for (e = g->nodes[src_cuid].out; e; e = e->next_out)
772 int dst_uid = INSN_UID (e->dest->insn);
773 int dst_cuid = e->dest->cuid;
775 /* Give the backarcs a different color. */
776 if (e->distance > 0)
777 fprintf (file, "backedge: {color: red ");
778 else
779 fprintf (file, "edge: { ");
781 fprintf (file, "sourcename: \"%d_%d\" ", src_cuid, src_uid);
782 fprintf (file, "targetname: \"%d_%d\" ", dst_cuid, dst_uid);
783 fprintf (file, "label: \"%d_%d\"}\n", e->latency, e->distance);
786 fprintf (file, "}\n");
789 /* Dump the sccs in SCCS. */
790 void
791 print_sccs (FILE *file, ddg_all_sccs_ptr sccs, ddg_ptr g)
793 unsigned int u = 0;
794 sbitmap_iterator sbi;
795 int i;
797 if (!file)
798 return;
800 fprintf (file, "\n;; Number of SCC nodes - %d\n", sccs->num_sccs);
801 for (i = 0; i < sccs->num_sccs; i++)
803 fprintf (file, "SCC number: %d\n", i);
804 EXECUTE_IF_SET_IN_BITMAP (sccs->sccs[i]->nodes, 0, u, sbi)
806 fprintf (file, "insn num %d\n", u);
807 print_rtl_single (file, g->nodes[u].insn);
810 fprintf (file, "\n");
813 /* Create an edge and initialize it with given values. */
814 static ddg_edge_ptr
815 create_ddg_edge (ddg_node_ptr src, ddg_node_ptr dest,
816 dep_type t, dep_data_type dt, int l, int d)
818 ddg_edge_ptr e = (ddg_edge_ptr) xmalloc (sizeof (struct ddg_edge));
820 e->src = src;
821 e->dest = dest;
822 e->type = t;
823 e->data_type = dt;
824 e->latency = l;
825 e->distance = d;
826 e->next_in = e->next_out = NULL;
827 e->aux.info = 0;
828 return e;
831 /* Add the given edge to the in/out linked lists of the DDG nodes. */
832 static void
833 add_edge_to_ddg (ddg_ptr g ATTRIBUTE_UNUSED, ddg_edge_ptr e)
835 ddg_node_ptr src = e->src;
836 ddg_node_ptr dest = e->dest;
838 /* Should have allocated the sbitmaps. */
839 gcc_assert (src->successors && dest->predecessors);
841 bitmap_set_bit (src->successors, dest->cuid);
842 bitmap_set_bit (dest->predecessors, src->cuid);
843 e->next_in = dest->in;
844 dest->in = e;
845 e->next_out = src->out;
846 src->out = e;
851 /* Algorithm for computing the recurrence_length of an scc. We assume at
852 for now that cycles in the data dependence graph contain a single backarc.
853 This simplifies the algorithm, and can be generalized later. */
854 static void
855 set_recurrence_length (ddg_scc_ptr scc, ddg_ptr g)
857 int j;
858 int result = -1;
860 for (j = 0; j < scc->num_backarcs; j++)
862 ddg_edge_ptr backarc = scc->backarcs[j];
863 int length;
864 int distance = backarc->distance;
865 ddg_node_ptr src = backarc->dest;
866 ddg_node_ptr dest = backarc->src;
868 length = longest_simple_path (g, src->cuid, dest->cuid, scc->nodes);
869 if (length < 0 )
871 /* fprintf (stderr, "Backarc not on simple cycle in SCC.\n"); */
872 continue;
874 length += backarc->latency;
875 result = MAX (result, (length / distance));
877 scc->recurrence_length = result;
880 /* Create a new SCC given the set of its nodes. Compute its recurrence_length
881 and mark edges that belong to this scc as IN_SCC. */
882 static ddg_scc_ptr
883 create_scc (ddg_ptr g, sbitmap nodes)
885 ddg_scc_ptr scc;
886 unsigned int u = 0;
887 sbitmap_iterator sbi;
889 scc = (ddg_scc_ptr) xmalloc (sizeof (struct ddg_scc));
890 scc->backarcs = NULL;
891 scc->num_backarcs = 0;
892 scc->nodes = sbitmap_alloc (g->num_nodes);
893 bitmap_copy (scc->nodes, nodes);
895 /* Mark the backarcs that belong to this SCC. */
896 EXECUTE_IF_SET_IN_BITMAP (nodes, 0, u, sbi)
898 ddg_edge_ptr e;
899 ddg_node_ptr n = &g->nodes[u];
901 for (e = n->out; e; e = e->next_out)
902 if (bitmap_bit_p (nodes, e->dest->cuid))
904 e->aux.count = IN_SCC;
905 if (e->distance > 0)
906 add_backarc_to_scc (scc, e);
910 set_recurrence_length (scc, g);
911 return scc;
914 /* Cleans the memory allocation of a given SCC. */
915 static void
916 free_scc (ddg_scc_ptr scc)
918 if (!scc)
919 return;
921 sbitmap_free (scc->nodes);
922 if (scc->num_backarcs > 0)
923 free (scc->backarcs);
924 free (scc);
928 /* Add a given edge known to be a backarc to the given DDG. */
929 static void
930 add_backarc_to_ddg (ddg_ptr g, ddg_edge_ptr e)
932 int size = (g->num_backarcs + 1) * sizeof (ddg_edge_ptr);
934 add_edge_to_ddg (g, e);
935 g->backarcs = (ddg_edge_ptr *) xrealloc (g->backarcs, size);
936 g->backarcs[g->num_backarcs++] = e;
939 /* Add backarc to an SCC. */
940 static void
941 add_backarc_to_scc (ddg_scc_ptr scc, ddg_edge_ptr e)
943 int size = (scc->num_backarcs + 1) * sizeof (ddg_edge_ptr);
945 scc->backarcs = (ddg_edge_ptr *) xrealloc (scc->backarcs, size);
946 scc->backarcs[scc->num_backarcs++] = e;
949 /* Add the given SCC to the DDG. */
950 static void
951 add_scc_to_ddg (ddg_all_sccs_ptr g, ddg_scc_ptr scc)
953 int size = (g->num_sccs + 1) * sizeof (ddg_scc_ptr);
955 g->sccs = (ddg_scc_ptr *) xrealloc (g->sccs, size);
956 g->sccs[g->num_sccs++] = scc;
959 /* Given the instruction INSN return the node that represents it. */
960 ddg_node_ptr
961 get_node_of_insn (ddg_ptr g, rtx insn)
963 int i;
965 for (i = 0; i < g->num_nodes; i++)
966 if (insn == g->nodes[i].insn)
967 return &g->nodes[i];
968 return NULL;
971 /* Given a set OPS of nodes in the DDG, find the set of their successors
972 which are not in OPS, and set their bits in SUCC. Bits corresponding to
973 OPS are cleared from SUCC. Leaves the other bits in SUCC unchanged. */
974 void
975 find_successors (sbitmap succ, ddg_ptr g, sbitmap ops)
977 unsigned int i = 0;
978 sbitmap_iterator sbi;
980 EXECUTE_IF_SET_IN_BITMAP (ops, 0, i, sbi)
982 const sbitmap node_succ = NODE_SUCCESSORS (&g->nodes[i]);
983 bitmap_ior (succ, succ, node_succ);
986 /* We want those that are not in ops. */
987 bitmap_and_compl (succ, succ, ops);
990 /* Given a set OPS of nodes in the DDG, find the set of their predecessors
991 which are not in OPS, and set their bits in PREDS. Bits corresponding to
992 OPS are cleared from PREDS. Leaves the other bits in PREDS unchanged. */
993 void
994 find_predecessors (sbitmap preds, ddg_ptr g, sbitmap ops)
996 unsigned int i = 0;
997 sbitmap_iterator sbi;
999 EXECUTE_IF_SET_IN_BITMAP (ops, 0, i, sbi)
1001 const sbitmap node_preds = NODE_PREDECESSORS (&g->nodes[i]);
1002 bitmap_ior (preds, preds, node_preds);
1005 /* We want those that are not in ops. */
1006 bitmap_and_compl (preds, preds, ops);
1010 /* Compare function to be passed to qsort to order the backarcs in descending
1011 recMII order. */
1012 static int
1013 compare_sccs (const void *s1, const void *s2)
1015 const int rec_l1 = (*(const ddg_scc_ptr *)s1)->recurrence_length;
1016 const int rec_l2 = (*(const ddg_scc_ptr *)s2)->recurrence_length;
1017 return ((rec_l2 > rec_l1) - (rec_l2 < rec_l1));
1021 /* Order the backarcs in descending recMII order using compare_sccs. */
1022 static void
1023 order_sccs (ddg_all_sccs_ptr g)
1025 qsort (g->sccs, g->num_sccs, sizeof (ddg_scc_ptr),
1026 (int (*) (const void *, const void *)) compare_sccs);
1029 #ifdef ENABLE_CHECKING
1030 /* Check that every node in SCCS belongs to exactly one strongly connected
1031 component and that no element of SCCS is empty. */
1032 static void
1033 check_sccs (ddg_all_sccs_ptr sccs, int num_nodes)
1035 int i = 0;
1036 sbitmap tmp = sbitmap_alloc (num_nodes);
1038 bitmap_clear (tmp);
1039 for (i = 0; i < sccs->num_sccs; i++)
1041 gcc_assert (!bitmap_empty_p (sccs->sccs[i]->nodes));
1042 /* Verify that every node in sccs is in exactly one strongly
1043 connected component. */
1044 gcc_assert (!bitmap_intersect_p (tmp, sccs->sccs[i]->nodes));
1045 bitmap_ior (tmp, tmp, sccs->sccs[i]->nodes);
1047 sbitmap_free (tmp);
1049 #endif
1051 /* Perform the Strongly Connected Components decomposing algorithm on the
1052 DDG and return DDG_ALL_SCCS structure that contains them. */
1053 ddg_all_sccs_ptr
1054 create_ddg_all_sccs (ddg_ptr g)
1056 int i;
1057 int num_nodes = g->num_nodes;
1058 sbitmap from = sbitmap_alloc (num_nodes);
1059 sbitmap to = sbitmap_alloc (num_nodes);
1060 sbitmap scc_nodes = sbitmap_alloc (num_nodes);
1061 ddg_all_sccs_ptr sccs = (ddg_all_sccs_ptr)
1062 xmalloc (sizeof (struct ddg_all_sccs));
1064 sccs->ddg = g;
1065 sccs->sccs = NULL;
1066 sccs->num_sccs = 0;
1068 for (i = 0; i < g->num_backarcs; i++)
1070 ddg_scc_ptr scc;
1071 ddg_edge_ptr backarc = g->backarcs[i];
1072 ddg_node_ptr src = backarc->src;
1073 ddg_node_ptr dest = backarc->dest;
1075 /* If the backarc already belongs to an SCC, continue. */
1076 if (backarc->aux.count == IN_SCC)
1077 continue;
1079 bitmap_clear (scc_nodes);
1080 bitmap_clear (from);
1081 bitmap_clear (to);
1082 bitmap_set_bit (from, dest->cuid);
1083 bitmap_set_bit (to, src->cuid);
1085 if (find_nodes_on_paths (scc_nodes, g, from, to))
1087 scc = create_scc (g, scc_nodes);
1088 add_scc_to_ddg (sccs, scc);
1091 order_sccs (sccs);
1092 sbitmap_free (from);
1093 sbitmap_free (to);
1094 sbitmap_free (scc_nodes);
1095 #ifdef ENABLE_CHECKING
1096 check_sccs (sccs, num_nodes);
1097 #endif
1098 return sccs;
1101 /* Frees the memory allocated for all SCCs of the DDG, but keeps the DDG. */
1102 void
1103 free_ddg_all_sccs (ddg_all_sccs_ptr all_sccs)
1105 int i;
1107 if (!all_sccs)
1108 return;
1110 for (i = 0; i < all_sccs->num_sccs; i++)
1111 free_scc (all_sccs->sccs[i]);
1113 free (all_sccs->sccs);
1114 free (all_sccs);
1118 /* Given FROM - a bitmap of source nodes - and TO - a bitmap of destination
1119 nodes - find all nodes that lie on paths from FROM to TO (not excluding
1120 nodes from FROM and TO). Return nonzero if nodes exist. */
1122 find_nodes_on_paths (sbitmap result, ddg_ptr g, sbitmap from, sbitmap to)
1124 int answer;
1125 int change;
1126 unsigned int u = 0;
1127 int num_nodes = g->num_nodes;
1128 sbitmap_iterator sbi;
1130 sbitmap workset = sbitmap_alloc (num_nodes);
1131 sbitmap reachable_from = sbitmap_alloc (num_nodes);
1132 sbitmap reach_to = sbitmap_alloc (num_nodes);
1133 sbitmap tmp = sbitmap_alloc (num_nodes);
1135 bitmap_copy (reachable_from, from);
1136 bitmap_copy (tmp, from);
1138 change = 1;
1139 while (change)
1141 change = 0;
1142 bitmap_copy (workset, tmp);
1143 bitmap_clear (tmp);
1144 EXECUTE_IF_SET_IN_BITMAP (workset, 0, u, sbi)
1146 ddg_edge_ptr e;
1147 ddg_node_ptr u_node = &g->nodes[u];
1149 for (e = u_node->out; e != (ddg_edge_ptr) 0; e = e->next_out)
1151 ddg_node_ptr v_node = e->dest;
1152 int v = v_node->cuid;
1154 if (!bitmap_bit_p (reachable_from, v))
1156 bitmap_set_bit (reachable_from, v);
1157 bitmap_set_bit (tmp, v);
1158 change = 1;
1164 bitmap_copy (reach_to, to);
1165 bitmap_copy (tmp, to);
1167 change = 1;
1168 while (change)
1170 change = 0;
1171 bitmap_copy (workset, tmp);
1172 bitmap_clear (tmp);
1173 EXECUTE_IF_SET_IN_BITMAP (workset, 0, u, sbi)
1175 ddg_edge_ptr e;
1176 ddg_node_ptr u_node = &g->nodes[u];
1178 for (e = u_node->in; e != (ddg_edge_ptr) 0; e = e->next_in)
1180 ddg_node_ptr v_node = e->src;
1181 int v = v_node->cuid;
1183 if (!bitmap_bit_p (reach_to, v))
1185 bitmap_set_bit (reach_to, v);
1186 bitmap_set_bit (tmp, v);
1187 change = 1;
1193 answer = bitmap_and (result, reachable_from, reach_to);
1194 sbitmap_free (workset);
1195 sbitmap_free (reachable_from);
1196 sbitmap_free (reach_to);
1197 sbitmap_free (tmp);
1198 return answer;
1202 /* Updates the counts of U_NODE's successors (that belong to NODES) to be
1203 at-least as large as the count of U_NODE plus the latency between them.
1204 Sets a bit in TMP for each successor whose count was changed (increased).
1205 Returns nonzero if any count was changed. */
1206 static int
1207 update_dist_to_successors (ddg_node_ptr u_node, sbitmap nodes, sbitmap tmp)
1209 ddg_edge_ptr e;
1210 int result = 0;
1212 for (e = u_node->out; e; e = e->next_out)
1214 ddg_node_ptr v_node = e->dest;
1215 int v = v_node->cuid;
1217 if (bitmap_bit_p (nodes, v)
1218 && (e->distance == 0)
1219 && (v_node->aux.count < u_node->aux.count + e->latency))
1221 v_node->aux.count = u_node->aux.count + e->latency;
1222 bitmap_set_bit (tmp, v);
1223 result = 1;
1226 return result;
1230 /* Find the length of a longest path from SRC to DEST in G,
1231 going only through NODES, and disregarding backarcs. */
1233 longest_simple_path (struct ddg * g, int src, int dest, sbitmap nodes)
1235 int i;
1236 unsigned int u = 0;
1237 int change = 1;
1238 int result;
1239 int num_nodes = g->num_nodes;
1240 sbitmap workset = sbitmap_alloc (num_nodes);
1241 sbitmap tmp = sbitmap_alloc (num_nodes);
1244 /* Data will hold the distance of the longest path found so far from
1245 src to each node. Initialize to -1 = less than minimum. */
1246 for (i = 0; i < g->num_nodes; i++)
1247 g->nodes[i].aux.count = -1;
1248 g->nodes[src].aux.count = 0;
1250 bitmap_clear (tmp);
1251 bitmap_set_bit (tmp, src);
1253 while (change)
1255 sbitmap_iterator sbi;
1257 change = 0;
1258 bitmap_copy (workset, tmp);
1259 bitmap_clear (tmp);
1260 EXECUTE_IF_SET_IN_BITMAP (workset, 0, u, sbi)
1262 ddg_node_ptr u_node = &g->nodes[u];
1264 change |= update_dist_to_successors (u_node, nodes, tmp);
1267 result = g->nodes[dest].aux.count;
1268 sbitmap_free (workset);
1269 sbitmap_free (tmp);
1270 return result;
1273 #endif /* INSN_SCHEDULING */