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

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [gcc/] [graphite-sese-to-poly.c] - Blame information for rev 744

Go to most recent revision | Details | Compare with Previous | View Log

Line No. Rev Author Line
1 684 jeremybenn
/* Conversion of SESE regions to Polyhedra.
2
   Copyright (C) 2009, 2010, 2011 Free Software Foundation, Inc.
3
   Contributed by Sebastian Pop <sebastian.pop@amd.com>.
4
 
5
This file is part of GCC.
6
 
7
GCC is free software; you can redistribute it and/or modify
8
it under the terms of the GNU General Public License as published by
9
the Free Software Foundation; either version 3, or (at your option)
10
any later version.
11
 
12
GCC is distributed in the hope that it will be useful,
13
but WITHOUT ANY WARRANTY; without even the implied warranty of
14
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15
GNU General Public License for more details.
16
 
17
You should have received a copy of the GNU General Public License
18
along with GCC; see the file COPYING3.  If not see
19
<http://www.gnu.org/licenses/>.  */
20
 
21
#include "config.h"
22
#include "system.h"
23
#include "coretypes.h"
24
#include "tree-flow.h"
25
#include "tree-dump.h"
26
#include "cfgloop.h"
27
#include "tree-chrec.h"
28
#include "tree-data-ref.h"
29
#include "tree-scalar-evolution.h"
30
#include "domwalk.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-sese-to-poly.h"
38
 
39
/* Returns the index of the PHI argument defined in the outermost
40
   loop.  */
41
 
42
static size_t
43
phi_arg_in_outermost_loop (gimple phi)
44
{
45
  loop_p loop = gimple_bb (phi)->loop_father;
46
  size_t i, res = 0;
47
 
48
  for (i = 0; i < gimple_phi_num_args (phi); i++)
49
    if (!flow_bb_inside_loop_p (loop, gimple_phi_arg_edge (phi, i)->src))
50
      {
51
        loop = gimple_phi_arg_edge (phi, i)->src->loop_father;
52
        res = i;
53
      }
54
 
55
  return res;
56
}
57
 
58
/* Removes a simple copy phi node "RES = phi (INIT, RES)" at position
59
   PSI by inserting on the loop ENTRY edge assignment "RES = INIT".  */
60
 
61
static void
62
remove_simple_copy_phi (gimple_stmt_iterator *psi)
63
{
64
  gimple phi = gsi_stmt (*psi);
65
  tree res = gimple_phi_result (phi);
66
  size_t entry = phi_arg_in_outermost_loop (phi);
67
  tree init = gimple_phi_arg_def (phi, entry);
68
  gimple stmt = gimple_build_assign (res, init);
69
  edge e = gimple_phi_arg_edge (phi, entry);
70
 
71
  remove_phi_node (psi, false);
72
  gsi_insert_on_edge_immediate (e, stmt);
73
  SSA_NAME_DEF_STMT (res) = stmt;
74
}
75
 
76
/* Removes an invariant phi node at position PSI by inserting on the
77
   loop ENTRY edge the assignment RES = INIT.  */
78
 
79
static void
80
remove_invariant_phi (sese region, gimple_stmt_iterator *psi)
81
{
82
  gimple phi = gsi_stmt (*psi);
83
  loop_p loop = loop_containing_stmt (phi);
84
  tree res = gimple_phi_result (phi);
85
  tree scev = scalar_evolution_in_region (region, loop, res);
86
  size_t entry = phi_arg_in_outermost_loop (phi);
87
  edge e = gimple_phi_arg_edge (phi, entry);
88
  tree var;
89
  gimple stmt;
90
  gimple_seq stmts;
91
  gimple_stmt_iterator gsi;
92
 
93
  if (tree_contains_chrecs (scev, NULL))
94
    scev = gimple_phi_arg_def (phi, entry);
95
 
96
  var = force_gimple_operand (scev, &stmts, true, NULL_TREE);
97
  stmt = gimple_build_assign (res, var);
98
  remove_phi_node (psi, false);
99
 
100
  if (!stmts)
101
    stmts = gimple_seq_alloc ();
102
 
103
  gsi = gsi_last (stmts);
104
  gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
105
  gsi_insert_seq_on_edge (e, stmts);
106
  gsi_commit_edge_inserts ();
107
  SSA_NAME_DEF_STMT (res) = stmt;
108
}
109
 
110
/* Returns true when the phi node at PSI is of the form "a = phi (a, x)".  */
111
 
112
static inline bool
113
simple_copy_phi_p (gimple phi)
114
{
115
  tree res;
116
 
117
  if (gimple_phi_num_args (phi) != 2)
118
    return false;
119
 
120
  res = gimple_phi_result (phi);
121
  return (res == gimple_phi_arg_def (phi, 0)
122
          || res == gimple_phi_arg_def (phi, 1));
123
}
124
 
125
/* Returns true when the phi node at position PSI is a reduction phi
126
   node in REGION.  Otherwise moves the pointer PSI to the next phi to
127
   be considered.  */
128
 
129
static bool
130
reduction_phi_p (sese region, gimple_stmt_iterator *psi)
131
{
132
  loop_p loop;
133
  gimple phi = gsi_stmt (*psi);
134
  tree res = gimple_phi_result (phi);
135
 
136
  loop = loop_containing_stmt (phi);
137
 
138
  if (simple_copy_phi_p (phi))
139
    {
140
      /* PRE introduces phi nodes like these, for an example,
141
         see id-5.f in the fortran graphite testsuite:
142
 
143
         # prephitmp.85_265 = PHI <prephitmp.85_258(33), prephitmp.85_265(18)>
144
      */
145
      remove_simple_copy_phi (psi);
146
      return false;
147
    }
148
 
149
  if (scev_analyzable_p (res, region))
150
    {
151
      tree scev = scalar_evolution_in_region (region, loop, res);
152
 
153
      if (evolution_function_is_invariant_p (scev, loop->num))
154
        remove_invariant_phi (region, psi);
155
      else
156
        gsi_next (psi);
157
 
158
      return false;
159
    }
160
 
161
  /* All the other cases are considered reductions.  */
162
  return true;
163
}
164
 
165
/* Store the GRAPHITE representation of BB.  */
166
 
167
static gimple_bb_p
168
new_gimple_bb (basic_block bb, VEC (data_reference_p, heap) *drs)
169
{
170
  struct gimple_bb *gbb;
171
 
172
  gbb = XNEW (struct gimple_bb);
173
  bb->aux = gbb;
174
  GBB_BB (gbb) = bb;
175
  GBB_DATA_REFS (gbb) = drs;
176
  GBB_CONDITIONS (gbb) = NULL;
177
  GBB_CONDITION_CASES (gbb) = NULL;
178
 
179
  return gbb;
180
}
181
 
182
static void
183
free_data_refs_aux (VEC (data_reference_p, heap) *datarefs)
184
{
185
  unsigned int i;
186
  struct data_reference *dr;
187
 
188
  FOR_EACH_VEC_ELT (data_reference_p, datarefs, i, dr)
189
    if (dr->aux)
190
      {
191
        base_alias_pair *bap = (base_alias_pair *)(dr->aux);
192
 
193
        free (bap->alias_set);
194
 
195
        free (bap);
196
        dr->aux = NULL;
197
      }
198
}
199
/* Frees GBB.  */
200
 
201
static void
202
free_gimple_bb (struct gimple_bb *gbb)
203
{
204
  free_data_refs_aux (GBB_DATA_REFS (gbb));
205
  free_data_refs (GBB_DATA_REFS (gbb));
206
 
207
  VEC_free (gimple, heap, GBB_CONDITIONS (gbb));
208
  VEC_free (gimple, heap, GBB_CONDITION_CASES (gbb));
209
  GBB_BB (gbb)->aux = 0;
210
  XDELETE (gbb);
211
}
212
 
213
/* Deletes all gimple bbs in SCOP.  */
214
 
215
static void
216
remove_gbbs_in_scop (scop_p scop)
217
{
218
  int i;
219
  poly_bb_p pbb;
220
 
221
  FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
222
    free_gimple_bb (PBB_BLACK_BOX (pbb));
223
}
224
 
225
/* Deletes all scops in SCOPS.  */
226
 
227
void
228
free_scops (VEC (scop_p, heap) *scops)
229
{
230
  int i;
231
  scop_p scop;
232
 
233
  FOR_EACH_VEC_ELT (scop_p, scops, i, scop)
234
    {
235
      remove_gbbs_in_scop (scop);
236
      free_sese (SCOP_REGION (scop));
237
      free_scop (scop);
238
    }
239
 
240
  VEC_free (scop_p, heap, scops);
241
}
242
 
243
/* Same as outermost_loop_in_sese, returns the outermost loop
244
   containing BB in REGION, but makes sure that the returned loop
245
   belongs to the REGION, and so this returns the first loop in the
246
   REGION when the loop containing BB does not belong to REGION.  */
247
 
248
static loop_p
249
outermost_loop_in_sese_1 (sese region, basic_block bb)
250
{
251
  loop_p nest = outermost_loop_in_sese (region, bb);
252
 
253
  if (loop_in_sese_p (nest, region))
254
    return nest;
255
 
256
  /* When the basic block BB does not belong to a loop in the region,
257
     return the first loop in the region.  */
258
  nest = nest->inner;
259
  while (nest)
260
    if (loop_in_sese_p (nest, region))
261
      break;
262
    else
263
      nest = nest->next;
264
 
265
  gcc_assert (nest);
266
  return nest;
267
}
268
 
269
/* Generates a polyhedral black box only if the bb contains interesting
270
   information.  */
271
 
272
static gimple_bb_p
273
try_generate_gimple_bb (scop_p scop, basic_block bb)
274
{
275
  VEC (data_reference_p, heap) *drs = VEC_alloc (data_reference_p, heap, 5);
276
  sese region = SCOP_REGION (scop);
277
  loop_p nest = outermost_loop_in_sese_1 (region, bb);
278
  gimple_stmt_iterator gsi;
279
 
280
  for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
281
    {
282
      gimple stmt = gsi_stmt (gsi);
283
      loop_p loop;
284
 
285
      if (is_gimple_debug (stmt))
286
        continue;
287
 
288
      loop = loop_containing_stmt (stmt);
289
      if (!loop_in_sese_p (loop, region))
290
        loop = nest;
291
 
292
      graphite_find_data_references_in_stmt (nest, loop, stmt, &drs);
293
    }
294
 
295
  return new_gimple_bb (bb, drs);
296
}
297
 
298
/* Returns true if all predecessors of BB, that are not dominated by BB, are
299
   marked in MAP.  The predecessors dominated by BB are loop latches and will
300
   be handled after BB.  */
301
 
302
static bool
303
all_non_dominated_preds_marked_p (basic_block bb, sbitmap map)
304
{
305
  edge e;
306
  edge_iterator ei;
307
 
308
  FOR_EACH_EDGE (e, ei, bb->preds)
309
    if (!TEST_BIT (map, e->src->index)
310
        && !dominated_by_p (CDI_DOMINATORS, e->src, bb))
311
        return false;
312
 
313
  return true;
314
}
315
 
316
/* Compare the depth of two basic_block's P1 and P2.  */
317
 
318
static int
319
compare_bb_depths (const void *p1, const void *p2)
320
{
321
  const_basic_block const bb1 = *(const_basic_block const*)p1;
322
  const_basic_block const bb2 = *(const_basic_block const*)p2;
323
  int d1 = loop_depth (bb1->loop_father);
324
  int d2 = loop_depth (bb2->loop_father);
325
 
326
  if (d1 < d2)
327
    return 1;
328
 
329
  if (d1 > d2)
330
    return -1;
331
 
332
  return 0;
333
}
334
 
335
/* Sort the basic blocks from DOM such that the first are the ones at
336
   a deepest loop level.  */
337
 
338
static void
339
graphite_sort_dominated_info (VEC (basic_block, heap) *dom)
340
{
341
  VEC_qsort (basic_block, dom, compare_bb_depths);
342
}
343
 
344
/* Recursive helper function for build_scops_bbs.  */
345
 
346
static void
347
build_scop_bbs_1 (scop_p scop, sbitmap visited, basic_block bb)
348
{
349
  sese region = SCOP_REGION (scop);
350
  VEC (basic_block, heap) *dom;
351
  poly_bb_p pbb;
352
 
353
  if (TEST_BIT (visited, bb->index)
354
      || !bb_in_sese_p (bb, region))
355
    return;
356
 
357
  pbb = new_poly_bb (scop, try_generate_gimple_bb (scop, bb));
358
  VEC_safe_push (poly_bb_p, heap, SCOP_BBS (scop), pbb);
359
  SET_BIT (visited, bb->index);
360
 
361
  dom = get_dominated_by (CDI_DOMINATORS, bb);
362
 
363
  if (dom == NULL)
364
    return;
365
 
366
  graphite_sort_dominated_info (dom);
367
 
368
  while (!VEC_empty (basic_block, dom))
369
    {
370
      int i;
371
      basic_block dom_bb;
372
 
373
      FOR_EACH_VEC_ELT (basic_block, dom, i, dom_bb)
374
        if (all_non_dominated_preds_marked_p (dom_bb, visited))
375
          {
376
            build_scop_bbs_1 (scop, visited, dom_bb);
377
            VEC_unordered_remove (basic_block, dom, i);
378
            break;
379
          }
380
    }
381
 
382
  VEC_free (basic_block, heap, dom);
383
}
384
 
385
/* Gather the basic blocks belonging to the SCOP.  */
386
 
387
static void
388
build_scop_bbs (scop_p scop)
389
{
390
  sbitmap visited = sbitmap_alloc (last_basic_block);
391
  sese region = SCOP_REGION (scop);
392
 
393
  sbitmap_zero (visited);
394
  build_scop_bbs_1 (scop, visited, SESE_ENTRY_BB (region));
395
  sbitmap_free (visited);
396
}
397
 
398
/* Converts the STATIC_SCHEDULE of PBB into a scattering polyhedron.
399
   We generate SCATTERING_DIMENSIONS scattering dimensions.
400
 
401
   CLooG 0.15.0 and previous versions require, that all
402
   scattering functions of one CloogProgram have the same number of
403
   scattering dimensions, therefore we allow to specify it.  This
404
   should be removed in future versions of CLooG.
405
 
406
   The scattering polyhedron consists of these dimensions: scattering,
407
   loop_iterators, parameters.
408
 
409
   Example:
410
 
411
   | scattering_dimensions = 5
412
   | used_scattering_dimensions = 3
413
   | nb_iterators = 1
414
   | scop_nb_params = 2
415
   |
416
   | Schedule:
417
   |   i
418
   | 4 5
419
   |
420
   | Scattering polyhedron:
421
   |
422
   | scattering: {s1, s2, s3, s4, s5}
423
   | loop_iterators: {i}
424
   | parameters: {p1, p2}
425
   |
426
   | s1  s2  s3  s4  s5  i   p1  p2  1
427
   | 1   0   0   0   0   0   0   0  -4  = 0
428
   | 0   1   0   0   0  -1   0   0   0  = 0
429
   | 0   0   1   0   0   0   0   0  -5  = 0  */
430
 
431
static void
432
build_pbb_scattering_polyhedrons (ppl_Linear_Expression_t static_schedule,
433
                                  poly_bb_p pbb, int scattering_dimensions)
434
{
435
  int i;
436
  scop_p scop = PBB_SCOP (pbb);
437
  int nb_iterators = pbb_dim_iter_domain (pbb);
438
  int used_scattering_dimensions = nb_iterators * 2 + 1;
439
  int nb_params = scop_nb_params (scop);
440
  ppl_Coefficient_t c;
441
  ppl_dimension_type dim = scattering_dimensions + nb_iterators + nb_params;
442
  mpz_t v;
443
 
444
  gcc_assert (scattering_dimensions >= used_scattering_dimensions);
445
 
446
  mpz_init (v);
447
  ppl_new_Coefficient (&c);
448
  PBB_TRANSFORMED (pbb) = poly_scattering_new ();
449
  ppl_new_C_Polyhedron_from_space_dimension
450
    (&PBB_TRANSFORMED_SCATTERING (pbb), dim, 0);
451
 
452
  PBB_NB_SCATTERING_TRANSFORM (pbb) = scattering_dimensions;
453
 
454
  for (i = 0; i < scattering_dimensions; i++)
455
    {
456
      ppl_Constraint_t cstr;
457
      ppl_Linear_Expression_t expr;
458
 
459
      ppl_new_Linear_Expression_with_dimension (&expr, dim);
460
      mpz_set_si (v, 1);
461
      ppl_assign_Coefficient_from_mpz_t (c, v);
462
      ppl_Linear_Expression_add_to_coefficient (expr, i, c);
463
 
464
      /* Textual order inside this loop.  */
465
      if ((i % 2) == 0)
466
        {
467
          ppl_Linear_Expression_coefficient (static_schedule, i / 2, c);
468
          ppl_Coefficient_to_mpz_t (c, v);
469
          mpz_neg (v, v);
470
          ppl_assign_Coefficient_from_mpz_t (c, v);
471
          ppl_Linear_Expression_add_to_inhomogeneous (expr, c);
472
        }
473
 
474
      /* Iterations of this loop.  */
475
      else /* if ((i % 2) == 1) */
476
        {
477
          int loop = (i - 1) / 2;
478
 
479
          mpz_set_si (v, -1);
480
          ppl_assign_Coefficient_from_mpz_t (c, v);
481
          ppl_Linear_Expression_add_to_coefficient
482
            (expr, scattering_dimensions + loop, c);
483
        }
484
 
485
      ppl_new_Constraint (&cstr, expr, PPL_CONSTRAINT_TYPE_EQUAL);
486
      ppl_Polyhedron_add_constraint (PBB_TRANSFORMED_SCATTERING (pbb), cstr);
487
      ppl_delete_Linear_Expression (expr);
488
      ppl_delete_Constraint (cstr);
489
    }
490
 
491
  mpz_clear (v);
492
  ppl_delete_Coefficient (c);
493
 
494
  PBB_ORIGINAL (pbb) = poly_scattering_copy (PBB_TRANSFORMED (pbb));
495
}
496
 
497
/* Build for BB the static schedule.
498
 
499
   The static schedule is a Dewey numbering of the abstract syntax
500
   tree: http://en.wikipedia.org/wiki/Dewey_Decimal_Classification
501
 
502
   The following example informally defines the static schedule:
503
 
504
   A
505
   for (i: ...)
506
     {
507
       for (j: ...)
508
         {
509
           B
510
           C
511
         }
512
 
513
       for (k: ...)
514
         {
515
           D
516
           E
517
         }
518
     }
519
   F
520
 
521
   Static schedules for A to F:
522
 
523
     DEPTH
524
 
525
   A 0
526
   B 1 0 0
527
   C 1 0 1
528
   D 1 1 0
529
   E 1 1 1
530
   F 2
531
*/
532
 
533
static void
534
build_scop_scattering (scop_p scop)
535
{
536
  int i;
537
  poly_bb_p pbb;
538
  gimple_bb_p previous_gbb = NULL;
539
  ppl_Linear_Expression_t static_schedule;
540
  ppl_Coefficient_t c;
541
  mpz_t v;
542
 
543
  mpz_init (v);
544
  ppl_new_Coefficient (&c);
545
  ppl_new_Linear_Expression (&static_schedule);
546
 
547
  /* We have to start schedules at 0 on the first component and
548
     because we cannot compare_prefix_loops against a previous loop,
549
     prefix will be equal to zero, and that index will be
550
     incremented before copying.  */
551
  mpz_set_si (v, -1);
552
  ppl_assign_Coefficient_from_mpz_t (c, v);
553
  ppl_Linear_Expression_add_to_coefficient (static_schedule, 0, c);
554
 
555
  FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
556
    {
557
      gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
558
      ppl_Linear_Expression_t common;
559
      int prefix;
560
      int nb_scat_dims = pbb_dim_iter_domain (pbb) * 2 + 1;
561
 
562
      if (previous_gbb)
563
        prefix = nb_common_loops (SCOP_REGION (scop), previous_gbb, gbb);
564
      else
565
        prefix = 0;
566
 
567
      previous_gbb = gbb;
568
      ppl_new_Linear_Expression_with_dimension (&common, prefix + 1);
569
      ppl_assign_Linear_Expression_from_Linear_Expression (common,
570
                                                           static_schedule);
571
 
572
      mpz_set_si (v, 1);
573
      ppl_assign_Coefficient_from_mpz_t (c, v);
574
      ppl_Linear_Expression_add_to_coefficient (common, prefix, c);
575
      ppl_assign_Linear_Expression_from_Linear_Expression (static_schedule,
576
                                                           common);
577
 
578
      build_pbb_scattering_polyhedrons (common, pbb, nb_scat_dims);
579
 
580
      ppl_delete_Linear_Expression (common);
581
    }
582
 
583
  mpz_clear (v);
584
  ppl_delete_Coefficient (c);
585
  ppl_delete_Linear_Expression (static_schedule);
586
}
587
 
588
/* Add the value K to the dimension D of the linear expression EXPR.  */
589
 
590
static void
591
add_value_to_dim (ppl_dimension_type d, ppl_Linear_Expression_t expr,
592
                  mpz_t k)
593
{
594
  mpz_t val;
595
  ppl_Coefficient_t coef;
596
 
597
  ppl_new_Coefficient (&coef);
598
  ppl_Linear_Expression_coefficient (expr, d, coef);
599
  mpz_init (val);
600
  ppl_Coefficient_to_mpz_t (coef, val);
601
 
602
  mpz_add (val, val, k);
603
 
604
  ppl_assign_Coefficient_from_mpz_t (coef, val);
605
  ppl_Linear_Expression_add_to_coefficient (expr, d, coef);
606
  mpz_clear (val);
607
  ppl_delete_Coefficient (coef);
608
}
609
 
610
/* In the context of scop S, scan E, the right hand side of a scalar
611
   evolution function in loop VAR, and translate it to a linear
612
   expression EXPR.  */
613
 
614
static void
615
scan_tree_for_params_right_scev (sese s, tree e, int var,
616
                                 ppl_Linear_Expression_t expr)
617
{
618
  if (expr)
619
    {
620
      loop_p loop = get_loop (var);
621
      ppl_dimension_type l = sese_loop_depth (s, loop) - 1;
622
      mpz_t val;
623
 
624
      /* Scalar evolutions should happen in the sese region.  */
625
      gcc_assert (sese_loop_depth (s, loop) > 0);
626
 
627
      /* We can not deal with parametric strides like:
628
 
629
      | p = parameter;
630
      |
631
      | for i:
632
      |   a [i * p] = ...   */
633
      gcc_assert (TREE_CODE (e) == INTEGER_CST);
634
 
635
      mpz_init (val);
636
      tree_int_to_gmp (e, val);
637
      add_value_to_dim (l, expr, val);
638
      mpz_clear (val);
639
    }
640
}
641
 
642
/* Scan the integer constant CST, and add it to the inhomogeneous part of the
643
   linear expression EXPR.  K is the multiplier of the constant.  */
644
 
645
static void
646
scan_tree_for_params_int (tree cst, ppl_Linear_Expression_t expr, mpz_t k)
647
{
648
  mpz_t val;
649
  ppl_Coefficient_t coef;
650
  tree type = TREE_TYPE (cst);
651
 
652
  mpz_init (val);
653
 
654
  /* Necessary to not get "-1 = 2^n - 1". */
655
  mpz_set_double_int (val, double_int_sext (tree_to_double_int (cst),
656
                                            TYPE_PRECISION (type)), false);
657
 
658
  mpz_mul (val, val, k);
659
  ppl_new_Coefficient (&coef);
660
  ppl_assign_Coefficient_from_mpz_t (coef, val);
661
  ppl_Linear_Expression_add_to_inhomogeneous (expr, coef);
662
  mpz_clear (val);
663
  ppl_delete_Coefficient (coef);
664
}
665
 
666
/* When parameter NAME is in REGION, returns its index in SESE_PARAMS.
667
   Otherwise returns -1.  */
668
 
669
static inline int
670
parameter_index_in_region_1 (tree name, sese region)
671
{
672
  int i;
673
  tree p;
674
 
675
  gcc_assert (TREE_CODE (name) == SSA_NAME);
676
 
677
  FOR_EACH_VEC_ELT (tree, SESE_PARAMS (region), i, p)
678
    if (p == name)
679
      return i;
680
 
681
  return -1;
682
}
683
 
684
/* When the parameter NAME is in REGION, returns its index in
685
   SESE_PARAMS.  Otherwise this function inserts NAME in SESE_PARAMS
686
   and returns the index of NAME.  */
687
 
688
static int
689
parameter_index_in_region (tree name, sese region)
690
{
691
  int i;
692
 
693
  gcc_assert (TREE_CODE (name) == SSA_NAME);
694
 
695
  i = parameter_index_in_region_1 (name, region);
696
  if (i != -1)
697
    return i;
698
 
699
  gcc_assert (SESE_ADD_PARAMS (region));
700
 
701
  i = VEC_length (tree, SESE_PARAMS (region));
702
  VEC_safe_push (tree, heap, SESE_PARAMS (region), name);
703
  return i;
704
}
705
 
706
/* In the context of sese S, scan the expression E and translate it to
707
   a linear expression C.  When parsing a symbolic multiplication, K
708
   represents the constant multiplier of an expression containing
709
   parameters.  */
710
 
711
static void
712
scan_tree_for_params (sese s, tree e, ppl_Linear_Expression_t c,
713
                      mpz_t k)
714
{
715
  if (e == chrec_dont_know)
716
    return;
717
 
718
  switch (TREE_CODE (e))
719
    {
720
    case POLYNOMIAL_CHREC:
721
      scan_tree_for_params_right_scev (s, CHREC_RIGHT (e),
722
                                       CHREC_VARIABLE (e), c);
723
      scan_tree_for_params (s, CHREC_LEFT (e), c, k);
724
      break;
725
 
726
    case MULT_EXPR:
727
      if (chrec_contains_symbols (TREE_OPERAND (e, 0)))
728
        {
729
          if (c)
730
            {
731
              mpz_t val;
732
              gcc_assert (host_integerp (TREE_OPERAND (e, 1), 0));
733
              mpz_init (val);
734
              tree_int_to_gmp (TREE_OPERAND (e, 1), val);
735
              mpz_mul (val, val, k);
736
              scan_tree_for_params (s, TREE_OPERAND (e, 0), c, val);
737
              mpz_clear (val);
738
            }
739
          else
740
            scan_tree_for_params (s, TREE_OPERAND (e, 0), c, k);
741
        }
742
      else
743
        {
744
          if (c)
745
            {
746
              mpz_t val;
747
              gcc_assert (host_integerp (TREE_OPERAND (e, 0), 0));
748
              mpz_init (val);
749
              tree_int_to_gmp (TREE_OPERAND (e, 0), val);
750
              mpz_mul (val, val, k);
751
              scan_tree_for_params (s, TREE_OPERAND (e, 1), c, val);
752
              mpz_clear (val);
753
            }
754
          else
755
            scan_tree_for_params (s, TREE_OPERAND (e, 1), c, k);
756
        }
757
      break;
758
 
759
    case PLUS_EXPR:
760
    case POINTER_PLUS_EXPR:
761
      scan_tree_for_params (s, TREE_OPERAND (e, 0), c, k);
762
      scan_tree_for_params (s, TREE_OPERAND (e, 1), c, k);
763
      break;
764
 
765
    case MINUS_EXPR:
766
      {
767
        ppl_Linear_Expression_t tmp_expr = NULL;
768
 
769
        if (c)
770
          {
771
            ppl_dimension_type dim;
772
            ppl_Linear_Expression_space_dimension (c, &dim);
773
            ppl_new_Linear_Expression_with_dimension (&tmp_expr, dim);
774
          }
775
 
776
        scan_tree_for_params (s, TREE_OPERAND (e, 0), c, k);
777
        scan_tree_for_params (s, TREE_OPERAND (e, 1), tmp_expr, k);
778
 
779
        if (c)
780
          {
781
            ppl_subtract_Linear_Expression_from_Linear_Expression (c,
782
                                                                   tmp_expr);
783
            ppl_delete_Linear_Expression (tmp_expr);
784
          }
785
 
786
        break;
787
      }
788
 
789
    case NEGATE_EXPR:
790
      {
791
        ppl_Linear_Expression_t tmp_expr = NULL;
792
 
793
        if (c)
794
          {
795
            ppl_dimension_type dim;
796
            ppl_Linear_Expression_space_dimension (c, &dim);
797
            ppl_new_Linear_Expression_with_dimension (&tmp_expr, dim);
798
          }
799
 
800
        scan_tree_for_params (s, TREE_OPERAND (e, 0), tmp_expr, k);
801
 
802
        if (c)
803
          {
804
            ppl_subtract_Linear_Expression_from_Linear_Expression (c,
805
                                                                   tmp_expr);
806
            ppl_delete_Linear_Expression (tmp_expr);
807
          }
808
 
809
        break;
810
      }
811
 
812
    case BIT_NOT_EXPR:
813
      {
814
        ppl_Linear_Expression_t tmp_expr = NULL;
815
 
816
        if (c)
817
          {
818
            ppl_dimension_type dim;
819
            ppl_Linear_Expression_space_dimension (c, &dim);
820
            ppl_new_Linear_Expression_with_dimension (&tmp_expr, dim);
821
          }
822
 
823
        scan_tree_for_params (s, TREE_OPERAND (e, 0), tmp_expr, k);
824
 
825
        if (c)
826
          {
827
            ppl_Coefficient_t coef;
828
            mpz_t minus_one;
829
 
830
            ppl_subtract_Linear_Expression_from_Linear_Expression (c,
831
                                                                   tmp_expr);
832
            ppl_delete_Linear_Expression (tmp_expr);
833
            mpz_init (minus_one);
834
            mpz_set_si (minus_one, -1);
835
            ppl_new_Coefficient_from_mpz_t (&coef, minus_one);
836
            ppl_Linear_Expression_add_to_inhomogeneous (c, coef);
837
            mpz_clear (minus_one);
838
            ppl_delete_Coefficient (coef);
839
          }
840
 
841
        break;
842
      }
843
 
844
    case SSA_NAME:
845
      {
846
        ppl_dimension_type p = parameter_index_in_region (e, s);
847
 
848
        if (c)
849
          {
850
            ppl_dimension_type dim;
851
            ppl_Linear_Expression_space_dimension (c, &dim);
852
            p += dim - sese_nb_params (s);
853
            add_value_to_dim (p, c, k);
854
          }
855
        break;
856
      }
857
 
858
    case INTEGER_CST:
859
      if (c)
860
        scan_tree_for_params_int (e, c, k);
861
      break;
862
 
863
    CASE_CONVERT:
864
    case NON_LVALUE_EXPR:
865
      scan_tree_for_params (s, TREE_OPERAND (e, 0), c, k);
866
      break;
867
 
868
    case ADDR_EXPR:
869
      break;
870
 
871
   default:
872
      gcc_unreachable ();
873
      break;
874
    }
875
}
876
 
877
/* Find parameters with respect to REGION in BB. We are looking in memory
878
   access functions, conditions and loop bounds.  */
879
 
880
static void
881
find_params_in_bb (sese region, gimple_bb_p gbb)
882
{
883
  int i;
884
  unsigned j;
885
  data_reference_p dr;
886
  gimple stmt;
887
  loop_p loop = GBB_BB (gbb)->loop_father;
888
  mpz_t one;
889
 
890
  mpz_init (one);
891
  mpz_set_si (one, 1);
892
 
893
  /* Find parameters in the access functions of data references.  */
894
  FOR_EACH_VEC_ELT (data_reference_p, GBB_DATA_REFS (gbb), i, dr)
895
    for (j = 0; j < DR_NUM_DIMENSIONS (dr); j++)
896
      scan_tree_for_params (region, DR_ACCESS_FN (dr, j), NULL, one);
897
 
898
  /* Find parameters in conditional statements.  */
899
  FOR_EACH_VEC_ELT (gimple, GBB_CONDITIONS (gbb), i, stmt)
900
    {
901
      tree lhs = scalar_evolution_in_region (region, loop,
902
                                             gimple_cond_lhs (stmt));
903
      tree rhs = scalar_evolution_in_region (region, loop,
904
                                             gimple_cond_rhs (stmt));
905
 
906
      scan_tree_for_params (region, lhs, NULL, one);
907
      scan_tree_for_params (region, rhs, NULL, one);
908
    }
909
 
910
  mpz_clear (one);
911
}
912
 
