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

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [gcc/] [graphite-clast-to-gimple.c] - Blame information for rev 707

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

Line No. Rev Author Line
1 684 jeremybenn
/* Translation of CLAST (CLooG AST) to Gimple.
2
   Copyright (C) 2009, 2010, 2011 Free Software Foundation, Inc.
3
   Contributed by Sebastian Pop <sebastian.pop@amd.com>.
4
 
5
This file is part of GCC.
6
 
7
GCC is free software; you can redistribute it and/or modify
8
it under the terms of the GNU General Public License as published by
9
the Free Software Foundation; either version 3, or (at your option)
10
any later version.
11
 
12
GCC is distributed in the hope that it will be useful,
13
but WITHOUT ANY WARRANTY; without even the implied warranty of
14
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15
GNU General Public License for more details.
16
 
17
You should have received a copy of the GNU General Public License
18
along with GCC; see the file COPYING3.  If not see
19
<http://www.gnu.org/licenses/>.  */
20
 
21
#include "config.h"
22
#include "system.h"
23
#include "coretypes.h"
24
#include "diagnostic-core.h"
25
#include "tree-flow.h"
26
#include "tree-dump.h"
27
#include "cfgloop.h"
28
#include "tree-chrec.h"
29
#include "tree-data-ref.h"
30
#include "tree-scalar-evolution.h"
31
#include "sese.h"
32
 
33
#ifdef HAVE_cloog
34
#include "cloog/cloog.h"
35
#include "ppl_c.h"
36
#include "graphite-cloog-util.h"
37
#include "graphite-ppl.h"
38
#include "graphite-poly.h"
39
#include "graphite-clast-to-gimple.h"
40
#include "graphite-dependences.h"
41
#include "graphite-cloog-compat.h"
42
 
43
#ifndef CLOOG_LANGUAGE_C
44
#define CLOOG_LANGUAGE_C LANGUAGE_C
45
#endif
46
 
47
/* This flag is set when an error occurred during the translation of
48
   CLAST to Gimple.  */
49
static bool gloog_error;
50
 
51
/* Verifies properties that GRAPHITE should maintain during translation.  */
52
 
53
static inline void
54
graphite_verify (void)
55
{
56
#ifdef ENABLE_CHECKING
57
  verify_loop_structure ();
58
  verify_dominators (CDI_DOMINATORS);
59
  verify_loop_closed_ssa (true);
60
#endif
61
}
62
 
63
/* Stores the INDEX in a vector and the loop nesting LEVEL for a given
64
   clast NAME.  BOUND_ONE and BOUND_TWO represent the exact lower and
65
   upper bounds that can be inferred from the polyhedral representation.  */
66
 
67
typedef struct clast_name_index {
68
  int index;
69
  int level;
70
  mpz_t bound_one, bound_two;
71
  const char *name;
72
} *clast_name_index_p;
73
 
74
/* Returns a pointer to a new element of type clast_name_index_p built
75
   from NAME, INDEX, LEVEL, BOUND_ONE, and BOUND_TWO.  */
76
 
77
static inline clast_name_index_p
78
new_clast_name_index (const char *name, int index, int level,
79
                      mpz_t bound_one, mpz_t bound_two)
80
{
81
  clast_name_index_p res = XNEW (struct clast_name_index);
82
 
83
  res->name = name;
84
  res->level = level;
85
  res->index = index;
86
  mpz_init (res->bound_one);
87
  mpz_init (res->bound_two);
88
  mpz_set (res->bound_one, bound_one);
89
  mpz_set (res->bound_two, bound_two);
90
  return res;
91
}
92
 
93
/* Free the memory taken by a clast_name_index struct.  */
94
 
95
static void
96
free_clast_name_index (void *ptr)
97
{
98
  struct clast_name_index *c = (struct clast_name_index *) ptr;
99
  mpz_clear (c->bound_one);
100
  mpz_clear (c->bound_two);
101
  free (ptr);
102
}
103
 
104
/* For a given clast NAME, returns -1 if NAME is not in the
105
   INDEX_TABLE, otherwise returns the loop level for the induction
106
   variable NAME, or if it is a parameter, the parameter number in the
107
   vector of parameters.  */
108
 
109
static inline int
110
clast_name_to_level (clast_name_p name, htab_t index_table)
111
{
112
  struct clast_name_index tmp;
113
  PTR *slot;
114
 
115
#ifdef CLOOG_ORG
116
  gcc_assert (name->type == clast_expr_name);
117
  tmp.name = ((const struct clast_name *) name)->name;
118
#else
119
  tmp.name = name;
120
#endif
121
 
122
  slot = htab_find_slot (index_table, &tmp, NO_INSERT);
123
 
124
  if (slot && *slot)
125
    return ((struct clast_name_index *) *slot)->level;
126
 
127
  return -1;
128
}
129
 
130
/* For a given clast NAME, returns -1 if it does not correspond to any
131
   parameter, or otherwise, returns the index in the PARAMS or
132
   SCATTERING_DIMENSIONS vector.  */
133
 
134
static inline int
135
clast_name_to_index (clast_name_p name, htab_t index_table)
136
{
137
  struct clast_name_index tmp;
138
  PTR *slot;
139
 
140
#ifdef CLOOG_ORG
141
  gcc_assert (name->type == clast_expr_name);
142
  tmp.name = ((const struct clast_name *) name)->name;
143
#else
144
  tmp.name = name;
145
#endif
146
 
147
  slot = htab_find_slot (index_table, &tmp, NO_INSERT);
148
 
149
  if (slot && *slot)
150
    return ((struct clast_name_index *) *slot)->index;
151
 
152
  return -1;
153
}
154
 
155
/* For a given clast NAME, initializes the lower and upper bounds BOUND_ONE
156
   and BOUND_TWO stored in the INDEX_TABLE.  Returns true when NAME has been
157
   found in the INDEX_TABLE, false otherwise.  */
158
 
159
static inline bool
160
clast_name_to_lb_ub (clast_name_p name, htab_t index_table, mpz_t bound_one,
161
                     mpz_t bound_two)
162
{
163
  struct clast_name_index tmp;
164
  PTR *slot;
165
 
166
#ifdef CLOOG_ORG
167
  gcc_assert (name->type == clast_expr_name);
168
  tmp.name = ((const struct clast_name *) name)->name;
169
#else
170
  tmp.name = name;
171
#endif
172
 
173
  slot = htab_find_slot (index_table, &tmp, NO_INSERT);
174
 
175
  if (slot && *slot)
176
    {
177
      mpz_set (bound_one, ((struct clast_name_index *) *slot)->bound_one);
178
      mpz_set (bound_two, ((struct clast_name_index *) *slot)->bound_two);
179
      return true;
180
    }
181
 
182
  return false;
183
}
184
 
185
/* Records in INDEX_TABLE the INDEX and LEVEL for NAME.  */
186
 
187
static inline void
188
save_clast_name_index (htab_t index_table, const char *name,
189
                       int index, int level, mpz_t bound_one, mpz_t bound_two)
190
{
191
  struct clast_name_index tmp;
192
  PTR *slot;
193
 
194
  tmp.name = name;
195
  slot = htab_find_slot (index_table, &tmp, INSERT);
196
 
197
  if (slot)
198
    {
199
      free (*slot);
200
 
201
      *slot = new_clast_name_index (name, index, level, bound_one, bound_two);
202
    }
203
}
204
 
205
/* Computes a hash function for database element ELT.  */
206
 
207
static inline hashval_t
208
clast_name_index_elt_info (const void *elt)
209
{
210
  return htab_hash_pointer (((const struct clast_name_index *) elt)->name);
211
}
212
 
213
/* Compares database elements E1 and E2.  */
214
 
215
static inline int
216
eq_clast_name_indexes (const void *e1, const void *e2)
217
{
218
  const struct clast_name_index *elt1 = (const struct clast_name_index *) e1;
219
  const struct clast_name_index *elt2 = (const struct clast_name_index *) e2;
220
 
221
  return (elt1->name == elt2->name);
222
}
223
 
224
 
225
 
226
/* NEWIVS_INDEX binds CLooG's scattering name to the index of the tree
227
   induction variable in NEWIVS.
228
 
229
   PARAMS_INDEX binds CLooG's parameter name to the index of the tree
230
   parameter in PARAMS.  */
