OpenCores
URL https://opencores.org/ocsvn/openrisc_me/openrisc_me/trunk

Subversion Repositories openrisc_me

[/] [openrisc/] [trunk/] [gnu-src/] [gcc-4.5.1/] [gcc/] [graphite-scop-detection.c] - Blame information for rev 280

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 280 jeremybenn
/* 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

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.