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