231
 
232
typedef struct ivs_params {
233
  VEC (tree, heap) *params, **newivs;
234
  htab_t newivs_index, params_index;
235
  sese region;
236
} *ivs_params_p;
237
 
238
/* Returns the tree variable from the name NAME that was given in
239
   Cloog representation.  */
240
 
241
static tree
242
clast_name_to_gcc (clast_name_p name, ivs_params_p ip)
243
{
244
  int index;
245
 
246
  if (ip->params && ip->params_index)
247
    {
248
      index = clast_name_to_index (name, ip->params_index);
249
 
250
      if (index >= 0)
251
        return VEC_index (tree, ip->params, index);
252
    }
253
 
254
  gcc_assert (*(ip->newivs) && ip->newivs_index);
255
  index = clast_name_to_index (name, ip->newivs_index);
256
  gcc_assert (index >= 0);
257
 
258
  return VEC_index (tree, *(ip->newivs), index);
259
}
260
 
261
/* Returns the maximal precision type for expressions TYPE1 and TYPE2.  */
262
 
263
static tree
264
max_precision_type (tree type1, tree type2)
265
{
266
  enum machine_mode mode;
267
  int p1, p2, precision;
268
  tree type;
269
 
270
  if (POINTER_TYPE_P (type1))
271
    return type1;
272
 
273
  if (POINTER_TYPE_P (type2))
274
    return type2;
275
 
276
  if (TYPE_UNSIGNED (type1)
277
      && TYPE_UNSIGNED (type2))
278
    return TYPE_PRECISION (type1) > TYPE_PRECISION (type2) ? type1 : type2;
279
 
280
  p1 = TYPE_PRECISION (type1);
281
  p2 = TYPE_PRECISION (type2);
282
 
283
  if (p1 > p2)
284
    precision = TYPE_UNSIGNED (type1) ? p1 * 2 : p1;
285
  else
286
    precision = TYPE_UNSIGNED (type2) ? p2 * 2 : p2;
287
 
288
  if (precision > BITS_PER_WORD)
289
    {
290
      gloog_error = true;
291
      return integer_type_node;
292
    }
293
 
294
  mode = smallest_mode_for_size (precision, MODE_INT);
295
  precision = GET_MODE_PRECISION (mode);
296
  type = build_nonstandard_integer_type (precision, false);
297
 
298
  if (!type)
299
    {
300
      gloog_error = true;
301
      return integer_type_node;
302
    }
303
 
304
  return type;
305
}
306
 
307
static tree
308
clast_to_gcc_expression (tree, struct clast_expr *, ivs_params_p);
309
 
310
/* Converts a Cloog reduction expression R with reduction operation OP
311
   to a GCC expression tree of type TYPE.  */
312
 
313
static tree
314
clast_to_gcc_expression_red (tree type, enum tree_code op,
315
                             struct clast_reduction *r, ivs_params_p ip)
316
{
317
  int i;
318
  tree res = clast_to_gcc_expression (type, r->elts[0], ip);
319
  tree operand_type = (op == POINTER_PLUS_EXPR) ? sizetype : type;
320
 
321
  for (i = 1; i < r->n; i++)
322
    {
323
      tree t = clast_to_gcc_expression (operand_type, r->elts[i], ip);
324
      res = fold_build2 (op, type, res, t);
325
    }
326
 
327
  return res;
328
}
329
 
330
/* Converts a Cloog AST expression E back to a GCC expression tree of
331
   type TYPE.  */
332
 
333
static tree
334
clast_to_gcc_expression (tree type, struct clast_expr *e, ivs_params_p ip)
335
{
336
  switch (e->type)
337
    {
338
    case clast_expr_term:
339
      {
340
        struct clast_term *t = (struct clast_term *) e;
341
 
342
        if (t->var)
343
          {
344
            if (mpz_cmp_si (t->val, 1) == 0)
345
              {
346
                tree name = clast_name_to_gcc (t->var, ip);
347
 
348
                if (POINTER_TYPE_P (TREE_TYPE (name)) != POINTER_TYPE_P (type))
349
                  name = convert_to_ptrofftype (name);
350
 
351
                name = fold_convert (type, name);
352
                return name;
353
              }
354
 
355
            else if (mpz_cmp_si (t->val, -1) == 0)
356
              {
357
                tree name = clast_name_to_gcc (t->var, ip);
358
 
359
                if (POINTER_TYPE_P (TREE_TYPE (name)) != POINTER_TYPE_P (type))
360
                  name = convert_to_ptrofftype (name);
361
 
362
                name = fold_convert (type, name);
363
 
364
                return fold_build1 (NEGATE_EXPR, type, name);
365
              }
366
            else
367
              {
368
                tree name = clast_name_to_gcc (t->var, ip);
369
                tree cst = gmp_cst_to_tree (type, t->val);
370
 
371
                if (POINTER_TYPE_P (TREE_TYPE (name)) != POINTER_TYPE_P (type))
372
                  name = convert_to_ptrofftype (name);
373
 
374
                name = fold_convert (type, name);
375
 
376
                if (!POINTER_TYPE_P (type))
377
                  return fold_build2 (MULT_EXPR, type, cst, name);
378
 
379
                gloog_error = true;
380
                return cst;
381
              }
382
          }
383
        else
384
          return gmp_cst_to_tree (type, t->val);
385
      }
386
 
387
    case clast_expr_red:
388
      {
389
        struct clast_reduction *r = (struct clast_reduction *) e;
390
 
391
        switch (r->type)
392
          {
393
          case clast_red_sum:
394
            return clast_to_gcc_expression_red
395
              (type, POINTER_TYPE_P (type) ? POINTER_PLUS_EXPR : PLUS_EXPR,
396
               r, ip);
397
 
398
          case clast_red_min:
399
            return clast_to_gcc_expression_red (type, MIN_EXPR, r, ip);
400
 
401
          case clast_red_max:
402
            return clast_to_gcc_expression_red (type, MAX_EXPR, r, ip);
403
 
404
          default:
405
            gcc_unreachable ();
406
          }
407
        break;
408
      }
409
 
410
    case clast_expr_bin:
411
      {
412
        struct clast_binary *b = (struct clast_binary *) e;
413
        struct clast_expr *lhs = (struct clast_expr *) b->LHS;
414
        tree tl = clast_to_gcc_expression (type, lhs, ip);
415
        tree tr = gmp_cst_to_tree (type, b->RHS);
416
 
417
        switch (b->type)
418
          {
419
          case clast_bin_fdiv:
420
            return fold_build2 (FLOOR_DIV_EXPR, type, tl, tr);
421
 
422
          case clast_bin_cdiv:
423
            return fold_build2 (CEIL_DIV_EXPR, type, tl, tr);
424
 
425
          case clast_bin_div:
426
            return fold_build2 (EXACT_DIV_EXPR, type, tl, tr);
427
 
428
          case clast_bin_mod:
429
            return fold_build2 (TRUNC_MOD_EXPR, type, tl, tr);
430
 
431
          default:
432
            gcc_unreachable ();
433
          }
434
      }
435
 
436
    default:
437
      gcc_unreachable ();
438
    }
439
 
440
  return NULL_TREE;
441
}
442
 
443
/* Return a type that could represent the values between BOUND_ONE and
444
   BOUND_TWO.  */
445
 
446
static tree
447
type_for_interval (mpz_t bound_one, mpz_t bound_two)
448
{
449
  bool unsigned_p;
450
  tree type;
451
  enum machine_mode mode;
452
  int wider_precision;
453
  int precision = MAX (mpz_sizeinbase (bound_one, 2),
454
                       mpz_sizeinbase (bound_two, 2));
455
 
456
  if (precision > BITS_PER_WORD)
457
    {
458
      gloog_error = true;
459
      return integer_type_node;
460
    }
461
 
462
  if (mpz_cmp (bound_one, bound_two) <= 0)
463
    unsigned_p = (mpz_sgn (bound_one) >= 0);
464
  else
465
    unsigned_p = (mpz_sgn (bound_two) >= 0);
466
 
467
  mode = smallest_mode_for_size (precision, MODE_INT);
468
  wider_precision = GET_MODE_PRECISION (mode);
469
 
470
  /* As we want to generate signed types as much as possible, try to
471
     fit the interval [bound_one, bound_two] in a signed type.  For example,
472
     supposing that we have the interval [0, 100], instead of
473
     generating unsigned char, we want to generate a signed char.  */
474
  if (unsigned_p && precision < wider_precision)
475
    unsigned_p = false;
476
 
477
  type = build_nonstandard_integer_type (wider_precision, unsigned_p);
478
 
479
  if (!type)
480
    {
481
      gloog_error = true;
482
      return integer_type_node;
483
    }
484
 
485
  return type;
486
}
487
 
