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
21using namespace llvm;
22
23#define DEBUG_TYPE "codemover-utils"
24
25STATISTIC(HasDependences,
26 "Cannot move across instructions that has memory dependences");
27STATISTIC(MayThrowException, "Cannot move across instructions that may throw");
28STATISTIC(NotMovedPHINode, "Movement of PHINodes are not supported");
29STATISTIC(NotMovedTerminator, "Movement of Terminator are not supported");
30
31static bool domTreeLevelBefore(DominatorTree *DT, const Instruction *InstA,
32 const Instruction *InstB) {
33 // Use ordered basic block in case the 2 instructions are in the same
34 // block.
35 if (InstA->getParent() == InstB->getParent())
36 return InstA->comesBefore(Other: InstB);
37
38 DomTreeNode *DA = DT->getNode(BB: InstA->getParent());
39 DomTreeNode *DB = DT->getNode(BB: InstB->getParent());
40 return DA->getLevel() < DB->getLevel();
41}
42
43static bool reportInvalidCandidate(const Instruction &I,
44 llvm::Statistic &Stat) {
45 ++Stat;
46 LLVM_DEBUG(dbgs() << "Unable to move instruction: " << I << ". "
47 << Stat.getDesc());
48 return false;
49}
50
51/// Collect all instructions in between \p StartInst and \p EndInst, and store
52/// them in \p InBetweenInsts.
53static void
54collectInstructionsInBetween(Instruction &StartInst, const Instruction &EndInst,
55 SmallPtrSetImpl<Instruction *> &InBetweenInsts) {
56 assert(InBetweenInsts.empty() && "Expecting InBetweenInsts to be empty");
57
58 /// Get the next instructions of \p I, and push them to \p WorkList.
59 auto getNextInsts = [](Instruction &I,
60 SmallPtrSetImpl<Instruction *> &WorkList) {
61 if (Instruction *NextInst = I.getNextNode())
62 WorkList.insert(Ptr: NextInst);
63 else {
64 assert(I.isTerminator() && "Expecting a terminator instruction");
65 for (BasicBlock *Succ : successors(I: &I))
66 WorkList.insert(Ptr: &Succ->front());
67 }
68 };
69
70 SmallPtrSet<Instruction *, 10> WorkList;
71 getNextInsts(StartInst, WorkList);
72 while (!WorkList.empty()) {
73 Instruction *CurInst = *WorkList.begin();
74 WorkList.erase(Ptr: CurInst);
75
76 if (CurInst == &EndInst)
77 continue;
78
79 if (!InBetweenInsts.insert(Ptr: CurInst).second)
80 continue;
81
82 getNextInsts(*CurInst, WorkList);
83 }
84}
85
86bool llvm::isSafeToMoveBefore(Instruction &I, Instruction &InsertPoint,
87 DominatorTree &DT, const PostDominatorTree *PDT,
88 DependenceInfo *DI, bool CheckForEntireBlock) {
89 // Skip tests when we don't have PDT or DI
90 if (!PDT || !DI)
91 return false;
92
93 // Cannot move itself before itself.
94 if (&I == &InsertPoint)
95 return false;
96
97 // Not moved.
98 if (I.getNextNode() == &InsertPoint)
99 return true;
100
101 if (isa<PHINode>(Val: I) || isa<PHINode>(Val: InsertPoint))
102 return reportInvalidCandidate(I, Stat&: NotMovedPHINode);
103
104 if (I.isTerminator())
105 return reportInvalidCandidate(I, Stat&: NotMovedTerminator);
106
107 if (isReachedBefore(I0: &I, I1: &InsertPoint, DT: &DT, PDT))
108 for (const Use &U : I.uses())
109 if (auto *UserInst = dyn_cast<Instruction>(Val: U.getUser())) {
110 // If InsertPoint is in a BB that comes after I, then we cannot move if
111 // I is used in the terminator of the current BB.
112 if (I.getParent() == InsertPoint.getParent() &&
113 UserInst == I.getParent()->getTerminator())
114 return false;
115 if (UserInst != &InsertPoint && !DT.dominates(Def: &InsertPoint, U)) {
116 // If UserInst is an instruction that appears later in the same BB as
117 // I, then it is okay to move since I will still be available when
118 // UserInst is executed.
119 if (CheckForEntireBlock && I.getParent() == UserInst->getParent() &&
120 DT.dominates(Def: &I, User: UserInst))
121 continue;
122 return false;
123 }
124 }
125 if (isReachedBefore(I0: &InsertPoint, I1: &I, DT: &DT, PDT))
126 for (const Value *Op : I.operands())
127 if (auto *OpInst = dyn_cast<Instruction>(Val: Op)) {
128 if (&InsertPoint == OpInst)
129 return false;
130 // If OpInst is an instruction that appears earlier in the same BB as
131 // I, then it is okay to move since OpInst will still be available.
132 if (CheckForEntireBlock && I.getParent() == OpInst->getParent() &&
133 DT.dominates(Def: OpInst, User: &I))
134 continue;
135 if (!DT.dominates(Def: OpInst, User: &InsertPoint))
136 return false;
137 }
138
139 DT.updateDFSNumbers();
140 const bool MoveForward = domTreeLevelBefore(DT: &DT, InstA: &I, InstB: &InsertPoint);
141 Instruction &StartInst = (MoveForward ? I : InsertPoint);
142 Instruction &EndInst = (MoveForward ? InsertPoint : I);
143 SmallPtrSet<Instruction *, 10> InstsToCheck;
144 collectInstructionsInBetween(StartInst, EndInst, InBetweenInsts&: InstsToCheck);
145 if (!MoveForward)
146 InstsToCheck.insert(Ptr: &InsertPoint);
147
148 // Check if there exists instructions which may throw, may synchonize, or may
149 // never return, from I to InsertPoint.
150 if (!isSafeToSpeculativelyExecute(I: &I))
151 if (llvm::any_of(Range&: InstsToCheck, P: [](Instruction *I) {
152 if (I->mayThrow())
153 return true;
154
155 const CallBase *CB = dyn_cast<CallBase>(Val: I);
156 if (!CB)
157 return false;
158 if (!CB->hasFnAttr(Kind: Attribute::WillReturn))
159 return true;
160 if (!CB->hasFnAttr(Kind: Attribute::NoSync))
161 return true;
162
163 return false;
164 })) {
165 return reportInvalidCandidate(I, Stat&: MayThrowException);
166 }
167
168 // Check if I has any output/flow/anti dependences with instructions from \p
169 // StartInst to \p EndInst.
170 if (llvm::any_of(Range&: InstsToCheck, P: [&DI, &I](Instruction *CurInst) {
171 auto DepResult = DI->depends(Src: &I, Dst: CurInst);
172 if (DepResult && (DepResult->isOutput() || DepResult->isFlow() ||
173 DepResult->isAnti()))
174 return true;
175 return false;
176 }))
177 return reportInvalidCandidate(I, Stat&: HasDependences);
178
179 return true;
180}
181
182bool llvm::isSafeToMoveBefore(BasicBlock &BB, Instruction &InsertPoint,
183 DominatorTree &DT, const PostDominatorTree *PDT,
184 DependenceInfo *DI) {
185 return llvm::all_of(Range&: BB, P: [&](Instruction &I) {
186 if (BB.getTerminator() == &I)
187 return true;
188
189 return isSafeToMoveBefore(I, InsertPoint, DT, PDT, DI,
190 /*CheckForEntireBlock=*/true);
191 });
192}
193
194void llvm::moveInstructionsToTheBeginning(BasicBlock &FromBB, BasicBlock &ToBB,
195 DominatorTree &DT,
196 const PostDominatorTree &PDT,
197 DependenceInfo &DI) {
198 for (Instruction &I :
199 llvm::make_early_inc_range(Range: llvm::drop_begin(RangeOrContainer: llvm::reverse(C&: FromBB)))) {
200 BasicBlock::iterator MovePos = ToBB.getFirstNonPHIOrDbg();
201
202 if (isSafeToMoveBefore(I, InsertPoint&: *MovePos, DT, PDT: &PDT, DI: &DI))
203 I.moveBeforePreserving(MovePos);
204 }
205}
206
207void llvm::moveInstructionsToTheEnd(BasicBlock &FromBB, BasicBlock &ToBB,
208 DominatorTree &DT,
209 const PostDominatorTree &PDT,
210 DependenceInfo &DI) {
211 Instruction *MovePos = ToBB.getTerminator();
212 while (FromBB.size() > 1) {
213 Instruction &I = FromBB.front();
214 if (isSafeToMoveBefore(I, InsertPoint&: *MovePos, DT, PDT: &PDT, DI: &DI))
215 I.moveBeforePreserving(MovePos: MovePos->getIterator());
216 }
217}
218
219bool llvm::nonStrictlyPostDominate(const BasicBlock *ThisBlock,
220 const BasicBlock *OtherBlock,
221 const DominatorTree *DT,
222 const PostDominatorTree *PDT) {
223 const BasicBlock *CommonDominator =
224 DT->findNearestCommonDominator(A: ThisBlock, B: OtherBlock);
225 if (CommonDominator == nullptr)
226 return false;
227
228 /// Recursively check the predecessors of \p ThisBlock up to
229 /// their common dominator, and see if any of them post-dominates
230 /// \p OtherBlock.
231 SmallVector<const BasicBlock *, 8> WorkList;
232 SmallPtrSet<const BasicBlock *, 8> Visited;
233 WorkList.push_back(Elt: ThisBlock);
234 while (!WorkList.empty()) {
235 const BasicBlock *CurBlock = WorkList.pop_back_val();
236 Visited.insert(Ptr: CurBlock);
237 if (PDT->dominates(A: CurBlock, B: OtherBlock))
238 return true;
239
240 for (const auto *Pred : predecessors(BB: CurBlock)) {
241 if (Pred == CommonDominator || Visited.count(Ptr: Pred))
242 continue;
243 WorkList.push_back(Elt: Pred);
244 }
245 }
246 return false;
247}
248
249bool llvm::isReachedBefore(const Instruction *I0, const Instruction *I1,
250 const DominatorTree *DT,
251 const PostDominatorTree *PDT) {
252 const BasicBlock *BB0 = I0->getParent();
253 const BasicBlock *BB1 = I1->getParent();
254 if (BB0 == BB1)
255 return DT->dominates(Def: I0, User: I1);
256
257 return nonStrictlyPostDominate(ThisBlock: BB1, OtherBlock: BB0, DT, PDT);
258}
259