[llvm-dev] CFG normalization: avoiding `br i1 false`

[Michael Zolotukhin via llvm-dev]

I agree that LoopSimplifyCFG is the right place to do this. As Anna pointed out, it’s not as easy as to just run SimplifyCFG on a blocks belonging to the current loop: updating loops structure and preserving LCSSA make it challenging, but in the end it not only should solve the original issue mentioned in this thread (eliminating br i1 false), but it also can help compile time by reducing IR size.

Michael

> On Feb 13, 2018, at 5:55 AM, Anna Thomas via llvm-dev <llvm-dev at lists.llvm.org> wrote:
> 
> [ + cc llvm-dev]. 
> 
> This came up again internally and I realized I hadn’t cc’ed llvm-dev in my original response.
> 
> 
> Anna
>> On Dec 4, 2017, at 7:06 PM, Anna Thomas via llvm-dev <llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>> wrote:
>> 
>> Hi Davide,
>> 
>>> On Nov 29, 2017, at 1:08 PM, Davide Italiano via llvm-dev <llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>> wrote:
>>> 
>>> On Wed, Nov 29, 2017 at 9:48 AM, Philip Reames
>>> <listmail at philipreames.com <mailto:listmail at philipreames.com>> wrote:
>>>> There's already a LoopSimplifyCFG which is a loop-pass (and thus can iterate
>>>> with other loop passes) and eliminates trivial branches.  Having a simple
>>>> pass which just strips unreachable blocks and converts conditional branches
>>>> to unconditional ones while updating appropriate analyzes (LoopInfo,
>>>> DomTree, LCSSA, etc..) seems very reasonable.
>>> 
>>> I'm not necessarily convinced having one-trick-pony pass is the best
>>> option here.
>>> It adds complexity, and there's already a pass in-tree which can
>>> provide this functionality.
>>> What are your concerns about running SimplifyCFG more often? It
>>> shouldn't be a compile-time sink
>> The main issue with running SimplifyCFG more often is if we were to place the pass 
>> *in between* a bunch of loop passes. Atleast in the Legacy pass manager, I think this breaks the nice
>> loop caching we have when placing all loop passes together.
>> I’ve not done any measurements on compile time to verify this theory.
>> 
>> LoopSimplifyCFG being a loop pass will not have this problem.
>> 
>>> 
>>>> This could also be a utility
>>>> function called from the end of other passes.  The hard bit is the analysis
>>>> preservation.  A good place to copy from might be the recent loop-unswitch
>>>> work Chandler did.
>>>> 
>>>> Philip
>>>> 
>>> 
>>> I don't think preserving the analyses is extremely hard (but I may be
>>> wrong on this).
>>> The incremental Dominator tree API makes the updates fairly easy.
>>> LCSSA is slightly more complicated.
>>> If you take a look at the new LoopUnswitch, in fact, it does call
>>> recalculate rather than fixing it incrementally.
>>> But, if LCSSA is computed right, recomputing entirely should take very
>>> little time.
>> 
>> The trouble (when I tried this transform in LoopSimplifyCFG) is updating 
>> loopInfo analysis: we can have cases where eliminating trivial branches in an inner loop 
>> will break the outer loop structure, and can cause it to no longer be a loop (consider a perfectly nested
>> inner loop within an outer loop, where the trivial branch is br i1 false, label %outerloopheader, label %innerloopHdr).
>> 
>> Another problem is if we changed the branches to unconditional ones, which then
>> makes some inner loop unreachable (i.e. no longer loops in LLVM terminology). 
>> 
>> We will need to record these kinds of loops and update the LPM. There maybe more here.
>> 
>> Thanks,
>> Anna
>>> 
>>> Thanks,
>>> 
>>> --
>>> Davide
>>> _______________________________________________
>>> 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/20180218/ee6f7a1d/attachment.html>