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
14 #include "llvm/Transforms/Utils/CodeMoverUtils.h"
15 #include "llvm/ADT/Statistic.h"
16 #include "llvm/Analysis/DependenceAnalysis.h"
17 #include "llvm/Analysis/PostDominators.h"
18 #include "llvm/Analysis/ValueTracking.h"
19 #include "llvm/IR/Dominators.h"
20
21 using namespace llvm;
22
23 #define DEBUG_TYPE "codemover-utils"
24
25 STATISTIC(HasDependences,
26 "Cannot move across instructions that has memory dependences");
27 STATISTIC(MayThrowException, "Cannot move across instructions that may throw");
28 STATISTIC(NotControlFlowEquivalent,
29 "Instructions are not control flow equivalent");
30 STATISTIC(NotMovedPHINode, "Movement of PHINodes are not supported");
31 STATISTIC(NotMovedTerminator, "Movement of Terminator are not supported");
32
isControlFlowEquivalent(const Instruction & I0,const Instruction & I1,const DominatorTree & DT,const PostDominatorTree & PDT)33 bool llvm::isControlFlowEquivalent(const Instruction &I0, const Instruction &I1,
34 const DominatorTree &DT,
35 const PostDominatorTree &PDT) {
36 return isControlFlowEquivalent(*I0.getParent(), *I1.getParent(), DT, PDT);
37 }
38
isControlFlowEquivalent(const BasicBlock & BB0,const BasicBlock & BB1,const DominatorTree & DT,const PostDominatorTree & PDT)39 bool llvm::isControlFlowEquivalent(const BasicBlock &BB0, const BasicBlock &BB1,
40 const DominatorTree &DT,
41 const PostDominatorTree &PDT) {
42 if (&BB0 == &BB1)
43 return true;
44
45 return ((DT.dominates(&BB0, &BB1) && PDT.dominates(&BB1, &BB0)) ||
46 (PDT.dominates(&BB0, &BB1) && DT.dominates(&BB1, &BB0)));
47 }
48
reportInvalidCandidate(const Instruction & I,llvm::Statistic & Stat)49 static bool reportInvalidCandidate(const Instruction &I,
50 llvm::Statistic &Stat) {
51 ++Stat;
52 LLVM_DEBUG(dbgs() << "Unable to move instruction: " << I << ". "
53 << Stat.getDesc());
54 return false;
55 }
56
57 /// Collect all instructions in between \p StartInst and \p EndInst, and store
58 /// them in \p InBetweenInsts.
59 static void
collectInstructionsInBetween(Instruction & StartInst,const Instruction & EndInst,SmallPtrSetImpl<Instruction * > & InBetweenInsts)60 collectInstructionsInBetween(Instruction &StartInst, const Instruction &EndInst,
61 SmallPtrSetImpl<Instruction *> &InBetweenInsts) {
62 assert(InBetweenInsts.empty() && "Expecting InBetweenInsts to be empty");
63
64 /// Get the next instructions of \p I, and push them to \p WorkList.
65 auto getNextInsts = [](Instruction &I,
66 SmallPtrSetImpl<Instruction *> &WorkList) {
67 if (Instruction *NextInst = I.getNextNode())
68 WorkList.insert(NextInst);
69 else {
70 assert(I.isTerminator() && "Expecting a terminator instruction");
71 for (BasicBlock *Succ : successors(&I))
72 WorkList.insert(&Succ->front());
73 }
74 };
75
76 SmallPtrSet<Instruction *, 10> WorkList;
77 getNextInsts(StartInst, WorkList);
78 while (!WorkList.empty()) {
79 Instruction *CurInst = *WorkList.begin();
80 WorkList.erase(CurInst);
81
82 if (CurInst == &EndInst)
83 continue;
84
85 if (!InBetweenInsts.insert(CurInst).second)
86 continue;
87
88 getNextInsts(*CurInst, WorkList);
89 }
90 }
91
isSafeToMoveBefore(Instruction & I,Instruction & InsertPoint,const DominatorTree & DT,const PostDominatorTree & PDT,DependenceInfo & DI)92 bool llvm::isSafeToMoveBefore(Instruction &I, Instruction &InsertPoint,
93 const DominatorTree &DT,
94 const PostDominatorTree &PDT,
95 DependenceInfo &DI) {
96 // Cannot move itself before itself.
97 if (&I == &InsertPoint)
98 return false;
99
100 // Not moved.
101 if (I.getNextNode() == &InsertPoint)
102 return true;
103
104 if (isa<PHINode>(I) || isa<PHINode>(InsertPoint))
105 return reportInvalidCandidate(I, NotMovedPHINode);
106
107 if (I.isTerminator())
108 return reportInvalidCandidate(I, NotMovedTerminator);
109
110 // TODO remove this limitation.
111 if (!isControlFlowEquivalent(I, InsertPoint, DT, PDT))
112 return reportInvalidCandidate(I, NotControlFlowEquivalent);
113
114 // As I and InsertPoint are control flow equivalent, if I dominates
115 // InsertPoint, then I comes before InsertPoint.
116 const bool MoveForward = DT.dominates(&I, &InsertPoint);
117 if (MoveForward) {
118 // When I is being moved forward, we need to make sure the InsertPoint
119 // dominates every users. Or else, a user may be using an undefined I.
120 for (const Use &U : I.uses())
121 if (auto *UserInst = dyn_cast<Instruction>(U.getUser()))
122 if (UserInst != &InsertPoint && !DT.dominates(&InsertPoint, U))
123 return false;
124 } else {
125 // When I is being moved backward, we need to make sure all its opernads
126 // dominates the InsertPoint. Or else, an operand may be undefined for I.
127 for (const Value *Op : I.operands())
128 if (auto *OpInst = dyn_cast<Instruction>(Op))
129 if (&InsertPoint == OpInst || !DT.dominates(OpInst, &InsertPoint))
130 return false;
131 }
132
133 Instruction &StartInst = (MoveForward ? I : InsertPoint);
134 Instruction &EndInst = (MoveForward ? InsertPoint : I);
135 SmallPtrSet<Instruction *, 10> InstsToCheck;
136 collectInstructionsInBetween(StartInst, EndInst, InstsToCheck);
137 if (!MoveForward)
138 InstsToCheck.insert(&InsertPoint);
139
140 // Check if there exists instructions which may throw, may synchonize, or may
141 // never return, from I to InsertPoint.
142 if (!isSafeToSpeculativelyExecute(&I))
143 if (std::any_of(InstsToCheck.begin(), InstsToCheck.end(),
144 [](Instruction *I) {
145 if (I->mayThrow())
146 return true;
147
148 const CallBase *CB = dyn_cast<CallBase>(I);
149 if (!CB)
150 return false;
151 if (!CB->hasFnAttr(Attribute::WillReturn))
152 return true;
153 if (!CB->hasFnAttr(Attribute::NoSync))
154 return true;
155
156 return false;
157 })) {
158 return reportInvalidCandidate(I, MayThrowException);
159 }
160
161 // Check if I has any output/flow/anti dependences with instructions from \p
162 // StartInst to \p EndInst.
163 if (std::any_of(InstsToCheck.begin(), InstsToCheck.end(),
164 [&DI, &I](Instruction *CurInst) {
165 auto DepResult = DI.depends(&I, CurInst, true);
166 if (DepResult &&
167 (DepResult->isOutput() || DepResult->isFlow() ||
168 DepResult->isAnti()))
169 return true;
170 return false;
171 }))
172 return reportInvalidCandidate(I, HasDependences);
173
174 return true;
175 }
176
moveInstsBottomUp(BasicBlock & FromBB,BasicBlock & ToBB,const DominatorTree & DT,const PostDominatorTree & PDT,DependenceInfo & DI)177 void llvm::moveInstsBottomUp(BasicBlock &FromBB, BasicBlock &ToBB,
178 const DominatorTree &DT,
179 const PostDominatorTree &PDT, DependenceInfo &DI) {
180 for (auto It = ++FromBB.rbegin(); It != FromBB.rend();) {
181 Instruction *MovePos = ToBB.getFirstNonPHIOrDbg();
182 Instruction &I = *It;
183 // Increment the iterator before modifying FromBB.
184 ++It;
185
186 if (isSafeToMoveBefore(I, *MovePos, DT, PDT, DI))
187 I.moveBefore(MovePos);
188 }
189 }
190