gcc/graphite-scop-detection.c

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