LCOV - code coverage report
Current view: top level - gcc - graphite-scop-detection.c (source / functions) Hit Total Coverage
Test: gcc.info Lines: 576 718 80.2 %
Date: 2020-04-04 11:58:09 Functions: 32 37 86.5 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 0 -

           Branch data     Line data    Source code
       1                 :            : /* Detection of Static Control Parts (SCoP) for Graphite.
       2                 :            :    Copyright (C) 2009-2020 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 "tree.h"
      34                 :            : #include "gimple.h"
      35                 :            : #include "ssa.h"
      36                 :            : #include "fold-const.h"
      37                 :            : #include "gimple-iterator.h"
      38                 :            : #include "tree-cfg.h"
      39                 :            : #include "tree-ssa-loop-manip.h"
      40                 :            : #include "tree-ssa-loop-niter.h"
      41                 :            : #include "tree-ssa-loop.h"
      42                 :            : #include "tree-into-ssa.h"
      43                 :            : #include "tree-ssa.h"
      44                 :            : #include "cfgloop.h"
      45                 :            : #include "tree-data-ref.h"
      46                 :            : #include "tree-scalar-evolution.h"
      47                 :            : #include "tree-pass.h"
      48                 :            : #include "tree-ssa-propagate.h"
      49                 :            : #include "gimple-pretty-print.h"
      50                 :            : #include "cfganal.h"
      51                 :            : #include "graphite.h"
      52                 :            : 
      53                 :            : class debug_printer
      54                 :            : {
      55                 :            : private:
      56                 :            :   FILE *dump_file;
      57                 :            : 
      58                 :            : public:
      59                 :            :   void
      60                 :        188 :   set_dump_file (FILE *f)
      61                 :            :   {
      62                 :        188 :     gcc_assert (f);
      63                 :        188 :     dump_file = f;
      64                 :        188 :   }
      65                 :            : 
      66                 :            :   friend debug_printer &
      67                 :       2006 :   operator<< (debug_printer &output, int i)
      68                 :            :   {
      69                 :          0 :     fprintf (output.dump_file, "%d", i);
      70                 :        187 :     return output;
      71                 :            :   }
      72                 :            :   friend debug_printer &
      73                 :       6960 :   operator<< (debug_printer &output, const char *s)
      74                 :            :   {
      75                 :       6960 :     fprintf (output.dump_file, "%s", s);
      76                 :       2181 :     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                 :          0 : dot_all_sese (FILE *file, vec<sese_l>& scops)
      97                 :            : {
      98                 :            :   /* Disable debugging while printing graph.  */
      99                 :          0 :   dump_flags_t tmp_dump_flags = dump_flags;
     100                 :          0 :   dump_flags = TDF_NONE;
     101                 :            : 
     102                 :          0 :   fprintf (file, "digraph all {\n");
     103                 :            : 
     104                 :          0 :   basic_block bb;
     105                 :          0 :   FOR_ALL_BB_FN (bb, cfun)
     106                 :            :     {
     107                 :          0 :       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                 :          0 :       fprintf (file, "%d [label=<\n  <TABLE BORDER=\"0\" CELLBORDER=\"1\" ",
     113                 :            :                bb->index);
     114                 :          0 :       fprintf (file, "CELLSPACING=\"0\">\n");
     115                 :            : 
     116                 :            :       /* Select color for SCoP.  */
     117                 :          0 :       sese_l *region;
     118                 :          0 :       int i;
     119                 :          0 :       FOR_EACH_VEC_ELT (scops, i, region)
     120                 :            :         {
     121                 :          0 :           bool sese_in_region = bb_in_sese_p (bb, *region);
     122                 :          0 :           if (sese_in_region || (region->exit->dest == bb)
     123                 :          0 :               || (region->entry->dest == bb))
     124                 :            :             {
     125                 :          0 :               const char *color;
     126                 :          0 :               switch (i % 17)
     127                 :            :                 {
     128                 :            :                 case 0: /* red */
     129                 :            :                   color = "#e41a1c";
     130                 :            :                   break;
     131                 :          0 :                 case 1: /* blue */
     132                 :          0 :                   color = "#377eb8";
     133                 :          0 :                   break;
     134                 :          0 :                 case 2: /* green */
     135                 :          0 :                   color = "#4daf4a";
     136                 :          0 :                   break;
     137                 :          0 :                 case 3: /* purple */
     138                 :          0 :                   color = "#984ea3";
     139                 :          0 :                   break;
     140                 :          0 :                 case 4: /* orange */
     141                 :          0 :                   color = "#ff7f00";
     142                 :          0 :                   break;
     143                 :          0 :                 case 5: /* yellow */
     144                 :          0 :                   color = "#ffff33";
     145                 :          0 :                   break;
     146                 :          0 :                 case 6: /* brown */
     147                 :          0 :                   color = "#a65628";
     148                 :          0 :                   break;
     149                 :          0 :                 case 7: /* rose */
     150                 :          0 :                   color = "#f781bf";
     151                 :          0 :                   break;
     152                 :          0 :                 case 8:
     153                 :          0 :                   color = "#8dd3c7";
     154                 :          0 :                   break;
     155                 :          0 :                 case 9:
     156                 :          0 :                   color = "#ffffb3";
     157                 :          0 :                   break;
     158                 :          0 :                 case 10:
     159                 :          0 :                   color = "#bebada";
     160                 :          0 :                   break;
     161                 :          0 :                 case 11:
     162                 :          0 :                   color = "#fb8072";
     163                 :          0 :                   break;
     164                 :          0 :                 case 12:
     165                 :          0 :                   color = "#80b1d3";
     166                 :          0 :                   break;
     167                 :          0 :                 case 13:
     168                 :          0 :                   color = "#fdb462";
     169                 :          0 :                   break;
     170                 :          0 :                 case 14:
     171                 :          0 :                   color = "#b3de69";
     172                 :          0 :                   break;
     173                 :          0 :                 case 15:
     174                 :          0 :                   color = "#fccde5";
     175                 :          0 :                   break;
     176                 :          0 :                 case 16:
     177                 :          0 :                   color = "#bc80bd";
     178                 :          0 :                   break;
     179                 :            :                 default: /* gray */
     180                 :            :                   color = "#999999";
     181                 :            :                 }
     182                 :            : 
     183                 :          0 :               fprintf (file, "    <TR><TD WIDTH=\"50\" BGCOLOR=\"%s\">",
     184                 :            :                        color);
     185                 :            : 
     186                 :          0 :               if (!sese_in_region)
     187                 :          0 :                 fprintf (file, " (");
     188                 :            : 
     189                 :          0 :               if (bb == region->entry->dest && bb == region->exit->dest)
     190                 :          0 :                 fprintf (file, " %d*# ", bb->index);
     191                 :          0 :               else if (bb == region->entry->dest)
     192                 :          0 :                 fprintf (file, " %d* ", bb->index);
     193                 :          0 :               else if (bb == region->exit->dest)
     194                 :          0 :                 fprintf (file, " %d# ", bb->index);
     195                 :            :               else
     196                 :          0 :                 fprintf (file, " %d ", bb->index);
     197                 :            : 
     198                 :          0 :               fprintf (file, "{lp_%d}", bb->loop_father->num);
     199                 :            : 
     200                 :          0 :               if (!sese_in_region)
     201                 :          0 :                 fprintf (file, ")");
     202                 :            : 
     203                 :          0 :               fprintf (file, "</TD></TR>\n");
     204                 :          0 :               part_of_scop = true;
     205                 :            :             }
     206                 :            :         }
     207                 :            : 
     208                 :          0 :         if (!part_of_scop)
     209                 :            :           {
     210                 :          0 :             fprintf (file, "    <TR><TD WIDTH=\"50\" BGCOLOR=\"#ffffff\">");
     211                 :          0 :             fprintf (file, " %d {lp_%d} </TD></TR>\n", bb->index,
     212                 :          0 :                      bb->loop_father->num);
     213                 :            :           }
     214                 :          0 :         fprintf (file, "  </TABLE>>, shape=box, style=\"setlinewidth(0)\"]\n");
     215                 :            :     }
     216                 :            : 
     217                 :          0 :     FOR_ALL_BB_FN (bb, cfun)
     218                 :            :       {
     219                 :          0 :         edge e;
     220                 :          0 :         edge_iterator ei;
     221                 :          0 :         FOR_EACH_EDGE (e, ei, bb->succs)
     222                 :          0 :           fprintf (file, "%d -> %d;\n", bb->index, e->dest->index);
     223                 :            :       }
     224                 :            : 
     225                 :          0 :   fputs ("}\n\n", file);
     226                 :            : 
     227                 :            :   /* Enable debugging again.  */
     228                 :          0 :   dump_flags = tmp_dump_flags;
     229                 :          0 : }
     230                 :            : 
     231                 :            : /* Display SCoP on stderr.  */
     232                 :            : 
     233                 :            : DEBUG_FUNCTION void
     234                 :          0 : dot_sese (sese_l& scop)
     235                 :            : {
     236                 :          0 :   vec<sese_l> scops;
     237                 :          0 :   scops.create (1);
     238                 :            : 
     239                 :          0 :   if (scop)
     240                 :          0 :     scops.safe_push (scop);
     241                 :            : 
     242                 :          0 :   dot_all_sese (stderr, scops);
     243                 :            : 
     244                 :          0 :   scops.release ();
     245                 :          0 : }
     246                 :            : 
     247                 :            : DEBUG_FUNCTION void
     248                 :          0 : dot_cfg ()
     249                 :            : {
     250                 :          0 :   vec<sese_l> scops;
     251                 :          0 :   scops.create (1);
     252                 :          0 :   dot_all_sese (stderr, scops);
     253                 :          0 :   scops.release ();
     254                 :          0 : }
     255                 :            : 
     256                 :            : /* Returns a COND_EXPR statement when BB has a single predecessor, the
     257                 :            :    edge between BB and its predecessor is not a loop exit edge, and
     258                 :            :    the last statement of the single predecessor is a COND_EXPR.  */
     259                 :            : 
     260                 :            : static gcond *
     261                 :       3628 : single_pred_cond_non_loop_exit (basic_block bb)
     262                 :            : {
     263                 :       3628 :   if (single_pred_p (bb))
     264                 :            :     {
     265                 :       2594 :       edge e = single_pred_edge (bb);
     266                 :       2594 :       basic_block pred = e->src;
     267                 :       2594 :       gimple *stmt;
     268                 :            : 
     269                 :       7146 :       if (loop_depth (pred->loop_father) > loop_depth (bb->loop_father))
     270                 :            :         return NULL;
     271                 :            : 
     272                 :       1646 :       stmt = last_stmt (pred);
     273                 :            : 
     274                 :       1646 :       if (stmt && gimple_code (stmt) == GIMPLE_COND)
     275                 :       3628 :         return as_a<gcond *> (stmt);
     276                 :            :     }
     277                 :            : 
     278                 :            :   return NULL;
     279                 :            : }
     280                 :            : 
     281                 :            : namespace
     282                 :            : {
     283                 :            : 
     284                 :            : /* Build the maximal scop containing LOOPs and add it to SCOPS.  */
     285                 :            : 
     286                 :            : class scop_detection
     287                 :            : {
     288                 :            : public:
     289                 :        548 :   scop_detection () : scops (vNULL) {}
     290                 :            : 
     291                 :        548 :   ~scop_detection ()
     292                 :            :   {
     293                 :       1096 :     scops.release ();
     294                 :            :   }
     295                 :            : 
     296                 :            :   /* A marker for invalid sese_l.  */
     297                 :            :   static sese_l invalid_sese;
     298                 :            : 
     299                 :            :   /* Return the SCOPS in this SCOP_DETECTION.  */
     300                 :            : 
     301                 :            :   vec<sese_l>
     302                 :        548 :   get_scops ()
     303                 :            :   {
     304                 :        548 :     return scops;
     305                 :            :   }
     306                 :            : 
     307                 :            :   /* Return an sese_l around the LOOP.  */
     308                 :            : 
     309                 :            :   sese_l get_sese (loop_p loop);
     310                 :            : 
     311                 :            :   /* Merge scops at same loop depth and returns the new sese.
     312                 :            :      Returns a new SESE when merge was successful, INVALID_SESE otherwise.  */
     313                 :            : 
     314                 :            :   sese_l merge_sese (sese_l first, sese_l second) const;
     315                 :            : 
     316                 :            :   /* Build scop outer->inner if possible.  */
     317                 :            : 
     318                 :            :   void build_scop_depth (loop_p loop);
     319                 :            : 
     320                 :            :   /* Return true when BEGIN is the preheader edge of a loop with a single exit
     321                 :            :      END.  */
     322                 :            : 
     323                 :            :   static bool region_has_one_loop (sese_l s);
     324                 :            : 
     325                 :            :   /* Add to SCOPS a scop starting at SCOP_BEGIN and ending at SCOP_END.  */
     326                 :            : 
     327                 :            :   void add_scop (sese_l s);
     328                 :            : 
     329                 :            :   /* Returns true if S1 subsumes/surrounds S2.  */
     330                 :            :   static bool subsumes (sese_l s1, sese_l s2);
     331                 :            : 
     332                 :            :   /* Remove a SCoP which is subsumed by S1.  */
     333                 :            :   void remove_subscops (sese_l s1);
     334                 :            : 
     335                 :            :   /* Returns true if S1 intersects with S2.  Since we already know that S1 does
     336                 :            :      not subsume S2 or vice-versa, we only check for entry bbs.  */
     337                 :            : 
     338                 :            :   static bool intersects (sese_l s1, sese_l s2);
     339                 :            : 
     340                 :            :   /* Remove one of the scops when it intersects with any other.  */
     341                 :            : 
     342                 :            :   void remove_intersecting_scops (sese_l s1);
     343                 :            : 
     344                 :            :   /* Return true when a statement in SCOP cannot be represented by Graphite.  */
     345                 :            : 
     346                 :            :   bool harmful_loop_in_region (sese_l scop) const;
     347                 :            : 
     348                 :            :   /* Return true only when STMT is simple enough for being handled by Graphite.
     349                 :            :      This depends on SCOP, as the parameters are initialized relatively to
     350                 :            :      this basic block, the linear functions are initialized based on the
     351                 :            :      outermost loop containing STMT inside the SCOP.  BB is the place where we
     352                 :            :      try to evaluate the STMT.  */
     353                 :            : 
     354                 :            :   bool stmt_simple_for_scop_p (sese_l scop, gimple *stmt,
     355                 :            :                                basic_block bb) const;
     356                 :            : 
     357                 :            :   /* Something like "n * m" is not allowed.  */
     358                 :            : 
     359                 :            :   static bool graphite_can_represent_init (tree e);
     360                 :            : 
     361                 :            :   /* Return true when SCEV can be represented in the polyhedral model.
     362                 :            : 
     363                 :            :      An expression can be represented, if it can be expressed as an
     364                 :            :      affine expression.  For loops (i, j) and parameters (m, n) all
     365                 :            :      affine expressions are of the form:
     366                 :            : 
     367                 :            :      x1 * i + x2 * j + x3 * m + x4 * n + x5 * 1 where x1..x5 element of Z
     368                 :            : 
     369                 :            :      1 i + 20 j + (-2) m + 25
     370                 :            : 
     371                 :            :      Something like "i * n" or "n * m" is not allowed.  */
     372                 :            : 
     373                 :            :   static bool graphite_can_represent_scev (sese_l scop, tree scev);
     374                 :            : 
     375                 :            :   /* Return true when EXPR can be represented in the polyhedral model.
     376                 :            : 
     377                 :            :      This means an expression can be represented, if it is linear with respect
     378                 :            :      to the loops and the strides are non parametric.  LOOP is the place where
     379                 :            :      the expr will be evaluated.  SCOP defines the region we analyse.  */
     380                 :            : 
     381                 :            :   static bool graphite_can_represent_expr (sese_l scop, loop_p loop,
     382                 :            :                                            tree expr);
     383                 :            : 
     384                 :            :   /* Return true if the data references of STMT can be represented by Graphite.
     385                 :            :      We try to analyze the data references in a loop contained in the SCOP.  */
     386                 :            : 
     387                 :            :   static bool stmt_has_simple_data_refs_p (sese_l scop, gimple *stmt);
     388                 :            : 
     389                 :            :   /* Remove the close phi node at GSI and replace its rhs with the rhs
     390                 :            :      of PHI.  */
     391                 :            : 
     392                 :            :   static void remove_duplicate_close_phi (gphi *phi, gphi_iterator *gsi);
     393                 :            : 
     394                 :            :   /* Returns true when Graphite can represent LOOP in SCOP.
     395                 :            :      FIXME: For the moment, graphite cannot be used on loops that iterate using
     396                 :            :      induction variables that wrap.  */
     397                 :            : 
     398                 :            :   static bool can_represent_loop (loop_p loop, sese_l scop);
     399                 :            : 
     400                 :            :   /* Returns the number of pbbs that are in loops contained in SCOP.  */
     401                 :            : 
     402                 :            :   static int nb_pbbs_in_loops (scop_p scop);
     403                 :            : 
     404                 :            : private:
     405                 :            :   vec<sese_l> scops;
     406                 :            : };
     407                 :            : 
     408                 :            : sese_l scop_detection::invalid_sese (NULL, NULL);
     409                 :            : 
     410                 :            : /* Return an sese_l around the LOOP.  */
     411                 :            : 
     412                 :            : sese_l
     413                 :       1102 : scop_detection::get_sese (loop_p loop)
     414                 :            : {
     415                 :       1102 :   if (!loop)
     416                 :          0 :     return invalid_sese;
     417                 :            : 
     418                 :       1102 :   edge scop_begin = loop_preheader_edge (loop);
     419                 :       1102 :   edge scop_end = single_exit (loop);
     420                 :       1102 :   if (!scop_end || (scop_end->flags & (EDGE_COMPLEX|EDGE_FAKE)))
     421                 :        200 :     return invalid_sese;
     422                 :            : 
     423                 :        902 :   return sese_l (scop_begin, scop_end);
     424                 :            : }
     425                 :            : 
     426                 :            : /* Merge scops at same loop depth and returns the new sese.
     427                 :            :    Returns a new SESE when merge was successful, INVALID_SESE otherwise.  */
     428                 :            : 
     429                 :            : sese_l
     430                 :        125 : scop_detection::merge_sese (sese_l first, sese_l second) const
     431                 :            : {
     432                 :            :   /* In the trivial case first/second may be NULL.  */
     433                 :        125 :   if (!first)
     434                 :          0 :     return second;
     435                 :        125 :   if (!second)
     436                 :          0 :     return first;
     437                 :            : 
     438                 :        125 :   DEBUG_PRINT (dp << "[scop-detection] try merging sese s1: ";
     439                 :            :                print_sese (dump_file, first);
     440                 :            :                dp << "[scop-detection] try merging sese s2: ";
     441                 :            :                print_sese (dump_file, second));
     442                 :            : 
     443                 :        250 :   auto_bitmap worklist, in_sese_region;
     444                 :        125 :   bitmap_set_bit (worklist, get_entry_bb (first)->index);
     445                 :        125 :   bitmap_set_bit (worklist, get_exit_bb (first)->index);
     446                 :        125 :   bitmap_set_bit (worklist, get_entry_bb (second)->index);
     447                 :        125 :   bitmap_set_bit (worklist, get_exit_bb (second)->index);
     448                 :        125 :   edge entry = NULL, exit = NULL;
     449                 :            : 
     450                 :            :   /* We can optimize the case of adding a loop entry dest or exit
     451                 :            :      src to the worklist (for single-exit loops) by skipping
     452                 :            :      directly to the exit dest / entry src.  in_sese_region
     453                 :            :      doesn't have to cover all blocks in the region but merely
     454                 :            :      its border it acts more like a visited bitmap.  */
     455                 :       1517 :   do
     456                 :            :     {
     457                 :       1517 :       int index = bitmap_first_set_bit (worklist);
     458                 :       1517 :       bitmap_clear_bit (worklist, index);
     459                 :       1517 :       basic_block bb = BASIC_BLOCK_FOR_FN (cfun, index);
     460                 :       1517 :       edge_iterator ei;
     461                 :       1517 :       edge e;
     462                 :            : 
     463                 :            :       /* With fake exit edges we can end up with no possible exit.  */
     464                 :       1517 :       if (index == EXIT_BLOCK)
     465                 :            :         {
     466                 :          5 :           DEBUG_PRINT (dp << "[scop-detection-fail] cannot merge seses.\n");
     467                 :          5 :           return invalid_sese;
     468                 :            :         }
     469                 :            : 
     470                 :       1512 :       bitmap_set_bit (in_sese_region, bb->index);
     471                 :            :          
     472                 :       1512 :       basic_block dom = get_immediate_dominator (CDI_DOMINATORS, bb);
     473                 :       3511 :       FOR_EACH_EDGE (e, ei, bb->preds)
     474                 :       1999 :         if (e->src == dom
     475                 :       1999 :             && (! entry
     476                 :       1324 :                 || dominated_by_p (CDI_DOMINATORS, entry->dest, bb)))
     477                 :            :           {
     478                 :        165 :             if (entry
     479                 :        165 :                 && ! bitmap_bit_p (in_sese_region, entry->src->index))
     480                 :         30 :               bitmap_set_bit (worklist, entry->src->index);
     481                 :        165 :             entry = e;
     482                 :            :           }
     483                 :       1834 :         else if (! bitmap_bit_p (in_sese_region, e->src->index))
     484                 :        804 :           bitmap_set_bit (worklist, e->src->index);
     485                 :            : 
     486                 :       1512 :       basic_block pdom = get_immediate_dominator (CDI_POST_DOMINATORS, bb);
     487                 :       3515 :       FOR_EACH_EDGE (e, ei, bb->succs)
     488                 :       2003 :         if (e->dest == pdom
     489                 :       2003 :             && (! exit
     490                 :       1317 :                 || dominated_by_p (CDI_POST_DOMINATORS, exit->src, bb)))
     491                 :            :           {
     492                 :        291 :             if (exit
     493                 :        291 :                 && ! bitmap_bit_p (in_sese_region, exit->dest->index))
     494                 :        147 :               bitmap_set_bit (worklist, exit->dest->index);
     495                 :        291 :             exit = e;
     496                 :            :           }
     497                 :       1712 :         else if (! bitmap_bit_p (in_sese_region, e->dest->index))
     498                 :        892 :           bitmap_set_bit (worklist, e->dest->index);
     499                 :            :     }
     500                 :       1512 :   while (! bitmap_empty_p (worklist));
     501                 :            : 
     502                 :        120 :   sese_l combined (entry, exit);
     503                 :            : 
     504                 :        120 :   DEBUG_PRINT (dp << "[merged-sese] s1: "; print_sese (dump_file, combined));
     505                 :            : 
     506                 :        120 :   return combined;
     507                 :            : }
     508                 :            : 
     509                 :            : /* Build scop outer->inner if possible.  */
     510                 :            : 
     511                 :            : void
     512                 :       1215 : scop_detection::build_scop_depth (loop_p loop)
     513                 :            : {
     514                 :       1215 :   sese_l s = invalid_sese;
     515                 :       1215 :   loop = loop->inner;
     516                 :       2317 :   while (loop)
     517                 :            :     {
     518                 :       1102 :       sese_l next = get_sese (loop);
     519                 :       1102 :       if (! next
     520                 :        902 :           || harmful_loop_in_region (next))
     521                 :            :         {
     522                 :        667 :           if (s)
     523                 :         54 :             add_scop (s);
     524                 :        667 :           build_scop_depth (loop);
     525                 :        667 :           s = invalid_sese;
     526                 :            :         }
     527                 :        435 :       else if (! s)
     528                 :            :         s = next;
     529                 :            :       else
     530                 :            :         {
     531                 :        125 :           sese_l combined = merge_sese (s, next);
     532                 :        125 :           if (! combined
     533                 :        120 :               || harmful_loop_in_region (combined))
     534                 :            :             {
     535                 :         60 :               add_scop (s);
     536                 :         60 :               s = next;
     537                 :            :             }
     538                 :            :           else
     539                 :            :             s = combined;
     540                 :            :         }
     541                 :       1102 :       loop = loop->next;
     542                 :            :     }
     543                 :       1215 :   if (s)
     544                 :        256 :     add_scop (s);
     545                 :       1215 : }
     546                 :            : 
     547                 :            : /* Returns true when Graphite can represent LOOP in SCOP.
     548                 :            :    FIXME: For the moment, graphite cannot be used on loops that iterate using
     549                 :            :    induction variables that wrap.  */
     550                 :            : 
     551                 :            : bool
     552                 :       1053 : scop_detection::can_represent_loop (loop_p loop, sese_l scop)
     553                 :            : {
     554                 :       1053 :   tree niter;
     555                 :       1053 :   struct tree_niter_desc niter_desc;
     556                 :            : 
     557                 :            :   /* We can only handle do {} while () style loops correctly.  */
     558                 :       1053 :   edge exit = single_exit (loop);
     559                 :       1053 :   if (!exit
     560                 :       1052 :       || !single_pred_p (loop->latch)
     561                 :       1041 :       || exit->src != single_pred (loop->latch)
     562                 :       2089 :       || !empty_block_p (loop->latch))
     563                 :         61 :     return false;
     564                 :            : 
     565                 :        992 :   return !(loop_preheader_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP)
     566                 :        990 :     && number_of_iterations_exit (loop, single_exit (loop), &niter_desc, false)
     567                 :        974 :     && niter_desc.control.no_overflow
     568                 :        974 :     && (niter = number_of_latch_executions (loop))
     569                 :        974 :     && !chrec_contains_undetermined (niter)
     570                 :       1966 :     && graphite_can_represent_expr (scop, loop, niter);
     571                 :            : }
     572                 :            : 
     573                 :            : /* Return true when BEGIN is the preheader edge of a loop with a single exit
     574                 :            :    END.  */
     575                 :            : 
     576                 :            : bool
     577                 :        370 : scop_detection::region_has_one_loop (sese_l s)
     578                 :            : {
     579                 :        370 :   edge begin = s.entry;
     580                 :        370 :   edge end = s.exit;
     581                 :            :   /* Check for a single perfectly nested loop.  */
     582                 :        370 :   if (begin->dest->loop_father->inner)
     583                 :            :     return false;
     584                 :            : 
     585                 :            :   /* Otherwise, check whether we have adjacent loops.  */
     586                 :        220 :   return (single_pred_p (end->src)
     587                 :        220 :           && begin->dest->loop_father == single_pred (end->src)->loop_father);
     588                 :            : }
     589                 :            : 
     590                 :            : /* Add to SCOPS a scop starting at SCOP_BEGIN and ending at SCOP_END.  */
     591                 :            : 
     592                 :            : void
     593                 :        370 : scop_detection::add_scop (sese_l s)
     594                 :            : {
     595                 :        370 :   gcc_assert (s);
     596                 :            : 
     597                 :            :   /* If the exit edge is fake discard the SCoP for now as we're removing the
     598                 :            :      fake edges again after analysis.  */
     599                 :        370 :   if (s.exit->flags & EDGE_FAKE)
     600                 :            :     {
     601                 :          0 :       DEBUG_PRINT (dp << "[scop-detection-fail] Discarding infinite loop SCoP: ";
     602                 :            :                    print_sese (dump_file, s));
     603                 :          0 :       return;
     604                 :            :     }
     605                 :            : 
     606                 :            :   /* Include the BB with the loop-closed SSA PHI nodes, we need this
     607                 :            :      block in the region for code-generating out-of-SSA copies.
     608                 :            :      canonicalize_loop_closed_ssa makes sure that is in proper shape.  */
     609                 :        370 :   if (s.exit->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
     610                 :        370 :       && loop_exit_edge_p (s.exit->src->loop_father, s.exit))
     611                 :            :     {
     612                 :        369 :       gcc_assert (single_pred_p (s.exit->dest)
     613                 :            :                   && single_succ_p (s.exit->dest)
     614                 :            :                   && sese_trivially_empty_bb_p (s.exit->dest));
     615                 :        369 :       s.exit = single_succ_edge (s.exit->dest);
     616                 :            :     }
     617                 :            : 
     618                 :            :   /* Do not add scops with only one loop.  */
     619                 :        370 :   if (region_has_one_loop (s))
     620                 :            :     {
     621                 :        184 :       DEBUG_PRINT (dp << "[scop-detection-fail] Discarding one loop SCoP: ";
     622                 :            :                    print_sese (dump_file, s));
     623                 :        184 :       return;
     624                 :            :     }
     625                 :            : 
     626                 :        186 :   if (get_exit_bb (s) == EXIT_BLOCK_PTR_FOR_FN (cfun))
     627                 :            :     {
     628                 :          0 :       DEBUG_PRINT (dp << "[scop-detection-fail] "
     629                 :            :                       << "Discarding SCoP exiting to return: ";
     630                 :            :                    print_sese (dump_file, s));
     631                 :          0 :       return;
     632                 :            :     }
     633                 :            : 
     634                 :            :   /* Remove all the scops which are subsumed by s.  */
     635                 :        186 :   remove_subscops (s);
     636                 :            : 
     637                 :            :   /* Remove intersecting scops. FIXME: It will be a good idea to keep
     638                 :            :      the non-intersecting part of the scop already in the list.  */
     639                 :        186 :   remove_intersecting_scops (s);
     640                 :            : 
     641                 :        186 :   scops.safe_push (s);
     642                 :        186 :   DEBUG_PRINT (dp << "[scop-detection] Adding SCoP: "; print_sese (dump_file, s));
     643                 :            : }
     644                 :            : 
     645                 :            : /* Return true when a statement in SCOP cannot be represented by Graphite.  */
     646                 :            : 
     647                 :            : bool
     648                 :       1022 : scop_detection::harmful_loop_in_region (sese_l scop) const
     649                 :            : {
     650                 :       1022 :   basic_block exit_bb = get_exit_bb (scop);
     651                 :       1022 :   basic_block entry_bb = get_entry_bb (scop);
     652                 :            : 
     653                 :       1022 :   DEBUG_PRINT (dp << "[checking-harmful-bbs] ";
     654                 :            :                print_sese (dump_file, scop));
     655                 :       1022 :   gcc_assert (dominated_by_p (CDI_DOMINATORS, exit_bb, entry_bb));
     656                 :            : 
     657                 :       1022 :   auto_vec<basic_block> worklist;
     658                 :       2044 :   auto_bitmap loops;
     659                 :            : 
     660                 :       1022 :   worklist.safe_push (entry_bb);
     661                 :       4982 :   while (! worklist.is_empty ())
     662                 :            :     {
     663                 :       4303 :       basic_block bb = worklist.pop ();
     664                 :       4303 :       DEBUG_PRINT (dp << "Visiting bb_" << bb->index << "\n");
     665                 :            : 
     666                 :            :       /* The basic block should not be part of an irreducible loop.  */
     667                 :       4303 :       if (bb->flags & BB_IRREDUCIBLE_LOOP)
     668                 :            :         return true;
     669                 :            : 
     670                 :            :       /* Check for unstructured control flow: CFG not generated by structured
     671                 :            :          if-then-else.  */
     672                 :       4301 :       if (bb->succs->length () > 1)
     673                 :            :         {
     674                 :       1746 :           edge e;
     675                 :       1746 :           edge_iterator ei;
     676                 :       5246 :           FOR_EACH_EDGE (e, ei, bb->succs)
     677                 :       3510 :             if (!dominated_by_p (CDI_POST_DOMINATORS, bb, e->dest)
     678                 :       3510 :                 && !dominated_by_p (CDI_DOMINATORS, e->dest, bb))
     679                 :         10 :               return true;
     680                 :            :         }
     681                 :            : 
     682                 :            :       /* Collect all loops in the current region.  */
     683                 :       4291 :       loop_p loop = bb->loop_father;
     684                 :       4291 :       if (loop_in_sese_p (loop, scop))
     685                 :       4003 :         bitmap_set_bit (loops, loop->num);
     686                 :            : 
     687                 :            :       /* Check for harmful statements in basic blocks part of the region.  */
     688                 :       4291 :       for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
     689                 :      15173 :            !gsi_end_p (gsi); gsi_next (&gsi))
     690                 :      11213 :         if (!stmt_simple_for_scop_p (scop, gsi_stmt (gsi), bb))
     691                 :        331 :           return true;
     692                 :            : 
     693                 :       3960 :       for (basic_block dom = first_dom_son (CDI_DOMINATORS, bb);
     694                 :       8132 :            dom;
     695                 :       4172 :            dom = next_dom_son (CDI_DOMINATORS, dom))
     696                 :       4172 :         if (dom != scop.exit->dest)
     697                 :       3437 :           worklist.safe_push (dom);
     698                 :            :     }
     699                 :            : 
     700                 :            :   /* Go through all loops and check that they are still valid in the combined
     701                 :            :      scop.  */
     702                 :        679 :   unsigned j;
     703                 :        679 :   bitmap_iterator bi;
     704                 :       1569 :   EXECUTE_IF_SET_IN_BITMAP (loops, 0, j, bi)
     705                 :            :     {
     706                 :       1069 :       loop_p loop = (*current_loops->larray)[j];
     707                 :       1069 :       gcc_assert (loop->num == (int) j);
     708                 :            : 
     709                 :            :       /* Check if the loop nests are to be optimized for speed.  */
     710                 :       1069 :       if (! loop->inner
     711                 :       1069 :           && ! optimize_loop_for_speed_p (loop))
     712                 :            :         {
     713                 :         16 :           DEBUG_PRINT (dp << "[scop-detection-fail] loop_"
     714                 :            :                        << loop->num << " is not on a hot path.\n");
     715                 :         16 :           return true;
     716                 :            :         }
     717                 :            : 
     718                 :       1053 :       if (! can_represent_loop (loop, scop))
     719                 :            :         {
     720                 :         94 :           DEBUG_PRINT (dp << "[scop-detection-fail] cannot represent loop_"
     721                 :            :                        << loop->num << "\n");
     722                 :         94 :           return true;
     723                 :            :         }
     724                 :            : 
     725                 :            :       /* Check if all loop nests have at least one data reference.
     726                 :            :          ???  This check is expensive and loops premature at this point.
     727                 :            :          If important to retain we can pre-compute this for all innermost
     728                 :            :          loops and reject those when we build a SESE region for a loop
     729                 :            :          during SESE discovery.  */
     730                 :        959 :       if (! loop->inner
     731                 :        959 :           && ! loop_nest_has_data_refs (loop))
     732                 :            :         {
     733                 :         69 :           DEBUG_PRINT (dp << "[scop-detection-fail] loop_" << loop->num
     734                 :            :                        << "does not have any data reference.\n");
     735                 :         69 :           return true;
     736                 :            :         }
     737                 :            :     }
     738                 :            : 
     739                 :            :   return false;
     740                 :            : }
     741                 :            : 
     742                 :            : /* Returns true if S1 subsumes/surrounds S2.  */
     743                 :            : bool
     744                 :          7 : scop_detection::subsumes (sese_l s1, sese_l s2)
     745                 :            : {
     746                 :          7 :   if (dominated_by_p (CDI_DOMINATORS, get_entry_bb (s2),
     747                 :          7 :                       get_entry_bb (s1))
     748                 :          7 :       && dominated_by_p (CDI_POST_DOMINATORS, s2.exit->dest,
     749                 :          0 :                          s1.exit->dest))
     750                 :          0 :     return true;
     751                 :            :   return false;
     752                 :            : }
     753                 :            : 
     754                 :            : /* Remove a SCoP which is subsumed by S1.  */
     755                 :            : void
     756                 :        186 : scop_detection::remove_subscops (sese_l s1)
     757                 :            : {
     758                 :        186 :   int j;
     759                 :        186 :   sese_l *s2;
     760                 :        200 :   FOR_EACH_VEC_ELT_REVERSE (scops, j, s2)
     761                 :            :     {
     762                 :          7 :       if (subsumes (s1, *s2))
     763                 :            :         {
     764                 :          0 :           DEBUG_PRINT (dp << "Removing sub-SCoP";
     765                 :            :                        print_sese (dump_file, *s2));
     766                 :          7 :           scops.unordered_remove (j);
     767                 :            :         }
     768                 :            :     }
     769                 :        186 : }
     770                 :            : 
     771                 :            : /* Returns true if S1 intersects with S2.  Since we already know that S1 does
     772                 :            :    not subsume S2 or vice-versa, we only check for entry bbs.  */
     773                 :            : 
     774                 :            : bool
     775                 :          7 : scop_detection::intersects (sese_l s1, sese_l s2)
     776                 :            : {
     777                 :          7 :   if (dominated_by_p (CDI_DOMINATORS, get_entry_bb (s2),
     778                 :          7 :                       get_entry_bb (s1))
     779                 :          7 :       && !dominated_by_p (CDI_DOMINATORS, get_entry_bb (s2),
     780                 :          0 :                           get_exit_bb (s1)))
     781                 :            :     return true;
     782                 :          7 :   if ((s1.exit == s2.entry) || (s2.exit == s1.entry))
     783                 :          0 :     return true;
     784                 :            : 
     785                 :            :   return false;
     786                 :            : }
     787                 :            : 
     788                 :            : /* Remove one of the scops when it intersects with any other.  */
     789                 :            : 
     790                 :            : void
     791                 :        186 : scop_detection::remove_intersecting_scops (sese_l s1)
     792                 :            : {
     793                 :        186 :   int j;
     794                 :        186 :   sese_l *s2;
     795                 :        200 :   FOR_EACH_VEC_ELT_REVERSE (scops, j, s2)
     796                 :            :     {
     797                 :          7 :       if (intersects (s1, *s2))
     798                 :            :         {
     799                 :          0 :           DEBUG_PRINT (dp << "Removing intersecting SCoP";
     800                 :            :                        print_sese (dump_file, *s2);
     801                 :            :                        dp << "Intersects with:";
     802                 :            :                        print_sese (dump_file, s1));
     803                 :          7 :           scops.unordered_remove (j);
     804                 :            :         }
     805                 :            :     }
     806                 :        186 : }
     807                 :            : 
     808                 :            : /* Something like "n * m" is not allowed.  */
     809                 :            : 
     810                 :            : bool
     811                 :      14004 : scop_detection::graphite_can_represent_init (tree e)
     812                 :            : {
     813                 :      14136 :   switch (TREE_CODE (e))
     814                 :            :     {
     815                 :       4417 :     case POLYNOMIAL_CHREC:
     816                 :       4417 :       return graphite_can_represent_init (CHREC_LEFT (e))
     817                 :       8828 :         && graphite_can_represent_init (CHREC_RIGHT (e));
     818                 :            : 
     819                 :         18 :     case MULT_EXPR:
     820                 :         18 :       if (chrec_contains_symbols (TREE_OPERAND (e, 0)))
     821                 :         18 :         return graphite_can_represent_init (TREE_OPERAND (e, 0))
     822                 :         18 :           && tree_fits_shwi_p (TREE_OPERAND (e, 1));
     823                 :            :       else
     824                 :          0 :         return graphite_can_represent_init (TREE_OPERAND (e, 1))
     825                 :          0 :           && tree_fits_shwi_p (TREE_OPERAND (e, 0));
     826                 :            : 
     827                 :        653 :     case PLUS_EXPR:
     828                 :        653 :     case POINTER_PLUS_EXPR:
     829                 :        653 :     case MINUS_EXPR:
     830                 :        653 :       return graphite_can_represent_init (TREE_OPERAND (e, 0))
     831                 :        653 :         && graphite_can_represent_init (TREE_OPERAND (e, 1));
     832                 :            : 
     833                 :        132 :     case NEGATE_EXPR:
     834                 :        132 :     case BIT_NOT_EXPR:
     835                 :        132 :     CASE_CONVERT:
     836                 :        132 :     case NON_LVALUE_EXPR:
     837                 :        132 :       return graphite_can_represent_init (TREE_OPERAND (e, 0));
     838                 :            : 
     839                 :            :     default:
     840                 :            :       break;
     841                 :            :     }
     842                 :            : 
     843                 :            :   return true;
     844                 :            : }
     845                 :            : 
     846                 :            : /* Return true when SCEV can be represented in the polyhedral model.
     847                 :            : 
     848                 :            :    An expression can be represented, if it can be expressed as an
     849                 :            :    affine expression.  For loops (i, j) and parameters (m, n) all
     850                 :            :    affine expressions are of the form:
     851                 :            : 
     852                 :            :    x1 * i + x2 * j + x3 * m + x4 * n + x5 * 1 where x1..x5 element of Z
     853                 :            : 
     854                 :            :    1 i + 20 j + (-2) m + 25
     855                 :            : 
     856                 :            :    Something like "i * n" or "n * m" is not allowed.  */
     857                 :            : 
     858                 :            : bool
     859                 :       8288 : scop_detection::graphite_can_represent_scev (sese_l scop, tree scev)
     860                 :            : {
     861                 :      12609 :   if (chrec_contains_undetermined (scev))
     862                 :            :     return false;
     863                 :            : 
     864                 :      12465 :   switch (TREE_CODE (scev))
     865                 :            :     {
     866                 :        467 :     case NEGATE_EXPR:
     867                 :        467 :     case BIT_NOT_EXPR:
     868                 :        467 :     CASE_CONVERT:
     869                 :        467 :     case NON_LVALUE_EXPR:
     870                 :        467 :       return graphite_can_represent_scev (scop, TREE_OPERAND (scev, 0));
     871                 :            : 
     872                 :        767 :     case PLUS_EXPR:
     873                 :        767 :     case POINTER_PLUS_EXPR:
     874                 :        767 :     case MINUS_EXPR:
     875                 :        767 :       return graphite_can_represent_scev (scop, TREE_OPERAND (scev, 0))
     876                 :        767 :         && graphite_can_represent_scev (scop, TREE_OPERAND (scev, 1));
     877                 :            : 
     878                 :         11 :     case MULT_EXPR:
     879                 :         13 :       return !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev, 0)))
     880                 :          2 :         && !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev, 1)))
     881                 :          4 :         && !(chrec_contains_symbols (TREE_OPERAND (scev, 0))
     882                 :          2 :              && chrec_contains_symbols (TREE_OPERAND (scev, 1)))
     883                 :          2 :         && graphite_can_represent_init (scev)
     884                 :          2 :         && graphite_can_represent_scev (scop, TREE_OPERAND (scev, 0))
     885                 :         13 :         && graphite_can_represent_scev (scop, TREE_OPERAND (scev, 1));
     886                 :            : 
     887                 :       3928 :     case POLYNOMIAL_CHREC:
     888                 :            :       /* Check for constant strides.  With a non constant stride of
     889                 :            :          'n' we would have a value of 'iv * n'.  Also check that the
     890                 :            :          initial value can represented: for example 'n * m' cannot be
     891                 :            :          represented.  */
     892                 :       3928 :       gcc_assert (loop_in_sese_p (get_loop (cfun,
     893                 :            :                                             CHREC_VARIABLE (scev)), scop));
     894                 :       3928 :       if (!evolution_function_right_is_integer_cst (scev)
     895                 :       3928 :           || !graphite_can_represent_init (scev))
     896                 :         74 :         return false;
     897                 :       3854 :       return graphite_can_represent_scev (scop, CHREC_LEFT (scev));
     898                 :            : 
     899                 :            :     case ADDR_EXPR:
     900                 :            :       /* We cannot encode addresses for ISL.  */
     901                 :            :       return false;
     902                 :            : 
     903                 :       7292 :     default:
     904                 :       7292 :       break;
     905                 :            :     }
     906                 :            : 
     907                 :            :   /* Only affine functions can be represented.  */
     908                 :       7292 :   if (tree_contains_chrecs (scev, NULL) || !scev_is_linear_expression (scev))
     909                 :          3 :     return false;
     910                 :            : 
     911                 :            :   return true;
     912                 :            : }
     913                 :            : 
     914                 :            : /* Return true when EXPR can be represented in the polyhedral model.
     915                 :            : 
     916                 :            :    This means an expression can be represented, if it is linear with respect to
     917                 :            :    the loops and the strides are non parametric.  LOOP is the place where the
     918                 :            :    expr will be evaluated.  SCOP defines the region we analyse.  */
     919                 :            : 
     920                 :            : bool
     921                 :       4045 : scop_detection::graphite_can_represent_expr (sese_l scop, loop_p loop,
     922                 :            :                                              tree expr)
     923                 :            : {
     924                 :        974 :   tree scev = cached_scalar_evolution_in_region (scop, loop, expr);
     925                 :       4045 :   return graphite_can_represent_scev (scop, scev);
     926                 :            : }
     927                 :            : 
     928                 :            : /* Return true if the data references of STMT can be represented by Graphite.
     929                 :            :    We try to analyze the data references in a loop contained in the SCOP.  */
     930                 :            : 
     931                 :            : bool
     932                 :      10941 : scop_detection::stmt_has_simple_data_refs_p (sese_l scop, gimple *stmt)
     933                 :            : {
     934                 :      10941 :   edge nest = scop.entry;
     935                 :      10941 :   loop_p loop = loop_containing_stmt (stmt);
     936                 :      10941 :   if (!loop_in_sese_p (loop, scop))
     937                 :        162 :     loop = NULL;
     938                 :            : 
     939                 :      10941 :   auto_vec<data_reference_p> drs;
     940                 :      10941 :   if (! graphite_find_data_references_in_stmt (nest, loop, stmt, &drs))
     941                 :            :     return false;
     942                 :            : 
     943                 :            :   int j;
     944                 :            :   data_reference_p dr;
     945                 :      17348 :   FOR_EACH_VEC_ELT (drs, j, dr)
     946                 :            :     {
     947                 :       9445 :       for (unsigned i = 0; i < DR_NUM_DIMENSIONS (dr); ++i)
     948                 :       2715 :         if (! graphite_can_represent_scev (scop, DR_ACCESS_FN (dr, i)))
     949                 :            :           return false;
     950                 :            :     }
     951                 :            : 
     952                 :            :   return true;
     953                 :            : }
     954                 :            : 
     955                 :            : /* GIMPLE_ASM and GIMPLE_CALL may embed arbitrary side effects.
     956                 :            :    Calls have side-effects, except those to const or pure
     957                 :            :    functions.  */
     958                 :            : 
     959                 :            : static bool
     960                 :      11032 : stmt_has_side_effects (gimple *stmt)
     961                 :            : {
     962                 :      20433 :   if (gimple_has_volatile_ops (stmt)
     963                 :      11012 :       || (gimple_code (stmt) == GIMPLE_CALL
     964                 :        100 :           && !(gimple_call_flags (stmt) & (ECF_CONST | ECF_PURE)))
     965                 :      20362 :       || (gimple_code (stmt) == GIMPLE_ASM))
     966                 :            :     {
     967                 :         91 :       DEBUG_PRINT (dp << "[scop-detection-fail] "
     968                 :            :                       << "Statement has side-effects:\n";
     969                 :            :         print_gimple_stmt (dump_file, stmt, 0, TDF_VOPS | TDF_MEMSYMS));
     970                 :         91 :       return true;
     971                 :            :     }
     972                 :            :   return false;
     973                 :            : }
     974                 :            : 
     975                 :            : /* Return true only when STMT is simple enough for being handled by Graphite.
     976                 :            :    This depends on SCOP, as the parameters are initialized relatively to
     977                 :            :    this basic block, the linear functions are initialized based on the outermost
     978                 :            :    loop containing STMT inside the SCOP.  BB is the place where we try to
     979                 :            :    evaluate the STMT.  */
     980                 :            : 
     981                 :            : bool
     982                 :      11213 : scop_detection::stmt_simple_for_scop_p (sese_l scop, gimple *stmt,
     983                 :            :                                         basic_block bb) const
     984                 :            : {
     985                 :      11213 :   gcc_assert (scop);
     986                 :            : 
     987                 :      11213 :   if (is_gimple_debug (stmt))
     988                 :            :     return true;
     989                 :            : 
     990                 :      11032 :   if (stmt_has_side_effects (stmt))
     991                 :            :     return false;
     992                 :            : 
     993                 :      10941 :   if (!stmt_has_simple_data_refs_p (scop, stmt))
     994                 :            :     {
     995                 :        105 :       DEBUG_PRINT (dp << "[scop-detection-fail] "
     996                 :            :                       << "Graphite cannot handle data-refs in stmt:\n";
     997                 :            :         print_gimple_stmt (dump_file, stmt, 0, TDF_VOPS|TDF_MEMSYMS););
     998                 :        105 :       return false;
     999                 :            :     }
    1000                 :            : 
    1001                 :      10836 :   switch (gimple_code (stmt))
    1002                 :            :     {
    1003                 :            :     case GIMPLE_LABEL:
    1004                 :            :       return true;
    1005                 :            : 
    1006                 :       1597 :     case GIMPLE_COND:
    1007                 :       1597 :       {
    1008                 :            :         /* We can handle all binary comparisons.  Inequalities are
    1009                 :            :            also supported as they can be represented with union of
    1010                 :            :            polyhedra.  */
    1011                 :       1597 :         enum tree_code code = gimple_cond_code (stmt);
    1012                 :       1004 :         if (!(code == LT_EXPR
    1013                 :       1597 :               || code == GT_EXPR
    1014                 :       1168 :               || code == LE_EXPR
    1015                 :       1168 :               || code == GE_EXPR
    1016                 :            :               || code == EQ_EXPR
    1017                 :            :               || code == NE_EXPR))
    1018                 :            :           {
    1019                 :          0 :             DEBUG_PRINT (dp << "[scop-detection-fail] "
    1020                 :            :                             << "Graphite cannot handle cond stmt:\n";
    1021                 :            :                          print_gimple_stmt (dump_file, stmt, 0,
    1022                 :            :                                             TDF_VOPS | TDF_MEMSYMS));
    1023                 :          0 :             return false;
    1024                 :            :           }
    1025                 :            : 
    1026                 :       1597 :         loop_p loop = bb->loop_father;
    1027                 :       4541 :         for (unsigned i = 0; i < 2; ++i)
    1028                 :            :           {
    1029                 :       3071 :             tree op = gimple_op (stmt, i);
    1030                 :       3071 :             if (!graphite_can_represent_expr (scop, loop, op)
    1031                 :            :                 /* We can only constrain on integer type.  */
    1032                 :       6027 :                 || ! INTEGRAL_TYPE_P (TREE_TYPE (op)))
    1033                 :            :               {
    1034                 :        127 :                 DEBUG_PRINT (dp << "[scop-detection-fail] "
    1035                 :            :                                 << "Graphite cannot represent stmt:\n";
    1036                 :            :                              print_gimple_stmt (dump_file, stmt, 0,
    1037                 :            :                                                 TDF_VOPS | TDF_MEMSYMS));
    1038                 :        127 :                 return false;
    1039                 :            :               }
    1040                 :            :           }
    1041                 :            : 
    1042                 :            :         return true;
    1043                 :            :       }
    1044                 :            : 
    1045                 :       9223 :     case GIMPLE_ASSIGN:
    1046                 :       9223 :     case GIMPLE_CALL:
    1047                 :       9223 :       {
    1048                 :       9223 :         tree op, lhs = gimple_get_lhs (stmt);
    1049                 :       9223 :         ssa_op_iter i;
    1050                 :            :         /* If we are not going to instantiate the stmt do not require
    1051                 :            :            its operands to be instantiatable at this point.  */
    1052                 :       9223 :         if (lhs
    1053                 :       9223 :             && TREE_CODE (lhs) == SSA_NAME
    1054                 :      17521 :             && scev_analyzable_p (lhs, scop))
    1055                 :            :           return true;
    1056                 :            :         /* Verify that if we can analyze operands at their def site we
    1057                 :            :            also can represent them when analyzed at their uses.  */
    1058                 :      10277 :         FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_USE)
    1059                 :       6445 :           if (scev_analyzable_p (op, scop)
    1060                 :       9761 :               && chrec_contains_undetermined
    1061                 :       3316 :                    (cached_scalar_evolution_in_region (scop,
    1062                 :            :                                                        bb->loop_father, op)))
    1063                 :            :             {
    1064                 :          1 :               DEBUG_PRINT (dp << "[scop-detection-fail] "
    1065                 :            :                            << "Graphite cannot code-gen stmt:\n";
    1066                 :            :                            print_gimple_stmt (dump_file, stmt, 0,
    1067                 :            :                                               TDF_VOPS | TDF_MEMSYMS));
    1068                 :          1 :               return false;
    1069                 :            :             }
    1070                 :            :         return true;
    1071                 :            :       }
    1072                 :            : 
    1073                 :          7 :     default:
    1074                 :            :       /* These nodes cut a new scope.  */
    1075                 :          7 :       DEBUG_PRINT (
    1076                 :            :           dp << "[scop-detection-fail] "
    1077                 :            :              << "Gimple stmt not handled in Graphite:\n";
    1078                 :            :           print_gimple_stmt (dump_file, stmt, 0, TDF_VOPS | TDF_MEMSYMS));
    1079                 :            :       return false;
    1080                 :            :     }
    1081                 :            : }
    1082                 :            : 
    1083                 :            : /* Returns the number of pbbs that are in loops contained in SCOP.  */
    1084                 :            : 
    1085                 :            : int
    1086                 :        176 : scop_detection::nb_pbbs_in_loops (scop_p scop)
    1087                 :            : {
    1088                 :        176 :   int i;
    1089                 :        176 :   poly_bb_p pbb;
    1090                 :        176 :   int res = 0;
    1091                 :            : 
    1092                 :        719 :   FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
    1093                 :        543 :     if (loop_in_sese_p (gbb_loop (PBB_BLACK_BOX (pbb)), scop->scop_info->region))
    1094                 :        472 :       res++;
    1095                 :            : 
    1096                 :        176 :   return res;
    1097                 :            : }
    1098                 :            : 
    1099                 :            : /* Assigns the parameter NAME an index in REGION.  */
    1100                 :            : 
    1101                 :            : static void
    1102                 :        270 : assign_parameter_index_in_region (tree name, sese_info_p region)
    1103                 :            : {
    1104                 :        270 :   gcc_assert (TREE_CODE (name) == SSA_NAME
    1105                 :            :               && ! defined_in_sese_p (name, region->region));
    1106                 :            :   int i;
    1107                 :            :   tree p;
    1108                 :        441 :   FOR_EACH_VEC_ELT (region->params, i, p)
    1109                 :        308 :     if (p == name)
    1110                 :        270 :       return;
    1111                 :            : 
    1112                 :        133 :   region->params.safe_push (name);
    1113                 :            : }
    1114                 :            : 
    1115                 :            : /* In the context of sese S, scan the expression E and translate it to
    1116                 :            :    a linear expression C.  When parsing a symbolic multiplication, K
    1117                 :            :    represents the constant multiplier of an expression containing
    1118                 :            :    parameters.  */
    1119                 :            : 
    1120                 :            : static void
    1121                 :       1274 : scan_tree_for_params (sese_info_p s, tree e)
    1122                 :            : {
    1123                 :       2529 :   if (e == chrec_dont_know)
    1124                 :            :     return;
    1125                 :            : 
    1126                 :       2529 :   switch (TREE_CODE (e))
    1127                 :            :     {
    1128                 :        956 :     case POLYNOMIAL_CHREC:
    1129                 :        956 :       scan_tree_for_params (s, CHREC_LEFT (e));
    1130                 :        956 :       break;
    1131                 :            : 
    1132                 :          0 :     case MULT_EXPR:
    1133                 :          0 :       if (chrec_contains_symbols (TREE_OPERAND (e, 0)))
    1134                 :          0 :         scan_tree_for_params (s, TREE_OPERAND (e, 0));
    1135                 :            :       else
    1136                 :          0 :         scan_tree_for_params (s, TREE_OPERAND (e, 1));
    1137                 :            :       break;
    1138                 :            : 
    1139                 :        156 :     case PLUS_EXPR:
    1140                 :        156 :     case POINTER_PLUS_EXPR:
    1141                 :        156 :     case MINUS_EXPR:
    1142                 :        156 :       scan_tree_for_params (s, TREE_OPERAND (e, 0));
    1143                 :        156 :       scan_tree_for_params (s, TREE_OPERAND (e, 1));
    1144                 :        156 :       break;
    1145                 :            : 
    1146                 :        143 :     case NEGATE_EXPR:
    1147                 :        143 :     case BIT_NOT_EXPR:
    1148                 :        143 :     CASE_CONVERT:
    1149                 :        143 :     case NON_LVALUE_EXPR:
    1150                 :        143 :       scan_tree_for_params (s, TREE_OPERAND (e, 0));
    1151                 :        143 :       break;
    1152                 :            : 
    1153                 :        270 :     case SSA_NAME:
    1154                 :        270 :       assign_parameter_index_in_region (e, s);
    1155                 :        270 :       break;
    1156                 :            : 
    1157                 :            :     case INTEGER_CST:
    1158                 :            :     case ADDR_EXPR:
    1159                 :            :     case REAL_CST:
    1160                 :            :     case COMPLEX_CST:
    1161                 :            :     case VECTOR_CST:
    1162                 :            :       break;
    1163                 :            : 
    1164                 :          0 :    default:
    1165                 :          0 :       gcc_unreachable ();
    1166                 :       1274 :       break;
    1167                 :            :     }
    1168                 :            : }
    1169                 :            : 
    1170                 :            : /* Find parameters with respect to REGION in BB. We are looking in memory
    1171                 :            :    access functions, conditions and loop bounds.  */
    1172                 :            : 
    1173                 :            : static void
    1174                 :        543 : find_params_in_bb (sese_info_p region, gimple_poly_bb_p gbb)
    1175                 :            : {
    1176                 :            :   /* Find parameters in the access functions of data references.  */
    1177                 :        543 :   int i;
    1178                 :        543 :   data_reference_p dr;
    1179                 :       1789 :   FOR_EACH_VEC_ELT (GBB_DATA_REFS (gbb), i, dr)
    1180                 :       3017 :     for (unsigned j = 0; j < DR_NUM_DIMENSIONS (dr); j++)
    1181                 :        889 :       scan_tree_for_params (region, DR_ACCESS_FN (dr, j));
    1182                 :            : 
    1183                 :            :   /* Find parameters in conditional statements.  */
    1184                 :            :   gimple *stmt;
    1185                 :        598 :   FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb), i, stmt)
    1186                 :            :     {
    1187                 :         55 :       loop_p loop = gimple_bb (stmt)->loop_father;
    1188                 :         55 :       tree lhs = cached_scalar_evolution_in_region (region->region, loop,
    1189                 :            :                                                     gimple_cond_lhs (stmt));
    1190                 :         55 :       tree rhs = cached_scalar_evolution_in_region (region->region, loop,
    1191                 :            :                                                     gimple_cond_rhs (stmt));
    1192                 :         55 :       gcc_assert (!chrec_contains_undetermined (lhs)
    1193                 :            :                   && !chrec_contains_undetermined (rhs));
    1194                 :            : 
    1195                 :         55 :       scan_tree_for_params (region, lhs);
    1196                 :         55 :       scan_tree_for_params (region, rhs);
    1197                 :            :     }
    1198                 :        543 : }
    1199                 :            : 
    1200                 :            : /* Record the parameters used in the SCOP BBs.  A variable is a parameter
    1201                 :            :    in a scop if it does not vary during the execution of that scop.  */
    1202                 :            : 
    1203                 :            : static void
    1204                 :        176 : find_scop_parameters (scop_p scop)
    1205                 :            : {
    1206                 :        176 :   unsigned i;
    1207                 :        176 :   sese_info_p region = scop->scop_info;
    1208                 :            : 
    1209                 :            :   /* Parameters used in loop bounds are processed during gather_bbs.  */
    1210                 :            : 
    1211                 :            :   /* Find the parameters used in data accesses.  */
    1212                 :        176 :   poly_bb_p pbb;
    1213                 :        719 :   FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
    1214                 :        543 :     find_params_in_bb (region, PBB_BLACK_BOX (pbb));
    1215                 :            : 
    1216                 :        176 :   int nbp = sese_nb_params (region);
    1217                 :        176 :   scop_set_nb_params (scop, nbp);
    1218                 :        176 : }
    1219                 :            : 
    1220                 :            : static void
    1221                 :        702 : add_write (vec<tree> *writes, tree def)
    1222                 :            : {
    1223                 :        702 :   writes->safe_push (def);
    1224                 :        702 :   DEBUG_PRINT (dp << "Adding scalar write: ";
    1225                 :            :                print_generic_expr (dump_file, def);
    1226                 :            :                dp << "\nFrom stmt: ";
    1227                 :            :                print_gimple_stmt (dump_file,
    1228                 :            :                                   SSA_NAME_DEF_STMT (def), 0));
    1229                 :        702 : }
    1230                 :            : 
    1231                 :            : static void
    1232                 :        538 : add_read (vec<scalar_use> *reads, tree use, gimple *use_stmt)
    1233                 :            : {
    1234                 :        538 :   DEBUG_PRINT (dp << "Adding scalar read: ";
    1235                 :            :                print_generic_expr (dump_file, use);
    1236                 :            :                dp << "\nFrom stmt: ";
    1237                 :            :                print_gimple_stmt (dump_file, use_stmt, 0));
    1238                 :        538 :   reads->safe_push (std::make_pair (use_stmt, use));
    1239                 :        538 : }
    1240                 :            : 
    1241                 :            : 
    1242                 :            : /* Record DEF if it is used in other bbs different than DEF_BB in the SCOP.  */
    1243                 :            : 
    1244                 :            : static void
    1245                 :       2685 : build_cross_bb_scalars_def (scop_p scop, tree def, basic_block def_bb,
    1246                 :            :                              vec<tree> *writes)
    1247                 :            : {
    1248                 :       2685 :   if (!is_gimple_reg (def))
    1249                 :        326 :     return;
    1250                 :            : 
    1251                 :       2359 :   bool scev_analyzable = scev_analyzable_p (def, scop->scop_info->region);
    1252                 :            : 
    1253                 :       2359 :   gimple *use_stmt;
    1254                 :       2359 :   imm_use_iterator imm_iter;
    1255                 :       5425 :   FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def)
    1256                 :            :     /* Do not gather scalar variables that can be analyzed by SCEV as they can
    1257                 :            :        be generated out of the induction variables.  */
    1258                 :       3189 :     if ((! scev_analyzable
    1259                 :            :          /* But gather SESE liveouts as we otherwise fail to rewrite their
    1260                 :            :             exit PHIs.  */
    1261                 :       2347 :          || ! bb_in_sese_p (gimple_bb (use_stmt), scop->scop_info->region))
    1262                 :       3191 :         && (def_bb != gimple_bb (use_stmt) && !is_gimple_debug (use_stmt)))
    1263                 :            :       {
    1264                 :        123 :         add_write (writes, def);
    1265                 :            :         /* This is required by the FOR_EACH_IMM_USE_STMT when we want to break
    1266                 :            :            before all the uses have been visited.  */
    1267                 :       5548 :         BREAK_FROM_IMM_USE_STMT (imm_iter);
    1268                 :            :       }
    1269                 :            : }
    1270                 :            : 
    1271                 :            : /* Record USE if it is defined in other bbs different than USE_STMT
    1272                 :            :    in the SCOP.  */
    1273                 :            : 
    1274                 :            : static void
    1275                 :       4369 : build_cross_bb_scalars_use (scop_p scop, tree use, gimple *use_stmt,
    1276                 :            :                             vec<scalar_use> *reads)
    1277                 :            : {
    1278                 :       4369 :   if (!is_gimple_reg (use))
    1279                 :            :     return;
    1280                 :            : 
    1281                 :            :   /* Do not gather scalar variables that can be analyzed by SCEV as they can be
    1282                 :            :      generated out of the induction variables.  */
    1283                 :       4369 :   if (scev_analyzable_p (use, scop->scop_info->region))
    1284                 :            :     return;
    1285                 :            : 
    1286                 :        827 :   gimple *def_stmt = SSA_NAME_DEF_STMT (use);
    1287                 :        827 :   if (gimple_bb (def_stmt) != gimple_bb (use_stmt))
    1288                 :         74 :     add_read (reads, use, use_stmt);
    1289                 :            : }
    1290                 :            : 
    1291                 :            : /* Generates a polyhedral black box only if the bb contains interesting
    1292                 :            :    information.  */
    1293                 :            : 
    1294                 :            : static gimple_poly_bb_p
    1295                 :       1814 : try_generate_gimple_bb (scop_p scop, basic_block bb)
    1296                 :            : {
    1297                 :       1814 :   vec<data_reference_p> drs = vNULL;
    1298                 :       1814 :   vec<tree> writes = vNULL;
    1299                 :       1814 :   vec<scalar_use> reads = vNULL;
    1300                 :            : 
    1301                 :       1814 :   sese_l region = scop->scop_info->region;
    1302                 :       1814 :   edge nest = region.entry;
    1303                 :       1814 :   loop_p loop = bb->loop_father;
    1304                 :       1814 :   if (!loop_in_sese_p (loop, region))
    1305                 :        322 :     loop = NULL;
    1306                 :            : 
    1307                 :       6903 :   for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
    1308                 :       3275 :        gsi_next (&gsi))
    1309                 :            :     {
    1310                 :       3275 :       gimple *stmt = gsi_stmt (gsi);
    1311                 :       3275 :       if (is_gimple_debug (stmt))
    1312                 :         73 :         continue;
    1313                 :            : 
    1314                 :       3202 :       graphite_find_data_references_in_stmt (nest, loop, stmt, &drs);
    1315                 :            : 
    1316                 :       3202 :       tree def = gimple_get_lhs (stmt);
    1317                 :       3202 :       if (def)
    1318                 :       2685 :         build_cross_bb_scalars_def (scop, def, gimple_bb (stmt), &writes);
    1319                 :            : 
    1320                 :       3202 :       ssa_op_iter iter;
    1321                 :       3202 :       tree use;
    1322                 :       7571 :       FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
    1323                 :       4369 :         build_cross_bb_scalars_use (scop, use, stmt, &reads);
    1324                 :            :     }
    1325                 :            : 
    1326                 :            :   /* Handle defs and uses in PHIs.  Those need special treatment given
    1327                 :            :      that we have to present ISL with sth that looks like we've rewritten
    1328                 :            :      the IL out-of-SSA.  */
    1329                 :       3397 :   for (gphi_iterator psi = gsi_start_phis (bb); !gsi_end_p (psi);
    1330                 :       1583 :        gsi_next (&psi))
    1331                 :            :     {
    1332                 :       1583 :       gphi *phi = psi.phi ();
    1333                 :       1583 :       tree res = gimple_phi_result (phi);
    1334                 :       1583 :       if (virtual_operand_p (res)
    1335                 :       1583 :           || scev_analyzable_p (res, scop->scop_info->region))
    1336                 :       1336 :         continue;
    1337                 :            :       /* To simulate out-of-SSA the block containing the PHI node has
    1338                 :            :          reads of the PHI destination.  And to preserve SSA dependences
    1339                 :            :          we also write to it (the out-of-SSA decl and the SSA result
    1340                 :            :          are coalesced for dependence purposes which is good enough).  */
    1341                 :        247 :       add_read (&reads, res, phi);
    1342                 :        247 :       add_write (&writes, res);
    1343                 :            :     }
    1344                 :       1814 :   basic_block bb_for_succs = bb;
    1345                 :       1814 :   if (bb_for_succs == bb_for_succs->loop_father->latch
    1346                 :        474 :       && bb_in_sese_p (bb_for_succs, scop->scop_info->region)
    1347                 :       2288 :       && sese_trivially_empty_bb_p (bb_for_succs))
    1348                 :            :     bb_for_succs = NULL;
    1349                 :       3628 :   while (bb_for_succs)
    1350                 :            :     {
    1351                 :       1814 :       basic_block latch = NULL;
    1352                 :       1814 :       edge_iterator ei;
    1353                 :       1814 :       edge e;
    1354                 :       4145 :       FOR_EACH_EDGE (e, ei, bb_for_succs->succs)
    1355                 :            :         {
    1356                 :       4831 :           for (gphi_iterator psi = gsi_start_phis (e->dest); !gsi_end_p (psi);
    1357                 :       2500 :                gsi_next (&psi))
    1358                 :            :             {
    1359                 :       2500 :               gphi *phi = psi.phi ();
    1360                 :       2500 :               tree res = gimple_phi_result (phi);
    1361                 :       5000 :               if (virtual_operand_p (res))
    1362                 :        791 :                 continue;
    1363                 :            :               /* To simulate out-of-SSA the predecessor of edges into PHI nodes
    1364                 :            :                  has a copy from the PHI argument to the PHI destination.  */
    1365                 :       1709 :               if (! scev_analyzable_p (res, scop->scop_info->region))
    1366                 :        332 :                 add_write (&writes, res);
    1367                 :       1709 :               tree use = PHI_ARG_DEF_FROM_EDGE (phi, e);
    1368                 :       1709 :               if (TREE_CODE (use) == SSA_NAME
    1369                 :       1182 :                   && ! SSA_NAME_IS_DEFAULT_DEF (use)
    1370                 :       1182 :                   && gimple_bb (SSA_NAME_DEF_STMT (use)) != bb_for_succs
    1371                 :       2739 :                   && ! scev_analyzable_p (use, scop->scop_info->region))
    1372                 :        165 :                 add_read (&reads, use, phi);
    1373                 :            :             }
    1374                 :       2331 :           if (e->dest == bb_for_succs->loop_father->latch
    1375                 :        475 :               && bb_in_sese_p (e->dest, scop->scop_info->region)
    1376                 :       2805 :               && sese_trivially_empty_bb_p (e->dest))
    1377                 :        474 :             latch = e->dest;
    1378                 :            :         }
    1379                 :            :       /* Handle empty latch block PHIs here, otherwise we confuse ISL
    1380                 :            :          with extra conditional code where it then peels off the last
    1381                 :            :          iteration just because of that.  It would be simplest if we
    1382                 :            :          just didn't force simple latches (thus remove the forwarder).  */
    1383                 :       1814 :       bb_for_succs = latch;
    1384                 :            :     }
    1385                 :            : 
    1386                 :            :   /* For the region exit block add reads for all live-out vars.  */
    1387                 :       1814 :   if (bb == scop->scop_info->region.exit->src)
    1388                 :            :     {
    1389                 :        186 :       sese_build_liveouts (scop->scop_info);
    1390                 :        186 :       unsigned i;
    1391                 :        186 :       bitmap_iterator bi;
    1392                 :        238 :       EXECUTE_IF_SET_IN_BITMAP (scop->scop_info->liveout, 0, i, bi)
    1393                 :            :         {
    1394                 :         52 :           tree use = ssa_name (i);
    1395                 :         52 :           add_read (&reads, use, NULL);
    1396                 :            :         }
    1397                 :            :     }
    1398                 :            : 
    1399                 :       1814 :   if (drs.is_empty () && writes.is_empty () && reads.is_empty ())
    1400                 :            :     return NULL;
    1401                 :            : 
    1402                 :        578 :   return new_gimple_poly_bb (bb, drs, reads, writes);
    1403                 :            : }
    1404                 :            : 
    1405                 :            : /* Compute alias-sets for all data references in DRS.  */
    1406                 :            : 
    1407                 :            : static bool 
    1408                 :        186 : build_alias_set (scop_p scop)
    1409                 :            : {
    1410                 :        186 :   int num_vertices = scop->drs.length ();
    1411                 :        186 :   struct graph *g = new_graph (num_vertices);
    1412                 :        186 :   dr_info *dr1, *dr2;
    1413                 :        186 :   int i, j;
    1414                 :        186 :   int *all_vertices;
    1415                 :            : 
    1416                 :        186 :   struct loop *nest
    1417                 :        186 :     = find_common_loop (scop->scop_info->region.entry->dest->loop_father,
    1418                 :        186 :                         scop->scop_info->region.exit->src->loop_father);
    1419                 :            : 
    1420                 :        186 :   FOR_EACH_VEC_ELT (scop->drs, i, dr1)
    1421                 :       3531 :     for (j = i+1; scop->drs.iterate (j, &dr2); j++)
    1422                 :       2099 :       if (dr_may_alias_p (dr1->dr, dr2->dr, nest))
    1423                 :            :         {
    1424                 :            :           /* Dependences in the same alias set need to be handled
    1425                 :            :              by just looking at DR_ACCESS_FNs.  */
    1426                 :       1496 :           if (DR_NUM_DIMENSIONS (dr1->dr) == 0
    1427                 :       2988 :               || DR_NUM_DIMENSIONS (dr1->dr) != DR_NUM_DIMENSIONS (dr2->dr)
    1428                 :       1492 :               || ! operand_equal_p (DR_BASE_OBJECT (dr1->dr),
    1429                 :       1492 :                                     DR_BASE_OBJECT (dr2->dr),
    1430                 :            :                                     OEP_ADDRESS_OF)
    1431                 :       2980 :               || ! types_compatible_p (TREE_TYPE (DR_BASE_OBJECT (dr1->dr)),
    1432                 :       1486 :                                        TREE_TYPE (DR_BASE_OBJECT (dr2->dr))))
    1433                 :            :             {
    1434                 :         10 :               free_graph (g);
    1435                 :         10 :               return false;
    1436                 :            :             }
    1437                 :       1486 :           add_edge (g, i, j);
    1438                 :       1486 :           add_edge (g, j, i);
    1439                 :            :         }
    1440                 :            : 
    1441                 :        176 :   all_vertices = XNEWVEC (int, num_vertices);
    1442                 :        799 :   for (i = 0; i < num_vertices; i++)
    1443                 :        623 :     all_vertices[i] = i;
    1444                 :            : 
    1445                 :        176 :   scop->max_alias_set
    1446                 :        176 :     = graphds_dfs (g, all_vertices, num_vertices, NULL, true, NULL) + 1;
    1447                 :        176 :   free (all_vertices);
    1448                 :            : 
    1449                 :        799 :   for (i = 0; i < g->n_vertices; i++)
    1450                 :        623 :     scop->drs[i].alias_set = g->vertices[i].component + 1;
    1451                 :            : 
    1452                 :        176 :   free_graph (g);
    1453                 :        176 :   return true;
    1454                 :            : }
    1455                 :            : 
    1456                 :            : /* Gather BBs and conditions for a SCOP.  */
    1457                 :            : class gather_bbs : public dom_walker
    1458                 :            : {
    1459                 :            : public:
    1460                 :            :   gather_bbs (cdi_direction, scop_p, int *);
    1461                 :            : 
    1462                 :            :   virtual edge before_dom_children (basic_block);
    1463                 :            :   virtual void after_dom_children (basic_block);
    1464                 :            : 
    1465                 :            : private:
    1466                 :            :   auto_vec<gimple *, 3> conditions, cases;
    1467                 :            :   scop_p scop;
    1468                 :            : };
    1469                 :            : }
    1470                 :        186 : gather_bbs::gather_bbs (cdi_direction direction, scop_p scop, int *bb_to_rpo)
    1471                 :        186 :   : dom_walker (direction, ALL_BLOCKS, bb_to_rpo), scop (scop)
    1472                 :            : {
    1473                 :          0 : }
    1474                 :            : 
    1475                 :            : /* Call-back for dom_walk executed before visiting the dominated
    1476                 :            :    blocks.  */
    1477                 :            : 
    1478                 :            : edge
    1479                 :       1979 : gather_bbs::before_dom_children (basic_block bb)
    1480                 :            : {
    1481                 :       1979 :   sese_info_p region = scop->scop_info;
    1482                 :       1979 :   if (!bb_in_sese_p (bb, region->region))
    1483                 :        165 :     return dom_walker::STOP;
    1484                 :            : 
    1485                 :            :   /* For loops fully contained in the region record parameters in the
    1486                 :            :      loop bounds.  */
    1487                 :       1814 :   loop_p loop = bb->loop_father;
    1488                 :       1814 :   if (loop->header == bb
    1489                 :       1814 :       && loop_in_sese_p (loop, region->region))
    1490                 :            :     {
    1491                 :        474 :       tree nb_iters = number_of_latch_executions (loop);
    1492                 :        474 :       if (chrec_contains_symbols (nb_iters))
    1493                 :            :         {
    1494                 :        119 :           nb_iters = cached_scalar_evolution_in_region (region->region,
    1495                 :            :                                                         loop, nb_iters);
    1496                 :        119 :           scan_tree_for_params (region, nb_iters);
    1497                 :            :         }
    1498                 :            :     }
    1499                 :            : 
    1500                 :       1814 :   if (gcond *stmt = single_pred_cond_non_loop_exit (bb))
    1501                 :            :     {
    1502                 :        541 :       edge e = single_pred_edge (bb);
    1503                 :            :       /* Make sure the condition is in the region and thus was verified
    1504                 :            :          to be handled.  */
    1505                 :        541 :       if (e != region->region.entry)
    1506                 :            :         {
    1507                 :        541 :           conditions.safe_push (stmt);
    1508                 :        541 :           if (e->flags & EDGE_TRUE_VALUE)
    1509                 :        404 :             cases.safe_push (stmt);
    1510                 :            :           else
    1511                 :        137 :             cases.safe_push (NULL);
    1512                 :            :         }
    1513                 :            :     }
    1514                 :            : 
    1515                 :       1814 :   scop->scop_info->bbs.safe_push (bb);
    1516                 :            : 
    1517                 :       1814 :   gimple_poly_bb_p gbb = try_generate_gimple_bb (scop, bb);
    1518                 :       1814 :   if (!gbb)
    1519                 :            :     return NULL;
    1520                 :            : 
    1521                 :        578 :   GBB_CONDITIONS (gbb) = conditions.copy ();
    1522                 :        578 :   GBB_CONDITION_CASES (gbb) = cases.copy ();
    1523                 :            : 
    1524                 :        578 :   poly_bb_p pbb = new_poly_bb (scop, gbb);
    1525                 :        578 :   scop->pbbs.safe_push (pbb);
    1526                 :            : 
    1527                 :        578 :   int i;
    1528                 :        578 :   data_reference_p dr;
    1529                 :       1268 :   FOR_EACH_VEC_ELT (gbb->data_refs, i, dr)
    1530                 :            :     {
    1531                 :       1050 :       DEBUG_PRINT (dp << "Adding memory ";
    1532                 :            :                    if (dr->is_read)
    1533                 :            :                      dp << "read: ";
    1534                 :            :                    else
    1535                 :            :                      dp << "write: ";
    1536                 :            :                    print_generic_expr (dump_file, dr->ref);
    1537                 :            :                    dp << "\nFrom stmt: ";
    1538                 :            :                    print_gimple_stmt (dump_file, dr->stmt, 0));
    1539                 :            : 
    1540                 :        690 :       scop->drs.safe_push (dr_info (dr, pbb));
    1541                 :            :     }
    1542                 :            : 
    1543                 :            :   return NULL;
    1544                 :            : }
    1545                 :            : 
    1546                 :            : /* Call-back for dom_walk executed after visiting the dominated
    1547                 :            :    blocks.  */
    1548                 :            : 
    1549                 :            : void
    1550                 :       1979 : gather_bbs::after_dom_children (basic_block bb)
    1551                 :            : {
    1552                 :       1979 :   if (!bb_in_sese_p (bb, scop->scop_info->region))
    1553                 :            :     return;
    1554                 :            : 
    1555                 :       1814 :   if (single_pred_cond_non_loop_exit (bb))
    1556                 :            :     {
    1557                 :        541 :       edge e = single_pred_edge (bb);
    1558                 :        541 :       if (e != scop->scop_info->region.entry)
    1559                 :            :         {
    1560                 :        541 :           conditions.pop ();
    1561                 :        541 :           cases.pop ();
    1562                 :            :         }
    1563                 :            :     }
    1564                 :            : }
    1565                 :            : 
    1566                 :            : 
    1567                 :            : /* Compute sth like an execution order, dominator order with first executing
    1568                 :            :    edges that stay inside the current loop, delaying processing exit edges.  */
    1569                 :            : 
    1570                 :            : static int *bb_to_rpo;
    1571                 :            : 
    1572                 :            : /* Helper for qsort, sorting after order above.  */
    1573                 :            : 
    1574                 :            : static int
    1575                 :       3116 : cmp_pbbs (const void *pa, const void *pb)
    1576                 :            : {
    1577                 :       3116 :   poly_bb_p bb1 = *((const poly_bb_p *)pa);
    1578                 :       3116 :   poly_bb_p bb2 = *((const poly_bb_p *)pb);
    1579                 :       3116 :   if (bb_to_rpo[bb1->black_box->bb->index]
    1580                 :       3116 :       < bb_to_rpo[bb2->black_box->bb->index])
    1581                 :            :     return -1;
    1582                 :       1697 :   else if (bb_to_rpo[bb1->black_box->bb->index]
    1583                 :            :            > bb_to_rpo[bb2->black_box->bb->index])
    1584                 :            :     return 1;
    1585                 :            :   else
    1586                 :          0 :     return 0;
    1587                 :            : }
    1588                 :            : 
    1589                 :            : /* Find Static Control Parts (SCoP) in the current function and pushes
    1590                 :            :    them to SCOPS.  */
    1591                 :            : 
    1592                 :            : void
    1593                 :        548 : build_scops (vec<scop_p> *scops)
    1594                 :            : {
    1595                 :        548 :   if (dump_file)
    1596                 :        188 :     dp.set_dump_file (dump_file);
    1597                 :            : 
    1598                 :       1096 :   scop_detection sb;
    1599                 :        548 :   sb.build_scop_depth (current_loops->tree_root);
    1600                 :            : 
    1601                 :            :   /* Now create scops from the lightweight SESEs.  */
    1602                 :        548 :   vec<sese_l> scops_l = sb.get_scops ();
    1603                 :            : 
    1604                 :            :   /* Domwalk needs a bb to RPO mapping.  Compute it once here.  */
    1605                 :        548 :   int *postorder = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
    1606                 :        548 :   int postorder_num = pre_and_rev_post_order_compute (NULL, postorder, true);
    1607                 :        548 :   bb_to_rpo = XNEWVEC (int, last_basic_block_for_fn (cfun));
    1608                 :       9827 :   for (int i = 0; i < postorder_num; ++i)
    1609                 :       9279 :     bb_to_rpo[postorder[i]] = i;
    1610                 :        548 :   free (postorder);
    1611                 :            : 
    1612                 :        548 :   int i;
    1613                 :        548 :   sese_l *s;
    1614                 :        734 :   FOR_EACH_VEC_ELT (scops_l, i, s)
    1615                 :            :     {
    1616                 :        186 :       scop_p scop = new_scop (s->entry, s->exit);
    1617                 :            : 
    1618                 :            :       /* Record all basic blocks and their conditions in REGION.  */
    1619                 :        186 :       gather_bbs (CDI_DOMINATORS, scop, bb_to_rpo).walk (s->entry->dest);
    1620                 :            : 
    1621                 :            :       /* Sort pbbs after execution order for initial schedule generation.  */
    1622                 :        186 :       scop->pbbs.qsort (cmp_pbbs);
    1623                 :            : 
    1624                 :        186 :       if (! build_alias_set (scop))
    1625                 :            :         {
    1626                 :         10 :           DEBUG_PRINT (dp << "[scop-detection-fail] cannot handle dependences\n");
    1627                 :         10 :           free_scop (scop);
    1628                 :         10 :           continue;
    1629                 :            :         }
    1630                 :            : 
    1631                 :            :       /* Do not optimize a scop containing only PBBs that do not belong
    1632                 :            :          to any loops.  */
    1633                 :        176 :       if (sb.nb_pbbs_in_loops (scop) == 0)
    1634                 :            :         {
    1635                 :          0 :           DEBUG_PRINT (dp << "[scop-detection-fail] no data references.\n");
    1636                 :          0 :           free_scop (scop);
    1637                 :          0 :           continue;
    1638                 :            :         }
    1639                 :            : 
    1640                 :        176 :       unsigned max_arrays = param_graphite_max_arrays_per_scop;
    1641                 :        176 :       if (max_arrays > 0
    1642                 :        352 :           && scop->drs.length () >= max_arrays)
    1643                 :            :         {
    1644                 :          0 :           DEBUG_PRINT (dp << "[scop-detection-fail] too many data references: "
    1645                 :            :                        << scop->drs.length ()
    1646                 :            :                        << " is larger than --param graphite-max-arrays-per-scop="
    1647                 :            :                        << max_arrays << ".\n");
    1648                 :          0 :           free_scop (scop);
    1649                 :          0 :           continue;
    1650                 :            :         }
    1651                 :            : 
    1652                 :        176 :       find_scop_parameters (scop);
    1653                 :        176 :       graphite_dim_t max_dim = param_graphite_max_nb_scop_params;
    1654                 :        176 :       if (max_dim > 0
    1655                 :        176 :           && scop_nb_params (scop) > max_dim)
    1656                 :            :         {
    1657                 :          0 :           DEBUG_PRINT (dp << "[scop-detection-fail] too many parameters: "
    1658                 :            :                           << scop_nb_params (scop)
    1659                 :            :                           << " larger than --param graphite-max-nb-scop-params="
    1660                 :            :                           << max_dim << ".\n");
    1661                 :          0 :           free_scop (scop);
    1662                 :          0 :           continue;
    1663                 :            :         }
    1664                 :            : 
    1665                 :        176 :       scops->safe_push (scop);
    1666                 :            :     }
    1667                 :            : 
    1668                 :        548 :   free (bb_to_rpo);
    1669                 :        548 :   bb_to_rpo = NULL;
    1670                 :        824 :   DEBUG_PRINT (dp << "number of SCoPs: " << (scops ? scops->length () : 0););
    1671                 :        548 : }
    1672                 :            : 
    1673                 :            : #endif /* HAVE_isl */

Generated by: LCOV version 1.0

LCOV profile is generated on x86_64 machine using following configure options: configure --disable-bootstrap --enable-coverage=opt --enable-languages=c,c++,fortran,go,jit,lto --enable-host-shared. GCC test suite is run with the built compiler.