LLVM 18.0.0git
MoveAutoInit.cpp
Go to the documentation of this file.
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
15#include "llvm/ADT/STLExtras.h"
16#include "llvm/ADT/Statistic.h"
17#include "llvm/ADT/StringSet.h"
21#include "llvm/IR/DebugInfo.h"
22#include "llvm/IR/Dominators.h"
23#include "llvm/IR/IRBuilder.h"
29
30using namespace llvm;
31
32#define DEBUG_TYPE "move-auto-init"
33
34STATISTIC(NumMoved, "Number of instructions moved");
35
37 "move-auto-init-threshold", cl::Hidden, cl::init(128),
38 cl::desc("Maximum instructions to analyze per moved initialization"));
39
40static bool hasAutoInitMetadata(const Instruction &I) {
41 return I.hasMetadata(LLVMContext::MD_annotation) &&
42 any_of(I.getMetadata(LLVMContext::MD_annotation)->operands(),
43 [](const MDOperand &Op) { return Op.equalsStr("auto-init"); });
44}
45
46static std::optional<MemoryLocation> writeToAlloca(const Instruction &I) {
48 if (auto *MI = dyn_cast<MemIntrinsic>(&I))
50 else if (auto *SI = dyn_cast<StoreInst>(&I))
52 else
53 return std::nullopt;
54
55 if (isa<AllocaInst>(getUnderlyingObject(ML.Ptr)))
56 return ML;
57 else
58 return {};
59}
60
61/// Finds a BasicBlock in the CFG where instruction `I` can be moved to while
62/// not changing the Memory SSA ordering and being guarded by at least one
63/// condition.
65 DominatorTree &DT, MemorySSA &MSSA) {
66 BasicBlock *CurrentDominator = nullptr;
67 MemoryUseOrDef &IMA = *MSSA.getMemoryAccess(I);
68 BatchAAResults AA(MSSA.getAA());
69
71
72 auto AsMemoryAccess = [](User *U) { return cast<MemoryAccess>(U); };
73 SmallVector<MemoryAccess *> WorkList(map_range(IMA.users(), AsMemoryAccess));
74
75 while (!WorkList.empty()) {
76 MemoryAccess *MA = WorkList.pop_back_val();
77 if (!Visited.insert(MA).second)
78 continue;
79
80 if (Visited.size() > MoveAutoInitThreshold)
81 return nullptr;
82
83 bool FoundClobberingUser = false;
84 if (auto *M = dyn_cast<MemoryUseOrDef>(MA)) {
85 Instruction *MI = M->getMemoryInst();
86
87 // If this memory instruction may not clobber `I`, we can skip it.
88 // LifetimeEnd is a valid user, but we do not want it in the user
89 // dominator.
90 if (AA.getModRefInfo(MI, ML) != ModRefInfo::NoModRef &&
91 !MI->isLifetimeStartOrEnd() && MI != I) {
92 FoundClobberingUser = true;
93 CurrentDominator = CurrentDominator
94 ? DT.findNearestCommonDominator(CurrentDominator,
95 MI->getParent())
96 : MI->getParent();
97 }
98 }
99 if (!FoundClobberingUser) {
100 auto UsersAsMemoryAccesses = map_range(MA->users(), AsMemoryAccess);
101 append_range(WorkList, UsersAsMemoryAccesses);
102 }
103 }
104 return CurrentDominator;
105}
106
108 BasicBlock &EntryBB = F.getEntryBlock();
110
111 //
112 // Compute movable instructions.
113 //
114 for (Instruction &I : EntryBB) {
116 continue;
117
118 std::optional<MemoryLocation> ML = writeToAlloca(I);
119 if (!ML)
120 continue;
121
122 if (I.isVolatile())
123 continue;
124
125 BasicBlock *UsersDominator = usersDominator(ML.value(), &I, DT, MSSA);
126 if (!UsersDominator)
127 continue;
128
129 if (UsersDominator == &EntryBB)
130 continue;
131
132 // Traverse the CFG to detect cycles `UsersDominator` would be part of.
133 SmallPtrSet<BasicBlock *, 8> TransitiveSuccessors;
134 SmallVector<BasicBlock *> WorkList(successors(UsersDominator));
135 bool HasCycle = false;
136 while (!WorkList.empty()) {
137 BasicBlock *CurrBB = WorkList.pop_back_val();
138 if (CurrBB == UsersDominator)
139 // No early exit because we want to compute the full set of transitive
140 // successors.
141 HasCycle = true;
142 for (BasicBlock *Successor : successors(CurrBB)) {
143 if (!TransitiveSuccessors.insert(Successor).second)
144 continue;
145 WorkList.push_back(Successor);
146 }
147 }
148
149 // Don't insert if that could create multiple execution of I,
150 // but we can insert it in the non back-edge predecessors, if it exists.
151 if (HasCycle) {
152 BasicBlock *UsersDominatorHead = UsersDominator;
153 while (BasicBlock *UniquePredecessor =
154 UsersDominatorHead->getUniquePredecessor())
155 UsersDominatorHead = UniquePredecessor;
156
157 if (UsersDominatorHead == &EntryBB)
158 continue;
159
160 BasicBlock *DominatingPredecessor = nullptr;
161 for (BasicBlock *Pred : predecessors(UsersDominatorHead)) {
162 // If one of the predecessor of the dominator also transitively is a
163 // successor, moving to the dominator would do the inverse of loop
164 // hoisting, and we don't want that.
165 if (TransitiveSuccessors.count(Pred))
166 continue;
167
168 DominatingPredecessor =
169 DominatingPredecessor
170 ? DT.findNearestCommonDominator(DominatingPredecessor, Pred)
171 : Pred;
172 }
173
174 if (!DominatingPredecessor || DominatingPredecessor == &EntryBB)
175 continue;
176
177 UsersDominator = DominatingPredecessor;
178 }
179
180 // CatchSwitchInst blocks can only have one instruction, so they are not
181 // good candidates for insertion.
182 while (isa<CatchSwitchInst>(UsersDominator->getFirstInsertionPt())) {
183 for (BasicBlock *Pred : predecessors(UsersDominator))
184 UsersDominator = DT.findNearestCommonDominator(UsersDominator, Pred);
185 }
186
187 // We finally found a place where I can be moved while not introducing extra
188 // execution, and guarded by at least one condition.
189 if (UsersDominator != &EntryBB)
190 JobList.emplace_back(&I, UsersDominator);
191 }
192
193 //
194 // Perform the actual substitution.
195 //
196 if (JobList.empty())
197 return false;
198
199 MemorySSAUpdater MSSAU(&MSSA);
200
201 // Reverse insertion to respect relative order between instructions:
202 // if two instructions are moved from the same BB to the same BB, we insert
203 // the second one in the front, then the first on top of it.
204 for (auto &Job : reverse(JobList)) {
205 Job.first->moveBefore(*Job.second, Job.second->getFirstInsertionPt());
206 MSSAU.moveToPlace(MSSA.getMemoryAccess(Job.first), Job.first->getParent(),
207 MemorySSA::InsertionPlace::Beginning);
208 }
209
210 if (VerifyMemorySSA)
211 MSSA.verifyMemorySSA();
212
213 NumMoved += JobList.size();
214
215 return true;
216}
217
220
221 auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
222 auto &MSSA = AM.getResult<MemorySSAAnalysis>(F).getMSSA();
223 if (!runMoveAutoInit(F, DT, MSSA))
224 return PreservedAnalyses::all();
225
230 return PA;
231}
IRTranslator LLVM IR MI
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...
static cl::opt< unsigned > MoveAutoInitThreshold("move-auto-init-threshold", cl::Hidden, cl::init(128), cl::desc("Maximum instructions to analyze per moved initialization"))
static bool runMoveAutoInit(Function &F, DominatorTree &DT, MemorySSA &MSSA)
static BasicBlock * usersDominator(const MemoryLocation &ML, Instruction *I, DominatorTree &DT, MemorySSA &MSSA)
Finds a BasicBlock in the CFG where instruction I can be moved to while not changing the Memory SSA o...
static bool hasAutoInitMetadata(const Instruction &I)
static std::optional< MemoryLocation > writeToAlloca(const Instruction &I)
This file contains some templates that are useful if you are working with the STL at all.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Definition: Statistic.h:167
StringSet - A set-like wrapper for the StringMap.
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:620
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:774
LLVM Basic Block Representation.
Definition: BasicBlock.h:56
const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
Definition: BasicBlock.cpp:257
const BasicBlock * getUniquePredecessor() const
Return the predecessor of this block if it has a unique predecessor block.
Definition: BasicBlock.cpp:304
This class is a wrapper over an AAResults, and it is intended to be used only when there are no IR ch...
ModRefInfo getModRefInfo(const Instruction *I, const std::optional< MemoryLocation > &OptLoc)
Represents analyses that only rely on functions' control flow.
Definition: PassManager.h:113
This class represents an Operation in the Expression.
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:279
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
Instruction * findNearestCommonDominator(Instruction *I1, Instruction *I2) const
Find the nearest instruction I that dominates both I1 and I2, in the sense that a result produced bef...
Definition: Dominators.cpp:344
Tracking metadata reference owned by Metadata.
Definition: Metadata.h:772
Representation for a specific memory location.
static MemoryLocation get(const LoadInst *LI)
Return a location with information about the memory reference by the given instruction.
static MemoryLocation getForDest(const MemIntrinsic *MI)
Return a location representing the destination of a memory set or transfer.
An analysis that produces MemorySSA for a function.
Definition: MemorySSA.h:923
void moveToPlace(MemoryUseOrDef *What, BasicBlock *BB, MemorySSA::InsertionPlace Where)
Encapsulates MemorySSA, including all data associated with memory accesses.
Definition: MemorySSA.h:700
AliasAnalysis & getAA()
Definition: MemorySSA.h:797
void verifyMemorySSA(VerificationLevel=VerificationLevel::Fast) const
Verify that MemorySSA is self consistent (IE definitions dominate all uses, uses appear in the right ...
Definition: MemorySSA.cpp:1857
MemoryUseOrDef * getMemoryAccess(const Instruction *I) const
Given a memory Mod/Ref'ing instruction, get the MemorySSA access associated with it.
Definition: MemorySSA.h:717
Class that has the common methods + fields of memory uses/defs.
Definition: MemorySSA.h:252
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
void preserveSet()
Mark an analysis set as preserved.
Definition: PassManager.h:188
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:173
size_type size() const
Definition: SmallPtrSet.h:93
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:384
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:366
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:451
bool empty() const
Definition: SmallVector.h:94
size_t size() const
Definition: SmallVector.h:91
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:941
void push_back(const T &Elt)
Definition: SmallVector.h:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
iterator_range< user_iterator > users()
Definition: Value.h:421
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:445
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
auto successors(const MachineBasicBlock *BB)
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
Definition: STLExtras.h:2037
const Value * getUnderlyingObject(const Value *V, unsigned MaxLookup=6)
This method strips off any GEP address adjustments and pointer casts from the specified value,...
auto map_range(ContainerTy &&C, FuncTy F)
Definition: STLExtras.h:378
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:1734
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:429
bool VerifyMemorySSA
Enables verification of MemorySSA.
Definition: MemorySSA.cpp:83
auto predecessors(const MachineBasicBlock *BB)