IndVarSimplify.cpp revision 85669637139089eaed8def1583ac04266c9654e2
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" 46d672ecb0178c6247a5eaa5b0fb0c3b23cd25bd7cOwen Anderson#include "llvm/LLVMContext.h" 4740bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner#include "llvm/Type.h" 4881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman#include "llvm/Analysis/Dominators.h" 4981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman#include "llvm/Analysis/IVUsers.h" 5036f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman#include "llvm/Analysis/ScalarEvolutionExpander.h" 5147df12d80db90e125e9f2ff764286ee11665476dJohn Criswell#include "llvm/Analysis/LoopInfo.h" 525ee99979065d75605d150d7e567e4351024aae8fDevang Patel#include "llvm/Analysis/LoopPass.h" 53455889aa79e3463a4b0f2161e3d9d72a683268b6Chris Lattner#include "llvm/Support/CFG.h" 54bdff548e4dd577a72094d57b282de4e765643b96Chris Lattner#include "llvm/Support/CommandLine.h" 55ee4f13a9046c380725cdeab62d57722db375c473Chris Lattner#include "llvm/Support/Debug.h" 56bdff548e4dd577a72094d57b282de4e765643b96Chris Lattner#include "llvm/Support/raw_ostream.h" 5747df12d80db90e125e9f2ff764286ee11665476dJohn Criswell#include "llvm/Transforms/Utils/Local.h" 5881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman#include "llvm/Transforms/Utils/BasicBlockUtils.h" 59a54b7cbd452b3adb2f51346140d996b29c2cdb30Reid Spencer#include "llvm/ADT/SmallVector.h" 60551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/Statistic.h" 6181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman#include "llvm/ADT/STLExtras.h" 6247df12d80db90e125e9f2ff764286ee11665476dJohn Criswellusing namespace llvm; 63d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 640e5f499638c8d277b9dc4a4385712177c53b5681Chris LattnerSTATISTIC(NumRemoved , "Number of aux indvars removed"); 650e5f499638c8d277b9dc4a4385712177c53b5681Chris LattnerSTATISTIC(NumInserted, "Number of canonical indvars added"); 660e5f499638c8d277b9dc4a4385712177c53b5681Chris LattnerSTATISTIC(NumReplaced, "Number of exit values replaced"); 670e5f499638c8d277b9dc4a4385712177c53b5681Chris LattnerSTATISTIC(NumLFTR , "Number of loop exit tests replaced"); 683324e718bc9ac2ede08a14c325848b576849542bChris Lattner 690e5f499638c8d277b9dc4a4385712177c53b5681Chris Lattnernamespace { 703e8b6631e67e01e4960a7ba4668a50c596607473Chris Lattner class IndVarSimplify : public LoopPass { 7181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman IVUsers *IU; 7240bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner LoopInfo *LI; 7340bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner ScalarEvolution *SE; 74de53dc03f5c1549f3176e979bbeeac965dfa5cbcDan Gohman DominatorTree *DT; 7515cad759fe2048ac5eb137c6bb0ab7287538677eChris Lattner bool Changed; 763324e718bc9ac2ede08a14c325848b576849542bChris Lattner public: 77794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel 785668cf77a77493ec9f2a9b33f08125e885c8e4cfDan Gohman static char ID; // Pass identification, replacement for typeid 795668cf77a77493ec9f2a9b33f08125e885c8e4cfDan Gohman IndVarSimplify() : LoopPass(&ID) {} 80794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel 815668cf77a77493ec9f2a9b33f08125e885c8e4cfDan Gohman virtual bool runOnLoop(Loop *L, LPPassManager &LPM); 8260f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman 835668cf77a77493ec9f2a9b33f08125e885c8e4cfDan Gohman virtual void getAnalysisUsage(AnalysisUsage &AU) const { 845668cf77a77493ec9f2a9b33f08125e885c8e4cfDan Gohman AU.addRequired<DominatorTree>(); 855668cf77a77493ec9f2a9b33f08125e885c8e4cfDan Gohman AU.addRequired<LoopInfo>(); 865668cf77a77493ec9f2a9b33f08125e885c8e4cfDan Gohman AU.addRequired<ScalarEvolution>(); 875668cf77a77493ec9f2a9b33f08125e885c8e4cfDan Gohman AU.addRequiredID(LoopSimplifyID); 885668cf77a77493ec9f2a9b33f08125e885c8e4cfDan Gohman AU.addRequiredID(LCSSAID); 895668cf77a77493ec9f2a9b33f08125e885c8e4cfDan Gohman AU.addRequired<IVUsers>(); 905668cf77a77493ec9f2a9b33f08125e885c8e4cfDan Gohman AU.addPreserved<ScalarEvolution>(); 915668cf77a77493ec9f2a9b33f08125e885c8e4cfDan Gohman AU.addPreservedID(LoopSimplifyID); 925668cf77a77493ec9f2a9b33f08125e885c8e4cfDan Gohman AU.addPreservedID(LCSSAID); 935668cf77a77493ec9f2a9b33f08125e885c8e4cfDan Gohman AU.addPreserved<IVUsers>(); 945668cf77a77493ec9f2a9b33f08125e885c8e4cfDan Gohman AU.setPreservesCFG(); 955668cf77a77493ec9f2a9b33f08125e885c8e4cfDan Gohman } 963324e718bc9ac2ede08a14c325848b576849542bChris Lattner 9740bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner private: 985ee99979065d75605d150d7e567e4351024aae8fDevang Patel 9960f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman void RewriteNonIntegerIVs(Loop *L); 10060f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman 1010bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman ICmpInst *LinearFunctionTestReplace(Loop *L, const SCEV *BackedgeTakenCount, 102a575871884b247b0946290876ac7d4657b384cf9Dan Gohman Value *IndVar, 103c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman BasicBlock *ExitingBlock, 104c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman BranchInst *BI, 10515cab2817b8f63fec0148609278bc2c1e05abb50Dan Gohman SCEVExpander &Rewriter); 106454d26dc43207ec537d843229db6f5e6a302e23dDan Gohman void RewriteLoopExitValues(Loop *L, SCEVExpander &Rewriter); 10740bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner 108454d26dc43207ec537d843229db6f5e6a302e23dDan Gohman void RewriteIVExpressions(Loop *L, SCEVExpander &Rewriter); 109d22a849282c45bbf7eb1734c274294d81e49e3a8Devang Patel 110667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman void SinkUnusedInvariants(Loop *L); 11181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 11281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman void HandleFloatingPointIV(Loop *L, PHINode *PH); 1133324e718bc9ac2ede08a14c325848b576849542bChris Lattner }; 1145e76140536ba66fadeced1cd892f79616f407e3cChris Lattner} 115394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner 116844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanchar IndVarSimplify::ID = 0; 117844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanstatic RegisterPass<IndVarSimplify> 118844731a7f1909f55935e3514c9e713a62d67662eDan GohmanX("indvars", "Canonicalize Induction Variables"); 119844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 120394f0441e06dafca29f0752cf400990a5b8fe4b1Daniel DunbarPass *llvm::createIndVarSimplifyPass() { 1213324e718bc9ac2ede08a14c325848b576849542bChris Lattner return new IndVarSimplify(); 122394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner} 123394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner 12440bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner/// LinearFunctionTestReplace - This method rewrites the exit condition of the 12559fdaeeae8f183e18bb6ad5c382ca23e28e6aaf6Chris Lattner/// loop to be a canonical != comparison against the incremented loop induction 12659fdaeeae8f183e18bb6ad5c382ca23e28e6aaf6Chris Lattner/// variable. This pass is able to rewrite the exit tests of any loop where the 12759fdaeeae8f183e18bb6ad5c382ca23e28e6aaf6Chris Lattner/// SCEV analysis can determine a loop-invariant trip count of the loop, which 12859fdaeeae8f183e18bb6ad5c382ca23e28e6aaf6Chris Lattner/// is actually a much broader range than just linear tests. 12981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan GohmanICmpInst *IndVarSimplify::LinearFunctionTestReplace(Loop *L, 1300bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *BackedgeTakenCount, 131c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman Value *IndVar, 132c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman BasicBlock *ExitingBlock, 133c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman BranchInst *BI, 13415cab2817b8f63fec0148609278bc2c1e05abb50Dan Gohman SCEVExpander &Rewriter) { 135d244057a48660c3cd30d219118ece3f947947790Chris Lattner // If the exiting block is not the same as the backedge block, we must compare 136d244057a48660c3cd30d219118ece3f947947790Chris Lattner // against the preincremented value, otherwise we prefer to compare against 137d244057a48660c3cd30d219118ece3f947947790Chris Lattner // the post-incremented value. 138c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman Value *CmpIndVar; 1390bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *RHS = BackedgeTakenCount; 140c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman if (ExitingBlock == L->getLoopLatch()) { 14146bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman // Add one to the "backedge-taken" count to get the trip count. 14246bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman // If this addition may overflow, we have to be more pessimistic and 14346bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman // cast the induction variable before doing the add. 1440bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *Zero = SE->getIntegerSCEV(0, BackedgeTakenCount->getType()); 1450bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *N = 14646bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman SE->getAddExpr(BackedgeTakenCount, 14746bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman SE->getIntegerSCEV(1, BackedgeTakenCount->getType())); 148c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman if ((isa<SCEVConstant>(N) && !N->isZero()) || 149c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman SE->isLoopGuardedByCond(L, ICmpInst::ICMP_NE, N, Zero)) { 150c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman // No overflow. Cast the sum. 15146bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman RHS = SE->getTruncateOrZeroExtend(N, IndVar->getType()); 152c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman } else { 153c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman // Potential overflow. Cast before doing the add. 15446bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman RHS = SE->getTruncateOrZeroExtend(BackedgeTakenCount, 15546bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman IndVar->getType()); 15646bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman RHS = SE->getAddExpr(RHS, 15746bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman SE->getIntegerSCEV(1, IndVar->getType())); 158c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman } 159c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman 16046bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman // The BackedgeTaken expression contains the number of times that the 16146bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman // backedge branches to the loop header. This is one less than the 16246bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman // number of times the loop executes, so use the incremented indvar. 163c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman CmpIndVar = L->getCanonicalInductionVariableIncrement(); 164d244057a48660c3cd30d219118ece3f947947790Chris Lattner } else { 165d244057a48660c3cd30d219118ece3f947947790Chris Lattner // We have to use the preincremented value... 16646bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman RHS = SE->getTruncateOrZeroExtend(BackedgeTakenCount, 16746bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman IndVar->getType()); 168c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman CmpIndVar = IndVar; 169d244057a48660c3cd30d219118ece3f947947790Chris Lattner } 17059fdaeeae8f183e18bb6ad5c382ca23e28e6aaf6Chris Lattner 171667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman // Expand the code for the iteration count. 17240a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman assert(RHS->isLoopInvariant(L) && 17340a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman "Computed iteration count is not loop invariant!"); 174667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman Value *ExitCnt = Rewriter.expandCodeFor(RHS, IndVar->getType(), BI); 17540bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner 176e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer // Insert a new icmp_ne or icmp_eq instruction before the branch. 177e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer ICmpInst::Predicate Opcode; 17840bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner if (L->contains(BI->getSuccessor(0))) 179e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer Opcode = ICmpInst::ICMP_NE; 18040bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner else 181e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer Opcode = ICmpInst::ICMP_EQ; 18240bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner 183f67ef318aa29e7cc0c7de76349881959936d9eeeDavid Greene DEBUG(dbgs() << "INDVARS: Rewriting loop exit condition to:\n" 184bdff548e4dd577a72094d57b282de4e765643b96Chris Lattner << " LHS:" << *CmpIndVar << '\n' 185bdff548e4dd577a72094d57b282de4e765643b96Chris Lattner << " op:\t" 186bdff548e4dd577a72094d57b282de4e765643b96Chris Lattner << (Opcode == ICmpInst::ICMP_NE ? "!=" : "==") << "\n" 187bdff548e4dd577a72094d57b282de4e765643b96Chris Lattner << " RHS:\t" << *RHS << "\n"); 188c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman 189333c40096561218bc3597cf153c0a3895274414cOwen Anderson ICmpInst *Cond = new ICmpInst(BI, Opcode, CmpIndVar, ExitCnt, "exitcond"); 19081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 1912444080ca4f1f63d647272650aae874360c604cdDan Gohman Value *OrigCond = BI->getCondition(); 19295bdbfa0668cc2b475429fbc6046f364bc01edf7Dan Gohman // It's tempting to use replaceAllUsesWith here to fully replace the old 19395bdbfa0668cc2b475429fbc6046f364bc01edf7Dan Gohman // comparison, but that's not immediately safe, since users of the old 19495bdbfa0668cc2b475429fbc6046f364bc01edf7Dan Gohman // comparison may not be dominated by the new comparison. Instead, just 19595bdbfa0668cc2b475429fbc6046f364bc01edf7Dan Gohman // update the branch to use the new comparison; in the common case this 19695bdbfa0668cc2b475429fbc6046f364bc01edf7Dan Gohman // will make old comparison dead. 19795bdbfa0668cc2b475429fbc6046f364bc01edf7Dan Gohman BI->setCondition(Cond); 19881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman RecursivelyDeleteTriviallyDeadInstructions(OrigCond); 19981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 20040bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner ++NumLFTR; 20140bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner Changed = true; 20281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman return Cond; 20340bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner} 2043324e718bc9ac2ede08a14c325848b576849542bChris Lattner 20540bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner/// RewriteLoopExitValues - Check to see if this loop has a computable 20640bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner/// loop-invariant execution count. If so, this means that we can compute the 20740bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner/// final value of any expressions that are recurrent in the loop, and 20840bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner/// substitute the exit values from the loop into any instructions outside of 20940bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner/// the loop that use the final values of the current expressions. 21081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman/// 21181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman/// This is mostly redundant with the regular IndVarSimplify activities that 21281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman/// happen later, except that it's more powerful in some cases, because it's 21381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman/// able to brute-force evaluate arbitrary instructions as long as they have 21481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman/// constant operands at the beginning of the loop. 215890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohmanvoid IndVarSimplify::RewriteLoopExitValues(Loop *L, 216667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman SCEVExpander &Rewriter) { 21781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Verify the input to the pass in already in LCSSA form. 21881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman assert(L->isLCSSAForm()); 21981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 220b7211a2ce13a0365e0e1dd2f27adda2ee3d1288bDevang Patel SmallVector<BasicBlock*, 8> ExitBlocks; 2219f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner L->getUniqueExitBlocks(ExitBlocks); 2229f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner 2239f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // Find all values that are computed inside the loop, but used outside of it. 2249f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // Because of LCSSA, these values will only occur in LCSSA PHI Nodes. Scan 2259f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // the exit blocks of the loop to find them. 2269f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) { 2279f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner BasicBlock *ExitBB = ExitBlocks[i]; 228cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 2299f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // If there are no PHI nodes in this exit block, then no values defined 2309f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // inside the loop are used on this path, skip it. 2319f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner PHINode *PN = dyn_cast<PHINode>(ExitBB->begin()); 2329f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner if (!PN) continue; 233cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 2349f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner unsigned NumPreds = PN->getNumIncomingValues(); 235cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 2369f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // Iterate over all of the PHI nodes. 2379f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner BasicBlock::iterator BBI = ExitBB->begin(); 2389f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner while ((PN = dyn_cast<PHINode>(BBI++))) { 2393790fb0c036acaa4db50aff83dd8b3bf51f8af6aTorok Edwin if (PN->use_empty()) 2403790fb0c036acaa4db50aff83dd8b3bf51f8af6aTorok Edwin continue; // dead use, don't replace it 241814f2b2d1927a5397c0e923588527277b9f67d6bDan Gohman 242814f2b2d1927a5397c0e923588527277b9f67d6bDan Gohman // SCEV only supports integer expressions for now. 243814f2b2d1927a5397c0e923588527277b9f67d6bDan Gohman if (!PN->getType()->isIntegerTy() && !PN->getType()->isPointerTy()) 244814f2b2d1927a5397c0e923588527277b9f67d6bDan Gohman continue; 245814f2b2d1927a5397c0e923588527277b9f67d6bDan Gohman 24645a2d7d44ae697e28df383d31455145fb754ac58Dale Johannesen // It's necessary to tell ScalarEvolution about this explicitly so that 24745a2d7d44ae697e28df383d31455145fb754ac58Dale Johannesen // it can walk the def-use list and forget all SCEVs, as it may not be 24845a2d7d44ae697e28df383d31455145fb754ac58Dale Johannesen // watching the PHI itself. Once the new exit value is in place, there 24945a2d7d44ae697e28df383d31455145fb754ac58Dale Johannesen // may not be a def-use connection between the loop and every instruction 25045a2d7d44ae697e28df383d31455145fb754ac58Dale Johannesen // which got a SCEVAddRecExpr for that loop. 25145a2d7d44ae697e28df383d31455145fb754ac58Dale Johannesen SE->forgetValue(PN); 25245a2d7d44ae697e28df383d31455145fb754ac58Dale Johannesen 2539f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // Iterate over all of the values in all the PHI nodes. 2549f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner for (unsigned i = 0; i != NumPreds; ++i) { 2559f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // If the value being merged in is not integer or is not defined 2569f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // in the loop, skip it. 2579f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner Value *InVal = PN->getIncomingValue(i); 258814f2b2d1927a5397c0e923588527277b9f67d6bDan Gohman if (!isa<Instruction>(InVal)) 2599f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner continue; 2609f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner 2619f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // If this pred is for a subloop, not L itself, skip it. 262cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman if (LI->getLoopFor(PN->getIncomingBlock(i)) != L) 2639f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner continue; // The Block is in a subloop, skip it. 2649f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner 2659f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // Check that InVal is defined in the loop. 2669f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner Instruction *Inst = cast<Instruction>(InVal); 26792329c7fbe572892c17aa2d2542a10e3ea16132fDan Gohman if (!L->contains(Inst)) 2689f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner continue; 269cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 2709f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // Okay, this instruction has a user outside of the current loop 2719f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // and varies predictably *inside* the loop. Evaluate the value it 2729f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // contains when the loop exits, if possible. 2730bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *ExitValue = SE->getSCEVAtScope(Inst, L->getParentLoop()); 274d594e6f0345b3e1e4b640a7099596ca613da16d6Dan Gohman if (!ExitValue->isLoopInvariant(L)) 2759f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner continue; 2769f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner 2779f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner Changed = true; 2789f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner ++NumReplaced; 279cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 280667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman Value *ExitVal = Rewriter.expandCodeFor(ExitValue, PN->getType(), Inst); 281cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 282f67ef318aa29e7cc0c7de76349881959936d9eeeDavid Greene DEBUG(dbgs() << "INDVARS: RLEV: AfterLoopVal = " << *ExitVal << '\n' 283bdff548e4dd577a72094d57b282de4e765643b96Chris Lattner << " LoopVal = " << *Inst << "\n"); 2849caed5440d59dac4b388152fe8b993dc0491e5e9Chris Lattner 2859f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner PN->setIncomingValue(i, ExitVal); 286cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 28781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // If this instruction is dead now, delete it. 28881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman RecursivelyDeleteTriviallyDeadInstructions(Inst); 289cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 29065d1e2b6e74fcd370093cbe518ebc15cbc445ad4Dan Gohman if (NumPreds == 1) { 29165d1e2b6e74fcd370093cbe518ebc15cbc445ad4Dan Gohman // Completely replace a single-pred PHI. This is safe, because the 29265d1e2b6e74fcd370093cbe518ebc15cbc445ad4Dan Gohman // NewVal won't be variant in the loop, so we don't need an LCSSA phi 29365d1e2b6e74fcd370093cbe518ebc15cbc445ad4Dan Gohman // node anymore. 2949f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner PN->replaceAllUsesWith(ExitVal); 29581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman RecursivelyDeleteTriviallyDeadInstructions(PN); 296c9838f25d53d3dd7d38949ef6c28f2505a110f45Chris Lattner } 2974bd09d70cceb3851f7eb1c2f98338b3071d405f3Chris Lattner } 29865d1e2b6e74fcd370093cbe518ebc15cbc445ad4Dan Gohman if (NumPreds != 1) { 299667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman // Clone the PHI and delete the original one. This lets IVUsers and 300667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman // any other maps purge the original user from their records. 30150b6e33584f4e4cf75c7795b1f1a90731861c825Devang Patel PHINode *NewPN = cast<PHINode>(PN->clone()); 302667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman NewPN->takeName(PN); 303667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman NewPN->insertBefore(PN); 304667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman PN->replaceAllUsesWith(NewPN); 305667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman PN->eraseFromParent(); 306667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman } 307c9838f25d53d3dd7d38949ef6c28f2505a110f45Chris Lattner } 308c9838f25d53d3dd7d38949ef6c28f2505a110f45Chris Lattner } 30940bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner} 31015cad759fe2048ac5eb137c6bb0ab7287538677eChris Lattner 31160f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohmanvoid IndVarSimplify::RewriteNonIntegerIVs(Loop *L) { 3122d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman // First step. Check to see if there are any floating-point recurrences. 31340bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // If there are, change them into integer recurrences, permitting analysis by 31440bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // the SCEV routines. 31515cad759fe2048ac5eb137c6bb0ab7287538677eChris Lattner // 31640bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner BasicBlock *Header = L->getHeader(); 317fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 31881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman SmallVector<WeakVH, 8> PHIs; 31981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman for (BasicBlock::iterator I = Header->begin(); 32081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman PHINode *PN = dyn_cast<PHINode>(I); ++I) 32181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman PHIs.push_back(PN); 32281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 32381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman for (unsigned i = 0, e = PHIs.size(); i != e; ++i) 32481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (PHINode *PN = dyn_cast_or_null<PHINode>(PHIs[i])) 32581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman HandleFloatingPointIV(L, PN); 32615cad759fe2048ac5eb137c6bb0ab7287538677eChris Lattner 3272d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman // If the loop previously had floating-point IV, ScalarEvolution 32860f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman // may not have been able to compute a trip count. Now that we've done some 32960f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman // re-writing, the trip count may be computable. 33060f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman if (Changed) 3314c7279ac726e338400626fca5a09b5533426eb6aDan Gohman SE->forgetLoop(L); 332c671d892ab1d3d8fed18a61f66f3f3a86e73ebd9Dale Johannesen} 333c671d892ab1d3d8fed18a61f66f3f3a86e73ebd9Dale Johannesen 334c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohmanbool IndVarSimplify::runOnLoop(Loop *L, LPPassManager &LPM) { 33581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman IU = &getAnalysis<IVUsers>(); 3365ee99979065d75605d150d7e567e4351024aae8fDevang Patel LI = &getAnalysis<LoopInfo>(); 3375ee99979065d75605d150d7e567e4351024aae8fDevang Patel SE = &getAnalysis<ScalarEvolution>(); 338de53dc03f5c1549f3176e979bbeeac965dfa5cbcDan Gohman DT = &getAnalysis<DominatorTree>(); 3395ee99979065d75605d150d7e567e4351024aae8fDevang Patel Changed = false; 34060f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman 3412d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman // If there are any floating-point recurrences, attempt to 34260f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman // transform them to use integer recurrences. 34360f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman RewriteNonIntegerIVs(L); 34460f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman 34581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman BasicBlock *ExitingBlock = L->getExitingBlock(); // may be null 3460bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *BackedgeTakenCount = SE->getBackedgeTakenCount(L); 3479caed5440d59dac4b388152fe8b993dc0491e5e9Chris Lattner 348667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman // Create a rewriter object which we'll use to transform the code with. 349667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman SCEVExpander Rewriter(*SE); 350667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman 35140bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // Check to see if this loop has a computable loop-invariant execution count. 35240bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // If so, this means that we can compute the final value of any expressions 35340bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // that are recurrent in the loop, and substitute the exit values from the 35440bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // loop into any instructions outside of the loop that use the final values of 35540bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // the current expressions. 356394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner // 35746bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman if (!isa<SCEVCouldNotCompute>(BackedgeTakenCount)) 358454d26dc43207ec537d843229db6f5e6a302e23dDan Gohman RewriteLoopExitValues(L, Rewriter); 35940bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner 36081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Compute the type of the largest recurrence expression, and decide whether 36181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // a canonical induction variable should be inserted. 362c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman const Type *LargestType = 0; 36381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman bool NeedCannIV = false; 36446bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman if (!isa<SCEVCouldNotCompute>(BackedgeTakenCount)) { 36546bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman LargestType = BackedgeTakenCount->getType(); 366af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman LargestType = SE->getEffectiveSCEVType(LargestType); 36781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // If we have a known trip count and a single exit block, we'll be 36881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // rewriting the loop exit test condition below, which requires a 36981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // canonical induction variable. 37081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (ExitingBlock) 37181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman NeedCannIV = true; 372f50af088f19f525f3d1026eb61db77e0037a9f43Chris Lattner } 373572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman for (IVUsers::const_iterator I = IU->begin(), E = IU->end(); I != E; ++I) { 374572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman const Type *Ty = 375572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman SE->getEffectiveSCEVType(I->getOperandValToReplace()->getType()); 376c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman if (!LargestType || 37781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman SE->getTypeSizeInBits(Ty) > 378af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman SE->getTypeSizeInBits(LargestType)) 37981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman LargestType = Ty; 380572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman NeedCannIV = true; 381500597a1c39e91a3020587318ed61e737b6c613aChris Lattner } 382394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner 383f451cb870efcf9e0302d25ed05f4cac6bb494e42Dan Gohman // Now that we know the largest of the induction variable expressions 38481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // in this loop, insert a canonical induction variable of the largest size. 385c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman Value *IndVar = 0; 38681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (NeedCannIV) { 38785669637139089eaed8def1583ac04266c9654e2Dan Gohman // Check to see if the loop already has any canonical-looking induction 38885669637139089eaed8def1583ac04266c9654e2Dan Gohman // variables. If any are present and wider than the planned canonical 38985669637139089eaed8def1583ac04266c9654e2Dan Gohman // induction variable, temporarily remove them, so that the Rewriter 39085669637139089eaed8def1583ac04266c9654e2Dan Gohman // doesn't attempt to reuse them. 39185669637139089eaed8def1583ac04266c9654e2Dan Gohman SmallVector<PHINode *, 2> OldCannIVs; 39285669637139089eaed8def1583ac04266c9654e2Dan Gohman while (PHINode *OldCannIV = L->getCanonicalInductionVariable()) { 3934d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman if (SE->getTypeSizeInBits(OldCannIV->getType()) > 3944d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman SE->getTypeSizeInBits(LargestType)) 3954d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman OldCannIV->removeFromParent(); 3964d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman else 39785669637139089eaed8def1583ac04266c9654e2Dan Gohman break; 39885669637139089eaed8def1583ac04266c9654e2Dan Gohman OldCannIVs.push_back(OldCannIV); 3994d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman } 4004d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman 401667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman IndVar = Rewriter.getOrInsertCanonicalInductionVariable(L, LargestType); 4024d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman 403c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman ++NumInserted; 404c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman Changed = true; 405f67ef318aa29e7cc0c7de76349881959936d9eeeDavid Greene DEBUG(dbgs() << "INDVARS: New CanIV: " << *IndVar << '\n'); 4064d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman 4074d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman // Now that the official induction variable is established, reinsert 40885669637139089eaed8def1583ac04266c9654e2Dan Gohman // any old canonical-looking variables after it so that the IR remains 40985669637139089eaed8def1583ac04266c9654e2Dan Gohman // consistent. They will be deleted as part of the dead-PHI deletion at 4104d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman // the end of the pass. 41185669637139089eaed8def1583ac04266c9654e2Dan Gohman while (!OldCannIVs.empty()) { 41285669637139089eaed8def1583ac04266c9654e2Dan Gohman PHINode *OldCannIV = OldCannIVs.pop_back_val(); 41385669637139089eaed8def1583ac04266c9654e2Dan Gohman OldCannIV->insertBefore(L->getHeader()->getFirstNonPHI()); 41485669637139089eaed8def1583ac04266c9654e2Dan Gohman } 415d19534add90a2a894af61523b830887097bb780bDan Gohman } 41640bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner 417c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman // If we have a trip count expression, rewrite the loop's exit condition 418c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman // using it. We can currently only handle loops with a single exit. 41981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman ICmpInst *NewICmp = 0; 42085669637139089eaed8def1583ac04266c9654e2Dan Gohman if (!isa<SCEVCouldNotCompute>(BackedgeTakenCount) && 42185669637139089eaed8def1583ac04266c9654e2Dan Gohman !BackedgeTakenCount->isZero() && 42285669637139089eaed8def1583ac04266c9654e2Dan Gohman ExitingBlock) { 42381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman assert(NeedCannIV && 42481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman "LinearFunctionTestReplace requires a canonical induction variable"); 425c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman // Can't rewrite non-branch yet. 42681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (BranchInst *BI = dyn_cast<BranchInst>(ExitingBlock->getTerminator())) 42781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman NewICmp = LinearFunctionTestReplace(L, BackedgeTakenCount, IndVar, 42881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman ExitingBlock, BI, Rewriter); 42981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman } 430c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman 4313d431384f05c9defc84f36eafe220415cc12ee93Torok Edwin // Rewrite IV-derived expressions. Clears the rewriter cache. 432454d26dc43207ec537d843229db6f5e6a302e23dDan Gohman RewriteIVExpressions(L, Rewriter); 433fcb81f5f4cbac61851b7dec403961cf88e614aa1Chris Lattner 434667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman // The Rewriter may not be used from this point on. 4353d431384f05c9defc84f36eafe220415cc12ee93Torok Edwin 43681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Loop-invariant instructions in the preheader that aren't used in the 43781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // loop may be sunk below the loop to reduce register pressure. 438667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman SinkUnusedInvariants(L); 43981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 44081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // For completeness, inform IVUsers of the IV use in the newly-created 44181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // loop exit test instruction. 44281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (NewICmp) 44381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman IU->AddUsersIfInteresting(cast<Instruction>(NewICmp->getOperand(0))); 44481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 44581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Clean up dead instructions. 4469fff2187a21f765ed87a25c48552a6942450f3e2Dan Gohman Changed |= DeleteDeadPHIs(L->getHeader()); 44781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Check a post-condition. 44881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman assert(L->isLCSSAForm() && "Indvars did not leave the loop in lcssa form!"); 44981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman return Changed; 45081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman} 45181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 452454d26dc43207ec537d843229db6f5e6a302e23dDan Gohmanvoid IndVarSimplify::RewriteIVExpressions(Loop *L, SCEVExpander &Rewriter) { 45381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman SmallVector<WeakVH, 16> DeadInsts; 45481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 45581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Rewrite all induction variable expressions in terms of the canonical 45681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // induction variable. 45781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // 45881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // If there were induction variables of other sizes or offsets, manually 45981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // add the offsets to the primary induction variable and cast, avoiding 46081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // the need for the code evaluation methods to insert induction variables 46181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // of different sizes. 462572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman for (IVUsers::iterator UI = IU->begin(), E = IU->end(); UI != E; ++UI) { 463572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman const SCEV *Stride = UI->getStride(); 464572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman Value *Op = UI->getOperandValToReplace(); 465572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman const Type *UseTy = Op->getType(); 466572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman Instruction *User = UI->getUser(); 467572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman 468572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // Compute the final addrec to expand into code. 469572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman const SCEV *AR = IU->getReplacementExpr(*UI); 470572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman 471572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // Evaluate the expression out of the loop, if possible. 472572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman if (!L->contains(UI->getUser())) { 473572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman const SCEV *ExitVal = SE->getSCEVAtScope(AR, L->getParentLoop()); 474572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman if (ExitVal->isLoopInvariant(L)) 475572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman AR = ExitVal; 47681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman } 477572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman 478572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // FIXME: It is an extremely bad idea to indvar substitute anything more 479572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // complex than affine induction variables. Doing so will put expensive 480572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // polynomial evaluations inside of the loop, and the str reduction pass 481572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // currently can only reduce affine polynomials. For now just disable 482572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // indvar subst on anything more complex than an affine addrec, unless 483572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // it can be expanded to a trivial value. 484572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman if (!AR->isLoopInvariant(L) && !Stride->isLoopInvariant(L)) 485572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman continue; 486572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman 487572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // Determine the insertion point for this user. By default, insert 488572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // immediately before the user. The SCEVExpander class will automatically 489572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // hoist loop invariants out of the loop. For PHI nodes, there may be 490572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // multiple uses, so compute the nearest common dominator for the 491572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // incoming blocks. 492572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman Instruction *InsertPt = User; 493572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman if (PHINode *PHI = dyn_cast<PHINode>(InsertPt)) 494572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i) 495572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman if (PHI->getIncomingValue(i) == Op) { 496572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman if (InsertPt == User) 497572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman InsertPt = PHI->getIncomingBlock(i)->getTerminator(); 498572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman else 499572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman InsertPt = 500572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman DT->findNearestCommonDominator(InsertPt->getParent(), 501572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman PHI->getIncomingBlock(i)) 502572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman ->getTerminator(); 503572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman } 504572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman 505572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // Now expand it into actual Instructions and patch it into place. 506572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman Value *NewVal = Rewriter.expandCodeFor(AR, UseTy, InsertPt); 507572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman 508572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // Patch the new value into place. 509572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman if (Op->hasName()) 510572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman NewVal->takeName(Op); 511572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman User->replaceUsesOfWith(Op, NewVal); 512572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman UI->setOperandValToReplace(NewVal); 513572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman DEBUG(dbgs() << "INDVARS: Rewrote IV '" << *AR << "' " << *Op << '\n' 514572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman << " into = " << *NewVal << "\n"); 515572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman ++NumRemoved; 516572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman Changed = true; 517572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman 518572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman // The old value may be dead now. 519572645cf84060c0fc25cb91d38cb9079918b3a88Dan Gohman DeadInsts.push_back(Op); 520500597a1c39e91a3020587318ed61e737b6c613aChris Lattner } 521ba4f3f6a419326df190599421fa149c90235cb72Chris Lattner 5223d431384f05c9defc84f36eafe220415cc12ee93Torok Edwin // Clear the rewriter cache, because values that are in the rewriter's cache 5233d431384f05c9defc84f36eafe220415cc12ee93Torok Edwin // can be deleted in the loop below, causing the AssertingVH in the cache to 5243d431384f05c9defc84f36eafe220415cc12ee93Torok Edwin // trigger. 5253d431384f05c9defc84f36eafe220415cc12ee93Torok Edwin Rewriter.clear(); 52681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Now that we're done iterating through lists, clean up any instructions 52781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // which are now dead. 528a10756ee657a4d43a48cca5c166919093930ed6bDan Gohman while (!DeadInsts.empty()) 529a10756ee657a4d43a48cca5c166919093930ed6bDan Gohman if (Instruction *Inst = 530a10756ee657a4d43a48cca5c166919093930ed6bDan Gohman dyn_cast_or_null<Instruction>(DeadInsts.pop_back_val())) 53181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman RecursivelyDeleteTriviallyDeadInstructions(Inst); 53281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman} 53381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 53481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman/// If there's a single exit block, sink any loop-invariant values that 53581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman/// were defined in the preheader but not used inside the loop into the 53681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman/// exit block to reduce register pressure in the loop. 537667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohmanvoid IndVarSimplify::SinkUnusedInvariants(Loop *L) { 53881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman BasicBlock *ExitBlock = L->getExitBlock(); 53981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (!ExitBlock) return; 54081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 54181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman BasicBlock *Preheader = L->getLoopPreheader(); 54203e896bd6073efc4523d8bcd0239d6ed62126db7Dan Gohman if (!Preheader) return; 54303e896bd6073efc4523d8bcd0239d6ed62126db7Dan Gohman 54403e896bd6073efc4523d8bcd0239d6ed62126db7Dan Gohman Instruction *InsertPt = ExitBlock->getFirstNonPHI(); 54581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman BasicBlock::iterator I = Preheader->getTerminator(); 54681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman while (I != Preheader->begin()) { 54781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman --I; 548667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman // New instructions were inserted at the end of the preheader. 549667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman if (isa<PHINode>(I)) 55081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman break; 5510c77db32dd8ae10b5a26d60718dbe03dc2745888Eli Friedman // Don't move instructions which might have side effects, since the side 5520c77db32dd8ae10b5a26d60718dbe03dc2745888Eli Friedman // effects need to complete before instructions inside the loop. Also 5530c77db32dd8ae10b5a26d60718dbe03dc2745888Eli Friedman // don't move instructions which might read memory, since the loop may 5540c77db32dd8ae10b5a26d60718dbe03dc2745888Eli Friedman // modify memory. Note that it's okay if the instruction might have 5550c77db32dd8ae10b5a26d60718dbe03dc2745888Eli Friedman // undefined behavior: LoopSimplify guarantees that the preheader 5560c77db32dd8ae10b5a26d60718dbe03dc2745888Eli Friedman // dominates the exit block. 5570c77db32dd8ae10b5a26d60718dbe03dc2745888Eli Friedman if (I->mayHaveSideEffects() || I->mayReadFromMemory()) 558667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman continue; 55976f497a351c562f366b5e93c27d3f1652fb48ff4Dan Gohman // Don't sink static AllocaInsts out of the entry block, which would 56076f497a351c562f366b5e93c27d3f1652fb48ff4Dan Gohman // turn them into dynamic allocas! 56176f497a351c562f366b5e93c27d3f1652fb48ff4Dan Gohman if (AllocaInst *AI = dyn_cast<AllocaInst>(I)) 56276f497a351c562f366b5e93c27d3f1652fb48ff4Dan Gohman if (AI->isStaticAlloca()) 56376f497a351c562f366b5e93c27d3f1652fb48ff4Dan Gohman continue; 56481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Determine if there is a use in or before the loop (direct or 56581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // otherwise). 56681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman bool UsedInLoop = false; 56781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman for (Value::use_iterator UI = I->use_begin(), UE = I->use_end(); 56881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman UI != UE; ++UI) { 56981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman BasicBlock *UseBB = cast<Instruction>(UI)->getParent(); 57081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (PHINode *P = dyn_cast<PHINode>(UI)) { 57181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman unsigned i = 57281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman PHINode::getIncomingValueNumForOperand(UI.getOperandNo()); 57381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman UseBB = P->getIncomingBlock(i); 57481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman } 57581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (UseBB == Preheader || L->contains(UseBB)) { 57681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman UsedInLoop = true; 57781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman break; 57881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman } 57981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman } 58081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // If there is, the def must remain in the preheader. 58181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (UsedInLoop) 58281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman continue; 58381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Otherwise, sink it to the exit block. 58481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman Instruction *ToMove = I; 58581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman bool Done = false; 58681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (I != Preheader->begin()) 58781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman --I; 58881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman else 58981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman Done = true; 590667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman ToMove->moveBefore(InsertPt); 59181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (Done) 59281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman break; 593667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman InsertPt = ToMove; 59481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman } 59581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman} 59681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 59713877bf6c20621541ff71583c626bda68ef09219Devang Patel/// Return true if it is OK to use SIToFPInst for an inducation variable 59813877bf6c20621541ff71583c626bda68ef09219Devang Patel/// with given inital and exit values. 59913877bf6c20621541ff71583c626bda68ef09219Devang Patelstatic bool useSIToFPInst(ConstantFP &InitV, ConstantFP &ExitV, 60013877bf6c20621541ff71583c626bda68ef09219Devang Patel uint64_t intIV, uint64_t intEV) { 60113877bf6c20621541ff71583c626bda68ef09219Devang Patel 602cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman if (InitV.getValueAPF().isNegative() || ExitV.getValueAPF().isNegative()) 60313877bf6c20621541ff71583c626bda68ef09219Devang Patel return true; 60413877bf6c20621541ff71583c626bda68ef09219Devang Patel 60513877bf6c20621541ff71583c626bda68ef09219Devang Patel // If the iteration range can be handled by SIToFPInst then use it. 60613877bf6c20621541ff71583c626bda68ef09219Devang Patel APInt Max = APInt::getSignedMaxValue(32); 607bae7d6dbeb842b5ed051c50a87bc282f2dec6e1fDale Johannesen if (Max.getZExtValue() > static_cast<uint64_t>(abs64(intEV - intIV))) 60813877bf6c20621541ff71583c626bda68ef09219Devang Patel return true; 609cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 61013877bf6c20621541ff71583c626bda68ef09219Devang Patel return false; 61113877bf6c20621541ff71583c626bda68ef09219Devang Patel} 61213877bf6c20621541ff71583c626bda68ef09219Devang Patel 61313877bf6c20621541ff71583c626bda68ef09219Devang Patel/// convertToInt - Convert APF to an integer, if possible. 614cd40233429fce385ae4b22301ce705273a6951a1Devang Patelstatic bool convertToInt(const APFloat &APF, uint64_t *intVal) { 615cd40233429fce385ae4b22301ce705273a6951a1Devang Patel 616cd40233429fce385ae4b22301ce705273a6951a1Devang Patel bool isExact = false; 617794a7dbce030f93315b1305f83a374232f09bba5Evan Cheng if (&APF.getSemantics() == &APFloat::PPCDoubleDouble) 618794a7dbce030f93315b1305f83a374232f09bba5Evan Cheng return false; 619cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman if (APF.convertToInteger(intVal, 32, APF.isNegative(), 620cd40233429fce385ae4b22301ce705273a6951a1Devang Patel APFloat::rmTowardZero, &isExact) 621cd40233429fce385ae4b22301ce705273a6951a1Devang Patel != APFloat::opOK) 622cd40233429fce385ae4b22301ce705273a6951a1Devang Patel return false; 623cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman if (!isExact) 624cd40233429fce385ae4b22301ce705273a6951a1Devang Patel return false; 625cd40233429fce385ae4b22301ce705273a6951a1Devang Patel return true; 626cd40233429fce385ae4b22301ce705273a6951a1Devang Patel 627cd40233429fce385ae4b22301ce705273a6951a1Devang Patel} 628cd40233429fce385ae4b22301ce705273a6951a1Devang Patel 62958d43d4a41b21085c063bdd21a2abb68056e2a6fDevang Patel/// HandleFloatingPointIV - If the loop has floating induction variable 63058d43d4a41b21085c063bdd21a2abb68056e2a6fDevang Patel/// then insert corresponding integer induction variable if possible. 63184e3515974407a606289c6e762a0419723b7918fDevang Patel/// For example, 63284e3515974407a606289c6e762a0419723b7918fDevang Patel/// for(double i = 0; i < 10000; ++i) 63384e3515974407a606289c6e762a0419723b7918fDevang Patel/// bar(i) 63484e3515974407a606289c6e762a0419723b7918fDevang Patel/// is converted into 63584e3515974407a606289c6e762a0419723b7918fDevang Patel/// for(int i = 0; i < 10000; ++i) 63684e3515974407a606289c6e762a0419723b7918fDevang Patel/// bar((double)i); 63784e3515974407a606289c6e762a0419723b7918fDevang Patel/// 63881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohmanvoid IndVarSimplify::HandleFloatingPointIV(Loop *L, PHINode *PH) { 63984e3515974407a606289c6e762a0419723b7918fDevang Patel 64084e3515974407a606289c6e762a0419723b7918fDevang Patel unsigned IncomingEdge = L->contains(PH->getIncomingBlock(0)); 64184e3515974407a606289c6e762a0419723b7918fDevang Patel unsigned BackEdge = IncomingEdge^1; 642cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 64384e3515974407a606289c6e762a0419723b7918fDevang Patel // Check incoming value. 644cd40233429fce385ae4b22301ce705273a6951a1Devang Patel ConstantFP *InitValue = dyn_cast<ConstantFP>(PH->getIncomingValue(IncomingEdge)); 645cd40233429fce385ae4b22301ce705273a6951a1Devang Patel if (!InitValue) return; 6461d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson uint64_t newInitValue = 6471d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson Type::getInt32Ty(PH->getContext())->getPrimitiveSizeInBits(); 648cd40233429fce385ae4b22301ce705273a6951a1Devang Patel if (!convertToInt(InitValue->getValueAPF(), &newInitValue)) 649cd40233429fce385ae4b22301ce705273a6951a1Devang Patel return; 650cd40233429fce385ae4b22301ce705273a6951a1Devang Patel 651cd40233429fce385ae4b22301ce705273a6951a1Devang Patel // Check IV increment. Reject this PH if increement operation is not 652cd40233429fce385ae4b22301ce705273a6951a1Devang Patel // an add or increment value can not be represented by an integer. 653cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman BinaryOperator *Incr = 65484e3515974407a606289c6e762a0419723b7918fDevang Patel dyn_cast<BinaryOperator>(PH->getIncomingValue(BackEdge)); 65584e3515974407a606289c6e762a0419723b7918fDevang Patel if (!Incr) return; 656ae3a0be92e33bc716722aa600983fc1535acb122Dan Gohman if (Incr->getOpcode() != Instruction::FAdd) return; 65784e3515974407a606289c6e762a0419723b7918fDevang Patel ConstantFP *IncrValue = NULL; 65884e3515974407a606289c6e762a0419723b7918fDevang Patel unsigned IncrVIndex = 1; 65984e3515974407a606289c6e762a0419723b7918fDevang Patel if (Incr->getOperand(1) == PH) 66084e3515974407a606289c6e762a0419723b7918fDevang Patel IncrVIndex = 0; 66184e3515974407a606289c6e762a0419723b7918fDevang Patel IncrValue = dyn_cast<ConstantFP>(Incr->getOperand(IncrVIndex)); 66284e3515974407a606289c6e762a0419723b7918fDevang Patel if (!IncrValue) return; 6631d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson uint64_t newIncrValue = 6641d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson Type::getInt32Ty(PH->getContext())->getPrimitiveSizeInBits(); 665cd40233429fce385ae4b22301ce705273a6951a1Devang Patel if (!convertToInt(IncrValue->getValueAPF(), &newIncrValue)) 666cd40233429fce385ae4b22301ce705273a6951a1Devang Patel return; 667cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 668cd40233429fce385ae4b22301ce705273a6951a1Devang Patel // Check Incr uses. One user is PH and the other users is exit condition used 669cd40233429fce385ae4b22301ce705273a6951a1Devang Patel // by the conditional terminator. 67084e3515974407a606289c6e762a0419723b7918fDevang Patel Value::use_iterator IncrUse = Incr->use_begin(); 67184e3515974407a606289c6e762a0419723b7918fDevang Patel Instruction *U1 = cast<Instruction>(IncrUse++); 67284e3515974407a606289c6e762a0419723b7918fDevang Patel if (IncrUse == Incr->use_end()) return; 67384e3515974407a606289c6e762a0419723b7918fDevang Patel Instruction *U2 = cast<Instruction>(IncrUse++); 67484e3515974407a606289c6e762a0419723b7918fDevang Patel if (IncrUse != Incr->use_end()) return; 675cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 67684e3515974407a606289c6e762a0419723b7918fDevang Patel // Find exit condition. 67784e3515974407a606289c6e762a0419723b7918fDevang Patel FCmpInst *EC = dyn_cast<FCmpInst>(U1); 67884e3515974407a606289c6e762a0419723b7918fDevang Patel if (!EC) 67984e3515974407a606289c6e762a0419723b7918fDevang Patel EC = dyn_cast<FCmpInst>(U2); 68084e3515974407a606289c6e762a0419723b7918fDevang Patel if (!EC) return; 68184e3515974407a606289c6e762a0419723b7918fDevang Patel 68284e3515974407a606289c6e762a0419723b7918fDevang Patel if (BranchInst *BI = dyn_cast<BranchInst>(EC->getParent()->getTerminator())) { 68384e3515974407a606289c6e762a0419723b7918fDevang Patel if (!BI->isConditional()) return; 68484e3515974407a606289c6e762a0419723b7918fDevang Patel if (BI->getCondition() != EC) return; 68558d43d4a41b21085c063bdd21a2abb68056e2a6fDevang Patel } 68684e3515974407a606289c6e762a0419723b7918fDevang Patel 687cd40233429fce385ae4b22301ce705273a6951a1Devang Patel // Find exit value. If exit value can not be represented as an interger then 688cd40233429fce385ae4b22301ce705273a6951a1Devang Patel // do not handle this floating point PH. 68984e3515974407a606289c6e762a0419723b7918fDevang Patel ConstantFP *EV = NULL; 69084e3515974407a606289c6e762a0419723b7918fDevang Patel unsigned EVIndex = 1; 69184e3515974407a606289c6e762a0419723b7918fDevang Patel if (EC->getOperand(1) == Incr) 69284e3515974407a606289c6e762a0419723b7918fDevang Patel EVIndex = 0; 69384e3515974407a606289c6e762a0419723b7918fDevang Patel EV = dyn_cast<ConstantFP>(EC->getOperand(EVIndex)); 69484e3515974407a606289c6e762a0419723b7918fDevang Patel if (!EV) return; 6951d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson uint64_t intEV = Type::getInt32Ty(PH->getContext())->getPrimitiveSizeInBits(); 696cd40233429fce385ae4b22301ce705273a6951a1Devang Patel if (!convertToInt(EV->getValueAPF(), &intEV)) 69784e3515974407a606289c6e762a0419723b7918fDevang Patel return; 698cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 69984e3515974407a606289c6e762a0419723b7918fDevang Patel // Find new predicate for integer comparison. 70084e3515974407a606289c6e762a0419723b7918fDevang Patel CmpInst::Predicate NewPred = CmpInst::BAD_ICMP_PREDICATE; 70184e3515974407a606289c6e762a0419723b7918fDevang Patel switch (EC->getPredicate()) { 70284e3515974407a606289c6e762a0419723b7918fDevang Patel case CmpInst::FCMP_OEQ: 70384e3515974407a606289c6e762a0419723b7918fDevang Patel case CmpInst::FCMP_UEQ: 70484e3515974407a606289c6e762a0419723b7918fDevang Patel NewPred = CmpInst::ICMP_EQ; 70584e3515974407a606289c6e762a0419723b7918fDevang Patel break; 70684e3515974407a606289c6e762a0419723b7918fDevang Patel case CmpInst::FCMP_OGT: 70784e3515974407a606289c6e762a0419723b7918fDevang Patel case CmpInst::FCMP_UGT: 70884e3515974407a606289c6e762a0419723b7918fDevang Patel NewPred = CmpInst::ICMP_UGT; 70984e3515974407a606289c6e762a0419723b7918fDevang Patel break; 71084e3515974407a606289c6e762a0419723b7918fDevang Patel case CmpInst::FCMP_OGE: 71184e3515974407a606289c6e762a0419723b7918fDevang Patel case CmpInst::FCMP_UGE: 71284e3515974407a606289c6e762a0419723b7918fDevang Patel NewPred = CmpInst::ICMP_UGE; 71384e3515974407a606289c6e762a0419723b7918fDevang Patel break; 71484e3515974407a606289c6e762a0419723b7918fDevang Patel case CmpInst::FCMP_OLT: 71584e3515974407a606289c6e762a0419723b7918fDevang Patel case CmpInst::FCMP_ULT: 71684e3515974407a606289c6e762a0419723b7918fDevang Patel NewPred = CmpInst::ICMP_ULT; 71784e3515974407a606289c6e762a0419723b7918fDevang Patel break; 71884e3515974407a606289c6e762a0419723b7918fDevang Patel case CmpInst::FCMP_OLE: 71984e3515974407a606289c6e762a0419723b7918fDevang Patel case CmpInst::FCMP_ULE: 72084e3515974407a606289c6e762a0419723b7918fDevang Patel NewPred = CmpInst::ICMP_ULE; 72184e3515974407a606289c6e762a0419723b7918fDevang Patel break; 72284e3515974407a606289c6e762a0419723b7918fDevang Patel default: 72384e3515974407a606289c6e762a0419723b7918fDevang Patel break; 72458d43d4a41b21085c063bdd21a2abb68056e2a6fDevang Patel } 72584e3515974407a606289c6e762a0419723b7918fDevang Patel if (NewPred == CmpInst::BAD_ICMP_PREDICATE) return; 726cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 72784e3515974407a606289c6e762a0419723b7918fDevang Patel // Insert new integer induction variable. 7281d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson PHINode *NewPHI = PHINode::Create(Type::getInt32Ty(PH->getContext()), 72984e3515974407a606289c6e762a0419723b7918fDevang Patel PH->getName()+".int", PH); 7301d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson NewPHI->addIncoming(ConstantInt::get(Type::getInt32Ty(PH->getContext()), 7311d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson newInitValue), 73284e3515974407a606289c6e762a0419723b7918fDevang Patel PH->getIncomingBlock(IncomingEdge)); 73384e3515974407a606289c6e762a0419723b7918fDevang Patel 734cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman Value *NewAdd = BinaryOperator::CreateAdd(NewPHI, 7351d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson ConstantInt::get(Type::getInt32Ty(PH->getContext()), 736cd40233429fce385ae4b22301ce705273a6951a1Devang Patel newIncrValue), 73784e3515974407a606289c6e762a0419723b7918fDevang Patel Incr->getName()+".int", Incr); 73884e3515974407a606289c6e762a0419723b7918fDevang Patel NewPHI->addIncoming(NewAdd, PH->getIncomingBlock(BackEdge)); 73984e3515974407a606289c6e762a0419723b7918fDevang Patel 740617d108a639b29015da2dbf0e54f61bd39c3c33cDale Johannesen // The back edge is edge 1 of newPHI, whatever it may have been in the 741617d108a639b29015da2dbf0e54f61bd39c3c33cDale Johannesen // original PHI. 7421d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson ConstantInt *NewEV = ConstantInt::get(Type::getInt32Ty(PH->getContext()), 7431d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson intEV); 744617d108a639b29015da2dbf0e54f61bd39c3c33cDale Johannesen Value *LHS = (EVIndex == 1 ? NewPHI->getIncomingValue(1) : NewEV); 745617d108a639b29015da2dbf0e54f61bd39c3c33cDale Johannesen Value *RHS = (EVIndex == 1 ? NewEV : NewPHI->getIncomingValue(1)); 746333c40096561218bc3597cf153c0a3895274414cOwen Anderson ICmpInst *NewEC = new ICmpInst(EC->getParent()->getTerminator(), 747460f656475738d1a95a6be95346908ce1597df25Daniel Dunbar NewPred, LHS, RHS, EC->getName()); 748cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 74981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // In the following deltions, PH may become dead and may be deleted. 75081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Use a WeakVH to observe whether this happens. 75181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman WeakVH WeakPH = PH; 75281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 75384e3515974407a606289c6e762a0419723b7918fDevang Patel // Delete old, floating point, exit comparision instruction. 75414fba294e1f2d619fe50b72d5fd88da2b17461ddDan Gohman NewEC->takeName(EC); 75584e3515974407a606289c6e762a0419723b7918fDevang Patel EC->replaceAllUsesWith(NewEC); 75681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman RecursivelyDeleteTriviallyDeadInstructions(EC); 757cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 75884e3515974407a606289c6e762a0419723b7918fDevang Patel // Delete old, floating point, increment instruction. 7599e9a0d5fc26878e51a58a8b57900fcbf952c2691Owen Anderson Incr->replaceAllUsesWith(UndefValue::get(Incr->getType())); 76081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman RecursivelyDeleteTriviallyDeadInstructions(Incr); 76181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 76281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Replace floating induction variable, if it isn't already deleted. 76381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Give SIToFPInst preference over UIToFPInst because it is faster on 76481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // platforms that are widely used. 76581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (WeakPH && !PH->use_empty()) { 76681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (useSIToFPInst(*InitValue, *EV, newInitValue, intEV)) { 76781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman SIToFPInst *Conv = new SIToFPInst(NewPHI, PH->getType(), "indvar.conv", 76881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman PH->getParent()->getFirstNonPHI()); 76981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman PH->replaceAllUsesWith(Conv); 77081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman } else { 77181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman UIToFPInst *Conv = new UIToFPInst(NewPHI, PH->getType(), "indvar.conv", 77281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman PH->getParent()->getFirstNonPHI()); 77381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman PH->replaceAllUsesWith(Conv); 77481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman } 77581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman RecursivelyDeleteTriviallyDeadInstructions(PH); 776cd40233429fce385ae4b22301ce705273a6951a1Devang Patel } 77758d43d4a41b21085c063bdd21a2abb68056e2a6fDevang Patel 77881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Add a new IVUsers entry for the newly-created integer PHI. 77981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman IU->AddUsersIfInteresting(NewPHI); 78081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman} 781