119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman//===- SparsePropagation.cpp - Sparse Conditional Property Propagation ----===// 219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// The LLVM Compiler Infrastructure 419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// This file is distributed under the University of Illinois Open Source 619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// License. See LICENSE.TXT for details. 719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman//===----------------------------------------------------------------------===// 919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 1019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// This file implements an abstract sparse conditional propagation algorithm, 1119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// modeled after SCCP, but with a customizable lattice function. 1219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 1319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman//===----------------------------------------------------------------------===// 1419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 1519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#define DEBUG_TYPE "sparseprop" 1619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/Analysis/SparsePropagation.h" 1719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/Constants.h" 1819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/Function.h" 1919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/Instructions.h" 2019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/Support/Debug.h" 2119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/Support/raw_ostream.h" 2219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanusing namespace llvm; 2319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 2419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman//===----------------------------------------------------------------------===// 2519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// AbstractLatticeFunction Implementation 2619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman//===----------------------------------------------------------------------===// 2719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 2819bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanAbstractLatticeFunction::~AbstractLatticeFunction() {} 2919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 3019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// PrintValue - Render the specified lattice value to the specified stream. 3119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanvoid AbstractLatticeFunction::PrintValue(LatticeVal V, raw_ostream &OS) { 3219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (V == UndefVal) 3319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman OS << "undefined"; 3419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman else if (V == OverdefinedVal) 3519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman OS << "overdefined"; 3619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman else if (V == UntrackedVal) 3719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman OS << "untracked"; 3819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman else 3919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman OS << "unknown lattice value"; 4019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 4119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 4219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman//===----------------------------------------------------------------------===// 4319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// SparseSolver Implementation 4419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman//===----------------------------------------------------------------------===// 4519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 4619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// getOrInitValueState - Return the LatticeVal object that corresponds to the 4719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// value, initializing the value's state if it hasn't been entered into the 4819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// map yet. This function is necessary because not all values should start 4919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// out in the underdefined state... Arguments should be overdefined, and 5019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// constants should be marked as constants. 5119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// 5219bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanSparseSolver::LatticeVal SparseSolver::getOrInitValueState(Value *V) { 5319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DenseMap<Value*, LatticeVal>::iterator I = ValueState.find(V); 5419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (I != ValueState.end()) return I->second; // Common case, in the map 5519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 5619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LatticeVal LV; 5719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (LatticeFunc->IsUntrackedValue(V)) 5819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return LatticeFunc->getUntrackedVal(); 5919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman else if (Constant *C = dyn_cast<Constant>(V)) 6019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LV = LatticeFunc->ComputeConstant(C); 6119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman else if (Argument *A = dyn_cast<Argument>(V)) 6219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LV = LatticeFunc->ComputeArgument(A); 6319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman else if (!isa<Instruction>(V)) 6419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // All other non-instructions are overdefined. 6519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LV = LatticeFunc->getOverdefinedVal(); 6619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman else 6719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // All instructions are underdefined by default. 6819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LV = LatticeFunc->getUndefVal(); 6919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 7019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If this value is untracked, don't add it to the map. 7119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (LV == LatticeFunc->getUntrackedVal()) 7219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return LV; 7319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return ValueState[V] = LV; 7419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 7519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 7619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// UpdateState - When the state for some instruction is potentially updated, 7719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// this function notices and adds I to the worklist if needed. 7819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanvoid SparseSolver::UpdateState(Instruction &Inst, LatticeVal V) { 7919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DenseMap<Value*, LatticeVal>::iterator I = ValueState.find(&Inst); 8019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (I != ValueState.end() && I->second == V) 8119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return; // No change. 8219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 8319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // An update. Visit uses of I. 8419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ValueState[&Inst] = V; 8519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman InstWorkList.push_back(&Inst); 8619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 8719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 8819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// MarkBlockExecutable - This method can be used by clients to mark all of 8919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// the blocks that are known to be intrinsically live in the processed unit. 9019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanvoid SparseSolver::MarkBlockExecutable(BasicBlock *BB) { 9119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DEBUG(dbgs() << "Marking Block Executable: " << BB->getName() << "\n"); 9219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BBExecutable.insert(BB); // Basic block is executable! 9319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BBWorkList.push_back(BB); // Add the block to the work list! 9419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 9519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 9619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// markEdgeExecutable - Mark a basic block as executable, adding it to the BB 9719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// work list if it is not already executable... 9819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanvoid SparseSolver::markEdgeExecutable(BasicBlock *Source, BasicBlock *Dest) { 9919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!KnownFeasibleEdges.insert(Edge(Source, Dest)).second) 10019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return; // This edge is already known to be executable! 10119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 10219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DEBUG(dbgs() << "Marking Edge Executable: " << Source->getName() 10319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman << " -> " << Dest->getName() << "\n"); 10419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 10519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (BBExecutable.count(Dest)) { 10619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // The destination is already executable, but we just made an edge 10719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // feasible that wasn't before. Revisit the PHI nodes in the block 10819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // because they have potentially new operands. 10919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (BasicBlock::iterator I = Dest->begin(); isa<PHINode>(I); ++I) 11019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman visitPHINode(*cast<PHINode>(I)); 11119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 11219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } else { 11319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MarkBlockExecutable(Dest); 11419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 11519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 11619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 11719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 11819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// getFeasibleSuccessors - Return a vector of booleans to indicate which 11919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// successors are reachable from a given terminator instruction. 12019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanvoid SparseSolver::getFeasibleSuccessors(TerminatorInst &TI, 12119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SmallVectorImpl<bool> &Succs, 12219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool AggressiveUndef) { 12319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Succs.resize(TI.getNumSuccessors()); 12419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (TI.getNumSuccessors() == 0) return; 12519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 12619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (BranchInst *BI = dyn_cast<BranchInst>(&TI)) { 12719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (BI->isUnconditional()) { 12819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Succs[0] = true; 12919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return; 13019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 13119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 13219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LatticeVal BCValue; 13319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (AggressiveUndef) 13419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BCValue = getOrInitValueState(BI->getCondition()); 13519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman else 13619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BCValue = getLatticeState(BI->getCondition()); 13719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 13819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (BCValue == LatticeFunc->getOverdefinedVal() || 13919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BCValue == LatticeFunc->getUntrackedVal()) { 14019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Overdefined condition variables can branch either way. 14119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Succs[0] = Succs[1] = true; 14219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return; 14319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 14419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 14519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If undefined, neither is feasible yet. 14619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (BCValue == LatticeFunc->getUndefVal()) 14719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return; 14819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 14919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Constant *C = LatticeFunc->GetConstant(BCValue, BI->getCondition(), *this); 15019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (C == 0 || !isa<ConstantInt>(C)) { 15119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Non-constant values can go either way. 15219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Succs[0] = Succs[1] = true; 15319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return; 15419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 15519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 15619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Constant condition variables mean the branch can only go a single way 15719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Succs[C->isNullValue()] = true; 15819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return; 15919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 16019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 16119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (isa<InvokeInst>(TI)) { 16219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Invoke instructions successors are always executable. 16319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // TODO: Could ask the lattice function if the value can throw. 16419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Succs[0] = Succs[1] = true; 16519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return; 16619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 16719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 16819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (isa<IndirectBrInst>(TI)) { 16919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Succs.assign(Succs.size(), true); 17019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return; 17119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 17219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 17319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SwitchInst &SI = cast<SwitchInst>(TI); 17419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LatticeVal SCValue; 17519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (AggressiveUndef) 17619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SCValue = getOrInitValueState(SI.getCondition()); 17719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman else 17819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SCValue = getLatticeState(SI.getCondition()); 17919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 18019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (SCValue == LatticeFunc->getOverdefinedVal() || 18119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SCValue == LatticeFunc->getUntrackedVal()) { 18219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // All destinations are executable! 18319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Succs.assign(TI.getNumSuccessors(), true); 18419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return; 18519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 18619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 18719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If undefined, neither is feasible yet. 18819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (SCValue == LatticeFunc->getUndefVal()) 18919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return; 19019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 19119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Constant *C = LatticeFunc->GetConstant(SCValue, SI.getCondition(), *this); 19219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (C == 0 || !isa<ConstantInt>(C)) { 19319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // All destinations are executable! 19419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Succs.assign(TI.getNumSuccessors(), true); 19519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return; 19619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 19719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 19819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Succs[SI.findCaseValue(cast<ConstantInt>(C))] = true; 19919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 20019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 20119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 20219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// isEdgeFeasible - Return true if the control flow edge from the 'From' 20319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// basic block to the 'To' basic block is currently feasible... 20419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanbool SparseSolver::isEdgeFeasible(BasicBlock *From, BasicBlock *To, 20519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool AggressiveUndef) { 20619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SmallVector<bool, 16> SuccFeasible; 20719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman TerminatorInst *TI = From->getTerminator(); 20819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman getFeasibleSuccessors(*TI, SuccFeasible, AggressiveUndef); 20919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 21019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) 21119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (TI->getSuccessor(i) == To && SuccFeasible[i]) 21219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return true; 21319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 21419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 21519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 21619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 21719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanvoid SparseSolver::visitTerminatorInst(TerminatorInst &TI) { 21819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SmallVector<bool, 16> SuccFeasible; 21919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman getFeasibleSuccessors(TI, SuccFeasible, true); 22019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 22119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BasicBlock *BB = TI.getParent(); 22219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 22319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Mark all feasible successors executable... 22419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (unsigned i = 0, e = SuccFeasible.size(); i != e; ++i) 22519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (SuccFeasible[i]) 22619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman markEdgeExecutable(BB, TI.getSuccessor(i)); 22719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 22819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 22919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanvoid SparseSolver::visitPHINode(PHINode &PN) { 23019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // The lattice function may store more information on a PHINode than could be 23119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // computed from its incoming values. For example, SSI form stores its sigma 23219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // functions as PHINodes with a single incoming value. 23319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (LatticeFunc->IsSpecialCasedPHI(&PN)) { 23419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LatticeVal IV = LatticeFunc->ComputeInstructionState(PN, *this); 23519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (IV != LatticeFunc->getUntrackedVal()) 23619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman UpdateState(PN, IV); 23719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return; 23819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 23919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 24019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LatticeVal PNIV = getOrInitValueState(&PN); 24119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LatticeVal Overdefined = LatticeFunc->getOverdefinedVal(); 24219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 24319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If this value is already overdefined (common) just return. 24419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (PNIV == Overdefined || PNIV == LatticeFunc->getUntrackedVal()) 24519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return; // Quick exit 24619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 24719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Super-extra-high-degree PHI nodes are unlikely to ever be interesting, 24819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // and slow us down a lot. Just mark them overdefined. 24919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (PN.getNumIncomingValues() > 64) { 25019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman UpdateState(PN, Overdefined); 25119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return; 25219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 25319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 25419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Look at all of the executable operands of the PHI node. If any of them 25519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // are overdefined, the PHI becomes overdefined as well. Otherwise, ask the 25619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // transfer function to give us the merge of the incoming values. 25719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) { 25819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If the edge is not yet known to be feasible, it doesn't impact the PHI. 25919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!isEdgeFeasible(PN.getIncomingBlock(i), PN.getParent(), true)) 26019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman continue; 26119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 26219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Merge in this value. 26319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LatticeVal OpVal = getOrInitValueState(PN.getIncomingValue(i)); 26419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (OpVal != PNIV) 26519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman PNIV = LatticeFunc->MergeValues(PNIV, OpVal); 26619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 26719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (PNIV == Overdefined) 26819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman break; // Rest of input values don't matter. 26919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 27019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 27119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Update the PHI with the compute value, which is the merge of the inputs. 27219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman UpdateState(PN, PNIV); 27319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 27419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 27519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 27619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanvoid SparseSolver::visitInst(Instruction &I) { 27719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // PHIs are handled by the propagation logic, they are never passed into the 27819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // transfer functions. 27919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (PHINode *PN = dyn_cast<PHINode>(&I)) 28019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return visitPHINode(*PN); 28119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 28219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Otherwise, ask the transfer function what the result is. If this is 28319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // something that we care about, remember it. 28419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LatticeVal IV = LatticeFunc->ComputeInstructionState(I, *this); 28519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (IV != LatticeFunc->getUntrackedVal()) 28619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman UpdateState(I, IV); 28719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 28819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (TerminatorInst *TI = dyn_cast<TerminatorInst>(&I)) 28919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman visitTerminatorInst(*TI); 29019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 29119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 29219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanvoid SparseSolver::Solve(Function &F) { 29319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MarkBlockExecutable(&F.getEntryBlock()); 29419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 29519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Process the work lists until they are empty! 29619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman while (!BBWorkList.empty() || !InstWorkList.empty()) { 29719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Process the instruction work list. 29819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman while (!InstWorkList.empty()) { 29919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Instruction *I = InstWorkList.back(); 30019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman InstWorkList.pop_back(); 30119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 30219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DEBUG(dbgs() << "\nPopped off I-WL: " << *I << "\n"); 30319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 30419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // "I" got into the work list because it made a transition. See if any 30519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // users are both live and in need of updating. 30619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); 30719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman UI != E; ++UI) { 30819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Instruction *U = cast<Instruction>(*UI); 30919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (BBExecutable.count(U->getParent())) // Inst is executable? 31019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman visitInst(*U); 31119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 31219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 31319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 31419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Process the basic block work list. 31519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman while (!BBWorkList.empty()) { 31619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BasicBlock *BB = BBWorkList.back(); 31719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BBWorkList.pop_back(); 31819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 31919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DEBUG(dbgs() << "\nPopped off BBWL: " << *BB); 32019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 32119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Notify all instructions in this basic block that they are newly 32219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // executable. 32319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) 32419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman visitInst(*I); 32519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 32619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 32719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 32819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 32919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanvoid SparseSolver::Print(Function &F, raw_ostream &OS) const { 33019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman OS << "\nFUNCTION: " << F.getNameStr() << "\n"; 33119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) { 33219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!BBExecutable.count(BB)) 33319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman OS << "INFEASIBLE: "; 33419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman OS << "\t"; 33519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (BB->hasName()) 33619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman OS << BB->getNameStr() << ":\n"; 33719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman else 33819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman OS << "; anon bb\n"; 33919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) { 34019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LatticeFunc->PrintValue(getLatticeState(I), OS); 34119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman OS << *I << "\n"; 34219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 34319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 34419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman OS << "\n"; 34519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 34619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 34719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 348