[llvm-dev] Path condition propagation

[Daniel Berlin via llvm-dev]

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/20160701/bcd6884e/attachment.html>