binutils221: Fix missing section start/end label generation
[dragonfly.git] / contrib / gcc-4.4 / gcc / ddg.c
1 /* DDG - Data Dependence Graph implementation.
2    Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009
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           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, DF_REF_ID (first_def)))
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, 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   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 (DF_REF_ID (last_def) != DF_REF_ID (first_def))
260     gcc_assert (!bitmap_bit_p (bb_info->gen, DF_REF_ID (first_def)));
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                                                           DF_REF_INSN (first_def));
293
294           gcc_assert (first_def_node);
295
296           if (DF_REF_ID (last_def) != DF_REF_ID (first_def)
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 (DF_REF_ID (last_def) == DF_REF_ID (first_def))
315         return;
316
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);
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     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 (!insn_alias_sets_conflict_p (from->insn, to->insn))
349     /* Do not create edge if memory references have disjoint alias sets.  */
350     return;
351     
352   if (mem_write_insn_p (from->insn))
353     {
354       if (mem_read_insn_p (to->insn))
355         create_ddg_dep_no_link (g, from, to, TRUE_DEP, MEM_DEP, 1);
356       else if (from->cuid != to->cuid)
357         create_ddg_dep_no_link (g, from, to, OUTPUT_DEP, MEM_DEP, 1);
358     }
359   else
360     {
361       if (mem_read_insn_p (to->insn))
362         return;
363       else if (from->cuid != to->cuid)
364         {
365           create_ddg_dep_no_link (g, from, to, ANTI_DEP, MEM_DEP, 1);
366           create_ddg_dep_no_link (g, to, from, TRUE_DEP, MEM_DEP, 1);
367         }
368     }
369
370 }
371
372 /* Perform intra-block Data Dependency analysis and connect the nodes in
373    the DDG.  We assume the loop has a single basic block.  */
374 static void
375 build_intra_loop_deps (ddg_ptr g)
376 {
377   int i;
378   /* Hold the dependency analysis state during dependency calculations.  */
379   struct deps tmp_deps;
380   rtx head, tail;
381
382   /* Build the dependence information, using the sched_analyze function.  */
383   init_deps_global ();
384   init_deps (&tmp_deps);
385
386   /* Do the intra-block data dependence analysis for the given block.  */
387   get_ebb_head_tail (g->bb, g->bb, &head, &tail);
388   sched_analyze (&tmp_deps, head, tail);
389
390   /* Build intra-loop data dependencies using the scheduler dependency
391      analysis.  */
392   for (i = 0; i < g->num_nodes; i++)
393     {
394       ddg_node_ptr dest_node = &g->nodes[i];
395       sd_iterator_def sd_it;
396       dep_t dep;
397
398       if (! INSN_P (dest_node->insn))
399         continue;
400
401       FOR_EACH_DEP (dest_node->insn, SD_LIST_BACK, sd_it, dep)
402         {
403           ddg_node_ptr src_node = get_node_of_insn (g, DEP_PRO (dep));
404
405           if (!src_node)
406             continue;
407
408           create_ddg_dep_from_intra_loop_link (g, src_node, dest_node, dep);
409         }
410
411       /* If this insn modifies memory, add an edge to all insns that access
412          memory.  */
413       if (mem_access_insn_p (dest_node->insn))
414         {
415           int j;
416
417           for (j = 0; j <= i; j++)
418             {
419               ddg_node_ptr j_node = &g->nodes[j];
420               if (mem_access_insn_p (j_node->insn))
421                 /* Don't bother calculating inter-loop dep if an intra-loop dep
422                    already exists.  */
423                   if (! TEST_BIT (dest_node->successors, j))
424                     add_inter_loop_mem_dep (g, dest_node, j_node);
425             }
426         }
427     }
428
429   /* Free the INSN_LISTs.  */
430   finish_deps_global ();
431   free_deps (&tmp_deps);
432
433   /* Free dependencies.  */
434   sched_free_deps (head, tail, false);
435 }
436
437
438 /* Given a basic block, create its DDG and return a pointer to a variable
439    of ddg type that represents it.
440    Initialize the ddg structure fields to the appropriate values.  */
441 ddg_ptr
442 create_ddg (basic_block bb, int closing_branch_deps)
443 {
444   ddg_ptr g;
445   rtx insn, first_note;
446   int i;
447   int num_nodes = 0;
448
449   g = (ddg_ptr) xcalloc (1, sizeof (struct ddg));
450
451   g->bb = bb;
452   g->closing_branch_deps = closing_branch_deps;
453
454   /* Count the number of insns in the BB.  */
455   for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb));
456        insn = NEXT_INSN (insn))
457     {
458       if (! INSN_P (insn) || GET_CODE (PATTERN (insn)) == USE)
459         continue;
460
461       if (mem_read_insn_p (insn))
462         g->num_loads++;
463       if (mem_write_insn_p (insn))
464         g->num_stores++;
465       num_nodes++;
466     }
467
468   /* There is nothing to do for this BB.  */
469   if (num_nodes <= 1)
470     {
471       free (g);
472       return NULL;
473     }
474
475   /* Allocate the nodes array, and initialize the nodes.  */
476   g->num_nodes = num_nodes;
477   g->nodes = (ddg_node_ptr) xcalloc (num_nodes, sizeof (struct ddg_node));
478   g->closing_branch = NULL;
479   i = 0;
480   first_note = NULL_RTX;
481   for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb));
482        insn = NEXT_INSN (insn))
483     {
484       if (! INSN_P (insn))
485         {
486           if (! first_note && NOTE_P (insn)
487               && NOTE_KIND (insn) !=  NOTE_INSN_BASIC_BLOCK)
488             first_note = insn;
489           continue;
490         }
491       if (JUMP_P (insn))
492         {
493           gcc_assert (!g->closing_branch);
494           g->closing_branch = &g->nodes[i];
495         }
496       else if (GET_CODE (PATTERN (insn)) == USE)
497         {
498           if (! first_note)
499             first_note = insn;
500           continue;
501         }
502
503       g->nodes[i].cuid = i;
504       g->nodes[i].successors = sbitmap_alloc (num_nodes);
505       sbitmap_zero (g->nodes[i].successors);
506       g->nodes[i].predecessors = sbitmap_alloc (num_nodes);
507       sbitmap_zero (g->nodes[i].predecessors);
508       g->nodes[i].first_note = (first_note ? first_note : insn);
509       g->nodes[i++].insn = insn;
510       first_note = NULL_RTX;
511     }
512   
513   /* We must have found a branch in DDG.  */
514   gcc_assert (g->closing_branch);
515   
516
517   /* Build the data dependency graph.  */
518   build_intra_loop_deps (g);
519   build_inter_loop_deps (g);
520   return g;
521 }
522
523 /* Free all the memory allocated for the DDG.  */
524 void
525 free_ddg (ddg_ptr g)
526 {
527   int i;
528
529   if (!g)
530     return;
531
532   for (i = 0; i < g->num_nodes; i++)
533     {
534       ddg_edge_ptr e = g->nodes[i].out;
535
536       while (e)
537         {
538           ddg_edge_ptr next = e->next_out;
539
540           free (e);
541           e = next;
542         }
543       sbitmap_free (g->nodes[i].successors);
544       sbitmap_free (g->nodes[i].predecessors);
545     }
546   if (g->num_backarcs > 0)
547     free (g->backarcs);
548   free (g->nodes);
549   free (g);
550 }
551
552 void
553 print_ddg_edge (FILE *file, ddg_edge_ptr e)
554 {
555   char dep_c;
556
557   switch (e->type)
558     {
559     case OUTPUT_DEP :
560       dep_c = 'O';
561       break;
562     case ANTI_DEP :
563       dep_c = 'A';
564       break;
565     default:
566       dep_c = 'T';
567     }
568
569   fprintf (file, " [%d -(%c,%d,%d)-> %d] ", INSN_UID (e->src->insn),
570            dep_c, e->latency, e->distance, INSN_UID (e->dest->insn));
571 }
572
573 /* Print the DDG nodes with there in/out edges to the dump file.  */
574 void
575 print_ddg (FILE *file, ddg_ptr g)
576 {
577   int i;
578
579   for (i = 0; i < g->num_nodes; i++)
580     {
581       ddg_edge_ptr e;
582
583       fprintf (file, "Node num: %d\n", g->nodes[i].cuid);
584       print_rtl_single (file, g->nodes[i].insn);
585       fprintf (file, "OUT ARCS: ");
586       for (e = g->nodes[i].out; e; e = e->next_out)
587         print_ddg_edge (file, e);
588
589       fprintf (file, "\nIN ARCS: ");
590       for (e = g->nodes[i].in; e; e = e->next_in)
591         print_ddg_edge (file, e);
592
593       fprintf (file, "\n");
594     }
595 }
596
597 /* Print the given DDG in VCG format.  */
598 void
599 vcg_print_ddg (FILE *file, ddg_ptr g)
600 {
601   int src_cuid;
602
603   fprintf (file, "graph: {\n");
604   for (src_cuid = 0; src_cuid < g->num_nodes; src_cuid++)
605     {
606       ddg_edge_ptr e;
607       int src_uid = INSN_UID (g->nodes[src_cuid].insn);
608
609       fprintf (file, "node: {title: \"%d_%d\" info1: \"", src_cuid, src_uid);
610       print_rtl_single (file, g->nodes[src_cuid].insn);
611       fprintf (file, "\"}\n");
612       for (e = g->nodes[src_cuid].out; e; e = e->next_out)
613         {
614           int dst_uid = INSN_UID (e->dest->insn);
615           int dst_cuid = e->dest->cuid;
616
617           /* Give the backarcs a different color.  */
618           if (e->distance > 0)
619             fprintf (file, "backedge: {color: red ");
620           else
621             fprintf (file, "edge: { ");
622
623           fprintf (file, "sourcename: \"%d_%d\" ", src_cuid, src_uid);
624           fprintf (file, "targetname: \"%d_%d\" ", dst_cuid, dst_uid);
625           fprintf (file, "label: \"%d_%d\"}\n", e->latency, e->distance);
626         }
627     }
628   fprintf (file, "}\n");
629 }
630
631 /* Dump the sccs in SCCS.  */
632 void
633 print_sccs (FILE *file, ddg_all_sccs_ptr sccs, ddg_ptr g)
634 {
635   unsigned int u = 0;
636   sbitmap_iterator sbi;
637   int i;
638
639   if (!file)
640     return;
641
642   fprintf (file, "\n;; Number of SCC nodes - %d\n", sccs->num_sccs);
643   for (i = 0; i < sccs->num_sccs; i++)
644     {
645       fprintf (file, "SCC number: %d\n", i);
646       EXECUTE_IF_SET_IN_SBITMAP (sccs->sccs[i]->nodes, 0, u, sbi)
647       {
648         fprintf (file, "insn num %d\n", u);
649         print_rtl_single (file, g->nodes[u].insn);
650       }
651     }
652   fprintf (file, "\n");
653 }
654
655 /* Create an edge and initialize it with given values.  */
656 static ddg_edge_ptr
657 create_ddg_edge (ddg_node_ptr src, ddg_node_ptr dest,
658                  dep_type t, dep_data_type dt, int l, int d)
659 {
660   ddg_edge_ptr e = (ddg_edge_ptr) xmalloc (sizeof (struct ddg_edge));
661
662   e->src = src;
663   e->dest = dest;
664   e->type = t;
665   e->data_type = dt;
666   e->latency = l;
667   e->distance = d;
668   e->next_in = e->next_out = NULL;
669   e->aux.info = 0;
670   return e;
671 }
672
673 /* Add the given edge to the in/out linked lists of the DDG nodes.  */
674 static void
675 add_edge_to_ddg (ddg_ptr g ATTRIBUTE_UNUSED, ddg_edge_ptr e)
676 {
677   ddg_node_ptr src = e->src;
678   ddg_node_ptr dest = e->dest;
679
680   /* Should have allocated the sbitmaps.  */
681   gcc_assert (src->successors && dest->predecessors);
682
683   SET_BIT (src->successors, dest->cuid);
684   SET_BIT (dest->predecessors, src->cuid);
685   e->next_in = dest->in;
686   dest->in = e;
687   e->next_out = src->out;
688   src->out = e;
689 }
690
691
692 \f
693 /* Algorithm for computing the recurrence_length of an scc.  We assume at
694    for now that cycles in the data dependence graph contain a single backarc.
695    This simplifies the algorithm, and can be generalized later.  */
696 static void
697 set_recurrence_length (ddg_scc_ptr scc, ddg_ptr g)
698 {
699   int j;
700   int result = -1;
701
702   for (j = 0; j < scc->num_backarcs; j++)
703     {
704       ddg_edge_ptr backarc = scc->backarcs[j];
705       int length;
706       int distance = backarc->distance;
707       ddg_node_ptr src = backarc->dest;
708       ddg_node_ptr dest = backarc->src;
709
710       length = longest_simple_path (g, src->cuid, dest->cuid, scc->nodes);
711       if (length < 0 )
712         {
713           /* fprintf (stderr, "Backarc not on simple cycle in SCC.\n"); */
714           continue;
715         }
716       length += backarc->latency;
717       result = MAX (result, (length / distance));
718     }
719   scc->recurrence_length = result;
720 }
721
722 /* Create a new SCC given the set of its nodes.  Compute its recurrence_length
723    and mark edges that belong to this scc as IN_SCC.  */
724 static ddg_scc_ptr
725 create_scc (ddg_ptr g, sbitmap nodes)
726 {
727   ddg_scc_ptr scc;
728   unsigned int u = 0;
729   sbitmap_iterator sbi;
730
731   scc = (ddg_scc_ptr) xmalloc (sizeof (struct ddg_scc));
732   scc->backarcs = NULL;
733   scc->num_backarcs = 0;
734   scc->nodes = sbitmap_alloc (g->num_nodes);
735   sbitmap_copy (scc->nodes, nodes);
736
737   /* Mark the backarcs that belong to this SCC.  */
738   EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, u, sbi)
739     {
740       ddg_edge_ptr e;
741       ddg_node_ptr n = &g->nodes[u];
742
743       for (e = n->out; e; e = e->next_out)
744         if (TEST_BIT (nodes, e->dest->cuid))
745           {
746             e->aux.count = IN_SCC;
747             if (e->distance > 0)
748               add_backarc_to_scc (scc, e);
749           }
750     }
751
752   set_recurrence_length (scc, g);
753   return scc;
754 }
755
756 /* Cleans the memory allocation of a given SCC.  */
757 static void
758 free_scc (ddg_scc_ptr scc)
759 {
760   if (!scc)
761     return;
762
763   sbitmap_free (scc->nodes);
764   if (scc->num_backarcs > 0)
765     free (scc->backarcs);
766   free (scc);
767 }
768
769
770 /* Add a given edge known to be a backarc to the given DDG.  */
771 static void
772 add_backarc_to_ddg (ddg_ptr g, ddg_edge_ptr e)
773 {
774   int size = (g->num_backarcs + 1) * sizeof (ddg_edge_ptr);
775
776   add_edge_to_ddg (g, e);
777   g->backarcs = (ddg_edge_ptr *) xrealloc (g->backarcs, size);
778   g->backarcs[g->num_backarcs++] = e;
779 }
780
781 /* Add backarc to an SCC.  */
782 static void
783 add_backarc_to_scc (ddg_scc_ptr scc, ddg_edge_ptr e)
784 {
785   int size = (scc->num_backarcs + 1) * sizeof (ddg_edge_ptr);
786
787   scc->backarcs = (ddg_edge_ptr *) xrealloc (scc->backarcs, size);
788   scc->backarcs[scc->num_backarcs++] = e;
789 }
790
791 /* Add the given SCC to the DDG.  */
792 static void
793 add_scc_to_ddg (ddg_all_sccs_ptr g, ddg_scc_ptr scc)
794 {
795   int size = (g->num_sccs + 1) * sizeof (ddg_scc_ptr);
796
797   g->sccs = (ddg_scc_ptr *) xrealloc (g->sccs, size);
798   g->sccs[g->num_sccs++] = scc;
799 }
800
801 /* Given the instruction INSN return the node that represents it.  */
802 ddg_node_ptr
803 get_node_of_insn (ddg_ptr g, rtx insn)
804 {
805   int i;
806
807   for (i = 0; i < g->num_nodes; i++)
808     if (insn == g->nodes[i].insn)
809       return &g->nodes[i];
810   return NULL;
811 }
812
813 /* Given a set OPS of nodes in the DDG, find the set of their successors
814    which are not in OPS, and set their bits in SUCC.  Bits corresponding to
815    OPS are cleared from SUCC.  Leaves the other bits in SUCC unchanged.  */
816 void
817 find_successors (sbitmap succ, ddg_ptr g, sbitmap ops)
818 {
819   unsigned int i = 0;
820   sbitmap_iterator sbi;
821
822   EXECUTE_IF_SET_IN_SBITMAP (ops, 0, i, sbi)
823     {
824       const sbitmap node_succ = NODE_SUCCESSORS (&g->nodes[i]);
825       sbitmap_a_or_b (succ, succ, node_succ);
826     };
827
828   /* We want those that are not in ops.  */
829   sbitmap_difference (succ, succ, ops);
830 }
831
832 /* Given a set OPS of nodes in the DDG, find the set of their predecessors
833    which are not in OPS, and set their bits in PREDS.  Bits corresponding to
834    OPS are cleared from PREDS.  Leaves the other bits in PREDS unchanged.  */
835 void
836 find_predecessors (sbitmap preds, ddg_ptr g, sbitmap ops)
837 {
838   unsigned int i = 0;
839   sbitmap_iterator sbi;
840
841   EXECUTE_IF_SET_IN_SBITMAP (ops, 0, i, sbi)
842     {
843       const sbitmap node_preds = NODE_PREDECESSORS (&g->nodes[i]);
844       sbitmap_a_or_b (preds, preds, node_preds);
845     };
846
847   /* We want those that are not in ops.  */
848   sbitmap_difference (preds, preds, ops);
849 }
850
851
852 /* Compare function to be passed to qsort to order the backarcs in descending
853    recMII order.  */
854 static int
855 compare_sccs (const void *s1, const void *s2)
856 {
857   const int rec_l1 = (*(const ddg_scc_ptr *)s1)->recurrence_length;
858   const int rec_l2 = (*(const ddg_scc_ptr *)s2)->recurrence_length; 
859   return ((rec_l2 > rec_l1) - (rec_l2 < rec_l1));
860           
861 }
862
863 /* Order the backarcs in descending recMII order using compare_sccs.  */
864 static void
865 order_sccs (ddg_all_sccs_ptr g)
866 {
867   qsort (g->sccs, g->num_sccs, sizeof (ddg_scc_ptr),
868          (int (*) (const void *, const void *)) compare_sccs);
869 }
870
871 #ifdef ENABLE_CHECKING
872 /* Check that every node in SCCS belongs to exactly one strongly connected
873    component and that no element of SCCS is empty.  */
874 static void
875 check_sccs (ddg_all_sccs_ptr sccs, int num_nodes)
876 {
877   int i = 0;
878   sbitmap tmp = sbitmap_alloc (num_nodes);
879
880   sbitmap_zero (tmp);
881   for (i = 0; i < sccs->num_sccs; i++)
882     {
883       gcc_assert (!sbitmap_empty_p (sccs->sccs[i]->nodes));
884       /* Verify that every node in sccs is in exactly one strongly
885          connected component.  */
886       gcc_assert (!sbitmap_any_common_bits (tmp, sccs->sccs[i]->nodes));
887       sbitmap_a_or_b (tmp, tmp, sccs->sccs[i]->nodes);
888     }
889   sbitmap_free (tmp);
890 }
891 #endif
892
893 /* Perform the Strongly Connected Components decomposing algorithm on the
894    DDG and return DDG_ALL_SCCS structure that contains them.  */
895 ddg_all_sccs_ptr
896 create_ddg_all_sccs (ddg_ptr g)
897 {
898   int i;
899   int num_nodes = g->num_nodes;
900   sbitmap from = sbitmap_alloc (num_nodes);
901   sbitmap to = sbitmap_alloc (num_nodes);
902   sbitmap scc_nodes = sbitmap_alloc (num_nodes);
903   ddg_all_sccs_ptr sccs = (ddg_all_sccs_ptr)
904                           xmalloc (sizeof (struct ddg_all_sccs));
905
906   sccs->ddg = g;
907   sccs->sccs = NULL;
908   sccs->num_sccs = 0;
909
910   for (i = 0; i < g->num_backarcs; i++)
911     {
912       ddg_scc_ptr  scc;
913       ddg_edge_ptr backarc = g->backarcs[i];
914       ddg_node_ptr src = backarc->src;
915       ddg_node_ptr dest = backarc->dest;
916
917       /* If the backarc already belongs to an SCC, continue.  */
918       if (backarc->aux.count == IN_SCC)
919         continue;
920
921       sbitmap_zero (scc_nodes);
922       sbitmap_zero (from);
923       sbitmap_zero (to);
924       SET_BIT (from, dest->cuid);
925       SET_BIT (to, src->cuid);
926
927       if (find_nodes_on_paths (scc_nodes, g, from, to))
928         {
929           scc = create_scc (g, scc_nodes);
930           add_scc_to_ddg (sccs, scc);
931         }
932     }
933   order_sccs (sccs);
934   sbitmap_free (from);
935   sbitmap_free (to);
936   sbitmap_free (scc_nodes);
937 #ifdef ENABLE_CHECKING
938   check_sccs (sccs, num_nodes);
939 #endif
940   return sccs;
941 }
942
943 /* Frees the memory allocated for all SCCs of the DDG, but keeps the DDG.  */
944 void
945 free_ddg_all_sccs (ddg_all_sccs_ptr all_sccs)
946 {
947   int i;
948
949   if (!all_sccs)
950     return;
951
952   for (i = 0; i < all_sccs->num_sccs; i++)
953     free_scc (all_sccs->sccs[i]);
954
955   free (all_sccs);
956 }
957
958 \f
959 /* Given FROM - a bitmap of source nodes - and TO - a bitmap of destination
960    nodes - find all nodes that lie on paths from FROM to TO (not excluding
961    nodes from FROM and TO).  Return nonzero if nodes exist.  */
962 int
963 find_nodes_on_paths (sbitmap result, ddg_ptr g, sbitmap from, sbitmap to)
964 {
965   int answer;
966   int change;
967   unsigned int u = 0;
968   int num_nodes = g->num_nodes;
969   sbitmap_iterator sbi;
970
971   sbitmap workset = sbitmap_alloc (num_nodes);
972   sbitmap reachable_from = sbitmap_alloc (num_nodes);
973   sbitmap reach_to = sbitmap_alloc (num_nodes);
974   sbitmap tmp = sbitmap_alloc (num_nodes);
975
976   sbitmap_copy (reachable_from, from);
977   sbitmap_copy (tmp, from);
978
979   change = 1;
980   while (change)
981     {
982       change = 0;
983       sbitmap_copy (workset, tmp);
984       sbitmap_zero (tmp);
985       EXECUTE_IF_SET_IN_SBITMAP (workset, 0, u, sbi)
986         {
987           ddg_edge_ptr e;
988           ddg_node_ptr u_node = &g->nodes[u];
989
990           for (e = u_node->out; e != (ddg_edge_ptr) 0; e = e->next_out)
991             {
992               ddg_node_ptr v_node = e->dest;
993               int v = v_node->cuid;
994
995               if (!TEST_BIT (reachable_from, v))
996                 {
997                   SET_BIT (reachable_from, v);
998                   SET_BIT (tmp, v);
999                   change = 1;
1000                 }
1001             }
1002         }
1003     }
1004
1005   sbitmap_copy (reach_to, to);
1006   sbitmap_copy (tmp, to);
1007
1008   change = 1;
1009   while (change)
1010     {
1011       change = 0;
1012       sbitmap_copy (workset, tmp);
1013       sbitmap_zero (tmp);
1014       EXECUTE_IF_SET_IN_SBITMAP (workset, 0, u, sbi)
1015         {
1016           ddg_edge_ptr e;
1017           ddg_node_ptr u_node = &g->nodes[u];
1018
1019           for (e = u_node->in; e != (ddg_edge_ptr) 0; e = e->next_in)
1020             {
1021               ddg_node_ptr v_node = e->src;
1022               int v = v_node->cuid;
1023
1024               if (!TEST_BIT (reach_to, v))
1025                 {
1026                   SET_BIT (reach_to, v);
1027                   SET_BIT (tmp, v);
1028                   change = 1;
1029                 }
1030             }
1031         }
1032     }
1033
1034   answer = sbitmap_a_and_b_cg (result, reachable_from, reach_to);
1035   sbitmap_free (workset);
1036   sbitmap_free (reachable_from);
1037   sbitmap_free (reach_to);
1038   sbitmap_free (tmp);
1039   return answer;
1040 }
1041
1042
1043 /* Updates the counts of U_NODE's successors (that belong to NODES) to be
1044    at-least as large as the count of U_NODE plus the latency between them.
1045    Sets a bit in TMP for each successor whose count was changed (increased).
1046    Returns nonzero if any count was changed.  */
1047 static int
1048 update_dist_to_successors (ddg_node_ptr u_node, sbitmap nodes, sbitmap tmp)
1049 {
1050   ddg_edge_ptr e;
1051   int result = 0;
1052
1053   for (e = u_node->out; e; e = e->next_out)
1054     {
1055       ddg_node_ptr v_node = e->dest;
1056       int v = v_node->cuid;
1057
1058       if (TEST_BIT (nodes, v)
1059           && (e->distance == 0)
1060           && (v_node->aux.count < u_node->aux.count + e->latency))
1061         {
1062           v_node->aux.count = u_node->aux.count + e->latency;
1063           SET_BIT (tmp, v);
1064           result = 1;
1065         }
1066     }
1067   return result;
1068 }
1069
1070
1071 /* Find the length of a longest path from SRC to DEST in G,
1072    going only through NODES, and disregarding backarcs.  */
1073 int
1074 longest_simple_path (struct ddg * g, int src, int dest, sbitmap nodes)
1075 {
1076   int i;
1077   unsigned int u = 0;
1078   int change = 1;
1079   int result;
1080   int num_nodes = g->num_nodes;
1081   sbitmap workset = sbitmap_alloc (num_nodes);
1082   sbitmap tmp = sbitmap_alloc (num_nodes);
1083
1084
1085   /* Data will hold the distance of the longest path found so far from
1086      src to each node.  Initialize to -1 = less than minimum.  */
1087   for (i = 0; i < g->num_nodes; i++)
1088     g->nodes[i].aux.count = -1;
1089   g->nodes[src].aux.count = 0;
1090
1091   sbitmap_zero (tmp);
1092   SET_BIT (tmp, src);
1093
1094   while (change)
1095     {
1096       sbitmap_iterator sbi;
1097
1098       change = 0;
1099       sbitmap_copy (workset, tmp);
1100       sbitmap_zero (tmp);
1101       EXECUTE_IF_SET_IN_SBITMAP (workset, 0, u, sbi)
1102         {
1103           ddg_node_ptr u_node = &g->nodes[u];
1104
1105           change |= update_dist_to_successors (u_node, nodes, tmp);
1106         }
1107     }
1108   result = g->nodes[dest].aux.count;
1109   sbitmap_free (workset);
1110   sbitmap_free (tmp);
1111   return result;
1112 }
1113
1114 #endif /* INSN_SCHEDULING */