llvm dev - Nov 2017 - CFG normalization: avoiding `br i1 false`

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

On Wed, Nov 29, 2017 at 9:48 AM, Philip Reames
<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
> 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.

Thanks,

--
Davide

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

Hi Davide,
> On Nov 29, 2017, at 1:08 PM, Davide Italiano via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
> 
> On Wed, Nov 29, 2017 at 9:48 AM, Philip Reames
> <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
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev