* gcc.dg/compat/struct-layout-1_generate.c (dg_options): New. Moved
[official-gcc.git] / gcc / ddg.c
blob1f8c1406fc45507a4757b82702d800c7d42b6ab9
1 /* DDG - Data Dependence Graph implementation.
2 Copyright (C) 2004, 2005, 2006, 2007
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 "toplev.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 "cfglayout.h"
41 #include "cfgloop.h"
42 #include "sbitmap.h"
43 #include "expr.h"
44 #include "bitmap.h"
45 #include "ddg.h"
47 #ifdef INSN_SCHEDULING
49 /* A flag indicating that a ddg edge belongs to an SCC or not. */
50 enum edge_flag {NOT_IN_SCC = 0, IN_SCC};
52 /* Forward declarations. */
53 static void add_backarc_to_ddg (ddg_ptr, ddg_edge_ptr);
54 static void add_backarc_to_scc (ddg_scc_ptr, ddg_edge_ptr);
55 static void add_scc_to_ddg (ddg_all_sccs_ptr, ddg_scc_ptr);
56 static void create_ddg_dep_from_intra_loop_link (ddg_ptr, ddg_node_ptr,
57 ddg_node_ptr, dep_t);
58 static void create_ddg_dep_no_link (ddg_ptr, ddg_node_ptr, ddg_node_ptr,
59 dep_type, dep_data_type, int);
60 static ddg_edge_ptr create_ddg_edge (ddg_node_ptr, ddg_node_ptr, dep_type,
61 dep_data_type, int, int);
62 static void add_edge_to_ddg (ddg_ptr g, ddg_edge_ptr);
64 /* Auxiliary variable for mem_read_insn_p/mem_write_insn_p. */
65 static bool mem_ref_p;
67 /* Auxiliary function for mem_read_insn_p. */
68 static int
69 mark_mem_use (rtx *x, void *data ATTRIBUTE_UNUSED)
71 if (MEM_P (*x))
72 mem_ref_p = true;
73 return 0;
76 /* Auxiliary function for mem_read_insn_p. */
77 static void
78 mark_mem_use_1 (rtx *x, void *data)
80 for_each_rtx (x, mark_mem_use, data);
83 /* Returns nonzero if INSN reads from memory. */
84 static bool
85 mem_read_insn_p (rtx insn)
87 mem_ref_p = false;
88 note_uses (&PATTERN (insn), mark_mem_use_1, NULL);
89 return mem_ref_p;
92 static void
93 mark_mem_store (rtx loc, const_rtx setter ATTRIBUTE_UNUSED, void *data ATTRIBUTE_UNUSED)
95 if (MEM_P (loc))
96 mem_ref_p = true;
99 /* Returns nonzero if INSN writes to memory. */
100 static bool
101 mem_write_insn_p (rtx insn)
103 mem_ref_p = false;
104 note_stores (PATTERN (insn), mark_mem_store, NULL);
105 return mem_ref_p;
108 /* Returns nonzero if X has access to memory. */
109 static bool
110 rtx_mem_access_p (rtx x)
112 int i, j;
113 const char *fmt;
114 enum rtx_code code;
116 if (x == 0)
117 return false;
119 if (MEM_P (x))
120 return true;
122 code = GET_CODE (x);
123 fmt = GET_RTX_FORMAT (code);
124 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
126 if (fmt[i] == 'e')
128 if (rtx_mem_access_p (XEXP (x, i)))
129 return true;
131 else if (fmt[i] == 'E')
132 for (j = 0; j < XVECLEN (x, i); j++)
134 if (rtx_mem_access_p (XVECEXP (x, i, j)))
135 return true;
138 return false;
141 /* Returns nonzero if INSN reads to or writes from memory. */
142 static bool
143 mem_access_insn_p (rtx insn)
145 return rtx_mem_access_p (PATTERN (insn));
148 /* Computes the dependence parameters (latency, distance etc.), creates
149 a ddg_edge and adds it to the given DDG. */
150 static void
151 create_ddg_dep_from_intra_loop_link (ddg_ptr g, ddg_node_ptr src_node,
152 ddg_node_ptr dest_node, dep_t link)
154 ddg_edge_ptr e;
155 int latency, distance = 0;
156 dep_type t = TRUE_DEP;
157 dep_data_type dt = (mem_access_insn_p (src_node->insn)
158 && mem_access_insn_p (dest_node->insn) ? MEM_DEP
159 : REG_DEP);
160 gcc_assert (src_node->cuid < dest_node->cuid);
161 gcc_assert (link);
163 /* Note: REG_DEP_ANTI applies to MEM ANTI_DEP as well!! */
164 if (DEP_TYPE (link) == REG_DEP_ANTI)
165 t = ANTI_DEP;
166 else if (DEP_TYPE (link) == REG_DEP_OUTPUT)
167 t = OUTPUT_DEP;
169 /* We currently choose not to create certain anti-deps edges and
170 compensate for that by generating reg-moves based on the life-range
171 analysis. The anti-deps that will be deleted are the ones which
172 have true-deps edges in the opposite direction (in other words
173 the kernel has only one def of the relevant register). TODO:
174 support the removal of all anti-deps edges, i.e. including those
175 whose register has multiple defs in the loop. */
176 if (flag_modulo_sched_allow_regmoves && (t == ANTI_DEP && dt == REG_DEP))
178 rtx set;
180 set = single_set (dest_node->insn);
181 /* TODO: Handle registers that REG_P is not true for them, i.e.
182 subregs and special registers. */
183 if (set && REG_P (SET_DEST (set)))
185 int regno = REGNO (SET_DEST (set));
186 struct df_ref *first_def;
187 struct df_rd_bb_info *bb_info = DF_RD_BB_INFO (g->bb);
189 first_def = df_bb_regno_first_def_find (g->bb, regno);
190 gcc_assert (first_def);
192 if (bitmap_bit_p (bb_info->gen, first_def->id))
193 return;
197 latency = dep_cost (link);
198 e = create_ddg_edge (src_node, dest_node, t, dt, latency, distance);
199 add_edge_to_ddg (g, e);
202 /* The same as the above function, but it doesn't require a link parameter. */
203 static void
204 create_ddg_dep_no_link (ddg_ptr g, ddg_node_ptr from, ddg_node_ptr to,
205 dep_type d_t, dep_data_type d_dt, int distance)
207 ddg_edge_ptr e;
208 int l;
209 enum reg_note dep_kind;
210 struct _dep _dep, *dep = &_dep;
212 if (d_t == ANTI_DEP)
213 dep_kind = REG_DEP_ANTI;
214 else if (d_t == OUTPUT_DEP)
215 dep_kind = REG_DEP_OUTPUT;
216 else
218 gcc_assert (d_t == TRUE_DEP);
220 dep_kind = REG_DEP_TRUE;
223 init_dep (dep, from->insn, to->insn, dep_kind);
225 l = dep_cost (dep);
227 e = create_ddg_edge (from, to, d_t, d_dt, l, distance);
228 if (distance > 0)
229 add_backarc_to_ddg (g, e);
230 else
231 add_edge_to_ddg (g, e);
235 /* Given a downwards exposed register def LAST_DEF (which is the last
236 definition of that register in the bb), add inter-loop true dependences
237 to all its uses in the next iteration, an output dependence to the
238 first def of the same register (possibly itself) in the next iteration
239 and anti-dependences from its uses in the current iteration to the
240 first definition in the next iteration. */
241 static void
242 add_cross_iteration_register_deps (ddg_ptr g, struct df_ref *last_def)
244 int regno = DF_REF_REGNO (last_def);
245 struct df_link *r_use;
246 int has_use_in_bb_p = false;
247 rtx def_insn = DF_REF_INSN (last_def);
248 ddg_node_ptr last_def_node = get_node_of_insn (g, def_insn);
249 ddg_node_ptr use_node;
250 #ifdef ENABLE_CHECKING
251 struct df_rd_bb_info *bb_info = DF_RD_BB_INFO (g->bb);
252 #endif
253 struct df_ref *first_def = df_bb_regno_first_def_find (g->bb, regno);
255 gcc_assert (last_def_node);
256 gcc_assert (first_def);
258 #ifdef ENABLE_CHECKING
259 if (last_def->id != first_def->id)
260 gcc_assert (!bitmap_bit_p (bb_info->gen, first_def->id));
261 #endif
263 /* Create inter-loop true dependences and anti dependences. */
264 for (r_use = DF_REF_CHAIN (last_def); r_use != NULL; r_use = r_use->next)
266 rtx use_insn = DF_REF_INSN (r_use->ref);
268 if (BLOCK_FOR_INSN (use_insn) != g->bb)
269 continue;
271 /* ??? Do not handle uses with DF_REF_IN_NOTE notes. */
272 use_node = get_node_of_insn (g, use_insn);
273 gcc_assert (use_node);
274 has_use_in_bb_p = true;
275 if (use_node->cuid <= last_def_node->cuid)
277 /* Add true deps from last_def to it's uses in the next
278 iteration. Any such upwards exposed use appears before
279 the last_def def. */
280 create_ddg_dep_no_link (g, last_def_node, use_node, TRUE_DEP,
281 REG_DEP, 1);
283 else
285 /* Add anti deps from last_def's uses in the current iteration
286 to the first def in the next iteration. We do not add ANTI
287 dep when there is an intra-loop TRUE dep in the opposite
288 direction, but use regmoves to fix such disregarded ANTI
289 deps when broken. If the first_def reaches the USE then
290 there is such a dep. */
291 ddg_node_ptr first_def_node = get_node_of_insn (g,
292 DF_REF_INSN (first_def));
294 gcc_assert (first_def_node);
296 if (last_def->id != first_def->id
297 || !flag_modulo_sched_allow_regmoves)
298 create_ddg_dep_no_link (g, use_node, first_def_node, ANTI_DEP,
299 REG_DEP, 1);
303 /* Create an inter-loop output dependence between LAST_DEF (which is the
304 last def in its block, being downwards exposed) and the first def in
305 its block. Avoid creating a self output dependence. Avoid creating
306 an output dependence if there is a dependence path between the two
307 defs starting with a true dependence to a use which can be in the
308 next iteration; followed by an anti dependence of that use to the
309 first def (i.e. if there is a use between the two defs.) */
310 if (!has_use_in_bb_p)
312 ddg_node_ptr dest_node;
314 if (last_def->id == first_def->id)
315 return;
317 dest_node = get_node_of_insn (g, DF_REF_INSN (first_def));
318 gcc_assert (dest_node);
319 create_ddg_dep_no_link (g, last_def_node, dest_node,
320 OUTPUT_DEP, REG_DEP, 1);
323 /* Build inter-loop dependencies, by looking at DF analysis backwards. */
324 static void
325 build_inter_loop_deps (ddg_ptr g)
327 unsigned rd_num;
328 struct df_rd_bb_info *rd_bb_info;
329 bitmap_iterator bi;
331 rd_bb_info = DF_RD_BB_INFO (g->bb);
333 /* Find inter-loop register output, true and anti deps. */
334 EXECUTE_IF_SET_IN_BITMAP (rd_bb_info->gen, 0, rd_num, bi)
336 struct df_ref *rd = DF_DEFS_GET (rd_num);
338 add_cross_iteration_register_deps (g, rd);
343 /* Given two nodes, analyze their RTL insns and add inter-loop mem deps
344 to ddg G. */
345 static void
346 add_inter_loop_mem_dep (ddg_ptr g, ddg_node_ptr from, ddg_node_ptr to)
348 if (mem_write_insn_p (from->insn))
350 if (mem_read_insn_p (to->insn))
351 create_ddg_dep_no_link (g, from, to, TRUE_DEP, MEM_DEP, 1);
352 else if (from->cuid != to->cuid)
353 create_ddg_dep_no_link (g, from, to, OUTPUT_DEP, MEM_DEP, 1);
355 else
357 if (mem_read_insn_p (to->insn))
358 return;
359 else if (from->cuid != to->cuid)
361 create_ddg_dep_no_link (g, from, to, ANTI_DEP, MEM_DEP, 1);
362 create_ddg_dep_no_link (g, to, from, TRUE_DEP, MEM_DEP, 1);
368 /* Perform intra-block Data Dependency analysis and connect the nodes in
369 the DDG. We assume the loop has a single basic block. */
370 static void
371 build_intra_loop_deps (ddg_ptr g)
373 int i;
374 /* Hold the dependency analysis state during dependency calculations. */
375 struct deps tmp_deps;
376 rtx head, tail;
378 /* Build the dependence information, using the sched_analyze function. */
379 init_deps_global ();
380 init_deps (&tmp_deps);
382 /* Do the intra-block data dependence analysis for the given block. */
383 get_ebb_head_tail (g->bb, g->bb, &head, &tail);
384 sched_analyze (&tmp_deps, head, tail);
386 /* Build intra-loop data dependencies using the scheduler dependency
387 analysis. */
388 for (i = 0; i < g->num_nodes; i++)
390 ddg_node_ptr dest_node = &g->nodes[i];
391 sd_iterator_def sd_it;
392 dep_t dep;
394 if (! INSN_P (dest_node->insn))
395 continue;
397 FOR_EACH_DEP (dest_node->insn, SD_LIST_BACK, sd_it, dep)
399 ddg_node_ptr src_node = get_node_of_insn (g, DEP_PRO (dep));
401 if (!src_node)
402 continue;
404 create_ddg_dep_from_intra_loop_link (g, src_node, dest_node, dep);
407 /* If this insn modifies memory, add an edge to all insns that access
408 memory. */
409 if (mem_access_insn_p (dest_node->insn))
411 int j;
413 for (j = 0; j <= i; j++)
415 ddg_node_ptr j_node = &g->nodes[j];
416 if (mem_access_insn_p (j_node->insn))
417 /* Don't bother calculating inter-loop dep if an intra-loop dep
418 already exists. */
419 if (! TEST_BIT (dest_node->successors, j))
420 add_inter_loop_mem_dep (g, dest_node, j_node);
425 /* Free the INSN_LISTs. */
426 finish_deps_global ();
427 free_deps (&tmp_deps);
429 /* Free dependencies. */
430 sched_free_deps (head, tail, false);
434 /* Given a basic block, create its DDG and return a pointer to a variable
435 of ddg type that represents it.
436 Initialize the ddg structure fields to the appropriate values. */
437 ddg_ptr
438 create_ddg (basic_block bb, int closing_branch_deps)
440 ddg_ptr g;
441 rtx insn, first_note;
442 int i;
443 int num_nodes = 0;
445 g = (ddg_ptr) xcalloc (1, sizeof (struct ddg));
447 g->bb = bb;
448 g->closing_branch_deps = closing_branch_deps;
450 /* Count the number of insns in the BB. */
451 for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb));
452 insn = NEXT_INSN (insn))
454 if (! INSN_P (insn) || GET_CODE (PATTERN (insn)) == USE)
455 continue;
457 if (mem_read_insn_p (insn))
458 g->num_loads++;
459 if (mem_write_insn_p (insn))
460 g->num_stores++;
461 num_nodes++;
464 /* There is nothing to do for this BB. */
465 if (num_nodes <= 1)
467 free (g);
468 return NULL;
471 /* Allocate the nodes array, and initialize the nodes. */
472 g->num_nodes = num_nodes;
473 g->nodes = (ddg_node_ptr) xcalloc (num_nodes, sizeof (struct ddg_node));
474 g->closing_branch = NULL;
475 i = 0;
476 first_note = NULL_RTX;
477 for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb));
478 insn = NEXT_INSN (insn))
480 if (! INSN_P (insn))
482 if (! first_note && NOTE_P (insn)
483 && NOTE_KIND (insn) != NOTE_INSN_BASIC_BLOCK)
484 first_note = insn;
485 continue;
487 if (JUMP_P (insn))
489 gcc_assert (!g->closing_branch);
490 g->closing_branch = &g->nodes[i];
492 else if (GET_CODE (PATTERN (insn)) == USE)
494 if (! first_note)
495 first_note = insn;
496 continue;
499 g->nodes[i].cuid = i;
500 g->nodes[i].successors = sbitmap_alloc (num_nodes);
501 sbitmap_zero (g->nodes[i].successors);
502 g->nodes[i].predecessors = sbitmap_alloc (num_nodes);
503 sbitmap_zero (g->nodes[i].predecessors);
504 g->nodes[i].first_note = (first_note ? first_note : insn);
505 g->nodes[i++].insn = insn;
506 first_note = NULL_RTX;
509 /* We must have found a branch in DDG. */
510 gcc_assert (g->closing_branch);
513 /* Build the data dependency graph. */
514 build_intra_loop_deps (g);
515 build_inter_loop_deps (g);
516 return g;
519 /* Free all the memory allocated for the DDG. */
520 void
521 free_ddg (ddg_ptr g)
523 int i;
525 if (!g)
526 return;
528 for (i = 0; i < g->num_nodes; i++)
530 ddg_edge_ptr e = g->nodes[i].out;
532 while (e)
534 ddg_edge_ptr next = e->next_out;
536 free (e);
537 e = next;
539 sbitmap_free (g->nodes[i].successors);
540 sbitmap_free (g->nodes[i].predecessors);
542 if (g->num_backarcs > 0)
543 free (g->backarcs);
544 free (g->nodes);
545 free (g);
548 void
549 print_ddg_edge (FILE *file, ddg_edge_ptr e)
551 char dep_c;
553 switch (e->type)
555 case OUTPUT_DEP :
556 dep_c = 'O';
557 break;
558 case ANTI_DEP :
559 dep_c = 'A';
560 break;
561 default:
562 dep_c = 'T';
565 fprintf (file, " [%d -(%c,%d,%d)-> %d] ", INSN_UID (e->src->insn),
566 dep_c, e->latency, e->distance, INSN_UID (e->dest->insn));
569 /* Print the DDG nodes with there in/out edges to the dump file. */
570 void
571 print_ddg (FILE *file, ddg_ptr g)
573 int i;
575 for (i = 0; i < g->num_nodes; i++)
577 ddg_edge_ptr e;
579 fprintf (file, "Node num: %d\n", g->nodes[i].cuid);
580 print_rtl_single (file, g->nodes[i].insn);
581 fprintf (file, "OUT ARCS: ");
582 for (e = g->nodes[i].out; e; e = e->next_out)
583 print_ddg_edge (file, e);
585 fprintf (file, "\nIN ARCS: ");
586 for (e = g->nodes[i].in; e; e = e->next_in)
587 print_ddg_edge (file, e);
589 fprintf (file, "\n");
593 /* Print the given DDG in VCG format. */
594 void
595 vcg_print_ddg (FILE *file, ddg_ptr g)
597 int src_cuid;
599 fprintf (file, "graph: {\n");
600 for (src_cuid = 0; src_cuid < g->num_nodes; src_cuid++)
602 ddg_edge_ptr e;
603 int src_uid = INSN_UID (g->nodes[src_cuid].insn);
605 fprintf (file, "node: {title: \"%d_%d\" info1: \"", src_cuid, src_uid);
606 print_rtl_single (file, g->nodes[src_cuid].insn);
607 fprintf (file, "\"}\n");
608 for (e = g->nodes[src_cuid].out; e; e = e->next_out)
610 int dst_uid = INSN_UID (e->dest->insn);
611 int dst_cuid = e->dest->cuid;
613 /* Give the backarcs a different color. */
614 if (e->distance > 0)
615 fprintf (file, "backedge: {color: red ");
616 else
617 fprintf (file, "edge: { ");
619 fprintf (file, "sourcename: \"%d_%d\" ", src_cuid, src_uid);
620 fprintf (file, "targetname: \"%d_%d\" ", dst_cuid, dst_uid);
621 fprintf (file, "label: \"%d_%d\"}\n", e->latency, e->distance);
624 fprintf (file, "}\n");
627 /* Dump the sccs in SCCS. */
628 void
629 print_sccs (FILE *file, ddg_all_sccs_ptr sccs, ddg_ptr g)
631 unsigned int u = 0;
632 sbitmap_iterator sbi;
633 int i;
635 if (!file)
636 return;
638 fprintf (file, "\n;; Number of SCC nodes - %d\n", sccs->num_sccs);
639 for (i = 0; i < sccs->num_sccs; i++)
641 fprintf (file, "SCC number: %d\n", i);
642 EXECUTE_IF_SET_IN_SBITMAP (sccs->sccs[i]->nodes, 0, u, sbi)
644 fprintf (file, "insn num %d\n", u);
645 print_rtl_single (file, g->nodes[u].insn);
648 fprintf (file, "\n");
651 /* Create an edge and initialize it with given values. */
652 static ddg_edge_ptr
653 create_ddg_edge (ddg_node_ptr src, ddg_node_ptr dest,
654 dep_type t, dep_data_type dt, int l, int d)
656 ddg_edge_ptr e = (ddg_edge_ptr) xmalloc (sizeof (struct ddg_edge));
658 e->src = src;
659 e->dest = dest;
660 e->type = t;
661 e->data_type = dt;
662 e->latency = l;
663 e->distance = d;
664 e->next_in = e->next_out = NULL;
665 e->aux.info = 0;
666 return e;
669 /* Add the given edge to the in/out linked lists of the DDG nodes. */
670 static void
671 add_edge_to_ddg (ddg_ptr g ATTRIBUTE_UNUSED, ddg_edge_ptr e)
673 ddg_node_ptr src = e->src;
674 ddg_node_ptr dest = e->dest;
676 /* Should have allocated the sbitmaps. */
677 gcc_assert (src->successors && dest->predecessors);
679 SET_BIT (src->successors, dest->cuid);
680 SET_BIT (dest->predecessors, src->cuid);
681 e->next_in = dest->in;
682 dest->in = e;
683 e->next_out = src->out;
684 src->out = e;
689 /* Algorithm for computing the recurrence_length of an scc. We assume at
690 for now that cycles in the data dependence graph contain a single backarc.
691 This simplifies the algorithm, and can be generalized later. */
692 static void
693 set_recurrence_length (ddg_scc_ptr scc, ddg_ptr g)
695 int j;
696 int result = -1;
698 for (j = 0; j < scc->num_backarcs; j++)
700 ddg_edge_ptr backarc = scc->backarcs[j];
701 int length;
702 int distance = backarc->distance;
703 ddg_node_ptr src = backarc->dest;
704 ddg_node_ptr dest = backarc->src;
706 length = longest_simple_path (g, src->cuid, dest->cuid, scc->nodes);
707 if (length < 0 )
709 /* fprintf (stderr, "Backarc not on simple cycle in SCC.\n"); */
710 continue;
712 length += backarc->latency;
713 result = MAX (result, (length / distance));
715 scc->recurrence_length = result;
718 /* Create a new SCC given the set of its nodes. Compute its recurrence_length
719 and mark edges that belong to this scc as IN_SCC. */
720 static ddg_scc_ptr
721 create_scc (ddg_ptr g, sbitmap nodes)
723 ddg_scc_ptr scc;
724 unsigned int u = 0;
725 sbitmap_iterator sbi;
727 scc = (ddg_scc_ptr) xmalloc (sizeof (struct ddg_scc));
728 scc->backarcs = NULL;
729 scc->num_backarcs = 0;
730 scc->nodes = sbitmap_alloc (g->num_nodes);
731 sbitmap_copy (scc->nodes, nodes);
733 /* Mark the backarcs that belong to this SCC. */
734 EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, u, sbi)
736 ddg_edge_ptr e;
737 ddg_node_ptr n = &g->nodes[u];
739 for (e = n->out; e; e = e->next_out)
740 if (TEST_BIT (nodes, e->dest->cuid))
742 e->aux.count = IN_SCC;
743 if (e->distance > 0)
744 add_backarc_to_scc (scc, e);
748 set_recurrence_length (scc, g);
749 return scc;
752 /* Cleans the memory allocation of a given SCC. */
753 static void
754 free_scc (ddg_scc_ptr scc)
756 if (!scc)
757 return;
759 sbitmap_free (scc->nodes);
760 if (scc->num_backarcs > 0)
761 free (scc->backarcs);
762 free (scc);
766 /* Add a given edge known to be a backarc to the given DDG. */
767 static void
768 add_backarc_to_ddg (ddg_ptr g, ddg_edge_ptr e)
770 int size = (g->num_backarcs + 1) * sizeof (ddg_edge_ptr);
772 add_edge_to_ddg (g, e);
773 g->backarcs = (ddg_edge_ptr *) xrealloc (g->backarcs, size);
774 g->backarcs[g->num_backarcs++] = e;
777 /* Add backarc to an SCC. */
778 static void
779 add_backarc_to_scc (ddg_scc_ptr scc, ddg_edge_ptr e)
781 int size = (scc->num_backarcs + 1) * sizeof (ddg_edge_ptr);
783 scc->backarcs = (ddg_edge_ptr *) xrealloc (scc->backarcs, size);
784 scc->backarcs[scc->num_backarcs++] = e;
787 /* Add the given SCC to the DDG. */
788 static void
789 add_scc_to_ddg (ddg_all_sccs_ptr g, ddg_scc_ptr scc)
791 int size = (g->num_sccs + 1) * sizeof (ddg_scc_ptr);
793 g->sccs = (ddg_scc_ptr *) xrealloc (g->sccs, size);
794 g->sccs[g->num_sccs++] = scc;
797 /* Given the instruction INSN return the node that represents it. */
798 ddg_node_ptr
799 get_node_of_insn (ddg_ptr g, rtx insn)
801 int i;
803 for (i = 0; i < g->num_nodes; i++)
804 if (insn == g->nodes[i].insn)
805 return &g->nodes[i];
806 return NULL;
809 /* Given a set OPS of nodes in the DDG, find the set of their successors
810 which are not in OPS, and set their bits in SUCC. Bits corresponding to
811 OPS are cleared from SUCC. Leaves the other bits in SUCC unchanged. */
812 void
813 find_successors (sbitmap succ, ddg_ptr g, sbitmap ops)
815 unsigned int i = 0;
816 sbitmap_iterator sbi;
818 EXECUTE_IF_SET_IN_SBITMAP (ops, 0, i, sbi)
820 const sbitmap node_succ = NODE_SUCCESSORS (&g->nodes[i]);
821 sbitmap_a_or_b (succ, succ, node_succ);
824 /* We want those that are not in ops. */
825 sbitmap_difference (succ, succ, ops);
828 /* Given a set OPS of nodes in the DDG, find the set of their predecessors
829 which are not in OPS, and set their bits in PREDS. Bits corresponding to
830 OPS are cleared from PREDS. Leaves the other bits in PREDS unchanged. */
831 void
832 find_predecessors (sbitmap preds, ddg_ptr g, sbitmap ops)
834 unsigned int i = 0;
835 sbitmap_iterator sbi;
837 EXECUTE_IF_SET_IN_SBITMAP (ops, 0, i, sbi)
839 const sbitmap node_preds = NODE_PREDECESSORS (&g->nodes[i]);
840 sbitmap_a_or_b (preds, preds, node_preds);
843 /* We want those that are not in ops. */
844 sbitmap_difference (preds, preds, ops);
848 /* Compare function to be passed to qsort to order the backarcs in descending
849 recMII order. */
850 static int
851 compare_sccs (const void *s1, const void *s2)
853 const int rec_l1 = (*(const ddg_scc_ptr *)s1)->recurrence_length;
854 const int rec_l2 = (*(const ddg_scc_ptr *)s2)->recurrence_length;
855 return ((rec_l2 > rec_l1) - (rec_l2 < rec_l1));
859 /* Order the backarcs in descending recMII order using compare_sccs. */
860 static void
861 order_sccs (ddg_all_sccs_ptr g)
863 qsort (g->sccs, g->num_sccs, sizeof (ddg_scc_ptr),
864 (int (*) (const void *, const void *)) compare_sccs);
867 #ifdef ENABLE_CHECKING
868 /* Check that every node in SCCS belongs to exactly one strongly connected
869 component and that no element of SCCS is empty. */
870 static void
871 check_sccs (ddg_all_sccs_ptr sccs, int num_nodes)
873 int i = 0;
874 sbitmap tmp = sbitmap_alloc (num_nodes);
876 sbitmap_zero (tmp);
877 for (i = 0; i < sccs->num_sccs; i++)
879 gcc_assert (!sbitmap_empty_p (sccs->sccs[i]->nodes));
880 /* Verify that every node in sccs is in exactly one strongly
881 connected component. */
882 gcc_assert (!sbitmap_any_common_bits (tmp, sccs->sccs[i]->nodes));
883 sbitmap_a_or_b (tmp, tmp, sccs->sccs[i]->nodes);
885 sbitmap_free (tmp);
887 #endif
889 /* Perform the Strongly Connected Components decomposing algorithm on the
890 DDG and return DDG_ALL_SCCS structure that contains them. */
891 ddg_all_sccs_ptr
892 create_ddg_all_sccs (ddg_ptr g)
894 int i;
895 int num_nodes = g->num_nodes;
896 sbitmap from = sbitmap_alloc (num_nodes);
897 sbitmap to = sbitmap_alloc (num_nodes);
898 sbitmap scc_nodes = sbitmap_alloc (num_nodes);
899 ddg_all_sccs_ptr sccs = (ddg_all_sccs_ptr)
900 xmalloc (sizeof (struct ddg_all_sccs));
902 sccs->ddg = g;
903 sccs->sccs = NULL;
904 sccs->num_sccs = 0;
906 for (i = 0; i < g->num_backarcs; i++)
908 ddg_scc_ptr scc;
909 ddg_edge_ptr backarc = g->backarcs[i];
910 ddg_node_ptr src = backarc->src;
911 ddg_node_ptr dest = backarc->dest;
913 /* If the backarc already belongs to an SCC, continue. */
914 if (backarc->aux.count == IN_SCC)
915 continue;
917 sbitmap_zero (scc_nodes);
918 sbitmap_zero (from);
919 sbitmap_zero (to);
920 SET_BIT (from, dest->cuid);
921 SET_BIT (to, src->cuid);
923 if (find_nodes_on_paths (scc_nodes, g, from, to))
925 scc = create_scc (g, scc_nodes);
926 add_scc_to_ddg (sccs, scc);
929 order_sccs (sccs);
930 sbitmap_free (from);
931 sbitmap_free (to);
932 sbitmap_free (scc_nodes);
933 #ifdef ENABLE_CHECKING
934 check_sccs (sccs, num_nodes);
935 #endif
936 return sccs;
939 /* Frees the memory allocated for all SCCs of the DDG, but keeps the DDG. */
940 void
941 free_ddg_all_sccs (ddg_all_sccs_ptr all_sccs)
943 int i;
945 if (!all_sccs)
946 return;
948 for (i = 0; i < all_sccs->num_sccs; i++)
949 free_scc (all_sccs->sccs[i]);
951 free (all_sccs);
955 /* Given FROM - a bitmap of source nodes - and TO - a bitmap of destination
956 nodes - find all nodes that lie on paths from FROM to TO (not excluding
957 nodes from FROM and TO). Return nonzero if nodes exist. */
959 find_nodes_on_paths (sbitmap result, ddg_ptr g, sbitmap from, sbitmap to)
961 int answer;
962 int change;
963 unsigned int u = 0;
964 int num_nodes = g->num_nodes;
965 sbitmap_iterator sbi;
967 sbitmap workset = sbitmap_alloc (num_nodes);
968 sbitmap reachable_from = sbitmap_alloc (num_nodes);
969 sbitmap reach_to = sbitmap_alloc (num_nodes);
970 sbitmap tmp = sbitmap_alloc (num_nodes);
972 sbitmap_copy (reachable_from, from);
973 sbitmap_copy (tmp, from);
975 change = 1;
976 while (change)
978 change = 0;
979 sbitmap_copy (workset, tmp);
980 sbitmap_zero (tmp);
981 EXECUTE_IF_SET_IN_SBITMAP (workset, 0, u, sbi)
983 ddg_edge_ptr e;
984 ddg_node_ptr u_node = &g->nodes[u];
986 for (e = u_node->out; e != (ddg_edge_ptr) 0; e = e->next_out)
988 ddg_node_ptr v_node = e->dest;
989 int v = v_node->cuid;
991 if (!TEST_BIT (reachable_from, v))
993 SET_BIT (reachable_from, v);
994 SET_BIT (tmp, v);
995 change = 1;
1001 sbitmap_copy (reach_to, to);
1002 sbitmap_copy (tmp, to);
1004 change = 1;
1005 while (change)
1007 change = 0;
1008 sbitmap_copy (workset, tmp);
1009 sbitmap_zero (tmp);
1010 EXECUTE_IF_SET_IN_SBITMAP (workset, 0, u, sbi)
1012 ddg_edge_ptr e;
1013 ddg_node_ptr u_node = &g->nodes[u];
1015 for (e = u_node->in; e != (ddg_edge_ptr) 0; e = e->next_in)
1017 ddg_node_ptr v_node = e->src;
1018 int v = v_node->cuid;
1020 if (!TEST_BIT (reach_to, v))
1022 SET_BIT (reach_to, v);
1023 SET_BIT (tmp, v);
1024 change = 1;
1030 answer = sbitmap_a_and_b_cg (result, reachable_from, reach_to);
1031 sbitmap_free (workset);
1032 sbitmap_free (reachable_from);
1033 sbitmap_free (reach_to);
1034 sbitmap_free (tmp);
1035 return answer;
1039 /* Updates the counts of U_NODE's successors (that belong to NODES) to be
1040 at-least as large as the count of U_NODE plus the latency between them.
1041 Sets a bit in TMP for each successor whose count was changed (increased).
1042 Returns nonzero if any count was changed. */
1043 static int
1044 update_dist_to_successors (ddg_node_ptr u_node, sbitmap nodes, sbitmap tmp)
1046 ddg_edge_ptr e;
1047 int result = 0;
1049 for (e = u_node->out; e; e = e->next_out)
1051 ddg_node_ptr v_node = e->dest;
1052 int v = v_node->cuid;
1054 if (TEST_BIT (nodes, v)
1055 && (e->distance == 0)
1056 && (v_node->aux.count < u_node->aux.count + e->latency))
1058 v_node->aux.count = u_node->aux.count + e->latency;
1059 SET_BIT (tmp, v);
1060 result = 1;
1063 return result;
1067 /* Find the length of a longest path from SRC to DEST in G,
1068 going only through NODES, and disregarding backarcs. */
1070 longest_simple_path (struct ddg * g, int src, int dest, sbitmap nodes)
1072 int i;
1073 unsigned int u = 0;
1074 int change = 1;
1075 int result;
1076 int num_nodes = g->num_nodes;
1077 sbitmap workset = sbitmap_alloc (num_nodes);
1078 sbitmap tmp = sbitmap_alloc (num_nodes);
1081 /* Data will hold the distance of the longest path found so far from
1082 src to each node. Initialize to -1 = less than minimum. */
1083 for (i = 0; i < g->num_nodes; i++)
1084 g->nodes[i].aux.count = -1;
1085 g->nodes[src].aux.count = 0;
1087 sbitmap_zero (tmp);
1088 SET_BIT (tmp, src);
1090 while (change)
1092 sbitmap_iterator sbi;
1094 change = 0;
1095 sbitmap_copy (workset, tmp);
1096 sbitmap_zero (tmp);
1097 EXECUTE_IF_SET_IN_SBITMAP (workset, 0, u, sbi)
1099 ddg_node_ptr u_node = &g->nodes[u];
1101 change |= update_dist_to_successors (u_node, nodes, tmp);
1104 result = g->nodes[dest].aux.count;
1105 sbitmap_free (workset);
1106 sbitmap_free (tmp);
1107 return result;
1110 #endif /* INSN_SCHEDULING */