14 #ifndef LLVM_ANALYSIS_SPARSEPROPAGATION_H
15 #define LLVM_ANALYSIS_SPARSEPROPAGATION_H
23 #define DEBUG_TYPE "sparseprop"
34 template <
class LatticeKey,
class LatticeVal,
49 LatticeVal UndefVal, OverdefinedVal, UntrackedVal;
53 LatticeVal untrackedVal) {
55 OverdefinedVal = overdefinedVal;
56 UntrackedVal = untrackedVal;
112 template <
class LatticeKey,
class LatticeVal,
class KeyInfo>
117 AbstractLatticeFunction<LatticeKey, LatticeVal> *LatticeFunc;
120 DenseMap<LatticeKey, LatticeVal> ValueState;
123 SmallPtrSet<BasicBlock *, 16> BBExecutable;
126 SmallVector<Value *, 64> ValueWorkList;
129 SmallVector<BasicBlock *, 64> BBWorkList;
131 using Edge = std::pair<BasicBlock *, BasicBlock *>;
135 std::set<Edge> KnownFeasibleEdges;
140 : LatticeFunc(Lattice) {}
153 auto I = ValueState.find(
Key);
154 return I != ValueState.end() ?
I->second : LatticeFunc->getUntrackedVal();
168 bool AggressiveUndef =
false);
174 return BBExecutable.count(
BB);
185 void UpdateState(LatticeKey
Key, LatticeVal LV);
194 bool AggressiveUndef);
205 template <
class LatticeKey,
class LatticeVal>
210 else if (V == OverdefinedVal)
212 else if (V == UntrackedVal)
215 OS <<
"unknown lattice value";
218 template <
class LatticeKey,
class LatticeVal>
221 OS <<
"unknown lattice key";
228 template <
class LatticeKey,
class LatticeVal,
class KeyInfo>
231 auto I = ValueState.find(
Key);
232 if (
I != ValueState.end())
235 if (LatticeFunc->IsUntrackedValue(
Key))
236 return LatticeFunc->getUntrackedVal();
237 LatticeVal LV = LatticeFunc->ComputeLatticeVal(
Key);
240 if (LV == LatticeFunc->getUntrackedVal())
245 template <
class LatticeKey,
class LatticeVal,
class KeyInfo>
248 auto I = ValueState.find(
Key);
249 if (
I != ValueState.end() &&
I->second == LV)
255 if (
Value *V = KeyInfo::getValueFromLatticeKey(
Key))
256 ValueWorkList.push_back(V);
259 template <
class LatticeKey,
class LatticeVal,
class KeyInfo>
262 if (!BBExecutable.insert(
BB).second)
264 LLVM_DEBUG(
dbgs() <<
"Marking Block Executable: " <<
BB->getName() <<
"\n");
265 BBWorkList.push_back(
BB);
268 template <
class LatticeKey,
class LatticeVal,
class KeyInfo>
271 if (!KnownFeasibleEdges.insert(Edge(
Source, Dest)).second)
275 <<
" -> " << Dest->
getName() <<
"\n");
277 if (BBExecutable.count(Dest)) {
282 visitPHINode(*cast<PHINode>(
I));
284 MarkBlockExecutable(Dest);
288 template <
class LatticeKey,
class LatticeVal,
class KeyInfo>
289 void SparseSolver<LatticeKey, LatticeVal, KeyInfo>::getFeasibleSuccessors(
290 Instruction &TI, SmallVectorImpl<bool> &Succs,
bool AggressiveUndef) {
291 Succs.resize(TI.getNumSuccessors());
292 if (TI.getNumSuccessors() == 0)
295 if (BranchInst *BI = dyn_cast<BranchInst>(&TI)) {
296 if (BI->isUnconditional()) {
304 getValueState(KeyInfo::getLatticeKeyFromValue(BI->getCondition()));
306 BCValue = getExistingValueState(
307 KeyInfo::getLatticeKeyFromValue(BI->getCondition()));
309 if (BCValue == LatticeFunc->getOverdefinedVal() ||
310 BCValue == LatticeFunc->getUntrackedVal()) {
312 Succs[0] = Succs[1] =
true;
317 if (BCValue == LatticeFunc->getUndefVal())
321 dyn_cast_or_null<Constant>(LatticeFunc->GetValueFromLatticeVal(
322 std::move(BCValue), BI->getCondition()->getType()));
323 if (!
C || !isa<ConstantInt>(
C)) {
325 Succs[0] = Succs[1] =
true;
330 Succs[
C->isNullValue()] =
true;
334 if (TI.isExceptionalTerminator() ||
335 TI.isIndirectTerminator()) {
336 Succs.assign(Succs.size(),
true);
340 SwitchInst &
SI = cast<SwitchInst>(TI);
343 SCValue = getValueState(KeyInfo::getLatticeKeyFromValue(
SI.getCondition()));
345 SCValue = getExistingValueState(
346 KeyInfo::getLatticeKeyFromValue(
SI.getCondition()));
348 if (SCValue == LatticeFunc->getOverdefinedVal() ||
349 SCValue == LatticeFunc->getUntrackedVal()) {
351 Succs.assign(TI.getNumSuccessors(),
true);
356 if (SCValue == LatticeFunc->getUndefVal())
359 Constant *
C = dyn_cast_or_null<Constant>(LatticeFunc->GetValueFromLatticeVal(
360 std::move(SCValue),
SI.getCondition()->getType()));
361 if (!
C || !isa<ConstantInt>(
C)) {
363 Succs.assign(TI.getNumSuccessors(),
true);
366 SwitchInst::CaseHandle Case = *
SI.findCaseValue(cast<ConstantInt>(
C));
367 Succs[Case.getSuccessorIndex()] =
true;
370 template <
class LatticeKey,
class LatticeVal,
class KeyInfo>
375 getFeasibleSuccessors(*TI, SuccFeasible, AggressiveUndef);
384 template <
class LatticeKey,
class LatticeVal,
class KeyInfo>
388 getFeasibleSuccessors(TI, SuccFeasible,
true);
393 for (
unsigned i = 0,
e = SuccFeasible.size();
i !=
e; ++
i)
398 template <
class LatticeKey,
class LatticeVal,
class KeyInfo>
399 void SparseSolver<LatticeKey, LatticeVal, KeyInfo>::visitPHINode(PHINode &PN) {
403 if (LatticeFunc->IsSpecialCasedPHI(&PN)) {
404 DenseMap<LatticeKey, LatticeVal> ChangedValues;
405 LatticeFunc->ComputeInstructionState(PN, ChangedValues, *
this);
406 for (
auto &ChangedValue : ChangedValues)
407 if (ChangedValue.second != LatticeFunc->getUntrackedVal())
408 UpdateState(
std::move(ChangedValue.first),
413 LatticeKey
Key = KeyInfo::getLatticeKeyFromValue(&PN);
414 LatticeVal PNIV = getValueState(
Key);
415 LatticeVal Overdefined = LatticeFunc->getOverdefinedVal();
418 if (PNIV == Overdefined || PNIV == LatticeFunc->getUntrackedVal())
423 if (PN.getNumIncomingValues() > 64) {
424 UpdateState(
Key, Overdefined);
431 for (
unsigned i = 0,
e = PN.getNumIncomingValues();
i !=
e; ++
i) {
433 if (!isEdgeFeasible(PN.getIncomingBlock(
i), PN.getParent(),
true))
438 getValueState(KeyInfo::getLatticeKeyFromValue(PN.getIncomingValue(
i)));
440 PNIV = LatticeFunc->MergeValues(PNIV, OpVal);
442 if (PNIV == Overdefined)
447 UpdateState(
Key, PNIV);
450 template <
class LatticeKey,
class LatticeVal,
class KeyInfo>
451 void SparseSolver<LatticeKey, LatticeVal, KeyInfo>::visitInst(Instruction &
I) {
454 if (PHINode *PN = dyn_cast<PHINode>(&
I))
455 return visitPHINode(*PN);
459 DenseMap<LatticeKey, LatticeVal> ChangedValues;
460 LatticeFunc->ComputeInstructionState(
I, ChangedValues, *
this);
461 for (
auto &ChangedValue : ChangedValues)
462 if (ChangedValue.second != LatticeFunc->getUntrackedVal())
463 UpdateState(ChangedValue.first, ChangedValue.second);
465 if (
I.isTerminator())
469 template <
class LatticeKey,
class LatticeVal,
class KeyInfo>
472 while (!BBWorkList.empty() || !ValueWorkList.empty()) {
474 while (!ValueWorkList.empty()) {
475 Value *V = ValueWorkList.pop_back_val();
483 if (BBExecutable.count(Inst->getParent()))
488 while (!BBWorkList.empty()) {
501 template <
class LatticeKey,
class LatticeVal,
class KeyInfo>
504 if (ValueState.empty())
510 OS <<
"ValueState:\n";
511 for (
auto &Entry : ValueState) {
512 std::tie(
Key, LV) = Entry;
513 if (LV == LatticeFunc->getUntrackedVal())
516 LatticeFunc->PrintLatticeVal(LV, OS);
518 LatticeFunc->PrintLatticeKey(
Key, OS);
526 #endif // LLVM_ANALYSIS_SPARSEPROPAGATION_H