LLVM  12.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) {
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 || !DT.dominates(OpInst, &InsertPoint))
344  return false;
345 
346  DT.updateDFSNumbers();
347  const bool MoveForward = domTreeLevelBefore(&DT, &I, &InsertPoint);
348  Instruction &StartInst = (MoveForward ? I : InsertPoint);
349  Instruction &EndInst = (MoveForward ? InsertPoint : I);
350  SmallPtrSet<Instruction *, 10> InstsToCheck;
351  collectInstructionsInBetween(StartInst, EndInst, InstsToCheck);
352  if (!MoveForward)
353  InstsToCheck.insert(&InsertPoint);
354 
355  // Check if there exists instructions which may throw, may synchonize, or may
356  // never return, from I to InsertPoint.
358  if (std::any_of(InstsToCheck.begin(), InstsToCheck.end(),
359  [](Instruction *I) {
360  if (I->mayThrow())
361  return true;
362 
363  const CallBase *CB = dyn_cast<CallBase>(I);
364  if (!CB)
365  return false;
366  if (!CB->hasFnAttr(Attribute::WillReturn))
367  return true;
368  if (!CB->hasFnAttr(Attribute::NoSync))
369  return true;
370 
371  return false;
372  })) {
373  return reportInvalidCandidate(I, MayThrowException);
374  }
375 
376  // Check if I has any output/flow/anti dependences with instructions from \p
377  // StartInst to \p EndInst.
378  if (std::any_of(InstsToCheck.begin(), InstsToCheck.end(),
379  [&DI, &I](Instruction *CurInst) {
380  auto DepResult = DI->depends(&I, CurInst, true);
381  if (DepResult &&
382  (DepResult->isOutput() || DepResult->isFlow() ||
383  DepResult->isAnti()))
384  return true;
385  return false;
386  }))
387  return reportInvalidCandidate(I, HasDependences);
388 
389  return true;
390 }
391 
393  DominatorTree &DT, const PostDominatorTree *PDT,
394  DependenceInfo *DI) {
395  return llvm::all_of(BB, [&](Instruction &I) {
396  if (BB.getTerminator() == &I)
397  return true;
398 
399  return isSafeToMoveBefore(I, InsertPoint, DT, PDT, DI);
400  });
401 }
402 
404  DominatorTree &DT,
405  const PostDominatorTree &PDT,
406  DependenceInfo &DI) {
407  for (auto It = ++FromBB.rbegin(); It != FromBB.rend();) {
408  Instruction *MovePos = ToBB.getFirstNonPHIOrDbg();
409  Instruction &I = *It;
410  // Increment the iterator before modifying FromBB.
411  ++It;
412 
413  if (isSafeToMoveBefore(I, *MovePos, DT, &PDT, &DI))
414  I.moveBefore(MovePos);
415  }
416 }
417 
419  DominatorTree &DT,
420  const PostDominatorTree &PDT,
421  DependenceInfo &DI) {
422  Instruction *MovePos = ToBB.getTerminator();
423  while (FromBB.size() > 1) {
424  Instruction &I = FromBB.front();
425  if (isSafeToMoveBefore(I, *MovePos, DT, &PDT, &DI))
426  I.moveBefore(MovePos);
427  }
428 }
uint64_t CallInst * C
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:715
iterator_range< use_iterator > uses()
Definition: Value.h:373
LLVM_NODISCARD std::enable_if_t< !is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type > dyn_cast(const Y &Val)
Definition: Casting.h:334
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
Definition: ilist_node.h:288
This class represents lattice values for constants.
Definition: AllocatorList.h:23
bool isTerminator() const
Definition: Instruction.h:163
NodeT * findNearestCommonDominator(NodeT *A, NodeT *B) const
findNearestCommonDominator - Find nearest common dominator basic block for basic block A and B...
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:1491
STATISTIC(NumFunctions, "Total number of functions")
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1100
reverse_iterator rend()
Definition: BasicBlock.h:296
reverse_iterator rbegin()
Definition: BasicBlock.h:294
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:150
DependenceInfo - This class is the main dependence-analysis driver.
bool isSafeToMoveBefore(Instruction &I, Instruction &InsertPoint, DominatorTree &DT, const PostDominatorTree *PDT=nullptr, DependenceInfo *DI=nullptr)
Return true if I can be safely moved before InsertPoint.
A Use represents the edge between a Value definition and its users.
Definition: Use.h:44
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:1505
const char * getDesc() const
Definition: Statistic.h:58
bool isControlFlowEquivalent(const Instruction &I0, const Instruction &I1, const DominatorTree &DT, const PostDominatorTree &PDT)
Return true if I0 and I1 are control flow equivalent.
static bool reportInvalidCandidate(const Instruction &I, llvm::Statistic &Stat)
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:144
NodeT * getBlock() const
std::unique_ptr< Dependence > depends(Instruction *Src, Instruction *Dst, bool PossiblyLoopIndependent)
depends - Tests for a dependence between the Src and Dst instructions.
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
bool dominates(const Instruction *I1, const Instruction *I2) const
Return true if I1 dominates I2.
Conditional or Unconditional Branch instruction.
DomTreeNodeBase * getIDom() const
LLVM_NODISCARD bool empty() const
Definition: SmallPtrSet.h:91
const Instruction & front() const
Definition: BasicBlock.h:301
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
size_t size() const
Definition: BasicBlock.h:299
bool mayThrow() const
Return true if this instruction may throw an exception.
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:1498
op_range operands()
Definition: User.h:242
bool hasFnAttr(Attribute::AttrKind Kind) const
Determine whether this call has the given attribute.
Definition: InstrTypes.h:1397
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:439
bool erase(PtrType Ptr)
erase - If the set contains the specified pointer, remove it and return true, otherwise return false...
Definition: SmallPtrSet.h:371
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:883
bool dominates(const Instruction *Def, const Use &U) const
Return true if Def dominates a use in User.
Definition: Dominators.cpp:251
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...
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...
iterator begin() const
Definition: SmallPtrSet.h:392
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:270
#define I(x, y, z)
Definition: MD5.cpp:59
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...
raw_ostream & operator<<(raw_ostream &OS, const APInt &I)
Definition: APInt.h:2099
iterator end() const
Definition: SmallPtrSet.h:397
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
bool isSafeToSpeculativelyExecute(const Value *V, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr)
Return true if the instruction does not have any effects besides calculating the result and does not ...
void updateDFSNumbers() const
updateDFSNumbers - Assign In and Out numbers to the nodes while walking dominator tree in dfs order...
LLVM Value Representation.
Definition: Value.h:74
bool comesBefore(const Instruction *Other) const
Given an instruction Other in the same basic block as this instruction, return true if this instructi...
succ_range successors(Instruction *I)
Definition: CFG.h:260
void moveBefore(Instruction *MovePos)
Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...
Definition: Instruction.cpp:99
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:46
unsigned getLevel() const
static bool domTreeLevelBefore(DominatorTree *DT, const Instruction *InstA, const Instruction *InstB)
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
Definition: InstrTypes.h:842
const Instruction * getFirstNonPHIOrDbg() const
Returns a pointer to the first instruction in this block that is not a PHINode or a debug intrinsic...
Definition: BasicBlock.cpp:221
static void collectInstructionsInBetween(Instruction &StartInst, const Instruction &EndInst, SmallPtrSetImpl< Instruction *> &InBetweenInsts)
Collect all instructions in between StartInst and EndInst, and store them in InBetweenInsts.
#define LLVM_DEBUG(X)
Definition: Debug.h:122
const BasicBlock * getParent() const
Definition: Instruction.h:94