SparsePropagation.h Source File (original) (raw)

14#ifndef LLVM_ANALYSIS_SPARSEPROPAGATION_H

15#define LLVM_ANALYSIS_SPARSEPROPAGATION_H

21#include

23#define DEBUG_TYPE "sparseprop"

25namespace llvm {

34template <class LatticeKey, class LatticeVal,

48private:

49 LatticeVal UndefVal, OverdefinedVal, UntrackedVal;

51public:

53 LatticeVal untrackedVal) {

54 UndefVal = undefVal;

55 OverdefinedVal = overdefinedVal;

56 UntrackedVal = untrackedVal;

57 }

61 LatticeVal getUndefVal() const { return UndefVal; }

100

101

102

103

105 return nullptr;

106 }

107};

108

109

110

111template <class LatticeKey, class LatticeVal, class KeyInfo>

113

114

115

117

118

120

121

123

124

126

127

129

130 using Edge = std::pair<BasicBlock *, BasicBlock *>;

131

132

133

134 std::set KnownFeasibleEdges;

135

136public:

139 : LatticeFunc(Lattice) {}

142

143

145

147

148

149

150

152 auto I = ValueState.find(Key);

153 return I != ValueState.end() ? I->second : LatticeFunc->getUntrackedVal();

154 }

155

156

157

158

160

161

162

163

164

165

167 bool AggressiveUndef = false);

168

169

170

171

173 return BBExecutable.count(BB);

174 }

175

176

177

179

180private:

181

182

183

184 void UpdateState(LatticeKey Key, LatticeVal LV);

185

186

187

189

190

191

193 bool AggressiveUndef);

194

196 void visitPHINode(PHINode &I);

198};

199

200

201

202

203

204template <class LatticeKey, class LatticeVal>

207 if (V == UndefVal)

208 OS << "undefined";

209 else if (V == OverdefinedVal)

210 OS << "overdefined";

211 else if (V == UntrackedVal)

212 OS << "untracked";

213 else

214 OS << "unknown lattice value";

215}

216

217template <class LatticeKey, class LatticeVal>

220 OS << "unknown lattice key";

221}

222

223

224

225

226

227template <class LatticeKey, class LatticeVal, class KeyInfo>

228LatticeVal

230 auto I = ValueState.find(Key);

231 if (I != ValueState.end())

232 return I->second;

233

234 if (LatticeFunc->IsUntrackedValue(Key))

235 return LatticeFunc->getUntrackedVal();

236 LatticeVal LV = LatticeFunc->ComputeLatticeVal(Key);

237

238

239 if (LV == LatticeFunc->getUntrackedVal())

240 return LV;

241 return ValueState[Key] = std::move(LV);

242}

243

244template <class LatticeKey, class LatticeVal, class KeyInfo>

245void SparseSolver<LatticeKey, LatticeVal, KeyInfo>::UpdateState(LatticeKey Key,

246 LatticeVal LV) {

247 auto [I, Inserted] = ValueState.try_emplace(Key);

248 if (!Inserted && I->second == LV)

249 return;

250

251

252

253 I->second = std::move(LV);

254 if (Value *V = KeyInfo::getValueFromLatticeKey(Key))

255 ValueWorkList.push_back(V);

256}

257

258template <class LatticeKey, class LatticeVal, class KeyInfo>

261 if (!BBExecutable.insert(BB).second)

262 return;

264 BBWorkList.push_back(BB);

265}

266

267template <class LatticeKey, class LatticeVal, class KeyInfo>

268void SparseSolver<LatticeKey, LatticeVal, KeyInfo>::markEdgeExecutable(

270 if (!KnownFeasibleEdges.insert(Edge(Source, Dest)).second)

271 return;

272

273 LLVM_DEBUG(dbgs() << "Marking Edge Executable: " << Source->getName()

274 << " -> " << Dest->getName() << "\n");

275

276 if (BBExecutable.count(Dest)) {

277

278

279

282 } else {

283 MarkBlockExecutable(Dest);

284 }

285}