913
/* Record the parameters used in the SCOP.  A variable is a parameter
914
   in a scop if it does not vary during the execution of that scop.  */
915
 
916
static void
917
find_scop_parameters (scop_p scop)
918
{
919
  poly_bb_p pbb;
920
  unsigned i;
921
  sese region = SCOP_REGION (scop);
922
  struct loop *loop;
923
  mpz_t one;
924
 
925
  mpz_init (one);
926
  mpz_set_si (one, 1);
927
 
928
  /* Find the parameters used in the loop bounds.  */
929
  FOR_EACH_VEC_ELT (loop_p, SESE_LOOP_NEST (region), i, loop)
930
    {
931
      tree nb_iters = number_of_latch_executions (loop);
932
 
933
      if (!chrec_contains_symbols (nb_iters))
934
        continue;
935
 
936
      nb_iters = scalar_evolution_in_region (region, loop, nb_iters);
937
      scan_tree_for_params (region, nb_iters, NULL, one);
938
    }
939
 
940
  mpz_clear (one);
941
 
942
  /* Find the parameters used in data accesses.  */
943
  FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
944
    find_params_in_bb (region, PBB_BLACK_BOX (pbb));
945
 
946
  scop_set_nb_params (scop, sese_nb_params (region));
947
  SESE_ADD_PARAMS (region) = false;
948
 
949
  ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension
950
    (&SCOP_CONTEXT (scop), scop_nb_params (scop), 0);
951
}
952
 
953
/* Insert in the SCOP context constraints from the estimation of the
954
   number of iterations.  UB_EXPR is a linear expression describing
955
   the number of iterations in a loop.  This expression is bounded by
956
   the estimation NIT.  */
957
 
958
static void
959
add_upper_bounds_from_estimated_nit (scop_p scop, double_int nit,
960
                                     ppl_dimension_type dim,
961
                                     ppl_Linear_Expression_t ub_expr)
962
{
963
  mpz_t val;
964
  ppl_Linear_Expression_t nb_iters_le;
965
  ppl_Polyhedron_t pol;
966
  ppl_Coefficient_t coef;
967
  ppl_Constraint_t ub;
968
 
969
  ppl_new_C_Polyhedron_from_space_dimension (&pol, dim, 0);
970
  ppl_new_Linear_Expression_from_Linear_Expression (&nb_iters_le,
971
                                                    ub_expr);
972
 
973
  /* Construct the negated number of last iteration in VAL.  */
974
  mpz_init (val);
975
  mpz_set_double_int (val, nit, false);
976
  mpz_sub_ui (val, val, 1);
977
  mpz_neg (val, val);
978
 
979
  /* NB_ITERS_LE holds the number of last iteration in
980
     parametrical form.  Subtract estimated number of last
981
     iteration and assert that result is not positive.  */
982
  ppl_new_Coefficient_from_mpz_t (&coef, val);
983
  ppl_Linear_Expression_add_to_inhomogeneous (nb_iters_le, coef);
984
  ppl_delete_Coefficient (coef);
985
  ppl_new_Constraint (&ub, nb_iters_le,
986
                      PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL);
987
  ppl_Polyhedron_add_constraint (pol, ub);
988
 
989
  /* Remove all but last GDIM dimensions from POL to obtain
990
     only the constraints on the parameters.  */
991
  {
992
    graphite_dim_t gdim = scop_nb_params (scop);
993
    ppl_dimension_type *dims = XNEWVEC (ppl_dimension_type, dim - gdim);
994
    graphite_dim_t i;
995
 
996
    for (i = 0; i < dim - gdim; i++)
997
      dims[i] = i;
998
 
999
    ppl_Polyhedron_remove_space_dimensions (pol, dims, dim - gdim);
1000
    XDELETEVEC (dims);
1001
  }
1002
 
1003
  /* Add the constraints on the parameters to the SCoP context.  */
1004
  {
1005
    ppl_Pointset_Powerset_C_Polyhedron_t constraints_ps;
1006
 
1007
    ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1008
      (&constraints_ps, pol);
1009
    ppl_Pointset_Powerset_C_Polyhedron_intersection_assign
1010
      (SCOP_CONTEXT (scop), constraints_ps);
1011
    ppl_delete_Pointset_Powerset_C_Polyhedron (constraints_ps);
1012
  }
1013
 
1014
  ppl_delete_Polyhedron (pol);
1015
  ppl_delete_Linear_Expression (nb_iters_le);
1016
  ppl_delete_Constraint (ub);
1017
  mpz_clear (val);
1018
}
1019
 
1020
/* Builds the constraint polyhedra for LOOP in SCOP.  OUTER_PH gives
1021
   the constraints for the surrounding loops.  */
1022
 
1023
static void
1024
build_loop_iteration_domains (scop_p scop, struct loop *loop,
1025
                              ppl_Polyhedron_t outer_ph, int nb,
1026
                              ppl_Pointset_Powerset_C_Polyhedron_t *domains)
