llvm dev - Mar 2018 - 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.

-- 
*Alexandre Isoard*
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20180328/18235895/attachment.html>

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.

On Wed, Mar 28, 2018 at 12:22 PM, Michael Kruse <llvmdev at meinersbur.de>
wrote:
> 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
>


-- 
*Alexandre Isoard*
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20180328/ec0ddc00/attachment.html>