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

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [gcc/] [graphite-scop-detection.c] - Blame information for rev 684

Details | Compare with Previous | View Log

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

powered by: WebSVN 2.1.0

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