IndVarSimplify.cpp revision 931e345e76e75391d2a7c96530e305f802b5429d
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 100931e345e76e75391d2a7c96530e305f802b5429dDan Gohman void EliminateIVComparisons(); 10160f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman void RewriteNonIntegerIVs(Loop *L); 10260f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman 1030bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman ICmpInst *LinearFunctionTestReplace(Loop *L, const SCEV *BackedgeTakenCount, 104a575871884b247b0946290876ac7d4657b384cf9Dan Gohman Value *IndVar, 105c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman BasicBlock *ExitingBlock, 106c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman BranchInst *BI, 10715cab2817b8f63fec0148609278bc2c1e05abb50Dan Gohman SCEVExpander &Rewriter); 108454d26dc43207ec537d843229db6f5e6a302e23dDan Gohman void RewriteLoopExitValues(Loop *L, SCEVExpander &Rewriter); 10940bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner 110454d26dc43207ec537d843229db6f5e6a302e23dDan Gohman void RewriteIVExpressions(Loop *L, SCEVExpander &Rewriter); 111d22a849282c45bbf7eb1734c274294d81e49e3a8Devang Patel 112667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman void SinkUnusedInvariants(Loop *L); 11381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 11481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman void HandleFloatingPointIV(Loop *L, PHINode *PH); 1153324e718bc9ac2ede08a14c325848b576849542bChris Lattner }; 1165e76140536ba66fadeced1cd892f79616f407e3cChris Lattner} 117394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner 118844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanchar IndVarSimplify::ID = 0; 119844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanstatic RegisterPass<IndVarSimplify> 120844731a7f1909f55935e3514c9e713a62d67662eDan GohmanX("indvars", "Canonicalize Induction Variables"); 121844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 122394f0441e06dafca29f0752cf400990a5b8fe4b1Daniel DunbarPass *llvm::createIndVarSimplifyPass() { 1233324e718bc9ac2ede08a14c325848b576849542bChris Lattner return new IndVarSimplify(); 124394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner} 125394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner 12640bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner/// LinearFunctionTestReplace - This method rewrites the exit condition of the 12759fdaeeae8f183e18bb6ad5c382ca23e28e6aaf6Chris Lattner/// loop to be a canonical != comparison against the incremented loop induction 12859fdaeeae8f183e18bb6ad5c382ca23e28e6aaf6Chris Lattner/// variable. This pass is able to rewrite the exit tests of any loop where the 12959fdaeeae8f183e18bb6ad5c382ca23e28e6aaf6Chris Lattner/// SCEV analysis can determine a loop-invariant trip count of the loop, which 13059fdaeeae8f183e18bb6ad5c382ca23e28e6aaf6Chris Lattner/// is actually a much broader range than just linear tests. 13181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan GohmanICmpInst *IndVarSimplify::LinearFunctionTestReplace(Loop *L, 1320bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *BackedgeTakenCount, 133c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman Value *IndVar, 134c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman BasicBlock *ExitingBlock, 135c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman BranchInst *BI, 13615cab2817b8f63fec0148609278bc2c1e05abb50Dan Gohman SCEVExpander &Rewriter) { 137d244057a48660c3cd30d219118ece3f947947790Chris Lattner // If the exiting block is not the same as the backedge block, we must compare 138d244057a48660c3cd30d219118ece3f947947790Chris Lattner // against the preincremented value, otherwise we prefer to compare against 139d244057a48660c3cd30d219118ece3f947947790Chris Lattner // the post-incremented value. 140c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman Value *CmpIndVar; 1410bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *RHS = BackedgeTakenCount; 142c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman if (ExitingBlock == L->getLoopLatch()) { 14346bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman // Add one to the "backedge-taken" count to get the trip count. 14446bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman // If this addition may overflow, we have to be more pessimistic and 14546bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman // cast the induction variable before doing the add. 1460bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *Zero = SE->getIntegerSCEV(0, BackedgeTakenCount->getType()); 1470bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *N = 14846bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman SE->getAddExpr(BackedgeTakenCount, 14946bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman SE->getIntegerSCEV(1, BackedgeTakenCount->getType())); 150c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman if ((isa<SCEVConstant>(N) && !N->isZero()) || 1513948d0b8b0a71fabf25fceba1858b2b6a60d3d00Dan Gohman SE->isLoopEntryGuardedByCond(L, ICmpInst::ICMP_NE, N, Zero)) { 152c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman // No overflow. Cast the sum. 15346bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman RHS = SE->getTruncateOrZeroExtend(N, IndVar->getType()); 154c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman } else { 155c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman // Potential overflow. Cast before doing the add. 15646bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman RHS = SE->getTruncateOrZeroExtend(BackedgeTakenCount, 15746bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman IndVar->getType()); 15846bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman RHS = SE->getAddExpr(RHS, 15946bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman SE->getIntegerSCEV(1, IndVar->getType())); 160c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman } 161c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman 16246bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman // The BackedgeTaken expression contains the number of times that the 16346bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman // backedge branches to the loop header. This is one less than the 16446bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman // number of times the loop executes, so use the incremented indvar. 165c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman CmpIndVar = L->getCanonicalInductionVariableIncrement(); 166d244057a48660c3cd30d219118ece3f947947790Chris Lattner } else { 167d244057a48660c3cd30d219118ece3f947947790Chris Lattner // We have to use the preincremented value... 16846bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman RHS = SE->getTruncateOrZeroExtend(BackedgeTakenCount, 16946bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman IndVar->getType()); 170c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman CmpIndVar = IndVar; 171d244057a48660c3cd30d219118ece3f947947790Chris Lattner } 17259fdaeeae8f183e18bb6ad5c382ca23e28e6aaf6Chris Lattner 173667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman // Expand the code for the iteration count. 17440a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman assert(RHS->isLoopInvariant(L) && 17540a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman "Computed iteration count is not loop invariant!"); 176667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman Value *ExitCnt = Rewriter.expandCodeFor(RHS, IndVar->getType(), BI); 17740bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner 178e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer // Insert a new icmp_ne or icmp_eq instruction before the branch. 179e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer ICmpInst::Predicate Opcode; 18040bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner if (L->contains(BI->getSuccessor(0))) 181e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer Opcode = ICmpInst::ICMP_NE; 18240bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner else 183e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer Opcode = ICmpInst::ICMP_EQ; 18440bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner 185f67ef318aa29e7cc0c7de76349881959936d9eeeDavid Greene DEBUG(dbgs() << "INDVARS: Rewriting loop exit condition to:\n" 186bdff548e4dd577a72094d57b282de4e765643b96Chris Lattner << " LHS:" << *CmpIndVar << '\n' 187bdff548e4dd577a72094d57b282de4e765643b96Chris Lattner << " op:\t" 188bdff548e4dd577a72094d57b282de4e765643b96Chris Lattner << (Opcode == ICmpInst::ICMP_NE ? "!=" : "==") << "\n" 189bdff548e4dd577a72094d57b282de4e765643b96Chris Lattner << " RHS:\t" << *RHS << "\n"); 190c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman 191333c40096561218bc3597cf153c0a3895274414cOwen Anderson ICmpInst *Cond = new ICmpInst(BI, Opcode, CmpIndVar, ExitCnt, "exitcond"); 19281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 1932444080ca4f1f63d647272650aae874360c604cdDan Gohman Value *OrigCond = BI->getCondition(); 19495bdbfa0668cc2b475429fbc6046f364bc01edf7Dan Gohman // It's tempting to use replaceAllUsesWith here to fully replace the old 19595bdbfa0668cc2b475429fbc6046f364bc01edf7Dan Gohman // comparison, but that's not immediately safe, since users of the old 19695bdbfa0668cc2b475429fbc6046f364bc01edf7Dan Gohman // comparison may not be dominated by the new comparison. Instead, just 19795bdbfa0668cc2b475429fbc6046f364bc01edf7Dan Gohman // update the branch to use the new comparison; in the common case this 19895bdbfa0668cc2b475429fbc6046f364bc01edf7Dan Gohman // will make old comparison dead. 19995bdbfa0668cc2b475429fbc6046f364bc01edf7Dan Gohman BI->setCondition(Cond); 20081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman RecursivelyDeleteTriviallyDeadInstructions(OrigCond); 20181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 20240bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner ++NumLFTR; 20340bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner Changed = true; 20481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman return Cond; 20540bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner} 2063324e718bc9ac2ede08a14c325848b576849542bChris Lattner 20740bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner/// RewriteLoopExitValues - Check to see if this loop has a computable 20840bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner/// loop-invariant execution count. If so, this means that we can compute the 20940bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner/// final value of any expressions that are recurrent in the loop, and 21040bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner/// substitute the exit values from the loop into any instructions outside of 21140bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner/// the loop that use the final values of the current expressions. 21281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman/// 21381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman/// This is mostly redundant with the regular IndVarSimplify activities that 21481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman/// happen later, except that it's more powerful in some cases, because it's 21581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman/// able to brute-force evaluate arbitrary instructions as long as they have 21681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman/// constant operands at the beginning of the loop. 217890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohmanvoid IndVarSimplify::RewriteLoopExitValues(Loop *L, 218667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman SCEVExpander &Rewriter) { 21981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Verify the input to the pass in already in LCSSA form. 220bbf81d88116d23fb0776412b5916f7d0b8b3ca7eDan Gohman assert(L->isLCSSAForm(*DT)); 22181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 222b7211a2ce13a0365e0e1dd2f27adda2ee3d1288bDevang Patel SmallVector<BasicBlock*, 8> ExitBlocks; 2239f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner L->getUniqueExitBlocks(ExitBlocks); 2249f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner 2259f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // Find all values that are computed inside the loop, but used outside of it. 2269f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // Because of LCSSA, these values will only occur in LCSSA PHI Nodes. Scan 2279f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // the exit blocks of the loop to find them. 2289f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) { 2299f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner BasicBlock *ExitBB = ExitBlocks[i]; 230cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 2319f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // If there are no PHI nodes in this exit block, then no values defined 2329f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // inside the loop are used on this path, skip it. 2339f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner PHINode *PN = dyn_cast<PHINode>(ExitBB->begin()); 2349f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner if (!PN) continue; 235cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 2369f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner unsigned NumPreds = PN->getNumIncomingValues(); 237cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 2389f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // Iterate over all of the PHI nodes. 2399f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner BasicBlock::iterator BBI = ExitBB->begin(); 2409f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner while ((PN = dyn_cast<PHINode>(BBI++))) { 2413790fb0c036acaa4db50aff83dd8b3bf51f8af6aTorok Edwin if (PN->use_empty()) 2423790fb0c036acaa4db50aff83dd8b3bf51f8af6aTorok Edwin continue; // dead use, don't replace it 243814f2b2d1927a5397c0e923588527277b9f67d6bDan Gohman 244814f2b2d1927a5397c0e923588527277b9f67d6bDan Gohman // SCEV only supports integer expressions for now. 245814f2b2d1927a5397c0e923588527277b9f67d6bDan Gohman if (!PN->getType()->isIntegerTy() && !PN->getType()->isPointerTy()) 246814f2b2d1927a5397c0e923588527277b9f67d6bDan Gohman continue; 247814f2b2d1927a5397c0e923588527277b9f67d6bDan Gohman 24845a2d7d44ae697e28df383d31455145fb754ac58Dale Johannesen // It's necessary to tell ScalarEvolution about this explicitly so that 24945a2d7d44ae697e28df383d31455145fb754ac58Dale Johannesen // it can walk the def-use list and forget all SCEVs, as it may not be 25045a2d7d44ae697e28df383d31455145fb754ac58Dale Johannesen // watching the PHI itself. Once the new exit value is in place, there 25145a2d7d44ae697e28df383d31455145fb754ac58Dale Johannesen // may not be a def-use connection between the loop and every instruction 25245a2d7d44ae697e28df383d31455145fb754ac58Dale Johannesen // which got a SCEVAddRecExpr for that loop. 25345a2d7d44ae697e28df383d31455145fb754ac58Dale Johannesen SE->forgetValue(PN); 25445a2d7d44ae697e28df383d31455145fb754ac58Dale Johannesen 2559f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // Iterate over all of the values in all the PHI nodes. 2569f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner for (unsigned i = 0; i != NumPreds; ++i) { 2579f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // If the value being merged in is not integer or is not defined 2589f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // in the loop, skip it. 2599f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner Value *InVal = PN->getIncomingValue(i); 260814f2b2d1927a5397c0e923588527277b9f67d6bDan Gohman if (!isa<Instruction>(InVal)) 2619f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner continue; 2629f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner 2639f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // If this pred is for a subloop, not L itself, skip it. 264cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman if (LI->getLoopFor(PN->getIncomingBlock(i)) != L) 2659f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner continue; // The Block is in a subloop, skip it. 2669f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner 2679f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // Check that InVal is defined in the loop. 2689f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner Instruction *Inst = cast<Instruction>(InVal); 26992329c7fbe572892c17aa2d2542a10e3ea16132fDan Gohman if (!L->contains(Inst)) 2709f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner continue; 271cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 2729f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // Okay, this instruction has a user outside of the current loop 2739f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // and varies predictably *inside* the loop. Evaluate the value it 2749f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // contains when the loop exits, if possible. 2750bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *ExitValue = SE->getSCEVAtScope(Inst, L->getParentLoop()); 276d594e6f0345b3e1e4b640a7099596ca613da16d6Dan Gohman if (!ExitValue->isLoopInvariant(L)) 2779f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner continue; 2789f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner 2799f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner Changed = true; 2809f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner ++NumReplaced; 281cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 282667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman Value *ExitVal = Rewriter.expandCodeFor(ExitValue, PN->getType(), Inst); 283cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 284f67ef318aa29e7cc0c7de76349881959936d9eeeDavid Greene DEBUG(dbgs() << "INDVARS: RLEV: AfterLoopVal = " << *ExitVal << '\n' 285bdff548e4dd577a72094d57b282de4e765643b96Chris Lattner << " LoopVal = " << *Inst << "\n"); 2869caed5440d59dac4b388152fe8b993dc0491e5e9Chris Lattner 2879f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner PN->setIncomingValue(i, ExitVal); 288cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 28981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // If this instruction is dead now, delete it. 29081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman RecursivelyDeleteTriviallyDeadInstructions(Inst); 291cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 29265d1e2b6e74fcd370093cbe518ebc15cbc445ad4Dan Gohman if (NumPreds == 1) { 29365d1e2b6e74fcd370093cbe518ebc15cbc445ad4Dan Gohman // Completely replace a single-pred PHI. This is safe, because the 29465d1e2b6e74fcd370093cbe518ebc15cbc445ad4Dan Gohman // NewVal won't be variant in the loop, so we don't need an LCSSA phi 29565d1e2b6e74fcd370093cbe518ebc15cbc445ad4Dan Gohman // node anymore. 2969f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner PN->replaceAllUsesWith(ExitVal); 29781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman RecursivelyDeleteTriviallyDeadInstructions(PN); 298c9838f25d53d3dd7d38949ef6c28f2505a110f45Chris Lattner } 2994bd09d70cceb3851f7eb1c2f98338b3071d405f3Chris Lattner } 30065d1e2b6e74fcd370093cbe518ebc15cbc445ad4Dan Gohman if (NumPreds != 1) { 301667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman // Clone the PHI and delete the original one. This lets IVUsers and 302667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman // any other maps purge the original user from their records. 30350b6e33584f4e4cf75c7795b1f1a90731861c825Devang Patel PHINode *NewPN = cast<PHINode>(PN->clone()); 304667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman NewPN->takeName(PN); 305667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman NewPN->insertBefore(PN); 306667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman PN->replaceAllUsesWith(NewPN); 307667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman PN->eraseFromParent(); 308667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman } 309c9838f25d53d3dd7d38949ef6c28f2505a110f45Chris Lattner } 310c9838f25d53d3dd7d38949ef6c28f2505a110f45Chris Lattner } 311472fdf7090bb00af3a3f9dcbe22263120a527533Dan Gohman 312472fdf7090bb00af3a3f9dcbe22263120a527533Dan Gohman // The insertion point instruction may have been deleted; clear it out 313472fdf7090bb00af3a3f9dcbe22263120a527533Dan Gohman // so that the rewriter doesn't trip over it later. 314472fdf7090bb00af3a3f9dcbe22263120a527533Dan Gohman Rewriter.clearInsertPoint(); 31540bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner} 31615cad759fe2048ac5eb137c6bb0ab7287538677eChris Lattner 31760f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohmanvoid IndVarSimplify::RewriteNonIntegerIVs(Loop *L) { 3182d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman // First step. Check to see if there are any floating-point recurrences. 31940bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // If there are, change them into integer recurrences, permitting analysis by 32040bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // the SCEV routines. 32115cad759fe2048ac5eb137c6bb0ab7287538677eChris Lattner // 32240bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner BasicBlock *Header = L->getHeader(); 323fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 32481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman SmallVector<WeakVH, 8> PHIs; 32581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman for (BasicBlock::iterator I = Header->begin(); 32681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman PHINode *PN = dyn_cast<PHINode>(I); ++I) 32781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman PHIs.push_back(PN); 32881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 32981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman for (unsigned i = 0, e = PHIs.size(); i != e; ++i) 33081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (PHINode *PN = dyn_cast_or_null<PHINode>(PHIs[i])) 33181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman HandleFloatingPointIV(L, PN); 33215cad759fe2048ac5eb137c6bb0ab7287538677eChris Lattner 3332d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman // If the loop previously had floating-point IV, ScalarEvolution 33460f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman // may not have been able to compute a trip count. Now that we've done some 33560f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman // re-writing, the trip count may be computable. 33660f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman if (Changed) 3374c7279ac726e338400626fca5a09b5533426eb6aDan Gohman SE->forgetLoop(L); 338c671d892ab1d3d8fed18a61f66f3f3a86e73ebd9Dale Johannesen} 339c671d892ab1d3d8fed18a61f66f3f3a86e73ebd9Dale Johannesen 340931e345e76e75391d2a7c96530e305f802b5429dDan Gohmanvoid IndVarSimplify::EliminateIVComparisons() { 341931e345e76e75391d2a7c96530e305f802b5429dDan Gohman // Look for ICmp users. 342931e345e76e75391d2a7c96530e305f802b5429dDan Gohman for (IVUsers::iterator I = IU->begin(), E = IU->end(); I != E;) { 343931e345e76e75391d2a7c96530e305f802b5429dDan Gohman IVStrideUse &UI = *I++; 344931e345e76e75391d2a7c96530e305f802b5429dDan Gohman ICmpInst *ICmp = dyn_cast<ICmpInst>(UI.getUser()); 345931e345e76e75391d2a7c96530e305f802b5429dDan Gohman if (!ICmp) continue; 346931e345e76e75391d2a7c96530e305f802b5429dDan Gohman 347931e345e76e75391d2a7c96530e305f802b5429dDan Gohman bool Swapped = UI.getOperandValToReplace() == ICmp->getOperand(1); 348931e345e76e75391d2a7c96530e305f802b5429dDan Gohman ICmpInst::Predicate Pred = ICmp->getPredicate(); 349931e345e76e75391d2a7c96530e305f802b5429dDan Gohman if (Swapped) Pred = ICmpInst::getSwappedPredicate(Pred); 350931e345e76e75391d2a7c96530e305f802b5429dDan Gohman 351931e345e76e75391d2a7c96530e305f802b5429dDan Gohman // Get the SCEVs for the ICmp operands. 352931e345e76e75391d2a7c96530e305f802b5429dDan Gohman const SCEV *S = IU->getReplacementExpr(UI); 353931e345e76e75391d2a7c96530e305f802b5429dDan Gohman const SCEV *X = SE->getSCEV(ICmp->getOperand(!Swapped)); 354931e345e76e75391d2a7c96530e305f802b5429dDan Gohman 355931e345e76e75391d2a7c96530e305f802b5429dDan Gohman // Simplify unnecessary loops away. 356931e345e76e75391d2a7c96530e305f802b5429dDan Gohman const Loop *ICmpLoop = LI->getLoopFor(ICmp->getParent()); 357931e345e76e75391d2a7c96530e305f802b5429dDan Gohman S = SE->getSCEVAtScope(S, ICmpLoop); 358931e345e76e75391d2a7c96530e305f802b5429dDan Gohman X = SE->getSCEVAtScope(X, ICmpLoop); 359931e345e76e75391d2a7c96530e305f802b5429dDan Gohman 360931e345e76e75391d2a7c96530e305f802b5429dDan Gohman // If the condition is always true or always false, replace it with 361931e345e76e75391d2a7c96530e305f802b5429dDan Gohman // a constant value. 362931e345e76e75391d2a7c96530e305f802b5429dDan Gohman if (SE->isKnownPredicate(Pred, S, X)) 363931e345e76e75391d2a7c96530e305f802b5429dDan Gohman ICmp->replaceAllUsesWith(ConstantInt::getTrue(ICmp->getContext())); 364931e345e76e75391d2a7c96530e305f802b5429dDan Gohman else if (SE->isKnownPredicate(ICmpInst::getInversePredicate(Pred), S, X)) 365931e345e76e75391d2a7c96530e305f802b5429dDan Gohman ICmp->replaceAllUsesWith(ConstantInt::getFalse(ICmp->getContext())); 366931e345e76e75391d2a7c96530e305f802b5429dDan Gohman else 367931e345e76e75391d2a7c96530e305f802b5429dDan Gohman continue; 368931e345e76e75391d2a7c96530e305f802b5429dDan Gohman 369931e345e76e75391d2a7c96530e305f802b5429dDan Gohman DEBUG(dbgs() << "INDVARS: Eliminated comparison: " << *ICmp << '\n'); 370931e345e76e75391d2a7c96530e305f802b5429dDan Gohman ICmp->eraseFromParent(); 371931e345e76e75391d2a7c96530e305f802b5429dDan Gohman } 372931e345e76e75391d2a7c96530e305f802b5429dDan Gohman} 373931e345e76e75391d2a7c96530e305f802b5429dDan Gohman 374c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohmanbool IndVarSimplify::runOnLoop(Loop *L, LPPassManager &LPM) { 37581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman IU = &getAnalysis<IVUsers>(); 3765ee99979065d75605d150d7e567e4351024aae8fDevang Patel LI = &getAnalysis<LoopInfo>(); 3775ee99979065d75605d150d7e567e4351024aae8fDevang Patel SE = &getAnalysis<ScalarEvolution>(); 378de53dc03f5c1549f3176e979bbeeac965dfa5cbcDan Gohman DT = &getAnalysis<DominatorTree>(); 3795ee99979065d75605d150d7e567e4351024aae8fDevang Patel Changed = false; 38060f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman 3812d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman // If there are any floating-point recurrences, attempt to 38260f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman // transform them to use integer recurrences. 38360f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman RewriteNonIntegerIVs(L); 38460f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman 38581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman BasicBlock *ExitingBlock = L->getExitingBlock(); // may be null 3860bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *BackedgeTakenCount = SE->getBackedgeTakenCount(L); 3879caed5440d59dac4b388152fe8b993dc0491e5e9Chris Lattner 388667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman // Create a rewriter object which we'll use to transform the code with. 389667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman SCEVExpander Rewriter(*SE); 390667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman 39140bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // Check to see if this loop has a computable loop-invariant execution count. 39240bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // If so, this means that we can compute the final value of any expressions 39340bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // that are recurrent in the loop, and substitute the exit values from the 39440bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // loop into any instructions outside of the loop that use the final values of 39540bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // the current expressions. 396394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner // 39746bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman if (!isa<SCEVCouldNotCompute>(BackedgeTakenCount)) 398454d26dc43207ec537d843229db6f5e6a302e23dDan Gohman RewriteLoopExitValues(L, Rewriter); 39940bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner 40081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Compute the type of the largest recurrence expression, and decide whether 40181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // a canonical induction variable should be inserted. 402c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman const Type *LargestType = 0; 40381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman bool NeedCannIV = false; 40446bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman if (!isa<SCEVCouldNotCompute>(BackedgeTakenCount)) { 40546bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman LargestType = BackedgeTakenCount->getType(); 406af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman LargestType = SE->getEffectiveSCEVType(LargestType); 40781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // If we have a known trip count and a single exit block, we'll be 40881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // rewriting the loop exit test condition below, which requires a 40981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // canonical induction variable. 41081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (ExitingBlock) 41181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman NeedCannIV = true; 412f50af088f19f525f3d1026eb61db77e0037a9f43Chris Lattner } 413572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman for (IVUsers::const_iterator I = IU->begin(), E = IU->end(); I != E; ++I) { 414572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman const Type *Ty = 415572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman SE->getEffectiveSCEVType(I->getOperandValToReplace()->getType()); 416c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman if (!LargestType || 41781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman SE->getTypeSizeInBits(Ty) > 418af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman SE->getTypeSizeInBits(LargestType)) 41981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman LargestType = Ty; 420572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman NeedCannIV = true; 421500597a1c39e91a3020587318ed61e737b6c613aChris Lattner } 422394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner 423f451cb870efcf9e0302d25ed05f4cac6bb494e42Dan Gohman // Now that we know the largest of the induction variable expressions 42481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // in this loop, insert a canonical induction variable of the largest size. 425c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman Value *IndVar = 0; 42681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (NeedCannIV) { 42785669637139089eaed8def1583ac04266c9654e2Dan Gohman // Check to see if the loop already has any canonical-looking induction 42885669637139089eaed8def1583ac04266c9654e2Dan Gohman // variables. If any are present and wider than the planned canonical 42985669637139089eaed8def1583ac04266c9654e2Dan Gohman // induction variable, temporarily remove them, so that the Rewriter 43085669637139089eaed8def1583ac04266c9654e2Dan Gohman // doesn't attempt to reuse them. 43185669637139089eaed8def1583ac04266c9654e2Dan Gohman SmallVector<PHINode *, 2> OldCannIVs; 43285669637139089eaed8def1583ac04266c9654e2Dan Gohman while (PHINode *OldCannIV = L->getCanonicalInductionVariable()) { 4334d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman if (SE->getTypeSizeInBits(OldCannIV->getType()) > 4344d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman SE->getTypeSizeInBits(LargestType)) 4354d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman OldCannIV->removeFromParent(); 4364d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman else 43785669637139089eaed8def1583ac04266c9654e2Dan Gohman break; 43885669637139089eaed8def1583ac04266c9654e2Dan Gohman OldCannIVs.push_back(OldCannIV); 4394d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman } 4404d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman 441667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman IndVar = Rewriter.getOrInsertCanonicalInductionVariable(L, LargestType); 4424d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman 443c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman ++NumInserted; 444c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman Changed = true; 445f67ef318aa29e7cc0c7de76349881959936d9eeeDavid Greene DEBUG(dbgs() << "INDVARS: New CanIV: " << *IndVar << '\n'); 4464d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman 4474d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman // Now that the official induction variable is established, reinsert 44885669637139089eaed8def1583ac04266c9654e2Dan Gohman // any old canonical-looking variables after it so that the IR remains 44985669637139089eaed8def1583ac04266c9654e2Dan Gohman // consistent. They will be deleted as part of the dead-PHI deletion at 4504d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman // the end of the pass. 45185669637139089eaed8def1583ac04266c9654e2Dan Gohman while (!OldCannIVs.empty()) { 45285669637139089eaed8def1583ac04266c9654e2Dan Gohman PHINode *OldCannIV = OldCannIVs.pop_back_val(); 45385669637139089eaed8def1583ac04266c9654e2Dan Gohman OldCannIV->insertBefore(L->getHeader()->getFirstNonPHI()); 45485669637139089eaed8def1583ac04266c9654e2Dan Gohman } 455d19534add90a2a894af61523b830887097bb780bDan Gohman } 45640bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner 457c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman // If we have a trip count expression, rewrite the loop's exit condition 458c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman // using it. We can currently only handle loops with a single exit. 45981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman ICmpInst *NewICmp = 0; 46085669637139089eaed8def1583ac04266c9654e2Dan Gohman if (!isa<SCEVCouldNotCompute>(BackedgeTakenCount) && 46185669637139089eaed8def1583ac04266c9654e2Dan Gohman !BackedgeTakenCount->isZero() && 46285669637139089eaed8def1583ac04266c9654e2Dan Gohman ExitingBlock) { 46381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman assert(NeedCannIV && 46481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman "LinearFunctionTestReplace requires a canonical induction variable"); 465931e345e76e75391d2a7c96530e305f802b5429dDan Gohman 466c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman // Can't rewrite non-branch yet. 467931e345e76e75391d2a7c96530e305f802b5429dDan Gohman if (BranchInst *BI = dyn_cast<BranchInst>(ExitingBlock->getTerminator())) { 468931e345e76e75391d2a7c96530e305f802b5429dDan Gohman // Eliminate comparisons which are always true or always false, due to 469931e345e76e75391d2a7c96530e305f802b5429dDan Gohman // the known backedge-taken count. This may include comparisons which 470931e345e76e75391d2a7c96530e305f802b5429dDan Gohman // are currently controlling (part of) the loop exit, so we can only do 471931e345e76e75391d2a7c96530e305f802b5429dDan Gohman // it when we know we're going to insert our own loop exit code. 472931e345e76e75391d2a7c96530e305f802b5429dDan Gohman EliminateIVComparisons(); 473931e345e76e75391d2a7c96530e305f802b5429dDan Gohman 474931e345e76e75391d2a7c96530e305f802b5429dDan Gohman // Insert new loop exit code. 47581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman NewICmp = LinearFunctionTestReplace(L, BackedgeTakenCount, IndVar, 47681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman ExitingBlock, BI, Rewriter); 477931e345e76e75391d2a7c96530e305f802b5429dDan Gohman } 47881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman } 479c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman 4803d431384f05c9defc84f36eafe220415cc12ee93Torok Edwin // Rewrite IV-derived expressions. Clears the rewriter cache. 481454d26dc43207ec537d843229db6f5e6a302e23dDan Gohman RewriteIVExpressions(L, Rewriter); 482fcb81f5f4cbac61851b7dec403961cf88e614aa1Chris Lattner 483667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman // The Rewriter may not be used from this point on. 4843d431384f05c9defc84f36eafe220415cc12ee93Torok Edwin 48581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Loop-invariant instructions in the preheader that aren't used in the 48681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // loop may be sunk below the loop to reduce register pressure. 487667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman SinkUnusedInvariants(L); 48881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 48981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // For completeness, inform IVUsers of the IV use in the newly-created 49081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // loop exit test instruction. 49181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (NewICmp) 49281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman IU->AddUsersIfInteresting(cast<Instruction>(NewICmp->getOperand(0))); 49381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 49481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Clean up dead instructions. 4959fff2187a21f765ed87a25c48552a6942450f3e2Dan Gohman Changed |= DeleteDeadPHIs(L->getHeader()); 49681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Check a post-condition. 497bbf81d88116d23fb0776412b5916f7d0b8b3ca7eDan Gohman assert(L->isLCSSAForm(*DT) && "Indvars did not leave the loop in lcssa form!"); 49881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman return Changed; 49981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman} 50081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 501448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman// FIXME: It is an extremely bad idea to indvar substitute anything more 502448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman// complex than affine induction variables. Doing so will put expensive 503448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman// polynomial evaluations inside of the loop, and the str reduction pass 504448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman// currently can only reduce affine polynomials. For now just disable 505448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman// indvar subst on anything more complex than an affine addrec, unless 506448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman// it can be expanded to a trivial value. 507448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohmanstatic bool isSafe(const SCEV *S, const Loop *L) { 508448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman // Loop-invariant values are safe. 509448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman if (S->isLoopInvariant(L)) return true; 510448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman 511448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman // Affine addrecs are safe. Non-affine are not, because LSR doesn't know how 512448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman // to transform them into efficient code. 513448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) 514448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman return AR->isAffine(); 515448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman 516448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman // An add is safe it all its operands are safe. 517448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman if (const SCEVCommutativeExpr *Commutative = dyn_cast<SCEVCommutativeExpr>(S)) { 518448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman for (SCEVCommutativeExpr::op_iterator I = Commutative->op_begin(), 519448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman E = Commutative->op_end(); I != E; ++I) 520448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman if (!isSafe(*I, L)) return false; 521448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman return true; 522448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman } 523448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman 524448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman // A cast is safe if its operand is. 525448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman if (const SCEVCastExpr *C = dyn_cast<SCEVCastExpr>(S)) 526448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman return isSafe(C->getOperand(), L); 527448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman 528448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman // A udiv is safe if its operands are. 529448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman if (const SCEVUDivExpr *UD = dyn_cast<SCEVUDivExpr>(S)) 530448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman return isSafe(UD->getLHS(), L) && 531448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman isSafe(UD->getRHS(), L); 532448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman 533448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman // SCEVUnknown is always safe. 534448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman if (isa<SCEVUnknown>(S)) 535448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman return true; 536448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman 537448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman // Nothing else is safe. 538448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman return false; 539448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman} 540448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman 541454d26dc43207ec537d843229db6f5e6a302e23dDan Gohmanvoid IndVarSimplify::RewriteIVExpressions(Loop *L, SCEVExpander &Rewriter) { 54281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman SmallVector<WeakVH, 16> DeadInsts; 54381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 54481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Rewrite all induction variable expressions in terms of the canonical 54581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // induction variable. 54681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // 54781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // If there were induction variables of other sizes or offsets, manually 54881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // add the offsets to the primary induction variable and cast, avoiding 54981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // the need for the code evaluation methods to insert induction variables 55081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // of different sizes. 551572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman for (IVUsers::iterator UI = IU->begin(), E = IU->end(); UI != E; ++UI) { 552572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman Value *Op = UI->getOperandValToReplace(); 553572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman const Type *UseTy = Op->getType(); 554572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman Instruction *User = UI->getUser(); 555572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman 556572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // Compute the final addrec to expand into code. 557572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman const SCEV *AR = IU->getReplacementExpr(*UI); 558572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman 559572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // Evaluate the expression out of the loop, if possible. 560572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman if (!L->contains(UI->getUser())) { 561572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman const SCEV *ExitVal = SE->getSCEVAtScope(AR, L->getParentLoop()); 562572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman if (ExitVal->isLoopInvariant(L)) 563572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman AR = ExitVal; 56481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman } 565572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman 566572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // FIXME: It is an extremely bad idea to indvar substitute anything more 567572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // complex than affine induction variables. Doing so will put expensive 568572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // polynomial evaluations inside of the loop, and the str reduction pass 569572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // currently can only reduce affine polynomials. For now just disable 570572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // indvar subst on anything more complex than an affine addrec, unless 571572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // it can be expanded to a trivial value. 572448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman if (!isSafe(AR, L)) 573572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman continue; 574572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman 575572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // Determine the insertion point for this user. By default, insert 576572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // immediately before the user. The SCEVExpander class will automatically 577572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // hoist loop invariants out of the loop. For PHI nodes, there may be 578572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // multiple uses, so compute the nearest common dominator for the 579572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // incoming blocks. 580572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman Instruction *InsertPt = User; 581572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman if (PHINode *PHI = dyn_cast<PHINode>(InsertPt)) 582572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i) 583572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman if (PHI->getIncomingValue(i) == Op) { 584572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman if (InsertPt == User) 585572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman InsertPt = PHI->getIncomingBlock(i)->getTerminator(); 586572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman else 587572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman InsertPt = 588572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman DT->findNearestCommonDominator(InsertPt->getParent(), 589572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman PHI->getIncomingBlock(i)) 590572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman ->getTerminator(); 591572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman } 592572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman 593572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // Now expand it into actual Instructions and patch it into place. 594572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman Value *NewVal = Rewriter.expandCodeFor(AR, UseTy, InsertPt); 595572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman 596d7bfd0028b273f2e3935e8c7ff95db6fa2b21789Dan Gohman // Inform ScalarEvolution that this value is changing. The change doesn't 597d7bfd0028b273f2e3935e8c7ff95db6fa2b21789Dan Gohman // affect its value, but it does potentially affect which use lists the 598d7bfd0028b273f2e3935e8c7ff95db6fa2b21789Dan Gohman // value will be on after the replacement, which affects ScalarEvolution's 599d7bfd0028b273f2e3935e8c7ff95db6fa2b21789Dan Gohman // ability to walk use lists and drop dangling pointers when a value is 600d7bfd0028b273f2e3935e8c7ff95db6fa2b21789Dan Gohman // deleted. 601d7bfd0028b273f2e3935e8c7ff95db6fa2b21789Dan Gohman SE->forgetValue(User); 602d7bfd0028b273f2e3935e8c7ff95db6fa2b21789Dan Gohman 603572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // Patch the new value into place. 604572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman if (Op->hasName()) 605572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman NewVal->takeName(Op); 606572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman User->replaceUsesOfWith(Op, NewVal); 607572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman UI->setOperandValToReplace(NewVal); 608572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman DEBUG(dbgs() << "INDVARS: Rewrote IV '" << *AR << "' " << *Op << '\n' 609572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman << " into = " << *NewVal << "\n"); 610572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman ++NumRemoved; 611572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman Changed = true; 612572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman 613572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // The old value may be dead now. 614572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman DeadInsts.push_back(Op); 615500597a1c39e91a3020587318ed61e737b6c613aChris Lattner } 616ba4f3f6a419326df190599421fa149c90235cb72Chris Lattner 6173d431384f05c9defc84f36eafe220415cc12ee93Torok Edwin // Clear the rewriter cache, because values that are in the rewriter's cache 6183d431384f05c9defc84f36eafe220415cc12ee93Torok Edwin // can be deleted in the loop below, causing the AssertingVH in the cache to 6193d431384f05c9defc84f36eafe220415cc12ee93Torok Edwin // trigger. 6203d431384f05c9defc84f36eafe220415cc12ee93Torok Edwin Rewriter.clear(); 62181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Now that we're done iterating through lists, clean up any instructions 62281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // which are now dead. 623a10756ee657a4d43a48cca5c166919093930ed6bDan Gohman while (!DeadInsts.empty()) 624a10756ee657a4d43a48cca5c166919093930ed6bDan Gohman if (Instruction *Inst = 625a10756ee657a4d43a48cca5c166919093930ed6bDan Gohman dyn_cast_or_null<Instruction>(DeadInsts.pop_back_val())) 62681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman RecursivelyDeleteTriviallyDeadInstructions(Inst); 62781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman} 62881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 62981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman/// If there's a single exit block, sink any loop-invariant values that 63081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman/// were defined in the preheader but not used inside the loop into the 63181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman/// exit block to reduce register pressure in the loop. 632667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohmanvoid IndVarSimplify::SinkUnusedInvariants(Loop *L) { 63381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman BasicBlock *ExitBlock = L->getExitBlock(); 63481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (!ExitBlock) return; 63581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 63681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman BasicBlock *Preheader = L->getLoopPreheader(); 63703e896bd6073efc4523d8bcd0239d6ed62126db7Dan Gohman if (!Preheader) return; 63803e896bd6073efc4523d8bcd0239d6ed62126db7Dan Gohman 63903e896bd6073efc4523d8bcd0239d6ed62126db7Dan Gohman Instruction *InsertPt = ExitBlock->getFirstNonPHI(); 64081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman BasicBlock::iterator I = Preheader->getTerminator(); 64181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman while (I != Preheader->begin()) { 64281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman --I; 643667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman // New instructions were inserted at the end of the preheader. 644667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman if (isa<PHINode>(I)) 64581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman break; 64687a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling 6470c77db32dd8ae10b5a26d60718dbe03dc2745888Eli Friedman // Don't move instructions which might have side effects, since the side 64887a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling // effects need to complete before instructions inside the loop. Also don't 64987a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling // move instructions which might read memory, since the loop may modify 65087a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling // memory. Note that it's okay if the instruction might have undefined 65187a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling // behavior: LoopSimplify guarantees that the preheader dominates the exit 65287a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling // block. 6530c77db32dd8ae10b5a26d60718dbe03dc2745888Eli Friedman if (I->mayHaveSideEffects() || I->mayReadFromMemory()) 654667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman continue; 65587a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling 6567b9f6b1b21bc0b06f3c72beae51e9db631319503Devang Patel // Skip debug info intrinsics. 6577b9f6b1b21bc0b06f3c72beae51e9db631319503Devang Patel if (isa<DbgInfoIntrinsic>(I)) 6587b9f6b1b21bc0b06f3c72beae51e9db631319503Devang Patel continue; 65987a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling 66076f497a351c562f366b5e93c27d3f1652fb48ff4Dan Gohman // Don't sink static AllocaInsts out of the entry block, which would 66176f497a351c562f366b5e93c27d3f1652fb48ff4Dan Gohman // turn them into dynamic allocas! 66276f497a351c562f366b5e93c27d3f1652fb48ff4Dan Gohman if (AllocaInst *AI = dyn_cast<AllocaInst>(I)) 66376f497a351c562f366b5e93c27d3f1652fb48ff4Dan Gohman if (AI->isStaticAlloca()) 66476f497a351c562f366b5e93c27d3f1652fb48ff4Dan Gohman continue; 66587a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling 66681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Determine if there is a use in or before the loop (direct or 66781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // otherwise). 66881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman bool UsedInLoop = false; 66981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman for (Value::use_iterator UI = I->use_begin(), UE = I->use_end(); 67081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman UI != UE; ++UI) { 67181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman BasicBlock *UseBB = cast<Instruction>(UI)->getParent(); 67281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (PHINode *P = dyn_cast<PHINode>(UI)) { 67381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman unsigned i = 67481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman PHINode::getIncomingValueNumForOperand(UI.getOperandNo()); 67581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman UseBB = P->getIncomingBlock(i); 67681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman } 67781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (UseBB == Preheader || L->contains(UseBB)) { 67881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman UsedInLoop = true; 67981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman break; 68081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman } 68181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman } 68287a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling 68381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // If there is, the def must remain in the preheader. 68481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (UsedInLoop) 68581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman continue; 68687a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling 68781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Otherwise, sink it to the exit block. 68881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman Instruction *ToMove = I; 68981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman bool Done = false; 69087a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling 69187a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling if (I != Preheader->begin()) { 69287a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling // Skip debug info intrinsics. 69387a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling do { 69487a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling --I; 69587a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling } while (isa<DbgInfoIntrinsic>(I) && I != Preheader->begin()); 69687a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling 69787a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling if (isa<DbgInfoIntrinsic>(I) && I == Preheader->begin()) 69887a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling Done = true; 69987a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling } else { 70081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman Done = true; 70187a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling } 70287a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling 703667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman ToMove->moveBefore(InsertPt); 70487a10f5b2fc26e418a7bde45136843aac4c7a7e6Bill Wendling if (Done) break; 705667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman InsertPt = ToMove; 70681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman } 70781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman} 70881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 709bbb91498da1a4dc77332bf93d7c13060f0c63a70Chris Lattner/// ConvertToSInt - Convert APF to an integer, if possible. 710bbb91498da1a4dc77332bf93d7c13060f0c63a70Chris Lattnerstatic bool ConvertToSInt(const APFloat &APF, int64_t &IntVal) { 711cd40233429fce385ae4b22301ce705273a6951a1Devang Patel bool isExact = false; 712794a7dbce030f93315b1305f83a374232f09bba5Evan Cheng if (&APF.getSemantics() == &APFloat::PPCDoubleDouble) 713794a7dbce030f93315b1305f83a374232f09bba5Evan Cheng return false; 714bbb91498da1a4dc77332bf93d7c13060f0c63a70Chris Lattner // See if we can convert this to an int64_t 715bbb91498da1a4dc77332bf93d7c13060f0c63a70Chris Lattner uint64_t UIntVal; 716bbb91498da1a4dc77332bf93d7c13060f0c63a70Chris Lattner if (APF.convertToInteger(&UIntVal, 64, true, APFloat::rmTowardZero, 717bbb91498da1a4dc77332bf93d7c13060f0c63a70Chris Lattner &isExact) != APFloat::opOK || !isExact) 718cd40233429fce385ae4b22301ce705273a6951a1Devang Patel return false; 719bbb91498da1a4dc77332bf93d7c13060f0c63a70Chris Lattner IntVal = UIntVal; 720cd40233429fce385ae4b22301ce705273a6951a1Devang Patel return true; 721cd40233429fce385ae4b22301ce705273a6951a1Devang Patel} 722cd40233429fce385ae4b22301ce705273a6951a1Devang Patel 72358d43d4a41b21085c063bdd21a2abb68056e2a6fDevang Patel/// HandleFloatingPointIV - If the loop has floating induction variable 72458d43d4a41b21085c063bdd21a2abb68056e2a6fDevang Patel/// then insert corresponding integer induction variable if possible. 72584e3515974407a606289c6e762a0419723b7918fDevang Patel/// For example, 72684e3515974407a606289c6e762a0419723b7918fDevang Patel/// for(double i = 0; i < 10000; ++i) 72784e3515974407a606289c6e762a0419723b7918fDevang Patel/// bar(i) 72884e3515974407a606289c6e762a0419723b7918fDevang Patel/// is converted into 72984e3515974407a606289c6e762a0419723b7918fDevang Patel/// for(int i = 0; i < 10000; ++i) 73084e3515974407a606289c6e762a0419723b7918fDevang Patel/// bar((double)i); 73184e3515974407a606289c6e762a0419723b7918fDevang Patel/// 732c91961e31b2a1cae655928e20b83cb6a457fdcd4Chris Lattnervoid IndVarSimplify::HandleFloatingPointIV(Loop *L, PHINode *PN) { 733c91961e31b2a1cae655928e20b83cb6a457fdcd4Chris Lattner unsigned IncomingEdge = L->contains(PN->getIncomingBlock(0)); 73484e3515974407a606289c6e762a0419723b7918fDevang Patel unsigned BackEdge = IncomingEdge^1; 735cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 73684e3515974407a606289c6e762a0419723b7918fDevang Patel // Check incoming value. 737c4f7e8061de19172d4c3f70a80447505b792e450Chris Lattner ConstantFP *InitValueVal = 738c91961e31b2a1cae655928e20b83cb6a457fdcd4Chris Lattner dyn_cast<ConstantFP>(PN->getIncomingValue(IncomingEdge)); 73996fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner 740bbb91498da1a4dc77332bf93d7c13060f0c63a70Chris Lattner int64_t InitValue; 74196fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner if (!InitValueVal || !ConvertToSInt(InitValueVal->getValueAPF(), InitValue)) 742cd40233429fce385ae4b22301ce705273a6951a1Devang Patel return; 743cd40233429fce385ae4b22301ce705273a6951a1Devang Patel 744c91961e31b2a1cae655928e20b83cb6a457fdcd4Chris Lattner // Check IV increment. Reject this PN if increment operation is not 745cd40233429fce385ae4b22301ce705273a6951a1Devang Patel // an add or increment value can not be represented by an integer. 746cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman BinaryOperator *Incr = 747c91961e31b2a1cae655928e20b83cb6a457fdcd4Chris Lattner dyn_cast<BinaryOperator>(PN->getIncomingValue(BackEdge)); 74807aa76ad939e053c1992a03cbcb16aff74f26651Chris Lattner if (Incr == 0 || Incr->getOpcode() != Instruction::FAdd) return; 74907aa76ad939e053c1992a03cbcb16aff74f26651Chris Lattner 75007aa76ad939e053c1992a03cbcb16aff74f26651Chris Lattner // If this is not an add of the PHI with a constantfp, or if the constant fp 75107aa76ad939e053c1992a03cbcb16aff74f26651Chris Lattner // is not an integer, bail out. 752c4f7e8061de19172d4c3f70a80447505b792e450Chris Lattner ConstantFP *IncValueVal = dyn_cast<ConstantFP>(Incr->getOperand(1)); 75396fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner int64_t IncValue; 754c91961e31b2a1cae655928e20b83cb6a457fdcd4Chris Lattner if (IncValueVal == 0 || Incr->getOperand(0) != PN || 75596fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner !ConvertToSInt(IncValueVal->getValueAPF(), IncValue)) 756cd40233429fce385ae4b22301ce705273a6951a1Devang Patel return; 757cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 758c91961e31b2a1cae655928e20b83cb6a457fdcd4Chris Lattner // Check Incr uses. One user is PN and the other user is an exit condition 75907aa76ad939e053c1992a03cbcb16aff74f26651Chris Lattner // used by the conditional terminator. 76084e3515974407a606289c6e762a0419723b7918fDevang Patel Value::use_iterator IncrUse = Incr->use_begin(); 76184e3515974407a606289c6e762a0419723b7918fDevang Patel Instruction *U1 = cast<Instruction>(IncrUse++); 76284e3515974407a606289c6e762a0419723b7918fDevang Patel if (IncrUse == Incr->use_end()) return; 76384e3515974407a606289c6e762a0419723b7918fDevang Patel Instruction *U2 = cast<Instruction>(IncrUse++); 76484e3515974407a606289c6e762a0419723b7918fDevang Patel if (IncrUse != Incr->use_end()) return; 765cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 76607aa76ad939e053c1992a03cbcb16aff74f26651Chris Lattner // Find exit condition, which is an fcmp. If it doesn't exist, or if it isn't 76707aa76ad939e053c1992a03cbcb16aff74f26651Chris Lattner // only used by a branch, we can't transform it. 768ca703bd56ba1f717b3735c6889334c319ca005b1Chris Lattner FCmpInst *Compare = dyn_cast<FCmpInst>(U1); 769ca703bd56ba1f717b3735c6889334c319ca005b1Chris Lattner if (!Compare) 770ca703bd56ba1f717b3735c6889334c319ca005b1Chris Lattner Compare = dyn_cast<FCmpInst>(U2); 771ca703bd56ba1f717b3735c6889334c319ca005b1Chris Lattner if (Compare == 0 || !Compare->hasOneUse() || 772ca703bd56ba1f717b3735c6889334c319ca005b1Chris Lattner !isa<BranchInst>(Compare->use_back())) 77307aa76ad939e053c1992a03cbcb16aff74f26651Chris Lattner return; 774c4f7e8061de19172d4c3f70a80447505b792e450Chris Lattner 775ca703bd56ba1f717b3735c6889334c319ca005b1Chris Lattner BranchInst *TheBr = cast<BranchInst>(Compare->use_back()); 77684e3515974407a606289c6e762a0419723b7918fDevang Patel 777d52c072777b9c9a9df9041b8b6cd199df7e43394Chris Lattner // We need to verify that the branch actually controls the iteration count 778d52c072777b9c9a9df9041b8b6cd199df7e43394Chris Lattner // of the loop. If not, the new IV can overflow and no one will notice. 779d52c072777b9c9a9df9041b8b6cd199df7e43394Chris Lattner // The branch block must be in the loop and one of the successors must be out 780d52c072777b9c9a9df9041b8b6cd199df7e43394Chris Lattner // of the loop. 781d52c072777b9c9a9df9041b8b6cd199df7e43394Chris Lattner assert(TheBr->isConditional() && "Can't use fcmp if not conditional"); 782d52c072777b9c9a9df9041b8b6cd199df7e43394Chris Lattner if (!L->contains(TheBr->getParent()) || 783d52c072777b9c9a9df9041b8b6cd199df7e43394Chris Lattner (L->contains(TheBr->getSuccessor(0)) && 784d52c072777b9c9a9df9041b8b6cd199df7e43394Chris Lattner L->contains(TheBr->getSuccessor(1)))) 785d52c072777b9c9a9df9041b8b6cd199df7e43394Chris Lattner return; 78696fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner 78796fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner 78807aa76ad939e053c1992a03cbcb16aff74f26651Chris Lattner // If it isn't a comparison with an integer-as-fp (the exit value), we can't 78907aa76ad939e053c1992a03cbcb16aff74f26651Chris Lattner // transform it. 790ca703bd56ba1f717b3735c6889334c319ca005b1Chris Lattner ConstantFP *ExitValueVal = dyn_cast<ConstantFP>(Compare->getOperand(1)); 791bbb91498da1a4dc77332bf93d7c13060f0c63a70Chris Lattner int64_t ExitValue; 792bbb91498da1a4dc77332bf93d7c13060f0c63a70Chris Lattner if (ExitValueVal == 0 || 793bbb91498da1a4dc77332bf93d7c13060f0c63a70Chris Lattner !ConvertToSInt(ExitValueVal->getValueAPF(), ExitValue)) 79484e3515974407a606289c6e762a0419723b7918fDevang Patel return; 795bbb91498da1a4dc77332bf93d7c13060f0c63a70Chris Lattner 79684e3515974407a606289c6e762a0419723b7918fDevang Patel // Find new predicate for integer comparison. 79784e3515974407a606289c6e762a0419723b7918fDevang Patel CmpInst::Predicate NewPred = CmpInst::BAD_ICMP_PREDICATE; 798ca703bd56ba1f717b3735c6889334c319ca005b1Chris Lattner switch (Compare->getPredicate()) { 799c4f7e8061de19172d4c3f70a80447505b792e450Chris Lattner default: return; // Unknown comparison. 80084e3515974407a606289c6e762a0419723b7918fDevang Patel case CmpInst::FCMP_OEQ: 801c4f7e8061de19172d4c3f70a80447505b792e450Chris Lattner case CmpInst::FCMP_UEQ: NewPred = CmpInst::ICMP_EQ; break; 80296fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner case CmpInst::FCMP_ONE: 80396fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner case CmpInst::FCMP_UNE: NewPred = CmpInst::ICMP_NE; break; 80484e3515974407a606289c6e762a0419723b7918fDevang Patel case CmpInst::FCMP_OGT: 805a40e4a0c8abbfe55d25a77e4e98508e43ed1c3aeChris Lattner case CmpInst::FCMP_UGT: NewPred = CmpInst::ICMP_SGT; break; 80684e3515974407a606289c6e762a0419723b7918fDevang Patel case CmpInst::FCMP_OGE: 807a40e4a0c8abbfe55d25a77e4e98508e43ed1c3aeChris Lattner case CmpInst::FCMP_UGE: NewPred = CmpInst::ICMP_SGE; break; 80884e3515974407a606289c6e762a0419723b7918fDevang Patel case CmpInst::FCMP_OLT: 80943b85273ee11536c81b14dca0114cd8b9407db8eChris Lattner case CmpInst::FCMP_ULT: NewPred = CmpInst::ICMP_SLT; break; 81084e3515974407a606289c6e762a0419723b7918fDevang Patel case CmpInst::FCMP_OLE: 81143b85273ee11536c81b14dca0114cd8b9407db8eChris Lattner case CmpInst::FCMP_ULE: NewPred = CmpInst::ICMP_SLE; break; 81258d43d4a41b21085c063bdd21a2abb68056e2a6fDevang Patel } 81396fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner 81496fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner // We convert the floating point induction variable to a signed i32 value if 81596fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner // we can. This is only safe if the comparison will not overflow in a way 81696fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner // that won't be trapped by the integer equivalent operations. Check for this 81796fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner // now. 81896fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner // TODO: We could use i64 if it is native and the range requires it. 81996fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner 82096fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner // The start/stride/exit values must all fit in signed i32. 82196fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner if (!isInt<32>(InitValue) || !isInt<32>(IncValue) || !isInt<32>(ExitValue)) 82296fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner return; 82396fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner 82496fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner // If not actually striding (add x, 0.0), avoid touching the code. 82596fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner if (IncValue == 0) 82696fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner return; 82796fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner 82896fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner // Positive and negative strides have different safety conditions. 82996fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner if (IncValue > 0) { 83096fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner // If we have a positive stride, we require the init to be less than the 83196fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner // exit value and an equality or less than comparison. 83296fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner if (InitValue >= ExitValue || 83396fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner NewPred == CmpInst::ICMP_SGT || NewPred == CmpInst::ICMP_SGE) 83496fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner return; 83596fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner 83696fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner uint32_t Range = uint32_t(ExitValue-InitValue); 83796fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner if (NewPred == CmpInst::ICMP_SLE) { 83896fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner // Normalize SLE -> SLT, check for infinite loop. 83996fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner if (++Range == 0) return; // Range overflows. 84096fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner } 84196fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner 84296fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner unsigned Leftover = Range % uint32_t(IncValue); 84396fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner 84496fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner // If this is an equality comparison, we require that the strided value 84596fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner // exactly land on the exit value, otherwise the IV condition will wrap 84696fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner // around and do things the fp IV wouldn't. 84796fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner if ((NewPred == CmpInst::ICMP_EQ || NewPred == CmpInst::ICMP_NE) && 84896fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner Leftover != 0) 84996fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner return; 85096fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner 85196fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner // If the stride would wrap around the i32 before exiting, we can't 85296fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner // transform the IV. 85396fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner if (Leftover != 0 && int32_t(ExitValue+IncValue) < ExitValue) 85496fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner return; 85596fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner 85696fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner } else { 85796fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner // If we have a negative stride, we require the init to be greater than the 85896fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner // exit value and an equality or greater than comparison. 85996fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner if (InitValue >= ExitValue || 86096fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner NewPred == CmpInst::ICMP_SLT || NewPred == CmpInst::ICMP_SLE) 86196fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner return; 86296fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner 86396fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner uint32_t Range = uint32_t(InitValue-ExitValue); 86496fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner if (NewPred == CmpInst::ICMP_SGE) { 86596fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner // Normalize SGE -> SGT, check for infinite loop. 86696fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner if (++Range == 0) return; // Range overflows. 86796fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner } 86896fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner 86996fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner unsigned Leftover = Range % uint32_t(-IncValue); 87096fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner 87196fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner // If this is an equality comparison, we require that the strided value 87296fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner // exactly land on the exit value, otherwise the IV condition will wrap 87396fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner // around and do things the fp IV wouldn't. 87496fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner if ((NewPred == CmpInst::ICMP_EQ || NewPred == CmpInst::ICMP_NE) && 87596fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner Leftover != 0) 87696fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner return; 87796fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner 87896fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner // If the stride would wrap around the i32 before exiting, we can't 87996fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner // transform the IV. 88096fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner if (Leftover != 0 && int32_t(ExitValue+IncValue) > ExitValue) 88196fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner return; 88296fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner } 88396fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner 88496fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner const IntegerType *Int32Ty = Type::getInt32Ty(PN->getContext()); 885cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 886bbb91498da1a4dc77332bf93d7c13060f0c63a70Chris Lattner // Insert new integer induction variable. 887c91961e31b2a1cae655928e20b83cb6a457fdcd4Chris Lattner PHINode *NewPHI = PHINode::Create(Int32Ty, PN->getName()+".int", PN); 888c4f7e8061de19172d4c3f70a80447505b792e450Chris Lattner NewPHI->addIncoming(ConstantInt::get(Int32Ty, InitValue), 889c91961e31b2a1cae655928e20b83cb6a457fdcd4Chris Lattner PN->getIncomingBlock(IncomingEdge)); 89084e3515974407a606289c6e762a0419723b7918fDevang Patel 891c4f7e8061de19172d4c3f70a80447505b792e450Chris Lattner Value *NewAdd = 89296fd76638b6be492c5e470c3b9d5ca12628be5a9Chris Lattner BinaryOperator::CreateAdd(NewPHI, ConstantInt::get(Int32Ty, IncValue), 893c4f7e8061de19172d4c3f70a80447505b792e450Chris Lattner Incr->getName()+".int", Incr); 894c91961e31b2a1cae655928e20b83cb6a457fdcd4Chris Lattner NewPHI->addIncoming(NewAdd, PN->getIncomingBlock(BackEdge)); 89584e3515974407a606289c6e762a0419723b7918fDevang Patel 896ca703bd56ba1f717b3735c6889334c319ca005b1Chris Lattner ICmpInst *NewCompare = new ICmpInst(TheBr, NewPred, NewAdd, 897ca703bd56ba1f717b3735c6889334c319ca005b1Chris Lattner ConstantInt::get(Int32Ty, ExitValue), 898ca703bd56ba1f717b3735c6889334c319ca005b1Chris Lattner Compare->getName()); 899cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 900c91961e31b2a1cae655928e20b83cb6a457fdcd4Chris Lattner // In the following deletions, PN may become dead and may be deleted. 90181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Use a WeakVH to observe whether this happens. 902c91961e31b2a1cae655928e20b83cb6a457fdcd4Chris Lattner WeakVH WeakPH = PN; 90381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 904ca703bd56ba1f717b3735c6889334c319ca005b1Chris Lattner // Delete the old floating point exit comparison. The branch starts using the 905ca703bd56ba1f717b3735c6889334c319ca005b1Chris Lattner // new comparison. 906ca703bd56ba1f717b3735c6889334c319ca005b1Chris Lattner NewCompare->takeName(Compare); 907ca703bd56ba1f717b3735c6889334c319ca005b1Chris Lattner Compare->replaceAllUsesWith(NewCompare); 908ca703bd56ba1f717b3735c6889334c319ca005b1Chris Lattner RecursivelyDeleteTriviallyDeadInstructions(Compare); 909cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 910ca703bd56ba1f717b3735c6889334c319ca005b1Chris Lattner // Delete the old floating point increment. 9119e9a0d5fc26878e51a58a8b57900fcbf952c2691Owen Anderson Incr->replaceAllUsesWith(UndefValue::get(Incr->getType())); 91281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman RecursivelyDeleteTriviallyDeadInstructions(Incr); 91381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 91470c0d4f7eb9c14bccc8a585be4086712e46bfbdbChris Lattner // If the FP induction variable still has uses, this is because something else 91570c0d4f7eb9c14bccc8a585be4086712e46bfbdbChris Lattner // in the loop uses its value. In order to canonicalize the induction 91670c0d4f7eb9c14bccc8a585be4086712e46bfbdbChris Lattner // variable, we chose to eliminate the IV and rewrite it in terms of an 91770c0d4f7eb9c14bccc8a585be4086712e46bfbdbChris Lattner // int->fp cast. 91870c0d4f7eb9c14bccc8a585be4086712e46bfbdbChris Lattner // 91970c0d4f7eb9c14bccc8a585be4086712e46bfbdbChris Lattner // We give preference to sitofp over uitofp because it is faster on most 92070c0d4f7eb9c14bccc8a585be4086712e46bfbdbChris Lattner // platforms. 92170c0d4f7eb9c14bccc8a585be4086712e46bfbdbChris Lattner if (WeakPH) { 922a40e4a0c8abbfe55d25a77e4e98508e43ed1c3aeChris Lattner Value *Conv = new SIToFPInst(NewPHI, PN->getType(), "indvar.conv", 923a40e4a0c8abbfe55d25a77e4e98508e43ed1c3aeChris Lattner PN->getParent()->getFirstNonPHI()); 924a40e4a0c8abbfe55d25a77e4e98508e43ed1c3aeChris Lattner PN->replaceAllUsesWith(Conv); 925c91961e31b2a1cae655928e20b83cb6a457fdcd4Chris Lattner RecursivelyDeleteTriviallyDeadInstructions(PN); 926cd40233429fce385ae4b22301ce705273a6951a1Devang Patel } 92758d43d4a41b21085c063bdd21a2abb68056e2a6fDevang Patel 92881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Add a new IVUsers entry for the newly-created integer PHI. 92981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman IU->AddUsersIfInteresting(NewPHI); 93081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman} 931