286

287template <class LatticeKey, class LatticeVal, class KeyInfo>

288void SparseSolver<LatticeKey, LatticeVal, KeyInfo>::getFeasibleSuccessors(

290 Succs.resize(TI.getNumSuccessors());

291 if (TI.getNumSuccessors() == 0)

292 return;

293

295 if (BI->isUnconditional()) {

296 Succs[0] = true;

297 return;

298 }

299

300 LatticeVal BCValue;

301 if (AggressiveUndef)

302 BCValue =

303 getValueState(KeyInfo::getLatticeKeyFromValue(BI->getCondition()));

304 else

305 BCValue = getExistingValueState(

306 KeyInfo::getLatticeKeyFromValue(BI->getCondition()));

307

308 if (BCValue == LatticeFunc->getOverdefinedVal() ||

309 BCValue == LatticeFunc->getUntrackedVal()) {

310

311 Succs[0] = Succs[1] = true;

312 return;

313 }

314

315

316 if (BCValue == LatticeFunc->getUndefVal())

317 return;

318

321 std::move(BCValue), BI->getCondition()->getType()));

323

324 Succs[0] = Succs[1] = true;

325 return;

326 }

327

328

329 Succs[C->isNullValue()] = true;

330 return;

331 }

332

334

335 Succs.assign(Succs.size(), true);

336 return;

337 }

338

340 LatticeVal SCValue;

341 if (AggressiveUndef)

342 SCValue = getValueState(KeyInfo::getLatticeKeyFromValue(SI.getCondition()));

343 else

344 SCValue = getExistingValueState(

345 KeyInfo::getLatticeKeyFromValue(SI.getCondition()));

346

347 if (SCValue == LatticeFunc->getOverdefinedVal() ||

348 SCValue == LatticeFunc->getUntrackedVal()) {

349

350 Succs.assign(TI.getNumSuccessors(), true);

351 return;

352 }

353

354

355 if (SCValue == LatticeFunc->getUndefVal())

356 return;

357

359 std::move(SCValue), SI.getCondition()->getType()));

361

362 Succs.assign(TI.getNumSuccessors(), true);

363 return;

364 }

366 Succs[Case.getSuccessorIndex()] = true;

367}

368

369template <class LatticeKey, class LatticeVal, class KeyInfo>

374 getFeasibleSuccessors(*TI, SuccFeasible, AggressiveUndef);

375

376 for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)

377 if (TI->getSuccessor(i) == To && SuccFeasible[i])

378 return true;

379

380 return false;

381}

382

383template <class LatticeKey, class LatticeVal, class KeyInfo>

384void SparseSolver<LatticeKey, LatticeVal, KeyInfo>::visitTerminator(

387 getFeasibleSuccessors(TI, SuccFeasible, true);

388

390

391

392 for (unsigned i = 0, e = SuccFeasible.size(); i != e; ++i)

393 if (SuccFeasible[i])

395}

396

397template <class LatticeKey, class LatticeVal, class KeyInfo>

