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

[Philip Reames via llvm-dev]

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