IndVarSimplify.cpp revision 7b9f6b1b21bc0b06f3c72beae51e9db631319503
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 } 31040bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner} 31115cad759fe2048ac5eb137c6bb0ab7287538677eChris Lattner 31260f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohmanvoid IndVarSimplify::RewriteNonIntegerIVs(Loop *L) { 3132d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman // First step. Check to see if there are any floating-point recurrences. 31440bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // If there are, change them into integer recurrences, permitting analysis by 31540bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // the SCEV routines. 31615cad759fe2048ac5eb137c6bb0ab7287538677eChris Lattner // 31740bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner BasicBlock *Header = L->getHeader(); 318fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 31981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman SmallVector<WeakVH, 8> PHIs; 32081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman for (BasicBlock::iterator I = Header->begin(); 32181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman PHINode *PN = dyn_cast<PHINode>(I); ++I) 32281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman PHIs.push_back(PN); 32381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 32481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman for (unsigned i = 0, e = PHIs.size(); i != e; ++i) 32581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (PHINode *PN = dyn_cast_or_null<PHINode>(PHIs[i])) 32681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman HandleFloatingPointIV(L, PN); 32715cad759fe2048ac5eb137c6bb0ab7287538677eChris Lattner 3282d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman // If the loop previously had floating-point IV, ScalarEvolution 32960f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman // may not have been able to compute a trip count. Now that we've done some 33060f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman // re-writing, the trip count may be computable. 33160f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman if (Changed) 3324c7279ac726e338400626fca5a09b5533426eb6aDan Gohman SE->forgetLoop(L); 333c671d892ab1d3d8fed18a61f66f3f3a86e73ebd9Dale Johannesen} 334c671d892ab1d3d8fed18a61f66f3f3a86e73ebd9Dale Johannesen 335c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohmanbool IndVarSimplify::runOnLoop(Loop *L, LPPassManager &LPM) { 33681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman IU = &getAnalysis<IVUsers>(); 3375ee99979065d75605d150d7e567e4351024aae8fDevang Patel LI = &getAnalysis<LoopInfo>(); 3385ee99979065d75605d150d7e567e4351024aae8fDevang Patel SE = &getAnalysis<ScalarEvolution>(); 339de53dc03f5c1549f3176e979bbeeac965dfa5cbcDan Gohman DT = &getAnalysis<DominatorTree>(); 3405ee99979065d75605d150d7e567e4351024aae8fDevang Patel Changed = false; 34160f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman 3422d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman // If there are any floating-point recurrences, attempt to 34360f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman // transform them to use integer recurrences. 34460f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman RewriteNonIntegerIVs(L); 34560f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman 34681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman BasicBlock *ExitingBlock = L->getExitingBlock(); // may be null 3470bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *BackedgeTakenCount = SE->getBackedgeTakenCount(L); 3489caed5440d59dac4b388152fe8b993dc0491e5e9Chris Lattner 349667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman // Create a rewriter object which we'll use to transform the code with. 350667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman SCEVExpander Rewriter(*SE); 351667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman 35240bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // Check to see if this loop has a computable loop-invariant execution count. 35340bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // If so, this means that we can compute the final value of any expressions 35440bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // that are recurrent in the loop, and substitute the exit values from the 35540bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // loop into any instructions outside of the loop that use the final values of 35640bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // the current expressions. 357394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner // 35846bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman if (!isa<SCEVCouldNotCompute>(BackedgeTakenCount)) 359454d26dc43207ec537d843229db6f5e6a302e23dDan Gohman RewriteLoopExitValues(L, Rewriter); 36040bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner 36181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Compute the type of the largest recurrence expression, and decide whether 36281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // a canonical induction variable should be inserted. 363c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman const Type *LargestType = 0; 36481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman bool NeedCannIV = false; 36546bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman if (!isa<SCEVCouldNotCompute>(BackedgeTakenCount)) { 36646bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman LargestType = BackedgeTakenCount->getType(); 367af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman LargestType = SE->getEffectiveSCEVType(LargestType); 36881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // If we have a known trip count and a single exit block, we'll be 36981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // rewriting the loop exit test condition below, which requires a 37081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // canonical induction variable. 37181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (ExitingBlock) 37281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman NeedCannIV = true; 373f50af088f19f525f3d1026eb61db77e0037a9f43Chris Lattner } 374572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman for (IVUsers::const_iterator I = IU->begin(), E = IU->end(); I != E; ++I) { 375572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman const Type *Ty = 376572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman SE->getEffectiveSCEVType(I->getOperandValToReplace()->getType()); 377c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman if (!LargestType || 37881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman SE->getTypeSizeInBits(Ty) > 379af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman SE->getTypeSizeInBits(LargestType)) 38081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman LargestType = Ty; 381572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman NeedCannIV = true; 382500597a1c39e91a3020587318ed61e737b6c613aChris Lattner } 383394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner 384f451cb870efcf9e0302d25ed05f4cac6bb494e42Dan Gohman // Now that we know the largest of the induction variable expressions 38581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // in this loop, insert a canonical induction variable of the largest size. 386c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman Value *IndVar = 0; 38781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (NeedCannIV) { 38885669637139089eaed8def1583ac04266c9654e2Dan Gohman // Check to see if the loop already has any canonical-looking induction 38985669637139089eaed8def1583ac04266c9654e2Dan Gohman // variables. If any are present and wider than the planned canonical 39085669637139089eaed8def1583ac04266c9654e2Dan Gohman // induction variable, temporarily remove them, so that the Rewriter 39185669637139089eaed8def1583ac04266c9654e2Dan Gohman // doesn't attempt to reuse them. 39285669637139089eaed8def1583ac04266c9654e2Dan Gohman SmallVector<PHINode *, 2> OldCannIVs; 39385669637139089eaed8def1583ac04266c9654e2Dan Gohman while (PHINode *OldCannIV = L->getCanonicalInductionVariable()) { 3944d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman if (SE->getTypeSizeInBits(OldCannIV->getType()) > 3954d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman SE->getTypeSizeInBits(LargestType)) 3964d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman OldCannIV->removeFromParent(); 3974d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman else 39885669637139089eaed8def1583ac04266c9654e2Dan Gohman break; 39985669637139089eaed8def1583ac04266c9654e2Dan Gohman OldCannIVs.push_back(OldCannIV); 4004d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman } 4014d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman 402667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman IndVar = Rewriter.getOrInsertCanonicalInductionVariable(L, LargestType); 4034d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman 404c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman ++NumInserted; 405c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman Changed = true; 406f67ef318aa29e7cc0c7de76349881959936d9eeeDavid Greene DEBUG(dbgs() << "INDVARS: New CanIV: " << *IndVar << '\n'); 4074d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman 4084d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman // Now that the official induction variable is established, reinsert 40985669637139089eaed8def1583ac04266c9654e2Dan Gohman // any old canonical-looking variables after it so that the IR remains 41085669637139089eaed8def1583ac04266c9654e2Dan Gohman // consistent. They will be deleted as part of the dead-PHI deletion at 4114d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman // the end of the pass. 41285669637139089eaed8def1583ac04266c9654e2Dan Gohman while (!OldCannIVs.empty()) { 41385669637139089eaed8def1583ac04266c9654e2Dan Gohman PHINode *OldCannIV = OldCannIVs.pop_back_val(); 41485669637139089eaed8def1583ac04266c9654e2Dan Gohman OldCannIV->insertBefore(L->getHeader()->getFirstNonPHI()); 41585669637139089eaed8def1583ac04266c9654e2Dan Gohman } 416d19534add90a2a894af61523b830887097bb780bDan Gohman } 41740bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner 418c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman // If we have a trip count expression, rewrite the loop's exit condition 419c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman // using it. We can currently only handle loops with a single exit. 42081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman ICmpInst *NewICmp = 0; 42185669637139089eaed8def1583ac04266c9654e2Dan Gohman if (!isa<SCEVCouldNotCompute>(BackedgeTakenCount) && 42285669637139089eaed8def1583ac04266c9654e2Dan Gohman !BackedgeTakenCount->isZero() && 42385669637139089eaed8def1583ac04266c9654e2Dan Gohman ExitingBlock) { 42481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman assert(NeedCannIV && 42581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman "LinearFunctionTestReplace requires a canonical induction variable"); 426c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman // Can't rewrite non-branch yet. 42781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (BranchInst *BI = dyn_cast<BranchInst>(ExitingBlock->getTerminator())) 42881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman NewICmp = LinearFunctionTestReplace(L, BackedgeTakenCount, IndVar, 42981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman ExitingBlock, BI, Rewriter); 43081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman } 431c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman 4323d431384f05c9defc84f36eafe220415cc12ee93Torok Edwin // Rewrite IV-derived expressions. Clears the rewriter cache. 433454d26dc43207ec537d843229db6f5e6a302e23dDan Gohman RewriteIVExpressions(L, Rewriter); 434fcb81f5f4cbac61851b7dec403961cf88e614aa1Chris Lattner 435667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman // The Rewriter may not be used from this point on. 4363d431384f05c9defc84f36eafe220415cc12ee93Torok Edwin 43781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Loop-invariant instructions in the preheader that aren't used in the 43881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // loop may be sunk below the loop to reduce register pressure. 439667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman SinkUnusedInvariants(L); 44081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 44181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // For completeness, inform IVUsers of the IV use in the newly-created 44281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // loop exit test instruction. 44381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (NewICmp) 44481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman IU->AddUsersIfInteresting(cast<Instruction>(NewICmp->getOperand(0))); 44581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 44681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Clean up dead instructions. 4479fff2187a21f765ed87a25c48552a6942450f3e2Dan Gohman Changed |= DeleteDeadPHIs(L->getHeader()); 44881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Check a post-condition. 449bbf81d88116d23fb0776412b5916f7d0b8b3ca7eDan Gohman assert(L->isLCSSAForm(*DT) && "Indvars did not leave the loop in lcssa form!"); 45081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman return Changed; 45181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman} 45281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 453454d26dc43207ec537d843229db6f5e6a302e23dDan Gohmanvoid IndVarSimplify::RewriteIVExpressions(Loop *L, SCEVExpander &Rewriter) { 45481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman SmallVector<WeakVH, 16> DeadInsts; 45581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 45681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Rewrite all induction variable expressions in terms of the canonical 45781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // induction variable. 45881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // 45981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // If there were induction variables of other sizes or offsets, manually 46081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // add the offsets to the primary induction variable and cast, avoiding 46181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // the need for the code evaluation methods to insert induction variables 46281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // of different sizes. 463572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman for (IVUsers::iterator UI = IU->begin(), E = IU->end(); UI != E; ++UI) { 464572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman const SCEV *Stride = UI->getStride(); 465572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman Value *Op = UI->getOperandValToReplace(); 466572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman const Type *UseTy = Op->getType(); 467572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman Instruction *User = UI->getUser(); 468572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman 469572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // Compute the final addrec to expand into code. 470572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman const SCEV *AR = IU->getReplacementExpr(*UI); 471572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman 472572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // Evaluate the expression out of the loop, if possible. 473572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman if (!L->contains(UI->getUser())) { 474572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman const SCEV *ExitVal = SE->getSCEVAtScope(AR, L->getParentLoop()); 475572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman if (ExitVal->isLoopInvariant(L)) 476572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman AR = ExitVal; 47781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman } 478572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman 479572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // FIXME: It is an extremely bad idea to indvar substitute anything more 480572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // complex than affine induction variables. Doing so will put expensive 481572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // polynomial evaluations inside of the loop, and the str reduction pass 482572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // currently can only reduce affine polynomials. For now just disable 483572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // indvar subst on anything more complex than an affine addrec, unless 484572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // it can be expanded to a trivial value. 485572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman if (!AR->isLoopInvariant(L) && !Stride->isLoopInvariant(L)) 486572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman continue; 487572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman 488572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // Determine the insertion point for this user. By default, insert 489572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // immediately before the user. The SCEVExpander class will automatically 490572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // hoist loop invariants out of the loop. For PHI nodes, there may be 491572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // multiple uses, so compute the nearest common dominator for the 492572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // incoming blocks. 493572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman Instruction *InsertPt = User; 494572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman if (PHINode *PHI = dyn_cast<PHINode>(InsertPt)) 495572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i) 496572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman if (PHI->getIncomingValue(i) == Op) { 497572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman if (InsertPt == User) 498572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman InsertPt = PHI->getIncomingBlock(i)->getTerminator(); 499572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman else 500572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman InsertPt = 501572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman DT->findNearestCommonDominator(InsertPt->getParent(), 502572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman PHI->getIncomingBlock(i)) 503572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman ->getTerminator(); 504572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman } 505572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman 506572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // Now expand it into actual Instructions and patch it into place. 507572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman Value *NewVal = Rewriter.expandCodeFor(AR, UseTy, InsertPt); 508572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman 509572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // Patch the new value into place. 510572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman if (Op->hasName()) 511572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman NewVal->takeName(Op); 512572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman User->replaceUsesOfWith(Op, NewVal); 513572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman UI->setOperandValToReplace(NewVal); 514572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman DEBUG(dbgs() << "INDVARS: Rewrote IV '" << *AR << "' " << *Op << '\n' 515572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman << " into = " << *NewVal << "\n"); 516572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman ++NumRemoved; 517572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman Changed = true; 518572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman 519572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // The old value may be dead now. 520572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman DeadInsts.push_back(Op); 521500597a1c39e91a3020587318ed61e737b6c613aChris Lattner } 522ba4f3f6a419326df190599421fa149c90235cb72Chris Lattner 5233d431384f05c9defc84f36eafe220415cc12ee93Torok Edwin // Clear the rewriter cache, because values that are in the rewriter's cache 5243d431384f05c9defc84f36eafe220415cc12ee93Torok Edwin // can be deleted in the loop below, causing the AssertingVH in the cache to 5253d431384f05c9defc84f36eafe220415cc12ee93Torok Edwin // trigger. 5263d431384f05c9defc84f36eafe220415cc12ee93Torok Edwin Rewriter.clear(); 52781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Now that we're done iterating through lists, clean up any instructions 52881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // which are now dead. 529a10756ee657a4d43a48cca5c166919093930ed6bDan Gohman while (!DeadInsts.empty()) 530a10756ee657a4d43a48cca5c166919093930ed6bDan Gohman if (Instruction *Inst = 531a10756ee657a4d43a48cca5c166919093930ed6bDan Gohman dyn_cast_or_null<Instruction>(DeadInsts.pop_back_val())) 53281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman RecursivelyDeleteTriviallyDeadInstructions(Inst); 53381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman} 53481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 53581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman/// If there's a single exit block, sink any loop-invariant values that 53681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman/// were defined in the preheader but not used inside the loop into the 53781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman/// exit block to reduce register pressure in the loop. 538667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohmanvoid IndVarSimplify::SinkUnusedInvariants(Loop *L) { 53981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman BasicBlock *ExitBlock = L->getExitBlock(); 54081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (!ExitBlock) return; 54181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 54281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman BasicBlock *Preheader = L->getLoopPreheader(); 54303e896bd6073efc4523d8bcd0239d6ed62126db7Dan Gohman if (!Preheader) return; 54403e896bd6073efc4523d8bcd0239d6ed62126db7Dan Gohman 54503e896bd6073efc4523d8bcd0239d6ed62126db7Dan Gohman Instruction *InsertPt = ExitBlock->getFirstNonPHI(); 54681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman BasicBlock::iterator I = Preheader->getTerminator(); 54781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman while (I != Preheader->begin()) { 54881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman --I; 549667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman // New instructions were inserted at the end of the preheader. 550667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman if (isa<PHINode>(I)) 55181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman break; 5520c77db32dd8ae10b5a26d60718dbe03dc2745888Eli Friedman // Don't move instructions which might have side effects, since the side 5530c77db32dd8ae10b5a26d60718dbe03dc2745888Eli Friedman // effects need to complete before instructions inside the loop. Also 5540c77db32dd8ae10b5a26d60718dbe03dc2745888Eli Friedman // don't move instructions which might read memory, since the loop may 5550c77db32dd8ae10b5a26d60718dbe03dc2745888Eli Friedman // modify memory. Note that it's okay if the instruction might have 5560c77db32dd8ae10b5a26d60718dbe03dc2745888Eli Friedman // undefined behavior: LoopSimplify guarantees that the preheader 5570c77db32dd8ae10b5a26d60718dbe03dc2745888Eli Friedman // dominates the exit block. 5580c77db32dd8ae10b5a26d60718dbe03dc2745888Eli Friedman if (I->mayHaveSideEffects() || I->mayReadFromMemory()) 559667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman continue; 5607b9f6b1b21bc0b06f3c72beae51e9db631319503Devang Patel // Skip debug info intrinsics. 5617b9f6b1b21bc0b06f3c72beae51e9db631319503Devang Patel if (isa<DbgInfoIntrinsic>(I)) 5627b9f6b1b21bc0b06f3c72beae51e9db631319503Devang Patel continue; 56376f497a351c562f366b5e93c27d3f1652fb48ff4Dan Gohman // Don't sink static AllocaInsts out of the entry block, which would 56476f497a351c562f366b5e93c27d3f1652fb48ff4Dan Gohman // turn them into dynamic allocas! 56576f497a351c562f366b5e93c27d3f1652fb48ff4Dan Gohman if (AllocaInst *AI = dyn_cast<AllocaInst>(I)) 56676f497a351c562f366b5e93c27d3f1652fb48ff4Dan Gohman if (AI->isStaticAlloca()) 56776f497a351c562f366b5e93c27d3f1652fb48ff4Dan Gohman continue; 56881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Determine if there is a use in or before the loop (direct or 56981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // otherwise). 57081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman bool UsedInLoop = false; 57181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman for (Value::use_iterator UI = I->use_begin(), UE = I->use_end(); 57281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman UI != UE; ++UI) { 57381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman BasicBlock *UseBB = cast<Instruction>(UI)->getParent(); 57481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (PHINode *P = dyn_cast<PHINode>(UI)) { 57581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman unsigned i = 57681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman PHINode::getIncomingValueNumForOperand(UI.getOperandNo()); 57781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman UseBB = P->getIncomingBlock(i); 57881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman } 57981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (UseBB == Preheader || L->contains(UseBB)) { 58081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman UsedInLoop = true; 58181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman break; 58281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman } 58381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman } 58481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // If there is, the def must remain in the preheader. 58581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (UsedInLoop) 58681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman continue; 58781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Otherwise, sink it to the exit block. 58881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman Instruction *ToMove = I; 58981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman bool Done = false; 59081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (I != Preheader->begin()) 59181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman --I; 59281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman else 59381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman Done = true; 594667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman ToMove->moveBefore(InsertPt); 59581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (Done) 59681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman break; 597667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman InsertPt = ToMove; 59881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman } 59981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman} 60081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 6013f46a3abeedba8d517b4182de34c821d752db058Dan Gohman/// Return true if it is OK to use SIToFPInst for an induction variable 6023f46a3abeedba8d517b4182de34c821d752db058Dan Gohman/// with given initial and exit values. 60313877bf6c20621541ff71583c626bda68ef09219Devang Patelstatic bool useSIToFPInst(ConstantFP &InitV, ConstantFP &ExitV, 60413877bf6c20621541ff71583c626bda68ef09219Devang Patel uint64_t intIV, uint64_t intEV) { 60513877bf6c20621541ff71583c626bda68ef09219Devang Patel 606cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman if (InitV.getValueAPF().isNegative() || ExitV.getValueAPF().isNegative()) 60713877bf6c20621541ff71583c626bda68ef09219Devang Patel return true; 60813877bf6c20621541ff71583c626bda68ef09219Devang Patel 60913877bf6c20621541ff71583c626bda68ef09219Devang Patel // If the iteration range can be handled by SIToFPInst then use it. 61013877bf6c20621541ff71583c626bda68ef09219Devang Patel APInt Max = APInt::getSignedMaxValue(32); 611bae7d6dbeb842b5ed051c50a87bc282f2dec6e1fDale Johannesen if (Max.getZExtValue() > static_cast<uint64_t>(abs64(intEV - intIV))) 61213877bf6c20621541ff71583c626bda68ef09219Devang Patel return true; 613cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 61413877bf6c20621541ff71583c626bda68ef09219Devang Patel return false; 61513877bf6c20621541ff71583c626bda68ef09219Devang Patel} 61613877bf6c20621541ff71583c626bda68ef09219Devang Patel 61713877bf6c20621541ff71583c626bda68ef09219Devang Patel/// convertToInt - Convert APF to an integer, if possible. 618cd40233429fce385ae4b22301ce705273a6951a1Devang Patelstatic bool convertToInt(const APFloat &APF, uint64_t *intVal) { 619cd40233429fce385ae4b22301ce705273a6951a1Devang Patel 620cd40233429fce385ae4b22301ce705273a6951a1Devang Patel bool isExact = false; 621794a7dbce030f93315b1305f83a374232f09bba5Evan Cheng if (&APF.getSemantics() == &APFloat::PPCDoubleDouble) 622794a7dbce030f93315b1305f83a374232f09bba5Evan Cheng return false; 623cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman if (APF.convertToInteger(intVal, 32, APF.isNegative(), 624cd40233429fce385ae4b22301ce705273a6951a1Devang Patel APFloat::rmTowardZero, &isExact) 625cd40233429fce385ae4b22301ce705273a6951a1Devang Patel != APFloat::opOK) 626cd40233429fce385ae4b22301ce705273a6951a1Devang Patel return false; 627cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman if (!isExact) 628cd40233429fce385ae4b22301ce705273a6951a1Devang Patel return false; 629cd40233429fce385ae4b22301ce705273a6951a1Devang Patel return true; 630cd40233429fce385ae4b22301ce705273a6951a1Devang Patel 631cd40233429fce385ae4b22301ce705273a6951a1Devang Patel} 632cd40233429fce385ae4b22301ce705273a6951a1Devang Patel 63358d43d4a41b21085c063bdd21a2abb68056e2a6fDevang Patel/// HandleFloatingPointIV - If the loop has floating induction variable 63458d43d4a41b21085c063bdd21a2abb68056e2a6fDevang Patel/// then insert corresponding integer induction variable if possible. 63584e3515974407a606289c6e762a0419723b7918fDevang Patel/// For example, 63684e3515974407a606289c6e762a0419723b7918fDevang Patel/// for(double i = 0; i < 10000; ++i) 63784e3515974407a606289c6e762a0419723b7918fDevang Patel/// bar(i) 63884e3515974407a606289c6e762a0419723b7918fDevang Patel/// is converted into 63984e3515974407a606289c6e762a0419723b7918fDevang Patel/// for(int i = 0; i < 10000; ++i) 64084e3515974407a606289c6e762a0419723b7918fDevang Patel/// bar((double)i); 64184e3515974407a606289c6e762a0419723b7918fDevang Patel/// 64281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohmanvoid IndVarSimplify::HandleFloatingPointIV(Loop *L, PHINode *PH) { 64384e3515974407a606289c6e762a0419723b7918fDevang Patel 64484e3515974407a606289c6e762a0419723b7918fDevang Patel unsigned IncomingEdge = L->contains(PH->getIncomingBlock(0)); 64584e3515974407a606289c6e762a0419723b7918fDevang Patel unsigned BackEdge = IncomingEdge^1; 646cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 64784e3515974407a606289c6e762a0419723b7918fDevang Patel // Check incoming value. 648cd40233429fce385ae4b22301ce705273a6951a1Devang Patel ConstantFP *InitValue = dyn_cast<ConstantFP>(PH->getIncomingValue(IncomingEdge)); 649cd40233429fce385ae4b22301ce705273a6951a1Devang Patel if (!InitValue) return; 6501d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson uint64_t newInitValue = 6511d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson Type::getInt32Ty(PH->getContext())->getPrimitiveSizeInBits(); 652cd40233429fce385ae4b22301ce705273a6951a1Devang Patel if (!convertToInt(InitValue->getValueAPF(), &newInitValue)) 653cd40233429fce385ae4b22301ce705273a6951a1Devang Patel return; 654cd40233429fce385ae4b22301ce705273a6951a1Devang Patel 6553f46a3abeedba8d517b4182de34c821d752db058Dan Gohman // Check IV increment. Reject this PH if increment operation is not 656cd40233429fce385ae4b22301ce705273a6951a1Devang Patel // an add or increment value can not be represented by an integer. 657cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman BinaryOperator *Incr = 65884e3515974407a606289c6e762a0419723b7918fDevang Patel dyn_cast<BinaryOperator>(PH->getIncomingValue(BackEdge)); 65984e3515974407a606289c6e762a0419723b7918fDevang Patel if (!Incr) return; 660ae3a0be92e33bc716722aa600983fc1535acb122Dan Gohman if (Incr->getOpcode() != Instruction::FAdd) return; 66184e3515974407a606289c6e762a0419723b7918fDevang Patel ConstantFP *IncrValue = NULL; 66284e3515974407a606289c6e762a0419723b7918fDevang Patel unsigned IncrVIndex = 1; 66384e3515974407a606289c6e762a0419723b7918fDevang Patel if (Incr->getOperand(1) == PH) 66484e3515974407a606289c6e762a0419723b7918fDevang Patel IncrVIndex = 0; 66584e3515974407a606289c6e762a0419723b7918fDevang Patel IncrValue = dyn_cast<ConstantFP>(Incr->getOperand(IncrVIndex)); 66684e3515974407a606289c6e762a0419723b7918fDevang Patel if (!IncrValue) return; 6671d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson uint64_t newIncrValue = 6681d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson Type::getInt32Ty(PH->getContext())->getPrimitiveSizeInBits(); 669cd40233429fce385ae4b22301ce705273a6951a1Devang Patel if (!convertToInt(IncrValue->getValueAPF(), &newIncrValue)) 670cd40233429fce385ae4b22301ce705273a6951a1Devang Patel return; 671cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 672cd40233429fce385ae4b22301ce705273a6951a1Devang Patel // Check Incr uses. One user is PH and the other users is exit condition used 673cd40233429fce385ae4b22301ce705273a6951a1Devang Patel // by the conditional terminator. 67484e3515974407a606289c6e762a0419723b7918fDevang Patel Value::use_iterator IncrUse = Incr->use_begin(); 67584e3515974407a606289c6e762a0419723b7918fDevang Patel Instruction *U1 = cast<Instruction>(IncrUse++); 67684e3515974407a606289c6e762a0419723b7918fDevang Patel if (IncrUse == Incr->use_end()) return; 67784e3515974407a606289c6e762a0419723b7918fDevang Patel Instruction *U2 = cast<Instruction>(IncrUse++); 67884e3515974407a606289c6e762a0419723b7918fDevang Patel if (IncrUse != Incr->use_end()) return; 679cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 68084e3515974407a606289c6e762a0419723b7918fDevang Patel // Find exit condition. 68184e3515974407a606289c6e762a0419723b7918fDevang Patel FCmpInst *EC = dyn_cast<FCmpInst>(U1); 68284e3515974407a606289c6e762a0419723b7918fDevang Patel if (!EC) 68384e3515974407a606289c6e762a0419723b7918fDevang Patel EC = dyn_cast<FCmpInst>(U2); 68484e3515974407a606289c6e762a0419723b7918fDevang Patel if (!EC) return; 68584e3515974407a606289c6e762a0419723b7918fDevang Patel 68684e3515974407a606289c6e762a0419723b7918fDevang Patel if (BranchInst *BI = dyn_cast<BranchInst>(EC->getParent()->getTerminator())) { 68784e3515974407a606289c6e762a0419723b7918fDevang Patel if (!BI->isConditional()) return; 68884e3515974407a606289c6e762a0419723b7918fDevang Patel if (BI->getCondition() != EC) return; 68958d43d4a41b21085c063bdd21a2abb68056e2a6fDevang Patel } 69084e3515974407a606289c6e762a0419723b7918fDevang Patel 6913f46a3abeedba8d517b4182de34c821d752db058Dan Gohman // Find exit value. If exit value can not be represented as an integer then 692cd40233429fce385ae4b22301ce705273a6951a1Devang Patel // do not handle this floating point PH. 69384e3515974407a606289c6e762a0419723b7918fDevang Patel ConstantFP *EV = NULL; 69484e3515974407a606289c6e762a0419723b7918fDevang Patel unsigned EVIndex = 1; 69584e3515974407a606289c6e762a0419723b7918fDevang Patel if (EC->getOperand(1) == Incr) 69684e3515974407a606289c6e762a0419723b7918fDevang Patel EVIndex = 0; 69784e3515974407a606289c6e762a0419723b7918fDevang Patel EV = dyn_cast<ConstantFP>(EC->getOperand(EVIndex)); 69884e3515974407a606289c6e762a0419723b7918fDevang Patel if (!EV) return; 6991d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson uint64_t intEV = Type::getInt32Ty(PH->getContext())->getPrimitiveSizeInBits(); 700cd40233429fce385ae4b22301ce705273a6951a1Devang Patel if (!convertToInt(EV->getValueAPF(), &intEV)) 70184e3515974407a606289c6e762a0419723b7918fDevang Patel return; 702cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 70384e3515974407a606289c6e762a0419723b7918fDevang Patel // Find new predicate for integer comparison. 70484e3515974407a606289c6e762a0419723b7918fDevang Patel CmpInst::Predicate NewPred = CmpInst::BAD_ICMP_PREDICATE; 70584e3515974407a606289c6e762a0419723b7918fDevang Patel switch (EC->getPredicate()) { 70684e3515974407a606289c6e762a0419723b7918fDevang Patel case CmpInst::FCMP_OEQ: 70784e3515974407a606289c6e762a0419723b7918fDevang Patel case CmpInst::FCMP_UEQ: 70884e3515974407a606289c6e762a0419723b7918fDevang Patel NewPred = CmpInst::ICMP_EQ; 70984e3515974407a606289c6e762a0419723b7918fDevang Patel break; 71084e3515974407a606289c6e762a0419723b7918fDevang Patel case CmpInst::FCMP_OGT: 71184e3515974407a606289c6e762a0419723b7918fDevang Patel case CmpInst::FCMP_UGT: 71284e3515974407a606289c6e762a0419723b7918fDevang Patel NewPred = CmpInst::ICMP_UGT; 71384e3515974407a606289c6e762a0419723b7918fDevang Patel break; 71484e3515974407a606289c6e762a0419723b7918fDevang Patel case CmpInst::FCMP_OGE: 71584e3515974407a606289c6e762a0419723b7918fDevang Patel case CmpInst::FCMP_UGE: 71684e3515974407a606289c6e762a0419723b7918fDevang Patel NewPred = CmpInst::ICMP_UGE; 71784e3515974407a606289c6e762a0419723b7918fDevang Patel break; 71884e3515974407a606289c6e762a0419723b7918fDevang Patel case CmpInst::FCMP_OLT: 71984e3515974407a606289c6e762a0419723b7918fDevang Patel case CmpInst::FCMP_ULT: 72084e3515974407a606289c6e762a0419723b7918fDevang Patel NewPred = CmpInst::ICMP_ULT; 72184e3515974407a606289c6e762a0419723b7918fDevang Patel break; 72284e3515974407a606289c6e762a0419723b7918fDevang Patel case CmpInst::FCMP_OLE: 72384e3515974407a606289c6e762a0419723b7918fDevang Patel case CmpInst::FCMP_ULE: 72484e3515974407a606289c6e762a0419723b7918fDevang Patel NewPred = CmpInst::ICMP_ULE; 72584e3515974407a606289c6e762a0419723b7918fDevang Patel break; 72684e3515974407a606289c6e762a0419723b7918fDevang Patel default: 72784e3515974407a606289c6e762a0419723b7918fDevang Patel break; 72858d43d4a41b21085c063bdd21a2abb68056e2a6fDevang Patel } 72984e3515974407a606289c6e762a0419723b7918fDevang Patel if (NewPred == CmpInst::BAD_ICMP_PREDICATE) return; 730cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 73184e3515974407a606289c6e762a0419723b7918fDevang Patel // Insert new integer induction variable. 7321d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson PHINode *NewPHI = PHINode::Create(Type::getInt32Ty(PH->getContext()), 73384e3515974407a606289c6e762a0419723b7918fDevang Patel PH->getName()+".int", PH); 7341d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson NewPHI->addIncoming(ConstantInt::get(Type::getInt32Ty(PH->getContext()), 7351d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson newInitValue), 73684e3515974407a606289c6e762a0419723b7918fDevang Patel PH->getIncomingBlock(IncomingEdge)); 73784e3515974407a606289c6e762a0419723b7918fDevang Patel 738cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman Value *NewAdd = BinaryOperator::CreateAdd(NewPHI, 7391d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson ConstantInt::get(Type::getInt32Ty(PH->getContext()), 740cd40233429fce385ae4b22301ce705273a6951a1Devang Patel newIncrValue), 74184e3515974407a606289c6e762a0419723b7918fDevang Patel Incr->getName()+".int", Incr); 74284e3515974407a606289c6e762a0419723b7918fDevang Patel NewPHI->addIncoming(NewAdd, PH->getIncomingBlock(BackEdge)); 74384e3515974407a606289c6e762a0419723b7918fDevang Patel 744617d108a639b29015da2dbf0e54f61bd39c3c33cDale Johannesen // The back edge is edge 1 of newPHI, whatever it may have been in the 745617d108a639b29015da2dbf0e54f61bd39c3c33cDale Johannesen // original PHI. 7461d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson ConstantInt *NewEV = ConstantInt::get(Type::getInt32Ty(PH->getContext()), 7471d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson intEV); 748617d108a639b29015da2dbf0e54f61bd39c3c33cDale Johannesen Value *LHS = (EVIndex == 1 ? NewPHI->getIncomingValue(1) : NewEV); 749617d108a639b29015da2dbf0e54f61bd39c3c33cDale Johannesen Value *RHS = (EVIndex == 1 ? NewEV : NewPHI->getIncomingValue(1)); 750333c40096561218bc3597cf153c0a3895274414cOwen Anderson ICmpInst *NewEC = new ICmpInst(EC->getParent()->getTerminator(), 751460f656475738d1a95a6be95346908ce1597df25Daniel Dunbar NewPred, LHS, RHS, EC->getName()); 752cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 7533f46a3abeedba8d517b4182de34c821d752db058Dan Gohman // In the following deletions, PH may become dead and may be deleted. 75481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Use a WeakVH to observe whether this happens. 75581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman WeakVH WeakPH = PH; 75681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 7573f46a3abeedba8d517b4182de34c821d752db058Dan Gohman // Delete old, floating point, exit comparison instruction. 75814fba294e1f2d619fe50b72d5fd88da2b17461ddDan Gohman NewEC->takeName(EC); 75984e3515974407a606289c6e762a0419723b7918fDevang Patel EC->replaceAllUsesWith(NewEC); 76081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman RecursivelyDeleteTriviallyDeadInstructions(EC); 761cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 76284e3515974407a606289c6e762a0419723b7918fDevang Patel // Delete old, floating point, increment instruction. 7639e9a0d5fc26878e51a58a8b57900fcbf952c2691Owen Anderson Incr->replaceAllUsesWith(UndefValue::get(Incr->getType())); 76481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman RecursivelyDeleteTriviallyDeadInstructions(Incr); 76581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 76681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Replace floating induction variable, if it isn't already deleted. 76781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Give SIToFPInst preference over UIToFPInst because it is faster on 76881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // platforms that are widely used. 76981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (WeakPH && !PH->use_empty()) { 77081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (useSIToFPInst(*InitValue, *EV, newInitValue, intEV)) { 77181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman SIToFPInst *Conv = new SIToFPInst(NewPHI, PH->getType(), "indvar.conv", 77281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman PH->getParent()->getFirstNonPHI()); 77381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman PH->replaceAllUsesWith(Conv); 77481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman } else { 77581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman UIToFPInst *Conv = new UIToFPInst(NewPHI, PH->getType(), "indvar.conv", 77681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman PH->getParent()->getFirstNonPHI()); 77781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman PH->replaceAllUsesWith(Conv); 77881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman } 77981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman RecursivelyDeleteTriviallyDeadInstructions(PH); 780cd40233429fce385ae4b22301ce705273a6951a1Devang Patel } 78158d43d4a41b21085c063bdd21a2abb68056e2a6fDevang Patel 78281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Add a new IVUsers entry for the newly-created integer PHI. 78381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman IU->AddUsersIfInteresting(NewPHI); 78481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman} 785