488
/* Return a type that could represent the integer value VAL, or
489
   otherwise return NULL_TREE.  */
490
 
491
static tree
492
type_for_value (mpz_t val)
493
{
494
  return type_for_interval (val, val);
495
}
496
 
497
/* Return the type for the clast_term T.  Initializes BOUND_ONE and
498
   BOUND_TWO to the bounds of the term.  */
499
 
500
static tree
501
type_for_clast_term (struct clast_term *t, ivs_params_p ip, mpz_t bound_one,
502
                     mpz_t bound_two)
503
{
504
  clast_name_p name = t->var;
505
  bool found = false;
506
 
507
  gcc_assert (t->expr.type == clast_expr_term);
508
 
509
  if (!name)
510
    {
511
      mpz_set (bound_one, t->val);
512
      mpz_set (bound_two, t->val);
513
      return type_for_value (t->val);
514
    }
515
 
516
  if (ip->params && ip->params_index)
517
    found = clast_name_to_lb_ub (name, ip->params_index, bound_one, bound_two);
518
 
519
  if (!found)
520
    {
521
      gcc_assert (*(ip->newivs) && ip->newivs_index);
522
      found = clast_name_to_lb_ub (name, ip->newivs_index,
523
                                   bound_one, bound_two);
524
      gcc_assert (found);
525
    }
526
 
527
  mpz_mul (bound_one, bound_one, t->val);
528
  mpz_mul (bound_two, bound_two, t->val);
529
 
530
  return TREE_TYPE (clast_name_to_gcc (name, ip));
531
}
532
 
533
static tree
534
type_for_clast_expr (struct clast_expr *, ivs_params_p, mpz_t, mpz_t);
535
 
536
/* Return the type for the clast_reduction R.  Initializes BOUND_ONE
537
   and BOUND_TWO to the bounds of the reduction expression.  */
538
 
539
static tree
540
type_for_clast_red (struct clast_reduction *r, ivs_params_p ip,
541
                    mpz_t bound_one, mpz_t bound_two)
542
{
543
  int i;
544
  tree type = type_for_clast_expr (r->elts[0], ip, bound_one, bound_two);
545
  mpz_t b1, b2, m1, m2;
546
 
547
  if (r->n == 1)
548
    return type;
549
 
550
  mpz_init (b1);
551
  mpz_init (b2);
552
  mpz_init (m1);
553
  mpz_init (m2);
554
 
555
  for (i = 1; i < r->n; i++)
556
    {
557
      tree t = type_for_clast_expr (r->elts[i], ip, b1, b2);
558
      type = max_precision_type (type, t);
559
 
560
      switch (r->type)
561
        {
562
        case clast_red_sum:
563
          value_min (m1, bound_one, bound_two);
564
          value_min (m2, b1, b2);
565
          mpz_add (bound_one, m1, m2);
566
 
567
          value_max (m1, bound_one, bound_two);
568
          value_max (m2, b1, b2);
569
          mpz_add (bound_two, m1, m2);
570
          break;
571
 
572
        case clast_red_min:
573
          value_min (bound_one, bound_one, bound_two);
574
          value_min (bound_two, b1, b2);
575
          break;
576
 
577
        case clast_red_max:
578
          value_max (bound_one, bound_one, bound_two);
579
          value_max (bound_two, b1, b2);
580
          break;
581
 
582
        default:
583
          gcc_unreachable ();
584
          break;
585
        }
586
    }
587
 
588
  mpz_clear (b1);
589
  mpz_clear (b2);
590
  mpz_clear (m1);
591
  mpz_clear (m2);
592
 
593
  /* Return a type that can represent the result of the reduction.  */
594
  return max_precision_type (type, type_for_interval (bound_one, bound_two));
595
}
596
 
597
/* Return the type for the clast_binary B used in STMT.  */
598
 
599
static tree
600
type_for_clast_bin (struct clast_binary *b, ivs_params_p ip, mpz_t bound_one,
601
                    mpz_t bound_two)
602
{
603
  mpz_t one;
604
  tree l = type_for_clast_expr ((struct clast_expr *) b->LHS, ip,
605
                                bound_one, bound_two);
606
  tree r = type_for_value (b->RHS);
607
  tree type = max_precision_type (l, r);
608
 
609
  switch (b->type)
610
    {
611
    case clast_bin_fdiv:
612
      mpz_mdiv (bound_one, bound_one, b->RHS);
613
      mpz_mdiv (bound_two, bound_two, b->RHS);
614
      break;
615
 
616
    case clast_bin_cdiv:
617
      mpz_mdiv (bound_one, bound_one, b->RHS);
618
      mpz_mdiv (bound_two, bound_two, b->RHS);
619
      mpz_init (one);
620
      mpz_add (bound_one, bound_one, one);
621
      mpz_add (bound_two, bound_two, one);
622
      mpz_clear (one);
623
      break;
624
 
625
    case clast_bin_div:
626
      mpz_div (bound_one, bound_one, b->RHS);
627
      mpz_div (bound_two, bound_two, b->RHS);
628
      break;
629
 
630
    case clast_bin_mod:
631
      mpz_mod (bound_one, bound_one, b->RHS);
632
      mpz_mod (bound_two, bound_two, b->RHS);
633
      break;
634
 
635
    default:
636
      gcc_unreachable ();
637
    }
638
 
639
  /* Return a type that can represent the result of the reduction.  */
640
  return max_precision_type (type, type_for_interval (bound_one, bound_two));
641
}
642
 
643
/* Returns the type for the CLAST expression E when used in statement
644
   STMT.  */
645
 
646
static tree
647
type_for_clast_expr (struct clast_expr *e, ivs_params_p ip, mpz_t bound_one,
648
                     mpz_t bound_two)
649
{
650
  switch (e->type)
651
    {
652
    case clast_expr_term:
653
      return type_for_clast_term ((struct clast_term *) e, ip,
654
                                  bound_one, bound_two);
655
 
656
    case clast_expr_red:
657
      return type_for_clast_red ((struct clast_reduction *) e, ip,
658
                                 bound_one, bound_two);
659
 
660
    case clast_expr_bin:
661
      return type_for_clast_bin ((struct clast_binary *) e, ip,
662
                                 bound_one, bound_two);
663
 
664
    default:
665
      gcc_unreachable ();
666
    }
667
 
668
  return NULL_TREE;
669
}
670
 
671
/* Returns the type for the equation CLEQ.  */
672
 
673
static tree
674
type_for_clast_eq (struct clast_equation *cleq, ivs_params_p ip)
675
{
676
  mpz_t bound_one, bound_two;
677
  tree l, r;
678
 
679
  mpz_init (bound_one);
680
  mpz_init (bound_two);
681
 
682
  l = type_for_clast_expr (cleq->LHS, ip, bound_one, bound_two);
683
  r = type_for_clast_expr (cleq->RHS, ip, bound_one, bound_two);
684
 
685
  mpz_clear (bound_one);
686
  mpz_clear (bound_two);
687
  return max_precision_type (l, r);
688
}
689
 
690
/* Translates a clast equation CLEQ to a tree.  */
691
 
692
static tree
693
graphite_translate_clast_equation (struct clast_equation *cleq,
694
                                   ivs_params_p ip)
695
{
696
  enum tree_code comp;
697
  tree type = type_for_clast_eq (cleq, ip);
698
  tree lhs = clast_to_gcc_expression (type, cleq->LHS, ip);
699
  tree rhs = clast_to_gcc_expression (type, cleq->RHS, ip);
700
 
701
  if (cleq->sign == 0)
702
    comp = EQ_EXPR;
703
 
704
  else if (cleq->sign > 0)
705
    comp = GE_EXPR;
706
 
707
  else
708
    comp = LE_EXPR;
709
 
710
  return fold_build2 (comp, boolean_type_node, lhs, rhs);
711
}
712
 
713
/* Creates the test for the condition in STMT.  */
714
 
715
static tree
716
graphite_create_guard_cond_expr (struct clast_guard *stmt,
717
                                 ivs_params_p ip)
718
{
719
  tree cond = NULL;
720
  int i;
721
 
722
  for (i = 0; i < stmt->n; i++)
723
    {
724
      tree eq = graphite_translate_clast_equation (&stmt->eq[i], ip);
725
 
726
      if (cond)
727
        cond = fold_build2 (TRUTH_AND_EXPR, TREE_TYPE (eq), cond, eq);
728
      else
729
        cond = eq;
730
    }
731
 
732
  return cond;
733
}
734
 
735
/* Creates a new if region corresponding to Cloog's guard.  */
736
 
737
static edge
738
graphite_create_new_guard (edge entry_edge, struct clast_guard *stmt,
739
                           ivs_params_p ip)
740
{
741
  tree cond_expr = graphite_create_guard_cond_expr (stmt, ip);
742
  edge exit_edge = create_empty_if_region_on_edge (entry_edge, cond_expr);
743
  return exit_edge;
744
}
745
 
746
/* Compute the lower bound LOW and upper bound UP for the parameter
747
   PARAM in scop SCOP based on the constraints in the context.  */
748
 
749
static void
750
compute_bounds_for_param (scop_p scop, int param, mpz_t low, mpz_t up)
751
{
752
  ppl_Linear_Expression_t le;
753
 
754
  /* Prepare the linear expression corresponding to the parameter that
755
     we want to maximize/minimize.  */
756
  ppl_new_Linear_Expression_with_dimension (&le, scop_nb_params (scop));
757
  ppl_set_coef (le, param, 1);
758
 
759
  ppl_max_for_le_pointset (SCOP_CONTEXT (scop), le, up);
760
  ppl_min_for_le_pointset (SCOP_CONTEXT (scop), le, low);
761
  ppl_delete_Linear_Expression (le);
762
}
763
 
764
/* Compute the lower bound LOW and upper bound UP for the induction
765
   variable at LEVEL for the statement PBB, based on the transformed
766
   scattering of PBB: T|I|G|Cst, with T the scattering transform, I
767
   the iteration domain, and G the context parameters.  */
768
 
769
static void
770
compute_bounds_for_level (poly_bb_p pbb, int level, mpz_t low, mpz_t up)
771
{
772
  ppl_Pointset_Powerset_C_Polyhedron_t ps;
773
  ppl_Linear_Expression_t le;
774
 
775
  combine_context_id_scat (&ps, pbb, false);
776
 
777
  /* Prepare the linear expression corresponding to the level that we
778
     want to maximize/minimize.  */
779
  {
780
    ppl_dimension_type dim = pbb_nb_scattering_transform (pbb)
781
      + pbb_dim_iter_domain (pbb) + pbb_nb_params (pbb);
782
 
783
    ppl_new_Linear_Expression_with_dimension (&le, dim);
784
    ppl_set_coef (le, psct_dynamic_dim (pbb, level), 1);
785
  }
786
 
787
  ppl_max_for_le_pointset (ps, le, up);
788
  ppl_min_for_le_pointset (ps, le, low);
789
  ppl_delete_Linear_Expression (le);
790
  ppl_delete_Pointset_Powerset_C_Polyhedron (ps);
791
}
792
 
793
/* Walks a CLAST and returns the first statement in the body of a
794
   loop.
795
 
796
   FIXME: This function should not be used to get a PBB in the STMT
797
   loop in order to find out the iteration domain of the loop: the
798
   counter example from Tobias is:
799
 
800
   | for (i = 0; i < 100; i++)
801
   |   {
802
   |     if (i == 0)
803
   |       S1;
804
   |     S2;
805
   |   }
806
 
807
   This function would return S1 whose iteration domain contains only
808
   one point "i = 0", whereas the iteration domain of S2 has 100 points.
809
 
810
   This should be implemented using some functionality existing in
811
   CLooG-ISL.  */
812
 
813
static struct clast_user_stmt *
814
clast_get_body_of_loop (struct clast_stmt *stmt)
815
{
816
  if (!stmt
817
      || CLAST_STMT_IS_A (stmt, stmt_user))
818
    return (struct clast_user_stmt *) stmt;
819
 
820
  if (CLAST_STMT_IS_A (stmt, stmt_for))
821
    return clast_get_body_of_loop (((struct clast_for *) stmt)->body);
822
 
823
  if (CLAST_STMT_IS_A (stmt, stmt_guard))
824
    return clast_get_body_of_loop (((struct clast_guard *) stmt)->then);
825
 
826
  if (CLAST_STMT_IS_A (stmt, stmt_block))
827
    return clast_get_body_of_loop (((struct clast_block *) stmt)->body);
828
 
829
  if (CLAST_STMT_IS_A (stmt, stmt_ass))
830
    return clast_get_body_of_loop (stmt->next);
831
 
832
  gcc_unreachable ();
833
}
834
 
835
/* Returns the type for the induction variable for the loop translated
836
   from STMT_FOR.  */
837
 
838
static tree
839
type_for_clast_for (struct clast_for *stmt_for, ivs_params_p ip)
840
{
841
  mpz_t bound_one, bound_two;
842
  tree lb_type, ub_type;
843
 
844
  mpz_init (bound_one);
845
  mpz_init (bound_two);
846
 
847
  lb_type = type_for_clast_expr (stmt_for->LB, ip, bound_one, bound_two);
848
  ub_type = type_for_clast_expr (stmt_for->UB, ip, bound_one, bound_two);
849
 
850
  mpz_clear (bound_one);
851
  mpz_clear (bound_two);
852
 
853
  return max_precision_type (lb_type, ub_type);
854
}
855
 
856
/* Creates a new LOOP corresponding to Cloog's STMT.  Inserts an
857
   induction variable for the new LOOP.  New LOOP is attached to CFG
858
   starting at ENTRY_EDGE.  LOOP is inserted into the loop tree and
859
   becomes the child loop of the OUTER_LOOP.  NEWIVS_INDEX binds
860
   CLooG's scattering name to the induction variable created for the
861
   loop of STMT.  The new induction variable is inserted in the NEWIVS
862
   vector and is of type TYPE.  */
863
 
864
static struct loop *
865
graphite_create_new_loop (edge entry_edge, struct clast_for *stmt,
866
                          loop_p outer, tree type, tree lb, tree ub,
867
                          int level, ivs_params_p ip)
868
{
869
  mpz_t low, up;
870
 
871
  struct clast_user_stmt *body
872
    = clast_get_body_of_loop ((struct clast_stmt *) stmt);
873
  poly_bb_p pbb = (poly_bb_p) cloog_statement_usr (body->statement);
874
 
875
  tree stride = gmp_cst_to_tree (type, stmt->stride);
876
  tree ivvar = create_tmp_var (type, "graphite_IV");
877
  tree iv, iv_after_increment;
878
  loop_p loop = create_empty_loop_on_edge
879
    (entry_edge, lb, stride, ub, ivvar, &iv, &iv_after_increment,
880
     outer ? outer : entry_edge->src->loop_father);
881
 
882
  add_referenced_var (ivvar);
883
 
884
  mpz_init (low);
885
  mpz_init (up);
886
  compute_bounds_for_level (pbb, level, low, up);
887
  save_clast_name_index (ip->newivs_index, stmt->iterator,
888
                         VEC_length (tree, *(ip->newivs)), level, low, up);
889
  mpz_clear (low);
890
  mpz_clear (up);
891
  VEC_safe_push (tree, heap, *(ip->newivs), iv);
892
  return loop;
893
}
894
 
895
/* Inserts in iv_map a tuple (OLD_LOOP->num, NEW_NAME) for the
896
   induction variables of the loops around GBB in SESE.  */
897
 
898
static void
899
build_iv_mapping (VEC (tree, heap) *iv_map, struct clast_user_stmt *user_stmt,
900
                  ivs_params_p ip)
