IndVarSimplify.cpp revision 60ac719c85366da04852c204aea5aa86d66dbb07
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 612cc359d9fa28a871b18d93da76fd9cf516499e39fAndrew Trick Instruction *WidenIVUse(Use &NarrowDefUse, Instruction *NarrowDef, 613f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick Instruction *WideDef); 614f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick}; 615f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick} // anonymous namespace 616f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 61703d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trickstatic Value *getExtend( Value *NarrowOper, const Type *WideType, 61803d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick bool IsSigned, IRBuilder<> &Builder) { 61903d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick return IsSigned ? Builder.CreateSExt(NarrowOper, WideType) : 62003d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick Builder.CreateZExt(NarrowOper, WideType); 621f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick} 622931e345e76e75391d2a7c96530e305f802b5429dDan Gohman 623f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick/// CloneIVUser - Instantiate a wide operation to replace a narrow 624f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick/// operation. This only needs to handle operations that can evaluation to 625f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick/// SCEVAddRec. It can safely return 0 for any operation we decide not to clone. 626f85092c25525f75eef6982ffa40c9b48b87da987Andrew TrickInstruction *WidenIV::CloneIVUser(Instruction *NarrowUse, 627f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick Instruction *NarrowDef, 628f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick Instruction *WideDef) { 629f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick unsigned Opcode = NarrowUse->getOpcode(); 630f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick switch (Opcode) { 631f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick default: 632f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick return 0; 633f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick case Instruction::Add: 634f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick case Instruction::Mul: 635f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick case Instruction::UDiv: 636f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick case Instruction::Sub: 637f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick case Instruction::And: 638f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick case Instruction::Or: 639f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick case Instruction::Xor: 640f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick case Instruction::Shl: 641f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick case Instruction::LShr: 642f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick case Instruction::AShr: 643f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick DEBUG(dbgs() << "Cloning IVUser: " << *NarrowUse << "\n"); 644f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 64503d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick IRBuilder<> Builder(NarrowUse); 64603d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick 64703d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick // Replace NarrowDef operands with WideDef. Otherwise, we don't know 64803d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick // anything about the narrow operand yet so must insert a [sz]ext. It is 64903d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick // probably loop invariant and will be folded or hoisted. If it actually 65003d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick // comes from a widened IV, it should be removed during a future call to 65103d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick // WidenIVUse. 65203d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick Value *LHS = (NarrowUse->getOperand(0) == NarrowDef) ? WideDef : 65303d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick getExtend(NarrowUse->getOperand(0), WideType, IsSigned, Builder); 65403d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick Value *RHS = (NarrowUse->getOperand(1) == NarrowDef) ? WideDef : 65503d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick getExtend(NarrowUse->getOperand(1), WideType, IsSigned, Builder); 65603d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick 657f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick BinaryOperator *NarrowBO = cast<BinaryOperator>(NarrowUse); 658f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick BinaryOperator *WideBO = BinaryOperator::Create(NarrowBO->getOpcode(), 65903d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick LHS, RHS, 660f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick NarrowBO->getName()); 661f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick Builder.Insert(WideBO); 662f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick if (NarrowBO->hasNoUnsignedWrap()) WideBO->setHasNoUnsignedWrap(); 663f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick if (NarrowBO->hasNoSignedWrap()) WideBO->setHasNoSignedWrap(); 664f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 66503d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick return WideBO; 666f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick } 667f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick llvm_unreachable(0); 668f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick} 669f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 67003d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick// GetWideRecurrence - Is this instruction potentially interesting from IVUsers' 67103d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick// perspective after widening it's type? In other words, can the extend be 67203d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick// safely hoisted out of the loop with SCEV reducing the value to a recurrence 67303d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick// on the same loop. If so, return the sign or zero extended 67403d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick// recurrence. Otherwise return NULL. 67503d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trickconst SCEVAddRecExpr *WidenIV::GetWideRecurrence(Instruction *NarrowUse) { 67603d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick if (!SE->isSCEVable(NarrowUse->getType())) 67703d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick return 0; 67803d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick 67903d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick const SCEV *NarrowExpr = SE->getSCEV(NarrowUse); 68003d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick const SCEV *WideExpr = IsSigned ? 68103d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick SE->getSignExtendExpr(NarrowExpr, WideType) : 68203d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick SE->getZeroExtendExpr(NarrowExpr, WideType); 68303d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(WideExpr); 68403d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick if (!AddRec || AddRec->getLoop() != L) 68503d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick return 0; 68603d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick 68703d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick return AddRec; 68803d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick} 68903d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick 690fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick/// HoistStep - Attempt to hoist an IV increment above a potential use. 691fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick/// 692fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick/// To successfully hoist, two criteria must be met: 693fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick/// - IncV operands dominate InsertPos and 694fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick/// - InsertPos dominates IncV 695fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick/// 696fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick/// Meeting the second condition means that we don't need to check all of IncV's 697fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick/// existing uses (it's moving up in the domtree). 698fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick/// 699fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick/// This does not yet recursively hoist the operands, although that would 700fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick/// not be difficult. 701fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trickstatic bool HoistStep(Instruction *IncV, Instruction *InsertPos, 702fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick const DominatorTree *DT) 703fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick{ 704fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick if (DT->dominates(IncV, InsertPos)) 705fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick return true; 706fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick 707fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick if (!DT->dominates(InsertPos->getParent(), IncV->getParent())) 708fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick return false; 709fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick 710fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick if (IncV->mayHaveSideEffects()) 711fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick return false; 712fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick 713fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick // Attempt to hoist IncV 714fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick for (User::op_iterator OI = IncV->op_begin(), OE = IncV->op_end(); 715fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick OI != OE; ++OI) { 716fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick Instruction *OInst = dyn_cast<Instruction>(OI); 717fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick if (OInst && !DT->dominates(OInst, InsertPos)) 718fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick return false; 719fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick } 720fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick IncV->moveBefore(InsertPos); 721fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick return true; 722fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick} 723fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick 724f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick/// WidenIVUse - Determine whether an individual user of the narrow IV can be 725f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick/// widened. If so, return the wide clone of the user. 726cc359d9fa28a871b18d93da76fd9cf516499e39fAndrew TrickInstruction *WidenIV::WidenIVUse(Use &NarrowDefUse, Instruction *NarrowDef, 727f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick Instruction *WideDef) { 728cc359d9fa28a871b18d93da76fd9cf516499e39fAndrew Trick Instruction *NarrowUse = cast<Instruction>(NarrowDefUse.getUser()); 729cc359d9fa28a871b18d93da76fd9cf516499e39fAndrew Trick 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. 747cc359d9fa28a871b18d93da76fd9cf516499e39fAndrew Trick IRBuilder<> Builder(NarrowDefUse); 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. 781cc359d9fa28a871b18d93da76fd9cf516499e39fAndrew Trick IRBuilder<> Builder(NarrowDefUse); 78203d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick Value *Trunc = Builder.CreateTrunc(WideDef, NarrowDef->getType()); 783f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick NarrowUse->replaceUsesOfWith(NarrowDef, Trunc); 784f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick return 0; 785f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick } 786cc359d9fa28a871b18d93da76fd9cf516499e39fAndrew Trick // We assume that block terminators are not SCEVable. 787cc359d9fa28a871b18d93da76fd9cf516499e39fAndrew Trick assert(NarrowUse != NarrowUse->getParent()->getTerminator() && 788cc359d9fa28a871b18d93da76fd9cf516499e39fAndrew Trick "can't split terminators"); 789cc359d9fa28a871b18d93da76fd9cf516499e39fAndrew Trick 790fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick // Reuse the IV increment that SCEVExpander created as long as it dominates 791fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick // NarrowUse. 792f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick Instruction *WideUse = 0; 793fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick if (WideAddRec == WideIncExpr && HoistStep(WideInc, NarrowUse, DT)) { 794f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick WideUse = WideInc; 795f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick } 796f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick else { 797f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick WideUse = CloneIVUser(NarrowUse, NarrowDef, WideDef); 798f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick if (!WideUse) 799f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick return 0; 800f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick } 801f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // GetWideRecurrence ensured that the narrow expression could be extended 802f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // outside the loop without overflow. This suggests that the wide use 803f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // evaluates to the same expression as the extended narrow use, but doesn't 804f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // absolutely guarantee it. Hence the following failsafe check. In rare cases 8052fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick // where it fails, we simply throw away the newly created wide use. 806f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick if (WideAddRec != SE->getSCEV(WideUse)) { 807f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick DEBUG(dbgs() << "Wide use expression mismatch: " << *WideUse 808f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick << ": " << *SE->getSCEV(WideUse) << " != " << *WideAddRec << "\n"); 809f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick DeadInsts.push_back(WideUse); 810f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick return 0; 811f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick } 812f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 813f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // Returning WideUse pushes it on the worklist. 814f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick return WideUse; 815f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick} 816f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 817f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick/// CreateWideIV - Process a single induction variable. First use the 818f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick/// SCEVExpander to create a wide induction variable that evaluates to the same 819f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick/// recurrence as the original narrow IV. Then use a worklist to forward 8202fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// traverse the narrow IV's def-use chain. After WidenIVUse has processed all 821f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick/// interesting IV users, the narrow IV will be isolated for removal by 822f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick/// DeleteDeadPHIs. 823f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick/// 824f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick/// It would be simpler to delete uses as they are processed, but we must avoid 825f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick/// invalidating SCEV expressions. 826f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick/// 8272fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew TrickPHINode *WidenIV::CreateWideIV(SCEVExpander &Rewriter) { 828f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // Is this phi an induction variable? 829f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(SE->getSCEV(OrigPhi)); 830f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick if (!AddRec) 8312fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick return NULL; 832f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 833f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // Widen the induction variable expression. 834f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick const SCEV *WideIVExpr = IsSigned ? 835f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick SE->getSignExtendExpr(AddRec, WideType) : 836f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick SE->getZeroExtendExpr(AddRec, WideType); 837f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 838f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick assert(SE->getEffectiveSCEVType(WideIVExpr->getType()) == WideType && 839f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick "Expect the new IV expression to preserve its type"); 840f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 841f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // Can the IV be extended outside the loop without overflow? 842f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick AddRec = dyn_cast<SCEVAddRecExpr>(WideIVExpr); 843f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick if (!AddRec || AddRec->getLoop() != L) 8442fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick return NULL; 845f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 8462fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick // An AddRec must have loop-invariant operands. Since this AddRec is 847f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // materialized by a loop header phi, the expression cannot have any post-loop 848f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // operands, so they must dominate the loop header. 849f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick assert(SE->properlyDominates(AddRec->getStart(), L->getHeader()) && 850f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick SE->properlyDominates(AddRec->getStepRecurrence(*SE), L->getHeader()) 851f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick && "Loop header phi recurrence inputs do not dominate the loop"); 852f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 853f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // The rewriter provides a value for the desired IV expression. This may 854f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // either find an existing phi or materialize a new one. Either way, we 855f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // expect a well-formed cyclic phi-with-increments. i.e. any operand not part 856f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // of the phi-SCC dominates the loop entry. 857f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick Instruction *InsertPt = L->getHeader()->begin(); 858f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick WidePhi = cast<PHINode>(Rewriter.expandCodeFor(AddRec, WideType, InsertPt)); 859f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 860f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // Remembering the WideIV increment generated by SCEVExpander allows 861f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // WidenIVUse to reuse it when widening the narrow IV's increment. We don't 862f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // employ a general reuse mechanism because the call above is the only call to 863f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // SCEVExpander. Henceforth, we produce 1-to-1 narrow to wide uses. 864fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick if (BasicBlock *LatchBlock = L->getLoopLatch()) { 865fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick WideInc = 866fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick cast<Instruction>(WidePhi->getIncomingValueForBlock(LatchBlock)); 867fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick WideIncExpr = SE->getSCEV(WideInc); 868fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick } 869f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 870f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick DEBUG(dbgs() << "Wide IV: " << *WidePhi << "\n"); 871f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick ++NumWidened; 872f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 873f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // Traverse the def-use chain using a worklist starting at the original IV. 8742fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick assert(Widened.empty() && "expect initial state" ); 875f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 876fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick // Each worklist entry has a Narrow def-use link and Wide def. 877fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick SmallVector<std::pair<Use *, Instruction *>, 8> NarrowIVUsers; 878fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick for (Value::use_iterator UI = OrigPhi->use_begin(), 879fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick UE = OrigPhi->use_end(); UI != UE; ++UI) { 880fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick NarrowIVUsers.push_back(std::make_pair(&UI.getUse(), WidePhi)); 881fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick } 882f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick while (!NarrowIVUsers.empty()) { 883cc359d9fa28a871b18d93da76fd9cf516499e39fAndrew Trick Use *UsePtr; 884fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick Instruction *WideDef; 885cc359d9fa28a871b18d93da76fd9cf516499e39fAndrew Trick tie(UsePtr, WideDef) = NarrowIVUsers.pop_back_val(); 886cc359d9fa28a871b18d93da76fd9cf516499e39fAndrew Trick Use &NarrowDefUse = *UsePtr; 887fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick 888fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick // Process a def-use edge. This may replace the use, so don't hold a 889fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick // use_iterator across it. 890cc359d9fa28a871b18d93da76fd9cf516499e39fAndrew Trick Instruction *NarrowDef = cast<Instruction>(NarrowDefUse.get()); 891cc359d9fa28a871b18d93da76fd9cf516499e39fAndrew Trick Instruction *WideUse = WidenIVUse(NarrowDefUse, NarrowDef, WideDef); 892fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick 893fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick // Follow all def-use edges from the previous narrow use. 894fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick if (WideUse) { 895cc359d9fa28a871b18d93da76fd9cf516499e39fAndrew Trick for (Value::use_iterator UI = NarrowDefUse.getUser()->use_begin(), 896cc359d9fa28a871b18d93da76fd9cf516499e39fAndrew Trick UE = NarrowDefUse.getUser()->use_end(); UI != UE; ++UI) { 897fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick NarrowIVUsers.push_back(std::make_pair(&UI.getUse(), WideUse)); 898fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick } 899aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick } 900fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick // WidenIVUse may have removed the def-use edge. 901fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick if (NarrowDef->use_empty()) 902fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick DeadInsts.push_back(NarrowDef); 903931e345e76e75391d2a7c96530e305f802b5429dDan Gohman } 9042fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick return WidePhi; 905931e345e76e75391d2a7c96530e305f802b5429dDan Gohman} 906931e345e76e75391d2a7c96530e305f802b5429dDan Gohman 907aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trickvoid IndVarSimplify::EliminateIVComparison(ICmpInst *ICmp, Value *IVOperand) { 908aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick unsigned IVOperIdx = 0; 909aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick ICmpInst::Predicate Pred = ICmp->getPredicate(); 910aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick if (IVOperand != ICmp->getOperand(0)) { 911aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick // Swapped 912aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick assert(IVOperand == ICmp->getOperand(1) && "Can't find IVOperand"); 913aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick IVOperIdx = 1; 914aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick Pred = ICmpInst::getSwappedPredicate(Pred); 915aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick } 916a590b79ee227b93c59f60ce1f54cae7a9ebec7c1Dan Gohman 917aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick // Get the SCEVs for the ICmp operands. 918aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick const SCEV *S = SE->getSCEV(ICmp->getOperand(IVOperIdx)); 919aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick const SCEV *X = SE->getSCEV(ICmp->getOperand(1 - IVOperIdx)); 920aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick 921aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick // Simplify unnecessary loops away. 922aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick const Loop *ICmpLoop = LI->getLoopFor(ICmp->getParent()); 923aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick S = SE->getSCEVAtScope(S, ICmpLoop); 924aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick X = SE->getSCEVAtScope(X, ICmpLoop); 925aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick 926aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick // If the condition is always true or always false, replace it with 927aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick // a constant value. 928aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick if (SE->isKnownPredicate(Pred, S, X)) 929aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick ICmp->replaceAllUsesWith(ConstantInt::getTrue(ICmp->getContext())); 930aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick else if (SE->isKnownPredicate(ICmpInst::getInversePredicate(Pred), S, X)) 931aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick ICmp->replaceAllUsesWith(ConstantInt::getFalse(ICmp->getContext())); 932aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick else 933aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick return; 934a590b79ee227b93c59f60ce1f54cae7a9ebec7c1Dan Gohman 935aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick DEBUG(dbgs() << "INDVARS: Eliminated comparison: " << *ICmp << '\n'); 93603d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick ++NumElimCmp; 937074397d75e0bf919995f9cf0005fa6fda1c0400cAndrew Trick Changed = true; 938aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick DeadInsts.push_back(ICmp); 939aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick} 940a590b79ee227b93c59f60ce1f54cae7a9ebec7c1Dan Gohman 941aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trickvoid IndVarSimplify::EliminateIVRemainder(BinaryOperator *Rem, 942aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick Value *IVOperand, 9434417e537b65c14b378aeca75b2773582dd102f63Andrew Trick bool IsSigned) { 944aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick // We're only interested in the case where we know something about 945aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick // the numerator. 946aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick if (IVOperand != Rem->getOperand(0)) 947aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick return; 948aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick 949aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick // Get the SCEVs for the ICmp operands. 950aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick const SCEV *S = SE->getSCEV(Rem->getOperand(0)); 951aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick const SCEV *X = SE->getSCEV(Rem->getOperand(1)); 952aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick 953aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick // Simplify unnecessary loops away. 954aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick const Loop *ICmpLoop = LI->getLoopFor(Rem->getParent()); 955aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick S = SE->getSCEVAtScope(S, ICmpLoop); 956aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick X = SE->getSCEVAtScope(X, ICmpLoop); 957aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick 958aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick // i % n --> i if i is in [0,n). 959074397d75e0bf919995f9cf0005fa6fda1c0400cAndrew Trick if ((!IsSigned || SE->isKnownNonNegative(S)) && 960074397d75e0bf919995f9cf0005fa6fda1c0400cAndrew Trick SE->isKnownPredicate(IsSigned ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT, 961aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick S, X)) 962aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick Rem->replaceAllUsesWith(Rem->getOperand(0)); 963aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick else { 964aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick // (i+1) % n --> (i+1)==n?0:(i+1) if i is in [0,n). 965aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick const SCEV *LessOne = 966aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick SE->getMinusSCEV(S, SE->getConstant(S->getType(), 1)); 967074397d75e0bf919995f9cf0005fa6fda1c0400cAndrew Trick if (IsSigned && !SE->isKnownNonNegative(LessOne)) 968aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick return; 969aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick 970074397d75e0bf919995f9cf0005fa6fda1c0400cAndrew Trick if (!SE->isKnownPredicate(IsSigned ? 971aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT, 972aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick LessOne, X)) 973aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick return; 974aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick 975aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick ICmpInst *ICmp = new ICmpInst(Rem, ICmpInst::ICMP_EQ, 976aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick Rem->getOperand(0), Rem->getOperand(1), 977aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick "tmp"); 978aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick SelectInst *Sel = 979aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick SelectInst::Create(ICmp, 980aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick ConstantInt::get(Rem->getType(), 0), 981aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick Rem->getOperand(0), "tmp", Rem); 982aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick Rem->replaceAllUsesWith(Sel); 983aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick } 984a590b79ee227b93c59f60ce1f54cae7a9ebec7c1Dan Gohman 985aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick // Inform IVUsers about the new users. 9862fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick if (IU) { 9872fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick if (Instruction *I = dyn_cast<Instruction>(Rem->getOperand(0))) 9884417e537b65c14b378aeca75b2773582dd102f63Andrew Trick IU->AddUsersIfInteresting(I); 9892fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick } 990aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick DEBUG(dbgs() << "INDVARS: Simplified rem: " << *Rem << '\n'); 99103d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick ++NumElimRem; 992074397d75e0bf919995f9cf0005fa6fda1c0400cAndrew Trick Changed = true; 993aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick DeadInsts.push_back(Rem); 994a590b79ee227b93c59f60ce1f54cae7a9ebec7c1Dan Gohman} 995a590b79ee227b93c59f60ce1f54cae7a9ebec7c1Dan Gohman 9962fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// EliminateIVUser - Eliminate an operation that consumes a simple IV and has 9972fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// no observable side-effect given the range of IV values. 9982fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trickbool IndVarSimplify::EliminateIVUser(Instruction *UseInst, 9992fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick Instruction *IVOperand) { 10002fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick if (ICmpInst *ICmp = dyn_cast<ICmpInst>(UseInst)) { 10012fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick EliminateIVComparison(ICmp, IVOperand); 10022fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick return true; 10032fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick } 10042fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick if (BinaryOperator *Rem = dyn_cast<BinaryOperator>(UseInst)) { 10052fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick bool IsSigned = Rem->getOpcode() == Instruction::SRem; 10062fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick if (IsSigned || Rem->getOpcode() == Instruction::URem) { 10074417e537b65c14b378aeca75b2773582dd102f63Andrew Trick EliminateIVRemainder(Rem, IVOperand, IsSigned); 10082fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick return true; 10092fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick } 10102fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick } 10112fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick 10122fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick // Eliminate any operation that SCEV can prove is an identity function. 10132fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick if (!SE->isSCEVable(UseInst->getType()) || 101411745d4c0276ccb5c64f83d6954b54c8ff2aec98Andrew Trick (UseInst->getType() != IVOperand->getType()) || 10152fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick (SE->getSCEV(UseInst) != SE->getSCEV(IVOperand))) 10162fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick return false; 10172fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick 10182fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick DEBUG(dbgs() << "INDVARS: Eliminated identity: " << *UseInst << '\n'); 101960ac719c85366da04852c204aea5aa86d66dbb07Andrew Trick 102060ac719c85366da04852c204aea5aa86d66dbb07Andrew Trick UseInst->replaceAllUsesWith(IVOperand); 10212fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick ++NumElimIdentity; 10222fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick Changed = true; 10232fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick DeadInsts.push_back(UseInst); 10242fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick return true; 10252fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick} 10262fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick 10272fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// pushIVUsers - Add all uses of Def to the current IV's worklist. 10282fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// 102915832f61775040995bb8aa6056176425bc2c9088Andrew Trickstatic void pushIVUsers( 103015832f61775040995bb8aa6056176425bc2c9088Andrew Trick Instruction *Def, 103115832f61775040995bb8aa6056176425bc2c9088Andrew Trick SmallPtrSet<Instruction*,16> &Simplified, 103215832f61775040995bb8aa6056176425bc2c9088Andrew Trick SmallVectorImpl< std::pair<Instruction*,Instruction*> > &SimpleIVUsers) { 10332fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick 10342fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick for (Value::use_iterator UI = Def->use_begin(), E = Def->use_end(); 10352fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick UI != E; ++UI) { 10362fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick Instruction *User = cast<Instruction>(*UI); 10372fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick 10382fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick // Avoid infinite or exponential worklist processing. 10392fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick // Also ensure unique worklist users. 104060ac719c85366da04852c204aea5aa86d66dbb07Andrew Trick // If Def is a LoopPhi, it may not be in the Simplified set, so check for 104160ac719c85366da04852c204aea5aa86d66dbb07Andrew Trick // self edges first. 104260ac719c85366da04852c204aea5aa86d66dbb07Andrew Trick if (User != Def && Simplified.insert(User)) 10432fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick SimpleIVUsers.push_back(std::make_pair(User, Def)); 10442fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick } 10452fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick} 10462fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick 10472fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// isSimpleIVUser - Return true if this instruction generates a simple SCEV 10482fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// expression in terms of that IV. 10492fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// 10502fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// This is similar to IVUsers' isInsteresting() but processes each instruction 10512fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// non-recursively when the operand is already known to be a simpleIVUser. 10522fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// 10532fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trickbool IndVarSimplify::isSimpleIVUser(Instruction *I, const Loop *L) { 10542fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick if (!SE->isSCEVable(I->getType())) 10552fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick return false; 10562fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick 10572fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick // Get the symbolic expression for this instruction. 10582fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick const SCEV *S = SE->getSCEV(I); 10592fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick 1060cc359d9fa28a871b18d93da76fd9cf516499e39fAndrew Trick // We assume that terminators are not SCEVable. 1061cc359d9fa28a871b18d93da76fd9cf516499e39fAndrew Trick assert((!S || I != I->getParent()->getTerminator()) && 1062cc359d9fa28a871b18d93da76fd9cf516499e39fAndrew Trick "can't fold terminators"); 1063cc359d9fa28a871b18d93da76fd9cf516499e39fAndrew Trick 10642fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick // Only consider affine recurrences. 10652fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S); 10662fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick if (AR && AR->getLoop() == L) 10672fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick return true; 10682fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick 10692fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick return false; 10702fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick} 10712fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick 10722fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// SimplifyIVUsersNoRewrite - Iteratively perform simplification on a worklist 10732fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// of IV users. Each successive simplification may push more users which may 10742fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// themselves be candidates for simplification. 10752fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// 10762fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// The "NoRewrite" algorithm does not require IVUsers analysis. Instead, it 10772fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// simplifies instructions in-place during analysis. Rather than rewriting 10782fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// induction variables bottom-up from their users, it transforms a chain of 10792fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// IVUsers top-down, updating the IR only when it encouters a clear 10802fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// optimization opportunitiy. A SCEVExpander "Rewriter" instance is still 10812fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// needed, but only used to generate a new IV (phi) of wider type for sign/zero 10822fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// extend elimination. 10832fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// 10842fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// Once DisableIVRewrite is default, LSR will be the only client of IVUsers. 10852fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// 10862fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trickvoid IndVarSimplify::SimplifyIVUsersNoRewrite(Loop *L, SCEVExpander &Rewriter) { 108715832f61775040995bb8aa6056176425bc2c9088Andrew Trick std::map<PHINode *, WideIVInfo> WideIVMap; 108815832f61775040995bb8aa6056176425bc2c9088Andrew Trick 10892fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick SmallVector<PHINode*, 8> LoopPhis; 10902fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I) { 10912fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick LoopPhis.push_back(cast<PHINode>(I)); 10922fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick } 109315832f61775040995bb8aa6056176425bc2c9088Andrew Trick // Each round of simplification iterates through the SimplifyIVUsers worklist 109415832f61775040995bb8aa6056176425bc2c9088Andrew Trick // for all current phis, then determines whether any IVs can be 109515832f61775040995bb8aa6056176425bc2c9088Andrew Trick // widened. Widening adds new phis to LoopPhis, inducing another round of 109615832f61775040995bb8aa6056176425bc2c9088Andrew Trick // simplification on the wide IVs. 10972fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick while (!LoopPhis.empty()) { 109815832f61775040995bb8aa6056176425bc2c9088Andrew Trick // Evaluate as many IV expressions as possible before widening any IVs. This 109999a92f67c7ee0d428e18f35c91311a2baba6c03eAndrew Trick // forces SCEV to set no-wrap flags before evaluating sign/zero 110015832f61775040995bb8aa6056176425bc2c9088Andrew Trick // extension. The first time SCEV attempts to normalize sign/zero extension, 110115832f61775040995bb8aa6056176425bc2c9088Andrew Trick // the result becomes final. So for the most predictable results, we delay 110215832f61775040995bb8aa6056176425bc2c9088Andrew Trick // evaluation of sign/zero extend evaluation until needed, and avoid running 110315832f61775040995bb8aa6056176425bc2c9088Andrew Trick // other SCEV based analysis prior to SimplifyIVUsersNoRewrite. 110415832f61775040995bb8aa6056176425bc2c9088Andrew Trick do { 110515832f61775040995bb8aa6056176425bc2c9088Andrew Trick PHINode *CurrIV = LoopPhis.pop_back_val(); 11062fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick 110715832f61775040995bb8aa6056176425bc2c9088Andrew Trick // Information about sign/zero extensions of CurrIV. 110815832f61775040995bb8aa6056176425bc2c9088Andrew Trick WideIVInfo WI; 11092fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick 111015832f61775040995bb8aa6056176425bc2c9088Andrew Trick // Instructions processed by SimplifyIVUsers for CurrIV. 111115832f61775040995bb8aa6056176425bc2c9088Andrew Trick SmallPtrSet<Instruction*,16> Simplified; 11122fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick 111315832f61775040995bb8aa6056176425bc2c9088Andrew Trick // Use-def pairs if IVUsers waiting to be processed for CurrIV. 111415832f61775040995bb8aa6056176425bc2c9088Andrew Trick SmallVector<std::pair<Instruction*, Instruction*>, 8> SimpleIVUsers; 11152fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick 111660ac719c85366da04852c204aea5aa86d66dbb07Andrew Trick // Push users of the current LoopPhi. In rare cases, pushIVUsers may be 111760ac719c85366da04852c204aea5aa86d66dbb07Andrew Trick // called multiple times for the same LoopPhi. This is the proper thing to 111860ac719c85366da04852c204aea5aa86d66dbb07Andrew Trick // do for loop header phis that use each other. 111915832f61775040995bb8aa6056176425bc2c9088Andrew Trick pushIVUsers(CurrIV, Simplified, SimpleIVUsers); 112015832f61775040995bb8aa6056176425bc2c9088Andrew Trick 112115832f61775040995bb8aa6056176425bc2c9088Andrew Trick while (!SimpleIVUsers.empty()) { 112215832f61775040995bb8aa6056176425bc2c9088Andrew Trick Instruction *UseInst, *Operand; 112315832f61775040995bb8aa6056176425bc2c9088Andrew Trick tie(UseInst, Operand) = SimpleIVUsers.pop_back_val(); 112415832f61775040995bb8aa6056176425bc2c9088Andrew Trick 112515832f61775040995bb8aa6056176425bc2c9088Andrew Trick if (EliminateIVUser(UseInst, Operand)) { 112615832f61775040995bb8aa6056176425bc2c9088Andrew Trick pushIVUsers(Operand, Simplified, SimpleIVUsers); 112715832f61775040995bb8aa6056176425bc2c9088Andrew Trick continue; 112815832f61775040995bb8aa6056176425bc2c9088Andrew Trick } 112915832f61775040995bb8aa6056176425bc2c9088Andrew Trick if (CastInst *Cast = dyn_cast<CastInst>(UseInst)) { 113015832f61775040995bb8aa6056176425bc2c9088Andrew Trick bool IsSigned = Cast->getOpcode() == Instruction::SExt; 113115832f61775040995bb8aa6056176425bc2c9088Andrew Trick if (IsSigned || Cast->getOpcode() == Instruction::ZExt) { 113215832f61775040995bb8aa6056176425bc2c9088Andrew Trick CollectExtend(Cast, IsSigned, WI, SE, TD); 113315832f61775040995bb8aa6056176425bc2c9088Andrew Trick } 113415832f61775040995bb8aa6056176425bc2c9088Andrew Trick continue; 113515832f61775040995bb8aa6056176425bc2c9088Andrew Trick } 113615832f61775040995bb8aa6056176425bc2c9088Andrew Trick if (isSimpleIVUser(UseInst, L)) { 113715832f61775040995bb8aa6056176425bc2c9088Andrew Trick pushIVUsers(UseInst, Simplified, SimpleIVUsers); 11382fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick } 11392fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick } 114015832f61775040995bb8aa6056176425bc2c9088Andrew Trick if (WI.WidestNativeType) { 114115832f61775040995bb8aa6056176425bc2c9088Andrew Trick WideIVMap[CurrIV] = WI; 11422fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick } 114315832f61775040995bb8aa6056176425bc2c9088Andrew Trick } while(!LoopPhis.empty()); 114415832f61775040995bb8aa6056176425bc2c9088Andrew Trick 114515832f61775040995bb8aa6056176425bc2c9088Andrew Trick for (std::map<PHINode *, WideIVInfo>::const_iterator I = WideIVMap.begin(), 114615832f61775040995bb8aa6056176425bc2c9088Andrew Trick E = WideIVMap.end(); I != E; ++I) { 114715832f61775040995bb8aa6056176425bc2c9088Andrew Trick WidenIV Widener(I->first, I->second, LI, SE, DT, DeadInsts); 11482fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick if (PHINode *WidePhi = Widener.CreateWideIV(Rewriter)) { 11492fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick Changed = true; 11502fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick LoopPhis.push_back(WidePhi); 11512fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick } 11522fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick } 115315832f61775040995bb8aa6056176425bc2c9088Andrew Trick WideIVMap.clear(); 11542fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick } 11552fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick} 11562fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick 1157c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohmanbool IndVarSimplify::runOnLoop(Loop *L, LPPassManager &LPM) { 1158a52838285b6dce66821f0b272cb3479af8c3edb2Dan Gohman // If LoopSimplify form is not available, stay out of trouble. Some notes: 1159a52838285b6dce66821f0b272cb3479af8c3edb2Dan Gohman // - LSR currently only supports LoopSimplify-form loops. Indvars' 1160a52838285b6dce66821f0b272cb3479af8c3edb2Dan Gohman // canonicalization can be a pessimization without LSR to "clean up" 1161a52838285b6dce66821f0b272cb3479af8c3edb2Dan Gohman // afterwards. 1162a52838285b6dce66821f0b272cb3479af8c3edb2Dan Gohman // - We depend on having a preheader; in particular, 1163a52838285b6dce66821f0b272cb3479af8c3edb2Dan Gohman // Loop::getCanonicalInductionVariable only supports loops with preheaders, 1164a52838285b6dce66821f0b272cb3479af8c3edb2Dan Gohman // and we're in trouble if we can't find the induction variable even when 1165a52838285b6dce66821f0b272cb3479af8c3edb2Dan Gohman // we've manually inserted one. 1166a52838285b6dce66821f0b272cb3479af8c3edb2Dan Gohman if (!L->isLoopSimplifyForm()) 1167a52838285b6dce66821f0b272cb3479af8c3edb2Dan Gohman return false; 1168a52838285b6dce66821f0b272cb3479af8c3edb2Dan Gohman 11692fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick if (!DisableIVRewrite) 11702fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick IU = &getAnalysis<IVUsers>(); 11715ee99979065d75605d150d7e567e4351024aae8fDevang Patel LI = &getAnalysis<LoopInfo>(); 11725ee99979065d75605d150d7e567e4351024aae8fDevang Patel SE = &getAnalysis<ScalarEvolution>(); 1173de53dc03f5c1549f3176e979bbeeac965dfa5cbcDan Gohman DT = &getAnalysis<DominatorTree>(); 117437da40875873d70b83dc08b2803052bec9b68886Andrew Trick TD = getAnalysisIfAvailable<TargetData>(); 117537da40875873d70b83dc08b2803052bec9b68886Andrew Trick 1176b12a754cce0c1d5542af605203a47820edba454dAndrew Trick DeadInsts.clear(); 11775ee99979065d75605d150d7e567e4351024aae8fDevang Patel Changed = false; 117860f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman 11792d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman // If there are any floating-point recurrences, attempt to 118060f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman // transform them to use integer recurrences. 118160f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman RewriteNonIntegerIVs(L); 118260f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman 11830bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *BackedgeTakenCount = SE->getBackedgeTakenCount(L); 11849caed5440d59dac4b388152fe8b993dc0491e5e9Chris Lattner 1185667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman // Create a rewriter object which we'll use to transform the code with. 11865e7645be4c9dd2193add44d30b5fef8036d7a3ceAndrew Trick SCEVExpander Rewriter(*SE, "indvars"); 1187156d460c758463eb407590cba2371857daf27d8aAndrew Trick 1188156d460c758463eb407590cba2371857daf27d8aAndrew Trick // Eliminate redundant IV users. 118915832f61775040995bb8aa6056176425bc2c9088Andrew Trick // 119015832f61775040995bb8aa6056176425bc2c9088Andrew Trick // Simplification works best when run before other consumers of SCEV. We 119115832f61775040995bb8aa6056176425bc2c9088Andrew Trick // attempt to avoid evaluating SCEVs for sign/zero extend operations until 119215832f61775040995bb8aa6056176425bc2c9088Andrew Trick // other expressions involving loop IVs have been evaluated. This helps SCEV 119399a92f67c7ee0d428e18f35c91311a2baba6c03eAndrew Trick // set no-wrap flags before normalizing sign/zero extension. 1194156d460c758463eb407590cba2371857daf27d8aAndrew Trick if (DisableIVRewrite) { 119537da40875873d70b83dc08b2803052bec9b68886Andrew Trick Rewriter.disableCanonicalMode(); 1196156d460c758463eb407590cba2371857daf27d8aAndrew Trick SimplifyIVUsersNoRewrite(L, Rewriter); 1197156d460c758463eb407590cba2371857daf27d8aAndrew Trick } 119837da40875873d70b83dc08b2803052bec9b68886Andrew Trick 119940bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // Check to see if this loop has a computable loop-invariant execution count. 120040bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // If so, this means that we can compute the final value of any expressions 120140bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // that are recurrent in the loop, and substitute the exit values from the 120240bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // loop into any instructions outside of the loop that use the final values of 120340bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // the current expressions. 1204394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner // 120546bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman if (!isa<SCEVCouldNotCompute>(BackedgeTakenCount)) 1206454d26dc43207ec537d843229db6f5e6a302e23dDan Gohman RewriteLoopExitValues(L, Rewriter); 120740bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner 1208f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // Eliminate redundant IV users. 1209156d460c758463eb407590cba2371857daf27d8aAndrew Trick if (!DisableIVRewrite) 12102fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick SimplifyIVUsers(Rewriter); 1211a590b79ee227b93c59f60ce1f54cae7a9ebec7c1Dan Gohman 121281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Compute the type of the largest recurrence expression, and decide whether 121381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // a canonical induction variable should be inserted. 1214f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick const Type *LargestType = 0; 121581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman bool NeedCannIV = false; 121603d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick bool ExpandBECount = canExpandBackedgeTakenCount(L, SE); 12174dfdf242c1917e98f407818eb5b68ae0b4678f26Andrew Trick if (ExpandBECount) { 121881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // If we have a known trip count and a single exit block, we'll be 121981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // rewriting the loop exit test condition below, which requires a 122081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // canonical induction variable. 12214dfdf242c1917e98f407818eb5b68ae0b4678f26Andrew Trick NeedCannIV = true; 12224dfdf242c1917e98f407818eb5b68ae0b4678f26Andrew Trick const Type *Ty = BackedgeTakenCount->getType(); 122303d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick if (DisableIVRewrite) { 122403d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick // In this mode, SimplifyIVUsers may have already widened the IV used by 122503d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick // the backedge test and inserted a Trunc on the compare's operand. Get 122603d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick // the wider type to avoid creating a redundant narrow IV only used by the 122703d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick // loop test. 122803d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick LargestType = getBackedgeIVType(L); 122903d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick } 12304dfdf242c1917e98f407818eb5b68ae0b4678f26Andrew Trick if (!LargestType || 12314dfdf242c1917e98f407818eb5b68ae0b4678f26Andrew Trick SE->getTypeSizeInBits(Ty) > 12324dfdf242c1917e98f407818eb5b68ae0b4678f26Andrew Trick SE->getTypeSizeInBits(LargestType)) 12334dfdf242c1917e98f407818eb5b68ae0b4678f26Andrew Trick LargestType = SE->getEffectiveSCEVType(Ty); 1234f50af088f19f525f3d1026eb61db77e0037a9f43Chris Lattner } 123537da40875873d70b83dc08b2803052bec9b68886Andrew Trick if (!DisableIVRewrite) { 123637da40875873d70b83dc08b2803052bec9b68886Andrew Trick for (IVUsers::const_iterator I = IU->begin(), E = IU->end(); I != E; ++I) { 123737da40875873d70b83dc08b2803052bec9b68886Andrew Trick NeedCannIV = true; 123837da40875873d70b83dc08b2803052bec9b68886Andrew Trick const Type *Ty = 123937da40875873d70b83dc08b2803052bec9b68886Andrew Trick SE->getEffectiveSCEVType(I->getOperandValToReplace()->getType()); 124037da40875873d70b83dc08b2803052bec9b68886Andrew Trick if (!LargestType || 124137da40875873d70b83dc08b2803052bec9b68886Andrew Trick SE->getTypeSizeInBits(Ty) > 1242af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman SE->getTypeSizeInBits(LargestType)) 124337da40875873d70b83dc08b2803052bec9b68886Andrew Trick LargestType = Ty; 124437da40875873d70b83dc08b2803052bec9b68886Andrew Trick } 1245500597a1c39e91a3020587318ed61e737b6c613aChris Lattner } 1246394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner 1247f451cb870efcf9e0302d25ed05f4cac6bb494e42Dan Gohman // Now that we know the largest of the induction variable expressions 124881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // in this loop, insert a canonical induction variable of the largest size. 124943ef3fbae12c7924a25df4563d86084973db9c67Dan Gohman PHINode *IndVar = 0; 125081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (NeedCannIV) { 125185669637139089eaed8def1583ac04266c9654e2Dan Gohman // Check to see if the loop already has any canonical-looking induction 125285669637139089eaed8def1583ac04266c9654e2Dan Gohman // variables. If any are present and wider than the planned canonical 125385669637139089eaed8def1583ac04266c9654e2Dan Gohman // induction variable, temporarily remove them, so that the Rewriter 125485669637139089eaed8def1583ac04266c9654e2Dan Gohman // doesn't attempt to reuse them. 125585669637139089eaed8def1583ac04266c9654e2Dan Gohman SmallVector<PHINode *, 2> OldCannIVs; 125685669637139089eaed8def1583ac04266c9654e2Dan Gohman while (PHINode *OldCannIV = L->getCanonicalInductionVariable()) { 12574d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman if (SE->getTypeSizeInBits(OldCannIV->getType()) > 12584d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman SE->getTypeSizeInBits(LargestType)) 12594d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman OldCannIV->removeFromParent(); 12604d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman else 126185669637139089eaed8def1583ac04266c9654e2Dan Gohman break; 126285669637139089eaed8def1583ac04266c9654e2Dan Gohman OldCannIVs.push_back(OldCannIV); 12634d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman } 12644d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman 1265667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman IndVar = Rewriter.getOrInsertCanonicalInductionVariable(L, LargestType); 12664d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman 1267c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman ++NumInserted; 1268c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman Changed = true; 1269f67ef318aa29e7cc0c7de76349881959936d9eeeDavid Greene DEBUG(dbgs() << "INDVARS: New CanIV: " << *IndVar << '\n'); 12704d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman 12714d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman // Now that the official induction variable is established, reinsert 127285669637139089eaed8def1583ac04266c9654e2Dan Gohman // any old canonical-looking variables after it so that the IR remains 127385669637139089eaed8def1583ac04266c9654e2Dan Gohman // consistent. They will be deleted as part of the dead-PHI deletion at 12744d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman // the end of the pass. 127585669637139089eaed8def1583ac04266c9654e2Dan Gohman while (!OldCannIVs.empty()) { 127685669637139089eaed8def1583ac04266c9654e2Dan Gohman PHINode *OldCannIV = OldCannIVs.pop_back_val(); 127785669637139089eaed8def1583ac04266c9654e2Dan Gohman OldCannIV->insertBefore(L->getHeader()->getFirstNonPHI()); 127885669637139089eaed8def1583ac04266c9654e2Dan Gohman } 1279d19534add90a2a894af61523b830887097bb780bDan Gohman } 128040bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner 1281c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman // If we have a trip count expression, rewrite the loop's exit condition 1282c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman // using it. We can currently only handle loops with a single exit. 128381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman ICmpInst *NewICmp = 0; 12844dfdf242c1917e98f407818eb5b68ae0b4678f26Andrew Trick if (ExpandBECount) { 128503d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick assert(canExpandBackedgeTakenCount(L, SE) && 12864dfdf242c1917e98f407818eb5b68ae0b4678f26Andrew Trick "canonical IV disrupted BackedgeTaken expansion"); 128781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman assert(NeedCannIV && 128881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman "LinearFunctionTestReplace requires a canonical induction variable"); 12894dfdf242c1917e98f407818eb5b68ae0b4678f26Andrew Trick NewICmp = LinearFunctionTestReplace(L, BackedgeTakenCount, IndVar, 12904dfdf242c1917e98f407818eb5b68ae0b4678f26Andrew Trick Rewriter); 129181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman } 1292b12a754cce0c1d5542af605203a47820edba454dAndrew Trick // Rewrite IV-derived expressions. 129337da40875873d70b83dc08b2803052bec9b68886Andrew Trick if (!DisableIVRewrite) 129437da40875873d70b83dc08b2803052bec9b68886Andrew Trick RewriteIVExpressions(L, Rewriter); 1295fcb81f5f4cbac61851b7dec403961cf88e614aa1Chris Lattner 1296b12a754cce0c1d5542af605203a47820edba454dAndrew Trick // Clear the rewriter cache, because values that are in the rewriter's cache 1297b12a754cce0c1d5542af605203a47820edba454dAndrew Trick // can be deleted in the loop below, causing the AssertingVH in the cache to 1298b12a754cce0c1d5542af605203a47820edba454dAndrew Trick // trigger. 1299b12a754cce0c1d5542af605203a47820edba454dAndrew Trick Rewriter.clear(); 1300b12a754cce0c1d5542af605203a47820edba454dAndrew Trick 1301b12a754cce0c1d5542af605203a47820edba454dAndrew Trick // Now that we're done iterating through lists, clean up any instructions 1302b12a754cce0c1d5542af605203a47820edba454dAndrew Trick // which are now dead. 1303b12a754cce0c1d5542af605203a47820edba454dAndrew Trick while (!DeadInsts.empty()) 1304b12a754cce0c1d5542af605203a47820edba454dAndrew Trick if (Instruction *Inst = 1305b12a754cce0c1d5542af605203a47820edba454dAndrew Trick dyn_cast_or_null<Instruction>(&*DeadInsts.pop_back_val())) 1306b12a754cce0c1d5542af605203a47820edba454dAndrew Trick RecursivelyDeleteTriviallyDeadInstructions(Inst); 1307b12a754cce0c1d5542af605203a47820edba454dAndrew Trick 1308667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman // The Rewriter may not be used from this point on. 13093d431384f05c9defc84f36eafe220415cc12ee93Torok Edwin 131081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Loop-invariant instructions in the preheader that aren't used in the 131181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // loop may be sunk below the loop to reduce register pressure. 1312667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman SinkUnusedInvariants(L); 131381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 131481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // For completeness, inform IVUsers of the IV use in the newly-created 131581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // loop exit test instruction. 13162fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick if (NewICmp && IU) 13174417e537b65c14b378aeca75b2773582dd102f63Andrew Trick IU->AddUsersIfInteresting(cast<Instruction>(NewICmp->getOperand(0))); 131881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 131981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Clean up dead instructions. 13209fff2187a21f765ed87a25c48552a6942450f3e2Dan Gohman Changed |= DeleteDeadPHIs(L->getHeader()); 132181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Check a post-condition. 1322bbf81d88116d23fb0776412b5916f7d0b8b3ca7eDan Gohman assert(L->isLCSSAForm(*DT) && "Indvars did not leave the loop in lcssa form!"); 132381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman return Changed; 132481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman} 132581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 1326448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman// FIXME: It is an extremely bad idea to indvar substitute anything more 1327448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman// complex than affine induction variables. Doing so will put expensive 1328448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman// polynomial evaluations inside of the loop, and the str reduction pass 1329448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman// currently can only reduce affine polynomials. For now just disable 1330448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman// indvar subst on anything more complex than an affine addrec, unless 1331448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman// it can be expanded to a trivial value. 133217ead4ff4baceb2c5503f233d0288d363ae44165Dan Gohmanstatic bool isSafe(const SCEV *S, const Loop *L, ScalarEvolution *SE) { 1333448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman // Loop-invariant values are safe. 133417ead4ff4baceb2c5503f233d0288d363ae44165Dan Gohman if (SE->isLoopInvariant(S, L)) return true; 1335448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman 1336448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman // Affine addrecs are safe. Non-affine are not, because LSR doesn't know how 1337448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman // to transform them into efficient code. 1338448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) 1339448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman return AR->isAffine(); 1340448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman 1341448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman // An add is safe it all its operands are safe. 1342448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman if (const SCEVCommutativeExpr *Commutative = dyn_cast<SCEVCommutativeExpr>(S)) { 1343448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman for (SCEVCommutativeExpr::op_iterator I = Commutative->op_begin(), 1344448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman E = Commutative->op_end(); I != E; ++I) 134517ead4ff4baceb2c5503f233d0288d363ae44165Dan Gohman if (!isSafe(*I, L, SE)) return false; 1346448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman return true; 1347448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman } 1348ead71d59a7685fbbbb92162556680abd9001d37bAndrew Trick 1349448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman // A cast is safe if its operand is. 1350448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman if (const SCEVCastExpr *C = dyn_cast<SCEVCastExpr>(S)) 135117ead4ff4baceb2c5503f233d0288d363ae44165Dan Gohman return isSafe(C->getOperand(), L, SE); 1352448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman 1353448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman // A udiv is safe if its operands are. 1354448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman if (const SCEVUDivExpr *UD = dyn_cast<SCEVUDivExpr>(S)) 135517ead4ff4baceb2c5503f233d0288d363ae44165Dan Gohman return isSafe(UD->getLHS(), L, SE) && 135617ead4ff4baceb2c5503f233d0288d363ae44165Dan Gohman isSafe(UD->getRHS(), L, SE); 1357448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman 1358448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman // SCEVUnknown is always safe. 1359448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman if (isa<SCEVUnknown>(S)) 1360448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman return true; 1361448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman 1362448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman // Nothing else is safe. 1363448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman return false; 1364448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman} 1365448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman 1366454d26dc43207ec537d843229db6f5e6a302e23dDan Gohmanvoid IndVarSimplify::RewriteIVExpressions(Loop *L, SCEVExpander &Rewriter) { 136781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Rewrite all induction variable expressions in terms of the canonical 136881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // induction variable. 136981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // 137081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // If there were induction variables of other sizes or offsets, manually 137181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // add the offsets to the primary induction variable and cast, avoiding 137281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // the need for the code evaluation methods to insert induction variables 137381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // of different sizes. 1374572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman for (IVUsers::iterator UI = IU->begin(), E = IU->end(); UI != E; ++UI) { 1375572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman Value *Op = UI->getOperandValToReplace(); 1376572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman const Type *UseTy = Op->getType(); 1377572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman Instruction *User = UI->getUser(); 1378572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman 1379572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // Compute the final addrec to expand into code. 1380572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman const SCEV *AR = IU->getReplacementExpr(*UI); 1381572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman 1382572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // Evaluate the expression out of the loop, if possible. 1383572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman if (!L->contains(UI->getUser())) { 1384572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman const SCEV *ExitVal = SE->getSCEVAtScope(AR, L->getParentLoop()); 138517ead4ff4baceb2c5503f233d0288d363ae44165Dan Gohman if (SE->isLoopInvariant(ExitVal, L)) 1386572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman AR = ExitVal; 138781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman } 1388572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman 1389572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // FIXME: It is an extremely bad idea to indvar substitute anything more 1390572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // complex than affine induction variables. Doing so will put expensive 1391572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // polynomial evaluations inside of the loop, and the str reduction pass 1392572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // currently can only reduce affine polynomials. For now just disable 1393572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // indvar subst on anything more complex than an affine addrec, unless 1394572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // it can be expanded to a trivial value. 139517ead4ff4baceb2c5503f233d0288d363ae44165Dan Gohman if (!isSafe(AR, L, SE)) 1396572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman continue; 1397572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman 1398572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // Determine the insertion point for this user. By default, insert 1399572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // immediately before the user. The SCEVExpander class will automatically 1400572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // hoist loop invariants out of the loop. For PHI nodes, there may be 1401572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // multiple uses, so compute the nearest common dominator for the 1402572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // incoming blocks. 1403572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman Instruction *InsertPt = User; 1404572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman if (PHINode *PHI = dyn_cast<PHINode>(InsertPt)) 1405572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i) 1406572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman if (PHI->getIncomingValue(i) == Op) { 1407572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman if (InsertPt == User) 1408572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman InsertPt = PHI->getIncomingBlock(i)->getTerminator(); 1409572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman else 1410572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman InsertPt = 1411572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman DT->findNearestCommonDominator(InsertPt->getParent(), 1412572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman PHI->getIncomingBlock(i)) 1413572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman ->getTerminator(); 1414572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman } 1415572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman 1416572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // Now expand it into actual Instructions and patch it into place. 1417572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman Value *NewVal = Rewriter.expandCodeFor(AR, UseTy, InsertPt); 1418572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman 1419b12a754cce0c1d5542af605203a47820edba454dAndrew Trick DEBUG(dbgs() << "INDVARS: Rewrote IV '" << *AR << "' " << *Op << '\n' 1420b12a754cce0c1d5542af605203a47820edba454dAndrew Trick << " into = " << *NewVal << "\n"); 1421b12a754cce0c1d5542af605203a47820edba454dAndrew Trick 1422b12a754cce0c1d5542af605203a47820edba454dAndrew Trick if (!isValidRewrite(Op, NewVal)) { 1423b12a754cce0c1d5542af605203a47820edba454dAndrew Trick DeadInsts.push_back(NewVal); 1424b12a754cce0c1d5542af605203a47820edba454dAndrew Trick continue; 1425b12a754cce0c1d5542af605203a47820edba454dAndrew Trick } 1426d7bfd0028b273f2e3935e8c7ff95db6fa2b21789Dan Gohman // Inform ScalarEvolution that this value is changing. The change doesn't 1427d7bfd0028b273f2e3935e8c7ff95db6fa2b21789Dan Gohman // affect its value, but it does potentially affect which use lists the 1428d7bfd0028b273f2e3935e8c7ff95db6fa2b21789Dan Gohman // value will be on after the replacement, which affects ScalarEvolution's 1429d7bfd0028b273f2e3935e8c7ff95db6fa2b21789Dan Gohman // ability to walk use lists and drop dangling pointers when a value is 1430d7bfd0028b273f2e3935e8c7ff95db6fa2b21789Dan Gohman // deleted. 1431d7bfd0028b273f2e3935e8c7ff95db6fa2b21789Dan Gohman SE->forgetValue(User); 1432d7bfd0028b273f2e3935e8c7ff95db6fa2b21789Dan Gohman 1433572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // Patch the new value into place. 1434572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman if (Op->hasName()) 1435572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman NewVal->takeName(Op); 1436a098bf1239ca1769c93de52324d2b73adedad7b8Devang Patel if (Instruction *NewValI = dyn_cast<Instruction>(NewVal)) 1437a098bf1239ca1769c93de52324d2b73adedad7b8Devang Patel NewValI->setDebugLoc(User->getDebugLoc()); 1438572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman User->replaceUsesOfWith(Op, NewVal); 1439572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman UI->setOperandValToReplace(NewVal); 1440b12a754cce0c1d5542af605203a47820edba454dAndrew Trick 1441572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman ++NumRemoved; 1442572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman Changed = true; 1443572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman 1444572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // The old value may be dead now. 1445572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman DeadInsts.push_back(Op); 1446500597a1c39e91a3020587318ed61e737b6c613aChris Lattner } 144781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman} 144881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 144981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman/// If there's a single exit block, sink any loop-invariant values that 145081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman/// were defined in the preheader but not used inside the loop into the 145181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman/// exit block to reduce register pressure in the loop. 1452667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohmanvoid IndVarSimplify::SinkUnusedInvariants(Loop *L) { 145381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman BasicBlock *ExitBlock = L->getExitBlock(); 145481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (!ExitBlock) return; 145581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 145681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman BasicBlock *Preheader = L->getLoopPreheader(); 145703e896bd6073efc4523d8bcd0239d6ed62126db7Dan Gohman if (!Preheader) return; 145803e896bd6073efc4523d8bcd0239d6ed62126db7Dan Gohman 145903e896bd6073efc4523d8bcd0239d6ed62126db7Dan Gohman Instruction *InsertPt = ExitBlock->getFirstNonPHI(); 146081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman BasicBlock::iterator I = Preheader->getTerminator(); 146181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman while (I != Preheader->begin()) { 146281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman --I; 1463667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman // New instructions were inserted at the end of the preheader. 1464667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman if (isa<PHINode>(I)) 146581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman break; 146687a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling 14670c77db32dd8ae10b5a26d60718dbe03dc2745888Eli Friedman // Don't move instructions which might have side effects, since the side 146887a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling // effects need to complete before instructions inside the loop. Also don't 146987a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling // move instructions which might read memory, since the loop may modify 147087a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling // memory. Note that it's okay if the instruction might have undefined 147187a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling // behavior: LoopSimplify guarantees that the preheader dominates the exit 147287a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling // block. 14730c77db32dd8ae10b5a26d60718dbe03dc2745888Eli Friedman if (I->mayHaveSideEffects() || I->mayReadFromMemory()) 1474667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman continue; 147587a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling 14767b9f6b1b21bc0b06f3c72beae51e9db631319503Devang Patel // Skip debug info intrinsics. 14777b9f6b1b21bc0b06f3c72beae51e9db631319503Devang Patel if (isa<DbgInfoIntrinsic>(I)) 14787b9f6b1b21bc0b06f3c72beae51e9db631319503Devang Patel continue; 147987a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling 148076f497a351c562f366b5e93c27d3f1652fb48ff4Dan Gohman // Don't sink static AllocaInsts out of the entry block, which would 148176f497a351c562f366b5e93c27d3f1652fb48ff4Dan Gohman // turn them into dynamic allocas! 148276f497a351c562f366b5e93c27d3f1652fb48ff4Dan Gohman if (AllocaInst *AI = dyn_cast<AllocaInst>(I)) 148376f497a351c562f366b5e93c27d3f1652fb48ff4Dan Gohman if (AI->isStaticAlloca()) 148476f497a351c562f366b5e93c27d3f1652fb48ff4Dan Gohman continue; 148587a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling 148681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Determine if there is a use in or before the loop (direct or 148781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // otherwise). 148881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman bool UsedInLoop = false; 148981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman for (Value::use_iterator UI = I->use_begin(), UE = I->use_end(); 149081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman UI != UE; ++UI) { 14917656018c2268285907cfdc106071462a01a73878Gabor Greif User *U = *UI; 14927656018c2268285907cfdc106071462a01a73878Gabor Greif BasicBlock *UseBB = cast<Instruction>(U)->getParent(); 14937656018c2268285907cfdc106071462a01a73878Gabor Greif if (PHINode *P = dyn_cast<PHINode>(U)) { 149481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman unsigned i = 149581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman PHINode::getIncomingValueNumForOperand(UI.getOperandNo()); 149681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman UseBB = P->getIncomingBlock(i); 149781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman } 149881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (UseBB == Preheader || L->contains(UseBB)) { 149981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman UsedInLoop = true; 150081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman break; 150181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman } 150281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman } 150387a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling 150481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // If there is, the def must remain in the preheader. 150581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (UsedInLoop) 150681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman continue; 150787a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling 150881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Otherwise, sink it to the exit block. 150981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman Instruction *ToMove = I; 151081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman bool Done = false; 151187a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling 151287a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling if (I != Preheader->begin()) { 151387a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling // Skip debug info intrinsics. 151487a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling do { 151587a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling --I; 151687a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling } while (isa<DbgInfoIntrinsic>(I) && I != Preheader->begin()); 151787a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling 151887a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling if (isa<DbgInfoIntrinsic>(I) && I == Preheader->begin()) 151987a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling Done = true; 152087a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling } else { 152181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman Done = true; 152287a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling } 152387a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling 1524667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman ToMove->moveBefore(InsertPt); 152587a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling if (Done) break; 1526667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman InsertPt = ToMove; 152781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman } 152881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman} 152981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 1530bbb91498da1a4dc77332bf93d7c13060f0c63a70Chris Lattner/// ConvertToSInt - Convert APF to an integer, if possible. 1531bbb91498da1a4dc77332bf93d7c13060f0c63a70Chris Lattnerstatic bool ConvertToSInt(const APFloat &APF, int64_t &IntVal) { 1532cd40233429fce385ae4b22301ce705273a6951a1Devang Patel bool isExact = false; 1533794a7dbce030f93315b1305f83a374232f09bba5Evan Cheng if (&APF.getSemantics() == &APFloat::PPCDoubleDouble) 1534794a7dbce030f93315b1305f83a374232f09bba5Evan Cheng return false; 1535bbb91498da1a4dc77332bf93d7c13060f0c63a70Chris Lattner // See if we can convert this to an int64_t 1536bbb91498da1a4dc77332bf93d7c13060f0c63a70Chris Lattner uint64_t UIntVal; 1537bbb91498da1a4dc77332bf93d7c13060f0c63a70Chris Lattner if (APF.convertToInteger(&UIntVal, 64, true, APFloat::rmTowardZero, 1538bbb91498da1a4dc77332bf93d7c13060f0c63a70Chris Lattner &isExact) != APFloat::opOK || !isExact) 1539cd40233429fce385ae4b22301ce705273a6951a1Devang Patel return false; 1540bbb91498da1a4dc77332bf93d7c13060f0c63a70Chris Lattner IntVal = UIntVal; 1541cd40233429fce385ae4b22301ce705273a6951a1Devang Patel return true; 1542cd40233429fce385ae4b22301ce705273a6951a1Devang Patel} 1543cd40233429fce385ae4b22301ce705273a6951a1Devang Patel 154458d43d4a41b21085c063bdd21a2abb68056e2a6fDevang Patel/// HandleFloatingPointIV - If the loop has floating induction variable 154558d43d4a41b21085c063bdd21a2abb68056e2a6fDevang Patel/// then insert corresponding integer induction variable if possible. 154684e3515974407a606289c6e762a0419723b7918fDevang Patel/// For example, 154784e3515974407a606289c6e762a0419723b7918fDevang Patel/// for(double i = 0; i < 10000; ++i) 154884e3515974407a606289c6e762a0419723b7918fDevang Patel/// bar(i) 154984e3515974407a606289c6e762a0419723b7918fDevang Patel/// is converted into 155084e3515974407a606289c6e762a0419723b7918fDevang Patel/// for(int i = 0; i < 10000; ++i) 155184e3515974407a606289c6e762a0419723b7918fDevang Patel/// bar((double)i); 155284e3515974407a606289c6e762a0419723b7918fDevang Patel/// 1553c91961e31b2a1cae655928e20b83cb6a457fdcd4Chris Lattnervoid IndVarSimplify::HandleFloatingPointIV(Loop *L, PHINode *PN) { 1554c91961e31b2a1cae655928e20b83cb6a457fdcd4Chris Lattner unsigned IncomingEdge = L->contains(PN->getIncomingBlock(0)); 155584e3515974407a606289c6e762a0419723b7918fDevang Patel unsigned BackEdge = IncomingEdge^1; 1556cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 155784e3515974407a606289c6e762a0419723b7918fDevang Patel // Check incoming value. 1558c4f7e8061de19172d4c3f70a80447505b792e450Chris Lattner ConstantFP *InitValueVal = 1559c91961e31b2a1cae655928e20b83cb6a457fdcd4Chris Lattner dyn_cast<ConstantFP>(PN->getIncomingValue(IncomingEdge)); 156096fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner 1561bbb91498da1a4dc77332bf93d7c13060f0c63a70Chris Lattner int64_t InitValue; 156296fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner if (!InitValueVal || !ConvertToSInt(InitValueVal->getValueAPF(), InitValue)) 1563cd40233429fce385ae4b22301ce705273a6951a1Devang Patel return; 1564cd40233429fce385ae4b22301ce705273a6951a1Devang Patel 1565c91961e31b2a1cae655928e20b83cb6a457fdcd4Chris Lattner // Check IV increment. Reject this PN if increment operation is not 1566cd40233429fce385ae4b22301ce705273a6951a1Devang Patel // an add or increment value can not be represented by an integer. 1567cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman BinaryOperator *Incr = 1568c91961e31b2a1cae655928e20b83cb6a457fdcd4Chris Lattner dyn_cast<BinaryOperator>(PN->getIncomingValue(BackEdge)); 156907aa76ad939e053c1992a03cbcb16aff74f26651Chris Lattner if (Incr == 0 || Incr->getOpcode() != Instruction::FAdd) return; 1570ead71d59a7685fbbbb92162556680abd9001d37bAndrew Trick 157107aa76ad939e053c1992a03cbcb16aff74f26651Chris Lattner // If this is not an add of the PHI with a constantfp, or if the constant fp 157207aa76ad939e053c1992a03cbcb16aff74f26651Chris Lattner // is not an integer, bail out. 1573c4f7e8061de19172d4c3f70a80447505b792e450Chris Lattner ConstantFP *IncValueVal = dyn_cast<ConstantFP>(Incr->getOperand(1)); 157496fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner int64_t IncValue; 1575c91961e31b2a1cae655928e20b83cb6a457fdcd4Chris Lattner if (IncValueVal == 0 || Incr->getOperand(0) != PN || 157696fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner !ConvertToSInt(IncValueVal->getValueAPF(), IncValue)) 1577cd40233429fce385ae4b22301ce705273a6951a1Devang Patel return; 1578cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 1579c91961e31b2a1cae655928e20b83cb6a457fdcd4Chris Lattner // Check Incr uses. One user is PN and the other user is an exit condition 158007aa76ad939e053c1992a03cbcb16aff74f26651Chris Lattner // used by the conditional terminator. 158184e3515974407a606289c6e762a0419723b7918fDevang Patel Value::use_iterator IncrUse = Incr->use_begin(); 158296f1d8ebdd33b3f9bdb3b1163f36072c68599f42Gabor Greif Instruction *U1 = cast<Instruction>(*IncrUse++); 158384e3515974407a606289c6e762a0419723b7918fDevang Patel if (IncrUse == Incr->use_end()) return; 158496f1d8ebdd33b3f9bdb3b1163f36072c68599f42Gabor Greif Instruction *U2 = cast<Instruction>(*IncrUse++); 158584e3515974407a606289c6e762a0419723b7918fDevang Patel if (IncrUse != Incr->use_end()) return; 1586cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 158707aa76ad939e053c1992a03cbcb16aff74f26651Chris Lattner // Find exit condition, which is an fcmp. If it doesn't exist, or if it isn't 158807aa76ad939e053c1992a03cbcb16aff74f26651Chris Lattner // only used by a branch, we can't transform it. 1589ca703bd56ba1f717b3735c6889334c319ca005b1Chris Lattner FCmpInst *Compare = dyn_cast<FCmpInst>(U1); 1590ca703bd56ba1f717b3735c6889334c319ca005b1Chris Lattner if (!Compare) 1591ca703bd56ba1f717b3735c6889334c319ca005b1Chris Lattner Compare = dyn_cast<FCmpInst>(U2); 1592ca703bd56ba1f717b3735c6889334c319ca005b1Chris Lattner if (Compare == 0 || !Compare->hasOneUse() || 1593ca703bd56ba1f717b3735c6889334c319ca005b1Chris Lattner !isa<BranchInst>(Compare->use_back())) 159407aa76ad939e053c1992a03cbcb16aff74f26651Chris Lattner return; 1595ead71d59a7685fbbbb92162556680abd9001d37bAndrew Trick 1596ca703bd56ba1f717b3735c6889334c319ca005b1Chris Lattner BranchInst *TheBr = cast<BranchInst>(Compare->use_back()); 159784e3515974407a606289c6e762a0419723b7918fDevang Patel 1598d52c072777b9c9a9df9041b8b6cd199df7e43394Chris Lattner // We need to verify that the branch actually controls the iteration count 1599d52c072777b9c9a9df9041b8b6cd199df7e43394Chris Lattner // of the loop. If not, the new IV can overflow and no one will notice. 1600d52c072777b9c9a9df9041b8b6cd199df7e43394Chris Lattner // The branch block must be in the loop and one of the successors must be out 1601d52c072777b9c9a9df9041b8b6cd199df7e43394Chris Lattner // of the loop. 1602d52c072777b9c9a9df9041b8b6cd199df7e43394Chris Lattner assert(TheBr->isConditional() && "Can't use fcmp if not conditional"); 1603d52c072777b9c9a9df9041b8b6cd199df7e43394Chris Lattner if (!L->contains(TheBr->getParent()) || 1604d52c072777b9c9a9df9041b8b6cd199df7e43394Chris Lattner (L->contains(TheBr->getSuccessor(0)) && 1605d52c072777b9c9a9df9041b8b6cd199df7e43394Chris Lattner L->contains(TheBr->getSuccessor(1)))) 1606d52c072777b9c9a9df9041b8b6cd199df7e43394Chris Lattner return; 1607ead71d59a7685fbbbb92162556680abd9001d37bAndrew Trick 1608ead71d59a7685fbbbb92162556680abd9001d37bAndrew Trick 160907aa76ad939e053c1992a03cbcb16aff74f26651Chris Lattner // If it isn't a comparison with an integer-as-fp (the exit value), we can't 161007aa76ad939e053c1992a03cbcb16aff74f26651Chris Lattner // transform it. 1611ca703bd56ba1f717b3735c6889334c319ca005b1Chris Lattner ConstantFP *ExitValueVal = dyn_cast<ConstantFP>(Compare->getOperand(1)); 1612bbb91498da1a4dc77332bf93d7c13060f0c63a70Chris Lattner int64_t ExitValue; 1613bbb91498da1a4dc77332bf93d7c13060f0c63a70Chris Lattner if (ExitValueVal == 0 || 1614bbb91498da1a4dc77332bf93d7c13060f0c63a70Chris Lattner !ConvertToSInt(ExitValueVal->getValueAPF(), ExitValue)) 161584e3515974407a606289c6e762a0419723b7918fDevang Patel return; 1616ead71d59a7685fbbbb92162556680abd9001d37bAndrew Trick 161784e3515974407a606289c6e762a0419723b7918fDevang Patel // Find new predicate for integer comparison. 161884e3515974407a606289c6e762a0419723b7918fDevang Patel CmpInst::Predicate NewPred = CmpInst::BAD_ICMP_PREDICATE; 1619ca703bd56ba1f717b3735c6889334c319ca005b1Chris Lattner switch (Compare->getPredicate()) { 1620c4f7e8061de19172d4c3f70a80447505b792e450Chris Lattner default: return; // Unknown comparison. 162184e3515974407a606289c6e762a0419723b7918fDevang Patel case CmpInst::FCMP_OEQ: 1622c4f7e8061de19172d4c3f70a80447505b792e450Chris Lattner case CmpInst::FCMP_UEQ: NewPred = CmpInst::ICMP_EQ; break; 162396fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner case CmpInst::FCMP_ONE: 162496fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner case CmpInst::FCMP_UNE: NewPred = CmpInst::ICMP_NE; break; 162584e3515974407a606289c6e762a0419723b7918fDevang Patel case CmpInst::FCMP_OGT: 1626a40e4a0c8abbfe55d25a77e4e98508e43ed1c3aeChris Lattner case CmpInst::FCMP_UGT: NewPred = CmpInst::ICMP_SGT; break; 162784e3515974407a606289c6e762a0419723b7918fDevang Patel case CmpInst::FCMP_OGE: 1628a40e4a0c8abbfe55d25a77e4e98508e43ed1c3aeChris Lattner case CmpInst::FCMP_UGE: NewPred = CmpInst::ICMP_SGE; break; 162984e3515974407a606289c6e762a0419723b7918fDevang Patel case CmpInst::FCMP_OLT: 163043b85273ee11536c81b14dca0114cd8b9407db8eChris Lattner case CmpInst::FCMP_ULT: NewPred = CmpInst::ICMP_SLT; break; 163184e3515974407a606289c6e762a0419723b7918fDevang Patel case CmpInst::FCMP_OLE: 163243b85273ee11536c81b14dca0114cd8b9407db8eChris Lattner case CmpInst::FCMP_ULE: NewPred = CmpInst::ICMP_SLE; break; 163358d43d4a41b21085c063bdd21a2abb68056e2a6fDevang Patel } 1634ead71d59a7685fbbbb92162556680abd9001d37bAndrew Trick 163596fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner // We convert the floating point induction variable to a signed i32 value if 163696fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner // we can. This is only safe if the comparison will not overflow in a way 163796fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner // that won't be trapped by the integer equivalent operations. Check for this 163896fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner // now. 163996fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner // TODO: We could use i64 if it is native and the range requires it. 1640ead71d59a7685fbbbb92162556680abd9001d37bAndrew Trick 164196fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner // The start/stride/exit values must all fit in signed i32. 164296fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner if (!isInt<32>(InitValue) || !isInt<32>(IncValue) || !isInt<32>(ExitValue)) 164396fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner return; 164496fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner 164596fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner // If not actually striding (add x, 0.0), avoid touching the code. 164696fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner if (IncValue == 0) 164796fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner return; 164896fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner 164996fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner // Positive and negative strides have different safety conditions. 165096fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner if (IncValue > 0) { 165196fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner // If we have a positive stride, we require the init to be less than the 165296fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner // exit value and an equality or less than comparison. 165396fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner if (InitValue >= ExitValue || 165496fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner NewPred == CmpInst::ICMP_SGT || NewPred == CmpInst::ICMP_SGE) 165596fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner return; 1656ead71d59a7685fbbbb92162556680abd9001d37bAndrew Trick 165796fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner uint32_t Range = uint32_t(ExitValue-InitValue); 165896fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner if (NewPred == CmpInst::ICMP_SLE) { 165996fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner // Normalize SLE -> SLT, check for infinite loop. 166096fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner if (++Range == 0) return; // Range overflows. 166196fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner } 1662ead71d59a7685fbbbb92162556680abd9001d37bAndrew Trick 166396fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner unsigned Leftover = Range % uint32_t(IncValue); 1664ead71d59a7685fbbbb92162556680abd9001d37bAndrew Trick 166596fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner // If this is an equality comparison, we require that the strided value 166696fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner // exactly land on the exit value, otherwise the IV condition will wrap 166796fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner // around and do things the fp IV wouldn't. 166896fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner if ((NewPred == CmpInst::ICMP_EQ || NewPred == CmpInst::ICMP_NE) && 166996fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner Leftover != 0) 167096fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner return; 1671ead71d59a7685fbbbb92162556680abd9001d37bAndrew Trick 167296fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner // If the stride would wrap around the i32 before exiting, we can't 167396fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner // transform the IV. 167496fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner if (Leftover != 0 && int32_t(ExitValue+IncValue) < ExitValue) 167596fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner return; 1676ead71d59a7685fbbbb92162556680abd9001d37bAndrew Trick 167796fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner } else { 167896fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner // If we have a negative stride, we require the init to be greater than the 167996fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner // exit value and an equality or greater than comparison. 168096fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner if (InitValue >= ExitValue || 168196fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner NewPred == CmpInst::ICMP_SLT || NewPred == CmpInst::ICMP_SLE) 168296fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner return; 1683ead71d59a7685fbbbb92162556680abd9001d37bAndrew Trick 168496fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner uint32_t Range = uint32_t(InitValue-ExitValue); 168596fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner if (NewPred == CmpInst::ICMP_SGE) { 168696fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner // Normalize SGE -> SGT, check for infinite loop. 168796fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner if (++Range == 0) return; // Range overflows. 168896fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner } 1689ead71d59a7685fbbbb92162556680abd9001d37bAndrew Trick 169096fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner unsigned Leftover = Range % uint32_t(-IncValue); 1691ead71d59a7685fbbbb92162556680abd9001d37bAndrew Trick 169296fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner // If this is an equality comparison, we require that the strided value 169396fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner // exactly land on the exit value, otherwise the IV condition will wrap 169496fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner // around and do things the fp IV wouldn't. 169596fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner if ((NewPred == CmpInst::ICMP_EQ || NewPred == CmpInst::ICMP_NE) && 169696fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner Leftover != 0) 169796fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner return; 1698ead71d59a7685fbbbb92162556680abd9001d37bAndrew Trick 169996fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner // If the stride would wrap around the i32 before exiting, we can't 170096fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner // transform the IV. 170196fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner if (Leftover != 0 && int32_t(ExitValue+IncValue) > ExitValue) 170296fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner return; 170396fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner } 1704ead71d59a7685fbbbb92162556680abd9001d37bAndrew Trick 170596fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner const IntegerType *Int32Ty = Type::getInt32Ty(PN->getContext()); 1706cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 1707bbb91498da1a4dc77332bf93d7c13060f0c63a70Chris Lattner // Insert new integer induction variable. 17083ecfc861b4365f341c5c969b40e1afccde676e6fJay Foad PHINode *NewPHI = PHINode::Create(Int32Ty, 2, PN->getName()+".int", PN); 1709c4f7e8061de19172d4c3f70a80447505b792e450Chris Lattner NewPHI->addIncoming(ConstantInt::get(Int32Ty, InitValue), 1710c91961e31b2a1cae655928e20b83cb6a457fdcd4Chris Lattner PN->getIncomingBlock(IncomingEdge)); 171184e3515974407a606289c6e762a0419723b7918fDevang Patel 1712c4f7e8061de19172d4c3f70a80447505b792e450Chris Lattner Value *NewAdd = 171396fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner BinaryOperator::CreateAdd(NewPHI, ConstantInt::get(Int32Ty, IncValue), 1714c4f7e8061de19172d4c3f70a80447505b792e450Chris Lattner Incr->getName()+".int", Incr); 1715c91961e31b2a1cae655928e20b83cb6a457fdcd4Chris Lattner NewPHI->addIncoming(NewAdd, PN->getIncomingBlock(BackEdge)); 171684e3515974407a606289c6e762a0419723b7918fDevang Patel 1717ca703bd56ba1f717b3735c6889334c319ca005b1Chris Lattner ICmpInst *NewCompare = new ICmpInst(TheBr, NewPred, NewAdd, 1718ca703bd56ba1f717b3735c6889334c319ca005b1Chris Lattner ConstantInt::get(Int32Ty, ExitValue), 1719ca703bd56ba1f717b3735c6889334c319ca005b1Chris Lattner Compare->getName()); 1720cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 1721c91961e31b2a1cae655928e20b83cb6a457fdcd4Chris Lattner // In the following deletions, PN may become dead and may be deleted. 172281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Use a WeakVH to observe whether this happens. 1723c91961e31b2a1cae655928e20b83cb6a457fdcd4Chris Lattner WeakVH WeakPH = PN; 172481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 1725ca703bd56ba1f717b3735c6889334c319ca005b1Chris Lattner // Delete the old floating point exit comparison. The branch starts using the 1726ca703bd56ba1f717b3735c6889334c319ca005b1Chris Lattner // new comparison. 1727ca703bd56ba1f717b3735c6889334c319ca005b1Chris Lattner NewCompare->takeName(Compare); 1728ca703bd56ba1f717b3735c6889334c319ca005b1Chris Lattner Compare->replaceAllUsesWith(NewCompare); 1729ca703bd56ba1f717b3735c6889334c319ca005b1Chris Lattner RecursivelyDeleteTriviallyDeadInstructions(Compare); 1730cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 1731ca703bd56ba1f717b3735c6889334c319ca005b1Chris Lattner // Delete the old floating point increment. 17329e9a0d5fc26878e51a58a8b57900fcbf952c2691Owen Anderson Incr->replaceAllUsesWith(UndefValue::get(Incr->getType())); 173381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman RecursivelyDeleteTriviallyDeadInstructions(Incr); 173481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 173570c0d4f7eb9c14bccc8a585be4086712e46bfbdbChris Lattner // If the FP induction variable still has uses, this is because something else 173670c0d4f7eb9c14bccc8a585be4086712e46bfbdbChris Lattner // in the loop uses its value. In order to canonicalize the induction 173770c0d4f7eb9c14bccc8a585be4086712e46bfbdbChris Lattner // variable, we chose to eliminate the IV and rewrite it in terms of an 173870c0d4f7eb9c14bccc8a585be4086712e46bfbdbChris Lattner // int->fp cast. 173970c0d4f7eb9c14bccc8a585be4086712e46bfbdbChris Lattner // 174070c0d4f7eb9c14bccc8a585be4086712e46bfbdbChris Lattner // We give preference to sitofp over uitofp because it is faster on most 174170c0d4f7eb9c14bccc8a585be4086712e46bfbdbChris Lattner // platforms. 174270c0d4f7eb9c14bccc8a585be4086712e46bfbdbChris Lattner if (WeakPH) { 1743a40e4a0c8abbfe55d25a77e4e98508e43ed1c3aeChris Lattner Value *Conv = new SIToFPInst(NewPHI, PN->getType(), "indvar.conv", 1744a40e4a0c8abbfe55d25a77e4e98508e43ed1c3aeChris Lattner PN->getParent()->getFirstNonPHI()); 1745a40e4a0c8abbfe55d25a77e4e98508e43ed1c3aeChris Lattner PN->replaceAllUsesWith(Conv); 1746c91961e31b2a1cae655928e20b83cb6a457fdcd4Chris Lattner RecursivelyDeleteTriviallyDeadInstructions(PN); 1747cd40233429fce385ae4b22301ce705273a6951a1Devang Patel } 174858d43d4a41b21085c063bdd21a2abb68056e2a6fDevang Patel 174981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Add a new IVUsers entry for the newly-created integer PHI. 17502fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick if (IU) 17514417e537b65c14b378aeca75b2773582dd102f63Andrew Trick IU->AddUsersIfInteresting(NewPHI); 175281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman} 1753