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

[via llvm-dev]

LoopSimplifyCFG should be updated to do this (I don’t know if it’s in the main pass pipeline yet, though).

When I wrote it I basically only included the simplest possible behavior that I needed with the possibility to add more in the future; I don’t know how much has been added since, of course.

—escha

> On Nov 29, 2017, at 9:48 AM, Philip Reames via llvm-dev <llvm-dev at lists.llvm.org> 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.  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
> 
> 
> On 11/15/2017 10:03 AM, Davide Italiano via llvm-dev wrote:
>> On Wed, Nov 15, 2017 at 5:15 AM, Ariel Ben-Yehuda <ariel.byd at gmail.com> wrote:
>>>> I'm not necessarily sympathetic to the idea of adding another canonicalization pass only for this purpose.
>>> 
>>> The problem is that as you said, SimplifyCfg does all sorts of stuff,
>>> and I suspect is not the fastest pass in the world.
>>> 
>> I've not seen it showing up in a profile myself, although I'm not sure
>> whether it will be true in the future.
>> Sinking, e.g., could be moved in a separate pass (in fact, there's one
>> already, disabled by default).
>> 
>>> Also, in the case that annoys me, there is an LCSSA pass in the
>>> middle, and I suspect it would be a better idea to only do the LCSSA
>>> etc. transform again if no changes were made, which I suspect is the
>>> most common case.
>>> 
>> LCSSA should be linear. Currently it's not because it uses the SSA
>> updater which computes dominance frontiers, so it might get O(N^3).
>> The alternative SSAupdater proposed solves this problem using the
>> novel algorithm from Braun et al. linked in the review
>> https://reviews.llvm.org/D28934
>> It still has the problem that if leaves redundant phis around at the
>> beginning of the block, e.g.
>> 
>> %patatino1 = phi [ %tinky, %somebb, %winky, %someotherbb ]
>> %patatino2 = phi [ %tinky, %somebb, %winky, %someotherbb ]
>> 
>> The current SSA updater pays a (sometimes high) cost to perform this
>> deduplication/removal (actually, checks whether there's already a PHI,
>> and if not inserts one).
>> 
>> --
>> Davide
>> _______________________________________________
>> 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