901
{
902
  struct clast_stmt *t;
903
  int depth = 0;
904
  CloogStatement *cs = user_stmt->statement;
905
  poly_bb_p pbb = (poly_bb_p) cloog_statement_usr (cs);
906
  gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
907
  mpz_t bound_one, bound_two;
908
 
909
  mpz_init (bound_one);
910
  mpz_init (bound_two);
911
 
912
  for (t = user_stmt->substitutions; t; t = t->next, depth++)
913
    {
914
      struct clast_expr *expr = (struct clast_expr *)
915
       ((struct clast_assignment *)t)->RHS;
916
      tree type = type_for_clast_expr (expr, ip, bound_one, bound_two);
917
      tree new_name = clast_to_gcc_expression (type, expr, ip);
918
      loop_p old_loop = gbb_loop_at_index (gbb, ip->region, depth);
919
 
920
      VEC_replace (tree, iv_map, old_loop->num, new_name);
921
    }
922
 
923
  mpz_clear (bound_one);
924
  mpz_clear (bound_two);
925
}
926
 
927
/* Construct bb_pbb_def with BB and PBB.  */
928
 
929
static bb_pbb_def *
930
new_bb_pbb_def (basic_block bb, poly_bb_p pbb)
931
{
932
  bb_pbb_def *bb_pbb_p;
933
 
934
  bb_pbb_p = XNEW (bb_pbb_def);
935
  bb_pbb_p->bb = bb;
936
  bb_pbb_p->pbb = pbb;
937
 
938
  return bb_pbb_p;
939
}
940
 
941
/* Mark BB with it's relevant PBB via hashing table BB_PBB_MAPPING.  */
942
 
943
static void
944
mark_bb_with_pbb (poly_bb_p pbb, basic_block bb, htab_t bb_pbb_mapping)
945
{
946
  bb_pbb_def tmp;
947
  PTR *x;
948
 
949
  tmp.bb = bb;
950
  x = htab_find_slot (bb_pbb_mapping, &tmp, INSERT);
951
 
952
  if (x && !*x)
953
    *x = new_bb_pbb_def (bb, pbb);
954
}
955
 
956
/* Find BB's related poly_bb_p in hash table BB_PBB_MAPPING.  */
957
 
958
static poly_bb_p
959
find_pbb_via_hash (htab_t bb_pbb_mapping, basic_block bb)
960
{
961
  bb_pbb_def tmp;
962
  PTR *slot;
963
 
964
  tmp.bb = bb;
965
  slot = htab_find_slot (bb_pbb_mapping, &tmp, NO_INSERT);
966
 
967
  if (slot && *slot)
968
    return ((bb_pbb_def *) *slot)->pbb;
969
 
970
  return NULL;
971
}
972
 
973
/* Check data dependency in LOOP at level LEVEL.
974
   BB_PBB_MAPPING is a basic_block and it's related poly_bb_p
975
   mapping.  */
976
 
977
static bool
978
dependency_in_loop_p (loop_p loop, htab_t bb_pbb_mapping, int level)
979
{
980
  unsigned i,j;
981
  basic_block *bbs = get_loop_body_in_dom_order (loop);
982
 
983
  for (i = 0; i < loop->num_nodes; i++)
984
    {
985
      poly_bb_p pbb1 = find_pbb_via_hash (bb_pbb_mapping, bbs[i]);
986
 
987
      if (pbb1 == NULL)
988
       continue;
989
 
990
      for (j = 0; j < loop->num_nodes; j++)
991
       {
992
         poly_bb_p pbb2 = find_pbb_via_hash (bb_pbb_mapping, bbs[j]);
993
 
994
         if (pbb2 == NULL)
995
           continue;
996
 
997
         if (dependency_between_pbbs_p (pbb1, pbb2, level))
998
           {
999
             free (bbs);
1000
             return true;
1001
           }
1002
       }
1003
    }
1004
 
1005
  free (bbs);
1006
 
1007
  return false;
1008
}
1009
 
1010
/* Translates a clast user statement STMT to gimple.
1011
 
1012
   - NEXT_E is the edge where new generated code should be attached.
1013
   - CONTEXT_LOOP is the loop in which the generated code will be placed
1014
   - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping.  */
1015
 
1016
static edge
1017
translate_clast_user (struct clast_user_stmt *stmt, edge next_e,
1018
                      htab_t bb_pbb_mapping, ivs_params_p ip)
1019
{
1020
  int i, nb_loops;
1021
  basic_block new_bb;
1022
  poly_bb_p pbb = (poly_bb_p) cloog_statement_usr (stmt->statement);
1023
  gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
1024
  VEC (tree, heap) *iv_map;
1025
 
1026
  if (GBB_BB (gbb) == ENTRY_BLOCK_PTR)
1027
    return next_e;
1028
 
1029
  nb_loops = number_of_loops ();
1030
  iv_map = VEC_alloc (tree, heap, nb_loops);
1031
  for (i = 0; i < nb_loops; i++)
1032
    VEC_quick_push (tree, iv_map, NULL_TREE);
1033
 
1034
  build_iv_mapping (iv_map, stmt, ip);
1035
  next_e = copy_bb_and_scalar_dependences (GBB_BB (gbb), ip->region,
1036
                                           next_e, iv_map, &gloog_error);
1037
  VEC_free (tree, heap, iv_map);
1038
 
1039
  new_bb = next_e->src;
1040
  mark_bb_with_pbb (pbb, new_bb, bb_pbb_mapping);
1041
  update_ssa (TODO_update_ssa);
1042
 
1043
  return next_e;
1044
}
1045
 
1046
/* Creates a new if region protecting the loop to be executed, if the execution
1047
   count is zero (lb > ub).  */
1048
 
1049
static edge
1050
graphite_create_new_loop_guard (edge entry_edge, struct clast_for *stmt,
1051
                                tree *type, tree *lb, tree *ub,
1052
                                ivs_params_p ip)
1053
{
1054
  tree cond_expr;
1055
  edge exit_edge;
1056
 
1057
  *type = type_for_clast_for (stmt, ip);
1058
  *lb = clast_to_gcc_expression (*type, stmt->LB, ip);
1059
  *ub = clast_to_gcc_expression (*type, stmt->UB, ip);
1060
 
1061
  /* When ub is simply a constant or a parameter, use lb <= ub.  */
1062
  if (TREE_CODE (*ub) == INTEGER_CST || TREE_CODE (*ub) == SSA_NAME)
1063
    cond_expr = fold_build2 (LE_EXPR, boolean_type_node, *lb, *ub);
1064
  else
1065
    {
1066
      tree one = (POINTER_TYPE_P (*type)
1067
                  ? convert_to_ptrofftype (integer_one_node)
1068
                  : fold_convert (*type, integer_one_node));
1069
      /* Adding +1 and using LT_EXPR helps with loop latches that have a
1070
         loop iteration count of "PARAMETER - 1".  For PARAMETER == 0 this becomes
1071
         2^k-1 due to integer overflow, and the condition lb <= ub is true,
1072
         even if we do not want this.  However lb < ub + 1 is false, as
1073
         expected.  */
1074
      tree ub_one = fold_build2 (POINTER_TYPE_P (*type) ? POINTER_PLUS_EXPR
1075
                                 : PLUS_EXPR, *type, *ub, one);
1076
 
1077
      cond_expr = fold_build2 (LT_EXPR, boolean_type_node, *lb, ub_one);
1078
    }
1079
 
1080
  exit_edge = create_empty_if_region_on_edge (entry_edge, cond_expr);
1081
 
1082
  return exit_edge;
1083
}
1084
 
1085
static edge
1086
translate_clast (loop_p, struct clast_stmt *, edge, htab_t, int, ivs_params_p);
1087
 
1088
/* Create the loop for a clast for statement.
1089
 
1090
   - NEXT_E is the edge where new generated code should be attached.
1091
   - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping.  */
1092
 
1093
static edge
1094
translate_clast_for_loop (loop_p context_loop, struct clast_for *stmt,
1095
                          edge next_e, htab_t bb_pbb_mapping, int level,
1096
                          tree type, tree lb, tree ub, ivs_params_p ip)
