[llvm-dev] [GSoC][Dominators] Preserving the DominatorTree along the pipeline

[Chijun Sima via llvm-dev]

I have been digging into the pipeline of the optimizer during the GSoC
to find whether it is possible to preserve the DominatorTree along it
to improve the compilation time. I managed to preserve the
DominatorTree in TailCallElim [6] and PGOMemOPSize [7]. I also removed
the unnecessary dependency of the domtree in ADCE [8]. I have some
results on preserving the DominatorTree along the pipeline and find
some potential improvements. These results are based on LLVM revision
339227.

In the legacy pass manager, the DominatorTree construction is
triggered by the following passes:
1. SROA
2. Promote Memory to Register
3. Basic Alias Analysis
4. Natural Loop Information pass
in the O2/O3 pipeline [1-2]. The PostDominatorTree construction is
triggered by ADCE because it’s the only pass using the
PostDominatorTree. After digging more, I found these passes all indeed
use the DominatorTree in their passes, so it’s not feasible to save
the DominatorTree construction by removing dependency on the domtree
analysis from passes that don’t need the DominatorTree.

The DominatorTree is invalidated in the legacy pass manager in two ways:
1. by a Module pass that invalidates domtree.
2. The tree encounters a SimplifyCFG Pass. (also applies to the
PostDominatorTree)

For the second one, I have created a work-in-progress patch [3] which
can automatically figure out all updates need to be applied after
simplifyCFG runs. I benchmarked to see whether it is profitable to
preserve the DominatorTree. [4-5] Although the benchmark does not show
good results currently (by comparing the total time used by the
DomTree Calculation), it is good to look into why preserving DomTree
in SimplifyCFG takes so long and whether we can improve it to make it
faster than reconstruction.

In the new pass manager, the pipeline is much more dynamic than the
legacy one. The way it runs varies across different bitcode files.
I observed that the DominatorTree construction is triggered by the
following passes:
1. AggressiveInstCombinePass (for O3)
2. CGProfilePass (Module pass)
3. GlobalOptPass (Module pass)
4. InstCombinePass
5. LoopSimplifyPass
6. SLPVectorizerPass
7. SpeculateAroundPHIsPass
8. SROA
The PostDominatorTree construction is triggered by ADCE.

The DomintorTree is invalidated in the new pass manager in the following ways:
1. After the last time CGSCC pass manager runs which invalidates all analysis.
2. by simplifyCFG pass. (It is the largest part)
3. by SpeculateAroundPHIsPass.
4. by InlinerPass. (Module pass)

I’m not sure whether the first one and the fourth one can be saved
because it involves the pass manager and I’m not familiar with it.
However, for the SpeculateAroundPHIsPass, I think it is possible to
preserve the DominatorTree in it.

The PostDominatorTree is invalidated in the new pass manager in the
following ways:
1. by simplifyCFG pass.
2. by CorrelatedValuePropagationPass (rarely)
3. by SimpleLoopUnswitchPass (rarely)

I think it is also feasible to preserve the PostDominatorTree in
CorrelatedValuePropagationPass and SimpleLoopUnswitchPass.


Best,
Chijun Sima

[1] https://github.com/llvm-mirror/llvm/blob/741af08ef576224b3468eefe758dc488c07062ba/test/Other/opt-O2-pipeline.ll
[2] https://github.com/llvm-mirror/llvm/blob/741af08ef576224b3468eefe758dc488c07062ba/test/Other/opt-O3-pipeline.ll
[3] https://reviews.llvm.org/D50305
[4] https://reviews.llvm.org/P8097
[5] https://reviews.llvm.org/P8099
[6] https://reviews.llvm.org/D49982
[7] https://reviews.llvm.org/D48914
[8] https://reviews.llvm.org/D49988