gcc/graphite.c

   1 /* Gimple Represented as Polyhedra.
   2    Copyright (C) 2006, 2007, 2008, 2009 Free Software Foundation, Inc.
   3    Contributed by Sebastian Pop <sebastian.pop@inria.fr>.
   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 /* This pass converts GIMPLE to GRAPHITE, performs some loop
  22    transformations and then converts the resulting representation back
  23    to GIMPLE.
  24
  25    An early description of this pass can be found in the GCC Summit'06
  26    paper "GRAPHITE: Polyhedral Analyses and Optimizations for GCC".
  27    The wiki page http://gcc.gnu.org/wiki/Graphite contains pointers to
  28    the related work.
  29
  30    One important document to read is CLooG's internal manual:
  31    http://repo.or.cz/w/cloog-ppl.git?a=blob_plain;f=doc/cloog.texi;hb=HEAD
  32    that describes the data structure of loops used in this file, and
  33    the functions that are used for transforming the code.  */
  34
  35 #include "config.h"
  36 #include "system.h"
  37 #include "coretypes.h"
  38 #include "tm.h"
  39 #include "ggc.h"
  40 #include "tree.h"
  41 #include "rtl.h"
  42 #include "basic-block.h"
  43 #include "diagnostic.h"
  44 #include "tree-flow.h"
  45 #include "toplev.h"
  46 #include "tree-dump.h"
  47 #include "timevar.h"
  48 #include "cfgloop.h"
  49 #include "tree-chrec.h"
  50 #include "tree-data-ref.h"
  51 #include "tree-scalar-evolution.h"
  52 #include "tree-pass.h"
  53 #include "domwalk.h"
  54 #include "value-prof.h"
  55 #include "pointer-set.h"
  56 #include "gimple.h"
  57
  58 #ifdef HAVE_cloog
  59 #include "cloog/cloog.h"
  60 #include "graphite.h"
  61
  62 static VEC (scop_p, heap) *current_scops;
  63
  64 /* Converts a GMP constant V to a tree and returns it.  */
  65
  66 static tree
  67 gmp_cst_to_tree (tree type, Value v)
  68 {
  69   return build_int_cst (type, value_get_si (v));
  70 }
  71
  72 /* Returns true when BB is in REGION.  */
  73
  74 static bool
  75 bb_in_sese_p (basic_block bb, sese region)
  76 {
  77   return pointer_set_contains (SESE_REGION_BBS (region), bb);
  78 }
  79
  80 /* Returns true when LOOP is in the SESE region R.  */
  81
  82 static inline bool
  83 loop_in_sese_p (struct loop *loop, sese r)
  84 {
  85   return (bb_in_sese_p (loop->header, r)
  86           && bb_in_sese_p (loop->latch, r));
  87 }
  88
  89 /* For a USE in BB, if BB is outside REGION, mark the USE in the
  90    SESE_LIVEIN and SESE_LIVEOUT sets.  */
  91
  92 static void
  93 sese_build_livein_liveouts_use (sese region, basic_block bb, tree use)
  94 {
  95   unsigned ver;
  96   basic_block def_bb;
  97
  98   if (TREE_CODE (use) != SSA_NAME)
  99     return;
 100
 101   ver = SSA_NAME_VERSION (use);
 102   def_bb = gimple_bb (SSA_NAME_DEF_STMT (use));
 103   if (!def_bb
 104       || !bb_in_sese_p (def_bb, region)
 105       || bb_in_sese_p (bb, region))
 106     return;
 107
 108   if (!SESE_LIVEIN_VER (region, ver))
 109     SESE_LIVEIN_VER (region, ver) = BITMAP_ALLOC (NULL);
 110
 111   bitmap_set_bit (SESE_LIVEIN_VER (region, ver), bb->index);
 112   bitmap_set_bit (SESE_LIVEOUT (region), ver);
 113 }
 114
 115 /* Marks for rewrite all the SSA_NAMES defined in REGION and that are
 116    used in BB that is outside of the REGION.  */
 117
 118 static void
 119 sese_build_livein_liveouts_bb (sese region, basic_block bb)
 120 {
 121   gimple_stmt_iterator bsi;
 122   edge e;
 123   edge_iterator ei;
 124   ssa_op_iter iter;
 125   tree var;
 126
 127   FOR_EACH_EDGE (e, ei, bb->succs)
 128     for (bsi = gsi_start_phis (e->dest); !gsi_end_p (bsi); gsi_next (&bsi))
 129       sese_build_livein_liveouts_use (region, bb,
 130                                       PHI_ARG_DEF_FROM_EDGE (gsi_stmt (bsi), e));
 131
 132   for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
 133     FOR_EACH_SSA_TREE_OPERAND (var, gsi_stmt (bsi), iter, SSA_OP_ALL_USES)
 134       sese_build_livein_liveouts_use (region, bb, var);
 135 }
 136
 137 /* Build the SESE_LIVEIN and SESE_LIVEOUT for REGION.  */
 138
 139 void
 140 sese_build_livein_liveouts (sese region)
 141 {
 142   basic_block bb;
 143
 144   SESE_LIVEOUT (region) = BITMAP_ALLOC (NULL);
 145   SESE_NUM_VER (region) = num_ssa_names;
 146   SESE_LIVEIN (region) = XCNEWVEC (bitmap, SESE_NUM_VER (region));
 147
 148   FOR_EACH_BB (bb)
 149     sese_build_livein_liveouts_bb (region, bb);
 150 }
 151
 152 /* Register basic blocks belonging to a region in a pointer set.  */
 153
 154 static void
 155 register_bb_in_sese (basic_block entry_bb, basic_block exit_bb, sese region)
 156 {
 157   edge_iterator ei;
 158   edge e;
 159   basic_block bb = entry_bb;
 160
 161   FOR_EACH_EDGE (e, ei, bb->succs)
 162     {
 163       if (!pointer_set_contains (SESE_REGION_BBS (region), e->dest) &&
 164           e->dest->index != exit_bb->index)
 165         {
 166           pointer_set_insert (SESE_REGION_BBS (region), e->dest);
 167           register_bb_in_sese (e->dest, exit_bb, region);
 168         }
 169     }
 170 }
 171
 172 /* Builds a new SESE region from edges ENTRY and EXIT.  */
 173
 174 sese
 175 new_sese (edge entry, edge exit)
 176 {
 177   sese res = XNEW (struct sese);
 178
 179   SESE_ENTRY (res) = entry;
 180   SESE_EXIT (res) = exit;
 181   SESE_REGION_BBS (res) = pointer_set_create ();
 182   register_bb_in_sese (entry->dest, exit->dest, res);
 183
 184   SESE_LIVEOUT (res) = NULL;
 185   SESE_NUM_VER (res) = 0;
 186   SESE_LIVEIN (res) = NULL;
 187
 188   return res;
 189 }
 190
 191 /* Deletes REGION.  */
 192
 193 void
 194 free_sese (sese region)
 195 {
 196   int i;
 197
 198   for (i = 0; i < SESE_NUM_VER (region); i++)
 199     BITMAP_FREE (SESE_LIVEIN_VER (region, i));
 200
 201   if (SESE_LIVEIN (region))
 202     free (SESE_LIVEIN (region));
 203
 204   if (SESE_LIVEOUT (region))
 205     BITMAP_FREE (SESE_LIVEOUT (region));
 206
 207   pointer_set_destroy (SESE_REGION_BBS (region));
 208   XDELETE (region);
 209 }
 210
 211 \f
 212
 213 /* Debug the list of old induction variables for this SCOP.  */
 214
 215 void
 216 debug_oldivs (scop_p scop)
 217 {
 218   int i;
 219   name_tree oldiv;
 220
 221   fprintf (stderr, "Old IVs:");
 222
 223   for (i = 0; VEC_iterate (name_tree, SCOP_OLDIVS (scop), i, oldiv); i++)
 224     {
 225       fprintf (stderr, "(");
 226       print_generic_expr (stderr, oldiv->t, 0);
 227       fprintf (stderr, ", %s, %d)\n", oldiv->name, oldiv->loop->num);
 228     }
 229   fprintf (stderr, "\n");
 230 }
 231
 232 /* Debug the loops around basic block GB.  */
 233
 234 void
 235 debug_loop_vec (graphite_bb_p gb)
 236 {
 237   int i;
 238   loop_p loop;
 239
 240   fprintf (stderr, "Loop Vec:");
 241
 242   for (i = 0; VEC_iterate (loop_p, GBB_LOOPS (gb), i, loop); i++)
 243     fprintf (stderr, "%d: %d, ", i, loop ? loop->num : -1);
 244
 245   fprintf (stderr, "\n");
 246 }
 247
 248 /* Returns true if stack ENTRY is a constant.  */
 249
 250 static bool
 251 iv_stack_entry_is_constant (iv_stack_entry *entry)
 252 {
 253   return entry->kind == iv_stack_entry_const;
 254 }
 255
 256 /* Returns true if stack ENTRY is an induction variable.  */
 257
 258 static bool
 259 iv_stack_entry_is_iv (iv_stack_entry *entry)
 260 {
 261   return entry->kind == iv_stack_entry_iv;
 262 }
 263
 264 /* Push (IV, NAME) on STACK.  */
 265
 266 static void
 267 loop_iv_stack_push_iv (loop_iv_stack stack, tree iv, const char *name)
 268 {
 269   iv_stack_entry *entry = XNEW (iv_stack_entry);
 270   name_tree named_iv = XNEW (struct name_tree);
 271
 272   named_iv->t = iv;
 273   named_iv->name = name;
 274
 275   entry->kind = iv_stack_entry_iv;
 276   entry->data.iv = named_iv;
 277
 278   VEC_safe_push (iv_stack_entry_p, heap, *stack, entry);
 279 }
 280
 281 /* Inserts a CONSTANT in STACK at INDEX.  */
 282
 283 static void
 284 loop_iv_stack_insert_constant (loop_iv_stack stack, int index,
 285                                tree constant)
 286 {
 287   iv_stack_entry *entry = XNEW (iv_stack_entry);
 288
 289   entry->kind = iv_stack_entry_const;
 290   entry->data.constant = constant;
 291
 292   VEC_safe_insert (iv_stack_entry_p, heap, *stack, index, entry);
 293 }
 294
 295 /* Pops and frees an element out of STACK.  */
 296
 297 static void
 298 loop_iv_stack_pop (loop_iv_stack stack)
 299 {
 300   iv_stack_entry_p entry = VEC_pop (iv_stack_entry_p, *stack);
 301
 302   free (entry->data.iv);
 303   free (entry);
 304 }
 305
 306 /* Get the IV at INDEX in STACK.  */
 307
 308 static tree
 309 loop_iv_stack_get_iv (loop_iv_stack stack, int index)
 310 {
 311   iv_stack_entry_p entry = VEC_index (iv_stack_entry_p, *stack, index);
 312   iv_stack_entry_data data = entry->data;
 313
 314   return iv_stack_entry_is_iv (entry) ? data.iv->t : data.constant;
 315 }
 316
 317 /* Get the IV from its NAME in STACK.  */
 318
 319 static tree
 320 loop_iv_stack_get_iv_from_name (loop_iv_stack stack, const char* name)
 321 {
 322   int i;
 323   iv_stack_entry_p entry;
 324
 325   for (i = 0; VEC_iterate (iv_stack_entry_p, *stack, i, entry); i++)
 326     {
 327       name_tree iv = entry->data.iv;
 328       if (!strcmp (name, iv->name))
 329         return iv->t;
 330     }
 331
 332   return NULL;
 333 }
 334
 335 /* Prints on stderr the contents of STACK.  */
 336
 337 void
 338 debug_loop_iv_stack (loop_iv_stack stack)
 339 {
 340   int i;
 341   iv_stack_entry_p entry;
 342   bool first = true;
 343
 344   fprintf (stderr, "(");
 345
 346   for (i = 0; VEC_iterate (iv_stack_entry_p, *stack, i, entry); i++)
 347     {
 348       if (first)
 349         first = false;
 350       else
 351         fprintf (stderr, " ");
 352
 353       if (iv_stack_entry_is_iv (entry))
 354         {
 355           name_tree iv = entry->data.iv;
 356           fprintf (stderr, "%s:", iv->name);
 357           print_generic_expr (stderr, iv->t, 0);
 358         }
 359       else
 360         {
 361           tree constant = entry->data.constant;
 362           print_generic_expr (stderr, constant, 0);
 363           fprintf (stderr, ":");
 364           print_generic_expr (stderr, constant, 0);
 365         }
 366     }
 367
 368   fprintf (stderr, ")\n");
 369 }
 370
 371 /* Frees STACK.  */
 372
 373 static void
 374 free_loop_iv_stack (loop_iv_stack stack)
 375 {
 376   int i;
 377   iv_stack_entry_p entry;
 378
 379   for (i = 0; VEC_iterate (iv_stack_entry_p, *stack, i, entry); i++)
 380     {
 381       free (entry->data.iv);
 382       free (entry);
 383     }
 384
 385   VEC_free (iv_stack_entry_p, heap, *stack);
 386 }
 387
 388 \f
 389
 390 /* Structure containing the mapping between the CLooG's induction
 391    variable and the type of the old induction variable.  */
 392 typedef struct ivtype_map_elt
 393 {
 394   tree type;
 395   const char *cloog_iv;
 396 } *ivtype_map_elt;
 397
 398 /* Print to stderr the element ELT.  */
 399
 400 static void
 401 debug_ivtype_elt (ivtype_map_elt elt)
 402 {
 403   fprintf (stderr, "(%s, ", elt->cloog_iv);
 404   print_generic_expr (stderr, elt->type, 0);
 405   fprintf (stderr, ")\n");
 406 }
 407
 408 /* Helper function for debug_ivtype_map.  */
 409
 410 static int
 411 debug_ivtype_map_1 (void **slot, void *s ATTRIBUTE_UNUSED)
 412 {
 413   struct ivtype_map_elt *entry = (struct ivtype_map_elt *) *slot;
 414   debug_ivtype_elt (entry);
 415   return 1;
 416 }
 417
 418 /* Print to stderr all the elements of MAP.  */
 419
 420 void
 421 debug_ivtype_map (htab_t map)
 422 {
 423   htab_traverse (map, debug_ivtype_map_1, NULL);
 424 }
 425
 426 /* Constructs a new SCEV_INFO_STR structure for VAR and INSTANTIATED_BELOW.  */
 427
 428 static inline ivtype_map_elt
 429 new_ivtype_map_elt (const char *cloog_iv, tree type)
 430 {
 431   ivtype_map_elt res;
 432
 433   res = XNEW (struct ivtype_map_elt);
 434   res->cloog_iv = cloog_iv;
 435   res->type = type;
 436
 437   return res;
 438 }
 439
 440 /* Computes a hash function for database element ELT.  */
 441
 442 static hashval_t
 443 ivtype_map_elt_info (const void *elt)
 444 {
 445   return htab_hash_pointer (((const struct ivtype_map_elt *) elt)->cloog_iv);
 446 }
 447
 448 /* Compares database elements E1 and E2.  */
 449
 450 static int
 451 eq_ivtype_map_elts (const void *e1, const void *e2)
 452 {
 453   const struct ivtype_map_elt *elt1 = (const struct ivtype_map_elt *) e1;
 454   const struct ivtype_map_elt *elt2 = (const struct ivtype_map_elt *) e2;
 455
 456   return (elt1->cloog_iv == elt2->cloog_iv);
 457 }
 458
 459 \f
 460
 461 /* Given a CLOOG_IV, returns the type that it should have in GCC land.
 462    If the information is not available, i.e. in the case one of the
 463    transforms created the loop, just return integer_type_node.  */
 464
 465 static tree
 466 gcc_type_for_cloog_iv (const char *cloog_iv, graphite_bb_p gbb)
 467 {
 468   struct ivtype_map_elt tmp;
 469   PTR *slot;
 470
 471   tmp.cloog_iv = cloog_iv;
 472   slot = htab_find_slot (GBB_CLOOG_IV_TYPES (gbb), &tmp, NO_INSERT);
 473
 474   if (slot && *slot)
 475     return ((ivtype_map_elt) *slot)->type;
 476
 477   return integer_type_node;
 478 }
 479
 480 /* Inserts constants derived from the USER_STMT argument list into the
 481    STACK.  This is needed to map old ivs to constants when loops have
 482    been eliminated.  */
 483
 484 static void
 485 loop_iv_stack_patch_for_consts (loop_iv_stack stack,
 486                                 struct clast_user_stmt *user_stmt)
 487 {
 488   struct clast_stmt *t;
 489   int index = 0;
 490   CloogStatement *cs = user_stmt->statement;
 491   graphite_bb_p gbb = (graphite_bb_p) cloog_statement_usr (cs);
 492
 493   for (t = user_stmt->substitutions; t; t = t->next)
 494     {
 495       struct clast_expr *expr = (struct clast_expr *)
 496         ((struct clast_assignment *)t)->RHS;
 497       struct clast_term *term = (struct clast_term *) expr;
 498
 499       /* FIXME: What should be done with expr_bin, expr_red?  */
 500       if (expr->type == expr_term
 501           && !term->var)
 502         {
 503           loop_p loop = gbb_loop_at_index (gbb, index);
 504           tree oldiv = oldiv_for_loop (GBB_SCOP (gbb), loop);
 505           tree type = oldiv ? TREE_TYPE (oldiv) : integer_type_node;
 506           tree value = gmp_cst_to_tree (type, term->val);
 507           loop_iv_stack_insert_constant (stack, index, value);
 508         }
 509       index = index + 1;
 510     }
 511 }
 512
 513 /* Removes all constants in the iv STACK.  */
 514
 515 static void
 516 loop_iv_stack_remove_constants (loop_iv_stack stack)
 517 {
 518   int i;
 519   iv_stack_entry *entry;
 520
 521   for (i = 0; VEC_iterate (iv_stack_entry_p, *stack, i, entry);)
 522     {
 523       if (iv_stack_entry_is_constant (entry))
 524         {
 525           free (VEC_index (iv_stack_entry_p, *stack, i));
 526           VEC_ordered_remove (iv_stack_entry_p, *stack, i);
 527         }
 528       else
 529         i++;
 530     }
 531 }
 532
 533 /* Returns a new loop_to_cloog_loop_str structure.  */
 534
 535 static inline struct loop_to_cloog_loop_str *
 536 new_loop_to_cloog_loop_str (int loop_num,
 537                             int loop_position,
 538                             CloogLoop *cloog_loop)
 539 {
 540   struct loop_to_cloog_loop_str *result;
 541
 542   result = XNEW (struct loop_to_cloog_loop_str);
 543   result->loop_num = loop_num;
 544   result->cloog_loop = cloog_loop;
 545   result->loop_position = loop_position;
 546
 547   return result;
 548 }
 549
 550 /* Hash function for SCOP_LOOP2CLOOG_LOOP hash table.  */
 551
 552 static hashval_t
 553 hash_loop_to_cloog_loop (const void *elt)
 554 {
 555   return ((const struct loop_to_cloog_loop_str *) elt)->loop_num;
 556 }
 557
 558 /* Equality function for SCOP_LOOP2CLOOG_LOOP hash table.  */
 559
 560 static int
 561 eq_loop_to_cloog_loop (const void *el1, const void *el2)
 562 {
 563   const struct loop_to_cloog_loop_str *elt1, *elt2;
 564
 565   elt1 = (const struct loop_to_cloog_loop_str *) el1;
 566   elt2 = (const struct loop_to_cloog_loop_str *) el2;
 567   return elt1->loop_num == elt2->loop_num;
 568 }
 569
 570 /* Compares two graphite bbs and returns an integer less than, equal to, or
 571    greater than zero if the first argument is considered to be respectively
 572    less than, equal to, or greater than the second.
 573    We compare using the lexicographic order of the static schedules.  */
 574
 575 static int
 576 gbb_compare (const void *p_1, const void *p_2)
 577 {
 578   const struct graphite_bb *const gbb_1
 579     = *(const struct graphite_bb *const*) p_1;
 580   const struct graphite_bb *const gbb_2
 581     = *(const struct graphite_bb *const*) p_2;
 582
 583   return lambda_vector_compare (GBB_STATIC_SCHEDULE (gbb_1),
 584                                 gbb_nb_loops (gbb_1) + 1,
 585                                 GBB_STATIC_SCHEDULE (gbb_2),
 586                                 gbb_nb_loops (gbb_2) + 1);
 587 }
 588
 589 /* Sort graphite bbs in SCOP.  */
 590
 591 static void
 592 graphite_sort_gbbs (scop_p scop)
 593 {
 594   VEC (graphite_bb_p, heap) *bbs = SCOP_BBS (scop);
 595
 596   qsort (VEC_address (graphite_bb_p, bbs),
 597          VEC_length (graphite_bb_p, bbs),
 598          sizeof (graphite_bb_p), gbb_compare);
 599 }
 600
 601 /* Dump conditions of a graphite basic block GBB on FILE.  */
 602
 603 static void
 604 dump_gbb_conditions (FILE *file, graphite_bb_p gbb)
 605 {
 606   int i;
 607   gimple stmt;
 608   VEC (gimple, heap) *conditions = GBB_CONDITIONS (gbb);
 609
 610   if (VEC_empty (gimple, conditions))
 611     return;
 612
 613   fprintf (file, "\tbb %d\t: cond = {", GBB_BB (gbb)->index);
 614
 615   for (i = 0; VEC_iterate (gimple, conditions, i, stmt); i++)
 616     print_gimple_stmt (file, stmt, 0, 0);
 617
 618   fprintf (file, "}\n");
 619 }
 620
 621 /* Converts the graphite scheduling function into a cloog scattering
 622    matrix.  This scattering matrix is used to limit the possible cloog
 623    output to valid programs in respect to the scheduling function.
 624
 625    SCATTERING_DIMENSIONS specifies the dimensionality of the scattering
 626    matrix. CLooG 0.14.0 and previous versions require, that all scattering
 627    functions of one CloogProgram have the same dimensionality, therefore we
 628    allow to specify it. (Should be removed in future versions)  */
 629
 630 static CloogMatrix *
 631 schedule_to_scattering (graphite_bb_p gb, int scattering_dimensions)
 632 {
 633   int i;
 634   scop_p scop = GBB_SCOP (gb);
 635
 636   int nb_iterators = gbb_nb_loops (gb);
 637
 638   /* The cloog scattering matrix consists of these colums:
 639      1                        col  = Eq/Inq,
 640      scattering_dimensions    cols = Scattering dimensions,
 641      nb_iterators             cols = bb's iterators,
 642      scop_nb_params        cols = Parameters,
 643      1                        col  = Constant 1.
 644
 645      Example:
 646
 647      scattering_dimensions = 5
 648      max_nb_iterators = 2
 649      nb_iterators = 1
 650      scop_nb_params = 2
 651
 652      Schedule:
 653      ? i
 654      4 5
 655
 656      Scattering Matrix:
 657      s1  s2  s3  s4  s5  i   p1  p2  1
 658      1   0   0   0   0   0   0   0  -4  = 0
 659      0   1   0   0   0  -1   0   0   0  = 0
 660      0   0   1   0   0   0   0   0  -5  = 0  */
 661   int nb_params = scop_nb_params (scop);
 662   int nb_cols = 1 + scattering_dimensions + nb_iterators + nb_params + 1;
 663   int col_const = nb_cols - 1;
 664   int col_iter_offset = 1 + scattering_dimensions;
 665
 666   CloogMatrix *scat = cloog_matrix_alloc (scattering_dimensions, nb_cols);
 667
 668   gcc_assert (scattering_dimensions >= nb_iterators * 2 + 1);
 669
 670   /* Initialize the identity matrix.  */
 671   for (i = 0; i < scattering_dimensions; i++)
 672     value_set_si (scat->p[i][i + 1], 1);
 673
 674   /* Textual order outside the first loop */
 675   value_set_si (scat->p[0][col_const], -GBB_STATIC_SCHEDULE (gb)[0]);
 676
 677   /* For all surrounding loops.  */
 678   for (i = 0;  i < nb_iterators; i++)
 679     {
 680       int schedule = GBB_STATIC_SCHEDULE (gb)[i + 1];
 681
 682       /* Iterations of this loop.  */
 683       value_set_si (scat->p[2 * i + 1][col_iter_offset + i], -1);
 684
 685       /* Textual order inside this loop.  */
 686       value_set_si (scat->p[2 * i + 2][col_const], -schedule);
 687     }
 688
 689   return scat;
 690 }
 691
 692 /* Print the schedules of GB to FILE with INDENT white spaces before.
 693    VERBOSITY determines how verbose the code pretty printers are.  */
 694
 695 void
 696 print_graphite_bb (FILE *file, graphite_bb_p gb, int indent, int verbosity)
 697 {
 698   CloogMatrix *scattering;
 699   int i;
 700   loop_p loop;
 701   fprintf (file, "\nGBB (\n");
 702
 703   print_loops_bb (file, GBB_BB (gb), indent+2, verbosity);
 704
 705   if (GBB_DOMAIN (gb))
 706     {
 707       fprintf (file, "       (domain: \n");
 708       cloog_matrix_print (file, GBB_DOMAIN (gb));
 709       fprintf (file, "       )\n");
 710     }
 711
 712   if (GBB_STATIC_SCHEDULE (gb))
 713     {
 714       fprintf (file, "       (static schedule: ");
 715       print_lambda_vector (file, GBB_STATIC_SCHEDULE (gb),
 716                            gbb_nb_loops (gb) + 1);
 717       fprintf (file, "       )\n");
 718     }
 719
 720   if (GBB_LOOPS (gb))
 721     {
 722       fprintf (file, "       (contained loops: \n");
 723       for (i = 0; VEC_iterate (loop_p, GBB_LOOPS (gb), i, loop); i++)
 724         if (loop == NULL)
 725           fprintf (file, "       iterator %d   =>  NULL \n", i);
 726         else
 727           fprintf (file, "       iterator %d   =>  loop %d \n", i,
 728                    loop->num);
 729       fprintf (file, "       )\n");
 730     }
 731
 732   if (GBB_DATA_REFS (gb))
 733     dump_data_references (file, GBB_DATA_REFS (gb));
 734
 735   if (GBB_CONDITIONS (gb))
 736     {
 737       fprintf (file, "       (conditions: \n");
 738       dump_gbb_conditions (file, gb);
 739       fprintf (file, "       )\n");
 740     }
 741
 742   if (GBB_SCOP (gb)
 743       && GBB_STATIC_SCHEDULE (gb))
 744     {
 745       fprintf (file, "       (scattering: \n");
 746       scattering = schedule_to_scattering (gb, 2 * gbb_nb_loops (gb) + 1);
 747       cloog_matrix_print (file, scattering);
 748       cloog_matrix_free (scattering);
 749       fprintf (file, "       )\n");
 750     }
 751
 752   fprintf (file, ")\n");
 753 }
 754
 755 /* Print to STDERR the schedules of GB with VERBOSITY level.  */
 756
 757 void
 758 debug_gbb (graphite_bb_p gb, int verbosity)
 759 {
 760   print_graphite_bb (stderr, gb, 0, verbosity);
 761 }
 762
 763
 764 /* Print SCOP to FILE.  VERBOSITY determines how verbose the pretty
 765    printers are.  */
 766
 767 static void
 768 print_scop (FILE *file, scop_p scop, int verbosity)
 769 {
 770   if (scop == NULL)
 771     return;
 772
 773   fprintf (file, "\nSCoP_%d_%d (\n",
 774            SCOP_ENTRY (scop)->index, SCOP_EXIT (scop)->index);
 775
 776   fprintf (file, "       (cloog: \n");
 777   cloog_program_print (file, SCOP_PROG (scop));
 778   fprintf (file, "       )\n");
 779
 780   if (SCOP_BBS (scop))
 781     {
 782       graphite_bb_p gb;
 783       int i;
 784
 785       for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
 786         print_graphite_bb (file, gb, 0, verbosity);
 787     }
 788
 789   fprintf (file, ")\n");
 790 }
 791
 792 /* Print all the SCOPs to FILE.  VERBOSITY determines how verbose the
 793    code pretty printers are.  */
 794
 795 static void
 796 print_scops (FILE *file, int verbosity)
 797 {
 798   int i;
 799   scop_p scop;
 800
 801   for (i = 0; VEC_iterate (scop_p, current_scops, i, scop); i++)
 802     print_scop (file, scop, verbosity);
 803 }
 804
 805 /* Debug SCOP.  VERBOSITY determines how verbose the code pretty
 806    printers are. */
 807
 808 void
 809 debug_scop (scop_p scop, int verbosity)
 810 {
 811   print_scop (stderr, scop, verbosity);
 812 }
 813
 814 /* Debug all SCOPs from CURRENT_SCOPS.  VERBOSITY determines how
 815    verbose the code pretty printers are.  */
 816
 817 void
 818 debug_scops (int verbosity)
 819 {
 820   print_scops (stderr, verbosity);
 821 }
 822
 823 /* Pretty print to FILE the SCOP in DOT format.  */
 824
 825 static void
 826 dot_scop_1 (FILE *file, scop_p scop)
 827 {
 828   edge e;
 829   edge_iterator ei;
 830   basic_block bb;
 831   basic_block entry = SCOP_ENTRY (scop);
 832   basic_block exit = SCOP_EXIT (scop);
 833
 834   fprintf (file, "digraph SCoP_%d_%d {\n", entry->index,
 835            exit->index);
 836
 837   FOR_ALL_BB (bb)
 838     {
 839       if (bb == entry)
 840         fprintf (file, "%d [shape=triangle];\n", bb->index);
 841
 842       if (bb == exit)
 843         fprintf (file, "%d [shape=box];\n", bb->index);
 844
 845       if (bb_in_sese_p (bb, SCOP_REGION (scop)))
 846         fprintf (file, "%d [color=red];\n", bb->index);
 847
 848       FOR_EACH_EDGE (e, ei, bb->succs)
 849         fprintf (file, "%d -> %d;\n", bb->index, e->dest->index);
 850     }
 851
 852   fputs ("}\n\n", file);
 853 }
 854
 855 /* Display SCOP using dotty.  */
 856
 857 void
 858 dot_scop (scop_p scop)
 859 {
 860   dot_scop_1 (stderr, scop);
 861 }
 862
 863 /* Pretty print all SCoPs in DOT format and mark them with different colors.
 864    If there are not enough colors, paint later SCoPs gray.
 865    Special nodes:
 866    - "*" after the node number: entry of a SCoP,
 867    - "#" after the node number: exit of a SCoP,
 868    - "()" entry or exit not part of SCoP.  */
 869
 870 static void
 871 dot_all_scops_1 (FILE *file)
 872 {
 873   basic_block bb;
 874   edge e;
 875   edge_iterator ei;
 876   scop_p scop;
 877   const char* color;
 878   int i;
 879
 880   /* Disable debugging while printing graph.  */
 881   int tmp_dump_flags = dump_flags;
 882   dump_flags = 0;
 883
 884   fprintf (file, "digraph all {\n");
 885
 886   FOR_ALL_BB (bb)
 887     {
 888       int part_of_scop = false;
 889
 890       /* Use HTML for every bb label.  So we are able to print bbs
 891          which are part of two different SCoPs, with two different
 892          background colors.  */
 893       fprintf (file, "%d [label=<\n  <TABLE BORDER=\"0\" CELLBORDER=\"1\" ",
 894                      bb->index);
 895       fprintf (file, "CELLSPACING=\"0\">\n");
 896
 897       /* Select color for SCoP.  */
 898       for (i = 0; VEC_iterate (scop_p, current_scops, i, scop); i++)
 899         if (bb_in_sese_p (bb, SCOP_REGION (scop))
 900             || (SCOP_EXIT (scop) == bb)
 901             || (SCOP_ENTRY (scop) == bb))
 902           {
 903             switch (i % 17)
 904               {
 905               case 0: /* red */
 906                 color = "#e41a1c";
 907                 break;
 908               case 1: /* blue */
 909                 color = "#377eb8";
 910                 break;
 911               case 2: /* green */
 912                 color = "#4daf4a";
 913                 break;
 914               case 3: /* purple */
 915                 color = "#984ea3";
 916                 break;
 917               case 4: /* orange */
 918                 color = "#ff7f00";
 919                 break;
 920               case 5: /* yellow */
 921                 color = "#ffff33";
 922                 break;
 923               case 6: /* brown */
 924                 color = "#a65628";
 925                 break;
 926               case 7: /* rose */
 927                 color = "#f781bf";
 928                 break;
 929               case 8:
 930                 color = "#8dd3c7";
 931                 break;
 932               case 9:
 933                 color = "#ffffb3";
 934                 break;
 935               case 10:
 936                 color = "#bebada";
 937                 break;
 938               case 11:
 939                 color = "#fb8072";
 940                 break;
 941               case 12:
 942                 color = "#80b1d3";
 943                 break;
 944               case 13:
 945                 color = "#fdb462";
 946                 break;
 947               case 14:
 948                 color = "#b3de69";
 949                 break;
 950               case 15:
 951                 color = "#fccde5";
 952                 break;
 953               case 16:
 954                 color = "#bc80bd";
 955                 break;
 956               default: /* gray */
 957                 color = "#999999";
 958               }
 959
 960             fprintf (file, "    <TR><TD WIDTH=\"50\" BGCOLOR=\"%s\">", color);
 961
 962             if (!bb_in_sese_p (bb, SCOP_REGION (scop)))
 963               fprintf (file, " (");
 964
 965             if (bb == SCOP_ENTRY (scop)
 966                 && bb == SCOP_EXIT (scop))
 967               fprintf (file, " %d*# ", bb->index);
 968             else if (bb == SCOP_ENTRY (scop))
 969               fprintf (file, " %d* ", bb->index);
 970             else if (bb == SCOP_EXIT (scop))
 971               fprintf (file, " %d# ", bb->index);
 972             else
 973               fprintf (file, " %d ", bb->index);
 974
 975             if (!bb_in_sese_p (bb, SCOP_REGION (scop)))
 976               fprintf (file, ")");
 977
 978             fprintf (file, "</TD></TR>\n");
 979             part_of_scop  = true;
 980           }
 981
 982       if (!part_of_scop)
 983         {
 984           fprintf (file, "    <TR><TD WIDTH=\"50\" BGCOLOR=\"#ffffff\">");
 985           fprintf (file, " %d </TD></TR>\n", bb->index);
 986         }
 987
 988       fprintf (file, "  </TABLE>>, shape=box, style=\"setlinewidth(0)\"]\n");
 989     }
 990
 991   FOR_ALL_BB (bb)
 992     {
 993       FOR_EACH_EDGE (e, ei, bb->succs)
 994               fprintf (file, "%d -> %d;\n", bb->index, e->dest->index);
 995     }
 996
 997   fputs ("}\n\n", file);
 998
 999   /* Enable debugging again.  */
1000   dump_flags = tmp_dump_flags;
1001 }
1002
1003 /* Display all SCoPs using dotty.  */
1004
1005 void
1006 dot_all_scops (void)
1007 {
1008   /* When debugging, enable the following code.  This cannot be used
1009      in production compilers because it calls "system".  */
1010 #if 0
1011   FILE *stream = fopen ("/tmp/allscops.dot", "w");
1012   gcc_assert (stream);
1013
1014   dot_all_scops_1 (stream);
1015   fclose (stream);
1016
1017   system ("dotty /tmp/allscops.dot");
1018 #else
1019   dot_all_scops_1 (stderr);
1020 #endif
1021 }
1022
1023 /* Returns the outermost loop in SCOP that contains BB.  */
1024
1025 static struct loop *
1026 outermost_loop_in_scop (scop_p scop, basic_block bb)
1027 {
1028   struct loop *nest;
1029
1030   nest = bb->loop_father;
1031   while (loop_outer (nest)
1032          && loop_in_sese_p (loop_outer (nest), SCOP_REGION (scop)))
1033     nest = loop_outer (nest);
1034
1035   return nest;
1036 }
1037
1038 /* Returns the block preceding the entry of SCOP.  */
1039
1040 static basic_block
1041 block_before_scop (scop_p scop)
1042 {
1043   return SESE_ENTRY (SCOP_REGION (scop))->src;
1044 }
1045
1046 /* Return true when EXPR is an affine function in LOOP with parameters
1047    instantiated relative to SCOP_ENTRY.  */
1048
1049 static bool
1050 loop_affine_expr (basic_block scop_entry, struct loop *loop, tree expr)
1051 {
1052   int n = loop->num;
1053   tree scev = analyze_scalar_evolution (loop, expr);
1054
1055   scev = instantiate_scev (scop_entry, loop, scev);
1056
1057   return (evolution_function_is_invariant_p (scev, n)
1058           || evolution_function_is_affine_multivariate_p (scev, n));
1059 }
1060
1061 /* Return false if the tree_code of the operand OP or any of its operands
1062    is component_ref.  */
1063
1064 static bool
1065 exclude_component_ref (tree op)
1066 {
1067   int i;
1068   int len;
1069
1070   if (op)
1071     {
1072       if (TREE_CODE (op) == COMPONENT_REF)
1073         return false;
1074       else
1075         {
1076           len = TREE_OPERAND_LENGTH (op);
1077           for (i = 0; i < len; ++i)
1078             {
1079               if (!exclude_component_ref (TREE_OPERAND (op, i)))
1080                 return false;
1081             }
1082         }
1083     }
1084
1085   return true;
1086 }
1087
1088 /* Return true if the operand OP is simple.  */
1089
1090 static bool
1091 is_simple_operand (loop_p loop, gimple stmt, tree op)
1092 {
1093   /* It is not a simple operand when it is a declaration,  */
1094   if (DECL_P (op)
1095       /* or a structure,  */
1096       || AGGREGATE_TYPE_P (TREE_TYPE (op))
1097       /* or a memory access that cannot be analyzed by the data
1098          reference analysis.  */
1099       || ((handled_component_p (op) || INDIRECT_REF_P (op))
1100           && !stmt_simple_memref_p (loop, stmt, op)))
1101     return false;
1102
1103   return exclude_component_ref (op);
1104 }
1105
1106 /* Return true only when STMT is simple enough for being handled by
1107    Graphite.  This depends on SCOP_ENTRY, as the parametetrs are
1108    initialized relatively to this basic block.  */
1109
1110 static bool
1111 stmt_simple_for_scop_p (basic_block scop_entry, gimple stmt)
1112 {
1113   basic_block bb = gimple_bb (stmt);
1114   struct loop *loop = bb->loop_father;
1115
1116   /* GIMPLE_ASM and GIMPLE_CALL may embed arbitrary side effects.
1117      Calls have side-effects, except those to const or pure
1118      functions.  */
1119   if (gimple_has_volatile_ops (stmt)
1120       || (gimple_code (stmt) == GIMPLE_CALL
1121           && !(gimple_call_flags (stmt) & (ECF_CONST | ECF_PURE)))
1122       || (gimple_code (stmt) == GIMPLE_ASM))
1123     return false;
1124
1125   switch (gimple_code (stmt))
1126     {
1127     case GIMPLE_RETURN:
1128     case GIMPLE_LABEL:
1129       return true;
1130
1131     case GIMPLE_COND:
1132       {
1133         tree op;
1134         ssa_op_iter op_iter;
1135         enum tree_code code = gimple_cond_code (stmt);
1136
1137         /* We can only handle this kind of conditional expressions.
1138            For inequalities like "if (i != 3 * k)" we need unions of
1139            polyhedrons.  Expressions like  "if (a)" or "if (a == 15)" need
1140            them for the else branch.  */
1141         if (!(code == LT_EXPR
1142               || code == GT_EXPR
1143               || code == LE_EXPR
1144               || code == GE_EXPR))
1145           return false;
1146
1147         if (!scop_entry)
1148           return false;
1149
1150         FOR_EACH_SSA_TREE_OPERAND (op, stmt, op_iter, SSA_OP_ALL_USES)
1151           if (!loop_affine_expr (scop_entry, loop, op))
1152             return false;
1153
1154         return true;
1155       }
1156
1157     case GIMPLE_ASSIGN:
1158       {
1159         enum tree_code code = gimple_assign_rhs_code (stmt);
1160
1161         switch (get_gimple_rhs_class (code))
1162           {
1163           case GIMPLE_UNARY_RHS:
1164           case GIMPLE_SINGLE_RHS:
1165             return (is_simple_operand (loop, stmt, gimple_assign_lhs (stmt))
1166                     && is_simple_operand (loop, stmt, gimple_assign_rhs1 (stmt)));
1167
1168           case GIMPLE_BINARY_RHS:
1169             return (is_simple_operand (loop, stmt, gimple_assign_lhs (stmt))
1170                     && is_simple_operand (loop, stmt, gimple_assign_rhs1 (stmt))
1171                     && is_simple_operand (loop, stmt, gimple_assign_rhs2 (stmt)));
1172
1173           case GIMPLE_INVALID_RHS:
1174           default:
1175             gcc_unreachable ();
1176           }
1177       }
1178
1179     case GIMPLE_CALL:
1180       {
1181         size_t i;
1182         size_t n = gimple_call_num_args (stmt);
1183         tree lhs = gimple_call_lhs (stmt);
1184
1185         if (lhs && !is_simple_operand (loop, stmt, lhs))
1186           return false;
1187
1188         for (i = 0; i < n; i++)
1189           if (!is_simple_operand (loop, stmt, gimple_call_arg (stmt, i)))
1190             return false;
1191
1192         return true;
1193       }
1194
1195     default:
1196       /* These nodes cut a new scope.  */
1197       return false;
1198     }
1199
1200   return false;
1201 }
1202
1203 /* Returns the statement of BB that contains a harmful operation: that
1204    can be a function call with side effects, the induction variables
1205    are not linear with respect to SCOP_ENTRY, etc.  The current open
1206    scop should end before this statement.  */
1207
1208 static gimple
1209 harmful_stmt_in_bb (basic_block scop_entry, basic_block bb)
1210 {
1211   gimple_stmt_iterator gsi;
1212   gimple stmt;
1213
1214   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1215     if (!stmt_simple_for_scop_p (scop_entry, gsi_stmt (gsi)))
1216       return gsi_stmt (gsi);
1217
1218   stmt = last_stmt (bb);
1219   if (stmt && gimple_code (stmt) == GIMPLE_COND)
1220     {
1221       tree lhs = gimple_cond_lhs (stmt);
1222       tree rhs = gimple_cond_rhs (stmt);
1223
1224       if (TREE_CODE (TREE_TYPE (lhs)) == REAL_TYPE
1225           || TREE_CODE (TREE_TYPE (rhs)) == REAL_TYPE)
1226         return stmt;
1227     }
1228
1229   return NULL;
1230 }
1231
1232 /* Returns true when BB will be represented in graphite.  Return false
1233    for the basic blocks that contain code eliminated in the code
1234    generation pass: i.e. induction variables and exit conditions.  */
1235
1236 static bool
1237 graphite_stmt_p (scop_p scop, basic_block bb,
1238                  VEC (data_reference_p, heap) *drs)
1239 {
1240   gimple_stmt_iterator gsi;
1241   loop_p loop = bb->loop_father;
1242
1243   if (VEC_length (data_reference_p, drs) > 0)
1244     return true;
1245
1246   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1247     {
1248       gimple stmt = gsi_stmt (gsi);
1249
1250       switch (gimple_code (stmt))
1251         {
1252           /* Control flow expressions can be ignored, as they are
1253              represented in the iteration domains and will be
1254              regenerated by graphite.  */
1255         case GIMPLE_COND:
1256         case GIMPLE_GOTO:
1257         case GIMPLE_SWITCH:
1258           break;
1259
1260         case GIMPLE_ASSIGN:
1261           {
1262             tree var = gimple_assign_lhs (stmt);
1263             var = analyze_scalar_evolution (loop, var);
1264             var = instantiate_scev (block_before_scop (scop), loop, var);
1265
1266             if (chrec_contains_undetermined (var))
1267               return true;
1268
1269             break;
1270           }
1271
1272         default:
1273           return true;
1274         }
1275     }
1276
1277   return false;
1278 }
1279
1280 /* Store the GRAPHITE representation of BB.  */
1281
1282 static void
1283 new_graphite_bb (scop_p scop, basic_block bb)
1284 {
1285   struct graphite_bb *gbb;
1286   VEC (data_reference_p, heap) *drs = VEC_alloc (data_reference_p, heap, 5);
1287   struct loop *nest = outermost_loop_in_scop (scop, bb);
1288   gimple_stmt_iterator gsi;
1289
1290   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1291     find_data_references_in_stmt (nest, gsi_stmt (gsi), &drs);
1292
1293   if (!graphite_stmt_p (scop, bb, drs))
1294     {
1295       free_data_refs (drs);
1296       return;
1297     }
1298
1299   gbb = XNEW (struct graphite_bb);
1300   bb->aux = gbb;
1301   GBB_BB (gbb) = bb;
1302   GBB_SCOP (gbb) = scop;
1303   GBB_DATA_REFS (gbb) = drs;
1304   GBB_DOMAIN (gbb) = NULL;
1305   GBB_CONDITIONS (gbb) = NULL;
1306   GBB_CONDITION_CASES (gbb) = NULL;
1307   GBB_LOOPS (gbb) = NULL;
1308   GBB_STATIC_SCHEDULE (gbb) = NULL;
1309   GBB_CLOOG_IV_TYPES (gbb) = NULL;
1310   VEC_safe_push (graphite_bb_p, heap, SCOP_BBS (scop), gbb);
1311 }
1312
1313 /* Frees GBB.  */
1314
1315 static void
1316 free_graphite_bb (struct graphite_bb *gbb)
1317 {
1318   if (GBB_DOMAIN (gbb))
1319     cloog_matrix_free (GBB_DOMAIN (gbb));
1320
1321   if (GBB_CLOOG_IV_TYPES (gbb))
1322     htab_delete (GBB_CLOOG_IV_TYPES (gbb));
1323
1324   /* FIXME: free_data_refs is disabled for the moment, but should be
1325      enabled.
1326
1327      free_data_refs (GBB_DATA_REFS (gbb)); */
1328
1329   VEC_free (gimple, heap, GBB_CONDITIONS (gbb));
1330   VEC_free (gimple, heap, GBB_CONDITION_CASES (gbb));
1331   VEC_free (loop_p, heap, GBB_LOOPS (gbb));
1332   GBB_BB (gbb)->aux = 0;
1333   XDELETE (gbb);
1334 }
1335
1336 \f
1337
1338 /* Structure containing the mapping between the old names and the new
1339    names used after block copy in the new loop context.  */
1340 typedef struct rename_map_elt
1341 {
1342   tree old_name, new_name;
1343 } *rename_map_elt;
1344
1345
1346 /* Print to stderr the element ELT.  */
1347
1348 static void
1349 debug_rename_elt (rename_map_elt elt)
1350 {
1351   fprintf (stderr, "(");
1352   print_generic_expr (stderr, elt->old_name, 0);
1353   fprintf (stderr, ", ");
1354   print_generic_expr (stderr, elt->new_name, 0);
1355   fprintf (stderr, ")\n");
1356 }
1357
1358 /* Helper function for debug_rename_map.  */
1359
1360 static int
1361 debug_rename_map_1 (void **slot, void *s ATTRIBUTE_UNUSED)
1362 {
1363   struct rename_map_elt *entry = (struct rename_map_elt *) *slot;
1364   debug_rename_elt (entry);
1365   return 1;
1366 }
1367
1368 /* Print to stderr all the elements of MAP.  */
1369
1370 void
1371 debug_rename_map (htab_t map)
1372 {
1373   htab_traverse (map, debug_rename_map_1, NULL);
1374 }
1375
1376 /* Constructs a new SCEV_INFO_STR structure for VAR and INSTANTIATED_BELOW.  */
1377
1378 static inline rename_map_elt
1379 new_rename_map_elt (tree old_name, tree new_name)
1380 {
1381   rename_map_elt res;
1382
1383   res = XNEW (struct rename_map_elt);
1384   res->old_name = old_name;
1385   res->new_name = new_name;
1386
1387   return res;
1388 }
1389
1390 /* Computes a hash function for database element ELT.  */
1391
1392 static hashval_t
1393 rename_map_elt_info (const void *elt)
1394 {
1395   return htab_hash_pointer (((const struct rename_map_elt *) elt)->old_name);
1396 }
1397
1398 /* Compares database elements E1 and E2.  */
1399
1400 static int
1401 eq_rename_map_elts (const void *e1, const void *e2)
1402 {
1403   const struct rename_map_elt *elt1 = (const struct rename_map_elt *) e1;
1404   const struct rename_map_elt *elt2 = (const struct rename_map_elt *) e2;
1405
1406   return (elt1->old_name == elt2->old_name);
1407 }
1408
1409 /* Returns the new name associated to OLD_NAME in MAP.  */
1410
1411 static tree
1412 get_new_name_from_old_name (htab_t map, tree old_name)
1413 {
1414   struct rename_map_elt tmp;
1415   PTR *slot;
1416
1417   tmp.old_name = old_name;
1418   slot = htab_find_slot (map, &tmp, NO_INSERT);
1419
1420   if (slot && *slot)
1421     return ((rename_map_elt) *slot)->new_name;
1422
1423   return old_name;
1424 }
1425
1426 \f
1427
1428 /* Creates a new scop starting with ENTRY.  */
1429
1430 static scop_p
1431 new_scop (edge entry, edge exit)
1432 {
1433   scop_p scop = XNEW (struct scop);
1434
1435   gcc_assert (entry && exit);
1436
1437   SCOP_REGION (scop) = new_sese (entry, exit);
1438   SCOP_BBS (scop) = VEC_alloc (graphite_bb_p, heap, 3);
1439   SCOP_OLDIVS (scop) = VEC_alloc (name_tree, heap, 3);
1440   SCOP_LOOPS (scop) = BITMAP_ALLOC (NULL);
1441   SCOP_LOOP_NEST (scop) = VEC_alloc (loop_p, heap, 3);
1442   SCOP_ADD_PARAMS (scop) = true;
1443   SCOP_PARAMS (scop) = VEC_alloc (name_tree, heap, 3);
1444   SCOP_PROG (scop) = cloog_program_malloc ();
1445   cloog_program_set_names (SCOP_PROG (scop), cloog_names_malloc ());
1446   SCOP_LOOP2CLOOG_LOOP (scop) = htab_create (10, hash_loop_to_cloog_loop,
1447                                              eq_loop_to_cloog_loop,
1448                                              free);
1449   SCOP_LIVEOUT_RENAMES (scop) = htab_create (10, rename_map_elt_info,
1450                                              eq_rename_map_elts, free);
1451   return scop;
1452 }
1453
1454 /* Deletes SCOP.  */
1455
1456 static void
1457 free_scop (scop_p scop)
1458 {
1459   int i;
1460   name_tree p;
1461   struct graphite_bb *gb;
1462   name_tree iv;
1463
1464   for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
1465     free_graphite_bb (gb);
1466
1467   VEC_free (graphite_bb_p, heap, SCOP_BBS (scop));
1468   BITMAP_FREE (SCOP_LOOPS (scop));
1469   VEC_free (loop_p, heap, SCOP_LOOP_NEST (scop));
1470
1471   for (i = 0; VEC_iterate (name_tree, SCOP_OLDIVS (scop), i, iv); i++)
1472     free (iv);
1473   VEC_free (name_tree, heap, SCOP_OLDIVS (scop));
1474
1475   for (i = 0; VEC_iterate (name_tree, SCOP_PARAMS (scop), i, p); i++)
1476     free (p);
1477
1478   VEC_free (name_tree, heap, SCOP_PARAMS (scop));
1479   cloog_program_free (SCOP_PROG (scop));
1480   htab_delete (SCOP_LOOP2CLOOG_LOOP (scop));
1481   htab_delete (SCOP_LIVEOUT_RENAMES (scop));
1482   free_sese (SCOP_REGION (scop));
1483   XDELETE (scop);
1484 }
1485
1486 /* Deletes all scops in SCOPS.  */
1487
1488 static void
1489 free_scops (VEC (scop_p, heap) *scops)
1490 {
1491   int i;
1492   scop_p scop;
1493
1494   for (i = 0; VEC_iterate (scop_p, scops, i, scop); i++)
1495     free_scop (scop);
1496
1497   VEC_free (scop_p, heap, scops);
1498 }
1499
1500 typedef enum gbb_type {
1501   GBB_UNKNOWN,
1502   GBB_LOOP_SING_EXIT_HEADER,
1503   GBB_LOOP_MULT_EXIT_HEADER,
1504   GBB_LOOP_EXIT,
1505   GBB_COND_HEADER,
1506   GBB_SIMPLE,
1507   GBB_LAST
1508 } gbb_type;
1509
1510 /* Detect the type of BB.  Loop headers are only marked, if they are
1511    new.  This means their loop_father is different to LAST_LOOP.
1512    Otherwise they are treated like any other bb and their type can be
1513    any other type.  */
1514
1515 static gbb_type
1516 get_bb_type (basic_block bb, struct loop *last_loop)
1517 {
1518   VEC (basic_block, heap) *dom;
1519   int nb_dom, nb_suc;
1520   struct loop *loop = bb->loop_father;
1521
1522   /* Check, if we entry into a new loop. */
1523   if (loop != last_loop)
1524     {
1525       if (single_exit (loop) != NULL)
1526         return GBB_LOOP_SING_EXIT_HEADER;
1527       else if (loop->num != 0)
1528         return GBB_LOOP_MULT_EXIT_HEADER;
1529       else
1530         return GBB_COND_HEADER;
1531     }
1532
1533   dom = get_dominated_by (CDI_DOMINATORS, bb);
1534   nb_dom = VEC_length (basic_block, dom);
1535   VEC_free (basic_block, heap, dom);
1536
1537   if (nb_dom == 0)
1538     return GBB_LAST;
1539
1540   nb_suc = VEC_length (edge, bb->succs);
1541
1542   if (nb_dom == 1 && nb_suc == 1)
1543     return GBB_SIMPLE;
1544
1545   return GBB_COND_HEADER;
1546 }
1547
1548 /* A SCoP detection region, defined using bbs as borders.
1549    All control flow touching this region, comes in passing basic_block ENTRY and
1550    leaves passing basic_block EXIT.  By using bbs instead of edges for the
1551    borders we are able to represent also regions that do not have a single
1552    entry or exit edge.
1553    But as they have a single entry basic_block and a single exit basic_block, we
1554    are able to generate for every sd_region a single entry and exit edge.
1555
1556    1   2
1557     \ /
1558      3  <- entry
1559      |
1560      4
1561     / \                 This region contains: {3, 4, 5, 6, 7, 8}
1562    5   6
1563    |   |
1564    7   8
1565     \ /
1566      9  <- exit  */
1567
1568
1569 typedef struct sd_region_p
1570 {
1571   /* The entry bb dominates all bbs in the sd_region.  It is part of the
1572      region.  */
1573   basic_block entry;
1574
1575   /* The exit bb postdominates all bbs in the sd_region, but is not
1576      part of the region.  */
1577   basic_block exit;
1578 } sd_region;
1579
1580 DEF_VEC_O(sd_region);
1581 DEF_VEC_ALLOC_O(sd_region, heap);
1582
1583
1584 /* Moves the scops from SOURCE to TARGET and clean up SOURCE.  */
1585
1586 static void
1587 move_sd_regions (VEC (sd_region, heap) **source, VEC (sd_region, heap) **target)
1588 {
1589   sd_region *s;
1590   int i;
1591
1592   for (i = 0; VEC_iterate (sd_region, *source, i, s); i++)
1593     VEC_safe_push (sd_region, heap, *target, s);
1594
1595   VEC_free (sd_region, heap, *source);
1596 }
1597
1598 /* Return true when it is not possible to represent the upper bound of
1599    LOOP in the polyhedral representation.  */
1600
1601 static bool
1602 graphite_cannot_represent_loop_niter (loop_p loop)
1603 {
1604   tree niter = number_of_latch_executions (loop);
1605
1606   return chrec_contains_undetermined (niter)
1607     || !scev_is_linear_expression (niter);
1608 }
1609 /* Store information needed by scopdet_* functions.  */
1610
1611 struct scopdet_info
1612 {
1613   /* Where the last open scop would stop if the current BB is harmful.  */
1614   basic_block last;
1615
1616   /* Where the next scop would start if the current BB is harmful.  */
1617   basic_block next;
1618
1619   /* The bb or one of its children contains open loop exits.  That means
1620      loop exit nodes that are not surrounded by a loop dominated by bb.  */
1621   bool exits;
1622
1623   /* The bb or one of its children contains only structures we can handle.  */
1624   bool difficult;
1625 };
1626
1627
1628 static struct scopdet_info build_scops_1 (basic_block, VEC (sd_region, heap) **,
1629                                           loop_p);
1630
1631 /* Calculates BB infos. If bb is difficult we add valid SCoPs dominated by BB
1632    to SCOPS.  TYPE is the gbb_type of BB.  */
1633
1634 static struct scopdet_info
1635 scopdet_basic_block_info (basic_block bb, VEC (sd_region, heap) **scops,
1636                           gbb_type type)
1637 {
1638   struct loop *loop = bb->loop_father;
1639   struct scopdet_info result;
1640   gimple stmt;
1641
1642   /* XXX: ENTRY_BLOCK_PTR could be optimized in later steps.  */
1643   stmt = harmful_stmt_in_bb (ENTRY_BLOCK_PTR, bb);
1644   result.difficult = (stmt != NULL);
1645   result.last = NULL;
1646
1647   switch (type)
1648     {
1649     case GBB_LAST:
1650       result.next = NULL;
1651       result.exits = false;
1652       result.last = bb;
1653
1654       /* Mark bbs terminating a SESE region difficult, if they start
1655          a condition.  */
1656       if (VEC_length (edge, bb->succs) > 1)
1657         result.difficult = true;
1658
1659       break;
1660
1661     case GBB_SIMPLE:
1662       result.next = single_succ (bb);
1663       result.exits = false;
1664       result.last = bb;
1665       break;
1666
1667     case GBB_LOOP_SING_EXIT_HEADER:
1668       {
1669         VEC (sd_region, heap) *tmp_scops = VEC_alloc (sd_region, heap,3);
1670         struct scopdet_info sinfo;
1671
1672         sinfo = build_scops_1 (bb, &tmp_scops, loop);
1673
1674         result.last = single_exit (bb->loop_father)->src;
1675         result.next = single_exit (bb->loop_father)->dest;
1676
1677         /* If we do not dominate result.next, remove it.  It's either
1678            the EXIT_BLOCK_PTR, or another bb dominates it and will
1679            call the scop detection for this bb.  */
1680         if (!dominated_by_p (CDI_DOMINATORS, result.next, bb))
1681           result.next = NULL;
1682
1683         if (result.last->loop_father != loop)
1684           result.next = NULL;
1685
1686         if (graphite_cannot_represent_loop_niter (loop))
1687           result.difficult = true;
1688
1689         if (sinfo.difficult)
1690           move_sd_regions (&tmp_scops, scops);
1691         else
1692           VEC_free (sd_region, heap, tmp_scops);
1693
1694         result.exits = false;
1695         result.difficult |= sinfo.difficult;
1696         break;
1697       }
1698
1699     case GBB_LOOP_MULT_EXIT_HEADER:
1700       {
1701         /* XXX: For now we just do not join loops with multiple exits.  If the
1702            exits lead to the same bb it may be possible to join the loop.  */
1703         VEC (sd_region, heap) *tmp_scops = VEC_alloc (sd_region, heap, 3);
1704         VEC (edge, heap) *exits = get_loop_exit_edges (loop);
1705         edge e;
1706         int i;
1707         build_scops_1 (bb, &tmp_scops, loop);
1708
1709         /* Scan the code dominated by this loop.  This means all bbs, that are
1710            are dominated by a bb in this loop, but are not part of this loop.
1711
1712            The easiest case:
1713              - The loop exit destination is dominated by the exit sources.
1714
1715            TODO: We miss here the more complex cases:
1716                   - The exit destinations are dominated by another bb inside the
1717                     loop.
1718                   - The loop dominates bbs, that are not exit destinations.  */
1719         for (i = 0; VEC_iterate (edge, exits, i, e); i++)
1720           if (e->src->loop_father == loop
1721               && dominated_by_p (CDI_DOMINATORS, e->dest, e->src))
1722             {
1723               /* Pass loop_outer to recognize e->dest as loop header in
1724                  build_scops_1.  */
1725               if (e->dest->loop_father->header == e->dest)
1726                 build_scops_1 (e->dest, &tmp_scops,
1727                                loop_outer (e->dest->loop_father));
1728               else
1729                 build_scops_1 (e->dest, &tmp_scops, e->dest->loop_father);
1730             }
1731
1732         result.next = NULL;
1733         result.last = NULL;
1734         result.difficult = true;
1735         result.exits = false;
1736         move_sd_regions (&tmp_scops, scops);
1737         VEC_free (edge, heap, exits);
1738         break;
1739       }
1740     case GBB_COND_HEADER:
1741       {
1742         VEC (sd_region, heap) *tmp_scops = VEC_alloc (sd_region, heap, 3);
1743         struct scopdet_info sinfo;
1744         VEC (basic_block, heap) *dominated;
1745         int i;
1746         basic_block dom_bb;
1747         basic_block last_bb = NULL;
1748         edge e;
1749         result.exits = false;
1750
1751         /* First check the successors of BB, and check if it is possible to join
1752            the different branches.  */
1753         for (i = 0; VEC_iterate (edge, bb->succs, i, e); i++)
1754           {
1755             /* Ignore loop exits.  They will be handled after the loop body.  */
1756             if (is_loop_exit (loop, e->dest))
1757               {
1758                 result.exits = true;
1759                 continue;
1760               }
1761
1762             /* Do not follow edges that lead to the end of the
1763                conditions block.  For example, in
1764
1765                |   0
1766                |  /|\
1767                | 1 2 |
1768                | | | |
1769                | 3 4 |
1770                |  \|/
1771                |   6
1772
1773                the edge from 0 => 6.  Only check if all paths lead to
1774                the same node 6.  */
1775
1776             if (!single_pred_p (e->dest))
1777               {
1778                 /* Check, if edge leads directly to the end of this
1779                    condition.  */
1780                 if (!last_bb)
1781                   {
1782                     last_bb = e->dest;
1783                   }
1784
1785                 if (e->dest != last_bb)
1786                   result.difficult = true;
1787
1788                 continue;
1789               }
1790
1791             if (!dominated_by_p (CDI_DOMINATORS, e->dest, bb))
1792               {
1793                 result.difficult = true;
1794                 continue;
1795               }
1796
1797             sinfo = build_scops_1 (e->dest, &tmp_scops, loop);
1798
1799             result.exits |= sinfo.exits;
1800             result.last = sinfo.last;
1801             result.difficult |= sinfo.difficult;
1802
1803             /* Checks, if all branches end at the same point.
1804                If that is true, the condition stays joinable.
1805                Have a look at the example above.  */
1806             if (sinfo.last && single_succ_p (sinfo.last))
1807               {
1808                 basic_block next_tmp = single_succ (sinfo.last);
1809
1810                 if (!last_bb)
1811                     last_bb = next_tmp;
1812
1813                 if (next_tmp != last_bb)
1814                   result.difficult = true;
1815               }
1816             else
1817               result.difficult = true;
1818           }
1819
1820         /* If the condition is joinable.  */
1821         if (!result.exits && !result.difficult)
1822           {
1823             /* Only return a next pointer if we dominate this pointer.
1824                Otherwise it will be handled by the bb dominating it.  */
1825             if (dominated_by_p (CDI_DOMINATORS, last_bb, bb) && last_bb != bb)
1826               result.next = last_bb;
1827             else
1828               result.next = NULL;
1829
1830             VEC_free (sd_region, heap, tmp_scops);
1831             break;
1832           }
1833
1834         /* Scan remaining bbs dominated by BB.  */
1835         dominated = get_dominated_by (CDI_DOMINATORS, bb);
1836
1837         for (i = 0; VEC_iterate (basic_block, dominated, i, dom_bb); i++)
1838           {
1839             /* Ignore loop exits: they will be handled after the loop body.  */
1840             if (loop_depth (find_common_loop (loop, dom_bb->loop_father))
1841                 < loop_depth (loop))
1842               {
1843                 result.exits = true;
1844                 continue;
1845               }
1846
1847             /* Ignore the bbs processed above.  */
1848             if (single_pred_p (dom_bb) && single_pred (dom_bb) == bb)
1849               continue;
1850
1851             if (loop_depth (loop) > loop_depth (dom_bb->loop_father))
1852               sinfo = build_scops_1 (dom_bb, &tmp_scops, loop_outer (loop));
1853             else
1854               sinfo = build_scops_1 (dom_bb, &tmp_scops, loop);
1855
1856
1857             result.exits |= sinfo.exits;
1858             result.difficult = true;
1859             result.last = NULL;
1860           }
1861
1862         VEC_free (basic_block, heap, dominated);
1863
1864         result.next = NULL;
1865         move_sd_regions (&tmp_scops, scops);
1866
1867         break;
1868       }
1869
1870     default:
1871       gcc_unreachable ();
1872     }
1873
1874   return result;
1875 }
1876
1877 /* Creates the SCoPs and writes entry and exit points for every SCoP.  */
1878
1879 static struct scopdet_info
1880 build_scops_1 (basic_block current, VEC (sd_region, heap) **scops, loop_p loop)
1881 {
1882   bool in_scop = false;
1883   sd_region open_scop;
1884   struct scopdet_info sinfo;
1885
1886   /* Initialize result.  */
1887   struct scopdet_info result;
1888   result.exits = false;
1889   result.difficult = false;
1890   result.next = NULL;
1891   result.last = NULL;
1892   open_scop.entry = NULL;
1893   open_scop.exit = NULL;
1894   sinfo.last = NULL;
1895
1896   /* Loop over the dominance tree.  If we meet a difficult bb, close
1897      the current SCoP.  Loop and condition header start a new layer,
1898      and can only be added if all bbs in deeper layers are simple.  */
1899   while (current != NULL)
1900     {
1901       sinfo = scopdet_basic_block_info (current, scops, get_bb_type (current,
1902                                                                      loop));
1903
1904       if (!in_scop && !(sinfo.exits || sinfo.difficult))
1905         {
1906           open_scop.entry = current;
1907           open_scop.exit = NULL;
1908           in_scop = true;
1909         }
1910       else if (in_scop && (sinfo.exits || sinfo.difficult))
1911         {
1912           open_scop.exit = current;
1913           VEC_safe_push (sd_region, heap, *scops, &open_scop);
1914           in_scop = false;
1915         }
1916
1917       result.difficult |= sinfo.difficult;
1918       result.exits |= sinfo.exits;
1919
1920       current = sinfo.next;
1921     }
1922
1923   /* Try to close open_scop, if we are still in an open SCoP.  */
1924   if (in_scop)
1925     {
1926       int i;
1927       edge e;
1928
1929         for (i = 0; VEC_iterate (edge, sinfo.last->succs, i, e); i++)
1930           if (dominated_by_p (CDI_POST_DOMINATORS, sinfo.last, e->dest))
1931             open_scop.exit = e->dest;
1932
1933         if (!open_scop.exit && open_scop.entry != sinfo.last)
1934           open_scop.exit = sinfo.last;
1935
1936         if (open_scop.exit)
1937           VEC_safe_push (sd_region, heap, *scops, &open_scop);
1938
1939     }
1940
1941   result.last = sinfo.last;
1942   return result;
1943 }
1944
1945 /* Checks if a bb is contained in REGION.  */
1946
1947 static bool
1948 bb_in_sd_region (basic_block bb, sd_region *region)
1949 {
1950   return dominated_by_p (CDI_DOMINATORS, bb, region->entry)
1951          && !(dominated_by_p (CDI_DOMINATORS, bb, region->exit)
1952               && !dominated_by_p (CDI_DOMINATORS, region->entry,
1953                                   region->exit));
1954 }
1955
1956 /* Returns the single entry edge of REGION, if it does not exits NULL.  */
1957
1958 static edge
1959 find_single_entry_edge (sd_region *region)
1960 {
1961   edge e;
1962   edge_iterator ei;
1963   edge entry = NULL;
1964
1965   FOR_EACH_EDGE (e, ei, region->entry->preds)
1966     if (!bb_in_sd_region (e->src, region))
1967       {
1968         if (entry)
1969           {
1970             entry = NULL;
1971             break;
1972           }
1973
1974         else
1975           entry = e;
1976       }
1977
1978   return entry;
1979 }
1980
1981 /* Returns the single exit edge of REGION, if it does not exits NULL.  */
1982
1983 static edge
1984 find_single_exit_edge (sd_region *region)
1985 {
1986   edge e;
1987   edge_iterator ei;
1988   edge exit = NULL;
1989
1990   FOR_EACH_EDGE (e, ei, region->exit->preds)
1991     if (bb_in_sd_region (e->src, region))
1992       {
1993         if (exit)
1994           {
1995             exit = NULL;
1996             break;
1997           }
1998
1999         else
2000           exit = e;
2001       }
2002
2003   return exit;
2004 }
2005
2006 /* Create a single entry edge for REGION.  */
2007
2008 static void
2009 create_single_entry_edge (sd_region *region)
2010 {
2011   if (find_single_entry_edge (region))
2012     return;
2013
2014   /* There are multiple predecessors for bb_3
2015
2016   |  1  2
2017   |  | /
2018   |  |/
2019   |  3  <- entry
2020   |  |\
2021   |  | |
2022   |  4 ^
2023   |  | |
2024   |  |/
2025   |  5
2026
2027   There are two edges (1->3, 2->3), that point from outside into the region,
2028   and another one (5->3), a loop latch, lead to bb_3.
2029
2030   We split bb_3.
2031
2032   |  1  2
2033   |  | /
2034   |  |/
2035   |3.0
2036   |  |\     (3.0 -> 3.1) = single entry edge
2037   |3.1 |        <- entry
2038   |  | |
2039   |  | |
2040   |  4 ^
2041   |  | |
2042   |  |/
2043   |  5
2044
2045   If the loop is part of the SCoP, we have to redirect the loop latches.
2046
2047   |  1  2
2048   |  | /
2049   |  |/
2050   |3.0
2051   |  |      (3.0 -> 3.1) = entry edge
2052   |3.1          <- entry
2053   |  |\
2054   |  | |
2055   |  4 ^
2056   |  | |
2057   |  |/
2058   |  5  */
2059
2060   if (region->entry->loop_father->header != region->entry
2061       || dominated_by_p (CDI_DOMINATORS,
2062                          loop_latch_edge (region->entry->loop_father)->src,
2063                          region->exit))
2064     {
2065       edge forwarder = split_block_after_labels (region->entry);
2066       region->entry = forwarder->dest;
2067     }
2068   else
2069     /* This case is never executed, as the loop headers seem always to have a
2070        single edge pointing from outside into the loop.  */
2071     gcc_unreachable ();
2072
2073 #ifdef ENABLE_CHECKING
2074   gcc_assert (find_single_entry_edge (region));
2075 #endif
2076 }
2077
2078 /* Check if the sd_region, mentioned in EDGE, has no exit bb.  */
2079
2080 static bool
2081 sd_region_without_exit (edge e)
2082 {
2083   sd_region *r = (sd_region *) e->aux;
2084
2085   if (r)
2086     return r->exit == NULL;
2087   else
2088     return false;
2089 }
2090
2091 /* Create a single exit edge for REGION.  */
2092
2093 static void
2094 create_single_exit_edge (sd_region *region)
2095 {
2096   edge e;
2097   edge_iterator ei;
2098   edge forwarder = NULL;
2099   basic_block exit;
2100
2101   if (find_single_exit_edge (region))
2102     return;
2103
2104   /* We create a forwarder bb (5) for all edges leaving this region
2105      (3->5, 4->5).  All other edges leading to the same bb, are moved
2106      to a new bb (6).  If these edges where part of another region (2->5)
2107      we update the region->exit pointer, of this region.
2108
2109      To identify which edge belongs to which region we depend on the e->aux
2110      pointer in every edge.  It points to the region of the edge or to NULL,
2111      if the edge is not part of any region.
2112
2113      1 2 3 4    1->5 no region,                 2->5 region->exit = 5,
2114       \| |/     3->5 region->exit = NULL,       4->5 region->exit = NULL
2115         5       <- exit
2116
2117      changes to
2118
2119      1 2 3 4    1->6 no region,                         2->6 region->exit = 6,
2120      | | \/     3->5 no region,                         4->5 no region,
2121      | |  5
2122       \| /      5->6 region->exit = 6
2123         6
2124
2125      Now there is only a single exit edge (5->6).  */
2126   exit = region->exit;
2127   region->exit = NULL;
2128   forwarder = make_forwarder_block (exit, &sd_region_without_exit, NULL);
2129
2130   /* Unmark the edges, that are no longer exit edges.  */
2131   FOR_EACH_EDGE (e, ei, forwarder->src->preds)
2132     if (e->aux)
2133       e->aux = NULL;
2134
2135   /* Mark the new exit edge.  */
2136   single_succ_edge (forwarder->src)->aux = region;
2137
2138   /* Update the exit bb of all regions, where exit edges lead to
2139      forwarder->dest.  */
2140   FOR_EACH_EDGE (e, ei, forwarder->dest->preds)
2141     if (e->aux)
2142       ((sd_region *) e->aux)->exit = forwarder->dest;
2143
2144 #ifdef ENABLE_CHECKING
2145   gcc_assert (find_single_exit_edge (region));
2146 #endif
2147 }
2148
2149 /* Unmark the exit edges of all REGIONS.
2150    See comment in "create_single_exit_edge". */
2151
2152 static void
2153 unmark_exit_edges (VEC (sd_region, heap) *regions)
2154 {
2155   int i;
2156   sd_region *s;
2157   edge e;
2158   edge_iterator ei;
2159
2160   for (i = 0; VEC_iterate (sd_region, regions, i, s); i++)
2161     FOR_EACH_EDGE (e, ei, s->exit->preds)
2162       e->aux = NULL;
2163 }
2164
2165
2166 /* Mark the exit edges of all REGIONS.
2167    See comment in "create_single_exit_edge". */
2168
2169 static void
2170 mark_exit_edges (VEC (sd_region, heap) *regions)
2171 {
2172   int i;
2173   sd_region *s;
2174   edge e;
2175   edge_iterator ei;
2176
2177   for (i = 0; VEC_iterate (sd_region, regions, i, s); i++)
2178     FOR_EACH_EDGE (e, ei, s->exit->preds)
2179       if (bb_in_sd_region (e->src, s))
2180         e->aux = s;
2181 }
2182
2183 /* Free and compute again all the dominators information.  */
2184
2185 static inline void
2186 recompute_all_dominators (void)
2187 {
2188   mark_irreducible_loops ();
2189   free_dominance_info (CDI_DOMINATORS);
2190   free_dominance_info (CDI_POST_DOMINATORS);
2191   calculate_dominance_info (CDI_DOMINATORS);
2192   calculate_dominance_info (CDI_POST_DOMINATORS);
2193 }
2194
2195 /* Verifies properties that GRAPHITE should maintain during translation.  */
2196
2197 static inline void
2198 graphite_verify (void)
2199 {
2200 #ifdef ENABLE_CHECKING
2201   verify_loop_structure ();
2202   verify_dominators (CDI_DOMINATORS);
2203   verify_dominators (CDI_POST_DOMINATORS);
2204   verify_ssa (false);
2205   verify_loop_closed_ssa ();
2206 #endif
2207 }
2208
2209 /* Create for all scop regions a single entry and a single exit edge.  */
2210
2211 static void
2212 create_sese_edges (VEC (sd_region, heap) *regions)
2213 {
2214   int i;
2215   sd_region *s;
2216
2217   for (i = 0; VEC_iterate (sd_region, regions, i, s); i++)
2218     create_single_entry_edge (s);
2219
2220   mark_exit_edges (regions);
2221
2222   for (i = 0; VEC_iterate (sd_region, regions, i, s); i++)
2223     create_single_exit_edge (s);
2224
2225   unmark_exit_edges (regions);
2226
2227   fix_loop_structure (NULL);
2228
2229 #ifdef ENABLE_CHECKING
2230   verify_loop_structure ();
2231   verify_dominators (CDI_DOMINATORS);
2232   verify_ssa (false);
2233 #endif
2234 }
2235
2236 /* Create graphite SCoPs from an array of scop detection regions.  */
2237
2238 static void
2239 build_graphite_scops (VEC (sd_region, heap) *scop_regions)
2240 {
2241   int i;
2242   sd_region *s;
2243
2244   for (i = 0; VEC_iterate (sd_region, scop_regions, i, s); i++)
2245     {
2246       edge entry = find_single_entry_edge (s);
2247       edge exit = find_single_exit_edge (s);
2248       scop_p scop = new_scop (entry, exit);
2249       VEC_safe_push (scop_p, heap, current_scops, scop);
2250
2251       /* Are there overlapping SCoPs?  */
2252 #ifdef ENABLE_CHECKING
2253         {
2254           int j;
2255           sd_region *s2;
2256
2257           for (j = 0; VEC_iterate (sd_region, scop_regions, j, s2); j++)
2258             if (s != s2)
2259               gcc_assert (!bb_in_sd_region (s->entry, s2));
2260         }
2261 #endif
2262     }
2263 }
2264
2265 /* Find static control parts.  */
2266
2267 static void
2268 build_scops (void)
2269 {
2270   struct loop *loop = current_loops->tree_root;
2271   VEC (sd_region, heap) *tmp_scops = VEC_alloc (sd_region, heap, 3);
2272
2273   build_scops_1 (single_succ (ENTRY_BLOCK_PTR), &tmp_scops, loop);
2274   create_sese_edges (tmp_scops);
2275   build_graphite_scops (tmp_scops);
2276   VEC_free (sd_region, heap, tmp_scops);
2277 }
2278
2279 /* Gather the basic blocks belonging to the SCOP.  */
2280
2281 static void
2282 build_scop_bbs (scop_p scop)
2283 {
2284   basic_block *stack = XNEWVEC (basic_block, n_basic_blocks + 1);
2285   sbitmap visited = sbitmap_alloc (last_basic_block);
2286   int sp = 0;
2287
2288   sbitmap_zero (visited);
2289   stack[sp++] = SCOP_ENTRY (scop);
2290
2291   while (sp)
2292     {
2293       basic_block bb = stack[--sp];
2294       int depth = loop_depth (bb->loop_father);
2295       int num = bb->loop_father->num;
2296       edge_iterator ei;
2297       edge e;
2298
2299       /* Scop's exit is not in the scop.  Exclude also bbs, which are
2300          dominated by the SCoP exit.  These are e.g. loop latches.  */
2301       if (TEST_BIT (visited, bb->index)
2302           || dominated_by_p (CDI_DOMINATORS, bb, SCOP_EXIT (scop))
2303           /* Every block in the scop is dominated by scop's entry.  */
2304           || !dominated_by_p (CDI_DOMINATORS, bb, SCOP_ENTRY (scop)))
2305         continue;
2306
2307       new_graphite_bb (scop, bb);
2308       SET_BIT (visited, bb->index);
2309
2310       /* First push the blocks that have to be processed last.  Note
2311          that this means that the order in which the code is organized
2312          below is important: do not reorder the following code.  */
2313       FOR_EACH_EDGE (e, ei, bb->succs)
2314         if (! TEST_BIT (visited, e->dest->index)
2315             && (int) loop_depth (e->dest->loop_father) < depth)
2316           stack[sp++] = e->dest;
2317
2318       FOR_EACH_EDGE (e, ei, bb->succs)
2319         if (! TEST_BIT (visited, e->dest->index)
2320             && (int) loop_depth (e->dest->loop_father) == depth
2321             && e->dest->loop_father->num != num)
2322           stack[sp++] = e->dest;
2323
2324       FOR_EACH_EDGE (e, ei, bb->succs)
2325         if (! TEST_BIT (visited, e->dest->index)
2326             && (int) loop_depth (e->dest->loop_father) == depth
2327             && e->dest->loop_father->num == num
2328             && EDGE_COUNT (e->dest->preds) > 1)
2329           stack[sp++] = e->dest;
2330
2331       FOR_EACH_EDGE (e, ei, bb->succs)
2332         if (! TEST_BIT (visited, e->dest->index)
2333             && (int) loop_depth (e->dest->loop_father) == depth
2334             && e->dest->loop_father->num == num
2335             && EDGE_COUNT (e->dest->preds) == 1)
2336           stack[sp++] = e->dest;
2337
2338       FOR_EACH_EDGE (e, ei, bb->succs)
2339         if (! TEST_BIT (visited, e->dest->index)
2340             && (int) loop_depth (e->dest->loop_father) > depth)
2341           stack[sp++] = e->dest;
2342     }
2343
2344   free (stack);
2345   sbitmap_free (visited);
2346 }
2347
2348 /* Returns the number of reduction phi nodes in LOOP.  */
2349
2350 static int
2351 nb_reductions_in_loop (loop_p loop)
2352 {
2353   int res = 0;
2354   gimple_stmt_iterator gsi;
2355
2356   for (gsi = gsi_start_phis (loop->header); !gsi_end_p (gsi); gsi_next (&gsi))
2357     {
2358       gimple phi = gsi_stmt (gsi);
2359       tree scev;
2360       affine_iv iv;
2361
2362       if (!is_gimple_reg (PHI_RESULT (phi)))
2363         continue;
2364
2365       scev = analyze_scalar_evolution (loop, PHI_RESULT (phi));
2366       scev = instantiate_parameters (loop, scev);
2367       if (!simple_iv (loop, loop, PHI_RESULT (phi), &iv, true))
2368         res++;
2369     }
2370
2371   return res;
2372 }
2373
2374 /* A LOOP is in normal form when it contains only one scalar phi node
2375    that defines the main induction variable of the loop, only one
2376    increment of the IV, and only one exit condition. */
2377
2378 static tree
2379 graphite_loop_normal_form (loop_p loop)
2380 {
2381   struct tree_niter_desc niter;
2382   tree nit;
2383   gimple_seq stmts;
2384   edge exit = single_dom_exit (loop);
2385   bool known_niter = number_of_iterations_exit (loop, exit, &niter, false);
2386
2387   gcc_assert (known_niter);
2388
2389   nit = force_gimple_operand (unshare_expr (niter.niter), &stmts, true,
2390                               NULL_TREE);
2391   if (stmts)
2392     gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
2393
2394   /* One IV per loop.  */
2395   if (nb_reductions_in_loop (loop) > 0)
2396     return NULL_TREE;
2397
2398   return canonicalize_loop_ivs (loop, NULL, &nit);
2399 }
2400
2401 /* Record LOOP as occuring in SCOP.  Returns true when the operation
2402    was successful.  */
2403
2404 static bool
2405 scop_record_loop (scop_p scop, loop_p loop)
2406 {
2407   tree induction_var;
2408   name_tree oldiv;
2409
2410   if (bitmap_bit_p (SCOP_LOOPS (scop), loop->num))
2411     return true;
2412
2413   bitmap_set_bit (SCOP_LOOPS (scop), loop->num);
2414   VEC_safe_push (loop_p, heap, SCOP_LOOP_NEST (scop), loop);
2415
2416   induction_var = graphite_loop_normal_form (loop);
2417   if (!induction_var)
2418     return false;
2419
2420   oldiv = XNEW (struct name_tree);
2421   oldiv->t = induction_var;
2422   oldiv->name = get_name (SSA_NAME_VAR (oldiv->t));
2423   oldiv->loop = loop;
2424   VEC_safe_push (name_tree, heap, SCOP_OLDIVS (scop), oldiv);
2425   return true;
2426 }
2427
2428 /* Build the loop nests contained in SCOP.  Returns true when the
2429    operation was successful.  */
2430
2431 static bool
2432 build_scop_loop_nests (scop_p scop)
2433 {
2434   unsigned i;
2435   basic_block bb;
2436   struct loop *loop0, *loop1;
2437
2438   FOR_EACH_BB (bb)
2439     if (bb_in_sese_p (bb, SCOP_REGION (scop)))
2440       {
2441         struct loop *loop = bb->loop_father;
2442
2443         /* Only add loops if they are completely contained in the SCoP.  */
2444         if (loop->header == bb
2445             && bb_in_sese_p (loop->latch, SCOP_REGION (scop)))
2446           {
2447             if (!scop_record_loop (scop, loop))
2448               return false;
2449           }
2450       }
2451
2452   /* Make sure that the loops in the SCOP_LOOP_NEST are ordered.  It
2453      can be the case that an inner loop is inserted before an outer
2454      loop.  To avoid this, semi-sort once.  */
2455   for (i = 0; VEC_iterate (loop_p, SCOP_LOOP_NEST (scop), i, loop0); i++)
2456     {
2457       if (VEC_length (loop_p, SCOP_LOOP_NEST (scop)) == i + 1)
2458         break;
2459
2460       loop1 = VEC_index (loop_p, SCOP_LOOP_NEST (scop), i + 1);
2461       if (loop0->num > loop1->num)
2462         {
2463           VEC_replace (loop_p, SCOP_LOOP_NEST (scop), i, loop1);
2464           VEC_replace (loop_p, SCOP_LOOP_NEST (scop), i + 1, loop0);
2465         }
2466     }
2467
2468   return true;
2469 }
2470
2471 /* Calculate the number of loops around LOOP in the SCOP.  */
2472
2473 static inline int
2474 nb_loops_around_loop_in_scop (struct loop *l, scop_p scop)
2475 {
2476   int d = 0;
2477
2478   for (; loop_in_sese_p (l, SCOP_REGION (scop)); d++, l = loop_outer (l));
2479
2480   return d;
2481 }
2482
2483 /* Calculate the number of loops around GB in the current SCOP.  */
2484
2485 int
2486 nb_loops_around_gb (graphite_bb_p gb)
2487 {
2488   return nb_loops_around_loop_in_scop (gbb_loop (gb), GBB_SCOP (gb));
2489 }
2490
2491 /* Returns the dimensionality of an enclosing loop iteration domain
2492    with respect to enclosing SCoP for a given data reference REF.  The
2493    returned dimensionality is homogeneous (depth of loop nest + number
2494    of SCoP parameters + const).  */
2495
2496 int
2497 ref_nb_loops (data_reference_p ref)
2498 {
2499   loop_p loop = loop_containing_stmt (DR_STMT (ref));
2500   scop_p scop = DR_SCOP (ref);
2501
2502   return nb_loops_around_loop_in_scop (loop, scop) + scop_nb_params (scop) + 2;
2503 }
2504
2505 /* Build dynamic schedules for all the BBs. */
2506
2507 static void
2508 build_scop_dynamic_schedules (scop_p scop)
2509 {
2510   int i, dim, loop_num, row, col;
2511   graphite_bb_p gb;
2512
2513   for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
2514     {
2515       loop_num = GBB_BB (gb)->loop_father->num;
2516
2517       if (loop_num != 0)
2518         {
2519           dim = nb_loops_around_gb (gb);
2520           GBB_DYNAMIC_SCHEDULE (gb) = cloog_matrix_alloc (dim, dim);
2521
2522           for (row = 0; row < GBB_DYNAMIC_SCHEDULE (gb)->NbRows; row++)
2523             for (col = 0; col < GBB_DYNAMIC_SCHEDULE (gb)->NbColumns; col++)
2524               if (row == col)
2525                 value_set_si (GBB_DYNAMIC_SCHEDULE (gb)->p[row][col], 1);
2526               else
2527                 value_set_si (GBB_DYNAMIC_SCHEDULE (gb)->p[row][col], 0);
2528         }
2529       else
2530         GBB_DYNAMIC_SCHEDULE (gb) = NULL;
2531     }
2532 }
2533
2534 /* Returns the number of loops that are identical at the beginning of
2535    the vectors A and B.  */
2536
2537 static int
2538 compare_prefix_loops (VEC (loop_p, heap) *a, VEC (loop_p, heap) *b)
2539 {
2540   int i;
2541   loop_p ea;
2542   int lb;
2543
2544   if (!a || !b)
2545     return 0;
2546
2547   lb = VEC_length (loop_p, b);
2548
2549   for (i = 0; VEC_iterate (loop_p, a, i, ea); i++)
2550     if (i >= lb
2551         || ea != VEC_index (loop_p, b, i))
2552       return i;
2553
2554   return 0;
2555 }
2556
2557 /* Build for BB the static schedule.
2558
2559    The STATIC_SCHEDULE is defined like this:
2560
2561    A
2562    for (i: ...)
2563      {
2564        for (j: ...)
2565          {
2566            B
2567            C
2568          }
2569
2570        for (k: ...)
2571          {
2572            D
2573            E
2574          }
2575      }
2576    F
2577
2578    Static schedules for A to F:
2579
2580      DEPTH
2581      0 1 2
2582    A 0
2583    B 1 0 0
2584    C 1 0 1
2585    D 1 1 0
2586    E 1 1 1
2587    F 2
2588 */
2589
2590 static void
2591 build_scop_canonical_schedules (scop_p scop)
2592 {
2593   int i;
2594   graphite_bb_p gb;
2595   int nb_loops = scop_nb_loops (scop);
2596   lambda_vector static_schedule = lambda_vector_new (nb_loops + 1);
2597   VEC (loop_p, heap) *loops_previous = NULL;
2598
2599   /* We have to start schedules at 0 on the first component and
2600      because we cannot compare_prefix_loops against a previous loop,
2601      prefix will be equal to zero, and that index will be
2602      incremented before copying.  */
2603   static_schedule[0] = -1;
2604
2605   for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
2606     {
2607       int prefix = compare_prefix_loops (loops_previous, GBB_LOOPS (gb));
2608       int nb = gbb_nb_loops (gb);
2609
2610       loops_previous = GBB_LOOPS (gb);
2611       memset (&(static_schedule[prefix + 1]), 0, sizeof (int) * (nb_loops - prefix));
2612       ++static_schedule[prefix];
2613       GBB_STATIC_SCHEDULE (gb) = lambda_vector_new (nb + 1);
2614       lambda_vector_copy (static_schedule,
2615                           GBB_STATIC_SCHEDULE (gb), nb + 1);
2616     }
2617 }
2618
2619 /* Build the LOOPS vector for all bbs in SCOP.  */
2620
2621 static void
2622 build_bb_loops (scop_p scop)
2623 {
2624   graphite_bb_p gb;
2625   int i;
2626
2627   for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
2628     {
2629       loop_p loop;
2630       int depth;
2631
2632       depth = nb_loops_around_gb (gb) - 1;
2633
2634       GBB_LOOPS (gb) = VEC_alloc (loop_p, heap, 3);
2635       VEC_safe_grow_cleared (loop_p, heap, GBB_LOOPS (gb), depth + 1);
2636
2637       loop = GBB_BB (gb)->loop_father;
2638
2639       while (scop_contains_loop (scop, loop))
2640         {
2641           VEC_replace (loop_p, GBB_LOOPS (gb), depth, loop);
2642           loop = loop_outer (loop);
2643           depth--;
2644         }
2645     }
2646 }
2647
2648 /* Get the index for parameter VAR in SCOP.  */
2649
2650 static int
2651 param_index (tree var, scop_p scop)
2652 {
2653   int i;
2654   name_tree p;
2655   name_tree nvar;
2656
2657   gcc_assert (TREE_CODE (var) == SSA_NAME);
2658
2659   for (i = 0; VEC_iterate (name_tree, SCOP_PARAMS (scop), i, p); i++)
2660     if (p->t == var)
2661       return i;
2662
2663   gcc_assert (SCOP_ADD_PARAMS (scop));
2664
2665   nvar = XNEW (struct name_tree);
2666   nvar->t = var;
2667   nvar->name = NULL;
2668   VEC_safe_push (name_tree, heap, SCOP_PARAMS (scop), nvar);
2669   return VEC_length (name_tree, SCOP_PARAMS (scop)) - 1;
2670 }
2671
2672 /* Scan EXPR and translate it to an inequality vector INEQ that will
2673    be added, or subtracted, in the constraint domain matrix C at row
2674    R.  K is the number of columns for loop iterators in C. */
2675
2676 static void
2677 scan_tree_for_params (scop_p s, tree e, CloogMatrix *c, int r, Value k,
2678                       bool subtract)
2679 {
2680   int cst_col, param_col;
2681
2682   if (e == chrec_dont_know)
2683     return;
2684
2685   switch (TREE_CODE (e))
2686     {
2687     case POLYNOMIAL_CHREC:
2688       {
2689         tree left = CHREC_LEFT (e);
2690         tree right = CHREC_RIGHT (e);
2691         int var = CHREC_VARIABLE (e);
2692
2693         if (TREE_CODE (right) != INTEGER_CST)
2694           return;
2695
2696         if (c)
2697           {
2698             int loop_col = scop_gimple_loop_depth (s, get_loop (var)) + 1;
2699
2700             if (subtract)
2701               value_sub_int (c->p[r][loop_col], c->p[r][loop_col],
2702                              int_cst_value (right));
2703             else
2704               value_add_int (c->p[r][loop_col], c->p[r][loop_col],
2705                              int_cst_value (right));
2706           }
2707
2708         switch (TREE_CODE (left))
2709           {
2710           case POLYNOMIAL_CHREC:
2711             scan_tree_for_params (s, left, c, r, k, subtract);
2712             return;
2713
2714           case INTEGER_CST:
2715             /* Constant part.  */
2716             if (c)
2717               {
2718                 int v = int_cst_value (left);
2719                 cst_col = c->NbColumns - 1;
2720
2721                 if (v < 0)
2722                   {
2723                     v = -v;
2724                     subtract = subtract ? false : true;
2725                   }
2726
2727                 if (subtract)
2728                   value_sub_int (c->p[r][cst_col], c->p[r][cst_col], v);
2729                 else
2730                   value_add_int (c->p[r][cst_col], c->p[r][cst_col], v);
2731               }
2732             return;
2733
2734           default:
2735             scan_tree_for_params (s, left, c, r, k, subtract);
2736             return;
2737           }
2738       }
2739       break;
2740
2741     case MULT_EXPR:
2742       if (chrec_contains_symbols (TREE_OPERAND (e, 0)))
2743         {
2744           if (c)
2745             {
2746               Value val;
2747               gcc_assert (host_integerp (TREE_OPERAND (e, 1), 0));
2748               value_init (val);
2749               value_set_si (val, int_cst_value (TREE_OPERAND (e, 1)));
2750               value_multiply (k, k, val);
2751               value_clear (val);
2752             }
2753           scan_tree_for_params (s, TREE_OPERAND (e, 0), c, r, k, subtract);
2754         }
2755       else
2756         {
2757           if (c)
2758             {
2759               Value val;
2760               gcc_assert (host_integerp (TREE_OPERAND (e, 0), 0));
2761               value_init (val);
2762               value_set_si (val, int_cst_value (TREE_OPERAND (e, 0)));
2763               value_multiply (k, k, val);
2764               value_clear (val);
2765             }
2766           scan_tree_for_params (s, TREE_OPERAND (e, 1), c, r, k, subtract);
2767         }
2768       break;
2769
2770     case PLUS_EXPR:
2771     case POINTER_PLUS_EXPR:
2772       scan_tree_for_params (s, TREE_OPERAND (e, 0), c, r, k, subtract);
2773       scan_tree_for_params (s, TREE_OPERAND (e, 1), c, r, k, subtract);
2774       break;
2775
2776     case MINUS_EXPR:
2777       scan_tree_for_params (s, TREE_OPERAND (e, 0), c, r, k, subtract);
2778       scan_tree_for_params (s, TREE_OPERAND (e, 1), c, r, k, !subtract);
2779       break;
2780
2781     case NEGATE_EXPR:
2782       scan_tree_for_params (s, TREE_OPERAND (e, 0), c, r, k, !subtract);
2783       break;
2784
2785     case SSA_NAME:
2786       param_col = param_index (e, s);
2787
2788       if (c)
2789         {
2790           param_col += c->NbColumns - scop_nb_params (s) - 1;
2791
2792           if (subtract)
2793             value_subtract (c->p[r][param_col], c->p[r][param_col], k);
2794           else
2795             value_addto (c->p[r][param_col], c->p[r][param_col], k);
2796         }
2797       break;
2798
2799     case INTEGER_CST:
2800       if (c)
2801         {
2802           int v = int_cst_value (e);
2803           cst_col = c->NbColumns - 1;
2804
2805           if (v < 0)
2806           {
2807             v = -v;
2808             subtract = subtract ? false : true;
2809           }
2810
2811           if (subtract)
2812             value_sub_int (c->p[r][cst_col], c->p[r][cst_col], v);
2813           else
2814             value_add_int (c->p[r][cst_col], c->p[r][cst_col], v);
2815         }
2816       break;
2817
2818     CASE_CONVERT:
2819     case NON_LVALUE_EXPR:
2820       scan_tree_for_params (s, TREE_OPERAND (e, 0), c, r, k, subtract);
2821       break;
2822
2823     default:
2824       gcc_unreachable ();
2825       break;
2826     }
2827 }
2828
2829 /* Data structure for idx_record_params.  */
2830
2831 struct irp_data
2832 {
2833   struct loop *loop;
2834   scop_p scop;
2835 };
2836
2837 /* For a data reference with an ARRAY_REF as its BASE, record the
2838    parameters occurring in IDX.  DTA is passed in as complementary
2839    information, and is used by the automatic walker function.  This
2840    function is a callback for for_each_index.  */
2841
2842 static bool
2843 idx_record_params (tree base, tree *idx, void *dta)
2844 {
2845   struct irp_data *data = (struct irp_data *) dta;
2846
2847   if (TREE_CODE (base) != ARRAY_REF)
2848     return true;
2849
2850   if (TREE_CODE (*idx) == SSA_NAME)
2851     {
2852       tree scev;
2853       scop_p scop = data->scop;
2854       struct loop *loop = data->loop;
2855       Value one;
2856
2857       scev = analyze_scalar_evolution (loop, *idx);
2858       scev = instantiate_scev (block_before_scop (scop), loop, scev);
2859
2860       value_init (one);
2861       value_set_si (one, 1);
2862       scan_tree_for_params (scop, scev, NULL, 0, one, false);
2863       value_clear (one);
2864     }
2865
2866   return true;
2867 }
2868
2869 /* Find parameters with respect to SCOP in BB. We are looking in memory
2870    access functions, conditions and loop bounds.  */
2871
2872 static void
2873 find_params_in_bb (scop_p scop, graphite_bb_p gb)
2874 {
2875   int i;
2876   data_reference_p dr;
2877   gimple stmt;
2878   loop_p father = GBB_BB (gb)->loop_father;
2879
2880   for (i = 0; VEC_iterate (data_reference_p, GBB_DATA_REFS (gb), i, dr); i++)
2881     {
2882       struct irp_data irp;
2883
2884       irp.loop = father;
2885       irp.scop = scop;
2886       for_each_index (&dr->ref, idx_record_params, &irp);
2887     }
2888
2889   /* Find parameters in conditional statements.  */
2890   for (i = 0; VEC_iterate (gimple, GBB_CONDITIONS (gb), i, stmt); i++)
2891     {
2892       Value one;
2893       loop_p loop = father;
2894
2895       tree lhs, rhs;
2896
2897       lhs = gimple_cond_lhs (stmt);
2898       lhs = analyze_scalar_evolution (loop, lhs);
2899       lhs = instantiate_scev (block_before_scop (scop), loop, lhs);
2900
2901       rhs = gimple_cond_rhs (stmt);
2902       rhs = analyze_scalar_evolution (loop, rhs);
2903       rhs = instantiate_scev (block_before_scop (scop), loop, rhs);
2904
2905       value_init (one);
2906       scan_tree_for_params (scop, lhs, NULL, 0, one, false);
2907       value_set_si (one, 1);
2908       scan_tree_for_params (scop, rhs, NULL, 0, one, false);
2909       value_clear (one);
2910     }
2911 }
2912
2913 /* Saves in NV the name of variable P->T.  */
2914
2915 static void
2916 save_var_name (char **nv, int i, name_tree p)
2917 {
2918   const char *name = get_name (SSA_NAME_VAR (p->t));
2919
2920   if (name)
2921     {
2922       int len = strlen (name) + 16;
2923       nv[i] = XNEWVEC (char, len);
2924       snprintf (nv[i], len, "%s_%d", name, SSA_NAME_VERSION (p->t));
2925     }
2926   else
2927     {
2928       nv[i] = XNEWVEC (char, 16);
2929       snprintf (nv[i], 2 + 16, "T_%d", SSA_NAME_VERSION (p->t));
2930     }
2931
2932   p->name = nv[i];
2933 }
2934
2935 /* Return the maximal loop depth in SCOP.  */
2936
2937 static int
2938 scop_max_loop_depth (scop_p scop)
2939 {
2940   int i;
2941   graphite_bb_p gbb;
2942   int max_nb_loops = 0;
2943
2944   for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gbb); i++)
2945     {
2946       int nb_loops = gbb_nb_loops (gbb);
2947       if (max_nb_loops < nb_loops)
2948         max_nb_loops = nb_loops;
2949     }
2950
2951   return max_nb_loops;
2952 }
2953
2954 /* Initialize Cloog's parameter names from the names used in GIMPLE.
2955    Initialize Cloog's iterator names, using 'graphite_iterator_%d'
2956    from 0 to scop_nb_loops (scop).  */
2957
2958 static void
2959 initialize_cloog_names (scop_p scop)
2960 {
2961   int i, nb_params = VEC_length (name_tree, SCOP_PARAMS (scop));
2962   char **params = XNEWVEC (char *, nb_params);
2963   int nb_iterators = scop_max_loop_depth (scop);
2964   int nb_scattering= cloog_program_nb_scattdims (SCOP_PROG (scop));
2965   char **iterators = XNEWVEC (char *, nb_iterators * 2);
2966   char **scattering = XNEWVEC (char *, nb_scattering);
2967   name_tree p;
2968
2969   for (i = 0; VEC_iterate (name_tree, SCOP_PARAMS (scop), i, p); i++)
2970     save_var_name (params, i, p);
2971
2972   cloog_names_set_nb_parameters (cloog_program_names (SCOP_PROG (scop)),
2973                                  nb_params);
2974   cloog_names_set_parameters (cloog_program_names (SCOP_PROG (scop)),
2975                               params);
2976
2977   for (i = 0; i < nb_iterators; i++)
2978     {
2979       int len = 18 + 16;
2980       iterators[i] = XNEWVEC (char, len);
2981       snprintf (iterators[i], len, "graphite_iterator_%d", i);
2982     }
2983
2984   cloog_names_set_nb_iterators (cloog_program_names (SCOP_PROG (scop)),
2985                                 nb_iterators);
2986   cloog_names_set_iterators (cloog_program_names (SCOP_PROG (scop)),
2987                              iterators);
2988
2989   for (i = 0; i < nb_scattering; i++)
2990     {
2991       int len = 2 + 16;
2992       scattering[i] = XNEWVEC (char, len);
2993       snprintf (scattering[i], len, "s_%d", i);
2994     }
2995
2996   cloog_names_set_nb_scattering (cloog_program_names (SCOP_PROG (scop)),
2997                                  nb_scattering);
2998   cloog_names_set_scattering (cloog_program_names (SCOP_PROG (scop)),
2999                               scattering);
3000 }
3001
3002 /* Record the parameters used in the SCOP.  A variable is a parameter
3003    in a scop if it does not vary during the execution of that scop.  */
3004
3005 static void
3006 find_scop_parameters (scop_p scop)
3007 {
3008   graphite_bb_p gb;
3009   unsigned i;
3010   struct loop *loop;
3011   Value one;
3012
3013   value_init (one);
3014   value_set_si (one, 1);
3015
3016   /* Find the parameters used in the loop bounds.  */
3017   for (i = 0; VEC_iterate (loop_p, SCOP_LOOP_NEST (scop), i, loop); i++)
3018     {
3019       tree nb_iters = number_of_latch_executions (loop);
3020
3021       if (!chrec_contains_symbols (nb_iters))
3022         continue;
3023
3024       nb_iters = analyze_scalar_evolution (loop, nb_iters);
3025       nb_iters = instantiate_scev (block_before_scop (scop), loop, nb_iters);
3026       scan_tree_for_params (scop, nb_iters, NULL, 0, one, false);
3027     }
3028
3029   value_clear (one);
3030
3031   /* Find the parameters used in data accesses.  */
3032   for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
3033     find_params_in_bb (scop, gb);
3034
3035   SCOP_ADD_PARAMS (scop) = false;
3036 }
3037
3038 /* Build the context constraints for SCOP: constraints and relations
3039    on parameters.  */
3040
3041 static void
3042 build_scop_context (scop_p scop)
3043 {
3044   int nb_params = scop_nb_params (scop);
3045   CloogMatrix *matrix = cloog_matrix_alloc (1, nb_params + 2);
3046
3047   /* Insert '0 >= 0' in the context matrix, as it is not allowed to be
3048      empty. */
3049
3050   value_set_si (matrix->p[0][0], 1);
3051
3052   value_set_si (matrix->p[0][nb_params + 1], 0);
3053
3054   cloog_program_set_context (SCOP_PROG (scop),
3055                              cloog_domain_matrix2domain (matrix));
3056   cloog_matrix_free (matrix);
3057 }
3058
3059 /* Returns a graphite_bb from BB.  */
3060
3061 static inline graphite_bb_p
3062 gbb_from_bb (basic_block bb)
3063 {
3064   return (graphite_bb_p) bb->aux;
3065 }
3066
3067 /* Builds the constraint matrix for LOOP in SCOP.  NB_OUTER_LOOPS is the
3068    number of loops surrounding LOOP in SCOP.  OUTER_CSTR gives the
3069    constraints matrix for the surrounding loops.  */
3070
3071 static void
3072 build_loop_iteration_domains (scop_p scop, struct loop *loop,
3073                               CloogMatrix *outer_cstr, int nb_outer_loops)
3074 {
3075   int i, j, row;
3076   CloogMatrix *cstr;
3077   graphite_bb_p gb;
3078
3079   int nb_rows = outer_cstr->NbRows + 1;
3080   int nb_cols = outer_cstr->NbColumns + 1;
3081
3082   /* Last column of CSTR is the column of constants.  */
3083   int cst_col = nb_cols - 1;
3084
3085   /* The column for the current loop is just after the columns of
3086      other outer loops.  */
3087   int loop_col = nb_outer_loops + 1;
3088
3089   tree nb_iters = number_of_latch_executions (loop);
3090
3091   /* When the number of iterations is a constant or a parameter, we
3092      add a constraint for the upper bound of the loop.  So add a row
3093      to the constraint matrix before allocating it.  */
3094   if (TREE_CODE (nb_iters) == INTEGER_CST
3095       || !chrec_contains_undetermined (nb_iters))
3096     nb_rows++;
3097
3098   cstr = cloog_matrix_alloc (nb_rows, nb_cols);
3099
3100   /* Copy the outer constraints.  */
3101   for (i = 0; i < outer_cstr->NbRows; i++)
3102     {
3103       /* Copy the eq/ineq and loops columns.  */
3104       for (j = 0; j < loop_col; j++)
3105         value_assign (cstr->p[i][j], outer_cstr->p[i][j]);
3106
3107       /* Leave an empty column in CSTR for the current loop, and then
3108          copy the parameter columns.  */
3109       for (j = loop_col; j < outer_cstr->NbColumns; j++)
3110         value_assign (cstr->p[i][j + 1], outer_cstr->p[i][j]);
3111     }
3112
3113   /* 0 <= loop_i */
3114   row = outer_cstr->NbRows;
3115   value_set_si (cstr->p[row][0], 1);
3116   value_set_si (cstr->p[row][loop_col], 1);
3117
3118   /* loop_i <= nb_iters */
3119   if (TREE_CODE (nb_iters) == INTEGER_CST)
3120     {
3121       row++;
3122       value_set_si (cstr->p[row][0], 1);
3123       value_set_si (cstr->p[row][loop_col], -1);
3124
3125       value_set_si (cstr->p[row][cst_col],
3126                     int_cst_value (nb_iters));
3127     }
3128   else if (!chrec_contains_undetermined (nb_iters))
3129     {
3130       /* Otherwise nb_iters contains parameters: scan the nb_iters
3131          expression and build its matrix representation.  */
3132       Value one;
3133
3134       row++;
3135       value_set_si (cstr->p[row][0], 1);
3136       value_set_si (cstr->p[row][loop_col], -1);
3137
3138       nb_iters = analyze_scalar_evolution (loop, nb_iters);
3139       nb_iters = instantiate_scev (block_before_scop (scop), loop, nb_iters);
3140
3141       value_init (one);
3142       value_set_si (one, 1);
3143       scan_tree_for_params (scop, nb_iters, cstr, row, one, false);
3144       value_clear (one);
3145     }
3146   else
3147     gcc_unreachable ();
3148
3149   if (loop->inner && loop_in_sese_p (loop->inner, SCOP_REGION (scop)))
3150     build_loop_iteration_domains (scop, loop->inner, cstr, nb_outer_loops + 1);
3151
3152   /* Only go to the next loops, if we are not at the outermost layer.  These
3153      have to be handled seperately, as we can be sure, that the chain at this
3154      layer will be connected.  */
3155   if (nb_outer_loops != 0 && loop->next && loop_in_sese_p (loop->next,
3156                                                            SCOP_REGION (scop)))
3157     build_loop_iteration_domains (scop, loop->next, outer_cstr, nb_outer_loops);
3158
3159   for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
3160     if (gbb_loop (gb) == loop)
3161       GBB_DOMAIN (gb) = cloog_matrix_copy (cstr);
3162
3163   cloog_matrix_free (cstr);
3164 }
3165
3166 /* Add conditions to the domain of GB.  */
3167
3168 static void
3169 add_conditions_to_domain (graphite_bb_p gb)
3170 {
3171   unsigned int i,j;
3172   gimple stmt;
3173   VEC (gimple, heap) *conditions = GBB_CONDITIONS (gb);
3174   CloogMatrix *domain = GBB_DOMAIN (gb);
3175   scop_p scop = GBB_SCOP (gb);
3176
3177   unsigned nb_rows;
3178   unsigned nb_cols;
3179   unsigned nb_new_rows = 0;
3180   unsigned row;
3181
3182   if (VEC_empty (gimple, conditions))
3183     return;
3184
3185   if (domain)
3186     {
3187       nb_rows = domain->NbRows;
3188       nb_cols = domain->NbColumns;
3189     }
3190   else
3191     {
3192       nb_rows = 0;
3193       nb_cols = nb_loops_around_gb (gb) + scop_nb_params (scop) + 2;
3194     }
3195
3196   /* Count number of necessary new rows to add the conditions to the
3197      domain.  */
3198   for (i = 0; VEC_iterate (gimple, conditions, i, stmt); i++)
3199     {
3200       switch (gimple_code (stmt))
3201         {
3202         case GIMPLE_COND:
3203           {
3204             enum tree_code code = gimple_cond_code (stmt);
3205
3206             switch (code)
3207               {
3208               case NE_EXPR:
3209               case EQ_EXPR:
3210                 /* NE and EQ statements are not supported right know. */
3211                 gcc_unreachable ();
3212                 break;
3213               case LT_EXPR:
3214               case GT_EXPR:
3215               case LE_EXPR:
3216               case GE_EXPR:
3217                 nb_new_rows++;
3218                 break;
3219               default:
3220                 gcc_unreachable ();
3221                 break;
3222               }
3223           break;
3224           }
3225         case SWITCH_EXPR:
3226           /* Switch statements are not supported right know.  */
3227           gcc_unreachable ();
3228           break;
3229
3230         default:
3231           gcc_unreachable ();
3232           break;
3233         }
3234     }
3235
3236
3237   /* Enlarge the matrix.  */
3238   {
3239     CloogMatrix *new_domain;
3240     new_domain = cloog_matrix_alloc (nb_rows + nb_new_rows, nb_cols);
3241
3242     if (domain)
3243       {
3244         for (i = 0; i < nb_rows; i++)
3245           for (j = 0; j < nb_cols; j++)
3246             value_assign (new_domain->p[i][j], domain->p[i][j]);
3247
3248         cloog_matrix_free (domain);
3249       }
3250
3251     domain = new_domain;
3252     GBB_DOMAIN (gb) = new_domain;
3253   }
3254
3255   /* Add the conditions to the new enlarged domain matrix.  */
3256   row = nb_rows;
3257   for (i = 0; VEC_iterate (gimple, conditions, i, stmt); i++)
3258     {
3259       switch (gimple_code (stmt))
3260         {
3261         case GIMPLE_COND:
3262           {
3263             Value one;
3264             enum tree_code code;
3265             tree left;
3266             tree right;
3267             loop_p loop = GBB_BB (gb)->loop_father;
3268
3269             left = gimple_cond_lhs (stmt);
3270             right = gimple_cond_rhs (stmt);
3271
3272             left = analyze_scalar_evolution (loop, left);
3273             right = analyze_scalar_evolution (loop, right);
3274
3275             left = instantiate_scev (block_before_scop (scop), loop, left);
3276             right = instantiate_scev (block_before_scop (scop), loop, right);
3277
3278             code = gimple_cond_code (stmt);
3279
3280             /* The conditions for ELSE-branches are inverted.  */
3281             if (VEC_index (gimple, gb->condition_cases, i) == NULL)
3282               code = invert_tree_comparison (code, false);
3283
3284             switch (code)
3285               {
3286               case NE_EXPR:
3287                 /* NE statements are not supported right know. */
3288                 gcc_unreachable ();
3289                 break;
3290               case EQ_EXPR:
3291                 value_set_si (domain->p[row][0], 1);
3292                 value_init (one);
3293                 value_set_si (one, 1);
3294                 scan_tree_for_params (scop, left, domain, row, one, true);
3295                 value_set_si (one, 1);
3296                 scan_tree_for_params (scop, right, domain, row, one, false);
3297                 row++;
3298                 value_set_si (domain->p[row][0], 1);
3299                 value_set_si (one, 1);
3300                 scan_tree_for_params (scop, left, domain, row, one, false);
3301                 value_set_si (one, 1);
3302                 scan_tree_for_params (scop, right, domain, row, one, true);
3303                 value_clear (one);
3304                 row++;
3305                 break;
3306               case LT_EXPR:
3307                 value_set_si (domain->p[row][0], 1);
3308                 value_init (one);
3309                 value_set_si (one, 1);
3310                 scan_tree_for_params (scop, left, domain, row, one, true);
3311                 value_set_si (one, 1);
3312                 scan_tree_for_params (scop, right, domain, row, one, false);
3313                 value_sub_int (domain->p[row][nb_cols - 1],
3314                     domain->p[row][nb_cols - 1], 1);
3315                 value_clear (one);
3316                 row++;
3317                 break;
3318               case GT_EXPR:
3319                 value_set_si (domain->p[row][0], 1);
3320                 value_init (one);
3321                 value_set_si (one, 1);
3322                 scan_tree_for_params (scop, left, domain, row, one, false);
3323                 value_set_si (one, 1);
3324                 scan_tree_for_params (scop, right, domain, row, one, true);
3325                 value_sub_int (domain->p[row][nb_cols - 1],
3326                     domain->p[row][nb_cols - 1], 1);
3327                 value_clear (one);
3328                 row++;
3329                 break;
3330               case LE_EXPR:
3331                 value_set_si (domain->p[row][0], 1);
3332                 value_init (one);
3333                 value_set_si (one, 1);
3334                 scan_tree_for_params (scop, left, domain, row, one, true);
3335                 value_set_si (one, 1);
3336                 scan_tree_for_params (scop, right, domain, row, one, false);
3337                 value_clear (one);
3338                 row++;
3339                 break;
3340               case GE_EXPR:
3341                 value_set_si (domain->p[row][0], 1);
3342                 value_init (one);
3343                 value_set_si (one, 1);
3344                 scan_tree_for_params (scop, left, domain, row, one, false);
3345                 value_set_si (one, 1);
3346                 scan_tree_for_params (scop, right, domain, row, one, true);
3347                 value_clear (one);
3348                 row++;
3349                 break;
3350               default:
3351                 gcc_unreachable ();
3352                 break;
3353               }
3354             break;
3355           }
3356         case GIMPLE_SWITCH:
3357           /* Switch statements are not supported right know.  */
3358           gcc_unreachable ();
3359           break;
3360
3361         default:
3362           gcc_unreachable ();
3363           break;
3364         }
3365     }
3366 }
3367
3368 /* Returns true when PHI defines an induction variable in the loop
3369    containing the PHI node.  */
3370
3371 static bool
3372 phi_node_is_iv (gimple phi)
3373 {
3374   loop_p loop = gimple_bb (phi)->loop_father;
3375   tree scev = analyze_scalar_evolution (loop, gimple_phi_result (phi));
3376
3377   return tree_contains_chrecs (scev, NULL);
3378 }
3379
3380 /* Returns true when BB contains scalar phi nodes that are not an
3381    induction variable of a loop.  */
3382
3383 static bool
3384 bb_contains_non_iv_scalar_phi_nodes (basic_block bb)
3385 {
3386   gimple phi = NULL;
3387   gimple_stmt_iterator si;
3388
3389   for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
3390     if (is_gimple_reg (gimple_phi_result (gsi_stmt (si))))
3391       {
3392         /* Store the unique scalar PHI node: at this point, loops
3393            should be in cannonical form, so we expect to see at most
3394            one scalar phi node in the loop header.  */
3395         if (phi
3396             || bb != bb->loop_father->header)
3397           return true;
3398
3399         phi = gsi_stmt (si);
3400       }
3401
3402   if (!phi
3403       || phi_node_is_iv (phi))
3404     return false;
3405
3406   return true;
3407 }
3408
3409 /* Helper recursive function.  Record in CONDITIONS and CASES all
3410    conditions from 'if's and 'switch'es occurring in BB from SCOP.
3411
3412    Returns false when the conditions contain scalar computations that
3413    depend on the condition, i.e. when there are scalar phi nodes on
3414    the junction after the condition.  Only the computations occurring
3415    on memory can be handled in the polyhedral model: operations that
3416    define scalar evolutions in conditions, that can potentially be
3417    used to index memory, can't be handled by the polyhedral model.  */
3418
3419 static bool
3420 build_scop_conditions_1 (VEC (gimple, heap) **conditions,
3421                          VEC (gimple, heap) **cases, basic_block bb,
3422                          scop_p scop)
3423 {
3424   bool res = true;
3425   int i, j;
3426   graphite_bb_p gbb;
3427   basic_block bb_child, bb_iter;
3428   VEC (basic_block, heap) *dom;
3429   gimple stmt;
3430
3431   /* Make sure we are in the SCoP.  */
3432   if (!bb_in_sese_p (bb, SCOP_REGION (scop)))
3433     return true;
3434
3435   if (bb_contains_non_iv_scalar_phi_nodes (bb))
3436     return false;
3437
3438   gbb = gbb_from_bb (bb);
3439   if (gbb)
3440     {
3441       GBB_CONDITIONS (gbb) = VEC_copy (gimple, heap, *conditions);
3442       GBB_CONDITION_CASES (gbb) = VEC_copy (gimple, heap, *cases);
3443     }
3444
3445   dom = get_dominated_by (CDI_DOMINATORS, bb);
3446
3447   stmt = last_stmt (bb);
3448   if (stmt)
3449     {
3450       VEC (edge, gc) *edges;
3451       edge e;
3452
3453       switch (gimple_code (stmt))
3454         {
3455         case GIMPLE_COND:
3456           edges = bb->succs;
3457           for (i = 0; VEC_iterate (edge, edges, i, e); i++)
3458             if ((dominated_by_p (CDI_DOMINATORS, e->dest, bb))
3459                 && VEC_length (edge, e->dest->preds) == 1)
3460               {
3461                 /* Remove the scanned block from the dominator successors.  */
3462                 for (j = 0; VEC_iterate (basic_block, dom, j, bb_iter); j++)
3463                   if (bb_iter == e->dest)
3464                     {
3465                       VEC_unordered_remove (basic_block, dom, j);
3466                       break;
3467                     }
3468
3469                 /* Recursively scan the then or else part.  */
3470                 if (e->flags & EDGE_TRUE_VALUE)
3471                   VEC_safe_push (gimple, heap, *cases, stmt);
3472                 else
3473                   {
3474                     gcc_assert (e->flags & EDGE_FALSE_VALUE);
3475                     VEC_safe_push (gimple, heap, *cases, NULL);
3476                   }
3477
3478                 VEC_safe_push (gimple, heap, *conditions, stmt);
3479                 if (!build_scop_conditions_1 (conditions, cases, e->dest, scop))
3480                   {
3481                     res = false;
3482                     goto done;
3483                   }
3484                 VEC_pop (gimple, *conditions);
3485                 VEC_pop (gimple, *cases);
3486               }
3487           break;
3488
3489         case GIMPLE_SWITCH:
3490           {
3491             unsigned i;
3492             gimple_stmt_iterator gsi_search_gimple_label;
3493
3494             for (i = 0; i < gimple_switch_num_labels (stmt); ++i)
3495               {
3496                 basic_block bb_iter;
3497                 size_t k;
3498                 size_t n_cases = VEC_length (gimple, *conditions);
3499                 unsigned n = gimple_switch_num_labels (stmt);
3500
3501                 bb_child = label_to_block
3502                   (CASE_LABEL (gimple_switch_label (stmt, i)));
3503
3504                 for (k = 0; k < n; k++)
3505                   if (i != k
3506                       && label_to_block
3507                       (CASE_LABEL (gimple_switch_label (stmt, k))) == bb_child)
3508                     break;
3509
3510                 /* Switches with multiple case values for the same
3511                    block are not handled.  */
3512                 if (k != n
3513                     /* Switch cases with more than one predecessor are
3514                        not handled.  */
3515                     || VEC_length (edge, bb_child->preds) != 1)
3516                   {
3517                     res = false;
3518                     goto done;
3519                   }
3520
3521                 /* Recursively scan the corresponding 'case' block.  */
3522                 for (gsi_search_gimple_label = gsi_start_bb (bb_child);
3523                      !gsi_end_p (gsi_search_gimple_label);
3524                      gsi_next (&gsi_search_gimple_label))
3525                   {
3526                     gimple label = gsi_stmt (gsi_search_gimple_label);
3527
3528                     if (gimple_code (label) == GIMPLE_LABEL)
3529                       {
3530                         tree t = gimple_label_label (label);
3531
3532                         gcc_assert (t == gimple_switch_label (stmt, i));
3533                         VEC_replace (gimple, *cases, n_cases, label);
3534                         break;
3535                       }
3536                   }
3537
3538                 if (!build_scop_conditions_1 (conditions, cases, bb_child, scop))
3539                   {
3540                     res = false;
3541                     goto done;
3542                   }
3543
3544                 /* Remove the scanned block from the dominator successors.  */
3545                 for (j = 0; VEC_iterate (basic_block, dom, j, bb_iter); j++)
3546                   if (bb_iter == bb_child)
3547                     {
3548                       VEC_unordered_remove (basic_block, dom, j);
3549                       break;
3550                     }
3551               }
3552
3553             VEC_pop (gimple, *conditions);
3554             VEC_pop (gimple, *cases);
3555             break;
3556           }
3557
3558         default:
3559           break;
3560       }
3561   }
3562
3563   /* Scan all immediate dominated successors.  */
3564   for (i = 0; VEC_iterate (basic_block, dom, i, bb_child); i++)
3565     if (!build_scop_conditions_1 (conditions, cases, bb_child, scop))
3566       {
3567         res = false;
3568         goto done;
3569       }
3570
3571  done:
3572   VEC_free (basic_block, heap, dom);
3573   return res;
3574 }
3575
3576 /* Record all conditions from SCOP.
3577
3578    Returns false when the conditions contain scalar computations that
3579    depend on the condition, i.e. when there are scalar phi nodes on
3580    the junction after the condition.  Only the computations occurring
3581    on memory can be handled in the polyhedral model: operations that
3582    define scalar evolutions in conditions, that can potentially be
3583    used to index memory, can't be handled by the polyhedral model.  */
3584
3585 static bool
3586 build_scop_conditions (scop_p scop)
3587 {
3588   bool res;
3589   VEC (gimple, heap) *conditions = NULL;
3590   VEC (gimple, heap) *cases = NULL;
3591
3592   res = build_scop_conditions_1 (&conditions, &cases, SCOP_ENTRY (scop), scop);
3593
3594   VEC_free (gimple, heap, conditions);
3595   VEC_free (gimple, heap, cases);
3596   return res;
3597 }
3598
3599 /* Traverses all the GBBs of the SCOP and add their constraints to the
3600    iteration domains.  */
3601
3602 static void
3603 add_conditions_to_constraints (scop_p scop)
3604 {
3605   int i;
3606   graphite_bb_p gbb;
3607
3608   for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gbb); i++)
3609     add_conditions_to_domain (gbb);
3610 }
3611
3612 /* Build the current domain matrix: the loops belonging to the current
3613    SCOP, and that vary for the execution of the current basic block.
3614    Returns false if there is no loop in SCOP.  */
3615
3616 static bool
3617 build_scop_iteration_domain (scop_p scop)
3618 {
3619   struct loop *loop;
3620   CloogMatrix *outer_cstr;
3621   int i;
3622
3623   /* Build cloog loop for all loops, that are in the uppermost loop layer of
3624      this SCoP.  */
3625   for (i = 0; VEC_iterate (loop_p, SCOP_LOOP_NEST (scop), i, loop); i++)
3626     if (!loop_in_sese_p (loop_outer (loop), SCOP_REGION (scop)))
3627       {
3628         /* The outermost constraints is a matrix that has:
3629            -first column: eq/ineq boolean
3630            -last column: a constant
3631            -scop_nb_params columns for the parameters used in the scop.  */
3632         outer_cstr = cloog_matrix_alloc (0, scop_nb_params (scop) + 2);
3633         build_loop_iteration_domains (scop, loop, outer_cstr, 0);
3634         cloog_matrix_free (outer_cstr);
3635       }
3636
3637   return (i != 0);
3638 }
3639
3640 /* Initializes an equation CY of the access matrix using the
3641    information for a subscript from AF, relatively to the loop
3642    indexes from LOOP_NEST and parameter indexes from PARAMS.  NDIM is
3643    the dimension of the array access, i.e. the number of
3644    subscripts.  Returns true when the operation succeeds.  */
3645
3646 static bool
3647 build_access_matrix_with_af (tree af, lambda_vector cy,
3648                              scop_p scop, int ndim)
3649 {
3650   int param_col;
3651
3652   switch (TREE_CODE (af))
3653     {
3654     case POLYNOMIAL_CHREC:
3655       {
3656         struct loop *outer_loop;
3657         tree left = CHREC_LEFT (af);
3658         tree right = CHREC_RIGHT (af);
3659         int var;
3660
3661         if (TREE_CODE (right) != INTEGER_CST)
3662           return false;
3663
3664         outer_loop = get_loop (CHREC_VARIABLE (af));
3665         var = nb_loops_around_loop_in_scop (outer_loop, scop);
3666         cy[var] = int_cst_value (right);
3667
3668         switch (TREE_CODE (left))
3669           {
3670           case POLYNOMIAL_CHREC:
3671             return build_access_matrix_with_af (left, cy, scop, ndim);
3672
3673           case INTEGER_CST:
3674             cy[ndim - 1] = int_cst_value (left);
3675             return true;
3676
3677           default:
3678             return build_access_matrix_with_af (left, cy, scop, ndim);
3679           }
3680       }
3681
3682     case PLUS_EXPR:
3683       build_access_matrix_with_af (TREE_OPERAND (af, 0), cy, scop, ndim);
3684       build_access_matrix_with_af (TREE_OPERAND (af, 1), cy, scop, ndim);
3685       return true;
3686
3687     case MINUS_EXPR:
3688       build_access_matrix_with_af (TREE_OPERAND (af, 0), cy, scop, ndim);
3689       build_access_matrix_with_af (TREE_OPERAND (af, 1), cy, scop, ndim);
3690       return true;
3691
3692     case INTEGER_CST:
3693       cy[ndim - 1] = int_cst_value (af);
3694       return true;
3695
3696     case SSA_NAME:
3697       param_col = param_index (af, scop);
3698       cy [ndim - scop_nb_params (scop) + param_col - 1] = 1;
3699       return true;
3700
3701     default:
3702       /* FIXME: access_fn can have parameters.  */
3703       return false;
3704     }
3705 }
3706
3707 /* Initialize the access matrix in the data reference REF with respect
3708    to the loop nesting LOOP_NEST.  Return true when the operation
3709    succeeded.  */
3710
3711 static bool
3712 build_access_matrix (data_reference_p ref, graphite_bb_p gb)
3713 {
3714   int i, ndim = DR_NUM_DIMENSIONS (ref);
3715   struct access_matrix *am = GGC_NEW (struct access_matrix);
3716
3717   AM_MATRIX (am) = VEC_alloc (lambda_vector, gc, ndim);
3718   DR_SCOP (ref) = GBB_SCOP (gb);
3719
3720   for (i = 0; i < ndim; i++)
3721     {
3722       lambda_vector v = lambda_vector_new (ref_nb_loops (ref));
3723       scop_p scop = GBB_SCOP (gb);
3724       tree af = DR_ACCESS_FN (ref, i);
3725
3726       if (!build_access_matrix_with_af (af, v, scop, ref_nb_loops (ref)))
3727         return false;
3728
3729       VEC_quick_push (lambda_vector, AM_MATRIX (am), v);
3730     }
3731
3732   DR_ACCESS_MATRIX (ref) = am;
3733   return true;
3734 }
3735
3736 /* Build the access matrices for the data references in the SCOP.  */
3737
3738 static void
3739 build_scop_data_accesses (scop_p scop)
3740 {
3741   int i;
3742   graphite_bb_p gb;
3743
3744   /* FIXME: Construction of access matrix is disabled until some
3745      pass, like the data dependence analysis, is using it.  */
3746   return;
3747
3748   for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
3749     {
3750       int j;
3751       data_reference_p dr;
3752
3753       /* Construct the access matrix for each data ref, with respect to
3754          the loop nest of the current BB in the considered SCOP.  */
3755       for (j = 0;
3756            VEC_iterate (data_reference_p, GBB_DATA_REFS (gb), j, dr);
3757            j++)
3758         {
3759           bool res = build_access_matrix (dr, gb);
3760
3761           /* FIXME: At this point the DRs should always have an affine
3762              form.  For the moment this fails as build_access_matrix
3763              does not build matrices with parameters.  */
3764           gcc_assert (res);
3765         }
3766     }
3767 }
3768
3769 /* Returns the tree variable from the name NAME that was given in
3770    Cloog representation.  All the parameters are stored in PARAMS, and
3771    all the loop induction variables are stored in IVSTACK.
3772
3773    FIXME: This is a hack, and Cloog should be fixed to not work with
3774    variable names represented as "char *string", but with void
3775    pointers that could be casted back to a tree.  The only problem in
3776    doing that is that Cloog's pretty printer still assumes that
3777    variable names are char *strings.  The solution would be to have a
3778    function pointer for pretty-printing that can be redirected to be
3779    print_generic_stmt in our case, or fprintf by default.
3780    ???  Too ugly to live.  */
3781
3782 static tree
3783 clast_name_to_gcc (const char *name, VEC (name_tree, heap) *params,
3784                    loop_iv_stack ivstack)
3785 {
3786   int i;
3787   name_tree t;
3788   tree iv;
3789
3790   if (params)
3791     for (i = 0; VEC_iterate (name_tree, params, i, t); i++)
3792       if (!strcmp (name, t->name))
3793         return t->t;
3794
3795   iv = loop_iv_stack_get_iv_from_name (ivstack, name);
3796   if (iv)
3797     return iv;
3798
3799   gcc_unreachable ();
3800 }
3801
3802 /* Returns the maximal precision type for expressions E1 and E2.  */
3803
3804 static inline tree
3805 max_precision_type (tree e1, tree e2)
3806 {
3807   tree type1 = TREE_TYPE (e1);
3808   tree type2 = TREE_TYPE (e2);
3809   return TYPE_PRECISION (type1) > TYPE_PRECISION (type2) ? type1 : type2;
3810 }
3811
3812 static tree
3813 clast_to_gcc_expression (tree, struct clast_expr *, VEC (name_tree, heap) *,
3814                          loop_iv_stack);
3815
3816 /* Converts a Cloog reduction expression R with reduction operation OP
3817    to a GCC expression tree of type TYPE.  PARAMS is a vector of
3818    parameters of the scop, and IVSTACK contains the stack of induction
3819    variables.  */
3820
3821 static tree
3822 clast_to_gcc_expression_red (tree type, enum tree_code op,
3823                              struct clast_reduction *r,
3824                              VEC (name_tree, heap) *params,
3825                              loop_iv_stack ivstack)
3826 {
3827   int i;
3828   tree res = clast_to_gcc_expression (type, r->elts[0], params, ivstack);
3829
3830   for (i = 1; i < r->n; i++)
3831     {
3832       tree t = clast_to_gcc_expression (type, r->elts[i], params, ivstack);
3833       res = fold_build2 (op, type, res, t);
3834     }
3835   return res;
3836 }
3837
3838 /* Converts a Cloog AST expression E back to a GCC expression tree of
3839    type TYPE.  PARAMS is a vector of parameters of the scop, and
3840    IVSTACK contains the stack of induction variables.  */
3841
3842 static tree
3843 clast_to_gcc_expression (tree type, struct clast_expr *e,
3844                          VEC (name_tree, heap) *params,
3845                          loop_iv_stack ivstack)
3846 {
3847   switch (e->type)
3848     {
3849     case expr_term:
3850       {
3851         struct clast_term *t = (struct clast_term *) e;
3852
3853         if (t->var)
3854           {
3855             if (value_one_p (t->val))
3856               {
3857                 tree name = clast_name_to_gcc (t->var, params, ivstack);
3858                 return fold_convert (type, name);
3859               }
3860
3861             else if (value_mone_p (t->val))
3862               {
3863                 tree name = clast_name_to_gcc (t->var, params, ivstack);
3864                 name = fold_convert (type, name);
3865                 return fold_build1 (NEGATE_EXPR, type, name);
3866               }
3867             else
3868               {
3869                 tree name = clast_name_to_gcc (t->var, params, ivstack);
3870                 tree cst = gmp_cst_to_tree (type, t->val);
3871                 name = fold_convert (type, name);
3872                 return fold_build2 (MULT_EXPR, type, cst, name);
3873               }
3874           }
3875         else
3876           return gmp_cst_to_tree (type, t->val);
3877       }
3878
3879     case expr_red:
3880       {
3881         struct clast_reduction *r = (struct clast_reduction *) e;
3882
3883         switch (r->type)
3884           {
3885           case clast_red_sum:
3886             return clast_to_gcc_expression_red (type, PLUS_EXPR, r, params, ivstack);
3887
3888           case clast_red_min:
3889             return clast_to_gcc_expression_red (type, MIN_EXPR, r, params, ivstack);
3890
3891           case clast_red_max:
3892             return clast_to_gcc_expression_red (type, MAX_EXPR, r, params, ivstack);
3893
3894           default:
3895             gcc_unreachable ();
3896           }
3897         break;
3898       }
3899
3900     case expr_bin:
3901       {
3902         struct clast_binary *b = (struct clast_binary *) e;
3903         struct clast_expr *lhs = (struct clast_expr *) b->LHS;
3904         tree tl = clast_to_gcc_expression (type, lhs, params, ivstack);
3905         tree tr = gmp_cst_to_tree (type, b->RHS);
3906
3907         switch (b->type)
3908           {
3909           case clast_bin_fdiv:
3910             return fold_build2 (FLOOR_DIV_EXPR, type, tl, tr);
3911
3912           case clast_bin_cdiv:
3913             return fold_build2 (CEIL_DIV_EXPR, type, tl, tr);
3914
3915           case clast_bin_div:
3916             return fold_build2 (EXACT_DIV_EXPR, type, tl, tr);
3917
3918           case clast_bin_mod:
3919             return fold_build2 (TRUNC_MOD_EXPR, type, tl, tr);
3920
3921           default:
3922             gcc_unreachable ();
3923           }
3924       }
3925
3926     default:
3927       gcc_unreachable ();
3928     }
3929
3930   return NULL_TREE;
3931 }
3932
3933 /* Returns the type for the expression E.  */
3934
3935 static tree
3936 gcc_type_for_clast_expr (struct clast_expr *e,
3937                          VEC (name_tree, heap) *params,
3938                          loop_iv_stack ivstack)
3939 {
3940   switch (e->type)
3941     {
3942     case expr_term:
3943       {
3944         struct clast_term *t = (struct clast_term *) e;
3945
3946         if (t->var)
3947           return TREE_TYPE (clast_name_to_gcc (t->var, params, ivstack));
3948         else
3949           return NULL_TREE;
3950       }
3951
3952     case expr_red:
3953       {
3954         struct clast_reduction *r = (struct clast_reduction *) e;
3955
3956         if (r->n == 1)
3957           return gcc_type_for_clast_expr (r->elts[0], params, ivstack);
3958         else
3959           {
3960             int i;
3961             for (i = 0; i < r->n; i++)
3962               {
3963                 tree type = gcc_type_for_clast_expr (r->elts[i], params, ivstack);
3964                 if (type)
3965                   return type;
3966               }
3967             return NULL_TREE;
3968           }
3969       }
3970
3971     case expr_bin:
3972       {
3973         struct clast_binary *b = (struct clast_binary *) e;
3974         struct clast_expr *lhs = (struct clast_expr *) b->LHS;
3975         return gcc_type_for_clast_expr (lhs, params, ivstack);
3976       }
3977
3978     default:
3979       gcc_unreachable ();
3980     }
3981
3982   return NULL_TREE;
3983 }
3984
3985 /* Returns the type for the equation CLEQ.  */
3986
3987 static tree
3988 gcc_type_for_clast_eq (struct clast_equation *cleq,
3989                        VEC (name_tree, heap) *params,
3990                        loop_iv_stack ivstack)
3991 {
3992   tree type = gcc_type_for_clast_expr (cleq->LHS, params, ivstack);
3993   if (type)
3994     return type;
3995
3996   return gcc_type_for_clast_expr (cleq->RHS, params, ivstack);
3997 }
3998
3999 /* Translates a clast equation CLEQ to a tree.  */
4000
4001 static tree
4002 graphite_translate_clast_equation (scop_p scop,
4003                                    struct clast_equation *cleq,
4004                                    loop_iv_stack ivstack)
4005 {
4006   enum tree_code comp;
4007   tree type = gcc_type_for_clast_eq (cleq, SCOP_PARAMS (scop), ivstack);
4008   tree lhs = clast_to_gcc_expression (type, cleq->LHS, SCOP_PARAMS (scop), ivstack);
4009   tree rhs = clast_to_gcc_expression (type, cleq->RHS, SCOP_PARAMS (scop), ivstack);
4010
4011   if (cleq->sign == 0)
4012     comp = EQ_EXPR;
4013
4014   else if (cleq->sign > 0)
4015     comp = GE_EXPR;
4016
4017   else
4018     comp = LE_EXPR;
4019
4020   return fold_build2 (comp, type, lhs, rhs);
4021 }
4022
4023 /* Creates the test for the condition in STMT.  */
4024
4025 static tree
4026 graphite_create_guard_cond_expr (scop_p scop, struct clast_guard *stmt,
4027                                  loop_iv_stack ivstack)
4028 {
4029   tree cond = NULL;
4030   int i;
4031
4032   for (i = 0; i < stmt->n; i++)
4033     {
4034       tree eq = graphite_translate_clast_equation (scop, &stmt->eq[i], ivstack);
4035
4036       if (cond)
4037         cond = fold_build2 (TRUTH_AND_EXPR, TREE_TYPE (eq), cond, eq);
4038       else
4039         cond = eq;
4040     }
4041
4042   return cond;
4043 }
4044
4045 /* Creates a new if region corresponding to Cloog's guard.  */
4046
4047 static edge
4048 graphite_create_new_guard (scop_p scop, edge entry_edge,
4049                            struct clast_guard *stmt,
4050                            loop_iv_stack ivstack)
4051 {
4052   tree cond_expr = graphite_create_guard_cond_expr (scop, stmt, ivstack);
4053   edge exit_edge = create_empty_if_region_on_edge (entry_edge, cond_expr);
4054   return exit_edge;
4055 }
4056
4057 /* Walks a CLAST and returns the first statement in the body of a
4058    loop.  */
4059
4060 static struct clast_user_stmt *
4061 clast_get_body_of_loop (struct clast_stmt *stmt)
4062 {
4063   if (!stmt
4064       || CLAST_STMT_IS_A (stmt, stmt_user))
4065     return (struct clast_user_stmt *) stmt;
4066
4067   if (CLAST_STMT_IS_A (stmt, stmt_for))
4068     return clast_get_body_of_loop (((struct clast_for *) stmt)->body);
4069
4070   if (CLAST_STMT_IS_A (stmt, stmt_guard))
4071     return clast_get_body_of_loop (((struct clast_guard *) stmt)->then);
4072
4073   if (CLAST_STMT_IS_A (stmt, stmt_block))
4074     return clast_get_body_of_loop (((struct clast_block *) stmt)->body);
4075
4076   gcc_unreachable ();
4077 }
4078
4079 /* Returns the induction variable for the loop that gets translated to
4080    STMT.  */
4081
4082 static tree
4083 gcc_type_for_iv_of_clast_loop (struct clast_for *stmt_for)
4084 {
4085   struct clast_user_stmt *stmt = clast_get_body_of_loop ((struct clast_stmt *) stmt_for);
4086   const char *cloog_iv = stmt_for->iterator;
4087   CloogStatement *cs = stmt->statement;
4088   graphite_bb_p gbb = (graphite_bb_p) cloog_statement_usr (cs);
4089
4090   return gcc_type_for_cloog_iv (cloog_iv, gbb);
4091 }
4092
4093 /* Creates a new LOOP corresponding to Cloog's STMT.  Inserts an induction
4094    variable for the new LOOP.  New LOOP is attached to CFG starting at
4095    ENTRY_EDGE.  LOOP is inserted into the loop tree and becomes the child
4096    loop of the OUTER_LOOP.  */
4097
4098 static struct loop *
4099 graphite_create_new_loop (scop_p scop, edge entry_edge,
4100                           struct clast_for *stmt, loop_iv_stack ivstack,
4101                           loop_p outer)
4102 {
4103   tree type = gcc_type_for_iv_of_clast_loop (stmt);
4104   VEC (name_tree, heap) *params = SCOP_PARAMS (scop);
4105   tree lb = clast_to_gcc_expression (type, stmt->LB, params, ivstack);
4106   tree ub = clast_to_gcc_expression (type, stmt->UB, params, ivstack);
4107   tree stride = gmp_cst_to_tree (type, stmt->stride);
4108   tree ivvar = create_tmp_var (type, "graphiteIV");
4109   tree iv_before;
4110   loop_p loop = create_empty_loop_on_edge
4111     (entry_edge, lb, stride, ub, ivvar, &iv_before,
4112      outer ? outer : entry_edge->src->loop_father);
4113
4114   add_referenced_var (ivvar);
4115   loop_iv_stack_push_iv (ivstack, iv_before, stmt->iterator);
4116   return loop;
4117 }
4118
4119 /* Rename the SSA_NAMEs used in STMT and that appear in IVSTACK.  */
4120
4121 static void
4122 rename_variables_in_stmt (gimple stmt, htab_t map)
4123 {
4124   ssa_op_iter iter;
4125   use_operand_p use_p;
4126
4127   FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
4128     {
4129       tree use = USE_FROM_PTR (use_p);
4130       tree new_name = get_new_name_from_old_name (map, use);
4131
4132       replace_exp (use_p, new_name);
4133     }
4134
4135   update_stmt (stmt);
4136 }
4137
4138 /* Returns true if SSA_NAME is a parameter of SCOP.  */
4139
4140 static bool
4141 is_parameter (scop_p scop, tree ssa_name)
4142 {
4143   int i;
4144   VEC (name_tree, heap) *params = SCOP_PARAMS (scop);
4145   name_tree param;
4146
4147   for (i = 0; VEC_iterate (name_tree, params, i, param); i++)
4148     if (param->t == ssa_name)
4149       return true;
4150
4151   return false;
4152 }
4153
4154 /* Returns true if NAME is an induction variable.  */
4155
4156 static bool
4157 is_iv (tree name)
4158 {
4159   return gimple_code (SSA_NAME_DEF_STMT (name)) == GIMPLE_PHI;
4160 }
4161
4162 static void expand_scalar_variables_stmt (gimple, basic_block, scop_p,
4163                                           htab_t);
4164 static tree
4165 expand_scalar_variables_expr (tree, tree, enum tree_code, tree, basic_block,
4166                               scop_p, htab_t, gimple_stmt_iterator *);
4167
4168 /* Copies at GSI all the scalar computations on which the ssa_name OP0
4169    depends on in the SCOP: these are all the scalar variables used in
4170    the definition of OP0, that are defined outside BB and still in the
4171    SCOP, i.e. not a parameter of the SCOP.  The expression that is
4172    returned contains only induction variables from the generated code:
4173    MAP contains the induction variables renaming mapping, and is used
4174    to translate the names of induction variables.  */
4175
4176 static tree
4177 expand_scalar_variables_ssa_name (tree op0, basic_block bb,
4178                                   scop_p scop, htab_t map,
4179                                   gimple_stmt_iterator *gsi)
4180 {
4181   tree var0, var1, type;
4182   gimple def_stmt;
4183   enum tree_code subcode;
4184
4185   if (is_parameter (scop, op0)
4186       || is_iv (op0))
4187     return get_new_name_from_old_name (map, op0);
4188
4189   def_stmt = SSA_NAME_DEF_STMT (op0);
4190
4191   if (gimple_bb (def_stmt) == bb)
4192     {
4193       /* If the defining statement is in the basic block already
4194          we do not need to create a new expression for it, we
4195          only need to ensure its operands are expanded.  */
4196       expand_scalar_variables_stmt (def_stmt, bb, scop, map);
4197       return get_new_name_from_old_name (map, op0);
4198     }
4199   else
4200     {
4201       if (gimple_code (def_stmt) != GIMPLE_ASSIGN
4202           || !bb_in_sese_p (gimple_bb (def_stmt), SCOP_REGION (scop)))
4203         return get_new_name_from_old_name (map, op0);
4204
4205       var0 = gimple_assign_rhs1 (def_stmt);
4206       subcode = gimple_assign_rhs_code (def_stmt);
4207       var1 = gimple_assign_rhs2 (def_stmt);
4208       type = gimple_expr_type (def_stmt);
4209
4210       return expand_scalar_variables_expr (type, var0, subcode, var1, bb, scop,
4211                                            map, gsi);
4212     }
4213 }
4214
4215 /* Copies at GSI all the scalar computations on which the expression
4216    OP0 CODE OP1 depends on in the SCOP: these are all the scalar
4217    variables used in OP0 and OP1, defined outside BB and still defined
4218    in the SCOP, i.e. not a parameter of the SCOP.  The expression that
4219    is returned contains only induction variables from the generated
4220    code: MAP contains the induction variables renaming mapping, and is
4221    used to translate the names of induction variables.  */
4222
4223 static tree
4224 expand_scalar_variables_expr (tree type, tree op0, enum tree_code code,
4225                               tree op1, basic_block bb, scop_p scop,
4226                               htab_t map, gimple_stmt_iterator *gsi)
4227 {
4228   if (TREE_CODE_CLASS (code) == tcc_constant
4229       || TREE_CODE_CLASS (code) == tcc_declaration)
4230     return op0;
4231
4232   /* For data references we have to duplicate also its memory
4233      indexing.  */
4234   if (TREE_CODE_CLASS (code) == tcc_reference)
4235     {
4236       switch (code)
4237         {
4238         case INDIRECT_REF:
4239           {
4240             tree old_name = TREE_OPERAND (op0, 0);
4241             tree expr = expand_scalar_variables_ssa_name
4242               (old_name, bb, scop, map, gsi);
4243             tree new_name = force_gimple_operand_gsi (gsi, expr, true, NULL,
4244                                                       true, GSI_SAME_STMT);
4245
4246             set_symbol_mem_tag (SSA_NAME_VAR (new_name),
4247                                 symbol_mem_tag (SSA_NAME_VAR (old_name)));
4248             return fold_build1 (code, type, new_name);
4249           }
4250
4251         case ARRAY_REF:
4252           {
4253             tree op00 = TREE_OPERAND (op0, 0);
4254             tree op01 = TREE_OPERAND (op0, 1);
4255             tree op02 = TREE_OPERAND (op0, 2);
4256             tree op03 = TREE_OPERAND (op0, 3);
4257             tree base = expand_scalar_variables_expr
4258               (TREE_TYPE (op00), op00, TREE_CODE (op00), NULL, bb, scop,
4259                map, gsi);
4260             tree subscript = expand_scalar_variables_expr
4261               (TREE_TYPE (op01), op01, TREE_CODE (op01), NULL, bb, scop,
4262                map, gsi);
4263
4264             return build4 (ARRAY_REF, type, base, subscript, op02, op03);
4265           }
4266
4267         default:
4268           /* The above cases should catch everything.  */
4269           gcc_unreachable ();
4270         }
4271     }
4272
4273   if (TREE_CODE_CLASS (code) == tcc_unary)
4274     {
4275       tree op0_type = TREE_TYPE (op0);
4276       enum tree_code op0_code = TREE_CODE (op0);
4277       tree op0_expr = expand_scalar_variables_expr (op0_type, op0, op0_code,
4278                                                     NULL, bb, scop, map, gsi);
4279
4280       return fold_build1 (code, type, op0_expr);
4281     }
4282
4283   if (TREE_CODE_CLASS (code) == tcc_binary)
4284     {
4285       tree op0_type = TREE_TYPE (op0);
4286       enum tree_code op0_code = TREE_CODE (op0);
4287       tree op0_expr = expand_scalar_variables_expr (op0_type, op0, op0_code,
4288                                                     NULL, bb, scop, map, gsi);
4289       tree op1_type = TREE_TYPE (op1);
4290       enum tree_code op1_code = TREE_CODE (op1);
4291       tree op1_expr = expand_scalar_variables_expr (op1_type, op1, op1_code,
4292                                                     NULL, bb, scop, map, gsi);
4293
4294       return fold_build2 (code, type, op0_expr, op1_expr);
4295     }
4296
4297   if (code == SSA_NAME)
4298     return expand_scalar_variables_ssa_name (op0, bb, scop, map, gsi);
4299
4300   gcc_unreachable ();
4301   return NULL;
4302 }
4303
4304 /* Copies at the beginning of BB all the scalar computations on which
4305    STMT depends on in the SCOP: these are all the scalar variables used
4306    in STMT, defined outside BB and still defined in the SCOP, i.e. not a
4307    parameter of the SCOP.  The expression that is returned contains
4308    only induction variables from the generated code: MAP contains the
4309    induction variables renaming mapping, and is used to translate the
4310    names of induction variables.  */
4311
4312 static void
4313 expand_scalar_variables_stmt (gimple stmt, basic_block bb, scop_p scop,
4314                               htab_t map)
4315 {
4316   ssa_op_iter iter;
4317   use_operand_p use_p;
4318   gimple_stmt_iterator gsi = gsi_after_labels (bb);
4319
4320   FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
4321     {
4322       tree use = USE_FROM_PTR (use_p);
4323       tree type = TREE_TYPE (use);
4324       enum tree_code code = TREE_CODE (use);
4325       tree use_expr = expand_scalar_variables_expr (type, use, code, NULL, bb,
4326                                                     scop, map, &gsi);
4327       if (use_expr != use)
4328         {
4329           tree new_use =
4330             force_gimple_operand_gsi (&gsi, use_expr, true, NULL,
4331                                       true, GSI_NEW_STMT);
4332           replace_exp (use_p, new_use);
4333         }
4334     }
4335
4336   update_stmt (stmt);
4337 }
4338
4339 /* Copies at the beginning of BB all the scalar computations on which
4340    BB depends on in the SCOP: these are all the scalar variables used
4341    in BB, defined outside BB and still defined in the SCOP, i.e. not a
4342    parameter of the SCOP.  The expression that is returned contains
4343    only induction variables from the generated code: MAP contains the
4344    induction variables renaming mapping, and is used to translate the
4345    names of induction variables.  */
4346
4347 static void
4348 expand_scalar_variables (basic_block bb, scop_p scop, htab_t map)
4349 {
4350   gimple_stmt_iterator gsi;
4351
4352   for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi);)
4353     {
4354       gimple stmt = gsi_stmt (gsi);
4355       expand_scalar_variables_stmt (stmt, bb, scop, map);
4356       gsi_next (&gsi);
4357     }
4358 }
4359
4360 /* Rename all the SSA_NAMEs from block BB according to the MAP.  */
4361
4362 static void
4363 rename_variables (basic_block bb, htab_t map)
4364 {
4365   gimple_stmt_iterator gsi;
4366
4367   for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi); gsi_next (&gsi))
4368     rename_variables_in_stmt (gsi_stmt (gsi), map);
4369 }
4370
4371 /* Remove condition from BB.  */
4372
4373 static void
4374 remove_condition (basic_block bb)
4375 {
4376   gimple last = last_stmt (bb);
4377
4378   if (last && gimple_code (last) == GIMPLE_COND)
4379     {
4380       gimple_stmt_iterator gsi = gsi_last_bb (bb);
4381       gsi_remove (&gsi, true);
4382     }
4383 }
4384
4385 /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag set.  */
4386
4387 static edge
4388 get_true_edge_from_guard_bb (basic_block bb)
4389 {
4390   edge e;
4391   edge_iterator ei;
4392
4393   FOR_EACH_EDGE (e, ei, bb->succs)
4394     if (e->flags & EDGE_TRUE_VALUE)
4395       return e;
4396
4397   gcc_unreachable ();
4398   return NULL;
4399 }
4400
4401 /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag cleared.  */
4402
4403 static edge
4404 get_false_edge_from_guard_bb (basic_block bb)
4405 {
4406   edge e;
4407   edge_iterator ei;
4408
4409   FOR_EACH_EDGE (e, ei, bb->succs)
4410     if (!(e->flags & EDGE_TRUE_VALUE))
4411       return e;
4412
4413   gcc_unreachable ();
4414   return NULL;
4415 }
4416
4417 /* Inserts in MAP a tuple (OLD_NAME, NEW_NAME) for the induction
4418    variables of the loops around GBB in SCOP, i.e. GBB_LOOPS.
4419    NEW_NAME is obtained from IVSTACK.  IVSTACK has the same stack
4420    ordering as GBB_LOOPS.  */
4421
4422 static void
4423 build_iv_mapping (loop_iv_stack ivstack, htab_t map, gbb_p gbb, scop_p scop)
4424 {
4425   int i;
4426   name_tree iv;
4427   PTR *slot;
4428
4429   for (i = 0; VEC_iterate (name_tree, SCOP_OLDIVS (scop), i, iv); i++)
4430     {
4431       struct rename_map_elt tmp;
4432
4433       if (!flow_bb_inside_loop_p (iv->loop, GBB_BB (gbb)))
4434         continue;
4435
4436       tmp.old_name = iv->t;
4437       slot = htab_find_slot (map, &tmp, INSERT);
4438
4439       if (!*slot)
4440         {
4441           tree new_name = loop_iv_stack_get_iv (ivstack,
4442                                                 gbb_loop_index (gbb, iv->loop));
4443           *slot = new_rename_map_elt (iv->t, new_name);
4444         }
4445     }
4446 }
4447
4448 /* Register in MAP the tuple (old_name, new_name).  */
4449
4450 static void
4451 register_old_and_new_names (htab_t map, tree old_name, tree new_name)
4452 {
4453   struct rename_map_elt tmp;
4454   PTR *slot;
4455
4456   tmp.old_name = old_name;
4457   slot = htab_find_slot (map, &tmp, INSERT);
4458
4459   if (!*slot)
4460     *slot = new_rename_map_elt (old_name, new_name);
4461 }
4462
4463 /* Create a duplicate of the basic block BB.  NOTE: This does not
4464    preserve SSA form.  */
4465
4466 static void
4467 graphite_copy_stmts_from_block (basic_block bb, basic_block new_bb, htab_t map)
4468 {
4469   gimple_stmt_iterator gsi, gsi_tgt;
4470
4471   gsi_tgt = gsi_start_bb (new_bb);
4472   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
4473     {
4474       def_operand_p def_p;
4475       ssa_op_iter op_iter;
4476       int region;
4477       gimple stmt = gsi_stmt (gsi);
4478       gimple copy;
4479
4480       if (gimple_code (stmt) == GIMPLE_LABEL)
4481         continue;
4482
4483       /* Create a new copy of STMT and duplicate STMT's virtual
4484          operands.  */
4485       copy = gimple_copy (stmt);
4486       gsi_insert_after (&gsi_tgt, copy, GSI_NEW_STMT);
4487       mark_symbols_for_renaming (copy);
4488
4489       region = lookup_stmt_eh_region (stmt);
4490       if (region >= 0)
4491         add_stmt_to_eh_region (copy, region);
4492       gimple_duplicate_stmt_histograms (cfun, copy, cfun, stmt);
4493
4494       /* Create new names for all the definitions created by COPY and
4495          add replacement mappings for each new name.  */
4496       FOR_EACH_SSA_DEF_OPERAND (def_p, copy, op_iter, SSA_OP_DEF)
4497         {
4498           tree old_name = DEF_FROM_PTR (def_p);
4499           tree new_name = create_new_def_for (old_name, copy, def_p);
4500           register_old_and_new_names (map, old_name, new_name);
4501         }
4502     }
4503 }
4504
4505 /* Records in SCOP_LIVEOUT_RENAMES the names that are live out of
4506    the SCOP and that appear in the RENAME_MAP.  */
4507
4508 static void
4509 register_scop_liveout_renames (scop_p scop, htab_t rename_map)
4510 {
4511   int i;
4512   sese region = SCOP_REGION (scop);
4513
4514   for (i = 0; i < SESE_NUM_VER (region); i++)
4515     if (bitmap_bit_p (SESE_LIVEOUT (region), i)
4516         && is_gimple_reg (ssa_name (i)))
4517       {
4518         tree old_name = ssa_name (i);
4519         tree new_name = get_new_name_from_old_name (rename_map, old_name);
4520
4521         register_old_and_new_names (SCOP_LIVEOUT_RENAMES (scop),
4522                                     old_name, new_name);
4523       }
4524 }
4525
4526 /* Copies BB and includes in the copied BB all the statements that can
4527    be reached following the use-def chains from the memory accesses,
4528    and returns the next edge following this new block.  */
4529
4530 static edge
4531 copy_bb_and_scalar_dependences (basic_block bb, scop_p scop,
4532                                 edge next_e, htab_t map)
4533 {
4534   basic_block new_bb = split_edge (next_e);
4535
4536   next_e = single_succ_edge (new_bb);
4537   graphite_copy_stmts_from_block (bb, new_bb, map);
4538   remove_condition (new_bb);
4539   rename_variables (new_bb, map);
4540   remove_phi_nodes (new_bb);
4541   expand_scalar_variables (new_bb, scop, map);
4542   register_scop_liveout_renames (scop, map);
4543
4544   return next_e;
4545 }
4546
4547 /* Helper function for htab_traverse in insert_loop_close_phis.  */
4548
4549 static int
4550 add_loop_exit_phis (void **slot, void *s)
4551 {
4552   struct rename_map_elt *entry = (struct rename_map_elt *) *slot;
4553   tree new_name = entry->new_name;
4554   basic_block bb = (basic_block) s;
4555   gimple phi = create_phi_node (new_name, bb);
4556   tree res = create_new_def_for (gimple_phi_result (phi), phi,
4557                                  gimple_phi_result_ptr (phi));
4558
4559   add_phi_arg (phi, new_name, single_pred_edge (bb));
4560
4561   entry->new_name = res;
4562   *slot = entry;
4563   return 1;
4564 }
4565
4566 /* Iterate over the SCOP_LIVEOUT_RENAMES (SCOP) and get tuples of the
4567    form (OLD_NAME, NEW_NAME).  Insert in BB "RES = phi (NEW_NAME)",
4568    and finally register in SCOP_LIVEOUT_RENAMES (scop) the tuple
4569    (OLD_NAME, RES).  */
4570
4571 static void
4572 insert_loop_close_phis (scop_p scop, basic_block bb)
4573 {
4574   update_ssa (TODO_update_ssa);
4575   htab_traverse (SCOP_LIVEOUT_RENAMES (scop), add_loop_exit_phis, bb);
4576   update_ssa (TODO_update_ssa);
4577 }
4578
4579 /* Helper structure for htab_traverse in insert_guard_phis.  */
4580
4581 struct igp {
4582   basic_block bb;
4583   edge true_edge, false_edge;
4584   htab_t liveout_before_guard;
4585 };
4586
4587 /* Return the default name that is before the guard.  */
4588
4589 static tree
4590 default_liveout_before_guard (htab_t liveout_before_guard, tree old_name)
4591 {
4592   tree res = get_new_name_from_old_name (liveout_before_guard, old_name);
4593
4594   if (res == old_name)
4595     {
4596       if (is_gimple_reg (res))
4597         return fold_convert (TREE_TYPE (res), integer_zero_node);
4598       return gimple_default_def (cfun, res);
4599     }
4600
4601   return res;
4602 }
4603
4604 /* Helper function for htab_traverse in insert_guard_phis.  */
4605
4606 static int
4607 add_guard_exit_phis (void **slot, void *s)
4608 {
4609   struct rename_map_elt *entry = (struct rename_map_elt *) *slot;
4610   struct igp *i = (struct igp *) s;
4611   basic_block bb = i->bb;
4612   edge true_edge = i->true_edge;
4613   edge false_edge = i->false_edge;
4614   tree name1 = entry->new_name;
4615   tree name2 = default_liveout_before_guard (i->liveout_before_guard,
4616                                              entry->old_name);
4617   gimple phi = create_phi_node (name1, bb);
4618   tree res = create_new_def_for (gimple_phi_result (phi), phi,
4619                                  gimple_phi_result_ptr (phi));
4620
4621   add_phi_arg (phi, name1, true_edge);
4622   add_phi_arg (phi, name2, false_edge);
4623
4624   entry->new_name = res;
4625   *slot = entry;
4626   return 1;
4627 }
4628
4629 /* Iterate over the SCOP_LIVEOUT_RENAMES (SCOP) and get tuples of the
4630    form (OLD_NAME, NAME1).  If there is a correspondent tuple of
4631    OLD_NAME in LIVEOUT_BEFORE_GUARD, i.e. (OLD_NAME, NAME2) then
4632    insert in BB
4633
4634    | RES = phi (NAME1 (on TRUE_EDGE), NAME2 (on FALSE_EDGE))"
4635
4636    if there is no tuple for OLD_NAME in LIVEOUT_BEFORE_GUARD, insert
4637
4638    | RES = phi (NAME1 (on TRUE_EDGE),
4639    |            DEFAULT_DEFINITION of NAME1 (on FALSE_EDGE))".
4640
4641    Finally register in SCOP_LIVEOUT_RENAMES (scop) the tuple
4642    (OLD_NAME, RES).  */
4643
4644 static void
4645 insert_guard_phis (scop_p scop, basic_block bb, edge true_edge,
4646                    edge false_edge, htab_t liveout_before_guard)
4647 {
4648   struct igp i;
4649   i.bb = bb;
4650   i.true_edge = true_edge;
4651   i.false_edge = false_edge;
4652   i.liveout_before_guard = liveout_before_guard;
4653
4654   update_ssa (TODO_update_ssa);
4655   htab_traverse (SCOP_LIVEOUT_RENAMES (scop), add_guard_exit_phis, &i);
4656   update_ssa (TODO_update_ssa);
4657 }
4658
4659 /* Helper function for htab_traverse.  */
4660
4661 static int
4662 copy_renames (void **slot, void *s)
4663 {
4664   struct rename_map_elt *entry = (struct rename_map_elt *) *slot;
4665   htab_t res = (htab_t) s;
4666   tree old_name = entry->old_name;
4667   tree new_name = entry->new_name;
4668   struct rename_map_elt tmp;
4669   PTR *x;
4670
4671   tmp.old_name = old_name;
4672   x = htab_find_slot (res, &tmp, INSERT);
4673
4674   if (!*x)
4675     *x = new_rename_map_elt (old_name, new_name);
4676
4677   return 1;
4678 }
4679
4680 /* Translates a CLAST statement STMT to GCC representation in the
4681    context of a SCOP.
4682
4683    - NEXT_E is the edge where new generated code should be attached.
4684    - CONTEXT_LOOP is the loop in which the generated code will be placed
4685      (might be NULL).
4686    - IVSTACK contains the surrounding loops around the statement to be
4687      translated.
4688 */
4689
4690 static edge
4691 translate_clast (scop_p scop, struct loop *context_loop,
4692                  struct clast_stmt *stmt, edge next_e, loop_iv_stack ivstack)
4693 {
4694   if (!stmt)
4695     return next_e;
4696
4697   if (CLAST_STMT_IS_A (stmt, stmt_root))
4698     return translate_clast (scop, context_loop, stmt->next, next_e, ivstack);
4699
4700   if (CLAST_STMT_IS_A (stmt, stmt_user))
4701     {
4702       htab_t map;
4703       CloogStatement *cs = ((struct clast_user_stmt *) stmt)->statement;
4704       graphite_bb_p gbb = (graphite_bb_p) cloog_statement_usr (cs);
4705
4706       if (GBB_BB (gbb) == ENTRY_BLOCK_PTR)
4707         return next_e;
4708
4709       map = htab_create (10, rename_map_elt_info, eq_rename_map_elts, free);
4710       loop_iv_stack_patch_for_consts (ivstack, (struct clast_user_stmt *) stmt);
4711       build_iv_mapping (ivstack, map, gbb, scop);
4712       next_e = copy_bb_and_scalar_dependences (GBB_BB (gbb), scop,
4713                                                next_e, map);
4714       htab_delete (map);
4715       loop_iv_stack_remove_constants (ivstack);
4716       update_ssa (TODO_update_ssa);
4717       recompute_all_dominators ();
4718       graphite_verify ();
4719       return translate_clast (scop, context_loop, stmt->next, next_e, ivstack);
4720     }
4721
4722   if (CLAST_STMT_IS_A (stmt, stmt_for))
4723     {
4724       struct loop *loop
4725         = graphite_create_new_loop (scop, next_e, (struct clast_for *) stmt,
4726                                     ivstack, context_loop ? context_loop
4727                                     : get_loop (0));
4728       edge last_e = single_exit (loop);
4729
4730       next_e = translate_clast (scop, loop, ((struct clast_for *) stmt)->body,
4731                                 single_pred_edge (loop->latch), ivstack);
4732       redirect_edge_succ_nodup (next_e, loop->latch);
4733
4734       set_immediate_dominator (CDI_DOMINATORS, next_e->dest, next_e->src);
4735       loop_iv_stack_pop (ivstack);
4736       last_e = single_succ_edge (split_edge (last_e));
4737       insert_loop_close_phis (scop, last_e->src);
4738
4739       recompute_all_dominators ();
4740       graphite_verify ();
4741       return translate_clast (scop, context_loop, stmt->next, last_e, ivstack);
4742     }
4743
4744   if (CLAST_STMT_IS_A (stmt, stmt_guard))
4745     {
4746       htab_t liveout_before_guard = htab_create (10, rename_map_elt_info,
4747                                                  eq_rename_map_elts, free);
4748       edge last_e = graphite_create_new_guard (scop, next_e,
4749                                                ((struct clast_guard *) stmt),
4750                                                ivstack);
4751       edge true_e = get_true_edge_from_guard_bb (next_e->dest);
4752       edge false_e = get_false_edge_from_guard_bb (next_e->dest);
4753       edge exit_true_e = single_succ_edge (true_e->dest);
4754       edge exit_false_e = single_succ_edge (false_e->dest);
4755
4756       htab_traverse (SCOP_LIVEOUT_RENAMES (scop), copy_renames,
4757                      liveout_before_guard);
4758
4759       next_e = translate_clast (scop, context_loop,
4760                                 ((struct clast_guard *) stmt)->then,
4761                                 true_e, ivstack);
4762       insert_guard_phis (scop, last_e->src, exit_true_e, exit_false_e,
4763                          liveout_before_guard);
4764       htab_delete (liveout_before_guard);
4765       recompute_all_dominators ();
4766       graphite_verify ();
4767
4768       return translate_clast (scop, context_loop, stmt->next, last_e, ivstack);
4769     }
4770
4771   if (CLAST_STMT_IS_A (stmt, stmt_block))
4772     {
4773       next_e = translate_clast (scop, context_loop,
4774                                 ((struct clast_block *) stmt)->body,
4775                                 next_e, ivstack);
4776       recompute_all_dominators ();
4777       graphite_verify ();
4778       return translate_clast (scop, context_loop, stmt->next, next_e, ivstack);
4779     }
4780
4781   gcc_unreachable ();
4782 }
4783
4784 /* Free the SCATTERING domain list.  */
4785
4786 static void
4787 free_scattering (CloogDomainList *scattering)
4788 {
4789   while (scattering)
4790     {
4791       CloogDomain *dom = cloog_domain (scattering);
4792       CloogDomainList *next = cloog_next_domain (scattering);
4793
4794       cloog_domain_free (dom);
4795       free (scattering);
4796       scattering = next;
4797     }
4798 }
4799
4800 /* Build cloog program for SCoP.  */
4801
4802 static void
4803 build_cloog_prog (scop_p scop)
4804 {
4805   int i;
4806   int max_nb_loops = scop_max_loop_depth (scop);
4807   graphite_bb_p gbb;
4808   CloogLoop *loop_list = NULL;
4809   CloogBlockList *block_list = NULL;
4810   CloogDomainList *scattering = NULL;
4811   CloogProgram *prog = SCOP_PROG (scop);
4812   int nbs = 2 * max_nb_loops + 1;
4813   int *scaldims = (int *) xmalloc (nbs * (sizeof (int)));
4814
4815   cloog_program_set_nb_scattdims (prog, nbs);
4816   initialize_cloog_names (scop);
4817
4818   for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gbb); i++)
4819     {
4820       /* Build new block.  */
4821       CloogMatrix *domain = GBB_DOMAIN (gbb);
4822       CloogStatement *stmt = cloog_statement_alloc (GBB_BB (gbb)->index);
4823       CloogBlock *block = cloog_block_alloc (stmt, 0, NULL,
4824                                              nb_loops_around_gb (gbb));
4825       cloog_statement_set_usr (stmt, gbb);
4826
4827       /* Add empty domain to all bbs, which do not yet have a domain, as they
4828          are not part of any loop.  */
4829       if (domain == NULL)
4830         {
4831           domain = cloog_matrix_alloc (0, scop_nb_params (scop) + 2);
4832           GBB_DOMAIN (gbb) = domain;
4833         }
4834
4835       /* Build loop list.  */
4836       {
4837         CloogLoop *new_loop_list = cloog_loop_malloc ();
4838         cloog_loop_set_next (new_loop_list, loop_list);
4839         cloog_loop_set_domain (new_loop_list,
4840                                cloog_domain_matrix2domain (domain));
4841         cloog_loop_set_block (new_loop_list, block);
4842         loop_list = new_loop_list;
4843       }
4844
4845       /* Build block list.  */
4846       {
4847         CloogBlockList *new_block_list = cloog_block_list_malloc ();
4848
4849         cloog_block_list_set_next (new_block_list, block_list);
4850         cloog_block_list_set_block (new_block_list, block);
4851         block_list = new_block_list;
4852       }
4853
4854       /* Build scattering list.  */
4855       {
4856         /* XXX: Replace with cloog_domain_list_alloc(), when available.  */
4857         CloogDomainList *new_scattering
4858           = (CloogDomainList *) xmalloc (sizeof (CloogDomainList));
4859         CloogMatrix *scat_mat = schedule_to_scattering (gbb, nbs);
4860
4861         cloog_set_next_domain (new_scattering, scattering);
4862         cloog_set_domain (new_scattering,
4863                           cloog_domain_matrix2domain (scat_mat));
4864         scattering = new_scattering;
4865         cloog_matrix_free (scat_mat);
4866       }
4867     }
4868
4869   cloog_program_set_loop (prog, loop_list);
4870   cloog_program_set_blocklist (prog, block_list);
4871
4872   for (i = 0; i < nbs; i++)
4873     scaldims[i] = 0 ;
4874
4875   cloog_program_set_scaldims (prog, scaldims);
4876
4877   /* Extract scalar dimensions to simplify the code generation problem.  */
4878   cloog_program_extract_scalars (prog, scattering);
4879
4880   /* Apply scattering.  */
4881   cloog_program_scatter (prog, scattering);
4882   free_scattering (scattering);
4883
4884   /* Iterators corresponding to scalar dimensions have to be extracted.  */
4885   cloog_names_scalarize (cloog_program_names (prog), nbs,
4886                          cloog_program_scaldims (prog));
4887
4888   /* Free blocklist.  */
4889   {
4890     CloogBlockList *next = cloog_program_blocklist (prog);
4891
4892     while (next)
4893       {
4894         CloogBlockList *toDelete = next;
4895         next = cloog_block_list_next (next);
4896         cloog_block_list_set_next (toDelete, NULL);
4897         cloog_block_list_set_block (toDelete, NULL);
4898         cloog_block_list_free (toDelete);
4899       }
4900     cloog_program_set_blocklist (prog, NULL);
4901   }
4902 }
4903
4904 /* Return the options that will be used in GLOOG.  */
4905
4906 static CloogOptions *
4907 set_cloog_options (void)
4908 {
4909   CloogOptions *options = cloog_options_malloc ();
4910
4911   /* Change cloog output language to C.  If we do use FORTRAN instead, cloog
4912      will stop e.g. with "ERROR: unbounded loops not allowed in FORTRAN.", if
4913      we pass an incomplete program to cloog.  */
4914   options->language = LANGUAGE_C;
4915
4916   /* Enable complex equality spreading: removes dummy statements
4917      (assignments) in the generated code which repeats the
4918      substitution equations for statements.  This is useless for
4919      GLooG.  */
4920   options->esp = 1;
4921
4922   /* Enable C pretty-printing mode: normalizes the substitution
4923      equations for statements.  */
4924   options->cpp = 1;
4925
4926   /* Allow cloog to build strides with a stride width different to one.
4927      This example has stride = 4:
4928
4929      for (i = 0; i < 20; i += 4)
4930        A  */
4931   options->strides = 1;
4932
4933   /* Disable optimizations and make cloog generate source code closer to the
4934      input.  This is useful for debugging,  but later we want the optimized
4935      code.
4936
4937      XXX: We can not disable optimizations, as loop blocking is not working
4938      without them.  */
4939   if (0)
4940     {
4941       options->f = -1;
4942       options->l = INT_MAX;
4943     }
4944
4945   return options;
4946 }
4947
4948 /* Prints STMT to STDERR.  */
4949
4950 void
4951 debug_clast_stmt (struct clast_stmt *stmt)
4952 {
4953   CloogOptions *options = set_cloog_options ();
4954
4955   pprint (stderr, stmt, 0, options);
4956 }
4957
4958 /* Find the right transform for the SCOP, and return a Cloog AST
4959    representing the new form of the program.  */
4960
4961 static struct clast_stmt *
4962 find_transform (scop_p scop)
4963 {
4964   struct clast_stmt *stmt;
4965   CloogOptions *options = set_cloog_options ();
4966
4967   /* Connect new cloog prog generation to graphite.  */
4968   build_cloog_prog (scop);
4969
4970   if (dump_file && (dump_flags & TDF_DETAILS))
4971     {
4972       fprintf (dump_file, "Cloog Input [\n");
4973       cloog_program_print (dump_file, SCOP_PROG(scop));
4974       fprintf (dump_file, "]\n");
4975     }
4976
4977   SCOP_PROG (scop) = cloog_program_generate (SCOP_PROG (scop), options);
4978   stmt = cloog_clast_create (SCOP_PROG (scop), options);
4979
4980   if (dump_file && (dump_flags & TDF_DETAILS))
4981     {
4982       fprintf (dump_file, "Cloog Output[\n");
4983       pprint (dump_file, stmt, 0, options);
4984       cloog_program_dump_cloog (dump_file, SCOP_PROG (scop));
4985       fprintf (dump_file, "]\n");
4986     }
4987
4988   cloog_options_free (options);
4989   return stmt;
4990 }
4991
4992 /* Remove from the CFG the REGION.  */
4993
4994 static inline void
4995 remove_sese_region (sese region)
4996 {
4997   VEC (basic_block, heap) *bbs = NULL;
4998   basic_block entry_bb = SESE_ENTRY (region)->dest;
4999   basic_block exit_bb = SESE_EXIT (region)->dest;
5000   basic_block bb;
5001   int i;
5002
5003   VEC_safe_push (basic_block, heap, bbs, entry_bb);
5004   gather_blocks_in_sese_region (entry_bb, exit_bb, &bbs);
5005
5006   for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++)
5007     delete_basic_block (bb);
5008
5009   VEC_free (basic_block, heap, bbs);
5010 }
5011
5012 typedef struct ifsese {
5013   sese region;
5014   sese true_region;
5015   sese false_region;
5016 } *ifsese;
5017
5018 static inline edge
5019 if_region_entry (ifsese if_region)
5020 {
5021   return SESE_ENTRY (if_region->region);
5022 }
5023
5024 static inline edge
5025 if_region_exit (ifsese if_region)
5026 {
5027   return SESE_EXIT (if_region->region);
5028 }
5029
5030 static inline basic_block
5031 if_region_get_condition_block (ifsese if_region)
5032 {
5033   return if_region_entry (if_region)->dest;
5034 }
5035
5036 static inline void
5037 if_region_set_false_region (ifsese if_region, sese region)
5038 {
5039   basic_block condition = if_region_get_condition_block (if_region);
5040   edge false_edge = get_false_edge_from_guard_bb (condition);
5041   basic_block dummy = false_edge->dest;
5042   edge entry_region = SESE_ENTRY (region);
5043   edge exit_region = SESE_EXIT (region);
5044   basic_block before_region = entry_region->src;
5045   basic_block last_in_region = exit_region->src;
5046   void **slot = htab_find_slot_with_hash (current_loops->exits, exit_region,
5047                                           htab_hash_pointer (exit_region),
5048                                           NO_INSERT);
5049
5050   entry_region->flags = false_edge->flags;
5051   false_edge->flags = exit_region->flags;
5052
5053   redirect_edge_pred (entry_region, condition);
5054   redirect_edge_pred (exit_region, before_region);
5055   redirect_edge_pred (false_edge, last_in_region);
5056   redirect_edge_succ (false_edge, single_succ (dummy));
5057   delete_basic_block (dummy);
5058
5059   exit_region->flags = EDGE_FALLTHRU;
5060   recompute_all_dominators ();
5061
5062   SESE_EXIT (region) = false_edge;
5063   if_region->false_region = region;
5064
5065   if (slot)
5066     {
5067       struct loop_exit *loop_exit = GGC_CNEW (struct loop_exit);
5068
5069       memcpy (loop_exit, *((struct loop_exit **) slot), sizeof (struct loop_exit));
5070       htab_clear_slot (current_loops->exits, slot);
5071
5072       slot = htab_find_slot_with_hash (current_loops->exits, false_edge,
5073                                        htab_hash_pointer (false_edge),
5074                                        INSERT);
5075       loop_exit->e = false_edge;
5076       *slot = loop_exit;
5077       false_edge->src->loop_father->exits->next = loop_exit;
5078     }
5079 }
5080
5081 static ifsese
5082 create_if_region_on_edge (edge entry, tree condition)
5083 {
5084   edge e;
5085   edge_iterator ei;
5086   sese sese_region = GGC_NEW (struct sese);
5087   sese true_region = GGC_NEW (struct sese);
5088   sese false_region = GGC_NEW (struct sese);
5089   ifsese if_region = GGC_NEW (struct ifsese);
5090   edge exit = create_empty_if_region_on_edge (entry, condition);
5091
5092   if_region->region = sese_region;
5093   if_region->region->entry = entry;
5094   if_region->region->exit = exit;
5095
5096   FOR_EACH_EDGE (e, ei, entry->dest->succs)
5097     {
5098       if (e->flags & EDGE_TRUE_VALUE)
5099         {
5100           true_region->entry = e;
5101           true_region->exit = single_succ_edge (e->dest);
5102           if_region->true_region = true_region;
5103         }
5104       else if (e->flags & EDGE_FALSE_VALUE)
5105         {
5106           false_region->entry = e;
5107           false_region->exit = single_succ_edge (e->dest);
5108           if_region->false_region = false_region;
5109         }
5110     }
5111
5112   return if_region;
5113 }
5114
5115 /* Moves REGION in a condition expression:
5116    | if (1)
5117    |   ;
5118    | else
5119    |   REGION;
5120 */
5121
5122 static ifsese
5123 move_sese_in_condition (sese region)
5124 {
5125   basic_block pred_block = split_edge (SESE_ENTRY (region));
5126   ifsese if_region = NULL;
5127
5128   SESE_ENTRY (region) = single_succ_edge (pred_block);
5129   if_region = create_if_region_on_edge (single_pred_edge (pred_block), integer_one_node);
5130   if_region_set_false_region (if_region, region);
5131
5132   return if_region;
5133 }
5134
5135 /* Add exit phis for USE on EXIT.  */
5136
5137 static void
5138 scop_add_exit_phis_edge (basic_block exit, tree use, edge false_e, edge true_e)
5139 {
5140   gimple phi = create_phi_node (use, exit);
5141
5142   create_new_def_for (gimple_phi_result (phi), phi,
5143                       gimple_phi_result_ptr (phi));
5144   add_phi_arg (phi, use, false_e);
5145   add_phi_arg (phi, use, true_e);
5146 }
5147
5148 /* Add phi nodes for VAR that is used in LIVEIN.  Phi nodes are
5149    inserted in block BB.  */
5150
5151 static void
5152 scop_add_exit_phis_var (basic_block bb, tree var, bitmap livein,
5153                         edge false_e, edge true_e)
5154 {
5155   bitmap def;
5156   basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (var));
5157
5158   if (is_gimple_reg (var))
5159     bitmap_clear_bit (livein, def_bb->index);
5160   else
5161     bitmap_set_bit (livein, def_bb->index);
5162
5163   def = BITMAP_ALLOC (NULL);
5164   bitmap_set_bit (def, def_bb->index);
5165   compute_global_livein (livein, def);
5166   BITMAP_FREE (def);
5167
5168   scop_add_exit_phis_edge (bb, var, false_e, true_e);
5169 }
5170
5171 /* Insert in the block BB phi nodes for variables defined in REGION
5172    and used outside the REGION.  The code generation moves REGION in
5173    the else clause of an "if (1)" and generates code in the then
5174    clause that is at this point empty:
5175
5176    | if (1)
5177    |   empty;
5178    | else
5179    |   REGION;
5180 */
5181
5182 static void
5183 scop_insert_phis_for_liveouts (sese region, basic_block bb,
5184                                edge false_e, edge true_e)
5185 {
5186   unsigned i;
5187   bitmap_iterator bi;
5188
5189   update_ssa (TODO_update_ssa);
5190
5191   EXECUTE_IF_SET_IN_BITMAP (SESE_LIVEOUT (region), 0, i, bi)
5192     scop_add_exit_phis_var (bb, ssa_name (i), SESE_LIVEIN_VER (region, i),
5193                             false_e, true_e);
5194
5195   update_ssa (TODO_update_ssa);
5196 }
5197
5198 /* Get the definition of NAME before the SCOP.  Keep track of the
5199    basic blocks that have been VISITED in a bitmap.  */
5200
5201 static tree
5202 get_vdef_before_scop (scop_p scop, tree name, sbitmap visited)
5203 {
5204   unsigned i;
5205   gimple def_stmt = SSA_NAME_DEF_STMT (name);
5206   basic_block def_bb = gimple_bb (def_stmt);
5207
5208   if (!def_bb
5209       || !bb_in_sese_p (def_bb, SCOP_REGION (scop)))
5210     return name;
5211
5212   if (TEST_BIT (visited, def_bb->index))
5213     return NULL_TREE;
5214
5215   SET_BIT (visited, def_bb->index);
5216
5217   switch (gimple_code (def_stmt))
5218     {
5219     case GIMPLE_PHI:
5220       for (i = 0; i < gimple_phi_num_args (def_stmt); i++)
5221         {
5222           tree arg = gimple_phi_arg_def (def_stmt, i);
5223           tree res = get_vdef_before_scop (scop, arg, visited);
5224           if (res)
5225             return res;
5226         }
5227       return NULL_TREE;
5228
5229     default:
5230       return NULL_TREE;
5231     }
5232 }
5233
5234 /* Adjust a virtual phi node PHI that is placed at the end of the
5235    generated code for SCOP:
5236
5237    | if (1)
5238    |   generated code from REGION;
5239    | else
5240    |   REGION;
5241
5242    The FALSE_E edge comes from the original code, TRUE_E edge comes
5243    from the code generated for the SCOP.  */
5244
5245 static void
5246 scop_adjust_vphi (scop_p scop, gimple phi, edge true_e)
5247 {
5248   unsigned i;
5249
5250   gcc_assert (gimple_phi_num_args (phi) == 2);
5251
5252   for (i = 0; i < gimple_phi_num_args (phi); i++)
5253     if (gimple_phi_arg_edge (phi, i) == true_e)
5254       {
5255         tree true_arg, false_arg, before_scop_arg;
5256         sbitmap visited;
5257
5258         true_arg = gimple_phi_arg_def (phi, i);
5259         if (!SSA_NAME_IS_DEFAULT_DEF (true_arg))
5260           return;
5261
5262         false_arg = gimple_phi_arg_def (phi, i == 0 ? 1 : 0);
5263         if (SSA_NAME_IS_DEFAULT_DEF (false_arg))
5264           return;
5265
5266         visited = sbitmap_alloc (last_basic_block);
5267         sbitmap_zero (visited);
5268         before_scop_arg = get_vdef_before_scop (scop, false_arg, visited);
5269         gcc_assert (before_scop_arg != NULL_TREE);
5270         SET_PHI_ARG_DEF (phi, i, before_scop_arg);
5271         sbitmap_free (visited);
5272       }
5273 }
5274
5275 /* Adjusts the phi nodes in the block BB for variables defined in
5276    SCOP_REGION and used outside the SCOP_REGION.  The code generation
5277    moves SCOP_REGION in the else clause of an "if (1)" and generates
5278    code in the then clause:
5279
5280    | if (1)
5281    |   generated code from REGION;
5282    | else
5283    |   REGION;
5284
5285    To adjust the phi nodes after the condition, SCOP_LIVEOUT_RENAMES
5286    hash table is used: this stores for a name that is part of the
5287    LIVEOUT of SCOP_REGION its new name in the generated code.  */
5288
5289 static void
5290 scop_adjust_phis_for_liveouts (scop_p scop, basic_block bb, edge false_e,
5291                                edge true_e)
5292 {
5293   gimple_stmt_iterator si;
5294
5295   for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
5296     {
5297       unsigned i;
5298       unsigned false_i = 0;
5299       gimple phi = gsi_stmt (si);
5300
5301       if (!is_gimple_reg (PHI_RESULT (phi)))
5302         {
5303           scop_adjust_vphi (scop, phi, true_e);
5304           continue;
5305         }
5306
5307       for (i = 0; i < gimple_phi_num_args (phi); i++)
5308         if (gimple_phi_arg_edge (phi, i) == false_e)
5309           {
5310             false_i = i;
5311             break;
5312           }
5313
5314       for (i = 0; i < gimple_phi_num_args (phi); i++)
5315         if (gimple_phi_arg_edge (phi, i) == true_e)
5316           {
5317             tree old_name = gimple_phi_arg_def (phi, false_i);
5318             tree new_name = get_new_name_from_old_name
5319               (SCOP_LIVEOUT_RENAMES (scop), old_name);
5320
5321             gcc_assert (old_name != new_name);
5322             SET_PHI_ARG_DEF (phi, i, new_name);
5323           }
5324     }
5325 }
5326
5327 /* Returns the first cloog name used in EXPR.  */
5328
5329 static const char *
5330 find_cloog_iv_in_expr (struct clast_expr *expr)
5331 {
5332   struct clast_term *term = (struct clast_term *) expr;
5333
5334   if (expr->type == expr_term
5335       && !term->var)
5336     return NULL;
5337
5338   if (expr->type == expr_term)
5339     return term->var;
5340
5341   if (expr->type == expr_red)
5342     {
5343       int i;
5344       struct clast_reduction *red = (struct clast_reduction *) expr;
5345
5346       for (i = 0; i < red->n; i++)
5347         {
5348           const char *res = find_cloog_iv_in_expr ((red)->elts[i]);
5349
5350           if (res)
5351             return res;
5352         }
5353     }
5354
5355   return NULL;
5356 }
5357
5358 /* Build for a clast_user_stmt USER_STMT a map between the CLAST
5359    induction variables and the corresponding GCC old induction
5360    variables.  This information is stored on each GRAPHITE_BB.  */
5361
5362 static void
5363 compute_cloog_iv_types_1 (graphite_bb_p gbb,
5364                           struct clast_user_stmt *user_stmt)
5365 {
5366   struct clast_stmt *t;
5367   int index = 0;
5368
5369   for (t = user_stmt->substitutions; t; t = t->next, index++)
5370     {
5371       PTR *slot;
5372       struct ivtype_map_elt tmp;
5373       struct clast_expr *expr = (struct clast_expr *)
5374         ((struct clast_assignment *)t)->RHS;
5375
5376       /* Create an entry (clast_var, type).  */
5377       tmp.cloog_iv = find_cloog_iv_in_expr (expr);
5378       if (!tmp.cloog_iv)
5379         continue;
5380
5381       slot = htab_find_slot (GBB_CLOOG_IV_TYPES (gbb), &tmp, INSERT);
5382
5383       if (!*slot)
5384         {
5385           loop_p loop = gbb_loop_at_index (gbb, index);
5386           tree oldiv = oldiv_for_loop (GBB_SCOP (gbb), loop);
5387           tree type = oldiv ? TREE_TYPE (oldiv) : integer_type_node;
5388           *slot = new_ivtype_map_elt (tmp.cloog_iv, type);
5389         }
5390     }
5391 }
5392
5393 /* Walk the CLAST tree starting from STMT and build for each
5394    clast_user_stmt a map between the CLAST induction variables and the
5395    corresponding GCC old induction variables.  This information is
5396    stored on each GRAPHITE_BB.  */
5397
5398 static void
5399 compute_cloog_iv_types (struct clast_stmt *stmt)
5400 {
5401   if (!stmt)
5402     return;
5403
5404   if (CLAST_STMT_IS_A (stmt, stmt_root))
5405     goto next;
5406
5407   if (CLAST_STMT_IS_A (stmt, stmt_user))
5408     {
5409       CloogStatement *cs = ((struct clast_user_stmt *) stmt)->statement;
5410       graphite_bb_p gbb = (graphite_bb_p) cloog_statement_usr (cs);
5411       GBB_CLOOG_IV_TYPES (gbb) = htab_create (10, ivtype_map_elt_info,
5412                                               eq_ivtype_map_elts, free);
5413       compute_cloog_iv_types_1 (gbb, (struct clast_user_stmt *) stmt);
5414       goto next;
5415     }
5416
5417   if (CLAST_STMT_IS_A (stmt, stmt_for))
5418     {
5419       struct clast_stmt *s = ((struct clast_for *) stmt)->body;
5420       compute_cloog_iv_types (s);
5421       goto next;
5422     }
5423
5424   if (CLAST_STMT_IS_A (stmt, stmt_guard))
5425     {
5426       struct clast_stmt *s = ((struct clast_guard *) stmt)->then;
5427       compute_cloog_iv_types (s);
5428       goto next;
5429     }
5430
5431   if (CLAST_STMT_IS_A (stmt, stmt_block))
5432     {
5433       struct clast_stmt *s = ((struct clast_block *) stmt)->body;
5434       compute_cloog_iv_types (s);
5435       goto next;
5436     }
5437
5438   gcc_unreachable ();
5439
5440  next:
5441   compute_cloog_iv_types (stmt->next);
5442 }
5443
5444 /* GIMPLE Loop Generator: generates loops from STMT in GIMPLE form for
5445    the given SCOP.  Return true if code generation succeeded.  */
5446
5447 static bool
5448 gloog (scop_p scop, struct clast_stmt *stmt)
5449 {
5450   edge new_scop_exit_edge = NULL;
5451   VEC (iv_stack_entry_p, heap) *ivstack = VEC_alloc (iv_stack_entry_p, heap,
5452                                                      10);
5453   loop_p context_loop;
5454   ifsese if_region = NULL;
5455
5456   recompute_all_dominators ();
5457   graphite_verify ();
5458   if_region = move_sese_in_condition (SCOP_REGION (scop));
5459   sese_build_livein_liveouts (SCOP_REGION (scop));
5460   scop_insert_phis_for_liveouts (SCOP_REGION (scop),
5461                                  if_region->region->exit->src,
5462                                  if_region->false_region->exit,
5463                                  if_region->true_region->exit);
5464   recompute_all_dominators ();
5465   graphite_verify ();
5466   context_loop = SESE_ENTRY (SCOP_REGION (scop))->src->loop_father;
5467   compute_cloog_iv_types (stmt);
5468
5469   new_scop_exit_edge = translate_clast (scop, context_loop, stmt,
5470                                         if_region->true_region->entry,
5471                                         &ivstack);
5472   free_loop_iv_stack (&ivstack);
5473   cloog_clast_free (stmt);
5474
5475   graphite_verify ();
5476   scop_adjust_phis_for_liveouts (scop,
5477                                  if_region->region->exit->src,
5478                                  if_region->false_region->exit,
5479                                  if_region->true_region->exit);
5480
5481   recompute_all_dominators ();
5482   graphite_verify ();
5483   return true;
5484 }
5485
5486 /* Returns the number of data references in SCOP.  */
5487
5488 static int
5489 nb_data_refs_in_scop (scop_p scop)
5490 {
5491   int i;
5492   graphite_bb_p gbb;
5493   int res = 0;
5494
5495   for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gbb); i++)
5496     res += VEC_length (data_reference_p, GBB_DATA_REFS (gbb));
5497
5498   return res;
5499 }
5500
5501 /* Move the loop at index LOOP and insert it before index NEW_LOOP_POS.
5502    This transformartion is only valid, if the loop nest between i and k is
5503    perfectly nested. Therefore we do not need to change the static schedule.
5504
5505    Example:
5506
5507    for (i = 0; i < 50; i++)
5508      for (j ...)
5509        for (k = 5; k < 100; k++)
5510          A
5511
5512    To move k before i use:
5513
5514    graphite_trans_bb_move_loop (A, 2, 0)
5515
5516    for (k = 5; k < 100; k++)
5517      for (i = 0; i < 50; i++)
5518        for (j ...)
5519          A
5520
5521    And to move k back:
5522
5523    graphite_trans_bb_move_loop (A, 0, 2)
5524
5525    This function does not check the validity of interchanging loops.
5526    This should be checked before calling this function.  */
5527
5528 static void
5529 graphite_trans_bb_move_loop (graphite_bb_p gb, int loop,
5530                              int new_loop_pos)
5531 {
5532   CloogMatrix *domain = GBB_DOMAIN (gb);
5533   int row, j;
5534   loop_p tmp_loop_p;
5535
5536   gcc_assert (loop < gbb_nb_loops (gb)
5537               && new_loop_pos < gbb_nb_loops (gb));
5538
5539   /* Update LOOPS vector.  */
5540   tmp_loop_p = VEC_index (loop_p, GBB_LOOPS (gb), loop);
5541   VEC_ordered_remove (loop_p, GBB_LOOPS (gb), loop);
5542   VEC_safe_insert (loop_p, heap, GBB_LOOPS (gb), new_loop_pos, tmp_loop_p);
5543
5544   /* Move the domain columns.  */
5545   if (loop < new_loop_pos)
5546     for (row = 0; row < domain->NbRows; row++)
5547       {
5548         Value tmp;
5549         value_init (tmp);
5550         value_assign (tmp, domain->p[row][loop + 1]);
5551
5552         for (j = loop ; j < new_loop_pos - 1; j++)
5553           value_assign (domain->p[row][j + 1], domain->p[row][j + 2]);
5554
5555         value_assign (domain->p[row][new_loop_pos], tmp);
5556         value_clear (tmp);
5557       }
5558   else
5559     for (row = 0; row < domain->NbRows; row++)
5560       {
5561         Value tmp;
5562         value_init (tmp);
5563         value_assign (tmp, domain->p[row][loop + 1]);
5564
5565         for (j = loop ; j > new_loop_pos; j--)
5566           value_assign (domain->p[row][j + 1], domain->p[row][j]);
5567
5568         value_assign (domain->p[row][new_loop_pos + 1], tmp);
5569         value_clear (tmp);
5570       }
5571 }
5572
5573 /* Get the index of the column representing constants in the DOMAIN
5574    matrix.  */
5575
5576 static int
5577 const_column_index (CloogMatrix *domain)
5578 {
5579   return domain->NbColumns - 1;
5580 }
5581
5582
5583 /* Get the first index that is positive or negative, determined
5584    following the value of POSITIVE, in matrix DOMAIN in COLUMN.  */
5585
5586 static int
5587 get_first_matching_sign_row_index (CloogMatrix *domain, int column,
5588                                    bool positive)
5589 {
5590   int row;
5591
5592   for (row = 0; row < domain->NbRows; row++)
5593     {
5594       int val = value_get_si (domain->p[row][column]);
5595
5596       if (val > 0 && positive)
5597         return row;
5598
5599       else if (val < 0 && !positive)
5600         return row;
5601     }
5602
5603   gcc_unreachable ();
5604 }
5605
5606 /* Get the lower bound of COLUMN in matrix DOMAIN.  */
5607
5608 static int
5609 get_lower_bound_row (CloogMatrix *domain, int column)
5610 {
5611   return get_first_matching_sign_row_index (domain, column, true);
5612 }
5613
5614 /* Get the upper bound of COLUMN in matrix DOMAIN.  */
5615
5616 static int
5617 get_upper_bound_row (CloogMatrix *domain, int column)
5618 {
5619   return get_first_matching_sign_row_index (domain, column, false);
5620 }
5621
5622 /* Copies the OLD_ROW constraint from OLD_DOMAIN to the NEW_DOMAIN at
5623    row NEW_ROW.  */
5624
5625 static void
5626 copy_constraint (CloogMatrix *old_domain, CloogMatrix *new_domain,
5627                  int old_row, int new_row)
5628 {
5629   int i;
5630
5631   gcc_assert (old_domain->NbColumns == new_domain->NbColumns
5632               && old_row < old_domain->NbRows
5633               && new_row < new_domain->NbRows);
5634
5635   for (i = 0; i < old_domain->NbColumns; i++)
5636     value_assign (new_domain->p[new_row][i], old_domain->p[old_row][i]);
5637 }
5638
5639 /* Swap coefficients of variables X and Y on row R.   */
5640
5641 static void
5642 swap_constraint_variables (CloogMatrix *domain,
5643                            int r, int x, int y)
5644 {
5645   value_swap (domain->p[r][x], domain->p[r][y]);
5646 }
5647
5648 /* Scale by X the coefficient C of constraint at row R in DOMAIN.  */
5649
5650 static void
5651 scale_constraint_variable (CloogMatrix *domain,
5652                            int r, int c, int x)
5653 {
5654   Value strip_size_value;
5655   value_init (strip_size_value);
5656   value_set_si (strip_size_value, x);
5657   value_multiply (domain->p[r][c], domain->p[r][c], strip_size_value);
5658   value_clear (strip_size_value);
5659 }
5660
5661 /* Strip mines the loop of BB at the position LOOP_DEPTH with STRIDE.
5662    Always valid, but not always a performance improvement.  */
5663
5664 static void
5665 graphite_trans_bb_strip_mine (graphite_bb_p gb, int loop_depth, int stride)
5666 {
5667   int row, col;
5668
5669   CloogMatrix *domain = GBB_DOMAIN (gb);
5670   CloogMatrix *new_domain = cloog_matrix_alloc (domain->NbRows + 3,
5671                                                 domain->NbColumns + 1);
5672
5673   int col_loop_old = loop_depth + 2;
5674   int col_loop_strip = col_loop_old - 1;
5675
5676   gcc_assert (loop_depth <= gbb_nb_loops (gb) - 1);
5677
5678   VEC_safe_insert (loop_p, heap, GBB_LOOPS (gb), loop_depth, NULL);
5679
5680   GBB_DOMAIN (gb) = new_domain;
5681
5682   for (row = 0; row < domain->NbRows; row++)
5683     for (col = 0; col < domain->NbColumns; col++)
5684       if (col <= loop_depth)
5685         value_assign (new_domain->p[row][col], domain->p[row][col]);
5686       else
5687         value_assign (new_domain->p[row][col + 1], domain->p[row][col]);
5688
5689   row = domain->NbRows;
5690
5691   /* Lower bound of the outer stripped loop.  */
5692   copy_constraint (new_domain, new_domain,
5693                    get_lower_bound_row (new_domain, col_loop_old), row);
5694   swap_constraint_variables (new_domain, row, col_loop_old, col_loop_strip);
5695   row++;
5696
5697   /* Upper bound of the outer stripped loop.  */
5698   copy_constraint (new_domain, new_domain,
5699                    get_upper_bound_row (new_domain, col_loop_old), row);
5700   swap_constraint_variables (new_domain, row, col_loop_old, col_loop_strip);
5701   scale_constraint_variable (new_domain, row, col_loop_strip, stride);
5702   row++;
5703
5704   /* Lower bound of a tile starts at "stride * outer_iv".  */
5705   row = get_lower_bound_row (new_domain, col_loop_old);
5706   value_set_si (new_domain->p[row][0], 1);
5707   value_set_si (new_domain->p[row][const_column_index (new_domain)], 0);
5708   value_set_si (new_domain->p[row][col_loop_old], 1);
5709   value_set_si (new_domain->p[row][col_loop_strip], -1 * stride);
5710
5711   /* Upper bound of a tile stops at "stride * outer_iv + stride - 1",
5712      or at the old upper bound that is not modified.  */
5713   row = new_domain->NbRows - 1;
5714   value_set_si (new_domain->p[row][0], 1);
5715   value_set_si (new_domain->p[row][col_loop_old], -1);
5716   value_set_si (new_domain->p[row][col_loop_strip], stride);
5717   value_set_si (new_domain->p[row][const_column_index (new_domain)],
5718                 stride - 1);
5719
5720   cloog_matrix_free (domain);
5721
5722   /* Update static schedule.  */
5723   {
5724     int i;
5725     int nb_loops = gbb_nb_loops (gb);
5726     lambda_vector new_schedule = lambda_vector_new (nb_loops + 1);
5727
5728     for (i = 0; i <= loop_depth; i++)
5729       new_schedule[i] = GBB_STATIC_SCHEDULE (gb)[i];
5730
5731     for (i = loop_depth + 1; i <= nb_loops - 2; i++)
5732       new_schedule[i + 2] = GBB_STATIC_SCHEDULE (gb)[i];
5733
5734     GBB_STATIC_SCHEDULE (gb) = new_schedule;
5735   }
5736 }
5737
5738 /* Returns true when the strip mining of LOOP_INDEX by STRIDE is
5739    profitable or undecidable.  GB is the statement around which the
5740    loops will be strip mined.  */
5741
5742 static bool
5743 strip_mine_profitable_p (graphite_bb_p gb, int stride,
5744                          int loop_index)
5745 {
5746   bool res = true;
5747   edge exit = NULL;
5748   tree niter;
5749   loop_p loop;
5750   long niter_val;
5751
5752   loop = VEC_index (loop_p, GBB_LOOPS (gb), loop_index);
5753   exit = single_exit (loop);
5754
5755   niter = find_loop_niter (loop, &exit);
5756   if (niter == chrec_dont_know
5757       || TREE_CODE (niter) != INTEGER_CST)
5758     return true;
5759
5760   niter_val = int_cst_value (niter);
5761
5762   if (niter_val < stride)
5763     {
5764       res = false;
5765       if (dump_file && (dump_flags & TDF_DETAILS))
5766         {
5767           fprintf (dump_file, "\nStrip Mining is not profitable for loop %d:",
5768                    loop->num);
5769           fprintf (dump_file, "number of iterations is too low.\n");
5770         }
5771     }
5772
5773   return res;
5774 }
5775
5776 /* Determines when the interchange of LOOP_A and LOOP_B belonging to
5777    SCOP is legal.  DEPTH is the number of loops around.  */
5778
5779 static bool
5780 is_interchange_valid (scop_p scop, int loop_a, int loop_b, int depth)
5781 {
5782   bool res;
5783   VEC (ddr_p, heap) *dependence_relations;
5784   VEC (data_reference_p, heap) *datarefs;
5785
5786   struct loop *nest = VEC_index (loop_p, SCOP_LOOP_NEST (scop), loop_a);
5787   lambda_trans_matrix trans;
5788
5789   gcc_assert (loop_a < loop_b);
5790
5791   dependence_relations = VEC_alloc (ddr_p, heap, 10 * 10);
5792   datarefs = VEC_alloc (data_reference_p, heap, 10);
5793
5794   if (!compute_data_dependences_for_loop (nest, true, &datarefs,
5795                                           &dependence_relations))
5796     return false;
5797
5798   if (dump_file && (dump_flags & TDF_DETAILS))
5799     dump_ddrs (dump_file, dependence_relations);
5800
5801   trans = lambda_trans_matrix_new (depth, depth);
5802   lambda_matrix_id (LTM_MATRIX (trans), depth);
5803
5804   lambda_matrix_row_exchange (LTM_MATRIX (trans), 0, loop_b - loop_a);
5805
5806   if (!lambda_transform_legal_p (trans, depth, dependence_relations))
5807     {
5808       lambda_matrix_row_exchange (LTM_MATRIX (trans), 0, loop_b - loop_a);
5809       res = false;
5810     }
5811   else
5812     res = true;
5813
5814   free_dependence_relations (dependence_relations);
5815   free_data_refs (datarefs);
5816   return res;
5817 }
5818
5819 /* Loop block the LOOPS innermost loops of GB with stride size STRIDE.
5820
5821    Example
5822
5823    for (i = 0; i <= 50; i++=4)
5824      for (k = 0; k <= 100; k++=4)
5825        for (l = 0; l <= 200; l++=4)
5826          A
5827
5828    To strip mine the two inner most loops with stride = 4 call:
5829
5830    graphite_trans_bb_block (A, 4, 2)
5831
5832    for (i = 0; i <= 50; i++)
5833      for (kk = 0; kk <= 100; kk+=4)
5834        for (ll = 0; ll <= 200; ll+=4)
5835          for (k = kk; k <= min (100, kk + 3); k++)
5836            for (l = ll; l <= min (200, ll + 3); l++)
5837              A
5838 */
5839
5840 static bool
5841 graphite_trans_bb_block (graphite_bb_p gb, int stride, int loops)
5842 {
5843   int i, j;
5844   int nb_loops = gbb_nb_loops (gb);
5845   int start = nb_loops - loops;
5846   scop_p scop = GBB_SCOP (gb);
5847
5848   gcc_assert (scop_contains_loop (scop, gbb_loop (gb)));
5849
5850   for (i = start ; i < nb_loops; i++)
5851     for (j = i + 1; j < nb_loops; j++)
5852       if (!is_interchange_valid (scop, i, j, nb_loops))
5853         {
5854           if (dump_file && (dump_flags & TDF_DETAILS))
5855             fprintf (dump_file,
5856                      "\nInterchange not valid for loops %d and %d:\n", i, j);
5857           return false;
5858         }
5859       else if (dump_file && (dump_flags & TDF_DETAILS))
5860         fprintf (dump_file,
5861                  "\nInterchange valid for loops %d and %d:\n", i, j);
5862
5863   /* Check if strip mining is profitable for every loop.  */
5864   for (i = 0; i < nb_loops - start; i++)
5865     if (!strip_mine_profitable_p (gb, stride, start + i))
5866       return false;
5867
5868   /* Strip mine loops.  */
5869   for (i = 0; i < nb_loops - start; i++)
5870     graphite_trans_bb_strip_mine (gb, start + 2 * i, stride);
5871
5872   /* Interchange loops.  */
5873   for (i = 1; i < nb_loops - start; i++)
5874     graphite_trans_bb_move_loop (gb, start + 2 * i, start + i);
5875
5876   if (dump_file && (dump_flags & TDF_DETAILS))
5877     fprintf (dump_file, "\nLoops containing BB %d will be loop blocked.\n",
5878              GBB_BB (gb)->index);
5879
5880   return true;
5881 }
5882
5883 /* Loop block LOOPS innermost loops of a loop nest.  BBS represent the
5884    basic blocks that belong to the loop nest to be blocked.  */
5885
5886 static bool
5887 graphite_trans_loop_block (VEC (graphite_bb_p, heap) *bbs, int loops)
5888 {
5889   graphite_bb_p gb;
5890   int i;
5891   bool transform_done = false;
5892
5893   /* TODO: - Calculate the stride size automatically.  */
5894   int stride_size = 51;
5895
5896   for (i = 0; VEC_iterate (graphite_bb_p, bbs, i, gb); i++)
5897     transform_done |= graphite_trans_bb_block (gb, stride_size, loops);
5898
5899   return transform_done;
5900 }
5901
5902 /* Loop block all basic blocks of SCOP.  Return false when the
5903    transform is not performed.  */
5904
5905 static bool
5906 graphite_trans_scop_block (scop_p scop)
5907 {
5908   graphite_bb_p gb;
5909   int i, j;
5910   int last_nb_loops;
5911   int nb_loops;
5912   bool perfect = true;
5913   bool transform_done = false;
5914
5915   VEC (graphite_bb_p, heap) *bbs = VEC_alloc (graphite_bb_p, heap, 3);
5916   int max_schedule = scop_max_loop_depth (scop) + 1;
5917   lambda_vector last_schedule = lambda_vector_new (max_schedule);
5918
5919   if (VEC_length (graphite_bb_p, SCOP_BBS (scop)) == 0)
5920     return false;
5921
5922   /* Get the data of the first bb.  */
5923   gb = VEC_index (graphite_bb_p, SCOP_BBS (scop), 0);
5924   last_nb_loops = gbb_nb_loops (gb);
5925   lambda_vector_copy (GBB_STATIC_SCHEDULE (gb), last_schedule,
5926                       last_nb_loops + 1);
5927   VEC_safe_push (graphite_bb_p, heap, bbs, gb);
5928
5929   for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
5930     {
5931       /* We did the first bb before.  */
5932       if (i == 0)
5933         continue;
5934
5935       nb_loops = gbb_nb_loops (gb);
5936
5937       /* If the number of loops is unchanged and only the last element of the
5938          schedule changes, we stay in the loop nest.  */
5939       if (nb_loops == last_nb_loops
5940           && (last_schedule [nb_loops + 1]
5941               != GBB_STATIC_SCHEDULE (gb)[nb_loops + 1]))
5942         {
5943           VEC_safe_push (graphite_bb_p, heap, bbs, gb);
5944           continue;
5945         }
5946
5947       /* Otherwise, we left the innermost loop. So check, if the last bb was in
5948          a perfect loop nest and how many loops are contained in this perfect
5949          loop nest.
5950
5951          Count the number of zeros from the end of the schedule. They are the
5952          number of surrounding loops.
5953
5954          Example:
5955          last_bb  2 3 2 0 0 0 0 3
5956          bb       2 4 0
5957          <------  j = 4
5958
5959          last_bb  2 3 2 0 0 0 0 3
5960          bb       2 3 2 0 1
5961          <--  j = 2
5962
5963          If there is no zero, there were other bbs in outer loops and the loop
5964          nest is not perfect.  */
5965       for (j = last_nb_loops - 1; j >= 0; j--)
5966         {
5967           if (last_schedule [j] != 0
5968               || (j <= nb_loops && GBB_STATIC_SCHEDULE (gb)[j] == 1))
5969             {
5970               j--;
5971               break;
5972             }
5973         }
5974
5975       j++;
5976
5977       /* Found perfect loop nest.  */
5978       if (perfect && last_nb_loops - j >= 2)
5979         transform_done |= graphite_trans_loop_block (bbs, last_nb_loops - j);
5980
5981       /* Check if we start with a new loop.
5982
5983          Example:
5984
5985          last_bb  2 3 2 0 0 0 0 3
5986          bb       2 3 2 0 0 1 0
5987
5988          Here we start with the loop "2 3 2 0 0 1"
5989
5990          last_bb  2 3 2 0 0 0 0 3
5991          bb       2 3 2 0 0 1
5992
5993          But here not, so the loop nest can never be perfect.  */
5994
5995       perfect = (GBB_STATIC_SCHEDULE (gb)[nb_loops] == 0);
5996
5997       /* Update the last_bb infos.  We do not do that for the bbs in the same
5998          loop, as the data we use is not changed.  */
5999       last_nb_loops = nb_loops;
6000       lambda_vector_copy (GBB_STATIC_SCHEDULE (gb), last_schedule,
6001                           nb_loops + 1);
6002       VEC_truncate (graphite_bb_p, bbs, 0);
6003       VEC_safe_push (graphite_bb_p, heap, bbs, gb);
6004     }
6005
6006   /* Check if the last loop nest was perfect.  It is the same check as above,
6007      but the comparison with the next bb is missing.  */
6008   for (j = last_nb_loops - 1; j >= 0; j--)
6009     if (last_schedule [j] != 0)
6010       {
6011         j--;
6012         break;
6013       }
6014
6015   j++;
6016
6017   /* Found perfect loop nest.  */
6018   if (last_nb_loops - j >= 2)
6019     transform_done |= graphite_trans_loop_block (bbs, last_nb_loops - j);
6020   VEC_free (graphite_bb_p, heap, bbs);
6021
6022   return transform_done;
6023 }
6024
6025 /* Apply graphite transformations to all the basic blocks of SCOP.  */
6026
6027 static bool
6028 graphite_apply_transformations (scop_p scop)
6029 {
6030   bool transform_done = false;
6031
6032   /* Sort the list of bbs.  Keep them always sorted.  */
6033   graphite_sort_gbbs (scop);
6034
6035   if (flag_loop_block)
6036     transform_done = graphite_trans_scop_block (scop);
6037
6038   /* Generate code even if we did not apply any real transformation.
6039      This also allows to check the performance for the identity
6040      transformation: GIMPLE -> GRAPHITE -> GIMPLE
6041      Keep in mind that CLooG optimizes in control, so the loop structure
6042      may change, even if we only use -fgraphite-identity.  */
6043   if (flag_graphite_identity)
6044     transform_done = true;
6045
6046   return transform_done;
6047 }
6048
6049 /* We limit all SCoPs to SCoPs, that are completely surrounded by a loop.
6050
6051    Example:
6052
6053    for (i      |
6054      {         |
6055        for (j  |  SCoP 1
6056        for (k  |
6057      }         |
6058
6059    * SCoP frontier, as this line is not surrounded by any loop. *
6060
6061    for (l      |  SCoP 2
6062
6063    This is necessary as scalar evolution and parameter detection need a
6064    outermost loop to initialize parameters correctly.
6065
6066    TODO: FIX scalar evolution and parameter detection to allow more flexible
6067          SCoP frontiers.  */
6068
6069 static void
6070 limit_scops (void)
6071 {
6072   VEC (sd_region, heap) *tmp_scops = VEC_alloc (sd_region, heap, 3);
6073
6074   int i;
6075   scop_p scop;
6076
6077   for (i = 0; VEC_iterate (scop_p, current_scops, i, scop); i++)
6078     {
6079       int j;
6080       loop_p loop;
6081       build_scop_bbs (scop);
6082
6083       if (!build_scop_loop_nests (scop))
6084         continue;
6085
6086       for (j = 0; VEC_iterate (loop_p, SCOP_LOOP_NEST (scop), j, loop); j++)
6087         if (!loop_in_sese_p (loop_outer (loop), SCOP_REGION (scop)))
6088           {
6089             sd_region open_scop;
6090             open_scop.entry = loop->header;
6091             open_scop.exit = single_exit (loop)->dest;
6092             VEC_safe_push (sd_region, heap, tmp_scops, &open_scop);
6093           }
6094     }
6095
6096   free_scops (current_scops);
6097   current_scops = VEC_alloc (scop_p, heap, 3);
6098
6099   create_sese_edges (tmp_scops);
6100   build_graphite_scops (tmp_scops);
6101   VEC_free (sd_region, heap, tmp_scops);
6102 }
6103
6104 /* Perform a set of linear transforms on the loops of the current
6105    function.  */
6106
6107 void
6108 graphite_transform_loops (void)
6109 {
6110   int i;
6111   scop_p scop;
6112   bool transform_done = false;
6113
6114   if (number_of_loops () <= 1)
6115     return;
6116
6117   current_scops = VEC_alloc (scop_p, heap, 3);
6118   recompute_all_dominators ();
6119
6120   if (dump_file && (dump_flags & TDF_DETAILS))
6121     fprintf (dump_file, "Graphite loop transformations \n");
6122
6123   initialize_original_copy_tables ();
6124   cloog_initialize ();
6125   build_scops ();
6126   limit_scops ();
6127
6128   if (dump_file && (dump_flags & TDF_DETAILS))
6129     fprintf (dump_file, "\nnumber of SCoPs: %d\n",
6130              VEC_length (scop_p, current_scops));
6131
6132   for (i = 0; VEC_iterate (scop_p, current_scops, i, scop); i++)
6133     {
6134       build_scop_bbs (scop);
6135       if (!build_scop_loop_nests (scop))
6136         continue;
6137
6138       build_bb_loops (scop);
6139
6140       if (!build_scop_conditions (scop))
6141         continue;
6142
6143       find_scop_parameters (scop);
6144       build_scop_context (scop);
6145
6146       if (dump_file && (dump_flags & TDF_DETAILS))
6147         {
6148           fprintf (dump_file, "\n(In SCoP %d:\n", i);
6149           fprintf (dump_file, "\nnumber of bbs: %d\n",
6150                    VEC_length (graphite_bb_p, SCOP_BBS (scop)));
6151           fprintf (dump_file, "\nnumber of loops: %d)\n",
6152                    VEC_length (loop_p, SCOP_LOOP_NEST (scop)));
6153         }
6154
6155       if (!build_scop_iteration_domain (scop))
6156         continue;
6157
6158       add_conditions_to_constraints (scop);
6159       build_scop_canonical_schedules (scop);
6160
6161       build_scop_data_accesses (scop);
6162       build_scop_dynamic_schedules (scop);
6163
6164       if (dump_file && (dump_flags & TDF_DETAILS))
6165         {
6166           int nbrefs = nb_data_refs_in_scop (scop);
6167           fprintf (dump_file, "\nnumber of data refs: %d\n", nbrefs);
6168         }
6169
6170       if (graphite_apply_transformations (scop))
6171         transform_done = gloog (scop, find_transform (scop));
6172 #ifdef ENABLE_CHECKING
6173       else
6174         {
6175           struct clast_stmt *stmt = find_transform (scop);
6176           cloog_clast_free (stmt);
6177         }
6178 #endif
6179     }
6180
6181   /* Cleanup.  */
6182   if (transform_done)
6183     cleanup_tree_cfg ();
6184
6185   free_scops (current_scops);
6186   cloog_finalize ();
6187   free_original_copy_tables ();
6188 }
6189
6190 #else /* If Cloog is not available: #ifndef HAVE_cloog.  */
6191
6192 void
6193 graphite_transform_loops (void)
6194 {
6195   sorry ("Graphite loop optimizations cannot be used");
6196 }
6197
6198 #endif