1027
{
1028
  int i;
1029
  ppl_Polyhedron_t ph;
1030
  tree nb_iters = number_of_latch_executions (loop);
1031
  ppl_dimension_type dim = nb + 1 + scop_nb_params (scop);
1032
  sese region = SCOP_REGION (scop);
1033
 
1034
  {
1035
    ppl_const_Constraint_System_t pcs;
1036
    ppl_dimension_type *map
1037
      = (ppl_dimension_type *) XNEWVEC (ppl_dimension_type, dim);
1038
 
1039
    ppl_new_C_Polyhedron_from_space_dimension (&ph, dim, 0);
1040
    ppl_Polyhedron_get_constraints (outer_ph, &pcs);
1041
    ppl_Polyhedron_add_constraints (ph, pcs);
1042
 
1043
    for (i = 0; i < (int) nb; i++)
1044
      map[i] = i;
1045
    for (i = (int) nb; i < (int) dim - 1; i++)
1046
      map[i] = i + 1;
1047
    map[dim - 1] = nb;
1048
 
1049
    ppl_Polyhedron_map_space_dimensions (ph, map, dim);
1050
    free (map);
1051
  }
1052
 
1053
  /* 0 <= loop_i */
1054
  {
1055
    ppl_Constraint_t lb;
1056
    ppl_Linear_Expression_t lb_expr;
1057
 
1058
    ppl_new_Linear_Expression_with_dimension (&lb_expr, dim);
1059
    ppl_set_coef (lb_expr, nb, 1);
1060
    ppl_new_Constraint (&lb, lb_expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1061
    ppl_delete_Linear_Expression (lb_expr);
1062
    ppl_Polyhedron_add_constraint (ph, lb);
1063
    ppl_delete_Constraint (lb);
1064
  }
1065
 
1066
  if (TREE_CODE (nb_iters) == INTEGER_CST)
1067
    {
1068
      ppl_Constraint_t ub;
1069
      ppl_Linear_Expression_t ub_expr;
1070
 
1071
      ppl_new_Linear_Expression_with_dimension (&ub_expr, dim);
1072
 
1073
      /* loop_i <= cst_nb_iters */
1074
      ppl_set_coef (ub_expr, nb, -1);
1075
      ppl_set_inhomogeneous_tree (ub_expr, nb_iters);
1076
      ppl_new_Constraint (&ub, ub_expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1077
      ppl_Polyhedron_add_constraint (ph, ub);
1078
      ppl_delete_Linear_Expression (ub_expr);
1079
      ppl_delete_Constraint (ub);
1080
    }
1081
  else if (!chrec_contains_undetermined (nb_iters))
1082
    {
1083
      mpz_t one;
1084
      ppl_Constraint_t ub;
1085
      ppl_Linear_Expression_t ub_expr;
1086
      double_int nit;
1087
 
1088
      mpz_init (one);
1089
      mpz_set_si (one, 1);
1090
      ppl_new_Linear_Expression_with_dimension (&ub_expr, dim);
1091
      nb_iters = scalar_evolution_in_region (region, loop, nb_iters);
1092
      scan_tree_for_params (SCOP_REGION (scop), nb_iters, ub_expr, one);
1093
      mpz_clear (one);
1094
 
1095
      if (max_stmt_executions (loop, true, &nit))
1096
        add_upper_bounds_from_estimated_nit (scop, nit, dim, ub_expr);
1097
 
1098
      /* loop_i <= expr_nb_iters */
1099
      ppl_set_coef (ub_expr, nb, -1);
1100
      ppl_new_Constraint (&ub, ub_expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1101
      ppl_Polyhedron_add_constraint (ph, ub);
1102
      ppl_delete_Linear_Expression (ub_expr);
1103
      ppl_delete_Constraint (ub);
1104
    }
1105
  else
1106
    gcc_unreachable ();
1107
 
1108
  if (loop->inner && loop_in_sese_p (loop->inner, region))
1109
    build_loop_iteration_domains (scop, loop->inner, ph, nb + 1, domains);
1110
 
1111
  if (nb != 0
1112
      && loop->next
1113
      && loop_in_sese_p (loop->next, region))
1114
    build_loop_iteration_domains (scop, loop->next, outer_ph, nb, domains);
1115
 
1116
  ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1117
    (&domains[loop->num], ph);
1118
 
1119
  ppl_delete_Polyhedron (ph);
1120
}
1121
 
1122
/* Returns a linear expression for tree T evaluated in PBB.  */
1123
 
1124
static ppl_Linear_Expression_t
1125
create_linear_expr_from_tree (poly_bb_p pbb, tree t)
1126
{
1127
  mpz_t one;
1128
  ppl_Linear_Expression_t res;
1129
  ppl_dimension_type dim;
1130
  sese region = SCOP_REGION (PBB_SCOP (pbb));
1131
  loop_p loop = pbb_loop (pbb);
1132
 
1133
  dim = pbb_dim_iter_domain (pbb) + pbb_nb_params (pbb);
1134
  ppl_new_Linear_Expression_with_dimension (&res, dim);
1135
 
1136
  t = scalar_evolution_in_region (region, loop, t);
1137
  gcc_assert (!automatically_generated_chrec_p (t));
1138
 
1139
  mpz_init (one);
1140
  mpz_set_si (one, 1);
1141
  scan_tree_for_params (region, t, res, one);
1142
  mpz_clear (one);
1143
 
1144
  return res;
1145
}
1146
 
1147
/* Returns the ppl constraint type from the gimple tree code CODE.  */
1148
 
1149
static enum ppl_enum_Constraint_Type
1150
ppl_constraint_type_from_tree_code (enum tree_code code)
1151
{
1152
  switch (code)
1153
    {
1154
    /* We do not support LT and GT to be able to work with C_Polyhedron.
1155
       As we work on integer polyhedron "a < b" can be expressed by
1156
       "a + 1 <= b".  */
1157
    case LT_EXPR:
1158
    case GT_EXPR:
1159
      gcc_unreachable ();
1160
 
1161
    case LE_EXPR:
1162
      return PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL;
1163
 
1164
    case GE_EXPR:
1165
      return PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL;
1166
 
1167
    case EQ_EXPR:
1168
      return PPL_CONSTRAINT_TYPE_EQUAL;
1169
 
1170
    default:
1171
      gcc_unreachable ();
1172
    }
1173
}
1174
 
1175
/* Add conditional statement STMT to PS.  It is evaluated in PBB and
1176
   CODE is used as the comparison operator.  This allows us to invert the
1177
   condition or to handle inequalities.  */
1178
 
1179
static void
1180
add_condition_to_domain (ppl_Pointset_Powerset_C_Polyhedron_t ps, gimple stmt,
1181
                         poly_bb_p pbb, enum tree_code code)
1182
{
1183
  mpz_t v;
1184
  ppl_Coefficient_t c;
1185
  ppl_Linear_Expression_t left, right;
1186
  ppl_Constraint_t cstr;
1187
  enum ppl_enum_Constraint_Type type;
1188
 
1189
  left = create_linear_expr_from_tree (pbb, gimple_cond_lhs (stmt));
1190
  right = create_linear_expr_from_tree (pbb, gimple_cond_rhs (stmt));
1191
 
1192
  /* If we have < or > expressions convert them to <= or >= by adding 1 to
1193
     the left or the right side of the expression. */
1194
  if (code == LT_EXPR)
1195
    {
1196
      mpz_init (v);
1197
      mpz_set_si (v, 1);
1198
      ppl_new_Coefficient (&c);
1199
      ppl_assign_Coefficient_from_mpz_t (c, v);
1200
      ppl_Linear_Expression_add_to_inhomogeneous (left, c);
1201
      ppl_delete_Coefficient (c);
1202
      mpz_clear (v);
1203
 
1204
      code = LE_EXPR;
1205
    }
1206
  else if (code == GT_EXPR)
1207
    {
1208
      mpz_init (v);
1209
      mpz_set_si (v, 1);
1210
      ppl_new_Coefficient (&c);
1211
      ppl_assign_Coefficient_from_mpz_t (c, v);
1212
      ppl_Linear_Expression_add_to_inhomogeneous (right, c);
1213
      ppl_delete_Coefficient (c);
1214
      mpz_clear (v);
1215
 
1216
      code = GE_EXPR;
1217
    }
1218
 
1219
  type = ppl_constraint_type_from_tree_code (code);
1220
 
1221
  ppl_subtract_Linear_Expression_from_Linear_Expression (left, right);
1222
 
1223
  ppl_new_Constraint (&cstr, left, type);
1224
  ppl_Pointset_Powerset_C_Polyhedron_add_constraint (ps, cstr);
1225
 
1226
  ppl_delete_Constraint (cstr);
1227
  ppl_delete_Linear_Expression (left);
1228
  ppl_delete_Linear_Expression (right);
1229
}
1230
 
1231
/* Add conditional statement STMT to pbb.  CODE is used as the comparision
1232
   operator.  This allows us to invert the condition or to handle
1233
   inequalities.  */
1234
 
1235
static void
1236
add_condition_to_pbb (poly_bb_p pbb, gimple stmt, enum tree_code code)
1237
{
1238
  if (code == NE_EXPR)
1239
    {
1240
      ppl_Pointset_Powerset_C_Polyhedron_t left = PBB_DOMAIN (pbb);
1241
      ppl_Pointset_Powerset_C_Polyhedron_t right;
1242
      ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
1243
        (&right, left);
1244
      add_condition_to_domain (left, stmt, pbb, LT_EXPR);
1245
      add_condition_to_domain (right, stmt, pbb, GT_EXPR);
1246
      ppl_Pointset_Powerset_C_Polyhedron_upper_bound_assign (left, right);
1247
      ppl_delete_Pointset_Powerset_C_Polyhedron (right);
1248
    }
1249
  else
1250
    add_condition_to_domain (PBB_DOMAIN (pbb), stmt, pbb, code);
1251
}
1252
 
1253
/* Add conditions to the domain of PBB.  */
1254
 
1255
static void
1256
add_conditions_to_domain (poly_bb_p pbb)
1257
{
1258
  unsigned int i;
1259
  gimple stmt;
1260
  gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
1261
 
1262
  if (VEC_empty (gimple, GBB_CONDITIONS (gbb)))
1263
    return;
1264
 
1265
  FOR_EACH_VEC_ELT (gimple, GBB_CONDITIONS (gbb), i, stmt)
1266
    switch (gimple_code (stmt))
1267
      {
1268
      case GIMPLE_COND:
1269
          {
1270
            enum tree_code code = gimple_cond_code (stmt);
1271
 
1272
            /* The conditions for ELSE-branches are inverted.  */
1273
            if (!VEC_index (gimple, GBB_CONDITION_CASES (gbb), i))
1274
              code = invert_tree_comparison (code, false);
1275
 
1276
            add_condition_to_pbb (pbb, stmt, code);
1277
            break;
1278
          }
1279
 
1280
      case GIMPLE_SWITCH:
1281
        /* Switch statements are not supported right now - fall throught.  */
1282
 
1283
      default:
1284
        gcc_unreachable ();
1285
        break;
1286
      }
1287
}
1288
 
1289
/* Traverses all the GBBs of the SCOP and add their constraints to the
1290
   iteration domains.  */
1291
 
1292
static void
1293
add_conditions_to_constraints (scop_p scop)
1294
{
1295
  int i;
1296
  poly_bb_p pbb;
1297
 
1298
  FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
1299
    add_conditions_to_domain (pbb);
1300
}
1301
 
1302
/* Structure used to pass data to dom_walk.  */
1303
 
1304
struct bsc
1305
{
1306
  VEC (gimple, heap) **conditions, **cases;
1307
  sese region;
1308
};
1309
 
1310
/* Returns a COND_EXPR statement when BB has a single predecessor, the
1311
   edge between BB and its predecessor is not a loop exit edge, and
1312
   the last statement of the single predecessor is a COND_EXPR.  */
1313
 
1314
static gimple
1315
single_pred_cond_non_loop_exit (basic_block bb)
1316
{
1317
  if (single_pred_p (bb))
1318
    {
1319
      edge e = single_pred_edge (bb);
1320
      basic_block pred = e->src;
1321
      gimple stmt;
1322
 
1323
      if (loop_depth (pred->loop_father) > loop_depth (bb->loop_father))
1324
        return NULL;
1325
 
1326
      stmt = last_stmt (pred);
1327
 
1328
      if (stmt && gimple_code (stmt) == GIMPLE_COND)
1329
        return stmt;
1330
    }
1331
 
1332
  return NULL;
1333
}
1334
 
1335
/* Call-back for dom_walk executed before visiting the dominated
1336
   blocks.  */
1337
 
1338
static void
1339
build_sese_conditions_before (struct dom_walk_data *dw_data,
1340
                              basic_block bb)
1341
{
1342
  struct bsc *data = (struct bsc *) dw_data->global_data;
1343
  VEC (gimple, heap) **conditions = data->conditions;
1344
  VEC (gimple, heap) **cases = data->cases;
1345
  gimple_bb_p gbb;
1346
  gimple stmt;
1347
 
1348
  if (!bb_in_sese_p (bb, data->region))
1349
    return;
1350
 
1351
  stmt = single_pred_cond_non_loop_exit (bb);
1352
 
1353
  if (stmt)
1354
    {
1355
      edge e = single_pred_edge (bb);
1356
 
1357
      VEC_safe_push (gimple, heap, *conditions, stmt);
1358
 
1359
      if (e->flags & EDGE_TRUE_VALUE)
1360
        VEC_safe_push (gimple, heap, *cases, stmt);
1361
      else
1362
        VEC_safe_push (gimple, heap, *cases, NULL);
1363
    }
1364
 
1365
  gbb = gbb_from_bb (bb);
1366
 
1367
  if (gbb)
1368
    {
1369
      GBB_CONDITIONS (gbb) = VEC_copy (gimple, heap, *conditions);
1370
      GBB_CONDITION_CASES (gbb) = VEC_copy (gimple, heap, *cases);
1371
    }
1372
}
1373
 
1374
/* Call-back for dom_walk executed after visiting the dominated
1375
   blocks.  */
1376
 
1377
static void
1378
build_sese_conditions_after (struct dom_walk_data *dw_data,
1379
                             basic_block bb)
1380
{
1381
  struct bsc *data = (struct bsc *) dw_data->global_data;
1382
  VEC (gimple, heap) **conditions = data->conditions;
1383
  VEC (gimple, heap) **cases = data->cases;
1384
 
1385
  if (!bb_in_sese_p (bb, data->region))
1386
    return;
1387
 
1388
  if (single_pred_cond_non_loop_exit (bb))
1389
    {
1390
      VEC_pop (gimple, *conditions);
1391
      VEC_pop (gimple, *cases);
1392
    }
1393
}
1394
 
1395
/* Record all conditions in REGION.  */
1396
 
1397
static void
1398
build_sese_conditions (sese region)
1399
{
1400
  struct dom_walk_data walk_data;
1401
  VEC (gimple, heap) *conditions = VEC_alloc (gimple, heap, 3);
1402
  VEC (gimple, heap) *cases = VEC_alloc (gimple, heap, 3);
1403
  struct bsc data;
1404
 
1405
  data.conditions = &conditions;
1406
  data.cases = &cases;
1407
  data.region = region;
1408
 
1409
  walk_data.dom_direction = CDI_DOMINATORS;
1410
  walk_data.initialize_block_local_data = NULL;
1411
  walk_data.before_dom_children = build_sese_conditions_before;
1412
  walk_data.after_dom_children = build_sese_conditions_after;
1413
  walk_data.global_data = &data;
1414
  walk_data.block_local_data_size = 0;
1415
 
1416
  init_walk_dominator_tree (&walk_data);
1417
  walk_dominator_tree (&walk_data, SESE_ENTRY_BB (region));
1418
  fini_walk_dominator_tree (&walk_data);
1419
 
1420
  VEC_free (gimple, heap, conditions);
1421
  VEC_free (gimple, heap, cases);
1422
}
1423
 
1424
/* Add constraints on the possible values of parameter P from the type
1425
   of P.  */
1426
 
1427
static void
1428
add_param_constraints (scop_p scop, ppl_Polyhedron_t context, graphite_dim_t p)
1429
{
1430
  ppl_Constraint_t cstr;
1431
  ppl_Linear_Expression_t le;
1432
  tree parameter = VEC_index (tree, SESE_PARAMS (SCOP_REGION (scop)), p);
1433
  tree type = TREE_TYPE (parameter);
1434
  tree lb = NULL_TREE;
1435
  tree ub = NULL_TREE;
1436
 
1437
  if (POINTER_TYPE_P (type) || !TYPE_MIN_VALUE (type))
1438
    lb = lower_bound_in_type (type, type);
1439
  else
1440
    lb = TYPE_MIN_VALUE (type);
1441
 
1442
  if (POINTER_TYPE_P (type) || !TYPE_MAX_VALUE (type))
1443
    ub = upper_bound_in_type (type, type);
1444
  else
1445
    ub = TYPE_MAX_VALUE (type);
1446
 
1447
  if (lb)
1448
    {
1449
      ppl_new_Linear_Expression_with_dimension (&le, scop_nb_params (scop));
1450
      ppl_set_coef (le, p, -1);
1451
      ppl_set_inhomogeneous_tree (le, lb);
1452
      ppl_new_Constraint (&cstr, le, PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL);
1453
      ppl_Polyhedron_add_constraint (context, cstr);
1454
      ppl_delete_Linear_Expression (le);
1455
      ppl_delete_Constraint (cstr);
1456
    }
1457
 
1458
  if (ub)
1459
    {
1460
      ppl_new_Linear_Expression_with_dimension (&le, scop_nb_params (scop));
1461
      ppl_set_coef (le, p, -1);
1462
      ppl_set_inhomogeneous_tree (le, ub);
1463
      ppl_new_Constraint (&cstr, le, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1464
      ppl_Polyhedron_add_constraint (context, cstr);
1465
      ppl_delete_Linear_Expression (le);
1466
      ppl_delete_Constraint (cstr);
1467
    }
1468
}
1469
 
1470
/* Build the context of the SCOP.  The context usually contains extra
1471
   constraints that are added to the iteration domains that constrain
1472
   some parameters.  */
1473
 
1474
static void
1475
build_scop_context (scop_p scop)
1476
{
1477
  ppl_Polyhedron_t context;
1478
  ppl_Pointset_Powerset_C_Polyhedron_t ps;
1479
  graphite_dim_t p, n = scop_nb_params (scop);
1480
 
1481
  ppl_new_C_Polyhedron_from_space_dimension (&context, n, 0);
1482
 
1483
  for (p = 0; p < n; p++)
1484
    add_param_constraints (scop, context, p);
1485
 
1486
  ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1487
    (&ps, context);
1488
  ppl_Pointset_Powerset_C_Polyhedron_intersection_assign
1489
    (SCOP_CONTEXT (scop), ps);
1490
 
1491
  ppl_delete_Pointset_Powerset_C_Polyhedron (ps);
1492
  ppl_delete_Polyhedron (context);
1493
}
1494
 
1495
/* Build the iteration domains: the loops belonging to the current
1496
   SCOP, and that vary for the execution of the current basic block.
1497
   Returns false if there is no loop in SCOP.  */
1498
 
1499
static void
1500
build_scop_iteration_domain (scop_p scop)
1501
{
1502
  struct loop *loop;
1503
  sese region = SCOP_REGION (scop);
1504
  int i;
1505
  ppl_Polyhedron_t ph;
1506
  poly_bb_p pbb;
1507
  int nb_loops = number_of_loops ();
1508
  ppl_Pointset_Powerset_C_Polyhedron_t *domains
1509
    = XNEWVEC (ppl_Pointset_Powerset_C_Polyhedron_t, nb_loops);
1510
 
1511
  for (i = 0; i < nb_loops; i++)
1512
    domains[i] = NULL;
1513
 
1514
  ppl_new_C_Polyhedron_from_space_dimension (&ph, scop_nb_params (scop), 0);
1515
 
1516
  FOR_EACH_VEC_ELT (loop_p, SESE_LOOP_NEST (region), i, loop)
1517
    if (!loop_in_sese_p (loop_outer (loop), region))
1518
      build_loop_iteration_domains (scop, loop, ph, 0, domains);
1519
 
1520
  FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
1521
    if (domains[gbb_loop (PBB_BLACK_BOX (pbb))->num])
1522
      ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
1523
        (&PBB_DOMAIN (pbb), (ppl_const_Pointset_Powerset_C_Polyhedron_t)
1524
         domains[gbb_loop (PBB_BLACK_BOX (pbb))->num]);
1525
    else
1526
      ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1527
        (&PBB_DOMAIN (pbb), ph);
1528
 
1529
  for (i = 0; i < nb_loops; i++)
1530
    if (domains[i])
1531
      ppl_delete_Pointset_Powerset_C_Polyhedron (domains[i]);
1532
 
1533
  ppl_delete_Polyhedron (ph);
1534
  free (domains);
1535
}
1536
 
1537
/* Add a constrain to the ACCESSES polyhedron for the alias set of
1538
   data reference DR.  ACCESSP_NB_DIMS is the dimension of the
1539
   ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1540
   domain.  */
1541
 
1542
static void
1543
pdr_add_alias_set (ppl_Polyhedron_t accesses, data_reference_p dr,
1544
                   ppl_dimension_type accessp_nb_dims,
1545
                   ppl_dimension_type dom_nb_dims)
1546
{
1547
  ppl_Linear_Expression_t alias;
1548
  ppl_Constraint_t cstr;
1549
  int alias_set_num = 0;
1550
  base_alias_pair *bap = (base_alias_pair *)(dr->aux);
1551
 
1552
  if (bap && bap->alias_set)
1553
    alias_set_num = *(bap->alias_set);
1554
 
1555
  ppl_new_Linear_Expression_with_dimension (&alias, accessp_nb_dims);
1556
 
1557
  ppl_set_coef (alias, dom_nb_dims, 1);
1558
  ppl_set_inhomogeneous (alias, -alias_set_num);
1559
  ppl_new_Constraint (&cstr, alias, PPL_CONSTRAINT_TYPE_EQUAL);
1560
  ppl_Polyhedron_add_constraint (accesses, cstr);
1561
 
1562
  ppl_delete_Linear_Expression (alias);
1563
  ppl_delete_Constraint (cstr);
1564
}
1565
 
1566
/* Add to ACCESSES polyhedron equalities defining the access functions
1567
   to the memory.  ACCESSP_NB_DIMS is the dimension of the ACCESSES
1568
   polyhedron, DOM_NB_DIMS is the dimension of the iteration domain.
1569
   PBB is the poly_bb_p that contains the data reference DR.  */
1570
 
1571
static void
1572
pdr_add_memory_accesses (ppl_Polyhedron_t accesses, data_reference_p dr,
1573
                         ppl_dimension_type accessp_nb_dims,
1574
                         ppl_dimension_type dom_nb_dims,
1575
                         poly_bb_p pbb)
1576
{
1577
  int i, nb_subscripts = DR_NUM_DIMENSIONS (dr);
1578
  mpz_t v;
1579
  scop_p scop = PBB_SCOP (pbb);
1580
  sese region = SCOP_REGION (scop);
1581
 
1582
  mpz_init (v);
1583
 
1584
  for (i = 0; i < nb_subscripts; i++)
1585
    {
1586
      ppl_Linear_Expression_t fn, access;
1587
      ppl_Constraint_t cstr;
1588
      ppl_dimension_type subscript = dom_nb_dims + 1 + i;
1589
      tree afn = DR_ACCESS_FN (dr, nb_subscripts - 1 - i);
1590
 
1591
      ppl_new_Linear_Expression_with_dimension (&fn, dom_nb_dims);
1592
      ppl_new_Linear_Expression_with_dimension (&access, accessp_nb_dims);
1593
 
1594
      mpz_set_si (v, 1);
1595
      scan_tree_for_params (region, afn, fn, v);
1596
      ppl_assign_Linear_Expression_from_Linear_Expression (access, fn);
1597
 
1598
      ppl_set_coef (access, subscript, -1);
1599
      ppl_new_Constraint (&cstr, access, PPL_CONSTRAINT_TYPE_EQUAL);
1600
      ppl_Polyhedron_add_constraint (accesses, cstr);
1601
 
1602
      ppl_delete_Linear_Expression (fn);
1603
      ppl_delete_Linear_Expression (access);
1604
      ppl_delete_Constraint (cstr);
1605
    }
1606
 
1607
  mpz_clear (v);
1608
}
1609
 
1610
/* Add constrains representing the size of the accessed data to the
1611
   ACCESSES polyhedron.  ACCESSP_NB_DIMS is the dimension of the
1612
   ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1613
   domain.  */
1614
 
1615
static void
1616
pdr_add_data_dimensions (ppl_Polyhedron_t accesses, data_reference_p dr,
1617
                         ppl_dimension_type accessp_nb_dims,
1618
                         ppl_dimension_type dom_nb_dims)
1619
{
1620
  tree ref = DR_REF (dr);
1621
  int i, nb_subscripts = DR_NUM_DIMENSIONS (dr);
1622
 
1623
  for (i = nb_subscripts - 1; i >= 0; i--, ref = TREE_OPERAND (ref, 0))
1624
    {
1625
      ppl_Linear_Expression_t expr;
1626
      ppl_Constraint_t cstr;
1627
      ppl_dimension_type subscript = dom_nb_dims + 1 + i;
1628
      tree low, high;
1629
 
1630
      if (TREE_CODE (ref) != ARRAY_REF)
1631
        break;
1632
 
1633
      low = array_ref_low_bound (ref);
1634
 
1635
      /* subscript - low >= 0 */
1636
      if (host_integerp (low, 0))
1637
        {
1638
          tree minus_low;
1639
 
1640
          ppl_new_Linear_Expression_with_dimension (&expr, accessp_nb_dims);
1641
          ppl_set_coef (expr, subscript, 1);
1642
 
1643
          minus_low = fold_build1 (NEGATE_EXPR, TREE_TYPE (low), low);
1644
          ppl_set_inhomogeneous_tree (expr, minus_low);
1645
 
1646
          ppl_new_Constraint (&cstr, expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1647
          ppl_Polyhedron_add_constraint (accesses, cstr);
1648
          ppl_delete_Linear_Expression (expr);
1649
          ppl_delete_Constraint (cstr);
1650
        }
1651
 
1652
      high = array_ref_up_bound (ref);
1653
 
1654
      /* high - subscript >= 0 */
1655
      if (high && host_integerp (high, 0)
1656
          /* 1-element arrays at end of structures may extend over
1657
             their declared size.  */
1658
          && !(array_at_struct_end_p (ref)
1659
               && operand_equal_p (low, high, 0)))
1660
        {
1661
          ppl_new_Linear_Expression_with_dimension (&expr, accessp_nb_dims);
1662
          ppl_set_coef (expr, subscript, -1);
1663
 
1664
          ppl_set_inhomogeneous_tree (expr, high);
1665
 
1666
          ppl_new_Constraint (&cstr, expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1667
          ppl_Polyhedron_add_constraint (accesses, cstr);
1668
          ppl_delete_Linear_Expression (expr);
1669
          ppl_delete_Constraint (cstr);
1670
        }
1671
    }
1672
}
1673
 
1674
/* Build data accesses for DR in PBB.  */
1675
 
1676
static void
1677
build_poly_dr (data_reference_p dr, poly_bb_p pbb)
1678
{
1679
  ppl_Polyhedron_t accesses;
1680
  ppl_Pointset_Powerset_C_Polyhedron_t accesses_ps;
1681
  ppl_dimension_type dom_nb_dims;
1682
  ppl_dimension_type accessp_nb_dims;
1683
  int dr_base_object_set;
1684
 
1685
  ppl_Pointset_Powerset_C_Polyhedron_space_dimension (PBB_DOMAIN (pbb),
1686
                                                      &dom_nb_dims);
1687
  accessp_nb_dims = dom_nb_dims + 1 + DR_NUM_DIMENSIONS (dr);
1688
 
1689
  ppl_new_C_Polyhedron_from_space_dimension (&accesses, accessp_nb_dims, 0);
1690
 
1691
  pdr_add_alias_set (accesses, dr, accessp_nb_dims, dom_nb_dims);
1692
  pdr_add_memory_accesses (accesses, dr, accessp_nb_dims, dom_nb_dims, pbb);
1693
  pdr_add_data_dimensions (accesses, dr, accessp_nb_dims, dom_nb_dims);
1694
 
1695
  ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&accesses_ps,
1696
                                                            accesses);
1697
  ppl_delete_Polyhedron (accesses);
1698
 
1699
  gcc_assert (dr->aux);
1700
  dr_base_object_set = ((base_alias_pair *)(dr->aux))->base_obj_set;
1701
 
1702
  new_poly_dr (pbb, dr_base_object_set, accesses_ps,
1703
               DR_IS_READ (dr) ? PDR_READ : PDR_WRITE,
1704
               dr, DR_NUM_DIMENSIONS (dr));
1705
}
1706
 
1707
/* Write to FILE the alias graph of data references in DIMACS format.  */
1708
 
1709
static inline bool
1710
write_alias_graph_to_ascii_dimacs (FILE *file, char *comment,
1711
                                   VEC (data_reference_p, heap) *drs)
1712
{
1713
  int num_vertex = VEC_length (data_reference_p, drs);
1714
  int edge_num = 0;
1715
  data_reference_p dr1, dr2;
1716
  int i, j;
1717
 
1718
  if (num_vertex == 0)
1719
    return true;
1720
 
1721
  FOR_EACH_VEC_ELT (data_reference_p, drs, i, dr1)
1722
    for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
1723
      if (dr_may_alias_p (dr1, dr2, true))
1724
        edge_num++;
1725
 
1726
  fprintf (file, "$\n");
1727
 
1728
  if (comment)
1729
    fprintf (file, "c %s\n", comment);
1730
 
1731
  fprintf (file, "p edge %d %d\n", num_vertex, edge_num);
1732
 
1733
  FOR_EACH_VEC_ELT (data_reference_p, drs, i, dr1)
1734
    for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
1735
      if (dr_may_alias_p (dr1, dr2, true))
1736
        fprintf (file, "e %d %d\n", i + 1, j + 1);
1737
 
1738
  return true;
1739
}
1740
 
1741
/* Write to FILE the alias graph of data references in DOT format.  */
1742
 
1743
static inline bool
1744
write_alias_graph_to_ascii_dot (FILE *file, char *comment,
1745
                                VEC (data_reference_p, heap) *drs)
1746
{
1747
  int num_vertex = VEC_length (data_reference_p, drs);
1748
  data_reference_p dr1, dr2;
1749
  int i, j;
1750
 
1751
  if (num_vertex == 0)
1752
    return true;
1753
 
1754
  fprintf (file, "$\n");
1755
 
1756
  if (comment)
1757
    fprintf (file, "c %s\n", comment);
1758
 
1759
  /* First print all the vertices.  */
1760
  FOR_EACH_VEC_ELT (data_reference_p, drs, i, dr1)
1761
    fprintf (file, "n%d;\n", i);
1762
 
1763
  FOR_EACH_VEC_ELT (data_reference_p, drs, i, dr1)
1764
    for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
1765
      if (dr_may_alias_p (dr1, dr2, true))
1766
        fprintf (file, "n%d n%d\n", i, j);
1767
 
1768
  return true;
1769
}
1770
 
1771
/* Write to FILE the alias graph of data references in ECC format.  */
1772
 
1773
static inline bool
1774
write_alias_graph_to_ascii_ecc (FILE *file, char *comment,
1775
                                VEC (data_reference_p, heap) *drs)
1776
{
1777
  int num_vertex = VEC_length (data_reference_p, drs);
1778
  data_reference_p dr1, dr2;
1779
  int i, j;
1780
 
1781
  if (num_vertex == 0)
1782
    return true;
1783
 
1784
  fprintf (file, "$\n");
1785
 
1786
  if (comment)
1787
    fprintf (file, "c %s\n", comment);
1788
 
1789
  FOR_EACH_VEC_ELT (data_reference_p, drs, i, dr1)
1790
    for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
1791
      if (dr_may_alias_p (dr1, dr2, true))
1792
        fprintf (file, "%d %d\n", i, j);
1793
 
1794
  return true;
1795
}
1796
 
1797
/* Check if DR1 and DR2 are in the same object set.  */
1798
 
1799
static bool
1800
dr_same_base_object_p (const struct data_reference *dr1,
1801
                       const struct data_reference *dr2)
1802
{
1803
  return operand_equal_p (DR_BASE_OBJECT (dr1), DR_BASE_OBJECT (dr2), 0);
1804
}
1805
 
1806
/* Uses DFS component number as representative of alias-sets. Also tests for
1807
   optimality by verifying if every connected component is a clique. Returns
1808
   true (1) if the above test is true, and false (0) otherwise.  */
1809
 
1810
static int
1811
build_alias_set_optimal_p (VEC (data_reference_p, heap) *drs)
1812
{
1813
  int num_vertices = VEC_length (data_reference_p, drs);
1814
  struct graph *g = new_graph (num_vertices);
1815
  data_reference_p dr1, dr2;
1816
  int i, j;
1817
  int num_connected_components;
1818
  int v_indx1, v_indx2, num_vertices_in_component;
1819
  int *all_vertices;
1820
  int *vertices;
1821
  struct graph_edge *e;
1822
  int this_component_is_clique;
1823
  int all_components_are_cliques = 1;
1824
 
1825
  FOR_EACH_VEC_ELT (data_reference_p, drs, i, dr1)
1826
    for (j = i+1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
1827
      if (dr_may_alias_p (dr1, dr2, true))
1828
        {
1829
          add_edge (g, i, j);
1830
          add_edge (g, j, i);
1831
        }
1832
 
1833
  all_vertices = XNEWVEC (int, num_vertices);
1834
  vertices = XNEWVEC (int, num_vertices);
1835
  for (i = 0; i < num_vertices; i++)
1836
    all_vertices[i] = i;
1837
 
1838
  num_connected_components = graphds_dfs (g, all_vertices, num_vertices,
1839
                                          NULL, true, NULL);
1840
  for (i = 0; i < g->n_vertices; i++)
1841
    {
1842
      data_reference_p dr = VEC_index (data_reference_p, drs, i);
1843
      base_alias_pair *bap;
1844
 
1845
      gcc_assert (dr->aux);
1846
      bap = (base_alias_pair *)(dr->aux);
1847
 
1848
      bap->alias_set = XNEW (int);
1849
      *(bap->alias_set) = g->vertices[i].component + 1;
1850
    }
1851
 
1852
  /* Verify if the DFS numbering results in optimal solution.  */
1853
  for (i = 0; i < num_connected_components; i++)
1854
    {
1855
      num_vertices_in_component = 0;
1856
      /* Get all vertices whose DFS component number is the same as i.  */
1857
      for (j = 0; j < num_vertices; j++)
1858
        if (g->vertices[j].component == i)
1859
          vertices[num_vertices_in_component++] = j;
1860
 
1861
      /* Now test if the vertices in 'vertices' form a clique, by testing
1862
         for edges among each pair.  */
1863
      this_component_is_clique = 1;
1864
      for (v_indx1 = 0; v_indx1 < num_vertices_in_component; v_indx1++)
1865
        {
1866
          for (v_indx2 = v_indx1+1; v_indx2 < num_vertices_in_component; v_indx2++)
1867
            {
1868
              /* Check if the two vertices are connected by iterating
1869
                 through all the edges which have one of these are source.  */
1870
              e = g->vertices[vertices[v_indx2]].pred;
1871
              while (e)
1872
                {
1873
                  if (e->src == vertices[v_indx1])
1874
                    break;
1875
                  e = e->pred_next;
1876
                }
1877
              if (!e)
1878
                {
1879
                  this_component_is_clique = 0;
1880
                  break;
1881
                }
1882
            }
1883
          if (!this_component_is_clique)
1884
            all_components_are_cliques = 0;
1885
        }
1886
    }
1887
 
1888
  free (all_vertices);
1889
  free (vertices);
1890
  free_graph (g);
1891
  return all_components_are_cliques;
1892
}
1893
 
1894
/* Group each data reference in DRS with its base object set num.  */
1895
 
1896
static void
1897
build_base_obj_set_for_drs (VEC (data_reference_p, heap) *drs)
1898
{
1899
  int num_vertex = VEC_length (data_reference_p, drs);
1900
  struct graph *g = new_graph (num_vertex);
1901
  data_reference_p dr1, dr2;
1902
  int i, j;
1903
  int *queue;
1904
 
1905
  FOR_EACH_VEC_ELT (data_reference_p, drs, i, dr1)
1906
    for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
1907
      if (dr_same_base_object_p (dr1, dr2))
1908
        {
1909
          add_edge (g, i, j);
1910
          add_edge (g, j, i);
1911
        }
1912
 
1913
  queue = XNEWVEC (int, num_vertex);
1914
  for (i = 0; i < num_vertex; i++)
1915
    queue[i] = i;
1916
 
1917
  graphds_dfs (g, queue, num_vertex, NULL, true, NULL);
1918
 
1919
  for (i = 0; i < g->n_vertices; i++)
1920
    {
1921
      data_reference_p dr = VEC_index (data_reference_p, drs, i);
1922
      base_alias_pair *bap;
1923
 
1924
      gcc_assert (dr->aux);
1925
      bap = (base_alias_pair *)(dr->aux);
1926
 
1927
      bap->base_obj_set = g->vertices[i].component + 1;
1928
    }
1929
 
1930
  free (queue);
1931
  free_graph (g);
1932
}
1933
 
1934
/* Build the data references for PBB.  */
1935
 
1936
static void
1937
build_pbb_drs (poly_bb_p pbb)
1938
{
1939
  int j;
1940
  data_reference_p dr;
1941
  VEC (data_reference_p, heap) *gbb_drs = GBB_DATA_REFS (PBB_BLACK_BOX (pbb));
1942
 
1943
  FOR_EACH_VEC_ELT (data_reference_p, gbb_drs, j, dr)
1944
    build_poly_dr (dr, pbb);
1945
}
1946
 
1947
/* Dump to file the alias graphs for the data references in DRS.  */
1948
 
1949
static void
1950
dump_alias_graphs (VEC (data_reference_p, heap) *drs)
1951
{
1952
  char comment[100];
1953
  FILE *file_dimacs, *file_ecc, *file_dot;
1954
 
1955
  file_dimacs = fopen ("/tmp/dr_alias_graph_dimacs", "ab");
1956
  if (file_dimacs)
1957
    {
1958
      snprintf (comment, sizeof (comment), "%s %s", main_input_filename,
1959
                current_function_name ());
1960
      write_alias_graph_to_ascii_dimacs (file_dimacs, comment, drs);
1961
      fclose (file_dimacs);
1962
    }
1963
 
1964
  file_ecc = fopen ("/tmp/dr_alias_graph_ecc", "ab");
1965
  if (file_ecc)
1966
    {
1967
      snprintf (comment, sizeof (comment), "%s %s", main_input_filename,
1968
                current_function_name ());
1969
      write_alias_graph_to_ascii_ecc (file_ecc, comment, drs);
1970
      fclose (file_ecc);
1971
    }
1972
 
1973
  file_dot = fopen ("/tmp/dr_alias_graph_dot", "ab");
1974
  if (file_dot)
1975
    {
1976
      snprintf (comment, sizeof (comment), "%s %s", main_input_filename,
1977
                current_function_name ());
1978
      write_alias_graph_to_ascii_dot (file_dot, comment, drs);
1979
      fclose (file_dot);
1980
    }
1981
}
1982
 
1983
/* Build data references in SCOP.  */
1984
 
1985
static void
1986
build_scop_drs (scop_p scop)
1987
{
1988
  int i, j;
1989
  poly_bb_p pbb;
1990
  data_reference_p dr;
1991
  VEC (data_reference_p, heap) *drs = VEC_alloc (data_reference_p, heap, 3);
1992
 
1993
  /* Remove all the PBBs that do not have data references: these basic
1994
     blocks are not handled in the polyhedral representation.  */
1995
  for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
1996
    if (VEC_empty (data_reference_p, GBB_DATA_REFS (PBB_BLACK_BOX (pbb))))
1997
      {
1998
        free_gimple_bb (PBB_BLACK_BOX (pbb));
1999
        VEC_ordered_remove (poly_bb_p, SCOP_BBS (scop), i);
2000
        i--;
2001
      }
2002
 
2003
  FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
2004
    for (j = 0; VEC_iterate (data_reference_p,
2005
                             GBB_DATA_REFS (PBB_BLACK_BOX (pbb)), j, dr); j++)
2006
      VEC_safe_push (data_reference_p, heap, drs, dr);
2007
 
2008
  FOR_EACH_VEC_ELT (data_reference_p, drs, i, dr)
2009
    dr->aux = XNEW (base_alias_pair);
2010
 
2011
  if (!build_alias_set_optimal_p (drs))
2012
    {
2013
      /* TODO: Add support when building alias set is not optimal.  */
2014
      ;
2015
    }
2016
 
2017
  build_base_obj_set_for_drs (drs);
2018
 
2019
  /* When debugging, enable the following code.  This cannot be used
2020
     in production compilers.  */
2021
  if (0)
2022
    dump_alias_graphs (drs);
2023
 
2024
  VEC_free (data_reference_p, heap, drs);
2025
 
2026
  FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
2027
    build_pbb_drs (pbb);
2028
}
2029
 
2030
/* Return a gsi at the position of the phi node STMT.  */
2031
 
2032
static gimple_stmt_iterator
2033
gsi_for_phi_node (gimple stmt)
2034
{
2035
  gimple_stmt_iterator psi;
2036
  basic_block bb = gimple_bb (stmt);
2037
 
2038
  for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
2039
    if (stmt == gsi_stmt (psi))
2040
      return psi;
2041
 
2042
  gcc_unreachable ();
2043
  return psi;
2044
}
2045
 
2046
/* Analyze all the data references of STMTS and add them to the
2047
   GBB_DATA_REFS vector of BB.  */
2048
 
2049
static void
2050
analyze_drs_in_stmts (scop_p scop, basic_block bb, VEC (gimple, heap) *stmts)
2051
{
2052
  loop_p nest;
2053
  gimple_bb_p gbb;
2054
  gimple stmt;
2055
  int i;
2056
  sese region = SCOP_REGION (scop);
2057
 
2058
  if (!bb_in_sese_p (bb, region))
2059
    return;
2060
 
2061
  nest = outermost_loop_in_sese_1 (region, bb);
2062
  gbb = gbb_from_bb (bb);
2063
 
2064
  FOR_EACH_VEC_ELT (gimple, stmts, i, stmt)
2065
    {
2066
      loop_p loop;
2067
 
2068
      if (is_gimple_debug (stmt))
2069
        continue;
2070
 
2071
      loop = loop_containing_stmt (stmt);
2072
      if (!loop_in_sese_p (loop, region))
2073
        loop = nest;
2074
 
2075
      graphite_find_data_references_in_stmt (nest, loop, stmt,
2076
                                             &GBB_DATA_REFS (gbb));
2077
    }
2078
}
2079
 
2080
/* Insert STMT at the end of the STMTS sequence and then insert the
2081
   statements from STMTS at INSERT_GSI and call analyze_drs_in_stmts
2082
   on STMTS.  */
2083
 
2084
static void
2085
insert_stmts (scop_p scop, gimple stmt, gimple_seq stmts,
2086
              gimple_stmt_iterator insert_gsi)
2087
{
2088
  gimple_stmt_iterator gsi;
2089
  VEC (gimple, heap) *x = VEC_alloc (gimple, heap, 3);
2090
 
2091
  if (!stmts)
2092
    stmts = gimple_seq_alloc ();
2093
 
2094
  gsi = gsi_last (stmts);
2095
  gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
2096
  for (gsi = gsi_start (stmts); !gsi_end_p (gsi); gsi_next (&gsi))
2097
    VEC_safe_push (gimple, heap, x, gsi_stmt (gsi));
2098
 
2099
  gsi_insert_seq_before (&insert_gsi, stmts, GSI_SAME_STMT);
2100
  analyze_drs_in_stmts (scop, gsi_bb (insert_gsi), x);
2101
  VEC_free (gimple, heap, x);
2102
}
2103
 
2104
/* Insert the assignment "RES := EXPR" just after AFTER_STMT.  */
2105
 
2106
static void
2107
insert_out_of_ssa_copy (scop_p scop, tree res, tree expr, gimple after_stmt)
2108
{
2109
  gimple_seq stmts;
2110
  gimple_stmt_iterator si;
2111
  gimple_stmt_iterator gsi;
2112
  tree var = force_gimple_operand (expr, &stmts, true, NULL_TREE);
2113
  gimple stmt = gimple_build_assign (res, var);
2114
  VEC (gimple, heap) *x = VEC_alloc (gimple, heap, 3);
2115
 
2116
  if (!stmts)
2117
    stmts = gimple_seq_alloc ();
2118
  si = gsi_last (stmts);
2119
  gsi_insert_after (&si, stmt, GSI_NEW_STMT);
2120
  for (gsi = gsi_start (stmts); !gsi_end_p (gsi); gsi_next (&gsi))
2121
    VEC_safe_push (gimple, heap, x, gsi_stmt (gsi));
2122
 
2123
  if (gimple_code (after_stmt) == GIMPLE_PHI)
2124
    {
2125
      gsi = gsi_after_labels (gimple_bb (after_stmt));
2126
      gsi_insert_seq_before (&gsi, stmts, GSI_NEW_STMT);
2127
    }
2128
  else
2129
    {
2130
      gsi = gsi_for_stmt (after_stmt);
2131
      gsi_insert_seq_after (&gsi, stmts, GSI_NEW_STMT);
2132
    }
2133
 
2134
  analyze_drs_in_stmts (scop, gimple_bb (after_stmt), x);
2135
  VEC_free (gimple, heap, x);
2136
}
2137
 
2138
/* Creates a poly_bb_p for basic_block BB from the existing PBB.  */
2139
 
2140
static void
2141
new_pbb_from_pbb (scop_p scop, poly_bb_p pbb, basic_block bb)
2142
{
2143
  VEC (data_reference_p, heap) *drs = VEC_alloc (data_reference_p, heap, 3);
2144
  gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
2145
  gimple_bb_p gbb1 = new_gimple_bb (bb, drs);
2146
  poly_bb_p pbb1 = new_poly_bb (scop, gbb1);
2147
  int index, n = VEC_length (poly_bb_p, SCOP_BBS (scop));
2148
 
2149
  /* The INDEX of PBB in SCOP_BBS.  */
2150
  for (index = 0; index < n; index++)
2151
    if (VEC_index (poly_bb_p, SCOP_BBS (scop), index) == pbb)
2152
      break;
2153
 
2154
  if (PBB_DOMAIN (pbb))
2155
    ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
2156
      (&PBB_DOMAIN (pbb1), PBB_DOMAIN (pbb));
2157
 
2158
  GBB_PBB (gbb1) = pbb1;
2159
  GBB_CONDITIONS (gbb1) = VEC_copy (gimple, heap, GBB_CONDITIONS (gbb));
2160
  GBB_CONDITION_CASES (gbb1) = VEC_copy (gimple, heap, GBB_CONDITION_CASES (gbb));
2161
  VEC_safe_insert (poly_bb_p, heap, SCOP_BBS (scop), index + 1, pbb1);
2162
}
2163
 
2164
/* Insert on edge E the assignment "RES := EXPR".  */
2165
 
2166
static void
2167
insert_out_of_ssa_copy_on_edge (scop_p scop, edge e, tree res, tree expr)
2168
{
2169
  gimple_stmt_iterator gsi;
2170
  gimple_seq stmts;
2171
  tree var = force_gimple_operand (expr, &stmts, true, NULL_TREE);
2172
  gimple stmt = gimple_build_assign (res, var);
2173
  basic_block bb;
2174
  VEC (gimple, heap) *x = VEC_alloc (gimple, heap, 3);
2175
 
2176
  if (!stmts)
2177
    stmts = gimple_seq_alloc ();
2178
 
2179
  gsi = gsi_last (stmts);
2180
  gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
2181
  for (gsi = gsi_start (stmts); !gsi_end_p (gsi); gsi_next (&gsi))
2182
    VEC_safe_push (gimple, heap, x, gsi_stmt (gsi));
2183
 
2184
  gsi_insert_seq_on_edge (e, stmts);
2185
  gsi_commit_edge_inserts ();
2186
  bb = gimple_bb (stmt);
2187
 
2188
  if (!bb_in_sese_p (bb, SCOP_REGION (scop)))
2189
    return;
2190
 
2191
  if (!gbb_from_bb (bb))
2192
    new_pbb_from_pbb (scop, pbb_from_bb (e->src), bb);
2193
 
2194
  analyze_drs_in_stmts (scop, bb, x);
2195
  VEC_free (gimple, heap, x);
2196
}
2197
 
2198
/* Creates a zero dimension array of the same type as VAR.  */
2199
 
2200
static tree
2201
create_zero_dim_array (tree var, const char *base_name)
2202
{
2203
  tree index_type = build_index_type (integer_zero_node);
2204
  tree elt_type = TREE_TYPE (var);
2205
  tree array_type = build_array_type (elt_type, index_type);
2206
  tree base = create_tmp_var (array_type, base_name);
2207
 
2208
  add_referenced_var (base);
2209
 
2210
  return build4 (ARRAY_REF, elt_type, base, integer_zero_node, NULL_TREE,
2211
                 NULL_TREE);
2212
}
2213
 
2214
/* Returns true when PHI is a loop close phi node.  */
2215
 
2216
static bool
2217
scalar_close_phi_node_p (gimple phi)
2218
{
2219
  if (gimple_code (phi) != GIMPLE_PHI
2220
      || !is_gimple_reg (gimple_phi_result (phi)))
2221
    return false;
2222
 
2223
  /* Note that loop close phi nodes should have a single argument
2224
     because we translated the representation into a canonical form
2225
     before Graphite: see canonicalize_loop_closed_ssa_form.  */
2226
  return (gimple_phi_num_args (phi) == 1);
2227
}
2228
 
2229
/* For a definition DEF in REGION, propagates the expression EXPR in
2230
   all the uses of DEF outside REGION.  */
2231
 
2232
static void
2233
propagate_expr_outside_region (tree def, tree expr, sese region)
2234
{
2235
  imm_use_iterator imm_iter;
2236
  gimple use_stmt;
2237
  gimple_seq stmts;
2238
  bool replaced_once = false;
2239
 
2240
  gcc_assert (TREE_CODE (def) == SSA_NAME);
2241
 
2242
  expr = force_gimple_operand (unshare_expr (expr), &stmts, true,
2243
                               NULL_TREE);
2244
 
2245
  FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def)
2246
    if (!is_gimple_debug (use_stmt)
2247
        && !bb_in_sese_p (gimple_bb (use_stmt), region))
2248
      {
2249
        ssa_op_iter iter;
2250
        use_operand_p use_p;
2251
 
2252
        FOR_EACH_PHI_OR_STMT_USE (use_p, use_stmt, iter, SSA_OP_ALL_USES)
2253
          if (operand_equal_p (def, USE_FROM_PTR (use_p), 0)
2254
              && (replaced_once = true))
2255
            replace_exp (use_p, expr);
2256
 
2257
        update_stmt (use_stmt);
2258
      }
2259
 
2260
  if (replaced_once)
2261
    {
2262
      gsi_insert_seq_on_edge (SESE_ENTRY (region), stmts);
2263
      gsi_commit_edge_inserts ();
2264
    }
2265
}
2266
 
2267
/* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2268
   dimension array for it.  */
2269
 
2270
static void
2271
rewrite_close_phi_out_of_ssa (scop_p scop, gimple_stmt_iterator *psi)
2272
{
2273
  sese region = SCOP_REGION (scop);
2274
  gimple phi = gsi_stmt (*psi);
2275
  tree res = gimple_phi_result (phi);
2276
  tree var = SSA_NAME_VAR (res);
2277
  basic_block bb = gimple_bb (phi);
2278
  gimple_stmt_iterator gsi = gsi_after_labels (bb);
2279
  tree arg = gimple_phi_arg_def (phi, 0);
2280
  gimple stmt;
2281
 
2282
  /* Note that loop close phi nodes should have a single argument
2283
     because we translated the representation into a canonical form
2284
     before Graphite: see canonicalize_loop_closed_ssa_form.  */
2285
  gcc_assert (gimple_phi_num_args (phi) == 1);
2286
 
2287
  /* The phi node can be a non close phi node, when its argument is
2288
     invariant, or a default definition.  */
2289
  if (is_gimple_min_invariant (arg)
2290
      || SSA_NAME_IS_DEFAULT_DEF (arg))
2291
    {
2292
      propagate_expr_outside_region (res, arg, region);
2293
      gsi_next (psi);
2294
      return;
2295
    }
2296
 
2297
  else if (gimple_bb (SSA_NAME_DEF_STMT (arg))->loop_father == bb->loop_father)
2298
    {
2299
      propagate_expr_outside_region (res, arg, region);
2300
      stmt = gimple_build_assign (res, arg);
2301
      remove_phi_node (psi, false);
2302
      gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
2303
      SSA_NAME_DEF_STMT (res) = stmt;
2304
      return;
2305
    }
2306
 
2307
  /* If res is scev analyzable and is not a scalar value, it is safe
2308
     to ignore the close phi node: it will be code generated in the
2309
     out of Graphite pass.  */
2310
  else if (scev_analyzable_p (res, region))
2311
    {
2312
      loop_p loop = loop_containing_stmt (SSA_NAME_DEF_STMT (res));
2313
      tree scev;
2314
 
2315
      if (!loop_in_sese_p (loop, region))
2316
        {
2317
          loop = loop_containing_stmt (SSA_NAME_DEF_STMT (arg));
2318
          scev = scalar_evolution_in_region (region, loop, arg);
2319
          scev = compute_overall_effect_of_inner_loop (loop, scev);
2320
        }
2321
      else
2322
        scev = scalar_evolution_in_region (region, loop, res);
2323
 
2324
      if (tree_does_not_contain_chrecs (scev))
2325
        propagate_expr_outside_region (res, scev, region);
2326
 
2327
      gsi_next (psi);
2328
      return;
2329
    }
2330
  else
2331
    {
2332
      tree zero_dim_array = create_zero_dim_array (var, "Close_Phi");
2333
 
2334
      stmt = gimple_build_assign (res, zero_dim_array);
2335
 
2336
      if (TREE_CODE (arg) == SSA_NAME)
2337
        insert_out_of_ssa_copy (scop, zero_dim_array, arg,
2338
                                SSA_NAME_DEF_STMT (arg));
2339
      else
2340
        insert_out_of_ssa_copy_on_edge (scop, single_pred_edge (bb),
2341
                                        zero_dim_array, arg);
2342
    }
2343
 
2344
  remove_phi_node (psi, false);
2345
  SSA_NAME_DEF_STMT (res) = stmt;
2346
 
2347
  insert_stmts (scop, stmt, NULL, gsi_after_labels (bb));
2348
}
2349
 
2350
/* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2351
   dimension array for it.  */
2352
 
2353
static void
2354
rewrite_phi_out_of_ssa (scop_p scop, gimple_stmt_iterator *psi)
2355
{
2356
  size_t i;
2357
  gimple phi = gsi_stmt (*psi);
2358
  basic_block bb = gimple_bb (phi);
2359
  tree res = gimple_phi_result (phi);
2360
  tree var = SSA_NAME_VAR (res);
2361
  tree zero_dim_array = create_zero_dim_array (var, "phi_out_of_ssa");
2362
  gimple stmt;
2363
  gimple_seq stmts;
2364
 
2365
  for (i = 0; i < gimple_phi_num_args (phi); i++)
2366
    {
2367
      tree arg = gimple_phi_arg_def (phi, i);
2368
      edge e = gimple_phi_arg_edge (phi, i);
2369
 
2370
      /* Avoid the insertion of code in the loop latch to please the
2371
         pattern matching of the vectorizer.  */
2372
      if (TREE_CODE (arg) == SSA_NAME
2373
          && e->src == bb->loop_father->latch)
2374
        insert_out_of_ssa_copy (scop, zero_dim_array, arg,
2375
                                SSA_NAME_DEF_STMT (arg));
2376
      else
2377
        insert_out_of_ssa_copy_on_edge (scop, e, zero_dim_array, arg);
2378
    }
2379
 
2380
  var = force_gimple_operand (zero_dim_array, &stmts, true, NULL_TREE);
2381
 
2382
  stmt = gimple_build_assign (res, var);
2383
  remove_phi_node (psi, false);
2384
  SSA_NAME_DEF_STMT (res) = stmt;
2385
 
2386
  insert_stmts (scop, stmt, stmts, gsi_after_labels (bb));
2387
}
2388
 
2389
/* Rewrite the degenerate phi node at position PSI from the degenerate
2390
   form "x = phi (y, y, ..., y)" to "x = y".  */
2391
 
2392
static void
2393
rewrite_degenerate_phi (gimple_stmt_iterator *psi)
2394
{
2395
  tree rhs;
2396
  gimple stmt;
2397
  gimple_stmt_iterator gsi;
2398
  gimple phi = gsi_stmt (*psi);
2399
  tree res = gimple_phi_result (phi);
2400
  basic_block bb;
2401
 
2402
  bb = gimple_bb (phi);
2403
  rhs = degenerate_phi_result (phi);
2404
  gcc_assert (rhs);
2405
 
2406
  stmt = gimple_build_assign (res, rhs);
2407
  remove_phi_node (psi, false);
2408
  SSA_NAME_DEF_STMT (res) = stmt;
2409
 
2410
  gsi = gsi_after_labels (bb);
2411
  gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
2412
}
2413
 
2414
/* Rewrite out of SSA all the reduction phi nodes of SCOP.  */
2415
 
2416
static void
2417
rewrite_reductions_out_of_ssa (scop_p scop)
2418
{
2419
  basic_block bb;
2420
  gimple_stmt_iterator psi;
2421
  sese region = SCOP_REGION (scop);
2422
 
2423
  FOR_EACH_BB (bb)
2424
    if (bb_in_sese_p (bb, region))
2425
      for (psi = gsi_start_phis (bb); !gsi_end_p (psi);)
2426
        {
2427
          gimple phi = gsi_stmt (psi);
2428
 
2429
          if (!is_gimple_reg (gimple_phi_result (phi)))
2430
            {
2431
              gsi_next (&psi);
2432
              continue;
2433
            }
2434
 
2435
          if (gimple_phi_num_args (phi) > 1
2436
              && degenerate_phi_result (phi))
2437
            rewrite_degenerate_phi (&psi);
2438
 
2439
          else if (scalar_close_phi_node_p (phi))
2440
            rewrite_close_phi_out_of_ssa (scop, &psi);
2441
 
2442
          else if (reduction_phi_p (region, &psi))
2443
            rewrite_phi_out_of_ssa (scop, &psi);
2444
        }
2445
 
2446
  update_ssa (TODO_update_ssa);
2447
#ifdef ENABLE_CHECKING
2448
  verify_loop_closed_ssa (true);
2449
#endif
2450
}
2451
 
2452
/* Rewrite the scalar dependence of DEF used in USE_STMT with a memory
2453
   read from ZERO_DIM_ARRAY.  */
2454
 
2455
static void
2456
rewrite_cross_bb_scalar_dependence (scop_p scop, tree zero_dim_array,
2457
                                    tree def, gimple use_stmt)
2458
{
2459
  tree var = SSA_NAME_VAR (def);
2460
  gimple name_stmt = gimple_build_assign (var, zero_dim_array);
2461
  tree name = make_ssa_name (var, name_stmt);
2462
  ssa_op_iter iter;
2463
  use_operand_p use_p;
2464
 
2465
  gcc_assert (gimple_code (use_stmt) != GIMPLE_PHI);
2466
 
2467
  gimple_assign_set_lhs (name_stmt, name);
2468
  insert_stmts (scop, name_stmt, NULL, gsi_for_stmt (use_stmt));
2469
 
2470
  FOR_EACH_SSA_USE_OPERAND (use_p, use_stmt, iter, SSA_OP_ALL_USES)
2471
    if (operand_equal_p (def, USE_FROM_PTR (use_p), 0))
2472
      replace_exp (use_p, name);
2473
 
2474
  update_stmt (use_stmt);
2475
}
2476
 
2477
/* For every definition DEF in the SCOP that is used outside the scop,
2478
   insert a closing-scop definition in the basic block just after this
2479
   SCOP.  */
2480
 
2481
static void
2482
handle_scalar_deps_crossing_scop_limits (scop_p scop, tree def, gimple stmt)
2483
{
2484
  tree var = create_tmp_reg (TREE_TYPE (def), NULL);
2485
  tree new_name = make_ssa_name (var, stmt);
2486
  bool needs_copy = false;
2487
  use_operand_p use_p;
2488
  imm_use_iterator imm_iter;
2489
  gimple use_stmt;
2490
  sese region = SCOP_REGION (scop);
2491
 
2492
  FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def)
2493
    {
2494
      if (!bb_in_sese_p (gimple_bb (use_stmt), region))
2495
        {
2496
          FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter)
2497
            {
2498
              SET_USE (use_p, new_name);
2499
            }
2500
          update_stmt (use_stmt);
2501
          needs_copy = true;
2502
        }
2503
    }
2504
 
2505
  /* Insert in the empty BB just after the scop a use of DEF such
2506
     that the rewrite of cross_bb_scalar_dependences won't insert
2507
     arrays everywhere else.  */
2508
  if (needs_copy)
2509
    {
2510
      gimple assign = gimple_build_assign (new_name, def);
2511
      gimple_stmt_iterator psi = gsi_after_labels (SESE_EXIT (region)->dest);
2512
 
2513
      add_referenced_var (var);
2514
      SSA_NAME_DEF_STMT (new_name) = assign;
2515
      update_stmt (assign);
2516
      gsi_insert_before (&psi, assign, GSI_SAME_STMT);
2517
    }
2518
}
2519
 
2520
/* Rewrite the scalar dependences crossing the boundary of the BB
2521
   containing STMT with an array.  Return true when something has been
2522
   changed.  */
2523
 
2524
static bool
2525
rewrite_cross_bb_scalar_deps (scop_p scop, gimple_stmt_iterator *gsi)
2526
{
2527
  sese region = SCOP_REGION (scop);
2528
  gimple stmt = gsi_stmt (*gsi);
2529
  imm_use_iterator imm_iter;
2530
  tree def;
2531
  basic_block def_bb;
2532
  tree zero_dim_array = NULL_TREE;
2533
  gimple use_stmt;
2534
  bool res = false;
2535
 
2536
  switch (gimple_code (stmt))
2537
    {
2538
    case GIMPLE_ASSIGN:
2539
      def = gimple_assign_lhs (stmt);
2540
      break;
2541
 
2542
    case GIMPLE_CALL:
2543
      def = gimple_call_lhs (stmt);
2544
      break;
2545
 
2546
    default:
2547
      return false;
2548
    }
2549
 
2550
  if (!def
2551
      || !is_gimple_reg (def))
2552
    return false;
2553
 
2554
  if (scev_analyzable_p (def, region))
2555
    {
2556
      loop_p loop = loop_containing_stmt (SSA_NAME_DEF_STMT (def));
2557
      tree scev = scalar_evolution_in_region (region, loop, def);
2558
 
2559
      if (tree_contains_chrecs (scev, NULL))
2560
        return false;
2561
 
2562
      propagate_expr_outside_region (def, scev, region);
2563
      return true;
2564
    }
2565
 
2566
  def_bb = gimple_bb (stmt);
2567
 
2568
  handle_scalar_deps_crossing_scop_limits (scop, def, stmt);
2569
 
2570
  FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def)
2571
    if (gimple_code (use_stmt) == GIMPLE_PHI
2572
        && (res = true))
2573
      {
2574
        gimple_stmt_iterator psi = gsi_for_stmt (use_stmt);
2575
 
2576
        if (scalar_close_phi_node_p (gsi_stmt (psi)))
2577
          rewrite_close_phi_out_of_ssa (scop, &psi);
2578
        else
2579
          rewrite_phi_out_of_ssa (scop, &psi);
2580
      }
2581
 
2582
  FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def)
2583
    if (gimple_code (use_stmt) != GIMPLE_PHI
2584
        && def_bb != gimple_bb (use_stmt)
2585
        && !is_gimple_debug (use_stmt)
2586
        && (res = true))
2587
      {
2588
        if (!zero_dim_array)
2589
          {
2590
            zero_dim_array = create_zero_dim_array
2591
              (SSA_NAME_VAR (def), "Cross_BB_scalar_dependence");
2592
            insert_out_of_ssa_copy (scop, zero_dim_array, def,
2593
                                    SSA_NAME_DEF_STMT (def));
2594
            gsi_next (gsi);
2595
          }
2596
 
2597
        rewrite_cross_bb_scalar_dependence (scop, zero_dim_array,
2598
                                            def, use_stmt);
2599
      }
2600
 
2601
  return res;
2602
}
2603
 
2604
/* Rewrite out of SSA all the reduction phi nodes of SCOP.  */
2605
 
2606
static void
2607
rewrite_cross_bb_scalar_deps_out_of_ssa (scop_p scop)
2608
{
2609
  basic_block bb;
2610
  gimple_stmt_iterator psi;
2611
  sese region = SCOP_REGION (scop);
2612
  bool changed = false;
2613
 
2614
  /* Create an extra empty BB after the scop.  */
2615
  split_edge (SESE_EXIT (region));
2616
 
2617
  FOR_EACH_BB (bb)
2618
    if (bb_in_sese_p (bb, region))
2619
      for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi))