1097
{
1098
  struct loop *loop = graphite_create_new_loop (next_e, stmt, context_loop,
1099
                                                type, lb, ub, level, ip);
1100
  edge last_e = single_exit (loop);
1101
  edge to_body = single_succ_edge (loop->header);
1102
  basic_block after = to_body->dest;
1103
 
1104
  /* Create a basic block for loop close phi nodes.  */
1105
  last_e = single_succ_edge (split_edge (last_e));
1106
 
1107
  /* Translate the body of the loop.  */
1108
  next_e = translate_clast (loop, stmt->body, to_body, bb_pbb_mapping,
1109
                            level + 1, ip);
1110
  redirect_edge_succ_nodup (next_e, after);
1111
  set_immediate_dominator (CDI_DOMINATORS, next_e->dest, next_e->src);
1112
 
1113
  if (flag_loop_parallelize_all
1114
      && !dependency_in_loop_p (loop, bb_pbb_mapping, level))
1115
    loop->can_be_parallel = true;
1116
 
1117
  return last_e;
1118
}
1119
 
1120
/* Translates a clast for statement STMT to gimple.  First a guard is created
1121
   protecting the loop, if it is executed zero times.  In this guard we create
1122
   the real loop structure.
1123
 
1124
   - NEXT_E is the edge where new generated code should be attached.
1125
   - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping.  */
1126
 
1127
static edge
1128
translate_clast_for (loop_p context_loop, struct clast_for *stmt, edge next_e,
1129
                     htab_t bb_pbb_mapping, int level, ivs_params_p ip)
1130
{
1131
  tree type, lb, ub;
1132
  edge last_e = graphite_create_new_loop_guard (next_e, stmt, &type,
1133
                                                &lb, &ub, ip);
1134
  edge true_e = get_true_edge_from_guard_bb (next_e->dest);
1135
 
1136
  translate_clast_for_loop (context_loop, stmt, true_e, bb_pbb_mapping, level,
1137
                            type, lb, ub, ip);
1138
  return last_e;
1139
}
1140
 
1141
/* Translates a clast assignment STMT to gimple.
1142
 
1143
   - NEXT_E is the edge where new generated code should be attached.
1144
   - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping.  */
1145
 
1146
static edge
1147
translate_clast_assignment (struct clast_assignment *stmt, edge next_e,
1148
                            int level, ivs_params_p ip)
1149
{
1150
  gimple_seq stmts;
1151
  mpz_t bound_one, bound_two;
1152
  tree type, new_name, var;
1153
  edge res = single_succ_edge (split_edge (next_e));
1154
  struct clast_expr *expr = (struct clast_expr *) stmt->RHS;
1155
 
1156
  mpz_init (bound_one);
1157
  mpz_init (bound_two);
1158
  type = type_for_clast_expr (expr, ip, bound_one, bound_two);
1159
  var = create_tmp_var (type, "graphite_var");
1160
  new_name = force_gimple_operand (clast_to_gcc_expression (type, expr, ip),
1161
                                   &stmts, true, var);
1162
  add_referenced_var (var);
1163
  if (stmts)
1164
    {
1165
      gsi_insert_seq_on_edge (next_e, stmts);
1166
      gsi_commit_edge_inserts ();
1167
    }
1168
 
1169
  save_clast_name_index (ip->newivs_index, stmt->LHS,
1170
                         VEC_length (tree, *(ip->newivs)), level,
1171
                         bound_one, bound_two);
1172
  VEC_safe_push (tree, heap, *(ip->newivs), new_name);
1173
 
1174
  mpz_clear (bound_one);
1175
  mpz_clear (bound_two);
1176
 
1177
  return res;
1178
}
1179
 
1180
/* Translates a clast guard statement STMT to gimple.
1181
 
1182
   - NEXT_E is the edge where new generated code should be attached.
1183
   - CONTEXT_LOOP is the loop in which the generated code will be placed
1184
   - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping.  */
1185
 
1186
static edge
1187
translate_clast_guard (loop_p context_loop, struct clast_guard *stmt,
1188
                       edge next_e, htab_t bb_pbb_mapping, int level,
1189
                       ivs_params_p ip)
1190
{
1191
  edge last_e = graphite_create_new_guard (next_e, stmt, ip);
1192
  edge true_e = get_true_edge_from_guard_bb (next_e->dest);
1193
 
1194
  translate_clast (context_loop, stmt->then, true_e, bb_pbb_mapping, level, ip);
1195
  return last_e;
1196
}
1197
 
1198
/* Translates a CLAST statement STMT to GCC representation in the
1199
   context of a SESE.
1200
 
1201
   - NEXT_E is the edge where new generated code should be attached.
1202
   - CONTEXT_LOOP is the loop in which the generated code will be placed
1203
   - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping.  */
1204
 
1205
static edge
1206
translate_clast (loop_p context_loop, struct clast_stmt *stmt, edge next_e,
1207
                 htab_t bb_pbb_mapping, int level, ivs_params_p ip)
1208
{
1209
  if (!stmt)
1210
    return next_e;
1211
 
1212
  if (CLAST_STMT_IS_A (stmt, stmt_root))
1213
    ; /* Do nothing.  */
1214
 
1215
  else if (CLAST_STMT_IS_A (stmt, stmt_user))
1216
    next_e = translate_clast_user ((struct clast_user_stmt *) stmt,
1217
                                   next_e, bb_pbb_mapping, ip);
1218
 
1219
  else if (CLAST_STMT_IS_A (stmt, stmt_for))
1220
    next_e = translate_clast_for (context_loop, (struct clast_for *) stmt,
1221
                                  next_e, bb_pbb_mapping, level, ip);
1222
 
1223
  else if (CLAST_STMT_IS_A (stmt, stmt_guard))
1224
    next_e = translate_clast_guard (context_loop, (struct clast_guard *) stmt,
1225
                                    next_e, bb_pbb_mapping, level, ip);
1226
 
1227
  else if (CLAST_STMT_IS_A (stmt, stmt_block))
1228
    next_e = translate_clast (context_loop, ((struct clast_block *) stmt)->body,
1229
                              next_e, bb_pbb_mapping, level, ip);
1230
 
1231
  else if (CLAST_STMT_IS_A (stmt, stmt_ass))
1232
    next_e = translate_clast_assignment ((struct clast_assignment *) stmt,
1233
                                         next_e, level, ip);
1234
  else
1235
    gcc_unreachable();
1236
 
1237
  recompute_all_dominators ();
1238
  graphite_verify ();
1239
 
1240
  return translate_clast (context_loop, stmt->next, next_e, bb_pbb_mapping,
1241
                          level, ip);
1242
}
1243
 
1244
/* Free the SCATTERING domain list.  */
1245
 
1246
static void
1247
free_scattering (CloogScatteringList *scattering)
1248
{
1249
  while (scattering)
1250
    {
1251
      CloogScattering *dom = cloog_scattering (scattering);
1252
      CloogScatteringList *next = cloog_next_scattering (scattering);
1253
 
1254
      cloog_scattering_free (dom);
1255
      free (scattering);
1256
      scattering = next;
1257
    }
1258
}
1259
 
1260
/* Initialize Cloog's parameter names from the names used in GIMPLE.
1261
   Initialize Cloog's iterator names, using 'graphite_iterator_%d'
1262
   from 0 to scop_nb_loops (scop).  */
1263
 
1264
static void
1265
initialize_cloog_names (scop_p scop, CloogProgram *prog)
1266
{
1267
  sese region = SCOP_REGION (scop);
1268
  int i;
1269
  int nb_iterators = scop_max_loop_depth (scop);
1270
  int nb_scattering = cloog_program_nb_scattdims (prog);
1271
  int nb_parameters = VEC_length (tree, SESE_PARAMS (region));
1272
  char **iterators = XNEWVEC (char *, nb_iterators * 2);
1273
  char **scattering = XNEWVEC (char *, nb_scattering);
1274
  char **parameters= XNEWVEC (char *, nb_parameters);
1275
 
1276
  cloog_program_set_names (prog, cloog_names_malloc ());
1277
 
1278
  for (i = 0; i < nb_parameters; i++)
1279
    {
1280
      tree param = VEC_index (tree, SESE_PARAMS (region), i);
1281
      const char *name = get_name (param);
1282
      int len;
1283
 
1284
      if (!name)
1285
        name = "T";
1286
 
1287
      len = strlen (name);
1288
      len += 17;
1289
      parameters[i] = XNEWVEC (char, len + 1);
1290
      snprintf (parameters[i], len, "%s_%d", name, SSA_NAME_VERSION (param));
1291
    }
1292
 
1293
  cloog_names_set_nb_parameters (cloog_program_names (prog), nb_parameters);
1294
  cloog_names_set_parameters (cloog_program_names (prog), parameters);
1295
 
1296
  for (i = 0; i < nb_iterators; i++)
1297
    {
1298
      int len = 4 + 16;
1299
      iterators[i] = XNEWVEC (char, len);
1300
      snprintf (iterators[i], len, "git_%d", i);
1301
    }
1302
 
1303
  cloog_names_set_nb_iterators (cloog_program_names (prog),
1304
                                nb_iterators);
1305
  cloog_names_set_iterators (cloog_program_names (prog),
1306
                             iterators);
1307
 
1308
  for (i = 0; i < nb_scattering; i++)
1309
    {
1310
      int len = 5 + 16;
1311
      scattering[i] = XNEWVEC (char, len);
1312
      snprintf (scattering[i], len, "scat_%d", i);
1313
    }
1314
 
1315
  cloog_names_set_nb_scattering (cloog_program_names (prog),
1316
                                 nb_scattering);
1317
  cloog_names_set_scattering (cloog_program_names (prog),
1318
                              scattering);
1319
}
1320
 
