On Mon, Jul 20, 2026 at 10:17 PM Robin Dapp <[email protected]> wrote:
>
> > But we are incrementally building up a CHREC and cache results,
> > consider
> >
> > # _1 = PHI <_2(entry), _3(latch)>
> > _3 = _1 + 1;
> > _4 = _3 * 6;
> > if (...)
> > goto loop;
> >
> > when we analyze _4 we recursively analyze _3 and then _1 which is
> > finally a loop PHI that will trigger the SCEV-DFS analysis (there we can't
> > do much). That result then, {_2, +, 1 } gets 1 added and the multiplied by
> > 6.
> > Now consider the multiplication being done as unsigned, first
> > converting _3 to unsigned. That's where we'd need to create a runtime
> > check to avoid ((unsigned){_2 + 1, +, 1 }) * 6 but instead get
> > (unsigned){(_2 + 1)*6, +, 6}. You register a runtime check (with the global
> > SCEV state?). If you'd then analyze a _5 = _4 + 30 the (unsigned){(_2
> > + 1)*6, +, 6}
> > CHREC is cached, so implicitly not overflowing. What do you do with the +
> > 30?
>
> Hmm, your example is mostly similar to vect-unsigned-assump-3.c (added
> in the vectorizer patch):
>
> I adjusted it slightly.
>
> int f (const uint8_t *cur, uint32_t n, uint32_t start)
> {
> uint32_t i = start;
> while (++i != n)
> {
> uint32_t k = i * 6;
> if (cur[k] != cur[k + 30])
> break;
> }
> return i;
> }
>
> We have:
>
> (set_scalar_evolution
> instantiated_below = 2
> (scalar = i_10)
> (scalar_evolution = {start_9(D) + 1, +, 1}_1)))
>
> (set_scalar_evolution
> instantiated_below = 2
> (scalar = k_12)
> (scalar_evolution = {(start_9(D) + 1) * 6, +, 6}_1))
>
> As you said, these two are fine, and we cache them with the "allow
> assumption" bit turned on but with _no_ actual assumption (as there was
> none needed so far).
>
> (set_scalar_evolution
> instantiated_below = 2
> (scalar = _1)
> (scalar_evolution = {(sizetype) ((start_9(D) + 1) * 6), +, 6}_1)))
>
> Now the last step goes through convert_affine_scev (?).
> scev_probably_wraps -> get_niter_type_bounds gives us
>
> nowrap bound: ~((start_9(D) + 1) * 6) / 6
>
> which we store in the current nowrap_bound passed by
> analyze_scalar_evolution_1 (as well as in the cache).
> A caller that doesn't want assumptions queried passes a nullptr
> nowrap_bound and wouldn't see this entry.
>
> An assumptions caller would see it, including the stored nowrap bound.
>
> (I just realized I used nowrap_bound != nullptr as cache query and not
> *nowrap_bound != NULL_TREE. Perhaps this can be improved but is no
> correctness issue in itself, just wastes cache slots.)
>
> > Given the global runtime check, you'd require a scev_reset before each
> > query?
> > How do you make sure all cached results have their runtime check registered
> > and not "lost"?
>
> The motivation for the cache "bit" was to _not_ need a reset before each
> query. So scev_probably_wraps on a scev/chrec path returns the bound
> for its current base and step (+type of course). Then we cache it
> with the assumption bit set and store the current assumption alongside.
>
> When we hit more assumptions along the way, the "more global" (up the
> tree) assumption consists of MIN'ed individual ones. Only then we
> (should) store the more restrictive assumption. The chrecs further down
> the tree only have the local assumption needed at that point.
>
> Maybe a better way to describe it is that the topmost/final assumption
> is built when walking back up the chrec tree, merging child assumptions
> at parent nodes.
Ah, OK. Thanks for the detailed explanation. There's probably
optimization opportunities on the MIN_EXPR chain as folding will
generally not consider re-association here, so something like
tree-affine might help here. This can be dealt with as a followup I think
if it turns out necessary. Some costing on the vectorizer versioning
condition is necessary of course.
> > I'm worried about wrong-code, not so much about missed optimizations
> > right now.
> >
> > So you say for my example above, when seeing (unsigned){(_2 + 1)*6, +, 6} +
> > 30
> > the nowrap condition computation does not assume that {(_2 + 1)*6, +,
> > 6 } does not
> > wrap? I guess I have to look at this more closely.
>
> I think I phrased it wrong. What I meant to say is that it works
> correctly, to my understanding at least, and the only thing I see is a
> missed optimization. There might still be functions I forgot to pass a
> nowrap_bound to but the strategy above should still work unless I'm
> missing something major.
OK, I'll give the rest of the patches a look.
Richard.
>
> --
> Regards
> Robin
>
