1//===-- MoveAutoInit.cpp - move auto-init inst closer to their use site----===//
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 pass moves instruction maked as auto-init closer to the basic block that
10// use it, eventually removing it from some control path of the function.
11//
12//===----------------------------------------------------------------------===//
13
14#include "llvm/Transforms/Utils/MoveAutoInit.h"
15#include "llvm/ADT/STLExtras.h"
16#include "llvm/ADT/Statistic.h"
17#include "llvm/Analysis/MemorySSA.h"
18#include "llvm/Analysis/MemorySSAUpdater.h"
19#include "llvm/Analysis/ValueTracking.h"
20#include "llvm/IR/DebugInfo.h"
21#include "llvm/IR/Dominators.h"
22#include "llvm/IR/IRBuilder.h"
23#include "llvm/IR/Instructions.h"
24#include "llvm/IR/IntrinsicInst.h"
25#include "llvm/Support/CommandLine.h"
26#include "llvm/Transforms/Utils.h"
27#include "llvm/Transforms/Utils/LoopUtils.h"
28
29using namespace llvm;
30
31#define DEBUG_TYPE "move-auto-init"
32
33STATISTIC(NumMoved, "Number of instructions moved");
34
35static cl::opt<unsigned> MoveAutoInitThreshold(
36 "move-auto-init-threshold", cl::Hidden, cl::init(Val: 128),
37 cl::desc("Maximum instructions to analyze per moved initialization"));
38
39static bool hasAutoInitMetadata(const Instruction &I) {
40 return I.hasMetadata(KindID: LLVMContext::MD_annotation) &&
41 any_of(Range: I.getMetadata(KindID: LLVMContext::MD_annotation)->operands(),
42 P: [](const MDOperand &Op) { return Op.equalsStr(Str: "auto-init"); });
43}
44
45static std::optional<MemoryLocation> writeToAlloca(const Instruction &I) {
46 MemoryLocation ML;
47 if (auto *MI = dyn_cast<MemIntrinsic>(Val: &I))
48 ML = MemoryLocation::getForDest(MI);
49 else if (auto *SI = dyn_cast<StoreInst>(Val: &I))
50 ML = MemoryLocation::get(SI);
51 else
52 return std::nullopt;
53
54 if (isa<AllocaInst>(Val: getUnderlyingObject(V: ML.Ptr)))
55 return ML;
56 else
57 return {};
58}
59
60/// Finds a BasicBlock in the CFG where instruction `I` can be moved to while
61/// not changing the Memory SSA ordering and being guarded by at least one
62/// condition.
63static BasicBlock *usersDominator(const MemoryLocation &ML, Instruction *I,
64 DominatorTree &DT, MemorySSA &MSSA) {
65 BasicBlock *CurrentDominator = nullptr;
66 MemoryUseOrDef &IMA = *MSSA.getMemoryAccess(I);
67 BatchAAResults AA(MSSA.getAA());
68
69 SmallPtrSet<MemoryAccess *, 8> Visited;
70
71 auto AsMemoryAccess = [](User *U) { return cast<MemoryAccess>(Val: U); };
72 SmallVector<MemoryAccess *> WorkList(map_range(C: IMA.users(), F: AsMemoryAccess));
73
74 while (!WorkList.empty()) {
75 MemoryAccess *MA = WorkList.pop_back_val();
76 if (!Visited.insert(Ptr: MA).second)
77 continue;
78
79 if (Visited.size() > MoveAutoInitThreshold)
80 return nullptr;
81
82 bool FoundClobberingUser = false;
83 if (auto *M = dyn_cast<MemoryUseOrDef>(Val: MA)) {
84 Instruction *MI = M->getMemoryInst();
85
86 // If this memory instruction may not clobber `I`, we can skip it.
87 // LifetimeEnd is a valid user, but we do not want it in the user
88 // dominator.
89 if (AA.getModRefInfo(I: MI, OptLoc: ML) != ModRefInfo::NoModRef &&
90 !MI->isLifetimeStartOrEnd() && MI != I) {
91 FoundClobberingUser = true;
92 CurrentDominator = CurrentDominator
93 ? DT.findNearestCommonDominator(A: CurrentDominator,
94 B: MI->getParent())
95 : MI->getParent();
96 }
97 }
98 if (!FoundClobberingUser) {
99 auto UsersAsMemoryAccesses = map_range(C: MA->users(), F: AsMemoryAccess);
100 append_range(C&: WorkList, R&: UsersAsMemoryAccesses);
101 }
102 }
103 return CurrentDominator;
104}
105
106static bool runMoveAutoInit(Function &F, DominatorTree &DT, MemorySSA &MSSA) {
107 BasicBlock &EntryBB = F.getEntryBlock();
108 SmallVector<std::pair<Instruction *, BasicBlock *>> JobList;
109
110 //
111 // Compute movable instructions.
112 //
113 for (Instruction &I : EntryBB) {
114 if (!hasAutoInitMetadata(I))
115 continue;
116
117 std::optional<MemoryLocation> ML = writeToAlloca(I);
118 if (!ML)
119 continue;
120
121 if (I.isVolatile())
122 continue;
123
124 BasicBlock *UsersDominator = usersDominator(ML: ML.value(), I: &I, DT, MSSA);
125 if (!UsersDominator)
126 continue;
127
128 if (UsersDominator == &EntryBB)
129 continue;
130
131 // Traverse the CFG to detect cycles `UsersDominator` would be part of.
132 SmallPtrSet<BasicBlock *, 8> TransitiveSuccessors;
133 SmallVector<BasicBlock *> WorkList(successors(BB: UsersDominator));
134 bool HasCycle = false;
135 while (!WorkList.empty()) {
136 BasicBlock *CurrBB = WorkList.pop_back_val();
137 if (CurrBB == UsersDominator)
138 // No early exit because we want to compute the full set of transitive
139 // successors.
140 HasCycle = true;
141 for (BasicBlock *Successor : successors(BB: CurrBB)) {
142 if (!TransitiveSuccessors.insert(Ptr: Successor).second)
143 continue;
144 WorkList.push_back(Elt: Successor);
145 }
146 }
147
148 // Don't insert if that could create multiple execution of I,
149 // but we can insert it in the non back-edge predecessors, if it exists.
150 if (HasCycle) {
151 BasicBlock *UsersDominatorHead = UsersDominator;
152 while (BasicBlock *UniquePredecessor =
153 UsersDominatorHead->getUniquePredecessor())
154 UsersDominatorHead = UniquePredecessor;
155
156 if (UsersDominatorHead == &EntryBB)
157 continue;
158
159 BasicBlock *DominatingPredecessor = nullptr;
160 for (BasicBlock *Pred : predecessors(BB: UsersDominatorHead)) {
161 // If one of the predecessor of the dominator also transitively is a
162 // successor, moving to the dominator would do the inverse of loop
163 // hoisting, and we don't want that.
164 if (TransitiveSuccessors.count(Ptr: Pred))
165 continue;
166
167 if (!DT.isReachableFromEntry(A: Pred))
168 continue;
169
170 DominatingPredecessor =
171 DominatingPredecessor
172 ? DT.findNearestCommonDominator(A: DominatingPredecessor, B: Pred)
173 : Pred;
174 }
175
176 if (!DominatingPredecessor || DominatingPredecessor == &EntryBB)
177 continue;
178
179 UsersDominator = DominatingPredecessor;
180 }
181
182 // CatchSwitchInst blocks can only have one instruction, so they are not
183 // good candidates for insertion.
184 while (isa<CatchSwitchInst>(Val: UsersDominator->getFirstNonPHI())) {
185 for (BasicBlock *Pred : predecessors(BB: UsersDominator))
186 if (DT.isReachableFromEntry(A: Pred))
187 UsersDominator = DT.findNearestCommonDominator(A: UsersDominator, B: Pred);
188 }
189
190 // We finally found a place where I can be moved while not introducing extra
191 // execution, and guarded by at least one condition.
192 if (UsersDominator != &EntryBB)
193 JobList.emplace_back(Args: &I, Args&: UsersDominator);
194 }
195
196 //
197 // Perform the actual substitution.
198 //
199 if (JobList.empty())
200 return false;
201
202 MemorySSAUpdater MSSAU(&MSSA);
203
204 // Reverse insertion to respect relative order between instructions:
205 // if two instructions are moved from the same BB to the same BB, we insert
206 // the second one in the front, then the first on top of it.
207 for (auto &Job : reverse(C&: JobList)) {
208 Job.first->moveBefore(BB&: *Job.second, I: Job.second->getFirstInsertionPt());
209 MSSAU.moveToPlace(What: MSSA.getMemoryAccess(I: Job.first), BB: Job.first->getParent(),
210 Where: MemorySSA::InsertionPlace::Beginning);
211 }
212
213 if (VerifyMemorySSA)
214 MSSA.verifyMemorySSA();
215
216 NumMoved += JobList.size();
217
218 return true;
219}
220
221PreservedAnalyses MoveAutoInitPass::run(Function &F,
222 FunctionAnalysisManager &AM) {
223
224 auto &DT = AM.getResult<DominatorTreeAnalysis>(IR&: F);
225 auto &MSSA = AM.getResult<MemorySSAAnalysis>(IR&: F).getMSSA();
226 if (!runMoveAutoInit(F, DT, MSSA))
227 return PreservedAnalyses::all();
228
229 PreservedAnalyses PA;
230 PA.preserve<DominatorTreeAnalysis>();
231 PA.preserve<MemorySSAAnalysis>();
232 PA.preserveSet<CFGAnalyses>();
233 return PA;
234}
235