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 \f
1187
1188 /* Structure containing the mapping between the old names and the new
1189    names used after block copy in the new loop context.  */
1190 typedef struct rename_map_elt
1191 {
1192   tree old_name, new_name;
1193 } *rename_map_elt;
1194
1195
1196 /* Print to stderr the element ELT.  */
1197
1198 static void
1199 debug_rename_elt (rename_map_elt elt)
1200 {
1201   fprintf (stderr, "(");
1202   print_generic_expr (stderr, elt->old_name, 0);
1203   fprintf (stderr, ", ");
1204   print_generic_expr (stderr, elt->new_name, 0);
1205   fprintf (stderr, ")\n");
1206 }
1207
1208 /* Helper function for debug_rename_map.  */
1209
1210 static int
1211 debug_rename_map_1 (void **slot, void *s ATTRIBUTE_UNUSED)
1212 {
1213   struct rename_map_elt *entry = (struct rename_map_elt *) *slot;
1214   debug_rename_elt (entry);
1215   return 1;
1216 }
1217
1218 /* Print to stderr all the elements of MAP.  */
1219
1220 void
1221 debug_rename_map (htab_t map)
1222 {
1223   htab_traverse (map, debug_rename_map_1, NULL);
1224 }
1225
1226 /* Constructs a new SCEV_INFO_STR structure for VAR and INSTANTIATED_BELOW.  */
1227
1228 static inline rename_map_elt
1229 new_rename_map_elt (tree old_name, tree new_name)
1230 {
1231   rename_map_elt res;
1232
1233   res = XNEW (struct rename_map_elt);
1234   res->old_name = old_name;
1235   res->new_name = new_name;
1236
1237   return res;
1238 }
1239
1240 /* Computes a hash function for database element ELT.  */
1241
1242 static hashval_t
1243 rename_map_elt_info (const void *elt)
1244 {
1245   return htab_hash_pointer (((const struct rename_map_elt *) elt)->old_name);
1246 }
1247
1248 /* Compares database elements E1 and E2.  */
1249
1250 static int
1251 eq_rename_map_elts (const void *e1, const void *e2)
1252 {
1253   const struct rename_map_elt *elt1 = (const struct rename_map_elt *) e1;
1254   const struct rename_map_elt *elt2 = (const struct rename_map_elt *) e2;
1255
1256   return (elt1->old_name == elt2->old_name);
1257 }
1258
1259 /* Returns the new name associated to OLD_NAME in MAP.  */
1260
1261 static tree
1262 get_new_name_from_old_name (htab_t map, tree old_name)
1263 {
1264   struct rename_map_elt tmp;
1265   PTR *slot;
1266
1267   tmp.old_name = old_name;
1268   slot = htab_find_slot (map, &tmp, NO_INSERT);
1269
1270   if (slot && *slot)
1271     return ((rename_map_elt) *slot)->new_name;
1272
1273   return old_name;
1274 }
1275
1276 \f
1277
1278 /* Returns true when BB is in REGION.  */
1279
1280 static bool
1281 bb_in_sese_p (basic_block bb, sese region)
1282 {
1283   return pointer_set_contains (SESE_REGION_BBS (region), bb);
1284 }
1285
1286 /* For a USE in BB, if BB is outside REGION, mark the USE in the
1287    SESE_LIVEIN and SESE_LIVEOUT sets.  */
1288
1289 static void
1290 sese_build_livein_liveouts_use (sese region, basic_block bb, tree use)
1291 {
1292   unsigned ver;
1293   basic_block def_bb;
1294
1295   if (TREE_CODE (use) != SSA_NAME)
1296     return;
1297
1298   ver = SSA_NAME_VERSION (use);
1299   def_bb = gimple_bb (SSA_NAME_DEF_STMT (use));
1300   if (!def_bb
1301       || !bb_in_sese_p (def_bb, region)
1302       || bb_in_sese_p (bb, region))
1303     return;
1304
1305   if (!SESE_LIVEIN_VER (region, ver))
1306     SESE_LIVEIN_VER (region, ver) = BITMAP_ALLOC (NULL);
1307
1308   bitmap_set_bit (SESE_LIVEIN_VER (region, ver), bb->index);
1309   bitmap_set_bit (SESE_LIVEOUT (region), ver);
1310 }
1311
1312 /* Marks for rewrite all the SSA_NAMES defined in REGION and that are
1313    used in BB that is outside of the REGION.  */
1314
1315 static void
1316 sese_build_livein_liveouts_bb (sese region, basic_block bb)
1317 {
1318   gimple_stmt_iterator bsi;
1319   edge e;
1320   edge_iterator ei;
1321   ssa_op_iter iter;
1322   tree var;
1323
1324   FOR_EACH_EDGE (e, ei, bb->succs)
1325     for (bsi = gsi_start_phis (e->dest); !gsi_end_p (bsi); gsi_next (&bsi))
1326       sese_build_livein_liveouts_use (region, bb,
1327                                       PHI_ARG_DEF_FROM_EDGE (gsi_stmt (bsi), e));
1328
1329   for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
1330     FOR_EACH_SSA_TREE_OPERAND (var, gsi_stmt (bsi), iter, SSA_OP_ALL_USES)
1331       sese_build_livein_liveouts_use (region, bb, var);
1332 }
1333
1334 /* Build the SESE_LIVEIN and SESE_LIVEOUT for REGION.  */
1335
1336 void
1337 sese_build_livein_liveouts (sese region)
1338 {
1339   basic_block bb;
1340
1341   SESE_LIVEOUT (region) = BITMAP_ALLOC (NULL);
1342   SESE_NUM_VER (region) = num_ssa_names;
1343   SESE_LIVEIN (region) = XCNEWVEC (bitmap, SESE_NUM_VER (region));
1344
1345   FOR_EACH_BB (bb)
1346     sese_build_livein_liveouts_bb (region, bb);
1347 }
1348
1349 /* Register basic blocks belonging to a region in a pointer set.  */
1350
1351 static void
1352 register_bb_in_sese (basic_block entry_bb, basic_block exit_bb, sese region)
1353 {
1354   edge_iterator ei;
1355   edge e;
1356   basic_block bb = entry_bb;
1357
1358   FOR_EACH_EDGE (e, ei, bb->succs)
1359     {
1360       if (!pointer_set_contains (SESE_REGION_BBS (region), e->dest) &&
1361           e->dest->index != exit_bb->index)
1362         {
1363           pointer_set_insert (SESE_REGION_BBS (region), e->dest);
1364           register_bb_in_sese (e->dest, exit_bb, region);
1365         }
1366     }
1367 }
1368
1369 /* Builds a new SESE region from edges ENTRY and EXIT.  */
1370
1371 sese
1372 new_sese (edge entry, edge exit)
1373 {
1374   sese res = XNEW (struct sese);
1375
1376   SESE_ENTRY (res) = entry;
1377   SESE_EXIT (res) = exit;
1378   SESE_REGION_BBS (res) = pointer_set_create ();
1379   register_bb_in_sese (entry->dest, exit->dest, res);
1380
1381   SESE_LIVEOUT (res) = NULL;
1382   SESE_NUM_VER (res) = 0;
1383   SESE_LIVEIN (res) = NULL;
1384
1385   return res;
1386 }
1387
1388 /* Deletes REGION.  */
1389
1390 void
1391 free_sese (sese region)
1392 {
1393   int i;
1394
1395   for (i = 0; i < SESE_NUM_VER (region); i++)
1396     BITMAP_FREE (SESE_LIVEIN_VER (region, i));
1397
1398   if (SESE_LIVEIN (region))
1399     free (SESE_LIVEIN (region));
1400
1401   if (SESE_LIVEOUT (region))
1402     BITMAP_FREE (SESE_LIVEOUT (region));
1403
1404   pointer_set_destroy (SESE_REGION_BBS (region));
1405   XDELETE (region);
1406 }
1407
1408 \f
1409
1410 /* Creates a new scop starting with ENTRY.  */
1411
1412 static scop_p
1413 new_scop (edge entry, edge exit)
1414 {
1415   scop_p scop = XNEW (struct scop);
1416
1417   gcc_assert (entry && exit);
1418
1419   SCOP_REGION (scop) = new_sese (entry, exit);
1420   SCOP_BBS (scop) = VEC_alloc (graphite_bb_p, heap, 3);
1421   SCOP_OLDIVS (scop) = VEC_alloc (name_tree, heap, 3);
1422   SCOP_BBS_B (scop) = BITMAP_ALLOC (NULL);
1423   SCOP_LOOPS (scop) = BITMAP_ALLOC (NULL);
1424   SCOP_LOOP_NEST (scop) = VEC_alloc (loop_p, heap, 3);
1425   SCOP_ADD_PARAMS (scop) = true;
1426   SCOP_PARAMS (scop) = VEC_alloc (name_tree, heap, 3);
1427   SCOP_PROG (scop) = cloog_program_malloc ();
1428   cloog_program_set_names (SCOP_PROG (scop), cloog_names_malloc ());
1429   SCOP_LOOP2CLOOG_LOOP (scop) = htab_create (10, hash_loop_to_cloog_loop,
1430                                              eq_loop_to_cloog_loop,
1431                                              free);
1432   SCOP_LIVEOUT_RENAMES (scop) = htab_create (10, rename_map_elt_info,
1433                                              eq_rename_map_elts, free);
1434   return scop;
1435 }
1436
1437 /* Deletes SCOP.  */
1438
1439 static void
1440 free_scop (scop_p scop)
1441 {
1442   int i;
1443   name_tree p;
1444   struct graphite_bb *gb;
1445   name_tree iv;
1446
1447   for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
1448     free_graphite_bb (gb);
1449
1450   VEC_free (graphite_bb_p, heap, SCOP_BBS (scop));
1451   BITMAP_FREE (SCOP_BBS_B (scop));
1452   BITMAP_FREE (SCOP_LOOPS (scop));
1453   VEC_free (loop_p, heap, SCOP_LOOP_NEST (scop));
1454
1455   for (i = 0; VEC_iterate (name_tree, SCOP_OLDIVS (scop), i, iv); i++)
1456     free (iv);
1457   VEC_free (name_tree, heap, SCOP_OLDIVS (scop));
1458
1459   for (i = 0; VEC_iterate (name_tree, SCOP_PARAMS (scop), i, p); i++)
1460     free (p);
1461
1462   VEC_free (name_tree, heap, SCOP_PARAMS (scop));
1463   cloog_program_free (SCOP_PROG (scop));
1464   htab_delete (SCOP_LOOP2CLOOG_LOOP (scop));
1465   htab_delete (SCOP_LIVEOUT_RENAMES (scop));
1466   free_sese (SCOP_REGION (scop));
1467   XDELETE (scop);
1468 }
1469
1470 /* Deletes all scops in SCOPS.  */
1471
1472 static void
1473 free_scops (VEC (scop_p, heap) *scops)
1474 {
1475   int i;
1476   scop_p scop;
1477
1478   for (i = 0; VEC_iterate (scop_p, scops, i, scop); i++)
1479     free_scop (scop);
1480
1481   VEC_free (scop_p, heap, scops);
1482 }
1483
1484 typedef enum gbb_type {
1485   GBB_UNKNOWN,
1486   GBB_LOOP_SING_EXIT_HEADER,
1487   GBB_LOOP_MULT_EXIT_HEADER,
1488   GBB_LOOP_EXIT,
1489   GBB_COND_HEADER,
1490   GBB_SIMPLE,
1491   GBB_LAST
1492 } gbb_type;
1493
1494 /* Detect the type of BB.  Loop headers are only marked, if they are
1495    new.  This means their loop_father is different to LAST_LOOP.
1496    Otherwise they are treated like any other bb and their type can be
1497    any other type.  */
1498
1499 static gbb_type
1500 get_bb_type (basic_block bb, struct loop *last_loop)
1501 {
1502   VEC (basic_block, heap) *dom;
1503   int nb_dom, nb_suc;
1504   struct loop *loop = bb->loop_father;
1505
1506   /* Check, if we entry into a new loop. */
1507   if (loop != last_loop)
1508     {
1509       if (single_exit (loop) != NULL)
1510         return GBB_LOOP_SING_EXIT_HEADER;
1511       else if (loop->num != 0)
1512         return GBB_LOOP_MULT_EXIT_HEADER;
1513       else
1514         return GBB_COND_HEADER;
1515     }
1516
1517   dom = get_dominated_by (CDI_DOMINATORS, bb);
1518   nb_dom = VEC_length (basic_block, dom);
1519   VEC_free (basic_block, heap, dom);
1520
1521   if (nb_dom == 0)
1522     return GBB_LAST;
1523
1524   nb_suc = VEC_length (edge, bb->succs);
1525
1526   if (nb_dom == 1 && nb_suc == 1)
1527     return GBB_SIMPLE;
1528
1529   return GBB_COND_HEADER;
1530 }
1531
1532 /* A SCoP detection region, defined using bbs as borders.
1533    All control flow touching this region, comes in passing basic_block ENTRY and
1534    leaves passing basic_block EXIT.  By using bbs instead of edges for the
1535    borders we are able to represent also regions that do not have a single
1536    entry or exit edge.
1537    But as they have a single entry basic_block and a single exit basic_block, we
1538    are able to generate for every sd_region a single entry and exit edge.
1539
1540    1   2
1541     \ /
1542      3  <- entry
1543      |
1544      4
1545     / \                 This region contains: {3, 4, 5, 6, 7, 8}
1546    5   6
1547    |   |
1548    7   8
1549     \ /
1550      9  <- exit  */
1551
1552
1553 typedef struct sd_region_p
1554 {
1555   /* The entry bb dominates all bbs in the sd_region.  It is part of the
1556      region.  */
1557   basic_block entry;
1558
1559   /* The exit bb postdominates all bbs in the sd_region, but is not
1560      part of the region.  */
1561   basic_block exit;
1562 } sd_region;
1563
1564 DEF_VEC_O(sd_region);
1565 DEF_VEC_ALLOC_O(sd_region, heap);
1566
1567
1568 /* Moves the scops from SOURCE to TARGET and clean up SOURCE.  */
1569
1570 static void
1571 move_sd_regions (VEC (sd_region, heap) **source, VEC (sd_region, heap) **target)
1572 {
1573   sd_region *s;
1574   int i;
1575
1576   for (i = 0; VEC_iterate (sd_region, *source, i, s); i++)
1577     VEC_safe_push (sd_region, heap, *target, s);
1578
1579   VEC_free (sd_region, heap, *source);
1580 }
1581
1582 /* Store information needed by scopdet_* functions.  */
1583
1584 struct scopdet_info
1585 {
1586   /* Where the last open scop would stop if the current BB is harmful.  */
1587   basic_block last;
1588
1589   /* Where the next scop would start if the current BB is harmful.  */
1590   basic_block next;
1591
1592   /* The bb or one of its children contains open loop exits.  That means
1593      loop exit nodes that are not surrounded by a loop dominated by bb.  */
1594   bool exits;
1595
1596   /* The bb or one of its children contains only structures we can handle.  */
1597   bool difficult;
1598 };
1599
1600
1601 static struct scopdet_info build_scops_1 (basic_block, VEC (sd_region, heap) **,
1602                                           loop_p);
1603
1604 /* Calculates BB infos. If bb is difficult we add valid SCoPs dominated by BB
1605    to SCOPS.  TYPE is the gbb_type of BB.  */
1606
1607 static struct scopdet_info
1608 scopdet_basic_block_info (basic_block bb, VEC (sd_region, heap) **scops,
1609                           gbb_type type)
1610 {
1611   struct loop *loop = bb->loop_father;
1612   struct scopdet_info result;
1613   gimple stmt;
1614
1615   /* XXX: ENTRY_BLOCK_PTR could be optimized in later steps.  */
1616   stmt = harmful_stmt_in_bb (ENTRY_BLOCK_PTR, bb);
1617   result.difficult = (stmt != NULL);
1618   result.last = NULL;
1619
1620   switch (type)
1621     {
1622     case GBB_LAST:
1623       result.next = NULL;
1624       result.exits = false;
1625       result.last = bb;
1626       break;
1627
1628     case GBB_SIMPLE:
1629       result.next = single_succ (bb);
1630       result.exits = false;
1631       result.last = bb;
1632       break;
1633
1634     case GBB_LOOP_SING_EXIT_HEADER:
1635       {
1636         VEC (sd_region, heap) *tmp_scops = VEC_alloc (sd_region, heap,3);
1637         struct scopdet_info sinfo;
1638
1639         sinfo = build_scops_1 (bb, &tmp_scops, loop);
1640
1641         result.last = single_exit (bb->loop_father)->src;
1642         result.next = single_exit (bb->loop_father)->dest;
1643
1644         /* If we do not dominate result.next, remove it.  It's either
1645            the EXIT_BLOCK_PTR, or another bb dominates it and will
1646            call the scop detection for this bb.  */
1647         if (!dominated_by_p (CDI_DOMINATORS, result.next, bb))
1648           result.next = NULL;
1649
1650         if (result.last->loop_father != loop)
1651           result.next = NULL;
1652
1653         if (TREE_CODE (number_of_latch_executions (loop))
1654             == SCEV_NOT_KNOWN)
1655           result.difficult = true;
1656
1657         if (sinfo.difficult)
1658           move_sd_regions (&tmp_scops, scops);
1659         else
1660           VEC_free (sd_region, heap, tmp_scops);
1661
1662         result.exits = false;
1663         result.difficult |= sinfo.difficult;
1664         break;
1665       }
1666
1667     case GBB_LOOP_MULT_EXIT_HEADER:
1668       {
1669         /* XXX: For now we just do not join loops with multiple exits.  If the
1670            exits lead to the same bb it may be possible to join the loop.  */
1671         VEC (sd_region, heap) *tmp_scops = VEC_alloc (sd_region, heap, 3);
1672         VEC (edge, heap) *exits = get_loop_exit_edges (loop);
1673         edge e;
1674         int i;
1675         build_scops_1 (bb, &tmp_scops, loop);
1676
1677         /* Scan the code dominated by this loop.  This means all bbs, that are
1678            are dominated by a bb in this loop, but are not part of this loop.
1679
1680            The easiest case:
1681              - The loop exit destination is dominated by the exit sources.
1682
1683            TODO: We miss here the more complex cases:
1684                   - The exit destinations are dominated by another bb inside the
1685                     loop.
1686                   - The loop dominates bbs, that are not exit destinations.  */
1687         for (i = 0; VEC_iterate (edge, exits, i, e); i++)
1688           if (e->src->loop_father == loop
1689               && dominated_by_p (CDI_DOMINATORS, e->dest, e->src))
1690             {
1691               /* Pass loop_outer to recognize e->dest as loop header in
1692                  build_scops_1.  */
1693               if (e->dest->loop_father->header == e->dest)
1694                 build_scops_1 (e->dest, &tmp_scops,
1695                                loop_outer (e->dest->loop_father));
1696               else
1697                 build_scops_1 (e->dest, &tmp_scops, e->dest->loop_father);
1698             }
1699
1700         result.next = NULL;
1701         result.last = NULL;
1702         result.difficult = true;
1703         result.exits = false;
1704         move_sd_regions (&tmp_scops, scops);
1705         VEC_free (edge, heap, exits);
1706         break;
1707       }
1708     case GBB_COND_HEADER:
1709       {
1710         VEC (sd_region, heap) *tmp_scops = VEC_alloc (sd_region, heap, 3);
1711         struct scopdet_info sinfo;
1712         VEC (basic_block, heap) *dominated;
1713         int i;
1714         basic_block dom_bb;
1715         basic_block last_bb = NULL;
1716         edge e;
1717         result.exits = false;
1718
1719         /* First check the successors of BB, and check if it is possible to join
1720            the different branches.  */
1721         for (i = 0; VEC_iterate (edge, bb->succs, i, e); i++)
1722           {
1723             /* Ignore loop exits.  They will be handled after the loop body.  */
1724             if (is_loop_exit (loop, e->dest))
1725               {
1726                 result.exits = true;
1727                 continue;
1728               }
1729
1730             /* Do not follow edges that lead to the end of the
1731                conditions block.  For example, in
1732
1733                |   0
1734                |  /|\
1735                | 1 2 |
1736                | | | |
1737                | 3 4 |
1738                |  \|/
1739                |   6
1740
1741                the edge from 0 => 6.  Only check if all paths lead to
1742                the same node 6.  */
1743
1744             if (!single_pred_p (e->dest))
1745               {
1746                 /* Check, if edge leads directly to the end of this
1747                    condition.  */
1748                 if (!last_bb)
1749                   {
1750                     last_bb = e->dest;
1751                   }
1752
1753                 if (e->dest != last_bb)
1754                   result.difficult = true;
1755
1756                 continue;
1757               }
1758
1759             if (!dominated_by_p (CDI_DOMINATORS, e->dest, bb))
1760               {
1761                 result.difficult = true;
1762                 continue;
1763               }
1764
1765             sinfo = build_scops_1 (e->dest, &tmp_scops, loop);
1766
1767             result.exits |= sinfo.exits;
1768             result.last = sinfo.last;
1769             result.difficult |= sinfo.difficult;
1770
1771             /* Checks, if all branches end at the same point.
1772                If that is true, the condition stays joinable.
1773                Have a look at the example above.  */
1774             if (sinfo.last && single_succ_p (sinfo.last))
1775               {
1776                 basic_block next_tmp = single_succ (sinfo.last);
1777
1778                 if (!last_bb)
1779                     last_bb = next_tmp;
1780
1781                 if (next_tmp != last_bb)
1782                   result.difficult = true;
1783               }
1784             else
1785               result.difficult = true;
1786           }
1787
1788         /* If the condition is joinable.  */
1789         if (!result.exits && !result.difficult)
1790           {
1791             /* Only return a next pointer if we dominate this pointer.
1792                Otherwise it will be handled by the bb dominating it.  */
1793             if (dominated_by_p (CDI_DOMINATORS, last_bb, bb) && last_bb != bb)
1794               result.next = last_bb;
1795             else
1796               result.next = NULL;
1797
1798             VEC_free (sd_region, heap, tmp_scops);
1799             break;
1800           }
1801
1802         /* Scan remaining bbs dominated by BB.  */
1803         dominated = get_dominated_by (CDI_DOMINATORS, bb);
1804
1805         for (i = 0; VEC_iterate (basic_block, dominated, i, dom_bb); i++)
1806           {
1807             /* Ignore loop exits: they will be handled after the loop body.  */
1808             if (loop_depth (find_common_loop (loop, dom_bb->loop_father))
1809                 < loop_depth (loop))
1810               {
1811                 result.exits = true;
1812                 continue;
1813               }
1814
1815             /* Ignore the bbs processed above.  */
1816             if (single_pred_p (dom_bb) && single_pred (dom_bb) == bb)
1817               continue;
1818
1819             if (loop_depth (loop) > loop_depth (dom_bb->loop_father))
1820               sinfo = build_scops_1 (dom_bb, &tmp_scops, loop_outer (loop));
1821             else
1822               sinfo = build_scops_1 (dom_bb, &tmp_scops, loop);
1823
1824
1825             result.exits |= sinfo.exits;
1826             result.difficult = true;
1827             result.last = NULL;
1828           }
1829
1830         VEC_free (basic_block, heap, dominated);
1831
1832         result.next = NULL;
1833         move_sd_regions (&tmp_scops, scops);
1834
1835         break;
1836       }
1837
1838     default:
1839       gcc_unreachable ();
1840     }
1841
1842   return result;
1843 }
1844
1845 /* Creates the SCoPs and writes entry and exit points for every SCoP.  */
1846
1847 static struct scopdet_info
1848 build_scops_1 (basic_block current, VEC (sd_region, heap) **scops, loop_p loop)
1849 {
1850   bool in_scop = false;
1851   sd_region open_scop;
1852   struct scopdet_info sinfo;
1853
1854   /* Initialize result.  */
1855   struct scopdet_info result;
1856   result.exits = false;
1857   result.difficult = false;
1858   result.next = NULL;
1859   result.last = NULL;
1860   open_scop.entry = NULL;
1861   open_scop.exit = NULL;
1862   sinfo.last = NULL;
1863
1864   /* Loop over the dominance tree.  If we meet a difficult bb, close
1865      the current SCoP.  Loop and condition header start a new layer,
1866      and can only be added if all bbs in deeper layers are simple.  */
1867   while (current != NULL)
1868     {
1869       sinfo = scopdet_basic_block_info (current, scops, get_bb_type (current,
1870                                                                      loop));
1871
1872       if (!in_scop && !(sinfo.exits || sinfo.difficult))
1873         {
1874           open_scop.entry = current;
1875           open_scop.exit = NULL;
1876           in_scop = true;
1877         }
1878       else if (in_scop && (sinfo.exits || sinfo.difficult))
1879         {
1880           open_scop.exit = current;
1881           VEC_safe_push (sd_region, heap, *scops, &open_scop);
1882           in_scop = false;
1883         }
1884
1885       result.difficult |= sinfo.difficult;
1886       result.exits |= sinfo.exits;
1887
1888       current = sinfo.next;
1889     }
1890
1891   /* Try to close open_scop, if we are still in an open SCoP.  */
1892   if (in_scop)
1893     {
1894       int i;
1895       edge e;
1896
1897         for (i = 0; VEC_iterate (edge, sinfo.last->succs, i, e); i++)
1898           if (dominated_by_p (CDI_POST_DOMINATORS, sinfo.last, e->dest))
1899             open_scop.exit = e->dest;
1900
1901         if (!open_scop.exit && open_scop.entry != sinfo.last)
1902           open_scop.exit = sinfo.last;
1903
1904         if (open_scop.exit)
1905           VEC_safe_push (sd_region, heap, *scops, &open_scop);
1906
1907     }
1908
1909   result.last = sinfo.last;
1910   return result;
1911 }
1912
1913 /* Checks if a bb is contained in REGION.  */
1914
1915 static bool
1916 bb_in_sd_region (basic_block bb, sd_region *region)
1917 {
1918   return dominated_by_p (CDI_DOMINATORS, bb, region->entry)
1919          && !(dominated_by_p (CDI_DOMINATORS, bb, region->exit)
1920               && !dominated_by_p (CDI_DOMINATORS, region->entry,
1921                                   region->exit));
1922 }
1923
1924 /* Returns the single entry edge of REGION, if it does not exits NULL.  */
1925
1926 static edge
1927 find_single_entry_edge (sd_region *region)
1928 {
1929   edge e;
1930   edge_iterator ei;
1931   edge entry = NULL;
1932
1933   FOR_EACH_EDGE (e, ei, region->entry->preds)
1934     if (!bb_in_sd_region (e->src, region))
1935       {
1936         if (entry)
1937           {
1938             entry = NULL;
1939             break;
1940           }
1941
1942         else
1943           entry = e;
1944       }
1945
1946   return entry;
1947 }
1948
1949 /* Returns the single exit edge of REGION, if it does not exits NULL.  */
1950
1951 static edge
1952 find_single_exit_edge (sd_region *region)
1953 {
1954   edge e;
1955   edge_iterator ei;
1956   edge exit = NULL;
1957
1958   FOR_EACH_EDGE (e, ei, region->exit->preds)
1959     if (bb_in_sd_region (e->src, region))
1960       {
1961         if (exit)
1962           {
1963             exit = NULL;
1964             break;
1965           }
1966
1967         else
1968           exit = e;
1969       }
1970
1971   return exit;
1972 }
1973
1974 /* Create a single entry edge for REGION.  */
1975
1976 static void
1977 create_single_entry_edge (sd_region *region)
1978 {
1979   if (find_single_entry_edge (region))
1980     return;
1981
1982   /* There are multiple predecessors for bb_3
1983
1984   |  1  2
1985   |  | /
1986   |  |/
1987   |  3  <- entry
1988   |  |\
1989   |  | |
1990   |  4 ^
1991   |  | |
1992   |  |/
1993   |  5
1994
1995   There are two edges (1->3, 2->3), that point from outside into the region,
1996   and another one (5->3), a loop latch, lead to bb_3.
1997
1998   We split bb_3.
1999
2000   |  1  2
2001   |  | /
2002   |  |/
2003   |3.0
2004   |  |\     (3.0 -> 3.1) = single entry edge
2005   |3.1 |        <- entry
2006   |  | |
2007   |  | |
2008   |  4 ^
2009   |  | |
2010   |  |/
2011   |  5
2012
2013   If the loop is part of the SCoP, we have to redirect the loop latches.
2014
2015   |  1  2
2016   |  | /
2017   |  |/
2018   |3.0
2019   |  |      (3.0 -> 3.1) = entry edge
2020   |3.1          <- entry
2021   |  |\
2022   |  | |
2023   |  4 ^
2024   |  | |
2025   |  |/
2026   |  5  */
2027
2028   if (region->entry->loop_father->header != region->entry
2029       || dominated_by_p (CDI_DOMINATORS,
2030                          loop_latch_edge (region->entry->loop_father)->src,
2031                          region->exit))
2032     {
2033       edge forwarder = split_block_after_labels (region->entry);
2034       region->entry = forwarder->dest;
2035     }
2036   else
2037     /* This case is never executed, as the loop headers seem always to have a
2038        single edge pointing from outside into the loop.  */
2039     gcc_unreachable ();
2040
2041 #ifdef ENABLE_CHECKING
2042   gcc_assert (find_single_entry_edge (region));
2043 #endif
2044 }
2045
2046 /* Check if the sd_region, mentioned in EDGE, has no exit bb.  */
2047
2048 static bool
2049 sd_region_without_exit (edge e)
2050 {
2051   sd_region *r = (sd_region *) e->aux;
2052
2053   if (r)
2054     return r->exit == NULL;
2055   else
2056     return false;
2057 }
2058
2059 /* Create a single exit edge for REGION.  */
2060
2061 static void
2062 create_single_exit_edge (sd_region *region)
2063 {
2064   edge e;
2065   edge_iterator ei;
2066   edge forwarder = NULL;
2067   basic_block exit;
2068
2069   if (find_single_exit_edge (region))
2070     return;
2071
2072   /* We create a forwarder bb (5) for all edges leaving this region
2073      (3->5, 4->5).  All other edges leading to the same bb, are moved
2074      to a new bb (6).  If these edges where part of another region (2->5)
2075      we update the region->exit pointer, of this region.
2076
2077      To identify which edge belongs to which region we depend on the e->aux
2078      pointer in every edge.  It points to the region of the edge or to NULL,
2079      if the edge is not part of any region.
2080
2081      1 2 3 4    1->5 no region,                 2->5 region->exit = 5,
2082       \| |/     3->5 region->exit = NULL,       4->5 region->exit = NULL
2083         5       <- exit
2084
2085      changes to
2086
2087      1 2 3 4    1->6 no region,                         2->6 region->exit = 6,
2088      | | \/     3->5 no region,                         4->5 no region,
2089      | |  5
2090       \| /      5->6 region->exit = 6
2091         6
2092
2093      Now there is only a single exit edge (5->6).  */
2094   exit = region->exit;
2095   region->exit = NULL;
2096   forwarder = make_forwarder_block (exit, &sd_region_without_exit, NULL);
2097
2098   /* Unmark the edges, that are no longer exit edges.  */
2099   FOR_EACH_EDGE (e, ei, forwarder->src->preds)
2100     if (e->aux)
2101       e->aux = NULL;
2102
2103   /* Mark the new exit edge.  */
2104   single_succ_edge (forwarder->src)->aux = region;
2105
2106   /* Update the exit bb of all regions, where exit edges lead to
2107      forwarder->dest.  */
2108   FOR_EACH_EDGE (e, ei, forwarder->dest->preds)
2109     if (e->aux)
2110       ((sd_region *) e->aux)->exit = forwarder->dest;
2111
2112 #ifdef ENABLE_CHECKING
2113   gcc_assert (find_single_exit_edge (region));
2114 #endif
2115 }
2116
2117 /* Unmark the exit edges of all REGIONS.
2118    See comment in "create_single_exit_edge". */
2119
2120 static void
2121 unmark_exit_edges (VEC (sd_region, heap) *regions)
2122 {
2123   int i;
2124   sd_region *s;
2125   edge e;
2126   edge_iterator ei;
2127
2128   for (i = 0; VEC_iterate (sd_region, regions, i, s); i++)
2129     FOR_EACH_EDGE (e, ei, s->exit->preds)
2130       e->aux = NULL;
2131 }
2132
2133
2134 /* Mark the exit edges of all REGIONS.
2135    See comment in "create_single_exit_edge". */
2136
2137 static void
2138 mark_exit_edges (VEC (sd_region, heap) *regions)
2139 {
2140   int i;
2141   sd_region *s;
2142   edge e;
2143   edge_iterator ei;
2144
2145   for (i = 0; VEC_iterate (sd_region, regions, i, s); i++)
2146     FOR_EACH_EDGE (e, ei, s->exit->preds)
2147       if (bb_in_sd_region (e->src, s))
2148         e->aux = s;
2149 }
2150
2151 /* Free and compute again all the dominators information.  */
2152
2153 static inline void
2154 recompute_all_dominators (void)
2155 {
2156   mark_irreducible_loops ();
2157   free_dominance_info (CDI_DOMINATORS);
2158   free_dominance_info (CDI_POST_DOMINATORS);
2159   calculate_dominance_info (CDI_DOMINATORS);
2160   calculate_dominance_info (CDI_POST_DOMINATORS);
2161 }
2162
2163 /* Verifies properties that GRAPHITE should maintain during translation.  */
2164
2165 static inline void
2166 graphite_verify (void)
2167 {
2168 #ifdef ENABLE_CHECKING
2169   verify_loop_structure ();
2170   verify_dominators (CDI_DOMINATORS);
2171   verify_dominators (CDI_POST_DOMINATORS);
2172   verify_ssa (false);
2173 #endif
2174 }
2175
2176 /* Create for all scop regions a single entry and a single exit edge.  */
2177
2178 static void
2179 create_sese_edges (VEC (sd_region, heap) *regions)
2180 {
2181   int i;
2182   sd_region *s;
2183
2184   for (i = 0; VEC_iterate (sd_region, regions, i, s); i++)
2185     create_single_entry_edge (s);
2186
2187   mark_exit_edges (regions);
2188
2189   for (i = 0; VEC_iterate (sd_region, regions, i, s); i++)
2190     create_single_exit_edge (s);
2191
2192   unmark_exit_edges (regions);
2193
2194   fix_loop_structure (NULL);
2195
2196 #ifdef ENABLE_CHECKING
2197   verify_loop_structure ();
2198   verify_dominators (CDI_DOMINATORS);
2199   verify_ssa (false);
2200 #endif
2201 }
2202
2203 /* Create graphite SCoPs from an array of scop detection regions.  */
2204
2205 static void
2206 build_graphite_scops (VEC (sd_region, heap) *scop_regions)
2207 {
2208   int i;
2209   sd_region *s;
2210
2211   for (i = 0; VEC_iterate (sd_region, scop_regions, i, s); i++)
2212     {
2213       edge entry = find_single_entry_edge (s);
2214       edge exit = find_single_exit_edge (s);
2215       scop_p scop = new_scop (entry, exit);
2216       VEC_safe_push (scop_p, heap, current_scops, scop);
2217
2218       /* Are there overlapping SCoPs?  */
2219 #ifdef ENABLE_CHECKING
2220         {
2221           int j;
2222           sd_region *s2;
2223
2224           for (j = 0; VEC_iterate (sd_region, scop_regions, j, s2); j++)
2225             if (s != s2)
2226               gcc_assert (!bb_in_sd_region (s->entry, s2));
2227         }
2228 #endif
2229     }
2230 }
2231
2232 /* Find static control parts.  */
2233
2234 static void
2235 build_scops (void)
2236 {
2237   struct loop *loop = current_loops->tree_root;
2238   VEC (sd_region, heap) *tmp_scops = VEC_alloc (sd_region, heap, 3);
2239
2240   build_scops_1 (single_succ (ENTRY_BLOCK_PTR), &tmp_scops, loop);
2241   create_sese_edges (tmp_scops);
2242   build_graphite_scops (tmp_scops);
2243   VEC_free (sd_region, heap, tmp_scops);
2244 }
2245
2246 /* Gather the basic blocks belonging to the SCOP.  */
2247
2248 static void
2249 build_scop_bbs (scop_p scop)
2250 {
2251   basic_block *stack = XNEWVEC (basic_block, n_basic_blocks + 1);
2252   sbitmap visited = sbitmap_alloc (last_basic_block);
2253   int sp = 0;
2254
2255   sbitmap_zero (visited);
2256   stack[sp++] = SCOP_ENTRY (scop);
2257
2258   while (sp)
2259     {
2260       basic_block bb = stack[--sp];
2261       int depth = loop_depth (bb->loop_father);
2262       int num = bb->loop_father->num;
2263       edge_iterator ei;
2264       edge e;
2265
2266       /* Scop's exit is not in the scop.  Exclude also bbs, which are
2267          dominated by the SCoP exit.  These are e.g. loop latches.  */
2268       if (TEST_BIT (visited, bb->index)
2269           || dominated_by_p (CDI_DOMINATORS, bb, SCOP_EXIT (scop))
2270           /* Every block in the scop is dominated by scop's entry.  */
2271           || !dominated_by_p (CDI_DOMINATORS, bb, SCOP_ENTRY (scop)))
2272         continue;
2273
2274       new_graphite_bb (scop, bb);
2275       SET_BIT (visited, bb->index);
2276
2277       /* First push the blocks that have to be processed last.  Note
2278          that this means that the order in which the code is organized
2279          below is important: do not reorder the following code.  */
2280       FOR_EACH_EDGE (e, ei, bb->succs)
2281         if (! TEST_BIT (visited, e->dest->index)
2282             && (int) loop_depth (e->dest->loop_father) < depth)
2283           stack[sp++] = e->dest;
2284
2285       FOR_EACH_EDGE (e, ei, bb->succs)
2286         if (! TEST_BIT (visited, e->dest->index)
2287             && (int) loop_depth (e->dest->loop_father) == depth
2288             && e->dest->loop_father->num != num)
2289           stack[sp++] = e->dest;
2290
2291       FOR_EACH_EDGE (e, ei, bb->succs)
2292         if (! TEST_BIT (visited, e->dest->index)
2293             && (int) loop_depth (e->dest->loop_father) == depth
2294             && e->dest->loop_father->num == num
2295             && EDGE_COUNT (e->dest->preds) > 1)
2296           stack[sp++] = e->dest;
2297
2298       FOR_EACH_EDGE (e, ei, bb->succs)
2299         if (! TEST_BIT (visited, e->dest->index)
2300             && (int) loop_depth (e->dest->loop_father) == depth
2301             && e->dest->loop_father->num == num
2302             && EDGE_COUNT (e->dest->preds) == 1)
2303           stack[sp++] = e->dest;
2304
2305       FOR_EACH_EDGE (e, ei, bb->succs)
2306         if (! TEST_BIT (visited, e->dest->index)
2307             && (int) loop_depth (e->dest->loop_father) > depth)
2308           stack[sp++] = e->dest;
2309     }
2310
2311   free (stack);
2312   sbitmap_free (visited);
2313 }
2314
2315 /* Returns the number of reduction phi nodes in LOOP.  */
2316
2317 static int
2318 nb_reductions_in_loop (loop_p loop)
2319 {
2320   int res = 0;
2321   gimple_stmt_iterator gsi;
2322
2323   for (gsi = gsi_start_phis (loop->header); !gsi_end_p (gsi); gsi_next (&gsi))
2324     {
2325       gimple phi = gsi_stmt (gsi);
2326       tree scev;
2327       affine_iv iv;
2328
2329       if (!is_gimple_reg (PHI_RESULT (phi)))
2330         continue;
2331
2332       scev = analyze_scalar_evolution (loop, PHI_RESULT (phi));
2333       scev = instantiate_parameters (loop, scev);
2334       if (!simple_iv (loop, phi, PHI_RESULT (phi), &iv, true))
2335         res++;
2336     }
2337
2338   return res;
2339 }
2340
2341 /* A LOOP is in normal form when it contains only one scalar phi node
2342    that defines the main induction variable of the loop, only one
2343    increment of the IV, and only one exit condition. */
2344
2345 static tree
2346 graphite_loop_normal_form (loop_p loop)
2347 {
2348   struct tree_niter_desc niter;
2349   tree nit;
2350   gimple_seq stmts;
2351   edge exit = single_dom_exit (loop);
2352
2353   if (!number_of_iterations_exit (loop, exit, &niter, false))
2354     gcc_unreachable ();
2355
2356   nit = force_gimple_operand (unshare_expr (niter.niter), &stmts, true,
2357                               NULL_TREE);
2358   if (stmts)
2359     gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
2360
2361   /* One IV per loop.  */
2362   if (nb_reductions_in_loop (loop) > 0)
2363     return NULL_TREE;
2364
2365   return canonicalize_loop_ivs (loop, NULL, nit);
2366 }
2367
2368 /* Record LOOP as occuring in SCOP.  Returns true when the operation
2369    was successful.  */
2370
2371 static bool
2372 scop_record_loop (scop_p scop, loop_p loop)
2373 {
2374   tree induction_var;
2375   name_tree oldiv;
2376
2377   if (bitmap_bit_p (SCOP_LOOPS (scop), loop->num))
2378     return true;
2379
2380   bitmap_set_bit (SCOP_LOOPS (scop), loop->num);
2381   VEC_safe_push (loop_p, heap, SCOP_LOOP_NEST (scop), loop);
2382
2383   induction_var = graphite_loop_normal_form (loop);
2384   if (!induction_var)
2385     return false;
2386
2387   oldiv = XNEW (struct name_tree);
2388   oldiv->t = induction_var;
2389   oldiv->name = get_name (SSA_NAME_VAR (oldiv->t));
2390   oldiv->loop = loop;
2391   VEC_safe_push (name_tree, heap, SCOP_OLDIVS (scop), oldiv);
2392   return true;
2393 }
2394
2395 /* Build the loop nests contained in SCOP.  Returns true when the
2396    operation was successful.  */
2397
2398 static bool
2399 build_scop_loop_nests (scop_p scop)
2400 {
2401   unsigned i;
2402   basic_block bb;
2403   struct loop *loop0, *loop1;
2404
2405   FOR_EACH_BB (bb)
2406     if (bb_in_scop_p (bb, scop))
2407       {
2408         struct loop *loop = bb->loop_father;
2409
2410         /* Only add loops if they are completely contained in the SCoP.  */
2411         if (loop->header == bb
2412             && bb_in_scop_p (loop->latch, scop))
2413           {
2414             if (!scop_record_loop (scop, loop))
2415               return false;
2416           }
2417       }
2418
2419   /* Make sure that the loops in the SCOP_LOOP_NEST are ordered.  It
2420      can be the case that an inner loop is inserted before an outer
2421      loop.  To avoid this, semi-sort once.  */
2422   for (i = 0; VEC_iterate (loop_p, SCOP_LOOP_NEST (scop), i, loop0); i++)
2423     {
2424       if (VEC_length (loop_p, SCOP_LOOP_NEST (scop)) == i + 1)
2425         break;
2426
2427       loop1 = VEC_index (loop_p, SCOP_LOOP_NEST (scop), i + 1);
2428       if (loop0->num > loop1->num)
2429         {
2430           VEC_replace (loop_p, SCOP_LOOP_NEST (scop), i, loop1);
2431           VEC_replace (loop_p, SCOP_LOOP_NEST (scop), i + 1, loop0);
2432         }
2433     }
2434
2435   return true;
2436 }
2437
2438 /* Build dynamic schedules for all the BBs. */
2439
2440 static void
2441 build_scop_dynamic_schedules (scop_p scop)
2442 {
2443   int i, dim, loop_num, row, col;
2444   graphite_bb_p gb;
2445
2446   for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
2447     {
2448       loop_num = GBB_BB (gb)->loop_father->num;
2449
2450       if (loop_num != 0)
2451         {
2452           dim = nb_loops_around_gb (gb);
2453           GBB_DYNAMIC_SCHEDULE (gb) = cloog_matrix_alloc (dim, dim);
2454
2455           for (row = 0; row < GBB_DYNAMIC_SCHEDULE (gb)->NbRows; row++)
2456             for (col = 0; col < GBB_DYNAMIC_SCHEDULE (gb)->NbColumns; col++)
2457               if (row == col)
2458                 value_set_si (GBB_DYNAMIC_SCHEDULE (gb)->p[row][col], 1);
2459               else
2460                 value_set_si (GBB_DYNAMIC_SCHEDULE (gb)->p[row][col], 0);
2461         }
2462       else
2463         GBB_DYNAMIC_SCHEDULE (gb) = NULL;
2464     }
2465 }
2466
2467 /* Build for BB the static schedule.
2468
2469    The STATIC_SCHEDULE is defined like this:
2470
2471    A
2472    for (i: ...)
2473      {
2474        for (j: ...)
2475          {
2476            B
2477            C
2478          }
2479
2480        for (k: ...)
2481          {
2482            D
2483            E
2484          }
2485      }
2486    F
2487
2488    Static schedules for A to F:
2489
2490      DEPTH
2491      0 1 2
2492    A 0
2493    B 1 0 0
2494    C 1 0 1
2495    D 1 1 0
2496    E 1 1 1
2497    F 2
2498 */
2499
2500 static void
2501 build_scop_canonical_schedules (scop_p scop)
2502 {
2503   int i, j;
2504   graphite_bb_p gb;
2505   int nb = scop_nb_loops (scop) + 1;
2506
2507   SCOP_STATIC_SCHEDULE (scop) = lambda_vector_new (nb);
2508
2509   for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
2510     {
2511       int offset = nb_loops_around_gb (gb);
2512
2513       /* After leaving a loop, it is possible that the schedule is not
2514          set at zero.  This loop reinitializes components located
2515          after OFFSET.  */
2516
2517       for (j = offset + 1; j < nb; j++)
2518         if (SCOP_STATIC_SCHEDULE (scop)[j])
2519           {
2520             memset (&(SCOP_STATIC_SCHEDULE (scop)[j]), 0,
2521                     sizeof (int) * (nb - j));
2522             ++SCOP_STATIC_SCHEDULE (scop)[offset];
2523             break;
2524           }
2525
2526       GBB_STATIC_SCHEDULE (gb) = lambda_vector_new (offset + 1);
2527       lambda_vector_copy (SCOP_STATIC_SCHEDULE (scop),
2528                           GBB_STATIC_SCHEDULE (gb), offset + 1);
2529
2530       ++SCOP_STATIC_SCHEDULE (scop)[offset];
2531     }
2532 }
2533
2534 /* Build the LOOPS vector for all bbs in SCOP.  */
2535
2536 static void
2537 build_bb_loops (scop_p scop)
2538 {
2539   graphite_bb_p gb;
2540   int i;
2541
2542   for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
2543     {
2544       loop_p loop;
2545       int depth;
2546
2547       depth = nb_loops_around_gb (gb) - 1;
2548
2549       GBB_LOOPS (gb) = VEC_alloc (loop_p, heap, 3);
2550       VEC_safe_grow_cleared (loop_p, heap, GBB_LOOPS (gb), depth + 1);
2551
2552       loop = GBB_BB (gb)->loop_father;
2553
2554       while (scop_contains_loop (scop, loop))
2555         {
2556           VEC_replace (loop_p, GBB_LOOPS (gb), depth, loop);
2557           loop = loop_outer (loop);
2558           depth--;
2559         }
2560     }
2561 }
2562
2563 /* Get the index for parameter VAR in SCOP.  */
2564
2565 static int
2566 param_index (tree var, scop_p scop)
2567 {
2568   int i;
2569   name_tree p;
2570   name_tree nvar;
2571
2572   gcc_assert (TREE_CODE (var) == SSA_NAME);
2573
2574   for (i = 0; VEC_iterate (name_tree, SCOP_PARAMS (scop), i, p); i++)
2575     if (p->t == var)
2576       return i;
2577
2578   gcc_assert (SCOP_ADD_PARAMS (scop));
2579
2580   nvar = XNEW (struct name_tree);
2581   nvar->t = var;
2582   nvar->name = NULL;
2583   VEC_safe_push (name_tree, heap, SCOP_PARAMS (scop), nvar);
2584   return VEC_length (name_tree, SCOP_PARAMS (scop)) - 1;
2585 }
2586
2587 /* Scan EXPR and translate it to an inequality vector INEQ that will
2588    be added, or subtracted, in the constraint domain matrix C at row
2589    R.  K is the number of columns for loop iterators in C. */
2590
2591 static void
2592 scan_tree_for_params (scop_p s, tree e, CloogMatrix *c, int r, Value k,
2593                       bool subtract)
2594 {
2595   int cst_col, param_col;
2596
2597   if (e == chrec_dont_know)
2598     return;
2599
2600   switch (TREE_CODE (e))
2601     {
2602     case POLYNOMIAL_CHREC:
2603       {
2604         tree left = CHREC_LEFT (e);
2605         tree right = CHREC_RIGHT (e);
2606         int var = CHREC_VARIABLE (e);
2607
2608         if (TREE_CODE (right) != INTEGER_CST)
2609           return;
2610
2611         if (c)
2612           {
2613             int loop_col = scop_gimple_loop_depth (s, get_loop (var)) + 1;
2614
2615             if (subtract)
2616               value_sub_int (c->p[r][loop_col], c->p[r][loop_col],
2617                              int_cst_value (right));
2618             else
2619               value_add_int (c->p[r][loop_col], c->p[r][loop_col],
2620                              int_cst_value (right));
2621           }
2622
2623         switch (TREE_CODE (left))
2624           {
2625           case POLYNOMIAL_CHREC:
2626             scan_tree_for_params (s, left, c, r, k, subtract);
2627             return;
2628
2629           case INTEGER_CST:
2630             /* Constant part.  */
2631             if (c)
2632               {
2633                 int v = int_cst_value (left);
2634                 cst_col = c->NbColumns - 1;
2635
2636                 if (v < 0)
2637                   {
2638                     v = -v;
2639                     subtract = subtract ? false : true;
2640                   }
2641
2642                 if (subtract)
2643                   value_sub_int (c->p[r][cst_col], c->p[r][cst_col], v);
2644                 else
2645                   value_add_int (c->p[r][cst_col], c->p[r][cst_col], v);
2646               }
2647             return;
2648
2649           default:
2650             scan_tree_for_params (s, left, c, r, k, subtract);
2651             return;
2652           }
2653       }
2654       break;
2655
2656     case MULT_EXPR:
2657       if (chrec_contains_symbols (TREE_OPERAND (e, 0)))
2658         {
2659           if (c)
2660             {
2661               Value val;
2662               gcc_assert (host_integerp (TREE_OPERAND (e, 1), 0));
2663               value_init (val);
2664               value_set_si (val, int_cst_value (TREE_OPERAND (e, 1)));
2665               value_multiply (k, k, val);
2666               value_clear (val);
2667             }
2668           scan_tree_for_params (s, TREE_OPERAND (e, 0), c, r, k, subtract);
2669         }
2670       else
2671         {
2672           if (c)
2673             {
2674               Value val;
2675               gcc_assert (host_integerp (TREE_OPERAND (e, 0), 0));
2676               value_init (val);
2677               value_set_si (val, int_cst_value (TREE_OPERAND (e, 0)));
2678               value_multiply (k, k, val);
2679               value_clear (val);
2680             }
2681           scan_tree_for_params (s, TREE_OPERAND (e, 1), c, r, k, subtract);
2682         }
2683       break;
2684
2685     case PLUS_EXPR:
2686     case POINTER_PLUS_EXPR:
2687       scan_tree_for_params (s, TREE_OPERAND (e, 0), c, r, k, subtract);
2688       scan_tree_for_params (s, TREE_OPERAND (e, 1), c, r, k, subtract);
2689       break;
2690
2691     case MINUS_EXPR:
2692       scan_tree_for_params (s, TREE_OPERAND (e, 0), c, r, k, subtract);
2693       value_oppose (k, k);
2694       scan_tree_for_params (s, TREE_OPERAND (e, 1), c, r, k, subtract);
2695       break;
2696
2697     case NEGATE_EXPR:
2698       value_oppose (k, k);
2699       scan_tree_for_params (s, TREE_OPERAND (e, 0), c, r, k, subtract);
2700       break;
2701
2702     case SSA_NAME:
2703       param_col = param_index (e, s);
2704
2705       if (c)
2706         {
2707           param_col += c->NbColumns - scop_nb_params (s) - 1;
2708
2709           if (subtract)
2710             value_subtract (c->p[r][param_col], c->p[r][param_col], k);
2711           else
2712             value_addto (c->p[r][param_col], c->p[r][param_col], k);
2713         }
2714       break;
2715
2716     case INTEGER_CST:
2717       if (c)
2718         {
2719           int v = int_cst_value (e);
2720           cst_col = c->NbColumns - 1;
2721
2722           if (v < 0)
2723           {
2724             v = -v;
2725             subtract = subtract ? false : true;
2726           }
2727
2728           if (subtract)
2729             value_sub_int (c->p[r][cst_col], c->p[r][cst_col], v);
2730           else
2731             value_add_int (c->p[r][cst_col], c->p[r][cst_col], v);
2732         }
2733       break;
2734
2735     case NOP_EXPR:
2736     case CONVERT_EXPR:
2737     case NON_LVALUE_EXPR:
2738       scan_tree_for_params (s, TREE_OPERAND (e, 0), c, r, k, subtract);
2739       break;
2740
2741     default:
2742       gcc_unreachable ();
2743       break;
2744     }
2745 }
2746
2747 /* Data structure for idx_record_params.  */
2748
2749 struct irp_data
2750 {
2751   struct loop *loop;
2752   scop_p scop;
2753 };
2754
2755 /* For a data reference with an ARRAY_REF as its BASE, record the
2756    parameters occurring in IDX.  DTA is passed in as complementary
2757    information, and is used by the automatic walker function.  This
2758    function is a callback for for_each_index.  */
2759
2760 static bool
2761 idx_record_params (tree base, tree *idx, void *dta)
2762 {
2763   struct irp_data *data = (struct irp_data *) dta;
2764
2765   if (TREE_CODE (base) != ARRAY_REF)
2766     return true;
2767
2768   if (TREE_CODE (*idx) == SSA_NAME)
2769     {
2770       tree scev;
2771       scop_p scop = data->scop;
2772       struct loop *loop = data->loop;
2773       Value one;
2774
2775       scev = analyze_scalar_evolution (loop, *idx);
2776       scev = instantiate_scev (block_before_scop (scop), loop, scev);
2777
2778       value_init (one);
2779       value_set_si (one, 1);
2780       scan_tree_for_params (scop, scev, NULL, 0, one, false);
2781       value_clear (one);
2782     }
2783
2784   return true;
2785 }
2786
2787 /* Find parameters with respect to SCOP in BB. We are looking in memory
2788    access functions, conditions and loop bounds.  */
2789
2790 static void
2791 find_params_in_bb (scop_p scop, graphite_bb_p gb)
2792 {
2793   int i;
2794   data_reference_p dr;
2795   gimple stmt;
2796   loop_p father = GBB_BB (gb)->loop_father;
2797
2798   for (i = 0; VEC_iterate (data_reference_p, GBB_DATA_REFS (gb), i, dr); i++)
2799     {
2800       struct irp_data irp;
2801
2802       irp.loop = father;
2803       irp.scop = scop;
2804       for_each_index (&dr->ref, idx_record_params, &irp);
2805     }
2806
2807   /* Find parameters in conditional statements.  */
2808   for (i = 0; VEC_iterate (gimple, GBB_CONDITIONS (gb), i, stmt); i++)
2809     {
2810       Value one;
2811       loop_p loop = father;
2812
2813       tree lhs, rhs;
2814
2815       lhs = gimple_cond_lhs (stmt);
2816       lhs = analyze_scalar_evolution (loop, lhs);
2817       lhs = instantiate_scev (block_before_scop (scop), loop, lhs);
2818
2819       rhs = gimple_cond_rhs (stmt);
2820       rhs = analyze_scalar_evolution (loop, rhs);
2821       rhs = instantiate_scev (block_before_scop (scop), loop, rhs);
2822
2823       value_init (one);
2824       scan_tree_for_params (scop, lhs, NULL, 0, one, false);
2825       value_set_si (one, 1);
2826       scan_tree_for_params (scop, rhs, NULL, 0, one, false);
2827       value_clear (one);
2828     }
2829 }
2830
2831 /* Saves in NV the name of variable P->T.  */
2832
2833 static void
2834 save_var_name (char **nv, int i, name_tree p)
2835 {
2836   const char *name = get_name (SSA_NAME_VAR (p->t));
2837
2838   if (name)
2839     {
2840       int len = strlen (name) + 16;
2841       nv[i] = XNEWVEC (char, len);
2842       snprintf (nv[i], len, "%s_%d", name, SSA_NAME_VERSION (p->t));
2843     }
2844   else
2845     {
2846       nv[i] = XNEWVEC (char, 16);
2847       snprintf (nv[i], 2 + 16, "T_%d", SSA_NAME_VERSION (p->t));
2848     }
2849
2850   p->name = nv[i];
2851 }
2852
2853 /* Return the maximal loop depth in SCOP.  */
2854
2855 static int
2856 scop_max_loop_depth (scop_p scop)
2857 {
2858   int i;
2859   graphite_bb_p gbb;
2860   int max_nb_loops = 0;
2861
2862   for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gbb); i++)
2863     {
2864       int nb_loops = gbb_nb_loops (gbb);
2865       if (max_nb_loops < nb_loops)
2866         max_nb_loops = nb_loops;
2867     }
2868
2869   return max_nb_loops;
2870 }
2871
2872 /* Initialize Cloog's parameter names from the names used in GIMPLE.
2873    Initialize Cloog's iterator names, using 'graphite_iterator_%d'
2874    from 0 to scop_nb_loops (scop).  */
2875
2876 static void
2877 initialize_cloog_names (scop_p scop)
2878 {
2879   int i, nb_params = VEC_length (name_tree, SCOP_PARAMS (scop));
2880   char **params = XNEWVEC (char *, nb_params);
2881   int nb_iterators = scop_max_loop_depth (scop);
2882   int nb_scattering= cloog_program_nb_scattdims (SCOP_PROG (scop));
2883   char **iterators = XNEWVEC (char *, nb_iterators * 2);
2884   char **scattering = XNEWVEC (char *, nb_scattering);
2885   name_tree p;
2886
2887   for (i = 0; VEC_iterate (name_tree, SCOP_PARAMS (scop), i, p); i++)
2888     save_var_name (params, i, p);
2889
2890   cloog_names_set_nb_parameters (cloog_program_names (SCOP_PROG (scop)),
2891                                  nb_params);
2892   cloog_names_set_parameters (cloog_program_names (SCOP_PROG (scop)),
2893                               params);
2894
2895   for (i = 0; i < nb_iterators; i++)
2896     {
2897       int len = 18 + 16;
2898       iterators[i] = XNEWVEC (char, len);
2899       snprintf (iterators[i], len, "graphite_iterator_%d", i);
2900     }
2901
2902   cloog_names_set_nb_iterators (cloog_program_names (SCOP_PROG (scop)),
2903                                 nb_iterators);
2904   cloog_names_set_iterators (cloog_program_names (SCOP_PROG (scop)),
2905                              iterators);
2906
2907   for (i = 0; i < nb_scattering; i++)
2908     {
2909       int len = 2 + 16;
2910       scattering[i] = XNEWVEC (char, len);
2911       snprintf (scattering[i], len, "s_%d", i);
2912     }
2913
2914   cloog_names_set_nb_scattering (cloog_program_names (SCOP_PROG (scop)),
2915                                  nb_scattering);
2916   cloog_names_set_scattering (cloog_program_names (SCOP_PROG (scop)),
2917                               scattering);
2918 }
2919
2920 /* Record the parameters used in the SCOP.  A variable is a parameter
2921    in a scop if it does not vary during the execution of that scop.  */
2922
2923 static void
2924 find_scop_parameters (scop_p scop)
2925 {
2926   graphite_bb_p gb;
2927   unsigned i;
2928   struct loop *loop;
2929   Value one;
2930
2931   value_init (one);
2932   value_set_si (one, 1);
2933
2934   /* Find the parameters used in the loop bounds.  */
2935   for (i = 0; VEC_iterate (loop_p, SCOP_LOOP_NEST (scop), i, loop); i++)
2936     {
2937       tree nb_iters = number_of_latch_executions (loop);
2938
2939       if (!chrec_contains_symbols (nb_iters))
2940         continue;
2941
2942       nb_iters = analyze_scalar_evolution (loop, nb_iters);
2943       nb_iters = instantiate_scev (block_before_scop (scop), loop, nb_iters);
2944       scan_tree_for_params (scop, nb_iters, NULL, 0, one, false);
2945     }
2946
2947   value_clear (one);
2948
2949   /* Find the parameters used in data accesses.  */
2950   for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
2951     find_params_in_bb (scop, gb);
2952
2953   SCOP_ADD_PARAMS (scop) = false;
2954 }
2955
2956 /* Build the context constraints for SCOP: constraints and relations
2957    on parameters.  */
2958
2959 static void
2960 build_scop_context (scop_p scop)
2961 {
2962   int nb_params = scop_nb_params (scop);
2963   CloogMatrix *matrix = cloog_matrix_alloc (1, nb_params + 2);
2964
2965   /* Insert '0 >= 0' in the context matrix, as it is not allowed to be
2966      empty. */
2967
2968   value_set_si (matrix->p[0][0], 1);
2969
2970   value_set_si (matrix->p[0][nb_params + 1], 0);
2971
2972   cloog_program_set_context (SCOP_PROG (scop),
2973                              cloog_domain_matrix2domain (matrix));
2974   cloog_matrix_free (matrix);
2975 }
2976
2977 /* Returns a graphite_bb from BB.  */
2978
2979 static inline graphite_bb_p
2980 gbb_from_bb (basic_block bb)
2981 {
2982   return (graphite_bb_p) bb->aux;
2983 }
2984
2985 /* Builds the constraint matrix for LOOP in SCOP.  NB_OUTER_LOOPS is the
2986    number of loops surrounding LOOP in SCOP.  OUTER_CSTR gives the
2987    constraints matrix for the surrounding loops.  */
2988
2989 static void
2990 build_loop_iteration_domains (scop_p scop, struct loop *loop,
2991                               CloogMatrix *outer_cstr, int nb_outer_loops)
2992 {
2993   int i, j, row;
2994   CloogMatrix *cstr;
2995   graphite_bb_p gb;
2996
2997   int nb_rows = outer_cstr->NbRows + 1;
2998   int nb_cols = outer_cstr->NbColumns + 1;
2999
3000   /* Last column of CSTR is the column of constants.  */
3001   int cst_col = nb_cols - 1;
3002
3003   /* The column for the current loop is just after the columns of
3004      other outer loops.  */
3005   int loop_col = nb_outer_loops + 1;
3006
3007   tree nb_iters = number_of_latch_executions (loop);
3008
3009   /* When the number of iterations is a constant or a parameter, we
3010      add a constraint for the upper bound of the loop.  So add a row
3011      to the constraint matrix before allocating it.  */
3012   if (TREE_CODE (nb_iters) == INTEGER_CST
3013       || !chrec_contains_undetermined (nb_iters))
3014     nb_rows++;
3015
3016   cstr = cloog_matrix_alloc (nb_rows, nb_cols);
3017
3018   /* Copy the outer constraints.  */
3019   for (i = 0; i < outer_cstr->NbRows; i++)
3020     {
3021       /* Copy the eq/ineq and loops columns.  */
3022       for (j = 0; j < loop_col; j++)
3023         value_assign (cstr->p[i][j], outer_cstr->p[i][j]);
3024
3025       /* Leave an empty column in CSTR for the current loop, and then
3026          copy the parameter columns.  */
3027       for (j = loop_col; j < outer_cstr->NbColumns; j++)
3028         value_assign (cstr->p[i][j + 1], outer_cstr->p[i][j]);
3029     }
3030
3031   /* 0 <= loop_i */
3032   row = outer_cstr->NbRows;
3033   value_set_si (cstr->p[row][0], 1);
3034   value_set_si (cstr->p[row][loop_col], 1);
3035
3036   /* loop_i <= nb_iters */
3037   if (TREE_CODE (nb_iters) == INTEGER_CST)
3038     {
3039       row++;
3040       value_set_si (cstr->p[row][0], 1);
3041       value_set_si (cstr->p[row][loop_col], -1);
3042
3043       value_set_si (cstr->p[row][cst_col],
3044                     int_cst_value (nb_iters));
3045     }
3046   else if (!chrec_contains_undetermined (nb_iters))
3047     {
3048       /* Otherwise nb_iters contains parameters: scan the nb_iters
3049          expression and build its matrix representation.  */
3050       Value one;
3051
3052       row++;
3053       value_set_si (cstr->p[row][0], 1);
3054       value_set_si (cstr->p[row][loop_col], -1);
3055
3056       nb_iters = analyze_scalar_evolution (loop, nb_iters);
3057       nb_iters = instantiate_scev (block_before_scop (scop), loop, nb_iters);
3058
3059       value_init (one);
3060       value_set_si (one, 1);
3061       scan_tree_for_params (scop, nb_iters, cstr, row, one, false);
3062       value_clear (one);
3063     }
3064   else
3065     gcc_unreachable ();
3066
3067   if (loop->inner && loop_in_scop_p (loop->inner, scop))
3068     build_loop_iteration_domains (scop, loop->inner, cstr, nb_outer_loops + 1);
3069
3070   /* Only go to the next loops, if we are not at the outermost layer.  These
3071      have to be handled seperately, as we can be sure, that the chain at this
3072      layer will be connected.  */
3073   if (nb_outer_loops != 0 && loop->next && loop_in_scop_p (loop->next, scop))
3074     build_loop_iteration_domains (scop, loop->next, outer_cstr, nb_outer_loops);
3075
3076   for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
3077     if (gbb_loop (gb) == loop)
3078       GBB_DOMAIN (gb) = cloog_matrix_copy (cstr);
3079
3080   cloog_matrix_free (cstr);
3081 }
3082
3083 /* Add conditions to the domain of GB.  */
3084
3085 static void
3086 add_conditions_to_domain (graphite_bb_p gb)
3087 {
3088   unsigned int i,j;
3089   gimple stmt;
3090   VEC (gimple, heap) *conditions = GBB_CONDITIONS (gb);
3091   CloogMatrix *domain = GBB_DOMAIN (gb);
3092   scop_p scop = GBB_SCOP (gb);
3093
3094   unsigned nb_rows;
3095   unsigned nb_cols;
3096   unsigned nb_new_rows = 0;
3097   unsigned row;
3098
3099   if (VEC_empty (gimple, conditions))
3100     return;
3101
3102   if (domain)
3103     {
3104       nb_rows = domain->NbRows;
3105       nb_cols = domain->NbColumns;
3106     }
3107   else
3108     {
3109       nb_rows = 0;
3110       nb_cols = scop_nb_params (scop) + 2;
3111     }
3112
3113   /* Count number of necessary new rows to add the conditions to the
3114      domain.  */
3115   for (i = 0; VEC_iterate (gimple, conditions, i, stmt); i++)
3116     {
3117       switch (gimple_code (stmt))
3118         {
3119         case GIMPLE_COND:
3120           {
3121             enum tree_code code = gimple_cond_code (stmt);
3122
3123             switch (code)
3124               {
3125               case NE_EXPR:
3126               case EQ_EXPR:
3127                 /* NE and EQ statements are not supported right know. */
3128                 gcc_unreachable ();
3129                 break;
3130               case LT_EXPR:
3131               case GT_EXPR:
3132               case LE_EXPR:
3133               case GE_EXPR:
3134                 nb_new_rows++;
3135                 break;
3136               default:
3137                 gcc_unreachable ();
3138                 break;
3139               }
3140           break;
3141           }
3142         case SWITCH_EXPR:
3143           /* Switch statements are not supported right know.  */
3144           gcc_unreachable ();
3145           break;
3146
3147         default:
3148           gcc_unreachable ();
3149           break;
3150         }
3151     }
3152
3153
3154   /* Enlarge the matrix.  */
3155   {
3156     CloogMatrix *new_domain;
3157     new_domain = cloog_matrix_alloc (nb_rows + nb_new_rows, nb_cols);
3158
3159     for (i = 0; i < nb_rows; i++)
3160       for (j = 0; j < nb_cols; j++)
3161           value_assign (new_domain->p[i][j], domain->p[i][j]);
3162
3163     cloog_matrix_free (domain);
3164     domain = new_domain;
3165     GBB_DOMAIN (gb) = new_domain;
3166   }
3167
3168   /* Add the conditions to the new enlarged domain matrix.  */
3169   row = nb_rows;
3170   for (i = 0; VEC_iterate (gimple, conditions, i, stmt); i++)
3171     {
3172       switch (gimple_code (stmt))
3173         {
3174         case GIMPLE_COND:
3175           {
3176             Value one;
3177             enum tree_code code;
3178             tree left;
3179             tree right;
3180             loop_p loop = GBB_BB (gb)->loop_father;
3181
3182             left = gimple_cond_lhs (stmt);
3183             right = gimple_cond_rhs (stmt);
3184
3185             left = analyze_scalar_evolution (loop, left);
3186             right = analyze_scalar_evolution (loop, right);
3187
3188             left = instantiate_scev (block_before_scop (scop), loop, left);
3189             right = instantiate_scev (block_before_scop (scop), loop, right);
3190
3191             code = gimple_cond_code (stmt);
3192
3193             /* The conditions for ELSE-branches are inverted.  */
3194             if (VEC_index (gimple, gb->condition_cases, i) == NULL)
3195               code = invert_tree_comparison (code, false);
3196
3197             switch (code)
3198               {
3199               case NE_EXPR:
3200                 /* NE statements are not supported right know. */
3201                 gcc_unreachable ();
3202                 break;
3203               case EQ_EXPR:
3204                 value_set_si (domain->p[row][0], 1);
3205                 value_init (one);
3206                 value_set_si (one, 1);
3207                 scan_tree_for_params (scop, left, domain, row, one, true);
3208                 value_set_si (one, 1);
3209                 scan_tree_for_params (scop, right, domain, row, one, false);
3210                 row++;
3211                 value_set_si (domain->p[row][0], 1);
3212                 value_set_si (one, 1);
3213                 scan_tree_for_params (scop, left, domain, row, one, false);
3214                 value_set_si (one, 1);
3215                 scan_tree_for_params (scop, right, domain, row, one, true);
3216                 value_clear (one);
3217                 row++;
3218                 break;
3219               case LT_EXPR:
3220                 value_set_si (domain->p[row][0], 1);
3221                 value_init (one);
3222                 value_set_si (one, 1);
3223                 scan_tree_for_params (scop, left, domain, row, one, true);
3224                 value_set_si (one, 1);
3225                 scan_tree_for_params (scop, right, domain, row, one, false);
3226                 value_sub_int (domain->p[row][nb_cols - 1],
3227                     domain->p[row][nb_cols - 1], 1);
3228                 value_clear (one);
3229                 row++;
3230                 break;
3231               case GT_EXPR:
3232                 value_set_si (domain->p[row][0], 1);
3233                 value_init (one);
3234                 value_set_si (one, 1);
3235                 scan_tree_for_params (scop, left, domain, row, one, false);
3236                 value_set_si (one, 1);
3237                 scan_tree_for_params (scop, right, domain, row, one, true);
3238                 value_sub_int (domain->p[row][nb_cols - 1],
3239                     domain->p[row][nb_cols - 1], 1);
3240                 value_clear (one);
3241                 row++;
3242                 break;
3243               case LE_EXPR:
3244                 value_set_si (domain->p[row][0], 1);
3245                 value_init (one);
3246                 value_set_si (one, 1);
3247                 scan_tree_for_params (scop, left, domain, row, one, true);
3248                 value_set_si (one, 1);
3249                 scan_tree_for_params (scop, right, domain, row, one, false);
3250                 value_clear (one);
3251                 row++;
3252                 break;
3253               case GE_EXPR:
3254                 value_set_si (domain->p[row][0], 1);
3255                 value_init (one);
3256                 value_set_si (one, 1);
3257                 scan_tree_for_params (scop, left, domain, row, one, false);
3258                 value_set_si (one, 1);
3259                 scan_tree_for_params (scop, right, domain, row, one, true);
3260                 value_clear (one);
3261                 row++;
3262                 break;
3263               default:
3264                 gcc_unreachable ();
3265                 break;
3266               }
3267             break;
3268           }
3269         case GIMPLE_SWITCH:
3270           /* Switch statements are not supported right know.  */
3271           gcc_unreachable ();
3272           break;
3273
3274         default:
3275           gcc_unreachable ();
3276           break;
3277         }
3278     }
3279 }
3280
3281 /* Helper recursive function.  */
3282
3283 static void
3284 build_scop_conditions_1 (VEC (gimple, heap) **conditions,
3285                          VEC (gimple, heap) **cases, basic_block bb,
3286                          scop_p scop)
3287 {
3288   int i, j;
3289   graphite_bb_p gbb;
3290   gimple_stmt_iterator gsi;
3291   basic_block bb_child, bb_iter;
3292   VEC (basic_block, heap) *dom;
3293
3294   /* Make sure we are in the SCoP.  */
3295   if (!bb_in_scop_p (bb, scop))
3296     return;
3297
3298   /* Record conditions in graphite_bb.  */
3299   gbb = gbb_from_bb (bb);
3300   if (gbb)
3301     {
3302       GBB_CONDITIONS (gbb) = VEC_copy (gimple, heap, *conditions);
3303       GBB_CONDITION_CASES (gbb) = VEC_copy (gimple, heap, *cases);
3304       add_conditions_to_domain (gbb);
3305     }
3306
3307   dom = get_dominated_by (CDI_DOMINATORS, bb);
3308
3309   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
3310     {
3311       gimple stmt = gsi_stmt (gsi);
3312       VEC (edge, gc) *edges;
3313       edge e;
3314
3315       switch (gimple_code (stmt))
3316         {
3317         case GIMPLE_COND:
3318           edges = bb->succs;
3319           for (i = 0; VEC_iterate (edge, edges, i, e); i++)
3320             if ((dominated_by_p (CDI_DOMINATORS, e->dest, bb))
3321                 && VEC_length (edge, e->dest->preds) == 1)
3322               {
3323                 /* Remove the scanned block from the dominator successors.  */
3324                 for (j = 0; VEC_iterate (basic_block, dom, j, bb_iter); j++)
3325                   if (bb_iter == e->dest)
3326                     {
3327                       VEC_unordered_remove (basic_block, dom, j);
3328                       break;
3329                     }
3330
3331                 /* Recursively scan the then or else part.  */
3332                 if (e->flags & EDGE_TRUE_VALUE)
3333                   VEC_safe_push (gimple, heap, *cases, stmt);
3334                 else if (e->flags & EDGE_FALSE_VALUE)
3335                   VEC_safe_push (gimple, heap, *cases, NULL);
3336                 else
3337                   gcc_unreachable ();
3338
3339                 VEC_safe_push (gimple, heap, *conditions, stmt);
3340                 build_scop_conditions_1 (conditions, cases, e->dest, scop);
3341                 VEC_pop (gimple, *conditions);
3342                 VEC_pop (gimple, *cases);
3343               }
3344           break;
3345
3346         case GIMPLE_SWITCH:
3347           {
3348             unsigned i;
3349             gimple_stmt_iterator gsi_search_gimple_label;
3350
3351             for (i = 0; i < gimple_switch_num_labels (stmt); ++i)
3352               {
3353                 basic_block bb_iter;
3354                 size_t k;
3355                 size_t n_cases = VEC_length (gimple, *conditions);
3356                 unsigned n = gimple_switch_num_labels (stmt);
3357
3358                 bb_child = label_to_block
3359                   (CASE_LABEL (gimple_switch_label (stmt, i)));
3360
3361                 /* Do not handle multiple values for the same block.  */
3362                 for (k = 0; k < n; k++)
3363                   if (i != k
3364                       && label_to_block
3365                       (CASE_LABEL (gimple_switch_label (stmt, k))) == bb_child)
3366                     break;
3367
3368                 if (k != n)
3369                   continue;
3370
3371                 /* Switch cases with more than one predecessor are not
3372                    handled.  */
3373                 if (VEC_length (edge, bb_child->preds) != 1)
3374                   continue;
3375
3376                 /* Recursively scan the corresponding 'case' block.  */
3377
3378                 for (gsi_search_gimple_label = gsi_start_bb (bb_child);
3379                      !gsi_end_p (gsi_search_gimple_label);
3380                      gsi_next (&gsi_search_gimple_label))
3381                   {
3382                     gimple stmt_gimple_label
3383                       = gsi_stmt (gsi_search_gimple_label);
3384
3385                     if (gimple_code (stmt_gimple_label) == GIMPLE_LABEL)
3386                       {
3387                         tree t = gimple_label_label (stmt_gimple_label);
3388
3389                         if (t == gimple_switch_label (stmt, i))
3390                           VEC_replace (gimple, *cases, n_cases,
3391                                        stmt_gimple_label);
3392                         else
3393                           gcc_unreachable ();
3394                       }
3395                   }
3396
3397                 build_scop_conditions_1 (conditions, cases, bb_child, scop);
3398
3399                 /* Remove the scanned block from the dominator successors.  */
3400                 for (j = 0; VEC_iterate (basic_block, dom, j, bb_iter); j++)
3401                   if (bb_iter == bb_child)
3402                     {
3403                       VEC_unordered_remove (basic_block, dom, j);
3404                       break;
3405                     }
3406               }
3407
3408             VEC_pop (gimple, *conditions);
3409             VEC_pop (gimple, *cases);
3410             break;
3411           }
3412         default:
3413           break;
3414       }
3415   }
3416
3417   /* Scan all immediate dominated successors.  */
3418   for (i = 0; VEC_iterate (basic_block, dom, i, bb_child); i++)
3419     build_scop_conditions_1 (conditions, cases, bb_child, scop);
3420
3421   VEC_free (basic_block, heap, dom);
3422 }
3423
3424 /* Record all 'if' and 'switch' conditions in each gbb of SCOP.  */
3425
3426 static void
3427 build_scop_conditions (scop_p scop)
3428 {
3429   VEC (gimple, heap) *conditions = NULL;
3430   VEC (gimple, heap) *cases = NULL;
3431
3432   build_scop_conditions_1 (&conditions, &cases, SCOP_ENTRY (scop), scop);
3433
3434   VEC_free (gimple, heap, conditions);
3435   VEC_free (gimple, heap, cases);
3436 }
3437
3438 /* Build the current domain matrix: the loops belonging to the current
3439    SCOP, and that vary for the execution of the current basic block.
3440    Returns false if there is no loop in SCOP.  */
3441
3442 static bool
3443 build_scop_iteration_domain (scop_p scop)
3444 {
3445   struct loop *loop;
3446   CloogMatrix *outer_cstr;
3447   int i;
3448
3449   /* Build cloog loop for all loops, that are in the uppermost loop layer of
3450      this SCoP.  */
3451   for (i = 0; VEC_iterate (loop_p, SCOP_LOOP_NEST (scop), i, loop); i++)
3452     if (!loop_in_scop_p (loop_outer (loop), scop))
3453       {
3454         /* The outermost constraints is a matrix that has:
3455            -first column: eq/ineq boolean
3456            -last column: a constant
3457            -scop_nb_params columns for the parameters used in the scop.  */
3458         outer_cstr = cloog_matrix_alloc (0, scop_nb_params (scop) + 2);
3459         build_loop_iteration_domains (scop, loop, outer_cstr, 0);
3460         cloog_matrix_free (outer_cstr);
3461       }
3462
3463   return (i != 0);
3464 }
3465
3466 /* Initializes an equation CY of the access matrix using the
3467    information for a subscript from AF, relatively to the loop
3468    indexes from LOOP_NEST and parameter indexes from PARAMS.  NDIM is
3469    the dimension of the array access, i.e. the number of
3470    subscripts.  Returns true when the operation succeeds.  */
3471
3472 static bool
3473 build_access_matrix_with_af (tree af, lambda_vector cy,
3474                              scop_p scop, int ndim)
3475 {
3476   int param_col;
3477
3478   switch (TREE_CODE (af))
3479     {
3480     case POLYNOMIAL_CHREC:
3481       {
3482         struct loop *outer_loop;
3483         tree left = CHREC_LEFT (af);
3484         tree right = CHREC_RIGHT (af);
3485         int var;
3486
3487         if (TREE_CODE (right) != INTEGER_CST)
3488           return false;
3489
3490         outer_loop = get_loop (CHREC_VARIABLE (af));
3491         var = nb_loops_around_loop_in_scop (outer_loop, scop);
3492         cy[var] = int_cst_value (right);
3493
3494         switch (TREE_CODE (left))
3495           {
3496           case POLYNOMIAL_CHREC:
3497             return build_access_matrix_with_af (left, cy, scop, ndim);
3498
3499           case INTEGER_CST:
3500             cy[ndim - 1] = int_cst_value (left);
3501             return true;
3502
3503           default:
3504             return build_access_matrix_with_af (left, cy, scop, ndim);
3505           }
3506       }
3507
3508     case PLUS_EXPR:
3509       build_access_matrix_with_af (TREE_OPERAND (af, 0), cy, scop, ndim);
3510       build_access_matrix_with_af (TREE_OPERAND (af, 1), cy, scop, ndim);
3511       return true;
3512
3513     case MINUS_EXPR:
3514       build_access_matrix_with_af (TREE_OPERAND (af, 0), cy, scop, ndim);
3515       build_access_matrix_with_af (TREE_OPERAND (af, 1), cy, scop, ndim);
3516       return true;
3517
3518     case INTEGER_CST:
3519       cy[ndim - 1] = int_cst_value (af);
3520       return true;
3521
3522     case SSA_NAME:
3523       param_col = param_index (af, scop);
3524       cy [ndim - scop_nb_params (scop) + param_col - 1] = 1;
3525       return true;
3526
3527     default:
3528       /* FIXME: access_fn can have parameters.  */
3529       return false;
3530     }
3531 }
3532
3533 /* Initialize the access matrix in the data reference REF with respect
3534    to the loop nesting LOOP_NEST.  Return true when the operation
3535    succeeded.  */
3536
3537 static bool
3538 build_access_matrix (data_reference_p ref, graphite_bb_p gb)
3539 {
3540   int i, ndim = DR_NUM_DIMENSIONS (ref);
3541   struct access_matrix *am = GGC_NEW (struct access_matrix);
3542
3543   AM_MATRIX (am) = VEC_alloc (lambda_vector, heap, ndim);
3544   DR_SCOP (ref) = GBB_SCOP (gb);
3545
3546   for (i = 0; i < ndim; i++)
3547     {
3548       lambda_vector v = lambda_vector_new (ref_nb_loops (ref));
3549       scop_p scop = GBB_SCOP (gb);
3550       tree af = DR_ACCESS_FN (ref, i);
3551
3552       if (!build_access_matrix_with_af (af, v, scop, ref_nb_loops (ref)))
3553         return false;
3554
3555       VEC_safe_push (lambda_vector, heap, AM_MATRIX (am), v);
3556     }
3557
3558   DR_ACCESS_MATRIX (ref) = am;
3559   return true;
3560 }
3561
3562 /* Build the access matrices for the data references in the SCOP.  */
3563
3564 static void
3565 build_scop_data_accesses (scop_p scop)
3566 {
3567   int i;
3568   graphite_bb_p gb;
3569
3570   /* FIXME: Construction of access matrix is disabled until some
3571      pass, like the data dependence analysis, is using it.  */
3572   return;
3573
3574   for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
3575     {
3576       int j;
3577       data_reference_p dr;
3578
3579       /* Construct the access matrix for each data ref, with respect to
3580          the loop nest of the current BB in the considered SCOP.  */
3581       for (j = 0;
3582            VEC_iterate (data_reference_p, GBB_DATA_REFS (gb), j, dr);
3583            j++)
3584         {
3585           bool res = build_access_matrix (dr, gb);
3586
3587           /* FIXME: At this point the DRs should always have an affine
3588              form.  For the moment this fails as build_access_matrix
3589              does not build matrices with parameters.  */
3590           gcc_assert (res);
3591         }
3592     }
3593 }
3594
3595 /* Returns the tree variable from the name NAME that was given in
3596    Cloog representation.  All the parameters are stored in PARAMS, and
3597    all the loop induction variables are stored in IVSTACK.
3598
3599    FIXME: This is a hack, and Cloog should be fixed to not work with
3600    variable names represented as "char *string", but with void
3601    pointers that could be casted back to a tree.  The only problem in
3602    doing that is that Cloog's pretty printer still assumes that
3603    variable names are char *strings.  The solution would be to have a
3604    function pointer for pretty-printing that can be redirected to be
3605    print_generic_stmt in our case, or fprintf by default.
3606    ???  Too ugly to live.  */
3607
3608 static tree
3609 clast_name_to_gcc (const char *name, VEC (name_tree, heap) *params,
3610                    loop_iv_stack ivstack)
3611 {
3612   int i;
3613   name_tree t;
3614   tree iv;
3615
3616   if (params)
3617     for (i = 0; VEC_iterate (name_tree, params, i, t); i++)
3618       if (!strcmp (name, t->name))
3619         return t->t;
3620
3621   iv = loop_iv_stack_get_iv_from_name (ivstack, name);
3622   if (iv)
3623     return iv;
3624
3625   gcc_unreachable ();
3626 }
3627
3628 /* Returns the maximal precision type for expressions E1 and E2.  */
3629
3630 static inline tree
3631 max_precision_type (tree e1, tree e2)
3632 {
3633   tree type1 = TREE_TYPE (e1);
3634   tree type2 = TREE_TYPE (e2);
3635   return TYPE_PRECISION (type1) > TYPE_PRECISION (type2) ? type1 : type2;
3636 }
3637
3638 /* Converts a Cloog AST expression E back to a GCC expression tree
3639    of type TYPE.  */
3640
3641 static tree
3642 clast_to_gcc_expression (tree type, struct clast_expr *e,
3643                          VEC (name_tree, heap) *params,
3644                          loop_iv_stack ivstack)
3645 {
3646   switch (e->type)
3647     {
3648     case expr_term:
3649       {
3650         struct clast_term *t = (struct clast_term *) e;
3651
3652         if (t->var)
3653           {
3654             if (value_one_p (t->val))
3655               {
3656                 tree name = clast_name_to_gcc (t->var, params, ivstack);
3657                 return fold_convert (type, name);
3658               }
3659
3660             else if (value_mone_p (t->val))
3661               {
3662                 tree name = clast_name_to_gcc (t->var, params, ivstack);
3663                 name = fold_convert (type, name);
3664                 return fold_build1 (NEGATE_EXPR, type, name);
3665               }
3666             else
3667               {
3668                 tree name = clast_name_to_gcc (t->var, params, ivstack);
3669                 tree cst = gmp_cst_to_tree (type, t->val);
3670                 name = fold_convert (type, name);
3671                 return fold_build2 (MULT_EXPR, type, cst, name);
3672               }
3673           }
3674         else
3675           return gmp_cst_to_tree (type, t->val);
3676       }
3677
3678     case expr_red:
3679       {
3680         struct clast_reduction *r = (struct clast_reduction *) e;
3681
3682         switch (r->type)
3683           {
3684           case clast_red_sum:
3685             if (r->n == 1)
3686               return clast_to_gcc_expression (type, r->elts[0], params, ivstack);
3687
3688             else
3689               {
3690                 tree tl = clast_to_gcc_expression (type, r->elts[0], params, ivstack);
3691                 tree tr = clast_to_gcc_expression (type, r->elts[1], params, ivstack);
3692
3693                 gcc_assert (r->n >= 1
3694                             && r->elts[0]->type == expr_term
3695                             && r->elts[1]->type == expr_term);
3696
3697                 return fold_build2 (PLUS_EXPR, type, tl, tr);
3698               }
3699
3700             break;
3701
3702           case clast_red_min:
3703             if (r->n == 1)
3704               return clast_to_gcc_expression (type, r->elts[0], params, ivstack);
3705
3706             else if (r->n == 2)
3707               {
3708                 tree tl = clast_to_gcc_expression (type, r->elts[0], params, ivstack);
3709                 tree tr = clast_to_gcc_expression (type, r->elts[1], params, ivstack);
3710                 return fold_build2 (MIN_EXPR, type, tl, tr);
3711               }
3712
3713             else
3714               gcc_unreachable();
3715
3716             break;
3717
3718           case clast_red_max:
3719             if (r->n == 1)
3720               return clast_to_gcc_expression (type, r->elts[0], params, ivstack);
3721
3722             else if (r->n == 2)
3723               {
3724                 tree tl = clast_to_gcc_expression (type, r->elts[0], params, ivstack);
3725                 tree tr = clast_to_gcc_expression (type, r->elts[1], params, ivstack);
3726                 return fold_build2 (MAX_EXPR, type, tl, tr);
3727               }
3728
3729             else
3730               gcc_unreachable();
3731
3732             break;
3733
3734           default:
3735             gcc_unreachable ();
3736           }
3737         break;
3738       }
3739
3740     case expr_bin:
3741       {
3742         struct clast_binary *b = (struct clast_binary *) e;
3743         struct clast_expr *lhs = (struct clast_expr *) b->LHS;
3744         tree tl = clast_to_gcc_expression (type, lhs, params, ivstack);
3745         tree tr = gmp_cst_to_tree (type, b->RHS);
3746
3747         switch (b->type)
3748           {
3749           case clast_bin_fdiv:
3750             return fold_build2 (FLOOR_DIV_EXPR, type, tl, tr);
3751
3752           case clast_bin_cdiv:
3753             return fold_build2 (CEIL_DIV_EXPR, type, tl, tr);
3754
3755           case clast_bin_div:
3756             return fold_build2 (EXACT_DIV_EXPR, type, tl, tr);
3757
3758           case clast_bin_mod:
3759             return fold_build2 (TRUNC_MOD_EXPR, type, tl, tr);
3760
3761           default:
3762             gcc_unreachable ();
3763           }
3764       }
3765
3766     default:
3767       gcc_unreachable ();
3768     }
3769
3770   return NULL_TREE;
3771 }
3772
3773 /* Returns the type for the expression E.  */
3774
3775 static tree
3776 gcc_type_for_clast_expr (struct clast_expr *e,
3777                          VEC (name_tree, heap) *params,
3778                          loop_iv_stack ivstack)
3779 {
3780   switch (e->type)
3781     {
3782     case expr_term:
3783       {
3784         struct clast_term *t = (struct clast_term *) e;
3785
3786         if (t->var)
3787           return TREE_TYPE (clast_name_to_gcc (t->var, params, ivstack));
3788         else
3789           return NULL_TREE;
3790       }
3791
3792     case expr_red:
3793       {
3794         struct clast_reduction *r = (struct clast_reduction *) e;
3795
3796         if (r->n == 1)
3797           return gcc_type_for_clast_expr (r->elts[0], params, ivstack);
3798         else
3799           {
3800             int i;
3801             for (i = 0; i < r->n; i++)
3802               {
3803                 tree type = gcc_type_for_clast_expr (r->elts[i], params, ivstack);
3804                 if (type)
3805                   return type;
3806               }
3807             return NULL_TREE;
3808           }
3809       }
3810
3811     case expr_bin:
3812       {
3813         struct clast_binary *b = (struct clast_binary *) e;
3814         struct clast_expr *lhs = (struct clast_expr *) b->LHS;
3815         return gcc_type_for_clast_expr (lhs, params, ivstack);
3816       }
3817
3818     default:
3819       gcc_unreachable ();
3820     }
3821
3822   return NULL_TREE;
3823 }
3824
3825 /* Returns the type for the equation CLEQ.  */
3826
3827 static tree
3828 gcc_type_for_clast_eq (struct clast_equation *cleq,
3829                        VEC (name_tree, heap) *params,
3830                        loop_iv_stack ivstack)
3831 {
3832   tree type = gcc_type_for_clast_expr (cleq->LHS, params, ivstack);
3833   if (type)
3834     return type;
3835
3836   return gcc_type_for_clast_expr (cleq->RHS, params, ivstack);
3837 }
3838
3839 /* Translates a clast equation CLEQ to a tree.  */
3840
3841 static tree
3842 graphite_translate_clast_equation (scop_p scop,
3843                                    struct clast_equation *cleq,
3844                                    loop_iv_stack ivstack)
3845 {
3846   enum tree_code comp;
3847   tree type = gcc_type_for_clast_eq (cleq, SCOP_PARAMS (scop), ivstack);
3848   tree lhs = clast_to_gcc_expression (type, cleq->LHS, SCOP_PARAMS (scop), ivstack);
3849   tree rhs = clast_to_gcc_expression (type, cleq->RHS, SCOP_PARAMS (scop), ivstack);
3850
3851   if (cleq->sign == 0)
3852     comp = EQ_EXPR;
3853
3854   else if (cleq->sign > 0)
3855     comp = GE_EXPR;
3856
3857   else
3858     comp = LE_EXPR;
3859
3860   return fold_build2 (comp, type, lhs, rhs);
3861 }
3862
3863 /* Creates the test for the condition in STMT.  */
3864
3865 static tree
3866 graphite_create_guard_cond_expr (scop_p scop, struct clast_guard *stmt,
3867                                  loop_iv_stack ivstack)
3868 {
3869   tree cond = NULL;
3870   int i;
3871
3872   for (i = 0; i < stmt->n; i++)
3873     {
3874       tree eq = graphite_translate_clast_equation (scop, &stmt->eq[i], ivstack);
3875
3876       if (cond)
3877         cond = fold_build2 (TRUTH_AND_EXPR, TREE_TYPE (eq), cond, eq);
3878       else
3879         cond = eq;
3880     }
3881
3882   return cond;
3883 }
3884
3885 /* Creates a new if region corresponding to Cloog's guard.  */
3886
3887 static edge
3888 graphite_create_new_guard (scop_p scop, edge entry_edge,
3889                            struct clast_guard *stmt,
3890                            loop_iv_stack ivstack)
3891 {
3892   tree cond_expr = graphite_create_guard_cond_expr (scop, stmt, ivstack);
3893   edge exit_edge = create_empty_if_region_on_edge (entry_edge, cond_expr);
3894   return exit_edge;
3895 }
3896
3897 /* Walks a CLAST and returns the first statement in the body of a
3898    loop.  */
3899
3900 static struct clast_user_stmt *
3901 clast_get_body_of_loop (struct clast_stmt *stmt)
3902 {
3903   if (!stmt
3904       || CLAST_STMT_IS_A (stmt, stmt_user))
3905     return (struct clast_user_stmt *) stmt;
3906
3907   if (CLAST_STMT_IS_A (stmt, stmt_for))
3908     return clast_get_body_of_loop (((struct clast_for *) stmt)->body);
3909
3910   if (CLAST_STMT_IS_A (stmt, stmt_guard))
3911     return clast_get_body_of_loop (((struct clast_guard *) stmt)->then);
3912
3913   if (CLAST_STMT_IS_A (stmt, stmt_block))
3914     return clast_get_body_of_loop (((struct clast_block *) stmt)->body);
3915
3916   gcc_unreachable ();
3917 }
3918
3919 /* Returns the induction variable for the loop that gets translated to
3920    STMT.  */
3921
3922 static tree
3923 gcc_type_for_iv_of_clast_loop (struct clast_for *stmt_for)
3924 {
3925   struct clast_user_stmt *stmt = clast_get_body_of_loop ((struct clast_stmt *) stmt_for);
3926   const char *cloog_iv = stmt_for->iterator;
3927   CloogStatement *cs = stmt->statement;
3928   graphite_bb_p gbb = (graphite_bb_p) cloog_statement_usr (cs);
3929
3930   return gcc_type_for_cloog_iv (cloog_iv, gbb);
3931 }
3932
3933 /* Creates a new LOOP corresponding to Cloog's STMT.  Inserts an induction
3934    variable for the new LOOP.  New LOOP is attached to CFG starting at
3935    ENTRY_EDGE.  LOOP is inserted into the loop tree and becomes the child
3936    loop of the OUTER_LOOP.  */
3937
3938 static struct loop *
3939 graphite_create_new_loop (scop_p scop, edge entry_edge,
3940                           struct clast_for *stmt, loop_iv_stack ivstack,
3941                           loop_p outer)
3942 {
3943   tree type = gcc_type_for_iv_of_clast_loop (stmt);
3944   VEC (name_tree, heap) *params = SCOP_PARAMS (scop);
3945   tree lb = clast_to_gcc_expression (type, stmt->LB, params, ivstack);
3946   tree ub = clast_to_gcc_expression (type, stmt->UB, params, ivstack);
3947   tree stride = gmp_cst_to_tree (type, stmt->stride);
3948   tree ivvar = create_tmp_var (type, "graphiteIV");
3949   tree iv_before;
3950   loop_p loop = create_empty_loop_on_edge
3951     (entry_edge, lb, stride, ub, ivvar, &iv_before,
3952      outer ? outer : entry_edge->src->loop_father);
3953
3954   add_referenced_var (ivvar);
3955   loop_iv_stack_push_iv (ivstack, iv_before, stmt->iterator);
3956   return loop;
3957 }
3958
3959 /* Rename the SSA_NAMEs used in STMT and that appear in IVSTACK.  */
3960
3961 static void
3962 rename_variables_in_stmt (gimple stmt, htab_t map)
3963 {
3964   ssa_op_iter iter;
3965   use_operand_p use_p;
3966
3967   FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
3968     {
3969       tree use = USE_FROM_PTR (use_p);
3970       tree new_name = get_new_name_from_old_name (map, use);
3971
3972       replace_exp (use_p, new_name);
3973     }
3974
3975   update_stmt (stmt);
3976 }
3977
3978 /* Returns true if SSA_NAME is a parameter of SCOP.  */
3979
3980 static bool
3981 is_parameter (scop_p scop, tree ssa_name)
3982 {
3983   int i;
3984   VEC (name_tree, heap) *params = SCOP_PARAMS (scop);
3985   name_tree param;
3986
3987   for (i = 0; VEC_iterate (name_tree, params, i, param); i++)
3988     if (param->t == ssa_name)
3989       return true;
3990
3991   return false;
3992 }
3993
3994 /* Returns true if NAME is an induction variable.  */
3995
3996 static bool
3997 is_iv (tree name)
3998 {
3999   return gimple_code (SSA_NAME_DEF_STMT (name)) == GIMPLE_PHI;
4000 }
4001
4002 static void expand_scalar_variables_stmt (gimple, basic_block, scop_p,
4003                                           loop_p, htab_t);
4004
4005 /* Constructs a tree which only contains old_ivs and parameters.  Any
4006    other variables that are defined outside BB will be eliminated by
4007    using their definitions in the constructed tree.  OLD_LOOP_FATHER
4008    is the original loop that contained BB.  */
4009
4010 static tree
4011 expand_scalar_variables_expr (tree type, tree op0, enum tree_code code,
4012                               tree op1, basic_block bb, scop_p scop,
4013                               loop_p old_loop_father, htab_t map)
4014 {
4015   if ((TREE_CODE_CLASS (code) == tcc_constant
4016        && code == INTEGER_CST)
4017       || TREE_CODE_CLASS (code) == tcc_reference)
4018     return op0;
4019
4020   if (TREE_CODE_CLASS (code) == tcc_unary)
4021     {
4022       tree op0_type = TREE_TYPE (op0);
4023       enum tree_code op0_code = TREE_CODE (op0);
4024       tree op0_expr =
4025         expand_scalar_variables_expr (op0_type, op0, op0_code,
4026                                       NULL, bb, scop, old_loop_father, map);
4027
4028       return fold_build1 (code, type, op0_expr);
4029     }
4030
4031   if (TREE_CODE_CLASS (code) == tcc_binary)
4032     {
4033       tree op0_type = TREE_TYPE (op0);
4034       enum tree_code op0_code = TREE_CODE (op0);
4035       tree op0_expr =
4036         expand_scalar_variables_expr (op0_type, op0, op0_code,
4037                                       NULL, bb, scop, old_loop_father, map);
4038       tree op1_type = TREE_TYPE (op1);
4039       enum tree_code op1_code = TREE_CODE (op1);
4040       tree op1_expr =
4041         expand_scalar_variables_expr (op1_type, op1, op1_code,
4042                                       NULL, bb, scop, old_loop_father, map);
4043
4044       return fold_build2 (code, type, op0_expr, op1_expr);
4045     }
4046
4047   if (code == SSA_NAME)
4048     {
4049       tree var0, var1;
4050       gimple def_stmt;
4051       enum tree_code subcode;
4052
4053       if (is_parameter (scop, op0)
4054           || is_iv (op0))
4055         return get_new_name_from_old_name (map, op0);
4056
4057       def_stmt = SSA_NAME_DEF_STMT (op0);
4058
4059       if (gimple_bb (def_stmt) == bb)
4060         {
4061           /* If the defining statement is in the basic block already
4062              we do not need to create a new expression for it, we
4063              only need to ensure its operands are expanded.  */
4064           expand_scalar_variables_stmt (def_stmt, bb, scop,
4065                                         old_loop_father, map);
4066           return get_new_name_from_old_name (map, op0);
4067
4068         }
4069       else
4070         {
4071           if (gimple_code (def_stmt) != GIMPLE_ASSIGN
4072               || !bb_in_scop_p (gimple_bb (def_stmt), scop))
4073             return get_new_name_from_old_name (map, op0);
4074
4075           var0 = gimple_assign_rhs1 (def_stmt);
4076           subcode = gimple_assign_rhs_code (def_stmt);
4077           var1 = gimple_assign_rhs2 (def_stmt);
4078
4079           return expand_scalar_variables_expr (type, var0, subcode, var1,
4080                                                bb, scop, old_loop_father, map);
4081         }
4082     }
4083
4084   gcc_unreachable ();
4085   return NULL;
4086 }
4087
4088 /* Replicates any uses of non-parameters and non-old-ivs variablesthat
4089    are defind outside BB with code that is inserted in BB.
4090    OLD_LOOP_FATHER is the original loop that contained STMT.  */
4091
4092 static void
4093 expand_scalar_variables_stmt (gimple stmt, basic_block bb, scop_p scop,
4094                               loop_p old_loop_father, htab_t map)
4095 {
4096   ssa_op_iter iter;
4097   use_operand_p use_p;
4098
4099   FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
4100     {
4101       tree use = USE_FROM_PTR (use_p);
4102       tree type = TREE_TYPE (use);
4103       enum tree_code code  = TREE_CODE (use);
4104       tree use_expr = expand_scalar_variables_expr (type, use, code, NULL, bb,
4105                                                     scop, old_loop_father, map);
4106       if (use_expr != use)
4107         {
4108           gimple_stmt_iterator gsi = gsi_after_labels (bb);
4109           tree new_use =
4110             force_gimple_operand_gsi (&gsi, use_expr, true, NULL,
4111                                       true, GSI_NEW_STMT);
4112           replace_exp (use_p, new_use);
4113         }
4114     }
4115
4116   update_stmt (stmt);
4117 }
4118
4119 /* Copies the definitions outside of BB of variables that are not
4120    induction variables nor parameters.  BB must only contain
4121    "external" references to these types of variables.  OLD_LOOP_FATHER
4122    is the original loop that contained BB.  */
4123
4124 static void
4125 expand_scalar_variables (basic_block bb, scop_p scop,
4126                          loop_p old_loop_father, htab_t map)
4127 {
4128   gimple_stmt_iterator gsi;
4129
4130   for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi);)
4131     {
4132       gimple stmt = gsi_stmt (gsi);
4133       expand_scalar_variables_stmt (stmt, bb, scop, old_loop_father, map);
4134       gsi_next (&gsi);
4135     }
4136 }
4137
4138 /* Rename all the SSA_NAMEs from block BB according to the MAP.  */
4139
4140 static void
4141 rename_variables (basic_block bb, htab_t map)
4142 {
4143   gimple_stmt_iterator gsi;
4144
4145   for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi); gsi_next (&gsi))
4146     rename_variables_in_stmt (gsi_stmt (gsi), map);
4147 }
4148
4149 /* Remove condition from BB.  */
4150
4151 static void
4152 remove_condition (basic_block bb)
4153 {
4154   gimple last = last_stmt (bb);
4155
4156   if (last && gimple_code (last) == GIMPLE_COND)
4157     {
4158       gimple_stmt_iterator gsi = gsi_last_bb (bb);
4159       gsi_remove (&gsi, true);
4160     }
4161 }
4162
4163 /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag set.  */
4164
4165 static edge
4166 get_true_edge_from_guard_bb (basic_block bb)
4167 {
4168   edge e;
4169   edge_iterator ei;
4170
4171   FOR_EACH_EDGE (e, ei, bb->succs)
4172     if (e->flags & EDGE_TRUE_VALUE)
4173       return e;
4174
4175   gcc_unreachable ();
4176   return NULL;
4177 }
4178
4179 /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag cleared.  */
4180
4181 static edge
4182 get_false_edge_from_guard_bb (basic_block bb)
4183 {
4184   edge e;
4185   edge_iterator ei;
4186
4187   FOR_EACH_EDGE (e, ei, bb->succs)
4188     if (!(e->flags & EDGE_TRUE_VALUE))
4189       return e;
4190
4191   gcc_unreachable ();
4192   return NULL;
4193 }
4194
4195 /* Inserts in MAP a tuple (OLD_NAME, NEW_NAME) for the induction
4196    variables of the loops around GBB in SCOP, i.e. GBB_LOOPS.
4197    NEW_NAME is obtained from IVSTACK.  IVSTACK has the same stack
4198    ordering as GBB_LOOPS.  */
4199
4200 static void
4201 build_iv_mapping (loop_iv_stack ivstack, htab_t map, gbb_p gbb, scop_p scop)
4202 {
4203   int i;
4204   name_tree iv;
4205   PTR *slot;
4206
4207   for (i = 0; VEC_iterate (name_tree, SCOP_OLDIVS (scop), i, iv); i++)
4208     {
4209       struct rename_map_elt tmp;
4210
4211       if (!flow_bb_inside_loop_p (iv->loop, GBB_BB (gbb)))
4212         continue;
4213
4214       tmp.old_name = iv->t;
4215       slot = htab_find_slot (map, &tmp, INSERT);
4216
4217       if (!*slot)
4218         {
4219           tree new_name = loop_iv_stack_get_iv (ivstack,
4220                                                 gbb_loop_index (gbb, iv->loop));
4221           *slot = new_rename_map_elt (iv->t, new_name);
4222         }
4223     }
4224 }
4225
4226 /* Register in MAP the tuple (old_name, new_name).  */
4227
4228 static void
4229 register_old_and_new_names (htab_t map, tree old_name, tree new_name)
4230 {
4231   struct rename_map_elt tmp;
4232   PTR *slot;
4233
4234   tmp.old_name = old_name;
4235   slot = htab_find_slot (map, &tmp, INSERT);
4236
4237   if (!*slot)
4238     *slot = new_rename_map_elt (old_name, new_name);
4239 }
4240
4241 /* Create a duplicate of the basic block BB.  NOTE: This does not
4242    preserve SSA form.  */
4243
4244 static void
4245 graphite_copy_stmts_from_block (basic_block bb, basic_block new_bb, htab_t map)
4246 {
4247   gimple_stmt_iterator gsi, gsi_tgt;
4248
4249   gsi_tgt = gsi_start_bb (new_bb);
4250   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
4251     {
4252       def_operand_p def_p;
4253       ssa_op_iter op_iter;
4254       int region;
4255       gimple stmt = gsi_stmt (gsi);
4256       gimple copy;
4257
4258       if (gimple_code (stmt) == GIMPLE_LABEL)
4259         continue;
4260
4261       /* Create a new copy of STMT and duplicate STMT's virtual
4262          operands.  */
4263       copy = gimple_copy (stmt);
4264       gsi_insert_after (&gsi_tgt, copy, GSI_NEW_STMT);
4265       mark_symbols_for_renaming (copy);
4266
4267       region = lookup_stmt_eh_region (stmt);
4268       if (region >= 0)
4269         add_stmt_to_eh_region (copy, region);
4270       gimple_duplicate_stmt_histograms (cfun, copy, cfun, stmt);
4271
4272       /* Create new names for all the definitions created by COPY and
4273          add replacement mappings for each new name.  */
4274       FOR_EACH_SSA_DEF_OPERAND (def_p, copy, op_iter, SSA_OP_DEF)
4275         {
4276           tree old_name = DEF_FROM_PTR (def_p);
4277           tree new_name = create_new_def_for (old_name, copy, def_p);
4278           register_old_and_new_names (map, old_name, new_name);
4279         }
4280     }
4281 }
4282
4283 /* Records in SCOP_LIVEOUT_RENAMES the names that are live out of
4284    the SCOP and that appear in the RENAME_MAP.  */
4285
4286 static void
4287 register_scop_liveout_renames (scop_p scop, htab_t rename_map)
4288 {
4289   int i;
4290   sese region = SCOP_REGION (scop);
4291
4292   for (i = 0; i < SESE_NUM_VER (region); i++)
4293     if (bitmap_bit_p (SESE_LIVEOUT (region), i)
4294         && is_gimple_reg (ssa_name (i)))
4295       {
4296         tree old_name = ssa_name (i);
4297         tree new_name = get_new_name_from_old_name (rename_map, old_name);
4298
4299         register_old_and_new_names (SCOP_LIVEOUT_RENAMES (scop),
4300                                     old_name, new_name);
4301       }
4302 }
4303
4304 /* Copies BB and includes in the copied BB all the statements that can
4305    be reached following the use-def chains from the memory accesses,
4306    and returns the next edge following this new block.  */
4307
4308 static edge
4309 copy_bb_and_scalar_dependences (basic_block bb, scop_p scop,
4310                                 loop_p context_loop,
4311                                 edge next_e, htab_t map)
4312 {
4313   basic_block new_bb = split_edge (next_e);
4314
4315   next_e = single_succ_edge (new_bb);
4316   graphite_copy_stmts_from_block (bb, new_bb, map);
4317   remove_condition (new_bb);
4318   rename_variables (new_bb, map);
4319   remove_phi_nodes (new_bb);
4320   expand_scalar_variables (new_bb, scop, context_loop, map);
4321   register_scop_liveout_renames (scop, map);
4322
4323   return next_e;
4324 }
4325
4326 /* Helper function for htab_traverse in insert_loop_close_phis.  */
4327
4328 static int
4329 add_loop_exit_phis (void **slot, void *s)
4330 {
4331   struct rename_map_elt *entry = (struct rename_map_elt *) *slot;
4332   tree new_name = entry->new_name;
4333   basic_block bb = (basic_block) s;
4334   gimple phi = create_phi_node (new_name, bb);
4335   tree res = create_new_def_for (gimple_phi_result (phi), phi,
4336                                  gimple_phi_result_ptr (phi));
4337
4338   add_phi_arg (phi, new_name, single_pred_edge (bb));
4339
4340   entry->new_name = res;
4341   *slot = entry;
4342   return 1;
4343 }
4344
4345 /* Iterate over the SCOP_LIVEOUT_RENAMES (SCOP) and get tuples of the
4346    form (OLD_NAME, NEW_NAME).  Insert in BB "RES = phi (NEW_NAME)",
4347    and finally register in SCOP_LIVEOUT_RENAMES (scop) the tuple
4348    (OLD_NAME, RES).  */
4349
4350 static void
4351 insert_loop_close_phis (scop_p scop, basic_block bb)
4352 {
4353   update_ssa (TODO_update_ssa);
4354   htab_traverse (SCOP_LIVEOUT_RENAMES (scop), add_loop_exit_phis, bb);
4355   update_ssa (TODO_update_ssa);
4356 }
4357
4358 /* Helper structure for htab_traverse in insert_guard_phis.  */
4359
4360 struct igp {
4361   basic_block bb;
4362   edge true_edge, false_edge;
4363   htab_t liveout_before_guard;
4364 };
4365
4366 /* Return the default name that is before the guard.  */
4367
4368 static tree
4369 default_liveout_before_guard (htab_t liveout_before_guard, tree old_name)
4370 {
4371   tree res = get_new_name_from_old_name (liveout_before_guard, old_name);
4372
4373   if (res == old_name)
4374     {
4375       if (is_gimple_reg (res))
4376         return fold_convert (TREE_TYPE (res), integer_zero_node);
4377       return gimple_default_def (cfun, res);
4378     }
4379
4380   return res;
4381 }
4382
4383 /* Helper function for htab_traverse in insert_guard_phis.  */
4384
4385 static int
4386 add_guard_exit_phis (void **slot, void *s)
4387 {
4388   struct rename_map_elt *entry = (struct rename_map_elt *) *slot;
4389   struct igp *i = (struct igp *) s;
4390   basic_block bb = i->bb;
4391   edge true_edge = i->true_edge;
4392   edge false_edge = i->false_edge;
4393   tree name1 = entry->new_name;
4394   tree name2 = default_liveout_before_guard (i->liveout_before_guard,
4395                                              entry->old_name);
4396   gimple phi = create_phi_node (name1, bb);
4397   tree res = create_new_def_for (gimple_phi_result (phi), phi,
4398                                  gimple_phi_result_ptr (phi));
4399
4400   add_phi_arg (phi, name1, true_edge);
4401   add_phi_arg (phi, name2, false_edge);
4402
4403   entry->new_name = res;
4404   *slot = entry;
4405   return 1;
4406 }
4407
4408 /* Iterate over the SCOP_LIVEOUT_RENAMES (SCOP) and get tuples of the
4409    form (OLD_NAME, NAME1).  If there is a correspondent tuple of
4410    OLD_NAME in LIVEOUT_BEFORE_GUARD, i.e. (OLD_NAME, NAME2) then
4411    insert in BB
4412
4413    | RES = phi (NAME1 (on TRUE_EDGE), NAME2 (on FALSE_EDGE))"
4414
4415    if there is no tuple for OLD_NAME in LIVEOUT_BEFORE_GUARD, insert
4416
4417    | RES = phi (NAME1 (on TRUE_EDGE),
4418    |            DEFAULT_DEFINITION of NAME1 (on FALSE_EDGE))".
4419
4420    Finally register in SCOP_LIVEOUT_RENAMES (scop) the tuple
4421    (OLD_NAME, RES).  */
4422
4423 static void
4424 insert_guard_phis (scop_p scop, basic_block bb, edge true_edge,
4425                    edge false_edge, htab_t liveout_before_guard)
4426 {
4427   struct igp i;
4428   i.bb = bb;
4429   i.true_edge = true_edge;
4430   i.false_edge = false_edge;
4431   i.liveout_before_guard = liveout_before_guard;
4432
4433   update_ssa (TODO_update_ssa);
4434   htab_traverse (SCOP_LIVEOUT_RENAMES (scop), add_guard_exit_phis, &i);
4435   update_ssa (TODO_update_ssa);
4436 }
4437
4438 /* Helper function for htab_traverse.  */
4439
4440 static int
4441 copy_renames (void **slot, void *s)
4442 {
4443   struct rename_map_elt *entry = (struct rename_map_elt *) *slot;
4444   htab_t res = (htab_t) s;
4445   tree old_name = entry->old_name;
4446   tree new_name = entry->new_name;
4447   struct rename_map_elt tmp;
4448   PTR *x;
4449
4450   tmp.old_name = old_name;
4451   x = htab_find_slot (res, &tmp, INSERT);
4452
4453   if (!*x)
4454     *x = new_rename_map_elt (old_name, new_name);
4455
4456   return 1;
4457 }
4458
4459 /* Translates a CLAST statement STMT to GCC representation in the
4460    context of a SCOP.
4461
4462    - NEXT_E is the edge where new generated code should be attached.
4463    - CONTEXT_LOOP is the loop in which the generated code will be placed
4464      (might be NULL).
4465    - IVSTACK contains the surrounding loops around the statement to be
4466      translated.
4467 */
4468
4469 static edge
4470 translate_clast (scop_p scop, struct loop *context_loop,
4471                  struct clast_stmt *stmt, edge next_e, loop_iv_stack ivstack)
4472 {
4473   if (!stmt)
4474     return next_e;
4475
4476   if (CLAST_STMT_IS_A (stmt, stmt_root))
4477     return translate_clast (scop, context_loop, stmt->next, next_e, ivstack);
4478
4479   if (CLAST_STMT_IS_A (stmt, stmt_user))
4480     {
4481       htab_t map;
4482       CloogStatement *cs = ((struct clast_user_stmt *) stmt)->statement;
4483       graphite_bb_p gbb = (graphite_bb_p) cloog_statement_usr (cs);
4484
4485       if (GBB_BB (gbb) == ENTRY_BLOCK_PTR)
4486         return next_e;
4487
4488       map = htab_create (10, rename_map_elt_info, eq_rename_map_elts, free);
4489       loop_iv_stack_patch_for_consts (ivstack, (struct clast_user_stmt *) stmt);
4490       build_iv_mapping (ivstack, map, gbb, scop);
4491       next_e = copy_bb_and_scalar_dependences (GBB_BB (gbb), scop,
4492                                                context_loop, next_e, map);
4493       htab_delete (map);
4494       loop_iv_stack_remove_constants (ivstack);
4495       update_ssa (TODO_update_ssa);
4496       recompute_all_dominators ();
4497       graphite_verify ();
4498       return translate_clast (scop, context_loop, stmt->next, next_e, ivstack);
4499     }
4500
4501   if (CLAST_STMT_IS_A (stmt, stmt_for))
4502     {
4503       struct loop *loop
4504         = graphite_create_new_loop (scop, next_e, (struct clast_for *) stmt,
4505                                     ivstack, context_loop ? context_loop
4506                                     : get_loop (0));
4507       edge last_e = single_exit (loop);
4508
4509       next_e = translate_clast (scop, loop, ((struct clast_for *) stmt)->body,
4510                                 single_pred_edge (loop->latch), ivstack);
4511       redirect_edge_succ_nodup (next_e, loop->latch);
4512
4513       set_immediate_dominator (CDI_DOMINATORS, next_e->dest, next_e->src);
4514       loop_iv_stack_pop (ivstack);
4515       last_e = single_succ_edge (split_edge (last_e));
4516       insert_loop_close_phis (scop, last_e->src);
4517
4518       recompute_all_dominators ();
4519       graphite_verify ();
4520       return translate_clast (scop, context_loop, stmt->next, last_e, ivstack);
4521     }
4522
4523   if (CLAST_STMT_IS_A (stmt, stmt_guard))
4524     {
4525       htab_t liveout_before_guard = htab_create (10, rename_map_elt_info,
4526                                                  eq_rename_map_elts, free);
4527       edge last_e = graphite_create_new_guard (scop, next_e,
4528                                                ((struct clast_guard *) stmt),
4529                                                ivstack);
4530       edge true_e = get_true_edge_from_guard_bb (next_e->dest);
4531       edge false_e = get_false_edge_from_guard_bb (next_e->dest);
4532       edge exit_true_e = single_succ_edge (true_e->dest);
4533       edge exit_false_e = single_succ_edge (false_e->dest);
4534
4535       htab_traverse (SCOP_LIVEOUT_RENAMES (scop), copy_renames,
4536                      liveout_before_guard);
4537
4538       next_e = translate_clast (scop, context_loop,
4539                                 ((struct clast_guard *) stmt)->then,
4540                                 true_e, ivstack);
4541       insert_guard_phis (scop, last_e->src, exit_true_e, exit_false_e,
4542                          liveout_before_guard);
4543       htab_delete (liveout_before_guard);
4544       recompute_all_dominators ();
4545       graphite_verify ();
4546
4547       return translate_clast (scop, context_loop, stmt->next, last_e, ivstack);
4548     }
4549
4550   if (CLAST_STMT_IS_A (stmt, stmt_block))
4551     {
4552       next_e = translate_clast (scop, context_loop,
4553                                 ((struct clast_block *) stmt)->body,
4554                                 next_e, ivstack);
4555       recompute_all_dominators ();
4556       graphite_verify ();
4557       return translate_clast (scop, context_loop, stmt->next, next_e, ivstack);
4558     }
4559
4560   gcc_unreachable ();
4561 }
4562
4563 /* Free the SCATTERING domain list.  */
4564
4565 static void
4566 free_scattering (CloogDomainList *scattering)
4567 {
4568   while (scattering)
4569     {
4570       CloogDomain *dom = cloog_domain (scattering);
4571       CloogDomainList *next = cloog_next_domain (scattering);
4572
4573       cloog_domain_free (dom);
4574       free (scattering);
4575       scattering = next;
4576     }
4577 }
4578
4579 /* Build cloog program for SCoP.  */
4580
4581 static void
4582 build_cloog_prog (scop_p scop)
4583 {
4584   int i;
4585   int max_nb_loops = scop_max_loop_depth (scop);
4586   graphite_bb_p gbb;
4587   CloogLoop *loop_list = NULL;
4588   CloogBlockList *block_list = NULL;
4589   CloogDomainList *scattering = NULL;
4590   CloogProgram *prog = SCOP_PROG (scop);
4591   int nbs = 2 * max_nb_loops + 1;
4592   int *scaldims = (int *) xmalloc (nbs * (sizeof (int)));
4593
4594   cloog_program_set_nb_scattdims (prog, nbs);
4595   initialize_cloog_names (scop);
4596
4597   for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gbb); i++)
4598     {
4599       /* Build new block.  */
4600       CloogMatrix *domain = GBB_DOMAIN (gbb);
4601       CloogStatement *stmt = cloog_statement_alloc (GBB_BB (gbb)->index);
4602       CloogBlock *block = cloog_block_alloc (stmt, 0, NULL,
4603                                              nb_loops_around_gb (gbb));
4604       cloog_statement_set_usr (stmt, gbb);
4605
4606       /* Add empty domain to all bbs, which do not yet have a domain, as they
4607          are not part of any loop.  */
4608       if (domain == NULL)
4609         {
4610           domain = cloog_matrix_alloc (0, scop_nb_params (scop) + 2);
4611           GBB_DOMAIN (gbb) = domain;
4612         }
4613
4614       /* Build loop list.  */
4615       {
4616         CloogLoop *new_loop_list = cloog_loop_malloc ();
4617         cloog_loop_set_next (new_loop_list, loop_list);
4618         cloog_loop_set_domain (new_loop_list,
4619                                cloog_domain_matrix2domain (domain));
4620         cloog_loop_set_block (new_loop_list, block);
4621         loop_list = new_loop_list;
4622       }
4623
4624       /* Build block list.  */
4625       {
4626         CloogBlockList *new_block_list = cloog_block_list_malloc ();
4627
4628         cloog_block_list_set_next (new_block_list, block_list);
4629         cloog_block_list_set_block (new_block_list, block);
4630         block_list = new_block_list;
4631       }
4632
4633       /* Build scattering list.  */
4634       {
4635         /* XXX: Replace with cloog_domain_list_alloc(), when available.  */
4636         CloogDomainList *new_scattering
4637           = (CloogDomainList *) xmalloc (sizeof (CloogDomainList));
4638         CloogMatrix *scat_mat = schedule_to_scattering (gbb, nbs);
4639
4640         cloog_set_next_domain (new_scattering, scattering);
4641         cloog_set_domain (new_scattering,
4642                           cloog_domain_matrix2domain (scat_mat));
4643         scattering = new_scattering;
4644         cloog_matrix_free (scat_mat);
4645       }
4646     }
4647
4648   cloog_program_set_loop (prog, loop_list);
4649   cloog_program_set_blocklist (prog, block_list);
4650
4651   for (i = 0; i < nbs; i++)
4652     scaldims[i] = 0 ;
4653
4654   cloog_program_set_scaldims (prog, scaldims);
4655
4656   /* Extract scalar dimensions to simplify the code generation problem.  */
4657   cloog_program_extract_scalars (prog, scattering);
4658
4659   /* Apply scattering.  */
4660   cloog_program_scatter (prog, scattering);
4661   free_scattering (scattering);
4662
4663   /* Iterators corresponding to scalar dimensions have to be extracted.  */
4664   cloog_names_scalarize (cloog_program_names (prog), nbs,
4665                          cloog_program_scaldims (prog));
4666
4667   /* Free blocklist.  */
4668   {
4669     CloogBlockList *next = cloog_program_blocklist (prog);
4670
4671     while (next)
4672       {
4673         CloogBlockList *toDelete = next;
4674         next = cloog_block_list_next (next);
4675         cloog_block_list_set_next (toDelete, NULL);
4676         cloog_block_list_set_block (toDelete, NULL);
4677         cloog_block_list_free (toDelete);
4678       }
4679     cloog_program_set_blocklist (prog, NULL);
4680   }
4681 }
4682
4683 /* Return the options that will be used in GLOOG.  */
4684
4685 static CloogOptions *
4686 set_cloog_options (void)
4687 {
4688   CloogOptions *options = cloog_options_malloc ();
4689
4690   /* Change cloog output language to C.  If we do use FORTRAN instead, cloog
4691      will stop e.g. with "ERROR: unbounded loops not allowed in FORTRAN.", if
4692      we pass an incomplete program to cloog.  */
4693   options->language = LANGUAGE_C;
4694
4695   /* Enable complex equality spreading: removes dummy statements
4696      (assignments) in the generated code which repeats the
4697      substitution equations for statements.  This is useless for
4698      GLooG.  */
4699   options->esp = 1;
4700
4701   /* Enable C pretty-printing mode: normalizes the substitution
4702      equations for statements.  */
4703   options->cpp = 1;
4704
4705   /* Allow cloog to build strides with a stride width different to one.
4706      This example has stride = 4:
4707
4708      for (i = 0; i < 20; i += 4)
4709        A  */
4710   options->strides = 1;
4711
4712   /* Disable optimizations and make cloog generate source code closer to the
4713      input.  This is useful for debugging,  but later we want the optimized
4714      code.
4715
4716      XXX: We can not disable optimizations, as loop blocking is not working
4717      without them.  */
4718   if (0)
4719     {
4720       options->f = -1;
4721       options->l = INT_MAX;
4722     }
4723
4724   return options;
4725 }
4726
4727 /* Prints STMT to STDERR.  */
4728
4729 void
4730 debug_clast_stmt (struct clast_stmt *stmt)
4731 {
4732   CloogOptions *options = set_cloog_options ();
4733
4734   pprint (stderr, stmt, 0, options);
4735 }
4736
4737 /* Find the right transform for the SCOP, and return a Cloog AST
4738    representing the new form of the program.  */
4739
4740 static struct clast_stmt *
4741 find_transform (scop_p scop)
4742 {
4743   struct clast_stmt *stmt;
4744   CloogOptions *options = set_cloog_options ();
4745
4746   /* Connect new cloog prog generation to graphite.  */
4747   build_cloog_prog (scop);
4748
4749   if (dump_file && (dump_flags & TDF_DETAILS))
4750     {
4751       fprintf (dump_file, "Cloog Input [\n");
4752       cloog_program_print (dump_file, SCOP_PROG(scop));
4753       fprintf (dump_file, "]\n");
4754     }
4755
4756   SCOP_PROG (scop) = cloog_program_generate (SCOP_PROG (scop), options);
4757   stmt = cloog_clast_create (SCOP_PROG (scop), options);
4758
4759   if (dump_file && (dump_flags & TDF_DETAILS))
4760     {
4761       fprintf (dump_file, "Cloog Output[\n");
4762       pprint (dump_file, stmt, 0, options);
4763       cloog_program_dump_cloog (dump_file, SCOP_PROG (scop));
4764       fprintf (dump_file, "]\n");
4765     }
4766
4767   cloog_options_free (options);
4768   return stmt;
4769 }
4770
4771 /* Returns true when it is possible to generate code for this STMT.
4772    For the moment we cannot generate code when Cloog decides to
4773    duplicate a statement, as we do not do a copy, but a move.
4774    USED_BASIC_BLOCKS records the blocks that have already been seen.
4775    We return false if we have to generate code twice for the same
4776    block.  */
4777
4778 static bool
4779 can_generate_code_stmt (struct clast_stmt *stmt,
4780                         struct pointer_set_t *used_basic_blocks)
4781 {
4782   if (!stmt)
4783     return true;
4784
4785   if (CLAST_STMT_IS_A (stmt, stmt_root))
4786     return can_generate_code_stmt (stmt->next, used_basic_blocks);
4787
4788   if (CLAST_STMT_IS_A (stmt, stmt_user))
4789     {
4790       CloogStatement *cs = ((struct clast_user_stmt *) stmt)->statement;
4791       graphite_bb_p gbb = (graphite_bb_p) cloog_statement_usr (cs);
4792
4793       if (pointer_set_contains (used_basic_blocks, gbb))
4794         return false;
4795       pointer_set_insert (used_basic_blocks, gbb);
4796       return can_generate_code_stmt (stmt->next, used_basic_blocks);
4797     }
4798
4799   if (CLAST_STMT_IS_A (stmt, stmt_for))
4800     return can_generate_code_stmt (((struct clast_for *) stmt)->body,
4801                                    used_basic_blocks)
4802       && can_generate_code_stmt (stmt->next, used_basic_blocks);
4803
4804   if (CLAST_STMT_IS_A (stmt, stmt_guard))
4805     return can_generate_code_stmt (((struct clast_guard *) stmt)->then,
4806                                    used_basic_blocks);
4807
4808   if (CLAST_STMT_IS_A (stmt, stmt_block))
4809     return can_generate_code_stmt (((struct clast_block *) stmt)->body,
4810                                    used_basic_blocks)
4811       && can_generate_code_stmt (stmt->next, used_basic_blocks);
4812
4813   return false;
4814 }
4815
4816 /* Returns true when it is possible to generate code for this STMT.  */
4817
4818 static bool
4819 can_generate_code (struct clast_stmt *stmt)
4820 {
4821   bool result;
4822   struct pointer_set_t *used_basic_blocks = pointer_set_create ();
4823
4824   result = can_generate_code_stmt (stmt, used_basic_blocks);
4825   pointer_set_destroy (used_basic_blocks);
4826   return result;
4827 }
4828
4829 /* Remove from the CFG the REGION.  */
4830
4831 static inline void
4832 remove_sese_region (sese region)
4833 {
4834   VEC (basic_block, heap) *bbs = NULL;
4835   basic_block entry_bb = SESE_ENTRY (region)->dest;
4836   basic_block exit_bb = SESE_EXIT (region)->dest;
4837   basic_block bb;
4838   int i;
4839
4840   VEC_safe_push (basic_block, heap, bbs, entry_bb);
4841   gather_blocks_in_sese_region (entry_bb, exit_bb, &bbs);
4842
4843   for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++)
4844     delete_basic_block (bb);
4845
4846   VEC_free (basic_block, heap, bbs);
4847 }
4848
4849 typedef struct ifsese {
4850   sese region;
4851   sese true_region;
4852   sese false_region;
4853 } *ifsese;
4854
4855 static inline edge
4856 if_region_entry (ifsese if_region)
4857 {
4858   return SESE_ENTRY (if_region->region);
4859 }
4860
4861 static inline edge
4862 if_region_exit (ifsese if_region)
4863 {
4864   return SESE_EXIT (if_region->region);
4865 }
4866
4867 static inline basic_block
4868 if_region_get_condition_block (ifsese if_region)
4869 {
4870   return if_region_entry (if_region)->dest;
4871 }
4872
4873 static inline void
4874 if_region_set_false_region (ifsese if_region, sese region)
4875 {
4876   basic_block condition = if_region_get_condition_block (if_region);
4877   edge false_edge = get_false_edge_from_guard_bb (condition);
4878   edge entry_region = SESE_ENTRY (region);
4879   edge exit_region = SESE_EXIT (region);
4880   basic_block before_region = entry_region->src;
4881   basic_block last_in_region = exit_region->src;
4882   void **slot = htab_find_slot_with_hash (current_loops->exits, exit_region,
4883                                           htab_hash_pointer (exit_region),
4884                                           NO_INSERT);
4885
4886   entry_region->flags = false_edge->flags;
4887   false_edge->flags = exit_region->flags;
4888
4889   redirect_edge_pred (entry_region, condition);
4890   redirect_edge_pred (exit_region, before_region);
4891   redirect_edge_pred (false_edge, last_in_region);
4892
4893   exit_region->flags = EDGE_FALLTHRU;
4894   recompute_all_dominators ();
4895
4896   SESE_EXIT (region) = single_succ_edge (false_edge->dest);
4897   if_region->false_region = region;
4898
4899   if (slot)
4900     {
4901       struct loop_exit *loop_exit = GGC_CNEW (struct loop_exit);
4902
4903       memcpy (loop_exit, *((struct loop_exit **) slot), sizeof (struct loop_exit));
4904       htab_clear_slot (current_loops->exits, slot);
4905
4906       slot = htab_find_slot_with_hash (current_loops->exits, false_edge,
4907                                        htab_hash_pointer (false_edge),
4908                                        INSERT);
4909       loop_exit->e = false_edge;
4910       *slot = loop_exit;
4911       false_edge->src->loop_father->exits->next = loop_exit;
4912     }
4913 }
4914
4915 static ifsese
4916 create_if_region_on_edge (edge entry, tree condition)
4917 {
4918   edge e;
4919   edge_iterator ei;
4920   sese sese_region = GGC_NEW (struct sese);
4921   sese true_region = GGC_NEW (struct sese);
4922   sese false_region = GGC_NEW (struct sese);
4923   ifsese if_region = GGC_NEW (struct ifsese);
4924   edge exit = create_empty_if_region_on_edge (entry, condition);
4925
4926   if_region->region = sese_region;
4927   if_region->region->entry = entry;
4928   if_region->region->exit = exit;
4929
4930   FOR_EACH_EDGE (e, ei, entry->dest->succs)
4931     {
4932       if (e->flags & EDGE_TRUE_VALUE)
4933         {
4934           true_region->entry = e;
4935           true_region->exit = single_succ_edge (e->dest);
4936           if_region->true_region = true_region;
4937         }
4938       else if (e->flags & EDGE_FALSE_VALUE)
4939         {
4940           false_region->entry = e;
4941           false_region->exit = single_succ_edge (e->dest);
4942           if_region->false_region = false_region;
4943         }
4944     }
4945
4946   return if_region;
4947 }
4948
4949 /* Moves REGION in a condition expression:
4950    | if (1)
4951    |   ;
4952    | else
4953    |   REGION;
4954 */
4955
4956 static ifsese
4957 move_sese_in_condition (sese region)
4958 {
4959   basic_block pred_block = split_edge (SESE_ENTRY (region));
4960   ifsese if_region = NULL;
4961
4962   SESE_ENTRY (region) = single_succ_edge (pred_block);
4963   if_region = create_if_region_on_edge (single_pred_edge (pred_block), integer_one_node);
4964   if_region_set_false_region (if_region, region);
4965
4966   return if_region;
4967 }
4968
4969 /* Add exit phis for USE on EXIT.  */
4970
4971 static void
4972 scop_add_exit_phis_edge (basic_block exit, tree use, edge false_e, edge true_e)
4973 {
4974   gimple phi = create_phi_node (use, exit);
4975
4976   create_new_def_for (gimple_phi_result (phi), phi,
4977                       gimple_phi_result_ptr (phi));
4978   add_phi_arg (phi, use, false_e);
4979   add_phi_arg (phi, use, true_e);
4980 }
4981
4982 /* Add phi nodes for VAR that is used in LIVEIN.  Phi nodes are
4983    inserted in block BB.  */
4984
4985 static void
4986 scop_add_exit_phis_var (basic_block bb, tree var, bitmap livein,
4987                         edge false_e, edge true_e)
4988 {
4989   bitmap def;
4990   basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (var));
4991
4992   if (is_gimple_reg (var))
4993     bitmap_clear_bit (livein, def_bb->index);
4994   else
4995     bitmap_set_bit (livein, def_bb->index);
4996
4997   def = BITMAP_ALLOC (NULL);
4998   bitmap_set_bit (def, def_bb->index);
4999   compute_global_livein (livein, def);
5000   BITMAP_FREE (def);
5001
5002   scop_add_exit_phis_edge (bb, var, false_e, true_e);
5003 }
5004
5005 /* Insert in the block BB phi nodes for variables defined in REGION
5006    and used outside the REGION.  The code generation moves REGION in
5007    the else clause of an "if (1)" and generates code in the then
5008    clause that is at this point empty:
5009
5010    | if (1)
5011    |   empty;
5012    | else
5013    |   REGION;
5014 */
5015
5016 static void
5017 scop_insert_phis_for_liveouts (sese region, basic_block bb,
5018                                edge false_e, edge true_e)
5019 {
5020   unsigned i;
5021   bitmap_iterator bi;
5022
5023   update_ssa (TODO_update_ssa);
5024
5025   EXECUTE_IF_SET_IN_BITMAP (SESE_LIVEOUT (region), 0, i, bi)
5026     scop_add_exit_phis_var (bb, ssa_name (i), SESE_LIVEIN_VER (region, i),
5027                             false_e, true_e);
5028
5029   update_ssa (TODO_update_ssa);
5030 }
5031
5032 /* Adjusts the phi nodes in the block BB for variables defined in
5033    SCOP_REGION and used outside the SCOP_REGION.  The code generation
5034    moves SCOP_REGION in the else clause of an "if (1)" and generates
5035    code in the then clause:
5036
5037    | if (1)
5038    |   generated code from REGION;
5039    | else
5040    |   REGION;
5041
5042    To adjust the phi nodes after the condition, SCOP_LIVEOUT_RENAMES
5043    hash table is used: this stores for a name that is part of the
5044    LIVEOUT of SCOP_REGION its new name in the generated code.  */
5045
5046 static void
5047 scop_adjust_phis_for_liveouts (scop_p scop, basic_block bb, edge false_e,
5048                                edge true_e)
5049 {
5050   gimple_stmt_iterator si;
5051
5052   for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
5053     {
5054       unsigned i, false_i;
5055       gimple phi = gsi_stmt (si);
5056
5057       if (!is_gimple_reg (PHI_RESULT (phi)))
5058         continue;
5059
5060       for (i = 0; i < gimple_phi_num_args (phi); i++)
5061         if (gimple_phi_arg_edge (phi, i) == false_e)
5062           {
5063             false_i = i;
5064             break;
5065           }
5066
5067       for (i = 0; i < gimple_phi_num_args (phi); i++)
5068         if (gimple_phi_arg_edge (phi, i) == true_e)
5069           {
5070             tree old_name = gimple_phi_arg_def (phi, false_i);
5071             tree new_name = get_new_name_from_old_name
5072               (SCOP_LIVEOUT_RENAMES (scop), old_name);
5073
5074             gcc_assert (old_name != new_name);
5075             SET_PHI_ARG_DEF (phi, i, new_name);
5076           }
5077     }
5078 }
5079
5080 /* Returns the first cloog name used in EXPR.  */
5081
5082 static const char *
5083 find_cloog_iv_in_expr (struct clast_expr *expr)
5084 {
5085   struct clast_term *term = (struct clast_term *) expr;
5086
5087   if (expr->type == expr_term
5088       && !term->var)
5089     return NULL;
5090
5091   if (expr->type == expr_term)
5092     return term->var;
5093
5094   if (expr->type == expr_red)
5095     {
5096       int i;
5097       struct clast_reduction *red = (struct clast_reduction *) expr;
5098
5099       for (i = 0; i < red->n; i++)
5100         {
5101           const char *res = find_cloog_iv_in_expr ((red)->elts[i]);
5102
5103           if (res)
5104             return res;
5105         }
5106     }
5107
5108   return NULL;
5109 }
5110
5111 /* Build for a clast_user_stmt USER_STMT a map between the CLAST
5112    induction variables and the corresponding GCC old induction
5113    variables.  This information is stored on each GRAPHITE_BB.  */
5114
5115 static void
5116 compute_cloog_iv_types_1 (graphite_bb_p gbb,
5117                           struct clast_user_stmt *user_stmt)
5118 {
5119   struct clast_stmt *t;
5120   int index = 0;
5121
5122   for (t = user_stmt->substitutions; t; t = t->next, index++)
5123     {
5124       PTR *slot;
5125       struct ivtype_map_elt tmp;
5126       struct clast_expr *expr = (struct clast_expr *)
5127         ((struct clast_assignment *)t)->RHS;
5128
5129       /* Create an entry (clast_var, type).  */
5130       tmp.cloog_iv = find_cloog_iv_in_expr (expr);
5131       if (!tmp.cloog_iv)
5132         continue;
5133
5134       slot = htab_find_slot (GBB_CLOOG_IV_TYPES (gbb), &tmp, INSERT);
5135
5136       if (!*slot)
5137         {
5138           loop_p loop = gbb_loop_at_index (gbb, index);
5139           tree oldiv = oldiv_for_loop (GBB_SCOP (gbb), loop);
5140           tree type = oldiv ? TREE_TYPE (oldiv) : integer_type_node;
5141           *slot = new_ivtype_map_elt (tmp.cloog_iv, type);
5142         }
5143     }
5144 }
5145
5146 /* Walk the CLAST tree starting from STMT and build for each
5147    clast_user_stmt a map between the CLAST induction variables and the
5148    corresponding GCC old induction variables.  This information is
5149    stored on each GRAPHITE_BB.  */
5150
5151 static void
5152 compute_cloog_iv_types (struct clast_stmt *stmt)
5153 {
5154   if (!stmt)
5155     return;
5156
5157   if (CLAST_STMT_IS_A (stmt, stmt_root))
5158     goto next;
5159
5160   if (CLAST_STMT_IS_A (stmt, stmt_user))
5161     {
5162       CloogStatement *cs = ((struct clast_user_stmt *) stmt)->statement;
5163       graphite_bb_p gbb = (graphite_bb_p) cloog_statement_usr (cs);
5164       GBB_CLOOG_IV_TYPES (gbb) = htab_create (10, ivtype_map_elt_info,
5165                                               eq_ivtype_map_elts, free);
5166       compute_cloog_iv_types_1 (gbb, (struct clast_user_stmt *) stmt);
5167       goto next;
5168     }
5169
5170   if (CLAST_STMT_IS_A (stmt, stmt_for))
5171     {
5172       struct clast_stmt *s = ((struct clast_for *) stmt)->body;
5173       compute_cloog_iv_types (s);
5174       goto next;
5175     }
5176
5177   if (CLAST_STMT_IS_A (stmt, stmt_guard))
5178     {
5179       struct clast_stmt *s = ((struct clast_guard *) stmt)->then;
5180       compute_cloog_iv_types (s);
5181       goto next;
5182     }
5183
5184   if (CLAST_STMT_IS_A (stmt, stmt_block))
5185     {
5186       struct clast_stmt *s = ((struct clast_block *) stmt)->body;
5187       compute_cloog_iv_types (s);
5188       goto next;
5189     }
5190
5191   gcc_unreachable ();
5192
5193  next:
5194   compute_cloog_iv_types (stmt->next);
5195 }
5196
5197 /* GIMPLE Loop Generator: generates loops from STMT in GIMPLE form for
5198    the given SCOP.  */
5199
5200 static void
5201 gloog (scop_p scop, struct clast_stmt *stmt)
5202 {
5203   edge new_scop_exit_edge = NULL;
5204   VEC (iv_stack_entry_p, heap) *ivstack = VEC_alloc (iv_stack_entry_p, heap,
5205                                                      10);
5206   loop_p context_loop;
5207   ifsese if_region = NULL;
5208
5209   if (!can_generate_code (stmt))
5210     {
5211       cloog_clast_free (stmt);
5212       return;
5213     }
5214
5215   if_region = move_sese_in_condition (SCOP_REGION (scop));
5216   sese_build_livein_liveouts (SCOP_REGION (scop));
5217   scop_insert_phis_for_liveouts (SCOP_REGION (scop),
5218                                  if_region->region->exit->src,
5219                                  if_region->false_region->exit,
5220                                  if_region->true_region->exit);
5221   recompute_all_dominators ();
5222   graphite_verify ();
5223   context_loop = SESE_ENTRY (SCOP_REGION (scop))->src->loop_father;
5224   compute_cloog_iv_types (stmt);
5225
5226   new_scop_exit_edge = translate_clast (scop, context_loop, stmt,
5227                                         if_region->true_region->entry,
5228                                         &ivstack);
5229   free_loop_iv_stack (&ivstack);
5230   cloog_clast_free (stmt);
5231
5232   graphite_verify ();
5233   scop_adjust_phis_for_liveouts (scop,
5234                                  if_region->region->exit->src,
5235                                  if_region->false_region->exit,
5236                                  if_region->true_region->exit);
5237
5238   recompute_all_dominators ();
5239   graphite_verify ();
5240   cleanup_tree_cfg ();
5241   recompute_all_dominators ();
5242   graphite_verify ();
5243 }
5244
5245 /* Returns the number of data references in SCOP.  */
5246
5247 static int
5248 nb_data_refs_in_scop (scop_p scop)
5249 {
5250   int i;
5251   graphite_bb_p gbb;
5252   int res = 0;
5253
5254   for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gbb); i++)
5255     res += VEC_length (data_reference_p, GBB_DATA_REFS (gbb));
5256
5257   return res;
5258 }
5259
5260 /* Move the loop at index LOOP and insert it before index NEW_LOOP_POS.
5261    This transformartion is only valid, if the loop nest between i and k is
5262    perfectly nested. Therefore we do not need to change the static schedule.
5263
5264    Example:
5265
5266    for (i = 0; i < 50; i++)
5267      for (j ...)
5268        for (k = 5; k < 100; k++)
5269          A
5270
5271    To move k before i use:
5272
5273    graphite_trans_bb_move_loop (A, 2, 0)
5274
5275    for (k = 5; k < 100; k++)
5276      for (i = 0; i < 50; i++)
5277        for (j ...)
5278          A
5279
5280    And to move k back:
5281
5282    graphite_trans_bb_move_loop (A, 0, 2)
5283
5284    This function does not check the validity of interchanging loops.
5285    This should be checked before calling this function.  */
5286
5287 static void
5288 graphite_trans_bb_move_loop (graphite_bb_p gb, int loop,
5289                              int new_loop_pos)
5290 {
5291   CloogMatrix *domain = GBB_DOMAIN (gb);
5292   int row, j;
5293   loop_p tmp_loop_p;
5294
5295   gcc_assert (loop < gbb_nb_loops (gb)
5296               && new_loop_pos < gbb_nb_loops (gb));
5297
5298   /* Update LOOPS vector.  */
5299   tmp_loop_p = VEC_index (loop_p, GBB_LOOPS (gb), loop);
5300   VEC_ordered_remove (loop_p, GBB_LOOPS (gb), loop);
5301   VEC_safe_insert (loop_p, heap, GBB_LOOPS (gb), new_loop_pos, tmp_loop_p);
5302
5303   /* Move the domain columns.  */
5304   if (loop < new_loop_pos)
5305     for (row = 0; row < domain->NbRows; row++)
5306       {
5307         Value tmp;
5308         value_init (tmp);
5309         value_assign (tmp, domain->p[row][loop + 1]);
5310
5311         for (j = loop ; j < new_loop_pos - 1; j++)
5312           value_assign (domain->p[row][j + 1], domain->p[row][j + 2]);
5313
5314         value_assign (domain->p[row][new_loop_pos], tmp);
5315         value_clear (tmp);
5316       }
5317   else
5318     for (row = 0; row < domain->NbRows; row++)
5319       {
5320         Value tmp;
5321         value_init (tmp);
5322         value_assign (tmp, domain->p[row][loop + 1]);
5323
5324         for (j = loop ; j > new_loop_pos; j--)
5325           value_assign (domain->p[row][j + 1], domain->p[row][j]);
5326
5327         value_assign (domain->p[row][new_loop_pos + 1], tmp);
5328         value_clear (tmp);
5329       }
5330 }
5331
5332 /* Get the index of the column representing constants in the DOMAIN
5333    matrix.  */
5334
5335 static int
5336 const_column_index (CloogMatrix *domain)
5337 {
5338   return domain->NbColumns - 1;
5339 }
5340
5341
5342 /* Get the first index that is positive or negative, determined
5343    following the value of POSITIVE, in matrix DOMAIN in COLUMN.  */
5344
5345 static int
5346 get_first_matching_sign_row_index (CloogMatrix *domain, int column,
5347                                    bool positive)
5348 {
5349   int row;
5350
5351   for (row = 0; row < domain->NbRows; row++)
5352     {
5353       int val = value_get_si (domain->p[row][column]);
5354
5355       if (val > 0 && positive)
5356         return row;
5357
5358       else if (val < 0 && !positive)
5359         return row;
5360     }
5361
5362   gcc_unreachable ();
5363 }
5364
5365 /* Get the lower bound of COLUMN in matrix DOMAIN.  */
5366
5367 static int
5368 get_lower_bound_row (CloogMatrix *domain, int column)
5369 {
5370   return get_first_matching_sign_row_index (domain, column, true);
5371 }
5372
5373 /* Get the upper bound of COLUMN in matrix DOMAIN.  */
5374
5375 static int
5376 get_upper_bound_row (CloogMatrix *domain, int column)
5377 {
5378   return get_first_matching_sign_row_index (domain, column, false);
5379 }
5380
5381 /* Get the lower bound of LOOP.  */
5382
5383 static void
5384 get_lower_bound (CloogMatrix *domain, int loop, Value lower_bound_result)
5385 {
5386   int lower_bound_row = get_lower_bound_row (domain, loop);
5387   value_assign (lower_bound_result,
5388                 domain->p[lower_bound_row][const_column_index(domain)]);
5389 }
5390
5391 /* Get the upper bound of LOOP.  */
5392
5393 static void
5394 get_upper_bound (CloogMatrix *domain, int loop, Value upper_bound_result)
5395 {
5396   int upper_bound_row = get_upper_bound_row (domain, loop);
5397   value_assign (upper_bound_result,
5398                 domain->p[upper_bound_row][const_column_index(domain)]);
5399 }
5400
5401 /* Strip mines the loop of BB at the position LOOP_DEPTH with STRIDE.
5402    Always valid, but not always a performance improvement.  */
5403
5404 static void
5405 graphite_trans_bb_strip_mine (graphite_bb_p gb, int loop_depth, int stride)
5406 {
5407   int row, col;
5408
5409   CloogMatrix *domain = GBB_DOMAIN (gb);
5410   CloogMatrix *new_domain = cloog_matrix_alloc (domain->NbRows + 3,
5411                                                 domain->NbColumns + 1);
5412
5413   int col_loop_old = loop_depth + 2;
5414   int col_loop_strip = col_loop_old - 1;
5415
5416   Value old_lower_bound;
5417   Value old_upper_bound;
5418
5419   gcc_assert (loop_depth <= gbb_nb_loops (gb) - 1);
5420
5421   VEC_safe_insert (loop_p, heap, GBB_LOOPS (gb), loop_depth, NULL);
5422
5423   GBB_DOMAIN (gb) = new_domain;
5424
5425   /*
5426    nrows = 4, ncols = 4
5427   eq    i    j    c
5428    1    1    0    0
5429    1   -1    0   99
5430    1    0    1    0
5431    1    0   -1   99
5432   */
5433
5434   /* Move domain.  */
5435   for (row = 0; row < domain->NbRows; row++)
5436     for (col = 0; col < domain->NbColumns; col++)
5437       if (col <= loop_depth)
5438         value_assign (new_domain->p[row][col], domain->p[row][col]);
5439       else
5440         value_assign (new_domain->p[row][col + 1], domain->p[row][col]);
5441
5442
5443   /*
5444     nrows = 6, ncols = 5
5445            outer inner
5446    eq   i   jj    j    c
5447    1    1    0    0    0
5448    1   -1    0    0   99
5449    1    0    0    1    0
5450    1    0    0   -1   99
5451    0    0    0    0    0
5452    0    0    0    0    0
5453    0    0    0    0    0
5454    */
5455
5456   row = domain->NbRows;
5457
5458   /* Add outer loop.  */
5459   value_init (old_lower_bound);
5460   value_init (old_upper_bound);
5461   get_lower_bound (new_domain, col_loop_old, old_lower_bound);
5462   get_upper_bound (new_domain, col_loop_old, old_upper_bound);
5463
5464   /* Set Lower Bound */
5465   value_set_si (new_domain->p[row][0], 1);
5466   value_set_si (new_domain->p[row][col_loop_strip], 1);
5467   value_assign (new_domain->p[row][const_column_index (new_domain)],
5468                 old_lower_bound);
5469   value_clear (old_lower_bound);
5470   row++;
5471
5472
5473   /*
5474     6 5
5475    eq   i   jj    j    c
5476    1    1    0    0    0
5477    1   -1    0    0   99
5478    1    0    0    1    0  -
5479    1    0    0   -1   99   | copy old lower bound
5480    1    0    1    0    0 <-
5481    0    0    0    0    0
5482    0    0    0    0    0
5483    */
5484
5485   {
5486     Value new_upper_bound;
5487     Value strip_size_value;
5488
5489     value_init (new_upper_bound);
5490     value_init (strip_size_value);
5491     value_set_si (strip_size_value, (int) stride);
5492
5493     value_pdivision (new_upper_bound, old_upper_bound, strip_size_value);
5494     value_add_int (new_upper_bound, new_upper_bound, 1);
5495
5496     /* Set Upper Bound */
5497     value_set_si (new_domain->p[row][0], 1);
5498     value_set_si (new_domain->p[row][col_loop_strip], -1);
5499     value_assign (new_domain->p[row][const_column_index (new_domain)],
5500                   new_upper_bound);
5501
5502     value_clear (strip_size_value);
5503     value_clear (old_upper_bound);
5504     value_clear (new_upper_bound);
5505     row++;
5506   }
5507   /*
5508     6 5
5509    eq   i   jj    j    c
5510    1    1    0    0    0
5511    1   -1    0    0   99
5512    1    0    0    1    0
5513    1    0    0   -1   99
5514    1    0    1    0    0
5515    1    0   -1    0   25  (divide old upper bound with stride)
5516    0    0    0    0    0
5517   */
5518
5519   {
5520     row = get_lower_bound_row (new_domain, col_loop_old);
5521     /* Add local variable to keep linear representation.  */
5522     value_set_si (new_domain->p[row][0], 1);
5523     value_set_si (new_domain->p[row][const_column_index (new_domain)],0);
5524     value_set_si (new_domain->p[row][col_loop_old], 1);
5525     value_set_si (new_domain->p[row][col_loop_strip], -1*((int)stride));
5526   }
5527
5528   /*
5529     6 5
5530    eq   i   jj    j    c
5531    1    1    0    0    0
5532    1   -1    0    0   99
5533    1    0    -1   1    0
5534    1    0    0   -1   99
5535    1    0    1    0    0
5536    1    0   -1    0   25  (divide old upper bound with stride)
5537    0    0    0    0    0
5538   */
5539
5540   {
5541     row = new_domain->NbRows-1;
5542
5543     value_set_si (new_domain->p[row][0], 1);
5544     value_set_si (new_domain->p[row][col_loop_old], -1);
5545     value_set_si (new_domain->p[row][col_loop_strip], stride);
5546     value_set_si (new_domain->p[row][const_column_index (new_domain)],
5547                   stride-1);
5548   }
5549
5550   /*
5551     6 5
5552    eq   i   jj    j    c
5553    1    1    0    0    0     i >= 0
5554    1   -1    0    0   99    99 >= i
5555    1    0    -4   1    0     j >= 4*jj
5556    1    0    0   -1   99    99 >= j
5557    1    0    1    0    0    jj >= 0
5558    1    0   -1    0   25    25 >= jj
5559    0    0    4    -1   3  jj+3 >= j
5560   */
5561
5562   cloog_matrix_free (domain);
5563
5564   /* Update static schedule.  */
5565   {
5566     int i;
5567     int nb_loops = gbb_nb_loops (gb);
5568     lambda_vector new_schedule = lambda_vector_new (nb_loops + 1);
5569
5570     for (i = 0; i <= loop_depth; i++)
5571       new_schedule[i] = GBB_STATIC_SCHEDULE (gb)[i];
5572
5573     for (i = loop_depth + 1; i <= nb_loops - 2; i++)
5574       new_schedule[i + 2] = GBB_STATIC_SCHEDULE (gb)[i];
5575
5576     GBB_STATIC_SCHEDULE (gb) = new_schedule;
5577   }
5578 }
5579
5580 /* Returns true when the strip mining of LOOP_INDEX by STRIDE is
5581    profitable or undecidable.  GB is the statement around which the
5582    loops will be strip mined.  */
5583
5584 static bool
5585 strip_mine_profitable_p (graphite_bb_p gb, int stride,
5586                          int loop_index)
5587 {
5588   bool res = true;
5589   edge exit = NULL;
5590   tree niter;
5591   loop_p loop;
5592   long niter_val;
5593
5594   loop = VEC_index (loop_p, GBB_LOOPS (gb), loop_index);
5595   exit = single_exit (loop);
5596
5597   niter = find_loop_niter (loop, &exit);
5598   if (niter == chrec_dont_know
5599       || TREE_CODE (niter) != INTEGER_CST)
5600     return true;
5601
5602   niter_val = int_cst_value (niter);
5603
5604   if (niter_val < stride)
5605     {
5606       res = false;
5607       if (dump_file && (dump_flags & TDF_DETAILS))
5608         {
5609           fprintf (dump_file, "\nStrip Mining is not profitable for loop %d:",
5610                    loop_index);
5611           fprintf (dump_file, "number of iterations is too low.\n");
5612         }
5613     }
5614
5615   return res;
5616 }
5617
5618 /* Determines when the interchange of LOOP_A and LOOP_B belonging to
5619    SCOP is legal.  */
5620
5621 static bool
5622 is_interchange_valid (scop_p scop, int loop_a, int loop_b)
5623 {
5624   bool res;
5625   VEC (ddr_p, heap) *dependence_relations;
5626   VEC (data_reference_p, heap) *datarefs;
5627
5628   struct loop *nest = VEC_index (loop_p, SCOP_LOOP_NEST (scop), loop_a);
5629   int depth = perfect_loop_nest_depth (nest);
5630   lambda_trans_matrix trans;
5631
5632   gcc_assert (loop_a < loop_b);
5633
5634   dependence_relations = VEC_alloc (ddr_p, heap, 10 * 10);
5635   datarefs = VEC_alloc (data_reference_p, heap, 10);
5636
5637   if (!compute_data_dependences_for_loop (nest, true, &datarefs,
5638                                           &dependence_relations))
5639     return false;
5640
5641   if (dump_file && (dump_flags & TDF_DETAILS))
5642     dump_ddrs (dump_file, dependence_relations);
5643
5644   trans = lambda_trans_matrix_new (depth, depth);
5645   lambda_matrix_id (LTM_MATRIX (trans), depth);
5646
5647   lambda_matrix_row_exchange (LTM_MATRIX (trans), 0, loop_b - loop_a);
5648
5649   if (!lambda_transform_legal_p (trans, depth, dependence_relations))
5650     {
5651       lambda_matrix_row_exchange (LTM_MATRIX (trans), 0, loop_b - loop_a);
5652       res = false;
5653     }
5654   else
5655     res = true;
5656
5657   free_dependence_relations (dependence_relations);
5658   free_data_refs (datarefs);
5659   return res;
5660 }
5661
5662 /* Loop block the LOOPS innermost loops of GB with stride size STRIDE.
5663
5664    Example
5665
5666    for (i = 0; i <= 50; i++=4)
5667      for (k = 0; k <= 100; k++=4)
5668        for (l = 0; l <= 200; l++=4)
5669          A
5670
5671    To strip mine the two inner most loops with stride = 4 call:
5672
5673    graphite_trans_bb_block (A, 4, 2)
5674
5675    for (i = 0; i <= 50; i++)
5676      for (kk = 0; kk <= 100; kk+=4)
5677        for (ll = 0; ll <= 200; ll+=4)
5678          for (k = kk; k <= min (100, kk + 3); k++)
5679            for (l = ll; l <= min (200, ll + 3); l++)
5680              A
5681 */
5682
5683 static bool
5684 graphite_trans_bb_block (graphite_bb_p gb, int stride, int loops)
5685 {
5686   int i, j;
5687   int nb_loops = gbb_nb_loops (gb);
5688   int start = nb_loops - loops;
5689   scop_p scop = GBB_SCOP (gb);
5690
5691   gcc_assert (scop_contains_loop (scop, gbb_loop (gb)));
5692
5693   for (i = start ; i < nb_loops; i++)
5694     for (j = i + 1; j < nb_loops; j++)
5695       if (!is_interchange_valid (scop, i, j))
5696         {
5697           if (dump_file && (dump_flags & TDF_DETAILS))
5698             fprintf (dump_file,
5699                      "\nInterchange not valid for loops %d and %d:\n", i, j);
5700           return false;
5701         }
5702       else if (dump_file && (dump_flags & TDF_DETAILS))
5703         fprintf (dump_file,
5704                  "\nInterchange valid for loops %d and %d:\n", i, j);
5705
5706   /* Check if strip mining is profitable for every loop.  */
5707   for (i = 0; i < nb_loops - start; i++)
5708     if (!strip_mine_profitable_p (gb, stride, start + i))
5709       return false;
5710
5711   /* Strip mine loops.  */
5712   for (i = 0; i < nb_loops - start; i++)
5713     graphite_trans_bb_strip_mine (gb, start + 2 * i, stride);
5714
5715   /* Interchange loops.  */
5716   for (i = 1; i < nb_loops - start; i++)
5717     graphite_trans_bb_move_loop (gb, start + 2 * i, start + i);
5718
5719   return true;
5720 }
5721
5722 /* Loop block LOOPS innermost loops of a loop nest.  BBS represent the
5723    basic blocks that belong to the loop nest to be blocked.  */
5724
5725 static bool
5726 graphite_trans_loop_block (VEC (graphite_bb_p, heap) *bbs, int loops)
5727 {
5728   graphite_bb_p gb;
5729   int i;
5730   bool transform_done = false;
5731
5732   /* TODO: - Calculate the stride size automatically.  */
5733   int stride_size = 64;
5734
5735   for (i = 0; VEC_iterate (graphite_bb_p, bbs, i, gb); i++)
5736     transform_done |= graphite_trans_bb_block (gb, stride_size, loops);
5737
5738   return transform_done;
5739 }
5740
5741 /* Loop block all basic blocks of SCOP.  Return false when the
5742    transform is not performed.  */
5743
5744 static bool
5745 graphite_trans_scop_block (scop_p scop)
5746 {
5747   graphite_bb_p gb;
5748   int i, j;
5749   int last_nb_loops;
5750   int nb_loops;
5751   bool perfect = true;
5752   bool transform_done = false;
5753
5754   VEC (graphite_bb_p, heap) *bbs = VEC_alloc (graphite_bb_p, heap, 3);
5755   int max_schedule = scop_max_loop_depth (scop) + 1;
5756   lambda_vector last_schedule = lambda_vector_new (max_schedule);
5757
5758   if (VEC_length (graphite_bb_p, SCOP_BBS (scop)) == 0)
5759     return false;
5760
5761   /* Get the data of the first bb.  */
5762   gb = VEC_index (graphite_bb_p, SCOP_BBS (scop), 0);
5763   last_nb_loops = gbb_nb_loops (gb);
5764   lambda_vector_copy (GBB_STATIC_SCHEDULE (gb), last_schedule,
5765                       last_nb_loops + 1);
5766   VEC_safe_push (graphite_bb_p, heap, bbs, gb);
5767
5768   for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
5769     {
5770       /* We did the first bb before.  */
5771       if (i == 0)
5772         continue;
5773
5774       nb_loops = gbb_nb_loops (gb);
5775
5776       /* If the number of loops is unchanged and only the last element of the
5777          schedule changes, we stay in the loop nest.  */
5778       if (nb_loops == last_nb_loops
5779           && (last_schedule [nb_loops + 1]
5780               != GBB_STATIC_SCHEDULE (gb)[nb_loops + 1]))
5781         {
5782           VEC_safe_push (graphite_bb_p, heap, bbs, gb);
5783           continue;
5784         }
5785
5786       /* Otherwise, we left the innermost loop. So check, if the last bb was in
5787          a perfect loop nest and how many loops are contained in this perfect
5788          loop nest.
5789
5790          Count the number of zeros from the end of the schedule. They are the
5791          number of surrounding loops.
5792
5793          Example:
5794          last_bb  2 3 2 0 0 0 0 3
5795          bb       2 4 0
5796          <------  j = 4
5797
5798          last_bb  2 3 2 0 0 0 0 3
5799          bb       2 3 2 0 1
5800          <--  j = 2
5801
5802          If there is no zero, there were other bbs in outer loops and the loop
5803          nest is not perfect.  */
5804       for (j = last_nb_loops - 1; j >= 0; j--)
5805         {
5806           if (last_schedule [j] != 0
5807               || (j <= nb_loops && GBB_STATIC_SCHEDULE (gb)[j] == 1))
5808             {
5809               j--;
5810               break;
5811             }
5812         }
5813
5814       j++;
5815
5816       /* Found perfect loop nest.  */
5817       if (perfect && last_nb_loops - j >= 2)
5818         transform_done |= graphite_trans_loop_block (bbs, last_nb_loops - j);
5819
5820       /* Check if we start with a new loop.
5821
5822          Example:
5823
5824          last_bb  2 3 2 0 0 0 0 3
5825          bb       2 3 2 0 0 1 0
5826
5827          Here we start with the loop "2 3 2 0 0 1"
5828
5829          last_bb  2 3 2 0 0 0 0 3
5830          bb       2 3 2 0 0 1
5831
5832          But here not, so the loop nest can never be perfect.  */
5833
5834       perfect = (GBB_STATIC_SCHEDULE (gb)[nb_loops] == 0);
5835
5836       /* Update the last_bb infos.  We do not do that for the bbs in the same
5837          loop, as the data we use is not changed.  */
5838       last_nb_loops = nb_loops;
5839       lambda_vector_copy (GBB_STATIC_SCHEDULE (gb), last_schedule,
5840                           nb_loops + 1);
5841       VEC_truncate (graphite_bb_p, bbs, 0);
5842       VEC_safe_push (graphite_bb_p, heap, bbs, gb);
5843     }
5844
5845   /* Check if the last loop nest was perfect.  It is the same check as above,
5846      but the comparison with the next bb is missing.  */
5847   for (j = last_nb_loops - 1; j >= 0; j--)
5848     if (last_schedule [j] != 0)
5849       {
5850         j--;
5851         break;
5852       }
5853
5854   j++;
5855
5856   /* Found perfect loop nest.  */
5857   if (last_nb_loops - j > 0)
5858     transform_done |= graphite_trans_loop_block (bbs, last_nb_loops - j);
5859   VEC_free (graphite_bb_p, heap, bbs);
5860
5861   if (dump_file && (dump_flags & TDF_DETAILS))
5862     fprintf (dump_file, "\nLoop blocked.\n");
5863
5864   return transform_done;
5865 }
5866
5867 /* Apply graphite transformations to all the basic blocks of SCOP.  */
5868
5869 static bool
5870 graphite_apply_transformations (scop_p scop)
5871 {
5872   bool transform_done = false;
5873
5874   /* Sort the list of bbs.  Keep them always sorted.  */
5875   graphite_sort_gbbs (scop);
5876
5877   if (flag_loop_block)
5878     transform_done = graphite_trans_scop_block (scop);
5879
5880   /* Generate code even if we did not apply any real transformation.
5881      This also allows to check the performance for the identity
5882      transformation: GIMPLE -> GRAPHITE -> GIMPLE
5883      Keep in mind that CLooG optimizes in control, so the loop structure
5884      may change, even if we only use -fgraphite-identity.  */
5885   if (flag_graphite_identity)
5886     transform_done = true;
5887
5888   return transform_done;
5889 }
5890
5891 /* We limit all SCoPs to SCoPs, that are completely surrounded by a loop.
5892
5893    Example:
5894
5895    for (i      |
5896      {         |
5897        for (j  |  SCoP 1
5898        for (k  |
5899      }         |
5900
5901    * SCoP frontier, as this line is not surrounded by any loop. *
5902
5903    for (l      |  SCoP 2
5904
5905    This is necessary as scalar evolution and parameter detection need a
5906    outermost loop to initialize parameters correctly.
5907
5908    TODO: FIX scalar evolution and parameter detection to allow more flexible
5909          SCoP frontiers.  */
5910
5911 static void
5912 limit_scops (void)
5913 {
5914   VEC (sd_region, heap) *tmp_scops = VEC_alloc (sd_region, heap, 3);
5915
5916   int i;
5917   scop_p scop;
5918
5919   for (i = 0; VEC_iterate (scop_p, current_scops, i, scop); i++)
5920     {
5921       int j;
5922       loop_p loop;
5923       build_scop_bbs (scop);
5924
5925       if (!build_scop_loop_nests (scop))
5926         continue;
5927
5928       for (j = 0; VEC_iterate (loop_p, SCOP_LOOP_NEST (scop), j, loop); j++)
5929         if (!loop_in_scop_p (loop_outer (loop), scop))
5930           {
5931             sd_region open_scop;
5932             open_scop.entry = loop->header;
5933             open_scop.exit = single_exit (loop)->dest;
5934             VEC_safe_push (sd_region, heap, tmp_scops, &open_scop);
5935           }
5936     }
5937
5938   free_scops (current_scops);
5939   current_scops = VEC_alloc (scop_p, heap, 3);
5940
5941   create_sese_edges (tmp_scops);
5942   build_graphite_scops (tmp_scops);
5943   VEC_free (sd_region, heap, tmp_scops);
5944 }
5945
5946 /* Perform a set of linear transforms on the loops of the current
5947    function.  */
5948
5949 void
5950 graphite_transform_loops (void)
5951 {
5952   int i;
5953   scop_p scop;
5954
5955   if (number_of_loops () <= 1)
5956     return;
5957
5958   current_scops = VEC_alloc (scop_p, heap, 3);
5959   recompute_all_dominators ();
5960
5961   if (dump_file && (dump_flags & TDF_DETAILS))
5962     fprintf (dump_file, "Graphite loop transformations \n");
5963
5964   initialize_original_copy_tables ();
5965   cloog_initialize ();
5966   build_scops ();
5967   limit_scops ();
5968
5969   if (dump_file && (dump_flags & TDF_DETAILS))
5970     fprintf (dump_file, "\nnumber of SCoPs: %d\n",
5971              VEC_length (scop_p, current_scops));
5972
5973   for (i = 0; VEC_iterate (scop_p, current_scops, i, scop); i++)
5974     {
5975       build_scop_bbs (scop);
5976       if (!build_scop_loop_nests (scop))
5977         continue;
5978
5979       build_scop_canonical_schedules (scop);
5980       build_bb_loops (scop);
5981       build_scop_conditions (scop);
5982       find_scop_parameters (scop);
5983       build_scop_context (scop);
5984
5985       if (dump_file && (dump_flags & TDF_DETAILS))
5986         {
5987           fprintf (dump_file, "\n(In SCoP %d:\n", i);
5988           fprintf (dump_file, "\nnumber of bbs: %d\n",
5989                    VEC_length (graphite_bb_p, SCOP_BBS (scop)));
5990           fprintf (dump_file, "\nnumber of loops: %d)\n",
5991                    VEC_length (loop_p, SCOP_LOOP_NEST (scop)));
5992         }
5993
5994       if (!build_scop_iteration_domain (scop))
5995         continue;
5996
5997       build_scop_data_accesses (scop);
5998       build_scop_dynamic_schedules (scop);
5999
6000       if (dump_file && (dump_flags & TDF_DETAILS))
6001         {
6002           int nbrefs = nb_data_refs_in_scop (scop);
6003           fprintf (dump_file, "\nnumber of data refs: %d\n", nbrefs);
6004         }
6005
6006       if (graphite_apply_transformations (scop))
6007         gloog (scop, find_transform (scop));
6008 #ifdef ENABLE_CHECKING
6009       else
6010         {
6011           struct clast_stmt *stmt = find_transform (scop);
6012           cloog_clast_free (stmt);
6013         }
6014 #endif
6015     }
6016
6017   /* Cleanup.  */
6018   free_scops (current_scops);
6019   cloog_finalize ();
6020   free_original_copy_tables ();
6021 }
6022
6023 #else /* If Cloog is not available: #ifndef HAVE_cloog.  */
6024
6025 void
6026 graphite_transform_loops (void)
6027 {
6028   sorry ("Graphite loop optimizations cannot be used");
6029 }
6030
6031 #endif