llvm dev - Mar 2020 - LLVM pass to optimize redundant branch conditions

Hello All

I am looking for an LLVM pass that is able to detect branches whose condition is
known if they are reached. To illustrate what I mean, I attached a screenshot
showing a partial CFG of a function. The branch in basic block for.cond.cleanup3
tests the same condition as the branch in the entry block, and has the same
target BB if the condition is false. Also, if you inspect the graph carefully,
the basic block for.cond.cleanup3 cannot be reached unless the first branch
condition was true. This means that the condition of the branch in
for.cond.cleanup3 will always be true. As such, it is possible to eliminate this
branch, making it unconditional. Is there an LLVM pass that is able to perform
such transformation?

Thanks
-Adel

--
Adel Ejjeh
PhD Candidate - Computer Science
University of Illinois at Urbana-Champaign
201 N Goodwin Ave, Urbana, IL 61801
aejjeh at illinois.edu | adel.ejjeh at gmail.com
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20200326/79c6b948/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image.png
Type: image/png
Size: 118075 bytes
Desc: image.png
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20200326/79c6b948/attachment-0001.png>

I didn't check in detail for this specific case, but the pass that does
optimization like this is lib/Transforms/Scalar/JumpThreading.cpp

~Craig


On Thu, Mar 26, 2020 at 6:25 PM Ejjeh, Adel via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> Hello All
>
> I am looking for an LLVM pass that is able to detect branches whose
> condition is known if they are reached. To illustrate what I mean, I
> attached a screenshot showing a partial CFG of a function. The branch in
> basic block for.cond.cleanup3 tests the same condition as the branch in the
> entry block, and has the same target BB if the condition is false. Also, if
> you inspect the graph carefully, the basic block for.cond.cleanup3 cannot
> be reached unless the first branch condition was true. This means that the
> condition of the branch in for.cond.cleanup3 will always be true. As such,
> it is possible to eliminate this branch, making it unconditional. Is there
> an LLVM pass that is able to perform such transformation?
>
> Thanks
> -Adel
>
> --
> *Adel Ejjeh*
> PhD Candidate - Computer Science
> University of Illinois at Urbana-Champaign
> 201 N Goodwin Ave, Urbana, IL 61801
> aejjeh at illinois.edu | adel.ejjeh at gmail.com
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> https://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/20200326/d4072c35/attachment.html>

Hi Adel,

This is a complicated example I think. It would help if you could provide a
more reduced one and a complete IR. I think that ome of the dead code
elimination passes or LICM may be able to help.

Best,
Stefanos Baziotis

On Fri, Mar 27, 2020, 03:25 Ejjeh, Adel via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> Hello All
>
> I am looking for an LLVM pass that is able to detect branches whose
> condition is known if they are reached. To illustrate what I mean, I
> attached a screenshot showing a partial CFG of a function. The branch in
> basic block for.cond.cleanup3 tests the same condition as the branch in the
> entry block, and has the same target BB if the condition is false. Also, if
> you inspect the graph carefully, the basic block for.cond.cleanup3 cannot
> be reached unless the first branch condition was true. This means that the
> condition of the branch in for.cond.cleanup3 will always be true. As such,
> it is possible to eliminate this branch, making it unconditional. Is there
> an LLVM pass that is able to perform such transformation?
>
> Thanks
> -Adel
>
> --
> *Adel Ejjeh*
> PhD Candidate - Computer Science
> University of Illinois at Urbana-Champaign
> 201 N Goodwin Ave, Urbana, IL 61801
> aejjeh at illinois.edu | adel.ejjeh at gmail.com
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> https://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/20200327/dbf27584/attachment.html>

Oh I didn't see Craig's comment. Thanks I didn't know about this
pass.

On Fri, Mar 27, 2020, 04:01 Stefanos Baziotis <stefanos.baziotis at
gmail.com>
wrote:
> Hi Adel,
>
> This is a complicated example I think. It would help if you could provide
> a more reduced one and a complete IR. I think that ome of the dead code
> elimination passes or LICM may be able to help.
>
> Best,
> Stefanos Baziotis
>
> On Fri, Mar 27, 2020, 03:25 Ejjeh, Adel via llvm-dev <
> llvm-dev at lists.llvm.org> wrote:
>
>> Hello All
>>
>> I am looking for an LLVM pass that is able to detect branches whose
>> condition is known if they are reached. To illustrate what I mean, I
>> attached a screenshot showing a partial CFG of a function. The branch
in
>> basic block for.cond.cleanup3 tests the same condition as the branch in
the
>> entry block, and has the same target BB if the condition is false.
Also, if
>> you inspect the graph carefully, the basic block for.cond.cleanup3
cannot
>> be reached unless the first branch condition was true. This means that
the
>> condition of the branch in for.cond.cleanup3 will always be true. As
such,
>> it is possible to eliminate this branch, making it unconditional. Is
there
>> an LLVM pass that is able to perform such transformation?
>>
>> Thanks
>> -Adel
>>
>> --
>> *Adel Ejjeh*
>> PhD Candidate - Computer Science
>> University of Illinois at Urbana-Champaign
>> 201 N Goodwin Ave, Urbana, IL 61801
>> aejjeh at illinois.edu | adel.ejjeh at gmail.com
>> _______________________________________________
>> LLVM Developers mailing list
>> llvm-dev at lists.llvm.org
>> https://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/20200327/5396dafa/attachment.html>