2620
        changed |= rewrite_cross_bb_scalar_deps (scop, &psi);
2621
 
2622
  if (changed)
2623
    {
2624
      scev_reset_htab ();
2625
      update_ssa (TODO_update_ssa);
2626
#ifdef ENABLE_CHECKING
2627
      verify_loop_closed_ssa (true);
2628
#endif
2629
    }
2630
}
2631
 
2632
/* Returns the number of pbbs that are in loops contained in SCOP.  */
2633
 
2634
static int
2635
nb_pbbs_in_loops (scop_p scop)
2636
{
2637
  int i;
2638
  poly_bb_p pbb;
2639
  int res = 0;
2640
 
2641
  FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
2642
    if (loop_in_sese_p (gbb_loop (PBB_BLACK_BOX (pbb)), SCOP_REGION (scop)))
2643
      res++;
2644
 
2645
  return res;
2646
}
2647
 
2648
/* Return the number of data references in BB that write in
2649
   memory.  */
2650
 
2651
static int
2652
nb_data_writes_in_bb (basic_block bb)
2653
{
2654
  int res = 0;
2655
  gimple_stmt_iterator gsi;
2656
 
2657
  for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2658
    if (gimple_vdef (gsi_stmt (gsi)))
2659
      res++;
2660
 
2661
  return res;
2662
}
2663
 
