Evaluate SCEV on "typically expected value"

Hello,

We have some transformations based on SCEV and they usually end-up making heuristic decision based on SCEV comparison. While there are some situations where the comparison is trivial (subtract then look at the sign of the range), there are also a lot of situation where it is not (the range contains 0 strictly [aka. not on the boundary]). And we then take a “default” choice.

To improve the quality of our heuristic, I wanted to evaluate those SCEV on “typically expected” values that the programmer would provide, sparsely, on different scalars of a function.

I am not sure if the __builtin_expect was meant for this purpose. It is nicely SSA friendly (it returns a value on which we can “attach” the expectation) but maybe something akin to __builtin_assume is preferable?

Basically:

%b = i64 call @llvm.expect(i64 %a, i64 16)

%c = i64 call something(%b)
%d = i64 call something(%a)

Can be easily transformed into:

%b = i64 call @llvm.expect(i64 %a, i64 16)

%c = i64 call something_that_handle_16_great(%b)
%d = i64 call something(%a)

But it is harder to transform the second one too. The “expect” does not propagate up.

Could we have an ExpectationTracker that does something similar?
Should it be based on @llvm.expect or a different built-in?

Ideally we could provide an “expected” range for SCEV. Where the SCEV is not guaranteed to be, but is a good hint.

Hi,

As far as I understand, AssumptionTracker is just a compile-time
optimization to avoid having to iterate over instructions to find a
relevant @llvm.assume. In case of @llvm.expect, one can just look up
the definition, which would be the @llvm.expect. Some time ago there
was a patch that replaced AssumptionTracker but got reverted.

I see an issue with @llvm.expect's design. It should not be part of
the SSA which defines semantics instead of optional optimization
hints. With
%b = i64 call @llvm.expect(i64 %a, i64 16)
in the code, %a can still be used, has the same value, but has not the
same hint associated with it.

To specify a range, I could imagine a @llvm.expect.range intrinsic. Or
alternatively, and more general,
void @llvm.expect_true(i1 %cond)
that is also tracked by AssumptionTracker, but with the difference
that when %cond evaluates to false, it is still defined behaviour.

Michael

Hi,

Ah, yes, the AssumptionTracker is feature light. You can use the PostDomTree to find the assumption that unconditionally apply to the current instruction.
To generalize that we would need a solver (still waiting for Polyhedral Value Analysis by the way…) and accumulate the “divergence” on the post dominance frontier.
Do we have such thing?

Anyway, after looking into the use of the @llvm.expect intrinsic, I found out that we do propagate-up in some situation.

For example we “detect” which side of a phi is probably taken by looking at “expect” downstream of the phi and find if it would be incompatible with all the other branches.
We only propagate up through “copies” or “xor”.

Anyway, I agree a “void @llvm.expect_true(i1 %cond)” is more aligned with the @llvm.assume (but I am unsure if this is a good or a bad thing).

Semantically speaking, I see @llvm.expect_true as being a function that is instantaneous in average, but excruciatingly slow when its condition is false (thus making any other optimization irrelevant for the slow case).
As opposed to @llvm.assume which is instantaneous if true, but destroys the universe and all that exists when the condition is false.