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