2664
/* Splits at STMT the basic block BB represented as PBB in the
2665
   polyhedral form.  */
2666
 
2667
static edge
2668
split_pbb (scop_p scop, poly_bb_p pbb, basic_block bb, gimple stmt)
2669
{
2670
  edge e1 = split_block (bb, stmt);
2671
  new_pbb_from_pbb (scop, pbb, e1->dest);
2672
  return e1;
2673
}
2674
 
2675
/* Splits STMT out of its current BB.  This is done for reduction
2676
   statements for which we want to ignore data dependences.  */
2677
 
2678
static basic_block
2679
split_reduction_stmt (scop_p scop, gimple stmt)
2680
{
2681
  basic_block bb = gimple_bb (stmt);
2682
  poly_bb_p pbb = pbb_from_bb (bb);
2683
  gimple_bb_p gbb = gbb_from_bb (bb);
2684
  edge e1;
2685
  int i;
2686
  data_reference_p dr;
2687
 
2688
  /* Do not split basic blocks with no writes to memory: the reduction
2689
     will be the only write to memory.  */
2690
  if (nb_data_writes_in_bb (bb) == 0
2691
      /* Or if we have already marked BB as a reduction.  */
2692
      || PBB_IS_REDUCTION (pbb_from_bb (bb)))
2693
    return bb;
2694
 
2695
  e1 = split_pbb (scop, pbb, bb, stmt);
2696
 
2697
  /* Split once more only when the reduction stmt is not the only one
2698
     left in the original BB.  */
2699
  if (!gsi_one_before_end_p (gsi_start_nondebug_bb (bb)))
2700
    {
2701
      gimple_stmt_iterator gsi = gsi_last_bb (bb);
2702
      gsi_prev (&gsi);
2703
      e1 = split_pbb (scop, pbb, bb, gsi_stmt (gsi));
2704
    }
2705
 
2706
  /* A part of the data references will end in a different basic block
2707
     after the split: move the DRs from the original GBB to the newly
2708
     created GBB1.  */
2709
  FOR_EACH_VEC_ELT (data_reference_p, GBB_DATA_REFS (gbb), i, dr)
2710
    {
2711
      basic_block bb1 = gimple_bb (DR_STMT (dr));
2712
 
2713
      if (bb1 != bb)
2714
        {
2715
          gimple_bb_p gbb1 = gbb_from_bb (bb1);
2716
          VEC_safe_push (data_reference_p, heap, GBB_DATA_REFS (gbb1), dr);
2717
          VEC_ordered_remove (data_reference_p, GBB_DATA_REFS (gbb), i);
2718
          i--;
2719
        }
2720
    }
2721
 
2722
  return e1->dest;
2723
}
2724
 
