CalledValuePropagation.cpp Source File (original) (raw)

28using namespace llvm;

30#define DEBUG_TYPE "called-value-propagation"

41 cl::desc("The maximum number of functions to track per lattice value"));

43namespace {

57class CVPLatticeVal {

58public:

62 enum CVPLatticeStateTy { Undefined, FunctionSet, Overdefined, Untracked };

66 struct Compare {

67 bool operator()(const Function *LHS, const Function *RHS) const {

69 }

70 };

72 CVPLatticeVal() = default;

73 CVPLatticeVal(CVPLatticeStateTy LatticeState) : LatticeState(LatticeState) {}

74 CVPLatticeVal(std::vector<Function *> &&Functions)

75 : LatticeState(FunctionSet), Functions(std::move(Functions)) {

77 }

81 const std::vector<Function *> &getFunctions() const {

82 return Functions;

83 }

86 bool isFunctionSet() const { return LatticeState == FunctionSet; }

89 return LatticeState == RHS.LatticeState && Functions == RHS.Functions;

90 }

93 return LatticeState != RHS.LatticeState || Functions != RHS.Functions;

94 }

96private:

98 CVPLatticeStateTy LatticeState = Undefined;

100

101

102

103

104

105

106

107 std::vector<Function *> Functions;

108};

109

110

111

112

113

114

115class CVPLatticeFunc

117public:

118 CVPLatticeFunc()

119 : AbstractLatticeFunction(CVPLatticeVal(CVPLatticeVal::Undefined),

120 CVPLatticeVal(CVPLatticeVal::Overdefined),

121 CVPLatticeVal(CVPLatticeVal::Untracked)) {}

122

123

124 CVPLatticeVal ComputeLatticeVal(CVPLatticeKey Key) override {

125 switch (Key.getInt()) {

126 case IPOGrouping::Register:

128 return getUndefVal();

131 return getUndefVal();

133 return computeConstant(C);

134 }

135 return getOverdefinedVal();

136 case IPOGrouping::Memory:

137 case IPOGrouping::Return:

140 return computeConstant(GV->getInitializer());

143 return getUndefVal();

144 }

145 return getOverdefinedVal();

146 }

147

148

149

150

151

152

153 CVPLatticeVal MergeValues(CVPLatticeVal X, CVPLatticeVal Y) override {

154 if (X == getOverdefinedVal() || Y == getOverdefinedVal())

155 return getOverdefinedVal();

156 if (X == getUndefVal() && Y == getUndefVal())

157 return getUndefVal();

158 std::vector<Function *> Union;

159 std::set_union(X.getFunctions().begin(), X.getFunctions().end(),

160 Y.getFunctions().begin(), Y.getFunctions().end(),

161 std::back_inserter(Union), CVPLatticeVal::Compare{});

163 return getOverdefinedVal();

164 return CVPLatticeVal(std::move(Union));

165 }

166

167

168

169

170

171 void ComputeInstructionState(

172 Instruction &I,

173 SmallDenseMap<CVPLatticeKey, CVPLatticeVal, 16> &ChangedValues,

174 SparseSolver<CVPLatticeKey, CVPLatticeVal> &SS) override {

175 switch (I.getOpcode()) {

176 case Instruction::Call:

177 case Instruction::Invoke:

178 return visitCallBase(cast(I), ChangedValues, SS);

179 case Instruction::Load:

180 return visitLoad(*cast(&I), ChangedValues, SS);

181 case Instruction::Ret:

183 case Instruction::Select:

185 case Instruction::Store:

187 default:

188 return visitInst(I, ChangedValues, SS);

189 }

190 }

191

192

193 void PrintLatticeVal(CVPLatticeVal LV, raw_ostream &OS) override {

194 if (LV == getUndefVal())

195 OS << "Undefined ";

196 else if (LV == getOverdefinedVal())

197 OS << "Overdefined";

198 else if (LV == getUntrackedVal())

199 OS << "Untracked ";

200 else

201 OS << "FunctionSet";

202 }

