[llvm-dev] Path condition propagation

[Carlos Liam via llvm-dev]

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> 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> wrote:
>> That seems ominous; should I not bother?
>> 
>>  - CL
>> 
>>> On Jul 3, 2016, at 5:58 PM, Daniel Berlin <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> 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> 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> wrote:
>>>>>>> On Thu, Jun 30, 2016 at 6:45 PM, Daniel Berlin via llvm-dev <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> 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
>>>>>>>> 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/20160703/e77c513c/attachment-0001.html>