gcc/graphite-scop-detection.c

   1 /* Detection of Static Control Parts (SCoP) for Graphite.
   2    Copyright (C) 2009-2016 Free Software Foundation, Inc.
   3    Contributed by Sebastian Pop <sebastian.pop@amd.com> and
   4    Tobias Grosser <grosser@fim.uni-passau.de>.
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify
   9 it under the terms of the GNU General Public License as published by
  10 the Free Software Foundation; either version 3, or (at your option)
  11 any later version.
  12
  13 GCC is distributed in the hope that it will be useful,
  14 but WITHOUT ANY WARRANTY; without even the implied warranty of
  15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16 GNU General Public License for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING3.  If not see
  20 <http://www.gnu.org/licenses/>.  */
  21
  22 #define USES_ISL
  23
  24 #include "config.h"
  25
  26 #ifdef HAVE_isl
  27
  28 #include "system.h"
  29 #include "coretypes.h"
  30 #include "backend.h"
  31 #include "cfghooks.h"
  32 #include "domwalk.h"
  33 #include "params.h"
  34 #include "tree.h"
  35 #include "gimple.h"
  36 #include "ssa.h"
  37 #include "fold-const.h"
  38 #include "gimple-iterator.h"
  39 #include "tree-cfg.h"
  40 #include "tree-ssa-loop-manip.h"
  41 #include "tree-ssa-loop-niter.h"
  42 #include "tree-ssa-loop.h"
  43 #include "tree-into-ssa.h"
  44 #include "tree-ssa.h"
  45 #include "cfgloop.h"
  46 #include "tree-data-ref.h"
  47 #include "tree-scalar-evolution.h"
  48 #include "tree-pass.h"
  49 #include "tree-ssa-propagate.h"
  50 #include "gimple-pretty-print.h"
  51 #include "graphite.h"
  52
  53 class debug_printer
  54 {
  55 private:
  56   FILE *dump_file;
  57
  58 public:
  59   void
  60   set_dump_file (FILE *f)
  61   {
  62     gcc_assert (f);
  63     dump_file = f;
  64   }
  65
  66   friend debug_printer &
  67   operator<< (debug_printer &output, int i)
  68   {
  69     fprintf (output.dump_file, "%d", i);
  70     return output;
  71   }
  72   friend debug_printer &
  73   operator<< (debug_printer &output, const char *s)
  74   {
  75     fprintf (output.dump_file, "%s", s);
  76     return output;
  77   }
  78 } dp;
  79
  80 #define DEBUG_PRINT(args) do \
  81     {                                                           \
  82       if (dump_file && (dump_flags & TDF_DETAILS)) { args; }    \
  83     } while (0);
  84
  85 /* Pretty print to FILE all the SCoPs in DOT format and mark them with
  86    different colors.  If there are not enough colors, paint the
  87    remaining SCoPs in gray.
  88
  89    Special nodes:
  90    - "*" after the node number denotes the entry of a SCoP,
  91    - "#" after the node number denotes the exit of a SCoP,
  92    - "()" around the node number denotes the entry or the
  93      exit nodes of the SCOP.  These are not part of SCoP.  */
  94
  95 DEBUG_FUNCTION void
  96 dot_all_sese (FILE *file, vec<sese_l>& scops)
  97 {
  98   /* Disable debugging while printing graph.  */
  99   int tmp_dump_flags = dump_flags;
 100   dump_flags = 0;
 101
 102   fprintf (file, "digraph all {\n");
 103
 104   basic_block bb;
 105   FOR_ALL_BB_FN (bb, cfun)
 106     {
 107       int part_of_scop = false;
 108
 109       /* Use HTML for every bb label.  So we are able to print bbs
 110          which are part of two different SCoPs, with two different
 111          background colors.  */
 112       fprintf (file, "%d [label=<\n  <TABLE BORDER=\"0\" CELLBORDER=\"1\" ",
 113                bb->index);
 114       fprintf (file, "CELLSPACING=\"0\">\n");
 115
 116       /* Select color for SCoP.  */
 117       sese_l *region;
 118       int i;
 119       FOR_EACH_VEC_ELT (scops, i, region)
 120         {
 121           bool sese_in_region = bb_in_sese_p (bb, *region);
 122           if (sese_in_region || (region->exit->dest == bb)
 123               || (region->entry->dest == bb))
 124             {
 125               const char *color;
 126               switch (i % 17)
 127                 {
 128                 case 0: /* red */
 129                   color = "#e41a1c";
 130                   break;
 131                 case 1: /* blue */
 132                   color = "#377eb8";
 133                   break;
 134                 case 2: /* green */
 135                   color = "#4daf4a";
 136                   break;
 137                 case 3: /* purple */
 138                   color = "#984ea3";
 139                   break;
 140                 case 4: /* orange */
 141                   color = "#ff7f00";
 142                   break;
 143                 case 5: /* yellow */
 144                   color = "#ffff33";
 145                   break;
 146                 case 6: /* brown */
 147                   color = "#a65628";
 148                   break;
 149                 case 7: /* rose */
 150                   color = "#f781bf";
 151                   break;
 152                 case 8:
 153                   color = "#8dd3c7";
 154                   break;
 155                 case 9:
 156                   color = "#ffffb3";
 157                   break;
 158                 case 10:
 159                   color = "#bebada";
 160                   break;
 161                 case 11:
 162                   color = "#fb8072";
 163                   break;
 164                 case 12:
 165                   color = "#80b1d3";
 166                   break;
 167                 case 13:
 168                   color = "#fdb462";
 169                   break;
 170                 case 14:
 171                   color = "#b3de69";
 172                   break;
 173                 case 15:
 174                   color = "#fccde5";
 175                   break;
 176                 case 16:
 177                   color = "#bc80bd";
 178                   break;
 179                 default: /* gray */
 180                   color = "#999999";
 181                 }
 182
 183               fprintf (file, "    <TR><TD WIDTH=\"50\" BGCOLOR=\"%s\">",
 184                        color);
 185
 186               if (!sese_in_region)
 187                 fprintf (file, " (");
 188
 189               if (bb == region->entry->dest && bb == region->exit->dest)
 190                 fprintf (file, " %d*# ", bb->index);
 191               else if (bb == region->entry->dest)
 192                 fprintf (file, " %d* ", bb->index);
 193               else if (bb == region->exit->dest)
 194                 fprintf (file, " %d# ", bb->index);
 195               else
 196                 fprintf (file, " %d ", bb->index);
 197
 198               fprintf (file, "{lp_%d}", bb->loop_father->num);
 199
 200               if (!sese_in_region)
 201                 fprintf (file, ")");
 202
 203               fprintf (file, "</TD></TR>\n");
 204               part_of_scop = true;
 205             }
 206         }
 207
 208         if (!part_of_scop)
 209           {
 210             fprintf (file, "    <TR><TD WIDTH=\"50\" BGCOLOR=\"#ffffff\">");
 211             fprintf (file, " %d {lp_%d} </TD></TR>\n", bb->index,
 212                      bb->loop_father->num);
 213           }
 214         fprintf (file, "  </TABLE>>, shape=box, style=\"setlinewidth(0)\"]\n");
 215     }
 216
 217     FOR_ALL_BB_FN (bb, cfun)
 218       {
 219         edge e;
 220         edge_iterator ei;
 221         FOR_EACH_EDGE (e, ei, bb->succs)
 222           fprintf (file, "%d -> %d;\n", bb->index, e->dest->index);
 223       }
 224
 225   fputs ("}\n\n", file);
 226
 227   /* Enable debugging again.  */
 228   dump_flags = tmp_dump_flags;
 229 }
 230
 231 /* Display SCoP on stderr.  */
 232
 233 DEBUG_FUNCTION void
 234 dot_sese (sese_l& scop)
 235 {
 236   vec<sese_l> scops;
 237   scops.create (1);
 238
 239   if (scop)
 240     scops.safe_push (scop);
 241
 242   dot_all_sese (stderr, scops);
 243
 244   scops.release ();
 245 }
 246
 247 DEBUG_FUNCTION void
 248 dot_cfg ()
 249 {
 250   vec<sese_l> scops;
 251   scops.create (1);
 252   dot_all_sese (stderr, scops);
 253   scops.release ();
 254 }
 255
 256 /* Return true if BB is empty, contains only DEBUG_INSNs.  */
 257
 258 static bool
 259 trivially_empty_bb_p (basic_block bb)
 260 {
 261   gimple_stmt_iterator gsi;
 262
 263   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 264     if (gimple_code (gsi_stmt (gsi)) != GIMPLE_DEBUG)
 265       return false;
 266
 267   return true;
 268 }
 269
 270 /* Returns true when P1 and P2 are close phis with the same
 271    argument.  */
 272
 273 static inline bool
 274 same_close_phi_node (gphi *p1, gphi *p2)
 275 {
 276   return operand_equal_p (gimple_phi_arg_def (p1, 0),
 277                           gimple_phi_arg_def (p2, 0), 0);
 278 }
 279
 280 static void make_close_phi_nodes_unique (basic_block bb);
 281
 282 /* Remove the close phi node at GSI and replace its rhs with the rhs
 283    of PHI.  */
 284
 285 static void
 286 remove_duplicate_close_phi (gphi *phi, gphi_iterator *gsi)
 287 {
 288   gimple *use_stmt;
 289   use_operand_p use_p;
 290   imm_use_iterator imm_iter;
 291   tree res = gimple_phi_result (phi);
 292   tree def = gimple_phi_result (gsi->phi ());
 293
 294   gcc_assert (same_close_phi_node (phi, gsi->phi ()));
 295
 296   FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def)
 297     {
 298       FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter)
 299         SET_USE (use_p, res);
 300
 301       update_stmt (use_stmt);
 302
 303       /* It is possible that we just created a duplicate close-phi
 304          for an already-processed containing loop.  Check for this
 305          case and clean it up.  */
 306       if (gimple_code (use_stmt) == GIMPLE_PHI
 307           && gimple_phi_num_args (use_stmt) == 1)
 308         make_close_phi_nodes_unique (gimple_bb (use_stmt));
 309     }
 310
 311   remove_phi_node (gsi, true);
 312 }
 313
 314 /* Removes all the close phi duplicates from BB.  */
 315
 316 static void
 317 make_close_phi_nodes_unique (basic_block bb)
 318 {
 319   gphi_iterator psi;
 320
 321   for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
 322     {
 323       gphi_iterator gsi = psi;
 324       gphi *phi = psi.phi ();
 325
 326       /* At this point, PHI should be a close phi in normal form.  */
 327       gcc_assert (gimple_phi_num_args (phi) == 1);
 328
 329       /* Iterate over the next phis and remove duplicates.  */
 330       gsi_next (&gsi);
 331       while (!gsi_end_p (gsi))
 332         if (same_close_phi_node (phi, gsi.phi ()))
 333           remove_duplicate_close_phi (phi, &gsi);
 334         else
 335           gsi_next (&gsi);
 336     }
 337 }
 338
 339 /* Transforms LOOP to the canonical loop closed SSA form.  */
 340
 341 static void
 342 canonicalize_loop_closed_ssa (loop_p loop)
 343 {
 344   edge e = single_exit (loop);
 345   basic_block bb;
 346
 347   if (!e || e->flags & EDGE_ABNORMAL)
 348     return;
 349
 350   bb = e->dest;
 351
 352   if (single_pred_p (bb))
 353     {
 354       e = split_block_after_labels (bb);
 355       DEBUG_PRINT (dp << "Splitting bb_" << bb->index << ".\n");
 356       make_close_phi_nodes_unique (e->src);
 357     }
 358   else
 359     {
 360       gphi_iterator psi;
 361       basic_block close = split_edge (e);
 362
 363       e = single_succ_edge (close);
 364       DEBUG_PRINT (dp << "Splitting edge (" << e->src->index << ","
 365                       << e->dest->index << ")\n");
 366
 367       for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
 368         {
 369           gphi *phi = psi.phi ();
 370           unsigned i;
 371
 372           for (i = 0; i < gimple_phi_num_args (phi); i++)
 373             if (gimple_phi_arg_edge (phi, i) == e)
 374               {
 375                 tree res, arg = gimple_phi_arg_def (phi, i);
 376                 use_operand_p use_p;
 377                 gphi *close_phi;
 378
 379                 if (TREE_CODE (arg) != SSA_NAME)
 380                   continue;
 381
 382                 close_phi = create_phi_node (NULL_TREE, close);
 383                 res = create_new_def_for (arg, close_phi,
 384                                           gimple_phi_result_ptr (close_phi));
 385                 add_phi_arg (close_phi, arg,
 386                              gimple_phi_arg_edge (close_phi, 0),
 387                              UNKNOWN_LOCATION);
 388                 use_p = gimple_phi_arg_imm_use_ptr (phi, i);
 389                 replace_exp (use_p, res);
 390                 update_stmt (phi);
 391               }
 392         }
 393
 394       make_close_phi_nodes_unique (close);
 395     }
 396
 397   /* The code above does not properly handle changes in the post dominance
 398      information (yet).  */
 399   recompute_all_dominators ();
 400 }
 401
 402 /* Converts the current loop closed SSA form to a canonical form
 403    expected by the Graphite code generation.
 404
 405    The loop closed SSA form has the following invariant: a variable
 406    defined in a loop that is used outside the loop appears only in the
 407    phi nodes in the destination of the loop exit.  These phi nodes are
 408    called close phi nodes.
 409
 410    The canonical loop closed SSA form contains the extra invariants:
 411
 412    - when the loop contains only one exit, the close phi nodes contain
 413    only one argument.  That implies that the basic block that contains
 414    the close phi nodes has only one predecessor, that is a basic block
 415    in the loop.
 416
 417    - the basic block containing the close phi nodes does not contain
 418    other statements.
 419
 420    - there exist only one phi node per definition in the loop.
 421 */
 422
 423 static void
 424 canonicalize_loop_closed_ssa_form (void)
 425 {
 426   checking_verify_loop_closed_ssa (true);
 427
 428   loop_p loop;
 429   FOR_EACH_LOOP (loop, 0)
 430     canonicalize_loop_closed_ssa (loop);
 431
 432   rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
 433   update_ssa (TODO_update_ssa);
 434
 435   checking_verify_loop_closed_ssa (true);
 436 }
 437
 438 /* Can all ivs be represented by a signed integer?
 439    As isl might generate negative values in its expressions, signed loop ivs
 440    are required in the backend.  */
 441
 442 static bool
 443 loop_ivs_can_be_represented (loop_p loop)
 444 {
 445   unsigned type_long_long = TYPE_PRECISION (long_long_integer_type_node);
 446   for (gphi_iterator psi = gsi_start_phis (loop->header); !gsi_end_p (psi);
 447        gsi_next (&psi))
 448     {
 449       gphi *phi = psi.phi ();
 450       tree res = PHI_RESULT (phi);
 451       tree type = TREE_TYPE (res);
 452
 453       if (TYPE_UNSIGNED (type) && TYPE_PRECISION (type) >= type_long_long)
 454         return false;
 455     }
 456
 457   return true;
 458 }
 459
 460 /* Returns a COND_EXPR statement when BB has a single predecessor, the
 461    edge between BB and its predecessor is not a loop exit edge, and
 462    the last statement of the single predecessor is a COND_EXPR.  */
 463
 464 static gcond *
 465 single_pred_cond_non_loop_exit (basic_block bb)
 466 {
 467   if (single_pred_p (bb))
 468     {
 469       edge e = single_pred_edge (bb);
 470       basic_block pred = e->src;
 471       gimple *stmt;
 472
 473       if (loop_depth (pred->loop_father) > loop_depth (bb->loop_father))
 474         return NULL;
 475
 476       stmt = last_stmt (pred);
 477
 478       if (stmt && gimple_code (stmt) == GIMPLE_COND)
 479         return as_a<gcond *> (stmt);
 480     }
 481
 482   return NULL;
 483 }
 484
 485 namespace
 486 {
 487
 488 /* Build the maximal scop containing LOOPs and add it to SCOPS.  */
 489
 490 class scop_detection
 491 {
 492 public:
 493   scop_detection () : scops (vNULL) {}
 494
 495   ~scop_detection ()
 496   {
 497     scops.release ();
 498   }
 499
 500   /* A marker for invalid sese_l.  */
 501   static sese_l invalid_sese;
 502
 503   /* Return the SCOPS in this SCOP_DETECTION.  */
 504
 505   vec<sese_l>
 506   get_scops ()
 507   {
 508     return scops;
 509   }
 510
 511   /* Return an sese_l around the LOOP.  */
 512
 513   sese_l get_sese (loop_p loop);
 514
 515   /* Return the closest dominator with a single entry edge.  In case of a
 516      back-loop the back-edge is not counted.  */
 517
 518   static edge get_nearest_dom_with_single_entry (basic_block dom);
 519
 520   /* Return the closest post-dominator with a single exit edge.  In case of a
 521      back-loop the back-edge is not counted.  */
 522
 523   static edge get_nearest_pdom_with_single_exit (basic_block dom);
 524
 525
 526   /* Pretty printers.  */
 527
 528   static void print_edge (FILE *file, const_edge e)
 529   {
 530     fprintf (file, "edge (bb_%d, bb_%d)", e->src->index, e->dest->index);
 531   }
 532
 533   static void print_sese (FILE *file, sese_l s)
 534   {
 535     fprintf (file, "(entry_"); print_edge (file, s.entry);
 536     fprintf (file, ", exit_"); print_edge (file, s.exit);
 537     fprintf (file, ")\n");
 538   }
 539
 540   /* Merge scops at same loop depth and returns the new sese.
 541      Returns a new SESE when merge was successful, INVALID_SESE otherwise.  */
 542
 543   sese_l merge_sese (sese_l first, sese_l second) const;
 544
 545   /* Build scop outer->inner if possible.  */
 546
 547   sese_l build_scop_depth (sese_l s, loop_p loop);
 548
 549   /* If loop and loop->next are valid scops, try to merge them.  */
 550
 551   sese_l build_scop_breadth (sese_l s1, loop_p loop);
 552
 553   /* Return true when LOOP is a valid scop, that is a Static Control Part, a
 554      region of code that can be represented in the polyhedral model.  SCOP
 555      defines the region we analyse.  */
 556
 557   bool loop_is_valid_scop (loop_p loop, sese_l scop) const;
 558
 559   /* Return true when BEGIN is the preheader edge of a loop with a single exit
 560      END.  */
 561
 562   static bool region_has_one_loop (sese_l s);
 563
 564   /* Add to SCOPS a scop starting at SCOP_BEGIN and ending at SCOP_END.  */
 565
 566   void add_scop (sese_l s);
 567
 568   /* Returns true if S1 subsumes/surrounds S2.  */
 569   static bool subsumes (sese_l s1, sese_l s2);
 570
 571   /* Remove a SCoP which is subsumed by S1.  */
 572   void remove_subscops (sese_l s1);
 573
 574   /* Returns true if S1 intersects with S2.  Since we already know that S1 does
 575      not subsume S2 or vice-versa, we only check for entry bbs.  */
 576
 577   static bool intersects (sese_l s1, sese_l s2);
 578
 579   /* Remove one of the scops when it intersects with any other.  */
 580
 581   void remove_intersecting_scops (sese_l s1);
 582
 583   /* Return true when the body of LOOP has statements that can be represented
 584      as a valid scop.  */
 585
 586   bool loop_body_is_valid_scop (loop_p loop, sese_l scop) const;
 587
 588   /* Return true when BB contains a harmful operation for a scop: that
 589      can be a function call with side effects, the induction variables
 590      are not linear with respect to SCOP, etc.  The current open
 591      scop should end before this statement.  */
 592
 593   bool harmful_stmt_in_bb (sese_l scop, basic_block bb) const;
 594
 595   /* Return true when a statement in SCOP cannot be represented by Graphite.
 596      The assumptions are that L1 dominates L2, and SCOP->entry dominates L1.
 597      Limit the number of bbs between adjacent loops to
 598      PARAM_SCOP_MAX_NUM_BBS_BETWEEN_LOOPS.  */
 599
 600   bool harmful_stmt_in_region (sese_l scop) const;
 601
 602   /* Return true only when STMT is simple enough for being handled by Graphite.
 603      This depends on SCOP, as the parameters are initialized relatively to
 604      this basic block, the linear functions are initialized based on the
 605      outermost loop containing STMT inside the SCOP.  BB is the place where we
 606      try to evaluate the STMT.  */
 607
 608   bool stmt_simple_for_scop_p (sese_l scop, gimple *stmt,
 609                                basic_block bb) const;
 610
 611   /* Something like "n * m" is not allowed.  */
 612
 613   static bool graphite_can_represent_init (tree e);
 614
 615   /* Return true when SCEV can be represented in the polyhedral model.
 616
 617      An expression can be represented, if it can be expressed as an
 618      affine expression.  For loops (i, j) and parameters (m, n) all
 619      affine expressions are of the form:
 620
 621      x1 * i + x2 * j + x3 * m + x4 * n + x5 * 1 where x1..x5 element of Z
 622
 623      1 i + 20 j + (-2) m + 25
 624
 625      Something like "i * n" or "n * m" is not allowed.  */
 626
 627   static bool graphite_can_represent_scev (tree scev);
 628
 629   /* Return true when EXPR can be represented in the polyhedral model.
 630
 631      This means an expression can be represented, if it is linear with respect
 632      to the loops and the strides are non parametric.  LOOP is the place where
 633      the expr will be evaluated.  SCOP defines the region we analyse.  */
 634
 635   static bool graphite_can_represent_expr (sese_l scop, loop_p loop,
 636                                            tree expr);
 637
 638   /* Return true if the data references of STMT can be represented by Graphite.
 639      We try to analyze the data references in a loop contained in the SCOP.  */
 640
 641   static bool stmt_has_simple_data_refs_p (sese_l scop, gimple *stmt);
 642
 643   /* Remove the close phi node at GSI and replace its rhs with the rhs
 644      of PHI.  */
 645
 646   static void remove_duplicate_close_phi (gphi *phi, gphi_iterator *gsi);
 647
 648   /* Returns true when Graphite can represent LOOP in SCOP.
 649      FIXME: For the moment, graphite cannot be used on loops that iterate using
 650      induction variables that wrap.  */
 651
 652   static bool can_represent_loop_1 (loop_p loop, sese_l scop);
 653
 654   /* Return true when all the loops within LOOP can be represented by
 655      Graphite.  */
 656
 657   static bool can_represent_loop (loop_p loop, sese_l scop);
 658
 659   /* Returns the number of pbbs that are in loops contained in SCOP.  */
 660
 661   static int nb_pbbs_in_loops (scop_p scop);
 662
 663   static bool graphite_can_represent_stmt (sese_l, gimple *, basic_block);
 664
 665 private:
 666   vec<sese_l> scops;
 667 };
 668
 669 sese_l scop_detection::invalid_sese (NULL, NULL);
 670
 671 /* Return an sese_l around the LOOP.  */
 672
 673 sese_l
 674 scop_detection::get_sese (loop_p loop)
 675 {
 676   if (!loop)
 677     return invalid_sese;
 678
 679   if (!loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS))
 680     return invalid_sese;
 681   edge scop_end = single_exit (loop);
 682   if (!scop_end)
 683     return invalid_sese;
 684   edge scop_begin = loop_preheader_edge (loop);
 685   sese_l s (scop_begin, scop_end);
 686   return s;
 687 }
 688
 689 /* Return the closest dominator with a single entry edge.  */
 690
 691 edge
 692 scop_detection::get_nearest_dom_with_single_entry (basic_block dom)
 693 {
 694   if (!dom->preds)
 695     return NULL;
 696
 697   /* If any of the dominators has two predecessors but one of them is a back
 698      edge, then that basic block also qualifies as a dominator with single
 699      entry.  */
 700   if (dom->preds->length () == 2)
 701     {
 702       /* If e1->src dominates e2->src then e1->src will also dominate dom.  */
 703       edge e1 = (*dom->preds)[0];
 704       edge e2 = (*dom->preds)[1];
 705       loop_p l = dom->loop_father;
 706       loop_p l1 = e1->src->loop_father;
 707       loop_p l2 = e2->src->loop_father;
 708       if (l != l1 && l == l2
 709           && dominated_by_p (CDI_DOMINATORS, e2->src, e1->src))
 710         return e1;
 711       if (l != l2 && l == l1
 712           && dominated_by_p (CDI_DOMINATORS, e1->src, e2->src))
 713         return e2;
 714     }
 715
 716   while (dom->preds->length () != 1)
 717     {
 718       if (dom->preds->length () < 1)
 719         return NULL;
 720       dom = get_immediate_dominator (CDI_DOMINATORS, dom);
 721       if (!dom->preds)
 722         return NULL;
 723     }
 724   return (*dom->preds)[0];
 725 }
 726
 727 /* Return the closest post-dominator with a single exit edge.  In case of a
 728    back-loop the back-edge is not counted.  */
 729
 730 edge
 731 scop_detection::get_nearest_pdom_with_single_exit (basic_block pdom)
 732 {
 733   if (!pdom->succs)
 734     return NULL;
 735
 736   /* If any of the post-dominators has two successors but one of them is a back
 737      edge, then that basic block also qualifies as a post-dominator with single
 738      exit. */
 739   if (pdom->succs->length () == 2)
 740     {
 741       /* If e1->dest post-dominates e2->dest then e1->dest will also
 742          post-dominate pdom.  */
 743       edge e1 = (*pdom->succs)[0];
 744       edge e2 = (*pdom->succs)[1];
 745       loop_p l = pdom->loop_father;
 746       loop_p l1 = e1->dest->loop_father;
 747       loop_p l2 = e2->dest->loop_father;
 748       if (l != l1 && l == l2
 749           && dominated_by_p (CDI_POST_DOMINATORS, e2->dest, e1->dest))
 750         return e1;
 751       if (l != l2 && l == l1
 752           && dominated_by_p (CDI_POST_DOMINATORS, e1->dest, e2->dest))
 753         return e2;
 754     }
 755
 756   while (pdom->succs->length () != 1)
 757     {
 758       if (pdom->succs->length () < 1)
 759         return NULL;
 760       pdom = get_immediate_dominator (CDI_POST_DOMINATORS, pdom);
 761       if (!pdom->succs)
 762         return NULL;
 763     }
 764
 765   return (*pdom->succs)[0];
 766 }
 767
 768 /* Merge scops at same loop depth and returns the new sese.
 769    Returns a new SESE when merge was successful, INVALID_SESE otherwise.  */
 770
 771 sese_l
 772 scop_detection::merge_sese (sese_l first, sese_l second) const
 773 {
 774   /* In the trivial case first/second may be NULL.  */
 775   if (!first)
 776     return second;
 777   if (!second)
 778     return first;
 779
 780   DEBUG_PRINT (dp << "[try-merging-sese] s1: "; print_sese (dump_file, first);
 781                dp << "[try-merging-sese] s2: ";
 782                print_sese (dump_file, second));
 783
 784   /* Assumption: Both the sese's should be at the same loop depth or one scop
 785      should subsume the other like in case of nested loops.  */
 786
 787   /* Find the common dominators for entry,
 788      and common post-dominators for the exit.  */
 789   basic_block dom = nearest_common_dominator (CDI_DOMINATORS,
 790                                               get_entry_bb (first),
 791                                               get_entry_bb (second));
 792
 793   edge entry = get_nearest_dom_with_single_entry (dom);
 794
 795   if (!entry || (entry->flags & EDGE_IRREDUCIBLE_LOOP))
 796     return invalid_sese;
 797
 798   basic_block pdom = nearest_common_dominator (CDI_POST_DOMINATORS,
 799                                                get_exit_bb (first),
 800                                                get_exit_bb (second));
 801   pdom = nearest_common_dominator (CDI_POST_DOMINATORS, dom, pdom);
 802
 803   edge exit = get_nearest_pdom_with_single_exit (pdom);
 804
 805   if (!exit || (exit->flags & EDGE_IRREDUCIBLE_LOOP))
 806     return invalid_sese;
 807
 808   sese_l combined (entry, exit);
 809
 810   DEBUG_PRINT (dp << "checking combined sese: ";
 811                print_sese (dump_file, combined));
 812
 813   /* FIXME: We could iterate to find the dom which dominates pdom, and pdom
 814      which post-dominates dom, until it stabilizes.  Also, ENTRY->SRC and
 815      EXIT->DEST should be in the same loop nest.  */
 816   if (!dominated_by_p (CDI_DOMINATORS, pdom, dom)
 817       || loop_depth (entry->src->loop_father)
 818          != loop_depth (exit->dest->loop_father))
 819     return invalid_sese;
 820
 821   /* For now we just want to bail out when exit does not post-dominate entry.
 822      TODO: We might just add a basic_block at the exit to make exit
 823      post-dominate entry (the entire region).  */
 824   if (!dominated_by_p (CDI_POST_DOMINATORS, get_entry_bb (combined),
 825                        get_exit_bb (combined))
 826       || !dominated_by_p (CDI_DOMINATORS, get_exit_bb (combined),
 827                           get_entry_bb (combined)))
 828     {
 829       DEBUG_PRINT (dp << "[scop-detection-fail] cannot merge seses.\n");
 830       return invalid_sese;
 831     }
 832
 833   /* FIXME: We should remove this piece of code once
 834      canonicalize_loop_closed_ssa has been removed, because that function
 835      adds a BB with single exit.  */
 836   if (!trivially_empty_bb_p (get_exit_bb (combined)))
 837     {
 838       /* Find the first empty succ (with single exit) of combined.exit.  */
 839       basic_block imm_succ = combined.exit->dest;
 840       if (single_succ_p (imm_succ) && trivially_empty_bb_p (imm_succ))
 841         combined.exit = single_succ_edge (imm_succ);
 842       else
 843         {
 844           DEBUG_PRINT (dp << "[scop-detection-fail] Discarding SCoP because "
 845                           << "no single exit (empty succ) for sese exit";
 846                        print_sese (dump_file, combined));
 847           return invalid_sese;
 848         }
 849     }
 850
 851   /* Analyze all the BBs in new sese.  */
 852   if (harmful_stmt_in_region (combined))
 853     return invalid_sese;
 854
 855   DEBUG_PRINT (dp << "[merged-sese] s1: "; print_sese (dump_file, combined));
 856
 857   return combined;
 858 }
 859
 860 /* Build scop outer->inner if possible.  */
 861
 862 sese_l
 863 scop_detection::build_scop_depth (sese_l s, loop_p loop)
 864 {
 865   if (!loop)
 866     return s;
 867
 868   DEBUG_PRINT (dp << "[Depth loop_" << loop->num << "]\n");
 869   s = build_scop_depth (s, loop->inner);
 870
 871   sese_l s2 = merge_sese (s, get_sese (loop));
 872   if (!s2)
 873     {
 874       /* s might be a valid scop, so return it and start analyzing from the
 875          adjacent loop.  */
 876       build_scop_depth (invalid_sese, loop->next);
 877       return s;
 878     }
 879
 880   if (!loop_is_valid_scop (loop, s2))
 881     return build_scop_depth (invalid_sese, loop->next);
 882
 883   return build_scop_breadth (s2, loop);
 884 }
 885
 886 /* If loop and loop->next are valid scops, try to merge them.  */
 887
 888 sese_l
 889 scop_detection::build_scop_breadth (sese_l s1, loop_p loop)
 890 {
 891   if (!loop)
 892     return s1;
 893   DEBUG_PRINT (dp << "[Breadth loop_" << loop->num << "]\n");
 894   gcc_assert (s1);
 895
 896   loop_p l = loop;
 897   sese_l s2 = build_scop_depth (invalid_sese, l->next);
 898   if (!s2)
 899     {
 900       if (s1)
 901         add_scop (s1);
 902       return s1;
 903     }
 904
 905   sese_l combined = merge_sese (s1, s2);
 906
 907   if (combined)
 908     s1 = combined;
 909   else
 910     add_scop (s2);
 911
 912   if (s1)
 913     add_scop (s1);
 914   return s1;
 915 }
 916
 917 /* Returns true when Graphite can represent LOOP in SCOP.
 918    FIXME: For the moment, graphite cannot be used on loops that iterate using
 919    induction variables that wrap.  */
 920
 921 bool
 922 scop_detection::can_represent_loop_1 (loop_p loop, sese_l scop)
 923 {
 924   tree niter;
 925   struct tree_niter_desc niter_desc;
 926
 927   return single_exit (loop)
 928     && !(loop_preheader_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP)
 929     && number_of_iterations_exit (loop, single_exit (loop), &niter_desc, false)
 930     && niter_desc.control.no_overflow
 931     && (niter = number_of_latch_executions (loop))
 932     && !chrec_contains_undetermined (niter)
 933     && graphite_can_represent_expr (scop, loop, niter);
 934 }
 935
 936 /* Return true when all the loops within LOOP can be represented by
 937    Graphite.  */
 938
 939 bool
 940 scop_detection::can_represent_loop (loop_p loop, sese_l scop)
 941 {
 942   if (!can_represent_loop_1 (loop, scop))
 943     return false;
 944   if (loop->inner && !can_represent_loop (loop->inner, scop))
 945     return false;
 946   if (loop->next && !can_represent_loop (loop->next, scop))
 947     return false;
 948
 949   return true;
 950 }
 951
 952 /* Return true when LOOP is a valid scop, that is a Static Control Part, a
 953    region of code that can be represented in the polyhedral model.  SCOP
 954    defines the region we analyse.  */
 955
 956 bool
 957 scop_detection::loop_is_valid_scop (loop_p loop, sese_l scop) const
 958 {
 959   if (!scop)
 960     return false;
 961
 962   if (!optimize_loop_nest_for_speed_p (loop))
 963     {
 964       DEBUG_PRINT (dp << "[scop-detection-fail] loop_"
 965                       << loop->num << " is not on a hot path.\n");
 966       return false;
 967     }
 968
 969   if (!can_represent_loop (loop, scop))
 970     {
 971       DEBUG_PRINT (dp << "[scop-detection-fail] cannot represent loop_"
 972                       << loop->num << "\n");
 973       return false;
 974     }
 975
 976   if (loop_body_is_valid_scop (loop, scop))
 977     {
 978       DEBUG_PRINT (dp << "[valid-scop] loop_" << loop->num
 979                       << " is a valid scop.\n");
 980       return true;
 981     }
 982   return false;
 983 }
 984
 985 /* Return true when BEGIN is the preheader edge of a loop with a single exit
 986    END.  */
 987
 988 bool
 989 scop_detection::region_has_one_loop (sese_l s)
 990 {
 991   edge begin = s.entry;
 992   edge end = s.exit;
 993   /* Check for a single perfectly nested loop.  */
 994   if (begin->dest->loop_father->inner)
 995     return false;
 996
 997   /* Otherwise, check whether we have adjacent loops.  */
 998   return begin->dest->loop_father == end->src->loop_father;
 999 }