203

204

205 void PrintLatticeKey(CVPLatticeKey Key, raw_ostream &OS) override {

206 if (Key.getInt() == IPOGrouping::Register)

207 OS << " ";

208 else if (Key.getInt() == IPOGrouping::Memory)

209 OS << " ";

210 else if (Key.getInt() == IPOGrouping::Return)

211 OS << " ";

213 OS << Key.getPointer()->getName();

214 else

215 OS << *Key.getPointer();

216 }

217

218

219

220 SmallPtrSetImpl<CallBase *> &getIndirectCalls() { return IndirectCalls; }

221

222private:

223

224

225

226 SmallPtrSet<CallBase *, 32> IndirectCalls;

227

228

229

230

231

232 CVPLatticeVal computeConstant(Constant *C) {

234 return CVPLatticeVal(CVPLatticeVal::FunctionSet);

236 return CVPLatticeVal({F});

237 return getOverdefinedVal();

238 }

239

240

241

242 void

243 visitReturn(ReturnInst &I,

244 SmallDenseMap<CVPLatticeKey, CVPLatticeVal, 16> &ChangedValues,

245 SparseSolver<CVPLatticeKey, CVPLatticeVal> &SS) {

246 Function *F = I.getParent()->getParent();

247 if (F->getReturnType()->isVoidTy())

248 return;

249 auto RegI = CVPLatticeKey(I.getReturnValue(), IPOGrouping::Register);

250 auto RetF = CVPLatticeKey(F, IPOGrouping::Return);

251 ChangedValues[RetF] =

252 MergeValues(SS.getValueState(RegI), SS.getValueState(RetF));

253 }

254

255

256

257

258

259 void

260 visitCallBase(CallBase &CB,

261 SmallDenseMap<CVPLatticeKey, CVPLatticeVal, 16> &ChangedValues,

262 SparseSolver<CVPLatticeKey, CVPLatticeVal> &SS) {

264 auto RegI = CVPLatticeKey(&CB, IPOGrouping::Register);

265

266

267

268 if ()

269 IndirectCalls.insert(&CB);

270

271

273

274

276 return;

277 ChangedValues[RegI] = getOverdefinedVal();

278 return;

279 }

280

281

282

283 SS.MarkBlockExecutable(&F->front());

284 auto RetF = CVPLatticeKey(F, IPOGrouping::Return);

285 for (Argument &A : F->args()) {

286 auto RegFormal = CVPLatticeKey(&A, IPOGrouping::Register);

287 auto RegActual =

288 CVPLatticeKey(CB.getArgOperand(A.getArgNo()), IPOGrouping::Register);

289 ChangedValues[RegFormal] =

290 MergeValues(SS.getValueState(RegFormal), SS.getValueState(RegActual));

291 }

292

293

294

296 return;

297

298 ChangedValues[RegI] =

299 MergeValues(SS.getValueState(RegI), SS.getValueState(RetF));

300 }

301

302

303

304 void

305 visitSelect(SelectInst &I,

306 SmallDenseMap<CVPLatticeKey, CVPLatticeVal, 16> &ChangedValues,

307 SparseSolver<CVPLatticeKey, CVPLatticeVal> &SS) {

308 auto RegI = CVPLatticeKey(&I, IPOGrouping::Register);

309 auto RegT = CVPLatticeKey(I.getTrueValue(), IPOGrouping::Register);

310 auto RegF = CVPLatticeKey(I.getFalseValue(), IPOGrouping::Register);

311 ChangedValues[RegI] =

312 MergeValues(SS.getValueState(RegT), SS.getValueState(RegF));

313 }

314

315

316

317

