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
  60 /* The CLooG header file is not -Wc++-compat ready as of 2009-05-11.
  61    This #pragma should be removed when it is ready.  */
  62 #if GCC_VERSION >= 4003
  63 #pragma GCC diagnostic warning "-Wc++-compat"
  64 #endif
  65
  66 #include "cloog/cloog.h"
  67 #include "graphite.h"
  68
  69 static VEC (scop_p, heap) *current_scops;
  70
  71 /* Converts a GMP constant V to a tree and returns it.  */
  72
  73 static tree
  74 gmp_cst_to_tree (tree type, Value v)
  75 {
  76   return build_int_cst (type, value_get_si (v));
  77 }
  78
  79 /* Returns true when BB is in REGION.  */
  80
  81 static bool
  82 bb_in_sese_p (basic_block bb, sese region)
  83 {
  84   return pointer_set_contains (SESE_REGION_BBS (region), bb);
  85 }
  86
  87 /* Returns true when LOOP is in the SESE region R.  */
  88
  89 static inline bool
  90 loop_in_sese_p (struct loop *loop, sese r)
  91 {
  92   return (bb_in_sese_p (loop->header, r)
  93           && bb_in_sese_p (loop->latch, r));
  94 }
  95
  96 /* For a USE in BB, if BB is outside REGION, mark the USE in the
  97    SESE_LIVEIN and SESE_LIVEOUT sets.  */
  98
  99 static void
 100 sese_build_livein_liveouts_use (sese region, basic_block bb, tree use)
 101 {
 102   unsigned ver;
 103   basic_block def_bb;
 104
 105   if (TREE_CODE (use) != SSA_NAME)
 106     return;
 107
 108   ver = SSA_NAME_VERSION (use);
 109   def_bb = gimple_bb (SSA_NAME_DEF_STMT (use));
 110   if (!def_bb
 111       || !bb_in_sese_p (def_bb, region)
 112       || bb_in_sese_p (bb, region))
 113     return;
 114
 115   if (!SESE_LIVEIN_VER (region, ver))
 116     SESE_LIVEIN_VER (region, ver) = BITMAP_ALLOC (NULL);
 117
 118   bitmap_set_bit (SESE_LIVEIN_VER (region, ver), bb->index);
 119   bitmap_set_bit (SESE_LIVEOUT (region), ver);
 120 }
 121
 122 /* Marks for rewrite all the SSA_NAMES defined in REGION and that are
 123    used in BB that is outside of the REGION.  */
 124
 125 static void
 126 sese_build_livein_liveouts_bb (sese region, basic_block bb)
 127 {
 128   gimple_stmt_iterator bsi;
 129   edge e;
 130   edge_iterator ei;
 131   ssa_op_iter iter;
 132   tree var;
 133
 134   FOR_EACH_EDGE (e, ei, bb->succs)
 135     for (bsi = gsi_start_phis (e->dest); !gsi_end_p (bsi); gsi_next (&bsi))
 136       sese_build_livein_liveouts_use (region, bb,
 137                                       PHI_ARG_DEF_FROM_EDGE (gsi_stmt (bsi), e));
 138
 139   for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
 140     FOR_EACH_SSA_TREE_OPERAND (var, gsi_stmt (bsi), iter, SSA_OP_ALL_USES)
 141       sese_build_livein_liveouts_use (region, bb, var);
 142 }
 143
 144 /* Build the SESE_LIVEIN and SESE_LIVEOUT for REGION.  */
 145
 146 void
 147 sese_build_livein_liveouts (sese region)
 148 {
 149   basic_block bb;
 150
 151   SESE_LIVEOUT (region) = BITMAP_ALLOC (NULL);
 152   SESE_NUM_VER (region) = num_ssa_names;
 153   SESE_LIVEIN (region) = XCNEWVEC (bitmap, SESE_NUM_VER (region));
 154
 155   FOR_EACH_BB (bb)
 156     sese_build_livein_liveouts_bb (region, bb);
 157 }
 158
 159 /* Register basic blocks belonging to a region in a pointer set.  */
 160
 161 static void
 162 register_bb_in_sese (basic_block entry_bb, basic_block exit_bb, sese region)
 163 {
 164   edge_iterator ei;
 165   edge e;
 166   basic_block bb = entry_bb;
 167
 168   FOR_EACH_EDGE (e, ei, bb->succs)
 169     {
 170       if (!pointer_set_contains (SESE_REGION_BBS (region), e->dest) &&
 171           e->dest->index != exit_bb->index)
 172         {
 173           pointer_set_insert (SESE_REGION_BBS (region), e->dest);
 174           register_bb_in_sese (e->dest, exit_bb, region);
 175         }
 176     }
 177 }
 178
 179 /* Builds a new SESE region from edges ENTRY and EXIT.  */
 180
 181 sese
 182 new_sese (edge entry, edge exit)
 183 {
 184   sese res = XNEW (struct sese_d);
 185
 186   SESE_ENTRY (res) = entry;
 187   SESE_EXIT (res) = exit;
 188   SESE_REGION_BBS (res) = pointer_set_create ();
 189   register_bb_in_sese (entry->dest, exit->dest, res);
 190
 191   SESE_LIVEOUT (res) = NULL;
 192   SESE_NUM_VER (res) = 0;
 193   SESE_LIVEIN (res) = NULL;
 194
 195   return res;
 196 }
 197
 198 /* Deletes REGION.  */
 199
 200 void
 201 free_sese (sese region)
 202 {
 203   int i;
 204
 205   for (i = 0; i < SESE_NUM_VER (region); i++)
 206     BITMAP_FREE (SESE_LIVEIN_VER (region, i));
 207
 208   if (SESE_LIVEIN (region))
 209     free (SESE_LIVEIN (region));
 210
 211   if (SESE_LIVEOUT (region))
 212     BITMAP_FREE (SESE_LIVEOUT (region));
 213
 214   pointer_set_destroy (SESE_REGION_BBS (region));
 215   XDELETE (region);
 216 }
 217
 218 \f
 219
 220 /* Debug the list of old induction variables for this SCOP.  */
 221
 222 void
 223 debug_oldivs (scop_p scop)
 224 {
 225   int i;
 226   name_tree oldiv;
 227
 228   fprintf (stderr, "Old IVs:");
 229
 230   for (i = 0; VEC_iterate (name_tree, SCOP_OLDIVS (scop), i, oldiv); i++)
 231     {
 232       fprintf (stderr, "(");
 233       print_generic_expr (stderr, oldiv->t, 0);
 234       fprintf (stderr, ", %s, %d)\n", oldiv->name, oldiv->loop->num);
 235     }
 236   fprintf (stderr, "\n");
 237 }
 238
 239 /* Debug the loops around basic block GB.  */
 240
 241 void
 242 debug_loop_vec (graphite_bb_p gb)
 243 {
 244   int i;
 245   loop_p loop;
 246
 247   fprintf (stderr, "Loop Vec:");
 248
 249   for (i = 0; VEC_iterate (loop_p, GBB_LOOPS (gb), i, loop); i++)
 250     fprintf (stderr, "%d: %d, ", i, loop ? loop->num : -1);
 251
 252   fprintf (stderr, "\n");
 253 }
 254
 255 /* Returns true if stack ENTRY is a constant.  */
 256
 257 static bool
 258 iv_stack_entry_is_constant (iv_stack_entry *entry)
 259 {
 260   return entry->kind == iv_stack_entry_const;
 261 }
 262
 263 /* Returns true if stack ENTRY is an induction variable.  */
 264
 265 static bool
 266 iv_stack_entry_is_iv (iv_stack_entry *entry)
 267 {
 268   return entry->kind == iv_stack_entry_iv;
 269 }
 270
 271 /* Push (IV, NAME) on STACK.  */
 272
 273 static void
 274 loop_iv_stack_push_iv (loop_iv_stack stack, tree iv, const char *name)
 275 {
 276   iv_stack_entry *entry = XNEW (iv_stack_entry);
 277   name_tree named_iv = XNEW (struct name_tree_d);
 278
 279   named_iv->t = iv;
 280   named_iv->name = name;
 281
 282   entry->kind = iv_stack_entry_iv;
 283   entry->data.iv = named_iv;
 284
 285   VEC_safe_push (iv_stack_entry_p, heap, *stack, entry);
 286 }
 287
 288 /* Inserts a CONSTANT in STACK at INDEX.  */
 289
 290 static void
 291 loop_iv_stack_insert_constant (loop_iv_stack stack, int index,
 292                                tree constant)
 293 {
 294   iv_stack_entry *entry = XNEW (iv_stack_entry);
 295
 296   entry->kind = iv_stack_entry_const;
 297   entry->data.constant = constant;
 298
 299   VEC_safe_insert (iv_stack_entry_p, heap, *stack, index, entry);
 300 }
 301
 302 /* Pops and frees an element out of STACK.  */
 303
 304 static void
 305 loop_iv_stack_pop (loop_iv_stack stack)
 306 {
 307   iv_stack_entry_p entry = VEC_pop (iv_stack_entry_p, *stack);
 308
 309   free (entry->data.iv);
 310   free (entry);
 311 }
 312
 313 /* Get the IV at INDEX in STACK.  */
 314
 315 static tree
 316 loop_iv_stack_get_iv (loop_iv_stack stack, int index)
 317 {
 318   iv_stack_entry_p entry = VEC_index (iv_stack_entry_p, *stack, index);
 319   iv_stack_entry_data data = entry->data;
 320
 321   return iv_stack_entry_is_iv (entry) ? data.iv->t : data.constant;
 322 }
 323
 324 /* Get the IV from its NAME in STACK.  */
 325
 326 static tree
 327 loop_iv_stack_get_iv_from_name (loop_iv_stack stack, const char* name)
 328 {
 329   int i;
 330   iv_stack_entry_p entry;
 331
 332   for (i = 0; VEC_iterate (iv_stack_entry_p, *stack, i, entry); i++)
 333     {
 334       name_tree iv = entry->data.iv;
 335       if (!strcmp (name, iv->name))
 336         return iv->t;
 337     }
 338
 339   return NULL;
 340 }
 341
 342 /* Prints on stderr the contents of STACK.  */
 343
 344 void
 345 debug_loop_iv_stack (loop_iv_stack stack)
 346 {
 347   int i;
 348   iv_stack_entry_p entry;
 349   bool first = true;
 350
 351   fprintf (stderr, "(");
 352
 353   for (i = 0; VEC_iterate (iv_stack_entry_p, *stack, i, entry); i++)
 354     {
 355       if (first)
 356         first = false;
 357       else
 358         fprintf (stderr, " ");
 359
 360       if (iv_stack_entry_is_iv (entry))
 361         {
 362           name_tree iv = entry->data.iv;
 363           fprintf (stderr, "%s:", iv->name);
 364           print_generic_expr (stderr, iv->t, 0);
 365         }
 366       else
 367         {
 368           tree constant = entry->data.constant;
 369           print_generic_expr (stderr, constant, 0);
 370           fprintf (stderr, ":");
 371           print_generic_expr (stderr, constant, 0);
 372         }
 373     }
 374
 375   fprintf (stderr, ")\n");
 376 }
 377
 378 /* Frees STACK.  */
 379
 380 static void
 381 free_loop_iv_stack (loop_iv_stack stack)
 382 {
 383   int i;
 384   iv_stack_entry_p entry;
 385
 386   for (i = 0; VEC_iterate (iv_stack_entry_p, *stack, i, entry); i++)
 387     {
 388       free (entry->data.iv);
 389       free (entry);
 390     }
 391
 392   VEC_free (iv_stack_entry_p, heap, *stack);
 393 }
 394
 395 \f
 396
 397 /* Structure containing the mapping between the CLooG's induction
 398    variable and the type of the old induction variable.  */
 399 typedef struct ivtype_map_elt_d
 400 {
 401   tree type;
 402   const char *cloog_iv;
 403 } *ivtype_map_elt;
 404
 405 /* Print to stderr the element ELT.  */
 406
 407 static void
 408 debug_ivtype_elt (ivtype_map_elt elt)
 409 {
 410   fprintf (stderr, "(%s, ", elt->cloog_iv);
 411   print_generic_expr (stderr, elt->type, 0);
 412   fprintf (stderr, ")\n");
 413 }
 414
 415 /* Helper function for debug_ivtype_map.  */
 416
 417 static int
 418 debug_ivtype_map_1 (void **slot, void *s ATTRIBUTE_UNUSED)
 419 {
 420   struct ivtype_map_elt_d *entry = (struct ivtype_map_elt_d *) *slot;
 421   debug_ivtype_elt (entry);
 422   return 1;
 423 }
 424
 425 /* Print to stderr all the elements of MAP.  */
 426
 427 void
 428 debug_ivtype_map (htab_t map)
 429 {
 430   htab_traverse (map, debug_ivtype_map_1, NULL);
 431 }
 432
 433 /* Constructs a new SCEV_INFO_STR structure for VAR and INSTANTIATED_BELOW.  */
 434
 435 static inline ivtype_map_elt
 436 new_ivtype_map_elt (const char *cloog_iv, tree type)
 437 {
 438   ivtype_map_elt res;
 439
 440   res = XNEW (struct ivtype_map_elt_d);
 441   res->cloog_iv = cloog_iv;
 442   res->type = type;
 443
 444   return res;
 445 }
 446
 447 /* Computes a hash function for database element ELT.  */
 448
 449 static hashval_t
 450 ivtype_map_elt_info (const void *elt)
 451 {
 452   return htab_hash_pointer (((const struct ivtype_map_elt_d *) elt)->cloog_iv);
 453 }
 454
 455 /* Compares database elements E1 and E2.  */
 456
 457 static int
 458 eq_ivtype_map_elts (const void *e1, const void *e2)
 459 {
 460   const struct ivtype_map_elt_d *elt1 = (const struct ivtype_map_elt_d *) e1;
 461   const struct ivtype_map_elt_d *elt2 = (const struct ivtype_map_elt_d *) e2;
 462
 463   return (elt1->cloog_iv == elt2->cloog_iv);
 464 }
 465
 466 \f
 467
 468 /* Given a CLOOG_IV, returns the type that it should have in GCC land.
 469    If the information is not available, i.e. in the case one of the
 470    transforms created the loop, just return integer_type_node.  */
 471
 472 static tree
 473 gcc_type_for_cloog_iv (const char *cloog_iv, graphite_bb_p gbb)
 474 {
 475   struct ivtype_map_elt_d tmp;
 476   PTR *slot;
 477
 478   tmp.cloog_iv = cloog_iv;
 479   slot = htab_find_slot (GBB_CLOOG_IV_TYPES (gbb), &tmp, NO_INSERT);
 480
 481   if (slot && *slot)
 482     return ((ivtype_map_elt) *slot)->type;
 483
 484   return integer_type_node;
 485 }
 486
 487 /* Inserts constants derived from the USER_STMT argument list into the
 488    STACK.  This is needed to map old ivs to constants when loops have
 489    been eliminated.  */
 490
 491 static void
 492 loop_iv_stack_patch_for_consts (loop_iv_stack stack,
 493                                 struct clast_user_stmt *user_stmt)
 494 {
 495   struct clast_stmt *t;
 496   int index = 0;
 497   CloogStatement *cs = user_stmt->statement;
 498   graphite_bb_p gbb = (graphite_bb_p) cloog_statement_usr (cs);
 499
 500   for (t = user_stmt->substitutions; t; t = t->next)
 501     {
 502       struct clast_expr *expr = (struct clast_expr *)
 503         ((struct clast_assignment *)t)->RHS;
 504       struct clast_term *term = (struct clast_term *) expr;
 505
 506       /* FIXME: What should be done with expr_bin, expr_red?  */
 507       if (expr->type == expr_term
 508           && !term->var)
 509         {
 510           loop_p loop = gbb_loop_at_index (gbb, index);
 511           tree oldiv = oldiv_for_loop (GBB_SCOP (gbb), loop);
 512           tree type = oldiv ? TREE_TYPE (oldiv) : integer_type_node;
 513           tree value = gmp_cst_to_tree (type, term->val);
 514           loop_iv_stack_insert_constant (stack, index, value);
 515         }
 516       index = index + 1;
 517     }
 518 }
 519
 520 /* Removes all constants in the iv STACK.  */
 521
 522 static void
 523 loop_iv_stack_remove_constants (loop_iv_stack stack)
 524 {
 525   int i;
 526   iv_stack_entry *entry;
 527
 528   for (i = 0; VEC_iterate (iv_stack_entry_p, *stack, i, entry);)
 529     {
 530       if (iv_stack_entry_is_constant (entry))
 531         {
 532           free (VEC_index (iv_stack_entry_p, *stack, i));
 533           VEC_ordered_remove (iv_stack_entry_p, *stack, i);
 534         }
 535       else
 536         i++;
 537     }
 538 }
 539
 540 /* Returns a new loop_to_cloog_loop_str structure.  */
 541
 542 static inline struct loop_to_cloog_loop_str *
 543 new_loop_to_cloog_loop_str (int loop_num,
 544                             int loop_position,
 545                             CloogLoop *cloog_loop)
 546 {
 547   struct loop_to_cloog_loop_str *result;
 548
 549   result = XNEW (struct loop_to_cloog_loop_str);
 550   result->loop_num = loop_num;
 551   result->cloog_loop = cloog_loop;
 552   result->loop_position = loop_position;
 553
 554   return result;
 555 }
 556
 557 /* Hash function for SCOP_LOOP2CLOOG_LOOP hash table.  */
 558
 559 static hashval_t
 560 hash_loop_to_cloog_loop (const void *elt)
 561 {
 562   return ((const struct loop_to_cloog_loop_str *) elt)->loop_num;
 563 }
 564
 565 /* Equality function for SCOP_LOOP2CLOOG_LOOP hash table.  */
 566
 567 static int
 568 eq_loop_to_cloog_loop (const void *el1, const void *el2)
 569 {
 570   const struct loop_to_cloog_loop_str *elt1, *elt2;
 571
 572   elt1 = (const struct loop_to_cloog_loop_str *) el1;
 573   elt2 = (const struct loop_to_cloog_loop_str *) el2;
 574   return elt1->loop_num == elt2->loop_num;
 575 }
 576
 577 /* Compares two graphite bbs and returns an integer less than, equal to, or
 578    greater than zero if the first argument is considered to be respectively
 579    less than, equal to, or greater than the second.
 580    We compare using the lexicographic order of the static schedules.  */
 581
 582 static int
 583 gbb_compare (const void *p_1, const void *p_2)
 584 {
 585   const struct graphite_bb *const gbb_1
 586     = *(const struct graphite_bb *const*) p_1;
 587   const struct graphite_bb *const gbb_2
 588     = *(const struct graphite_bb *const*) p_2;
 589
 590   return lambda_vector_compare (GBB_STATIC_SCHEDULE (gbb_1),
 591                                 gbb_nb_loops (gbb_1) + 1,
 592                                 GBB_STATIC_SCHEDULE (gbb_2),
 593                                 gbb_nb_loops (gbb_2) + 1);
 594 }
 595
 596 /* Sort graphite bbs in SCOP.  */
 597
 598 static void
 599 graphite_sort_gbbs (scop_p scop)
 600 {
 601   VEC (graphite_bb_p, heap) *bbs = SCOP_BBS (scop);
 602
 603   qsort (VEC_address (graphite_bb_p, bbs),
 604          VEC_length (graphite_bb_p, bbs),
 605          sizeof (graphite_bb_p), gbb_compare);
 606 }
 607
 608 /* Dump conditions of a graphite basic block GBB on FILE.  */
 609
 610 static void
 611 dump_gbb_conditions (FILE *file, graphite_bb_p gbb)
 612 {
 613   int i;
 614   gimple stmt;
 615   VEC (gimple, heap) *conditions = GBB_CONDITIONS (gbb);
 616
 617   if (VEC_empty (gimple, conditions))
 618     return;
 619
 620   fprintf (file, "\tbb %d\t: cond = {", GBB_BB (gbb)->index);
 621
 622   for (i = 0; VEC_iterate (gimple, conditions, i, stmt); i++)
 623     print_gimple_stmt (file, stmt, 0, 0);
 624
 625   fprintf (file, "}\n");
 626 }
 627
 628 /* Converts the graphite scheduling function into a cloog scattering
 629    matrix.  This scattering matrix is used to limit the possible cloog
 630    output to valid programs in respect to the scheduling function.
 631
 632    SCATTERING_DIMENSIONS specifies the dimensionality of the scattering
 633    matrix. CLooG 0.14.0 and previous versions require, that all scattering
 634    functions of one CloogProgram have the same dimensionality, therefore we
 635    allow to specify it. (Should be removed in future versions)  */
 636
 637 static CloogMatrix *
 638 schedule_to_scattering (graphite_bb_p gb, int scattering_dimensions)
 639 {
 640   int i;
 641   scop_p scop = GBB_SCOP (gb);
 642
 643   int nb_iterators = gbb_nb_loops (gb);
 644
 645   /* The cloog scattering matrix consists of these colums:
 646      1                        col  = Eq/Inq,
 647      scattering_dimensions    cols = Scattering dimensions,
 648      nb_iterators             cols = bb's iterators,
 649      scop_nb_params        cols = Parameters,
 650      1                        col  = Constant 1.
 651
 652      Example:
 653
 654      scattering_dimensions = 5
 655      max_nb_iterators = 2
 656      nb_iterators = 1
 657      scop_nb_params = 2
 658
 659      Schedule:
 660      ? i
 661      4 5
 662
 663      Scattering Matrix:
 664      s1  s2  s3  s4  s5  i   p1  p2  1
 665      1   0   0   0   0   0   0   0  -4  = 0
 666      0   1   0   0   0  -1   0   0   0  = 0
 667      0   0   1   0   0   0   0   0  -5  = 0  */
 668   int nb_params = scop_nb_params (scop);
 669   int nb_cols = 1 + scattering_dimensions + nb_iterators + nb_params + 1;
 670   int col_const = nb_cols - 1;
 671   int col_iter_offset = 1 + scattering_dimensions;
 672
 673   CloogMatrix *scat = cloog_matrix_alloc (scattering_dimensions, nb_cols);
 674
 675   gcc_assert (scattering_dimensions >= nb_iterators * 2 + 1);
 676
 677   /* Initialize the identity matrix.  */
 678   for (i = 0; i < scattering_dimensions; i++)
 679     value_set_si (scat->p[i][i + 1], 1);
 680
 681   /* Textual order outside the first loop */
 682   value_set_si (scat->p[0][col_const], -GBB_STATIC_SCHEDULE (gb)[0]);
 683
 684   /* For all surrounding loops.  */
 685   for (i = 0;  i < nb_iterators; i++)
 686     {
 687       int schedule = GBB_STATIC_SCHEDULE (gb)[i + 1];
 688
 689       /* Iterations of this loop.  */
 690       value_set_si (scat->p[2 * i + 1][col_iter_offset + i], -1);
 691
 692       /* Textual order inside this loop.  */
 693       value_set_si (scat->p[2 * i + 2][col_const], -schedule);
 694     }
 695
 696   return scat;
 697 }
 698
 699 /* Print the schedules of GB to FILE with INDENT white spaces before.
 700    VERBOSITY determines how verbose the code pretty printers are.  */
 701
 702 void
 703 print_graphite_bb (FILE *file, graphite_bb_p gb, int indent, int verbosity)
 704 {
 705   CloogMatrix *scattering;
 706   int i;
 707   loop_p loop;
 708   fprintf (file, "\nGBB (\n");
 709
 710   print_loops_bb (file, GBB_BB (gb), indent+2, verbosity);
 711
 712   if (GBB_DOMAIN (gb))
 713     {
 714       fprintf (file, "       (domain: \n");
 715       cloog_matrix_print (file, GBB_DOMAIN (gb));
 716       fprintf (file, "       )\n");
 717     }
 718
 719   if (GBB_STATIC_SCHEDULE (gb))
 720     {
 721       fprintf (file, "       (static schedule: ");
 722       print_lambda_vector (file, GBB_STATIC_SCHEDULE (gb),
 723                            gbb_nb_loops (gb) + 1);
 724       fprintf (file, "       )\n");
 725     }
 726
 727   if (GBB_LOOPS (gb))
 728     {
 729       fprintf (file, "       (contained loops: \n");
 730       for (i = 0; VEC_iterate (loop_p, GBB_LOOPS (gb), i, loop); i++)
 731         if (loop == NULL)
 732           fprintf (file, "       iterator %d   =>  NULL \n", i);
 733         else
 734           fprintf (file, "       iterator %d   =>  loop %d \n", i,
 735                    loop->num);
 736       fprintf (file, "       )\n");
 737     }
 738
 739   if (GBB_DATA_REFS (gb))
 740     dump_data_references (file, GBB_DATA_REFS (gb));
 741
 742   if (GBB_CONDITIONS (gb))
 743     {
 744       fprintf (file, "       (conditions: \n");
 745       dump_gbb_conditions (file, gb);
 746       fprintf (file, "       )\n");
 747     }
 748
 749   if (GBB_SCOP (gb)
 750       && GBB_STATIC_SCHEDULE (gb))
 751     {
 752       fprintf (file, "       (scattering: \n");
 753       scattering = schedule_to_scattering (gb, 2 * gbb_nb_loops (gb) + 1);
 754       cloog_matrix_print (file, scattering);
 755       cloog_matrix_free (scattering);
 756       fprintf (file, "       )\n");
 757     }
 758
 759   fprintf (file, ")\n");
 760 }
 761
 762 /* Print to STDERR the schedules of GB with VERBOSITY level.  */
 763
 764 void
 765 debug_gbb (graphite_bb_p gb, int verbosity)
 766 {
 767   print_graphite_bb (stderr, gb, 0, verbosity);
 768 }
 769
 770
 771 /* Print SCOP to FILE.  VERBOSITY determines how verbose the pretty
 772    printers are.  */
 773
 774 static void
 775 print_scop (FILE *file, scop_p scop, int verbosity)
 776 {
 777   if (scop == NULL)
 778     return;
 779
 780   fprintf (file, "\nSCoP_%d_%d (\n",
 781            SCOP_ENTRY (scop)->index, SCOP_EXIT (scop)->index);
 782
 783   fprintf (file, "       (cloog: \n");
 784   cloog_program_print (file, SCOP_PROG (scop));
 785   fprintf (file, "       )\n");
 786
 787   if (SCOP_BBS (scop))
 788     {
 789       graphite_bb_p gb;
 790       int i;
 791
 792       for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
 793         print_graphite_bb (file, gb, 0, verbosity);
 794     }
 795
 796   fprintf (file, ")\n");
 797 }
 798
 799 /* Print all the SCOPs to FILE.  VERBOSITY determines how verbose the
 800    code pretty printers are.  */
 801
 802 static void
 803 print_scops (FILE *file, int verbosity)
 804 {
 805   int i;
 806   scop_p scop;
 807
 808   for (i = 0; VEC_iterate (scop_p, current_scops, i, scop); i++)
 809     print_scop (file, scop, verbosity);
 810 }
 811
 812 /* Debug SCOP.  VERBOSITY determines how verbose the code pretty
 813    printers are. */
 814
 815 void
 816 debug_scop (scop_p scop, int verbosity)
 817 {
 818   print_scop (stderr, scop, verbosity);
 819 }
 820
 821 /* Debug all SCOPs from CURRENT_SCOPS.  VERBOSITY determines how
 822    verbose the code pretty printers are.  */
 823
 824 void
 825 debug_scops (int verbosity)
 826 {
 827   print_scops (stderr, verbosity);
 828 }
 829
 830 /* Pretty print to FILE the SCOP in DOT format.  */
 831
 832 static void
 833 dot_scop_1 (FILE *file, scop_p scop)
 834 {
 835   edge e;
 836   edge_iterator ei;
 837   basic_block bb;
 838   basic_block entry = SCOP_ENTRY (scop);
 839   basic_block exit = SCOP_EXIT (scop);
 840
 841   fprintf (file, "digraph SCoP_%d_%d {\n", entry->index,
 842            exit->index);
 843
 844   FOR_ALL_BB (bb)
 845     {
 846       if (bb == entry)
 847         fprintf (file, "%d [shape=triangle];\n", bb->index);
 848
 849       if (bb == exit)
 850         fprintf (file, "%d [shape=box];\n", bb->index);
 851
 852       if (bb_in_sese_p (bb, SCOP_REGION (scop)))
 853         fprintf (file, "%d [color=red];\n", bb->index);
 854
 855       FOR_EACH_EDGE (e, ei, bb->succs)
 856         fprintf (file, "%d -> %d;\n", bb->index, e->dest->index);
 857     }
 858
 859   fputs ("}\n\n", file);
 860 }
 861
 862 /* Display SCOP using dotty.  */
 863
 864 void
 865 dot_scop (scop_p scop)
 866 {
 867   dot_scop_1 (stderr, scop);
 868 }
 869
 870 /* Pretty print all SCoPs in DOT format and mark them with different colors.
 871    If there are not enough colors, paint later SCoPs gray.
 872    Special nodes:
 873    - "*" after the node number: entry of a SCoP,
 874    - "#" after the node number: exit of a SCoP,
 875    - "()" entry or exit not part of SCoP.  */
 876
 877 static void
 878 dot_all_scops_1 (FILE *file)
 879 {
 880   basic_block bb;
 881   edge e;
 882   edge_iterator ei;
 883   scop_p scop;
 884   const char* color;
 885   int i;
 886
 887   /* Disable debugging while printing graph.  */
 888   int tmp_dump_flags = dump_flags;
 889   dump_flags = 0;
 890
 891   fprintf (file, "digraph all {\n");
 892
 893   FOR_ALL_BB (bb)
 894     {
 895       int part_of_scop = false;
 896
 897       /* Use HTML for every bb label.  So we are able to print bbs
 898          which are part of two different SCoPs, with two different
 899          background colors.  */
 900       fprintf (file, "%d [label=<\n  <TABLE BORDER=\"0\" CELLBORDER=\"1\" ",
 901                      bb->index);
 902       fprintf (file, "CELLSPACING=\"0\">\n");
 903
 904       /* Select color for SCoP.  */
 905       for (i = 0; VEC_iterate (scop_p, current_scops, i, scop); i++)
 906         if (bb_in_sese_p (bb, SCOP_REGION (scop))
 907             || (SCOP_EXIT (scop) == bb)
 908             || (SCOP_ENTRY (scop) == bb))
 909           {
 910             switch (i % 17)
 911               {
 912               case 0: /* red */
 913                 color = "#e41a1c";
 914                 break;
 915               case 1: /* blue */
 916                 color = "#377eb8";
 917                 break;
 918               case 2: /* green */
 919                 color = "#4daf4a";
 920                 break;
 921               case 3: /* purple */
 922                 color = "#984ea3";
 923                 break;
 924               case 4: /* orange */
 925                 color = "#ff7f00";
 926                 break;
 927               case 5: /* yellow */
 928                 color = "#ffff33";
 929                 break;
 930               case 6: /* brown */
 931                 color = "#a65628";
 932                 break;
 933               case 7: /* rose */
 934                 color = "#f781bf";
 935                 break;
 936               case 8:
 937                 color = "#8dd3c7";
 938                 break;
 939               case 9:
 940                 color = "#ffffb3";
 941                 break;
 942               case 10:
 943                 color = "#bebada";
 944                 break;
 945               case 11:
 946                 color = "#fb8072";
 947                 break;
 948               case 12:
 949                 color = "#80b1d3";
 950                 break;
 951               case 13:
 952                 color = "#fdb462";
 953                 break;
 954               case 14:
 955                 color = "#b3de69";
 956                 break;
 957               case 15:
 958                 color = "#fccde5";
 959                 break;
 960               case 16:
 961                 color = "#bc80bd";
 962                 break;
 963               default: /* gray */
 964                 color = "#999999";
 965               }
 966
 967             fprintf (file, "    <TR><TD WIDTH=\"50\" BGCOLOR=\"%s\">", color);
 968
 969             if (!bb_in_sese_p (bb, SCOP_REGION (scop)))
 970               fprintf (file, " (");
 971
 972             if (bb == SCOP_ENTRY (scop)
 973                 && bb == SCOP_EXIT (scop))
 974               fprintf (file, " %d*# ", bb->index);
 975             else if (bb == SCOP_ENTRY (scop))
 976               fprintf (file, " %d* ", bb->index);
 977             else if (bb == SCOP_EXIT (scop))
 978               fprintf (file, " %d# ", bb->index);
 979             else
 980               fprintf (file, " %d ", bb->index);
 981
 982             if (!bb_in_sese_p (bb, SCOP_REGION (scop)))
 983               fprintf (file, ")");
 984
 985             fprintf (file, "</TD></TR>\n");
 986             part_of_scop  = true;
 987           }
 988
 989       if (!part_of_scop)
 990         {
 991           fprintf (file, "    <TR><TD WIDTH=\"50\" BGCOLOR=\"#ffffff\">");
 992           fprintf (file, " %d </TD></TR>\n", bb->index);
 993         }
 994
 995       fprintf (file, "  </TABLE>>, shape=box, style=\"setlinewidth(0)\"]\n");
 996     }
 997
 998   FOR_ALL_BB (bb)
 999     {
1000       FOR_EACH_EDGE (e, ei, bb->succs)
1001               fprintf (file, "%d -> %d;\n", bb->index, e->dest->index);
1002     }
1003
1004   fputs ("}\n\n", file);
1005
1006   /* Enable debugging again.  */
1007   dump_flags = tmp_dump_flags;
1008 }
1009
1010 /* Display all SCoPs using dotty.  */
1011
1012 void
1013 dot_all_scops (void)
1014 {
1015   /* When debugging, enable the following code.  This cannot be used
1016      in production compilers because it calls "system".  */
1017 #if 0
1018   FILE *stream = fopen ("/tmp/allscops.dot", "w");
1019   gcc_assert (stream);
1020
1021   dot_all_scops_1 (stream);
1022   fclose (stream);
1023
1024   system ("dotty /tmp/allscops.dot");
1025 #else
1026   dot_all_scops_1 (stderr);
1027 #endif
1028 }
1029
1030 /* Returns the outermost loop in SCOP that contains BB.  */
1031
1032 static struct loop *
1033 outermost_loop_in_scop (scop_p scop, basic_block bb)
1034 {
1035   struct loop *nest;
1036
1037   nest = bb->loop_father;
1038   while (loop_outer (nest)
1039          && loop_in_sese_p (loop_outer (nest), SCOP_REGION (scop)))
1040     nest = loop_outer (nest);
1041
1042   return nest;
1043 }
1044
1045 /* Returns the block preceding the entry of SCOP.  */
1046
1047 static basic_block
1048 block_before_scop (scop_p scop)
1049 {
1050   return SESE_ENTRY (SCOP_REGION (scop))->src;
1051 }
1052
1053 /* Return true when EXPR is an affine function in LOOP with parameters
1054    instantiated relative to SCOP_ENTRY.  */
1055
1056 static bool
1057 loop_affine_expr (basic_block scop_entry, struct loop *loop, tree expr)
1058 {
1059   int n = loop->num;
1060   tree scev = analyze_scalar_evolution (loop, expr);
1061
1062   scev = instantiate_scev (scop_entry, loop, scev);
1063
1064   return (evolution_function_is_invariant_p (scev, n)
1065           || evolution_function_is_affine_multivariate_p (scev, n));
1066 }
1067
1068 /* Return true if REF or any of its subtrees contains a
1069    component_ref.  */
1070
1071 static bool
1072 contains_component_ref_p (tree ref)
1073 {
1074   if (!ref)
1075     return false;
1076
1077   while (handled_component_p (ref))
1078     {
1079       if (TREE_CODE (ref) == COMPONENT_REF)
1080         return true;
1081
1082       ref = TREE_OPERAND (ref, 0);
1083     }
1084
1085   return false;
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 COMPONENT_REF,  */
1098       || contains_component_ref_p (op)
1099       /* or a memory access that cannot be analyzed by the data
1100          reference analysis.  */
1101       || ((handled_component_p (op) || INDIRECT_REF_P (op))
1102           && !stmt_simple_memref_p (loop, stmt, op)))
1103     return false;
1104
1105   return true;
1106 }
1107
1108 /* Return true only when STMT is simple enough for being handled by
1109    Graphite.  This depends on SCOP_ENTRY, as the parametetrs are
1110    initialized relatively to this basic block.  */
1111
1112 static bool
1113 stmt_simple_for_scop_p (basic_block scop_entry, gimple stmt)
1114 {
1115   basic_block bb = gimple_bb (stmt);
1116   struct loop *loop = bb->loop_father;
1117
1118   /* GIMPLE_ASM and GIMPLE_CALL may embed arbitrary side effects.
1119      Calls have side-effects, except those to const or pure
1120      functions.  */
1121   if (gimple_has_volatile_ops (stmt)
1122       || (gimple_code (stmt) == GIMPLE_CALL
1123           && !(gimple_call_flags (stmt) & (ECF_CONST | ECF_PURE)))
1124       || (gimple_code (stmt) == GIMPLE_ASM))
1125     return false;
1126
1127   switch (gimple_code (stmt))
1128     {
1129     case GIMPLE_RETURN:
1130     case GIMPLE_LABEL:
1131       return true;
1132
1133     case GIMPLE_COND:
1134       {
1135         tree op;
1136         ssa_op_iter op_iter;
1137         enum tree_code code = gimple_cond_code (stmt);
1138
1139         /* We can only handle this kind of conditional expressions.
1140            For inequalities like "if (i != 3 * k)" we need unions of
1141            polyhedrons.  Expressions like  "if (a)" or "if (a == 15)" need
1142            them for the else branch.  */
1143         if (!(code == LT_EXPR
1144               || code == GT_EXPR
1145               || code == LE_EXPR
1146               || code == GE_EXPR))
1147           return false;
1148
1149         if (!scop_entry)
1150           return false;
1151
1152         FOR_EACH_SSA_TREE_OPERAND (op, stmt, op_iter, SSA_OP_ALL_USES)
1153           if (!loop_affine_expr (scop_entry, loop, op))
1154             return false;
1155
1156         return true;
1157       }
1158
1159     case GIMPLE_ASSIGN:
1160       {
1161         enum tree_code code = gimple_assign_rhs_code (stmt);
1162
1163         switch (get_gimple_rhs_class (code))
1164           {
1165           case GIMPLE_UNARY_RHS:
1166           case GIMPLE_SINGLE_RHS:
1167             return (is_simple_operand (loop, stmt, gimple_assign_lhs (stmt))
1168                     && is_simple_operand (loop, stmt, gimple_assign_rhs1 (stmt)));
1169
1170           case GIMPLE_BINARY_RHS:
1171             return (is_simple_operand (loop, stmt, gimple_assign_lhs (stmt))
1172                     && is_simple_operand (loop, stmt, gimple_assign_rhs1 (stmt))
1173                     && is_simple_operand (loop, stmt, gimple_assign_rhs2 (stmt)));
1174
1175           case GIMPLE_INVALID_RHS:
1176           default:
1177             gcc_unreachable ();
1178           }
1179       }
1180
1181     case GIMPLE_CALL:
1182       {
1183         size_t i;
1184         size_t n = gimple_call_num_args (stmt);
1185         tree lhs = gimple_call_lhs (stmt);
1186
1187         if (lhs && !is_simple_operand (loop, stmt, lhs))
1188           return false;
1189
1190         for (i = 0; i < n; i++)
1191           if (!is_simple_operand (loop, stmt, gimple_call_arg (stmt, i)))
1192             return false;
1193
1194         return true;
1195       }
1196
1197     default:
1198       /* These nodes cut a new scope.  */
1199       return false;
1200     }
1201
1202   return false;
1203 }
1204
1205 /* Returns the statement of BB that contains a harmful operation: that
1206    can be a function call with side effects, the induction variables
1207    are not linear with respect to SCOP_ENTRY, etc.  The current open
1208    scop should end before this statement.  */
1209
1210 static gimple
1211 harmful_stmt_in_bb (basic_block scop_entry, basic_block bb)
1212 {
1213   gimple_stmt_iterator gsi;
1214   gimple stmt;
1215
1216   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1217     if (!stmt_simple_for_scop_p (scop_entry, gsi_stmt (gsi)))
1218       return gsi_stmt (gsi);
1219
1220   stmt = last_stmt (bb);
1221   if (stmt && gimple_code (stmt) == GIMPLE_COND)
1222     {
1223       tree lhs = gimple_cond_lhs (stmt);
1224       tree rhs = gimple_cond_rhs (stmt);
1225
1226       if (TREE_CODE (TREE_TYPE (lhs)) == REAL_TYPE
1227           || TREE_CODE (TREE_TYPE (rhs)) == REAL_TYPE)
1228         return stmt;
1229     }
1230
1231   return NULL;
1232 }
1233
1234 /* Returns true when BB will be represented in graphite.  Return false
1235    for the basic blocks that contain code eliminated in the code
1236    generation pass: i.e. induction variables and exit conditions.  */
1237
1238 static bool
1239 graphite_stmt_p (scop_p scop, basic_block bb,
1240                  VEC (data_reference_p, heap) *drs)
1241 {
1242   gimple_stmt_iterator gsi;
1243   loop_p loop = bb->loop_father;
1244
1245   if (VEC_length (data_reference_p, drs) > 0)
1246     return true;
1247
1248   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1249     {
1250       gimple stmt = gsi_stmt (gsi);
1251
1252       switch (gimple_code (stmt))
1253         {
1254           /* Control flow expressions can be ignored, as they are
1255              represented in the iteration domains and will be
1256              regenerated by graphite.  */
1257         case GIMPLE_COND:
1258         case GIMPLE_GOTO:
1259         case GIMPLE_SWITCH:
1260           break;
1261
1262         case GIMPLE_ASSIGN:
1263           {
1264             tree var = gimple_assign_lhs (stmt);
1265             var = analyze_scalar_evolution (loop, var);
1266             var = instantiate_scev (block_before_scop (scop), loop, var);
1267
1268             if (chrec_contains_undetermined (var))
1269               return true;
1270
1271             break;
1272           }
1273
1274         default:
1275           return true;
1276         }
1277     }
1278
1279   return false;
1280 }
1281
1282 /* Store the GRAPHITE representation of BB.  */
1283
1284 static void
1285 new_graphite_bb (scop_p scop, basic_block bb)
1286 {
1287   struct graphite_bb *gbb;
1288   VEC (data_reference_p, heap) *drs = VEC_alloc (data_reference_p, heap, 5);
1289   struct loop *nest = outermost_loop_in_scop (scop, bb);
1290   gimple_stmt_iterator gsi;
1291
1292   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1293     find_data_references_in_stmt (nest, gsi_stmt (gsi), &drs);
1294
1295   if (!graphite_stmt_p (scop, bb, drs))
1296     {
1297       free_data_refs (drs);
1298       return;
1299     }
1300
1301   gbb = XNEW (struct graphite_bb);
1302   bb->aux = gbb;
1303   GBB_BB (gbb) = bb;
1304   GBB_SCOP (gbb) = scop;
1305   GBB_DATA_REFS (gbb) = drs;
1306   GBB_DOMAIN (gbb) = NULL;
1307   GBB_CONDITIONS (gbb) = NULL;
1308   GBB_CONDITION_CASES (gbb) = NULL;
1309   GBB_LOOPS (gbb) = NULL;
1310   GBB_STATIC_SCHEDULE (gbb) = NULL;
1311   GBB_CLOOG_IV_TYPES (gbb) = NULL;
1312   VEC_safe_push (graphite_bb_p, heap, SCOP_BBS (scop), gbb);
1313 }
1314
1315 /* Frees GBB.  */
1316
1317 static void
1318 free_graphite_bb (struct graphite_bb *gbb)
1319 {
1320   if (GBB_DOMAIN (gbb))
1321     cloog_matrix_free (GBB_DOMAIN (gbb));
1322
1323   if (GBB_CLOOG_IV_TYPES (gbb))
1324     htab_delete (GBB_CLOOG_IV_TYPES (gbb));
1325
1326   /* FIXME: free_data_refs is disabled for the moment, but should be
1327      enabled.
1328
1329      free_data_refs (GBB_DATA_REFS (gbb)); */
1330
1331   VEC_free (gimple, heap, GBB_CONDITIONS (gbb));
1332   VEC_free (gimple, heap, GBB_CONDITION_CASES (gbb));
1333   VEC_free (loop_p, heap, GBB_LOOPS (gbb));
1334   GBB_BB (gbb)->aux = 0;
1335   XDELETE (gbb);
1336 }
1337
1338 \f
1339
1340 /* Structure containing the mapping between the old names and the new
1341    names used after block copy in the new loop context.  */
1342 typedef struct rename_map_elt_d
1343 {
1344   tree old_name, new_name;
1345 } *rename_map_elt;
1346
1347
1348 /* Print to stderr the element ELT.  */
1349
1350 static void
1351 debug_rename_elt (rename_map_elt elt)
1352 {
1353   fprintf (stderr, "(");
1354   print_generic_expr (stderr, elt->old_name, 0);
1355   fprintf (stderr, ", ");
1356   print_generic_expr (stderr, elt->new_name, 0);
1357   fprintf (stderr, ")\n");
1358 }
1359
1360 /* Helper function for debug_rename_map.  */
1361
1362 static int
1363 debug_rename_map_1 (void **slot, void *s ATTRIBUTE_UNUSED)
1364 {
1365   struct rename_map_elt_d *entry = (struct rename_map_elt_d *) *slot;
1366   debug_rename_elt (entry);
1367   return 1;
1368 }
1369
1370 /* Print to stderr all the elements of MAP.  */
1371
1372 void
1373 debug_rename_map (htab_t map)
1374 {
1375   htab_traverse (map, debug_rename_map_1, NULL);
1376 }
1377
1378 /* Constructs a new SCEV_INFO_STR structure for VAR and INSTANTIATED_BELOW.  */
1379
1380 static inline rename_map_elt
1381 new_rename_map_elt (tree old_name, tree new_name)
1382 {
1383   rename_map_elt res;
1384
1385   res = XNEW (struct rename_map_elt_d);
1386   res->old_name = old_name;
1387   res->new_name = new_name;
1388
1389   return res;
1390 }
1391
1392 /* Computes a hash function for database element ELT.  */
1393
1394 static hashval_t
1395 rename_map_elt_info (const void *elt)
1396 {
1397   return htab_hash_pointer (((const struct rename_map_elt_d *) elt)->old_name);
1398 }
1399
1400 /* Compares database elements E1 and E2.  */
1401
1402 static int
1403 eq_rename_map_elts (const void *e1, const void *e2)
1404 {
1405   const struct rename_map_elt_d *elt1 = (const struct rename_map_elt_d *) e1;
1406   const struct rename_map_elt_d *elt2 = (const struct rename_map_elt_d *) e2;
1407
1408   return (elt1->old_name == elt2->old_name);
1409 }
1410
1411 /* Returns the new name associated to OLD_NAME in MAP.  */
1412
1413 static tree
1414 get_new_name_from_old_name (htab_t map, tree old_name)
1415 {
1416   struct rename_map_elt_d tmp;
1417   PTR *slot;
1418
1419   tmp.old_name = old_name;
1420   slot = htab_find_slot (map, &tmp, NO_INSERT);
1421
1422   if (slot && *slot)
1423     return ((rename_map_elt) *slot)->new_name;
1424
1425   return old_name;
1426 }
1427
1428 \f
1429
1430 /* Creates a new scop starting with ENTRY.  */
1431
1432 static scop_p
1433 new_scop (edge entry, edge exit)
1434 {
1435   scop_p scop = XNEW (struct scop);
1436
1437   gcc_assert (entry && exit);
1438
1439   SCOP_REGION (scop) = new_sese (entry, exit);
1440   SCOP_BBS (scop) = VEC_alloc (graphite_bb_p, heap, 3);
1441   SCOP_OLDIVS (scop) = VEC_alloc (name_tree, heap, 3);
1442   SCOP_LOOPS (scop) = BITMAP_ALLOC (NULL);
1443   SCOP_LOOP_NEST (scop) = VEC_alloc (loop_p, heap, 3);
1444   SCOP_ADD_PARAMS (scop) = true;
1445   SCOP_PARAMS (scop) = VEC_alloc (name_tree, heap, 3);
1446   SCOP_PROG (scop) = cloog_program_malloc ();
1447   cloog_program_set_names (SCOP_PROG (scop), cloog_names_malloc ());
1448   SCOP_LOOP2CLOOG_LOOP (scop) = htab_create (10, hash_loop_to_cloog_loop,
1449                                              eq_loop_to_cloog_loop,
1450                                              free);
1451   SCOP_LIVEOUT_RENAMES (scop) = htab_create (10, rename_map_elt_info,
1452                                              eq_rename_map_elts, free);
1453   return scop;
1454 }
1455
1456 /* Deletes SCOP.  */
1457
1458 static void
1459 free_scop (scop_p scop)
1460 {
1461   int i;
1462   name_tree p;
1463   struct graphite_bb *gb;
1464   name_tree iv;
1465
1466   for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
1467     free_graphite_bb (gb);
1468
1469   VEC_free (graphite_bb_p, heap, SCOP_BBS (scop));
1470   BITMAP_FREE (SCOP_LOOPS (scop));
1471   VEC_free (loop_p, heap, SCOP_LOOP_NEST (scop));
1472
1473   for (i = 0; VEC_iterate (name_tree, SCOP_OLDIVS (scop), i, iv); i++)
1474     free (iv);
1475   VEC_free (name_tree, heap, SCOP_OLDIVS (scop));
1476
1477   for (i = 0; VEC_iterate (name_tree, SCOP_PARAMS (scop), i, p); i++)
1478     free (p);
1479
1480   VEC_free (name_tree, heap, SCOP_PARAMS (scop));
1481   cloog_program_free (SCOP_PROG (scop));
1482   htab_delete (SCOP_LOOP2CLOOG_LOOP (scop));
1483   htab_delete (SCOP_LIVEOUT_RENAMES (scop));
1484   free_sese (SCOP_REGION (scop));
1485   XDELETE (scop);
1486 }
1487
1488 /* Deletes all scops in SCOPS.  */
1489
1490 static void
1491 free_scops (VEC (scop_p, heap) *scops)
1492 {
1493   int i;
1494   scop_p scop;
1495
1496   for (i = 0; VEC_iterate (scop_p, scops, i, scop); i++)
1497     free_scop (scop);
1498
1499   VEC_free (scop_p, heap, scops);
1500 }
1501
1502 typedef enum gbb_type {
1503   GBB_UNKNOWN,
1504   GBB_LOOP_SING_EXIT_HEADER,
1505   GBB_LOOP_MULT_EXIT_HEADER,
1506   GBB_LOOP_EXIT,
1507   GBB_COND_HEADER,
1508   GBB_SIMPLE,
1509   GBB_LAST
1510 } gbb_type;
1511
1512 /* Detect the type of BB.  Loop headers are only marked, if they are
1513    new.  This means their loop_father is different to LAST_LOOP.
1514    Otherwise they are treated like any other bb and their type can be
1515    any other type.  */
1516
1517 static gbb_type
1518 get_bb_type (basic_block bb, struct loop *last_loop)
1519 {
1520   VEC (basic_block, heap) *dom;
1521   int nb_dom, nb_suc;
1522   struct loop *loop = bb->loop_father;
1523
1524   /* Check, if we entry into a new loop. */
1525   if (loop != last_loop)
1526     {
1527       if (single_exit (loop) != NULL)
1528         return GBB_LOOP_SING_EXIT_HEADER;
1529       else if (loop->num != 0)
1530         return GBB_LOOP_MULT_EXIT_HEADER;
1531       else
1532         return GBB_COND_HEADER;
1533     }
1534
1535   dom = get_dominated_by (CDI_DOMINATORS, bb);
1536   nb_dom = VEC_length (basic_block, dom);
1537   VEC_free (basic_block, heap, dom);
1538
1539   if (nb_dom == 0)
1540     return GBB_LAST;
1541
1542   nb_suc = VEC_length (edge, bb->succs);
1543
1544   if (nb_dom == 1 && nb_suc == 1)
1545     return GBB_SIMPLE;
1546
1547   return GBB_COND_HEADER;
1548 }
1549
1550 /* A SCoP detection region, defined using bbs as borders.
1551    All control flow touching this region, comes in passing basic_block ENTRY and
1552    leaves passing basic_block EXIT.  By using bbs instead of edges for the
1553    borders we are able to represent also regions that do not have a single
1554    entry or exit edge.
1555    But as they have a single entry basic_block and a single exit basic_block, we
1556    are able to generate for every sd_region a single entry and exit edge.
1557
1558    1   2
1559     \ /
1560      3  <- entry
1561      |
1562      4
1563     / \                 This region contains: {3, 4, 5, 6, 7, 8}
1564    5   6
1565    |   |
1566    7   8
1567     \ /
1568      9  <- exit  */
1569
1570
1571 typedef struct sd_region_p
1572 {
1573   /* The entry bb dominates all bbs in the sd_region.  It is part of the
1574      region.  */
1575   basic_block entry;
1576
1577   /* The exit bb postdominates all bbs in the sd_region, but is not
1578      part of the region.  */
1579   basic_block exit;
1580 } sd_region;
1581
1582 DEF_VEC_O(sd_region);
1583 DEF_VEC_ALLOC_O(sd_region, heap);
1584
1585
1586 /* Moves the scops from SOURCE to TARGET and clean up SOURCE.  */
1587
1588 static void
1589 move_sd_regions (VEC (sd_region, heap) **source, VEC (sd_region, heap) **target)
1590 {
1591   sd_region *s;
1592   int i;
1593
1594   for (i = 0; VEC_iterate (sd_region, *source, i, s); i++)
1595     VEC_safe_push (sd_region, heap, *target, s);
1596
1597   VEC_free (sd_region, heap, *source);
1598 }
1599
1600 /* Return true when it is not possible to represent the upper bound of
1601    LOOP in the polyhedral representation.  */
1602
1603 static bool
1604 graphite_cannot_represent_loop_niter (loop_p loop)
1605 {
1606   tree niter = number_of_latch_executions (loop);
1607
1608   return chrec_contains_undetermined (niter)
1609     || !scev_is_linear_expression (niter);
1610 }
1611 /* Store information needed by scopdet_* functions.  */
1612
1613 struct scopdet_info
1614 {
1615   /* Where the last open scop would stop if the current BB is harmful.  */
1616   basic_block last;
1617
1618   /* Where the next scop would start if the current BB is harmful.  */
1619   basic_block next;
1620
1621   /* The bb or one of its children contains open loop exits.  That means
1622      loop exit nodes that are not surrounded by a loop dominated by bb.  */
1623   bool exits;
1624
1625   /* The bb or one of its children contains only structures we can handle.  */
1626   bool difficult;
1627 };
1628
1629
1630 static struct scopdet_info build_scops_1 (basic_block, VEC (sd_region, heap) **,
1631                                           loop_p);
1632
1633 /* Calculates BB infos. If bb is difficult we add valid SCoPs dominated by BB
1634    to SCOPS.  TYPE is the gbb_type of BB.  */
1635
1636 static struct scopdet_info
1637 scopdet_basic_block_info (basic_block bb, VEC (sd_region, heap) **scops,
1638                           gbb_type type)
1639 {
1640   struct loop *loop = bb->loop_father;
1641   struct scopdet_info result;
1642   gimple stmt;
1643
1644   /* XXX: ENTRY_BLOCK_PTR could be optimized in later steps.  */
1645   stmt = harmful_stmt_in_bb (ENTRY_BLOCK_PTR, bb);
1646   result.difficult = (stmt != NULL);
1647   result.last = NULL;
1648
1649   switch (type)
1650     {
1651     case GBB_LAST:
1652       result.next = NULL;
1653       result.exits = false;
1654       result.last = bb;
1655
1656       /* Mark bbs terminating a SESE region difficult, if they start
1657          a condition.  */
1658       if (VEC_length (edge, bb->succs) > 1)
1659         result.difficult = true;
1660
1661       break;
1662
1663     case GBB_SIMPLE:
1664       result.next = single_succ (bb);
1665       result.exits = false;
1666       result.last = bb;
1667       break;
1668
1669     case GBB_LOOP_SING_EXIT_HEADER:
1670       {
1671         VEC (sd_region, heap) *tmp_scops = VEC_alloc (sd_region, heap,3);
1672         struct scopdet_info sinfo;
1673
1674         sinfo = build_scops_1 (bb, &tmp_scops, loop);
1675
1676         result.last = single_exit (bb->loop_father)->src;
1677         result.next = single_exit (bb->loop_father)->dest;
1678
1679         /* If we do not dominate result.next, remove it.  It's either
1680            the EXIT_BLOCK_PTR, or another bb dominates it and will
1681            call the scop detection for this bb.  */
1682         if (!dominated_by_p (CDI_DOMINATORS, result.next, bb))
1683           result.next = NULL;
1684
1685         if (result.last->loop_father != loop)
1686           result.next = NULL;
1687
1688         if (graphite_cannot_represent_loop_niter (loop))
1689           result.difficult = true;
1690
1691         if (sinfo.difficult)
1692           move_sd_regions (&tmp_scops, scops);
1693         else
1694           VEC_free (sd_region, heap, tmp_scops);
1695
1696         result.exits = false;
1697         result.difficult |= sinfo.difficult;
1698         break;
1699       }
1700
1701     case GBB_LOOP_MULT_EXIT_HEADER:
1702       {
1703         /* XXX: For now we just do not join loops with multiple exits.  If the
1704            exits lead to the same bb it may be possible to join the loop.  */
1705         VEC (sd_region, heap) *tmp_scops = VEC_alloc (sd_region, heap, 3);
1706         VEC (edge, heap) *exits = get_loop_exit_edges (loop);
1707         edge e;
1708         int i;
1709         build_scops_1 (bb, &tmp_scops, loop);
1710
1711         /* Scan the code dominated by this loop.  This means all bbs, that are
1712            are dominated by a bb in this loop, but are not part of this loop.
1713
1714            The easiest case:
1715              - The loop exit destination is dominated by the exit sources.
1716
1717            TODO: We miss here the more complex cases:
1718                   - The exit destinations are dominated by another bb inside the
1719                     loop.
1720                   - The loop dominates bbs, that are not exit destinations.  */
1721         for (i = 0; VEC_iterate (edge, exits, i, e); i++)
1722           if (e->src->loop_father == loop
1723               && dominated_by_p (CDI_DOMINATORS, e->dest, e->src))
1724             {
1725               /* Pass loop_outer to recognize e->dest as loop header in
1726                  build_scops_1.  */
1727               if (e->dest->loop_father->header == e->dest)
1728                 build_scops_1 (e->dest, &tmp_scops,
1729                                loop_outer (e->dest->loop_father));
1730               else
1731                 build_scops_1 (e->dest, &tmp_scops, e->dest->loop_father);
1732             }
1733
1734         result.next = NULL;
1735         result.last = NULL;
1736         result.difficult = true;
1737         result.exits = false;
1738         move_sd_regions (&tmp_scops, scops);
1739         VEC_free (edge, heap, exits);
1740         break;
1741       }
1742     case GBB_COND_HEADER:
1743       {
1744         VEC (sd_region, heap) *tmp_scops = VEC_alloc (sd_region, heap, 3);
1745         struct scopdet_info sinfo;
1746         VEC (basic_block, heap) *dominated;
1747         int i;
1748         basic_block dom_bb;
1749         basic_block last_bb = NULL;
1750         edge e;
1751         result.exits = false;
1752
1753         /* First check the successors of BB, and check if it is possible to join
1754            the different branches.  */
1755         for (i = 0; VEC_iterate (edge, bb->succs, i, e); i++)
1756           {
1757             /* Ignore loop exits.  They will be handled after the loop body.  */
1758             if (is_loop_exit (loop, e->dest))
1759               {
1760                 result.exits = true;
1761                 continue;
1762               }
1763
1764             /* Do not follow edges that lead to the end of the
1765                conditions block.  For example, in
1766
1767                |   0
1768                |  /|\
1769                | 1 2 |
1770                | | | |
1771                | 3 4 |
1772                |  \|/
1773                |   6
1774
1775                the edge from 0 => 6.  Only check if all paths lead to
1776                the same node 6.  */
1777
1778             if (!single_pred_p (e->dest))
1779               {
1780                 /* Check, if edge leads directly to the end of this
1781                    condition.  */
1782                 if (!last_bb)
1783                   {
1784                     last_bb = e->dest;
1785                   }
1786
1787                 if (e->dest != last_bb)
1788                   result.difficult = true;
1789
1790                 continue;
1791               }
1792
1793             if (!dominated_by_p (CDI_DOMINATORS, e->dest, bb))
1794               {
1795                 result.difficult = true;
1796                 continue;
1797               }
1798
1799             sinfo = build_scops_1 (e->dest, &tmp_scops, loop);
1800
1801             result.exits |= sinfo.exits;
1802             result.last = sinfo.last;
1803             result.difficult |= sinfo.difficult;
1804
1805             /* Checks, if all branches end at the same point.
1806                If that is true, the condition stays joinable.
1807                Have a look at the example above.  */
1808             if (sinfo.last && single_succ_p (sinfo.last))
1809               {
1810                 basic_block next_tmp = single_succ (sinfo.last);
1811
1812                 if (!last_bb)
1813                     last_bb = next_tmp;
1814
1815                 if (next_tmp != last_bb)
1816                   result.difficult = true;
1817               }
1818             else
1819               result.difficult = true;
1820           }
1821
1822         /* If the condition is joinable.  */
1823         if (!result.exits && !result.difficult)
1824           {
1825             /* Only return a next pointer if we dominate this pointer.
1826                Otherwise it will be handled by the bb dominating it.  */
1827             if (dominated_by_p (CDI_DOMINATORS, last_bb, bb) && last_bb != bb)
1828               result.next = last_bb;
1829             else
1830               result.next = NULL;
1831
1832             VEC_free (sd_region, heap, tmp_scops);
1833             break;
1834           }
1835
1836         /* Scan remaining bbs dominated by BB.  */
1837         dominated = get_dominated_by (CDI_DOMINATORS, bb);
1838
1839         for (i = 0; VEC_iterate (basic_block, dominated, i, dom_bb); i++)
1840           {
1841             /* Ignore loop exits: they will be handled after the loop body.  */
1842             if (loop_depth (find_common_loop (loop, dom_bb->loop_father))
1843                 < loop_depth (loop))
1844               {
1845                 result.exits = true;
1846                 continue;
1847               }
1848
1849             /* Ignore the bbs processed above.  */
1850             if (single_pred_p (dom_bb) && single_pred (dom_bb) == bb)
1851               continue;
1852
1853             if (loop_depth (loop) > loop_depth (dom_bb->loop_father))
1854               sinfo = build_scops_1 (dom_bb, &tmp_scops, loop_outer (loop));
1855             else
1856               sinfo = build_scops_1 (dom_bb, &tmp_scops, loop);
1857
1858
1859             result.exits |= sinfo.exits;
1860             result.difficult = true;
1861             result.last = NULL;
1862           }
1863
1864         VEC_free (basic_block, heap, dominated);
1865
1866         result.next = NULL;
1867         move_sd_regions (&tmp_scops, scops);
1868
1869         break;
1870       }
1871
1872     default:
1873       gcc_unreachable ();
1874     }
1875
1876   return result;
1877 }
1878
1879 /* Creates the SCoPs and writes entry and exit points for every SCoP.  */
1880
1881 static struct scopdet_info
1882 build_scops_1 (basic_block current, VEC (sd_region, heap) **scops, loop_p loop)
1883 {
1884   bool in_scop = false;
1885   sd_region open_scop;
1886   struct scopdet_info sinfo;
1887
1888   /* Initialize result.  */
1889   struct scopdet_info result;
1890   result.exits = false;
1891   result.difficult = false;
1892   result.next = NULL;
1893   result.last = NULL;
1894   open_scop.entry = NULL;
1895   open_scop.exit = NULL;
1896   sinfo.last = NULL;
1897
1898   /* Loop over the dominance tree.  If we meet a difficult bb, close
1899      the current SCoP.  Loop and condition header start a new layer,
1900      and can only be added if all bbs in deeper layers are simple.  */
1901   while (current != NULL)
1902     {
1903       sinfo = scopdet_basic_block_info (current, scops, get_bb_type (current,
1904                                                                      loop));
1905
1906       if (!in_scop && !(sinfo.exits || sinfo.difficult))
1907         {
1908           open_scop.entry = current;
1909           open_scop.exit = NULL;
1910           in_scop = true;
1911         }
1912       else if (in_scop && (sinfo.exits || sinfo.difficult))
1913         {
1914           open_scop.exit = current;
1915           VEC_safe_push (sd_region, heap, *scops, &open_scop);
1916           in_scop = false;
1917         }
1918
1919       result.difficult |= sinfo.difficult;
1920       result.exits |= sinfo.exits;
1921
1922       current = sinfo.next;
1923     }
1924
1925   /* Try to close open_scop, if we are still in an open SCoP.  */
1926   if (in_scop)
1927     {
1928       int i;
1929       edge e;
1930
1931         for (i = 0; VEC_iterate (edge, sinfo.last->succs, i, e); i++)
1932           if (dominated_by_p (CDI_POST_DOMINATORS, sinfo.last, e->dest))
1933             open_scop.exit = e->dest;
1934
1935         if (!open_scop.exit && open_scop.entry != sinfo.last)
1936           open_scop.exit = sinfo.last;
1937
1938         if (open_scop.exit)
1939           VEC_safe_push (sd_region, heap, *scops, &open_scop);
1940
1941     }
1942
1943   result.last = sinfo.last;
1944   return result;
1945 }
1946
1947 /* Checks if a bb is contained in REGION.  */
1948
1949 static bool
1950 bb_in_sd_region (basic_block bb, sd_region *region)
1951 {
1952   return dominated_by_p (CDI_DOMINATORS, bb, region->entry)
1953          && !(dominated_by_p (CDI_DOMINATORS, bb, region->exit)
1954               && !dominated_by_p (CDI_DOMINATORS, region->entry,
1955                                   region->exit));
1956 }
1957
1958 /* Returns the single entry edge of REGION, if it does not exits NULL.  */
1959
1960 static edge
1961 find_single_entry_edge (sd_region *region)
1962 {
1963   edge e;
1964   edge_iterator ei;
1965   edge entry = NULL;
1966
1967   FOR_EACH_EDGE (e, ei, region->entry->preds)
1968     if (!bb_in_sd_region (e->src, region))
1969       {
1970         if (entry)
1971           {
1972             entry = NULL;
1973             break;
1974           }
1975
1976         else
1977           entry = e;
1978       }
1979
1980   return entry;
1981 }
1982
1983 /* Returns the single exit edge of REGION, if it does not exits NULL.  */
1984
1985 static edge
1986 find_single_exit_edge (sd_region *region)
1987 {
1988   edge e;
1989   edge_iterator ei;
1990   edge exit = NULL;
1991
1992   FOR_EACH_EDGE (e, ei, region->exit->preds)
1993     if (bb_in_sd_region (e->src, region))
1994       {
1995         if (exit)
1996           {
1997             exit = NULL;
1998             break;
1999           }
2000
2001         else
2002           exit = e;
2003       }
2004
2005   return exit;
2006 }
2007
2008 /* Create a single entry edge for REGION.  */
2009
2010 static void
2011 create_single_entry_edge (sd_region *region)
2012 {
2013   if (find_single_entry_edge (region))
2014     return;
2015
2016   /* There are multiple predecessors for bb_3
2017
2018   |  1  2
2019   |  | /
2020   |  |/
2021   |  3  <- entry
2022   |  |\
2023   |  | |
2024   |  4 ^
2025   |  | |
2026   |  |/
2027   |  5
2028
2029   There are two edges (1->3, 2->3), that point from outside into the region,
2030   and another one (5->3), a loop latch, lead to bb_3.
2031
2032   We split bb_3.
2033
2034   |  1  2
2035   |  | /
2036   |  |/
2037   |3.0
2038   |  |\     (3.0 -> 3.1) = single entry edge
2039   |3.1 |        <- entry
2040   |  | |
2041   |  | |
2042   |  4 ^
2043   |  | |
2044   |  |/
2045   |  5
2046
2047   If the loop is part of the SCoP, we have to redirect the loop latches.
2048
2049   |  1  2
2050   |  | /
2051   |  |/
2052   |3.0
2053   |  |      (3.0 -> 3.1) = entry edge
2054   |3.1          <- entry
2055   |  |\
2056   |  | |
2057   |  4 ^
2058   |  | |
2059   |  |/
2060   |  5  */
2061
2062   if (region->entry->loop_father->header != region->entry
2063       || dominated_by_p (CDI_DOMINATORS,
2064                          loop_latch_edge (region->entry->loop_father)->src,
2065                          region->exit))
2066     {
2067       edge forwarder = split_block_after_labels (region->entry);
2068       region->entry = forwarder->dest;
2069     }
2070   else
2071     /* This case is never executed, as the loop headers seem always to have a
2072        single edge pointing from outside into the loop.  */
2073     gcc_unreachable ();
2074
2075 #ifdef ENABLE_CHECKING
2076   gcc_assert (find_single_entry_edge (region));
2077 #endif
2078 }
2079
2080 /* Check if the sd_region, mentioned in EDGE, has no exit bb.  */
2081
2082 static bool
2083 sd_region_without_exit (edge e)
2084 {
2085   sd_region *r = (sd_region *) e->aux;
2086
2087   if (r)
2088     return r->exit == NULL;
2089   else
2090     return false;
2091 }
2092
2093 /* Create a single exit edge for REGION.  */
2094
2095 static void
2096 create_single_exit_edge (sd_region *region)
2097 {
2098   edge e;
2099   edge_iterator ei;
2100   edge forwarder = NULL;
2101   basic_block exit;
2102
2103   if (find_single_exit_edge (region))
2104     return;
2105
2106   /* We create a forwarder bb (5) for all edges leaving this region
2107      (3->5, 4->5).  All other edges leading to the same bb, are moved
2108      to a new bb (6).  If these edges where part of another region (2->5)
2109      we update the region->exit pointer, of this region.
2110
2111      To identify which edge belongs to which region we depend on the e->aux
2112      pointer in every edge.  It points to the region of the edge or to NULL,
2113      if the edge is not part of any region.
2114
2115      1 2 3 4    1->5 no region,                 2->5 region->exit = 5,
2116       \| |/     3->5 region->exit = NULL,       4->5 region->exit = NULL
2117         5       <- exit
2118
2119      changes to
2120
2121      1 2 3 4    1->6 no region,                         2->6 region->exit = 6,
2122      | | \/     3->5 no region,                         4->5 no region,
2123      | |  5
2124       \| /      5->6 region->exit = 6
2125         6
2126
2127      Now there is only a single exit edge (5->6).  */
2128   exit = region->exit;
2129   region->exit = NULL;
2130   forwarder = make_forwarder_block (exit, &sd_region_without_exit, NULL);
2131
2132   /* Unmark the edges, that are no longer exit edges.  */
2133   FOR_EACH_EDGE (e, ei, forwarder->src->preds)
2134     if (e->aux)
2135       e->aux = NULL;
2136
2137   /* Mark the new exit edge.  */
2138   single_succ_edge (forwarder->src)->aux = region;
2139
2140   /* Update the exit bb of all regions, where exit edges lead to
2141      forwarder->dest.  */
2142   FOR_EACH_EDGE (e, ei, forwarder->dest->preds)
2143     if (e->aux)
2144       ((sd_region *) e->aux)->exit = forwarder->dest;
2145
2146 #ifdef ENABLE_CHECKING
2147   gcc_assert (find_single_exit_edge (region));
2148 #endif
2149 }
2150
2151 /* Unmark the exit edges of all REGIONS.
2152    See comment in "create_single_exit_edge". */
2153
2154 static void
2155 unmark_exit_edges (VEC (sd_region, heap) *regions)
2156 {
2157   int i;
2158   sd_region *s;
2159   edge e;
2160   edge_iterator ei;
2161
2162   for (i = 0; VEC_iterate (sd_region, regions, i, s); i++)
2163     FOR_EACH_EDGE (e, ei, s->exit->preds)
2164       e->aux = NULL;
2165 }
2166
2167
2168 /* Mark the exit edges of all REGIONS.
2169    See comment in "create_single_exit_edge". */
2170
2171 static void
2172 mark_exit_edges (VEC (sd_region, heap) *regions)
2173 {
2174   int i;
2175   sd_region *s;
2176   edge e;
2177   edge_iterator ei;
2178
2179   for (i = 0; VEC_iterate (sd_region, regions, i, s); i++)
2180     FOR_EACH_EDGE (e, ei, s->exit->preds)
2181       if (bb_in_sd_region (e->src, s))
2182         e->aux = s;
2183 }
2184
2185 /* Free and compute again all the dominators information.  */
2186
2187 static inline void
2188 recompute_all_dominators (void)
2189 {
2190   mark_irreducible_loops ();
2191   free_dominance_info (CDI_DOMINATORS);
2192   free_dominance_info (CDI_POST_DOMINATORS);
2193   calculate_dominance_info (CDI_DOMINATORS);
2194   calculate_dominance_info (CDI_POST_DOMINATORS);
2195 }
2196
2197 /* Verifies properties that GRAPHITE should maintain during translation.  */
2198
2199 static inline void
2200 graphite_verify (void)
2201 {
2202 #ifdef ENABLE_CHECKING
2203   verify_loop_structure ();
2204   verify_dominators (CDI_DOMINATORS);
2205   verify_dominators (CDI_POST_DOMINATORS);
2206   verify_ssa (false);
2207   verify_loop_closed_ssa ();
2208 #endif
2209 }
2210
2211 /* Create for all scop regions a single entry and a single exit edge.  */
2212
2213 static void
2214 create_sese_edges (VEC (sd_region, heap) *regions)
2215 {
2216   int i;
2217   sd_region *s;
2218
2219   for (i = 0; VEC_iterate (sd_region, regions, i, s); i++)
2220     create_single_entry_edge (s);
2221
2222   mark_exit_edges (regions);
2223
2224   for (i = 0; VEC_iterate (sd_region, regions, i, s); i++)
2225     create_single_exit_edge (s);
2226
2227   unmark_exit_edges (regions);
2228
2229   fix_loop_structure (NULL);
2230
2231 #ifdef ENABLE_CHECKING
2232   verify_loop_structure ();
2233   verify_dominators (CDI_DOMINATORS);
2234   verify_ssa (false);
2235 #endif
2236 }
2237
2238 /* Create graphite SCoPs from an array of scop detection regions.  */
2239
2240 static void
2241 build_graphite_scops (VEC (sd_region, heap) *scop_regions)
2242 {
2243   int i;
2244   sd_region *s;
2245
2246   for (i = 0; VEC_iterate (sd_region, scop_regions, i, s); i++)
2247     {
2248       edge entry = find_single_entry_edge (s);
2249       edge exit = find_single_exit_edge (s);
2250       scop_p scop = new_scop (entry, exit);
2251       VEC_safe_push (scop_p, heap, current_scops, scop);
2252
2253       /* Are there overlapping SCoPs?  */
2254 #ifdef ENABLE_CHECKING
2255         {
2256           int j;
2257           sd_region *s2;
2258
2259           for (j = 0; VEC_iterate (sd_region, scop_regions, j, s2); j++)
2260             if (s != s2)
2261               gcc_assert (!bb_in_sd_region (s->entry, s2));
2262         }
2263 #endif
2264     }
2265 }
2266
2267 /* Find static control parts.  */
2268
2269 static void
2270 build_scops (void)
2271 {
2272   struct loop *loop = current_loops->tree_root;
2273   VEC (sd_region, heap) *tmp_scops = VEC_alloc (sd_region, heap, 3);
2274
2275   build_scops_1 (single_succ (ENTRY_BLOCK_PTR), &tmp_scops, loop);
2276   create_sese_edges (tmp_scops);
2277   build_graphite_scops (tmp_scops);
2278   VEC_free (sd_region, heap, tmp_scops);
2279 }
2280
2281 /* Gather the basic blocks belonging to the SCOP.  */
2282
2283 static void
2284 build_scop_bbs (scop_p scop)
2285 {
2286   basic_block *stack = XNEWVEC (basic_block, n_basic_blocks + 1);
2287   sbitmap visited = sbitmap_alloc (last_basic_block);
2288   int sp = 0;
2289
2290   sbitmap_zero (visited);
2291   stack[sp++] = SCOP_ENTRY (scop);
2292
2293   while (sp)
2294     {
2295       basic_block bb = stack[--sp];
2296       int depth = loop_depth (bb->loop_father);
2297       int num = bb->loop_father->num;
2298       edge_iterator ei;
2299       edge e;
2300
2301       /* Scop's exit is not in the scop.  Exclude also bbs, which are
2302          dominated by the SCoP exit.  These are e.g. loop latches.  */
2303       if (TEST_BIT (visited, bb->index)
2304           || dominated_by_p (CDI_DOMINATORS, bb, SCOP_EXIT (scop))
2305           /* Every block in the scop is dominated by scop's entry.  */
2306           || !dominated_by_p (CDI_DOMINATORS, bb, SCOP_ENTRY (scop)))
2307         continue;
2308
2309       new_graphite_bb (scop, bb);
2310       SET_BIT (visited, bb->index);
2311
2312       /* First push the blocks that have to be processed last.  Note
2313          that this means that the order in which the code is organized
2314          below is important: do not reorder the following code.  */
2315       FOR_EACH_EDGE (e, ei, bb->succs)
2316         if (! TEST_BIT (visited, e->dest->index)
2317             && (int) loop_depth (e->dest->loop_father) < depth)
2318           stack[sp++] = e->dest;
2319
2320       FOR_EACH_EDGE (e, ei, bb->succs)
2321         if (! TEST_BIT (visited, e->dest->index)
2322             && (int) loop_depth (e->dest->loop_father) == depth
2323             && e->dest->loop_father->num != num)
2324           stack[sp++] = e->dest;
2325
2326       FOR_EACH_EDGE (e, ei, bb->succs)
2327         if (! TEST_BIT (visited, e->dest->index)
2328             && (int) loop_depth (e->dest->loop_father) == depth
2329             && e->dest->loop_father->num == num
2330             && EDGE_COUNT (e->dest->preds) > 1)
2331           stack[sp++] = e->dest;
2332
2333       FOR_EACH_EDGE (e, ei, bb->succs)
2334         if (! TEST_BIT (visited, e->dest->index)
2335             && (int) loop_depth (e->dest->loop_father) == depth
2336             && e->dest->loop_father->num == num
2337             && EDGE_COUNT (e->dest->preds) == 1)
2338           stack[sp++] = e->dest;
2339
2340       FOR_EACH_EDGE (e, ei, bb->succs)
2341         if (! TEST_BIT (visited, e->dest->index)
2342             && (int) loop_depth (e->dest->loop_father) > depth)
2343           stack[sp++] = e->dest;
2344     }
2345
2346   free (stack);
2347   sbitmap_free (visited);
2348 }
2349
2350 /* Returns the number of reduction phi nodes in LOOP.  */
2351
2352 static int
2353 nb_reductions_in_loop (loop_p loop)
2354 {
2355   int res = 0;
2356   gimple_stmt_iterator gsi;
2357
2358   for (gsi = gsi_start_phis (loop->header); !gsi_end_p (gsi); gsi_next (&gsi))
2359     {
2360       gimple phi = gsi_stmt (gsi);
2361       tree scev;
2362       affine_iv iv;
2363
2364       if (!is_gimple_reg (PHI_RESULT (phi)))
2365         continue;
2366
2367       scev = analyze_scalar_evolution (loop, PHI_RESULT (phi));
2368       scev = instantiate_parameters (loop, scev);
2369       if (!simple_iv (loop, loop, PHI_RESULT (phi), &iv, true))
2370         res++;
2371     }
2372
2373   return res;
2374 }
2375
2376 /* A LOOP is in normal form when it contains only one scalar phi node
2377    that defines the main induction variable of the loop, only one
2378    increment of the IV, and only one exit condition. */
2379
2380 static tree
2381 graphite_loop_normal_form (loop_p loop)
2382 {
2383   struct tree_niter_desc niter;
2384   tree nit;
2385   gimple_seq stmts;
2386   edge exit = single_dom_exit (loop);
2387   bool known_niter = number_of_iterations_exit (loop, exit, &niter, false);
2388
2389   gcc_assert (known_niter);
2390
2391   nit = force_gimple_operand (unshare_expr (niter.niter), &stmts, true,
2392                               NULL_TREE);
2393   if (stmts)
2394     gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
2395
2396   /* One IV per loop.  */
2397   if (nb_reductions_in_loop (loop) > 0)
2398     return NULL_TREE;
2399
2400   return canonicalize_loop_ivs (loop, NULL, &nit);
2401 }
2402
2403 /* Record LOOP as occuring in SCOP.  Returns true when the operation
2404    was successful.  */
2405
2406 static bool
2407 scop_record_loop (scop_p scop, loop_p loop)
2408 {
2409   tree induction_var;
2410   name_tree oldiv;
2411
2412   if (bitmap_bit_p (SCOP_LOOPS (scop), loop->num))
2413     return true;
2414
2415   bitmap_set_bit (SCOP_LOOPS (scop), loop->num);
2416   VEC_safe_push (loop_p, heap, SCOP_LOOP_NEST (scop), loop);
2417
2418   induction_var = graphite_loop_normal_form (loop);
2419   if (!induction_var)
2420     return false;
2421
2422   oldiv = XNEW (struct name_tree_d);
2423   oldiv->t = induction_var;
2424   oldiv->name = get_name (SSA_NAME_VAR (oldiv->t));
2425   oldiv->loop = loop;
2426   VEC_safe_push (name_tree, heap, SCOP_OLDIVS (scop), oldiv);
2427   return true;
2428 }
2429
2430 /* Build the loop nests contained in SCOP.  Returns true when the
2431    operation was successful.  */
2432
2433 static bool
2434 build_scop_loop_nests (scop_p scop)
2435 {
2436   unsigned i;
2437   basic_block bb;
2438   struct loop *loop0, *loop1;
2439
2440   FOR_EACH_BB (bb)
2441     if (bb_in_sese_p (bb, SCOP_REGION (scop)))
2442       {
2443         struct loop *loop = bb->loop_father;
2444
2445         /* Only add loops if they are completely contained in the SCoP.  */
2446         if (loop->header == bb
2447             && bb_in_sese_p (loop->latch, SCOP_REGION (scop)))
2448           {
2449             if (!scop_record_loop (scop, loop))
2450               return false;
2451           }
2452       }
2453
2454   /* Make sure that the loops in the SCOP_LOOP_NEST are ordered.  It
2455      can be the case that an inner loop is inserted before an outer
2456      loop.  To avoid this, semi-sort once.  */
2457   for (i = 0; VEC_iterate (loop_p, SCOP_LOOP_NEST (scop), i, loop0); i++)
2458     {
2459       if (VEC_length (loop_p, SCOP_LOOP_NEST (scop)) == i + 1)
2460         break;
2461
2462       loop1 = VEC_index (loop_p, SCOP_LOOP_NEST (scop), i + 1);
2463       if (loop0->num > loop1->num)
2464         {
2465           VEC_replace (loop_p, SCOP_LOOP_NEST (scop), i, loop1);
2466           VEC_replace (loop_p, SCOP_LOOP_NEST (scop), i + 1, loop0);
2467         }
2468     }
2469
2470   return true;
2471 }
2472
2473 /* Calculate the number of loops around LOOP in the SCOP.  */
2474
2475 static inline int
2476 nb_loops_around_loop_in_scop (struct loop *l, scop_p scop)
2477 {
2478   int d = 0;
2479
2480   for (; loop_in_sese_p (l, SCOP_REGION (scop)); d++, l = loop_outer (l));
2481
2482   return d;
2483 }
2484
2485 /* Calculate the number of loops around GB in the current SCOP.  */
2486
2487 int
2488 nb_loops_around_gb (graphite_bb_p gb)
2489 {
2490   return nb_loops_around_loop_in_scop (gbb_loop (gb), GBB_SCOP (gb));
2491 }
2492
2493 /* Returns the dimensionality of an enclosing loop iteration domain
2494    with respect to enclosing SCoP for a given data reference REF.  The
2495    returned dimensionality is homogeneous (depth of loop nest + number
2496    of SCoP parameters + const).  */
2497
2498 int
2499 ref_nb_loops (data_reference_p ref)
2500 {
2501   loop_p loop = loop_containing_stmt (DR_STMT (ref));
2502   scop_p scop = DR_SCOP (ref);
2503
2504   return nb_loops_around_loop_in_scop (loop, scop) + scop_nb_params (scop) + 2;
2505 }
2506
2507 /* Build dynamic schedules for all the BBs. */
2508
2509 static void
2510 build_scop_dynamic_schedules (scop_p scop)
2511 {
2512   int i, dim, loop_num, row, col;
2513   graphite_bb_p gb;
2514
2515   for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
2516     {
2517       loop_num = GBB_BB (gb)->loop_father->num;
2518
2519       if (loop_num != 0)
2520         {
2521           dim = nb_loops_around_gb (gb);
2522           GBB_DYNAMIC_SCHEDULE (gb) = cloog_matrix_alloc (dim, dim);
2523
2524           for (row = 0; row < GBB_DYNAMIC_SCHEDULE (gb)->NbRows; row++)
2525             for (col = 0; col < GBB_DYNAMIC_SCHEDULE (gb)->NbColumns; col++)
2526               if (row == col)
2527                 value_set_si (GBB_DYNAMIC_SCHEDULE (gb)->p[row][col], 1);
2528               else
2529                 value_set_si (GBB_DYNAMIC_SCHEDULE (gb)->p[row][col], 0);
2530         }
2531       else
2532         GBB_DYNAMIC_SCHEDULE (gb) = NULL;
2533     }
2534 }
2535
2536 /* Returns the number of loops that are identical at the beginning of
2537    the vectors A and B.  */
2538
2539 static int
2540 compare_prefix_loops (VEC (loop_p, heap) *a, VEC (loop_p, heap) *b)
2541 {
2542   int i;
2543   loop_p ea;
2544   int lb;
2545
2546   if (!a || !b)
2547     return 0;
2548
2549   lb = VEC_length (loop_p, b);
2550
2551   for (i = 0; VEC_iterate (loop_p, a, i, ea); i++)
2552     if (i >= lb
2553         || ea != VEC_index (loop_p, b, i))
2554       return i;
2555
2556   return 0;
2557 }
2558
2559 /* Build for BB the static schedule.
2560
2561    The STATIC_SCHEDULE is defined like this:
2562
2563    A
2564    for (i: ...)
2565      {
2566        for (j: ...)
2567          {
2568            B
2569            C
2570          }
2571
2572        for (k: ...)
2573          {
2574            D
2575            E
2576          }
2577      }
2578    F
2579
2580    Static schedules for A to F:
2581
2582      DEPTH
2583      0 1 2
2584    A 0
2585    B 1 0 0
2586    C 1 0 1
2587    D 1 1 0
2588    E 1 1 1
2589    F 2
2590 */
2591
2592 static void
2593 build_scop_canonical_schedules (scop_p scop)
2594 {
2595   int i;
2596   graphite_bb_p gb;
2597   int nb_loops = scop_nb_loops (scop);
2598   lambda_vector static_schedule = lambda_vector_new (nb_loops + 1);
2599   VEC (loop_p, heap) *loops_previous = NULL;
2600
2601   /* We have to start schedules at 0 on the first component and
2602      because we cannot compare_prefix_loops against a previous loop,
2603      prefix will be equal to zero, and that index will be
2604      incremented before copying.  */
2605   static_schedule[0] = -1;
2606
2607   for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
2608     {
2609       int prefix = compare_prefix_loops (loops_previous, GBB_LOOPS (gb));
2610       int nb = gbb_nb_loops (gb);
2611
2612       loops_previous = GBB_LOOPS (gb);
2613       memset (&(static_schedule[prefix + 1]), 0, sizeof (int) * (nb_loops - prefix));
2614       ++static_schedule[prefix];
2615       GBB_STATIC_SCHEDULE (gb) = lambda_vector_new (nb + 1);
2616       lambda_vector_copy (static_schedule,
2617                           GBB_STATIC_SCHEDULE (gb), nb + 1);
2618     }
2619 }
2620
2621 /* Build the LOOPS vector for all bbs in SCOP.  */
2622
2623 static void
2624 build_bb_loops (scop_p scop)
2625 {
2626   graphite_bb_p gb;
2627   int i;
2628
2629   for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
2630     {
2631       loop_p loop;
2632       int depth;
2633
2634       depth = nb_loops_around_gb (gb) - 1;
2635
2636       GBB_LOOPS (gb) = VEC_alloc (loop_p, heap, 3);
2637       VEC_safe_grow_cleared (loop_p, heap, GBB_LOOPS (gb), depth + 1);
2638
2639       loop = GBB_BB (gb)->loop_father;
2640
2641       while (scop_contains_loop (scop, loop))
2642         {
2643           VEC_replace (loop_p, GBB_LOOPS (gb), depth, loop);
2644           loop = loop_outer (loop);
2645           depth--;
2646         }
2647     }
2648 }
2649
2650 /* Get the index for parameter VAR in SCOP.  */
2651
2652 static int
2653 param_index (tree var, scop_p scop)
2654 {
2655   int i;
2656   name_tree p;
2657   name_tree nvar;
2658
2659   gcc_assert (TREE_CODE (var) == SSA_NAME);
2660
2661   for (i = 0; VEC_iterate (name_tree, SCOP_PARAMS (scop), i, p); i++)
2662     if (p->t == var)
2663       return i;
2664
2665   gcc_assert (SCOP_ADD_PARAMS (scop));
2666
2667   nvar = XNEW (struct name_tree_d);
2668   nvar->t = var;
2669   nvar->name = NULL;
2670   VEC_safe_push (name_tree, heap, SCOP_PARAMS (scop), nvar);
2671   return VEC_length (name_tree, SCOP_PARAMS (scop)) - 1;
2672 }
2673
2674 /* Scan EXPR and translate it to an inequality vector INEQ that will
2675    be added, or subtracted, in the constraint domain matrix C at row
2676    R.  K is the number of columns for loop iterators in C. */
2677
2678 static void
2679 scan_tree_for_params (scop_p s, tree e, CloogMatrix *c, int r, Value k,
2680                       bool subtract)
2681 {
2682   int cst_col, param_col;
2683
2684   if (e == chrec_dont_know)
2685     return;
2686
2687   switch (TREE_CODE (e))
2688     {
2689     case POLYNOMIAL_CHREC:
2690       {
2691         tree left = CHREC_LEFT (e);
2692         tree right = CHREC_RIGHT (e);
2693         int var = CHREC_VARIABLE (e);
2694
2695         if (TREE_CODE (right) != INTEGER_CST)
2696           return;
2697
2698         if (c)
2699           {
2700             int loop_col = scop_gimple_loop_depth (s, get_loop (var)) + 1;
2701
2702             if (subtract)
2703               value_sub_int (c->p[r][loop_col], c->p[r][loop_col],
2704                              int_cst_value (right));
2705             else
2706               value_add_int (c->p[r][loop_col], c->p[r][loop_col],
2707                              int_cst_value (right));
2708           }
2709
2710         switch (TREE_CODE (left))
2711           {
2712           case POLYNOMIAL_CHREC:
2713             scan_tree_for_params (s, left, c, r, k, subtract);
2714             return;
2715
2716           case INTEGER_CST:
2717             /* Constant part.  */
2718             if (c)
2719               {
2720                 int v = int_cst_value (left);
2721                 cst_col = c->NbColumns - 1;
2722
2723                 if (v < 0)
2724                   {
2725                     v = -v;
2726                     subtract = subtract ? false : true;
2727                   }
2728
2729                 if (subtract)
2730                   value_sub_int (c->p[r][cst_col], c->p[r][cst_col], v);
2731                 else
2732                   value_add_int (c->p[r][cst_col], c->p[r][cst_col], v);
2733               }
2734             return;
2735
2736           default:
2737             scan_tree_for_params (s, left, c, r, k, subtract);
2738             return;
2739           }
2740       }
2741       break;
2742
2743     case MULT_EXPR:
2744       if (chrec_contains_symbols (TREE_OPERAND (e, 0)))
2745         {
2746           if (c)
2747             {
2748               Value val;
2749               gcc_assert (host_integerp (TREE_OPERAND (e, 1), 0));
2750               value_init (val);
2751               value_set_si (val, int_cst_value (TREE_OPERAND (e, 1)));
2752               value_multiply (k, k, val);
2753               value_clear (val);
2754             }
2755           scan_tree_for_params (s, TREE_OPERAND (e, 0), c, r, k, subtract);
2756         }
2757       else
2758         {
2759           if (c)
2760             {
2761               Value val;
2762               gcc_assert (host_integerp (TREE_OPERAND (e, 0), 0));
2763               value_init (val);
2764               value_set_si (val, int_cst_value (TREE_OPERAND (e, 0)));
2765               value_multiply (k, k, val);
2766               value_clear (val);
2767             }
2768           scan_tree_for_params (s, TREE_OPERAND (e, 1), c, r, k, subtract);
2769         }
2770       break;
2771
2772     case PLUS_EXPR:
2773     case POINTER_PLUS_EXPR:
2774       scan_tree_for_params (s, TREE_OPERAND (e, 0), c, r, k, subtract);
2775       scan_tree_for_params (s, TREE_OPERAND (e, 1), c, r, k, subtract);
2776       break;
2777
2778     case MINUS_EXPR:
2779       scan_tree_for_params (s, TREE_OPERAND (e, 0), c, r, k, subtract);
2780       scan_tree_for_params (s, TREE_OPERAND (e, 1), c, r, k, !subtract);
2781       break;
2782
2783     case NEGATE_EXPR:
2784       scan_tree_for_params (s, TREE_OPERAND (e, 0), c, r, k, !subtract);
2785       break;
2786
2787     case SSA_NAME:
2788       param_col = param_index (e, s);
2789
2790       if (c)
2791         {
2792           param_col += c->NbColumns - scop_nb_params (s) - 1;
2793
2794           if (subtract)
2795             value_subtract (c->p[r][param_col], c->p[r][param_col], k);
2796           else
2797             value_addto (c->p[r][param_col], c->p[r][param_col], k);
2798         }
2799       break;
2800
2801     case INTEGER_CST:
2802       if (c)
2803         {
2804           int v = int_cst_value (e);
2805           cst_col = c->NbColumns - 1;
2806
2807           if (v < 0)
2808           {
2809             v = -v;
2810             subtract = subtract ? false : true;
2811           }
2812
2813           if (subtract)
2814             value_sub_int (c->p[r][cst_col], c->p[r][cst_col], v);
2815           else
2816             value_add_int (c->p[r][cst_col], c->p[r][cst_col], v);
2817         }
2818       break;
2819
2820     CASE_CONVERT:
2821     case NON_LVALUE_EXPR:
2822       scan_tree_for_params (s, TREE_OPERAND (e, 0), c, r, k, subtract);
2823       break;
2824
2825     default:
2826       gcc_unreachable ();
2827       break;
2828     }
2829 }
2830
2831 /* Data structure for idx_record_params.  */
2832
2833 struct irp_data
2834 {
2835   struct loop *loop;
2836   scop_p scop;
2837 };
2838
2839 /* For a data reference with an ARRAY_REF as its BASE, record the
2840    parameters occurring in IDX.  DTA is passed in as complementary
2841    information, and is used by the automatic walker function.  This
2842    function is a callback for for_each_index.  */
2843
2844 static bool
2845 idx_record_params (tree base, tree *idx, void *dta)
2846 {
2847   struct irp_data *data = (struct irp_data *) dta;
2848
2849   if (TREE_CODE (base) != ARRAY_REF)
2850     return true;
2851
2852   if (TREE_CODE (*idx) == SSA_NAME)
2853     {
2854       tree scev;
2855       scop_p scop = data->scop;
2856       struct loop *loop = data->loop;
2857       Value one;
2858
2859       scev = analyze_scalar_evolution (loop, *idx);
2860       scev = instantiate_scev (block_before_scop (scop), loop, scev);
2861
2862       value_init (one);
2863       value_set_si (one, 1);
2864       scan_tree_for_params (scop, scev, NULL, 0, one, false);
2865       value_clear (one);
2866     }
2867
2868   return true;
2869 }
2870
2871 /* Find parameters with respect to SCOP in BB. We are looking in memory
2872    access functions, conditions and loop bounds.  */
2873
2874 static void
2875 find_params_in_bb (scop_p scop, graphite_bb_p gb)
2876 {
2877   int i;
2878   data_reference_p dr;
2879   gimple stmt;
2880   loop_p father = GBB_BB (gb)->loop_father;
2881
2882   for (i = 0; VEC_iterate (data_reference_p, GBB_DATA_REFS (gb), i, dr); i++)
2883     {
2884       struct irp_data irp;
2885
2886       irp.loop = father;
2887       irp.scop = scop;
2888       for_each_index (&dr->ref, idx_record_params, &irp);
2889     }
2890
2891   /* Find parameters in conditional statements.  */
2892   for (i = 0; VEC_iterate (gimple, GBB_CONDITIONS (gb), i, stmt); i++)
2893     {
2894       Value one;
2895       loop_p loop = father;
2896
2897       tree lhs, rhs;
2898
2899       lhs = gimple_cond_lhs (stmt);
2900       lhs = analyze_scalar_evolution (loop, lhs);
2901       lhs = instantiate_scev (block_before_scop (scop), loop, lhs);
2902
2903       rhs = gimple_cond_rhs (stmt);
2904       rhs = analyze_scalar_evolution (loop, rhs);
2905       rhs = instantiate_scev (block_before_scop (scop), loop, rhs);
2906
2907       value_init (one);
2908       scan_tree_for_params (scop, lhs, NULL, 0, one, false);
2909       value_set_si (one, 1);
2910       scan_tree_for_params (scop, rhs, NULL, 0, one, false);
2911       value_clear (one);
2912     }
2913 }
2914
2915 /* Saves in NV the name of variable P->T.  */
2916
2917 static void
2918 save_var_name (char **nv, int i, name_tree p)
2919 {
2920   const char *name = get_name (SSA_NAME_VAR (p->t));
2921
2922   if (name)
2923     {
2924       int len = strlen (name) + 16;
2925       nv[i] = XNEWVEC (char, len);
2926       snprintf (nv[i], len, "%s_%d", name, SSA_NAME_VERSION (p->t));
2927     }
2928   else
2929     {
2930       nv[i] = XNEWVEC (char, 16);
2931       snprintf (nv[i], 2 + 16, "T_%d", SSA_NAME_VERSION (p->t));
2932     }
2933
2934   p->name = nv[i];
2935 }
2936
2937 /* Return the maximal loop depth in SCOP.  */
2938
2939 static int
2940 scop_max_loop_depth (scop_p scop)
2941 {
2942   int i;
2943   graphite_bb_p gbb;
2944   int max_nb_loops = 0;
2945
2946   for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gbb); i++)
2947     {
2948       int nb_loops = gbb_nb_loops (gbb);
2949       if (max_nb_loops < nb_loops)
2950         max_nb_loops = nb_loops;
2951     }
2952
2953   return max_nb_loops;
2954 }
2955
2956 /* Initialize Cloog's parameter names from the names used in GIMPLE.
2957    Initialize Cloog's iterator names, using 'graphite_iterator_%d'
2958    from 0 to scop_nb_loops (scop).  */
2959
2960 static void
2961 initialize_cloog_names (scop_p scop)
2962 {
2963   int i, nb_params = VEC_length (name_tree, SCOP_PARAMS (scop));
2964   char **params = XNEWVEC (char *, nb_params);
2965   int nb_iterators = scop_max_loop_depth (scop);
2966   int nb_scattering= cloog_program_nb_scattdims (SCOP_PROG (scop));
2967   char **iterators = XNEWVEC (char *, nb_iterators * 2);
2968   char **scattering = XNEWVEC (char *, nb_scattering);
2969   name_tree p;
2970
2971   for (i = 0; VEC_iterate (name_tree, SCOP_PARAMS (scop), i, p); i++)
2972     save_var_name (params, i, p);
2973
2974   cloog_names_set_nb_parameters (cloog_program_names (SCOP_PROG (scop)),
2975                                  nb_params);
2976   cloog_names_set_parameters (cloog_program_names (SCOP_PROG (scop)),
2977                               params);
2978
2979   for (i = 0; i < nb_iterators; i++)
2980     {
2981       int len = 18 + 16;
2982       iterators[i] = XNEWVEC (char, len);
2983       snprintf (iterators[i], len, "graphite_iterator_%d", i);
2984     }
2985
2986   cloog_names_set_nb_iterators (cloog_program_names (SCOP_PROG (scop)),
2987                                 nb_iterators);
2988   cloog_names_set_iterators (cloog_program_names (SCOP_PROG (scop)),
2989                              iterators);
2990
2991   for (i = 0; i < nb_scattering; i++)
2992     {
2993       int len = 2 + 16;
2994       scattering[i] = XNEWVEC (char, len);
2995       snprintf (scattering[i], len, "s_%d", i);
2996     }
2997
2998   cloog_names_set_nb_scattering (cloog_program_names (SCOP_PROG (scop)),
2999                                  nb_scattering);
3000   cloog_names_set_scattering (cloog_program_names (SCOP_PROG (scop)),
3001                               scattering);
3002 }
3003
3004 /* Record the parameters used in the SCOP.  A variable is a parameter
3005    in a scop if it does not vary during the execution of that scop.  */
3006
3007 static void
3008 find_scop_parameters (scop_p scop)
3009 {
3010   graphite_bb_p gb;
3011   unsigned i;
3012   struct loop *loop;
3013   Value one;
3014
3015   value_init (one);
3016   value_set_si (one, 1);
3017
3018   /* Find the parameters used in the loop bounds.  */
3019   for (i = 0; VEC_iterate (loop_p, SCOP_LOOP_NEST (scop), i, loop); i++)
3020     {
3021       tree nb_iters = number_of_latch_executions (loop);
3022
3023       if (!chrec_contains_symbols (nb_iters))
3024         continue;
3025
3026       nb_iters = analyze_scalar_evolution (loop, nb_iters);
3027       nb_iters = instantiate_scev (block_before_scop (scop), loop, nb_iters);
3028       scan_tree_for_params (scop, nb_iters, NULL, 0, one, false);
3029     }
3030
3031   value_clear (one);
3032
3033   /* Find the parameters used in data accesses.  */
3034   for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
3035     find_params_in_bb (scop, gb);
3036
3037   SCOP_ADD_PARAMS (scop) = false;
3038 }
3039
3040 /* Build the context constraints for SCOP: constraints and relations
3041    on parameters.  */
3042
3043 static void
3044 build_scop_context (scop_p scop)
3045 {
3046   int nb_params = scop_nb_params (scop);
3047   CloogMatrix *matrix = cloog_matrix_alloc (1, nb_params + 2);
3048
3049   /* Insert '0 >= 0' in the context matrix, as it is not allowed to be
3050      empty. */
3051
3052   value_set_si (matrix->p[0][0], 1);
3053
3054   value_set_si (matrix->p[0][nb_params + 1], 0);
3055
3056   cloog_program_set_context (SCOP_PROG (scop),
3057                              cloog_domain_matrix2domain (matrix));
3058   cloog_matrix_free (matrix);
3059 }
3060
3061 /* Returns a graphite_bb from BB.  */
3062
3063 static inline graphite_bb_p
3064 gbb_from_bb (basic_block bb)
3065 {
3066   return (graphite_bb_p) bb->aux;
3067 }
3068
3069 /* Builds the constraint matrix for LOOP in SCOP.  NB_OUTER_LOOPS is the
3070    number of loops surrounding LOOP in SCOP.  OUTER_CSTR gives the
3071    constraints matrix for the surrounding loops.  */
3072
3073 static void
3074 build_loop_iteration_domains (scop_p scop, struct loop *loop,
3075                               CloogMatrix *outer_cstr, int nb_outer_loops)
3076 {
3077   int i, j, row;
3078   CloogMatrix *cstr;
3079   graphite_bb_p gb;
3080
3081   int nb_rows = outer_cstr->NbRows + 1;
3082   int nb_cols = outer_cstr->NbColumns + 1;
3083
3084   /* Last column of CSTR is the column of constants.  */
3085   int cst_col = nb_cols - 1;
3086
3087   /* The column for the current loop is just after the columns of
3088      other outer loops.  */
3089   int loop_col = nb_outer_loops + 1;
3090
3091   tree nb_iters = number_of_latch_executions (loop);
3092
3093   /* When the number of iterations is a constant or a parameter, we
3094      add a constraint for the upper bound of the loop.  So add a row
3095      to the constraint matrix before allocating it.  */
3096   if (TREE_CODE (nb_iters) == INTEGER_CST
3097       || !chrec_contains_undetermined (nb_iters))
3098     nb_rows++;
3099
3100   cstr = cloog_matrix_alloc (nb_rows, nb_cols);
3101
3102   /* Copy the outer constraints.  */
3103   for (i = 0; i < outer_cstr->NbRows; i++)
3104     {
3105       /* Copy the eq/ineq and loops columns.  */
3106       for (j = 0; j < loop_col; j++)
3107         value_assign (cstr->p[i][j], outer_cstr->p[i][j]);
3108
3109       /* Leave an empty column in CSTR for the current loop, and then
3110          copy the parameter columns.  */
3111       for (j = loop_col; j < outer_cstr->NbColumns; j++)
3112         value_assign (cstr->p[i][j + 1], outer_cstr->p[i][j]);
3113     }
3114
3115   /* 0 <= loop_i */
3116   row = outer_cstr->NbRows;
3117   value_set_si (cstr->p[row][0], 1);
3118   value_set_si (cstr->p[row][loop_col], 1);
3119
3120   /* loop_i <= nb_iters */
3121   if (TREE_CODE (nb_iters) == INTEGER_CST)
3122     {
3123       row++;
3124       value_set_si (cstr->p[row][0], 1);
3125       value_set_si (cstr->p[row][loop_col], -1);
3126
3127       value_set_si (cstr->p[row][cst_col],
3128                     int_cst_value (nb_iters));
3129     }
3130   else if (!chrec_contains_undetermined (nb_iters))
3131     {
3132       /* Otherwise nb_iters contains parameters: scan the nb_iters
3133          expression and build its matrix representation.  */
3134       Value one;
3135
3136       row++;
3137       value_set_si (cstr->p[row][0], 1);
3138       value_set_si (cstr->p[row][loop_col], -1);
3139
3140       nb_iters = analyze_scalar_evolution (loop, nb_iters);
3141       nb_iters = instantiate_scev (block_before_scop (scop), loop, nb_iters);
3142
3143       value_init (one);
3144       value_set_si (one, 1);
3145       scan_tree_for_params (scop, nb_iters, cstr, row, one, false);
3146       value_clear (one);
3147     }
3148   else
3149     gcc_unreachable ();
3150
3151   if (loop->inner && loop_in_sese_p (loop->inner, SCOP_REGION (scop)))
3152     build_loop_iteration_domains (scop, loop->inner, cstr, nb_outer_loops + 1);
3153
3154   /* Only go to the next loops, if we are not at the outermost layer.  These
3155      have to be handled seperately, as we can be sure, that the chain at this
3156      layer will be connected.  */
3157   if (nb_outer_loops != 0 && loop->next && loop_in_sese_p (loop->next,
3158                                                            SCOP_REGION (scop)))
3159     build_loop_iteration_domains (scop, loop->next, outer_cstr, nb_outer_loops);
3160
3161   for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
3162     if (gbb_loop (gb) == loop)
3163       GBB_DOMAIN (gb) = cloog_matrix_copy (cstr);
3164
3165   cloog_matrix_free (cstr);
3166 }
3167
3168 /* Add conditions to the domain of GB.  */
3169
3170 static void
3171 add_conditions_to_domain (graphite_bb_p gb)
3172 {
3173   unsigned int i,j;
3174   gimple stmt;
3175   VEC (gimple, heap) *conditions = GBB_CONDITIONS (gb);
3176   CloogMatrix *domain = GBB_DOMAIN (gb);
3177   scop_p scop = GBB_SCOP (gb);
3178
3179   unsigned nb_rows;
3180   unsigned nb_cols;
3181   unsigned nb_new_rows = 0;
3182   unsigned row;
3183
3184   if (VEC_empty (gimple, conditions))
3185     return;
3186
3187   if (domain)
3188     {
3189       nb_rows = domain->NbRows;
3190       nb_cols = domain->NbColumns;
3191     }
3192   else
3193     {
3194       nb_rows = 0;
3195       nb_cols = nb_loops_around_gb (gb) + scop_nb_params (scop) + 2;
3196     }
3197
3198   /* Count number of necessary new rows to add the conditions to the
3199      domain.  */
3200   for (i = 0; VEC_iterate (gimple, conditions, i, stmt); i++)
3201     {
3202       switch (gimple_code (stmt))
3203         {
3204         case GIMPLE_COND:
3205           {
3206             enum tree_code code = gimple_cond_code (stmt);
3207
3208             switch (code)
3209               {
3210               case NE_EXPR:
3211               case EQ_EXPR:
3212                 /* NE and EQ statements are not supported right know. */
3213                 gcc_unreachable ();
3214                 break;
3215               case LT_EXPR:
3216               case GT_EXPR:
3217               case LE_EXPR:
3218               case GE_EXPR:
3219                 nb_new_rows++;
3220                 break;
3221               default:
3222                 gcc_unreachable ();
3223                 break;
3224               }
3225           break;
3226           }
3227         case GIMPLE_SWITCH:
3228           /* Switch statements are not supported right know.  */
3229           gcc_unreachable ();
3230           break;
3231
3232         default:
3233           gcc_unreachable ();
3234           break;
3235         }
3236     }
3237
3238
3239   /* Enlarge the matrix.  */
3240   {
3241     CloogMatrix *new_domain;
3242     new_domain = cloog_matrix_alloc (nb_rows + nb_new_rows, nb_cols);
3243
3244     if (domain)
3245       {
3246         for (i = 0; i < nb_rows; i++)
3247           for (j = 0; j < nb_cols; j++)
3248             value_assign (new_domain->p[i][j], domain->p[i][j]);
3249
3250         cloog_matrix_free (domain);
3251       }
3252
3253     domain = new_domain;
3254     GBB_DOMAIN (gb) = new_domain;
3255   }
3256
3257   /* Add the conditions to the new enlarged domain matrix.  */
3258   row = nb_rows;
3259   for (i = 0; VEC_iterate (gimple, conditions, i, stmt); i++)
3260     {
3261       switch (gimple_code (stmt))
3262         {
3263         case GIMPLE_COND:
3264           {
3265             Value one;
3266             enum tree_code code;
3267             tree left;
3268             tree right;
3269             loop_p loop = GBB_BB (gb)->loop_father;
3270
3271             left = gimple_cond_lhs (stmt);
3272             right = gimple_cond_rhs (stmt);
3273
3274             left = analyze_scalar_evolution (loop, left);
3275             right = analyze_scalar_evolution (loop, right);
3276
3277             left = instantiate_scev (block_before_scop (scop), loop, left);
3278             right = instantiate_scev (block_before_scop (scop), loop, right);
3279
3280             code = gimple_cond_code (stmt);
3281
3282             /* The conditions for ELSE-branches are inverted.  */
3283             if (VEC_index (gimple, gb->condition_cases, i) == NULL)
3284               code = invert_tree_comparison (code, false);
3285
3286             switch (code)
3287               {
3288               case NE_EXPR:
3289                 /* NE statements are not supported right know. */
3290                 gcc_unreachable ();
3291                 break;
3292               case EQ_EXPR:
3293                 value_set_si (domain->p[row][0], 1);
3294                 value_init (one);
3295                 value_set_si (one, 1);
3296                 scan_tree_for_params (scop, left, domain, row, one, true);
3297                 value_set_si (one, 1);
3298                 scan_tree_for_params (scop, right, domain, row, one, false);
3299                 row++;
3300                 value_set_si (domain->p[row][0], 1);
3301                 value_set_si (one, 1);
3302                 scan_tree_for_params (scop, left, domain, row, one, false);
3303                 value_set_si (one, 1);
3304                 scan_tree_for_params (scop, right, domain, row, one, true);
3305                 value_clear (one);
3306                 row++;
3307                 break;
3308               case LT_EXPR:
3309                 value_set_si (domain->p[row][0], 1);
3310                 value_init (one);
3311                 value_set_si (one, 1);
3312                 scan_tree_for_params (scop, left, domain, row, one, true);
3313                 value_set_si (one, 1);
3314                 scan_tree_for_params (scop, right, domain, row, one, false);
3315                 value_sub_int (domain->p[row][nb_cols - 1],
3316                     domain->p[row][nb_cols - 1], 1);
3317                 value_clear (one);
3318                 row++;
3319                 break;
3320               case GT_EXPR:
3321                 value_set_si (domain->p[row][0], 1);
3322                 value_init (one);
3323                 value_set_si (one, 1);
3324                 scan_tree_for_params (scop, left, domain, row, one, false);
3325                 value_set_si (one, 1);
3326                 scan_tree_for_params (scop, right, domain, row, one, true);
3327                 value_sub_int (domain->p[row][nb_cols - 1],
3328                     domain->p[row][nb_cols - 1], 1);
3329                 value_clear (one);
3330                 row++;
3331                 break;
3332               case LE_EXPR:
3333                 value_set_si (domain->p[row][0], 1);
3334                 value_init (one);
3335                 value_set_si (one, 1);
3336                 scan_tree_for_params (scop, left, domain, row, one, true);
3337                 value_set_si (one, 1);
3338                 scan_tree_for_params (scop, right, domain, row, one, false);
3339                 value_clear (one);
3340                 row++;
3341                 break;
3342               case GE_EXPR:
3343                 value_set_si (domain->p[row][0], 1);
3344                 value_init (one);
3345                 value_set_si (one, 1);
3346                 scan_tree_for_params (scop, left, domain, row, one, false);
3347                 value_set_si (one, 1);
3348                 scan_tree_for_params (scop, right, domain, row, one, true);
3349                 value_clear (one);
3350                 row++;
3351                 break;
3352               default:
3353                 gcc_unreachable ();
3354                 break;
3355               }
3356             break;
3357           }
3358         case GIMPLE_SWITCH:
3359           /* Switch statements are not supported right know.  */
3360           gcc_unreachable ();
3361           break;
3362
3363         default:
3364           gcc_unreachable ();
3365           break;
3366         }
3367     }
3368 }
3369
3370 /* Returns true when PHI defines an induction variable in the loop
3371    containing the PHI node.  */
3372
3373 static bool
3374 phi_node_is_iv (gimple phi)
3375 {
3376   loop_p loop = gimple_bb (phi)->loop_father;
3377   tree scev = analyze_scalar_evolution (loop, gimple_phi_result (phi));
3378
3379   return tree_contains_chrecs (scev, NULL);
3380 }
3381
3382 /* Returns true when BB contains scalar phi nodes that are not an
3383    induction variable of a loop.  */
3384
3385 static bool
3386 bb_contains_non_iv_scalar_phi_nodes (basic_block bb)
3387 {
3388   gimple phi = NULL;
3389   gimple_stmt_iterator si;
3390
3391   for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
3392     if (is_gimple_reg (gimple_phi_result (gsi_stmt (si))))
3393       {
3394         /* Store the unique scalar PHI node: at this point, loops
3395            should be in cannonical form, so we expect to see at most
3396            one scalar phi node in the loop header.  */
3397         if (phi
3398             || bb != bb->loop_father->header)
3399           return true;
3400
3401         phi = gsi_stmt (si);
3402       }
3403
3404   if (!phi
3405       || phi_node_is_iv (phi))
3406     return false;
3407
3408   return true;
3409 }
3410
3411 /* Helper recursive function.  Record in CONDITIONS and CASES all
3412    conditions from 'if's and 'switch'es occurring in BB from SCOP.
3413
3414    Returns false when the conditions contain scalar computations that
3415    depend on the condition, i.e. when there are scalar phi nodes on
3416    the junction after the condition.  Only the computations occurring
3417    on memory can be handled in the polyhedral model: operations that
3418    define scalar evolutions in conditions, that can potentially be
3419    used to index memory, can't be handled by the polyhedral model.  */
3420
3421 static bool
3422 build_scop_conditions_1 (VEC (gimple, heap) **conditions,
3423                          VEC (gimple, heap) **cases, basic_block bb,
3424                          scop_p scop)
3425 {
3426   bool res = true;
3427   int i, j;
3428   graphite_bb_p gbb;
3429   basic_block bb_child, bb_iter;
3430   VEC (basic_block, heap) *dom;
3431   gimple stmt;
3432
3433   /* Make sure we are in the SCoP.  */
3434   if (!bb_in_sese_p (bb, SCOP_REGION (scop)))
3435     return true;
3436
3437   if (bb_contains_non_iv_scalar_phi_nodes (bb))
3438     return false;
3439
3440   gbb = gbb_from_bb (bb);
3441   if (gbb)
3442     {
3443       GBB_CONDITIONS (gbb) = VEC_copy (gimple, heap, *conditions);
3444       GBB_CONDITION_CASES (gbb) = VEC_copy (gimple, heap, *cases);
3445     }
3446
3447   dom = get_dominated_by (CDI_DOMINATORS, bb);
3448
3449   stmt = last_stmt (bb);
3450   if (stmt)
3451     {
3452       VEC (edge, gc) *edges;
3453       edge e;
3454
3455       switch (gimple_code (stmt))
3456         {
3457         case GIMPLE_COND:
3458           edges = bb->succs;
3459           for (i = 0; VEC_iterate (edge, edges, i, e); i++)
3460             if ((dominated_by_p (CDI_DOMINATORS, e->dest, bb))
3461                 && VEC_length (edge, e->dest->preds) == 1)
3462               {
3463                 /* Remove the scanned block from the dominator successors.  */
3464                 for (j = 0; VEC_iterate (basic_block, dom, j, bb_iter); j++)
3465                   if (bb_iter == e->dest)
3466                     {
3467                       VEC_unordered_remove (basic_block, dom, j);
3468                       break;
3469                     }
3470
3471                 /* Recursively scan the then or else part.  */
3472                 if (e->flags & EDGE_TRUE_VALUE)
3473                   VEC_safe_push (gimple, heap, *cases, stmt);
3474                 else
3475                   {
3476                     gcc_assert (e->flags & EDGE_FALSE_VALUE);
3477                     VEC_safe_push (gimple, heap, *cases, NULL);
3478                   }
3479
3480                 VEC_safe_push (gimple, heap, *conditions, stmt);
3481                 if (!build_scop_conditions_1 (conditions, cases, e->dest, scop))
3482                   {
3483                     res = false;
3484                     goto done;
3485                   }
3486                 VEC_pop (gimple, *conditions);
3487                 VEC_pop (gimple, *cases);
3488               }
3489           break;
3490
3491         case GIMPLE_SWITCH:
3492           {
3493             unsigned i;
3494             gimple_stmt_iterator gsi_search_gimple_label;
3495
3496             for (i = 0; i < gimple_switch_num_labels (stmt); ++i)
3497               {
3498                 basic_block bb_iter;
3499                 size_t k;
3500                 size_t n_cases = VEC_length (gimple, *conditions);
3501                 unsigned n = gimple_switch_num_labels (stmt);
3502
3503                 bb_child = label_to_block
3504                   (CASE_LABEL (gimple_switch_label (stmt, i)));
3505
3506                 for (k = 0; k < n; k++)
3507                   if (i != k
3508                       && label_to_block
3509                       (CASE_LABEL (gimple_switch_label (stmt, k))) == bb_child)
3510                     break;
3511
3512                 /* Switches with multiple case values for the same
3513                    block are not handled.  */
3514                 if (k != n
3515                     /* Switch cases with more than one predecessor are
3516                        not handled.  */
3517                     || VEC_length (edge, bb_child->preds) != 1)
3518                   {
3519                     res = false;
3520                     goto done;
3521                   }
3522
3523                 /* Recursively scan the corresponding 'case' block.  */
3524                 for (gsi_search_gimple_label = gsi_start_bb (bb_child);
3525                      !gsi_end_p (gsi_search_gimple_label);
3526                      gsi_next (&gsi_search_gimple_label))
3527                   {
3528                     gimple label = gsi_stmt (gsi_search_gimple_label);
3529
3530                     if (gimple_code (label) == GIMPLE_LABEL)
3531                       {
3532                         tree t = gimple_label_label (label);
3533
3534                         gcc_assert (t == gimple_switch_label (stmt, i));
3535                         VEC_replace (gimple, *cases, n_cases, label);
3536                         break;
3537                       }
3538                   }
3539
3540                 if (!build_scop_conditions_1 (conditions, cases, bb_child, scop))
3541                   {
3542                     res = false;
3543                     goto done;
3544                   }
3545
3546                 /* Remove the scanned block from the dominator successors.  */
3547                 for (j = 0; VEC_iterate (basic_block, dom, j, bb_iter); j++)
3548                   if (bb_iter == bb_child)
3549                     {
3550                       VEC_unordered_remove (basic_block, dom, j);
3551                       break;
3552                     }
3553               }
3554
3555             VEC_pop (gimple, *conditions);
3556             VEC_pop (gimple, *cases);
3557             break;
3558           }
3559
3560         default:
3561           break;
3562       }
3563   }
3564
3565   /* Scan all immediate dominated successors.  */
3566   for (i = 0; VEC_iterate (basic_block, dom, i, bb_child); i++)
3567     if (!build_scop_conditions_1 (conditions, cases, bb_child, scop))
3568       {
3569         res = false;
3570         goto done;
3571       }
3572
3573  done:
3574   VEC_free (basic_block, heap, dom);
3575   return res;
3576 }
3577
3578 /* Record all conditions from SCOP.
3579
3580    Returns false when the conditions contain scalar computations that
3581    depend on the condition, i.e. when there are scalar phi nodes on
3582    the junction after the condition.  Only the computations occurring
3583    on memory can be handled in the polyhedral model: operations that
3584    define scalar evolutions in conditions, that can potentially be
3585    used to index memory, can't be handled by the polyhedral model.  */
3586
3587 static bool
3588 build_scop_conditions (scop_p scop)
3589 {
3590   bool res;
3591   VEC (gimple, heap) *conditions = NULL;
3592   VEC (gimple, heap) *cases = NULL;
3593
3594   res = build_scop_conditions_1 (&conditions, &cases, SCOP_ENTRY (scop), scop);
3595
3596   VEC_free (gimple, heap, conditions);
3597   VEC_free (gimple, heap, cases);
3598   return res;
3599 }
3600
3601 /* Traverses all the GBBs of the SCOP and add their constraints to the
3602    iteration domains.  */
3603
3604 static void
3605 add_conditions_to_constraints (scop_p scop)
3606 {
3607   int i;
3608   graphite_bb_p gbb;
3609
3610   for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gbb); i++)
3611     add_conditions_to_domain (gbb);
3612 }
3613
3614 /* Build the current domain matrix: the loops belonging to the current
3615    SCOP, and that vary for the execution of the current basic block.
3616    Returns false if there is no loop in SCOP.  */
3617
3618 static bool
3619 build_scop_iteration_domain (scop_p scop)
3620 {
3621   struct loop *loop;
3622   CloogMatrix *outer_cstr;
3623   int i;
3624
3625   /* Build cloog loop for all loops, that are in the uppermost loop layer of
3626      this SCoP.  */
3627   for (i = 0; VEC_iterate (loop_p, SCOP_LOOP_NEST (scop), i, loop); i++)
3628     if (!loop_in_sese_p (loop_outer (loop), SCOP_REGION (scop)))
3629       {
3630         /* The outermost constraints is a matrix that has:
3631            -first column: eq/ineq boolean
3632            -last column: a constant
3633            -scop_nb_params columns for the parameters used in the scop.  */
3634         outer_cstr = cloog_matrix_alloc (0, scop_nb_params (scop) + 2);
3635         build_loop_iteration_domains (scop, loop, outer_cstr, 0);
3636         cloog_matrix_free (outer_cstr);
3637       }
3638
3639   return (i != 0);
3640 }
3641
3642 /* Initializes an equation CY of the access matrix using the
3643    information for a subscript from AF, relatively to the loop
3644    indexes from LOOP_NEST and parameter indexes from PARAMS.  NDIM is
3645    the dimension of the array access, i.e. the number of
3646    subscripts.  Returns true when the operation succeeds.  */
3647
3648 static bool
3649 build_access_matrix_with_af (tree af, lambda_vector cy,
3650                              scop_p scop, int ndim)
3651 {
3652   int param_col;
3653
3654   switch (TREE_CODE (af))
3655     {
3656     case POLYNOMIAL_CHREC:
3657       {
3658         struct loop *outer_loop;
3659         tree left = CHREC_LEFT (af);
3660         tree right = CHREC_RIGHT (af);
3661         int var;
3662
3663         if (TREE_CODE (right) != INTEGER_CST)
3664           return false;
3665
3666         outer_loop = get_loop (CHREC_VARIABLE (af));
3667         var = nb_loops_around_loop_in_scop (outer_loop, scop);
3668         cy[var] = int_cst_value (right);
3669
3670         switch (TREE_CODE (left))
3671           {
3672           case POLYNOMIAL_CHREC:
3673             return build_access_matrix_with_af (left, cy, scop, ndim);
3674
3675           case INTEGER_CST:
3676             cy[ndim - 1] = int_cst_value (left);
3677             return true;
3678
3679           default:
3680             return build_access_matrix_with_af (left, cy, scop, ndim);
3681           }
3682       }
3683
3684     case PLUS_EXPR:
3685       build_access_matrix_with_af (TREE_OPERAND (af, 0), cy, scop, ndim);
3686       build_access_matrix_with_af (TREE_OPERAND (af, 1), cy, scop, ndim);
3687       return true;
3688
3689     case MINUS_EXPR:
3690       build_access_matrix_with_af (TREE_OPERAND (af, 0), cy, scop, ndim);
3691       build_access_matrix_with_af (TREE_OPERAND (af, 1), cy, scop, ndim);
3692       return true;
3693
3694     case INTEGER_CST:
3695       cy[ndim - 1] = int_cst_value (af);
3696       return true;
3697
3698     case SSA_NAME:
3699       param_col = param_index (af, scop);
3700       cy [ndim - scop_nb_params (scop) + param_col - 1] = 1;
3701 &n