125e9405272630204eb721d8b6ab47a5a25f24885Owen Anderson//===- CorrelatedValuePropagation.cpp - Propagate CFG-derived info --------===// 2a0b59f6bd23afaeba923b94f46838cffd5218a12Owen Anderson// 3a0b59f6bd23afaeba923b94f46838cffd5218a12Owen Anderson// The LLVM Compiler Infrastructure 4a0b59f6bd23afaeba923b94f46838cffd5218a12Owen Anderson// 5a0b59f6bd23afaeba923b94f46838cffd5218a12Owen Anderson// This file is distributed under the University of Illinois Open Source 6a0b59f6bd23afaeba923b94f46838cffd5218a12Owen Anderson// License. See LICENSE.TXT for details. 7a0b59f6bd23afaeba923b94f46838cffd5218a12Owen Anderson// 8a0b59f6bd23afaeba923b94f46838cffd5218a12Owen Anderson//===----------------------------------------------------------------------===// 9a0b59f6bd23afaeba923b94f46838cffd5218a12Owen Anderson// 1025e9405272630204eb721d8b6ab47a5a25f24885Owen Anderson// This file implements the Correlated Value Propagation pass. 11a0b59f6bd23afaeba923b94f46838cffd5218a12Owen Anderson// 12a0b59f6bd23afaeba923b94f46838cffd5218a12Owen Anderson//===----------------------------------------------------------------------===// 13a0b59f6bd23afaeba923b94f46838cffd5218a12Owen Anderson 1425e9405272630204eb721d8b6ab47a5a25f24885Owen Anderson#define DEBUG_TYPE "correlated-value-propagation" 15a0b59f6bd23afaeba923b94f46838cffd5218a12Owen Anderson#include "llvm/Transforms/Scalar.h" 16d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/Statistic.h" 17d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Analysis/InstructionSimplify.h" 18d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Analysis/LazyValueInfo.h" 190b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Constants.h" 200b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Function.h" 210b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Instructions.h" 22a0b59f6bd23afaeba923b94f46838cffd5218a12Owen Anderson#include "llvm/Pass.h" 23597dad35b8b86c076dbbb0d095319c79de7806caOwen Anderson#include "llvm/Support/CFG.h" 24e8aa36a4afa02dde89e10f39b6ca87cfe1949dd8Benjamin Kramer#include "llvm/Support/Debug.h" 25e8aa36a4afa02dde89e10f39b6ca87cfe1949dd8Benjamin Kramer#include "llvm/Support/raw_ostream.h" 26a0b59f6bd23afaeba923b94f46838cffd5218a12Owen Anderson#include "llvm/Transforms/Utils/Local.h" 27a0b59f6bd23afaeba923b94f46838cffd5218a12Owen Andersonusing namespace llvm; 28a0b59f6bd23afaeba923b94f46838cffd5218a12Owen Anderson 291593dd6779d7ab1db13c44f32f987c32aff2b54bOwen AndersonSTATISTIC(NumPhis, "Number of phis propagated"); 301593dd6779d7ab1db13c44f32f987c32aff2b54bOwen AndersonSTATISTIC(NumSelects, "Number of selects propagated"); 311593dd6779d7ab1db13c44f32f987c32aff2b54bOwen AndersonSTATISTIC(NumMemAccess, "Number of memory access targets propagated"); 32597dad35b8b86c076dbbb0d095319c79de7806caOwen AndersonSTATISTIC(NumCmps, "Number of comparisons propagated"); 33a8eb6bb408e84ceb468ceb409f4c87308e67b9ebDuncan SandsSTATISTIC(NumDeadCases, "Number of switch cases removed"); 34f523b3e0878ea47e72b7d880b8fd18a33636fbdeOwen Anderson 35a0b59f6bd23afaeba923b94f46838cffd5218a12Owen Andersonnamespace { 3625e9405272630204eb721d8b6ab47a5a25f24885Owen Anderson class CorrelatedValuePropagation : public FunctionPass { 37a0b59f6bd23afaeba923b94f46838cffd5218a12Owen Anderson LazyValueInfo *LVI; 3893f83deba1df95211898fe756758e81969955bd9Owen Anderson 39a0b59f6bd23afaeba923b94f46838cffd5218a12Owen Anderson bool processSelect(SelectInst *SI); 40a0b59f6bd23afaeba923b94f46838cffd5218a12Owen Anderson bool processPHI(PHINode *P); 411593dd6779d7ab1db13c44f32f987c32aff2b54bOwen Anderson bool processMemAccess(Instruction *I); 42597dad35b8b86c076dbbb0d095319c79de7806caOwen Anderson bool processCmp(CmpInst *C); 436f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands bool processSwitch(SwitchInst *SI); 4493f83deba1df95211898fe756758e81969955bd9Owen Anderson 45a0b59f6bd23afaeba923b94f46838cffd5218a12Owen Anderson public: 46a0b59f6bd23afaeba923b94f46838cffd5218a12Owen Anderson static char ID; 47081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson CorrelatedValuePropagation(): FunctionPass(ID) { 48081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeCorrelatedValuePropagationPass(*PassRegistry::getPassRegistry()); 49081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson } 5093f83deba1df95211898fe756758e81969955bd9Owen Anderson 51a0b59f6bd23afaeba923b94f46838cffd5218a12Owen Anderson bool runOnFunction(Function &F); 5293f83deba1df95211898fe756758e81969955bd9Owen Anderson 53a0b59f6bd23afaeba923b94f46838cffd5218a12Owen Anderson virtual void getAnalysisUsage(AnalysisUsage &AU) const { 54a0b59f6bd23afaeba923b94f46838cffd5218a12Owen Anderson AU.addRequired<LazyValueInfo>(); 55a0b59f6bd23afaeba923b94f46838cffd5218a12Owen Anderson } 56a0b59f6bd23afaeba923b94f46838cffd5218a12Owen Anderson }; 57a0b59f6bd23afaeba923b94f46838cffd5218a12Owen Anderson} 58a0b59f6bd23afaeba923b94f46838cffd5218a12Owen Anderson 5925e9405272630204eb721d8b6ab47a5a25f24885Owen Andersonchar CorrelatedValuePropagation::ID = 0; 602ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_BEGIN(CorrelatedValuePropagation, "correlated-propagation", 612ab36d350293c77fc8941ce1023e4899df7e3a82Owen Anderson "Value Propagation", false, false) 622ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(LazyValueInfo) 632ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_END(CorrelatedValuePropagation, "correlated-propagation", 64ce665bd2e2b581ab0858d1afe359192bac96b868Owen Anderson "Value Propagation", false, false) 65a0b59f6bd23afaeba923b94f46838cffd5218a12Owen Anderson 66a0b59f6bd23afaeba923b94f46838cffd5218a12Owen Anderson// Public interface to the Value Propagation pass 6725e9405272630204eb721d8b6ab47a5a25f24885Owen AndersonPass *llvm::createCorrelatedValuePropagationPass() { 6825e9405272630204eb721d8b6ab47a5a25f24885Owen Anderson return new CorrelatedValuePropagation(); 69a0b59f6bd23afaeba923b94f46838cffd5218a12Owen Anderson} 70a0b59f6bd23afaeba923b94f46838cffd5218a12Owen Anderson 7125e9405272630204eb721d8b6ab47a5a25f24885Owen Andersonbool CorrelatedValuePropagation::processSelect(SelectInst *S) { 72a081d15b842e87c670260006eb17b5c1a826b5eeOwen Anderson if (S->getType()->isVectorTy()) return false; 731593dd6779d7ab1db13c44f32f987c32aff2b54bOwen Anderson if (isa<Constant>(S->getOperand(0))) return false; 7493f83deba1df95211898fe756758e81969955bd9Owen Anderson 75a0b59f6bd23afaeba923b94f46838cffd5218a12Owen Anderson Constant *C = LVI->getConstant(S->getOperand(0), S->getParent()); 76a0b59f6bd23afaeba923b94f46838cffd5218a12Owen Anderson if (!C) return false; 7793f83deba1df95211898fe756758e81969955bd9Owen Anderson 78a0b59f6bd23afaeba923b94f46838cffd5218a12Owen Anderson ConstantInt *CI = dyn_cast<ConstantInt>(C); 79a0b59f6bd23afaeba923b94f46838cffd5218a12Owen Anderson if (!CI) return false; 8093f83deba1df95211898fe756758e81969955bd9Owen Anderson 8186e8a700f516e8993417fb57d5386614b35c775dOwen Anderson Value *ReplaceWith = S->getOperand(1); 8286e8a700f516e8993417fb57d5386614b35c775dOwen Anderson Value *Other = S->getOperand(2); 8386e8a700f516e8993417fb57d5386614b35c775dOwen Anderson if (!CI->isOne()) std::swap(ReplaceWith, Other); 8486e8a700f516e8993417fb57d5386614b35c775dOwen Anderson if (ReplaceWith == S) ReplaceWith = UndefValue::get(S->getType()); 8586e8a700f516e8993417fb57d5386614b35c775dOwen Anderson 8686e8a700f516e8993417fb57d5386614b35c775dOwen Anderson S->replaceAllUsesWith(ReplaceWith); 87a081d15b842e87c670260006eb17b5c1a826b5eeOwen Anderson S->eraseFromParent(); 88a081d15b842e87c670260006eb17b5c1a826b5eeOwen Anderson 89f523b3e0878ea47e72b7d880b8fd18a33636fbdeOwen Anderson ++NumSelects; 9093f83deba1df95211898fe756758e81969955bd9Owen Anderson 91a0b59f6bd23afaeba923b94f46838cffd5218a12Owen Anderson return true; 92a0b59f6bd23afaeba923b94f46838cffd5218a12Owen Anderson} 93a0b59f6bd23afaeba923b94f46838cffd5218a12Owen Anderson 9425e9405272630204eb721d8b6ab47a5a25f24885Owen Andersonbool CorrelatedValuePropagation::processPHI(PHINode *P) { 95a081d15b842e87c670260006eb17b5c1a826b5eeOwen Anderson bool Changed = false; 9693f83deba1df95211898fe756758e81969955bd9Owen Anderson 97a0b59f6bd23afaeba923b94f46838cffd5218a12Owen Anderson BasicBlock *BB = P->getParent(); 98a081d15b842e87c670260006eb17b5c1a826b5eeOwen Anderson for (unsigned i = 0, e = P->getNumIncomingValues(); i < e; ++i) { 99a081d15b842e87c670260006eb17b5c1a826b5eeOwen Anderson Value *Incoming = P->getIncomingValue(i); 100a081d15b842e87c670260006eb17b5c1a826b5eeOwen Anderson if (isa<Constant>(Incoming)) continue; 10193f83deba1df95211898fe756758e81969955bd9Owen Anderson 102e8aa36a4afa02dde89e10f39b6ca87cfe1949dd8Benjamin Kramer Value *V = LVI->getConstantOnEdge(Incoming, P->getIncomingBlock(i), BB); 10393f83deba1df95211898fe756758e81969955bd9Owen Anderson 104e8aa36a4afa02dde89e10f39b6ca87cfe1949dd8Benjamin Kramer // Look if the incoming value is a select with a constant but LVI tells us 105e8aa36a4afa02dde89e10f39b6ca87cfe1949dd8Benjamin Kramer // that the incoming value can never be that constant. In that case replace 106e8aa36a4afa02dde89e10f39b6ca87cfe1949dd8Benjamin Kramer // the incoming value with the other value of the select. This often allows 107e8aa36a4afa02dde89e10f39b6ca87cfe1949dd8Benjamin Kramer // us to remove the select later. 108e8aa36a4afa02dde89e10f39b6ca87cfe1949dd8Benjamin Kramer if (!V) { 109e8aa36a4afa02dde89e10f39b6ca87cfe1949dd8Benjamin Kramer SelectInst *SI = dyn_cast<SelectInst>(Incoming); 110e8aa36a4afa02dde89e10f39b6ca87cfe1949dd8Benjamin Kramer if (!SI) continue; 111e8aa36a4afa02dde89e10f39b6ca87cfe1949dd8Benjamin Kramer 112e8aa36a4afa02dde89e10f39b6ca87cfe1949dd8Benjamin Kramer Constant *C = dyn_cast<Constant>(SI->getFalseValue()); 113e8aa36a4afa02dde89e10f39b6ca87cfe1949dd8Benjamin Kramer if (!C) continue; 114e8aa36a4afa02dde89e10f39b6ca87cfe1949dd8Benjamin Kramer 115e8aa36a4afa02dde89e10f39b6ca87cfe1949dd8Benjamin Kramer if (LVI->getPredicateOnEdge(ICmpInst::ICMP_EQ, SI, C, 116e8aa36a4afa02dde89e10f39b6ca87cfe1949dd8Benjamin Kramer P->getIncomingBlock(i), BB) != 117e8aa36a4afa02dde89e10f39b6ca87cfe1949dd8Benjamin Kramer LazyValueInfo::False) 118e8aa36a4afa02dde89e10f39b6ca87cfe1949dd8Benjamin Kramer continue; 119e8aa36a4afa02dde89e10f39b6ca87cfe1949dd8Benjamin Kramer 120e8aa36a4afa02dde89e10f39b6ca87cfe1949dd8Benjamin Kramer DEBUG(dbgs() << "CVP: Threading PHI over " << *SI << '\n'); 121e8aa36a4afa02dde89e10f39b6ca87cfe1949dd8Benjamin Kramer V = SI->getTrueValue(); 122e8aa36a4afa02dde89e10f39b6ca87cfe1949dd8Benjamin Kramer } 123e8aa36a4afa02dde89e10f39b6ca87cfe1949dd8Benjamin Kramer 124e8aa36a4afa02dde89e10f39b6ca87cfe1949dd8Benjamin Kramer P->setIncomingValue(i, V); 125a081d15b842e87c670260006eb17b5c1a826b5eeOwen Anderson Changed = true; 126a0b59f6bd23afaeba923b94f46838cffd5218a12Owen Anderson } 127cdbd99262286e96729007ac535cd430ecb3d38acDuncan Sands 128cdbd99262286e96729007ac535cd430ecb3d38acDuncan Sands if (Value *V = SimplifyInstruction(P)) { 129cdbd99262286e96729007ac535cd430ecb3d38acDuncan Sands P->replaceAllUsesWith(V); 130a0b59f6bd23afaeba923b94f46838cffd5218a12Owen Anderson P->eraseFromParent(); 131a081d15b842e87c670260006eb17b5c1a826b5eeOwen Anderson Changed = true; 132a0b59f6bd23afaeba923b94f46838cffd5218a12Owen Anderson } 133cdbd99262286e96729007ac535cd430ecb3d38acDuncan Sands 134a8eb6bb408e84ceb468ceb409f4c87308e67b9ebDuncan Sands if (Changed) 135a8eb6bb408e84ceb468ceb409f4c87308e67b9ebDuncan Sands ++NumPhis; 13693f83deba1df95211898fe756758e81969955bd9Owen Anderson 137a081d15b842e87c670260006eb17b5c1a826b5eeOwen Anderson return Changed; 138a0b59f6bd23afaeba923b94f46838cffd5218a12Owen Anderson} 139a0b59f6bd23afaeba923b94f46838cffd5218a12Owen Anderson 1401593dd6779d7ab1db13c44f32f987c32aff2b54bOwen Andersonbool CorrelatedValuePropagation::processMemAccess(Instruction *I) { 1411593dd6779d7ab1db13c44f32f987c32aff2b54bOwen Anderson Value *Pointer = 0; 1421593dd6779d7ab1db13c44f32f987c32aff2b54bOwen Anderson if (LoadInst *L = dyn_cast<LoadInst>(I)) 1431593dd6779d7ab1db13c44f32f987c32aff2b54bOwen Anderson Pointer = L->getPointerOperand(); 1441593dd6779d7ab1db13c44f32f987c32aff2b54bOwen Anderson else 1451593dd6779d7ab1db13c44f32f987c32aff2b54bOwen Anderson Pointer = cast<StoreInst>(I)->getPointerOperand(); 14693f83deba1df95211898fe756758e81969955bd9Owen Anderson 1471593dd6779d7ab1db13c44f32f987c32aff2b54bOwen Anderson if (isa<Constant>(Pointer)) return false; 14893f83deba1df95211898fe756758e81969955bd9Owen Anderson 1491593dd6779d7ab1db13c44f32f987c32aff2b54bOwen Anderson Constant *C = LVI->getConstant(Pointer, I->getParent()); 1501593dd6779d7ab1db13c44f32f987c32aff2b54bOwen Anderson if (!C) return false; 15193f83deba1df95211898fe756758e81969955bd9Owen Anderson 1521593dd6779d7ab1db13c44f32f987c32aff2b54bOwen Anderson ++NumMemAccess; 1531593dd6779d7ab1db13c44f32f987c32aff2b54bOwen Anderson I->replaceUsesOfWith(Pointer, C); 1541593dd6779d7ab1db13c44f32f987c32aff2b54bOwen Anderson return true; 1551593dd6779d7ab1db13c44f32f987c32aff2b54bOwen Anderson} 1561593dd6779d7ab1db13c44f32f987c32aff2b54bOwen Anderson 157597dad35b8b86c076dbbb0d095319c79de7806caOwen Anderson/// processCmp - If the value of this comparison could be determined locally, 158597dad35b8b86c076dbbb0d095319c79de7806caOwen Anderson/// constant propagation would already have figured it out. Instead, walk 159597dad35b8b86c076dbbb0d095319c79de7806caOwen Anderson/// the predecessors and statically evaluate the comparison based on information 160597dad35b8b86c076dbbb0d095319c79de7806caOwen Anderson/// available on that edge. If a given static evaluation is true on ALL 161597dad35b8b86c076dbbb0d095319c79de7806caOwen Anderson/// incoming edges, then it's true universally and we can simplify the compare. 162597dad35b8b86c076dbbb0d095319c79de7806caOwen Andersonbool CorrelatedValuePropagation::processCmp(CmpInst *C) { 163597dad35b8b86c076dbbb0d095319c79de7806caOwen Anderson Value *Op0 = C->getOperand(0); 164597dad35b8b86c076dbbb0d095319c79de7806caOwen Anderson if (isa<Instruction>(Op0) && 165597dad35b8b86c076dbbb0d095319c79de7806caOwen Anderson cast<Instruction>(Op0)->getParent() == C->getParent()) 166597dad35b8b86c076dbbb0d095319c79de7806caOwen Anderson return false; 16793f83deba1df95211898fe756758e81969955bd9Owen Anderson 168597dad35b8b86c076dbbb0d095319c79de7806caOwen Anderson Constant *Op1 = dyn_cast<Constant>(C->getOperand(1)); 169597dad35b8b86c076dbbb0d095319c79de7806caOwen Anderson if (!Op1) return false; 17093f83deba1df95211898fe756758e81969955bd9Owen Anderson 171597dad35b8b86c076dbbb0d095319c79de7806caOwen Anderson pred_iterator PI = pred_begin(C->getParent()), PE = pred_end(C->getParent()); 172597dad35b8b86c076dbbb0d095319c79de7806caOwen Anderson if (PI == PE) return false; 17393f83deba1df95211898fe756758e81969955bd9Owen Anderson 17493f83deba1df95211898fe756758e81969955bd9Owen Anderson LazyValueInfo::Tristate Result = LVI->getPredicateOnEdge(C->getPredicate(), 175597dad35b8b86c076dbbb0d095319c79de7806caOwen Anderson C->getOperand(0), Op1, *PI, C->getParent()); 176597dad35b8b86c076dbbb0d095319c79de7806caOwen Anderson if (Result == LazyValueInfo::Unknown) return false; 177597dad35b8b86c076dbbb0d095319c79de7806caOwen Anderson 178597dad35b8b86c076dbbb0d095319c79de7806caOwen Anderson ++PI; 179597dad35b8b86c076dbbb0d095319c79de7806caOwen Anderson while (PI != PE) { 18093f83deba1df95211898fe756758e81969955bd9Owen Anderson LazyValueInfo::Tristate Res = LVI->getPredicateOnEdge(C->getPredicate(), 181597dad35b8b86c076dbbb0d095319c79de7806caOwen Anderson C->getOperand(0), Op1, *PI, C->getParent()); 182597dad35b8b86c076dbbb0d095319c79de7806caOwen Anderson if (Res != Result) return false; 183597dad35b8b86c076dbbb0d095319c79de7806caOwen Anderson ++PI; 184597dad35b8b86c076dbbb0d095319c79de7806caOwen Anderson } 18593f83deba1df95211898fe756758e81969955bd9Owen Anderson 186597dad35b8b86c076dbbb0d095319c79de7806caOwen Anderson ++NumCmps; 18793f83deba1df95211898fe756758e81969955bd9Owen Anderson 188597dad35b8b86c076dbbb0d095319c79de7806caOwen Anderson if (Result == LazyValueInfo::True) 189597dad35b8b86c076dbbb0d095319c79de7806caOwen Anderson C->replaceAllUsesWith(ConstantInt::getTrue(C->getContext())); 190597dad35b8b86c076dbbb0d095319c79de7806caOwen Anderson else 191597dad35b8b86c076dbbb0d095319c79de7806caOwen Anderson C->replaceAllUsesWith(ConstantInt::getFalse(C->getContext())); 19293f83deba1df95211898fe756758e81969955bd9Owen Anderson 193597dad35b8b86c076dbbb0d095319c79de7806caOwen Anderson C->eraseFromParent(); 194597dad35b8b86c076dbbb0d095319c79de7806caOwen Anderson 195597dad35b8b86c076dbbb0d095319c79de7806caOwen Anderson return true; 196597dad35b8b86c076dbbb0d095319c79de7806caOwen Anderson} 197597dad35b8b86c076dbbb0d095319c79de7806caOwen Anderson 1986f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands/// processSwitch - Simplify a switch instruction by removing cases which can 1996f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands/// never fire. If the uselessness of a case could be determined locally then 2006f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands/// constant propagation would already have figured it out. Instead, walk the 2016f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands/// predecessors and statically evaluate cases based on information available 2026f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands/// on that edge. Cases that cannot fire no matter what the incoming edge can 2036f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands/// safely be removed. If a case fires on every incoming edge then the entire 2046f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands/// switch can be removed and replaced with a branch to the case destination. 2056f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sandsbool CorrelatedValuePropagation::processSwitch(SwitchInst *SI) { 2066f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands Value *Cond = SI->getCondition(); 2076f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands BasicBlock *BB = SI->getParent(); 2086f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands 2096f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands // If the condition was defined in same block as the switch then LazyValueInfo 2106f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands // currently won't say anything useful about it, though in theory it could. 2116f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands if (isa<Instruction>(Cond) && cast<Instruction>(Cond)->getParent() == BB) 2126f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands return false; 2136f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands 2146f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands // If the switch is unreachable then trying to improve it is a waste of time. 2156f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands pred_iterator PB = pred_begin(BB), PE = pred_end(BB); 2166f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands if (PB == PE) return false; 2176f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands 2186f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands // Analyse each switch case in turn. This is done in reverse order so that 2196f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands // removing a case doesn't cause trouble for the iteration. 2206f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands bool Changed = false; 2213d3abe0852d5f499bed7ab014519dd582a0a795dStepan Dyatkovskiy for (SwitchInst::CaseIt CI = SI->case_end(), CE = SI->case_begin(); CI-- != CE; 2226f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands ) { 2236f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands ConstantInt *Case = CI.getCaseValue(); 2246f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands 2256f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands // Check to see if the switch condition is equal to/not equal to the case 2266f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands // value on every incoming edge, equal/not equal being the same each time. 2276f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands LazyValueInfo::Tristate State = LazyValueInfo::Unknown; 2286f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands for (pred_iterator PI = PB; PI != PE; ++PI) { 2296f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands // Is the switch condition equal to the case value? 2306f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands LazyValueInfo::Tristate Value = LVI->getPredicateOnEdge(CmpInst::ICMP_EQ, 2316f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands Cond, Case, *PI, BB); 2326f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands // Give up on this case if nothing is known. 2336f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands if (Value == LazyValueInfo::Unknown) { 2346f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands State = LazyValueInfo::Unknown; 2356f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands break; 2366f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands } 2376f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands 2386f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands // If this was the first edge to be visited, record that all other edges 2396f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands // need to give the same result. 2406f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands if (PI == PB) { 2416f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands State = Value; 2426f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands continue; 2436f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands } 2446f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands 2456f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands // If this case is known to fire for some edges and known not to fire for 2466f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands // others then there is nothing we can do - give up. 2476f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands if (Value != State) { 2486f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands State = LazyValueInfo::Unknown; 2496f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands break; 2506f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands } 2516f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands } 2526f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands 2536f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands if (State == LazyValueInfo::False) { 2546f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands // This case never fires - remove it. 2556f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands CI.getCaseSuccessor()->removePredecessor(BB); 2566f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands SI->removeCase(CI); // Does not invalidate the iterator. 2578be16fe70395c30762081388b8f6df323ddc82ebBenjamin Kramer 2588be16fe70395c30762081388b8f6df323ddc82ebBenjamin Kramer // The condition can be modified by removePredecessor's PHI simplification 2598be16fe70395c30762081388b8f6df323ddc82ebBenjamin Kramer // logic. 2608be16fe70395c30762081388b8f6df323ddc82ebBenjamin Kramer Cond = SI->getCondition(); 2618be16fe70395c30762081388b8f6df323ddc82ebBenjamin Kramer 262a8eb6bb408e84ceb468ceb409f4c87308e67b9ebDuncan Sands ++NumDeadCases; 2636f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands Changed = true; 2646f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands } else if (State == LazyValueInfo::True) { 2656f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands // This case always fires. Arrange for the switch to be turned into an 2666f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands // unconditional branch by replacing the switch condition with the case 2676f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands // value. 2686f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands SI->setCondition(Case); 269a8eb6bb408e84ceb468ceb409f4c87308e67b9ebDuncan Sands NumDeadCases += SI->getNumCases(); 2706f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands Changed = true; 2716f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands break; 2726f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands } 2736f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands } 2746f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands 2756f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands if (Changed) 2766f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands // If the switch has been simplified to the point where it can be replaced 2776f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands // by a branch then do so now. 2786f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands ConstantFoldTerminator(BB); 2796f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands 2806f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands return Changed; 2816f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands} 2826f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands 28325e9405272630204eb721d8b6ab47a5a25f24885Owen Andersonbool CorrelatedValuePropagation::runOnFunction(Function &F) { 284a0b59f6bd23afaeba923b94f46838cffd5218a12Owen Anderson LVI = &getAnalysis<LazyValueInfo>(); 28593f83deba1df95211898fe756758e81969955bd9Owen Anderson 286869a144f4e53db38789e630fbd9cc57384685ce6Owen Anderson bool FnChanged = false; 28793f83deba1df95211898fe756758e81969955bd9Owen Anderson 2880995f20cfd97110cb842407b5757f217841b0defOwen Anderson for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) { 289869a144f4e53db38789e630fbd9cc57384685ce6Owen Anderson bool BBChanged = false; 290a0b59f6bd23afaeba923b94f46838cffd5218a12Owen Anderson for (BasicBlock::iterator BI = FI->begin(), BE = FI->end(); BI != BE; ) { 291a0b59f6bd23afaeba923b94f46838cffd5218a12Owen Anderson Instruction *II = BI++; 2921593dd6779d7ab1db13c44f32f987c32aff2b54bOwen Anderson switch (II->getOpcode()) { 2931593dd6779d7ab1db13c44f32f987c32aff2b54bOwen Anderson case Instruction::Select: 2941593dd6779d7ab1db13c44f32f987c32aff2b54bOwen Anderson BBChanged |= processSelect(cast<SelectInst>(II)); 2951593dd6779d7ab1db13c44f32f987c32aff2b54bOwen Anderson break; 2961593dd6779d7ab1db13c44f32f987c32aff2b54bOwen Anderson case Instruction::PHI: 2971593dd6779d7ab1db13c44f32f987c32aff2b54bOwen Anderson BBChanged |= processPHI(cast<PHINode>(II)); 2981593dd6779d7ab1db13c44f32f987c32aff2b54bOwen Anderson break; 299597dad35b8b86c076dbbb0d095319c79de7806caOwen Anderson case Instruction::ICmp: 300597dad35b8b86c076dbbb0d095319c79de7806caOwen Anderson case Instruction::FCmp: 301597dad35b8b86c076dbbb0d095319c79de7806caOwen Anderson BBChanged |= processCmp(cast<CmpInst>(II)); 302597dad35b8b86c076dbbb0d095319c79de7806caOwen Anderson break; 3031593dd6779d7ab1db13c44f32f987c32aff2b54bOwen Anderson case Instruction::Load: 3041593dd6779d7ab1db13c44f32f987c32aff2b54bOwen Anderson case Instruction::Store: 3051593dd6779d7ab1db13c44f32f987c32aff2b54bOwen Anderson BBChanged |= processMemAccess(II); 3061593dd6779d7ab1db13c44f32f987c32aff2b54bOwen Anderson break; 3071593dd6779d7ab1db13c44f32f987c32aff2b54bOwen Anderson } 308a0b59f6bd23afaeba923b94f46838cffd5218a12Owen Anderson } 30993f83deba1df95211898fe756758e81969955bd9Owen Anderson 3106f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands Instruction *Term = FI->getTerminator(); 3116f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands switch (Term->getOpcode()) { 3126f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands case Instruction::Switch: 3136f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands BBChanged |= processSwitch(cast<SwitchInst>(Term)); 3146f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands break; 3156f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands } 3166f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands 317869a144f4e53db38789e630fbd9cc57384685ce6Owen Anderson FnChanged |= BBChanged; 3187c37f6d2d9d7fe0327e1de5e0dcda729a73d2a6fOwen Anderson } 31993f83deba1df95211898fe756758e81969955bd9Owen Anderson 320869a144f4e53db38789e630fbd9cc57384685ce6Owen Anderson return FnChanged; 3216cfabc7974c74f5a071f9f0621379902614d5179Benjamin Kramer} 322