1//===- FlatternCFG.cpp - Code to perform CFG flattening -------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// Reduce conditional branches in CFG.
10//
11//===----------------------------------------------------------------------===//
12
13#include "llvm/ADT/SmallPtrSet.h"
14#include "llvm/Analysis/AliasAnalysis.h"
15#include "llvm/Analysis/ValueTracking.h"
16#include "llvm/IR/BasicBlock.h"
17#include "llvm/IR/IRBuilder.h"
18#include "llvm/IR/InstrTypes.h"
19#include "llvm/IR/Instruction.h"
20#include "llvm/IR/Instructions.h"
21#include "llvm/IR/ProfDataUtils.h"
22#include "llvm/IR/Value.h"
23#include "llvm/Support/Casting.h"
24#include "llvm/Support/Debug.h"
25#include "llvm/Support/raw_ostream.h"
26#include "llvm/Transforms/Utils/BasicBlockUtils.h"
27#include "llvm/Transforms/Utils/Local.h"
28#include <cassert>
29
30using namespace llvm;
31
32#define DEBUG_TYPE "flatten-cfg"
33
34namespace {
35
36class FlattenCFGOpt {
37 AliasAnalysis *AA;
38
39 /// Use parallel-and or parallel-or to generate conditions for
40 /// conditional branches.
41 bool FlattenParallelAndOr(BasicBlock *BB, IRBuilder<> &Builder);
42
43 /// If \param BB is the merge block of an if-region, attempt to merge
44 /// the if-region with an adjacent if-region upstream if two if-regions
45 /// contain identical instructions.
46 bool MergeIfRegion(BasicBlock *BB, IRBuilder<> &Builder);
47
48 /// Compare a pair of blocks: \p Block1 and \p Block2, which
49 /// are from two if-regions, where \p Head2 is the entry block of the 2nd
50 /// if-region. \returns true if \p Block1 and \p Block2 contain identical
51 /// instructions, and have no memory reference alias with \p Head2.
52 /// This is used as a legality check for merging if-regions.
53 bool CompareIfRegionBlock(BasicBlock *Block1, BasicBlock *Block2,
54 BasicBlock *Head2);
55
56public:
57 FlattenCFGOpt(AliasAnalysis *AA) : AA(AA) {}
58
59 bool run(BasicBlock *BB);
60};
61
62} // end anonymous namespace
63
64/// If \param [in] BB has more than one predecessor that is a conditional
65/// branch, attempt to use parallel and/or for the branch condition. \returns
66/// true on success.
67///
68/// Before:
69/// ......
70/// %cmp10 = fcmp une float %tmp1, %tmp2
71/// br i1 %cmp10, label %if.then, label %lor.rhs
72///
73/// lor.rhs:
74/// ......
75/// %cmp11 = fcmp une float %tmp3, %tmp4
76/// br i1 %cmp11, label %if.then, label %ifend
77///
78/// if.end: // the merge block
79/// ......
80///
81/// if.then: // has two predecessors, both of them contains conditional branch.
82/// ......
83/// br label %if.end;
84///
85/// After:
86/// ......
87/// %cmp10 = fcmp une float %tmp1, %tmp2
88/// ......
89/// %cmp11 = fcmp une float %tmp3, %tmp4
90/// %cmp12 = or i1 %cmp10, %cmp11 // parallel-or mode.
91/// br i1 %cmp12, label %if.then, label %ifend
92///
93/// if.end:
94/// ......
95///
96/// if.then:
97/// ......
98/// br label %if.end;
99///
100/// Current implementation handles two cases.
101/// Case 1: BB is on the else-path.
102///
103/// BB1
104/// / |
105/// BB2 |
106/// / \ |
107/// BB3 \ | where, BB1, BB2 contain conditional branches.
108/// \ | / BB3 contains unconditional branch.
109/// \ | / BB4 corresponds to BB which is also the merge.
110/// BB => BB4
111///
112///
113/// Corresponding source code:
114///
115/// if (a == b && c == d)
116/// statement; // BB3
117///
118/// Case 2: BB is on the then-path.
119///
120/// BB1
121/// / |
122/// | BB2
123/// \ / | where BB1, BB2 contain conditional branches.
124/// BB => BB3 | BB3 contains unconditiona branch and corresponds
125/// \ / to BB. BB4 is the merge.
126/// BB4
127///
128/// Corresponding source code:
129///
130/// if (a == b || c == d)
131/// statement; // BB3
132///
133/// In both cases, BB is the common successor of conditional branches.
134/// In Case 1, BB (BB4) has an unconditional branch (BB3) as
135/// its predecessor. In Case 2, BB (BB3) only has conditional branches
136/// as its predecessors.
137bool FlattenCFGOpt::FlattenParallelAndOr(BasicBlock *BB, IRBuilder<> &Builder) {
138 PHINode *PHI = dyn_cast<PHINode>(Val: BB->begin());
139 if (PHI)
140 return false; // For simplicity, avoid cases containing PHI nodes.
141
142 BasicBlock *LastCondBlock = nullptr;
143 BasicBlock *FirstCondBlock = nullptr;
144 BasicBlock *UnCondBlock = nullptr;
145 int Idx = -1;
146
147 // Check predecessors of \param BB.
148 SmallPtrSet<BasicBlock *, 16> Preds(llvm::from_range, predecessors(BB));
149 for (BasicBlock *Pred : Preds) {
150 BasicBlock *PP = Pred->getSinglePredecessor();
151
152 if (isa<UncondBrInst>(Val: Pred->getTerminator())) {
153 // Case 1: Pred (BB3) is an unconditional block, it should
154 // have a single predecessor (BB2) that is also a predecessor
155 // of \param BB (BB4) and should not have address-taken.
156 // There should exist only one such unconditional
157 // branch among the predecessors.
158 if (UnCondBlock || !PP || !Preds.contains(Ptr: PP) ||
159 Pred->hasAddressTaken())
160 return false;
161
162 UnCondBlock = Pred;
163 continue;
164 }
165
166 // Only conditional branches are allowed beyond this point.
167 CondBrInst *PBI = dyn_cast<CondBrInst>(Val: Pred->getTerminator());
168 if (!PBI)
169 return false;
170
171 // Condition's unique use should be the branch instruction.
172 Value *PC = PBI->getCondition();
173 if (!PC || !PC->hasOneUse())
174 return false;
175
176 if (PP && Preds.count(Ptr: PP)) {
177 // These are internal condition blocks to be merged from, e.g.,
178 // BB2 in both cases.
179 // Should not be address-taken.
180 if (Pred->hasAddressTaken())
181 return false;
182
183 // Instructions in the internal condition blocks should be safe
184 // to hoist up.
185 for (BasicBlock::iterator BI = Pred->begin(), BE = PBI->getIterator();
186 BI != BE;) {
187 Instruction *CI = &*BI++;
188 if (isa<PHINode>(Val: CI) || !isSafeToSpeculativelyExecute(I: CI))
189 return false;
190 }
191 } else {
192 // This is the condition block to be merged into, e.g. BB1 in
193 // both cases.
194 if (FirstCondBlock)
195 return false;
196 FirstCondBlock = Pred;
197 }
198
199 // Find whether BB is uniformly on the true (or false) path
200 // for all of its predecessors.
201 BasicBlock *PS1 = PBI->getSuccessor(i: 0);
202 BasicBlock *PS2 = PBI->getSuccessor(i: 1);
203 BasicBlock *PS = (PS1 == BB) ? PS2 : PS1;
204 int CIdx = (PS1 == BB) ? 0 : 1;
205
206 if (Idx == -1)
207 Idx = CIdx;
208 else if (CIdx != Idx)
209 return false;
210
211 // PS is the successor which is not BB. Check successors to identify
212 // the last conditional branch.
213 if (!Preds.contains(Ptr: PS)) {
214 // Case 2.
215 LastCondBlock = Pred;
216 } else if (isa<UncondBrInst>(Val: PS->getTerminator())) {
217 // Case 1: PS(BB3) should be an unconditional branch.
218 LastCondBlock = Pred;
219 }
220 }
221
222 if (!FirstCondBlock || !LastCondBlock || (FirstCondBlock == LastCondBlock))
223 return false;
224
225 Instruction *TBB = LastCondBlock->getTerminator();
226 BasicBlock *PS1 = TBB->getSuccessor(Idx: 0);
227 BasicBlock *PS2 = TBB->getSuccessor(Idx: 1);
228 UncondBrInst *PBI1 = dyn_cast<UncondBrInst>(Val: PS1->getTerminator());
229 UncondBrInst *PBI2 = dyn_cast<UncondBrInst>(Val: PS2->getTerminator());
230
231 // If PS1 does not jump into PS2, but PS2 jumps into PS1,
232 // attempt branch inversion.
233 if (!PBI1 || (PS1->getTerminator()->getSuccessor(Idx: 0) != PS2)) {
234 // Check whether PS2 jumps into PS1.
235 if (!PBI2 || (PS2->getTerminator()->getSuccessor(Idx: 0) != PS1))
236 return false;
237
238 // Do branch inversion.
239 BasicBlock *CurrBlock = LastCondBlock;
240 bool EverChanged = false;
241 for (; CurrBlock != FirstCondBlock;
242 CurrBlock = CurrBlock->getSinglePredecessor()) {
243 auto *BI = cast<CondBrInst>(Val: CurrBlock->getTerminator());
244 auto *CI = dyn_cast<CmpInst>(Val: BI->getCondition());
245 if (!CI)
246 continue;
247
248 CmpInst::Predicate Predicate = CI->getPredicate();
249 // Canonicalize icmp_ne -> icmp_eq, fcmp_one -> fcmp_oeq
250 if ((Predicate == CmpInst::ICMP_NE) || (Predicate == CmpInst::FCMP_ONE)) {
251 CI->setPredicate(ICmpInst::getInversePredicate(pred: Predicate));
252 BI->swapSuccessors();
253 EverChanged = true;
254 }
255 }
256 return EverChanged;
257 }
258
259 // PS1 must have a conditional branch.
260 if (!PBI1)
261 return false;
262
263 // PS2 should not contain PHI node.
264 PHI = dyn_cast<PHINode>(Val: PS2->begin());
265 if (PHI)
266 return false;
267
268 // Do the transformation.
269 BasicBlock *CB;
270 CondBrInst *PBI = cast<CondBrInst>(Val: FirstCondBlock->getTerminator());
271 bool Iteration = true;
272 IRBuilder<>::InsertPointGuard Guard(Builder);
273 Value *PC = PBI->getCondition();
274
275 do {
276 CB = PBI->getSuccessor(i: 1 - Idx);
277 // Delete the conditional branch.
278 FirstCondBlock->back().eraseFromParent();
279 FirstCondBlock->splice(ToIt: FirstCondBlock->end(), FromBB: CB);
280 PBI = cast<CondBrInst>(Val: FirstCondBlock->getTerminator());
281 Value *CC = PBI->getCondition();
282 // Merge conditions.
283 Builder.SetInsertPoint(PBI);
284 Value *NC;
285 if (Idx == 0)
286 // Case 2, use parallel or.
287 NC = Builder.CreateLogicalOr(Cond1: PC, Cond2: CC);
288 else
289 // Case 1, use parallel and.
290 NC = Builder.CreateLogicalAnd(Cond1: PC, Cond2: CC);
291
292 if (SelectInst *SI = dyn_cast<SelectInst>(Val: NC))
293 setExplicitlyUnknownBranchWeightsIfProfiled(I&: *SI, DEBUG_TYPE);
294
295 PBI->replaceUsesOfWith(From: CC, To: NC);
296 PC = NC;
297 if (CB == LastCondBlock)
298 Iteration = false;
299 // Remove internal conditional branches.
300 CB->dropAllReferences();
301 // make CB unreachable and let downstream to delete the block.
302 new UnreachableInst(CB->getContext(), CB);
303 } while (Iteration);
304
305 LLVM_DEBUG(dbgs() << "Use parallel and/or in:\n" << *FirstCondBlock);
306 return true;
307}
308
309/// Compare blocks from two if-regions, where \param Head2 is the entry of the
310/// 2nd if-region. \param Block1 is a block in the 1st if-region to compare.
311/// \param Block2 is a block in the 2nd if-region to compare. \returns true if
312/// Block1 and Block2 have identical instructions and do not have
313/// memory reference alias with Head2.
314bool FlattenCFGOpt::CompareIfRegionBlock(BasicBlock *Block1, BasicBlock *Block2,
315 BasicBlock *Head2) {
316 Instruction *PTI2 = Head2->getTerminator();
317 Instruction *PBI2 = &Head2->front();
318
319 // Check whether instructions in Block1 and Block2 are identical
320 // and do not alias with instructions in Head2.
321 BasicBlock::iterator iter1 = Block1->begin();
322 BasicBlock::iterator end1 = Block1->getTerminator()->getIterator();
323 BasicBlock::iterator iter2 = Block2->begin();
324 BasicBlock::iterator end2 = Block2->getTerminator()->getIterator();
325
326 while (true) {
327 if (iter1 == end1) {
328 if (iter2 != end2)
329 return false;
330 break;
331 }
332
333 if (!iter1->isIdenticalTo(I: &*iter2))
334 return false;
335
336 // Illegal to remove instructions with side effects except
337 // non-volatile stores.
338 if (iter1->mayHaveSideEffects()) {
339 Instruction *CurI = &*iter1;
340 StoreInst *SI = dyn_cast<StoreInst>(Val: CurI);
341 if (!SI || SI->isVolatile())
342 return false;
343 }
344
345 // For simplicity and speed, data dependency check can be
346 // avoided if read from memory doesn't exist.
347 if (iter1->mayReadFromMemory())
348 return false;
349
350 if (iter1->mayWriteToMemory()) {
351 for (BasicBlock::iterator BI(PBI2), BE(PTI2); BI != BE; ++BI) {
352 if (BI->mayReadFromMemory() || BI->mayWriteToMemory()) {
353 // Check whether iter1 and BI may access the same memory location.
354 if (!AA || AA->getModRefInfo(I1: &*iter1, I2: &*BI) != ModRefInfo::NoModRef)
355 return false;
356 }
357 }
358 }
359 ++iter1;
360 ++iter2;
361 }
362
363 return true;
364}
365
366/// Check whether \param BB is the merge block of a if-region. If yes, check
367/// whether there exists an adjacent if-region upstream, the two if-regions
368/// contain identical instructions and can be legally merged. \returns true if
369/// the two if-regions are merged.
370///
371/// From:
372/// if (a)
373/// statement;
374/// if (b)
375/// statement;
376///
377/// To:
378/// if (a || b)
379/// statement;
380///
381///
382/// And from:
383/// if (a)
384/// ;
385/// else
386/// statement;
387/// if (b)
388/// ;
389/// else
390/// statement;
391///
392/// To:
393/// if (a && b)
394/// ;
395/// else
396/// statement;
397///
398/// We always take the form of the first if-region. This means that if the
399/// statement in the first if-region, is in the "then-path", while in the second
400/// if-region it is in the "else-path", then we convert the second to the first
401/// form, by inverting the condition and the branch successors. The same
402/// approach goes for the opposite case.
403bool FlattenCFGOpt::MergeIfRegion(BasicBlock *BB, IRBuilder<> &Builder) {
404 // We cannot merge the if-region if the merge point has phi nodes.
405 if (isa<PHINode>(Val: BB->front()))
406 return false;
407
408 BasicBlock *IfTrue2, *IfFalse2;
409 CondBrInst *DomBI2 = GetIfCondition(BB, IfTrue&: IfTrue2, IfFalse&: IfFalse2);
410 if (!DomBI2)
411 return false;
412 Instruction *CInst2 = dyn_cast<Instruction>(Val: DomBI2->getCondition());
413 if (!CInst2)
414 return false;
415
416 BasicBlock *SecondEntryBlock = CInst2->getParent();
417 if (SecondEntryBlock->hasAddressTaken())
418 return false;
419
420 BasicBlock *IfTrue1, *IfFalse1;
421 CondBrInst *DomBI1 = GetIfCondition(BB: SecondEntryBlock, IfTrue&: IfTrue1, IfFalse&: IfFalse1);
422 if (!DomBI1)
423 return false;
424 Instruction *CInst1 = dyn_cast<Instruction>(Val: DomBI1->getCondition());
425 if (!CInst1)
426 return false;
427
428 BasicBlock *FirstEntryBlock = CInst1->getParent();
429 // Don't die trying to process degenerate/unreachable code.
430 if (FirstEntryBlock == SecondEntryBlock)
431 return false;
432
433 // Either then-path or else-path should be empty.
434 bool InvertCond2 = false;
435 BinaryOperator::BinaryOps CombineOp;
436 if (IfFalse1 == FirstEntryBlock) {
437 // The else-path is empty, so we must use "or" operation to combine the
438 // conditions.
439 CombineOp = BinaryOperator::Or;
440 if (IfFalse2 != SecondEntryBlock) {
441 if (IfTrue2 != SecondEntryBlock)
442 return false;
443
444 InvertCond2 = true;
445 std::swap(a&: IfTrue2, b&: IfFalse2);
446 }
447
448 if (!CompareIfRegionBlock(Block1: IfTrue1, Block2: IfTrue2, Head2: SecondEntryBlock))
449 return false;
450 } else if (IfTrue1 == FirstEntryBlock) {
451 // The then-path is empty, so we must use "and" operation to combine the
452 // conditions.
453 CombineOp = BinaryOperator::And;
454 if (IfTrue2 != SecondEntryBlock) {
455 if (IfFalse2 != SecondEntryBlock)
456 return false;
457
458 InvertCond2 = true;
459 std::swap(a&: IfTrue2, b&: IfFalse2);
460 }
461
462 if (!CompareIfRegionBlock(Block1: IfFalse1, Block2: IfFalse2, Head2: SecondEntryBlock))
463 return false;
464 } else
465 return false;
466
467 Instruction *PTI2 = SecondEntryBlock->getTerminator();
468 Instruction *PBI2 = &SecondEntryBlock->front();
469
470 // Check whether \param SecondEntryBlock has side-effect and is safe to
471 // speculate.
472 for (BasicBlock::iterator BI(PBI2), BE(PTI2); BI != BE; ++BI) {
473 Instruction *CI = &*BI;
474 if (isa<PHINode>(Val: CI) || CI->mayHaveSideEffects() ||
475 !isSafeToSpeculativelyExecute(I: CI))
476 return false;
477 }
478
479 // Merge \param SecondEntryBlock into \param FirstEntryBlock.
480 FirstEntryBlock->back().eraseFromParent();
481 FirstEntryBlock->splice(ToIt: FirstEntryBlock->end(), FromBB: SecondEntryBlock);
482 CondBrInst *PBI = cast<CondBrInst>(Val: FirstEntryBlock->getTerminator());
483 assert(PBI->getCondition() == CInst2);
484 BasicBlock *SaveInsertBB = Builder.GetInsertBlock();
485 BasicBlock::iterator SaveInsertPt = Builder.GetInsertPoint();
486 Builder.SetInsertPoint(PBI);
487 if (InvertCond2) {
488 InvertBranch(PBI, Builder);
489 }
490 Value *NC = Builder.CreateBinOp(Opc: CombineOp, LHS: CInst1, RHS: PBI->getCondition());
491 PBI->replaceUsesOfWith(From: PBI->getCondition(), To: NC);
492 Builder.SetInsertPoint(TheBB: SaveInsertBB, IP: SaveInsertPt);
493
494 // Remove IfTrue1
495 if (IfTrue1 != FirstEntryBlock) {
496 IfTrue1->dropAllReferences();
497 IfTrue1->eraseFromParent();
498 }
499
500 // Remove IfFalse1
501 if (IfFalse1 != FirstEntryBlock) {
502 IfFalse1->dropAllReferences();
503 IfFalse1->eraseFromParent();
504 }
505
506 // Remove \param SecondEntryBlock
507 SecondEntryBlock->dropAllReferences();
508 SecondEntryBlock->eraseFromParent();
509 LLVM_DEBUG(dbgs() << "If conditions merged into:\n" << *FirstEntryBlock);
510 return true;
511}
512
513bool FlattenCFGOpt::run(BasicBlock *BB) {
514 assert(BB && BB->getParent() && "Block not embedded in function!");
515 assert(BB->getTerminator() && "Degenerate basic block encountered!");
516
517 IRBuilder<> Builder(BB);
518
519 if (FlattenParallelAndOr(BB, Builder) || MergeIfRegion(BB, Builder))
520 return true;
521 return false;
522}
523
524/// FlattenCFG - This function is used to flatten a CFG. For
525/// example, it uses parallel-and and parallel-or mode to collapse
526/// if-conditions and merge if-regions with identical statements.
527bool llvm::FlattenCFG(BasicBlock *BB, AAResults *AA) {
528 return FlattenCFGOpt(AA).run(BB);
529}
530