IndVarSimplify.cpp revision fc933c073e9357a791c0f6b307355ed735e3557f
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" 61037d1c0c7e01cefeff7e538682c9a1e536e14030Andrew Trick#include "llvm/ADT/DenseMap.h" 62a54b7cbd452b3adb2f51346140d996b29c2cdb30Reid Spencer#include "llvm/ADT/SmallVector.h" 63551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/Statistic.h" 6481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman#include "llvm/ADT/STLExtras.h" 6547df12d80db90e125e9f2ff764286ee11665476dJohn Criswellusing namespace llvm; 66d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 672fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew TrickSTATISTIC(NumRemoved , "Number of aux indvars removed"); 682fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew TrickSTATISTIC(NumWidened , "Number of indvars widened"); 692fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew TrickSTATISTIC(NumInserted , "Number of canonical indvars added"); 702fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew TrickSTATISTIC(NumReplaced , "Number of exit values replaced"); 712fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew TrickSTATISTIC(NumLFTR , "Number of loop exit tests replaced"); 722fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew TrickSTATISTIC(NumElimIdentity, "Number of IV identities eliminated"); 732fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew TrickSTATISTIC(NumElimExt , "Number of IV sign/zero extends eliminated"); 742fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew TrickSTATISTIC(NumElimRem , "Number of IV remainder operations eliminated"); 752fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew TrickSTATISTIC(NumElimCmp , "Number of IV comparisons eliminated"); 76037d1c0c7e01cefeff7e538682c9a1e536e14030Andrew TrickSTATISTIC(NumElimIV , "Number of congruent IVs eliminated"); 773324e718bc9ac2ede08a14c325848b576849542bChris Lattner 7856caa098085977c14cfab39d92c7dfa15dde0d90Andrew Trickstatic cl::opt<bool> DisableIVRewrite( 7956caa098085977c14cfab39d92c7dfa15dde0d90Andrew Trick "disable-iv-rewrite", cl::Hidden, 8056caa098085977c14cfab39d92c7dfa15dde0d90Andrew Trick cl::desc("Disable canonical induction variable rewriting")); 8137da40875873d70b83dc08b2803052bec9b68886Andrew Trick 82fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick// Temporary flag for use with -disable-iv-rewrite to force a canonical IV for 83fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick// LFTR purposes. 84fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trickstatic cl::opt<bool> ForceLFTR( 85fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick "force-lftr", cl::Hidden, 86fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick cl::desc("Enable forced linear function test replacement")); 87fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick 880e5f499638c8d277b9dc4a4385712177c53b5681Chris Lattnernamespace { 893e8b6631e67e01e4960a7ba4668a50c596607473Chris Lattner class IndVarSimplify : public LoopPass { 9081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman IVUsers *IU; 9140bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner LoopInfo *LI; 9240bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner ScalarEvolution *SE; 93de53dc03f5c1549f3176e979bbeeac965dfa5cbcDan Gohman DominatorTree *DT; 9437da40875873d70b83dc08b2803052bec9b68886Andrew Trick TargetData *TD; 952fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick 96b12a754cce0c1d5542af605203a47820edba454dAndrew Trick SmallVector<WeakVH, 16> DeadInsts; 9715cad759fe2048ac5eb137c6bb0ab7287538677eChris Lattner bool Changed; 983324e718bc9ac2ede08a14c325848b576849542bChris Lattner public: 99794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel 1005668cf77a77493ec9f2a9b33f08125e885c8e4cfDan Gohman static char ID; // Pass identification, replacement for typeid 1012fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick IndVarSimplify() : LoopPass(ID), IU(0), LI(0), SE(0), DT(0), TD(0), 10215832f61775040995bb8aa6056176425bc2c9088Andrew Trick Changed(false) { 103081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeIndVarSimplifyPass(*PassRegistry::getPassRegistry()); 104081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson } 105794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel 1065668cf77a77493ec9f2a9b33f08125e885c8e4cfDan Gohman virtual bool runOnLoop(Loop *L, LPPassManager &LPM); 10760f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman 1085668cf77a77493ec9f2a9b33f08125e885c8e4cfDan Gohman virtual void getAnalysisUsage(AnalysisUsage &AU) const { 1095668cf77a77493ec9f2a9b33f08125e885c8e4cfDan Gohman AU.addRequired<DominatorTree>(); 1105668cf77a77493ec9f2a9b33f08125e885c8e4cfDan Gohman AU.addRequired<LoopInfo>(); 1115668cf77a77493ec9f2a9b33f08125e885c8e4cfDan Gohman AU.addRequired<ScalarEvolution>(); 1125668cf77a77493ec9f2a9b33f08125e885c8e4cfDan Gohman AU.addRequiredID(LoopSimplifyID); 1135668cf77a77493ec9f2a9b33f08125e885c8e4cfDan Gohman AU.addRequiredID(LCSSAID); 11456caa098085977c14cfab39d92c7dfa15dde0d90Andrew Trick if (!DisableIVRewrite) 11556caa098085977c14cfab39d92c7dfa15dde0d90Andrew Trick AU.addRequired<IVUsers>(); 1165668cf77a77493ec9f2a9b33f08125e885c8e4cfDan Gohman AU.addPreserved<ScalarEvolution>(); 1175668cf77a77493ec9f2a9b33f08125e885c8e4cfDan Gohman AU.addPreservedID(LoopSimplifyID); 1185668cf77a77493ec9f2a9b33f08125e885c8e4cfDan Gohman AU.addPreservedID(LCSSAID); 1192fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick if (!DisableIVRewrite) 1202fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick AU.addPreserved<IVUsers>(); 1215668cf77a77493ec9f2a9b33f08125e885c8e4cfDan Gohman AU.setPreservesCFG(); 1225668cf77a77493ec9f2a9b33f08125e885c8e4cfDan Gohman } 1233324e718bc9ac2ede08a14c325848b576849542bChris Lattner 12440bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner private: 125037d1c0c7e01cefeff7e538682c9a1e536e14030Andrew Trick virtual void releaseMemory() { 126037d1c0c7e01cefeff7e538682c9a1e536e14030Andrew Trick DeadInsts.clear(); 127037d1c0c7e01cefeff7e538682c9a1e536e14030Andrew Trick } 128037d1c0c7e01cefeff7e538682c9a1e536e14030Andrew Trick 129b12a754cce0c1d5542af605203a47820edba454dAndrew Trick bool isValidRewrite(Value *FromVal, Value *ToVal); 1305ee99979065d75605d150d7e567e4351024aae8fDevang Patel 1311a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick void HandleFloatingPointIV(Loop *L, PHINode *PH); 1321a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick void RewriteNonIntegerIVs(Loop *L); 1331a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 1341a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick void RewriteLoopExitValues(Loop *L, SCEVExpander &Rewriter); 1351a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 136f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick void SimplifyIVUsers(SCEVExpander &Rewriter); 1372fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick void SimplifyIVUsersNoRewrite(Loop *L, SCEVExpander &Rewriter); 1382fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick 1392fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick bool EliminateIVUser(Instruction *UseInst, Instruction *IVOperand); 140aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick void EliminateIVComparison(ICmpInst *ICmp, Value *IVOperand); 141aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick void EliminateIVRemainder(BinaryOperator *Rem, 142aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick Value *IVOperand, 1434417e537b65c14b378aeca75b2773582dd102f63Andrew Trick bool IsSigned); 14440bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner 145037d1c0c7e01cefeff7e538682c9a1e536e14030Andrew Trick void SimplifyCongruentIVs(Loop *L); 146037d1c0c7e01cefeff7e538682c9a1e536e14030Andrew Trick 147454d26dc43207ec537d843229db6f5e6a302e23dDan Gohman void RewriteIVExpressions(Loop *L, SCEVExpander &Rewriter); 148d22a849282c45bbf7eb1734c274294d81e49e3a8Devang Patel 149fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick Value *LinearFunctionTestReplace(Loop *L, const SCEV *BackedgeTakenCount, 150fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick PHINode *IndVar, SCEVExpander &Rewriter); 15181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 1521a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick void SinkUnusedInvariants(Loop *L); 1533324e718bc9ac2ede08a14c325848b576849542bChris Lattner }; 1545e76140536ba66fadeced1cd892f79616f407e3cChris Lattner} 155394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner 156844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanchar IndVarSimplify::ID = 0; 1572ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_BEGIN(IndVarSimplify, "indvars", 15837da40875873d70b83dc08b2803052bec9b68886Andrew Trick "Induction Variable Simplification", false, false) 1592ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(DominatorTree) 1602ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(LoopInfo) 1612ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(ScalarEvolution) 1622ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(LoopSimplify) 1632ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(LCSSA) 1642ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(IVUsers) 1652ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_END(IndVarSimplify, "indvars", 16637da40875873d70b83dc08b2803052bec9b68886Andrew Trick "Induction Variable Simplification", false, false) 167844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 168394f0441e06dafca29f0752cf400990a5b8fe4b1Daniel DunbarPass *llvm::createIndVarSimplifyPass() { 1693324e718bc9ac2ede08a14c325848b576849542bChris Lattner return new IndVarSimplify(); 170394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner} 171394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner 172b12a754cce0c1d5542af605203a47820edba454dAndrew Trick/// isValidRewrite - Return true if the SCEV expansion generated by the 173b12a754cce0c1d5542af605203a47820edba454dAndrew Trick/// rewriter can replace the original value. SCEV guarantees that it 174b12a754cce0c1d5542af605203a47820edba454dAndrew Trick/// produces the same value, but the way it is produced may be illegal IR. 175b12a754cce0c1d5542af605203a47820edba454dAndrew Trick/// Ideally, this function will only be called for verification. 176b12a754cce0c1d5542af605203a47820edba454dAndrew Trickbool IndVarSimplify::isValidRewrite(Value *FromVal, Value *ToVal) { 177b12a754cce0c1d5542af605203a47820edba454dAndrew Trick // If an SCEV expression subsumed multiple pointers, its expansion could 178b12a754cce0c1d5542af605203a47820edba454dAndrew Trick // reassociate the GEP changing the base pointer. This is illegal because the 179b12a754cce0c1d5542af605203a47820edba454dAndrew Trick // final address produced by a GEP chain must be inbounds relative to its 180b12a754cce0c1d5542af605203a47820edba454dAndrew Trick // underlying object. Otherwise basic alias analysis, among other things, 181b12a754cce0c1d5542af605203a47820edba454dAndrew Trick // could fail in a dangerous way. Ultimately, SCEV will be improved to avoid 182b12a754cce0c1d5542af605203a47820edba454dAndrew Trick // producing an expression involving multiple pointers. Until then, we must 183b12a754cce0c1d5542af605203a47820edba454dAndrew Trick // bail out here. 184b12a754cce0c1d5542af605203a47820edba454dAndrew Trick // 185b12a754cce0c1d5542af605203a47820edba454dAndrew Trick // Retrieve the pointer operand of the GEP. Don't use GetUnderlyingObject 186b12a754cce0c1d5542af605203a47820edba454dAndrew Trick // because it understands lcssa phis while SCEV does not. 187b12a754cce0c1d5542af605203a47820edba454dAndrew Trick Value *FromPtr = FromVal; 188b12a754cce0c1d5542af605203a47820edba454dAndrew Trick Value *ToPtr = ToVal; 189b12a754cce0c1d5542af605203a47820edba454dAndrew Trick if (GEPOperator *GEP = dyn_cast<GEPOperator>(FromVal)) { 190b12a754cce0c1d5542af605203a47820edba454dAndrew Trick FromPtr = GEP->getPointerOperand(); 191b12a754cce0c1d5542af605203a47820edba454dAndrew Trick } 192b12a754cce0c1d5542af605203a47820edba454dAndrew Trick if (GEPOperator *GEP = dyn_cast<GEPOperator>(ToVal)) { 193b12a754cce0c1d5542af605203a47820edba454dAndrew Trick ToPtr = GEP->getPointerOperand(); 194b12a754cce0c1d5542af605203a47820edba454dAndrew Trick } 195b12a754cce0c1d5542af605203a47820edba454dAndrew Trick if (FromPtr != FromVal || ToPtr != ToVal) { 196b12a754cce0c1d5542af605203a47820edba454dAndrew Trick // Quickly check the common case 197b12a754cce0c1d5542af605203a47820edba454dAndrew Trick if (FromPtr == ToPtr) 198b12a754cce0c1d5542af605203a47820edba454dAndrew Trick return true; 199b12a754cce0c1d5542af605203a47820edba454dAndrew Trick 200b12a754cce0c1d5542af605203a47820edba454dAndrew Trick // SCEV may have rewritten an expression that produces the GEP's pointer 201b12a754cce0c1d5542af605203a47820edba454dAndrew Trick // operand. That's ok as long as the pointer operand has the same base 202b12a754cce0c1d5542af605203a47820edba454dAndrew Trick // pointer. Unlike GetUnderlyingObject(), getPointerBase() will find the 203b12a754cce0c1d5542af605203a47820edba454dAndrew Trick // base of a recurrence. This handles the case in which SCEV expansion 204b12a754cce0c1d5542af605203a47820edba454dAndrew Trick // converts a pointer type recurrence into a nonrecurrent pointer base 205b12a754cce0c1d5542af605203a47820edba454dAndrew Trick // indexed by an integer recurrence. 206b12a754cce0c1d5542af605203a47820edba454dAndrew Trick const SCEV *FromBase = SE->getPointerBase(SE->getSCEV(FromPtr)); 207b12a754cce0c1d5542af605203a47820edba454dAndrew Trick const SCEV *ToBase = SE->getPointerBase(SE->getSCEV(ToPtr)); 208b12a754cce0c1d5542af605203a47820edba454dAndrew Trick if (FromBase == ToBase) 209b12a754cce0c1d5542af605203a47820edba454dAndrew Trick return true; 210b12a754cce0c1d5542af605203a47820edba454dAndrew Trick 211b12a754cce0c1d5542af605203a47820edba454dAndrew Trick DEBUG(dbgs() << "INDVARS: GEP rewrite bail out " 212b12a754cce0c1d5542af605203a47820edba454dAndrew Trick << *FromBase << " != " << *ToBase << "\n"); 213b12a754cce0c1d5542af605203a47820edba454dAndrew Trick 214b12a754cce0c1d5542af605203a47820edba454dAndrew Trick return false; 215b12a754cce0c1d5542af605203a47820edba454dAndrew Trick } 216b12a754cce0c1d5542af605203a47820edba454dAndrew Trick return true; 217b12a754cce0c1d5542af605203a47820edba454dAndrew Trick} 218b12a754cce0c1d5542af605203a47820edba454dAndrew Trick 2191a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick//===----------------------------------------------------------------------===// 2201a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick// RewriteNonIntegerIVs and helpers. Prefer integer IVs. 2211a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick//===----------------------------------------------------------------------===// 2224dfdf242c1917e98f407818eb5b68ae0b4678f26Andrew Trick 2231a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick/// ConvertToSInt - Convert APF to an integer, if possible. 2241a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trickstatic bool ConvertToSInt(const APFloat &APF, int64_t &IntVal) { 2251a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick bool isExact = false; 2261a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (&APF.getSemantics() == &APFloat::PPCDoubleDouble) 2274dfdf242c1917e98f407818eb5b68ae0b4678f26Andrew Trick return false; 2281a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // See if we can convert this to an int64_t 2291a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick uint64_t UIntVal; 2301a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (APF.convertToInteger(&UIntVal, 64, true, APFloat::rmTowardZero, 2311a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick &isExact) != APFloat::opOK || !isExact) 2324dfdf242c1917e98f407818eb5b68ae0b4678f26Andrew Trick return false; 2331a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick IntVal = UIntVal; 2344dfdf242c1917e98f407818eb5b68ae0b4678f26Andrew Trick return true; 2354dfdf242c1917e98f407818eb5b68ae0b4678f26Andrew Trick} 2364dfdf242c1917e98f407818eb5b68ae0b4678f26Andrew Trick 2371a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick/// HandleFloatingPointIV - If the loop has floating induction variable 2381a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick/// then insert corresponding integer induction variable if possible. 2391a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick/// For example, 2401a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick/// for(double i = 0; i < 10000; ++i) 2411a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick/// bar(i) 2421a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick/// is converted into 2431a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick/// for(int i = 0; i < 10000; ++i) 2441a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick/// bar((double)i); 24503d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick/// 2461a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trickvoid IndVarSimplify::HandleFloatingPointIV(Loop *L, PHINode *PN) { 2471a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick unsigned IncomingEdge = L->contains(PN->getIncomingBlock(0)); 2481a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick unsigned BackEdge = IncomingEdge^1; 24903d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick 2501a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // Check incoming value. 2511a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick ConstantFP *InitValueVal = 2521a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick dyn_cast<ConstantFP>(PN->getIncomingValue(IncomingEdge)); 25303d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick 2541a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick int64_t InitValue; 2551a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (!InitValueVal || !ConvertToSInt(InitValueVal->getValueAPF(), InitValue)) 2561a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick return; 25703d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick 2581a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // Check IV increment. Reject this PN if increment operation is not 2591a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // an add or increment value can not be represented by an integer. 2601a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick BinaryOperator *Incr = 2611a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick dyn_cast<BinaryOperator>(PN->getIncomingValue(BackEdge)); 2621a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (Incr == 0 || Incr->getOpcode() != Instruction::FAdd) return; 26303d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick 2641a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // If this is not an add of the PHI with a constantfp, or if the constant fp 2651a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // is not an integer, bail out. 2661a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick ConstantFP *IncValueVal = dyn_cast<ConstantFP>(Incr->getOperand(1)); 2671a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick int64_t IncValue; 2681a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (IncValueVal == 0 || Incr->getOperand(0) != PN || 2691a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick !ConvertToSInt(IncValueVal->getValueAPF(), IncValue)) 2701a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick return; 27103d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick 2721a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // Check Incr uses. One user is PN and the other user is an exit condition 2731a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // used by the conditional terminator. 2741a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick Value::use_iterator IncrUse = Incr->use_begin(); 2751a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick Instruction *U1 = cast<Instruction>(*IncrUse++); 2761a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (IncrUse == Incr->use_end()) return; 2771a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick Instruction *U2 = cast<Instruction>(*IncrUse++); 2781a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (IncrUse != Incr->use_end()) return; 279ca9b7037e28759c200fe5ca98190cabd121a1bbaDan Gohman 2801a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // Find exit condition, which is an fcmp. If it doesn't exist, or if it isn't 2811a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // only used by a branch, we can't transform it. 2821a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick FCmpInst *Compare = dyn_cast<FCmpInst>(U1); 2831a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (!Compare) 2841a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick Compare = dyn_cast<FCmpInst>(U2); 2851a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (Compare == 0 || !Compare->hasOneUse() || 2861a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick !isa<BranchInst>(Compare->use_back())) 2871a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick return; 288c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman 2891a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick BranchInst *TheBr = cast<BranchInst>(Compare->use_back()); 29059fdaeeae8f183e18bb6ad5c382ca23e28e6aaf6Chris Lattner 2911a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // We need to verify that the branch actually controls the iteration count 2921a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // of the loop. If not, the new IV can overflow and no one will notice. 2931a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // The branch block must be in the loop and one of the successors must be out 2941a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // of the loop. 2951a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick assert(TheBr->isConditional() && "Can't use fcmp if not conditional"); 2961a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (!L->contains(TheBr->getParent()) || 2971a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick (L->contains(TheBr->getSuccessor(0)) && 2981a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick L->contains(TheBr->getSuccessor(1)))) 2991a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick return; 30040bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner 30140bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner 3021a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // If it isn't a comparison with an integer-as-fp (the exit value), we can't 3031a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // transform it. 3041a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick ConstantFP *ExitValueVal = dyn_cast<ConstantFP>(Compare->getOperand(1)); 3051a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick int64_t ExitValue; 3061a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (ExitValueVal == 0 || 3071a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick !ConvertToSInt(ExitValueVal->getValueAPF(), ExitValue)) 3081a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick return; 309c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman 3101a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // Find new predicate for integer comparison. 3111a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick CmpInst::Predicate NewPred = CmpInst::BAD_ICMP_PREDICATE; 3121a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick switch (Compare->getPredicate()) { 3131a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick default: return; // Unknown comparison. 3141a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick case CmpInst::FCMP_OEQ: 3151a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick case CmpInst::FCMP_UEQ: NewPred = CmpInst::ICMP_EQ; break; 3161a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick case CmpInst::FCMP_ONE: 3171a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick case CmpInst::FCMP_UNE: NewPred = CmpInst::ICMP_NE; break; 3181a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick case CmpInst::FCMP_OGT: 3191a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick case CmpInst::FCMP_UGT: NewPred = CmpInst::ICMP_SGT; break; 3201a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick case CmpInst::FCMP_OGE: 3211a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick case CmpInst::FCMP_UGE: NewPred = CmpInst::ICMP_SGE; break; 3221a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick case CmpInst::FCMP_OLT: 3231a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick case CmpInst::FCMP_ULT: NewPred = CmpInst::ICMP_SLT; break; 3241a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick case CmpInst::FCMP_OLE: 3251a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick case CmpInst::FCMP_ULE: NewPred = CmpInst::ICMP_SLE; break; 3261a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick } 32781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 3281a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // We convert the floating point induction variable to a signed i32 value if 3291a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // we can. This is only safe if the comparison will not overflow in a way 3301a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // that won't be trapped by the integer equivalent operations. Check for this 3311a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // now. 3321a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // TODO: We could use i64 if it is native and the range requires it. 3333324e718bc9ac2ede08a14c325848b576849542bChris Lattner 3341a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // The start/stride/exit values must all fit in signed i32. 3351a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (!isInt<32>(InitValue) || !isInt<32>(IncValue) || !isInt<32>(ExitValue)) 3361a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick return; 33781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 3381a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // If not actually striding (add x, 0.0), avoid touching the code. 3391a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (IncValue == 0) 3401a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick return; 3411a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 3421a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // Positive and negative strides have different safety conditions. 3431a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (IncValue > 0) { 3441a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // If we have a positive stride, we require the init to be less than the 3451a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // exit value and an equality or less than comparison. 3461a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (InitValue >= ExitValue || 3471a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick NewPred == CmpInst::ICMP_SGT || NewPred == CmpInst::ICMP_SGE) 3481a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick return; 3491a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 3501a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick uint32_t Range = uint32_t(ExitValue-InitValue); 3511a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (NewPred == CmpInst::ICMP_SLE) { 3521a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // Normalize SLE -> SLT, check for infinite loop. 3531a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (++Range == 0) return; // Range overflows. 3541a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick } 3551a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 3561a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick unsigned Leftover = Range % uint32_t(IncValue); 3571a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 3581a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // If this is an equality comparison, we require that the strided value 3591a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // exactly land on the exit value, otherwise the IV condition will wrap 3601a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // around and do things the fp IV wouldn't. 3611a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if ((NewPred == CmpInst::ICMP_EQ || NewPred == CmpInst::ICMP_NE) && 3621a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick Leftover != 0) 3631a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick return; 3641a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 3651a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // If the stride would wrap around the i32 before exiting, we can't 3661a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // transform the IV. 3671a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (Leftover != 0 && int32_t(ExitValue+IncValue) < ExitValue) 3681a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick return; 3691a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 3701a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick } else { 3711a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // If we have a negative stride, we require the init to be greater than the 3721a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // exit value and an equality or greater than comparison. 3731a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (InitValue >= ExitValue || 3741a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick NewPred == CmpInst::ICMP_SLT || NewPred == CmpInst::ICMP_SLE) 3751a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick return; 3761a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 3771a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick uint32_t Range = uint32_t(InitValue-ExitValue); 3781a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (NewPred == CmpInst::ICMP_SGE) { 3791a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // Normalize SGE -> SGT, check for infinite loop. 3801a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (++Range == 0) return; // Range overflows. 3811a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick } 3821a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 3831a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick unsigned Leftover = Range % uint32_t(-IncValue); 3841a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 3851a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // If this is an equality comparison, we require that the strided value 3861a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // exactly land on the exit value, otherwise the IV condition will wrap 3871a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // around and do things the fp IV wouldn't. 3881a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if ((NewPred == CmpInst::ICMP_EQ || NewPred == CmpInst::ICMP_NE) && 3891a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick Leftover != 0) 3901a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick return; 3911a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 3921a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // If the stride would wrap around the i32 before exiting, we can't 3931a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // transform the IV. 3941a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (Leftover != 0 && int32_t(ExitValue+IncValue) > ExitValue) 3951a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick return; 3961a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick } 3971a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 398db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner IntegerType *Int32Ty = Type::getInt32Ty(PN->getContext()); 3991a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 4001a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // Insert new integer induction variable. 4011a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick PHINode *NewPHI = PHINode::Create(Int32Ty, 2, PN->getName()+".int", PN); 4021a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick NewPHI->addIncoming(ConstantInt::get(Int32Ty, InitValue), 4031a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick PN->getIncomingBlock(IncomingEdge)); 4041a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 4051a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick Value *NewAdd = 4061a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick BinaryOperator::CreateAdd(NewPHI, ConstantInt::get(Int32Ty, IncValue), 4071a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick Incr->getName()+".int", Incr); 4081a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick NewPHI->addIncoming(NewAdd, PN->getIncomingBlock(BackEdge)); 4091a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 4101a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick ICmpInst *NewCompare = new ICmpInst(TheBr, NewPred, NewAdd, 4111a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick ConstantInt::get(Int32Ty, ExitValue), 4121a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick Compare->getName()); 4131a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 4141a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // In the following deletions, PN may become dead and may be deleted. 4151a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // Use a WeakVH to observe whether this happens. 4161a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick WeakVH WeakPH = PN; 4171a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 4181a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // Delete the old floating point exit comparison. The branch starts using the 4191a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // new comparison. 4201a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick NewCompare->takeName(Compare); 4211a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick Compare->replaceAllUsesWith(NewCompare); 4221a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick RecursivelyDeleteTriviallyDeadInstructions(Compare); 4231a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 4241a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // Delete the old floating point increment. 4251a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick Incr->replaceAllUsesWith(UndefValue::get(Incr->getType())); 4261a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick RecursivelyDeleteTriviallyDeadInstructions(Incr); 4271a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 4281a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // If the FP induction variable still has uses, this is because something else 4291a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // in the loop uses its value. In order to canonicalize the induction 4301a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // variable, we chose to eliminate the IV and rewrite it in terms of an 4311a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // int->fp cast. 4321a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // 4331a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // We give preference to sitofp over uitofp because it is faster on most 4341a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // platforms. 4351a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (WeakPH) { 4361a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick Value *Conv = new SIToFPInst(NewPHI, PN->getType(), "indvar.conv", 4371a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick PN->getParent()->getFirstNonPHI()); 4381a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick PN->replaceAllUsesWith(Conv); 4391a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick RecursivelyDeleteTriviallyDeadInstructions(PN); 4401a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick } 4411a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 4421a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // Add a new IVUsers entry for the newly-created integer PHI. 4431a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (IU) 4441a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick IU->AddUsersIfInteresting(NewPHI); 4451a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick} 4461a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 4471a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trickvoid IndVarSimplify::RewriteNonIntegerIVs(Loop *L) { 4481a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // First step. Check to see if there are any floating-point recurrences. 4491a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // If there are, change them into integer recurrences, permitting analysis by 4501a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // the SCEV routines. 4511a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // 4521a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick BasicBlock *Header = L->getHeader(); 4531a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 4541a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick SmallVector<WeakVH, 8> PHIs; 4551a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick for (BasicBlock::iterator I = Header->begin(); 4561a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick PHINode *PN = dyn_cast<PHINode>(I); ++I) 4571a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick PHIs.push_back(PN); 4581a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 4591a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick for (unsigned i = 0, e = PHIs.size(); i != e; ++i) 4601a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (PHINode *PN = dyn_cast_or_null<PHINode>(&*PHIs[i])) 4611a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick HandleFloatingPointIV(L, PN); 4621a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 4631a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // If the loop previously had floating-point IV, ScalarEvolution 4641a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // may not have been able to compute a trip count. Now that we've done some 4651a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // re-writing, the trip count may be computable. 4661a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (Changed) 4671a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick SE->forgetLoop(L); 4681a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick} 4691a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 4701a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick//===----------------------------------------------------------------------===// 4711a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick// RewriteLoopExitValues - Optimize IV users outside the loop. 4721a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick// As a side effect, reduces the amount of IV processing within the loop. 4731a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick//===----------------------------------------------------------------------===// 4741a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 4751a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick/// RewriteLoopExitValues - Check to see if this loop has a computable 4761a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick/// loop-invariant execution count. If so, this means that we can compute the 4771a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick/// final value of any expressions that are recurrent in the loop, and 4781a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick/// substitute the exit values from the loop into any instructions outside of 4791a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick/// the loop that use the final values of the current expressions. 4801a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick/// 4811a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick/// This is mostly redundant with the regular IndVarSimplify activities that 4821a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick/// happen later, except that it's more powerful in some cases, because it's 4831a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick/// able to brute-force evaluate arbitrary instructions as long as they have 4841a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick/// constant operands at the beginning of the loop. 4851a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trickvoid IndVarSimplify::RewriteLoopExitValues(Loop *L, SCEVExpander &Rewriter) { 4861a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // Verify the input to the pass in already in LCSSA form. 4871a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick assert(L->isLCSSAForm(*DT)); 4881a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 4891a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick SmallVector<BasicBlock*, 8> ExitBlocks; 4909f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner L->getUniqueExitBlocks(ExitBlocks); 4919f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner 4929f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // Find all values that are computed inside the loop, but used outside of it. 4939f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // Because of LCSSA, these values will only occur in LCSSA PHI Nodes. Scan 4949f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // the exit blocks of the loop to find them. 4959f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) { 4969f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner BasicBlock *ExitBB = ExitBlocks[i]; 497cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 4989f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // If there are no PHI nodes in this exit block, then no values defined 4999f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // inside the loop are used on this path, skip it. 5009f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner PHINode *PN = dyn_cast<PHINode>(ExitBB->begin()); 5019f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner if (!PN) continue; 502cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 5039f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner unsigned NumPreds = PN->getNumIncomingValues(); 504cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 5059f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // Iterate over all of the PHI nodes. 5069f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner BasicBlock::iterator BBI = ExitBB->begin(); 5079f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner while ((PN = dyn_cast<PHINode>(BBI++))) { 5083790fb0c036acaa4db50aff83dd8b3bf51f8af6aTorok Edwin if (PN->use_empty()) 5093790fb0c036acaa4db50aff83dd8b3bf51f8af6aTorok Edwin continue; // dead use, don't replace it 510814f2b2d1927a5397c0e923588527277b9f67d6bDan Gohman 511814f2b2d1927a5397c0e923588527277b9f67d6bDan Gohman // SCEV only supports integer expressions for now. 512814f2b2d1927a5397c0e923588527277b9f67d6bDan Gohman if (!PN->getType()->isIntegerTy() && !PN->getType()->isPointerTy()) 513814f2b2d1927a5397c0e923588527277b9f67d6bDan Gohman continue; 514814f2b2d1927a5397c0e923588527277b9f67d6bDan Gohman 51545a2d7d44ae697e28df383d31455145fb754ac58Dale Johannesen // It's necessary to tell ScalarEvolution about this explicitly so that 51645a2d7d44ae697e28df383d31455145fb754ac58Dale Johannesen // it can walk the def-use list and forget all SCEVs, as it may not be 51745a2d7d44ae697e28df383d31455145fb754ac58Dale Johannesen // watching the PHI itself. Once the new exit value is in place, there 51845a2d7d44ae697e28df383d31455145fb754ac58Dale Johannesen // may not be a def-use connection between the loop and every instruction 51945a2d7d44ae697e28df383d31455145fb754ac58Dale Johannesen // which got a SCEVAddRecExpr for that loop. 52045a2d7d44ae697e28df383d31455145fb754ac58Dale Johannesen SE->forgetValue(PN); 52145a2d7d44ae697e28df383d31455145fb754ac58Dale Johannesen 5229f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // Iterate over all of the values in all the PHI nodes. 5239f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner for (unsigned i = 0; i != NumPreds; ++i) { 5249f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // If the value being merged in is not integer or is not defined 5259f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // in the loop, skip it. 5269f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner Value *InVal = PN->getIncomingValue(i); 527814f2b2d1927a5397c0e923588527277b9f67d6bDan Gohman if (!isa<Instruction>(InVal)) 5289f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner continue; 5299f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner 5309f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // If this pred is for a subloop, not L itself, skip it. 531cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman if (LI->getLoopFor(PN->getIncomingBlock(i)) != L) 5329f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner continue; // The Block is in a subloop, skip it. 5339f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner 5349f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // Check that InVal is defined in the loop. 5359f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner Instruction *Inst = cast<Instruction>(InVal); 53692329c7fbe572892c17aa2d2542a10e3ea16132fDan Gohman if (!L->contains(Inst)) 5379f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner continue; 538cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 5399f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // Okay, this instruction has a user outside of the current loop 5409f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // and varies predictably *inside* the loop. Evaluate the value it 5419f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // contains when the loop exits, if possible. 5420bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *ExitValue = SE->getSCEVAtScope(Inst, L->getParentLoop()); 54317ead4ff4baceb2c5503f233d0288d363ae44165Dan Gohman if (!SE->isLoopInvariant(ExitValue, L)) 5449f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner continue; 5459f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner 546667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman Value *ExitVal = Rewriter.expandCodeFor(ExitValue, PN->getType(), Inst); 547cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 548f67ef318aa29e7cc0c7de76349881959936d9eeeDavid Greene DEBUG(dbgs() << "INDVARS: RLEV: AfterLoopVal = " << *ExitVal << '\n' 549bdff548e4dd577a72094d57b282de4e765643b96Chris Lattner << " LoopVal = " << *Inst << "\n"); 5509caed5440d59dac4b388152fe8b993dc0491e5e9Chris Lattner 551b12a754cce0c1d5542af605203a47820edba454dAndrew Trick if (!isValidRewrite(Inst, ExitVal)) { 552b12a754cce0c1d5542af605203a47820edba454dAndrew Trick DeadInsts.push_back(ExitVal); 553b12a754cce0c1d5542af605203a47820edba454dAndrew Trick continue; 554b12a754cce0c1d5542af605203a47820edba454dAndrew Trick } 555b12a754cce0c1d5542af605203a47820edba454dAndrew Trick Changed = true; 556b12a754cce0c1d5542af605203a47820edba454dAndrew Trick ++NumReplaced; 557b12a754cce0c1d5542af605203a47820edba454dAndrew Trick 5589f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner PN->setIncomingValue(i, ExitVal); 559cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 56081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // If this instruction is dead now, delete it. 56181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman RecursivelyDeleteTriviallyDeadInstructions(Inst); 562cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 56365d1e2b6e74fcd370093cbe518ebc15cbc445ad4Dan Gohman if (NumPreds == 1) { 56465d1e2b6e74fcd370093cbe518ebc15cbc445ad4Dan Gohman // Completely replace a single-pred PHI. This is safe, because the 56565d1e2b6e74fcd370093cbe518ebc15cbc445ad4Dan Gohman // NewVal won't be variant in the loop, so we don't need an LCSSA phi 56665d1e2b6e74fcd370093cbe518ebc15cbc445ad4Dan Gohman // node anymore. 5679f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner PN->replaceAllUsesWith(ExitVal); 56881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman RecursivelyDeleteTriviallyDeadInstructions(PN); 569c9838f25d53d3dd7d38949ef6c28f2505a110f45Chris Lattner } 5704bd09d70cceb3851f7eb1c2f98338b3071d405f3Chris Lattner } 57165d1e2b6e74fcd370093cbe518ebc15cbc445ad4Dan Gohman if (NumPreds != 1) { 572667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman // Clone the PHI and delete the original one. This lets IVUsers and 573667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman // any other maps purge the original user from their records. 57450b6e33584f4e4cf75c7795b1f1a90731861c825Devang Patel PHINode *NewPN = cast<PHINode>(PN->clone()); 575667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman NewPN->takeName(PN); 576667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman NewPN->insertBefore(PN); 577667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman PN->replaceAllUsesWith(NewPN); 578667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman PN->eraseFromParent(); 579667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman } 580c9838f25d53d3dd7d38949ef6c28f2505a110f45Chris Lattner } 581c9838f25d53d3dd7d38949ef6c28f2505a110f45Chris Lattner } 582472fdf7090bb00af3a3f9dcbe22263120a527533Dan Gohman 583472fdf7090bb00af3a3f9dcbe22263120a527533Dan Gohman // The insertion point instruction may have been deleted; clear it out 584472fdf7090bb00af3a3f9dcbe22263120a527533Dan Gohman // so that the rewriter doesn't trip over it later. 585472fdf7090bb00af3a3f9dcbe22263120a527533Dan Gohman Rewriter.clearInsertPoint(); 58640bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner} 58715cad759fe2048ac5eb137c6bb0ab7287538677eChris Lattner 5881a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick//===----------------------------------------------------------------------===// 5891a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick// Rewrite IV users based on a canonical IV. 5901a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick// To be replaced by -disable-iv-rewrite. 5911a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick//===----------------------------------------------------------------------===// 592c671d892ab1d3d8fed18a61f66f3f3a86e73ebd9Dale Johannesen 5932fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// SimplifyIVUsers - Iteratively perform simplification on IVUsers within this 5942fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// loop. IVUsers is treated as a worklist. Each successive simplification may 5952fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// push more users which may themselves be candidates for simplification. 5962fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// 5972fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// This is the old approach to IV simplification to be replaced by 5982fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// SimplifyIVUsersNoRewrite. 5992fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// 6002fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trickvoid IndVarSimplify::SimplifyIVUsers(SCEVExpander &Rewriter) { 6012fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick // Each round of simplification involves a round of eliminating operations 6022fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick // followed by a round of widening IVs. A single IVUsers worklist is used 6032fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick // across all rounds. The inner loop advances the user. If widening exposes 6042fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick // more uses, then another pass through the outer loop is triggered. 6052fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick for (IVUsers::iterator I = IU->begin(); I != IU->end(); ++I) { 6062fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick Instruction *UseInst = I->getUser(); 6072fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick Value *IVOperand = I->getOperandValToReplace(); 6082fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick 6092fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick if (ICmpInst *ICmp = dyn_cast<ICmpInst>(UseInst)) { 6102fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick EliminateIVComparison(ICmp, IVOperand); 6112fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick continue; 6122fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick } 6132fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick if (BinaryOperator *Rem = dyn_cast<BinaryOperator>(UseInst)) { 6142fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick bool IsSigned = Rem->getOpcode() == Instruction::SRem; 6152fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick if (IsSigned || Rem->getOpcode() == Instruction::URem) { 6164417e537b65c14b378aeca75b2773582dd102f63Andrew Trick EliminateIVRemainder(Rem, IVOperand, IsSigned); 6172fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick continue; 6182fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick } 6192fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick } 6202fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick } 6212fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick} 6222fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick 6231a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick// FIXME: It is an extremely bad idea to indvar substitute anything more 6241a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick// complex than affine induction variables. Doing so will put expensive 6251a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick// polynomial evaluations inside of the loop, and the str reduction pass 6261a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick// currently can only reduce affine polynomials. For now just disable 6271a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick// indvar subst on anything more complex than an affine addrec, unless 6281a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick// it can be expanded to a trivial value. 6291a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trickstatic bool isSafe(const SCEV *S, const Loop *L, ScalarEvolution *SE) { 6301a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // Loop-invariant values are safe. 6311a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (SE->isLoopInvariant(S, L)) return true; 632f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 6331a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // Affine addrecs are safe. Non-affine are not, because LSR doesn't know how 6341a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // to transform them into efficient code. 6351a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) 6361a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick return AR->isAffine(); 637f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 6381a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // An add is safe it all its operands are safe. 6391a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (const SCEVCommutativeExpr *Commutative = dyn_cast<SCEVCommutativeExpr>(S)) { 6401a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick for (SCEVCommutativeExpr::op_iterator I = Commutative->op_begin(), 6411a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick E = Commutative->op_end(); I != E; ++I) 6421a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (!isSafe(*I, L, SE)) return false; 6431a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick return true; 644f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick } 645f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 6461a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // A cast is safe if its operand is. 6471a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (const SCEVCastExpr *C = dyn_cast<SCEVCastExpr>(S)) 6481a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick return isSafe(C->getOperand(), L, SE); 649f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 6501a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // A udiv is safe if its operands are. 6511a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (const SCEVUDivExpr *UD = dyn_cast<SCEVUDivExpr>(S)) 6521a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick return isSafe(UD->getLHS(), L, SE) && 6531a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick isSafe(UD->getRHS(), L, SE); 654f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 6551a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // SCEVUnknown is always safe. 6561a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (isa<SCEVUnknown>(S)) 6571a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick return true; 658f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 6591a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // Nothing else is safe. 6601a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick return false; 6611a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick} 662f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 6631a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trickvoid IndVarSimplify::RewriteIVExpressions(Loop *L, SCEVExpander &Rewriter) { 6641a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // Rewrite all induction variable expressions in terms of the canonical 6651a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // induction variable. 6661a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // 6671a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // If there were induction variables of other sizes or offsets, manually 6681a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // add the offsets to the primary induction variable and cast, avoiding 6691a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // the need for the code evaluation methods to insert induction variables 6701a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // of different sizes. 6711a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick for (IVUsers::iterator UI = IU->begin(), E = IU->end(); UI != E; ++UI) { 6721a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick Value *Op = UI->getOperandValToReplace(); 673db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner Type *UseTy = Op->getType(); 6741a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick Instruction *User = UI->getUser(); 6751a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 6761a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // Compute the final addrec to expand into code. 6771a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick const SCEV *AR = IU->getReplacementExpr(*UI); 6781a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 6791a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // Evaluate the expression out of the loop, if possible. 6801a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (!L->contains(UI->getUser())) { 6811a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick const SCEV *ExitVal = SE->getSCEVAtScope(AR, L->getParentLoop()); 6821a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (SE->isLoopInvariant(ExitVal, L)) 6831a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick AR = ExitVal; 6841a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick } 6851a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 6861a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // FIXME: It is an extremely bad idea to indvar substitute anything more 6871a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // complex than affine induction variables. Doing so will put expensive 6881a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // polynomial evaluations inside of the loop, and the str reduction pass 6891a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // currently can only reduce affine polynomials. For now just disable 6901a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // indvar subst on anything more complex than an affine addrec, unless 6911a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // it can be expanded to a trivial value. 6921a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (!isSafe(AR, L, SE)) 6931a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick continue; 6941a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 6951a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // Determine the insertion point for this user. By default, insert 6961a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // immediately before the user. The SCEVExpander class will automatically 6971a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // hoist loop invariants out of the loop. For PHI nodes, there may be 6981a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // multiple uses, so compute the nearest common dominator for the 6991a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // incoming blocks. 7001a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick Instruction *InsertPt = User; 7011a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (PHINode *PHI = dyn_cast<PHINode>(InsertPt)) 7021a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i) 7031a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (PHI->getIncomingValue(i) == Op) { 7041a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (InsertPt == User) 7051a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick InsertPt = PHI->getIncomingBlock(i)->getTerminator(); 7061a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick else 7071a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick InsertPt = 7081a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick DT->findNearestCommonDominator(InsertPt->getParent(), 7091a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick PHI->getIncomingBlock(i)) 7101a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick ->getTerminator(); 7111a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick } 7121a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 7131a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // Now expand it into actual Instructions and patch it into place. 7141a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick Value *NewVal = Rewriter.expandCodeFor(AR, UseTy, InsertPt); 7151a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 7161a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick DEBUG(dbgs() << "INDVARS: Rewrote IV '" << *AR << "' " << *Op << '\n' 7171a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick << " into = " << *NewVal << "\n"); 7181a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 7191a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (!isValidRewrite(Op, NewVal)) { 7201a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick DeadInsts.push_back(NewVal); 7211a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick continue; 7221a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick } 7231a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // Inform ScalarEvolution that this value is changing. The change doesn't 7241a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // affect its value, but it does potentially affect which use lists the 7251a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // value will be on after the replacement, which affects ScalarEvolution's 7261a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // ability to walk use lists and drop dangling pointers when a value is 7271a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // deleted. 7281a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick SE->forgetValue(User); 7291a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 7301a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // Patch the new value into place. 7311a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (Op->hasName()) 7321a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick NewVal->takeName(Op); 7331a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (Instruction *NewValI = dyn_cast<Instruction>(NewVal)) 7341a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick NewValI->setDebugLoc(User->getDebugLoc()); 7351a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick User->replaceUsesOfWith(Op, NewVal); 7361a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick UI->setOperandValToReplace(NewVal); 7371a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 7381a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick ++NumRemoved; 7391a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick Changed = true; 7401a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 7411a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // The old value may be dead now. 7421a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick DeadInsts.push_back(Op); 7431a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick } 7441a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick} 7451a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 7461a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick//===----------------------------------------------------------------------===// 7471a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick// IV Widening - Extend the width of an IV to cover its widest uses. 7481a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick//===----------------------------------------------------------------------===// 7491a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 7501a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Tricknamespace { 7511a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // Collect information about induction variables that are used by sign/zero 7521a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // extend operations. This information is recorded by CollectExtend and 7531a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // provides the input to WidenIV. 7541a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick struct WideIVInfo { 755db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner Type *WidestNativeType; // Widest integer type created [sz]ext 7561a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick bool IsSigned; // Was an sext user seen before a zext? 7571a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 7581a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick WideIVInfo() : WidestNativeType(0), IsSigned(false) {} 7591a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick }; 7601a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick} 7611a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 7621a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick/// CollectExtend - Update information about the induction variable that is 7631a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick/// extended by this sign or zero extend operation. This is used to determine 7641a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick/// the final width of the IV before actually widening it. 7651a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trickstatic void CollectExtend(CastInst *Cast, bool IsSigned, WideIVInfo &WI, 7661a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick ScalarEvolution *SE, const TargetData *TD) { 767db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner Type *Ty = Cast->getType(); 7681a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick uint64_t Width = SE->getTypeSizeInBits(Ty); 7691a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (TD && !TD->isLegalInteger(Width)) 7701a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick return; 7711a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 7721a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (!WI.WidestNativeType) { 7731a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick WI.WidestNativeType = SE->getEffectiveSCEVType(Ty); 7741a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick WI.IsSigned = IsSigned; 7751a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick return; 7761a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick } 7771a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 7781a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // We extend the IV to satisfy the sign of its first user, arbitrarily. 7791a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (WI.IsSigned != IsSigned) 7801a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick return; 7811a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 7821a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (Width > SE->getTypeSizeInBits(WI.WidestNativeType)) 7831a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick WI.WidestNativeType = SE->getEffectiveSCEVType(Ty); 7841a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick} 7851a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 7861a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Tricknamespace { 7871a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick/// WidenIV - The goal of this transform is to remove sign and zero extends 7881a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick/// without creating any new induction variables. To do this, it creates a new 7891a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick/// phi of the wider type and redirects all users, either removing extends or 7901a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick/// inserting truncs whenever we stop propagating the type. 7911a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick/// 7921a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trickclass WidenIV { 7931a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // Parameters 7941a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick PHINode *OrigPhi; 795db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner Type *WideType; 7961a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick bool IsSigned; 7971a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 7981a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // Context 7991a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick LoopInfo *LI; 8001a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick Loop *L; 8011a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick ScalarEvolution *SE; 8021a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick DominatorTree *DT; 8031a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 8041a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // Result 8051a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick PHINode *WidePhi; 8061a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick Instruction *WideInc; 8071a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick const SCEV *WideIncExpr; 8082fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick SmallVectorImpl<WeakVH> &DeadInsts; 809f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 8102fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick SmallPtrSet<Instruction*,16> Widened; 8114b02915386046fa882a95553a7457ae7d05e9f27Andrew Trick SmallVector<std::pair<Use *, Instruction *>, 8> NarrowIVUsers; 812f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 813f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trickpublic: 8142fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick WidenIV(PHINode *PN, const WideIVInfo &WI, LoopInfo *LInfo, 8152fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick ScalarEvolution *SEv, DominatorTree *DTree, 816fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick SmallVectorImpl<WeakVH> &DI) : 817f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick OrigPhi(PN), 8182fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick WideType(WI.WidestNativeType), 8192fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick IsSigned(WI.IsSigned), 820f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick LI(LInfo), 821f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick L(LI->getLoopFor(OrigPhi->getParent())), 822f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick SE(SEv), 823fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick DT(DTree), 824f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick WidePhi(0), 825f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick WideInc(0), 8262fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick WideIncExpr(0), 8272fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick DeadInsts(DI) { 828f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick assert(L->getHeader() == OrigPhi->getParent() && "Phi must be an IV"); 829f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick } 830f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 8312fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick PHINode *CreateWideIV(SCEVExpander &Rewriter); 832f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 833f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trickprotected: 834f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick Instruction *CloneIVUser(Instruction *NarrowUse, 835f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick Instruction *NarrowDef, 836f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick Instruction *WideDef); 837f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 838e0dc2faaa0105c9d1cc56f0b70e93d532a6f8c4cAndrew Trick const SCEVAddRecExpr *GetWideRecurrence(Instruction *NarrowUse); 839e0dc2faaa0105c9d1cc56f0b70e93d532a6f8c4cAndrew Trick 840cc359d9fa28a871b18d93da76fd9cf516499e39fAndrew Trick Instruction *WidenIVUse(Use &NarrowDefUse, Instruction *NarrowDef, 841f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick Instruction *WideDef); 8424b02915386046fa882a95553a7457ae7d05e9f27Andrew Trick 8434b02915386046fa882a95553a7457ae7d05e9f27Andrew Trick void pushNarrowIVUsers(Instruction *NarrowDef, Instruction *WideDef); 844f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick}; 845f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick} // anonymous namespace 846f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 847db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattnerstatic Value *getExtend( Value *NarrowOper, Type *WideType, 84803d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick bool IsSigned, IRBuilder<> &Builder) { 84903d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick return IsSigned ? Builder.CreateSExt(NarrowOper, WideType) : 85003d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick Builder.CreateZExt(NarrowOper, WideType); 851f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick} 852931e345e76e75391d2a7c96530e305f802b5429dDan Gohman 853f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick/// CloneIVUser - Instantiate a wide operation to replace a narrow 854f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick/// operation. This only needs to handle operations that can evaluation to 855f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick/// SCEVAddRec. It can safely return 0 for any operation we decide not to clone. 856f85092c25525f75eef6982ffa40c9b48b87da987Andrew TrickInstruction *WidenIV::CloneIVUser(Instruction *NarrowUse, 857f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick Instruction *NarrowDef, 858f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick Instruction *WideDef) { 859f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick unsigned Opcode = NarrowUse->getOpcode(); 860f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick switch (Opcode) { 861f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick default: 862f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick return 0; 863f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick case Instruction::Add: 864f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick case Instruction::Mul: 865f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick case Instruction::UDiv: 866f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick case Instruction::Sub: 867f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick case Instruction::And: 868f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick case Instruction::Or: 869f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick case Instruction::Xor: 870f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick case Instruction::Shl: 871f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick case Instruction::LShr: 872f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick case Instruction::AShr: 873f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick DEBUG(dbgs() << "Cloning IVUser: " << *NarrowUse << "\n"); 874f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 87503d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick IRBuilder<> Builder(NarrowUse); 87603d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick 87703d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick // Replace NarrowDef operands with WideDef. Otherwise, we don't know 87803d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick // anything about the narrow operand yet so must insert a [sz]ext. It is 87903d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick // probably loop invariant and will be folded or hoisted. If it actually 88003d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick // comes from a widened IV, it should be removed during a future call to 88103d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick // WidenIVUse. 88203d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick Value *LHS = (NarrowUse->getOperand(0) == NarrowDef) ? WideDef : 88303d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick getExtend(NarrowUse->getOperand(0), WideType, IsSigned, Builder); 88403d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick Value *RHS = (NarrowUse->getOperand(1) == NarrowDef) ? WideDef : 88503d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick getExtend(NarrowUse->getOperand(1), WideType, IsSigned, Builder); 88603d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick 887f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick BinaryOperator *NarrowBO = cast<BinaryOperator>(NarrowUse); 888f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick BinaryOperator *WideBO = BinaryOperator::Create(NarrowBO->getOpcode(), 88903d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick LHS, RHS, 890f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick NarrowBO->getName()); 891f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick Builder.Insert(WideBO); 8926e0ce24e0ca8b0dc05872b9b4cec3a18972bee40Andrew Trick if (const OverflowingBinaryOperator *OBO = 8936e0ce24e0ca8b0dc05872b9b4cec3a18972bee40Andrew Trick dyn_cast<OverflowingBinaryOperator>(NarrowBO)) { 8946e0ce24e0ca8b0dc05872b9b4cec3a18972bee40Andrew Trick if (OBO->hasNoUnsignedWrap()) WideBO->setHasNoUnsignedWrap(); 8956e0ce24e0ca8b0dc05872b9b4cec3a18972bee40Andrew Trick if (OBO->hasNoSignedWrap()) WideBO->setHasNoSignedWrap(); 8966e0ce24e0ca8b0dc05872b9b4cec3a18972bee40Andrew Trick } 89703d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick return WideBO; 898f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick } 899f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick llvm_unreachable(0); 900f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick} 901f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 902fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick/// HoistStep - Attempt to hoist an IV increment above a potential use. 903fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick/// 904fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick/// To successfully hoist, two criteria must be met: 905fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick/// - IncV operands dominate InsertPos and 906fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick/// - InsertPos dominates IncV 907fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick/// 908fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick/// Meeting the second condition means that we don't need to check all of IncV's 909fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick/// existing uses (it's moving up in the domtree). 910fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick/// 911fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick/// This does not yet recursively hoist the operands, although that would 912fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick/// not be difficult. 913fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trickstatic bool HoistStep(Instruction *IncV, Instruction *InsertPos, 914fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick const DominatorTree *DT) 915fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick{ 916fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick if (DT->dominates(IncV, InsertPos)) 917fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick return true; 918fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick 919fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick if (!DT->dominates(InsertPos->getParent(), IncV->getParent())) 920fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick return false; 921fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick 922fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick if (IncV->mayHaveSideEffects()) 923fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick return false; 924fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick 925fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick // Attempt to hoist IncV 926fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick for (User::op_iterator OI = IncV->op_begin(), OE = IncV->op_end(); 927fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick OI != OE; ++OI) { 928fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick Instruction *OInst = dyn_cast<Instruction>(OI); 929fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick if (OInst && !DT->dominates(OInst, InsertPos)) 930fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick return false; 931fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick } 932fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick IncV->moveBefore(InsertPos); 933fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick return true; 934fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick} 935fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick 936e0dc2faaa0105c9d1cc56f0b70e93d532a6f8c4cAndrew Trick// GetWideRecurrence - Is this instruction potentially interesting from IVUsers' 937e0dc2faaa0105c9d1cc56f0b70e93d532a6f8c4cAndrew Trick// perspective after widening it's type? In other words, can the extend be 938e0dc2faaa0105c9d1cc56f0b70e93d532a6f8c4cAndrew Trick// safely hoisted out of the loop with SCEV reducing the value to a recurrence 939e0dc2faaa0105c9d1cc56f0b70e93d532a6f8c4cAndrew Trick// on the same loop. If so, return the sign or zero extended 940e0dc2faaa0105c9d1cc56f0b70e93d532a6f8c4cAndrew Trick// recurrence. Otherwise return NULL. 941e0dc2faaa0105c9d1cc56f0b70e93d532a6f8c4cAndrew Trickconst SCEVAddRecExpr *WidenIV::GetWideRecurrence(Instruction *NarrowUse) { 942e0dc2faaa0105c9d1cc56f0b70e93d532a6f8c4cAndrew Trick if (!SE->isSCEVable(NarrowUse->getType())) 943e0dc2faaa0105c9d1cc56f0b70e93d532a6f8c4cAndrew Trick return 0; 944e0dc2faaa0105c9d1cc56f0b70e93d532a6f8c4cAndrew Trick 945e0dc2faaa0105c9d1cc56f0b70e93d532a6f8c4cAndrew Trick const SCEV *NarrowExpr = SE->getSCEV(NarrowUse); 946e0dc2faaa0105c9d1cc56f0b70e93d532a6f8c4cAndrew Trick if (SE->getTypeSizeInBits(NarrowExpr->getType()) 947e0dc2faaa0105c9d1cc56f0b70e93d532a6f8c4cAndrew Trick >= SE->getTypeSizeInBits(WideType)) { 948e0dc2faaa0105c9d1cc56f0b70e93d532a6f8c4cAndrew Trick // NarrowUse implicitly widens its operand. e.g. a gep with a narrow 949e0dc2faaa0105c9d1cc56f0b70e93d532a6f8c4cAndrew Trick // index. So don't follow this use. 950e0dc2faaa0105c9d1cc56f0b70e93d532a6f8c4cAndrew Trick return 0; 951e0dc2faaa0105c9d1cc56f0b70e93d532a6f8c4cAndrew Trick } 952e0dc2faaa0105c9d1cc56f0b70e93d532a6f8c4cAndrew Trick 953e0dc2faaa0105c9d1cc56f0b70e93d532a6f8c4cAndrew Trick const SCEV *WideExpr = IsSigned ? 954e0dc2faaa0105c9d1cc56f0b70e93d532a6f8c4cAndrew Trick SE->getSignExtendExpr(NarrowExpr, WideType) : 955e0dc2faaa0105c9d1cc56f0b70e93d532a6f8c4cAndrew Trick SE->getZeroExtendExpr(NarrowExpr, WideType); 956e0dc2faaa0105c9d1cc56f0b70e93d532a6f8c4cAndrew Trick const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(WideExpr); 957e0dc2faaa0105c9d1cc56f0b70e93d532a6f8c4cAndrew Trick if (!AddRec || AddRec->getLoop() != L) 958e0dc2faaa0105c9d1cc56f0b70e93d532a6f8c4cAndrew Trick return 0; 959e0dc2faaa0105c9d1cc56f0b70e93d532a6f8c4cAndrew Trick 960e0dc2faaa0105c9d1cc56f0b70e93d532a6f8c4cAndrew Trick return AddRec; 961e0dc2faaa0105c9d1cc56f0b70e93d532a6f8c4cAndrew Trick} 962e0dc2faaa0105c9d1cc56f0b70e93d532a6f8c4cAndrew Trick 963f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick/// WidenIVUse - Determine whether an individual user of the narrow IV can be 964f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick/// widened. If so, return the wide clone of the user. 965cc359d9fa28a871b18d93da76fd9cf516499e39fAndrew TrickInstruction *WidenIV::WidenIVUse(Use &NarrowDefUse, Instruction *NarrowDef, 966f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick Instruction *WideDef) { 967cc359d9fa28a871b18d93da76fd9cf516499e39fAndrew Trick Instruction *NarrowUse = cast<Instruction>(NarrowDefUse.getUser()); 968cc359d9fa28a871b18d93da76fd9cf516499e39fAndrew Trick 9694b02915386046fa882a95553a7457ae7d05e9f27Andrew Trick // Stop traversing the def-use chain at inner-loop phis or post-loop phis. 970f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick if (isa<PHINode>(NarrowUse) && LI->getLoopFor(NarrowUse->getParent()) != L) 971f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick return 0; 972f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 973f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // Our raison d'etre! Eliminate sign and zero extension. 974f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick if (IsSigned ? isa<SExtInst>(NarrowUse) : isa<ZExtInst>(NarrowUse)) { 97503d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick Value *NewDef = WideDef; 97603d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick if (NarrowUse->getType() != WideType) { 97703d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick unsigned CastWidth = SE->getTypeSizeInBits(NarrowUse->getType()); 97803d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick unsigned IVWidth = SE->getTypeSizeInBits(WideType); 97903d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick if (CastWidth < IVWidth) { 98003d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick // The cast isn't as wide as the IV, so insert a Trunc. 981cc359d9fa28a871b18d93da76fd9cf516499e39fAndrew Trick IRBuilder<> Builder(NarrowDefUse); 98203d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick NewDef = Builder.CreateTrunc(WideDef, NarrowUse->getType()); 98303d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick } 98403d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick else { 98503d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick // A wider extend was hidden behind a narrower one. This may induce 98603d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick // another round of IV widening in which the intermediate IV becomes 98703d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick // dead. It should be very rare. 98803d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick DEBUG(dbgs() << "INDVARS: New IV " << *WidePhi 98903d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick << " not wide enough to subsume " << *NarrowUse << "\n"); 99003d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick NarrowUse->replaceUsesOfWith(NarrowDef, WideDef); 99103d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick NewDef = NarrowUse; 99203d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick } 99303d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick } 99403d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick if (NewDef != NarrowUse) { 99503d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick DEBUG(dbgs() << "INDVARS: eliminating " << *NarrowUse 99603d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick << " replaced by " << *WideDef << "\n"); 99703d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick ++NumElimExt; 99803d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick NarrowUse->replaceAllUsesWith(NewDef); 99903d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick DeadInsts.push_back(NarrowUse); 100003d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick } 10012fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick // Now that the extend is gone, we want to expose it's uses for potential 10022fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick // further simplification. We don't need to directly inform SimplifyIVUsers 10032fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick // of the new users, because their parent IV will be processed later as a 10042fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick // new loop phi. If we preserved IVUsers analysis, we would also want to 10052fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick // push the uses of WideDef here. 1006f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 1007f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // No further widening is needed. The deceased [sz]ext had done it for us. 1008f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick return 0; 1009f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick } 10104b02915386046fa882a95553a7457ae7d05e9f27Andrew Trick 10114b02915386046fa882a95553a7457ae7d05e9f27Andrew Trick // Does this user itself evaluate to a recurrence after widening? 1012e0dc2faaa0105c9d1cc56f0b70e93d532a6f8c4cAndrew Trick const SCEVAddRecExpr *WideAddRec = GetWideRecurrence(NarrowUse); 1013f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick if (!WideAddRec) { 1014f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // This user does not evaluate to a recurence after widening, so don't 1015f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // follow it. Instead insert a Trunc to kill off the original use, 1016f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // eventually isolating the original narrow IV so it can be removed. 1017cc359d9fa28a871b18d93da76fd9cf516499e39fAndrew Trick IRBuilder<> Builder(NarrowDefUse); 101803d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick Value *Trunc = Builder.CreateTrunc(WideDef, NarrowDef->getType()); 1019f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick NarrowUse->replaceUsesOfWith(NarrowDef, Trunc); 1020f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick return 0; 1021f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick } 1022fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick // Assume block terminators cannot evaluate to a recurrence. We can't to 10234b02915386046fa882a95553a7457ae7d05e9f27Andrew Trick // insert a Trunc after a terminator if there happens to be a critical edge. 1024cc359d9fa28a871b18d93da76fd9cf516499e39fAndrew Trick assert(NarrowUse != NarrowUse->getParent()->getTerminator() && 10254b02915386046fa882a95553a7457ae7d05e9f27Andrew Trick "SCEV is not expected to evaluate a block terminator"); 1026cc359d9fa28a871b18d93da76fd9cf516499e39fAndrew Trick 1027fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick // Reuse the IV increment that SCEVExpander created as long as it dominates 1028fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick // NarrowUse. 1029f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick Instruction *WideUse = 0; 1030fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick if (WideAddRec == WideIncExpr && HoistStep(WideInc, NarrowUse, DT)) { 1031f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick WideUse = WideInc; 1032f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick } 1033f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick else { 1034f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick WideUse = CloneIVUser(NarrowUse, NarrowDef, WideDef); 1035f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick if (!WideUse) 1036f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick return 0; 1037f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick } 10384b02915386046fa882a95553a7457ae7d05e9f27Andrew Trick // Evaluation of WideAddRec ensured that the narrow expression could be 10394b02915386046fa882a95553a7457ae7d05e9f27Andrew Trick // extended outside the loop without overflow. This suggests that the wide use 1040f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // evaluates to the same expression as the extended narrow use, but doesn't 1041f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // absolutely guarantee it. Hence the following failsafe check. In rare cases 10422fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick // where it fails, we simply throw away the newly created wide use. 1043f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick if (WideAddRec != SE->getSCEV(WideUse)) { 1044f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick DEBUG(dbgs() << "Wide use expression mismatch: " << *WideUse 1045f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick << ": " << *SE->getSCEV(WideUse) << " != " << *WideAddRec << "\n"); 1046f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick DeadInsts.push_back(WideUse); 1047f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick return 0; 1048f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick } 1049f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 1050f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // Returning WideUse pushes it on the worklist. 1051f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick return WideUse; 1052f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick} 1053f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 10544b02915386046fa882a95553a7457ae7d05e9f27Andrew Trick/// pushNarrowIVUsers - Add eligible users of NarrowDef to NarrowIVUsers. 10554b02915386046fa882a95553a7457ae7d05e9f27Andrew Trick/// 10564b02915386046fa882a95553a7457ae7d05e9f27Andrew Trickvoid WidenIV::pushNarrowIVUsers(Instruction *NarrowDef, Instruction *WideDef) { 10574b02915386046fa882a95553a7457ae7d05e9f27Andrew Trick for (Value::use_iterator UI = NarrowDef->use_begin(), 10584b02915386046fa882a95553a7457ae7d05e9f27Andrew Trick UE = NarrowDef->use_end(); UI != UE; ++UI) { 10594b02915386046fa882a95553a7457ae7d05e9f27Andrew Trick Use &U = UI.getUse(); 10604b02915386046fa882a95553a7457ae7d05e9f27Andrew Trick 10614b02915386046fa882a95553a7457ae7d05e9f27Andrew Trick // Handle data flow merges and bizarre phi cycles. 10624b02915386046fa882a95553a7457ae7d05e9f27Andrew Trick if (!Widened.insert(cast<Instruction>(U.getUser()))) 10634b02915386046fa882a95553a7457ae7d05e9f27Andrew Trick continue; 10644b02915386046fa882a95553a7457ae7d05e9f27Andrew Trick 10654b02915386046fa882a95553a7457ae7d05e9f27Andrew Trick NarrowIVUsers.push_back(std::make_pair(&UI.getUse(), WideDef)); 10664b02915386046fa882a95553a7457ae7d05e9f27Andrew Trick } 10674b02915386046fa882a95553a7457ae7d05e9f27Andrew Trick} 10684b02915386046fa882a95553a7457ae7d05e9f27Andrew Trick 1069f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick/// CreateWideIV - Process a single induction variable. First use the 1070f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick/// SCEVExpander to create a wide induction variable that evaluates to the same 1071f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick/// recurrence as the original narrow IV. Then use a worklist to forward 10722fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// traverse the narrow IV's def-use chain. After WidenIVUse has processed all 1073f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick/// interesting IV users, the narrow IV will be isolated for removal by 1074f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick/// DeleteDeadPHIs. 1075f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick/// 1076f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick/// It would be simpler to delete uses as they are processed, but we must avoid 1077f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick/// invalidating SCEV expressions. 1078f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick/// 10792fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew TrickPHINode *WidenIV::CreateWideIV(SCEVExpander &Rewriter) { 1080f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // Is this phi an induction variable? 1081f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(SE->getSCEV(OrigPhi)); 1082f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick if (!AddRec) 10832fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick return NULL; 1084f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 1085f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // Widen the induction variable expression. 1086f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick const SCEV *WideIVExpr = IsSigned ? 1087f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick SE->getSignExtendExpr(AddRec, WideType) : 1088f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick SE->getZeroExtendExpr(AddRec, WideType); 1089f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 1090f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick assert(SE->getEffectiveSCEVType(WideIVExpr->getType()) == WideType && 1091f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick "Expect the new IV expression to preserve its type"); 1092f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 1093f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // Can the IV be extended outside the loop without overflow? 1094f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick AddRec = dyn_cast<SCEVAddRecExpr>(WideIVExpr); 1095f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick if (!AddRec || AddRec->getLoop() != L) 10962fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick return NULL; 1097f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 10982fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick // An AddRec must have loop-invariant operands. Since this AddRec is 1099f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // materialized by a loop header phi, the expression cannot have any post-loop 1100f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // operands, so they must dominate the loop header. 1101f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick assert(SE->properlyDominates(AddRec->getStart(), L->getHeader()) && 1102f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick SE->properlyDominates(AddRec->getStepRecurrence(*SE), L->getHeader()) 1103f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick && "Loop header phi recurrence inputs do not dominate the loop"); 1104f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 1105f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // The rewriter provides a value for the desired IV expression. This may 1106f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // either find an existing phi or materialize a new one. Either way, we 1107f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // expect a well-formed cyclic phi-with-increments. i.e. any operand not part 1108f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // of the phi-SCC dominates the loop entry. 1109f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick Instruction *InsertPt = L->getHeader()->begin(); 1110f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick WidePhi = cast<PHINode>(Rewriter.expandCodeFor(AddRec, WideType, InsertPt)); 1111f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 1112f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // Remembering the WideIV increment generated by SCEVExpander allows 1113f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // WidenIVUse to reuse it when widening the narrow IV's increment. We don't 1114f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // employ a general reuse mechanism because the call above is the only call to 1115f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // SCEVExpander. Henceforth, we produce 1-to-1 narrow to wide uses. 1116fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick if (BasicBlock *LatchBlock = L->getLoopLatch()) { 1117fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick WideInc = 1118fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick cast<Instruction>(WidePhi->getIncomingValueForBlock(LatchBlock)); 1119fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick WideIncExpr = SE->getSCEV(WideInc); 1120fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick } 1121f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 1122f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick DEBUG(dbgs() << "Wide IV: " << *WidePhi << "\n"); 1123f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick ++NumWidened; 1124f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 1125f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // Traverse the def-use chain using a worklist starting at the original IV. 11264b02915386046fa882a95553a7457ae7d05e9f27Andrew Trick assert(Widened.empty() && NarrowIVUsers.empty() && "expect initial state" ); 11274b02915386046fa882a95553a7457ae7d05e9f27Andrew Trick 11284b02915386046fa882a95553a7457ae7d05e9f27Andrew Trick Widened.insert(OrigPhi); 11294b02915386046fa882a95553a7457ae7d05e9f27Andrew Trick pushNarrowIVUsers(OrigPhi, WidePhi); 1130f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 1131f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick while (!NarrowIVUsers.empty()) { 1132cc359d9fa28a871b18d93da76fd9cf516499e39fAndrew Trick Use *UsePtr; 1133fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick Instruction *WideDef; 1134cc359d9fa28a871b18d93da76fd9cf516499e39fAndrew Trick tie(UsePtr, WideDef) = NarrowIVUsers.pop_back_val(); 1135cc359d9fa28a871b18d93da76fd9cf516499e39fAndrew Trick Use &NarrowDefUse = *UsePtr; 1136fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick 1137fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick // Process a def-use edge. This may replace the use, so don't hold a 1138fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick // use_iterator across it. 1139cc359d9fa28a871b18d93da76fd9cf516499e39fAndrew Trick Instruction *NarrowDef = cast<Instruction>(NarrowDefUse.get()); 1140cc359d9fa28a871b18d93da76fd9cf516499e39fAndrew Trick Instruction *WideUse = WidenIVUse(NarrowDefUse, NarrowDef, WideDef); 1141fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick 1142fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick // Follow all def-use edges from the previous narrow use. 11434b02915386046fa882a95553a7457ae7d05e9f27Andrew Trick if (WideUse) 11444b02915386046fa882a95553a7457ae7d05e9f27Andrew Trick pushNarrowIVUsers(cast<Instruction>(NarrowDefUse.getUser()), WideUse); 11454b02915386046fa882a95553a7457ae7d05e9f27Andrew Trick 1146fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick // WidenIVUse may have removed the def-use edge. 1147fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick if (NarrowDef->use_empty()) 1148fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick DeadInsts.push_back(NarrowDef); 1149931e345e76e75391d2a7c96530e305f802b5429dDan Gohman } 11502fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick return WidePhi; 1151931e345e76e75391d2a7c96530e305f802b5429dDan Gohman} 1152931e345e76e75391d2a7c96530e305f802b5429dDan Gohman 11531a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick//===----------------------------------------------------------------------===// 11541a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick// Simplification of IV users based on SCEV evaluation. 11551a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick//===----------------------------------------------------------------------===// 11561a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 1157aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trickvoid IndVarSimplify::EliminateIVComparison(ICmpInst *ICmp, Value *IVOperand) { 1158aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick unsigned IVOperIdx = 0; 1159aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick ICmpInst::Predicate Pred = ICmp->getPredicate(); 1160aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick if (IVOperand != ICmp->getOperand(0)) { 1161aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick // Swapped 1162aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick assert(IVOperand == ICmp->getOperand(1) && "Can't find IVOperand"); 1163aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick IVOperIdx = 1; 1164aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick Pred = ICmpInst::getSwappedPredicate(Pred); 1165aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick } 1166a590b79ee227b93c59f60ce1f54cae7a9ebec7c1Dan Gohman 1167aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick // Get the SCEVs for the ICmp operands. 1168aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick const SCEV *S = SE->getSCEV(ICmp->getOperand(IVOperIdx)); 1169aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick const SCEV *X = SE->getSCEV(ICmp->getOperand(1 - IVOperIdx)); 1170aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick 1171aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick // Simplify unnecessary loops away. 1172aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick const Loop *ICmpLoop = LI->getLoopFor(ICmp->getParent()); 1173aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick S = SE->getSCEVAtScope(S, ICmpLoop); 1174aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick X = SE->getSCEVAtScope(X, ICmpLoop); 1175aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick 1176aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick // If the condition is always true or always false, replace it with 1177aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick // a constant value. 1178aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick if (SE->isKnownPredicate(Pred, S, X)) 1179aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick ICmp->replaceAllUsesWith(ConstantInt::getTrue(ICmp->getContext())); 1180aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick else if (SE->isKnownPredicate(ICmpInst::getInversePredicate(Pred), S, X)) 1181aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick ICmp->replaceAllUsesWith(ConstantInt::getFalse(ICmp->getContext())); 1182aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick else 1183aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick return; 1184a590b79ee227b93c59f60ce1f54cae7a9ebec7c1Dan Gohman 1185aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick DEBUG(dbgs() << "INDVARS: Eliminated comparison: " << *ICmp << '\n'); 118603d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick ++NumElimCmp; 1187074397d75e0bf919995f9cf0005fa6fda1c0400cAndrew Trick Changed = true; 1188aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick DeadInsts.push_back(ICmp); 1189aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick} 1190a590b79ee227b93c59f60ce1f54cae7a9ebec7c1Dan Gohman 1191aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trickvoid IndVarSimplify::EliminateIVRemainder(BinaryOperator *Rem, 1192aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick Value *IVOperand, 11934417e537b65c14b378aeca75b2773582dd102f63Andrew Trick bool IsSigned) { 1194aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick // We're only interested in the case where we know something about 1195aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick // the numerator. 1196aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick if (IVOperand != Rem->getOperand(0)) 1197aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick return; 1198aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick 1199aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick // Get the SCEVs for the ICmp operands. 1200aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick const SCEV *S = SE->getSCEV(Rem->getOperand(0)); 1201aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick const SCEV *X = SE->getSCEV(Rem->getOperand(1)); 1202aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick 1203aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick // Simplify unnecessary loops away. 1204aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick const Loop *ICmpLoop = LI->getLoopFor(Rem->getParent()); 1205aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick S = SE->getSCEVAtScope(S, ICmpLoop); 1206aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick X = SE->getSCEVAtScope(X, ICmpLoop); 1207aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick 1208aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick // i % n --> i if i is in [0,n). 1209074397d75e0bf919995f9cf0005fa6fda1c0400cAndrew Trick if ((!IsSigned || SE->isKnownNonNegative(S)) && 1210074397d75e0bf919995f9cf0005fa6fda1c0400cAndrew Trick SE->isKnownPredicate(IsSigned ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT, 1211aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick S, X)) 1212aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick Rem->replaceAllUsesWith(Rem->getOperand(0)); 1213aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick else { 1214aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick // (i+1) % n --> (i+1)==n?0:(i+1) if i is in [0,n). 1215aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick const SCEV *LessOne = 1216aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick SE->getMinusSCEV(S, SE->getConstant(S->getType(), 1)); 1217074397d75e0bf919995f9cf0005fa6fda1c0400cAndrew Trick if (IsSigned && !SE->isKnownNonNegative(LessOne)) 1218aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick return; 1219aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick 1220074397d75e0bf919995f9cf0005fa6fda1c0400cAndrew Trick if (!SE->isKnownPredicate(IsSigned ? 1221aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT, 1222aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick LessOne, X)) 1223aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick return; 1224aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick 1225aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick ICmpInst *ICmp = new ICmpInst(Rem, ICmpInst::ICMP_EQ, 1226aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick Rem->getOperand(0), Rem->getOperand(1), 1227aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick "tmp"); 1228aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick SelectInst *Sel = 1229aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick SelectInst::Create(ICmp, 1230aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick ConstantInt::get(Rem->getType(), 0), 1231aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick Rem->getOperand(0), "tmp", Rem); 1232aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick Rem->replaceAllUsesWith(Sel); 1233aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick } 1234a590b79ee227b93c59f60ce1f54cae7a9ebec7c1Dan Gohman 1235aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick // Inform IVUsers about the new users. 12362fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick if (IU) { 12372fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick if (Instruction *I = dyn_cast<Instruction>(Rem->getOperand(0))) 12384417e537b65c14b378aeca75b2773582dd102f63Andrew Trick IU->AddUsersIfInteresting(I); 12392fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick } 1240aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick DEBUG(dbgs() << "INDVARS: Simplified rem: " << *Rem << '\n'); 124103d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick ++NumElimRem; 1242074397d75e0bf919995f9cf0005fa6fda1c0400cAndrew Trick Changed = true; 1243aeee4616dd12d58fd8d040ab00277747f0312321Andrew Trick DeadInsts.push_back(Rem); 1244a590b79ee227b93c59f60ce1f54cae7a9ebec7c1Dan Gohman} 1245a590b79ee227b93c59f60ce1f54cae7a9ebec7c1Dan Gohman 12462fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// EliminateIVUser - Eliminate an operation that consumes a simple IV and has 12472fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// no observable side-effect given the range of IV values. 12482fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trickbool IndVarSimplify::EliminateIVUser(Instruction *UseInst, 12492fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick Instruction *IVOperand) { 12502fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick if (ICmpInst *ICmp = dyn_cast<ICmpInst>(UseInst)) { 12512fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick EliminateIVComparison(ICmp, IVOperand); 12522fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick return true; 12532fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick } 12542fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick if (BinaryOperator *Rem = dyn_cast<BinaryOperator>(UseInst)) { 12552fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick bool IsSigned = Rem->getOpcode() == Instruction::SRem; 12562fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick if (IsSigned || Rem->getOpcode() == Instruction::URem) { 12574417e537b65c14b378aeca75b2773582dd102f63Andrew Trick EliminateIVRemainder(Rem, IVOperand, IsSigned); 12582fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick return true; 12592fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick } 12602fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick } 12612fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick 12622fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick // Eliminate any operation that SCEV can prove is an identity function. 12632fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick if (!SE->isSCEVable(UseInst->getType()) || 126411745d4c0276ccb5c64f83d6954b54c8ff2aec98Andrew Trick (UseInst->getType() != IVOperand->getType()) || 12652fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick (SE->getSCEV(UseInst) != SE->getSCEV(IVOperand))) 12662fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick return false; 12672fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick 12682fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick DEBUG(dbgs() << "INDVARS: Eliminated identity: " << *UseInst << '\n'); 126960ac719c85366da04852c204aea5aa86d66dbb07Andrew Trick 127060ac719c85366da04852c204aea5aa86d66dbb07Andrew Trick UseInst->replaceAllUsesWith(IVOperand); 12712fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick ++NumElimIdentity; 12722fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick Changed = true; 12732fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick DeadInsts.push_back(UseInst); 12742fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick return true; 12752fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick} 12762fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick 12772fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// pushIVUsers - Add all uses of Def to the current IV's worklist. 12782fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// 127915832f61775040995bb8aa6056176425bc2c9088Andrew Trickstatic void pushIVUsers( 128015832f61775040995bb8aa6056176425bc2c9088Andrew Trick Instruction *Def, 128115832f61775040995bb8aa6056176425bc2c9088Andrew Trick SmallPtrSet<Instruction*,16> &Simplified, 128215832f61775040995bb8aa6056176425bc2c9088Andrew Trick SmallVectorImpl< std::pair<Instruction*,Instruction*> > &SimpleIVUsers) { 12832fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick 12842fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick for (Value::use_iterator UI = Def->use_begin(), E = Def->use_end(); 12852fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick UI != E; ++UI) { 12862fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick Instruction *User = cast<Instruction>(*UI); 12872fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick 12882fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick // Avoid infinite or exponential worklist processing. 12892fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick // Also ensure unique worklist users. 129060ac719c85366da04852c204aea5aa86d66dbb07Andrew Trick // If Def is a LoopPhi, it may not be in the Simplified set, so check for 129160ac719c85366da04852c204aea5aa86d66dbb07Andrew Trick // self edges first. 129260ac719c85366da04852c204aea5aa86d66dbb07Andrew Trick if (User != Def && Simplified.insert(User)) 12932fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick SimpleIVUsers.push_back(std::make_pair(User, Def)); 12942fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick } 12952fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick} 12962fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick 12972fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// isSimpleIVUser - Return true if this instruction generates a simple SCEV 12982fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// expression in terms of that IV. 12992fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// 13002fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// This is similar to IVUsers' isInsteresting() but processes each instruction 13012fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// non-recursively when the operand is already known to be a simpleIVUser. 13022fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// 13031a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trickstatic bool isSimpleIVUser(Instruction *I, const Loop *L, ScalarEvolution *SE) { 13042fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick if (!SE->isSCEVable(I->getType())) 13052fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick return false; 13062fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick 13072fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick // Get the symbolic expression for this instruction. 13082fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick const SCEV *S = SE->getSCEV(I); 13092fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick 13102fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick // Only consider affine recurrences. 13112fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S); 13122fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick if (AR && AR->getLoop() == L) 13132fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick return true; 13142fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick 13152fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick return false; 13162fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick} 13172fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick 13182fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// SimplifyIVUsersNoRewrite - Iteratively perform simplification on a worklist 13192fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// of IV users. Each successive simplification may push more users which may 13202fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// themselves be candidates for simplification. 13212fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// 13222fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// The "NoRewrite" algorithm does not require IVUsers analysis. Instead, it 13232fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// simplifies instructions in-place during analysis. Rather than rewriting 13242fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// induction variables bottom-up from their users, it transforms a chain of 13252fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// IVUsers top-down, updating the IR only when it encouters a clear 13262fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// optimization opportunitiy. A SCEVExpander "Rewriter" instance is still 13272fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// needed, but only used to generate a new IV (phi) of wider type for sign/zero 13282fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// extend elimination. 13292fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// 13302fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// Once DisableIVRewrite is default, LSR will be the only client of IVUsers. 13312fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// 13322fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trickvoid IndVarSimplify::SimplifyIVUsersNoRewrite(Loop *L, SCEVExpander &Rewriter) { 133315832f61775040995bb8aa6056176425bc2c9088Andrew Trick std::map<PHINode *, WideIVInfo> WideIVMap; 133415832f61775040995bb8aa6056176425bc2c9088Andrew Trick 13352fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick SmallVector<PHINode*, 8> LoopPhis; 13362fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I) { 13372fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick LoopPhis.push_back(cast<PHINode>(I)); 13382fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick } 133915832f61775040995bb8aa6056176425bc2c9088Andrew Trick // Each round of simplification iterates through the SimplifyIVUsers worklist 134015832f61775040995bb8aa6056176425bc2c9088Andrew Trick // for all current phis, then determines whether any IVs can be 134115832f61775040995bb8aa6056176425bc2c9088Andrew Trick // widened. Widening adds new phis to LoopPhis, inducing another round of 134215832f61775040995bb8aa6056176425bc2c9088Andrew Trick // simplification on the wide IVs. 13432fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick while (!LoopPhis.empty()) { 134415832f61775040995bb8aa6056176425bc2c9088Andrew Trick // Evaluate as many IV expressions as possible before widening any IVs. This 134599a92f67c7ee0d428e18f35c91311a2baba6c03eAndrew Trick // forces SCEV to set no-wrap flags before evaluating sign/zero 134615832f61775040995bb8aa6056176425bc2c9088Andrew Trick // extension. The first time SCEV attempts to normalize sign/zero extension, 134715832f61775040995bb8aa6056176425bc2c9088Andrew Trick // the result becomes final. So for the most predictable results, we delay 134815832f61775040995bb8aa6056176425bc2c9088Andrew Trick // evaluation of sign/zero extend evaluation until needed, and avoid running 134915832f61775040995bb8aa6056176425bc2c9088Andrew Trick // other SCEV based analysis prior to SimplifyIVUsersNoRewrite. 135015832f61775040995bb8aa6056176425bc2c9088Andrew Trick do { 135115832f61775040995bb8aa6056176425bc2c9088Andrew Trick PHINode *CurrIV = LoopPhis.pop_back_val(); 13522fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick 135315832f61775040995bb8aa6056176425bc2c9088Andrew Trick // Information about sign/zero extensions of CurrIV. 135415832f61775040995bb8aa6056176425bc2c9088Andrew Trick WideIVInfo WI; 13552fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick 135615832f61775040995bb8aa6056176425bc2c9088Andrew Trick // Instructions processed by SimplifyIVUsers for CurrIV. 135715832f61775040995bb8aa6056176425bc2c9088Andrew Trick SmallPtrSet<Instruction*,16> Simplified; 13582fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick 1359037d1c0c7e01cefeff7e538682c9a1e536e14030Andrew Trick // Use-def pairs if IV users waiting to be processed for CurrIV. 136015832f61775040995bb8aa6056176425bc2c9088Andrew Trick SmallVector<std::pair<Instruction*, Instruction*>, 8> SimpleIVUsers; 13612fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick 136260ac719c85366da04852c204aea5aa86d66dbb07Andrew Trick // Push users of the current LoopPhi. In rare cases, pushIVUsers may be 136360ac719c85366da04852c204aea5aa86d66dbb07Andrew Trick // called multiple times for the same LoopPhi. This is the proper thing to 136460ac719c85366da04852c204aea5aa86d66dbb07Andrew Trick // do for loop header phis that use each other. 136515832f61775040995bb8aa6056176425bc2c9088Andrew Trick pushIVUsers(CurrIV, Simplified, SimpleIVUsers); 136615832f61775040995bb8aa6056176425bc2c9088Andrew Trick 136715832f61775040995bb8aa6056176425bc2c9088Andrew Trick while (!SimpleIVUsers.empty()) { 136815832f61775040995bb8aa6056176425bc2c9088Andrew Trick Instruction *UseInst, *Operand; 136915832f61775040995bb8aa6056176425bc2c9088Andrew Trick tie(UseInst, Operand) = SimpleIVUsers.pop_back_val(); 13706e0ce24e0ca8b0dc05872b9b4cec3a18972bee40Andrew Trick // Bypass back edges to avoid extra work. 13716e0ce24e0ca8b0dc05872b9b4cec3a18972bee40Andrew Trick if (UseInst == CurrIV) continue; 137215832f61775040995bb8aa6056176425bc2c9088Andrew Trick 137315832f61775040995bb8aa6056176425bc2c9088Andrew Trick if (EliminateIVUser(UseInst, Operand)) { 137415832f61775040995bb8aa6056176425bc2c9088Andrew Trick pushIVUsers(Operand, Simplified, SimpleIVUsers); 137515832f61775040995bb8aa6056176425bc2c9088Andrew Trick continue; 137615832f61775040995bb8aa6056176425bc2c9088Andrew Trick } 137715832f61775040995bb8aa6056176425bc2c9088Andrew Trick if (CastInst *Cast = dyn_cast<CastInst>(UseInst)) { 137815832f61775040995bb8aa6056176425bc2c9088Andrew Trick bool IsSigned = Cast->getOpcode() == Instruction::SExt; 137915832f61775040995bb8aa6056176425bc2c9088Andrew Trick if (IsSigned || Cast->getOpcode() == Instruction::ZExt) { 138015832f61775040995bb8aa6056176425bc2c9088Andrew Trick CollectExtend(Cast, IsSigned, WI, SE, TD); 138115832f61775040995bb8aa6056176425bc2c9088Andrew Trick } 138215832f61775040995bb8aa6056176425bc2c9088Andrew Trick continue; 138315832f61775040995bb8aa6056176425bc2c9088Andrew Trick } 13841a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (isSimpleIVUser(UseInst, L, SE)) { 138515832f61775040995bb8aa6056176425bc2c9088Andrew Trick pushIVUsers(UseInst, Simplified, SimpleIVUsers); 13862fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick } 13872fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick } 138815832f61775040995bb8aa6056176425bc2c9088Andrew Trick if (WI.WidestNativeType) { 138915832f61775040995bb8aa6056176425bc2c9088Andrew Trick WideIVMap[CurrIV] = WI; 13902fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick } 139115832f61775040995bb8aa6056176425bc2c9088Andrew Trick } while(!LoopPhis.empty()); 139215832f61775040995bb8aa6056176425bc2c9088Andrew Trick 139315832f61775040995bb8aa6056176425bc2c9088Andrew Trick for (std::map<PHINode *, WideIVInfo>::const_iterator I = WideIVMap.begin(), 139415832f61775040995bb8aa6056176425bc2c9088Andrew Trick E = WideIVMap.end(); I != E; ++I) { 139515832f61775040995bb8aa6056176425bc2c9088Andrew Trick WidenIV Widener(I->first, I->second, LI, SE, DT, DeadInsts); 13962fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick if (PHINode *WidePhi = Widener.CreateWideIV(Rewriter)) { 13972fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick Changed = true; 13982fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick LoopPhis.push_back(WidePhi); 13992fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick } 14002fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick } 140115832f61775040995bb8aa6056176425bc2c9088Andrew Trick WideIVMap.clear(); 14022fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick } 14032fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick} 14042fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick 1405037d1c0c7e01cefeff7e538682c9a1e536e14030Andrew Trick/// SimplifyCongruentIVs - Check for congruent phis in this loop header and 1406037d1c0c7e01cefeff7e538682c9a1e536e14030Andrew Trick/// populate ExprToIVMap for use later. 1407037d1c0c7e01cefeff7e538682c9a1e536e14030Andrew Trick/// 1408037d1c0c7e01cefeff7e538682c9a1e536e14030Andrew Trickvoid IndVarSimplify::SimplifyCongruentIVs(Loop *L) { 14096f684b0becc4c1b2ece3ec6dcecf30b19343128dAndrew Trick DenseMap<const SCEV *, PHINode *> ExprToIVMap; 1410037d1c0c7e01cefeff7e538682c9a1e536e14030Andrew Trick for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I) { 1411037d1c0c7e01cefeff7e538682c9a1e536e14030Andrew Trick PHINode *Phi = cast<PHINode>(I); 14121a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (!SE->isSCEVable(Phi->getType())) 14131a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick continue; 14141a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 1415037d1c0c7e01cefeff7e538682c9a1e536e14030Andrew Trick const SCEV *S = SE->getSCEV(Phi); 14166f684b0becc4c1b2ece3ec6dcecf30b19343128dAndrew Trick DenseMap<const SCEV *, PHINode *>::const_iterator Pos; 1417037d1c0c7e01cefeff7e538682c9a1e536e14030Andrew Trick bool Inserted; 1418037d1c0c7e01cefeff7e538682c9a1e536e14030Andrew Trick tie(Pos, Inserted) = ExprToIVMap.insert(std::make_pair(S, Phi)); 1419037d1c0c7e01cefeff7e538682c9a1e536e14030Andrew Trick if (Inserted) 1420037d1c0c7e01cefeff7e538682c9a1e536e14030Andrew Trick continue; 1421037d1c0c7e01cefeff7e538682c9a1e536e14030Andrew Trick PHINode *OrigPhi = Pos->second; 1422037d1c0c7e01cefeff7e538682c9a1e536e14030Andrew Trick // Replacing the congruent phi is sufficient because acyclic redundancy 1423037d1c0c7e01cefeff7e538682c9a1e536e14030Andrew Trick // elimination, CSE/GVN, should handle the rest. However, once SCEV proves 1424037d1c0c7e01cefeff7e538682c9a1e536e14030Andrew Trick // that a phi is congruent, it's almost certain to be the head of an IV 1425037d1c0c7e01cefeff7e538682c9a1e536e14030Andrew Trick // user cycle that is isomorphic with the original phi. So it's worth 1426037d1c0c7e01cefeff7e538682c9a1e536e14030Andrew Trick // eagerly cleaning up the common case of a single IV increment. 1427037d1c0c7e01cefeff7e538682c9a1e536e14030Andrew Trick if (BasicBlock *LatchBlock = L->getLoopLatch()) { 1428037d1c0c7e01cefeff7e538682c9a1e536e14030Andrew Trick Instruction *OrigInc = 1429037d1c0c7e01cefeff7e538682c9a1e536e14030Andrew Trick cast<Instruction>(OrigPhi->getIncomingValueForBlock(LatchBlock)); 1430037d1c0c7e01cefeff7e538682c9a1e536e14030Andrew Trick Instruction *IsomorphicInc = 1431037d1c0c7e01cefeff7e538682c9a1e536e14030Andrew Trick cast<Instruction>(Phi->getIncomingValueForBlock(LatchBlock)); 1432037d1c0c7e01cefeff7e538682c9a1e536e14030Andrew Trick if (OrigInc != IsomorphicInc && 1433037d1c0c7e01cefeff7e538682c9a1e536e14030Andrew Trick SE->getSCEV(OrigInc) == SE->getSCEV(IsomorphicInc) && 1434037d1c0c7e01cefeff7e538682c9a1e536e14030Andrew Trick HoistStep(OrigInc, IsomorphicInc, DT)) { 1435037d1c0c7e01cefeff7e538682c9a1e536e14030Andrew Trick DEBUG(dbgs() << "INDVARS: Eliminated congruent iv.inc: " 1436037d1c0c7e01cefeff7e538682c9a1e536e14030Andrew Trick << *IsomorphicInc << '\n'); 1437037d1c0c7e01cefeff7e538682c9a1e536e14030Andrew Trick IsomorphicInc->replaceAllUsesWith(OrigInc); 1438037d1c0c7e01cefeff7e538682c9a1e536e14030Andrew Trick DeadInsts.push_back(IsomorphicInc); 1439037d1c0c7e01cefeff7e538682c9a1e536e14030Andrew Trick } 1440037d1c0c7e01cefeff7e538682c9a1e536e14030Andrew Trick } 1441037d1c0c7e01cefeff7e538682c9a1e536e14030Andrew Trick DEBUG(dbgs() << "INDVARS: Eliminated congruent iv: " << *Phi << '\n'); 1442037d1c0c7e01cefeff7e538682c9a1e536e14030Andrew Trick ++NumElimIV; 1443037d1c0c7e01cefeff7e538682c9a1e536e14030Andrew Trick Phi->replaceAllUsesWith(OrigPhi); 1444037d1c0c7e01cefeff7e538682c9a1e536e14030Andrew Trick DeadInsts.push_back(Phi); 1445037d1c0c7e01cefeff7e538682c9a1e536e14030Andrew Trick } 1446037d1c0c7e01cefeff7e538682c9a1e536e14030Andrew Trick} 1447037d1c0c7e01cefeff7e538682c9a1e536e14030Andrew Trick 14481a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick//===----------------------------------------------------------------------===// 14491a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick// LinearFunctionTestReplace and its kin. Rewrite the loop exit condition. 14501a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick//===----------------------------------------------------------------------===// 14511a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 14525241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick// Check for expressions that ScalarEvolution generates to compute 14535241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick// BackedgeTakenInfo. If these expressions have not been reduced, then expanding 14545241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick// them may incur additional cost (albeit in the loop preheader). 14555241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trickstatic bool isHighCostExpansion(const SCEV *S, BranchInst *BI, 14565241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick ScalarEvolution *SE) { 14575241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick // If the backedge-taken count is a UDiv, it's very likely a UDiv that 14585241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick // ScalarEvolution's HowFarToZero or HowManyLessThans produced to compute a 14595241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick // precise expression, rather than a UDiv from the user's code. If we can't 14605241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick // find a UDiv in the code with some simple searching, assume the former and 14615241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick // forego rewriting the loop. 14625241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick if (isa<SCEVUDivExpr>(S)) { 14635241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick ICmpInst *OrigCond = dyn_cast<ICmpInst>(BI->getCondition()); 14645241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick if (!OrigCond) return true; 14655241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick const SCEV *R = SE->getSCEV(OrigCond->getOperand(1)); 14665241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick R = SE->getMinusSCEV(R, SE->getConstant(R->getType(), 1)); 14675241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick if (R != S) { 14685241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick const SCEV *L = SE->getSCEV(OrigCond->getOperand(0)); 14695241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick L = SE->getMinusSCEV(L, SE->getConstant(L->getType(), 1)); 14705241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick if (L != S) 14715241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick return true; 14725241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick } 14735241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick } 14745241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick 1475fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick if (!DisableIVRewrite || ForceLFTR) 14765241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick return false; 14775241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick 14785241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick // Recurse past add expressions, which commonly occur in the 14795241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick // BackedgeTakenCount. They may already exist in program code, and if not, 14805241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick // they are not too expensive rematerialize. 14815241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) { 14825241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick for (SCEVAddExpr::op_iterator I = Add->op_begin(), E = Add->op_end(); 14835241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick I != E; ++I) { 14845241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick if (isHighCostExpansion(*I, BI, SE)) 14855241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick return true; 14865241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick } 14875241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick return false; 14885241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick } 14895241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick 14905241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick // HowManyLessThans uses a Max expression whenever the loop is not guarded by 14915241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick // the exit condition. 14925241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick if (isa<SCEVSMaxExpr>(S) || isa<SCEVUMaxExpr>(S)) 14935241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick return true; 14945241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick 14955241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick // If we haven't recognized an expensive SCEV patter, assume its an expression 14965241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick // produced by program code. 14975241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick return false; 14985241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick} 14995241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick 15001a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick/// canExpandBackedgeTakenCount - Return true if this loop's backedge taken 15011a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick/// count expression can be safely and cheaply expanded into an instruction 15021a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick/// sequence that can be used by LinearFunctionTestReplace. 15031a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trickstatic bool canExpandBackedgeTakenCount(Loop *L, ScalarEvolution *SE) { 15041a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick const SCEV *BackedgeTakenCount = SE->getBackedgeTakenCount(L); 15051a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (isa<SCEVCouldNotCompute>(BackedgeTakenCount) || 15061a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick BackedgeTakenCount->isZero()) 1507a52838285b6dce66821f0b272cb3479af8c3edb2Dan Gohman return false; 1508a52838285b6dce66821f0b272cb3479af8c3edb2Dan Gohman 15091a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (!L->getExitingBlock()) 15101a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick return false; 151137da40875873d70b83dc08b2803052bec9b68886Andrew Trick 15121a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // Can't rewrite non-branch yet. 15131a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick BranchInst *BI = dyn_cast<BranchInst>(L->getExitingBlock()->getTerminator()); 15141a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (!BI) 15151a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick return false; 151660f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman 15175241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick if (isHighCostExpansion(BackedgeTakenCount, BI, SE)) 15185241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick return false; 15195241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick 15201a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick return true; 15211a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick} 152260f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman 15231a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick/// getBackedgeIVType - Get the widest type used by the loop test after peeking 15241a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick/// through Truncs. 15251a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick/// 1526fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick/// TODO: Unnecessary when ForceLFTR is removed. 1527db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattnerstatic Type *getBackedgeIVType(Loop *L) { 15281a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (!L->getExitingBlock()) 15291a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick return 0; 15309caed5440d59dac4b388152fe8b993dc0491e5e9Chris Lattner 15311a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // Can't rewrite non-branch yet. 15321a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick BranchInst *BI = dyn_cast<BranchInst>(L->getExitingBlock()->getTerminator()); 15331a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (!BI) 15341a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick return 0; 1535156d460c758463eb407590cba2371857daf27d8aAndrew Trick 15361a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick ICmpInst *Cond = dyn_cast<ICmpInst>(BI->getCondition()); 15371a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (!Cond) 15381a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick return 0; 153937da40875873d70b83dc08b2803052bec9b68886Andrew Trick 1540db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner Type *Ty = 0; 15411a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick for(User::op_iterator OI = Cond->op_begin(), OE = Cond->op_end(); 15421a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick OI != OE; ++OI) { 15431a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick assert((!Ty || Ty == (*OI)->getType()) && "bad icmp operand types"); 15441a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick TruncInst *Trunc = dyn_cast<TruncInst>(*OI); 15451a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (!Trunc) 15461a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick continue; 154740bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner 15481a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick return Trunc->getSrcTy(); 15491a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick } 15501a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick return Ty; 15511a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick} 1552a590b79ee227b93c59f60ce1f54cae7a9ebec7c1Dan Gohman 1553fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick/// isLoopInvariant - Perform a quick domtree based check for loop invariance 1554fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick/// assuming that V is used within the loop. LoopInfo::isLoopInvariant() seems 1555fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick/// gratuitous for this purpose. 1556fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trickstatic bool isLoopInvariant(Value *V, Loop *L, DominatorTree *DT) { 1557fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick Instruction *Inst = dyn_cast<Instruction>(V); 1558fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick if (!Inst) 1559fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick return true; 1560fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick 1561fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick return DT->properlyDominates(Inst->getParent(), L->getHeader()); 1562fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick} 1563fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick 1564fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick/// getLoopPhiForCounter - Return the loop header phi IFF IncV adds a loop 1565fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick/// invariant value to the phi. 1566fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trickstatic PHINode *getLoopPhiForCounter(Value *IncV, Loop *L, DominatorTree *DT) { 1567fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick Instruction *IncI = dyn_cast<Instruction>(IncV); 1568fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick if (!IncI) 1569fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick return 0; 1570fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick 1571fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick switch (IncI->getOpcode()) { 1572fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick case Instruction::Add: 1573fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick case Instruction::Sub: 1574fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick break; 1575fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick case Instruction::GetElementPtr: 1576fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick // An IV counter must preserve its type. 1577fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick if (IncI->getNumOperands() == 2) 1578fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick break; 1579fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick default: 1580fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick return 0; 1581fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick } 1582fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick 1583fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick PHINode *Phi = dyn_cast<PHINode>(IncI->getOperand(0)); 1584fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick if (Phi && Phi->getParent() == L->getHeader()) { 1585fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick if (isLoopInvariant(IncI->getOperand(1), L, DT)) 1586fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick return Phi; 1587fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick return 0; 1588fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick } 1589fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick if (IncI->getOpcode() == Instruction::GetElementPtr) 1590fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick return 0; 1591fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick 1592fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick // Allow add/sub to be commuted. 1593fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick Phi = dyn_cast<PHINode>(IncI->getOperand(1)); 1594fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick if (Phi && Phi->getParent() == L->getHeader()) { 1595fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick if (isLoopInvariant(IncI->getOperand(0), L, DT)) 1596fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick return Phi; 1597fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick } 1598fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick return 0; 1599fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick} 1600fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick 1601fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick/// needsLFTR - LinearFunctionTestReplace policy. Return true unless we can show 1602fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick/// that the current exit test is already sufficiently canonical. 1603fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trickstatic bool needsLFTR(Loop *L, DominatorTree *DT) { 1604fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick assert(L->getExitingBlock() && "expected loop exit"); 1605fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick 1606fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick BasicBlock *LatchBlock = L->getLoopLatch(); 1607fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick // Don't bother with LFTR if the loop is not properly simplified. 1608fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick if (!LatchBlock) 1609fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick return false; 1610fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick 1611fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick BranchInst *BI = dyn_cast<BranchInst>(L->getExitingBlock()->getTerminator()); 1612fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick assert(BI && "expected exit branch"); 1613fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick 1614fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick // Do LFTR to simplify the exit condition to an ICMP. 1615fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick ICmpInst *Cond = dyn_cast<ICmpInst>(BI->getCondition()); 1616fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick if (!Cond) 1617fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick return true; 1618fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick 1619fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick // Do LFTR to simplify the exit ICMP to EQ/NE 1620fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick ICmpInst::Predicate Pred = Cond->getPredicate(); 1621fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick if (Pred != ICmpInst::ICMP_NE && Pred != ICmpInst::ICMP_EQ) 1622fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick return true; 1623fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick 1624fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick // Look for a loop invariant RHS 1625fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick Value *LHS = Cond->getOperand(0); 1626fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick Value *RHS = Cond->getOperand(1); 1627fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick if (!isLoopInvariant(RHS, L, DT)) { 1628fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick if (!isLoopInvariant(LHS, L, DT)) 1629fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick return true; 1630fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick std::swap(LHS, RHS); 1631fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick } 1632fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick // Look for a simple IV counter LHS 1633fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick PHINode *Phi = dyn_cast<PHINode>(LHS); 1634fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick if (!Phi) 1635fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick Phi = getLoopPhiForCounter(LHS, L, DT); 1636fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick 1637fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick if (!Phi) 1638fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick return true; 1639fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick 1640fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick // Do LFTR if the exit condition's IV is *not* a simple counter. 1641fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick Value *IncV = Phi->getIncomingValueForBlock(L->getLoopLatch()); 1642fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick return Phi != getLoopPhiForCounter(IncV, L, DT); 1643fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick} 1644fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick 1645fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick/// AlmostDeadIV - Return true if this IV has any uses other than the (soon to 1646fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick/// be rewritten) loop exit test. 1647fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trickstatic bool AlmostDeadIV(PHINode *Phi, BasicBlock *LatchBlock, Value *Cond) { 1648fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick int LatchIdx = Phi->getBasicBlockIndex(LatchBlock); 1649fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick Value *IncV = Phi->getIncomingValue(LatchIdx); 1650fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick 1651fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick for (Value::use_iterator UI = Phi->use_begin(), UE = Phi->use_end(); 1652fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick UI != UE; ++UI) { 1653fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick if (*UI != Cond && *UI != IncV) return false; 1654fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick } 1655fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick 1656fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick for (Value::use_iterator UI = IncV->use_begin(), UE = IncV->use_end(); 1657fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick UI != UE; ++UI) { 1658fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick if (*UI != Cond && *UI != Phi) return false; 1659fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick } 1660fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick return true; 1661fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick} 1662fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick 1663fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick/// FindLoopCounter - Find an affine IV in canonical form. 1664fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick/// 1665fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick/// FIXME: Accept -1 stride and set IVLimit = IVInit - BECount 1666fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick/// 1667fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick/// FIXME: Accept non-unit stride as long as SCEV can reduce BECount * Stride. 1668fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick/// This is difficult in general for SCEV because of potential overflow. But we 1669fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick/// could at least handle constant BECounts. 1670fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trickstatic PHINode * 1671fc933c073e9357a791c0f6b307355ed735e3557fAndrew TrickFindLoopCounter(Loop *L, const SCEV *BECount, 1672fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick ScalarEvolution *SE, DominatorTree *DT, const TargetData *TD) { 1673fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick // I'm not sure how BECount could be a pointer type, but we definitely don't 1674fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick // want to LFTR that. 1675fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick if (BECount->getType()->isPointerTy()) 1676fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick return 0; 1677fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick 1678fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick uint64_t BCWidth = SE->getTypeSizeInBits(BECount->getType()); 1679fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick 1680fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick Value *Cond = 1681fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick cast<BranchInst>(L->getExitingBlock()->getTerminator())->getCondition(); 1682fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick 1683fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick // Loop over all of the PHI nodes, looking for a simple counter. 1684fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick PHINode *BestPhi = 0; 1685fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick const SCEV *BestInit = 0; 1686fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick BasicBlock *LatchBlock = L->getLoopLatch(); 1687fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick assert(LatchBlock && "needsLFTR should guarantee a loop latch"); 1688fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick 1689fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I) { 1690fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick PHINode *Phi = cast<PHINode>(I); 1691fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick if (!SE->isSCEVable(Phi->getType())) 1692fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick continue; 1693fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick 1694fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(SE->getSCEV(Phi)); 1695fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick if (!AR || AR->getLoop() != L || !AR->isAffine()) 1696fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick continue; 1697fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick 1698fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick // AR may be a pointer type, while BECount is an integer type. 1699fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick // AR may be wider than BECount. With eq/ne tests overflow is immaterial. 1700fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick // AR may not be a narrower type, or we may never exit. 1701fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick uint64_t PhiWidth = SE->getTypeSizeInBits(AR->getType()); 1702fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick if (PhiWidth < BCWidth || (TD && !TD->isLegalInteger(PhiWidth))) 1703fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick continue; 1704fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick 1705fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick const SCEV *Step = dyn_cast<SCEVConstant>(AR->getStepRecurrence(*SE)); 1706fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick if (!Step || !Step->isOne()) 1707fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick continue; 1708fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick 1709fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick int LatchIdx = Phi->getBasicBlockIndex(LatchBlock); 1710fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick Value *IncV = Phi->getIncomingValue(LatchIdx); 1711fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick if (getLoopPhiForCounter(IncV, L, DT) != Phi) 1712fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick continue; 1713fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick 1714fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick const SCEV *Init = AR->getStart(); 1715fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick 1716fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick if (BestPhi && !AlmostDeadIV(BestPhi, LatchBlock, Cond)) { 1717fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick // Don't force a live loop counter if another IV can be used. 1718fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick if (AlmostDeadIV(Phi, LatchBlock, Cond)) 1719fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick continue; 1720fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick 1721fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick // Prefer to count-from-zero. This is a more "canonical" counter form. It 1722fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick // also prefers integer to pointer IVs. 1723fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick if (BestInit->isZero() != Init->isZero()) { 1724fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick if (BestInit->isZero()) 1725fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick continue; 1726fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick } 1727fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick // If two IVs both count from zero or both count from nonzero then the 1728fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick // narrower is likely a dead phi that has been widened. Use the wider phi 1729fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick // to allow the other to be eliminated. 1730fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick if (PhiWidth <= SE->getTypeSizeInBits(BestPhi->getType())) 1731fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick continue; 1732fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick } 1733fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick BestPhi = Phi; 1734fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick BestInit = Init; 1735fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick } 1736fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick return BestPhi; 1737fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick} 1738fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick 17391a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick/// LinearFunctionTestReplace - This method rewrites the exit condition of the 17401a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick/// loop to be a canonical != comparison against the incremented loop induction 17411a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick/// variable. This pass is able to rewrite the exit tests of any loop where the 17421a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick/// SCEV analysis can determine a loop-invariant trip count of the loop, which 17431a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick/// is actually a much broader range than just linear tests. 1744fc933c073e9357a791c0f6b307355ed735e3557fAndrew TrickValue *IndVarSimplify:: 17451a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew TrickLinearFunctionTestReplace(Loop *L, 17461a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick const SCEV *BackedgeTakenCount, 17471a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick PHINode *IndVar, 17481a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick SCEVExpander &Rewriter) { 17491a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick assert(canExpandBackedgeTakenCount(L, SE) && "precondition"); 17501a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick BranchInst *BI = cast<BranchInst>(L->getExitingBlock()->getTerminator()); 17511a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 1752fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick // In DisableIVRewrite mode, IndVar is not necessarily a canonical IV. In this 1753fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick // mode, LFTR can ignore IV overflow and truncate to the width of 1754fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick // BECount. This avoids materializing the add(zext(add)) expression. 1755fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick Type *CntTy = DisableIVRewrite ? 1756fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick BackedgeTakenCount->getType() : IndVar->getType(); 1757fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick 1758fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick const SCEV *IVLimit = BackedgeTakenCount; 1759fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick 17601a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // If the exiting block is not the same as the backedge block, we must compare 17611a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // against the preincremented value, otherwise we prefer to compare against 17621a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // the post-incremented value. 17631a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick Value *CmpIndVar; 17641a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (L->getExitingBlock() == L->getLoopLatch()) { 17651a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // Add one to the "backedge-taken" count to get the trip count. 17661a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // If this addition may overflow, we have to be more pessimistic and 17671a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // cast the induction variable before doing the add. 17681a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick const SCEV *N = 1769fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick SE->getAddExpr(IVLimit, SE->getConstant(IVLimit->getType(), 1)); 1770fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick if (CntTy == IVLimit->getType()) 1771fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick IVLimit = N; 1772fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick else { 1773fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick const SCEV *Zero = SE->getConstant(IVLimit->getType(), 0); 1774fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick if ((isa<SCEVConstant>(N) && !N->isZero()) || 1775fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick SE->isLoopEntryGuardedByCond(L, ICmpInst::ICMP_NE, N, Zero)) { 1776fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick // No overflow. Cast the sum. 1777fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick IVLimit = SE->getTruncateOrZeroExtend(N, CntTy); 1778fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick } else { 1779fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick // Potential overflow. Cast before doing the add. 1780fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick IVLimit = SE->getTruncateOrZeroExtend(IVLimit, CntTy); 1781fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick IVLimit = SE->getAddExpr(IVLimit, SE->getConstant(CntTy, 1)); 1782fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick } 17831a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick } 17841a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // The BackedgeTaken expression contains the number of times that the 17851a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // backedge branches to the loop header. This is one less than the 17861a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // number of times the loop executes, so use the incremented indvar. 17871a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick CmpIndVar = IndVar->getIncomingValueForBlock(L->getExitingBlock()); 17881a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick } else { 17891a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // We have to use the preincremented value... 1790fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick IVLimit = SE->getTruncateOrZeroExtend(IVLimit, CntTy); 17911a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick CmpIndVar = IndVar; 17921a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick } 17931a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 1794fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick // For unit stride, IVLimit = Start + BECount with 2's complement overflow. 1795fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick // So for, non-zero start compute the IVLimit here. 1796fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick bool isPtrIV = false; 1797fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick Type *CmpTy = CntTy; 1798fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(SE->getSCEV(IndVar)); 1799fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick assert(AR && AR->getLoop() == L && AR->isAffine() && "bad loop counter"); 1800fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick if (!AR->getStart()->isZero()) { 1801fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick assert(AR->getStepRecurrence(*SE)->isOne() && "only handles unit stride"); 1802fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick const SCEV *IVInit = AR->getStart(); 1803fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick 1804fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick // For pointer types, sign extend BECount in order to materialize a GEP. 1805fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick // Note that for DisableIVRewrite, we never run SCEVExpander on a 1806fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick // pointer type, because we must preserve the existing GEPs. Instead we 1807fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick // directly generate a GEP later. 1808fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick if (IVInit->getType()->isPointerTy()) { 1809fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick isPtrIV = true; 1810fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick CmpTy = SE->getEffectiveSCEVType(IVInit->getType()); 1811fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick IVLimit = SE->getTruncateOrSignExtend(IVLimit, CmpTy); 1812fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick } 1813fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick // For integer types, truncate the IV before computing IVInit + BECount. 1814fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick else { 1815fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick if (SE->getTypeSizeInBits(IVInit->getType()) 1816fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick > SE->getTypeSizeInBits(CmpTy)) 1817fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick IVInit = SE->getTruncateExpr(IVInit, CmpTy); 1818fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick 1819fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick IVLimit = SE->getAddExpr(IVInit, IVLimit); 1820fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick } 1821fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick } 18221a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // Expand the code for the iteration count. 1823fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick IRBuilder<> Builder(BI); 1824fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick 1825fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick assert(SE->isLoopInvariant(IVLimit, L) && 18261a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick "Computed iteration count is not loop invariant!"); 1827fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick Value *ExitCnt = Rewriter.expandCodeFor(IVLimit, CmpTy, BI); 1828fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick 1829fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick // Create a gep for IVInit + IVLimit from on an existing pointer base. 1830fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick assert(isPtrIV == IndVar->getType()->isPointerTy() && 1831fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick "IndVar type must match IVInit type"); 1832fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick if (isPtrIV) { 1833fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick Value *IVStart = IndVar->getIncomingValueForBlock(L->getLoopPreheader()); 1834fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick assert(AR->getStart() == SE->getSCEV(IVStart) && "bad loop counter"); 1835fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick const PointerType *PointerTy = cast<PointerType>(IVStart->getType()); 1836fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick assert(SE->getSizeOfExpr(PointerTy->getElementType())->isOne() && 1837fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick "unit stride pointer IV must be i8*"); 1838fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick 1839fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick Builder.SetInsertPoint(L->getLoopPreheader()->getTerminator()); 1840fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick ExitCnt = Builder.CreateGEP(IVStart, ExitCnt, "lftr.limit"); 1841fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick Builder.SetInsertPoint(BI); 1842fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick } 18431a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 18441a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // Insert a new icmp_ne or icmp_eq instruction before the branch. 1845fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick ICmpInst::Predicate P; 18461a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (L->contains(BI->getSuccessor(0))) 1847fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick P = ICmpInst::ICMP_NE; 18481a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick else 1849fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick P = ICmpInst::ICMP_EQ; 18501a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 18511a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick DEBUG(dbgs() << "INDVARS: Rewriting loop exit condition to:\n" 18521a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick << " LHS:" << *CmpIndVar << '\n' 18531a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick << " op:\t" 1854fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick << (P == ICmpInst::ICMP_NE ? "!=" : "==") << "\n" 1855fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick << " RHS:\t" << *ExitCnt << "\n" 1856fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick << " Expr:\t" << *IVLimit << "\n"); 18571a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 1858fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick if (SE->getTypeSizeInBits(CmpIndVar->getType()) 1859fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick > SE->getTypeSizeInBits(CmpTy)) { 1860fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick CmpIndVar = Builder.CreateTrunc(CmpIndVar, CmpTy, "lftr.wideiv"); 1861fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick } 1862fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick 1863fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick Value *Cond = Builder.CreateICmp(P, CmpIndVar, ExitCnt, "exitcond"); 18641a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick Value *OrigCond = BI->getCondition(); 18651a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // It's tempting to use replaceAllUsesWith here to fully replace the old 18661a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // comparison, but that's not immediately safe, since users of the old 18671a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // comparison may not be dominated by the new comparison. Instead, just 18681a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // update the branch to use the new comparison; in the common case this 18691a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // will make old comparison dead. 18701a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick BI->setCondition(Cond); 18711a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick DeadInsts.push_back(OrigCond); 18721a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 18731a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick ++NumLFTR; 18741a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick Changed = true; 18751a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick return Cond; 18761a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick} 18771a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 18781a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick//===----------------------------------------------------------------------===// 18791a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick// SinkUnusedInvariants. A late subpass to cleanup loop preheaders. 18801a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick//===----------------------------------------------------------------------===// 18811a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 18821a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick/// If there's a single exit block, sink any loop-invariant values that 18831a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick/// were defined in the preheader but not used inside the loop into the 18841a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick/// exit block to reduce register pressure in the loop. 18851a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trickvoid IndVarSimplify::SinkUnusedInvariants(Loop *L) { 18861a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick BasicBlock *ExitBlock = L->getExitBlock(); 18871a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (!ExitBlock) return; 18881a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 18891a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick BasicBlock *Preheader = L->getLoopPreheader(); 18901a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (!Preheader) return; 18911a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 18921a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick Instruction *InsertPt = ExitBlock->getFirstNonPHI(); 18931a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick BasicBlock::iterator I = Preheader->getTerminator(); 18941a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick while (I != Preheader->begin()) { 18951a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick --I; 18961a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // New instructions were inserted at the end of the preheader. 18971a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (isa<PHINode>(I)) 18981a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick break; 18991a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 19001a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // Don't move instructions which might have side effects, since the side 19011a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // effects need to complete before instructions inside the loop. Also don't 19021a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // move instructions which might read memory, since the loop may modify 19031a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // memory. Note that it's okay if the instruction might have undefined 19041a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // behavior: LoopSimplify guarantees that the preheader dominates the exit 19051a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // block. 19061a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (I->mayHaveSideEffects() || I->mayReadFromMemory()) 19071a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick continue; 19081a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 19091a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // Skip debug info intrinsics. 19101a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (isa<DbgInfoIntrinsic>(I)) 19111a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick continue; 19121a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 19131a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // Don't sink static AllocaInsts out of the entry block, which would 19141a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // turn them into dynamic allocas! 19151a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (AllocaInst *AI = dyn_cast<AllocaInst>(I)) 19161a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (AI->isStaticAlloca()) 19171a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick continue; 19181a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 19191a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // Determine if there is a use in or before the loop (direct or 19201a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // otherwise). 19211a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick bool UsedInLoop = false; 19221a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick for (Value::use_iterator UI = I->use_begin(), UE = I->use_end(); 19231a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick UI != UE; ++UI) { 19241a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick User *U = *UI; 19251a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick BasicBlock *UseBB = cast<Instruction>(U)->getParent(); 19261a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (PHINode *P = dyn_cast<PHINode>(U)) { 19271a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick unsigned i = 19281a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick PHINode::getIncomingValueNumForOperand(UI.getOperandNo()); 19291a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick UseBB = P->getIncomingBlock(i); 19301a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick } 19311a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (UseBB == Preheader || L->contains(UseBB)) { 19321a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick UsedInLoop = true; 19331a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick break; 19341a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick } 19351a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick } 19361a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 19371a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // If there is, the def must remain in the preheader. 19381a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (UsedInLoop) 19391a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick continue; 19401a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 19411a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // Otherwise, sink it to the exit block. 19421a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick Instruction *ToMove = I; 19431a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick bool Done = false; 19441a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 19451a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (I != Preheader->begin()) { 19461a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // Skip debug info intrinsics. 19471a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick do { 19481a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick --I; 19491a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick } while (isa<DbgInfoIntrinsic>(I) && I != Preheader->begin()); 19501a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 19511a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (isa<DbgInfoIntrinsic>(I) && I == Preheader->begin()) 19521a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick Done = true; 19531a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick } else { 19541a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick Done = true; 19551a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick } 19561a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 19571a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick ToMove->moveBefore(InsertPt); 19581a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (Done) break; 19591a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick InsertPt = ToMove; 19601a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick } 19611a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick} 19621a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 19631a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick//===----------------------------------------------------------------------===// 19641a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick// IndVarSimplify driver. Manage several subpasses of IV simplification. 19651a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick//===----------------------------------------------------------------------===// 19661a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 19671a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trickbool IndVarSimplify::runOnLoop(Loop *L, LPPassManager &LPM) { 19681a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // If LoopSimplify form is not available, stay out of trouble. Some notes: 19691a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // - LSR currently only supports LoopSimplify-form loops. Indvars' 19701a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // canonicalization can be a pessimization without LSR to "clean up" 19711a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // afterwards. 19721a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // - We depend on having a preheader; in particular, 19731a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // Loop::getCanonicalInductionVariable only supports loops with preheaders, 19741a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // and we're in trouble if we can't find the induction variable even when 19751a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // we've manually inserted one. 19761a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (!L->isLoopSimplifyForm()) 19771a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick return false; 19781a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 19791a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (!DisableIVRewrite) 19801a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick IU = &getAnalysis<IVUsers>(); 19811a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick LI = &getAnalysis<LoopInfo>(); 19821a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick SE = &getAnalysis<ScalarEvolution>(); 19831a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick DT = &getAnalysis<DominatorTree>(); 19841a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick TD = getAnalysisIfAvailable<TargetData>(); 19851a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 19861a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick DeadInsts.clear(); 19871a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick Changed = false; 19881a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 19891a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // If there are any floating-point recurrences, attempt to 19901a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // transform them to use integer recurrences. 19911a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick RewriteNonIntegerIVs(L); 19921a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 19931a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick const SCEV *BackedgeTakenCount = SE->getBackedgeTakenCount(L); 19941a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 19951a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // Create a rewriter object which we'll use to transform the code with. 19961a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick SCEVExpander Rewriter(*SE, "indvars"); 19971a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 19981a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // Eliminate redundant IV users. 19991a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // 20001a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // Simplification works best when run before other consumers of SCEV. We 20011a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // attempt to avoid evaluating SCEVs for sign/zero extend operations until 20021a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // other expressions involving loop IVs have been evaluated. This helps SCEV 20031a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // set no-wrap flags before normalizing sign/zero extension. 20041a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (DisableIVRewrite) { 20051a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick Rewriter.disableCanonicalMode(); 20061a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick SimplifyIVUsersNoRewrite(L, Rewriter); 20071a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick } 20081a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 20091a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // Check to see if this loop has a computable loop-invariant execution count. 20101a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // If so, this means that we can compute the final value of any expressions 20111a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // that are recurrent in the loop, and substitute the exit values from the 20121a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // loop into any instructions outside of the loop that use the final values of 20131a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // the current expressions. 20141a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // 20151a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (!isa<SCEVCouldNotCompute>(BackedgeTakenCount)) 20161a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick RewriteLoopExitValues(L, Rewriter); 20171a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 20181a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // Eliminate redundant IV users. 20191a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (!DisableIVRewrite) 20201a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick SimplifyIVUsers(Rewriter); 20211a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 20226f684b0becc4c1b2ece3ec6dcecf30b19343128dAndrew Trick // Eliminate redundant IV cycles. 2023037d1c0c7e01cefeff7e538682c9a1e536e14030Andrew Trick if (DisableIVRewrite) 2024037d1c0c7e01cefeff7e538682c9a1e536e14030Andrew Trick SimplifyCongruentIVs(L); 2025037d1c0c7e01cefeff7e538682c9a1e536e14030Andrew Trick 202681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Compute the type of the largest recurrence expression, and decide whether 202781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // a canonical induction variable should be inserted. 2028db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner Type *LargestType = 0; 202981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman bool NeedCannIV = false; 2030fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick bool ReuseIVForExit = DisableIVRewrite && !ForceLFTR; 203103d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick bool ExpandBECount = canExpandBackedgeTakenCount(L, SE); 2032fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick if (ExpandBECount && !ReuseIVForExit) { 203381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // If we have a known trip count and a single exit block, we'll be 203481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // rewriting the loop exit test condition below, which requires a 203581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // canonical induction variable. 20364dfdf242c1917e98f407818eb5b68ae0b4678f26Andrew Trick NeedCannIV = true; 2037db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner Type *Ty = BackedgeTakenCount->getType(); 203803d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick if (DisableIVRewrite) { 203903d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick // In this mode, SimplifyIVUsers may have already widened the IV used by 204003d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick // the backedge test and inserted a Trunc on the compare's operand. Get 204103d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick // the wider type to avoid creating a redundant narrow IV only used by the 204203d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick // loop test. 204303d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick LargestType = getBackedgeIVType(L); 204403d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick } 20454dfdf242c1917e98f407818eb5b68ae0b4678f26Andrew Trick if (!LargestType || 20464dfdf242c1917e98f407818eb5b68ae0b4678f26Andrew Trick SE->getTypeSizeInBits(Ty) > 20474dfdf242c1917e98f407818eb5b68ae0b4678f26Andrew Trick SE->getTypeSizeInBits(LargestType)) 20484dfdf242c1917e98f407818eb5b68ae0b4678f26Andrew Trick LargestType = SE->getEffectiveSCEVType(Ty); 2049f50af088f19f525f3d1026eb61db77e0037a9f43Chris Lattner } 205037da40875873d70b83dc08b2803052bec9b68886Andrew Trick if (!DisableIVRewrite) { 205137da40875873d70b83dc08b2803052bec9b68886Andrew Trick for (IVUsers::const_iterator I = IU->begin(), E = IU->end(); I != E; ++I) { 205237da40875873d70b83dc08b2803052bec9b68886Andrew Trick NeedCannIV = true; 2053db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner Type *Ty = 205437da40875873d70b83dc08b2803052bec9b68886Andrew Trick SE->getEffectiveSCEVType(I->getOperandValToReplace()->getType()); 205537da40875873d70b83dc08b2803052bec9b68886Andrew Trick if (!LargestType || 205637da40875873d70b83dc08b2803052bec9b68886Andrew Trick SE->getTypeSizeInBits(Ty) > 2057af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman SE->getTypeSizeInBits(LargestType)) 205837da40875873d70b83dc08b2803052bec9b68886Andrew Trick LargestType = Ty; 205937da40875873d70b83dc08b2803052bec9b68886Andrew Trick } 2060500597a1c39e91a3020587318ed61e737b6c613aChris Lattner } 2061394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner 2062f451cb870efcf9e0302d25ed05f4cac6bb494e42Dan Gohman // Now that we know the largest of the induction variable expressions 206381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // in this loop, insert a canonical induction variable of the largest size. 206443ef3fbae12c7924a25df4563d86084973db9c67Dan Gohman PHINode *IndVar = 0; 206581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (NeedCannIV) { 206685669637139089eaed8def1583ac04266c9654e2Dan Gohman // Check to see if the loop already has any canonical-looking induction 206785669637139089eaed8def1583ac04266c9654e2Dan Gohman // variables. If any are present and wider than the planned canonical 206885669637139089eaed8def1583ac04266c9654e2Dan Gohman // induction variable, temporarily remove them, so that the Rewriter 206985669637139089eaed8def1583ac04266c9654e2Dan Gohman // doesn't attempt to reuse them. 207085669637139089eaed8def1583ac04266c9654e2Dan Gohman SmallVector<PHINode *, 2> OldCannIVs; 207185669637139089eaed8def1583ac04266c9654e2Dan Gohman while (PHINode *OldCannIV = L->getCanonicalInductionVariable()) { 20724d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman if (SE->getTypeSizeInBits(OldCannIV->getType()) > 20734d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman SE->getTypeSizeInBits(LargestType)) 20744d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman OldCannIV->removeFromParent(); 20754d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman else 207685669637139089eaed8def1583ac04266c9654e2Dan Gohman break; 207785669637139089eaed8def1583ac04266c9654e2Dan Gohman OldCannIVs.push_back(OldCannIV); 20784d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman } 20794d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman 2080667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman IndVar = Rewriter.getOrInsertCanonicalInductionVariable(L, LargestType); 20814d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman 2082c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman ++NumInserted; 2083c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman Changed = true; 2084f67ef318aa29e7cc0c7de76349881959936d9eeeDavid Greene DEBUG(dbgs() << "INDVARS: New CanIV: " << *IndVar << '\n'); 20854d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman 20864d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman // Now that the official induction variable is established, reinsert 208785669637139089eaed8def1583ac04266c9654e2Dan Gohman // any old canonical-looking variables after it so that the IR remains 208885669637139089eaed8def1583ac04266c9654e2Dan Gohman // consistent. They will be deleted as part of the dead-PHI deletion at 20894d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman // the end of the pass. 209085669637139089eaed8def1583ac04266c9654e2Dan Gohman while (!OldCannIVs.empty()) { 209185669637139089eaed8def1583ac04266c9654e2Dan Gohman PHINode *OldCannIV = OldCannIVs.pop_back_val(); 209285669637139089eaed8def1583ac04266c9654e2Dan Gohman OldCannIV->insertBefore(L->getHeader()->getFirstNonPHI()); 209385669637139089eaed8def1583ac04266c9654e2Dan Gohman } 2094d19534add90a2a894af61523b830887097bb780bDan Gohman } 2095fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick else if (ExpandBECount && ReuseIVForExit && needsLFTR(L, DT)) { 2096fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick IndVar = FindLoopCounter(L, BackedgeTakenCount, SE, DT, TD); 2097fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick } 2098c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman // If we have a trip count expression, rewrite the loop's exit condition 2099c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman // using it. We can currently only handle loops with a single exit. 2100fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick Value *NewICmp = 0; 2101fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick if (ExpandBECount && IndVar) { 21025614769d557600fda3cf73b481581fe32fbff258Andrew Trick // Check preconditions for proper SCEVExpander operation. SCEV does not 21035614769d557600fda3cf73b481581fe32fbff258Andrew Trick // express SCEVExpander's dependencies, such as LoopSimplify. Instead any 21045614769d557600fda3cf73b481581fe32fbff258Andrew Trick // pass that uses the SCEVExpander must do it. This does not work well for 21055614769d557600fda3cf73b481581fe32fbff258Andrew Trick // loop passes because SCEVExpander makes assumptions about all loops, while 21065614769d557600fda3cf73b481581fe32fbff258Andrew Trick // LoopPassManager only forces the current loop to be simplified. 21075614769d557600fda3cf73b481581fe32fbff258Andrew Trick // 21085614769d557600fda3cf73b481581fe32fbff258Andrew Trick // FIXME: SCEV expansion has no way to bail out, so the caller must 21095614769d557600fda3cf73b481581fe32fbff258Andrew Trick // explicitly check any assumptions made by SCEV. Brittle. 21105614769d557600fda3cf73b481581fe32fbff258Andrew Trick const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(BackedgeTakenCount); 21115614769d557600fda3cf73b481581fe32fbff258Andrew Trick if (!AR || AR->getLoop()->getLoopPreheader()) 21125614769d557600fda3cf73b481581fe32fbff258Andrew Trick NewICmp = 21135614769d557600fda3cf73b481581fe32fbff258Andrew Trick LinearFunctionTestReplace(L, BackedgeTakenCount, IndVar, Rewriter); 211481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman } 2115b12a754cce0c1d5542af605203a47820edba454dAndrew Trick // Rewrite IV-derived expressions. 211637da40875873d70b83dc08b2803052bec9b68886Andrew Trick if (!DisableIVRewrite) 211737da40875873d70b83dc08b2803052bec9b68886Andrew Trick RewriteIVExpressions(L, Rewriter); 2118fcb81f5f4cbac61851b7dec403961cf88e614aa1Chris Lattner 2119b12a754cce0c1d5542af605203a47820edba454dAndrew Trick // Clear the rewriter cache, because values that are in the rewriter's cache 2120b12a754cce0c1d5542af605203a47820edba454dAndrew Trick // can be deleted in the loop below, causing the AssertingVH in the cache to 2121b12a754cce0c1d5542af605203a47820edba454dAndrew Trick // trigger. 2122b12a754cce0c1d5542af605203a47820edba454dAndrew Trick Rewriter.clear(); 2123b12a754cce0c1d5542af605203a47820edba454dAndrew Trick 2124b12a754cce0c1d5542af605203a47820edba454dAndrew Trick // Now that we're done iterating through lists, clean up any instructions 2125b12a754cce0c1d5542af605203a47820edba454dAndrew Trick // which are now dead. 2126b12a754cce0c1d5542af605203a47820edba454dAndrew Trick while (!DeadInsts.empty()) 2127b12a754cce0c1d5542af605203a47820edba454dAndrew Trick if (Instruction *Inst = 2128b12a754cce0c1d5542af605203a47820edba454dAndrew Trick dyn_cast_or_null<Instruction>(&*DeadInsts.pop_back_val())) 2129b12a754cce0c1d5542af605203a47820edba454dAndrew Trick RecursivelyDeleteTriviallyDeadInstructions(Inst); 2130b12a754cce0c1d5542af605203a47820edba454dAndrew Trick 2131667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman // The Rewriter may not be used from this point on. 21323d431384f05c9defc84f36eafe220415cc12ee93Torok Edwin 213381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Loop-invariant instructions in the preheader that aren't used in the 213481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // loop may be sunk below the loop to reduce register pressure. 2135667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman SinkUnusedInvariants(L); 213681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 213781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // For completeness, inform IVUsers of the IV use in the newly-created 213881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // loop exit test instruction. 2139fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick if (IU && NewICmp) { 2140fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick ICmpInst *NewICmpInst = dyn_cast<ICmpInst>(NewICmp); 2141fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick if (NewICmpInst) 2142fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick IU->AddUsersIfInteresting(cast<Instruction>(NewICmpInst->getOperand(0))); 2143fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick } 214481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Clean up dead instructions. 21459fff2187a21f765ed87a25c48552a6942450f3e2Dan Gohman Changed |= DeleteDeadPHIs(L->getHeader()); 214681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Check a post-condition. 2147f6a0dbaaf4f68f8e948a818135b9272776b8a52fAndrew Trick assert(L->isLCSSAForm(*DT) && 2148f6a0dbaaf4f68f8e948a818135b9272776b8a52fAndrew Trick "Indvars did not leave the loop in lcssa form!"); 2149f6a0dbaaf4f68f8e948a818135b9272776b8a52fAndrew Trick 2150f6a0dbaaf4f68f8e948a818135b9272776b8a52fAndrew Trick // Verify that LFTR, and any other change have not interfered with SCEV's 2151f6a0dbaaf4f68f8e948a818135b9272776b8a52fAndrew Trick // ability to compute trip count. 2152f6a0dbaaf4f68f8e948a818135b9272776b8a52fAndrew Trick#ifndef NDEBUG 2153f6a0dbaaf4f68f8e948a818135b9272776b8a52fAndrew Trick if (DisableIVRewrite && !isa<SCEVCouldNotCompute>(BackedgeTakenCount)) { 2154f6a0dbaaf4f68f8e948a818135b9272776b8a52fAndrew Trick SE->forgetLoop(L); 2155f6a0dbaaf4f68f8e948a818135b9272776b8a52fAndrew Trick const SCEV *NewBECount = SE->getBackedgeTakenCount(L); 2156f6a0dbaaf4f68f8e948a818135b9272776b8a52fAndrew Trick if (SE->getTypeSizeInBits(BackedgeTakenCount->getType()) < 2157f6a0dbaaf4f68f8e948a818135b9272776b8a52fAndrew Trick SE->getTypeSizeInBits(NewBECount->getType())) 2158f6a0dbaaf4f68f8e948a818135b9272776b8a52fAndrew Trick NewBECount = SE->getTruncateOrNoop(NewBECount, 2159f6a0dbaaf4f68f8e948a818135b9272776b8a52fAndrew Trick BackedgeTakenCount->getType()); 2160f6a0dbaaf4f68f8e948a818135b9272776b8a52fAndrew Trick else 2161f6a0dbaaf4f68f8e948a818135b9272776b8a52fAndrew Trick BackedgeTakenCount = SE->getTruncateOrNoop(BackedgeTakenCount, 2162f6a0dbaaf4f68f8e948a818135b9272776b8a52fAndrew Trick NewBECount->getType()); 2163f6a0dbaaf4f68f8e948a818135b9272776b8a52fAndrew Trick assert(BackedgeTakenCount == NewBECount && "indvars must preserve SCEV"); 2164f6a0dbaaf4f68f8e948a818135b9272776b8a52fAndrew Trick } 2165f6a0dbaaf4f68f8e948a818135b9272776b8a52fAndrew Trick#endif 2166f6a0dbaaf4f68f8e948a818135b9272776b8a52fAndrew Trick 216781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman return Changed; 216881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman} 2169