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, phi, 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
2386   gcc_assert (number_of_iterations_exit (loop, exit, &niter, false));
2387   nit = force_gimple_operand (unshare_expr (niter.niter), &stmts, true,
2388                               NULL_TREE);
2389   if (stmts)
2390     gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
2391
2392   /* One IV per loop.  */
2393   if (nb_reductions_in_loop (loop) > 0)
2394     return NULL_TREE;
2395
2396   return canonicalize_loop_ivs (loop, NULL, nit);
2397 }
2398
2399 /* Record LOOP as occuring in SCOP.  Returns true when the operation
2400    was successful.  */
2401
2402 static bool
2403 scop_record_loop (scop_p scop, loop_p loop)
2404 {
2405   tree induction_var;
2406   name_tree oldiv;
2407
2408   if (bitmap_bit_p (SCOP_LOOPS (scop), loop->num))
2409     return true;
2410
2411   bitmap_set_bit (SCOP_LOOPS (scop), loop->num);
2412   VEC_safe_push (loop_p, heap, SCOP_LOOP_NEST (scop), loop);
2413
2414   induction_var = graphite_loop_normal_form (loop);
2415   if (!induction_var)
2416     return false;
2417
2418   oldiv = XNEW (struct name_tree);
2419   oldiv->t = induction_var;
2420   oldiv->name = get_name (SSA_NAME_VAR (oldiv->t));
2421   oldiv->loop = loop;
2422   VEC_safe_push (name_tree, heap, SCOP_OLDIVS (scop), oldiv);
2423   return true;
2424 }
2425
2426 /* Build the loop nests contained in SCOP.  Returns true when the
2427    operation was successful.  */
2428
2429 static bool
2430 build_scop_loop_nests (scop_p scop)
2431 {
2432   unsigned i;
2433   basic_block bb;
2434   struct loop *loop0, *loop1;
2435
2436   FOR_EACH_BB (bb)
2437     if (bb_in_sese_p (bb, SCOP_REGION (scop)))
2438       {
2439         struct loop *loop = bb->loop_father;
2440
2441         /* Only add loops if they are completely contained in the SCoP.  */
2442         if (loop->header == bb
2443             && bb_in_sese_p (loop->latch, SCOP_REGION (scop)))
2444           {
2445             if (!scop_record_loop (scop, loop))
2446               return false;
2447           }
2448       }
2449
2450   /* Make sure that the loops in the SCOP_LOOP_NEST are ordered.  It
2451      can be the case that an inner loop is inserted before an outer
2452      loop.  To avoid this, semi-sort once.  */
2453   for (i = 0; VEC_iterate (loop_p, SCOP_LOOP_NEST (scop), i, loop0); i++)
2454     {
2455       if (VEC_length (loop_p, SCOP_LOOP_NEST (scop)) == i + 1)
2456         break;
2457
2458       loop1 = VEC_index (loop_p, SCOP_LOOP_NEST (scop), i + 1);
2459       if (loop0->num > loop1->num)
2460         {
2461           VEC_replace (loop_p, SCOP_LOOP_NEST (scop), i, loop1);
2462           VEC_replace (loop_p, SCOP_LOOP_NEST (scop), i + 1, loop0);
2463         }
2464     }
2465
2466   return true;
2467 }
2468
2469 /* Calculate the number of loops around LOOP in the SCOP.  */
2470
2471 static inline int
2472 nb_loops_around_loop_in_scop (struct loop *l, scop_p scop)
2473 {
2474   int d = 0;
2475
2476   for (; loop_in_sese_p (l, SCOP_REGION (scop)); d++, l = loop_outer (l));
2477
2478   return d;
2479 }
2480
2481 /* Calculate the number of loops around GB in the current SCOP.  */
2482
2483 int
2484 nb_loops_around_gb (graphite_bb_p gb)
2485 {
2486   return nb_loops_around_loop_in_scop (gbb_loop (gb), GBB_SCOP (gb));
2487 }
2488
2489 /* Returns the dimensionality of an enclosing loop iteration domain
2490    with respect to enclosing SCoP for a given data reference REF.  The
2491    returned dimensionality is homogeneous (depth of loop nest + number
2492    of SCoP parameters + const).  */
2493
2494 int
2495 ref_nb_loops (data_reference_p ref)
2496 {
2497   loop_p loop = loop_containing_stmt (DR_STMT (ref));
2498   scop_p scop = DR_SCOP (ref);
2499
2500   return nb_loops_around_loop_in_scop (loop, scop) + scop_nb_params (scop) + 2;
2501 }
2502
2503 /* Build dynamic schedules for all the BBs. */
2504
2505 static void
2506 build_scop_dynamic_schedules (scop_p scop)
2507 {
2508   int i, dim, loop_num, row, col;
2509   graphite_bb_p gb;
2510
2511   for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
2512     {
2513       loop_num = GBB_BB (gb)->loop_father->num;
2514
2515       if (loop_num != 0)
2516         {
2517           dim = nb_loops_around_gb (gb);
2518           GBB_DYNAMIC_SCHEDULE (gb) = cloog_matrix_alloc (dim, dim);
2519
2520           for (row = 0; row < GBB_DYNAMIC_SCHEDULE (gb)->NbRows; row++)
2521             for (col = 0; col < GBB_DYNAMIC_SCHEDULE (gb)->NbColumns; col++)
2522               if (row == col)
2523                 value_set_si (GBB_DYNAMIC_SCHEDULE (gb)->p[row][col], 1);
2524               else
2525                 value_set_si (GBB_DYNAMIC_SCHEDULE (gb)->p[row][col], 0);
2526         }
2527       else
2528         GBB_DYNAMIC_SCHEDULE (gb) = NULL;
2529     }
2530 }
2531
2532 /* Returns the number of loops that are identical at the beginning of
2533    the vectors A and B.  */
2534
2535 static int
2536 compare_prefix_loops (VEC (loop_p, heap) *a, VEC (loop_p, heap) *b)
2537 {
2538   int i;
2539   loop_p ea;
2540   int lb;
2541
2542   if (!a || !b)
2543     return 0;
2544
2545   lb = VEC_length (loop_p, b);
2546
2547   for (i = 0; VEC_iterate (loop_p, a, i, ea); i++)
2548     if (i >= lb
2549         || ea != VEC_index (loop_p, b, i))
2550       return i;
2551
2552   return 0;
2553 }
2554
2555 /* Build for BB the static schedule.
2556
2557    The STATIC_SCHEDULE is defined like this:
2558
2559    A
2560    for (i: ...)
2561      {
2562        for (j: ...)
2563          {
2564            B
2565            C
2566          }
2567
2568        for (k: ...)
2569          {
2570            D
2571            E
2572          }
2573      }
2574    F
2575
2576    Static schedules for A to F:
2577
2578      DEPTH
2579      0 1 2
2580    A 0
2581    B 1 0 0
2582    C 1 0 1
2583    D 1 1 0
2584    E 1 1 1
2585    F 2
2586 */
2587
2588 static void
2589 build_scop_canonical_schedules (scop_p scop)
2590 {
2591   int i;
2592   graphite_bb_p gb;
2593   int nb_loops = scop_nb_loops (scop);
2594   lambda_vector static_schedule = lambda_vector_new (nb_loops + 1);
2595   VEC (loop_p, heap) *loops_previous = NULL;
2596
2597   /* We have to start schedules at 0 on the first component and
2598      because we cannot compare_prefix_loops against a previous loop,
2599      prefix will be equal to zero, and that index will be
2600      incremented before copying.  */
2601   static_schedule[0] = -1;
2602
2603   for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
2604     {
2605       int prefix = compare_prefix_loops (loops_previous, GBB_LOOPS (gb));
2606       int nb = gbb_nb_loops (gb);
2607
2608       loops_previous = GBB_LOOPS (gb);
2609       memset (&(static_schedule[prefix + 1]), 0, sizeof (int) * (nb_loops - prefix));
2610       ++static_schedule[prefix];
2611       GBB_STATIC_SCHEDULE (gb) = lambda_vector_new (nb + 1);
2612       lambda_vector_copy (static_schedule,
2613                           GBB_STATIC_SCHEDULE (gb), nb + 1);
2614     }
2615 }
2616
2617 /* Build the LOOPS vector for all bbs in SCOP.  */
2618
2619 static void
2620 build_bb_loops (scop_p scop)
2621 {
2622   graphite_bb_p gb;
2623   int i;
2624
2625   for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
2626     {
2627       loop_p loop;
2628       int depth;
2629
2630       depth = nb_loops_around_gb (gb) - 1;
2631
2632       GBB_LOOPS (gb) = VEC_alloc (loop_p, heap, 3);
2633       VEC_safe_grow_cleared (loop_p, heap, GBB_LOOPS (gb), depth + 1);
2634
2635       loop = GBB_BB (gb)->loop_father;
2636
2637       while (scop_contains_loop (scop, loop))
2638         {
2639           VEC_replace (loop_p, GBB_LOOPS (gb), depth, loop);
2640           loop = loop_outer (loop);
2641           depth--;
2642         }
2643     }
2644 }
2645
2646 /* Get the index for parameter VAR in SCOP.  */
2647
2648 static int
2649 param_index (tree var, scop_p scop)
2650 {
2651   int i;
2652   name_tree p;
2653   name_tree nvar;
2654
2655   gcc_assert (TREE_CODE (var) == SSA_NAME);
2656
2657   for (i = 0; VEC_iterate (name_tree, SCOP_PARAMS (scop), i, p); i++)
2658     if (p->t == var)
2659       return i;
2660
2661   gcc_assert (SCOP_ADD_PARAMS (scop));
2662
2663   nvar = XNEW (struct name_tree);
2664   nvar->t = var;
2665   nvar->name = NULL;
2666   VEC_safe_push (name_tree, heap, SCOP_PARAMS (scop), nvar);
2667   return VEC_length (name_tree, SCOP_PARAMS (scop)) - 1;
2668 }
2669
2670 /* Scan EXPR and translate it to an inequality vector INEQ that will
2671    be added, or subtracted, in the constraint domain matrix C at row
2672    R.  K is the number of columns for loop iterators in C. */
2673
2674 static void
2675 scan_tree_for_params (scop_p s, tree e, CloogMatrix *c, int r, Value k,
2676                       bool subtract)
2677 {
2678   int cst_col, param_col;
2679
2680   if (e == chrec_dont_know)
2681     return;
2682
2683   switch (TREE_CODE (e))
2684     {
2685     case POLYNOMIAL_CHREC:
2686       {
2687         tree left = CHREC_LEFT (e);
2688         tree right = CHREC_RIGHT (e);
2689         int var = CHREC_VARIABLE (e);
2690
2691         if (TREE_CODE (right) != INTEGER_CST)
2692           return;
2693
2694         if (c)
2695           {
2696             int loop_col = scop_gimple_loop_depth (s, get_loop (var)) + 1;
2697
2698             if (subtract)
2699               value_sub_int (c->p[r][loop_col], c->p[r][loop_col],
2700                              int_cst_value (right));
2701             else
2702               value_add_int (c->p[r][loop_col], c->p[r][loop_col],
2703                              int_cst_value (right));
2704           }
2705
2706         switch (TREE_CODE (left))
2707           {
2708           case POLYNOMIAL_CHREC:
2709             scan_tree_for_params (s, left, c, r, k, subtract);
2710             return;
2711
2712           case INTEGER_CST:
2713             /* Constant part.  */
2714             if (c)
2715               {
2716                 int v = int_cst_value (left);
2717                 cst_col = c->NbColumns - 1;
2718
2719                 if (v < 0)
2720                   {
2721                     v = -v;
2722                     subtract = subtract ? false : true;
2723                   }
2724
2725                 if (subtract)
2726                   value_sub_int (c->p[r][cst_col], c->p[r][cst_col], v);
2727                 else
2728                   value_add_int (c->p[r][cst_col], c->p[r][cst_col], v);
2729               }
2730             return;
2731
2732           default:
2733             scan_tree_for_params (s, left, c, r, k, subtract);
2734             return;
2735           }
2736       }
2737       break;
2738
2739     case MULT_EXPR:
2740       if (chrec_contains_symbols (TREE_OPERAND (e, 0)))
2741         {
2742           if (c)
2743             {
2744               Value val;
2745               gcc_assert (host_integerp (TREE_OPERAND (e, 1), 0));
2746               value_init (val);
2747               value_set_si (val, int_cst_value (TREE_OPERAND (e, 1)));
2748               value_multiply (k, k, val);
2749               value_clear (val);
2750             }
2751           scan_tree_for_params (s, TREE_OPERAND (e, 0), c, r, k, subtract);
2752         }
2753       else
2754         {
2755           if (c)
2756             {
2757               Value val;
2758               gcc_assert (host_integerp (TREE_OPERAND (e, 0), 0));
2759               value_init (val);
2760               value_set_si (val, int_cst_value (TREE_OPERAND (e, 0)));
2761               value_multiply (k, k, val);
2762               value_clear (val);
2763             }
2764           scan_tree_for_params (s, TREE_OPERAND (e, 1), c, r, k, subtract);
2765         }
2766       break;
2767
2768     case PLUS_EXPR:
2769     case POINTER_PLUS_EXPR:
2770       scan_tree_for_params (s, TREE_OPERAND (e, 0), c, r, k, subtract);
2771       scan_tree_for_params (s, TREE_OPERAND (e, 1), c, r, k, subtract);
2772       break;
2773
2774     case MINUS_EXPR:
2775       scan_tree_for_params (s, TREE_OPERAND (e, 0), c, r, k, subtract);
2776       scan_tree_for_params (s, TREE_OPERAND (e, 1), c, r, k, !subtract);
2777       break;
2778
2779     case NEGATE_EXPR:
2780       scan_tree_for_params (s, TREE_OPERAND (e, 0), c, r, k, !subtract);
2781       break;
2782
2783     case SSA_NAME:
2784       param_col = param_index (e, s);
2785
2786       if (c)
2787         {
2788           param_col += c->NbColumns - scop_nb_params (s) - 1;
2789
2790           if (subtract)
2791             value_subtract (c->p[r][param_col], c->p[r][param_col], k);
2792           else
2793             value_addto (c->p[r][param_col], c->p[r][param_col], k);
2794         }
2795       break;
2796
2797     case INTEGER_CST:
2798       if (c)
2799         {
2800           int v = int_cst_value (e);
2801           cst_col = c->NbColumns - 1;
2802
2803           if (v < 0)
2804           {
2805             v = -v;
2806             subtract = subtract ? false : true;
2807           }
2808
2809           if (subtract)
2810             value_sub_int (c->p[r][cst_col], c->p[r][cst_col], v);
2811           else
2812             value_add_int (c->p[r][cst_col], c->p[r][cst_col], v);
2813         }
2814       break;
2815
2816     CASE_CONVERT:
2817     case NON_LVALUE_EXPR:
2818       scan_tree_for_params (s, TREE_OPERAND (e, 0), c, r, k, subtract);
2819       break;
2820
2821     default:
2822       gcc_unreachable ();
2823       break;
2824     }
2825 }
2826
2827 /* Data structure for idx_record_params.  */
2828
2829 struct irp_data
2830 {
2831   struct loop *loop;
2832   scop_p scop;
2833 };
2834
2835 /* For a data reference with an ARRAY_REF as its BASE, record the
2836    parameters occurring in IDX.  DTA is passed in as complementary
2837    information, and is used by the automatic walker function.  This
2838    function is a callback for for_each_index.  */
2839
2840 static bool
2841 idx_record_params (tree base, tree *idx, void *dta)
2842 {
2843   struct irp_data *data = (struct irp_data *) dta;
2844
2845   if (TREE_CODE (base) != ARRAY_REF)
2846     return true;
2847
2848   if (TREE_CODE (*idx) == SSA_NAME)
2849     {
2850       tree scev;
2851       scop_p scop = data->scop;
2852       struct loop *loop = data->loop;
2853       Value one;
2854
2855       scev = analyze_scalar_evolution (loop, *idx);
2856       scev = instantiate_scev (block_before_scop (scop), loop, scev);
2857
2858       value_init (one);
2859       value_set_si (one, 1);
2860       scan_tree_for_params (scop, scev, NULL, 0, one, false);
2861       value_clear (one);
2862     }
2863
2864   return true;
2865 }
2866
2867 /* Find parameters with respect to SCOP in BB. We are looking in memory
2868    access functions, conditions and loop bounds.  */
2869
2870 static void
2871 find_params_in_bb (scop_p scop, graphite_bb_p gb)
2872 {
2873   int i;
2874   data_reference_p dr;
2875   gimple stmt;
2876   loop_p father = GBB_BB (gb)->loop_father;
2877
2878   for (i = 0; VEC_iterate (data_reference_p, GBB_DATA_REFS (gb), i, dr); i++)
2879     {
2880       struct irp_data irp;
2881
2882       irp.loop = father;
2883       irp.scop = scop;
2884       for_each_index (&dr->ref, idx_record_params, &irp);
2885     }
2886
2887   /* Find parameters in conditional statements.  */
2888   for (i = 0; VEC_iterate (gimple, GBB_CONDITIONS (gb), i, stmt); i++)
2889     {
2890       Value one;
2891       loop_p loop = father;
2892
2893       tree lhs, rhs;
2894
2895       lhs = gimple_cond_lhs (stmt);
2896       lhs = analyze_scalar_evolution (loop, lhs);
2897       lhs = instantiate_scev (block_before_scop (scop), loop, lhs);
2898
2899       rhs = gimple_cond_rhs (stmt);
2900       rhs = analyze_scalar_evolution (loop, rhs);
2901       rhs = instantiate_scev (block_before_scop (scop), loop, rhs);
2902
2903       value_init (one);
2904       scan_tree_for_params (scop, lhs, NULL, 0, one, false);
2905       value_set_si (one, 1);
2906       scan_tree_for_params (scop, rhs, NULL, 0, one, false);
2907       value_clear (one);
2908     }
2909 }
2910
2911 /* Saves in NV the name of variable P->T.  */
2912
2913 static void
2914 save_var_name (char **nv, int i, name_tree p)
2915 {
2916   const char *name = get_name (SSA_NAME_VAR (p->t));
2917
2918   if (name)
2919     {
2920       int len = strlen (name) + 16;
2921       nv[i] = XNEWVEC (char, len);
2922       snprintf (nv[i], len, "%s_%d", name, SSA_NAME_VERSION (p->t));
2923     }
2924   else
2925     {
2926       nv[i] = XNEWVEC (char, 16);
2927       snprintf (nv[i], 2 + 16, "T_%d", SSA_NAME_VERSION (p->t));
2928     }
2929
2930   p->name = nv[i];
2931 }
2932
2933 /* Return the maximal loop depth in SCOP.  */
2934
2935 static int
2936 scop_max_loop_depth (scop_p scop)
2937 {
2938   int i;
2939   graphite_bb_p gbb;
2940   int max_nb_loops = 0;
2941
2942   for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gbb); i++)
2943     {
2944       int nb_loops = gbb_nb_loops (gbb);
2945       if (max_nb_loops < nb_loops)
2946         max_nb_loops = nb_loops;
2947     }
2948
2949   return max_nb_loops;
2950 }
2951
2952 /* Initialize Cloog's parameter names from the names used in GIMPLE.
2953    Initialize Cloog's iterator names, using 'graphite_iterator_%d'
2954    from 0 to scop_nb_loops (scop).  */
2955
2956 static void
2957 initialize_cloog_names (scop_p scop)
2958 {
2959   int i, nb_params = VEC_length (name_tree, SCOP_PARAMS (scop));
2960   char **params = XNEWVEC (char *, nb_params);
2961   int nb_iterators = scop_max_loop_depth (scop);
2962   int nb_scattering= cloog_program_nb_scattdims (SCOP_PROG (scop));
2963   char **iterators = XNEWVEC (char *, nb_iterators * 2);
2964   char **scattering = XNEWVEC (char *, nb_scattering);
2965   name_tree p;
2966
2967   for (i = 0; VEC_iterate (name_tree, SCOP_PARAMS (scop), i, p); i++)
2968     save_var_name (params, i, p);
2969
2970   cloog_names_set_nb_parameters (cloog_program_names (SCOP_PROG (scop)),
2971                                  nb_params);
2972   cloog_names_set_parameters (cloog_program_names (SCOP_PROG (scop)),
2973                               params);
2974
2975   for (i = 0; i < nb_iterators; i++)
2976     {
2977       int len = 18 + 16;
2978       iterators[i] = XNEWVEC (char, len);
2979       snprintf (iterators[i], len, "graphite_iterator_%d", i);
2980     }
2981
2982   cloog_names_set_nb_iterators (cloog_program_names (SCOP_PROG (scop)),
2983                                 nb_iterators);
2984   cloog_names_set_iterators (cloog_program_names (SCOP_PROG (scop)),
2985                              iterators);
2986
2987   for (i = 0; i < nb_scattering; i++)
2988     {
2989       int len = 2 + 16;
2990       scattering[i] = XNEWVEC (char, len);
2991       snprintf (scattering[i], len, "s_%d", i);
2992     }
2993
2994   cloog_names_set_nb_scattering (cloog_program_names (SCOP_PROG (scop)),
2995                                  nb_scattering);
2996   cloog_names_set_scattering (cloog_program_names (SCOP_PROG (scop)),
2997                               scattering);
2998 }
2999
3000 /* Record the parameters used in the SCOP.  A variable is a parameter
3001    in a scop if it does not vary during the execution of that scop.  */
3002
3003 static void
3004 find_scop_parameters (scop_p scop)
3005 {
3006   graphite_bb_p gb;
3007   unsigned i;
3008   struct loop *loop;
3009   Value one;
3010
3011   value_init (one);
3012   value_set_si (one, 1);
3013
3014   /* Find the parameters used in the loop bounds.  */
3015   for (i = 0; VEC_iterate (loop_p, SCOP_LOOP_NEST (scop), i, loop); i++)
3016     {
3017       tree nb_iters = number_of_latch_executions (loop);
3018
3019       if (!chrec_contains_symbols (nb_iters))
3020         continue;
3021
3022       nb_iters = analyze_scalar_evolution (loop, nb_iters);
3023       nb_iters = instantiate_scev (block_before_scop (scop), loop, nb_iters);
3024       scan_tree_for_params (scop, nb_iters, NULL, 0, one, false);
3025     }
3026
3027   value_clear (one);
3028
3029   /* Find the parameters used in data accesses.  */
3030   for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
3031     find_params_in_bb (scop, gb);
3032
3033   SCOP_ADD_PARAMS (scop) = false;
3034 }
3035
3036 /* Build the context constraints for SCOP: constraints and relations
3037    on parameters.  */
3038
3039 static void
3040 build_scop_context (scop_p scop)
3041 {
3042   int nb_params = scop_nb_params (scop);
3043   CloogMatrix *matrix = cloog_matrix_alloc (1, nb_params + 2);
3044
3045   /* Insert '0 >= 0' in the context matrix, as it is not allowed to be
3046      empty. */
3047
3048   value_set_si (matrix->p[0][0], 1);
3049
3050   value_set_si (matrix->p[0][nb_params + 1], 0);
3051
3052   cloog_program_set_context (SCOP_PROG (scop),
3053                              cloog_domain_matrix2domain (matrix));
3054   cloog_matrix_free (matrix);
3055 }
3056
3057 /* Returns a graphite_bb from BB.  */
3058
3059 static inline graphite_bb_p
3060 gbb_from_bb (basic_block bb)
3061 {
3062   return (graphite_bb_p) bb->aux;
3063 }
3064
3065 /* Builds the constraint matrix for LOOP in SCOP.  NB_OUTER_LOOPS is the
3066    number of loops surrounding LOOP in SCOP.  OUTER_CSTR gives the
3067    constraints matrix for the surrounding loops.  */
3068
3069 static void
3070 build_loop_iteration_domains (scop_p scop, struct loop *loop,
3071                               CloogMatrix *outer_cstr, int nb_outer_loops)
3072 {
3073   int i, j, row;
3074   CloogMatrix *cstr;
3075   graphite_bb_p gb;
3076
3077   int nb_rows = outer_cstr->NbRows + 1;
3078   int nb_cols = outer_cstr->NbColumns + 1;
3079
3080   /* Last column of CSTR is the column of constants.  */
3081   int cst_col = nb_cols - 1;
3082
3083   /* The column for the current loop is just after the columns of
3084      other outer loops.  */
3085   int loop_col = nb_outer_loops + 1;
3086
3087   tree nb_iters = number_of_latch_executions (loop);
3088
3089   /* When the number of iterations is a constant or a parameter, we
3090      add a constraint for the upper bound of the loop.  So add a row
3091      to the constraint matrix before allocating it.  */
3092   if (TREE_CODE (nb_iters) == INTEGER_CST
3093       || !chrec_contains_undetermined (nb_iters))
3094     nb_rows++;
3095
3096   cstr = cloog_matrix_alloc (nb_rows, nb_cols);
3097
3098   /* Copy the outer constraints.  */
3099   for (i = 0; i < outer_cstr->NbRows; i++)
3100     {
3101       /* Copy the eq/ineq and loops columns.  */
3102       for (j = 0; j < loop_col; j++)
3103         value_assign (cstr->p[i][j], outer_cstr->p[i][j]);
3104
3105       /* Leave an empty column in CSTR for the current loop, and then
3106          copy the parameter columns.  */
3107       for (j = loop_col; j < outer_cstr->NbColumns; j++)
3108         value_assign (cstr->p[i][j + 1], outer_cstr->p[i][j]);
3109     }
3110
3111   /* 0 <= loop_i */
3112   row = outer_cstr->NbRows;
3113   value_set_si (cstr->p[row][0], 1);
3114   value_set_si (cstr->p[row][loop_col], 1);
3115
3116   /* loop_i <= nb_iters */
3117   if (TREE_CODE (nb_iters) == INTEGER_CST)
3118     {
3119       row++;
3120       value_set_si (cstr->p[row][0], 1);
3121       value_set_si (cstr->p[row][loop_col], -1);
3122
3123       value_set_si (cstr->p[row][cst_col],
3124                     int_cst_value (nb_iters));
3125     }
3126   else if (!chrec_contains_undetermined (nb_iters))
3127     {
3128       /* Otherwise nb_iters contains parameters: scan the nb_iters
3129          expression and build its matrix representation.  */
3130       Value one;
3131
3132       row++;
3133       value_set_si (cstr->p[row][0], 1);
3134       value_set_si (cstr->p[row][loop_col], -1);
3135
3136       nb_iters = analyze_scalar_evolution (loop, nb_iters);
3137       nb_iters = instantiate_scev (block_before_scop (scop), loop, nb_iters);
3138
3139       value_init (one);
3140       value_set_si (one, 1);
3141       scan_tree_for_params (scop, nb_iters, cstr, row, one, false);
3142       value_clear (one);
3143     }
3144   else
3145     gcc_unreachable ();
3146
3147   if (loop->inner && loop_in_sese_p (loop->inner, SCOP_REGION (scop)))
3148     build_loop_iteration_domains (scop, loop->inner, cstr, nb_outer_loops + 1);
3149
3150   /* Only go to the next loops, if we are not at the outermost layer.  These
3151      have to be handled seperately, as we can be sure, that the chain at this
3152      layer will be connected.  */
3153   if (nb_outer_loops != 0 && loop->next && loop_in_sese_p (loop->next,
3154                                                            SCOP_REGION (scop)))
3155     build_loop_iteration_domains (scop, loop->next, outer_cstr, nb_outer_loops);
3156
3157   for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
3158     if (gbb_loop (gb) == loop)
3159       GBB_DOMAIN (gb) = cloog_matrix_copy (cstr);
3160
3161   cloog_matrix_free (cstr);
3162 }
3163
3164 /* Add conditions to the domain of GB.  */
3165
3166 static void
3167 add_conditions_to_domain (graphite_bb_p gb)
3168 {
3169   unsigned int i,j;
3170   gimple stmt;
3171   VEC (gimple, heap) *conditions = GBB_CONDITIONS (gb);
3172   CloogMatrix *domain = GBB_DOMAIN (gb);
3173   scop_p scop = GBB_SCOP (gb);
3174
3175   unsigned nb_rows;
3176   unsigned nb_cols;
3177   unsigned nb_new_rows = 0;
3178   unsigned row;
3179
3180   if (VEC_empty (gimple, conditions))
3181     return;
3182
3183   if (domain)
3184     {
3185       nb_rows = domain->NbRows;
3186       nb_cols = domain->NbColumns;
3187     }
3188   else
3189     {
3190       nb_rows = 0;
3191       nb_cols = nb_loops_around_gb (gb) + scop_nb_params (scop) + 2;
3192     }
3193
3194   /* Count number of necessary new rows to add the conditions to the
3195      domain.  */
3196   for (i = 0; VEC_iterate (gimple, conditions, i, stmt); i++)
3197     {
3198       switch (gimple_code (stmt))
3199         {
3200         case GIMPLE_COND:
3201           {
3202             enum tree_code code = gimple_cond_code (stmt);
3203
3204             switch (code)
3205               {
3206               case NE_EXPR:
3207               case EQ_EXPR:
3208                 /* NE and EQ statements are not supported right know. */
3209                 gcc_unreachable ();
3210                 break;
3211               case LT_EXPR:
3212               case GT_EXPR:
3213               case LE_EXPR:
3214               case GE_EXPR:
3215                 nb_new_rows++;
3216                 break;
3217               default:
3218                 gcc_unreachable ();
3219                 break;
3220               }
3221           break;
3222           }
3223         case SWITCH_EXPR:
3224           /* Switch statements are not supported right know.  */
3225           gcc_unreachable ();
3226           break;
3227
3228         default:
3229           gcc_unreachable ();
3230           break;
3231         }
3232     }
3233
3234
3235   /* Enlarge the matrix.  */
3236   {
3237     CloogMatrix *new_domain;
3238     new_domain = cloog_matrix_alloc (nb_rows + nb_new_rows, nb_cols);
3239
3240     if (domain)
3241       {
3242         for (i = 0; i < nb_rows; i++)
3243           for (j = 0; j < nb_cols; j++)
3244             value_assign (new_domain->p[i][j], domain->p[i][j]);
3245
3246         cloog_matrix_free (domain);
3247       }
3248
3249     domain = new_domain;
3250     GBB_DOMAIN (gb) = new_domain;
3251   }
3252
3253   /* Add the conditions to the new enlarged domain matrix.  */
3254   row = nb_rows;
3255   for (i = 0; VEC_iterate (gimple, conditions, i, stmt); i++)
3256     {
3257       switch (gimple_code (stmt))
3258         {
3259         case GIMPLE_COND:
3260           {
3261             Value one;
3262             enum tree_code code;
3263             tree left;
3264             tree right;
3265             loop_p loop = GBB_BB (gb)->loop_father;
3266
3267             left = gimple_cond_lhs (stmt);
3268             right = gimple_cond_rhs (stmt);
3269
3270             left = analyze_scalar_evolution (loop, left);
3271             right = analyze_scalar_evolution (loop, right);
3272
3273             left = instantiate_scev (block_before_scop (scop), loop, left);
3274             right = instantiate_scev (block_before_scop (scop), loop, right);
3275
3276             code = gimple_cond_code (stmt);
3277
3278             /* The conditions for ELSE-branches are inverted.  */
3279             if (VEC_index (gimple, gb->condition_cases, i) == NULL)
3280               code = invert_tree_comparison (code, false);
3281
3282             switch (code)
3283               {
3284               case NE_EXPR:
3285                 /* NE statements are not supported right know. */
3286                 gcc_unreachable ();
3287                 break;
3288               case EQ_EXPR:
3289                 value_set_si (domain->p[row][0], 1);
3290                 value_init (one);
3291                 value_set_si (one, 1);
3292                 scan_tree_for_params (scop, left, domain, row, one, true);
3293                 value_set_si (one, 1);
3294                 scan_tree_for_params (scop, right, domain, row, one, false);
3295                 row++;
3296                 value_set_si (domain->p[row][0], 1);
3297                 value_set_si (one, 1);
3298                 scan_tree_for_params (scop, left, domain, row, one, false);
3299                 value_set_si (one, 1);
3300                 scan_tree_for_params (scop, right, domain, row, one, true);
3301                 value_clear (one);
3302                 row++;
3303                 break;
3304               case LT_EXPR:
3305                 value_set_si (domain->p[row][0], 1);
3306                 value_init (one);
3307                 value_set_si (one, 1);
3308                 scan_tree_for_params (scop, left, domain, row, one, true);
3309                 value_set_si (one, 1);
3310                 scan_tree_for_params (scop, right, domain, row, one, false);
3311                 value_sub_int (domain->p[row][nb_cols - 1],
3312                     domain->p[row][nb_cols - 1], 1);
3313                 value_clear (one);
3314                 row++;
3315                 break;
3316               case GT_EXPR:
3317                 value_set_si (domain->p[row][0], 1);
3318                 value_init (one);
3319                 value_set_si (one, 1);
3320                 scan_tree_for_params (scop, left, domain, row, one, false);
3321                 value_set_si (one, 1);
3322                 scan_tree_for_params (scop, right, domain, row, one, true);
3323                 value_sub_int (domain->p[row][nb_cols - 1],
3324                     domain->p[row][nb_cols - 1], 1);
3325                 value_clear (one);
3326                 row++;
3327                 break;
3328               case LE_EXPR:
3329                 value_set_si (domain->p[row][0], 1);
3330                 value_init (one);
3331                 value_set_si (one, 1);
3332                 scan_tree_for_params (scop, left, domain, row, one, true);
3333                 value_set_si (one, 1);
3334                 scan_tree_for_params (scop, right, domain, row, one, false);
3335                 value_clear (one);
3336                 row++;
3337                 break;
3338               case GE_EXPR:
3339                 value_set_si (domain->p[row][0], 1);
3340                 value_init (one);
3341                 value_set_si (one, 1);
3342                 scan_tree_for_params (scop, left, domain, row, one, false);
3343                 value_set_si (one, 1);
3344                 scan_tree_for_params (scop, right, domain, row, one, true);
3345                 value_clear (one);
3346                 row++;
3347                 break;
3348               default:
3349                 gcc_unreachable ();
3350                 break;
3351               }
3352             break;
3353           }
3354         case GIMPLE_SWITCH:
3355           /* Switch statements are not supported right know.  */
3356           gcc_unreachable ();
3357           break;
3358
3359         default:
3360           gcc_unreachable ();
3361           break;
3362         }
3363     }
3364 }
3365
3366 /* Returns true when PHI defines an induction variable in the loop
3367    containing the PHI node.  */
3368
3369 static bool
3370 phi_node_is_iv (gimple phi)
3371 {
3372   loop_p loop = gimple_bb (phi)->loop_father;
3373   tree scev = analyze_scalar_evolution (loop, gimple_phi_result (phi));
3374
3375   return tree_contains_chrecs (scev, NULL);
3376 }
3377
3378 /* Returns true when BB contains scalar phi nodes that are not an
3379    induction variable of a loop.  */
3380
3381 static bool
3382 bb_contains_non_iv_scalar_phi_nodes (basic_block bb)
3383 {
3384   gimple phi = NULL;
3385   gimple_stmt_iterator si;
3386
3387   for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
3388     if (is_gimple_reg (gimple_phi_result (gsi_stmt (si))))
3389       {
3390         /* Store the unique scalar PHI node: at this point, loops
3391            should be in cannonical form, so we expect to see at most
3392            one scalar phi node in the loop header.  */
3393         if (phi
3394             || bb != bb->loop_father->header)
3395           return true;
3396
3397         phi = gsi_stmt (si);
3398       }
3399
3400   if (!phi
3401       || phi_node_is_iv (phi))
3402     return false;
3403
3404   return true;
3405 }
3406
3407 /* Helper recursive function.  Record in CONDITIONS and CASES all
3408    conditions from 'if's and 'switch'es occurring in BB from SCOP.
3409
3410    Returns false when the conditions contain scalar computations that
3411    depend on the condition, i.e. when there are scalar phi nodes on
3412    the junction after the condition.  Only the computations occurring
3413    on memory can be handled in the polyhedral model: operations that
3414    define scalar evolutions in conditions, that can potentially be
3415    used to index memory, can't be handled by the polyhedral model.  */
3416
3417 static bool
3418 build_scop_conditions_1 (VEC (gimple, heap) **conditions,
3419                          VEC (gimple, heap) **cases, basic_block bb,
3420                          scop_p scop)
3421 {
3422   bool res = true;
3423   int i, j;
3424   graphite_bb_p gbb;
3425   basic_block bb_child, bb_iter;
3426   VEC (basic_block, heap) *dom;
3427   gimple stmt;
3428
3429   /* Make sure we are in the SCoP.  */
3430   if (!bb_in_sese_p (bb, SCOP_REGION (scop)))
3431     return true;
3432
3433   if (bb_contains_non_iv_scalar_phi_nodes (bb))
3434     return false;
3435
3436   gbb = gbb_from_bb (bb);
3437   if (gbb)
3438     {
3439       GBB_CONDITIONS (gbb) = VEC_copy (gimple, heap, *conditions);
3440       GBB_CONDITION_CASES (gbb) = VEC_copy (gimple, heap, *cases);
3441     }
3442
3443   dom = get_dominated_by (CDI_DOMINATORS, bb);
3444
3445   stmt = last_stmt (bb);
3446   if (stmt)
3447     {
3448       VEC (edge, gc) *edges;
3449       edge e;
3450
3451       switch (gimple_code (stmt))
3452         {
3453         case GIMPLE_COND:
3454           edges = bb->succs;
3455           for (i = 0; VEC_iterate (edge, edges, i, e); i++)
3456             if ((dominated_by_p (CDI_DOMINATORS, e->dest, bb))
3457                 && VEC_length (edge, e->dest->preds) == 1)
3458               {
3459                 /* Remove the scanned block from the dominator successors.  */
3460                 for (j = 0; VEC_iterate (basic_block, dom, j, bb_iter); j++)
3461                   if (bb_iter == e->dest)
3462                     {
3463                       VEC_unordered_remove (basic_block, dom, j);
3464                       break;
3465                     }
3466
3467                 /* Recursively scan the then or else part.  */
3468                 if (e->flags & EDGE_TRUE_VALUE)
3469                   VEC_safe_push (gimple, heap, *cases, stmt);
3470                 else
3471                   {
3472                     gcc_assert (e->flags & EDGE_FALSE_VALUE);
3473                     VEC_safe_push (gimple, heap, *cases, NULL);
3474                   }
3475
3476                 VEC_safe_push (gimple, heap, *conditions, stmt);
3477                 if (!build_scop_conditions_1 (conditions, cases, e->dest, scop))
3478                   {
3479                     res = false;
3480                     goto done;
3481                   }
3482                 VEC_pop (gimple, *conditions);
3483                 VEC_pop (gimple, *cases);
3484               }
3485           break;
3486
3487         case GIMPLE_SWITCH:
3488           {
3489             unsigned i;
3490             gimple_stmt_iterator gsi_search_gimple_label;
3491
3492             for (i = 0; i < gimple_switch_num_labels (stmt); ++i)
3493               {
3494                 basic_block bb_iter;
3495                 size_t k;
3496                 size_t n_cases = VEC_length (gimple, *conditions);
3497                 unsigned n = gimple_switch_num_labels (stmt);
3498
3499                 bb_child = label_to_block
3500                   (CASE_LABEL (gimple_switch_label (stmt, i)));
3501
3502                 for (k = 0; k < n; k++)
3503                   if (i != k
3504                       && label_to_block
3505                       (CASE_LABEL (gimple_switch_label (stmt, k))) == bb_child)
3506                     break;
3507
3508                 /* Switches with multiple case values for the same
3509                    block are not handled.  */
3510                 if (k != n
3511                     /* Switch cases with more than one predecessor are
3512                        not handled.  */
3513                     || VEC_length (edge, bb_child->preds) != 1)
3514                   {
3515                     res = false;
3516                     goto done;
3517                   }
3518
3519                 /* Recursively scan the corresponding 'case' block.  */
3520                 for (gsi_search_gimple_label = gsi_start_bb (bb_child);
3521                      !gsi_end_p (gsi_search_gimple_label);
3522                      gsi_next (&gsi_search_gimple_label))
3523                   {
3524                     gimple label = gsi_stmt (gsi_search_gimple_label);
3525
3526                     if (gimple_code (label) == GIMPLE_LABEL)
3527                       {
3528                         tree t = gimple_label_label (label);
3529
3530                         gcc_assert (t == gimple_switch_label (stmt, i));
3531                         VEC_replace (gimple, *cases, n_cases, label);
3532                         break;
3533                       }
3534                   }
3535
3536                 if (!build_scop_conditions_1 (conditions, cases, bb_child, scop))
3537                   {
3538                     res = false;
3539                     goto done;
3540                   }
3541
3542                 /* Remove the scanned block from the dominator successors.  */
3543                 for (j = 0; VEC_iterate (basic_block, dom, j, bb_iter); j++)
3544                   if (bb_iter == bb_child)
3545                     {
3546                       VEC_unordered_remove (basic_block, dom, j);
3547                       break;
3548                     }
3549               }
3550
3551             VEC_pop (gimple, *conditions);
3552             VEC_pop (gimple, *cases);
3553             break;
3554           }
3555
3556         default:
3557           break;
3558       }
3559   }
3560
3561   /* Scan all immediate dominated successors.  */
3562   for (i = 0; VEC_iterate (basic_block, dom, i, bb_child); i++)
3563     if (!build_scop_conditions_1 (conditions, cases, bb_child, scop))
3564       {
3565         res = false;
3566         goto done;
3567       }
3568
3569  done:
3570   VEC_free (basic_block, heap, dom);
3571   return res;
3572 }
3573
3574 /* Record all conditions from SCOP.
3575
3576    Returns false when the conditions contain scalar computations that
3577    depend on the condition, i.e. when there are scalar phi nodes on
3578    the junction after the condition.  Only the computations occurring
3579    on memory can be handled in the polyhedral model: operations that
3580    define scalar evolutions in conditions, that can potentially be
3581    used to index memory, can't be handled by the polyhedral model.  */
3582
3583 static bool
3584 build_scop_conditions (scop_p scop)
3585 {
3586   bool res;
3587   VEC (gimple, heap) *conditions = NULL;
3588   VEC (gimple, heap) *cases = NULL;
3589
3590   res = build_scop_conditions_1 (&conditions, &cases, SCOP_ENTRY (scop), scop);
3591
3592   VEC_free (gimple, heap, conditions);
3593   VEC_free (gimple, heap, cases);
3594   return res;
3595 }
3596
3597 /* Traverses all the GBBs of the SCOP and add their constraints to the
3598    iteration domains.  */
3599
3600 static void
3601 add_conditions_to_constraints (scop_p scop)
3602 {
3603   int i;
3604   graphite_bb_p gbb;
3605
3606   for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gbb); i++)
3607     add_conditions_to_domain (gbb);
3608 }
3609
3610 /* Build the current domain matrix: the loops belonging to the current
3611    SCOP, and that vary for the execution of the current basic block.
3612    Returns false if there is no loop in SCOP.  */
3613
3614 static bool
3615 build_scop_iteration_domain (scop_p scop)
3616 {
3617   struct loop *loop;
3618   CloogMatrix *outer_cstr;
3619   int i;
3620
3621   /* Build cloog loop for all loops, that are in the uppermost loop layer of
3622      this SCoP.  */
3623   for (i = 0; VEC_iterate (loop_p, SCOP_LOOP_NEST (scop), i, loop); i++)
3624     if (!loop_in_sese_p (loop_outer (loop), SCOP_REGION (scop)))
3625       {
3626         /* The outermost constraints is a matrix that has:
3627            -first column: eq/ineq boolean
3628            -last column: a constant
3629            -scop_nb_params columns for the parameters used in the scop.  */
3630         outer_cstr = cloog_matrix_alloc (0, scop_nb_params (scop) + 2);
3631         build_loop_iteration_domains (scop, loop, outer_cstr, 0);
3632         cloog_matrix_free (outer_cstr);
3633       }
3634
3635   return (i != 0);
3636 }
3637
3638 /* Initializes an equation CY of the access matrix using the
3639    information for a subscript from AF, relatively to the loop
3640    indexes from LOOP_NEST and parameter indexes from PARAMS.  NDIM is
3641    the dimension of the array access, i.e. the number of
3642    subscripts.  Returns true when the operation succeeds.  */
3643
3644 static bool
3645 build_access_matrix_with_af (tree af, lambda_vector cy,
3646                              scop_p scop, int ndim)
3647 {
3648   int param_col;
3649
3650   switch (TREE_CODE (af))
3651     {
3652     case POLYNOMIAL_CHREC:
3653       {
3654         struct loop *outer_loop;
3655         tree left = CHREC_LEFT (af);
3656         tree right = CHREC_RIGHT (af);
3657         int var;
3658
3659         if (TREE_CODE (right) != INTEGER_CST)
3660           return false;
3661
3662         outer_loop = get_loop (CHREC_VARIABLE (af));
3663         var = nb_loops_around_loop_in_scop (outer_loop, scop);
3664         cy[var] = int_cst_value (right);
3665
3666         switch (TREE_CODE (left))
3667           {
3668           case POLYNOMIAL_CHREC:
3669             return build_access_matrix_with_af (left, cy, scop, ndim);
3670
3671           case INTEGER_CST:
3672             cy[ndim - 1] = int_cst_value (left);
3673             return true;
3674
3675           default:
3676             return build_access_matrix_with_af (left, cy, scop, ndim);
3677           }
3678       }
3679
3680     case PLUS_EXPR:
3681       build_access_matrix_with_af (TREE_OPERAND (af, 0), cy, scop, ndim);
3682       build_access_matrix_with_af (TREE_OPERAND (af, 1), cy, scop, ndim);
3683       return true;
3684
3685     case MINUS_EXPR:
3686       build_access_matrix_with_af (TREE_OPERAND (af, 0), cy, scop, ndim);
3687       build_access_matrix_with_af (TREE_OPERAND (af, 1), cy, scop, ndim);
3688       return true;
3689
3690     case INTEGER_CST:
3691       cy[ndim - 1] = int_cst_value (af);
3692       return true;
3693
3694     case SSA_NAME:
3695       param_col = param_index (af, scop);
3696       cy [ndim - scop_nb_params (scop) + param_col - 1] = 1;
3697       return true;
3698
3699     default:
3700       /* FIXME: access_fn can have parameters.  */
3701       return false;
3702     }
3703 }
3704
3705 /* Initialize the access matrix in the data reference REF with respect
3706    to the loop nesting LOOP_NEST.  Return true when the operation
3707    succeeded.  */
3708
3709 static bool
3710 build_access_matrix (data_reference_p ref, graphite_bb_p gb)
3711 {
3712   int i, ndim = DR_NUM_DIMENSIONS (ref);
3713   struct access_matrix *am = GGC_NEW (struct access_matrix);
3714
3715   AM_MATRIX (am) = VEC_alloc (lambda_vector, gc, ndim);
3716   DR_SCOP (ref) = GBB_SCOP (gb);
3717
3718   for (i = 0; i < ndim; i++)
3719     {
3720       lambda_vector v = lambda_vector_new (ref_nb_loops (ref));
3721       scop_p scop = GBB_SCOP (gb);
3722       tree af = DR_ACCESS_FN (ref, i);
3723
3724       if (!build_access_matrix_with_af (af, v, scop, ref_nb_loops (ref)))
3725         return false;
3726
3727       VEC_quick_push (lambda_vector, AM_MATRIX (am), v);
3728     }
3729
3730   DR_ACCESS_MATRIX (ref) = am;
3731   return true;
3732 }
3733
3734 /* Build the access matrices for the data references in the SCOP.  */
3735
3736 static void
3737 build_scop_data_accesses (scop_p scop)
3738 {
3739   int i;
3740   graphite_bb_p gb;
3741
3742   /* FIXME: Construction of access matrix is disabled until some
3743      pass, like the data dependence analysis, is using it.  */
3744   return;
3745
3746   for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
3747     {
3748       int j;
3749       data_reference_p dr;
3750
3751       /* Construct the access matrix for each data ref, with respect to
3752          the loop nest of the current BB in the considered SCOP.  */
3753       for (j = 0;
3754            VEC_iterate (data_reference_p, GBB_DATA_REFS (gb), j, dr);
3755            j++)
3756         {
3757           bool res = build_access_matrix (dr, gb);
3758
3759           /* FIXME: At this point the DRs should always have an affine
3760              form.  For the moment this fails as build_access_matrix
3761              does not build matrices with parameters.  */
3762           gcc_assert (res);
3763         }
3764     }
3765 }
3766
3767 /* Returns the tree variable from the name NAME that was given in
3768    Cloog representation.  All the parameters are stored in PARAMS, and
3769    all the loop induction variables are stored in IVSTACK.
3770
3771    FIXME: This is a hack, and Cloog should be fixed to not work with
3772    variable names represented as "char *string", but with void
3773    pointers that could be casted back to a tree.  The only problem in
3774    doing that is that Cloog's pretty printer still assumes that
3775    variable names are char *strings.  The solution would be to have a
3776    function pointer for pretty-printing that can be redirected to be
3777    print_generic_stmt in our case, or fprintf by default.
3778    ???  Too ugly to live.  */
3779
3780 static tree
3781 clast_name_to_gcc (const char *name, VEC (name_tree, heap) *params,
3782                    loop_iv_stack ivstack)
3783 {
3784   int i;
3785   name_tree t;
3786   tree iv;
3787
3788   if (params)
3789     for (i = 0; VEC_iterate (name_tree, params, i, t); i++)
3790       if (!strcmp (name, t->name))
3791         return t->t;
3792
3793   iv = loop_iv_stack_get_iv_from_name (ivstack, name);
3794   if (iv)
3795     return iv;
3796
3797   gcc_unreachable ();
3798 }
3799
3800 /* Returns the maximal precision type for expressions E1 and E2.  */
3801
3802 static inline tree
3803 max_precision_type (tree e1, tree e2)
3804 {
3805   tree type1 = TREE_TYPE (e1);
3806   tree type2 = TREE_TYPE (e2);
3807   return TYPE_PRECISION (type1) > TYPE_PRECISION (type2) ? type1 : type2;
3808 }
3809
3810 static tree
3811 clast_to_gcc_expression (tree, struct clast_expr *, VEC (name_tree, heap) *,
3812                          loop_iv_stack);
3813
3814 /* Converts a Cloog reduction expression R with reduction operation OP
3815    to a GCC expression tree of type TYPE.  PARAMS is a vector of
3816    parameters of the scop, and IVSTACK contains the stack of induction
3817    variables.  */
3818
3819 static tree
3820 clast_to_gcc_expression_red (tree type, enum tree_code op,
3821                              struct clast_reduction *r,
3822                              VEC (name_tree, heap) *params,
3823                              loop_iv_stack ivstack)
3824 {
3825   int i;
3826   tree res = clast_to_gcc_expression (type, r->elts[0], params, ivstack);
3827
3828   for (i = 1; i < r->n; i++)
3829     {
3830       tree t = clast_to_gcc_expression (type, r->elts[i], params, ivstack);
3831       res = fold_build2 (op, type, res, t);
3832     }
3833   return res;
3834 }
3835
3836 /* Converts a Cloog AST expression E back to a GCC expression tree of
3837    type TYPE.  PARAMS is a vector of parameters of the scop, and
3838    IVSTACK contains the stack of induction variables.  */
3839
3840 static tree
3841 clast_to_gcc_expression (tree type, struct clast_expr *e,
3842                          VEC (name_tree, heap) *params,
3843                          loop_iv_stack ivstack)
3844 {
3845   switch (e->type)
3846     {
3847     case expr_term:
3848       {
3849         struct clast_term *t = (struct clast_term *) e;
3850
3851         if (t->var)
3852           {
3853             if (value_one_p (t->val))
3854               {
3855                 tree name = clast_name_to_gcc (t->var, params, ivstack);
3856                 return fold_convert (type, name);
3857               }
3858
3859             else if (value_mone_p (t->val))
3860               {
3861                 tree name = clast_name_to_gcc (t->var, params, ivstack);
3862                 name = fold_convert (type, name);
3863                 return fold_build1 (NEGATE_EXPR, type, name);
3864               }
3865             else
3866               {
3867                 tree name = clast_name_to_gcc (t->var, params, ivstack);
3868                 tree cst = gmp_cst_to_tree (type, t->val);
3869                 name = fold_convert (type, name);
3870                 return fold_build2 (MULT_EXPR, type, cst, name);
3871               }
3872           }
3873         else
3874           return gmp_cst_to_tree (type, t->val);
3875       }
3876
3877     case expr_red:
3878       {
3879         struct clast_reduction *r = (struct clast_reduction *) e;
3880
3881         switch (r->type)
3882           {
3883           case clast_red_sum:
3884             return clast_to_gcc_expression_red (type, PLUS_EXPR, r, params, ivstack);
3885
3886           case clast_red_min:
3887             return clast_to_gcc_expression_red (type, MIN_EXPR, r, params, ivstack);
3888
3889           case clast_red_max:
3890             return clast_to_gcc_expression_red (type, MAX_EXPR, r, params, ivstack);
3891
3892           default:
3893             gcc_unreachable ();
3894           }
3895         break;
3896       }
3897
3898     case expr_bin:
3899       {
3900         struct clast_binary *b = (struct clast_binary *) e;
3901         struct clast_expr *lhs = (struct clast_expr *) b->LHS;
3902         tree tl = clast_to_gcc_expression (type, lhs, params, ivstack);
3903         tree tr = gmp_cst_to_tree (type, b->RHS);
3904
3905         switch (b->type)
3906           {
3907           case clast_bin_fdiv:
3908             return fold_build2 (FLOOR_DIV_EXPR, type, tl, tr);
3909
3910           case clast_bin_cdiv:
3911             return fold_build2 (CEIL_DIV_EXPR, type, tl, tr);
3912
3913           case clast_bin_div:
3914             return fold_build2 (EXACT_DIV_EXPR, type, tl, tr);
3915
3916           case clast_bin_mod:
3917             return fold_build2 (TRUNC_MOD_EXPR, type, tl, tr);
3918
3919           default:
3920             gcc_unreachable ();
3921           }
3922       }
3923
3924     default:
3925       gcc_unreachable ();
3926     }
3927
3928   return NULL_TREE;
3929 }
3930
3931 /* Returns the type for the expression E.  */
3932
3933 static tree
3934 gcc_type_for_clast_expr (struct clast_expr *e,
3935                          VEC (name_tree, heap) *params,
3936                          loop_iv_stack ivstack)
3937 {
3938   switch (e->type)
3939     {
3940     case expr_term:
3941       {
3942         struct clast_term *t = (struct clast_term *) e;
3943
3944         if (t->var)
3945           return TREE_TYPE (clast_name_to_gcc (t->var, params, ivstack));
3946         else
3947           return NULL_TREE;
3948       }
3949
3950     case expr_red:
3951       {
3952         struct clast_reduction *r = (struct clast_reduction *) e;
3953
3954         if (r->n == 1)
3955           return gcc_type_for_clast_expr (r->elts[0], params, ivstack);
3956         else
3957           {
3958             int i;
3959             for (i = 0; i < r->n; i++)
3960               {
3961                 tree type = gcc_type_for_clast_expr (r->elts[i], params, ivstack);
3962                 if (type)
3963                   return type;
3964               }
3965             return NULL_TREE;
3966           }
3967       }
3968
3969     case expr_bin:
3970       {
3971         struct clast_binary *b = (struct clast_binary *) e;
3972         struct clast_expr *lhs = (struct clast_expr *) b->LHS;
3973         return gcc_type_for_clast_expr (lhs, params, ivstack);
3974       }
3975
3976     default:
3977       gcc_unreachable ();
3978     }
3979
3980   return NULL_TREE;
3981 }
3982
3983 /* Returns the type for the equation CLEQ.  */
3984
3985 static tree
3986 gcc_type_for_clast_eq (struct clast_equation *cleq,
3987                        VEC (name_tree, heap) *params,
3988                        loop_iv_stack ivstack)
3989 {
3990   tree type = gcc_type_for_clast_expr (cleq->LHS, params, ivstack);
3991   if (type)
3992     return type;
3993
3994   return gcc_type_for_clast_expr (cleq->RHS, params, ivstack);
3995 }
3996
3997 /* Translates a clast equation CLEQ to a tree.  */
3998
3999 static tree
4000 graphite_translate_clast_equation (scop_p scop,
4001                                    struct clast_equation *cleq,
4002                                    loop_iv_stack ivstack)
4003 {
4004   enum tree_code comp;
4005   tree type = gcc_type_for_clast_eq (cleq, SCOP_PARAMS (scop), ivstack);
4006   tree lhs = clast_to_gcc_expression (type, cleq->LHS, SCOP_PARAMS (scop), ivstack);
4007   tree rhs = clast_to_gcc_expression (type, cleq->RHS, SCOP_PARAMS (scop), ivstack);
4008
4009   if (cleq->sign == 0)
4010     comp = EQ_EXPR;
4011
4012   else if (cleq->sign > 0)
4013     comp = GE_EXPR;
4014
4015   else
4016     comp = LE_EXPR;
4017
4018   return fold_build2 (comp, type, lhs, rhs);
4019 }
4020
4021 /* Creates the test for the condition in STMT.  */
4022
4023 static tree
4024 graphite_create_guard_cond_expr (scop_p scop, struct clast_guard *stmt,
4025                                  loop_iv_stack ivstack)
4026 {
4027   tree cond = NULL;
4028   int i;
4029
4030   for (i = 0; i < stmt->n; i++)
4031     {
4032       tree eq = graphite_translate_clast_equation (scop, &stmt->eq[i], ivstack);
4033
4034       if (cond)
4035         cond = fold_build2 (TRUTH_AND_EXPR, TREE_TYPE (eq), cond, eq);
4036       else
4037         cond = eq;
4038     }
4039
4040   return cond;
4041 }
4042
4043 /* Creates a new if region corresponding to Cloog's guard.  */
4044
4045 static edge
4046 graphite_create_new_guard (scop_p scop, edge entry_edge,
4047                            struct clast_guard *stmt,
4048                            loop_iv_stack ivstack)
4049 {
4050   tree cond_expr = graphite_create_guard_cond_expr (scop, stmt, ivstack);
4051   edge exit_edge = create_empty_if_region_on_edge (entry_edge, cond_expr);
4052   return exit_edge;
4053 }
4054
4055 /* Walks a CLAST and returns the first statement in the body of a
4056    loop.  */
4057
4058 static struct clast_user_stmt *
4059 clast_get_body_of_loop (struct clast_stmt *stmt)
4060 {
4061   if (!stmt
4062       || CLAST_STMT_IS_A (stmt, stmt_user))
4063     return (struct clast_user_stmt *) stmt;
4064
4065   if (CLAST_STMT_IS_A (stmt, stmt_for))
4066     return clast_get_body_of_loop (((struct clast_for *) stmt)->body);
4067
4068   if (CLAST_STMT_IS_A (stmt, stmt_guard))
4069     return clast_get_body_of_loop (((struct clast_guard *) stmt)->then);
4070
4071   if (CLAST_STMT_IS_A (stmt, stmt_block))
4072     return clast_get_body_of_loop (((struct clast_block *) stmt)->body);
4073
4074   gcc_unreachable ();
4075 }
4076
4077 /* Returns the induction variable for the loop that gets translated to
4078    STMT.  */
4079
4080 static tree
4081 gcc_type_for_iv_of_clast_loop (struct clast_for *stmt_for)
4082 {
4083   struct clast_user_stmt *stmt = clast_get_body_of_loop ((struct clast_stmt *) stmt_for);
4084   const char *cloog_iv = stmt_for->iterator;
4085   CloogStatement *cs = stmt->statement;
4086   graphite_bb_p gbb = (graphite_bb_p) cloog_statement_usr (cs);
4087
4088   return gcc_type_for_cloog_iv (cloog_iv, gbb);
4089 }
4090
4091 /* Creates a new LOOP corresponding to Cloog's STMT.  Inserts an induction
4092    variable for the new LOOP.  New LOOP is attached to CFG starting at
4093    ENTRY_EDGE.  LOOP is inserted into the loop tree and becomes the child
4094    loop of the OUTER_LOOP.  */
4095
4096 static struct loop *
4097 graphite_create_new_loop (scop_p scop, edge entry_edge,
4098                           struct clast_for *stmt, loop_iv_stack ivstack,
4099                           loop_p outer)
4100 {
4101   tree type = gcc_type_for_iv_of_clast_loop (stmt);
4102   VEC (name_tree, heap) *params = SCOP_PARAMS (scop);
4103   tree lb = clast_to_gcc_expression (type, stmt->LB, params, ivstack);
4104   tree ub = clast_to_gcc_expression (type, stmt->UB, params, ivstack);
4105   tree stride = gmp_cst_to_tree (type, stmt->stride);
4106   tree ivvar = create_tmp_var (type, "graphiteIV");
4107   tree iv_before;
4108   loop_p loop = create_empty_loop_on_edge
4109     (entry_edge, lb, stride, ub, ivvar, &iv_before,
4110      outer ? outer : entry_edge->src->loop_father);
4111
4112   add_referenced_var (ivvar);
4113   loop_iv_stack_push_iv (ivstack, iv_before, stmt->iterator);
4114   return loop;
4115 }
4116
4117 /* Rename the SSA_NAMEs used in STMT and that appear in IVSTACK.  */
4118
4119 static void
4120 rename_variables_in_stmt (gimple stmt, htab_t map)
4121 {
4122   ssa_op_iter iter;
4123   use_operand_p use_p;
4124
4125   FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
4126     {
4127       tree use = USE_FROM_PTR (use_p);
4128       tree new_name = get_new_name_from_old_name (map, use);
4129
4130       replace_exp (use_p, new_name);
4131     }
4132
4133   update_stmt (stmt);
4134 }
4135
4136 /* Returns true if SSA_NAME is a parameter of SCOP.  */
4137
4138 static bool
4139 is_parameter (scop_p scop, tree ssa_name)
4140 {
4141   int i;
4142   VEC (name_tree, heap) *params = SCOP_PARAMS (scop);
4143   name_tree param;
4144
4145   for (i = 0; VEC_iterate (name_tree, params, i, param); i++)
4146     if (param->t == ssa_name)
4147       return true;
4148
4149   return false;
4150 }
4151
4152 /* Returns true if NAME is an induction variable.  */
4153
4154 static bool
4155 is_iv (tree name)
4156 {
4157   return gimple_code (SSA_NAME_DEF_STMT (name)) == GIMPLE_PHI;
4158 }
4159
4160 static void expand_scalar_variables_stmt (gimple, basic_block, scop_p,
4161                                           htab_t);
4162 static tree
4163 expand_scalar_variables_expr (tree, tree, enum tree_code, tree, basic_block,
4164                               scop_p, htab_t, gimple_stmt_iterator *);
4165
4166 /* Copies at GSI all the scalar computations on which the ssa_name OP0
4167    depends on in the SCOP: these are all the scalar variables used in
4168    the definition of OP0, that are defined outside BB and still in the
4169    SCOP, i.e. not a parameter of the SCOP.  The expression that is
4170    returned contains only induction variables from the generated code:
4171    MAP contains the induction variables renaming mapping, and is used
4172    to translate the names of induction variables.  */
4173
4174 static tree
4175 expand_scalar_variables_ssa_name (tree op0, basic_block bb,
4176                                   scop_p scop, htab_t map,
4177                                   gimple_stmt_iterator *gsi)
4178 {
4179   tree var0, var1, type;
4180   gimple def_stmt;
4181   enum tree_code subcode;
4182
4183   if (is_parameter (scop, op0)
4184       || is_iv (op0))
4185     return get_new_name_from_old_name (map, op0);
4186
4187   def_stmt = SSA_NAME_DEF_STMT (op0);
4188
4189   if (gimple_bb (def_stmt) == bb)
4190     {
4191       /* If the defining statement is in the basic block already
4192          we do not need to create a new expression for it, we
4193          only need to ensure its operands are expanded.  */
4194       expand_scalar_variables_stmt (def_stmt, bb, scop, map);
4195       return get_new_name_from_old_name (map, op0);
4196     }
4197   else
4198     {
4199       if (gimple_code (def_stmt) != GIMPLE_ASSIGN
4200           || !bb_in_sese_p (gimple_bb (def_stmt), SCOP_REGION (scop)))
4201         return get_new_name_from_old_name (map, op0);
4202
4203       var0 = gimple_assign_rhs1 (def_stmt);
4204       subcode = gimple_assign_rhs_code (def_stmt);
4205       var1 = gimple_assign_rhs2 (def_stmt);
4206       type = gimple_expr_type (def_stmt);
4207
4208       return expand_scalar_variables_expr (type, var0, subcode, var1, bb, scop,
4209                                            map, gsi);
4210     }
4211 }
4212
4213 /* Copies at GSI all the scalar computations on which the expression
4214    OP0 CODE OP1 depends on in the SCOP: these are all the scalar
4215    variables used in OP0 and OP1, defined outside BB and still defined
4216    in the SCOP, i.e. not a parameter of the SCOP.  The expression that
4217    is returned contains only induction variables from the generated
4218    code: MAP contains the induction variables renaming mapping, and is
4219    used to translate the names of induction variables.  */
4220
4221 static tree
4222 expand_scalar_variables_expr (tree type, tree op0, enum tree_code code,
4223                               tree op1, basic_block bb, scop_p scop,
4224                               htab_t map, gimple_stmt_iterator *gsi)
4225 {
4226   if (TREE_CODE_CLASS (code) == tcc_constant
4227       || TREE_CODE_CLASS (code) == tcc_declaration)
4228     return op0;
4229
4230   /* For data references we have to duplicate also its memory
4231      indexing.  */
4232   if (TREE_CODE_CLASS (code) == tcc_reference)
4233     {
4234       switch (code)
4235         {
4236         case INDIRECT_REF:
4237           {
4238             tree old_name = TREE_OPERAND (op0, 0);
4239             tree expr = expand_scalar_variables_ssa_name
4240               (old_name, bb, scop, map, gsi);
4241             tree new_name = force_gimple_operand_gsi (gsi, expr, true, NULL,
4242                                                       true, GSI_SAME_STMT);
4243
4244             set_symbol_mem_tag (SSA_NAME_VAR (new_name),
4245                                 symbol_mem_tag (SSA_NAME_VAR (old_name)));
4246             return fold_build1 (code, type, new_name);
4247           }
4248
4249         case ARRAY_REF:
4250           {
4251             tree op00 = TREE_OPERAND (op0, 0);
4252             tree op01 = TREE_OPERAND (op0, 1);
4253             tree op02 = TREE_OPERAND (op0, 2);
4254             tree op03 = TREE_OPERAND (op0, 3);
4255             tree base = expand_scalar_variables_expr
4256               (TREE_TYPE (op00), op00, TREE_CODE (op00), NULL, bb, scop,
4257                map, gsi);
4258             tree subscript = expand_scalar_variables_expr
4259               (TREE_TYPE (op01), op01, TREE_CODE (op01), NULL, bb, scop,
4260                map, gsi);
4261
4262             return build4 (ARRAY_REF, type, base, subscript, op02, op03);
4263           }
4264
4265         default:
4266           /* The above cases should catch everything.  */
4267           gcc_unreachable ();
4268         }
4269     }
4270
4271   if (TREE_CODE_CLASS (code) == tcc_unary)
4272     {
4273       tree op0_type = TREE_TYPE (op0);
4274       enum tree_code op0_code = TREE_CODE (op0);
4275       tree op0_expr = expand_scalar_variables_expr (op0_type, op0, op0_code,
4276                                                     NULL, bb, scop, map, gsi);
4277
4278       return fold_build1 (code, type, op0_expr);
4279     }
4280
4281   if (TREE_CODE_CLASS (code) == tcc_binary)
4282     {
4283       tree op0_type = TREE_TYPE (op0);
4284       enum tree_code op0_code = TREE_CODE (op0);
4285       tree op0_expr = expand_scalar_variables_expr (op0_type, op0, op0_code,
4286                                                     NULL, bb, scop, map, gsi);
4287       tree op1_type = TREE_TYPE (op1);
4288       enum tree_code op1_code = TREE_CODE (op1);
4289       tree op1_expr = expand_scalar_variables_expr (op1_type, op1, op1_code,
4290                                                     NULL, bb, scop, map, gsi);
4291
4292       return fold_build2 (code, type, op0_expr, op1_expr);
4293     }
4294
4295   if (code == SSA_NAME)
4296     return expand_scalar_variables_ssa_name (op0, bb, scop, map, gsi);
4297
4298   gcc_unreachable ();
4299   return NULL;
4300 }
4301
4302 /* Copies at the beginning of BB all the scalar computations on which
4303    STMT depends on in the SCOP: these are all the scalar variables used
4304    in STMT, defined outside BB and still defined in the SCOP, i.e. not a
4305    parameter of the SCOP.  The expression that is returned contains
4306    only induction variables from the generated code: MAP contains the
4307    induction variables renaming mapping, and is used to translate the
4308    names of induction variables.  */
4309
4310 static void
4311 expand_scalar_variables_stmt (gimple stmt, basic_block bb, scop_p scop,
4312                               htab_t map)
4313 {
4314   ssa_op_iter iter;
4315   use_operand_p use_p;
4316   gimple_stmt_iterator gsi = gsi_after_labels (bb);
4317
4318   FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
4319     {
4320       tree use = USE_FROM_PTR (use_p);
4321       tree type = TREE_TYPE (use);
4322       enum tree_code code = TREE_CODE (use);
4323       tree use_expr = expand_scalar_variables_expr (type, use, code, NULL, bb,
4324                                                     scop, map, &gsi);
4325       if (use_expr != use)
4326         {
4327           tree new_use =
4328             force_gimple_operand_gsi (&gsi, use_expr, true, NULL,
4329                                       true, GSI_NEW_STMT);
4330           replace_exp (use_p, new_use);
4331         }
4332     }
4333
4334   update_stmt (stmt);
4335 }
4336
4337 /* Copies at the beginning of BB all the scalar computations on which
4338    BB depends on in the SCOP: these are all the scalar variables used
4339    in BB, defined outside BB and still defined in the SCOP, i.e. not a
4340    parameter of the SCOP.  The expression that is returned contains
4341    only induction variables from the generated code: MAP contains the
4342    induction variables renaming mapping, and is used to translate the
4343    names of induction variables.  */
4344
4345 static void
4346 expand_scalar_variables (basic_block bb, scop_p scop, htab_t map)
4347 {
4348   gimple_stmt_iterator gsi;
4349
4350   for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi);)
4351     {
4352       gimple stmt = gsi_stmt (gsi);
4353       expand_scalar_variables_stmt (stmt, bb, scop, map);
4354       gsi_next (&gsi);
4355     }
4356 }
4357
4358 /* Rename all the SSA_NAMEs from block BB according to the MAP.  */
4359
4360 static void
4361 rename_variables (basic_block bb, htab_t map)
4362 {
4363   gimple_stmt_iterator gsi;
4364
4365   for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi); gsi_next (&gsi))
4366     rename_variables_in_stmt (gsi_stmt (gsi), map);
4367 }
4368
4369 /* Remove condition from BB.  */
4370
4371 static void
4372 remove_condition (basic_block bb)
4373 {
4374   gimple last = last_stmt (bb);
4375
4376   if (last && gimple_code (last) == GIMPLE_COND)
4377     {
4378       gimple_stmt_iterator gsi = gsi_last_bb (bb);
4379       gsi_remove (&gsi, true);
4380     }
4381 }
4382
4383 /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag set.  */
4384
4385 static edge
4386 get_true_edge_from_guard_bb (basic_block bb)
4387 {
4388   edge e;
4389   edge_iterator ei;
4390
4391   FOR_EACH_EDGE (e, ei, bb->succs)
4392     if (e->flags & EDGE_TRUE_VALUE)
4393       return e;
4394
4395   gcc_unreachable ();
4396   return NULL;
4397 }
4398
4399 /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag cleared.  */
4400
4401 static edge
4402 get_false_edge_from_guard_bb (basic_block bb)
4403 {
4404   edge e;
4405   edge_iterator ei;
4406
4407   FOR_EACH_EDGE (e, ei, bb->succs)
4408     if (!(e->flags & EDGE_TRUE_VALUE))
4409       return e;
4410
4411   gcc_unreachable ();
4412   return NULL;
4413 }
4414
4415 /* Inserts in MAP a tuple (OLD_NAME, NEW_NAME) for the induction
4416    variables of the loops around GBB in SCOP, i.e. GBB_LOOPS.
4417    NEW_NAME is obtained from IVSTACK.  IVSTACK has the same stack
4418    ordering as GBB_LOOPS.  */
4419
4420 static void
4421 build_iv_mapping (loop_iv_stack ivstack, htab_t map, gbb_p gbb, scop_p scop)
4422 {
4423   int i;
4424   name_tree iv;
4425   PTR *slot;
4426
4427   for (i = 0; VEC_iterate (name_tree, SCOP_OLDIVS (scop), i, iv); i++)
4428     {
4429       struct rename_map_elt tmp;
4430
4431       if (!flow_bb_inside_loop_p (iv->loop, GBB_BB (gbb)))
4432         continue;
4433
4434       tmp.old_name = iv->t;
4435       slot = htab_find_slot (map, &tmp, INSERT);
4436
4437       if (!*slot)
4438         {
4439           tree new_name = loop_iv_stack_get_iv (ivstack,
4440                                                 gbb_loop_index (gbb, iv->loop));
4441           *slot = new_rename_map_elt (iv->t, new_name);
4442         }
4443     }
4444 }
4445
4446 /* Register in MAP the tuple (old_name, new_name).  */
4447
4448 static void
4449 register_old_and_new_names (htab_t map, tree old_name, tree new_name)
4450 {
4451   struct rename_map_elt tmp;
4452   PTR *slot;
4453
4454   tmp.old_name = old_name;
4455   slot = htab_find_slot (map, &tmp, INSERT);
4456
4457   if (!*slot)
4458     *slot = new_rename_map_elt (old_name, new_name);
4459 }
4460
4461 /* Create a duplicate of the basic block BB.  NOTE: This does not
4462    preserve SSA form.  */
4463
4464 static void
4465 graphite_copy_stmts_from_block (basic_block bb, basic_block new_bb, htab_t map)
4466 {
4467   gimple_stmt_iterator gsi, gsi_tgt;
4468
4469   gsi_tgt = gsi_start_bb (new_bb);
4470   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
4471     {
4472       def_operand_p def_p;
4473       ssa_op_iter op_iter;
4474       int region;
4475       gimple stmt = gsi_stmt (gsi);
4476       gimple copy;
4477
4478       if (gimple_code (stmt) == GIMPLE_LABEL)
4479         continue;
4480
4481       /* Create a new copy of STMT and duplicate STMT's virtual
4482          operands.  */
4483       copy = gimple_copy (stmt);
4484       gsi_insert_after (&gsi_tgt, copy, GSI_NEW_STMT);
4485       mark_symbols_for_renaming (copy);
4486
4487       region = lookup_stmt_eh_region (stmt);
4488       if (region >= 0)
4489         add_stmt_to_eh_region (copy, region);
4490       gimple_duplicate_stmt_histograms (cfun, copy, cfun, stmt);
4491
4492       /* Create new names for all the definitions created by COPY and
4493          add replacement mappings for each new name.  */
4494       FOR_EACH_SSA_DEF_OPERAND (def_p, copy, op_iter, SSA_OP_DEF)
4495         {
4496           tree old_name = DEF_FROM_PTR (def_p);
4497           tree new_name = create_new_def_for (old_name, copy, def_p);
4498           register_old_and_new_names (map, old_name, new_name);
4499         }
4500     }
4501 }
4502
4503 /* Records in SCOP_LIVEOUT_RENAMES the names that are live out of
4504    the SCOP and that appear in the RENAME_MAP.  */
4505
4506 static void
4507 register_scop_liveout_renames (scop_p scop, htab_t rename_map)
4508 {
4509   int i;
4510   sese region = SCOP_REGION (scop);
4511
4512   for (i = 0; i < SESE_NUM_VER (region); i++)
4513     if (bitmap_bit_p (SESE_LIVEOUT (region), i)
4514         && is_gimple_reg (ssa_name (i)))
4515       {
4516         tree old_name = ssa_name (i);
4517         tree new_name = get_new_name_from_old_name (rename_map, old_name);
4518
4519         register_old_and_new_names (SCOP_LIVEOUT_RENAMES (scop),
4520                                     old_name, new_name);
4521       }
4522 }
4523
4524 /* Copies BB and includes in the copied BB all the statements that can
4525    be reached following the use-def chains from the memory accesses,
4526    and returns the next edge following this new block.  */
4527
4528 static edge
4529 copy_bb_and_scalar_dependences (basic_block bb, scop_p scop,
4530                                 edge next_e, htab_t map)
4531 {
4532   basic_block new_bb = split_edge (next_e);
4533
4534   next_e = single_succ_edge (new_bb);
4535   graphite_copy_stmts_from_block (bb, new_bb, map);
4536   remove_condition (new_bb);
4537   rename_variables (new_bb, map);
4538   remove_phi_nodes (new_bb);
4539   expand_scalar_variables (new_bb, scop, map);
4540   register_scop_liveout_renames (scop, map);
4541
4542   return next_e;
4543 }
4544
4545 /* Helper function for htab_traverse in insert_loop_close_phis.  */
4546
4547 static int
4548 add_loop_exit_phis (void **slot, void *s)
4549 {
4550   struct rename_map_elt *entry = (struct rename_map_elt *) *slot;
4551   tree new_name = entry->new_name;
4552   basic_block bb = (basic_block) s;
4553   gimple phi = create_phi_node (new_name, bb);
4554   tree res = create_new_def_for (gimple_phi_result (phi), phi,
4555                                  gimple_phi_result_ptr (phi));
4556
4557   add_phi_arg (phi, new_name, single_pred_edge (bb));
4558
4559   entry->new_name = res;
4560   *slot = entry;
4561   return 1;
4562 }
4563
4564 /* Iterate over the SCOP_LIVEOUT_RENAMES (SCOP) and get tuples of the
4565    form (OLD_NAME, NEW_NAME).  Insert in BB "RES = phi (NEW_NAME)",
4566    and finally register in SCOP_LIVEOUT_RENAMES (scop) the tuple
4567    (OLD_NAME, RES).  */
4568
4569 static void
4570 insert_loop_close_phis (scop_p scop, basic_block bb)
4571 {
4572   update_ssa (TODO_update_ssa);
4573   htab_traverse (SCOP_LIVEOUT_RENAMES (scop), add_loop_exit_phis, bb);
4574   update_ssa (TODO_update_ssa);
4575 }
4576
4577 /* Helper structure for htab_traverse in insert_guard_phis.  */
4578
4579 struct igp {
4580   basic_block bb;
4581   edge true_edge, false_edge;
4582   htab_t liveout_before_guard;
4583 };
4584
4585 /* Return the default name that is before the guard.  */
4586
4587 static tree
4588 default_liveout_before_guard (htab_t liveout_before_guard, tree old_name)
4589 {
4590   tree res = get_new_name_from_old_name (liveout_before_guard, old_name);
4591
4592   if (res == old_name)
4593     {
4594       if (is_gimple_reg (res))
4595         return fold_convert (TREE_TYPE (res), integer_zero_node);
4596       return gimple_default_def (cfun, res);
4597     }
4598
4599   return res;
4600 }
4601
4602 /* Helper function for htab_traverse in insert_guard_phis.  */
4603
4604 static int
4605 add_guard_exit_phis (void **slot, void *s)
4606 {
4607   struct rename_map_elt *entry = (struct rename_map_elt *) *slot;
4608   struct igp *i = (struct igp *) s;
4609   basic_block bb = i->bb;
4610   edge true_edge = i->true_edge;
4611   edge false_edge = i->false_edge;
4612   tree name1 = entry->new_name;
4613   tree name2 = default_liveout_before_guard (i->liveout_before_guard,
4614                                              entry->old_name);
4615   gimple phi = create_phi_node (name1, bb);
4616   tree res = create_new_def_for (gimple_phi_result (phi), phi,
4617                                  gimple_phi_result_ptr (phi));
4618
4619   add_phi_arg (phi, name1, true_edge);
4620   add_phi_arg (phi, name2, false_edge);
4621
4622   entry->new_name = res;
4623   *slot = entry;
4624   return 1;
4625 }
4626
4627 /* Iterate over the SCOP_LIVEOUT_RENAMES (SCOP) and get tuples of the
4628    form (OLD_NAME, NAME1).  If there is a correspondent tuple of
4629    OLD_NAME in LIVEOUT_BEFORE_GUARD, i.e. (OLD_NAME, NAME2) then
4630    insert in BB
4631
4632    | RES = phi (NAME1 (on TRUE_EDGE), NAME2 (on FALSE_EDGE))"
4633
4634    if there is no tuple for OLD_NAME in LIVEOUT_BEFORE_GUARD, insert
4635
4636    | RES = phi (NAME1 (on TRUE_EDGE),
4637    |            DEFAULT_DEFINITION of NAME1 (on FALSE_EDGE))".
4638
4639    Finally register in SCOP_LIVEOUT_RENAMES (scop) the tuple
4640    (OLD_NAME, RES).  */
4641
4642 static void
4643 insert_guard_phis (scop_p scop, basic_block bb, edge true_edge,
4644                    edge false_edge, htab_t liveout_before_guard)
4645 {
4646   struct igp i;
4647   i.bb = bb;
4648   i.true_edge = true_edge;
4649   i.false_edge = false_edge;
4650   i.liveout_before_guard = liveout_before_guard;
4651
4652   update_ssa (TODO_update_ssa);
4653   htab_traverse (SCOP_LIVEOUT_RENAMES (scop), add_guard_exit_phis, &i);
4654   update_ssa (TODO_update_ssa);
4655 }
4656
4657 /* Helper function for htab_traverse.  */
4658
4659 static int
4660 copy_renames (void **slot, void *s)
4661 {
4662   struct rename_map_elt *entry = (struct rename_map_elt *) *slot;
4663   htab_t res = (htab_t) s;
4664   tree old_name = entry->old_name;
4665   tree new_name = entry->new_name;
4666   struct rename_map_elt tmp;
4667   PTR *x;
4668
4669   tmp.old_name = old_name;
4670   x = htab_find_slot (res, &tmp, INSERT);
4671
4672   if (!*x)
4673     *x = new_rename_map_elt (old_name, new_name);
4674
4675   return 1;
4676 }
4677
4678 /* Translates a CLAST statement STMT to GCC representation in the
4679    context of a SCOP.
4680
4681    - NEXT_E is the edge where new generated code should be attached.
4682    - CONTEXT_LOOP is the loop in which the generated code will be placed
4683      (might be NULL).
4684    - IVSTACK contains the surrounding loops around the statement to be
4685      translated.
4686 */
4687
4688 static edge
4689 translate_clast (scop_p scop, struct loop *context_loop,
4690                  struct clast_stmt *stmt, edge next_e, loop_iv_stack ivstack)
4691 {
4692   if (!stmt)
4693     return next_e;
4694
4695   if (CLAST_STMT_IS_A (stmt, stmt_root))
4696     return translate_clast (scop, context_loop, stmt->next, next_e, ivstack);
4697
4698   if (CLAST_STMT_IS_A (stmt, stmt_user))
4699     {
4700       htab_t map;
4701       CloogStatement *cs = ((struct clast_user_stmt *) stmt)->statement;
4702       graphite_bb_p gbb = (graphite_bb_p) cloog_statement_usr (cs);
4703
4704       if (GBB_BB (gbb) == ENTRY_BLOCK_PTR)
4705         return next_e;
4706
4707       map = htab_create (10, rename_map_elt_info, eq_rename_map_elts, free);
4708       loop_iv_stack_patch_for_consts (ivstack, (struct clast_user_stmt *) stmt);
4709       build_iv_mapping (ivstack, map, gbb, scop);
4710       next_e = copy_bb_and_scalar_dependences (GBB_BB (gbb), scop,
4711                                                next_e, map);
4712       htab_delete (map);
4713       loop_iv_stack_remove_constants (ivstack);
4714       update_ssa (TODO_update_ssa);
4715       recompute_all_dominators ();
4716       graphite_verify ();
4717       return translate_clast (scop, context_loop, stmt->next, next_e, ivstack);
4718     }
4719
4720   if (CLAST_STMT_IS_A (stmt, stmt_for))
4721     {
4722       struct loop *loop
4723         = graphite_create_new_loop (scop, next_e, (struct clast_for *) stmt,
4724                                     ivstack, context_loop ? context_loop
4725                                     : get_loop (0));
4726       edge last_e = single_exit (loop);
4727
4728       next_e = translate_clast (scop, loop, ((struct clast_for *) stmt)->body,
4729                                 single_pred_edge (loop->latch), ivstack);
4730       redirect_edge_succ_nodup (next_e, loop->latch);
4731
4732       set_immediate_dominator (CDI_DOMINATORS, next_e->dest, next_e->src);
4733       loop_iv_stack_pop (ivstack);
4734       last_e = single_succ_edge (split_edge (last_e));
4735       insert_loop_close_phis (scop, last_e->src);
4736
4737       recompute_all_dominators ();
4738       graphite_verify ();
4739       return translate_clast (scop, context_loop, stmt->next, last_e, ivstack);
4740     }
4741
4742   if (CLAST_STMT_IS_A (stmt, stmt_guard))
4743     {
4744       htab_t liveout_before_guard = htab_create (10, rename_map_elt_info,
4745                                                  eq_rename_map_elts, free);
4746       edge last_e = graphite_create_new_guard (scop, next_e,
4747                                                ((struct clast_guard *) stmt),
4748                                                ivstack);
4749       edge true_e = get_true_edge_from_guard_bb (next_e->dest);
4750       edge false_e = get_false_edge_from_guard_bb (next_e->dest);
4751       edge exit_true_e = single_succ_edge (true_e->dest);
4752       edge exit_false_e = single_succ_edge (false_e->dest);
4753
4754       htab_traverse (SCOP_LIVEOUT_RENAMES (scop), copy_renames,
4755                      liveout_before_guard);
4756
4757       next_e = translate_clast (scop, context_loop,
4758                                 ((struct clast_guard *) stmt)->then,
4759                                 true_e, ivstack);
4760       insert_guard_phis (scop, last_e->src, exit_true_e, exit_false_e,
4761                          liveout_before_guard);
4762       htab_delete (liveout_before_guard);
4763       recompute_all_dominators ();
4764       graphite_verify ();
4765
4766       return translate_clast (scop, context_loop, stmt->next, last_e, ivstack);
4767     }
4768
4769   if (CLAST_STMT_IS_A (stmt, stmt_block))
4770     {
4771       next_e = translate_clast (scop, context_loop,
4772                                 ((struct clast_block *) stmt)->body,
4773                                 next_e, ivstack);
4774       recompute_all_dominators ();
4775       graphite_verify ();
4776       return translate_clast (scop, context_loop, stmt->next, next_e, ivstack);
4777     }
4778
4779   gcc_unreachable ();
4780 }
4781
4782 /* Free the SCATTERING domain list.  */
4783
4784 static void
4785 free_scattering (CloogDomainList *scattering)
4786 {
4787   while (scattering)
4788     {
4789       CloogDomain *dom = cloog_domain (scattering);
4790       CloogDomainList *next = cloog_next_domain (scattering);
4791
4792       cloog_domain_free (dom);
4793       free (scattering);
4794       scattering = next;
4795     }
4796 }
4797
4798 /* Build cloog program for SCoP.  */
4799
4800 static void
4801 build_cloog_prog (scop_p scop)
4802 {
4803   int i;
4804   int max_nb_loops = scop_max_loop_depth (scop);
4805   graphite_bb_p gbb;
4806   CloogLoop *loop_list = NULL;
4807   CloogBlockList *block_list = NULL;
4808   CloogDomainList *scattering = NULL;
4809   CloogProgram *prog = SCOP_PROG (scop);
4810   int nbs = 2 * max_nb_loops + 1;
4811   int *scaldims = (int *) xmalloc (nbs * (sizeof (int)));
4812
4813   cloog_program_set_nb_scattdims (prog, nbs);
4814   initialize_cloog_names (scop);
4815
4816   for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gbb); i++)
4817     {
4818       /* Build new block.  */
4819       CloogMatrix *domain = GBB_DOMAIN (gbb);
4820       CloogStatement *stmt = cloog_statement_alloc (GBB_BB (gbb)->index);
4821       CloogBlock *block = cloog_block_alloc (stmt, 0, NULL,
4822                                              nb_loops_around_gb (gbb));
4823       cloog_statement_set_usr (stmt, gbb);
4824
4825       /* Add empty domain to all bbs, which do not yet have a domain, as they
4826          are not part of any loop.  */
4827       if (domain == NULL)
4828         {
4829           domain = cloog_matrix_alloc (0, scop_nb_params (scop) + 2);
4830           GBB_DOMAIN (gbb) = domain;
4831         }
4832
4833       /* Build loop list.  */
4834       {
4835         CloogLoop *new_loop_list = cloog_loop_malloc ();
4836         cloog_loop_set_next (new_loop_list, loop_list);
4837         cloog_loop_set_domain (new_loop_list,
4838                                cloog_domain_matrix2domain (domain));
4839         cloog_loop_set_block (new_loop_list, block);
4840         loop_list = new_loop_list;
4841       }
4842
4843       /* Build block list.  */
4844       {
4845         CloogBlockList *new_block_list = cloog_block_list_malloc ();
4846
4847         cloog_block_list_set_next (new_block_list, block_list);
4848         cloog_block_list_set_block (new_block_list, block);
4849         block_list = new_block_list;
4850       }
4851
4852       /* Build scattering list.  */
4853       {
4854         /* XXX: Replace with cloog_domain_list_alloc(), when available.  */
4855         CloogDomainList *new_scattering
4856           = (CloogDomainList *) xmalloc (sizeof (CloogDomainList));
4857         CloogMatrix *scat_mat = schedule_to_scattering (gbb, nbs);
4858
4859         cloog_set_next_domain (new_scattering, scattering);
4860         cloog_set_domain (new_scattering,
4861                           cloog_domain_matrix2domain (scat_mat));
4862         scattering = new_scattering;
4863         cloog_matrix_free (scat_mat);
4864       }
4865     }
4866
4867   cloog_program_set_loop (prog, loop_list);
4868   cloog_program_set_blocklist (prog, block_list);
4869
4870   for (i = 0; i < nbs; i++)
4871     scaldims[i] = 0 ;
4872
4873   cloog_program_set_scaldims (prog, scaldims);
4874
4875   /* Extract scalar dimensions to simplify the code generation problem.  */
4876   cloog_program_extract_scalars (prog, scattering);
4877
4878   /* Apply scattering.  */
4879   cloog_program_scatter (prog, scattering);
4880   free_scattering (scattering);
4881
4882   /* Iterators corresponding to scalar dimensions have to be extracted.  */
4883   cloog_names_scalarize (cloog_program_names (prog), nbs,
4884                          cloog_program_scaldims (prog));
4885
4886   /* Free blocklist.  */
4887   {
4888     CloogBlockList *next = cloog_program_blocklist (prog);
4889
4890     while (next)
4891       {
4892         CloogBlockList *toDelete = next;
4893         next = cloog_block_list_next (next);
4894         cloog_block_list_set_next (toDelete, NULL);
4895         cloog_block_list_set_block (toDelete, NULL);
4896         cloog_block_list_free (toDelete);
4897       }
4898     cloog_program_set_blocklist (prog, NULL);
4899   }
4900 }
4901
4902 /* Return the options that will be used in GLOOG.  */
4903
4904 static CloogOptions *
4905 set_cloog_options (void)
4906 {
4907   CloogOptions *options = cloog_options_malloc ();
4908
4909   /* Change cloog output language to C.  If we do use FORTRAN instead, cloog
4910      will stop e.g. with "ERROR: unbounded loops not allowed in FORTRAN.", if
4911      we pass an incomplete program to cloog.  */
4912   options->language = LANGUAGE_C;
4913
4914   /* Enable complex equality spreading: removes dummy statements
4915      (assignments) in the generated code which repeats the
4916      substitution equations for statements.  This is useless for
4917      GLooG.  */
4918   options->esp = 1;
4919
4920   /* Enable C pretty-printing mode: normalizes the substitution
4921      equations for statements.  */
4922   options->cpp = 1;
4923
4924   /* Allow cloog to build strides with a stride width different to one.
4925      This example has stride = 4:
4926
4927      for (i = 0; i < 20; i += 4)
4928        A  */
4929   options->strides = 1;
4930
4931   /* Disable optimizations and make cloog generate source code closer to the
4932      input.  This is useful for debugging,  but later we want the optimized
4933      code.
4934
4935      XXX: We can not disable optimizations, as loop blocking is not working
4936      without them.  */
4937   if (0)
4938     {
4939       options->f = -1;
4940       options->l = INT_MAX;
4941     }
4942
4943   return options;
4944 }
4945
4946 /* Prints STMT to STDERR.  */
4947
4948 void
4949 debug_clast_stmt (struct clast_stmt *stmt)
4950 {
4951   CloogOptions *options = set_cloog_options ();
4952
4953   pprint (stderr, stmt, 0, options);
4954 }
4955
4956 /* Find the right transform for the SCOP, and return a Cloog AST
4957    representing the new form of the program.  */
4958
4959 static struct clast_stmt *
4960 find_transform (scop_p scop)
4961 {
4962   struct clast_stmt *stmt;
4963   CloogOptions *options = set_cloog_options ();
4964
4965   /* Connect new cloog prog generation to graphite.  */
4966   build_cloog_prog (scop);
4967
4968   if (dump_file && (dump_flags & TDF_DETAILS))
4969     {
4970       fprintf (dump_file, "Cloog Input [\n");
4971       cloog_program_print (dump_file, SCOP_PROG(scop));
4972       fprintf (dump_file, "]\n");
4973     }
4974
4975   SCOP_PROG (scop) = cloog_program_generate (SCOP_PROG (scop), options);
4976   stmt = cloog_clast_create (SCOP_PROG (scop), options);
4977
4978   if (dump_file && (dump_flags & TDF_DETAILS))
4979     {
4980       fprintf (dump_file, "Cloog Output[\n");
4981       pprint (dump_file, stmt, 0, options);
4982       cloog_program_dump_cloog (dump_file, SCOP_PROG (scop));
4983       fprintf (dump_file, "]\n");
4984     }
4985
4986   cloog_options_free (options);
4987   return stmt;
4988 }
4989
4990 /* Remove from the CFG the REGION.  */
4991
4992 static inline void
4993 remove_sese_region (sese region)
4994 {
4995   VEC (basic_block, heap) *bbs = NULL;
4996   basic_block entry_bb = SESE_ENTRY (region)->dest;
4997   basic_block exit_bb = SESE_EXIT (region)->dest;
4998   basic_block bb;
4999   int i;
5000
5001   VEC_safe_push (basic_block, heap, bbs, entry_bb);
5002   gather_blocks_in_sese_region (entry_bb, exit_bb, &bbs);
5003
5004   for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++)
5005     delete_basic_block (bb);
5006
5007   VEC_free (basic_block, heap, bbs);
5008 }
5009
5010 typedef struct ifsese {
5011   sese region;
5012   sese true_region;
5013   sese false_region;
5014 } *ifsese;
5015
5016 static inline edge
5017 if_region_entry (ifsese if_region)
5018 {
5019   return SESE_ENTRY (if_region->region);
5020 }
5021
5022 static inline edge
5023 if_region_exit (ifsese if_region)
5024 {
5025   return SESE_EXIT (if_region->region);
5026 }
5027
5028 static inline basic_block
5029 if_region_get_condition_block (ifsese if_region)
5030 {
5031   return if_region_entry (if_region)->dest;
5032 }
5033
5034 static inline void
5035 if_region_set_false_region (ifsese if_region, sese region)
5036 {
5037   basic_block condition = if_region_get_condition_block (if_region);
5038   edge false_edge = get_false_edge_from_guard_bb (condition);
5039   basic_block dummy = false_edge->dest;
5040   edge entry_region = SESE_ENTRY (region);
5041   edge exit_region = SESE_EXIT (region);
5042   basic_block before_region = entry_region->src;
5043   basic_block last_in_region = exit_region->src;
5044   void **slot = htab_find_slot_with_hash (current_loops->exits, exit_region,
5045                                           htab_hash_pointer (exit_region),
5046                                           NO_INSERT);
5047
5048   entry_region->flags = false_edge->flags;
5049   false_edge->flags = exit_region->flags;
5050
5051   redirect_edge_pred (entry_region, condition);
5052   redirect_edge_pred (exit_region, before_region);
5053   redirect_edge_pred (false_edge, last_in_region);
5054   redirect_edge_succ (false_edge, single_succ (dummy));
5055   delete_basic_block (dummy);
5056
5057   exit_region->flags = EDGE_FALLTHRU;
5058   recompute_all_dominators ();
5059
5060   SESE_EXIT (region) = false_edge;
5061   if_region->false_region = region;
5062
5063   if (slot)
5064     {
5065       struct loop_exit *loop_exit = GGC_CNEW (struct loop_exit);
5066
5067       memcpy (loop_exit, *((struct loop_exit **) slot), sizeof (struct loop_exit));
5068       htab_clear_slot (current_loops->exits, slot);
5069
5070       slot = htab_find_slot_with_hash (current_loops->exits, false_edge,
5071                                        htab_hash_pointer (false_edge),
5072                                        INSERT);
5073       loop_exit->e = false_edge;
5074       *slot = loop_exit;
5075       false_edge->src->loop_father->exits->next = loop_exit;
5076     }
5077 }
5078
5079 static ifsese
5080 create_if_region_on_edge (edge entry, tree condition)
5081 {
5082   edge e;
5083   edge_iterator ei;
5084   sese sese_region = GGC_NEW (struct sese);
5085   sese true_region = GGC_NEW (struct sese);
5086   sese false_region = GGC_NEW (struct sese);
5087   ifsese if_region = GGC_NEW (struct ifsese);
5088   edge exit = create_empty_if_region_on_edge (entry, condition);
5089
5090   if_region->region = sese_region;
5091   if_region->region->entry = entry;
5092   if_region->region->exit = exit;
5093
5094   FOR_EACH_EDGE (e, ei, entry->dest->succs)
5095     {
5096       if (e->flags & EDGE_TRUE_VALUE)
5097         {
5098           true_region->entry = e;
5099           true_region->exit = single_succ_edge (e->dest);
5100           if_region->true_region = true_region;
5101         }
5102       else if (e->flags & EDGE_FALSE_VALUE)
5103         {
5104           false_region->entry = e;
5105           false_region->exit = single_succ_edge (e->dest);
5106           if_region->false_region = false_region;
5107         }
5108     }
5109
5110   return if_region;
5111 }
5112
5113 /* Moves REGION in a condition expression:
5114    | if (1)
5115    |   ;
5116    | else
5117    |   REGION;
5118 */
5119
5120 static ifsese
5121 move_sese_in_condition (sese region)
5122 {
5123   basic_block pred_block = split_edge (SESE_ENTRY (region));
5124   ifsese if_region = NULL;
5125
5126   SESE_ENTRY (region) = single_succ_edge (pred_block);
5127   if_region = create_if_region_on_edge (single_pred_edge (pred_block), integer_one_node);
5128   if_region_set_false_region (if_region, region);
5129
5130   return if_region;
5131 }
5132
5133 /* Add exit phis for USE on EXIT.  */
5134
5135 static void
5136 scop_add_exit_phis_edge (basic_block exit, tree use, edge false_e, edge true_e)
5137 {
5138   gimple phi = create_phi_node (use, exit);
5139
5140   create_new_def_for (gimple_phi_result (phi), phi,
5141                       gimple_phi_result_ptr (phi));
5142   add_phi_arg (phi, use, false_e);
5143   add_phi_arg (phi, use, true_e);
5144 }
5145
5146 /* Add phi nodes for VAR that is used in LIVEIN.  Phi nodes are
5147    inserted in block BB.  */
5148
5149 static void
5150 scop_add_exit_phis_var (basic_block bb, tree var, bitmap livein,
5151                         edge false_e, edge true_e)
5152 {
5153   bitmap def;
5154   basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (var));
5155
5156   if (is_gimple_reg (var))
5157     bitmap_clear_bit (livein, def_bb->index);
5158   else
5159     bitmap_set_bit (livein, def_bb->index);
5160
5161   def = BITMAP_ALLOC (NULL);
5162   bitmap_set_bit (def, def_bb->index);
5163   compute_global_livein (livein, def);
5164   BITMAP_FREE (def);
5165
5166   scop_add_exit_phis_edge (bb, var, false_e, true_e);
5167 }
5168
5169 /* Insert in the block BB phi nodes for variables defined in REGION
5170    and used outside the REGION.  The code generation moves REGION in
5171    the else clause of an "if (1)" and generates code in the then
5172    clause that is at this point empty:
5173
5174    | if (1)
5175    |   empty;
5176    | else
5177    |   REGION;
5178 */
5179
5180 static void
5181 scop_insert_phis_for_liveouts (sese region, basic_block bb,
5182                                edge false_e, edge true_e)
5183 {
5184   unsigned i;
5185   bitmap_iterator bi;
5186
5187   update_ssa (TODO_update_ssa);
5188
5189   EXECUTE_IF_SET_IN_BITMAP (SESE_LIVEOUT (region), 0, i, bi)
5190     scop_add_exit_phis_var (bb, ssa_name (i), SESE_LIVEIN_VER (region, i),
5191                             false_e, true_e);
5192
5193   update_ssa (TODO_update_ssa);
5194 }
5195
5196 /* Get the definition of NAME before the SCOP.  Keep track of the
5197    basic blocks that have been VISITED in a bitmap.  */
5198
5199 static tree
5200 get_vdef_before_scop (scop_p scop, tree name, sbitmap visited)
5201 {
5202   unsigned i;
5203   gimple def_stmt = SSA_NAME_DEF_STMT (name);
5204   basic_block def_bb = gimple_bb (def_stmt);
5205
5206   if (!def_bb
5207       || !bb_in_sese_p (def_bb, SCOP_REGION (scop)))
5208     return name;
5209
5210   if (TEST_BIT (visited, def_bb->index))
5211     return NULL_TREE;
5212
5213   SET_BIT (visited, def_bb->index);
5214
5215   switch (gimple_code (def_stmt))
5216     {
5217     case GIMPLE_PHI:
5218       for (i = 0; i < gimple_phi_num_args (def_stmt); i++)
5219         {
5220           tree arg = gimple_phi_arg_def (def_stmt, i);
5221           tree res = get_vdef_before_scop (scop, arg, visited);
5222           if (res)
5223             return res;
5224         }
5225       return NULL_TREE;
5226
5227     default:
5228       return NULL_TREE;
5229     }
5230 }
5231
5232 /* Adjust a virtual phi node PHI that is placed at the end of the
5233    generated code for SCOP:
5234
5235    | if (1)
5236    |   generated code from REGION;
5237    | else
5238    |   REGION;
5239
5240    The FALSE_E edge comes from the original code, TRUE_E edge comes
5241    from the code generated for the SCOP.  */
5242
5243 static void
5244 scop_adjust_vphi (scop_p scop, gimple phi, edge true_e)
5245 {
5246   unsigned i;
5247
5248   gcc_assert (gimple_phi_num_args (phi) == 2);
5249
5250   for (i = 0; i < gimple_phi_num_args (phi); i++)
5251     if (gimple_phi_arg_edge (phi, i) == true_e)
5252       {
5253         tree true_arg, false_arg, before_scop_arg;
5254         sbitmap visited;
5255
5256         true_arg = gimple_phi_arg_def (phi, i);
5257         if (!SSA_NAME_IS_DEFAULT_DEF (true_arg))
5258           return;
5259
5260         false_arg = gimple_phi_arg_def (phi, i == 0 ? 1 : 0);
5261         if (SSA_NAME_IS_DEFAULT_DEF (false_arg))
5262           return;
5263
5264         visited = sbitmap_alloc (last_basic_block);
5265         sbitmap_zero (visited);
5266         before_scop_arg = get_vdef_before_scop (scop, false_arg, visited);
5267         gcc_assert (before_scop_arg != NULL_TREE);
5268         SET_PHI_ARG_DEF (phi, i, before_scop_arg);
5269         sbitmap_free (visited);
5270       }
5271 }
5272
5273 /* Adjusts the phi nodes in the block BB for variables defined in
5274    SCOP_REGION and used outside the SCOP_REGION.  The code generation
5275    moves SCOP_REGION in the else clause of an "if (1)" and generates
5276    code in the then clause:
5277
5278    | if (1)
5279    |   generated code from REGION;
5280    | else
5281    |   REGION;
5282
5283    To adjust the phi nodes after the condition, SCOP_LIVEOUT_RENAMES
5284    hash table is used: this stores for a name that is part of the
5285    LIVEOUT of SCOP_REGION its new name in the generated code.  */
5286
5287 static void
5288 scop_adjust_phis_for_liveouts (scop_p scop, basic_block bb, edge false_e,
5289                                edge true_e)
5290 {
5291   gimple_stmt_iterator si;
5292
5293   for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
5294     {
5295       unsigned i;
5296       unsigned false_i = 0;
5297       gimple phi = gsi_stmt (si);
5298
5299       if (!is_gimple_reg (PHI_RESULT (phi)))
5300         {
5301           scop_adjust_vphi (scop, phi, true_e);
5302           continue;
5303         }
5304
5305       for (i = 0; i < gimple_phi_num_args (phi); i++)
5306         if (gimple_phi_arg_edge (phi, i) == false_e)
5307           {
5308             false_i = i;
5309             break;
5310           }
5311
5312       for (i = 0; i < gimple_phi_num_args (phi); i++)
5313         if (gimple_phi_arg_edge (phi, i) == true_e)
5314           {
5315             tree old_name = gimple_phi_arg_def (phi, false_i);
5316             tree new_name = get_new_name_from_old_name
5317               (SCOP_LIVEOUT_RENAMES (scop), old_name);
5318
5319             gcc_assert (old_name != new_name);
5320             SET_PHI_ARG_DEF (phi, i, new_name);
5321           }
5322     }
5323 }
5324
5325 /* Returns the first cloog name used in EXPR.  */
5326
5327 static const char *
5328 find_cloog_iv_in_expr (struct clast_expr *expr)
5329 {
5330   struct clast_term *term = (struct clast_term *) expr;
5331
5332   if (expr->type == expr_term
5333       && !term->var)
5334     return NULL;
5335
5336   if (expr->type == expr_term)
5337     return term->var;
5338
5339   if (expr->type == expr_red)
5340     {
5341       int i;
5342       struct clast_reduction *red = (struct clast_reduction *) expr;
5343
5344       for (i = 0; i < red->n; i++)
5345         {
5346           const char *res = find_cloog_iv_in_expr ((red)->elts[i]);
5347
5348           if (res)
5349             return res;
5350         }
5351     }
5352
5353   return NULL;
5354 }
5355
5356 /* Build for a clast_user_stmt USER_STMT a map between the CLAST
5357    induction variables and the corresponding GCC old induction
5358    variables.  This information is stored on each GRAPHITE_BB.  */
5359
5360 static void
5361 compute_cloog_iv_types_1 (graphite_bb_p gbb,
5362                           struct clast_user_stmt *user_stmt)
5363 {
5364   struct clast_stmt *t;
5365   int index = 0;
5366
5367   for (t = user_stmt->substitutions; t; t = t->next, index++)
5368     {
5369       PTR *slot;
5370       struct ivtype_map_elt tmp;
5371       struct clast_expr *expr = (struct clast_expr *)
5372         ((struct clast_assignment *)t)->RHS;
5373
5374       /* Create an entry (clast_var, type).  */
5375       tmp.cloog_iv = find_cloog_iv_in_expr (expr);
5376       if (!tmp.cloog_iv)
5377         continue;
5378
5379       slot = htab_find_slot (GBB_CLOOG_IV_TYPES (gbb), &tmp, INSERT);
5380
5381       if (!*slot)
5382         {
5383           loop_p loop = gbb_loop_at_index (gbb, index);
5384           tree oldiv = oldiv_for_loop (GBB_SCOP (gbb), loop);
5385           tree type = oldiv ? TREE_TYPE (oldiv) : integer_type_node;
5386           *slot = new_ivtype_map_elt (tmp.cloog_iv, type);
5387         }
5388     }
5389 }
5390
5391 /* Walk the CLAST tree starting from STMT and build for each
5392    clast_user_stmt a map between the CLAST induction variables and the
5393    corresponding GCC old induction variables.  This information is
5394    stored on each GRAPHITE_BB.  */
5395
5396 static void
5397 compute_cloog_iv_types (struct clast_stmt *stmt)
5398 {
5399   if (!stmt)
5400     return;
5401
5402   if (CLAST_STMT_IS_A (stmt, stmt_root))
5403     goto next;
5404
5405   if (CLAST_STMT_IS_A (stmt, stmt_user))
5406     {
5407       CloogStatement *cs = ((struct clast_user_stmt *) stmt)->statement;
5408       graphite_bb_p gbb = (graphite_bb_p) cloog_statement_usr (cs);
5409       GBB_CLOOG_IV_TYPES (gbb) = htab_create (10, ivtype_map_elt_info,
5410                                               eq_ivtype_map_elts, free);
5411       compute_cloog_iv_types_1 (gbb, (struct clast_user_stmt *) stmt);
5412       goto next;
5413     }
5414
5415   if (CLAST_STMT_IS_A (stmt, stmt_for))
5416     {
5417       struct clast_stmt *s = ((struct clast_for *) stmt)->body;
5418       compute_cloog_iv_types (s);
5419       goto next;
5420     }
5421
5422   if (CLAST_STMT_IS_A (stmt, stmt_guard))
5423     {
5424       struct clast_stmt *s = ((struct clast_guard *) stmt)->then;
5425       compute_cloog_iv_types (s);
5426       goto next;
5427     }
5428
5429   if (CLAST_STMT_IS_A (stmt, stmt_block))
5430     {
5431       struct clast_stmt *s = ((struct clast_block *) stmt)->body;
5432       compute_cloog_iv_types (s);
5433       goto next;
5434     }
5435
5436   gcc_unreachable ();
5437
5438  next:
5439   compute_cloog_iv_types (stmt->next);
5440 }
5441
5442 /* GIMPLE Loop Generator: generates loops from STMT in GIMPLE form for
5443    the given SCOP.  Return true if code generation succeeded.  */
5444
5445 static bool
5446 gloog (scop_p scop, struct clast_stmt *stmt)
5447 {
5448   edge new_scop_exit_edge = NULL;
5449   VEC (iv_stack_entry_p, heap) *ivstack = VEC_alloc (iv_stack_entry_p, heap,
5450                                                      10);
5451   loop_p context_loop;
5452   ifsese if_region = NULL;
5453
5454   recompute_all_dominators ();
5455   graphite_verify ();
5456   if_region = move_sese_in_condition (SCOP_REGION (scop));
5457   sese_build_livein_liveouts (SCOP_REGION (scop));
5458   scop_insert_phis_for_liveouts (SCOP_REGION (scop),
5459                                  if_region->region->exit->src,
5460                                  if_region->false_region->exit,
5461                                  if_region->true_region->exit);
5462   recompute_all_dominators ();
5463   graphite_verify ();
5464   context_loop = SESE_ENTRY (SCOP_REGION (scop))->src->loop_father;
5465   compute_cloog_iv_types (stmt);
5466
5467   new_scop_exit_edge = translate_clast (scop, context_loop, stmt,
5468                                         if_region->true_region->entry,
5469                                         &ivstack);
5470   free_loop_iv_stack (&ivstack);
5471   cloog_clast_free (stmt);
5472
5473   graphite_verify ();
5474   scop_adjust_phis_for_liveouts (scop,
5475                                  if_region->region->exit->src,
5476                                  if_region->false_region->exit,
5477                                  if_region->true_region->exit);
5478
5479   recompute_all_dominators ();
5480   graphite_verify ();
5481   return true;
5482 }
5483
5484 /* Returns the number of data references in SCOP.  */
5485
5486 static int
5487 nb_data_refs_in_scop (scop_p scop)
5488 {
5489   int i;
5490   graphite_bb_p gbb;
5491   int res = 0;
5492
5493   for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gbb); i++)
5494     res += VEC_length (data_reference_p, GBB_DATA_REFS (gbb));
5495
5496   return res;
5497 }
5498
5499 /* Move the loop at index LOOP and insert it before index NEW_LOOP_POS.
5500    This transformartion is only valid, if the loop nest between i and k is
5501    perfectly nested. Therefore we do not need to change the static schedule.
5502
5503    Example:
5504
5505    for (i = 0; i < 50; i++)
5506      for (j ...)
5507        for (k = 5; k < 100; k++)
5508          A
5509
5510    To move k before i use:
5511
5512    graphite_trans_bb_move_loop (A, 2, 0)
5513
5514    for (k = 5; k < 100; k++)
5515      for (i = 0; i < 50; i++)
5516        for (j ...)
5517          A
5518
5519    And to move k back:
5520
5521    graphite_trans_bb_move_loop (A, 0, 2)
5522
5523    This function does not check the validity of interchanging loops.
5524    This should be checked before calling this function.  */
5525
5526 static void
5527 graphite_trans_bb_move_loop (graphite_bb_p gb, int loop,
5528                              int new_loop_pos)
5529 {
5530   CloogMatrix *domain = GBB_DOMAIN (gb);
5531   int row, j;
5532   loop_p tmp_loop_p;
5533
5534   gcc_assert (loop < gbb_nb_loops (gb)
5535               && new_loop_pos < gbb_nb_loops (gb));
5536
5537   /* Update LOOPS vector.  */
5538   tmp_loop_p = VEC_index (loop_p, GBB_LOOPS (gb), loop);
5539   VEC_ordered_remove (loop_p, GBB_LOOPS (gb), loop);
5540   VEC_safe_insert (loop_p, heap, GBB_LOOPS (gb), new_loop_pos, tmp_loop_p);
5541
5542   /* Move the domain columns.  */
5543   if (loop < new_loop_pos)
5544     for (row = 0; row < domain->NbRows; row++)
5545       {
5546         Value tmp;
5547         value_init (tmp);
5548         value_assign (tmp, domain->p[row][loop + 1]);
5549
5550         for (j = loop ; j < new_loop_pos - 1; j++)
5551           value_assign (domain->p[row][j + 1], domain->p[row][j + 2]);
5552
5553         value_assign (domain->p[row][new_loop_pos], tmp);
5554         value_clear (tmp);
5555       }
5556   else
5557     for (row = 0; row < domain->NbRows; row++)
5558       {
5559         Value tmp;
5560         value_init (tmp);
5561         value_assign (tmp, domain->p[row][loop + 1]);
5562
5563         for (j = loop ; j > new_loop_pos; j--)
5564           value_assign (domain->p[row][j + 1], domain->p[row][j]);
5565
5566         value_assign (domain->p[row][new_loop_pos + 1], tmp);
5567         value_clear (tmp);
5568       }
5569 }
5570
5571 /* Get the index of the column representing constants in the DOMAIN
5572    matrix.  */
5573
5574 static int
5575 const_column_index (CloogMatrix *domain)
5576 {
5577   return domain->NbColumns - 1;
5578 }
5579
5580
5581 /* Get the first index that is positive or negative, determined
5582    following the value of POSITIVE, in matrix DOMAIN in COLUMN.  */
5583
5584 static int
5585 get_first_matching_sign_row_index (CloogMatrix *domain, int column,
5586                                    bool positive)
5587 {
5588   int row;
5589
5590   for (row = 0; row < domain->NbRows; row++)
5591     {
5592       int val = value_get_si (domain->p[row][column]);
5593
5594       if (val > 0 && positive)
5595         return row;
5596
5597       else if (val < 0 && !positive)
5598         return row;
5599     }
5600
5601   gcc_unreachable ();
5602 }
5603
5604 /* Get the lower bound of COLUMN in matrix DOMAIN.  */
5605
5606 static int
5607 get_lower_bound_row (CloogMatrix *domain, int column)
5608 {
5609   return get_first_matching_sign_row_index (domain, column, true);
5610 }
5611
5612 /* Get the upper bound of COLUMN in matrix DOMAIN.  */
5613
5614 static int
5615 get_upper_bound_row (CloogMatrix *domain, int column)
5616 {
5617   return get_first_matching_sign_row_index (domain, column, false);
5618 }
5619
5620 /* Copies the OLD_ROW constraint from OLD_DOMAIN to the NEW_DOMAIN at
5621    row NEW_ROW.  */
5622
5623 static void
5624 copy_constraint (CloogMatrix *old_domain, CloogMatrix *new_domain,
5625                  int old_row, int new_row)
5626 {
5627   int i;
5628
5629   gcc_assert (old_domain->NbColumns == new_domain->NbColumns
5630               && old_row < old_domain->NbRows
5631               && new_row < new_domain->NbRows);
5632
5633   for (i = 0; i < old_domain->NbColumns; i++)
5634     value_assign (new_domain->p[new_row][i], old_domain->p[old_row][i]);
5635 }
5636
5637 /* Swap coefficients of variables X and Y on row R.   */
5638
5639 static void
5640 swap_constraint_variables (CloogMatrix *domain,
5641                            int r, int x, int y)
5642 {
5643   value_swap (domain->p[r][x], domain->p[r][y]);
5644 }
5645
5646 /* Scale by X the coefficient C of constraint at row R in DOMAIN.  */
5647
5648 static void
5649 scale_constraint_variable (CloogMatrix *domain,
5650                            int r, int c, int x)
5651 {
5652   Value strip_size_value;
5653   value_init (strip_size_value);
5654   value_set_si (strip_size_value, x);
5655   value_multiply (domain->p[r][c], domain->p[r][c], strip_size_value);
5656   value_clear (strip_size_value);
5657 }
5658
5659 /* Strip mines the loop of BB at the position LOOP_DEPTH with STRIDE.
5660    Always valid, but not always a performance improvement.  */
5661
5662 static void
5663 graphite_trans_bb_strip_mine (graphite_bb_p gb, int loop_depth, int stride)
5664 {
5665   int row, col;
5666
5667   CloogMatrix *domain = GBB_DOMAIN (gb);
5668   CloogMatrix *new_domain = cloog_matrix_alloc (domain->NbRows + 3,
5669                                                 domain->NbColumns + 1);
5670
5671   int col_loop_old = loop_depth + 2;
5672   int col_loop_strip = col_loop_old - 1;
5673
5674   gcc_assert (loop_depth <= gbb_nb_loops (gb) - 1);
5675
5676   VEC_safe_insert (loop_p, heap, GBB_LOOPS (gb), loop_depth, NULL);
5677
5678   GBB_DOMAIN (gb) = new_domain;
5679
5680   for (row = 0; row < domain->NbRows; row++)
5681     for (col = 0; col < domain->NbColumns; col++)
5682       if (col <= loop_depth)
5683         value_assign (new_domain->p[row][col], domain->p[row][col]);
5684       else
5685         value_assign (new_domain->p[row][col + 1], domain->p[row][col]);
5686
5687   row = domain->NbRows;
5688
5689   /* Lower bound of the outer stripped loop.  */
5690   copy_constraint (new_domain, new_domain,
5691                    get_lower_bound_row (new_domain, col_loop_old), row);
5692   swap_constraint_variables (new_domain, row, col_loop_old, col_loop_strip);
5693   row++;
5694
5695   /* Upper bound of the outer stripped loop.  */
5696   copy_constraint (new_domain, new_domain,
5697                    get_upper_bound_row (new_domain, col_loop_old), row);
5698   swap_constraint_variables (new_domain, row, col_loop_old, col_loop_strip);
5699   scale_constraint_variable (new_domain, row, col_loop_strip, stride);
5700   row++;
5701
5702   /* Lower bound of a tile starts at "stride * outer_iv".  */
5703   row = get_lower_bound_row (new_domain, col_loop_old);
5704   value_set_si (new_domain->p[row][0], 1);
5705   value_set_si (new_domain->p[row][const_column_index (new_domain)], 0);
5706   value_set_si (new_domain->p[row][col_loop_old], 1);
5707   value_set_si (new_domain->p[row][col_loop_strip], -1 * stride);
5708
5709   /* Upper bound of a tile stops at "stride * outer_iv + stride - 1",
5710      or at the old upper bound that is not modified.  */
5711   row = new_domain->NbRows - 1;
5712   value_set_si (new_domain->p[row][0], 1);
5713   value_set_si (new_domain->p[row][col_loop_old], -1);
5714   value_set_si (new_domain->p[row][col_loop_strip], stride);
5715   value_set_si (new_domain->p[row][const_column_index (new_domain)],
5716                 stride - 1);
5717
5718   cloog_matrix_free (domain);
5719
5720   /* Update static schedule.  */
5721   {
5722     int i;
5723     int nb_loops = gbb_nb_loops (gb);
5724     lambda_vector new_schedule = lambda_vector_new (nb_loops + 1);
5725
5726     for (i = 0; i <= loop_depth; i++)
5727       new_schedule[i] = GBB_STATIC_SCHEDULE (gb)[i];
5728
5729     for (i = loop_depth + 1; i <= nb_loops - 2; i++)
5730       new_schedule[i + 2] = GBB_STATIC_SCHEDULE (gb)[i];
5731
5732     GBB_STATIC_SCHEDULE (gb) = new_schedule;
5733   }
5734 }
5735
5736 /* Returns true when the strip mining of LOOP_INDEX by STRIDE is
5737    profitable or undecidable.  GB is the statement around which the
5738    loops will be strip mined.  */
5739
5740 static bool
5741 strip_mine_profitable_p (graphite_bb_p gb, int stride,
5742                          int loop_index)
5743 {
5744   bool res = true;
5745   edge exit = NULL;
5746   tree niter;
5747   loop_p loop;
5748   long niter_val;
5749
5750   loop = VEC_index (loop_p, GBB_LOOPS (gb), loop_index);
5751   exit = single_exit (loop);
5752
5753   niter = find_loop_niter (loop, &exit);
5754   if (niter == chrec_dont_know
5755       || TREE_CODE (niter) != INTEGER_CST)
5756     return true;
5757
5758   niter_val = int_cst_value (niter);
5759
5760   if (niter_val < stride)
5761     {
5762       res = false;
5763       if (dump_file && (dump_flags & TDF_DETAILS))
5764         {
5765           fprintf (dump_file, "\nStrip Mining is not profitable for loop %d:",
5766                    loop->num);
5767           fprintf (dump_file, "number of iterations is too low.\n");
5768         }
5769     }
5770
5771   return res;
5772 }
5773
5774 /* Determines when the interchange of LOOP_A and LOOP_B belonging to
5775    SCOP is legal.  DEPTH is the number of loops around.  */
5776
5777 static bool
5778 is_interchange_valid (scop_p scop, int loop_a, int loop_b, int depth)
5779 {
5780   bool res;
5781   VEC (ddr_p, heap) *dependence_relations;
5782   VEC (data_reference_p, heap) *datarefs;
5783
5784   struct loop *nest = VEC_index (loop_p, SCOP_LOOP_NEST (scop), loop_a);
5785   lambda_trans_matrix trans;
5786
5787   gcc_assert (loop_a < loop_b);
5788
5789   dependence_relations = VEC_alloc (ddr_p, heap, 10 * 10);
5790   datarefs = VEC_alloc (data_reference_p, heap, 10);
5791
5792   if (!compute_data_dependences_for_loop (nest, true, &datarefs,
5793                                           &dependence_relations))
5794     return false;
5795
5796   if (dump_file && (dump_flags & TDF_DETAILS))
5797     dump_ddrs (dump_file, dependence_relations);
5798
5799   trans = lambda_trans_matrix_new (depth, depth);
5800   lambda_matrix_id (LTM_MATRIX (trans), depth);
5801
5802   lambda_matrix_row_exchange (LTM_MATRIX (trans), 0, loop_b - loop_a);
5803
5804   if (!lambda_transform_legal_p (trans, depth, dependence_relations))
5805     {
5806       lambda_matrix_row_exchange (LTM_MATRIX (trans), 0, loop_b - loop_a);
5807       res = false;
5808     }
5809   else
5810     res = true;
5811
5812   free_dependence_relations (dependence_relations);
5813   free_data_refs (datarefs);
5814   return res;
5815 }
5816
5817 /* Loop block the LOOPS innermost loops of GB with stride size STRIDE.
5818
5819    Example
5820
5821    for (i = 0; i <= 50; i++=4)
5822      for (k = 0; k <= 100; k++=4)
5823        for (l = 0; l <= 200; l++=4)
5824          A
5825
5826    To strip mine the two inner most loops with stride = 4 call:
5827
5828    graphite_trans_bb_block (A, 4, 2)
5829
5830    for (i = 0; i <= 50; i++)
5831      for (kk = 0; kk <= 100; kk+=4)
5832        for (ll = 0; ll <= 200; ll+=4)
5833          for (k = kk; k <= min (100, kk + 3); k++)
5834            for (l = ll; l <= min (200, ll + 3); l++)
5835              A
5836 */
5837
5838 static bool
5839 graphite_trans_bb_block (graphite_bb_p gb, int stride, int loops)
5840 {
5841   int i, j;
5842   int nb_loops = gbb_nb_loops (gb);
5843   int start = nb_loops - loops;
5844   scop_p scop = GBB_SCOP (gb);
5845
5846   gcc_assert (scop_contains_loop (scop, gbb_loop (gb)));
5847
5848   for (i = start ; i < nb_loops; i++)
5849     for (j = i + 1; j < nb_loops; j++)
5850       if (!is_interchange_valid (scop, i, j, nb_loops))
5851         {
5852           if (dump_file && (dump_flags & TDF_DETAILS))
5853             fprintf (dump_file,
5854                      "\nInterchange not valid for loops %d and %d:\n", i, j);
5855           return false;
5856         }
5857       else if (dump_file && (dump_flags & TDF_DETAILS))
5858         fprintf (dump_file,
5859                  "\nInterchange valid for loops %d and %d:\n", i, j);
5860
5861   /* Check if strip mining is profitable for every loop.  */
5862   for (i = 0; i < nb_loops - start; i++)
5863     if (!strip_mine_profitable_p (gb, stride, start + i))
5864       return false;
5865
5866   /* Strip mine loops.  */
5867   for (i = 0; i < nb_loops - start; i++)
5868     graphite_trans_bb_strip_mine (gb, start + 2 * i, stride);
5869
5870   /* Interchange loops.  */
5871   for (i = 1; i < nb_loops - start; i++)
5872     graphite_trans_bb_move_loop (gb, start + 2 * i, start + i);
5873
5874   if (dump_file && (dump_flags & TDF_DETAILS))
5875     fprintf (dump_file, "\nLoops containing BB %d will be loop blocked.\n",
5876              GBB_BB (gb)->index);
5877
5878   return true;
5879 }
5880
5881 /* Loop block LOOPS innermost loops of a loop nest.  BBS represent the
5882    basic blocks that belong to the loop nest to be blocked.  */
5883
5884 static bool
5885 graphite_trans_loop_block (VEC (graphite_bb_p, heap) *bbs, int loops)
5886 {
5887   graphite_bb_p gb;
5888   int i;
5889   bool transform_done = false;
5890
5891   /* TODO: - Calculate the stride size automatically.  */
5892   int stride_size = 51;
5893
5894   for (i = 0; VEC_iterate (graphite_bb_p, bbs, i, gb); i++)
5895     transform_done |= graphite_trans_bb_block (gb, stride_size, loops);
5896
5897   return transform_done;
5898 }
5899
5900 /* Loop block all basic blocks of SCOP.  Return false when the
5901    transform is not performed.  */
5902
5903 static bool
5904 graphite_trans_scop_block (scop_p scop)
5905 {
5906   graphite_bb_p gb;
5907   int i, j;
5908   int last_nb_loops;
5909   int nb_loops;
5910   bool perfect = true;
5911   bool transform_done = false;
5912
5913   VEC (graphite_bb_p, heap) *bbs = VEC_alloc (graphite_bb_p, heap, 3);
5914   int max_schedule = scop_max_loop_depth (scop) + 1;
5915   lambda_vector last_schedule = lambda_vector_new (max_schedule);
5916
5917   if (VEC_length (graphite_bb_p, SCOP_BBS (scop)) == 0)
5918     return false;
5919
5920   /* Get the data of the first bb.  */
5921   gb = VEC_index (graphite_bb_p, SCOP_BBS (scop), 0);
5922   last_nb_loops = gbb_nb_loops (gb);
5923   lambda_vector_copy (GBB_STATIC_SCHEDULE (gb), last_schedule,
5924                       last_nb_loops + 1);
5925   VEC_safe_push (graphite_bb_p, heap, bbs, gb);
5926
5927   for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
5928     {
5929       /* We did the first bb before.  */
5930       if (i == 0)
5931         continue;
5932
5933       nb_loops = gbb_nb_loops (gb);
5934
5935       /* If the number of loops is unchanged and only the last element of the
5936          schedule changes, we stay in the loop nest.  */
5937       if (nb_loops == last_nb_loops
5938           && (last_schedule [nb_loops + 1]
5939               != GBB_STATIC_SCHEDULE (gb)[nb_loops + 1]))
5940         {
5941           VEC_safe_push (graphite_bb_p, heap, bbs, gb);
5942           continue;
5943         }
5944
5945       /* Otherwise, we left the innermost loop. So check, if the last bb was in
5946          a perfect loop nest and how many loops are contained in this perfect
5947          loop nest.
5948
5949          Count the number of zeros from the end of the schedule. They are the
5950          number of surrounding loops.
5951
5952          Example:
5953          last_bb  2 3 2 0 0 0 0 3
5954          bb       2 4 0
5955          <------  j = 4
5956
5957          last_bb  2 3 2 0 0 0 0 3
5958          bb       2 3 2 0 1
5959          <--  j = 2
5960
5961          If there is no zero, there were other bbs in outer loops and the loop
5962          nest is not perfect.  */
5963       for (j = last_nb_loops - 1; j >= 0; j--)
5964         {
5965           if (last_schedule [j] != 0
5966               || (j <= nb_loops && GBB_STATIC_SCHEDULE (gb)[j] == 1))
5967             {
5968               j--;
5969               break;
5970             }
5971         }
5972
5973       j++;
5974
5975       /* Found perfect loop nest.  */
5976       if (perfect && last_nb_loops - j >= 2)
5977         transform_done |= graphite_trans_loop_block (bbs, last_nb_loops - j);
5978
5979       /* Check if we start with a new loop.
5980
5981          Example:
5982
5983          last_bb  2 3 2 0 0 0 0 3
5984          bb       2 3 2 0 0 1 0
5985
5986          Here we start with the loop "2 3 2 0 0 1"
5987
5988          last_bb  2 3 2 0 0 0 0 3
5989          bb       2 3 2 0 0 1
5990
5991          But here not, so the loop nest can never be perfect.  */
5992
5993       perfect = (GBB_STATIC_SCHEDULE (gb)[nb_loops] == 0);
5994
5995       /* Update the last_bb infos.  We do not do that for the bbs in the same
5996          loop, as the data we use is not changed.  */
5997       last_nb_loops = nb_loops;
5998       lambda_vector_copy (GBB_STATIC_SCHEDULE (gb), last_schedule,
5999                           nb_loops + 1);
6000       VEC_truncate (graphite_bb_p, bbs, 0);
6001       VEC_safe_push (graphite_bb_p, heap, bbs, gb);
6002     }
6003
6004   /* Check if the last loop nest was perfect.  It is the same check as above,
6005      but the comparison with the next bb is missing.  */
6006   for (j = last_nb_loops - 1; j >= 0; j--)
6007     if (last_schedule [j] != 0)
6008       {
6009         j--;
6010         break;
6011       }
6012
6013   j++;
6014
6015   /* Found perfect loop nest.  */
6016   if (last_nb_loops - j >= 2)
6017     transform_done |= graphite_trans_loop_block (bbs, last_nb_loops - j);
6018   VEC_free (graphite_bb_p, heap, bbs);
6019
6020   return transform_done;
6021 }
6022
6023 /* Apply graphite transformations to all the basic blocks of SCOP.  */
6024
6025 static bool
6026 graphite_apply_transformations (scop_p scop)
6027 {
6028   bool transform_done = false;
6029
6030   /* Sort the list of bbs.  Keep them always sorted.  */
6031   graphite_sort_gbbs (scop);
6032
6033   if (flag_loop_block)
6034     transform_done = graphite_trans_scop_block (scop);
6035
6036   /* Generate code even if we did not apply any real transformation.
6037      This also allows to check the performance for the identity
6038      transformation: GIMPLE -> GRAPHITE -> GIMPLE
6039      Keep in mind that CLooG optimizes in control, so the loop structure
6040      may change, even if we only use -fgraphite-identity.  */
6041   if (flag_graphite_identity)
6042     transform_done = true;
6043
6044   return transform_done;
6045 }
6046
6047 /* We limit all SCoPs to SCoPs, that are completely surrounded by a loop.
6048
6049    Example:
6050
6051    for (i      |
6052      {         |
6053        for (j  |  SCoP 1
6054        for (k  |
6055      }         |
6056
6057    * SCoP frontier, as this line is not surrounded by any loop. *
6058
6059    for (l      |  SCoP 2
6060
6061    This is necessary as scalar evolution and parameter detection need a
6062    outermost loop to initialize parameters correctly.
6063
6064    TODO: FIX scalar evolution and parameter detection to allow more flexible
6065          SCoP frontiers.  */
6066
6067 static void
6068 limit_scops (void)
6069 {
6070   VEC (sd_region, heap) *tmp_scops = VEC_alloc (sd_region, heap, 3);
6071
6072   int i;
6073   scop_p scop;
6074
6075   for (i = 0; VEC_iterate (scop_p, current_scops, i, scop); i++)
6076     {
6077       int j;
6078       loop_p loop;
6079       build_scop_bbs (scop);
6080
6081       if (!build_scop_loop_nests (scop))
6082         continue;
6083
6084       for (j = 0; VEC_iterate (loop_p, SCOP_LOOP_NEST (scop), j, loop); j++)
6085         if (!loop_in_sese_p (loop_outer (loop), SCOP_REGION (scop)))
6086           {
6087             sd_region open_scop;
6088             open_scop.entry = loop->header;
6089             open_scop.exit = single_exit (loop)->dest;
6090             VEC_safe_push (sd_region, heap, tmp_scops, &open_scop);
6091           }
6092     }
6093
6094   free_scops (current_scops);
6095   current_scops = VEC_alloc (scop_p, heap, 3);
6096
6097   create_sese_edges (tmp_scops);
6098   build_graphite_scops (tmp_scops);
6099   VEC_free (sd_region, heap, tmp_scops);
6100 }
6101
6102 /* Perform a set of linear transforms on the loops of the current
6103    function.  */
6104
6105 void
6106 graphite_transform_loops (void)
6107 {
6108   int i;
6109   scop_p scop;
6110   bool transform_done = false;
6111
6112   if (number_of_loops () <= 1)
6113     return;
6114
6115   current_scops = VEC_alloc (scop_p, heap, 3);
6116   recompute_all_dominators ();
6117
6118   if (dump_file && (dump_flags & TDF_DETAILS))
6119     fprintf (dump_file, "Graphite loop transformations \n");
6120
6121   initialize_original_copy_tables ();
6122   cloog_initialize ();
6123   build_scops ();
6124   limit_scops ();
6125
6126   if (dump_file && (dump_flags & TDF_DETAILS))
6127     fprintf (dump_file, "\nnumber of SCoPs: %d\n",
6128              VEC_length (scop_p, current_scops));
6129
6130   for (i = 0; VEC_iterate (scop_p, current_scops, i, scop); i++)
6131     {
6132       build_scop_bbs (scop);
6133       if (!build_scop_loop_nests (scop))
6134         continue;
6135
6136       build_bb_loops (scop);
6137
6138       if (!build_scop_conditions (scop))
6139         continue;
6140
6141       find_scop_parameters (scop);
6142       build_scop_context (scop);
6143
6144       if (dump_file && (dump_flags & TDF_DETAILS))
6145         {
6146           fprintf (dump_file, "\n(In SCoP %d:\n", i);
6147           fprintf (dump_file, "\nnumber of bbs: %d\n",
6148                    VEC_length (graphite_bb_p, SCOP_BBS (scop)));
6149           fprintf (dump_file, "\nnumber of loops: %d)\n",
6150                    VEC_length (loop_p, SCOP_LOOP_NEST (scop)));
6151         }
6152
6153       if (!build_scop_iteration_domain (scop))
6154         continue;
6155
6156       add_conditions_to_constraints (scop);
6157       build_scop_canonical_schedules (scop);
6158
6159       build_scop_data_accesses (scop);
6160       build_scop_dynamic_schedules (scop);
6161
6162       if (dump_file && (dump_flags & TDF_DETAILS))
6163         {
6164           int nbrefs = nb_data_refs_in_scop (scop);
6165           fprintf (dump_file, "\nnumber of data refs: %d\n", nbrefs);
6166         }
6167
6168       if (graphite_apply_transformations (scop))
6169         transform_done = gloog (scop, find_transform (scop));
6170 #ifdef ENABLE_CHECKING
6171       else
6172         {
6173           struct clast_stmt *stmt = find_transform (scop);
6174           cloog_clast_free (stmt);
6175         }
6176 #endif
6177     }
6178
6179   /* Cleanup.  */
6180   if (transform_done)
6181     cleanup_tree_cfg ();
6182
6183   free_scops (current_scops);
6184   cloog_finalize ();
6185   free_original_copy_tables ();
6186 }
6187
6188 #else /* If Cloog is not available: #ifndef HAVE_cloog.  */
6189
6190 void
6191 graphite_transform_loops (void)
6192 {
6193   sorry ("Graphite loop optimizations cannot be used");
6194 }
6195
6196 #endif