1000
1001 /* Add to SCOPS a scop starting at SCOP_BEGIN and ending at SCOP_END.  */
1002
1003 void
1004 scop_detection::add_scop (sese_l s)
1005 {
1006   gcc_assert (s);
1007
1008   /* Do not add scops with only one loop.  */
1009   if (region_has_one_loop (s))
1010     {
1011       DEBUG_PRINT (dp << "[scop-detection-fail] Discarding one loop SCoP.\n";
1012                    print_sese (dump_file, s));
1013       return;
1014     }
1015
1016   if (get_exit_bb (s) == EXIT_BLOCK_PTR_FOR_FN (cfun))
1017     {
1018       DEBUG_PRINT (dp << "[scop-detection-fail] "
1019                       << "Discarding SCoP exiting to return.";
1020                    print_sese (dump_file, s));
1021       return;
1022     }
1023
1024   /* Remove all the scops which are subsumed by s.  */
1025   remove_subscops (s);
1026
1027   /* Remove intersecting scops. FIXME: It will be a good idea to keep
1028      the non-intersecting part of the scop already in the list.  */
1029   remove_intersecting_scops (s);
1030
1031   scops.safe_push (s);
1032   DEBUG_PRINT (dp << "Adding SCoP "; print_sese (dump_file, s));
1033 }
1034
1035 /* Return true when a statement in SCOP cannot be represented by Graphite.
1036    The assumptions are that L1 dominates L2, and SCOP->entry dominates L1.
1037    Limit the number of bbs between adjacent loops to
1038    PARAM_SCOP_MAX_NUM_BBS_BETWEEN_LOOPS.  */
1039
1040 bool
1041 scop_detection::harmful_stmt_in_region (sese_l scop) const
1042 {
1043   basic_block exit_bb = get_exit_bb (scop);
1044   basic_block entry_bb = get_entry_bb (scop);
1045
1046   DEBUG_PRINT (dp << "[checking-harmful-bbs] ";
1047                print_sese (dump_file, scop));
1048   gcc_assert (dominated_by_p (CDI_DOMINATORS, exit_bb, entry_bb));
1049
1050   int depth = bb_dom_dfs_in (CDI_DOMINATORS, exit_bb)
1051     - bb_dom_dfs_in (CDI_DOMINATORS, entry_bb);
1052
1053   gcc_assert (depth > 0);
1054
1055   vec<basic_block> dom
1056       = get_dominated_to_depth (CDI_DOMINATORS, entry_bb, depth);
1057   int i;
1058   basic_block bb;
1059   FOR_EACH_VEC_ELT (dom, i, bb)
1060     {
1061       DEBUG_PRINT (dp << "Visiting bb_" << bb->index << "\n");
1062
1063       /* We don't want to analyze any bb outside sese.  */
1064       if (!dominated_by_p (CDI_POST_DOMINATORS, bb, exit_bb))
1065         continue;
1066
1067       /* Basic blocks dominated by the scop->exit are not in the scop.  */
1068       if (bb != exit_bb && dominated_by_p (CDI_DOMINATORS, bb, exit_bb))
1069         continue;
1070
1071       /* The basic block should not be part of an irreducible loop.  */
1072       if (bb->flags & BB_IRREDUCIBLE_LOOP)
1073         {
1074           dom.release ();
1075           return true;
1076         }
1077
1078       if (harmful_stmt_in_bb (scop, bb))
1079         {
1080           dom.release ();
1081           return true;
1082         }
1083     }
1084
1085   dom.release ();
1086   return false;
1087 }
1088
1089 /* Returns true if S1 subsumes/surrounds S2.  */
1090 bool
1091 scop_detection::subsumes (sese_l s1, sese_l s2)
1092 {
1093   if (dominated_by_p (CDI_DOMINATORS, get_entry_bb (s2),
1094                       get_entry_bb (s1))
1095       && dominated_by_p (CDI_POST_DOMINATORS, s2.exit->dest,
1096                          s1.exit->dest))
1097     return true;
1098   return false;
1099 }
1100
1101 /* Remove a SCoP which is subsumed by S1.  */
1102 void
1103 scop_detection::remove_subscops (sese_l s1)
1104 {
1105   int j;
1106   sese_l *s2;
1107   FOR_EACH_VEC_ELT_REVERSE (scops, j, s2)
1108     {
1109       if (subsumes (s1, *s2))
1110         {
1111           DEBUG_PRINT (dp << "Removing sub-SCoP";
1112                        print_sese (dump_file, *s2));
1113           scops.unordered_remove (j);
1114         }
1115     }
1116 }
1117
1118 /* Returns true if S1 intersects with S2.  Since we already know that S1 does
1119    not subsume S2 or vice-versa, we only check for entry bbs.  */
1120
1121 bool
1122 scop_detection::intersects (sese_l s1, sese_l s2)
1123 {
1124   if (dominated_by_p (CDI_DOMINATORS, get_entry_bb (s2),
1125                       get_entry_bb (s1))
1126       && !dominated_by_p (CDI_DOMINATORS, get_entry_bb (s2),
1127                           get_exit_bb (s1)))
1128     return true;
1129   if ((s1.exit == s2.entry) || (s2.exit == s1.entry))
1130     return true;
1131
1132   return false;
1133 }
1134
1135 /* Remove one of the scops when it intersects with any other.  */
1136
1137 void
1138 scop_detection::remove_intersecting_scops (sese_l s1)
1139 {
1140   int j;
1141   sese_l *s2;
1142   FOR_EACH_VEC_ELT_REVERSE (scops, j, s2)
1143     {
1144       if (intersects (s1, *s2))
1145         {
1146           DEBUG_PRINT (dp << "Removing intersecting SCoP";
1147                        print_sese (dump_file, *s2);
1148                        dp << "Intersects with:";
1149                        print_sese (dump_file, s1));
1150           scops.unordered_remove (j);
1151         }
1152     }
1153 }
1154
1155 /* Something like "n * m" is not allowed.  */
1156
1157 bool
1158 scop_detection::graphite_can_represent_init (tree e)
1159 {
1160   switch (TREE_CODE (e))
1161     {
1162     case POLYNOMIAL_CHREC:
1163       return graphite_can_represent_init (CHREC_LEFT (e))
1164         && graphite_can_represent_init (CHREC_RIGHT (e));
1165
1166     case MULT_EXPR:
1167       if (chrec_contains_symbols (TREE_OPERAND (e, 0)))
1168         return graphite_can_represent_init (TREE_OPERAND (e, 0))
1169           && tree_fits_shwi_p (TREE_OPERAND (e, 1));
1170       else
1171         return graphite_can_represent_init (TREE_OPERAND (e, 1))
1172           && tree_fits_shwi_p (TREE_OPERAND (e, 0));
1173
1174     case PLUS_EXPR:
1175     case POINTER_PLUS_EXPR:
1176     case MINUS_EXPR:
1177       return graphite_can_represent_init (TREE_OPERAND (e, 0))
1178         && graphite_can_represent_init (TREE_OPERAND (e, 1));
1179
1180     case NEGATE_EXPR:
1181     case BIT_NOT_EXPR:
1182     CASE_CONVERT:
1183     case NON_LVALUE_EXPR:
1184       return graphite_can_represent_init (TREE_OPERAND (e, 0));
1185
1186     default:
1187       break;
1188     }
1189
1190   return true;
1191 }
1192
1193 /* Return true when SCEV can be represented in the polyhedral model.
1194
1195    An expression can be represented, if it can be expressed as an
1196    affine expression.  For loops (i, j) and parameters (m, n) all
1197    affine expressions are of the form:
1198
1199    x1 * i + x2 * j + x3 * m + x4 * n + x5 * 1 where x1..x5 element of Z
1200
1201    1 i + 20 j + (-2) m + 25
1202
1203    Something like "i * n" or "n * m" is not allowed.  */
1204
1205 bool
1206 scop_detection::graphite_can_represent_scev (tree scev)
1207 {
1208   if (chrec_contains_undetermined (scev))
1209     return false;
1210
1211   /* We disable the handling of pointer types, because it’s currently not
1212      supported by Graphite with the isl AST generator. SSA_NAME nodes are
1213      the only nodes, which are disabled in case they are pointers to object
1214      types, but this can be changed.  */
1215
1216   if (POINTER_TYPE_P (TREE_TYPE (scev)) && TREE_CODE (scev) == SSA_NAME)
1217     return false;
1218
1219   switch (TREE_CODE (scev))
1220     {
1221     case NEGATE_EXPR:
1222     case BIT_NOT_EXPR:
1223     CASE_CONVERT:
1224     case NON_LVALUE_EXPR:
1225       return graphite_can_represent_scev (TREE_OPERAND (scev, 0));
1226
1227     case PLUS_EXPR:
1228     case POINTER_PLUS_EXPR:
1229     case MINUS_EXPR:
1230       return graphite_can_represent_scev (TREE_OPERAND (scev, 0))
1231         && graphite_can_represent_scev (TREE_OPERAND (scev, 1));
1232
1233     case MULT_EXPR:
1234       return !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev, 0)))
1235         && !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev, 1)))
1236         && !(chrec_contains_symbols (TREE_OPERAND (scev, 0))
1237              && chrec_contains_symbols (TREE_OPERAND (scev, 1)))
1238         && graphite_can_represent_init (scev)
1239         && graphite_can_represent_scev (TREE_OPERAND (scev, 0))
1240         && graphite_can_represent_scev (TREE_OPERAND (scev, 1));
1241
1242     case POLYNOMIAL_CHREC:
1243       /* Check for constant strides.  With a non constant stride of
1244          'n' we would have a value of 'iv * n'.  Also check that the
1245          initial value can represented: for example 'n * m' cannot be
1246          represented.  */
1247       if (!evolution_function_right_is_integer_cst (scev)
1248           || !graphite_can_represent_init (scev))
1249         return false;
1250       return graphite_can_represent_scev (CHREC_LEFT (scev));
1251
1252     default:
1253       break;
1254     }
1255
1256   /* Only affine functions can be represented.  */
1257   if (tree_contains_chrecs (scev, NULL) || !scev_is_linear_expression (scev))
1258     return false;
1259
1260   return true;
1261 }
1262
1263 /* Return true when EXPR can be represented in the polyhedral model.
1264
1265    This means an expression can be represented, if it is linear with respect to
1266    the loops and the strides are non parametric.  LOOP is the place where the
1267    expr will be evaluated.  SCOP defines the region we analyse.  */
1268
1269 bool
1270 scop_detection::graphite_can_represent_expr (sese_l scop, loop_p loop,
1271                                              tree expr)
1272 {
1273   tree scev = scalar_evolution_in_region (scop, loop, expr);
1274   return graphite_can_represent_scev (scev);
1275 }
1276
1277 /* Return true if the data references of STMT can be represented by Graphite.
1278    We try to analyze the data references in a loop contained in the SCOP.  */
1279
1280 bool
1281 scop_detection::stmt_has_simple_data_refs_p (sese_l scop, gimple *stmt)
1282 {
1283   loop_p nest = outermost_loop_in_sese (scop, gimple_bb (stmt));
1284   loop_p loop = loop_containing_stmt (stmt);
1285   vec<data_reference_p> drs = vNULL;
1286
1287   graphite_find_data_references_in_stmt (nest, loop, stmt, &drs);
1288
1289   int j;
1290   data_reference_p dr;
1291   FOR_EACH_VEC_ELT (drs, j, dr)
1292     {
1293       int nb_subscripts = DR_NUM_DIMENSIONS (dr);
1294
1295       if (nb_subscripts < 1)
1296         {
1297           free_data_refs (drs);
1298           return false;
1299         }
1300
1301       tree ref = DR_REF (dr);
1302
1303       for (int i = nb_subscripts - 1; i >= 0; i--)
1304         {
1305           if (!graphite_can_represent_scev (DR_ACCESS_FN (dr, i))
1306               || (TREE_CODE (ref) != ARRAY_REF && TREE_CODE (ref) != MEM_REF
1307                   && TREE_CODE (ref) != COMPONENT_REF))
1308             {
1309               free_data_refs (drs);
1310               return false;
1311             }
1312
1313           ref = TREE_OPERAND (ref, 0);
1314         }
1315     }
1316
1317     free_data_refs (drs);
1318     return true;
1319 }
1320
1321 /* GIMPLE_ASM and GIMPLE_CALL may embed arbitrary side effects.
1322    Calls have side-effects, except those to const or pure
1323    functions.  */
1324
1325 static bool
1326 stmt_has_side_effects (gimple *stmt)
1327 {
1328   if (gimple_has_volatile_ops (stmt)
1329       || (gimple_code (stmt) == GIMPLE_CALL
1330           && !(gimple_call_flags (stmt) & (ECF_CONST | ECF_PURE)))
1331       || (gimple_code (stmt) == GIMPLE_ASM))
1332     {
1333       DEBUG_PRINT (dp << "[scop-detection-fail] "
1334                       << "Statement has side-effects:\n";
1335         print_gimple_stmt (dump_file, stmt, 0, TDF_VOPS | TDF_MEMSYMS));
1336       return true;
1337     }
1338   return false;
1339 }
1340
1341 /* Returns true if STMT can be represented in polyhedral model. LABEL,
1342    simple COND stmts, pure calls, and assignments can be repesented.  */
1343
1344 bool
1345 scop_detection::graphite_can_represent_stmt (sese_l scop, gimple *stmt,
1346                                              basic_block bb)
1347 {
1348   loop_p loop = bb->loop_father;
1349   switch (gimple_code (stmt))
1350     {
1351     case GIMPLE_LABEL:
1352       return true;
1353
1354     case GIMPLE_COND:
1355       {
1356         /* We can handle all binary comparisons.  Inequalities are
1357            also supported as they can be represented with union of
1358            polyhedra.  */
1359         enum tree_code code = gimple_cond_code (stmt);
1360         if (!(code == LT_EXPR
1361               || code == GT_EXPR
1362               || code == LE_EXPR
1363               || code == GE_EXPR
1364               || code == EQ_EXPR
1365               || code == NE_EXPR))
1366           {
1367             DEBUG_PRINT (dp << "[scop-detection-fail] "
1368                             << "Graphite cannot handle cond stmt:\n";
1369                          print_gimple_stmt (dump_file, stmt, 0,
1370                                             TDF_VOPS | TDF_MEMSYMS));
1371             return false;
1372           }
1373
1374         for (unsigned i = 0; i < 2; ++i)
1375           {
1376             tree op = gimple_op (stmt, i);
1377             if (!graphite_can_represent_expr (scop, loop, op)
1378                 /* We can only constrain on integer type.  */
1379                 || (TREE_CODE (TREE_TYPE (op)) != INTEGER_TYPE))
1380               {
1381                 DEBUG_PRINT (dp << "[scop-detection-fail] "
1382                                 << "Graphite cannot represent stmt:\n";
1383                              print_gimple_stmt (dump_file, stmt, 0,
1384                                                 TDF_VOPS | TDF_MEMSYMS));
1385                 return false;
1386               }
1387           }
1388
1389         return true;
1390       }
1391
1392     case GIMPLE_ASSIGN:
1393     case GIMPLE_CALL:
1394       return true;
1395
1396     default:
1397       /* These nodes cut a new scope.  */
1398       DEBUG_PRINT (
1399           dp << "[scop-detection-fail] "
1400              << "Gimple stmt not handled in Graphite:\n";
1401           print_gimple_stmt (dump_file, stmt, 0, TDF_VOPS | TDF_MEMSYMS));
1402       return false;
1403     }
1404 }
1405
1406 /* Return true only when STMT is simple enough for being handled by Graphite.
1407    This depends on SCOP, as the parameters are initialized relatively to
1408    this basic block, the linear functions are initialized based on the outermost
1409    loop containing STMT inside the SCOP.  BB is the place where we try to
1410    evaluate the STMT.  */
1411
1412 bool
1413 scop_detection::stmt_simple_for_scop_p (sese_l scop, gimple *stmt,
1414                                         basic_block bb) const
1415 {
1416   gcc_assert (scop);
1417
1418   if (is_gimple_debug (stmt))
1419     return true;
1420
1421   if (stmt_has_side_effects (stmt))
1422     return false;
1423
1424   if (!stmt_has_simple_data_refs_p (scop, stmt))
1425     {
1426       DEBUG_PRINT (dp << "[scop-detection-fail] "
1427                       << "Graphite cannot handle data-refs in stmt:\n";
1428         print_gimple_stmt (dump_file, stmt, 0, TDF_VOPS|TDF_MEMSYMS););
1429       return false;
1430     }
1431
1432   return graphite_can_represent_stmt (scop, stmt, bb);
1433 }
1434
1435 /* Return true when BB contains a harmful operation for a scop: that
1436    can be a function call with side effects, the induction variables
1437    are not linear with respect to SCOP, etc.  The current open
1438    scop should end before this statement.  */
1439
1440 bool
1441 scop_detection::harmful_stmt_in_bb (sese_l scop, basic_block bb) const
1442 {
1443   gimple_stmt_iterator gsi;
1444
1445   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1446     if (!stmt_simple_for_scop_p (scop, gsi_stmt (gsi), bb))
1447       return true;
1448
1449   return false;
1450 }
1451
1452 /* Return true when the body of LOOP has statements that can be represented as a
1453    valid scop.  */
1454
1455 bool
1456 scop_detection::loop_body_is_valid_scop (loop_p loop, sese_l scop) const
1457 {
1458   if (!loop_ivs_can_be_represented (loop))
1459     {
1460       DEBUG_PRINT (dp << "[scop-detection-fail] loop_" << loop->num
1461                       << "IV cannot be represented.\n");
1462       return false;
1463     }
1464
1465   if (!loop_nest_has_data_refs (loop))
1466     {
1467       DEBUG_PRINT (dp << "[scop-detection-fail] loop_" << loop->num
1468                       << "does not have any data reference.\n");
1469       return false;
1470     }
1471
1472   basic_block *bbs = get_loop_body (loop);
1473   for (unsigned i = 0; i < loop->num_nodes; i++)
1474     {
1475       basic_block bb = bbs[i];
1476
1477       if (harmful_stmt_in_bb (scop, bb))
1478         return false;
1479     }
1480   free (bbs);
1481
1482   if (loop->inner)
1483     {
1484       loop = loop->inner;
1485       while (loop)
1486         {
1487           if (!loop_body_is_valid_scop (loop, scop))
1488             return false;
1489           loop = loop->next;
1490         }
1491     }
1492
1493   return true;
1494 }
1495
1496 /* Returns the number of pbbs that are in loops contained in SCOP.  */
1497
1498 int
1499 scop_detection::nb_pbbs_in_loops (scop_p scop)
1500 {
1501   int i;
1502   poly_bb_p pbb;
1503   int res = 0;
1504
1505   FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
1506     if (loop_in_sese_p (gbb_loop (PBB_BLACK_BOX (pbb)), scop->scop_info->region))
1507       res++;
1508
1509   return res;
1510 }
1511
1512 /* When parameter NAME is in REGION, returns its index in SESE_PARAMS.
1513    Otherwise returns -1.  */
1514
1515 static inline int
1516 parameter_index_in_region_1 (tree name, sese_info_p region)
1517 {
1518   int i;
1519   tree p;
1520
1521   gcc_assert (TREE_CODE (name) == SSA_NAME);
1522
1523   FOR_EACH_VEC_ELT (region->params, i, p)
1524     if (p == name)
1525       return i;
1526
1527   return -1;
1528 }
1529
1530 /* When the parameter NAME is in REGION, returns its index in
1531    SESE_PARAMS.  Otherwise this function inserts NAME in SESE_PARAMS
1532    and returns the index of NAME.  */
1533
1534 static int
1535 parameter_index_in_region (tree name, sese_info_p region)
1536 {
1537   int i;
1538
1539   gcc_assert (TREE_CODE (name) == SSA_NAME);
1540
1541   /* Cannot constrain on anything else than INTEGER_TYPE parameters.  */
1542   if (TREE_CODE (TREE_TYPE (name)) != INTEGER_TYPE)
1543     return -1;
1544
1545   if (!invariant_in_sese_p_rec (name, region->region, NULL))
1546     return -1;
1547
1548   i = parameter_index_in_region_1 (name, region);
1549   if (i != -1)
1550     return i;
1551
1552   i = region->params.length ();
1553   region->params.safe_push (name);
1554   return i;
1555 }
1556
1557 /* In the context of sese S, scan the expression E and translate it to
1558    a linear expression C.  When parsing a symbolic multiplication, K
1559    represents the constant multiplier of an expression containing
1560    parameters.  */
1561
1562 static void
1563 scan_tree_for_params (sese_info_p s, tree e)
1564 {
1565   if (e == chrec_dont_know)
1566     return;
1567
1568   switch (TREE_CODE (e))
1569     {
1570     case POLYNOMIAL_CHREC:
1571       scan_tree_for_params (s, CHREC_LEFT (e));
1572       break;
1573
1574     case MULT_EXPR:
1575       if (chrec_contains_symbols (TREE_OPERAND (e, 0)))
1576         scan_tree_for_params (s, TREE_OPERAND (e, 0));
1577       else
1578         scan_tree_for_params (s, TREE_OPERAND (e, 1));
1579       break;
1580
1581     case PLUS_EXPR:
1582     case POINTER_PLUS_EXPR:
1583     case MINUS_EXPR:
1584       scan_tree_for_params (s, TREE_OPERAND (e, 0));
1585       scan_tree_for_params (s, TREE_OPERAND (e, 1));
1586       break;
1587
1588     case NEGATE_EXPR:
1589     case BIT_NOT_EXPR:
1590     CASE_CONVERT:
1591     case NON_LVALUE_EXPR:
1592       scan_tree_for_params (s, TREE_OPERAND (e, 0));
1593       break;
1594
1595     case SSA_NAME:
1596       parameter_index_in_region (e, s);
1597       break;
1598
1599     case INTEGER_CST:
1600     case ADDR_EXPR:
1601     case REAL_CST:
1602     case COMPLEX_CST:
1603     case VECTOR_CST:
1604       break;
1605
1606    default:
1607       gcc_unreachable ();
1608       break;
1609     }
1610 }
1611
1612 /* Find parameters with respect to REGION in BB. We are looking in memory
1613    access functions, conditions and loop bounds.  */
1614
1615 static void
1616 find_params_in_bb (sese_info_p region, gimple_poly_bb_p gbb)
1617 {
1618   /* Find parameters in the access functions of data references.  */
1619   int i;
1620   data_reference_p dr;
1621   FOR_EACH_VEC_ELT (GBB_DATA_REFS (gbb), i, dr)
1622     for (unsigned j = 0; j < DR_NUM_DIMENSIONS (dr); j++)
1623       scan_tree_for_params (region, DR_ACCESS_FN (dr, j));
1624
1625   /* Find parameters in conditional statements.  */
1626   gimple *stmt;
1627   loop_p loop = GBB_BB (gbb)->loop_father;
1628   FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb), i, stmt)
1629     {
1630       tree lhs = scalar_evolution_in_region (region->region, loop,
1631                                              gimple_cond_lhs (stmt));
1632       tree rhs = scalar_evolution_in_region (region->region, loop,
1633                                              gimple_cond_rhs (stmt));
1634
1635       scan_tree_for_params (region, lhs);
1636       scan_tree_for_params (region, rhs);
1637     }
1638 }
1639
1640 /* Record the parameters used in the SCOP.  A variable is a parameter
1641    in a scop if it does not vary during the execution of that scop.  */
1642
1643 static void
1644 find_scop_parameters (scop_p scop)
1645 {
1646   unsigned i;
1647   sese_info_p region = scop->scop_info;
1648   struct loop *loop;
1649
1650   /* Find the parameters used in the loop bounds.  */
1651   FOR_EACH_VEC_ELT (region->loop_nest, i, loop)
1652     {
1653       tree nb_iters = number_of_latch_executions (loop);
1654
1655       if (!chrec_contains_symbols (nb_iters))
1656         continue;
1657
1658       nb_iters = scalar_evolution_in_region (region->region, loop, nb_iters);
1659       scan_tree_for_params (region, nb_iters);
1660     }
1661
1662   /* Find the parameters used in data accesses.  */
1663   poly_bb_p pbb;
1664   FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
1665     find_params_in_bb (region, PBB_BLACK_BOX (pbb));
1666
1667   int nbp = sese_nb_params (region);
1668   scop_set_nb_params (scop, nbp);
1669 }
1670
1671 /* Record DEF if it is used in other bbs different than DEF_BB in the SCOP.  */
1672
1673 static void
1674 build_cross_bb_scalars_def (scop_p scop, tree def, basic_block def_bb,
1675                              vec<tree> *writes)
1676 {
1677   gcc_assert (def);
1678   if (!is_gimple_reg (def))
1679     return;
1680
1681   /* Do not gather scalar variables that can be analyzed by SCEV as they can be
1682      generated out of the induction variables.  */
1683   if (scev_analyzable_p (def, scop->scop_info->region))
1684     return;
1685
1686   gimple *use_stmt;
1687   imm_use_iterator imm_iter;
1688   FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def)
1689     if (def_bb != gimple_bb (use_stmt) && !is_gimple_debug (use_stmt))
1690       {
1691         writes->safe_push (def);
1692         DEBUG_PRINT (dp << "Adding scalar write: ";
1693                      print_generic_expr (dump_file, def, 0);
1694                      dp << "\nFrom stmt: ";
1695                      print_gimple_stmt (dump_file,
1696                                         SSA_NAME_DEF_STMT (def), 0, 0));
1697         /* This is required by the FOR_EACH_IMM_USE_STMT when we want to break
1698            before all the uses have been visited.  */
1699         BREAK_FROM_IMM_USE_STMT (imm_iter);
1700       }
1701 }
1702
1703 /* Record DEF if it is used in other bbs different than DEF_BB in the SCOP.  */
1704
1705 static void
1706 build_cross_bb_scalars_use (scop_p scop, tree use, gimple *use_stmt,
1707                             vec<scalar_use> *reads)
1708 {
1709   gcc_assert (use);
1710   if (!is_gimple_reg (use))
1711     return;
1712
1713   /* Do not gather scalar variables that can be analyzed by SCEV as they can be
1714      generated out of the induction variables.  */
1715   if (scev_analyzable_p (use, scop->scop_info->region))
1716     return;
1717
1718   gimple *def_stmt = SSA_NAME_DEF_STMT (use);
1719   if (gimple_bb (def_stmt) != gimple_bb (use_stmt))
1720     {
1721       DEBUG_PRINT (dp << "Adding scalar read: ";
1722                    print_generic_expr (dump_file, use, 0);
1723                    dp << "\nFrom stmt: ";
1724                    print_gimple_stmt (dump_file, use_stmt, 0, 0));
1725       reads->safe_push (std::make_pair (use_stmt, use));
1726     }
1727 }
1728
1729 /* Record all scalar variables that are defined and used in different BBs of the
1730    SCOP.  */
1731
1732 static void
1733 graphite_find_cross_bb_scalar_vars (scop_p scop, gimple *stmt,
1734                                     vec<scalar_use> *reads, vec<tree> *writes)
1735 {
1736   tree def;
1737
1738   if (gimple_code (stmt) == GIMPLE_ASSIGN)
1739     def = gimple_assign_lhs (stmt);
1740   else if (gimple_code (stmt) == GIMPLE_CALL)
1741     def = gimple_call_lhs (stmt);
1742   else if (gimple_code (stmt) == GIMPLE_PHI)
1743     def = gimple_phi_result (stmt);
1744   else
1745     return;
1746
1747
1748   build_cross_bb_scalars_def (scop, def, gimple_bb (stmt), writes);
1749
1750   ssa_op_iter iter;
1751   use_operand_p use_p;
1752   FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE)
1753     {
1754       tree use = USE_FROM_PTR (use_p);
1755       build_cross_bb_scalars_use (scop, use, stmt, reads);
1756     }
1757 }
1758
1759 /* Generates a polyhedral black box only if the bb contains interesting
1760    information.  */
1761
1762 static gimple_poly_bb_p
1763 try_generate_gimple_bb (scop_p scop, basic_block bb)
1764 {
1765   vec<data_reference_p> drs = vNULL;
1766   vec<tree> writes = vNULL;
1767   vec<scalar_use> reads = vNULL;
1768
1769   sese_l region = scop->scop_info->region;
1770   loop_p nest = outermost_loop_in_sese (region, bb);
1771
1772   loop_p loop = bb->loop_father;
1773   if (!loop_in_sese_p (loop, region))
1774     loop = nest;
1775
1776   for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
1777        gsi_next (&gsi))
1778     {
1779       gimple *stmt = gsi_stmt (gsi);
1780       if (is_gimple_debug (stmt))
1781         continue;
1782
1783       graphite_find_data_references_in_stmt (nest, loop, stmt, &drs);
1784       graphite_find_cross_bb_scalar_vars (scop, stmt, &reads, &writes);
1785     }
1786
1787   for (gphi_iterator psi = gsi_start_phis (bb); !gsi_end_p (psi);
1788        gsi_next (&psi))
1789     if (!virtual_operand_p (gimple_phi_result (psi.phi ())))
1790       graphite_find_cross_bb_scalar_vars (scop, psi.phi (), &reads, &writes);
1791
1792   if (drs.is_empty () && writes.is_empty () && reads.is_empty ())
1793     return NULL;
1794
1795   return new_gimple_poly_bb (bb, drs, reads, writes);
1796 }
1797
1798 /* Compute alias-sets for all data references in DRS.  */
1799
1800 static void
1801 build_alias_set (scop_p scop)
1802 {
1803   int num_vertices = scop->drs.length ();
1804   struct graph *g = new_graph (num_vertices);
1805   dr_info *dr1, *dr2;
1806   int i, j;
1807   int *all_vertices;
1808
1809   FOR_EACH_VEC_ELT (scop->drs, i, dr1)
1810     for (j = i+1; scop->drs.iterate (j, &dr2); j++)
1811       if (dr_may_alias_p (dr1->dr, dr2->dr, true))
1812         {
1813           add_edge (g, i, j);
1814           add_edge (g, j, i);
1815         }
1816
1817   all_vertices = XNEWVEC (int, num_vertices);
1818   for (i = 0; i < num_vertices; i++)
1819     all_vertices[i] = i;
1820
1821   graphds_dfs (g, all_vertices, num_vertices, NULL, true, NULL);
1822   free (all_vertices);
1823
1824   for (i = 0; i < g->n_vertices; i++)
1825     scop->drs[i].alias_set = g->vertices[i].component + 1;
1826
1827   free_graph (g);
1828 }
1829
1830 /* Gather BBs and conditions for a SCOP.  */
1831 class gather_bbs : public dom_walker
1832 {
1833 public:
1834   gather_bbs (cdi_direction, scop_p);
1835
1836   virtual edge before_dom_children (basic_block);
1837   virtual void after_dom_children (basic_block);
1838
1839 private:
1840   auto_vec<gimple *, 3> conditions, cases;
1841   scop_p scop;
1842 };
1843 }
1844 gather_bbs::gather_bbs (cdi_direction direction, scop_p scop)
1845   : dom_walker (direction), scop (scop)
1846 {
1847 }
1848
1849 /* Call-back for dom_walk executed before visiting the dominated
1850    blocks.  */
1851
1852 edge
1853 gather_bbs::before_dom_children (basic_block bb)
1854 {
1855   if (!bb_in_sese_p (bb, scop->scop_info->region))
1856     return NULL;
1857
1858   gcond *stmt = single_pred_cond_non_loop_exit (bb);
1859
1860   if (stmt)
1861     {
1862       edge e = single_pred_edge (bb);
1863
1864       conditions.safe_push (stmt);
1865
1866       if (e->flags & EDGE_TRUE_VALUE)
1867         cases.safe_push (stmt);
1868       else
1869         cases.safe_push (NULL);
1870     }
1871
1872   scop->scop_info->bbs.safe_push (bb);
1873
1874   gimple_poly_bb_p gbb = try_generate_gimple_bb (scop, bb);
1875   if (!gbb)
1876     return NULL;
1877
1878   GBB_CONDITIONS (gbb) = conditions.copy ();
1879   GBB_CONDITION_CASES (gbb) = cases.copy ();
1880
1881   poly_bb_p pbb = new_poly_bb (scop, gbb);
1882   scop->pbbs.safe_push (pbb);
1883
1884   int i;
1885   data_reference_p dr;
1886   FOR_EACH_VEC_ELT (gbb->data_refs, i, dr)
1887     {
1888       DEBUG_PRINT (dp << "Adding memory ";
1889                    if (dr->is_read)
1890                      dp << "read: ";
1891                    else
1892                      dp << "write: ";
1893                    print_generic_expr (dump_file, dr->ref, 0);
1894                    dp << "\nFrom stmt: ";
1895                    print_gimple_stmt (dump_file, dr->stmt, 0, 0));
1896
1897       scop->drs.safe_push (dr_info (dr, pbb));
1898     }
1899
1900   return NULL;
1901 }
1902
1903 /* Call-back for dom_walk executed after visiting the dominated
1904    blocks.  */
1905
1906 void
1907 gather_bbs::after_dom_children (basic_block bb)
1908 {
1909   if (!bb_in_sese_p (bb, scop->scop_info->region))
1910     return;
1911
1912   if (single_pred_cond_non_loop_exit (bb))
1913     {
1914       conditions.pop ();
1915       cases.pop ();
1916     }
1917 }
1918
1919 /* Find Static Control Parts (SCoP) in the current function and pushes
1920    them to SCOPS.  */
1921
1922 void
1923 build_scops (vec<scop_p> *scops)
1924 {
1925   if (dump_file)
1926     dp.set_dump_file (dump_file);
1927
1928   canonicalize_loop_closed_ssa_form ();
1929
1930   scop_detection sb;
1931   sb.build_scop_depth (scop_detection::invalid_sese, current_loops->tree_root);
1932
1933   /* Now create scops from the lightweight SESEs.  */
1934   vec<sese_l> scops_l = sb.get_scops ();
1935   int i;
1936   sese_l *s;
1937   FOR_EACH_VEC_ELT (scops_l, i, s)
1938     {
1939       scop_p scop = new_scop (s->entry, s->exit);
1940
1941       /* Record all basic blocks and their conditions in REGION.  */
1942       gather_bbs (CDI_DOMINATORS, scop).walk (cfun->cfg->x_entry_block_ptr);
1943
1944       build_alias_set (scop);
1945
1946       /* Do not optimize a scop containing only PBBs that do not belong
1947          to any loops.  */
1948       if (sb.nb_pbbs_in_loops (scop) == 0)
1949         {
1950           DEBUG_PRINT (dp << "[scop-detection-fail] no data references.\n");
1951           free_scop (scop);
1952           continue;
1953         }
1954
1955       unsigned max_arrays = PARAM_VALUE (PARAM_GRAPHITE_MAX_ARRAYS_PER_SCOP);
1956       if (scop->drs.length () >= max_arrays)
1957         {
1958           DEBUG_PRINT (dp << "[scop-detection-fail] too many data references: "
1959                        << scop->drs.length ()
1960                        << " is larger than --param graphite-max-arrays-per-scop="
1961                        << max_arrays << ".\n");
1962           free_scop (scop);
1963           continue;
1964         }
1965
1966       build_sese_loop_nests (scop->scop_info);
1967
1968       find_scop_parameters (scop);
1969       graphite_dim_t max_dim = PARAM_VALUE (PARAM_GRAPHITE_MAX_NB_SCOP_PARAMS);
1970
1971       if (scop_nb_params (scop) > max_dim)
1972         {
1973           DEBUG_PRINT (dp << "[scop-detection-fail] too many parameters: "
1974                           << scop_nb_params (scop)
1975                           << " larger than --param graphite-max-nb-scop-params="
1976                           << max_dim << ".\n");
1977           free_scop (scop);
1978           continue;
1979         }
1980
1981       scops->safe_push (scop);
1982     }
1983
1984   DEBUG_PRINT (dp << "number of SCoPs: " << (scops ? scops->length () : 0););
1985 }
1986
1987 #endif /* HAVE_isl */