318 void visitLoad(LoadInst &I,

319 SmallDenseMap<CVPLatticeKey, CVPLatticeVal, 16> &ChangedValues,

320 SparseSolver<CVPLatticeKey, CVPLatticeVal> &SS) {

321 auto RegI = CVPLatticeKey(&I, IPOGrouping::Register);

323 auto MemGV = CVPLatticeKey(GV, IPOGrouping::Memory);

324 ChangedValues[RegI] =

325 MergeValues(SS.getValueState(RegI), SS.getValueState(MemGV));

326 } else {

327 ChangedValues[RegI] = getOverdefinedVal();

328 }

329 }

330

331

332

333

334 void

335 visitStore(StoreInst &I,

336 SmallDenseMap<CVPLatticeKey, CVPLatticeVal, 16> &ChangedValues,

337 SparseSolver<CVPLatticeKey, CVPLatticeVal> &SS) {

339 if (!GV)

340 return;

341 auto RegI = CVPLatticeKey(I.getValueOperand(), IPOGrouping::Register);

342 auto MemGV = CVPLatticeKey(GV, IPOGrouping::Memory);

343 ChangedValues[MemGV] =

344 MergeValues(SS.getValueState(RegI), SS.getValueState(MemGV));

345 }

346

347

348

349 void visitInst(Instruction &I,

350 SmallDenseMap<CVPLatticeKey, CVPLatticeVal, 16> &ChangedValues,

351 SparseSolver<CVPLatticeKey, CVPLatticeVal> &SS) {

352

353 if (I.use_empty())

354 return;

355 auto RegI = CVPLatticeKey(&I, IPOGrouping::Register);

356 ChangedValues[RegI] = getOverdefinedVal();

357 }

358};

359}

360

361namespace llvm {

362

363

364

367 return Key.getPointer();

368 }

370 return CVPLatticeKey(V, IPOGrouping::Register);

371 }

372};

373}

374

376

377 CVPLatticeFunc Lattice;

379

380

381

385

386

387

389

390

391

394 for (CallBase *C : Lattice.getIndirectCalls()) {

395 auto RegI = CVPLatticeKey(C->getCalledOperand(), IPOGrouping::Register);

397 if (!LV.isFunctionSet() || LV.getFunctions().empty())

398 continue;

400 C->setMetadata(LLVMContext::MD_callees, Callees);

402 }

403

405}

406

assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")

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)

Definition CalledValuePropagation.cpp:375

This file contains the declarations for the subclasses of Constant, which represent the different fla...

Module.h This file contains the declarations for the Module class.

static TableGen::Emitter::Opt Y("gen-skeleton-entry", EmitSkeleton, "Generate example skeleton entry")

static TableGen::Emitter::OptClass< SkeletonEmitter > X("gen-skeleton-class", "Generate example skeleton class")

AbstractLatticeFunction - This class is implemented by the dataflow instance to specify what the latt...

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 &)

Definition CalledValuePropagation.cpp:407

LLVM_ABI 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.

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...

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.

LLVM_ABI StringRef getName() const

Return a constant reference to the value's name.

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.

decltype(auto) dyn_cast(const From &Val)

dyn_cast - Return the argument parameter cast to the specified type.

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 isa(const From &Val)

isa - Return true if the parameter to the template is an instance of one of the template type argu...

LLVM_ATTRIBUTE_VISIBILITY_DEFAULT AnalysisKey InnerAnalysisManagerProxy< AnalysisManagerT, IRUnitT, ExtraArgTs... >::Key

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.

decltype(auto) cast(const From &Val)

cast - Return the argument parameter cast to the specified type.

bool canTrackArgumentsInterprocedurally(Function *F)

Determine if the values of the given function's arguments can be tracked interprocedurally.

AnalysisManager< Module > ModuleAnalysisManager

Convenience typedef for the Module analysis manager.

static CVPLatticeKey getLatticeKeyFromValue(Value *V)

Definition CalledValuePropagation.cpp:369

static Value * getValueFromLatticeKey(CVPLatticeKey Key)

Definition CalledValuePropagation.cpp:366

A template for translating between LLVM Values and LatticeKeys.