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

Subversion Repositories openrisc_me

[/] [openrisc/] [trunk/] [gnu-src/] [gcc-4.5.1/] [gcc/] [graphite-sese-to-poly.c] - Blame information for rev 280

Details | Compare with Previous | View Log

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

powered by: WebSVN 2.1.0

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