Hi, this patch adds the ability to infer ranges from loads from global constant static aggregates which have static initializers. Even when the load has one or more ARRAY_REFs with an unknown index and thus we do not know the particular constant that is being loaded, we can traverse the correponding elements of the initializer and see if we know in what range(s) the loaed value must fall - or for pointers we can sometimes infer that the value cannot be NULL.
I thought this was similar to fold_using_range::range_of_address and so I decided to put my implementation alongside of it. The changes compared to v1 posted in https://inbox.sourceware.org/gcc-patches/[email protected]/T/#m974fa6138bb074a239fb2a300e1d60bc087913ad are: - The limiting parameter limits the number of constructor leaf "elements" that we traverse. - I have incorporated (hopefully) all suggestions from Richi, mainly assuming value zero if we do not encounter a corresponding part of a static initializer and using get_array_ctor_element_at_index to get at an element of an array with known constant index. I tried to emulate how it is used in fold_array_ctor_reference, I hope I got it right. - I have changed to code to only work for pranges and iranges for now. I will file a bug about extending it for frange and attach a patch to the code I'm now adding to handle frange. But as I mentioned in an earlier email, something else will need to change too to get it working as expected. - I have changed range_from_readonly_load to simply work true or false for pointers - where true means we can infer that it does not contain NULL and false means we cannot do anything. For integers, I have changed it to instantiate int_range<1> rather than value_range to add another constant. - I have introduced range_from_missing_constructor_part to handle the cases of missing bits in a constructor. - I have put the (now simplified) functionality of add_loaded_invariant_to_range at the beginning of range_from_readonly_load. That function remains recursive and walks the memory reference expression "backwards" for reasons explained in the previous email thread. - The case where we need to iterate over all elements of an array was optimized for pointers, we first check if all elements are present and do not iterate if not. For integers, we still need to iterate, of course. - I have added testcases to cover situations with two-dimensional arrays. Both when both indices are unknown and when only the second one is (in the C-sense). Bootstrapped and tested on x86_64-linux. I assume there will be more feedback but eventually I'd like to push this to master. Thanks, Martin gcc/ChangeLog: 2025-11-03 Martin Jambor <[email protected]> * gimple-range-fold.h (class fold_using_range): New member function range_from_readonly_var. * gimple-range-fold.cc (fold_using_range::fold_stmt): Call range_from_readonly_var on assignments. (range_from_missing_constructor_part): New function. (range_from_readonly_load): Likewise. (fold_using_range::range_from_readonly_var): Likewise. * params.opt (param_vrp_cstload_limit): New. * doc/invoke.texi (vrp-cstload-limit): Likewise. gcc/testsuite/ChangeLog: 2025-10-31 Martin Jambor <[email protected]> * gcc.dg/tree-ssa/vrp-from-cst-agg-1.c: New test. * gcc.dg/tree-ssa/vrp-from-cst-agg-2.c: Likewise. * gcc.dg/tree-ssa/vrp-from-cst-agg-3.c: Likewise. * gcc.dg/tree-ssa/vrp-from-cst-agg-4.c: Likewise. * gcc.dg/tree-ssa/vrp-from-cst-agg-5.c: Likewise. * gcc.dg/tree-ssa/vrp-from-cst-agg-6.c: Likewise. * gcc.dg/tree-ssa/vrp-from-cst-agg-7.c: Likewise. * gcc.dg/ipa/vrp-from-cst-agg-1.c: Likewise. --- gcc/doc/invoke.texi | 3 + gcc/gimple-range-fold.cc | 194 +++++++++++++++++- gcc/gimple-range-fold.h | 1 + gcc/params.opt | 4 + gcc/testsuite/gcc.dg/ipa/vrp-from-cst-agg-1.c | 33 +++ .../gcc.dg/tree-ssa/vrp-from-cst-agg-1.c | 32 +++ .../gcc.dg/tree-ssa/vrp-from-cst-agg-2.c | 57 +++++ .../gcc.dg/tree-ssa/vrp-from-cst-agg-3.c | 30 +++ .../gcc.dg/tree-ssa/vrp-from-cst-agg-4.c | 30 +++ .../gcc.dg/tree-ssa/vrp-from-cst-agg-5.c | 36 ++++ .../gcc.dg/tree-ssa/vrp-from-cst-agg-6.c | 42 ++++ .../gcc.dg/tree-ssa/vrp-from-cst-agg-7.c | 36 ++++ 12 files changed, 494 insertions(+), 4 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/ipa/vrp-from-cst-agg-1.c create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/vrp-from-cst-agg-1.c create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/vrp-from-cst-agg-2.c create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/vrp-from-cst-agg-3.c create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/vrp-from-cst-agg-4.c create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/vrp-from-cst-agg-5.c create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/vrp-from-cst-agg-6.c create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/vrp-from-cst-agg-7.c diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi index 32b9c48f155..dba20f473df 100644 --- a/gcc/doc/invoke.texi +++ b/gcc/doc/invoke.texi @@ -17632,6 +17632,9 @@ Increasing the cost multiplier will make vector loops more profitable. @item vrp-block-limit Maximum number of basic blocks before VRP switches to a lower memory algorithm. +@item vrp-cstload-limit +Maximum number of steps when inferring a value range from a load from a constant aggregate. + @item vrp-sparse-threshold Maximum number of basic blocks before VRP uses a sparse bitmap cache. diff --git a/gcc/gimple-range-fold.cc b/gcc/gimple-range-fold.cc index 06c645f3d08..c29460aea84 100644 --- a/gcc/gimple-range-fold.cc +++ b/gcc/gimple-range-fold.cc @@ -639,10 +639,14 @@ fold_using_range::fold_stmt (vrange &r, gimple *s, fur_source &src, tree name) if (!name) name = gimple_get_lhs (s); - // Process addresses. - if (gimple_code (s) == GIMPLE_ASSIGN - && gimple_assign_rhs_code (s) == ADDR_EXPR) - return range_of_address (as_a <prange> (r), s, src); + // Process addresses and loads from static constructors. + if (gimple_code (s) == GIMPLE_ASSIGN) + { + if (gimple_assign_rhs_code (s) == ADDR_EXPR) + return range_of_address (as_a <prange> (r), s, src); + if (range_from_readonly_var (r, s)) + return true; + } gimple_range_op_handler handler (s); if (handler) @@ -891,6 +895,188 @@ fold_using_range::range_of_address (prange &r, gimple *stmt, fur_source &src) return true; } +/* If TYPE is a pointer, return false. Otherwise, add zero of TYPE (which must + be an integer) to R and return true. */ + +static bool +range_from_missing_constructor_part (vrange &r, tree type) +{ + if (POINTER_TYPE_P (type)) + return false; + gcc_checking_assert (irange::supports_p (type)); + wide_int zero = wi::zero (TYPE_PRECISION (type)); + r.union_ (int_range<1> (type, zero, zero)); + return true; +} + +// One step of fold_using_range::range_from_readonly_var. Process expressions +// in COMPS which together load a value of TYPE, from index I to 0 according to +// the corresponding static initializer in CST which should be either a scalar +// invariant or a constructor. Currently TYPE must be either a pointer or an +// integer. If TYPE is a pointer, return true if all potentially loaded values +// are known not to be zero and false if any of them can be zero. Otherwise +// return true if it is possible to add all constants which can be loaded from +// CST (which must be storable to TYPE) to R and do so. In any case, decrement +// *BUDGET when inspecting a scalar constant and return false (and fail) if it +// is already zero. +// TODO: Add support for franges. + +static bool +range_from_readonly_load (vrange &r, tree type, tree cst, + const vec <tree> &comps, unsigned i, + int *budget) +{ + if (i == 0) + { + if (!*budget) + return false; + (*budget)--; + + if (!is_gimple_ip_invariant (cst) + || !useless_type_conversion_p (type, TREE_TYPE (cst))) + return false; + + if (POINTER_TYPE_P (type)) + { + bool strict_overflow_p; + return tree_single_nonzero_warnv_p (cst, &strict_overflow_p); + } + gcc_checking_assert (irange::supports_p (type)); + wide_int wi_cst = wi::to_wide (cst); + r.union_ (int_range<1> (type, wi_cst, wi_cst)); + return true; + } + /* TODO: Perhaps handle RAW_DATA_CST too. */ + if (TREE_CODE (cst) != CONSTRUCTOR) + return false; + + i--; + tree expr = comps[i]; + unsigned ix; + tree index, val; + + if (TREE_CODE (expr) == COMPONENT_REF) + { + tree ref_fld = TREE_OPERAND (expr, 1); + FOR_EACH_CONSTRUCTOR_ELT (CONSTRUCTOR_ELTS (cst), ix, index, val) + { + if (index != ref_fld) + continue; + return range_from_readonly_load (r, type, val, comps, i, budget); + } + if (TREE_CODE (TREE_TYPE (cst)) == RECORD_TYPE) + return range_from_missing_constructor_part (r, type); + else + /* Missing constructor of a union field just isn't like other missing + constructor parts. x*/ + return false; + } + + gcc_assert (TREE_CODE (expr) == ARRAY_REF); + tree op1 = TREE_OPERAND (expr, 1); + + if (TREE_CODE (op1) == INTEGER_CST) + { + unsigned ctor_idx; + val = get_array_ctor_element_at_index (cst, wi::to_offset (op1), + &ctor_idx); + if (!val) + { + if (ctor_idx < CONSTRUCTOR_NELTS (cst)) + return false; + return range_from_missing_constructor_part (r, type); + } + return range_from_readonly_load (r, type, val, comps, i, budget); + } + + tree arr_type = TREE_TYPE (cst); + tree domain = TYPE_DOMAIN (arr_type); + if (!TYPE_MIN_VALUE (domain) + || !TYPE_MAX_VALUE (domain) + || !tree_fits_uhwi_p (TYPE_MIN_VALUE (domain)) + || !tree_fits_uhwi_p (TYPE_MAX_VALUE (domain))) + return false; + unsigned HOST_WIDE_INT needed_count + = (tree_to_uhwi (TYPE_MAX_VALUE (domain)) + - tree_to_uhwi (TYPE_MIN_VALUE (domain)) + 1); + if (CONSTRUCTOR_NELTS (cst) < needed_count) + { + if (!range_from_missing_constructor_part (r, type)) + return false; + } + + FOR_EACH_CONSTRUCTOR_ELT (CONSTRUCTOR_ELTS (cst), ix, index, val) + { + /* 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 (!range_from_readonly_load (r, type, val, comps, i, budget)) + return false; + } + + return true; +} + +// Attempt to calculate the range of value loaded by STMT (which must be an +// assignment) if it is a load from a read-only aggregate variable. If +// successful, return true and set the discovered range in R. Otherwise return +// false and leave R untouched. + +bool +fold_using_range::range_from_readonly_var (vrange &r, gimple *stmt) +{ + gcc_checking_assert (gimple_code (stmt) == GIMPLE_ASSIGN); + tree type = TREE_TYPE (gimple_assign_lhs (stmt)); + /* TODO: Add support for frange. */ + if (!irange::supports_p (type) + && !prange::supports_p (type)) + return false; + + int budget = param_vrp_cstload_limit; + if (!budget) + return false; + + tree t = gimple_assign_rhs1 (stmt); + unsigned count = 0; + while (TREE_CODE (t) == ARRAY_REF + || TREE_CODE (t) == COMPONENT_REF) + { + count++; + t = TREE_OPERAND (t, 0); + } + if (!count + || !VAR_P (t) + || !is_global_var (t) + || !TREE_READONLY (t) + || !DECL_INITIAL (t) + || TREE_CODE (DECL_INITIAL (t)) != CONSTRUCTOR) + return false; + + t = gimple_assign_rhs1 (stmt); + auto_vec <tree, 4> comps; + comps.safe_grow (count, true); + int i = 0; + while (TREE_CODE (t) == ARRAY_REF + || TREE_CODE (t) == COMPONENT_REF) + { + comps[i] = t; + t = TREE_OPERAND (t, 0); + i++; + } + + value_range tmp (type); + bool res = range_from_readonly_load (tmp, type, DECL_INITIAL (t), comps, + count, &budget); + if (res) + { + if (POINTER_TYPE_P (type)) + r.set_nonzero (type); + else + r = tmp; + } + return res; +} + // Calculate a range for phi statement S and return it in R. // If a range cannot be calculated, return false. diff --git a/gcc/gimple-range-fold.h b/gcc/gimple-range-fold.h index 826a10fd9e8..bc5c6686a65 100644 --- a/gcc/gimple-range-fold.h +++ b/gcc/gimple-range-fold.h @@ -180,6 +180,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_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/params.opt b/gcc/params.opt index f8884e976e7..beaa61c48ab 100644 --- a/gcc/params.opt +++ b/gcc/params.opt @@ -1273,6 +1273,10 @@ The scaling multiplier as a percentage to apply to all scalar loop costing when Common Joined UInteger Var(param_vrp_block_limit) Init(150000) Optimization Param Maximum number of basic blocks before VRP switches to a fast model with less memory requirements. +-param=vrp-cstload-limit= +Common Joined UInteger Var(param_vrp_cstload_limit) Init(32) IntegerRange(0, 255) Optimization Param +Maximum number of steps when inferring a value range from a load from a constant aggregate. + -param=vrp-sparse-threshold= Common Joined UInteger Var(param_vrp_sparse_threshold) Init(3000) Optimization Param Maximum number of basic blocks before VRP uses a sparse bitmap cache. diff --git a/gcc/testsuite/gcc.dg/ipa/vrp-from-cst-agg-1.c b/gcc/testsuite/gcc.dg/ipa/vrp-from-cst-agg-1.c new file mode 100644 index 00000000000..cd71d329487 --- /dev/null +++ b/gcc/testsuite/gcc.dg/ipa/vrp-from-cst-agg-1.c @@ -0,0 +1,33 @@ +/* { dg-do compile } */ +/* { dg-options "-O3 -fdump-ipa-cp-details" } */ + +static const struct { + int w; + int h; +} sizes[7] = { + { 16, 16 }, + { 16, 8 }, + { 8, 16 }, + { 8, 8 }, + { 8, 4 }, + { 4, 8 }, + { 4, 4 } +}; + +int baz(int, int); + +[[gnu::noinline]] void bar(int w, int h) +{ + for (int i = 0; i < w; i++) + for (int j = 0; i < h; j++) + baz (i, j); +} + +void foo (int index) +{ + int w = sizes[index].w; + int h = sizes[index].h; + + bar (w, h); +} +/* { dg-final { scan-ipa-dump-times "irange" 2 "cp" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp-from-cst-agg-1.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp-from-cst-agg-1.c new file mode 100644 index 00000000000..6612a88f029 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp-from-cst-agg-1.c @@ -0,0 +1,32 @@ +/* { dg-do link } */ +/* { dg-options "-O2" } */ + +int ga = 1; +int gb = 2; +int gc = 3; +volatile int gi; + +static const int *vars[3] = {&ga, &gb, &gc}; + +void link_error (void); + +[[gnu::noinline]] void foo (int index) +{ + const int *p = vars[index]; + if (!p) + link_error (); + else + gi = *p; +} + +[[gnu::noipa]] int +get_index (void) +{ + return 1; +} + +int main (int argc, char **argv) +{ + foo (get_index ()); + return 0; +} diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp-from-cst-agg-2.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp-from-cst-agg-2.c new file mode 100644 index 00000000000..0f7677d90b8 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp-from-cst-agg-2.c @@ -0,0 +1,57 @@ +/* { dg-do run } */ +/* { dg-options "-O2" } */ + +enum comp_cat_tag +{ + cc_partial_ordering, + cc_weak_ordering, + cc_strong_ordering, + cc_last +}; + +struct comp_cat_info_t +{ + const char *name; + const char *members[4]; +}; + +static const struct comp_cat_info_t comp_cat_info[cc_last] += { + { "partial_ordering", { "equivalent", "greater", "less", "unordered" } }, + { "weak_ordering", { "equivalent", "greater", "less" } }, + { "strong_ordering", { "equal", "greater", "less" } } +}; + +volatile const char *gp; + +[[gnu::noipa]] static void +check (const char *p) +{ + if (!p) + __builtin_abort (); + gp = p; +} + +[[gnu::noinline]] int foo (enum comp_cat_tag tag) +{ + for (int i = 0; i < 4; ++i) + { + const char *p = comp_cat_info[tag].members[i]; + if (!p) + continue;; + check (p); + } + return 0; +} + +[[gnu::noipa]] enum comp_cat_tag +get_index (void) +{ + return cc_strong_ordering; +} + +int main (int argc, char **argv) +{ + foo (get_index ()); + return 0; +} diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp-from-cst-agg-3.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp-from-cst-agg-3.c new file mode 100644 index 00000000000..d45928e0a25 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp-from-cst-agg-3.c @@ -0,0 +1,30 @@ +/* { dg-do link } */ +/* { dg-options "-O2" } */ + +volatile int gi; + +static const int values[3] = {5, 7, 11}; + +void link_error (void); + +[[gnu::noinline]] void foo (int index) +{ + const int v = values[index]; + if (v <= 2 + || v > 666) + link_error (); + else + gi = v; +} + +[[gnu::noipa]] int +get_index (void) +{ + return 1; +} + +int main (int argc, char **argv) +{ + foo (get_index ()); + return 0; +} diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp-from-cst-agg-4.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp-from-cst-agg-4.c new file mode 100644 index 00000000000..f0fc8c1f1df --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp-from-cst-agg-4.c @@ -0,0 +1,30 @@ +/* { dg-do link } */ +/* { dg-options "-O2" } */ + +volatile int gi; + +static const int values[25] = {5, 7, 11}; + +void link_error (void); + +[[gnu::noinline]] void foo (int index) +{ + const int v = values[index]; + if (v <= -2 + || v > 666) + link_error (); + else + gi = v; +} + +[[gnu::noipa]] int +get_index (void) +{ + return 1; +} + +int main (int argc, char **argv) +{ + foo (get_index ()); + return 0; +} diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp-from-cst-agg-5.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp-from-cst-agg-5.c new file mode 100644 index 00000000000..f14e1ee9892 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp-from-cst-agg-5.c @@ -0,0 +1,36 @@ +/* { dg-do link } */ +/* { dg-options "-O2" } */ + +volatile int gi; + +static const struct { + int a; + int b; +} values[2][2] = { + { {1000, 1 }, {1001, 2} }, + { {1003, 1 }, {1004, 2} } +}; + +void link_error (void); + +[[gnu::noinline]] void foo (int i, int j) +{ + const int v = values[i][j].b; + if (v <= 0 + || v > 666) + link_error (); + else + gi = v; +} + +[[gnu::noipa]] int +get_index (void) +{ + return 1; +} + +int main (int argc, char **argv) +{ + foo (get_index (), get_index ()); + return 0; +} diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp-from-cst-agg-6.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp-from-cst-agg-6.c new file mode 100644 index 00000000000..0dd6a841f79 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp-from-cst-agg-6.c @@ -0,0 +1,42 @@ +/* { dg-do run } */ +/* { dg-options "-O2" } */ + +volatile int gi; + +static const struct { + int a; + int b; +} values[2][2] = { + { {0, 1 }, {0, 2} }, + { {0, 1 }, {0, 2} } +}; + +[[gnu::noipa]] static void +check (int v) +{ + if (!v) + __builtin_abort (); + gi = v; +} + + +[[gnu::noinline]] void foo (int i, int j) +{ + const int v = values[i][j].a; + if (v <= 0 + || v > 666) + return; + check (v); +} + +[[gnu::noipa]] int +get_index (void) +{ + return 1; +} + +int main (int argc, char **argv) +{ + foo (get_index (), get_index ()); + return 0; +} diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp-from-cst-agg-7.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp-from-cst-agg-7.c new file mode 100644 index 00000000000..a062aa958b2 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp-from-cst-agg-7.c @@ -0,0 +1,36 @@ +/* { dg-do link } */ +/* { dg-options "-O2" } */ + +volatile int gi; + +static const struct { + int a; + int b; +} values[2][2] = { + { {1000, 1 }, {1001, 2} }, + { {1003, 1 }, {1004, 2} } +}; + +void link_error (void); + +[[gnu::noinline]] void foo (int i) +{ + const int v = values[0][i].b; + if (v <= 0 + || v > 666) + link_error (); + else + gi = v; +} + +[[gnu::noipa]] int +get_index (void) +{ + return 1; +} + +int main (int argc, char **argv) +{ + foo (get_index ()); + return 0; +} -- 2.51.1