1321
/* Initialize a CLooG input file.  */
1322
 
1323
static FILE *
1324
init_cloog_input_file (int scop_number)
1325
{
1326
  FILE *graphite_out_file;
1327
  int len = strlen (dump_base_name);
1328
  char *dumpname = XNEWVEC (char, len + 25);
1329
  char *s_scop_number = XNEWVEC (char, 15);
1330
 
1331
  memcpy (dumpname, dump_base_name, len + 1);
1332
  strip_off_ending (dumpname, len);
1333
  sprintf (s_scop_number, ".%d", scop_number);
1334
  strcat (dumpname, s_scop_number);
1335
  strcat (dumpname, ".cloog");
1336
  graphite_out_file = fopen (dumpname, "w+b");
1337
 
1338
  if (graphite_out_file == 0)
1339
    fatal_error ("can%'t open %s for writing: %m", dumpname);
1340
 
1341
  free (dumpname);
1342
 
1343
  return graphite_out_file;
1344
}
1345
 
1346
/* Build cloog program for SCoP.  */
1347
 
1348
static void
1349
build_cloog_prog (scop_p scop, CloogProgram *prog,
1350
                  CloogOptions *options)
1351
{
1352
  int i;
1353
  int max_nb_loops = scop_max_loop_depth (scop);
1354
  poly_bb_p pbb;
1355
  CloogLoop *loop_list = NULL;
1356
  CloogBlockList *block_list = NULL;
1357
  CloogScatteringList *scattering = NULL;
1358
  int nbs = 2 * max_nb_loops + 1;
1359
  int *scaldims;
1360
 
1361
  cloog_program_set_context
1362
    (prog, new_Cloog_Domain_from_ppl_Pointset_Powerset (SCOP_CONTEXT (scop),
1363
      scop_nb_params (scop), cloog_state));
1364
  nbs = unify_scattering_dimensions (scop);
1365
  scaldims = (int *) xmalloc (nbs * (sizeof (int)));
1366
  cloog_program_set_nb_scattdims (prog, nbs);
1367
  initialize_cloog_names (scop, prog);
1368
 
1369
  FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
1370
    {
1371
      CloogStatement *stmt;
1372
      CloogBlock *block;
1373
      CloogDomain *dom;
1374
 
1375
      /* Dead code elimination: when the domain of a PBB is empty,
1376
         don't generate code for the PBB.  */
1377
      if (ppl_Pointset_Powerset_C_Polyhedron_is_empty (PBB_DOMAIN (pbb)))
1378
        continue;
1379
 
1380
      /* Build the new statement and its block.  */
1381
      stmt = cloog_statement_alloc (cloog_state, pbb_index (pbb));
1382
      dom = new_Cloog_Domain_from_ppl_Pointset_Powerset (PBB_DOMAIN (pbb),
1383
                                                         scop_nb_params (scop),
1384
                                                         cloog_state);
1385
      block = cloog_block_alloc (stmt, 0, NULL, pbb_dim_iter_domain (pbb));
1386
      cloog_statement_set_usr (stmt, pbb);
1387
 
1388
      /* Build loop list.  */
1389
      {
1390
        CloogLoop *new_loop_list = cloog_loop_malloc (cloog_state);
1391
        cloog_loop_set_next (new_loop_list, loop_list);
1392
        cloog_loop_set_domain (new_loop_list, dom);
1393
        cloog_loop_set_block (new_loop_list, block);
1394
        loop_list = new_loop_list;
1395
      }
1396
 
1397
      /* Build block list.  */
1398
      {
1399
        CloogBlockList *new_block_list = cloog_block_list_malloc ();
1400
 
1401
        cloog_block_list_set_next (new_block_list, block_list);
1402
        cloog_block_list_set_block (new_block_list, block);
1403
        block_list = new_block_list;
1404
      }
1405
 
1406
      /* Build scattering list.  */
1407
      {
1408
        /* XXX: Replace with cloog_domain_list_alloc(), when available.  */
1409
        CloogScatteringList *new_scattering
1410
          = (CloogScatteringList *) xmalloc (sizeof (CloogScatteringList));
1411
        ppl_Polyhedron_t scat;
1412
        CloogScattering *dom;
1413
 
1414
        scat = PBB_TRANSFORMED_SCATTERING (pbb);
1415
        dom = new_Cloog_Scattering_from_ppl_Polyhedron
1416
          (scat, scop_nb_params (scop), pbb_nb_scattering_transform (pbb),
1417
           cloog_state);
1418
 
1419
        cloog_set_next_scattering (new_scattering, scattering);
1420
        cloog_set_scattering (new_scattering, dom);
1421
        scattering = new_scattering;
1422
      }
1423
    }
1424
 
1425
  cloog_program_set_loop (prog, loop_list);
1426
  cloog_program_set_blocklist (prog, block_list);
1427
 
1428
  for (i = 0; i < nbs; i++)
1429
    scaldims[i] = 0 ;
1430
 
1431
  cloog_program_set_scaldims (prog, scaldims);
1432
 
1433
  /* Extract scalar dimensions to simplify the code generation problem.  */
1434
  cloog_program_extract_scalars (prog, scattering, options);
1435
 
1436
  /* Dump a .cloog input file, if requested.  This feature is only
1437
     enabled in the Graphite branch.  */
1438
  if (0)
1439
    {
1440
      static size_t file_scop_number = 0;
1441
      FILE *cloog_file = init_cloog_input_file (file_scop_number);
1442
 
1443
      cloog_program_dump_cloog (cloog_file, prog, scattering);
1444
      ++file_scop_number;
1445
    }
1446
 
1447
  /* Apply scattering.  */
1448
  cloog_program_scatter (prog, scattering, options);
1449
  free_scattering (scattering);
1450
 
1451
  /* Iterators corresponding to scalar dimensions have to be extracted.  */
1452
  cloog_names_scalarize (cloog_program_names (prog), nbs,
1453
                         cloog_program_scaldims (prog));
1454
 
1455
  /* Free blocklist.  */
1456
  {
1457
    CloogBlockList *next = cloog_program_blocklist (prog);
1458
 
1459
    while (next)
1460
      {
1461
        CloogBlockList *toDelete = next;
1462
        next = cloog_block_list_next (next);
1463
        cloog_block_list_set_next (toDelete, NULL);
1464
        cloog_block_list_set_block (toDelete, NULL);
1465
        cloog_block_list_free (toDelete);
1466
      }
1467
    cloog_program_set_blocklist (prog, NULL);
1468
  }
1469
}
1470
 
1471
/* Return the options that will be used in GLOOG.  */
1472
 
