IndVarSimplify.cpp revision 11745d4c0276ccb5c64f83d6954b54c8ff2aec98
16148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner//===- IndVarSimplify.cpp - Induction Variable Elimination ----------------===// 2fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 3b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// The LLVM Compiler Infrastructure 4b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 54ee451de366474b9c228b4e5fa573795a715216dChris Lattner// This file is distributed under the University of Illinois Open Source 64ee451de366474b9c228b4e5fa573795a715216dChris Lattner// License. See LICENSE.TXT for details. 7fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 8b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell//===----------------------------------------------------------------------===// 96148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner// 1040bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner// This transformation analyzes and transforms the induction variables (and 1140bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner// computations derived from them) into simpler forms suitable for subsequent 1240bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner// analysis and transformation. 1340bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner// 1447a53ac726ceb1ac11bc1326be3fbe095f726b0dReid Spencer// This transformation makes the following changes to each loop with an 1540bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner// identifiable induction variable: 1640bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner// 1. All loops are transformed to have a SINGLE canonical induction variable 1740bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner// which starts at zero and steps by one. 1840bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner// 2. The canonical induction variable is guaranteed to be the first PHI node 1940bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner// in the loop header block. 20ea73f3c2e14d84bb4cb07bd6a1a3d7915f3aff83Dan Gohman// 3. The canonical induction variable is guaranteed to be in a wide enough 21ea73f3c2e14d84bb4cb07bd6a1a3d7915f3aff83Dan Gohman// type so that IV expressions need not be (directly) zero-extended or 22ea73f3c2e14d84bb4cb07bd6a1a3d7915f3aff83Dan Gohman// sign-extended. 23ea73f3c2e14d84bb4cb07bd6a1a3d7915f3aff83Dan Gohman// 4. Any pointer arithmetic recurrences are raised to use array subscripts. 2440bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner// 2540bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner// If the trip count of a loop is computable, this pass also makes the following 2640bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner// changes: 2740bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner// 1. The exit condition for the loop is canonicalized to compare the 2840bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner// induction value against the exit value. This turns loops like: 2940bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner// 'for (i = 7; i*i < 1000; ++i)' into 'for (i = 0; i != 25; ++i)' 3040bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner// 2. Any use outside of the loop of an expression derived from the indvar 3140bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner// is changed to compute the derived value outside of the loop, eliminating 3240bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner// the dependence on the exit value of the induction variable. If the only 3340bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner// purpose of the loop is to compute the exit value of some derived 3440bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner// expression, this transformation will make the loop dead. 3540bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner// 3640bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner// This transformation should be followed by strength reduction after all of the 37c2c4cbf7b3a0229cf1804ca9d7c18113f75bab46Dan Gohman// desired loop transformations have been performed. 386148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner// 396148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner//===----------------------------------------------------------------------===// 406148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner 410e5f499638c8d277b9dc4a4385712177c53b5681Chris Lattner#define DEBUG_TYPE "indvars" 42022103b3f33febb7e54b8fdf2c9bc461eea78cbaChris Lattner#include "llvm/Transforms/Scalar.h" 4340bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner#include "llvm/BasicBlock.h" 4459fdaeeae8f183e18bb6ad5c382ca23e28e6aaf6Chris Lattner#include "llvm/Constants.h" 4518b3c97bc773b24a66eb779e85da1820b0f16b31Chris Lattner#include "llvm/Instructions.h" 467b9f6b1b21bc0b06f3c72beae51e9db631319503Devang Patel#include "llvm/IntrinsicInst.h" 47d672ecb0178c6247a5eaa5b0fb0c3b23cd25bd7cOwen Anderson#include "llvm/LLVMContext.h" 4840bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner#include "llvm/Type.h" 4981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman#include "llvm/Analysis/Dominators.h" 5081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman#include "llvm/Analysis/IVUsers.h" 5136f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman#include "llvm/Analysis/ScalarEvolutionExpander.h" 5247df12d80db90e125e9f2ff764286ee11665476dJohn Criswell#include "llvm/Analysis/LoopInfo.h" 535ee99979065d75605d150d7e567e4351024aae8fDevang Patel#include "llvm/Analysis/LoopPass.h" 54455889aa79e3463a4b0f2161e3d9d72a683268b6Chris Lattner#include "llvm/Support/CFG.h" 5556caa098085977c14cfab39d92c7dfa15dde0d90Andrew Trick#include "llvm/Support/CommandLine.h" 56ee4f13a9046c380725cdeab62d57722db375c473Chris Lattner#include "llvm/Support/Debug.h" 57bdff548e4dd577a72094d57b282de4e765643b96Chris Lattner#include "llvm/Support/raw_ostream.h" 5847df12d80db90e125e9f2ff764286ee11665476dJohn Criswell#include "llvm/Transforms/Utils/Local.h" 5981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman#include "llvm/Transforms/Utils/BasicBlockUtils.h" 6037da40875873d70b83dc08b2803052bec9b68886Andrew Trick#include "llvm/Target/TargetData.h" 61a54b7cbd452b3adb2f51346140d996b29c2cdb30Reid Spencer#include "llvm/ADT/SmallVector.h" 62551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/Statistic.h" 6381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman#include "llvm/ADT/STLExtras.h" 6447df12d80db90e125e9f2ff764286ee11665476dJohn Criswellusing namespace llvm; 65d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 662fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew TrickSTATISTIC(NumRemoved , "Number of aux indvars removed"); 672fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew TrickSTATISTIC(NumWidened , "Number of indvars widened"); 682fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew TrickSTATISTIC(NumInserted , "Number of canonical indvars added"); 692fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew TrickSTATISTIC(NumReplaced , "Number of exit values replaced"); 702fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew TrickSTATISTIC(NumLFTR , "Number of loop exit tests replaced"); 712fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew TrickSTATISTIC(NumElimIdentity, "Number of IV identities eliminated"); 722fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew TrickSTATISTIC(NumElimExt , "Number of IV sign/zero extends eliminated"); 732fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew TrickSTATISTIC(NumElimRem , "Number of IV remainder operations eliminated"); 742fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew TrickSTATISTIC(NumElimCmp , "Number of IV comparisons eliminated"); 753324e718bc9ac2ede08a14c325848b576849542bChris Lattner 7656caa098085977c14cfab39d92c7dfa15dde0d90Andrew Trickstatic cl::opt<bool> DisableIVRewrite( 7756caa098085977c14cfab39d92c7dfa15dde0d90Andrew Trick "disable-iv-rewrite", cl::Hidden, 7856caa098085977c14cfab39d92c7dfa15dde0d90Andrew Trick cl::desc("Disable canonical induction variable rewriting")); 7937da40875873d70b83dc08b2803052bec9b68886Andrew Trick 800e5f499638c8d277b9dc4a4385712177c53b5681Chris Lattnernamespace { 813e8b6631e67e01e4960a7ba4668a50c596607473Chris Lattner class IndVarSimplify : public LoopPass { 8281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman IVUsers *IU; 8340bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner LoopInfo *LI; 8440bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner ScalarEvolution *SE; 85de53dc03f5c1549f3176e979bbeeac965dfa5cbcDan Gohman DominatorTree *DT; 8637da40875873d70b83dc08b2803052bec9b68886Andrew Trick TargetData *TD; 872fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick 88b12a754cce0c1d5542af605203a47820edba454dAndrew Trick SmallVector<WeakVH, 16> DeadInsts; 8915cad759fe2048ac5eb137c6bb0ab7287538677eChris Lattner bool Changed; 903324e718bc9ac2ede08a14c325848b576849542bChris Lattner public: 91794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel 925668cf77a77493ec9f2a9b33f08125e885c8e4cfDan Gohman static char ID; // Pass identification, replacement for typeid 932fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick IndVarSimplify() : LoopPass(ID), IU(0), LI(0), SE(0), DT(0), TD(0), 9415832f61775040995bb8aa6056176425bc2c9088Andrew Trick Changed(false) { 95081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeIndVarSimplifyPass(*PassRegistry::getPassRegistry()); 96081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson } 97794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel 985668cf77a77493ec9f2a9b33f08125e885c8e4cfDan Gohman virtual bool runOnLoop(Loop *L, LPPassManager &LPM); 9960f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman 1005668cf77a77493ec9f2a9b33f08125e885c8e4cfDan Gohman virtual void getAnalysisUsage(AnalysisUsage &AU) const { 1015668cf77a77493ec9f2a9b33f08125e885c8e4cfDan Gohman AU.addRequired<DominatorTree>(); 1025668cf77a77493ec9f2a9b33f08125e885c8e4cfDan Gohman AU.addRequired<LoopInfo>(); 1035668cf77a77493ec9f2a9b33f08125e885c8e4cfDan Gohman AU.addRequired<ScalarEvolution>(); 1045668cf77a77493ec9f2a9b33f08125e885c8e4cfDan Gohman AU.addRequiredID(LoopSimplifyID); 1055668cf77a77493ec9f2a9b33f08125e885c8e4cfDan Gohman AU.addRequiredID(LCSSAID); 10656caa098085977c14cfab39d92c7dfa15dde0d90Andrew Trick if (!DisableIVRewrite) 10756caa098085977c14cfab39d92c7dfa15dde0d90Andrew Trick AU.addRequired<IVUsers>(); 1085668cf77a77493ec9f2a9b33f08125e885c8e4cfDan Gohman AU.addPreserved<ScalarEvolution>(); 1095668cf77a77493ec9f2a9b33f08125e885c8e4cfDan Gohman AU.addPreservedID(LoopSimplifyID); 1105668cf77a77493ec9f2a9b33f08125e885c8e4cfDan Gohman AU.addPreservedID(LCSSAID); 1112fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick if (!DisableIVRewrite) 1122fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick AU.addPreserved<IVUsers>(); 1135668cf77a77493ec9f2a9b33f08125e885c8e4cfDan Gohman AU.setPreservesCFG(); 1145668cf77a77493ec9f2a9b33f08125e885c8e4cfDan Gohman } 1153324e718bc9ac2ede08a14c325848b576849542bChris Lattner 11640bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner private: 117b12a754cce0c1d5542af605203a47820edba454dAndrew Trick bool isValidRewrite(Value *FromVal, Value *ToVal); 1185ee99979065d75605d150d7e567e4351024aae8fDevang Patel 119f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick void SimplifyIVUsers(SCEVExpander &Rewriter); 1202fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick void SimplifyIVUsersNoRewrite(Loop *L, SCEVExpander &Rewriter); 1212fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick 1222fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick bool EliminateIVUser(Instruction *UseInst, Instruction *IVOperand); 123aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick void EliminateIVComparison(ICmpInst *ICmp, Value *IVOperand); 124aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick void EliminateIVRemainder(BinaryOperator *Rem, 125aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick Value *IVOperand, 1264417e537b65c14b378aeca75b2773582dd102f63Andrew Trick bool IsSigned); 1272fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick bool isSimpleIVUser(Instruction *I, const Loop *L); 12860f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman void RewriteNonIntegerIVs(Loop *L); 12960f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman 1300bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman ICmpInst *LinearFunctionTestReplace(Loop *L, const SCEV *BackedgeTakenCount, 1314dfdf242c1917e98f407818eb5b68ae0b4678f26Andrew Trick PHINode *IndVar, 1324dfdf242c1917e98f407818eb5b68ae0b4678f26Andrew Trick SCEVExpander &Rewriter); 13337da40875873d70b83dc08b2803052bec9b68886Andrew Trick 134454d26dc43207ec537d843229db6f5e6a302e23dDan Gohman void RewriteLoopExitValues(Loop *L, SCEVExpander &Rewriter); 13540bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner 136454d26dc43207ec537d843229db6f5e6a302e23dDan Gohman void RewriteIVExpressions(Loop *L, SCEVExpander &Rewriter); 137d22a849282c45bbf7eb1734c274294d81e49e3a8Devang Patel 138667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman void SinkUnusedInvariants(Loop *L); 13981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 14081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman void HandleFloatingPointIV(Loop *L, PHINode *PH); 1413324e718bc9ac2ede08a14c325848b576849542bChris Lattner }; 1425e76140536ba66fadeced1cd892f79616f407e3cChris Lattner} 143394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner 144844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanchar IndVarSimplify::ID = 0; 1452ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_BEGIN(IndVarSimplify, "indvars", 14637da40875873d70b83dc08b2803052bec9b68886Andrew Trick "Induction Variable Simplification", false, false) 1472ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(DominatorTree) 1482ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(LoopInfo) 1492ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(ScalarEvolution) 1502ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(LoopSimplify) 1512ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(LCSSA) 1522ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(IVUsers) 1532ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_END(IndVarSimplify, "indvars", 15437da40875873d70b83dc08b2803052bec9b68886Andrew Trick "Induction Variable Simplification", false, false) 155844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 156394f0441e06dafca29f0752cf400990a5b8fe4b1Daniel DunbarPass *llvm::createIndVarSimplifyPass() { 1573324e718bc9ac2ede08a14c325848b576849542bChris Lattner return new IndVarSimplify(); 158394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner} 159394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner 160b12a754cce0c1d5542af605203a47820edba454dAndrew Trick/// isValidRewrite - Return true if the SCEV expansion generated by the 161b12a754cce0c1d5542af605203a47820edba454dAndrew Trick/// rewriter can replace the original value. SCEV guarantees that it 162b12a754cce0c1d5542af605203a47820edba454dAndrew Trick/// produces the same value, but the way it is produced may be illegal IR. 163b12a754cce0c1d5542af605203a47820edba454dAndrew Trick/// Ideally, this function will only be called for verification. 164b12a754cce0c1d5542af605203a47820edba454dAndrew Trickbool IndVarSimplify::isValidRewrite(Value *FromVal, Value *ToVal) { 165b12a754cce0c1d5542af605203a47820edba454dAndrew Trick // If an SCEV expression subsumed multiple pointers, its expansion could 166b12a754cce0c1d5542af605203a47820edba454dAndrew Trick // reassociate the GEP changing the base pointer. This is illegal because the 167b12a754cce0c1d5542af605203a47820edba454dAndrew Trick // final address produced by a GEP chain must be inbounds relative to its 168b12a754cce0c1d5542af605203a47820edba454dAndrew Trick // underlying object. Otherwise basic alias analysis, among other things, 169b12a754cce0c1d5542af605203a47820edba454dAndrew Trick // could fail in a dangerous way. Ultimately, SCEV will be improved to avoid 170b12a754cce0c1d5542af605203a47820edba454dAndrew Trick // producing an expression involving multiple pointers. Until then, we must 171b12a754cce0c1d5542af605203a47820edba454dAndrew Trick // bail out here. 172b12a754cce0c1d5542af605203a47820edba454dAndrew Trick // 173b12a754cce0c1d5542af605203a47820edba454dAndrew Trick // Retrieve the pointer operand of the GEP. Don't use GetUnderlyingObject 174b12a754cce0c1d5542af605203a47820edba454dAndrew Trick // because it understands lcssa phis while SCEV does not. 175b12a754cce0c1d5542af605203a47820edba454dAndrew Trick Value *FromPtr = FromVal; 176b12a754cce0c1d5542af605203a47820edba454dAndrew Trick Value *ToPtr = ToVal; 177b12a754cce0c1d5542af605203a47820edba454dAndrew Trick if (GEPOperator *GEP = dyn_cast<GEPOperator>(FromVal)) { 178b12a754cce0c1d5542af605203a47820edba454dAndrew Trick FromPtr = GEP->getPointerOperand(); 179b12a754cce0c1d5542af605203a47820edba454dAndrew Trick } 180b12a754cce0c1d5542af605203a47820edba454dAndrew Trick if (GEPOperator *GEP = dyn_cast<GEPOperator>(ToVal)) { 181b12a754cce0c1d5542af605203a47820edba454dAndrew Trick ToPtr = GEP->getPointerOperand(); 182b12a754cce0c1d5542af605203a47820edba454dAndrew Trick } 183b12a754cce0c1d5542af605203a47820edba454dAndrew Trick if (FromPtr != FromVal || ToPtr != ToVal) { 184b12a754cce0c1d5542af605203a47820edba454dAndrew Trick // Quickly check the common case 185b12a754cce0c1d5542af605203a47820edba454dAndrew Trick if (FromPtr == ToPtr) 186b12a754cce0c1d5542af605203a47820edba454dAndrew Trick return true; 187b12a754cce0c1d5542af605203a47820edba454dAndrew Trick 188b12a754cce0c1d5542af605203a47820edba454dAndrew Trick // SCEV may have rewritten an expression that produces the GEP's pointer 189b12a754cce0c1d5542af605203a47820edba454dAndrew Trick // operand. That's ok as long as the pointer operand has the same base 190b12a754cce0c1d5542af605203a47820edba454dAndrew Trick // pointer. Unlike GetUnderlyingObject(), getPointerBase() will find the 191b12a754cce0c1d5542af605203a47820edba454dAndrew Trick // base of a recurrence. This handles the case in which SCEV expansion 192b12a754cce0c1d5542af605203a47820edba454dAndrew Trick // converts a pointer type recurrence into a nonrecurrent pointer base 193b12a754cce0c1d5542af605203a47820edba454dAndrew Trick // indexed by an integer recurrence. 194b12a754cce0c1d5542af605203a47820edba454dAndrew Trick const SCEV *FromBase = SE->getPointerBase(SE->getSCEV(FromPtr)); 195b12a754cce0c1d5542af605203a47820edba454dAndrew Trick const SCEV *ToBase = SE->getPointerBase(SE->getSCEV(ToPtr)); 196b12a754cce0c1d5542af605203a47820edba454dAndrew Trick if (FromBase == ToBase) 197b12a754cce0c1d5542af605203a47820edba454dAndrew Trick return true; 198b12a754cce0c1d5542af605203a47820edba454dAndrew Trick 199b12a754cce0c1d5542af605203a47820edba454dAndrew Trick DEBUG(dbgs() << "INDVARS: GEP rewrite bail out " 200b12a754cce0c1d5542af605203a47820edba454dAndrew Trick << *FromBase << " != " << *ToBase << "\n"); 201b12a754cce0c1d5542af605203a47820edba454dAndrew Trick 202b12a754cce0c1d5542af605203a47820edba454dAndrew Trick return false; 203b12a754cce0c1d5542af605203a47820edba454dAndrew Trick } 204b12a754cce0c1d5542af605203a47820edba454dAndrew Trick return true; 205b12a754cce0c1d5542af605203a47820edba454dAndrew Trick} 206b12a754cce0c1d5542af605203a47820edba454dAndrew Trick 2074dfdf242c1917e98f407818eb5b68ae0b4678f26Andrew Trick/// canExpandBackedgeTakenCount - Return true if this loop's backedge taken 2084dfdf242c1917e98f407818eb5b68ae0b4678f26Andrew Trick/// count expression can be safely and cheaply expanded into an instruction 2094dfdf242c1917e98f407818eb5b68ae0b4678f26Andrew Trick/// sequence that can be used by LinearFunctionTestReplace. 21003d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trickstatic bool canExpandBackedgeTakenCount(Loop *L, ScalarEvolution *SE) { 21103d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick const SCEV *BackedgeTakenCount = SE->getBackedgeTakenCount(L); 2124dfdf242c1917e98f407818eb5b68ae0b4678f26Andrew Trick if (isa<SCEVCouldNotCompute>(BackedgeTakenCount) || 2134dfdf242c1917e98f407818eb5b68ae0b4678f26Andrew Trick BackedgeTakenCount->isZero()) 2144dfdf242c1917e98f407818eb5b68ae0b4678f26Andrew Trick return false; 2154dfdf242c1917e98f407818eb5b68ae0b4678f26Andrew Trick 2164dfdf242c1917e98f407818eb5b68ae0b4678f26Andrew Trick if (!L->getExitingBlock()) 2174dfdf242c1917e98f407818eb5b68ae0b4678f26Andrew Trick return false; 2184dfdf242c1917e98f407818eb5b68ae0b4678f26Andrew Trick 2194dfdf242c1917e98f407818eb5b68ae0b4678f26Andrew Trick // Can't rewrite non-branch yet. 2204dfdf242c1917e98f407818eb5b68ae0b4678f26Andrew Trick BranchInst *BI = dyn_cast<BranchInst>(L->getExitingBlock()->getTerminator()); 2214dfdf242c1917e98f407818eb5b68ae0b4678f26Andrew Trick if (!BI) 2224dfdf242c1917e98f407818eb5b68ae0b4678f26Andrew Trick return false; 2234dfdf242c1917e98f407818eb5b68ae0b4678f26Andrew Trick 224ca9b7037e28759c200fe5ca98190cabd121a1bbaDan Gohman // Special case: If the backedge-taken count is a UDiv, it's very likely a 225ca9b7037e28759c200fe5ca98190cabd121a1bbaDan Gohman // UDiv that ScalarEvolution produced in order to compute a precise 226ca9b7037e28759c200fe5ca98190cabd121a1bbaDan Gohman // expression, rather than a UDiv from the user's code. If we can't find a 227ca9b7037e28759c200fe5ca98190cabd121a1bbaDan Gohman // UDiv in the code with some simple searching, assume the former and forego 228ca9b7037e28759c200fe5ca98190cabd121a1bbaDan Gohman // rewriting the loop. 229ca9b7037e28759c200fe5ca98190cabd121a1bbaDan Gohman if (isa<SCEVUDivExpr>(BackedgeTakenCount)) { 230ca9b7037e28759c200fe5ca98190cabd121a1bbaDan Gohman ICmpInst *OrigCond = dyn_cast<ICmpInst>(BI->getCondition()); 23137da40875873d70b83dc08b2803052bec9b68886Andrew Trick if (!OrigCond) return false; 232ca9b7037e28759c200fe5ca98190cabd121a1bbaDan Gohman const SCEV *R = SE->getSCEV(OrigCond->getOperand(1)); 233deff621abdd48bd70434bd4d7ef30f08ddba1cd8Dan Gohman R = SE->getMinusSCEV(R, SE->getConstant(R->getType(), 1)); 234ca9b7037e28759c200fe5ca98190cabd121a1bbaDan Gohman if (R != BackedgeTakenCount) { 235ca9b7037e28759c200fe5ca98190cabd121a1bbaDan Gohman const SCEV *L = SE->getSCEV(OrigCond->getOperand(0)); 236deff621abdd48bd70434bd4d7ef30f08ddba1cd8Dan Gohman L = SE->getMinusSCEV(L, SE->getConstant(L->getType(), 1)); 237ca9b7037e28759c200fe5ca98190cabd121a1bbaDan Gohman if (L != BackedgeTakenCount) 2384dfdf242c1917e98f407818eb5b68ae0b4678f26Andrew Trick return false; 239ca9b7037e28759c200fe5ca98190cabd121a1bbaDan Gohman } 240ca9b7037e28759c200fe5ca98190cabd121a1bbaDan Gohman } 2414dfdf242c1917e98f407818eb5b68ae0b4678f26Andrew Trick return true; 2424dfdf242c1917e98f407818eb5b68ae0b4678f26Andrew Trick} 2434dfdf242c1917e98f407818eb5b68ae0b4678f26Andrew Trick 24403d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick/// getBackedgeIVType - Get the widest type used by the loop test after peeking 24503d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick/// through Truncs. 24603d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick/// 24703d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick/// TODO: Unnecessary once LinearFunctionTestReplace is removed. 24803d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trickstatic const Type *getBackedgeIVType(Loop *L) { 24903d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick if (!L->getExitingBlock()) 25003d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick return 0; 25103d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick 25203d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick // Can't rewrite non-branch yet. 25303d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick BranchInst *BI = dyn_cast<BranchInst>(L->getExitingBlock()->getTerminator()); 25403d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick if (!BI) 25503d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick return 0; 25603d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick 25703d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick ICmpInst *Cond = dyn_cast<ICmpInst>(BI->getCondition()); 25803d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick if (!Cond) 25903d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick return 0; 26003d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick 26103d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick const Type *Ty = 0; 26203d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick for(User::op_iterator OI = Cond->op_begin(), OE = Cond->op_end(); 26303d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick OI != OE; ++OI) { 26403d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick assert((!Ty || Ty == (*OI)->getType()) && "bad icmp operand types"); 26503d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick TruncInst *Trunc = dyn_cast<TruncInst>(*OI); 26603d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick if (!Trunc) 26703d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick continue; 26803d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick 26903d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick return Trunc->getSrcTy(); 27003d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick } 27103d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick return Ty; 27203d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick} 27303d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick 2744dfdf242c1917e98f407818eb5b68ae0b4678f26Andrew Trick/// LinearFunctionTestReplace - This method rewrites the exit condition of the 2754dfdf242c1917e98f407818eb5b68ae0b4678f26Andrew Trick/// loop to be a canonical != comparison against the incremented loop induction 2764dfdf242c1917e98f407818eb5b68ae0b4678f26Andrew Trick/// variable. This pass is able to rewrite the exit tests of any loop where the 2774dfdf242c1917e98f407818eb5b68ae0b4678f26Andrew Trick/// SCEV analysis can determine a loop-invariant trip count of the loop, which 2784dfdf242c1917e98f407818eb5b68ae0b4678f26Andrew Trick/// is actually a much broader range than just linear tests. 2794dfdf242c1917e98f407818eb5b68ae0b4678f26Andrew TrickICmpInst *IndVarSimplify:: 2804dfdf242c1917e98f407818eb5b68ae0b4678f26Andrew TrickLinearFunctionTestReplace(Loop *L, 2814dfdf242c1917e98f407818eb5b68ae0b4678f26Andrew Trick const SCEV *BackedgeTakenCount, 2824dfdf242c1917e98f407818eb5b68ae0b4678f26Andrew Trick PHINode *IndVar, 2834dfdf242c1917e98f407818eb5b68ae0b4678f26Andrew Trick SCEVExpander &Rewriter) { 28403d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick assert(canExpandBackedgeTakenCount(L, SE) && "precondition"); 2854dfdf242c1917e98f407818eb5b68ae0b4678f26Andrew Trick BranchInst *BI = cast<BranchInst>(L->getExitingBlock()->getTerminator()); 286ca9b7037e28759c200fe5ca98190cabd121a1bbaDan Gohman 287d244057a48660c3cd30d219118ece3f947947790Chris Lattner // If the exiting block is not the same as the backedge block, we must compare 288d244057a48660c3cd30d219118ece3f947947790Chris Lattner // against the preincremented value, otherwise we prefer to compare against 289d244057a48660c3cd30d219118ece3f947947790Chris Lattner // the post-incremented value. 290c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman Value *CmpIndVar; 2910bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *RHS = BackedgeTakenCount; 2924dfdf242c1917e98f407818eb5b68ae0b4678f26Andrew Trick if (L->getExitingBlock() == L->getLoopLatch()) { 29346bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman // Add one to the "backedge-taken" count to get the trip count. 29446bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman // If this addition may overflow, we have to be more pessimistic and 29546bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman // cast the induction variable before doing the add. 296deff621abdd48bd70434bd4d7ef30f08ddba1cd8Dan Gohman const SCEV *Zero = SE->getConstant(BackedgeTakenCount->getType(), 0); 2970bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *N = 29846bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman SE->getAddExpr(BackedgeTakenCount, 299deff621abdd48bd70434bd4d7ef30f08ddba1cd8Dan Gohman SE->getConstant(BackedgeTakenCount->getType(), 1)); 300c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman if ((isa<SCEVConstant>(N) && !N->isZero()) || 3013948d0b8b0a71fabf25fceba1858b2b6a60d3d00Dan Gohman SE->isLoopEntryGuardedByCond(L, ICmpInst::ICMP_NE, N, Zero)) { 302c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman // No overflow. Cast the sum. 30346bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman RHS = SE->getTruncateOrZeroExtend(N, IndVar->getType()); 304c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman } else { 305c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman // Potential overflow. Cast before doing the add. 30646bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman RHS = SE->getTruncateOrZeroExtend(BackedgeTakenCount, 30746bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman IndVar->getType()); 30846bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman RHS = SE->getAddExpr(RHS, 309deff621abdd48bd70434bd4d7ef30f08ddba1cd8Dan Gohman SE->getConstant(IndVar->getType(), 1)); 310c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman } 311c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman 31246bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman // The BackedgeTaken expression contains the number of times that the 31346bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman // backedge branches to the loop header. This is one less than the 31446bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman // number of times the loop executes, so use the incremented indvar. 3154dfdf242c1917e98f407818eb5b68ae0b4678f26Andrew Trick CmpIndVar = IndVar->getIncomingValueForBlock(L->getExitingBlock()); 316d244057a48660c3cd30d219118ece3f947947790Chris Lattner } else { 317d244057a48660c3cd30d219118ece3f947947790Chris Lattner // We have to use the preincremented value... 31846bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman RHS = SE->getTruncateOrZeroExtend(BackedgeTakenCount, 31946bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman IndVar->getType()); 320c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman CmpIndVar = IndVar; 321d244057a48660c3cd30d219118ece3f947947790Chris Lattner } 32259fdaeeae8f183e18bb6ad5c382ca23e28e6aaf6Chris Lattner 323667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman // Expand the code for the iteration count. 32417ead4ff4baceb2c5503f233d0288d363ae44165Dan Gohman assert(SE->isLoopInvariant(RHS, L) && 32540a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman "Computed iteration count is not loop invariant!"); 326667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman Value *ExitCnt = Rewriter.expandCodeFor(RHS, IndVar->getType(), BI); 32740bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner 328e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer // Insert a new icmp_ne or icmp_eq instruction before the branch. 329e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer ICmpInst::Predicate Opcode; 33040bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner if (L->contains(BI->getSuccessor(0))) 331e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer Opcode = ICmpInst::ICMP_NE; 33240bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner else 333e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer Opcode = ICmpInst::ICMP_EQ; 33440bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner 335f67ef318aa29e7cc0c7de76349881959936d9eeeDavid Greene DEBUG(dbgs() << "INDVARS: Rewriting loop exit condition to:\n" 336bdff548e4dd577a72094d57b282de4e765643b96Chris Lattner << " LHS:" << *CmpIndVar << '\n' 337bdff548e4dd577a72094d57b282de4e765643b96Chris Lattner << " op:\t" 338bdff548e4dd577a72094d57b282de4e765643b96Chris Lattner << (Opcode == ICmpInst::ICMP_NE ? "!=" : "==") << "\n" 339bdff548e4dd577a72094d57b282de4e765643b96Chris Lattner << " RHS:\t" << *RHS << "\n"); 340c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman 341333c40096561218bc3597cf153c0a3895274414cOwen Anderson ICmpInst *Cond = new ICmpInst(BI, Opcode, CmpIndVar, ExitCnt, "exitcond"); 34281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 3432444080ca4f1f63d647272650aae874360c604cdDan Gohman Value *OrigCond = BI->getCondition(); 34495bdbfa0668cc2b475429fbc6046f364bc01edf7Dan Gohman // It's tempting to use replaceAllUsesWith here to fully replace the old 34595bdbfa0668cc2b475429fbc6046f364bc01edf7Dan Gohman // comparison, but that's not immediately safe, since users of the old 34695bdbfa0668cc2b475429fbc6046f364bc01edf7Dan Gohman // comparison may not be dominated by the new comparison. Instead, just 34795bdbfa0668cc2b475429fbc6046f364bc01edf7Dan Gohman // update the branch to use the new comparison; in the common case this 34895bdbfa0668cc2b475429fbc6046f364bc01edf7Dan Gohman // will make old comparison dead. 34995bdbfa0668cc2b475429fbc6046f364bc01edf7Dan Gohman BI->setCondition(Cond); 35088e92cf16b92ec609e2700bcf4d184d0c3cac202Andrew Trick DeadInsts.push_back(OrigCond); 35181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 35240bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner ++NumLFTR; 35340bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner Changed = true; 35481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman return Cond; 35540bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner} 3563324e718bc9ac2ede08a14c325848b576849542bChris Lattner 35740bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner/// RewriteLoopExitValues - Check to see if this loop has a computable 35840bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner/// loop-invariant execution count. If so, this means that we can compute the 35940bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner/// final value of any expressions that are recurrent in the loop, and 36040bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner/// substitute the exit values from the loop into any instructions outside of 36140bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner/// the loop that use the final values of the current expressions. 36281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman/// 36381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman/// This is mostly redundant with the regular IndVarSimplify activities that 36481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman/// happen later, except that it's more powerful in some cases, because it's 36581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman/// able to brute-force evaluate arbitrary instructions as long as they have 36681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman/// constant operands at the beginning of the loop. 367f1859891b7bef1ac8d5cea100f152aeb5783c3b3Chris Lattnervoid IndVarSimplify::RewriteLoopExitValues(Loop *L, SCEVExpander &Rewriter) { 36881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Verify the input to the pass in already in LCSSA form. 369bbf81d88116d23fb0776412b5916f7d0b8b3ca7eDan Gohman assert(L->isLCSSAForm(*DT)); 37081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 371b7211a2ce13a0365e0e1dd2f27adda2ee3d1288bDevang Patel SmallVector<BasicBlock*, 8> ExitBlocks; 3729f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner L->getUniqueExitBlocks(ExitBlocks); 3739f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner 3749f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // Find all values that are computed inside the loop, but used outside of it. 3759f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // Because of LCSSA, these values will only occur in LCSSA PHI Nodes. Scan 3769f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // the exit blocks of the loop to find them. 3779f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) { 3789f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner BasicBlock *ExitBB = ExitBlocks[i]; 379cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 3809f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // If there are no PHI nodes in this exit block, then no values defined 3819f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // inside the loop are used on this path, skip it. 3829f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner PHINode *PN = dyn_cast<PHINode>(ExitBB->begin()); 3839f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner if (!PN) continue; 384cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 3859f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner unsigned NumPreds = PN->getNumIncomingValues(); 386cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 3879f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // Iterate over all of the PHI nodes. 3889f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner BasicBlock::iterator BBI = ExitBB->begin(); 3899f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner while ((PN = dyn_cast<PHINode>(BBI++))) { 3903790fb0c036acaa4db50aff83dd8b3bf51f8af6aTorok Edwin if (PN->use_empty()) 3913790fb0c036acaa4db50aff83dd8b3bf51f8af6aTorok Edwin continue; // dead use, don't replace it 392814f2b2d1927a5397c0e923588527277b9f67d6bDan Gohman 393814f2b2d1927a5397c0e923588527277b9f67d6bDan Gohman // SCEV only supports integer expressions for now. 394814f2b2d1927a5397c0e923588527277b9f67d6bDan Gohman if (!PN->getType()->isIntegerTy() && !PN->getType()->isPointerTy()) 395814f2b2d1927a5397c0e923588527277b9f67d6bDan Gohman continue; 396814f2b2d1927a5397c0e923588527277b9f67d6bDan Gohman 39745a2d7d44ae697e28df383d31455145fb754ac58Dale Johannesen // It's necessary to tell ScalarEvolution about this explicitly so that 39845a2d7d44ae697e28df383d31455145fb754ac58Dale Johannesen // it can walk the def-use list and forget all SCEVs, as it may not be 39945a2d7d44ae697e28df383d31455145fb754ac58Dale Johannesen // watching the PHI itself. Once the new exit value is in place, there 40045a2d7d44ae697e28df383d31455145fb754ac58Dale Johannesen // may not be a def-use connection between the loop and every instruction 40145a2d7d44ae697e28df383d31455145fb754ac58Dale Johannesen // which got a SCEVAddRecExpr for that loop. 40245a2d7d44ae697e28df383d31455145fb754ac58Dale Johannesen SE->forgetValue(PN); 40345a2d7d44ae697e28df383d31455145fb754ac58Dale Johannesen 4049f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // Iterate over all of the values in all the PHI nodes. 4059f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner for (unsigned i = 0; i != NumPreds; ++i) { 4069f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // If the value being merged in is not integer or is not defined 4079f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // in the loop, skip it. 4089f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner Value *InVal = PN->getIncomingValue(i); 409814f2b2d1927a5397c0e923588527277b9f67d6bDan Gohman if (!isa<Instruction>(InVal)) 4109f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner continue; 4119f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner 4129f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // If this pred is for a subloop, not L itself, skip it. 413cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman if (LI->getLoopFor(PN->getIncomingBlock(i)) != L) 4149f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner continue; // The Block is in a subloop, skip it. 4159f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner 4169f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // Check that InVal is defined in the loop. 4179f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner Instruction *Inst = cast<Instruction>(InVal); 41892329c7fbe572892c17aa2d2542a10e3ea16132fDan Gohman if (!L->contains(Inst)) 4199f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner continue; 420cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 4219f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // Okay, this instruction has a user outside of the current loop 4229f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // and varies predictably *inside* the loop. Evaluate the value it 4239f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // contains when the loop exits, if possible. 4240bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *ExitValue = SE->getSCEVAtScope(Inst, L->getParentLoop()); 42517ead4ff4baceb2c5503f233d0288d363ae44165Dan Gohman if (!SE->isLoopInvariant(ExitValue, L)) 4269f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner continue; 4279f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner 428667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman Value *ExitVal = Rewriter.expandCodeFor(ExitValue, PN->getType(), Inst); 429cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 430f67ef318aa29e7cc0c7de76349881959936d9eeeDavid Greene DEBUG(dbgs() << "INDVARS: RLEV: AfterLoopVal = " << *ExitVal << '\n' 431bdff548e4dd577a72094d57b282de4e765643b96Chris Lattner << " LoopVal = " << *Inst << "\n"); 4329caed5440d59dac4b388152fe8b993dc0491e5e9Chris Lattner 433b12a754cce0c1d5542af605203a47820edba454dAndrew Trick if (!isValidRewrite(Inst, ExitVal)) { 434b12a754cce0c1d5542af605203a47820edba454dAndrew Trick DeadInsts.push_back(ExitVal); 435b12a754cce0c1d5542af605203a47820edba454dAndrew Trick continue; 436b12a754cce0c1d5542af605203a47820edba454dAndrew Trick } 437b12a754cce0c1d5542af605203a47820edba454dAndrew Trick Changed = true; 438b12a754cce0c1d5542af605203a47820edba454dAndrew Trick ++NumReplaced; 439b12a754cce0c1d5542af605203a47820edba454dAndrew Trick 4409f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner PN->setIncomingValue(i, ExitVal); 441cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 44281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // If this instruction is dead now, delete it. 44381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman RecursivelyDeleteTriviallyDeadInstructions(Inst); 444cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 44565d1e2b6e74fcd370093cbe518ebc15cbc445ad4Dan Gohman if (NumPreds == 1) { 44665d1e2b6e74fcd370093cbe518ebc15cbc445ad4Dan Gohman // Completely replace a single-pred PHI. This is safe, because the 44765d1e2b6e74fcd370093cbe518ebc15cbc445ad4Dan Gohman // NewVal won't be variant in the loop, so we don't need an LCSSA phi 44865d1e2b6e74fcd370093cbe518ebc15cbc445ad4Dan Gohman // node anymore. 4499f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner PN->replaceAllUsesWith(ExitVal); 45081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman RecursivelyDeleteTriviallyDeadInstructions(PN); 451c9838f25d53d3dd7d38949ef6c28f2505a110f45Chris Lattner } 4524bd09d70cceb3851f7eb1c2f98338b3071d405f3Chris Lattner } 45365d1e2b6e74fcd370093cbe518ebc15cbc445ad4Dan Gohman if (NumPreds != 1) { 454667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman // Clone the PHI and delete the original one. This lets IVUsers and 455667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman // any other maps purge the original user from their records. 45650b6e33584f4e4cf75c7795b1f1a90731861c825Devang Patel PHINode *NewPN = cast<PHINode>(PN->clone()); 457667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman NewPN->takeName(PN); 458667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman NewPN->insertBefore(PN); 459667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman PN->replaceAllUsesWith(NewPN); 460667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman PN->eraseFromParent(); 461667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman } 462c9838f25d53d3dd7d38949ef6c28f2505a110f45Chris Lattner } 463c9838f25d53d3dd7d38949ef6c28f2505a110f45Chris Lattner } 464472fdf7090bb00af3a3f9dcbe22263120a527533Dan Gohman 465472fdf7090bb00af3a3f9dcbe22263120a527533Dan Gohman // The insertion point instruction may have been deleted; clear it out 466472fdf7090bb00af3a3f9dcbe22263120a527533Dan Gohman // so that the rewriter doesn't trip over it later. 467472fdf7090bb00af3a3f9dcbe22263120a527533Dan Gohman Rewriter.clearInsertPoint(); 46840bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner} 46915cad759fe2048ac5eb137c6bb0ab7287538677eChris Lattner 47060f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohmanvoid IndVarSimplify::RewriteNonIntegerIVs(Loop *L) { 4712d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman // First step. Check to see if there are any floating-point recurrences. 47240bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // If there are, change them into integer recurrences, permitting analysis by 47340bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // the SCEV routines. 47415cad759fe2048ac5eb137c6bb0ab7287538677eChris Lattner // 475f1859891b7bef1ac8d5cea100f152aeb5783c3b3Chris Lattner BasicBlock *Header = L->getHeader(); 476fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 47781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman SmallVector<WeakVH, 8> PHIs; 47881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman for (BasicBlock::iterator I = Header->begin(); 47981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman PHINode *PN = dyn_cast<PHINode>(I); ++I) 48081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman PHIs.push_back(PN); 48181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 48281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman for (unsigned i = 0, e = PHIs.size(); i != e; ++i) 483ea4894a7fcfb8946d1f7b1301aef98f7f6c9f251Gabor Greif if (PHINode *PN = dyn_cast_or_null<PHINode>(&*PHIs[i])) 48481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman HandleFloatingPointIV(L, PN); 48515cad759fe2048ac5eb137c6bb0ab7287538677eChris Lattner 4862d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman // If the loop previously had floating-point IV, ScalarEvolution 48760f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman // may not have been able to compute a trip count. Now that we've done some 48860f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman // re-writing, the trip count may be computable. 48960f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman if (Changed) 4904c7279ac726e338400626fca5a09b5533426eb6aDan Gohman SE->forgetLoop(L); 491c671d892ab1d3d8fed18a61f66f3f3a86e73ebd9Dale Johannesen} 492c671d892ab1d3d8fed18a61f66f3f3a86e73ebd9Dale Johannesen 4932fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// SimplifyIVUsers - Iteratively perform simplification on IVUsers within this 4942fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// loop. IVUsers is treated as a worklist. Each successive simplification may 4952fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// push more users which may themselves be candidates for simplification. 4962fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// 4972fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// This is the old approach to IV simplification to be replaced by 4982fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// SimplifyIVUsersNoRewrite. 4992fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// 5002fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trickvoid IndVarSimplify::SimplifyIVUsers(SCEVExpander &Rewriter) { 5012fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick // Each round of simplification involves a round of eliminating operations 5022fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick // followed by a round of widening IVs. A single IVUsers worklist is used 5032fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick // across all rounds. The inner loop advances the user. If widening exposes 5042fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick // more uses, then another pass through the outer loop is triggered. 5052fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick for (IVUsers::iterator I = IU->begin(); I != IU->end(); ++I) { 5062fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick Instruction *UseInst = I->getUser(); 5072fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick Value *IVOperand = I->getOperandValToReplace(); 5082fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick 5092fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick if (ICmpInst *ICmp = dyn_cast<ICmpInst>(UseInst)) { 5102fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick EliminateIVComparison(ICmp, IVOperand); 5112fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick continue; 5122fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick } 5132fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick if (BinaryOperator *Rem = dyn_cast<BinaryOperator>(UseInst)) { 5142fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick bool IsSigned = Rem->getOpcode() == Instruction::SRem; 5152fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick if (IsSigned || Rem->getOpcode() == Instruction::URem) { 5164417e537b65c14b378aeca75b2773582dd102f63Andrew Trick EliminateIVRemainder(Rem, IVOperand, IsSigned); 5172fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick continue; 5182fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick } 5192fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick } 5202fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick } 5212fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick} 5222fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick 523f85092c25525f75eef6982ffa40c9b48b87da987Andrew Tricknamespace { 524f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // Collect information about induction variables that are used by sign/zero 525f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // extend operations. This information is recorded by CollectExtend and 526f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // provides the input to WidenIV. 527f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick struct WideIVInfo { 528f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick const Type *WidestNativeType; // Widest integer type created [sz]ext 529f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick bool IsSigned; // Was an sext user seen before a zext? 530f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 531f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick WideIVInfo() : WidestNativeType(0), IsSigned(false) {} 532f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick }; 533f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick} 534f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 535f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick/// CollectExtend - Update information about the induction variable that is 536f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick/// extended by this sign or zero extend operation. This is used to determine 537f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick/// the final width of the IV before actually widening it. 5382fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trickstatic void CollectExtend(CastInst *Cast, bool IsSigned, WideIVInfo &WI, 5392fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick ScalarEvolution *SE, const TargetData *TD) { 540f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick const Type *Ty = Cast->getType(); 541f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick uint64_t Width = SE->getTypeSizeInBits(Ty); 542f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick if (TD && !TD->isLegalInteger(Width)) 543f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick return; 544f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 5452fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick if (!WI.WidestNativeType) { 5462fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick WI.WidestNativeType = SE->getEffectiveSCEVType(Ty); 5472fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick WI.IsSigned = IsSigned; 548f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick return; 549f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick } 550f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 551f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // We extend the IV to satisfy the sign of its first user, arbitrarily. 5522fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick if (WI.IsSigned != IsSigned) 553f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick return; 554f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 5552fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick if (Width > SE->getTypeSizeInBits(WI.WidestNativeType)) 5562fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick WI.WidestNativeType = SE->getEffectiveSCEVType(Ty); 557f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick} 558f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 559f85092c25525f75eef6982ffa40c9b48b87da987Andrew Tricknamespace { 560f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick/// WidenIV - The goal of this transform is to remove sign and zero extends 561f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick/// without creating any new induction variables. To do this, it creates a new 562f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick/// phi of the wider type and redirects all users, either removing extends or 563f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick/// inserting truncs whenever we stop propagating the type. 564f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick/// 565f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trickclass WidenIV { 5662fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick // Parameters 567f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick PHINode *OrigPhi; 568f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick const Type *WideType; 569f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick bool IsSigned; 570f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 5712fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick // Context 5722fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick LoopInfo *LI; 5732fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick Loop *L; 574f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick ScalarEvolution *SE; 5752fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick DominatorTree *DT; 576f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 5772fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick // Result 578f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick PHINode *WidePhi; 579f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick Instruction *WideInc; 580f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick const SCEV *WideIncExpr; 5812fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick SmallVectorImpl<WeakVH> &DeadInsts; 582f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 5832fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick SmallPtrSet<Instruction*,16> Widened; 584f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 585f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trickpublic: 5862fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick WidenIV(PHINode *PN, const WideIVInfo &WI, LoopInfo *LInfo, 5872fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick ScalarEvolution *SEv, DominatorTree *DTree, 588fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick SmallVectorImpl<WeakVH> &DI) : 589f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick OrigPhi(PN), 5902fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick WideType(WI.WidestNativeType), 5912fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick IsSigned(WI.IsSigned), 592f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick LI(LInfo), 593f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick L(LI->getLoopFor(OrigPhi->getParent())), 594f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick SE(SEv), 595fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick DT(DTree), 596f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick WidePhi(0), 597f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick WideInc(0), 5982fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick WideIncExpr(0), 5992fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick DeadInsts(DI) { 600f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick assert(L->getHeader() == OrigPhi->getParent() && "Phi must be an IV"); 601f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick } 602f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 6032fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick PHINode *CreateWideIV(SCEVExpander &Rewriter); 604f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 605f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trickprotected: 606f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick Instruction *CloneIVUser(Instruction *NarrowUse, 607f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick Instruction *NarrowDef, 608f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick Instruction *WideDef); 609f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 61003d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick const SCEVAddRecExpr *GetWideRecurrence(Instruction *NarrowUse); 61103d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick 612f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick Instruction *WidenIVUse(Instruction *NarrowUse, 613f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick Instruction *NarrowDef, 614f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick Instruction *WideDef); 615f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick}; 616f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick} // anonymous namespace 617f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 61803d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trickstatic Value *getExtend( Value *NarrowOper, const Type *WideType, 61903d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick bool IsSigned, IRBuilder<> &Builder) { 62003d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick return IsSigned ? Builder.CreateSExt(NarrowOper, WideType) : 62103d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick Builder.CreateZExt(NarrowOper, WideType); 622f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick} 623931e345e76e75391d2a7c96530e305f802b5429dDan Gohman 624f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick/// CloneIVUser - Instantiate a wide operation to replace a narrow 625f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick/// operation. This only needs to handle operations that can evaluation to 626f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick/// SCEVAddRec. It can safely return 0 for any operation we decide not to clone. 627f85092c25525f75eef6982ffa40c9b48b87da987Andrew TrickInstruction *WidenIV::CloneIVUser(Instruction *NarrowUse, 628f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick Instruction *NarrowDef, 629f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick Instruction *WideDef) { 630f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick unsigned Opcode = NarrowUse->getOpcode(); 631f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick switch (Opcode) { 632f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick default: 633f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick return 0; 634f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick case Instruction::Add: 635f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick case Instruction::Mul: 636f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick case Instruction::UDiv: 637f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick case Instruction::Sub: 638f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick case Instruction::And: 639f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick case Instruction::Or: 640f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick case Instruction::Xor: 641f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick case Instruction::Shl: 642f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick case Instruction::LShr: 643f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick case Instruction::AShr: 644f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick DEBUG(dbgs() << "Cloning IVUser: " << *NarrowUse << "\n"); 645f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 64603d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick IRBuilder<> Builder(NarrowUse); 64703d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick 64803d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick // Replace NarrowDef operands with WideDef. Otherwise, we don't know 64903d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick // anything about the narrow operand yet so must insert a [sz]ext. It is 65003d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick // probably loop invariant and will be folded or hoisted. If it actually 65103d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick // comes from a widened IV, it should be removed during a future call to 65203d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick // WidenIVUse. 65303d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick Value *LHS = (NarrowUse->getOperand(0) == NarrowDef) ? WideDef : 65403d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick getExtend(NarrowUse->getOperand(0), WideType, IsSigned, Builder); 65503d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick Value *RHS = (NarrowUse->getOperand(1) == NarrowDef) ? WideDef : 65603d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick getExtend(NarrowUse->getOperand(1), WideType, IsSigned, Builder); 65703d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick 658f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick BinaryOperator *NarrowBO = cast<BinaryOperator>(NarrowUse); 659f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick BinaryOperator *WideBO = BinaryOperator::Create(NarrowBO->getOpcode(), 66003d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick LHS, RHS, 661f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick NarrowBO->getName()); 662f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick Builder.Insert(WideBO); 663f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick if (NarrowBO->hasNoUnsignedWrap()) WideBO->setHasNoUnsignedWrap(); 664f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick if (NarrowBO->hasNoSignedWrap()) WideBO->setHasNoSignedWrap(); 665f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 66603d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick return WideBO; 667f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick } 668f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick llvm_unreachable(0); 669f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick} 670f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 67103d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick// GetWideRecurrence - Is this instruction potentially interesting from IVUsers' 67203d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick// perspective after widening it's type? In other words, can the extend be 67303d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick// safely hoisted out of the loop with SCEV reducing the value to a recurrence 67403d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick// on the same loop. If so, return the sign or zero extended 67503d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick// recurrence. Otherwise return NULL. 67603d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trickconst SCEVAddRecExpr *WidenIV::GetWideRecurrence(Instruction *NarrowUse) { 67703d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick if (!SE->isSCEVable(NarrowUse->getType())) 67803d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick return 0; 67903d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick 68003d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick const SCEV *NarrowExpr = SE->getSCEV(NarrowUse); 68103d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick const SCEV *WideExpr = IsSigned ? 68203d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick SE->getSignExtendExpr(NarrowExpr, WideType) : 68303d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick SE->getZeroExtendExpr(NarrowExpr, WideType); 68403d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(WideExpr); 68503d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick if (!AddRec || AddRec->getLoop() != L) 68603d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick return 0; 68703d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick 68803d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick return AddRec; 68903d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick} 69003d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick 691fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick/// HoistStep - Attempt to hoist an IV increment above a potential use. 692fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick/// 693fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick/// To successfully hoist, two criteria must be met: 694fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick/// - IncV operands dominate InsertPos and 695fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick/// - InsertPos dominates IncV 696fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick/// 697fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick/// Meeting the second condition means that we don't need to check all of IncV's 698fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick/// existing uses (it's moving up in the domtree). 699fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick/// 700fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick/// This does not yet recursively hoist the operands, although that would 701fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick/// not be difficult. 702fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trickstatic bool HoistStep(Instruction *IncV, Instruction *InsertPos, 703fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick const DominatorTree *DT) 704fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick{ 705fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick if (DT->dominates(IncV, InsertPos)) 706fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick return true; 707fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick 708fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick if (!DT->dominates(InsertPos->getParent(), IncV->getParent())) 709fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick return false; 710fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick 711fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick if (IncV->mayHaveSideEffects()) 712fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick return false; 713fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick 714fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick // Attempt to hoist IncV 715fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick for (User::op_iterator OI = IncV->op_begin(), OE = IncV->op_end(); 716fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick OI != OE; ++OI) { 717fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick Instruction *OInst = dyn_cast<Instruction>(OI); 718fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick if (OInst && !DT->dominates(OInst, InsertPos)) 719fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick return false; 720fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick } 721fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick IncV->moveBefore(InsertPos); 722fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick return true; 723fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick} 724fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick 725f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick/// WidenIVUse - Determine whether an individual user of the narrow IV can be 726f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick/// widened. If so, return the wide clone of the user. 727f85092c25525f75eef6982ffa40c9b48b87da987Andrew TrickInstruction *WidenIV::WidenIVUse(Instruction *NarrowUse, 728f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick Instruction *NarrowDef, 729f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick Instruction *WideDef) { 730f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // To be consistent with IVUsers, stop traversing the def-use chain at 731f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // inner-loop phis or post-loop phis. 732f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick if (isa<PHINode>(NarrowUse) && LI->getLoopFor(NarrowUse->getParent()) != L) 733f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick return 0; 734f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 735f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // Handle data flow merges and bizarre phi cycles. 7362fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick if (!Widened.insert(NarrowUse)) 737f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick return 0; 738f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 739f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // Our raison d'etre! Eliminate sign and zero extension. 740f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick if (IsSigned ? isa<SExtInst>(NarrowUse) : isa<ZExtInst>(NarrowUse)) { 74103d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick Value *NewDef = WideDef; 74203d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick if (NarrowUse->getType() != WideType) { 74303d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick unsigned CastWidth = SE->getTypeSizeInBits(NarrowUse->getType()); 74403d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick unsigned IVWidth = SE->getTypeSizeInBits(WideType); 74503d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick if (CastWidth < IVWidth) { 74603d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick // The cast isn't as wide as the IV, so insert a Trunc. 74703d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick IRBuilder<> Builder(NarrowUse); 74803d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick NewDef = Builder.CreateTrunc(WideDef, NarrowUse->getType()); 74903d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick } 75003d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick else { 75103d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick // A wider extend was hidden behind a narrower one. This may induce 75203d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick // another round of IV widening in which the intermediate IV becomes 75303d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick // dead. It should be very rare. 75403d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick DEBUG(dbgs() << "INDVARS: New IV " << *WidePhi 75503d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick << " not wide enough to subsume " << *NarrowUse << "\n"); 75603d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick NarrowUse->replaceUsesOfWith(NarrowDef, WideDef); 75703d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick NewDef = NarrowUse; 75803d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick } 75903d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick } 76003d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick if (NewDef != NarrowUse) { 76103d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick DEBUG(dbgs() << "INDVARS: eliminating " << *NarrowUse 76203d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick << " replaced by " << *WideDef << "\n"); 76303d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick ++NumElimExt; 76403d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick NarrowUse->replaceAllUsesWith(NewDef); 76503d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick DeadInsts.push_back(NarrowUse); 76603d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick } 7672fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick // Now that the extend is gone, we want to expose it's uses for potential 7682fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick // further simplification. We don't need to directly inform SimplifyIVUsers 7692fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick // of the new users, because their parent IV will be processed later as a 7702fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick // new loop phi. If we preserved IVUsers analysis, we would also want to 7712fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick // push the uses of WideDef here. 772f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 773f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // No further widening is needed. The deceased [sz]ext had done it for us. 774f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick return 0; 775f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick } 776f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick const SCEVAddRecExpr *WideAddRec = GetWideRecurrence(NarrowUse); 777f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick if (!WideAddRec) { 778f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // This user does not evaluate to a recurence after widening, so don't 779f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // follow it. Instead insert a Trunc to kill off the original use, 780f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // eventually isolating the original narrow IV so it can be removed. 781f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick IRBuilder<> Builder(NarrowUse); 78203d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick Value *Trunc = Builder.CreateTrunc(WideDef, NarrowDef->getType()); 783f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick NarrowUse->replaceUsesOfWith(NarrowDef, Trunc); 784f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick return 0; 785f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick } 786fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick // Reuse the IV increment that SCEVExpander created as long as it dominates 787fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick // NarrowUse. 788f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick Instruction *WideUse = 0; 789fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick if (WideAddRec == WideIncExpr && HoistStep(WideInc, NarrowUse, DT)) { 790f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick WideUse = WideInc; 791f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick } 792f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick else { 793f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick WideUse = CloneIVUser(NarrowUse, NarrowDef, WideDef); 794f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick if (!WideUse) 795f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick return 0; 796f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick } 797f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // GetWideRecurrence ensured that the narrow expression could be extended 798f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // outside the loop without overflow. This suggests that the wide use 799f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // evaluates to the same expression as the extended narrow use, but doesn't 800f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // absolutely guarantee it. Hence the following failsafe check. In rare cases 8012fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick // where it fails, we simply throw away the newly created wide use. 802f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick if (WideAddRec != SE->getSCEV(WideUse)) { 803f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick DEBUG(dbgs() << "Wide use expression mismatch: " << *WideUse 804f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick << ": " << *SE->getSCEV(WideUse) << " != " << *WideAddRec << "\n"); 805f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick DeadInsts.push_back(WideUse); 806f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick return 0; 807f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick } 808f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 809f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // Returning WideUse pushes it on the worklist. 810f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick return WideUse; 811f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick} 812f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 813f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick/// CreateWideIV - Process a single induction variable. First use the 814f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick/// SCEVExpander to create a wide induction variable that evaluates to the same 815f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick/// recurrence as the original narrow IV. Then use a worklist to forward 8162fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// traverse the narrow IV's def-use chain. After WidenIVUse has processed all 817f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick/// interesting IV users, the narrow IV will be isolated for removal by 818f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick/// DeleteDeadPHIs. 819f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick/// 820f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick/// It would be simpler to delete uses as they are processed, but we must avoid 821f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick/// invalidating SCEV expressions. 822f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick/// 8232fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew TrickPHINode *WidenIV::CreateWideIV(SCEVExpander &Rewriter) { 824f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // Is this phi an induction variable? 825f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(SE->getSCEV(OrigPhi)); 826f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick if (!AddRec) 8272fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick return NULL; 828f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 829f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // Widen the induction variable expression. 830f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick const SCEV *WideIVExpr = IsSigned ? 831f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick SE->getSignExtendExpr(AddRec, WideType) : 832f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick SE->getZeroExtendExpr(AddRec, WideType); 833f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 834f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick assert(SE->getEffectiveSCEVType(WideIVExpr->getType()) == WideType && 835f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick "Expect the new IV expression to preserve its type"); 836f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 837f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // Can the IV be extended outside the loop without overflow? 838f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick AddRec = dyn_cast<SCEVAddRecExpr>(WideIVExpr); 839f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick if (!AddRec || AddRec->getLoop() != L) 8402fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick return NULL; 841f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 8422fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick // An AddRec must have loop-invariant operands. Since this AddRec is 843f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // materialized by a loop header phi, the expression cannot have any post-loop 844f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // operands, so they must dominate the loop header. 845f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick assert(SE->properlyDominates(AddRec->getStart(), L->getHeader()) && 846f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick SE->properlyDominates(AddRec->getStepRecurrence(*SE), L->getHeader()) 847f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick && "Loop header phi recurrence inputs do not dominate the loop"); 848f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 849f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // The rewriter provides a value for the desired IV expression. This may 850f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // either find an existing phi or materialize a new one. Either way, we 851f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // expect a well-formed cyclic phi-with-increments. i.e. any operand not part 852f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // of the phi-SCC dominates the loop entry. 853f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick Instruction *InsertPt = L->getHeader()->begin(); 854f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick WidePhi = cast<PHINode>(Rewriter.expandCodeFor(AddRec, WideType, InsertPt)); 855f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 856f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // Remembering the WideIV increment generated by SCEVExpander allows 857f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // WidenIVUse to reuse it when widening the narrow IV's increment. We don't 858f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // employ a general reuse mechanism because the call above is the only call to 859f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // SCEVExpander. Henceforth, we produce 1-to-1 narrow to wide uses. 860fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick if (BasicBlock *LatchBlock = L->getLoopLatch()) { 861fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick WideInc = 862fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick cast<Instruction>(WidePhi->getIncomingValueForBlock(LatchBlock)); 863fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick WideIncExpr = SE->getSCEV(WideInc); 864fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick } 865f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 866f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick DEBUG(dbgs() << "Wide IV: " << *WidePhi << "\n"); 867f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick ++NumWidened; 868f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 869f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // Traverse the def-use chain using a worklist starting at the original IV. 8702fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick assert(Widened.empty() && "expect initial state" ); 871f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 872fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick // Each worklist entry has a Narrow def-use link and Wide def. 873fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick SmallVector<std::pair<Use *, Instruction *>, 8> NarrowIVUsers; 874fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick for (Value::use_iterator UI = OrigPhi->use_begin(), 875fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick UE = OrigPhi->use_end(); UI != UE; ++UI) { 876fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick NarrowIVUsers.push_back(std::make_pair(&UI.getUse(), WidePhi)); 877fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick } 878f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick while (!NarrowIVUsers.empty()) { 879fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick Use *NarrowDefUse; 880fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick Instruction *WideDef; 881fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick tie(NarrowDefUse, WideDef) = NarrowIVUsers.pop_back_val(); 882fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick 883fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick // Process a def-use edge. This may replace the use, so don't hold a 884fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick // use_iterator across it. 885fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick Instruction *NarrowDef = cast<Instruction>(NarrowDefUse->get()); 886fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick Instruction *NarrowUse = cast<Instruction>(NarrowDefUse->getUser()); 887fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick Instruction *WideUse = WidenIVUse(NarrowUse, NarrowDef, WideDef); 888fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick 889fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick // Follow all def-use edges from the previous narrow use. 890fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick if (WideUse) { 891fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick for (Value::use_iterator UI = NarrowUse->use_begin(), 892fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick UE = NarrowUse->use_end(); UI != UE; ++UI) { 893fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick NarrowIVUsers.push_back(std::make_pair(&UI.getUse(), WideUse)); 894fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick } 895aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick } 896fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick // WidenIVUse may have removed the def-use edge. 897fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick if (NarrowDef->use_empty()) 898fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick DeadInsts.push_back(NarrowDef); 899931e345e76e75391d2a7c96530e305f802b5429dDan Gohman } 9002fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick return WidePhi; 901931e345e76e75391d2a7c96530e305f802b5429dDan Gohman} 902931e345e76e75391d2a7c96530e305f802b5429dDan Gohman 903aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trickvoid IndVarSimplify::EliminateIVComparison(ICmpInst *ICmp, Value *IVOperand) { 904aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick unsigned IVOperIdx = 0; 905aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick ICmpInst::Predicate Pred = ICmp->getPredicate(); 906aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick if (IVOperand != ICmp->getOperand(0)) { 907aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick // Swapped 908aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick assert(IVOperand == ICmp->getOperand(1) && "Can't find IVOperand"); 909aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick IVOperIdx = 1; 910aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick Pred = ICmpInst::getSwappedPredicate(Pred); 911aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick } 912a590b79ee227b93c59f60ce1f54cae7a9ebec7c1Dan Gohman 913aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick // Get the SCEVs for the ICmp operands. 914aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick const SCEV *S = SE->getSCEV(ICmp->getOperand(IVOperIdx)); 915aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick const SCEV *X = SE->getSCEV(ICmp->getOperand(1 - IVOperIdx)); 916aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick 917aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick // Simplify unnecessary loops away. 918aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick const Loop *ICmpLoop = LI->getLoopFor(ICmp->getParent()); 919aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick S = SE->getSCEVAtScope(S, ICmpLoop); 920aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick X = SE->getSCEVAtScope(X, ICmpLoop); 921aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick 922aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick // If the condition is always true or always false, replace it with 923aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick // a constant value. 924aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick if (SE->isKnownPredicate(Pred, S, X)) 925aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick ICmp->replaceAllUsesWith(ConstantInt::getTrue(ICmp->getContext())); 926aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick else if (SE->isKnownPredicate(ICmpInst::getInversePredicate(Pred), S, X)) 927aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick ICmp->replaceAllUsesWith(ConstantInt::getFalse(ICmp->getContext())); 928aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick else 929aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick return; 930a590b79ee227b93c59f60ce1f54cae7a9ebec7c1Dan Gohman 931aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick DEBUG(dbgs() << "INDVARS: Eliminated comparison: " << *ICmp << '\n'); 93203d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick ++NumElimCmp; 933074397d75e0bf919995f9cf0005fa6fda1c0400cAndrew Trick Changed = true; 934aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick DeadInsts.push_back(ICmp); 935aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick} 936a590b79ee227b93c59f60ce1f54cae7a9ebec7c1Dan Gohman 937aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trickvoid IndVarSimplify::EliminateIVRemainder(BinaryOperator *Rem, 938aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick Value *IVOperand, 9394417e537b65c14b378aeca75b2773582dd102f63Andrew Trick bool IsSigned) { 940aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick // We're only interested in the case where we know something about 941aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick // the numerator. 942aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick if (IVOperand != Rem->getOperand(0)) 943aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick return; 944aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick 945aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick // Get the SCEVs for the ICmp operands. 946aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick const SCEV *S = SE->getSCEV(Rem->getOperand(0)); 947aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick const SCEV *X = SE->getSCEV(Rem->getOperand(1)); 948aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick 949aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick // Simplify unnecessary loops away. 950aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick const Loop *ICmpLoop = LI->getLoopFor(Rem->getParent()); 951aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick S = SE->getSCEVAtScope(S, ICmpLoop); 952aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick X = SE->getSCEVAtScope(X, ICmpLoop); 953aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick 954aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick // i % n --> i if i is in [0,n). 955074397d75e0bf919995f9cf0005fa6fda1c0400cAndrew Trick if ((!IsSigned || SE->isKnownNonNegative(S)) && 956074397d75e0bf919995f9cf0005fa6fda1c0400cAndrew Trick SE->isKnownPredicate(IsSigned ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT, 957aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick S, X)) 958aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick Rem->replaceAllUsesWith(Rem->getOperand(0)); 959aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick else { 960aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick // (i+1) % n --> (i+1)==n?0:(i+1) if i is in [0,n). 961aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick const SCEV *LessOne = 962aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick SE->getMinusSCEV(S, SE->getConstant(S->getType(), 1)); 963074397d75e0bf919995f9cf0005fa6fda1c0400cAndrew Trick if (IsSigned && !SE->isKnownNonNegative(LessOne)) 964aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick return; 965aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick 966074397d75e0bf919995f9cf0005fa6fda1c0400cAndrew Trick if (!SE->isKnownPredicate(IsSigned ? 967aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT, 968aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick LessOne, X)) 969aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick return; 970aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick 971aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick ICmpInst *ICmp = new ICmpInst(Rem, ICmpInst::ICMP_EQ, 972aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick Rem->getOperand(0), Rem->getOperand(1), 973aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick "tmp"); 974aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick SelectInst *Sel = 975aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick SelectInst::Create(ICmp, 976aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick ConstantInt::get(Rem->getType(), 0), 977aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick Rem->getOperand(0), "tmp", Rem); 978aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick Rem->replaceAllUsesWith(Sel); 979aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick } 980a590b79ee227b93c59f60ce1f54cae7a9ebec7c1Dan Gohman 981aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick // Inform IVUsers about the new users. 9822fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick if (IU) { 9832fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick if (Instruction *I = dyn_cast<Instruction>(Rem->getOperand(0))) 9844417e537b65c14b378aeca75b2773582dd102f63Andrew Trick IU->AddUsersIfInteresting(I); 9852fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick } 986aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick DEBUG(dbgs() << "INDVARS: Simplified rem: " << *Rem << '\n'); 98703d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick ++NumElimRem; 988074397d75e0bf919995f9cf0005fa6fda1c0400cAndrew Trick Changed = true; 989aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick DeadInsts.push_back(Rem); 990a590b79ee227b93c59f60ce1f54cae7a9ebec7c1Dan Gohman} 991a590b79ee227b93c59f60ce1f54cae7a9ebec7c1Dan Gohman 9922fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// EliminateIVUser - Eliminate an operation that consumes a simple IV and has 9932fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// no observable side-effect given the range of IV values. 9942fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trickbool IndVarSimplify::EliminateIVUser(Instruction *UseInst, 9952fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick Instruction *IVOperand) { 9962fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick if (ICmpInst *ICmp = dyn_cast<ICmpInst>(UseInst)) { 9972fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick EliminateIVComparison(ICmp, IVOperand); 9982fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick return true; 9992fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick } 10002fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick if (BinaryOperator *Rem = dyn_cast<BinaryOperator>(UseInst)) { 10012fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick bool IsSigned = Rem->getOpcode() == Instruction::SRem; 10022fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick if (IsSigned || Rem->getOpcode() == Instruction::URem) { 10034417e537b65c14b378aeca75b2773582dd102f63Andrew Trick EliminateIVRemainder(Rem, IVOperand, IsSigned); 10042fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick return true; 10052fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick } 10062fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick } 10072fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick 10082fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick // Eliminate any operation that SCEV can prove is an identity function. 10092fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick if (!SE->isSCEVable(UseInst->getType()) || 101011745d4c0276ccb5c64f83d6954b54c8ff2aec98Andrew Trick (UseInst->getType() != IVOperand->getType()) || 10112fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick (SE->getSCEV(UseInst) != SE->getSCEV(IVOperand))) 10122fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick return false; 10132fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick 10142fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick UseInst->replaceAllUsesWith(IVOperand); 10152fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick 10162fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick DEBUG(dbgs() << "INDVARS: Eliminated identity: " << *UseInst << '\n'); 10172fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick ++NumElimIdentity; 10182fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick Changed = true; 10192fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick DeadInsts.push_back(UseInst); 10202fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick return true; 10212fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick} 10222fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick 10232fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// pushIVUsers - Add all uses of Def to the current IV's worklist. 10242fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// 102515832f61775040995bb8aa6056176425bc2c9088Andrew Trickstatic void pushIVUsers( 102615832f61775040995bb8aa6056176425bc2c9088Andrew Trick Instruction *Def, 102715832f61775040995bb8aa6056176425bc2c9088Andrew Trick SmallPtrSet<Instruction*,16> &Simplified, 102815832f61775040995bb8aa6056176425bc2c9088Andrew Trick SmallVectorImpl< std::pair<Instruction*,Instruction*> > &SimpleIVUsers) { 10292fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick 10302fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick for (Value::use_iterator UI = Def->use_begin(), E = Def->use_end(); 10312fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick UI != E; ++UI) { 10322fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick Instruction *User = cast<Instruction>(*UI); 10332fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick 10342fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick // Avoid infinite or exponential worklist processing. 10352fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick // Also ensure unique worklist users. 10362fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick if (Simplified.insert(User)) 10372fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick SimpleIVUsers.push_back(std::make_pair(User, Def)); 10382fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick } 10392fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick} 10402fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick 10412fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// isSimpleIVUser - Return true if this instruction generates a simple SCEV 10422fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// expression in terms of that IV. 10432fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// 10442fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// This is similar to IVUsers' isInsteresting() but processes each instruction 10452fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// non-recursively when the operand is already known to be a simpleIVUser. 10462fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// 10472fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trickbool IndVarSimplify::isSimpleIVUser(Instruction *I, const Loop *L) { 10482fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick if (!SE->isSCEVable(I->getType())) 10492fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick return false; 10502fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick 10512fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick // Get the symbolic expression for this instruction. 10522fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick const SCEV *S = SE->getSCEV(I); 10532fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick 10542fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick // Only consider affine recurrences. 10552fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S); 10562fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick if (AR && AR->getLoop() == L) 10572fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick return true; 10582fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick 10592fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick return false; 10602fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick} 10612fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick 10622fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// SimplifyIVUsersNoRewrite - Iteratively perform simplification on a worklist 10632fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// of IV users. Each successive simplification may push more users which may 10642fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// themselves be candidates for simplification. 10652fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// 10662fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// The "NoRewrite" algorithm does not require IVUsers analysis. Instead, it 10672fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// simplifies instructions in-place during analysis. Rather than rewriting 10682fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// induction variables bottom-up from their users, it transforms a chain of 10692fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// IVUsers top-down, updating the IR only when it encouters a clear 10702fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// optimization opportunitiy. A SCEVExpander "Rewriter" instance is still 10712fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// needed, but only used to generate a new IV (phi) of wider type for sign/zero 10722fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// extend elimination. 10732fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// 10742fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// Once DisableIVRewrite is default, LSR will be the only client of IVUsers. 10752fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// 10762fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trickvoid IndVarSimplify::SimplifyIVUsersNoRewrite(Loop *L, SCEVExpander &Rewriter) { 107715832f61775040995bb8aa6056176425bc2c9088Andrew Trick std::map<PHINode *, WideIVInfo> WideIVMap; 107815832f61775040995bb8aa6056176425bc2c9088Andrew Trick 10792fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick SmallVector<PHINode*, 8> LoopPhis; 10802fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I) { 10812fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick LoopPhis.push_back(cast<PHINode>(I)); 10822fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick } 108315832f61775040995bb8aa6056176425bc2c9088Andrew Trick // Each round of simplification iterates through the SimplifyIVUsers worklist 108415832f61775040995bb8aa6056176425bc2c9088Andrew Trick // for all current phis, then determines whether any IVs can be 108515832f61775040995bb8aa6056176425bc2c9088Andrew Trick // widened. Widening adds new phis to LoopPhis, inducing another round of 108615832f61775040995bb8aa6056176425bc2c9088Andrew Trick // simplification on the wide IVs. 10872fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick while (!LoopPhis.empty()) { 108815832f61775040995bb8aa6056176425bc2c9088Andrew Trick // Evaluate as many IV expressions as possible before widening any IVs. This 108999a92f67c7ee0d428e18f35c91311a2baba6c03eAndrew Trick // forces SCEV to set no-wrap flags before evaluating sign/zero 109015832f61775040995bb8aa6056176425bc2c9088Andrew Trick // extension. The first time SCEV attempts to normalize sign/zero extension, 109115832f61775040995bb8aa6056176425bc2c9088Andrew Trick // the result becomes final. So for the most predictable results, we delay 109215832f61775040995bb8aa6056176425bc2c9088Andrew Trick // evaluation of sign/zero extend evaluation until needed, and avoid running 109315832f61775040995bb8aa6056176425bc2c9088Andrew Trick // other SCEV based analysis prior to SimplifyIVUsersNoRewrite. 109415832f61775040995bb8aa6056176425bc2c9088Andrew Trick do { 109515832f61775040995bb8aa6056176425bc2c9088Andrew Trick PHINode *CurrIV = LoopPhis.pop_back_val(); 10962fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick 109715832f61775040995bb8aa6056176425bc2c9088Andrew Trick // Information about sign/zero extensions of CurrIV. 109815832f61775040995bb8aa6056176425bc2c9088Andrew Trick WideIVInfo WI; 10992fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick 110015832f61775040995bb8aa6056176425bc2c9088Andrew Trick // Instructions processed by SimplifyIVUsers for CurrIV. 110115832f61775040995bb8aa6056176425bc2c9088Andrew Trick SmallPtrSet<Instruction*,16> Simplified; 11022fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick 110315832f61775040995bb8aa6056176425bc2c9088Andrew Trick // Use-def pairs if IVUsers waiting to be processed for CurrIV. 110415832f61775040995bb8aa6056176425bc2c9088Andrew Trick SmallVector<std::pair<Instruction*, Instruction*>, 8> SimpleIVUsers; 11052fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick 110615832f61775040995bb8aa6056176425bc2c9088Andrew Trick pushIVUsers(CurrIV, Simplified, SimpleIVUsers); 110715832f61775040995bb8aa6056176425bc2c9088Andrew Trick 110815832f61775040995bb8aa6056176425bc2c9088Andrew Trick while (!SimpleIVUsers.empty()) { 110915832f61775040995bb8aa6056176425bc2c9088Andrew Trick Instruction *UseInst, *Operand; 111015832f61775040995bb8aa6056176425bc2c9088Andrew Trick tie(UseInst, Operand) = SimpleIVUsers.pop_back_val(); 111115832f61775040995bb8aa6056176425bc2c9088Andrew Trick 111215832f61775040995bb8aa6056176425bc2c9088Andrew Trick if (EliminateIVUser(UseInst, Operand)) { 111315832f61775040995bb8aa6056176425bc2c9088Andrew Trick pushIVUsers(Operand, Simplified, SimpleIVUsers); 111415832f61775040995bb8aa6056176425bc2c9088Andrew Trick continue; 111515832f61775040995bb8aa6056176425bc2c9088Andrew Trick } 111615832f61775040995bb8aa6056176425bc2c9088Andrew Trick if (CastInst *Cast = dyn_cast<CastInst>(UseInst)) { 111715832f61775040995bb8aa6056176425bc2c9088Andrew Trick bool IsSigned = Cast->getOpcode() == Instruction::SExt; 111815832f61775040995bb8aa6056176425bc2c9088Andrew Trick if (IsSigned || Cast->getOpcode() == Instruction::ZExt) { 111915832f61775040995bb8aa6056176425bc2c9088Andrew Trick CollectExtend(Cast, IsSigned, WI, SE, TD); 112015832f61775040995bb8aa6056176425bc2c9088Andrew Trick } 112115832f61775040995bb8aa6056176425bc2c9088Andrew Trick continue; 112215832f61775040995bb8aa6056176425bc2c9088Andrew Trick } 112315832f61775040995bb8aa6056176425bc2c9088Andrew Trick if (isSimpleIVUser(UseInst, L)) { 112415832f61775040995bb8aa6056176425bc2c9088Andrew Trick pushIVUsers(UseInst, Simplified, SimpleIVUsers); 11252fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick } 11262fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick } 112715832f61775040995bb8aa6056176425bc2c9088Andrew Trick if (WI.WidestNativeType) { 112815832f61775040995bb8aa6056176425bc2c9088Andrew Trick WideIVMap[CurrIV] = WI; 11292fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick } 113015832f61775040995bb8aa6056176425bc2c9088Andrew Trick } while(!LoopPhis.empty()); 113115832f61775040995bb8aa6056176425bc2c9088Andrew Trick 113215832f61775040995bb8aa6056176425bc2c9088Andrew Trick for (std::map<PHINode *, WideIVInfo>::const_iterator I = WideIVMap.begin(), 113315832f61775040995bb8aa6056176425bc2c9088Andrew Trick E = WideIVMap.end(); I != E; ++I) { 113415832f61775040995bb8aa6056176425bc2c9088Andrew Trick WidenIV Widener(I->first, I->second, LI, SE, DT, DeadInsts); 11352fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick if (PHINode *WidePhi = Widener.CreateWideIV(Rewriter)) { 11362fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick Changed = true; 11372fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick LoopPhis.push_back(WidePhi); 11382fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick } 11392fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick } 114015832f61775040995bb8aa6056176425bc2c9088Andrew Trick WideIVMap.clear(); 11412fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick } 11422fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick} 11432fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick 1144c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohmanbool IndVarSimplify::runOnLoop(Loop *L, LPPassManager &LPM) { 1145a52838285b6dce66821f0b272cb3479af8c3edb2Dan Gohman // If LoopSimplify form is not available, stay out of trouble. Some notes: 1146a52838285b6dce66821f0b272cb3479af8c3edb2Dan Gohman // - LSR currently only supports LoopSimplify-form loops. Indvars' 1147a52838285b6dce66821f0b272cb3479af8c3edb2Dan Gohman // canonicalization can be a pessimization without LSR to "clean up" 1148a52838285b6dce66821f0b272cb3479af8c3edb2Dan Gohman // afterwards. 1149a52838285b6dce66821f0b272cb3479af8c3edb2Dan Gohman // - We depend on having a preheader; in particular, 1150a52838285b6dce66821f0b272cb3479af8c3edb2Dan Gohman // Loop::getCanonicalInductionVariable only supports loops with preheaders, 1151a52838285b6dce66821f0b272cb3479af8c3edb2Dan Gohman // and we're in trouble if we can't find the induction variable even when 1152a52838285b6dce66821f0b272cb3479af8c3edb2Dan Gohman // we've manually inserted one. 1153a52838285b6dce66821f0b272cb3479af8c3edb2Dan Gohman if (!L->isLoopSimplifyForm()) 1154a52838285b6dce66821f0b272cb3479af8c3edb2Dan Gohman return false; 1155a52838285b6dce66821f0b272cb3479af8c3edb2Dan Gohman 11562fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick if (!DisableIVRewrite) 11572fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick IU = &getAnalysis<IVUsers>(); 11585ee99979065d75605d150d7e567e4351024aae8fDevang Patel LI = &getAnalysis<LoopInfo>(); 11595ee99979065d75605d150d7e567e4351024aae8fDevang Patel SE = &getAnalysis<ScalarEvolution>(); 1160de53dc03f5c1549f3176e979bbeeac965dfa5cbcDan Gohman DT = &getAnalysis<DominatorTree>(); 116137da40875873d70b83dc08b2803052bec9b68886Andrew Trick TD = getAnalysisIfAvailable<TargetData>(); 116237da40875873d70b83dc08b2803052bec9b68886Andrew Trick 1163b12a754cce0c1d5542af605203a47820edba454dAndrew Trick DeadInsts.clear(); 11645ee99979065d75605d150d7e567e4351024aae8fDevang Patel Changed = false; 116560f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman 11662d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman // If there are any floating-point recurrences, attempt to 116760f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman // transform them to use integer recurrences. 116860f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman RewriteNonIntegerIVs(L); 116960f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman 11700bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *BackedgeTakenCount = SE->getBackedgeTakenCount(L); 11719caed5440d59dac4b388152fe8b993dc0491e5e9Chris Lattner 1172667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman // Create a rewriter object which we'll use to transform the code with. 11735e7645be4c9dd2193add44d30b5fef8036d7a3ceAndrew Trick SCEVExpander Rewriter(*SE, "indvars"); 1174156d460c758463eb407590cba2371857daf27d8aAndrew Trick 1175156d460c758463eb407590cba2371857daf27d8aAndrew Trick // Eliminate redundant IV users. 117615832f61775040995bb8aa6056176425bc2c9088Andrew Trick // 117715832f61775040995bb8aa6056176425bc2c9088Andrew Trick // Simplification works best when run before other consumers of SCEV. We 117815832f61775040995bb8aa6056176425bc2c9088Andrew Trick // attempt to avoid evaluating SCEVs for sign/zero extend operations until 117915832f61775040995bb8aa6056176425bc2c9088Andrew Trick // other expressions involving loop IVs have been evaluated. This helps SCEV 118099a92f67c7ee0d428e18f35c91311a2baba6c03eAndrew Trick // set no-wrap flags before normalizing sign/zero extension. 1181156d460c758463eb407590cba2371857daf27d8aAndrew Trick if (DisableIVRewrite) { 118237da40875873d70b83dc08b2803052bec9b68886Andrew Trick Rewriter.disableCanonicalMode(); 1183156d460c758463eb407590cba2371857daf27d8aAndrew Trick SimplifyIVUsersNoRewrite(L, Rewriter); 1184156d460c758463eb407590cba2371857daf27d8aAndrew Trick } 118537da40875873d70b83dc08b2803052bec9b68886Andrew Trick 118640bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // Check to see if this loop has a computable loop-invariant execution count. 118740bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // If so, this means that we can compute the final value of any expressions 118840bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // that are recurrent in the loop, and substitute the exit values from the 118940bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // loop into any instructions outside of the loop that use the final values of 119040bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // the current expressions. 1191394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner // 119246bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman if (!isa<SCEVCouldNotCompute>(BackedgeTakenCount)) 1193454d26dc43207ec537d843229db6f5e6a302e23dDan Gohman RewriteLoopExitValues(L, Rewriter); 119440bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner 1195f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // Eliminate redundant IV users. 1196156d460c758463eb407590cba2371857daf27d8aAndrew Trick if (!DisableIVRewrite) 11972fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick SimplifyIVUsers(Rewriter); 1198a590b79ee227b93c59f60ce1f54cae7a9ebec7c1Dan Gohman 119981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Compute the type of the largest recurrence expression, and decide whether 120081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // a canonical induction variable should be inserted. 1201f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick const Type *LargestType = 0; 120281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman bool NeedCannIV = false; 120303d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick bool ExpandBECount = canExpandBackedgeTakenCount(L, SE); 12044dfdf242c1917e98f407818eb5b68ae0b4678f26Andrew Trick if (ExpandBECount) { 120581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // If we have a known trip count and a single exit block, we'll be 120681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // rewriting the loop exit test condition below, which requires a 120781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // canonical induction variable. 12084dfdf242c1917e98f407818eb5b68ae0b4678f26Andrew Trick NeedCannIV = true; 12094dfdf242c1917e98f407818eb5b68ae0b4678f26Andrew Trick const Type *Ty = BackedgeTakenCount->getType(); 121003d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick if (DisableIVRewrite) { 121103d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick // In this mode, SimplifyIVUsers may have already widened the IV used by 121203d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick // the backedge test and inserted a Trunc on the compare's operand. Get 121303d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick // the wider type to avoid creating a redundant narrow IV only used by the 121403d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick // loop test. 121503d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick LargestType = getBackedgeIVType(L); 121603d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick } 12174dfdf242c1917e98f407818eb5b68ae0b4678f26Andrew Trick if (!LargestType || 12184dfdf242c1917e98f407818eb5b68ae0b4678f26Andrew Trick SE->getTypeSizeInBits(Ty) > 12194dfdf242c1917e98f407818eb5b68ae0b4678f26Andrew Trick SE->getTypeSizeInBits(LargestType)) 12204dfdf242c1917e98f407818eb5b68ae0b4678f26Andrew Trick LargestType = SE->getEffectiveSCEVType(Ty); 1221f50af088f19f525f3d1026eb61db77e0037a9f43Chris Lattner } 122237da40875873d70b83dc08b2803052bec9b68886Andrew Trick if (!DisableIVRewrite) { 122337da40875873d70b83dc08b2803052bec9b68886Andrew Trick for (IVUsers::const_iterator I = IU->begin(), E = IU->end(); I != E; ++I) { 122437da40875873d70b83dc08b2803052bec9b68886Andrew Trick NeedCannIV = true; 122537da40875873d70b83dc08b2803052bec9b68886Andrew Trick const Type *Ty = 122637da40875873d70b83dc08b2803052bec9b68886Andrew Trick SE->getEffectiveSCEVType(I->getOperandValToReplace()->getType()); 122737da40875873d70b83dc08b2803052bec9b68886Andrew Trick if (!LargestType || 122837da40875873d70b83dc08b2803052bec9b68886Andrew Trick SE->getTypeSizeInBits(Ty) > 1229af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman SE->getTypeSizeInBits(LargestType)) 123037da40875873d70b83dc08b2803052bec9b68886Andrew Trick LargestType = Ty; 123137da40875873d70b83dc08b2803052bec9b68886Andrew Trick } 1232500597a1c39e91a3020587318ed61e737b6c613aChris Lattner } 1233394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner 1234f451cb870efcf9e0302d25ed05f4cac6bb494e42Dan Gohman // Now that we know the largest of the induction variable expressions 123581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // in this loop, insert a canonical induction variable of the largest size. 123643ef3fbae12c7924a25df4563d86084973db9c67Dan Gohman PHINode *IndVar = 0; 123781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (NeedCannIV) { 123885669637139089eaed8def1583ac04266c9654e2Dan Gohman // Check to see if the loop already has any canonical-looking induction 123985669637139089eaed8def1583ac04266c9654e2Dan Gohman // variables. If any are present and wider than the planned canonical 124085669637139089eaed8def1583ac04266c9654e2Dan Gohman // induction variable, temporarily remove them, so that the Rewriter 124185669637139089eaed8def1583ac04266c9654e2Dan Gohman // doesn't attempt to reuse them. 124285669637139089eaed8def1583ac04266c9654e2Dan Gohman SmallVector<PHINode *, 2> OldCannIVs; 124385669637139089eaed8def1583ac04266c9654e2Dan Gohman while (PHINode *OldCannIV = L->getCanonicalInductionVariable()) { 12444d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman if (SE->getTypeSizeInBits(OldCannIV->getType()) > 12454d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman SE->getTypeSizeInBits(LargestType)) 12464d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman OldCannIV->removeFromParent(); 12474d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman else 124885669637139089eaed8def1583ac04266c9654e2Dan Gohman break; 124985669637139089eaed8def1583ac04266c9654e2Dan Gohman OldCannIVs.push_back(OldCannIV); 12504d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman } 12514d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman 1252667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman IndVar = Rewriter.getOrInsertCanonicalInductionVariable(L, LargestType); 12534d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman 1254c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman ++NumInserted; 1255c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman Changed = true; 1256f67ef318aa29e7cc0c7de76349881959936d9eeeDavid Greene DEBUG(dbgs() << "INDVARS: New CanIV: " << *IndVar << '\n'); 12574d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman 12584d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman // Now that the official induction variable is established, reinsert 125985669637139089eaed8def1583ac04266c9654e2Dan Gohman // any old canonical-looking variables after it so that the IR remains 126085669637139089eaed8def1583ac04266c9654e2Dan Gohman // consistent. They will be deleted as part of the dead-PHI deletion at 12614d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman // the end of the pass. 126285669637139089eaed8def1583ac04266c9654e2Dan Gohman while (!OldCannIVs.empty()) { 126385669637139089eaed8def1583ac04266c9654e2Dan Gohman PHINode *OldCannIV = OldCannIVs.pop_back_val(); 126485669637139089eaed8def1583ac04266c9654e2Dan Gohman OldCannIV->insertBefore(L->getHeader()->getFirstNonPHI()); 126585669637139089eaed8def1583ac04266c9654e2Dan Gohman } 1266d19534add90a2a894af61523b830887097bb780bDan Gohman } 126740bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner 1268c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman // If we have a trip count expression, rewrite the loop's exit condition 1269c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman // using it. We can currently only handle loops with a single exit. 127081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman ICmpInst *NewICmp = 0; 12714dfdf242c1917e98f407818eb5b68ae0b4678f26Andrew Trick if (ExpandBECount) { 127203d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick assert(canExpandBackedgeTakenCount(L, SE) && 12734dfdf242c1917e98f407818eb5b68ae0b4678f26Andrew Trick "canonical IV disrupted BackedgeTaken expansion"); 127481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman assert(NeedCannIV && 127581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman "LinearFunctionTestReplace requires a canonical induction variable"); 12764dfdf242c1917e98f407818eb5b68ae0b4678f26Andrew Trick NewICmp = LinearFunctionTestReplace(L, BackedgeTakenCount, IndVar, 12774dfdf242c1917e98f407818eb5b68ae0b4678f26Andrew Trick Rewriter); 127881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman } 1279b12a754cce0c1d5542af605203a47820edba454dAndrew Trick // Rewrite IV-derived expressions. 128037da40875873d70b83dc08b2803052bec9b68886Andrew Trick if (!DisableIVRewrite) 128137da40875873d70b83dc08b2803052bec9b68886Andrew Trick RewriteIVExpressions(L, Rewriter); 1282fcb81f5f4cbac61851b7dec403961cf88e614aa1Chris Lattner 1283b12a754cce0c1d5542af605203a47820edba454dAndrew Trick // Clear the rewriter cache, because values that are in the rewriter's cache 1284b12a754cce0c1d5542af605203a47820edba454dAndrew Trick // can be deleted in the loop below, causing the AssertingVH in the cache to 1285b12a754cce0c1d5542af605203a47820edba454dAndrew Trick // trigger. 1286b12a754cce0c1d5542af605203a47820edba454dAndrew Trick Rewriter.clear(); 1287b12a754cce0c1d5542af605203a47820edba454dAndrew Trick 1288b12a754cce0c1d5542af605203a47820edba454dAndrew Trick // Now that we're done iterating through lists, clean up any instructions 1289b12a754cce0c1d5542af605203a47820edba454dAndrew Trick // which are now dead. 1290b12a754cce0c1d5542af605203a47820edba454dAndrew Trick while (!DeadInsts.empty()) 1291b12a754cce0c1d5542af605203a47820edba454dAndrew Trick if (Instruction *Inst = 1292b12a754cce0c1d5542af605203a47820edba454dAndrew Trick dyn_cast_or_null<Instruction>(&*DeadInsts.pop_back_val())) 1293b12a754cce0c1d5542af605203a47820edba454dAndrew Trick RecursivelyDeleteTriviallyDeadInstructions(Inst); 1294b12a754cce0c1d5542af605203a47820edba454dAndrew Trick 1295667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman // The Rewriter may not be used from this point on. 12963d431384f05c9defc84f36eafe220415cc12ee93Torok Edwin 129781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Loop-invariant instructions in the preheader that aren't used in the 129881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // loop may be sunk below the loop to reduce register pressure. 1299667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman SinkUnusedInvariants(L); 130081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 130181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // For completeness, inform IVUsers of the IV use in the newly-created 130281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // loop exit test instruction. 13032fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick if (NewICmp && IU) 13044417e537b65c14b378aeca75b2773582dd102f63Andrew Trick IU->AddUsersIfInteresting(cast<Instruction>(NewICmp->getOperand(0))); 130581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 130681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Clean up dead instructions. 13079fff2187a21f765ed87a25c48552a6942450f3e2Dan Gohman Changed |= DeleteDeadPHIs(L->getHeader()); 130881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Check a post-condition. 1309bbf81d88116d23fb0776412b5916f7d0b8b3ca7eDan Gohman assert(L->isLCSSAForm(*DT) && "Indvars did not leave the loop in lcssa form!"); 131081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman return Changed; 131181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman} 131281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 1313448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman// FIXME: It is an extremely bad idea to indvar substitute anything more 1314448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman// complex than affine induction variables. Doing so will put expensive 1315448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman// polynomial evaluations inside of the loop, and the str reduction pass 1316448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman// currently can only reduce affine polynomials. For now just disable 1317448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman// indvar subst on anything more complex than an affine addrec, unless 1318448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman// it can be expanded to a trivial value. 131917ead4ff4baceb2c5503f233d0288d363ae44165Dan Gohmanstatic bool isSafe(const SCEV *S, const Loop *L, ScalarEvolution *SE) { 1320448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman // Loop-invariant values are safe. 132117ead4ff4baceb2c5503f233d0288d363ae44165Dan Gohman if (SE->isLoopInvariant(S, L)) return true; 1322448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman 1323448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman // Affine addrecs are safe. Non-affine are not, because LSR doesn't know how 1324448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman // to transform them into efficient code. 1325448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) 1326448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman return AR->isAffine(); 1327448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman 1328448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman // An add is safe it all its operands are safe. 1329448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman if (const SCEVCommutativeExpr *Commutative = dyn_cast<SCEVCommutativeExpr>(S)) { 1330448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman for (SCEVCommutativeExpr::op_iterator I = Commutative->op_begin(), 1331448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman E = Commutative->op_end(); I != E; ++I) 133217ead4ff4baceb2c5503f233d0288d363ae44165Dan Gohman if (!isSafe(*I, L, SE)) return false; 1333448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman return true; 1334448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman } 1335ead71d59a7685fbbbb92162556680abd9001d37bAndrew Trick 1336448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman // A cast is safe if its operand is. 1337448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman if (const SCEVCastExpr *C = dyn_cast<SCEVCastExpr>(S)) 133817ead4ff4baceb2c5503f233d0288d363ae44165Dan Gohman return isSafe(C->getOperand(), L, SE); 1339448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman 1340448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman // A udiv is safe if its operands are. 1341448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman if (const SCEVUDivExpr *UD = dyn_cast<SCEVUDivExpr>(S)) 134217ead4ff4baceb2c5503f233d0288d363ae44165Dan Gohman return isSafe(UD->getLHS(), L, SE) && 134317ead4ff4baceb2c5503f233d0288d363ae44165Dan Gohman isSafe(UD->getRHS(), L, SE); 1344448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman 1345448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman // SCEVUnknown is always safe. 1346448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman if (isa<SCEVUnknown>(S)) 1347448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman return true; 1348448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman 1349448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman // Nothing else is safe. 1350448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman return false; 1351448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman} 1352448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman 1353454d26dc43207ec537d843229db6f5e6a302e23dDan Gohmanvoid IndVarSimplify::RewriteIVExpressions(Loop *L, SCEVExpander &Rewriter) { 135481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Rewrite all induction variable expressions in terms of the canonical 135581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // induction variable. 135681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // 135781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // If there were induction variables of other sizes or offsets, manually 135881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // add the offsets to the primary induction variable and cast, avoiding 135981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // the need for the code evaluation methods to insert induction variables 136081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // of different sizes. 1361572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman for (IVUsers::iterator UI = IU->begin(), E = IU->end(); UI != E; ++UI) { 1362572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman Value *Op = UI->getOperandValToReplace(); 1363572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman const Type *UseTy = Op->getType(); 1364572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman Instruction *User = UI->getUser(); 1365572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman 1366572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // Compute the final addrec to expand into code. 1367572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman const SCEV *AR = IU->getReplacementExpr(*UI); 1368572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman 1369572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // Evaluate the expression out of the loop, if possible. 1370572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman if (!L->contains(UI->getUser())) { 1371572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman const SCEV *ExitVal = SE->getSCEVAtScope(AR, L->getParentLoop()); 137217ead4ff4baceb2c5503f233d0288d363ae44165Dan Gohman if (SE->isLoopInvariant(ExitVal, L)) 1373572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman AR = ExitVal; 137481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman } 1375572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman 1376572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // FIXME: It is an extremely bad idea to indvar substitute anything more 1377572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // complex than affine induction variables. Doing so will put expensive 1378572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // polynomial evaluations inside of the loop, and the str reduction pass 1379572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // currently can only reduce affine polynomials. For now just disable 1380572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // indvar subst on anything more complex than an affine addrec, unless 1381572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // it can be expanded to a trivial value. 138217ead4ff4baceb2c5503f233d0288d363ae44165Dan Gohman if (!isSafe(AR, L, SE)) 1383572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman continue; 1384572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman 1385572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // Determine the insertion point for this user. By default, insert 1386572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // immediately before the user. The SCEVExpander class will automatically 1387572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // hoist loop invariants out of the loop. For PHI nodes, there may be 1388572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // multiple uses, so compute the nearest common dominator for the 1389572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // incoming blocks. 1390572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman Instruction *InsertPt = User; 1391572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman if (PHINode *PHI = dyn_cast<PHINode>(InsertPt)) 1392572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i) 1393572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman if (PHI->getIncomingValue(i) == Op) { 1394572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman if (InsertPt == User) 1395572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman InsertPt = PHI->getIncomingBlock(i)->getTerminator(); 1396572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman else 1397572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman InsertPt = 1398572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman DT->findNearestCommonDominator(InsertPt->getParent(), 1399572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman PHI->getIncomingBlock(i)) 1400572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman ->getTerminator(); 1401572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman } 1402572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman 1403572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // Now expand it into actual Instructions and patch it into place. 1404572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman Value *NewVal = Rewriter.expandCodeFor(AR, UseTy, InsertPt); 1405572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman 1406b12a754cce0c1d5542af605203a47820edba454dAndrew Trick DEBUG(dbgs() << "INDVARS: Rewrote IV '" << *AR << "' " << *Op << '\n' 1407b12a754cce0c1d5542af605203a47820edba454dAndrew Trick << " into = " << *NewVal << "\n"); 1408b12a754cce0c1d5542af605203a47820edba454dAndrew Trick 1409b12a754cce0c1d5542af605203a47820edba454dAndrew Trick if (!isValidRewrite(Op, NewVal)) { 1410b12a754cce0c1d5542af605203a47820edba454dAndrew Trick DeadInsts.push_back(NewVal); 1411b12a754cce0c1d5542af605203a47820edba454dAndrew Trick continue; 1412b12a754cce0c1d5542af605203a47820edba454dAndrew Trick } 1413d7bfd0028b273f2e3935e8c7ff95db6fa2b21789Dan Gohman // Inform ScalarEvolution that this value is changing. The change doesn't 1414d7bfd0028b273f2e3935e8c7ff95db6fa2b21789Dan Gohman // affect its value, but it does potentially affect which use lists the 1415d7bfd0028b273f2e3935e8c7ff95db6fa2b21789Dan Gohman // value will be on after the replacement, which affects ScalarEvolution's 1416d7bfd0028b273f2e3935e8c7ff95db6fa2b21789Dan Gohman // ability to walk use lists and drop dangling pointers when a value is 1417d7bfd0028b273f2e3935e8c7ff95db6fa2b21789Dan Gohman // deleted. 1418d7bfd0028b273f2e3935e8c7ff95db6fa2b21789Dan Gohman SE->forgetValue(User); 1419d7bfd0028b273f2e3935e8c7ff95db6fa2b21789Dan Gohman 1420572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // Patch the new value into place. 1421572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman if (Op->hasName()) 1422572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman NewVal->takeName(Op); 1423a098bf1239ca1769c93de52324d2b73adedad7b8Devang Patel if (Instruction *NewValI = dyn_cast<Instruction>(NewVal)) 1424a098bf1239ca1769c93de52324d2b73adedad7b8Devang Patel NewValI->setDebugLoc(User->getDebugLoc()); 1425572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman User->replaceUsesOfWith(Op, NewVal); 1426572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman UI->setOperandValToReplace(NewVal); 1427b12a754cce0c1d5542af605203a47820edba454dAndrew Trick 1428572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman ++NumRemoved; 1429572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman Changed = true; 1430572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman 1431572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // The old value may be dead now. 1432572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman DeadInsts.push_back(Op); 1433500597a1c39e91a3020587318ed61e737b6c613aChris Lattner } 143481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman} 143581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 143681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman/// If there's a single exit block, sink any loop-invariant values that 143781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman/// were defined in the preheader but not used inside the loop into the 143881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman/// exit block to reduce register pressure in the loop. 1439667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohmanvoid IndVarSimplify::SinkUnusedInvariants(Loop *L) { 144081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman BasicBlock *ExitBlock = L->getExitBlock(); 144181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (!ExitBlock) return; 144281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 144381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman BasicBlock *Preheader = L->getLoopPreheader(); 144403e896bd6073efc4523d8bcd0239d6ed62126db7Dan Gohman if (!Preheader) return; 144503e896bd6073efc4523d8bcd0239d6ed62126db7Dan Gohman 144603e896bd6073efc4523d8bcd0239d6ed62126db7Dan Gohman Instruction *InsertPt = ExitBlock->getFirstNonPHI(); 144781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman BasicBlock::iterator I = Preheader->getTerminator(); 144881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman while (I != Preheader->begin()) { 144981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman --I; 1450667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman // New instructions were inserted at the end of the preheader. 1451667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman if (isa<PHINode>(I)) 145281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman break; 145387a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling 14540c77db32dd8ae10b5a26d60718dbe03dc2745888Eli Friedman // Don't move instructions which might have side effects, since the side 145587a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling // effects need to complete before instructions inside the loop. Also don't 145687a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling // move instructions which might read memory, since the loop may modify 145787a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling // memory. Note that it's okay if the instruction might have undefined 145887a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling // behavior: LoopSimplify guarantees that the preheader dominates the exit 145987a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling // block. 14600c77db32dd8ae10b5a26d60718dbe03dc2745888Eli Friedman if (I->mayHaveSideEffects() || I->mayReadFromMemory()) 1461667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman continue; 146287a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling 14637b9f6b1b21bc0b06f3c72beae51e9db631319503Devang Patel // Skip debug info intrinsics. 14647b9f6b1b21bc0b06f3c72beae51e9db631319503Devang Patel if (isa<DbgInfoIntrinsic>(I)) 14657b9f6b1b21bc0b06f3c72beae51e9db631319503Devang Patel continue; 146687a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling 146776f497a351c562f366b5e93c27d3f1652fb48ff4Dan Gohman // Don't sink static AllocaInsts out of the entry block, which would 146876f497a351c562f366b5e93c27d3f1652fb48ff4Dan Gohman // turn them into dynamic allocas! 146976f497a351c562f366b5e93c27d3f1652fb48ff4Dan Gohman if (AllocaInst *AI = dyn_cast<AllocaInst>(I)) 147076f497a351c562f366b5e93c27d3f1652fb48ff4Dan Gohman if (AI->isStaticAlloca()) 147176f497a351c562f366b5e93c27d3f1652fb48ff4Dan Gohman continue; 147287a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling 147381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Determine if there is a use in or before the loop (direct or 147481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // otherwise). 147581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman bool UsedInLoop = false; 147681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman for (Value::use_iterator UI = I->use_begin(), UE = I->use_end(); 147781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman UI != UE; ++UI) { 14787656018c2268285907cfdc106071462a01a73878Gabor Greif User *U = *UI; 14797656018c2268285907cfdc106071462a01a73878Gabor Greif BasicBlock *UseBB = cast<Instruction>(U)->getParent(); 14807656018c2268285907cfdc106071462a01a73878Gabor Greif if (PHINode *P = dyn_cast<PHINode>(U)) { 148181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman unsigned i = 148281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman PHINode::getIncomingValueNumForOperand(UI.getOperandNo()); 148381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman UseBB = P->getIncomingBlock(i); 148481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman } 148581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (UseBB == Preheader || L->contains(UseBB)) { 148681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman UsedInLoop = true; 148781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman break; 148881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman } 148981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman } 149087a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling 149181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // If there is, the def must remain in the preheader. 149281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (UsedInLoop) 149381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman continue; 149487a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling 149581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Otherwise, sink it to the exit block. 149681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman Instruction *ToMove = I; 149781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman bool Done = false; 149887a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling 149987a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling if (I != Preheader->begin()) { 150087a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling // Skip debug info intrinsics. 150187a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling do { 150287a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling --I; 150387a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling } while (isa<DbgInfoIntrinsic>(I) && I != Preheader->begin()); 150487a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling 150587a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling if (isa<DbgInfoIntrinsic>(I) && I == Preheader->begin()) 150687a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling Done = true; 150787a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling } else { 150881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman Done = true; 150987a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling } 151087a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling 1511667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman ToMove->moveBefore(InsertPt); 151287a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling if (Done) break; 1513667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman InsertPt = ToMove; 151481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman } 151581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman} 151681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 1517bbb91498da1a4dc77332bf93d7c13060f0c63a70Chris Lattner/// ConvertToSInt - Convert APF to an integer, if possible. 1518bbb91498da1a4dc77332bf93d7c13060f0c63a70Chris Lattnerstatic bool ConvertToSInt(const APFloat &APF, int64_t &IntVal) { 1519cd40233429fce385ae4b22301ce705273a6951a1Devang Patel bool isExact = false; 1520794a7dbce030f93315b1305f83a374232f09bba5Evan Cheng if (&APF.getSemantics() == &APFloat::PPCDoubleDouble) 1521794a7dbce030f93315b1305f83a374232f09bba5Evan Cheng return false; 1522bbb91498da1a4dc77332bf93d7c13060f0c63a70Chris Lattner // See if we can convert this to an int64_t 1523bbb91498da1a4dc77332bf93d7c13060f0c63a70Chris Lattner uint64_t UIntVal; 1524bbb91498da1a4dc77332bf93d7c13060f0c63a70Chris Lattner if (APF.convertToInteger(&UIntVal, 64, true, APFloat::rmTowardZero, 1525bbb91498da1a4dc77332bf93d7c13060f0c63a70Chris Lattner &isExact) != APFloat::opOK || !isExact) 1526cd40233429fce385ae4b22301ce705273a6951a1Devang Patel return false; 1527bbb91498da1a4dc77332bf93d7c13060f0c63a70Chris Lattner IntVal = UIntVal; 1528cd40233429fce385ae4b22301ce705273a6951a1Devang Patel return true; 1529cd40233429fce385ae4b22301ce705273a6951a1Devang Patel} 1530cd40233429fce385ae4b22301ce705273a6951a1Devang Patel 153158d43d4a41b21085c063bdd21a2abb68056e2a6fDevang Patel/// HandleFloatingPointIV - If the loop has floating induction variable 153258d43d4a41b21085c063bdd21a2abb68056e2a6fDevang Patel/// then insert corresponding integer induction variable if possible. 153384e3515974407a606289c6e762a0419723b7918fDevang Patel/// For example, 153484e3515974407a606289c6e762a0419723b7918fDevang Patel/// for(double i = 0; i < 10000; ++i) 153584e3515974407a606289c6e762a0419723b7918fDevang Patel/// bar(i) 153684e3515974407a606289c6e762a0419723b7918fDevang Patel/// is converted into 153784e3515974407a606289c6e762a0419723b7918fDevang Patel/// for(int i = 0; i < 10000; ++i) 153884e3515974407a606289c6e762a0419723b7918fDevang Patel/// bar((double)i); 153984e3515974407a606289c6e762a0419723b7918fDevang Patel/// 1540c91961e31b2a1cae655928e20b83cb6a457fdcd4Chris Lattnervoid IndVarSimplify::HandleFloatingPointIV(Loop *L, PHINode *PN) { 1541c91961e31b2a1cae655928e20b83cb6a457fdcd4Chris Lattner unsigned IncomingEdge = L->contains(PN->getIncomingBlock(0)); 154284e3515974407a606289c6e762a0419723b7918fDevang Patel unsigned BackEdge = IncomingEdge^1; 1543cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 154484e3515974407a606289c6e762a0419723b7918fDevang Patel // Check incoming value. 1545c4f7e8061de19172d4c3f70a80447505b792e450Chris Lattner ConstantFP *InitValueVal = 1546c91961e31b2a1cae655928e20b83cb6a457fdcd4Chris Lattner dyn_cast<ConstantFP>(PN->getIncomingValue(IncomingEdge)); 154796fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner 1548bbb91498da1a4dc77332bf93d7c13060f0c63a70Chris Lattner int64_t InitValue; 154996fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner if (!InitValueVal || !ConvertToSInt(InitValueVal->getValueAPF(), InitValue)) 1550cd40233429fce385ae4b22301ce705273a6951a1Devang Patel return; 1551cd40233429fce385ae4b22301ce705273a6951a1Devang Patel 1552c91961e31b2a1cae655928e20b83cb6a457fdcd4Chris Lattner // Check IV increment. Reject this PN if increment operation is not 1553cd40233429fce385ae4b22301ce705273a6951a1Devang Patel // an add or increment value can not be represented by an integer. 1554cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman BinaryOperator *Incr = 1555c91961e31b2a1cae655928e20b83cb6a457fdcd4Chris Lattner dyn_cast<BinaryOperator>(PN->getIncomingValue(BackEdge)); 155607aa76ad939e053c1992a03cbcb16aff74f26651Chris Lattner if (Incr == 0 || Incr->getOpcode() != Instruction::FAdd) return; 1557ead71d59a7685fbbbb92162556680abd9001d37bAndrew Trick 155807aa76ad939e053c1992a03cbcb16aff74f26651Chris Lattner // If this is not an add of the PHI with a constantfp, or if the constant fp 155907aa76ad939e053c1992a03cbcb16aff74f26651Chris Lattner // is not an integer, bail out. 1560c4f7e8061de19172d4c3f70a80447505b792e450Chris Lattner ConstantFP *IncValueVal = dyn_cast<ConstantFP>(Incr->getOperand(1)); 156196fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner int64_t IncValue; 1562c91961e31b2a1cae655928e20b83cb6a457fdcd4Chris Lattner if (IncValueVal == 0 || Incr->getOperand(0) != PN || 156396fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner !ConvertToSInt(IncValueVal->getValueAPF(), IncValue)) 1564cd40233429fce385ae4b22301ce705273a6951a1Devang Patel return; 1565cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 1566c91961e31b2a1cae655928e20b83cb6a457fdcd4Chris Lattner // Check Incr uses. One user is PN and the other user is an exit condition 156707aa76ad939e053c1992a03cbcb16aff74f26651Chris Lattner // used by the conditional terminator. 156884e3515974407a606289c6e762a0419723b7918fDevang Patel Value::use_iterator IncrUse = Incr->use_begin(); 156996f1d8ebdd33b3f9bdb3b1163f36072c68599f42Gabor Greif Instruction *U1 = cast<Instruction>(*IncrUse++); 157084e3515974407a606289c6e762a0419723b7918fDevang Patel if (IncrUse == Incr->use_end()) return; 157196f1d8ebdd33b3f9bdb3b1163f36072c68599f42Gabor Greif Instruction *U2 = cast<Instruction>(*IncrUse++); 157284e3515974407a606289c6e762a0419723b7918fDevang Patel if (IncrUse != Incr->use_end()) return; 1573cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 157407aa76ad939e053c1992a03cbcb16aff74f26651Chris Lattner // Find exit condition, which is an fcmp. If it doesn't exist, or if it isn't 157507aa76ad939e053c1992a03cbcb16aff74f26651Chris Lattner // only used by a branch, we can't transform it. 1576ca703bd56ba1f717b3735c6889334c319ca005b1Chris Lattner FCmpInst *Compare = dyn_cast<FCmpInst>(U1); 1577ca703bd56ba1f717b3735c6889334c319ca005b1Chris Lattner if (!Compare) 1578ca703bd56ba1f717b3735c6889334c319ca005b1Chris Lattner Compare = dyn_cast<FCmpInst>(U2); 1579ca703bd56ba1f717b3735c6889334c319ca005b1Chris Lattner if (Compare == 0 || !Compare->hasOneUse() || 1580ca703bd56ba1f717b3735c6889334c319ca005b1Chris Lattner !isa<BranchInst>(Compare->use_back())) 158107aa76ad939e053c1992a03cbcb16aff74f26651Chris Lattner return; 1582ead71d59a7685fbbbb92162556680abd9001d37bAndrew Trick 1583ca703bd56ba1f717b3735c6889334c319ca005b1Chris Lattner BranchInst *TheBr = cast<BranchInst>(Compare->use_back()); 158484e3515974407a606289c6e762a0419723b7918fDevang Patel 1585d52c072777b9c9a9df9041b8b6cd199df7e43394Chris Lattner // We need to verify that the branch actually controls the iteration count 1586d52c072777b9c9a9df9041b8b6cd199df7e43394Chris Lattner // of the loop. If not, the new IV can overflow and no one will notice. 1587d52c072777b9c9a9df9041b8b6cd199df7e43394Chris Lattner // The branch block must be in the loop and one of the successors must be out 1588d52c072777b9c9a9df9041b8b6cd199df7e43394Chris Lattner // of the loop. 1589d52c072777b9c9a9df9041b8b6cd199df7e43394Chris Lattner assert(TheBr->isConditional() && "Can't use fcmp if not conditional"); 1590d52c072777b9c9a9df9041b8b6cd199df7e43394Chris Lattner if (!L->contains(TheBr->getParent()) || 1591d52c072777b9c9a9df9041b8b6cd199df7e43394Chris Lattner (L->contains(TheBr->getSuccessor(0)) && 1592d52c072777b9c9a9df9041b8b6cd199df7e43394Chris Lattner L->contains(TheBr->getSuccessor(1)))) 1593d52c072777b9c9a9df9041b8b6cd199df7e43394Chris Lattner return; 1594ead71d59a7685fbbbb92162556680abd9001d37bAndrew Trick 1595ead71d59a7685fbbbb92162556680abd9001d37bAndrew Trick 159607aa76ad939e053c1992a03cbcb16aff74f26651Chris Lattner // If it isn't a comparison with an integer-as-fp (the exit value), we can't 159707aa76ad939e053c1992a03cbcb16aff74f26651Chris Lattner // transform it. 1598ca703bd56ba1f717b3735c6889334c319ca005b1Chris Lattner ConstantFP *ExitValueVal = dyn_cast<ConstantFP>(Compare->getOperand(1)); 1599bbb91498da1a4dc77332bf93d7c13060f0c63a70Chris Lattner int64_t ExitValue; 1600bbb91498da1a4dc77332bf93d7c13060f0c63a70Chris Lattner if (ExitValueVal == 0 || 1601bbb91498da1a4dc77332bf93d7c13060f0c63a70Chris Lattner !ConvertToSInt(ExitValueVal->getValueAPF(), ExitValue)) 160284e3515974407a606289c6e762a0419723b7918fDevang Patel return; 1603ead71d59a7685fbbbb92162556680abd9001d37bAndrew Trick 160484e3515974407a606289c6e762a0419723b7918fDevang Patel // Find new predicate for integer comparison. 160584e3515974407a606289c6e762a0419723b7918fDevang Patel CmpInst::Predicate NewPred = CmpInst::BAD_ICMP_PREDICATE; 1606ca703bd56ba1f717b3735c6889334c319ca005b1Chris Lattner switch (Compare->getPredicate()) { 1607c4f7e8061de19172d4c3f70a80447505b792e450Chris Lattner default: return; // Unknown comparison. 160884e3515974407a606289c6e762a0419723b7918fDevang Patel case CmpInst::FCMP_OEQ: 1609c4f7e8061de19172d4c3f70a80447505b792e450Chris Lattner case CmpInst::FCMP_UEQ: NewPred = CmpInst::ICMP_EQ; break; 161096fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner case CmpInst::FCMP_ONE: 161196fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner case CmpInst::FCMP_UNE: NewPred = CmpInst::ICMP_NE; break; 161284e3515974407a606289c6e762a0419723b7918fDevang Patel case CmpInst::FCMP_OGT: 1613a40e4a0c8abbfe55d25a77e4e98508e43ed1c3aeChris Lattner case CmpInst::FCMP_UGT: NewPred = CmpInst::ICMP_SGT; break; 161484e3515974407a606289c6e762a0419723b7918fDevang Patel case CmpInst::FCMP_OGE: 1615a40e4a0c8abbfe55d25a77e4e98508e43ed1c3aeChris Lattner case CmpInst::FCMP_UGE: NewPred = CmpInst::ICMP_SGE; break; 161684e3515974407a606289c6e762a0419723b7918fDevang Patel case CmpInst::FCMP_OLT: 161743b85273ee11536c81b14dca0114cd8b9407db8eChris Lattner case CmpInst::FCMP_ULT: NewPred = CmpInst::ICMP_SLT; break; 161884e3515974407a606289c6e762a0419723b7918fDevang Patel case CmpInst::FCMP_OLE: 161943b85273ee11536c81b14dca0114cd8b9407db8eChris Lattner case CmpInst::FCMP_ULE: NewPred = CmpInst::ICMP_SLE; break; 162058d43d4a41b21085c063bdd21a2abb68056e2a6fDevang Patel } 1621ead71d59a7685fbbbb92162556680abd9001d37bAndrew Trick 162296fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner // We convert the floating point induction variable to a signed i32 value if 162396fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner // we can. This is only safe if the comparison will not overflow in a way 162496fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner // that won't be trapped by the integer equivalent operations. Check for this 162596fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner // now. 162696fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner // TODO: We could use i64 if it is native and the range requires it. 1627ead71d59a7685fbbbb92162556680abd9001d37bAndrew Trick 162896fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner // The start/stride/exit values must all fit in signed i32. 162996fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner if (!isInt<32>(InitValue) || !isInt<32>(IncValue) || !isInt<32>(ExitValue)) 163096fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner return; 163196fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner 163296fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner // If not actually striding (add x, 0.0), avoid touching the code. 163396fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner if (IncValue == 0) 163496fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner return; 163596fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner 163696fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner // Positive and negative strides have different safety conditions. 163796fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner if (IncValue > 0) { 163896fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner // If we have a positive stride, we require the init to be less than the 163996fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner // exit value and an equality or less than comparison. 164096fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner if (InitValue >= ExitValue || 164196fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner NewPred == CmpInst::ICMP_SGT || NewPred == CmpInst::ICMP_SGE) 164296fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner return; 1643ead71d59a7685fbbbb92162556680abd9001d37bAndrew Trick 164496fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner uint32_t Range = uint32_t(ExitValue-InitValue); 164596fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner if (NewPred == CmpInst::ICMP_SLE) { 164696fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner // Normalize SLE -> SLT, check for infinite loop. 164796fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner if (++Range == 0) return; // Range overflows. 164896fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner } 1649ead71d59a7685fbbbb92162556680abd9001d37bAndrew Trick 165096fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner unsigned Leftover = Range % uint32_t(IncValue); 1651ead71d59a7685fbbbb92162556680abd9001d37bAndrew Trick 165296fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner // If this is an equality comparison, we require that the strided value 165396fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner // exactly land on the exit value, otherwise the IV condition will wrap 165496fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner // around and do things the fp IV wouldn't. 165596fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner if ((NewPred == CmpInst::ICMP_EQ || NewPred == CmpInst::ICMP_NE) && 165696fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner Leftover != 0) 165796fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner return; 1658ead71d59a7685fbbbb92162556680abd9001d37bAndrew Trick 165996fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner // If the stride would wrap around the i32 before exiting, we can't 166096fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner // transform the IV. 166196fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner if (Leftover != 0 && int32_t(ExitValue+IncValue) < ExitValue) 166296fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner return; 1663ead71d59a7685fbbbb92162556680abd9001d37bAndrew Trick 166496fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner } else { 166596fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner // If we have a negative stride, we require the init to be greater than the 166696fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner // exit value and an equality or greater than comparison. 166796fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner if (InitValue >= ExitValue || 166896fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner NewPred == CmpInst::ICMP_SLT || NewPred == CmpInst::ICMP_SLE) 166996fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner return; 1670ead71d59a7685fbbbb92162556680abd9001d37bAndrew Trick 167196fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner uint32_t Range = uint32_t(InitValue-ExitValue); 167296fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner if (NewPred == CmpInst::ICMP_SGE) { 167396fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner // Normalize SGE -> SGT, check for infinite loop. 167496fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner if (++Range == 0) return; // Range overflows. 167596fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner } 1676ead71d59a7685fbbbb92162556680abd9001d37bAndrew Trick 167796fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner unsigned Leftover = Range % uint32_t(-IncValue); 1678ead71d59a7685fbbbb92162556680abd9001d37bAndrew Trick 167996fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner // If this is an equality comparison, we require that the strided value 168096fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner // exactly land on the exit value, otherwise the IV condition will wrap 168196fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner // around and do things the fp IV wouldn't. 168296fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner if ((NewPred == CmpInst::ICMP_EQ || NewPred == CmpInst::ICMP_NE) && 168396fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner Leftover != 0) 168496fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner return; 1685ead71d59a7685fbbbb92162556680abd9001d37bAndrew Trick 168696fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner // If the stride would wrap around the i32 before exiting, we can't 168796fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner // transform the IV. 168896fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner if (Leftover != 0 && int32_t(ExitValue+IncValue) > ExitValue) 168996fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner return; 169096fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner } 1691ead71d59a7685fbbbb92162556680abd9001d37bAndrew Trick 169296fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner const IntegerType *Int32Ty = Type::getInt32Ty(PN->getContext()); 1693cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 1694bbb91498da1a4dc77332bf93d7c13060f0c63a70Chris Lattner // Insert new integer induction variable. 16953ecfc861b4365f341c5c969b40e1afccde676e6fJay Foad PHINode *NewPHI = PHINode::Create(Int32Ty, 2, PN->getName()+".int", PN); 1696c4f7e8061de19172d4c3f70a80447505b792e450Chris Lattner NewPHI->addIncoming(ConstantInt::get(Int32Ty, InitValue), 1697c91961e31b2a1cae655928e20b83cb6a457fdcd4Chris Lattner PN->getIncomingBlock(IncomingEdge)); 169884e3515974407a606289c6e762a0419723b7918fDevang Patel 1699c4f7e8061de19172d4c3f70a80447505b792e450Chris Lattner Value *NewAdd = 170096fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner BinaryOperator::CreateAdd(NewPHI, ConstantInt::get(Int32Ty, IncValue), 1701c4f7e8061de19172d4c3f70a80447505b792e450Chris Lattner Incr->getName()+".int", Incr); 1702c91961e31b2a1cae655928e20b83cb6a457fdcd4Chris Lattner NewPHI->addIncoming(NewAdd, PN->getIncomingBlock(BackEdge)); 170384e3515974407a606289c6e762a0419723b7918fDevang Patel 1704ca703bd56ba1f717b3735c6889334c319ca005b1Chris Lattner ICmpInst *NewCompare = new ICmpInst(TheBr, NewPred, NewAdd, 1705ca703bd56ba1f717b3735c6889334c319ca005b1Chris Lattner ConstantInt::get(Int32Ty, ExitValue), 1706ca703bd56ba1f717b3735c6889334c319ca005b1Chris Lattner Compare->getName()); 1707cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 1708c91961e31b2a1cae655928e20b83cb6a457fdcd4Chris Lattner // In the following deletions, PN may become dead and may be deleted. 170981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Use a WeakVH to observe whether this happens. 1710c91961e31b2a1cae655928e20b83cb6a457fdcd4Chris Lattner WeakVH WeakPH = PN; 171181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 1712ca703bd56ba1f717b3735c6889334c319ca005b1Chris Lattner // Delete the old floating point exit comparison. The branch starts using the 1713ca703bd56ba1f717b3735c6889334c319ca005b1Chris Lattner // new comparison. 1714ca703bd56ba1f717b3735c6889334c319ca005b1Chris Lattner NewCompare->takeName(Compare); 1715ca703bd56ba1f717b3735c6889334c319ca005b1Chris Lattner Compare->replaceAllUsesWith(NewCompare); 1716ca703bd56ba1f717b3735c6889334c319ca005b1Chris Lattner RecursivelyDeleteTriviallyDeadInstructions(Compare); 1717cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 1718ca703bd56ba1f717b3735c6889334c319ca005b1Chris Lattner // Delete the old floating point increment. 17199e9a0d5fc26878e51a58a8b57900fcbf952c2691Owen Anderson Incr->replaceAllUsesWith(UndefValue::get(Incr->getType())); 172081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman RecursivelyDeleteTriviallyDeadInstructions(Incr); 172181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 172270c0d4f7eb9c14bccc8a585be4086712e46bfbdbChris Lattner // If the FP induction variable still has uses, this is because something else 172370c0d4f7eb9c14bccc8a585be4086712e46bfbdbChris Lattner // in the loop uses its value. In order to canonicalize the induction 172470c0d4f7eb9c14bccc8a585be4086712e46bfbdbChris Lattner // variable, we chose to eliminate the IV and rewrite it in terms of an 172570c0d4f7eb9c14bccc8a585be4086712e46bfbdbChris Lattner // int->fp cast. 172670c0d4f7eb9c14bccc8a585be4086712e46bfbdbChris Lattner // 172770c0d4f7eb9c14bccc8a585be4086712e46bfbdbChris Lattner // We give preference to sitofp over uitofp because it is faster on most 172870c0d4f7eb9c14bccc8a585be4086712e46bfbdbChris Lattner // platforms. 172970c0d4f7eb9c14bccc8a585be4086712e46bfbdbChris Lattner if (WeakPH) { 1730a40e4a0c8abbfe55d25a77e4e98508e43ed1c3aeChris Lattner Value *Conv = new SIToFPInst(NewPHI, PN->getType(), "indvar.conv", 1731a40e4a0c8abbfe55d25a77e4e98508e43ed1c3aeChris Lattner PN->getParent()->getFirstNonPHI()); 1732a40e4a0c8abbfe55d25a77e4e98508e43ed1c3aeChris Lattner PN->replaceAllUsesWith(Conv); 1733c91961e31b2a1cae655928e20b83cb6a457fdcd4Chris Lattner RecursivelyDeleteTriviallyDeadInstructions(PN); 1734cd40233429fce385ae4b22301ce705273a6951a1Devang Patel } 173558d43d4a41b21085c063bdd21a2abb68056e2a6fDevang Patel 173681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Add a new IVUsers entry for the newly-created integer PHI. 17372fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick if (IU) 17384417e537b65c14b378aeca75b2773582dd102f63Andrew Trick IU->AddUsersIfInteresting(NewPHI); 173981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman} 1740