Page MenuHomePhabricator

[WIP!][DomTreeUpdater/Auto[2]] A new Auto UpdateStrategy candidate

Authored by NutshellySima on Aug 5 2018, 7:51 AM.



This patch is a work-in-process and I don't intend to commit it. If you are automatically subscribed to this patch, please ignore it.

This patch is an 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).

This patch implements the Auto UpdateStrategy by getting a full snapshot the first time DomTreeUpdater is initialized. Then use the information submitted by users (especially the From points) to avoid full snapshot later. Because the JumpThreading pass always calls DTU.recalculate(F) deep in the MergeBasicBlockIntoOnlyPred in Local.cpp, so though this implementation is theoretically faster than D50302, the result of benchmark don't show great difference.

Diff Detail

Event Timeline

NutshellySima created this revision.Aug 5 2018, 7:51 AM

Some benchmarks on Auto UpdateStrategy 2:

NutshellySima abandoned this revision.Feb 22 2019, 12:13 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 14 seconds to snapshot the CFG.

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