> 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.
> 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.
--
Regards
Robin
