https://gcc.gnu.org/g:977fd87bade47e7624d803ba0cc549d819c03fe1
commit r17-3206-g977fd87bade47e7624d803ba0cc549d819c03fe1 Author: Andrew MacLeod <[email protected]> Date: Fri Aug 7 13:23:40 2026 -0400 Allow range invert to fail. Return a boolean from range invert() to handle cases where an inversion cannot be represented. PR tree-optimization/126536 gcc/ * gimple-range-edge.cc (calc_switch_ranges): Check that invert worked. * gimple-range-op.cc (cfn_toupper_tolower::fold_range): Likewise. * range-op-ptr.cc (operator_equal::op1_range): Likewise. (operator_not_equal::op1_range): Likewise. * range-op.cc (operator_equal::op1_range): Likewise. (operator_not_equal::op1_range): Likewise. (operator_rshift::op1_range): Likewise. (operator_logical_not::fold_range): Likewise. * tree-ssa-loop-unswitch.cc (unswitch_predicate): Likewise. * value-range.cc (irange_bitmask::range_from_mask): Likewise. (prange::invert): Return bool for success/fail. (irange::invert): Likewise. (irange::snap_subranges): Check that invert worked. (range_tests_int_range_max): Confirm failed invert works. (range_tests_misc): Check invert return value. * value-range.h (irange::invert): Add boolean return value. (prange::invert): Add boolean return value. * vr-values.cc (simplify_switch_using_ranges): Check invert result. gcc/testsuite/ * gcc.dg/pr126536-1.c: New. * gcc.dg/pr126536-2.c: New. Diff: --- gcc/gimple-range-edge.cc | 3 +- gcc/gimple-range-op.cc | 6 ++- gcc/range-op-ptr.cc | 6 ++- gcc/range-op.cc | 15 ++++-- gcc/testsuite/gcc.dg/pr126536-1.c | 55 ++++++++++++++++++++++ gcc/testsuite/gcc.dg/pr126536-2.c | 47 +++++++++++++++++++ gcc/tree-ssa-loop-unswitch.cc | 8 +++- gcc/value-range.cc | 97 ++++++++++++++++++++++++++------------- gcc/value-range.h | 4 +- gcc/vr-values.cc | 3 +- 10 files changed, 197 insertions(+), 47 deletions(-) diff --git a/gcc/gimple-range-edge.cc b/gcc/gimple-range-edge.cc index a8fc6995e852..5fb6f6bf783e 100644 --- a/gcc/gimple-range-edge.cc +++ b/gcc/gimple-range-edge.cc @@ -166,7 +166,8 @@ gimple_outgoing_range::calc_switch_ranges (gswitch *sw) default_range.set_undefined (); else { - def_range.invert (); + bool res = def_range.invert (); + gcc_checking_assert (res); default_range.intersect (def_range); } diff --git a/gcc/gimple-range-op.cc b/gcc/gimple-range-op.cc index 9be143f85cd1..63eccc3fb9fe 100644 --- a/gcc/gimple-range-op.cc +++ b/gcc/gimple-range-op.cc @@ -848,7 +848,8 @@ cfn_toupper_tolower::fold_range (irange &r, tree type, const irange &lh, { // Return the range passed in without any lower case characters, // but including all the upper case ones. - lowers.invert (); + bool res = lowers.invert (); + gcc_checking_assert (res); r.intersect (lowers); r.union_ (uppers); } @@ -856,7 +857,8 @@ cfn_toupper_tolower::fold_range (irange &r, tree type, const irange &lh, { // Return the range passed in without any lower case characters, // but including all the upper case ones. - uppers.invert (); + bool res = uppers.invert (); + gcc_checking_assert (res); r.intersect (uppers); r.union_ (lowers); } diff --git a/gcc/range-op-ptr.cc b/gcc/range-op-ptr.cc index a96e53bf1412..8113d67f62e0 100644 --- a/gcc/range-op-ptr.cc +++ b/gcc/range-op-ptr.cc @@ -952,7 +952,8 @@ operator_equal::op1_range (prange &r, tree type, && wi::eq_p (op2.lower_bound(), op2.upper_bound())) { r = op2; - r.invert (); + if (!r.invert ()) + return false; } else r.set_varying (type); @@ -1051,7 +1052,8 @@ operator_not_equal::op1_range (prange &r, tree type, && wi::eq_p (op2.lower_bound(), op2.upper_bound())) { r = op2; - r.invert (); + if (!r.invert ()) + return false; } else r.set_varying (type); diff --git a/gcc/range-op.cc b/gcc/range-op.cc index 333ac748815c..39c1271f0806 100644 --- a/gcc/range-op.cc +++ b/gcc/range-op.cc @@ -1124,7 +1124,8 @@ operator_equal::op1_range (irange &r, tree type, && wi::eq_p (op2.lower_bound(), op2.upper_bound())) { r = op2; - r.invert (); + if (!r.invert ()) + return false; } else r.set_varying (type); @@ -1227,7 +1228,8 @@ operator_not_equal::op1_range (irange &r, tree type, && wi::eq_p (op2.lower_bound(), op2.upper_bound())) { r = op2; - r.invert (); + if (!r.invert ()) + return false; } else r.set_varying (type); @@ -2981,7 +2983,8 @@ operator_rshift::op1_range (irange &r, r.union_ (ub); if (!lhs_refined.contains_zero_p ()) { - mask_range.invert (); + if (!mask_range.invert ()) + return false; r.intersect (mask_range); } return true; @@ -4517,8 +4520,10 @@ operator_logical_not::fold_range (irange &r, tree type, r = lh; if (!lh.varying_p () && !lh.undefined_p ()) - r.invert (); - + { + if (!r.invert ()) + return false; + } return true; } diff --git a/gcc/testsuite/gcc.dg/pr126536-1.c b/gcc/testsuite/gcc.dg/pr126536-1.c new file mode 100644 index 000000000000..0f8701589bcb --- /dev/null +++ b/gcc/testsuite/gcc.dg/pr126536-1.c @@ -0,0 +1,55 @@ +/* { dg-do run } */ +/* { dg-options "-O2" } */ +volatile int v; + +__attribute__((noipa)) int +f (int a) +{ + switch (a) + { + case 1: case 3: case 5: case 7: case 9: case 11: case 13: case 15: case 17: case 19: case 21: case 23: case 25: case 27: case 29: + case 31: case 33: case 35: case 37: case 39: case 41: case 43: case 45: case 47: case 49: case 51: case 53: case 55: case 57: case 59: + case 61: case 63: case 65: case 67: case 69: case 71: case 73: case 75: case 77: case 79: case 81: case 83: case 85: case 87: case 89: + case 91: case 93: case 95: case 97: case 99: case 101: case 103: case 105: case 107: case 109: case 111: case 113: case 115: case 117: case 119: + case 121: case 123: case 125: case 127: case 129: case 131: case 133: case 135: case 137: case 139: case 141: case 143: case 145: case 147: case 149: + case 151: case 153: case 155: case 157: case 159: case 161: case 163: case 165: case 167: case 169: case 171: case 173: case 175: case 177: case 179: + case 181: case 183: case 185: case 187: case 189: case 191: case 193: case 195: case 197: case 199: case 201: case 203: case 205: case 207: case 209: + case 211: case 213: case 215: case 217: case 219: case 221: case 223: case 225: case 227: case 229: case 231: case 233: case 235: case 237: case 239: + case 241: case 243: case 245: case 247: case 249: case 251: case 253: case 255: case 257: case 259: case 261: case 263: case 265: case 267: case 269: + case 271: case 273: case 275: case 277: case 279: case 281: case 283: case 285: case 287: case 289: case 291: case 293: case 295: case 297: case 299: + case 301: case 303: case 305: case 307: case 309: case 311: case 313: case 315: case 317: case 319: case 321: case 323: case 325: case 327: case 329: + case 331: case 333: case 335: case 337: case 339: case 341: case 343: case 345: case 347: case 349: case 351: case 353: case 355: case 357: case 359: + case 361: case 363: case 365: case 367: case 369: case 371: case 373: case 375: case 377: case 379: case 381: case 383: case 385: case 387: case 389: + case 391: case 393: case 395: case 397: case 399: case 401: case 403: case 405: case 407: case 409: case 411: case 413: case 415: case 417: case 419: + case 421: case 423: case 425: case 427: case 429: case 431: case 433: case 435: case 437: case 439: case 441: case 443: case 445: case 447: case 449: + case 451: case 453: case 455: case 457: case 459: case 461: case 463: case 465: case 467: case 469: case 471: case 473: case 475: case 477: case 479: + case 481: case 483: case 485: case 487: case 489: case 491: case 493: case 495: case 497: case 499: case 501: case 503: case 505: case 507: case 509: + break; + default: + return 0; + } + v += 1; v += 2; v += 3; v += 4; v += 5; v += 6; v += 7; v += 8; v += 9; v += 10; + v += 11; v += 12; v += 13; v += 14; v += 15; v += 16; v += 17; v += 18; v += 19; v += 20; + v += 21; v += 22; v += 23; v += 24; v += 25; v += 26; v += 27; v += 28; v += 29; v += 30; + v += 31; v += 32; v += 33; v += 34; v += 35; v += 36; v += 37; v += 38; v += 39; v += 40; + switch (a) + { + case 0 ... 100000: + return 1; + case 200000: + return 3; + default: + return 2; + } +} + +int +main (void) +{ + if (f (3) != 1) + __builtin_abort (); + if (f (2) != 0) + __builtin_abort (); + return 0; +} + diff --git a/gcc/testsuite/gcc.dg/pr126536-2.c b/gcc/testsuite/gcc.dg/pr126536-2.c new file mode 100644 index 000000000000..cb18c8f8662b --- /dev/null +++ b/gcc/testsuite/gcc.dg/pr126536-2.c @@ -0,0 +1,47 @@ +/* { dg-do run } */ +/* { dg-options "-O2 -funswitch-loops" } */ +volatile int v; + +__attribute__((noipa)) int +f (int a, int n) +{ + int s = 0; + for (int i = 0; i < n; i++) + { + switch (a) + { + case 1: case 3: case 5: case 7: case 9: case 11: case 13: case 15: case 17: case 19: case 21: case 23: case 25: case 27: case 29: + case 31: case 33: case 35: case 37: case 39: case 41: case 43: case 45: case 47: case 49: case 51: case 53: case 55: case 57: case 59: + case 61: case 63: case 65: case 67: case 69: case 71: case 73: case 75: case 77: case 79: case 81: case 83: case 85: case 87: case 89: + case 91: case 93: case 95: case 97: case 99: case 101: case 103: case 105: case 107: case 109: case 111: case 113: case 115: case 117: case 119: + case 121: case 123: case 125: case 127: case 129: case 131: case 133: case 135: case 137: case 139: case 141: case 143: case 145: case 147: case 149: + case 151: case 153: case 155: case 157: case 159: case 161: case 163: case 165: case 167: case 169: case 171: case 173: case 175: case 177: case 179: + case 181: case 183: case 185: case 187: case 189: case 191: case 193: case 195: case 197: case 199: case 201: case 203: case 205: case 207: case 209: + case 211: case 213: case 215: case 217: case 219: case 221: case 223: case 225: case 227: case 229: case 231: case 233: case 235: case 237: case 239: + case 241: case 243: case 245: case 247: case 249: case 251: case 253: case 255: case 257: case 259: case 261: case 263: case 265: case 267: case 269: + case 271: case 273: case 275: case 277: case 279: case 281: case 283: case 285: case 287: case 289: case 291: case 293: case 295: case 297: case 299: + case 301: case 303: case 305: case 307: case 309: case 311: case 313: case 315: case 317: case 319: case 321: case 323: case 325: case 327: case 329: + case 331: case 333: case 335: case 337: case 339: case 341: case 343: case 345: case 347: case 349: case 351: case 353: case 355: case 357: case 359: + case 361: case 363: case 365: case 367: case 369: case 371: case 373: case 375: case 377: case 379: case 381: case 383: case 385: case 387: case 389: + case 391: case 393: case 395: case 397: case 399: case 401: case 403: case 405: case 407: case 409: case 411: case 413: case 415: case 417: case 419: + case 421: case 423: case 425: case 427: case 429: case 431: case 433: case 435: case 437: case 439: case 441: case 443: case 445: case 447: case 449: + case 451: case 453: case 455: case 457: case 459: case 461: case 463: case 465: case 467: case 469: case 471: case 473: case 475: case 477: case 479: + case 481: case 483: case 485: case 487: case 489: case 491: case 493: case 495: case 497: case 499: case 501: case 503: case 505: case 507: case 509: + s += 1; break; + default: + s += 2; break; + } + v++; + } + return s; +} + +int +main (void) +{ + if (f (1, 3) != 3) + __builtin_abort (); + if (f (2, 3) != 6) + __builtin_abort (); + return 0; +} diff --git a/gcc/tree-ssa-loop-unswitch.cc b/gcc/tree-ssa-loop-unswitch.cc index a34c5385c7cc..6b3c8c4a2918 100644 --- a/gcc/tree-ssa-loop-unswitch.cc +++ b/gcc/tree-ssa-loop-unswitch.cc @@ -116,7 +116,13 @@ struct unswitch_predicate false_range = true_range; if (!false_range.varying_p () && !false_range.undefined_p ()) - false_range.invert (); + { + if (!false_range.invert ()) + { + true_range.set_varying (TREE_TYPE (lhs)); + false_range.set_varying (TREE_TYPE (lhs)); + } + } count = e->count (); num = predicates->length (); predicates->safe_push (this); diff --git a/gcc/value-range.cc b/gcc/value-range.cc index 93a956796743..8c0d418f6144 100644 --- a/gcc/value-range.cc +++ b/gcc/value-range.cc @@ -126,7 +126,8 @@ irange_bitmask::range_from_mask (irange &r, tree type) const // Remove the valid value from the excluded range and form an anti-range. wide_int allow = value () & ub; mask_range.intersect (int_range<2> (type, allow, allow, VR_ANTI_RANGE)); - mask_range.invert (); + bool res = mask_range.invert (); + gcc_checking_assert (res); r.intersect (mask_range); if (TYPE_SIGN (type) == SIGNED) @@ -138,7 +139,8 @@ irange_bitmask::range_from_mask (irange &r, tree type) const // Remove the one allowed value from that set. wide_int allow = value () | lb; mask_range.intersect (int_range<2> (type, allow, allow, VR_ANTI_RANGE)); - mask_range.invert (); + res = mask_range.invert (); + gcc_checking_assert (res); r.intersect (mask_range); } return true; @@ -882,14 +884,18 @@ prange::operator== (const prange &src) const } -void +// Return the inverse of a range. Return false if thre is no invert +// calculatable. + +bool prange::invert () { - gcc_checking_assert (!undefined_p () && !varying_p ()); + if (undefined_p () || varying_p ()) + return false; // Invert the points_to object. If that worked, this is done. if (pt_invert ()) - return; + return true; else set_pt_unknown (); @@ -918,6 +924,7 @@ prange::invert () } else set_varying (type ()); + return true; } void @@ -2723,12 +2730,18 @@ add_one (const wide_int &x, tree type, wi::overflow_type &overflow) return wi::add (x, 1, UNSIGNED, &overflow); } -// Return the inverse of a range. +// Return the inverse of a range. Return false if thre is no invert +// calculatable. -void +bool irange::invert () { - gcc_checking_assert (!undefined_p () && !varying_p ()); + // UNDEFINED cannot be converted to varying because there is no type + // assocaited. Callers need to handle these cases. + // Its also ambiguous.. VARYING inverted could also arguably be VARYING + // in some cases. Likewise with UNDEFINED. + if (undefined_p () || varying_p ()) + return false; // We always need one more set of bounds to represent an inverse, so // if we're at the limit, we can't properly represent things. @@ -2737,7 +2750,7 @@ irange::invert () // [5, 10][20, 30], we would need a 3 sub-range set // [-MIN, 4][11, 19][31, MAX]. // - // In this case, return the most conservative thing. + // In this case, return false. // // However, if any of the extremes of the range are -MIN/+MAX, we // know we will not need an extra bound. For example: @@ -2805,10 +2818,19 @@ irange::invert () if (type_max != orig_range.m_base[i]) { tmp = add_one (orig_range.m_base[i], ttype, ovf); - m_base[nitems++] = tmp; - m_base[nitems++] = type_max; - if (ovf) - nitems -= 2; + if (!ovf) + { + // Check to see if this inversion is going to work. + if (nitems / 2 >= m_max_ranges) + { + // No room for the extra field, so revert to the original value + // and return false. + *this = orig_range; + return false; + } + m_base[nitems++] = tmp; + m_base[nitems++] = type_max; + } } m_num_ranges = nitems / 2; @@ -2818,6 +2840,7 @@ irange::invert () if (flag_checking) verify_range (); + return true; } // This routine will take the bounds [LB, UB], and apply the bitmask to those @@ -2912,7 +2935,8 @@ irange::snap_subranges () // Remove any subranges which are no invalid. if (!invalid.undefined_p ()) { - invalid.invert (); + bool res = invalid.invert (); + gcc_checking_assert (res); intersect (invalid); } return changed; @@ -3318,6 +3342,9 @@ range_tests_int_range_max () big.intersect (tmp); ASSERT_TRUE (big.num_pairs () == 4); + // Cannot resize tmp, and the invert does not fit, + ASSERT_FALSE (tmp.invert ()); + // Test that [10,10][20,20] does NOT contain 15. { int_range_max i1 = range_int (10, 10); @@ -3469,6 +3496,7 @@ test_irange_snap_bounds () static void range_tests_misc () { + bool res; tree u128_type = build_nonstandard_integer_type (128, /*unsigned=*/1); int_range<2> i1, i2, i3; int_range<2> r0, r1, rold; @@ -3493,11 +3521,11 @@ range_tests_misc () int_range<2> max = int_range<2> (one_bit_type, one_bit_max, one_bit_max); int_range<2> t; t = min; - t.invert (); - ASSERT_TRUE (t == max); + res = t.invert (); + ASSERT_TRUE (res && t == max); t = max; - t.invert (); - ASSERT_TRUE (t == min); + res = t.invert (); + ASSERT_TRUE (res && t == min); } // Test that NOT(255) is [0..254] in 8-bit land. @@ -3522,8 +3550,8 @@ range_tests_misc () r1 = int_range<1> (u128_type, wi::uhwi (128, 128), wi::sub (wi::minus_one (128), wi::uhwi (128, 128))); - r0.invert (); - ASSERT_TRUE (r0 == r1); + res = r0.invert (); + ASSERT_TRUE (res && r0 == r1); r0.set_varying (integer_type_node); wide_int minint = r0.lower_bound (); @@ -3536,7 +3564,8 @@ range_tests_misc () // Check that ~[0,5] => [6,MAX] for unsigned int. r0 = range_uint (0, 5); - r0.invert (); + res = r0.invert (); + ASSERT_TRUE (res); ASSERT_TRUE (r0 == int_range<1> (unsigned_type_node, wi::uhwi (6, TYPE_PRECISION (unsigned_type_node)), maxuint)); @@ -3545,8 +3574,8 @@ range_tests_misc () r0 = int_range<1> (unsigned_type_node, wi::uhwi (10, TYPE_PRECISION (unsigned_type_node)), maxuint); - r0.invert (); - ASSERT_TRUE (r0 == range_uint (0, 9)); + res = r0.invert (); + ASSERT_TRUE (res && r0 == range_uint (0, 9)); // Check that ~[0,5] => [6,MAX] for unsigned 128-bit numbers. r0 = range_uint128 (0, 5, VR_ANTI_RANGE); @@ -3578,17 +3607,17 @@ range_tests_misc () r2 = int_range<1> (integer_type_node, minint, INT(9)); r2.union_ (int_range<1> (integer_type_node, INT(21), maxint)); ASSERT_FALSE (r2.undefined_p ()); - r1.invert (); - ASSERT_TRUE (r1 == r2); + res = r1.invert (); + ASSERT_TRUE (res && r1 == r2); // Test that NOT(NOT(x)) == x. - r2.invert (); - ASSERT_TRUE (r0 == r2); + res = r2.invert (); + ASSERT_TRUE (res && r0 == r2); // Test that booleans and their inverse work as expected. r0.set_zero (boolean_type_node); ASSERT_TRUE (r0 == range_false ()); - r0.invert (); - ASSERT_TRUE (r0 == range_true ()); + res = r0.invert (); + ASSERT_TRUE (res && r0 == range_true ()); // Make sure NULL and non-NULL of pointer types work, and that // inverses of them are consistent. @@ -3596,9 +3625,10 @@ range_tests_misc () prange p0; p0.set_zero (voidp); prange p1 = p0; - p0.invert (); - p0.invert (); - ASSERT_TRUE (p0 == p1); + res = p0.invert (); + ASSERT_TRUE (res); + res = p0.invert (); + ASSERT_TRUE (res && p0 == p1); // The intersection of: // [0, +INF] MASK 0xff..00 VALUE 0xf8 @@ -3657,7 +3687,8 @@ range_tests_misc () // Test contains_zero_p(). r0 = range_int (0, 0); - r0.invert (); + res = r0.invert (); + ASSERT_TRUE (res); ASSERT_FALSE (r0.contains_zero_p ()); // r0 = ~[1,1] diff --git a/gcc/value-range.h b/gcc/value-range.h index d7c426fd2f74..290ea4bb83c5 100644 --- a/gcc/value-range.h +++ b/gcc/value-range.h @@ -326,7 +326,7 @@ public: // In-place operators. virtual bool union_ (const vrange &) override; virtual bool intersect (const vrange &) override; - void invert (); + bool invert (); // Operator overloads. irange& operator= (const irange &); @@ -435,7 +435,7 @@ public: bool operator== (const prange &) const; void set (tree type, const wide_int &, const wide_int &, value_range_kind = VR_RANGE); - void invert (); + bool invert (); bool contains_p (const wide_int &) const; wide_int lower_bound () const; wide_int upper_bound () const; diff --git a/gcc/vr-values.cc b/gcc/vr-values.cc index f0d9a71bd40e..c4edff871f06 100644 --- a/gcc/vr-values.cc +++ b/gcc/vr-values.cc @@ -1350,7 +1350,8 @@ simplify_using_ranges::simplify_switch_using_ranges (gswitch *stmt) // Add case label to the keep list. cases.safe_push (x); // Remove case_range from needing to be handled by the default. - case_range.invert (); + if (!case_range.invert ()) + return false; default_range.intersect (case_range); }
