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 /* Returns the number of loops that are identical at the beginning of
2476    the vectors A and B.  */
2477
2478 static int
2479 compare_prefix_loops (VEC (loop_p, heap) *a, VEC (loop_p, heap) *b)
2480 {
2481   int i;
2482   loop_p ea;
2483   int lb;
2484
2485   if (!a || !b)
2486     return 0;
2487
2488   lb = VEC_length (loop_p, b);
2489
2490   for (i = 0; VEC_iterate (loop_p, a, i, ea); i++)
2491     if (i >= lb
2492         || ea != VEC_index (loop_p, b, i))
2493       return i;
2494
2495   return 0;
2496 }
2497
2498 /* Build for BB the static schedule.
2499
2500    The STATIC_SCHEDULE is defined like this:
2501
2502    A
2503    for (i: ...)
2504      {
2505        for (j: ...)
2506          {
2507            B
2508            C
2509          }
2510
2511        for (k: ...)
2512          {
2513            D
2514            E
2515          }
2516      }
2517    F
2518
2519    Static schedules for A to F:
2520
2521      DEPTH
2522      0 1 2
2523    A 0
2524    B 1 0 0
2525    C 1 0 1
2526    D 1 1 0
2527    E 1 1 1
2528    F 2
2529 */
2530
2531 static void
2532 build_scop_canonical_schedules (scop_p scop)
2533 {
2534   int i;
2535   graphite_bb_p gb;
2536   int nb_loops = scop_nb_loops (scop);
2537   lambda_vector static_schedule = lambda_vector_new (nb_loops + 1);
2538   VEC (loop_p, heap) *loops_previous = NULL;
2539
2540   /* We have to start schedules at 0 on the first component and
2541      because we cannot compare_prefix_loops against a previous loop,
2542      prefix will be equal to zero, and that index will be
2543      incremented before copying.  */
2544   static_schedule[0] = -1;
2545
2546   for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
2547     {
2548       int prefix = compare_prefix_loops (loops_previous, GBB_LOOPS (gb));
2549       int nb = gbb_nb_loops (gb);
2550
2551       loops_previous = GBB_LOOPS (gb);
2552       memset (&(static_schedule[prefix + 1]), 0, sizeof (int) * (nb_loops - prefix));
2553       ++static_schedule[prefix];
2554       GBB_STATIC_SCHEDULE (gb) = lambda_vector_new (nb + 1);
2555       lambda_vector_copy (static_schedule,
2556                           GBB_STATIC_SCHEDULE (gb), nb + 1);
2557     }
2558 }
2559
2560 /* Build the LOOPS vector for all bbs in SCOP.  */
2561
2562 static void
2563 build_bb_loops (scop_p scop)
2564 {
2565   graphite_bb_p gb;
2566   int i;
2567
2568   for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
2569     {
2570       loop_p loop;
2571       int depth;
2572
2573       depth = nb_loops_around_gb (gb) - 1;
2574
2575       GBB_LOOPS (gb) = VEC_alloc (loop_p, heap, 3);
2576       VEC_safe_grow_cleared (loop_p, heap, GBB_LOOPS (gb), depth + 1);
2577
2578       loop = GBB_BB (gb)->loop_father;
2579
2580       while (scop_contains_loop (scop, loop))
2581         {
2582           VEC_replace (loop_p, GBB_LOOPS (gb), depth, loop);
2583           loop = loop_outer (loop);
2584           depth--;
2585         }
2586     }
2587 }
2588
2589 /* Get the index for parameter VAR in SCOP.  */
2590
2591 static int
2592 param_index (tree var, scop_p scop)
2593 {
2594   int i;
2595   name_tree p;
2596   name_tree nvar;
2597
2598   gcc_assert (TREE_CODE (var) == SSA_NAME);
2599
2600   for (i = 0; VEC_iterate (name_tree, SCOP_PARAMS (scop), i, p); i++)
2601     if (p->t == var)
2602       return i;
2603
2604   gcc_assert (SCOP_ADD_PARAMS (scop));
2605
2606   nvar = XNEW (struct name_tree);
2607   nvar->t = var;
2608   nvar->name = NULL;
2609   VEC_safe_push (name_tree, heap, SCOP_PARAMS (scop), nvar);
2610   return VEC_length (name_tree, SCOP_PARAMS (scop)) - 1;
2611 }
2612
2613 /* Scan EXPR and translate it to an inequality vector INEQ that will
2614    be added, or subtracted, in the constraint domain matrix C at row
2615    R.  K is the number of columns for loop iterators in C. */
2616
2617 static void
2618 scan_tree_for_params (scop_p s, tree e, CloogMatrix *c, int r, Value k,
2619                       bool subtract)
2620 {
2621   int cst_col, param_col;
2622
2623   if (e == chrec_dont_know)
2624     return;
2625
2626   switch (TREE_CODE (e))
2627     {
2628     case POLYNOMIAL_CHREC:
2629       {
2630         tree left = CHREC_LEFT (e);
2631         tree right = CHREC_RIGHT (e);
2632         int var = CHREC_VARIABLE (e);
2633
2634         if (TREE_CODE (right) != INTEGER_CST)
2635           return;
2636
2637         if (c)
2638           {
2639             int loop_col = scop_gimple_loop_depth (s, get_loop (var)) + 1;
2640
2641             if (subtract)
2642               value_sub_int (c->p[r][loop_col], c->p[r][loop_col],
2643                              int_cst_value (right));
2644             else
2645               value_add_int (c->p[r][loop_col], c->p[r][loop_col],
2646                              int_cst_value (right));
2647           }
2648
2649         switch (TREE_CODE (left))
2650           {
2651           case POLYNOMIAL_CHREC:
2652             scan_tree_for_params (s, left, c, r, k, subtract);
2653             return;
2654
2655           case INTEGER_CST:
2656             /* Constant part.  */
2657             if (c)
2658               {
2659                 int v = int_cst_value (left);
2660                 cst_col = c->NbColumns - 1;
2661
2662                 if (v < 0)
2663                   {
2664                     v = -v;
2665                     subtract = subtract ? false : true;
2666                   }
2667
2668                 if (subtract)
2669                   value_sub_int (c->p[r][cst_col], c->p[r][cst_col], v);
2670                 else
2671                   value_add_int (c->p[r][cst_col], c->p[r][cst_col], v);
2672               }
2673             return;
2674
2675           default:
2676             scan_tree_for_params (s, left, c, r, k, subtract);
2677             return;
2678           }
2679       }
2680       break;
2681
2682     case MULT_EXPR:
2683       if (chrec_contains_symbols (TREE_OPERAND (e, 0)))
2684         {
2685           if (c)
2686             {
2687               Value val;
2688               gcc_assert (host_integerp (TREE_OPERAND (e, 1), 0));
2689               value_init (val);
2690               value_set_si (val, int_cst_value (TREE_OPERAND (e, 1)));
2691               value_multiply (k, k, val);
2692               value_clear (val);
2693             }
2694           scan_tree_for_params (s, TREE_OPERAND (e, 0), c, r, k, subtract);
2695         }
2696       else
2697         {
2698           if (c)
2699             {
2700               Value val;
2701               gcc_assert (host_integerp (TREE_OPERAND (e, 0), 0));
2702               value_init (val);
2703               value_set_si (val, int_cst_value (TREE_OPERAND (e, 0)));
2704               value_multiply (k, k, val);
2705               value_clear (val);
2706             }
2707           scan_tree_for_params (s, TREE_OPERAND (e, 1), c, r, k, subtract);
2708         }
2709       break;
2710
2711     case PLUS_EXPR:
2712     case POINTER_PLUS_EXPR:
2713       scan_tree_for_params (s, TREE_OPERAND (e, 0), c, r, k, subtract);
2714       scan_tree_for_params (s, TREE_OPERAND (e, 1), c, r, k, subtract);
2715       break;
2716
2717     case MINUS_EXPR:
2718       scan_tree_for_params (s, TREE_OPERAND (e, 0), c, r, k, subtract);
2719       scan_tree_for_params (s, TREE_OPERAND (e, 1), c, r, k, !subtract);
2720       break;
2721
2722     case NEGATE_EXPR:
2723       scan_tree_for_params (s, TREE_OPERAND (e, 0), c, r, k, !subtract);
2724       break;
2725
2726     case SSA_NAME:
2727       param_col = param_index (e, s);
2728
2729       if (c)
2730         {
2731           param_col += c->NbColumns - scop_nb_params (s) - 1;
2732
2733           if (subtract)
2734             value_subtract (c->p[r][param_col], c->p[r][param_col], k);
2735           else
2736             value_addto (c->p[r][param_col], c->p[r][param_col], k);
2737         }
2738       break;
2739
2740     case INTEGER_CST:
2741       if (c)
2742         {
2743           int v = int_cst_value (e);
2744           cst_col = c->NbColumns - 1;
2745
2746           if (v < 0)
2747           {
2748             v = -v;
2749             subtract = subtract ? false : true;
2750           }
2751
2752           if (subtract)
2753             value_sub_int (c->p[r][cst_col], c->p[r][cst_col], v);
2754           else
2755             value_add_int (c->p[r][cst_col], c->p[r][cst_col], v);
2756         }
2757       break;
2758
2759     CASE_CONVERT:
2760     case NON_LVALUE_EXPR:
2761       scan_tree_for_params (s, TREE_OPERAND (e, 0), c, r, k, subtract);
2762       break;
2763
2764     default:
2765       gcc_unreachable ();
2766       break;
2767     }
2768 }
2769
2770 /* Data structure for idx_record_params.  */
2771
2772 struct irp_data
2773 {
2774   struct loop *loop;
2775   scop_p scop;
2776 };
2777
2778 /* For a data reference with an ARRAY_REF as its BASE, record the
2779    parameters occurring in IDX.  DTA is passed in as complementary
2780    information, and is used by the automatic walker function.  This
2781    function is a callback for for_each_index.  */
2782
2783 static bool
2784 idx_record_params (tree base, tree *idx, void *dta)
2785 {
2786   struct irp_data *data = (struct irp_data *) dta;
2787
2788   if (TREE_CODE (base) != ARRAY_REF)
2789     return true;
2790
2791   if (TREE_CODE (*idx) == SSA_NAME)
2792     {
2793       tree scev;
2794       scop_p scop = data->scop;
2795       struct loop *loop = data->loop;
2796       Value one;
2797
2798       scev = analyze_scalar_evolution (loop, *idx);
2799       scev = instantiate_scev (block_before_scop (scop), loop, scev);
2800
2801       value_init (one);
2802       value_set_si (one, 1);
2803       scan_tree_for_params (scop, scev, NULL, 0, one, false);
2804       value_clear (one);
2805     }
2806
2807   return true;
2808 }
2809
2810 /* Find parameters with respect to SCOP in BB. We are looking in memory
2811    access functions, conditions and loop bounds.  */
2812
2813 static void
2814 find_params_in_bb (scop_p scop, graphite_bb_p gb)
2815 {
2816   int i;
2817   data_reference_p dr;
2818   gimple stmt;
2819   loop_p father = GBB_BB (gb)->loop_father;
2820
2821   for (i = 0; VEC_iterate (data_reference_p, GBB_DATA_REFS (gb), i, dr); i++)
2822     {
2823       struct irp_data irp;
2824
2825       irp.loop = father;
2826       irp.scop = scop;
2827       for_each_index (&dr->ref, idx_record_params, &irp);
2828     }
2829
2830   /* Find parameters in conditional statements.  */
2831   for (i = 0; VEC_iterate (gimple, GBB_CONDITIONS (gb), i, stmt); i++)
2832     {
2833       Value one;
2834       loop_p loop = father;
2835
2836       tree lhs, rhs;
2837
2838       lhs = gimple_cond_lhs (stmt);
2839       lhs = analyze_scalar_evolution (loop, lhs);
2840       lhs = instantiate_scev (block_before_scop (scop), loop, lhs);
2841
2842       rhs = gimple_cond_rhs (stmt);
2843       rhs = analyze_scalar_evolution (loop, rhs);
2844       rhs = instantiate_scev (block_before_scop (scop), loop, rhs);
2845
2846       value_init (one);
2847       scan_tree_for_params (scop, lhs, NULL, 0, one, false);
2848       value_set_si (one, 1);
2849       scan_tree_for_params (scop, rhs, NULL, 0, one, false);
2850       value_clear (one);
2851     }
2852 }
2853
2854 /* Saves in NV the name of variable P->T.  */
2855
2856 static void
2857 save_var_name (char **nv, int i, name_tree p)
2858 {
2859   const char *name = get_name (SSA_NAME_VAR (p->t));
2860
2861   if (name)
2862     {
2863       int len = strlen (name) + 16;
2864       nv[i] = XNEWVEC (char, len);
2865       snprintf (nv[i], len, "%s_%d", name, SSA_NAME_VERSION (p->t));
2866     }
2867   else
2868     {
2869       nv[i] = XNEWVEC (char, 16);
2870       snprintf (nv[i], 2 + 16, "T_%d", SSA_NAME_VERSION (p->t));
2871     }
2872
2873   p->name = nv[i];
2874 }
2875
2876 /* Return the maximal loop depth in SCOP.  */
2877
2878 static int
2879 scop_max_loop_depth (scop_p scop)
2880 {
2881   int i;
2882   graphite_bb_p gbb;
2883   int max_nb_loops = 0;
2884
2885   for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gbb); i++)
2886     {
2887       int nb_loops = gbb_nb_loops (gbb);
2888       if (max_nb_loops < nb_loops)
2889         max_nb_loops = nb_loops;
2890     }
2891
2892   return max_nb_loops;
2893 }
2894
2895 /* Initialize Cloog's parameter names from the names used in GIMPLE.
2896    Initialize Cloog's iterator names, using 'graphite_iterator_%d'
2897    from 0 to scop_nb_loops (scop).  */
2898
2899 static void
2900 initialize_cloog_names (scop_p scop)
2901 {
2902   int i, nb_params = VEC_length (name_tree, SCOP_PARAMS (scop));
2903   char **params = XNEWVEC (char *, nb_params);
2904   int nb_iterators = scop_max_loop_depth (scop);
2905   int nb_scattering= cloog_program_nb_scattdims (SCOP_PROG (scop));
2906   char **iterators = XNEWVEC (char *, nb_iterators * 2);
2907   char **scattering = XNEWVEC (char *, nb_scattering);
2908   name_tree p;
2909
2910   for (i = 0; VEC_iterate (name_tree, SCOP_PARAMS (scop), i, p); i++)
2911     save_var_name (params, i, p);
2912
2913   cloog_names_set_nb_parameters (cloog_program_names (SCOP_PROG (scop)),
2914                                  nb_params);
2915   cloog_names_set_parameters (cloog_program_names (SCOP_PROG (scop)),
2916                               params);
2917
2918   for (i = 0; i < nb_iterators; i++)
2919     {
2920       int len = 18 + 16;
2921       iterators[i] = XNEWVEC (char, len);
2922       snprintf (iterators[i], len, "graphite_iterator_%d", i);
2923     }
2924
2925   cloog_names_set_nb_iterators (cloog_program_names (SCOP_PROG (scop)),
2926                                 nb_iterators);
2927   cloog_names_set_iterators (cloog_program_names (SCOP_PROG (scop)),
2928                              iterators);
2929
2930   for (i = 0; i < nb_scattering; i++)
2931     {
2932       int len = 2 + 16;
2933       scattering[i] = XNEWVEC (char, len);
2934       snprintf (scattering[i], len, "s_%d", i);
2935     }
2936
2937   cloog_names_set_nb_scattering (cloog_program_names (SCOP_PROG (scop)),
2938                                  nb_scattering);
2939   cloog_names_set_scattering (cloog_program_names (SCOP_PROG (scop)),
2940                               scattering);
2941 }
2942
2943 /* Record the parameters used in the SCOP.  A variable is a parameter
2944    in a scop if it does not vary during the execution of that scop.  */
2945
2946 static void
2947 find_scop_parameters (scop_p scop)
2948 {
2949   graphite_bb_p gb;
2950   unsigned i;
2951   struct loop *loop;
2952   Value one;
2953
2954   value_init (one);
2955   value_set_si (one, 1);
2956
2957   /* Find the parameters used in the loop bounds.  */
2958   for (i = 0; VEC_iterate (loop_p, SCOP_LOOP_NEST (scop), i, loop); i++)
2959     {
2960       tree nb_iters = number_of_latch_executions (loop);
2961
2962       if (!chrec_contains_symbols (nb_iters))
2963         continue;
2964
2965       nb_iters = analyze_scalar_evolution (loop, nb_iters);
2966       nb_iters = instantiate_scev (block_before_scop (scop), loop, nb_iters);
2967       scan_tree_for_params (scop, nb_iters, NULL, 0, one, false);
2968     }
2969
2970   value_clear (one);
2971
2972   /* Find the parameters used in data accesses.  */
2973   for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
2974     find_params_in_bb (scop, gb);
2975
2976   SCOP_ADD_PARAMS (scop) = false;
2977 }
2978
2979 /* Build the context constraints for SCOP: constraints and relations
2980    on parameters.  */
2981
2982 static void
2983 build_scop_context (scop_p scop)
2984 {
2985   int nb_params = scop_nb_params (scop);
2986   CloogMatrix *matrix = cloog_matrix_alloc (1, nb_params + 2);
2987
2988   /* Insert '0 >= 0' in the context matrix, as it is not allowed to be
2989      empty. */
2990
2991   value_set_si (matrix->p[0][0], 1);
2992
2993   value_set_si (matrix->p[0][nb_params + 1], 0);
2994
2995   cloog_program_set_context (SCOP_PROG (scop),
2996                              cloog_domain_matrix2domain (matrix));
2997   cloog_matrix_free (matrix);
2998 }
2999
3000 /* Returns a graphite_bb from BB.  */
3001
3002 static inline graphite_bb_p
3003 gbb_from_bb (basic_block bb)
3004 {
3005   return (graphite_bb_p) bb->aux;
3006 }
3007
3008 /* Builds the constraint matrix for LOOP in SCOP.  NB_OUTER_LOOPS is the
3009    number of loops surrounding LOOP in SCOP.  OUTER_CSTR gives the
3010    constraints matrix for the surrounding loops.  */
3011
3012 static void
3013 build_loop_iteration_domains (scop_p scop, struct loop *loop,
3014                               CloogMatrix *outer_cstr, int nb_outer_loops)
3015 {
3016   int i, j, row;
3017   CloogMatrix *cstr;
3018   graphite_bb_p gb;
3019
3020   int nb_rows = outer_cstr->NbRows + 1;
3021   int nb_cols = outer_cstr->NbColumns + 1;
3022
3023   /* Last column of CSTR is the column of constants.  */
3024   int cst_col = nb_cols - 1;
3025
3026   /* The column for the current loop is just after the columns of
3027      other outer loops.  */
3028   int loop_col = nb_outer_loops + 1;
3029
3030   tree nb_iters = number_of_latch_executions (loop);
3031
3032   /* When the number of iterations is a constant or a parameter, we
3033      add a constraint for the upper bound of the loop.  So add a row
3034      to the constraint matrix before allocating it.  */
3035   if (TREE_CODE (nb_iters) == INTEGER_CST
3036       || !chrec_contains_undetermined (nb_iters))
3037     nb_rows++;
3038
3039   cstr = cloog_matrix_alloc (nb_rows, nb_cols);
3040
3041   /* Copy the outer constraints.  */
3042   for (i = 0; i < outer_cstr->NbRows; i++)
3043     {
3044       /* Copy the eq/ineq and loops columns.  */
3045       for (j = 0; j < loop_col; j++)
3046         value_assign (cstr->p[i][j], outer_cstr->p[i][j]);
3047
3048       /* Leave an empty column in CSTR for the current loop, and then
3049          copy the parameter columns.  */
3050       for (j = loop_col; j < outer_cstr->NbColumns; j++)
3051         value_assign (cstr->p[i][j + 1], outer_cstr->p[i][j]);
3052     }
3053
3054   /* 0 <= loop_i */
3055   row = outer_cstr->NbRows;
3056   value_set_si (cstr->p[row][0], 1);
3057   value_set_si (cstr->p[row][loop_col], 1);
3058
3059   /* loop_i <= nb_iters */
3060   if (TREE_CODE (nb_iters) == INTEGER_CST)
3061     {
3062       row++;
3063       value_set_si (cstr->p[row][0], 1);
3064       value_set_si (cstr->p[row][loop_col], -1);
3065
3066       value_set_si (cstr->p[row][cst_col],
3067                     int_cst_value (nb_iters));
3068     }
3069   else if (!chrec_contains_undetermined (nb_iters))
3070     {
3071       /* Otherwise nb_iters contains parameters: scan the nb_iters
3072          expression and build its matrix representation.  */
3073       Value one;
3074
3075       row++;
3076       value_set_si (cstr->p[row][0], 1);
3077       value_set_si (cstr->p[row][loop_col], -1);
3078
3079       nb_iters = analyze_scalar_evolution (loop, nb_iters);
3080       nb_iters = instantiate_scev (block_before_scop (scop), loop, nb_iters);
3081
3082       value_init (one);
3083       value_set_si (one, 1);
3084       scan_tree_for_params (scop, nb_iters, cstr, row, one, false);
3085       value_clear (one);
3086     }
3087   else
3088     gcc_unreachable ();
3089
3090   if (loop->inner && loop_in_scop_p (loop->inner, scop))
3091     build_loop_iteration_domains (scop, loop->inner, cstr, nb_outer_loops + 1);
3092
3093   /* Only go to the next loops, if we are not at the outermost layer.  These
3094      have to be handled seperately, as we can be sure, that the chain at this
3095      layer will be connected.  */
3096   if (nb_outer_loops != 0 && loop->next && loop_in_scop_p (loop->next, scop))
3097     build_loop_iteration_domains (scop, loop->next, outer_cstr, nb_outer_loops);
3098
3099   for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
3100     if (gbb_loop (gb) == loop)
3101       GBB_DOMAIN (gb) = cloog_matrix_copy (cstr);
3102
3103   cloog_matrix_free (cstr);
3104 }
3105
3106 /* Add conditions to the domain of GB.  */
3107
3108 static void
3109 add_conditions_to_domain (graphite_bb_p gb)
3110 {
3111   unsigned int i,j;
3112   gimple stmt;
3113   VEC (gimple, heap) *conditions = GBB_CONDITIONS (gb);
3114   CloogMatrix *domain = GBB_DOMAIN (gb);
3115   scop_p scop = GBB_SCOP (gb);
3116
3117   unsigned nb_rows;
3118   unsigned nb_cols;
3119   unsigned nb_new_rows = 0;
3120   unsigned row;
3121
3122   if (VEC_empty (gimple, conditions))
3123     return;
3124
3125   if (domain)
3126     {
3127       nb_rows = domain->NbRows;
3128       nb_cols = domain->NbColumns;
3129     }
3130   else
3131     {
3132       nb_rows = 0;
3133       nb_cols = nb_loops_around_gb (gb) + scop_nb_params (scop) + 2;
3134     }
3135
3136   /* Count number of necessary new rows to add the conditions to the
3137      domain.  */
3138   for (i = 0; VEC_iterate (gimple, conditions, i, stmt); i++)
3139     {
3140       switch (gimple_code (stmt))
3141         {
3142         case GIMPLE_COND:
3143           {
3144             enum tree_code code = gimple_cond_code (stmt);
3145
3146             switch (code)
3147               {
3148               case NE_EXPR:
3149               case EQ_EXPR:
3150                 /* NE and EQ statements are not supported right know. */
3151                 gcc_unreachable ();
3152                 break;
3153               case LT_EXPR:
3154               case GT_EXPR:
3155               case LE_EXPR:
3156               case GE_EXPR:
3157                 nb_new_rows++;
3158                 break;
3159               default:
3160                 gcc_unreachable ();
3161                 break;
3162               }
3163           break;
3164           }
3165         case SWITCH_EXPR:
3166           /* Switch statements are not supported right know.  */
3167           gcc_unreachable ();
3168           break;
3169
3170         default:
3171           gcc_unreachable ();
3172           break;
3173         }
3174     }
3175
3176
3177   /* Enlarge the matrix.  */
3178   {
3179     CloogMatrix *new_domain;
3180     new_domain = cloog_matrix_alloc (nb_rows + nb_new_rows, nb_cols);
3181
3182     if (domain)
3183       {
3184         for (i = 0; i < nb_rows; i++)
3185           for (j = 0; j < nb_cols; j++)
3186             value_assign (new_domain->p[i][j], domain->p[i][j]);
3187
3188         cloog_matrix_free (domain);
3189       }
3190
3191     domain = new_domain;
3192     GBB_DOMAIN (gb) = new_domain;
3193   }
3194
3195   /* Add the conditions to the new enlarged domain matrix.  */
3196   row = nb_rows;
3197   for (i = 0; VEC_iterate (gimple, conditions, i, stmt); i++)
3198     {
3199       switch (gimple_code (stmt))
3200         {
3201         case GIMPLE_COND:
3202           {
3203             Value one;
3204             enum tree_code code;
3205             tree left;
3206             tree right;
3207             loop_p loop = GBB_BB (gb)->loop_father;
3208
3209             left = gimple_cond_lhs (stmt);
3210             right = gimple_cond_rhs (stmt);
3211
3212             left = analyze_scalar_evolution (loop, left);
3213             right = analyze_scalar_evolution (loop, right);
3214
3215             left = instantiate_scev (block_before_scop (scop), loop, left);
3216             right = instantiate_scev (block_before_scop (scop), loop, right);
3217
3218             code = gimple_cond_code (stmt);
3219
3220             /* The conditions for ELSE-branches are inverted.  */
3221             if (VEC_index (gimple, gb->condition_cases, i) == NULL)
3222               code = invert_tree_comparison (code, false);
3223
3224             switch (code)
3225               {
3226               case NE_EXPR:
3227                 /* NE statements are not supported right know. */
3228                 gcc_unreachable ();
3229                 break;
3230               case EQ_EXPR:
3231                 value_set_si (domain->p[row][0], 1);
3232                 value_init (one);
3233                 value_set_si (one, 1);
3234                 scan_tree_for_params (scop, left, domain, row, one, true);
3235                 value_set_si (one, 1);
3236                 scan_tree_for_params (scop, right, domain, row, one, false);
3237                 row++;
3238                 value_set_si (domain->p[row][0], 1);
3239                 value_set_si (one, 1);
3240                 scan_tree_for_params (scop, left, domain, row, one, false);
3241                 value_set_si (one, 1);
3242                 scan_tree_for_params (scop, right, domain, row, one, true);
3243                 value_clear (one);
3244                 row++;
3245                 break;
3246               case LT_EXPR:
3247                 value_set_si (domain->p[row][0], 1);
3248                 value_init (one);
3249                 value_set_si (one, 1);
3250                 scan_tree_for_params (scop, left, domain, row, one, true);
3251                 value_set_si (one, 1);
3252                 scan_tree_for_params (scop, right, domain, row, one, false);
3253                 value_sub_int (domain->p[row][nb_cols - 1],
3254                     domain->p[row][nb_cols - 1], 1);
3255                 value_clear (one);
3256                 row++;
3257                 break;
3258               case GT_EXPR:
3259                 value_set_si (domain->p[row][0], 1);
3260                 value_init (one);
3261                 value_set_si (one, 1);
3262                 scan_tree_for_params (scop, left, domain, row, one, false);
3263                 value_set_si (one, 1);
3264                 scan_tree_for_params (scop, right, domain, row, one, true);
3265                 value_sub_int (domain->p[row][nb_cols - 1],
3266                     domain->p[row][nb_cols - 1], 1);
3267                 value_clear (one);
3268                 row++;
3269                 break;
3270               case LE_EXPR:
3271                 value_set_si (domain->p[row][0], 1);
3272                 value_init (one);
3273                 value_set_si (one, 1);
3274                 scan_tree_for_params (scop, left, domain, row, one, true);
3275                 value_set_si (one, 1);
3276                 scan_tree_for_params (scop, right, domain, row, one, false);
3277                 value_clear (one);
3278                 row++;
3279                 break;
3280               case GE_EXPR:
3281                 value_set_si (domain->p[row][0], 1);
3282                 value_init (one);
3283                 value_set_si (one, 1);
3284                 scan_tree_for_params (scop, left, domain, row, one, false);
3285                 value_set_si (one, 1);
3286                 scan_tree_for_params (scop, right, domain, row, one, true);
3287                 value_clear (one);
3288                 row++;
3289                 break;
3290               default:
3291                 gcc_unreachable ();
3292                 break;
3293               }
3294             break;
3295           }
3296         case GIMPLE_SWITCH:
3297           /* Switch statements are not supported right know.  */
3298           gcc_unreachable ();
3299           break;
3300
3301         default:
3302           gcc_unreachable ();
3303           break;
3304         }
3305     }
3306 }
3307
3308 /* Returns true when PHI defines an induction variable in the loop
3309    containing the PHI node.  */
3310
3311 static bool
3312 phi_node_is_iv (gimple phi)
3313 {
3314   loop_p loop = gimple_bb (phi)->loop_father;
3315   tree scev = analyze_scalar_evolution (loop, gimple_phi_result (phi));
3316
3317   return tree_contains_chrecs (scev, NULL);
3318 }
3319
3320 /* Returns true when BB contains scalar phi nodes that are not an
3321    induction variable of a loop.  */
3322
3323 static bool
3324 bb_contains_non_iv_scalar_phi_nodes (basic_block bb)
3325 {
3326   gimple phi = NULL;
3327   gimple_stmt_iterator si;
3328
3329   for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
3330     if (is_gimple_reg (gimple_phi_result (gsi_stmt (si))))
3331       {
3332         /* Store the unique scalar PHI node: at this point, loops
3333            should be in cannonical form, so we expect to see at most
3334            one scalar phi node in the loop header.  */
3335         if (phi
3336             || bb != bb->loop_father->header)
3337           return true;
3338
3339         phi = gsi_stmt (si);
3340       }
3341
3342   if (!phi
3343       || phi_node_is_iv (phi))
3344     return false;
3345
3346   return true;
3347 }
3348
3349 /* Helper recursive function.  Record in CONDITIONS and CASES all
3350    conditions from 'if's and 'switch'es occurring in BB from SCOP.
3351
3352    Returns false when the conditions contain scalar computations that
3353    depend on the condition, i.e. when there are scalar phi nodes on
3354    the junction after the condition.  Only the computations occurring
3355    on memory can be handled in the polyhedral model: operations that
3356    define scalar evolutions in conditions, that can potentially be
3357    used to index memory, can't be handled by the polyhedral model.  */
3358
3359 static bool
3360 build_scop_conditions_1 (VEC (gimple, heap) **conditions,
3361                          VEC (gimple, heap) **cases, basic_block bb,
3362                          scop_p scop)
3363 {
3364   bool res = true;
3365   int i, j;
3366   graphite_bb_p gbb;
3367   gimple_stmt_iterator gsi;
3368   basic_block bb_child, bb_iter;
3369   VEC (basic_block, heap) *dom;
3370
3371   /* Make sure we are in the SCoP.  */
3372   if (!bb_in_scop_p (bb, scop))
3373     return true;
3374
3375   if (bb_contains_non_iv_scalar_phi_nodes (bb))
3376     return false;
3377
3378   gbb = gbb_from_bb (bb);
3379   if (gbb)
3380     {
3381       GBB_CONDITIONS (gbb) = VEC_copy (gimple, heap, *conditions);
3382       GBB_CONDITION_CASES (gbb) = VEC_copy (gimple, heap, *cases);
3383     }
3384
3385   dom = get_dominated_by (CDI_DOMINATORS, bb);
3386
3387   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
3388     {
3389       gimple stmt = gsi_stmt (gsi);
3390       VEC (edge, gc) *edges;
3391       edge e;
3392
3393       switch (gimple_code (stmt))
3394         {
3395         case GIMPLE_COND:
3396           edges = bb->succs;
3397           for (i = 0; VEC_iterate (edge, edges, i, e); i++)
3398             if ((dominated_by_p (CDI_DOMINATORS, e->dest, bb))
3399                 && VEC_length (edge, e->dest->preds) == 1)
3400               {
3401                 /* Remove the scanned block from the dominator successors.  */
3402                 for (j = 0; VEC_iterate (basic_block, dom, j, bb_iter); j++)
3403                   if (bb_iter == e->dest)
3404                     {
3405                       VEC_unordered_remove (basic_block, dom, j);
3406                       break;
3407                     }
3408
3409                 /* Recursively scan the then or else part.  */
3410                 if (e->flags & EDGE_TRUE_VALUE)
3411                   VEC_safe_push (gimple, heap, *cases, stmt);
3412                 else
3413                   {
3414                     gcc_assert (e->flags & EDGE_FALSE_VALUE);
3415                     VEC_safe_push (gimple, heap, *cases, NULL);
3416                   }
3417
3418                 VEC_safe_push (gimple, heap, *conditions, stmt);
3419                 if (!build_scop_conditions_1 (conditions, cases, e->dest, scop))
3420                   {
3421                     res = false;
3422                     goto done;
3423                   }
3424                 VEC_pop (gimple, *conditions);
3425                 VEC_pop (gimple, *cases);
3426               }
3427           break;
3428
3429         case GIMPLE_SWITCH:
3430           {
3431             unsigned i;
3432             gimple_stmt_iterator gsi_search_gimple_label;
3433
3434             for (i = 0; i < gimple_switch_num_labels (stmt); ++i)
3435               {
3436                 basic_block bb_iter;
3437                 size_t k;
3438                 size_t n_cases = VEC_length (gimple, *conditions);
3439                 unsigned n = gimple_switch_num_labels (stmt);
3440
3441                 bb_child = label_to_block
3442                   (CASE_LABEL (gimple_switch_label (stmt, i)));
3443
3444                 for (k = 0; k < n; k++)
3445                   if (i != k
3446                       && label_to_block
3447                       (CASE_LABEL (gimple_switch_label (stmt, k))) == bb_child)
3448                     break;
3449
3450                 /* Switches with multiple case values for the same
3451                    block are not handled.  */
3452                 if (k != n
3453                     /* Switch cases with more than one predecessor are
3454                        not handled.  */
3455                     || VEC_length (edge, bb_child->preds) != 1)
3456                   {
3457                     res = false;
3458                     goto done;
3459                   }
3460
3461                 /* Recursively scan the corresponding 'case' block.  */
3462                 for (gsi_search_gimple_label = gsi_start_bb (bb_child);
3463                      !gsi_end_p (gsi_search_gimple_label);
3464                      gsi_next (&gsi_search_gimple_label))
3465                   {
3466                     gimple label = gsi_stmt (gsi_search_gimple_label);
3467
3468                     if (gimple_code (label) == GIMPLE_LABEL)
3469                       {
3470                         tree t = gimple_label_label (label);
3471
3472                         gcc_assert (t == gimple_switch_label (stmt, i));
3473                         VEC_replace (gimple, *cases, n_cases, label);
3474                         break;
3475                       }
3476                   }
3477
3478                 if (!build_scop_conditions_1 (conditions, cases, bb_child, scop))
3479                   {
3480                     res = false;
3481                     goto done;
3482                   }
3483
3484                 /* Remove the scanned block from the dominator successors.  */
3485                 for (j = 0; VEC_iterate (basic_block, dom, j, bb_iter); j++)
3486                   if (bb_iter == bb_child)
3487                     {
3488                       VEC_unordered_remove (basic_block, dom, j);
3489                       break;
3490                     }
3491               }
3492
3493             VEC_pop (gimple, *conditions);
3494             VEC_pop (gimple, *cases);
3495             break;
3496           }
3497
3498         default:
3499           break;
3500       }
3501   }
3502
3503   /* Scan all immediate dominated successors.  */
3504   for (i = 0; VEC_iterate (basic_block, dom, i, bb_child); i++)
3505     if (!build_scop_conditions_1 (conditions, cases, bb_child, scop))
3506       {
3507         res = false;
3508         goto done;
3509       }
3510
3511  done:
3512   VEC_free (basic_block, heap, dom);
3513   return res;
3514 }
3515
3516 /* Record all conditions from SCOP.
3517
3518    Returns false when the conditions contain scalar computations that
3519    depend on the condition, i.e. when there are scalar phi nodes on
3520    the junction after the condition.  Only the computations occurring
3521    on memory can be handled in the polyhedral model: operations that
3522    define scalar evolutions in conditions, that can potentially be
3523    used to index memory, can't be handled by the polyhedral model.  */
3524
3525 static bool
3526 build_scop_conditions (scop_p scop)
3527 {
3528   bool res;
3529   VEC (gimple, heap) *conditions = NULL;
3530   VEC (gimple, heap) *cases = NULL;
3531
3532   res = build_scop_conditions_1 (&conditions, &cases, SCOP_ENTRY (scop), scop);
3533
3534   VEC_free (gimple, heap, conditions);
3535   VEC_free (gimple, heap, cases);
3536   return res;
3537 }
3538
3539 /* Traverses all the GBBs of the SCOP and add their constraints to the
3540    iteration domains.  */
3541
3542 static void
3543 add_conditions_to_constraints (scop_p scop)
3544 {
3545   int i;
3546   graphite_bb_p gbb;
3547
3548   for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gbb); i++)
3549     add_conditions_to_domain (gbb);
3550 }
3551
3552 /* Build the current domain matrix: the loops belonging to the current
3553    SCOP, and that vary for the execution of the current basic block.
3554    Returns false if there is no loop in SCOP.  */
3555
3556 static bool
3557 build_scop_iteration_domain (scop_p scop)
3558 {
3559   struct loop *loop;
3560   CloogMatrix *outer_cstr;
3561   int i;
3562
3563   /* Build cloog loop for all loops, that are in the uppermost loop layer of
3564      this SCoP.  */
3565   for (i = 0; VEC_iterate (loop_p, SCOP_LOOP_NEST (scop), i, loop); i++)
3566     if (!loop_in_scop_p (loop_outer (loop), scop))
3567       {
3568         /* The outermost constraints is a matrix that has:
3569            -first column: eq/ineq boolean
3570            -last column: a constant
3571            -scop_nb_params columns for the parameters used in the scop.  */
3572         outer_cstr = cloog_matrix_alloc (0, scop_nb_params (scop) + 2);
3573         build_loop_iteration_domains (scop, loop, outer_cstr, 0);
3574         cloog_matrix_free (outer_cstr);
3575       }
3576
3577   return (i != 0);
3578 }
3579
3580 /* Initializes an equation CY of the access matrix using the
3581    information for a subscript from AF, relatively to the loop
3582    indexes from LOOP_NEST and parameter indexes from PARAMS.  NDIM is
3583    the dimension of the array access, i.e. the number of
3584    subscripts.  Returns true when the operation succeeds.  */
3585
3586 static bool
3587 build_access_matrix_with_af (tree af, lambda_vector cy,
3588                              scop_p scop, int ndim)
3589 {
3590   int param_col;
3591
3592   switch (TREE_CODE (af))
3593     {
3594     case POLYNOMIAL_CHREC:
3595       {
3596         struct loop *outer_loop;
3597         tree left = CHREC_LEFT (af);
3598         tree right = CHREC_RIGHT (af);
3599         int var;
3600
3601         if (TREE_CODE (right) != INTEGER_CST)
3602           return false;
3603
3604         outer_loop = get_loop (CHREC_VARIABLE (af));
3605         var = nb_loops_around_loop_in_scop (outer_loop, scop);
3606         cy[var] = int_cst_value (right);
3607
3608         switch (TREE_CODE (left))
3609           {
3610           case POLYNOMIAL_CHREC:
3611             return build_access_matrix_with_af (left, cy, scop, ndim);
3612
3613           case INTEGER_CST:
3614             cy[ndim - 1] = int_cst_value (left);
3615             return true;
3616
3617           default:
3618             return build_access_matrix_with_af (left, cy, scop, ndim);
3619           }
3620       }
3621
3622     case PLUS_EXPR:
3623       build_access_matrix_with_af (TREE_OPERAND (af, 0), cy, scop, ndim);
3624       build_access_matrix_with_af (TREE_OPERAND (af, 1), cy, scop, ndim);
3625       return true;
3626
3627     case MINUS_EXPR:
3628       build_access_matrix_with_af (TREE_OPERAND (af, 0), cy, scop, ndim);
3629       build_access_matrix_with_af (TREE_OPERAND (af, 1), cy, scop, ndim);
3630       return true;
3631
3632     case INTEGER_CST:
3633       cy[ndim - 1] = int_cst_value (af);
3634       return true;
3635
3636     case SSA_NAME:
3637       param_col = param_index (af, scop);
3638       cy [ndim - scop_nb_params (scop) + param_col - 1] = 1;
3639       return true;
3640
3641     default:
3642       /* FIXME: access_fn can have parameters.  */
3643       return false;
3644     }
3645 }
3646
3647 /* Initialize the access matrix in the data reference REF with respect
3648    to the loop nesting LOOP_NEST.  Return true when the operation
3649    succeeded.  */
3650
3651 static bool
3652 build_access_matrix (data_reference_p ref, graphite_bb_p gb)
3653 {
3654   int i, ndim = DR_NUM_DIMENSIONS (ref);
3655   struct access_matrix *am = GGC_NEW (struct access_matrix);
3656
3657   AM_MATRIX (am) = VEC_alloc (lambda_vector, gc, ndim);
3658   DR_SCOP (ref) = GBB_SCOP (gb);
3659
3660   for (i = 0; i < ndim; i++)
3661     {
3662       lambda_vector v = lambda_vector_new (ref_nb_loops (ref));
3663       scop_p scop = GBB_SCOP (gb);
3664       tree af = DR_ACCESS_FN (ref, i);
3665
3666       if (!build_access_matrix_with_af (af, v, scop, ref_nb_loops (ref)))
3667         return false;
3668
3669       VEC_quick_push (lambda_vector, AM_MATRIX (am), v);
3670     }
3671
3672   DR_ACCESS_MATRIX (ref) = am;
3673   return true;
3674 }
3675
3676 /* Build the access matrices for the data references in the SCOP.  */
3677
3678 static void
3679 build_scop_data_accesses (scop_p scop)
3680 {
3681   int i;
3682   graphite_bb_p gb;
3683
3684   /* FIXME: Construction of access matrix is disabled until some
3685      pass, like the data dependence analysis, is using it.  */
3686   return;
3687
3688   for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
3689     {
3690       int j;
3691       data_reference_p dr;
3692
3693       /* Construct the access matrix for each data ref, with respect to
3694          the loop nest of the current BB in the considered SCOP.  */
3695       for (j = 0;
3696            VEC_iterate (data_reference_p, GBB_DATA_REFS (gb), j, dr);
3697            j++)
3698         {
3699           bool res = build_access_matrix (dr, gb);
3700
3701           /* FIXME: At this point the DRs should always have an affine
3702              form.  For the moment this fails as build_access_matrix
3703              does not build matrices with parameters.  */
3704           gcc_assert (res);
3705         }
3706     }
3707 }
3708
3709 /* Returns the tree variable from the name NAME that was given in
3710    Cloog representation.  All the parameters are stored in PARAMS, and
3711    all the loop induction variables are stored in IVSTACK.
3712
3713    FIXME: This is a hack, and Cloog should be fixed to not work with
3714    variable names represented as "char *string", but with void
3715    pointers that could be casted back to a tree.  The only problem in
3716    doing that is that Cloog's pretty printer still assumes that
3717    variable names are char *strings.  The solution would be to have a
3718    function pointer for pretty-printing that can be redirected to be
3719    print_generic_stmt in our case, or fprintf by default.
3720    ???  Too ugly to live.  */
3721
3722 static tree
3723 clast_name_to_gcc (const char *name, VEC (name_tree, heap) *params,
3724                    loop_iv_stack ivstack)
3725 {
3726   int i;
3727   name_tree t;
3728   tree iv;
3729
3730   if (params)
3731     for (i = 0; VEC_iterate (name_tree, params, i, t); i++)
3732       if (!strcmp (name, t->name))
3733         return t->t;
3734
3735   iv = loop_iv_stack_get_iv_from_name (ivstack, name);
3736   if (iv)
3737     return iv;
3738
3739   gcc_unreachable ();
3740 }
3741
3742 /* Returns the maximal precision type for expressions E1 and E2.  */
3743
3744 static inline tree
3745 max_precision_type (tree e1, tree e2)
3746 {
3747   tree type1 = TREE_TYPE (e1);
3748   tree type2 = TREE_TYPE (e2);
3749   return TYPE_PRECISION (type1) > TYPE_PRECISION (type2) ? type1 : type2;
3750 }
3751
3752 static tree
3753 clast_to_gcc_expression (tree, struct clast_expr *, VEC (name_tree, heap) *,
3754                          loop_iv_stack);
3755
3756 /* Converts a Cloog reduction expression R with reduction operation OP
3757    to a GCC expression tree of type TYPE.  PARAMS is a vector of
3758    parameters of the scop, and IVSTACK contains the stack of induction
3759    variables.  */
3760
3761 static tree
3762 clast_to_gcc_expression_red (tree type, enum tree_code op,
3763                              struct clast_reduction *r,
3764                              VEC (name_tree, heap) *params,
3765                              loop_iv_stack ivstack)
3766 {
3767   int i;
3768   tree res = clast_to_gcc_expression (type, r->elts[0], params, ivstack);
3769
3770   for (i = 1; i < r->n; i++)
3771     {
3772       tree t = clast_to_gcc_expression (type, r->elts[i], params, ivstack);
3773       res = fold_build2 (op, type, res, t);
3774     }
3775   return res;
3776 }
3777
3778 /* Converts a Cloog AST expression E back to a GCC expression tree of
3779    type TYPE.  PARAMS is a vector of parameters of the scop, and
3780    IVSTACK contains the stack of induction variables.  */
3781
3782 static tree
3783 clast_to_gcc_expression (tree type, struct clast_expr *e,
3784                          VEC (name_tree, heap) *params,
3785                          loop_iv_stack ivstack)
3786 {
3787   switch (e->type)
3788     {
3789     case expr_term:
3790       {
3791         struct clast_term *t = (struct clast_term *) e;
3792
3793         if (t->var)
3794           {
3795             if (value_one_p (t->val))
3796               {
3797                 tree name = clast_name_to_gcc (t->var, params, ivstack);
3798                 return fold_convert (type, name);
3799               }
3800
3801             else if (value_mone_p (t->val))
3802               {
3803                 tree name = clast_name_to_gcc (t->var, params, ivstack);
3804                 name = fold_convert (type, name);
3805                 return fold_build1 (NEGATE_EXPR, type, name);
3806               }
3807             else
3808               {
3809                 tree name = clast_name_to_gcc (t->var, params, ivstack);
3810                 tree cst = gmp_cst_to_tree (type, t->val);
3811                 name = fold_convert (type, name);
3812                 return fold_build2 (MULT_EXPR, type, cst, name);
3813               }
3814           }
3815         else
3816           return gmp_cst_to_tree (type, t->val);
3817       }
3818
3819     case expr_red:
3820       {
3821         struct clast_reduction *r = (struct clast_reduction *) e;
3822
3823         switch (r->type)
3824           {
3825           case clast_red_sum:
3826             return clast_to_gcc_expression_red (type, PLUS_EXPR, r, params, ivstack);
3827
3828           case clast_red_min:
3829             return clast_to_gcc_expression_red (type, MIN_EXPR, r, params, ivstack);
3830
3831           case clast_red_max:
3832             return clast_to_gcc_expression_red (type, MAX_EXPR, r, params, ivstack);
3833
3834           default:
3835             gcc_unreachable ();
3836           }
3837         break;
3838       }
3839
3840     case expr_bin:
3841       {
3842         struct clast_binary *b = (struct clast_binary *) e;
3843         struct clast_expr *lhs = (struct clast_expr *) b->LHS;
3844         tree tl = clast_to_gcc_expression (type, lhs, params, ivstack);
3845         tree tr = gmp_cst_to_tree (type, b->RHS);
3846
3847         switch (b->type)
3848           {
3849           case clast_bin_fdiv:
3850             return fold_build2 (FLOOR_DIV_EXPR, type, tl, tr);
3851
3852           case clast_bin_cdiv:
3853             return fold_build2 (CEIL_DIV_EXPR, type, tl, tr);
3854
3855           case clast_bin_div:
3856             return fold_build2 (EXACT_DIV_EXPR, type, tl, tr);
3857
3858           case clast_bin_mod:
3859             return fold_build2 (TRUNC_MOD_EXPR, type, tl, tr);
3860
3861           default:
3862             gcc_unreachable ();
3863           }
3864       }
3865
3866     default:
3867       gcc_unreachable ();
3868     }
3869
3870   return NULL_TREE;
3871 }
3872
3873 /* Returns the type for the expression E.  */
3874
3875 static tree
3876 gcc_type_for_clast_expr (struct clast_expr *e,
3877                          VEC (name_tree, heap) *params,
3878                          loop_iv_stack ivstack)
3879 {
3880   switch (e->type)
3881     {
3882     case expr_term:
3883       {
3884         struct clast_term *t = (struct clast_term *) e;
3885
3886         if (t->var)
3887           return TREE_TYPE (clast_name_to_gcc (t->var, params, ivstack));
3888         else
3889           return NULL_TREE;
3890       }
3891
3892     case expr_red:
3893       {
3894         struct clast_reduction *r = (struct clast_reduction *) e;
3895
3896         if (r->n == 1)
3897           return gcc_type_for_clast_expr (r->elts[0], params, ivstack);
3898         else
3899           {
3900             int i;
3901             for (i = 0; i < r->n; i++)
3902               {
3903                 tree type = gcc_type_for_clast_expr (r->elts[i], params, ivstack);
3904                 if (type)
3905                   return type;
3906               }
3907             return NULL_TREE;
3908           }
3909       }
3910
3911     case expr_bin:
3912       {
3913         struct clast_binary *b = (struct clast_binary *) e;
3914         struct clast_expr *lhs = (struct clast_expr *) b->LHS;
3915         return gcc_type_for_clast_expr (lhs, params, ivstack);
3916       }
3917
3918     default:
3919       gcc_unreachable ();
3920     }
3921
3922   return NULL_TREE;
3923 }
3924
3925 /* Returns the type for the equation CLEQ.  */
3926
3927 static tree
3928 gcc_type_for_clast_eq (struct clast_equation *cleq,
3929                        VEC (name_tree, heap) *params,
3930                        loop_iv_stack ivstack)
3931 {
3932   tree type = gcc_type_for_clast_expr (cleq->LHS, params, ivstack);
3933   if (type)
3934     return type;
3935
3936   return gcc_type_for_clast_expr (cleq->RHS, params, ivstack);
3937 }
3938
3939 /* Translates a clast equation CLEQ to a tree.  */
3940
3941 static tree
3942 graphite_translate_clast_equation (scop_p scop,
3943                                    struct clast_equation *cleq,
3944                                    loop_iv_stack ivstack)
3945 {
3946   enum tree_code comp;
3947   tree type = gcc_type_for_clast_eq (cleq, SCOP_PARAMS (scop), ivstack);
3948   tree lhs = clast_to_gcc_expression (type, cleq->LHS, SCOP_PARAMS (scop), ivstack);
3949   tree rhs = clast_to_gcc_expression (type, cleq->RHS, SCOP_PARAMS (scop), ivstack);
3950
3951   if (cleq->sign == 0)
3952     comp = EQ_EXPR;
3953
3954   else if (cleq->sign > 0)
3955     comp = GE_EXPR;
3956
3957   else
3958     comp = LE_EXPR;
3959
3960   return fold_build2 (comp, type, lhs, rhs);
3961 }
3962
3963 /* Creates the test for the condition in STMT.  */
3964
3965 static tree
3966 graphite_create_guard_cond_expr (scop_p scop, struct clast_guard *stmt,
3967                                  loop_iv_stack ivstack)
3968 {
3969   tree cond = NULL;
3970   int i;
3971
3972   for (i = 0; i < stmt->n; i++)
3973     {
3974       tree eq = graphite_translate_clast_equation (scop, &stmt->eq[i], ivstack);
3975
3976       if (cond)
3977         cond = fold_build2 (TRUTH_AND_EXPR, TREE_TYPE (eq), cond, eq);
3978       else
3979         cond = eq;
3980     }
3981
3982   return cond;
3983 }
3984
3985 /* Creates a new if region corresponding to Cloog's guard.  */
3986
3987 static edge
3988 graphite_create_new_guard (scop_p scop, edge entry_edge,
3989                            struct clast_guard *stmt,
3990                            loop_iv_stack ivstack)
3991 {
3992   tree cond_expr = graphite_create_guard_cond_expr (scop, stmt, ivstack);
3993   edge exit_edge = create_empty_if_region_on_edge (entry_edge, cond_expr);
3994   return exit_edge;
3995 }
3996
3997 /* Walks a CLAST and returns the first statement in the body of a
3998    loop.  */
3999
4000 static struct clast_user_stmt *
4001 clast_get_body_of_loop (struct clast_stmt *stmt)
4002 {
4003   if (!stmt
4004       || CLAST_STMT_IS_A (stmt, stmt_user))
4005     return (struct clast_user_stmt *) stmt;
4006
4007   if (CLAST_STMT_IS_A (stmt, stmt_for))
4008     return clast_get_body_of_loop (((struct clast_for *) stmt)->body);
4009
4010   if (CLAST_STMT_IS_A (stmt, stmt_guard))
4011     return clast_get_body_of_loop (((struct clast_guard *) stmt)->then);
4012
4013   if (CLAST_STMT_IS_A (stmt, stmt_block))
4014     return clast_get_body_of_loop (((struct clast_block *) stmt)->body);
4015
4016   gcc_unreachable ();
4017 }
4018
4019 /* Returns the induction variable for the loop that gets translated to
4020    STMT.  */
4021
4022 static tree
4023 gcc_type_for_iv_of_clast_loop (struct clast_for *stmt_for)
4024 {
4025   struct clast_user_stmt *stmt = clast_get_body_of_loop ((struct clast_stmt *) stmt_for);
4026   const char *cloog_iv = stmt_for->iterator;
4027   CloogStatement *cs = stmt->statement;
4028   graphite_bb_p gbb = (graphite_bb_p) cloog_statement_usr (cs);
4029
4030   return gcc_type_for_cloog_iv (cloog_iv, gbb);
4031 }
4032
4033 /* Creates a new LOOP corresponding to Cloog's STMT.  Inserts an induction
4034    variable for the new LOOP.  New LOOP is attached to CFG starting at
4035    ENTRY_EDGE.  LOOP is inserted into the loop tree and becomes the child
4036    loop of the OUTER_LOOP.  */
4037
4038 static struct loop *
4039 graphite_create_new_loop (scop_p scop, edge entry_edge,
4040                           struct clast_for *stmt, loop_iv_stack ivstack,
4041                           loop_p outer)
4042 {
4043   tree type = gcc_type_for_iv_of_clast_loop (stmt);
4044   VEC (name_tree, heap) *params = SCOP_PARAMS (scop);
4045   tree lb = clast_to_gcc_expression (type, stmt->LB, params, ivstack);
4046   tree ub = clast_to_gcc_expression (type, stmt->UB, params, ivstack);
4047   tree stride = gmp_cst_to_tree (type, stmt->stride);
4048   tree ivvar = create_tmp_var (type, "graphiteIV");
4049   tree iv_before;
4050   loop_p loop = create_empty_loop_on_edge
4051     (entry_edge, lb, stride, ub, ivvar, &iv_before,
4052      outer ? outer : entry_edge->src->loop_father);
4053
4054   add_referenced_var (ivvar);
4055   loop_iv_stack_push_iv (ivstack, iv_before, stmt->iterator);
4056   return loop;
4057 }
4058
4059 /* Rename the SSA_NAMEs used in STMT and that appear in IVSTACK.  */
4060
4061 static void
4062 rename_variables_in_stmt (gimple stmt, htab_t map)
4063 {
4064   ssa_op_iter iter;
4065   use_operand_p use_p;
4066
4067   FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
4068     {
4069       tree use = USE_FROM_PTR (use_p);
4070       tree new_name = get_new_name_from_old_name (map, use);
4071
4072       replace_exp (use_p, new_name);
4073     }
4074
4075   update_stmt (stmt);
4076 }
4077
4078 /* Returns true if SSA_NAME is a parameter of SCOP.  */
4079
4080 static bool
4081 is_parameter (scop_p scop, tree ssa_name)
4082 {
4083   int i;
4084   VEC (name_tree, heap) *params = SCOP_PARAMS (scop);
4085   name_tree param;
4086
4087   for (i = 0; VEC_iterate (name_tree, params, i, param); i++)
4088     if (param->t == ssa_name)
4089       return true;
4090
4091   return false;
4092 }
4093
4094 /* Returns true if NAME is an induction variable.  */
4095
4096 static bool
4097 is_iv (tree name)
4098 {
4099   return gimple_code (SSA_NAME_DEF_STMT (name)) == GIMPLE_PHI;
4100 }
4101
4102 static void expand_scalar_variables_stmt (gimple, basic_block, scop_p,
4103                                           htab_t);
4104 static tree
4105 expand_scalar_variables_expr (tree, tree, enum tree_code, tree, basic_block,
4106                               scop_p, htab_t, gimple_stmt_iterator *);
4107
4108 /* Copies at GSI all the scalar computations on which the ssa_name OP0
4109    depends on in the SCOP: these are all the scalar variables used in
4110    the definition of OP0, that are defined outside BB and still in the
4111    SCOP, i.e. not a parameter of the SCOP.  The expression that is
4112    returned contains only induction variables from the generated code:
4113    MAP contains the induction variables renaming mapping, and is used
4114    to translate the names of induction variables.  */
4115
4116 static tree
4117 expand_scalar_variables_ssa_name (tree op0, basic_block bb,
4118                                   scop_p scop, htab_t map,
4119                                   gimple_stmt_iterator *gsi)
4120 {
4121   tree var0, var1, type;
4122   gimple def_stmt;
4123   enum tree_code subcode;
4124
4125   if (is_parameter (scop, op0)
4126       || is_iv (op0))
4127     return get_new_name_from_old_name (map, op0);
4128
4129   def_stmt = SSA_NAME_DEF_STMT (op0);
4130
4131   if (gimple_bb (def_stmt) == bb)
4132     {
4133       /* If the defining statement is in the basic block already
4134          we do not need to create a new expression for it, we
4135          only need to ensure its operands are expanded.  */
4136       expand_scalar_variables_stmt (def_stmt, bb, scop, map);
4137       return get_new_name_from_old_name (map, op0);
4138     }
4139   else
4140     {
4141       if (gimple_code (def_stmt) != GIMPLE_ASSIGN
4142           || !bb_in_scop_p (gimple_bb (def_stmt), scop))
4143         return get_new_name_from_old_name (map, op0);
4144
4145       var0 = gimple_assign_rhs1 (def_stmt);
4146       subcode = gimple_assign_rhs_code (def_stmt);
4147       var1 = gimple_assign_rhs2 (def_stmt);
4148       type = gimple_expr_type (def_stmt);
4149
4150       return expand_scalar_variables_expr (type, var0, subcode, var1, bb, scop,
4151                                            map, gsi);
4152     }
4153 }
4154
4155 /* Copies at GSI all the scalar computations on which the expression
4156    OP0 CODE OP1 depends on in the SCOP: these are all the scalar
4157    variables used in OP0 and OP1, defined outside BB and still defined
4158    in the SCOP, i.e. not a parameter of the SCOP.  The expression that
4159    is returned contains only induction variables from the generated
4160    code: MAP contains the induction variables renaming mapping, and is
4161    used to translate the names of induction variables.  */
4162
4163 static tree
4164 expand_scalar_variables_expr (tree type, tree op0, enum tree_code code,
4165                               tree op1, basic_block bb, scop_p scop,
4166                               htab_t map, gimple_stmt_iterator *gsi)
4167 {
4168   if (TREE_CODE_CLASS (code) == tcc_constant
4169       || TREE_CODE_CLASS (code) == tcc_declaration)
4170     return op0;
4171
4172   /* For data references we have to duplicate also its memory
4173      indexing.  */
4174   if (TREE_CODE_CLASS (code) == tcc_reference)
4175     {
4176       switch (code)
4177         {
4178         case INDIRECT_REF:
4179           {
4180             tree old_name = TREE_OPERAND (op0, 0);
4181             tree expr = expand_scalar_variables_ssa_name
4182               (old_name, bb, scop, map, gsi);
4183             tree new_name = force_gimple_operand_gsi (gsi, expr, true, NULL,
4184                                                       true, GSI_SAME_STMT);
4185
4186             set_symbol_mem_tag (SSA_NAME_VAR (new_name),
4187                                 symbol_mem_tag (SSA_NAME_VAR (old_name)));
4188             return fold_build1 (code, type, new_name);
4189           }
4190
4191         case ARRAY_REF:
4192           {
4193             tree op00 = TREE_OPERAND (op0, 0);
4194             tree op01 = TREE_OPERAND (op0, 1);
4195             tree op02 = TREE_OPERAND (op0, 2);
4196             tree op03 = TREE_OPERAND (op0, 3);
4197             tree base = expand_scalar_variables_expr
4198               (TREE_TYPE (op00), op00, TREE_CODE (op00), NULL, bb, scop,
4199                map, gsi);
4200             tree subscript = expand_scalar_variables_expr
4201               (TREE_TYPE (op01), op01, TREE_CODE (op01), NULL, bb, scop,
4202                map, gsi);
4203
4204             return build4 (ARRAY_REF, type, base, subscript, op02, op03);
4205           }
4206
4207         default:
4208           /* The above cases should catch everything.  */
4209           gcc_unreachable ();
4210         }
4211     }
4212
4213   if (TREE_CODE_CLASS (code) == tcc_unary)
4214     {
4215       tree op0_type = TREE_TYPE (op0);
4216       enum tree_code op0_code = TREE_CODE (op0);
4217       tree op0_expr = expand_scalar_variables_expr (op0_type, op0, op0_code,
4218                                                     NULL, bb, scop, map, gsi);
4219
4220       return fold_build1 (code, type, op0_expr);
4221     }
4222
4223   if (TREE_CODE_CLASS (code) == tcc_binary)
4224     {
4225       tree op0_type = TREE_TYPE (op0);
4226       enum tree_code op0_code = TREE_CODE (op0);
4227       tree op0_expr = expand_scalar_variables_expr (op0_type, op0, op0_code,
4228                                                     NULL, bb, scop, map, gsi);
4229       tree op1_type = TREE_TYPE (op1);
4230       enum tree_code op1_code = TREE_CODE (op1);
4231       tree op1_expr = expand_scalar_variables_expr (op1_type, op1, op1_code,
4232                                                     NULL, bb, scop, map, gsi);
4233
4234       return fold_build2 (code, type, op0_expr, op1_expr);
4235     }
4236
4237   if (code == SSA_NAME)
4238     return expand_scalar_variables_ssa_name (op0, bb, scop, map, gsi);
4239
4240   gcc_unreachable ();
4241   return NULL;
4242 }
4243
4244 /* Copies at the beginning of BB all the scalar computations on which
4245    STMT depends on in the SCOP: these are all the scalar variables used
4246    in STMT, defined outside BB and still defined in the SCOP, i.e. not a
4247    parameter of the SCOP.  The expression that is returned contains
4248    only induction variables from the generated code: MAP contains the
4249    induction variables renaming mapping, and is used to translate the
4250    names of induction variables.  */
4251
4252 static void
4253 expand_scalar_variables_stmt (gimple stmt, basic_block bb, scop_p scop,
4254                               htab_t map)
4255 {
4256   ssa_op_iter iter;
4257   use_operand_p use_p;
4258   gimple_stmt_iterator gsi = gsi_after_labels (bb);
4259
4260   FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
4261     {
4262       tree use = USE_FROM_PTR (use_p);
4263       tree type = TREE_TYPE (use);
4264       enum tree_code code = TREE_CODE (use);
4265       tree use_expr = expand_scalar_variables_expr (type, use, code, NULL, bb,
4266                                                     scop, map, &gsi);
4267       if (use_expr != use)
4268         {
4269           tree new_use =
4270             force_gimple_operand_gsi (&gsi, use_expr, true, NULL,
4271                                       true, GSI_NEW_STMT);
4272           replace_exp (use_p, new_use);
4273         }
4274     }
4275
4276   update_stmt (stmt);
4277 }
4278
4279 /* Copies at the beginning of BB all the scalar computations on which
4280    BB depends on in the SCOP: these are all the scalar variables used
4281    in BB, defined outside BB and still defined in the SCOP, i.e. not a
4282    parameter of the SCOP.  The expression that is returned contains
4283    only induction variables from the generated code: MAP contains the
4284    induction variables renaming mapping, and is used to translate the
4285    names of induction variables.  */
4286
4287 static void
4288 expand_scalar_variables (basic_block bb, scop_p scop, htab_t map)
4289 {
4290   gimple_stmt_iterator gsi;
4291
4292   for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi);)
4293     {
4294       gimple stmt = gsi_stmt (gsi);
4295       expand_scalar_variables_stmt (stmt, bb, scop, map);
4296       gsi_next (&gsi);
4297     }
4298 }
4299
4300 /* Rename all the SSA_NAMEs from block BB according to the MAP.  */
4301
4302 static void
4303 rename_variables (basic_block bb, htab_t map)
4304 {
4305   gimple_stmt_iterator gsi;
4306
4307   for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi); gsi_next (&gsi))
4308     rename_variables_in_stmt (gsi_stmt (gsi), map);
4309 }
4310
4311 /* Remove condition from BB.  */
4312
4313 static void
4314 remove_condition (basic_block bb)
4315 {
4316   gimple last = last_stmt (bb);
4317
4318   if (last && gimple_code (last) == GIMPLE_COND)
4319     {
4320       gimple_stmt_iterator gsi = gsi_last_bb (bb);
4321       gsi_remove (&gsi, true);
4322     }
4323 }
4324
4325 /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag set.  */
4326
4327 static edge
4328 get_true_edge_from_guard_bb (basic_block bb)
4329 {
4330   edge e;
4331   edge_iterator ei;
4332
4333   FOR_EACH_EDGE (e, ei, bb->succs)
4334     if (e->flags & EDGE_TRUE_VALUE)
4335       return e;
4336
4337   gcc_unreachable ();
4338   return NULL;
4339 }
4340
4341 /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag cleared.  */
4342
4343 static edge
4344 get_false_edge_from_guard_bb (basic_block bb)
4345 {
4346   edge e;
4347   edge_iterator ei;
4348
4349   FOR_EACH_EDGE (e, ei, bb->succs)
4350     if (!(e->flags & EDGE_TRUE_VALUE))
4351       return e;
4352
4353   gcc_unreachable ();
4354   return NULL;
4355 }
4356
4357 /* Inserts in MAP a tuple (OLD_NAME, NEW_NAME) for the induction
4358    variables of the loops around GBB in SCOP, i.e. GBB_LOOPS.
4359    NEW_NAME is obtained from IVSTACK.  IVSTACK has the same stack
4360    ordering as GBB_LOOPS.  */
4361
4362 static void
4363 build_iv_mapping (loop_iv_stack ivstack, htab_t map, gbb_p gbb, scop_p scop)
4364 {
4365   int i;
4366   name_tree iv;
4367   PTR *slot;
4368
4369   for (i = 0; VEC_iterate (name_tree, SCOP_OLDIVS (scop), i, iv); i++)
4370     {
4371       struct rename_map_elt tmp;
4372
4373       if (!flow_bb_inside_loop_p (iv->loop, GBB_BB (gbb)))
4374         continue;
4375
4376       tmp.old_name = iv->t;
4377       slot = htab_find_slot (map, &tmp, INSERT);
4378
4379       if (!*slot)
4380         {
4381           tree new_name = loop_iv_stack_get_iv (ivstack,
4382                                                 gbb_loop_index (gbb, iv->loop));
4383           *slot = new_rename_map_elt (iv->t, new_name);
4384         }
4385     }
4386 }
4387
4388 /* Register in MAP the tuple (old_name, new_name).  */
4389
4390 static void
4391 register_old_and_new_names (htab_t map, tree old_name, tree new_name)
4392 {
4393   struct rename_map_elt tmp;
4394   PTR *slot;
4395
4396   tmp.old_name = old_name;
4397   slot = htab_find_slot (map, &tmp, INSERT);
4398
4399   if (!*slot)
4400     *slot = new_rename_map_elt (old_name, new_name);
4401 }
4402
4403 /* Create a duplicate of the basic block BB.  NOTE: This does not
4404    preserve SSA form.  */
4405
4406 static void
4407 graphite_copy_stmts_from_block (basic_block bb, basic_block new_bb, htab_t map)
4408 {
4409   gimple_stmt_iterator gsi, gsi_tgt;
4410
4411   gsi_tgt = gsi_start_bb (new_bb);
4412   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
4413     {
4414       def_operand_p def_p;
4415       ssa_op_iter op_iter;
4416       int region;
4417       gimple stmt = gsi_stmt (gsi);
4418       gimple copy;
4419
4420       if (gimple_code (stmt) == GIMPLE_LABEL)
4421         continue;
4422
4423       /* Create a new copy of STMT and duplicate STMT's virtual
4424          operands.  */
4425       copy = gimple_copy (stmt);
4426       gsi_insert_after (&gsi_tgt, copy, GSI_NEW_STMT);
4427       mark_symbols_for_renaming (copy);
4428
4429       region = lookup_stmt_eh_region (stmt);
4430       if (region >= 0)
4431         add_stmt_to_eh_region (copy, region);
4432       gimple_duplicate_stmt_histograms (cfun, copy, cfun, stmt);
4433
4434       /* Create new names for all the definitions created by COPY and
4435          add replacement mappings for each new name.  */
4436       FOR_EACH_SSA_DEF_OPERAND (def_p, copy, op_iter, SSA_OP_DEF)
4437         {
4438           tree old_name = DEF_FROM_PTR (def_p);
4439           tree new_name = create_new_def_for (old_name, copy, def_p);
4440           register_old_and_new_names (map, old_name, new_name);
4441         }
4442     }
4443 }
4444
4445 /* Records in SCOP_LIVEOUT_RENAMES the names that are live out of
4446    the SCOP and that appear in the RENAME_MAP.  */
4447
4448 static void
4449 register_scop_liveout_renames (scop_p scop, htab_t rename_map)
4450 {
4451   int i;
4452   sese region = SCOP_REGION (scop);
4453
4454   for (i = 0; i < SESE_NUM_VER (region); i++)
4455     if (bitmap_bit_p (SESE_LIVEOUT (region), i)
4456         && is_gimple_reg (ssa_name (i)))
4457       {
4458         tree old_name = ssa_name (i);
4459         tree new_name = get_new_name_from_old_name (rename_map, old_name);
4460
4461         register_old_and_new_names (SCOP_LIVEOUT_RENAMES (scop),
4462                                     old_name, new_name);
4463       }
4464 }
4465
4466 /* Copies BB and includes in the copied BB all the statements that can
4467    be reached following the use-def chains from the memory accesses,
4468    and returns the next edge following this new block.  */
4469
4470 static edge
4471 copy_bb_and_scalar_dependences (basic_block bb, scop_p scop,
4472                                 edge next_e, htab_t map)
4473 {
4474   basic_block new_bb = split_edge (next_e);
4475
4476   next_e = single_succ_edge (new_bb);
4477   graphite_copy_stmts_from_block (bb, new_bb, map);
4478   remove_condition (new_bb);
4479   rename_variables (new_bb, map);
4480   remove_phi_nodes (new_bb);
4481   expand_scalar_variables (new_bb, scop, map);
4482   register_scop_liveout_renames (scop, map);
4483
4484   return next_e;
4485 }
4486
4487 /* Helper function for htab_traverse in insert_loop_close_phis.  */
4488
4489 static int
4490 add_loop_exit_phis (void **slot, void *s)
4491 {
4492   struct rename_map_elt *entry = (struct rename_map_elt *) *slot;
4493   tree new_name = entry->new_name;
4494   basic_block bb = (basic_block) s;
4495   gimple phi = create_phi_node (new_name, bb);
4496   tree res = create_new_def_for (gimple_phi_result (phi), phi,
4497                                  gimple_phi_result_ptr (phi));
4498
4499   add_phi_arg (phi, new_name, single_pred_edge (bb));
4500
4501   entry->new_name = res;
4502   *slot = entry;
4503   return 1;
4504 }
4505
4506 /* Iterate over the SCOP_LIVEOUT_RENAMES (SCOP) and get tuples of the
4507    form (OLD_NAME, NEW_NAME).  Insert in BB "RES = phi (NEW_NAME)",
4508    and finally register in SCOP_LIVEOUT_RENAMES (scop) the tuple
4509    (OLD_NAME, RES).  */
4510
4511 static void
4512 insert_loop_close_phis (scop_p scop, basic_block bb)
4513 {
4514   update_ssa (TODO_update_ssa);
4515   htab_traverse (SCOP_LIVEOUT_RENAMES (scop), add_loop_exit_phis, bb);
4516   update_ssa (TODO_update_ssa);
4517 }
4518
4519 /* Helper structure for htab_traverse in insert_guard_phis.  */
4520
4521 struct igp {
4522   basic_block bb;
4523   edge true_edge, false_edge;
4524   htab_t liveout_before_guard;
4525 };
4526
4527 /* Return the default name that is before the guard.  */
4528
4529 static tree
4530 default_liveout_before_guard (htab_t liveout_before_guard, tree old_name)
4531 {
4532   tree res = get_new_name_from_old_name (liveout_before_guard, old_name);
4533
4534   if (res == old_name)
4535     {
4536       if (is_gimple_reg (res))
4537         return fold_convert (TREE_TYPE (res), integer_zero_node);
4538       return gimple_default_def (cfun, res);
4539     }
4540
4541   return res;
4542 }
4543
4544 /* Helper function for htab_traverse in insert_guard_phis.  */
4545
4546 static int
4547 add_guard_exit_phis (void **slot, void *s)
4548 {
4549   struct rename_map_elt *entry = (struct rename_map_elt *) *slot;
4550   struct igp *i = (struct igp *) s;
4551   basic_block bb = i->bb;
4552   edge true_edge = i->true_edge;
4553   edge false_edge = i->false_edge;
4554   tree name1 = entry->new_name;
4555   tree name2 = default_liveout_before_guard (i->liveout_before_guard,
4556                                              entry->old_name);
4557   gimple phi = create_phi_node (name1, bb);
4558   tree res = create_new_def_for (gimple_phi_result (phi), phi,
4559                                  gimple_phi_result_ptr (phi));
4560
4561   add_phi_arg (phi, name1, true_edge);
4562   add_phi_arg (phi, name2, false_edge);
4563
4564   entry->new_name = res;
4565   *slot = entry;
4566   return 1;
4567 }
4568
4569 /* Iterate over the SCOP_LIVEOUT_RENAMES (SCOP) and get tuples of the
4570    form (OLD_NAME, NAME1).  If there is a correspondent tuple of
4571    OLD_NAME in LIVEOUT_BEFORE_GUARD, i.e. (OLD_NAME, NAME2) then
4572    insert in BB
4573
4574    | RES = phi (NAME1 (on TRUE_EDGE), NAME2 (on FALSE_EDGE))"
4575
4576    if there is no tuple for OLD_NAME in LIVEOUT_BEFORE_GUARD, insert
4577
4578    | RES = phi (NAME1 (on TRUE_EDGE),
4579    |            DEFAULT_DEFINITION of NAME1 (on FALSE_EDGE))".
4580
4581    Finally register in SCOP_LIVEOUT_RENAMES (scop) the tuple
4582    (OLD_NAME, RES).  */
4583
4584 static void
4585 insert_guard_phis (scop_p scop, basic_block bb, edge true_edge,
4586                    edge false_edge, htab_t liveout_before_guard)
4587 {
4588   struct igp i;
4589   i.bb = bb;
4590   i.true_edge = true_edge;
4591   i.false_edge = false_edge;
4592   i.liveout_before_guard = liveout_before_guard;
4593
4594   update_ssa (TODO_update_ssa);
4595   htab_traverse (SCOP_LIVEOUT_RENAMES (scop), add_guard_exit_phis, &i);
4596   update_ssa (TODO_update_ssa);
4597 }
4598
4599 /* Helper function for htab_traverse.  */
4600
4601 static int
4602 copy_renames (void **slot, void *s)
4603 {
4604   struct rename_map_elt *entry = (struct rename_map_elt *) *slot;
4605   htab_t res = (htab_t) s;
4606   tree old_name = entry->old_name;
4607   tree new_name = entry->new_name;
4608   struct rename_map_elt tmp;
4609   PTR *x;
4610
4611   tmp.old_name = old_name;
4612   x = htab_find_slot (res, &tmp, INSERT);
4613
4614   if (!*x)
4615     *x = new_rename_map_elt (old_name, new_name);
4616
4617   return 1;
4618 }
4619
4620 /* Translates a CLAST statement STMT to GCC representation in the
4621    context of a SCOP.
4622
4623    - NEXT_E is the edge where new generated code should be attached.
4624    - CONTEXT_LOOP is the loop in which the generated code will be placed
4625      (might be NULL).
4626    - IVSTACK contains the surrounding loops around the statement to be
4627      translated.
4628 */
4629
4630 static edge
4631 translate_clast (scop_p scop, struct loop *context_loop,
4632                  struct clast_stmt *stmt, edge next_e, loop_iv_stack ivstack)
4633 {
4634   if (!stmt)
4635     return next_e;
4636
4637   if (CLAST_STMT_IS_A (stmt, stmt_root))
4638     return translate_clast (scop, context_loop, stmt->next, next_e, ivstack);
4639
4640   if (CLAST_STMT_IS_A (stmt, stmt_user))
4641     {
4642       htab_t map;
4643       CloogStatement *cs = ((struct clast_user_stmt *) stmt)->statement;
4644       graphite_bb_p gbb = (graphite_bb_p) cloog_statement_usr (cs);
4645
4646       if (GBB_BB (gbb) == ENTRY_BLOCK_PTR)
4647         return next_e;
4648
4649       map = htab_create (10, rename_map_elt_info, eq_rename_map_elts, free);
4650       loop_iv_stack_patch_for_consts (ivstack, (struct clast_user_stmt *) stmt);
4651       build_iv_mapping (ivstack, map, gbb, scop);
4652       next_e = copy_bb_and_scalar_dependences (GBB_BB (gbb), scop,
4653                                                next_e, map);
4654       htab_delete (map);
4655       loop_iv_stack_remove_constants (ivstack);
4656       update_ssa (TODO_update_ssa);
4657       recompute_all_dominators ();
4658       graphite_verify ();
4659       return translate_clast (scop, context_loop, stmt->next, next_e, ivstack);
4660     }
4661
4662   if (CLAST_STMT_IS_A (stmt, stmt_for))
4663     {
4664       struct loop *loop
4665         = graphite_create_new_loop (scop, next_e, (struct clast_for *) stmt,
4666                                     ivstack, context_loop ? context_loop
4667                                     : get_loop (0));
4668       edge last_e = single_exit (loop);
4669
4670       next_e = translate_clast (scop, loop, ((struct clast_for *) stmt)->body,
4671                                 single_pred_edge (loop->latch), ivstack);
4672       redirect_edge_succ_nodup (next_e, loop->latch);
4673
4674       set_immediate_dominator (CDI_DOMINATORS, next_e->dest, next_e->src);
4675       loop_iv_stack_pop (ivstack);
4676       last_e = single_succ_edge (split_edge (last_e));
4677       insert_loop_close_phis (scop, last_e->src);
4678
4679       recompute_all_dominators ();
4680       graphite_verify ();
4681       return translate_clast (scop, context_loop, stmt->next, last_e, ivstack);
4682     }
4683
4684   if (CLAST_STMT_IS_A (stmt, stmt_guard))
4685     {
4686       htab_t liveout_before_guard = htab_create (10, rename_map_elt_info,
4687                                                  eq_rename_map_elts, free);
4688       edge last_e = graphite_create_new_guard (scop, next_e,
4689                                                ((struct clast_guard *) stmt),
4690                                                ivstack);
4691       edge true_e = get_true_edge_from_guard_bb (next_e->dest);
4692       edge false_e = get_false_edge_from_guard_bb (next_e->dest);
4693       edge exit_true_e = single_succ_edge (true_e->dest);
4694       edge exit_false_e = single_succ_edge (false_e->dest);
4695
4696       htab_traverse (SCOP_LIVEOUT_RENAMES (scop), copy_renames,
4697                      liveout_before_guard);
4698
4699       next_e = translate_clast (scop, context_loop,
4700                                 ((struct clast_guard *) stmt)->then,
4701                                 true_e, ivstack);
4702       insert_guard_phis (scop, last_e->src, exit_true_e, exit_false_e,
4703                          liveout_before_guard);
4704       htab_delete (liveout_before_guard);
4705       recompute_all_dominators ();
4706       graphite_verify ();
4707
4708       return translate_clast (scop, context_loop, stmt->next, last_e, ivstack);
4709     }
4710
4711   if (CLAST_STMT_IS_A (stmt, stmt_block))
4712     {
4713       next_e = translate_clast (scop, context_loop,
4714                                 ((struct clast_block *) stmt)->body,
4715                                 next_e, ivstack);
4716       recompute_all_dominators ();
4717       graphite_verify ();
4718       return translate_clast (scop, context_loop, stmt->next, next_e, ivstack);
4719     }
4720
4721   gcc_unreachable ();
4722 }
4723
4724 /* Free the SCATTERING domain list.  */
4725
4726 static void
4727 free_scattering (CloogDomainList *scattering)
4728 {
4729   while (scattering)
4730     {
4731       CloogDomain *dom = cloog_domain (scattering);
4732       CloogDomainList *next = cloog_next_domain (scattering);
4733
4734       cloog_domain_free (dom);
4735       free (scattering);
4736       scattering = next;
4737     }
4738 }
4739
4740 /* Build cloog program for SCoP.  */
4741
4742 static void
4743 build_cloog_prog (scop_p scop)
4744 {
4745   int i;
4746   int max_nb_loops = scop_max_loop_depth (scop);
4747   graphite_bb_p gbb;
4748   CloogLoop *loop_list = NULL;
4749   CloogBlockList *block_list = NULL;
4750   CloogDomainList *scattering = NULL;
4751   CloogProgram *prog = SCOP_PROG (scop);
4752   int nbs = 2 * max_nb_loops + 1;
4753   int *scaldims = (int *) xmalloc (nbs * (sizeof (int)));
4754
4755   cloog_program_set_nb_scattdims (prog, nbs);
4756   initialize_cloog_names (scop);
4757
4758   for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gbb); i++)
4759     {
4760       /* Build new block.  */
4761       CloogMatrix *domain = GBB_DOMAIN (gbb);
4762       CloogStatement *stmt = cloog_statement_alloc (GBB_BB (gbb)->index);
4763       CloogBlock *block = cloog_block_alloc (stmt, 0, NULL,
4764                                              nb_loops_around_gb (gbb));
4765       cloog_statement_set_usr (stmt, gbb);
4766
4767       /* Add empty domain to all bbs, which do not yet have a domain, as they
4768          are not part of any loop.  */
4769       if (domain == NULL)
4770         {
4771           domain = cloog_matrix_alloc (0, scop_nb_params (scop) + 2);
4772           GBB_DOMAIN (gbb) = domain;
4773         }
4774
4775       /* Build loop list.  */
4776       {
4777         CloogLoop *new_loop_list = cloog_loop_malloc ();
4778         cloog_loop_set_next (new_loop_list, loop_list);
4779         cloog_loop_set_domain (new_loop_list,
4780                                cloog_domain_matrix2domain (domain));
4781         cloog_loop_set_block (new_loop_list, block);
4782         loop_list = new_loop_list;
4783       }
4784
4785       /* Build block list.  */
4786       {
4787         CloogBlockList *new_block_list = cloog_block_list_malloc ();
4788
4789         cloog_block_list_set_next (new_block_list, block_list);
4790         cloog_block_list_set_block (new_block_list, block);
4791         block_list = new_block_list;
4792       }
4793
4794       /* Build scattering list.  */
4795       {
4796         /* XXX: Replace with cloog_domain_list_alloc(), when available.  */
4797         CloogDomainList *new_scattering
4798           = (CloogDomainList *) xmalloc (sizeof (CloogDomainList));
4799         CloogMatrix *scat_mat = schedule_to_scattering (gbb, nbs);
4800
4801         cloog_set_next_domain (new_scattering, scattering);
4802         cloog_set_domain (new_scattering,
4803                           cloog_domain_matrix2domain (scat_mat));
4804         scattering = new_scattering;
4805         cloog_matrix_free (scat_mat);
4806       }
4807     }
4808
4809   cloog_program_set_loop (prog, loop_list);
4810   cloog_program_set_blocklist (prog, block_list);
4811
4812   for (i = 0; i < nbs; i++)
4813     scaldims[i] = 0 ;
4814
4815   cloog_program_set_scaldims (prog, scaldims);
4816
4817   /* Extract scalar dimensions to simplify the code generation problem.  */
4818   cloog_program_extract_scalars (prog, scattering);
4819
4820   /* Apply scattering.  */
4821   cloog_program_scatter (prog, scattering);
4822   free_scattering (scattering);
4823
4824   /* Iterators corresponding to scalar dimensions have to be extracted.  */
4825   cloog_names_scalarize (cloog_program_names (prog), nbs,
4826                          cloog_program_scaldims (prog));
4827
4828   /* Free blocklist.  */
4829   {
4830     CloogBlockList *next = cloog_program_blocklist (prog);
4831
4832     while (next)
4833       {
4834         CloogBlockList *toDelete = next;
4835         next = cloog_block_list_next (next);
4836         cloog_block_list_set_next (toDelete, NULL);
4837         cloog_block_list_set_block (toDelete, NULL);
4838         cloog_block_list_free (toDelete);
4839       }
4840     cloog_program_set_blocklist (prog, NULL);
4841   }
4842 }
4843
4844 /* Return the options that will be used in GLOOG.  */
4845
4846 static CloogOptions *
4847 set_cloog_options (void)
4848 {
4849   CloogOptions *options = cloog_options_malloc ();
4850
4851   /* Change cloog output language to C.  If we do use FORTRAN instead, cloog
4852      will stop e.g. with "ERROR: unbounded loops not allowed in FORTRAN.", if
4853      we pass an incomplete program to cloog.  */
4854   options->language = LANGUAGE_C;
4855
4856   /* Enable complex equality spreading: removes dummy statements
4857      (assignments) in the generated code which repeats the
4858      substitution equations for statements.  This is useless for
4859      GLooG.  */
4860   options->esp = 1;
4861
4862   /* Enable C pretty-printing mode: normalizes the substitution
4863      equations for statements.  */
4864   options->cpp = 1;
4865
4866   /* Allow cloog to build strides with a stride width different to one.
4867      This example has stride = 4:
4868
4869      for (i = 0; i < 20; i += 4)
4870        A  */
4871   options->strides = 1;
4872
4873   /* Disable optimizations and make cloog generate source code closer to the
4874      input.  This is useful for debugging,  but later we want the optimized
4875      code.
4876
4877      XXX: We can not disable optimizations, as loop blocking is not working
4878      without them.  */
4879   if (0)
4880     {
4881       options->f = -1;
4882       options->l = INT_MAX;
4883     }
4884
4885   return options;
4886 }
4887
4888 /* Prints STMT to STDERR.  */
4889
4890 void
4891 debug_clast_stmt (struct clast_stmt *stmt)
4892 {
4893   CloogOptions *options = set_cloog_options ();
4894
4895   pprint (stderr, stmt, 0, options);
4896 }
4897
4898 /* Find the right transform for the SCOP, and return a Cloog AST
4899    representing the new form of the program.  */
4900
4901 static struct clast_stmt *
4902 find_transform (scop_p scop)
4903 {
4904   struct clast_stmt *stmt;
4905   CloogOptions *options = set_cloog_options ();
4906
4907   /* Connect new cloog prog generation to graphite.  */
4908   build_cloog_prog (scop);
4909
4910   if (dump_file && (dump_flags & TDF_DETAILS))
4911     {
4912       fprintf (dump_file, "Cloog Input [\n");
4913       cloog_program_print (dump_file, SCOP_PROG(scop));
4914       fprintf (dump_file, "]\n");
4915     }
4916
4917   SCOP_PROG (scop) = cloog_program_generate (SCOP_PROG (scop), options);
4918   stmt = cloog_clast_create (SCOP_PROG (scop), options);
4919
4920   if (dump_file && (dump_flags & TDF_DETAILS))
4921     {
4922       fprintf (dump_file, "Cloog Output[\n");
4923       pprint (dump_file, stmt, 0, options);
4924       cloog_program_dump_cloog (dump_file, SCOP_PROG (scop));
4925       fprintf (dump_file, "]\n");
4926     }
4927
4928   cloog_options_free (options);
4929   return stmt;
4930 }
4931
4932 /* Remove from the CFG the REGION.  */
4933
4934 static inline void
4935 remove_sese_region (sese region)
4936 {
4937   VEC (basic_block, heap) *bbs = NULL;
4938   basic_block entry_bb = SESE_ENTRY (region)->dest;
4939   basic_block exit_bb = SESE_EXIT (region)->dest;
4940   basic_block bb;
4941   int i;
4942
4943   VEC_safe_push (basic_block, heap, bbs, entry_bb);
4944   gather_blocks_in_sese_region (entry_bb, exit_bb, &bbs);
4945
4946   for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++)
4947     delete_basic_block (bb);
4948
4949   VEC_free (basic_block, heap, bbs);
4950 }
4951
4952 typedef struct ifsese {
4953   sese region;
4954   sese true_region;
4955   sese false_region;
4956 } *ifsese;
4957
4958 static inline edge
4959 if_region_entry (ifsese if_region)
4960 {
4961   return SESE_ENTRY (if_region->region);
4962 }
4963
4964 static inline edge
4965 if_region_exit (ifsese if_region)
4966 {
4967   return SESE_EXIT (if_region->region);
4968 }
4969
4970 static inline basic_block
4971 if_region_get_condition_block (ifsese if_region)
4972 {
4973   return if_region_entry (if_region)->dest;
4974 }
4975
4976 static inline void
4977 if_region_set_false_region (ifsese if_region, sese region)
4978 {
4979   basic_block condition = if_region_get_condition_block (if_region);
4980   edge false_edge = get_false_edge_from_guard_bb (condition);
4981   edge entry_region = SESE_ENTRY (region);
4982   edge exit_region = SESE_EXIT (region);
4983   basic_block before_region = entry_region->src;
4984   basic_block last_in_region = exit_region->src;
4985   void **slot = htab_find_slot_with_hash (current_loops->exits, exit_region,
4986                                           htab_hash_pointer (exit_region),
4987                                           NO_INSERT);
4988
4989   entry_region->flags = false_edge->flags;
4990   false_edge->flags = exit_region->flags;
4991
4992   redirect_edge_pred (entry_region, condition);
4993   redirect_edge_pred (exit_region, before_region);
4994   redirect_edge_pred (false_edge, last_in_region);
4995
4996   exit_region->flags = EDGE_FALLTHRU;
4997   recompute_all_dominators ();
4998
4999   SESE_EXIT (region) = single_succ_edge (false_edge->dest);
5000   if_region->false_region = region;
5001
5002   if (slot)
5003     {
5004       struct loop_exit *loop_exit = GGC_CNEW (struct loop_exit);
5005
5006       memcpy (loop_exit, *((struct loop_exit **) slot), sizeof (struct loop_exit));
5007       htab_clear_slot (current_loops->exits, slot);
5008
5009       slot = htab_find_slot_with_hash (current_loops->exits, false_edge,
5010                                        htab_hash_pointer (false_edge),
5011                                        INSERT);
5012       loop_exit->e = false_edge;
5013       *slot = loop_exit;
5014       false_edge->src->loop_father->exits->next = loop_exit;
5015     }
5016 }
5017
5018 static ifsese
5019 create_if_region_on_edge (edge entry, tree condition)
5020 {
5021   edge e;
5022   edge_iterator ei;
5023   sese sese_region = GGC_NEW (struct sese);
5024   sese true_region = GGC_NEW (struct sese);
5025   sese false_region = GGC_NEW (struct sese);
5026   ifsese if_region = GGC_NEW (struct ifsese);
5027   edge exit = create_empty_if_region_on_edge (entry, condition);
5028
5029   if_region->region = sese_region;
5030   if_region->region->entry = entry;
5031   if_region->region->exit = exit;
5032
5033   FOR_EACH_EDGE (e, ei, entry->dest->succs)
5034     {
5035       if (e->flags & EDGE_TRUE_VALUE)
5036         {
5037           true_region->entry = e;
5038           true_region->exit = single_succ_edge (e->dest);
5039           if_region->true_region = true_region;
5040         }
5041       else if (e->flags & EDGE_FALSE_VALUE)
5042         {
5043           false_region->entry = e;
5044           false_region->exit = single_succ_edge (e->dest);
5045           if_region->false_region = false_region;
5046         }
5047     }
5048
5049   return if_region;
5050 }
5051
5052 /* Moves REGION in a condition expression:
5053    | if (1)
5054    |   ;
5055    | else
5056    |   REGION;
5057 */
5058
5059 static ifsese
5060 move_sese_in_condition (sese region)
5061 {
5062   basic_block pred_block = split_edge (SESE_ENTRY (region));
5063   ifsese if_region = NULL;
5064
5065   SESE_ENTRY (region) = single_succ_edge (pred_block);
5066   if_region = create_if_region_on_edge (single_pred_edge (pred_block), integer_one_node);
5067   if_region_set_false_region (if_region, region);
5068
5069   return if_region;
5070 }
5071
5072 /* Add exit phis for USE on EXIT.  */
5073
5074 static void
5075 scop_add_exit_phis_edge (basic_block exit, tree use, edge false_e, edge true_e)
5076 {
5077   gimple phi = create_phi_node (use, exit);
5078
5079   create_new_def_for (gimple_phi_result (phi), phi,
5080                       gimple_phi_result_ptr (phi));
5081   add_phi_arg (phi, use, false_e);
5082   add_phi_arg (phi, use, true_e);
5083 }
5084
5085 /* Add phi nodes for VAR that is used in LIVEIN.  Phi nodes are
5086    inserted in block BB.  */
5087
5088 static void
5089 scop_add_exit_phis_var (basic_block bb, tree var, bitmap livein,
5090                         edge false_e, edge true_e)
5091 {
5092   bitmap def;
5093   basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (var));
5094
5095   if (is_gimple_reg (var))
5096     bitmap_clear_bit (livein, def_bb->index);
5097   else
5098     bitmap_set_bit (livein, def_bb->index);
5099
5100   def = BITMAP_ALLOC (NULL);
5101   bitmap_set_bit (def, def_bb->index);
5102   compute_global_livein (livein, def);
5103   BITMAP_FREE (def);
5104
5105   scop_add_exit_phis_edge (bb, var, false_e, true_e);
5106 }
5107
5108 /* Insert in the block BB phi nodes for variables defined in REGION
5109    and used outside the REGION.  The code generation moves REGION in
5110    the else clause of an "if (1)" and generates code in the then
5111    clause that is at this point empty:
5112
5113    | if (1)
5114    |   empty;
5115    | else
5116    |   REGION;
5117 */
5118
5119 static void
5120 scop_insert_phis_for_liveouts (sese region, basic_block bb,
5121                                edge false_e, edge true_e)
5122 {
5123   unsigned i;
5124   bitmap_iterator bi;
5125
5126   update_ssa (TODO_update_ssa);
5127
5128   EXECUTE_IF_SET_IN_BITMAP (SESE_LIVEOUT (region), 0, i, bi)
5129     scop_add_exit_phis_var (bb, ssa_name (i), SESE_LIVEIN_VER (region, i),
5130                             false_e, true_e);
5131
5132   update_ssa (TODO_update_ssa);
5133 }
5134
5135 /* Get the definition of NAME before the SCOP.  Keep track of the
5136    basic blocks that have been VISITED in a bitmap.  */
5137
5138 static tree
5139 get_vdef_before_scop (scop_p scop, tree name, sbitmap visited)
5140 {
5141   unsigned i;
5142   gimple def_stmt = SSA_NAME_DEF_STMT (name);
5143   basic_block def_bb = gimple_bb (def_stmt);
5144
5145   if (!def_bb
5146       || !bb_in_scop_p (def_bb, scop))
5147     return name;
5148
5149   if (TEST_BIT (visited, def_bb->index))
5150     return NULL_TREE;
5151
5152   SET_BIT (visited, def_bb->index);
5153
5154   switch (gimple_code (def_stmt))
5155     {
5156     case GIMPLE_PHI:
5157       for (i = 0; i < gimple_phi_num_args (def_stmt); i++)
5158         {
5159           tree arg = gimple_phi_arg_def (def_stmt, i);
5160           tree res = get_vdef_before_scop (scop, arg, visited);
5161           if (res)
5162             return res;
5163         }
5164       return NULL_TREE;
5165
5166     default:
5167       return NULL_TREE;
5168     }
5169 }
5170
5171 /* Adjust a virtual phi node PHI that is placed at the end of the
5172    generated code for SCOP:
5173
5174    | if (1)
5175    |   generated code from REGION;
5176    | else
5177    |   REGION;
5178
5179    The FALSE_E edge comes from the original code, TRUE_E edge comes
5180    from the code generated for the SCOP.  */
5181
5182 static void
5183 scop_adjust_vphi (scop_p scop, gimple phi, edge true_e)
5184 {
5185   unsigned i;
5186
5187   gcc_assert (gimple_phi_num_args (phi) == 2);
5188
5189   for (i = 0; i < gimple_phi_num_args (phi); i++)
5190     if (gimple_phi_arg_edge (phi, i) == true_e)
5191       {
5192         tree true_arg, false_arg, before_scop_arg;
5193         sbitmap visited;
5194
5195         true_arg = gimple_phi_arg_def (phi, i);
5196         if (!SSA_NAME_IS_DEFAULT_DEF (true_arg))
5197           return;
5198
5199         false_arg = gimple_phi_arg_def (phi, i == 0 ? 1 : 0);
5200         if (SSA_NAME_IS_DEFAULT_DEF (false_arg))
5201           return;
5202
5203         visited = sbitmap_alloc (last_basic_block);
5204         sbitmap_zero (visited);
5205         before_scop_arg = get_vdef_before_scop (scop, false_arg, visited);
5206         gcc_assert (before_scop_arg != NULL_TREE);
5207         SET_PHI_ARG_DEF (phi, i, before_scop_arg);
5208         sbitmap_free (visited);
5209       }
5210 }
5211
5212 /* Adjusts the phi nodes in the block BB for variables defined in
5213    SCOP_REGION and used outside the SCOP_REGION.  The code generation
5214    moves SCOP_REGION in the else clause of an "if (1)" and generates
5215    code in the then clause:
5216
5217    | if (1)
5218    |   generated code from REGION;
5219    | else
5220    |   REGION;
5221
5222    To adjust the phi nodes after the condition, SCOP_LIVEOUT_RENAMES
5223    hash table is used: this stores for a name that is part of the
5224    LIVEOUT of SCOP_REGION its new name in the generated code.  */
5225
5226 static void
5227 scop_adjust_phis_for_liveouts (scop_p scop, basic_block bb, edge false_e,
5228                                edge true_e)
5229 {
5230   gimple_stmt_iterator si;
5231
5232   for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
5233     {
5234       unsigned i, false_i;
5235       gimple phi = gsi_stmt (si);
5236
5237       if (!is_gimple_reg (PHI_RESULT (phi)))
5238         {
5239           scop_adjust_vphi (scop, phi, true_e);
5240           continue;
5241         }
5242
5243       for (i = 0; i < gimple_phi_num_args (phi); i++)
5244         if (gimple_phi_arg_edge (phi, i) == false_e)
5245           {
5246             false_i = i;
5247             break;
5248           }
5249
5250       for (i = 0; i < gimple_phi_num_args (phi); i++)
5251         if (gimple_phi_arg_edge (phi, i) == true_e)
5252           {
5253             tree old_name = gimple_phi_arg_def (phi, false_i);
5254             tree new_name = get_new_name_from_old_name
5255               (SCOP_LIVEOUT_RENAMES (scop), old_name);
5256
5257             gcc_assert (old_name != new_name);
5258             SET_PHI_ARG_DEF (phi, i, new_name);
5259           }
5260     }
5261 }
5262
5263 /* Returns the first cloog name used in EXPR.  */
5264
5265 static const char *
5266 find_cloog_iv_in_expr (struct clast_expr *expr)
5267 {
5268   struct clast_term *term = (struct clast_term *) expr;
5269
5270   if (expr->type == expr_term
5271       && !term->var)
5272     return NULL;
5273
5274   if (expr->type == expr_term)
5275     return term->var;
5276
5277   if (expr->type == expr_red)
5278     {
5279       int i;
5280       struct clast_reduction *red = (struct clast_reduction *) expr;
5281
5282       for (i = 0; i < red->n; i++)
5283         {
5284           const char *res = find_cloog_iv_in_expr ((red)->elts[i]);
5285
5286           if (res)
5287             return res;
5288         }
5289     }
5290
5291   return NULL;
5292 }
5293
5294 /* Build for a clast_user_stmt USER_STMT a map between the CLAST
5295    induction variables and the corresponding GCC old induction
5296    variables.  This information is stored on each GRAPHITE_BB.  */
5297
5298 static void
5299 compute_cloog_iv_types_1 (graphite_bb_p gbb,
5300                           struct clast_user_stmt *user_stmt)
5301 {
5302   struct clast_stmt *t;
5303   int index = 0;
5304
5305   for (t = user_stmt->substitutions; t; t = t->next, index++)
5306     {
5307       PTR *slot;
5308       struct ivtype_map_elt tmp;
5309       struct clast_expr *expr = (struct clast_expr *)
5310         ((struct clast_assignment *)t)->RHS;
5311
5312       /* Create an entry (clast_var, type).  */
5313       tmp.cloog_iv = find_cloog_iv_in_expr (expr);
5314       if (!tmp.cloog_iv)
5315         continue;
5316
5317       slot = htab_find_slot (GBB_CLOOG_IV_TYPES (gbb), &tmp, INSERT);
5318
5319       if (!*slot)
5320         {
5321           loop_p loop = gbb_loop_at_index (gbb, index);
5322           tree oldiv = oldiv_for_loop (GBB_SCOP (gbb), loop);
5323           tree type = oldiv ? TREE_TYPE (oldiv) : integer_type_node;
5324           *slot = new_ivtype_map_elt (tmp.cloog_iv, type);
5325         }
5326     }
5327 }
5328
5329 /* Walk the CLAST tree starting from STMT and build for each
5330    clast_user_stmt a map between the CLAST induction variables and the
5331    corresponding GCC old induction variables.  This information is
5332    stored on each GRAPHITE_BB.  */
5333
5334 static void
5335 compute_cloog_iv_types (struct clast_stmt *stmt)
5336 {
5337   if (!stmt)
5338     return;
5339
5340   if (CLAST_STMT_IS_A (stmt, stmt_root))
5341     goto next;
5342
5343   if (CLAST_STMT_IS_A (stmt, stmt_user))
5344     {
5345       CloogStatement *cs = ((struct clast_user_stmt *) stmt)->statement;
5346       graphite_bb_p gbb = (graphite_bb_p) cloog_statement_usr (cs);
5347       GBB_CLOOG_IV_TYPES (gbb) = htab_create (10, ivtype_map_elt_info,
5348                                               eq_ivtype_map_elts, free);
5349       compute_cloog_iv_types_1 (gbb, (struct clast_user_stmt *) stmt);
5350       goto next;
5351     }
5352
5353   if (CLAST_STMT_IS_A (stmt, stmt_for))
5354     {
5355       struct clast_stmt *s = ((struct clast_for *) stmt)->body;
5356       compute_cloog_iv_types (s);
5357       goto next;
5358     }
5359
5360   if (CLAST_STMT_IS_A (stmt, stmt_guard))
5361     {
5362       struct clast_stmt *s = ((struct clast_guard *) stmt)->then;
5363       compute_cloog_iv_types (s);
5364       goto next;
5365     }
5366
5367   if (CLAST_STMT_IS_A (stmt, stmt_block))
5368     {
5369       struct clast_stmt *s = ((struct clast_block *) stmt)->body;
5370       compute_cloog_iv_types (s);
5371       goto next;
5372     }
5373
5374   gcc_unreachable ();
5375
5376  next:
5377   compute_cloog_iv_types (stmt->next);
5378 }
5379
5380 /* GIMPLE Loop Generator: generates loops from STMT in GIMPLE form for
5381    the given SCOP.  */
5382
5383 static void
5384 gloog (scop_p scop, struct clast_stmt *stmt)
5385 {
5386   edge new_scop_exit_edge = NULL;
5387   VEC (iv_stack_entry_p, heap) *ivstack = VEC_alloc (iv_stack_entry_p, heap,
5388                                                      10);
5389   loop_p context_loop;
5390   ifsese if_region = NULL;
5391
5392   if_region = move_sese_in_condition (SCOP_REGION (scop));
5393   sese_build_livein_liveouts (SCOP_REGION (scop));
5394   scop_insert_phis_for_liveouts (SCOP_REGION (scop),
5395                                  if_region->region->exit->src,
5396                                  if_region->false_region->exit,
5397                                  if_region->true_region->exit);
5398   recompute_all_dominators ();
5399   graphite_verify ();
5400   context_loop = SESE_ENTRY (SCOP_REGION (scop))->src->loop_father;
5401   compute_cloog_iv_types (stmt);
5402
5403   new_scop_exit_edge = translate_clast (scop, context_loop, stmt,
5404                                         if_region->true_region->entry,
5405                                         &ivstack);
5406   free_loop_iv_stack (&ivstack);
5407   cloog_clast_free (stmt);
5408
5409   graphite_verify ();
5410   scop_adjust_phis_for_liveouts (scop,
5411                                  if_region->region->exit->src,
5412                                  if_region->false_region->exit,
5413                                  if_region->true_region->exit);
5414
5415   recompute_all_dominators ();
5416   graphite_verify ();
5417 }
5418
5419 /* Returns the number of data references in SCOP.  */
5420
5421 static int
5422 nb_data_refs_in_scop (scop_p scop)
5423 {
5424   int i;
5425   graphite_bb_p gbb;
5426   int res = 0;
5427
5428   for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gbb); i++)
5429     res += VEC_length (data_reference_p, GBB_DATA_REFS (gbb));
5430
5431   return res;
5432 }
5433
5434 /* Move the loop at index LOOP and insert it before index NEW_LOOP_POS.
5435    This transformartion is only valid, if the loop nest between i and k is
5436    perfectly nested. Therefore we do not need to change the static schedule.
5437
5438    Example:
5439
5440    for (i = 0; i < 50; i++)
5441      for (j ...)
5442        for (k = 5; k < 100; k++)
5443          A
5444
5445    To move k before i use:
5446
5447    graphite_trans_bb_move_loop (A, 2, 0)
5448
5449    for (k = 5; k < 100; k++)
5450      for (i = 0; i < 50; i++)
5451        for (j ...)
5452          A
5453
5454    And to move k back:
5455
5456    graphite_trans_bb_move_loop (A, 0, 2)
5457
5458    This function does not check the validity of interchanging loops.
5459    This should be checked before calling this function.  */
5460
5461 static void
5462 graphite_trans_bb_move_loop (graphite_bb_p gb, int loop,
5463                              int new_loop_pos)
5464 {
5465   CloogMatrix *domain = GBB_DOMAIN (gb);
5466   int row, j;
5467   loop_p tmp_loop_p;
5468
5469   gcc_assert (loop < gbb_nb_loops (gb)
5470               && new_loop_pos < gbb_nb_loops (gb));
5471
5472   /* Update LOOPS vector.  */
5473   tmp_loop_p = VEC_index (loop_p, GBB_LOOPS (gb), loop);
5474   VEC_ordered_remove (loop_p, GBB_LOOPS (gb), loop);
5475   VEC_safe_insert (loop_p, heap, GBB_LOOPS (gb), new_loop_pos, tmp_loop_p);
5476
5477   /* Move the domain columns.  */
5478   if (loop < new_loop_pos)
5479     for (row = 0; row < domain->NbRows; row++)
5480       {
5481         Value tmp;
5482         value_init (tmp);
5483         value_assign (tmp, domain->p[row][loop + 1]);
5484
5485         for (j = loop ; j < new_loop_pos - 1; j++)
5486           value_assign (domain->p[row][j + 1], domain->p[row][j + 2]);
5487
5488         value_assign (domain->p[row][new_loop_pos], tmp);
5489         value_clear (tmp);
5490       }
5491   else
5492     for (row = 0; row < domain->NbRows; row++)
5493       {
5494         Value tmp;
5495         value_init (tmp);
5496         value_assign (tmp, domain->p[row][loop + 1]);
5497
5498         for (j = loop ; j > new_loop_pos; j--)
5499           value_assign (domain->p[row][j + 1], domain->p[row][j]);
5500
5501         value_assign (domain->p[row][new_loop_pos + 1], tmp);
5502         value_clear (tmp);
5503       }
5504 }
5505
5506 /* Get the index of the column representing constants in the DOMAIN
5507    matrix.  */
5508
5509 static int
5510 const_column_index (CloogMatrix *domain)
5511 {
5512   return domain->NbColumns - 1;
5513 }
5514
5515
5516 /* Get the first index that is positive or negative, determined
5517    following the value of POSITIVE, in matrix DOMAIN in COLUMN.  */
5518
5519 static int
5520 get_first_matching_sign_row_index (CloogMatrix *domain, int column,
5521                                    bool positive)
5522 {
5523   int row;
5524
5525   for (row = 0; row < domain->NbRows; row++)
5526     {
5527       int val = value_get_si (domain->p[row][column]);
5528
5529       if (val > 0 && positive)
5530         return row;
5531
5532       else if (val < 0 && !positive)
5533         return row;
5534     }
5535
5536   gcc_unreachable ();
5537 }
5538
5539 /* Get the lower bound of COLUMN in matrix DOMAIN.  */
5540
5541 static int
5542 get_lower_bound_row (CloogMatrix *domain, int column)
5543 {
5544   return get_first_matching_sign_row_index (domain, column, true);
5545 }
5546
5547 /* Get the upper bound of COLUMN in matrix DOMAIN.  */
5548
5549 static int
5550 get_upper_bound_row (CloogMatrix *domain, int column)
5551 {
5552   return get_first_matching_sign_row_index (domain, column, false);
5553 }
5554
5555 /* Copies the OLD_ROW constraint from OLD_DOMAIN to the NEW_DOMAIN at
5556    row NEW_ROW.  */
5557
5558 static void
5559 copy_constraint (CloogMatrix *old_domain, CloogMatrix *new_domain,
5560                  int old_row, int new_row)
5561 {
5562   int i;
5563
5564   gcc_assert (old_domain->NbColumns == new_domain->NbColumns
5565               && old_row < old_domain->NbRows
5566               && new_row < new_domain->NbRows);
5567
5568   for (i = 0; i < old_domain->NbColumns; i++)
5569     value_assign (new_domain->p[new_row][i], old_domain->p[old_row][i]);
5570 }
5571
5572 /* Swap coefficients of variables X and Y on row R.   */
5573
5574 static void
5575 swap_constraint_variables (CloogMatrix *domain,
5576                            int r, int x, int y)
5577 {
5578   value_swap (domain->p[r][x], domain->p[r][y]);
5579 }
5580
5581 /* Scale by X the coefficient C of constraint at row R in DOMAIN.  */
5582
5583 static void
5584 scale_constraint_variable (CloogMatrix *domain,
5585                            int r, int c, int x)
5586 {
5587   Value strip_size_value;
5588   value_init (strip_size_value);
5589   value_set_si (strip_size_value, x);
5590   value_multiply (domain->p[r][c], domain->p[r][c], strip_size_value);
5591   value_clear (strip_size_value);
5592 }
5593
5594 /* Strip mines the loop of BB at the position LOOP_DEPTH with STRIDE.
5595    Always valid, but not always a performance improvement.  */
5596
5597 static void
5598 graphite_trans_bb_strip_mine (graphite_bb_p gb, int loop_depth, int stride)
5599 {
5600   int row, col;
5601
5602   CloogMatrix *domain = GBB_DOMAIN (gb);
5603   CloogMatrix *new_domain = cloog_matrix_alloc (domain->NbRows + 3,
5604                                                 domain->NbColumns + 1);
5605
5606   int col_loop_old = loop_depth + 2;
5607   int col_loop_strip = col_loop_old - 1;
5608
5609   gcc_assert (loop_depth <= gbb_nb_loops (gb) - 1);
5610
5611   VEC_safe_insert (loop_p, heap, GBB_LOOPS (gb), loop_depth, NULL);
5612
5613   GBB_DOMAIN (gb) = new_domain;
5614
5615   for (row = 0; row < domain->NbRows; row++)
5616     for (col = 0; col < domain->NbColumns; col++)
5617       if (col <= loop_depth)
5618         value_assign (new_domain->p[row][col], domain->p[row][col]);
5619       else
5620         value_assign (new_domain->p[row][col + 1], domain->p[row][col]);
5621
5622   row = domain->NbRows;
5623
5624   /* Lower bound of the outer stripped loop.  */
5625   copy_constraint (new_domain, new_domain,
5626                    get_lower_bound_row (new_domain, col_loop_old), row);
5627   swap_constraint_variables (new_domain, row, col_loop_old, col_loop_strip);
5628   row++;
5629
5630   /* Upper bound of the outer stripped loop.  */
5631   copy_constraint (new_domain, new_domain,
5632                    get_upper_bound_row (new_domain, col_loop_old), row);
5633   swap_constraint_variables (new_domain, row, col_loop_old, col_loop_strip);
5634   scale_constraint_variable (new_domain, row, col_loop_strip, stride);
5635   row++;
5636
5637   /* Lower bound of a tile starts at "stride * outer_iv".  */
5638   row = get_lower_bound_row (new_domain, col_loop_old);
5639   value_set_si (new_domain->p[row][0], 1);
5640   value_set_si (new_domain->p[row][const_column_index (new_domain)], 0);
5641   value_set_si (new_domain->p[row][col_loop_old], 1);
5642   value_set_si (new_domain->p[row][col_loop_strip], -1 * stride);
5643
5644   /* Upper bound of a tile stops at "stride * outer_iv + stride - 1",
5645      or at the old upper bound that is not modified.  */
5646   row = new_domain->NbRows - 1;
5647   value_set_si (new_domain->p[row][0], 1);
5648   value_set_si (new_domain->p[row][col_loop_old], -1);
5649   value_set_si (new_domain->p[row][col_loop_strip], stride);
5650   value_set_si (new_domain->p[row][const_column_index (new_domain)],
5651                 stride - 1);
5652
5653   cloog_matrix_free (domain);
5654
5655   /* Update static schedule.  */
5656   {
5657     int i;
5658     int nb_loops = gbb_nb_loops (gb);
5659     lambda_vector new_schedule = lambda_vector_new (nb_loops + 1);
5660
5661     for (i = 0; i <= loop_depth; i++)
5662       new_schedule[i] = GBB_STATIC_SCHEDULE (gb)[i];
5663
5664     for (i = loop_depth + 1; i <= nb_loops - 2; i++)
5665       new_schedule[i + 2] = GBB_STATIC_SCHEDULE (gb)[i];
5666
5667     GBB_STATIC_SCHEDULE (gb) = new_schedule;
5668   }
5669 }
5670
5671 /* Returns true when the strip mining of LOOP_INDEX by STRIDE is
5672    profitable or undecidable.  GB is the statement around which the
5673    loops will be strip mined.  */
5674
5675 static bool
5676 strip_mine_profitable_p (graphite_bb_p gb, int stride,
5677                          int loop_index)
5678 {
5679   bool res = true;
5680   edge exit = NULL;
5681   tree niter;
5682   loop_p loop;
5683   long niter_val;
5684
5685   loop = VEC_index (loop_p, GBB_LOOPS (gb), loop_index);
5686   exit = single_exit (loop);
5687
5688   niter = find_loop_niter (loop, &exit);
5689   if (niter == chrec_dont_know
5690       || TREE_CODE (niter) != INTEGER_CST)
5691     return true;
5692
5693   niter_val = int_cst_value (niter);
5694
5695   if (niter_val < stride)
5696     {
5697       res = false;
5698       if (dump_file && (dump_flags & TDF_DETAILS))
5699         {
5700           fprintf (dump_file, "\nStrip Mining is not profitable for loop %d:",
5701                    loop->num);
5702           fprintf (dump_file, "number of iterations is too low.\n");
5703         }
5704     }
5705
5706   return res;
5707 }
5708
5709 /* Determines when the interchange of LOOP_A and LOOP_B belonging to
5710    SCOP is legal.  DEPTH is the number of loops around.  */
5711
5712 static bool
5713 is_interchange_valid (scop_p scop, int loop_a, int loop_b, int depth)
5714 {
5715   bool res;
5716   VEC (ddr_p, heap) *dependence_relations;
5717   VEC (data_reference_p, heap) *datarefs;
5718
5719   struct loop *nest = VEC_index (loop_p, SCOP_LOOP_NEST (scop), loop_a);
5720   lambda_trans_matrix trans;
5721
5722   gcc_assert (loop_a < loop_b);
5723
5724   dependence_relations = VEC_alloc (ddr_p, heap, 10 * 10);
5725   datarefs = VEC_alloc (data_reference_p, heap, 10);
5726
5727   if (!compute_data_dependences_for_loop (nest, true, &datarefs,
5728                                           &dependence_relations))
5729     return false;
5730
5731   if (dump_file && (dump_flags & TDF_DETAILS))
5732     dump_ddrs (dump_file, dependence_relations);
5733
5734   trans = lambda_trans_matrix_new (depth, depth);
5735   lambda_matrix_id (LTM_MATRIX (trans), depth);
5736
5737   lambda_matrix_row_exchange (LTM_MATRIX (trans), 0, loop_b - loop_a);
5738
5739   if (!lambda_transform_legal_p (trans, depth, dependence_relations))
5740     {
5741       lambda_matrix_row_exchange (LTM_MATRIX (trans), 0, loop_b - loop_a);
5742       res = false;
5743     }
5744   else
5745     res = true;
5746
5747   free_dependence_relations (dependence_relations);
5748   free_data_refs (datarefs);
5749   return res;
5750 }
5751
5752 /* Loop block the LOOPS innermost loops of GB with stride size STRIDE.
5753
5754    Example
5755
5756    for (i = 0; i <= 50; i++=4)
5757      for (k = 0; k <= 100; k++=4)
5758        for (l = 0; l <= 200; l++=4)
5759          A
5760
5761    To strip mine the two inner most loops with stride = 4 call:
5762
5763    graphite_trans_bb_block (A, 4, 2)
5764
5765    for (i = 0; i <= 50; i++)
5766      for (kk = 0; kk <= 100; kk+=4)
5767        for (ll = 0; ll <= 200; ll+=4)
5768          for (k = kk; k <= min (100, kk + 3); k++)
5769            for (l = ll; l <= min (200, ll + 3); l++)
5770              A
5771 */
5772
5773 static bool
5774 graphite_trans_bb_block (graphite_bb_p gb, int stride, int loops)
5775 {
5776   int i, j;
5777   int nb_loops = gbb_nb_loops (gb);
5778   int start = nb_loops - loops;
5779   scop_p scop = GBB_SCOP (gb);
5780
5781   gcc_assert (scop_contains_loop (scop, gbb_loop (gb)));
5782
5783   for (i = start ; i < nb_loops; i++)
5784     for (j = i + 1; j < nb_loops; j++)
5785       if (!is_interchange_valid (scop, i, j, nb_loops))
5786         {
5787           if (dump_file && (dump_flags & TDF_DETAILS))
5788             fprintf (dump_file,
5789                      "\nInterchange not valid for loops %d and %d:\n", i, j);
5790           return false;
5791         }
5792       else if (dump_file && (dump_flags & TDF_DETAILS))
5793         fprintf (dump_file,
5794                  "\nInterchange valid for loops %d and %d:\n", i, j);
5795
5796   /* Check if strip mining is profitable for every loop.  */
5797   for (i = 0; i < nb_loops - start; i++)
5798     if (!strip_mine_profitable_p (gb, stride, start + i))
5799       return false;
5800
5801   /* Strip mine loops.  */
5802   for (i = 0; i < nb_loops - start; i++)
5803     graphite_trans_bb_strip_mine (gb, start + 2 * i, stride);
5804
5805   /* Interchange loops.  */
5806   for (i = 1; i < nb_loops - start; i++)
5807     graphite_trans_bb_move_loop (gb, start + 2 * i, start + i);
5808
5809   if (dump_file && (dump_flags & TDF_DETAILS))
5810     fprintf (dump_file, "\nLoops containing BB %d will be loop blocked.\n",
5811              GBB_BB (gb)->index);
5812
5813   return true;
5814 }
5815
5816 /* Loop block LOOPS innermost loops of a loop nest.  BBS represent the
5817    basic blocks that belong to the loop nest to be blocked.  */
5818
5819 static bool
5820 graphite_trans_loop_block (VEC (graphite_bb_p, heap) *bbs, int loops)
5821 {
5822   graphite_bb_p gb;
5823   int i;
5824   bool transform_done = false;
5825
5826   /* TODO: - Calculate the stride size automatically.  */
5827   int stride_size = 64;
5828
5829   for (i = 0; VEC_iterate (graphite_bb_p, bbs, i, gb); i++)
5830     transform_done |= graphite_trans_bb_block (gb, stride_size, loops);
5831
5832   return transform_done;
5833 }
5834
5835 /* Loop block all basic blocks of SCOP.  Return false when the
5836    transform is not performed.  */
5837
5838 static bool
5839 graphite_trans_scop_block (scop_p scop)
5840 {
5841   graphite_bb_p gb;
5842   int i, j;
5843   int last_nb_loops;
5844   int nb_loops;
5845   bool perfect = true;
5846   bool transform_done = false;
5847
5848   VEC (graphite_bb_p, heap) *bbs = VEC_alloc (graphite_bb_p, heap, 3);
5849   int max_schedule = scop_max_loop_depth (scop) + 1;
5850   lambda_vector last_schedule = lambda_vector_new (max_schedule);
5851
5852   if (VEC_length (graphite_bb_p, SCOP_BBS (scop)) == 0)
5853     return false;
5854
5855   /* Get the data of the first bb.  */
5856   gb = VEC_index (graphite_bb_p, SCOP_BBS (scop), 0);
5857   last_nb_loops = gbb_nb_loops (gb);
5858   lambda_vector_copy (GBB_STATIC_SCHEDULE (gb), last_schedule,
5859                       last_nb_loops + 1);
5860   VEC_safe_push (graphite_bb_p, heap, bbs, gb);
5861
5862   for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
5863     {
5864       /* We did the first bb before.  */
5865       if (i == 0)
5866         continue;
5867
5868       nb_loops = gbb_nb_loops (gb);
5869
5870       /* If the number of loops is unchanged and only the last element of the
5871          schedule changes, we stay in the loop nest.  */
5872       if (nb_loops == last_nb_loops
5873           && (last_schedule [nb_loops + 1]
5874               != GBB_STATIC_SCHEDULE (gb)[nb_loops + 1]))
5875         {
5876           VEC_safe_push (graphite_bb_p, heap, bbs, gb);
5877           continue;
5878         }
5879
5880       /* Otherwise, we left the innermost loop. So check, if the last bb was in
5881          a perfect loop nest and how many loops are contained in this perfect
5882          loop nest.
5883
5884          Count the number of zeros from the end of the schedule. They are the
5885          number of surrounding loops.
5886
5887          Example:
5888          last_bb  2 3 2 0 0 0 0 3
5889          bb       2 4 0
5890          <------  j = 4
5891
5892          last_bb  2 3 2 0 0 0 0 3
5893          bb       2 3 2 0 1
5894          <--  j = 2
5895
5896          If there is no zero, there were other bbs in outer loops and the loop
5897          nest is not perfect.  */
5898       for (j = last_nb_loops - 1; j >= 0; j--)
5899         {
5900           if (last_schedule [j] != 0
5901               || (j <= nb_loops && GBB_STATIC_SCHEDULE (gb)[j] == 1))
5902             {
5903               j--;
5904               break;
5905             }
5906         }
5907
5908       j++;
5909
5910       /* Found perfect loop nest.  */
5911       if (perfect && last_nb_loops - j >= 2)
5912         transform_done |= graphite_trans_loop_block (bbs, last_nb_loops - j);
5913
5914       /* Check if we start with a new loop.
5915
5916          Example:
5917
5918          last_bb  2 3 2 0 0 0 0 3
5919          bb       2 3 2 0 0 1 0
5920
5921          Here we start with the loop "2 3 2 0 0 1"
5922
5923          last_bb  2 3 2 0 0 0 0 3
5924          bb       2 3 2 0 0 1
5925
5926          But here not, so the loop nest can never be perfect.  */
5927
5928       perfect = (GBB_STATIC_SCHEDULE (gb)[nb_loops] == 0);
5929
5930       /* Update the last_bb infos.  We do not do that for the bbs in the same
5931          loop, as the data we use is not changed.  */
5932       last_nb_loops = nb_loops;
5933       lambda_vector_copy (GBB_STATIC_SCHEDULE (gb), last_schedule,
5934                           nb_loops + 1);
5935       VEC_truncate (graphite_bb_p, bbs, 0);
5936       VEC_safe_push (graphite_bb_p, heap, bbs, gb);
5937     }
5938
5939   /* Check if the last loop nest was perfect.  It is the same check as above,
5940      but the comparison with the next bb is missing.  */
5941   for (j = last_nb_loops - 1; j >= 0; j--)
5942     if (last_schedule [j] != 0)
5943       {
5944         j--;
5945         break;
5946       }
5947
5948   j++;
5949
5950   /* Found perfect loop nest.  */
5951   if (last_nb_loops - j >= 2)
5952     transform_done |= graphite_trans_loop_block (bbs, last_nb_loops - j);
5953   VEC_free (graphite_bb_p, heap, bbs);
5954
5955   return transform_done;
5956 }
5957
5958 /* Apply graphite transformations to all the basic blocks of SCOP.  */
5959
5960 static bool
5961 graphite_apply_transformations (scop_p scop)
5962 {
5963   bool transform_done = false;
5964
5965   /* Sort the list of bbs.  Keep them always sorted.  */
5966   graphite_sort_gbbs (scop);
5967
5968   if (flag_loop_block)
5969     transform_done = graphite_trans_scop_block (scop);
5970
5971   /* Generate code even if we did not apply any real transformation.
5972      This also allows to check the performance for the identity
5973      transformation: GIMPLE -> GRAPHITE -> GIMPLE
5974      Keep in mind that CLooG optimizes in control, so the loop structure
5975      may change, even if we only use -fgraphite-identity.  */
5976   if (flag_graphite_identity)
5977     transform_done = true;
5978
5979   return transform_done;
5980 }
5981
5982 /* We limit all SCoPs to SCoPs, that are completely surrounded by a loop.
5983
5984    Example:
5985
5986    for (i      |
5987      {         |
5988        for (j  |  SCoP 1
5989        for (k  |
5990      }         |
5991
5992    * SCoP frontier, as this line is not surrounded by any loop. *
5993
5994    for (l      |  SCoP 2
5995
5996    This is necessary as scalar evolution and parameter detection need a
5997    outermost loop to initialize parameters correctly.
5998
5999    TODO: FIX scalar evolution and parameter detection to allow more flexible
6000          SCoP frontiers.  */
6001
6002 static void
6003 limit_scops (void)
6004 {
6005   VEC (sd_region, heap) *tmp_scops = VEC_alloc (sd_region, heap, 3);
6006
6007   int i;
6008   scop_p scop;
6009
6010   for (i = 0; VEC_iterate (scop_p, current_scops, i, scop); i++)
6011     {
6012       int j;
6013       loop_p loop;
6014       build_scop_bbs (scop);
6015
6016       if (!build_scop_loop_nests (scop))
6017         continue;
6018
6019       for (j = 0; VEC_iterate (loop_p, SCOP_LOOP_NEST (scop), j, loop); j++)
6020         if (!loop_in_scop_p (loop_outer (loop), scop))
6021           {
6022             sd_region open_scop;
6023             open_scop.entry = loop->header;
6024             open_scop.exit = single_exit (loop)->dest;
6025             VEC_safe_push (sd_region, heap, tmp_scops, &open_scop);
6026           }
6027     }
6028
6029   free_scops (current_scops);
6030   current_scops = VEC_alloc (scop_p, heap, 3);
6031
6032   create_sese_edges (tmp_scops);
6033   build_graphite_scops (tmp_scops);
6034   VEC_free (sd_region, heap, tmp_scops);
6035 }
6036
6037 /* Perform a set of linear transforms on the loops of the current
6038    function.  */
6039
6040 void
6041 graphite_transform_loops (void)
6042 {
6043   int i;
6044   scop_p scop;
6045
6046   if (number_of_loops () <= 1)
6047     return;
6048
6049   current_scops = VEC_alloc (scop_p, heap, 3);
6050   recompute_all_dominators ();
6051
6052   if (dump_file && (dump_flags & TDF_DETAILS))
6053     fprintf (dump_file, "Graphite loop transformations \n");
6054
6055   initialize_original_copy_tables ();
6056   cloog_initialize ();
6057   build_scops ();
6058   limit_scops ();
6059
6060   if (dump_file && (dump_flags & TDF_DETAILS))
6061     fprintf (dump_file, "\nnumber of SCoPs: %d\n",
6062              VEC_length (scop_p, current_scops));
6063
6064   for (i = 0; VEC_iterate (scop_p, current_scops, i, scop); i++)
6065     {
6066       build_scop_bbs (scop);
6067       if (!build_scop_loop_nests (scop))
6068         continue;
6069
6070       build_bb_loops (scop);
6071
6072       if (!build_scop_conditions (scop))
6073         continue;
6074
6075       find_scop_parameters (scop);
6076       build_scop_context (scop);
6077
6078       if (dump_file && (dump_flags & TDF_DETAILS))
6079         {
6080           fprintf (dump_file, "\n(In SCoP %d:\n", i);
6081           fprintf (dump_file, "\nnumber of bbs: %d\n",
6082                    VEC_length (graphite_bb_p, SCOP_BBS (scop)));
6083           fprintf (dump_file, "\nnumber of loops: %d)\n",
6084                    VEC_length (loop_p, SCOP_LOOP_NEST (scop)));
6085         }
6086
6087       if (!build_scop_iteration_domain (scop))
6088         continue;
6089
6090       add_conditions_to_constraints (scop);
6091       build_scop_canonical_schedules (scop);
6092
6093       build_scop_data_accesses (scop);
6094       build_scop_dynamic_schedules (scop);
6095
6096       if (dump_file && (dump_flags & TDF_DETAILS))
6097         {
6098           int nbrefs = nb_data_refs_in_scop (scop);
6099           fprintf (dump_file, "\nnumber of data refs: %d\n", nbrefs);
6100         }
6101
6102       if (graphite_apply_transformations (scop))
6103         gloog (scop, find_transform (scop));
6104 #ifdef ENABLE_CHECKING
6105       else
6106         {
6107           struct clast_stmt *stmt = find_transform (scop);
6108           cloog_clast_free (stmt);
6109         }
6110 #endif
6111     }
6112
6113   /* Cleanup.  */
6114   cleanup_tree_cfg ();
6115   free_scops (current_scops);
6116   cloog_finalize ();
6117   free_original_copy_tables ();
6118 }
6119
6120 #else /* If Cloog is not available: #ifndef HAVE_cloog.  */
6121
6122 void
6123 graphite_transform_loops (void)
6124 {
6125   sorry ("Graphite loop optimizations cannot be used");
6126 }
6127
6128 #endif