[llvm-dev] Path condition propagation
Carlos Liam via llvm-dev
llvm-dev at lists.llvm.org
Wed Jul 6 17:24:45 PDT 2016
I've submitted a working patch for review: http://reviews.llvm.org/D22076 <http://reviews.llvm.org/D22076>
- CL
> On Jul 6, 2016, at 3:09 PM, Carlos Liam via llvm-dev <llvm-dev at lists.llvm.org> wrote:
>
> I have this patch to GVN.cpp, but it doesn't seem to be working; any ideas?
>
> diff --git a/lib/Transforms/Scalar/GVN.cpp b/lib/Transforms/Scalar/GVN.cpp
> index a963b2f..97d7b4b 100644
> --- a/lib/Transforms/Scalar/GVN.cpp
> +++ b/lib/Transforms/Scalar/GVN.cpp
> @@ -2036,6 +2036,22 @@ bool GVN::propagateEquality(Value *LHS, Value *RHS, const BasicBlockEdge &Root,
> if (RootDominatesEnd)
> addToLeaderTable(Num, NotVal, Root.getEnd());
>
> + // If "A > B" or "A < B", then propagate "(A == B) == false".
> + if (ICmpInst *ICmp = dyn_cast<ICmpInst>(Cmp)) {
> + if (ICmp->isRelational() &&
> + ((isKnownTrue && Cmp->isFalseWhenEqual()) ||
> + (isKnownFalse && Cmp->isTrueWhenEqual()))) {
> + Worklist.push_back(
> + std::make_pair(CmpInst::Create(
> + Cmp->getOpcode(),
> + CmpInst::Predicate::ICMP_EQ,
> + A,
> + B
> + ), ConstantInt::getFalse(Cmp->getContext()))
> + );
> + }
> + }
> +
> continue;
> }
> }
>
>
> - CL
>
>> On Jul 3, 2016, at 8:40 PM, Daniel Berlin <dberlin at dberlin.org <mailto:dberlin at dberlin.org>> wrote:
>>
>> Sure
>>
>> On Mon, Jul 4, 2016, 9:40 AM Carlos Liam <carlos at aarzee.me <mailto:carlos at aarzee.me>> wrote:
>> It looks like there's already something similar in PropagateEquality which eg X >= Y == true and replaces X < Y == false, which is somewhat similar - could I base an addition off of that?
>>
>>
>> - CL
>>
>> On Jul 3, 2016, at 7:13 PM, Daniel Berlin <dberlin at dberlin.org <mailto:dberlin at dberlin.org>> wrote:
>>
>>> It's going to be really hard to do something sane in the current infrastructure.
>>> Its possible, but it would also be slow. You would have to go looking at uses of variables compared in predicates in PropagateEquality and if the uses appear in a comparison that is dominated by the true or false edge of the existing predicate, see if it tells you something about the dominated one.
>>>
>>>
>>> On Mon, Jul 4, 2016, 8:23 AM Carlos Liam <carlos at aarzee.me <mailto:carlos at aarzee.me>> wrote:
>>> That seems ominous; should I not bother?
>>>
>>> - CL
>>>
>>> On Jul 3, 2016, at 5:58 PM, Daniel Berlin <dberlin at dberlin.org <mailto:dberlin at dberlin.org>> wrote:
>>>
>>>> PropagateEquality in gvn.cpp
>>>>
>>>> However, if you are going to do it, remember the goal is to make the code simpler and easier, not just pile on to the current mess to catch more cases :)
>>>>
>>>> On Mon, Jul 4, 2016, 7:51 AM Carlos Liam <carlos at aarzee.me <mailto:carlos at aarzee.me>> wrote:
>>>> Where would I look to change the equality propagation?
>>>>
>>>>
>>>> - CL
>>>>
>>>> On Jun 30, 2016, at 11:45 PM, Daniel Berlin <dberlin at dberlin.org <mailto:dberlin at dberlin.org>> wrote:
>>>>
>>>>> The current gvn equality propagation is not powerful enough to get this because it doesn't try to infer values in predicates based on other predicates, so it never realizes a>b -> a !=b in a useful way.
>>>>>
>>>>> It otherwise would get this
>>>>>
>>>>> On Thu, Jun 30, 2016, 7:41 PM Sean Silva <chisophugis at gmail.com <mailto:chisophugis at gmail.com>> wrote:
>>>>> On Thu, Jun 30, 2016 at 6:45 PM, Daniel Berlin via llvm-dev <llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>> wrote:
>>>>>
>>>>>
>>>>> On Thu, Jun 30, 2016 at 6:09 PM, Carlos Liam via llvm-dev <llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>> wrote:
>>>>> Hi all,
>>>>>
>>>>> Consider this C code:
>>>>>
>>>>> #include <stdbool.h>
>>>>>
>>>>> bool func(int n1, int n2, bool b) {
>>>>> bool greater = n1 > n2;
>>>>> if (greater && b) {
>>>>> if (n1 == n2) {
>>>>> return false; // unreachable
>>>>> }
>>>>> }
>>>>> return true;
>>>>> }
>>>>>
>>>>> The line marked unreachable cannot be reached, however currently LLVM does not optimize it out
>>>>> ?????
>>>>> Yes it does.
>>>>>
>>>>> It seems like we get this almost by accident though. I find that I need `-mem2reg -instcombine -simplifycfg -instcombine` (on clang -O0 IR; the `-mem2reg -instcombine` are just cleanup) and essentially it boils down to simplifycfg merging everything into a single branch-free expression and then instcombine algebraically merging the comparisons.
>>>>>
>>>>> A small modification defeats LLVM's optimizer:
>>>>>
>>>>> bool func(int n1, int n2, bool b) {
>>>>> bool greater = n1 > n2;
>>>>> if (greater && b) {
>>>>> foo();
>>>>>
>>>>> if (n1 == n2) {
>>>>> return false; // unreachable
>>>>> }
>>>>> }
>>>>> return true;
>>>>> }
>>>>>
>>>>> In this case, simplifycfg doesn't go wild merging everything into a single branch-free expression and so we don't get it.
>>>>>
>>>>>
>>>>> CorrelatedValuePropagation doesn't get this because its processCmp is quite weak (it bails out if one operand isn't a constant). JumpThreading is the only other pass that uses LazyValueInfo and it can't fold this since it can't thread a jump around the side-effecting `foo()` call.
>>>>>
>>>>> I'm not familiar with GVN but it doesn't seem to help for this modified test case either.
>>>>>
>>>>> Carlos, in answer to your original question, you may want to see if you can make LLVM get this case by modifying processCmp in lib/Transforms/Scalar/CorrelatedValuePropagation.cpp
>>>>>
>>>>> -- Sean Silva
>>>>>
>>>>> [dannyb at dannyb-macbookpro3 18:39:18] ~/sources/llvm (git-svn)-[newgvn-predicates]- :( $ clang -c -emit-llvm ~/greater.c -O1
>>>>> [dannyb at dannyb-macbookpro3 18:39:22] ~/sources/llvm (git-svn)-[newgvn-predicates]- :) $ debug-build/bin/llvm-dis greater.bc
>>>>> [dannyb at dannyb-macbookpro3 18:39:24] ~/sources/llvm (git-svn)-[newgvn-predicates]- :) $ cat greater.ll
>>>>> ; Function Attrs: norecurse nounwind readnone ssp uwtable
>>>>> define zeroext i1 @func(i32, i32, i1 zeroext) #0 {
>>>>> ret i1 true
>>>>> }
>>>>>
>>>>>
>>>>> opt -simplifycfg -instcombine does the same thing to it if you use -O0 with clang
>>>>>
>>>>> I believe this is because LLVM does not recognize that meeting path conditions like, for example, X && Y logically means that X is true and Y is true.
>>>>>
>>>>>
>>>>> Yes it does. See both GVN's propagateequality and correlatedvaluepropagation, among other things :)
>>>>>
>>>>> In this case, simplifycfg +instcombine will do it
>>>>>
>>>>> The new predicate support i'm building for GVN will also do it.
>>>>>
>>>>>
>>>>> I'm interested in creating a patch to remedy this; is there a file or function I should look at?
>>>>>
>>>>> Thanks in advance.
>>>>>
>>>>> - CL
>>>>> _______________________________________________
>>>>> LLVM Developers mailing list
>>>>> llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>
>>>>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev <http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev>
>>>>>
>>>>>
>>>>> _______________________________________________
>>>>> LLVM Developers mailing list
>>>>> llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>
>>>>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev <http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev>
>>>>>
>
> _______________________________________________
> 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/20160706/f4ab334a/attachment.html>
More information about the llvm-dev
mailing list