IndVarSimplify.cpp revision ca703bd56ba1f717b3735c6889334c319ca005b1
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" 55bdff548e4dd577a72094d57b282de4e765643b96Chris Lattner#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" 60a54b7cbd452b3adb2f51346140d996b29c2cdb30Reid Spencer#include "llvm/ADT/SmallVector.h" 61551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/Statistic.h" 6281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman#include "llvm/ADT/STLExtras.h" 6347df12d80db90e125e9f2ff764286ee11665476dJohn Criswellusing namespace llvm; 64d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 650e5f499638c8d277b9dc4a4385712177c53b5681Chris LattnerSTATISTIC(NumRemoved , "Number of aux indvars removed"); 660e5f499638c8d277b9dc4a4385712177c53b5681Chris LattnerSTATISTIC(NumInserted, "Number of canonical indvars added"); 670e5f499638c8d277b9dc4a4385712177c53b5681Chris LattnerSTATISTIC(NumReplaced, "Number of exit values replaced"); 680e5f499638c8d277b9dc4a4385712177c53b5681Chris LattnerSTATISTIC(NumLFTR , "Number of loop exit tests replaced"); 693324e718bc9ac2ede08a14c325848b576849542bChris Lattner 700e5f499638c8d277b9dc4a4385712177c53b5681Chris Lattnernamespace { 713e8b6631e67e01e4960a7ba4668a50c596607473Chris Lattner class IndVarSimplify : public LoopPass { 7281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman IVUsers *IU; 7340bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner LoopInfo *LI; 7440bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner ScalarEvolution *SE; 75de53dc03f5c1549f3176e979bbeeac965dfa5cbcDan Gohman DominatorTree *DT; 7615cad759fe2048ac5eb137c6bb0ab7287538677eChris Lattner bool Changed; 773324e718bc9ac2ede08a14c325848b576849542bChris Lattner public: 78794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel 795668cf77a77493ec9f2a9b33f08125e885c8e4cfDan Gohman static char ID; // Pass identification, replacement for typeid 805668cf77a77493ec9f2a9b33f08125e885c8e4cfDan Gohman IndVarSimplify() : LoopPass(&ID) {} 81794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel 825668cf77a77493ec9f2a9b33f08125e885c8e4cfDan Gohman virtual bool runOnLoop(Loop *L, LPPassManager &LPM); 8360f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman 845668cf77a77493ec9f2a9b33f08125e885c8e4cfDan Gohman virtual void getAnalysisUsage(AnalysisUsage &AU) const { 855668cf77a77493ec9f2a9b33f08125e885c8e4cfDan Gohman AU.addRequired<DominatorTree>(); 865668cf77a77493ec9f2a9b33f08125e885c8e4cfDan Gohman AU.addRequired<LoopInfo>(); 875668cf77a77493ec9f2a9b33f08125e885c8e4cfDan Gohman AU.addRequired<ScalarEvolution>(); 885668cf77a77493ec9f2a9b33f08125e885c8e4cfDan Gohman AU.addRequiredID(LoopSimplifyID); 895668cf77a77493ec9f2a9b33f08125e885c8e4cfDan Gohman AU.addRequiredID(LCSSAID); 905668cf77a77493ec9f2a9b33f08125e885c8e4cfDan Gohman AU.addRequired<IVUsers>(); 915668cf77a77493ec9f2a9b33f08125e885c8e4cfDan Gohman AU.addPreserved<ScalarEvolution>(); 925668cf77a77493ec9f2a9b33f08125e885c8e4cfDan Gohman AU.addPreservedID(LoopSimplifyID); 935668cf77a77493ec9f2a9b33f08125e885c8e4cfDan Gohman AU.addPreservedID(LCSSAID); 945668cf77a77493ec9f2a9b33f08125e885c8e4cfDan Gohman AU.addPreserved<IVUsers>(); 955668cf77a77493ec9f2a9b33f08125e885c8e4cfDan Gohman AU.setPreservesCFG(); 965668cf77a77493ec9f2a9b33f08125e885c8e4cfDan Gohman } 973324e718bc9ac2ede08a14c325848b576849542bChris Lattner 9840bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner private: 995ee99979065d75605d150d7e567e4351024aae8fDevang Patel 10060f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman void RewriteNonIntegerIVs(Loop *L); 10160f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman 1020bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman ICmpInst *LinearFunctionTestReplace(Loop *L, const SCEV *BackedgeTakenCount, 103a575871884b247b0946290876ac7d4657b384cf9Dan Gohman Value *IndVar, 104c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman BasicBlock *ExitingBlock, 105c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman BranchInst *BI, 10615cab2817b8f63fec0148609278bc2c1e05abb50Dan Gohman SCEVExpander &Rewriter); 107454d26dc43207ec537d843229db6f5e6a302e23dDan Gohman void RewriteLoopExitValues(Loop *L, SCEVExpander &Rewriter); 10840bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner 109454d26dc43207ec537d843229db6f5e6a302e23dDan Gohman void RewriteIVExpressions(Loop *L, SCEVExpander &Rewriter); 110d22a849282c45bbf7eb1734c274294d81e49e3a8Devang Patel 111667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman void SinkUnusedInvariants(Loop *L); 11281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 11381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman void HandleFloatingPointIV(Loop *L, PHINode *PH); 1143324e718bc9ac2ede08a14c325848b576849542bChris Lattner }; 1155e76140536ba66fadeced1cd892f79616f407e3cChris Lattner} 116394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner 117844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanchar IndVarSimplify::ID = 0; 118844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanstatic RegisterPass<IndVarSimplify> 119844731a7f1909f55935e3514c9e713a62d67662eDan GohmanX("indvars", "Canonicalize Induction Variables"); 120844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 121394f0441e06dafca29f0752cf400990a5b8fe4b1Daniel DunbarPass *llvm::createIndVarSimplifyPass() { 1223324e718bc9ac2ede08a14c325848b576849542bChris Lattner return new IndVarSimplify(); 123394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner} 124394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner 12540bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner/// LinearFunctionTestReplace - This method rewrites the exit condition of the 12659fdaeeae8f183e18bb6ad5c382ca23e28e6aaf6Chris Lattner/// loop to be a canonical != comparison against the incremented loop induction 12759fdaeeae8f183e18bb6ad5c382ca23e28e6aaf6Chris Lattner/// variable. This pass is able to rewrite the exit tests of any loop where the 12859fdaeeae8f183e18bb6ad5c382ca23e28e6aaf6Chris Lattner/// SCEV analysis can determine a loop-invariant trip count of the loop, which 12959fdaeeae8f183e18bb6ad5c382ca23e28e6aaf6Chris Lattner/// is actually a much broader range than just linear tests. 13081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan GohmanICmpInst *IndVarSimplify::LinearFunctionTestReplace(Loop *L, 1310bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *BackedgeTakenCount, 132c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman Value *IndVar, 133c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman BasicBlock *ExitingBlock, 134c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman BranchInst *BI, 13515cab2817b8f63fec0148609278bc2c1e05abb50Dan Gohman SCEVExpander &Rewriter) { 136d244057a48660c3cd30d219118ece3f947947790Chris Lattner // If the exiting block is not the same as the backedge block, we must compare 137d244057a48660c3cd30d219118ece3f947947790Chris Lattner // against the preincremented value, otherwise we prefer to compare against 138d244057a48660c3cd30d219118ece3f947947790Chris Lattner // the post-incremented value. 139c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman Value *CmpIndVar; 1400bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *RHS = BackedgeTakenCount; 141c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman if (ExitingBlock == L->getLoopLatch()) { 14246bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman // Add one to the "backedge-taken" count to get the trip count. 14346bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman // If this addition may overflow, we have to be more pessimistic and 14446bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman // cast the induction variable before doing the add. 1450bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *Zero = SE->getIntegerSCEV(0, BackedgeTakenCount->getType()); 1460bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *N = 14746bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman SE->getAddExpr(BackedgeTakenCount, 14846bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman SE->getIntegerSCEV(1, BackedgeTakenCount->getType())); 149c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman if ((isa<SCEVConstant>(N) && !N->isZero()) || 150c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman SE->isLoopGuardedByCond(L, ICmpInst::ICMP_NE, N, Zero)) { 151c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman // No overflow. Cast the sum. 15246bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman RHS = SE->getTruncateOrZeroExtend(N, IndVar->getType()); 153c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman } else { 154c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman // Potential overflow. Cast before doing the add. 15546bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman RHS = SE->getTruncateOrZeroExtend(BackedgeTakenCount, 15646bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman IndVar->getType()); 15746bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman RHS = SE->getAddExpr(RHS, 15846bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman SE->getIntegerSCEV(1, IndVar->getType())); 159c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman } 160c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman 16146bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman // The BackedgeTaken expression contains the number of times that the 16246bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman // backedge branches to the loop header. This is one less than the 16346bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman // number of times the loop executes, so use the incremented indvar. 164c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman CmpIndVar = L->getCanonicalInductionVariableIncrement(); 165d244057a48660c3cd30d219118ece3f947947790Chris Lattner } else { 166d244057a48660c3cd30d219118ece3f947947790Chris Lattner // We have to use the preincremented value... 16746bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman RHS = SE->getTruncateOrZeroExtend(BackedgeTakenCount, 16846bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman IndVar->getType()); 169c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman CmpIndVar = IndVar; 170d244057a48660c3cd30d219118ece3f947947790Chris Lattner } 17159fdaeeae8f183e18bb6ad5c382ca23e28e6aaf6Chris Lattner 172667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman // Expand the code for the iteration count. 17340a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman assert(RHS->isLoopInvariant(L) && 17440a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman "Computed iteration count is not loop invariant!"); 175667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman Value *ExitCnt = Rewriter.expandCodeFor(RHS, IndVar->getType(), BI); 17640bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner 177e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer // Insert a new icmp_ne or icmp_eq instruction before the branch. 178e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer ICmpInst::Predicate Opcode; 17940bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner if (L->contains(BI->getSuccessor(0))) 180e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer Opcode = ICmpInst::ICMP_NE; 18140bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner else 182e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer Opcode = ICmpInst::ICMP_EQ; 18340bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner 184f67ef318aa29e7cc0c7de76349881959936d9eeeDavid Greene DEBUG(dbgs() << "INDVARS: Rewriting loop exit condition to:\n" 185bdff548e4dd577a72094d57b282de4e765643b96Chris Lattner << " LHS:" << *CmpIndVar << '\n' 186bdff548e4dd577a72094d57b282de4e765643b96Chris Lattner << " op:\t" 187bdff548e4dd577a72094d57b282de4e765643b96Chris Lattner << (Opcode == ICmpInst::ICMP_NE ? "!=" : "==") << "\n" 188bdff548e4dd577a72094d57b282de4e765643b96Chris Lattner << " RHS:\t" << *RHS << "\n"); 189c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman 190333c40096561218bc3597cf153c0a3895274414cOwen Anderson ICmpInst *Cond = new ICmpInst(BI, Opcode, CmpIndVar, ExitCnt, "exitcond"); 19181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 1922444080ca4f1f63d647272650aae874360c604cdDan Gohman Value *OrigCond = BI->getCondition(); 19395bdbfa0668cc2b475429fbc6046f364bc01edf7Dan Gohman // It's tempting to use replaceAllUsesWith here to fully replace the old 19495bdbfa0668cc2b475429fbc6046f364bc01edf7Dan Gohman // comparison, but that's not immediately safe, since users of the old 19595bdbfa0668cc2b475429fbc6046f364bc01edf7Dan Gohman // comparison may not be dominated by the new comparison. Instead, just 19695bdbfa0668cc2b475429fbc6046f364bc01edf7Dan Gohman // update the branch to use the new comparison; in the common case this 19795bdbfa0668cc2b475429fbc6046f364bc01edf7Dan Gohman // will make old comparison dead. 19895bdbfa0668cc2b475429fbc6046f364bc01edf7Dan Gohman BI->setCondition(Cond); 19981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman RecursivelyDeleteTriviallyDeadInstructions(OrigCond); 20081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 20140bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner ++NumLFTR; 20240bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner Changed = true; 20381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman return Cond; 20440bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner} 2053324e718bc9ac2ede08a14c325848b576849542bChris Lattner 20640bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner/// RewriteLoopExitValues - Check to see if this loop has a computable 20740bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner/// loop-invariant execution count. If so, this means that we can compute the 20840bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner/// final value of any expressions that are recurrent in the loop, and 20940bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner/// substitute the exit values from the loop into any instructions outside of 21040bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner/// the loop that use the final values of the current expressions. 21181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman/// 21281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman/// This is mostly redundant with the regular IndVarSimplify activities that 21381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman/// happen later, except that it's more powerful in some cases, because it's 21481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman/// able to brute-force evaluate arbitrary instructions as long as they have 21581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman/// constant operands at the beginning of the loop. 216890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohmanvoid IndVarSimplify::RewriteLoopExitValues(Loop *L, 217667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman SCEVExpander &Rewriter) { 21881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Verify the input to the pass in already in LCSSA form. 219bbf81d88116d23fb0776412b5916f7d0b8b3ca7eDan Gohman assert(L->isLCSSAForm(*DT)); 22081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 221b7211a2ce13a0365e0e1dd2f27adda2ee3d1288bDevang Patel SmallVector<BasicBlock*, 8> ExitBlocks; 2229f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner L->getUniqueExitBlocks(ExitBlocks); 2239f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner 2249f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // Find all values that are computed inside the loop, but used outside of it. 2259f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // Because of LCSSA, these values will only occur in LCSSA PHI Nodes. Scan 2269f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // the exit blocks of the loop to find them. 2279f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) { 2289f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner BasicBlock *ExitBB = ExitBlocks[i]; 229cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 2309f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // If there are no PHI nodes in this exit block, then no values defined 2319f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // inside the loop are used on this path, skip it. 2329f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner PHINode *PN = dyn_cast<PHINode>(ExitBB->begin()); 2339f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner if (!PN) continue; 234cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 2359f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner unsigned NumPreds = PN->getNumIncomingValues(); 236cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 2379f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // Iterate over all of the PHI nodes. 2389f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner BasicBlock::iterator BBI = ExitBB->begin(); 2399f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner while ((PN = dyn_cast<PHINode>(BBI++))) { 2403790fb0c036acaa4db50aff83dd8b3bf51f8af6aTorok Edwin if (PN->use_empty()) 2413790fb0c036acaa4db50aff83dd8b3bf51f8af6aTorok Edwin continue; // dead use, don't replace it 242814f2b2d1927a5397c0e923588527277b9f67d6bDan Gohman 243814f2b2d1927a5397c0e923588527277b9f67d6bDan Gohman // SCEV only supports integer expressions for now. 244814f2b2d1927a5397c0e923588527277b9f67d6bDan Gohman if (!PN->getType()->isIntegerTy() && !PN->getType()->isPointerTy()) 245814f2b2d1927a5397c0e923588527277b9f67d6bDan Gohman continue; 246814f2b2d1927a5397c0e923588527277b9f67d6bDan Gohman 24745a2d7d44ae697e28df383d31455145fb754ac58Dale Johannesen // It's necessary to tell ScalarEvolution about this explicitly so that 24845a2d7d44ae697e28df383d31455145fb754ac58Dale Johannesen // it can walk the def-use list and forget all SCEVs, as it may not be 24945a2d7d44ae697e28df383d31455145fb754ac58Dale Johannesen // watching the PHI itself. Once the new exit value is in place, there 25045a2d7d44ae697e28df383d31455145fb754ac58Dale Johannesen // may not be a def-use connection between the loop and every instruction 25145a2d7d44ae697e28df383d31455145fb754ac58Dale Johannesen // which got a SCEVAddRecExpr for that loop. 25245a2d7d44ae697e28df383d31455145fb754ac58Dale Johannesen SE->forgetValue(PN); 25345a2d7d44ae697e28df383d31455145fb754ac58Dale Johannesen 2549f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // Iterate over all of the values in all the PHI nodes. 2559f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner for (unsigned i = 0; i != NumPreds; ++i) { 2569f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // If the value being merged in is not integer or is not defined 2579f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // in the loop, skip it. 2589f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner Value *InVal = PN->getIncomingValue(i); 259814f2b2d1927a5397c0e923588527277b9f67d6bDan Gohman if (!isa<Instruction>(InVal)) 2609f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner continue; 2619f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner 2629f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // If this pred is for a subloop, not L itself, skip it. 263cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman if (LI->getLoopFor(PN->getIncomingBlock(i)) != L) 2649f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner continue; // The Block is in a subloop, skip it. 2659f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner 2669f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // Check that InVal is defined in the loop. 2679f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner Instruction *Inst = cast<Instruction>(InVal); 26892329c7fbe572892c17aa2d2542a10e3ea16132fDan Gohman if (!L->contains(Inst)) 2699f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner continue; 270cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 2719f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // Okay, this instruction has a user outside of the current loop 2729f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // and varies predictably *inside* the loop. Evaluate the value it 2739f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // contains when the loop exits, if possible. 2740bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *ExitValue = SE->getSCEVAtScope(Inst, L->getParentLoop()); 275d594e6f0345b3e1e4b640a7099596ca613da16d6Dan Gohman if (!ExitValue->isLoopInvariant(L)) 2769f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner continue; 2779f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner 2789f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner Changed = true; 2799f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner ++NumReplaced; 280cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 281667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman Value *ExitVal = Rewriter.expandCodeFor(ExitValue, PN->getType(), Inst); 282cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 283f67ef318aa29e7cc0c7de76349881959936d9eeeDavid Greene DEBUG(dbgs() << "INDVARS: RLEV: AfterLoopVal = " << *ExitVal << '\n' 284bdff548e4dd577a72094d57b282de4e765643b96Chris Lattner << " LoopVal = " << *Inst << "\n"); 2859caed5440d59dac4b388152fe8b993dc0491e5e9Chris Lattner 2869f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner PN->setIncomingValue(i, ExitVal); 287cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 28881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // If this instruction is dead now, delete it. 28981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman RecursivelyDeleteTriviallyDeadInstructions(Inst); 290cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 29165d1e2b6e74fcd370093cbe518ebc15cbc445ad4Dan Gohman if (NumPreds == 1) { 29265d1e2b6e74fcd370093cbe518ebc15cbc445ad4Dan Gohman // Completely replace a single-pred PHI. This is safe, because the 29365d1e2b6e74fcd370093cbe518ebc15cbc445ad4Dan Gohman // NewVal won't be variant in the loop, so we don't need an LCSSA phi 29465d1e2b6e74fcd370093cbe518ebc15cbc445ad4Dan Gohman // node anymore. 2959f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner PN->replaceAllUsesWith(ExitVal); 29681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman RecursivelyDeleteTriviallyDeadInstructions(PN); 297c9838f25d53d3dd7d38949ef6c28f2505a110f45Chris Lattner } 2984bd09d70cceb3851f7eb1c2f98338b3071d405f3Chris Lattner } 29965d1e2b6e74fcd370093cbe518ebc15cbc445ad4Dan Gohman if (NumPreds != 1) { 300667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman // Clone the PHI and delete the original one. This lets IVUsers and 301667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman // any other maps purge the original user from their records. 30250b6e33584f4e4cf75c7795b1f1a90731861c825Devang Patel PHINode *NewPN = cast<PHINode>(PN->clone()); 303667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman NewPN->takeName(PN); 304667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman NewPN->insertBefore(PN); 305667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman PN->replaceAllUsesWith(NewPN); 306667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman PN->eraseFromParent(); 307667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman } 308c9838f25d53d3dd7d38949ef6c28f2505a110f45Chris Lattner } 309c9838f25d53d3dd7d38949ef6c28f2505a110f45Chris Lattner } 310472fdf7090bb00af3a3f9dcbe22263120a527533Dan Gohman 311472fdf7090bb00af3a3f9dcbe22263120a527533Dan Gohman // The insertion point instruction may have been deleted; clear it out 312472fdf7090bb00af3a3f9dcbe22263120a527533Dan Gohman // so that the rewriter doesn't trip over it later. 313472fdf7090bb00af3a3f9dcbe22263120a527533Dan Gohman Rewriter.clearInsertPoint(); 31440bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner} 31515cad759fe2048ac5eb137c6bb0ab7287538677eChris Lattner 31660f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohmanvoid IndVarSimplify::RewriteNonIntegerIVs(Loop *L) { 3172d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman // First step. Check to see if there are any floating-point recurrences. 31840bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // If there are, change them into integer recurrences, permitting analysis by 31940bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // the SCEV routines. 32015cad759fe2048ac5eb137c6bb0ab7287538677eChris Lattner // 32140bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner BasicBlock *Header = L->getHeader(); 322fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 32381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman SmallVector<WeakVH, 8> PHIs; 32481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman for (BasicBlock::iterator I = Header->begin(); 32581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman PHINode *PN = dyn_cast<PHINode>(I); ++I) 32681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman PHIs.push_back(PN); 32781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 32881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman for (unsigned i = 0, e = PHIs.size(); i != e; ++i) 32981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (PHINode *PN = dyn_cast_or_null<PHINode>(PHIs[i])) 33081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman HandleFloatingPointIV(L, PN); 33115cad759fe2048ac5eb137c6bb0ab7287538677eChris Lattner 3322d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman // If the loop previously had floating-point IV, ScalarEvolution 33360f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman // may not have been able to compute a trip count. Now that we've done some 33460f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman // re-writing, the trip count may be computable. 33560f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman if (Changed) 3364c7279ac726e338400626fca5a09b5533426eb6aDan Gohman SE->forgetLoop(L); 337c671d892ab1d3d8fed18a61f66f3f3a86e73ebd9Dale Johannesen} 338c671d892ab1d3d8fed18a61f66f3f3a86e73ebd9Dale Johannesen 339c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohmanbool IndVarSimplify::runOnLoop(Loop *L, LPPassManager &LPM) { 34081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman IU = &getAnalysis<IVUsers>(); 3415ee99979065d75605d150d7e567e4351024aae8fDevang Patel LI = &getAnalysis<LoopInfo>(); 3425ee99979065d75605d150d7e567e4351024aae8fDevang Patel SE = &getAnalysis<ScalarEvolution>(); 343de53dc03f5c1549f3176e979bbeeac965dfa5cbcDan Gohman DT = &getAnalysis<DominatorTree>(); 3445ee99979065d75605d150d7e567e4351024aae8fDevang Patel Changed = false; 34560f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman 3462d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman // If there are any floating-point recurrences, attempt to 34760f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman // transform them to use integer recurrences. 34860f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman RewriteNonIntegerIVs(L); 34960f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman 35081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman BasicBlock *ExitingBlock = L->getExitingBlock(); // may be null 3510bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *BackedgeTakenCount = SE->getBackedgeTakenCount(L); 3529caed5440d59dac4b388152fe8b993dc0491e5e9Chris Lattner 353667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman // Create a rewriter object which we'll use to transform the code with. 354667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman SCEVExpander Rewriter(*SE); 355667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman 35640bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // Check to see if this loop has a computable loop-invariant execution count. 35740bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // If so, this means that we can compute the final value of any expressions 35840bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // that are recurrent in the loop, and substitute the exit values from the 35940bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // loop into any instructions outside of the loop that use the final values of 36040bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // the current expressions. 361394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner // 36246bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman if (!isa<SCEVCouldNotCompute>(BackedgeTakenCount)) 363454d26dc43207ec537d843229db6f5e6a302e23dDan Gohman RewriteLoopExitValues(L, Rewriter); 36440bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner 36581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Compute the type of the largest recurrence expression, and decide whether 36681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // a canonical induction variable should be inserted. 367c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman const Type *LargestType = 0; 36881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman bool NeedCannIV = false; 36946bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman if (!isa<SCEVCouldNotCompute>(BackedgeTakenCount)) { 37046bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman LargestType = BackedgeTakenCount->getType(); 371af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman LargestType = SE->getEffectiveSCEVType(LargestType); 37281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // If we have a known trip count and a single exit block, we'll be 37381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // rewriting the loop exit test condition below, which requires a 37481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // canonical induction variable. 37581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (ExitingBlock) 37681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman NeedCannIV = true; 377f50af088f19f525f3d1026eb61db77e0037a9f43Chris Lattner } 378572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman for (IVUsers::const_iterator I = IU->begin(), E = IU->end(); I != E; ++I) { 379572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman const Type *Ty = 380572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman SE->getEffectiveSCEVType(I->getOperandValToReplace()->getType()); 381c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman if (!LargestType || 38281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman SE->getTypeSizeInBits(Ty) > 383af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman SE->getTypeSizeInBits(LargestType)) 38481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman LargestType = Ty; 385572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman NeedCannIV = true; 386500597a1c39e91a3020587318ed61e737b6c613aChris Lattner } 387394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner 388f451cb870efcf9e0302d25ed05f4cac6bb494e42Dan Gohman // Now that we know the largest of the induction variable expressions 38981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // in this loop, insert a canonical induction variable of the largest size. 390c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman Value *IndVar = 0; 39181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (NeedCannIV) { 39285669637139089eaed8def1583ac04266c9654e2Dan Gohman // Check to see if the loop already has any canonical-looking induction 39385669637139089eaed8def1583ac04266c9654e2Dan Gohman // variables. If any are present and wider than the planned canonical 39485669637139089eaed8def1583ac04266c9654e2Dan Gohman // induction variable, temporarily remove them, so that the Rewriter 39585669637139089eaed8def1583ac04266c9654e2Dan Gohman // doesn't attempt to reuse them. 39685669637139089eaed8def1583ac04266c9654e2Dan Gohman SmallVector<PHINode *, 2> OldCannIVs; 39785669637139089eaed8def1583ac04266c9654e2Dan Gohman while (PHINode *OldCannIV = L->getCanonicalInductionVariable()) { 3984d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman if (SE->getTypeSizeInBits(OldCannIV->getType()) > 3994d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman SE->getTypeSizeInBits(LargestType)) 4004d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman OldCannIV->removeFromParent(); 4014d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman else 40285669637139089eaed8def1583ac04266c9654e2Dan Gohman break; 40385669637139089eaed8def1583ac04266c9654e2Dan Gohman OldCannIVs.push_back(OldCannIV); 4044d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman } 4054d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman 406667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman IndVar = Rewriter.getOrInsertCanonicalInductionVariable(L, LargestType); 4074d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman 408c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman ++NumInserted; 409c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman Changed = true; 410f67ef318aa29e7cc0c7de76349881959936d9eeeDavid Greene DEBUG(dbgs() << "INDVARS: New CanIV: " << *IndVar << '\n'); 4114d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman 4124d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman // Now that the official induction variable is established, reinsert 41385669637139089eaed8def1583ac04266c9654e2Dan Gohman // any old canonical-looking variables after it so that the IR remains 41485669637139089eaed8def1583ac04266c9654e2Dan Gohman // consistent. They will be deleted as part of the dead-PHI deletion at 4154d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman // the end of the pass. 41685669637139089eaed8def1583ac04266c9654e2Dan Gohman while (!OldCannIVs.empty()) { 41785669637139089eaed8def1583ac04266c9654e2Dan Gohman PHINode *OldCannIV = OldCannIVs.pop_back_val(); 41885669637139089eaed8def1583ac04266c9654e2Dan Gohman OldCannIV->insertBefore(L->getHeader()->getFirstNonPHI()); 41985669637139089eaed8def1583ac04266c9654e2Dan Gohman } 420d19534add90a2a894af61523b830887097bb780bDan Gohman } 42140bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner 422c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman // If we have a trip count expression, rewrite the loop's exit condition 423c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman // using it. We can currently only handle loops with a single exit. 42481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman ICmpInst *NewICmp = 0; 42585669637139089eaed8def1583ac04266c9654e2Dan Gohman if (!isa<SCEVCouldNotCompute>(BackedgeTakenCount) && 42685669637139089eaed8def1583ac04266c9654e2Dan Gohman !BackedgeTakenCount->isZero() && 42785669637139089eaed8def1583ac04266c9654e2Dan Gohman ExitingBlock) { 42881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman assert(NeedCannIV && 42981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman "LinearFunctionTestReplace requires a canonical induction variable"); 430c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman // Can't rewrite non-branch yet. 43181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (BranchInst *BI = dyn_cast<BranchInst>(ExitingBlock->getTerminator())) 43281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman NewICmp = LinearFunctionTestReplace(L, BackedgeTakenCount, IndVar, 43381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman ExitingBlock, BI, Rewriter); 43481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman } 435c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman 4363d431384f05c9defc84f36eafe220415cc12ee93Torok Edwin // Rewrite IV-derived expressions. Clears the rewriter cache. 437454d26dc43207ec537d843229db6f5e6a302e23dDan Gohman RewriteIVExpressions(L, Rewriter); 438fcb81f5f4cbac61851b7dec403961cf88e614aa1Chris Lattner 439667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman // The Rewriter may not be used from this point on. 4403d431384f05c9defc84f36eafe220415cc12ee93Torok Edwin 44181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Loop-invariant instructions in the preheader that aren't used in the 44281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // loop may be sunk below the loop to reduce register pressure. 443667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman SinkUnusedInvariants(L); 44481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 44581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // For completeness, inform IVUsers of the IV use in the newly-created 44681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // loop exit test instruction. 44781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (NewICmp) 44881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman IU->AddUsersIfInteresting(cast<Instruction>(NewICmp->getOperand(0))); 44981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 45081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Clean up dead instructions. 4519fff2187a21f765ed87a25c48552a6942450f3e2Dan Gohman Changed |= DeleteDeadPHIs(L->getHeader()); 45281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Check a post-condition. 453bbf81d88116d23fb0776412b5916f7d0b8b3ca7eDan Gohman assert(L->isLCSSAForm(*DT) && "Indvars did not leave the loop in lcssa form!"); 45481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman return Changed; 45581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman} 45681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 457454d26dc43207ec537d843229db6f5e6a302e23dDan Gohmanvoid IndVarSimplify::RewriteIVExpressions(Loop *L, SCEVExpander &Rewriter) { 45881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman SmallVector<WeakVH, 16> DeadInsts; 45981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 46081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Rewrite all induction variable expressions in terms of the canonical 46181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // induction variable. 46281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // 46381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // If there were induction variables of other sizes or offsets, manually 46481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // add the offsets to the primary induction variable and cast, avoiding 46581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // the need for the code evaluation methods to insert induction variables 46681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // of different sizes. 467572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman for (IVUsers::iterator UI = IU->begin(), E = IU->end(); UI != E; ++UI) { 468572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman const SCEV *Stride = UI->getStride(); 469572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman Value *Op = UI->getOperandValToReplace(); 470572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman const Type *UseTy = Op->getType(); 471572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman Instruction *User = UI->getUser(); 472572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman 473572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // Compute the final addrec to expand into code. 474572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman const SCEV *AR = IU->getReplacementExpr(*UI); 475572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman 476572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // Evaluate the expression out of the loop, if possible. 477572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman if (!L->contains(UI->getUser())) { 478572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman const SCEV *ExitVal = SE->getSCEVAtScope(AR, L->getParentLoop()); 479572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman if (ExitVal->isLoopInvariant(L)) 480572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman AR = ExitVal; 48181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman } 482572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman 483572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // FIXME: It is an extremely bad idea to indvar substitute anything more 484572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // complex than affine induction variables. Doing so will put expensive 485572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // polynomial evaluations inside of the loop, and the str reduction pass 486572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // currently can only reduce affine polynomials. For now just disable 487572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // indvar subst on anything more complex than an affine addrec, unless 488572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // it can be expanded to a trivial value. 489572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman if (!AR->isLoopInvariant(L) && !Stride->isLoopInvariant(L)) 490572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman continue; 491572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman 492572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // Determine the insertion point for this user. By default, insert 493572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // immediately before the user. The SCEVExpander class will automatically 494572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // hoist loop invariants out of the loop. For PHI nodes, there may be 495572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // multiple uses, so compute the nearest common dominator for the 496572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // incoming blocks. 497572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman Instruction *InsertPt = User; 498572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman if (PHINode *PHI = dyn_cast<PHINode>(InsertPt)) 499572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i) 500572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman if (PHI->getIncomingValue(i) == Op) { 501572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman if (InsertPt == User) 502572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman InsertPt = PHI->getIncomingBlock(i)->getTerminator(); 503572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman else 504572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman InsertPt = 505572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman DT->findNearestCommonDominator(InsertPt->getParent(), 506572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman PHI->getIncomingBlock(i)) 507572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman ->getTerminator(); 508572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman } 509572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman 510572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // Now expand it into actual Instructions and patch it into place. 511572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman Value *NewVal = Rewriter.expandCodeFor(AR, UseTy, InsertPt); 512572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman 513d7bfd0028b273f2e3935e8c7ff95db6fa2b21789Dan Gohman // Inform ScalarEvolution that this value is changing. The change doesn't 514d7bfd0028b273f2e3935e8c7ff95db6fa2b21789Dan Gohman // affect its value, but it does potentially affect which use lists the 515d7bfd0028b273f2e3935e8c7ff95db6fa2b21789Dan Gohman // value will be on after the replacement, which affects ScalarEvolution's 516d7bfd0028b273f2e3935e8c7ff95db6fa2b21789Dan Gohman // ability to walk use lists and drop dangling pointers when a value is 517d7bfd0028b273f2e3935e8c7ff95db6fa2b21789Dan Gohman // deleted. 518d7bfd0028b273f2e3935e8c7ff95db6fa2b21789Dan Gohman SE->forgetValue(User); 519d7bfd0028b273f2e3935e8c7ff95db6fa2b21789Dan Gohman 520572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // Patch the new value into place. 521572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman if (Op->hasName()) 522572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman NewVal->takeName(Op); 523572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman User->replaceUsesOfWith(Op, NewVal); 524572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman UI->setOperandValToReplace(NewVal); 525572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman DEBUG(dbgs() << "INDVARS: Rewrote IV '" << *AR << "' " << *Op << '\n' 526572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman << " into = " << *NewVal << "\n"); 527572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman ++NumRemoved; 528572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman Changed = true; 529572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman 530572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // The old value may be dead now. 531572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman DeadInsts.push_back(Op); 532500597a1c39e91a3020587318ed61e737b6c613aChris Lattner } 533ba4f3f6a419326df190599421fa149c90235cb72Chris Lattner 5343d431384f05c9defc84f36eafe220415cc12ee93Torok Edwin // Clear the rewriter cache, because values that are in the rewriter's cache 5353d431384f05c9defc84f36eafe220415cc12ee93Torok Edwin // can be deleted in the loop below, causing the AssertingVH in the cache to 5363d431384f05c9defc84f36eafe220415cc12ee93Torok Edwin // trigger. 5373d431384f05c9defc84f36eafe220415cc12ee93Torok Edwin Rewriter.clear(); 53881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Now that we're done iterating through lists, clean up any instructions 53981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // which are now dead. 540a10756ee657a4d43a48cca5c166919093930ed6bDan Gohman while (!DeadInsts.empty()) 541a10756ee657a4d43a48cca5c166919093930ed6bDan Gohman if (Instruction *Inst = 542a10756ee657a4d43a48cca5c166919093930ed6bDan Gohman dyn_cast_or_null<Instruction>(DeadInsts.pop_back_val())) 54381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman RecursivelyDeleteTriviallyDeadInstructions(Inst); 54481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman} 54581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 54681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman/// If there's a single exit block, sink any loop-invariant values that 54781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman/// were defined in the preheader but not used inside the loop into the 54881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman/// exit block to reduce register pressure in the loop. 549667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohmanvoid IndVarSimplify::SinkUnusedInvariants(Loop *L) { 55081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman BasicBlock *ExitBlock = L->getExitBlock(); 55181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (!ExitBlock) return; 55281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 55381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman BasicBlock *Preheader = L->getLoopPreheader(); 55403e896bd6073efc4523d8bcd0239d6ed62126db7Dan Gohman if (!Preheader) return; 55503e896bd6073efc4523d8bcd0239d6ed62126db7Dan Gohman 55603e896bd6073efc4523d8bcd0239d6ed62126db7Dan Gohman Instruction *InsertPt = ExitBlock->getFirstNonPHI(); 55781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman BasicBlock::iterator I = Preheader->getTerminator(); 55881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman while (I != Preheader->begin()) { 55981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman --I; 560667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman // New instructions were inserted at the end of the preheader. 561667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman if (isa<PHINode>(I)) 56281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman break; 56387a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling 5640c77db32dd8ae10b5a26d60718dbe03dc2745888Eli Friedman // Don't move instructions which might have side effects, since the side 56587a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling // effects need to complete before instructions inside the loop. Also don't 56687a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling // move instructions which might read memory, since the loop may modify 56787a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling // memory. Note that it's okay if the instruction might have undefined 56887a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling // behavior: LoopSimplify guarantees that the preheader dominates the exit 56987a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling // block. 5700c77db32dd8ae10b5a26d60718dbe03dc2745888Eli Friedman if (I->mayHaveSideEffects() || I->mayReadFromMemory()) 571667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman continue; 57287a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling 5737b9f6b1b21bc0b06f3c72beae51e9db631319503Devang Patel // Skip debug info intrinsics. 5747b9f6b1b21bc0b06f3c72beae51e9db631319503Devang Patel if (isa<DbgInfoIntrinsic>(I)) 5757b9f6b1b21bc0b06f3c72beae51e9db631319503Devang Patel continue; 57687a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling 57776f497a351c562f366b5e93c27d3f1652fb48ff4Dan Gohman // Don't sink static AllocaInsts out of the entry block, which would 57876f497a351c562f366b5e93c27d3f1652fb48ff4Dan Gohman // turn them into dynamic allocas! 57976f497a351c562f366b5e93c27d3f1652fb48ff4Dan Gohman if (AllocaInst *AI = dyn_cast<AllocaInst>(I)) 58076f497a351c562f366b5e93c27d3f1652fb48ff4Dan Gohman if (AI->isStaticAlloca()) 58176f497a351c562f366b5e93c27d3f1652fb48ff4Dan Gohman continue; 58287a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling 58381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Determine if there is a use in or before the loop (direct or 58481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // otherwise). 58581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman bool UsedInLoop = false; 58681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman for (Value::use_iterator UI = I->use_begin(), UE = I->use_end(); 58781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman UI != UE; ++UI) { 58881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman BasicBlock *UseBB = cast<Instruction>(UI)->getParent(); 58981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (PHINode *P = dyn_cast<PHINode>(UI)) { 59081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman unsigned i = 59181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman PHINode::getIncomingValueNumForOperand(UI.getOperandNo()); 59281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman UseBB = P->getIncomingBlock(i); 59381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman } 59481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (UseBB == Preheader || L->contains(UseBB)) { 59581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman UsedInLoop = true; 59681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman break; 59781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman } 59881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman } 59987a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling 60081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // If there is, the def must remain in the preheader. 60181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (UsedInLoop) 60281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman continue; 60387a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling 60481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Otherwise, sink it to the exit block. 60581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman Instruction *ToMove = I; 60681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman bool Done = false; 60787a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling 60887a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling if (I != Preheader->begin()) { 60987a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling // Skip debug info intrinsics. 61087a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling do { 61187a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling --I; 61287a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling } while (isa<DbgInfoIntrinsic>(I) && I != Preheader->begin()); 61387a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling 61487a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling if (isa<DbgInfoIntrinsic>(I) && I == Preheader->begin()) 61587a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling Done = true; 61687a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling } else { 61781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman Done = true; 61887a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling } 61987a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling 620667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman ToMove->moveBefore(InsertPt); 62187a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling if (Done) break; 622667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman InsertPt = ToMove; 62381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman } 62481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman} 62581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 6263f46a3abeedba8d517b4182de34c821d752db058Dan Gohman/// Return true if it is OK to use SIToFPInst for an induction variable 6273f46a3abeedba8d517b4182de34c821d752db058Dan Gohman/// with given initial and exit values. 628ca703bd56ba1f717b3735c6889334c319ca005b1Chris Lattnerstatic bool CanUseSIToFP(ConstantFP *InitV, ConstantFP *ExitV, 629ca703bd56ba1f717b3735c6889334c319ca005b1Chris Lattner uint64_t intIV, uint64_t intEV) { 63013877bf6c20621541ff71583c626bda68ef09219Devang Patel 63107aa76ad939e053c1992a03cbcb16aff74f26651Chris Lattner if (InitV->getValueAPF().isNegative() || ExitV->getValueAPF().isNegative()) 63213877bf6c20621541ff71583c626bda68ef09219Devang Patel return true; 63313877bf6c20621541ff71583c626bda68ef09219Devang Patel 63413877bf6c20621541ff71583c626bda68ef09219Devang Patel // If the iteration range can be handled by SIToFPInst then use it. 63513877bf6c20621541ff71583c626bda68ef09219Devang Patel APInt Max = APInt::getSignedMaxValue(32); 636bae7d6dbeb842b5ed051c50a87bc282f2dec6e1fDale Johannesen if (Max.getZExtValue() > static_cast<uint64_t>(abs64(intEV - intIV))) 63713877bf6c20621541ff71583c626bda68ef09219Devang Patel return true; 638cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 63913877bf6c20621541ff71583c626bda68ef09219Devang Patel return false; 64013877bf6c20621541ff71583c626bda68ef09219Devang Patel} 64113877bf6c20621541ff71583c626bda68ef09219Devang Patel 64213877bf6c20621541ff71583c626bda68ef09219Devang Patel/// convertToInt - Convert APF to an integer, if possible. 64307aa76ad939e053c1992a03cbcb16aff74f26651Chris Lattnerstatic bool convertToInt(const APFloat &APF, uint64_t &intVal) { 644cd40233429fce385ae4b22301ce705273a6951a1Devang Patel bool isExact = false; 645794a7dbce030f93315b1305f83a374232f09bba5Evan Cheng if (&APF.getSemantics() == &APFloat::PPCDoubleDouble) 646794a7dbce030f93315b1305f83a374232f09bba5Evan Cheng return false; 64707aa76ad939e053c1992a03cbcb16aff74f26651Chris Lattner if (APF.convertToInteger(&intVal, 32, APF.isNegative(), 64807aa76ad939e053c1992a03cbcb16aff74f26651Chris Lattner APFloat::rmTowardZero, &isExact) != APFloat::opOK) 649cd40233429fce385ae4b22301ce705273a6951a1Devang Patel return false; 650cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman if (!isExact) 651cd40233429fce385ae4b22301ce705273a6951a1Devang Patel return false; 652cd40233429fce385ae4b22301ce705273a6951a1Devang Patel return true; 653cd40233429fce385ae4b22301ce705273a6951a1Devang Patel} 654cd40233429fce385ae4b22301ce705273a6951a1Devang Patel 65558d43d4a41b21085c063bdd21a2abb68056e2a6fDevang Patel/// HandleFloatingPointIV - If the loop has floating induction variable 65658d43d4a41b21085c063bdd21a2abb68056e2a6fDevang Patel/// then insert corresponding integer induction variable if possible. 65784e3515974407a606289c6e762a0419723b7918fDevang Patel/// For example, 65884e3515974407a606289c6e762a0419723b7918fDevang Patel/// for(double i = 0; i < 10000; ++i) 65984e3515974407a606289c6e762a0419723b7918fDevang Patel/// bar(i) 66084e3515974407a606289c6e762a0419723b7918fDevang Patel/// is converted into 66184e3515974407a606289c6e762a0419723b7918fDevang Patel/// for(int i = 0; i < 10000; ++i) 66284e3515974407a606289c6e762a0419723b7918fDevang Patel/// bar((double)i); 66384e3515974407a606289c6e762a0419723b7918fDevang Patel/// 66481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohmanvoid IndVarSimplify::HandleFloatingPointIV(Loop *L, PHINode *PH) { 66584e3515974407a606289c6e762a0419723b7918fDevang Patel unsigned IncomingEdge = L->contains(PH->getIncomingBlock(0)); 66684e3515974407a606289c6e762a0419723b7918fDevang Patel unsigned BackEdge = IncomingEdge^1; 667cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 66884e3515974407a606289c6e762a0419723b7918fDevang Patel // Check incoming value. 669c4f7e8061de19172d4c3f70a80447505b792e450Chris Lattner ConstantFP *InitValueVal = 67007aa76ad939e053c1992a03cbcb16aff74f26651Chris Lattner dyn_cast<ConstantFP>(PH->getIncomingValue(IncomingEdge)); 671c4f7e8061de19172d4c3f70a80447505b792e450Chris Lattner if (!InitValueVal) return; 67207aa76ad939e053c1992a03cbcb16aff74f26651Chris Lattner 673c4f7e8061de19172d4c3f70a80447505b792e450Chris Lattner uint64_t InitValue; 674c4f7e8061de19172d4c3f70a80447505b792e450Chris Lattner if (!convertToInt(InitValueVal->getValueAPF(), InitValue)) 675cd40233429fce385ae4b22301ce705273a6951a1Devang Patel return; 676cd40233429fce385ae4b22301ce705273a6951a1Devang Patel 6773f46a3abeedba8d517b4182de34c821d752db058Dan Gohman // Check IV increment. Reject this PH if increment operation is not 678cd40233429fce385ae4b22301ce705273a6951a1Devang Patel // an add or increment value can not be represented by an integer. 679cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman BinaryOperator *Incr = 68084e3515974407a606289c6e762a0419723b7918fDevang Patel dyn_cast<BinaryOperator>(PH->getIncomingValue(BackEdge)); 68107aa76ad939e053c1992a03cbcb16aff74f26651Chris Lattner if (Incr == 0 || Incr->getOpcode() != Instruction::FAdd) return; 68207aa76ad939e053c1992a03cbcb16aff74f26651Chris Lattner 68307aa76ad939e053c1992a03cbcb16aff74f26651Chris Lattner // If this is not an add of the PHI with a constantfp, or if the constant fp 68407aa76ad939e053c1992a03cbcb16aff74f26651Chris Lattner // is not an integer, bail out. 685c4f7e8061de19172d4c3f70a80447505b792e450Chris Lattner ConstantFP *IncValueVal = dyn_cast<ConstantFP>(Incr->getOperand(1)); 686c4f7e8061de19172d4c3f70a80447505b792e450Chris Lattner uint64_t IntValue; 687c4f7e8061de19172d4c3f70a80447505b792e450Chris Lattner if (IncValueVal == 0 || Incr->getOperand(0) != PH || 688c4f7e8061de19172d4c3f70a80447505b792e450Chris Lattner !convertToInt(IncValueVal->getValueAPF(), IntValue)) 689cd40233429fce385ae4b22301ce705273a6951a1Devang Patel return; 690cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 69107aa76ad939e053c1992a03cbcb16aff74f26651Chris Lattner // Check Incr uses. One user is PH and the other user is an exit condition 69207aa76ad939e053c1992a03cbcb16aff74f26651Chris Lattner // used by the conditional terminator. 69384e3515974407a606289c6e762a0419723b7918fDevang Patel Value::use_iterator IncrUse = Incr->use_begin(); 69484e3515974407a606289c6e762a0419723b7918fDevang Patel Instruction *U1 = cast<Instruction>(IncrUse++); 69584e3515974407a606289c6e762a0419723b7918fDevang Patel if (IncrUse == Incr->use_end()) return; 69684e3515974407a606289c6e762a0419723b7918fDevang Patel Instruction *U2 = cast<Instruction>(IncrUse++); 69784e3515974407a606289c6e762a0419723b7918fDevang Patel if (IncrUse != Incr->use_end()) return; 698cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 69907aa76ad939e053c1992a03cbcb16aff74f26651Chris Lattner // Find exit condition, which is an fcmp. If it doesn't exist, or if it isn't 70007aa76ad939e053c1992a03cbcb16aff74f26651Chris Lattner // only used by a branch, we can't transform it. 701ca703bd56ba1f717b3735c6889334c319ca005b1Chris Lattner FCmpInst *Compare = dyn_cast<FCmpInst>(U1); 702ca703bd56ba1f717b3735c6889334c319ca005b1Chris Lattner if (!Compare) 703ca703bd56ba1f717b3735c6889334c319ca005b1Chris Lattner Compare = dyn_cast<FCmpInst>(U2); 704ca703bd56ba1f717b3735c6889334c319ca005b1Chris Lattner if (Compare == 0 || !Compare->hasOneUse() || 705ca703bd56ba1f717b3735c6889334c319ca005b1Chris Lattner !isa<BranchInst>(Compare->use_back())) 70607aa76ad939e053c1992a03cbcb16aff74f26651Chris Lattner return; 707c4f7e8061de19172d4c3f70a80447505b792e450Chris Lattner 708ca703bd56ba1f717b3735c6889334c319ca005b1Chris Lattner BranchInst *TheBr = cast<BranchInst>(Compare->use_back()); 70984e3515974407a606289c6e762a0419723b7918fDevang Patel 71007aa76ad939e053c1992a03cbcb16aff74f26651Chris Lattner // If it isn't a comparison with an integer-as-fp (the exit value), we can't 71107aa76ad939e053c1992a03cbcb16aff74f26651Chris Lattner // transform it. 712ca703bd56ba1f717b3735c6889334c319ca005b1Chris Lattner ConstantFP *ExitValueVal = dyn_cast<ConstantFP>(Compare->getOperand(1)); 71307aa76ad939e053c1992a03cbcb16aff74f26651Chris Lattner uint64_t ExitValue; 71407aa76ad939e053c1992a03cbcb16aff74f26651Chris Lattner if (ExitValueVal == 0 || !convertToInt(ExitValueVal->getValueAPF(),ExitValue)) 71584e3515974407a606289c6e762a0419723b7918fDevang Patel return; 716cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 71784e3515974407a606289c6e762a0419723b7918fDevang Patel // Find new predicate for integer comparison. 71884e3515974407a606289c6e762a0419723b7918fDevang Patel CmpInst::Predicate NewPred = CmpInst::BAD_ICMP_PREDICATE; 719ca703bd56ba1f717b3735c6889334c319ca005b1Chris Lattner switch (Compare->getPredicate()) { 720c4f7e8061de19172d4c3f70a80447505b792e450Chris Lattner default: return; // Unknown comparison. 72184e3515974407a606289c6e762a0419723b7918fDevang Patel case CmpInst::FCMP_OEQ: 722c4f7e8061de19172d4c3f70a80447505b792e450Chris Lattner case CmpInst::FCMP_UEQ: NewPred = CmpInst::ICMP_EQ; break; 72384e3515974407a606289c6e762a0419723b7918fDevang Patel case CmpInst::FCMP_OGT: 724c4f7e8061de19172d4c3f70a80447505b792e450Chris Lattner case CmpInst::FCMP_UGT: NewPred = CmpInst::ICMP_UGT; break; 72584e3515974407a606289c6e762a0419723b7918fDevang Patel case CmpInst::FCMP_OGE: 726c4f7e8061de19172d4c3f70a80447505b792e450Chris Lattner case CmpInst::FCMP_UGE: NewPred = CmpInst::ICMP_UGE; break; 72784e3515974407a606289c6e762a0419723b7918fDevang Patel case CmpInst::FCMP_OLT: 728c4f7e8061de19172d4c3f70a80447505b792e450Chris Lattner case CmpInst::FCMP_ULT: NewPred = CmpInst::ICMP_ULT; break; 72984e3515974407a606289c6e762a0419723b7918fDevang Patel case CmpInst::FCMP_OLE: 730c4f7e8061de19172d4c3f70a80447505b792e450Chris Lattner case CmpInst::FCMP_ULE: NewPred = CmpInst::ICMP_ULE; break; 73158d43d4a41b21085c063bdd21a2abb68056e2a6fDevang Patel } 732cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 733c4f7e8061de19172d4c3f70a80447505b792e450Chris Lattner const IntegerType *Int32Ty = Type::getInt32Ty(PH->getContext()); 734c4f7e8061de19172d4c3f70a80447505b792e450Chris Lattner 735ca703bd56ba1f717b3735c6889334c319ca005b1Chris Lattner // Insert new i32 integer induction variable. 736c4f7e8061de19172d4c3f70a80447505b792e450Chris Lattner PHINode *NewPHI = PHINode::Create(Int32Ty, PH->getName()+".int", PH); 737c4f7e8061de19172d4c3f70a80447505b792e450Chris Lattner NewPHI->addIncoming(ConstantInt::get(Int32Ty, InitValue), 73884e3515974407a606289c6e762a0419723b7918fDevang Patel PH->getIncomingBlock(IncomingEdge)); 73984e3515974407a606289c6e762a0419723b7918fDevang Patel 740c4f7e8061de19172d4c3f70a80447505b792e450Chris Lattner Value *NewAdd = 741c4f7e8061de19172d4c3f70a80447505b792e450Chris Lattner BinaryOperator::CreateAdd(NewPHI, ConstantInt::get(Int32Ty, IntValue), 742c4f7e8061de19172d4c3f70a80447505b792e450Chris Lattner Incr->getName()+".int", Incr); 74384e3515974407a606289c6e762a0419723b7918fDevang Patel NewPHI->addIncoming(NewAdd, PH->getIncomingBlock(BackEdge)); 74484e3515974407a606289c6e762a0419723b7918fDevang Patel 745ca703bd56ba1f717b3735c6889334c319ca005b1Chris Lattner ICmpInst *NewCompare = new ICmpInst(TheBr, NewPred, NewAdd, 746ca703bd56ba1f717b3735c6889334c319ca005b1Chris Lattner ConstantInt::get(Int32Ty, ExitValue), 747ca703bd56ba1f717b3735c6889334c319ca005b1Chris Lattner Compare->getName()); 748cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 7493f46a3abeedba8d517b4182de34c821d752db058Dan Gohman // In the following deletions, PH may become dead and may be deleted. 75081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Use a WeakVH to observe whether this happens. 75181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman WeakVH WeakPH = PH; 75281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 753ca703bd56ba1f717b3735c6889334c319ca005b1Chris Lattner // Delete the old floating point exit comparison. The branch starts using the 754ca703bd56ba1f717b3735c6889334c319ca005b1Chris Lattner // new comparison. 755ca703bd56ba1f717b3735c6889334c319ca005b1Chris Lattner NewCompare->takeName(Compare); 756ca703bd56ba1f717b3735c6889334c319ca005b1Chris Lattner Compare->replaceAllUsesWith(NewCompare); 757ca703bd56ba1f717b3735c6889334c319ca005b1Chris Lattner RecursivelyDeleteTriviallyDeadInstructions(Compare); 758cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 759ca703bd56ba1f717b3735c6889334c319ca005b1Chris Lattner // Delete the old floating point increment. 7609e9a0d5fc26878e51a58a8b57900fcbf952c2691Owen Anderson Incr->replaceAllUsesWith(UndefValue::get(Incr->getType())); 76181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman RecursivelyDeleteTriviallyDeadInstructions(Incr); 76281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 76381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Replace floating induction variable, if it isn't already deleted. 76481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Give SIToFPInst preference over UIToFPInst because it is faster on 76581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // platforms that are widely used. 76681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (WeakPH && !PH->use_empty()) { 767ca703bd56ba1f717b3735c6889334c319ca005b1Chris Lattner if (CanUseSIToFP(InitValueVal, ExitValueVal, InitValue, ExitValue)) { 76881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman SIToFPInst *Conv = new SIToFPInst(NewPHI, PH->getType(), "indvar.conv", 76981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman PH->getParent()->getFirstNonPHI()); 77081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman PH->replaceAllUsesWith(Conv); 77181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman } else { 77281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman UIToFPInst *Conv = new UIToFPInst(NewPHI, PH->getType(), "indvar.conv", 77381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman PH->getParent()->getFirstNonPHI()); 77481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman PH->replaceAllUsesWith(Conv); 77581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman } 77681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman RecursivelyDeleteTriviallyDeadInstructions(PH); 777cd40233429fce385ae4b22301ce705273a6951a1Devang Patel } 77858d43d4a41b21085c063bdd21a2abb68056e2a6fDevang Patel 77981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Add a new IVUsers entry for the newly-created integer PHI. 78081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman IU->AddUsersIfInteresting(NewPHI); 78181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman} 782