1//===-- MoveAutoInit.cpp - move auto-init inst closer to their use site----===//
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 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.
12//===----------------------------------------------------------------------===//
29 #define DEBUG_TYPE "move-auto-init"
31 STATISTIC(NumMoved,
"Number of instructions moved");
35 cl::desc(
"Maximum instructions to analyze per moved initialization"));
38 return I.hasMetadata(LLVMContext::MD_annotation) &&
39 any_of(
I.getMetadata(LLVMContext::MD_annotation)->operands(),
40 [](
const MDOperand &
Op) { return Op.equalsStr(
"auto-init"); });
58/// Finds a BasicBlock in the CFG where instruction `I` can be moved to while
59/// not changing the Memory SSA ordering and being guarded by at least one
72 while (!WorkList.
empty()) {
74 if (!Visited.
insert(MA).second)
80 bool FoundClobberingUser =
false;
84 // If this memory instruction may not clobber `I`, we can skip it.
85 // LifetimeEnd is a valid user, but we do not want it in the user
88 !
MI->isLifetimeStartOrEnd() &&
MI !=
I) {
89 FoundClobberingUser =
true;
90 CurrentDominator = CurrentDominator
96 if (!FoundClobberingUser) {
97 auto UsersAsMemoryAccesses =
map_range(MA->
users(), AsMemoryAccess);
101 return CurrentDominator;
109 // Compute movable instructions.
126 if (UsersDominator == &EntryBB)
129 // Traverse the CFG to detect cycles `UsersDominator` would be part of.
132 bool HasCycle =
false;
133 while (!WorkList.
empty()) {
135 if (CurrBB == UsersDominator)
136 // No early exit because we want to compute the full set of transitive
146 // Don't insert if that could create multiple execution of I,
147 // but we can insert it in the non back-edge predecessors, if it exists.
149 BasicBlock *UsersDominatorHead = UsersDominator;
152 UsersDominatorHead = UniquePredecessor;
154 if (UsersDominatorHead == &EntryBB)
159 // If one of the predecessor of the dominator also transitively is a
160 // successor, moving to the dominator would do the inverse of loop
161 // hoisting, and we don't want that.
162 if (TransitiveSuccessors.
count(Pred))
168 DominatingPredecessor =
169 DominatingPredecessor
174 if (!DominatingPredecessor || DominatingPredecessor == &EntryBB)
177 UsersDominator = DominatingPredecessor;
180 // CatchSwitchInst blocks can only have one instruction, so they are not
181 // good candidates for insertion.
188 // We finally found a place where I can be moved while not introducing extra
189 // execution, and guarded by at least one condition.
190 if (UsersDominator != &EntryBB)
195 // Perform the actual substitution.
202 // Reverse insertion to respect relative order between instructions:
203 // if two instructions are moved from the same BB to the same BB, we insert
204 // the second one in the front, then the first on top of it.
205 for (
auto &Job :
reverse(JobList)) {
206 Job.first->moveBefore(*Job.second, Job.second->getFirstInsertionPt());
214 NumMoved += JobList.
size();
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 defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
LLVM Basic Block Representation.
LLVM_ABI InstListType::const_iterator getFirstNonPHIIt() const
Returns an iterator to the first instruction in this block that is not a PHINode instruction.
LLVM_ABI const BasicBlock * getUniquePredecessor() const
Return the predecessor of this block if it has a unique predecessor block.
This class is a wrapper over an AAResults, and it is intended to be used only when there are no IR ch...
Represents analyses that only rely on functions' control flow.
Analysis pass which computes a DominatorTree.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
LLVM_ABI bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
LLVM_ABI 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...
Tracking metadata reference owned by Metadata.
Representation for a specific memory location.
static LLVM_ABI MemoryLocation get(const LoadInst *LI)
Return a location with information about the memory reference by the given instruction.
static LLVM_ABI 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.
LLVM_ABI void moveToPlace(MemoryUseOrDef *What, BasicBlock *BB, MemorySSA::InsertionPlace Where)
Encapsulates MemorySSA, including all data associated with memory accesses.
LLVM_ABI void verifyMemorySSA(VerificationLevel=VerificationLevel::Fast) const
Verify that MemorySSA is self consistent (IE definitions dominate all uses, uses appear in the right ...
MemoryUseOrDef * getMemoryAccess(const Instruction *I) const
Given a memory Mod/Ref'ing instruction, get the MemorySSA access associated with it.
Class that has the common methods + fields of memory uses/defs.
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
A set of analyses that are preserved following a run of a transformation pass.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
PreservedAnalyses & preserveSet()
Mark an analysis set as preserved.
PreservedAnalyses & preserve()
Mark an analysis as preserved.
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
reference emplace_back(ArgTypes &&... Args)
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
iterator_range< user_iterator > users()
const ParentTy * getParent() const
Abstract Attribute helper functions.
initializer< Ty > init(const Ty &Val)
This is an optimization pass for GlobalISel generic memory operations.
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
auto successors(const MachineBasicBlock *BB)
void append_range(Container &C, Range &&R)
Wrapper function to append range R to container C.
auto map_range(ContainerTy &&C, FuncTy F)
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
auto reverse(ContainerTy &&C)
bool isa(const From &Val)
isa<X> - Return true if the parameter to the template is an instance of one of the template type argu...
@ NoModRef
The access neither references nor modifies the value stored in memory.
LLVM_ABI bool VerifyMemorySSA
Enables verification of MemorySSA.
DWARFExpression::Operation Op
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
auto predecessors(const MachineBasicBlock *BB)
AnalysisManager< Function > FunctionAnalysisManager
Convenience typedef for the Function analysis manager.
LLVM_ABI const Value * getUnderlyingObject(const Value *V, unsigned MaxLookup=MaxLookupSearchDepth)
This method strips off any GEP address adjustments, pointer casts or llvm.threadlocal....