OSDN Git Service

14b18745823752615eeeb264eaf23121f3f83f59
[pf3gnuchains/gcc-fork.git] / gcc / ddg.c
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>
5
6 This file is part of GCC.
7
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.
12
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.
17
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/>.  */
21
22
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"
46
47 #ifdef INSN_SCHEDULING
48
49 /* A flag indicating that a ddg edge belongs to an SCC or not.  */
50 enum edge_flag {NOT_IN_SCC = 0, IN_SCC};
51
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);
63 \f
64 /* Auxiliary variable for mem_read_insn_p/mem_write_insn_p.  */
65 static bool mem_ref_p;
66
67 /* Auxiliary function for mem_read_insn_p.  */
68 static int
69 mark_mem_use (rtx *x, void *data ATTRIBUTE_UNUSED)
70 {
71   if (MEM_P (*x))
72     mem_ref_p = true;
73   return 0;
74 }
75
76 /* Auxiliary function for mem_read_insn_p.  */
77 static void
78 mark_mem_use_1 (rtx *x, void *data)
79 {
80   for_each_rtx (x, mark_mem_use, data);
81 }
82
83 /* Returns nonzero if INSN reads from memory.  */
84 static bool
85 mem_read_insn_p (rtx insn)
86 {
87   mem_ref_p = false;
88   note_uses (&PATTERN (insn), mark_mem_use_1, NULL);
89   return mem_ref_p;
90 }
91
92 static void
93 mark_mem_store (rtx loc, const_rtx setter ATTRIBUTE_UNUSED, void *data ATTRIBUTE_UNUSED)
94 {
95   if (MEM_P (loc))
96     mem_ref_p = true;
97 }
98
99 /* Returns nonzero if INSN writes to memory.  */
100 static bool
101 mem_write_insn_p (rtx insn)
102 {
103   mem_ref_p = false;
104   note_stores (PATTERN (insn), mark_mem_store, NULL);
105   return mem_ref_p;
106 }
107
108 /* Returns nonzero if X has access to memory.  */
109 static bool
110 rtx_mem_access_p (rtx x)
111 {
112   int i, j;
113   const char *fmt;
114   enum rtx_code code;
115
116   if (x == 0)
117     return false;
118
119   if (MEM_P (x))
120     return true;
121
122   code = GET_CODE (x);
123   fmt = GET_RTX_FORMAT (code);
124   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
125     {
126       if (fmt[i] == 'e')
127         {
128           if (rtx_mem_access_p (XEXP (x, i)))
129             return true;
130         }
131       else if (fmt[i] == 'E')
132         for (j = 0; j < XVECLEN (x, i); j++)
133           {
134             if (rtx_mem_access_p (XVECEXP (x, i, j)))
135               return true;
136           }
137     }
138   return false;
139 }
140
141 /* Returns nonzero if INSN reads to or writes from memory.  */
142 static bool
143 mem_access_insn_p (rtx insn)
144 {
145   return rtx_mem_access_p (PATTERN (insn));
146 }
147
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)
153 {
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);
162
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;
168
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))
177     {
178       rtx set;
179
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)))
184         {
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);
188
189           first_def = df_bb_regno_first_def_find (g->bb, regno);
190           gcc_assert (first_def);
191
192           if (bitmap_bit_p (bb_info->gen, first_def->id))
193             return;
194         }
195     }
196
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);
200 }
201
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)
206 {
207   ddg_edge_ptr e;
208   int l;
209   enum reg_note dep_kind;
210   struct _dep _dep, *dep = &_dep;
211
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
217     {
218       gcc_assert (d_t == TRUE_DEP);
219
220       dep_kind = REG_DEP_TRUE;
221     }
222
223   init_dep (dep, from->insn, to->insn, dep_kind);
224
225   l = dep_cost (dep);
226
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);
232 }
233
234
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)
243 {
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);
254
255   gcc_assert (last_def_node);
256   gcc_assert (first_def);
257
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
262
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)
265     {
266       rtx use_insn = DF_REF_INSN (r_use->ref);
267
268       if (BLOCK_FOR_INSN (use_insn) != g->bb)
269         continue;
270
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)
276         {
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);
282         }
283       else
284         {
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                                                           first_def->insn);
293
294           gcc_assert (first_def_node);
295
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);
300
301         }
302     }
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)
311     {
312       ddg_node_ptr dest_node;
313
314       if (last_def->id == first_def->id)
315         return;
316
317       dest_node = get_node_of_insn (g, first_def->insn);
318       gcc_assert (dest_node);
319       create_ddg_dep_no_link (g, last_def_node, dest_node,
320                               OUTPUT_DEP, REG_DEP, 1);
321     }
322 }
323 /* Build inter-loop dependencies, by looking at DF analysis backwards.  */
324 static void
325 build_inter_loop_deps (ddg_ptr g)
326 {
327   unsigned rd_num;
328   struct df_rd_bb_info *rd_bb_info;
329   bitmap_iterator bi;
330
331   rd_bb_info = DF_RD_BB_INFO (g->bb);
332
333   /* Find inter-loop register output, true and anti deps.  */
334   EXECUTE_IF_SET_IN_BITMAP (rd_bb_info->gen, 0, rd_num, bi)
335   {
336     struct df_ref *rd = DF_DEFS_GET (rd_num);
337
338     add_cross_iteration_register_deps (g, rd);
339   }
340 }
341
342
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)
347 {
348   if (mem_write_insn_p (from->insn))
349     {
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);
354     }
355   else
356     {
357       if (mem_read_insn_p (to->insn))
358         return;
359       else if (from->cuid != to->cuid)
360         {
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);
363         }
364     }
365
366 }
367
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)
372 {
373   int i;
374   /* Hold the dependency analysis state during dependency calculations.  */
375   struct deps tmp_deps;
376   rtx head, tail;
377
378   /* Build the dependence information, using the sched_analyze function.  */
379   init_deps_global ();
380   init_deps (&tmp_deps);
381
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);
385
386   /* Build intra-loop data dependencies using the scheduler dependency
387      analysis.  */
388   for (i = 0; i < g->num_nodes; i++)
389     {
390       ddg_node_ptr dest_node = &g->nodes[i];
391       sd_iterator_def sd_it;
392       dep_t dep;
393
394       if (! INSN_P (dest_node->insn))
395         continue;
396
397       FOR_EACH_DEP (dest_node->insn, SD_LIST_BACK, sd_it, dep)
398         {
399           ddg_node_ptr src_node = get_node_of_insn (g, DEP_PRO (dep));
400
401           if (!src_node)
402             continue;
403
404           create_ddg_dep_from_intra_loop_link (g, src_node, dest_node, dep);
405         }
406
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))
410         {
411           int j;
412
413           for (j = 0; j <= i; j++)
414             {
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);
421             }
422         }
423     }
424
425   /* Free the INSN_LISTs.  */
426   finish_deps_global ();
427   free_deps (&tmp_deps);
428
429   /* Free dependencies.  */
430   sched_free_deps (head, tail, false);
431 }
432
433
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)
439 {
440   ddg_ptr g;
441   rtx insn, first_note;
442   int i;
443   int num_nodes = 0;
444
445   g = (ddg_ptr) xcalloc (1, sizeof (struct ddg));
446
447   g->bb = bb;
448   g->closing_branch_deps = closing_branch_deps;
449
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))
453     {
454       if (! INSN_P (insn) || GET_CODE (PATTERN (insn)) == USE)
455         continue;
456
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++;
462     }
463
464   /* There is nothing to do for this BB.  */
465   if (num_nodes <= 1)
466     {
467       free (g);
468       return NULL;
469     }
470
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))
479     {
480       if (! INSN_P (insn))
481         {
482           if (! first_note && NOTE_P (insn)
483               && NOTE_KIND (insn) !=  NOTE_INSN_BASIC_BLOCK)
484             first_note = insn;
485           continue;
486         }
487       if (JUMP_P (insn))
488         {
489           gcc_assert (!g->closing_branch);
490           g->closing_branch = &g->nodes[i];
491         }
492       else if (GET_CODE (PATTERN (insn)) == USE)
493         {
494           if (! first_note)
495             first_note = insn;
496           continue;
497         }
498
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;
507     }
508   
509   /* We must have found a branch in DDG.  */
510   gcc_assert (g->closing_branch);
511   
512
513   /* Build the data dependency graph.  */
514   build_intra_loop_deps (g);
515   build_inter_loop_deps (g);
516   return g;
517 }
518
519 /* Free all the memory allocated for the DDG.  */
520 void
521 free_ddg (ddg_ptr g)
522 {
523   int i;
524
525   if (!g)
526     return;
527
528   for (i = 0; i < g->num_nodes; i++)
529     {
530       ddg_edge_ptr e = g->nodes[i].out;
531
532       while (e)
533         {
534           ddg_edge_ptr next = e->next_out;
535
536           free (e);
537           e = next;
538         }
539       sbitmap_free (g->nodes[i].successors);
540       sbitmap_free (g->nodes[i].predecessors);
541     }
542   if (g->num_backarcs > 0)
543     free (g->backarcs);
544   free (g->nodes);
545   free (g);
546 }
547
548 void
549 print_ddg_edge (FILE *file, ddg_edge_ptr e)
550 {
551   char dep_c;
552
553   switch (e->type)
554     {
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';
563     }
564
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));
567 }
568
569 /* Print the DDG nodes with there in/out edges to the dump file.  */
570 void
571 print_ddg (FILE *file, ddg_ptr g)
572 {
573   int i;
574
575   for (i = 0; i < g->num_nodes; i++)
576     {
577       ddg_edge_ptr e;
578
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);
584
585       fprintf (file, "\nIN ARCS: ");
586       for (e = g->nodes[i].in; e; e = e->next_in)
587         print_ddg_edge (file, e);
588
589       fprintf (file, "\n");
590     }
591 }
592
593 /* Print the given DDG in VCG format.  */
594 void
595 vcg_print_ddg (FILE *file, ddg_ptr g)
596 {
597   int src_cuid;
598
599   fprintf (file, "graph: {\n");
600   for (src_cuid = 0; src_cuid < g->num_nodes; src_cuid++)
601     {
602       ddg_edge_ptr e;
603       int src_uid = INSN_UID (g->nodes[src_cuid].insn);
604
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)
609         {
610           int dst_uid = INSN_UID (e->dest->insn);
611           int dst_cuid = e->dest->cuid;
612
613           /* Give the backarcs a different color.  */
614           if (e->distance > 0)
615             fprintf (file, "backedge: {color: red ");
616           else
617             fprintf (file, "edge: { ");
618
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);
622         }
623     }
624   fprintf (file, "}\n");
625 }
626
627 /* Dump the sccs in SCCS.  */
628 void
629 print_sccs (FILE *file, ddg_all_sccs_ptr sccs, ddg_ptr g)
630 {
631   unsigned int u = 0;
632   sbitmap_iterator sbi;
633   int i;
634
635   if (!file)
636     return;
637
638   fprintf (file, "\n;; Number of SCC nodes - %d\n", sccs->num_sccs);
639   for (i = 0; i < sccs->num_sccs; i++)
640     {
641       fprintf (file, "SCC number: %d\n", i);
642       EXECUTE_IF_SET_IN_SBITMAP (sccs->sccs[i]->nodes, 0, u, sbi)
643       {
644         fprintf (file, "insn num %d\n", u);
645         print_rtl_single (file, g->nodes[u].insn);
646       }
647     }
648   fprintf (file, "\n");
649 }
650
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)
655 {
656   ddg_edge_ptr e = (ddg_edge_ptr) xmalloc (sizeof (struct ddg_edge));
657
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;
667 }
668
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)
672 {
673   ddg_node_ptr src = e->src;
674   ddg_node_ptr dest = e->dest;
675
676   /* Should have allocated the sbitmaps.  */
677   gcc_assert (src->successors && dest->predecessors);
678
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;
685 }
686
687
688 \f
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)
694 {
695   int j;
696   int result = -1;
697
698   for (j = 0; j < scc->num_backarcs; j++)
699     {
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;
705
706       length = longest_simple_path (g, src->cuid, dest->cuid, scc->nodes);
707       if (length < 0 )
708         {
709           /* fprintf (stderr, "Backarc not on simple cycle in SCC.\n"); */
710           continue;
711         }
712       length += backarc->latency;
713       result = MAX (result, (length / distance));
714     }
715   scc->recurrence_length = result;
716 }
717
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)
722 {
723   ddg_scc_ptr scc;
724   unsigned int u = 0;
725   sbitmap_iterator sbi;
726
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);
732
733   /* Mark the backarcs that belong to this SCC.  */
734   EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, u, sbi)
735     {
736       ddg_edge_ptr e;
737       ddg_node_ptr n = &g->nodes[u];
738
739       for (e = n->out; e; e = e->next_out)
740         if (TEST_BIT (nodes, e->dest->cuid))
741           {
742             e->aux.count = IN_SCC;
743             if (e->distance > 0)
744               add_backarc_to_scc (scc, e);
745           }
746     }
747
748   set_recurrence_length (scc, g);
749   return scc;
750 }
751
752 /* Cleans the memory allocation of a given SCC.  */
753 static void
754 free_scc (ddg_scc_ptr scc)
755 {
756   if (!scc)
757     return;
758
759   sbitmap_free (scc->nodes);
760   if (scc->num_backarcs > 0)
761     free (scc->backarcs);
762   free (scc);
763 }
764
765
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)
769 {
770   int size = (g->num_backarcs + 1) * sizeof (ddg_edge_ptr);
771
772   add_edge_to_ddg (g, e);
773   g->backarcs = (ddg_edge_ptr *) xrealloc (g->backarcs, size);
774   g->backarcs[g->num_backarcs++] = e;
775 }
776
777 /* Add backarc to an SCC.  */
778 static void
779 add_backarc_to_scc (ddg_scc_ptr scc, ddg_edge_ptr e)
780 {
781   int size = (scc->num_backarcs + 1) * sizeof (ddg_edge_ptr);
782
783   scc->backarcs = (ddg_edge_ptr *) xrealloc (scc->backarcs, size);
784   scc->backarcs[scc->num_backarcs++] = e;
785 }
786
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)
790 {
791   int size = (g->num_sccs + 1) * sizeof (ddg_scc_ptr);
792
793   g->sccs = (ddg_scc_ptr *) xrealloc (g->sccs, size);
794   g->sccs[g->num_sccs++] = scc;
795 }
796
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)
800 {
801   int i;
802
803   for (i = 0; i < g->num_nodes; i++)
804     if (insn == g->nodes[i].insn)
805       return &g->nodes[i];
806   return NULL;
807 }
808
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)
814 {
815   unsigned int i = 0;
816   sbitmap_iterator sbi;
817
818   EXECUTE_IF_SET_IN_SBITMAP (ops, 0, i, sbi)
819     {
820       const sbitmap node_succ = NODE_SUCCESSORS (&g->nodes[i]);
821       sbitmap_a_or_b (succ, succ, node_succ);
822     };
823
824   /* We want those that are not in ops.  */
825   sbitmap_difference (succ, succ, ops);
826 }
827
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)
833 {
834   unsigned int i = 0;
835   sbitmap_iterator sbi;
836
837   EXECUTE_IF_SET_IN_SBITMAP (ops, 0, i, sbi)
838     {
839       const sbitmap node_preds = NODE_PREDECESSORS (&g->nodes[i]);
840       sbitmap_a_or_b (preds, preds, node_preds);
841     };
842
843   /* We want those that are not in ops.  */
844   sbitmap_difference (preds, preds, ops);
845 }
846
847
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)
852 {
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));
856           
857 }
858
859 /* Order the backarcs in descending recMII order using compare_sccs.  */
860 static void
861 order_sccs (ddg_all_sccs_ptr g)
862 {
863   qsort (g->sccs, g->num_sccs, sizeof (ddg_scc_ptr),
864          (int (*) (const void *, const void *)) compare_sccs);
865 }
866
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)
872 {
873   int i = 0;
874   sbitmap tmp = sbitmap_alloc (num_nodes);
875
876   sbitmap_zero (tmp);
877   for (i = 0; i < sccs->num_sccs; i++)
878     {
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);
884     }
885   sbitmap_free (tmp);
886 }
887 #endif
888
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)
893 {
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));
901
902   sccs->ddg = g;
903   sccs->sccs = NULL;
904   sccs->num_sccs = 0;
905
906   for (i = 0; i < g->num_backarcs; i++)
907     {
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;
912
913       /* If the backarc already belongs to an SCC, continue.  */
914       if (backarc->aux.count == IN_SCC)
915         continue;
916
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);
922
923       if (find_nodes_on_paths (scc_nodes, g, from, to))
924         {
925           scc = create_scc (g, scc_nodes);
926           add_scc_to_ddg (sccs, scc);
927         }
928     }
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;
937 }
938
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)
942 {
943   int i;
944
945   if (!all_sccs)
946     return;
947
948   for (i = 0; i < all_sccs->num_sccs; i++)
949     free_scc (all_sccs->sccs[i]);
950
951   free (all_sccs);
952 }
953
954 \f
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.  */
958 int
959 find_nodes_on_paths (sbitmap result, ddg_ptr g, sbitmap from, sbitmap to)
960 {
961   int answer;
962   int change;
963   unsigned int u = 0;
964   int num_nodes = g->num_nodes;
965   sbitmap_iterator sbi;
966
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);
971
972   sbitmap_copy (reachable_from, from);
973   sbitmap_copy (tmp, from);
974
975   change = 1;
976   while (change)
977     {
978       change = 0;
979       sbitmap_copy (workset, tmp);
980       sbitmap_zero (tmp);
981       EXECUTE_IF_SET_IN_SBITMAP (workset, 0, u, sbi)
982         {
983           ddg_edge_ptr e;
984           ddg_node_ptr u_node = &g->nodes[u];
985
986           for (e = u_node->out; e != (ddg_edge_ptr) 0; e = e->next_out)
987             {
988               ddg_node_ptr v_node = e->dest;
989               int v = v_node->cuid;
990
991               if (!TEST_BIT (reachable_from, v))
992                 {
993                   SET_BIT (reachable_from, v);
994                   SET_BIT (tmp, v);
995                   change = 1;
996                 }
997             }
998         }
999     }
1000
1001   sbitmap_copy (reach_to, to);
1002   sbitmap_copy (tmp, to);
1003
1004   change = 1;
1005   while (change)
1006     {
1007       change = 0;
1008       sbitmap_copy (workset, tmp);
1009       sbitmap_zero (tmp);
1010       EXECUTE_IF_SET_IN_SBITMAP (workset, 0, u, sbi)
1011         {
1012           ddg_edge_ptr e;
1013           ddg_node_ptr u_node = &g->nodes[u];
1014
1015           for (e = u_node->in; e != (ddg_edge_ptr) 0; e = e->next_in)
1016             {
1017               ddg_node_ptr v_node = e->src;
1018               int v = v_node->cuid;
1019
1020               if (!TEST_BIT (reach_to, v))
1021                 {
1022                   SET_BIT (reach_to, v);
1023                   SET_BIT (tmp, v);
1024                   change = 1;
1025                 }
1026             }
1027         }
1028     }
1029
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;
1036 }
1037
1038
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)
1045 {
1046   ddg_edge_ptr e;
1047   int result = 0;
1048
1049   for (e = u_node->out; e; e = e->next_out)
1050     {
1051       ddg_node_ptr v_node = e->dest;
1052       int v = v_node->cuid;
1053
1054       if (TEST_BIT (nodes, v)
1055           && (e->distance == 0)
1056           && (v_node->aux.count < u_node->aux.count + e->latency))
1057         {
1058           v_node->aux.count = u_node->aux.count + e->latency;
1059           SET_BIT (tmp, v);
1060           result = 1;
1061         }
1062     }
1063   return result;
1064 }
1065
1066
1067 /* Find the length of a longest path from SRC to DEST in G,
1068    going only through NODES, and disregarding backarcs.  */
1069 int
1070 longest_simple_path (struct ddg * g, int src, int dest, sbitmap nodes)
1071 {
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);
1079
1080
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;
1086
1087   sbitmap_zero (tmp);
1088   SET_BIT (tmp, src);
1089
1090   while (change)
1091     {
1092       sbitmap_iterator sbi;
1093
1094       change = 0;
1095       sbitmap_copy (workset, tmp);
1096       sbitmap_zero (tmp);
1097       EXECUTE_IF_SET_IN_SBITMAP (workset, 0, u, sbi)
1098         {
1099           ddg_node_ptr u_node = &g->nodes[u];
1100
1101           change |= update_dist_to_successors (u_node, nodes, tmp);
1102         }
1103     }
1104   result = g->nodes[dest].aux.count;
1105   sbitmap_free (workset);
1106   sbitmap_free (tmp);
1107   return result;
1108 }
1109
1110 #endif /* INSN_SCHEDULING */