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

[Davide Italiano via llvm-dev]

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