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