LCOV - code coverage report
Current view: top level - gcc - graphite-sese-to-poly.c (source / functions) Hit Total Coverage
Test: gcc.info Lines: 562 615 91.4 %
Date: 2020-03-28 11:57:23 Functions: 39 43 90.7 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 0 -

           Branch data     Line data    Source code
       1                 :            : /* Conversion of SESE regions to Polyhedra.
       2                 :            :    Copyright (C) 2009-2020 Free Software Foundation, Inc.
       3                 :            :    Contributed by Sebastian Pop <sebastian.pop@amd.com>.
       4                 :            : 
       5                 :            : This file is part of GCC.
       6                 :            : 
       7                 :            : GCC is free software; you can redistribute it and/or modify
       8                 :            : it under the terms of the GNU General Public License as published by
       9                 :            : the Free Software Foundation; either version 3, or (at your option)
      10                 :            : any later version.
      11                 :            : 
      12                 :            : GCC is distributed in the hope that it will be useful,
      13                 :            : but WITHOUT ANY WARRANTY; without even the implied warranty of
      14                 :            : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      15                 :            : GNU General Public License for more details.
      16                 :            : 
      17                 :            : You should have received a copy of the GNU General Public License
      18                 :            : along with GCC; see the file COPYING3.  If not see
      19                 :            : <http://www.gnu.org/licenses/>.  */
      20                 :            : 
      21                 :            : #define USES_ISL
      22                 :            : 
      23                 :            : #include "config.h"
      24                 :            : 
      25                 :            : #ifdef HAVE_isl
      26                 :            : 
      27                 :            : #include "system.h"
      28                 :            : #include "coretypes.h"
      29                 :            : #include "backend.h"
      30                 :            : #include "cfghooks.h"
      31                 :            : #include "tree.h"
      32                 :            : #include "gimple.h"
      33                 :            : #include "ssa.h"
      34                 :            : #include "fold-const.h"
      35                 :            : #include "gimple-iterator.h"
      36                 :            : #include "gimplify.h"
      37                 :            : #include "gimplify-me.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-pass.h"
      44                 :            : #include "cfgloop.h"
      45                 :            : #include "tree-data-ref.h"
      46                 :            : #include "tree-scalar-evolution.h"
      47                 :            : #include "domwalk.h"
      48                 :            : #include "tree-ssa-propagate.h"
      49                 :            : 
      50                 :            : #include <isl/constraint.h>
      51                 :            : #include <isl/set.h>
      52                 :            : #include <isl/map.h>
      53                 :            : #include <isl/union_map.h>
      54                 :            : #include <isl/constraint.h>
      55                 :            : #include <isl/aff.h>
      56                 :            : #include <isl/val.h>
      57                 :            : 
      58                 :            : #include "graphite.h"
      59                 :            : 
      60                 :            : /* Return an isl identifier for the polyhedral basic block PBB.  */
      61                 :            : 
      62                 :            : static isl_id *
      63                 :        527 : isl_id_for_pbb (scop_p s, poly_bb_p pbb)
      64                 :            : {
      65                 :        527 :   char name[14];
      66                 :        527 :   snprintf (name, sizeof (name), "S_%d", pbb_index (pbb));
      67                 :        527 :   return isl_id_alloc (s->isl_context, name, pbb);
      68                 :            : }
      69                 :            : 
      70                 :            : static isl_pw_aff *extract_affine (scop_p, tree, __isl_take isl_space *space);
      71                 :            : 
      72                 :            : /* Extract an affine expression from the chain of recurrence E.  */
      73                 :            : 
      74                 :            : static isl_pw_aff *
      75                 :        947 : extract_affine_chrec (scop_p s, tree e, __isl_take isl_space *space)
      76                 :            : {
      77                 :        947 :   isl_pw_aff *lhs = extract_affine (s, CHREC_LEFT (e), isl_space_copy (space));
      78                 :        947 :   isl_pw_aff *rhs = extract_affine (s, CHREC_RIGHT (e), isl_space_copy (space));
      79                 :        947 :   isl_local_space *ls = isl_local_space_from_space (space);
      80                 :        947 :   unsigned pos = sese_loop_depth (s->scop_info->region, get_chrec_loop (e)) - 1;
      81                 :        947 :   isl_aff *loop = isl_aff_set_coefficient_si
      82                 :        947 :     (isl_aff_zero_on_domain (ls), isl_dim_in, pos, 1);
      83                 :        947 :   isl_pw_aff *l = isl_pw_aff_from_aff (loop);
      84                 :            : 
      85                 :            :   /* Before multiplying, make sure that the result is affine.  */
      86                 :        947 :   gcc_assert (isl_pw_aff_is_cst (rhs)
      87                 :            :               || isl_pw_aff_is_cst (l));
      88                 :            : 
      89                 :        947 :   return isl_pw_aff_add (lhs, isl_pw_aff_mul (rhs, l));
      90                 :            : }
      91                 :            : 
      92                 :            : /* Extract an affine expression from the mult_expr E.  */
      93                 :            : 
      94                 :            : static isl_pw_aff *
      95                 :          0 : extract_affine_mul (scop_p s, tree e, __isl_take isl_space *space)
      96                 :            : {
      97                 :          0 :   isl_pw_aff *lhs = extract_affine (s, TREE_OPERAND (e, 0),
      98                 :            :                                     isl_space_copy (space));
      99                 :          0 :   isl_pw_aff *rhs = extract_affine (s, TREE_OPERAND (e, 1), space);
     100                 :            : 
     101                 :          0 :   if (!isl_pw_aff_is_cst (lhs)
     102                 :          0 :       && !isl_pw_aff_is_cst (rhs))
     103                 :            :     {
     104                 :          0 :       isl_pw_aff_free (lhs);
     105                 :          0 :       isl_pw_aff_free (rhs);
     106                 :          0 :       return NULL;
     107                 :            :     }
     108                 :            : 
     109                 :          0 :   return isl_pw_aff_mul (lhs, rhs);
     110                 :            : }
     111                 :            : 
     112                 :            : /* Return an isl identifier from the name of the ssa_name E.  */
     113                 :            : 
     114                 :            : static isl_id *
     115                 :        122 : isl_id_for_ssa_name (scop_p s, tree e)
     116                 :            : {
     117                 :        122 :   char name1[14];
     118                 :        122 :   snprintf (name1, sizeof (name1), "P_%d", SSA_NAME_VERSION (e));
     119                 :        122 :   return isl_id_alloc (s->isl_context, name1, e);
     120                 :            : }
     121                 :            : 
     122                 :            : /* Return an isl identifier for the data reference DR.  Data references and
     123                 :            :    scalar references get the same isl_id.  They need to be comparable and are
     124                 :            :    distinguished through the first dimension, which contains the alias set or
     125                 :            :    SSA_NAME_VERSION number.  */
     126                 :            : 
     127                 :            : static isl_id *
     128                 :       1142 : isl_id_for_dr (scop_p s)
     129                 :            : {
     130                 :          0 :   return isl_id_alloc (s->isl_context, "", 0);
     131                 :            : }
     132                 :            : 
     133                 :            : /* Extract an affine expression from the ssa_name E.  */
     134                 :            : 
     135                 :            : static isl_pw_aff *
     136                 :        262 : extract_affine_name (int dimension, __isl_take isl_space *space)
     137                 :            : {
     138                 :        262 :   isl_set *dom = isl_set_universe (isl_space_copy (space));
     139                 :        262 :   isl_aff *aff = isl_aff_zero_on_domain (isl_local_space_from_space (space));
     140                 :        262 :   aff = isl_aff_add_coefficient_si (aff, isl_dim_param, dimension, 1);
     141                 :        262 :   return isl_pw_aff_alloc (dom, aff);
     142                 :            : }
     143                 :            : 
     144                 :            : /* Convert WI to a isl_val with CTX.  */
     145                 :            : 
     146                 :            : static __isl_give isl_val *
     147                 :       4173 : isl_val_int_from_wi (isl_ctx *ctx, const widest_int &wi)
     148                 :            : {
     149                 :       4173 :   if (wi::neg_p (wi, SIGNED))
     150                 :            :     {
     151                 :        155 :       widest_int mwi = -wi;
     152                 :        155 :       return isl_val_neg (isl_val_int_from_chunks (ctx, mwi.get_len (),
     153                 :            :                                                    sizeof (HOST_WIDE_INT),
     154                 :        155 :                                                    mwi.get_val ()));
     155                 :            :     }
     156                 :       4018 :   return isl_val_int_from_chunks (ctx, wi.get_len (), sizeof (HOST_WIDE_INT),
     157                 :       4018 :                                   wi.get_val ());
     158                 :            : }
     159                 :            : 
     160                 :            : /* Extract an affine expression from the gmp constant G.  */
     161                 :            : 
     162                 :            : static isl_pw_aff *
     163                 :       3458 : extract_affine_wi (const widest_int &g, __isl_take isl_space *space)
     164                 :            : {
     165                 :       3458 :   isl_local_space *ls = isl_local_space_from_space (isl_space_copy (space));
     166                 :       3458 :   isl_aff *aff = isl_aff_zero_on_domain (ls);
     167                 :       3458 :   isl_set *dom = isl_set_universe (space);
     168                 :       3458 :   isl_ctx *ct = isl_aff_get_ctx (aff);
     169                 :       3458 :   isl_val *v = isl_val_int_from_wi (ct, g);
     170                 :       3458 :   aff = isl_aff_add_constant_val (aff, v);
     171                 :            : 
     172                 :       3458 :   return isl_pw_aff_alloc (dom, aff);
     173                 :            : }
     174                 :            : 
     175                 :            : /* Extract an affine expression from the integer_cst E.  */
     176                 :            : 
     177                 :            : static isl_pw_aff *
     178                 :       3346 : extract_affine_int (tree e, __isl_take isl_space *space)
     179                 :            : {
     180                 :       3346 :   isl_pw_aff *res = extract_affine_wi (wi::to_widest (e), space);
     181                 :       3346 :   return res;
     182                 :            : }
     183                 :            : 
     184                 :            : /* Compute pwaff mod 2^width.  */
     185                 :            : 
     186                 :            : static isl_pw_aff *
     187                 :        250 : wrap (isl_pw_aff *pwaff, unsigned width)
     188                 :            : {
     189                 :        250 :   isl_val *mod;
     190                 :            : 
     191                 :        250 :   mod = isl_val_int_from_ui (isl_pw_aff_get_ctx (pwaff), width);
     192                 :        250 :   mod = isl_val_2exp (mod);
     193                 :        250 :   pwaff = isl_pw_aff_mod_val (pwaff, mod);
     194                 :            : 
     195                 :        250 :   return pwaff;
     196                 :            : }
     197                 :            : 
     198                 :            : /* When parameter NAME is in REGION, returns its index in SESE_PARAMS.
     199                 :            :    Otherwise returns -1.  */
     200                 :            : 
     201                 :            : static inline int
     202                 :        262 : parameter_index_in_region (tree name, sese_info_p region)
     203                 :            : {
     204                 :        262 :   int i;
     205                 :        262 :   tree p;
     206                 :        431 :   FOR_EACH_VEC_ELT (region->params, i, p)
     207                 :        431 :     if (p == name)
     208                 :            :       return i;
     209                 :            :   return -1;
     210                 :            : }
     211                 :            : 
     212                 :            : /* Extract an affine expression from the tree E in the scop S.  */
     213                 :            : 
     214                 :            : static isl_pw_aff *
     215                 :       3426 : extract_affine (scop_p s, tree e, __isl_take isl_space *space)
     216                 :            : {
     217                 :       3426 :   isl_pw_aff *lhs, *rhs, *res;
     218                 :            : 
     219                 :       3426 :   if (e == chrec_dont_know) {
     220                 :          0 :     isl_space_free (space);
     221                 :          0 :     return NULL;
     222                 :            :   }
     223                 :            : 
     224                 :       3426 :   tree type = TREE_TYPE (e);
     225                 :       3426 :   switch (TREE_CODE (e))
     226                 :            :     {
     227                 :        947 :     case POLYNOMIAL_CHREC:
     228                 :        947 :       res = extract_affine_chrec (s, e, space);
     229                 :        947 :       break;
     230                 :            : 
     231                 :          0 :     case MULT_EXPR:
     232                 :          0 :       res = extract_affine_mul (s, e, space);
     233                 :          0 :       break;
     234                 :            : 
     235                 :          0 :     case POINTER_PLUS_EXPR:
     236                 :          0 :       {
     237                 :          0 :         lhs = extract_affine (s, TREE_OPERAND (e, 0), isl_space_copy (space));
     238                 :            :         /* The RHS of a pointer-plus expression is to be interpreted
     239                 :            :            as signed value.  Try to look through a sign-changing conversion
     240                 :            :            first.  */
     241                 :          0 :         tree tem = TREE_OPERAND (e, 1);
     242                 :          0 :         STRIP_NOPS (tem);
     243                 :          0 :         rhs = extract_affine (s, tem, space);
     244                 :          0 :         if (TYPE_UNSIGNED (TREE_TYPE (tem)))
     245                 :          0 :           rhs = wrap (rhs, TYPE_PRECISION (type) - 1);
     246                 :          0 :         res = isl_pw_aff_add (lhs, rhs);
     247                 :          0 :         break;
     248                 :            :       }
     249                 :            : 
     250                 :        138 :     case PLUS_EXPR:
     251                 :        138 :       lhs = extract_affine (s, TREE_OPERAND (e, 0), isl_space_copy (space));
     252                 :        138 :       rhs = extract_affine (s, TREE_OPERAND (e, 1), space);
     253                 :        138 :       res = isl_pw_aff_add (lhs, rhs);
     254                 :        138 :       break;
     255                 :            : 
     256                 :         10 :     case MINUS_EXPR:
     257                 :         10 :       lhs = extract_affine (s, TREE_OPERAND (e, 0), isl_space_copy (space));
     258                 :         10 :       rhs = extract_affine (s, TREE_OPERAND (e, 1), space);
     259                 :         10 :       res = isl_pw_aff_sub (lhs, rhs);
     260                 :         10 :       break;
     261                 :            : 
     262                 :          0 :     case BIT_NOT_EXPR:
     263                 :          0 :       lhs = extract_affine (s, integer_minus_one_node, isl_space_copy (space));
     264                 :          0 :       rhs = extract_affine (s, TREE_OPERAND (e, 0), space);
     265                 :          0 :       res = isl_pw_aff_sub (lhs, rhs);
     266                 :            :       /* We need to always wrap the result of a bitwise operation.  */
     267                 :          0 :       return wrap (res, TYPE_PRECISION (type) - (TYPE_UNSIGNED (type) ? 0 : 1));
     268                 :            : 
     269                 :          5 :     case NEGATE_EXPR:
     270                 :          5 :       lhs = extract_affine (s, TREE_OPERAND (e, 0), isl_space_copy (space));
     271                 :          5 :       rhs = extract_affine (s, integer_minus_one_node, space);
     272                 :          5 :       res = isl_pw_aff_mul (lhs, rhs);
     273                 :          5 :       break;
     274                 :            : 
     275                 :        262 :     case SSA_NAME:
     276                 :        262 :       {
     277                 :        262 :         gcc_assert (! defined_in_sese_p (e, s->scop_info->region));
     278                 :        262 :         int dim = parameter_index_in_region (e, s->scop_info);
     279                 :        262 :         gcc_assert (dim != -1);
     280                 :            :         /* No need to wrap a parameter.  */
     281                 :        262 :         return extract_affine_name (dim, space);
     282                 :            :       }
     283                 :            : 
     284                 :       1934 :     case INTEGER_CST:
     285                 :       1934 :       res = extract_affine_int (e, space);
     286                 :            :       /* No need to wrap a single integer.  */
     287                 :       1934 :       return res;
     288                 :            : 
     289                 :        130 :     CASE_CONVERT:
     290                 :        130 :       {
     291                 :        130 :         tree itype = TREE_TYPE (TREE_OPERAND (e, 0));
     292                 :        130 :         res = extract_affine (s, TREE_OPERAND (e, 0), space);
     293                 :            :         /* Signed values, even if overflow is undefined, get modulo-reduced.
     294                 :            :            But only if not all values of the old type fit in the new.  */
     295                 :        130 :         if (! TYPE_UNSIGNED (type)
     296                 :        130 :             && ((TYPE_UNSIGNED (itype)
     297                 :         14 :                  && TYPE_PRECISION (type) <= TYPE_PRECISION (itype))
     298                 :          7 :                 || TYPE_PRECISION (type) < TYPE_PRECISION (itype)))
     299                 :          7 :           res = wrap (res, TYPE_PRECISION (type) - 1);
     300                 :        123 :         else if (TYPE_UNSIGNED (type)
     301                 :        239 :                  && (!TYPE_UNSIGNED (itype)
     302                 :          0 :                      || TYPE_PRECISION (type) < TYPE_PRECISION (itype)))
     303                 :        116 :           res = wrap (res, TYPE_PRECISION (type));
     304                 :            :         return res;
     305                 :            :       }
     306                 :            : 
     307                 :          0 :     case NON_LVALUE_EXPR:
     308                 :          0 :       res = extract_affine (s, TREE_OPERAND (e, 0), space);
     309                 :          0 :       break;
     310                 :            : 
     311                 :          0 :     default:
     312                 :          0 :       gcc_unreachable ();
     313                 :       1100 :       break;
     314                 :            :     }
     315                 :            : 
     316                 :            :   /* For all wrapping arithmetic wrap the result.  */
     317                 :       2008 :   if (TYPE_OVERFLOW_WRAPS (type))
     318                 :        127 :     res = wrap (res, TYPE_PRECISION (type));
     319                 :            : 
     320                 :            :   return res;
     321                 :            : }
     322                 :            : 
     323                 :            : /* Returns a linear expression for tree T evaluated in PBB.  */
     324                 :            : 
     325                 :            : static isl_pw_aff *
     326                 :        108 : create_pw_aff_from_tree (poly_bb_p pbb, loop_p loop, tree t)
     327                 :            : {
     328                 :        108 :   scop_p scop = PBB_SCOP (pbb);
     329                 :            : 
     330                 :        108 :   t = cached_scalar_evolution_in_region (scop->scop_info->region, loop, t);
     331                 :            : 
     332                 :        108 :   gcc_assert (!chrec_contains_undetermined (t));
     333                 :        108 :   gcc_assert (!automatically_generated_chrec_p (t));
     334                 :            : 
     335                 :        108 :   return extract_affine (scop, t, isl_set_get_space (pbb->domain));
     336                 :            : }
     337                 :            : 
     338                 :            : /* Add conditional statement STMT to pbb.  CODE is used as the comparison
     339                 :            :    operator.  This allows us to invert the condition or to handle
     340                 :            :    inequalities.  */
     341                 :            : 
     342                 :            : static void
     343                 :         54 : add_condition_to_pbb (poly_bb_p pbb, gcond *stmt, enum tree_code code)
     344                 :            : {
     345                 :         54 :   loop_p loop = gimple_bb (stmt)->loop_father;
     346                 :         54 :   isl_pw_aff *lhs = create_pw_aff_from_tree (pbb, loop, gimple_cond_lhs (stmt));
     347                 :         54 :   isl_pw_aff *rhs = create_pw_aff_from_tree (pbb, loop, gimple_cond_rhs (stmt));
     348                 :            : 
     349                 :         54 :   isl_set *cond;
     350                 :         54 :   switch (code)
     351                 :            :     {
     352                 :          0 :       case LT_EXPR:
     353                 :          0 :         cond = isl_pw_aff_lt_set (lhs, rhs);
     354                 :          0 :         break;
     355                 :            : 
     356                 :         19 :       case GT_EXPR:
     357                 :         19 :         cond = isl_pw_aff_gt_set (lhs, rhs);
     358                 :         19 :         break;
     359                 :            : 
     360                 :          8 :       case LE_EXPR:
     361                 :          8 :         cond = isl_pw_aff_le_set (lhs, rhs);
     362                 :          8 :         break;
     363                 :            : 
     364                 :          1 :       case GE_EXPR:
     365                 :          1 :         cond = isl_pw_aff_ge_set (lhs, rhs);
     366                 :          1 :         break;
     367                 :            : 
     368                 :         13 :       case EQ_EXPR:
     369                 :         13 :         cond = isl_pw_aff_eq_set (lhs, rhs);
     370                 :         13 :         break;
     371                 :            : 
     372                 :         13 :       case NE_EXPR:
     373                 :         13 :         cond = isl_pw_aff_ne_set (lhs, rhs);
     374                 :         13 :         break;
     375                 :            : 
     376                 :          0 :       default:
     377                 :          0 :         gcc_unreachable ();
     378                 :            :     }
     379                 :            : 
     380                 :         54 :   cond = isl_set_coalesce (cond);
     381                 :         54 :   cond = isl_set_set_tuple_id (cond, isl_set_get_tuple_id (pbb->domain));
     382                 :         54 :   pbb->domain = isl_set_coalesce (isl_set_intersect (pbb->domain, cond));
     383                 :         54 : }
     384                 :            : 
     385                 :            : /* Add conditions to the domain of PBB.  */
     386                 :            : 
     387                 :            : static void
     388                 :        527 : add_conditions_to_domain (poly_bb_p pbb)
     389                 :            : {
     390                 :        527 :   unsigned int i;
     391                 :        527 :   gimple *stmt;
     392                 :        527 :   gimple_poly_bb_p gbb = PBB_BLACK_BOX (pbb);
     393                 :            : 
     394                 :        527 :   if (GBB_CONDITIONS (gbb).is_empty ())
     395                 :        527 :     return;
     396                 :            : 
     397                 :        106 :   FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb), i, stmt)
     398                 :         54 :     switch (gimple_code (stmt))
     399                 :            :       {
     400                 :         54 :       case GIMPLE_COND:
     401                 :         54 :           {
     402                 :            :             /* Don't constrain on anything else than INTEGER_TYPE.  */
     403                 :         54 :             if (TREE_CODE (TREE_TYPE (gimple_cond_lhs (stmt))) != INTEGER_TYPE)
     404                 :            :               break;
     405                 :            : 
     406                 :         54 :             gcond *cond_stmt = as_a <gcond *> (stmt);
     407                 :         54 :             enum tree_code code = gimple_cond_code (cond_stmt);
     408                 :            : 
     409                 :            :             /* The conditions for ELSE-branches are inverted.  */
     410                 :         54 :             if (!GBB_CONDITION_CASES (gbb)[i])
     411                 :         20 :               code = invert_tree_comparison (code, false);
     412                 :            : 
     413                 :         54 :             add_condition_to_pbb (pbb, cond_stmt, code);
     414                 :         54 :             break;
     415                 :            :           }
     416                 :            : 
     417                 :          0 :       default:
     418                 :          0 :         gcc_unreachable ();
     419                 :         54 :         break;
     420                 :            :       }
     421                 :            : }
     422                 :            : 
     423                 :            : /* Add constraints on the possible values of parameter P from the type
     424                 :            :    of P.  */
     425                 :            : 
     426                 :            : static void
     427                 :        122 : add_param_constraints (scop_p scop, graphite_dim_t p, tree parameter)
     428                 :            : {
     429                 :        122 :   tree type = TREE_TYPE (parameter);
     430                 :        122 :   wide_int min, max;
     431                 :            : 
     432                 :        122 :   gcc_assert (INTEGRAL_TYPE_P (type) || POINTER_TYPE_P (type));
     433                 :            : 
     434                 :        122 :   if (INTEGRAL_TYPE_P (type)
     435                 :        122 :       && get_range_info (parameter, &min, &max) == VR_RANGE)
     436                 :            :     ;
     437                 :            :   else
     438                 :            :     {
     439                 :         92 :       min = wi::min_value (TYPE_PRECISION (type), TYPE_SIGN (type));
     440                 :         92 :       max = wi::max_value (TYPE_PRECISION (type), TYPE_SIGN (type));
     441                 :            :     }
     442                 :            : 
     443                 :        122 :   isl_space *space = isl_set_get_space (scop->param_context);
     444                 :        122 :   isl_constraint *c = isl_inequality_alloc (isl_local_space_from_space (space));
     445                 :        122 :   isl_val *v = isl_val_int_from_wi (scop->isl_context,
     446                 :        122 :                                     widest_int::from (min, TYPE_SIGN (type)));
     447                 :        122 :   v = isl_val_neg (v);
     448                 :        122 :   c = isl_constraint_set_constant_val (c, v);
     449                 :        122 :   c = isl_constraint_set_coefficient_si (c, isl_dim_param, p, 1);
     450                 :        244 :   scop->param_context = isl_set_coalesce
     451                 :        122 :       (isl_set_add_constraint (scop->param_context, c));
     452                 :            : 
     453                 :        122 :   space = isl_set_get_space (scop->param_context);
     454                 :        122 :   c = isl_inequality_alloc (isl_local_space_from_space (space));
     455                 :        122 :   v = isl_val_int_from_wi (scop->isl_context,
     456                 :        122 :                            widest_int::from (max, TYPE_SIGN (type)));
     457                 :        122 :   c = isl_constraint_set_constant_val (c, v);
     458                 :        122 :   c = isl_constraint_set_coefficient_si (c, isl_dim_param, p, -1);
     459                 :        244 :   scop->param_context = isl_set_coalesce
     460                 :        122 :       (isl_set_add_constraint (scop->param_context, c));
     461                 :        122 : }
     462                 :            : 
     463                 :            : /* Add a constrain to the ACCESSES polyhedron for the alias set of
     464                 :            :    data reference DR.  ACCESSP_NB_DIMS is the dimension of the
     465                 :            :    ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
     466                 :            :    domain.  */
     467                 :            : 
     468                 :            : static isl_map *
     469                 :        615 : pdr_add_alias_set (isl_map *acc, dr_info &dri)
     470                 :            : {
     471                 :        615 :   isl_constraint *c = isl_equality_alloc
     472                 :        615 :       (isl_local_space_from_space (isl_map_get_space (acc)));
     473                 :            :   /* Positive numbers for all alias sets.  */
     474                 :        615 :   c = isl_constraint_set_constant_si (c, -dri.alias_set);
     475                 :        615 :   c = isl_constraint_set_coefficient_si (c, isl_dim_out, 0, 1);
     476                 :            : 
     477                 :        615 :   return isl_map_add_constraint (acc, c);
     478                 :            : }
     479                 :            : 
     480                 :            : /* Assign the affine expression INDEX to the output dimension POS of
     481                 :            :    MAP and return the result.  */
     482                 :            : 
     483                 :            : static isl_map *
     484                 :        876 : set_index (isl_map *map, int pos, isl_pw_aff *index)
     485                 :            : {
     486                 :        876 :   isl_map *index_map;
     487                 :        876 :   int len = isl_map_dim (map, isl_dim_out);
     488                 :        876 :   isl_id *id;
     489                 :            : 
     490                 :        876 :   index_map = isl_map_from_pw_aff (index);
     491                 :        876 :   index_map = isl_map_insert_dims (index_map, isl_dim_out, 0, pos);
     492                 :        876 :   index_map = isl_map_add_dims (index_map, isl_dim_out, len - pos - 1);
     493                 :            : 
     494                 :        876 :   id = isl_map_get_tuple_id (map, isl_dim_out);
     495                 :        876 :   index_map = isl_map_set_tuple_id (index_map, isl_dim_out, id);
     496                 :        876 :   id = isl_map_get_tuple_id (map, isl_dim_in);
     497                 :        876 :   index_map = isl_map_set_tuple_id (index_map, isl_dim_in, id);
     498                 :            : 
     499                 :        876 :   return isl_map_intersect (map, index_map);
     500                 :            : }
     501                 :            : 
     502                 :            : /* Add to ACCESSES polyhedron equalities defining the access functions
     503                 :            :    to the memory.  ACCESSP_NB_DIMS is the dimension of the ACCESSES
     504                 :            :    polyhedron, DOM_NB_DIMS is the dimension of the iteration domain.
     505                 :            :    PBB is the poly_bb_p that contains the data reference DR.  */
     506                 :            : 
     507                 :            : static isl_map *
     508                 :        615 : pdr_add_memory_accesses (isl_map *acc, dr_info &dri)
     509                 :            : {
     510                 :        615 :   data_reference_p dr = dri.dr;
     511                 :        615 :   poly_bb_p pbb = dri.pbb;
     512                 :        615 :   int i, nb_subscripts = DR_NUM_DIMENSIONS (dr);
     513                 :        615 :   scop_p scop = PBB_SCOP (pbb);
     514                 :            : 
     515                 :       1491 :   for (i = 0; i < nb_subscripts; i++)
     516                 :            :     {
     517                 :        876 :       isl_pw_aff *aff;
     518                 :        876 :       tree afn = DR_ACCESS_FN (dr, i);
     519                 :            : 
     520                 :        876 :       aff = extract_affine (scop, afn,
     521                 :            :                             isl_space_domain (isl_map_get_space (acc)));
     522                 :        876 :       acc = set_index (acc, nb_subscripts - i , aff);
     523                 :            :     }
     524                 :            : 
     525                 :        615 :   return isl_map_coalesce (acc);
     526                 :            : }
     527                 :            : 
     528                 :            : /* Return true when the LOW and HIGH bounds of an array reference REF are valid
     529                 :            :    to extract constraints on accessed elements of the array.  Returning false is
     530                 :            :    the conservative answer.  */
     531                 :            : 
     532                 :            : static bool
     533                 :        769 : bounds_are_valid (tree ref, tree low, tree high)
     534                 :            : {
     535                 :        769 :   if (!high)
     536                 :            :     return false;
     537                 :            : 
     538                 :        745 :   if (!tree_fits_shwi_p (low)
     539                 :        745 :       || !tree_fits_shwi_p (high))
     540                 :            :     return false;
     541                 :            : 
     542                 :            :   /* 1-element arrays at end of structures may extend over
     543                 :            :      their declared size.  */
     544                 :        706 :   if (array_at_struct_end_p (ref)
     545                 :        706 :       && operand_equal_p (low, high, 0))
     546                 :            :     return false;
     547                 :            : 
     548                 :            :   /* Fortran has some arrays where high bound is -1 and low is 0.  */
     549                 :        706 :   if (integer_onep (fold_build2 (LT_EXPR, boolean_type_node, high, low)))
     550                 :          0 :     return false;
     551                 :            : 
     552                 :            :   return true;
     553                 :            : }
     554                 :            : 
     555                 :            : /* Add constrains representing the size of the accessed data to the
     556                 :            :    ACCESSES polyhedron.  ACCESSP_NB_DIMS is the dimension of the
     557                 :            :    ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration
     558                 :            :    domain.  */
     559                 :            : 
     560                 :            : static isl_set *
     561                 :        615 : pdr_add_data_dimensions (isl_set *subscript_sizes, scop_p scop,
     562                 :            :                          data_reference_p dr)
     563                 :            : {
     564                 :        615 :   tree ref = DR_REF (dr);
     565                 :            : 
     566                 :        615 :   int nb_subscripts = DR_NUM_DIMENSIONS (dr);
     567                 :       1384 :   for (int i = nb_subscripts - 1; i >= 0; i--, ref = TREE_OPERAND (ref, 0))
     568                 :            :     {
     569                 :        863 :       if (TREE_CODE (ref) != ARRAY_REF)
     570                 :         94 :         return subscript_sizes;
     571                 :            : 
     572                 :        769 :       tree low = array_ref_low_bound (ref);
     573                 :        769 :       tree high = array_ref_up_bound (ref);
     574                 :            : 
     575                 :        769 :       if (!bounds_are_valid (ref, low, high))
     576                 :         63 :         continue;
     577                 :            : 
     578                 :        706 :       isl_space *space = isl_set_get_space (subscript_sizes);
     579                 :        706 :       isl_pw_aff *lb = extract_affine_int (low, isl_space_copy (space));
     580                 :        706 :       isl_pw_aff *ub = extract_affine_int (high, isl_space_copy (space));
     581                 :            : 
     582                 :            :       /* high >= 0 */
     583                 :        706 :       isl_set *valid = isl_pw_aff_nonneg_set (isl_pw_aff_copy (ub));
     584                 :        706 :       valid = isl_set_project_out (valid, isl_dim_set, 0,
     585                 :        706 :                                    isl_set_dim (valid, isl_dim_set));
     586                 :       1412 :       scop->param_context = isl_set_coalesce
     587                 :        706 :         (isl_set_intersect (scop->param_context, valid));
     588                 :            : 
     589                 :        706 :       isl_aff *aff
     590                 :        706 :         = isl_aff_zero_on_domain (isl_local_space_from_space (space));
     591                 :        706 :       aff = isl_aff_add_coefficient_si (aff, isl_dim_in, i + 1, 1);
     592                 :        706 :       isl_set *univ
     593                 :        706 :         = isl_set_universe (isl_space_domain (isl_aff_get_space (aff)));
     594                 :        706 :       isl_pw_aff *index = isl_pw_aff_alloc (univ, aff);
     595                 :            : 
     596                 :        706 :       isl_id *id = isl_set_get_tuple_id (subscript_sizes);
     597                 :        706 :       lb = isl_pw_aff_set_tuple_id (lb, isl_dim_in, isl_id_copy (id));
     598                 :        706 :       ub = isl_pw_aff_set_tuple_id (ub, isl_dim_in, id);
     599                 :            : 
     600                 :            :       /* low <= sub_i <= high */
     601                 :        706 :       isl_set *lbs = isl_pw_aff_ge_set (isl_pw_aff_copy (index), lb);
     602                 :        706 :       isl_set *ubs = isl_pw_aff_le_set (index, ub);
     603                 :        706 :       subscript_sizes = isl_set_intersect (subscript_sizes, lbs);
     604                 :        706 :       subscript_sizes = isl_set_intersect (subscript_sizes, ubs);
     605                 :            :     }
     606                 :            : 
     607                 :        521 :   return isl_set_coalesce (subscript_sizes);
     608                 :            : }
     609                 :            : 
     610                 :            : /* Build data accesses for DRI.  */
     611                 :            : 
     612                 :            : static void
     613                 :        615 : build_poly_dr (dr_info &dri)
     614                 :            : {
     615                 :        615 :   isl_map *acc;
     616                 :        615 :   isl_set *subscript_sizes;
     617                 :        615 :   poly_bb_p pbb = dri.pbb;
     618                 :        615 :   data_reference_p dr = dri.dr;
     619                 :        615 :   scop_p scop = PBB_SCOP (pbb);
     620                 :        615 :   isl_id *id = isl_id_for_dr (scop);
     621                 :            : 
     622                 :        615 :   {
     623                 :        615 :     isl_space *dc = isl_set_get_space (pbb->domain);
     624                 :        615 :     int nb_out = 1 + DR_NUM_DIMENSIONS (dr);
     625                 :        615 :     isl_space *space = isl_space_add_dims (isl_space_from_domain (dc),
     626                 :            :                                            isl_dim_out, nb_out);
     627                 :            : 
     628                 :        615 :     acc = isl_map_universe (space);
     629                 :        615 :     acc = isl_map_set_tuple_id (acc, isl_dim_out, isl_id_copy (id));
     630                 :            :   }
     631                 :            : 
     632                 :        615 :   acc = pdr_add_alias_set (acc, dri);
     633                 :        615 :   acc = pdr_add_memory_accesses (acc, dri);
     634                 :            : 
     635                 :        615 :   {
     636                 :        615 :     int nb = 1 + DR_NUM_DIMENSIONS (dr);
     637                 :        615 :     isl_space *space = isl_space_set_alloc (scop->isl_context, 0, nb);
     638                 :            : 
     639                 :        615 :     space = isl_space_set_tuple_id (space, isl_dim_set, id);
     640                 :        615 :     subscript_sizes = isl_set_nat_universe (space);
     641                 :        615 :     subscript_sizes = isl_set_fix_si (subscript_sizes, isl_dim_set, 0,
     642                 :            :                                       dri.alias_set);
     643                 :        615 :     subscript_sizes = pdr_add_data_dimensions (subscript_sizes, scop, dr);
     644                 :            :   }
     645                 :            : 
     646                 :        919 :   new_poly_dr (pbb, DR_STMT (dr), DR_IS_READ (dr) ? PDR_READ : PDR_WRITE,
     647                 :            :                acc, subscript_sizes);
     648                 :        615 : }
     649                 :            : 
     650                 :            : static void
     651                 :       1115 : build_poly_sr_1 (poly_bb_p pbb, gimple *stmt, tree var, enum poly_dr_type kind,
     652                 :            :                  isl_map *acc, isl_set *subscript_sizes)
     653                 :            : {
     654                 :       1115 :   scop_p scop = PBB_SCOP (pbb);
     655                 :            :   /* Each scalar variables has a unique alias set number starting from
     656                 :            :      the maximum alias set assigned to a dr.  */
     657                 :       1115 :   int alias_set = scop->max_alias_set + SSA_NAME_VERSION (var);
     658                 :       1115 :   subscript_sizes = isl_set_fix_si (subscript_sizes, isl_dim_set, 0,
     659                 :            :                                     alias_set);
     660                 :            : 
     661                 :            :   /* Add a constrain to the ACCESSES polyhedron for the alias set of
     662                 :            :      data reference DR.  */
     663                 :       1115 :   isl_constraint *c
     664                 :       1115 :     = isl_equality_alloc (isl_local_space_from_space (isl_map_get_space (acc)));
     665                 :       1115 :   c = isl_constraint_set_constant_si (c, -alias_set);
     666                 :       1115 :   c = isl_constraint_set_coefficient_si (c, isl_dim_out, 0, 1);
     667                 :            : 
     668                 :       1115 :   new_poly_dr (pbb, stmt, kind, isl_map_add_constraint (acc, c),
     669                 :            :                subscript_sizes);
     670                 :       1115 : }
     671                 :            : 
     672                 :            : /* Record all cross basic block scalar variables in PBB.  */
     673                 :            : 
     674                 :            : static void
     675                 :        527 : build_poly_sr (poly_bb_p pbb)
     676                 :            : {
     677                 :        527 :   scop_p scop = PBB_SCOP (pbb);
     678                 :        527 :   gimple_poly_bb_p gbb = PBB_BLACK_BOX (pbb);
     679                 :        527 :   vec<scalar_use> &reads = gbb->read_scalar_refs;
     680                 :        527 :   vec<tree> &writes = gbb->write_scalar_refs;
     681                 :            : 
     682                 :        527 :   isl_space *dc = isl_set_get_space (pbb->domain);
     683                 :        527 :   int nb_out = 1;
     684                 :        527 :   isl_space *space = isl_space_add_dims (isl_space_from_domain (dc),
     685                 :            :                                          isl_dim_out, nb_out);
     686                 :        527 :   isl_id *id = isl_id_for_dr (scop);
     687                 :        527 :   space = isl_space_set_tuple_id (space, isl_dim_set, isl_id_copy (id));
     688                 :        527 :   isl_map *acc = isl_map_universe (isl_space_copy (space));
     689                 :        527 :   acc = isl_map_set_tuple_id (acc, isl_dim_out, id);
     690                 :        527 :   isl_set *subscript_sizes = isl_set_nat_universe (space);
     691                 :            : 
     692                 :        527 :   int i;
     693                 :        527 :   tree var;
     694                 :       1161 :   FOR_EACH_VEC_ELT (writes, i, var)
     695                 :        634 :     build_poly_sr_1 (pbb, SSA_NAME_DEF_STMT (var), var, PDR_WRITE,
     696                 :            :                      isl_map_copy (acc), isl_set_copy (subscript_sizes));
     697                 :            : 
     698                 :            :   scalar_use *use;
     699                 :       1008 :   FOR_EACH_VEC_ELT (reads, i, use)
     700                 :        481 :     build_poly_sr_1 (pbb, use->first, use->second, PDR_READ, isl_map_copy (acc),
     701                 :            :                      isl_set_copy (subscript_sizes));
     702                 :            : 
     703                 :        527 :   isl_map_free (acc);
     704                 :        527 :   isl_set_free (subscript_sizes);
     705                 :        527 : }
     706                 :            : 
     707                 :            : /* Build data references in SCOP.  */
     708                 :            : 
     709                 :            : static void
     710                 :        172 : build_scop_drs (scop_p scop)
     711                 :            : {
     712                 :        172 :   int i;
     713                 :        172 :   dr_info *dri;
     714                 :        787 :   FOR_EACH_VEC_ELT (scop->drs, i, dri)
     715                 :        615 :     build_poly_dr (*dri);
     716                 :            : 
     717                 :            :   poly_bb_p pbb;
     718                 :        699 :   FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
     719                 :        527 :     build_poly_sr (pbb);
     720                 :        172 : }
     721                 :            : 
     722                 :            : /* Add to the iteration DOMAIN one extra dimension for LOOP->num.  */
     723                 :            : 
     724                 :            : static isl_set *
     725                 :        471 : add_iter_domain_dimension (__isl_take isl_set *domain, loop_p loop, scop_p scop)
     726                 :            : {
     727                 :        471 :   int loop_index = isl_set_dim (domain, isl_dim_set);
     728                 :        471 :   domain = isl_set_add_dims (domain, isl_dim_set, 1);
     729                 :        471 :   char name[50];
     730                 :        471 :   snprintf (name, sizeof(name), "i%d", loop->num);
     731                 :        471 :   isl_id *label = isl_id_alloc (scop->isl_context, name, NULL);
     732                 :        471 :   return isl_set_set_dim_id (domain, isl_dim_set, loop_index, label);
     733                 :            : }
     734                 :            : 
     735                 :            : /* Add constraints to DOMAIN for each loop from LOOP up to CONTEXT.  */
     736                 :            : 
     737                 :            : static isl_set *
     738                 :        851 : add_loop_constraints (scop_p scop, __isl_take isl_set *domain, loop_p loop,
     739                 :            :                       loop_p context)
     740                 :            : {
     741                 :        851 :   if (loop == context)
     742                 :            :     return domain;
     743                 :        755 :   const sese_l &region = scop->scop_info->region;
     744                 :        755 :   if (!loop_in_sese_p (loop, region))
     745                 :            :     return domain;
     746                 :            : 
     747                 :            :   /* Recursion all the way up to the context loop.  */
     748                 :        942 :   domain = add_loop_constraints (scop, domain, loop_outer (loop), context);
     749                 :            : 
     750                 :            :   /* Then, build constraints over the loop in post-order: outer to inner.  */
     751                 :            : 
     752                 :        471 :   int loop_index = isl_set_dim (domain, isl_dim_set);
     753                 :        471 :   if (dump_file)
     754                 :        269 :     fprintf (dump_file, "[sese-to-poly] adding one extra dimension to the "
     755                 :            :              "domain for loop_%d.\n", loop->num);
     756                 :        471 :   domain = add_iter_domain_dimension (domain, loop, scop);
     757                 :        471 :   isl_space *space = isl_set_get_space (domain);
     758                 :            : 
     759                 :            :   /* 0 <= loop_i */
     760                 :        471 :   isl_local_space *ls = isl_local_space_from_space (isl_space_copy (space));
     761                 :        471 :   isl_constraint *c = isl_inequality_alloc (ls);
     762                 :        471 :   c = isl_constraint_set_coefficient_si (c, isl_dim_set, loop_index, 1);
     763                 :        471 :   if (dump_file)
     764                 :            :     {
     765                 :        269 :       fprintf (dump_file, "[sese-to-poly] adding constraint to the domain: ");
     766                 :        269 :       print_isl_constraint (dump_file, c);
     767                 :            :     }
     768                 :        471 :   domain = isl_set_add_constraint (domain, c);
     769                 :            : 
     770                 :        471 :   tree nb_iters = number_of_latch_executions (loop);
     771                 :        471 :   if (TREE_CODE (nb_iters) == INTEGER_CST)
     772                 :            :     {
     773                 :            :       /* loop_i <= cst_nb_iters */
     774                 :        359 :       isl_local_space *ls = isl_local_space_from_space (space);
     775                 :        359 :       isl_constraint *c = isl_inequality_alloc (ls);
     776                 :        359 :       c = isl_constraint_set_coefficient_si (c, isl_dim_set, loop_index, -1);
     777                 :        359 :       isl_val *v
     778                 :        359 :         = isl_val_int_from_wi (scop->isl_context, wi::to_widest (nb_iters));
     779                 :        359 :       c = isl_constraint_set_constant_val (c, v);
     780                 :        359 :       return isl_set_add_constraint (domain, c);
     781                 :            :     }
     782                 :            :   /* loop_i <= expr_nb_iters */
     783                 :        112 :   gcc_assert (!chrec_contains_undetermined (nb_iters));
     784                 :        112 :   nb_iters = cached_scalar_evolution_in_region (region, loop, nb_iters);
     785                 :        112 :   gcc_assert (!chrec_contains_undetermined (nb_iters));
     786                 :            : 
     787                 :        112 :   isl_pw_aff *aff_nb_iters = extract_affine (scop, nb_iters,
     788                 :            :                                              isl_space_copy (space));
     789                 :        112 :   isl_set *valid = isl_pw_aff_nonneg_set (isl_pw_aff_copy (aff_nb_iters));
     790                 :        112 :   valid = isl_set_project_out (valid, isl_dim_set, 0,
     791                 :        112 :                                isl_set_dim (valid, isl_dim_set));
     792                 :            : 
     793                 :        112 :   if (valid)
     794                 :        112 :     scop->param_context = isl_set_intersect (scop->param_context, valid);
     795                 :            : 
     796                 :        112 :   ls = isl_local_space_from_space (isl_space_copy (space));
     797                 :        112 :   isl_aff *loop_i = isl_aff_set_coefficient_si (isl_aff_zero_on_domain (ls),
     798                 :            :                                                 isl_dim_in, loop_index, 1);
     799                 :        112 :   isl_set *le = isl_pw_aff_le_set (isl_pw_aff_from_aff (loop_i),
     800                 :            :                                    isl_pw_aff_copy (aff_nb_iters));
     801                 :        112 :   if (dump_file)
     802                 :            :     {
     803                 :         35 :       fprintf (dump_file, "[sese-to-poly] adding constraint to the domain: ");
     804                 :         35 :       print_isl_set (dump_file, le);
     805                 :            :     }
     806                 :        112 :   domain = isl_set_intersect (domain, le);
     807                 :            : 
     808                 :        112 :   widest_int nit;
     809                 :        112 :   if (!max_stmt_executions (loop, &nit))
     810                 :            :     {
     811                 :          0 :       isl_pw_aff_free (aff_nb_iters);
     812                 :          0 :       isl_space_free (space);
     813                 :          0 :       return domain;
     814                 :            :     }
     815                 :            : 
     816                 :            :   /* NIT is an upper bound to NB_ITERS: "NIT >= NB_ITERS", although we
     817                 :            :      do not know whether the loop executes at least once.  */
     818                 :        112 :   --nit;
     819                 :            : 
     820                 :        112 :   isl_pw_aff *approx = extract_affine_wi (nit, isl_space_copy (space));
     821                 :        112 :   isl_set *x = isl_pw_aff_ge_set (approx, aff_nb_iters);
     822                 :        112 :   x = isl_set_project_out (x, isl_dim_set, 0,
     823                 :        112 :                            isl_set_dim (x, isl_dim_set));
     824                 :        112 :   scop->param_context = isl_set_intersect (scop->param_context, x);
     825                 :            : 
     826                 :        112 :   ls = isl_local_space_from_space (space);
     827                 :        112 :   c = isl_inequality_alloc (ls);
     828                 :        112 :   c = isl_constraint_set_coefficient_si (c, isl_dim_set, loop_index, -1);
     829                 :        112 :   isl_val *v = isl_val_int_from_wi (scop->isl_context, nit);
     830                 :        112 :   c = isl_constraint_set_constant_val (c, v);
     831                 :            : 
     832                 :        112 :   if (dump_file)
     833                 :            :     {
     834                 :         35 :       fprintf (dump_file, "[sese-to-poly] adding constraint to the domain: ");
     835                 :         35 :       print_isl_constraint (dump_file, c);
     836                 :            :     }
     837                 :            : 
     838                 :        112 :   return isl_set_add_constraint (domain, c);
     839                 :            : }
     840                 :            : 
     841                 :            : /* Builds the original iteration domains for each pbb in the SCOP.  */
     842                 :            : 
     843                 :            : static int
     844                 :        380 : build_iteration_domains (scop_p scop, __isl_keep isl_set *context,
     845                 :            :                          int index, loop_p context_loop)
     846                 :            : {
     847                 :        380 :   loop_p current = pbb_loop (scop->pbbs[index]);
     848                 :        380 :   isl_set *domain = isl_set_copy (context);
     849                 :        380 :   domain = add_loop_constraints (scop, domain, current, context_loop);
     850                 :        380 :   const sese_l &region = scop->scop_info->region;
     851                 :            : 
     852                 :        380 :   int i;
     853                 :        380 :   poly_bb_p pbb;
     854                 :       1003 :   FOR_EACH_VEC_ELT_FROM (scop->pbbs, i, pbb, index)
     855                 :            :     {
     856                 :        807 :       loop_p loop = pbb_loop (pbb);
     857                 :        807 :       if (current == loop)
     858                 :            :         {
     859                 :        527 :           pbb->iterators = isl_set_copy (domain);
     860                 :        527 :           pbb->domain = isl_set_copy (domain);
     861                 :        527 :           pbb->domain = isl_set_set_tuple_id (pbb->domain,
     862                 :            :                                               isl_id_for_pbb (scop, pbb));
     863                 :        527 :           add_conditions_to_domain (pbb);
     864                 :            : 
     865                 :        527 :           if (dump_file)
     866                 :            :             {
     867                 :        299 :               fprintf (dump_file, "[sese-to-poly] set pbb_%d->domain: ",
     868                 :            :                        pbb_index (pbb));
     869                 :        299 :               print_isl_set (dump_file, domain);
     870                 :            :             }
     871                 :        527 :           continue;
     872                 :            :         }
     873                 :            : 
     874                 :        545 :       while (loop_in_sese_p (loop, region)
     875                 :        545 :              && current != loop)
     876                 :        265 :         loop = loop_outer (loop);
     877                 :            : 
     878                 :        280 :       if (current != loop)
     879                 :            :         {
     880                 :            :           /* A statement in a different loop nest than CURRENT loop.  */
     881                 :        184 :           isl_set_free (domain);
     882                 :        184 :           return i;
     883                 :            :         }
     884                 :            : 
     885                 :            :       /* A statement nested in the CURRENT loop.  */
     886                 :         96 :       i = build_iteration_domains (scop, domain, i, current);
     887                 :         96 :       i--;
     888                 :            :     }
     889                 :            : 
     890                 :        196 :   isl_set_free (domain);
     891                 :        196 :   return i;
     892                 :            : }
     893                 :            : 
     894                 :            : /* Assign dimension for each parameter in SCOP and add constraints for the
     895                 :            :    parameters.  */
     896                 :            : 
     897                 :            : static void
     898                 :        172 : build_scop_context (scop_p scop)
     899                 :            : {
     900                 :        172 :   sese_info_p region = scop->scop_info;
     901                 :        172 :   unsigned nbp = sese_nb_params (region);
     902                 :        172 :   isl_space *space = isl_space_set_alloc (scop->isl_context, nbp, 0);
     903                 :            : 
     904                 :        172 :   unsigned i;
     905                 :        172 :   tree e;
     906                 :        294 :   FOR_EACH_VEC_ELT (region->params, i, e)
     907                 :        122 :     space = isl_space_set_dim_id (space, isl_dim_param, i,
     908                 :            :                                   isl_id_for_ssa_name (scop, e));
     909                 :            : 
     910                 :        172 :   scop->param_context = isl_set_universe (space);
     911                 :            : 
     912                 :        294 :   FOR_EACH_VEC_ELT (region->params, i, e)
     913                 :        122 :     add_param_constraints (scop, i, e);
     914                 :        172 : }
     915                 :            : 
     916                 :            : /* Return true when loop A is nested in loop B.  */
     917                 :            : 
     918                 :            : static bool
     919                 :        907 : nested_in (loop_p a, loop_p b)
     920                 :            : {
     921                 :        208 :   return b == find_common_loop (a, b);
     922                 :            : }
     923                 :            : 
     924                 :            : /* Return the loop at a specific SCOP->pbbs[*INDEX].  */
     925                 :            : static loop_p
     926                 :       1881 : loop_at (scop_p scop, int *index)
     927                 :            : {
     928                 :       1881 :   return pbb_loop (scop->pbbs[*index]);
     929                 :            : }
     930                 :            : 
     931                 :            : /* Return the index of any pbb belonging to loop or a subloop of A.  */
     932                 :            : 
     933                 :            : static int
     934                 :        106 : index_outermost_in_loop (loop_p a, scop_p scop)
     935                 :            : {
     936                 :        106 :   int i, outermost = -1;
     937                 :        106 :   int last_depth = -1;
     938                 :        106 :   poly_bb_p pbb;
     939                 :        314 :   FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
     940                 :        208 :     if (nested_in (pbb_loop (pbb), a)
     941                 :        208 :         && (last_depth == -1
     942                 :         66 :             || last_depth > (int) loop_depth (pbb_loop (pbb))))
     943                 :            :       {
     944                 :        107 :         outermost = i;
     945                 :        214 :         last_depth = loop_depth (pbb_loop (pbb));
     946                 :            :       }
     947                 :        106 :   return outermost;
     948                 :            : }
     949                 :            : 
     950                 :            : /* Return the index of any pbb belonging to loop or a subloop of A.  */
     951                 :            : 
     952                 :            : static int
     953                 :        439 : index_pbb_in_loop (loop_p a, scop_p scop)
     954                 :            : {
     955                 :        439 :   int i;
     956                 :        439 :   poly_bb_p pbb;
     957                 :        929 :   FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
     958                 :        823 :     if (pbb_loop (pbb) == a)
     959                 :          0 :       return i;
     960                 :            :   return -1;
     961                 :            : }
     962                 :            : 
     963                 :            : static poly_bb_p
     964                 :        439 : outermost_pbb_in (loop_p loop, scop_p scop)
     965                 :            : {
     966                 :        439 :   int x = index_pbb_in_loop (loop, scop);
     967                 :        439 :   if (x == -1)
     968                 :        106 :     x = index_outermost_in_loop (loop, scop);
     969                 :        439 :   return scop->pbbs[x];
     970                 :            : }
     971                 :            : 
     972                 :            : static isl_schedule *
     973                 :        842 : add_in_sequence (__isl_take isl_schedule *a, __isl_take isl_schedule *b)
     974                 :            : {
     975                 :        842 :   gcc_assert (a || b);
     976                 :            : 
     977                 :        842 :   if (!a)
     978                 :            :     return b;
     979                 :            : 
     980                 :        355 :   if (!b)
     981                 :            :     return a;
     982                 :            : 
     983                 :        355 :   return isl_schedule_sequence (a, b);
     984                 :            : }
     985                 :            : 
     986                 :            : struct map_to_dimension_data {
     987                 :            :   int n;
     988                 :            :   isl_union_pw_multi_aff *res;
     989                 :            : };
     990                 :            : 
     991                 :            : /* Create a function that maps the elements of SET to its N-th dimension and add
     992                 :            :    it to USER->res.  */
     993                 :            : 
     994                 :            : static isl_stat
     995                 :        714 : add_outer_projection (__isl_take isl_set *set, void *user)
     996                 :            : {
     997                 :        714 :   struct map_to_dimension_data *data = (struct map_to_dimension_data *) user;
     998                 :        714 :   int dim = isl_set_dim (set, isl_dim_set);
     999                 :        714 :   isl_space *space = isl_set_get_space (set);
    1000                 :            : 
    1001                 :        714 :   gcc_assert (dim >= data->n);
    1002                 :        714 :   isl_pw_multi_aff *pma
    1003                 :       1428 :     = isl_pw_multi_aff_project_out_map (space, isl_dim_set, data->n,
    1004                 :        714 :                                         dim - data->n);
    1005                 :        714 :   data->res = isl_union_pw_multi_aff_add_pw_multi_aff (data->res, pma);
    1006                 :            : 
    1007                 :        714 :   isl_set_free (set);
    1008                 :        714 :   return isl_stat_ok;
    1009                 :            : }
    1010                 :            : 
    1011                 :            : /* Return SET in which all inner dimensions above N are removed.  */
    1012                 :            : 
    1013                 :            : static isl_multi_union_pw_aff *
    1014                 :        439 : outer_projection_mupa (__isl_take isl_union_set *set, int n)
    1015                 :            : {
    1016                 :        439 :   gcc_assert (n >= 0);
    1017                 :        439 :   gcc_assert (set);
    1018                 :        439 :   gcc_assert (!isl_union_set_is_empty (set));
    1019                 :            : 
    1020                 :        439 :   isl_space *space = isl_union_set_get_space (set);
    1021                 :        439 :   isl_union_pw_multi_aff *pwaff = isl_union_pw_multi_aff_empty (space);
    1022                 :            : 
    1023                 :        439 :   struct map_to_dimension_data data = {n, pwaff};
    1024                 :            : 
    1025                 :        439 :   if (isl_union_set_foreach_set (set, &add_outer_projection, &data) < 0)
    1026                 :          0 :     data.res = isl_union_pw_multi_aff_free (data.res);
    1027                 :            : 
    1028                 :        439 :   isl_union_set_free (set);
    1029                 :        439 :   return isl_multi_union_pw_aff_from_union_pw_multi_aff (data.res);
    1030                 :            : }
    1031                 :            : 
    1032                 :            : /* Embed SCHEDULE in the constraints of the LOOP domain.  */
    1033                 :            : 
    1034                 :            : static isl_schedule *
    1035                 :        439 : add_loop_schedule (__isl_take isl_schedule *schedule, loop_p loop,
    1036                 :            :                    scop_p scop)
    1037                 :            : {
    1038                 :        439 :   poly_bb_p pbb = outermost_pbb_in (loop, scop);
    1039                 :        439 :   isl_set *iterators = pbb->iterators;
    1040                 :            : 
    1041                 :        439 :   int empty = isl_set_is_empty (iterators);
    1042                 :        439 :   if (empty < 0 || empty)
    1043                 :          0 :     return empty < 0 ? isl_schedule_free (schedule) : schedule;
    1044                 :            : 
    1045                 :        439 :   isl_union_set *domain = isl_schedule_get_domain (schedule);
    1046                 :            :   /* We cannot apply an empty domain to pbbs in this loop so return early.  */
    1047                 :        439 :   if (isl_union_set_is_empty (domain))
    1048                 :            :     {
    1049                 :          0 :       isl_union_set_free (domain);
    1050                 :          0 :       return schedule;
    1051                 :            :     }
    1052                 :            : 
    1053                 :        439 :   isl_space *space = isl_set_get_space (iterators);
    1054                 :        439 :   int loop_index = isl_space_dim (space, isl_dim_set) - 1;
    1055                 :            : 
    1056                 :        439 :   loop_p ploop = pbb_loop (pbb);
    1057                 :        565 :   while (loop != ploop)
    1058                 :            :     {
    1059                 :        126 :       --loop_index;
    1060                 :        126 :       ploop = loop_outer (ploop);
    1061                 :            :     }
    1062                 :            : 
    1063                 :        439 :   isl_local_space *ls = isl_local_space_from_space (space);
    1064                 :        439 :   isl_aff *aff = isl_aff_var_on_domain (ls, isl_dim_set, loop_index);
    1065                 :        439 :   isl_multi_aff *prefix = isl_multi_aff_from_aff (aff);
    1066                 :        439 :   char name[50];
    1067                 :        439 :   snprintf (name, sizeof(name), "L_%d", loop->num);
    1068                 :        439 :   isl_id *label = isl_id_alloc (isl_schedule_get_ctx (schedule),
    1069                 :            :                                 name, NULL);
    1070                 :        439 :   prefix = isl_multi_aff_set_tuple_id (prefix, isl_dim_out, label);
    1071                 :            : 
    1072                 :        439 :   int n = isl_multi_aff_dim (prefix, isl_dim_in);
    1073                 :        439 :   isl_multi_union_pw_aff *mupa = outer_projection_mupa (domain, n);
    1074                 :        439 :   mupa = isl_multi_union_pw_aff_apply_multi_aff (mupa, prefix);
    1075                 :        439 :   return isl_schedule_insert_partial_schedule (schedule, mupa);
    1076                 :            : }
    1077                 :            : 
    1078                 :            : /* Build schedule for the pbb at INDEX.  */
    1079                 :            : 
    1080                 :            : static isl_schedule *
    1081                 :        527 : build_schedule_pbb (scop_p scop, int *index)
    1082                 :            : {
    1083                 :        527 :   poly_bb_p pbb = scop->pbbs[*index];
    1084                 :        527 :   ++*index;
    1085                 :        527 :   isl_set *domain = isl_set_copy (pbb->domain);
    1086                 :        527 :   isl_union_set *ud = isl_union_set_from_set (domain);
    1087                 :        527 :   return isl_schedule_from_domain (ud);
    1088                 :            : }
    1089                 :            : 
    1090                 :            : static isl_schedule *build_schedule_loop_nest (scop_p, int *, loop_p);
    1091                 :            : 
    1092                 :            : /* Build the schedule of the loop containing the SCOP pbb at INDEX.  */
    1093                 :            : 
    1094                 :            : static isl_schedule *
    1095                 :        315 : build_schedule_loop (scop_p scop, int *index)
    1096                 :            : {
    1097                 :        315 :   int max = scop->pbbs.length ();
    1098                 :        315 :   gcc_assert (*index < max);
    1099                 :        315 :   loop_p loop = loop_at (scop, index);
    1100                 :            : 
    1101                 :        315 :   isl_schedule *s = NULL;
    1102                 :        672 :   while (nested_in (loop_at (scop, index), loop))
    1103                 :            :     {
    1104                 :        496 :       if (loop == loop_at (scop, index))
    1105                 :        430 :         s = add_in_sequence (s, build_schedule_pbb (scop, index));
    1106                 :            :       else
    1107                 :         66 :         s = add_in_sequence (s, build_schedule_loop_nest (scop, index, loop));
    1108                 :            : 
    1109                 :        496 :       if (*index == max)
    1110                 :            :         break;
    1111                 :            :     }
    1112                 :            : 
    1113                 :        315 :   return add_loop_schedule (s, loop, scop);
    1114                 :            : }
    1115                 :            : 
    1116                 :            : /* S is the schedule of the loop LOOP.  Embed the schedule S in all outer loops.
    1117                 :            :    When CONTEXT_LOOP is null, embed the schedule in all loops contained in the
    1118                 :            :    SCOP surrounding LOOP.  When CONTEXT_LOOP is non null, only embed S in the
    1119                 :            :    maximal loop nest contained within CONTEXT_LOOP.  */
    1120                 :            : 
    1121                 :            : static isl_schedule *
    1122                 :        422 : embed_in_surrounding_loops (__isl_take isl_schedule *s, scop_p scop,
    1123                 :            :                             loop_p loop, int *index, loop_p context_loop)
    1124                 :            : {
    1125                 :        422 :   loop_p outer = loop_outer (loop);
    1126                 :        422 :   sese_l region = scop->scop_info->region;
    1127                 :        422 :   if (context_loop == outer
    1128                 :        422 :       || !loop_in_sese_p (outer, region))
    1129                 :        298 :     return s;
    1130                 :            : 
    1131                 :        124 :   int max = scop->pbbs.length ();
    1132                 :        124 :   if (*index == max
    1133                 :         45 :       || (context_loop && !nested_in (loop_at (scop, index), context_loop))
    1134                 :        169 :       || (!context_loop
    1135                 :         45 :           && !loop_in_sese_p (find_common_loop (outer, loop_at (scop, index)),
    1136                 :            :                               region)))
    1137                 :         98 :     return embed_in_surrounding_loops (add_loop_schedule (s, outer, scop),
    1138                 :         98 :                                        scop, outer, index, context_loop);
    1139                 :            : 
    1140                 :         55 :   bool a_pbb;
    1141                 :        110 :   while ((a_pbb = (outer == loop_at (scop, index)))
    1142                 :         55 :          || nested_in (loop_at (scop, index), outer))
    1143                 :            :     {
    1144                 :         45 :       if (a_pbb)
    1145                 :         28 :         s = add_in_sequence (s, build_schedule_pbb (scop, index));
    1146                 :            :       else
    1147                 :         17 :         s = add_in_sequence (s, build_schedule_loop (scop, index));
    1148                 :            : 
    1149                 :         45 :       if (*index == max)
    1150                 :            :         break;
    1151                 :            :     }
    1152                 :            : 
    1153                 :            :   /* We reached the end of the OUTER loop: embed S in OUTER.  */
    1154                 :         26 :   return embed_in_surrounding_loops (add_loop_schedule (s, outer, scop), scop,
    1155                 :         26 :                                      outer, index, context_loop);
    1156                 :            : }
    1157                 :            : 
    1158                 :            : /* Build schedule for the full loop nest containing the pbb at INDEX.  When
    1159                 :            :    CONTEXT_LOOP is null, build the schedule of all loops contained in the SCOP
    1160                 :            :    surrounding the pbb.  When CONTEXT_LOOP is non null, only build the maximal loop
    1161                 :            :    nest contained within CONTEXT_LOOP.  */
    1162                 :            : 
    1163                 :            : static isl_schedule *
    1164                 :        298 : build_schedule_loop_nest (scop_p scop, int *index, loop_p context_loop)
    1165                 :            : {
    1166                 :        596 :   gcc_assert (*index != (int) scop->pbbs.length ());
    1167                 :            : 
    1168                 :        298 :   loop_p loop = loop_at (scop, index);
    1169                 :        298 :   isl_schedule *s = build_schedule_loop (scop, index);
    1170                 :        298 :   return embed_in_surrounding_loops (s, scop, loop, index, context_loop);
    1171                 :            : }
    1172                 :            : 
    1173                 :            : /* Build the schedule of the SCOP.  */
    1174                 :            : 
    1175                 :            : static void
    1176                 :        172 : build_original_schedule (scop_p scop)
    1177                 :            : {
    1178                 :        172 :   int i = 0;
    1179                 :        344 :   int n = scop->pbbs.length ();
    1180                 :        473 :   while (i < n)
    1181                 :            :     {
    1182                 :        301 :       poly_bb_p pbb = scop->pbbs[i];
    1183                 :        301 :       isl_schedule *s = NULL;
    1184                 :        301 :       if (!loop_in_sese_p (pbb_loop (pbb), scop->scop_info->region))
    1185                 :         69 :         s = build_schedule_pbb (scop, &i);
    1186                 :            :       else
    1187                 :        232 :         s = build_schedule_loop_nest (scop, &i, NULL);
    1188                 :            : 
    1189                 :        301 :       scop->original_schedule = add_in_sequence (scop->original_schedule, s);
    1190                 :            :     }
    1191                 :            : 
    1192                 :        172 :   if (dump_file)
    1193                 :            :     {
    1194                 :         93 :       fprintf (dump_file, "[sese-to-poly] original schedule:\n");
    1195                 :         93 :       print_isl_schedule (dump_file, scop->original_schedule);
    1196                 :            :     }
    1197                 :        172 : }
    1198                 :            : 
    1199                 :            : /* Builds the polyhedral representation for a SESE region.  */
    1200                 :            : 
    1201                 :            : bool
    1202                 :        172 : build_poly_scop (scop_p scop)
    1203                 :            : {
    1204                 :        172 :   int old_err = isl_options_get_on_error (scop->isl_context);
    1205                 :        172 :   isl_options_set_on_error (scop->isl_context, ISL_ON_ERROR_CONTINUE);
    1206                 :            : 
    1207                 :        172 :   build_scop_context (scop);
    1208                 :            : 
    1209                 :        172 :   unsigned i = 0;
    1210                 :        344 :   unsigned n = scop->pbbs.length ();
    1211                 :        456 :   while (i < n)
    1212                 :        284 :     i = build_iteration_domains (scop, scop->param_context, i, NULL);
    1213                 :            : 
    1214                 :        172 :   build_scop_drs (scop);
    1215                 :        172 :   build_original_schedule (scop);
    1216                 :            : 
    1217                 :        172 :   enum isl_error err = isl_ctx_last_error (scop->isl_context);
    1218                 :        172 :   isl_ctx_reset_error (scop->isl_context);
    1219                 :        172 :   isl_options_set_on_error (scop->isl_context, old_err);
    1220                 :        172 :   if (err != isl_error_none
    1221                 :        172 :       && dump_enabled_p ())
    1222                 :          0 :     dump_printf (MSG_MISSED_OPTIMIZATION,
    1223                 :            :                  "ISL error while building poly scop\n");
    1224                 :            : 
    1225                 :        172 :   return err == isl_error_none;
    1226                 :            : }
    1227                 :            : #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.