更激进的死代码删除.
在 llvm/lib/Transforms/Scalar/ADCE.cpp:
其中 auto *DT = FAM.getCachedResult<DominatorTreeAnalysis>(F); 是支配树, auto &PDT = FAM.getResult<PostDominatorTreeAnalysis>(F); 是后支配树. ADCEPass 的核心实现就是 AggressiveDeadCodeElimination(F, DT, PDT).performDeadCodeElimination();. 在看 AggressiveDeadCodeElimination 类之前, 让我们简单回忆一下必经节点, 后必经节点, 支配, 支配树, 后支配树等概念:
我们先看这两个储存指令和基本块信息的结构体:
回到 AggressiveDeadCodeElimination:
我们跟着 performDeadCodeElimination 中的调用看一看, 首先是 initialize:
瞄一眼
再看看 markLive:
可以看到 markLive 还是做了很多的, 两个重载对指令和块处理:
在来看 markLiveInstructions:
在来看看 removeDeadInstructions:
对比 DCEPass 与 ADCEPass
使用一下:
可以看到 BB2 被正确处理了.
更新地址: 460K9s2c8@1M7s2y4Q4x3@1q4Q4x3V1k6Q4x3V1k6Y4K9i4c8Z5N6h3u0Q4x3X3g2U0L8$3#2Q4x3V1k6F1L8%4c8Z5K9h3&6Y4i4K6u0V1x3U0x3K6x3#2)9J5c8X3I4D9N6X3#2Q4x3X3c8H3j5i4y4K6i4K6u0V1L8r3g2S2M7X3^5`.
PreservedAnalyses ADCEPass::run(Function &F, FunctionAnalysisManager &FAM) {
auto *DT = FAM.getCachedResult<DominatorTreeAnalysis>(F);
auto &PDT = FAM.getResult<PostDominatorTreeAnalysis>(F);
ADCEChanged Changed =
AggressiveDeadCodeElimination(F, DT, PDT).performDeadCodeElimination();
if (!Changed.ChangedAnything)
return PreservedAnalyses::all();
PreservedAnalyses PA;
if (!Changed.ChangedControlFlow) {
PA.preserveSet<CFGAnalyses>();
if (!Changed.ChangedNonDebugInstr) {
PA.preserve<MemorySSAAnalysis>();
}
}
PA.preserve<DominatorTreeAnalysis>();
PA.preserve<PostDominatorTreeAnalysis>();
return PA;
}
struct InstInfoType {
bool Live = false;
struct BlockInfoType *Block = nullptr;
};
struct BlockInfoType {
bool Live = false;
bool UnconditionalBranch = false;
bool HasLivePhiNodes = false;
bool CFLive = false;
InstInfoType *TerminatorLiveInfo = nullptr;
BasicBlock *BB = nullptr;
Instruction *Terminator = nullptr;
unsigned PostOrder;
bool terminatorIsLive() const { return TerminatorLiveInfo->Live; }
};
AggressiveDeadCodeElimination(Function &F, DominatorTree *DT,
PostDominatorTree &PDT)
: F(F), DT(DT), PDT(PDT) {}
ADCEChanged AggressiveDeadCodeElimination::performDeadCodeElimination() {
initialize();
markLiveInstructions();
return removeDeadInstructions();
}
void AggressiveDeadCodeElimination::initialize() {
auto NumBlocks = F.size();
BlockInfo.reserve(NumBlocks);
size_t NumInsts = 0;
for (auto &BB : F) {
NumInsts += BB.size();
auto &Info = BlockInfo[&BB];
Info.BB = &BB;
Info.Terminator = BB.getTerminator();
Info.UnconditionalBranch = isUnconditionalBranch(Info.Terminator);
}
InstInfo.reserve(NumInsts);
for (auto &BBInfo : BlockInfo)
for (Instruction &I : *BBInfo.second.BB)
InstInfo[&I].Block = &BBInfo.second;
for (auto &BBInfo : BlockInfo)
BBInfo.second.TerminatorLiveInfo = &InstInfo[BBInfo.second.Terminator];
for (Instruction &I : instructions(F))
if (isAlwaysLive(I))
markLive(&I);
if (!RemoveControlFlowFlag)
return;
if (!RemoveLoops) {
using StatusMap = DenseMap<BasicBlock *, bool>;
class DFState : public StatusMap {
public:
std::pair<StatusMap::iterator, bool> insert(BasicBlock *BB) {
return StatusMap::insert(std::make_pair(BB, true));
}
void completed(BasicBlock *BB) { (*this)[BB] = false; }
bool onStack(BasicBlock *BB) {
auto Iter = find(BB);
return Iter != end() && Iter->second;
}
} State;
State.reserve(F.size());
for (auto *BB: depth_first_ext(&F.getEntryBlock(), State)) {
Instruction *Term = BB->getTerminator();
if (isLive(Term))
continue;
for (auto *Succ : successors(BB))
if (State.onStack(Succ)) {
markLive(Term);
break;
}
}
}
for (const auto &PDTChild : children<DomTreeNode *>(PDT.getRootNode())) {
auto *BB = PDTChild->getBlock();
auto &Info = BlockInfo[BB];
if (isa<ReturnInst>(Info.Terminator)) {
LLVM_DEBUG(dbgs() << "post-dom root child is a return: " << BB->getName()
<< '\n';);
continue;
}
for (auto *DFNode : depth_first(PDTChild))
markLive(BlockInfo[DFNode->getBlock()].Terminator);
}
auto *BB = &F.getEntryBlock();
auto &EntryInfo = BlockInfo[BB];
EntryInfo.Live = true;
if (EntryInfo.UnconditionalBranch)
markLive(EntryInfo.Terminator);
for (auto &BBInfo : BlockInfo)
if (!BBInfo.second.terminatorIsLive())
BlocksWithDeadTerminators.insert(BBInfo.second.BB);
}
bool Instruction::mayHaveSideEffects() const {
return mayWriteToMemory() || mayThrow() || !willReturn();
}
bool AggressiveDeadCodeElimination::isAlwaysLive(Instruction &I) {
if (I.isEHPad() || I.mayHaveSideEffects()) {
if (isInstrumentsConstant(I))
return false;
return true;
}
if (!I.isTerminator())
return false;
if (RemoveControlFlowFlag && (isa<BranchInst>(I) || isa<SwitchInst>(I)))
return false;
return true;
}
void AggresiveDeadCodeElimination::markLive(Instruction *I) {
auto &Info = InstInfo[I];
if (Info.Live)
return;
LLVM_DEBUG(dbgs() << "mark live: "; I->dump());
Info.Live = true;
Worklist.push_back(I);
if (const DILocation *DL = I->getDebugLoc())
collectLiveScopes(*DL);
auto &BBInfo = *Info.Block;
if (BBInfo.Terminator == I) {
BlocksWithDeadTerminators.remove(BBInfo.BB);
if (!BBInfo.UnconditionalBranch)
for (auto *BB : successors(I->getParent()))
markLive(BB);
}
markLive(BBInfo);
}
void AggressiveDeadCodeElimination::markLive(BlockInfoType &BBInfo) {
if (BBInfo.Live)
return;
LLVM_DEBUG(dbgs() << "mark block live: " << BBInfo.BB->getName() << '\n');
BBInfo.Live = true;
if (!BBInfo.CFLive) {
BBInfo.CFLive = true;
NewLiveBlocks.insert(BBInfo.BB);
}
if (BBInfo.UnconditionalBranch)
markLive(BBInfo.Terminator);
}
void AggressiveDeadCodeElimination::markLiveInstructions() {
do {
while (!Worklist.empty()) {
Instruction *LiveInst = Worklist.pop_back_val();
LLVM_DEBUG(dbgs() << "work live: "; LiveInst->dump(););
for (Use &OI : LiveInst->operands())
if (Instruction *Inst = dyn_cast<Instruction>(OI))
markLive(Inst);
if (auto *PN = dyn_cast<PHINode>(LiveInst))
markPhiLive(PN);
}
markLiveBranchesFromControlDependences();
} while (!Worklist.empty());
}
void AggressiveDeadCodeElimination::markPhiLive(PHINode *PN) {
auto &Info = BlockInfo[PN->getParent()];
if (Info.HasLivePhiNodes)
return;
Info.HasLivePhiNodes = true;
for (auto *PredBB : predecessors(Info.BB)) {
auto &Info = BlockInfo[PredBB];
if (!Info.CFLive) {
Info.CFLive = true;
NewLiveBlocks.insert(PredBB);
}
}
}
void AggressiveDeadCodeElimination::markLiveBranchesFromControlDependences() {
if (BlocksWithDeadTerminators.empty())
return;
LLVM_DEBUG({
dbgs() << "new live blocks:\n";
for (auto *BB : NewLiveBlocks)
dbgs() << "\t" << BB->getName() << '\n';
dbgs() << "dead terminator blocks:\n";
for (auto *BB : BlocksWithDeadTerminators)
dbgs() << "\t" << BB->getName() << '\n';
});
const SmallPtrSet<BasicBlock *, 16> BWDT(llvm::from_range,
BlocksWithDeadTerminators);
SmallVector<BasicBlock *, 32> IDFBlocks;
ReverseIDFCalculator IDFs(PDT);
IDFs.setDefiningBlocks(NewLiveBlocks);
IDFs.setLiveInBlocks(BWDT);
IDFs.calculate(IDFBlocks);
NewLiveBlocks.clear();
for (auto *BB : IDFBlocks) {
LLVM_DEBUG(dbgs() << "live control in: " << BB->getName() << '\n');
markLive(BB->getTerminator());
}
}
ADCEChanged AggressiveDeadCodeElimination::removeDeadInstructions() {
ADCEChanged Changed;
Changed.ChangedControlFlow = updateDeadRegions();
LLVM_DEBUG({
for (Instruction &I : instructions(F)) {
if (isLive(&I))
continue;
if (auto *DII = dyn_cast<DbgVariableIntrinsic>(&I)) {
if (AliveScopes.count(DII->getDebugLoc()->getScope()))
continue;
for (Value *V : DII->location_ops()) {
if (Instruction *II = dyn_cast<Instruction>(V)) {
if (isLive(II)) {
dbgs() << "Dropping debug info for " << *DII << "\n";
break;
}
}
}
}
}
});
for (Instruction &I : llvm::reverse(instructions(F))) {
for (DbgRecord &DR : make_early_inc_range(I.getDbgRecordRange())) {
if (DbgVariableRecord *DVR = dyn_cast<DbgVariableRecord>(&DR);
DVR && DVR->isDbgAssign())
if (!at::getAssignmentInsts(DVR).empty())
continue;
if (AliveScopes.count(DR.getDebugLoc()->getScope()))
continue;
I.dropOneDbgRecord(&DR);
}
if (isLive(&I))
continue;
Changed.ChangedNonDebugInstr = true;
Worklist.push_back(&I);
salvageDebugInfo(I);
}
for (Instruction *&I : Worklist)
I->dropAllReferences();
for (Instruction *&I : Worklist) {
++NumRemoved;
I->eraseFromParent();
}
Changed.ChangedAnything = Changed.ChangedControlFlow || !Worklist.empty();
return Changed;
}
bool AggressiveDeadCodeElimination::updateDeadRegions() {
LLVM_DEBUG({
dbgs() << "final dead terminator blocks: " << '\n';
for (auto *BB : BlocksWithDeadTerminators)
dbgs() << '\t' << BB->getName()
<< (BlockInfo[BB].Live ? " LIVE\n" : "\n");
});
bool HavePostOrder = false;
bool Changed = false;
SmallVector<DominatorTree::UpdateType, 10> DeletedEdges;
for (auto *BB : BlocksWithDeadTerminators) {
auto &Info = BlockInfo[BB];
if (Info.UnconditionalBranch) {
InstInfo[Info.Terminator].Live = true;
continue;
}
if (!HavePostOrder) {
computeReversePostOrder();
HavePostOrder = true;
}
BlockInfoType *PreferredSucc = nullptr;
for (auto *Succ : successors(BB)) {
auto *Info = &BlockInfo[Succ];
if (!PreferredSucc || PreferredSucc->PostOrder < Info->PostOrder)
PreferredSucc = Info;
}
assert((PreferredSucc && PreferredSucc->PostOrder > 0) &&
"Failed to find safe successor for dead branch");
SmallPtrSet<BasicBlock *, 4> RemovedSuccessors;
bool First = true;
for (auto *Succ : successors(BB)) {
if (!First || Succ != PreferredSucc->BB) {
Succ->removePredecessor(BB);
RemovedSuccessors.insert(Succ);
} else
First = false;
}
makeUnconditional(BB, PreferredSucc->BB);
for (auto *Succ : RemovedSuccessors) {
if (Succ != PreferredSucc->BB) {
LLVM_DEBUG(dbgs() << "ADCE: (Post)DomTree edge enqueued for deletion"
<< BB->getName() << " -> " << Succ->getName()
<< "\n");
DeletedEdges.push_back({DominatorTree::Delete, BB, Succ});
}
}
NumBranchesRemoved += 1;
Changed = true;
}
if (!DeletedEdges.empty())
DomTreeUpdater(DT, &PDT, DomTreeUpdater::UpdateStrategy::Eager)
.applyUpdates(DeletedEdges);
return Changed;
}
void AggressiveDeadCodeElimination::computeReversePostOrder() {
SmallPtrSet<BasicBlock*, 16> Visited;
unsigned PostOrder = 0;
for (auto &BB : F) {
if (!succ_empty(&BB))
continue;
for (BasicBlock *Block : inverse_post_order_ext(&BB,Visited))
BlockInfo[Block].PostOrder = PostOrder++;
}
}
define i32 @Test(i32 %A, i32 %B) {
BB1:
br label %BB4
BB2: ; No predecessors!
%tmp = add i32 1, 2
br label %BB3
BB3: ; preds = %BB4, %BB2
%ret = phi i32 [ %X, %BB4 ], [ %B, %BB2 ] ; <i32> [#uses=1]
ret i32 %ret
BB4: ; preds = %BB1
%X = phi i32 [ %A, %BB1 ] ; <i32> [#uses=1]
br label %BB3
}
./build/bin/opt -passes=adce -S /tmp/a.ll
; ModuleID = '/tmp/a.ll'
source_filename = "/tmp/a.ll"
define i32 @Test(i32 %A, i32 %B) {
BB1:
br label %BB4
BB2: ; No predecessors!
br label %BB3
BB3: ; preds = %BB4, %BB2
%ret = phi i32 [ %X, %BB4 ], [ %B, %BB2 ]
ret i32 %ret
BB4: ; preds = %BB1
%X = phi i32 [ %A, %BB1 ]
br label %BB3
}
- 想象一个 cfg: 有很多基本块(包括基本块 A 与 B), 有各种语句.
- 支配节点与支配: A 支配 B = 从入口走到 B, 必须经过 A, 则 A 是 B 的支配节点. 每个块支配自己.
- 严格支配: A 支配 B, A ≠ B, A 严格支配 B.
- 必经节点: 离 B 最近的支配节点是必经节点. 则每个节点只有一个必经节点.
- 支配树: 将所有的直接支配关系链接起来就是一棵树(由 "每个节点只有一个必经节点" 可以推是树不是环). 树上从根到任何节点的路径 = 支配链.
- 后支配节点: A 后支配 B = 从 B 走到函数出口, 必须经过 A. 每个块后支配自己.
- 后必经节点: 离 B 最近的后支配节点是后必经节点, 则每个节点只有一个后必经节点.
- 后支配树: 把所有直接后支配关系连起来, 也是一棵树
- 支配边界: A 支配 B 的某个前驱块, A 不严格支配 B, B 是 A 的支配边界. 也就是说
A 能管住一条到 B 的路, 但管不住所有到 B 的路, 那么 B 是 A 的支配边界. (phi 节点所在块, 必须是「不同分支中变量定义块」的支配边界, 这个后续 SSA 再谈)
- 后支配边界: 支配边界定义反过来, B 被 A 的某个后继块后支配, B 不被 A 严格后支配, B 是 A 的后支配边界. 也就是说
A 有多条路走向出口, 其中一部分路会经过 B, 另一部分不经过 B, 那么 B 就是 A 的后支配边界.
- 迭代支配边界: DF 的迭代 = 把所有间接能影响到的块全都算进去, 即
IDF(X) = DF(X) ∪ DF(DF(X)) ∪ DF(DF(DF(X)))...
- 半支配节点: 只用于高效算支配树, 是个工具节点, Lengauer-Tarjan 算法.

- 维护 Worklist 等, 方便后续处理
- 收集调试信息
- 以条件分支指令为终止指令的基本块, 将其及其后继标记为活
- 无条件分支标记其为活