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