398void SparseSolver<LatticeKey, LatticeVal, KeyInfo>::visitPHINode(PHINode &PN) {

399

400

401

402 if (LatticeFunc->IsSpecialCasedPHI(&PN)) {

403 SmallDenseMap<LatticeKey, LatticeVal, 16> ChangedValues;

404 LatticeFunc->ComputeInstructionState(PN, ChangedValues, *this);

405 for (auto &ChangedValue : ChangedValues)

406 if (ChangedValue.second != LatticeFunc->getUntrackedVal())

407 UpdateState(std::move(ChangedValue.first),

408 std::move(ChangedValue.second));

409 return;

410 }

411

412 LatticeKey Key = KeyInfo::getLatticeKeyFromValue(&PN);

413 LatticeVal PNIV = getValueState(Key);

414 LatticeVal Overdefined = LatticeFunc->getOverdefinedVal();

415

416

417 if (PNIV == Overdefined || PNIV == LatticeFunc->getUntrackedVal())

418 return;

419

420

421

422 if (PN.getNumIncomingValues() > 64) {

423 UpdateState(Key, Overdefined);

424 return;

425 }

426

427

428

429

430 for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) {

431

432 if (!isEdgeFeasible(PN.getIncomingBlock(i), PN.getParent(), true))

433 continue;

434

435

436 LatticeVal OpVal =

437 getValueState(KeyInfo::getLatticeKeyFromValue(PN.getIncomingValue(i)));

438 if (OpVal != PNIV)

439 PNIV = LatticeFunc->MergeValues(PNIV, OpVal);

440

441 if (PNIV == Overdefined)

442 break;

443 }

444

445

446 UpdateState(Key, PNIV);

447}

448

449template <class LatticeKey, class LatticeVal, class KeyInfo>

450void SparseSolver<LatticeKey, LatticeVal, KeyInfo>::visitInst(Instruction &I) {

451

452

454 return visitPHINode(*PN);

455

456

457

459 LatticeFunc->ComputeInstructionState(I, ChangedValues, *this);

460 for (auto &ChangedValue : ChangedValues)

461 if (ChangedValue.second != LatticeFunc->getUntrackedVal())

462 UpdateState(ChangedValue.first, ChangedValue.second);

463

464 if (I.isTerminator())

465 visitTerminator(I);

466}

467

468template <class LatticeKey, class LatticeVal, class KeyInfo>

470

471 while (!BBWorkList.empty() || !ValueWorkList.empty()) {

472

473 while (!ValueWorkList.empty()) {

474 Value *V = ValueWorkList.pop_back_val();

475

476 LLVM_DEBUG(dbgs() << "\nPopped off V-WL: " << *V << "\n");

477

478

479

482 if (BBExecutable.count(Inst->getParent()))

483 visitInst(*Inst);

484 }

485

486

487 while (!BBWorkList.empty()) {

488 BasicBlock *BB = BBWorkList.pop_back_val();

489

491

492

493

495 visitInst(I);

496 }

497 }

498}

499

500template <class LatticeKey, class LatticeVal, class KeyInfo>

503 if (ValueState.empty())

504 return;

505

506 LatticeKey Key;

507 LatticeVal LV;

508

509 OS << "ValueState:\n";

510 for (auto &Entry : ValueState) {

511 std::tie(Key, LV) = Entry;

512 if (LV == LatticeFunc->getUntrackedVal())

513 continue;

514 OS << "\t";

515 LatticeFunc->PrintLatticeVal(LV, OS);

516 OS << ": ";

517 LatticeFunc->PrintLatticeKey(Key, OS);

518 OS << "\n";

519 }

520}

521}

522

523#undef DEBUG_TYPE

524

525#endif

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

This file defines the SmallPtrSet 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...

Definition SparsePropagation.h:47

LatticeVal getOverdefinedVal() const

Definition SparsePropagation.h:62

AbstractLatticeFunction(LatticeVal undefVal, LatticeVal overdefinedVal, LatticeVal untrackedVal)

Definition SparsePropagation.h:52

