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#define DEBUG_TYPE "sparseprop" 16ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner#include "llvm/Analysis/SparsePropagation.h" 17ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner#include "llvm/Constants.h" 18ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner#include "llvm/Function.h" 19ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner#include "llvm/Instructions.h" 20ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner#include "llvm/Support/Debug.h" 21460f656475738d1a95a6be95346908ce1597df25Daniel Dunbar#include "llvm/Support/raw_ostream.h" 22ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattnerusing namespace llvm; 23ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 24ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner//===----------------------------------------------------------------------===// 25ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner// AbstractLatticeFunction Implementation 26ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner//===----------------------------------------------------------------------===// 27ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 28ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris LattnerAbstractLatticeFunction::~AbstractLatticeFunction() {} 29ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 30ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner/// PrintValue - Render the specified lattice value to the specified stream. 31bdff548e4dd577a72094d57b282de4e765643b96Chris Lattnervoid AbstractLatticeFunction::PrintValue(LatticeVal V, raw_ostream &OS) { 32ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner if (V == UndefVal) 33ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner OS << "undefined"; 34ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner else if (V == OverdefinedVal) 35ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner OS << "overdefined"; 36ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner else if (V == UntrackedVal) 37ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner OS << "untracked"; 38ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner else 39ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner OS << "unknown lattice value"; 40ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner} 41ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 42ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner//===----------------------------------------------------------------------===// 43ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner// SparseSolver Implementation 44ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner//===----------------------------------------------------------------------===// 45ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 46ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner/// getOrInitValueState - Return the LatticeVal object that corresponds to the 47ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner/// value, initializing the value's state if it hasn't been entered into the 48ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner/// map yet. This function is necessary because not all values should start 49ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner/// out in the underdefined state... Arguments should be overdefined, and 50ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner/// constants should be marked as constants. 51ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner/// 52ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris LattnerSparseSolver::LatticeVal SparseSolver::getOrInitValueState(Value *V) { 53ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner DenseMap<Value*, LatticeVal>::iterator I = ValueState.find(V); 54ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner if (I != ValueState.end()) return I->second; // Common case, in the map 55ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 56ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner LatticeVal LV; 57ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner if (LatticeFunc->IsUntrackedValue(V)) 58ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner return LatticeFunc->getUntrackedVal(); 59ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner else if (Constant *C = dyn_cast<Constant>(V)) 60ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner LV = LatticeFunc->ComputeConstant(C); 61afcde473c5baf292038ec494917f18c77a043340Chris Lattner else if (Argument *A = dyn_cast<Argument>(V)) 62afcde473c5baf292038ec494917f18c77a043340Chris Lattner LV = LatticeFunc->ComputeArgument(A); 63ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner else if (!isa<Instruction>(V)) 64afcde473c5baf292038ec494917f18c77a043340Chris Lattner // All other non-instructions are overdefined. 65ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner LV = LatticeFunc->getOverdefinedVal(); 66ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner else 67ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner // All instructions are underdefined by default. 68ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner LV = LatticeFunc->getUndefVal(); 69ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 70ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner // If this value is untracked, don't add it to the map. 71ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner if (LV == LatticeFunc->getUntrackedVal()) 72ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner return LV; 73ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner return ValueState[V] = LV; 74ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner} 75ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 76ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner/// UpdateState - When the state for some instruction is potentially updated, 77ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner/// this function notices and adds I to the worklist if needed. 78ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattnervoid SparseSolver::UpdateState(Instruction &Inst, LatticeVal V) { 79ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner DenseMap<Value*, LatticeVal>::iterator I = ValueState.find(&Inst); 80ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner if (I != ValueState.end() && I->second == V) 81ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner return; // No change. 82ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 83ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner // An update. Visit uses of I. 84ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner ValueState[&Inst] = V; 85ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner InstWorkList.push_back(&Inst); 86ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner} 87ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 88ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner/// MarkBlockExecutable - This method can be used by clients to mark all of 89ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner/// the blocks that are known to be intrinsically live in the processed unit. 90ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattnervoid SparseSolver::MarkBlockExecutable(BasicBlock *BB) { 9189282915fdc03561b7d87ecd91126db7643e304dDavid Greene DEBUG(dbgs() << "Marking Block Executable: " << BB->getName() << "\n"); 92ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner BBExecutable.insert(BB); // Basic block is executable! 93ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner BBWorkList.push_back(BB); // Add the block to the work list! 94ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner} 95ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 96ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner/// markEdgeExecutable - Mark a basic block as executable, adding it to the BB 97ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner/// work list if it is not already executable... 98ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattnervoid SparseSolver::markEdgeExecutable(BasicBlock *Source, BasicBlock *Dest) { 99ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner if (!KnownFeasibleEdges.insert(Edge(Source, Dest)).second) 100ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner return; // This edge is already known to be executable! 101ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 10289282915fdc03561b7d87ecd91126db7643e304dDavid Greene DEBUG(dbgs() << "Marking Edge Executable: " << Source->getName() 103460f656475738d1a95a6be95346908ce1597df25Daniel Dunbar << " -> " << Dest->getName() << "\n"); 104b22d6ac348ca632bef17dc8050b14d8cb78218f3Dan Gohman 105ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner if (BBExecutable.count(Dest)) { 106ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner // The destination is already executable, but we just made an edge 107ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner // feasible that wasn't before. Revisit the PHI nodes in the block 108ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner // because they have potentially new operands. 109ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner for (BasicBlock::iterator I = Dest->begin(); isa<PHINode>(I); ++I) 110ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner visitPHINode(*cast<PHINode>(I)); 111ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 112ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner } else { 113ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner MarkBlockExecutable(Dest); 114ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner } 115ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner} 116ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 117ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 118ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner/// getFeasibleSuccessors - Return a vector of booleans to indicate which 119ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner/// successors are reachable from a given terminator instruction. 120ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattnervoid SparseSolver::getFeasibleSuccessors(TerminatorInst &TI, 12128a8dbc35fe6da6b7d2633529b73453aca254207Chris Lattner SmallVectorImpl<bool> &Succs, 12228a8dbc35fe6da6b7d2633529b73453aca254207Chris Lattner bool AggressiveUndef) { 123ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner Succs.resize(TI.getNumSuccessors()); 124ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner if (TI.getNumSuccessors() == 0) return; 125ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 126ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner if (BranchInst *BI = dyn_cast<BranchInst>(&TI)) { 127ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner if (BI->isUnconditional()) { 128ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner Succs[0] = true; 129ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner return; 130ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner } 131ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 13228a8dbc35fe6da6b7d2633529b73453aca254207Chris Lattner LatticeVal BCValue; 13328a8dbc35fe6da6b7d2633529b73453aca254207Chris Lattner if (AggressiveUndef) 13428a8dbc35fe6da6b7d2633529b73453aca254207Chris Lattner BCValue = getOrInitValueState(BI->getCondition()); 13528a8dbc35fe6da6b7d2633529b73453aca254207Chris Lattner else 13628a8dbc35fe6da6b7d2633529b73453aca254207Chris Lattner BCValue = getLatticeState(BI->getCondition()); 13728a8dbc35fe6da6b7d2633529b73453aca254207Chris Lattner 138ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner if (BCValue == LatticeFunc->getOverdefinedVal() || 139ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner BCValue == LatticeFunc->getUntrackedVal()) { 140ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner // Overdefined condition variables can branch either way. 141ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner Succs[0] = Succs[1] = true; 142ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner return; 143ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner } 144ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 145ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner // If undefined, neither is feasible yet. 146ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner if (BCValue == LatticeFunc->getUndefVal()) 147ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner return; 148ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 149ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner Constant *C = LatticeFunc->GetConstant(BCValue, BI->getCondition(), *this); 150ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner if (C == 0 || !isa<ConstantInt>(C)) { 151ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner // Non-constant values can go either way. 152ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner Succs[0] = Succs[1] = true; 153ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner return; 154ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner } 155ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 156ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner // Constant condition variables mean the branch can only go a single way 15743ea505fb07e303721d92f2b2bdda6e601868523Dan Gohman Succs[C->isNullValue()] = true; 158ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner return; 159ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner } 160ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 161ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner if (isa<InvokeInst>(TI)) { 162ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner // Invoke instructions successors are always executable. 163ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner // TODO: Could ask the lattice function if the value can throw. 164ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner Succs[0] = Succs[1] = true; 165ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner return; 166ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner } 167ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 168ab21db79ef1d2530880ad11f21f0b87ffca02dd4Chris Lattner if (isa<IndirectBrInst>(TI)) { 1692688bcbee188c1b5071f3a2b38923cd06013f490Chris Lattner Succs.assign(Succs.size(), true); 1702688bcbee188c1b5071f3a2b38923cd06013f490Chris Lattner return; 1712688bcbee188c1b5071f3a2b38923cd06013f490Chris Lattner } 1722688bcbee188c1b5071f3a2b38923cd06013f490Chris Lattner 173ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner SwitchInst &SI = cast<SwitchInst>(TI); 17428a8dbc35fe6da6b7d2633529b73453aca254207Chris Lattner LatticeVal SCValue; 17528a8dbc35fe6da6b7d2633529b73453aca254207Chris Lattner if (AggressiveUndef) 17628a8dbc35fe6da6b7d2633529b73453aca254207Chris Lattner SCValue = getOrInitValueState(SI.getCondition()); 17728a8dbc35fe6da6b7d2633529b73453aca254207Chris Lattner else 17828a8dbc35fe6da6b7d2633529b73453aca254207Chris Lattner SCValue = getLatticeState(SI.getCondition()); 17928a8dbc35fe6da6b7d2633529b73453aca254207Chris Lattner 180ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner if (SCValue == LatticeFunc->getOverdefinedVal() || 181ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner SCValue == LatticeFunc->getUntrackedVal()) { 182ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner // All destinations are executable! 183ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner Succs.assign(TI.getNumSuccessors(), true); 184ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner return; 185ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner } 186ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 187ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner // If undefined, neither is feasible yet. 188ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner if (SCValue == LatticeFunc->getUndefVal()) 189ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner return; 190ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 191ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner Constant *C = LatticeFunc->GetConstant(SCValue, SI.getCondition(), *this); 192ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner if (C == 0 || !isa<ConstantInt>(C)) { 193ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner // All destinations are executable! 194ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner Succs.assign(TI.getNumSuccessors(), true); 195ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner return; 196ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner } 197c10fa6c801e48771b5eade50afc2fe6abaf08227Stepan Dyatkovskiy SwitchInst::CaseIt Case = SI.findCaseValue(cast<ConstantInt>(C)); 198c10fa6c801e48771b5eade50afc2fe6abaf08227Stepan Dyatkovskiy Succs[Case.getSuccessorIndex()] = true; 199ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner} 200ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 201ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 202ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner/// isEdgeFeasible - Return true if the control flow edge from the 'From' 203ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner/// basic block to the 'To' basic block is currently feasible... 20428a8dbc35fe6da6b7d2633529b73453aca254207Chris Lattnerbool SparseSolver::isEdgeFeasible(BasicBlock *From, BasicBlock *To, 20528a8dbc35fe6da6b7d2633529b73453aca254207Chris Lattner bool AggressiveUndef) { 206ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner SmallVector<bool, 16> SuccFeasible; 207ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner TerminatorInst *TI = From->getTerminator(); 20828a8dbc35fe6da6b7d2633529b73453aca254207Chris Lattner getFeasibleSuccessors(*TI, SuccFeasible, AggressiveUndef); 209ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 210ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) 211ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner if (TI->getSuccessor(i) == To && SuccFeasible[i]) 212ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner return true; 213ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 214ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner return false; 215ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner} 216ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 217ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattnervoid SparseSolver::visitTerminatorInst(TerminatorInst &TI) { 218ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner SmallVector<bool, 16> SuccFeasible; 21928a8dbc35fe6da6b7d2633529b73453aca254207Chris Lattner getFeasibleSuccessors(TI, SuccFeasible, true); 220ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 221ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner BasicBlock *BB = TI.getParent(); 222ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 223ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner // Mark all feasible successors executable... 224ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner for (unsigned i = 0, e = SuccFeasible.size(); i != e; ++i) 225ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner if (SuccFeasible[i]) 226ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner markEdgeExecutable(BB, TI.getSuccessor(i)); 227ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner} 228ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 229ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattnervoid SparseSolver::visitPHINode(PHINode &PN) { 230c2fc1fec6c8c5360828aa778e8fcc446bb9c6ae9Nick Lewycky // The lattice function may store more information on a PHINode than could be 231c2fc1fec6c8c5360828aa778e8fcc446bb9c6ae9Nick Lewycky // computed from its incoming values. For example, SSI form stores its sigma 232c2fc1fec6c8c5360828aa778e8fcc446bb9c6ae9Nick Lewycky // functions as PHINodes with a single incoming value. 233875646f376f6c83bf8426fdb44e1dbf312cf784eNick Lewycky if (LatticeFunc->IsSpecialCasedPHI(&PN)) { 234875646f376f6c83bf8426fdb44e1dbf312cf784eNick Lewycky LatticeVal IV = LatticeFunc->ComputeInstructionState(PN, *this); 235875646f376f6c83bf8426fdb44e1dbf312cf784eNick Lewycky if (IV != LatticeFunc->getUntrackedVal()) 236875646f376f6c83bf8426fdb44e1dbf312cf784eNick Lewycky UpdateState(PN, IV); 237875646f376f6c83bf8426fdb44e1dbf312cf784eNick Lewycky return; 238875646f376f6c83bf8426fdb44e1dbf312cf784eNick Lewycky } 239875646f376f6c83bf8426fdb44e1dbf312cf784eNick Lewycky 240ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner LatticeVal PNIV = getOrInitValueState(&PN); 241ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner LatticeVal Overdefined = LatticeFunc->getOverdefinedVal(); 242ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 243ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner // If this value is already overdefined (common) just return. 244ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner if (PNIV == Overdefined || PNIV == LatticeFunc->getUntrackedVal()) 245ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner return; // Quick exit 246ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 247ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner // Super-extra-high-degree PHI nodes are unlikely to ever be interesting, 248ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner // and slow us down a lot. Just mark them overdefined. 249ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner if (PN.getNumIncomingValues() > 64) { 250ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner UpdateState(PN, Overdefined); 251ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner return; 252ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner } 253ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 254ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner // Look at all of the executable operands of the PHI node. If any of them 255ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner // are overdefined, the PHI becomes overdefined as well. Otherwise, ask the 256ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner // transfer function to give us the merge of the incoming values. 257ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) { 258ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner // If the edge is not yet known to be feasible, it doesn't impact the PHI. 25928a8dbc35fe6da6b7d2633529b73453aca254207Chris Lattner if (!isEdgeFeasible(PN.getIncomingBlock(i), PN.getParent(), true)) 260ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner continue; 261ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 262ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner // Merge in this value. 263ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner LatticeVal OpVal = getOrInitValueState(PN.getIncomingValue(i)); 264ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner if (OpVal != PNIV) 265ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner PNIV = LatticeFunc->MergeValues(PNIV, OpVal); 266ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 267ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner if (PNIV == Overdefined) 268ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner break; // Rest of input values don't matter. 269ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner } 270ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 271ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner // Update the PHI with the compute value, which is the merge of the inputs. 272ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner UpdateState(PN, PNIV); 273ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner} 274ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 275ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 276ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattnervoid SparseSolver::visitInst(Instruction &I) { 277ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner // PHIs are handled by the propagation logic, they are never passed into the 278ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner // transfer functions. 279ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner if (PHINode *PN = dyn_cast<PHINode>(&I)) 280ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner return visitPHINode(*PN); 281ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 282ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner // Otherwise, ask the transfer function what the result is. If this is 283ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner // something that we care about, remember it. 284ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner LatticeVal IV = LatticeFunc->ComputeInstructionState(I, *this); 285ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner if (IV != LatticeFunc->getUntrackedVal()) 286ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner UpdateState(I, IV); 287ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 288ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner if (TerminatorInst *TI = dyn_cast<TerminatorInst>(&I)) 289ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner visitTerminatorInst(*TI); 290ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner} 291ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 292ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattnervoid SparseSolver::Solve(Function &F) { 293ef61af01df5ab39141f532e821920da2f5341406Dan Gohman MarkBlockExecutable(&F.getEntryBlock()); 294ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 295ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner // Process the work lists until they are empty! 296ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner while (!BBWorkList.empty() || !InstWorkList.empty()) { 297ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner // Process the instruction work list. 298ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner while (!InstWorkList.empty()) { 299ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner Instruction *I = InstWorkList.back(); 300ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner InstWorkList.pop_back(); 301ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 30289282915fdc03561b7d87ecd91126db7643e304dDavid Greene DEBUG(dbgs() << "\nPopped off I-WL: " << *I << "\n"); 303ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner 304ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner // "I" got into the work list because it made a transition. See if any 305ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner // users are both live and in need of updating. 306ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); 307ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner UI != E; ++UI) { 308ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner Instruction *U = cast<Instruction>(*UI); 309ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner if (BBExecutable.count(U->getParent())) // Inst is executable? 310ab7d9ccf188da6b07977e3a003a0fe6a07b07e81Chris Lattner visitInst(*U); 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