1ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner//===- SparsePropagation.cpp - Sparse Conditional Property Propagation ----===// 2ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner// 3ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner// The LLVM Compiler Infrastructure 4ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner// 5ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner// This file is distributed under the University of Illinois Open Source 6ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner// License. See LICENSE.TXT for details. 7ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner// 8ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner//===----------------------------------------------------------------------===// 9ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner// 10ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner// This file implements an abstract sparse conditional propagation algorithm, 11ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner// modeled after SCCP, but with a customizable lattice function. 12ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner// 13ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner//===----------------------------------------------------------------------===// 14ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 15ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner#include "llvm/Analysis/SparsePropagation.h" 160b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Constants.h" 170b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Function.h" 180b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Instructions.h" 19ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner#include "llvm/Support/Debug.h" 20460f656475738d1a95a6be95346908ce1597df25Daniel Dunbar#include "llvm/Support/raw_ostream.h" 21ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattnerusing namespace llvm; 22ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 23dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#define DEBUG_TYPE "sparseprop" 24dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 25ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner//===----------------------------------------------------------------------===// 26ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner// AbstractLatticeFunction Implementation 27ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner//===----------------------------------------------------------------------===// 28ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 29ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris LattnerAbstractLatticeFunction::~AbstractLatticeFunction() {} 30ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 31ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner/// PrintValue - Render the specified lattice value to the specified stream. 32bdff548e4dd577a72094d57b282de4e765643b96Chris Lattnervoid AbstractLatticeFunction::PrintValue(LatticeVal V, raw_ostream &OS) { 33ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner if (V == UndefVal) 34ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner OS << "undefined"; 35ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner else if (V == OverdefinedVal) 36ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner OS << "overdefined"; 37ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner else if (V == UntrackedVal) 38ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner OS << "untracked"; 39ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner else 40ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner OS << "unknown lattice value"; 41ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner} 42ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 43ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner//===----------------------------------------------------------------------===// 44ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner// SparseSolver Implementation 45ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner//===----------------------------------------------------------------------===// 46ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 47ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner/// getOrInitValueState - Return the LatticeVal object that corresponds to the 48ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner/// value, initializing the value's state if it hasn't been entered into the 49ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner/// map yet. This function is necessary because not all values should start 50ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner/// out in the underdefined state... Arguments should be overdefined, and 51ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner/// constants should be marked as constants. 52ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner/// 53ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris LattnerSparseSolver::LatticeVal SparseSolver::getOrInitValueState(Value *V) { 54ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner DenseMap<Value*, LatticeVal>::iterator I = ValueState.find(V); 55ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner if (I != ValueState.end()) return I->second; // Common case, in the map 56ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 57ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner LatticeVal LV; 58ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner if (LatticeFunc->IsUntrackedValue(V)) 59ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner return LatticeFunc->getUntrackedVal(); 60ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner else if (Constant *C = dyn_cast<Constant>(V)) 61ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner LV = LatticeFunc->ComputeConstant(C); 62afcde473c5baf292038ec494917f18c77a043340Chris Lattner else if (Argument *A = dyn_cast<Argument>(V)) 63afcde473c5baf292038ec494917f18c77a043340Chris Lattner LV = LatticeFunc->ComputeArgument(A); 64ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner else if (!isa<Instruction>(V)) 65afcde473c5baf292038ec494917f18c77a043340Chris Lattner // All other non-instructions are overdefined. 66ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner LV = LatticeFunc->getOverdefinedVal(); 67ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner else 68ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner // All instructions are underdefined by default. 69ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner LV = LatticeFunc->getUndefVal(); 70ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 71ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner // If this value is untracked, don't add it to the map. 72ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner if (LV == LatticeFunc->getUntrackedVal()) 73ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner return LV; 74ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner return ValueState[V] = LV; 75ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner} 76ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 77ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner/// UpdateState - When the state for some instruction is potentially updated, 78ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner/// this function notices and adds I to the worklist if needed. 79ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattnervoid SparseSolver::UpdateState(Instruction &Inst, LatticeVal V) { 80ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner DenseMap<Value*, LatticeVal>::iterator I = ValueState.find(&Inst); 81ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner if (I != ValueState.end() && I->second == V) 82ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner return; // No change. 83ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 84ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner // An update. Visit uses of I. 85ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner ValueState[&Inst] = V; 86ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner InstWorkList.push_back(&Inst); 87ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner} 88ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 89ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner/// MarkBlockExecutable - This method can be used by clients to mark all of 90ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner/// the blocks that are known to be intrinsically live in the processed unit. 91ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattnervoid SparseSolver::MarkBlockExecutable(BasicBlock *BB) { 9289282915fdc03561b7d87ecd91126db7643e304dDavid Greene DEBUG(dbgs() << "Marking Block Executable: " << BB->getName() << "\n"); 93ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner BBExecutable.insert(BB); // Basic block is executable! 94ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner BBWorkList.push_back(BB); // Add the block to the work list! 95ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner} 96ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 97ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner/// markEdgeExecutable - Mark a basic block as executable, adding it to the BB 98ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner/// work list if it is not already executable... 99ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattnervoid SparseSolver::markEdgeExecutable(BasicBlock *Source, BasicBlock *Dest) { 100ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner if (!KnownFeasibleEdges.insert(Edge(Source, Dest)).second) 101ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner return; // This edge is already known to be executable! 102ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 10389282915fdc03561b7d87ecd91126db7643e304dDavid Greene DEBUG(dbgs() << "Marking Edge Executable: " << Source->getName() 104460f656475738d1a95a6be95346908ce1597df25Daniel Dunbar << " -> " << Dest->getName() << "\n"); 105b22d6ac348ca632bef17dc8050b14d8cb78218f3Dan Gohman 106ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner if (BBExecutable.count(Dest)) { 107ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner // The destination is already executable, but we just made an edge 108ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner // feasible that wasn't before. Revisit the PHI nodes in the block 109ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner // because they have potentially new operands. 110ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner for (BasicBlock::iterator I = Dest->begin(); isa<PHINode>(I); ++I) 111ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner visitPHINode(*cast<PHINode>(I)); 112ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 113ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner } else { 114ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner MarkBlockExecutable(Dest); 115ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner } 116ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner} 117ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 118ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 119ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner/// getFeasibleSuccessors - Return a vector of booleans to indicate which 120ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner/// successors are reachable from a given terminator instruction. 121ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattnervoid SparseSolver::getFeasibleSuccessors(TerminatorInst &TI, 12228a8dbc35fe6da6b7d2633529b73453aca254207Chris Lattner SmallVectorImpl<bool> &Succs, 12328a8dbc35fe6da6b7d2633529b73453aca254207Chris Lattner bool AggressiveUndef) { 124ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner Succs.resize(TI.getNumSuccessors()); 125ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner if (TI.getNumSuccessors() == 0) return; 126ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 127ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner if (BranchInst *BI = dyn_cast<BranchInst>(&TI)) { 128ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner if (BI->isUnconditional()) { 129ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner Succs[0] = true; 130ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner return; 131ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner } 132ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 13328a8dbc35fe6da6b7d2633529b73453aca254207Chris Lattner LatticeVal BCValue; 13428a8dbc35fe6da6b7d2633529b73453aca254207Chris Lattner if (AggressiveUndef) 13528a8dbc35fe6da6b7d2633529b73453aca254207Chris Lattner BCValue = getOrInitValueState(BI->getCondition()); 13628a8dbc35fe6da6b7d2633529b73453aca254207Chris Lattner else 13728a8dbc35fe6da6b7d2633529b73453aca254207Chris Lattner BCValue = getLatticeState(BI->getCondition()); 13828a8dbc35fe6da6b7d2633529b73453aca254207Chris Lattner 139ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner if (BCValue == LatticeFunc->getOverdefinedVal() || 140ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner BCValue == LatticeFunc->getUntrackedVal()) { 141ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner // Overdefined condition variables can branch either way. 142ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner Succs[0] = Succs[1] = true; 143ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner return; 144ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner } 145ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 146ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner // If undefined, neither is feasible yet. 147ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner if (BCValue == LatticeFunc->getUndefVal()) 148ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner return; 149ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 150ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner Constant *C = LatticeFunc->GetConstant(BCValue, BI->getCondition(), *this); 151dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!C || !isa<ConstantInt>(C)) { 152ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner // Non-constant values can go either way. 153ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner Succs[0] = Succs[1] = true; 154ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner return; 155ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner } 156ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 157ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner // Constant condition variables mean the branch can only go a single way 15843ea505fb07e303721d92f2b2bdda6e601868523Dan Gohman Succs[C->isNullValue()] = true; 159ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner return; 160ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner } 161ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 162ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner if (isa<InvokeInst>(TI)) { 163ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner // Invoke instructions successors are always executable. 164ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner // TODO: Could ask the lattice function if the value can throw. 165ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner Succs[0] = Succs[1] = true; 166ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner return; 167ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner } 168ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 169ab21db79ef1d2530880ad11f21f0b87ffca02dd4Chris Lattner if (isa<IndirectBrInst>(TI)) { 1702688bcbee188c1b5071f3a2b38923cd06013f490Chris Lattner Succs.assign(Succs.size(), true); 1712688bcbee188c1b5071f3a2b38923cd06013f490Chris Lattner return; 1722688bcbee188c1b5071f3a2b38923cd06013f490Chris Lattner } 1732688bcbee188c1b5071f3a2b38923cd06013f490Chris Lattner 174ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner SwitchInst &SI = cast<SwitchInst>(TI); 17528a8dbc35fe6da6b7d2633529b73453aca254207Chris Lattner LatticeVal SCValue; 17628a8dbc35fe6da6b7d2633529b73453aca254207Chris Lattner if (AggressiveUndef) 17728a8dbc35fe6da6b7d2633529b73453aca254207Chris Lattner SCValue = getOrInitValueState(SI.getCondition()); 17828a8dbc35fe6da6b7d2633529b73453aca254207Chris Lattner else 17928a8dbc35fe6da6b7d2633529b73453aca254207Chris Lattner SCValue = getLatticeState(SI.getCondition()); 18028a8dbc35fe6da6b7d2633529b73453aca254207Chris Lattner 181ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner if (SCValue == LatticeFunc->getOverdefinedVal() || 182ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner SCValue == LatticeFunc->getUntrackedVal()) { 183ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner // All destinations are executable! 184ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner Succs.assign(TI.getNumSuccessors(), true); 185ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner return; 186ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner } 187ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 188ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner // If undefined, neither is feasible yet. 189ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner if (SCValue == LatticeFunc->getUndefVal()) 190ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner return; 191ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 192ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner Constant *C = LatticeFunc->GetConstant(SCValue, SI.getCondition(), *this); 193dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!C || !isa<ConstantInt>(C)) { 194ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner // All destinations are executable! 195ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner Succs.assign(TI.getNumSuccessors(), true); 196ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner return; 197ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner } 198c10fa6c801e48771b5eade50afc2fe6abaf08227Stepan Dyatkovskiy SwitchInst::CaseIt Case = SI.findCaseValue(cast<ConstantInt>(C)); 199c10fa6c801e48771b5eade50afc2fe6abaf08227Stepan Dyatkovskiy Succs[Case.getSuccessorIndex()] = true; 200ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner} 201ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 202ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 203ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner/// isEdgeFeasible - Return true if the control flow edge from the 'From' 204ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner/// basic block to the 'To' basic block is currently feasible... 20528a8dbc35fe6da6b7d2633529b73453aca254207Chris Lattnerbool SparseSolver::isEdgeFeasible(BasicBlock *From, BasicBlock *To, 20628a8dbc35fe6da6b7d2633529b73453aca254207Chris Lattner bool AggressiveUndef) { 207ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner SmallVector<bool, 16> SuccFeasible; 208ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner TerminatorInst *TI = From->getTerminator(); 20928a8dbc35fe6da6b7d2633529b73453aca254207Chris Lattner getFeasibleSuccessors(*TI, SuccFeasible, AggressiveUndef); 210ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 211ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) 212ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner if (TI->getSuccessor(i) == To && SuccFeasible[i]) 213ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner return true; 214ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 215ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner return false; 216ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner} 217ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 218ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattnervoid SparseSolver::visitTerminatorInst(TerminatorInst &TI) { 219ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner SmallVector<bool, 16> SuccFeasible; 22028a8dbc35fe6da6b7d2633529b73453aca254207Chris Lattner getFeasibleSuccessors(TI, SuccFeasible, true); 221ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 222ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner BasicBlock *BB = TI.getParent(); 223ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 224ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner // Mark all feasible successors executable... 225ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner for (unsigned i = 0, e = SuccFeasible.size(); i != e; ++i) 226ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner if (SuccFeasible[i]) 227ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner markEdgeExecutable(BB, TI.getSuccessor(i)); 228ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner} 229ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 230ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattnervoid SparseSolver::visitPHINode(PHINode &PN) { 231c2fc1fec6c8c5360828aa778e8fcc446bb9c6ae9Nick Lewycky // The lattice function may store more information on a PHINode than could be 232c2fc1fec6c8c5360828aa778e8fcc446bb9c6ae9Nick Lewycky // computed from its incoming values. For example, SSI form stores its sigma 233c2fc1fec6c8c5360828aa778e8fcc446bb9c6ae9Nick Lewycky // functions as PHINodes with a single incoming value. 234875646f376f6c83bf8426fdb44e1dbf312cf784eNick Lewycky if (LatticeFunc->IsSpecialCasedPHI(&PN)) { 235875646f376f6c83bf8426fdb44e1dbf312cf784eNick Lewycky LatticeVal IV = LatticeFunc->ComputeInstructionState(PN, *this); 236875646f376f6c83bf8426fdb44e1dbf312cf784eNick Lewycky if (IV != LatticeFunc->getUntrackedVal()) 237875646f376f6c83bf8426fdb44e1dbf312cf784eNick Lewycky UpdateState(PN, IV); 238875646f376f6c83bf8426fdb44e1dbf312cf784eNick Lewycky return; 239875646f376f6c83bf8426fdb44e1dbf312cf784eNick Lewycky } 240875646f376f6c83bf8426fdb44e1dbf312cf784eNick Lewycky 241ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner LatticeVal PNIV = getOrInitValueState(&PN); 242ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner LatticeVal Overdefined = LatticeFunc->getOverdefinedVal(); 243ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 244ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner // If this value is already overdefined (common) just return. 245ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner if (PNIV == Overdefined || PNIV == LatticeFunc->getUntrackedVal()) 246ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner return; // Quick exit 247ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 248ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner // Super-extra-high-degree PHI nodes are unlikely to ever be interesting, 249ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner // and slow us down a lot. Just mark them overdefined. 250ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner if (PN.getNumIncomingValues() > 64) { 251ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner UpdateState(PN, Overdefined); 252ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner return; 253ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner } 254ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 255ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner // Look at all of the executable operands of the PHI node. If any of them 256ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner // are overdefined, the PHI becomes overdefined as well. Otherwise, ask the 257ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner // transfer function to give us the merge of the incoming values. 258ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) { 259ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner // If the edge is not yet known to be feasible, it doesn't impact the PHI. 26028a8dbc35fe6da6b7d2633529b73453aca254207Chris Lattner if (!isEdgeFeasible(PN.getIncomingBlock(i), PN.getParent(), true)) 261ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner continue; 262ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 263ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner // Merge in this value. 264ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner LatticeVal OpVal = getOrInitValueState(PN.getIncomingValue(i)); 265ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner if (OpVal != PNIV) 266ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner PNIV = LatticeFunc->MergeValues(PNIV, OpVal); 267ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 268ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner if (PNIV == Overdefined) 269ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner break; // Rest of input values don't matter. 270ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner } 271ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 272ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner // Update the PHI with the compute value, which is the merge of the inputs. 273ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner UpdateState(PN, PNIV); 274ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner} 275ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 276ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 277ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattnervoid SparseSolver::visitInst(Instruction &I) { 278ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner // PHIs are handled by the propagation logic, they are never passed into the 279ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner // transfer functions. 280ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner if (PHINode *PN = dyn_cast<PHINode>(&I)) 281ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner return visitPHINode(*PN); 282ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 283ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner // Otherwise, ask the transfer function what the result is. If this is 284ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner // something that we care about, remember it. 285ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner LatticeVal IV = LatticeFunc->ComputeInstructionState(I, *this); 286ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner if (IV != LatticeFunc->getUntrackedVal()) 287ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner UpdateState(I, IV); 288ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 289ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner if (TerminatorInst *TI = dyn_cast<TerminatorInst>(&I)) 290ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner visitTerminatorInst(*TI); 291ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner} 292ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 293ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattnervoid SparseSolver::Solve(Function &F) { 294ef61af01df5ab39141f532e821920da2f5341406Dan Gohman MarkBlockExecutable(&F.getEntryBlock()); 295ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 296ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner // Process the work lists until they are empty! 297ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner while (!BBWorkList.empty() || !InstWorkList.empty()) { 298ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner // Process the instruction work list. 299ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner while (!InstWorkList.empty()) { 300ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner Instruction *I = InstWorkList.back(); 301ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner InstWorkList.pop_back(); 302ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 30389282915fdc03561b7d87ecd91126db7643e304dDavid Greene DEBUG(dbgs() << "\nPopped off I-WL: " << *I << "\n"); 304ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 305ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner // "I" got into the work list because it made a transition. See if any 306ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner // users are both live and in need of updating. 30736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (User *U : I->users()) { 30836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Instruction *UI = cast<Instruction>(U); 30936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (BBExecutable.count(UI->getParent())) // Inst is executable? 31036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines visitInst(*UI); 311ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner } 312ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner } 313ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 314ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner // Process the basic block work list. 315ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner while (!BBWorkList.empty()) { 316ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner BasicBlock *BB = BBWorkList.back(); 317ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner BBWorkList.pop_back(); 318ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 31989282915fdc03561b7d87ecd91126db7643e304dDavid Greene DEBUG(dbgs() << "\nPopped off BBWL: " << *BB); 320ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 321ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner // Notify all instructions in this basic block that they are newly 322ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner // executable. 323ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) 324ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner visitInst(*I); 325ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner } 326ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner } 327ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner} 328ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 329bdff548e4dd577a72094d57b282de4e765643b96Chris Lattnervoid SparseSolver::Print(Function &F, raw_ostream &OS) const { 330a7b0cb759433c715065440ee2a963a04db7f2b0bBenjamin Kramer OS << "\nFUNCTION: " << F.getName() << "\n"; 331ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) { 332ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner if (!BBExecutable.count(BB)) 333ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner OS << "INFEASIBLE: "; 334ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner OS << "\t"; 335ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner if (BB->hasName()) 336a7b0cb759433c715065440ee2a963a04db7f2b0bBenjamin Kramer OS << BB->getName() << ":\n"; 337ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner else 338ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner OS << "; anon bb\n"; 339ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) { 340ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner LatticeFunc->PrintValue(getLatticeState(I), OS); 3411134dc5cc0cb83abcdf072dc4300cd7a898f830cNick Lewycky OS << *I << "\n"; 342ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner } 343ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 344ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner OS << "\n"; 345ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner } 346ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner} 347ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 348