LLVM  16.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 (BasicBlock *Pred : Preds) {
149  BranchInst *PBI = dyn_cast<BranchInst>(Pred->getTerminator());
150 
151  // All predecessors should terminate with a branch.
152  if (!PBI)
153  return false;
154 
155  BasicBlock *PP = Pred->getSinglePredecessor();
156 
157  if (PBI->isUnconditional()) {
158  // Case 1: Pred (BB3) is an unconditional block, it should
159  // have a single predecessor (BB2) that is also a predecessor
160  // of \param BB (BB4) and should not have address-taken.
161  // There should exist only one such unconditional
162  // branch among the predecessors.
163  if (UnCondBlock || !PP || !Preds.contains(PP) ||
164  Pred->hasAddressTaken())
165  return false;
166 
167  UnCondBlock = Pred;
168  continue;
169  }
170 
171  // Only conditional branches are allowed beyond this point.
172  assert(PBI->isConditional());
173 
174  // Condition's unique use should be the branch instruction.
175  Value *PC = PBI->getCondition();
176  if (!PC || !PC->hasOneUse())
177  return false;
178 
179  if (PP && Preds.count(PP)) {
180  // These are internal condition blocks to be merged from, e.g.,
181  // BB2 in both cases.
182  // Should not be address-taken.
183  if (Pred->hasAddressTaken())
184  return false;
185 
186  // Instructions in the internal condition blocks should be safe
187  // to hoist up.
188  for (BasicBlock::iterator BI = Pred->begin(), BE = PBI->getIterator();
189  BI != BE;) {
190  Instruction *CI = &*BI++;
191  if (isa<PHINode>(CI) || !isSafeToSpeculativelyExecute(CI))
192  return false;
193  }
194  } else {
195  // This is the condition block to be merged into, e.g. BB1 in
196  // both cases.
197  if (FirstCondBlock)
198  return false;
199  FirstCondBlock = Pred;
200  }
201 
202  // Find whether BB is uniformly on the true (or false) path
203  // for all of its predecessors.
204  BasicBlock *PS1 = PBI->getSuccessor(0);
205  BasicBlock *PS2 = PBI->getSuccessor(1);
206  BasicBlock *PS = (PS1 == BB) ? PS2 : PS1;
207  int CIdx = (PS1 == BB) ? 0 : 1;
208 
209  if (Idx == -1)
210  Idx = CIdx;
211  else if (CIdx != Idx)
212  return false;
213 
214  // PS is the successor which is not BB. Check successors to identify
215  // the last conditional branch.
216  if (!Preds.contains(PS)) {
217  // Case 2.
218  LastCondBlock = Pred;
219  } else {
220  // Case 1
221  BranchInst *BPS = dyn_cast<BranchInst>(PS->getTerminator());
222  if (BPS && BPS->isUnconditional()) {
223  // Case 1: PS(BB3) should be an unconditional branch.
224  LastCondBlock = Pred;
225  }
226  }
227  }
228 
229  if (!FirstCondBlock || !LastCondBlock || (FirstCondBlock == LastCondBlock))
230  return false;
231 
232  Instruction *TBB = LastCondBlock->getTerminator();
233  BasicBlock *PS1 = TBB->getSuccessor(0);
234  BasicBlock *PS2 = TBB->getSuccessor(1);
235  BranchInst *PBI1 = dyn_cast<BranchInst>(PS1->getTerminator());
236  BranchInst *PBI2 = dyn_cast<BranchInst>(PS2->getTerminator());
237 
238  // If PS1 does not jump into PS2, but PS2 jumps into PS1,
239  // attempt branch inversion.
240  if (!PBI1 || !PBI1->isUnconditional() ||
241  (PS1->getTerminator()->getSuccessor(0) != PS2)) {
242  // Check whether PS2 jumps into PS1.
243  if (!PBI2 || !PBI2->isUnconditional() ||
244  (PS2->getTerminator()->getSuccessor(0) != PS1))
245  return false;
246 
247  // Do branch inversion.
248  BasicBlock *CurrBlock = LastCondBlock;
249  bool EverChanged = false;
250  for (; CurrBlock != FirstCondBlock;
251  CurrBlock = CurrBlock->getSinglePredecessor()) {
252  auto *BI = cast<BranchInst>(CurrBlock->getTerminator());
253  auto *CI = dyn_cast<CmpInst>(BI->getCondition());
254  if (!CI)
255  continue;
256 
257  CmpInst::Predicate Predicate = CI->getPredicate();
258  // Canonicalize icmp_ne -> icmp_eq, fcmp_one -> fcmp_oeq
260  CI->setPredicate(ICmpInst::getInversePredicate(Predicate));
261  BI->swapSuccessors();
262  EverChanged = true;
263  }
264  }
265  return EverChanged;
266  }
267 
268  // PS1 must have a conditional branch.
269  if (!PBI1 || !PBI1->isUnconditional())
270  return false;
271 
272  // PS2 should not contain PHI node.
273  PHI = dyn_cast<PHINode>(PS2->begin());
274  if (PHI)
275  return false;
276 
277  // Do the transformation.
278  BasicBlock *CB;
279  BranchInst *PBI = cast<BranchInst>(FirstCondBlock->getTerminator());
280  bool Iteration = true;
282  Value *PC = PBI->getCondition();
283 
284  do {
285  CB = PBI->getSuccessor(1 - Idx);
286  // Delete the conditional branch.
287  FirstCondBlock->back().eraseFromParent();
288  FirstCondBlock->splice(FirstCondBlock->end(), CB);
289  PBI = cast<BranchInst>(FirstCondBlock->getTerminator());
290  Value *CC = PBI->getCondition();
291  // Merge conditions.
292  Builder.SetInsertPoint(PBI);
293  Value *NC;
294  if (Idx == 0)
295  // Case 2, use parallel or.
296  NC = Builder.CreateOr(PC, CC);
297  else
298  // Case 1, use parallel and.
299  NC = Builder.CreateAnd(PC, CC);
300 
301  PBI->replaceUsesOfWith(CC, NC);
302  PC = NC;
303  if (CB == LastCondBlock)
304  Iteration = false;
305  // Remove internal conditional branches.
306  CB->dropAllReferences();
307  // make CB unreachable and let downstream to delete the block.
308  new UnreachableInst(CB->getContext(), CB);
309  } while (Iteration);
310 
311  LLVM_DEBUG(dbgs() << "Use parallel and/or in:\n" << *FirstCondBlock);
312  return true;
313 }
314 
315 /// Compare blocks from two if-regions, where \param Head2 is the entry of the
316 /// 2nd if-region. \param Block1 is a block in the 1st if-region to compare.
317 /// \param Block2 is a block in the 2nd if-region to compare. \returns true if
318 /// Block1 and Block2 have identical instructions and do not have
319 /// memory reference alias with Head2.
320 bool FlattenCFGOpt::CompareIfRegionBlock(BasicBlock *Block1, BasicBlock *Block2,
321  BasicBlock *Head2) {
322  Instruction *PTI2 = Head2->getTerminator();
323  Instruction *PBI2 = &Head2->front();
324 
325  // Check whether instructions in Block1 and Block2 are identical
326  // and do not alias with instructions in Head2.
327  BasicBlock::iterator iter1 = Block1->begin();
328  BasicBlock::iterator end1 = Block1->getTerminator()->getIterator();
329  BasicBlock::iterator iter2 = Block2->begin();
330  BasicBlock::iterator end2 = Block2->getTerminator()->getIterator();
331 
332  while (true) {
333  if (iter1 == end1) {
334  if (iter2 != end2)
335  return false;
336  break;
337  }
338 
339  if (!iter1->isIdenticalTo(&*iter2))
340  return false;
341 
342  // Illegal to remove instructions with side effects except
343  // non-volatile stores.
344  if (iter1->mayHaveSideEffects()) {
345  Instruction *CurI = &*iter1;
346  StoreInst *SI = dyn_cast<StoreInst>(CurI);
347  if (!SI || SI->isVolatile())
348  return false;
349  }
350 
351  // For simplicity and speed, data dependency check can be
352  // avoided if read from memory doesn't exist.
353  if (iter1->mayReadFromMemory())
354  return false;
355 
356  if (iter1->mayWriteToMemory()) {
357  for (BasicBlock::iterator BI(PBI2), BE(PTI2); BI != BE; ++BI) {
358  if (BI->mayReadFromMemory() || BI->mayWriteToMemory()) {
359  // Check alias with Head2.
360  if (!AA || !AA->isNoAlias(&*iter1, &*BI))
361  return false;
362  }
363  }
364  }
365  ++iter1;
366  ++iter2;
367  }
368 
369  return true;
370 }
371 
372 /// Check whether \param BB is the merge block of a if-region. If yes, check
373 /// whether there exists an adjacent if-region upstream, the two if-regions
374 /// contain identical instructions and can be legally merged. \returns true if
375 /// the two if-regions are merged.
376 ///
377 /// From:
378 /// if (a)
379 /// statement;
380 /// if (b)
381 /// statement;
382 ///
383 /// To:
384 /// if (a || b)
385 /// statement;
386 ///
387 ///
388 /// And from:
389 /// if (a)
390 /// ;
391 /// else
392 /// statement;
393 /// if (b)
394 /// ;
395 /// else
396 /// statement;
397 ///
398 /// To:
399 /// if (a && b)
400 /// ;
401 /// else
402 /// statement;
403 ///
404 /// We always take the form of the first if-region. This means that if the
405 /// statement in the first if-region, is in the "then-path", while in the second
406 /// if-region it is in the "else-path", then we convert the second to the first
407 /// form, by inverting the condition and the branch successors. The same
408 /// approach goes for the opposite case.
409 bool FlattenCFGOpt::MergeIfRegion(BasicBlock *BB, IRBuilder<> &Builder) {
410  BasicBlock *IfTrue2, *IfFalse2;
411  BranchInst *DomBI2 = GetIfCondition(BB, IfTrue2, IfFalse2);
412  if (!DomBI2)
413  return false;
414  Instruction *CInst2 = dyn_cast<Instruction>(DomBI2->getCondition());
415  if (!CInst2)
416  return false;
417 
418  BasicBlock *SecondEntryBlock = CInst2->getParent();
419  if (SecondEntryBlock->hasAddressTaken())
420  return false;
421 
422  BasicBlock *IfTrue1, *IfFalse1;
423  BranchInst *DomBI1 = GetIfCondition(SecondEntryBlock, IfTrue1, IfFalse1);
424  if (!DomBI1)
425  return false;
426  Instruction *CInst1 = dyn_cast<Instruction>(DomBI1->getCondition());
427  if (!CInst1)
428  return false;
429 
430  BasicBlock *FirstEntryBlock = CInst1->getParent();
431  // Don't die trying to process degenerate/unreachable code.
432  if (FirstEntryBlock == SecondEntryBlock)
433  return false;
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->back().eraseFromParent();
483  FirstEntryBlock->splice(FirstEntryBlock->end(), SecondEntryBlock);
484  BranchInst *PBI = cast<BranchInst>(FirstEntryBlock->getTerminator());
485  assert(PBI->getCondition() == CInst2);
486  BasicBlock *SaveInsertBB = Builder.GetInsertBlock();
487  BasicBlock::iterator SaveInsertPt = Builder.GetInsertPoint();
488  Builder.SetInsertPoint(PBI);
489  if (InvertCond2) {
490  // If this is a "cmp" instruction, only used for branching (and nowhere
491  // else), then we can simply invert the predicate.
492  auto Cmp2 = dyn_cast<CmpInst>(CInst2);
493  if (Cmp2 && Cmp2->hasOneUse())
494  Cmp2->setPredicate(Cmp2->getInversePredicate());
495  else
496  CInst2 = cast<Instruction>(Builder.CreateNot(CInst2));
497  PBI->swapSuccessors();
498  }
499  Value *NC = Builder.CreateBinOp(CombineOp, CInst1, CInst2);
500  PBI->replaceUsesOfWith(CInst2, NC);
501  Builder.SetInsertPoint(SaveInsertBB, SaveInsertPt);
502 
503  // Handle PHI node to replace its predecessors to FirstEntryBlock.
504  for (BasicBlock *Succ : successors(PBI)) {
505  for (PHINode &Phi : Succ->phis()) {
506  for (unsigned i = 0, e = Phi.getNumIncomingValues(); i != e; ++i) {
507  if (Phi.getIncomingBlock(i) == SecondEntryBlock)
508  Phi.setIncomingBlock(i, FirstEntryBlock);
509  }
510  }
511  }
512 
513  // Remove IfTrue1
514  if (IfTrue1 != FirstEntryBlock) {
515  IfTrue1->dropAllReferences();
516  IfTrue1->eraseFromParent();
517  }
518 
519  // Remove IfFalse1
520  if (IfFalse1 != FirstEntryBlock) {
521  IfFalse1->dropAllReferences();
522  IfFalse1->eraseFromParent();
523  }
524 
525  // Remove \param SecondEntryBlock
526  SecondEntryBlock->dropAllReferences();
527  SecondEntryBlock->eraseFromParent();
528  LLVM_DEBUG(dbgs() << "If conditions merged into:\n" << *FirstEntryBlock);
529  return true;
530 }
531 
533  assert(BB && BB->getParent() && "Block not embedded in function!");
534  assert(BB->getTerminator() && "Degenerate basic block encountered!");
535 
537 
538  if (FlattenParallelAndOr(BB, Builder) || MergeIfRegion(BB, Builder))
539  return true;
540  return false;
541 }
542 
543 /// FlattenCFG - This function is used to flatten a CFG. For
544 /// example, it uses parallel-and and parallel-or mode to collapse
545 /// if-conditions and merge if-regions with identical statements.
547  return FlattenCFGOpt(AA).run(BB);
548 }
i
i
Definition: README.txt:29
llvm::BasicBlock::splice
void splice(BasicBlock::iterator ToIt, BasicBlock *FromBB)
Transfer all instructions from FromBB to this basic block at ToIt.
Definition: BasicBlock.h:457
llvm::BasicBlock::end
iterator end()
Definition: BasicBlock.h:308
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::Value::hasOneUse
bool hasOneUse() const
Return true if there is exactly one use of this value.
Definition: Value.h:434
llvm::CmpInst::Predicate
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:719
llvm::BasicBlock::iterator
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:87
PHI
Rewrite undef for PHI
Definition: AMDGPURewriteUndefForPHI.cpp:101
llvm::CmpInst::FCMP_ONE
@ FCMP_ONE
0 1 1 0 True if ordered and operands are unequal
Definition: InstrTypes.h:727
llvm::IRBuilder<>
llvm::CmpInst::ICMP_NE
@ ICMP_NE
not equal
Definition: InstrTypes.h:741
llvm::CmpInst::getInversePredicate
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE,...
Definition: InstrTypes.h:833
ValueTracking.h
Local.h
llvm::BasicBlock::eraseFromParent
SymbolTableList< BasicBlock >::iterator eraseFromParent()
Unlink 'this' from the containing function and delete it.
Definition: BasicBlock.cpp:132
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
llvm::successors
auto successors(MachineBasicBlock *BB)
Definition: MachineSSAContext.h:29
llvm::BasicBlock::getSinglePredecessor
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
Definition: BasicBlock.cpp:285
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:1419
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
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:294
InstrTypes.h
llvm::BasicBlock::begin
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:306
SI
@ SI
Definition: SIInstrInfo.cpp:7966
TBB
const SmallVectorImpl< MachineOperand > MachineBasicBlock * TBB
Definition: RISCVRedundantCopyElimination.cpp:76
llvm::Instruction
Definition: Instruction.h:42
SmallPtrSet.h
llvm::dxil::PointerTypeAnalysis::run
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
Definition: PointerTypeAnalysis.cpp:189
llvm::BranchInst::getCondition
Value * getCondition() const
Definition: Instructions.h:3213
llvm::GetIfCondition
BranchInst * GetIfCondition(BasicBlock *BB, BasicBlock *&IfTrue, BasicBlock *&IfFalse)
Check whether BB is the merge point of a if-region.
Definition: BasicBlockUtils.cpp:1565
llvm::BasicBlock::hasAddressTaken
bool hasAddressTaken() const
Returns true if there are any uses of this basic block other than direct branches,...
Definition: BasicBlock.h:484
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:298
llvm::Instruction::getSuccessor
BasicBlock * getSuccessor(unsigned Idx) const LLVM_READONLY
Return the specified successor. This instruction must be a terminator.
Definition: Instruction.cpp:826
llvm::Instruction::eraseFromParent
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:81
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:53
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:853
Builder
assume Assume Builder
Definition: AssumeBundleBuilder.cpp:651
llvm::BranchInst::isUnconditional
bool isUnconditional() const
Definition: Instructions.h:3210
llvm::FlattenCFG
bool FlattenCFG(BasicBlock *BB, AAResults *AA=nullptr)
This function is used to flatten a CFG.
Definition: FlattenCFG.cpp:546
llvm::ilist_node_impl::getIterator
self_iterator getIterator()
Definition: ilist_node.h:82
CC
auto CC
Definition: RISCVRedundantCopyElimination.cpp:79
llvm::BasicBlock::dropAllReferences
void dropAllReferences()
Cause all subinstructions to "let go" of all the references that said subinstructions are maintaining...
Definition: BasicBlock.cpp:280
llvm::User::replaceUsesOfWith
bool replaceUsesOfWith(Value *From, Value *To)
Replace uses of one Value with another.
Definition: User.cpp:21
llvm::BasicBlock::front
const Instruction & front() const
Definition: BasicBlock.h:318
llvm::Instruction::mayHaveSideEffects
bool mayHaveSideEffects() const LLVM_READONLY
Return true if the instruction may have side effects.
Definition: Instruction.cpp:732
llvm::BasicBlock::getContext
LLVMContext & getContext() const
Get the context in which this basic block lives.
Definition: BasicBlock.cpp:35
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:793
llvm::BasicBlock::back
const Instruction & back() const
Definition: BasicBlock.h:320
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
Instructions.h
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:91
llvm::PHINode
Definition: Instructions.h:2697
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.h:119
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:4768
llvm::BranchInst
Conditional or Unconditional Branch instruction.
Definition: Instructions.h:3132
raw_ostream.h
BasicBlockUtils.h
Value.h
llvm::isSafeToSpeculativelyExecute
bool isSafeToSpeculativelyExecute(const Instruction *I, const Instruction *CtxI=nullptr, AssumptionCache *AC=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:4736
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
Debug.h
llvm::BranchInst::isConditional
bool isConditional() const
Definition: Instructions.h:3211
llvm::BranchInst::getSuccessor
BasicBlock * getSuccessor(unsigned i) const
Definition: Instructions.h:3225