1193323Sed//===- SparsePropagation.cpp - Sparse Conditional Property Propagation ----===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// This file implements an abstract sparse conditional propagation algorithm, 11193323Sed// modeled after SCCP, but with a customizable lattice function. 12193323Sed// 13193323Sed//===----------------------------------------------------------------------===// 14193323Sed 15193323Sed#define DEBUG_TYPE "sparseprop" 16193323Sed#include "llvm/Analysis/SparsePropagation.h" 17249423Sdim#include "llvm/IR/Constants.h" 18249423Sdim#include "llvm/IR/Function.h" 19249423Sdim#include "llvm/IR/Instructions.h" 20193323Sed#include "llvm/Support/Debug.h" 21198090Srdivacky#include "llvm/Support/raw_ostream.h" 22193323Sedusing namespace llvm; 23193323Sed 24193323Sed//===----------------------------------------------------------------------===// 25193323Sed// AbstractLatticeFunction Implementation 26193323Sed//===----------------------------------------------------------------------===// 27193323Sed 28193323SedAbstractLatticeFunction::~AbstractLatticeFunction() {} 29193323Sed 30193323Sed/// PrintValue - Render the specified lattice value to the specified stream. 31198090Srdivackyvoid AbstractLatticeFunction::PrintValue(LatticeVal V, raw_ostream &OS) { 32193323Sed if (V == UndefVal) 33193323Sed OS << "undefined"; 34193323Sed else if (V == OverdefinedVal) 35193323Sed OS << "overdefined"; 36193323Sed else if (V == UntrackedVal) 37193323Sed OS << "untracked"; 38193323Sed else 39193323Sed OS << "unknown lattice value"; 40193323Sed} 41193323Sed 42193323Sed//===----------------------------------------------------------------------===// 43193323Sed// SparseSolver Implementation 44193323Sed//===----------------------------------------------------------------------===// 45193323Sed 46193323Sed/// getOrInitValueState - Return the LatticeVal object that corresponds to the 47193323Sed/// value, initializing the value's state if it hasn't been entered into the 48193323Sed/// map yet. This function is necessary because not all values should start 49193323Sed/// out in the underdefined state... Arguments should be overdefined, and 50193323Sed/// constants should be marked as constants. 51193323Sed/// 52193323SedSparseSolver::LatticeVal SparseSolver::getOrInitValueState(Value *V) { 53193323Sed DenseMap<Value*, LatticeVal>::iterator I = ValueState.find(V); 54193323Sed if (I != ValueState.end()) return I->second; // Common case, in the map 55193323Sed 56193323Sed LatticeVal LV; 57193323Sed if (LatticeFunc->IsUntrackedValue(V)) 58193323Sed return LatticeFunc->getUntrackedVal(); 59193323Sed else if (Constant *C = dyn_cast<Constant>(V)) 60193323Sed LV = LatticeFunc->ComputeConstant(C); 61193323Sed else if (Argument *A = dyn_cast<Argument>(V)) 62193323Sed LV = LatticeFunc->ComputeArgument(A); 63193323Sed else if (!isa<Instruction>(V)) 64193323Sed // All other non-instructions are overdefined. 65193323Sed LV = LatticeFunc->getOverdefinedVal(); 66193323Sed else 67193323Sed // All instructions are underdefined by default. 68193323Sed LV = LatticeFunc->getUndefVal(); 69193323Sed 70193323Sed // If this value is untracked, don't add it to the map. 71193323Sed if (LV == LatticeFunc->getUntrackedVal()) 72193323Sed return LV; 73193323Sed return ValueState[V] = LV; 74193323Sed} 75193323Sed 76193323Sed/// UpdateState - When the state for some instruction is potentially updated, 77193323Sed/// this function notices and adds I to the worklist if needed. 78193323Sedvoid SparseSolver::UpdateState(Instruction &Inst, LatticeVal V) { 79193323Sed DenseMap<Value*, LatticeVal>::iterator I = ValueState.find(&Inst); 80193323Sed if (I != ValueState.end() && I->second == V) 81193323Sed return; // No change. 82193323Sed 83193323Sed // An update. Visit uses of I. 84193323Sed ValueState[&Inst] = V; 85193323Sed InstWorkList.push_back(&Inst); 86193323Sed} 87193323Sed 88193323Sed/// MarkBlockExecutable - This method can be used by clients to mark all of 89193323Sed/// the blocks that are known to be intrinsically live in the processed unit. 90193323Sedvoid SparseSolver::MarkBlockExecutable(BasicBlock *BB) { 91201360Srdivacky DEBUG(dbgs() << "Marking Block Executable: " << BB->getName() << "\n"); 92193323Sed BBExecutable.insert(BB); // Basic block is executable! 93193323Sed BBWorkList.push_back(BB); // Add the block to the work list! 94193323Sed} 95193323Sed 96193323Sed/// markEdgeExecutable - Mark a basic block as executable, adding it to the BB 97193323Sed/// work list if it is not already executable... 98193323Sedvoid SparseSolver::markEdgeExecutable(BasicBlock *Source, BasicBlock *Dest) { 99193323Sed if (!KnownFeasibleEdges.insert(Edge(Source, Dest)).second) 100193323Sed return; // This edge is already known to be executable! 101193323Sed 102201360Srdivacky DEBUG(dbgs() << "Marking Edge Executable: " << Source->getName() 103198090Srdivacky << " -> " << Dest->getName() << "\n"); 104193323Sed 105193323Sed if (BBExecutable.count(Dest)) { 106193323Sed // The destination is already executable, but we just made an edge 107193323Sed // feasible that wasn't before. Revisit the PHI nodes in the block 108193323Sed // because they have potentially new operands. 109193323Sed for (BasicBlock::iterator I = Dest->begin(); isa<PHINode>(I); ++I) 110193323Sed visitPHINode(*cast<PHINode>(I)); 111193323Sed 112193323Sed } else { 113193323Sed MarkBlockExecutable(Dest); 114193323Sed } 115193323Sed} 116193323Sed 117193323Sed 118193323Sed/// getFeasibleSuccessors - Return a vector of booleans to indicate which 119193323Sed/// successors are reachable from a given terminator instruction. 120193323Sedvoid SparseSolver::getFeasibleSuccessors(TerminatorInst &TI, 121193323Sed SmallVectorImpl<bool> &Succs, 122193323Sed bool AggressiveUndef) { 123193323Sed Succs.resize(TI.getNumSuccessors()); 124193323Sed if (TI.getNumSuccessors() == 0) return; 125193323Sed 126193323Sed if (BranchInst *BI = dyn_cast<BranchInst>(&TI)) { 127193323Sed if (BI->isUnconditional()) { 128193323Sed Succs[0] = true; 129193323Sed return; 130193323Sed } 131193323Sed 132193323Sed LatticeVal BCValue; 133193323Sed if (AggressiveUndef) 134193323Sed BCValue = getOrInitValueState(BI->getCondition()); 135193323Sed else 136193323Sed BCValue = getLatticeState(BI->getCondition()); 137193323Sed 138193323Sed if (BCValue == LatticeFunc->getOverdefinedVal() || 139193323Sed BCValue == LatticeFunc->getUntrackedVal()) { 140193323Sed // Overdefined condition variables can branch either way. 141193323Sed Succs[0] = Succs[1] = true; 142193323Sed return; 143193323Sed } 144193323Sed 145193323Sed // If undefined, neither is feasible yet. 146193323Sed if (BCValue == LatticeFunc->getUndefVal()) 147193323Sed return; 148193323Sed 149193323Sed Constant *C = LatticeFunc->GetConstant(BCValue, BI->getCondition(), *this); 150193323Sed if (C == 0 || !isa<ConstantInt>(C)) { 151193323Sed // Non-constant values can go either way. 152193323Sed Succs[0] = Succs[1] = true; 153193323Sed return; 154193323Sed } 155193323Sed 156193323Sed // Constant condition variables mean the branch can only go a single way 157201360Srdivacky Succs[C->isNullValue()] = true; 158193323Sed return; 159193323Sed } 160193323Sed 161193323Sed if (isa<InvokeInst>(TI)) { 162193323Sed // Invoke instructions successors are always executable. 163193323Sed // TODO: Could ask the lattice function if the value can throw. 164193323Sed Succs[0] = Succs[1] = true; 165193323Sed return; 166193323Sed } 167193323Sed 168198892Srdivacky if (isa<IndirectBrInst>(TI)) { 169198892Srdivacky Succs.assign(Succs.size(), true); 170198892Srdivacky return; 171198892Srdivacky } 172198892Srdivacky 173193323Sed SwitchInst &SI = cast<SwitchInst>(TI); 174193323Sed LatticeVal SCValue; 175193323Sed if (AggressiveUndef) 176193323Sed SCValue = getOrInitValueState(SI.getCondition()); 177193323Sed else 178193323Sed SCValue = getLatticeState(SI.getCondition()); 179193323Sed 180193323Sed if (SCValue == LatticeFunc->getOverdefinedVal() || 181193323Sed SCValue == LatticeFunc->getUntrackedVal()) { 182193323Sed // All destinations are executable! 183193323Sed Succs.assign(TI.getNumSuccessors(), true); 184193323Sed return; 185193323Sed } 186193323Sed 187193323Sed // If undefined, neither is feasible yet. 188193323Sed if (SCValue == LatticeFunc->getUndefVal()) 189193323Sed return; 190193323Sed 191193323Sed Constant *C = LatticeFunc->GetConstant(SCValue, SI.getCondition(), *this); 192193323Sed if (C == 0 || !isa<ConstantInt>(C)) { 193193323Sed // All destinations are executable! 194193323Sed Succs.assign(TI.getNumSuccessors(), true); 195193323Sed return; 196193323Sed } 197234353Sdim SwitchInst::CaseIt Case = SI.findCaseValue(cast<ConstantInt>(C)); 198234353Sdim Succs[Case.getSuccessorIndex()] = true; 199193323Sed} 200193323Sed 201193323Sed 202193323Sed/// isEdgeFeasible - Return true if the control flow edge from the 'From' 203193323Sed/// basic block to the 'To' basic block is currently feasible... 204193323Sedbool SparseSolver::isEdgeFeasible(BasicBlock *From, BasicBlock *To, 205193323Sed bool AggressiveUndef) { 206193323Sed SmallVector<bool, 16> SuccFeasible; 207193323Sed TerminatorInst *TI = From->getTerminator(); 208193323Sed getFeasibleSuccessors(*TI, SuccFeasible, AggressiveUndef); 209193323Sed 210193323Sed for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) 211193323Sed if (TI->getSuccessor(i) == To && SuccFeasible[i]) 212193323Sed return true; 213193323Sed 214193323Sed return false; 215193323Sed} 216193323Sed 217193323Sedvoid SparseSolver::visitTerminatorInst(TerminatorInst &TI) { 218193323Sed SmallVector<bool, 16> SuccFeasible; 219193323Sed getFeasibleSuccessors(TI, SuccFeasible, true); 220193323Sed 221193323Sed BasicBlock *BB = TI.getParent(); 222193323Sed 223193323Sed // Mark all feasible successors executable... 224193323Sed for (unsigned i = 0, e = SuccFeasible.size(); i != e; ++i) 225193323Sed if (SuccFeasible[i]) 226193323Sed markEdgeExecutable(BB, TI.getSuccessor(i)); 227193323Sed} 228193323Sed 229193323Sedvoid SparseSolver::visitPHINode(PHINode &PN) { 230198090Srdivacky // The lattice function may store more information on a PHINode than could be 231198090Srdivacky // computed from its incoming values. For example, SSI form stores its sigma 232198090Srdivacky // functions as PHINodes with a single incoming value. 233198090Srdivacky if (LatticeFunc->IsSpecialCasedPHI(&PN)) { 234198090Srdivacky LatticeVal IV = LatticeFunc->ComputeInstructionState(PN, *this); 235198090Srdivacky if (IV != LatticeFunc->getUntrackedVal()) 236198090Srdivacky UpdateState(PN, IV); 237198090Srdivacky return; 238198090Srdivacky } 239198090Srdivacky 240193323Sed LatticeVal PNIV = getOrInitValueState(&PN); 241193323Sed LatticeVal Overdefined = LatticeFunc->getOverdefinedVal(); 242193323Sed 243193323Sed // If this value is already overdefined (common) just return. 244193323Sed if (PNIV == Overdefined || PNIV == LatticeFunc->getUntrackedVal()) 245193323Sed return; // Quick exit 246193323Sed 247193323Sed // Super-extra-high-degree PHI nodes are unlikely to ever be interesting, 248193323Sed // and slow us down a lot. Just mark them overdefined. 249193323Sed if (PN.getNumIncomingValues() > 64) { 250193323Sed UpdateState(PN, Overdefined); 251193323Sed return; 252193323Sed } 253193323Sed 254193323Sed // Look at all of the executable operands of the PHI node. If any of them 255193323Sed // are overdefined, the PHI becomes overdefined as well. Otherwise, ask the 256193323Sed // transfer function to give us the merge of the incoming values. 257193323Sed for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) { 258193323Sed // If the edge is not yet known to be feasible, it doesn't impact the PHI. 259193323Sed if (!isEdgeFeasible(PN.getIncomingBlock(i), PN.getParent(), true)) 260193323Sed continue; 261193323Sed 262193323Sed // Merge in this value. 263193323Sed LatticeVal OpVal = getOrInitValueState(PN.getIncomingValue(i)); 264193323Sed if (OpVal != PNIV) 265193323Sed PNIV = LatticeFunc->MergeValues(PNIV, OpVal); 266193323Sed 267193323Sed if (PNIV == Overdefined) 268193323Sed break; // Rest of input values don't matter. 269193323Sed } 270193323Sed 271193323Sed // Update the PHI with the compute value, which is the merge of the inputs. 272193323Sed UpdateState(PN, PNIV); 273193323Sed} 274193323Sed 275193323Sed 276193323Sedvoid SparseSolver::visitInst(Instruction &I) { 277193323Sed // PHIs are handled by the propagation logic, they are never passed into the 278193323Sed // transfer functions. 279193323Sed if (PHINode *PN = dyn_cast<PHINode>(&I)) 280193323Sed return visitPHINode(*PN); 281193323Sed 282193323Sed // Otherwise, ask the transfer function what the result is. If this is 283193323Sed // something that we care about, remember it. 284193323Sed LatticeVal IV = LatticeFunc->ComputeInstructionState(I, *this); 285193323Sed if (IV != LatticeFunc->getUntrackedVal()) 286193323Sed UpdateState(I, IV); 287193323Sed 288193323Sed if (TerminatorInst *TI = dyn_cast<TerminatorInst>(&I)) 289193323Sed visitTerminatorInst(*TI); 290193323Sed} 291193323Sed 292193323Sedvoid SparseSolver::Solve(Function &F) { 293193323Sed MarkBlockExecutable(&F.getEntryBlock()); 294193323Sed 295193323Sed // Process the work lists until they are empty! 296193323Sed while (!BBWorkList.empty() || !InstWorkList.empty()) { 297193323Sed // Process the instruction work list. 298193323Sed while (!InstWorkList.empty()) { 299193323Sed Instruction *I = InstWorkList.back(); 300193323Sed InstWorkList.pop_back(); 301193323Sed 302201360Srdivacky DEBUG(dbgs() << "\nPopped off I-WL: " << *I << "\n"); 303193323Sed 304193323Sed // "I" got into the work list because it made a transition. See if any 305193323Sed // users are both live and in need of updating. 306193323Sed for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); 307193323Sed UI != E; ++UI) { 308193323Sed Instruction *U = cast<Instruction>(*UI); 309193323Sed if (BBExecutable.count(U->getParent())) // Inst is executable? 310193323Sed visitInst(*U); 311193323Sed } 312193323Sed } 313193323Sed 314193323Sed // Process the basic block work list. 315193323Sed while (!BBWorkList.empty()) { 316193323Sed BasicBlock *BB = BBWorkList.back(); 317193323Sed BBWorkList.pop_back(); 318193323Sed 319201360Srdivacky DEBUG(dbgs() << "\nPopped off BBWL: " << *BB); 320193323Sed 321193323Sed // Notify all instructions in this basic block that they are newly 322193323Sed // executable. 323193323Sed for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) 324193323Sed visitInst(*I); 325193323Sed } 326193323Sed } 327193323Sed} 328193323Sed 329198090Srdivackyvoid SparseSolver::Print(Function &F, raw_ostream &OS) const { 330234353Sdim OS << "\nFUNCTION: " << F.getName() << "\n"; 331193323Sed for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) { 332193323Sed if (!BBExecutable.count(BB)) 333193323Sed OS << "INFEASIBLE: "; 334193323Sed OS << "\t"; 335193323Sed if (BB->hasName()) 336234353Sdim OS << BB->getName() << ":\n"; 337193323Sed else 338193323Sed OS << "; anon bb\n"; 339193323Sed for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) { 340193323Sed LatticeFunc->PrintValue(getLatticeState(I), OS); 341198090Srdivacky OS << *I << "\n"; 342193323Sed } 343193323Sed 344193323Sed OS << "\n"; 345193323Sed } 346193323Sed} 347193323Sed 348