29#define DEBUG_TYPE "called-value-propagation"
40 cl::desc(
"The maximum number of functions to track per lattice value"));
61 enum CVPLatticeStateTy {
Undefined, FunctionSet, Overdefined, Untracked };
71 CVPLatticeVal() =
default;
72 CVPLatticeVal(CVPLatticeStateTy LatticeState) : LatticeState(LatticeState) {}
73 CVPLatticeVal(std::vector<Function *> &&Functions)
74 : LatticeState(FunctionSet), Functions(
std::
move(Functions)) {
80 const std::vector<Function *> &getFunctions()
const {
85 bool isFunctionSet()
const {
return LatticeState == FunctionSet; }
87 bool operator==(
const CVPLatticeVal &RHS)
const {
88 return LatticeState ==
RHS.LatticeState && Functions ==
RHS.Functions;
91 bool operator!=(
const CVPLatticeVal &RHS)
const {
92 return LatticeState !=
RHS.LatticeState || Functions !=
RHS.Functions;
97 CVPLatticeStateTy LatticeState =
Undefined;
106 std::vector<Function *> Functions;
119 CVPLatticeVal(CVPLatticeVal::Overdefined),
120 CVPLatticeVal(CVPLatticeVal::Untracked)) {}
124 switch (
Key.getInt()) {
125 case IPOGrouping::Register:
126 if (isa<Instruction>(
Key.getPointer())) {
128 }
else if (
auto *
A = dyn_cast<Argument>(
Key.getPointer())) {
131 }
else if (
auto *
C = dyn_cast<Constant>(
Key.getPointer())) {
132 return computeConstant(
C);
135 case IPOGrouping::Memory:
136 case IPOGrouping::Return:
137 if (
auto *GV = dyn_cast<GlobalVariable>(
Key.getPointer())) {
139 return computeConstant(GV->getInitializer());
140 }
else if (
auto *
F = cast<Function>(
Key.getPointer()))
152 CVPLatticeVal
MergeValues(CVPLatticeVal
X, CVPLatticeVal
Y)
override {
157 std::vector<Function *>
Union;
158 std::set_union(
X.getFunctions().begin(),
X.getFunctions().end(),
159 Y.getFunctions().begin(),
Y.getFunctions().end(),
160 std::back_inserter(Union), CVPLatticeVal::Compare{});
163 return CVPLatticeVal(std::move(Union));
173 switch (
I.getOpcode()) {
174 case Instruction::Call:
175 case Instruction::Invoke:
176 return visitCallBase(cast<CallBase>(
I), ChangedValues, SS);
177 case Instruction::Load:
178 return visitLoad(*cast<LoadInst>(&
I), ChangedValues, SS);
179 case Instruction::Ret:
180 return visitReturn(*cast<ReturnInst>(&
I), ChangedValues, SS);
181 case Instruction::Select:
182 return visitSelect(*cast<SelectInst>(&
I), ChangedValues, SS);
183 case Instruction::Store:
184 return visitStore(*cast<StoreInst>(&
I), ChangedValues, SS);
186 return visitInst(
I, ChangedValues, SS);
204 if (
Key.getInt() == IPOGrouping::Register)
206 else if (
Key.getInt() == IPOGrouping::Memory)
208 else if (
Key.getInt() == IPOGrouping::Return)
210 if (isa<Function>(
Key.getPointer()))
211 OS <<
Key.getPointer()->getName();
213 OS << *
Key.getPointer();
230 CVPLatticeVal computeConstant(
Constant *
C) {
231 if (isa<ConstantPointerNull>(
C))
232 return CVPLatticeVal(CVPLatticeVal::FunctionSet);
233 if (
auto *
F = dyn_cast<Function>(
C->stripPointerCasts()))
234 return CVPLatticeVal({
F});
244 if (
F->getReturnType()->isVoidTy())
246 auto RegI = CVPLatticeKey(
I.getReturnValue(), IPOGrouping::Register);
247 auto RetF = CVPLatticeKey(
F, IPOGrouping::Return);
248 ChangedValues[RetF] =
260 auto RegI = CVPLatticeKey(&CB, IPOGrouping::Register);
265 IndirectCalls.
insert(&CB);
279 SS.MarkBlockExecutable(&
F->front());
280 auto RetF = CVPLatticeKey(
F, IPOGrouping::Return);
282 auto RegFormal = CVPLatticeKey(&
A, IPOGrouping::Register);
284 CVPLatticeKey(CB.
getArgOperand(
A.getArgNo()), IPOGrouping::Register);
285 ChangedValues[RegFormal] =
294 ChangedValues[RegI] =
303 auto RegI = CVPLatticeKey(&
I, IPOGrouping::Register);
304 auto RegT = CVPLatticeKey(
I.getTrueValue(), IPOGrouping::Register);
305 auto RegF = CVPLatticeKey(
I.getFalseValue(), IPOGrouping::Register);
306 ChangedValues[RegI] =
316 auto RegI = CVPLatticeKey(&
I, IPOGrouping::Register);
317 if (
auto *GV = dyn_cast<GlobalVariable>(
I.getPointerOperand())) {
318 auto MemGV = CVPLatticeKey(GV, IPOGrouping::Memory);
319 ChangedValues[RegI] =
332 auto *GV = dyn_cast<GlobalVariable>(
I.getPointerOperand());
335 auto RegI = CVPLatticeKey(
I.getValueOperand(), IPOGrouping::Register);
336 auto MemGV = CVPLatticeKey(GV, IPOGrouping::Memory);
337 ChangedValues[MemGV] =
349 auto RegI = CVPLatticeKey(&
I, IPOGrouping::Register);
361 return Key.getPointer();
364 return CVPLatticeKey(V, IPOGrouping::Register);
371 CVPLatticeFunc Lattice;
386 bool Changed =
false;
388 for (
CallBase *
C : Lattice.getIndirectCalls()) {
389 auto RegI = CVPLatticeKey(
C->getCalledOperand(), IPOGrouping::Register);
391 if (!LV.isFunctionSet() || LV.getFunctions().empty())
394 C->setMetadata(LLVMContext::MD_callees, Callees);
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
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.
static bool runCVP(Module &M)
This file contains the declarations for the subclasses of Constant, which represent the different fla...
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
AbstractLatticeFunction - This class is implemented by the dataflow instance to specify what the latt...
LatticeVal getOverdefinedVal() const
virtual void ComputeInstructionState(Instruction &I, DenseMap< LatticeKey, LatticeVal > &ChangedValues, SparseSolver< LatticeKey, LatticeVal > &SS)=0
ComputeInstructionState - Compute the LatticeKeys that change as a result of executing instruction I.
virtual void PrintLatticeKey(LatticeKey Key, raw_ostream &OS)
PrintLatticeKey - Render the given LatticeKey to the specified stream.
virtual void PrintLatticeVal(LatticeVal LV, raw_ostream &OS)
PrintLatticeVal - Render the given LatticeVal to the specified stream.
LatticeVal getUntrackedVal() const
virtual LatticeVal MergeValues(LatticeVal X, LatticeVal Y)
MergeValues - Compute and return the merge of the two specified lattice values.
virtual LatticeVal ComputeLatticeVal(LatticeKey Key)
ComputeLatticeVal - Compute and return a LatticeVal corresponding to the given LatticeKey.
LatticeVal getUndefVal() const
A container for analyses that lazily runs them and caches their results.
This class represents an incoming formal argument to a Function.
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Function * getCalledFunction() const
Returns the function called, or null if this is an indirect function invocation or the function signa...
Value * getArgOperand(unsigned i) const
PreservedAnalyses run(Module &M, ModuleAnalysisManager &)
This is an important base class in LLVM.
An instruction for reading from memory.
MDNode * createCallees(ArrayRef< Function * > Callees)
Return metadata indicating the possible callees of indirect calls.
A Module instance is used to store all the information related to an LLVM module.
PointerIntPair - This class implements a pair of a pointer and small integer.
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.
Wrapper class representing virtual and physical registers.
Return a value (possibly void), from a function.
This class represents the LLVM 'select' instruction.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
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.
SparseSolver - This class is a general purpose solver for Sparse Conditional Propagation with a progr...
void MarkBlockExecutable(BasicBlock *BB)
MarkBlockExecutable - This method can be used by clients to mark all of the blocks that are known to ...
void Solve()
Solve - Solve for constants and executable blocks.
LatticeVal getExistingValueState(LatticeKey Key) const
getExistingValueState - Return the LatticeVal object corresponding to the given value from the ValueS...
An instruction for storing to memory.
bool isVoidTy() const
Return true if this is 'void'.
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
StringRef getName() const
Return a constant reference to the value's name.
This class implements an extremely fast bulk output stream that can only output to a stream.
This class provides various memory handling functions that manipulate MemoryBlock instances.
@ C
The default llvm calling convention, compatible with C.
initializer< Ty > init(const Ty &Val)
This is an optimization pass for GlobalISel generic memory operations.
bool operator!=(uint64_t V1, const APInt &V2)
bool operator==(const AddressRangeValuePair &LHS, const AddressRangeValuePair &RHS)
bool canTrackGlobalVariableInterprocedurally(GlobalVariable *GV)
Determine if the value maintained in the given global variable can be tracked interprocedurally.
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...
bool canTrackReturnsInterprocedurally(Function *F)
Determine if the values of the given function's returns can be tracked interprocedurally.
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
bool canTrackArgumentsInterprocedurally(Function *F)
Determine if the values of the given function's arguments can be tracked interprocedurally.
Implement std::hash so that hash_code can be used in STL containers.
static CVPLatticeKey getLatticeKeyFromValue(Value *V)
static Value * getValueFromLatticeKey(CVPLatticeKey Key)
A template for translating between LLVM Values and LatticeKeys.