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 14de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar#include "llvm/Transforms/Scalar/CorrelatedValuePropagation.h" 15a0b59f6bd23afaeba923b94f46838cffd5218a12Owen Anderson#include "llvm/Transforms/Scalar.h" 16d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/Statistic.h" 17f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar#include "llvm/Analysis/GlobalsModRef.h" 18d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Analysis/InstructionSimplify.h" 19d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Analysis/LazyValueInfo.h" 2036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/CFG.h" 210b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Constants.h" 220b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Function.h" 230b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Instructions.h" 244c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar#include "llvm/IR/Module.h" 25a0b59f6bd23afaeba923b94f46838cffd5218a12Owen Anderson#include "llvm/Pass.h" 26e8aa36a4afa02dde89e10f39b6ca87cfe1949dd8Benjamin Kramer#include "llvm/Support/Debug.h" 27e8aa36a4afa02dde89e10f39b6ca87cfe1949dd8Benjamin Kramer#include "llvm/Support/raw_ostream.h" 28a0b59f6bd23afaeba923b94f46838cffd5218a12Owen Anderson#include "llvm/Transforms/Utils/Local.h" 29a0b59f6bd23afaeba923b94f46838cffd5218a12Owen Andersonusing namespace llvm; 30a0b59f6bd23afaeba923b94f46838cffd5218a12Owen Anderson 31dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#define DEBUG_TYPE "correlated-value-propagation" 32dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 331593dd6779d7ab1db13c44f32f987c32aff2b54bOwen AndersonSTATISTIC(NumPhis, "Number of phis propagated"); 341593dd6779d7ab1db13c44f32f987c32aff2b54bOwen AndersonSTATISTIC(NumSelects, "Number of selects propagated"); 351593dd6779d7ab1db13c44f32f987c32aff2b54bOwen AndersonSTATISTIC(NumMemAccess, "Number of memory access targets propagated"); 36597dad35b8b86c076dbbb0d095319c79de7806caOwen AndersonSTATISTIC(NumCmps, "Number of comparisons propagated"); 37f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga NainarSTATISTIC(NumReturns, "Number of return values propagated"); 38a8eb6bb408e84ceb468ceb409f4c87308e67b9ebDuncan SandsSTATISTIC(NumDeadCases, "Number of switch cases removed"); 39de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga NainarSTATISTIC(NumSDivs, "Number of sdiv converted to udiv"); 40de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga NainarSTATISTIC(NumSRems, "Number of srem converted to urem"); 41f523b3e0878ea47e72b7d880b8fd18a33636fbdeOwen Anderson 42a0b59f6bd23afaeba923b94f46838cffd5218a12Owen Andersonnamespace { 4325e9405272630204eb721d8b6ab47a5a25f24885Owen Anderson class CorrelatedValuePropagation : public FunctionPass { 44a0b59f6bd23afaeba923b94f46838cffd5218a12Owen Anderson public: 45a0b59f6bd23afaeba923b94f46838cffd5218a12Owen Anderson static char ID; 46081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson CorrelatedValuePropagation(): FunctionPass(ID) { 47081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeCorrelatedValuePropagationPass(*PassRegistry::getPassRegistry()); 48081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson } 4993f83deba1df95211898fe756758e81969955bd9Owen Anderson 5036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool runOnFunction(Function &F) override; 5193f83deba1df95211898fe756758e81969955bd9Owen Anderson 5236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void getAnalysisUsage(AnalysisUsage &AU) const override { 53de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar AU.addRequired<LazyValueInfoWrapperPass>(); 54f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar AU.addPreserved<GlobalsAAWrapperPass>(); 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) 62de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga NainarINITIALIZE_PASS_DEPENDENCY(LazyValueInfoWrapperPass) 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 71de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarstatic bool processSelect(SelectInst *S, LazyValueInfo *LVI) { 72a081d15b842e87c670260006eb17b5c1a826b5eeOwen Anderson if (S->getType()->isVectorTy()) return false; 731593dd6779d7ab1db13c44f32f987c32aff2b54bOwen Anderson if (isa<Constant>(S->getOperand(0))) return false; 7493f83deba1df95211898fe756758e81969955bd9Owen Anderson 7537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines Constant *C = LVI->getConstant(S->getOperand(0), S->getParent(), S); 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 94de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarstatic bool processPHI(PHINode *P, LazyValueInfo *LVI) { 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 10237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines Value *V = LVI->getConstantOnEdge(Incoming, P->getIncomingBlock(i), BB, P); 10393f83deba1df95211898fe756758e81969955bd9Owen Anderson 1046948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // Look if the incoming value is a select with a scalar condition for which 1056948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // LVI can tells us the value. In that case replace the incoming value with 1066948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // the appropriate value of the select. This often allows us to remove the 1076948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // select later. 108e8aa36a4afa02dde89e10f39b6ca87cfe1949dd8Benjamin Kramer if (!V) { 109e8aa36a4afa02dde89e10f39b6ca87cfe1949dd8Benjamin Kramer SelectInst *SI = dyn_cast<SelectInst>(Incoming); 110e8aa36a4afa02dde89e10f39b6ca87cfe1949dd8Benjamin Kramer if (!SI) continue; 111e8aa36a4afa02dde89e10f39b6ca87cfe1949dd8Benjamin Kramer 1126948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar Value *Condition = SI->getCondition(); 1136948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (!Condition->getType()->isVectorTy()) { 1146948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (Constant *C = LVI->getConstantOnEdge( 1156948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar Condition, P->getIncomingBlock(i), BB, P)) { 1166948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (C->isOneValue()) { 1176948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar V = SI->getTrueValue(); 1186948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar } else if (C->isZeroValue()) { 1196948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar V = SI->getFalseValue(); 1206948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar } 1216948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // Once LVI learns to handle vector types, we could also add support 1226948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // for vector type constants that are not all zeroes or all ones. 1236948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar } 1246948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar } 1256948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar 1266948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // Look if the select has a constant but LVI tells us that the incoming 1276948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // value can never be that constant. In that case replace the incoming 1286948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // value with the other value of the select. This often allows us to 1296948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar // remove the select later. 1306948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (!V) { 1316948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar Constant *C = dyn_cast<Constant>(SI->getFalseValue()); 1326948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (!C) continue; 1336948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar 1346948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (LVI->getPredicateOnEdge(ICmpInst::ICMP_EQ, SI, C, 1356948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar P->getIncomingBlock(i), BB, P) != 1366948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar LazyValueInfo::False) 1376948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar continue; 1386948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar V = SI->getTrueValue(); 1396948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar } 140e8aa36a4afa02dde89e10f39b6ca87cfe1949dd8Benjamin Kramer 141e8aa36a4afa02dde89e10f39b6ca87cfe1949dd8Benjamin Kramer DEBUG(dbgs() << "CVP: Threading PHI over " << *SI << '\n'); 142e8aa36a4afa02dde89e10f39b6ca87cfe1949dd8Benjamin Kramer } 143e8aa36a4afa02dde89e10f39b6ca87cfe1949dd8Benjamin Kramer 144e8aa36a4afa02dde89e10f39b6ca87cfe1949dd8Benjamin Kramer P->setIncomingValue(i, V); 145a081d15b842e87c670260006eb17b5c1a826b5eeOwen Anderson Changed = true; 146a0b59f6bd23afaeba923b94f46838cffd5218a12Owen Anderson } 147cdbd99262286e96729007ac535cd430ecb3d38acDuncan Sands 1484c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // FIXME: Provide TLI, DT, AT to SimplifyInstruction. 1494c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar const DataLayout &DL = BB->getModule()->getDataLayout(); 1504c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar if (Value *V = SimplifyInstruction(P, DL)) { 151cdbd99262286e96729007ac535cd430ecb3d38acDuncan Sands P->replaceAllUsesWith(V); 152a0b59f6bd23afaeba923b94f46838cffd5218a12Owen Anderson P->eraseFromParent(); 153a081d15b842e87c670260006eb17b5c1a826b5eeOwen Anderson Changed = true; 154a0b59f6bd23afaeba923b94f46838cffd5218a12Owen Anderson } 155cdbd99262286e96729007ac535cd430ecb3d38acDuncan Sands 156a8eb6bb408e84ceb468ceb409f4c87308e67b9ebDuncan Sands if (Changed) 157a8eb6bb408e84ceb468ceb409f4c87308e67b9ebDuncan Sands ++NumPhis; 15893f83deba1df95211898fe756758e81969955bd9Owen Anderson 159a081d15b842e87c670260006eb17b5c1a826b5eeOwen Anderson return Changed; 160a0b59f6bd23afaeba923b94f46838cffd5218a12Owen Anderson} 161a0b59f6bd23afaeba923b94f46838cffd5218a12Owen Anderson 162de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarstatic bool processMemAccess(Instruction *I, LazyValueInfo *LVI) { 163dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Value *Pointer = nullptr; 1641593dd6779d7ab1db13c44f32f987c32aff2b54bOwen Anderson if (LoadInst *L = dyn_cast<LoadInst>(I)) 1651593dd6779d7ab1db13c44f32f987c32aff2b54bOwen Anderson Pointer = L->getPointerOperand(); 1661593dd6779d7ab1db13c44f32f987c32aff2b54bOwen Anderson else 1671593dd6779d7ab1db13c44f32f987c32aff2b54bOwen Anderson Pointer = cast<StoreInst>(I)->getPointerOperand(); 16893f83deba1df95211898fe756758e81969955bd9Owen Anderson 1691593dd6779d7ab1db13c44f32f987c32aff2b54bOwen Anderson if (isa<Constant>(Pointer)) return false; 17093f83deba1df95211898fe756758e81969955bd9Owen Anderson 17137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines Constant *C = LVI->getConstant(Pointer, I->getParent(), I); 1721593dd6779d7ab1db13c44f32f987c32aff2b54bOwen Anderson if (!C) return false; 17393f83deba1df95211898fe756758e81969955bd9Owen Anderson 1741593dd6779d7ab1db13c44f32f987c32aff2b54bOwen Anderson ++NumMemAccess; 1751593dd6779d7ab1db13c44f32f987c32aff2b54bOwen Anderson I->replaceUsesOfWith(Pointer, C); 1761593dd6779d7ab1db13c44f32f987c32aff2b54bOwen Anderson return true; 1771593dd6779d7ab1db13c44f32f987c32aff2b54bOwen Anderson} 1781593dd6779d7ab1db13c44f32f987c32aff2b54bOwen Anderson 179de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// See if LazyValueInfo's ability to exploit edge conditions or range 180de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// information is sufficient to prove this comparison. Even for local 181de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// conditions, this can sometimes prove conditions instcombine can't by 182f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar/// exploiting range information. 183de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarstatic bool processCmp(CmpInst *C, LazyValueInfo *LVI) { 184597dad35b8b86c076dbbb0d095319c79de7806caOwen Anderson Value *Op0 = C->getOperand(0); 185597dad35b8b86c076dbbb0d095319c79de7806caOwen Anderson Constant *Op1 = dyn_cast<Constant>(C->getOperand(1)); 186597dad35b8b86c076dbbb0d095319c79de7806caOwen Anderson if (!Op1) return false; 18793f83deba1df95211898fe756758e81969955bd9Owen Anderson 188f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // As a policy choice, we choose not to waste compile time on anything where 189f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // the comparison is testing local values. While LVI can sometimes reason 190f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // about such cases, it's not its primary purpose. We do make sure to do 191f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // the block local query for uses from terminator instructions, but that's 192f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // handled in the code for each terminator. 193f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar auto *I = dyn_cast<Instruction>(Op0); 194f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (I && I->getParent() == C->getParent()) 195f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return false; 19693f83deba1df95211898fe756758e81969955bd9Owen Anderson 197f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar LazyValueInfo::Tristate Result = 198f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar LVI->getPredicateAt(C->getPredicate(), Op0, Op1, C); 199597dad35b8b86c076dbbb0d095319c79de7806caOwen Anderson if (Result == LazyValueInfo::Unknown) return false; 200597dad35b8b86c076dbbb0d095319c79de7806caOwen Anderson 201597dad35b8b86c076dbbb0d095319c79de7806caOwen Anderson ++NumCmps; 202597dad35b8b86c076dbbb0d095319c79de7806caOwen Anderson if (Result == LazyValueInfo::True) 203597dad35b8b86c076dbbb0d095319c79de7806caOwen Anderson C->replaceAllUsesWith(ConstantInt::getTrue(C->getContext())); 204597dad35b8b86c076dbbb0d095319c79de7806caOwen Anderson else 205597dad35b8b86c076dbbb0d095319c79de7806caOwen Anderson C->replaceAllUsesWith(ConstantInt::getFalse(C->getContext())); 206597dad35b8b86c076dbbb0d095319c79de7806caOwen Anderson C->eraseFromParent(); 207597dad35b8b86c076dbbb0d095319c79de7806caOwen Anderson 208597dad35b8b86c076dbbb0d095319c79de7806caOwen Anderson return true; 209597dad35b8b86c076dbbb0d095319c79de7806caOwen Anderson} 210597dad35b8b86c076dbbb0d095319c79de7806caOwen Anderson 211de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// Simplify a switch instruction by removing cases which can never fire. If the 212de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// uselessness of a case could be determined locally then constant propagation 213de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// would already have figured it out. Instead, walk the predecessors and 214de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// statically evaluate cases based on information available on that edge. Cases 215de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// that cannot fire no matter what the incoming edge can safely be removed. If 216de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// a case fires on every incoming edge then the entire switch can be removed 217de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// and replaced with a branch to the case destination. 218de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarstatic bool processSwitch(SwitchInst *SI, LazyValueInfo *LVI) { 2196f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands Value *Cond = SI->getCondition(); 2206f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands BasicBlock *BB = SI->getParent(); 2216f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands 2226f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands // If the condition was defined in same block as the switch then LazyValueInfo 2236f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands // currently won't say anything useful about it, though in theory it could. 2246f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands if (isa<Instruction>(Cond) && cast<Instruction>(Cond)->getParent() == BB) 2256f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands return false; 2266f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands 2276f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands // If the switch is unreachable then trying to improve it is a waste of time. 2286f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands pred_iterator PB = pred_begin(BB), PE = pred_end(BB); 2296f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands if (PB == PE) return false; 2306f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands 2316f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands // Analyse each switch case in turn. This is done in reverse order so that 2326f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands // removing a case doesn't cause trouble for the iteration. 2336f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands bool Changed = false; 2343d3abe0852d5f499bed7ab014519dd582a0a795dStepan Dyatkovskiy for (SwitchInst::CaseIt CI = SI->case_end(), CE = SI->case_begin(); CI-- != CE; 2356f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands ) { 2366f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands ConstantInt *Case = CI.getCaseValue(); 2376f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands 2386f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands // Check to see if the switch condition is equal to/not equal to the case 2396f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands // value on every incoming edge, equal/not equal being the same each time. 2406f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands LazyValueInfo::Tristate State = LazyValueInfo::Unknown; 2416f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands for (pred_iterator PI = PB; PI != PE; ++PI) { 2426f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands // Is the switch condition equal to the case value? 2436f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands LazyValueInfo::Tristate Value = LVI->getPredicateOnEdge(CmpInst::ICMP_EQ, 24437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines Cond, Case, *PI, 24537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines BB, SI); 2466f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands // Give up on this case if nothing is known. 2476f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands if (Value == LazyValueInfo::Unknown) { 2486f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands State = LazyValueInfo::Unknown; 2496f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands break; 2506f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands } 2516f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands 2526f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands // If this was the first edge to be visited, record that all other edges 2536f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands // need to give the same result. 2546f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands if (PI == PB) { 2556f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands State = Value; 2566f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands continue; 2576f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands } 2586f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands 2596f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands // If this case is known to fire for some edges and known not to fire for 2606f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands // others then there is nothing we can do - give up. 2616f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands if (Value != State) { 2626f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands State = LazyValueInfo::Unknown; 2636f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands break; 2646f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands } 2656f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands } 2666f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands 2676f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands if (State == LazyValueInfo::False) { 2686f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands // This case never fires - remove it. 2696f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands CI.getCaseSuccessor()->removePredecessor(BB); 2706f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands SI->removeCase(CI); // Does not invalidate the iterator. 2718be16fe70395c30762081388b8f6df323ddc82ebBenjamin Kramer 2728be16fe70395c30762081388b8f6df323ddc82ebBenjamin Kramer // The condition can be modified by removePredecessor's PHI simplification 2738be16fe70395c30762081388b8f6df323ddc82ebBenjamin Kramer // logic. 2748be16fe70395c30762081388b8f6df323ddc82ebBenjamin Kramer Cond = SI->getCondition(); 2758be16fe70395c30762081388b8f6df323ddc82ebBenjamin Kramer 276a8eb6bb408e84ceb468ceb409f4c87308e67b9ebDuncan Sands ++NumDeadCases; 2776f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands Changed = true; 2786f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands } else if (State == LazyValueInfo::True) { 2796f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands // This case always fires. Arrange for the switch to be turned into an 2806f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands // unconditional branch by replacing the switch condition with the case 2816f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands // value. 2826f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands SI->setCondition(Case); 283a8eb6bb408e84ceb468ceb409f4c87308e67b9ebDuncan Sands NumDeadCases += SI->getNumCases(); 2846f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands Changed = true; 2856f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands break; 2866f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands } 2876f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands } 2886f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands 2896f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands if (Changed) 2906f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands // If the switch has been simplified to the point where it can be replaced 2916f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands // by a branch then do so now. 2926f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands ConstantFoldTerminator(BB); 2936f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands 2946f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands return Changed; 2956f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands} 2966f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands 297de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// Infer nonnull attributes for the arguments at the specified callsite. 298de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarstatic bool processCallSite(CallSite CS, LazyValueInfo *LVI) { 299f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar SmallVector<unsigned, 4> Indices; 300f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar unsigned ArgNo = 0; 301f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 302f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar for (Value *V : CS.args()) { 303f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar PointerType *Type = dyn_cast<PointerType>(V->getType()); 304de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Try to mark pointer typed parameters as non-null. We skip the 305de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // relatively expensive analysis for constants which are obviously either 306de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // null or non-null to start with. 307f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (Type && !CS.paramHasAttr(ArgNo + 1, Attribute::NonNull) && 308de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar !isa<Constant>(V) && 309f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar LVI->getPredicateAt(ICmpInst::ICMP_EQ, V, 310f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar ConstantPointerNull::get(Type), 311f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar CS.getInstruction()) == LazyValueInfo::False) 312f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar Indices.push_back(ArgNo + 1); 313f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar ArgNo++; 314f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 315f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 316f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar assert(ArgNo == CS.arg_size() && "sanity check"); 317f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 318f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (Indices.empty()) 319f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return false; 320f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 321f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar AttributeSet AS = CS.getAttributes(); 322f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar LLVMContext &Ctx = CS.getInstruction()->getContext(); 323f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar AS = AS.addAttribute(Ctx, Indices, Attribute::get(Ctx, Attribute::NonNull)); 324f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar CS.setAttributes(AS); 325f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 326f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return true; 327f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar} 328f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 329de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// Helper function to rewrite srem and sdiv. As a policy choice, we choose not 330de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// to waste compile time on anything where the operands are local defs. While 331de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// LVI can sometimes reason about such cases, it's not its primary purpose. 332de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarstatic bool hasLocalDefs(BinaryOperator *SDI) { 333de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (Value *O : SDI->operands()) { 334de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar auto *I = dyn_cast<Instruction>(O); 335de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (I && I->getParent() == SDI->getParent()) 336de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return true; 337de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 338de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return false; 339de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar} 340de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 341de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarstatic bool hasPositiveOperands(BinaryOperator *SDI, LazyValueInfo *LVI) { 342de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Constant *Zero = ConstantInt::get(SDI->getType(), 0); 343de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (Value *O : SDI->operands()) { 344de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar auto Result = LVI->getPredicateAt(ICmpInst::ICMP_SGE, O, Zero, SDI); 345de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (Result != LazyValueInfo::True) 346de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return false; 347de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 348de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return true; 349de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar} 350de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 351de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarstatic bool processSRem(BinaryOperator *SDI, LazyValueInfo *LVI) { 352de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (SDI->getType()->isVectorTy() || hasLocalDefs(SDI) || 353de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar !hasPositiveOperands(SDI, LVI)) 354de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return false; 355de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 356de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar ++NumSRems; 357de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar auto *BO = BinaryOperator::CreateURem(SDI->getOperand(0), SDI->getOperand(1), 358de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar SDI->getName(), SDI); 359de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar SDI->replaceAllUsesWith(BO); 360de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar SDI->eraseFromParent(); 361de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return true; 362de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar} 363de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 364de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// See if LazyValueInfo's ability to exploit edge conditions or range 365de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// information is sufficient to prove the both operands of this SDiv are 366de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// positive. If this is the case, replace the SDiv with a UDiv. Even for local 367de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// conditions, this can sometimes prove conditions instcombine can't by 368de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// exploiting range information. 369de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarstatic bool processSDiv(BinaryOperator *SDI, LazyValueInfo *LVI) { 370de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (SDI->getType()->isVectorTy() || hasLocalDefs(SDI) || 371de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar !hasPositiveOperands(SDI, LVI)) 372de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return false; 373de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 374de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar ++NumSDivs; 375de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar auto *BO = BinaryOperator::CreateUDiv(SDI->getOperand(0), SDI->getOperand(1), 376de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar SDI->getName(), SDI); 377de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar BO->setIsExact(SDI->isExact()); 378de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar SDI->replaceAllUsesWith(BO); 379de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar SDI->eraseFromParent(); 380de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 381de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return true; 382de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar} 383de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 384de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarstatic Constant *getConstantAt(Value *V, Instruction *At, LazyValueInfo *LVI) { 385f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (Constant *C = LVI->getConstant(V, At->getParent(), At)) 386f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return C; 387f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 388f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // TODO: The following really should be sunk inside LVI's core algorithm, or 389f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // at least the outer shims around such. 390f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar auto *C = dyn_cast<CmpInst>(V); 391f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (!C) return nullptr; 392f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 393f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar Value *Op0 = C->getOperand(0); 394f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar Constant *Op1 = dyn_cast<Constant>(C->getOperand(1)); 395f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (!Op1) return nullptr; 396f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 397f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar LazyValueInfo::Tristate Result = 398f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar LVI->getPredicateAt(C->getPredicate(), Op0, Op1, At); 399f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (Result == LazyValueInfo::Unknown) 400f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return nullptr; 401f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 402f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return (Result == LazyValueInfo::True) ? 403f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar ConstantInt::getTrue(C->getContext()) : 404f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar ConstantInt::getFalse(C->getContext()); 405f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar} 406f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 407de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarstatic bool runImpl(Function &F, LazyValueInfo *LVI) { 408869a144f4e53db38789e630fbd9cc57384685ce6Owen Anderson bool FnChanged = false; 40993f83deba1df95211898fe756758e81969955bd9Owen Anderson 410de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (BasicBlock &BB : F) { 411869a144f4e53db38789e630fbd9cc57384685ce6Owen Anderson bool BBChanged = false; 412de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (BasicBlock::iterator BI = BB.begin(), BE = BB.end(); BI != BE;) { 413f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar Instruction *II = &*BI++; 4141593dd6779d7ab1db13c44f32f987c32aff2b54bOwen Anderson switch (II->getOpcode()) { 4151593dd6779d7ab1db13c44f32f987c32aff2b54bOwen Anderson case Instruction::Select: 416de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar BBChanged |= processSelect(cast<SelectInst>(II), LVI); 4171593dd6779d7ab1db13c44f32f987c32aff2b54bOwen Anderson break; 4181593dd6779d7ab1db13c44f32f987c32aff2b54bOwen Anderson case Instruction::PHI: 419de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar BBChanged |= processPHI(cast<PHINode>(II), LVI); 4201593dd6779d7ab1db13c44f32f987c32aff2b54bOwen Anderson break; 421597dad35b8b86c076dbbb0d095319c79de7806caOwen Anderson case Instruction::ICmp: 422597dad35b8b86c076dbbb0d095319c79de7806caOwen Anderson case Instruction::FCmp: 423de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar BBChanged |= processCmp(cast<CmpInst>(II), LVI); 424597dad35b8b86c076dbbb0d095319c79de7806caOwen Anderson break; 4251593dd6779d7ab1db13c44f32f987c32aff2b54bOwen Anderson case Instruction::Load: 4261593dd6779d7ab1db13c44f32f987c32aff2b54bOwen Anderson case Instruction::Store: 427de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar BBChanged |= processMemAccess(II, LVI); 4281593dd6779d7ab1db13c44f32f987c32aff2b54bOwen Anderson break; 429f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar case Instruction::Call: 430f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar case Instruction::Invoke: 431de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar BBChanged |= processCallSite(CallSite(II), LVI); 432de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar break; 433de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar case Instruction::SRem: 434de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar BBChanged |= processSRem(cast<BinaryOperator>(II), LVI); 435de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar break; 436de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar case Instruction::SDiv: 437de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar BBChanged |= processSDiv(cast<BinaryOperator>(II), LVI); 438f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar break; 4391593dd6779d7ab1db13c44f32f987c32aff2b54bOwen Anderson } 440a0b59f6bd23afaeba923b94f46838cffd5218a12Owen Anderson } 44193f83deba1df95211898fe756758e81969955bd9Owen Anderson 442de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Instruction *Term = BB.getTerminator(); 4436f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands switch (Term->getOpcode()) { 4446f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands case Instruction::Switch: 445de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar BBChanged |= processSwitch(cast<SwitchInst>(Term), LVI); 4466f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands break; 447f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar case Instruction::Ret: { 448f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar auto *RI = cast<ReturnInst>(Term); 449f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Try to determine the return value if we can. This is mainly here to 450f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // simplify the writing of unit tests, but also helps to enable IPO by 451f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // constant folding the return values of callees. 452f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar auto *RetVal = RI->getReturnValue(); 453f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (!RetVal) break; // handle "ret void" 454f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (isa<Constant>(RetVal)) break; // nothing to do 455de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (auto *C = getConstantAt(RetVal, RI, LVI)) { 456f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar ++NumReturns; 457f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar RI->replaceUsesOfWith(RetVal, C); 458f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar BBChanged = true; 459f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 4606f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands } 461f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar }; 4626f1d7994155c535455b7543e2af6dce5b65de37bDuncan Sands 463869a144f4e53db38789e630fbd9cc57384685ce6Owen Anderson FnChanged |= BBChanged; 4647c37f6d2d9d7fe0327e1de5e0dcda729a73d2a6fOwen Anderson } 46593f83deba1df95211898fe756758e81969955bd9Owen Anderson 466869a144f4e53db38789e630fbd9cc57384685ce6Owen Anderson return FnChanged; 4676cfabc7974c74f5a071f9f0621379902614d5179Benjamin Kramer} 468de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 469de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarbool CorrelatedValuePropagation::runOnFunction(Function &F) { 470de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (skipFunction(F)) 471de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return false; 472de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 473de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar LazyValueInfo *LVI = &getAnalysis<LazyValueInfoWrapperPass>().getLVI(); 474de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return runImpl(F, LVI); 475de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar} 476de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 477de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga NainarPreservedAnalyses 478de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga NainarCorrelatedValuePropagationPass::run(Function &F, FunctionAnalysisManager &AM) { 479de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 480de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar LazyValueInfo *LVI = &AM.getResult<LazyValueAnalysis>(F); 481de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar bool Changed = runImpl(F, LVI); 482de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 483de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // FIXME: We need to invalidate LVI to avoid PR28400. Is there a better 484de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // solution? 485de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar AM.invalidate<LazyValueAnalysis>(F); 486de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 487de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (!Changed) 488de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return PreservedAnalyses::all(); 489de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar PreservedAnalyses PA; 490de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar PA.preserve<GlobalsAA>(); 491de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return PA; 492de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar} 493