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