gcc/graphite-sese-to-poly.c

   1 /* Conversion of SESE regions to Polyhedra.
   2    Copyright (C) 2009 Free Software Foundation, Inc.
   3    Contributed by Sebastian Pop <sebastian.pop@amd.com>.
   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 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tm.h"
  25 #include "ggc.h"
  26 #include "tree.h"
  27 #include "rtl.h"
  28 #include "basic-block.h"
  29 #include "diagnostic.h"
  30 #include "tree-flow.h"
  31 #include "toplev.h"
  32 #include "tree-dump.h"
  33 #include "timevar.h"
  34 #include "cfgloop.h"
  35 #include "tree-chrec.h"
  36 #include "tree-data-ref.h"
  37 #include "tree-scalar-evolution.h"
  38 #include "tree-pass.h"
  39 #include "domwalk.h"
  40 #include "value-prof.h"
  41 #include "pointer-set.h"
  42 #include "gimple.h"
  43 #include "sese.h"
  44
  45 #ifdef HAVE_cloog
  46 #include "cloog/cloog.h"
  47 #include "ppl_c.h"
  48 #include "graphite-ppl.h"
  49 #include "graphite.h"
  50 #include "graphite-poly.h"
  51 #include "graphite-scop-detection.h"
  52 #include "graphite-clast-to-gimple.h"
  53 #include "graphite-sese-to-poly.h"
  54
  55 /* Check if VAR is used in a phi node, that is no loop header.  */
  56
  57 static bool
  58 var_used_in_not_loop_header_phi_node (tree var)
  59 {
  60   imm_use_iterator imm_iter;
  61   gimple stmt;
  62   bool result = false;
  63
  64   FOR_EACH_IMM_USE_STMT (stmt, imm_iter, var)
  65     {
  66       basic_block bb = gimple_bb (stmt);
  67
  68       if (gimple_code (stmt) == GIMPLE_PHI
  69           && bb->loop_father->header != bb)
  70         result = true;
  71     }
  72
  73   return result;
  74 }
  75
  76 /* Returns the index of the phi argument corresponding to the initial
  77    value in the loop.  */
  78
  79 static size_t
  80 loop_entry_phi_arg (gimple phi)
  81 {
  82   loop_p loop = gimple_bb (phi)->loop_father;
  83   size_t i;
  84
  85   for (i = 0; i < gimple_phi_num_args (phi); i++)
  86     if (!flow_bb_inside_loop_p (loop, gimple_phi_arg_edge (phi, i)->src))
  87       return i;
  88
  89   gcc_unreachable ();
  90   return 0;
  91 }
  92
  93 /* Removes a simple copy phi node "RES = phi (INIT, RES)" at position
  94    PSI by inserting on the loop ENTRY edge assignment "RES = INIT".  */
  95
  96 static void
  97 remove_simple_copy_phi (gimple_stmt_iterator *psi)
  98 {
  99   gimple phi = gsi_stmt (*psi);
 100   tree res = gimple_phi_result (phi);
 101   size_t entry = loop_entry_phi_arg (phi);
 102   tree init = gimple_phi_arg_def (phi, entry);
 103   gimple stmt = gimple_build_assign (res, init);
 104   edge e = gimple_phi_arg_edge (phi, entry);
 105
 106   remove_phi_node (psi, false);
 107   gsi_insert_on_edge_immediate (e, stmt);
 108   SSA_NAME_DEF_STMT (res) = stmt;
 109 }
 110
 111 /* Removes an invariant phi node at position PSI by inserting on the
 112    loop ENTRY edge the assignment RES = INIT.  */
 113
 114 static void
 115 remove_invariant_phi (sese region, gimple_stmt_iterator *psi)
 116 {
 117   gimple phi = gsi_stmt (*psi);
 118   loop_p loop = loop_containing_stmt (phi);
 119   tree res = gimple_phi_result (phi);
 120   tree scev = scalar_evolution_in_region (region, loop, res);
 121   size_t entry = loop_entry_phi_arg (phi);
 122   edge e = gimple_phi_arg_edge (phi, entry);
 123   tree var;
 124   gimple stmt;
 125   gimple_seq stmts;
 126   gimple_stmt_iterator gsi;
 127
 128   if (tree_contains_chrecs (scev, NULL))
 129     scev = gimple_phi_arg_def (phi, entry);
 130
 131   var = force_gimple_operand (scev, &stmts, true, NULL_TREE);
 132   stmt = gimple_build_assign (res, var);
 133   remove_phi_node (psi, false);
 134
 135   if (!stmts)
 136     stmts = gimple_seq_alloc ();
 137
 138   gsi = gsi_last (stmts);
 139   gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
 140   gsi_insert_seq_on_edge (e, stmts);
 141   gsi_commit_edge_inserts ();
 142   SSA_NAME_DEF_STMT (res) = stmt;
 143 }
 144
 145 /* Returns true when the phi node at PSI is of the form "a = phi (a, x)".  */
 146
 147 static inline bool
 148 simple_copy_phi_p (gimple phi)
 149 {
 150   tree res;
 151
 152   if (gimple_phi_num_args (phi) != 2)
 153     return false;
 154
 155   res = gimple_phi_result (phi);
 156   return (res == gimple_phi_arg_def (phi, 0)
 157           || res == gimple_phi_arg_def (phi, 1));
 158 }
 159
 160 /* Returns true when the phi node at position PSI is a reduction phi
 161    node in REGION.  Otherwise moves the pointer PSI to the next phi to
 162    be considered.  */
 163
 164 static bool
 165 reduction_phi_p (sese region, gimple_stmt_iterator *psi)
 166 {
 167   loop_p loop;
 168   tree scev;
 169   affine_iv iv;
 170   gimple phi = gsi_stmt (*psi);
 171   tree res = gimple_phi_result (phi);
 172
 173   if (!is_gimple_reg (res))
 174     {
 175       gsi_next (psi);
 176       return false;
 177     }
 178
 179   loop = loop_containing_stmt (phi);
 180
 181   if (simple_copy_phi_p (phi))
 182     {
 183       /* FIXME: PRE introduces phi nodes like these, for an example,
 184          see id-5.f in the fortran graphite testsuite:
 185
 186          # prephitmp.85_265 = PHI <prephitmp.85_258(33), prephitmp.85_265(18)>
 187       */
 188       remove_simple_copy_phi (psi);
 189       return false;
 190     }
 191
 192   /* Main induction variables with constant strides in LOOP are not
 193      reductions.  */
 194   if (simple_iv (loop, loop, res, &iv, true))
 195     {
 196       if (integer_zerop (iv.step))
 197         remove_invariant_phi (region, psi);
 198       else
 199         gsi_next (psi);
 200
 201       return false;
 202     }
 203
 204   scev = scalar_evolution_in_region (region, loop, res);
 205   if (chrec_contains_undetermined (scev))
 206     return true;
 207
 208   if (evolution_function_is_invariant_p (scev, loop->num))
 209     {
 210       remove_invariant_phi (region, psi);
 211       return false;
 212     }
 213
 214   /* All the other cases are considered reductions.  */
 215   return true;
 216 }
 217
 218 /* Returns true when BB will be represented in graphite.  Return false
 219    for the basic blocks that contain code eliminated in the code
 220    generation pass: i.e. induction variables and exit conditions.  */
 221
 222 static bool
 223 graphite_stmt_p (sese region, basic_block bb,
 224                  VEC (data_reference_p, heap) *drs)
 225 {
 226   gimple_stmt_iterator gsi;
 227   loop_p loop = bb->loop_father;
 228
 229   if (VEC_length (data_reference_p, drs) > 0)
 230     return true;
 231
 232   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 233     {
 234       gimple stmt = gsi_stmt (gsi);
 235
 236       switch (gimple_code (stmt))
 237         {
 238         case GIMPLE_DEBUG:
 239           /* Control flow expressions can be ignored, as they are
 240              represented in the iteration domains and will be
 241              regenerated by graphite.  */
 242         case GIMPLE_COND:
 243         case GIMPLE_GOTO:
 244         case GIMPLE_SWITCH:
 245           break;
 246
 247         case GIMPLE_ASSIGN:
 248           {
 249             tree var = gimple_assign_lhs (stmt);
 250
 251             /* We need these bbs to be able to construct the phi nodes.  */
 252             if (var_used_in_not_loop_header_phi_node (var))
 253               return true;
 254
 255             var = scalar_evolution_in_region (region, loop, var);
 256             if (chrec_contains_undetermined (var))
 257               return true;
 258
 259             break;
 260           }
 261
 262         default:
 263           return true;
 264         }
 265     }
 266
 267   return false;
 268 }
 269
 270 /* Store the GRAPHITE representation of BB.  */
 271
 272 static gimple_bb_p
 273 new_gimple_bb (basic_block bb, VEC (data_reference_p, heap) *drs)
 274 {
 275   struct gimple_bb *gbb;
 276
 277   gbb = XNEW (struct gimple_bb);
 278   bb->aux = gbb;
 279   GBB_BB (gbb) = bb;
 280   GBB_DATA_REFS (gbb) = drs;
 281   GBB_CONDITIONS (gbb) = NULL;
 282   GBB_CONDITION_CASES (gbb) = NULL;
 283   GBB_CLOOG_IV_TYPES (gbb) = NULL;
 284
 285   return gbb;
 286 }
 287
 288 static void
 289 free_data_refs_aux (VEC (data_reference_p, heap) *datarefs)
 290 {
 291   unsigned int i;
 292   struct data_reference *dr;
 293
 294   for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
 295     if (dr->aux)
 296       {
 297         base_alias_pair *bap = (base_alias_pair *)(dr->aux);
 298
 299         if (bap->alias_set)
 300           free (bap->alias_set);
 301
 302         free (bap);
 303         dr->aux = NULL;
 304       }
 305 }
 306 /* Frees GBB.  */
 307
 308 static void
 309 free_gimple_bb (struct gimple_bb *gbb)
 310 {
 311   if (GBB_CLOOG_IV_TYPES (gbb))
 312     htab_delete (GBB_CLOOG_IV_TYPES (gbb));
 313
 314   free_data_refs_aux (GBB_DATA_REFS (gbb));
 315   free_data_refs (GBB_DATA_REFS (gbb));
 316
 317   VEC_free (gimple, heap, GBB_CONDITIONS (gbb));
 318   VEC_free (gimple, heap, GBB_CONDITION_CASES (gbb));
 319   GBB_BB (gbb)->aux = 0;
 320   XDELETE (gbb);
 321 }
 322
 323 /* Deletes all gimple bbs in SCOP.  */
 324
 325 static void
 326 remove_gbbs_in_scop (scop_p scop)
 327 {
 328   int i;
 329   poly_bb_p pbb;
 330
 331   for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
 332     free_gimple_bb (PBB_BLACK_BOX (pbb));
 333 }
 334
 335 /* Deletes all scops in SCOPS.  */
 336
 337 void
 338 free_scops (VEC (scop_p, heap) *scops)
 339 {
 340   int i;
 341   scop_p scop;
 342
 343   for (i = 0; VEC_iterate (scop_p, scops, i, scop); i++)
 344     {
 345       remove_gbbs_in_scop (scop);
 346       free_sese (SCOP_REGION (scop));
 347       free_scop (scop);
 348     }
 349
 350   VEC_free (scop_p, heap, scops);
 351 }
 352
 353 /* Generates a polyhedral black box only if the bb contains interesting
 354    information.  */
 355
 356 static void
 357 try_generate_gimple_bb (scop_p scop, basic_block bb, sbitmap reductions)
 358 {
 359   VEC (data_reference_p, heap) *drs = VEC_alloc (data_reference_p, heap, 5);
 360   loop_p nest = outermost_loop_in_sese (SCOP_REGION (scop), bb);
 361   gimple_stmt_iterator gsi;
 362
 363   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 364     {
 365       gimple stmt = gsi_stmt (gsi);
 366       if (!is_gimple_debug (stmt))
 367         graphite_find_data_references_in_stmt (nest, stmt, &drs);
 368     }
 369
 370   if (!graphite_stmt_p (SCOP_REGION (scop), bb, drs))
 371     free_data_refs (drs);
 372   else
 373     new_poly_bb (scop, new_gimple_bb (bb, drs), TEST_BIT (reductions,
 374                                                           bb->index));
 375 }
 376
 377 /* Returns true if all predecessors of BB, that are not dominated by BB, are
 378    marked in MAP.  The predecessors dominated by BB are loop latches and will
 379    be handled after BB.  */
 380
 381 static bool
 382 all_non_dominated_preds_marked_p (basic_block bb, sbitmap map)
 383 {
 384   edge e;
 385   edge_iterator ei;
 386
 387   FOR_EACH_EDGE (e, ei, bb->preds)
 388     if (!TEST_BIT (map, e->src->index)
 389         && !dominated_by_p (CDI_DOMINATORS, e->src, bb))
 390         return false;
 391
 392   return true;
 393 }
 394
 395 /* Compare the depth of two basic_block's P1 and P2.  */
 396
 397 static int
 398 compare_bb_depths (const void *p1, const void *p2)
 399 {
 400   const_basic_block const bb1 = *(const_basic_block const*)p1;
 401   const_basic_block const bb2 = *(const_basic_block const*)p2;
 402   int d1 = loop_depth (bb1->loop_father);
 403   int d2 = loop_depth (bb2->loop_father);
 404
 405   if (d1 < d2)
 406     return 1;
 407
 408   if (d1 > d2)
 409     return -1;
 410
 411   return 0;
 412 }
 413
 414 /* Sort the basic blocks from DOM such that the first are the ones at
 415    a deepest loop level.  */
 416
 417 static void
 418 graphite_sort_dominated_info (VEC (basic_block, heap) *dom)
 419 {
 420   size_t len = VEC_length (basic_block, dom);
 421
 422   qsort (VEC_address (basic_block, dom), len, sizeof (basic_block),
 423          compare_bb_depths);
 424 }
 425
 426 /* Recursive helper function for build_scops_bbs.  */
 427
 428 static void
 429 build_scop_bbs_1 (scop_p scop, sbitmap visited, basic_block bb, sbitmap reductions)
 430 {
 431   sese region = SCOP_REGION (scop);
 432   VEC (basic_block, heap) *dom;
 433
 434   if (TEST_BIT (visited, bb->index)
 435       || !bb_in_sese_p (bb, region))
 436     return;
 437
 438   try_generate_gimple_bb (scop, bb, reductions);
 439   SET_BIT (visited, bb->index);
 440
 441   dom = get_dominated_by (CDI_DOMINATORS, bb);
 442
 443   if (dom == NULL)
 444     return;
 445
 446   graphite_sort_dominated_info (dom);
 447
 448   while (!VEC_empty (basic_block, dom))
 449     {
 450       int i;
 451       basic_block dom_bb;
 452
 453       for (i = 0; VEC_iterate (basic_block, dom, i, dom_bb); i++)
 454         if (all_non_dominated_preds_marked_p (dom_bb, visited))
 455           {
 456             build_scop_bbs_1 (scop, visited, dom_bb, reductions);
 457             VEC_unordered_remove (basic_block, dom, i);
 458             break;
 459           }
 460     }
 461
 462   VEC_free (basic_block, heap, dom);
 463 }
 464
 465 /* Gather the basic blocks belonging to the SCOP.  */
 466
 467 static void
 468 build_scop_bbs (scop_p scop, sbitmap reductions)
 469 {
 470   sbitmap visited = sbitmap_alloc (last_basic_block);
 471   sese region = SCOP_REGION (scop);
 472
 473   sbitmap_zero (visited);
 474   build_scop_bbs_1 (scop, visited, SESE_ENTRY_BB (region), reductions);
 475   sbitmap_free (visited);
 476 }
 477
 478 /* Converts the STATIC_SCHEDULE of PBB into a scattering polyhedron.
 479    We generate SCATTERING_DIMENSIONS scattering dimensions.
 480
 481    CLooG 0.15.0 and previous versions require, that all
 482    scattering functions of one CloogProgram have the same number of
 483    scattering dimensions, therefore we allow to specify it.  This
 484    should be removed in future versions of CLooG.
 485
 486    The scattering polyhedron consists of these dimensions: scattering,
 487    loop_iterators, parameters.
 488
 489    Example:
 490
 491    | scattering_dimensions = 5
 492    | used_scattering_dimensions = 3
 493    | nb_iterators = 1
 494    | scop_nb_params = 2
 495    |
 496    | Schedule:
 497    |   i
 498    | 4 5
 499    |
 500    | Scattering polyhedron:
 501    |
 502    | scattering: {s1, s2, s3, s4, s5}
 503    | loop_iterators: {i}
 504    | parameters: {p1, p2}
 505    |
 506    | s1  s2  s3  s4  s5  i   p1  p2  1
 507    | 1   0   0   0   0   0   0   0  -4  = 0
 508    | 0   1   0   0   0  -1   0   0   0  = 0
 509    | 0   0   1   0   0   0   0   0  -5  = 0  */
 510
 511 static void
 512 build_pbb_scattering_polyhedrons (ppl_Linear_Expression_t static_schedule,
 513                                   poly_bb_p pbb, int scattering_dimensions)
 514 {
 515   int i;
 516   scop_p scop = PBB_SCOP (pbb);
 517   int nb_iterators = pbb_dim_iter_domain (pbb);
 518   int used_scattering_dimensions = nb_iterators * 2 + 1;
 519   int nb_params = scop_nb_params (scop);
 520   ppl_Coefficient_t c;
 521   ppl_dimension_type dim = scattering_dimensions + nb_iterators + nb_params;
 522   Value v;
 523
 524   gcc_assert (scattering_dimensions >= used_scattering_dimensions);
 525
 526   value_init (v);
 527   ppl_new_Coefficient (&c);
 528   PBB_TRANSFORMED (pbb) = poly_scattering_new ();
 529   ppl_new_C_Polyhedron_from_space_dimension
 530     (&PBB_TRANSFORMED_SCATTERING (pbb), dim, 0);
 531
 532   PBB_NB_SCATTERING_TRANSFORM (pbb) = scattering_dimensions;
 533
 534   for (i = 0; i < scattering_dimensions; i++)
 535     {
 536       ppl_Constraint_t cstr;
 537       ppl_Linear_Expression_t expr;
 538
 539       ppl_new_Linear_Expression_with_dimension (&expr, dim);
 540       value_set_si (v, 1);
 541       ppl_assign_Coefficient_from_mpz_t (c, v);
 542       ppl_Linear_Expression_add_to_coefficient (expr, i, c);
 543
 544       /* Textual order inside this loop.  */
 545       if ((i % 2) == 0)
 546         {
 547           ppl_Linear_Expression_coefficient (static_schedule, i / 2, c);
 548           ppl_Coefficient_to_mpz_t (c, v);
 549           value_oppose (v, v);
 550           ppl_assign_Coefficient_from_mpz_t (c, v);
 551           ppl_Linear_Expression_add_to_inhomogeneous (expr, c);
 552         }
 553
 554       /* Iterations of this loop.  */
 555       else /* if ((i % 2) == 1) */
 556         {
 557           int loop = (i - 1) / 2;
 558
 559           value_set_si (v, -1);
 560           ppl_assign_Coefficient_from_mpz_t (c, v);
 561           ppl_Linear_Expression_add_to_coefficient
 562             (expr, scattering_dimensions + loop, c);
 563         }
 564
 565       ppl_new_Constraint (&cstr, expr, PPL_CONSTRAINT_TYPE_EQUAL);
 566       ppl_Polyhedron_add_constraint (PBB_TRANSFORMED_SCATTERING (pbb), cstr);
 567       ppl_delete_Linear_Expression (expr);
 568       ppl_delete_Constraint (cstr);
 569     }
 570
 571   value_clear (v);
 572   ppl_delete_Coefficient (c);
 573
 574   PBB_ORIGINAL (pbb) = poly_scattering_copy (PBB_TRANSFORMED (pbb));
 575 }
 576
 577 /* Build for BB the static schedule.
 578
 579    The static schedule is a Dewey numbering of the abstract syntax
 580    tree: http://en.wikipedia.org/wiki/Dewey_Decimal_Classification
 581
 582    The following example informally defines the static schedule:
 583
 584    A
 585    for (i: ...)
 586      {
 587        for (j: ...)
 588          {
 589            B
 590            C
 591          }
 592
 593        for (k: ...)
 594          {
 595            D
 596            E
 597          }
 598      }
 599    F
 600
 601    Static schedules for A to F:
 602
 603      DEPTH
 604      0 1 2
 605    A 0
 606    B 1 0 0
 607    C 1 0 1
 608    D 1 1 0
 609    E 1 1 1
 610    F 2
 611 */
 612
 613 static void
 614 build_scop_scattering (scop_p scop)
 615 {
 616   int i;
 617   poly_bb_p pbb;
 618   gimple_bb_p previous_gbb = NULL;
 619   ppl_Linear_Expression_t static_schedule;
 620   ppl_Coefficient_t c;
 621   Value v;
 622
 623   value_init (v);
 624   ppl_new_Coefficient (&c);
 625   ppl_new_Linear_Expression (&static_schedule);
 626
 627   /* We have to start schedules at 0 on the first component and
 628      because we cannot compare_prefix_loops against a previous loop,
 629      prefix will be equal to zero, and that index will be
 630      incremented before copying.  */
 631   value_set_si (v, -1);
 632   ppl_assign_Coefficient_from_mpz_t (c, v);
 633   ppl_Linear_Expression_add_to_coefficient (static_schedule, 0, c);
 634
 635   for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
 636     {
 637       gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
 638       ppl_Linear_Expression_t common;
 639       int prefix;
 640       int nb_scat_dims = pbb_dim_iter_domain (pbb) * 2 + 1;
 641
 642       if (previous_gbb)
 643         prefix = nb_common_loops (SCOP_REGION (scop), previous_gbb, gbb);
 644       else
 645         prefix = 0;
 646
 647       previous_gbb = gbb;
 648       ppl_new_Linear_Expression_with_dimension (&common, prefix + 1);
 649       ppl_assign_Linear_Expression_from_Linear_Expression (common,
 650                                                            static_schedule);
 651
 652       value_set_si (v, 1);
 653       ppl_assign_Coefficient_from_mpz_t (c, v);
 654       ppl_Linear_Expression_add_to_coefficient (common, prefix, c);
 655       ppl_assign_Linear_Expression_from_Linear_Expression (static_schedule,
 656                                                            common);
 657
 658       build_pbb_scattering_polyhedrons (common, pbb, nb_scat_dims);
 659
 660       ppl_delete_Linear_Expression (common);
 661     }
 662
 663   value_clear (v);
 664   ppl_delete_Coefficient (c);
 665   ppl_delete_Linear_Expression (static_schedule);
 666 }
 667
 668 /* Add the value K to the dimension D of the linear expression EXPR.  */
 669
 670 static void
 671 add_value_to_dim (ppl_dimension_type d, ppl_Linear_Expression_t expr,
 672                   Value k)
 673 {
 674   Value val;
 675   ppl_Coefficient_t coef;
 676
 677   ppl_new_Coefficient (&coef);
 678   ppl_Linear_Expression_coefficient (expr, d, coef);
 679   value_init (val);
 680   ppl_Coefficient_to_mpz_t (coef, val);
 681
 682   value_addto (val, val, k);
 683
 684   ppl_assign_Coefficient_from_mpz_t (coef, val);
 685   ppl_Linear_Expression_add_to_coefficient (expr, d, coef);
 686   value_clear (val);
 687   ppl_delete_Coefficient (coef);
 688 }
 689
 690 /* In the context of scop S, scan E, the right hand side of a scalar
 691    evolution function in loop VAR, and translate it to a linear
 692    expression EXPR.  */
 693
 694 static void
 695 scan_tree_for_params_right_scev (sese s, tree e, int var,
 696                                  ppl_Linear_Expression_t expr)
 697 {
 698   if (expr)
 699     {
 700       loop_p loop = get_loop (var);
 701       ppl_dimension_type l = sese_loop_depth (s, loop) - 1;
 702       Value val;
 703
 704       /* Scalar evolutions should happen in the sese region.  */
 705       gcc_assert (sese_loop_depth (s, loop) > 0);
 706
 707       /* We can not deal with parametric strides like:
 708
 709       | p = parameter;
 710       |
 711       | for i:
 712       |   a [i * p] = ...   */
 713       gcc_assert (TREE_CODE (e) == INTEGER_CST);
 714
 715       value_init (val);
 716       value_set_si (val, int_cst_value (e));
 717       add_value_to_dim (l, expr, val);
 718       value_clear (val);
 719     }
 720 }
 721
 722 /* Scan the integer constant CST, and add it to the inhomogeneous part of the
 723    linear expression EXPR.  K is the multiplier of the constant.  */
 724
 725 static void
 726 scan_tree_for_params_int (tree cst, ppl_Linear_Expression_t expr, Value k)
 727 {
 728   Value val;
 729   ppl_Coefficient_t coef;
 730   int v = int_cst_value (cst);
 731
 732   value_init (val);
 733   value_set_si (val, 0);
 734
 735   /* Necessary to not get "-1 = 2^n - 1". */
 736   if (v < 0)
 737     value_sub_int (val, val, -v);
 738   else
 739     value_add_int (val, val, v);
 740
 741   value_multiply (val, val, k);
 742   ppl_new_Coefficient (&coef);
 743   ppl_assign_Coefficient_from_mpz_t (coef, val);
 744   ppl_Linear_Expression_add_to_inhomogeneous (expr, coef);
 745   value_clear (val);
 746   ppl_delete_Coefficient (coef);
 747 }
 748
 749 /* When parameter NAME is in REGION, returns its index in SESE_PARAMS.
 750    Otherwise returns -1.  */
 751
 752 static inline int
 753 parameter_index_in_region_1 (tree name, sese region)
 754 {
 755   int i;
 756   tree p;
 757
 758   gcc_assert (TREE_CODE (name) == SSA_NAME);
 759
 760   for (i = 0; VEC_iterate (tree, SESE_PARAMS (region), i, p); i++)
 761     if (p == name)
 762       return i;
 763
 764   return -1;
 765 }
 766
 767 /* When the parameter NAME is in REGION, returns its index in
 768    SESE_PARAMS.  Otherwise this function inserts NAME in SESE_PARAMS
 769    and returns the index of NAME.  */
 770
 771 static int
 772 parameter_index_in_region (tree name, sese region)
 773 {
 774   int i;
 775
 776   gcc_assert (TREE_CODE (name) == SSA_NAME);
 777
 778   i = parameter_index_in_region_1 (name, region);
 779   if (i != -1)
 780     return i;
 781
 782   gcc_assert (SESE_ADD_PARAMS (region));
 783
 784   i = VEC_length (tree, SESE_PARAMS (region));
 785   VEC_safe_push (tree, heap, SESE_PARAMS (region), name);
 786   return i;
 787 }
 788
 789 /* In the context of sese S, scan the expression E and translate it to
 790    a linear expression C.  When parsing a symbolic multiplication, K
 791    represents the constant multiplier of an expression containing
 792    parameters.  */
 793
 794 static void
 795 scan_tree_for_params (sese s, tree e, ppl_Linear_Expression_t c,
 796                       Value k)
 797 {
 798   if (e == chrec_dont_know)
 799     return;
 800
 801   switch (TREE_CODE (e))
 802     {
 803     case POLYNOMIAL_CHREC:
 804       scan_tree_for_params_right_scev (s, CHREC_RIGHT (e),
 805                                        CHREC_VARIABLE (e), c);
 806       scan_tree_for_params (s, CHREC_LEFT (e), c, k);
 807       break;
 808
 809     case MULT_EXPR:
 810       if (chrec_contains_symbols (TREE_OPERAND (e, 0)))
 811         {
 812           if (c)
 813             {
 814               Value val;
 815               gcc_assert (host_integerp (TREE_OPERAND (e, 1), 0));
 816               value_init (val);
 817               value_set_si (val, int_cst_value (TREE_OPERAND (e, 1)));
 818               value_multiply (val, val, k);
 819               scan_tree_for_params (s, TREE_OPERAND (e, 0), c, val);
 820               value_clear (val);
 821             }
 822           else
 823             scan_tree_for_params (s, TREE_OPERAND (e, 0), c, k);
 824         }
 825       else
 826         {
 827           if (c)
 828             {
 829               Value val;
 830               gcc_assert (host_integerp (TREE_OPERAND (e, 0), 0));
 831               value_init (val);
 832               value_set_si (val, int_cst_value (TREE_OPERAND (e, 0)));
 833               value_multiply (val, val, k);
 834               scan_tree_for_params (s, TREE_OPERAND (e, 1), c, val);
 835               value_clear (val);
 836             }
 837           else
 838             scan_tree_for_params (s, TREE_OPERAND (e, 1), c, k);
 839         }
 840       break;
 841
 842     case PLUS_EXPR:
 843     case POINTER_PLUS_EXPR:
 844       scan_tree_for_params (s, TREE_OPERAND (e, 0), c, k);
 845       scan_tree_for_params (s, TREE_OPERAND (e, 1), c, k);
 846       break;
 847
 848     case MINUS_EXPR:
 849       {
 850         ppl_Linear_Expression_t tmp_expr = NULL;
 851
 852         if (c)
 853           {
 854             ppl_dimension_type dim;
 855             ppl_Linear_Expression_space_dimension (c, &dim);
 856             ppl_new_Linear_Expression_with_dimension (&tmp_expr, dim);
 857           }
 858
 859         scan_tree_for_params (s, TREE_OPERAND (e, 0), c, k);
 860         scan_tree_for_params (s, TREE_OPERAND (e, 1), tmp_expr, k);
 861
 862         if (c)
 863           {
 864             ppl_subtract_Linear_Expression_from_Linear_Expression (c,
 865                                                                    tmp_expr);
 866             ppl_delete_Linear_Expression (tmp_expr);
 867           }
 868
 869         break;
 870       }
 871
 872     case NEGATE_EXPR:
 873       {
 874         ppl_Linear_Expression_t tmp_expr = NULL;
 875
 876         if (c)
 877           {
 878             ppl_dimension_type dim;
 879             ppl_Linear_Expression_space_dimension (c, &dim);
 880             ppl_new_Linear_Expression_with_dimension (&tmp_expr, dim);
 881           }
 882
 883         scan_tree_for_params (s, TREE_OPERAND (e, 0), tmp_expr, k);
 884
 885         if (c)
 886           {
 887             ppl_subtract_Linear_Expression_from_Linear_Expression (c,
 888                                                                    tmp_expr);
 889             ppl_delete_Linear_Expression (tmp_expr);
 890           }
 891
 892         break;
 893       }
 894
 895     case BIT_NOT_EXPR:
 896       {
 897         ppl_Linear_Expression_t tmp_expr = NULL;
 898
 899         if (c)
 900           {
 901             ppl_dimension_type dim;
 902             ppl_Linear_Expression_space_dimension (c, &dim);
 903             ppl_new_Linear_Expression_with_dimension (&tmp_expr, dim);
 904           }
 905
 906         scan_tree_for_params (s, TREE_OPERAND (e, 0), tmp_expr, k);
 907
 908         if (c)
 909           {
 910             ppl_Coefficient_t coef;
 911             Value minus_one;
 912
 913             ppl_subtract_Linear_Expression_from_Linear_Expression (c,
 914                                                                    tmp_expr);
 915             ppl_delete_Linear_Expression (tmp_expr);
 916             value_init (minus_one);
 917             value_set_si (minus_one, -1);
 918             ppl_new_Coefficient_from_mpz_t (&coef, minus_one);
 919             ppl_Linear_Expression_add_to_inhomogeneous (c, coef);
 920             value_clear (minus_one);
 921             ppl_delete_Coefficient (coef);
 922           }
 923
 924         break;
 925       }
 926
 927     case SSA_NAME:
 928       {
 929         ppl_dimension_type p = parameter_index_in_region (e, s);
 930
 931         if (c)
 932           {
 933             ppl_dimension_type dim;
 934             ppl_Linear_Expression_space_dimension (c, &dim);
 935             p += dim - sese_nb_params (s);
 936             add_value_to_dim (p, c, k);
 937           }
 938         break;
 939       }
 940
 941     case INTEGER_CST:
 942       if (c)
 943         scan_tree_for_params_int (e, c, k);
 944       break;
 945
 946     CASE_CONVERT:
 947     case NON_LVALUE_EXPR:
 948       scan_tree_for_params (s, TREE_OPERAND (e, 0), c, k);
 949       break;
 950
 951    default:
 952       gcc_unreachable ();
 953       break;
 954     }
 955 }
 956
 957 /* Find parameters with respect to REGION in BB. We are looking in memory
 958    access functions, conditions and loop bounds.  */
 959
 960 static void
 961 find_params_in_bb (sese region, gimple_bb_p gbb)
 962 {
 963   int i;
 964   unsigned j;
 965   data_reference_p dr;
 966   gimple stmt;
 967   loop_p loop = GBB_BB (gbb)->loop_father;
 968   Value one;
 969
 970   value_init (one);
 971   value_set_si (one, 1);
 972
 973   /* Find parameters in the access functions of data references.  */
 974   for (i = 0; VEC_iterate (data_reference_p, GBB_DATA_REFS (gbb), i, dr); i++)
 975     for (j = 0; j < DR_NUM_DIMENSIONS (dr); j++)
 976       scan_tree_for_params (region, DR_ACCESS_FN (dr, j), NULL, one);
 977
 978   /* Find parameters in conditional statements.  */
 979   for (i = 0; VEC_iterate (gimple, GBB_CONDITIONS (gbb), i, stmt); i++)
 980     {
 981       tree lhs = scalar_evolution_in_region (region, loop,
 982                                              gimple_cond_lhs (stmt));
 983       tree rhs = scalar_evolution_in_region (region, loop,
 984                                              gimple_cond_rhs (stmt));
 985
 986       scan_tree_for_params (region, lhs, NULL, one);
 987       scan_tree_for_params (region, rhs, NULL, one);
 988     }
 989
 990   value_clear (one);
 991 }
 992
 993 /* Record the parameters used in the SCOP.  A variable is a parameter
 994    in a scop if it does not vary during the execution of that scop.  */
 995
 996 static void
 997 find_scop_parameters (scop_p scop)
 998 {
 999   poly_bb_p pbb;
1000   unsigned i;
1001   sese region = SCOP_REGION (scop);
1002   struct loop *loop;
1003   Value one;
1004
1005   value_init (one);
1006   value_set_si (one, 1);
1007
1008   /* Find the parameters used in the loop bounds.  */
1009   for (i = 0; VEC_iterate (loop_p, SESE_LOOP_NEST (region), i, loop); i++)
1010     {
1011       tree nb_iters = number_of_latch_executions (loop);
1012
1013       if (!chrec_contains_symbols (nb_iters))
1014         continue;
1015
1016       nb_iters = scalar_evolution_in_region (region, loop, nb_iters);
1017       scan_tree_for_params (region, nb_iters, NULL, one);
1018     }
1019
1020   value_clear (one);
1021
1022   /* Find the parameters used in data accesses.  */
1023   for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
1024     find_params_in_bb (region, PBB_BLACK_BOX (pbb));
1025
1026   scop_set_nb_params (scop, sese_nb_params (region));
1027   SESE_ADD_PARAMS (region) = false;
1028
1029   ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension
1030     (&SCOP_CONTEXT (scop), scop_nb_params (scop), 0);
1031 }
1032
1033 /* Returns a gimple_bb from BB.  */
1034
1035 static inline gimple_bb_p
1036 gbb_from_bb (basic_block bb)
1037 {
1038   return (gimple_bb_p) bb->aux;
1039 }
1040
1041 /* Builds the constraint polyhedra for LOOP in SCOP.  OUTER_PH gives
1042    the constraints for the surrounding loops.  */
1043
1044 static void
1045 build_loop_iteration_domains (scop_p scop, struct loop *loop,
1046                               ppl_Polyhedron_t outer_ph, int nb,
1047                               ppl_Pointset_Powerset_C_Polyhedron_t *domains)
1048 {
1049   int i;
1050   ppl_Polyhedron_t ph;
1051   tree nb_iters = number_of_latch_executions (loop);
1052   ppl_dimension_type dim = nb + 1 + scop_nb_params (scop);
1053   sese region = SCOP_REGION (scop);
1054
1055   {
1056     ppl_const_Constraint_System_t pcs;
1057     ppl_dimension_type *map
1058       = (ppl_dimension_type *) XNEWVEC (ppl_dimension_type, dim);
1059
1060     ppl_new_C_Polyhedron_from_space_dimension (&ph, dim, 0);
1061     ppl_Polyhedron_get_constraints (outer_ph, &pcs);
1062     ppl_Polyhedron_add_constraints (ph, pcs);
1063
1064     for (i = 0; i < (int) nb; i++)
1065       map[i] = i;
1066     for (i = (int) nb; i < (int) dim - 1; i++)
1067       map[i] = i + 1;
1068     map[dim - 1] = nb;
1069
1070     ppl_Polyhedron_map_space_dimensions (ph, map, dim);
1071     free (map);
1072   }
1073
1074   /* 0 <= loop_i */
1075   {
1076     ppl_Constraint_t lb;
1077     ppl_Linear_Expression_t lb_expr;
1078
1079     ppl_new_Linear_Expression_with_dimension (&lb_expr, dim);
1080     ppl_set_coef (lb_expr, nb, 1);
1081     ppl_new_Constraint (&lb, lb_expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1082     ppl_delete_Linear_Expression (lb_expr);
1083     ppl_Polyhedron_add_constraint (ph, lb);
1084     ppl_delete_Constraint (lb);
1085   }
1086
1087   if (TREE_CODE (nb_iters) == INTEGER_CST)
1088     {
1089       ppl_Constraint_t ub;
1090       ppl_Linear_Expression_t ub_expr;
1091
1092       ppl_new_Linear_Expression_with_dimension (&ub_expr, dim);
1093
1094       /* loop_i <= cst_nb_iters */
1095       ppl_set_coef (ub_expr, nb, -1);
1096       ppl_set_inhomogeneous_tree (ub_expr, nb_iters);
1097       ppl_new_Constraint (&ub, ub_expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1098       ppl_Polyhedron_add_constraint (ph, ub);
1099       ppl_delete_Linear_Expression (ub_expr);
1100       ppl_delete_Constraint (ub);
1101     }
1102   else if (!chrec_contains_undetermined (nb_iters))
1103     {
1104       Value one;
1105       ppl_Constraint_t ub;
1106       ppl_Linear_Expression_t ub_expr;
1107       double_int nit;
1108
1109       value_init (one);
1110       value_set_si (one, 1);
1111       ppl_new_Linear_Expression_with_dimension (&ub_expr, dim);
1112       nb_iters = scalar_evolution_in_region (region, loop, nb_iters);
1113       scan_tree_for_params (SCOP_REGION (scop), nb_iters, ub_expr, one);
1114       value_clear (one);
1115
1116       /* N <= estimated_nb_iters
1117
1118          FIXME: This is a workaround that should go away once we will
1119          have the PIP algorithm.  */
1120       if (estimated_loop_iterations (loop, true, &nit))
1121         {
1122           Value val;
1123           ppl_Linear_Expression_t nb_iters_le;
1124           ppl_Polyhedron_t pol;
1125           graphite_dim_t n = scop_nb_params (scop);
1126           ppl_Coefficient_t coef;
1127
1128           ppl_new_C_Polyhedron_from_space_dimension (&pol, dim, 0);
1129           ppl_new_Linear_Expression_from_Linear_Expression (&nb_iters_le,
1130                                                             ub_expr);
1131
1132           /* Construct the negated number of last iteration in VAL.  */
1133           value_init (val);
1134           mpz_set_double_int (val, nit, false);
1135           value_sub_int (val, val, 1);
1136           value_oppose (val, val);
1137
1138           /* NB_ITERS_LE holds number of last iteration in parametrical form.
1139           Subtract estimated number of last iteration and assert that result
1140           is not positive.  */
1141           ppl_new_Coefficient_from_mpz_t (&coef, val);
1142           ppl_Linear_Expression_add_to_inhomogeneous (nb_iters_le, coef);
1143           ppl_delete_Coefficient (coef);
1144           ppl_new_Constraint (&ub, nb_iters_le,
1145                               PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL);
1146           ppl_Polyhedron_add_constraint (pol, ub);
1147
1148           /* Remove all but last N dimensions from POL to obtain constraints
1149              on parameters.  */
1150             {
1151               ppl_dimension_type *dims = XNEWVEC (ppl_dimension_type, dim - n);
1152               graphite_dim_t i;
1153               for (i = 0; i < dim - n; i++)
1154                 dims[i] = i;
1155               ppl_Polyhedron_remove_space_dimensions (pol, dims, dim - n);
1156               XDELETEVEC (dims);
1157             }
1158
1159           /* Add constraints on parameters to SCoP context.  */
1160             {
1161               ppl_Pointset_Powerset_C_Polyhedron_t constraints_ps;
1162               ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1163                (&constraints_ps, pol);
1164               ppl_Pointset_Powerset_C_Polyhedron_intersection_assign
1165                (SCOP_CONTEXT (scop), constraints_ps);
1166               ppl_delete_Pointset_Powerset_C_Polyhedron (constraints_ps);
1167             }
1168
1169           ppl_delete_Polyhedron (pol);
1170           ppl_delete_Linear_Expression (nb_iters_le);
1171           ppl_delete_Constraint (ub);
1172           value_clear (val);
1173         }
1174
1175       /* loop_i <= expr_nb_iters */
1176       ppl_set_coef (ub_expr, nb, -1);
1177       ppl_new_Constraint (&ub, ub_expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1178       ppl_Polyhedron_add_constraint (ph, ub);
1179       ppl_delete_Linear_Expression (ub_expr);
1180       ppl_delete_Constraint (ub);
1181     }
1182   else
1183     gcc_unreachable ();
1184
1185   if (loop->inner && loop_in_sese_p (loop->inner, region))
1186     build_loop_iteration_domains (scop, loop->inner, ph, nb + 1, domains);
1187
1188   if (nb != 0
1189       && loop->next
1190       && loop_in_sese_p (loop->next, region))
1191     build_loop_iteration_domains (scop, loop->next, outer_ph, nb, domains);
1192
1193   ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1194     (&domains[loop->num], ph);
1195
1196   ppl_delete_Polyhedron (ph);
1197 }
1198
1199 /* Returns a linear expression for tree T evaluated in PBB.  */
1200
1201 static ppl_Linear_Expression_t
1202 create_linear_expr_from_tree (poly_bb_p pbb, tree t)
1203 {
1204   Value one;
1205   ppl_Linear_Expression_t res;
1206   ppl_dimension_type dim;
1207   sese region = SCOP_REGION (PBB_SCOP (pbb));
1208   loop_p loop = pbb_loop (pbb);
1209
1210   dim = pbb_dim_iter_domain (pbb) + pbb_nb_params (pbb);
1211   ppl_new_Linear_Expression_with_dimension (&res, dim);
1212
1213   t = scalar_evolution_in_region (region, loop, t);
1214   gcc_assert (!automatically_generated_chrec_p (t));
1215
1216   value_init (one);
1217   value_set_si (one, 1);
1218   scan_tree_for_params (region, t, res, one);
1219   value_clear (one);
1220
1221   return res;
1222 }
1223
1224 /* Returns the ppl constraint type from the gimple tree code CODE.  */
1225
1226 static enum ppl_enum_Constraint_Type
1227 ppl_constraint_type_from_tree_code (enum tree_code code)
1228 {
1229   switch (code)
1230     {
1231     /* We do not support LT and GT to be able to work with C_Polyhedron.
1232        As we work on integer polyhedron "a < b" can be expressed by
1233        "a + 1 <= b".  */
1234     case LT_EXPR:
1235     case GT_EXPR:
1236       gcc_unreachable ();
1237
1238     case LE_EXPR:
1239       return PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL;
1240
1241     case GE_EXPR:
1242       return PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL;
1243
1244     case EQ_EXPR:
1245       return PPL_CONSTRAINT_TYPE_EQUAL;
1246
1247     default:
1248       gcc_unreachable ();
1249     }
1250 }
1251
1252 /* Add conditional statement STMT to PS.  It is evaluated in PBB and
1253    CODE is used as the comparison operator.  This allows us to invert the
1254    condition or to handle inequalities.  */
1255
1256 static void
1257 add_condition_to_domain (ppl_Pointset_Powerset_C_Polyhedron_t ps, gimple stmt,
1258                          poly_bb_p pbb, enum tree_code code)
1259 {
1260   Value v;
1261   ppl_Coefficient_t c;
1262   ppl_Linear_Expression_t left, right;
1263   ppl_Constraint_t cstr;
1264   enum ppl_enum_Constraint_Type type;
1265
1266   left = create_linear_expr_from_tree (pbb, gimple_cond_lhs (stmt));
1267   right = create_linear_expr_from_tree (pbb, gimple_cond_rhs (stmt));
1268
1269   /* If we have < or > expressions convert them to <= or >= by adding 1 to
1270      the left or the right side of the expression. */
1271   if (code == LT_EXPR)
1272     {
1273       value_init (v);
1274       value_set_si (v, 1);
1275       ppl_new_Coefficient (&c);
1276       ppl_assign_Coefficient_from_mpz_t (c, v);
1277       ppl_Linear_Expression_add_to_inhomogeneous (left, c);
1278       ppl_delete_Coefficient (c);
1279       value_clear (v);
1280
1281       code = LE_EXPR;
1282     }
1283   else if (code == GT_EXPR)
1284     {
1285       value_init (v);
1286       value_set_si (v, 1);
1287       ppl_new_Coefficient (&c);
1288       ppl_assign_Coefficient_from_mpz_t (c, v);
1289       ppl_Linear_Expression_add_to_inhomogeneous (right, c);
1290       ppl_delete_Coefficient (c);
1291       value_clear (v);
1292
1293       code = GE_EXPR;
1294     }
1295
1296   type = ppl_constraint_type_from_tree_code (code);
1297
1298   ppl_subtract_Linear_Expression_from_Linear_Expression (left, right);
1299
1300   ppl_new_Constraint (&cstr, left, type);
1301   ppl_Pointset_Powerset_C_Polyhedron_add_constraint (ps, cstr);
1302
1303   ppl_delete_Constraint (cstr);
1304   ppl_delete_Linear_Expression (left);
1305   ppl_delete_Linear_Expression (right);
1306 }
1307
1308 /* Add conditional statement STMT to pbb.  CODE is used as the comparision
1309    operator.  This allows us to invert the condition or to handle
1310    inequalities.  */
1311
1312 static void
1313 add_condition_to_pbb (poly_bb_p pbb, gimple stmt, enum tree_code code)
1314 {
1315   if (code == NE_EXPR)
1316     {
1317       ppl_Pointset_Powerset_C_Polyhedron_t left = PBB_DOMAIN (pbb);
1318       ppl_Pointset_Powerset_C_Polyhedron_t right;
1319       ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
1320         (&right, left);
1321       add_condition_to_domain (left, stmt, pbb, LT_EXPR);
1322       add_condition_to_domain (right, stmt, pbb, GT_EXPR);
1323       ppl_Pointset_Powerset_C_Polyhedron_upper_bound_assign (left,
1324                                                                right);
1325       ppl_delete_Pointset_Powerset_C_Polyhedron (right);
1326     }
1327   else
1328     add_condition_to_domain (PBB_DOMAIN (pbb), stmt, pbb, code);
1329 }
1330
1331 /* Add conditions to the domain of PBB.  */
1332
1333 static void
1334 add_conditions_to_domain (poly_bb_p pbb)
1335 {
1336   unsigned int i;
1337   gimple stmt;
1338   gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
1339   VEC (gimple, heap) *conditions = GBB_CONDITIONS (gbb);
1340
1341   if (VEC_empty (gimple, conditions))
1342     return;
1343
1344   for (i = 0; VEC_iterate (gimple, conditions, i, stmt); i++)
1345     switch (gimple_code (stmt))
1346       {
1347       case GIMPLE_COND:
1348           {
1349             enum tree_code code = gimple_cond_code (stmt);
1350
1351             /* The conditions for ELSE-branches are inverted.  */
1352             if (VEC_index (gimple, gbb->condition_cases, i) == NULL)
1353               code = invert_tree_comparison (code, false);
1354
1355             add_condition_to_pbb (pbb, stmt, code);
1356             break;
1357           }
1358
1359       case GIMPLE_SWITCH:
1360         /* Switch statements are not supported right now - fall throught.  */
1361
1362       default:
1363         gcc_unreachable ();
1364         break;
1365       }
1366 }
1367
1368 /* Structure used to pass data to dom_walk.  */
1369
1370 struct bsc
1371 {
1372   VEC (gimple, heap) **conditions, **cases;
1373   sese region;
1374 };
1375
1376 /* Returns non NULL when BB has a single predecessor and the last
1377    statement of that predecessor is a COND_EXPR.  */
1378
1379 static gimple
1380 single_pred_cond (basic_block bb)
1381 {
1382   if (single_pred_p (bb))
1383     {
1384       edge e = single_pred_edge (bb);
1385       basic_block pred = e->src;
1386       gimple stmt = last_stmt (pred);
1387
1388       if (stmt && gimple_code (stmt) == GIMPLE_COND)
1389         return stmt;
1390     }
1391   return NULL;
1392 }
1393
1394 /* Call-back for dom_walk executed before visiting the dominated
1395    blocks.  */
1396
1397 static void
1398 build_sese_conditions_before (struct dom_walk_data *dw_data,
1399                               basic_block bb)
1400 {
1401   struct bsc *data = (struct bsc *) dw_data->global_data;
1402   VEC (gimple, heap) **conditions = data->conditions;
1403   VEC (gimple, heap) **cases = data->cases;
1404   gimple_bb_p gbb = gbb_from_bb (bb);
1405   gimple stmt = single_pred_cond (bb);
1406
1407   if (!bb_in_sese_p (bb, data->region))
1408     return;
1409
1410   if (stmt)
1411     {
1412       edge e = single_pred_edge (bb);
1413
1414       VEC_safe_push (gimple, heap, *conditions, stmt);
1415
1416       if (e->flags & EDGE_TRUE_VALUE)
1417         VEC_safe_push (gimple, heap, *cases, stmt);
1418       else
1419         VEC_safe_push (gimple, heap, *cases, NULL);
1420     }
1421
1422   if (gbb)
1423     {
1424       GBB_CONDITIONS (gbb) = VEC_copy (gimple, heap, *conditions);
1425       GBB_CONDITION_CASES (gbb) = VEC_copy (gimple, heap, *cases);
1426     }
1427 }
1428
1429 /* Call-back for dom_walk executed after visiting the dominated
1430    blocks.  */
1431
1432 static void
1433 build_sese_conditions_after (struct dom_walk_data *dw_data,
1434                              basic_block bb)
1435 {
1436   struct bsc *data = (struct bsc *) dw_data->global_data;
1437   VEC (gimple, heap) **conditions = data->conditions;
1438   VEC (gimple, heap) **cases = data->cases;
1439
1440   if (!bb_in_sese_p (bb, data->region))
1441     return;
1442
1443   if (single_pred_cond (bb))
1444     {
1445       VEC_pop (gimple, *conditions);
1446       VEC_pop (gimple, *cases);
1447     }
1448 }
1449
1450 /* Record all conditions in REGION.  */
1451
1452 static void
1453 build_sese_conditions (sese region)
1454 {
1455   struct dom_walk_data walk_data;
1456   VEC (gimple, heap) *conditions = VEC_alloc (gimple, heap, 3);
1457   VEC (gimple, heap) *cases = VEC_alloc (gimple, heap, 3);
1458   struct bsc data;
1459
1460   data.conditions = &conditions;
1461   data.cases = &cases;
1462   data.region = region;
1463
1464   walk_data.dom_direction = CDI_DOMINATORS;
1465   walk_data.initialize_block_local_data = NULL;
1466   walk_data.before_dom_children = build_sese_conditions_before;
1467   walk_data.after_dom_children = build_sese_conditions_after;
1468   walk_data.global_data = &data;
1469   walk_data.block_local_data_size = 0;
1470
1471   init_walk_dominator_tree (&walk_data);
1472   walk_dominator_tree (&walk_data, SESE_ENTRY_BB (region));
1473   fini_walk_dominator_tree (&walk_data);
1474
1475   VEC_free (gimple, heap, conditions);
1476   VEC_free (gimple, heap, cases);
1477 }
1478
1479 /* Traverses all the GBBs of the SCOP and add their constraints to the
1480    iteration domains.  */
1481
1482 static void
1483 add_conditions_to_constraints (scop_p scop)
1484 {
1485   int i;
1486   poly_bb_p pbb;
1487
1488   for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
1489     add_conditions_to_domain (pbb);
1490 }
1491
1492 /* Add constraints on the possible values of parameter P from the type
1493    of P.  */
1494
1495 static void
1496 add_param_constraints (scop_p scop, ppl_Polyhedron_t context, graphite_dim_t p)
1497 {
1498   ppl_Constraint_t cstr;
1499   ppl_Linear_Expression_t le;
1500   tree parameter = VEC_index (tree, SESE_PARAMS (SCOP_REGION (scop)), p);
1501   tree type = TREE_TYPE (parameter);
1502   tree lb = NULL_TREE;
1503   tree ub = NULL_TREE;
1504
1505   if (POINTER_TYPE_P (type) || !TYPE_MIN_VALUE (type))
1506     lb = lower_bound_in_type (type, type);
1507   else
1508     lb = TYPE_MIN_VALUE (type);
1509
1510   if (POINTER_TYPE_P (type) || !TYPE_MAX_VALUE (type))
1511     ub = upper_bound_in_type (type, type);
1512   else
1513     ub = TYPE_MAX_VALUE (type);
1514
1515   if (lb)
1516     {
1517       ppl_new_Linear_Expression_with_dimension (&le, scop_nb_params (scop));
1518       ppl_set_coef (le, p, -1);
1519       ppl_set_inhomogeneous_tree (le, lb);
1520       ppl_new_Constraint (&cstr, le, PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL);
1521       ppl_Polyhedron_add_constraint (context, cstr);
1522       ppl_delete_Linear_Expression (le);
1523       ppl_delete_Constraint (cstr);
1524     }
1525
1526   if (ub)
1527     {
1528       ppl_new_Linear_Expression_with_dimension (&le, scop_nb_params (scop));
1529       ppl_set_coef (le, p, -1);
1530       ppl_set_inhomogeneous_tree (le, ub);
1531       ppl_new_Constraint (&cstr, le, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1532       ppl_Polyhedron_add_constraint (context, cstr);
1533       ppl_delete_Linear_Expression (le);
1534       ppl_delete_Constraint (cstr);
1535     }
1536 }
1537
1538 /* Build the context of the SCOP.  The context usually contains extra
1539    constraints that are added to the iteration domains that constrain
1540    some parameters.  */
1541
1542 static void
1543 build_scop_context (scop_p scop)
1544 {
1545   ppl_Polyhedron_t context;
1546   ppl_Pointset_Powerset_C_Polyhedron_t ps;
1547   graphite_dim_t p, n = scop_nb_params (scop);
1548
1549   ppl_new_C_Polyhedron_from_space_dimension (&context, n, 0);
1550
1551   for (p = 0; p < n; p++)
1552     add_param_constraints (scop, context, p);
1553
1554   ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1555     (&ps, context);
1556   ppl_Pointset_Powerset_C_Polyhedron_intersection_assign
1557     (SCOP_CONTEXT (scop), ps);
1558
1559   ppl_delete_Pointset_Powerset_C_Polyhedron (ps);
1560   ppl_delete_Polyhedron (context);
1561 }
1562
1563 /* Build the iteration domains: the loops belonging to the current
1564    SCOP, and that vary for the execution of the current basic block.
1565    Returns false if there is no loop in SCOP.  */
1566
1567 static void
1568 build_scop_iteration_domain (scop_p scop)
1569 {
1570   struct loop *loop;
1571   sese region = SCOP_REGION (scop);
1572   int i;
1573   ppl_Polyhedron_t ph;
1574   poly_bb_p pbb;
1575   int nb_loops = number_of_loops ();
1576   ppl_Pointset_Powerset_C_Polyhedron_t *domains
1577     = XNEWVEC (ppl_Pointset_Powerset_C_Polyhedron_t, nb_loops);
1578
1579   for (i = 0; i < nb_loops; i++)
1580     domains[i] = NULL;
1581
1582   ppl_new_C_Polyhedron_from_space_dimension (&ph, scop_nb_params (scop), 0);
1583
1584   for (i = 0; VEC_iterate (loop_p, SESE_LOOP_NEST (region), i, loop); i++)
1585     if (!loop_in_sese_p (loop_outer (loop), region))
1586       build_loop_iteration_domains (scop, loop, ph, 0, domains);
1587
1588   for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
1589     if (domains[gbb_loop (PBB_BLACK_BOX (pbb))->num])
1590       ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
1591         (&PBB_DOMAIN (pbb), (ppl_const_Pointset_Powerset_C_Polyhedron_t)
1592          domains[gbb_loop (PBB_BLACK_BOX (pbb))->num]);
1593     else
1594       ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1595         (&PBB_DOMAIN (pbb), ph);
1596
1597   for (i = 0; i < nb_loops; i++)
1598     if (domains[i])
1599       ppl_delete_Pointset_Powerset_C_Polyhedron (domains[i]);
1600
1601   ppl_delete_Polyhedron (ph);
1602   free (domains);
1603 }
1604
1605 /* Add a constrain to the ACCESSES polyhedron for the alias set of
1606    data reference DR.  ACCESSP_NB_DIMS is the dimension of the
1607    ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1608    domain.  */
1609
1610 static void
1611 pdr_add_alias_set (ppl_Polyhedron_t accesses, data_reference_p dr,
1612                    ppl_dimension_type accessp_nb_dims,
1613                    ppl_dimension_type dom_nb_dims)
1614 {
1615   ppl_Linear_Expression_t alias;
1616   ppl_Constraint_t cstr;
1617   int alias_set_num = 0;
1618   base_alias_pair *bap = (base_alias_pair *)(dr->aux);
1619
1620   if (bap && bap->alias_set)
1621     alias_set_num = *(bap->alias_set);
1622
1623   ppl_new_Linear_Expression_with_dimension (&alias, accessp_nb_dims);
1624
1625   ppl_set_coef (alias, dom_nb_dims, 1);
1626   ppl_set_inhomogeneous (alias, -alias_set_num);
1627   ppl_new_Constraint (&cstr, alias, PPL_CONSTRAINT_TYPE_EQUAL);
1628   ppl_Polyhedron_add_constraint (accesses, cstr);
1629
1630   ppl_delete_Linear_Expression (alias);
1631   ppl_delete_Constraint (cstr);
1632 }
1633
1634 /* Add to ACCESSES polyhedron equalities defining the access functions
1635    to the memory.  ACCESSP_NB_DIMS is the dimension of the ACCESSES
1636    polyhedron, DOM_NB_DIMS is the dimension of the iteration domain.
1637    PBB is the poly_bb_p that contains the data reference DR.  */
1638
1639 static void
1640 pdr_add_memory_accesses (ppl_Polyhedron_t accesses, data_reference_p dr,
1641                          ppl_dimension_type accessp_nb_dims,
1642                          ppl_dimension_type dom_nb_dims,
1643                          poly_bb_p pbb)
1644 {
1645   int i, nb_subscripts = DR_NUM_DIMENSIONS (dr);
1646   Value v;
1647   scop_p scop = PBB_SCOP (pbb);
1648   sese region = SCOP_REGION (scop);
1649
1650   value_init (v);
1651
1652   for (i = 0; i < nb_subscripts; i++)
1653     {
1654       ppl_Linear_Expression_t fn, access;
1655       ppl_Constraint_t cstr;
1656       ppl_dimension_type subscript = dom_nb_dims + 1 + i;
1657       tree afn = DR_ACCESS_FN (dr, nb_subscripts - 1 - i);
1658
1659       ppl_new_Linear_Expression_with_dimension (&fn, dom_nb_dims);
1660       ppl_new_Linear_Expression_with_dimension (&access, accessp_nb_dims);
1661
1662       value_set_si (v, 1);
1663       scan_tree_for_params (region, afn, fn, v);
1664       ppl_assign_Linear_Expression_from_Linear_Expression (access, fn);
1665
1666       ppl_set_coef (access, subscript, -1);
1667       ppl_new_Constraint (&cstr, access, PPL_CONSTRAINT_TYPE_EQUAL);
1668       ppl_Polyhedron_add_constraint (accesses, cstr);
1669
1670       ppl_delete_Linear_Expression (fn);
1671       ppl_delete_Linear_Expression (access);
1672       ppl_delete_Constraint (cstr);
1673     }
1674
1675   value_clear (v);
1676 }
1677
1678 /* Add constrains representing the size of the accessed data to the
1679    ACCESSES polyhedron.  ACCESSP_NB_DIMS is the dimension of the
1680    ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
1681    domain.  */
1682
1683 static void
1684 pdr_add_data_dimensions (ppl_Polyhedron_t accesses, data_reference_p dr,
1685                          ppl_dimension_type accessp_nb_dims,
1686                          ppl_dimension_type dom_nb_dims)
1687 {
1688   tree ref = DR_REF (dr);
1689   int i, nb_subscripts = DR_NUM_DIMENSIONS (dr);
1690
1691   for (i = nb_subscripts - 1; i >= 0; i--, ref = TREE_OPERAND (ref, 0))
1692     {
1693       ppl_Linear_Expression_t expr;
1694       ppl_Constraint_t cstr;
1695       ppl_dimension_type subscript = dom_nb_dims + 1 + i;
1696       tree low, high;
1697
1698       if (TREE_CODE (ref) != ARRAY_REF)
1699         break;
1700
1701       low = array_ref_low_bound (ref);
1702
1703       /* subscript - low >= 0 */
1704       if (host_integerp (low, 0))
1705         {
1706           ppl_new_Linear_Expression_with_dimension (&expr, accessp_nb_dims);
1707           ppl_set_coef (expr, subscript, 1);
1708
1709           ppl_set_inhomogeneous (expr, -int_cst_value (low));
1710
1711           ppl_new_Constraint (&cstr, expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1712           ppl_Polyhedron_add_constraint (accesses, cstr);
1713           ppl_delete_Linear_Expression (expr);
1714           ppl_delete_Constraint (cstr);
1715         }
1716
1717       high = array_ref_up_bound (ref);
1718
1719       /* high - subscript >= 0 */
1720       if (high && host_integerp (high, 0)
1721           /* 1-element arrays at end of structures may extend over
1722              their declared size.  */
1723           && !(array_at_struct_end_p (ref)
1724                && operand_equal_p (low, high, 0)))
1725         {
1726           ppl_new_Linear_Expression_with_dimension (&expr, accessp_nb_dims);
1727           ppl_set_coef (expr, subscript, -1);
1728
1729           ppl_set_inhomogeneous (expr, int_cst_value (high));
1730
1731           ppl_new_Constraint (&cstr, expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
1732           ppl_Polyhedron_add_constraint (accesses, cstr);
1733           ppl_delete_Linear_Expression (expr);
1734           ppl_delete_Constraint (cstr);
1735         }
1736     }
1737 }
1738
1739 /* Build data accesses for DR in PBB.  */
1740
1741 static void
1742 build_poly_dr (data_reference_p dr, poly_bb_p pbb)
1743 {
1744   ppl_Polyhedron_t accesses;
1745   ppl_Pointset_Powerset_C_Polyhedron_t accesses_ps;
1746   ppl_dimension_type dom_nb_dims;
1747   ppl_dimension_type accessp_nb_dims;
1748   int dr_base_object_set;
1749
1750   ppl_Pointset_Powerset_C_Polyhedron_space_dimension (PBB_DOMAIN (pbb),
1751                                                       &dom_nb_dims);
1752   accessp_nb_dims = dom_nb_dims + 1 + DR_NUM_DIMENSIONS (dr);
1753
1754   ppl_new_C_Polyhedron_from_space_dimension (&accesses, accessp_nb_dims, 0);
1755
1756   pdr_add_alias_set (accesses, dr, accessp_nb_dims, dom_nb_dims);
1757   pdr_add_memory_accesses (accesses, dr, accessp_nb_dims, dom_nb_dims, pbb);
1758   pdr_add_data_dimensions (accesses, dr, accessp_nb_dims, dom_nb_dims);
1759
1760   ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&accesses_ps,
1761                                                             accesses);
1762   ppl_delete_Polyhedron (accesses);
1763
1764   if (dr->aux)
1765     dr_base_object_set = ((base_alias_pair *)(dr->aux))->base_obj_set;
1766
1767   new_poly_dr (pbb, dr_base_object_set, accesses_ps, DR_IS_READ (dr) ? PDR_READ : PDR_WRITE,
1768                dr, DR_NUM_DIMENSIONS (dr));
1769 }
1770
1771 /* Write to FILE the alias graph of data references in DIMACS format.  */
1772
1773 static inline bool
1774 write_alias_graph_to_ascii_dimacs (FILE *file, char *comment,
1775                                    VEC (data_reference_p, heap) *drs)
1776 {
1777   int num_vertex = VEC_length (data_reference_p, drs);
1778   int edge_num = 0;
1779   data_reference_p dr1, dr2;
1780   int i, j;
1781
1782   if (num_vertex == 0)
1783     return true;
1784
1785   for (i = 0; VEC_iterate (data_reference_p, drs, i, dr1); i++)
1786     for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
1787       if (dr_may_alias_p (dr1, dr2))
1788         edge_num++;
1789
1790   fprintf (file, "$\n");
1791
1792   if (comment)
1793     fprintf (file, "c %s\n", comment);
1794
1795   fprintf (file, "p edge %d %d\n", num_vertex, edge_num);
1796
1797   for (i = 0; VEC_iterate (data_reference_p, drs, i, dr1); i++)
1798     for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
1799       if (dr_may_alias_p (dr1, dr2))
1800         fprintf (file, "e %d %d\n", i + 1, j + 1);
1801
1802   return true;
1803 }
1804
1805 /* Write to FILE the alias graph of data references in DOT format.  */
1806
1807 static inline bool
1808 write_alias_graph_to_ascii_dot (FILE *file, char *comment,
1809                                 VEC (data_reference_p, heap) *drs)
1810 {
1811   int num_vertex = VEC_length (data_reference_p, drs);
1812   data_reference_p dr1, dr2;
1813   int i, j;
1814
1815   if (num_vertex == 0)
1816     return true;
1817
1818   fprintf (file, "$\n");
1819
1820   if (comment)
1821     fprintf (file, "c %s\n", comment);
1822
1823   /* First print all the vertices.  */
1824   for (i = 0; VEC_iterate (data_reference_p, drs, i, dr1); i++)
1825     fprintf (file, "n%d;\n", i);
1826
1827   for (i = 0; VEC_iterate (data_reference_p, drs, i, dr1); i++)
1828     for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
1829       if (dr_may_alias_p (dr1, dr2))
1830         fprintf (file, "n%d n%d\n", i, j);
1831
1832   return true;
1833 }
1834
1835 /* Write to FILE the alias graph of data references in ECC format.  */
1836
1837 static inline bool
1838 write_alias_graph_to_ascii_ecc (FILE *file, char *comment,
1839                                 VEC (data_reference_p, heap) *drs)
1840 {
1841   int num_vertex = VEC_length (data_reference_p, drs);
1842   data_reference_p dr1, dr2;
1843   int i, j;
1844
1845   if (num_vertex == 0)
1846     return true;
1847
1848   fprintf (file, "$\n");
1849
1850   if (comment)
1851     fprintf (file, "c %s\n", comment);
1852
1853   for (i = 0; VEC_iterate (data_reference_p, drs, i, dr1); i++)
1854     for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
1855       if (dr_may_alias_p (dr1, dr2))
1856         fprintf (file, "%d %d\n", i, j);
1857
1858   return true;
1859 }
1860
1861 /* Check if DR1 and DR2 are in the same object set.  */
1862
1863 static bool
1864 dr_same_base_object_p (const struct data_reference *dr1,
1865                        const struct data_reference *dr2)
1866 {
1867   return operand_equal_p (DR_BASE_OBJECT (dr1), DR_BASE_OBJECT (dr2), 0);
1868 }
1869
1870 /* Uses DFS component number as representative of alias-sets. Also tests for
1871    optimality by verifying if every connected component is a clique. Returns
1872    true (1) if the above test is true, and false (0) otherwise.  */
1873
1874 static int
1875 build_alias_set_optimal_p (VEC (data_reference_p, heap) *drs)
1876 {
1877   int num_vertices = VEC_length (data_reference_p, drs);
1878   struct graph *g = new_graph (num_vertices);
1879   data_reference_p dr1, dr2;
1880   int i, j;
1881   int num_connected_components;
1882   int v_indx1, v_indx2, num_vertices_in_component;
1883   int *all_vertices;
1884   int *vertices;
1885   struct graph_edge *e;
1886   int this_component_is_clique;
1887   int all_components_are_cliques = 1;
1888
1889   for (i = 0; VEC_iterate (data_reference_p, drs, i, dr1); i++)
1890     for (j = i+1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
1891       if (dr_may_alias_p (dr1, dr2))
1892         {
1893           add_edge (g, i, j);
1894           add_edge (g, j, i);
1895         }
1896
1897   all_vertices = XNEWVEC (int, num_vertices);
1898   vertices = XNEWVEC (int, num_vertices);
1899   for (i = 0; i < num_vertices; i++)
1900     all_vertices[i] = i;
1901
1902   num_connected_components = graphds_dfs (g, all_vertices, num_vertices,
1903                                           NULL, true, NULL);
1904   for (i = 0; i < g->n_vertices; i++)
1905     {
1906       data_reference_p dr = VEC_index (data_reference_p, drs, i);
1907       base_alias_pair *bap;
1908
1909       if (dr->aux)
1910         bap = (base_alias_pair *)(dr->aux);
1911
1912       bap->alias_set = XNEW (int);
1913       *(bap->alias_set) = g->vertices[i].component + 1;
1914     }
1915
1916   /* Verify if the DFS numbering results in optimal solution.  */
1917   for (i = 0; i < num_connected_components; i++)
1918     {
1919       num_vertices_in_component = 0;
1920       /* Get all vertices whose DFS component number is the same as i.  */
1921       for (j = 0; j < num_vertices; j++)
1922         if (g->vertices[j].component == i)
1923           vertices[num_vertices_in_component++] = j;
1924
1925       /* Now test if the vertices in 'vertices' form a clique, by testing
1926          for edges among each pair.  */
1927       this_component_is_clique = 1;
1928       for (v_indx1 = 0; v_indx1 < num_vertices_in_component; v_indx1++)
1929         {
1930           for (v_indx2 = v_indx1+1; v_indx2 < num_vertices_in_component; v_indx2++)
1931             {
1932               /* Check if the two vertices are connected by iterating
1933                  through all the edges which have one of these are source.  */
1934               e = g->vertices[vertices[v_indx2]].pred;
1935               while (e)
1936                 {
1937                   if (e->src == vertices[v_indx1])
1938                     break;
1939                   e = e->pred_next;
1940                 }
1941               if (!e)
1942                 {
1943                   this_component_is_clique = 0;
1944                   break;
1945                 }
1946             }
1947           if (!this_component_is_clique)
1948             all_components_are_cliques = 0;
1949         }
1950     }
1951
1952   free (all_vertices);
1953   free (vertices);
1954   free_graph (g);
1955   return all_components_are_cliques;
1956 }
1957
1958 /* Group each data reference in DRS with it's base object set num.  */
1959
1960 static void
1961 build_base_obj_set_for_drs (VEC (data_reference_p, heap) *drs)
1962 {
1963   int num_vertex = VEC_length (data_reference_p, drs);
1964   struct graph *g = new_graph (num_vertex);
1965   data_reference_p dr1, dr2;
1966   int i, j;
1967   int *queue;
1968
1969   for (i = 0; VEC_iterate (data_reference_p, drs, i, dr1); i++)
1970     for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
1971       if (dr_same_base_object_p (dr1, dr2))
1972         {
1973           add_edge (g, i, j);
1974           add_edge (g, j, i);
1975         }
1976
1977   queue = XNEWVEC (int, num_vertex);
1978   for (i = 0; i < num_vertex; i++)
1979     queue[i] = i;
1980
1981   graphds_dfs (g, queue, num_vertex, NULL, true, NULL);
1982
1983   for (i = 0; i < g->n_vertices; i++)
1984     {
1985       data_reference_p dr = VEC_index (data_reference_p, drs, i);
1986       base_alias_pair *bap;
1987
1988       if (dr->aux)
1989         bap = (base_alias_pair *)(dr->aux);
1990
1991       bap->base_obj_set = g->vertices[i].component + 1;
1992     }
1993
1994   free (queue);
1995   free_graph (g);
1996 }
1997
1998 /* Build the data references for PBB.  */
1999
2000 static void
2001 build_pbb_drs (poly_bb_p pbb)
2002 {
2003   int j;
2004   data_reference_p dr;
2005   VEC (data_reference_p, heap) *gbb_drs = GBB_DATA_REFS (PBB_BLACK_BOX (pbb));
2006
2007   for (j = 0; VEC_iterate (data_reference_p, gbb_drs, j, dr); j++)
2008     build_poly_dr (dr, pbb);
2009 }
2010
2011 /* Dump to file the alias graphs for the data references in DRS.  */
2012
2013 static void
2014 dump_alias_graphs (VEC (data_reference_p, heap) *drs)
2015 {
2016   char comment[100];
2017   FILE *file_dimacs, *file_ecc, *file_dot;
2018
2019   file_dimacs = fopen ("/tmp/dr_alias_graph_dimacs", "ab");
2020   if (file_dimacs)
2021     {
2022       snprintf (comment, sizeof (comment), "%s %s", main_input_filename,
2023                 current_function_name ());
2024       write_alias_graph_to_ascii_dimacs (file_dimacs, comment, drs);
2025       fclose (file_dimacs);
2026     }
2027
2028   file_ecc = fopen ("/tmp/dr_alias_graph_ecc", "ab");
2029   if (file_ecc)
2030     {
2031       snprintf (comment, sizeof (comment), "%s %s", main_input_filename,
2032                 current_function_name ());
2033       write_alias_graph_to_ascii_ecc (file_ecc, comment, drs);
2034       fclose (file_ecc);
2035     }
2036
2037   file_dot = fopen ("/tmp/dr_alias_graph_dot", "ab");
2038   if (file_dot)
2039     {
2040       snprintf (comment, sizeof (comment), "%s %s", main_input_filename,
2041                 current_function_name ());
2042       write_alias_graph_to_ascii_dot (file_dot, comment, drs);
2043       fclose (file_dot);
2044     }
2045 }
2046
2047 /* Build data references in SCOP.  */
2048
2049 static void
2050 build_scop_drs (scop_p scop)
2051 {
2052   int i, j;
2053   poly_bb_p pbb;
2054   data_reference_p dr;
2055   VEC (data_reference_p, heap) *drs = VEC_alloc (data_reference_p, heap, 3);
2056
2057   for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
2058     for (j = 0; VEC_iterate (data_reference_p,
2059                              GBB_DATA_REFS (PBB_BLACK_BOX (pbb)), j, dr); j++)
2060       VEC_safe_push (data_reference_p, heap, drs, dr);
2061
2062   for (i = 0; VEC_iterate (data_reference_p, drs, i, dr); i++)
2063     dr->aux = XNEW (base_alias_pair);
2064
2065   if (!build_alias_set_optimal_p (drs))
2066     {
2067       /* TODO: Add support when building alias set is not optimal.  */
2068       ;
2069     }
2070
2071   build_base_obj_set_for_drs (drs);
2072
2073   /* When debugging, enable the following code.  This cannot be used
2074      in production compilers.  */
2075   if (0)
2076     dump_alias_graphs (drs);
2077
2078   VEC_free (data_reference_p, heap, drs);
2079
2080   for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
2081     build_pbb_drs (pbb);
2082 }
2083
2084 /* Return a gsi at the position of the phi node STMT.  */
2085
2086 static gimple_stmt_iterator
2087 gsi_for_phi_node (gimple stmt)
2088 {
2089   gimple_stmt_iterator psi;
2090   basic_block bb = gimple_bb (stmt);
2091
2092   for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
2093     if (stmt == gsi_stmt (psi))
2094       return psi;
2095
2096   gcc_unreachable ();
2097   return psi;
2098 }
2099
2100 /* Insert the assignment "RES := VAR" just after the definition of VAR.  */
2101
2102 static void
2103 insert_out_of_ssa_copy (tree res, tree var)
2104 {
2105   gimple stmt;
2106   gimple_seq stmts;
2107   gimple_stmt_iterator si;
2108   gimple_stmt_iterator gsi;
2109
2110   var = force_gimple_operand (var, &stmts, true, NULL_TREE);
2111   stmt = gimple_build_assign (res, var);
2112   if (!stmts)
2113     stmts = gimple_seq_alloc ();
2114   si = gsi_last (stmts);
2115   gsi_insert_after (&si, stmt, GSI_NEW_STMT);
2116
2117   stmt = SSA_NAME_DEF_STMT (var);
2118   if (gimple_code (stmt) == GIMPLE_PHI)
2119     {
2120       gsi = gsi_after_labels (gimple_bb (stmt));
2121       gsi_insert_seq_before (&gsi, stmts, GSI_NEW_STMT);
2122     }
2123   else
2124     {
2125       gsi = gsi_for_stmt (stmt);
2126       gsi_insert_seq_after (&gsi, stmts, GSI_NEW_STMT);
2127     }
2128 }
2129
2130 /* Insert on edge E the assignment "RES := EXPR".  */
2131
2132 static void
2133 insert_out_of_ssa_copy_on_edge (edge e, tree res, tree expr)
2134 {
2135   gimple_stmt_iterator gsi;
2136   gimple_seq stmts;
2137   tree var = force_gimple_operand (expr, &stmts, true, NULL_TREE);
2138   gimple stmt = gimple_build_assign (res, var);
2139
2140   if (!stmts)
2141     stmts = gimple_seq_alloc ();
2142
2143   gsi = gsi_last (stmts);
2144   gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
2145   gsi_insert_seq_on_edge (e, stmts);
2146   gsi_commit_edge_inserts ();
2147 }
2148
2149 /* Creates a zero dimension array of the same type as VAR.  */
2150
2151 static tree
2152 create_zero_dim_array (tree var, const char *base_name)
2153 {
2154   tree index_type = build_index_type (integer_zero_node);
2155   tree elt_type = TREE_TYPE (var);
2156   tree array_type = build_array_type (elt_type, index_type);
2157   tree base = create_tmp_var (array_type, base_name);
2158
2159   add_referenced_var (base);
2160
2161   return build4 (ARRAY_REF, elt_type, base, integer_zero_node, NULL_TREE,
2162                  NULL_TREE);
2163 }
2164
2165 /* Returns true when PHI is a loop close phi node.  */
2166
2167 static bool
2168 scalar_close_phi_node_p (gimple phi)
2169 {
2170   if (gimple_code (phi) != GIMPLE_PHI
2171       || !is_gimple_reg (gimple_phi_result (phi)))
2172     return false;
2173
2174   return (gimple_phi_num_args (phi) == 1);
2175 }
2176
2177 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2178    dimension array for it.  */
2179
2180 static void
2181 rewrite_close_phi_out_of_ssa (gimple_stmt_iterator *psi)
2182 {
2183   gimple phi = gsi_stmt (*psi);
2184   tree res = gimple_phi_result (phi);
2185   tree var = SSA_NAME_VAR (res);
2186   tree zero_dim_array = create_zero_dim_array (var, "Close_Phi");
2187   gimple_stmt_iterator gsi = gsi_after_labels (gimple_bb (phi));
2188   gimple stmt = gimple_build_assign (res, zero_dim_array);
2189   tree arg = gimple_phi_arg_def (phi, 0);
2190
2191   if (TREE_CODE (arg) == SSA_NAME)
2192     insert_out_of_ssa_copy (zero_dim_array, arg);
2193   else
2194     insert_out_of_ssa_copy_on_edge (single_pred_edge (gimple_bb (phi)),
2195                                     zero_dim_array, arg);
2196
2197   remove_phi_node (psi, false);
2198   gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
2199   SSA_NAME_DEF_STMT (res) = stmt;
2200 }
2201
2202 /* Rewrite out of SSA the reduction phi node at PSI by creating a zero
2203    dimension array for it.  */
2204
2205 static void
2206 rewrite_phi_out_of_ssa (gimple_stmt_iterator *psi)
2207 {
2208   size_t i;
2209   gimple phi = gsi_stmt (*psi);
2210   basic_block bb = gimple_bb (phi);
2211   tree res = gimple_phi_result (phi);
2212   tree var = SSA_NAME_VAR (res);
2213   tree zero_dim_array = create_zero_dim_array (var, "General_Reduction");
2214   gimple_stmt_iterator gsi;
2215   gimple stmt;
2216   gimple_seq stmts;
2217
2218   for (i = 0; i < gimple_phi_num_args (phi); i++)
2219     {
2220       tree arg = gimple_phi_arg_def (phi, i);
2221
2222       /* Try to avoid the insertion on edges as much as possible: this
2223          would avoid the insertion of code on loop latch edges, making
2224          the pattern matching of the vectorizer happy, or it would
2225          avoid the insertion of useless basic blocks.  Note that it is
2226          incorrect to insert out of SSA copies close by their
2227          definition when they are more than two loop levels apart:
2228          for example, starting from a double nested loop
2229
2230          | a = ...
2231          | loop_1
2232          |  loop_2
2233          |    b = phi (a, c)
2234          |    c = ...
2235          |  end_2
2236          | end_1
2237
2238          the following transform is incorrect
2239
2240          | a = ...
2241          | Red[0] = a
2242          | loop_1
2243          |  loop_2
2244          |    b = Red[0]
2245          |    c = ...
2246          |    Red[0] = c
2247          |  end_2
2248          | end_1
2249
2250          whereas inserting the copy on the incoming edge is correct
2251
2252          | a = ...
2253          | loop_1
2254          |  Red[0] = a
2255          |  loop_2
2256          |    b = Red[0]
2257          |    c = ...
2258          |    Red[0] = c
2259          |  end_2
2260          | end_1
2261       */
2262       if (TREE_CODE (arg) == SSA_NAME
2263           && is_gimple_reg (arg)
2264           && gimple_bb (SSA_NAME_DEF_STMT (arg))
2265           && (flow_bb_inside_loop_p (bb->loop_father,
2266                                      gimple_bb (SSA_NAME_DEF_STMT (arg)))
2267               || flow_bb_inside_loop_p (loop_outer (bb->loop_father),
2268                                         gimple_bb (SSA_NAME_DEF_STMT (arg)))))
2269         insert_out_of_ssa_copy (zero_dim_array, arg);
2270       else
2271         insert_out_of_ssa_copy_on_edge (gimple_phi_arg_edge (phi, i),
2272                                         zero_dim_array, arg);
2273     }
2274
2275   var = force_gimple_operand (zero_dim_array, &stmts, true, NULL_TREE);
2276
2277   if (!stmts)
2278     stmts = gimple_seq_alloc ();
2279
2280   stmt = gimple_build_assign (res, var);
2281   remove_phi_node (psi, false);
2282   SSA_NAME_DEF_STMT (res) = stmt;
2283
2284   gsi = gsi_last (stmts);
2285   gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
2286
2287   gsi = gsi_after_labels (bb);
2288   gsi_insert_seq_before (&gsi, stmts, GSI_NEW_STMT);
2289 }
2290
2291 /* Return true when DEF can be analyzed in REGION by the scalar
2292    evolution analyzer.  */
2293
2294 static bool
2295 scev_analyzable_p (tree def, sese region)
2296 {
2297   gimple stmt = SSA_NAME_DEF_STMT (def);
2298   loop_p loop = loop_containing_stmt (stmt);
2299   tree scev = scalar_evolution_in_region (region, loop, def);
2300
2301   return !chrec_contains_undetermined (scev);
2302 }
2303
2304 /* Rewrite the scalar dependence of DEF used in USE_STMT with a memory
2305    read from ZERO_DIM_ARRAY.  */
2306
2307 static void
2308 rewrite_cross_bb_scalar_dependence (tree zero_dim_array, tree def, gimple use_stmt)
2309 {
2310   tree var = SSA_NAME_VAR (def);
2311   gimple name_stmt = gimple_build_assign (var, zero_dim_array);
2312   tree name = make_ssa_name (var, name_stmt);
2313   ssa_op_iter iter;
2314   use_operand_p use_p;
2315   gimple_stmt_iterator gsi;
2316
2317   gcc_assert (gimple_code (use_stmt) != GIMPLE_PHI);
2318
2319   gimple_assign_set_lhs (name_stmt, name);
2320
2321   gsi = gsi_for_stmt (use_stmt);
2322   gsi_insert_before (&gsi, name_stmt, GSI_NEW_STMT);
2323
2324   FOR_EACH_SSA_USE_OPERAND (use_p, use_stmt, iter, SSA_OP_ALL_USES)
2325     if (operand_equal_p (def, USE_FROM_PTR (use_p), 0))
2326       replace_exp (use_p, name);
2327
2328   update_stmt (use_stmt);
2329 }
2330
2331 /* Rewrite the scalar dependences crossing the boundary of the BB
2332    containing STMT with an array.  */
2333
2334 static void
2335 rewrite_cross_bb_scalar_deps (sese region, gimple_stmt_iterator *gsi)
2336 {
2337   gimple stmt = gsi_stmt (*gsi);
2338   imm_use_iterator imm_iter;
2339   tree def;
2340   basic_block def_bb;
2341   tree zero_dim_array = NULL_TREE;
2342   gimple use_stmt;
2343
2344   if (gimple_code (stmt) != GIMPLE_ASSIGN)
2345     return;
2346
2347   def = gimple_assign_lhs (stmt);
2348   if (!is_gimple_reg (def)
2349       || scev_analyzable_p (def, region))
2350     return;
2351
2352   def_bb = gimple_bb (stmt);
2353
2354   FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def)
2355     if (def_bb != gimple_bb (use_stmt)
2356         && gimple_code (use_stmt) != GIMPLE_PHI)
2357       {
2358         if (!zero_dim_array)
2359           {
2360             zero_dim_array = create_zero_dim_array
2361               (SSA_NAME_VAR (def), "Cross_BB_scalar_dependence");
2362             insert_out_of_ssa_copy (zero_dim_array, def);
2363             gsi_next (gsi);
2364           }
2365
2366         rewrite_cross_bb_scalar_dependence (zero_dim_array, def, use_stmt);
2367       }
2368 }
2369
2370 /* Rewrite out of SSA all the reduction phi nodes of SCOP.  */
2371
2372 static void
2373 rewrite_reductions_out_of_ssa (scop_p scop)
2374 {
2375   basic_block bb;
2376   gimple_stmt_iterator psi;
2377   sese region = SCOP_REGION (scop);
2378
2379   FOR_EACH_BB (bb)
2380     if (bb_in_sese_p (bb, region))
2381       for (psi = gsi_start_phis (bb); !gsi_end_p (psi);)
2382         {
2383           if (scalar_close_phi_node_p (gsi_stmt (psi)))
2384             rewrite_close_phi_out_of_ssa (&psi);
2385           else if (reduction_phi_p (region, &psi))
2386             rewrite_phi_out_of_ssa (&psi);
2387         }
2388
2389   update_ssa (TODO_update_ssa);
2390 #ifdef ENABLE_CHECKING
2391   verify_ssa (false);
2392   verify_loop_closed_ssa ();
2393 #endif
2394
2395   FOR_EACH_BB (bb)
2396     if (bb_in_sese_p (bb, region))
2397       for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi))
2398         rewrite_cross_bb_scalar_deps (region, &psi);
2399
2400   update_ssa (TODO_update_ssa);
2401 #ifdef ENABLE_CHECKING
2402   verify_ssa (false);
2403   verify_loop_closed_ssa ();
2404 #endif
2405 }
2406
2407 /* Returns the number of pbbs that are in loops contained in SCOP.  */
2408
2409 static int
2410 nb_pbbs_in_loops (scop_p scop)
2411 {
2412   int i;
2413   poly_bb_p pbb;
2414   int res = 0;
2415
2416   for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
2417     if (loop_in_sese_p (gbb_loop (PBB_BLACK_BOX (pbb)), SCOP_REGION (scop)))
2418       res++;
2419
2420   return res;
2421 }
2422
2423 /* Return the number of data references in BB that write in
2424    memory.  */
2425
2426 static int
2427 nb_data_writes_in_bb (basic_block bb)
2428 {
2429   int res = 0;
2430   gimple_stmt_iterator gsi;
2431
2432   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2433     if (gimple_vdef (gsi_stmt (gsi)))
2434       res++;
2435
2436   return res;
2437 }
2438
2439 /* Splits STMT out of its current BB.  */
2440
2441 static basic_block
2442 split_reduction_stmt (gimple stmt)
2443 {
2444   gimple_stmt_iterator gsi;
2445   basic_block bb = gimple_bb (stmt);
2446   edge e;
2447
2448   /* Do not split basic blocks with no writes to memory: the reduction
2449      will be the only write to memory.  */
2450   if (nb_data_writes_in_bb (bb) == 0)
2451     return bb;
2452
2453   split_block (bb, stmt);
2454
2455   if (gsi_one_before_end_p (gsi_start_bb (bb)))
2456     return bb;
2457
2458   gsi = gsi_last_bb (bb);
2459   gsi_prev (&gsi);
2460   e = split_block (bb, gsi_stmt (gsi));
2461
2462   return e->dest;
2463 }
2464
2465 /* Return true when stmt is a reduction operation.  */
2466
2467 static inline bool
2468 is_reduction_operation_p (gimple stmt)
2469 {
2470   enum tree_code code;
2471
2472   gcc_assert (is_gimple_assign (stmt));
2473   code = gimple_assign_rhs_code (stmt);
2474
2475   return flag_associative_math
2476     && commutative_tree_code (code)
2477     && associative_tree_code (code);
2478 }
2479
2480 /* Returns true when PHI contains an argument ARG.  */
2481
2482 static bool
2483 phi_contains_arg (gimple phi, tree arg)
2484 {
2485   size_t i;
2486
2487   for (i = 0; i < gimple_phi_num_args (phi); i++)
2488     if (operand_equal_p (arg, gimple_phi_arg_def (phi, i), 0))
2489       return true;
2490
2491   return false;
2492 }
2493
2494 /* Return a loop phi node that corresponds to a reduction containing LHS.  */
2495
2496 static gimple
2497 follow_ssa_with_commutative_ops (tree arg, tree lhs)
2498 {
2499   gimple stmt;
2500
2501   if (TREE_CODE (arg) != SSA_NAME)
2502     return NULL;
2503
2504   stmt = SSA_NAME_DEF_STMT (arg);
2505
2506   if (gimple_code (stmt) == GIMPLE_NOP
2507       || gimple_code (stmt) == GIMPLE_CALL)
2508     return NULL;
2509
2510   if (gimple_code (stmt) == GIMPLE_PHI)
2511     {
2512       if (phi_contains_arg (stmt, lhs))
2513         return stmt;
2514       return NULL;
2515     }
2516
2517   if (!is_gimple_assign (stmt))
2518     return NULL;
2519
2520   if (gimple_num_ops (stmt) == 2)
2521     return follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt), lhs);
2522
2523   if (is_reduction_operation_p (stmt))
2524     {
2525       gimple res = follow_ssa_with_commutative_ops (gimple_assign_rhs1 (stmt), lhs);
2526
2527       return res ? res :
2528         follow_ssa_with_commutative_ops (gimple_assign_rhs2 (stmt), lhs);
2529     }
2530
2531   return NULL;
2532 }
2533
2534 /* Detect commutative and associative scalar reductions starting at
2535    the STMT.  Return the phi node of the reduction cycle, or NULL.  */
2536
2537 static gimple
2538 detect_commutative_reduction_arg (tree lhs, gimple stmt, tree arg,
2539                                   VEC (gimple, heap) **in,
2540                                   VEC (gimple, heap) **out)
2541 {
2542   gimple phi = follow_ssa_with_commutative_ops (arg, lhs);
2543
2544   if (!phi)
2545     return NULL;
2546
2547   VEC_safe_push (gimple, heap, *in, stmt);
2548   VEC_safe_push (gimple, heap, *out, stmt);
2549   return phi;
2550 }
2551
2552 /* Detect commutative and associative scalar reductions starting at
2553    the STMT.  Return the phi node of the reduction cycle, or NULL.  */
2554
2555 static gimple
2556 detect_commutative_reduction_assign (gimple stmt, VEC (gimple, heap) **in,
2557                                      VEC (gimple, heap) **out)
2558 {
2559   tree lhs = gimple_assign_lhs (stmt);
2560
2561   if (gimple_num_ops (stmt) == 2)
2562     return detect_commutative_reduction_arg (lhs, stmt,
2563                                              gimple_assign_rhs1 (stmt),
2564                                              in, out);
2565
2566   if (is_reduction_operation_p (stmt))
2567     {
2568       gimple res = detect_commutative_reduction_arg (lhs, stmt,
2569                                                      gimple_assign_rhs1 (stmt),
2570                                                      in, out);
2571       return res ? res
2572         : detect_commutative_reduction_arg (lhs, stmt,
2573                                             gimple_assign_rhs2 (stmt),
2574                                             in, out);
2575     }
2576
2577   return NULL;
2578 }
2579
2580 /* Return a loop phi node that corresponds to a reduction containing LHS.  */
2581
2582 static gimple
2583 follow_inital_value_to_phi (tree arg, tree lhs)
2584 {
2585   gimple stmt;
2586
2587   if (!arg || TREE_CODE (arg) != SSA_NAME)
2588     return NULL;
2589
2590   stmt = SSA_NAME_DEF_STMT (arg);
2591
2592   if (gimple_code (stmt) == GIMPLE_PHI
2593       && phi_contains_arg (stmt, lhs))
2594     return stmt;
2595
2596   return NULL;
2597 }
2598
2599
2600 /* Return the argument of the loop PHI that is the inital value coming
2601    from outside the loop.  */
2602
2603 static edge
2604 edge_initial_value_for_loop_phi (gimple phi)
2605 {
2606   size_t i;
2607
2608   for (i = 0; i < gimple_phi_num_args (phi); i++)
2609     {
2610       edge e = gimple_phi_arg_edge (phi, i);
2611
2612       if (loop_depth (e->src->loop_father)
2613           < loop_depth (e->dest->loop_father))
2614         return e;
2615     }
2616
2617   return NULL;
2618 }
2619
2620 /* Return the argument of the loop PHI that is the inital value coming
2621    from outside the loop.  */
2622
2623 static tree
2624 initial_value_for_loop_phi (gimple phi)
2625 {
2626   size_t i;
2627
2628   for (i = 0; i < gimple_phi_num_args (phi); i++)
2629     {
2630       edge e = gimple_phi_arg_edge (phi, i);
2631
2632       if (loop_depth (e->src->loop_father)
2633           < loop_depth (e->dest->loop_father))
2634         return gimple_phi_arg_def (phi, i);
2635     }
2636
2637   return NULL_TREE;
2638 }
2639
2640 /* Detect commutative and associative scalar reductions starting at
2641    the loop closed phi node CLOSE_PHI.  Return the phi node of the
2642    reduction cycle, or NULL.  */
2643
2644 static gimple
2645 detect_commutative_reduction (gimple stmt, VEC (gimple, heap) **in,
2646                               VEC (gimple, heap) **out)
2647 {
2648   if (scalar_close_phi_node_p (stmt))
2649     {
2650       tree arg = gimple_phi_arg_def (stmt, 0);
2651       gimple def, loop_phi;
2652
2653       if (TREE_CODE (arg) != SSA_NAME)
2654         return NULL;
2655
2656       def = SSA_NAME_DEF_STMT (arg);
2657       loop_phi = detect_commutative_reduction (def, in, out);
2658
2659       if (loop_phi)
2660         {
2661           tree lhs = gimple_phi_result (stmt);
2662           tree init = initial_value_for_loop_phi (loop_phi);
2663           gimple phi = follow_inital_value_to_phi (init, lhs);
2664
2665           VEC_safe_push (gimple, heap, *in, loop_phi);
2666           VEC_safe_push (gimple, heap, *out, stmt);
2667           return phi;
2668         }
2669       else
2670         return NULL;
2671     }
2672
2673   if (gimple_code (stmt) == GIMPLE_ASSIGN)
2674     return detect_commutative_reduction_assign (stmt, in, out);
2675
2676   return NULL;
2677 }
2678
2679 /* Translate the scalar reduction statement STMT to an array RED
2680    knowing that its recursive phi node is LOOP_PHI.  */
2681
2682 static void
2683 translate_scalar_reduction_to_array_for_stmt (tree red, gimple stmt,
2684                                               gimple loop_phi)
2685 {
2686   gimple_stmt_iterator insert_gsi = gsi_after_labels (gimple_bb (loop_phi));
2687   tree res = gimple_phi_result (loop_phi);
2688   gimple assign = gimple_build_assign (res, red);
2689
2690   gsi_insert_before (&insert_gsi, assign, GSI_SAME_STMT);
2691
2692   insert_gsi = gsi_after_labels (gimple_bb (stmt));
2693   assign = gimple_build_assign (red, gimple_assign_lhs (stmt));
2694   insert_gsi = gsi_for_stmt (stmt);
2695   gsi_insert_after (&insert_gsi, assign, GSI_SAME_STMT);
2696 }
2697
2698 /* Insert the assignment "result (CLOSE_PHI) = RED".  */
2699
2700 static void
2701 insert_copyout (tree red, gimple close_phi)
2702 {
2703   tree res = gimple_phi_result (close_phi);
2704   basic_block bb = gimple_bb (close_phi);
2705   gimple_stmt_iterator insert_gsi = gsi_after_labels (bb);
2706   gimple assign = gimple_build_assign (res, red);
2707
2708   gsi_insert_before (&insert_gsi, assign, GSI_SAME_STMT);
2709 }
2710
2711 /* Insert the assignment "RED = initial_value (LOOP_PHI)".  */
2712
2713 static void
2714 insert_copyin (tree red, gimple loop_phi)
2715 {
2716   gimple_seq stmts;
2717   tree init = initial_value_for_loop_phi (loop_phi);
2718   tree expr = build2 (MODIFY_EXPR, TREE_TYPE (init), red, init);
2719
2720   force_gimple_operand (expr, &stmts, true, NULL);
2721   gsi_insert_seq_on_edge (edge_initial_value_for_loop_phi (loop_phi), stmts);
2722 }
2723
2724 /* Removes the PHI node and resets all the debug stmts that are using
2725    the PHI_RESULT.  */
2726
2727 static void
2728 remove_phi (gimple phi)
2729 {
2730   imm_use_iterator imm_iter;
2731   tree def;
2732   use_operand_p use_p;
2733   gimple_stmt_iterator gsi;
2734   VEC (gimple, heap) *update = VEC_alloc (gimple, heap, 3);
2735   unsigned int i;
2736   gimple stmt;
2737
2738   def = PHI_RESULT (phi);
2739   FOR_EACH_IMM_USE_FAST (use_p, imm_iter, def)
2740     {
2741       stmt = USE_STMT (use_p);
2742
2743       if (is_gimple_debug (stmt))
2744         {
2745           gimple_debug_bind_reset_value (stmt);
2746           VEC_safe_push (gimple, heap, update, stmt);
2747         }
2748     }
2749
2750   for (i = 0; VEC_iterate (gimple, update, i, stmt); i++)
2751     update_stmt (stmt);
2752
2753   VEC_free (gimple, heap, update);
2754
2755   gsi = gsi_for_phi_node (phi);
2756   remove_phi_node (&gsi, false);
2757 }
2758
2759 /* Rewrite out of SSA the reduction described by the loop phi nodes
2760    IN, and the close phi nodes OUT.  IN and OUT are structured by loop
2761    levels like this:
2762
2763    IN: stmt, loop_n, ..., loop_0
2764    OUT: stmt, close_n, ..., close_0
2765
2766    the first element is the reduction statement, and the next elements
2767    are the loop and close phi nodes of each of the outer loops.  */
2768
2769 static void
2770 translate_scalar_reduction_to_array (VEC (gimple, heap) *in,
2771                                      VEC (gimple, heap) *out,
2772                                      sbitmap reductions)
2773 {
2774   unsigned int i;
2775   gimple loop_phi;
2776   tree red;
2777
2778   for (i = 0; VEC_iterate (gimple, in, i, loop_phi); i++)
2779     {
2780       gimple close_phi = VEC_index (gimple, out, i);
2781
2782       if (i == 0)
2783         {
2784           gimple stmt = loop_phi;
2785           basic_block bb = split_reduction_stmt (stmt);
2786
2787           SET_BIT (reductions, bb->index);
2788           gcc_assert (close_phi == loop_phi);
2789
2790           red = create_zero_dim_array
2791             (gimple_assign_lhs (stmt), "Commutative_Associative_Reduction");
2792           translate_scalar_reduction_to_array_for_stmt
2793             (red, stmt, VEC_index (gimple, in, 1));
2794           continue;
2795         }
2796
2797       if (i == VEC_length (gimple, in) - 1)
2798         {
2799           insert_copyout (red, close_phi);
2800           insert_copyin (red, loop_phi);
2801         }
2802
2803       remove_phi (loop_phi);
2804       remove_phi (close_phi);
2805     }
2806 }
2807
2808 /* Rewrites out of SSA a commutative reduction at CLOSE_PHI.  */
2809
2810 static void
2811 rewrite_commutative_reductions_out_of_ssa_close_phi (gimple close_phi,
2812                                                      sbitmap reductions)
2813 {
2814   VEC (gimple, heap) *in = VEC_alloc (gimple, heap, 10);
2815   VEC (gimple, heap) *out = VEC_alloc (gimple, heap, 10);
2816
2817   detect_commutative_reduction (close_phi, &in, &out);
2818   if (VEC_length (gimple, in) > 0)
2819     translate_scalar_reduction_to_array (in, out, reductions);
2820
2821   VEC_free (gimple, heap, in);
2822   VEC_free (gimple, heap, out);
2823 }
2824
2825 /* Rewrites all the commutative reductions from LOOP out of SSA.  */
2826
2827 static void
2828 rewrite_commutative_reductions_out_of_ssa_loop (loop_p loop,
2829                                                 sbitmap reductions)
2830 {
2831   gimple_stmt_iterator gsi;
2832   edge exit = single_exit (loop);
2833
2834   if (!exit)
2835     return;
2836
2837   for (gsi = gsi_start_phis (exit->dest); !gsi_end_p (gsi); gsi_next (&gsi))
2838     rewrite_commutative_reductions_out_of_ssa_close_phi (gsi_stmt (gsi),
2839                                                          reductions);
2840 }
2841
2842 /* Rewrites all the commutative reductions from SCOP out of SSA.  */
2843
2844 static void
2845 rewrite_commutative_reductions_out_of_ssa (sese region, sbitmap reductions)
2846 {
2847   loop_iterator li;
2848   loop_p loop;
2849
2850   FOR_EACH_LOOP (li, loop, 0)
2851     if (loop_in_sese_p (loop, region))
2852       rewrite_commutative_reductions_out_of_ssa_loop (loop, reductions);
2853
2854   gsi_commit_edge_inserts ();
2855   update_ssa (TODO_update_ssa);
2856 #ifdef ENABLE_CHECKING
2857   verify_ssa (false);
2858   verify_loop_closed_ssa ();
2859 #endif
2860 }
2861
2862 /* A LOOP is in normal form for Graphite when it contains only one
2863    scalar phi node that defines the main induction variable of the
2864    loop, only one increment of the IV, and only one exit condition.  */
2865
2866 static void
2867 graphite_loop_normal_form (loop_p loop)
2868 {
2869   struct tree_niter_desc niter;
2870   tree nit;
2871   gimple_seq stmts;
2872   edge exit = single_dom_exit (loop);
2873
2874   bool known_niter = number_of_iterations_exit (loop, exit, &niter, false);
2875
2876   /* At this point we should know the number of iterations,  */
2877   gcc_assert (known_niter);
2878
2879   nit = force_gimple_operand (unshare_expr (niter.niter), &stmts, true,
2880                               NULL_TREE);
2881   if (stmts)
2882     gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
2883
2884   loop->single_iv = canonicalize_loop_ivs (loop, &nit);
2885 }
2886
2887 /* Rewrite all the loops of SCOP in normal form: one induction
2888    variable per loop.  */
2889
2890 static void
2891 scop_canonicalize_loops (scop_p scop)
2892 {
2893   loop_iterator li;
2894   loop_p loop;
2895
2896   FOR_EACH_LOOP (li, loop, 0)
2897     if (loop_in_sese_p (loop, SCOP_REGION (scop)))
2898       graphite_loop_normal_form (loop);
2899 }
2900
2901 /* Can all ivs be represented by a signed integer?
2902    As CLooG might generate negative values in its expressions, signed loop ivs
2903    are required in the backend. */
2904 static bool
2905 scop_ivs_can_be_represented (scop_p scop)
2906 {
2907   loop_iterator li;
2908   loop_p loop;
2909
2910   FOR_EACH_LOOP (li, loop, 0)
2911     {
2912       tree type;
2913       int precision;
2914
2915       if (!loop_in_sese_p (loop, SCOP_REGION (scop)))
2916         continue;
2917
2918       if (!loop->single_iv)
2919         continue;
2920
2921       type = TREE_TYPE(loop->single_iv);
2922       precision = TYPE_PRECISION (type);
2923
2924       if (TYPE_UNSIGNED (type)
2925           && precision >= TYPE_PRECISION (long_long_integer_type_node))
2926         return false;
2927     }
2928
2929   return true;
2930 }
2931
2932
2933 /* Builds the polyhedral representation for a SESE region.  */
2934
2935 void
2936 build_poly_scop (scop_p scop)
2937 {
2938   sese region = SCOP_REGION (scop);
2939   sbitmap reductions = sbitmap_alloc (last_basic_block * 2);
2940   graphite_dim_t max_dim;
2941
2942   sbitmap_zero (reductions);
2943   rewrite_commutative_reductions_out_of_ssa (region, reductions);
2944   rewrite_reductions_out_of_ssa (scop);
2945   build_scop_bbs (scop, reductions);
2946   sbitmap_free (reductions);
2947
2948   /* FIXME: This restriction is needed to avoid a problem in CLooG.
2949      Once CLooG is fixed, remove this guard.  Anyways, it makes no
2950      sense to optimize a scop containing only PBBs that do not belong
2951      to any loops.  */
2952   if (nb_pbbs_in_loops (scop) == 0)
2953     return;
2954
2955   scop_canonicalize_loops (scop);
2956   if (!scop_ivs_can_be_represented (scop))
2957     return;
2958
2959   build_sese_loop_nests (region);
2960   build_sese_conditions (region);
2961   find_scop_parameters (scop);
2962
2963   max_dim = PARAM_VALUE (PARAM_GRAPHITE_MAX_NB_SCOP_PARAMS);
2964   if (scop_nb_params (scop) > max_dim)
2965     return;
2966
2967   build_scop_iteration_domain (scop);
2968   build_scop_context (scop);
2969
2970   add_conditions_to_constraints (scop);
2971   scop_to_lst (scop);
2972   build_scop_scattering (scop);
2973   build_scop_drs (scop);
2974
2975   /* This SCoP has been translated to the polyhedral
2976      representation.  */
2977   POLY_SCOP_P (scop) = true;
2978 }
2979
2980 /* Always return false.  Exercise the scop_to_clast function.  */
2981
2982 void
2983 check_poly_representation (scop_p scop ATTRIBUTE_UNUSED)
2984 {
2985 #ifdef ENABLE_CHECKING
2986   cloog_prog_clast pc = scop_to_clast (scop);
2987   cloog_clast_free (pc.stmt);
2988   cloog_program_free (pc.prog);
2989 #endif
2990 }
2991 #endif