Chijun Sima via llvm-dev
2018-Aug-08 20:17 UTC
[llvm-dev] [GSoC][Dominators] Preserving the DominatorTree along the pipeline
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