LLVM  14.0.0git
FlattenCFG.cpp
Go to the documentation of this file.
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"
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"
27 #include <cassert>
28 
29 using namespace llvm;
30 
31 #define DEBUG_TYPE "flattencfg"
32 
33 namespace {
34 
35 class 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 
55 public:
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.
136 bool FlattenCFGOpt::FlattenParallelAndOr(BasicBlock *BB, IRBuilder<> &Builder) {
137  PHINode *PHI = dyn_cast<PHINode>(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.
148  for (SmallPtrSetIterator<BasicBlock *> PI = Preds.begin(), PE = Preds.end();
149  PI != PE; ++PI) {
150  BasicBlock *Pred = *PI;
151  BranchInst *PBI = dyn_cast<BranchInst>(Pred->getTerminator());
152 
153  // All predecessors should terminate with a branch.
154  if (!PBI)
155  return false;
156 
157  BasicBlock *PP = Pred->getSinglePredecessor();
158 
159  if (PBI->isUnconditional()) {
160  // Case 1: Pred (BB3) is an unconditional block, it should
161  // have a single predecessor (BB2) that is also a predecessor
162  // of \param BB (BB4) and should not have address-taken.
163  // There should exist only one such unconditional
164  // branch among the predecessors.
165  if (UnCondBlock || !PP || (Preds.count(PP) == 0) ||
166  Pred->hasAddressTaken())
167  return false;
168 
169  UnCondBlock = Pred;
170  continue;
171  }
172 
173  // Only conditional branches are allowed beyond this point.
174  assert(PBI->isConditional());
175 
176  // Condition's unique use should be the branch instruction.
177  Value *PC = PBI->getCondition();
178  if (!PC || !PC->hasOneUse())
179  return false;
180 
181  if (PP && Preds.count(PP)) {
182  // These are internal condition blocks to be merged from, e.g.,
183  // BB2 in both cases.
184  // Should not be address-taken.
185  if (Pred->hasAddressTaken())
186  return false;
187 
188  // Instructions in the internal condition blocks should be safe
189  // to hoist up.
190  for (BasicBlock::iterator BI = Pred->begin(), BE = PBI->getIterator();
191  BI != BE;) {
192  Instruction *CI = &*BI++;
193  if (isa<PHINode>(CI) || !isSafeToSpeculativelyExecute(CI))
194  return false;
195  }
196  } else {
197  // This is the condition block to be merged into, e.g. BB1 in
198  // both cases.
199  if (FirstCondBlock)
200  return false;
201  FirstCondBlock = Pred;
202  }
203 
204  // Find whether BB is uniformly on the true (or false) path
205  // for all of its predecessors.
206  BasicBlock *PS1 = PBI->getSuccessor(0);
207  BasicBlock *PS2 = PBI->getSuccessor(1);
208  BasicBlock *PS = (PS1 == BB) ? PS2 : PS1;
209  int CIdx = (PS1 == BB) ? 0 : 1;
210 
211  if (Idx == -1)
212  Idx = CIdx;
213  else if (CIdx != Idx)
214  return false;
215 
216  // PS is the successor which is not BB. Check successors to identify
217  // the last conditional branch.
218  if (Preds.count(PS) == 0) {
219  // Case 2.
220  LastCondBlock = Pred;
221  } else {
222  // Case 1
223  BranchInst *BPS = dyn_cast<BranchInst>(PS->getTerminator());
224  if (BPS && BPS->isUnconditional()) {
225  // Case 1: PS(BB3) should be an unconditional branch.
226  LastCondBlock = Pred;
227  }
228  }
229  }
230 
231  if (!FirstCondBlock || !LastCondBlock || (FirstCondBlock == LastCondBlock))
232  return false;
233 
234  Instruction *TBB = LastCondBlock->getTerminator();
235  BasicBlock *PS1 = TBB->getSuccessor(0);
236  BasicBlock *PS2 = TBB->getSuccessor(1);
237  BranchInst *PBI1 = dyn_cast<BranchInst>(PS1->getTerminator());
238  BranchInst *PBI2 = dyn_cast<BranchInst>(PS2->getTerminator());
239 
240  // If PS1 does not jump into PS2, but PS2 jumps into PS1,
241  // attempt branch inversion.
242  if (!PBI1 || !PBI1->isUnconditional() ||
243  (PS1->getTerminator()->getSuccessor(0) != PS2)) {
244  // Check whether PS2 jumps into PS1.
245  if (!PBI2 || !PBI2->isUnconditional() ||
246  (PS2->getTerminator()->getSuccessor(0) != PS1))
247  return false;
248 
249  // Do branch inversion.
250  BasicBlock *CurrBlock = LastCondBlock;
251  bool EverChanged = false;
252  for (; CurrBlock != FirstCondBlock;
253  CurrBlock = CurrBlock->getSinglePredecessor()) {
254  auto *BI = cast<BranchInst>(CurrBlock->getTerminator());
255  auto *CI = dyn_cast<CmpInst>(BI->getCondition());
256  if (!CI)
257  continue;
258 
259  CmpInst::Predicate Predicate = CI->getPredicate();
260  // Canonicalize icmp_ne -> icmp_eq, fcmp_one -> fcmp_oeq
262  CI->setPredicate(ICmpInst::getInversePredicate(Predicate));
263  BI->swapSuccessors();
264  EverChanged = true;
265  }
266  }
267  return EverChanged;
268  }
269 
270  // PS1 must have a conditional branch.
271  if (!PBI1 || !PBI1->isUnconditional())
272  return false;
273 
274  // PS2 should not contain PHI node.
275  PHI = dyn_cast<PHINode>(PS2->begin());
276  if (PHI)
277  return false;
278 
279  // Do the transformation.
280  BasicBlock *CB;
281  BranchInst *PBI = cast<BranchInst>(FirstCondBlock->getTerminator());
282  bool Iteration = true;
284  Value *PC = PBI->getCondition();
285 
286  do {
287  CB = PBI->getSuccessor(1 - Idx);
288  // Delete the conditional branch.
289  FirstCondBlock->getInstList().pop_back();
290  FirstCondBlock->getInstList()
291  .splice(FirstCondBlock->end(), CB->getInstList());
292  PBI = cast<BranchInst>(FirstCondBlock->getTerminator());
293  Value *CC = PBI->getCondition();
294  // Merge conditions.
295  Builder.SetInsertPoint(PBI);
296  Value *NC;
297  if (Idx == 0)
298  // Case 2, use parallel or.
299  NC = Builder.CreateOr(PC, CC);
300  else
301  // Case 1, use parallel and.
302  NC = Builder.CreateAnd(PC, CC);
303 
304  PBI->replaceUsesOfWith(CC, NC);
305  PC = NC;
306  if (CB == LastCondBlock)
307  Iteration = false;
308  // Remove internal conditional branches.
309  CB->dropAllReferences();
310  // make CB unreachable and let downstream to delete the block.
311  new UnreachableInst(CB->getContext(), CB);
312  } while (Iteration);
313 
314  LLVM_DEBUG(dbgs() << "Use parallel and/or in:\n" << *FirstCondBlock);
315  return true;
316 }
317 
318 /// Compare blocks from two if-regions, where \param Head2 is the entry of the
319 /// 2nd if-region. \param Block1 is a block in the 1st if-region to compare.
320 /// \param Block2 is a block in the 2nd if-region to compare. \returns true if
321 /// Block1 and Block2 have identical instructions and do not have
322 /// memory reference alias with Head2.
323 bool FlattenCFGOpt::CompareIfRegionBlock(BasicBlock *Block1, BasicBlock *Block2,
324  BasicBlock *Head2) {
325  Instruction *PTI2 = Head2->getTerminator();
326  Instruction *PBI2 = &Head2->front();
327 
328  // Check whether instructions in Block1 and Block2 are identical
329  // and do not alias with instructions in Head2.
330  BasicBlock::iterator iter1 = Block1->begin();
331  BasicBlock::iterator end1 = Block1->getTerminator()->getIterator();
332  BasicBlock::iterator iter2 = Block2->begin();
333  BasicBlock::iterator end2 = Block2->getTerminator()->getIterator();
334 
335  while (true) {
336  if (iter1 == end1) {
337  if (iter2 != end2)
338  return false;
339  break;
340  }
341 
342  if (!iter1->isIdenticalTo(&*iter2))
343  return false;
344 
345  // Illegal to remove instructions with side effects except
346  // non-volatile stores.
347  if (iter1->mayHaveSideEffects()) {
348  Instruction *CurI = &*iter1;
349  StoreInst *SI = dyn_cast<StoreInst>(CurI);
350  if (!SI || SI->isVolatile())
351  return false;
352  }
353 
354  // For simplicity and speed, data dependency check can be
355  // avoided if read from memory doesn't exist.
356  if (iter1->mayReadFromMemory())
357  return false;
358 
359  if (iter1->mayWriteToMemory()) {
360  for (BasicBlock::iterator BI(PBI2), BE(PTI2); BI != BE; ++BI) {
361  if (BI->mayReadFromMemory() || BI->mayWriteToMemory()) {
362  // Check alias with Head2.
363  if (!AA || !AA->isNoAlias(&*iter1, &*BI))
364  return false;
365  }
366  }
367  }
368  ++iter1;
369  ++iter2;
370  }
371 
372  return true;
373 }
374 
375 /// Check whether \param BB is the merge block of a if-region. If yes, check
376 /// whether there exists an adjacent if-region upstream, the two if-regions
377 /// contain identical instructions and can be legally merged. \returns true if
378 /// the two if-regions are merged.
379 ///
380 /// From:
381 /// if (a)
382 /// statement;
383 /// if (b)
384 /// statement;
385 ///
386 /// To:
387 /// if (a || b)
388 /// statement;
389 ///
390 ///
391 /// And from:
392 /// if (a)
393 /// ;
394 /// else
395 /// statement;
396 /// if (b)
397 /// ;
398 /// else
399 /// statement;
400 ///
401 /// To:
402 /// if (a && b)
403 /// ;
404 /// else
405 /// statement;
406 ///
407 /// We always take the form of the first if-region. This means that if the
408 /// statement in the first if-region, is in the "then-path", while in the second
409 /// if-region it is in the "else-path", then we convert the second to the first
410 /// form, by inverting the condition and the branch successors. The same
411 /// approach goes for the opposite case.
412 bool FlattenCFGOpt::MergeIfRegion(BasicBlock *BB, IRBuilder<> &Builder) {
413  BasicBlock *IfTrue2, *IfFalse2;
414  BranchInst *DomBI2 = GetIfCondition(BB, IfTrue2, IfFalse2);
415  if (!DomBI2)
416  return false;
417  Instruction *CInst2 = dyn_cast<Instruction>(DomBI2->getCondition());
418  if (!CInst2)
419  return false;
420 
421  BasicBlock *SecondEntryBlock = CInst2->getParent();
422  if (SecondEntryBlock->hasAddressTaken())
423  return false;
424 
425  BasicBlock *IfTrue1, *IfFalse1;
426  BranchInst *DomBI1 = GetIfCondition(SecondEntryBlock, IfTrue1, IfFalse1);
427  if (!DomBI1)
428  return false;
429  Instruction *CInst1 = dyn_cast<Instruction>(DomBI1->getCondition());
430  if (!CInst1)
431  return false;
432 
433  BasicBlock *FirstEntryBlock = CInst1->getParent();
434 
435  // Either then-path or else-path should be empty.
436  bool InvertCond2 = false;
437  BinaryOperator::BinaryOps CombineOp;
438  if (IfFalse1 == FirstEntryBlock) {
439  // The else-path is empty, so we must use "or" operation to combine the
440  // conditions.
441  CombineOp = BinaryOperator::Or;
442  if (IfFalse2 != SecondEntryBlock) {
443  if (IfTrue2 != SecondEntryBlock)
444  return false;
445 
446  InvertCond2 = true;
447  std::swap(IfTrue2, IfFalse2);
448  }
449 
450  if (!CompareIfRegionBlock(IfTrue1, IfTrue2, SecondEntryBlock))
451  return false;
452  } else if (IfTrue1 == FirstEntryBlock) {
453  // The then-path is empty, so we must use "and" operation to combine the
454  // conditions.
455  CombineOp = BinaryOperator::And;
456  if (IfTrue2 != SecondEntryBlock) {
457  if (IfFalse2 != SecondEntryBlock)
458  return false;
459 
460  InvertCond2 = true;
461  std::swap(IfTrue2, IfFalse2);
462  }
463 
464  if (!CompareIfRegionBlock(IfFalse1, IfFalse2, SecondEntryBlock))
465  return false;
466  } else
467  return false;
468 
469  Instruction *PTI2 = SecondEntryBlock->getTerminator();
470  Instruction *PBI2 = &SecondEntryBlock->front();
471 
472  // Check whether \param SecondEntryBlock has side-effect and is safe to
473  // speculate.
474  for (BasicBlock::iterator BI(PBI2), BE(PTI2); BI != BE; ++BI) {
475  Instruction *CI = &*BI;
476  if (isa<PHINode>(CI) || CI->mayHaveSideEffects() ||
478  return false;
479  }
480 
481  // Merge \param SecondEntryBlock into \param FirstEntryBlock.
482  FirstEntryBlock->getInstList().pop_back();
483  FirstEntryBlock->getInstList()
484  .splice(FirstEntryBlock->end(), SecondEntryBlock->getInstList());
485  BranchInst *PBI = cast<BranchInst>(FirstEntryBlock->getTerminator());
486  assert(PBI->getCondition() == CInst2);
487  BasicBlock *SaveInsertBB = Builder.GetInsertBlock();
488  BasicBlock::iterator SaveInsertPt = Builder.GetInsertPoint();
489  Builder.SetInsertPoint(PBI);
490  if (InvertCond2) {
491  // If this is a "cmp" instruction, only used for branching (and nowhere
492  // else), then we can simply invert the predicate.
493  auto Cmp2 = dyn_cast<CmpInst>(CInst2);
494  if (Cmp2 && Cmp2->hasOneUse())
495  Cmp2->setPredicate(Cmp2->getInversePredicate());
496  else
497  CInst2 = cast<Instruction>(Builder.CreateNot(CInst2));
498  PBI->swapSuccessors();
499  }
500  Value *NC = Builder.CreateBinOp(CombineOp, CInst1, CInst2);
501  PBI->replaceUsesOfWith(CInst2, NC);
502  Builder.SetInsertPoint(SaveInsertBB, SaveInsertPt);
503 
504  // Handle PHI node to replace its predecessors to FirstEntryBlock.
505  for (BasicBlock *Succ : successors(PBI)) {
506  for (PHINode &Phi : Succ->phis()) {
507  for (unsigned i = 0, e = Phi.getNumIncomingValues(); i != e; ++i) {
508  if (Phi.getIncomingBlock(i) == SecondEntryBlock)
509  Phi.setIncomingBlock(i, FirstEntryBlock);
510  }
511  }
512  }
513 
514  // Remove IfTrue1
515  if (IfTrue1 != FirstEntryBlock) {
516  IfTrue1->dropAllReferences();
517  IfTrue1->eraseFromParent();
518  }
519 
520  // Remove IfFalse1
521  if (IfFalse1 != FirstEntryBlock) {
522  IfFalse1->dropAllReferences();
523  IfFalse1->eraseFromParent();
524  }
525 
526  // Remove \param SecondEntryBlock
527  SecondEntryBlock->dropAllReferences();
528  SecondEntryBlock->eraseFromParent();
529  LLVM_DEBUG(dbgs() << "If conditions merged into:\n" << *FirstEntryBlock);
530  return true;
531 }
532 
533 bool FlattenCFGOpt::run(BasicBlock *BB) {
534  assert(BB && BB->getParent() && "Block not embedded in function!");
535  assert(BB->getTerminator() && "Degenerate basic block encountered!");
536 
538 
539  if (FlattenParallelAndOr(BB, Builder) || MergeIfRegion(BB, Builder))
540  return true;
541  return false;
542 }
543 
544 /// FlattenCFG - This function is used to flatten a CFG. For
545 /// example, it uses parallel-and and parallel-or mode to collapse
546 /// if-conditions and merge if-regions with identical statements.
548  return FlattenCFGOpt(AA).run(BB);
549 }
i
i
Definition: README.txt:29
llvm::BasicBlock::end
iterator end()
Definition: BasicBlock.h:298
llvm
This file implements support for optimizing divisions by a constant.
Definition: AllocatorList.h:23
llvm::Value::hasOneUse
bool hasOneUse() const
Return true if there is exactly one use of this value.
Definition: Value.h:435
llvm::CmpInst::Predicate
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:720
llvm::BasicBlock::iterator
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:90
llvm::isSafeToSpeculativelyExecute
bool isSafeToSpeculativelyExecute(const Value *V, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr)
Return true if the instruction does not have any effects besides calculating the result and does not ...
Definition: ValueTracking.cpp:4609
llvm::CmpInst::FCMP_ONE
@ FCMP_ONE
0 1 1 0 True if ordered and operands are unequal
Definition: InstrTypes.h:728
llvm::IRBuilder<>
llvm::CmpInst::ICMP_NE
@ ICMP_NE
not equal
Definition: InstrTypes.h:742
llvm::CmpInst::getInversePredicate
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE,...
Definition: InstrTypes.h:820
ValueTracking.h
Local.h
llvm::BasicBlock::eraseFromParent
SymbolTableList< BasicBlock >::iterator eraseFromParent()
Unlink 'this' from the containing function and delete it.
Definition: BasicBlock.cpp:133
llvm::SmallPtrSetIterator
SmallPtrSetIterator - This implements a const_iterator for SmallPtrSet.
Definition: SmallPtrSet.h:266
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:449
llvm::BasicBlock::getSinglePredecessor
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
Definition: BasicBlock.cpp:268
llvm::successors
succ_range successors(Instruction *I)
Definition: CFG.h:262
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
llvm::BranchInst::swapSuccessors
void swapSuccessors()
Swap the successors of this branch instruction.
Definition: Instructions.cpp:1307
llvm::Instruction::mayHaveSideEffects
bool mayHaveSideEffects() const
Return true if the instruction may have side effects.
Definition: Instruction.cpp:683
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
AliasAnalysis.h
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
Instruction.h
llvm::AAResults
Definition: AliasAnalysis.h:508
InstrTypes.h
llvm::BasicBlock::begin
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:296
llvm::Instruction
Definition: Instruction.h:45
SmallPtrSet.h
llvm::Instruction::getSuccessor
BasicBlock * getSuccessor(unsigned Idx) const
Return the specified successor. This instruction must be a terminator.
Definition: Instruction.cpp:777
llvm::BranchInst::getCondition
Value * getCondition() const
Definition: Instructions.h:3149
llvm::GetIfCondition
BranchInst * GetIfCondition(BasicBlock *BB, BasicBlock *&IfTrue, BasicBlock *&IfFalse)
Check whether BB is the merge point of a if-region.
Definition: BasicBlockUtils.cpp:1459
llvm::BasicBlock::hasAddressTaken
bool hasAddressTaken() const
Returns true if there are any uses of this basic block other than direct branches,...
Definition: BasicBlock.h:448
BasicBlock.h
llvm::PPC::Predicate
Predicate
Predicate - These are "(BI << 5) | BO" for various predicates.
Definition: PPCPredicates.h:26
llvm::StoreInst
An instruction for storing to memory.
Definition: Instructions.h:304
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
IRBuilder.h
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
std::swap
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:840
SI
StandardInstrumentations SI(Debug, VerifyEach)
llvm::User::replaceUsesOfWith
void replaceUsesOfWith(Value *From, Value *To)
Replace uses of one Value with another.
Definition: User.cpp:21
Builder
assume Assume Builder
Definition: AssumeBundleBuilder.cpp:650
llvm::BranchInst::isUnconditional
bool isUnconditional() const
Definition: Instructions.h:3146
llvm::FlattenCFG
bool FlattenCFG(BasicBlock *BB, AAResults *AA=nullptr)
This function is used to flatten a CFG.
Definition: FlattenCFG.cpp:547
llvm::ilist_node_impl::getIterator
self_iterator getIterator()
Definition: ilist_node.h:81
llvm::BasicBlock::dropAllReferences
void dropAllReferences()
Cause all subinstructions to "let go" of all the references that said subinstructions are maintaining...
Definition: BasicBlock.cpp:263
llvm::BasicBlock::getTerminator
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.cpp:152
llvm::BasicBlock::front
const Instruction & front() const
Definition: BasicBlock.h:308
llvm::BasicBlock::getContext
LLVMContext & getContext() const
Get the context in which this basic block lives.
Definition: BasicBlock.cpp:36
NC
#define NC
Definition: regutils.h:42
llvm::pred_end
Interval::pred_iterator pred_end(Interval *I)
Definition: Interval.h:112
Casting.h
llvm::Instruction::BinaryOps
BinaryOps
Definition: Instruction.h:785
llvm::pred_begin
Interval::pred_iterator pred_begin(Interval *I)
pred_begin/pred_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:109
llvm::BasicBlock::getInstList
const InstListType & getInstList() const
Return the underlying instruction list container.
Definition: BasicBlock.h:363
Instructions.h
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:94
llvm::PHINode
Definition: Instructions.h:2633
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::UnreachableInst
This function has undefined behavior.
Definition: Instructions.h:4713
llvm::BranchInst
Conditional or Unconditional Branch instruction.
Definition: Instructions.h:3068
raw_ostream.h
BasicBlockUtils.h
Value.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
Debug.h
llvm::BranchInst::isConditional
bool isConditional() const
Definition: Instructions.h:3147
llvm::BranchInst::getSuccessor
BasicBlock * getSuccessor(unsigned i) const
Definition: Instructions.h:3161