1473
static CloogOptions *
1474
set_cloog_options (void)
1475
{
1476
  CloogOptions *options = cloog_options_malloc (cloog_state);
1477
 
1478
  /* Change cloog output language to C.  If we do use FORTRAN instead, cloog
1479
     will stop e.g. with "ERROR: unbounded loops not allowed in FORTRAN.", if
1480
     we pass an incomplete program to cloog.  */
1481
  options->language = CLOOG_LANGUAGE_C;
1482
 
1483
  /* Enable complex equality spreading: removes dummy statements
1484
     (assignments) in the generated code which repeats the
1485
     substitution equations for statements.  This is useless for
1486
     GLooG.  */
1487
  options->esp = 1;
1488
 
1489
#ifdef CLOOG_ORG
1490
  /* Silence CLooG to avoid failing tests due to debug output to stderr.  */
1491
  options->quiet = 1;
1492
#else
1493
  /* Enable C pretty-printing mode: normalizes the substitution
1494
     equations for statements.  */
1495
  options->cpp = 1;
1496
#endif
1497
 
1498
  /* Allow cloog to build strides with a stride width different to one.
1499
     This example has stride = 4:
1500
 
1501
     for (i = 0; i < 20; i += 4)
1502
       A  */
1503
  options->strides = 1;
1504
 
1505
  /* Disable optimizations and make cloog generate source code closer to the
1506
     input.  This is useful for debugging,  but later we want the optimized
1507
     code.
1508
 
1509
     XXX: We can not disable optimizations, as loop blocking is not working
1510
     without them.  */
1511
  if (0)
1512
    {
1513
      options->f = -1;
1514
      options->l = INT_MAX;
1515
    }
1516
 
1517
  return options;
1518
}
1519
 
1520
/* Prints STMT to STDERR.  */
1521
 
1522
void
1523
print_clast_stmt (FILE *file, struct clast_stmt *stmt)
1524
{
1525
  CloogOptions *options = set_cloog_options ();
1526
 
1527
  clast_pprint (file, stmt, 0, options);
1528
  cloog_options_free (options);
1529
}
1530
 
1531
/* Prints STMT to STDERR.  */
1532
 
1533
DEBUG_FUNCTION void
1534
debug_clast_stmt (struct clast_stmt *stmt)
1535
{
1536
  print_clast_stmt (stderr, stmt);
1537
}
1538
 
1539
/* Translate SCOP to a CLooG program and clast.  These two
1540
   representations should be freed together: a clast cannot be used
1541
   without a program.  */
1542
 
1543
cloog_prog_clast
1544
scop_to_clast (scop_p scop)
1545
{
1546
  CloogOptions *options = set_cloog_options ();
1547
  cloog_prog_clast pc;
1548
 
1549
  /* Connect new cloog prog generation to graphite.  */
1550
  pc.prog = cloog_program_malloc ();
1551
  build_cloog_prog (scop, pc.prog, options);
1552
  pc.prog = cloog_program_generate (pc.prog, options);
1553
  pc.stmt = cloog_clast_create (pc.prog, options);
1554
 
1555
  cloog_options_free (options);
1556
  return pc;
1557
}
1558
 
1559
/* Prints to FILE the code generated by CLooG for SCOP.  */
1560
 
1561
void
1562
print_generated_program (FILE *file, scop_p scop)
1563
{
1564
  CloogOptions *options = set_cloog_options ();
1565
 
1566
  cloog_prog_clast pc = scop_to_clast (scop);
1567
 
1568
  fprintf (file, "       (prog: \n");
1569
  cloog_program_print (file, pc.prog);
1570
  fprintf (file, "       )\n");
1571
 
1572
  fprintf (file, "       (clast: \n");
1573
  clast_pprint (file, pc.stmt, 0, options);
1574
  fprintf (file, "       )\n");
1575
 
1576
  cloog_options_free (options);
1577
  cloog_clast_free (pc.stmt);
1578
  cloog_program_free (pc.prog);
1579
}
1580
 
1581
/* Prints to STDERR the code generated by CLooG for SCOP.  */
1582
 
1583
DEBUG_FUNCTION void
1584
debug_generated_program (scop_p scop)
1585
{
1586
  print_generated_program (stderr, scop);
1587
}
1588
 
1589
/* Add CLooG names to parameter index.  The index is used to translate
1590
   back from CLooG names to GCC trees.  */
1591
 
1592
static void
1593
create_params_index (scop_p scop, htab_t index_table, CloogProgram *prog) {
1594
  CloogNames* names = cloog_program_names (prog);
1595
  int nb_parameters = cloog_names_nb_parameters (names);
1596
  char **parameters = cloog_names_parameters (names);
1597
  int i;
1598
  mpz_t bound_one, bound_two;
1599
 
1600
  mpz_init (bound_one);
1601
  mpz_init (bound_two);
1602
 
1603
  for (i = 0; i < nb_parameters; i++)
1604
    {
1605
      compute_bounds_for_param (scop, i, bound_one, bound_two);
1606
      save_clast_name_index (index_table, parameters[i], i, i,
1607
                             bound_one, bound_two);
1608
    }
1609
 
1610
  mpz_clear (bound_one);
1611
  mpz_clear (bound_two);
1612
}
1613
 
1614
/* GIMPLE Loop Generator: generates loops from STMT in GIMPLE form for
1615
   the given SCOP.  Return true if code generation succeeded.
1616
   BB_PBB_MAPPING is a basic_block and it's related poly_bb_p mapping.
1617
*/
1618
 
1619
bool
1620
gloog (scop_p scop, htab_t bb_pbb_mapping)
1621
{
1622
  VEC (tree, heap) *newivs = VEC_alloc (tree, heap, 10);
1623
  loop_p context_loop;
1624
  sese region = SCOP_REGION (scop);
1625
  ifsese if_region = NULL;
1626
  htab_t newivs_index, params_index;
1627
  cloog_prog_clast pc;
1628
  struct ivs_params ip;
1629
 
1630
  timevar_push (TV_GRAPHITE_CODE_GEN);
1631
  gloog_error = false;
1632
 
1633
  pc = scop_to_clast (scop);
1634
 
1635
  if (dump_file && (dump_flags & TDF_DETAILS))
1636
    {
1637
      fprintf (dump_file, "\nCLAST generated by CLooG: \n");
1638
      print_clast_stmt (dump_file, pc.stmt);
1639
      fprintf (dump_file, "\n");
1640
    }
1641
 
1642
  recompute_all_dominators ();
1643
  graphite_verify ();
1644
 
1645
  if_region = move_sese_in_condition (region);
1646
  sese_insert_phis_for_liveouts (region,
1647
                                 if_region->region->exit->src,
1648
                                 if_region->false_region->exit,
1649
                                 if_region->true_region->exit);
1650
  recompute_all_dominators ();
1651
  graphite_verify ();
1652
 
1653
  context_loop = SESE_ENTRY (region)->src->loop_father;
1654
  newivs_index = htab_create (10, clast_name_index_elt_info,
1655
                              eq_clast_name_indexes, free_clast_name_index);
1656
  params_index = htab_create (10, clast_name_index_elt_info,
1657
                              eq_clast_name_indexes, free_clast_name_index);
1658
 
1659
  create_params_index (scop, params_index, pc.prog);
1660
 
1661
  ip.newivs = &newivs;
1662
  ip.newivs_index = newivs_index;
1663
  ip.params = SESE_PARAMS (region);
1664
  ip.params_index = params_index;
1665
  ip.region = region;
1666
 
1667
  translate_clast (context_loop, pc.stmt, if_region->true_region->entry,
1668
                   bb_pbb_mapping, 0, &ip);
1669
  graphite_verify ();
1670
  scev_reset ();
1671
  recompute_all_dominators ();
1672
  graphite_verify ();
1673
 
1674
  if (gloog_error)
1675
    set_ifsese_condition (if_region, integer_zero_node);
1676
 
1677
  free (if_region->true_region);
1678
  free (if_region->region);
1679
  free (if_region);
1680
 
1681
  htab_delete (newivs_index);
1682
  htab_delete (params_index);
1683
  VEC_free (tree, heap, newivs);
1684
  cloog_clast_free (pc.stmt);
1685
  cloog_program_free (pc.prog);
1686
  timevar_pop (TV_GRAPHITE_CODE_GEN);
1687
 
1688
  if (dump_file && (dump_flags & TDF_DETAILS))
1689
    {
1690
      loop_p loop;
1691
      loop_iterator li;
1692
      int num_no_dependency = 0;
1693
 
1694
      FOR_EACH_LOOP (li, loop, 0)
1695
        if (loop->can_be_parallel)
1696
          num_no_dependency++;
1697
 
1698
      fprintf (dump_file, "\n%d loops carried no dependency.\n",
1699
               num_no_dependency);
1700
    }
1701
 
1702
  return !gloog_error;
1703
}
1704
#endif

powered by: WebSVN 2.1.0

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