gcc/graphite.c

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