[llvm-dev] Path condition propagation
Daniel Berlin via llvm-dev
llvm-dev at lists.llvm.org
Sun Jul 3 17:40:43 PDT 2016
Sure
On Mon, Jul 4, 2016, 9:40 AM Carlos Liam <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> 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/20160704/9328d902/attachment.html>
More information about the llvm-dev
mailing list