[llvm-dev] Evaluate SCEV on "typically expected value"

[Alexandre Isoard via llvm-dev]

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>