gcc/range-op-ptr.cc

   1 /* Code for range operators.
   2    Copyright (C) 2017-2023 Free Software Foundation, Inc.
   3    Contributed by Andrew MacLeod <amacleod@redhat.com>
   4    and Aldy Hernandez <aldyh@redhat.com>.
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify
   9 it under the terms of the GNU General Public License as published by
  10 the Free Software Foundation; either version 3, or (at your option)
  11 any later version.
  12
  13 GCC is distributed in the hope that it will be useful,
  14 but WITHOUT ANY WARRANTY; without even the implied warranty of
  15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16 GNU General Public License for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING3.  If not see
  20 <http://www.gnu.org/licenses/>.  */
  21
  22 #include "config.h"
  23 #include "system.h"
  24 #include "coretypes.h"
  25 #include "backend.h"
  26 #include "insn-codes.h"
  27 #include "rtl.h"
  28 #include "tree.h"
  29 #include "gimple.h"
  30 #include "cfghooks.h"
  31 #include "tree-pass.h"
  32 #include "ssa.h"
  33 #include "optabs-tree.h"
  34 #include "gimple-pretty-print.h"
  35 #include "diagnostic-core.h"
  36 #include "flags.h"
  37 #include "fold-const.h"
  38 #include "stor-layout.h"
  39 #include "calls.h"
  40 #include "cfganal.h"
  41 #include "gimple-iterator.h"
  42 #include "gimple-fold.h"
  43 #include "tree-eh.h"
  44 #include "gimple-walk.h"
  45 #include "tree-cfg.h"
  46 #include "wide-int.h"
  47 #include "value-relation.h"
  48 #include "range-op.h"
  49 #include "tree-ssa-ccp.h"
  50 #include "range-op-mixed.h"
  51
  52 class pointer_plus_operator : public range_operator
  53 {
  54   using range_operator::op2_range;
  55 public:
  56   virtual void wi_fold (irange &r, tree type,
  57                         const wide_int &lh_lb,
  58                         const wide_int &lh_ub,
  59                         const wide_int &rh_lb,
  60                         const wide_int &rh_ub) const;
  61   virtual bool op2_range (irange &r, tree type,
  62                           const irange &lhs,
  63                           const irange &op1,
  64                           relation_trio = TRIO_VARYING) const;
  65   void update_bitmask (irange &r, const irange &lh, const irange &rh) const
  66     { update_known_bitmask (r, POINTER_PLUS_EXPR, lh, rh); }
  67 } op_pointer_plus;
  68
  69 void
  70 pointer_plus_operator::wi_fold (irange &r, tree type,
  71                                 const wide_int &lh_lb,
  72                                 const wide_int &lh_ub,
  73                                 const wide_int &rh_lb,
  74                                 const wide_int &rh_ub) const
  75 {
  76   // Check for [0,0] + const, and simply return the const.
  77   if (lh_lb == 0 && lh_ub == 0 && rh_lb == rh_ub)
  78     {
  79       r.set (type, rh_lb, rh_lb);
  80       return;
  81     }
  82
  83   // For pointer types, we are really only interested in asserting
  84   // whether the expression evaluates to non-NULL.
  85   //
  86   // With -fno-delete-null-pointer-checks we need to be more
  87   // conservative.  As some object might reside at address 0,
  88   // then some offset could be added to it and the same offset
  89   // subtracted again and the result would be NULL.
  90   // E.g.
  91   // static int a[12]; where &a[0] is NULL and
  92   // ptr = &a[6];
  93   // ptr -= 6;
  94   // ptr will be NULL here, even when there is POINTER_PLUS_EXPR
  95   // where the first range doesn't include zero and the second one
  96   // doesn't either.  As the second operand is sizetype (unsigned),
  97   // consider all ranges where the MSB could be set as possible
  98   // subtractions where the result might be NULL.
  99   if ((!wi_includes_zero_p (type, lh_lb, lh_ub)
 100        || !wi_includes_zero_p (type, rh_lb, rh_ub))
 101       && !TYPE_OVERFLOW_WRAPS (type)
 102       && (flag_delete_null_pointer_checks
 103           || !wi::sign_mask (rh_ub)))
 104     r = range_nonzero (type);
 105   else if (lh_lb == lh_ub && lh_lb == 0
 106            && rh_lb == rh_ub && rh_lb == 0)
 107     r = range_zero (type);
 108   else
 109    r.set_varying (type);
 110 }
 111
 112 bool
 113 pointer_plus_operator::op2_range (irange &r, tree type,
 114                                   const irange &lhs ATTRIBUTE_UNUSED,
 115                                   const irange &op1 ATTRIBUTE_UNUSED,
 116                                   relation_trio trio) const
 117 {
 118   relation_kind rel = trio.lhs_op1 ();
 119   r.set_varying (type);
 120
 121   // If the LHS and OP1 are equal, the op2 must be zero.
 122   if (rel == VREL_EQ)
 123     r.set_zero (type);
 124   // If the LHS and OP1 are not equal, the offset must be non-zero.
 125   else if (rel == VREL_NE)
 126     r.set_nonzero (type);
 127   else
 128     return false;
 129   return true;
 130 }
 131
 132 class pointer_min_max_operator : public range_operator
 133 {
 134 public:
 135   virtual void wi_fold (irange & r, tree type,
 136                         const wide_int &lh_lb, const wide_int &lh_ub,
 137                         const wide_int &rh_lb, const wide_int &rh_ub) const;
 138 } op_ptr_min_max;
 139
 140 void
 141 pointer_min_max_operator::wi_fold (irange &r, tree type,
 142                                    const wide_int &lh_lb,
 143                                    const wide_int &lh_ub,
 144                                    const wide_int &rh_lb,
 145                                    const wide_int &rh_ub) const
 146 {
 147   // For MIN/MAX expressions with pointers, we only care about
 148   // nullness.  If both are non null, then the result is nonnull.
 149   // If both are null, then the result is null.  Otherwise they
 150   // are varying.
 151   if (!wi_includes_zero_p (type, lh_lb, lh_ub)
 152       && !wi_includes_zero_p (type, rh_lb, rh_ub))
 153     r = range_nonzero (type);
 154   else if (wi_zero_p (type, lh_lb, lh_ub) && wi_zero_p (type, rh_lb, rh_ub))
 155     r = range_zero (type);
 156   else
 157     r.set_varying (type);
 158 }
 159
 160 class pointer_and_operator : public range_operator
 161 {
 162 public:
 163   virtual void wi_fold (irange &r, tree type,
 164                         const wide_int &lh_lb, const wide_int &lh_ub,
 165                         const wide_int &rh_lb, const wide_int &rh_ub) const;
 166 } op_pointer_and;
 167
 168 void
 169 pointer_and_operator::wi_fold (irange &r, tree type,
 170                                const wide_int &lh_lb,
 171                                const wide_int &lh_ub,
 172                                const wide_int &rh_lb ATTRIBUTE_UNUSED,
 173                                const wide_int &rh_ub ATTRIBUTE_UNUSED) const
 174 {
 175   // For pointer types, we are really only interested in asserting
 176   // whether the expression evaluates to non-NULL.
 177   if (wi_zero_p (type, lh_lb, lh_ub) || wi_zero_p (type, lh_lb, lh_ub))
 178     r = range_zero (type);
 179   else
 180     r.set_varying (type);
 181 }
 182
 183
 184 class pointer_or_operator : public range_operator
 185 {
 186 public:
 187   using range_operator::op1_range;
 188   using range_operator::op2_range;
 189   virtual bool op1_range (irange &r, tree type,
 190                           const irange &lhs,
 191                           const irange &op2,
 192                           relation_trio rel = TRIO_VARYING) const;
 193   virtual bool op2_range (irange &r, tree type,
 194                           const irange &lhs,
 195                           const irange &op1,
 196                           relation_trio rel = TRIO_VARYING) const;
 197   virtual void wi_fold (irange &r, tree type,
 198                         const wide_int &lh_lb, const wide_int &lh_ub,
 199                         const wide_int &rh_lb, const wide_int &rh_ub) const;
 200 } op_pointer_or;
 201
 202 bool
 203 pointer_or_operator::op1_range (irange &r, tree type,
 204                                 const irange &lhs,
 205                                 const irange &op2 ATTRIBUTE_UNUSED,
 206                                 relation_trio) const
 207 {
 208   if (lhs.undefined_p ())
 209     return false;
 210   if (lhs.zero_p ())
 211     {
 212       r.set_zero (type);
 213       return true;
 214     }
 215   r.set_varying (type);
 216   return true;
 217 }
 218
 219 bool
 220 pointer_or_operator::op2_range (irange &r, tree type,
 221                                 const irange &lhs,
 222                                 const irange &op1,
 223                                 relation_trio) const
 224 {
 225   return pointer_or_operator::op1_range (r, type, lhs, op1);
 226 }
 227
 228 void
 229 pointer_or_operator::wi_fold (irange &r, tree type,
 230                               const wide_int &lh_lb,
 231                               const wide_int &lh_ub,
 232                               const wide_int &rh_lb,
 233                               const wide_int &rh_ub) const
 234 {
 235   // For pointer types, we are really only interested in asserting
 236   // whether the expression evaluates to non-NULL.
 237   if (!wi_includes_zero_p (type, lh_lb, lh_ub)
 238       && !wi_includes_zero_p (type, rh_lb, rh_ub))
 239     r = range_nonzero (type);
 240   else if (wi_zero_p (type, lh_lb, lh_ub) && wi_zero_p (type, rh_lb, rh_ub))
 241     r = range_zero (type);
 242   else
 243     r.set_varying (type);
 244 }
 245
 246 class operator_pointer_diff : public range_operator
 247 {
 248   virtual bool op1_op2_relation_effect (irange &lhs_range,
 249                                         tree type,
 250                                         const irange &op1_range,
 251                                         const irange &op2_range,
 252                                         relation_kind rel) const;
 253   void update_bitmask (irange &r, const irange &lh, const irange &rh) const
 254     { update_known_bitmask (r, POINTER_DIFF_EXPR, lh, rh); }
 255 } op_pointer_diff;
 256
 257 bool
 258 operator_pointer_diff::op1_op2_relation_effect (irange &lhs_range, tree type,
 259                                                 const irange &op1_range,
 260                                                 const irange &op2_range,
 261                                                 relation_kind rel) const
 262 {
 263   return minus_op1_op2_relation_effect (lhs_range, type, op1_range, op2_range,
 264                                         rel);
 265 }
 266
 267 // ----------------------------------------------------------------------
 268 // Hybrid operators for the 4 operations which integer and pointers share,
 269 // but which have different implementations.  Simply check the type in
 270 // the call and choose the appropriate method.
 271 // Once there is a PRANGE signature, simply add the appropriate
 272 // prototypes in the rmixed range class, and remove these hybrid classes.
 273
 274 class hybrid_and_operator : public operator_bitwise_and
 275 {
 276 public:
 277   using range_operator::op1_range;
 278   using range_operator::op2_range;
 279   using range_operator::lhs_op1_relation;
 280   bool op1_range (irange &r, tree type,
 281                   const irange &lhs, const irange &op2,
 282                   relation_trio rel = TRIO_VARYING) const final override
 283     {
 284       if (INTEGRAL_TYPE_P (type))
 285         return operator_bitwise_and::op1_range (r, type, lhs, op2, rel);
 286       else
 287         return false;
 288     }
 289   bool op2_range (irange &r, tree type,
 290                   const irange &lhs, const irange &op1,
 291                   relation_trio rel = TRIO_VARYING) const final override
 292     {
 293       if (INTEGRAL_TYPE_P (type))
 294         return operator_bitwise_and::op2_range (r, type, lhs, op1, rel);
 295       else
 296         return false;
 297     }
 298   relation_kind lhs_op1_relation (const irange &lhs,
 299                                   const irange &op1, const irange &op2,
 300                                   relation_kind rel) const final override
 301     {
 302       if (!lhs.undefined_p () && INTEGRAL_TYPE_P (lhs.type ()))
 303         return operator_bitwise_and::lhs_op1_relation (lhs, op1, op2, rel);
 304       else
 305         return VREL_VARYING;
 306     }
 307   void update_bitmask (irange &r, const irange &lh,
 308                        const irange &rh) const final override
 309     {
 310       if (!r.undefined_p () && INTEGRAL_TYPE_P (r.type ()))
 311         operator_bitwise_and::update_bitmask (r, lh, rh);
 312     }
 313
 314   void wi_fold (irange &r, tree type, const wide_int &lh_lb,
 315                 const wide_int &lh_ub, const wide_int &rh_lb,
 316                 const wide_int &rh_ub) const final override
 317     {
 318       if (INTEGRAL_TYPE_P (type))
 319         return operator_bitwise_and::wi_fold (r, type, lh_lb, lh_ub,
 320                                               rh_lb, rh_ub);
 321       else
 322         return op_pointer_and.wi_fold (r, type, lh_lb, lh_ub, rh_lb, rh_ub);
 323     }
 324 } op_hybrid_and;
 325
 326 // Temporary class which dispatches routines to either the INT version or
 327 // the pointer version depending on the type.  Once PRANGE is a range
 328 // class, we can remove the hybrid.
 329
 330 class hybrid_or_operator : public operator_bitwise_or
 331 {
 332 public:
 333   using range_operator::op1_range;
 334   using range_operator::op2_range;
 335   using range_operator::lhs_op1_relation;
 336   bool op1_range (irange &r, tree type,
 337                   const irange &lhs, const irange &op2,
 338                   relation_trio rel = TRIO_VARYING) const final override
 339     {
 340       if (INTEGRAL_TYPE_P (type))
 341         return operator_bitwise_or::op1_range (r, type, lhs, op2, rel);
 342       else
 343         return op_pointer_or.op1_range (r, type, lhs, op2, rel);
 344     }
 345   bool op2_range (irange &r, tree type,
 346                   const irange &lhs, const irange &op1,
 347                   relation_trio rel = TRIO_VARYING) const final override
 348     {
 349       if (INTEGRAL_TYPE_P (type))
 350         return operator_bitwise_or::op2_range (r, type, lhs, op1, rel);
 351       else
 352         return op_pointer_or.op2_range (r, type, lhs, op1, rel);
 353     }
 354   void update_bitmask (irange &r, const irange &lh,
 355                        const irange &rh) const final override
 356     {
 357       if (!r.undefined_p () && INTEGRAL_TYPE_P (r.type ()))
 358         operator_bitwise_or::update_bitmask (r, lh, rh);
 359     }
 360
 361   void wi_fold (irange &r, tree type, const wide_int &lh_lb,
 362                 const wide_int &lh_ub, const wide_int &rh_lb,
 363                 const wide_int &rh_ub) const final override
 364     {
 365       if (INTEGRAL_TYPE_P (type))
 366         return operator_bitwise_or::wi_fold (r, type, lh_lb, lh_ub,
 367                                               rh_lb, rh_ub);
 368       else
 369         return op_pointer_or.wi_fold (r, type, lh_lb, lh_ub, rh_lb, rh_ub);
 370     }
 371 } op_hybrid_or;
 372
 373 // Temporary class which dispatches routines to either the INT version or
 374 // the pointer version depending on the type.  Once PRANGE is a range
 375 // class, we can remove the hybrid.
 376
 377 class hybrid_min_operator : public operator_min
 378 {
 379 public:
 380   void update_bitmask (irange &r, const irange &lh,
 381                        const irange &rh) const final override
 382     {
 383       if (!r.undefined_p () && INTEGRAL_TYPE_P (r.type ()))
 384         operator_min::update_bitmask (r, lh, rh);
 385     }
 386
 387   void wi_fold (irange &r, tree type, const wide_int &lh_lb,
 388                 const wide_int &lh_ub, const wide_int &rh_lb,
 389                 const wide_int &rh_ub) const final override
 390     {
 391       if (INTEGRAL_TYPE_P (type))
 392         return operator_min::wi_fold (r, type, lh_lb, lh_ub, rh_lb, rh_ub);
 393       else
 394         return op_ptr_min_max.wi_fold (r, type, lh_lb, lh_ub, rh_lb, rh_ub);
 395     }
 396 } op_hybrid_min;
 397
 398 class hybrid_max_operator : public operator_max
 399 {
 400 public:
 401   void update_bitmask (irange &r, const irange &lh,
 402                        const irange &rh) const final override
 403     {
 404       if (!r.undefined_p () && INTEGRAL_TYPE_P (r.type ()))
 405         operator_max::update_bitmask (r, lh, rh);
 406     }
 407
 408   void wi_fold (irange &r, tree type, const wide_int &lh_lb,
 409                 const wide_int &lh_ub, const wide_int &rh_lb,
 410                 const wide_int &rh_ub) const final override
 411     {
 412       if (INTEGRAL_TYPE_P (type))
 413         return operator_max::wi_fold (r, type, lh_lb, lh_ub, rh_lb, rh_ub);
 414       else
 415         return op_ptr_min_max.wi_fold (r, type, lh_lb, lh_ub, rh_lb, rh_ub);
 416     }
 417 } op_hybrid_max;
 418
 419 // Initialize any pointer operators to the primary table
 420
 421 void
 422 range_op_table::initialize_pointer_ops ()
 423 {
 424   set (POINTER_PLUS_EXPR, op_pointer_plus);
 425   set (POINTER_DIFF_EXPR, op_pointer_diff);
 426   set (BIT_AND_EXPR, op_hybrid_and);
 427   set (BIT_IOR_EXPR, op_hybrid_or);
 428   set (MIN_EXPR, op_hybrid_min);
 429   set (MAX_EXPR, op_hybrid_max);
 430 }