LCOV - code coverage report
Current view: top level - gcc - tree-affine.cc (source / functions) Coverage Total Hit
Test: gcc.info Lines: 89.2 % 528 471
Test Date: 2024-03-23 14:05:01 Functions: 93.1 % 29 27
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-2024 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                 :             : #include "value-query.h"
      35                 :             : 
      36                 :             : /* Extends CST as appropriate for the affine combinations COMB.  */
      37                 :             : 
      38                 :             : static widest_int
      39                 :   100964750 : wide_int_ext_for_comb (const widest_int &cst, tree type)
      40                 :             : {
      41                 :   100964750 :   return wi::sext (cst, TYPE_PRECISION (type));
      42                 :             : }
      43                 :             : 
      44                 :             : /* Likewise for polynomial offsets.  */
      45                 :             : 
      46                 :             : static poly_widest_int
      47                 :   111398082 : wide_int_ext_for_comb (const poly_widest_int &cst, tree type)
      48                 :             : {
      49                 :   111398082 :   return wi::sext (cst, TYPE_PRECISION (type));
      50                 :             : }
      51                 :             : 
      52                 :             : /* Initializes affine combination COMB so that its value is zero in TYPE.  */
      53                 :             : 
      54                 :             : static void
      55                 :    76940214 : aff_combination_zero (aff_tree *comb, tree type)
      56                 :             : {
      57                 :    76940214 :   int i;
      58                 :    76940214 :   comb->type = type;
      59                 :    76940214 :   comb->offset = 0;
      60                 :    76940214 :   comb->n = 0;
      61                 :   692461926 :   for (i = 0; i < MAX_AFF_ELTS; i++)
      62                 :   615521712 :     comb->elts[i].coef = 0;
      63                 :    76940214 :   comb->rest = NULL_TREE;
      64                 :    76940214 : }
      65                 :             : 
      66                 :             : /* Sets COMB to CST.  */
      67                 :             : 
      68                 :             : void
      69                 :    43630055 : aff_combination_const (aff_tree *comb, tree type, const poly_widest_int &cst)
      70                 :             : {
      71                 :    43630055 :   aff_combination_zero (comb, type);
      72                 :    43630055 :   comb->offset = wide_int_ext_for_comb (cst, comb->type);;
      73                 :    43630055 : }
      74                 :             : 
      75                 :             : /* Sets COMB to single element ELT.  */
      76                 :             : 
      77                 :             : void
      78                 :    29599020 : aff_combination_elt (aff_tree *comb, tree type, tree elt)
      79                 :             : {
      80                 :    29599020 :   aff_combination_zero (comb, type);
      81                 :             : 
      82                 :    29599020 :   comb->n = 1;
      83                 :    29599020 :   comb->elts[0].val = elt;
      84                 :    29599020 :   comb->elts[0].coef = 1;
      85                 :    29599020 : }
      86                 :             : 
      87                 :             : /* Scales COMB by SCALE.  */
      88                 :             : 
      89                 :             : void
      90                 :    30659235 : aff_combination_scale (aff_tree *comb, const widest_int &scale_in)
      91                 :             : {
      92                 :    30659235 :   unsigned i, j;
      93                 :             : 
      94                 :    30659235 :   widest_int scale = wide_int_ext_for_comb (scale_in, comb->type);
      95                 :    30659235 :   if (scale == 1)
      96                 :             :     return;
      97                 :             : 
      98                 :    21787251 :   if (scale == 0)
      99                 :             :     {
     100                 :          16 :       aff_combination_zero (comb, comb->type);
     101                 :          16 :       return;
     102                 :             :     }
     103                 :             : 
     104                 :    21787235 :   comb->offset = wide_int_ext_for_comb (scale * comb->offset, comb->type);
     105                 :    39347875 :   for (i = 0, j = 0; i < comb->n; i++)
     106                 :             :     {
     107                 :    17560640 :       widest_int new_coef
     108                 :    17560640 :         = wide_int_ext_for_comb (scale * comb->elts[i].coef, comb->type);
     109                 :             :       /* A coefficient may become zero due to overflow.  Remove the zero
     110                 :             :          elements.  */
     111                 :    17560640 :       if (new_coef == 0)
     112                 :           5 :         continue;
     113                 :    17560635 :       comb->elts[j].coef = new_coef;
     114                 :    17560635 :       comb->elts[j].val = comb->elts[i].val;
     115                 :    17560635 :       j++;
     116                 :    17560640 :     }
     117                 :    21787235 :   comb->n = j;
     118                 :             : 
     119                 :    21787235 :   if (comb->rest)
     120                 :             :     {
     121                 :          84 :       tree type = comb->type;
     122                 :          84 :       if (POINTER_TYPE_P (type))
     123                 :          76 :         type = sizetype;
     124                 :          84 :       if (comb->n < MAX_AFF_ELTS)
     125                 :             :         {
     126                 :           0 :           comb->elts[comb->n].coef = scale;
     127                 :           0 :           comb->elts[comb->n].val = comb->rest;
     128                 :           0 :           comb->rest = NULL_TREE;
     129                 :           0 :           comb->n++;
     130                 :             :         }
     131                 :             :       else
     132                 :          84 :         comb->rest = fold_build2 (MULT_EXPR, type, comb->rest,
     133                 :             :                                   wide_int_to_tree (type, scale));
     134                 :             :     }
     135                 :    30659235 : }
     136                 :             : 
     137                 :             : /* Adds ELT * SCALE to COMB.  */
     138                 :             : 
     139                 :             : void
     140                 :    24835290 : aff_combination_add_elt (aff_tree *comb, tree elt, const widest_int &scale_in)
     141                 :             : {
     142                 :    24835290 :   unsigned i;
     143                 :    24835290 :   tree type;
     144                 :             : 
     145                 :    24835290 :   widest_int scale = wide_int_ext_for_comb (scale_in, comb->type);
     146                 :    24835290 :   if (scale == 0)
     147                 :             :     return;
     148                 :             : 
     149                 :    35997752 :   for (i = 0; i < comb->n; i++)
     150                 :    18093887 :     if (operand_equal_p (comb->elts[i].val, elt, 0))
     151                 :             :       {
     152                 :     6931425 :         widest_int new_coef
     153                 :     6931425 :           = wide_int_ext_for_comb (comb->elts[i].coef + scale, comb->type);
     154                 :     6931425 :         if (new_coef != 0)
     155                 :             :           {
     156                 :      132295 :             comb->elts[i].coef = new_coef;
     157                 :      132295 :             return;
     158                 :             :           }
     159                 :             : 
     160                 :     6799130 :         comb->n--;
     161                 :     6799130 :         comb->elts[i] = comb->elts[comb->n];
     162                 :             : 
     163                 :     6799130 :         if (comb->rest)
     164                 :             :           {
     165                 :         140 :             gcc_assert (comb->n == MAX_AFF_ELTS - 1);
     166                 :         140 :             comb->elts[comb->n].coef = 1;
     167                 :         140 :             comb->elts[comb->n].val = comb->rest;
     168                 :         140 :             comb->rest = NULL_TREE;
     169                 :         140 :             comb->n++;
     170                 :             :           }
     171                 :     6799130 :         return;
     172                 :     6931425 :       }
     173                 :    17903865 :   if (comb->n < MAX_AFF_ELTS)
     174                 :             :     {
     175                 :    17903483 :       comb->elts[comb->n].coef = scale;
     176                 :    17903483 :       comb->elts[comb->n].val = elt;
     177                 :    17903483 :       comb->n++;
     178                 :    17903483 :       return;
     179                 :             :     }
     180                 :             : 
     181                 :         382 :   type = comb->type;
     182                 :         382 :   if (POINTER_TYPE_P (type))
     183                 :         334 :     type = sizetype;
     184                 :             : 
     185                 :         382 :   if (scale == 1)
     186                 :         134 :     elt = fold_convert (type, elt);
     187                 :             :   else
     188                 :         248 :     elt = fold_build2 (MULT_EXPR, type,
     189                 :             :                        fold_convert (type, elt),
     190                 :             :                        wide_int_to_tree (type, scale));
     191                 :             : 
     192                 :         382 :   if (comb->rest)
     193                 :          66 :     comb->rest = fold_build2 (PLUS_EXPR, type, comb->rest,
     194                 :             :                               elt);
     195                 :             :   else
     196                 :         316 :     comb->rest = elt;
     197                 :    24835290 : }
     198                 :             : 
     199                 :             : /* Adds CST to C.  */
     200                 :             : 
     201                 :             : static void
     202                 :    45890344 : aff_combination_add_cst (aff_tree *c, const poly_widest_int &cst)
     203                 :             : {
     204                 :    45890344 :   c->offset = wide_int_ext_for_comb (c->offset + cst, c->type);
     205                 :    45890344 : }
     206                 :             : 
     207                 :             : /* Adds COMB2 to COMB1.  */
     208                 :             : 
     209                 :             : void
     210                 :    42432534 : aff_combination_add (aff_tree *comb1, aff_tree *comb2)
     211                 :             : {
     212                 :    42432534 :   unsigned i;
     213                 :             : 
     214                 :    42432534 :   aff_combination_add_cst (comb1, comb2->offset);
     215                 :   101077444 :   for (i = 0; i < comb2->n; i++)
     216                 :    16212376 :     aff_combination_add_elt (comb1, comb2->elts[i].val, comb2->elts[i].coef);
     217                 :    42432534 :   if (comb2->rest)
     218                 :         104 :     aff_combination_add_elt (comb1, comb2->rest, 1);
     219                 :    42432534 : }
     220                 :             : 
     221                 :             : /* Converts affine combination COMB to TYPE.  */
     222                 :             : 
     223                 :             : void
     224                 :    25014987 : aff_combination_convert (aff_tree *comb, tree type)
     225                 :             : {
     226                 :    25014987 :   unsigned i, j;
     227                 :    25014987 :   tree comb_type = comb->type;
     228                 :             : 
     229                 :    25014987 :   if  (TYPE_PRECISION (type) > TYPE_PRECISION (comb_type))
     230                 :             :     {
     231                 :      775518 :       tree val = fold_convert (type, aff_combination_to_tree (comb));
     232                 :      775518 :       tree_to_aff_combination (val, type, comb);
     233                 :      775518 :       return;
     234                 :             :     }
     235                 :             : 
     236                 :    24239469 :   comb->type = type;
     237                 :    24239469 :   if (comb->rest && !POINTER_TYPE_P (type))
     238                 :         116 :     comb->rest = fold_convert (type, comb->rest);
     239                 :             : 
     240                 :    24239469 :   if (TYPE_PRECISION (type) == TYPE_PRECISION (comb_type))
     241                 :             :     return;
     242                 :             : 
     243                 :       90448 :   comb->offset = wide_int_ext_for_comb (comb->offset, comb->type);
     244                 :      118181 :   for (i = j = 0; i < comb->n; i++)
     245                 :             :     {
     246                 :       27733 :       if (comb->elts[i].coef == 0)
     247                 :           0 :         continue;
     248                 :       27733 :       comb->elts[j].coef = comb->elts[i].coef;
     249                 :       27733 :       comb->elts[j].val = fold_convert (type, comb->elts[i].val);
     250                 :       27733 :       j++;
     251                 :             :     }
     252                 :             : 
     253                 :       90448 :   comb->n = j;
     254                 :       90448 :   if (comb->n < MAX_AFF_ELTS && comb->rest)
     255                 :             :     {
     256                 :           0 :       comb->elts[comb->n].coef = 1;
     257                 :           0 :       comb->elts[comb->n].val = comb->rest;
     258                 :           0 :       comb->rest = NULL_TREE;
     259                 :           0 :       comb->n++;
     260                 :             :     }
     261                 :             : }
     262                 :             : 
     263                 :             : /* Tries to handle OP0 CODE OP1 as affine combination of parts.  Returns
     264                 :             :    true when that was successful and returns the combination in COMB.  */
     265                 :             : 
     266                 :             : static bool
     267                 :    16896694 : expr_to_aff_combination (aff_tree *comb, tree_code code, tree type,
     268                 :             :                          tree op0, tree op1 = NULL_TREE)
     269                 :             : {
     270                 :    16896694 :   aff_tree tmp;
     271                 :             : 
     272                 :    16896694 :   switch (code)
     273                 :             :     {
     274                 :     5905392 :     case POINTER_PLUS_EXPR:
     275                 :     5905392 :       tree_to_aff_combination (op0, type, comb);
     276                 :     5905392 :       tree_to_aff_combination (op1, sizetype, &tmp);
     277                 :     5905392 :       aff_combination_add (comb, &tmp);
     278                 :     5905392 :       return true;
     279                 :             : 
     280                 :     5017314 :     case PLUS_EXPR:
     281                 :     5017314 :     case MINUS_EXPR:
     282                 :     5017314 :       tree_to_aff_combination (op0, type, comb);
     283                 :     5017314 :       tree_to_aff_combination (op1, type, &tmp);
     284                 :     5017314 :       if (code == MINUS_EXPR)
     285                 :      402819 :         aff_combination_scale (&tmp, -1);
     286                 :     5017314 :       aff_combination_add (comb, &tmp);
     287                 :     5017314 :       return true;
     288                 :             : 
     289                 :     3448654 :     case MULT_EXPR:
     290                 :     3448654 :       if (TREE_CODE (op1) != INTEGER_CST)
     291                 :             :         break;
     292                 :     2973028 :       tree_to_aff_combination (op0, type, comb);
     293                 :     2973028 :       aff_combination_scale (comb, wi::to_widest (op1));
     294                 :     2973028 :       return true;
     295                 :             : 
     296                 :       24537 :     case NEGATE_EXPR:
     297                 :       24537 :       tree_to_aff_combination (op0, type, comb);
     298                 :       24537 :       aff_combination_scale (comb, -1);
     299                 :       24537 :       return true;
     300                 :             : 
     301                 :        4088 :     case BIT_NOT_EXPR:
     302                 :             :       /* ~x = -x - 1 */
     303                 :        4088 :       tree_to_aff_combination (op0, type, comb);
     304                 :        4088 :       aff_combination_scale (comb, -1);
     305                 :        4088 :       aff_combination_add_cst (comb, -1);
     306                 :        4088 :       return true;
     307                 :             : 
     308                 :     2496709 :     CASE_CONVERT:
     309                 :     2496709 :       {
     310                 :     2496709 :         tree otype = type;
     311                 :     2496709 :         tree inner = op0;
     312                 :     2496709 :         tree itype = TREE_TYPE (inner);
     313                 :     2496709 :         enum tree_code icode = TREE_CODE (inner);
     314                 :             : 
     315                 :             :         /* STRIP_NOPS  */
     316                 :     2496709 :         if (tree_nop_conversion_p (otype, itype))
     317                 :             :           {
     318                 :        5525 :             tree_to_aff_combination (op0, type, comb);
     319                 :        5525 :             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                 :     2491184 :         if ((icode == PLUS_EXPR || icode == MINUS_EXPR || icode == MULT_EXPR)
     325                 :      279577 :             && TREE_CODE (itype) == INTEGER_TYPE
     326                 :      279577 :             && TREE_CODE (otype) == INTEGER_TYPE
     327                 :     2770755 :             && TYPE_PRECISION (otype) > TYPE_PRECISION (itype))
     328                 :             :           {
     329                 :      253163 :             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                 :      253163 :             if (TYPE_OVERFLOW_UNDEFINED (itype)
     336                 :      176967 :                 && (TREE_CODE (op1) == INTEGER_CST
     337                 :        5857 :                     || (icode == PLUS_EXPR && operand_equal_p (op0, op1, 0))))
     338                 :             :               {
     339                 :      171110 :                 op0 = fold_convert (otype, op0);
     340                 :      171110 :                 op1 = fold_convert (otype, op1);
     341                 :      171913 :                 return expr_to_aff_combination (comb, icode, otype, op0, op1);
     342                 :             :               }
     343                 :       82053 :             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.  */
     348                 :       82053 :             value_range vr;
     349                 :       82053 :             if (TYPE_UNSIGNED (itype)
     350                 :       75982 :                 && TYPE_OVERFLOW_WRAPS (itype)
     351                 :       75982 :                 && TREE_CODE (op1) == INTEGER_CST
     352                 :      113622 :                 && get_range_query (cfun)->range_of_expr (vr, op0)
     353                 :       56811 :                 && !vr.varying_p ()
     354                 :       90928 :                 && !vr.undefined_p ())
     355                 :             :               {
     356                 :        8866 :                 wide_int minv = vr.lower_bound ();
     357                 :        8866 :                 wide_int maxv = vr.upper_bound ();
     358                 :        8866 :                 wi::overflow_type overflow = wi::OVF_NONE;
     359                 :        8866 :                 signop sign = UNSIGNED;
     360                 :        8866 :                 if (icode == PLUS_EXPR)
     361                 :        8782 :                   wi::add (maxv, wi::to_wide (op1), sign, &overflow);
     362                 :          84 :                 else if (icode == MULT_EXPR)
     363                 :          84 :                   wi::mul (maxv, wi::to_wide (op1), sign, &overflow);
     364                 :             :                 else
     365                 :           0 :                   wi::sub (minv, wi::to_wide (op1), sign, &overflow);
     366                 :             : 
     367                 :        8866 :                 if (overflow == wi::OVF_NONE)
     368                 :             :                   {
     369                 :         803 :                     op0 = fold_convert (otype, op0);
     370                 :         803 :                     op1 = fold_convert (otype, op1);
     371                 :         803 :                     return expr_to_aff_combination (comb, icode, otype, op0,
     372                 :             :                                                     op1);
     373                 :             :                   }
     374                 :        8866 :               }
     375                 :       82053 :           }
     376                 :             :       }
     377                 :             :       break;
     378                 :             : 
     379                 :      475626 :     default:;
     380                 :             :     }
     381                 :             : 
     382                 :             :   return false;
     383                 :    16896694 : }
     384                 :             : 
     385                 :             : /* Splits EXPR into an affine combination of parts.  */
     386                 :             : 
     387                 :             : void
     388                 :    82140903 : tree_to_aff_combination (tree expr, tree type, aff_tree *comb)
     389                 :             : {
     390                 :    82140903 :   aff_tree tmp;
     391                 :    82140903 :   enum tree_code code;
     392                 :    82140903 :   tree core, toffset;
     393                 :    82140903 :   poly_int64 bitpos, bitsize, bytepos;
     394                 :    82140903 :   machine_mode mode;
     395                 :    82140903 :   int unsignedp, reversep, volatilep;
     396                 :             : 
     397                 :    82140903 :   STRIP_NOPS (expr);
     398                 :             : 
     399                 :    82140903 :   code = TREE_CODE (expr);
     400                 :    82140903 :   switch (code)
     401                 :             :     {
     402                 :    14170515 :     case POINTER_PLUS_EXPR:
     403                 :    14170515 :     case PLUS_EXPR:
     404                 :    14170515 :     case MINUS_EXPR:
     405                 :    14170515 :     case MULT_EXPR:
     406                 :    14170515 :       if (expr_to_aff_combination (comb, code, type, TREE_OPERAND (expr, 0),
     407                 :    14170515 :                                    TREE_OPERAND (expr, 1)))
     408                 :             :         return;
     409                 :             :       break;
     410                 :             : 
     411                 :       28233 :     case NEGATE_EXPR:
     412                 :       28233 :     case BIT_NOT_EXPR:
     413                 :       28233 :       if (expr_to_aff_combination (comb, code, type, TREE_OPERAND (expr, 0)))
     414                 :             :         return;
     415                 :             :       break;
     416                 :             : 
     417                 :     2482951 :     CASE_CONVERT:
     418                 :             :       /* ???  TREE_TYPE (expr) should be equal to type here, but IVOPTS
     419                 :             :          calls this with not showing an outer widening cast.  */
     420                 :     2482951 :       if (expr_to_aff_combination (comb, code,
     421                 :     2482951 :                                    TREE_TYPE (expr), TREE_OPERAND (expr, 0)))
     422                 :             :         {
     423                 :      171913 :           aff_combination_convert (comb, type);
     424                 :      171913 :           return;
     425                 :             :         }
     426                 :             :       break;
     427                 :             : 
     428                 :     8147346 :     case ADDR_EXPR:
     429                 :             :       /* Handle &MEM[ptr + CST] which is equivalent to POINTER_PLUS_EXPR.  */
     430                 :     8147346 :       if (TREE_CODE (TREE_OPERAND (expr, 0)) == MEM_REF)
     431                 :             :         {
     432                 :      467962 :           expr = TREE_OPERAND (expr, 0);
     433                 :      467962 :           tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb);
     434                 :      467962 :           tree_to_aff_combination (TREE_OPERAND (expr, 1), sizetype, &tmp);
     435                 :      467962 :           aff_combination_add (comb, &tmp);
     436                 :      467962 :           return;
     437                 :             :         }
     438                 :     7679384 :       core = get_inner_reference (TREE_OPERAND (expr, 0), &bitsize, &bitpos,
     439                 :             :                                   &toffset, &mode, &unsignedp, &reversep,
     440                 :             :                                   &volatilep);
     441                 :    15358768 :       if (!multiple_p (bitpos, BITS_PER_UNIT, &bytepos))
     442                 :             :         break;
     443                 :     7679384 :       aff_combination_const (comb, type, bytepos);
     444                 :     7679384 :       if (TREE_CODE (core) == MEM_REF)
     445                 :             :         {
     446                 :      222770 :           tree mem_offset = TREE_OPERAND (core, 1);
     447                 :      222770 :           aff_combination_add_cst (comb, wi::to_poly_widest (mem_offset));
     448                 :      222770 :           core = TREE_OPERAND (core, 0);
     449                 :             :         }
     450                 :             :       else
     451                 :     7456614 :         core = build_fold_addr_expr (core);
     452                 :             : 
     453                 :     7679384 :       if (TREE_CODE (core) == ADDR_EXPR)
     454                 :     7456614 :         aff_combination_add_elt (comb, core, 1);
     455                 :             :       else
     456                 :             :         {
     457                 :      222770 :           tree_to_aff_combination (core, type, &tmp);
     458                 :      222770 :           aff_combination_add (comb, &tmp);
     459                 :             :         }
     460                 :     7679384 :       if (toffset)
     461                 :             :         {
     462                 :       50401 :           tree_to_aff_combination (toffset, type, &tmp);
     463                 :       50401 :           aff_combination_add (comb, &tmp);
     464                 :             :         }
     465                 :             :       return;
     466                 :             : 
     467                 :    57311858 :     default:
     468                 :    57311858 :       {
     469                 :    57311858 :         if (poly_int_tree_p (expr))
     470                 :             :           {
     471                 :    30500375 :             aff_combination_const (comb, type, wi::to_poly_widest (expr));
     472                 :    30500375 :             return;
     473                 :             :           }
     474                 :             :         break;
     475                 :             :       }
     476                 :             :     }
     477                 :             : 
     478                 :    29590787 :   aff_combination_elt (comb, type, expr);
     479                 :    82140903 : }
     480                 :             : 
     481                 :             : /* Creates EXPR + ELT * SCALE in TYPE.  EXPR is taken from affine
     482                 :             :    combination COMB.  */
     483                 :             : 
     484                 :             : static tree
     485                 :    20978160 : add_elt_to_tree (tree expr, tree type, tree elt, const widest_int &scale_in)
     486                 :             : {
     487                 :    20978160 :   enum tree_code code;
     488                 :             : 
     489                 :    20978160 :   widest_int scale = wide_int_ext_for_comb (scale_in, type);
     490                 :             : 
     491                 :    20978160 :   elt = fold_convert (type, elt);
     492                 :    20978160 :   if (scale == 1)
     493                 :             :     {
     494                 :    16887672 :       if (!expr)
     495                 :             :         return elt;
     496                 :             : 
     497                 :     6388449 :       return fold_build2 (PLUS_EXPR, type, expr, elt);
     498                 :             :     }
     499                 :             : 
     500                 :     4090488 :   if (scale == -1)
     501                 :             :     {
     502                 :     2040346 :       if (!expr)
     503                 :     1329868 :         return fold_build1 (NEGATE_EXPR, type, elt);
     504                 :             : 
     505                 :      710478 :       return fold_build2 (MINUS_EXPR, type, expr, elt);
     506                 :             :     }
     507                 :             : 
     508                 :     2050142 :   if (!expr)
     509                 :      729634 :     return fold_build2 (MULT_EXPR, type, elt, wide_int_to_tree (type, scale));
     510                 :             : 
     511                 :     1320508 :   if (wi::neg_p (scale))
     512                 :             :     {
     513                 :      260101 :       code = MINUS_EXPR;
     514                 :      260101 :       scale = -scale;
     515                 :             :     }
     516                 :             :   else
     517                 :             :     code = PLUS_EXPR;
     518                 :             : 
     519                 :     1320508 :   elt = fold_build2 (MULT_EXPR, type, elt, wide_int_to_tree (type, scale));
     520                 :     1320508 :   return fold_build2 (code, type, expr, elt);
     521                 :    20978160 : }
     522                 :             : 
     523                 :             : /* Makes tree from the affine combination COMB.  */
     524                 :             : 
     525                 :             : tree
     526                 :    12558725 : aff_combination_to_tree (aff_tree *comb)
     527                 :             : {
     528                 :    12558725 :   tree type = comb->type, base = NULL_TREE, expr = NULL_TREE;
     529                 :    12558725 :   unsigned i;
     530                 :    12558725 :   poly_widest_int off;
     531                 :    12558725 :   int sgn;
     532                 :             : 
     533                 :    12558725 :   gcc_assert (comb->n == MAX_AFF_ELTS || comb->rest == NULL_TREE);
     534                 :             : 
     535                 :    12558725 :   i = 0;
     536                 :    12558725 :   if (POINTER_TYPE_P (type))
     537                 :             :     {
     538                 :      531743 :       type = sizetype;
     539                 :      534398 :       if (comb->n > 0 && comb->elts[0].coef == 1
     540                 :     1063315 :           && POINTER_TYPE_P (TREE_TYPE (comb->elts[0].val)))
     541                 :             :         {
     542                 :      528917 :           base = comb->elts[0].val;
     543                 :      528917 :           ++i;
     544                 :             :         }
     545                 :             :     }
     546                 :             : 
     547                 :    20978096 :   for (; i < comb->n; i++)
     548                 :     8419371 :     expr = add_elt_to_tree (expr, type, comb->elts[i].val, comb->elts[i].coef);
     549                 :             : 
     550                 :    12558725 :   if (comb->rest)
     551                 :          64 :     expr = add_elt_to_tree (expr, type, comb->rest, 1);
     552                 :             : 
     553                 :             :   /* Ensure that we get x - 1, not x + (-1) or x + 0xff..f if x is
     554                 :             :      unsigned.  */
     555                 :    12558725 :   if (known_lt (comb->offset, 0))
     556                 :             :     {
     557                 :     1610989 :       off = -comb->offset;
     558                 :     1610989 :       sgn = -1;
     559                 :             :     }
     560                 :             :   else
     561                 :             :     {
     562                 :    10947736 :       off = comb->offset;
     563                 :    10947736 :       sgn = 1;
     564                 :             :     }
     565                 :    12558725 :   expr = add_elt_to_tree (expr, type, wide_int_to_tree (type, off), sgn);
     566                 :             : 
     567                 :    12558725 :   if (base)
     568                 :      528917 :     return fold_build_pointer_plus (base, expr);
     569                 :             :   else
     570                 :    12029808 :     return fold_convert (comb->type, expr);
     571                 :    12558725 : }
     572                 :             : 
     573                 :             : /* Copies the tree elements of COMB to ensure that they are not shared.  */
     574                 :             : 
     575                 :             : void
     576                 :     1533179 : unshare_aff_combination (aff_tree *comb)
     577                 :             : {
     578                 :     1533179 :   unsigned i;
     579                 :             : 
     580                 :     3316886 :   for (i = 0; i < comb->n; i++)
     581                 :     1783707 :     comb->elts[i].val = unshare_expr (comb->elts[i].val);
     582                 :     1533179 :   if (comb->rest)
     583                 :           0 :     comb->rest = unshare_expr (comb->rest);
     584                 :     1533179 : }
     585                 :             : 
     586                 :             : /* Remove M-th element from COMB.  */
     587                 :             : 
     588                 :             : void
     589                 :     1573809 : aff_combination_remove_elt (aff_tree *comb, unsigned m)
     590                 :             : {
     591                 :     1573809 :   comb->n--;
     592                 :     1573809 :   if (m <= comb->n)
     593                 :     1573809 :     comb->elts[m] = comb->elts[comb->n];
     594                 :     1573809 :   if (comb->rest)
     595                 :             :     {
     596                 :           0 :       comb->elts[comb->n].coef = 1;
     597                 :           0 :       comb->elts[comb->n].val = comb->rest;
     598                 :           0 :       comb->rest = NULL_TREE;
     599                 :           0 :       comb->n++;
     600                 :             :     }
     601                 :     1573809 : }
     602                 :             : 
     603                 :             : /* Adds C * COEF * VAL to R.  VAL may be NULL, in that case only
     604                 :             :    C * COEF is added to R.  */
     605                 :             : 
     606                 :             : 
     607                 :             : static void
     608                 :     3230952 : aff_combination_add_product (aff_tree *c, const widest_int &coef, tree val,
     609                 :             :                              aff_tree *r)
     610                 :             : {
     611                 :     3230952 :   unsigned i;
     612                 :     3230952 :   tree aval, type;
     613                 :             : 
     614                 :     4331721 :   for (i = 0; i < c->n; i++)
     615                 :             :     {
     616                 :     1100769 :       aval = c->elts[i].val;
     617                 :     1100769 :       if (val)
     618                 :             :         {
     619                 :           0 :           type = TREE_TYPE (aval);
     620                 :           0 :           aval = fold_build2 (MULT_EXPR, type, aval,
     621                 :             :                               fold_convert (type, val));
     622                 :             :         }
     623                 :             : 
     624                 :     1100769 :       aff_combination_add_elt (r, aval, coef * c->elts[i].coef);
     625                 :             :     }
     626                 :             : 
     627                 :     3230952 :   if (c->rest)
     628                 :             :     {
     629                 :           0 :       aval = c->rest;
     630                 :           0 :       if (val)
     631                 :             :         {
     632                 :           0 :           type = TREE_TYPE (aval);
     633                 :           0 :           aval = fold_build2 (MULT_EXPR, type, aval,
     634                 :             :                               fold_convert (type, val));
     635                 :             :         }
     636                 :             : 
     637                 :           0 :       aff_combination_add_elt (r, aval, coef);
     638                 :             :     }
     639                 :             : 
     640                 :     3230952 :   if (val)
     641                 :             :     {
     642                 :           0 :       if (c->offset.is_constant ())
     643                 :             :         /* Access coeffs[0] directly, for efficiency.  */
     644                 :           0 :         aff_combination_add_elt (r, val, coef * c->offset.coeffs[0]);
     645                 :             :       else
     646                 :             :         {
     647                 :             :           /* c->offset is polynomial, so multiply VAL rather than COEF
     648                 :             :              by it.  */
     649                 :             :           tree offset = wide_int_to_tree (TREE_TYPE (val), c->offset);
     650                 :             :           val = fold_build2 (MULT_EXPR, TREE_TYPE (val), val, offset);
     651                 :             :           aff_combination_add_elt (r, val, coef);
     652                 :             :         }
     653                 :             :     }
     654                 :             :   else
     655                 :     3230952 :     aff_combination_add_cst (r, coef * c->offset);
     656                 :     3230952 : }
     657                 :             : 
     658                 :             : /* Multiplies C1 by C2, storing the result to R  */
     659                 :             : 
     660                 :             : void
     661                 :     3230952 : aff_combination_mult (aff_tree *c1, aff_tree *c2, aff_tree *r)
     662                 :             : {
     663                 :     3230952 :   unsigned i;
     664                 :     3230952 :   gcc_assert (TYPE_PRECISION (c1->type) == TYPE_PRECISION (c2->type));
     665                 :             : 
     666                 :     3230952 :   aff_combination_zero (r, c1->type);
     667                 :             : 
     668                 :     6461904 :   for (i = 0; i < c2->n; i++)
     669                 :           0 :     aff_combination_add_product (c1, c2->elts[i].coef, c2->elts[i].val, r);
     670                 :     3230952 :   if (c2->rest)
     671                 :           0 :     aff_combination_add_product (c1, 1, c2->rest, r);
     672                 :     3230952 :   if (c2->offset.is_constant ())
     673                 :             :     /* Access coeffs[0] directly, for efficiency.  */
     674                 :     3230952 :     aff_combination_add_product (c1, c2->offset.coeffs[0], NULL, r);
     675                 :             :   else
     676                 :             :     {
     677                 :             :       /* c2->offset is polynomial, so do the multiplication in tree form.  */
     678                 :             :       tree offset = wide_int_to_tree (c2->type, c2->offset);
     679                 :             :       aff_combination_add_product (c1, 1, offset, r);
     680                 :             :     }
     681                 :     3230952 : }
     682                 :             : 
     683                 :             : /* Returns the element of COMB whose value is VAL, or NULL if no such
     684                 :             :    element exists.  If IDX is not NULL, it is set to the index of VAL in
     685                 :             :    COMB.  */
     686                 :             : 
     687                 :             : static class aff_comb_elt *
     688                 :          47 : aff_combination_find_elt (aff_tree *comb, tree val, unsigned *idx)
     689                 :             : {
     690                 :          47 :   unsigned i;
     691                 :             : 
     692                 :          51 :   for (i = 0; i < comb->n; i++)
     693                 :          47 :     if (operand_equal_p (comb->elts[i].val, val, 0))
     694                 :             :       {
     695                 :          43 :         if (idx)
     696                 :           0 :           *idx = i;
     697                 :             : 
     698                 :          43 :         return &comb->elts[i];
     699                 :             :       }
     700                 :             : 
     701                 :             :   return NULL;
     702                 :             : }
     703                 :             : 
     704                 :             : /* Element of the cache that maps ssa name NAME to its expanded form
     705                 :             :    as an affine expression EXPANSION.  */
     706                 :             : 
     707                 :      143464 : class name_expansion
     708                 :             : {
     709                 :             : public:
     710                 :             :   aff_tree expansion;
     711                 :             : 
     712                 :             :   /* True if the expansion for the name is just being generated.  */
     713                 :             :   unsigned in_progress : 1;
     714                 :             : };
     715                 :             : 
     716                 :             : /* Expands SSA names in COMB recursively.  CACHE is used to cache the
     717                 :             :    results.  */
     718                 :             : 
     719                 :             : void
     720                 :      421448 : aff_combination_expand (aff_tree *comb ATTRIBUTE_UNUSED,
     721                 :             :                         hash_map<tree, name_expansion *> **cache)
     722                 :             : {
     723                 :      421448 :   unsigned i;
     724                 :     1264344 :   aff_tree to_add, current, curre;
     725                 :      421448 :   tree e;
     726                 :      421448 :   gimple *def;
     727                 :      421448 :   widest_int scale;
     728                 :      421448 :   class name_expansion *exp;
     729                 :             : 
     730                 :      421448 :   aff_combination_zero (&to_add, comb->type);
     731                 :      665022 :   for (i = 0; i < comb->n; i++)
     732                 :             :     {
     733                 :      243574 :       tree type, name;
     734                 :      243574 :       enum tree_code code;
     735                 :             : 
     736                 :      243574 :       e = comb->elts[i].val;
     737                 :      243574 :       type = TREE_TYPE (e);
     738                 :      243574 :       name = e;
     739                 :             :       /* Look through some conversions.  */
     740                 :      213515 :       if (CONVERT_EXPR_P (e)
     741                 :      243574 :           && (TYPE_PRECISION (type)
     742                 :       30059 :               >= TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (e, 0)))))
     743                 :       29524 :         name = TREE_OPERAND (e, 0);
     744                 :      243574 :       if (TREE_CODE (name) != SSA_NAME)
     745                 :      184851 :         continue;
     746                 :      171293 :       def = SSA_NAME_DEF_STMT (name);
     747                 :      171293 :       if (!is_gimple_assign (def) || gimple_assign_lhs (def) != name)
     748                 :       71360 :         continue;
     749                 :             : 
     750                 :       99933 :       code = gimple_assign_rhs_code (def);
     751                 :      104252 :       if (code != SSA_NAME
     752                 :       98698 :           && !IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code))
     753                 :      104255 :           && (get_gimple_rhs_class (code) != GIMPLE_SINGLE_RHS
     754                 :        4322 :               || !is_gimple_min_invariant (gimple_assign_rhs1 (def))))
     755                 :        4319 :         continue;
     756                 :             : 
     757                 :             :       /* We do not know whether the reference retains its value at the
     758                 :             :          place where the expansion is used.  */
     759                 :       95614 :       if (TREE_CODE_CLASS (code) == tcc_reference)
     760                 :       23258 :         continue;
     761                 :             : 
     762                 :       72356 :       name_expansion **slot = NULL;
     763                 :       72356 :       if (*cache)
     764                 :       49475 :         slot = (*cache)->get (name);
     765                 :       49475 :       exp = slot ? *slot : NULL;
     766                 :       72356 :       if (!exp)
     767                 :             :         {
     768                 :             :           /* Only bother to handle cases tree_to_aff_combination will.  */
     769                 :       49499 :           switch (code)
     770                 :             :             {
     771                 :       28932 :             case POINTER_PLUS_EXPR:
     772                 :       28932 :             case PLUS_EXPR:
     773                 :       28932 :             case MINUS_EXPR:
     774                 :       28932 :             case MULT_EXPR:
     775                 :       28932 :               if (!expr_to_aff_combination (&current, code, TREE_TYPE (name),
     776                 :             :                                             gimple_assign_rhs1 (def),
     777                 :             :                                             gimple_assign_rhs2 (def)))
     778                 :        7360 :                 continue;
     779                 :             :               break;
     780                 :         392 :             case NEGATE_EXPR:
     781                 :         392 :             case BIT_NOT_EXPR:
     782                 :         392 :               if (!expr_to_aff_combination (&current, code, TREE_TYPE (name),
     783                 :             :                                             gimple_assign_rhs1 (def)))
     784                 :           0 :                 continue;
     785                 :             :               break;
     786                 :       13758 :             CASE_CONVERT:
     787                 :       13758 :               if (!expr_to_aff_combination (&current, code, TREE_TYPE (name),
     788                 :             :                                             gimple_assign_rhs1 (def)))
     789                 :             :                 /* This makes us always expand conversions which we did
     790                 :             :                    in the past and makes gcc.dg/tree-ssa/ivopts-lt-2.c
     791                 :             :                    PASS, eliminating one induction variable in IVOPTs.
     792                 :             :                    ???  But it is really excessive and we should try
     793                 :             :                    harder to do without it.  */
     794                 :       16466 :                 aff_combination_elt (&current, TREE_TYPE (name),
     795                 :        8233 :                                      fold_convert (TREE_TYPE (name),
     796                 :             :                                                    gimple_assign_rhs1 (def)));
     797                 :             :               break;
     798                 :         144 :             case ADDR_EXPR:
     799                 :         144 :             case INTEGER_CST:
     800                 :         144 :             case POLY_INT_CST:
     801                 :         144 :               tree_to_aff_combination (gimple_assign_rhs1 (def),
     802                 :         144 :                                        TREE_TYPE (name), &current);
     803                 :         144 :               break;
     804                 :        6273 :             default:
     805                 :        6273 :               continue;
     806                 :             :             }
     807                 :       35866 :           exp = XNEW (class name_expansion);
     808                 :       35866 :           ::new (static_cast<void *> (exp)) name_expansion ();
     809                 :       35866 :           exp->in_progress = 1;
     810                 :       35866 :           if (!*cache)
     811                 :       15463 :             *cache = new hash_map<tree, name_expansion *>;
     812                 :       35866 :           (*cache)->put (name, exp);
     813                 :       35866 :           aff_combination_expand (&current, cache);
     814                 :       35866 :           exp->expansion = current;
     815                 :       35866 :           exp->in_progress = 0;
     816                 :             :         }
     817                 :             :       else
     818                 :             :         {
     819                 :             :           /* Since we follow the definitions in the SSA form, we should not
     820                 :             :              enter a cycle unless we pass through a phi node.  */
     821                 :       22857 :           gcc_assert (!exp->in_progress);
     822                 :       22857 :           current = exp->expansion;
     823                 :             :         }
     824                 :       58723 :       if (!useless_type_conversion_p (comb->type, current.type))
     825                 :       23542 :         aff_combination_convert (&current, comb->type);
     826                 :             : 
     827                 :             :       /* Accumulate the new terms to TO_ADD, so that we do not modify
     828                 :             :          COMB while traversing it; include the term -coef * E, to remove
     829                 :             :          it from COMB.  */
     830                 :       58723 :       scale = comb->elts[i].coef;
     831                 :       58723 :       aff_combination_zero (&curre, comb->type);
     832                 :       58723 :       aff_combination_add_elt (&curre, e, -scale);
     833                 :       58723 :       aff_combination_scale (&current, scale);
     834                 :       58723 :       aff_combination_add (&to_add, &current);
     835                 :       58723 :       aff_combination_add (&to_add, &curre);
     836                 :             :     }
     837                 :      421448 :   aff_combination_add (comb, &to_add);
     838                 :      421448 : }
     839                 :             : 
     840                 :             : /* Similar to tree_to_aff_combination, but follows SSA name definitions
     841                 :             :    and expands them recursively.  CACHE is used to cache the expansions
     842                 :             :    of the ssa names, to avoid exponential time complexity for cases
     843                 :             :    like
     844                 :             : 
     845                 :             :    a1 = a0 + a0;
     846                 :             :    a2 = a1 + a1;
     847                 :             :    a3 = a2 + a2;
     848                 :             :    ...  */
     849                 :             : 
     850                 :             : void
     851                 :      289986 : tree_to_aff_combination_expand (tree expr, tree type, aff_tree *comb,
     852                 :             :                                 hash_map<tree, name_expansion *> **cache)
     853                 :             : {
     854                 :      289986 :   tree_to_aff_combination (expr, type, comb);
     855                 :      289986 :   aff_combination_expand (comb, cache);
     856                 :      289986 : }
     857                 :             : 
     858                 :             : /* Frees memory occupied by struct name_expansion in *VALUE.  Callback for
     859                 :             :    hash_map::traverse.  */
     860                 :             : 
     861                 :             : bool
     862                 :       35866 : free_name_expansion (tree const &, name_expansion **value, void *)
     863                 :             : {
     864                 :       35866 :   (*value)->~name_expansion ();
     865                 :       35866 :   free (*value);
     866                 :       35866 :   return true;
     867                 :             : }
     868                 :             : 
     869                 :             : /* Frees memory allocated for the CACHE used by
     870                 :             :    tree_to_aff_combination_expand.  */
     871                 :             : 
     872                 :             : void
     873                 :     1563918 : free_affine_expand_cache (hash_map<tree, name_expansion *> **cache)
     874                 :             : {
     875                 :     1563918 :   if (!*cache)
     876                 :             :     return;
     877                 :             : 
     878                 :       15463 :   (*cache)->traverse<void *, free_name_expansion> (NULL);
     879                 :       30926 :   delete (*cache);
     880                 :       15463 :   *cache = NULL;
     881                 :             : }
     882                 :             : 
     883                 :             : /* If VAL != CST * DIV for any constant CST, returns false.
     884                 :             :    Otherwise, if *MULT_SET is true, additionally compares CST and MULT,
     885                 :             :    and if they are different, returns false.  Finally, if neither of these
     886                 :             :    two cases occur, true is returned, and CST is stored to MULT and MULT_SET
     887                 :             :    is set to true.  */
     888                 :             : 
     889                 :             : static bool
     890                 :       40459 : wide_int_constant_multiple_p (const poly_widest_int &val,
     891                 :             :                               const poly_widest_int &div,
     892                 :             :                               bool *mult_set, poly_widest_int *mult)
     893                 :             : {
     894                 :       80918 :   poly_widest_int rem, cst;
     895                 :             : 
     896                 :       40459 :   if (known_eq (val, 0))
     897                 :             :     {
     898                 :          35 :       if (*mult_set && maybe_ne (*mult, 0))
     899                 :           0 :         return false;
     900                 :          35 :       *mult_set = true;
     901                 :          35 :       *mult = 0;
     902                 :          35 :       return true;
     903                 :             :     }
     904                 :             : 
     905                 :       40424 :   if (maybe_eq (div, 0))
     906                 :             :     return false;
     907                 :             : 
     908                 :       40418 :   if (!multiple_p (val, div, &cst))
     909                 :             :     return false;
     910                 :             : 
     911                 :       38248 :   if (*mult_set && maybe_ne (*mult, cst))
     912                 :             :     return false;
     913                 :             : 
     914                 :       38174 :   *mult_set = true;
     915                 :       38174 :   *mult = cst;
     916                 :       38174 :   return true;
     917                 :       40459 : }
     918                 :             : 
     919                 :             : /* Returns true if VAL = X * DIV for some constant X.  If this is the case,
     920                 :             :    X is stored to MULT.  */
     921                 :             : 
     922                 :             : bool
     923                 :       83336 : aff_combination_constant_multiple_p (aff_tree *val, aff_tree *div,
     924                 :             :                                      poly_widest_int *mult)
     925                 :             : {
     926                 :       83336 :   bool mult_set = false;
     927                 :       83336 :   unsigned i;
     928                 :             : 
     929                 :       83336 :   if (val->n == 0 && known_eq (val->offset, 0))
     930                 :             :     {
     931                 :       38107 :       *mult = 0;
     932                 :       38107 :       return true;
     933                 :             :     }
     934                 :       45229 :   if (val->n != div->n)
     935                 :             :     return false;
     936                 :             : 
     937                 :       40416 :   if (val->rest || div->rest)
     938                 :             :     return false;
     939                 :             : 
     940                 :       40416 :   if (!wide_int_constant_multiple_p (val->offset, div->offset,
     941                 :             :                                      &mult_set, mult))
     942                 :             :     return false;
     943                 :             : 
     944                 :       38209 :   for (i = 0; i < div->n; i++)
     945                 :             :     {
     946                 :          47 :       class aff_comb_elt *elt
     947                 :          47 :               = aff_combination_find_elt (val, div->elts[i].val, NULL);
     948                 :          47 :       if (!elt)
     949                 :             :         return false;
     950                 :          43 :       if (!wide_int_constant_multiple_p (elt->coef, div->elts[i].coef,
     951                 :             :                                          &mult_set, mult))
     952                 :             :         return false;
     953                 :             :     }
     954                 :             : 
     955                 :       38162 :   gcc_assert (mult_set);
     956                 :             :   return true;
     957                 :             : }
     958                 :             : 
     959                 :             : /* Prints the affine VAL to the FILE. */
     960                 :             : 
     961                 :             : static void
     962                 :           0 : print_aff (FILE *file, aff_tree *val)
     963                 :             : {
     964                 :           0 :   unsigned i;
     965                 :           0 :   signop sgn = TYPE_SIGN (val->type);
     966                 :           0 :   if (POINTER_TYPE_P (val->type))
     967                 :           0 :     sgn = SIGNED;
     968                 :           0 :   fprintf (file, "{\n  type = ");
     969                 :           0 :   print_generic_expr (file, val->type, TDF_VOPS|TDF_MEMSYMS);
     970                 :           0 :   fprintf (file, "\n  offset = ");
     971                 :           0 :   print_dec (val->offset, file, sgn);
     972                 :           0 :   if (val->n > 0)
     973                 :             :     {
     974                 :           0 :       fprintf (file, "\n  elements = {\n");
     975                 :           0 :       for (i = 0; i < val->n; i++)
     976                 :             :         {
     977                 :           0 :           fprintf (file, "    [%d] = ", i);
     978                 :           0 :           print_generic_expr (file, val->elts[i].val, TDF_VOPS|TDF_MEMSYMS);
     979                 :             : 
     980                 :           0 :           fprintf (file, " * ");
     981                 :           0 :           print_dec (val->elts[i].coef, file, sgn);
     982                 :           0 :           if (i != val->n - 1)
     983                 :           0 :             fprintf (file, ", \n");
     984                 :             :         }
     985                 :           0 :       fprintf (file, "\n  }");
     986                 :             :   }
     987                 :           0 :   if (val->rest)
     988                 :             :     {
     989                 :           0 :       fprintf (file, "\n  rest = ");
     990                 :           0 :       print_generic_expr (file, val->rest, TDF_VOPS|TDF_MEMSYMS);
     991                 :             :     }
     992                 :           0 :   fprintf (file, "\n}");
     993                 :           0 : }
     994                 :             : 
     995                 :             : /* Prints the affine VAL to the standard error, used for debugging.  */
     996                 :             : 
     997                 :             : DEBUG_FUNCTION void
     998                 :           0 : debug_aff (aff_tree *val)
     999                 :             : {
    1000                 :           0 :   print_aff (stderr, val);
    1001                 :           0 :   fprintf (stderr, "\n");
    1002                 :           0 : }
    1003                 :             : 
    1004                 :             : /* Computes address of the reference REF in ADDR.  The size of the accessed
    1005                 :             :    location is stored to SIZE.  Returns the ultimate containing object to
    1006                 :             :    which REF refers.  */
    1007                 :             : 
    1008                 :             : tree
    1009                 :     5283624 : get_inner_reference_aff (tree ref, aff_tree *addr, poly_widest_int *size)
    1010                 :             : {
    1011                 :     5283624 :   poly_int64 bitsize, bitpos;
    1012                 :     5283624 :   tree toff;
    1013                 :     5283624 :   machine_mode mode;
    1014                 :     5283624 :   int uns, rev, vol;
    1015                 :     5283624 :   aff_tree tmp;
    1016                 :     5283624 :   tree base = get_inner_reference (ref, &bitsize, &bitpos, &toff, &mode,
    1017                 :             :                                    &uns, &rev, &vol);
    1018                 :     5283624 :   tree base_addr = build_fold_addr_expr (base);
    1019                 :             : 
    1020                 :             :   /* ADDR = &BASE + TOFF + BITPOS / BITS_PER_UNIT.  */
    1021                 :             : 
    1022                 :     5283624 :   tree_to_aff_combination (base_addr, sizetype, addr);
    1023                 :             : 
    1024                 :     5283624 :   if (toff)
    1025                 :             :     {
    1026                 :      150427 :       tree_to_aff_combination (toff, sizetype, &tmp);
    1027                 :      150427 :       aff_combination_add (addr, &tmp);
    1028                 :             :     }
    1029                 :             : 
    1030                 :     5283624 :   aff_combination_const (&tmp, sizetype, bits_to_bytes_round_down (bitpos));
    1031                 :     5283624 :   aff_combination_add (addr, &tmp);
    1032                 :             : 
    1033                 :     5283624 :   *size = bits_to_bytes_round_up (bitsize);
    1034                 :             : 
    1035                 :    10567248 :   return base;
    1036                 :     5283624 : }
    1037                 :             : 
    1038                 :             : /* Returns true if a region of size SIZE1 at position 0 and a region of
    1039                 :             :    size SIZE2 at position DIFF cannot overlap.  */
    1040                 :             : 
    1041                 :             : bool
    1042                 :     2641959 : aff_comb_cannot_overlap_p (aff_tree *diff, const poly_widest_int &size1,
    1043                 :             :                            const poly_widest_int &size2)
    1044                 :             : {
    1045                 :             :   /* Unless the difference is a constant, we fail.  */
    1046                 :     2641959 :   if (diff->n != 0)
    1047                 :             :     return false;
    1048                 :             : 
    1049                 :     1712227 :   if (!ordered_p (diff->offset, 0))
    1050                 :             :     return false;
    1051                 :             : 
    1052                 :     1712227 :   if (maybe_lt (diff->offset, 0))
    1053                 :             :     {
    1054                 :             :       /* The second object is before the first one, we succeed if the last
    1055                 :             :          element of the second object is before the start of the first one.  */
    1056                 :      233984 :       return known_le (diff->offset + size2, 0);
    1057                 :             :     }
    1058                 :             :   else
    1059                 :             :     {
    1060                 :             :       /* We succeed if the second object starts after the first one ends.  */
    1061                 :     1478243 :       return known_le (size1, diff->offset);
    1062                 :             :     }
    1063                 :             : }
    1064                 :             : 
        

Generated by: LCOV version 2.0-1

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,rust,m2 --enable-host-shared. GCC test suite is run with the built compiler.