Go to the documentation of this file.
31 #define DEBUG_TYPE "called-value-propagation"
42 cl::desc(
"The maximum number of functions to track per lattice value"));
63 enum CVPLatticeStateTy {
Undefined, FunctionSet, Overdefined, Untracked };
73 CVPLatticeVal() : LatticeState(
Undefined) {}
74 CVPLatticeVal(CVPLatticeStateTy LatticeState) : LatticeState(LatticeState) {}
75 CVPLatticeVal(std::vector<Function *> &&Functions)
76 : LatticeState(FunctionSet), Functions(
std::
move(Functions)) {
82 const std::vector<Function *> &getFunctions()
const {
87 bool isFunctionSet()
const {
return LatticeState == FunctionSet; }
90 return LatticeState ==
RHS.LatticeState && Functions ==
RHS.Functions;
94 return LatticeState !=
RHS.LatticeState || Functions !=
RHS.Functions;
99 CVPLatticeStateTy LatticeState;
108 std::vector<Function *> Functions;
121 CVPLatticeVal(CVPLatticeVal::Overdefined),
122 CVPLatticeVal(CVPLatticeVal::Untracked)) {}
125 CVPLatticeVal ComputeLatticeVal(CVPLatticeKey
Key)
override {
126 switch (
Key.getInt()) {
128 if (isa<Instruction>(
Key.getPointer())) {
129 return getUndefVal();
130 }
else if (
auto *A = dyn_cast<Argument>(
Key.getPointer())) {
132 return getUndefVal();
133 }
else if (
auto *
C = dyn_cast<Constant>(
Key.getPointer())) {
134 return computeConstant(
C);
136 return getOverdefinedVal();
137 case IPOGrouping::Memory:
139 if (
auto *GV = dyn_cast<GlobalVariable>(
Key.getPointer())) {
141 return computeConstant(GV->getInitializer());
142 }
else if (
auto *
F = cast<Function>(
Key.getPointer()))
144 return getUndefVal();
146 return getOverdefinedVal();
154 CVPLatticeVal MergeValues(CVPLatticeVal
X, CVPLatticeVal
Y)
override {
155 if (
X == getOverdefinedVal() ||
Y == getOverdefinedVal())
156 return getOverdefinedVal();
157 if (
X == getUndefVal() &&
Y == getUndefVal())
158 return getUndefVal();
159 std::vector<Function *>
Union;
161 Y.getFunctions().begin(),
Y.getFunctions().end(),
164 return getOverdefinedVal();
172 void ComputeInstructionState(
175 switch (
I.getOpcode()) {
177 case Instruction::Invoke:
178 return visitCallBase(cast<CallBase>(
I), ChangedValues,
SS);
180 return visitLoad(*cast<LoadInst>(&
I), ChangedValues,
SS);
182 return visitReturn(*cast<ReturnInst>(&
I), ChangedValues,
SS);
184 return visitSelect(*cast<SelectInst>(&
I), ChangedValues,
SS);
186 return visitStore(*cast<StoreInst>(&
I), ChangedValues,
SS);
188 return visitInst(
I, ChangedValues,
SS);
193 void PrintLatticeVal(CVPLatticeVal LV,
raw_ostream &OS)
override {
194 if (LV == getUndefVal())
196 else if (LV == getOverdefinedVal())
198 else if (LV == getUntrackedVal())
205 void PrintLatticeKey(CVPLatticeKey
Key,
raw_ostream &OS)
override {
208 else if (
Key.getInt() == IPOGrouping::Memory)
212 if (isa<Function>(
Key.getPointer()))
213 OS <<
Key.getPointer()->getName();
215 OS << *
Key.getPointer();
232 CVPLatticeVal computeConstant(
Constant *
C) {
233 if (isa<ConstantPointerNull>(
C))
234 return CVPLatticeVal(CVPLatticeVal::FunctionSet);
235 if (
auto *
F = dyn_cast<Function>(
C->stripPointerCasts()))
236 return CVPLatticeVal({
F});
237 return getOverdefinedVal();
246 if (
F->getReturnType()->isVoidTy())
250 ChangedValues[RetF] =
251 MergeValues(
SS.getValueState(RegI),
SS.getValueState(RetF));
267 IndirectCalls.
insert(&CB);
275 ChangedValues[RegI] = getOverdefinedVal();
281 SS.MarkBlockExecutable(&
F->front());
287 ChangedValues[RegFormal] =
288 MergeValues(
SS.getValueState(RegFormal),
SS.getValueState(RegActual));
296 ChangedValues[RegI] =
297 MergeValues(
SS.getValueState(RegI),
SS.getValueState(RetF));
308 ChangedValues[RegI] =
309 MergeValues(
SS.getValueState(RegT),
SS.getValueState(RegF));
319 if (
auto *GV = dyn_cast<GlobalVariable>(
I.getPointerOperand())) {
320 auto MemGV = CVPLatticeKey(GV, IPOGrouping::Memory);
321 ChangedValues[RegI] =
322 MergeValues(
SS.getValueState(RegI),
SS.getValueState(MemGV));
324 ChangedValues[RegI] = getOverdefinedVal();
334 auto *GV = dyn_cast<GlobalVariable>(
I.getPointerOperand());
338 auto MemGV = CVPLatticeKey(GV, IPOGrouping::Memory);
339 ChangedValues[MemGV] =
340 MergeValues(
SS.getValueState(RegI),
SS.getValueState(MemGV));
352 ChangedValues[RegI] = getOverdefinedVal();
363 return Key.getPointer();
373 CVPLatticeFunc Lattice;
388 bool Changed =
false;
390 for (
CallBase *
C : Lattice.getIndirectCalls()) {
393 if (!LV.isFunctionSet() || LV.getFunctions().empty())
396 C->setMetadata(LLVMContext::MD_callees, Callees);
410 class CalledValuePropagationLegacyPass :
public ModulePass {
423 bool runOnModule(
Module &M)
override {
433 "Called Value Propagation",
false,
false)
436 return new CalledValuePropagationLegacyPass();
A set of analyses that are preserved following a run of a transformation pass.
static cl::opt< unsigned > MaxFunctionsPerValue("cvp-max-functions-per-value", cl::Hidden, cl::init(4), cl::desc("The maximum number of functions to track per lattice value"))
The maximum number of functions to track per lattice value.
This class represents an incoming formal argument to a Function.
This is an optimization pass for GlobalISel generic memory operations.
PreservedAnalyses run(Module &M, ModuleAnalysisManager &)
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
Return a value (possibly void), from a function.
ModulePass class - This class is used to implement unstructured interprocedural optimizations and ana...
bool set_union(S1Ty &S1, const S2Ty &S2)
set_union(A, B) - Compute A := A u B, return whether A changed.
static Value * getValueFromLatticeKey(CVPLatticeKey Key)
bool operator!=(uint64_t V1, const APInt &V2)
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
static bool runCVP(Module &M)
AbstractLatticeFunction - This class is implemented by the dataflow instance to specify what the latt...
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
INITIALIZE_PASS(CalledValuePropagationLegacyPass, "called-value-propagation", "Called Value Propagation", false, false) ModulePass *llvm
void Solve()
Solve - Solve for constants and executable blocks.
(vector float) vec_cmpeq(*A, *B) C
Function * getCalledFunction() const
Returns the function called, or null if this is an indirect function invocation or the function signa...
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
Represent the analysis usage information of a pass.
This class implements an extremely fast bulk output stream that can only output to a stream.
A template for translating between LLVM Values and LatticeKeys.
bool canTrackGlobalVariableInterprocedurally(GlobalVariable *GV)
Determine if the value maintained in the given global variable can be tracked interprocedurally.
Promote Memory to Register
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
An instruction for storing to memory.
This is an important base class in LLVM.
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
initializer< Ty > init(const Ty &Val)
static CVPLatticeKey getLatticeKeyFromValue(Value *V)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
bool operator==(uint64_t V1, const APInt &V2)
This class represents the LLVM 'select' instruction.
bool isVoidTy() const
Return true if this is 'void'.
A Module instance is used to store all the information related to an LLVM module.
QP Compare Ordered outs ins xscmpudp No builtin are required Or llvm fcmp order unorder compare DP QP Compare builtin are required DP Compare
This class provides various memory handling functions that manipulate MemoryBlock instances.
Type * getType() const
All values are typed, get the type of this value.
void initializeCalledValuePropagationLegacyPassPass(PassRegistry &)
ModulePass * createCalledValuePropagationPass()
createCalledValuePropagationPass - Attach metadata to indirct call sites indicating the set of functi...
StringRef getName() const
Return a constant reference to the value's name.
An instruction for reading from memory.
Wrapper class representing virtual and physical registers.
void setPreservesAll()
Set by analyses that do not transform their input at all.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
void MarkBlockExecutable(BasicBlock *BB)
MarkBlockExecutable - This method can be used by clients to mark all of the blocks that are known to ...
bool is_sorted(R &&Range, Compare C)
Wrapper function around std::is_sorted to check if elements in a range R are sorted with respect to a...
PointerIntPair - This class implements a pair of a pointer and small integer.
MDNode * createCallees(ArrayRef< Function * > Callees)
Return metadata indicating the possible callees of indirect calls.
bool canTrackArgumentsInterprocedurally(Function *F)
Determine if the values of the given function's arguments can be tracked interprocedurally.
Value * getArgOperand(unsigned i) const
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
A container for analyses that lazily runs them and caches their results.
LatticeVal getExistingValueState(LatticeKey Key) const
getExistingValueState - Return the LatticeVal object corresponding to the given value from the ValueS...
LLVM Value Representation.
SparseSolver - This class is a general purpose solver for Sparse Conditional Propagation with a progr...
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
bool canTrackReturnsInterprocedurally(Function *F)
Determine if the values of the given function's returns can be tracked interprocedurally.