IndVarSimplify.cpp revision bae7d6dbeb842b5ed051c50a87bc282f2dec6e1f
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. 2040bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner// 3. Any pointer arithmetic recurrences are raised to use array subscripts. 2140bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner// 2240bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner// If the trip count of a loop is computable, this pass also makes the following 2340bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner// changes: 2440bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner// 1. The exit condition for the loop is canonicalized to compare the 2540bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner// induction value against the exit value. This turns loops like: 2640bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner// 'for (i = 7; i*i < 1000; ++i)' into 'for (i = 0; i != 25; ++i)' 2740bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner// 2. Any use outside of the loop of an expression derived from the indvar 2840bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner// is changed to compute the derived value outside of the loop, eliminating 2940bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner// the dependence on the exit value of the induction variable. If the only 3040bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner// purpose of the loop is to compute the exit value of some derived 3140bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner// expression, this transformation will make the loop dead. 3240bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner// 3340bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner// This transformation should be followed by strength reduction after all of the 3440bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner// desired loop transformations have been performed. Additionally, on targets 3540bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner// where it is profitable, the loop could be transformed to count down to zero 3640bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner// (the "do loop" optimization). 376148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner// 386148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner//===----------------------------------------------------------------------===// 396148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner 400e5f499638c8d277b9dc4a4385712177c53b5681Chris Lattner#define DEBUG_TYPE "indvars" 41022103b3f33febb7e54b8fdf2c9bc461eea78cbaChris Lattner#include "llvm/Transforms/Scalar.h" 4240bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner#include "llvm/BasicBlock.h" 4359fdaeeae8f183e18bb6ad5c382ca23e28e6aaf6Chris Lattner#include "llvm/Constants.h" 4418b3c97bc773b24a66eb779e85da1820b0f16b31Chris Lattner#include "llvm/Instructions.h" 4540bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner#include "llvm/Type.h" 4681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman#include "llvm/Analysis/Dominators.h" 4781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman#include "llvm/Analysis/IVUsers.h" 4836f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman#include "llvm/Analysis/ScalarEvolutionExpander.h" 4947df12d80db90e125e9f2ff764286ee11665476dJohn Criswell#include "llvm/Analysis/LoopInfo.h" 505ee99979065d75605d150d7e567e4351024aae8fDevang Patel#include "llvm/Analysis/LoopPass.h" 51455889aa79e3463a4b0f2161e3d9d72a683268b6Chris Lattner#include "llvm/Support/CFG.h" 529133fe28954d498fc4de13064c7d65bd811de02cReid Spencer#include "llvm/Support/Compiler.h" 53ee4f13a9046c380725cdeab62d57722db375c473Chris Lattner#include "llvm/Support/Debug.h" 54a4b9c7841f94b6a3a2ba6c562b5dc4f4de02c637Chris Lattner#include "llvm/Support/GetElementPtrTypeIterator.h" 5547df12d80db90e125e9f2ff764286ee11665476dJohn Criswell#include "llvm/Transforms/Utils/Local.h" 5681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman#include "llvm/Transforms/Utils/BasicBlockUtils.h" 57551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/Support/CommandLine.h" 58a54b7cbd452b3adb2f51346140d996b29c2cdb30Reid Spencer#include "llvm/ADT/SmallVector.h" 59c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman#include "llvm/ADT/SetVector.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 { 705ee99979065d75605d150d7e567e4351024aae8fDevang Patel class VISIBILITY_HIDDEN IndVarSimplify : public LoopPass { 7181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman IVUsers *IU; 7240bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner LoopInfo *LI; 7340bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner ScalarEvolution *SE; 7415cad759fe2048ac5eb137c6bb0ab7287538677eChris Lattner bool Changed; 753324e718bc9ac2ede08a14c325848b576849542bChris Lattner public: 76794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel 77ecd94c804a563f2a86572dcf1d2e81f397e19daaNick Lewycky static char ID; // Pass identification, replacement for typeid 78ae73dc1448d25b02cabc7c64c86c64371453dda8Dan Gohman IndVarSimplify() : LoopPass(&ID) {} 79794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel 8060f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman virtual bool runOnLoop(Loop *L, LPPassManager &LPM); 8160f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman 825ee99979065d75605d150d7e567e4351024aae8fDevang Patel virtual void getAnalysisUsage(AnalysisUsage &AU) const { 8381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman AU.addRequired<DominatorTree>(); 84bc533cd1286ebb393c37a2a8b03079bfc9655585Devang Patel AU.addRequired<ScalarEvolution>(); 855ee99979065d75605d150d7e567e4351024aae8fDevang Patel AU.addRequiredID(LCSSAID); 865ee99979065d75605d150d7e567e4351024aae8fDevang Patel AU.addRequiredID(LoopSimplifyID); 875ee99979065d75605d150d7e567e4351024aae8fDevang Patel AU.addRequired<LoopInfo>(); 8881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman AU.addRequired<IVUsers>(); 89474cecf0e9bca95ab7091a341784550c7eb1e887Dan Gohman AU.addPreserved<ScalarEvolution>(); 905ee99979065d75605d150d7e567e4351024aae8fDevang Patel AU.addPreservedID(LoopSimplifyID); 9181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman AU.addPreserved<IVUsers>(); 925ee99979065d75605d150d7e567e4351024aae8fDevang Patel AU.addPreservedID(LCSSAID); 935ee99979065d75605d150d7e567e4351024aae8fDevang Patel AU.setPreservesCFG(); 945ee99979065d75605d150d7e567e4351024aae8fDevang Patel } 953324e718bc9ac2ede08a14c325848b576849542bChris Lattner 9640bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner private: 975ee99979065d75605d150d7e567e4351024aae8fDevang Patel 9860f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman void RewriteNonIntegerIVs(Loop *L); 9960f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman 10081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman ICmpInst *LinearFunctionTestReplace(Loop *L, SCEVHandle BackedgeTakenCount, 101a575871884b247b0946290876ac7d4657b384cf9Dan Gohman Value *IndVar, 102c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman BasicBlock *ExitingBlock, 103c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman BranchInst *BI, 10415cab2817b8f63fec0148609278bc2c1e05abb50Dan Gohman SCEVExpander &Rewriter); 105890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman void RewriteLoopExitValues(Loop *L, const SCEV *BackedgeTakenCount); 10640bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner 10781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman void RewriteIVExpressions(Loop *L, const Type *LargestType, 10881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman SCEVExpander &Rewriter); 109d22a849282c45bbf7eb1734c274294d81e49e3a8Devang Patel 11081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman void SinkUnusedInvariants(Loop *L, SCEVExpander &Rewriter); 11181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 11281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman void FixUsesBeforeDefs(Loop *L, SCEVExpander &Rewriter); 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, 13246bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman SCEVHandle 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; 14146bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman SCEVHandle 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. 14646bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman SCEVHandle Zero = SE->getIntegerSCEV(0, BackedgeTakenCount->getType()); 147c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman SCEVHandle N = 14846bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman SE->getAddExpr(BackedgeTakenCount, 14946bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman SE->getIntegerSCEV(1, BackedgeTakenCount->getType())); 150c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman if ((isa<SCEVConstant>(N) && !N->isZero()) || 151c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman SE->isLoopGuardedByCond(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 17340bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // Expand the code for the iteration count into the preheader of the loop. 17440bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner BasicBlock *Preheader = L->getLoopPreheader(); 1752d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman Value *ExitCnt = Rewriter.expandCodeFor(RHS, IndVar->getType(), 176c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman Preheader->getTerminator()); 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 185c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman DOUT << "INDVARS: Rewriting loop exit condition to:\n" 186c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman << " LHS:" << *CmpIndVar // includes a newline 187c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman << " op:\t" 188f108e2eaaa788272a3ced1eef1bbb84f0d03b60cDan Gohman << (Opcode == ICmpInst::ICMP_NE ? "!=" : "==") << "\n" 18946bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman << " RHS:\t" << *RHS << "\n"; 190c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman 19181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman ICmpInst *Cond = new ICmpInst(Opcode, CmpIndVar, ExitCnt, "exitcond", BI); 19281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 19381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman Instruction *OrigCond = cast<Instruction>(BI->getCondition()); 19481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman OrigCond->replaceAllUsesWith(Cond); 19581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman RecursivelyDeleteTriviallyDeadInstructions(OrigCond); 19681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 19740bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner ++NumLFTR; 19840bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner Changed = true; 19981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman return Cond; 20040bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner} 2013324e718bc9ac2ede08a14c325848b576849542bChris Lattner 20240bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner/// RewriteLoopExitValues - Check to see if this loop has a computable 20340bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner/// loop-invariant execution count. If so, this means that we can compute the 20440bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner/// final value of any expressions that are recurrent in the loop, and 20540bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner/// substitute the exit values from the loop into any instructions outside of 20640bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner/// the loop that use the final values of the current expressions. 20781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman/// 20881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman/// This is mostly redundant with the regular IndVarSimplify activities that 20981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman/// happen later, except that it's more powerful in some cases, because it's 21081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman/// able to brute-force evaluate arbitrary instructions as long as they have 21181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman/// constant operands at the beginning of the loop. 212890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohmanvoid IndVarSimplify::RewriteLoopExitValues(Loop *L, 213890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman const SCEV *BackedgeTakenCount) { 21481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Verify the input to the pass in already in LCSSA form. 21581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman assert(L->isLCSSAForm()); 21681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 21740bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner BasicBlock *Preheader = L->getLoopPreheader(); 21840bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner 21940bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // Scan all of the instructions in the loop, looking at those that have 22040bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // extra-loop users and which are recurrences. 221af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman SCEVExpander Rewriter(*SE, *LI); 22240bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner 22340bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // We insert the code into the preheader of the loop if the loop contains 22440bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // multiple exit blocks, or in the exit block if there is exactly one. 22540bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner BasicBlock *BlockToInsertInto; 226b7211a2ce13a0365e0e1dd2f27adda2ee3d1288bDevang Patel SmallVector<BasicBlock*, 8> ExitBlocks; 2279f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner L->getUniqueExitBlocks(ExitBlocks); 228f1ab4b4eac5603d19c20f4a508f93a118a52bdd5Chris Lattner if (ExitBlocks.size() == 1) 229f1ab4b4eac5603d19c20f4a508f93a118a52bdd5Chris Lattner BlockToInsertInto = ExitBlocks[0]; 23040bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner else 23140bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner BlockToInsertInto = Preheader; 23202dea8b39f3acad5de1df36273444d149145e7fcDan Gohman BasicBlock::iterator InsertPt = BlockToInsertInto->getFirstNonPHI(); 23340bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner 2349f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner std::map<Instruction*, Value*> ExitValues; 2359f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner 2369f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // Find all values that are computed inside the loop, but used outside of it. 2379f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // Because of LCSSA, these values will only occur in LCSSA PHI Nodes. Scan 2389f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // the exit blocks of the loop to find them. 2399f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) { 2409f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner BasicBlock *ExitBB = ExitBlocks[i]; 241cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 2429f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // If there are no PHI nodes in this exit block, then no values defined 2439f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // inside the loop are used on this path, skip it. 2449f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner PHINode *PN = dyn_cast<PHINode>(ExitBB->begin()); 2459f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner if (!PN) continue; 246cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 2479f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner unsigned NumPreds = PN->getNumIncomingValues(); 248cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 2499f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // Iterate over all of the PHI nodes. 2509f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner BasicBlock::iterator BBI = ExitBB->begin(); 2519f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner while ((PN = dyn_cast<PHINode>(BBI++))) { 252cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 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); 2589f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner if (!isa<Instruction>(InVal) || 2599f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // SCEV only supports integer expressions for now. 2602d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman (!isa<IntegerType>(InVal->getType()) && 2612d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman !isa<PointerType>(InVal->getType()))) 2629f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner continue; 2639f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner 2649f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // If this pred is for a subloop, not L itself, skip it. 265cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman if (LI->getLoopFor(PN->getIncomingBlock(i)) != L) 2669f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner continue; // The Block is in a subloop, skip it. 2679f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner 2689f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // Check that InVal is defined in the loop. 2699f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner Instruction *Inst = cast<Instruction>(InVal); 2709f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner if (!L->contains(Inst->getParent())) 2719f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner continue; 272cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 2739f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // Okay, this instruction has a user outside of the current loop 2749f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // and varies predictably *inside* the loop. Evaluate the value it 2759f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // contains when the loop exits, if possible. 27681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman SCEVHandle SH = SE->getSCEV(Inst); 27781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman SCEVHandle ExitValue = SE->getSCEVAtScope(SH, L->getParentLoop()); 2789f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner if (isa<SCEVCouldNotCompute>(ExitValue) || 2799f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner !ExitValue->isLoopInvariant(L)) 2809f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner continue; 2819f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner 2829f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner Changed = true; 2839f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner ++NumReplaced; 284cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 2859f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // See if we already computed the exit value for the instruction, if so, 2869f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // just reuse it. 2879f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner Value *&ExitVal = ExitValues[Inst]; 2889f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner if (!ExitVal) 2892d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman ExitVal = Rewriter.expandCodeFor(ExitValue, PN->getType(), InsertPt); 290cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 2919f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner DOUT << "INDVARS: RLEV: AfterLoopVal = " << *ExitVal 2929f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner << " LoopVal = " << *Inst << "\n"; 2939caed5440d59dac4b388152fe8b993dc0491e5e9Chris Lattner 2949f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner PN->setIncomingValue(i, ExitVal); 295cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 29681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // If this instruction is dead now, delete it. 29781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman RecursivelyDeleteTriviallyDeadInstructions(Inst); 298cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 2999f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // See if this is a single-entry LCSSA PHI node. If so, we can (and 3009f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // have to) remove 3019caed5440d59dac4b388152fe8b993dc0491e5e9Chris Lattner // the PHI entirely. This is safe, because the NewVal won't be variant 3029caed5440d59dac4b388152fe8b993dc0491e5e9Chris Lattner // in the loop, so we don't need an LCSSA phi node anymore. 3039f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner if (NumPreds == 1) { 3049f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner PN->replaceAllUsesWith(ExitVal); 30581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman RecursivelyDeleteTriviallyDeadInstructions(PN); 3069f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner break; 307c9838f25d53d3dd7d38949ef6c28f2505a110f45Chris Lattner } 3084bd09d70cceb3851f7eb1c2f98338b3071d405f3Chris Lattner } 309c9838f25d53d3dd7d38949ef6c28f2505a110f45Chris Lattner } 310c9838f25d53d3dd7d38949ef6c28f2505a110f45Chris Lattner } 31140bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner} 31215cad759fe2048ac5eb137c6bb0ab7287538677eChris Lattner 31360f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohmanvoid IndVarSimplify::RewriteNonIntegerIVs(Loop *L) { 3142d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman // First step. Check to see if there are any floating-point recurrences. 31540bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // If there are, change them into integer recurrences, permitting analysis by 31640bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // the SCEV routines. 31715cad759fe2048ac5eb137c6bb0ab7287538677eChris Lattner // 31840bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner BasicBlock *Header = L->getHeader(); 319fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 32081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman SmallVector<WeakVH, 8> PHIs; 32181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman for (BasicBlock::iterator I = Header->begin(); 32281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman PHINode *PN = dyn_cast<PHINode>(I); ++I) 32381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman PHIs.push_back(PN); 32481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 32581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman for (unsigned i = 0, e = PHIs.size(); i != e; ++i) 32681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (PHINode *PN = dyn_cast_or_null<PHINode>(PHIs[i])) 32781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman HandleFloatingPointIV(L, PN); 32815cad759fe2048ac5eb137c6bb0ab7287538677eChris Lattner 3292d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman // If the loop previously had floating-point IV, ScalarEvolution 33060f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman // may not have been able to compute a trip count. Now that we've done some 33160f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman // re-writing, the trip count may be computable. 33260f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman if (Changed) 33346bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman SE->forgetLoopBackedgeTakenCount(L); 334c671d892ab1d3d8fed18a61f66f3f3a86e73ebd9Dale Johannesen} 335c671d892ab1d3d8fed18a61f66f3f3a86e73ebd9Dale Johannesen 336c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohmanbool IndVarSimplify::runOnLoop(Loop *L, LPPassManager &LPM) { 33781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman IU = &getAnalysis<IVUsers>(); 3385ee99979065d75605d150d7e567e4351024aae8fDevang Patel LI = &getAnalysis<LoopInfo>(); 3395ee99979065d75605d150d7e567e4351024aae8fDevang Patel SE = &getAnalysis<ScalarEvolution>(); 3405ee99979065d75605d150d7e567e4351024aae8fDevang Patel Changed = false; 34160f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman 3422d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman // If there are any floating-point recurrences, attempt to 34360f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman // transform them to use integer recurrences. 34460f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman RewriteNonIntegerIVs(L); 34560f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman 346c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman BasicBlock *Header = L->getHeader(); 34781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman BasicBlock *ExitingBlock = L->getExitingBlock(); // may be null 34881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman SCEVHandle BackedgeTakenCount = SE->getBackedgeTakenCount(L); 3499caed5440d59dac4b388152fe8b993dc0491e5e9Chris Lattner 35040bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // Check to see if this loop has a computable loop-invariant execution count. 35140bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // If so, this means that we can compute the final value of any expressions 35240bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // that are recurrent in the loop, and substitute the exit values from the 35340bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // loop into any instructions outside of the loop that use the final values of 35440bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // the current expressions. 355394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner // 35646bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman if (!isa<SCEVCouldNotCompute>(BackedgeTakenCount)) 35746bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman RewriteLoopExitValues(L, BackedgeTakenCount); 35840bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner 35981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Compute the type of the largest recurrence expression, and decide whether 36081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // a canonical induction variable should be inserted. 361c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman const Type *LargestType = 0; 36281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman bool NeedCannIV = false; 36346bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman if (!isa<SCEVCouldNotCompute>(BackedgeTakenCount)) { 36446bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman LargestType = BackedgeTakenCount->getType(); 365af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman LargestType = SE->getEffectiveSCEVType(LargestType); 36681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // If we have a known trip count and a single exit block, we'll be 36781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // rewriting the loop exit test condition below, which requires a 36881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // canonical induction variable. 36981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (ExitingBlock) 37081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman NeedCannIV = true; 371f50af088f19f525f3d1026eb61db77e0037a9f43Chris Lattner } 37281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman for (unsigned i = 0, e = IU->StrideOrder.size(); i != e; ++i) { 37381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman SCEVHandle Stride = IU->StrideOrder[i]; 37481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman const Type *Ty = SE->getEffectiveSCEVType(Stride->getType()); 375c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman if (!LargestType || 37681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman SE->getTypeSizeInBits(Ty) > 377af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman SE->getTypeSizeInBits(LargestType)) 37881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman LargestType = Ty; 37981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 38081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman std::map<SCEVHandle, IVUsersOfOneStride *>::iterator SI = 38181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman IU->IVUsesByStride.find(IU->StrideOrder[i]); 38281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman assert(SI != IU->IVUsesByStride.end() && "Stride doesn't exist!"); 38381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 38481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (!SI->second->Users.empty()) 38581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman NeedCannIV = true; 386500597a1c39e91a3020587318ed61e737b6c613aChris Lattner } 387394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner 38840bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // Create a rewriter object which we'll use to transform the code with. 389af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman SCEVExpander Rewriter(*SE, *LI); 39040bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner 39181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Now that we know the largest of of the induction variable expressions 39281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // in this loop, insert a canonical induction variable of the largest size. 393c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman Value *IndVar = 0; 39481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (NeedCannIV) { 395c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman IndVar = Rewriter.getOrInsertCanonicalInductionVariable(L,LargestType); 396c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman ++NumInserted; 397c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman Changed = true; 398c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman DOUT << "INDVARS: New CanIV: " << *IndVar; 399d19534add90a2a894af61523b830887097bb780bDan Gohman } 40040bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner 401c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman // If we have a trip count expression, rewrite the loop's exit condition 402c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman // using it. We can currently only handle loops with a single exit. 40381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman ICmpInst *NewICmp = 0; 40481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (!isa<SCEVCouldNotCompute>(BackedgeTakenCount) && ExitingBlock) { 40581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman assert(NeedCannIV && 40681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman "LinearFunctionTestReplace requires a canonical induction variable"); 407c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman // Can't rewrite non-branch yet. 40881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (BranchInst *BI = dyn_cast<BranchInst>(ExitingBlock->getTerminator())) 40981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman NewICmp = LinearFunctionTestReplace(L, BackedgeTakenCount, IndVar, 41081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman ExitingBlock, BI, Rewriter); 41181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman } 412c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman 41381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman Rewriter.setInsertionPoint(Header->getFirstNonPHI()); 414c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman 41581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Rewrite IV-derived expressions. 41681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman RewriteIVExpressions(L, LargestType, Rewriter); 417fcb81f5f4cbac61851b7dec403961cf88e614aa1Chris Lattner 41881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Loop-invariant instructions in the preheader that aren't used in the 41981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // loop may be sunk below the loop to reduce register pressure. 42081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman SinkUnusedInvariants(L, Rewriter); 42181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 42281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Reorder instructions to avoid use-before-def conditions. 42381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman FixUsesBeforeDefs(L, Rewriter); 42481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 42581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // For completeness, inform IVUsers of the IV use in the newly-created 42681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // loop exit test instruction. 42781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (NewICmp) 42881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman IU->AddUsersIfInteresting(cast<Instruction>(NewICmp->getOperand(0))); 42981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 43081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Clean up dead instructions. 43181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman DeleteDeadPHIs(L->getHeader()); 43281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Check a post-condition. 43381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman assert(L->isLCSSAForm() && "Indvars did not leave the loop in lcssa form!"); 43481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman return Changed; 43581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman} 43681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 43781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohmanvoid IndVarSimplify::RewriteIVExpressions(Loop *L, const Type *LargestType, 43881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman SCEVExpander &Rewriter) { 43981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman SmallVector<WeakVH, 16> DeadInsts; 44081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 44181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Rewrite all induction variable expressions in terms of the canonical 44281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // induction variable. 44381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // 44481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // If there were induction variables of other sizes or offsets, manually 44581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // add the offsets to the primary induction variable and cast, avoiding 44681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // the need for the code evaluation methods to insert induction variables 44781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // of different sizes. 44881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman for (unsigned i = 0, e = IU->StrideOrder.size(); i != e; ++i) { 44981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman SCEVHandle Stride = IU->StrideOrder[i]; 45081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 45181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman std::map<SCEVHandle, IVUsersOfOneStride *>::iterator SI = 45281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman IU->IVUsesByStride.find(IU->StrideOrder[i]); 45381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman assert(SI != IU->IVUsesByStride.end() && "Stride doesn't exist!"); 45481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman ilist<IVStrideUse> &List = SI->second->Users; 45581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman for (ilist<IVStrideUse>::iterator UI = List.begin(), 45681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman E = List.end(); UI != E; ++UI) { 45781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman SCEVHandle Offset = UI->getOffset(); 45881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman Value *Op = UI->getOperandValToReplace(); 45981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman Instruction *User = UI->getUser(); 46081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman bool isSigned = UI->isSigned(); 46181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 46281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Compute the final addrec to expand into code. 46381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman SCEVHandle AR = IU->getReplacementExpr(*UI); 46481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 46581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // FIXME: It is an extremely bad idea to indvar substitute anything more 46681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // complex than affine induction variables. Doing so will put expensive 46781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // polynomial evaluations inside of the loop, and the str reduction pass 46881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // currently can only reduce affine polynomials. For now just disable 46981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // indvar subst on anything more complex than an affine addrec, unless 47081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // it can be expanded to a trivial value. 47181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (!Stride->isLoopInvariant(L) && 47281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman !isa<SCEVConstant>(AR) && 47381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman L->contains(User->getParent())) 47481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman continue; 47581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 47681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman Value *NewVal = 0; 47781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (AR->isLoopInvariant(L)) { 47881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman BasicBlock::iterator I = Rewriter.getInsertionPoint(); 47981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Expand loop-invariant values in the loop preheader. They will 48081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // be sunk to the exit block later, if possible. 48181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman NewVal = 48281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman Rewriter.expandCodeFor(AR, LargestType, 48381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman L->getLoopPreheader()->getTerminator()); 48481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman Rewriter.setInsertionPoint(I); 48581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman ++NumReplaced; 48681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman } else { 48781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman const Type *IVTy = Offset->getType(); 48881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman const Type *UseTy = Op->getType(); 48981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 49081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Promote the Offset and Stride up to the canonical induction 49181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // variable's bit width. 49281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman SCEVHandle PromotedOffset = Offset; 49381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman SCEVHandle PromotedStride = Stride; 49481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (SE->getTypeSizeInBits(IVTy) != SE->getTypeSizeInBits(LargestType)) { 49581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // It doesn't matter for correctness whether zero or sign extension 49681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // is used here, since the value is truncated away below, but if the 49781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // value is signed, sign extension is more likely to be folded. 49881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (isSigned) { 49981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman PromotedOffset = SE->getSignExtendExpr(PromotedOffset, LargestType); 50081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman PromotedStride = SE->getSignExtendExpr(PromotedStride, LargestType); 50181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman } else { 50281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman PromotedOffset = SE->getZeroExtendExpr(PromotedOffset, LargestType); 50381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // If the stride is obviously negative, use sign extension to 50481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // produce things like x-1 instead of x+255. 50581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (isa<SCEVConstant>(PromotedStride) && 50681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman cast<SCEVConstant>(PromotedStride) 50781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman ->getValue()->getValue().isNegative()) 50881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman PromotedStride = SE->getSignExtendExpr(PromotedStride, 50981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman LargestType); 51081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman else 51181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman PromotedStride = SE->getZeroExtendExpr(PromotedStride, 51281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman LargestType); 513c671d892ab1d3d8fed18a61f66f3f3a86e73ebd9Dale Johannesen } 514d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen } 51581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 51681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Create the SCEV representing the offset from the canonical 51781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // induction variable, still in the canonical induction variable's 51881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // type, so that all expanded arithmetic is done in the same type. 51981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman SCEVHandle NewAR = SE->getAddRecExpr(SE->getIntegerSCEV(0, LargestType), 52081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman PromotedStride, L); 52181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Add the PromotedOffset as a separate step, because it may not be 52281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // loop-invariant. 52381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman NewAR = SE->getAddExpr(NewAR, PromotedOffset); 52481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 52581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Expand the addrec into instructions. 52681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman Value *V = Rewriter.expandCodeFor(NewAR, LargestType); 52781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 52881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Insert an explicit cast if necessary to truncate the value 52981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // down to the original stride type. This is done outside of 53081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // SCEVExpander because in SCEV expressions, a truncate of an 53181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // addrec is always folded. 53281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (LargestType != IVTy) { 53381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (SE->getTypeSizeInBits(IVTy) != SE->getTypeSizeInBits(LargestType)) 53481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman NewAR = SE->getTruncateExpr(NewAR, IVTy); 53581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (Rewriter.isInsertedExpression(NewAR)) 53681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman V = Rewriter.expandCodeFor(NewAR, IVTy); 53781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman else { 53881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman V = Rewriter.InsertCastOfTo(CastInst::getCastOpcode(V, false, 53981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman IVTy, false), 54081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman V, IVTy); 54181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman assert(!isa<SExtInst>(V) && !isa<ZExtInst>(V) && 54281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman "LargestType wasn't actually the largest type!"); 54381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Force the rewriter to use this trunc whenever this addrec 54481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // appears so that it doesn't insert new phi nodes or 54581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // arithmetic in a different type. 54681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman Rewriter.addInsertedValue(V, NewAR); 547d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen } 548aa03649af255fbbb049f393a2cf7d533da86d951Dan Gohman } 54981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 55081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman DOUT << "INDVARS: Made offset-and-trunc IV for offset " 55181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman << *IVTy << " " << *Offset << ": "; 55281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman DEBUG(WriteAsOperand(*DOUT, V, false)); 55381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman DOUT << "\n"; 55481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 55581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Now expand it into actual Instructions and patch it into place. 55681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman NewVal = Rewriter.expandCodeFor(AR, UseTy); 557aa03649af255fbbb049f393a2cf7d533da86d951Dan Gohman } 558c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman 55981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Patch the new value into place. 56081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (Op->hasName()) 56181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman NewVal->takeName(Op); 56281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman User->replaceUsesOfWith(Op, NewVal); 56381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman UI->setOperandValToReplace(NewVal); 56481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman DOUT << "INDVARS: Rewrote IV '" << *AR << "' " << *Op 56581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman << " into = " << *NewVal << "\n"; 56681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman ++NumRemoved; 56781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman Changed = true; 56881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 56981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // The old value may be dead now. 57081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman DeadInsts.push_back(Op); 57181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman } 572500597a1c39e91a3020587318ed61e737b6c613aChris Lattner } 573ba4f3f6a419326df190599421fa149c90235cb72Chris Lattner 57481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Now that we're done iterating through lists, clean up any instructions 57581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // which are now dead. 57681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman while (!DeadInsts.empty()) { 57781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman Instruction *Inst = dyn_cast_or_null<Instruction>(DeadInsts.pop_back_val()); 57881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (Inst) 57981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman RecursivelyDeleteTriviallyDeadInstructions(Inst); 58081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman } 58181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman} 58281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 58381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman/// If there's a single exit block, sink any loop-invariant values that 58481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman/// were defined in the preheader but not used inside the loop into the 58581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman/// exit block to reduce register pressure in the loop. 58681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohmanvoid IndVarSimplify::SinkUnusedInvariants(Loop *L, SCEVExpander &Rewriter) { 58781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman BasicBlock *ExitBlock = L->getExitBlock(); 58881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (!ExitBlock) return; 58981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 59081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman Instruction *NonPHI = ExitBlock->getFirstNonPHI(); 59181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman BasicBlock *Preheader = L->getLoopPreheader(); 59281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman BasicBlock::iterator I = Preheader->getTerminator(); 59381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman while (I != Preheader->begin()) { 59481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman --I; 59581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // New instructions were inserted at the end of the preheader. Only 59681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // consider those new instructions. 59781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (!Rewriter.isInsertedInstruction(I)) 59881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman break; 59981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Determine if there is a use in or before the loop (direct or 60081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // otherwise). 60181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman bool UsedInLoop = false; 60281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman for (Value::use_iterator UI = I->use_begin(), UE = I->use_end(); 60381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman UI != UE; ++UI) { 60481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman BasicBlock *UseBB = cast<Instruction>(UI)->getParent(); 60581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (PHINode *P = dyn_cast<PHINode>(UI)) { 60681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman unsigned i = 60781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman PHINode::getIncomingValueNumForOperand(UI.getOperandNo()); 60881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman UseBB = P->getIncomingBlock(i); 60981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman } 61081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (UseBB == Preheader || L->contains(UseBB)) { 61181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman UsedInLoop = true; 61281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman break; 61381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman } 61481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman } 61581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // If there is, the def must remain in the preheader. 61681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (UsedInLoop) 61781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman continue; 61881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Otherwise, sink it to the exit block. 61981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman Instruction *ToMove = I; 62081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman bool Done = false; 62181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (I != Preheader->begin()) 62281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman --I; 62381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman else 62481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman Done = true; 62581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman ToMove->moveBefore(NonPHI); 62681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (Done) 62781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman break; 62881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman } 62981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman} 63081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 63181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman/// Re-schedule the inserted instructions to put defs before uses. This 63281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman/// fixes problems that arrise when SCEV expressions contain loop-variant 63381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman/// values unrelated to the induction variable which are defined inside the 63481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman/// loop. FIXME: It would be better to insert instructions in the right 63581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman/// place so that this step isn't needed. 63681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohmanvoid IndVarSimplify::FixUsesBeforeDefs(Loop *L, SCEVExpander &Rewriter) { 63781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Visit all the blocks in the loop in pre-order dom-tree dfs order. 63881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman DominatorTree *DT = &getAnalysis<DominatorTree>(); 63981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman std::map<Instruction *, unsigned> NumPredsLeft; 64081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman SmallVector<DomTreeNode *, 16> Worklist; 64181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman Worklist.push_back(DT->getNode(L->getHeader())); 64281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman do { 64381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman DomTreeNode *Node = Worklist.pop_back_val(); 64481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman for (DomTreeNode::iterator I = Node->begin(), E = Node->end(); I != E; ++I) 64581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (L->contains((*I)->getBlock())) 64681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman Worklist.push_back(*I); 64781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman BasicBlock *BB = Node->getBlock(); 64881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Visit all the instructions in the block top down. 64981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) { 65081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Count the number of operands that aren't properly dominating. 65181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman unsigned NumPreds = 0; 65281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (Rewriter.isInsertedInstruction(I) && !isa<PHINode>(I)) 65381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman for (User::op_iterator OI = I->op_begin(), OE = I->op_end(); 65481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman OI != OE; ++OI) 65581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (Instruction *Inst = dyn_cast<Instruction>(OI)) 65681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (L->contains(Inst->getParent()) && !NumPredsLeft.count(Inst)) 65781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman ++NumPreds; 65881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman NumPredsLeft[I] = NumPreds; 65981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Notify uses of the position of this instruction, and move the 66081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // users (and their dependents, recursively) into place after this 66181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // instruction if it is their last outstanding operand. 66281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman for (Value::use_iterator UI = I->use_begin(), UE = I->use_end(); 66381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman UI != UE; ++UI) { 66481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman Instruction *Inst = cast<Instruction>(UI); 66581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman std::map<Instruction *, unsigned>::iterator Z = NumPredsLeft.find(Inst); 66681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (Z != NumPredsLeft.end() && Z->second != 0 && --Z->second == 0) { 66781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman SmallVector<Instruction *, 4> UseWorkList; 66881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman UseWorkList.push_back(Inst); 66981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman BasicBlock::iterator InsertPt = next(I); 67081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman while (isa<PHINode>(InsertPt)) ++InsertPt; 67181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman do { 67281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman Instruction *Use = UseWorkList.pop_back_val(); 67381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman Use->moveBefore(InsertPt); 67481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman NumPredsLeft.erase(Use); 67581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman for (Value::use_iterator IUI = Use->use_begin(), 67681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman IUE = Use->use_end(); IUI != IUE; ++IUI) { 67781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman Instruction *IUIInst = cast<Instruction>(IUI); 67881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (L->contains(IUIInst->getParent()) && 67981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman Rewriter.isInsertedInstruction(IUIInst) && 68081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman !isa<PHINode>(IUIInst)) 68181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman UseWorkList.push_back(IUIInst); 68281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman } 68381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman } while (!UseWorkList.empty()); 68481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman } 68581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman } 68681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman } 68781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman } while (!Worklist.empty()); 6886148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner} 689d22a849282c45bbf7eb1734c274294d81e49e3a8Devang Patel 69013877bf6c20621541ff71583c626bda68ef09219Devang Patel/// Return true if it is OK to use SIToFPInst for an inducation variable 69113877bf6c20621541ff71583c626bda68ef09219Devang Patel/// with given inital and exit values. 69213877bf6c20621541ff71583c626bda68ef09219Devang Patelstatic bool useSIToFPInst(ConstantFP &InitV, ConstantFP &ExitV, 69313877bf6c20621541ff71583c626bda68ef09219Devang Patel uint64_t intIV, uint64_t intEV) { 69413877bf6c20621541ff71583c626bda68ef09219Devang Patel 695cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman if (InitV.getValueAPF().isNegative() || ExitV.getValueAPF().isNegative()) 69613877bf6c20621541ff71583c626bda68ef09219Devang Patel return true; 69713877bf6c20621541ff71583c626bda68ef09219Devang Patel 69813877bf6c20621541ff71583c626bda68ef09219Devang Patel // If the iteration range can be handled by SIToFPInst then use it. 69913877bf6c20621541ff71583c626bda68ef09219Devang Patel APInt Max = APInt::getSignedMaxValue(32); 700bae7d6dbeb842b5ed051c50a87bc282f2dec6e1fDale Johannesen if (Max.getZExtValue() > static_cast<uint64_t>(abs64(intEV - intIV))) 70113877bf6c20621541ff71583c626bda68ef09219Devang Patel return true; 702cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 70313877bf6c20621541ff71583c626bda68ef09219Devang Patel return false; 70413877bf6c20621541ff71583c626bda68ef09219Devang Patel} 70513877bf6c20621541ff71583c626bda68ef09219Devang Patel 70613877bf6c20621541ff71583c626bda68ef09219Devang Patel/// convertToInt - Convert APF to an integer, if possible. 707cd40233429fce385ae4b22301ce705273a6951a1Devang Patelstatic bool convertToInt(const APFloat &APF, uint64_t *intVal) { 708cd40233429fce385ae4b22301ce705273a6951a1Devang Patel 709cd40233429fce385ae4b22301ce705273a6951a1Devang Patel bool isExact = false; 710794a7dbce030f93315b1305f83a374232f09bba5Evan Cheng if (&APF.getSemantics() == &APFloat::PPCDoubleDouble) 711794a7dbce030f93315b1305f83a374232f09bba5Evan Cheng return false; 712cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman if (APF.convertToInteger(intVal, 32, APF.isNegative(), 713cd40233429fce385ae4b22301ce705273a6951a1Devang Patel APFloat::rmTowardZero, &isExact) 714cd40233429fce385ae4b22301ce705273a6951a1Devang Patel != APFloat::opOK) 715cd40233429fce385ae4b22301ce705273a6951a1Devang Patel return false; 716cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman if (!isExact) 717cd40233429fce385ae4b22301ce705273a6951a1Devang Patel return false; 718cd40233429fce385ae4b22301ce705273a6951a1Devang Patel return true; 719cd40233429fce385ae4b22301ce705273a6951a1Devang Patel 720cd40233429fce385ae4b22301ce705273a6951a1Devang Patel} 721cd40233429fce385ae4b22301ce705273a6951a1Devang Patel 72258d43d4a41b21085c063bdd21a2abb68056e2a6fDevang Patel/// HandleFloatingPointIV - If the loop has floating induction variable 72358d43d4a41b21085c063bdd21a2abb68056e2a6fDevang Patel/// then insert corresponding integer induction variable if possible. 72484e3515974407a606289c6e762a0419723b7918fDevang Patel/// For example, 72584e3515974407a606289c6e762a0419723b7918fDevang Patel/// for(double i = 0; i < 10000; ++i) 72684e3515974407a606289c6e762a0419723b7918fDevang Patel/// bar(i) 72784e3515974407a606289c6e762a0419723b7918fDevang Patel/// is converted into 72884e3515974407a606289c6e762a0419723b7918fDevang Patel/// for(int i = 0; i < 10000; ++i) 72984e3515974407a606289c6e762a0419723b7918fDevang Patel/// bar((double)i); 73084e3515974407a606289c6e762a0419723b7918fDevang Patel/// 73181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohmanvoid IndVarSimplify::HandleFloatingPointIV(Loop *L, PHINode *PH) { 73284e3515974407a606289c6e762a0419723b7918fDevang Patel 73384e3515974407a606289c6e762a0419723b7918fDevang Patel unsigned IncomingEdge = L->contains(PH->getIncomingBlock(0)); 73484e3515974407a606289c6e762a0419723b7918fDevang Patel unsigned BackEdge = IncomingEdge^1; 735cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 73684e3515974407a606289c6e762a0419723b7918fDevang Patel // Check incoming value. 737cd40233429fce385ae4b22301ce705273a6951a1Devang Patel ConstantFP *InitValue = dyn_cast<ConstantFP>(PH->getIncomingValue(IncomingEdge)); 738cd40233429fce385ae4b22301ce705273a6951a1Devang Patel if (!InitValue) return; 739cd40233429fce385ae4b22301ce705273a6951a1Devang Patel uint64_t newInitValue = Type::Int32Ty->getPrimitiveSizeInBits(); 740cd40233429fce385ae4b22301ce705273a6951a1Devang Patel if (!convertToInt(InitValue->getValueAPF(), &newInitValue)) 741cd40233429fce385ae4b22301ce705273a6951a1Devang Patel return; 742cd40233429fce385ae4b22301ce705273a6951a1Devang Patel 743cd40233429fce385ae4b22301ce705273a6951a1Devang Patel // Check IV increment. Reject this PH if increement operation is not 744cd40233429fce385ae4b22301ce705273a6951a1Devang Patel // an add or increment value can not be represented by an integer. 745cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman BinaryOperator *Incr = 74684e3515974407a606289c6e762a0419723b7918fDevang Patel dyn_cast<BinaryOperator>(PH->getIncomingValue(BackEdge)); 74784e3515974407a606289c6e762a0419723b7918fDevang Patel if (!Incr) return; 74884e3515974407a606289c6e762a0419723b7918fDevang Patel if (Incr->getOpcode() != Instruction::Add) return; 74984e3515974407a606289c6e762a0419723b7918fDevang Patel ConstantFP *IncrValue = NULL; 75084e3515974407a606289c6e762a0419723b7918fDevang Patel unsigned IncrVIndex = 1; 75184e3515974407a606289c6e762a0419723b7918fDevang Patel if (Incr->getOperand(1) == PH) 75284e3515974407a606289c6e762a0419723b7918fDevang Patel IncrVIndex = 0; 75384e3515974407a606289c6e762a0419723b7918fDevang Patel IncrValue = dyn_cast<ConstantFP>(Incr->getOperand(IncrVIndex)); 75484e3515974407a606289c6e762a0419723b7918fDevang Patel if (!IncrValue) return; 755cd40233429fce385ae4b22301ce705273a6951a1Devang Patel uint64_t newIncrValue = Type::Int32Ty->getPrimitiveSizeInBits(); 756cd40233429fce385ae4b22301ce705273a6951a1Devang Patel if (!convertToInt(IncrValue->getValueAPF(), &newIncrValue)) 757cd40233429fce385ae4b22301ce705273a6951a1Devang Patel return; 758cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 759cd40233429fce385ae4b22301ce705273a6951a1Devang Patel // Check Incr uses. One user is PH and the other users is exit condition used 760cd40233429fce385ae4b22301ce705273a6951a1Devang Patel // by the conditional terminator. 76184e3515974407a606289c6e762a0419723b7918fDevang Patel Value::use_iterator IncrUse = Incr->use_begin(); 76284e3515974407a606289c6e762a0419723b7918fDevang Patel Instruction *U1 = cast<Instruction>(IncrUse++); 76384e3515974407a606289c6e762a0419723b7918fDevang Patel if (IncrUse == Incr->use_end()) return; 76484e3515974407a606289c6e762a0419723b7918fDevang Patel Instruction *U2 = cast<Instruction>(IncrUse++); 76584e3515974407a606289c6e762a0419723b7918fDevang Patel if (IncrUse != Incr->use_end()) return; 766cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 76784e3515974407a606289c6e762a0419723b7918fDevang Patel // Find exit condition. 76884e3515974407a606289c6e762a0419723b7918fDevang Patel FCmpInst *EC = dyn_cast<FCmpInst>(U1); 76984e3515974407a606289c6e762a0419723b7918fDevang Patel if (!EC) 77084e3515974407a606289c6e762a0419723b7918fDevang Patel EC = dyn_cast<FCmpInst>(U2); 77184e3515974407a606289c6e762a0419723b7918fDevang Patel if (!EC) return; 77284e3515974407a606289c6e762a0419723b7918fDevang Patel 77384e3515974407a606289c6e762a0419723b7918fDevang Patel if (BranchInst *BI = dyn_cast<BranchInst>(EC->getParent()->getTerminator())) { 77484e3515974407a606289c6e762a0419723b7918fDevang Patel if (!BI->isConditional()) return; 77584e3515974407a606289c6e762a0419723b7918fDevang Patel if (BI->getCondition() != EC) return; 77658d43d4a41b21085c063bdd21a2abb68056e2a6fDevang Patel } 77784e3515974407a606289c6e762a0419723b7918fDevang Patel 778cd40233429fce385ae4b22301ce705273a6951a1Devang Patel // Find exit value. If exit value can not be represented as an interger then 779cd40233429fce385ae4b22301ce705273a6951a1Devang Patel // do not handle this floating point PH. 78084e3515974407a606289c6e762a0419723b7918fDevang Patel ConstantFP *EV = NULL; 78184e3515974407a606289c6e762a0419723b7918fDevang Patel unsigned EVIndex = 1; 78284e3515974407a606289c6e762a0419723b7918fDevang Patel if (EC->getOperand(1) == Incr) 78384e3515974407a606289c6e762a0419723b7918fDevang Patel EVIndex = 0; 78484e3515974407a606289c6e762a0419723b7918fDevang Patel EV = dyn_cast<ConstantFP>(EC->getOperand(EVIndex)); 78584e3515974407a606289c6e762a0419723b7918fDevang Patel if (!EV) return; 78684e3515974407a606289c6e762a0419723b7918fDevang Patel uint64_t intEV = Type::Int32Ty->getPrimitiveSizeInBits(); 787cd40233429fce385ae4b22301ce705273a6951a1Devang Patel if (!convertToInt(EV->getValueAPF(), &intEV)) 78884e3515974407a606289c6e762a0419723b7918fDevang Patel return; 789cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 79084e3515974407a606289c6e762a0419723b7918fDevang Patel // Find new predicate for integer comparison. 79184e3515974407a606289c6e762a0419723b7918fDevang Patel CmpInst::Predicate NewPred = CmpInst::BAD_ICMP_PREDICATE; 79284e3515974407a606289c6e762a0419723b7918fDevang Patel switch (EC->getPredicate()) { 79384e3515974407a606289c6e762a0419723b7918fDevang Patel case CmpInst::FCMP_OEQ: 79484e3515974407a606289c6e762a0419723b7918fDevang Patel case CmpInst::FCMP_UEQ: 79584e3515974407a606289c6e762a0419723b7918fDevang Patel NewPred = CmpInst::ICMP_EQ; 79684e3515974407a606289c6e762a0419723b7918fDevang Patel break; 79784e3515974407a606289c6e762a0419723b7918fDevang Patel case CmpInst::FCMP_OGT: 79884e3515974407a606289c6e762a0419723b7918fDevang Patel case CmpInst::FCMP_UGT: 79984e3515974407a606289c6e762a0419723b7918fDevang Patel NewPred = CmpInst::ICMP_UGT; 80084e3515974407a606289c6e762a0419723b7918fDevang Patel break; 80184e3515974407a606289c6e762a0419723b7918fDevang Patel case CmpInst::FCMP_OGE: 80284e3515974407a606289c6e762a0419723b7918fDevang Patel case CmpInst::FCMP_UGE: 80384e3515974407a606289c6e762a0419723b7918fDevang Patel NewPred = CmpInst::ICMP_UGE; 80484e3515974407a606289c6e762a0419723b7918fDevang Patel break; 80584e3515974407a606289c6e762a0419723b7918fDevang Patel case CmpInst::FCMP_OLT: 80684e3515974407a606289c6e762a0419723b7918fDevang Patel case CmpInst::FCMP_ULT: 80784e3515974407a606289c6e762a0419723b7918fDevang Patel NewPred = CmpInst::ICMP_ULT; 80884e3515974407a606289c6e762a0419723b7918fDevang Patel break; 80984e3515974407a606289c6e762a0419723b7918fDevang Patel case CmpInst::FCMP_OLE: 81084e3515974407a606289c6e762a0419723b7918fDevang Patel case CmpInst::FCMP_ULE: 81184e3515974407a606289c6e762a0419723b7918fDevang Patel NewPred = CmpInst::ICMP_ULE; 81284e3515974407a606289c6e762a0419723b7918fDevang Patel break; 81384e3515974407a606289c6e762a0419723b7918fDevang Patel default: 81484e3515974407a606289c6e762a0419723b7918fDevang Patel break; 81558d43d4a41b21085c063bdd21a2abb68056e2a6fDevang Patel } 81684e3515974407a606289c6e762a0419723b7918fDevang Patel if (NewPred == CmpInst::BAD_ICMP_PREDICATE) return; 817cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 81884e3515974407a606289c6e762a0419723b7918fDevang Patel // Insert new integer induction variable. 81984e3515974407a606289c6e762a0419723b7918fDevang Patel PHINode *NewPHI = PHINode::Create(Type::Int32Ty, 82084e3515974407a606289c6e762a0419723b7918fDevang Patel PH->getName()+".int", PH); 821cd40233429fce385ae4b22301ce705273a6951a1Devang Patel NewPHI->addIncoming(ConstantInt::get(Type::Int32Ty, newInitValue), 82284e3515974407a606289c6e762a0419723b7918fDevang Patel PH->getIncomingBlock(IncomingEdge)); 82384e3515974407a606289c6e762a0419723b7918fDevang Patel 824cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman Value *NewAdd = BinaryOperator::CreateAdd(NewPHI, 825cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman ConstantInt::get(Type::Int32Ty, 826cd40233429fce385ae4b22301ce705273a6951a1Devang Patel newIncrValue), 82784e3515974407a606289c6e762a0419723b7918fDevang Patel Incr->getName()+".int", Incr); 82884e3515974407a606289c6e762a0419723b7918fDevang Patel NewPHI->addIncoming(NewAdd, PH->getIncomingBlock(BackEdge)); 82984e3515974407a606289c6e762a0419723b7918fDevang Patel 830617d108a639b29015da2dbf0e54f61bd39c3c33cDale Johannesen // The back edge is edge 1 of newPHI, whatever it may have been in the 831617d108a639b29015da2dbf0e54f61bd39c3c33cDale Johannesen // original PHI. 83284e3515974407a606289c6e762a0419723b7918fDevang Patel ConstantInt *NewEV = ConstantInt::get(Type::Int32Ty, intEV); 833617d108a639b29015da2dbf0e54f61bd39c3c33cDale Johannesen Value *LHS = (EVIndex == 1 ? NewPHI->getIncomingValue(1) : NewEV); 834617d108a639b29015da2dbf0e54f61bd39c3c33cDale Johannesen Value *RHS = (EVIndex == 1 ? NewEV : NewPHI->getIncomingValue(1)); 835cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman ICmpInst *NewEC = new ICmpInst(NewPred, LHS, RHS, EC->getNameStart(), 83684e3515974407a606289c6e762a0419723b7918fDevang Patel EC->getParent()->getTerminator()); 837cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 83881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // In the following deltions, PH may become dead and may be deleted. 83981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Use a WeakVH to observe whether this happens. 84081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman WeakVH WeakPH = PH; 84181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 84284e3515974407a606289c6e762a0419723b7918fDevang Patel // Delete old, floating point, exit comparision instruction. 84384e3515974407a606289c6e762a0419723b7918fDevang Patel EC->replaceAllUsesWith(NewEC); 84481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman RecursivelyDeleteTriviallyDeadInstructions(EC); 845cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 84684e3515974407a606289c6e762a0419723b7918fDevang Patel // Delete old, floating point, increment instruction. 84784e3515974407a606289c6e762a0419723b7918fDevang Patel Incr->replaceAllUsesWith(UndefValue::get(Incr->getType())); 84881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman RecursivelyDeleteTriviallyDeadInstructions(Incr); 84981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 85081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Replace floating induction variable, if it isn't already deleted. 85181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Give SIToFPInst preference over UIToFPInst because it is faster on 85281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // platforms that are widely used. 85381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (WeakPH && !PH->use_empty()) { 85481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman if (useSIToFPInst(*InitValue, *EV, newInitValue, intEV)) { 85581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman SIToFPInst *Conv = new SIToFPInst(NewPHI, PH->getType(), "indvar.conv", 85681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman PH->getParent()->getFirstNonPHI()); 85781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman PH->replaceAllUsesWith(Conv); 85881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman } else { 85981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman UIToFPInst *Conv = new UIToFPInst(NewPHI, PH->getType(), "indvar.conv", 86081db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman PH->getParent()->getFirstNonPHI()); 86181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman PH->replaceAllUsesWith(Conv); 86281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman } 86381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman RecursivelyDeleteTriviallyDeadInstructions(PH); 864cd40233429fce385ae4b22301ce705273a6951a1Devang Patel } 86558d43d4a41b21085c063bdd21a2abb68056e2a6fDevang Patel 86681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Add a new IVUsers entry for the newly-created integer PHI. 86781db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman IU->AddUsersIfInteresting(NewPHI); 86881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman} 869