CorrelatedValuePropagation.cpp revision 2ab36d350293c77fc8941ce1023e4899df7e3a82
1ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown//===- CorrelatedValuePropagation.cpp - Propagate CFG-derived info --------===// 2ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// 3ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// The LLVM Compiler Infrastructure 4ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// 5ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// This file is distributed under the University of Illinois Open Source 6ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// License. See LICENSE.TXT for details. 7ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// 8ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown//===----------------------------------------------------------------------===// 9ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// 10ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// This file implements the Correlated Value Propagation pass. 11ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// 12ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown//===----------------------------------------------------------------------===// 13ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 14ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#define DEBUG_TYPE "correlated-value-propagation" 15ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#include "llvm/Transforms/Scalar.h" 16ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#include "llvm/Function.h" 17ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#include "llvm/Instructions.h" 18ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#include "llvm/Pass.h" 19ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#include "llvm/Analysis/LazyValueInfo.h" 20ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#include "llvm/Support/CFG.h" 21ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#include "llvm/Transforms/Utils/Local.h" 22ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#include "llvm/ADT/DepthFirstIterator.h" 23ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#include "llvm/ADT/Statistic.h" 24ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownusing namespace llvm; 25ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 26ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownSTATISTIC(NumPhis, "Number of phis propagated"); 27ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownSTATISTIC(NumSelects, "Number of selects propagated"); 28ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownSTATISTIC(NumMemAccess, "Number of memory access targets propagated"); 29ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownSTATISTIC(NumCmps, "Number of comparisons propagated"); 30ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 31ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownnamespace { 32ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown class CorrelatedValuePropagation : public FunctionPass { 33ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown LazyValueInfo *LVI; 34ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 35ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bool processSelect(SelectInst *SI); 36ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bool processPHI(PHINode *P); 37ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bool processMemAccess(Instruction *I); 38ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bool processCmp(CmpInst *C); 39ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 40ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown public: 41ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown static char ID; 42ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown CorrelatedValuePropagation(): FunctionPass(ID) { } 43ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 44ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bool runOnFunction(Function &F); 45ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 46ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown virtual void getAnalysisUsage(AnalysisUsage &AU) const { 47ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown AU.addRequired<LazyValueInfo>(); 48ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 49ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown }; 50ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 51ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 52ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownchar CorrelatedValuePropagation::ID = 0; 53ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownINITIALIZE_PASS_BEGIN(CorrelatedValuePropagation, "correlated-propagation", 54b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov "Value Propagation", false, false) 55ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownINITIALIZE_PASS_DEPENDENCY(LazyValueInfo) 56ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownINITIALIZE_PASS_END(CorrelatedValuePropagation, "correlated-propagation", 57ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown "Value Propagation", false, false) 58ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 59ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// Public interface to the Value Propagation pass 60ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownPass *llvm::createCorrelatedValuePropagationPass() { 61ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return new CorrelatedValuePropagation(); 62ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 63ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 64ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownbool CorrelatedValuePropagation::processSelect(SelectInst *S) { 65ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (S->getType()->isVectorTy()) return false; 66ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (isa<Constant>(S->getOperand(0))) return false; 67ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 68ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Constant *C = LVI->getConstant(S->getOperand(0), S->getParent()); 69ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (!C) return false; 70ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 71ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown ConstantInt *CI = dyn_cast<ConstantInt>(C); 72ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (!CI) return false; 73ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 74ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown S->replaceAllUsesWith(S->getOperand(CI->isOne() ? 1 : 2)); 75ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown S->eraseFromParent(); 76ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 77ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown ++NumSelects; 78ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 79ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return true; 80ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 81ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 82ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownbool CorrelatedValuePropagation::processPHI(PHINode *P) { 83ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bool Changed = false; 84ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 85ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown BasicBlock *BB = P->getParent(); 86ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (unsigned i = 0, e = P->getNumIncomingValues(); i < e; ++i) { 87ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Value *Incoming = P->getIncomingValue(i); 88ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (isa<Constant>(Incoming)) continue; 89ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 90ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Constant *C = LVI->getConstantOnEdge(P->getIncomingValue(i), 91ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown P->getIncomingBlock(i), 92ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown BB); 93ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (!C) continue; 94ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 95ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown P->setIncomingValue(i, C); 96ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Changed = true; 97ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 98ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 99ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (Value *ConstVal = P->hasConstantValue()) { 100ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown P->replaceAllUsesWith(ConstVal); 101ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown P->eraseFromParent(); 102ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Changed = true; 103ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 104ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 105ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown ++NumPhis; 106ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 107ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return Changed; 108ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 109b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov 110ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownbool CorrelatedValuePropagation::processMemAccess(Instruction *I) { 111ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Value *Pointer = 0; 112ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (LoadInst *L = dyn_cast<LoadInst>(I)) 113ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Pointer = L->getPointerOperand(); 114ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown else 115ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Pointer = cast<StoreInst>(I)->getPointerOperand(); 116ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 117ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (isa<Constant>(Pointer)) return false; 118ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 119ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Constant *C = LVI->getConstant(Pointer, I->getParent()); 120ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (!C) return false; 121ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 122ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown ++NumMemAccess; 123ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown I->replaceUsesOfWith(Pointer, C); 124ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return true; 125ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 126ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 127ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/// processCmp - If the value of this comparison could be determined locally, 128ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/// constant propagation would already have figured it out. Instead, walk 129ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/// the predecessors and statically evaluate the comparison based on information 130ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/// available on that edge. If a given static evaluation is true on ALL 131ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/// incoming edges, then it's true universally and we can simplify the compare. 132ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownbool CorrelatedValuePropagation::processCmp(CmpInst *C) { 133ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Value *Op0 = C->getOperand(0); 134ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (isa<Instruction>(Op0) && 135ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown cast<Instruction>(Op0)->getParent() == C->getParent()) 136ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return false; 137ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 138ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Constant *Op1 = dyn_cast<Constant>(C->getOperand(1)); 139ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (!Op1) return false; 140ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 141ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown pred_iterator PI = pred_begin(C->getParent()), PE = pred_end(C->getParent()); 142ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (PI == PE) return false; 143ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 144ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown LazyValueInfo::Tristate Result = LVI->getPredicateOnEdge(C->getPredicate(), 145ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown C->getOperand(0), Op1, *PI, C->getParent()); 146ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (Result == LazyValueInfo::Unknown) return false; 147ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 148ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown ++PI; 149ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while (PI != PE) { 150ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown LazyValueInfo::Tristate Res = LVI->getPredicateOnEdge(C->getPredicate(), 151ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown C->getOperand(0), Op1, *PI, C->getParent()); 152ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (Res != Result) return false; 153ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown ++PI; 154b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov } 155ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 156ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown ++NumCmps; 157ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 158ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (Result == LazyValueInfo::True) 159ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown C->replaceAllUsesWith(ConstantInt::getTrue(C->getContext())); 160ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown else 161ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown C->replaceAllUsesWith(ConstantInt::getFalse(C->getContext())); 162ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 163ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown C->eraseFromParent(); 164ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 165ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return true; 166ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 167ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 168ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownbool CorrelatedValuePropagation::runOnFunction(Function &F) { 169ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown LVI = &getAnalysis<LazyValueInfo>(); 170ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 171ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bool FnChanged = false; 172ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 173ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Perform a depth-first walk of the CFG so that we don't waste time 174ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // optimizing unreachable blocks. 175ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (df_iterator<BasicBlock*> FI = df_begin(&F.getEntryBlock()), 176ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown FE = df_end(&F.getEntryBlock()); FI != FE; ++FI) { 177ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bool BBChanged = false; 178ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (BasicBlock::iterator BI = FI->begin(), BE = FI->end(); BI != BE; ) { 179ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Instruction *II = BI++; 180ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown switch (II->getOpcode()) { 181ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown case Instruction::Select: 182ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown BBChanged |= processSelect(cast<SelectInst>(II)); 183ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown break; 184ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown case Instruction::PHI: 185ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown BBChanged |= processPHI(cast<PHINode>(II)); 186ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown break; 187ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown case Instruction::ICmp: 188ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown case Instruction::FCmp: 189ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown BBChanged |= processCmp(cast<CmpInst>(II)); 190ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown break; 191ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown case Instruction::Load: 192ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown case Instruction::Store: 193ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown BBChanged |= processMemAccess(II); 194ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown break; 195ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 196ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 197ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 198ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Propagating correlated values might leave cruft around. 199ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Try to clean it up before we continue. 200ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (BBChanged) 201ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown SimplifyInstructionsInBlock(*FI); 202ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 203ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown FnChanged |= BBChanged; 204ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 205ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 206ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return FnChanged; 207ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 208ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown