IndVarSimplify.cpp revision d3325d289736dec93c37f24bffd63cb91b643b87
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" 4636f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman#include "llvm/Analysis/ScalarEvolutionExpander.h" 4747df12d80db90e125e9f2ff764286ee11665476dJohn Criswell#include "llvm/Analysis/LoopInfo.h" 485ee99979065d75605d150d7e567e4351024aae8fDevang Patel#include "llvm/Analysis/LoopPass.h" 49455889aa79e3463a4b0f2161e3d9d72a683268b6Chris Lattner#include "llvm/Support/CFG.h" 509133fe28954d498fc4de13064c7d65bd811de02cReid Spencer#include "llvm/Support/Compiler.h" 51ee4f13a9046c380725cdeab62d57722db375c473Chris Lattner#include "llvm/Support/Debug.h" 52a4b9c7841f94b6a3a2ba6c562b5dc4f4de02c637Chris Lattner#include "llvm/Support/GetElementPtrTypeIterator.h" 5347df12d80db90e125e9f2ff764286ee11665476dJohn Criswell#include "llvm/Transforms/Utils/Local.h" 54551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/Support/CommandLine.h" 55a54b7cbd452b3adb2f51346140d996b29c2cdb30Reid Spencer#include "llvm/ADT/SmallVector.h" 56c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman#include "llvm/ADT/SetVector.h" 571a6111f32dcc1f4b0bc5993a09af4adb65a23b3fChris Lattner#include "llvm/ADT/SmallPtrSet.h" 58551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/Statistic.h" 5947df12d80db90e125e9f2ff764286ee11665476dJohn Criswellusing namespace llvm; 60d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 610e5f499638c8d277b9dc4a4385712177c53b5681Chris LattnerSTATISTIC(NumRemoved , "Number of aux indvars removed"); 620e5f499638c8d277b9dc4a4385712177c53b5681Chris LattnerSTATISTIC(NumPointer , "Number of pointer indvars promoted"); 630e5f499638c8d277b9dc4a4385712177c53b5681Chris LattnerSTATISTIC(NumInserted, "Number of canonical indvars added"); 640e5f499638c8d277b9dc4a4385712177c53b5681Chris LattnerSTATISTIC(NumReplaced, "Number of exit values replaced"); 650e5f499638c8d277b9dc4a4385712177c53b5681Chris LattnerSTATISTIC(NumLFTR , "Number of loop exit tests replaced"); 663324e718bc9ac2ede08a14c325848b576849542bChris Lattner 670e5f499638c8d277b9dc4a4385712177c53b5681Chris Lattnernamespace { 685ee99979065d75605d150d7e567e4351024aae8fDevang Patel class VISIBILITY_HIDDEN IndVarSimplify : public LoopPass { 6940bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner LoopInfo *LI; 7040bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner ScalarEvolution *SE; 7115cad759fe2048ac5eb137c6bb0ab7287538677eChris Lattner bool Changed; 723324e718bc9ac2ede08a14c325848b576849542bChris Lattner public: 73794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel 74ecd94c804a563f2a86572dcf1d2e81f397e19daaNick Lewycky static char ID; // Pass identification, replacement for typeid 75ae73dc1448d25b02cabc7c64c86c64371453dda8Dan Gohman IndVarSimplify() : LoopPass(&ID) {} 76794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel 7760f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman virtual bool runOnLoop(Loop *L, LPPassManager &LPM); 7860f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman 795ee99979065d75605d150d7e567e4351024aae8fDevang Patel virtual void getAnalysisUsage(AnalysisUsage &AU) const { 80bc533cd1286ebb393c37a2a8b03079bfc9655585Devang Patel AU.addRequired<ScalarEvolution>(); 815ee99979065d75605d150d7e567e4351024aae8fDevang Patel AU.addRequiredID(LCSSAID); 825ee99979065d75605d150d7e567e4351024aae8fDevang Patel AU.addRequiredID(LoopSimplifyID); 835ee99979065d75605d150d7e567e4351024aae8fDevang Patel AU.addRequired<LoopInfo>(); 84474cecf0e9bca95ab7091a341784550c7eb1e887Dan Gohman AU.addPreserved<ScalarEvolution>(); 855ee99979065d75605d150d7e567e4351024aae8fDevang Patel AU.addPreservedID(LoopSimplifyID); 865ee99979065d75605d150d7e567e4351024aae8fDevang Patel AU.addPreservedID(LCSSAID); 875ee99979065d75605d150d7e567e4351024aae8fDevang Patel AU.setPreservesCFG(); 885ee99979065d75605d150d7e567e4351024aae8fDevang Patel } 893324e718bc9ac2ede08a14c325848b576849542bChris Lattner 9040bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner private: 915ee99979065d75605d150d7e567e4351024aae8fDevang Patel 9260f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman void RewriteNonIntegerIVs(Loop *L); 9360f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman 9440bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner void EliminatePointerRecurrence(PHINode *PN, BasicBlock *Preheader, 951a6111f32dcc1f4b0bc5993a09af4adb65a23b3fChris Lattner SmallPtrSet<Instruction*, 16> &DeadInsts); 9646bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman void LinearFunctionTestReplace(Loop *L, SCEVHandle BackedgeTakenCount, 97a575871884b247b0946290876ac7d4657b384cf9Dan Gohman Value *IndVar, 98c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman BasicBlock *ExitingBlock, 99c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman BranchInst *BI, 10015cab2817b8f63fec0148609278bc2c1e05abb50Dan Gohman SCEVExpander &Rewriter); 10146bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman void RewriteLoopExitValues(Loop *L, SCEV *BackedgeTakenCount); 10240bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner 1031a6111f32dcc1f4b0bc5993a09af4adb65a23b3fChris Lattner void DeleteTriviallyDeadInstructions(SmallPtrSet<Instruction*, 16> &Insts); 104d22a849282c45bbf7eb1734c274294d81e49e3a8Devang Patel 105cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman void HandleFloatingPointIV(Loop *L, PHINode *PH, 10684e3515974407a606289c6e762a0419723b7918fDevang Patel SmallPtrSet<Instruction*, 16> &DeadInsts); 1073324e718bc9ac2ede08a14c325848b576849542bChris Lattner }; 1085e76140536ba66fadeced1cd892f79616f407e3cChris Lattner} 109394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner 110844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanchar IndVarSimplify::ID = 0; 111844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanstatic RegisterPass<IndVarSimplify> 112844731a7f1909f55935e3514c9e713a62d67662eDan GohmanX("indvars", "Canonicalize Induction Variables"); 113844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 114394f0441e06dafca29f0752cf400990a5b8fe4b1Daniel DunbarPass *llvm::createIndVarSimplifyPass() { 1153324e718bc9ac2ede08a14c325848b576849542bChris Lattner return new IndVarSimplify(); 116394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner} 117394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner 11840bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner/// DeleteTriviallyDeadInstructions - If any of the instructions is the 11940bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner/// specified set are trivially dead, delete them and see if this makes any of 12040bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner/// their operands subsequently dead. 12140bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattnervoid IndVarSimplify:: 1221a6111f32dcc1f4b0bc5993a09af4adb65a23b3fChris LattnerDeleteTriviallyDeadInstructions(SmallPtrSet<Instruction*, 16> &Insts) { 12340bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner while (!Insts.empty()) { 12440bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner Instruction *I = *Insts.begin(); 1251a6111f32dcc1f4b0bc5993a09af4adb65a23b3fChris Lattner Insts.erase(I); 12640bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner if (isInstructionTriviallyDead(I)) { 12740bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) 12840bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner if (Instruction *U = dyn_cast<Instruction>(I->getOperand(i))) 12940bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner Insts.insert(U); 1305cec4db6ae13a41d04d86f37e347fc5b5997c948Dan Gohman SE->deleteValueFromRecords(I); 131ee4f13a9046c380725cdeab62d57722db375c473Chris Lattner DOUT << "INDVARS: Deleting: " << *I; 132a4b9c7841f94b6a3a2ba6c562b5dc4f4de02c637Chris Lattner I->eraseFromParent(); 13340bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner Changed = true; 13440bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner } 13540bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner } 13640bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner} 1373324e718bc9ac2ede08a14c325848b576849542bChris Lattner 1386148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner 13940bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner/// EliminatePointerRecurrence - Check to see if this is a trivial GEP pointer 14040bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner/// recurrence. If so, change it into an integer recurrence, permitting 14140bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner/// analysis by the SCEV routines. 142fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukmanvoid IndVarSimplify::EliminatePointerRecurrence(PHINode *PN, 14340bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner BasicBlock *Preheader, 1441a6111f32dcc1f4b0bc5993a09af4adb65a23b3fChris Lattner SmallPtrSet<Instruction*, 16> &DeadInsts) { 14540bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner assert(PN->getNumIncomingValues() == 2 && "Noncanonicalized loop!"); 14640bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner unsigned PreheaderIdx = PN->getBasicBlockIndex(Preheader); 14740bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner unsigned BackedgeIdx = PreheaderIdx^1; 14840bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner if (GetElementPtrInst *GEPI = 149cda9ca5a4fed09ea3788b572dbddabf2a5a7a5d9Chris Lattner dyn_cast<GetElementPtrInst>(PN->getIncomingValue(BackedgeIdx))) 15040bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner if (GEPI->getOperand(0) == PN) { 151cda9ca5a4fed09ea3788b572dbddabf2a5a7a5d9Chris Lattner assert(GEPI->getNumOperands() == 2 && "GEP types must match!"); 152ee4f13a9046c380725cdeab62d57722db375c473Chris Lattner DOUT << "INDVARS: Eliminating pointer recurrence: " << *GEPI; 153cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 15440bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // Okay, we found a pointer recurrence. Transform this pointer 15540bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // recurrence into an integer recurrence. Compute the value that gets 15640bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // added to the pointer at every iteration. 15740bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner Value *AddedVal = GEPI->getOperand(1); 15840bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner 15940bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // Insert a new integer PHI node into the top of the block. 160051a950000e21935165db56695e35bade668193bGabor Greif PHINode *NewPhi = PHINode::Create(AddedVal->getType(), 161051a950000e21935165db56695e35bade668193bGabor Greif PN->getName()+".rec", PN); 162c5c5e6afe584ffbd2bf2ce755e65bc89f170053aChris Lattner NewPhi->addIncoming(Constant::getNullValue(NewPhi->getType()), Preheader); 163c5c5e6afe584ffbd2bf2ce755e65bc89f170053aChris Lattner 16440bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // Create the new add instruction. 1657cbd8a3e92221437048b484d5ef9c0a22d0f8c58Gabor Greif Value *NewAdd = BinaryOperator::CreateAdd(NewPhi, AddedVal, 166c5c5e6afe584ffbd2bf2ce755e65bc89f170053aChris Lattner GEPI->getName()+".rec", GEPI); 16740bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner NewPhi->addIncoming(NewAdd, PN->getIncomingBlock(BackedgeIdx)); 168fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 16940bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // Update the existing GEP to use the recurrence. 17040bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner GEPI->setOperand(0, PN->getIncomingValue(PreheaderIdx)); 171fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 17240bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // Update the GEP to use the new recurrence we just inserted. 17340bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner GEPI->setOperand(1, NewAdd); 17440bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner 175a4b9c7841f94b6a3a2ba6c562b5dc4f4de02c637Chris Lattner // If the incoming value is a constant expr GEP, try peeling out the array 176a4b9c7841f94b6a3a2ba6c562b5dc4f4de02c637Chris Lattner // 0 index if possible to make things simpler. 177a4b9c7841f94b6a3a2ba6c562b5dc4f4de02c637Chris Lattner if (ConstantExpr *CE = dyn_cast<ConstantExpr>(GEPI->getOperand(0))) 178a4b9c7841f94b6a3a2ba6c562b5dc4f4de02c637Chris Lattner if (CE->getOpcode() == Instruction::GetElementPtr) { 179a4b9c7841f94b6a3a2ba6c562b5dc4f4de02c637Chris Lattner unsigned NumOps = CE->getNumOperands(); 180a4b9c7841f94b6a3a2ba6c562b5dc4f4de02c637Chris Lattner assert(NumOps > 1 && "CE folding didn't work!"); 181a4b9c7841f94b6a3a2ba6c562b5dc4f4de02c637Chris Lattner if (CE->getOperand(NumOps-1)->isNullValue()) { 182a4b9c7841f94b6a3a2ba6c562b5dc4f4de02c637Chris Lattner // Check to make sure the last index really is an array index. 1831730078d5f553d7516a06e098e6c2089dc8bef9cChris Lattner gep_type_iterator GTI = gep_type_begin(CE); 184ceda605fd7d0e3532a22743538c6d118fe5e40c1Chris Lattner for (unsigned i = 1, e = CE->getNumOperands()-1; 185a4b9c7841f94b6a3a2ba6c562b5dc4f4de02c637Chris Lattner i != e; ++i, ++GTI) 186a4b9c7841f94b6a3a2ba6c562b5dc4f4de02c637Chris Lattner /*empty*/; 187a4b9c7841f94b6a3a2ba6c562b5dc4f4de02c637Chris Lattner if (isa<SequentialType>(*GTI)) { 188a4b9c7841f94b6a3a2ba6c562b5dc4f4de02c637Chris Lattner // Pull the last index out of the constant expr GEP. 18955eb1c47de30a6b4e8707b6392e878e32a6583e9Chris Lattner SmallVector<Value*, 8> CEIdxs(CE->op_begin()+1, CE->op_end()-1); 190a4b9c7841f94b6a3a2ba6c562b5dc4f4de02c637Chris Lattner Constant *NCE = ConstantExpr::getGetElementPtr(CE->getOperand(0), 19155eb1c47de30a6b4e8707b6392e878e32a6583e9Chris Lattner &CEIdxs[0], 19255eb1c47de30a6b4e8707b6392e878e32a6583e9Chris Lattner CEIdxs.size()); 193b8f74793b9d161bc666fe27fc92fe112b6ec169bDavid Greene Value *Idx[2]; 194b8f74793b9d161bc666fe27fc92fe112b6ec169bDavid Greene Idx[0] = Constant::getNullValue(Type::Int32Ty); 195b8f74793b9d161bc666fe27fc92fe112b6ec169bDavid Greene Idx[1] = NewAdd; 196051a950000e21935165db56695e35bade668193bGabor Greif GetElementPtrInst *NGEPI = GetElementPtrInst::Create( 197cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman NCE, Idx, Idx + 2, 198cae5754619433aed7be74abbf1c0551a82d369cbReid Spencer GEPI->getName(), GEPI); 1995cec4db6ae13a41d04d86f37e347fc5b5997c948Dan Gohman SE->deleteValueFromRecords(GEPI); 200a4b9c7841f94b6a3a2ba6c562b5dc4f4de02c637Chris Lattner GEPI->replaceAllUsesWith(NGEPI); 201a4b9c7841f94b6a3a2ba6c562b5dc4f4de02c637Chris Lattner GEPI->eraseFromParent(); 202a4b9c7841f94b6a3a2ba6c562b5dc4f4de02c637Chris Lattner GEPI = NGEPI; 203a4b9c7841f94b6a3a2ba6c562b5dc4f4de02c637Chris Lattner } 204a4b9c7841f94b6a3a2ba6c562b5dc4f4de02c637Chris Lattner } 205a4b9c7841f94b6a3a2ba6c562b5dc4f4de02c637Chris Lattner } 206a4b9c7841f94b6a3a2ba6c562b5dc4f4de02c637Chris Lattner 207a4b9c7841f94b6a3a2ba6c562b5dc4f4de02c637Chris Lattner 20840bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // Finally, if there are any other users of the PHI node, we must 20940bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // insert a new GEP instruction that uses the pre-incremented version 21040bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // of the induction amount. 21140bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner if (!PN->use_empty()) { 21240bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner BasicBlock::iterator InsertPos = PN; ++InsertPos; 21340bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner while (isa<PHINode>(InsertPos)) ++InsertPos; 21440bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner Value *PreInc = 215051a950000e21935165db56695e35bade668193bGabor Greif GetElementPtrInst::Create(PN->getIncomingValue(PreheaderIdx), 216051a950000e21935165db56695e35bade668193bGabor Greif NewPhi, "", InsertPos); 2176934a04a8c15e9971cd1ea4d5c8df2d7afdd5be5Chris Lattner PreInc->takeName(PN); 21840bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner PN->replaceAllUsesWith(PreInc); 21940bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner } 22040bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner 22140bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // Delete the old PHI for sure, and the GEP if its otherwise unused. 22240bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner DeadInsts.insert(PN); 2233324e718bc9ac2ede08a14c325848b576849542bChris Lattner 22440bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner ++NumPointer; 22540bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner Changed = true; 22640bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner } 22740bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner} 2283324e718bc9ac2ede08a14c325848b576849542bChris Lattner 22940bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner/// LinearFunctionTestReplace - This method rewrites the exit condition of the 23059fdaeeae8f183e18bb6ad5c382ca23e28e6aaf6Chris Lattner/// loop to be a canonical != comparison against the incremented loop induction 23159fdaeeae8f183e18bb6ad5c382ca23e28e6aaf6Chris Lattner/// variable. This pass is able to rewrite the exit tests of any loop where the 23259fdaeeae8f183e18bb6ad5c382ca23e28e6aaf6Chris Lattner/// SCEV analysis can determine a loop-invariant trip count of the loop, which 23359fdaeeae8f183e18bb6ad5c382ca23e28e6aaf6Chris Lattner/// is actually a much broader range than just linear tests. 234c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohmanvoid IndVarSimplify::LinearFunctionTestReplace(Loop *L, 23546bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman SCEVHandle BackedgeTakenCount, 236c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman Value *IndVar, 237c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman BasicBlock *ExitingBlock, 238c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman BranchInst *BI, 23915cab2817b8f63fec0148609278bc2c1e05abb50Dan Gohman SCEVExpander &Rewriter) { 240d244057a48660c3cd30d219118ece3f947947790Chris Lattner // If the exiting block is not the same as the backedge block, we must compare 241d244057a48660c3cd30d219118ece3f947947790Chris Lattner // against the preincremented value, otherwise we prefer to compare against 242d244057a48660c3cd30d219118ece3f947947790Chris Lattner // the post-incremented value. 243c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman Value *CmpIndVar; 24446bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman SCEVHandle RHS = BackedgeTakenCount; 245c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman if (ExitingBlock == L->getLoopLatch()) { 24646bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman // Add one to the "backedge-taken" count to get the trip count. 24746bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman // If this addition may overflow, we have to be more pessimistic and 24846bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman // cast the induction variable before doing the add. 24946bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman SCEVHandle Zero = SE->getIntegerSCEV(0, BackedgeTakenCount->getType()); 250c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman SCEVHandle N = 25146bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman SE->getAddExpr(BackedgeTakenCount, 25246bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman SE->getIntegerSCEV(1, BackedgeTakenCount->getType())); 253c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman if ((isa<SCEVConstant>(N) && !N->isZero()) || 254c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman SE->isLoopGuardedByCond(L, ICmpInst::ICMP_NE, N, Zero)) { 255c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman // No overflow. Cast the sum. 25646bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman RHS = SE->getTruncateOrZeroExtend(N, IndVar->getType()); 257c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman } else { 258c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman // Potential overflow. Cast before doing the add. 25946bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman RHS = SE->getTruncateOrZeroExtend(BackedgeTakenCount, 26046bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman IndVar->getType()); 26146bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman RHS = SE->getAddExpr(RHS, 26246bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman SE->getIntegerSCEV(1, IndVar->getType())); 263c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman } 264c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman 26546bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman // The BackedgeTaken expression contains the number of times that the 26646bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman // backedge branches to the loop header. This is one less than the 26746bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman // number of times the loop executes, so use the incremented indvar. 268c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman CmpIndVar = L->getCanonicalInductionVariableIncrement(); 269d244057a48660c3cd30d219118ece3f947947790Chris Lattner } else { 270d244057a48660c3cd30d219118ece3f947947790Chris Lattner // We have to use the preincremented value... 27146bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman RHS = SE->getTruncateOrZeroExtend(BackedgeTakenCount, 27246bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman IndVar->getType()); 273c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman CmpIndVar = IndVar; 274d244057a48660c3cd30d219118ece3f947947790Chris Lattner } 27559fdaeeae8f183e18bb6ad5c382ca23e28e6aaf6Chris Lattner 27640bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // Expand the code for the iteration count into the preheader of the loop. 27740bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner BasicBlock *Preheader = L->getLoopPreheader(); 27846bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman Value *ExitCnt = Rewriter.expandCodeFor(RHS, 279c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman Preheader->getTerminator()); 28040bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner 281e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer // Insert a new icmp_ne or icmp_eq instruction before the branch. 282e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer ICmpInst::Predicate Opcode; 28340bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner if (L->contains(BI->getSuccessor(0))) 284e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer Opcode = ICmpInst::ICMP_NE; 28540bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner else 286e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer Opcode = ICmpInst::ICMP_EQ; 28740bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner 288c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman DOUT << "INDVARS: Rewriting loop exit condition to:\n" 289c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman << " LHS:" << *CmpIndVar // includes a newline 290c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman << " op:\t" 291f108e2eaaa788272a3ced1eef1bbb84f0d03b60cDan Gohman << (Opcode == ICmpInst::ICMP_NE ? "!=" : "==") << "\n" 29246bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman << " RHS:\t" << *RHS << "\n"; 293c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman 294c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman Value *Cond = new ICmpInst(Opcode, CmpIndVar, ExitCnt, "exitcond", BI); 29540bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner BI->setCondition(Cond); 29640bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner ++NumLFTR; 29740bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner Changed = true; 29840bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner} 2993324e718bc9ac2ede08a14c325848b576849542bChris Lattner 30040bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner/// RewriteLoopExitValues - Check to see if this loop has a computable 30140bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner/// loop-invariant execution count. If so, this means that we can compute the 30240bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner/// final value of any expressions that are recurrent in the loop, and 30340bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner/// substitute the exit values from the loop into any instructions outside of 30440bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner/// the loop that use the final values of the current expressions. 30546bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohmanvoid IndVarSimplify::RewriteLoopExitValues(Loop *L, SCEV *BackedgeTakenCount) { 30640bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner BasicBlock *Preheader = L->getLoopPreheader(); 30740bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner 30840bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // Scan all of the instructions in the loop, looking at those that have 30940bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // extra-loop users and which are recurrences. 3104a7553e2da506a718f59869c03c5ce113eb40f7aChris Lattner SCEVExpander Rewriter(*SE, *LI); 31140bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner 31240bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // We insert the code into the preheader of the loop if the loop contains 31340bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // multiple exit blocks, or in the exit block if there is exactly one. 31440bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner BasicBlock *BlockToInsertInto; 315b7211a2ce13a0365e0e1dd2f27adda2ee3d1288bDevang Patel SmallVector<BasicBlock*, 8> ExitBlocks; 3169f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner L->getUniqueExitBlocks(ExitBlocks); 317f1ab4b4eac5603d19c20f4a508f93a118a52bdd5Chris Lattner if (ExitBlocks.size() == 1) 318f1ab4b4eac5603d19c20f4a508f93a118a52bdd5Chris Lattner BlockToInsertInto = ExitBlocks[0]; 31940bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner else 32040bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner BlockToInsertInto = Preheader; 32102dea8b39f3acad5de1df36273444d149145e7fcDan Gohman BasicBlock::iterator InsertPt = BlockToInsertInto->getFirstNonPHI(); 32240bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner 32346bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman bool HasConstantItCount = isa<SCEVConstant>(BackedgeTakenCount); 32420aa098ba694aa7e3f5fb5a52d22dba7c1e857aeChris Lattner 3251a6111f32dcc1f4b0bc5993a09af4adb65a23b3fChris Lattner SmallPtrSet<Instruction*, 16> InstructionsToDelete; 3269f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner std::map<Instruction*, Value*> ExitValues; 3279f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner 3289f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // Find all values that are computed inside the loop, but used outside of it. 3299f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // Because of LCSSA, these values will only occur in LCSSA PHI Nodes. Scan 3309f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // the exit blocks of the loop to find them. 3319f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) { 3329f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner BasicBlock *ExitBB = ExitBlocks[i]; 333cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 3349f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // If there are no PHI nodes in this exit block, then no values defined 3359f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // inside the loop are used on this path, skip it. 3369f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner PHINode *PN = dyn_cast<PHINode>(ExitBB->begin()); 3379f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner if (!PN) continue; 338cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 3399f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner unsigned NumPreds = PN->getNumIncomingValues(); 340cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 3419f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // Iterate over all of the PHI nodes. 3429f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner BasicBlock::iterator BBI = ExitBB->begin(); 3439f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner while ((PN = dyn_cast<PHINode>(BBI++))) { 344cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 3459f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // Iterate over all of the values in all the PHI nodes. 3469f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner for (unsigned i = 0; i != NumPreds; ++i) { 3479f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // If the value being merged in is not integer or is not defined 3489f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // in the loop, skip it. 3499f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner Value *InVal = PN->getIncomingValue(i); 3509f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner if (!isa<Instruction>(InVal) || 3519f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // SCEV only supports integer expressions for now. 3529f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner !isa<IntegerType>(InVal->getType())) 3539f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner continue; 3549f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner 3559f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // If this pred is for a subloop, not L itself, skip it. 356cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman if (LI->getLoopFor(PN->getIncomingBlock(i)) != L) 3579f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner continue; // The Block is in a subloop, skip it. 3589f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner 3599f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // Check that InVal is defined in the loop. 3609f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner Instruction *Inst = cast<Instruction>(InVal); 3619f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner if (!L->contains(Inst->getParent())) 3629f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner continue; 363cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 3649f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // We require that this value either have a computable evolution or that 3659f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // the loop have a constant iteration count. In the case where the loop 3669f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // has a constant iteration count, we can sometimes force evaluation of 3679f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // the exit value through brute force. 3689f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner SCEVHandle SH = SE->getSCEV(Inst); 3699f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner if (!SH->hasComputableLoopEvolution(L) && !HasConstantItCount) 3709f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner continue; // Cannot get exit evolution for the loop value. 371cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 3729f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // Okay, this instruction has a user outside of the current loop 3739f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // and varies predictably *inside* the loop. Evaluate the value it 3749f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // contains when the loop exits, if possible. 3759f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner SCEVHandle ExitValue = SE->getSCEVAtScope(Inst, L->getParentLoop()); 3769f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner if (isa<SCEVCouldNotCompute>(ExitValue) || 3779f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner !ExitValue->isLoopInvariant(L)) 3789f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner continue; 3799f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner 3809f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner Changed = true; 3819f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner ++NumReplaced; 382cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 3839f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // See if we already computed the exit value for the instruction, if so, 3849f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // just reuse it. 3859f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner Value *&ExitVal = ExitValues[Inst]; 3869f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner if (!ExitVal) 387d19534add90a2a894af61523b830887097bb780bDan Gohman ExitVal = Rewriter.expandCodeFor(ExitValue, InsertPt); 388cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 3899f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner DOUT << "INDVARS: RLEV: AfterLoopVal = " << *ExitVal 3909f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner << " LoopVal = " << *Inst << "\n"; 3919caed5440d59dac4b388152fe8b993dc0491e5e9Chris Lattner 3929f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner PN->setIncomingValue(i, ExitVal); 393cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 3949f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // If this instruction is dead now, schedule it to be removed. 3959f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner if (Inst->use_empty()) 3969f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner InstructionsToDelete.insert(Inst); 397cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 3989f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // See if this is a single-entry LCSSA PHI node. If so, we can (and 3999f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // have to) remove 4009caed5440d59dac4b388152fe8b993dc0491e5e9Chris Lattner // the PHI entirely. This is safe, because the NewVal won't be variant 4019caed5440d59dac4b388152fe8b993dc0491e5e9Chris Lattner // in the loop, so we don't need an LCSSA phi node anymore. 4029f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner if (NumPreds == 1) { 4035cec4db6ae13a41d04d86f37e347fc5b5997c948Dan Gohman SE->deleteValueFromRecords(PN); 4049f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner PN->replaceAllUsesWith(ExitVal); 4059f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner PN->eraseFromParent(); 4069f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner break; 407c9838f25d53d3dd7d38949ef6c28f2505a110f45Chris Lattner } 4084bd09d70cceb3851f7eb1c2f98338b3071d405f3Chris Lattner } 409c9838f25d53d3dd7d38949ef6c28f2505a110f45Chris Lattner } 410c9838f25d53d3dd7d38949ef6c28f2505a110f45Chris Lattner } 411cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 41240bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner DeleteTriviallyDeadInstructions(InstructionsToDelete); 41340bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner} 41415cad759fe2048ac5eb137c6bb0ab7287538677eChris Lattner 41560f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohmanvoid IndVarSimplify::RewriteNonIntegerIVs(Loop *L) { 41640bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // First step. Check to see if there are any trivial GEP pointer recurrences. 41740bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // If there are, change them into integer recurrences, permitting analysis by 41840bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // the SCEV routines. 41915cad759fe2048ac5eb137c6bb0ab7287538677eChris Lattner // 42040bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner BasicBlock *Header = L->getHeader(); 42140bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner BasicBlock *Preheader = L->getLoopPreheader(); 422fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 4231a6111f32dcc1f4b0bc5993a09af4adb65a23b3fChris Lattner SmallPtrSet<Instruction*, 16> DeadInsts; 4242da5c3dda6f5b9c4ec6d55008d33327764364bd4Reid Spencer for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) { 4252da5c3dda6f5b9c4ec6d55008d33327764364bd4Reid Spencer PHINode *PN = cast<PHINode>(I); 42640bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner if (isa<PointerType>(PN->getType())) 42740bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner EliminatePointerRecurrence(PN, Preheader, DeadInsts); 42884e3515974407a606289c6e762a0419723b7918fDevang Patel else 42984e3515974407a606289c6e762a0419723b7918fDevang Patel HandleFloatingPointIV(L, PN, DeadInsts); 4302da5c3dda6f5b9c4ec6d55008d33327764364bd4Reid Spencer } 43115cad759fe2048ac5eb137c6bb0ab7287538677eChris Lattner 43260f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman // If the loop previously had a pointer or floating-point IV, ScalarEvolution 43360f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman // may not have been able to compute a trip count. Now that we've done some 43460f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman // re-writing, the trip count may be computable. 43560f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman if (Changed) 43646bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman SE->forgetLoopBackedgeTakenCount(L); 43760f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman 43840bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner if (!DeadInsts.empty()) 43940bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner DeleteTriviallyDeadInstructions(DeadInsts); 4405ee99979065d75605d150d7e567e4351024aae8fDevang Patel} 4415ee99979065d75605d150d7e567e4351024aae8fDevang Patel 442c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman/// getEffectiveIndvarType - Determine the widest type that the 443c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman/// induction-variable PHINode Phi is cast to. 444c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman/// 445c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohmanstatic const Type *getEffectiveIndvarType(const PHINode *Phi) { 446c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman const Type *Ty = Phi->getType(); 447c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman 448c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman for (Value::use_const_iterator UI = Phi->use_begin(), UE = Phi->use_end(); 449c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman UI != UE; ++UI) { 450c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman const Type *CandidateType = NULL; 451c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman if (const ZExtInst *ZI = dyn_cast<ZExtInst>(UI)) 452c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman CandidateType = ZI->getDestTy(); 453c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman else if (const SExtInst *SI = dyn_cast<SExtInst>(UI)) 454c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman CandidateType = SI->getDestTy(); 455c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman if (CandidateType && 456c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman CandidateType->getPrimitiveSizeInBits() > 457c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman Ty->getPrimitiveSizeInBits()) 458c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman Ty = CandidateType; 459c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman } 460c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman 461c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman return Ty; 462c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman} 4635ee99979065d75605d150d7e567e4351024aae8fDevang Patel 464aa03649af255fbbb049f393a2cf7d533da86d951Dan Gohman/// TestOrigIVForWrap - Analyze the original induction variable 465d2067fd730b2b266f5c244d5871a244b534e10eaDan Gohman/// that controls the loop's iteration to determine whether it 466f5a309e989b8d2199cb542793e9edf48395d9fedDan Gohman/// would ever undergo signed or unsigned overflow. Also, check 467f5a309e989b8d2199cb542793e9edf48395d9fedDan Gohman/// whether an induction variable in the same type that starts 468f5a309e989b8d2199cb542793e9edf48395d9fedDan Gohman/// at 0 would undergo signed overflow. 469d2067fd730b2b266f5c244d5871a244b534e10eaDan Gohman/// 470dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen/// In addition to setting the NoSignedWrap and NoUnsignedWrap 471dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen/// variables to true when appropriate (they are not set to false here), 472dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen/// return the PHI for this induction variable. Also record the initial 473dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen/// and final values and the increment; these are not meaningful unless 474dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen/// either NoSignedWrap or NoUnsignedWrap is true, and are always meaningful 475dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen/// in that case, although the final value may be 0 indicating a nonconstant. 476c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman/// 477c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman/// TODO: This duplicates a fair amount of ScalarEvolution logic. 47846bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman/// Perhaps this can be merged with 47946bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman/// ScalarEvolution::getBackedgeTakenCount 480aa03649af255fbbb049f393a2cf7d533da86d951Dan Gohman/// and/or ScalarEvolution::get{Sign,Zero}ExtendExpr. 481c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman/// 482d2067fd730b2b266f5c244d5871a244b534e10eaDan Gohmanstatic const PHINode *TestOrigIVForWrap(const Loop *L, 483d2067fd730b2b266f5c244d5871a244b534e10eaDan Gohman const BranchInst *BI, 484d2067fd730b2b266f5c244d5871a244b534e10eaDan Gohman const Instruction *OrigCond, 485d2067fd730b2b266f5c244d5871a244b534e10eaDan Gohman bool &NoSignedWrap, 486dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen bool &NoUnsignedWrap, 487dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen const ConstantInt* &InitialVal, 488dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen const ConstantInt* &IncrVal, 489dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen const ConstantInt* &LimitVal) { 490c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman // Verify that the loop is sane and find the exit condition. 491c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman const ICmpInst *Cmp = dyn_cast<ICmpInst>(OrigCond); 492d2067fd730b2b266f5c244d5871a244b534e10eaDan Gohman if (!Cmp) return 0; 493aa03649af255fbbb049f393a2cf7d533da86d951Dan Gohman 494aa03649af255fbbb049f393a2cf7d533da86d951Dan Gohman const Value *CmpLHS = Cmp->getOperand(0); 495aa03649af255fbbb049f393a2cf7d533da86d951Dan Gohman const Value *CmpRHS = Cmp->getOperand(1); 496aa03649af255fbbb049f393a2cf7d533da86d951Dan Gohman const BasicBlock *TrueBB = BI->getSuccessor(0); 497aa03649af255fbbb049f393a2cf7d533da86d951Dan Gohman const BasicBlock *FalseBB = BI->getSuccessor(1); 498aa03649af255fbbb049f393a2cf7d533da86d951Dan Gohman ICmpInst::Predicate Pred = Cmp->getPredicate(); 499aa03649af255fbbb049f393a2cf7d533da86d951Dan Gohman 500aa03649af255fbbb049f393a2cf7d533da86d951Dan Gohman // Canonicalize a constant to the RHS. 501aa03649af255fbbb049f393a2cf7d533da86d951Dan Gohman if (isa<ConstantInt>(CmpLHS)) { 502aa03649af255fbbb049f393a2cf7d533da86d951Dan Gohman Pred = ICmpInst::getSwappedPredicate(Pred); 503aa03649af255fbbb049f393a2cf7d533da86d951Dan Gohman std::swap(CmpLHS, CmpRHS); 504aa03649af255fbbb049f393a2cf7d533da86d951Dan Gohman } 505aa03649af255fbbb049f393a2cf7d533da86d951Dan Gohman // Canonicalize SLE to SLT. 506aa03649af255fbbb049f393a2cf7d533da86d951Dan Gohman if (Pred == ICmpInst::ICMP_SLE) 507aa03649af255fbbb049f393a2cf7d533da86d951Dan Gohman if (const ConstantInt *CI = dyn_cast<ConstantInt>(CmpRHS)) 508aa03649af255fbbb049f393a2cf7d533da86d951Dan Gohman if (!CI->getValue().isMaxSignedValue()) { 509aa03649af255fbbb049f393a2cf7d533da86d951Dan Gohman CmpRHS = ConstantInt::get(CI->getValue() + 1); 510aa03649af255fbbb049f393a2cf7d533da86d951Dan Gohman Pred = ICmpInst::ICMP_SLT; 511aa03649af255fbbb049f393a2cf7d533da86d951Dan Gohman } 512aa03649af255fbbb049f393a2cf7d533da86d951Dan Gohman // Canonicalize SGT to SGE. 513aa03649af255fbbb049f393a2cf7d533da86d951Dan Gohman if (Pred == ICmpInst::ICMP_SGT) 514aa03649af255fbbb049f393a2cf7d533da86d951Dan Gohman if (const ConstantInt *CI = dyn_cast<ConstantInt>(CmpRHS)) 515aa03649af255fbbb049f393a2cf7d533da86d951Dan Gohman if (!CI->getValue().isMaxSignedValue()) { 516aa03649af255fbbb049f393a2cf7d533da86d951Dan Gohman CmpRHS = ConstantInt::get(CI->getValue() + 1); 517aa03649af255fbbb049f393a2cf7d533da86d951Dan Gohman Pred = ICmpInst::ICMP_SGE; 518aa03649af255fbbb049f393a2cf7d533da86d951Dan Gohman } 519aa03649af255fbbb049f393a2cf7d533da86d951Dan Gohman // Canonicalize SGE to SLT. 520aa03649af255fbbb049f393a2cf7d533da86d951Dan Gohman if (Pred == ICmpInst::ICMP_SGE) { 521aa03649af255fbbb049f393a2cf7d533da86d951Dan Gohman std::swap(TrueBB, FalseBB); 522aa03649af255fbbb049f393a2cf7d533da86d951Dan Gohman Pred = ICmpInst::ICMP_SLT; 523aa03649af255fbbb049f393a2cf7d533da86d951Dan Gohman } 524aa03649af255fbbb049f393a2cf7d533da86d951Dan Gohman // Canonicalize ULE to ULT. 525aa03649af255fbbb049f393a2cf7d533da86d951Dan Gohman if (Pred == ICmpInst::ICMP_ULE) 526aa03649af255fbbb049f393a2cf7d533da86d951Dan Gohman if (const ConstantInt *CI = dyn_cast<ConstantInt>(CmpRHS)) 527aa03649af255fbbb049f393a2cf7d533da86d951Dan Gohman if (!CI->getValue().isMaxValue()) { 528aa03649af255fbbb049f393a2cf7d533da86d951Dan Gohman CmpRHS = ConstantInt::get(CI->getValue() + 1); 529aa03649af255fbbb049f393a2cf7d533da86d951Dan Gohman Pred = ICmpInst::ICMP_ULT; 530aa03649af255fbbb049f393a2cf7d533da86d951Dan Gohman } 531aa03649af255fbbb049f393a2cf7d533da86d951Dan Gohman // Canonicalize UGT to UGE. 532aa03649af255fbbb049f393a2cf7d533da86d951Dan Gohman if (Pred == ICmpInst::ICMP_UGT) 533aa03649af255fbbb049f393a2cf7d533da86d951Dan Gohman if (const ConstantInt *CI = dyn_cast<ConstantInt>(CmpRHS)) 534aa03649af255fbbb049f393a2cf7d533da86d951Dan Gohman if (!CI->getValue().isMaxValue()) { 535aa03649af255fbbb049f393a2cf7d533da86d951Dan Gohman CmpRHS = ConstantInt::get(CI->getValue() + 1); 536aa03649af255fbbb049f393a2cf7d533da86d951Dan Gohman Pred = ICmpInst::ICMP_UGE; 537aa03649af255fbbb049f393a2cf7d533da86d951Dan Gohman } 538aa03649af255fbbb049f393a2cf7d533da86d951Dan Gohman // Canonicalize UGE to ULT. 539aa03649af255fbbb049f393a2cf7d533da86d951Dan Gohman if (Pred == ICmpInst::ICMP_UGE) { 540aa03649af255fbbb049f393a2cf7d533da86d951Dan Gohman std::swap(TrueBB, FalseBB); 541aa03649af255fbbb049f393a2cf7d533da86d951Dan Gohman Pred = ICmpInst::ICMP_ULT; 542aa03649af255fbbb049f393a2cf7d533da86d951Dan Gohman } 543aa03649af255fbbb049f393a2cf7d533da86d951Dan Gohman // For now, analyze only LT loops for signed overflow. 544aa03649af255fbbb049f393a2cf7d533da86d951Dan Gohman if (Pred != ICmpInst::ICMP_SLT && Pred != ICmpInst::ICMP_ULT) 545d2067fd730b2b266f5c244d5871a244b534e10eaDan Gohman return 0; 546c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman 547aa03649af255fbbb049f393a2cf7d533da86d951Dan Gohman bool isSigned = Pred == ICmpInst::ICMP_SLT; 548c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman 549aa03649af255fbbb049f393a2cf7d533da86d951Dan Gohman // Get the increment instruction. Look past casts if we will 550c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman // be able to prove that the original induction variable doesn't 551aa03649af255fbbb049f393a2cf7d533da86d951Dan Gohman // undergo signed or unsigned overflow, respectively. 552dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen const Value *IncrInst = CmpLHS; 553aa03649af255fbbb049f393a2cf7d533da86d951Dan Gohman if (isSigned) { 554aa03649af255fbbb049f393a2cf7d533da86d951Dan Gohman if (const SExtInst *SI = dyn_cast<SExtInst>(CmpLHS)) { 555aa03649af255fbbb049f393a2cf7d533da86d951Dan Gohman if (!isa<ConstantInt>(CmpRHS) || 556aa03649af255fbbb049f393a2cf7d533da86d951Dan Gohman !cast<ConstantInt>(CmpRHS)->getValue() 557dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen .isSignedIntN(IncrInst->getType()->getPrimitiveSizeInBits())) 558d2067fd730b2b266f5c244d5871a244b534e10eaDan Gohman return 0; 559dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen IncrInst = SI->getOperand(0); 560aa03649af255fbbb049f393a2cf7d533da86d951Dan Gohman } 561aa03649af255fbbb049f393a2cf7d533da86d951Dan Gohman } else { 562aa03649af255fbbb049f393a2cf7d533da86d951Dan Gohman if (const ZExtInst *ZI = dyn_cast<ZExtInst>(CmpLHS)) { 563aa03649af255fbbb049f393a2cf7d533da86d951Dan Gohman if (!isa<ConstantInt>(CmpRHS) || 564aa03649af255fbbb049f393a2cf7d533da86d951Dan Gohman !cast<ConstantInt>(CmpRHS)->getValue() 565dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen .isIntN(IncrInst->getType()->getPrimitiveSizeInBits())) 566d2067fd730b2b266f5c244d5871a244b534e10eaDan Gohman return 0; 567dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen IncrInst = ZI->getOperand(0); 568aa03649af255fbbb049f393a2cf7d533da86d951Dan Gohman } 569c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman } 570c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman 571c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman // For now, only analyze induction variables that have simple increments. 572dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen const BinaryOperator *IncrOp = dyn_cast<BinaryOperator>(IncrInst); 573dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen if (!IncrOp || IncrOp->getOpcode() != Instruction::Add) 574dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen return 0; 575dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen IncrVal = dyn_cast<ConstantInt>(IncrOp->getOperand(1)); 576dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen if (!IncrVal) 577d2067fd730b2b266f5c244d5871a244b534e10eaDan Gohman return 0; 578c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman 579c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman // Make sure the PHI looks like a normal IV. 580c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman const PHINode *PN = dyn_cast<PHINode>(IncrOp->getOperand(0)); 581c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman if (!PN || PN->getNumIncomingValues() != 2) 582d2067fd730b2b266f5c244d5871a244b534e10eaDan Gohman return 0; 583c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman unsigned IncomingEdge = L->contains(PN->getIncomingBlock(0)); 584c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman unsigned BackEdge = !IncomingEdge; 585c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman if (!L->contains(PN->getIncomingBlock(BackEdge)) || 586c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman PN->getIncomingValue(BackEdge) != IncrOp) 587d2067fd730b2b266f5c244d5871a244b534e10eaDan Gohman return 0; 588aa03649af255fbbb049f393a2cf7d533da86d951Dan Gohman if (!L->contains(TrueBB)) 589d2067fd730b2b266f5c244d5871a244b534e10eaDan Gohman return 0; 590c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman 591c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman // For now, only analyze loops with a constant start value, so that 592aa03649af255fbbb049f393a2cf7d533da86d951Dan Gohman // we can easily determine if the start value is not a maximum value 593aa03649af255fbbb049f393a2cf7d533da86d951Dan Gohman // which would wrap on the first iteration. 594dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen InitialVal = dyn_cast<ConstantInt>(PN->getIncomingValue(IncomingEdge)); 595cad24c9abc834db5cf8f92019f99370507d8d07aDan Gohman if (!InitialVal) 596d2067fd730b2b266f5c244d5871a244b534e10eaDan Gohman return 0; 597aa03649af255fbbb049f393a2cf7d533da86d951Dan Gohman 598dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen // The upper limit need not be a constant; we'll check later. 599dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen LimitVal = dyn_cast<ConstantInt>(CmpRHS); 600dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen 601dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen // We detect the impossibility of wrapping in two cases, both of 602dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen // which require starting with a non-max value: 603dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen // - The IV counts up by one, and the loop iterates only while it remains 604dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen // less than a limiting value (any) in the same type. 605dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen // - The IV counts up by a positive increment other than 1, and the 606dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen // constant limiting value + the increment is less than the max value 607dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen // (computed as max-increment to avoid overflow) 608f5a309e989b8d2199cb542793e9edf48395d9fedDan Gohman if (isSigned && !InitialVal->getValue().isMaxSignedValue()) { 609dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen if (IncrVal->equalsInt(1)) 610dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen NoSignedWrap = true; // LimitVal need not be constant 611dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen else if (LimitVal) { 612dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen uint64_t numBits = LimitVal->getValue().getBitWidth(); 613dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen if (IncrVal->getValue().sgt(APInt::getNullValue(numBits)) && 614dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen (APInt::getSignedMaxValue(numBits) - IncrVal->getValue()) 615dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen .sgt(LimitVal->getValue())) 616dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen NoSignedWrap = true; 617dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen } 618dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen } else if (!isSigned && !InitialVal->getValue().isMaxValue()) { 619dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen if (IncrVal->equalsInt(1)) 620dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen NoUnsignedWrap = true; // LimitVal need not be constant 621dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen else if (LimitVal) { 622dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen uint64_t numBits = LimitVal->getValue().getBitWidth(); 623dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen if (IncrVal->getValue().ugt(APInt::getNullValue(numBits)) && 624dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen (APInt::getMaxValue(numBits) - IncrVal->getValue()) 625dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen .ugt(LimitVal->getValue())) 626dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen NoUnsignedWrap = true; 627dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen } 628dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen } 629d2067fd730b2b266f5c244d5871a244b534e10eaDan Gohman return PN; 630c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman} 631c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman 632dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesenstatic Value *getSignExtendedTruncVar(const SCEVAddRecExpr *AR, 633dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen ScalarEvolution *SE, 634dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen const Type *LargestType, Loop *L, 635dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen const Type *myType, 636dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen SCEVExpander &Rewriter, 637dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen BasicBlock::iterator InsertPt) { 638dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen SCEVHandle ExtendedStart = 639dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen SE->getSignExtendExpr(AR->getStart(), LargestType); 640dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen SCEVHandle ExtendedStep = 641dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen SE->getSignExtendExpr(AR->getStepRecurrence(*SE), LargestType); 642dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen SCEVHandle ExtendedAddRec = 643dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen SE->getAddRecExpr(ExtendedStart, ExtendedStep, L); 644dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen if (LargestType != myType) 645dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen ExtendedAddRec = SE->getTruncateExpr(ExtendedAddRec, myType); 646dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen return Rewriter.expandCodeFor(ExtendedAddRec, InsertPt); 647dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen} 648dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen 649dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesenstatic Value *getZeroExtendedTruncVar(const SCEVAddRecExpr *AR, 650dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen ScalarEvolution *SE, 651dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen const Type *LargestType, Loop *L, 652dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen const Type *myType, 653dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen SCEVExpander &Rewriter, 654dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen BasicBlock::iterator InsertPt) { 655dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen SCEVHandle ExtendedStart = 656dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen SE->getZeroExtendExpr(AR->getStart(), LargestType); 657dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen SCEVHandle ExtendedStep = 658dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen SE->getZeroExtendExpr(AR->getStepRecurrence(*SE), LargestType); 659dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen SCEVHandle ExtendedAddRec = 660dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen SE->getAddRecExpr(ExtendedStart, ExtendedStep, L); 661dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen if (LargestType != myType) 662dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen ExtendedAddRec = SE->getTruncateExpr(ExtendedAddRec, myType); 663dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen return Rewriter.expandCodeFor(ExtendedAddRec, InsertPt); 664dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen} 665dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen 666c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohmanbool IndVarSimplify::runOnLoop(Loop *L, LPPassManager &LPM) { 6675ee99979065d75605d150d7e567e4351024aae8fDevang Patel LI = &getAnalysis<LoopInfo>(); 6685ee99979065d75605d150d7e567e4351024aae8fDevang Patel SE = &getAnalysis<ScalarEvolution>(); 6695ee99979065d75605d150d7e567e4351024aae8fDevang Patel Changed = false; 67060f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman 67160f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman // If there are any floating-point or pointer recurrences, attempt to 67260f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman // transform them to use integer recurrences. 67360f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman RewriteNonIntegerIVs(L); 67460f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman 675c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman BasicBlock *Header = L->getHeader(); 676c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman BasicBlock *ExitingBlock = L->getExitingBlock(); 6771a6111f32dcc1f4b0bc5993a09af4adb65a23b3fChris Lattner SmallPtrSet<Instruction*, 16> DeadInsts; 678c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman 6799caed5440d59dac4b388152fe8b993dc0491e5e9Chris Lattner // Verify the input to the pass in already in LCSSA form. 6809caed5440d59dac4b388152fe8b993dc0491e5e9Chris Lattner assert(L->isLCSSAForm()); 6819caed5440d59dac4b388152fe8b993dc0491e5e9Chris Lattner 68240bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // Check to see if this loop has a computable loop-invariant execution count. 68340bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // If so, this means that we can compute the final value of any expressions 68440bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // that are recurrent in the loop, and substitute the exit values from the 68540bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // loop into any instructions outside of the loop that use the final values of 68640bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // the current expressions. 687394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner // 68846bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman SCEVHandle BackedgeTakenCount = SE->getBackedgeTakenCount(L); 68946bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman if (!isa<SCEVCouldNotCompute>(BackedgeTakenCount)) 69046bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman RewriteLoopExitValues(L, BackedgeTakenCount); 69140bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner 69240bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // Next, analyze all of the induction variables in the loop, canonicalizing 69340bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // auxillary induction variables. 69440bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner std::vector<std::pair<PHINode*, SCEVHandle> > IndVars; 69540bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner 6962da5c3dda6f5b9c4ec6d55008d33327764364bd4Reid Spencer for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) { 6972da5c3dda6f5b9c4ec6d55008d33327764364bd4Reid Spencer PHINode *PN = cast<PHINode>(I); 69842a75517250017a52afb03a0ade03cbd49559fe5Chris Lattner if (PN->getType()->isInteger()) { // FIXME: when we have fast-math, enable! 69940bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner SCEVHandle SCEV = SE->getSCEV(PN); 700cd3eb9b09882087761c811d349c2b3be4e5c8a34Dan Gohman // FIXME: It is an extremely bad idea to indvar substitute anything more 701cd3eb9b09882087761c811d349c2b3be4e5c8a34Dan Gohman // complex than affine induction variables. Doing so will put expensive 702cd3eb9b09882087761c811d349c2b3be4e5c8a34Dan Gohman // polynomial evaluations inside of the loop, and the str reduction pass 703cd3eb9b09882087761c811d349c2b3be4e5c8a34Dan Gohman // currently can only reduce affine polynomials. For now just disable 704cd3eb9b09882087761c811d349c2b3be4e5c8a34Dan Gohman // indvar subst on anything more complex than an affine addrec. 705cd3eb9b09882087761c811d349c2b3be4e5c8a34Dan Gohman if (SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(SCEV)) 706cd3eb9b09882087761c811d349c2b3be4e5c8a34Dan Gohman if (AR->getLoop() == L && AR->isAffine()) 707cd3eb9b09882087761c811d349c2b3be4e5c8a34Dan Gohman IndVars.push_back(std::make_pair(PN, SCEV)); 70840bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner } 7092da5c3dda6f5b9c4ec6d55008d33327764364bd4Reid Spencer } 710f016ea4ff80c56c467247a90567dd07bddb590f3Chris Lattner 711c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman // Compute the type of the largest recurrence expression, and collect 712c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman // the set of the types of the other recurrence expressions. 713c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman const Type *LargestType = 0; 714c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman SmallSetVector<const Type *, 4> SizesToInsert; 71546bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman if (!isa<SCEVCouldNotCompute>(BackedgeTakenCount)) { 71646bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman LargestType = BackedgeTakenCount->getType(); 71746bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman SizesToInsert.insert(BackedgeTakenCount->getType()); 718f50af088f19f525f3d1026eb61db77e0037a9f43Chris Lattner } 719c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman for (unsigned i = 0, e = IndVars.size(); i != e; ++i) { 720c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman const PHINode *PN = IndVars[i].first; 721c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman SizesToInsert.insert(PN->getType()); 722c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman const Type *EffTy = getEffectiveIndvarType(PN); 723c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman SizesToInsert.insert(EffTy); 724c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman if (!LargestType || 725c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman EffTy->getPrimitiveSizeInBits() > 726c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman LargestType->getPrimitiveSizeInBits()) 727c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman LargestType = EffTy; 728500597a1c39e91a3020587318ed61e737b6c613aChris Lattner } 729394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner 73040bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // Create a rewriter object which we'll use to transform the code with. 7314a7553e2da506a718f59869c03c5ce113eb40f7aChris Lattner SCEVExpander Rewriter(*SE, *LI); 73240bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner 73340bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // Now that we know the largest of of the induction variables in this loop, 73440bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // insert a canonical induction variable of the largest size. 735c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman Value *IndVar = 0; 736c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman if (!SizesToInsert.empty()) { 737c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman IndVar = Rewriter.getOrInsertCanonicalInductionVariable(L,LargestType); 738c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman ++NumInserted; 739c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman Changed = true; 740c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman DOUT << "INDVARS: New CanIV: " << *IndVar; 741d19534add90a2a894af61523b830887097bb780bDan Gohman } 74240bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner 743c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman // If we have a trip count expression, rewrite the loop's exit condition 744c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman // using it. We can currently only handle loops with a single exit. 745aa03649af255fbbb049f393a2cf7d533da86d951Dan Gohman bool NoSignedWrap = false; 746aa03649af255fbbb049f393a2cf7d533da86d951Dan Gohman bool NoUnsignedWrap = false; 747dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen const ConstantInt* InitialVal, * IncrVal, * LimitVal; 748d2067fd730b2b266f5c244d5871a244b534e10eaDan Gohman const PHINode *OrigControllingPHI = 0; 74946bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman if (!isa<SCEVCouldNotCompute>(BackedgeTakenCount) && ExitingBlock) 750c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman // Can't rewrite non-branch yet. 751c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman if (BranchInst *BI = dyn_cast<BranchInst>(ExitingBlock->getTerminator())) { 752c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman if (Instruction *OrigCond = dyn_cast<Instruction>(BI->getCondition())) { 753aa03649af255fbbb049f393a2cf7d533da86d951Dan Gohman // Determine if the OrigIV will ever undergo overflow. 754d2067fd730b2b266f5c244d5871a244b534e10eaDan Gohman OrigControllingPHI = 755d2067fd730b2b266f5c244d5871a244b534e10eaDan Gohman TestOrigIVForWrap(L, BI, OrigCond, 756dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen NoSignedWrap, NoUnsignedWrap, 757dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen InitialVal, IncrVal, LimitVal); 758c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman 759c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman // We'll be replacing the original condition, so it'll be dead. 760c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman DeadInsts.insert(OrigCond); 761c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman } 762c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman 76346bdfb0e6bb9de86b19562fc52fddefd7014cf73Dan Gohman LinearFunctionTestReplace(L, BackedgeTakenCount, IndVar, 76415cab2817b8f63fec0148609278bc2c1e05abb50Dan Gohman ExitingBlock, BI, Rewriter); 765c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman } 766c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman 76740bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // Now that we have a canonical induction variable, we can rewrite any 76840bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // recurrences in terms of the induction variable. Start with the auxillary 76940bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // induction variables, and recursively rewrite any of their uses. 77002dea8b39f3acad5de1df36273444d149145e7fcDan Gohman BasicBlock::iterator InsertPt = Header->getFirstNonPHI(); 77140bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner 7725d461d20aea308471f2a31b718a274bfee28b60cChris Lattner // If there were induction variables of other sizes, cast the primary 7735d461d20aea308471f2a31b718a274bfee28b60cChris Lattner // induction variable to the right size for them, avoiding the need for the 7745d461d20aea308471f2a31b718a274bfee28b60cChris Lattner // code evaluation methods to insert induction variables of different sizes. 775c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman for (unsigned i = 0, e = SizesToInsert.size(); i != e; ++i) { 776c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman const Type *Ty = SizesToInsert[i]; 777c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman if (Ty != LargestType) { 778c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman Instruction *New = new TruncInst(IndVar, Ty, "indvar", InsertPt); 779c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman Rewriter.addInsertedValue(New, SE->getSCEV(New)); 780c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman DOUT << "INDVARS: Made trunc IV for type " << *Ty << ": " 781c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman << *New << "\n"; 782a54b7cbd452b3adb2f51346140d996b29c2cdb30Reid Spencer } 783fcb81f5f4cbac61851b7dec403961cf88e614aa1Chris Lattner } 784fcb81f5f4cbac61851b7dec403961cf88e614aa1Chris Lattner 785ee4f13a9046c380725cdeab62d57722db375c473Chris Lattner // Rewrite all induction variables in terms of the canonical induction 786ee4f13a9046c380725cdeab62d57722db375c473Chris Lattner // variable. 78740bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner while (!IndVars.empty()) { 78840bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner PHINode *PN = IndVars.back().first; 7891a5e936c53acda949afd8fa21b5a837b1d9fede9Dan Gohman SCEVAddRecExpr *AR = cast<SCEVAddRecExpr>(IndVars.back().second); 7901a5e936c53acda949afd8fa21b5a837b1d9fede9Dan Gohman Value *NewVal = Rewriter.expandCodeFor(AR, InsertPt); 7911a5e936c53acda949afd8fa21b5a837b1d9fede9Dan Gohman DOUT << "INDVARS: Rewrote IV '" << *AR << "' " << *PN 792ee4f13a9046c380725cdeab62d57722db375c473Chris Lattner << " into = " << *NewVal << "\n"; 7936934a04a8c15e9971cd1ea4d5c8df2d7afdd5be5Chris Lattner NewVal->takeName(PN); 7945d461d20aea308471f2a31b718a274bfee28b60cChris Lattner 795c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman /// If the new canonical induction variable is wider than the original, 796c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman /// and the original has uses that are casts to wider types, see if the 797c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman /// truncate and extend can be omitted. 798d2067fd730b2b266f5c244d5871a244b534e10eaDan Gohman if (PN == OrigControllingPHI && PN->getType() != LargestType) 799c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman for (Value::use_iterator UI = PN->use_begin(), UE = PN->use_end(); 800aa03649af255fbbb049f393a2cf7d533da86d951Dan Gohman UI != UE; ++UI) { 801d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen Instruction *UInst = dyn_cast<Instruction>(*UI); 802d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen if (UInst && isa<SExtInst>(UInst) && NoSignedWrap) { 803dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen Value *TruncIndVar = getSignExtendedTruncVar(AR, SE, LargestType, L, 804d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen UInst->getType(), Rewriter, InsertPt); 805d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen UInst->replaceAllUsesWith(TruncIndVar); 806d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen DeadInsts.insert(UInst); 807c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman } 808dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen // See if we can figure out sext(i+constant) doesn't wrap, so we can 809dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen // use a larger add. This is common in subscripting. 810dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen if (UInst && UInst->getOpcode()==Instruction::Add && 811dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen UInst->hasOneUse() && 812dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen isa<ConstantInt>(UInst->getOperand(1)) && 813d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen NoSignedWrap && LimitVal) { 814d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen uint64_t oldBitSize = LimitVal->getValue().getBitWidth(); 815d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen uint64_t newBitSize = LargestType->getPrimitiveSizeInBits(); 816d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen ConstantInt* AddRHS = dyn_cast<ConstantInt>(UInst->getOperand(1)); 817d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen if (((APInt::getSignedMaxValue(oldBitSize) - IncrVal->getValue()) - 818d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen AddRHS->getValue()).sgt(LimitVal->getValue())) { 819d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen // We've determined this is (i+constant) and it won't overflow. 820d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen if (isa<SExtInst>(UInst->use_begin())) { 821d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen SExtInst* oldSext = dyn_cast<SExtInst>(UInst->use_begin()); 822d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen Value *TruncIndVar = getSignExtendedTruncVar(AR, SE, LargestType, 823d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen L, oldSext->getType(), Rewriter, 824d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen InsertPt); 825d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen APInt APcopy = APInt(AddRHS->getValue()); 826d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen ConstantInt* newAddRHS =ConstantInt::get(APcopy.sext(newBitSize)); 827d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen Value *NewAdd = 828d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen BinaryOperator::CreateAdd(TruncIndVar, newAddRHS, 829d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen UInst->getName()+".nosex", UInst); 830d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen oldSext->replaceAllUsesWith(NewAdd); 831d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen if (Instruction *DeadUse = dyn_cast<Instruction>(oldSext)) 832d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen DeadInsts.insert(DeadUse); 833d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen DeadInsts.insert(UInst); 834d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen } 835dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen } 836dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen } 837d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen if (UInst && isa<ZExtInst>(UInst) && NoUnsignedWrap) { 838dd1f9e4bf6e7d427fd581728f3d2e431e12e6e71Dale Johannesen Value *TruncIndVar = getZeroExtendedTruncVar(AR, SE, LargestType, L, 839d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen UInst->getType(), Rewriter, InsertPt); 840d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen UInst->replaceAllUsesWith(TruncIndVar); 841d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen DeadInsts.insert(UInst); 842d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen } 843d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen // If we have zext(i&constant), we can use the larger variable. This 844d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen // is not common but is a bottleneck in Openssl. 845d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen // (RHS doesn't have to be constant. There should be a better approach 846d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen // than bottom-up pattern matching for this...) 847d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen if (UInst && UInst->getOpcode()==Instruction::And && 848d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen UInst->hasOneUse() && 849d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen isa<ConstantInt>(UInst->getOperand(1)) && 850d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen isa<ZExtInst>(UInst->use_begin())) { 851d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen uint64_t newBitSize = LargestType->getPrimitiveSizeInBits(); 852d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen ConstantInt* AndRHS = dyn_cast<ConstantInt>(UInst->getOperand(1)); 853d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen ZExtInst* oldZext = dyn_cast<ZExtInst>(UInst->use_begin()); 854d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen Value *TruncIndVar = getSignExtendedTruncVar(AR, SE, LargestType, 855d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen L, oldZext->getType(), Rewriter, InsertPt); 856d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen APInt APcopy = APInt(AndRHS->getValue()); 857d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen ConstantInt* newAndRHS = ConstantInt::get(APcopy.zext(newBitSize)); 858d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen Value *NewAnd = 859d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen BinaryOperator::CreateAnd(TruncIndVar, newAndRHS, 860d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen UInst->getName()+".nozex", UInst); 861d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen oldZext->replaceAllUsesWith(NewAnd); 862d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen if (Instruction *DeadUse = dyn_cast<Instruction>(oldZext)) 863aa03649af255fbbb049f393a2cf7d533da86d951Dan Gohman DeadInsts.insert(DeadUse); 864d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen DeadInsts.insert(UInst); 865d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen } 866d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen // If we have zext((i+constant)&constant), we can use the larger 867d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen // variable even if the add does overflow. This works whenever the 868d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen // constant being ANDed is the same size as i, which it presumably is. 869d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen // We don't need to restrict the expression being and'ed to i+const, 870d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen // but we have to promote everything in it, so it's convenient. 871d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen if (UInst && UInst->getOpcode()==Instruction::Add && 872d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen UInst->hasOneUse() && 873d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen isa<ConstantInt>(UInst->getOperand(1))) { 874d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen uint64_t newBitSize = LargestType->getPrimitiveSizeInBits(); 875d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen ConstantInt* AddRHS = dyn_cast<ConstantInt>(UInst->getOperand(1)); 876d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen Instruction *UInst2 = dyn_cast<Instruction>(UInst->use_begin()); 877d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen if (UInst2 && UInst2->getOpcode() == Instruction::And && 878d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen UInst2->hasOneUse() && 879d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen isa<ConstantInt>(UInst2->getOperand(1)) && 880d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen isa<ZExtInst>(UInst2->use_begin())) { 881d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen ZExtInst* oldZext = dyn_cast<ZExtInst>(UInst2->use_begin()); 882d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen Value *TruncIndVar = getSignExtendedTruncVar(AR, SE, LargestType, 883d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen L, oldZext->getType(), Rewriter, InsertPt); 884d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen ConstantInt* AndRHS = dyn_cast<ConstantInt>(UInst2->getOperand(1)); 885d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen APInt APcopy = APInt(AddRHS->getValue()); 886d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen ConstantInt* newAddRHS = ConstantInt::get(APcopy.zext(newBitSize)); 887d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen Value *NewAdd = 888d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen BinaryOperator::CreateAdd(TruncIndVar, newAddRHS, 889d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen UInst->getName()+".nozex", UInst2); 890d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen APInt APcopy2 = APInt(AndRHS->getValue()); 891d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen ConstantInt* newAndRHS = ConstantInt::get(APcopy2.zext(newBitSize)); 892d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen Value *NewAnd = 893d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen BinaryOperator::CreateAnd(NewAdd, newAndRHS, 894d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen UInst->getName()+".nozex", UInst2); 895d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen oldZext->replaceAllUsesWith(NewAnd); 896d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen if (Instruction *DeadUse = dyn_cast<Instruction>(oldZext)) 897d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen DeadInsts.insert(DeadUse); 898d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen DeadInsts.insert(UInst); 899d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen DeadInsts.insert(UInst2); 900d3325d289736dec93c37f24bffd63cb91b643b87Dale Johannesen } 901aa03649af255fbbb049f393a2cf7d533da86d951Dan Gohman } 902aa03649af255fbbb049f393a2cf7d533da86d951Dan Gohman } 903c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman 90440bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner // Replace the old PHI Node with the inserted computation. 905fcb81f5f4cbac61851b7dec403961cf88e614aa1Chris Lattner PN->replaceAllUsesWith(NewVal); 90640bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner DeadInsts.insert(PN); 90740bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner IndVars.pop_back(); 90840bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner ++NumRemoved; 90940bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner Changed = true; 910500597a1c39e91a3020587318ed61e737b6c613aChris Lattner } 911ba4f3f6a419326df190599421fa149c90235cb72Chris Lattner 9121363e85df74627530ceede53280613c62a4cdbe3Chris Lattner DeleteTriviallyDeadInstructions(DeadInsts); 9139caed5440d59dac4b388152fe8b993dc0491e5e9Chris Lattner assert(L->isLCSSAForm()); 9145ee99979065d75605d150d7e567e4351024aae8fDevang Patel return Changed; 9156148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner} 916d22a849282c45bbf7eb1734c274294d81e49e3a8Devang Patel 91713877bf6c20621541ff71583c626bda68ef09219Devang Patel/// Return true if it is OK to use SIToFPInst for an inducation variable 91813877bf6c20621541ff71583c626bda68ef09219Devang Patel/// with given inital and exit values. 91913877bf6c20621541ff71583c626bda68ef09219Devang Patelstatic bool useSIToFPInst(ConstantFP &InitV, ConstantFP &ExitV, 92013877bf6c20621541ff71583c626bda68ef09219Devang Patel uint64_t intIV, uint64_t intEV) { 92113877bf6c20621541ff71583c626bda68ef09219Devang Patel 922cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman if (InitV.getValueAPF().isNegative() || ExitV.getValueAPF().isNegative()) 92313877bf6c20621541ff71583c626bda68ef09219Devang Patel return true; 92413877bf6c20621541ff71583c626bda68ef09219Devang Patel 92513877bf6c20621541ff71583c626bda68ef09219Devang Patel // If the iteration range can be handled by SIToFPInst then use it. 92613877bf6c20621541ff71583c626bda68ef09219Devang Patel APInt Max = APInt::getSignedMaxValue(32); 9279bef70609cdee0bf7e641a02a56890610a5a7125Bill Wendling if (Max.getZExtValue() > static_cast<uint64_t>(abs(intEV - intIV))) 92813877bf6c20621541ff71583c626bda68ef09219Devang Patel return true; 929cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 93013877bf6c20621541ff71583c626bda68ef09219Devang Patel return false; 93113877bf6c20621541ff71583c626bda68ef09219Devang Patel} 93213877bf6c20621541ff71583c626bda68ef09219Devang Patel 93313877bf6c20621541ff71583c626bda68ef09219Devang Patel/// convertToInt - Convert APF to an integer, if possible. 934cd40233429fce385ae4b22301ce705273a6951a1Devang Patelstatic bool convertToInt(const APFloat &APF, uint64_t *intVal) { 935cd40233429fce385ae4b22301ce705273a6951a1Devang Patel 936cd40233429fce385ae4b22301ce705273a6951a1Devang Patel bool isExact = false; 937794a7dbce030f93315b1305f83a374232f09bba5Evan Cheng if (&APF.getSemantics() == &APFloat::PPCDoubleDouble) 938794a7dbce030f93315b1305f83a374232f09bba5Evan Cheng return false; 939cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman if (APF.convertToInteger(intVal, 32, APF.isNegative(), 940cd40233429fce385ae4b22301ce705273a6951a1Devang Patel APFloat::rmTowardZero, &isExact) 941cd40233429fce385ae4b22301ce705273a6951a1Devang Patel != APFloat::opOK) 942cd40233429fce385ae4b22301ce705273a6951a1Devang Patel return false; 943cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman if (!isExact) 944cd40233429fce385ae4b22301ce705273a6951a1Devang Patel return false; 945cd40233429fce385ae4b22301ce705273a6951a1Devang Patel return true; 946cd40233429fce385ae4b22301ce705273a6951a1Devang Patel 947cd40233429fce385ae4b22301ce705273a6951a1Devang Patel} 948cd40233429fce385ae4b22301ce705273a6951a1Devang Patel 94958d43d4a41b21085c063bdd21a2abb68056e2a6fDevang Patel/// HandleFloatingPointIV - If the loop has floating induction variable 95058d43d4a41b21085c063bdd21a2abb68056e2a6fDevang Patel/// then insert corresponding integer induction variable if possible. 95184e3515974407a606289c6e762a0419723b7918fDevang Patel/// For example, 95284e3515974407a606289c6e762a0419723b7918fDevang Patel/// for(double i = 0; i < 10000; ++i) 95384e3515974407a606289c6e762a0419723b7918fDevang Patel/// bar(i) 95484e3515974407a606289c6e762a0419723b7918fDevang Patel/// is converted into 95584e3515974407a606289c6e762a0419723b7918fDevang Patel/// for(int i = 0; i < 10000; ++i) 95684e3515974407a606289c6e762a0419723b7918fDevang Patel/// bar((double)i); 95784e3515974407a606289c6e762a0419723b7918fDevang Patel/// 958cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohmanvoid IndVarSimplify::HandleFloatingPointIV(Loop *L, PHINode *PH, 95984e3515974407a606289c6e762a0419723b7918fDevang Patel SmallPtrSet<Instruction*, 16> &DeadInsts) { 96084e3515974407a606289c6e762a0419723b7918fDevang Patel 96184e3515974407a606289c6e762a0419723b7918fDevang Patel unsigned IncomingEdge = L->contains(PH->getIncomingBlock(0)); 96284e3515974407a606289c6e762a0419723b7918fDevang Patel unsigned BackEdge = IncomingEdge^1; 963cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 96484e3515974407a606289c6e762a0419723b7918fDevang Patel // Check incoming value. 965cd40233429fce385ae4b22301ce705273a6951a1Devang Patel ConstantFP *InitValue = dyn_cast<ConstantFP>(PH->getIncomingValue(IncomingEdge)); 966cd40233429fce385ae4b22301ce705273a6951a1Devang Patel if (!InitValue) return; 967cd40233429fce385ae4b22301ce705273a6951a1Devang Patel uint64_t newInitValue = Type::Int32Ty->getPrimitiveSizeInBits(); 968cd40233429fce385ae4b22301ce705273a6951a1Devang Patel if (!convertToInt(InitValue->getValueAPF(), &newInitValue)) 969cd40233429fce385ae4b22301ce705273a6951a1Devang Patel return; 970cd40233429fce385ae4b22301ce705273a6951a1Devang Patel 971cd40233429fce385ae4b22301ce705273a6951a1Devang Patel // Check IV increment. Reject this PH if increement operation is not 972cd40233429fce385ae4b22301ce705273a6951a1Devang Patel // an add or increment value can not be represented by an integer. 973cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman BinaryOperator *Incr = 97484e3515974407a606289c6e762a0419723b7918fDevang Patel dyn_cast<BinaryOperator>(PH->getIncomingValue(BackEdge)); 97584e3515974407a606289c6e762a0419723b7918fDevang Patel if (!Incr) return; 97684e3515974407a606289c6e762a0419723b7918fDevang Patel if (Incr->getOpcode() != Instruction::Add) return; 97784e3515974407a606289c6e762a0419723b7918fDevang Patel ConstantFP *IncrValue = NULL; 97884e3515974407a606289c6e762a0419723b7918fDevang Patel unsigned IncrVIndex = 1; 97984e3515974407a606289c6e762a0419723b7918fDevang Patel if (Incr->getOperand(1) == PH) 98084e3515974407a606289c6e762a0419723b7918fDevang Patel IncrVIndex = 0; 98184e3515974407a606289c6e762a0419723b7918fDevang Patel IncrValue = dyn_cast<ConstantFP>(Incr->getOperand(IncrVIndex)); 98284e3515974407a606289c6e762a0419723b7918fDevang Patel if (!IncrValue) return; 983cd40233429fce385ae4b22301ce705273a6951a1Devang Patel uint64_t newIncrValue = Type::Int32Ty->getPrimitiveSizeInBits(); 984cd40233429fce385ae4b22301ce705273a6951a1Devang Patel if (!convertToInt(IncrValue->getValueAPF(), &newIncrValue)) 985cd40233429fce385ae4b22301ce705273a6951a1Devang Patel return; 986cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 987cd40233429fce385ae4b22301ce705273a6951a1Devang Patel // Check Incr uses. One user is PH and the other users is exit condition used 988cd40233429fce385ae4b22301ce705273a6951a1Devang Patel // by the conditional terminator. 98984e3515974407a606289c6e762a0419723b7918fDevang Patel Value::use_iterator IncrUse = Incr->use_begin(); 99084e3515974407a606289c6e762a0419723b7918fDevang Patel Instruction *U1 = cast<Instruction>(IncrUse++); 99184e3515974407a606289c6e762a0419723b7918fDevang Patel if (IncrUse == Incr->use_end()) return; 99284e3515974407a606289c6e762a0419723b7918fDevang Patel Instruction *U2 = cast<Instruction>(IncrUse++); 99384e3515974407a606289c6e762a0419723b7918fDevang Patel if (IncrUse != Incr->use_end()) return; 994cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 99584e3515974407a606289c6e762a0419723b7918fDevang Patel // Find exit condition. 99684e3515974407a606289c6e762a0419723b7918fDevang Patel FCmpInst *EC = dyn_cast<FCmpInst>(U1); 99784e3515974407a606289c6e762a0419723b7918fDevang Patel if (!EC) 99884e3515974407a606289c6e762a0419723b7918fDevang Patel EC = dyn_cast<FCmpInst>(U2); 99984e3515974407a606289c6e762a0419723b7918fDevang Patel if (!EC) return; 100084e3515974407a606289c6e762a0419723b7918fDevang Patel 100184e3515974407a606289c6e762a0419723b7918fDevang Patel if (BranchInst *BI = dyn_cast<BranchInst>(EC->getParent()->getTerminator())) { 100284e3515974407a606289c6e762a0419723b7918fDevang Patel if (!BI->isConditional()) return; 100384e3515974407a606289c6e762a0419723b7918fDevang Patel if (BI->getCondition() != EC) return; 100458d43d4a41b21085c063bdd21a2abb68056e2a6fDevang Patel } 100584e3515974407a606289c6e762a0419723b7918fDevang Patel 1006cd40233429fce385ae4b22301ce705273a6951a1Devang Patel // Find exit value. If exit value can not be represented as an interger then 1007cd40233429fce385ae4b22301ce705273a6951a1Devang Patel // do not handle this floating point PH. 100884e3515974407a606289c6e762a0419723b7918fDevang Patel ConstantFP *EV = NULL; 100984e3515974407a606289c6e762a0419723b7918fDevang Patel unsigned EVIndex = 1; 101084e3515974407a606289c6e762a0419723b7918fDevang Patel if (EC->getOperand(1) == Incr) 101184e3515974407a606289c6e762a0419723b7918fDevang Patel EVIndex = 0; 101284e3515974407a606289c6e762a0419723b7918fDevang Patel EV = dyn_cast<ConstantFP>(EC->getOperand(EVIndex)); 101384e3515974407a606289c6e762a0419723b7918fDevang Patel if (!EV) return; 101484e3515974407a606289c6e762a0419723b7918fDevang Patel uint64_t intEV = Type::Int32Ty->getPrimitiveSizeInBits(); 1015cd40233429fce385ae4b22301ce705273a6951a1Devang Patel if (!convertToInt(EV->getValueAPF(), &intEV)) 101684e3515974407a606289c6e762a0419723b7918fDevang Patel return; 1017cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 101884e3515974407a606289c6e762a0419723b7918fDevang Patel // Find new predicate for integer comparison. 101984e3515974407a606289c6e762a0419723b7918fDevang Patel CmpInst::Predicate NewPred = CmpInst::BAD_ICMP_PREDICATE; 102084e3515974407a606289c6e762a0419723b7918fDevang Patel switch (EC->getPredicate()) { 102184e3515974407a606289c6e762a0419723b7918fDevang Patel case CmpInst::FCMP_OEQ: 102284e3515974407a606289c6e762a0419723b7918fDevang Patel case CmpInst::FCMP_UEQ: 102384e3515974407a606289c6e762a0419723b7918fDevang Patel NewPred = CmpInst::ICMP_EQ; 102484e3515974407a606289c6e762a0419723b7918fDevang Patel break; 102584e3515974407a606289c6e762a0419723b7918fDevang Patel case CmpInst::FCMP_OGT: 102684e3515974407a606289c6e762a0419723b7918fDevang Patel case CmpInst::FCMP_UGT: 102784e3515974407a606289c6e762a0419723b7918fDevang Patel NewPred = CmpInst::ICMP_UGT; 102884e3515974407a606289c6e762a0419723b7918fDevang Patel break; 102984e3515974407a606289c6e762a0419723b7918fDevang Patel case CmpInst::FCMP_OGE: 103084e3515974407a606289c6e762a0419723b7918fDevang Patel case CmpInst::FCMP_UGE: 103184e3515974407a606289c6e762a0419723b7918fDevang Patel NewPred = CmpInst::ICMP_UGE; 103284e3515974407a606289c6e762a0419723b7918fDevang Patel break; 103384e3515974407a606289c6e762a0419723b7918fDevang Patel case CmpInst::FCMP_OLT: 103484e3515974407a606289c6e762a0419723b7918fDevang Patel case CmpInst::FCMP_ULT: 103584e3515974407a606289c6e762a0419723b7918fDevang Patel NewPred = CmpInst::ICMP_ULT; 103684e3515974407a606289c6e762a0419723b7918fDevang Patel break; 103784e3515974407a606289c6e762a0419723b7918fDevang Patel case CmpInst::FCMP_OLE: 103884e3515974407a606289c6e762a0419723b7918fDevang Patel case CmpInst::FCMP_ULE: 103984e3515974407a606289c6e762a0419723b7918fDevang Patel NewPred = CmpInst::ICMP_ULE; 104084e3515974407a606289c6e762a0419723b7918fDevang Patel break; 104184e3515974407a606289c6e762a0419723b7918fDevang Patel default: 104284e3515974407a606289c6e762a0419723b7918fDevang Patel break; 104358d43d4a41b21085c063bdd21a2abb68056e2a6fDevang Patel } 104484e3515974407a606289c6e762a0419723b7918fDevang Patel if (NewPred == CmpInst::BAD_ICMP_PREDICATE) return; 1045cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 104684e3515974407a606289c6e762a0419723b7918fDevang Patel // Insert new integer induction variable. 104784e3515974407a606289c6e762a0419723b7918fDevang Patel PHINode *NewPHI = PHINode::Create(Type::Int32Ty, 104884e3515974407a606289c6e762a0419723b7918fDevang Patel PH->getName()+".int", PH); 1049cd40233429fce385ae4b22301ce705273a6951a1Devang Patel NewPHI->addIncoming(ConstantInt::get(Type::Int32Ty, newInitValue), 105084e3515974407a606289c6e762a0419723b7918fDevang Patel PH->getIncomingBlock(IncomingEdge)); 105184e3515974407a606289c6e762a0419723b7918fDevang Patel 1052cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman Value *NewAdd = BinaryOperator::CreateAdd(NewPHI, 1053cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman ConstantInt::get(Type::Int32Ty, 1054cd40233429fce385ae4b22301ce705273a6951a1Devang Patel newIncrValue), 105584e3515974407a606289c6e762a0419723b7918fDevang Patel Incr->getName()+".int", Incr); 105684e3515974407a606289c6e762a0419723b7918fDevang Patel NewPHI->addIncoming(NewAdd, PH->getIncomingBlock(BackEdge)); 105784e3515974407a606289c6e762a0419723b7918fDevang Patel 105884e3515974407a606289c6e762a0419723b7918fDevang Patel ConstantInt *NewEV = ConstantInt::get(Type::Int32Ty, intEV); 105984e3515974407a606289c6e762a0419723b7918fDevang Patel Value *LHS = (EVIndex == 1 ? NewPHI->getIncomingValue(BackEdge) : NewEV); 106084e3515974407a606289c6e762a0419723b7918fDevang Patel Value *RHS = (EVIndex == 1 ? NewEV : NewPHI->getIncomingValue(BackEdge)); 1061cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman ICmpInst *NewEC = new ICmpInst(NewPred, LHS, RHS, EC->getNameStart(), 106284e3515974407a606289c6e762a0419723b7918fDevang Patel EC->getParent()->getTerminator()); 1063cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 106484e3515974407a606289c6e762a0419723b7918fDevang Patel // Delete old, floating point, exit comparision instruction. 106584e3515974407a606289c6e762a0419723b7918fDevang Patel EC->replaceAllUsesWith(NewEC); 106684e3515974407a606289c6e762a0419723b7918fDevang Patel DeadInsts.insert(EC); 1067cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 106884e3515974407a606289c6e762a0419723b7918fDevang Patel // Delete old, floating point, increment instruction. 106984e3515974407a606289c6e762a0419723b7918fDevang Patel Incr->replaceAllUsesWith(UndefValue::get(Incr->getType())); 107084e3515974407a606289c6e762a0419723b7918fDevang Patel DeadInsts.insert(Incr); 1071cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 107213877bf6c20621541ff71583c626bda68ef09219Devang Patel // Replace floating induction variable. Give SIToFPInst preference over 107313877bf6c20621541ff71583c626bda68ef09219Devang Patel // UIToFPInst because it is faster on platforms that are widely used. 107413877bf6c20621541ff71583c626bda68ef09219Devang Patel if (useSIToFPInst(*InitValue, *EV, newInitValue, intEV)) { 1075cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman SIToFPInst *Conv = new SIToFPInst(NewPHI, PH->getType(), "indvar.conv", 1076cd40233429fce385ae4b22301ce705273a6951a1Devang Patel PH->getParent()->getFirstNonPHI()); 1077cd40233429fce385ae4b22301ce705273a6951a1Devang Patel PH->replaceAllUsesWith(Conv); 1078cd40233429fce385ae4b22301ce705273a6951a1Devang Patel } else { 1079cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman UIToFPInst *Conv = new UIToFPInst(NewPHI, PH->getType(), "indvar.conv", 1080cd40233429fce385ae4b22301ce705273a6951a1Devang Patel PH->getParent()->getFirstNonPHI()); 1081cd40233429fce385ae4b22301ce705273a6951a1Devang Patel PH->replaceAllUsesWith(Conv); 1082cd40233429fce385ae4b22301ce705273a6951a1Devang Patel } 108384e3515974407a606289c6e762a0419723b7918fDevang Patel DeadInsts.insert(PH); 108458d43d4a41b21085c063bdd21a2abb68056e2a6fDevang Patel} 108558d43d4a41b21085c063bdd21a2abb68056e2a6fDevang Patel 1086