On Fri, Jul 10, 2026 at 6:13 PM Robin Dapp <[email protected]> wrote:
>
> From: Robin Dapp <[email protected]>
>
> This patch adds a nowrap_bound field to data_reference which denotes the
> upper bound under which the DR is non wrapping.
>
> dr_analyze_innermost, create_data_ref, and find_data_references_in_stmt
> get an additional parameter to control whether or not a no-wrap bound
> should be recorded.
This looks OK, the only thing might be to mimic
number_of_iterations_exit_assumptions
vs. number_of_iterations_exit instead of adding a (defaulted)
parameter indicating
whether to allow assumptions. I think I prefer the extra parameter as
done here.
Thanks,
Richard.
> gcc/ChangeLog:
>
> * tree-data-ref.cc (dr_analyze_innermost): Add nowrap-bound param.
> (dr_analyze_indices): Likewise.
> (create_data_ref): Likewise.
> (find_data_references_in_stmt): Add allow_assumptions param.
> * tree-data-ref.h (struct data_reference): Add nowrap_bound.
> (DR_NOWRAP_BOUND): New.
> (dr_analyze_innermost): Pass on nowrap_bound.
> (find_data_references_in_stmt): Likewise.
> ---
> gcc/tree-data-ref.cc | 77 +++++++++++++++++++++++++++++++++-----------
> gcc/tree-data-ref.h | 13 ++++++--
> 2 files changed, 68 insertions(+), 22 deletions(-)
>
> diff --git a/gcc/tree-data-ref.cc b/gcc/tree-data-ref.cc
> index 1114903784e..2d6ddb14a23 100644
> --- a/gcc/tree-data-ref.cc
> +++ b/gcc/tree-data-ref.cc
> @@ -1129,11 +1129,15 @@ canonicalize_base_object_address (tree addr)
> dummy outermost loop. In other cases perform loop analysis.
>
> Return true if the analysis succeeded and store the results in DRB if so.
> - BB analysis can only fail for bitfield or reversed-storage accesses. */
> + BB analysis can only fail for bitfield or reversed-storage accesses.
> +
> + If NOWRAP_BOUND is nonzero, allow simple_iv to record no-wrap bounds.
> + Then, store non-trivial bounds in NOWRAP_BOUND. */
>
> opt_result
> dr_analyze_innermost (innermost_loop_behavior *drb, tree ref,
> - class loop *loop, const gimple *stmt)
> + class loop *loop, const gimple *stmt,
> + tree *nowrap_bound)
> {
> poly_int64 pbitsize, pbitpos;
> tree base, poffset;
> @@ -1195,9 +1199,11 @@ dr_analyze_innermost (innermost_loop_behavior *drb,
> tree ref,
> base = build_fold_addr_expr (base);
> }
>
> + bool allow_wrapping = (nowrap_bound != nullptr);
> +
> if (in_loop)
> {
> - if (!simple_iv (loop, loop, base, &base_iv, true))
> + if (!simple_iv (loop, loop, base, &base_iv, true, allow_wrapping))
> return opt_result::failure_at
> (stmt, "failed: evolution of base is not affine.\n");
> }
> @@ -1206,25 +1212,35 @@ dr_analyze_innermost (innermost_loop_behavior *drb,
> tree ref,
> base_iv.base = base;
> base_iv.step = ssize_int (0);
> base_iv.no_overflow = true;
> + base_iv.nowrap_bound = NULL_TREE;
> }
>
> if (!poffset)
> {
> offset_iv.base = ssize_int (0);
> offset_iv.step = ssize_int (0);
> + offset_iv.nowrap_bound = NULL_TREE;
> }
> else
> {
> if (!in_loop)
> - {
> - offset_iv.base = poffset;
> - offset_iv.step = ssize_int (0);
> - }
> - else if (!simple_iv (loop, loop, poffset, &offset_iv, true))
> + {
> + offset_iv.base = poffset;
> + offset_iv.step = ssize_int (0);
> + offset_iv.nowrap_bound = NULL_TREE;
> + }
> + else if (!simple_iv (loop, loop, poffset, &offset_iv, true,
> + allow_wrapping))
> return opt_result::failure_at
> (stmt, "failed: evolution of offset is not affine.\n");
> }
>
> + if (nowrap_bound)
> + {
> + *nowrap_bound = base_iv.nowrap_bound;
> + scev_add_nowrap_bound (nowrap_bound, offset_iv.nowrap_bound);
> + }
> +
> init = ssize_int (pbytepos);
>
> /* Subtract any constant component from the base and add it to INIT
> instead.
> @@ -1320,10 +1336,14 @@ base_supports_access_fn_components_p (tree base)
> }
>
> /* Determines the base object and the list of indices of memory reference
> - DR, analyzed in LOOP and instantiated before NEST. */
> + DR, analyzed in LOOP and instantiated before NEST.
> +
> + If NOWRAP_BOUND is nonzero, pass it to scev which will then store
> + the bound under which we do not wrap. */
>
> static void
> -dr_analyze_indices (struct indices *dri, tree ref, edge nest, loop_p loop)
> +dr_analyze_indices (struct indices *dri, tree ref, edge nest, loop_p loop,
> + tree *nowrap_bound = nullptr)
> {
> /* If analyzing a basic-block there are no indices to analyze
> and thus no access functions. */
> @@ -1358,7 +1378,7 @@ dr_analyze_indices (struct indices *dri, tree ref, edge
> nest, loop_p loop)
> if (TREE_CODE (ref) == ARRAY_REF)
> {
> tree op = TREE_OPERAND (ref, 1);
> - tree access_fn = analyze_scalar_evolution (loop, op);
> + tree access_fn = analyze_scalar_evolution (loop, op, nowrap_bound);
> access_fn = instantiate_scev (nest, loop, access_fn);
> access_fns.safe_push (access_fn);
> }
> @@ -1390,7 +1410,7 @@ dr_analyze_indices (struct indices *dri, tree ref, edge
> nest, loop_p loop)
> if (TREE_CODE (ref) == MEM_REF)
> {
> tree op = TREE_OPERAND (ref, 0);
> - tree access_fn = analyze_scalar_evolution (loop, op);
> + tree access_fn = analyze_scalar_evolution (loop, op, nowrap_bound);
> access_fn = instantiate_scev (nest, loop, access_fn);
> STRIP_NOPS (access_fn);
> if (TREE_CODE (access_fn) == POLYNOMIAL_CHREC)
> @@ -1496,11 +1516,16 @@ free_data_ref (data_reference_p dr)
>
> Return the data_reference description of MEMREF. NEST is the outermost
> loop in which the reference should be instantiated, LOOP is the loop
> - in which the data reference should be analyzed. */
> + in which the data reference should be analyzed.
> +
> + If ALLOW_ASSUMPTIONS is true, pass an empty no-wrap bound to scev and
> + have it store its assumptions there. If we got a nontrivial
> + assumption, save it in DR's DR_NOWRAP_BOUND. */
>
> struct data_reference *
> create_data_ref (edge nest, loop_p loop, tree memref, gimple *stmt,
> - bool is_read, bool is_conditional_in_stmt)
> + bool is_read, bool is_conditional_in_stmt,
> + bool allow_assumptions)
> {
> struct data_reference *dr;
>
> @@ -1517,11 +1542,16 @@ create_data_ref (edge nest, loop_p loop, tree memref,
> gimple *stmt,
> DR_IS_READ (dr) = is_read;
> DR_IS_CONDITIONAL_IN_STMT (dr) = is_conditional_in_stmt;
>
> + tree nowrap_bound = NULL_TREE;
> dr_analyze_innermost (&DR_INNERMOST (dr), memref,
> - nest != NULL ? loop : NULL, stmt);
> - dr_analyze_indices (&dr->indices, DR_REF (dr), nest, loop);
> + nest != NULL ? loop : NULL, stmt,
> + allow_assumptions ? &nowrap_bound : nullptr);
> + dr_analyze_indices (&dr->indices, DR_REF (dr), nest, loop,
> + allow_assumptions ? &nowrap_bound : nullptr);
> dr_analyze_alias (dr);
>
> + DR_NOWRAP_BOUND (dr) = nowrap_bound;
> +
> if (dump_file && (dump_flags & TDF_DETAILS))
> {
> unsigned i;
> @@ -1541,6 +1571,11 @@ create_data_ref (edge nest, loop_p loop, tree memref,
> gimple *stmt,
> fprintf (dump_file, "\n\tstep alignment: %d", DR_STEP_ALIGNMENT (dr));
> fprintf (dump_file, "\n\tbase_object: ");
> print_generic_expr (dump_file, DR_BASE_OBJECT (dr), TDF_SLIM);
> + if (DR_NOWRAP_BOUND (dr))
> + {
> + fprintf (dump_file, "\n\tnowrap bound: ");
> + print_generic_expr (dump_file, DR_NOWRAP_BOUND (dr), TDF_SLIM);
> + }
> fprintf (dump_file, "\n");
> for (i = 0; i < DR_NUM_DIMENSIONS (dr); i++)
> {
> @@ -6025,11 +6060,14 @@ loop_nest_has_data_refs (loop_p loop)
>
> /* Stores the data references in STMT to DATAREFS. If there is an
> unanalyzable
> reference, returns false, otherwise returns true. NEST is the outermost
> - loop of the loop nest in which the references should be analyzed. */
> + loop of the loop nest in which the references should be analyzed.
> + ALLOW_ASSUMPTIONS determines whether or not no-wrap assumptions
> + are allowed. */
>
> opt_result
> find_data_references_in_stmt (class loop *nest, gimple *stmt,
> - vec<data_reference_p> *datarefs)
> + vec<data_reference_p> *datarefs,
> + bool allow_assumptions)
> {
> auto_vec<data_ref_loc, 2> references;
> data_reference_p dr;
> @@ -6042,7 +6080,8 @@ find_data_references_in_stmt (class loop *nest, gimple
> *stmt,
> {
> dr = create_data_ref (nest ? loop_preheader_edge (nest) : NULL,
> loop_containing_stmt (stmt), ref.ref,
> - stmt, ref.is_read, ref.is_conditional_in_stmt);
> + stmt, ref.is_read, ref.is_conditional_in_stmt,
> + allow_assumptions);
> gcc_assert (dr != NULL);
> datarefs->safe_push (dr);
> }
> diff --git a/gcc/tree-data-ref.h b/gcc/tree-data-ref.h
> index e25f98d2966..deb264ded2e 100644
> --- a/gcc/tree-data-ref.h
> +++ b/gcc/tree-data-ref.h
> @@ -172,6 +172,10 @@ struct data_reference
> /* Behavior of the memory reference in the innermost loop. */
> struct innermost_loop_behavior innermost;
>
> + /* Upper bound for the number of loop iterations for which this DR's
> + IV does not wrap. */
> + tree nowrap_bound;
> +
> /* Subscripts of this data reference. */
> struct indices indices;
>
> @@ -201,6 +205,7 @@ struct data_reference
> #define DR_OFFSET_ALIGNMENT(DR) (DR)->innermost.offset_alignment
> #define DR_STEP_ALIGNMENT(DR) (DR)->innermost.step_alignment
> #define DR_INNERMOST(DR) (DR)->innermost
> +#define DR_NOWRAP_BOUND(DR) (DR)->nowrap_bound
>
> typedef struct data_reference *data_reference_p;
>
> @@ -520,7 +525,8 @@ typedef struct data_dependence_relation *ddr_p;
>
>
> opt_result dr_analyze_innermost (innermost_loop_behavior *, tree,
> - class loop *, const gimple *);
> + class loop *, const gimple *,
> + tree * = nullptr);
> extern bool compute_data_dependences_for_loop (class loop *, bool,
> vec<loop_p> *,
> vec<data_reference_p> *,
> @@ -543,13 +549,14 @@ extern void free_dependence_relations (vec<ddr_p>& );
> extern void free_data_ref (data_reference_p);
> extern void free_data_refs (vec<data_reference_p>& );
> extern opt_result find_data_references_in_stmt (class loop *, gimple *,
> - vec<data_reference_p> *);
> + vec<data_reference_p> *,
> + bool = false);
> extern bool graphite_find_data_references_in_stmt (edge, loop_p, gimple *,
> vec<data_reference_p> *);
> tree find_data_references_in_loop (class loop *, vec<data_reference_p> *);
> bool loop_nest_has_data_refs (loop_p loop);
> struct data_reference *create_data_ref (edge, loop_p, tree, gimple *, bool,
> - bool);
> + bool, bool = false);
> extern bool find_loop_nest (class loop *, vec<loop_p> *);
> extern struct data_dependence_relation *initialize_data_dependence_relation
> (struct data_reference *, struct data_reference *, vec<loop_p>);
> --
> 2.54.0
>
