LLVM  14.0.0git
CodeMoverUtils.cpp
Go to the documentation of this file.
1 //===- CodeMoverUtils.cpp - CodeMover Utilities ----------------------------==//
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 // This family of functions perform movements on basic blocks, and instructions
10 // contained within a function.
11 //
12 //===----------------------------------------------------------------------===//
13 
15 #include "llvm/ADT/Optional.h"
16 #include "llvm/ADT/Statistic.h"
20 #include "llvm/IR/Dominators.h"
21 
22 using namespace llvm;
23 
24 #define DEBUG_TYPE "codemover-utils"
25 
26 STATISTIC(HasDependences,
27  "Cannot move across instructions that has memory dependences");
28 STATISTIC(MayThrowException, "Cannot move across instructions that may throw");
29 STATISTIC(NotControlFlowEquivalent,
30  "Instructions are not control flow equivalent");
31 STATISTIC(NotMovedPHINode, "Movement of PHINodes are not supported");
32 STATISTIC(NotMovedTerminator, "Movement of Terminator are not supported");
33 
34 namespace {
35 /// Represent a control condition. A control condition is a condition of a
36 /// terminator to decide which successors to execute. The pointer field
37 /// represents the address of the condition of the terminator. The integer field
38 /// is a bool, it is true when the basic block is executed when V is true. For
39 /// example, `br %cond, bb0, bb1` %cond is a control condition of bb0 with the
40 /// integer field equals to true, while %cond is a control condition of bb1 with
41 /// the integer field equals to false.
42 using ControlCondition = PointerIntPair<Value *, 1, bool>;
43 #ifndef NDEBUG
44 raw_ostream &operator<<(raw_ostream &OS, const ControlCondition &C) {
45  OS << "[" << *C.getPointer() << ", " << (C.getInt() ? "true" : "false")
46  << "]";
47  return OS;
48 }
49 #endif
50 
51 /// Represent a set of control conditions required to execute ToBB from FromBB.
52 class ControlConditions {
53  using ConditionVectorTy = SmallVector<ControlCondition, 6>;
54 
55  /// A SmallVector of control conditions.
56  ConditionVectorTy Conditions;
57 
58 public:
59  /// Return a ControlConditions which stores all conditions required to execute
60  /// \p BB from \p Dominator. If \p MaxLookup is non-zero, it limits the
61  /// number of conditions to collect. Return None if not all conditions are
62  /// collected successfully, or we hit the limit.
63  static const Optional<ControlConditions>
64  collectControlConditions(const BasicBlock &BB, const BasicBlock &Dominator,
65  const DominatorTree &DT,
66  const PostDominatorTree &PDT,
67  unsigned MaxLookup = 6);
68 
69  /// Return true if there exists no control conditions required to execute ToBB
70  /// from FromBB.
71  bool isUnconditional() const { return Conditions.empty(); }
72 
73  /// Return a constant reference of Conditions.
74  const ConditionVectorTy &getControlConditions() const { return Conditions; }
75 
76  /// Add \p V as one of the ControlCondition in Condition with IsTrueCondition
77  /// equals to \p True. Return true if inserted successfully.
78  bool addControlCondition(ControlCondition C);
79 
80  /// Return true if for all control conditions in Conditions, there exists an
81  /// equivalent control condition in \p Other.Conditions.
82  bool isEquivalent(const ControlConditions &Other) const;
83 
84  /// Return true if \p C1 and \p C2 are equivalent.
85  static bool isEquivalent(const ControlCondition &C1,
86  const ControlCondition &C2);
87 
88 private:
89  ControlConditions() = default;
90 
91  static bool isEquivalent(const Value &V1, const Value &V2);
92  static bool isInverse(const Value &V1, const Value &V2);
93 };
94 } // namespace
95 
96 static bool domTreeLevelBefore(DominatorTree *DT, const Instruction *InstA,
97  const Instruction *InstB) {
98  // Use ordered basic block in case the 2 instructions are in the same
99  // block.
100  if (InstA->getParent() == InstB->getParent())
101  return InstA->comesBefore(InstB);
102 
103  DomTreeNode *DA = DT->getNode(InstA->getParent());
104  DomTreeNode *DB = DT->getNode(InstB->getParent());
105  return DA->getLevel() < DB->getLevel();
106 }
107 
108 const Optional<ControlConditions> ControlConditions::collectControlConditions(
109  const BasicBlock &BB, const BasicBlock &Dominator, const DominatorTree &DT,
110  const PostDominatorTree &PDT, unsigned MaxLookup) {
111  assert(DT.dominates(&Dominator, &BB) && "Expecting Dominator to dominate BB");
112 
113  ControlConditions Conditions;
114  unsigned NumConditions = 0;
115 
116  // BB is executed unconditional from itself.
117  if (&Dominator == &BB)
118  return Conditions;
119 
120  const BasicBlock *CurBlock = &BB;
121  // Walk up the dominator tree from the associated DT node for BB to the
122  // associated DT node for Dominator.
123  do {
124  assert(DT.getNode(CurBlock) && "Expecting a valid DT node for CurBlock");
125  BasicBlock *IDom = DT.getNode(CurBlock)->getIDom()->getBlock();
126  assert(DT.dominates(&Dominator, IDom) &&
127  "Expecting Dominator to dominate IDom");
128 
129  // Limitation: can only handle branch instruction currently.
130  const BranchInst *BI = dyn_cast<BranchInst>(IDom->getTerminator());
131  if (!BI)
132  return None;
133 
134  bool Inserted = false;
135  if (PDT.dominates(CurBlock, IDom)) {
136  LLVM_DEBUG(dbgs() << CurBlock->getName()
137  << " is executed unconditionally from "
138  << IDom->getName() << "\n");
139  } else if (PDT.dominates(CurBlock, BI->getSuccessor(0))) {
140  LLVM_DEBUG(dbgs() << CurBlock->getName() << " is executed when \""
141  << *BI->getCondition() << "\" is true from "
142  << IDom->getName() << "\n");
143  Inserted = Conditions.addControlCondition(
144  ControlCondition(BI->getCondition(), true));
145  } else if (PDT.dominates(CurBlock, BI->getSuccessor(1))) {
146  LLVM_DEBUG(dbgs() << CurBlock->getName() << " is executed when \""
147  << *BI->getCondition() << "\" is false from "
148  << IDom->getName() << "\n");
149  Inserted = Conditions.addControlCondition(
150  ControlCondition(BI->getCondition(), false));
151  } else
152  return None;
153 
154  if (Inserted)
155  ++NumConditions;
156 
157  if (MaxLookup != 0 && NumConditions > MaxLookup)
158  return None;
159 
160  CurBlock = IDom;
161  } while (CurBlock != &Dominator);
162 
163  return Conditions;
164 }
165 
166 bool ControlConditions::addControlCondition(ControlCondition C) {
167  bool Inserted = false;
168  if (none_of(Conditions, [&](ControlCondition &Exists) {
169  return ControlConditions::isEquivalent(C, Exists);
170  })) {
171  Conditions.push_back(C);
172  Inserted = true;
173  }
174 
175  LLVM_DEBUG(dbgs() << (Inserted ? "Inserted " : "Not inserted ") << C << "\n");
176  return Inserted;
177 }
178 
179 bool ControlConditions::isEquivalent(const ControlConditions &Other) const {
180  if (Conditions.empty() && Other.Conditions.empty())
181  return true;
182 
183  if (Conditions.size() != Other.Conditions.size())
184  return false;
185 
186  return all_of(Conditions, [&](const ControlCondition &C) {
187  return any_of(Other.Conditions, [&](const ControlCondition &OtherC) {
188  return ControlConditions::isEquivalent(C, OtherC);
189  });
190  });
191 }
192 
193 bool ControlConditions::isEquivalent(const ControlCondition &C1,
194  const ControlCondition &C2) {
195  if (C1.getInt() == C2.getInt()) {
196  if (isEquivalent(*C1.getPointer(), *C2.getPointer()))
197  return true;
198  } else if (isInverse(*C1.getPointer(), *C2.getPointer()))
199  return true;
200 
201  return false;
202 }
203 
204 // FIXME: Use SCEV and reuse GVN/CSE logic to check for equivalence between
205 // Values.
206 // Currently, isEquivalent rely on other passes to ensure equivalent conditions
207 // have the same value, e.g. GVN.
208 bool ControlConditions::isEquivalent(const Value &V1, const Value &V2) {
209  return &V1 == &V2;
210 }
211 
212 bool ControlConditions::isInverse(const Value &V1, const Value &V2) {
213  if (const CmpInst *Cmp1 = dyn_cast<CmpInst>(&V1))
214  if (const CmpInst *Cmp2 = dyn_cast<CmpInst>(&V2)) {
215  if (Cmp1->getPredicate() == Cmp2->getInversePredicate() &&
216  Cmp1->getOperand(0) == Cmp2->getOperand(0) &&
217  Cmp1->getOperand(1) == Cmp2->getOperand(1))
218  return true;
219 
220  if (Cmp1->getPredicate() ==
221  CmpInst::getSwappedPredicate(Cmp2->getInversePredicate()) &&
222  Cmp1->getOperand(0) == Cmp2->getOperand(1) &&
223  Cmp1->getOperand(1) == Cmp2->getOperand(0))
224  return true;
225  }
226  return false;
227 }
228 
230  const DominatorTree &DT,
231  const PostDominatorTree &PDT) {
232  return isControlFlowEquivalent(*I0.getParent(), *I1.getParent(), DT, PDT);
233 }
234 
236  const DominatorTree &DT,
237  const PostDominatorTree &PDT) {
238  if (&BB0 == &BB1)
239  return true;
240 
241  if ((DT.dominates(&BB0, &BB1) && PDT.dominates(&BB1, &BB0)) ||
242  (PDT.dominates(&BB0, &BB1) && DT.dominates(&BB1, &BB0)))
243  return true;
244 
245  // If the set of conditions required to execute BB0 and BB1 from their common
246  // dominator are the same, then BB0 and BB1 are control flow equivalent.
247  const BasicBlock *CommonDominator = DT.findNearestCommonDominator(&BB0, &BB1);
248  LLVM_DEBUG(dbgs() << "The nearest common dominator of " << BB0.getName()
249  << " and " << BB1.getName() << " is "
250  << CommonDominator->getName() << "\n");
251 
252  const Optional<ControlConditions> BB0Conditions =
253  ControlConditions::collectControlConditions(BB0, *CommonDominator, DT,
254  PDT);
255  if (BB0Conditions == None)
256  return false;
257 
258  const Optional<ControlConditions> BB1Conditions =
259  ControlConditions::collectControlConditions(BB1, *CommonDominator, DT,
260  PDT);
261  if (BB1Conditions == None)
262  return false;
263 
264  return BB0Conditions->isEquivalent(*BB1Conditions);
265 }
266 
268  llvm::Statistic &Stat) {
269  ++Stat;
270  LLVM_DEBUG(dbgs() << "Unable to move instruction: " << I << ". "
271  << Stat.getDesc());
272  return false;
273 }
274 
275 /// Collect all instructions in between \p StartInst and \p EndInst, and store
276 /// them in \p InBetweenInsts.
277 static void
279  SmallPtrSetImpl<Instruction *> &InBetweenInsts) {
280  assert(InBetweenInsts.empty() && "Expecting InBetweenInsts to be empty");
281 
282  /// Get the next instructions of \p I, and push them to \p WorkList.
283  auto getNextInsts = [](Instruction &I,
284  SmallPtrSetImpl<Instruction *> &WorkList) {
285  if (Instruction *NextInst = I.getNextNode())
286  WorkList.insert(NextInst);
287  else {
288  assert(I.isTerminator() && "Expecting a terminator instruction");
289  for (BasicBlock *Succ : successors(&I))
290  WorkList.insert(&Succ->front());
291  }
292  };
293 
295  getNextInsts(StartInst, WorkList);
296  while (!WorkList.empty()) {
297  Instruction *CurInst = *WorkList.begin();
298  WorkList.erase(CurInst);
299 
300  if (CurInst == &EndInst)
301  continue;
302 
303  if (!InBetweenInsts.insert(CurInst).second)
304  continue;
305 
306  getNextInsts(*CurInst, WorkList);
307  }
308 }
309 
311  DominatorTree &DT, const PostDominatorTree *PDT,
312  DependenceInfo *DI, bool CheckForEntireBlock) {
313  // Skip tests when we don't have PDT or DI
314  if (!PDT || !DI)
315  return false;
316 
317  // Cannot move itself before itself.
318  if (&I == &InsertPoint)
319  return false;
320 
321  // Not moved.
322  if (I.getNextNode() == &InsertPoint)
323  return true;
324 
325  if (isa<PHINode>(I) || isa<PHINode>(InsertPoint))
326  return reportInvalidCandidate(I, NotMovedPHINode);
327 
328  if (I.isTerminator())
329  return reportInvalidCandidate(I, NotMovedTerminator);
330 
331  // TODO remove this limitation.
332  if (!isControlFlowEquivalent(I, InsertPoint, DT, *PDT))
333  return reportInvalidCandidate(I, NotControlFlowEquivalent);
334 
335  if (!DT.dominates(&InsertPoint, &I))
336  for (const Use &U : I.uses())
337  if (auto *UserInst = dyn_cast<Instruction>(U.getUser()))
338  if (UserInst != &InsertPoint && !DT.dominates(&InsertPoint, U))
339  return false;
340  if (!DT.dominates(&I, &InsertPoint))
341  for (const Value *Op : I.operands())
342  if (auto *OpInst = dyn_cast<Instruction>(Op)) {
343  if (&InsertPoint == OpInst)
344  return false;
345  // If OpInst is an instruction that appears earlier in the same BB as
346  // I, then it is okay to move since OpInst will still be available.
347  if (CheckForEntireBlock && I.getParent() == OpInst->getParent() &&
348  DT.dominates(OpInst, &I))
349  continue;
350  if (!DT.dominates(OpInst, &InsertPoint))
351  return false;
352  }
353 
354  DT.updateDFSNumbers();
355  const bool MoveForward = domTreeLevelBefore(&DT, &I, &InsertPoint);
356  Instruction &StartInst = (MoveForward ? I : InsertPoint);
357  Instruction &EndInst = (MoveForward ? InsertPoint : I);
358  SmallPtrSet<Instruction *, 10> InstsToCheck;
359  collectInstructionsInBetween(StartInst, EndInst, InstsToCheck);
360  if (!MoveForward)
361  InstsToCheck.insert(&InsertPoint);
362 
363  // Check if there exists instructions which may throw, may synchonize, or may
364  // never return, from I to InsertPoint.
366  if (llvm::any_of(InstsToCheck, [](Instruction *I) {
367  if (I->mayThrow())
368  return true;
369 
370  const CallBase *CB = dyn_cast<CallBase>(I);
371  if (!CB)
372  return false;
373  if (!CB->hasFnAttr(Attribute::WillReturn))
374  return true;
375  if (!CB->hasFnAttr(Attribute::NoSync))
376  return true;
377 
378  return false;
379  })) {
380  return reportInvalidCandidate(I, MayThrowException);
381  }
382 
383  // Check if I has any output/flow/anti dependences with instructions from \p
384  // StartInst to \p EndInst.
385  if (llvm::any_of(InstsToCheck, [&DI, &I](Instruction *CurInst) {
386  auto DepResult = DI->depends(&I, CurInst, true);
387  if (DepResult && (DepResult->isOutput() || DepResult->isFlow() ||
388  DepResult->isAnti()))
389  return true;
390  return false;
391  }))
392  return reportInvalidCandidate(I, HasDependences);
393 
394  return true;
395 }
396 
398  DominatorTree &DT, const PostDominatorTree *PDT,
399  DependenceInfo *DI) {
400  return llvm::all_of(BB, [&](Instruction &I) {
401  if (BB.getTerminator() == &I)
402  return true;
403 
404  return isSafeToMoveBefore(I, InsertPoint, DT, PDT, DI,
405  /*CheckForEntireBlock=*/true);
406  });
407 }
408 
410  DominatorTree &DT,
411  const PostDominatorTree &PDT,
412  DependenceInfo &DI) {
413  for (auto It = ++FromBB.rbegin(); It != FromBB.rend();) {
414  Instruction *MovePos = ToBB.getFirstNonPHIOrDbg();
415  Instruction &I = *It;
416  // Increment the iterator before modifying FromBB.
417  ++It;
418 
419  if (isSafeToMoveBefore(I, *MovePos, DT, &PDT, &DI))
420  I.moveBefore(MovePos);
421  }
422 }
423 
425  DominatorTree &DT,
426  const PostDominatorTree &PDT,
427  DependenceInfo &DI) {
428  Instruction *MovePos = ToBB.getTerminator();
429  while (FromBB.size() > 1) {
430  Instruction &I = FromBB.front();
431  if (isSafeToMoveBefore(I, *MovePos, DT, &PDT, &DI))
432  I.moveBefore(MovePos);
433  }
434 }
llvm::CmpInst::getSwappedPredicate
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
Definition: InstrTypes.h:836
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::DominatorTreeBase::findNearestCommonDominator
NodeT * findNearestCommonDominator(NodeT *A, NodeT *B) const
Find nearest common dominator basic block for basic block A and B.
Definition: GenericDomTree.h:468
llvm::none_of
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1565
llvm::SmallPtrSetImpl::erase
bool erase(PtrType Ptr)
erase - If the set contains the specified pointer, remove it and return true, otherwise return false.
Definition: SmallPtrSet.h:378
Optional.h
llvm::BasicBlock::getFirstNonPHIOrDbg
const Instruction * getFirstNonPHIOrDbg(bool SkipPseudoOp=false) const
Returns a pointer to the first instruction in this block that is not a PHINode or a debug intrinsic,...
Definition: BasicBlock.cpp:219
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:4611
domTreeLevelBefore
static bool domTreeLevelBefore(DominatorTree *DT, const Instruction *InstA, const Instruction *InstB)
Definition: CodeMoverUtils.cpp:96
C1
instcombine should handle this C2 when C1
Definition: README.txt:263
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
Statistic.h
ValueTracking.h
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
llvm::DominatorTreeBase::getNode
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
Definition: GenericDomTree.h:351
llvm::Instruction::comesBefore
bool comesBefore(const Instruction *Other) const
Given an instruction Other in the same basic block as this instruction, return true if this instructi...
Definition: Instruction.cpp:111
llvm::Optional
Definition: APInt.h:33
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:449
llvm::DomTreeNodeBase::getIDom
DomTreeNodeBase * getIDom() const
Definition: GenericDomTree.h:89
llvm::successors
succ_range successors(Instruction *I)
Definition: CFG.h:262
llvm::isControlFlowEquivalent
bool isControlFlowEquivalent(const Instruction &I0, const Instruction &I1, const DominatorTree &DT, const PostDominatorTree &PDT)
Return true if I0 and I1 are control flow equivalent.
Definition: CodeMoverUtils.cpp:229
llvm::BasicBlock::rend
reverse_iterator rend()
Definition: BasicBlock.h:303
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::DominatorTree::dominates
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
Definition: Dominators.cpp:115
llvm::all_of
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1551
PostDominators.h
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::Instruction
Definition: Instruction.h:45
collectInstructionsInBetween
static void collectInstructionsInBetween(Instruction &StartInst, const Instruction &EndInst, SmallPtrSetImpl< Instruction * > &InBetweenInsts)
Collect all instructions in between StartInst and EndInst, and store them in InBetweenInsts.
Definition: CodeMoverUtils.cpp:278
llvm::M68kBeads::DA
@ DA
Definition: M68kBaseInfo.h:59
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:53
llvm::operator<<
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
Definition: APFixedPoint.h:230
llvm::BasicBlock::rbegin
reverse_iterator rbegin()
Definition: BasicBlock.h:301
llvm::DominatorTreeBase::updateDFSNumbers
void updateDFSNumbers() const
updateDFSNumbers - Assign In and Out numbers to the nodes while walking dominator tree in dfs order.
Definition: GenericDomTree.h:732
llvm::None
const NoneType None
Definition: None.h:23
llvm::BranchInst::getCondition
Value * getCondition() const
Definition: Instructions.h:3149
llvm::CmpInst
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:710
llvm::TrackingStatistic::getDesc
const char * getDesc() const
Definition: Statistic.h:65
llvm::DependenceInfo
DependenceInfo - This class is the main dependence-analysis driver.
Definition: DependenceAnalysis.h:272
llvm::moveInstructionsToTheEnd
void moveInstructionsToTheEnd(BasicBlock &FromBB, BasicBlock &ToBB, DominatorTree &DT, const PostDominatorTree &PDT, DependenceInfo &DI)
Move instructions, in an order-preserving manner, from FromBB to the end of ToBB when proven safe.
Definition: CodeMoverUtils.cpp:424
llvm::DomTreeNodeBase::getBlock
NodeT * getBlock() const
Definition: GenericDomTree.h:88
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::SmallPtrSetImpl::begin
iterator begin() const
Definition: SmallPtrSet.h:402
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::any_of
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1558
llvm::PostDominatorTree
PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...
Definition: PostDominators.h:28
if
if(llvm_vc STREQUAL "") set(fake_version_inc "$
Definition: CMakeLists.txt:14
llvm::moveInstructionsToTheBeginning
void moveInstructionsToTheBeginning(BasicBlock &FromBB, BasicBlock &ToBB, DominatorTree &DT, const PostDominatorTree &PDT, DependenceInfo &DI)
Move instructions, in an order-preserving manner, from FromBB to the beginning of ToBB when proven sa...
Definition: CodeMoverUtils.cpp:409
CodeMoverUtils.h
reportInvalidCandidate
static bool reportInvalidCandidate(const Instruction &I, llvm::Statistic &Stat)
Definition: CodeMoverUtils.cpp:267
llvm::TrackingStatistic
Definition: Statistic.h:49
llvm::DomTreeNodeBase< BasicBlock >
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:309
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:148
llvm::BasicBlock::front
const Instruction & front() const
Definition: BasicBlock.h:308
llvm::NVPTX::PTXLdStInstCode::V2
@ V2
Definition: NVPTX.h:123
llvm::DomTreeNodeBase::getLevel
unsigned getLevel() const
Definition: GenericDomTree.h:90
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:321
llvm::DependenceInfo::depends
std::unique_ptr< Dependence > depends(Instruction *Src, Instruction *Dst, bool PossiblyLoopIndependent)
depends - Tests for a dependence between the Src and Dst instructions.
Definition: DependenceAnalysis.cpp:3525
llvm::PointerIntPair< Value *, 1, bool >
Dominators.h
llvm::SmallPtrSetImplBase::empty
LLVM_NODISCARD bool empty() const
Definition: SmallPtrSet.h:91
llvm::BasicBlock::size
size_t size() const
Definition: BasicBlock.h:306
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:94
llvm::CallBase
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1161
llvm::SmallPtrSetImpl< Instruction * >
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
DependenceAnalysis.h
llvm::isSafeToMoveBefore
bool isSafeToMoveBefore(Instruction &I, Instruction &InsertPoint, DominatorTree &DT, const PostDominatorTree *PDT=nullptr, DependenceInfo *DI=nullptr, bool CheckForEntireBlock=false)
Return true if I can be safely moved before InsertPoint.
Definition: CodeMoverUtils.cpp:310
llvm::BranchInst
Conditional or Unconditional Branch instruction.
Definition: Instructions.h:3068
llvm::PostDominatorTree::dominates
bool dominates(const Instruction *I1, const Instruction *I2) const
Return true if I1 dominates I2.
Definition: PostDominators.cpp:54
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
llvm::BranchInst::getSuccessor
BasicBlock * getSuccessor(unsigned i) const
Definition: Instructions.h:3161
Other
Optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:1172
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:44
llvm::SmallPtrSetImpl::insert
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:364