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