https://gcc.gnu.org/g:4d22d3ead95ec862afd6726a10230e27587f4663
commit r17-4827-g4d22d3ead95ec862afd6726a10230e27587f4663 Author: Aldy Hernandez <[email protected]> Date: Wed Sep 30 10:01:36 2026 +0000 ranger: use the index range for loads from constant aggregates Currently a load from a constant table gets the range of the whole table, no matter what is known of its index. For example, with static const int tbl[4] = { 0, 5, 6, 7 }; and i in [0, 1], tbl[i] is currently [0, 0][5, 7]. With this patch we get [0, 0][5, 5]. This work comes from my DOM parity obsession, but goes beyond what DOM gets here. DOM folds a load from a constant table only when the index can be determined to be a constant, as on the path through i = 1 in: if (c) i = 1; if (tbl[i] == 5) With this patch we also narrow a load whose index is in a range: if (i < 2 && tbl[i] > 5) tbl[i] is [0, 0][5, 5], and we can fold the comparison away. This implements the following TODO in the code: /* TODO: If the array index in the expr is an SSA_NAME with a known range, we could use just values loaded from the corresponding array elements. */ Oh, and we no longer have to special case INTEGER_CSTs, as ranger happily handles those. I've also added a testcase for r17-4029-g7dab38c9d7104e, a phiopt tweak which couldn't be properly tested until now. Tested on ppc64le Linux. gcc/ChangeLog: * gimple-range-fold.cc (intersects_p): New. (class ctor_ref_range): Add SRC. (ctor_ref_range::accumulate_range_from_array_ref): Load only from the elements the range of the index reaches, a constant index included. (fold_using_range::fold_stmt): Pass the source to range_from_readonly_var. (fold_using_range::range_from_readonly_var): Add SRC. * gimple-range-fold.h (fold_using_range::range_from_readonly_var): Adjust. gcc/testsuite/ChangeLog: * gcc.dg/tree-ssa/phi-opt-52.c: New test. * gcc.dg/tree-ssa/vrp-from-cst-agg-10.c: New test. * gcc.dg/tree-ssa/vrp-from-cst-agg-11.c: New test. * gcc.dg/tree-ssa/vrp-from-cst-agg-13.c: New test. Diff: --- gcc/gimple-range-fold.cc | 61 ++++++++++++---------- gcc/gimple-range-fold.h | 2 +- gcc/testsuite/gcc.dg/tree-ssa/phi-opt-52.c | 38 ++++++++++++++ .../gcc.dg/tree-ssa/vrp-from-cst-agg-10.c | 46 ++++++++++++++++ .../gcc.dg/tree-ssa/vrp-from-cst-agg-11.c | 27 ++++++++++ .../gcc.dg/tree-ssa/vrp-from-cst-agg-13.c | 19 +++++++ 6 files changed, 163 insertions(+), 30 deletions(-) diff --git a/gcc/gimple-range-fold.cc b/gcc/gimple-range-fold.cc index 554bb4e122c2..9ac5a94341cf 100644 --- a/gcc/gimple-range-fold.cc +++ b/gcc/gimple-range-fold.cc @@ -687,7 +687,7 @@ fold_using_range::fold_stmt (vrange &r, gimple *s, fur_source &src, tree name) name = gimple_get_lhs (s); // Process addresses and loads from static constructors. - if (gimple_code (s) == GIMPLE_ASSIGN && range_from_readonly_var (r, s)) + if (gimple_code (s) == GIMPLE_ASSIGN && range_from_readonly_var (r, s, src)) return true; // Save the current range query and restore it before returning. @@ -992,6 +992,16 @@ fold_using_range::range_of_address (prange &r, gimple *stmt, fur_source &src) return true; } +// Does R contain anything in [LO, HI]? + +static bool +intersects_p (const irange &r, const wide_int &lo, const wide_int &hi) +{ + int_range_max tmp (r); + tmp.intersect (int_range<1> (r.type (), lo, hi)); + return !tmp.undefined_p (); +} + // The range of a load from a read-only aggregate: walk its initializer along // the component path of the reference, COMPONENT_PATH, from the aggregate out, // unioning into R the constants the load can reach. For example: @@ -1006,8 +1016,10 @@ fold_using_range::range_of_address (prange &r, gimple *stmt, fur_source &src) class ctor_ref_range { public: - ctor_ref_range (vrange &r, tree type, const vec<tree> &component_path) - : m_r (r), m_type (type), m_component_path (component_path) { } + ctor_ref_range (vrange &r, tree type, const vec<tree> &component_path, + fur_source &src) + : m_r (r), m_type (type), m_component_path (component_path), + m_src (src) { } bool accumulate_range (tree init, unsigned i); private: bool accumulate_range_from_scalar (tree init); @@ -1018,6 +1030,7 @@ private: vrange &m_r; tree m_type; const vec<tree> &m_component_path; + fur_source &m_src; }; // Accumulate the range of the load from INIT, the initializer reached after @@ -1132,24 +1145,6 @@ bool ctor_ref_range::accumulate_range_from_array_ref (tree init, unsigned i, tree idx) { - if (TREE_CODE (idx) == INTEGER_CST) - { - unsigned ctor_idx; - tree val = get_array_ctor_element_at_index (init, wi::to_offset (idx), - &ctor_idx); - if (!val) - { - // An index the initializer skips over, like t[1] of - // static const int t[4] = { [2] = 5 }; - // is not read as zero, unlike one past its end. - if (ctor_idx < CONSTRUCTOR_NELTS (init)) - return false; - accumulate_range_from_missing_constructor_elt (); - return true; - } - return accumulate_range (val, i); - } - tree domain = TYPE_DOMAIN (TREE_TYPE (init)); if (!TYPE_MIN_VALUE (domain) || !TYPE_MAX_VALUE (domain) @@ -1172,8 +1167,18 @@ ctor_ref_range::accumulate_range_from_array_ref (tree init, unsigned i, return true; unsigned prec = TYPE_PRECISION (type); - int_range_max missing (type, min, max); - wide_int next = missing.lower_bound (); + int_range<1> domain_r (type, min, max); + + // Narrow IDX to the ranges it can actually take. + int_range_max idx_r; + m_src.get_operand (idx_r, idx); + range_cast (idx_r, type); + idx_r.intersect (domain_r); + if (idx_r.undefined_p ()) + return false; + + int_range_max missing (idx_r); + wide_int next = domain_r.lower_bound (); unsigned ix; tree index, val; @@ -1203,10 +1208,7 @@ ctor_ref_range::accumulate_range_from_array_ref (tree init, unsigned i, missing.intersect (int_range<2> (type, lo, hi, VR_ANTI_RANGE)); next = wi::add (hi, 1); - /* TODO: If the array index in the expr is an SSA_NAME with a known - range, we could use just values loaded from the corresponding array - elements. */ - if (!accumulate_range (val, i)) + if (intersects_p (idx_r, lo, hi) && !accumulate_range (val, i)) return false; } @@ -1234,7 +1236,8 @@ ctor_ref_range::accumulate_range_from_missing_constructor_elt () // false and leave R untouched. bool -fold_using_range::range_from_readonly_var (vrange &r, gimple *stmt) +fold_using_range::range_from_readonly_var (vrange &r, gimple *stmt, + fur_source &src) { gcc_checking_assert (gimple_code (stmt) == GIMPLE_ASSIGN); tree type = TREE_TYPE (gimple_assign_lhs (stmt)); @@ -1279,7 +1282,7 @@ fold_using_range::range_from_readonly_var (vrange &r, gimple *stmt) return false; value_range tmp (type); - ctor_ref_range load (tmp, type, component_path); + ctor_ref_range load (tmp, type, component_path, src); bool res = load.accumulate_range (ctor, 0) && !tmp.varying_p (); if (res) r = tmp; diff --git a/gcc/gimple-range-fold.h b/gcc/gimple-range-fold.h index bf4310847e41..0cf14cf90dd7 100644 --- a/gcc/gimple-range-fold.h +++ b/gcc/gimple-range-fold.h @@ -181,7 +181,7 @@ protected: bool range_of_call (vrange &r, gcall *call, fur_source &src); bool range_of_cond_expr (vrange &r, gassign* cond, fur_source &src); bool range_of_address (prange &r, gimple *s, fur_source &src); - bool range_from_readonly_var (vrange &r, gimple *stmt); + bool range_from_readonly_var (vrange &r, gimple *stmt, fur_source &src); bool range_of_phi (vrange &r, gphi *phi, fur_source &src); void range_of_ssa_name_with_loop_info (vrange &, tree, class loop *, gphi *, fur_source &src); diff --git a/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-52.c b/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-52.c new file mode 100644 index 000000000000..583b32ba72c1 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-52.c @@ -0,0 +1,38 @@ +/* { dg-do run } */ +/* { dg-options "-O2" } */ + +/* The range of the load of sa[i].a under i < 2 is [1, 3]. Once it is + hoisted above the condition, that range must not fold the later + sa[i].a > 3. + + This is the testcase for r17-4029-g7dab38c9d7104e ("phiopt: clear the + range info of hoisted adjacent loads"), which could not be exercised + until now. */ + +struct S { int a, b; }; +static const struct S sa[4] = { { 1, 2 }, { 3, 4 }, { 5, 6 }, { 7, 8 } }; +volatile int vol; + +__attribute__((noipa)) int +f (int i) +{ + int r; + if (i < 2) + r = sa[i].a; + else + r = sa[i].b; + /* Enough statements that the merge block is not worth threading. */ + vol; vol; vol; vol; vol; vol; vol; vol; + vol; vol; vol; vol; vol; vol; vol; vol; + if (sa[i].a > 3) + return 100 + r; + return r; +} + +int +main () +{ + if (f (0) != 1 || f (1) != 3 || f (2) != 106 || f (3) != 108) + __builtin_abort (); + return 0; +} diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp-from-cst-agg-10.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp-from-cst-agg-10.c new file mode 100644 index 000000000000..e329f59259f8 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp-from-cst-agg-10.c @@ -0,0 +1,46 @@ +/* { dg-do link } */ +/* { dg-options "-O2 -fgimple" } */ + +/* This is: + + if (i < 2 && tbl[i] > 5) + link_error (); + + The index is [0, 1] so the range for v_3 should be [0, 0][5, 5]. */ + +static const int tbl[4] = { 0, 5, 6, 7 }; + +void link_error (void); + +[[gnu::noipa]] void __GIMPLE (ssa,startwith("evrp")) +foo (unsigned int i) +{ + int v; + + __BB(2): + if (i_2(D) < 2u) + goto __BB3; + else + goto __BB5; + + __BB(3): + v_3 = tbl[i_2(D)]; + if (v_3 > 5) + goto __BB4; + else + goto __BB5; + + __BB(4): + link_error (); + goto __BB5; + + __BB(5): + return; +} + +int +main (void) +{ + foo (0); + return 0; +} diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp-from-cst-agg-11.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp-from-cst-agg-11.c new file mode 100644 index 000000000000..425981f1f21c --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp-from-cst-agg-11.c @@ -0,0 +1,27 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fgimple -fdump-tree-evrp" } */ + +/* The index is [0, 2] so the range for v_3 should be [0, 0][5, 5]. */ + +static const int tbl[8] = { [2] = 5, [5] = 9 }; + +int __GIMPLE (ssa,startwith("evrp")) +foo (unsigned int i) +{ + int v; + + __BB(2): + if (i_2(D) > 2u) + goto __BB4; + else + goto __BB3; + + __BB(3): + v_3 = tbl[i_2(D)]; + return v_3; + + __BB(4): + return 0; +} + +/* { dg-final { scan-tree-dump "v_3 = .irange. int .0, 0..5, 5.\n" "evrp" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp-from-cst-agg-13.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp-from-cst-agg-13.c new file mode 100644 index 000000000000..2ead51b33ecb --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp-from-cst-agg-13.c @@ -0,0 +1,19 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fgimple -fdump-tree-evrp" } */ + +/* The index is unknown so the range for v_3 should be [0, 0][7, 7]. */ + +static const struct { int a; int b[4]; } tbl[2] + = { { 1, { [3] = 5 } }, { 2, { 6, 7, 8, 9 } } }; + +int __GIMPLE (ssa,startwith("evrp")) +foo (int i) +{ + int v; + + __BB(2): + v_3 = tbl[i_2(D)].b[1]; + return v_3; +} + +/* { dg-final { scan-tree-dump "v_3 = .irange. int .0, 0..7, 7.\n" "evrp" } } */
