LCOV - code coverage report
Current view: top level - gcc - tree-affine.c (source / functions) Hit Total Coverage
Test: gcc.info Lines: 429 509 84.3 %
Date: 2020-03-28 11:57:23 Functions: 25 29 86.2 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 0 -

           Branch data     Line data    Source code
       1                 :            : /* Operations with affine combinations of trees.
       2                 :            :    Copyright (C) 2005-2020 Free Software Foundation, Inc.
       3                 :            : 
       4                 :            : This file is part of GCC.
       5                 :            : 
       6                 :            : GCC is free software; you can redistribute it and/or modify it
       7                 :            : under the terms of the GNU General Public License as published by the
       8                 :            : Free Software Foundation; either version 3, or (at your option) any
       9                 :            : later version.
      10                 :            : 
      11                 :            : GCC is distributed in the hope that it will be useful, but WITHOUT
      12                 :            : ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
      13                 :            : FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
      14                 :            : for more details.
      15                 :            : 
      16                 :            : You should have received a copy of the GNU General Public License
      17                 :            : along with GCC; see the file COPYING3.  If not see
      18                 :            : <http://www.gnu.org/licenses/>.  */
      19                 :            : 
      20                 :            : #include "config.h"
      21                 :            : #include "system.h"
      22                 :            : #include "coretypes.h"
      23                 :            : #include "backend.h"
      24                 :            : #include "rtl.h"
      25                 :            : #include "tree.h"
      26                 :            : #include "gimple.h"
      27                 :            : #include "ssa.h"
      28                 :            : #include "tree-pretty-print.h"
      29                 :            : #include "fold-const.h"
      30                 :            : #include "tree-affine.h"
      31                 :            : #include "gimplify.h"
      32                 :            : #include "dumpfile.h"
      33                 :            : #include "cfgexpand.h"
      34                 :            : 
      35                 :            : /* Extends CST as appropriate for the affine combinations COMB.  */
      36                 :            : 
      37                 :            : static widest_int
      38                 :   70686900 : wide_int_ext_for_comb (const widest_int &cst, tree type)
      39                 :            : {
      40                 :   70686900 :   return wi::sext (cst, TYPE_PRECISION (type));
      41                 :            : }
      42                 :            : 
      43                 :            : /* Likewise for polynomial offsets.  */
      44                 :            : 
      45                 :            : static poly_widest_int
      46                 :   71289900 : wide_int_ext_for_comb (const poly_widest_int &cst, tree type)
      47                 :            : {
      48                 :   71289900 :   return wi::sext (cst, TYPE_PRECISION (type));
      49                 :            : }
      50                 :            : 
      51                 :            : /* Initializes affine combination COMB so that its value is zero in TYPE.  */
      52                 :            : 
      53                 :            : static void
      54                 :   50361500 : aff_combination_zero (aff_tree *comb, tree type)
      55                 :            : {
      56                 :   50361500 :   int i;
      57                 :   50361500 :   comb->type = type;
      58                 :          0 :   comb->offset = 0;
      59                 :   50361500 :   comb->n = 0;
      60                 :  453253000 :   for (i = 0; i < MAX_AFF_ELTS; i++)
      61                 :  402892000 :     comb->elts[i].coef = 0;
      62                 :   50361500 :   comb->rest = NULL_TREE;
      63                 :          0 : }
      64                 :            : 
      65                 :            : /* Sets COMB to CST.  */
      66                 :            : 
      67                 :            : void
      68                 :   26538100 : aff_combination_const (aff_tree *comb, tree type, const poly_widest_int &cst)
      69                 :            : {
      70                 :   26538100 :   aff_combination_zero (comb, type);
      71                 :   26538100 :   comb->offset = wide_int_ext_for_comb (cst, comb->type);;
      72                 :   26538100 : }
      73                 :            : 
      74                 :            : /* Sets COMB to single element ELT.  */
      75                 :            : 
      76                 :            : void
      77                 :   21602700 : aff_combination_elt (aff_tree *comb, tree type, tree elt)
      78                 :            : {
      79                 :   21602700 :   aff_combination_zero (comb, type);
      80                 :            : 
      81                 :   21602700 :   comb->n = 1;
      82                 :   21602700 :   comb->elts[0].val = elt;
      83                 :   21602700 :   comb->elts[0].coef = 1;
      84                 :   21602700 : }
      85                 :            : 
      86                 :            : /* Scales COMB by SCALE.  */
      87                 :            : 
      88                 :            : void
      89                 :   21207500 : aff_combination_scale (aff_tree *comb, const widest_int &scale_in)
      90                 :            : {
      91                 :   21207500 :   unsigned i, j;
      92                 :            : 
      93                 :   21207500 :   widest_int scale = wide_int_ext_for_comb (scale_in, comb->type);
      94                 :   21207500 :   if (scale == 1)
      95                 :    6348850 :     return;
      96                 :            : 
      97                 :   14858700 :   if (scale == 0)
      98                 :            :     {
      99                 :         20 :       aff_combination_zero (comb, comb->type);
     100                 :         20 :       return;
     101                 :            :     }
     102                 :            : 
     103                 :   14858600 :   comb->offset = wide_int_ext_for_comb (scale * comb->offset, comb->type);
     104                 :   27244200 :   for (i = 0, j = 0; i < comb->n; i++)
     105                 :            :     {
     106                 :   12385600 :       widest_int new_coef
     107                 :   12385600 :         = wide_int_ext_for_comb (scale * comb->elts[i].coef, comb->type);
     108                 :            :       /* A coefficient may become zero due to overflow.  Remove the zero
     109                 :            :          elements.  */
     110                 :   12385600 :       if (new_coef == 0)
     111                 :          4 :         continue;
     112                 :   12385600 :       comb->elts[j].coef = new_coef;
     113                 :   12385600 :       comb->elts[j].val = comb->elts[i].val;
     114                 :   12385600 :       j++;
     115                 :            :     }
     116                 :   14858600 :   comb->n = j;
     117                 :            : 
     118                 :   14858600 :   if (comb->rest)
     119                 :            :     {
     120                 :          0 :       tree type = comb->type;
     121                 :          0 :       if (POINTER_TYPE_P (type))
     122                 :          0 :         type = sizetype;
     123                 :          0 :       if (comb->n < MAX_AFF_ELTS)
     124                 :            :         {
     125                 :          0 :           comb->elts[comb->n].coef = scale;
     126                 :          0 :           comb->elts[comb->n].val = comb->rest;
     127                 :          0 :           comb->rest = NULL_TREE;
     128                 :          0 :           comb->n++;
     129                 :            :         }
     130                 :            :       else
     131                 :          0 :         comb->rest = fold_build2 (MULT_EXPR, type, comb->rest,
     132                 :            :                                   wide_int_to_tree (type, scale));
     133                 :            :     }
     134                 :            : }
     135                 :            : 
     136                 :            : /* Adds ELT * SCALE to COMB.  */
     137                 :            : 
     138                 :            : void
     139                 :   16881700 : aff_combination_add_elt (aff_tree *comb, tree elt, const widest_int &scale_in)
     140                 :            : {
     141                 :   16881700 :   unsigned i;
     142                 :   16881700 :   tree type;
     143                 :            : 
     144                 :   16881700 :   widest_int scale = wide_int_ext_for_comb (scale_in, comb->type);
     145                 :   16881700 :   if (scale == 0)
     146                 :   16881700 :     return;
     147                 :            : 
     148                 :   26278800 :   for (i = 0; i < comb->n; i++)
     149                 :   13977400 :     if (operand_equal_p (comb->elts[i].val, elt, 0))
     150                 :            :       {
     151                 :    4580400 :         widest_int new_coef
     152                 :    4580400 :           = wide_int_ext_for_comb (comb->elts[i].coef + scale, comb->type);
     153                 :    4580400 :         if (new_coef != 0)
     154                 :            :           {
     155                 :      95280 :             comb->elts[i].coef = new_coef;
     156                 :      95280 :             return;
     157                 :            :           }
     158                 :            : 
     159                 :    4485120 :         comb->n--;
     160                 :    4485120 :         comb->elts[i] = comb->elts[comb->n];
     161                 :            : 
     162                 :    4485120 :         if (comb->rest)
     163                 :            :           {
     164                 :          0 :             gcc_assert (comb->n == MAX_AFF_ELTS - 1);
     165                 :          0 :             comb->elts[comb->n].coef = 1;
     166                 :          0 :             comb->elts[comb->n].val = comb->rest;
     167                 :          0 :             comb->rest = NULL_TREE;
     168                 :          0 :             comb->n++;
     169                 :            :           }
     170                 :    4485120 :         return;
     171                 :            :       }
     172                 :   12301300 :   if (comb->n < MAX_AFF_ELTS)
     173                 :            :     {
     174                 :   12301300 :       comb->elts[comb->n].coef = scale;
     175                 :   12301300 :       comb->elts[comb->n].val = elt;
     176                 :   12301300 :       comb->n++;
     177                 :   12301300 :       return;
     178                 :            :     }
     179                 :            : 
     180                 :          0 :   type = comb->type;
     181                 :          0 :   if (POINTER_TYPE_P (type))
     182                 :          0 :     type = sizetype;
     183                 :            : 
     184                 :          0 :   if (scale == 1)
     185                 :          0 :     elt = fold_convert (type, elt);
     186                 :            :   else
     187                 :          0 :     elt = fold_build2 (MULT_EXPR, type,
     188                 :            :                        fold_convert (type, elt),
     189                 :            :                        wide_int_to_tree (type, scale));
     190                 :            : 
     191                 :          0 :   if (comb->rest)
     192                 :          0 :     comb->rest = fold_build2 (PLUS_EXPR, type, comb->rest,
     193                 :            :                               elt);
     194                 :            :   else
     195                 :          0 :     comb->rest = elt;
     196                 :            : }
     197                 :            : 
     198                 :            : /* Adds CST to C.  */
     199                 :            : 
     200                 :            : static void
     201                 :   29822700 : aff_combination_add_cst (aff_tree *c, const poly_widest_int &cst)
     202                 :            : {
     203                 :   29822700 :   c->offset = wide_int_ext_for_comb (c->offset + cst, c->type);
     204                 :   29822700 : }
     205                 :            : 
     206                 :            : /* Adds COMB2 to COMB1.  */
     207                 :            : 
     208                 :            : void
     209                 :   27655100 : aff_combination_add (aff_tree *comb1, aff_tree *comb2)
     210                 :            : {
     211                 :   27655100 :   unsigned i;
     212                 :            : 
     213                 :   27655100 :   aff_combination_add_cst (comb1, comb2->offset);
     214                 :   39771300 :   for (i = 0; i < comb2->n; i++)
     215                 :   12116200 :     aff_combination_add_elt (comb1, comb2->elts[i].val, comb2->elts[i].coef);
     216                 :   27655100 :   if (comb2->rest)
     217                 :          0 :     aff_combination_add_elt (comb1, comb2->rest, 1);
     218                 :   27655100 : }
     219                 :            : 
     220                 :            : /* Converts affine combination COMB to TYPE.  */
     221                 :            : 
     222                 :            : void
     223                 :   17250400 : aff_combination_convert (aff_tree *comb, tree type)
     224                 :            : {
     225                 :   17250400 :   unsigned i, j;
     226                 :   17250400 :   tree comb_type = comb->type;
     227                 :            : 
     228                 :   17250400 :   if  (TYPE_PRECISION (type) > TYPE_PRECISION (comb_type))
     229                 :            :     {
     230                 :     428099 :       tree val = fold_convert (type, aff_combination_to_tree (comb));
     231                 :     428099 :       tree_to_aff_combination (val, type, comb);
     232                 :     428099 :       return;
     233                 :            :     }
     234                 :            : 
     235                 :   16822300 :   comb->type = type;
     236                 :   16822300 :   if (comb->rest && !POINTER_TYPE_P (type))
     237                 :          0 :     comb->rest = fold_convert (type, comb->rest);
     238                 :            : 
     239                 :   16822300 :   if (TYPE_PRECISION (type) == TYPE_PRECISION (comb_type))
     240                 :            :     return;
     241                 :            : 
     242                 :      70373 :   comb->offset = wide_int_ext_for_comb (comb->offset, comb->type);
     243                 :      97958 :   for (i = j = 0; i < comb->n; i++)
     244                 :            :     {
     245                 :      27585 :       if (comb->elts[i].coef == 0)
     246                 :          0 :         continue;
     247                 :      27585 :       comb->elts[j].coef = comb->elts[i].coef;
     248                 :      27585 :       comb->elts[j].val = fold_convert (type, comb->elts[i].val);
     249                 :      27585 :       j++;
     250                 :            :     }
     251                 :            : 
     252                 :      70373 :   comb->n = j;
     253                 :      70373 :   if (comb->n < MAX_AFF_ELTS && comb->rest)
     254                 :            :     {
     255                 :          0 :       comb->elts[comb->n].coef = 1;
     256                 :          0 :       comb->elts[comb->n].val = comb->rest;
     257                 :          0 :       comb->rest = NULL_TREE;
     258                 :          0 :       comb->n++;
     259                 :            :     }
     260                 :            : }
     261                 :            : 
     262                 :            : /* Tries to handle OP0 CODE OP1 as affine combination of parts.  Returns
     263                 :            :    true when that was successful and returns the combination in COMB.  */
     264                 :            : 
     265                 :            : static bool
     266                 :   14156600 : expr_to_aff_combination (aff_tree *comb, tree_code code, tree type,
     267                 :            :                          tree op0, tree op1 = NULL_TREE)
     268                 :            : {
     269                 :   14156600 :   aff_tree tmp;
     270                 :   14156600 :   poly_int64 bitpos, bitsize, bytepos;
     271                 :            : 
     272                 :   14156600 :   switch (code)
     273                 :            :     {
     274                 :    4936720 :     case POINTER_PLUS_EXPR:
     275                 :    4936720 :       tree_to_aff_combination (op0, type, comb);
     276                 :    4936720 :       tree_to_aff_combination (op1, sizetype, &tmp);
     277                 :    4936720 :       aff_combination_add (comb, &tmp);
     278                 :    4936720 :       return true;
     279                 :            : 
     280                 :    4452480 :     case PLUS_EXPR:
     281                 :    4452480 :     case MINUS_EXPR:
     282                 :    4452480 :       tree_to_aff_combination (op0, type, comb);
     283                 :    4452480 :       tree_to_aff_combination (op1, type, &tmp);
     284                 :    4452480 :       if (code == MINUS_EXPR)
     285                 :     385715 :         aff_combination_scale (&tmp, -1);
     286                 :    4452480 :       aff_combination_add (comb, &tmp);
     287                 :    4452480 :       return true;
     288                 :            : 
     289                 :    2947600 :     case MULT_EXPR:
     290                 :    2947600 :       if (TREE_CODE (op1) != INTEGER_CST)
     291                 :            :         break;
     292                 :    2505230 :       tree_to_aff_combination (op0, type, comb);
     293                 :    2505230 :       aff_combination_scale (comb, wi::to_widest (op1));
     294                 :    2505230 :       return true;
     295                 :            : 
     296                 :      19888 :     case NEGATE_EXPR:
     297                 :      19888 :       tree_to_aff_combination (op0, type, comb);
     298                 :      19888 :       aff_combination_scale (comb, -1);
     299                 :      19888 :       return true;
     300                 :            : 
     301                 :       3396 :     case BIT_NOT_EXPR:
     302                 :            :       /* ~x = -x - 1 */
     303                 :       3396 :       tree_to_aff_combination (op0, type, comb);
     304                 :       3396 :       aff_combination_scale (comb, -1);
     305                 :       3396 :       aff_combination_add_cst (comb, -1);
     306                 :       3396 :       return true;
     307                 :            : 
     308                 :    1796530 :     CASE_CONVERT:
     309                 :    1796530 :       {
     310                 :    1796530 :         tree otype = type;
     311                 :    1796530 :         tree inner = op0;
     312                 :    1796530 :         tree itype = TREE_TYPE (inner);
     313                 :    1796530 :         enum tree_code icode = TREE_CODE (inner);
     314                 :            : 
     315                 :            :         /* STRIP_NOPS  */
     316                 :    1796530 :         if (tree_nop_conversion_p (otype, itype))
     317                 :            :           {
     318                 :       5399 :             tree_to_aff_combination (op0, type, comb);
     319                 :       5399 :             return true;
     320                 :            :           }
     321                 :            : 
     322                 :            :         /* In principle this is a valid folding, but it isn't necessarily
     323                 :            :            an optimization, so do it here and not in fold_unary.  */
     324                 :    1791130 :         if ((icode == PLUS_EXPR || icode == MINUS_EXPR || icode == MULT_EXPR)
     325                 :     257505 :             && TREE_CODE (itype) == INTEGER_TYPE
     326                 :     257505 :             && TREE_CODE (otype) == INTEGER_TYPE
     327                 :    2048630 :             && TYPE_PRECISION (otype) > TYPE_PRECISION (itype))
     328                 :            :           {
     329                 :     237206 :             tree op0 = TREE_OPERAND (inner, 0), op1 = TREE_OPERAND (inner, 1);
     330                 :            : 
     331                 :            :             /* If inner type has undefined overflow behavior, fold conversion
     332                 :            :                for below two cases:
     333                 :            :                  (T1)(X *+- CST) -> (T1)X *+- (T1)CST
     334                 :            :                  (T1)(X + X)     -> (T1)X + (T1)X.  */
     335                 :     237206 :             if (TYPE_OVERFLOW_UNDEFINED (itype)
     336                 :     139507 :                 && (TREE_CODE (op1) == INTEGER_CST
     337                 :       4171 :                     || (icode == PLUS_EXPR && operand_equal_p (op0, op1, 0))))
     338                 :            :               {
     339                 :     135336 :                 op0 = fold_convert (otype, op0);
     340                 :     135336 :                 op1 = fold_convert (otype, op1);
     341                 :     165004 :                 return expr_to_aff_combination (comb, icode, otype, op0, op1);
     342                 :            :               }
     343                 :     101870 :             wide_int minv, maxv;
     344                 :            :             /* If inner type has wrapping overflow behavior, fold conversion
     345                 :            :                for below case:
     346                 :            :                  (T1)(X - CST) -> (T1)X - (T1)CST
     347                 :            :                if X - CST doesn't overflow by range information.  Also handle
     348                 :            :                (T1)(X + CST) as (T1)(X - (-CST)).  */
     349                 :     101870 :             if (TYPE_UNSIGNED (itype)
     350                 :      97557 :                 && TYPE_OVERFLOW_WRAPS (itype)
     351                 :      97557 :                 && TREE_CODE (op0) == SSA_NAME
     352                 :      34468 :                 && TREE_CODE (op1) == INTEGER_CST
     353                 :      34436 :                 && icode != MULT_EXPR
     354                 :     136306 :                 && get_range_info (op0, &minv, &maxv) == VR_RANGE)
     355                 :            :               {
     356                 :      30488 :                 if (icode == PLUS_EXPR)
     357                 :      30488 :                   op1 = wide_int_to_tree (itype, -wi::to_wide (op1));
     358                 :      30488 :                 if (wi::geu_p (minv, wi::to_wide (op1)))
     359                 :            :                   {
     360                 :      29668 :                     op0 = fold_convert (otype, op0);
     361                 :      29668 :                     op1 = fold_convert (otype, op1);
     362                 :      29668 :                     return expr_to_aff_combination (comb, MINUS_EXPR, otype,
     363                 :      29668 :                                                     op0, op1);
     364                 :            :                   }
     365                 :            :               }
     366                 :            :           }
     367                 :            :       }
     368                 :            :       break;
     369                 :            : 
     370                 :     442378 :     default:;
     371                 :            :     }
     372                 :            : 
     373                 :            :   return false;
     374                 :            : }
     375                 :            : 
     376                 :            : /* Splits EXPR into an affine combination of parts.  */
     377                 :            : 
     378                 :            : void
     379                 :   58689500 : tree_to_aff_combination (tree expr, tree type, aff_tree *comb)
     380                 :            : {
     381                 :   58689500 :   aff_tree tmp;
     382                 :   58689500 :   enum tree_code code;
     383                 :   58689500 :   tree core, toffset;
     384                 :   58689500 :   poly_int64 bitpos, bitsize, bytepos;
     385                 :   58689500 :   machine_mode mode;
     386                 :   58689500 :   int unsignedp, reversep, volatilep;
     387                 :            : 
     388                 :   58689500 :   STRIP_NOPS (expr);
     389                 :            : 
     390                 :   58689500 :   code = TREE_CODE (expr);
     391                 :   58689500 :   switch (code)
     392                 :            :     {
     393                 :   12145900 :     case POINTER_PLUS_EXPR:
     394                 :   12145900 :     case PLUS_EXPR:
     395                 :   12145900 :     case MINUS_EXPR:
     396                 :   12145900 :     case MULT_EXPR:
     397                 :   12145900 :       if (expr_to_aff_combination (comb, code, type, TREE_OPERAND (expr, 0),
     398                 :   12145900 :                                    TREE_OPERAND (expr, 1)))
     399                 :   37092400 :         return;
     400                 :            :       break;
     401                 :            : 
     402                 :      22946 :     case NEGATE_EXPR:
     403                 :      22946 :     case BIT_NOT_EXPR:
     404                 :      22946 :       if (expr_to_aff_combination (comb, code, type, TREE_OPERAND (expr, 0)))
     405                 :            :         return;
     406                 :            :       break;
     407                 :            : 
     408                 :    1785560 :     CASE_CONVERT:
     409                 :            :       /* ???  TREE_TYPE (expr) should be equal to type here, but IVOPTS
     410                 :            :          calls this with not showing an outer widening cast.  */
     411                 :    3571120 :       if (expr_to_aff_combination (comb, code,
     412                 :    3571120 :                                    TREE_TYPE (expr), TREE_OPERAND (expr, 0)))
     413                 :            :         {
     414                 :     165004 :           aff_combination_convert (comb, type);
     415                 :     165004 :           return;
     416                 :            :         }
     417                 :            :       break;
     418                 :            : 
     419                 :    4231580 :     case ADDR_EXPR:
     420                 :            :       /* Handle &MEM[ptr + CST] which is equivalent to POINTER_PLUS_EXPR.  */
     421                 :    4231580 :       if (TREE_CODE (TREE_OPERAND (expr, 0)) == MEM_REF)
     422                 :            :         {
     423                 :     222336 :           expr = TREE_OPERAND (expr, 0);
     424                 :     222336 :           tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb);
     425                 :     222336 :           tree_to_aff_combination (TREE_OPERAND (expr, 1), sizetype, &tmp);
     426                 :     222336 :           aff_combination_add (comb, &tmp);
     427                 :     222336 :           return;
     428                 :            :         }
     429                 :    4009240 :       core = get_inner_reference (TREE_OPERAND (expr, 0), &bitsize, &bitpos,
     430                 :            :                                   &toffset, &mode, &unsignedp, &reversep,
     431                 :            :                                   &volatilep);
     432                 :    8018490 :       if (!multiple_p (bitpos, BITS_PER_UNIT, &bytepos))
     433                 :            :         break;
     434                 :    4009240 :       aff_combination_const (comb, type, bytepos);
     435                 :    4009240 :       if (TREE_CODE (core) == MEM_REF)
     436                 :            :         {
     437                 :     162680 :           tree mem_offset = TREE_OPERAND (core, 1);
     438                 :     162680 :           aff_combination_add_cst (comb, wi::to_poly_widest (mem_offset));
     439                 :     162680 :           core = TREE_OPERAND (core, 0);
     440                 :            :         }
     441                 :            :       else
     442                 :    3846560 :         core = build_fold_addr_expr (core);
     443                 :            : 
     444                 :    4009240 :       if (TREE_CODE (core) == ADDR_EXPR)
     445                 :    3846560 :         aff_combination_add_elt (comb, core, 1);
     446                 :            :       else
     447                 :            :         {
     448                 :     162680 :           tree_to_aff_combination (core, type, &tmp);
     449                 :     162680 :           aff_combination_add (comb, &tmp);
     450                 :            :         }
     451                 :    4009240 :       if (toffset)
     452                 :            :         {
     453                 :      51721 :           tree_to_aff_combination (toffset, type, &tmp);
     454                 :      51721 :           aff_combination_add (comb, &tmp);
     455                 :            :         }
     456                 :            :       return;
     457                 :            : 
     458                 :   40503500 :     default:
     459                 :   40503500 :       {
     460                 :   40503500 :         if (poly_int_tree_p (expr))
     461                 :            :           {
     462                 :   20962000 :             aff_combination_const (comb, type, wi::to_poly_widest (expr));
     463                 :   20962000 :             return;
     464                 :            :           }
     465                 :            :         break;
     466                 :            :       }
     467                 :            :     }
     468                 :            : 
     469                 :   21597100 :   aff_combination_elt (comb, type, expr);
     470                 :            : }
     471                 :            : 
     472                 :            : /* Creates EXPR + ELT * SCALE in TYPE.  EXPR is taken from affine
     473                 :            :    combination COMB.  */
     474                 :            : 
     475                 :            : static tree
     476                 :   15631700 : add_elt_to_tree (tree expr, tree type, tree elt, const widest_int &scale_in)
     477                 :            : {
     478                 :   15631700 :   enum tree_code code;
     479                 :            : 
     480                 :   15631700 :   widest_int scale = wide_int_ext_for_comb (scale_in, type);
     481                 :            : 
     482                 :   15631700 :   elt = fold_convert (type, elt);
     483                 :   15631700 :   if (scale == 1)
     484                 :            :     {
     485                 :   12253300 :       if (!expr)
     486                 :            :         return elt;
     487                 :            : 
     488                 :    4857690 :       return fold_build2 (PLUS_EXPR, type, expr, elt);
     489                 :            :     }
     490                 :            : 
     491                 :    3378410 :   if (scale == -1)
     492                 :            :     {
     493                 :    1605190 :       if (!expr)
     494                 :     947065 :         return fold_build1 (NEGATE_EXPR, type, elt);
     495                 :            : 
     496                 :     658125 :       return fold_build2 (MINUS_EXPR, type, expr, elt);
     497                 :            :     }
     498                 :            : 
     499                 :    1773220 :   if (!expr)
     500                 :     555860 :     return fold_build2 (MULT_EXPR, type, elt, wide_int_to_tree (type, scale));
     501                 :            : 
     502                 :    1217360 :   if (wi::neg_p (scale))
     503                 :            :     {
     504                 :     272570 :       code = MINUS_EXPR;
     505                 :     272570 :       scale = -scale;
     506                 :            :     }
     507                 :            :   else
     508                 :            :     code = PLUS_EXPR;
     509                 :            : 
     510                 :    1217360 :   elt = fold_build2 (MULT_EXPR, type, elt, wide_int_to_tree (type, scale));
     511                 :    1217360 :   return fold_build2 (code, type, expr, elt);
     512                 :            : }
     513                 :            : 
     514                 :            : /* Makes tree from the affine combination COMB.  */
     515                 :            : 
     516                 :            : tree
     517                 :    8898520 : aff_combination_to_tree (aff_tree *comb)
     518                 :            : {
     519                 :    8898520 :   tree type = comb->type, base = NULL_TREE, expr = NULL_TREE;
     520                 :    8898520 :   unsigned i;
     521                 :    8898520 :   poly_widest_int off;
     522                 :    8898520 :   int sgn;
     523                 :            : 
     524                 :    8898520 :   gcc_assert (comb->n == MAX_AFF_ELTS || comb->rest == NULL_TREE);
     525                 :            : 
     526                 :    8898520 :   i = 0;
     527                 :    8898520 :   if (POINTER_TYPE_P (type))
     528                 :            :     {
     529                 :     551338 :       type = sizetype;
     530                 :    9449730 :       if (comb->n > 0 && comb->elts[0].coef == 1
     531                 :    1102500 :           && POINTER_TYPE_P (TREE_TYPE (comb->elts[0].val)))
     532                 :            :         {
     533                 :    8898520 :           base = comb->elts[0].val;
     534                 :    8898520 :           ++i;
     535                 :            :         }
     536                 :            :     }
     537                 :            : 
     538                 :   15631700 :   for (; i < comb->n; i++)
     539                 :    6733170 :     expr = add_elt_to_tree (expr, type, comb->elts[i].val, comb->elts[i].coef);
     540                 :            : 
     541                 :    8898520 :   if (comb->rest)
     542                 :          0 :     expr = add_elt_to_tree (expr, type, comb->rest, 1);
     543                 :            : 
     544                 :            :   /* Ensure that we get x - 1, not x + (-1) or x + 0xff..f if x is
     545                 :            :      unsigned.  */
     546                 :    8898520 :   if (known_lt (comb->offset, 0))
     547                 :            :     {
     548                 :    1222920 :       off = -comb->offset;
     549                 :    1222920 :       sgn = -1;
     550                 :            :     }
     551                 :            :   else
     552                 :            :     {
     553                 :    7675600 :       off = comb->offset;
     554                 :    7675600 :       sgn = 1;
     555                 :            :     }
     556                 :    8898520 :   expr = add_elt_to_tree (expr, type, wide_int_to_tree (type, off), sgn);
     557                 :            : 
     558                 :    8898520 :   if (base)
     559                 :     549854 :     return fold_build_pointer_plus (base, expr);
     560                 :            :   else
     561                 :    8348660 :     return fold_convert (comb->type, expr);
     562                 :            : }
     563                 :            : 
     564                 :            : /* Copies the tree elements of COMB to ensure that they are not shared.  */
     565                 :            : 
     566                 :            : void
     567                 :    1112320 : unshare_aff_combination (aff_tree *comb)
     568                 :            : {
     569                 :    1112320 :   unsigned i;
     570                 :            : 
     571                 :    2395460 :   for (i = 0; i < comb->n; i++)
     572                 :    1283140 :     comb->elts[i].val = unshare_expr (comb->elts[i].val);
     573                 :    1112320 :   if (comb->rest)
     574                 :          0 :     comb->rest = unshare_expr (comb->rest);
     575                 :    1112320 : }
     576                 :            : 
     577                 :            : /* Remove M-th element from COMB.  */
     578                 :            : 
     579                 :            : void
     580                 :    1007250 : aff_combination_remove_elt (aff_tree *comb, unsigned m)
     581                 :            : {
     582                 :    1007250 :   comb->n--;
     583                 :    1007250 :   if (m <= comb->n)
     584                 :    1007250 :     comb->elts[m] = comb->elts[comb->n];
     585                 :    1007250 :   if (comb->rest)
     586                 :            :     {
     587                 :          0 :       comb->elts[comb->n].coef = 1;
     588                 :          0 :       comb->elts[comb->n].val = comb->rest;
     589                 :          0 :       comb->rest = NULL_TREE;
     590                 :          0 :       comb->n++;
     591                 :            :     }
     592                 :    1007250 : }
     593                 :            : 
     594                 :            : /* Adds C * COEF * VAL to R.  VAL may be NULL, in that case only
     595                 :            :    C * COEF is added to R.  */
     596                 :            : 
     597                 :            : 
     598                 :            : static void
     599                 :    2001510 : aff_combination_add_product (aff_tree *c, const widest_int &coef, tree val,
     600                 :            :                              aff_tree *r)
     601                 :            : {
     602                 :    2001510 :   unsigned i;
     603                 :    2001510 :   tree aval, type;
     604                 :            : 
     605                 :    2862100 :   for (i = 0; i < c->n; i++)
     606                 :            :     {
     607                 :     860588 :       aval = c->elts[i].val;
     608                 :     860588 :       if (val)
     609                 :            :         {
     610                 :          0 :           type = TREE_TYPE (aval);
     611                 :          0 :           aval = fold_build2 (MULT_EXPR, type, aval,
     612                 :            :                               fold_convert (type, val));
     613                 :            :         }
     614                 :            : 
     615                 :     860588 :       aff_combination_add_elt (r, aval, coef * c->elts[i].coef);
     616                 :            :     }
     617                 :            : 
     618                 :    2001510 :   if (c->rest)
     619                 :            :     {
     620                 :          0 :       aval = c->rest;
     621                 :          0 :       if (val)
     622                 :            :         {
     623                 :          0 :           type = TREE_TYPE (aval);
     624                 :          0 :           aval = fold_build2 (MULT_EXPR, type, aval,
     625                 :            :                               fold_convert (type, val));
     626                 :            :         }
     627                 :            : 
     628                 :          0 :       aff_combination_add_elt (r, aval, coef);
     629                 :            :     }
     630                 :            : 
     631                 :    2001510 :   if (val)
     632                 :            :     {
     633                 :          0 :       if (c->offset.is_constant ())
     634                 :            :         /* Access coeffs[0] directly, for efficiency.  */
     635                 :          0 :         aff_combination_add_elt (r, val, coef * c->offset.coeffs[0]);
     636                 :            :       else
     637                 :            :         {
     638                 :            :           /* c->offset is polynomial, so multiply VAL rather than COEF
     639                 :            :              by it.  */
     640                 :            :           tree offset = wide_int_to_tree (TREE_TYPE (val), c->offset);
     641                 :            :           val = fold_build2 (MULT_EXPR, TREE_TYPE (val), val, offset);
     642                 :            :           aff_combination_add_elt (r, val, coef);
     643                 :            :         }
     644                 :            :     }
     645                 :            :   else
     646                 :    2001510 :     aff_combination_add_cst (r, coef * c->offset);
     647                 :    2001510 : }
     648                 :            : 
     649                 :            : /* Multiplies C1 by C2, storing the result to R  */
     650                 :            : 
     651                 :            : void
     652                 :    2001510 : aff_combination_mult (aff_tree *c1, aff_tree *c2, aff_tree *r)
     653                 :            : {
     654                 :    2001510 :   unsigned i;
     655                 :    2001510 :   gcc_assert (TYPE_PRECISION (c1->type) == TYPE_PRECISION (c2->type));
     656                 :            : 
     657                 :    2001510 :   aff_combination_zero (r, c1->type);
     658                 :            : 
     659                 :    2001510 :   for (i = 0; i < c2->n; i++)
     660                 :          0 :     aff_combination_add_product (c1, c2->elts[i].coef, c2->elts[i].val, r);
     661                 :    2001510 :   if (c2->rest)
     662                 :          0 :     aff_combination_add_product (c1, 1, c2->rest, r);
     663                 :    2001510 :   if (c2->offset.is_constant ())
     664                 :            :     /* Access coeffs[0] directly, for efficiency.  */
     665                 :    2001510 :     aff_combination_add_product (c1, c2->offset.coeffs[0], NULL, r);
     666                 :            :   else
     667                 :            :     {
     668                 :            :       /* c2->offset is polynomial, so do the multiplication in tree form.  */
     669                 :            :       tree offset = wide_int_to_tree (c2->type, c2->offset);
     670                 :            :       aff_combination_add_product (c1, 1, offset, r);
     671                 :            :     }
     672                 :    2001510 : }
     673                 :            : 
     674                 :            : /* Returns the element of COMB whose value is VAL, or NULL if no such
     675                 :            :    element exists.  If IDX is not NULL, it is set to the index of VAL in
     676                 :            :    COMB.  */
     677                 :            : 
     678                 :            : static class aff_comb_elt *
     679                 :       1317 : aff_combination_find_elt (aff_tree *comb, tree val, unsigned *idx)
     680                 :            : {
     681                 :       1317 :   unsigned i;
     682                 :            : 
     683                 :       2617 :   for (i = 0; i < comb->n; i++)
     684                 :       1317 :     if (operand_equal_p (comb->elts[i].val, val, 0))
     685                 :            :       {
     686                 :          0 :         if (idx)
     687                 :          0 :           *idx = i;
     688                 :            : 
     689                 :         17 :         return &comb->elts[i];
     690                 :            :       }
     691                 :            : 
     692                 :            :   return NULL;
     693                 :            : }
     694                 :            : 
     695                 :            : /* Element of the cache that maps ssa name NAME to its expanded form
     696                 :            :    as an affine expression EXPANSION.  */
     697                 :            : 
     698                 :            : class name_expansion
     699                 :            : {
     700                 :            : public:
     701                 :            :   aff_tree expansion;
     702                 :            : 
     703                 :            :   /* True if the expansion for the name is just being generated.  */
     704                 :            :   unsigned in_progress : 1;
     705                 :            : };
     706                 :            : 
     707                 :            : /* Expands SSA names in COMB recursively.  CACHE is used to cache the
     708                 :            :    results.  */
     709                 :            : 
     710                 :            : void
     711                 :     168759 : aff_combination_expand (aff_tree *comb ATTRIBUTE_UNUSED,
     712                 :            :                         hash_map<tree, name_expansion *> **cache)
     713                 :            : {
     714                 :     168759 :   unsigned i;
     715                 :     168759 :   aff_tree to_add, current, curre;
     716                 :     168759 :   tree e;
     717                 :     168759 :   gimple *def;
     718                 :     168759 :   widest_int scale;
     719                 :     168759 :   class name_expansion *exp;
     720                 :            : 
     721                 :     168759 :   aff_combination_zero (&to_add, comb->type);
     722                 :     329853 :   for (i = 0; i < comb->n; i++)
     723                 :            :     {
     724                 :     161094 :       tree type, name;
     725                 :     161094 :       enum tree_code code;
     726                 :            : 
     727                 :     161094 :       e = comb->elts[i].val;
     728                 :     161094 :       type = TREE_TYPE (e);
     729                 :     161094 :       name = e;
     730                 :            :       /* Look through some conversions.  */
     731                 :     147983 :       if (CONVERT_EXPR_P (e)
     732                 :     161094 :           && (TYPE_PRECISION (type)
     733                 :      13111 :               >= TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (e, 0)))))
     734                 :      12972 :         name = TREE_OPERAND (e, 0);
     735                 :     161094 :       if (TREE_CODE (name) != SSA_NAME)
     736                 :     110752 :         continue;
     737                 :     135229 :       def = SSA_NAME_DEF_STMT (name);
     738                 :     135229 :       if (!is_gimple_assign (def) || gimple_assign_lhs (def) != name)
     739                 :      44976 :         continue;
     740                 :            : 
     741                 :      90253 :       code = gimple_assign_rhs_code (def);
     742                 :      92333 :       if (code != SSA_NAME
     743                 :      90216 :           && !IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code))
     744                 :      92347 :           && (get_gimple_rhs_class (code) != GIMPLE_SINGLE_RHS
     745                 :       2094 :               || !is_gimple_min_invariant (gimple_assign_rhs1 (def))))
     746                 :       2080 :         continue;
     747                 :            : 
     748                 :            :       /* We do not know whether the reference retains its value at the
     749                 :            :          place where the expansion is used.  */
     750                 :      88173 :       if (TREE_CODE_CLASS (code) == tcc_reference)
     751                 :      28894 :         continue;
     752                 :            : 
     753                 :      59279 :       name_expansion **slot = NULL;
     754                 :      59279 :       if (*cache)
     755                 :      46309 :         slot = (*cache)->get (name);
     756                 :      20359 :       exp = slot ? *slot : NULL;
     757                 :      59279 :       if (!exp)
     758                 :            :         {
     759                 :            :           /* Only bother to handle cases tree_to_aff_combination will.  */
     760                 :      38920 :           switch (code)
     761                 :            :             {
     762                 :      25882 :             case POINTER_PLUS_EXPR:
     763                 :      25882 :             case PLUS_EXPR:
     764                 :      25882 :             case MINUS_EXPR:
     765                 :      25882 :             case MULT_EXPR:
     766                 :      25882 :               if (!expr_to_aff_combination (&current, code, TREE_TYPE (name),
     767                 :            :                                             gimple_assign_rhs1 (def),
     768                 :            :                                             gimple_assign_rhs2 (def)))
     769                 :       7284 :                 continue;
     770                 :            :               break;
     771                 :        338 :             case NEGATE_EXPR:
     772                 :        338 :             case BIT_NOT_EXPR:
     773                 :        338 :               if (!expr_to_aff_combination (&current, code, TREE_TYPE (name),
     774                 :            :                                             gimple_assign_rhs1 (def)))
     775                 :          0 :                 continue;
     776                 :            :               break;
     777                 :      10969 :             CASE_CONVERT:
     778                 :      10969 :               if (!expr_to_aff_combination (&current, code, TREE_TYPE (name),
     779                 :            :                                             gimple_assign_rhs1 (def)))
     780                 :            :                 /* This makes us always expand conversions which we did
     781                 :            :                    in the past and makes gcc.dg/tree-ssa/ivopts-lt-2.c
     782                 :            :                    PASS, eliminating one induction variable in IVOPTs.
     783                 :            :                    ???  But it is really excessive and we should try
     784                 :            :                    harder to do without it.  */
     785                 :      11140 :                 aff_combination_elt (&current, TREE_TYPE (name),
     786                 :       5570 :                                      fold_convert (TREE_TYPE (name),
     787                 :            :                                                    gimple_assign_rhs1 (def)));
     788                 :            :               break;
     789                 :         78 :             case ADDR_EXPR:
     790                 :         78 :             case INTEGER_CST:
     791                 :         78 :             case POLY_INT_CST:
     792                 :        234 :               tree_to_aff_combination (gimple_assign_rhs1 (def),
     793                 :         78 :                                        TREE_TYPE (name), &current);
     794                 :         78 :               break;
     795                 :       1653 :             default:
     796                 :       1653 :               continue;
     797                 :            :             }
     798                 :      29983 :           exp = XNEW (class name_expansion);
     799                 :      29983 :           exp->in_progress = 1;
     800                 :      29983 :           if (!*cache)
     801                 :      11408 :             *cache = new hash_map<tree, name_expansion *>;
     802                 :      29983 :           (*cache)->put (name, exp);
     803                 :      29983 :           aff_combination_expand (&current, cache);
     804                 :      29983 :           exp->expansion = current;
     805                 :      29983 :           exp->in_progress = 0;
     806                 :            :         }
     807                 :            :       else
     808                 :            :         {
     809                 :            :           /* Since we follow the definitions in the SSA form, we should not
     810                 :            :              enter a cycle unless we pass through a phi node.  */
     811                 :      20359 :           gcc_assert (!exp->in_progress);
     812                 :      20359 :           current = exp->expansion;
     813                 :            :         }
     814                 :      50342 :       if (!useless_type_conversion_p (comb->type, current.type))
     815                 :      13691 :         aff_combination_convert (&current, comb->type);
     816                 :            : 
     817                 :            :       /* Accumulate the new terms to TO_ADD, so that we do not modify
     818                 :            :          COMB while traversing it; include the term -coef * E, to remove
     819                 :            :          it from COMB.  */
     820                 :      50342 :       scale = comb->elts[i].coef;
     821                 :      50342 :       aff_combination_zero (&curre, comb->type);
     822                 :      50342 :       aff_combination_add_elt (&curre, e, -scale);
     823                 :      50342 :       aff_combination_scale (&current, scale);
     824                 :      50342 :       aff_combination_add (&to_add, &current);
     825                 :      50342 :       aff_combination_add (&to_add, &curre);
     826                 :            :     }
     827                 :     168759 :   aff_combination_add (comb, &to_add);
     828                 :     168759 : }
     829                 :            : 
     830                 :            : /* Similar to tree_to_aff_combination, but follows SSA name definitions
     831                 :            :    and expands them recursively.  CACHE is used to cache the expansions
     832                 :            :    of the ssa names, to avoid exponential time complexity for cases
     833                 :            :    like
     834                 :            : 
     835                 :            :    a1 = a0 + a0;
     836                 :            :    a2 = a1 + a1;
     837                 :            :    a3 = a2 + a2;
     838                 :            :    ...  */
     839                 :            : 
     840                 :            : void
     841                 :      97718 : tree_to_aff_combination_expand (tree expr, tree type, aff_tree *comb,
     842                 :            :                                 hash_map<tree, name_expansion *> **cache)
     843                 :            : {
     844                 :      97718 :   tree_to_aff_combination (expr, type, comb);
     845                 :      97718 :   aff_combination_expand (comb, cache);
     846                 :      97718 : }
     847                 :            : 
     848                 :            : /* Frees memory occupied by struct name_expansion in *VALUE.  Callback for
     849                 :            :    hash_map::traverse.  */
     850                 :            : 
     851                 :            : bool
     852                 :      29983 : free_name_expansion (tree const &, name_expansion **value, void *)
     853                 :            : {
     854                 :      29983 :   free (*value);
     855                 :      29983 :   return true;
     856                 :            : }
     857                 :            : 
     858                 :            : /* Frees memory allocated for the CACHE used by
     859                 :            :    tree_to_aff_combination_expand.  */
     860                 :            : 
     861                 :            : void
     862                 :     886989 : free_affine_expand_cache (hash_map<tree, name_expansion *> **cache)
     863                 :            : {
     864                 :     886989 :   if (!*cache)
     865                 :            :     return;
     866                 :            : 
     867                 :      11408 :   (*cache)->traverse<void *, free_name_expansion> (NULL);
     868                 :      22816 :   delete (*cache);
     869                 :      11408 :   *cache = NULL;
     870                 :            : }
     871                 :            : 
     872                 :            : /* If VAL != CST * DIV for any constant CST, returns false.
     873                 :            :    Otherwise, if *MULT_SET is true, additionally compares CST and MULT,
     874                 :            :    and if they are different, returns false.  Finally, if neither of these
     875                 :            :    two cases occur, true is returned, and CST is stored to MULT and MULT_SET
     876                 :            :    is set to true.  */
     877                 :            : 
     878                 :            : static bool
     879                 :       5690 : wide_int_constant_multiple_p (const poly_widest_int &val,
     880                 :            :                               const poly_widest_int &div,
     881                 :            :                               bool *mult_set, poly_widest_int *mult)
     882                 :            : {
     883                 :       5690 :   poly_widest_int rem, cst;
     884                 :            : 
     885                 :       5690 :   if (known_eq (val, 0))
     886                 :            :     {
     887                 :       1309 :       if (*mult_set && maybe_ne (*mult, 0))
     888                 :            :         return false;
     889                 :       1309 :       *mult_set = true;
     890                 :       1309 :       *mult = 0;
     891                 :       1309 :       return true;
     892                 :            :     }
     893                 :            : 
     894                 :       4381 :   if (maybe_eq (div, 0))
     895                 :            :     return false;
     896                 :            : 
     897                 :       4381 :   if (!multiple_p (val, div, &cst))
     898                 :            :     return false;
     899                 :            : 
     900                 :       3688 :   if (*mult_set && maybe_ne (*mult, cst))
     901                 :            :     return false;
     902                 :            : 
     903                 :       3668 :   *mult_set = true;
     904                 :       3668 :   *mult = cst;
     905                 :       3668 :   return true;
     906                 :            : }
     907                 :            : 
     908                 :            : /* Returns true if VAL = X * DIV for some constant X.  If this is the case,
     909                 :            :    X is stored to MULT.  */
     910                 :            : 
     911                 :            : bool
     912                 :      21465 : aff_combination_constant_multiple_p (aff_tree *val, aff_tree *div,
     913                 :            :                                      poly_widest_int *mult)
     914                 :            : {
     915                 :      21465 :   bool mult_set = false;
     916                 :      21465 :   unsigned i;
     917                 :            : 
     918                 :      21465 :   if (val->n == 0 && known_eq (val->offset, 0))
     919                 :            :     {
     920                 :      11350 :       *mult = 0;
     921                 :      11350 :       return true;
     922                 :            :     }
     923                 :      10115 :   if (val->n != div->n)
     924                 :            :     return false;
     925                 :            : 
     926                 :       5673 :   if (val->rest || div->rest)
     927                 :            :     return false;
     928                 :            : 
     929                 :       5673 :   if (!wide_int_constant_multiple_p (val->offset, div->offset,
     930                 :            :                                      &mult_set, mult))
     931                 :            :     return false;
     932                 :            : 
     933                 :       4977 :   for (i = 0; i < div->n; i++)
     934                 :            :     {
     935                 :       1317 :       class aff_comb_elt *elt
     936                 :       1317 :               = aff_combination_find_elt (val, div->elts[i].val, NULL);
     937                 :       1317 :       if (!elt)
     938                 :            :         return false;
     939                 :         17 :       if (!wide_int_constant_multiple_p (elt->coef, div->elts[i].coef,
     940                 :            :                                          &mult_set, mult))
     941                 :            :         return false;
     942                 :            :     }
     943                 :            : 
     944                 :       3660 :   gcc_assert (mult_set);
     945                 :            :   return true;
     946                 :            : }
     947                 :            : 
     948                 :            : /* Prints the affine VAL to the FILE. */
     949                 :            : 
     950                 :            : static void
     951                 :          0 : print_aff (FILE *file, aff_tree *val)
     952                 :            : {
     953                 :          0 :   unsigned i;
     954                 :          0 :   signop sgn = TYPE_SIGN (val->type);
     955                 :          0 :   if (POINTER_TYPE_P (val->type))
     956                 :          0 :     sgn = SIGNED;
     957                 :          0 :   fprintf (file, "{\n  type = ");
     958                 :          0 :   print_generic_expr (file, val->type, TDF_VOPS|TDF_MEMSYMS);
     959                 :          0 :   fprintf (file, "\n  offset = ");
     960                 :          0 :   print_dec (val->offset, file, sgn);
     961                 :          0 :   if (val->n > 0)
     962                 :            :     {
     963                 :          0 :       fprintf (file, "\n  elements = {\n");
     964                 :          0 :       for (i = 0; i < val->n; i++)
     965                 :            :         {
     966                 :          0 :           fprintf (file, "    [%d] = ", i);
     967                 :          0 :           print_generic_expr (file, val->elts[i].val, TDF_VOPS|TDF_MEMSYMS);
     968                 :            : 
     969                 :          0 :           fprintf (file, " * ");
     970                 :          0 :           print_dec (val->elts[i].coef, file, sgn);
     971                 :          0 :           if (i != val->n - 1)
     972                 :          0 :             fprintf (file, ", \n");
     973                 :            :         }
     974                 :          0 :       fprintf (file, "\n  }");
     975                 :            :   }
     976                 :          0 :   if (val->rest)
     977                 :            :     {
     978                 :          0 :       fprintf (file, "\n  rest = ");
     979                 :          0 :       print_generic_expr (file, val->rest, TDF_VOPS|TDF_MEMSYMS);
     980                 :            :     }
     981                 :          0 :   fprintf (file, "\n}");
     982                 :          0 : }
     983                 :            : 
     984                 :            : /* Prints the affine VAL to the standard error, used for debugging.  */
     985                 :            : 
     986                 :            : DEBUG_FUNCTION void
     987                 :          0 : debug_aff (aff_tree *val)
     988                 :            : {
     989                 :          0 :   print_aff (stderr, val);
     990                 :          0 :   fprintf (stderr, "\n");
     991                 :          0 : }
     992                 :            : 
     993                 :            : /* Computes address of the reference REF in ADDR.  The size of the accessed
     994                 :            :    location is stored to SIZE.  Returns the ultimate containing object to
     995                 :            :    which REF refers.  */
     996                 :            : 
     997                 :            : tree
     998                 :    1523960 : get_inner_reference_aff (tree ref, aff_tree *addr, poly_widest_int *size)
     999                 :            : {
    1000                 :    1523960 :   poly_int64 bitsize, bitpos;
    1001                 :    1523960 :   tree toff;
    1002                 :    1523960 :   machine_mode mode;
    1003                 :    1523960 :   int uns, rev, vol;
    1004                 :    1523960 :   aff_tree tmp;
    1005                 :    1523960 :   tree base = get_inner_reference (ref, &bitsize, &bitpos, &toff, &mode,
    1006                 :            :                                    &uns, &rev, &vol);
    1007                 :    1523960 :   tree base_addr = build_fold_addr_expr (base);
    1008                 :            : 
    1009                 :            :   /* ADDR = &BASE + TOFF + BITPOS / BITS_PER_UNIT.  */
    1010                 :            : 
    1011                 :    1523960 :   tree_to_aff_combination (base_addr, sizetype, addr);
    1012                 :            : 
    1013                 :    1523960 :   if (toff)
    1014                 :            :     {
    1015                 :     226527 :       tree_to_aff_combination (toff, sizetype, &tmp);
    1016                 :     226527 :       aff_combination_add (addr, &tmp);
    1017                 :            :     }
    1018                 :            : 
    1019                 :    1523960 :   aff_combination_const (&tmp, sizetype, bits_to_bytes_round_down (bitpos));
    1020                 :    1523960 :   aff_combination_add (addr, &tmp);
    1021                 :            : 
    1022                 :    1523960 :   *size = bits_to_bytes_round_up (bitsize);
    1023                 :            : 
    1024                 :    1523960 :   return base;
    1025                 :            : }
    1026                 :            : 
    1027                 :            : /* Returns true if a region of size SIZE1 at position 0 and a region of
    1028                 :            :    size SIZE2 at position DIFF cannot overlap.  */
    1029                 :            : 
    1030                 :            : bool
    1031                 :     761982 : aff_comb_cannot_overlap_p (aff_tree *diff, const poly_widest_int &size1,
    1032                 :            :                            const poly_widest_int &size2)
    1033                 :            : {
    1034                 :            :   /* Unless the difference is a constant, we fail.  */
    1035                 :     761982 :   if (diff->n != 0)
    1036                 :            :     return false;
    1037                 :            : 
    1038                 :     628640 :   if (!ordered_p (diff->offset, 0))
    1039                 :            :     return false;
    1040                 :            : 
    1041                 :     628640 :   if (maybe_lt (diff->offset, 0))
    1042                 :            :     {
    1043                 :            :       /* The second object is before the first one, we succeed if the last
    1044                 :            :          element of the second object is before the start of the first one.  */
    1045                 :      67383 :       return known_le (diff->offset + size2, 0);
    1046                 :            :     }
    1047                 :            :   else
    1048                 :            :     {
    1049                 :            :       /* We succeed if the second object starts after the first one ends.  */
    1050                 :     561257 :       return known_le (size1, diff->offset);
    1051                 :            :     }
    1052                 :            : }
    1053                 :            : 

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.