gcc/range-op-ptr.cc

   1 /* Code for range operators.
   2    Copyright (C) 2017-2025 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 bool
  53 range_operator::fold_range (prange &, tree, const prange &, const prange &,
  54                             relation_trio) const
  55 {
  56   return false;
  57 }
  58
  59 bool
  60 range_operator::fold_range (prange &, tree, const prange &, const irange &,
  61                             relation_trio) const
  62 {
  63   return false;
  64 }
  65
  66 bool
  67 range_operator::fold_range (irange &, tree, const prange &, const prange &,
  68                             relation_trio) const
  69 {
  70   return false;
  71 }
  72
  73 bool
  74 range_operator::fold_range (prange &, tree, const irange &, const prange &,
  75                             relation_trio) const
  76 {
  77   return false;
  78 }
  79
  80 bool
  81 range_operator::fold_range (irange &, tree, const prange &, const irange &,
  82                             relation_trio) const
  83 {
  84   return false;
  85 }
  86
  87 bool
  88 range_operator::op1_op2_relation_effect (prange &, tree,
  89                                          const prange &,
  90                                          const prange &,
  91                                          relation_kind) const
  92 {
  93   return false;
  94 }
  95
  96 bool
  97 range_operator::op1_op2_relation_effect (prange &, tree,
  98                                          const prange &,
  99                                          const irange &,
 100                                          relation_kind) const
 101 {
 102   return false;
 103 }
 104
 105 bool
 106 range_operator::op1_op2_relation_effect (irange &, tree,
 107                                          const prange &,
 108                                          const prange &,
 109                                          relation_kind) const
 110 {
 111   return false;
 112 }
 113
 114 bool
 115 range_operator::op1_op2_relation_effect (prange &, tree,
 116                                          const irange &,
 117                                          const prange &,
 118                                          relation_kind) const
 119 {
 120   return false;
 121 }
 122
 123 bool
 124 range_operator::op1_op2_relation_effect (irange &, tree,
 125                                          const prange &,
 126                                          const irange &,
 127                                          relation_kind) const
 128 {
 129   return false;
 130 }
 131
 132 bool
 133 range_operator::op1_range (prange &, tree,
 134                            const prange &lhs ATTRIBUTE_UNUSED,
 135                            const prange &op2 ATTRIBUTE_UNUSED,
 136                            relation_trio) const
 137 {
 138   return false;
 139 }
 140
 141 bool
 142 range_operator::op1_range (prange &, tree,
 143                            const irange &lhs ATTRIBUTE_UNUSED,
 144                            const prange &op2 ATTRIBUTE_UNUSED,
 145                            relation_trio) const
 146 {
 147   return false;
 148 }
 149
 150 bool
 151 range_operator::op1_range (prange &, tree,
 152                            const prange &lhs ATTRIBUTE_UNUSED,
 153                            const irange &op2 ATTRIBUTE_UNUSED,
 154                            relation_trio) const
 155 {
 156   return false;
 157 }
 158
 159 bool
 160 range_operator::op1_range (irange &, tree,
 161                            const prange &lhs ATTRIBUTE_UNUSED,
 162                            const irange &op2 ATTRIBUTE_UNUSED,
 163                            relation_trio) const
 164 {
 165   return false;
 166 }
 167
 168 bool
 169 range_operator::op2_range (prange &, tree,
 170                            const irange &lhs ATTRIBUTE_UNUSED,
 171                            const prange &op1 ATTRIBUTE_UNUSED,
 172                            relation_trio) const
 173 {
 174   return false;
 175 }
 176
 177 bool
 178 range_operator::op2_range (irange &, tree,
 179                            const prange &lhs ATTRIBUTE_UNUSED,
 180                            const prange &op1 ATTRIBUTE_UNUSED,
 181                            relation_trio) const
 182 {
 183   return false;
 184 }
 185
 186 relation_kind
 187 range_operator::op1_op2_relation (const irange &lhs ATTRIBUTE_UNUSED,
 188                                   const prange &op1 ATTRIBUTE_UNUSED,
 189                                   const prange &op2 ATTRIBUTE_UNUSED) const
 190 {
 191   return VREL_VARYING;
 192 }
 193
 194 relation_kind
 195 range_operator::lhs_op1_relation (const prange &lhs ATTRIBUTE_UNUSED,
 196                                   const irange &op1 ATTRIBUTE_UNUSED,
 197                                   const irange &op2 ATTRIBUTE_UNUSED,
 198                                   relation_kind rel ATTRIBUTE_UNUSED) const
 199 {
 200   return VREL_VARYING;
 201 }
 202
 203 relation_kind
 204 range_operator::lhs_op1_relation (const irange &lhs ATTRIBUTE_UNUSED,
 205                                   const prange &op1 ATTRIBUTE_UNUSED,
 206                                   const prange &op2 ATTRIBUTE_UNUSED,
 207                                   relation_kind rel ATTRIBUTE_UNUSED) const
 208 {
 209   return VREL_VARYING;
 210 }
 211
 212 relation_kind
 213 range_operator::lhs_op1_relation (const prange &lhs ATTRIBUTE_UNUSED,
 214                                   const prange &op1 ATTRIBUTE_UNUSED,
 215                                   const prange &op2 ATTRIBUTE_UNUSED,
 216                                   relation_kind rel ATTRIBUTE_UNUSED) const
 217 {
 218   return VREL_VARYING;
 219 }
 220
 221 void
 222 range_operator::update_bitmask (irange &,
 223                                 const prange &,
 224                                 const prange &) const
 225 {
 226 }
 227
 228 // Return the upper limit for a type.
 229
 230 static inline wide_int
 231 max_limit (const_tree type)
 232 {
 233   return wi::max_value (TYPE_PRECISION (type), TYPE_SIGN (type));
 234 }
 235
 236 // Return the lower limit for a type.
 237
 238 static inline wide_int
 239 min_limit (const_tree type)
 240 {
 241   return wi::min_value (TYPE_PRECISION (type), TYPE_SIGN (type));
 242 }
 243
 244 // Build a range that is < VAL and store it in R.
 245
 246 static void
 247 build_lt (prange &r, tree type, const prange &val)
 248 {
 249   wi::overflow_type ov;
 250   wide_int lim = wi::sub (val.upper_bound (), 1, UNSIGNED, &ov);
 251
 252   // If val - 1 underflows, check if X < MIN, which is an empty range.
 253   if (ov)
 254     r.set_undefined ();
 255   else
 256     r.set (type, min_limit (type), lim);
 257 }
 258
 259 // Build a range that is <= VAL and store it in R.
 260
 261 static void
 262 build_le (prange &r, tree type, const prange &val)
 263 {
 264   r.set (type, min_limit (type), val.upper_bound ());
 265 }
 266
 267 // Build a range that is > VAL and store it in R.
 268
 269 static void
 270 build_gt (prange &r, tree type, const prange &val)
 271 {
 272   wi::overflow_type ov;
 273   wide_int lim = wi::add (val.lower_bound (), 1, UNSIGNED, &ov);
 274
 275   // If val + 1 overflows, check is for X > MAX, which is an empty range.
 276   if (ov)
 277     r.set_undefined ();
 278   else
 279     r.set (type, lim, max_limit (type));
 280
 281 }
 282
 283 // Build a range that is >= VAL and store it in R.
 284
 285 static void
 286 build_ge (prange &r, tree type, const prange &val)
 287 {
 288   r.set (type, val.lower_bound (), max_limit (type));
 289 }
 290
 291 class pointer_plus_operator : public range_operator
 292 {
 293   using range_operator::update_bitmask;
 294   using range_operator::fold_range;
 295   using range_operator::op2_range;
 296 public:
 297   virtual bool fold_range (prange &r, tree type,
 298                            const prange &op1,
 299                            const irange &op2,
 300                            relation_trio) const final override;
 301   virtual bool op2_range (irange &r, tree type,
 302                           const prange &lhs,
 303                           const prange &op1,
 304                           relation_trio = TRIO_VARYING) const final override;
 305   void update_bitmask (prange &r, const prange &lh, const irange &rh) const
 306     { update_known_bitmask (r, POINTER_PLUS_EXPR, lh, rh); }
 307 } op_pointer_plus;
 308
 309 bool
 310 pointer_plus_operator::fold_range (prange &r, tree type,
 311                                    const prange &op1,
 312                                    const irange &op2,
 313                                    relation_trio) const
 314 {
 315   if (empty_range_varying (r, type, op1, op2))
 316     return true;
 317
 318   const wide_int lh_lb = op1.lower_bound ();
 319   const wide_int lh_ub = op1.upper_bound ();
 320   const wide_int rh_lb = op2.lower_bound ();
 321   const wide_int rh_ub = op2.upper_bound ();
 322
 323   // Check for [0,0] + const, and simply return the const.
 324   if (lh_lb == 0 && lh_ub == 0 && rh_lb == rh_ub)
 325     {
 326       r.set (type, rh_lb, rh_lb);
 327       return true;
 328     }
 329
 330   // For pointer types, we are really only interested in asserting
 331   // whether the expression evaluates to non-NULL.
 332   //
 333   // With -fno-delete-null-pointer-checks we need to be more
 334   // conservative.  As some object might reside at address 0,
 335   // then some offset could be added to it and the same offset
 336   // subtracted again and the result would be NULL.
 337   // E.g.
 338   // static int a[12]; where &a[0] is NULL and
 339   // ptr = &a[6];
 340   // ptr -= 6;
 341   // ptr will be NULL here, even when there is POINTER_PLUS_EXPR
 342   // where the first range doesn't include zero and the second one
 343   // doesn't either.  As the second operand is sizetype (unsigned),
 344   // consider all ranges where the MSB could be set as possible
 345   // subtractions where the result might be NULL.
 346   if ((!wi_includes_zero_p (type, lh_lb, lh_ub)
 347        || !wi_includes_zero_p (type, rh_lb, rh_ub))
 348       && !TYPE_OVERFLOW_WRAPS (type)
 349       && (flag_delete_null_pointer_checks
 350           || !wi::sign_mask (rh_ub)))
 351     r.set_nonzero (type);
 352   else if (lh_lb == lh_ub && lh_lb == 0
 353            && rh_lb == rh_ub && rh_lb == 0)
 354     r.set_zero (type);
 355   else
 356    r.set_varying (type);
 357
 358   update_known_bitmask (r, POINTER_PLUS_EXPR, op1, op2);
 359   return true;
 360 }
 361
 362 bool
 363 pointer_plus_operator::op2_range (irange &r, tree type,
 364                                   const prange &lhs ATTRIBUTE_UNUSED,
 365                                   const prange &op1 ATTRIBUTE_UNUSED,
 366                                   relation_trio trio) const
 367 {
 368   relation_kind rel = trio.lhs_op1 ();
 369   r.set_varying (type);
 370
 371   // If the LHS and OP1 are equal, the op2 must be zero.
 372   if (rel == VREL_EQ)
 373     r.set_zero (type);
 374   // If the LHS and OP1 are not equal, the offset must be non-zero.
 375   else if (rel == VREL_NE)
 376     r.set_nonzero (type);
 377   else
 378     return false;
 379   return true;
 380 }
 381
 382 bool
 383 operator_bitwise_or::fold_range (prange &r, tree type,
 384                                  const prange &op1,
 385                                  const prange &op2,
 386                                  relation_trio) const
 387 {
 388   // For pointer types, we are really only interested in asserting
 389   // whether the expression evaluates to non-NULL.
 390   if (!range_includes_zero_p (op1) || !range_includes_zero_p (op2))
 391     r.set_nonzero (type);
 392   else if (op1.zero_p () && op2.zero_p ())
 393     r.set_zero (type);
 394   else
 395     r.set_varying (type);
 396
 397   update_known_bitmask (r, BIT_IOR_EXPR, op1, op2);
 398   return true;
 399 }
 400
 401
 402 class operator_pointer_diff : public range_operator
 403 {
 404   using range_operator::fold_range;
 405   using range_operator::update_bitmask;
 406   using range_operator::op1_op2_relation_effect;
 407   virtual bool fold_range (irange &r, tree type,
 408                            const prange &op1,
 409                            const prange &op2,
 410                            relation_trio trio) const final override;
 411   virtual bool op1_op2_relation_effect (irange &lhs_range,
 412                                         tree type,
 413                                         const prange &op1_range,
 414                                         const prange &op2_range,
 415                                         relation_kind rel) const final override;
 416   void update_bitmask (irange &r,
 417                        const prange &lh, const prange &rh) const final override
 418   { update_known_bitmask (r, POINTER_DIFF_EXPR, lh, rh); }
 419 } op_pointer_diff;
 420
 421 bool
 422 operator_pointer_diff::fold_range (irange &r, tree type,
 423                                    const prange &op1,
 424                                    const prange &op2,
 425                                    relation_trio trio) const
 426 {
 427   gcc_checking_assert (r.supports_type_p (type));
 428
 429   r.set_varying (type);
 430   relation_kind rel = trio.op1_op2 ();
 431   op1_op2_relation_effect (r, type, op1, op2, rel);
 432   update_bitmask (r, op1, op2);
 433   return true;
 434 }
 435
 436 bool
 437 operator_pointer_diff::op1_op2_relation_effect (irange &lhs_range, tree type,
 438                                                 const prange &op1_range,
 439                                                 const prange &op2_range,
 440                                                 relation_kind rel) const
 441 {
 442   int_range<2> op1, op2, tmp;
 443   range_op_handler cast (CONVERT_EXPR);
 444
 445   if (!cast.fold_range (op1, type, op1_range, tmp)
 446       || !cast.fold_range (op2, type, op2_range, tmp))
 447     return false;
 448
 449   return minus_op1_op2_relation_effect (lhs_range, type, op1, op2, rel);
 450 }
 451
 452 bool
 453 operator_identity::fold_range (prange &r, tree type ATTRIBUTE_UNUSED,
 454                                const prange &lh ATTRIBUTE_UNUSED,
 455                                const prange &rh ATTRIBUTE_UNUSED,
 456                                relation_trio) const
 457 {
 458   r = lh;
 459   return true;
 460 }
 461
 462 relation_kind
 463 operator_identity::lhs_op1_relation (const prange &lhs,
 464                                      const prange &op1 ATTRIBUTE_UNUSED,
 465                                      const prange &op2 ATTRIBUTE_UNUSED,
 466                                      relation_kind) const
 467 {
 468   if (lhs.undefined_p ())
 469     return VREL_VARYING;
 470   // Simply a copy, so they are equivalent.
 471   return VREL_EQ;
 472 }
 473
 474 bool
 475 operator_identity::op1_range (prange &r, tree type ATTRIBUTE_UNUSED,
 476                               const prange &lhs,
 477                               const prange &op2 ATTRIBUTE_UNUSED,
 478                               relation_trio) const
 479 {
 480   r = lhs;
 481   return true;
 482 }
 483
 484 bool
 485 operator_cst::fold_range (prange &r, tree type ATTRIBUTE_UNUSED,
 486                           const prange &lh,
 487                           const prange & ATTRIBUTE_UNUSED,
 488                           relation_trio) const
 489 {
 490   r = lh;
 491   return true;
 492 }
 493
 494 // Cast between pointers.
 495
 496 bool
 497 operator_cast::fold_range (prange &r, tree type,
 498                            const prange &inner,
 499                            const prange &outer,
 500                            relation_trio) const
 501 {
 502   if (empty_range_varying (r, type, inner, outer))
 503     return true;
 504
 505   r.set (type, inner.lower_bound (), inner.upper_bound ());
 506   r.update_bitmask (inner.get_bitmask ());
 507   return true;
 508 }
 509
 510 // Cast a pointer to an integer.
 511
 512 bool
 513 operator_cast::fold_range (irange &r, tree type,
 514                            const prange &inner,
 515                            const irange &outer,
 516                            relation_trio) const
 517 {
 518   if (empty_range_varying (r, type, inner, outer))
 519     return true;
 520
 521   // Represent INNER as an integer of the same size, and then cast it
 522   // to the resulting integer type.
 523   tree pointer_uint_type = make_unsigned_type (TYPE_PRECISION (inner.type ()));
 524   r.set (pointer_uint_type, inner.lower_bound (), inner.upper_bound ());
 525   r.update_bitmask (inner.get_bitmask ());
 526   range_cast (r, type);
 527   return true;
 528 }
 529
 530 // Cast an integer to a pointer.
 531
 532 bool
 533 operator_cast::fold_range (prange &r, tree type,
 534                            const irange &inner,
 535                            const prange &outer,
 536                            relation_trio) const
 537 {
 538   if (empty_range_varying (r, type, inner, outer))
 539     return true;
 540
 541   // Cast INNER to an integer of the same size as the pointer we want,
 542   // and then copy the bounds to the resulting pointer range.
 543   int_range<2> tmp = inner;
 544   tree pointer_uint_type = make_unsigned_type (TYPE_PRECISION (type));
 545   range_cast (tmp, pointer_uint_type);
 546   r.set (type, tmp.lower_bound (), tmp.upper_bound ());
 547   r.update_bitmask (tmp.get_bitmask ());
 548   return true;
 549 }
 550
 551 bool
 552 operator_cast::op1_range (prange &r, tree type,
 553                           const prange &lhs,
 554                           const prange &op2,
 555                           relation_trio trio) const
 556 {
 557   if (lhs.undefined_p ())
 558     return false;
 559   gcc_checking_assert (types_compatible_p (op2.type(), type));
 560
 561   // Conversion from other pointers or a constant (including 0/NULL)
 562   // are straightforward.
 563   if (POINTER_TYPE_P (lhs.type ())
 564       || (lhs.singleton_p ()
 565           && TYPE_PRECISION (lhs.type ()) >= TYPE_PRECISION (type)))
 566     fold_range (r, type, lhs, op2, trio);
 567   else
 568     {
 569       // If the LHS is not a pointer nor a singleton, then it is
 570       // either VARYING or non-zero.
 571       if (!lhs.undefined_p () && !range_includes_zero_p (lhs))
 572         r.set_nonzero (type);
 573       else
 574         r.set_varying (type);
 575     }
 576   r.intersect (op2);
 577   return true;
 578 }
 579
 580 bool
 581 operator_cast::op1_range (irange &r, tree type,
 582                           const prange &lhs,
 583                           const irange &op2,
 584                           relation_trio trio) const
 585 {
 586   if (lhs.undefined_p ())
 587     return false;
 588   gcc_checking_assert (types_compatible_p (op2.type(), type));
 589
 590   // Conversion from other pointers or a constant (including 0/NULL)
 591   // are straightforward.
 592   if (POINTER_TYPE_P (lhs.type ())
 593       || (lhs.singleton_p ()
 594           && TYPE_PRECISION (lhs.type ()) >= TYPE_PRECISION (type)))
 595     fold_range (r, type, lhs, op2, trio);
 596   else
 597     {
 598       // If the LHS is not a pointer nor a singleton, then it is
 599       // either VARYING or non-zero.
 600       if (!lhs.undefined_p () && !range_includes_zero_p (lhs))
 601         r.set_nonzero (type);
 602       else
 603         r.set_varying (type);
 604     }
 605   r.intersect (op2);
 606   return true;
 607 }
 608
 609 bool
 610 operator_cast::op1_range (prange &r, tree type,
 611                           const irange &lhs,
 612                           const prange &op2,
 613                           relation_trio trio) const
 614 {
 615   if (lhs.undefined_p ())
 616     return false;
 617   gcc_checking_assert (types_compatible_p (op2.type(), type));
 618
 619   // Conversion from other pointers or a constant (including 0/NULL)
 620   // are straightforward.
 621   if (POINTER_TYPE_P (lhs.type ())
 622       || (lhs.singleton_p ()
 623           && TYPE_PRECISION (lhs.type ()) >= TYPE_PRECISION (type)))
 624     fold_range (r, type, lhs, op2, trio);
 625   else
 626     {
 627       // If the LHS is not a pointer nor a singleton, then it is
 628       // either VARYING or non-zero.
 629       if (!lhs.undefined_p () && !range_includes_zero_p (lhs))
 630         r.set_nonzero (type);
 631       else
 632         r.set_varying (type);
 633     }
 634   r.intersect (op2);
 635   return true;
 636 }
 637
 638 relation_kind
 639 operator_cast::lhs_op1_relation (const prange &lhs,
 640                                  const prange &op1,
 641                                  const prange &op2 ATTRIBUTE_UNUSED,
 642                                  relation_kind) const
 643 {
 644   if (lhs.undefined_p () || op1.undefined_p ())
 645     return VREL_VARYING;
 646   unsigned lhs_prec = TYPE_PRECISION (lhs.type ());
 647   unsigned op1_prec = TYPE_PRECISION (op1.type ());
 648   // If the result gets sign extended into a larger type check first if this
 649   // qualifies as a partial equivalence.
 650   if (TYPE_SIGN (op1.type ()) == SIGNED && lhs_prec > op1_prec)
 651     {
 652       // If the result is sign extended, and the LHS is larger than op1,
 653       // check if op1's range can be negative as the sign extension will
 654       // cause the upper bits to be 1 instead of 0, invalidating the PE.
 655       int_range<3> negs = range_negatives (op1.type ());
 656       negs.intersect (op1);
 657       if (!negs.undefined_p ())
 658         return VREL_VARYING;
 659     }
 660
 661   unsigned prec = MIN (lhs_prec, op1_prec);
 662   return bits_to_pe (prec);
 663 }
 664
 665 relation_kind
 666 operator_cast::lhs_op1_relation (const prange &lhs,
 667                                  const irange &op1,
 668                                  const irange &op2 ATTRIBUTE_UNUSED,
 669                                  relation_kind) const
 670 {
 671   if (lhs.undefined_p () || op1.undefined_p ())
 672     return VREL_VARYING;
 673   unsigned lhs_prec = TYPE_PRECISION (lhs.type ());
 674   unsigned op1_prec = TYPE_PRECISION (op1.type ());
 675   // If the result gets sign extended into a larger type check first if this
 676   // qualifies as a partial equivalence.
 677   if (TYPE_SIGN (op1.type ()) == SIGNED && lhs_prec > op1_prec)
 678     {
 679       // If the result is sign extended, and the LHS is larger than op1,
 680       // check if op1's range can be negative as the sign extension will
 681       // cause the upper bits to be 1 instead of 0, invalidating the PE.
 682       int_range<3> negs = range_negatives (op1.type ());
 683       negs.intersect (op1);
 684       if (!negs.undefined_p ())
 685         return VREL_VARYING;
 686     }
 687
 688   unsigned prec = MIN (lhs_prec, op1_prec);
 689   return bits_to_pe (prec);
 690 }
 691
 692 relation_kind
 693 operator_cast::lhs_op1_relation (const irange &lhs,
 694                                  const prange &op1,
 695                                  const prange &op2 ATTRIBUTE_UNUSED,
 696                                  relation_kind) const
 697 {
 698   if (lhs.undefined_p () || op1.undefined_p ())
 699     return VREL_VARYING;
 700   unsigned lhs_prec = TYPE_PRECISION (lhs.type ());
 701   unsigned op1_prec = TYPE_PRECISION (op1.type ());
 702   // If the result gets sign extended into a larger type check first if this
 703   // qualifies as a partial equivalence.
 704   if (TYPE_SIGN (op1.type ()) == SIGNED && lhs_prec > op1_prec)
 705     {
 706       // If the result is sign extended, and the LHS is larger than op1,
 707       // check if op1's range can be negative as the sign extension will
 708       // cause the upper bits to be 1 instead of 0, invalidating the PE.
 709       int_range<3> negs = range_negatives (op1.type ());
 710       negs.intersect (op1);
 711       if (!negs.undefined_p ())
 712         return VREL_VARYING;
 713     }
 714
 715   unsigned prec = MIN (lhs_prec, op1_prec);
 716   return bits_to_pe (prec);
 717 }
 718
 719 bool
 720 operator_min::fold_range (prange &r, tree type,
 721                           const prange &op1,
 722                           const prange &op2,
 723                           relation_trio) const
 724 {
 725   // For MIN/MAX expressions with pointers, we only care about
 726   // nullness.  If both are non null, then the result is nonnull.
 727   // If both are null, then the result is null.  Otherwise they
 728   // are varying.
 729   if (!range_includes_zero_p (op1)
 730       && !range_includes_zero_p (op2))
 731     r.set_nonzero (type);
 732   else if (op1.zero_p () && op2.zero_p ())
 733     r.set_zero (type);
 734   else
 735     r.set_varying (type);
 736
 737   update_known_bitmask (r, MIN_EXPR, op1, op2);
 738   return true;
 739 }
 740
 741 bool
 742 operator_max::fold_range (prange &r, tree type,
 743                           const prange &op1,
 744                           const prange &op2,
 745                           relation_trio) const
 746 {
 747   // For MIN/MAX expressions with pointers, we only care about
 748   // nullness.  If both are non null, then the result is nonnull.
 749   // If both are null, then the result is null.  Otherwise they
 750   // are varying.
 751   if (!range_includes_zero_p (op1)
 752       && !range_includes_zero_p (op2))
 753     r.set_nonzero (type);
 754   else if (op1.zero_p () && op2.zero_p ())
 755     r.set_zero (type);
 756   else
 757     r.set_varying (type);
 758
 759   update_known_bitmask (r, MAX_EXPR, op1, op2);
 760   return true;
 761 }
 762
 763 bool
 764 operator_addr_expr::op1_range (prange &r, tree type,
 765                                const prange &lhs,
 766                                const prange &op2,
 767                                relation_trio) const
 768 {
 769   if (empty_range_varying (r, type, lhs, op2))
 770     return true;
 771
 772   // Return a non-null pointer of the LHS type (passed in op2), but only
 773   // if we cant overflow, eitherwise a no-zero offset could wrap to zero.
 774   // See PR 111009.
 775   if (!lhs.undefined_p ()
 776       && !range_includes_zero_p (lhs)
 777       && TYPE_OVERFLOW_UNDEFINED (type))
 778     r.set_nonzero (type);
 779   else
 780     r.set_varying (type);
 781   return true;
 782 }
 783
 784 bool
 785 operator_bitwise_and::fold_range (prange &r, tree type,
 786                                   const prange &op1,
 787                                   const prange &op2 ATTRIBUTE_UNUSED,
 788                                   relation_trio) const
 789 {
 790   // For pointer types, we are really only interested in asserting
 791   // whether the expression evaluates to non-NULL.
 792   if (op1.zero_p () || op2.zero_p ())
 793     r.set_zero (type);
 794   else
 795     r.set_varying (type);
 796
 797   update_known_bitmask (r, BIT_AND_EXPR, op1, op2);
 798   return true;
 799 }
 800
 801 bool
 802 operator_equal::fold_range (irange &r, tree type,
 803                             const prange &op1,
 804                             const prange &op2,
 805                             relation_trio rel) const
 806 {
 807   if (relop_early_resolve (r, type, op1, op2, rel, VREL_EQ))
 808     return true;
 809
 810   // We can be sure the values are always equal or not if both ranges
 811   // consist of a single value, and then compare them.
 812   bool op1_const = wi::eq_p (op1.lower_bound (), op1.upper_bound ());
 813   bool op2_const = wi::eq_p (op2.lower_bound (), op2.upper_bound ());
 814   if (op1_const && op2_const)
 815     {
 816       if (wi::eq_p (op1.lower_bound (), op2.upper_bound()))
 817         r = range_true (type);
 818       else
 819         r = range_false (type);
 820     }
 821   else
 822     {
 823       // If ranges do not intersect, we know the range is not equal,
 824       // otherwise we don't know anything for sure.
 825       prange tmp = op1;
 826       tmp.intersect (op2);
 827       if (tmp.undefined_p ())
 828         r = range_false (type);
 829       // Check if a constant cannot satisfy the bitmask requirements.
 830       else if (op2_const && !op1.get_bitmask ().member_p (op2.lower_bound ()))
 831          r = range_false (type);
 832       else if (op1_const && !op2.get_bitmask ().member_p (op1.lower_bound ()))
 833          r = range_false (type);
 834       else
 835         r = range_true_and_false (type);
 836     }
 837
 838   //update_known_bitmask (r, EQ_EXPR, op1, op2);
 839   return true;
 840 }
 841
 842 bool
 843 operator_equal::op1_range (prange &r, tree type,
 844                            const irange &lhs,
 845                            const prange &op2,
 846                            relation_trio) const
 847 {
 848   switch (get_bool_state (r, lhs, type))
 849     {
 850     case BRS_TRUE:
 851       // If it's true, the result is the same as OP2.
 852       r = op2;
 853       break;
 854
 855     case BRS_FALSE:
 856       // If the result is false, the only time we know anything is
 857       // if OP2 is a constant.
 858       if (!op2.undefined_p ()
 859           && wi::eq_p (op2.lower_bound(), op2.upper_bound()))
 860         {
 861           r = op2;
 862           r.invert ();
 863         }
 864       else
 865         r.set_varying (type);
 866       break;
 867
 868     default:
 869       break;
 870     }
 871   return true;
 872 }
 873
 874 bool
 875 operator_equal::op2_range (prange &r, tree type,
 876                            const irange &lhs,
 877                            const prange &op1,
 878                            relation_trio rel) const
 879 {
 880   return operator_equal::op1_range (r, type, lhs, op1, rel.swap_op1_op2 ());
 881 }
 882
 883 relation_kind
 884 operator_equal::op1_op2_relation (const irange &lhs, const prange &,
 885                                   const prange &) const
 886 {
 887   if (lhs.undefined_p ())
 888     return VREL_UNDEFINED;
 889
 890   // FALSE = op1 == op2 indicates NE_EXPR.
 891   if (lhs.zero_p ())
 892     return VREL_NE;
 893
 894   // TRUE = op1 == op2 indicates EQ_EXPR.
 895   if (!range_includes_zero_p (lhs))
 896     return VREL_EQ;
 897   return VREL_VARYING;
 898 }
 899
 900 bool
 901 operator_not_equal::fold_range (irange &r, tree type,
 902                                 const prange &op1,
 903                                 const prange &op2,
 904                                 relation_trio rel) const
 905 {
 906   if (relop_early_resolve (r, type, op1, op2, rel, VREL_NE))
 907     return true;
 908
 909   // We can be sure the values are always equal or not if both ranges
 910   // consist of a single value, and then compare them.
 911   bool op1_const = wi::eq_p (op1.lower_bound (), op1.upper_bound ());
 912   bool op2_const = wi::eq_p (op2.lower_bound (), op2.upper_bound ());
 913   if (op1_const && op2_const)
 914     {
 915       if (wi::ne_p (op1.lower_bound (), op2.upper_bound()))
 916         r = range_true (type);
 917       else
 918         r = range_false (type);
 919     }
 920   else
 921     {
 922       // If ranges do not intersect, we know the range is not equal,
 923       // otherwise we don't know anything for sure.
 924       prange tmp = op1;
 925       tmp.intersect (op2);
 926       if (tmp.undefined_p ())
 927         r = range_true (type);
 928       // Check if a constant cannot satisfy the bitmask requirements.
 929       else if (op2_const && !op1.get_bitmask ().member_p (op2.lower_bound ()))
 930          r = range_true (type);
 931       else if (op1_const && !op2.get_bitmask ().member_p (op1.lower_bound ()))
 932          r = range_true (type);
 933       else
 934         r = range_true_and_false (type);
 935     }
 936
 937   //update_known_bitmask (r, NE_EXPR, op1, op2);
 938   return true;
 939 }
 940
 941 bool
 942 operator_not_equal::op1_range (prange &r, tree type,
 943                                const irange &lhs,
 944                                const prange &op2,
 945                                relation_trio) const
 946 {
 947   switch (get_bool_state (r, lhs, type))
 948     {
 949     case BRS_TRUE:
 950       // If the result is true, the only time we know anything is if
 951       // OP2 is a constant.
 952       if (!op2.undefined_p ()
 953           && wi::eq_p (op2.lower_bound(), op2.upper_bound()))
 954         {
 955           r = op2;
 956           r.invert ();
 957         }
 958       else
 959         r.set_varying (type);
 960       break;
 961
 962     case BRS_FALSE:
 963       // If it's false, the result is the same as OP2.
 964       r = op2;
 965       break;
 966
 967     default:
 968       break;
 969     }
 970   return true;
 971 }
 972
 973
 974 bool
 975 operator_not_equal::op2_range (prange &r, tree type,
 976                                const irange &lhs,
 977                                const prange &op1,
 978                                relation_trio rel) const
 979 {
 980   return operator_not_equal::op1_range (r, type, lhs, op1, rel.swap_op1_op2 ());
 981 }
 982
 983 relation_kind
 984 operator_not_equal::op1_op2_relation (const irange &lhs, const prange &,
 985                                       const prange &) const
 986 {
 987   if (lhs.undefined_p ())
 988     return VREL_UNDEFINED;
 989
 990   // FALSE = op1 != op2  indicates EQ_EXPR.
 991   if (lhs.zero_p ())
 992     return VREL_EQ;
 993
 994   // TRUE = op1 != op2  indicates NE_EXPR.
 995   if (!range_includes_zero_p (lhs))
 996     return VREL_NE;
 997   return VREL_VARYING;
 998 }
 999
1000 bool
1001 operator_lt::fold_range (irange &r, tree type,
1002                          const prange &op1,
1003                          const prange &op2,
1004                          relation_trio rel) const
1005 {
1006   if (relop_early_resolve (r, type, op1, op2, rel, VREL_LT))
1007     return true;
1008
1009   signop sign = TYPE_SIGN (op1.type ());
1010   gcc_checking_assert (sign == TYPE_SIGN (op2.type ()));
1011
1012   if (wi::lt_p (op1.upper_bound (), op2.lower_bound (), sign))
1013     r = range_true (type);
1014   else if (!wi::lt_p (op1.lower_bound (), op2.upper_bound (), sign))
1015     r = range_false (type);
1016   // Use nonzero bits to determine if < 0 is false.
1017   else if (op2.zero_p () && !wi::neg_p (op1.get_nonzero_bits (), sign))
1018     r = range_false (type);
1019   else
1020     r = range_true_and_false (type);
1021
1022   //update_known_bitmask (r, LT_EXPR, op1, op2);
1023   return true;
1024 }
1025
1026 bool
1027 operator_lt::op1_range (prange &r, tree type,
1028                         const irange &lhs,
1029                         const prange &op2,
1030                         relation_trio) const
1031 {
1032   if (op2.undefined_p ())
1033     return false;
1034
1035   switch (get_bool_state (r, lhs, type))
1036     {
1037     case BRS_TRUE:
1038       build_lt (r, type, op2);
1039       break;
1040
1041     case BRS_FALSE:
1042       build_ge (r, type, op2);
1043       break;
1044
1045     default:
1046       break;
1047     }
1048   return true;
1049 }
1050
1051 bool
1052 operator_lt::op2_range (prange &r, tree type,
1053                         const irange &lhs,
1054                         const prange &op1,
1055                         relation_trio) const
1056 {
1057   if (op1.undefined_p ())
1058     return false;
1059
1060   switch (get_bool_state (r, lhs, type))
1061     {
1062     case BRS_TRUE:
1063       build_gt (r, type, op1);
1064       break;
1065
1066     case BRS_FALSE:
1067       build_le (r, type, op1);
1068       break;
1069
1070     default:
1071       break;
1072     }
1073   return true;
1074 }
1075
1076 relation_kind
1077 operator_lt::op1_op2_relation (const irange &lhs, const prange &,
1078                                const prange &) const
1079 {
1080   if (lhs.undefined_p ())
1081     return VREL_UNDEFINED;
1082
1083   // FALSE = op1 < op2 indicates GE_EXPR.
1084   if (lhs.zero_p ())
1085     return VREL_GE;
1086
1087   // TRUE = op1 < op2 indicates LT_EXPR.
1088   if (!range_includes_zero_p (lhs))
1089     return VREL_LT;
1090   return VREL_VARYING;
1091 }
1092
1093 bool
1094 operator_le::fold_range (irange &r, tree type,
1095                          const prange &op1,
1096                          const prange &op2,
1097                          relation_trio rel) const
1098 {
1099   if (relop_early_resolve (r, type, op1, op2, rel, VREL_LE))
1100     return true;
1101
1102   signop sign = TYPE_SIGN (op1.type ());
1103   gcc_checking_assert (sign == TYPE_SIGN (op2.type ()));
1104
1105   if (wi::le_p (op1.upper_bound (), op2.lower_bound (), sign))
1106     r = range_true (type);
1107   else if (!wi::le_p (op1.lower_bound (), op2.upper_bound (), sign))
1108     r = range_false (type);
1109   else
1110     r = range_true_and_false (type);
1111
1112   //update_known_bitmask (r, LE_EXPR, op1, op2);
1113   return true;
1114 }
1115
1116 bool
1117 operator_le::op1_range (prange &r, tree type,
1118                         const irange &lhs,
1119                         const prange &op2,
1120                         relation_trio) const
1121 {
1122   if (op2.undefined_p ())
1123     return false;
1124
1125   switch (get_bool_state (r, lhs, type))
1126     {
1127     case BRS_TRUE:
1128       build_le (r, type, op2);
1129       break;
1130
1131     case BRS_FALSE:
1132       build_gt (r, type, op2);
1133       break;
1134
1135     default:
1136       break;
1137     }
1138   return true;
1139 }
1140
1141 bool
1142 operator_le::op2_range (prange &r, tree type,
1143                         const irange &lhs,
1144                         const prange &op1,
1145                         relation_trio) const
1146 {
1147   if (op1.undefined_p ())
1148     return false;
1149
1150   switch (get_bool_state (r, lhs, type))
1151     {
1152     case BRS_TRUE:
1153       build_ge (r, type, op1);
1154       break;
1155
1156     case BRS_FALSE:
1157       build_lt (r, type, op1);
1158       break;
1159
1160     default:
1161       break;
1162     }
1163   return true;
1164 }
1165
1166 relation_kind
1167 operator_le::op1_op2_relation (const irange &lhs, const prange &,
1168                                const prange &) const
1169 {
1170   if (lhs.undefined_p ())
1171     return VREL_UNDEFINED;
1172
1173   // FALSE = op1 <= op2 indicates GT_EXPR.
1174   if (lhs.zero_p ())
1175     return VREL_GT;
1176
1177   // TRUE = op1 <= op2 indicates LE_EXPR.
1178   if (!range_includes_zero_p (lhs))
1179     return VREL_LE;
1180   return VREL_VARYING;
1181 }
1182
1183 bool
1184 operator_gt::fold_range (irange &r, tree type,
1185                          const prange &op1, const prange &op2,
1186                          relation_trio rel) const
1187 {
1188   if (relop_early_resolve (r, type, op1, op2, rel, VREL_GT))
1189     return true;
1190
1191   signop sign = TYPE_SIGN (op1.type ());
1192   gcc_checking_assert (sign == TYPE_SIGN (op2.type ()));
1193
1194   if (wi::gt_p (op1.lower_bound (), op2.upper_bound (), sign))
1195     r = range_true (type);
1196   else if (!wi::gt_p (op1.upper_bound (), op2.lower_bound (), sign))
1197     r = range_false (type);
1198   else
1199     r = range_true_and_false (type);
1200
1201   //update_known_bitmask (r, GT_EXPR, op1, op2);
1202   return true;
1203 }
1204
1205 bool
1206 operator_gt::op1_range (prange &r, tree type,
1207                         const irange &lhs, const prange &op2,
1208                         relation_trio) const
1209 {
1210   if (op2.undefined_p ())
1211     return false;
1212
1213   switch (get_bool_state (r, lhs, type))
1214     {
1215     case BRS_TRUE:
1216       build_gt (r, type, op2);
1217       break;
1218
1219     case BRS_FALSE:
1220       build_le (r, type, op2);
1221       break;
1222
1223     default:
1224       break;
1225     }
1226   return true;
1227 }
1228
1229 bool
1230 operator_gt::op2_range (prange &r, tree type,
1231                         const irange &lhs,
1232                         const prange &op1,
1233                         relation_trio) const
1234 {
1235   if (op1.undefined_p ())
1236     return false;
1237
1238   switch (get_bool_state (r, lhs, type))
1239     {
1240     case BRS_TRUE:
1241       build_lt (r, type, op1);
1242       break;
1243
1244     case BRS_FALSE:
1245       build_ge (r, type, op1);
1246       break;
1247
1248     default:
1249       break;
1250     }
1251   return true;
1252 }
1253
1254 relation_kind
1255 operator_gt::op1_op2_relation (const irange &lhs, const prange &,
1256                                const prange &) const
1257 {
1258   if (lhs.undefined_p ())
1259     return VREL_UNDEFINED;
1260
1261   // FALSE = op1 > op2 indicates LE_EXPR.
1262   if (lhs.zero_p ())
1263     return VREL_LE;
1264
1265   // TRUE = op1 > op2 indicates GT_EXPR.
1266   if (!range_includes_zero_p (lhs))
1267     return VREL_GT;
1268   return VREL_VARYING;
1269 }
1270
1271 bool
1272 operator_ge::fold_range (irange &r, tree type,
1273                          const prange &op1,
1274                          const prange &op2,
1275                          relation_trio rel) const
1276 {
1277   if (relop_early_resolve (r, type, op1, op2, rel, VREL_GE))
1278     return true;
1279
1280   signop sign = TYPE_SIGN (op1.type ());
1281   gcc_checking_assert (sign == TYPE_SIGN (op2.type ()));
1282
1283   if (wi::ge_p (op1.lower_bound (), op2.upper_bound (), sign))
1284     r = range_true (type);
1285   else if (!wi::ge_p (op1.upper_bound (), op2.lower_bound (), sign))
1286     r = range_false (type);
1287   else
1288     r = range_true_and_false (type);
1289
1290   //update_known_bitmask (r, GE_EXPR, op1, op2);
1291   return true;
1292 }
1293
1294 bool
1295 operator_ge::op1_range (prange &r, tree type,
1296                         const irange &lhs,
1297                         const prange &op2,
1298                         relation_trio) const
1299 {
1300   if (op2.undefined_p ())
1301     return false;
1302
1303   switch (get_bool_state (r, lhs, type))
1304     {
1305     case BRS_TRUE:
1306       build_ge (r, type, op2);
1307       break;
1308
1309     case BRS_FALSE:
1310       build_lt (r, type, op2);
1311       break;
1312
1313     default:
1314       break;
1315     }
1316   return true;
1317 }
1318
1319 bool
1320 operator_ge::op2_range (prange &r, tree type,
1321                         const irange &lhs,
1322                         const prange &op1,
1323                         relation_trio) const
1324 {
1325   if (op1.undefined_p ())
1326     return false;
1327
1328   switch (get_bool_state (r, lhs, type))
1329     {
1330     case BRS_TRUE:
1331       build_le (r, type, op1);
1332       break;
1333
1334     case BRS_FALSE:
1335       build_gt (r, type, op1);
1336       break;
1337
1338     default:
1339       break;
1340     }
1341   return true;
1342 }
1343
1344 relation_kind
1345 operator_ge::op1_op2_relation (const irange &lhs, const prange &,
1346                                const prange &) const
1347 {
1348   if (lhs.undefined_p ())
1349     return VREL_UNDEFINED;
1350
1351   // FALSE = op1 >= op2 indicates LT_EXPR.
1352   if (lhs.zero_p ())
1353     return VREL_LT;
1354
1355   // TRUE = op1 >= op2 indicates GE_EXPR.
1356   if (!range_includes_zero_p (lhs))
1357     return VREL_GE;
1358   return VREL_VARYING;
1359 }
1360
1361 // Initialize any pointer operators to the primary table
1362
1363 void
1364 range_op_table::initialize_pointer_ops ()
1365 {
1366   set (POINTER_PLUS_EXPR, op_pointer_plus);
1367   set (POINTER_DIFF_EXPR, op_pointer_diff);
1368 }