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 (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 want to bail out when exit does not post-dominate entry.
 821      TODO: We might just add a basic_block at the exit to make exit
 822      post-dominate entry (the entire region).  */
 823   if (!dominated_by_p (CDI_POST_DOMINATORS, get_entry_bb (combined),
 824                        get_exit_bb (combined))
 825       || !dominated_by_p (CDI_DOMINATORS, get_exit_bb (combined),
 826                           get_entry_bb (combined)))
 827     {
 828       DEBUG_PRINT (dp << "[scop-detection-fail] cannot merge seses.\n");
 829       return invalid_sese;
 830     }
 831
 832   /* FIXME: We should remove this piece of code once
 833      canonicalize_loop_closed_ssa has been removed, because that function
 834      adds a BB with single exit.  */
 835   if (!trivially_empty_bb_p (get_exit_bb (combined)))
 836     {
 837       /* Find the first empty succ (with single exit) of combined.exit.  */
 838       basic_block imm_succ = combined.exit->dest;
 839       if (single_succ_p (imm_succ)
 840           && single_pred_p (imm_succ)
 841           && trivially_empty_bb_p (imm_succ))
 842         combined.exit = single_succ_edge (imm_succ);
 843       else
 844         {
 845           DEBUG_PRINT (dp << "[scop-detection-fail] Discarding SCoP because "
 846                           << "no single exit (empty succ) for sese exit";
 847                        print_sese (dump_file, combined));
 848           return invalid_sese;
 849         }
 850     }
 851
 852   /* Analyze all the BBs in new sese.  */
 853   if (harmful_loop_in_region (combined))
 854     return invalid_sese;
 855
 856   DEBUG_PRINT (dp << "[merged-sese] s1: "; print_sese (dump_file, combined));
 857
 858   return combined;
 859 }
 860
 861 /* Build scop outer->inner if possible.  */
 862
 863 sese_l
 864 scop_detection::build_scop_depth (sese_l s, loop_p loop)
 865 {
 866   if (!loop)
 867     return s;
 868
 869   DEBUG_PRINT (dp << "[Depth loop_" << loop->num << "]\n");
 870   s = build_scop_depth (s, loop->inner);
 871
 872   sese_l s2 = merge_sese (s, get_sese (loop));
 873   if (!s2)
 874     {
 875       /* s might be a valid scop, so return it and start analyzing from the
 876          adjacent loop.  */
 877       build_scop_depth (invalid_sese, loop->next);
 878       return s;
 879     }
 880
 881   if (!loop_is_valid_in_scop (loop, s2))
 882     return build_scop_depth (invalid_sese, loop->next);
 883
 884   return build_scop_breadth (s2, loop);
 885 }
 886
 887 /* If loop and loop->next are valid scops, try to merge them.  */
 888
 889 sese_l
 890 scop_detection::build_scop_breadth (sese_l s1, loop_p loop)
 891 {
 892   if (!loop)
 893     return s1;
 894   DEBUG_PRINT (dp << "[Breadth loop_" << loop->num << "]\n");
 895   gcc_assert (s1);
 896
 897   loop_p l = loop;
 898   sese_l s2 = build_scop_depth (invalid_sese, l->next);
 899   if (!s2)
 900     {
 901       if (s1)
 902         add_scop (s1);
 903       return s1;
 904     }
 905
 906   sese_l combined = merge_sese (s1, s2);
 907
 908   if (combined)
 909     s1 = combined;
 910   else
 911     add_scop (s2);
 912
 913   if (s1)
 914     add_scop (s1);
 915   return s1;
 916 }
 917
 918 /* Returns true when Graphite can represent LOOP in SCOP.
 919    FIXME: For the moment, graphite cannot be used on loops that iterate using
 920    induction variables that wrap.  */
 921
 922 bool
 923 scop_detection::can_represent_loop_1 (loop_p loop, sese_l scop)
 924 {
 925   tree niter;
 926   struct tree_niter_desc niter_desc;
 927
 928   return single_exit (loop)
 929     && !(loop_preheader_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP)
 930     && number_of_iterations_exit (loop, single_exit (loop), &niter_desc, false)
 931     && niter_desc.control.no_overflow
 932     && (niter = number_of_latch_executions (loop))
 933     && !chrec_contains_undetermined (niter)
 934     && graphite_can_represent_expr (scop, loop, niter);
 935 }
 936
 937 /* Return true when all the loops within LOOP can be represented by
 938    Graphite.  */
 939
 940 bool
 941 scop_detection::can_represent_loop (loop_p loop, sese_l scop)
 942 {
 943   if (!can_represent_loop_1 (loop, scop))
 944     return false;
 945   if (loop->inner && !can_represent_loop (loop->inner, scop))
 946     return false;
 947   if (loop->next && !can_represent_loop (loop->next, scop))
 948     return false;
 949
 950   return true;
 951 }
 952
 953 /* Return true when LOOP is a valid scop, that is a Static Control Part, a
 954    region of code that can be represented in the polyhedral model.  SCOP
 955    defines the region we analyse.  */
 956
 957 bool
 958 scop_detection::loop_is_valid_in_scop (loop_p loop, sese_l scop) const
 959 {
 960   if (!scop)
 961     return false;
 962
 963   if (!optimize_loop_nest_for_speed_p (loop))
 964     {
 965       DEBUG_PRINT (dp << "[scop-detection-fail] loop_"
 966                       << loop->num << " is not on a hot path.\n");
 967       return false;
 968     }
 969
 970   if (!can_represent_loop (loop, scop))
 971     {
 972       DEBUG_PRINT (dp << "[scop-detection-fail] cannot represent loop_"
 973                       << loop->num << "\n");
 974       return false;
 975     }
 976
 977   if (loop_body_is_valid_scop (loop, scop))
 978     {
 979       DEBUG_PRINT (dp << "[valid-scop] loop_" << loop->num
 980                       << " is a valid scop.\n");
 981       return true;
 982     }
 983   return false;
 984 }
 985
 986 /* Return true when BEGIN is the preheader edge of a loop with a single exit
 987    END.  */
 988
 989 bool
 990 scop_detection::region_has_one_loop (sese_l s)
 991 {
 992   edge begin = s.entry;
 993   edge end = s.exit;
 994   /* Check for a single perfectly nested loop.  */
 995   if (begin->dest->loop_father->inner)
 996     return false;
 997
 998   /* Otherwise, check whether we have adjacent loops.  */
 999   return begin->dest->loop_father == end->src->loop_father;
1000 }
1001
1002 /* Add to SCOPS a scop starting at SCOP_BEGIN and ending at SCOP_END.  */
1003
1004 void
1005 scop_detection::add_scop (sese_l s)
1006 {
1007   gcc_assert (s);
1008
1009   /* Do not add scops with only one loop.  */
1010   if (region_has_one_loop (s))
1011     {
1012       DEBUG_PRINT (dp << "[scop-detection-fail] Discarding one loop SCoP: ";
1013                    print_sese (dump_file, s));
1014       return;
1015     }
1016
1017   if (get_exit_bb (s) == EXIT_BLOCK_PTR_FOR_FN (cfun))
1018     {
1019       DEBUG_PRINT (dp << "[scop-detection-fail] "
1020                       << "Discarding SCoP exiting to return: ";
1021                    print_sese (dump_file, s));
1022       return;
1023     }
1024
1025   /* Remove all the scops which are subsumed by s.  */
1026   remove_subscops (s);
1027
1028   /* Remove intersecting scops. FIXME: It will be a good idea to keep
1029      the non-intersecting part of the scop already in the list.  */
1030   remove_intersecting_scops (s);
1031
1032   scops.safe_push (s);
1033   DEBUG_PRINT (dp << "[scop-detection] Adding SCoP: "; print_sese (dump_file, s));
1034 }
1035
1036 /* Return true when a statement in SCOP cannot be represented by Graphite.
1037    The assumptions are that L1 dominates L2, and SCOP->entry dominates L1.
1038    Limit the number of bbs between adjacent loops to
1039    PARAM_SCOP_MAX_NUM_BBS_BETWEEN_LOOPS.  */
1040
1041 bool
1042 scop_detection::harmful_loop_in_region (sese_l scop) const
1043 {
1044   basic_block exit_bb = get_exit_bb (scop);
1045   basic_block entry_bb = get_entry_bb (scop);
1046
1047   DEBUG_PRINT (dp << "[checking-harmful-bbs] ";
1048                print_sese (dump_file, scop));
1049   gcc_assert (dominated_by_p (CDI_DOMINATORS, exit_bb, entry_bb));
1050
1051   int depth = bb_dom_dfs_in (CDI_DOMINATORS, exit_bb)
1052     - bb_dom_dfs_in (CDI_DOMINATORS, entry_bb);
1053
1054   gcc_assert (depth > 0);
1055
1056   vec<basic_block> dom
1057       = get_dominated_to_depth (CDI_DOMINATORS, entry_bb, depth);
1058   int i;
1059   basic_block bb;
1060   bitmap loops = BITMAP_ALLOC (NULL);
1061   FOR_EACH_VEC_ELT (dom, i, bb)
1062     {
1063       DEBUG_PRINT (dp << "Visiting bb_" << bb->index << "\n");
1064
1065       /* We don't want to analyze any bb outside sese.  */
1066       if (!dominated_by_p (CDI_POST_DOMINATORS, bb, exit_bb))
1067         continue;
1068
1069       /* Basic blocks dominated by the scop->exit are not in the scop.  */
1070       if (bb != exit_bb && dominated_by_p (CDI_DOMINATORS, bb, exit_bb))
1071         continue;
1072
1073       /* The basic block should not be part of an irreducible loop.  */
1074       if (bb->flags & BB_IRREDUCIBLE_LOOP)
1075         {
1076           dom.release ();
1077           BITMAP_FREE (loops);
1078           return true;
1079         }
1080
1081       /* Check for unstructured control flow: CFG not generated by structured
1082          if-then-else.  */
1083       if (bb->succs->length () > 1)
1084         {
1085           edge e;
1086           edge_iterator ei;
1087           FOR_EACH_EDGE (e, ei, bb->succs)
1088             if (!dominated_by_p (CDI_POST_DOMINATORS, bb, e->dest)
1089                 && !dominated_by_p (CDI_DOMINATORS, e->dest, bb))
1090               return true;
1091         }
1092
1093       /* Collect all loops in the current region.  */
1094       loop_p loop = bb->loop_father;
1095       if (loop_in_sese_p (loop, scop))
1096         bitmap_set_bit (loops, loop->num);
1097       else
1098         {
1099           /* We only check for harmful statements in basic blocks not part of
1100              any loop fully contained in the scop: other bbs are checked below
1101              in loop_is_valid_in_scop.  */
1102           if (harmful_stmt_in_bb (scop, bb))
1103             {
1104               dom.release ();
1105               BITMAP_FREE (loops);
1106               return true;
1107             }
1108         }
1109
1110     }
1111
1112   /* Go through all loops and check that they are still valid in the combined
1113      scop.  */
1114   unsigned j;
1115   bitmap_iterator bi;
1116   EXECUTE_IF_SET_IN_BITMAP (loops, 0, j, bi)
1117     {
1118       loop_p loop = (*current_loops->larray)[j];
1119       gcc_assert (loop->num == (int) j);
1120
1121       if (!loop_is_valid_in_scop (loop, scop))
1122         {
1123           dom.release ();
1124           BITMAP_FREE (loops);
1125           return true;
1126         }
1127     }
1128
1129   dom.release ();
1130   BITMAP_FREE (loops);
1131   return false;
1132 }
1133
1134 /* Returns true if S1 subsumes/surrounds S2.  */
1135 bool
1136 scop_detection::subsumes (sese_l s1, sese_l s2)
1137 {
1138   if (dominated_by_p (CDI_DOMINATORS, get_entry_bb (s2),
1139                       get_entry_bb (s1))
1140       && dominated_by_p (CDI_POST_DOMINATORS, s2.exit->dest,
1141                          s1.exit->dest))
1142     return true;
1143   return false;
1144 }
1145
1146 /* Remove a SCoP which is subsumed by S1.  */
1147 void
1148 scop_detection::remove_subscops (sese_l s1)
1149 {
1150   int j;
1151   sese_l *s2;
1152   FOR_EACH_VEC_ELT_REVERSE (scops, j, s2)
1153     {
1154       if (subsumes (s1, *s2))
1155         {
1156           DEBUG_PRINT (dp << "Removing sub-SCoP";
1157                        print_sese (dump_file, *s2));
1158           scops.unordered_remove (j);
1159         }
1160     }
1161 }
1162
1163 /* Returns true if S1 intersects with S2.  Since we already know that S1 does
1164    not subsume S2 or vice-versa, we only check for entry bbs.  */
1165
1166 bool
1167 scop_detection::intersects (sese_l s1, sese_l s2)
1168 {
1169   if (dominated_by_p (CDI_DOMINATORS, get_entry_bb (s2),
1170                       get_entry_bb (s1))
1171       && !dominated_by_p (CDI_DOMINATORS, get_entry_bb (s2),
1172                           get_exit_bb (s1)))
1173     return true;
1174   if ((s1.exit == s2.entry) || (s2.exit == s1.entry))
1175     return true;
1176
1177   return false;
1178 }
1179
1180 /* Remove one of the scops when it intersects with any other.  */
1181
1182 void
1183 scop_detection::remove_intersecting_scops (sese_l s1)
1184 {
1185   int j;
1186   sese_l *s2;
1187   FOR_EACH_VEC_ELT_REVERSE (scops, j, s2)
1188     {
1189       if (intersects (s1, *s2))
1190         {
1191           DEBUG_PRINT (dp << "Removing intersecting SCoP";
1192                        print_sese (dump_file, *s2);
1193                        dp << "Intersects with:";
1194                        print_sese (dump_file, s1));
1195           scops.unordered_remove (j);
1196         }
1197     }
1198 }
1199
1200 /* Something like "n * m" is not allowed.  */
1201
1202 bool
1203 scop_detection::graphite_can_represent_init (tree e)
1204 {
1205   switch (TREE_CODE (e))
1206     {
1207     case POLYNOMIAL_CHREC:
1208       return graphite_can_represent_init (CHREC_LEFT (e))
1209         && graphite_can_represent_init (CHREC_RIGHT (e));
1210
1211     case MULT_EXPR:
1212       if (chrec_contains_symbols (TREE_OPERAND (e, 0)))
1213         return graphite_can_represent_init (TREE_OPERAND (e, 0))
1214           && tree_fits_shwi_p (TREE_OPERAND (e, 1));
1215       else
1216         return graphite_can_represent_init (TREE_OPERAND (e, 1))
1217           && tree_fits_shwi_p (TREE_OPERAND (e, 0));
1218
1219     case PLUS_EXPR:
1220     case POINTER_PLUS_EXPR:
1221     case MINUS_EXPR:
1222       return graphite_can_represent_init (TREE_OPERAND (e, 0))
1223         && graphite_can_represent_init (TREE_OPERAND (e, 1));
1224
1225     case NEGATE_EXPR:
1226     case BIT_NOT_EXPR:
1227     CASE_CONVERT:
1228     case NON_LVALUE_EXPR:
1229       return graphite_can_represent_init (TREE_OPERAND (e, 0));
1230
1231     default:
1232       break;
1233     }
1234
1235   return true;
1236 }
1237
1238 /* Return true when SCEV can be represented in the polyhedral model.
1239
1240    An expression can be represented, if it can be expressed as an
1241    affine expression.  For loops (i, j) and parameters (m, n) all
1242    affine expressions are of the form:
1243
1244    x1 * i + x2 * j + x3 * m + x4 * n + x5 * 1 where x1..x5 element of Z
1245
1246    1 i + 20 j + (-2) m + 25
1247
1248    Something like "i * n" or "n * m" is not allowed.  */
1249
1250 bool
1251 scop_detection::graphite_can_represent_scev (tree scev)
1252 {
1253   if (chrec_contains_undetermined (scev))
1254     return false;
1255
1256   /* We disable the handling of pointer types, because it’s currently not
1257      supported by Graphite with the isl AST generator. SSA_NAME nodes are
1258      the only nodes, which are disabled in case they are pointers to object
1259      types, but this can be changed.  */
1260
1261   if (POINTER_TYPE_P (TREE_TYPE (scev)) && TREE_CODE (scev) == SSA_NAME)
1262     return false;
1263
1264   switch (TREE_CODE (scev))
1265     {
1266     case NEGATE_EXPR:
1267     case BIT_NOT_EXPR:
1268     CASE_CONVERT:
1269     case NON_LVALUE_EXPR:
1270       return graphite_can_represent_scev (TREE_OPERAND (scev, 0));
1271
1272     case PLUS_EXPR:
1273     case POINTER_PLUS_EXPR:
1274     case MINUS_EXPR:
1275       return graphite_can_represent_scev (TREE_OPERAND (scev, 0))
1276         && graphite_can_represent_scev (TREE_OPERAND (scev, 1));
1277
1278     case MULT_EXPR:
1279       return !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev, 0)))
1280         && !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev, 1)))
1281         && !(chrec_contains_symbols (TREE_OPERAND (scev, 0))
1282              && chrec_contains_symbols (TREE_OPERAND (scev, 1)))
1283         && graphite_can_represent_init (scev)
1284         && graphite_can_represent_scev (TREE_OPERAND (scev, 0))
1285         && graphite_can_represent_scev (TREE_OPERAND (scev, 1));
1286
1287     case POLYNOMIAL_CHREC:
1288       /* Check for constant strides.  With a non constant stride of
1289          'n' we would have a value of 'iv * n'.  Also check that the
1290          initial value can represented: for example 'n * m' cannot be
1291          represented.  */
1292       if (!evolution_function_right_is_integer_cst (scev)
1293           || !graphite_can_represent_init (scev))
1294         return false;
1295       return graphite_can_represent_scev (CHREC_LEFT (scev));
1296
1297     default:
1298       break;
1299     }
1300
1301   /* Only affine functions can be represented.  */
1302   if (tree_contains_chrecs (scev, NULL) || !scev_is_linear_expression (scev))
1303     return false;
1304
1305   return true;
1306 }
1307
1308 /* Return true when EXPR can be represented in the polyhedral model.
1309
1310    This means an expression can be represented, if it is linear with respect to
1311    the loops and the strides are non parametric.  LOOP is the place where the
1312    expr will be evaluated.  SCOP defines the region we analyse.  */
1313
1314 bool
1315 scop_detection::graphite_can_represent_expr (sese_l scop, loop_p loop,
1316                                              tree expr)
1317 {
1318   tree scev = scalar_evolution_in_region (scop, loop, expr);
1319   return graphite_can_represent_scev (scev);
1320 }
1321
1322 /* Return true if the data references of STMT can be represented by Graphite.
1323    We try to analyze the data references in a loop contained in the SCOP.  */
1324
1325 bool
1326 scop_detection::stmt_has_simple_data_refs_p (sese_l scop, gimple *stmt)
1327 {
1328   loop_p nest = outermost_loop_in_sese (scop, gimple_bb (stmt));
1329   loop_p loop = loop_containing_stmt (stmt);
1330   vec<data_reference_p> drs = vNULL;
1331
1332   graphite_find_data_references_in_stmt (nest, loop, stmt, &drs);
1333
1334   int j;
1335   data_reference_p dr;
1336   FOR_EACH_VEC_ELT (drs, j, dr)
1337     {
1338       int nb_subscripts = DR_NUM_DIMENSIONS (dr);
1339
1340       if (nb_subscripts < 1)
1341         {
1342           free_data_refs (drs);
1343           return false;
1344         }
1345
1346       tree ref = DR_REF (dr);
1347
1348       for (int i = nb_subscripts - 1; i >= 0; i--)
1349         {
1350           if (!graphite_can_represent_scev (DR_ACCESS_FN (dr, i))
1351               || (TREE_CODE (ref) != ARRAY_REF && TREE_CODE (ref) != MEM_REF
1352                   && TREE_CODE (ref) != COMPONENT_REF))
1353             {
1354               free_data_refs (drs);
1355               return false;
1356             }
1357
1358           ref = TREE_OPERAND (ref, 0);
1359         }
1360     }
1361
1362     free_data_refs (drs);
1363     return true;
1364 }
1365
1366 /* GIMPLE_ASM and GIMPLE_CALL may embed arbitrary side effects.
1367    Calls have side-effects, except those to const or pure
1368    functions.  */
1369
1370 static bool
1371 stmt_has_side_effects (gimple *stmt)
1372 {
1373   if (gimple_has_volatile_ops (stmt)
1374       || (gimple_code (stmt) == GIMPLE_CALL
1375           && !(gimple_call_flags (stmt) & (ECF_CONST | ECF_PURE)))
1376       || (gimple_code (stmt) == GIMPLE_ASM))
1377     {
1378       DEBUG_PRINT (dp << "[scop-detection-fail] "
1379                       << "Statement has side-effects:\n";
1380         print_gimple_stmt (dump_file, stmt, 0, TDF_VOPS | TDF_MEMSYMS));
1381       return true;
1382     }
1383   return false;
1384 }
1385
1386 /* Returns true if STMT can be represented in polyhedral model. LABEL,
1387    simple COND stmts, pure calls, and assignments can be repesented.  */
1388
1389 bool
1390 scop_detection::graphite_can_represent_stmt (sese_l scop, gimple *stmt,
1391                                              basic_block bb)
1392 {
1393   loop_p loop = bb->loop_father;
1394   switch (gimple_code (stmt))
1395     {
1396     case GIMPLE_LABEL:
1397       return true;
1398
1399     case GIMPLE_COND:
1400       {
1401         /* We can handle all binary comparisons.  Inequalities are
1402            also supported as they can be represented with union of
1403            polyhedra.  */
1404         enum tree_code code = gimple_cond_code (stmt);
1405         if (!(code == LT_EXPR
1406               || code == GT_EXPR
1407               || code == LE_EXPR
1408               || code == GE_EXPR
1409               || code == EQ_EXPR
1410               || code == NE_EXPR))
1411           {
1412             DEBUG_PRINT (dp << "[scop-detection-fail] "
1413                             << "Graphite cannot handle cond stmt:\n";
1414                          print_gimple_stmt (dump_file, stmt, 0,
1415                                             TDF_VOPS | TDF_MEMSYMS));
1416             return false;
1417           }
1418
1419         for (unsigned i = 0; i < 2; ++i)
1420           {
1421             tree op = gimple_op (stmt, i);
1422             if (!graphite_can_represent_expr (scop, loop, op)
1423                 /* We can only constrain on integer type.  */
1424                 || (TREE_CODE (TREE_TYPE (op)) != INTEGER_TYPE))
1425               {
1426                 DEBUG_PRINT (dp << "[scop-detection-fail] "
1427                                 << "Graphite cannot represent stmt:\n";
1428                              print_gimple_stmt (dump_file, stmt, 0,
1429                                                 TDF_VOPS | TDF_MEMSYMS));
1430                 return false;
1431               }
1432           }
1433
1434         return true;
1435       }
1436
1437     case GIMPLE_ASSIGN:
1438     case GIMPLE_CALL:
1439       return true;
1440
1441     default:
1442       /* These nodes cut a new scope.  */
1443       DEBUG_PRINT (
1444           dp << "[scop-detection-fail] "
1445              << "Gimple stmt not handled in Graphite:\n";
1446           print_gimple_stmt (dump_file, stmt, 0, TDF_VOPS | TDF_MEMSYMS));
1447       return false;
1448     }
1449 }
1450
1451 /* Return true only when STMT is simple enough for being handled by Graphite.
1452    This depends on SCOP, as the parameters are initialized relatively to
1453    this basic block, the linear functions are initialized based on the outermost
1454    loop containing STMT inside the SCOP.  BB is the place where we try to
1455    evaluate the STMT.  */
1456
1457 bool
1458 scop_detection::stmt_simple_for_scop_p (sese_l scop, gimple *stmt,
1459                                         basic_block bb) const
1460 {
1461   gcc_assert (scop);
1462
1463   if (is_gimple_debug (stmt))
1464     return true;
1465
1466   if (stmt_has_side_effects (stmt))
1467     return false;
1468
1469   if (!stmt_has_simple_data_refs_p (scop, stmt))
1470     {
1471       DEBUG_PRINT (dp << "[scop-detection-fail] "
1472                       << "Graphite cannot handle data-refs in stmt:\n";
1473         print_gimple_stmt (dump_file, stmt, 0, TDF_VOPS|TDF_MEMSYMS););
1474       return false;
1475     }
1476
1477   return graphite_can_represent_stmt (scop, stmt, bb);
1478 }
1479
1480 /* Return true when BB contains a harmful operation for a scop: that
1481    can be a function call with side effects, the induction variables
1482    are not linear with respect to SCOP, etc.  The current open
1483    scop should end before this statement.  */
1484
1485 bool
1486 scop_detection::harmful_stmt_in_bb (sese_l scop, basic_block bb) const
1487 {
1488   gimple_stmt_iterator gsi;
1489
1490   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1491     if (!stmt_simple_for_scop_p (scop, gsi_stmt (gsi), bb))
1492       return true;
1493
1494   return false;
1495 }
1496
1497 /* Return true when the body of LOOP has statements that can be represented as a
1498    valid scop.  */
1499
1500 bool
1501 scop_detection::loop_body_is_valid_scop (loop_p loop, sese_l scop) const
1502 {
1503   if (!loop_ivs_can_be_represented (loop))
1504     {
1505       DEBUG_PRINT (dp << "[scop-detection-fail] loop_" << loop->num
1506                       << "IV cannot be represented.\n");
1507       return false;
1508     }
1509
1510   if (!loop_nest_has_data_refs (loop))
1511     {
1512       DEBUG_PRINT (dp << "[scop-detection-fail] loop_" << loop->num
1513                       << "does not have any data reference.\n");
1514       return false;
1515     }
1516
1517   basic_block *bbs = get_loop_body (loop);
1518   for (unsigned i = 0; i < loop->num_nodes; i++)
1519     {
1520       basic_block bb = bbs[i];
1521
1522       if (harmful_stmt_in_bb (scop, bb))
1523         {
1524           free (bbs);
1525           return false;
1526         }
1527     }
1528   free (bbs);
1529
1530   if (loop->inner)
1531     {
1532       loop = loop->inner;
1533       while (loop)
1534         {
1535           if (!loop_body_is_valid_scop (loop, scop))
1536             return false;
1537           loop = loop->next;
1538         }
1539     }
1540
1541   return true;
1542 }
1543
1544 /* Returns the number of pbbs that are in loops contained in SCOP.  */
1545
1546 int
1547 scop_detection::nb_pbbs_in_loops (scop_p scop)
1548 {
1549   int i;
1550   poly_bb_p pbb;
1551   int res = 0;
1552
1553   FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
1554     if (loop_in_sese_p (gbb_loop (PBB_BLACK_BOX (pbb)), scop->scop_info->region))
1555       res++;
1556
1557   return res;
1558 }
1559
1560 /* When parameter NAME is in REGION, returns its index in SESE_PARAMS.
1561    Otherwise returns -1.  */
1562
1563 static inline int
1564 parameter_index_in_region_1 (tree name, sese_info_p region)
1565 {
1566   int i;
1567   tree p;
1568
1569   gcc_assert (TREE_CODE (name) == SSA_NAME);
1570
1571   FOR_EACH_VEC_ELT (region->params, i, p)
1572     if (p == name)
1573       return i;
1574
1575   return -1;
1576 }
1577
1578 /* When the parameter NAME is in REGION, returns its index in
1579    SESE_PARAMS.  Otherwise this function inserts NAME in SESE_PARAMS
1580    and returns the index of NAME.  */
1581
1582 static int
1583 parameter_index_in_region (tree name, sese_info_p region)
1584 {
1585   int i;
1586
1587   gcc_assert (TREE_CODE (name) == SSA_NAME);
1588
1589   /* Cannot constrain on anything else than INTEGER_TYPE parameters.  */
1590   if (TREE_CODE (TREE_TYPE (name)) != INTEGER_TYPE)
1591     return -1;
1592
1593   if (!invariant_in_sese_p_rec (name, region->region, NULL))
1594     return -1;
1595
1596   i = parameter_index_in_region_1 (name, region);
1597   if (i != -1)
1598     return i;
1599
1600   i = region->params.length ();
1601   region->params.safe_push (name);
1602   return i;
1603 }
1604
1605 /* In the context of sese S, scan the expression E and translate it to
1606    a linear expression C.  When parsing a symbolic multiplication, K
1607    represents the constant multiplier of an expression containing
1608    parameters.  */
1609
1610 static void
1611 scan_tree_for_params (sese_info_p s, tree e)
1612 {
1613   if (e == chrec_dont_know)
1614     return;
1615
1616   switch (TREE_CODE (e))
1617     {
1618     case POLYNOMIAL_CHREC:
1619       scan_tree_for_params (s, CHREC_LEFT (e));
1620       break;
1621
1622     case MULT_EXPR:
1623       if (chrec_contains_symbols (TREE_OPERAND (e, 0)))
1624         scan_tree_for_params (s, TREE_OPERAND (e, 0));
1625       else
1626         scan_tree_for_params (s, TREE_OPERAND (e, 1));
1627       break;
1628
1629     case PLUS_EXPR:
1630     case POINTER_PLUS_EXPR:
1631     case MINUS_EXPR:
1632       scan_tree_for_params (s, TREE_OPERAND (e, 0));
1633       scan_tree_for_params (s, TREE_OPERAND (e, 1));
1634       break;
1635
1636     case NEGATE_EXPR:
1637     case BIT_NOT_EXPR:
1638     CASE_CONVERT:
1639     case NON_LVALUE_EXPR:
1640       scan_tree_for_params (s, TREE_OPERAND (e, 0));
1641       break;
1642
1643     case SSA_NAME:
1644       parameter_index_in_region (e, s);
1645       break;
1646
1647     case INTEGER_CST:
1648     case ADDR_EXPR:
1649     case REAL_CST:
1650     case COMPLEX_CST:
1651     case VECTOR_CST:
1652       break;
1653
1654    default:
1655       gcc_unreachable ();
1656       break;
1657     }
1658 }
1659
1660 /* Find parameters with respect to REGION in BB. We are looking in memory
1661    access functions, conditions and loop bounds.  */
1662
1663 static void
1664 find_params_in_bb (sese_info_p region, gimple_poly_bb_p gbb)
1665 {
1666   /* Find parameters in the access functions of data references.  */
1667   int i;
1668   data_reference_p dr;
1669   FOR_EACH_VEC_ELT (GBB_DATA_REFS (gbb), i, dr)
1670     for (unsigned j = 0; j < DR_NUM_DIMENSIONS (dr); j++)
1671       scan_tree_for_params (region, DR_ACCESS_FN (dr, j));
1672
1673   /* Find parameters in conditional statements.  */
1674   gimple *stmt;
1675   loop_p loop = GBB_BB (gbb)->loop_father;
1676   FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb), i, stmt)
1677     {
1678       tree lhs = scalar_evolution_in_region (region->region, loop,
1679                                              gimple_cond_lhs (stmt));
1680       tree rhs = scalar_evolution_in_region (region->region, loop,
1681                                              gimple_cond_rhs (stmt));
1682
1683       scan_tree_for_params (region, lhs);
1684       scan_tree_for_params (region, rhs);
1685     }
1686 }
1687
1688 /* Record the parameters used in the SCOP.  A variable is a parameter
1689    in a scop if it does not vary during the execution of that scop.  */
1690
1691 static void
1692 find_scop_parameters (scop_p scop)
1693 {
1694   unsigned i;
1695   sese_info_p region = scop->scop_info;
1696   struct loop *loop;
1697
1698   /* Find the parameters used in the loop bounds.  */
1699   FOR_EACH_VEC_ELT (region->loop_nest, i, loop)
1700     {
1701       tree nb_iters = number_of_latch_executions (loop);
1702
1703       if (!chrec_contains_symbols (nb_iters))
1704         continue;
1705
1706       nb_iters = scalar_evolution_in_region (region->region, loop, nb_iters);
1707       scan_tree_for_params (region, nb_iters);
1708     }
1709
1710   /* Find the parameters used in data accesses.  */
1711   poly_bb_p pbb;
1712   FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
1713     find_params_in_bb (region, PBB_BLACK_BOX (pbb));
1714
1715   int nbp = sese_nb_params (region);
1716   scop_set_nb_params (scop, nbp);
1717 }
1718
1719 /* Record DEF if it is used in other bbs different than DEF_BB in the SCOP.  */
1720
1721 static void
1722 build_cross_bb_scalars_def (scop_p scop, tree def, basic_block def_bb,
1723                              vec<tree> *writes)
1724 {
1725   if (!def || !is_gimple_reg (def))
1726     return;
1727
1728   /* Do not gather scalar variables that can be analyzed by SCEV as they can be
1729      generated out of the induction variables.  */
1730   if (scev_analyzable_p (def, scop->scop_info->region))
1731     return;
1732
1733   gimple *use_stmt;
1734   imm_use_iterator imm_iter;
1735   FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def)
1736     if (def_bb != gimple_bb (use_stmt) && !is_gimple_debug (use_stmt))
1737       {
1738         writes->safe_push (def);
1739         DEBUG_PRINT (dp << "Adding scalar write: ";
1740                      print_generic_expr (dump_file, def, 0);
1741                      dp << "\nFrom stmt: ";
1742                      print_gimple_stmt (dump_file,
1743                                         SSA_NAME_DEF_STMT (def), 0, 0));
1744         /* This is required by the FOR_EACH_IMM_USE_STMT when we want to break
1745            before all the uses have been visited.  */
1746         BREAK_FROM_IMM_USE_STMT (imm_iter);
1747       }
1748 }
1749
1750 /* Record DEF if it is used in other bbs different than DEF_BB in the SCOP.  */
1751
1752 static void
1753 build_cross_bb_scalars_use (scop_p scop, tree use, gimple *use_stmt,
1754                             vec<scalar_use> *reads)
1755 {
1756   gcc_assert (use);
1757   if (!is_gimple_reg (use))
1758     return;
1759
1760   /* Do not gather scalar variables that can be analyzed by SCEV as they can be
1761      generated out of the induction variables.  */
1762   if (scev_analyzable_p (use, scop->scop_info->region))
1763     return;
1764
1765   gimple *def_stmt = SSA_NAME_DEF_STMT (use);
1766   if (gimple_bb (def_stmt) != gimple_bb (use_stmt))
1767     {
1768       DEBUG_PRINT (dp << "Adding scalar read: ";
1769                    print_generic_expr (dump_file, use, 0);
1770                    dp << "\nFrom stmt: ";
1771                    print_gimple_stmt (dump_file, use_stmt, 0, 0));
1772       reads->safe_push (std::make_pair (use_stmt, use));
1773     }
1774 }
1775
1776 /* Record all scalar variables that are defined and used in different BBs of the
1777    SCOP.  */
1778
1779 static void
1780 graphite_find_cross_bb_scalar_vars (scop_p scop, gimple *stmt,
1781                                     vec<scalar_use> *reads, vec<tree> *writes)
1782 {
1783   tree def;
1784
1785   if (gimple_code (stmt) == GIMPLE_ASSIGN)
1786     def = gimple_assign_lhs (stmt);
1787   else if (gimple_code (stmt) == GIMPLE_CALL)
1788     def = gimple_call_lhs (stmt);
1789   else if (gimple_code (stmt) == GIMPLE_PHI)
1790     def = gimple_phi_result (stmt);
1791   else
1792     return;
1793
1794
1795   build_cross_bb_scalars_def (scop, def, gimple_bb (stmt), writes);
1796
1797   ssa_op_iter iter;
1798   use_operand_p use_p;
1799   FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE)
1800     {
1801       tree use = USE_FROM_PTR (use_p);
1802       build_cross_bb_scalars_use (scop, use, stmt, reads);
1803     }
1804 }
1805
1806 /* Generates a polyhedral black box only if the bb contains interesting
1807    information.  */
1808
1809 static gimple_poly_bb_p
1810 try_generate_gimple_bb (scop_p scop, basic_block bb)
1811 {
1812   vec<data_reference_p> drs = vNULL;
1813   vec<tree> writes = vNULL;
1814   vec<scalar_use> reads = vNULL;
1815
1816   sese_l region = scop->scop_info->region;
1817   loop_p nest = outermost_loop_in_sese (region, bb);
1818
1819   loop_p loop = bb->loop_father;
1820   if (!loop_in_sese_p (loop, region))
1821     loop = nest;
1822
1823   for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
1824        gsi_next (&gsi))
1825     {
1826       gimple *stmt = gsi_stmt (gsi);
1827       if (is_gimple_debug (stmt))
1828         continue;
1829
1830       graphite_find_data_references_in_stmt (nest, loop, stmt, &drs);
1831       graphite_find_cross_bb_scalar_vars (scop, stmt, &reads, &writes);
1832     }
1833
1834   for (gphi_iterator psi = gsi_start_phis (bb); !gsi_end_p (psi);
1835        gsi_next (&psi))
1836     if (!virtual_operand_p (gimple_phi_result (psi.phi ())))
1837       graphite_find_cross_bb_scalar_vars (scop, psi.phi (), &reads, &writes);
1838
1839   if (drs.is_empty () && writes.is_empty () && reads.is_empty ())
1840     return NULL;
1841
1842   return new_gimple_poly_bb (bb, drs, reads, writes);
1843 }
1844
1845 /* Compute alias-sets for all data references in DRS.  */
1846
1847 static void
1848 build_alias_set (scop_p scop)
1849 {
1850   int num_vertices = scop->drs.length ();
1851   struct graph *g = new_graph (num_vertices);
1852   dr_info *dr1, *dr2;
1853   int i, j;
1854   int *all_vertices;
1855
1856   FOR_EACH_VEC_ELT (scop->drs, i, dr1)
1857     for (j = i+1; scop->drs.iterate (j, &dr2); j++)
1858       if (dr_may_alias_p (dr1->dr, dr2->dr, true))
1859         {
1860           add_edge (g, i, j);
1861           add_edge (g, j, i);
1862         }
1863
1864   all_vertices = XNEWVEC (int, num_vertices);
1865   for (i = 0; i < num_vertices; i++)
1866     all_vertices[i] = i;
1867
1868   graphds_dfs (g, all_vertices, num_vertices, NULL, true, NULL);
1869   free (all_vertices);
1870
1871   for (i = 0; i < g->n_vertices; i++)
1872     scop->drs[i].alias_set = g->vertices[i].component + 1;
1873
1874   free_graph (g);
1875 }
1876
1877 /* Gather BBs and conditions for a SCOP.  */
1878 class gather_bbs : public dom_walker
1879 {
1880 public:
1881   gather_bbs (cdi_direction, scop_p);
1882
1883   virtual edge before_dom_children (basic_block);
1884   virtual void after_dom_children (basic_block);
1885
1886 private:
1887   auto_vec<gimple *, 3> conditions, cases;
1888   scop_p scop;
1889 };
1890 }
1891 gather_bbs::gather_bbs (cdi_direction direction, scop_p scop)
1892   : dom_walker (direction), scop (scop)
1893 {
1894 }
1895
1896 /* Record in execution order the loops fully contained in the region.  */
1897
1898 static void
1899 record_loop_in_sese (basic_block bb, sese_info_p region)
1900 {
1901   loop_p father = bb->loop_father;
1902   if (loop_in_sese_p (father, region->region))
1903     {
1904       bool found = false;
1905       loop_p loop0;
1906       int j;
1907       FOR_EACH_VEC_ELT (region->loop_nest, j, loop0)
1908         if (father == loop0)
1909           {
1910             found = true;
1911             break;
1912           }
1913       if (!found)
1914         region->loop_nest.safe_push (father);
1915     }
1916 }
1917
1918 /* Call-back for dom_walk executed before visiting the dominated
1919    blocks.  */
1920
1921 edge
1922 gather_bbs::before_dom_children (basic_block bb)
1923 {
1924   sese_info_p region = scop->scop_info;
1925   if (!bb_in_sese_p (bb, region->region))
1926     return NULL;
1927
1928   record_loop_in_sese (bb, region);
1929
1930   gcond *stmt = single_pred_cond_non_loop_exit (bb);
1931
1932   if (stmt)
1933     {
1934       edge e = single_pred_edge (bb);
1935
1936       conditions.safe_push (stmt);
1937
1938       if (e->flags & EDGE_TRUE_VALUE)
1939         cases.safe_push (stmt);
1940       else
1941         cases.safe_push (NULL);
1942     }
1943
1944   scop->scop_info->bbs.safe_push (bb);
1945
1946   gimple_poly_bb_p gbb = try_generate_gimple_bb (scop, bb);
1947   if (!gbb)
1948     return NULL;
1949
1950   GBB_CONDITIONS (gbb) = conditions.copy ();
1951   GBB_CONDITION_CASES (gbb) = cases.copy ();
1952
1953   poly_bb_p pbb = new_poly_bb (scop, gbb);
1954   scop->pbbs.safe_push (pbb);
1955
1956   int i;
1957   data_reference_p dr;
1958   FOR_EACH_VEC_ELT (gbb->data_refs, i, dr)
1959     {
1960       DEBUG_PRINT (dp << "Adding memory ";
1961                    if (dr->is_read)
1962                      dp << "read: ";
1963                    else
1964                      dp << "write: ";
1965                    print_generic_expr (dump_file, dr->ref, 0);
1966                    dp << "\nFrom stmt: ";
1967                    print_gimple_stmt (dump_file, dr->stmt, 0, 0));
1968
1969       scop->drs.safe_push (dr_info (dr, pbb));
1970     }
1971
1972   return NULL;
1973 }
1974
1975 /* Call-back for dom_walk executed after visiting the dominated
1976    blocks.  */
1977
1978 void
1979 gather_bbs::after_dom_children (basic_block bb)
1980 {
1981   if (!bb_in_sese_p (bb, scop->scop_info->region))
1982     return;
1983
1984   if (single_pred_cond_non_loop_exit (bb))
1985     {
1986       conditions.pop ();
1987       cases.pop ();
1988     }
1989 }
1990
1991 /* Find Static Control Parts (SCoP) in the current function and pushes
1992    them to SCOPS.  */
1993
1994 void
1995 build_scops (vec<scop_p> *scops)
1996 {
1997   if (dump_file)
1998     dp.set_dump_file (dump_file);
1999
2000   canonicalize_loop_closed_ssa_form ();
2001
2002   scop_detection sb;
2003   sb.build_scop_depth (scop_detection::invalid_sese, current_loops->tree_root);
2004
2005   /* Now create scops from the lightweight SESEs.  */
2006   vec<sese_l> scops_l = sb.get_scops ();
2007   int i;
2008   sese_l *s;
2009   FOR_EACH_VEC_ELT (scops_l, i, s)
2010     {
2011       scop_p scop = new_scop (s->entry, s->exit);
2012
2013       /* Record all basic blocks and their conditions in REGION.  */
2014       gather_bbs (CDI_DOMINATORS, scop).walk (cfun->cfg->x_entry_block_ptr);
2015
2016       build_alias_set (scop);
2017
2018       /* Do not optimize a scop containing only PBBs that do not belong
2019          to any loops.  */
2020       if (sb.nb_pbbs_in_loops (scop) == 0)
2021         {
2022           DEBUG_PRINT (dp << "[scop-detection-fail] no data references.\n");
2023           free_scop (scop);
2024           continue;
2025         }
2026
2027       unsigned max_arrays = PARAM_VALUE (PARAM_GRAPHITE_MAX_ARRAYS_PER_SCOP);
2028       if (scop->drs.length () >= max_arrays)
2029         {
2030           DEBUG_PRINT (dp << "[scop-detection-fail] too many data references: "
2031                        << scop->drs.length ()
2032                        << " is larger than --param graphite-max-arrays-per-scop="
2033                        << max_arrays << ".\n");
2034           free_scop (scop);
2035           continue;
2036         }
2037
2038       find_scop_parameters (scop);
2039       graphite_dim_t max_dim = PARAM_VALUE (PARAM_GRAPHITE_MAX_NB_SCOP_PARAMS);
2040
2041       if (scop_nb_params (scop) > max_dim)
2042         {
2043           DEBUG_PRINT (dp << "[scop-detection-fail] too many parameters: "
2044                           << scop_nb_params (scop)
2045                           << " larger than --param graphite-max-nb-scop-params="
2046                           << max_dim << ".\n");
2047           free_scop (scop);
2048           continue;
2049         }
2050
2051       scops->safe_push (scop);
2052     }
2053
2054   DEBUG_PRINT (dp << "number of SCoPs: " << (scops ? scops->length () : 0););
2055 }
2056
2057 #endif /* HAVE_isl */