Skip to content

Commit c04b530

Browse files
author
Max Kazantsev
committedNov 20, 2018
Recommit "[LoopSimplifyCFG] Teach LoopSimplifyCFG to constant-fold branches and switches"
The initial version of patch lacked Phi nodes updates in destinations of removed edges. This version contains this update and tests on this situation. Differential Revision: https://reviews.llvm.org/D54021 llvm-svn: 347289
1 parent 9b39390 commit c04b530

File tree

2 files changed

+464
-9
lines changed

2 files changed

+464
-9
lines changed
 

‎llvm/lib/Transforms/Scalar/LoopSimplifyCFG.cpp

+315
Original file line numberDiff line numberDiff line change
@@ -41,6 +41,318 @@ using namespace llvm;
4141

4242
#define DEBUG_TYPE "loop-simplifycfg"
4343

44+
STATISTIC(NumTerminatorsFolded,
45+
"Number of terminators folded to unconditional branches");
46+
47+
/// If \p BB is a switch or a conditional branch, but only one of its successors
48+
/// can be reached from this block in runtime, return this successor. Otherwise,
49+
/// return nullptr.
50+
static BasicBlock *getOnlyLiveSuccessor(BasicBlock *BB) {
51+
Instruction *TI = BB->getTerminator();
52+
if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
53+
if (BI->isUnconditional())
54+
return nullptr;
55+
if (BI->getSuccessor(0) == BI->getSuccessor(1))
56+
return BI->getSuccessor(0);
57+
ConstantInt *Cond = dyn_cast<ConstantInt>(BI->getCondition());
58+
if (!Cond)
59+
return nullptr;
60+
return Cond->isZero() ? BI->getSuccessor(1) : BI->getSuccessor(0);
61+
}
62+
63+
if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
64+
auto *CI = dyn_cast<ConstantInt>(SI->getCondition());
65+
if (!CI)
66+
return nullptr;
67+
for (auto Case : SI->cases())
68+
if (Case.getCaseValue() == CI)
69+
return Case.getCaseSuccessor();
70+
return SI->getDefaultDest();
71+
}
72+
73+
return nullptr;
74+
}
75+
76+
/// Helper class that can turn branches and switches with constant conditions
77+
/// into unconditional branches.
78+
class ConstantTerminatorFoldingImpl {
79+
private:
80+
Loop &L;
81+
LoopInfo &LI;
82+
DominatorTree &DT;
83+
84+
// Whether or not the current loop will still exist after terminator constant
85+
// folding will be done. In theory, there are two ways how it can happen:
86+
// 1. Loop's latch(es) become unreachable from loop header;
87+
// 2. Loop's header becomes unreachable from method entry.
88+
// In practice, the second situation is impossible because we only modify the
89+
// current loop and its preheader and do not affect preheader's reachibility
90+
// from any other block. So this variable set to true means that loop's latch
91+
// has become unreachable from loop header.
92+
bool DeleteCurrentLoop = false;
93+
94+
// The blocks of the original loop that will still be reachable from entry
95+
// after the constant folding.
96+
SmallPtrSet<BasicBlock *, 8> LiveLoopBlocks;
97+
// The blocks of the original loop that will become unreachable from entry
98+
// after the constant folding.
99+
SmallPtrSet<BasicBlock *, 8> DeadLoopBlocks;
100+
// The exits of the original loop that will still be reachable from entry
101+
// after the constant folding.
102+
SmallPtrSet<BasicBlock *, 8> LiveExitBlocks;
103+
// The exits of the original loop that will become unreachable from entry
104+
// after the constant folding.
105+
SmallPtrSet<BasicBlock *, 8> DeadExitBlocks;
106+
// The blocks that will still be a part of the current loop after folding.
107+
SmallPtrSet<BasicBlock *, 8> BlocksInLoopAfterFolding;
108+
// The blocks that have terminators with constant condition that can be
109+
// folded. Note: fold candidates should be in L but not in any of its
110+
// subloops to avoid complex LI updates.
111+
SmallVector<BasicBlock *, 8> FoldCandidates;
112+
113+
void dump() const {
114+
dbgs() << "Constant terminator folding for loop " << L << "\n";
115+
dbgs() << "After terminator constant-folding, the loop will";
116+
if (!DeleteCurrentLoop)
117+
dbgs() << " not";
118+
dbgs() << " be destroyed\n";
119+
dbgs() << "Blocks in which we can constant-fold terminator:\n";
120+
for (const BasicBlock *BB : FoldCandidates)
121+
dbgs() << "\t" << BB->getName() << "\n";
122+
auto PrintOutSet = [&](const char *Message,
123+
const SmallPtrSetImpl<BasicBlock *> &S) {
124+
dbgs() << Message << "\n";
125+
for (const BasicBlock *BB : S)
126+
dbgs() << "\t" << BB->getName() << "\n";
127+
};
128+
PrintOutSet("Live blocks from the original loop:", LiveLoopBlocks);
129+
PrintOutSet("Dead blocks from the original loop:", DeadLoopBlocks);
130+
PrintOutSet("Live exit blocks:", LiveExitBlocks);
131+
PrintOutSet("Dead exit blocks:", DeadExitBlocks);
132+
if (!DeleteCurrentLoop)
133+
PrintOutSet("The following blocks will still be part of the loop:",
134+
BlocksInLoopAfterFolding);
135+
}
136+
137+
/// Fill all information about status of blocks and exits of the current loop
138+
/// if constant folding of all branches will be done.
139+
void analyze() {
140+
LoopBlocksDFS DFS(&L);
141+
DFS.perform(&LI);
142+
assert(DFS.isComplete() && "DFS is expected to be finished");
143+
144+
// Collect live and dead loop blocks and exits.
145+
SmallPtrSet<BasicBlock *, 8> ExitBlocks;
146+
LiveLoopBlocks.insert(L.getHeader());
147+
for (auto I = DFS.beginRPO(), E = DFS.endRPO(); I != E; ++I) {
148+
BasicBlock *BB = *I;
149+
150+
// If a loop block wasn't marked as live so far, then it's dead.
151+
if (!LiveLoopBlocks.count(BB)) {
152+
DeadLoopBlocks.insert(BB);
153+
continue;
154+
}
155+
156+
BasicBlock *TheOnlySucc = getOnlyLiveSuccessor(BB);
157+
158+
// If a block has only one live successor, it's a candidate on constant
159+
// folding. Only handle blocks from current loop: branches in child loops
160+
// are skipped because if they can be folded, they should be folded during
161+
// the processing of child loops.
162+
if (TheOnlySucc && LI.getLoopFor(BB) == &L)
163+
FoldCandidates.push_back(BB);
164+
165+
// Handle successors.
166+
auto ProcessSuccessor = [&](BasicBlock *Succ, bool IsLive) {
167+
if (!L.contains(Succ)) {
168+
if (IsLive)
169+
LiveExitBlocks.insert(Succ);
170+
ExitBlocks.insert(Succ);
171+
} else if (IsLive)
172+
LiveLoopBlocks.insert(Succ);
173+
};
174+
for (BasicBlock *Succ : successors(BB))
175+
ProcessSuccessor(Succ, !TheOnlySucc || TheOnlySucc == Succ);
176+
}
177+
178+
// Sanity check: amount of dead and live loop blocks should match the total
179+
// number of blocks in loop.
180+
assert(L.getNumBlocks() == LiveLoopBlocks.size() + DeadLoopBlocks.size() &&
181+
"Malformed block sets?");
182+
183+
// Now, all exit blocks that are not marked as live are dead.
184+
for (auto *ExitBlock : ExitBlocks)
185+
if (!LiveExitBlocks.count(ExitBlock))
186+
DeadExitBlocks.insert(ExitBlock);
187+
188+
// Whether or not the edge From->To will still be present in graph after the
189+
// folding.
190+
auto IsEdgeLive = [&](BasicBlock *From, BasicBlock *To) {
191+
if (!LiveLoopBlocks.count(From))
192+
return false;
193+
BasicBlock *TheOnlySucc = getOnlyLiveSuccessor(From);
194+
return !TheOnlySucc || TheOnlySucc == To;
195+
};
196+
197+
// The loop will not be destroyed if its latch is live.
198+
DeleteCurrentLoop = !IsEdgeLive(L.getLoopLatch(), L.getHeader());
199+
200+
// If we are going to delete the current loop completely, no extra analysis
201+
// is needed.
202+
if (DeleteCurrentLoop)
203+
return;
204+
205+
// Otherwise, we should check which blocks will still be a part of the
206+
// current loop after the transform.
207+
BlocksInLoopAfterFolding.insert(L.getLoopLatch());
208+
// If the loop is live, then we should compute what blocks are still in
209+
// loop after all branch folding has been done. A block is in loop if
210+
// it has a live edge to another block that is in the loop; by definition,
211+
// latch is in the loop.
212+
auto BlockIsInLoop = [&](BasicBlock *BB) {
213+
return any_of(successors(BB), [&](BasicBlock *Succ) {
214+
return BlocksInLoopAfterFolding.count(Succ) && IsEdgeLive(BB, Succ);
215+
});
216+
};
217+
for (auto I = DFS.beginPostorder(), E = DFS.endPostorder(); I != E; ++I) {
218+
BasicBlock *BB = *I;
219+
if (BlockIsInLoop(BB))
220+
BlocksInLoopAfterFolding.insert(BB);
221+
}
222+
223+
// Sanity check: header must be in loop.
224+
assert(BlocksInLoopAfterFolding.count(L.getHeader()) &&
225+
"Header not in loop?");
226+
}
227+
228+
/// Constant-fold terminators of blocks acculumated in FoldCandidates into the
229+
/// unconditional branches.
230+
void foldTerminators() {
231+
DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
232+
233+
for (BasicBlock *BB : FoldCandidates) {
234+
assert(LI.getLoopFor(BB) == &L && "Should be a loop block!");
235+
BasicBlock *TheOnlySucc = getOnlyLiveSuccessor(BB);
236+
assert(TheOnlySucc && "Should have one live successor!");
237+
238+
LLVM_DEBUG(dbgs() << "Replacing terminator of " << BB->getName()
239+
<< " with an unconditional branch to the block "
240+
<< TheOnlySucc->getName() << "\n");
241+
242+
SmallPtrSet<BasicBlock *, 2> DeadSuccessors;
243+
// Remove all BB's successors except for the live one.
244+
for (auto *Succ : successors(BB))
245+
if (Succ != TheOnlySucc) {
246+
DeadSuccessors.insert(Succ);
247+
Succ->removePredecessor(BB);
248+
}
249+
250+
IRBuilder<> Builder(BB->getContext());
251+
Instruction *Term = BB->getTerminator();
252+
Builder.SetInsertPoint(Term);
253+
Builder.CreateBr(TheOnlySucc);
254+
Term->eraseFromParent();
255+
256+
for (auto *DeadSucc : DeadSuccessors)
257+
DTU.deleteEdge(BB, DeadSucc);
258+
259+
++NumTerminatorsFolded;
260+
}
261+
}
262+
263+
public:
264+
ConstantTerminatorFoldingImpl(Loop &L, LoopInfo &LI, DominatorTree &DT)
265+
: L(L), LI(LI), DT(DT) {}
266+
bool run() {
267+
assert(L.getLoopLatch() && "Should be single latch!");
268+
269+
// Collect all available information about status of blocks after constant
270+
// folding.
271+
analyze();
272+
273+
LLVM_DEBUG(dbgs() << "In function " << L.getHeader()->getParent()->getName()
274+
<< ": ");
275+
276+
// Nothing to constant-fold.
277+
if (FoldCandidates.empty()) {
278+
LLVM_DEBUG(
279+
dbgs() << "No constant terminator folding candidates found in loop "
280+
<< L.getHeader()->getName() << "\n");
281+
return false;
282+
}
283+
284+
// TODO: Support deletion of the current loop.
285+
if (DeleteCurrentLoop) {
286+
LLVM_DEBUG(
287+
dbgs()
288+
<< "Give up constant terminator folding in loop "
289+
<< L.getHeader()->getName()
290+
<< ": we don't currently support deletion of the current loop.\n");
291+
return false;
292+
}
293+
294+
// TODO: Support deletion of dead loop blocks.
295+
if (!DeadLoopBlocks.empty()) {
296+
LLVM_DEBUG(dbgs() << "Give up constant terminator folding in loop "
297+
<< L.getHeader()->getName()
298+
<< ": we don't currently"
299+
" support deletion of dead in-loop blocks.\n");
300+
return false;
301+
}
302+
303+
// TODO: Support dead loop exits.
304+
if (!DeadExitBlocks.empty()) {
305+
LLVM_DEBUG(dbgs() << "Give up constant terminator folding in loop "
306+
<< L.getHeader()->getName()
307+
<< ": we don't currently support dead loop exits.\n");
308+
return false;
309+
}
310+
311+
// TODO: Support blocks that are not dead, but also not in loop after the
312+
// folding.
313+
if (BlocksInLoopAfterFolding.size() != L.getNumBlocks()) {
314+
LLVM_DEBUG(
315+
dbgs() << "Give up constant terminator folding in loop "
316+
<< L.getHeader()->getName()
317+
<< ": we don't currently"
318+
" support blocks that are not dead, but will stop "
319+
"being a part of the loop after constant-folding.\n");
320+
return false;
321+
}
322+
323+
// Dump analysis results.
324+
LLVM_DEBUG(dump());
325+
326+
LLVM_DEBUG(dbgs() << "Constant-folding " << FoldCandidates.size()
327+
<< " terminators in loop " << L.getHeader()->getName()
328+
<< "\n");
329+
330+
// Make the actual transforms.
331+
foldTerminators();
332+
333+
#ifndef NDEBUG
334+
// Make sure that we have preserved all data structures after the transform.
335+
DT.verify();
336+
assert(DT.isReachableFromEntry(L.getHeader()));
337+
LI.verify(DT);
338+
#endif
339+
340+
return true;
341+
}
342+
};
343+
344+
/// Turn branches and switches with known constant conditions into unconditional
345+
/// branches.
346+
static bool constantFoldTerminators(Loop &L, DominatorTree &DT, LoopInfo &LI) {
347+
// To keep things simple, only process loops with single latch. We
348+
// canonicalize most loops to this form. We can support multi-latch if needed.
349+
if (!L.getLoopLatch())
350+
return false;
351+
352+
ConstantTerminatorFoldingImpl BranchFolder(L, LI, DT);
353+
return BranchFolder.run();
354+
}
355+
44356
static bool mergeBlocksIntoPredecessors(Loop &L, DominatorTree &DT,
45357
LoopInfo &LI, MemorySSAUpdater *MSSAU) {
46358
bool Changed = false;
@@ -73,6 +385,9 @@ static bool simplifyLoopCFG(Loop &L, DominatorTree &DT, LoopInfo &LI,
73385
ScalarEvolution &SE, MemorySSAUpdater *MSSAU) {
74386
bool Changed = false;
75387

388+
// Constant-fold terminators with known constant conditions.
389+
Changed |= constantFoldTerminators(L, DT, LI);
390+
76391
// Eliminate unconditional branches by merging blocks into their predecessors.
77392
Changed |= mergeBlocksIntoPredecessors(L, DT, LI, MSSAU);
78393

0 commit comments

Comments
 (0)