virtual void ComputeInstructionState(Instruction &I, SmallDenseMap< LatticeKey, LatticeVal, 16 > &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.

Definition SparsePropagation.h:218

virtual Value * GetValueFromLatticeVal(LatticeVal LV, Type *Ty=nullptr)

GetValueFromLatticeVal - If the given LatticeVal is representable as an LLVM value,...

Definition SparsePropagation.h:104

virtual bool IsUntrackedValue(LatticeKey Key)

IsUntrackedValue - If the specified LatticeKey is obviously uninteresting to the analysis (i....

Definition SparsePropagation.h:68

virtual void PrintLatticeVal(LatticeVal LV, raw_ostream &OS)

PrintLatticeVal - Render the given LatticeVal to the specified stream.

Definition SparsePropagation.h:205

LatticeVal getUntrackedVal() const

Definition SparsePropagation.h:63

virtual LatticeVal MergeValues(LatticeVal X, LatticeVal Y)

MergeValues - Compute and return the merge of the two specified lattice values.

Definition SparsePropagation.h:83

virtual LatticeVal ComputeLatticeVal(LatticeKey Key)

ComputeLatticeVal - Compute and return a LatticeVal corresponding to the given LatticeKey.

Definition SparsePropagation.h:72

virtual ~AbstractLatticeFunction()=default

LatticeVal getUndefVal() const

Definition SparsePropagation.h:61

virtual bool IsSpecialCasedPHI(PHINode *PN)

IsSpecialCasedPHI - Given a PHI node, determine whether this PHI node is one that the we want to hand...

Definition SparsePropagation.h:78

LLVM Basic Block Representation.

iterator begin()

Instruction iterator methods.

InstListType::iterator iterator

Instruction iterators...

const Instruction * getTerminator() const LLVM_READONLY

Returns the terminator instruction if the block is well formed or null if the block is not well forme...

Conditional or Unconditional Branch instruction.

This is an important base class in LLVM.

LLVM_ABI unsigned getNumSuccessors() const LLVM_READONLY

Return the number of successors that this instruction has.

LLVM_ABI BasicBlock * getSuccessor(unsigned Idx) const LLVM_READONLY

Return the specified successor. This instruction must be a terminator.

SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.

This class consists of common code factored out of the SmallVector class to reduce code duplication b...

This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.

SparseSolver - This class is a general purpose solver for Sparse Conditional Propagation with a progr...

Definition SparsePropagation.h:112

bool isEdgeFeasible(BasicBlock *From, BasicBlock *To, bool AggressiveUndef=false)

isEdgeFeasible - Return true if the control flow edge from the 'From' basic block to the 'To' basic b...

Definition SparsePropagation.h:370

void Print(raw_ostream &OS) const

Definition SparsePropagation.h:501

LatticeVal getValueState(LatticeKey Key)

getValueState - Return the LatticeVal object corresponding to the given value from the ValueState map...

Definition SparsePropagation.h:229

SparseSolver(AbstractLatticeFunction< LatticeKey, LatticeVal > *Lattice)

Definition SparsePropagation.h:137

SparseSolver(const SparseSolver &)=delete

void MarkBlockExecutable(BasicBlock *BB)

MarkBlockExecutable - This method can be used by clients to mark all of the blocks that are known to ...

Definition SparsePropagation.h:259

void Solve()

Solve - Solve for constants and executable blocks.

Definition SparsePropagation.h:469

LatticeVal getExistingValueState(LatticeKey Key) const

getExistingValueState - Return the LatticeVal object corresponding to the given value from the ValueS...

Definition SparsePropagation.h:151

bool isBlockExecutable(BasicBlock *BB) const

isBlockExecutable - Return true if there are any known feasible edges into the basic block.

Definition SparsePropagation.h:172

SparseSolver & operator=(const SparseSolver &)=delete

The instances of the Type class are immutable: once they are created, they are never changed.

LLVM Value Representation.

iterator_range< user_iterator > users()

LLVM_ABI StringRef getName() const

Return a constant reference to the value's name.

const ParentTy * getParent() const

This class implements an extremely fast bulk output stream that can only output to a stream.

@ C

The default llvm calling convention, compatible with C.

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.

auto dyn_cast_or_null(const Y &Val)

LLVM_ABI raw_ostream & dbgs()

dbgs() - This returns a reference to a raw_ostream for debugging messages.

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

decltype(auto) cast(const From &Val)

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

A template for translating between LLVM Values and LatticeKeys.

Definition SparsePropagation.h:29