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() =
default;
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; }
89 bool operator==(
const CVPLatticeVal &RHS)
const {
90 return LatticeState ==
RHS.LatticeState && Functions ==
RHS.Functions;
93 bool operator!=(
const CVPLatticeVal &RHS)
const {
94 return LatticeState !=
RHS.LatticeState || Functions !=
RHS.Functions;
99 CVPLatticeStateTy LatticeState =
Undefined;
108 std::vector<Function *> Functions;
121 CVPLatticeVal(CVPLatticeVal::Overdefined),
122 CVPLatticeVal(CVPLatticeVal::Untracked)) {}
126 switch (
Key.getInt()) {
127 case IPOGrouping::Register:
128 if (isa<Instruction>(
Key.getPointer())) {
130 }
else if (
auto *
A = dyn_cast<Argument>(
Key.getPointer())) {
133 }
else if (
auto *
C = dyn_cast<Constant>(
Key.getPointer())) {
134 return computeConstant(
C);
137 case IPOGrouping::Memory:
138 case IPOGrouping::Return:
139 if (
auto *GV = dyn_cast<GlobalVariable>(
Key.getPointer())) {
141 return computeConstant(GV->getInitializer());
142 }
else if (
auto *
F = cast<Function>(
Key.getPointer()))
154 CVPLatticeVal
MergeValues(CVPLatticeVal
X, CVPLatticeVal
Y)
override {
159 std::vector<Function *>
Union;
160 std::set_union(
X.getFunctions().begin(),
X.getFunctions().end(),
161 Y.getFunctions().begin(),
Y.getFunctions().end(),
162 std::back_inserter(Union), CVPLatticeVal::Compare{});
165 return CVPLatticeVal(std::move(Union));
175 switch (
I.getOpcode()) {
176 case Instruction::Call:
177 case Instruction::Invoke:
178 return visitCallBase(cast<CallBase>(
I), ChangedValues, SS);
179 case Instruction::Load:
180 return visitLoad(*cast<LoadInst>(&
I), ChangedValues, SS);
181 case Instruction::Ret:
182 return visitReturn(*cast<ReturnInst>(&
I), ChangedValues, SS);
183 case Instruction::Select:
184 return visitSelect(*cast<SelectInst>(&
I), ChangedValues, SS);
185 case Instruction::Store:
186 return visitStore(*cast<StoreInst>(&
I), ChangedValues, SS);
188 return visitInst(
I, ChangedValues, SS);
206 if (
Key.getInt() == IPOGrouping::Register)
208 else if (
Key.getInt() == IPOGrouping::Memory)
210 else if (
Key.getInt() == IPOGrouping::Return)
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});
246 if (
F->getReturnType()->isVoidTy())
248 auto RegI = CVPLatticeKey(
I.getReturnValue(), IPOGrouping::Register);
249 auto RetF = CVPLatticeKey(
F, IPOGrouping::Return);
250 ChangedValues[RetF] =
262 auto RegI = CVPLatticeKey(&CB, IPOGrouping::Register);
267 IndirectCalls.
insert(&CB);
281 SS.MarkBlockExecutable(&
F->front());
282 auto RetF = CVPLatticeKey(
F, IPOGrouping::Return);
284 auto RegFormal = CVPLatticeKey(&
A, IPOGrouping::Register);
286 CVPLatticeKey(CB.
getArgOperand(
A.getArgNo()), IPOGrouping::Register);
287 ChangedValues[RegFormal] =
296 ChangedValues[RegI] =
305 auto RegI = CVPLatticeKey(&
I, IPOGrouping::Register);
306 auto RegT = CVPLatticeKey(
I.getTrueValue(), IPOGrouping::Register);
307 auto RegF = CVPLatticeKey(
I.getFalseValue(), IPOGrouping::Register);
308 ChangedValues[RegI] =
318 auto RegI = CVPLatticeKey(&
I, IPOGrouping::Register);
319 if (
auto *GV = dyn_cast<GlobalVariable>(
I.getPointerOperand())) {
320 auto MemGV = CVPLatticeKey(GV, IPOGrouping::Memory);
321 ChangedValues[RegI] =
334 auto *GV = dyn_cast<GlobalVariable>(
I.getPointerOperand());
337 auto RegI = CVPLatticeKey(
I.getValueOperand(), IPOGrouping::Register);
338 auto MemGV = CVPLatticeKey(GV, IPOGrouping::Memory);
339 ChangedValues[MemGV] =
351 auto RegI = CVPLatticeKey(&
I, IPOGrouping::Register);
363 return Key.getPointer();
366 return CVPLatticeKey(V, IPOGrouping::Register);
373 CVPLatticeFunc Lattice;
388 bool Changed =
false;
390 for (
CallBase *
C : Lattice.getIndirectCalls()) {
391 auto RegI = CVPLatticeKey(
C->getCalledOperand(), IPOGrouping::Register);
393 if (!LV.isFunctionSet() || LV.getFunctions().empty())
396 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.
static CVPLatticeKey getLatticeKeyFromValue(Value *V)
static Value * getValueFromLatticeKey(CVPLatticeKey Key)
A template for translating between LLVM Values and LatticeKeys.