xref: /netbsd-src/external/gpl3/gcc.old/dist/gcc/graphite-scop-detection.c (revision b7b7574d3bf8eeb51a1fa3977b59142ec6434a55)
1 /* Detection of Static Control Parts (SCoP) for Graphite.
2    Copyright (C) 2009, 2010 Free Software Foundation, Inc.
3    Contributed by Sebastian Pop <sebastian.pop@amd.com> and
4    Tobias Grosser <grosser@fim.uni-passau.de>.
5 
6 This file is part of GCC.
7 
8 GCC is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 3, or (at your option)
11 any later version.
12 
13 GCC is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16 GNU General Public License 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 #include "config.h"
23 #include "system.h"
24 #include "coretypes.h"
25 #include "tm.h"
26 #include "ggc.h"
27 #include "tree.h"
28 #include "rtl.h"
29 #include "basic-block.h"
30 #include "diagnostic.h"
31 #include "tree-flow.h"
32 #include "toplev.h"
33 #include "tree-dump.h"
34 #include "timevar.h"
35 #include "cfgloop.h"
36 #include "tree-chrec.h"
37 #include "tree-data-ref.h"
38 #include "tree-scalar-evolution.h"
39 #include "tree-pass.h"
40 #include "domwalk.h"
41 #include "value-prof.h"
42 #include "pointer-set.h"
43 #include "gimple.h"
44 #include "sese.h"
45 
46 #ifdef HAVE_cloog
47 #include "cloog/cloog.h"
48 #include "ppl_c.h"
49 #include "graphite-ppl.h"
50 #include "graphite.h"
51 #include "graphite-poly.h"
52 #include "graphite-scop-detection.h"
53 
54 /* The type of the analyzed basic block.  */
55 
56 typedef enum gbb_type {
57   GBB_UNKNOWN,
58   GBB_LOOP_SING_EXIT_HEADER,
59   GBB_LOOP_MULT_EXIT_HEADER,
60   GBB_LOOP_EXIT,
61   GBB_COND_HEADER,
62   GBB_SIMPLE,
63   GBB_LAST
64 } gbb_type;
65 
66 /* Detect the type of BB.  Loop headers are only marked, if they are
67    new.  This means their loop_father is different to LAST_LOOP.
68    Otherwise they are treated like any other bb and their type can be
69    any other type.  */
70 
71 static gbb_type
72 get_bb_type (basic_block bb, struct loop *last_loop)
73 {
74   VEC (basic_block, heap) *dom;
75   int nb_dom, nb_suc;
76   struct loop *loop = bb->loop_father;
77 
78   /* Check, if we entry into a new loop. */
79   if (loop != last_loop)
80     {
81       if (single_exit (loop) != NULL)
82         return GBB_LOOP_SING_EXIT_HEADER;
83       else if (loop->num != 0)
84         return GBB_LOOP_MULT_EXIT_HEADER;
85       else
86 	return GBB_COND_HEADER;
87     }
88 
89   dom = get_dominated_by (CDI_DOMINATORS, bb);
90   nb_dom = VEC_length (basic_block, dom);
91   VEC_free (basic_block, heap, dom);
92 
93   if (nb_dom == 0)
94     return GBB_LAST;
95 
96   nb_suc = VEC_length (edge, bb->succs);
97 
98   if (nb_dom == 1 && nb_suc == 1)
99     return GBB_SIMPLE;
100 
101   return GBB_COND_HEADER;
102 }
103 
104 /* A SCoP detection region, defined using bbs as borders.
105 
106    All control flow touching this region, comes in passing basic_block
107    ENTRY and leaves passing basic_block EXIT.  By using bbs instead of
108    edges for the borders we are able to represent also regions that do
109    not have a single entry or exit edge.
110 
111    But as they have a single entry basic_block and a single exit
112    basic_block, we are able to generate for every sd_region a single
113    entry and exit edge.
114 
115    1   2
116     \ /
117      3	<- entry
118      |
119      4
120     / \			This region contains: {3, 4, 5, 6, 7, 8}
121    5   6
122    |   |
123    7   8
124     \ /
125      9	<- exit  */
126 
127 
128 typedef struct sd_region_p
129 {
130   /* The entry bb dominates all bbs in the sd_region.  It is part of
131      the region.  */
132   basic_block entry;
133 
134   /* The exit bb postdominates all bbs in the sd_region, but is not
135      part of the region.  */
136   basic_block exit;
137 } sd_region;
138 
139 DEF_VEC_O(sd_region);
140 DEF_VEC_ALLOC_O(sd_region, heap);
141 
142 
143 /* Moves the scops from SOURCE to TARGET and clean up SOURCE.  */
144 
145 static void
146 move_sd_regions (VEC (sd_region, heap) **source,
147 		 VEC (sd_region, heap) **target)
148 {
149   sd_region *s;
150   int i;
151 
152   for (i = 0; VEC_iterate (sd_region, *source, i, s); i++)
153     VEC_safe_push (sd_region, heap, *target, s);
154 
155   VEC_free (sd_region, heap, *source);
156 }
157 
158 /* Something like "n * m" is not allowed.  */
159 
160 static bool
161 graphite_can_represent_init (tree e)
162 {
163   switch (TREE_CODE (e))
164     {
165     case POLYNOMIAL_CHREC:
166       return graphite_can_represent_init (CHREC_LEFT (e))
167 	&& graphite_can_represent_init (CHREC_RIGHT (e));
168 
169     case MULT_EXPR:
170       if (chrec_contains_symbols (TREE_OPERAND (e, 0)))
171 	return graphite_can_represent_init (TREE_OPERAND (e, 0))
172 	  && host_integerp (TREE_OPERAND (e, 1), 0);
173       else
174 	return graphite_can_represent_init (TREE_OPERAND (e, 1))
175 	  && host_integerp (TREE_OPERAND (e, 0), 0);
176 
177     case PLUS_EXPR:
178     case POINTER_PLUS_EXPR:
179     case MINUS_EXPR:
180       return graphite_can_represent_init (TREE_OPERAND (e, 0))
181 	&& graphite_can_represent_init (TREE_OPERAND (e, 1));
182 
183     case NEGATE_EXPR:
184     case BIT_NOT_EXPR:
185     CASE_CONVERT:
186     case NON_LVALUE_EXPR:
187       return graphite_can_represent_init (TREE_OPERAND (e, 0));
188 
189    default:
190      break;
191     }
192 
193   return true;
194 }
195 
196 /* Return true when SCEV can be represented in the polyhedral model.
197 
198    An expression can be represented, if it can be expressed as an
199    affine expression.  For loops (i, j) and parameters (m, n) all
200    affine expressions are of the form:
201 
202    x1 * i + x2 * j + x3 * m + x4 * n + x5 * 1 where x1..x5 element of Z
203 
204    1 i + 20 j + (-2) m + 25
205 
206    Something like "i * n" or "n * m" is not allowed.
207 
208    OUTERMOST_LOOP defines the outermost loop that can variate.  */
209 
210 static bool
211 graphite_can_represent_scev (tree scev, int outermost_loop)
212 {
213   if (chrec_contains_undetermined (scev))
214     return false;
215 
216   switch (TREE_CODE (scev))
217     {
218     case PLUS_EXPR:
219     case MINUS_EXPR:
220       return graphite_can_represent_scev (TREE_OPERAND (scev, 0), outermost_loop)
221 	&& graphite_can_represent_scev (TREE_OPERAND (scev, 1), outermost_loop);
222 
223     case MULT_EXPR:
224       return !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev, 0)))
225 	&& !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev, 1)))
226 	&& !(chrec_contains_symbols (TREE_OPERAND (scev, 0))
227 	     && chrec_contains_symbols (TREE_OPERAND (scev, 1)))
228 	&& graphite_can_represent_init (scev)
229 	&& graphite_can_represent_scev (TREE_OPERAND (scev, 0), outermost_loop)
230 	&& graphite_can_represent_scev (TREE_OPERAND (scev, 1), outermost_loop);
231 
232     case POLYNOMIAL_CHREC:
233       /* Check for constant strides.  With a non constant stride of
234 	 'n' we would have a value of 'iv * n'.  Also check that the
235 	 initial value can represented: for example 'n * m' cannot be
236 	 represented.  */
237       if (!evolution_function_right_is_integer_cst (scev)
238 	  || !graphite_can_represent_init (scev))
239 	return false;
240 
241     default:
242       break;
243     }
244 
245   /* Only affine functions can be represented.  */
246   if (!scev_is_linear_expression (scev))
247     return false;
248 
249   return evolution_function_is_invariant_p (scev, outermost_loop)
250     || evolution_function_is_affine_multivariate_p (scev, outermost_loop);
251 }
252 
253 
254 /* Return true when EXPR can be represented in the polyhedral model.
255 
256    This means an expression can be represented, if it is linear with
257    respect to the loops and the strides are non parametric.
258    LOOP is the place where the expr will be evaluated and OUTERMOST_LOOP
259    defindes the outermost loop that can variate.  SCOP_ENTRY defines the
260    entry of the region we analyse.  */
261 
262 static bool
263 graphite_can_represent_expr (basic_block scop_entry, loop_p loop,
264 			     loop_p outermost_loop, tree expr)
265 {
266   tree scev = analyze_scalar_evolution (loop, expr);
267 
268   scev = instantiate_scev (scop_entry, loop, scev);
269 
270   return graphite_can_represent_scev (scev, outermost_loop->num);
271 }
272 
273 /* Return true if the data references of STMT can be represented by
274    Graphite.  */
275 
276 static bool
277 stmt_has_simple_data_refs_p (loop_p outermost_loop, gimple stmt)
278 {
279   data_reference_p dr;
280   unsigned i;
281   int j;
282   bool res = true;
283   int loop = outermost_loop->num;
284   VEC (data_reference_p, heap) *drs = VEC_alloc (data_reference_p, heap, 5);
285 
286   graphite_find_data_references_in_stmt (outermost_loop, stmt, &drs);
287 
288   for (j = 0; VEC_iterate (data_reference_p, drs, j, dr); j++)
289     for (i = 0; i < DR_NUM_DIMENSIONS (dr); i++)
290       if (!graphite_can_represent_scev (DR_ACCESS_FN (dr, i), loop))
291 	{
292 	  res = false;
293 	  goto done;
294 	}
295 
296  done:
297   free_data_refs (drs);
298   return res;
299 }
300 
301 /* Return true only when STMT is simple enough for being handled by
302    Graphite.  This depends on SCOP_ENTRY, as the parameters are
303    initialized relatively to this basic block, the linear functions
304    are initialized to OUTERMOST_LOOP and BB is the place where we try
305    to evaluate the STMT.  */
306 
307 static bool
308 stmt_simple_for_scop_p (basic_block scop_entry, loop_p outermost_loop,
309 			gimple stmt, basic_block bb)
310 {
311   loop_p loop = bb->loop_father;
312 
313   gcc_assert (scop_entry);
314 
315   /* GIMPLE_ASM and GIMPLE_CALL may embed arbitrary side effects.
316      Calls have side-effects, except those to const or pure
317      functions.  */
318   if (gimple_has_volatile_ops (stmt)
319       || (gimple_code (stmt) == GIMPLE_CALL
320 	  && !(gimple_call_flags (stmt) & (ECF_CONST | ECF_PURE)))
321       || (gimple_code (stmt) == GIMPLE_ASM))
322     return false;
323 
324   if (is_gimple_debug (stmt))
325     return true;
326 
327   if (!stmt_has_simple_data_refs_p (outermost_loop, stmt))
328     return false;
329 
330   switch (gimple_code (stmt))
331     {
332     case GIMPLE_RETURN:
333     case GIMPLE_LABEL:
334       return true;
335 
336     case GIMPLE_COND:
337       {
338 	tree op;
339 	ssa_op_iter op_iter;
340         enum tree_code code = gimple_cond_code (stmt);
341 
342 	/* We can handle all binary comparisons.  Inequalities are
343 	   also supported as they can be represented with union of
344 	   polyhedra.  */
345         if (!(code == LT_EXPR
346 	      || code == GT_EXPR
347 	      || code == LE_EXPR
348 	      || code == GE_EXPR
349 	      || code == EQ_EXPR
350 	      || code == NE_EXPR))
351           return false;
352 
353 	FOR_EACH_SSA_TREE_OPERAND (op, stmt, op_iter, SSA_OP_ALL_USES)
354 	  if (!graphite_can_represent_expr (scop_entry, loop, outermost_loop,
355 					    op)
356 	      /* We can not handle REAL_TYPE. Failed for pr39260.  */
357 	      || TREE_CODE (TREE_TYPE (op)) == REAL_TYPE)
358 	    return false;
359 
360 	return true;
361       }
362 
363     case GIMPLE_ASSIGN:
364     case GIMPLE_CALL:
365       return true;
366 
367     default:
368       /* These nodes cut a new scope.  */
369       return false;
370     }
371 
372   return false;
373 }
374 
375 /* Returns the statement of BB that contains a harmful operation: that
376    can be a function call with side effects, the induction variables
377    are not linear with respect to SCOP_ENTRY, etc.  The current open
378    scop should end before this statement.  The evaluation is limited using
379    OUTERMOST_LOOP as outermost loop that may change.  */
380 
381 static gimple
382 harmful_stmt_in_bb (basic_block scop_entry, loop_p outer_loop, basic_block bb)
383 {
384   gimple_stmt_iterator gsi;
385 
386   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
387     if (!stmt_simple_for_scop_p (scop_entry, outer_loop, gsi_stmt (gsi), bb))
388       return gsi_stmt (gsi);
389 
390   return NULL;
391 }
392 
393 /* Return true when it is not possible to represent LOOP in the
394    polyhedral representation.  This is evaluated taking SCOP_ENTRY and
395    OUTERMOST_LOOP in mind.  */
396 
397 static bool
398 graphite_can_represent_loop (basic_block scop_entry, loop_p outermost_loop,
399 			     loop_p loop)
400 {
401   tree niter = number_of_latch_executions (loop);
402 
403   /* Number of iterations unknown.  */
404   if (chrec_contains_undetermined (niter))
405     return false;
406 
407   /* Number of iterations not affine.  */
408   if (!graphite_can_represent_expr (scop_entry, loop, outermost_loop, niter))
409     return false;
410 
411   return true;
412 }
413 
414 /* Store information needed by scopdet_* functions.  */
415 
416 struct scopdet_info
417 {
418   /* Exit of the open scop would stop if the current BB is harmful.  */
419   basic_block exit;
420 
421   /* Where the next scop would start if the current BB is harmful.  */
422   basic_block next;
423 
424   /* The bb or one of its children contains open loop exits.  That means
425      loop exit nodes that are not surrounded by a loop dominated by bb.  */
426   bool exits;
427 
428   /* The bb or one of its children contains only structures we can handle.  */
429   bool difficult;
430 };
431 
432 static struct scopdet_info build_scops_1 (basic_block, loop_p,
433 					  VEC (sd_region, heap) **, loop_p);
434 
435 /* Calculates BB infos. If bb is difficult we add valid SCoPs dominated by BB
436    to SCOPS.  TYPE is the gbb_type of BB.  */
437 
438 static struct scopdet_info
439 scopdet_basic_block_info (basic_block bb, loop_p outermost_loop,
440 			  VEC (sd_region, heap) **scops, gbb_type type)
441 {
442   loop_p loop = bb->loop_father;
443   struct scopdet_info result;
444   gimple stmt;
445 
446   /* XXX: ENTRY_BLOCK_PTR could be optimized in later steps.  */
447   basic_block entry_block = ENTRY_BLOCK_PTR;
448   stmt = harmful_stmt_in_bb (entry_block, outermost_loop, bb);
449   result.difficult = (stmt != NULL);
450   result.exit = NULL;
451 
452   switch (type)
453     {
454     case GBB_LAST:
455       result.next = NULL;
456       result.exits = false;
457 
458       /* Mark bbs terminating a SESE region difficult, if they start
459 	 a condition.  */
460       if (!single_succ_p (bb))
461 	result.difficult = true;
462       else
463 	result.exit = single_succ (bb);
464 
465       break;
466 
467     case GBB_SIMPLE:
468       result.next = single_succ (bb);
469       result.exits = false;
470       result.exit = single_succ (bb);
471       break;
472 
473     case GBB_LOOP_SING_EXIT_HEADER:
474       {
475 	VEC (sd_region, heap) *regions = VEC_alloc (sd_region, heap, 3);
476 	struct scopdet_info sinfo;
477 	edge exit_e = single_exit (loop);
478 
479 	sinfo = build_scops_1 (bb, outermost_loop, &regions, loop);
480 
481 	if (!graphite_can_represent_loop (entry_block, outermost_loop, loop))
482 	  result.difficult = true;
483 
484 	result.difficult |= sinfo.difficult;
485 
486 	/* Try again with another loop level.  */
487 	if (result.difficult
488 	    && loop_depth (outermost_loop) + 1 == loop_depth (loop))
489 	  {
490 	    outermost_loop = loop;
491 
492 	    VEC_free (sd_region, heap, regions);
493 	    regions = VEC_alloc (sd_region, heap, 3);
494 
495 	    sinfo = scopdet_basic_block_info (bb, outermost_loop, scops, type);
496 
497 	    result = sinfo;
498 	    result.difficult = true;
499 
500 	    if (sinfo.difficult)
501 	      move_sd_regions (&regions, scops);
502 	    else
503 	      {
504 		sd_region open_scop;
505 		open_scop.entry = bb;
506 		open_scop.exit = exit_e->dest;
507 		VEC_safe_push (sd_region, heap, *scops, &open_scop);
508 		VEC_free (sd_region, heap, regions);
509 	      }
510 	  }
511 	else
512 	  {
513 	    result.exit = exit_e->dest;
514 	    result.next = exit_e->dest;
515 
516 	    /* If we do not dominate result.next, remove it.  It's either
517 	       the EXIT_BLOCK_PTR, or another bb dominates it and will
518 	       call the scop detection for this bb.  */
519 	    if (!dominated_by_p (CDI_DOMINATORS, result.next, bb))
520 	      result.next = NULL;
521 
522 	    if (exit_e->src->loop_father != loop)
523 	      result.next = NULL;
524 
525 	    result.exits = false;
526 
527 	    if (result.difficult)
528 	      move_sd_regions (&regions, scops);
529 	    else
530 	      VEC_free (sd_region, heap, regions);
531 	  }
532 
533 	break;
534       }
535 
536     case GBB_LOOP_MULT_EXIT_HEADER:
537       {
538         /* XXX: For now we just do not join loops with multiple exits.  If the
539            exits lead to the same bb it may be possible to join the loop.  */
540         VEC (sd_region, heap) *regions = VEC_alloc (sd_region, heap, 3);
541         VEC (edge, heap) *exits = get_loop_exit_edges (loop);
542         edge e;
543         int i;
544 	build_scops_1 (bb, loop, &regions, loop);
545 
546 	/* Scan the code dominated by this loop.  This means all bbs, that are
547 	   are dominated by a bb in this loop, but are not part of this loop.
548 
549 	   The easiest case:
550 	     - The loop exit destination is dominated by the exit sources.
551 
552 	   TODO: We miss here the more complex cases:
553 		  - The exit destinations are dominated by another bb inside
554 		    the loop.
555 		  - The loop dominates bbs, that are not exit destinations.  */
556         for (i = 0; VEC_iterate (edge, exits, i, e); i++)
557           if (e->src->loop_father == loop
558 	      && dominated_by_p (CDI_DOMINATORS, e->dest, e->src))
559 	    {
560 	      if (loop_outer (outermost_loop))
561 		outermost_loop = loop_outer (outermost_loop);
562 
563 	      /* Pass loop_outer to recognize e->dest as loop header in
564 		 build_scops_1.  */
565 	      if (e->dest->loop_father->header == e->dest)
566 		build_scops_1 (e->dest, outermost_loop, &regions,
567 			       loop_outer (e->dest->loop_father));
568 	      else
569 		build_scops_1 (e->dest, outermost_loop, &regions,
570 			       e->dest->loop_father);
571 	    }
572 
573         result.next = NULL;
574         result.exit = NULL;
575         result.difficult = true;
576         result.exits = false;
577         move_sd_regions (&regions, scops);
578         VEC_free (edge, heap, exits);
579         break;
580       }
581     case GBB_COND_HEADER:
582       {
583 	VEC (sd_region, heap) *regions = VEC_alloc (sd_region, heap, 3);
584 	struct scopdet_info sinfo;
585 	VEC (basic_block, heap) *dominated;
586 	int i;
587 	basic_block dom_bb;
588 	basic_block last_exit = NULL;
589 	edge e;
590 	result.exits = false;
591 
592 	/* First check the successors of BB, and check if it is
593 	   possible to join the different branches.  */
594 	for (i = 0; VEC_iterate (edge, bb->succs, i, e); i++)
595 	  {
596 	    /* Ignore loop exits.  They will be handled after the loop
597 	       body.  */
598 	    if (is_loop_exit (loop, e->dest))
599 	      {
600 		result.exits = true;
601 		continue;
602 	      }
603 
604 	    /* Do not follow edges that lead to the end of the
605 	       conditions block.  For example, in
606 
607                |   0
608 	       |  /|\
609 	       | 1 2 |
610 	       | | | |
611 	       | 3 4 |
612 	       |  \|/
613                |   6
614 
615 	       the edge from 0 => 6.  Only check if all paths lead to
616 	       the same node 6.  */
617 
618 	    if (!single_pred_p (e->dest))
619 	      {
620 		/* Check, if edge leads directly to the end of this
621 		   condition.  */
622 		if (!last_exit)
623 		  last_exit = e->dest;
624 
625 		if (e->dest != last_exit)
626 		  result.difficult = true;
627 
628 		continue;
629 	      }
630 
631 	    if (!dominated_by_p (CDI_DOMINATORS, e->dest, bb))
632 	      {
633 		result.difficult = true;
634 		continue;
635 	      }
636 
637 	    sinfo = build_scops_1 (e->dest, outermost_loop, &regions, loop);
638 
639 	    result.exits |= sinfo.exits;
640 	    result.difficult |= sinfo.difficult;
641 
642 	    /* Checks, if all branches end at the same point.
643 	       If that is true, the condition stays joinable.
644 	       Have a look at the example above.  */
645 	    if (sinfo.exit)
646 	      {
647 		if (!last_exit)
648 		  last_exit = sinfo.exit;
649 
650 		if (sinfo.exit != last_exit)
651 		  result.difficult = true;
652 	      }
653 	    else
654 	      result.difficult = true;
655 	  }
656 
657 	if (!last_exit)
658 	  result.difficult = true;
659 
660 	/* Join the branches of the condition if possible.  */
661 	if (!result.exits && !result.difficult)
662 	  {
663 	    /* Only return a next pointer if we dominate this pointer.
664 	       Otherwise it will be handled by the bb dominating it.  */
665 	    if (dominated_by_p (CDI_DOMINATORS, last_exit, bb)
666 		&& last_exit != bb)
667 	      result.next = last_exit;
668 	    else
669 	      result.next = NULL;
670 
671 	    result.exit = last_exit;
672 
673 	    VEC_free (sd_region, heap, regions);
674 	    break;
675 	  }
676 
677 	/* Scan remaining bbs dominated by BB.  */
678 	dominated = get_dominated_by (CDI_DOMINATORS, bb);
679 
680 	for (i = 0; VEC_iterate (basic_block, dominated, i, dom_bb); i++)
681 	  {
682 	    /* Ignore loop exits: they will be handled after the loop body.  */
683 	    if (loop_depth (find_common_loop (loop, dom_bb->loop_father))
684 		< loop_depth (loop))
685 	      {
686 		result.exits = true;
687 		continue;
688 	      }
689 
690 	    /* Ignore the bbs processed above.  */
691 	    if (single_pred_p (dom_bb) && single_pred (dom_bb) == bb)
692 	      continue;
693 
694 	    if (loop_depth (loop) > loop_depth (dom_bb->loop_father))
695 	      sinfo = build_scops_1 (dom_bb, outermost_loop, &regions,
696 				     loop_outer (loop));
697 	    else
698 	      sinfo = build_scops_1 (dom_bb, outermost_loop, &regions, loop);
699 
700 	    result.exits |= sinfo.exits;
701 	    result.difficult = true;
702 	    result.exit = NULL;
703 	  }
704 
705 	VEC_free (basic_block, heap, dominated);
706 
707 	result.next = NULL;
708 	move_sd_regions (&regions, scops);
709 
710 	break;
711       }
712 
713     default:
714       gcc_unreachable ();
715     }
716 
717   return result;
718 }
719 
720 /* Starting from CURRENT we walk the dominance tree and add new sd_regions to
721    SCOPS. The analyse if a sd_region can be handled is based on the value
722    of OUTERMOST_LOOP. Only loops inside OUTERMOST loops may change.  LOOP
723    is the loop in which CURRENT is handled.
724 
725    TODO: These functions got a little bit big. They definitely should be cleaned
726 	 up.  */
727 
728 static struct scopdet_info
729 build_scops_1 (basic_block current, loop_p outermost_loop,
730 	       VEC (sd_region, heap) **scops, loop_p loop)
731 {
732   bool in_scop = false;
733   sd_region open_scop;
734   struct scopdet_info sinfo;
735 
736   /* Initialize result.  */
737   struct scopdet_info result;
738   result.exits = false;
739   result.difficult = false;
740   result.next = NULL;
741   result.exit = NULL;
742   open_scop.entry = NULL;
743   open_scop.exit = NULL;
744   sinfo.exit = NULL;
745 
746   /* Loop over the dominance tree.  If we meet a difficult bb, close
747      the current SCoP.  Loop and condition header start a new layer,
748      and can only be added if all bbs in deeper layers are simple.  */
749   while (current != NULL)
750     {
751       sinfo = scopdet_basic_block_info (current, outermost_loop, scops,
752 					get_bb_type (current, loop));
753 
754       if (!in_scop && !(sinfo.exits || sinfo.difficult))
755         {
756 	  open_scop.entry = current;
757 	  open_scop.exit = NULL;
758           in_scop = true;
759         }
760       else if (in_scop && (sinfo.exits || sinfo.difficult))
761         {
762 	  open_scop.exit = current;
763           VEC_safe_push (sd_region, heap, *scops, &open_scop);
764           in_scop = false;
765         }
766 
767       result.difficult |= sinfo.difficult;
768       result.exits |= sinfo.exits;
769 
770       current = sinfo.next;
771     }
772 
773   /* Try to close open_scop, if we are still in an open SCoP.  */
774   if (in_scop)
775     {
776       open_scop.exit = sinfo.exit;
777       gcc_assert (open_scop.exit);
778       VEC_safe_push (sd_region, heap, *scops, &open_scop);
779     }
780 
781   result.exit = sinfo.exit;
782   return result;
783 }
784 
785 /* Checks if a bb is contained in REGION.  */
786 
787 static bool
788 bb_in_sd_region (basic_block bb, sd_region *region)
789 {
790   return bb_in_region (bb, region->entry, region->exit);
791 }
792 
793 /* Returns the single entry edge of REGION, if it does not exits NULL.  */
794 
795 static edge
796 find_single_entry_edge (sd_region *region)
797 {
798   edge e;
799   edge_iterator ei;
800   edge entry = NULL;
801 
802   FOR_EACH_EDGE (e, ei, region->entry->preds)
803     if (!bb_in_sd_region (e->src, region))
804       {
805 	if (entry)
806 	  {
807 	    entry = NULL;
808 	    break;
809 	  }
810 
811 	else
812 	  entry = e;
813       }
814 
815   return entry;
816 }
817 
818 /* Returns the single exit edge of REGION, if it does not exits NULL.  */
819 
820 static edge
821 find_single_exit_edge (sd_region *region)
822 {
823   edge e;
824   edge_iterator ei;
825   edge exit = NULL;
826 
827   FOR_EACH_EDGE (e, ei, region->exit->preds)
828     if (bb_in_sd_region (e->src, region))
829       {
830 	if (exit)
831 	  {
832 	    exit = NULL;
833 	    break;
834 	  }
835 
836 	else
837 	  exit = e;
838       }
839 
840   return exit;
841 }
842 
843 /* Create a single entry edge for REGION.  */
844 
845 static void
846 create_single_entry_edge (sd_region *region)
847 {
848   if (find_single_entry_edge (region))
849     return;
850 
851   /* There are multiple predecessors for bb_3
852 
853   |  1  2
854   |  | /
855   |  |/
856   |  3	<- entry
857   |  |\
858   |  | |
859   |  4 ^
860   |  | |
861   |  |/
862   |  5
863 
864   There are two edges (1->3, 2->3), that point from outside into the region,
865   and another one (5->3), a loop latch, lead to bb_3.
866 
867   We split bb_3.
868 
869   |  1  2
870   |  | /
871   |  |/
872   |3.0
873   |  |\     (3.0 -> 3.1) = single entry edge
874   |3.1 |  	<- entry
875   |  | |
876   |  | |
877   |  4 ^
878   |  | |
879   |  |/
880   |  5
881 
882   If the loop is part of the SCoP, we have to redirect the loop latches.
883 
884   |  1  2
885   |  | /
886   |  |/
887   |3.0
888   |  |      (3.0 -> 3.1) = entry edge
889   |3.1  	<- entry
890   |  |\
891   |  | |
892   |  4 ^
893   |  | |
894   |  |/
895   |  5  */
896 
897   if (region->entry->loop_father->header != region->entry
898       || dominated_by_p (CDI_DOMINATORS,
899 			 loop_latch_edge (region->entry->loop_father)->src,
900 			 region->exit))
901     {
902       edge forwarder = split_block_after_labels (region->entry);
903       region->entry = forwarder->dest;
904     }
905   else
906     /* This case is never executed, as the loop headers seem always to have a
907        single edge pointing from outside into the loop.  */
908     gcc_unreachable ();
909 
910 #ifdef ENABLE_CHECKING
911   gcc_assert (find_single_entry_edge (region));
912 #endif
913 }
914 
915 /* Check if the sd_region, mentioned in EDGE, has no exit bb.  */
916 
917 static bool
918 sd_region_without_exit (edge e)
919 {
920   sd_region *r = (sd_region *) e->aux;
921 
922   if (r)
923     return r->exit == NULL;
924   else
925     return false;
926 }
927 
928 /* Create a single exit edge for REGION.  */
929 
930 static void
931 create_single_exit_edge (sd_region *region)
932 {
933   edge e;
934   edge_iterator ei;
935   edge forwarder = NULL;
936   basic_block exit;
937 
938   /* We create a forwarder bb (5) for all edges leaving this region
939      (3->5, 4->5).  All other edges leading to the same bb, are moved
940      to a new bb (6).  If these edges where part of another region (2->5)
941      we update the region->exit pointer, of this region.
942 
943      To identify which edge belongs to which region we depend on the e->aux
944      pointer in every edge.  It points to the region of the edge or to NULL,
945      if the edge is not part of any region.
946 
947      1 2 3 4   	1->5 no region, 		2->5 region->exit = 5,
948       \| |/    	3->5 region->exit = NULL, 	4->5 region->exit = NULL
949         5	<- exit
950 
951      changes to
952 
953      1 2 3 4   	1->6 no region, 			2->6 region->exit = 6,
954      | | \/	3->5 no region,				4->5 no region,
955      | |  5
956       \| /	5->6 region->exit = 6
957 	6
958 
959      Now there is only a single exit edge (5->6).  */
960   exit = region->exit;
961   region->exit = NULL;
962   forwarder = make_forwarder_block (exit, &sd_region_without_exit, NULL);
963 
964   /* Unmark the edges, that are no longer exit edges.  */
965   FOR_EACH_EDGE (e, ei, forwarder->src->preds)
966     if (e->aux)
967       e->aux = NULL;
968 
969   /* Mark the new exit edge.  */
970   single_succ_edge (forwarder->src)->aux = region;
971 
972   /* Update the exit bb of all regions, where exit edges lead to
973      forwarder->dest.  */
974   FOR_EACH_EDGE (e, ei, forwarder->dest->preds)
975     if (e->aux)
976       ((sd_region *) e->aux)->exit = forwarder->dest;
977 
978 #ifdef ENABLE_CHECKING
979   gcc_assert (find_single_exit_edge (region));
980 #endif
981 }
982 
983 /* Unmark the exit edges of all REGIONS.
984    See comment in "create_single_exit_edge". */
985 
986 static void
987 unmark_exit_edges (VEC (sd_region, heap) *regions)
988 {
989   int i;
990   sd_region *s;
991   edge e;
992   edge_iterator ei;
993 
994   for (i = 0; VEC_iterate (sd_region, regions, i, s); i++)
995     FOR_EACH_EDGE (e, ei, s->exit->preds)
996       e->aux = NULL;
997 }
998 
999 
1000 /* Mark the exit edges of all REGIONS.
1001    See comment in "create_single_exit_edge". */
1002 
1003 static void
1004 mark_exit_edges (VEC (sd_region, heap) *regions)
1005 {
1006   int i;
1007   sd_region *s;
1008   edge e;
1009   edge_iterator ei;
1010 
1011   for (i = 0; VEC_iterate (sd_region, regions, i, s); i++)
1012     FOR_EACH_EDGE (e, ei, s->exit->preds)
1013       if (bb_in_sd_region (e->src, s))
1014 	e->aux = s;
1015 }
1016 
1017 /* Create for all scop regions a single entry and a single exit edge.  */
1018 
1019 static void
1020 create_sese_edges (VEC (sd_region, heap) *regions)
1021 {
1022   int i;
1023   sd_region *s;
1024 
1025   for (i = 0; VEC_iterate (sd_region, regions, i, s); i++)
1026     create_single_entry_edge (s);
1027 
1028   mark_exit_edges (regions);
1029 
1030   for (i = 0; VEC_iterate (sd_region, regions, i, s); i++)
1031     /* Don't handle multiple edges exiting the function.  */
1032     if (!find_single_exit_edge (s)
1033 	&& s->exit != EXIT_BLOCK_PTR)
1034       create_single_exit_edge (s);
1035 
1036   unmark_exit_edges (regions);
1037 
1038   fix_loop_structure (NULL);
1039 
1040 #ifdef ENABLE_CHECKING
1041   verify_loop_structure ();
1042   verify_dominators (CDI_DOMINATORS);
1043   verify_ssa (false);
1044 #endif
1045 }
1046 
1047 /* Create graphite SCoPs from an array of scop detection REGIONS.  */
1048 
1049 static void
1050 build_graphite_scops (VEC (sd_region, heap) *regions,
1051 		      VEC (scop_p, heap) **scops)
1052 {
1053   int i;
1054   sd_region *s;
1055 
1056   for (i = 0; VEC_iterate (sd_region, regions, i, s); i++)
1057     {
1058       edge entry = find_single_entry_edge (s);
1059       edge exit = find_single_exit_edge (s);
1060       scop_p scop;
1061 
1062       if (!exit)
1063 	continue;
1064 
1065       scop = new_scop (new_sese (entry, exit));
1066       VEC_safe_push (scop_p, heap, *scops, scop);
1067 
1068       /* Are there overlapping SCoPs?  */
1069 #ifdef ENABLE_CHECKING
1070 	{
1071 	  int j;
1072 	  sd_region *s2;
1073 
1074 	  for (j = 0; VEC_iterate (sd_region, regions, j, s2); j++)
1075 	    if (s != s2)
1076 	      gcc_assert (!bb_in_sd_region (s->entry, s2));
1077 	}
1078 #endif
1079     }
1080 }
1081 
1082 /* Returns true when BB contains only close phi nodes.  */
1083 
1084 static bool
1085 contains_only_close_phi_nodes (basic_block bb)
1086 {
1087   gimple_stmt_iterator gsi;
1088 
1089   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1090     if (gimple_code (gsi_stmt (gsi)) != GIMPLE_LABEL)
1091       return false;
1092 
1093   return true;
1094 }
1095 
1096 /* Print statistics for SCOP to FILE.  */
1097 
1098 static void
1099 print_graphite_scop_statistics (FILE* file, scop_p scop)
1100 {
1101   long n_bbs = 0;
1102   long n_loops = 0;
1103   long n_stmts = 0;
1104   long n_conditions = 0;
1105   long n_p_bbs = 0;
1106   long n_p_loops = 0;
1107   long n_p_stmts = 0;
1108   long n_p_conditions = 0;
1109 
1110   basic_block bb;
1111 
1112   FOR_ALL_BB (bb)
1113     {
1114       gimple_stmt_iterator psi;
1115       loop_p loop = bb->loop_father;
1116 
1117       if (!bb_in_sese_p (bb, SCOP_REGION (scop)))
1118 	continue;
1119 
1120       n_bbs++;
1121       n_p_bbs += bb->count;
1122 
1123       if (VEC_length (edge, bb->succs) > 1)
1124 	{
1125 	  n_conditions++;
1126 	  n_p_conditions += bb->count;
1127 	}
1128 
1129       for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi))
1130 	{
1131 	  n_stmts++;
1132 	  n_p_stmts += bb->count;
1133 	}
1134 
1135       if (loop->header == bb && loop_in_sese_p (loop, SCOP_REGION (scop)))
1136 	{
1137 	  n_loops++;
1138 	  n_p_loops += bb->count;
1139 	}
1140 
1141     }
1142 
1143   fprintf (file, "\nBefore limit_scops SCoP statistics (");
1144   fprintf (file, "BBS:%ld, ", n_bbs);
1145   fprintf (file, "LOOPS:%ld, ", n_loops);
1146   fprintf (file, "CONDITIONS:%ld, ", n_conditions);
1147   fprintf (file, "STMTS:%ld)\n", n_stmts);
1148   fprintf (file, "\nBefore limit_scops SCoP profiling statistics (");
1149   fprintf (file, "BBS:%ld, ", n_p_bbs);
1150   fprintf (file, "LOOPS:%ld, ", n_p_loops);
1151   fprintf (file, "CONDITIONS:%ld, ", n_p_conditions);
1152   fprintf (file, "STMTS:%ld)\n", n_p_stmts);
1153 }
1154 
1155 /* Print statistics for SCOPS to FILE.  */
1156 
1157 static void
1158 print_graphite_statistics (FILE* file, VEC (scop_p, heap) *scops)
1159 {
1160   int i;
1161   scop_p scop;
1162 
1163   for (i = 0; VEC_iterate (scop_p, scops, i, scop); i++)
1164     print_graphite_scop_statistics (file, scop);
1165 }
1166 
1167 /* We limit all SCoPs to SCoPs, that are completely surrounded by a loop.
1168 
1169    Example:
1170 
1171    for (i      |
1172      {         |
1173        for (j  |  SCoP 1
1174        for (k  |
1175      }         |
1176 
1177    * SCoP frontier, as this line is not surrounded by any loop. *
1178 
1179    for (l      |  SCoP 2
1180 
1181    This is necessary as scalar evolution and parameter detection need a
1182    outermost loop to initialize parameters correctly.
1183 
1184    TODO: FIX scalar evolution and parameter detection to allow more flexible
1185          SCoP frontiers.  */
1186 
1187 static void
1188 limit_scops (VEC (scop_p, heap) **scops)
1189 {
1190   VEC (sd_region, heap) *regions = VEC_alloc (sd_region, heap, 3);
1191 
1192   int i;
1193   scop_p scop;
1194 
1195   for (i = 0; VEC_iterate (scop_p, *scops, i, scop); i++)
1196     {
1197       int j;
1198       loop_p loop;
1199       sese region = SCOP_REGION (scop);
1200       build_sese_loop_nests (region);
1201 
1202       for (j = 0; VEC_iterate (loop_p, SESE_LOOP_NEST (region), j, loop); j++)
1203         if (!loop_in_sese_p (loop_outer (loop), region)
1204 	    && single_exit (loop))
1205           {
1206 	    sd_region open_scop;
1207 	    open_scop.entry = loop->header;
1208 	    open_scop.exit = single_exit (loop)->dest;
1209 
1210 	    /* This is a hack on top of the limit_scops hack.  The
1211 	       limit_scops hack should disappear all together.  */
1212 	    if (single_succ_p (open_scop.exit)
1213 		&& contains_only_close_phi_nodes (open_scop.exit))
1214 	      open_scop.exit = single_succ_edge (open_scop.exit)->dest;
1215 
1216 	    VEC_safe_push (sd_region, heap, regions, &open_scop);
1217 	  }
1218     }
1219 
1220   free_scops (*scops);
1221   *scops = VEC_alloc (scop_p, heap, 3);
1222 
1223   create_sese_edges (regions);
1224   build_graphite_scops (regions, scops);
1225   VEC_free (sd_region, heap, regions);
1226 }
1227 
1228 /* Transforms LOOP to the canonical loop closed SSA form.  */
1229 
1230 static void
1231 canonicalize_loop_closed_ssa (loop_p loop)
1232 {
1233   edge e = single_exit (loop);
1234   basic_block bb;
1235 
1236   if (!e || e->flags & EDGE_ABNORMAL)
1237     return;
1238 
1239   bb = e->dest;
1240 
1241   if (VEC_length (edge, bb->preds) == 1)
1242     split_block_after_labels (bb);
1243   else
1244     {
1245       gimple_stmt_iterator psi;
1246       basic_block close = split_edge (e);
1247 
1248       e = single_succ_edge (close);
1249 
1250       for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
1251 	{
1252 	  gimple phi = gsi_stmt (psi);
1253 	  unsigned i;
1254 
1255 	  for (i = 0; i < gimple_phi_num_args (phi); i++)
1256 	    if (gimple_phi_arg_edge (phi, i) == e)
1257 	      {
1258 		tree res, arg = gimple_phi_arg_def (phi, i);
1259 		use_operand_p use_p;
1260 		gimple close_phi;
1261 
1262 		if (TREE_CODE (arg) != SSA_NAME)
1263 		  continue;
1264 
1265 		close_phi = create_phi_node (arg, close);
1266 		res = create_new_def_for (gimple_phi_result (close_phi),
1267 					  close_phi,
1268 					  gimple_phi_result_ptr (close_phi));
1269 		add_phi_arg (close_phi, arg,
1270 			     gimple_phi_arg_edge (close_phi, 0),
1271 			     UNKNOWN_LOCATION);
1272 		use_p = gimple_phi_arg_imm_use_ptr (phi, i);
1273 		replace_exp (use_p, res);
1274 		update_stmt (phi);
1275 	      }
1276 	}
1277     }
1278 }
1279 
1280 /* Converts the current loop closed SSA form to a canonical form
1281    expected by the Graphite code generation.
1282 
1283    The loop closed SSA form has the following invariant: a variable
1284    defined in a loop that is used outside the loop appears only in the
1285    phi nodes in the destination of the loop exit.  These phi nodes are
1286    called close phi nodes.
1287 
1288    The canonical loop closed SSA form contains the extra invariants:
1289 
1290    - when the loop contains only one exit, the close phi nodes contain
1291    only one argument.  That implies that the basic block that contains
1292    the close phi nodes has only one predecessor, that is a basic block
1293    in the loop.
1294 
1295    - the basic block containing the close phi nodes does not contain
1296    other statements.
1297 */
1298 
1299 static void
1300 canonicalize_loop_closed_ssa_form (void)
1301 {
1302   loop_iterator li;
1303   loop_p loop;
1304 
1305 #ifdef ENABLE_CHECKING
1306   verify_loop_closed_ssa ();
1307 #endif
1308 
1309   FOR_EACH_LOOP (li, loop, 0)
1310     canonicalize_loop_closed_ssa (loop);
1311 
1312   rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
1313   update_ssa (TODO_update_ssa);
1314 
1315 #ifdef ENABLE_CHECKING
1316   verify_loop_closed_ssa ();
1317 #endif
1318 }
1319 
1320 /* Find Static Control Parts (SCoP) in the current function and pushes
1321    them to SCOPS.  */
1322 
1323 void
1324 build_scops (VEC (scop_p, heap) **scops)
1325 {
1326   struct loop *loop = current_loops->tree_root;
1327   VEC (sd_region, heap) *regions = VEC_alloc (sd_region, heap, 3);
1328 
1329   canonicalize_loop_closed_ssa_form ();
1330   build_scops_1 (single_succ (ENTRY_BLOCK_PTR), ENTRY_BLOCK_PTR->loop_father,
1331 		 &regions, loop);
1332   create_sese_edges (regions);
1333   build_graphite_scops (regions, scops);
1334 
1335   if (dump_file && (dump_flags & TDF_DETAILS))
1336     print_graphite_statistics (dump_file, *scops);
1337 
1338   limit_scops (scops);
1339   VEC_free (sd_region, heap, regions);
1340 
1341   if (dump_file && (dump_flags & TDF_DETAILS))
1342     fprintf (dump_file, "\nnumber of SCoPs: %d\n",
1343 	     VEC_length (scop_p, *scops));
1344 }
1345 
1346 /* Pretty print to FILE all the SCoPs in DOT format and mark them with
1347    different colors.  If there are not enough colors, paint the
1348    remaining SCoPs in gray.
1349 
1350    Special nodes:
1351    - "*" after the node number denotes the entry of a SCoP,
1352    - "#" after the node number denotes the exit of a SCoP,
1353    - "()" around the node number denotes the entry or the
1354      exit nodes of the SCOP.  These are not part of SCoP.  */
1355 
1356 static void
1357 dot_all_scops_1 (FILE *file, VEC (scop_p, heap) *scops)
1358 {
1359   basic_block bb;
1360   edge e;
1361   edge_iterator ei;
1362   scop_p scop;
1363   const char* color;
1364   int i;
1365 
1366   /* Disable debugging while printing graph.  */
1367   int tmp_dump_flags = dump_flags;
1368   dump_flags = 0;
1369 
1370   fprintf (file, "digraph all {\n");
1371 
1372   FOR_ALL_BB (bb)
1373     {
1374       int part_of_scop = false;
1375 
1376       /* Use HTML for every bb label.  So we are able to print bbs
1377          which are part of two different SCoPs, with two different
1378          background colors.  */
1379       fprintf (file, "%d [label=<\n  <TABLE BORDER=\"0\" CELLBORDER=\"1\" ",
1380                      bb->index);
1381       fprintf (file, "CELLSPACING=\"0\">\n");
1382 
1383       /* Select color for SCoP.  */
1384       for (i = 0; VEC_iterate (scop_p, scops, i, scop); i++)
1385 	{
1386 	  sese region = SCOP_REGION (scop);
1387 	  if (bb_in_sese_p (bb, region)
1388 	      || (SESE_EXIT_BB (region) == bb)
1389 	      || (SESE_ENTRY_BB (region) == bb))
1390 	    {
1391 	      switch (i % 17)
1392 		{
1393 		case 0: /* red */
1394 		  color = "#e41a1c";
1395 		  break;
1396 		case 1: /* blue */
1397 		  color = "#377eb8";
1398 		  break;
1399 		case 2: /* green */
1400 		  color = "#4daf4a";
1401 		  break;
1402 		case 3: /* purple */
1403 		  color = "#984ea3";
1404 		  break;
1405 		case 4: /* orange */
1406 		  color = "#ff7f00";
1407 		  break;
1408 		case 5: /* yellow */
1409 		  color = "#ffff33";
1410 		  break;
1411 		case 6: /* brown */
1412 		  color = "#a65628";
1413 		  break;
1414 		case 7: /* rose */
1415 		  color = "#f781bf";
1416 		  break;
1417 		case 8:
1418 		  color = "#8dd3c7";
1419 		  break;
1420 		case 9:
1421 		  color = "#ffffb3";
1422 		  break;
1423 		case 10:
1424 		  color = "#bebada";
1425 		  break;
1426 		case 11:
1427 		  color = "#fb8072";
1428 		  break;
1429 		case 12:
1430 		  color = "#80b1d3";
1431 		  break;
1432 		case 13:
1433 		  color = "#fdb462";
1434 		  break;
1435 		case 14:
1436 		  color = "#b3de69";
1437 		  break;
1438 		case 15:
1439 		  color = "#fccde5";
1440 		  break;
1441 		case 16:
1442 		  color = "#bc80bd";
1443 		  break;
1444 		default: /* gray */
1445 		  color = "#999999";
1446 		}
1447 
1448 	      fprintf (file, "    <TR><TD WIDTH=\"50\" BGCOLOR=\"%s\">", color);
1449 
1450 	      if (!bb_in_sese_p (bb, region))
1451 		fprintf (file, " (");
1452 
1453 	      if (bb == SESE_ENTRY_BB (region)
1454 		  && bb == SESE_EXIT_BB (region))
1455 		fprintf (file, " %d*# ", bb->index);
1456 	      else if (bb == SESE_ENTRY_BB (region))
1457 		fprintf (file, " %d* ", bb->index);
1458 	      else if (bb == SESE_EXIT_BB (region))
1459 		fprintf (file, " %d# ", bb->index);
1460 	      else
1461 		fprintf (file, " %d ", bb->index);
1462 
1463 	      if (!bb_in_sese_p (bb,region))
1464 		fprintf (file, ")");
1465 
1466 	      fprintf (file, "</TD></TR>\n");
1467 	      part_of_scop  = true;
1468 	    }
1469 	}
1470 
1471       if (!part_of_scop)
1472 	{
1473 	  fprintf (file, "    <TR><TD WIDTH=\"50\" BGCOLOR=\"#ffffff\">");
1474 	  fprintf (file, " %d </TD></TR>\n", bb->index);
1475 	}
1476       fprintf (file, "  </TABLE>>, shape=box, style=\"setlinewidth(0)\"]\n");
1477     }
1478 
1479   FOR_ALL_BB (bb)
1480     {
1481       FOR_EACH_EDGE (e, ei, bb->succs)
1482 	      fprintf (file, "%d -> %d;\n", bb->index, e->dest->index);
1483     }
1484 
1485   fputs ("}\n\n", file);
1486 
1487   /* Enable debugging again.  */
1488   dump_flags = tmp_dump_flags;
1489 }
1490 
1491 /* Display all SCoPs using dotty.  */
1492 
1493 void
1494 dot_all_scops (VEC (scop_p, heap) *scops)
1495 {
1496   /* When debugging, enable the following code.  This cannot be used
1497      in production compilers because it calls "system".  */
1498 #if 0
1499   int x;
1500   FILE *stream = fopen ("/tmp/allscops.dot", "w");
1501   gcc_assert (stream);
1502 
1503   dot_all_scops_1 (stream, scops);
1504   fclose (stream);
1505 
1506   x = system ("dotty /tmp/allscops.dot &");
1507 #else
1508   dot_all_scops_1 (stderr, scops);
1509 #endif
1510 }
1511 
1512 /* Display all SCoPs using dotty.  */
1513 
1514 void
1515 dot_scop (scop_p scop)
1516 {
1517   VEC (scop_p, heap) *scops = NULL;
1518 
1519   if (scop)
1520     VEC_safe_push (scop_p, heap, scops, scop);
1521 
1522   /* When debugging, enable the following code.  This cannot be used
1523      in production compilers because it calls "system".  */
1524 #if 0
1525   {
1526     int x;
1527     FILE *stream = fopen ("/tmp/allscops.dot", "w");
1528     gcc_assert (stream);
1529 
1530     dot_all_scops_1 (stream, scops);
1531     fclose (stream);
1532     x = system ("dotty /tmp/allscops.dot &");
1533   }
1534 #else
1535   dot_all_scops_1 (stderr, scops);
1536 #endif
1537 
1538   VEC_free (scop_p, heap, scops);
1539 }
1540 
1541 #endif
1542