2725
/* Return true when stmt is a reduction operation.  */
2726
 
2727
static inline bool
2728
is_reduction_operation_p (gimple stmt)
2729
{
2730
  enum tree_code code;
2731
 
2732
  gcc_assert (is_gimple_assign (stmt));
2733
  code = gimple_assign_rhs_code (stmt);
2734
 
2735
  return flag_associative_math
2736
    && commutative_tree_code (code)
2737
    && associative_tree_code (code);
2738
}
2739
 
2740
/* Returns true when PHI contains an argument ARG.  */
2741
 
2742
static bool
2743
phi_contains_arg (gimple phi, tree arg)
2744
{
2745
  size_t i;
2746
 
2747
  for (i = 0; i < gimple_phi_num_args (phi); i++)
2748
    if (operand_equal_p (arg, gimple_phi_arg_def (phi, i), 0))
2749
      return true;
2750
 
2751
  return false;
2752
}
2753
 
2754
/* Return a loop phi node that corresponds to a reduction containing LHS.  */
2755
 
2756
static gimple
2757
follow_ssa_with_commutative_ops (tree arg, tree lhs)
2758
{
2759
  gimple stmt;
2760
 
2761
  if (TREE_CODE (arg) != SSA_NAME)
2762
    return NULL;
2763
 
2764
  stmt = SSA_NAME_DEF_STMT (arg);
2765
 
2766
  if (gimple_code (stmt) == GIMPLE_NOP
2767
      || gimple_code (stmt) == GIMPLE_CALL)
2768
    return NULL;
2769
 
2770
  if (gimple_code (stmt) == GIMPLE_PHI)
2771
    {
2772
      if (phi_contains_arg (stmt, lhs))
2773
        return stmt;
2774
      return NULL;
2775
    }
2776
 
2777
  if (!is_gimple_assign (stmt))
2778
    return NULL;
2779
 
2780
  if (gimple_num_ops (stmt) == 2)
2781
    return follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt), lhs);
2782
 
2783
  if (is_reduction_operation_p (stmt))
2784
    {
2785
      gimple res = follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt), lhs);
2786
 
2787
      return res ? res :
2788
        follow_ssa_with_commutative_ops (gimple_assign_rhs2 (stmt), lhs);
2789
    }
2790
 
2791
  return NULL;
2792
}
2793
 
2794
/* Detect commutative and associative scalar reductions starting at
2795
   the STMT.  Return the phi node of the reduction cycle, or NULL.  */
2796
 
2797
static gimple
2798
detect_commutative_reduction_arg (tree lhs, gimple stmt, tree arg,
2799
                                  VEC (gimple, heap) **in,
2800
                                  VEC (gimple, heap) **out)
2801
{
2802
  gimple phi = follow_ssa_with_commutative_ops (arg, lhs);
2803
 
2804
  if (!phi)
2805
    return NULL;
2806
 
2807
  VEC_safe_push (gimple, heap, *in, stmt);
2808
  VEC_safe_push (gimple, heap, *out, stmt);
2809
  return phi;
2810
}
2811
 
2812
/* Detect commutative and associative scalar reductions starting at
2813
   STMT.  Return the phi node of the reduction cycle, or NULL.  */
2814
 
2815
static gimple
2816
detect_commutative_reduction_assign (gimple stmt, VEC (gimple, heap) **in,
2817
                                     VEC (gimple, heap) **out)
2818
{
2819
  tree lhs = gimple_assign_lhs (stmt);
2820
 
2821
  if (gimple_num_ops (stmt) == 2)
2822
    return detect_commutative_reduction_arg (lhs, stmt,
2823
                                             gimple_assign_rhs1 (stmt),
2824
                                             in, out);
2825
 
2826
  if (is_reduction_operation_p (stmt))
2827
    {
2828
      gimple res = detect_commutative_reduction_arg (lhs, stmt,
2829
                                                     gimple_assign_rhs1 (stmt),
2830
                                                     in, out);
2831
      return res ? res
2832
        : detect_commutative_reduction_arg (lhs, stmt,
2833
                                            gimple_assign_rhs2 (stmt),
2834
                                            in, out);
2835
    }
2836
 
2837
  return NULL;
2838
}
2839
 
2840
/* Return a loop phi node that corresponds to a reduction containing LHS.  */
2841
 
2842
static gimple
2843
follow_inital_value_to_phi (tree arg, tree lhs)
2844
{
2845
  gimple stmt;
2846
 
2847
  if (!arg || TREE_CODE (arg) != SSA_NAME)
2848
    return NULL;
2849
 
2850
  stmt = SSA_NAME_DEF_STMT (arg);
2851
 
2852
  if (gimple_code (stmt) == GIMPLE_PHI
2853
      && phi_contains_arg (stmt, lhs))
2854
    return stmt;
2855
 
2856
  return NULL;
2857
}
2858
 
2859
 
2860
/* Return the argument of the loop PHI that is the inital value coming
2861
   from outside the loop.  */
2862
 
2863
static edge
2864
edge_initial_value_for_loop_phi (gimple phi)
2865
{
2866
  size_t i;
2867
 
2868
  for (i = 0; i < gimple_phi_num_args (phi); i++)
2869
    {
2870
      edge e = gimple_phi_arg_edge (phi, i);
2871
 
2872
      if (loop_depth (e->src->loop_father)
2873
          < loop_depth (e->dest->loop_father))
2874
        return e;
2875
    }
2876
 
2877
  return NULL;
2878
}
2879
 
2880
/* Return the argument of the loop PHI that is the inital value coming
2881
   from outside the loop.  */
2882
 
2883
static tree
2884
initial_value_for_loop_phi (gimple phi)
2885
{
2886
  size_t i;
2887
 
2888
  for (i = 0; i < gimple_phi_num_args (phi); i++)
2889
    {
2890
      edge e = gimple_phi_arg_edge (phi, i);
2891
 
2892
      if (loop_depth (e->src->loop_father)
2893
          < loop_depth (e->dest->loop_father))
2894
        return gimple_phi_arg_def (phi, i);
2895
    }
2896
 
2897
  return NULL_TREE;
2898
}
2899
 
