gcc/graphite.c

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