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// 1440bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner// If the trip count of a loop is computable, this pass also makes the following 1540bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner// changes: 1640bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner// 1. The exit condition for the loop is canonicalized to compare the 1740bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner// induction value against the exit value. This turns loops like: 1840bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner// 'for (i = 7; i*i < 1000; ++i)' into 'for (i = 0; i != 25; ++i)' 1940bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner// 2. Any use outside of the loop of an expression derived from the indvar 2040bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner// is changed to compute the derived value outside of the loop, eliminating 2140bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner// the dependence on the exit value of the induction variable. If the only 2240bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner// purpose of the loop is to compute the exit value of some derived 2340bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner// expression, this transformation will make the loop dead. 2440bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner// 256148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner//===----------------------------------------------------------------------===// 266148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner 270e5f499638c8d277b9dc4a4385712177c53b5681Chris Lattner#define DEBUG_TYPE "indvars" 28022103b3f33febb7e54b8fdf2c9bc461eea78cbaChris Lattner#include "llvm/Transforms/Scalar.h" 29d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/DenseMap.h" 30d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/SmallVector.h" 31d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/Statistic.h" 32d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Analysis/Dominators.h" 33d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Analysis/LoopInfo.h" 34d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Analysis/LoopPass.h" 35d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Analysis/ScalarEvolutionExpander.h" 360b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/BasicBlock.h" 370b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Constants.h" 380b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/DataLayout.h" 390b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Instructions.h" 400b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/IntrinsicInst.h" 410b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/LLVMContext.h" 420b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Type.h" 43455889aa79e3463a4b0f2161e3d9d72a683268b6Chris Lattner#include "llvm/Support/CFG.h" 4456caa098085977c14cfab39d92c7dfa15dde0d90Andrew Trick#include "llvm/Support/CommandLine.h" 45ee4f13a9046c380725cdeab62d57722db375c473Chris Lattner#include "llvm/Support/Debug.h" 46bdff548e4dd577a72094d57b282de4e765643b96Chris Lattner#include "llvm/Support/raw_ostream.h" 47d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Target/TargetLibraryInfo.h" 4881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman#include "llvm/Transforms/Utils/BasicBlockUtils.h" 49d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Transforms/Utils/Local.h" 504b4bb71bcdfd8c17cd4acb6116fc9a56c5fecd47Andrew Trick#include "llvm/Transforms/Utils/SimplifyIndVar.h" 5147df12d80db90e125e9f2ff764286ee11665476dJohn Criswellusing namespace llvm; 52d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 532fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew TrickSTATISTIC(NumWidened , "Number of indvars widened"); 542fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew TrickSTATISTIC(NumReplaced , "Number of exit values replaced"); 552fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew TrickSTATISTIC(NumLFTR , "Number of loop exit tests replaced"); 562fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew TrickSTATISTIC(NumElimExt , "Number of IV sign/zero extends eliminated"); 57037d1c0c7e01cefeff7e538682c9a1e536e14030Andrew TrickSTATISTIC(NumElimIV , "Number of congruent IVs eliminated"); 583324e718bc9ac2ede08a14c325848b576849542bChris Lattner 590861f5793a1834f02b522fb86fb037cd592c134fBenjamin Kramer// Trip count verification can be enabled by default under NDEBUG if we 600861f5793a1834f02b522fb86fb037cd592c134fBenjamin Kramer// implement a strong expression equivalence checker in SCEV. Until then, we 610861f5793a1834f02b522fb86fb037cd592c134fBenjamin Kramer// use the verify-indvars flag, which may assert in some cases. 620861f5793a1834f02b522fb86fb037cd592c134fBenjamin Kramerstatic cl::opt<bool> VerifyIndvars( 630861f5793a1834f02b522fb86fb037cd592c134fBenjamin Kramer "verify-indvars", cl::Hidden, 640861f5793a1834f02b522fb86fb037cd592c134fBenjamin Kramer cl::desc("Verify the ScalarEvolution result after running indvars")); 6537da40875873d70b83dc08b2803052bec9b68886Andrew Trick 660e5f499638c8d277b9dc4a4385712177c53b5681Chris Lattnernamespace { 673e8b6631e67e01e4960a7ba4668a50c596607473Chris Lattner class IndVarSimplify : public LoopPass { 6840bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner LoopInfo *LI; 6940bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner ScalarEvolution *SE; 70de53dc03f5c1549f3176e979bbeeac965dfa5cbcDan Gohman DominatorTree *DT; 713574eca1b02600bac4e625297f4ecf745f4c4f32Micah Villmow DataLayout *TD; 728e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer TargetLibraryInfo *TLI; 732fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick 74b12a754cce0c1d5542af605203a47820edba454dAndrew Trick SmallVector<WeakVH, 16> DeadInsts; 7515cad759fe2048ac5eb137c6bb0ab7287538677eChris Lattner bool Changed; 763324e718bc9ac2ede08a14c325848b576849542bChris Lattner public: 77794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel 785668cf77a77493ec9f2a9b33f08125e885c8e4cfDan Gohman static char ID; // Pass identification, replacement for typeid 79db0d666578388026278c17f848095b396b7ea27dAndrew Trick IndVarSimplify() : LoopPass(ID), LI(0), SE(0), DT(0), TD(0), 8015832f61775040995bb8aa6056176425bc2c9088Andrew Trick Changed(false) { 81081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeIndVarSimplifyPass(*PassRegistry::getPassRegistry()); 82081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson } 83794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel 845668cf77a77493ec9f2a9b33f08125e885c8e4cfDan Gohman virtual bool runOnLoop(Loop *L, LPPassManager &LPM); 8560f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman 865668cf77a77493ec9f2a9b33f08125e885c8e4cfDan Gohman virtual void getAnalysisUsage(AnalysisUsage &AU) const { 875668cf77a77493ec9f2a9b33f08125e885c8e4cfDan Gohman AU.addRequired<DominatorTree>(); 885668cf77a77493ec9f2a9b33f08125e885c8e4cfDan Gohman AU.addRequired<LoopInfo>(); 895668cf77a77493ec9f2a9b33f08125e885c8e4cfDan Gohman AU.addRequired<ScalarEvolution>(); 905668cf77a77493ec9f2a9b33f08125e885c8e4cfDan Gohman AU.addRequiredID(LoopSimplifyID); 915668cf77a77493ec9f2a9b33f08125e885c8e4cfDan Gohman AU.addRequiredID(LCSSAID); 925668cf77a77493ec9f2a9b33f08125e885c8e4cfDan Gohman AU.addPreserved<ScalarEvolution>(); 935668cf77a77493ec9f2a9b33f08125e885c8e4cfDan Gohman AU.addPreservedID(LoopSimplifyID); 945668cf77a77493ec9f2a9b33f08125e885c8e4cfDan Gohman AU.addPreservedID(LCSSAID); 955668cf77a77493ec9f2a9b33f08125e885c8e4cfDan Gohman AU.setPreservesCFG(); 965668cf77a77493ec9f2a9b33f08125e885c8e4cfDan Gohman } 973324e718bc9ac2ede08a14c325848b576849542bChris Lattner 9840bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner private: 99037d1c0c7e01cefeff7e538682c9a1e536e14030Andrew Trick virtual void releaseMemory() { 100037d1c0c7e01cefeff7e538682c9a1e536e14030Andrew Trick DeadInsts.clear(); 101037d1c0c7e01cefeff7e538682c9a1e536e14030Andrew Trick } 102037d1c0c7e01cefeff7e538682c9a1e536e14030Andrew Trick 103b12a754cce0c1d5542af605203a47820edba454dAndrew Trick bool isValidRewrite(Value *FromVal, Value *ToVal); 1045ee99979065d75605d150d7e567e4351024aae8fDevang Patel 1051a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick void HandleFloatingPointIV(Loop *L, PHINode *PH); 1061a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick void RewriteNonIntegerIVs(Loop *L); 1071a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 1084b4bb71bcdfd8c17cd4acb6116fc9a56c5fecd47Andrew Trick void SimplifyAndExtend(Loop *L, SCEVExpander &Rewriter, LPPassManager &LPM); 10906988bcf6a5c74e81cf7e76f06a686aa822ec00aAndrew Trick 1104b4bb71bcdfd8c17cd4acb6116fc9a56c5fecd47Andrew Trick void RewriteLoopExitValues(Loop *L, SCEVExpander &Rewriter); 1114b4bb71bcdfd8c17cd4acb6116fc9a56c5fecd47Andrew Trick 112fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick Value *LinearFunctionTestReplace(Loop *L, const SCEV *BackedgeTakenCount, 113fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick PHINode *IndVar, SCEVExpander &Rewriter); 11481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 1151a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick void SinkUnusedInvariants(Loop *L); 1163324e718bc9ac2ede08a14c325848b576849542bChris Lattner }; 1175e76140536ba66fadeced1cd892f79616f407e3cChris Lattner} 118394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner 119844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanchar IndVarSimplify::ID = 0; 1202ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_BEGIN(IndVarSimplify, "indvars", 12137da40875873d70b83dc08b2803052bec9b68886Andrew Trick "Induction Variable Simplification", false, false) 1222ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(DominatorTree) 1232ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(LoopInfo) 1242ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(ScalarEvolution) 1252ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(LoopSimplify) 1262ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(LCSSA) 1272ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_END(IndVarSimplify, "indvars", 12837da40875873d70b83dc08b2803052bec9b68886Andrew Trick "Induction Variable Simplification", false, false) 129844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 130394f0441e06dafca29f0752cf400990a5b8fe4b1Daniel DunbarPass *llvm::createIndVarSimplifyPass() { 1313324e718bc9ac2ede08a14c325848b576849542bChris Lattner return new IndVarSimplify(); 132394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner} 133394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner 134b12a754cce0c1d5542af605203a47820edba454dAndrew Trick/// isValidRewrite - Return true if the SCEV expansion generated by the 135b12a754cce0c1d5542af605203a47820edba454dAndrew Trick/// rewriter can replace the original value. SCEV guarantees that it 136b12a754cce0c1d5542af605203a47820edba454dAndrew Trick/// produces the same value, but the way it is produced may be illegal IR. 137b12a754cce0c1d5542af605203a47820edba454dAndrew Trick/// Ideally, this function will only be called for verification. 138b12a754cce0c1d5542af605203a47820edba454dAndrew Trickbool IndVarSimplify::isValidRewrite(Value *FromVal, Value *ToVal) { 139b12a754cce0c1d5542af605203a47820edba454dAndrew Trick // If an SCEV expression subsumed multiple pointers, its expansion could 140b12a754cce0c1d5542af605203a47820edba454dAndrew Trick // reassociate the GEP changing the base pointer. This is illegal because the 141b12a754cce0c1d5542af605203a47820edba454dAndrew Trick // final address produced by a GEP chain must be inbounds relative to its 142b12a754cce0c1d5542af605203a47820edba454dAndrew Trick // underlying object. Otherwise basic alias analysis, among other things, 143b12a754cce0c1d5542af605203a47820edba454dAndrew Trick // could fail in a dangerous way. Ultimately, SCEV will be improved to avoid 144b12a754cce0c1d5542af605203a47820edba454dAndrew Trick // producing an expression involving multiple pointers. Until then, we must 145b12a754cce0c1d5542af605203a47820edba454dAndrew Trick // bail out here. 146b12a754cce0c1d5542af605203a47820edba454dAndrew Trick // 147b12a754cce0c1d5542af605203a47820edba454dAndrew Trick // Retrieve the pointer operand of the GEP. Don't use GetUnderlyingObject 148b12a754cce0c1d5542af605203a47820edba454dAndrew Trick // because it understands lcssa phis while SCEV does not. 149b12a754cce0c1d5542af605203a47820edba454dAndrew Trick Value *FromPtr = FromVal; 150b12a754cce0c1d5542af605203a47820edba454dAndrew Trick Value *ToPtr = ToVal; 151b12a754cce0c1d5542af605203a47820edba454dAndrew Trick if (GEPOperator *GEP = dyn_cast<GEPOperator>(FromVal)) { 152b12a754cce0c1d5542af605203a47820edba454dAndrew Trick FromPtr = GEP->getPointerOperand(); 153b12a754cce0c1d5542af605203a47820edba454dAndrew Trick } 154b12a754cce0c1d5542af605203a47820edba454dAndrew Trick if (GEPOperator *GEP = dyn_cast<GEPOperator>(ToVal)) { 155b12a754cce0c1d5542af605203a47820edba454dAndrew Trick ToPtr = GEP->getPointerOperand(); 156b12a754cce0c1d5542af605203a47820edba454dAndrew Trick } 157b12a754cce0c1d5542af605203a47820edba454dAndrew Trick if (FromPtr != FromVal || ToPtr != ToVal) { 158b12a754cce0c1d5542af605203a47820edba454dAndrew Trick // Quickly check the common case 159b12a754cce0c1d5542af605203a47820edba454dAndrew Trick if (FromPtr == ToPtr) 160b12a754cce0c1d5542af605203a47820edba454dAndrew Trick return true; 161b12a754cce0c1d5542af605203a47820edba454dAndrew Trick 162b12a754cce0c1d5542af605203a47820edba454dAndrew Trick // SCEV may have rewritten an expression that produces the GEP's pointer 163b12a754cce0c1d5542af605203a47820edba454dAndrew Trick // operand. That's ok as long as the pointer operand has the same base 164b12a754cce0c1d5542af605203a47820edba454dAndrew Trick // pointer. Unlike GetUnderlyingObject(), getPointerBase() will find the 165b12a754cce0c1d5542af605203a47820edba454dAndrew Trick // base of a recurrence. This handles the case in which SCEV expansion 166b12a754cce0c1d5542af605203a47820edba454dAndrew Trick // converts a pointer type recurrence into a nonrecurrent pointer base 167b12a754cce0c1d5542af605203a47820edba454dAndrew Trick // indexed by an integer recurrence. 1681608769abeb1430dc34f31ffac0d9850f99ae36aNadav Rotem 1691608769abeb1430dc34f31ffac0d9850f99ae36aNadav Rotem // If the GEP base pointer is a vector of pointers, abort. 1701608769abeb1430dc34f31ffac0d9850f99ae36aNadav Rotem if (!FromPtr->getType()->isPointerTy() || !ToPtr->getType()->isPointerTy()) 1711608769abeb1430dc34f31ffac0d9850f99ae36aNadav Rotem return false; 1721608769abeb1430dc34f31ffac0d9850f99ae36aNadav Rotem 173b12a754cce0c1d5542af605203a47820edba454dAndrew Trick const SCEV *FromBase = SE->getPointerBase(SE->getSCEV(FromPtr)); 174b12a754cce0c1d5542af605203a47820edba454dAndrew Trick const SCEV *ToBase = SE->getPointerBase(SE->getSCEV(ToPtr)); 175b12a754cce0c1d5542af605203a47820edba454dAndrew Trick if (FromBase == ToBase) 176b12a754cce0c1d5542af605203a47820edba454dAndrew Trick return true; 177b12a754cce0c1d5542af605203a47820edba454dAndrew Trick 178b12a754cce0c1d5542af605203a47820edba454dAndrew Trick DEBUG(dbgs() << "INDVARS: GEP rewrite bail out " 179b12a754cce0c1d5542af605203a47820edba454dAndrew Trick << *FromBase << " != " << *ToBase << "\n"); 180b12a754cce0c1d5542af605203a47820edba454dAndrew Trick 181b12a754cce0c1d5542af605203a47820edba454dAndrew Trick return false; 182b12a754cce0c1d5542af605203a47820edba454dAndrew Trick } 183b12a754cce0c1d5542af605203a47820edba454dAndrew Trick return true; 184b12a754cce0c1d5542af605203a47820edba454dAndrew Trick} 185b12a754cce0c1d5542af605203a47820edba454dAndrew Trick 18686c98145b268a0d10e062792f98bc8eea6b639b4Andrew Trick/// Determine the insertion point for this user. By default, insert immediately 18786c98145b268a0d10e062792f98bc8eea6b639b4Andrew Trick/// before the user. SCEVExpander or LICM will hoist loop invariants out of the 18886c98145b268a0d10e062792f98bc8eea6b639b4Andrew Trick/// loop. For PHI nodes, there may be multiple uses, so compute the nearest 18986c98145b268a0d10e062792f98bc8eea6b639b4Andrew Trick/// common dominator for the incoming blocks. 19086c98145b268a0d10e062792f98bc8eea6b639b4Andrew Trickstatic Instruction *getInsertPointForUses(Instruction *User, Value *Def, 19186c98145b268a0d10e062792f98bc8eea6b639b4Andrew Trick DominatorTree *DT) { 19286c98145b268a0d10e062792f98bc8eea6b639b4Andrew Trick PHINode *PHI = dyn_cast<PHINode>(User); 19386c98145b268a0d10e062792f98bc8eea6b639b4Andrew Trick if (!PHI) 19486c98145b268a0d10e062792f98bc8eea6b639b4Andrew Trick return User; 19586c98145b268a0d10e062792f98bc8eea6b639b4Andrew Trick 19686c98145b268a0d10e062792f98bc8eea6b639b4Andrew Trick Instruction *InsertPt = 0; 19786c98145b268a0d10e062792f98bc8eea6b639b4Andrew Trick for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i) { 19886c98145b268a0d10e062792f98bc8eea6b639b4Andrew Trick if (PHI->getIncomingValue(i) != Def) 19986c98145b268a0d10e062792f98bc8eea6b639b4Andrew Trick continue; 20086c98145b268a0d10e062792f98bc8eea6b639b4Andrew Trick 20186c98145b268a0d10e062792f98bc8eea6b639b4Andrew Trick BasicBlock *InsertBB = PHI->getIncomingBlock(i); 20286c98145b268a0d10e062792f98bc8eea6b639b4Andrew Trick if (!InsertPt) { 20386c98145b268a0d10e062792f98bc8eea6b639b4Andrew Trick InsertPt = InsertBB->getTerminator(); 20486c98145b268a0d10e062792f98bc8eea6b639b4Andrew Trick continue; 20586c98145b268a0d10e062792f98bc8eea6b639b4Andrew Trick } 20686c98145b268a0d10e062792f98bc8eea6b639b4Andrew Trick InsertBB = DT->findNearestCommonDominator(InsertPt->getParent(), InsertBB); 20786c98145b268a0d10e062792f98bc8eea6b639b4Andrew Trick InsertPt = InsertBB->getTerminator(); 20886c98145b268a0d10e062792f98bc8eea6b639b4Andrew Trick } 20986c98145b268a0d10e062792f98bc8eea6b639b4Andrew Trick assert(InsertPt && "Missing phi operand"); 210626f52d43df67c29b156f524551327d741ef80bfJay Foad assert((!isa<Instruction>(Def) || 211626f52d43df67c29b156f524551327d741ef80bfJay Foad DT->dominates(cast<Instruction>(Def), InsertPt)) && 21286c98145b268a0d10e062792f98bc8eea6b639b4Andrew Trick "def does not dominate all uses"); 21386c98145b268a0d10e062792f98bc8eea6b639b4Andrew Trick return InsertPt; 21486c98145b268a0d10e062792f98bc8eea6b639b4Andrew Trick} 21586c98145b268a0d10e062792f98bc8eea6b639b4Andrew Trick 2161a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick//===----------------------------------------------------------------------===// 2171a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick// RewriteNonIntegerIVs and helpers. Prefer integer IVs. 2181a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick//===----------------------------------------------------------------------===// 2194dfdf242c1917e98f407818eb5b68ae0b4678f26Andrew Trick 2201a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick/// ConvertToSInt - Convert APF to an integer, if possible. 2211a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trickstatic bool ConvertToSInt(const APFloat &APF, int64_t &IntVal) { 2221a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick bool isExact = false; 2231a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // See if we can convert this to an int64_t 2241a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick uint64_t UIntVal; 2251a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (APF.convertToInteger(&UIntVal, 64, true, APFloat::rmTowardZero, 2261a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick &isExact) != APFloat::opOK || !isExact) 2274dfdf242c1917e98f407818eb5b68ae0b4678f26Andrew Trick return false; 2281a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick IntVal = UIntVal; 2294dfdf242c1917e98f407818eb5b68ae0b4678f26Andrew Trick return true; 2304dfdf242c1917e98f407818eb5b68ae0b4678f26Andrew Trick} 2314dfdf242c1917e98f407818eb5b68ae0b4678f26Andrew Trick 2321a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick/// HandleFloatingPointIV - If the loop has floating induction variable 2331a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick/// then insert corresponding integer induction variable if possible. 2341a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick/// For example, 2351a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick/// for(double i = 0; i < 10000; ++i) 2361a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick/// bar(i) 2371a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick/// is converted into 2381a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick/// for(int i = 0; i < 10000; ++i) 2391a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick/// bar((double)i); 24003d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick/// 2411a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trickvoid IndVarSimplify::HandleFloatingPointIV(Loop *L, PHINode *PN) { 2421a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick unsigned IncomingEdge = L->contains(PN->getIncomingBlock(0)); 2431a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick unsigned BackEdge = IncomingEdge^1; 24403d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick 2451a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // Check incoming value. 2461a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick ConstantFP *InitValueVal = 2471a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick dyn_cast<ConstantFP>(PN->getIncomingValue(IncomingEdge)); 24803d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick 2491a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick int64_t InitValue; 2501a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (!InitValueVal || !ConvertToSInt(InitValueVal->getValueAPF(), InitValue)) 2511a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick return; 25203d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick 2531a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // Check IV increment. Reject this PN if increment operation is not 2541a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // an add or increment value can not be represented by an integer. 2551a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick BinaryOperator *Incr = 2561a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick dyn_cast<BinaryOperator>(PN->getIncomingValue(BackEdge)); 2571a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (Incr == 0 || Incr->getOpcode() != Instruction::FAdd) return; 25803d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick 2591a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // If this is not an add of the PHI with a constantfp, or if the constant fp 2601a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // is not an integer, bail out. 2611a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick ConstantFP *IncValueVal = dyn_cast<ConstantFP>(Incr->getOperand(1)); 2621a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick int64_t IncValue; 2631a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (IncValueVal == 0 || Incr->getOperand(0) != PN || 2641a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick !ConvertToSInt(IncValueVal->getValueAPF(), IncValue)) 2651a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick return; 26603d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick 2671a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // Check Incr uses. One user is PN and the other user is an exit condition 2681a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // used by the conditional terminator. 2691a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick Value::use_iterator IncrUse = Incr->use_begin(); 2701a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick Instruction *U1 = cast<Instruction>(*IncrUse++); 2711a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (IncrUse == Incr->use_end()) return; 2721a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick Instruction *U2 = cast<Instruction>(*IncrUse++); 2731a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (IncrUse != Incr->use_end()) return; 274ca9b7037e28759c200fe5ca98190cabd121a1bbaDan Gohman 2751a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // Find exit condition, which is an fcmp. If it doesn't exist, or if it isn't 2761a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // only used by a branch, we can't transform it. 2771a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick FCmpInst *Compare = dyn_cast<FCmpInst>(U1); 2781a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (!Compare) 2791a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick Compare = dyn_cast<FCmpInst>(U2); 2801a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (Compare == 0 || !Compare->hasOneUse() || 2811a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick !isa<BranchInst>(Compare->use_back())) 2821a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick return; 283c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman 2841a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick BranchInst *TheBr = cast<BranchInst>(Compare->use_back()); 28559fdaeeae8f183e18bb6ad5c382ca23e28e6aaf6Chris Lattner 2861a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // We need to verify that the branch actually controls the iteration count 2871a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // of the loop. If not, the new IV can overflow and no one will notice. 2881a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // The branch block must be in the loop and one of the successors must be out 2891a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // of the loop. 2901a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick assert(TheBr->isConditional() && "Can't use fcmp if not conditional"); 2911a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (!L->contains(TheBr->getParent()) || 2921a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick (L->contains(TheBr->getSuccessor(0)) && 2931a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick L->contains(TheBr->getSuccessor(1)))) 2941a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick return; 29540bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner 29640bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner 2971a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // If it isn't a comparison with an integer-as-fp (the exit value), we can't 2981a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // transform it. 2991a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick ConstantFP *ExitValueVal = dyn_cast<ConstantFP>(Compare->getOperand(1)); 3001a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick int64_t ExitValue; 3011a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (ExitValueVal == 0 || 3021a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick !ConvertToSInt(ExitValueVal->getValueAPF(), ExitValue)) 3031a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick return; 304c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman 3051a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // Find new predicate for integer comparison. 3061a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick CmpInst::Predicate NewPred = CmpInst::BAD_ICMP_PREDICATE; 3071a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick switch (Compare->getPredicate()) { 3081a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick default: return; // Unknown comparison. 3091a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick case CmpInst::FCMP_OEQ: 3101a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick case CmpInst::FCMP_UEQ: NewPred = CmpInst::ICMP_EQ; break; 3111a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick case CmpInst::FCMP_ONE: 3121a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick case CmpInst::FCMP_UNE: NewPred = CmpInst::ICMP_NE; break; 3131a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick case CmpInst::FCMP_OGT: 3141a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick case CmpInst::FCMP_UGT: NewPred = CmpInst::ICMP_SGT; break; 3151a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick case CmpInst::FCMP_OGE: 3161a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick case CmpInst::FCMP_UGE: NewPred = CmpInst::ICMP_SGE; break; 3171a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick case CmpInst::FCMP_OLT: 3181a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick case CmpInst::FCMP_ULT: NewPred = CmpInst::ICMP_SLT; break; 3191a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick case CmpInst::FCMP_OLE: 3201a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick case CmpInst::FCMP_ULE: NewPred = CmpInst::ICMP_SLE; break; 3211a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick } 32281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 3231a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // We convert the floating point induction variable to a signed i32 value if 3241a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // we can. This is only safe if the comparison will not overflow in a way 3251a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // that won't be trapped by the integer equivalent operations. Check for this 3261a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // now. 3271a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // TODO: We could use i64 if it is native and the range requires it. 3283324e718bc9ac2ede08a14c325848b576849542bChris Lattner 3291a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // The start/stride/exit values must all fit in signed i32. 3301a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (!isInt<32>(InitValue) || !isInt<32>(IncValue) || !isInt<32>(ExitValue)) 3311a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick return; 33281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 3331a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // If not actually striding (add x, 0.0), avoid touching the code. 3341a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (IncValue == 0) 3351a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick return; 3361a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 3371a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // Positive and negative strides have different safety conditions. 3381a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (IncValue > 0) { 3391a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // If we have a positive stride, we require the init to be less than the 34094f2c23d24b3ca682ea192f1d9a4e2c2e0f4eeb3Andrew Trick // exit value. 34194f2c23d24b3ca682ea192f1d9a4e2c2e0f4eeb3Andrew Trick if (InitValue >= ExitValue) 3421a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick return; 3431a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 3441a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick uint32_t Range = uint32_t(ExitValue-InitValue); 34594f2c23d24b3ca682ea192f1d9a4e2c2e0f4eeb3Andrew Trick // Check for infinite loop, either: 34694f2c23d24b3ca682ea192f1d9a4e2c2e0f4eeb3Andrew Trick // while (i <= Exit) or until (i > Exit) 34794f2c23d24b3ca682ea192f1d9a4e2c2e0f4eeb3Andrew Trick if (NewPred == CmpInst::ICMP_SLE || NewPred == CmpInst::ICMP_SGT) { 3481a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (++Range == 0) return; // Range overflows. 3491a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick } 3501a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 3511a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick unsigned Leftover = Range % uint32_t(IncValue); 3521a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 3531a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // If this is an equality comparison, we require that the strided value 3541a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // exactly land on the exit value, otherwise the IV condition will wrap 3551a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // around and do things the fp IV wouldn't. 3561a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if ((NewPred == CmpInst::ICMP_EQ || NewPred == CmpInst::ICMP_NE) && 3571a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick Leftover != 0) 3581a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick return; 3591a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 3601a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // If the stride would wrap around the i32 before exiting, we can't 3611a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // transform the IV. 3621a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (Leftover != 0 && int32_t(ExitValue+IncValue) < ExitValue) 3631a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick return; 3641a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 3651a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick } else { 3661a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // If we have a negative stride, we require the init to be greater than the 36794f2c23d24b3ca682ea192f1d9a4e2c2e0f4eeb3Andrew Trick // exit value. 36894f2c23d24b3ca682ea192f1d9a4e2c2e0f4eeb3Andrew Trick if (InitValue <= ExitValue) 3691a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick return; 3701a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 3711a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick uint32_t Range = uint32_t(InitValue-ExitValue); 37294f2c23d24b3ca682ea192f1d9a4e2c2e0f4eeb3Andrew Trick // Check for infinite loop, either: 37394f2c23d24b3ca682ea192f1d9a4e2c2e0f4eeb3Andrew Trick // while (i >= Exit) or until (i < Exit) 37494f2c23d24b3ca682ea192f1d9a4e2c2e0f4eeb3Andrew Trick if (NewPred == CmpInst::ICMP_SGE || NewPred == CmpInst::ICMP_SLT) { 3751a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (++Range == 0) return; // Range overflows. 3761a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick } 3771a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 3781a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick unsigned Leftover = Range % uint32_t(-IncValue); 3791a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 3801a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // If this is an equality comparison, we require that the strided value 3811a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // exactly land on the exit value, otherwise the IV condition will wrap 3821a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // around and do things the fp IV wouldn't. 3831a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if ((NewPred == CmpInst::ICMP_EQ || NewPred == CmpInst::ICMP_NE) && 3841a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick Leftover != 0) 3851a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick return; 3861a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 3871a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // If the stride would wrap around the i32 before exiting, we can't 3881a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // transform the IV. 3891a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (Leftover != 0 && int32_t(ExitValue+IncValue) > ExitValue) 3901a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick return; 3911a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick } 3921a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 393db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner IntegerType *Int32Ty = Type::getInt32Ty(PN->getContext()); 3941a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 3951a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // Insert new integer induction variable. 3961a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick PHINode *NewPHI = PHINode::Create(Int32Ty, 2, PN->getName()+".int", PN); 3971a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick NewPHI->addIncoming(ConstantInt::get(Int32Ty, InitValue), 3981a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick PN->getIncomingBlock(IncomingEdge)); 3991a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 4001a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick Value *NewAdd = 4011a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick BinaryOperator::CreateAdd(NewPHI, ConstantInt::get(Int32Ty, IncValue), 4021a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick Incr->getName()+".int", Incr); 4031a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick NewPHI->addIncoming(NewAdd, PN->getIncomingBlock(BackEdge)); 4041a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 4051a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick ICmpInst *NewCompare = new ICmpInst(TheBr, NewPred, NewAdd, 4061a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick ConstantInt::get(Int32Ty, ExitValue), 4071a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick Compare->getName()); 4081a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 4091a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // In the following deletions, PN may become dead and may be deleted. 4101a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // Use a WeakVH to observe whether this happens. 4111a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick WeakVH WeakPH = PN; 4121a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 4131a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // Delete the old floating point exit comparison. The branch starts using the 4141a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // new comparison. 4151a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick NewCompare->takeName(Compare); 4161a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick Compare->replaceAllUsesWith(NewCompare); 4178e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer RecursivelyDeleteTriviallyDeadInstructions(Compare, TLI); 4181a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 4191a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // Delete the old floating point increment. 4201a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick Incr->replaceAllUsesWith(UndefValue::get(Incr->getType())); 4218e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer RecursivelyDeleteTriviallyDeadInstructions(Incr, TLI); 4221a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 4231a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // If the FP induction variable still has uses, this is because something else 4241a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // in the loop uses its value. In order to canonicalize the induction 4251a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // variable, we chose to eliminate the IV and rewrite it in terms of an 4261a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // int->fp cast. 4271a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // 4281a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // We give preference to sitofp over uitofp because it is faster on most 4291a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // platforms. 4301a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (WeakPH) { 4311a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick Value *Conv = new SIToFPInst(NewPHI, PN->getType(), "indvar.conv", 432b05fdd6babada25da2ec3ba54bb462c2ecfc42a8Bill Wendling PN->getParent()->getFirstInsertionPt()); 4331a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick PN->replaceAllUsesWith(Conv); 4348e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer RecursivelyDeleteTriviallyDeadInstructions(PN, TLI); 4351a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick } 4364b4bb71bcdfd8c17cd4acb6116fc9a56c5fecd47Andrew Trick Changed = true; 4371a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick} 4381a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 4391a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trickvoid IndVarSimplify::RewriteNonIntegerIVs(Loop *L) { 4401a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // First step. Check to see if there are any floating-point recurrences. 4411a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // If there are, change them into integer recurrences, permitting analysis by 4421a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // the SCEV routines. 4431a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // 4441a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick BasicBlock *Header = L->getHeader(); 4451a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 4461a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick SmallVector<WeakVH, 8> PHIs; 4471a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick for (BasicBlock::iterator I = Header->begin(); 4481a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick PHINode *PN = dyn_cast<PHINode>(I); ++I) 4491a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick PHIs.push_back(PN); 4501a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 4511a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick for (unsigned i = 0, e = PHIs.size(); i != e; ++i) 4521a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (PHINode *PN = dyn_cast_or_null<PHINode>(&*PHIs[i])) 4531a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick HandleFloatingPointIV(L, PN); 4541a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 4551a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // If the loop previously had floating-point IV, ScalarEvolution 4561a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // may not have been able to compute a trip count. Now that we've done some 4571a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // re-writing, the trip count may be computable. 4581a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (Changed) 4591a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick SE->forgetLoop(L); 4601a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick} 4611a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 4621a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick//===----------------------------------------------------------------------===// 4631a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick// RewriteLoopExitValues - Optimize IV users outside the loop. 4641a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick// As a side effect, reduces the amount of IV processing within the loop. 4651a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick//===----------------------------------------------------------------------===// 4661a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 4671a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick/// RewriteLoopExitValues - Check to see if this loop has a computable 4681a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick/// loop-invariant execution count. If so, this means that we can compute the 4691a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick/// final value of any expressions that are recurrent in the loop, and 4701a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick/// substitute the exit values from the loop into any instructions outside of 4711a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick/// the loop that use the final values of the current expressions. 4721a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick/// 4731a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick/// This is mostly redundant with the regular IndVarSimplify activities that 4741a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick/// happen later, except that it's more powerful in some cases, because it's 4751a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick/// able to brute-force evaluate arbitrary instructions as long as they have 4761a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick/// constant operands at the beginning of the loop. 4771a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trickvoid IndVarSimplify::RewriteLoopExitValues(Loop *L, SCEVExpander &Rewriter) { 4781a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // Verify the input to the pass in already in LCSSA form. 4791a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick assert(L->isLCSSAForm(*DT)); 4801a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 4811a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick SmallVector<BasicBlock*, 8> ExitBlocks; 4829f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner L->getUniqueExitBlocks(ExitBlocks); 4839f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner 4849f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // Find all values that are computed inside the loop, but used outside of it. 4859f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // Because of LCSSA, these values will only occur in LCSSA PHI Nodes. Scan 4869f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // the exit blocks of the loop to find them. 4879f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) { 4889f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner BasicBlock *ExitBB = ExitBlocks[i]; 489cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 4909f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // If there are no PHI nodes in this exit block, then no values defined 4919f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // inside the loop are used on this path, skip it. 4929f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner PHINode *PN = dyn_cast<PHINode>(ExitBB->begin()); 4939f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner if (!PN) continue; 494cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 4959f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner unsigned NumPreds = PN->getNumIncomingValues(); 496cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 4979f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // Iterate over all of the PHI nodes. 4989f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner BasicBlock::iterator BBI = ExitBB->begin(); 4999f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner while ((PN = dyn_cast<PHINode>(BBI++))) { 5003790fb0c036acaa4db50aff83dd8b3bf51f8af6aTorok Edwin if (PN->use_empty()) 5013790fb0c036acaa4db50aff83dd8b3bf51f8af6aTorok Edwin continue; // dead use, don't replace it 502814f2b2d1927a5397c0e923588527277b9f67d6bDan Gohman 503814f2b2d1927a5397c0e923588527277b9f67d6bDan Gohman // SCEV only supports integer expressions for now. 504814f2b2d1927a5397c0e923588527277b9f67d6bDan Gohman if (!PN->getType()->isIntegerTy() && !PN->getType()->isPointerTy()) 505814f2b2d1927a5397c0e923588527277b9f67d6bDan Gohman continue; 506814f2b2d1927a5397c0e923588527277b9f67d6bDan Gohman 50745a2d7d44ae697e28df383d31455145fb754ac58Dale Johannesen // It's necessary to tell ScalarEvolution about this explicitly so that 50845a2d7d44ae697e28df383d31455145fb754ac58Dale Johannesen // it can walk the def-use list and forget all SCEVs, as it may not be 50945a2d7d44ae697e28df383d31455145fb754ac58Dale Johannesen // watching the PHI itself. Once the new exit value is in place, there 51045a2d7d44ae697e28df383d31455145fb754ac58Dale Johannesen // may not be a def-use connection between the loop and every instruction 51145a2d7d44ae697e28df383d31455145fb754ac58Dale Johannesen // which got a SCEVAddRecExpr for that loop. 51245a2d7d44ae697e28df383d31455145fb754ac58Dale Johannesen SE->forgetValue(PN); 51345a2d7d44ae697e28df383d31455145fb754ac58Dale Johannesen 5149f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // Iterate over all of the values in all the PHI nodes. 5159f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner for (unsigned i = 0; i != NumPreds; ++i) { 5169f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // If the value being merged in is not integer or is not defined 5179f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // in the loop, skip it. 5189f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner Value *InVal = PN->getIncomingValue(i); 519814f2b2d1927a5397c0e923588527277b9f67d6bDan Gohman if (!isa<Instruction>(InVal)) 5209f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner continue; 5219f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner 5229f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // If this pred is for a subloop, not L itself, skip it. 523cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman if (LI->getLoopFor(PN->getIncomingBlock(i)) != L) 5249f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner continue; // The Block is in a subloop, skip it. 5259f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner 5269f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // Check that InVal is defined in the loop. 5279f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner Instruction *Inst = cast<Instruction>(InVal); 52892329c7fbe572892c17aa2d2542a10e3ea16132fDan Gohman if (!L->contains(Inst)) 5299f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner continue; 530cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 5319f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // Okay, this instruction has a user outside of the current loop 5329f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // and varies predictably *inside* the loop. Evaluate the value it 5339f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner // contains when the loop exits, if possible. 5340bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *ExitValue = SE->getSCEVAtScope(Inst, L->getParentLoop()); 53517ead4ff4baceb2c5503f233d0288d363ae44165Dan Gohman if (!SE->isLoopInvariant(ExitValue, L)) 5369f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner continue; 5379f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner 538667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman Value *ExitVal = Rewriter.expandCodeFor(ExitValue, PN->getType(), Inst); 539cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 540f67ef318aa29e7cc0c7de76349881959936d9eeeDavid Greene DEBUG(dbgs() << "INDVARS: RLEV: AfterLoopVal = " << *ExitVal << '\n' 541bdff548e4dd577a72094d57b282de4e765643b96Chris Lattner << " LoopVal = " << *Inst << "\n"); 5429caed5440d59dac4b388152fe8b993dc0491e5e9Chris Lattner 543b12a754cce0c1d5542af605203a47820edba454dAndrew Trick if (!isValidRewrite(Inst, ExitVal)) { 544b12a754cce0c1d5542af605203a47820edba454dAndrew Trick DeadInsts.push_back(ExitVal); 545b12a754cce0c1d5542af605203a47820edba454dAndrew Trick continue; 546b12a754cce0c1d5542af605203a47820edba454dAndrew Trick } 547b12a754cce0c1d5542af605203a47820edba454dAndrew Trick Changed = true; 548b12a754cce0c1d5542af605203a47820edba454dAndrew Trick ++NumReplaced; 549b12a754cce0c1d5542af605203a47820edba454dAndrew Trick 5509f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner PN->setIncomingValue(i, ExitVal); 551cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 5527182126b0f3100cfddfbe6939be1a7eaeaf9fd57Benjamin Kramer // If this instruction is dead now, delete it. Don't do it now to avoid 5537182126b0f3100cfddfbe6939be1a7eaeaf9fd57Benjamin Kramer // invalidating iterators. 5547182126b0f3100cfddfbe6939be1a7eaeaf9fd57Benjamin Kramer if (isInstructionTriviallyDead(Inst, TLI)) 5557182126b0f3100cfddfbe6939be1a7eaeaf9fd57Benjamin Kramer DeadInsts.push_back(Inst); 556cafb81337bdf2574049533f5b8a6bc1ed92f1f3eDan Gohman 55765d1e2b6e74fcd370093cbe518ebc15cbc445ad4Dan Gohman if (NumPreds == 1) { 55865d1e2b6e74fcd370093cbe518ebc15cbc445ad4Dan Gohman // Completely replace a single-pred PHI. This is safe, because the 55965d1e2b6e74fcd370093cbe518ebc15cbc445ad4Dan Gohman // NewVal won't be variant in the loop, so we don't need an LCSSA phi 56065d1e2b6e74fcd370093cbe518ebc15cbc445ad4Dan Gohman // node anymore. 5619f3d73886612fd06812fb63cf8e6fa10db9b17e7Chris Lattner PN->replaceAllUsesWith(ExitVal); 5627182126b0f3100cfddfbe6939be1a7eaeaf9fd57Benjamin Kramer PN->eraseFromParent(); 563c9838f25d53d3dd7d38949ef6c28f2505a110f45Chris Lattner } 5644bd09d70cceb3851f7eb1c2f98338b3071d405f3Chris Lattner } 56565d1e2b6e74fcd370093cbe518ebc15cbc445ad4Dan Gohman if (NumPreds != 1) { 566667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman // Clone the PHI and delete the original one. This lets IVUsers and 567667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman // any other maps purge the original user from their records. 56850b6e33584f4e4cf75c7795b1f1a90731861c825Devang Patel PHINode *NewPN = cast<PHINode>(PN->clone()); 569667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman NewPN->takeName(PN); 570667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman NewPN->insertBefore(PN); 571667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman PN->replaceAllUsesWith(NewPN); 572667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman PN->eraseFromParent(); 573667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman } 574c9838f25d53d3dd7d38949ef6c28f2505a110f45Chris Lattner } 575c9838f25d53d3dd7d38949ef6c28f2505a110f45Chris Lattner } 576472fdf7090bb00af3a3f9dcbe22263120a527533Dan Gohman 577472fdf7090bb00af3a3f9dcbe22263120a527533Dan Gohman // The insertion point instruction may have been deleted; clear it out 578472fdf7090bb00af3a3f9dcbe22263120a527533Dan Gohman // so that the rewriter doesn't trip over it later. 579472fdf7090bb00af3a3f9dcbe22263120a527533Dan Gohman Rewriter.clearInsertPoint(); 58040bf8b48cdb9961898dba1bc67320be1e49e3da1Chris Lattner} 58115cad759fe2048ac5eb137c6bb0ab7287538677eChris Lattner 5821a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick//===----------------------------------------------------------------------===// 5831a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick// IV Widening - Extend the width of an IV to cover its widest uses. 5841a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick//===----------------------------------------------------------------------===// 5851a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 5861a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Tricknamespace { 5871a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // Collect information about induction variables that are used by sign/zero 5881a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // extend operations. This information is recorded by CollectExtend and 5891a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // provides the input to WidenIV. 5901a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick struct WideIVInfo { 591513b1f47c1ddef0638bd63399bf64965e592c2bfAndrew Trick PHINode *NarrowIV; 592db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner Type *WidestNativeType; // Widest integer type created [sz]ext 5934b4bb71bcdfd8c17cd4acb6116fc9a56c5fecd47Andrew Trick bool IsSigned; // Was an sext user seen before a zext? 5941a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 595513b1f47c1ddef0638bd63399bf64965e592c2bfAndrew Trick WideIVInfo() : NarrowIV(0), WidestNativeType(0), IsSigned(false) {} 5961a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick }; 5974b4bb71bcdfd8c17cd4acb6116fc9a56c5fecd47Andrew Trick 5984b4bb71bcdfd8c17cd4acb6116fc9a56c5fecd47Andrew Trick class WideIVVisitor : public IVVisitor { 5994b4bb71bcdfd8c17cd4acb6116fc9a56c5fecd47Andrew Trick ScalarEvolution *SE; 6003574eca1b02600bac4e625297f4ecf745f4c4f32Micah Villmow const DataLayout *TD; 6014b4bb71bcdfd8c17cd4acb6116fc9a56c5fecd47Andrew Trick 6024b4bb71bcdfd8c17cd4acb6116fc9a56c5fecd47Andrew Trick public: 6034b4bb71bcdfd8c17cd4acb6116fc9a56c5fecd47Andrew Trick WideIVInfo WI; 6044b4bb71bcdfd8c17cd4acb6116fc9a56c5fecd47Andrew Trick 605513b1f47c1ddef0638bd63399bf64965e592c2bfAndrew Trick WideIVVisitor(PHINode *NarrowIV, ScalarEvolution *SCEV, 6063574eca1b02600bac4e625297f4ecf745f4c4f32Micah Villmow const DataLayout *TData) : 607513b1f47c1ddef0638bd63399bf64965e592c2bfAndrew Trick SE(SCEV), TD(TData) { WI.NarrowIV = NarrowIV; } 6084b4bb71bcdfd8c17cd4acb6116fc9a56c5fecd47Andrew Trick 6094b4bb71bcdfd8c17cd4acb6116fc9a56c5fecd47Andrew Trick // Implement the interface used by simplifyUsersOfIV. 6104b4bb71bcdfd8c17cd4acb6116fc9a56c5fecd47Andrew Trick virtual void visitCast(CastInst *Cast); 6114b4bb71bcdfd8c17cd4acb6116fc9a56c5fecd47Andrew Trick }; 6121a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick} 6131a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 6144b4bb71bcdfd8c17cd4acb6116fc9a56c5fecd47Andrew Trick/// visitCast - Update information about the induction variable that is 6151a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick/// extended by this sign or zero extend operation. This is used to determine 6161a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick/// the final width of the IV before actually widening it. 6174b4bb71bcdfd8c17cd4acb6116fc9a56c5fecd47Andrew Trickvoid WideIVVisitor::visitCast(CastInst *Cast) { 6184b4bb71bcdfd8c17cd4acb6116fc9a56c5fecd47Andrew Trick bool IsSigned = Cast->getOpcode() == Instruction::SExt; 6194b4bb71bcdfd8c17cd4acb6116fc9a56c5fecd47Andrew Trick if (!IsSigned && Cast->getOpcode() != Instruction::ZExt) 6204b4bb71bcdfd8c17cd4acb6116fc9a56c5fecd47Andrew Trick return; 6214b4bb71bcdfd8c17cd4acb6116fc9a56c5fecd47Andrew Trick 622db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner Type *Ty = Cast->getType(); 6231a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick uint64_t Width = SE->getTypeSizeInBits(Ty); 6241a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (TD && !TD->isLegalInteger(Width)) 6251a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick return; 6261a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 6271a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (!WI.WidestNativeType) { 6281a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick WI.WidestNativeType = SE->getEffectiveSCEVType(Ty); 6291a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick WI.IsSigned = IsSigned; 6301a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick return; 6311a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick } 6321a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 6331a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // We extend the IV to satisfy the sign of its first user, arbitrarily. 6341a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (WI.IsSigned != IsSigned) 6351a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick return; 6361a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 6371a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (Width > SE->getTypeSizeInBits(WI.WidestNativeType)) 6381a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick WI.WidestNativeType = SE->getEffectiveSCEVType(Ty); 6391a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick} 6401a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 6411a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Tricknamespace { 64213bcf2e68a88cb87378c9773effa5b79b3091d75Andrew Trick 64313bcf2e68a88cb87378c9773effa5b79b3091d75Andrew Trick/// NarrowIVDefUse - Record a link in the Narrow IV def-use chain along with the 64413bcf2e68a88cb87378c9773effa5b79b3091d75Andrew Trick/// WideIV that computes the same value as the Narrow IV def. This avoids 64513bcf2e68a88cb87378c9773effa5b79b3091d75Andrew Trick/// caching Use* pointers. 64613bcf2e68a88cb87378c9773effa5b79b3091d75Andrew Trickstruct NarrowIVDefUse { 64713bcf2e68a88cb87378c9773effa5b79b3091d75Andrew Trick Instruction *NarrowDef; 64813bcf2e68a88cb87378c9773effa5b79b3091d75Andrew Trick Instruction *NarrowUse; 64913bcf2e68a88cb87378c9773effa5b79b3091d75Andrew Trick Instruction *WideDef; 65013bcf2e68a88cb87378c9773effa5b79b3091d75Andrew Trick 65113bcf2e68a88cb87378c9773effa5b79b3091d75Andrew Trick NarrowIVDefUse(): NarrowDef(0), NarrowUse(0), WideDef(0) {} 65213bcf2e68a88cb87378c9773effa5b79b3091d75Andrew Trick 65313bcf2e68a88cb87378c9773effa5b79b3091d75Andrew Trick NarrowIVDefUse(Instruction *ND, Instruction *NU, Instruction *WD): 65413bcf2e68a88cb87378c9773effa5b79b3091d75Andrew Trick NarrowDef(ND), NarrowUse(NU), WideDef(WD) {} 65513bcf2e68a88cb87378c9773effa5b79b3091d75Andrew Trick}; 65613bcf2e68a88cb87378c9773effa5b79b3091d75Andrew Trick 6571a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick/// WidenIV - The goal of this transform is to remove sign and zero extends 6581a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick/// without creating any new induction variables. To do this, it creates a new 6591a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick/// phi of the wider type and redirects all users, either removing extends or 6601a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick/// inserting truncs whenever we stop propagating the type. 6611a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick/// 6621a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trickclass WidenIV { 6631a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // Parameters 6641a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick PHINode *OrigPhi; 665db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner Type *WideType; 6661a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick bool IsSigned; 6671a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 6681a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // Context 6691a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick LoopInfo *LI; 6701a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick Loop *L; 6711a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick ScalarEvolution *SE; 6721a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick DominatorTree *DT; 6731a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 6741a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // Result 6751a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick PHINode *WidePhi; 6761a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick Instruction *WideInc; 6771a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick const SCEV *WideIncExpr; 6782fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick SmallVectorImpl<WeakVH> &DeadInsts; 679f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 6802fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick SmallPtrSet<Instruction*,16> Widened; 68113bcf2e68a88cb87378c9773effa5b79b3091d75Andrew Trick SmallVector<NarrowIVDefUse, 8> NarrowIVUsers; 682f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 683f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trickpublic: 684513b1f47c1ddef0638bd63399bf64965e592c2bfAndrew Trick WidenIV(const WideIVInfo &WI, LoopInfo *LInfo, 6852fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick ScalarEvolution *SEv, DominatorTree *DTree, 686fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick SmallVectorImpl<WeakVH> &DI) : 687513b1f47c1ddef0638bd63399bf64965e592c2bfAndrew Trick OrigPhi(WI.NarrowIV), 6882fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick WideType(WI.WidestNativeType), 6892fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick IsSigned(WI.IsSigned), 690f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick LI(LInfo), 691f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick L(LI->getLoopFor(OrigPhi->getParent())), 692f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick SE(SEv), 693fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick DT(DTree), 694f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick WidePhi(0), 695f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick WideInc(0), 6962fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick WideIncExpr(0), 6972fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick DeadInsts(DI) { 698f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick assert(L->getHeader() == OrigPhi->getParent() && "Phi must be an IV"); 699f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick } 700f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 7012fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick PHINode *CreateWideIV(SCEVExpander &Rewriter); 702f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 703f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trickprotected: 704909ef7db3dad5247648e1e89a34f1382815442b8Andrew Trick Value *getExtend(Value *NarrowOper, Type *WideType, bool IsSigned, 705909ef7db3dad5247648e1e89a34f1382815442b8Andrew Trick Instruction *Use); 706909ef7db3dad5247648e1e89a34f1382815442b8Andrew Trick 70713bcf2e68a88cb87378c9773effa5b79b3091d75Andrew Trick Instruction *CloneIVUser(NarrowIVDefUse DU); 708f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 709e0dc2faaa0105c9d1cc56f0b70e93d532a6f8c4cAndrew Trick const SCEVAddRecExpr *GetWideRecurrence(Instruction *NarrowUse); 710e0dc2faaa0105c9d1cc56f0b70e93d532a6f8c4cAndrew Trick 71120151da8c38287b9fa181e9fef93f70bc2cd9fd2Andrew Trick const SCEVAddRecExpr* GetExtendedOperandRecurrence(NarrowIVDefUse DU); 71220151da8c38287b9fa181e9fef93f70bc2cd9fd2Andrew Trick 713b5c26ef9da16052597d59a412eaae32098aa1be0Andrew Trick Instruction *WidenIVUse(NarrowIVDefUse DU, SCEVExpander &Rewriter); 7144b02915386046fa882a95553a7457ae7d05e9f27Andrew Trick 7154b02915386046fa882a95553a7457ae7d05e9f27Andrew Trick void pushNarrowIVUsers(Instruction *NarrowDef, Instruction *WideDef); 716f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick}; 717f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick} // anonymous namespace 718f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 719909ef7db3dad5247648e1e89a34f1382815442b8Andrew Trick/// isLoopInvariant - Perform a quick domtree based check for loop invariance 720909ef7db3dad5247648e1e89a34f1382815442b8Andrew Trick/// assuming that V is used within the loop. LoopInfo::isLoopInvariant() seems 721909ef7db3dad5247648e1e89a34f1382815442b8Andrew Trick/// gratuitous for this purpose. 722909ef7db3dad5247648e1e89a34f1382815442b8Andrew Trickstatic bool isLoopInvariant(Value *V, const Loop *L, const DominatorTree *DT) { 723909ef7db3dad5247648e1e89a34f1382815442b8Andrew Trick Instruction *Inst = dyn_cast<Instruction>(V); 724909ef7db3dad5247648e1e89a34f1382815442b8Andrew Trick if (!Inst) 725909ef7db3dad5247648e1e89a34f1382815442b8Andrew Trick return true; 726909ef7db3dad5247648e1e89a34f1382815442b8Andrew Trick 727909ef7db3dad5247648e1e89a34f1382815442b8Andrew Trick return DT->properlyDominates(Inst->getParent(), L->getHeader()); 728909ef7db3dad5247648e1e89a34f1382815442b8Andrew Trick} 729909ef7db3dad5247648e1e89a34f1382815442b8Andrew Trick 730909ef7db3dad5247648e1e89a34f1382815442b8Andrew TrickValue *WidenIV::getExtend(Value *NarrowOper, Type *WideType, bool IsSigned, 731909ef7db3dad5247648e1e89a34f1382815442b8Andrew Trick Instruction *Use) { 732909ef7db3dad5247648e1e89a34f1382815442b8Andrew Trick // Set the debug location and conservative insertion point. 733909ef7db3dad5247648e1e89a34f1382815442b8Andrew Trick IRBuilder<> Builder(Use); 734909ef7db3dad5247648e1e89a34f1382815442b8Andrew Trick // Hoist the insertion point into loop preheaders as far as possible. 735909ef7db3dad5247648e1e89a34f1382815442b8Andrew Trick for (const Loop *L = LI->getLoopFor(Use->getParent()); 736909ef7db3dad5247648e1e89a34f1382815442b8Andrew Trick L && L->getLoopPreheader() && isLoopInvariant(NarrowOper, L, DT); 737909ef7db3dad5247648e1e89a34f1382815442b8Andrew Trick L = L->getParentLoop()) 738909ef7db3dad5247648e1e89a34f1382815442b8Andrew Trick Builder.SetInsertPoint(L->getLoopPreheader()->getTerminator()); 739909ef7db3dad5247648e1e89a34f1382815442b8Andrew Trick 74003d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick return IsSigned ? Builder.CreateSExt(NarrowOper, WideType) : 74103d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick Builder.CreateZExt(NarrowOper, WideType); 742f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick} 743931e345e76e75391d2a7c96530e305f802b5429dDan Gohman 744f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick/// CloneIVUser - Instantiate a wide operation to replace a narrow 745f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick/// operation. This only needs to handle operations that can evaluation to 746f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick/// SCEVAddRec. It can safely return 0 for any operation we decide not to clone. 74713bcf2e68a88cb87378c9773effa5b79b3091d75Andrew TrickInstruction *WidenIV::CloneIVUser(NarrowIVDefUse DU) { 74813bcf2e68a88cb87378c9773effa5b79b3091d75Andrew Trick unsigned Opcode = DU.NarrowUse->getOpcode(); 749f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick switch (Opcode) { 750f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick default: 751f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick return 0; 752f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick case Instruction::Add: 753f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick case Instruction::Mul: 754f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick case Instruction::UDiv: 755f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick case Instruction::Sub: 756f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick case Instruction::And: 757f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick case Instruction::Or: 758f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick case Instruction::Xor: 759f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick case Instruction::Shl: 760f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick case Instruction::LShr: 761f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick case Instruction::AShr: 76213bcf2e68a88cb87378c9773effa5b79b3091d75Andrew Trick DEBUG(dbgs() << "Cloning IVUser: " << *DU.NarrowUse << "\n"); 763f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 76403d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick // Replace NarrowDef operands with WideDef. Otherwise, we don't know 76503d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick // anything about the narrow operand yet so must insert a [sz]ext. It is 76603d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick // probably loop invariant and will be folded or hoisted. If it actually 76703d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick // comes from a widened IV, it should be removed during a future call to 76803d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick // WidenIVUse. 76913bcf2e68a88cb87378c9773effa5b79b3091d75Andrew Trick Value *LHS = (DU.NarrowUse->getOperand(0) == DU.NarrowDef) ? DU.WideDef : 770909ef7db3dad5247648e1e89a34f1382815442b8Andrew Trick getExtend(DU.NarrowUse->getOperand(0), WideType, IsSigned, DU.NarrowUse); 77113bcf2e68a88cb87378c9773effa5b79b3091d75Andrew Trick Value *RHS = (DU.NarrowUse->getOperand(1) == DU.NarrowDef) ? DU.WideDef : 772909ef7db3dad5247648e1e89a34f1382815442b8Andrew Trick getExtend(DU.NarrowUse->getOperand(1), WideType, IsSigned, DU.NarrowUse); 77303d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick 77413bcf2e68a88cb87378c9773effa5b79b3091d75Andrew Trick BinaryOperator *NarrowBO = cast<BinaryOperator>(DU.NarrowUse); 775f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick BinaryOperator *WideBO = BinaryOperator::Create(NarrowBO->getOpcode(), 77603d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick LHS, RHS, 777f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick NarrowBO->getName()); 778909ef7db3dad5247648e1e89a34f1382815442b8Andrew Trick IRBuilder<> Builder(DU.NarrowUse); 779f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick Builder.Insert(WideBO); 7806e0ce24e0ca8b0dc05872b9b4cec3a18972bee40Andrew Trick if (const OverflowingBinaryOperator *OBO = 7816e0ce24e0ca8b0dc05872b9b4cec3a18972bee40Andrew Trick dyn_cast<OverflowingBinaryOperator>(NarrowBO)) { 7826e0ce24e0ca8b0dc05872b9b4cec3a18972bee40Andrew Trick if (OBO->hasNoUnsignedWrap()) WideBO->setHasNoUnsignedWrap(); 7836e0ce24e0ca8b0dc05872b9b4cec3a18972bee40Andrew Trick if (OBO->hasNoSignedWrap()) WideBO->setHasNoSignedWrap(); 7846e0ce24e0ca8b0dc05872b9b4cec3a18972bee40Andrew Trick } 78503d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick return WideBO; 786f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick } 787f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick} 788f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 78920151da8c38287b9fa181e9fef93f70bc2cd9fd2Andrew Trick/// No-wrap operations can transfer sign extension of their result to their 79020151da8c38287b9fa181e9fef93f70bc2cd9fd2Andrew Trick/// operands. Generate the SCEV value for the widened operation without 79120151da8c38287b9fa181e9fef93f70bc2cd9fd2Andrew Trick/// actually modifying the IR yet. If the expression after extending the 79220151da8c38287b9fa181e9fef93f70bc2cd9fd2Andrew Trick/// operands is an AddRec for this loop, return it. 79320151da8c38287b9fa181e9fef93f70bc2cd9fd2Andrew Trickconst SCEVAddRecExpr* WidenIV::GetExtendedOperandRecurrence(NarrowIVDefUse DU) { 79420151da8c38287b9fa181e9fef93f70bc2cd9fd2Andrew Trick // Handle the common case of add<nsw/nuw> 79520151da8c38287b9fa181e9fef93f70bc2cd9fd2Andrew Trick if (DU.NarrowUse->getOpcode() != Instruction::Add) 79620151da8c38287b9fa181e9fef93f70bc2cd9fd2Andrew Trick return 0; 79720151da8c38287b9fa181e9fef93f70bc2cd9fd2Andrew Trick 79820151da8c38287b9fa181e9fef93f70bc2cd9fd2Andrew Trick // One operand (NarrowDef) has already been extended to WideDef. Now determine 79920151da8c38287b9fa181e9fef93f70bc2cd9fd2Andrew Trick // if extending the other will lead to a recurrence. 80020151da8c38287b9fa181e9fef93f70bc2cd9fd2Andrew Trick unsigned ExtendOperIdx = DU.NarrowUse->getOperand(0) == DU.NarrowDef ? 1 : 0; 80120151da8c38287b9fa181e9fef93f70bc2cd9fd2Andrew Trick assert(DU.NarrowUse->getOperand(1-ExtendOperIdx) == DU.NarrowDef && "bad DU"); 80220151da8c38287b9fa181e9fef93f70bc2cd9fd2Andrew Trick 80320151da8c38287b9fa181e9fef93f70bc2cd9fd2Andrew Trick const SCEV *ExtendOperExpr = 0; 80420151da8c38287b9fa181e9fef93f70bc2cd9fd2Andrew Trick const OverflowingBinaryOperator *OBO = 80520151da8c38287b9fa181e9fef93f70bc2cd9fd2Andrew Trick cast<OverflowingBinaryOperator>(DU.NarrowUse); 80620151da8c38287b9fa181e9fef93f70bc2cd9fd2Andrew Trick if (IsSigned && OBO->hasNoSignedWrap()) 80720151da8c38287b9fa181e9fef93f70bc2cd9fd2Andrew Trick ExtendOperExpr = SE->getSignExtendExpr( 80820151da8c38287b9fa181e9fef93f70bc2cd9fd2Andrew Trick SE->getSCEV(DU.NarrowUse->getOperand(ExtendOperIdx)), WideType); 80920151da8c38287b9fa181e9fef93f70bc2cd9fd2Andrew Trick else if(!IsSigned && OBO->hasNoUnsignedWrap()) 81020151da8c38287b9fa181e9fef93f70bc2cd9fd2Andrew Trick ExtendOperExpr = SE->getZeroExtendExpr( 81120151da8c38287b9fa181e9fef93f70bc2cd9fd2Andrew Trick SE->getSCEV(DU.NarrowUse->getOperand(ExtendOperIdx)), WideType); 81220151da8c38287b9fa181e9fef93f70bc2cd9fd2Andrew Trick else 81320151da8c38287b9fa181e9fef93f70bc2cd9fd2Andrew Trick return 0; 81420151da8c38287b9fa181e9fef93f70bc2cd9fd2Andrew Trick 815ecb35ece5c42d89057da3c2c7bc2e95f08b1dbefAndrew Trick // When creating this AddExpr, don't apply the current operations NSW or NUW 816ecb35ece5c42d89057da3c2c7bc2e95f08b1dbefAndrew Trick // flags. This instruction may be guarded by control flow that the no-wrap 817ecb35ece5c42d89057da3c2c7bc2e95f08b1dbefAndrew Trick // behavior depends on. Non-control-equivalent instructions can be mapped to 818ecb35ece5c42d89057da3c2c7bc2e95f08b1dbefAndrew Trick // the same SCEV expression, and it would be incorrect to transfer NSW/NUW 819ecb35ece5c42d89057da3c2c7bc2e95f08b1dbefAndrew Trick // semantics to those operations. 82020151da8c38287b9fa181e9fef93f70bc2cd9fd2Andrew Trick const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>( 821ecb35ece5c42d89057da3c2c7bc2e95f08b1dbefAndrew Trick SE->getAddExpr(SE->getSCEV(DU.WideDef), ExtendOperExpr)); 82220151da8c38287b9fa181e9fef93f70bc2cd9fd2Andrew Trick 82320151da8c38287b9fa181e9fef93f70bc2cd9fd2Andrew Trick if (!AddRec || AddRec->getLoop() != L) 82420151da8c38287b9fa181e9fef93f70bc2cd9fd2Andrew Trick return 0; 82520151da8c38287b9fa181e9fef93f70bc2cd9fd2Andrew Trick return AddRec; 82620151da8c38287b9fa181e9fef93f70bc2cd9fd2Andrew Trick} 82720151da8c38287b9fa181e9fef93f70bc2cd9fd2Andrew Trick 82839d7802224532c075f4c781c3e51ffed83d17420Andrew Trick/// GetWideRecurrence - Is this instruction potentially interesting from 82939d7802224532c075f4c781c3e51ffed83d17420Andrew Trick/// IVUsers' perspective after widening it's type? In other words, can the 83039d7802224532c075f4c781c3e51ffed83d17420Andrew Trick/// extend be safely hoisted out of the loop with SCEV reducing the value to a 83139d7802224532c075f4c781c3e51ffed83d17420Andrew Trick/// recurrence on the same loop. If so, return the sign or zero extended 83239d7802224532c075f4c781c3e51ffed83d17420Andrew Trick/// recurrence. Otherwise return NULL. 833e0dc2faaa0105c9d1cc56f0b70e93d532a6f8c4cAndrew Trickconst SCEVAddRecExpr *WidenIV::GetWideRecurrence(Instruction *NarrowUse) { 834e0dc2faaa0105c9d1cc56f0b70e93d532a6f8c4cAndrew Trick if (!SE->isSCEVable(NarrowUse->getType())) 835e0dc2faaa0105c9d1cc56f0b70e93d532a6f8c4cAndrew Trick return 0; 836e0dc2faaa0105c9d1cc56f0b70e93d532a6f8c4cAndrew Trick 837e0dc2faaa0105c9d1cc56f0b70e93d532a6f8c4cAndrew Trick const SCEV *NarrowExpr = SE->getSCEV(NarrowUse); 838e0dc2faaa0105c9d1cc56f0b70e93d532a6f8c4cAndrew Trick if (SE->getTypeSizeInBits(NarrowExpr->getType()) 839e0dc2faaa0105c9d1cc56f0b70e93d532a6f8c4cAndrew Trick >= SE->getTypeSizeInBits(WideType)) { 840e0dc2faaa0105c9d1cc56f0b70e93d532a6f8c4cAndrew Trick // NarrowUse implicitly widens its operand. e.g. a gep with a narrow 841e0dc2faaa0105c9d1cc56f0b70e93d532a6f8c4cAndrew Trick // index. So don't follow this use. 842e0dc2faaa0105c9d1cc56f0b70e93d532a6f8c4cAndrew Trick return 0; 843e0dc2faaa0105c9d1cc56f0b70e93d532a6f8c4cAndrew Trick } 844e0dc2faaa0105c9d1cc56f0b70e93d532a6f8c4cAndrew Trick 845e0dc2faaa0105c9d1cc56f0b70e93d532a6f8c4cAndrew Trick const SCEV *WideExpr = IsSigned ? 846e0dc2faaa0105c9d1cc56f0b70e93d532a6f8c4cAndrew Trick SE->getSignExtendExpr(NarrowExpr, WideType) : 847e0dc2faaa0105c9d1cc56f0b70e93d532a6f8c4cAndrew Trick SE->getZeroExtendExpr(NarrowExpr, WideType); 848e0dc2faaa0105c9d1cc56f0b70e93d532a6f8c4cAndrew Trick const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(WideExpr); 849e0dc2faaa0105c9d1cc56f0b70e93d532a6f8c4cAndrew Trick if (!AddRec || AddRec->getLoop() != L) 850e0dc2faaa0105c9d1cc56f0b70e93d532a6f8c4cAndrew Trick return 0; 851e0dc2faaa0105c9d1cc56f0b70e93d532a6f8c4cAndrew Trick return AddRec; 852e0dc2faaa0105c9d1cc56f0b70e93d532a6f8c4cAndrew Trick} 853e0dc2faaa0105c9d1cc56f0b70e93d532a6f8c4cAndrew Trick 854f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick/// WidenIVUse - Determine whether an individual user of the narrow IV can be 855f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick/// widened. If so, return the wide clone of the user. 856b5c26ef9da16052597d59a412eaae32098aa1be0Andrew TrickInstruction *WidenIV::WidenIVUse(NarrowIVDefUse DU, SCEVExpander &Rewriter) { 857cc359d9fa28a871b18d93da76fd9cf516499e39fAndrew Trick 8584b02915386046fa882a95553a7457ae7d05e9f27Andrew Trick // Stop traversing the def-use chain at inner-loop phis or post-loop phis. 85913bcf2e68a88cb87378c9773effa5b79b3091d75Andrew Trick if (isa<PHINode>(DU.NarrowUse) && 86013bcf2e68a88cb87378c9773effa5b79b3091d75Andrew Trick LI->getLoopFor(DU.NarrowUse->getParent()) != L) 861f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick return 0; 862f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 863f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // Our raison d'etre! Eliminate sign and zero extension. 86413bcf2e68a88cb87378c9773effa5b79b3091d75Andrew Trick if (IsSigned ? isa<SExtInst>(DU.NarrowUse) : isa<ZExtInst>(DU.NarrowUse)) { 86513bcf2e68a88cb87378c9773effa5b79b3091d75Andrew Trick Value *NewDef = DU.WideDef; 86613bcf2e68a88cb87378c9773effa5b79b3091d75Andrew Trick if (DU.NarrowUse->getType() != WideType) { 86713bcf2e68a88cb87378c9773effa5b79b3091d75Andrew Trick unsigned CastWidth = SE->getTypeSizeInBits(DU.NarrowUse->getType()); 86803d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick unsigned IVWidth = SE->getTypeSizeInBits(WideType); 86903d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick if (CastWidth < IVWidth) { 87003d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick // The cast isn't as wide as the IV, so insert a Trunc. 87113bcf2e68a88cb87378c9773effa5b79b3091d75Andrew Trick IRBuilder<> Builder(DU.NarrowUse); 87213bcf2e68a88cb87378c9773effa5b79b3091d75Andrew Trick NewDef = Builder.CreateTrunc(DU.WideDef, DU.NarrowUse->getType()); 87303d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick } 87403d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick else { 87503d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick // A wider extend was hidden behind a narrower one. This may induce 87603d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick // another round of IV widening in which the intermediate IV becomes 87703d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick // dead. It should be very rare. 87803d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick DEBUG(dbgs() << "INDVARS: New IV " << *WidePhi 87913bcf2e68a88cb87378c9773effa5b79b3091d75Andrew Trick << " not wide enough to subsume " << *DU.NarrowUse << "\n"); 88013bcf2e68a88cb87378c9773effa5b79b3091d75Andrew Trick DU.NarrowUse->replaceUsesOfWith(DU.NarrowDef, DU.WideDef); 88113bcf2e68a88cb87378c9773effa5b79b3091d75Andrew Trick NewDef = DU.NarrowUse; 88203d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick } 88303d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick } 88413bcf2e68a88cb87378c9773effa5b79b3091d75Andrew Trick if (NewDef != DU.NarrowUse) { 88513bcf2e68a88cb87378c9773effa5b79b3091d75Andrew Trick DEBUG(dbgs() << "INDVARS: eliminating " << *DU.NarrowUse 88613bcf2e68a88cb87378c9773effa5b79b3091d75Andrew Trick << " replaced by " << *DU.WideDef << "\n"); 88703d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick ++NumElimExt; 88813bcf2e68a88cb87378c9773effa5b79b3091d75Andrew Trick DU.NarrowUse->replaceAllUsesWith(NewDef); 88913bcf2e68a88cb87378c9773effa5b79b3091d75Andrew Trick DeadInsts.push_back(DU.NarrowUse); 89003d3d3b361800f28c75d3386978d22e6d57744b7Andrew Trick } 8912fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick // Now that the extend is gone, we want to expose it's uses for potential 8922fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick // further simplification. We don't need to directly inform SimplifyIVUsers 8932fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick // of the new users, because their parent IV will be processed later as a 8942fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick // new loop phi. If we preserved IVUsers analysis, we would also want to 8952fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick // push the uses of WideDef here. 896f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 897f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // No further widening is needed. The deceased [sz]ext had done it for us. 898f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick return 0; 899f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick } 9004b02915386046fa882a95553a7457ae7d05e9f27Andrew Trick 9014b02915386046fa882a95553a7457ae7d05e9f27Andrew Trick // Does this user itself evaluate to a recurrence after widening? 90213bcf2e68a88cb87378c9773effa5b79b3091d75Andrew Trick const SCEVAddRecExpr *WideAddRec = GetWideRecurrence(DU.NarrowUse); 903f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick if (!WideAddRec) { 90420151da8c38287b9fa181e9fef93f70bc2cd9fd2Andrew Trick WideAddRec = GetExtendedOperandRecurrence(DU); 90520151da8c38287b9fa181e9fef93f70bc2cd9fd2Andrew Trick } 90620151da8c38287b9fa181e9fef93f70bc2cd9fd2Andrew Trick if (!WideAddRec) { 907f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // This user does not evaluate to a recurence after widening, so don't 908f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // follow it. Instead insert a Trunc to kill off the original use, 909f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // eventually isolating the original narrow IV so it can be removed. 91086c98145b268a0d10e062792f98bc8eea6b639b4Andrew Trick IRBuilder<> Builder(getInsertPointForUses(DU.NarrowUse, DU.NarrowDef, DT)); 91113bcf2e68a88cb87378c9773effa5b79b3091d75Andrew Trick Value *Trunc = Builder.CreateTrunc(DU.WideDef, DU.NarrowDef->getType()); 91213bcf2e68a88cb87378c9773effa5b79b3091d75Andrew Trick DU.NarrowUse->replaceUsesOfWith(DU.NarrowDef, Trunc); 913f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick return 0; 914f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick } 915fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick // Assume block terminators cannot evaluate to a recurrence. We can't to 9164b02915386046fa882a95553a7457ae7d05e9f27Andrew Trick // insert a Trunc after a terminator if there happens to be a critical edge. 91713bcf2e68a88cb87378c9773effa5b79b3091d75Andrew Trick assert(DU.NarrowUse != DU.NarrowUse->getParent()->getTerminator() && 9184b02915386046fa882a95553a7457ae7d05e9f27Andrew Trick "SCEV is not expected to evaluate a block terminator"); 919cc359d9fa28a871b18d93da76fd9cf516499e39fAndrew Trick 920fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick // Reuse the IV increment that SCEVExpander created as long as it dominates 921fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick // NarrowUse. 922f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick Instruction *WideUse = 0; 923204494149b6f846e8f173f525b129f5508076049Andrew Trick if (WideAddRec == WideIncExpr 924b5c26ef9da16052597d59a412eaae32098aa1be0Andrew Trick && Rewriter.hoistIVInc(WideInc, DU.NarrowUse)) 925f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick WideUse = WideInc; 926f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick else { 92713bcf2e68a88cb87378c9773effa5b79b3091d75Andrew Trick WideUse = CloneIVUser(DU); 928f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick if (!WideUse) 929f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick return 0; 930f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick } 9314b02915386046fa882a95553a7457ae7d05e9f27Andrew Trick // Evaluation of WideAddRec ensured that the narrow expression could be 9324b02915386046fa882a95553a7457ae7d05e9f27Andrew Trick // extended outside the loop without overflow. This suggests that the wide use 933f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // evaluates to the same expression as the extended narrow use, but doesn't 934f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // absolutely guarantee it. Hence the following failsafe check. In rare cases 9352fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick // where it fails, we simply throw away the newly created wide use. 936f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick if (WideAddRec != SE->getSCEV(WideUse)) { 937f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick DEBUG(dbgs() << "Wide use expression mismatch: " << *WideUse 938f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick << ": " << *SE->getSCEV(WideUse) << " != " << *WideAddRec << "\n"); 939f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick DeadInsts.push_back(WideUse); 940f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick return 0; 941f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick } 942f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 943f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // Returning WideUse pushes it on the worklist. 944f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick return WideUse; 945f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick} 946f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 9474b02915386046fa882a95553a7457ae7d05e9f27Andrew Trick/// pushNarrowIVUsers - Add eligible users of NarrowDef to NarrowIVUsers. 9484b02915386046fa882a95553a7457ae7d05e9f27Andrew Trick/// 9494b02915386046fa882a95553a7457ae7d05e9f27Andrew Trickvoid WidenIV::pushNarrowIVUsers(Instruction *NarrowDef, Instruction *WideDef) { 9504b02915386046fa882a95553a7457ae7d05e9f27Andrew Trick for (Value::use_iterator UI = NarrowDef->use_begin(), 9514b02915386046fa882a95553a7457ae7d05e9f27Andrew Trick UE = NarrowDef->use_end(); UI != UE; ++UI) { 95213bcf2e68a88cb87378c9773effa5b79b3091d75Andrew Trick Instruction *NarrowUse = cast<Instruction>(*UI); 9534b02915386046fa882a95553a7457ae7d05e9f27Andrew Trick 9544b02915386046fa882a95553a7457ae7d05e9f27Andrew Trick // Handle data flow merges and bizarre phi cycles. 95513bcf2e68a88cb87378c9773effa5b79b3091d75Andrew Trick if (!Widened.insert(NarrowUse)) 9564b02915386046fa882a95553a7457ae7d05e9f27Andrew Trick continue; 9574b02915386046fa882a95553a7457ae7d05e9f27Andrew Trick 95813bcf2e68a88cb87378c9773effa5b79b3091d75Andrew Trick NarrowIVUsers.push_back(NarrowIVDefUse(NarrowDef, NarrowUse, WideDef)); 9594b02915386046fa882a95553a7457ae7d05e9f27Andrew Trick } 9604b02915386046fa882a95553a7457ae7d05e9f27Andrew Trick} 9614b02915386046fa882a95553a7457ae7d05e9f27Andrew Trick 962f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick/// CreateWideIV - Process a single induction variable. First use the 963f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick/// SCEVExpander to create a wide induction variable that evaluates to the same 964f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick/// recurrence as the original narrow IV. Then use a worklist to forward 9652fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// traverse the narrow IV's def-use chain. After WidenIVUse has processed all 966f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick/// interesting IV users, the narrow IV will be isolated for removal by 967f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick/// DeleteDeadPHIs. 968f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick/// 969f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick/// It would be simpler to delete uses as they are processed, but we must avoid 970f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick/// invalidating SCEV expressions. 971f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick/// 9722fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew TrickPHINode *WidenIV::CreateWideIV(SCEVExpander &Rewriter) { 973f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // Is this phi an induction variable? 974f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(SE->getSCEV(OrigPhi)); 975f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick if (!AddRec) 9762fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick return NULL; 977f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 978f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // Widen the induction variable expression. 979f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick const SCEV *WideIVExpr = IsSigned ? 980f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick SE->getSignExtendExpr(AddRec, WideType) : 981f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick SE->getZeroExtendExpr(AddRec, WideType); 982f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 983f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick assert(SE->getEffectiveSCEVType(WideIVExpr->getType()) == WideType && 984f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick "Expect the new IV expression to preserve its type"); 985f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 986f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // Can the IV be extended outside the loop without overflow? 987f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick AddRec = dyn_cast<SCEVAddRecExpr>(WideIVExpr); 988f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick if (!AddRec || AddRec->getLoop() != L) 9892fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick return NULL; 990f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 9912fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick // An AddRec must have loop-invariant operands. Since this AddRec is 992f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // materialized by a loop header phi, the expression cannot have any post-loop 993f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // operands, so they must dominate the loop header. 994f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick assert(SE->properlyDominates(AddRec->getStart(), L->getHeader()) && 995f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick SE->properlyDominates(AddRec->getStepRecurrence(*SE), L->getHeader()) 996f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick && "Loop header phi recurrence inputs do not dominate the loop"); 997f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 998f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // The rewriter provides a value for the desired IV expression. This may 999f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // either find an existing phi or materialize a new one. Either way, we 1000f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // expect a well-formed cyclic phi-with-increments. i.e. any operand not part 1001f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // of the phi-SCC dominates the loop entry. 1002f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick Instruction *InsertPt = L->getHeader()->begin(); 1003f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick WidePhi = cast<PHINode>(Rewriter.expandCodeFor(AddRec, WideType, InsertPt)); 1004f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 1005f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // Remembering the WideIV increment generated by SCEVExpander allows 1006f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // WidenIVUse to reuse it when widening the narrow IV's increment. We don't 1007f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // employ a general reuse mechanism because the call above is the only call to 1008f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // SCEVExpander. Henceforth, we produce 1-to-1 narrow to wide uses. 1009fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick if (BasicBlock *LatchBlock = L->getLoopLatch()) { 1010fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick WideInc = 1011fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick cast<Instruction>(WidePhi->getIncomingValueForBlock(LatchBlock)); 1012fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick WideIncExpr = SE->getSCEV(WideInc); 1013fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick } 1014f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 1015f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick DEBUG(dbgs() << "Wide IV: " << *WidePhi << "\n"); 1016f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick ++NumWidened; 1017f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 1018f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick // Traverse the def-use chain using a worklist starting at the original IV. 10194b02915386046fa882a95553a7457ae7d05e9f27Andrew Trick assert(Widened.empty() && NarrowIVUsers.empty() && "expect initial state" ); 10204b02915386046fa882a95553a7457ae7d05e9f27Andrew Trick 10214b02915386046fa882a95553a7457ae7d05e9f27Andrew Trick Widened.insert(OrigPhi); 10224b02915386046fa882a95553a7457ae7d05e9f27Andrew Trick pushNarrowIVUsers(OrigPhi, WidePhi); 1023f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick 1024f85092c25525f75eef6982ffa40c9b48b87da987Andrew Trick while (!NarrowIVUsers.empty()) { 102513bcf2e68a88cb87378c9773effa5b79b3091d75Andrew Trick NarrowIVDefUse DU = NarrowIVUsers.pop_back_val(); 1026fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick 1027fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick // Process a def-use edge. This may replace the use, so don't hold a 1028fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick // use_iterator across it. 1029b5c26ef9da16052597d59a412eaae32098aa1be0Andrew Trick Instruction *WideUse = WidenIVUse(DU, Rewriter); 1030fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick 1031fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick // Follow all def-use edges from the previous narrow use. 10324b02915386046fa882a95553a7457ae7d05e9f27Andrew Trick if (WideUse) 103313bcf2e68a88cb87378c9773effa5b79b3091d75Andrew Trick pushNarrowIVUsers(DU.NarrowUse, WideUse); 10344b02915386046fa882a95553a7457ae7d05e9f27Andrew Trick 1035fcdc9a44e59ff2846c6f929e91c90ee34e6ba5d5Andrew Trick // WidenIVUse may have removed the def-use edge. 103613bcf2e68a88cb87378c9773effa5b79b3091d75Andrew Trick if (DU.NarrowDef->use_empty()) 103713bcf2e68a88cb87378c9773effa5b79b3091d75Andrew Trick DeadInsts.push_back(DU.NarrowDef); 1038931e345e76e75391d2a7c96530e305f802b5429dDan Gohman } 10392fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick return WidePhi; 1040931e345e76e75391d2a7c96530e305f802b5429dDan Gohman} 1041931e345e76e75391d2a7c96530e305f802b5429dDan Gohman 10421a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick//===----------------------------------------------------------------------===// 10431a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick// Simplification of IV users based on SCEV evaluation. 10441a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick//===----------------------------------------------------------------------===// 10451a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 104606988bcf6a5c74e81cf7e76f06a686aa822ec00aAndrew Trick 10474b4bb71bcdfd8c17cd4acb6116fc9a56c5fecd47Andrew Trick/// SimplifyAndExtend - Iteratively perform simplification on a worklist of IV 10484b4bb71bcdfd8c17cd4acb6116fc9a56c5fecd47Andrew Trick/// users. Each successive simplification may push more users which may 10492fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// themselves be candidates for simplification. 10502fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// 10514b4bb71bcdfd8c17cd4acb6116fc9a56c5fecd47Andrew Trick/// Sign/Zero extend elimination is interleaved with IV simplification. 10522fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick/// 10534b4bb71bcdfd8c17cd4acb6116fc9a56c5fecd47Andrew Trickvoid IndVarSimplify::SimplifyAndExtend(Loop *L, 10544b4bb71bcdfd8c17cd4acb6116fc9a56c5fecd47Andrew Trick SCEVExpander &Rewriter, 10554b4bb71bcdfd8c17cd4acb6116fc9a56c5fecd47Andrew Trick LPPassManager &LPM) { 1056513b1f47c1ddef0638bd63399bf64965e592c2bfAndrew Trick SmallVector<WideIVInfo, 8> WideIVs; 105715832f61775040995bb8aa6056176425bc2c9088Andrew Trick 10582fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick SmallVector<PHINode*, 8> LoopPhis; 10592fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I) { 10602fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick LoopPhis.push_back(cast<PHINode>(I)); 10612fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick } 106215832f61775040995bb8aa6056176425bc2c9088Andrew Trick // Each round of simplification iterates through the SimplifyIVUsers worklist 106315832f61775040995bb8aa6056176425bc2c9088Andrew Trick // for all current phis, then determines whether any IVs can be 106415832f61775040995bb8aa6056176425bc2c9088Andrew Trick // widened. Widening adds new phis to LoopPhis, inducing another round of 106515832f61775040995bb8aa6056176425bc2c9088Andrew Trick // simplification on the wide IVs. 10662fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick while (!LoopPhis.empty()) { 106715832f61775040995bb8aa6056176425bc2c9088Andrew Trick // Evaluate as many IV expressions as possible before widening any IVs. This 106899a92f67c7ee0d428e18f35c91311a2baba6c03eAndrew Trick // forces SCEV to set no-wrap flags before evaluating sign/zero 106915832f61775040995bb8aa6056176425bc2c9088Andrew Trick // extension. The first time SCEV attempts to normalize sign/zero extension, 107015832f61775040995bb8aa6056176425bc2c9088Andrew Trick // the result becomes final. So for the most predictable results, we delay 107115832f61775040995bb8aa6056176425bc2c9088Andrew Trick // evaluation of sign/zero extend evaluation until needed, and avoid running 10724b4bb71bcdfd8c17cd4acb6116fc9a56c5fecd47Andrew Trick // other SCEV based analysis prior to SimplifyAndExtend. 107315832f61775040995bb8aa6056176425bc2c9088Andrew Trick do { 107415832f61775040995bb8aa6056176425bc2c9088Andrew Trick PHINode *CurrIV = LoopPhis.pop_back_val(); 10752fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick 107615832f61775040995bb8aa6056176425bc2c9088Andrew Trick // Information about sign/zero extensions of CurrIV. 1077513b1f47c1ddef0638bd63399bf64965e592c2bfAndrew Trick WideIVVisitor WIV(CurrIV, SE, TD); 107815832f61775040995bb8aa6056176425bc2c9088Andrew Trick 1079bddb7f82103deb226baa6793f41c5961661167e7Andrew Trick Changed |= simplifyUsersOfIV(CurrIV, SE, &LPM, DeadInsts, &WIV); 108006988bcf6a5c74e81cf7e76f06a686aa822ec00aAndrew Trick 10814b4bb71bcdfd8c17cd4acb6116fc9a56c5fecd47Andrew Trick if (WIV.WI.WidestNativeType) { 1082513b1f47c1ddef0638bd63399bf64965e592c2bfAndrew Trick WideIVs.push_back(WIV.WI); 10832fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick } 108415832f61775040995bb8aa6056176425bc2c9088Andrew Trick } while(!LoopPhis.empty()); 108515832f61775040995bb8aa6056176425bc2c9088Andrew Trick 1086513b1f47c1ddef0638bd63399bf64965e592c2bfAndrew Trick for (; !WideIVs.empty(); WideIVs.pop_back()) { 1087513b1f47c1ddef0638bd63399bf64965e592c2bfAndrew Trick WidenIV Widener(WideIVs.back(), LI, SE, DT, DeadInsts); 10882fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick if (PHINode *WidePhi = Widener.CreateWideIV(Rewriter)) { 10892fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick Changed = true; 10902fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick LoopPhis.push_back(WidePhi); 10912fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick } 10922fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick } 10932fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick } 10942fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick} 10952fabd464ae9fd33f068066e3fc3d0caa7ea2279dAndrew Trick 10961a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick//===----------------------------------------------------------------------===// 10971a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick// LinearFunctionTestReplace and its kin. Rewrite the loop exit condition. 10981a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick//===----------------------------------------------------------------------===// 10991a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 110039d7802224532c075f4c781c3e51ffed83d17420Andrew Trick/// Check for expressions that ScalarEvolution generates to compute 110139d7802224532c075f4c781c3e51ffed83d17420Andrew Trick/// BackedgeTakenInfo. If these expressions have not been reduced, then 110239d7802224532c075f4c781c3e51ffed83d17420Andrew Trick/// expanding them may incur additional cost (albeit in the loop preheader). 11035241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trickstatic bool isHighCostExpansion(const SCEV *S, BranchInst *BI, 110486d34100cf164f6ba5c0c2344b7dff86cc0a0980Andrew Trick SmallPtrSet<const SCEV*, 8> &Processed, 11055241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick ScalarEvolution *SE) { 110686d34100cf164f6ba5c0c2344b7dff86cc0a0980Andrew Trick if (!Processed.insert(S)) 110786d34100cf164f6ba5c0c2344b7dff86cc0a0980Andrew Trick return false; 110886d34100cf164f6ba5c0c2344b7dff86cc0a0980Andrew Trick 11095241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick // If the backedge-taken count is a UDiv, it's very likely a UDiv that 11105241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick // ScalarEvolution's HowFarToZero or HowManyLessThans produced to compute a 11115241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick // precise expression, rather than a UDiv from the user's code. If we can't 11125241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick // find a UDiv in the code with some simple searching, assume the former and 11135241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick // forego rewriting the loop. 11145241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick if (isa<SCEVUDivExpr>(S)) { 11155241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick ICmpInst *OrigCond = dyn_cast<ICmpInst>(BI->getCondition()); 11165241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick if (!OrigCond) return true; 11175241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick const SCEV *R = SE->getSCEV(OrigCond->getOperand(1)); 11185241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick R = SE->getMinusSCEV(R, SE->getConstant(R->getType(), 1)); 11195241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick if (R != S) { 11205241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick const SCEV *L = SE->getSCEV(OrigCond->getOperand(0)); 11215241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick L = SE->getMinusSCEV(L, SE->getConstant(L->getType(), 1)); 11225241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick if (L != S) 11235241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick return true; 11245241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick } 11255241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick } 11265241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick 11275241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick // Recurse past add expressions, which commonly occur in the 11285241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick // BackedgeTakenCount. They may already exist in program code, and if not, 11295241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick // they are not too expensive rematerialize. 11305241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) { 11315241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick for (SCEVAddExpr::op_iterator I = Add->op_begin(), E = Add->op_end(); 11325241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick I != E; ++I) { 113386d34100cf164f6ba5c0c2344b7dff86cc0a0980Andrew Trick if (isHighCostExpansion(*I, BI, Processed, SE)) 11345241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick return true; 11355241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick } 11365241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick return false; 11375241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick } 11385241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick 11395241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick // HowManyLessThans uses a Max expression whenever the loop is not guarded by 11405241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick // the exit condition. 11415241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick if (isa<SCEVSMaxExpr>(S) || isa<SCEVUMaxExpr>(S)) 11425241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick return true; 11435241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick 11445fef01db01592903d3a22701b598fb6a69265c53Nick Lewycky // If we haven't recognized an expensive SCEV pattern, assume it's an 11455fef01db01592903d3a22701b598fb6a69265c53Nick Lewycky // expression produced by program code. 11465241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick return false; 11475241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick} 11485241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick 11491a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick/// canExpandBackedgeTakenCount - Return true if this loop's backedge taken 11501a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick/// count expression can be safely and cheaply expanded into an instruction 11511a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick/// sequence that can be used by LinearFunctionTestReplace. 1152d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick/// 1153d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick/// TODO: This fails for pointer-type loop counters with greater than one byte 1154d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick/// strides, consequently preventing LFTR from running. For the purpose of LFTR 1155d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick/// we could skip this check in the case that the LFTR loop counter (chosen by 1156d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick/// FindLoopCounter) is also pointer type. Instead, we could directly convert 1157d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick/// the loop test to an inequality test by checking the target data's alignment 1158d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick/// of element types (given that the initial pointer value originates from or is 1159d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick/// used by ABI constrained operation, as opposed to inttoptr/ptrtoint). 1160d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick/// However, we don't yet have a strong motivation for converting loop tests 1161d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick/// into inequality tests. 11621a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trickstatic bool canExpandBackedgeTakenCount(Loop *L, ScalarEvolution *SE) { 11631a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick const SCEV *BackedgeTakenCount = SE->getBackedgeTakenCount(L); 11641a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (isa<SCEVCouldNotCompute>(BackedgeTakenCount) || 11651a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick BackedgeTakenCount->isZero()) 1166a52838285b6dce66821f0b272cb3479af8c3edb2Dan Gohman return false; 1167a52838285b6dce66821f0b272cb3479af8c3edb2Dan Gohman 11681a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (!L->getExitingBlock()) 11691a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick return false; 117037da40875873d70b83dc08b2803052bec9b68886Andrew Trick 11711a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // Can't rewrite non-branch yet. 11721a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick BranchInst *BI = dyn_cast<BranchInst>(L->getExitingBlock()->getTerminator()); 11731a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (!BI) 11741a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick return false; 117560f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman 117686d34100cf164f6ba5c0c2344b7dff86cc0a0980Andrew Trick SmallPtrSet<const SCEV*, 8> Processed; 117786d34100cf164f6ba5c0c2344b7dff86cc0a0980Andrew Trick if (isHighCostExpansion(BackedgeTakenCount, BI, Processed, SE)) 11785241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick return false; 11795241b79ebc3ec10469dab49a24e4ed3a8b4c3fa5Andrew Trick 11801a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick return true; 11811a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick} 118260f8a63e2502d57e879bf52a4a48505b74fa9716Dan Gohman 1183fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick/// getLoopPhiForCounter - Return the loop header phi IFF IncV adds a loop 1184fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick/// invariant value to the phi. 1185fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trickstatic PHINode *getLoopPhiForCounter(Value *IncV, Loop *L, DominatorTree *DT) { 1186fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick Instruction *IncI = dyn_cast<Instruction>(IncV); 1187fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick if (!IncI) 1188fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick return 0; 1189fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick 1190fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick switch (IncI->getOpcode()) { 1191fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick case Instruction::Add: 1192fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick case Instruction::Sub: 1193fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick break; 1194fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick case Instruction::GetElementPtr: 1195fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick // An IV counter must preserve its type. 1196fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick if (IncI->getNumOperands() == 2) 1197fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick break; 1198fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick default: 1199fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick return 0; 1200fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick } 1201fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick 1202fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick PHINode *Phi = dyn_cast<PHINode>(IncI->getOperand(0)); 1203fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick if (Phi && Phi->getParent() == L->getHeader()) { 1204fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick if (isLoopInvariant(IncI->getOperand(1), L, DT)) 1205fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick return Phi; 1206fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick return 0; 1207fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick } 1208fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick if (IncI->getOpcode() == Instruction::GetElementPtr) 1209fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick return 0; 1210fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick 1211fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick // Allow add/sub to be commuted. 1212fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick Phi = dyn_cast<PHINode>(IncI->getOperand(1)); 1213fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick if (Phi && Phi->getParent() == L->getHeader()) { 1214fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick if (isLoopInvariant(IncI->getOperand(0), L, DT)) 1215fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick return Phi; 1216fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick } 1217fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick return 0; 1218fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick} 1219fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick 12204781d8ee1cd586bf7a569f80e1e49694c93eddd8Andrew Trick/// Return the compare guarding the loop latch, or NULL for unrecognized tests. 12214781d8ee1cd586bf7a569f80e1e49694c93eddd8Andrew Trickstatic ICmpInst *getLoopTest(Loop *L) { 1222fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick assert(L->getExitingBlock() && "expected loop exit"); 1223fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick 1224fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick BasicBlock *LatchBlock = L->getLoopLatch(); 1225fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick // Don't bother with LFTR if the loop is not properly simplified. 1226fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick if (!LatchBlock) 12274781d8ee1cd586bf7a569f80e1e49694c93eddd8Andrew Trick return 0; 1228fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick 1229fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick BranchInst *BI = dyn_cast<BranchInst>(L->getExitingBlock()->getTerminator()); 1230fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick assert(BI && "expected exit branch"); 1231fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick 12324781d8ee1cd586bf7a569f80e1e49694c93eddd8Andrew Trick return dyn_cast<ICmpInst>(BI->getCondition()); 12334781d8ee1cd586bf7a569f80e1e49694c93eddd8Andrew Trick} 12344781d8ee1cd586bf7a569f80e1e49694c93eddd8Andrew Trick 12354781d8ee1cd586bf7a569f80e1e49694c93eddd8Andrew Trick/// needsLFTR - LinearFunctionTestReplace policy. Return true unless we can show 12364781d8ee1cd586bf7a569f80e1e49694c93eddd8Andrew Trick/// that the current exit test is already sufficiently canonical. 12374781d8ee1cd586bf7a569f80e1e49694c93eddd8Andrew Trickstatic bool needsLFTR(Loop *L, DominatorTree *DT) { 1238fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick // Do LFTR to simplify the exit condition to an ICMP. 12394781d8ee1cd586bf7a569f80e1e49694c93eddd8Andrew Trick ICmpInst *Cond = getLoopTest(L); 1240fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick if (!Cond) 1241fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick return true; 1242fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick 1243fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick // Do LFTR to simplify the exit ICMP to EQ/NE 1244fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick ICmpInst::Predicate Pred = Cond->getPredicate(); 1245fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick if (Pred != ICmpInst::ICMP_NE && Pred != ICmpInst::ICMP_EQ) 1246fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick return true; 1247fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick 1248fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick // Look for a loop invariant RHS 1249fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick Value *LHS = Cond->getOperand(0); 1250fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick Value *RHS = Cond->getOperand(1); 1251fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick if (!isLoopInvariant(RHS, L, DT)) { 1252fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick if (!isLoopInvariant(LHS, L, DT)) 1253fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick return true; 1254fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick std::swap(LHS, RHS); 1255fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick } 1256fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick // Look for a simple IV counter LHS 1257fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick PHINode *Phi = dyn_cast<PHINode>(LHS); 1258fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick if (!Phi) 1259fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick Phi = getLoopPhiForCounter(LHS, L, DT); 1260fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick 1261fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick if (!Phi) 1262fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick return true; 1263fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick 1264eb51e95e61bd93cb764e14cdd5f0271e237e4673Jakub Staszak // Do LFTR if PHI node is defined in the loop, but is *not* a counter. 1265395c1502a7e6380ec2210ee4be1fdb3128c10528Jakub Staszak int Idx = Phi->getBasicBlockIndex(L->getLoopLatch()); 1266395c1502a7e6380ec2210ee4be1fdb3128c10528Jakub Staszak if (Idx < 0) 1267395c1502a7e6380ec2210ee4be1fdb3128c10528Jakub Staszak return true; 1268eb51e95e61bd93cb764e14cdd5f0271e237e4673Jakub Staszak 1269eb51e95e61bd93cb764e14cdd5f0271e237e4673Jakub Staszak // Do LFTR if the exit condition's IV is *not* a simple counter. 1270395c1502a7e6380ec2210ee4be1fdb3128c10528Jakub Staszak Value *IncV = Phi->getIncomingValue(Idx); 1271fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick return Phi != getLoopPhiForCounter(IncV, L, DT); 1272fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick} 1273fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick 12744781d8ee1cd586bf7a569f80e1e49694c93eddd8Andrew Trick/// Recursive helper for hasConcreteDef(). Unfortunately, this currently boils 12754781d8ee1cd586bf7a569f80e1e49694c93eddd8Andrew Trick/// down to checking that all operands are constant and listing instructions 12764781d8ee1cd586bf7a569f80e1e49694c93eddd8Andrew Trick/// that may hide undef. 12774781d8ee1cd586bf7a569f80e1e49694c93eddd8Andrew Trickstatic bool hasConcreteDefImpl(Value *V, SmallPtrSet<Value*, 8> &Visited, 12784781d8ee1cd586bf7a569f80e1e49694c93eddd8Andrew Trick unsigned Depth) { 12794781d8ee1cd586bf7a569f80e1e49694c93eddd8Andrew Trick if (isa<Constant>(V)) 12804781d8ee1cd586bf7a569f80e1e49694c93eddd8Andrew Trick return !isa<UndefValue>(V); 12814781d8ee1cd586bf7a569f80e1e49694c93eddd8Andrew Trick 12824781d8ee1cd586bf7a569f80e1e49694c93eddd8Andrew Trick if (Depth >= 6) 12834781d8ee1cd586bf7a569f80e1e49694c93eddd8Andrew Trick return false; 12844781d8ee1cd586bf7a569f80e1e49694c93eddd8Andrew Trick 12854781d8ee1cd586bf7a569f80e1e49694c93eddd8Andrew Trick // Conservatively handle non-constant non-instructions. For example, Arguments 12864781d8ee1cd586bf7a569f80e1e49694c93eddd8Andrew Trick // may be undef. 12874781d8ee1cd586bf7a569f80e1e49694c93eddd8Andrew Trick Instruction *I = dyn_cast<Instruction>(V); 12884781d8ee1cd586bf7a569f80e1e49694c93eddd8Andrew Trick if (!I) 12894781d8ee1cd586bf7a569f80e1e49694c93eddd8Andrew Trick return false; 12904781d8ee1cd586bf7a569f80e1e49694c93eddd8Andrew Trick 12914781d8ee1cd586bf7a569f80e1e49694c93eddd8Andrew Trick // Load and return values may be undef. 12924781d8ee1cd586bf7a569f80e1e49694c93eddd8Andrew Trick if(I->mayReadFromMemory() || isa<CallInst>(I) || isa<InvokeInst>(I)) 12934781d8ee1cd586bf7a569f80e1e49694c93eddd8Andrew Trick return false; 12944781d8ee1cd586bf7a569f80e1e49694c93eddd8Andrew Trick 12954781d8ee1cd586bf7a569f80e1e49694c93eddd8Andrew Trick // Optimistically handle other instructions. 12964781d8ee1cd586bf7a569f80e1e49694c93eddd8Andrew Trick for (User::op_iterator OI = I->op_begin(), E = I->op_end(); OI != E; ++OI) { 12974781d8ee1cd586bf7a569f80e1e49694c93eddd8Andrew Trick if (!Visited.insert(*OI)) 12984781d8ee1cd586bf7a569f80e1e49694c93eddd8Andrew Trick continue; 12994781d8ee1cd586bf7a569f80e1e49694c93eddd8Andrew Trick if (!hasConcreteDefImpl(*OI, Visited, Depth+1)) 13004781d8ee1cd586bf7a569f80e1e49694c93eddd8Andrew Trick return false; 13014781d8ee1cd586bf7a569f80e1e49694c93eddd8Andrew Trick } 13024781d8ee1cd586bf7a569f80e1e49694c93eddd8Andrew Trick return true; 13034781d8ee1cd586bf7a569f80e1e49694c93eddd8Andrew Trick} 13044781d8ee1cd586bf7a569f80e1e49694c93eddd8Andrew Trick 13054781d8ee1cd586bf7a569f80e1e49694c93eddd8Andrew Trick/// Return true if the given value is concrete. We must prove that undef can 13064781d8ee1cd586bf7a569f80e1e49694c93eddd8Andrew Trick/// never reach it. 13074781d8ee1cd586bf7a569f80e1e49694c93eddd8Andrew Trick/// 13084781d8ee1cd586bf7a569f80e1e49694c93eddd8Andrew Trick/// TODO: If we decide that this is a good approach to checking for undef, we 13094781d8ee1cd586bf7a569f80e1e49694c93eddd8Andrew Trick/// may factor it into a common location. 13104781d8ee1cd586bf7a569f80e1e49694c93eddd8Andrew Trickstatic bool hasConcreteDef(Value *V) { 13114781d8ee1cd586bf7a569f80e1e49694c93eddd8Andrew Trick SmallPtrSet<Value*, 8> Visited; 13124781d8ee1cd586bf7a569f80e1e49694c93eddd8Andrew Trick Visited.insert(V); 13134781d8ee1cd586bf7a569f80e1e49694c93eddd8Andrew Trick return hasConcreteDefImpl(V, Visited, 0); 13144781d8ee1cd586bf7a569f80e1e49694c93eddd8Andrew Trick} 13154781d8ee1cd586bf7a569f80e1e49694c93eddd8Andrew Trick 1316fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick/// AlmostDeadIV - Return true if this IV has any uses other than the (soon to 1317fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick/// be rewritten) loop exit test. 1318fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trickstatic bool AlmostDeadIV(PHINode *Phi, BasicBlock *LatchBlock, Value *Cond) { 1319fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick int LatchIdx = Phi->getBasicBlockIndex(LatchBlock); 1320fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick Value *IncV = Phi->getIncomingValue(LatchIdx); 1321fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick 1322fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick for (Value::use_iterator UI = Phi->use_begin(), UE = Phi->use_end(); 1323fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick UI != UE; ++UI) { 1324fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick if (*UI != Cond && *UI != IncV) return false; 1325fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick } 1326fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick 1327fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick for (Value::use_iterator UI = IncV->use_begin(), UE = IncV->use_end(); 1328fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick UI != UE; ++UI) { 1329fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick if (*UI != Cond && *UI != Phi) return false; 1330fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick } 1331fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick return true; 1332fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick} 1333fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick 1334fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick/// FindLoopCounter - Find an affine IV in canonical form. 1335fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick/// 1336d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick/// BECount may be an i8* pointer type. The pointer difference is already 1337d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick/// valid count without scaling the address stride, so it remains a pointer 1338d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick/// expression as far as SCEV is concerned. 1339d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick/// 13404781d8ee1cd586bf7a569f80e1e49694c93eddd8Andrew Trick/// Currently only valid for LFTR. See the comments on hasConcreteDef below. 13414781d8ee1cd586bf7a569f80e1e49694c93eddd8Andrew Trick/// 1342fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick/// FIXME: Accept -1 stride and set IVLimit = IVInit - BECount 1343fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick/// 1344fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick/// FIXME: Accept non-unit stride as long as SCEV can reduce BECount * Stride. 1345fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick/// This is difficult in general for SCEV because of potential overflow. But we 1346fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick/// could at least handle constant BECounts. 1347fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trickstatic PHINode * 1348fc933c073e9357a791c0f6b307355ed735e3557fAndrew TrickFindLoopCounter(Loop *L, const SCEV *BECount, 13493574eca1b02600bac4e625297f4ecf745f4c4f32Micah Villmow ScalarEvolution *SE, DominatorTree *DT, const DataLayout *TD) { 1350fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick uint64_t BCWidth = SE->getTypeSizeInBits(BECount->getType()); 1351fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick 1352fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick Value *Cond = 1353fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick cast<BranchInst>(L->getExitingBlock()->getTerminator())->getCondition(); 1354fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick 1355fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick // Loop over all of the PHI nodes, looking for a simple counter. 1356fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick PHINode *BestPhi = 0; 1357fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick const SCEV *BestInit = 0; 1358fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick BasicBlock *LatchBlock = L->getLoopLatch(); 1359fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick assert(LatchBlock && "needsLFTR should guarantee a loop latch"); 1360fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick 1361fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I) { 1362fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick PHINode *Phi = cast<PHINode>(I); 1363fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick if (!SE->isSCEVable(Phi->getType())) 1364fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick continue; 1365fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick 1366d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick // Avoid comparing an integer IV against a pointer Limit. 1367d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick if (BECount->getType()->isPointerTy() && !Phi->getType()->isPointerTy()) 1368d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick continue; 1369d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick 1370fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(SE->getSCEV(Phi)); 1371fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick if (!AR || AR->getLoop() != L || !AR->isAffine()) 1372fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick continue; 1373fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick 1374fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick // AR may be a pointer type, while BECount is an integer type. 1375fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick // AR may be wider than BECount. With eq/ne tests overflow is immaterial. 1376fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick // AR may not be a narrower type, or we may never exit. 1377fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick uint64_t PhiWidth = SE->getTypeSizeInBits(AR->getType()); 1378fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick if (PhiWidth < BCWidth || (TD && !TD->isLegalInteger(PhiWidth))) 1379fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick continue; 1380fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick 1381fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick const SCEV *Step = dyn_cast<SCEVConstant>(AR->getStepRecurrence(*SE)); 1382fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick if (!Step || !Step->isOne()) 1383fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick continue; 1384fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick 1385fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick int LatchIdx = Phi->getBasicBlockIndex(LatchBlock); 1386fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick Value *IncV = Phi->getIncomingValue(LatchIdx); 1387fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick if (getLoopPhiForCounter(IncV, L, DT) != Phi) 1388fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick continue; 1389fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick 13904781d8ee1cd586bf7a569f80e1e49694c93eddd8Andrew Trick // Avoid reusing a potentially undef value to compute other values that may 13914781d8ee1cd586bf7a569f80e1e49694c93eddd8Andrew Trick // have originally had a concrete definition. 13924781d8ee1cd586bf7a569f80e1e49694c93eddd8Andrew Trick if (!hasConcreteDef(Phi)) { 13934781d8ee1cd586bf7a569f80e1e49694c93eddd8Andrew Trick // We explicitly allow unknown phis as long as they are already used by 13944781d8ee1cd586bf7a569f80e1e49694c93eddd8Andrew Trick // the loop test. In this case we assume that performing LFTR could not 13954781d8ee1cd586bf7a569f80e1e49694c93eddd8Andrew Trick // increase the number of undef users. 13964781d8ee1cd586bf7a569f80e1e49694c93eddd8Andrew Trick if (ICmpInst *Cond = getLoopTest(L)) { 13974781d8ee1cd586bf7a569f80e1e49694c93eddd8Andrew Trick if (Phi != getLoopPhiForCounter(Cond->getOperand(0), L, DT) 13984781d8ee1cd586bf7a569f80e1e49694c93eddd8Andrew Trick && Phi != getLoopPhiForCounter(Cond->getOperand(1), L, DT)) { 13994781d8ee1cd586bf7a569f80e1e49694c93eddd8Andrew Trick continue; 14004781d8ee1cd586bf7a569f80e1e49694c93eddd8Andrew Trick } 14014781d8ee1cd586bf7a569f80e1e49694c93eddd8Andrew Trick } 14024781d8ee1cd586bf7a569f80e1e49694c93eddd8Andrew Trick } 1403fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick const SCEV *Init = AR->getStart(); 1404fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick 1405fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick if (BestPhi && !AlmostDeadIV(BestPhi, LatchBlock, Cond)) { 1406fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick // Don't force a live loop counter if another IV can be used. 1407fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick if (AlmostDeadIV(Phi, LatchBlock, Cond)) 1408fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick continue; 1409fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick 1410fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick // Prefer to count-from-zero. This is a more "canonical" counter form. It 1411fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick // also prefers integer to pointer IVs. 1412fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick if (BestInit->isZero() != Init->isZero()) { 1413fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick if (BestInit->isZero()) 1414fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick continue; 1415fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick } 1416fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick // If two IVs both count from zero or both count from nonzero then the 1417fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick // narrower is likely a dead phi that has been widened. Use the wider phi 1418fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick // to allow the other to be eliminated. 14197f496a628eb93d60eed39340fcc5e89479eda488Andrew Trick else if (PhiWidth <= SE->getTypeSizeInBits(BestPhi->getType())) 1420fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick continue; 1421fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick } 1422fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick BestPhi = Phi; 1423fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick BestInit = Init; 1424fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick } 1425fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick return BestPhi; 1426fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick} 1427fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick 1428d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick/// genLoopLimit - Help LinearFunctionTestReplace by generating a value that 1429d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick/// holds the RHS of the new loop test. 1430d3714b60b5adf15376a8803e6622c74694884b28Andrew Trickstatic Value *genLoopLimit(PHINode *IndVar, const SCEV *IVCount, Loop *L, 1431ece6c6bb6329748b92403c06ac87f45c43485911Chandler Carruth SCEVExpander &Rewriter, ScalarEvolution *SE) { 1432d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(SE->getSCEV(IndVar)); 1433d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick assert(AR && AR->getLoop() == L && AR->isAffine() && "bad loop counter"); 1434d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick const SCEV *IVInit = AR->getStart(); 1435d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick 1436d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick // IVInit may be a pointer while IVCount is an integer when FindLoopCounter 1437d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick // finds a valid pointer IV. Sign extend BECount in order to materialize a 1438d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick // GEP. Avoid running SCEVExpander on a new pointer value, instead reusing 1439d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick // the existing GEPs whenever possible. 1440d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick if (IndVar->getType()->isPointerTy() 1441d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick && !IVCount->getType()->isPointerTy()) { 1442d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick 1443d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick Type *OfsTy = SE->getEffectiveSCEVType(IVInit->getType()); 1444d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick const SCEV *IVOffset = SE->getTruncateOrSignExtend(IVCount, OfsTy); 1445d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick 1446d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick // Expand the code for the iteration count. 1447d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick assert(SE->isLoopInvariant(IVOffset, L) && 1448d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick "Computed iteration count is not loop invariant!"); 1449d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick BranchInst *BI = cast<BranchInst>(L->getExitingBlock()->getTerminator()); 1450d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick Value *GEPOffset = Rewriter.expandCodeFor(IVOffset, OfsTy, BI); 1451d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick 1452d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick Value *GEPBase = IndVar->getIncomingValueForBlock(L->getLoopPreheader()); 1453d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick assert(AR->getStart() == SE->getSCEV(GEPBase) && "bad loop counter"); 1454d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick // We could handle pointer IVs other than i8*, but we need to compensate for 1455d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick // gep index scaling. See canExpandBackedgeTakenCount comments. 1456d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick assert(SE->getSizeOfExpr( 1457ece6c6bb6329748b92403c06ac87f45c43485911Chandler Carruth cast<PointerType>(GEPBase->getType())->getElementType())->isOne() 1458d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick && "unit stride pointer IV must be i8*"); 1459d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick 1460d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick IRBuilder<> Builder(L->getLoopPreheader()->getTerminator()); 1461d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick return Builder.CreateGEP(GEPBase, GEPOffset, "lftr.limit"); 1462d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick } 1463d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick else { 1464d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick // In any other case, convert both IVInit and IVCount to integers before 1465d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick // comparing. This may result in SCEV expension of pointers, but in practice 1466d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick // SCEV will fold the pointer arithmetic away as such: 1467d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick // BECount = (IVEnd - IVInit - 1) => IVLimit = IVInit (postinc). 1468d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick // 1469d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick // Valid Cases: (1) both integers is most common; (2) both may be pointers 1470d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick // for simple memset-style loops; (3) IVInit is an integer and IVCount is a 1471d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick // pointer may occur when enable-iv-rewrite generates a canonical IV on top 1472d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick // of case #2. 1473d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick 1474d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick const SCEV *IVLimit = 0; 1475d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick // For unit stride, IVCount = Start + BECount with 2's complement overflow. 1476d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick // For non-zero Start, compute IVCount here. 1477d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick if (AR->getStart()->isZero()) 1478d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick IVLimit = IVCount; 1479d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick else { 1480d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick assert(AR->getStepRecurrence(*SE)->isOne() && "only handles unit stride"); 1481d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick const SCEV *IVInit = AR->getStart(); 1482d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick 1483d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick // For integer IVs, truncate the IV before computing IVInit + BECount. 1484d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick if (SE->getTypeSizeInBits(IVInit->getType()) 1485d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick > SE->getTypeSizeInBits(IVCount->getType())) 1486d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick IVInit = SE->getTruncateExpr(IVInit, IVCount->getType()); 1487d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick 1488d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick IVLimit = SE->getAddExpr(IVInit, IVCount); 1489d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick } 1490d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick // Expand the code for the iteration count. 1491d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick BranchInst *BI = cast<BranchInst>(L->getExitingBlock()->getTerminator()); 1492d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick IRBuilder<> Builder(BI); 1493d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick assert(SE->isLoopInvariant(IVLimit, L) && 1494d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick "Computed iteration count is not loop invariant!"); 1495d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick // Ensure that we generate the same type as IndVar, or a smaller integer 1496d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick // type. In the presence of null pointer values, we have an integer type 1497d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick // SCEV expression (IVInit) for a pointer type IV value (IndVar). 1498d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick Type *LimitTy = IVCount->getType()->isPointerTy() ? 1499d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick IndVar->getType() : IVCount->getType(); 1500d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick return Rewriter.expandCodeFor(IVLimit, LimitTy, BI); 1501d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick } 1502d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick} 1503d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick 15041a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick/// LinearFunctionTestReplace - This method rewrites the exit condition of the 15051a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick/// loop to be a canonical != comparison against the incremented loop induction 15061a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick/// variable. This pass is able to rewrite the exit tests of any loop where the 15071a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick/// SCEV analysis can determine a loop-invariant trip count of the loop, which 15081a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick/// is actually a much broader range than just linear tests. 1509fc933c073e9357a791c0f6b307355ed735e3557fAndrew TrickValue *IndVarSimplify:: 15101a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew TrickLinearFunctionTestReplace(Loop *L, 15111a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick const SCEV *BackedgeTakenCount, 15121a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick PHINode *IndVar, 15131a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick SCEVExpander &Rewriter) { 15141a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick assert(canExpandBackedgeTakenCount(L, SE) && "precondition"); 15151a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 1516f21bdf4f429223bcd76bf0198295a7ddbe7a1fdfAndrew Trick // LFTR can ignore IV overflow and truncate to the width of 1517fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick // BECount. This avoids materializing the add(zext(add)) expression. 1518db0d666578388026278c17f848095b396b7ea27dAndrew Trick Type *CntTy = BackedgeTakenCount->getType(); 1519fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick 1520d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick const SCEV *IVCount = BackedgeTakenCount; 1521fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick 1522d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick // If the exiting block is the same as the backedge block, we prefer to 1523d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick // compare against the post-incremented value, otherwise we must compare 1524d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick // against the preincremented value. 15251a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick Value *CmpIndVar; 15261a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (L->getExitingBlock() == L->getLoopLatch()) { 15271a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // Add one to the "backedge-taken" count to get the trip count. 15281a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // If this addition may overflow, we have to be more pessimistic and 15291a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // cast the induction variable before doing the add. 15301a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick const SCEV *N = 1531d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick SE->getAddExpr(IVCount, SE->getConstant(IVCount->getType(), 1)); 1532d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick if (CntTy == IVCount->getType()) 1533d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick IVCount = N; 1534fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick else { 1535d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick const SCEV *Zero = SE->getConstant(IVCount->getType(), 0); 1536fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick if ((isa<SCEVConstant>(N) && !N->isZero()) || 1537fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick SE->isLoopEntryGuardedByCond(L, ICmpInst::ICMP_NE, N, Zero)) { 1538fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick // No overflow. Cast the sum. 1539d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick IVCount = SE->getTruncateOrZeroExtend(N, CntTy); 1540fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick } else { 1541fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick // Potential overflow. Cast before doing the add. 1542d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick IVCount = SE->getTruncateOrZeroExtend(IVCount, CntTy); 1543d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick IVCount = SE->getAddExpr(IVCount, SE->getConstant(CntTy, 1)); 1544fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick } 15451a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick } 15461a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // The BackedgeTaken expression contains the number of times that the 15471a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // backedge branches to the loop header. This is one less than the 15481a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // number of times the loop executes, so use the incremented indvar. 15491a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick CmpIndVar = IndVar->getIncomingValueForBlock(L->getExitingBlock()); 15501a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick } else { 1551d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick // We must use the preincremented value... 1552d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick IVCount = SE->getTruncateOrZeroExtend(IVCount, CntTy); 15531a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick CmpIndVar = IndVar; 15541a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick } 15551a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 1556ece6c6bb6329748b92403c06ac87f45c43485911Chandler Carruth Value *ExitCnt = genLoopLimit(IndVar, IVCount, L, Rewriter, SE); 1557d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick assert(ExitCnt->getType()->isPointerTy() == IndVar->getType()->isPointerTy() 1558d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick && "genLoopLimit missed a cast"); 15591a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 15601a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // Insert a new icmp_ne or icmp_eq instruction before the branch. 1561d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick BranchInst *BI = cast<BranchInst>(L->getExitingBlock()->getTerminator()); 1562fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick ICmpInst::Predicate P; 15631a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (L->contains(BI->getSuccessor(0))) 1564fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick P = ICmpInst::ICMP_NE; 15651a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick else 1566fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick P = ICmpInst::ICMP_EQ; 15671a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 15681a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick DEBUG(dbgs() << "INDVARS: Rewriting loop exit condition to:\n" 15691a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick << " LHS:" << *CmpIndVar << '\n' 15701a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick << " op:\t" 1571fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick << (P == ICmpInst::ICMP_NE ? "!=" : "==") << "\n" 1572fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick << " RHS:\t" << *ExitCnt << "\n" 1573d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick << " IVCount:\t" << *IVCount << "\n"); 15741a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 1575d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick IRBuilder<> Builder(BI); 1576fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick if (SE->getTypeSizeInBits(CmpIndVar->getType()) 1577d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick > SE->getTypeSizeInBits(ExitCnt->getType())) { 1578d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick CmpIndVar = Builder.CreateTrunc(CmpIndVar, ExitCnt->getType(), 1579d3714b60b5adf15376a8803e6622c74694884b28Andrew Trick "lftr.wideiv"); 1580fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick } 1581fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick 1582fc933c073e9357a791c0f6b307355ed735e3557fAndrew Trick Value *Cond = Builder.CreateICmp(P, CmpIndVar, ExitCnt, "exitcond"); 15831a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick Value *OrigCond = BI->getCondition(); 15841a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // It's tempting to use replaceAllUsesWith here to fully replace the old 15851a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // comparison, but that's not immediately safe, since users of the old 15861a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // comparison may not be dominated by the new comparison. Instead, just 15871a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // update the branch to use the new comparison; in the common case this 15881a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // will make old comparison dead. 15891a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick BI->setCondition(Cond); 15901a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick DeadInsts.push_back(OrigCond); 15911a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 15921a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick ++NumLFTR; 15931a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick Changed = true; 15941a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick return Cond; 15951a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick} 15961a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 15971a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick//===----------------------------------------------------------------------===// 15981a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick// SinkUnusedInvariants. A late subpass to cleanup loop preheaders. 15991a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick//===----------------------------------------------------------------------===// 16001a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 16011a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick/// If there's a single exit block, sink any loop-invariant values that 16021a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick/// were defined in the preheader but not used inside the loop into the 16031a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick/// exit block to reduce register pressure in the loop. 16041a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trickvoid IndVarSimplify::SinkUnusedInvariants(Loop *L) { 16051a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick BasicBlock *ExitBlock = L->getExitBlock(); 16061a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (!ExitBlock) return; 16071a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 16081a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick BasicBlock *Preheader = L->getLoopPreheader(); 16091a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (!Preheader) return; 16101a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 1611b05fdd6babada25da2ec3ba54bb462c2ecfc42a8Bill Wendling Instruction *InsertPt = ExitBlock->getFirstInsertionPt(); 16121a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick BasicBlock::iterator I = Preheader->getTerminator(); 16131a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick while (I != Preheader->begin()) { 16141a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick --I; 16151a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // New instructions were inserted at the end of the preheader. 16161a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (isa<PHINode>(I)) 16171a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick break; 16181a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 16191a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // Don't move instructions which might have side effects, since the side 16201a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // effects need to complete before instructions inside the loop. Also don't 16211a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // move instructions which might read memory, since the loop may modify 16221a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // memory. Note that it's okay if the instruction might have undefined 16231a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // behavior: LoopSimplify guarantees that the preheader dominates the exit 16241a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // block. 16251a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (I->mayHaveSideEffects() || I->mayReadFromMemory()) 16261a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick continue; 16271a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 16281a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // Skip debug info intrinsics. 16291a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (isa<DbgInfoIntrinsic>(I)) 16301a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick continue; 16311a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 16322b18881185b123e5f163eb7b32b3452fc3f339d8Bill Wendling // Skip landingpad instructions. 16332b18881185b123e5f163eb7b32b3452fc3f339d8Bill Wendling if (isa<LandingPadInst>(I)) 16342b18881185b123e5f163eb7b32b3452fc3f339d8Bill Wendling continue; 16352b18881185b123e5f163eb7b32b3452fc3f339d8Bill Wendling 16368ecde6cbf87cfa3184cec5a4eedb70b06dbb4a85Eli Friedman // Don't sink alloca: we never want to sink static alloca's out of the 16378ecde6cbf87cfa3184cec5a4eedb70b06dbb4a85Eli Friedman // entry block, and correctly sinking dynamic alloca's requires 16388ecde6cbf87cfa3184cec5a4eedb70b06dbb4a85Eli Friedman // checks for stacksave/stackrestore intrinsics. 16398ecde6cbf87cfa3184cec5a4eedb70b06dbb4a85Eli Friedman // FIXME: Refactor this check somehow? 16408ecde6cbf87cfa3184cec5a4eedb70b06dbb4a85Eli Friedman if (isa<AllocaInst>(I)) 16418ecde6cbf87cfa3184cec5a4eedb70b06dbb4a85Eli Friedman continue; 16421a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 16431a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // Determine if there is a use in or before the loop (direct or 16441a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // otherwise). 16451a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick bool UsedInLoop = false; 16461a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick for (Value::use_iterator UI = I->use_begin(), UE = I->use_end(); 16471a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick UI != UE; ++UI) { 16481a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick User *U = *UI; 16491a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick BasicBlock *UseBB = cast<Instruction>(U)->getParent(); 16501a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (PHINode *P = dyn_cast<PHINode>(U)) { 16511a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick unsigned i = 16521a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick PHINode::getIncomingValueNumForOperand(UI.getOperandNo()); 16531a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick UseBB = P->getIncomingBlock(i); 16541a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick } 16551a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (UseBB == Preheader || L->contains(UseBB)) { 16561a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick UsedInLoop = true; 16571a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick break; 16581a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick } 16591a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick } 16601a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 16611a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // If there is, the def must remain in the preheader. 16621a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (UsedInLoop) 16631a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick continue; 16641a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 16651a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // Otherwise, sink it to the exit block. 16661a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick Instruction *ToMove = I; 16671a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick bool Done = false; 16681a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 16691a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (I != Preheader->begin()) { 16701a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // Skip debug info intrinsics. 16711a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick do { 16721a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick --I; 16731a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick } while (isa<DbgInfoIntrinsic>(I) && I != Preheader->begin()); 16741a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 16751a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (isa<DbgInfoIntrinsic>(I) && I == Preheader->begin()) 16761a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick Done = true; 16771a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick } else { 16781a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick Done = true; 16791a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick } 16801a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 16811a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick ToMove->moveBefore(InsertPt); 16821a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (Done) break; 16831a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick InsertPt = ToMove; 16841a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick } 16851a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick} 16861a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 16871a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick//===----------------------------------------------------------------------===// 16881a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick// IndVarSimplify driver. Manage several subpasses of IV simplification. 16891a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick//===----------------------------------------------------------------------===// 16901a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 16911a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trickbool IndVarSimplify::runOnLoop(Loop *L, LPPassManager &LPM) { 16921a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // If LoopSimplify form is not available, stay out of trouble. Some notes: 16931a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // - LSR currently only supports LoopSimplify-form loops. Indvars' 16941a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // canonicalization can be a pessimization without LSR to "clean up" 16951a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // afterwards. 16961a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // - We depend on having a preheader; in particular, 16971a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // Loop::getCanonicalInductionVariable only supports loops with preheaders, 16981a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // and we're in trouble if we can't find the induction variable even when 16991a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // we've manually inserted one. 17001a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (!L->isLoopSimplifyForm()) 17011a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick return false; 17021a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 17031a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick LI = &getAnalysis<LoopInfo>(); 17041a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick SE = &getAnalysis<ScalarEvolution>(); 17051a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick DT = &getAnalysis<DominatorTree>(); 17063574eca1b02600bac4e625297f4ecf745f4c4f32Micah Villmow TD = getAnalysisIfAvailable<DataLayout>(); 17078e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer TLI = getAnalysisIfAvailable<TargetLibraryInfo>(); 17081a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 17091a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick DeadInsts.clear(); 17101a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick Changed = false; 17111a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 17121a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // If there are any floating-point recurrences, attempt to 17131a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // transform them to use integer recurrences. 17141a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick RewriteNonIntegerIVs(L); 17151a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 17161a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick const SCEV *BackedgeTakenCount = SE->getBackedgeTakenCount(L); 17171a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 17181a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // Create a rewriter object which we'll use to transform the code with. 17191a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick SCEVExpander Rewriter(*SE, "indvars"); 1720204494149b6f846e8f173f525b129f5508076049Andrew Trick#ifndef NDEBUG 1721204494149b6f846e8f173f525b129f5508076049Andrew Trick Rewriter.setDebugType(DEBUG_TYPE); 1722204494149b6f846e8f173f525b129f5508076049Andrew Trick#endif 17231a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 17241a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // Eliminate redundant IV users. 17251a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // 17261a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // Simplification works best when run before other consumers of SCEV. We 17271a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // attempt to avoid evaluating SCEVs for sign/zero extend operations until 17281a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // other expressions involving loop IVs have been evaluated. This helps SCEV 17291a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // set no-wrap flags before normalizing sign/zero extension. 1730db0d666578388026278c17f848095b396b7ea27dAndrew Trick Rewriter.disableCanonicalMode(); 1731db0d666578388026278c17f848095b396b7ea27dAndrew Trick SimplifyAndExtend(L, Rewriter, LPM); 17321a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 17331a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // Check to see if this loop has a computable loop-invariant execution count. 17341a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // If so, this means that we can compute the final value of any expressions 17351a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // that are recurrent in the loop, and substitute the exit values from the 17361a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // loop into any instructions outside of the loop that use the final values of 17371a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // the current expressions. 17381a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick // 17391a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick if (!isa<SCEVCouldNotCompute>(BackedgeTakenCount)) 17401a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick RewriteLoopExitValues(L, Rewriter); 17411a54bb28c79d5fc5b1c4e7fb0273ccb6a92c74e0Andrew Trick 17426f684b0becc4c1b2ece3ec6dcecf30b19343128dAndrew Trick // Eliminate redundant IV cycles. 1743db0d666578388026278c17f848095b396b7ea27dAndrew Trick NumElimIV += Rewriter.replaceCongruentIVs(L, DT, DeadInsts); 1744037d1c0c7e01cefeff7e538682c9a1e536e14030Andrew Trick 1745c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman // If we have a trip count expression, rewrite the loop's exit condition 1746c2390b14c91764cba6e4394d05e58e387a7dfb19Dan Gohman // using it. We can currently only handle loops with a single exit. 1747c5480c634c9de552f9f65c899bd55cc8f1f89e68Andrew Trick if (canExpandBackedgeTakenCount(L, SE) && needsLFTR(L, DT)) { 1748c5480c634c9de552f9f65c899bd55cc8f1f89e68Andrew Trick PHINode *IndVar = FindLoopCounter(L, BackedgeTakenCount, SE, DT, TD); 1749c5480c634c9de552f9f65c899bd55cc8f1f89e68Andrew Trick if (IndVar) { 1750c5480c634c9de552f9f65c899bd55cc8f1f89e68Andrew Trick // Check preconditions for proper SCEVExpander operation. SCEV does not 1751c5480c634c9de552f9f65c899bd55cc8f1f89e68Andrew Trick // express SCEVExpander's dependencies, such as LoopSimplify. Instead any 1752c5480c634c9de552f9f65c899bd55cc8f1f89e68Andrew Trick // pass that uses the SCEVExpander must do it. This does not work well for 1753c5480c634c9de552f9f65c899bd55cc8f1f89e68Andrew Trick // loop passes because SCEVExpander makes assumptions about all loops, while 1754c5480c634c9de552f9f65c899bd55cc8f1f89e68Andrew Trick // LoopPassManager only forces the current loop to be simplified. 1755c5480c634c9de552f9f65c899bd55cc8f1f89e68Andrew Trick // 1756c5480c634c9de552f9f65c899bd55cc8f1f89e68Andrew Trick // FIXME: SCEV expansion has no way to bail out, so the caller must 1757c5480c634c9de552f9f65c899bd55cc8f1f89e68Andrew Trick // explicitly check any assumptions made by SCEV. Brittle. 1758c5480c634c9de552f9f65c899bd55cc8f1f89e68Andrew Trick const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(BackedgeTakenCount); 1759c5480c634c9de552f9f65c899bd55cc8f1f89e68Andrew Trick if (!AR || AR->getLoop()->getLoopPreheader()) 1760c5480c634c9de552f9f65c899bd55cc8f1f89e68Andrew Trick (void)LinearFunctionTestReplace(L, BackedgeTakenCount, IndVar, 1761c5480c634c9de552f9f65c899bd55cc8f1f89e68Andrew Trick Rewriter); 1762c5480c634c9de552f9f65c899bd55cc8f1f89e68Andrew Trick } 176381db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman } 1764b12a754cce0c1d5542af605203a47820edba454dAndrew Trick // Clear the rewriter cache, because values that are in the rewriter's cache 1765b12a754cce0c1d5542af605203a47820edba454dAndrew Trick // can be deleted in the loop below, causing the AssertingVH in the cache to 1766b12a754cce0c1d5542af605203a47820edba454dAndrew Trick // trigger. 1767b12a754cce0c1d5542af605203a47820edba454dAndrew Trick Rewriter.clear(); 1768b12a754cce0c1d5542af605203a47820edba454dAndrew Trick 1769b12a754cce0c1d5542af605203a47820edba454dAndrew Trick // Now that we're done iterating through lists, clean up any instructions 1770b12a754cce0c1d5542af605203a47820edba454dAndrew Trick // which are now dead. 1771b12a754cce0c1d5542af605203a47820edba454dAndrew Trick while (!DeadInsts.empty()) 1772b12a754cce0c1d5542af605203a47820edba454dAndrew Trick if (Instruction *Inst = 1773b12a754cce0c1d5542af605203a47820edba454dAndrew Trick dyn_cast_or_null<Instruction>(&*DeadInsts.pop_back_val())) 17748e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer RecursivelyDeleteTriviallyDeadInstructions(Inst, TLI); 1775b12a754cce0c1d5542af605203a47820edba454dAndrew Trick 1776667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman // The Rewriter may not be used from this point on. 17773d431384f05c9defc84f36eafe220415cc12ee93Torok Edwin 177881db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Loop-invariant instructions in the preheader that aren't used in the 177981db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // loop may be sunk below the loop to reduce register pressure. 1780667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman SinkUnusedInvariants(L); 178181db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman 178281db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Clean up dead instructions. 17838e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer Changed |= DeleteDeadPHIs(L->getHeader(), TLI); 178481db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman // Check a post-condition. 1785f6a0dbaaf4f68f8e948a818135b9272776b8a52fAndrew Trick assert(L->isLCSSAForm(*DT) && 1786f6a0dbaaf4f68f8e948a818135b9272776b8a52fAndrew Trick "Indvars did not leave the loop in lcssa form!"); 1787f6a0dbaaf4f68f8e948a818135b9272776b8a52fAndrew Trick 1788f6a0dbaaf4f68f8e948a818135b9272776b8a52fAndrew Trick // Verify that LFTR, and any other change have not interfered with SCEV's 1789f6a0dbaaf4f68f8e948a818135b9272776b8a52fAndrew Trick // ability to compute trip count. 1790f6a0dbaaf4f68f8e948a818135b9272776b8a52fAndrew Trick#ifndef NDEBUG 1791db0d666578388026278c17f848095b396b7ea27dAndrew Trick if (VerifyIndvars && !isa<SCEVCouldNotCompute>(BackedgeTakenCount)) { 1792f6a0dbaaf4f68f8e948a818135b9272776b8a52fAndrew Trick SE->forgetLoop(L); 1793f6a0dbaaf4f68f8e948a818135b9272776b8a52fAndrew Trick const SCEV *NewBECount = SE->getBackedgeTakenCount(L); 1794f6a0dbaaf4f68f8e948a818135b9272776b8a52fAndrew Trick if (SE->getTypeSizeInBits(BackedgeTakenCount->getType()) < 1795f6a0dbaaf4f68f8e948a818135b9272776b8a52fAndrew Trick SE->getTypeSizeInBits(NewBECount->getType())) 1796f6a0dbaaf4f68f8e948a818135b9272776b8a52fAndrew Trick NewBECount = SE->getTruncateOrNoop(NewBECount, 1797f6a0dbaaf4f68f8e948a818135b9272776b8a52fAndrew Trick BackedgeTakenCount->getType()); 1798f6a0dbaaf4f68f8e948a818135b9272776b8a52fAndrew Trick else 1799f6a0dbaaf4f68f8e948a818135b9272776b8a52fAndrew Trick BackedgeTakenCount = SE->getTruncateOrNoop(BackedgeTakenCount, 1800f6a0dbaaf4f68f8e948a818135b9272776b8a52fAndrew Trick NewBECount->getType()); 1801f6a0dbaaf4f68f8e948a818135b9272776b8a52fAndrew Trick assert(BackedgeTakenCount == NewBECount && "indvars must preserve SCEV"); 1802f6a0dbaaf4f68f8e948a818135b9272776b8a52fAndrew Trick } 1803f6a0dbaaf4f68f8e948a818135b9272776b8a52fAndrew Trick#endif 1804f6a0dbaaf4f68f8e948a818135b9272776b8a52fAndrew Trick 180581db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman return Changed; 180681db61a2e6d3c95a2738c3559a108e05e9d7a05aDan Gohman} 1807