2900
/* Returns true when DEF is used outside the reduction cycle of
2901
   LOOP_PHI.  */
2902
 
2903
static bool
2904
used_outside_reduction (tree def, gimple loop_phi)
2905
{
2906
  use_operand_p use_p;
2907
  imm_use_iterator imm_iter;
2908
  loop_p loop = loop_containing_stmt (loop_phi);
2909
 
2910
  /* In LOOP, DEF should be used only in LOOP_PHI.  */
2911
  FOR_EACH_IMM_USE_FAST (use_p, imm_iter, def)
2912
    {
2913
      gimple stmt = USE_STMT (use_p);
2914
 
2915
      if (stmt != loop_phi
2916
          && !is_gimple_debug (stmt)
2917
          && flow_bb_inside_loop_p (loop, gimple_bb (stmt)))
2918
        return true;
2919
    }
2920
 
2921
  return false;
2922
}
2923
 
2924
/* Detect commutative and associative scalar reductions belonging to
2925
   the SCOP starting at the loop closed phi node STMT.  Return the phi
2926
   node of the reduction cycle, or NULL.  */
2927
 
2928
static gimple
2929
detect_commutative_reduction (scop_p scop, gimple stmt, VEC (gimple, heap) **in,
2930
                              VEC (gimple, heap) **out)
2931
{
2932
  if (scalar_close_phi_node_p (stmt))
2933
    {
2934
      gimple def, loop_phi, phi, close_phi = stmt;
2935
      tree init, lhs, arg = gimple_phi_arg_def (close_phi, 0);
2936
 
2937
      if (TREE_CODE (arg) != SSA_NAME)
2938
        return NULL;
2939
 
2940
      /* Note that loop close phi nodes should have a single argument
2941
         because we translated the representation into a canonical form
2942
         before Graphite: see canonicalize_loop_closed_ssa_form.  */
2943
      gcc_assert (gimple_phi_num_args (close_phi) == 1);
2944
 
2945
      def = SSA_NAME_DEF_STMT (arg);
2946
      if (!stmt_in_sese_p (def, SCOP_REGION (scop))
2947
          || !(loop_phi = detect_commutative_reduction (scop, def, in, out)))
2948
        return NULL;
2949
 
2950
      lhs = gimple_phi_result (close_phi);
2951
      init = initial_value_for_loop_phi (loop_phi);
2952
      phi = follow_inital_value_to_phi (init, lhs);
2953
 
2954
      if (phi && (used_outside_reduction (lhs, phi)
2955
                  || !has_single_use (gimple_phi_result (phi))))
2956
        return NULL;
2957
 
2958
      VEC_safe_push (gimple, heap, *in, loop_phi);
2959
      VEC_safe_push (gimple, heap, *out, close_phi);
2960
      return phi;
2961
    }
2962
 
2963
  if (gimple_code (stmt) == GIMPLE_ASSIGN)
2964
    return detect_commutative_reduction_assign (stmt, in, out);
2965
 
2966
  return NULL;
2967
}
2968
 
2969
/* Translate the scalar reduction statement STMT to an array RED
2970
   knowing that its recursive phi node is LOOP_PHI.  */
2971
 
2972
static void
2973
translate_scalar_reduction_to_array_for_stmt (scop_p scop, tree red,
2974
                                              gimple stmt, gimple loop_phi)
2975
{
2976
  tree res = gimple_phi_result (loop_phi);
2977
  gimple assign = gimple_build_assign (res, unshare_expr (red));
2978
  gimple_stmt_iterator gsi;
2979
 
2980
  insert_stmts (scop, assign, NULL, gsi_after_labels (gimple_bb (loop_phi)));
2981
 
2982
  assign = gimple_build_assign (unshare_expr (red), gimple_assign_lhs (stmt));
2983
  gsi = gsi_for_stmt (stmt);
2984
  gsi_next (&gsi);
2985
  insert_stmts (scop, assign, NULL, gsi);
2986
}
2987
 
2988
/* Removes the PHI node and resets all the debug stmts that are using
2989
   the PHI_RESULT.  */
2990
 
2991
static void
2992
remove_phi (gimple phi)
2993
{
2994
  imm_use_iterator imm_iter;
2995
  tree def;
2996
  use_operand_p use_p;
2997
  gimple_stmt_iterator gsi;
2998
  VEC (gimple, heap) *update = VEC_alloc (gimple, heap, 3);
2999
  unsigned int i;
3000
  gimple stmt;
3001
 
3002
  def = PHI_RESULT (phi);
3003
  FOR_EACH_IMM_USE_FAST (use_p, imm_iter, def)
3004
    {
3005
      stmt = USE_STMT (use_p);
3006
 
3007
      if (is_gimple_debug (stmt))
3008
        {
3009
          gimple_debug_bind_reset_value (stmt);
3010
          VEC_safe_push (gimple, heap, update, stmt);
3011
        }
3012
    }
3013
 
3014
  FOR_EACH_VEC_ELT (gimple, update, i, stmt)
3015
    update_stmt (stmt);
3016
 
3017
  VEC_free (gimple, heap, update);
3018
 
3019
  gsi = gsi_for_phi_node (phi);
3020
  remove_phi_node (&gsi, false);
3021
}
3022
 
3023
/* Helper function for for_each_index.  For each INDEX of the data
3024
   reference REF, returns true when its indices are valid in the loop
3025
   nest LOOP passed in as DATA.  */
3026
 
3027
static bool
3028
dr_indices_valid_in_loop (tree ref ATTRIBUTE_UNUSED, tree *index, void *data)
3029
{
3030
  loop_p loop;
3031
  basic_block header, def_bb;
3032
  gimple stmt;
3033
 
3034
  if (TREE_CODE (*index) != SSA_NAME)
3035
    return true;
3036
 
3037
  loop = *((loop_p *) data);
3038
  header = loop->header;
3039
  stmt = SSA_NAME_DEF_STMT (*index);
3040
 
3041
  if (!stmt)
3042
    return true;
3043
 
3044
  def_bb = gimple_bb (stmt);
3045
 
3046
  if (!def_bb)
3047
    return true;
3048
 
3049
  return dominated_by_p (CDI_DOMINATORS, header, def_bb);
3050
}
3051
 
3052
/* When the result of a CLOSE_PHI is written to a memory location,
3053
   return a pointer to that memory reference, otherwise return
3054
   NULL_TREE.  */
3055
 
3056
static tree
3057
close_phi_written_to_memory (gimple close_phi)
3058
{
3059
  imm_use_iterator imm_iter;
3060
  use_operand_p use_p;
3061
  gimple stmt;
3062
  tree res, def = gimple_phi_result (close_phi);
3063
 
3064
  FOR_EACH_IMM_USE_FAST (use_p, imm_iter, def)
3065
    if ((stmt = USE_STMT (use_p))
3066
        && gimple_code (stmt) == GIMPLE_ASSIGN
3067
        && (res = gimple_assign_lhs (stmt)))
3068
      {
3069
        switch (TREE_CODE (res))
3070
          {
3071
          case VAR_DECL:
3072
          case PARM_DECL:
3073
          case RESULT_DECL:
3074
            return res;
3075
 
3076
          case ARRAY_REF:
3077
          case MEM_REF:
3078
            {
3079
              tree arg = gimple_phi_arg_def (close_phi, 0);
3080
              loop_p nest = loop_containing_stmt (SSA_NAME_DEF_STMT (arg));
3081
 
3082
              /* FIXME: this restriction is for id-{24,25}.f and
3083
                 could be handled by duplicating the computation of
3084
                 array indices before the loop of the close_phi.  */
3085
              if (for_each_index (&res, dr_indices_valid_in_loop, &nest))
3086
                return res;
3087
            }
3088
            /* Fallthru.  */
3089
 
3090
          default:
3091
            continue;
3092
          }
3093
      }
3094
  return NULL_TREE;
3095
}
3096
 
3097
/* Rewrite out of SSA the reduction described by the loop phi nodes
3098
   IN, and the close phi nodes OUT.  IN and OUT are structured by loop
3099
   levels like this:
3100
 
3101
   IN: stmt, loop_n, ..., loop_0
3102
   OUT: stmt, close_n, ..., close_0
3103
 
3104
   the first element is the reduction statement, and the next elements
3105
   are the loop and close phi nodes of each of the outer loops.  */
3106
 
3107
static void
3108
translate_scalar_reduction_to_array (scop_p scop,
3109
                                     VEC (gimple, heap) *in,
3110
                                     VEC (gimple, heap) *out)
3111
{
3112
  gimple loop_phi;
3113
  unsigned int i = VEC_length (gimple, out) - 1;
3114
  tree red = close_phi_written_to_memory (VEC_index (gimple, out, i));
3115
 
3116
  FOR_EACH_VEC_ELT (gimple, in, i, loop_phi)
3117
    {
3118
      gimple close_phi = VEC_index (gimple, out, i);
3119
 
3120
      if (i == 0)
3121
        {
3122
          gimple stmt = loop_phi;
3123
          basic_block bb = split_reduction_stmt (scop, stmt);
3124
          poly_bb_p pbb = pbb_from_bb (bb);
3125
          PBB_IS_REDUCTION (pbb) = true;
3126
          gcc_assert (close_phi == loop_phi);
3127
 
3128
          if (!red)
3129
            red = create_zero_dim_array
3130
              (gimple_assign_lhs (stmt), "Commutative_Associative_Reduction");
3131
 
3132
          translate_scalar_reduction_to_array_for_stmt
3133
            (scop, red, stmt, VEC_index (gimple, in, 1));
3134
          continue;
3135
        }
3136
 
3137
      if (i == VEC_length (gimple, in) - 1)
3138
        {
3139
          insert_out_of_ssa_copy (scop, gimple_phi_result (close_phi),
3140
                                  unshare_expr (red), close_phi);
3141
          insert_out_of_ssa_copy_on_edge
3142
            (scop, edge_initial_value_for_loop_phi (loop_phi),
3143
             unshare_expr (red), initial_value_for_loop_phi (loop_phi));
3144
        }
3145
 
3146
      remove_phi (loop_phi);
3147
      remove_phi (close_phi);
3148
    }
3149
}
3150
 
3151
/* Rewrites out of SSA a commutative reduction at CLOSE_PHI.  Returns
3152
   true when something has been changed.  */
3153
 
3154
static bool
3155
rewrite_commutative_reductions_out_of_ssa_close_phi (scop_p scop,
3156
                                                     gimple close_phi)
3157
{
3158
  bool res;
3159
  VEC (gimple, heap) *in = VEC_alloc (gimple, heap, 10);
3160
  VEC (gimple, heap) *out = VEC_alloc (gimple, heap, 10);
3161
 
3162
  detect_commutative_reduction (scop, close_phi, &in, &out);
3163
  res = VEC_length (gimple, in) > 1;
3164
  if (res)
3165
    translate_scalar_reduction_to_array (scop, in, out);
3166
 
3167
  VEC_free (gimple, heap, in);
3168
  VEC_free (gimple, heap, out);
3169
  return res;
3170
}
3171
 
3172
/* Rewrites all the commutative reductions from LOOP out of SSA.
3173
   Returns true when something has been changed.  */
3174
 
3175
static bool
3176
rewrite_commutative_reductions_out_of_ssa_loop (scop_p scop,
3177
                                                loop_p loop)
3178
{
3179
  gimple_stmt_iterator gsi;
3180
  edge exit = single_exit (loop);
3181
  tree res;
3182
  bool changed = false;
3183
 
3184
  if (!exit)
3185
    return false;
3186
 
3187
  for (gsi = gsi_start_phis (exit->dest); !gsi_end_p (gsi); gsi_next (&gsi))
3188
    if ((res = gimple_phi_result (gsi_stmt (gsi)))
3189
        && is_gimple_reg (res)
3190
        && !scev_analyzable_p (res, SCOP_REGION (scop)))
3191
      changed |= rewrite_commutative_reductions_out_of_ssa_close_phi
3192
        (scop, gsi_stmt (gsi));
3193
 
3194
  return changed;
3195
}
3196
 
3197
/* Rewrites all the commutative reductions from SCOP out of SSA.  */
3198
 
3199
static void
3200
rewrite_commutative_reductions_out_of_ssa (scop_p scop)
3201
{
3202
  loop_iterator li;
3203
  loop_p loop;
3204
  bool changed = false;
3205
  sese region = SCOP_REGION (scop);
3206
 
3207
  FOR_EACH_LOOP (li, loop, 0)
3208
    if (loop_in_sese_p (loop, region))
3209
      changed |= rewrite_commutative_reductions_out_of_ssa_loop (scop, loop);
3210
 
3211
  if (changed)
3212
    {
3213
      scev_reset_htab ();
3214
      gsi_commit_edge_inserts ();
3215
      update_ssa (TODO_update_ssa);
3216
#ifdef ENABLE_CHECKING
3217
      verify_loop_closed_ssa (true);
3218
#endif
3219
    }
3220
}
3221
 
3222
/* Can all ivs be represented by a signed integer?
3223
   As CLooG might generate negative values in its expressions, signed loop ivs
3224
   are required in the backend. */
3225
 
3226
static bool
3227
scop_ivs_can_be_represented (scop_p scop)
3228
{
3229
  loop_iterator li;
3230
  loop_p loop;
3231
  gimple_stmt_iterator psi;
3232
 
3233
  FOR_EACH_LOOP (li, loop, 0)
3234
    {
3235
      if (!loop_in_sese_p (loop, SCOP_REGION (scop)))
3236
        continue;
3237
 
3238
      for (psi = gsi_start_phis (loop->header);
3239
           !gsi_end_p (psi); gsi_next (&psi))
3240
        {
3241
          gimple phi = gsi_stmt (psi);
3242
          tree res = PHI_RESULT (phi);
3243
          tree type = TREE_TYPE (res);
3244
 
3245
          if (TYPE_UNSIGNED (type)
3246
              && TYPE_PRECISION (type) >= TYPE_PRECISION (long_long_integer_type_node))
3247
            return false;
3248
        }
3249
    }
3250
 
3251
  return true;
3252
}
3253
 
3254
/* Builds the polyhedral representation for a SESE region.  */
3255
 
3256
void
3257
build_poly_scop (scop_p scop)
3258
{
3259
  sese region = SCOP_REGION (scop);
3260
  graphite_dim_t max_dim;
3261
 
3262
  build_scop_bbs (scop);
3263
 
3264
  /* FIXME: This restriction is needed to avoid a problem in CLooG.
3265
     Once CLooG is fixed, remove this guard.  Anyways, it makes no
3266
     sense to optimize a scop containing only PBBs that do not belong
3267
     to any loops.  */
3268
  if (nb_pbbs_in_loops (scop) == 0)
3269
    return;
3270
 
3271
  if (!scop_ivs_can_be_represented (scop))
3272
    return;
3273
 
3274
  if (flag_associative_math)
3275
    rewrite_commutative_reductions_out_of_ssa (scop);
3276
 
3277
  build_sese_loop_nests (region);
3278
  build_sese_conditions (region);
3279
  find_scop_parameters (scop);
3280
 
3281
  max_dim = PARAM_VALUE (PARAM_GRAPHITE_MAX_NB_SCOP_PARAMS);
3282
  if (scop_nb_params (scop) > max_dim)
3283
    return;
3284
 
3285
  build_scop_iteration_domain (scop);
3286
  build_scop_context (scop);
3287
  add_conditions_to_constraints (scop);
3288
 
3289
  /* Rewrite out of SSA only after having translated the
3290
     representation to the polyhedral representation to avoid scev
3291
     analysis failures.  That means that these functions will insert
3292
     new data references that they create in the right place.  */
3293
  rewrite_reductions_out_of_ssa (scop);
3294
  rewrite_cross_bb_scalar_deps_out_of_ssa (scop);
3295
 
3296
  build_scop_drs (scop);
3297
  scop_to_lst (scop);
3298
  build_scop_scattering (scop);
3299
 
3300
  /* This SCoP has been translated to the polyhedral
3301
     representation.  */
3302
  POLY_SCOP_P (scop) = true;
3303
}
3304
#endif

powered by: WebSVN 2.1.0

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