sourcebuild.texi: Add libcpp, now that CPP has its own directory.
[official-gcc.git] / gcc / ddg.c
blob34a5971b5a6544d33685cd990daa7f18e10f6067
1 /* DDG - Data Dependence Graph implementation.
2 Copyright (C) 2004
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 2, 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 COPYING. If not, write to the Free
20 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
21 02111-1307, USA. */
24 #include "config.h"
25 #include "system.h"
26 #include "coretypes.h"
27 #include "tm.h"
28 #include "toplev.h"
29 #include "rtl.h"
30 #include "tm_p.h"
31 #include "hard-reg-set.h"
32 #include "basic-block.h"
33 #include "regs.h"
34 #include "function.h"
35 #include "flags.h"
36 #include "insn-config.h"
37 #include "insn-attr.h"
38 #include "except.h"
39 #include "recog.h"
40 #include "sched-int.h"
41 #include "target.h"
42 #include "cfglayout.h"
43 #include "cfgloop.h"
44 #include "sbitmap.h"
45 #include "expr.h"
46 #include "bitmap.h"
47 #include "df.h"
48 #include "ddg.h"
50 /* A flag indicating that a ddg edge belongs to an SCC or not. */
51 enum edge_flag {NOT_IN_SCC = 0, IN_SCC};
53 /* Forward declarations. */
54 static void add_backarc_to_ddg (ddg_ptr, ddg_edge_ptr);
55 static void add_backarc_to_scc (ddg_scc_ptr, ddg_edge_ptr);
56 static void add_scc_to_ddg (ddg_all_sccs_ptr, ddg_scc_ptr);
57 static void create_ddg_dependence (ddg_ptr, ddg_node_ptr, ddg_node_ptr, rtx);
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, 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_dependence (ddg_ptr g, ddg_node_ptr src_node,
152 ddg_node_ptr dest_node, rtx link)
154 ddg_edge_ptr e;
155 int latency, distance = 0;
156 int interloop = (src_node->cuid >= dest_node->cuid);
157 dep_type t = TRUE_DEP;
158 dep_data_type dt = (mem_access_insn_p (src_node->insn)
159 && mem_access_insn_p (dest_node->insn) ? MEM_DEP
160 : REG_DEP);
162 /* For now we don't have an exact calculation of the distance,
163 so assume 1 conservatively. */
164 if (interloop)
165 distance = 1;
167 if (!link)
168 abort ();
170 /* Note: REG_DEP_ANTI applies to MEM ANTI_DEP as well!! */
171 if (REG_NOTE_KIND (link) == REG_DEP_ANTI)
172 t = ANTI_DEP;
173 else if (REG_NOTE_KIND (link) == REG_DEP_OUTPUT)
174 t = OUTPUT_DEP;
175 latency = insn_cost (src_node->insn, link, dest_node->insn);
177 e = create_ddg_edge (src_node, dest_node, t, dt, latency, distance);
179 if (interloop)
181 /* Some interloop dependencies are relaxed:
182 1. Every insn is output dependent on itself; ignore such deps.
183 2. Every true/flow dependence is an anti dependence in the
184 opposite direction with distance 1; such register deps
185 will be removed by renaming if broken --- ignore them. */
186 if (!(t == OUTPUT_DEP && src_node == dest_node)
187 && !(t == ANTI_DEP && dt == REG_DEP))
188 add_backarc_to_ddg (g, e);
189 else
190 free (e);
192 else
193 add_edge_to_ddg (g, e);
196 /* The same as the above function, but it doesn't require a link parameter. */
197 static void
198 create_ddg_dep_no_link (ddg_ptr g, ddg_node_ptr from, ddg_node_ptr to,
199 dep_type d_t, dep_data_type d_dt, int distance)
201 ddg_edge_ptr e;
202 int l;
203 rtx link = alloc_INSN_LIST (to->insn, NULL_RTX);
205 if (d_t == ANTI_DEP)
206 PUT_REG_NOTE_KIND (link, REG_DEP_ANTI);
207 else if (d_t == OUTPUT_DEP)
208 PUT_REG_NOTE_KIND (link, REG_DEP_OUTPUT);
210 l = insn_cost (from->insn, link, to->insn);
211 free_INSN_LIST_node (link);
213 e = create_ddg_edge (from, to, d_t, d_dt, l, distance);
214 if (distance > 0)
215 add_backarc_to_ddg (g, e);
216 else
217 add_edge_to_ddg (g, e);
221 /* Given a downwards exposed register def RD, add inter-loop true dependences
222 for all its uses in the next iteration, and an output dependence to the
223 first def of the next iteration. */
224 static void
225 add_deps_for_def (ddg_ptr g, struct df *df, struct ref *rd)
227 int regno = DF_REF_REGNO (rd);
228 struct bb_info *bb_info = DF_BB_INFO (df, g->bb);
229 struct df_link *r_use;
230 int use_before_def = false;
231 rtx def_insn = DF_REF_INSN (rd);
232 ddg_node_ptr src_node = get_node_of_insn (g, def_insn);
234 /* Create and inter-loop true dependence between RD and each of its uses
235 that is upwards exposed in RD's block. */
236 for (r_use = DF_REF_CHAIN (rd); r_use != NULL; r_use = r_use->next)
238 if (bitmap_bit_p (bb_info->ru_gen, r_use->ref->id))
240 rtx use_insn = DF_REF_INSN (r_use->ref);
241 ddg_node_ptr dest_node = get_node_of_insn (g, use_insn);
243 if (!src_node || !dest_node)
244 abort ();
246 /* Any such upwards exposed use appears before the rd def. */
247 use_before_def = true;
248 create_ddg_dep_no_link (g, src_node, dest_node, TRUE_DEP,
249 REG_DEP, 1);
253 /* Create an inter-loop output dependence between RD (which is the
254 last def in its block, being downwards exposed) and the first def
255 in its block. Avoid creating a self output dependence. Avoid creating
256 an output dependence if there is a dependence path between the two defs
257 starting with a true dependence followed by an anti dependence (i.e. if
258 there is a use between the two defs. */
259 if (! use_before_def)
261 struct ref *def = df_bb_regno_first_def_find (df, g->bb, regno);
262 int i;
263 ddg_node_ptr dest_node;
265 if (!def || rd->id == def->id)
266 return;
268 /* Check if there are uses after RD. */
269 for (i = src_node->cuid + 1; i < g->num_nodes; i++)
270 if (df_reg_used (df, g->nodes[i].insn, rd->reg))
271 return;
273 dest_node = get_node_of_insn (g, def->insn);
274 create_ddg_dep_no_link (g, src_node, dest_node, OUTPUT_DEP, REG_DEP, 1);
278 /* Given a register USE, add an inter-loop anti dependence to the first
279 (nearest BLOCK_BEGIN) def of the next iteration, unless USE is followed
280 by a def in the block. */
281 static void
282 add_deps_for_use (ddg_ptr g, struct df *df, struct ref *use)
284 int i;
285 int regno = DF_REF_REGNO (use);
286 struct ref *first_def = df_bb_regno_first_def_find (df, g->bb, regno);
287 ddg_node_ptr use_node;
288 ddg_node_ptr def_node;
289 struct bb_info *bb_info;
291 bb_info = DF_BB_INFO (df, g->bb);
293 if (!first_def)
294 return;
296 use_node = get_node_of_insn (g, use->insn);
297 def_node = get_node_of_insn (g, first_def->insn);
299 if (!use_node || !def_node)
300 abort ();
302 /* Make sure there are no defs after USE. */
303 for (i = use_node->cuid + 1; i < g->num_nodes; i++)
304 if (df_find_def (df, g->nodes[i].insn, use->reg))
305 return;
306 /* We must not add ANTI dep when there is an intra-loop TRUE dep in
307 the opozite direction. If the first_def reaches the USE then there is
308 such a dep. */
309 if (! bitmap_bit_p (bb_info->rd_gen, first_def->id))
310 create_ddg_dep_no_link (g, use_node, def_node, ANTI_DEP, REG_DEP, 1);
313 /* Build inter-loop dependencies, by looking at DF analysis backwards. */
314 static void
315 build_inter_loop_deps (ddg_ptr g, struct df *df)
317 int rd_num, u_num;
318 struct bb_info *bb_info;
320 bb_info = DF_BB_INFO (df, g->bb);
322 /* Find inter-loop output and true deps by connecting downward exposed defs
323 to the first def of the BB and to upwards exposed uses. */
324 EXECUTE_IF_SET_IN_BITMAP (bb_info->rd_gen, 0, rd_num,
326 struct ref *rd = df->defs[rd_num];
328 add_deps_for_def (g, df, rd);
331 /* Find inter-loop anti deps. We are interested in uses of the block that
332 appear below all defs; this implies that these uses are killed. */
333 EXECUTE_IF_SET_IN_BITMAP (bb_info->ru_kill, 0, u_num,
335 struct ref *use = df->uses[u_num];
337 /* We are interested in uses of this BB. */
338 if (BLOCK_FOR_INSN (use->insn) == g->bb)
339 add_deps_for_use (g, df,use);
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, link;
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_block_head_tail (g->bb->index, &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];
392 if (! INSN_P (dest_node->insn))
393 continue;
395 for (link = LOG_LINKS (dest_node->insn); link; link = XEXP (link, 1))
397 ddg_node_ptr src_node = get_node_of_insn (g, XEXP (link, 0));
399 if (!src_node)
400 continue;
402 add_forward_dependence (XEXP (link, 0), dest_node->insn,
403 REG_NOTE_KIND (link));
404 create_ddg_dependence (g, src_node, dest_node,
405 INSN_DEPEND (src_node->insn));
408 /* If this insn modifies memory, add an edge to all insns that access
409 memory. */
410 if (mem_access_insn_p (dest_node->insn))
412 int j;
414 for (j = 0; j <= i; j++)
416 ddg_node_ptr j_node = &g->nodes[j];
417 if (mem_access_insn_p (j_node->insn))
418 /* Don't bother calculating inter-loop dep if an intra-loop dep
419 already exists. */
420 if (! TEST_BIT (dest_node->successors, j))
421 add_inter_loop_mem_dep (g, dest_node, j_node);
426 /* Free the INSN_LISTs. */
427 finish_deps_global ();
428 free_deps (&tmp_deps);
432 /* Given a basic block, create its DDG and return a pointer to a variable
433 of ddg type that represents it.
434 Initialize the ddg structure fields to the appropriate values. */
435 ddg_ptr
436 create_ddg (basic_block bb, struct df *df, int closing_branch_deps)
438 ddg_ptr g;
439 rtx insn, first_note;
440 int i;
441 int num_nodes = 0;
443 g = (ddg_ptr) xcalloc (1, sizeof (struct ddg));
445 g->bb = bb;
446 g->closing_branch_deps = closing_branch_deps;
448 /* Count the number of insns in the BB. */
449 for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb));
450 insn = NEXT_INSN (insn))
452 if (! INSN_P (insn) || GET_CODE (PATTERN (insn)) == USE)
453 continue;
455 if (mem_read_insn_p (insn))
456 g->num_loads++;
457 if (mem_write_insn_p (insn))
458 g->num_stores++;
459 num_nodes++;
462 /* There is nothing to do for this BB. */
463 if (num_nodes <= 1)
465 free (g);
466 return NULL;
469 /* Allocate the nodes array, and initialize the nodes. */
470 g->num_nodes = num_nodes;
471 g->nodes = (ddg_node_ptr) xcalloc (num_nodes, sizeof (struct ddg_node));
472 g->closing_branch = NULL;
473 i = 0;
474 first_note = NULL_RTX;
475 for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb));
476 insn = NEXT_INSN (insn))
478 if (! INSN_P (insn))
480 if (! first_note && NOTE_P (insn)
481 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_BASIC_BLOCK)
482 first_note = insn;
483 continue;
485 if (JUMP_P (insn))
487 if (g->closing_branch)
488 abort (); /* Found two branches in DDG. */
489 else
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 if (!g->closing_branch)
510 abort (); /* Found no branch in DDG. */
512 /* Build the data dependency graph. */
513 build_intra_loop_deps (g);
514 build_inter_loop_deps (g, df);
515 return g;
518 /* Free all the memory allocated for the DDG. */
519 void
520 free_ddg (ddg_ptr g)
522 int i;
524 if (!g)
525 return;
527 for (i = 0; i < g->num_nodes; i++)
529 ddg_edge_ptr e = g->nodes[i].out;
531 while (e)
533 ddg_edge_ptr next = e->next_out;
535 free (e);
536 e = next;
538 sbitmap_free (g->nodes[i].successors);
539 sbitmap_free (g->nodes[i].predecessors);
541 if (g->num_backarcs > 0)
542 free (g->backarcs);
543 free (g->nodes);
544 free (g);
547 void
548 print_ddg_edge (FILE *dump_file, ddg_edge_ptr e)
550 char dep_c;
552 switch (e->type) {
553 case OUTPUT_DEP :
554 dep_c = 'O';
555 break;
556 case ANTI_DEP :
557 dep_c = 'A';
558 break;
559 default:
560 dep_c = 'T';
563 fprintf (dump_file, " [%d -(%c,%d,%d)-> %d] ", INSN_UID (e->src->insn),
564 dep_c, e->latency, e->distance, INSN_UID (e->dest->insn));
567 /* Print the DDG nodes with there in/out edges to the dump file. */
568 void
569 print_ddg (FILE *dump_file, ddg_ptr g)
571 int i;
573 for (i = 0; i < g->num_nodes; i++)
575 ddg_edge_ptr e;
577 print_rtl_single (dump_file, g->nodes[i].insn);
578 fprintf (dump_file, "OUT ARCS: ");
579 for (e = g->nodes[i].out; e; e = e->next_out)
580 print_ddg_edge (dump_file, e);
582 fprintf (dump_file, "\nIN ARCS: ");
583 for (e = g->nodes[i].in; e; e = e->next_in)
584 print_ddg_edge (dump_file, e);
586 fprintf (dump_file, "\n");
590 /* Print the given DDG in VCG format. */
591 void
592 vcg_print_ddg (FILE *dump_file, ddg_ptr g)
594 int src_cuid;
596 fprintf (dump_file, "graph: {\n");
597 for (src_cuid = 0; src_cuid < g->num_nodes; src_cuid++)
599 ddg_edge_ptr e;
600 int src_uid = INSN_UID (g->nodes[src_cuid].insn);
602 fprintf (dump_file, "node: {title: \"%d_%d\" info1: \"", src_cuid, src_uid);
603 print_rtl_single (dump_file, g->nodes[src_cuid].insn);
604 fprintf (dump_file, "\"}\n");
605 for (e = g->nodes[src_cuid].out; e; e = e->next_out)
607 int dst_uid = INSN_UID (e->dest->insn);
608 int dst_cuid = e->dest->cuid;
610 /* Give the backarcs a different color. */
611 if (e->distance > 0)
612 fprintf (dump_file, "backedge: {color: red ");
613 else
614 fprintf (dump_file, "edge: { ");
616 fprintf (dump_file, "sourcename: \"%d_%d\" ", src_cuid, src_uid);
617 fprintf (dump_file, "targetname: \"%d_%d\" ", dst_cuid, dst_uid);
618 fprintf (dump_file, "label: \"%d_%d\"}\n", e->latency, e->distance);
621 fprintf (dump_file, "}\n");
624 /* Create an edge and initialize it with given values. */
625 static ddg_edge_ptr
626 create_ddg_edge (ddg_node_ptr src, ddg_node_ptr dest,
627 dep_type t, dep_data_type dt, int l, int d)
629 ddg_edge_ptr e = (ddg_edge_ptr) xmalloc (sizeof (struct ddg_edge));
631 e->src = src;
632 e->dest = dest;
633 e->type = t;
634 e->data_type = dt;
635 e->latency = l;
636 e->distance = d;
637 e->next_in = e->next_out = NULL;
638 e->aux.info = 0;
639 return e;
642 /* Add the given edge to the in/out linked lists of the DDG nodes. */
643 static void
644 add_edge_to_ddg (ddg_ptr g ATTRIBUTE_UNUSED, ddg_edge_ptr e)
646 ddg_node_ptr src = e->src;
647 ddg_node_ptr dest = e->dest;
649 if (!src->successors || !dest->predecessors)
650 abort (); /* Should have allocated the sbitmaps. */
652 SET_BIT (src->successors, dest->cuid);
653 SET_BIT (dest->predecessors, src->cuid);
654 e->next_in = dest->in;
655 dest->in = e;
656 e->next_out = src->out;
657 src->out = e;
662 /* Algorithm for computing the recurrence_length of an scc. We assume at
663 for now that cycles in the data dependence graph contain a single backarc.
664 This simplifies the algorithm, and can be generalized later. */
665 static void
666 set_recurrence_length (ddg_scc_ptr scc, ddg_ptr g)
668 int j;
669 int result = -1;
671 for (j = 0; j < scc->num_backarcs; j++)
673 ddg_edge_ptr backarc = scc->backarcs[j];
674 int length;
675 int distance = backarc->distance;
676 ddg_node_ptr src = backarc->dest;
677 ddg_node_ptr dest = backarc->src;
679 length = longest_simple_path (g, src->cuid, dest->cuid, scc->nodes);
680 if (length < 0 )
682 /* fprintf (stderr, "Backarc not on simple cycle in SCC.\n"); */
683 continue;
685 length += backarc->latency;
686 result = MAX (result, (length / distance));
688 scc->recurrence_length = result;
691 /* Create a new SCC given the set of its nodes. Compute its recurrence_length
692 and mark edges that belong to this scc as IN_SCC. */
693 static ddg_scc_ptr
694 create_scc (ddg_ptr g, sbitmap nodes)
696 ddg_scc_ptr scc;
697 int u;
699 scc = (ddg_scc_ptr) xmalloc (sizeof (struct ddg_scc));
700 scc->backarcs = NULL;
701 scc->num_backarcs = 0;
702 scc->nodes = sbitmap_alloc (g->num_nodes);
703 sbitmap_copy (scc->nodes, nodes);
705 /* Mark the backarcs that belong to this SCC. */
706 EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, u,
708 ddg_edge_ptr e;
709 ddg_node_ptr n = &g->nodes[u];
711 for (e = n->out; e; e = e->next_out)
712 if (TEST_BIT (nodes, e->dest->cuid))
714 e->aux.count = IN_SCC;
715 if (e->distance > 0)
716 add_backarc_to_scc (scc, e);
720 set_recurrence_length (scc, g);
721 return scc;
724 /* Cleans the memory allocation of a given SCC. */
725 static void
726 free_scc (ddg_scc_ptr scc)
728 if (!scc)
729 return;
731 sbitmap_free (scc->nodes);
732 if (scc->num_backarcs > 0)
733 free (scc->backarcs);
734 free (scc);
738 /* Add a given edge known to be a backarc to the given DDG. */
739 static void
740 add_backarc_to_ddg (ddg_ptr g, ddg_edge_ptr e)
742 int size = (g->num_backarcs + 1) * sizeof (ddg_edge_ptr);
744 add_edge_to_ddg (g, e);
745 g->backarcs = (ddg_edge_ptr *) xrealloc (g->backarcs, size);
746 g->backarcs[g->num_backarcs++] = e;
749 /* Add backarc to an SCC. */
750 static void
751 add_backarc_to_scc (ddg_scc_ptr scc, ddg_edge_ptr e)
753 int size = (scc->num_backarcs + 1) * sizeof (ddg_edge_ptr);
755 scc->backarcs = (ddg_edge_ptr *) xrealloc (scc->backarcs, size);
756 scc->backarcs[scc->num_backarcs++] = e;
759 /* Add the given SCC to the DDG. */
760 static void
761 add_scc_to_ddg (ddg_all_sccs_ptr g, ddg_scc_ptr scc)
763 int size = (g->num_sccs + 1) * sizeof (ddg_scc_ptr);
765 g->sccs = (ddg_scc_ptr *) xrealloc (g->sccs, size);
766 g->sccs[g->num_sccs++] = scc;
769 /* Given the instruction INSN return the node that represents it. */
770 ddg_node_ptr
771 get_node_of_insn (ddg_ptr g, rtx insn)
773 int i;
775 for (i = 0; i < g->num_nodes; i++)
776 if (insn == g->nodes[i].insn)
777 return &g->nodes[i];
778 return NULL;
781 /* Given a set OPS of nodes in the DDG, find the set of their successors
782 which are not in OPS, and set their bits in SUCC. Bits corresponding to
783 OPS are cleared from SUCC. Leaves the other bits in SUCC unchanged. */
784 void
785 find_successors (sbitmap succ, ddg_ptr g, sbitmap ops)
787 int i;
789 EXECUTE_IF_SET_IN_SBITMAP (ops, 0, i,
791 const sbitmap node_succ = NODE_SUCCESSORS (&g->nodes[i]);
792 sbitmap_a_or_b (succ, succ, node_succ);
795 /* We want those that are not in ops. */
796 sbitmap_difference (succ, succ, ops);
799 /* Given a set OPS of nodes in the DDG, find the set of their predecessors
800 which are not in OPS, and set their bits in PREDS. Bits corresponding to
801 OPS are cleared from PREDS. Leaves the other bits in PREDS unchanged. */
802 void
803 find_predecessors (sbitmap preds, ddg_ptr g, sbitmap ops)
805 int i;
807 EXECUTE_IF_SET_IN_SBITMAP (ops, 0, i,
809 const sbitmap node_preds = NODE_PREDECESSORS (&g->nodes[i]);
810 sbitmap_a_or_b (preds, preds, node_preds);
813 /* We want those that are not in ops. */
814 sbitmap_difference (preds, preds, ops);
818 /* Compare function to be passed to qsort to order the backarcs in descending
819 recMII order. */
820 static int
821 compare_sccs (const void *s1, const void *s2)
823 int rec_l1 = (*(ddg_scc_ptr *)s1)->recurrence_length;
824 int rec_l2 = (*(ddg_scc_ptr *)s2)->recurrence_length;
825 return ((rec_l2 > rec_l1) - (rec_l2 < rec_l1));
829 /* Order the backarcs in descending recMII order using compare_sccs. */
830 static void
831 order_sccs (ddg_all_sccs_ptr g)
833 qsort (g->sccs, g->num_sccs, sizeof (ddg_scc_ptr),
834 (int (*) (const void *, const void *)) compare_sccs);
837 /* Perform the Strongly Connected Components decomposing algorithm on the
838 DDG and return DDG_ALL_SCCS structure that contains them. */
839 ddg_all_sccs_ptr
840 create_ddg_all_sccs (ddg_ptr g)
842 int i;
843 int num_nodes = g->num_nodes;
844 sbitmap from = sbitmap_alloc (num_nodes);
845 sbitmap to = sbitmap_alloc (num_nodes);
846 sbitmap scc_nodes = sbitmap_alloc (num_nodes);
847 ddg_all_sccs_ptr sccs = (ddg_all_sccs_ptr)
848 xmalloc (sizeof (struct ddg_all_sccs));
850 sccs->ddg = g;
851 sccs->sccs = NULL;
852 sccs->num_sccs = 0;
854 for (i = 0; i < g->num_backarcs; i++)
856 ddg_scc_ptr scc;
857 ddg_edge_ptr backarc = g->backarcs[i];
858 ddg_node_ptr src = backarc->src;
859 ddg_node_ptr dest = backarc->dest;
861 /* If the backarc already belongs to an SCC, continue. */
862 if (backarc->aux.count == IN_SCC)
863 continue;
865 sbitmap_zero (from);
866 sbitmap_zero (to);
867 SET_BIT (from, dest->cuid);
868 SET_BIT (to, src->cuid);
870 if (find_nodes_on_paths (scc_nodes, g, from, to))
872 scc = create_scc (g, scc_nodes);
873 add_scc_to_ddg (sccs, scc);
876 order_sccs (sccs);
877 sbitmap_free (from);
878 sbitmap_free (to);
879 sbitmap_free (scc_nodes);
880 return sccs;
883 /* Frees the memory allocated for all SCCs of the DDG, but keeps the DDG. */
884 void
885 free_ddg_all_sccs (ddg_all_sccs_ptr all_sccs)
887 int i;
889 if (!all_sccs)
890 return;
892 for (i = 0; i < all_sccs->num_sccs; i++)
893 free_scc (all_sccs->sccs[i]);
895 free (all_sccs);
899 /* Given FROM - a bitmap of source nodes - and TO - a bitmap of destination
900 nodes - find all nodes that lie on paths from FROM to TO (not excluding
901 nodes from FROM and TO). Return non zero if nodes exist. */
903 find_nodes_on_paths (sbitmap result, ddg_ptr g, sbitmap from, sbitmap to)
905 int answer;
906 int change, u;
907 int num_nodes = g->num_nodes;
908 sbitmap workset = sbitmap_alloc (num_nodes);
909 sbitmap reachable_from = sbitmap_alloc (num_nodes);
910 sbitmap reach_to = sbitmap_alloc (num_nodes);
911 sbitmap tmp = sbitmap_alloc (num_nodes);
913 sbitmap_copy (reachable_from, from);
914 sbitmap_copy (tmp, from);
916 change = 1;
917 while (change)
919 change = 0;
920 sbitmap_copy (workset, tmp);
921 sbitmap_zero (tmp);
922 EXECUTE_IF_SET_IN_SBITMAP (workset, 0, u,
924 ddg_edge_ptr e;
925 ddg_node_ptr u_node = &g->nodes[u];
927 for (e = u_node->out; e != (ddg_edge_ptr) 0; e = e->next_out)
929 ddg_node_ptr v_node = e->dest;
930 int v = v_node->cuid;
932 if (!TEST_BIT (reachable_from, v))
934 SET_BIT (reachable_from, v);
935 SET_BIT (tmp, v);
936 change = 1;
942 sbitmap_copy (reach_to, to);
943 sbitmap_copy (tmp, to);
945 change = 1;
946 while (change)
948 change = 0;
949 sbitmap_copy (workset, tmp);
950 sbitmap_zero (tmp);
951 EXECUTE_IF_SET_IN_SBITMAP (workset, 0, u,
953 ddg_edge_ptr e;
954 ddg_node_ptr u_node = &g->nodes[u];
956 for (e = u_node->in; e != (ddg_edge_ptr) 0; e = e->next_in)
958 ddg_node_ptr v_node = e->src;
959 int v = v_node->cuid;
961 if (!TEST_BIT (reach_to, v))
963 SET_BIT (reach_to, v);
964 SET_BIT (tmp, v);
965 change = 1;
971 answer = sbitmap_a_and_b_cg (result, reachable_from, reach_to);
972 sbitmap_free (workset);
973 sbitmap_free (reachable_from);
974 sbitmap_free (reach_to);
975 sbitmap_free (tmp);
976 return answer;
980 /* Updates the counts of U_NODE's successors (that belong to NODES) to be
981 at-least as large as the count of U_NODE plus the latency between them.
982 Sets a bit in TMP for each successor whose count was changed (increased).
983 Returns nonzero if any count was changed. */
984 static int
985 update_dist_to_successors (ddg_node_ptr u_node, sbitmap nodes, sbitmap tmp)
987 ddg_edge_ptr e;
988 int result = 0;
990 for (e = u_node->out; e; e = e->next_out)
992 ddg_node_ptr v_node = e->dest;
993 int v = v_node->cuid;
995 if (TEST_BIT (nodes, v)
996 && (e->distance == 0)
997 && (v_node->aux.count < u_node->aux.count + e->latency))
999 v_node->aux.count = u_node->aux.count + e->latency;
1000 SET_BIT (tmp, v);
1001 result = 1;
1004 return result;
1008 /* Find the length of a longest path from SRC to DEST in G,
1009 going only through NODES, and disregarding backarcs. */
1011 longest_simple_path (struct ddg * g, int src, int dest, sbitmap nodes)
1013 int i, u;
1014 int change = 1;
1015 int result;
1016 int num_nodes = g->num_nodes;
1017 sbitmap workset = sbitmap_alloc (num_nodes);
1018 sbitmap tmp = sbitmap_alloc (num_nodes);
1021 /* Data will hold the distance of the longest path found so far from
1022 src to each node. Initialize to -1 = less than minimum. */
1023 for (i = 0; i < g->num_nodes; i++)
1024 g->nodes[i].aux.count = -1;
1025 g->nodes[src].aux.count = 0;
1027 sbitmap_zero (tmp);
1028 SET_BIT (tmp, src);
1030 while (change)
1032 change = 0;
1033 sbitmap_copy (workset, tmp);
1034 sbitmap_zero (tmp);
1035 EXECUTE_IF_SET_IN_SBITMAP (workset, 0, u,
1037 ddg_node_ptr u_node = &g->nodes[u];
1039 change |= update_dist_to_successors (u_node, nodes, tmp);
1042 result = g->nodes[dest].aux.count;
1043 sbitmap_free (workset);
1044 sbitmap_free (tmp);
1045 return result;