[llvm-dev] Early CSE clobbering llvm.assume

Fri Jun 10 16:57:11 PDT 2016

https://llvm.org/bugs/show_bug.cgi?id=28086

Thank you so much for the helpful responses. Is the new GVN algorithm
available in trunk? If so I couldn't find it, and I'm curious to try the
NewGVN-before-GVN workaround.

On Fri, Jun 10, 2016 at 5:34 PM, Daniel Berlin <dberlin at dberlin.org> wrote:

> :(
> This, at least, is something newgvn fixes.
>
> Loads, stores, scalars, insertvalues, etc, are all just expression types.
> They all go into the value table.  any required memory state, etc, that
> goes along with it is just a thing that is part of that expression.
>
> But even that won't help in this case. It will only notice that
>
>
> In any case, for now, you should file a bug pointing out this use of
> assume can't be used to optimize, and assign/cc me.
> It'll be a while, and it'll like get reassigned, but it's good for us to
> not lose track of this.
>
> (Of course, if you have time to help with the more complex problems here,
> happy to try to set you on the right path :P)
>
>
> FWIW: Newgvn comes up with:
>
> define i32 @foo(i32*) {
> entry:
>   %1 = load i32, i32* %0
>   %2 = icmp eq i32 %1, 3
>   call void @llvm.assume(i1 %2)
>   ret i32 %1
> }
>
> It has no assume handling, it's still a todo.
>
> Humorously, gvn will already turn the above into
>
> define i32 @foo(i32*) {
> entry:
>   ret i32 3
> }
>
>
>
> On Fri, Jun 10, 2016 at 4:09 PM, Josh Klontz <josh.klontz at gmail.com>
> wrote:
>
>> Turns out the lookup isn't good enough, the SimpleValue key type for
>> the AvailableValues map doesn't support LoadInst.
>>
>> On Fri, Jun 10, 2016 at 4:59 PM, Daniel Berlin <dberlin at dberlin.org>
>> wrote:
>>
>>> Maybe.  It may not fix it directly because you never use %1 or %2 again.
>>>   I haven't looked to see how good the lookup is.
>>>
>>> On Fri, Jun 10, 2016, 3:45 PM Josh Klontz <josh.klontz at gmail.com> wrote:
>>>
>>>> Thanks Daniel, with that knowledge I think I can at least work around
>>>> the issue in my frontend.
>>>>
>>>> Ignoring GVN for a second though, and just looking at Early CSE, it
>>>> seems to me that at least in this pass that there is the potential for an
>>>> easy fix. Here the issue appears to be that we hit
>>>>
>>>>   if (Value *V = SimplifyInstruction(Inst, DL, &TLI, &DT, &AC))
>>>>
>>>> immediately replacing %1 with 3 before we even reach %3. If we were to
>>>> record this replacement in EarlyCSE::AvailableValues, wouldn't that address
>>>> the issue? I'll try this out and see.
>>>>
>>>> v/r,
>>>> Josh
>>>>
>>>> On Fri, Jun 10, 2016 at 4:23 PM, Daniel Berlin <dberlin at dberlin.org>
>>>> wrote:
>>>>
>>>>> Yeah, that change is completely unrelated, that is about correctness,
>>>>> this is about optimization.
>>>>> I'm working on a proposal to just fix assume at some point to deal
>>>>> with the former issue.
>>>>>
>>>>> The problem with this testcase is that all the ways assume is
>>>>> propagate expect the variable in the assume to later be used.
>>>>>
>>>>>
>>>>> <This is the main way assume constants are propagated>
>>>>> bool GVN::processAssumeIntrinsic(IntrinsicInst *Inst) {
>>>>> ...
>>>>>
>>>>>    // We can replace assume value with true, which covers cases like
>>>>> this:
>>>>>    // call void @llvm.assume(i1 %cmp)
>>>>>    // br i1 %cmp, label %bb1, label %bb2 ; will change %cmp to true
>>>>>    ReplaceWithConstMap[V] = True;
>>>>> ...
>>>>> }
>>>>>
>>>>> ...
>>>>> bool GVN::processBlock(BasicBlock *BB) {
>>>>> ...
>>>>>    // Clearing map before every BB because it can be used only for
>>>>> single BB.
>>>>>    ReplaceWithConstMap.clear();
>>>>> ....
>>>>>
>>>>> }
>>>>>
>>>>>
>>>>> So it's going to go through the rest of the bb, see nothing with %2,
>>>>> do nothing, and then next iteration, clear the constant map.  It's not
>>>>> valid to avoid clearing the constant map, and in fact,  what is happening
>>>>> here is a pretty complicated to help with.
>>>>> There is no easy way to see that the load  at %3 is affected at all by
>>>>> the assume.
>>>>>
>>>>> It's possible to make this work using the predication/value inference
>>>>> algorithms in the paper newgvn is based on, but it's not even implemented
>>>>> there.
>>>>>
>>>>> Short answer, without special casing this in magic ways, i wouldn't
>>>>> expect this to get fixed anytime soon.
>>>>>
>>>>> If we fixed assume in one of the ways i thought about, like bodik's
>>>>> extended ssa:
>>>>>
>>>>> http://homepages.dcc.ufmg.br/~fernando/classes/dcc888/ementa/slides/RangeAnalysis.pdf
>>>>>
>>>>> You would at least see that the load result is used by an assume, and
>>>>> could go look at that assume and so something with it.  Currently, it's a
>>>>> few steps away.
>>>>>
>>>>> In the current scheme, assumes just float in air, and so it can be
>>>>> hard to see what their effects touch
>>>>> :)
>>>>>
>>>>>
>>>>> On Fri, Jun 10, 2016 at 2:00 PM, Josh Klontz via llvm-dev <
>>>>> llvm-dev at lists.llvm.org> wrote:
>>>>>
>>>>>> Thanks for the lead Kevin. Unfortunately when I updated to ToT the
>>>>>> problem persists. Will put together a minimum reproducing example.
>>>>>>
>>>>>> On Fri, Jun 10, 2016 at 12:26 PM, Smith, Kevin B <
>>>>>> kevin.b.smith at intel.com> wrote:
>>>>>>
>>>>>>> You might look at this commit to fix the problem: r270823
>>>>>>> "MemorySSA: Revert r269678 and r268068; replace with special casing
>>>>>>> in MemorySSA."
>>>>>>>
>>>>>>> I think that might fix the issue for you.
>>>>>>>
>>>>>>> Kevin Smith
>>>>>>>
>>>>>>>
>>>>>>
>>>>>> _______________________________________________
>>>>>> LLVM Developers mailing list
>>>>>> llvm-dev at lists.llvm.org
>>>>>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>>>>>
>>>>>>
>>>>>
>>>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160610/ac80a47a/attachment.html>