Daniel Berlin via llvm-dev
2016-Jun-10 22:59 UTC
[llvm-dev] Early CSE clobbering llvm.assume
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/360457b3/attachment.html>
Daniel Berlin via llvm-dev
2016-Jun-10 23:06 UTC
[llvm-dev] Early CSE clobbering llvm.assume
(and you pointed out one of the other problems with current assume, which is that by not attaching the equality to the assume, and saying nothing should touch it, they can get messed up indiscriminately by random things. So we often can lose valuable info for no good reason) On Fri, Jun 10, 2016, 3: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/26fd39ae/attachment.html>
Josh Klontz via llvm-dev
2016-Jun-10 23:09 UTC
[llvm-dev] Early CSE clobbering llvm.assume
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/9ec3a172/attachment.html>
Daniel Berlin via llvm-dev
2016-Jun-10 23:34 UTC
[llvm-dev] Early CSE clobbering llvm.assume
:(
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/72e9e94a/attachment.html>