1 //===- CodeMoverUtils.cpp - CodeMover Utilities ----------------------------==//
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
7 //===----------------------------------------------------------------------===//
9 // This family of functions perform movements on basic blocks, and instructions
10 // contained within a function.
12 //===----------------------------------------------------------------------===//
14 #include "llvm/Transforms/Utils/CodeMoverUtils.h"
15 #include "llvm/ADT/Optional.h"
16 #include "llvm/ADT/Statistic.h"
17 #include "llvm/Analysis/DependenceAnalysis.h"
18 #include "llvm/Analysis/PostDominators.h"
19 #include "llvm/Analysis/ValueTracking.h"
20 #include "llvm/IR/Dominators.h"
24 #define DEBUG_TYPE "codemover-utils"
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");
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>;
44 raw_ostream &operator<<(raw_ostream &OS, const ControlCondition &C) {
45 OS << "[" << *C.getPointer() << ", " << (C.getInt() ? "true" : "false")
51 /// Represent a set of control conditions required to execute ToBB from FromBB.
52 class ControlConditions {
53 using ConditionVectorTy = SmallVector<ControlCondition, 6>;
55 /// A SmallVector of control conditions.
56 ConditionVectorTy Conditions;
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);
69 /// Return true if there exists no control conditions required to execute ToBB
71 bool isUnconditional() const { return Conditions.empty(); }
73 /// Return a constant reference of Conditions.
74 const ConditionVectorTy &getControlConditions() const { return Conditions; }
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);
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;
84 /// Return true if \p C1 and \p C2 are equivalent.
85 static bool isEquivalent(const ControlCondition &C1,
86 const ControlCondition &C2);
89 ControlConditions() = default;
91 static bool isEquivalent(const Value &V1, const Value &V2);
92 static bool isInverse(const Value &V1, const Value &V2);
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
100 if (InstA->getParent() == InstB->getParent())
101 return InstA->comesBefore(InstB);
103 DomTreeNode *DA = DT->getNode(InstA->getParent());
104 DomTreeNode *DB = DT->getNode(InstB->getParent());
105 return DA->getLevel() < DB->getLevel();
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");
113 ControlConditions Conditions;
114 unsigned NumConditions = 0;
116 // BB is executed unconditional from itself.
117 if (&Dominator == &BB)
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.
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");
129 // Limitation: can only handle branch instruction currently.
130 const BranchInst *BI = dyn_cast<BranchInst>(IDom->getTerminator());
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));
157 if (MaxLookup != 0 && NumConditions > MaxLookup)
161 } while (CurBlock != &Dominator);
166 bool ControlConditions::addControlCondition(ControlCondition C) {
167 bool Inserted = false;
168 if (none_of(Conditions, [&](ControlCondition &Exists) {
169 return ControlConditions::isEquivalent(C, Exists);
171 Conditions.push_back(C);
175 LLVM_DEBUG(dbgs() << (Inserted ? "Inserted " : "Not inserted ") << C << "\n");
179 bool ControlConditions::isEquivalent(const ControlConditions &Other) const {
180 if (Conditions.empty() && Other.Conditions.empty())
183 if (Conditions.size() != Other.Conditions.size())
186 return all_of(Conditions, [&](const ControlCondition &C) {
187 return any_of(Other.Conditions, [&](const ControlCondition &OtherC) {
188 return ControlConditions::isEquivalent(C, OtherC);
193 bool ControlConditions::isEquivalent(const ControlCondition &C1,
194 const ControlCondition &C2) {
195 if (C1.getInt() == C2.getInt()) {
196 if (isEquivalent(*C1.getPointer(), *C2.getPointer()))
198 } else if (isInverse(*C1.getPointer(), *C2.getPointer()))
204 // FIXME: Use SCEV and reuse GVN/CSE logic to check for equivalence between
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) {
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))
220 if (Cmp1->getPredicate() ==
221 CmpInst::getSwappedPredicate(Cmp2->getInversePredicate()) &&
222 Cmp1->getOperand(0) == Cmp2->getOperand(1) &&
223 Cmp1->getOperand(1) == Cmp2->getOperand(0))
229 bool llvm::isControlFlowEquivalent(const Instruction &I0, const Instruction &I1,
230 const DominatorTree &DT,
231 const PostDominatorTree &PDT) {
232 return isControlFlowEquivalent(*I0.getParent(), *I1.getParent(), DT, PDT);
235 bool llvm::isControlFlowEquivalent(const BasicBlock &BB0, const BasicBlock &BB1,
236 const DominatorTree &DT,
237 const PostDominatorTree &PDT) {
241 if ((DT.dominates(&BB0, &BB1) && PDT.dominates(&BB1, &BB0)) ||
242 (PDT.dominates(&BB0, &BB1) && DT.dominates(&BB1, &BB0)))
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");
252 const Optional<ControlConditions> BB0Conditions =
253 ControlConditions::collectControlConditions(BB0, *CommonDominator, DT,
255 if (BB0Conditions == None)
258 const Optional<ControlConditions> BB1Conditions =
259 ControlConditions::collectControlConditions(BB1, *CommonDominator, DT,
261 if (BB1Conditions == None)
264 return BB0Conditions->isEquivalent(*BB1Conditions);
267 static bool reportInvalidCandidate(const Instruction &I,
268 llvm::Statistic &Stat) {
270 LLVM_DEBUG(dbgs() << "Unable to move instruction: " << I << ". "
275 /// Collect all instructions in between \p StartInst and \p EndInst, and store
276 /// them in \p InBetweenInsts.
278 collectInstructionsInBetween(Instruction &StartInst, const Instruction &EndInst,
279 SmallPtrSetImpl<Instruction *> &InBetweenInsts) {
280 assert(InBetweenInsts.empty() && "Expecting InBetweenInsts to be empty");
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);
288 assert(I.isTerminator() && "Expecting a terminator instruction");
289 for (BasicBlock *Succ : successors(&I))
290 WorkList.insert(&Succ->front());
294 SmallPtrSet<Instruction *, 10> WorkList;
295 getNextInsts(StartInst, WorkList);
296 while (!WorkList.empty()) {
297 Instruction *CurInst = *WorkList.begin();
298 WorkList.erase(CurInst);
300 if (CurInst == &EndInst)
303 if (!InBetweenInsts.insert(CurInst).second)
306 getNextInsts(*CurInst, WorkList);
310 bool llvm::isSafeToMoveBefore(Instruction &I, Instruction &InsertPoint,
311 DominatorTree &DT, const PostDominatorTree *PDT,
312 DependenceInfo *DI, bool CheckForEntireBlock) {
313 // Skip tests when we don't have PDT or DI
317 // Cannot move itself before itself.
318 if (&I == &InsertPoint)
322 if (I.getNextNode() == &InsertPoint)
325 if (isa<PHINode>(I) || isa<PHINode>(InsertPoint))
326 return reportInvalidCandidate(I, NotMovedPHINode);
328 if (I.isTerminator())
329 return reportInvalidCandidate(I, NotMovedTerminator);
331 // TODO remove this limitation.
332 if (!isControlFlowEquivalent(I, InsertPoint, DT, *PDT))
333 return reportInvalidCandidate(I, NotControlFlowEquivalent);
335 if (isReachedBefore(&I, &InsertPoint, &DT, PDT))
336 for (const Use &U : I.uses())
337 if (auto *UserInst = dyn_cast<Instruction>(U.getUser()))
338 if (UserInst != &InsertPoint && !DT.dominates(&InsertPoint, U))
340 if (isReachedBefore(&InsertPoint, &I, &DT, PDT))
341 for (const Value *Op : I.operands())
342 if (auto *OpInst = dyn_cast<Instruction>(Op)) {
343 if (&InsertPoint == OpInst)
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))
350 if (!DT.dominates(OpInst, &InsertPoint))
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);
361 InstsToCheck.insert(&InsertPoint);
363 // Check if there exists instructions which may throw, may synchonize, or may
364 // never return, from I to InsertPoint.
365 if (!isSafeToSpeculativelyExecute(&I))
366 if (llvm::any_of(InstsToCheck, [](Instruction *I) {
370 const CallBase *CB = dyn_cast<CallBase>(I);
373 if (!CB->hasFnAttr(Attribute::WillReturn))
375 if (!CB->hasFnAttr(Attribute::NoSync))
380 return reportInvalidCandidate(I, MayThrowException);
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()))
392 return reportInvalidCandidate(I, HasDependences);
397 bool llvm::isSafeToMoveBefore(BasicBlock &BB, Instruction &InsertPoint,
398 DominatorTree &DT, const PostDominatorTree *PDT,
399 DependenceInfo *DI) {
400 return llvm::all_of(BB, [&](Instruction &I) {
401 if (BB.getTerminator() == &I)
404 return isSafeToMoveBefore(I, InsertPoint, DT, PDT, DI,
405 /*CheckForEntireBlock=*/true);
409 void llvm::moveInstructionsToTheBeginning(BasicBlock &FromBB, BasicBlock &ToBB,
411 const PostDominatorTree &PDT,
412 DependenceInfo &DI) {
413 for (Instruction &I :
414 llvm::make_early_inc_range(llvm::drop_begin(llvm::reverse(FromBB)))) {
415 Instruction *MovePos = ToBB.getFirstNonPHIOrDbg();
417 if (isSafeToMoveBefore(I, *MovePos, DT, &PDT, &DI))
418 I.moveBefore(MovePos);
422 void llvm::moveInstructionsToTheEnd(BasicBlock &FromBB, BasicBlock &ToBB,
424 const PostDominatorTree &PDT,
425 DependenceInfo &DI) {
426 Instruction *MovePos = ToBB.getTerminator();
427 while (FromBB.size() > 1) {
428 Instruction &I = FromBB.front();
429 if (isSafeToMoveBefore(I, *MovePos, DT, &PDT, &DI))
430 I.moveBefore(MovePos);
434 bool llvm::nonStrictlyPostDominate(const BasicBlock *ThisBlock,
435 const BasicBlock *OtherBlock,
436 const DominatorTree *DT,
437 const PostDominatorTree *PDT) {
438 assert(isControlFlowEquivalent(*ThisBlock, *OtherBlock, *DT, *PDT) &&
439 "ThisBlock and OtherBlock must be CFG equivalent!");
440 const BasicBlock *CommonDominator =
441 DT->findNearestCommonDominator(ThisBlock, OtherBlock);
442 if (CommonDominator == nullptr)
445 /// Recursively check the predecessors of \p ThisBlock up to
446 /// their common dominator, and see if any of them post-dominates
448 SmallVector<const BasicBlock *, 8> WorkList;
449 SmallPtrSet<const BasicBlock *, 8> Visited;
450 WorkList.push_back(ThisBlock);
451 while (!WorkList.empty()) {
452 const BasicBlock *CurBlock = WorkList.back();
454 Visited.insert(CurBlock);
455 if (PDT->dominates(CurBlock, OtherBlock))
458 for (auto *Pred : predecessors(CurBlock)) {
459 if (Pred == CommonDominator || Visited.count(Pred))
461 WorkList.push_back(Pred);
467 bool llvm::isReachedBefore(const Instruction *I0, const Instruction *I1,
468 const DominatorTree *DT,
469 const PostDominatorTree *PDT) {
470 const BasicBlock *BB0 = I0->getParent();
471 const BasicBlock *BB1 = I1->getParent();
473 return DT->dominates(I0, I1);
475 return nonStrictlyPostDominate(BB1, BB0, DT, PDT);