This is an archive of the discontinued LLVM Phabricator instance.

[WIP!][DomTreeUpdater/Auto[1]] A new Auto UpdateStrategy to test the impact of passes preserving DomTree
AbandonedPublic

Authored by NutshellySima on Aug 5 2018, 3:40 AM.

Details

Reviewers
kuhar
Summary

This patch is a work-in-process and I don't intend to commit it.

The Auto UpdateStrategy in this patch gets a *full* snapshot every time it is going to apply updates to the DominatorTree and it also needs to snapshot the Function every time a DomTreeUpdater is constructed.

This patch is at first a approach to solve the problems in the current DomTreeUpdater and JumpThreading pass. (We need to figure out the previous state of the CFG when we call applyUpdates()/insertEdge()/deleteEdge() or we need to concern about the internal state of the DomTreeUpdater.) It shows a similar performance most of the times on bitcode files with the current DomTreeUpdater working under Lazy UpdateStrategy after converting CorrelatedValuePropagation/RewriteStatepointsForGC/JumpThreading and testing under the -O3 pipeline. But it also suffers a performance degradation sometimes which is caused by 1. the LazyValueInfo relies on whether the DominatorTree is up to date to perform queries and the new Auto UpdateStrategy reports up-to-date less than the Lazy UpdateStrategy (this issue needs to inspect further); 2. some Function contains a lot of BasicBlock which causes snapshotting really slow. (we can use some other compilers like rustc which emits a lot of BasicBlocks to test it).

Due to the drawbacks above, now this patch is proposed to be a util for developers to inspect whether it is profitable to make a pass preserving the DominatorTree, for example, the SimplifyCFG pass, or some other complicated new passes. It is easy to test it out combining with D50300 and you only need to deal with BasicBlock deletions.

Diff Detail

Event Timeline

NutshellySima created this revision.Aug 5 2018, 3:40 AM
NutshellySima retitled this revision from [WIP!][Dominators] A new Auto UpdateStrategy to test the impact of passes preserving DomTree to [WIP!][DomTreeUpdater/Auto[1]] A new Auto UpdateStrategy to test the impact of passes preserving DomTree.Aug 5 2018, 8:31 AM

Some benchmarks on Auto UpdateStrategy 1:
https://reviews.llvm.org/P8099

NutshellySima abandoned this revision.Feb 22 2019, 12:15 PM

Close this revision because D58170 is landed. D58170 solves the problem this patch trying to resolve.
It also improves the implementation of deduplication, which only takes 0.31s when it deduplicates and validates updates when optimizing clang-5.0.0.bc, while this patch takes 10.8 seconds to snapshot the CFG.

Herald added a project: Restricted Project. · View Herald TranscriptFeb 22 2019, 12:15 PM
Herald added subscribers: jdoerfert, jfb. · View Herald Transcript