gcc/graphite-scop-detection.c

   1 /* Detection of Static Control Parts (SCoP) for Graphite.
   2    Copyright (C) 2009-2017 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   dump_flags_t tmp_dump_flags = dump_flags;
 100   dump_flags = TDF_NONE;
 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 (types_compatible_p (TREE_TYPE (gimple_phi_result (p1)),
 277                               TREE_TYPE (gimple_phi_result (p2)))
 278           && operand_equal_p (gimple_phi_arg_def (p1, 0),
 279                               gimple_phi_arg_def (p2, 0), 0));
 280 }
 281
 282 static void make_close_phi_nodes_unique (basic_block bb);
 283
 284 /* Remove the close phi node at GSI and replace its rhs with the rhs
 285    of PHI.  */
 286
 287 static void
 288 remove_duplicate_close_phi (gphi *phi, gphi_iterator *gsi)
 289 {
 290   gimple *use_stmt;
 291   use_operand_p use_p;
 292   imm_use_iterator imm_iter;
 293   tree res = gimple_phi_result (phi);
 294   tree def = gimple_phi_result (gsi->phi ());
 295
 296   gcc_assert (same_close_phi_node (phi, gsi->phi ()));
 297
 298   FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def)
 299     {
 300       FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter)
 301         SET_USE (use_p, res);
 302
 303       update_stmt (use_stmt);
 304
 305       /* It is possible that we just created a duplicate close-phi
 306          for an already-processed containing loop.  Check for this
 307          case and clean it up.  */
 308       if (gimple_code (use_stmt) == GIMPLE_PHI
 309           && gimple_phi_num_args (use_stmt) == 1)
 310         make_close_phi_nodes_unique (gimple_bb (use_stmt));
 311     }
 312
 313   remove_phi_node (gsi, true);
 314 }
 315
 316 /* Removes all the close phi duplicates from BB.  */
 317
 318 static void
 319 make_close_phi_nodes_unique (basic_block bb)
 320 {
 321   gphi_iterator psi;
 322
 323   for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
 324     {
 325       gphi_iterator gsi = psi;
 326       gphi *phi = psi.phi ();
 327
 328       /* At this point, PHI should be a close phi in normal form.  */
 329       gcc_assert (gimple_phi_num_args (phi) == 1);
 330
 331       /* Iterate over the next phis and remove duplicates.  */
 332       gsi_next (&gsi);
 333       while (!gsi_end_p (gsi))
 334         if (same_close_phi_node (phi, gsi.phi ()))
 335           remove_duplicate_close_phi (phi, &gsi);
 336         else
 337           gsi_next (&gsi);
 338     }
 339 }
 340
 341 /* Return true when NAME is defined in LOOP.  */
 342
 343 static bool
 344 defined_in_loop_p (tree name, loop_p loop)
 345 {
 346   gcc_assert (TREE_CODE (name) == SSA_NAME);
 347   return loop == loop_containing_stmt (SSA_NAME_DEF_STMT (name));
 348 }
 349
 350 /* Transforms LOOP to the canonical loop closed SSA form.  */
 351
 352 static void
 353 canonicalize_loop_closed_ssa (loop_p loop)
 354 {
 355   edge e = single_exit (loop);
 356   basic_block bb;
 357
 358   if (!e || e->flags & EDGE_ABNORMAL)
 359     return;
 360
 361   bb = e->dest;
 362
 363   if (single_pred_p (bb))
 364     {
 365       e = split_block_after_labels (bb);
 366       DEBUG_PRINT (dp << "Splitting bb_" << bb->index << ".\n");
 367       make_close_phi_nodes_unique (e->src);
 368     }
 369   else
 370     {
 371       gphi_iterator psi;
 372       basic_block close = split_edge (e);
 373
 374       e = single_succ_edge (close);
 375       DEBUG_PRINT (dp << "Splitting edge (" << e->src->index << ","
 376                       << e->dest->index << ")\n");
 377
 378       for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
 379         {
 380           gphi *phi = psi.phi ();
 381           unsigned i;
 382
 383           for (i = 0; i < gimple_phi_num_args (phi); i++)
 384             if (gimple_phi_arg_edge (phi, i) == e)
 385               {
 386                 tree res, arg = gimple_phi_arg_def (phi, i);
 387                 use_operand_p use_p;
 388                 gphi *close_phi;
 389
 390                 /* Only add close phi nodes for SSA_NAMEs defined in LOOP.  */
 391                 if (TREE_CODE (arg) != SSA_NAME
 392                     || !defined_in_loop_p (arg, loop))
 393                   continue;
 394
 395                 close_phi = create_phi_node (NULL_TREE, close);
 396                 res = create_new_def_for (arg, close_phi,
 397                                           gimple_phi_result_ptr (close_phi));
 398                 add_phi_arg (close_phi, arg,
 399                              gimple_phi_arg_edge (close_phi, 0),
 400                              UNKNOWN_LOCATION);
 401                 use_p = gimple_phi_arg_imm_use_ptr (phi, i);
 402                 replace_exp (use_p, res);
 403                 update_stmt (phi);
 404               }
 405         }
 406
 407       make_close_phi_nodes_unique (close);
 408     }
 409
 410   /* The code above does not properly handle changes in the post dominance
 411      information (yet).  */
 412   recompute_all_dominators ();
 413 }
 414
 415 /* Converts the current loop closed SSA form to a canonical form
 416    expected by the Graphite code generation.
 417
 418    The loop closed SSA form has the following invariant: a variable
 419    defined in a loop that is used outside the loop appears only in the
 420    phi nodes in the destination of the loop exit.  These phi nodes are
 421    called close phi nodes.
 422
 423    The canonical loop closed SSA form contains the extra invariants:
 424
 425    - when the loop contains only one exit, the close phi nodes contain
 426    only one argument.  That implies that the basic block that contains
 427    the close phi nodes has only one predecessor, that is a basic block
 428    in the loop.
 429
 430    - the basic block containing the close phi nodes does not contain
 431    other statements.
 432
 433    - there exist only one phi node per definition in the loop.
 434 */
 435
 436 static void
 437 canonicalize_loop_closed_ssa_form (void)
 438 {
 439   checking_verify_loop_closed_ssa (true);
 440
 441   loop_p loop;
 442   FOR_EACH_LOOP (loop, 0)
 443     canonicalize_loop_closed_ssa (loop);
 444
 445   rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
 446   update_ssa (TODO_update_ssa);
 447
 448   checking_verify_loop_closed_ssa (true);
 449 }
 450
 451 /* Can all ivs be represented by a signed integer?
 452    As isl might generate negative values in its expressions, signed loop ivs
 453    are required in the backend.  */
 454
 455 static bool
 456 loop_ivs_can_be_represented (loop_p loop)
 457 {
 458   unsigned type_long_long = TYPE_PRECISION (long_long_integer_type_node);
 459   for (gphi_iterator psi = gsi_start_phis (loop->header); !gsi_end_p (psi);
 460        gsi_next (&psi))
 461     {
 462       gphi *phi = psi.phi ();
 463       tree res = PHI_RESULT (phi);
 464       tree type = TREE_TYPE (res);
 465
 466       if (TYPE_UNSIGNED (type) && TYPE_PRECISION (type) >= type_long_long)
 467         return false;
 468     }
 469
 470   return true;
 471 }
 472
 473 /* Returns a COND_EXPR statement when BB has a single predecessor, the
 474    edge between BB and its predecessor is not a loop exit edge, and
 475    the last statement of the single predecessor is a COND_EXPR.  */
 476
 477 static gcond *
 478 single_pred_cond_non_loop_exit (basic_block bb)
 479 {
 480   if (single_pred_p (bb))
 481     {
 482       edge e = single_pred_edge (bb);
 483       basic_block pred = e->src;
 484       gimple *stmt;
 485
 486       if (loop_depth (pred->loop_father) > loop_depth (bb->loop_father))
 487         return NULL;
 488
 489       stmt = last_stmt (pred);
 490
 491       if (stmt && gimple_code (stmt) == GIMPLE_COND)
 492         return as_a<gcond *> (stmt);
 493     }
 494
 495   return NULL;
 496 }
 497
 498 namespace
 499 {
 500
 501 /* Build the maximal scop containing LOOPs and add it to SCOPS.  */
 502
 503 class scop_detection
 504 {
 505 public:
 506   scop_detection () : scops (vNULL) {}
 507
 508   ~scop_detection ()
 509   {
 510     scops.release ();
 511   }
 512
 513   /* A marker for invalid sese_l.  */
 514   static sese_l invalid_sese;
 515
 516   /* Return the SCOPS in this SCOP_DETECTION.  */
 517
 518   vec<sese_l>
 519   get_scops ()
 520   {
 521     return scops;
 522   }
 523
 524   /* Return an sese_l around the LOOP.  */
 525
 526   sese_l get_sese (loop_p loop);
 527
 528   /* Return the closest dominator with a single entry edge.  In case of a
 529      back-loop the back-edge is not counted.  */
 530
 531   static edge get_nearest_dom_with_single_entry (basic_block dom);
 532
 533   /* Return the closest post-dominator with a single exit edge.  In case of a
 534      back-loop the back-edge is not counted.  */
 535
 536   static edge get_nearest_pdom_with_single_exit (basic_block dom);
 537
 538   /* Merge scops at same loop depth and returns the new sese.
 539      Returns a new SESE when merge was successful, INVALID_SESE otherwise.  */
 540
 541   sese_l merge_sese (sese_l first, sese_l second) const;
 542
 543   /* Build scop outer->inner if possible.  */
 544
 545   sese_l build_scop_depth (sese_l s, loop_p loop);
 546
 547   /* If loop and loop->next are valid scops, try to merge them.  */
 548
 549   sese_l build_scop_breadth (sese_l s1, loop_p loop);
 550
 551   /* Return true when LOOP is a valid scop, that is a Static Control Part, a
 552      region of code that can be represented in the polyhedral model.  SCOP
 553      defines the region we analyse.  */
 554
 555   bool loop_is_valid_in_scop (loop_p loop, sese_l scop) const;
 556
 557   /* Return true when BEGIN is the preheader edge of a loop with a single exit
 558      END.  */
 559
 560   static bool region_has_one_loop (sese_l s);
 561
 562   /* Add to SCOPS a scop starting at SCOP_BEGIN and ending at SCOP_END.  */
 563
 564   void add_scop (sese_l s);
 565
 566   /* Returns true if S1 subsumes/surrounds S2.  */
 567   static bool subsumes (sese_l s1, sese_l s2);
 568
 569   /* Remove a SCoP which is subsumed by S1.  */
 570   void remove_subscops (sese_l s1);
 571
 572   /* Returns true if S1 intersects with S2.  Since we already know that S1 does
 573      not subsume S2 or vice-versa, we only check for entry bbs.  */
 574
 575   static bool intersects (sese_l s1, sese_l s2);
 576
 577   /* Remove one of the scops when it intersects with any other.  */
 578
 579   void remove_intersecting_scops (sese_l s1);
 580
 581   /* Return true when the body of LOOP has statements that can be represented
 582      as a valid scop.  */
 583
 584   bool loop_body_is_valid_scop (loop_p loop, sese_l scop) const;
 585
 586   /* Return true when BB contains a harmful operation for a scop: that
 587      can be a function call with side effects, the induction variables
 588      are not linear with respect to SCOP, etc.  The current open
 589      scop should end before this statement.  */
 590
 591   bool harmful_stmt_in_bb (sese_l scop, basic_block bb) const;
 592
 593   /* Return true when a statement in SCOP cannot be represented by Graphite.
 594      The assumptions are that L1 dominates L2, and SCOP->entry dominates L1.
 595      Limit the number of bbs between adjacent loops to
 596      PARAM_SCOP_MAX_NUM_BBS_BETWEEN_LOOPS.  */
 597
 598   bool harmful_loop_in_region (sese_l scop) const;
 599
 600   /* Return true only when STMT is simple enough for being handled by Graphite.
 601      This depends on SCOP, as the parameters are initialized relatively to
 602      this basic block, the linear functions are initialized based on the
 603      outermost loop containing STMT inside the SCOP.  BB is the place where we
 604      try to evaluate the STMT.  */
 605
 606   bool stmt_simple_for_scop_p (sese_l scop, gimple *stmt,
 607                                basic_block bb) const;
 608
 609   /* Something like "n * m" is not allowed.  */
 610
 611   static bool graphite_can_represent_init (tree e);
 612
 613   /* Return true when SCEV can be represented in the polyhedral model.
 614
 615      An expression can be represented, if it can be expressed as an
 616      affine expression.  For loops (i, j) and parameters (m, n) all
 617      affine expressions are of the form:
 618
 619      x1 * i + x2 * j + x3 * m + x4 * n + x5 * 1 where x1..x5 element of Z
 620
 621      1 i + 20 j + (-2) m + 25
 622
 623      Something like "i * n" or "n * m" is not allowed.  */
 624
 625   static bool graphite_can_represent_scev (tree scev);
 626
 627   /* Return true when EXPR can be represented in the polyhedral model.
 628
 629      This means an expression can be represented, if it is linear with respect
 630      to the loops and the strides are non parametric.  LOOP is the place where
 631      the expr will be evaluated.  SCOP defines the region we analyse.  */
 632
 633   static bool graphite_can_represent_expr (sese_l scop, loop_p loop,
 634                                            tree expr);
 635
 636   /* Return true if the data references of STMT can be represented by Graphite.
 637      We try to analyze the data references in a loop contained in the SCOP.  */
 638
 639   static bool stmt_has_simple_data_refs_p (sese_l scop, gimple *stmt);
 640
 641   /* Remove the close phi node at GSI and replace its rhs with the rhs
 642      of PHI.  */
 643
 644   static void remove_duplicate_close_phi (gphi *phi, gphi_iterator *gsi);
 645
 646   /* Returns true when Graphite can represent LOOP in SCOP.
 647      FIXME: For the moment, graphite cannot be used on loops that iterate using
 648      induction variables that wrap.  */
 649
 650   static bool can_represent_loop_1 (loop_p loop, sese_l scop);
 651
 652   /* Return true when all the loops within LOOP can be represented by
 653      Graphite.  */
 654
 655   static bool can_represent_loop (loop_p loop, sese_l scop);
 656
 657   /* Returns the number of pbbs that are in loops contained in SCOP.  */
 658
 659   static int nb_pbbs_in_loops (scop_p scop);
 660
 661   static bool graphite_can_represent_stmt (sese_l, gimple *, basic_block);
 662
 663 private:
 664   vec<sese_l> scops;
 665 };
 666
 667 sese_l scop_detection::invalid_sese (NULL, NULL);
 668
 669 /* Return an sese_l around the LOOP.  */
 670
 671 sese_l
 672 scop_detection::get_sese (loop_p loop)
 673 {
 674   if (!loop)
 675     return invalid_sese;
 676
 677   if (!loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS))
 678     return invalid_sese;
 679   edge scop_end = single_exit (loop);
 680   if (!scop_end)
 681     return invalid_sese;
 682   edge scop_begin = loop_preheader_edge (loop);
 683   sese_l s (scop_begin, scop_end);
 684   return s;
 685 }
 686
 687 /* Return the closest dominator with a single entry edge.  */
 688
 689 edge
 690 scop_detection::get_nearest_dom_with_single_entry (basic_block dom)
 691 {
 692   if (!dom->preds)
 693     return NULL;
 694
 695   /* If any of the dominators has two predecessors but one of them is a back
 696      edge, then that basic block also qualifies as a dominator with single
 697      entry.  */
 698   if (dom->preds->length () == 2)
 699     {
 700       /* If e1->src dominates e2->src then e1->src will also dominate dom.  */
 701       edge e1 = (*dom->preds)[0];
 702       edge e2 = (*dom->preds)[1];
 703       loop_p l = dom->loop_father;
 704       loop_p l1 = e1->src->loop_father;
 705       loop_p l2 = e2->src->loop_father;
 706       if (l != l1 && l == l2
 707           && dominated_by_p (CDI_DOMINATORS, e2->src, e1->src))
 708         return e1;
 709       if (l != l2 && l == l1
 710           && dominated_by_p (CDI_DOMINATORS, e1->src, e2->src))
 711         return e2;
 712     }
 713
 714   while (dom->preds->length () != 1)
 715     {
 716       if (dom->preds->length () < 1)
 717         return NULL;
 718       dom = get_immediate_dominator (CDI_DOMINATORS, dom);
 719       if (!dom->preds)
 720         return NULL;
 721     }
 722   return (*dom->preds)[0];
 723 }
 724
 725 /* Return the closest post-dominator with a single exit edge.  In case of a
 726    back-loop the back-edge is not counted.  */
 727
 728 edge
 729 scop_detection::get_nearest_pdom_with_single_exit (basic_block pdom)
 730 {
 731   if (!pdom->succs)
 732     return NULL;
 733
 734   /* If any of the post-dominators has two successors but one of them is a back
 735      edge, then that basic block also qualifies as a post-dominator with single
 736      exit. */
 737   if (pdom->succs->length () == 2)
 738     {
 739       /* If e1->dest post-dominates e2->dest then e1->dest will also
 740          post-dominate pdom.  */
 741       edge e1 = (*pdom->succs)[0];
 742       edge e2 = (*pdom->succs)[1];
 743       loop_p l = pdom->loop_father;
 744       loop_p l1 = e1->dest->loop_father;
 745       loop_p l2 = e2->dest->loop_father;
 746       if (l != l1 && l == l2
 747           && dominated_by_p (CDI_POST_DOMINATORS, e2->dest, e1->dest))
 748         return e1;
 749       if (l != l2 && l == l1
 750           && dominated_by_p (CDI_POST_DOMINATORS, e1->dest, e2->dest))
 751         return e2;
 752     }
 753
 754   while (pdom->succs->length () != 1)
 755     {
 756       if (pdom->succs->length () < 1)
 757         return NULL;
 758       pdom = get_immediate_dominator (CDI_POST_DOMINATORS, pdom);
 759       if (!pdom->succs)
 760         return NULL;
 761     }
 762
 763   return (*pdom->succs)[0];
 764 }
 765
 766 /* Merge scops at same loop depth and returns the new sese.
 767    Returns a new SESE when merge was successful, INVALID_SESE otherwise.  */
 768
 769 sese_l
 770 scop_detection::merge_sese (sese_l first, sese_l second) const
 771 {
 772   /* In the trivial case first/second may be NULL.  */
 773   if (!first)
 774     return second;
 775   if (!second)
 776     return first;
 777
 778   DEBUG_PRINT (dp << "[scop-detection] try merging sese s1: ";
 779                print_sese (dump_file, first);
 780                dp << "[scop-detection] try merging sese s2: ";
 781                print_sese (dump_file, second));
 782
 783   /* Assumption: Both the sese's should be at the same loop depth or one scop
 784      should subsume the other like in case of nested loops.  */
 785
 786   /* Find the common dominators for entry,
 787      and common post-dominators for the exit.  */
 788   basic_block dom = nearest_common_dominator (CDI_DOMINATORS,
 789                                               get_entry_bb (first),
 790                                               get_entry_bb (second));
 791
 792   edge entry = get_nearest_dom_with_single_entry (dom);
 793
 794   if (!entry || (entry->flags & EDGE_IRREDUCIBLE_LOOP))
 795     return invalid_sese;
 796
 797   basic_block pdom = nearest_common_dominator (CDI_POST_DOMINATORS,
 798                                                get_exit_bb (first),
 799                                                get_exit_bb (second));
 800   pdom = nearest_common_dominator (CDI_POST_DOMINATORS, dom, pdom);
 801
 802   edge exit = get_nearest_pdom_with_single_exit (pdom);
 803
 804   if (!exit || (exit->flags & EDGE_IRREDUCIBLE_LOOP))
 805     return invalid_sese;
 806
 807   sese_l combined (entry, exit);
 808
 809   DEBUG_PRINT (dp << "[scop-detection] checking combined sese: ";
 810                print_sese (dump_file, combined));
 811
 812   /* FIXME: We could iterate to find the dom which dominates pdom, and pdom
 813      which post-dominates dom, until it stabilizes.  Also, ENTRY->SRC and
 814      EXIT->DEST should be in the same loop nest.  */
 815   if (!dominated_by_p (CDI_DOMINATORS, pdom, dom)
 816       || loop_depth (entry->src->loop_father)
 817          != loop_depth (exit->dest->loop_father))
 818     return invalid_sese;
 819
 820   /* For now we just bail out when there is a loop exit in the region
 821      that is not also the exit of the region.  We could enlarge the
 822      region to cover the loop that region exits to.  See PR79977.  */
 823   if (loop_outer (entry->src->loop_father))
 824     {
 825       vec<edge> exits = get_loop_exit_edges (entry->src->loop_father);
 826       for (unsigned i = 0; i < exits.length (); ++i)
 827         {
 828           if (exits[i] != exit
 829               && bb_in_region (exits[i]->src, entry->dest, exit->src))
 830             {
 831               DEBUG_PRINT (dp << "[scop-detection-fail] cannot merge seses.\n");
 832               exits.release ();
 833               return invalid_sese;
 834             }
 835         }
 836       exits.release ();
 837     }
 838
 839   /* For now we just want to bail out when exit does not post-dominate entry.
 840      TODO: We might just add a basic_block at the exit to make exit
 841      post-dominate entry (the entire region).  */
 842   if (!dominated_by_p (CDI_POST_DOMINATORS, get_entry_bb (combined),
 843                        get_exit_bb (combined))
 844       || !dominated_by_p (CDI_DOMINATORS, get_exit_bb (combined),
 845                           get_entry_bb (combined)))
 846     {
 847       DEBUG_PRINT (dp << "[scop-detection-fail] cannot merge seses.\n");
 848       return invalid_sese;
 849     }
 850
 851   /* FIXME: We should remove this piece of code once
 852      canonicalize_loop_closed_ssa has been removed, because that function
 853      adds a BB with single exit.  */
 854   if (!trivially_empty_bb_p (get_exit_bb (combined)))
 855     {
 856       /* Find the first empty succ (with single exit) of combined.exit.  */
 857       basic_block imm_succ = combined.exit->dest;
 858       if (single_succ_p (imm_succ)
 859           && single_pred_p (imm_succ)
 860           && trivially_empty_bb_p (imm_succ))
 861         combined.exit = single_succ_edge (imm_succ);
 862       else
 863         {
 864           DEBUG_PRINT (dp << "[scop-detection-fail] Discarding SCoP because "
 865                           << "no single exit (empty succ) for sese exit";
 866                        print_sese (dump_file, combined));
 867           return invalid_sese;
 868         }
 869     }
 870
 871   /* Analyze all the BBs in new sese.  */
 872   if (harmful_loop_in_region (combined))
 873     return invalid_sese;
 874
 875   DEBUG_PRINT (dp << "[merged-sese] s1: "; print_sese (dump_file, combined));
 876
 877   return combined;
 878 }
 879
 880 /* Build scop outer->inner if possible.  */
 881
 882 sese_l
 883 scop_detection::build_scop_depth (sese_l s, loop_p loop)
 884 {
 885   if (!loop)
 886     return s;
 887
 888   DEBUG_PRINT (dp << "[Depth loop_" << loop->num << "]\n");
 889   s = build_scop_depth (s, loop->inner);
 890
 891   sese_l s2 = merge_sese (s, get_sese (loop));
 892   if (!s2)
 893     {
 894       /* s might be a valid scop, so return it and start analyzing from the
 895          adjacent loop.  */
 896       build_scop_depth (invalid_sese, loop->next);
 897       return s;
 898     }
 899
 900   if (!loop_is_valid_in_scop (loop, s2))
 901     return build_scop_depth (invalid_sese, loop->next);
 902
 903   return build_scop_breadth (s2, loop);
 904 }
 905
 906 /* If loop and loop->next are valid scops, try to merge them.  */
 907
 908 sese_l
 909 scop_detection::build_scop_breadth (sese_l s1, loop_p loop)
 910 {
 911   if (!loop)
 912     return s1;
 913   DEBUG_PRINT (dp << "[Breadth loop_" << loop->num << "]\n");
 914   gcc_assert (s1);
 915
 916   loop_p l = loop;
 917   sese_l s2 = build_scop_depth (invalid_sese, l->next);
 918   if (!s2)
 919     {
 920       if (s1)
 921         add_scop (s1);
 922       return s1;
 923     }
 924
 925   sese_l combined = merge_sese (s1, s2);
 926
 927   /* Combining adjacent loops may add unrelated loops into the
 928      region so we have to check all sub-loops of the outer loop
 929      that are in the combined region.  */
 930   if (combined)
 931     for (l = loop_outer (loop)->inner; l; l = l->next)
 932       if (bb_in_sese_p (l->header, combined)
 933           && ! loop_is_valid_in_scop (l, combined))
 934         {
 935           combined = invalid_sese;
 936           break;
 937         }
 938
 939   if (combined)
 940     s1 = combined;
 941   else
 942     add_scop (s2);
 943
 944   if (s1)
 945     add_scop (s1);
 946   return s1;
 947 }
 948
 949 /* Returns true when Graphite can represent LOOP in SCOP.
 950    FIXME: For the moment, graphite cannot be used on loops that iterate using
 951    induction variables that wrap.  */
 952
 953 bool
 954 scop_detection::can_represent_loop_1 (loop_p loop, sese_l scop)
 955 {
 956   tree niter;
 957   struct tree_niter_desc niter_desc;
 958
 959   return single_exit (loop)
 960     && !(loop_preheader_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP)
 961     && number_of_iterations_exit (loop, single_exit (loop), &niter_desc, false)
 962     && niter_desc.control.no_overflow
 963     && (niter = number_of_latch_executions (loop))
 964     && !chrec_contains_undetermined (niter)
 965     && !chrec_contains_undetermined (scalar_evolution_in_region (scop,
 966                                                                  loop, niter))
 967     && graphite_can_represent_expr (scop, loop, niter);
 968 }
 969
 970 /* Return true when all the loops within LOOP can be represented by
 971    Graphite.  */
 972
 973 bool
 974 scop_detection::can_represent_loop (loop_p loop, sese_l scop)
 975 {
 976   if (!can_represent_loop_1 (loop, scop))
 977     return false;
 978   if (loop->inner && !can_represent_loop (loop->inner, scop))
 979     return false;
 980   if (loop->next && !can_represent_loop (loop->next, scop))
 981     return false;
 982
 983   return true;
 984 }
 985
 986 /* Return true when LOOP is a valid scop, that is a Static Control Part, a
 987    region of code that can be represented in the polyhedral model.  SCOP
 988    defines the region we analyse.  */
 989
 990 bool
 991 scop_detection::loop_is_valid_in_scop (loop_p loop, sese_l scop) const
 992 {
 993   if (!scop)
 994     return false;
 995
 996   if (!optimize_loop_nest_for_speed_p (loop))
 997     {
 998       DEBUG_PRINT (dp << "[scop-detection-fail] loop_"
 999                       << loop->num << " is not on a hot path.\n");
1000       return false;
1001     }
1002
1003   if (!can_represent_loop (loop, scop))
1004     {
1005       DEBUG_PRINT (dp << "[scop-detection-fail] cannot represent loop_"
1006                       << loop->num << "\n");
1007       return false;
1008     }
1009
1010   if (loop_body_is_valid_scop (loop, scop))
1011     {
1012       DEBUG_PRINT (dp << "[valid-scop] loop_" << loop->num
1013                       << " is a valid scop.\n");
1014       return true;
1015     }
1016   return false;
1017 }
1018
1019 /* Return true when BEGIN is the preheader edge of a loop with a single exit
1020    END.  */
1021
1022 bool
1023 scop_detection::region_has_one_loop (sese_l s)
1024 {
1025   edge begin = s.entry;
1026   edge end = s.exit;
1027   /* Check for a single perfectly nested loop.  */
1028   if (begin->dest->loop_father->inner)
1029     return false;
1030
1031   /* Otherwise, check whether we have adjacent loops.  */
1032   return begin->dest->loop_father == end->src->loop_father;
1033 }
1034
1035 /* Add to SCOPS a scop starting at SCOP_BEGIN and ending at SCOP_END.  */
1036
1037 void
1038 scop_detection::add_scop (sese_l s)
1039 {
1040   gcc_assert (s);
1041
1042   /* Do not add scops with only one loop.  */
1043   if (region_has_one_loop (s))
1044     {
1045       DEBUG_PRINT (dp << "[scop-detection-fail] Discarding one loop SCoP: ";
1046                    print_sese (dump_file, s));
1047       return;
1048     }
1049
1050   if (get_exit_bb (s) == EXIT_BLOCK_PTR_FOR_FN (cfun))
1051     {
1052       DEBUG_PRINT (dp << "[scop-detection-fail] "
1053                       << "Discarding SCoP exiting to return: ";
1054                    print_sese (dump_file, s));
1055       return;
1056     }
1057
1058   /* Remove all the scops which are subsumed by s.  */
1059   remove_subscops (s);
1060
1061   /* Remove intersecting scops. FIXME: It will be a good idea to keep
1062      the non-intersecting part of the scop already in the list.  */
1063   remove_intersecting_scops (s);
1064
1065   scops.safe_push (s);
1066   DEBUG_PRINT (dp << "[scop-detection] Adding SCoP: "; print_sese (dump_file, s));
1067 }
1068
1069 /* Return true when a statement in SCOP cannot be represented by Graphite.
1070    The assumptions are that L1 dominates L2, and SCOP->entry dominates L1.
1071    Limit the number of bbs between adjacent loops to
1072    PARAM_SCOP_MAX_NUM_BBS_BETWEEN_LOOPS.  */
1073
1074 bool
1075 scop_detection::harmful_loop_in_region (sese_l scop) const
1076 {
1077   basic_block exit_bb = get_exit_bb (scop);
1078   basic_block entry_bb = get_entry_bb (scop);
1079
1080   DEBUG_PRINT (dp << "[checking-harmful-bbs] ";
1081                print_sese (dump_file, scop));
1082   gcc_assert (dominated_by_p (CDI_DOMINATORS, exit_bb, entry_bb));
1083
1084   auto_vec<basic_block> worklist;
1085   auto_bitmap loops;
1086
1087   worklist.safe_push (entry_bb);
1088   while (! worklist.is_empty ())
1089     {
1090       basic_block bb = worklist.pop ();
1091       DEBUG_PRINT (dp << "Visiting bb_" << bb->index << "\n");
1092
1093       /* The basic block should not be part of an irreducible loop.  */
1094       if (bb->flags & BB_IRREDUCIBLE_LOOP)
1095         return true;
1096
1097       /* Check for unstructured control flow: CFG not generated by structured
1098          if-then-else.  */
1099       if (bb->succs->length () > 1)
1100         {
1101           edge e;
1102           edge_iterator ei;
1103           FOR_EACH_EDGE (e, ei, bb->succs)
1104             if (!dominated_by_p (CDI_POST_DOMINATORS, bb, e->dest)
1105                 && !dominated_by_p (CDI_DOMINATORS, e->dest, bb))
1106               return true;
1107         }
1108
1109       /* Collect all loops in the current region.  */
1110       loop_p loop = bb->loop_father;
1111       if (loop_in_sese_p (loop, scop))
1112         bitmap_set_bit (loops, loop->num);
1113       else
1114         {
1115           /* We only check for harmful statements in basic blocks not part of
1116              any loop fully contained in the scop: other bbs are checked below
1117              in loop_is_valid_in_scop.  */
1118           if (harmful_stmt_in_bb (scop, bb))
1119             return true;
1120         }
1121
1122       if (bb != exit_bb)
1123         for (basic_block dom = first_dom_son (CDI_DOMINATORS, bb);
1124              dom;
1125              dom = next_dom_son (CDI_DOMINATORS, dom))
1126           worklist.safe_push (dom);
1127     }
1128
1129   /* Go through all loops and check that they are still valid in the combined
1130      scop.  */
1131   unsigned j;
1132   bitmap_iterator bi;
1133   EXECUTE_IF_SET_IN_BITMAP (loops, 0, j, bi)
1134     {
1135       loop_p loop = (*current_loops->larray)[j];
1136       gcc_assert (loop->num == (int) j);
1137
1138       if (!loop_is_valid_in_scop (loop, scop))
1139         return true;
1140     }
1141
1142   return false;
1143 }
1144
1145 /* Returns true if S1 subsumes/surrounds S2.  */
1146 bool
1147 scop_detection::subsumes (sese_l s1, sese_l s2)
1148 {
1149   if (dominated_by_p (CDI_DOMINATORS, get_entry_bb (s2),
1150                       get_entry_bb (s1))
1151       && dominated_by_p (CDI_POST_DOMINATORS, s2.exit->dest,
1152                          s1.exit->dest))
1153     return true;
1154   return false;
1155 }
1156
1157 /* Remove a SCoP which is subsumed by S1.  */
1158 void
1159 scop_detection::remove_subscops (sese_l s1)
1160 {
1161   int j;
1162   sese_l *s2;
1163   FOR_EACH_VEC_ELT_REVERSE (scops, j, s2)
1164     {
1165       if (subsumes (s1, *s2))
1166         {
1167           DEBUG_PRINT (dp << "Removing sub-SCoP";
1168                        print_sese (dump_file, *s2));
1169           scops.unordered_remove (j);
1170         }
1171     }
1172 }
1173
1174 /* Returns true if S1 intersects with S2.  Since we already know that S1 does
1175    not subsume S2 or vice-versa, we only check for entry bbs.  */
1176
1177 bool
1178 scop_detection::intersects (sese_l s1, sese_l s2)
1179 {
1180   if (dominated_by_p (CDI_DOMINATORS, get_entry_bb (s2),
1181                       get_entry_bb (s1))
1182       && !dominated_by_p (CDI_DOMINATORS, get_entry_bb (s2),
1183                           get_exit_bb (s1)))
1184     return true;
1185   if ((s1.exit == s2.entry) || (s2.exit == s1.entry))
1186     return true;
1187
1188   return false;
1189 }
1190
1191 /* Remove one of the scops when it intersects with any other.  */
1192
1193 void
1194 scop_detection::remove_intersecting_scops (sese_l s1)
1195 {
1196   int j;
1197   sese_l *s2;
1198   FOR_EACH_VEC_ELT_REVERSE (scops, j, s2)
1199     {
1200       if (intersects (s1, *s2))
1201         {
1202           DEBUG_PRINT (dp << "Removing intersecting SCoP";
1203                        print_sese (dump_file, *s2);
1204                        dp << "Intersects with:";
1205                        print_sese (dump_file, s1));
1206           scops.unordered_remove (j);
1207         }
1208     }
1209 }
1210
1211 /* Something like "n * m" is not allowed.  */
1212
1213 bool
1214 scop_detection::graphite_can_represent_init (tree e)
1215 {
1216   switch (TREE_CODE (e))
1217     {
1218     case POLYNOMIAL_CHREC:
1219       return graphite_can_represent_init (CHREC_LEFT (e))
1220         && graphite_can_represent_init (CHREC_RIGHT (e));
1221
1222     case MULT_EXPR:
1223       if (chrec_contains_symbols (TREE_OPERAND (e, 0)))
1224         return graphite_can_represent_init (TREE_OPERAND (e, 0))
1225           && tree_fits_shwi_p (TREE_OPERAND (e, 1));
1226       else
1227         return graphite_can_represent_init (TREE_OPERAND (e, 1))
1228           && tree_fits_shwi_p (TREE_OPERAND (e, 0));
1229
1230     case PLUS_EXPR:
1231     case POINTER_PLUS_EXPR:
1232     case MINUS_EXPR:
1233       return graphite_can_represent_init (TREE_OPERAND (e, 0))
1234         && graphite_can_represent_init (TREE_OPERAND (e, 1));
1235
1236     case NEGATE_EXPR:
1237     case BIT_NOT_EXPR:
1238     CASE_CONVERT:
1239     case NON_LVALUE_EXPR:
1240       return graphite_can_represent_init (TREE_OPERAND (e, 0));
1241
1242     default:
1243       break;
1244     }
1245
1246   return true;
1247 }
1248
1249 /* Return true when SCEV can be represented in the polyhedral model.
1250
1251    An expression can be represented, if it can be expressed as an
1252    affine expression.  For loops (i, j) and parameters (m, n) all
1253    affine expressions are of the form:
1254
1255    x1 * i + x2 * j + x3 * m + x4 * n + x5 * 1 where x1..x5 element of Z
1256
1257    1 i + 20 j + (-2) m + 25
1258
1259    Something like "i * n" or "n * m" is not allowed.  */
1260
1261 bool
1262 scop_detection::graphite_can_represent_scev (tree scev)
1263 {
1264   if (chrec_contains_undetermined (scev))
1265     return false;
1266
1267   /* We disable the handling of pointer types, because it’s currently not
1268      supported by Graphite with the isl AST generator. SSA_NAME nodes are
1269      the only nodes, which are disabled in case they are pointers to object
1270      types, but this can be changed.  */
1271
1272   if (POINTER_TYPE_P (TREE_TYPE (scev)) && TREE_CODE (scev) == SSA_NAME)
1273     return false;
1274
1275   switch (TREE_CODE (scev))
1276     {
1277     case NEGATE_EXPR:
1278     case BIT_NOT_EXPR:
1279     CASE_CONVERT:
1280     case NON_LVALUE_EXPR:
1281       return graphite_can_represent_scev (TREE_OPERAND (scev, 0));
1282
1283     case PLUS_EXPR:
1284     case POINTER_PLUS_EXPR:
1285     case MINUS_EXPR:
1286       return graphite_can_represent_scev (TREE_OPERAND (scev, 0))
1287         && graphite_can_represent_scev (TREE_OPERAND (scev, 1));
1288
1289     case MULT_EXPR:
1290       return !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev, 0)))
1291         && !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev, 1)))
1292         && !(chrec_contains_symbols (TREE_OPERAND (scev, 0))
1293              && chrec_contains_symbols (TREE_OPERAND (scev, 1)))
1294         && graphite_can_represent_init (scev)
1295         && graphite_can_represent_scev (TREE_OPERAND (scev, 0))
1296         && graphite_can_represent_scev (TREE_OPERAND (scev, 1));
1297
1298     case POLYNOMIAL_CHREC:
1299       /* Check for constant strides.  With a non constant stride of
1300          'n' we would have a value of 'iv * n'.  Also check that the
1301          initial value can represented: for example 'n * m' cannot be
1302          represented.  */
1303       if (!evolution_function_right_is_integer_cst (scev)
1304           || !graphite_can_represent_init (scev))
1305         return false;
1306       return graphite_can_represent_scev (CHREC_LEFT (scev));
1307
1308     default:
1309       break;
1310     }
1311
1312   /* Only affine functions can be represented.  */
1313   if (tree_contains_chrecs (scev, NULL) || !scev_is_linear_expression (scev))
1314     return false;
1315
1316   return true;
1317 }
1318
1319 /* Return true when EXPR can be represented in the polyhedral model.
1320
1321    This means an expression can be represented, if it is linear with respect to
1322    the loops and the strides are non parametric.  LOOP is the place where the
1323    expr will be evaluated.  SCOP defines the region we analyse.  */
1324
1325 bool
1326 scop_detection::graphite_can_represent_expr (sese_l scop, loop_p loop,
1327                                              tree expr)
1328 {
1329   tree scev = scalar_evolution_in_region (scop, loop, expr);
1330   return graphite_can_represent_scev (scev);
1331 }
1332
1333 /* Return true if the data references of STMT can be represented by Graphite.
1334    We try to analyze the data references in a loop contained in the SCOP.  */
1335
1336 bool
1337 scop_detection::stmt_has_simple_data_refs_p (sese_l scop, gimple *stmt)
1338 {
1339   loop_p nest = outermost_loop_in_sese (scop, gimple_bb (stmt));
1340   loop_p loop = loop_containing_stmt (stmt);
1341   vec<data_reference_p> drs = vNULL;
1342
1343   graphite_find_data_references_in_stmt (nest, loop, stmt, &drs);
1344
1345   int j;
1346   data_reference_p dr;
1347   FOR_EACH_VEC_ELT (drs, j, dr)
1348     {
1349       int nb_subscripts = DR_NUM_DIMENSIONS (dr);
1350
1351       if (nb_subscripts < 1)
1352         {
1353           free_data_refs (drs);
1354           return false;
1355         }
1356
1357       tree ref = DR_REF (dr);
1358
1359       for (int i = nb_subscripts - 1; i >= 0; i--)
1360         {
1361           if (!graphite_can_represent_scev (DR_ACCESS_FN (dr, i))
1362               || (TREE_CODE (ref) != ARRAY_REF && TREE_CODE (ref) != MEM_REF
1363                   && TREE_CODE (ref) != COMPONENT_REF))
1364             {
1365               free_data_refs (drs);
1366               return false;
1367             }
1368
1369           ref = TREE_OPERAND (ref, 0);
1370         }
1371     }
1372
1373     free_data_refs (drs);
1374     return true;
1375 }
1376
1377 /* GIMPLE_ASM and GIMPLE_CALL may embed arbitrary side effects.
1378    Calls have side-effects, except those to const or pure
1379    functions.  */
1380
1381 static bool
1382 stmt_has_side_effects (gimple *stmt)
1383 {
1384   if (gimple_has_volatile_ops (stmt)
1385       || (gimple_code (stmt) == GIMPLE_CALL
1386           && !(gimple_call_flags (stmt) & (ECF_CONST | ECF_PURE)))
1387       || (gimple_code (stmt) == GIMPLE_ASM))
1388     {
1389       DEBUG_PRINT (dp << "[scop-detection-fail] "
1390                       << "Statement has side-effects:\n";
1391         print_gimple_stmt (dump_file, stmt, 0, TDF_VOPS | TDF_MEMSYMS));
1392       return true;
1393     }
1394   return false;
1395 }
1396
1397 /* Returns true if STMT can be represented in polyhedral model. LABEL,
1398    simple COND stmts, pure calls, and assignments can be repesented.  */
1399
1400 bool
1401 scop_detection::graphite_can_represent_stmt (sese_l scop, gimple *stmt,
1402                                              basic_block bb)
1403 {
1404   loop_p loop = bb->loop_father;
1405   switch (gimple_code (stmt))
1406     {
1407     case GIMPLE_LABEL:
1408       return true;
1409
1410     case GIMPLE_COND:
1411       {
1412         /* We can handle all binary comparisons.  Inequalities are
1413            also supported as they can be represented with union of
1414            polyhedra.  */
1415         enum tree_code code = gimple_cond_code (stmt);
1416         if (!(code == LT_EXPR
1417               || code == GT_EXPR
1418               || code == LE_EXPR
1419               || code == GE_EXPR
1420               || code == EQ_EXPR
1421               || code == NE_EXPR))
1422           {
1423             DEBUG_PRINT (dp << "[scop-detection-fail] "
1424                             << "Graphite cannot handle cond stmt:\n";
1425                          print_gimple_stmt (dump_file, stmt, 0,
1426                                             TDF_VOPS | TDF_MEMSYMS));
1427             return false;
1428           }
1429
1430         for (unsigned i = 0; i < 2; ++i)
1431           {
1432             tree op = gimple_op (stmt, i);
1433             if (!graphite_can_represent_expr (scop, loop, op)
1434                 /* We can only constrain on integer type.  */
1435                 || (TREE_CODE (TREE_TYPE (op)) != INTEGER_TYPE))
1436               {
1437                 DEBUG_PRINT (dp << "[scop-detection-fail] "
1438                                 << "Graphite cannot represent stmt:\n";
1439                              print_gimple_stmt (dump_file, stmt, 0,
1440                                                 TDF_VOPS | TDF_MEMSYMS));
1441                 return false;
1442               }
1443           }
1444
1445         return true;
1446       }
1447
1448     case GIMPLE_ASSIGN:
1449     case GIMPLE_CALL:
1450       return true;
1451
1452     default:
1453       /* These nodes cut a new scope.  */
1454       DEBUG_PRINT (
1455           dp << "[scop-detection-fail] "
1456              << "Gimple stmt not handled in Graphite:\n";
1457           print_gimple_stmt (dump_file, stmt, 0, TDF_VOPS | TDF_MEMSYMS));
1458       return false;
1459     }
1460 }
1461
1462 /* Return true only when STMT is simple enough for being handled by Graphite.
1463    This depends on SCOP, as the parameters are initialized relatively to
1464    this basic block, the linear functions are initialized based on the outermost
1465    loop containing STMT inside the SCOP.  BB is the place where we try to
1466    evaluate the STMT.  */
1467
1468 bool
1469 scop_detection::stmt_simple_for_scop_p (sese_l scop, gimple *stmt,
1470                                         basic_block bb) const
1471 {
1472   gcc_assert (scop);
1473
1474   if (is_gimple_debug (stmt))
1475     return true;
1476
1477   if (stmt_has_side_effects (stmt))
1478     return false;
1479
1480   if (!stmt_has_simple_data_refs_p (scop, stmt))
1481     {
1482       DEBUG_PRINT (dp << "[scop-detection-fail] "
1483                       << "Graphite cannot handle data-refs in stmt:\n";
1484         print_gimple_stmt (dump_file, stmt, 0, TDF_VOPS|TDF_MEMSYMS););
1485       return false;
1486     }
1487
1488   return graphite_can_represent_stmt (scop, stmt, bb);
1489 }
1490
1491 /* Return true when BB contains a harmful operation for a scop: that
1492    can be a function call with side effects, the induction variables
1493    are not linear with respect to SCOP, etc.  The current open
1494    scop should end before this statement.  */
1495
1496 bool
1497 scop_detection::harmful_stmt_in_bb (sese_l scop, basic_block bb) const
1498 {
1499   gimple_stmt_iterator gsi;
1500
1501   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1502     if (!stmt_simple_for_scop_p (scop, gsi_stmt (gsi), bb))
1503       return true;
1504
1505   return false;
1506 }
1507
1508 /* Return true when the body of LOOP has statements that can be represented as a
1509    valid scop.  */
1510
1511 bool
1512 scop_detection::loop_body_is_valid_scop (loop_p loop, sese_l scop) const
1513 {
1514   if (!loop_ivs_can_be_represented (loop))
1515     {
1516       DEBUG_PRINT (dp << "[scop-detection-fail] loop_" << loop->num
1517                       << "IV cannot be represented.\n");
1518       return false;
1519     }
1520
1521   if (!loop_nest_has_data_refs (loop))
1522     {
1523       DEBUG_PRINT (dp << "[scop-detection-fail] loop_" << loop->num
1524                       << "does not have any data reference.\n");
1525       return false;
1526     }
1527
1528   basic_block *bbs = get_loop_body (loop);
1529   for (unsigned i = 0; i < loop->num_nodes; i++)
1530     {
1531       basic_block bb = bbs[i];
1532
1533       if (harmful_stmt_in_bb (scop, bb))
1534         {
1535           free (bbs);
1536           return false;
1537         }
1538     }
1539   free (bbs);
1540
1541   if (loop->inner)
1542     {
1543       loop = loop->inner;
1544       while (loop)
1545         {
1546           if (!loop_body_is_valid_scop (loop, scop))
1547             return false;
1548           loop = loop->next;
1549         }
1550     }
1551
1552   return true;
1553 }
1554
1555 /* Returns the number of pbbs that are in loops contained in SCOP.  */
1556
1557 int
1558 scop_detection::nb_pbbs_in_loops (scop_p scop)
1559 {
1560   int i;
1561   poly_bb_p pbb;
1562   int res = 0;
1563
1564   FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
1565     if (loop_in_sese_p (gbb_loop (PBB_BLACK_BOX (pbb)), scop->scop_info->region))
1566       res++;
1567
1568   return res;
1569 }
1570
1571 /* When parameter NAME is in REGION, returns its index in SESE_PARAMS.
1572    Otherwise returns -1.  */
1573
1574 static inline int
1575 parameter_index_in_region_1 (tree name, sese_info_p region)
1576 {
1577   int i;
1578   tree p;
1579
1580   gcc_assert (TREE_CODE (name) == SSA_NAME);
1581
1582   FOR_EACH_VEC_ELT (region->params, i, p)
1583     if (p == name)
1584       return i;
1585
1586   return -1;
1587 }
1588
1589 /* When the parameter NAME is in REGION, returns its index in
1590    SESE_PARAMS.  Otherwise this function inserts NAME in SESE_PARAMS
1591    and returns the index of NAME.  */
1592
1593 static int
1594 parameter_index_in_region (tree name, sese_info_p region)
1595 {
1596   int i;
1597
1598   gcc_assert (TREE_CODE (name) == SSA_NAME);
1599
1600   /* Cannot constrain on anything else than INTEGER_TYPE parameters.  */
1601   if (TREE_CODE (TREE_TYPE (name)) != INTEGER_TYPE)
1602     return -1;
1603
1604   if (!invariant_in_sese_p_rec (name, region->region, NULL))
1605     return -1;
1606
1607   i = parameter_index_in_region_1 (name, region);
1608   if (i != -1)
1609     return i;
1610
1611   i = region->params.length ();
1612   region->params.safe_push (name);
1613   return i;
1614 }
1615
1616 /* In the context of sese S, scan the expression E and translate it to
1617    a linear expression C.  When parsing a symbolic multiplication, K
1618    represents the constant multiplier of an expression containing
1619    parameters.  */
1620
1621 static void
1622 scan_tree_for_params (sese_info_p s, tree e)
1623 {
1624   if (e == chrec_dont_know)
1625     return;
1626
1627   switch (TREE_CODE (e))
1628     {
1629     case POLYNOMIAL_CHREC:
1630       scan_tree_for_params (s, CHREC_LEFT (e));
1631       break;
1632
1633     case MULT_EXPR:
1634       if (chrec_contains_symbols (TREE_OPERAND (e, 0)))
1635         scan_tree_for_params (s, TREE_OPERAND (e, 0));
1636       else
1637         scan_tree_for_params (s, TREE_OPERAND (e, 1));
1638       break;
1639
1640     case PLUS_EXPR:
1641     case POINTER_PLUS_EXPR:
1642     case MINUS_EXPR:
1643       scan_tree_for_params (s, TREE_OPERAND (e, 0));
1644       scan_tree_for_params (s, TREE_OPERAND (e, 1));
1645       break;
1646
1647     case NEGATE_EXPR:
1648     case BIT_NOT_EXPR:
1649     CASE_CONVERT:
1650     case NON_LVALUE_EXPR:
1651       scan_tree_for_params (s, TREE_OPERAND (e, 0));
1652       break;
1653
1654     case SSA_NAME:
1655       parameter_index_in_region (e, s);
1656       break;
1657
1658     case INTEGER_CST:
1659     case ADDR_EXPR:
1660     case REAL_CST:
1661     case COMPLEX_CST:
1662     case VECTOR_CST:
1663       break;
1664
1665    default:
1666       gcc_unreachable ();
1667       break;
1668     }
1669 }
1670
1671 /* Find parameters with respect to REGION in BB. We are looking in memory
1672    access functions, conditions and loop bounds.  */
1673
1674 static void
1675 find_params_in_bb (sese_info_p region, gimple_poly_bb_p gbb)
1676 {
1677   /* Find parameters in the access functions of data references.  */
1678   int i;
1679   data_reference_p dr;
1680   FOR_EACH_VEC_ELT (GBB_DATA_REFS (gbb), i, dr)
1681     for (unsigned j = 0; j < DR_NUM_DIMENSIONS (dr); j++)
1682       scan_tree_for_params (region, DR_ACCESS_FN (dr, j));
1683
1684   /* Find parameters in conditional statements.  */
1685   gimple *stmt;
1686   loop_p loop = GBB_BB (gbb)->loop_father;
1687   FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb), i, stmt)
1688     {
1689       tree lhs = scalar_evolution_in_region (region->region, loop,
1690                                              gimple_cond_lhs (stmt));
1691       tree rhs = scalar_evolution_in_region (region->region, loop,
1692                                              gimple_cond_rhs (stmt));
1693
1694       scan_tree_for_params (region, lhs);
1695       scan_tree_for_params (region, rhs);
1696     }
1697 }
1698
1699 /* Record the parameters used in the SCOP.  A variable is a parameter
1700    in a scop if it does not vary during the execution of that scop.  */
1701
1702 static void
1703 find_scop_parameters (scop_p scop)
1704 {
1705   unsigned i;
1706   sese_info_p region = scop->scop_info;
1707   struct loop *loop;
1708
1709   /* Find the parameters used in the loop bounds.  */
1710   FOR_EACH_VEC_ELT (region->loop_nest, i, loop)
1711     {
1712       tree nb_iters = number_of_latch_executions (loop);
1713
1714       if (!chrec_contains_symbols (nb_iters))
1715         continue;
1716
1717       nb_iters = scalar_evolution_in_region (region->region, loop, nb_iters);
1718       scan_tree_for_params (region, nb_iters);
1719     }
1720
1721   /* Find the parameters used in data accesses.  */
1722   poly_bb_p pbb;
1723   FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
1724     find_params_in_bb (region, PBB_BLACK_BOX (pbb));
1725
1726   int nbp = sese_nb_params (region);
1727   scop_set_nb_params (scop, nbp);
1728 }
1729
1730 /* Record DEF if it is used in other bbs different than DEF_BB in the SCOP.  */
1731
1732 static void
1733 build_cross_bb_scalars_def (scop_p scop, tree def, basic_block def_bb,
1734                              vec<tree> *writes)
1735 {
1736   if (!def || !is_gimple_reg (def))
1737     return;
1738
1739   /* Do not gather scalar variables that can be analyzed by SCEV as they can be
1740      generated out of the induction variables.  */
1741   if (scev_analyzable_p (def, scop->scop_info->region))
1742     return;
1743
1744   gimple *use_stmt;
1745   imm_use_iterator imm_iter;
1746   FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def)
1747     if (def_bb != gimple_bb (use_stmt) && !is_gimple_debug (use_stmt))
1748       {
1749         writes->safe_push (def);
1750         DEBUG_PRINT (dp << "Adding scalar write: ";
1751                      print_generic_expr (dump_file, def);
1752                      dp << "\nFrom stmt: ";
1753                      print_gimple_stmt (dump_file,
1754                                         SSA_NAME_DEF_STMT (def), 0));
1755         /* This is required by the FOR_EACH_IMM_USE_STMT when we want to break
1756            before all the uses have been visited.  */
1757         BREAK_FROM_IMM_USE_STMT (imm_iter);
1758       }
1759 }
1760
1761 /* Record DEF if it is used in other bbs different than DEF_BB in the SCOP.  */
1762
1763 static void
1764 build_cross_bb_scalars_use (scop_p scop, tree use, gimple *use_stmt,
1765                             vec<scalar_use> *reads)
1766 {
1767   gcc_assert (use);
1768   if (!is_gimple_reg (use))
1769     return;
1770
1771   /* Do not gather scalar variables that can be analyzed by SCEV as they can be
1772      generated out of the induction variables.  */
1773   if (scev_analyzable_p (use, scop->scop_info->region))
1774     return;
1775
1776   gimple *def_stmt = SSA_NAME_DEF_STMT (use);
1777   if (gimple_bb (def_stmt) != gimple_bb (use_stmt))
1778     {
1779       DEBUG_PRINT (dp << "Adding scalar read: ";
1780                    print_generic_expr (dump_file, use);
1781                    dp << "\nFrom stmt: ";
1782                    print_gimple_stmt (dump_file, use_stmt, 0));
1783       reads->safe_push (std::make_pair (use_stmt, use));
1784     }
1785 }
1786
1787 /* Record all scalar variables that are defined and used in different BBs of the
1788    SCOP.  */
1789
1790 static void
1791 graphite_find_cross_bb_scalar_vars (scop_p scop, gimple *stmt,
1792                                     vec<scalar_use> *reads, vec<tree> *writes)
1793 {
1794   tree def;
1795
1796   if (gimple_code (stmt) == GIMPLE_ASSIGN)
1797     def = gimple_assign_lhs (stmt);
1798   else if (gimple_code (stmt) == GIMPLE_CALL)
1799     def = gimple_call_lhs (stmt);
1800   else if (gimple_code (stmt) == GIMPLE_PHI)
1801     def = gimple_phi_result (stmt);
1802   else
1803     return;
1804
1805
1806   build_cross_bb_scalars_def (scop, def, gimple_bb (stmt), writes);
1807
1808   ssa_op_iter iter;
1809   use_operand_p use_p;
1810   FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE)
1811     {
1812       tree use = USE_FROM_PTR (use_p);
1813       build_cross_bb_scalars_use (scop, use, stmt, reads);
1814     }
1815 }
1816
1817 /* Generates a polyhedral black box only if the bb contains interesting
1818    information.  */
1819
1820 static gimple_poly_bb_p
1821 try_generate_gimple_bb (scop_p scop, basic_block bb)
1822 {
1823   vec<data_reference_p> drs = vNULL;
1824   vec<tree> writes = vNULL;
1825   vec<scalar_use> reads = vNULL;
1826
1827   sese_l region = scop->scop_info->region;
1828   loop_p nest = outermost_loop_in_sese (region, bb);
1829
1830   loop_p loop = bb->loop_father;
1831   if (!loop_in_sese_p (loop, region))
1832     loop = nest;
1833
1834   for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
1835        gsi_next (&gsi))
1836     {
1837       gimple *stmt = gsi_stmt (gsi);
1838       if (is_gimple_debug (stmt))
1839         continue;
1840
1841       graphite_find_data_references_in_stmt (nest, loop, stmt, &drs);
1842       graphite_find_cross_bb_scalar_vars (scop, stmt, &reads, &writes);
1843     }
1844
1845   for (gphi_iterator psi = gsi_start_phis (bb); !gsi_end_p (psi);
1846        gsi_next (&psi))
1847     if (!virtual_operand_p (gimple_phi_result (psi.phi ())))
1848       graphite_find_cross_bb_scalar_vars (scop, psi.phi (), &reads, &writes);
1849
1850   if (drs.is_empty () && writes.is_empty () && reads.is_empty ())
1851     return NULL;
1852
1853   return new_gimple_poly_bb (bb, drs, reads, writes);
1854 }
1855
1856 /* Compute alias-sets for all data references in DRS.  */
1857
1858 static void
1859 build_alias_set (scop_p scop)
1860 {
1861   int num_vertices = scop->drs.length ();
1862   struct graph *g = new_graph (num_vertices);
1863   dr_info *dr1, *dr2;
1864   int i, j;
1865   int *all_vertices;
1866
1867   FOR_EACH_VEC_ELT (scop->drs, i, dr1)
1868     for (j = i+1; scop->drs.iterate (j, &dr2); j++)
1869       if (dr_may_alias_p (dr1->dr, dr2->dr, true))
1870         {
1871           add_edge (g, i, j);
1872           add_edge (g, j, i);
1873         }
1874
1875   all_vertices = XNEWVEC (int, num_vertices);
1876   for (i = 0; i < num_vertices; i++)
1877     all_vertices[i] = i;
1878
1879   graphds_dfs (g, all_vertices, num_vertices, NULL, true, NULL);
1880   free (all_vertices);
1881
1882   for (i = 0; i < g->n_vertices; i++)
1883     scop->drs[i].alias_set = g->vertices[i].component + 1;
1884
1885   free_graph (g);
1886 }
1887
1888 /* Gather BBs and conditions for a SCOP.  */
1889 class gather_bbs : public dom_walker
1890 {
1891 public:
1892   gather_bbs (cdi_direction, scop_p);
1893
1894   virtual edge before_dom_children (basic_block);
1895   virtual void after_dom_children (basic_block);
1896
1897 private:
1898   auto_vec<gimple *, 3> conditions, cases;
1899   scop_p scop;
1900 };
1901 }
1902 gather_bbs::gather_bbs (cdi_direction direction, scop_p scop)
1903   : dom_walker (direction), scop (scop)
1904 {
1905 }
1906
1907 /* Record in execution order the loops fully contained in the region.  */
1908
1909 static void
1910 record_loop_in_sese (basic_block bb, sese_info_p region)
1911 {
1912   loop_p father = bb->loop_father;
1913   if (loop_in_sese_p (father, region->region))
1914     {
1915       bool found = false;
1916       loop_p loop0;
1917       int j;
1918       FOR_EACH_VEC_ELT (region->loop_nest, j, loop0)
1919         if (father == loop0)
1920           {
1921             found = true;
1922             break;
1923           }
1924       if (!found)
1925         region->loop_nest.safe_push (father);
1926     }
1927 }
1928
1929 /* Call-back for dom_walk executed before visiting the dominated
1930    blocks.  */
1931
1932 edge
1933 gather_bbs::before_dom_children (basic_block bb)
1934 {
1935   sese_info_p region = scop->scop_info;
1936   if (!bb_in_sese_p (bb, region->region))
1937     return NULL;
1938
1939   record_loop_in_sese (bb, region);
1940
1941   gcond *stmt = single_pred_cond_non_loop_exit (bb);
1942
1943   if (stmt)
1944     {
1945       edge e = single_pred_edge (bb);
1946
1947       conditions.safe_push (stmt);
1948
1949       if (e->flags & EDGE_TRUE_VALUE)
1950         cases.safe_push (stmt);
1951       else
1952         cases.safe_push (NULL);
1953     }
1954
1955   scop->scop_info->bbs.safe_push (bb);
1956
1957   gimple_poly_bb_p gbb = try_generate_gimple_bb (scop, bb);
1958   if (!gbb)
1959     return NULL;
1960
1961   GBB_CONDITIONS (gbb) = conditions.copy ();
1962   GBB_CONDITION_CASES (gbb) = cases.copy ();
1963
1964   poly_bb_p pbb = new_poly_bb (scop, gbb);
1965   scop->pbbs.safe_push (pbb);
1966
1967   int i;
1968   data_reference_p dr;
1969   FOR_EACH_VEC_ELT (gbb->data_refs, i, dr)
1970     {
1971       DEBUG_PRINT (dp << "Adding memory ";
1972                    if (dr->is_read)
1973                      dp << "read: ";
1974                    else
1975                      dp << "write: ";
1976                    print_generic_expr (dump_file, dr->ref);
1977                    dp << "\nFrom stmt: ";
1978                    print_gimple_stmt (dump_file, dr->stmt, 0));
1979
1980       scop->drs.safe_push (dr_info (dr, pbb));
1981     }
1982
1983   return NULL;
1984 }
1985
1986 /* Call-back for dom_walk executed after visiting the dominated
1987    blocks.  */
1988
1989 void
1990 gather_bbs::after_dom_children (basic_block bb)
1991 {
1992   if (!bb_in_sese_p (bb, scop->scop_info->region))
1993     return;
1994
1995   if (single_pred_cond_non_loop_exit (bb))
1996     {
1997       conditions.pop ();
1998       cases.pop ();
1999     }
2000 }
2001
2002
2003 /* Compute sth like an execution order, dominator order with first executing
2004    edges that stay inside the current loop, delaying processing exit edges.  */
2005
2006 static vec<unsigned> order;
2007
2008 static void
2009 get_order (scop_p scop, basic_block bb, vec<unsigned> *order, unsigned *dfs_num)
2010 {
2011   if (! bb_in_sese_p (bb, scop->scop_info->region))
2012     return;
2013
2014   (*order)[bb->index] = (*dfs_num)++;
2015   for (basic_block son = first_dom_son (CDI_DOMINATORS, bb);
2016        son;
2017        son = next_dom_son (CDI_DOMINATORS, son))
2018     if (flow_bb_inside_loop_p (bb->loop_father, son))
2019       get_order (scop, son, order, dfs_num);
2020   for (basic_block son = first_dom_son (CDI_DOMINATORS, bb);
2021        son;
2022        son = next_dom_son (CDI_DOMINATORS, son))
2023     if (! flow_bb_inside_loop_p (bb->loop_father, son))
2024       get_order (scop, son, order, dfs_num);
2025 }
2026
2027 /* Helper for qsort, sorting after order above.  */
2028
2029 static int
2030 cmp_pbbs (const void *pa, const void *pb)
2031 {
2032   poly_bb_p bb1 = *((const poly_bb_p *)pa);
2033   poly_bb_p bb2 = *((const poly_bb_p *)pb);
2034   if (order[bb1->black_box->bb->index] < order[bb2->black_box->bb->index])
2035     return -1;
2036   else if (order[bb1->black_box->bb->index] > order[bb2->black_box->bb->index])
2037     return 1;
2038   else
2039     return 0;
2040 }
2041
2042 /* Find Static Control Parts (SCoP) in the current function and pushes
2043    them to SCOPS.  */
2044
2045 void
2046 build_scops (vec<scop_p> *scops)
2047 {
2048   if (dump_file)
2049     dp.set_dump_file (dump_file);
2050
2051   canonicalize_loop_closed_ssa_form ();
2052
2053   scop_detection sb;
2054   sb.build_scop_depth (scop_detection::invalid_sese, current_loops->tree_root);
2055
2056   /* Now create scops from the lightweight SESEs.  */
2057   vec<sese_l> scops_l = sb.get_scops ();
2058   int i;
2059   sese_l *s;
2060   FOR_EACH_VEC_ELT (scops_l, i, s)
2061     {
2062       scop_p scop = new_scop (s->entry, s->exit);
2063
2064       /* Record all basic blocks and their conditions in REGION.  */
2065       gather_bbs (CDI_DOMINATORS, scop).walk (s->entry->dest);
2066
2067       /* domwalk does not fulfil our code-generations constraints on the
2068          order of pbb which is to produce sth like execution order, delaying
2069          exection of loop exit edges.  So compute such order and sort after
2070          that.  */
2071       order.create (last_basic_block_for_fn (cfun));
2072       order.quick_grow (last_basic_block_for_fn (cfun));
2073       unsigned dfs_num = 0;
2074       get_order (scop, s->entry->dest, &order, &dfs_num);
2075       scop->pbbs.qsort (cmp_pbbs);
2076       order.release ();
2077
2078       build_alias_set (scop);
2079
2080       /* Do not optimize a scop containing only PBBs that do not belong
2081          to any loops.  */
2082       if (sb.nb_pbbs_in_loops (scop) == 0)
2083         {
2084           DEBUG_PRINT (dp << "[scop-detection-fail] no data references.\n");
2085           free_scop (scop);
2086           continue;
2087         }
2088
2089       unsigned max_arrays = PARAM_VALUE (PARAM_GRAPHITE_MAX_ARRAYS_PER_SCOP);
2090       if (scop->drs.length () >= max_arrays)
2091         {
2092           DEBUG_PRINT (dp << "[scop-detection-fail] too many data references: "
2093                        << scop->drs.length ()
2094                        << " is larger than --param graphite-max-arrays-per-scop="
2095                        << max_arrays << ".\n");
2096           free_scop (scop);
2097           continue;
2098         }
2099
2100       find_scop_parameters (scop);
2101       graphite_dim_t max_dim = PARAM_VALUE (PARAM_GRAPHITE_MAX_NB_SCOP_PARAMS);
2102
2103       if (scop_nb_params (scop) > max_dim)
2104         {
2105           DEBUG_PRINT (dp << "[scop-detection-fail] too many parameters: "
2106                           << scop_nb_params (scop)
2107                           << " larger than --param graphite-max-nb-scop-params="
2108                           << max_dim << ".\n");
2109           free_scop (scop);
2110           continue;
2111         }
2112
2113       scops->safe_push (scop);
2114     }
2115
2116   DEBUG_PRINT (dp << "number of SCoPs: " << (scops ? scops->length () : 0););
2117 }
2118
2119 #endif /* HAVE_isl */