IVUsers.h revision 75ae20366fd1b480f4cc38400bb075c43c9f4f7f
1c3aae25116e66c177579b0b79182b09340b19753Chris Lattner//===- llvm/Analysis/IVUsers.h - Induction Variable Users -------*- C++ -*-===// 2ea61c358720aa6c7a159d51658b34276316aa841Misha Brukman// 36fbcc26f1460eaee4e0eb8b426fc1ff0c7af11beJohn Criswell// The LLVM Compiler Infrastructure 46fbcc26f1460eaee4e0eb8b426fc1ff0c7af11beJohn Criswell// 57ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// This file is distributed under the University of Illinois Open Source 67ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// License. See LICENSE.TXT for details. 7ea61c358720aa6c7a159d51658b34276316aa841Misha Brukman// 86fbcc26f1460eaee4e0eb8b426fc1ff0c7af11beJohn Criswell//===----------------------------------------------------------------------===// 9ea61c358720aa6c7a159d51658b34276316aa841Misha Brukman// 10c3aae25116e66c177579b0b79182b09340b19753Chris Lattner// This file implements bookkeeping for "interesting" users of expressions 11c3aae25116e66c177579b0b79182b09340b19753Chris Lattner// computed from induction variables. 12ea61c358720aa6c7a159d51658b34276316aa841Misha Brukman// 13cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner//===----------------------------------------------------------------------===// 14cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner 15cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner#ifndef LLVM_ANALYSIS_IVUSERS_H 16cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner#define LLVM_ANALYSIS_IVUSERS_H 17cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner 18c5e7e8d87d4a3b10edd5ac93ba1f3cdb4d1b449aDavid Greene#include "llvm/Analysis/LoopPass.h" 194b84086e89d86fb16f562166d9fea8df37db6be7Dan Gohman#include "llvm/Analysis/ScalarEvolutionNormalization.h" 20255f89faee13dc491cb64fbeae3c763e7e2ea4e6Chandler Carruth#include "llvm/Support/ValueHandle.h" 21444b4bf5c84c80833ff283244de0885124091a13Nadav Rotem 22583bd47f777fe3eb8305872fa0eadab31e833dffJim Laskeynamespace llvm { 23c76909abfec876c6b751d693ebd3df07df686aa0Dan Gohman 2498a366d547772010e94609e4584489b3e5ce0043Bill Wendlingclass DominatorTree; 25acaf09dbe4a6781163857db1321bbd5795e7d410Dan Gohmanclass Instruction; 26322812e603705e1c2037313633e72f689524b163Evan Chengclass Value; 27eb19e40efbd3cae80c908a30cdf4d33450733c45Chris Lattnerclass IVUsers; 28255f89faee13dc491cb64fbeae3c763e7e2ea4e6Chandler Carruthclass ScalarEvolution; 29d0fde30ce850b78371fd1386338350591f9ff494Brian Gaekeclass SCEV; 30d0fde30ce850b78371fd1386338350591f9ff494Brian Gaekeclass IVUsers; 31fed90b6d097d50881afb45e4d79f430db66dd741Dan Gohmanclass TargetData; 32fed90b6d097d50881afb45e4d79f430db66dd741Dan Gohman 33b4e6a5df5dada0cd919cc6e2717eb3118db9cc45Bill Wendling/// IVStrideUse - Keep track of one use of a strided induction variable. 34b4e6a5df5dada0cd919cc6e2717eb3118db9cc45Bill Wendling/// The Expr member keeps track of the expression, User is the actual user 3531441b7e95e0840e1ae144e5db6f791d6a36bc60Evan Cheng/// instruction of the operand, and 'OperandValToReplace' is the operand of 36b4e6a5df5dada0cd919cc6e2717eb3118db9cc45Bill Wendling/// the User that is the use. 37bfdf7f38523bd38ae0538861a2bfd8bdc46e5c33Dale Johannesenclass IVStrideUse : public CallbackVH, public ilist_node<IVStrideUse> { 38b4e6a5df5dada0cd919cc6e2717eb3118db9cc45Bill Wendling friend class IVUsers; 39ff7a562751604a9fe13efc75bd59622244b54d35Dan Gohmanpublic: 40fed90b6d097d50881afb45e4d79f430db66dd741Dan Gohman IVStrideUse(IVUsers *P, Instruction* U, Value *O) 418e4018e2de52c534405d7155c7009d0b35afb861Cedric Venet : CallbackVH(U), Parent(P), OperandValToReplace(O) { 428e4018e2de52c534405d7155c7009d0b35afb861Cedric Venet } 437309be6735666143bd9835b275dc8501617a2591Gabor Greif 44fed90b6d097d50881afb45e4d79f430db66dd741Dan Gohman /// getUser - Return the user instruction for this use. 45fed90b6d097d50881afb45e4d79f430db66dd741Dan Gohman Instruction *getUser() const { 46c7f6b8c5d40e17bf43fd3a1549d7d89c9da735e1Gabor Greif return cast<Instruction>(getValPtr()); 47fed90b6d097d50881afb45e4d79f430db66dd741Dan Gohman } 48fed90b6d097d50881afb45e4d79f430db66dd741Dan Gohman 49fed90b6d097d50881afb45e4d79f430db66dd741Dan Gohman /// setUser - Assign a new user instruction for this use. 50c23b8719ef9d6b1220e854b37d40e9e1c48a82bcGabor Greif void setUser(Instruction *NewUser) { 51c23b8719ef9d6b1220e854b37d40e9e1c48a82bcGabor Greif setValPtr(NewUser); 52f3841fcbd587c31aa9842b3f33bd57de40c9f443Gabor Greif } 53c23b8719ef9d6b1220e854b37d40e9e1c48a82bcGabor Greif 54fed90b6d097d50881afb45e4d79f430db66dd741Dan Gohman /// getOperandValToReplace - Return the Value of the operand in the user 5550bee42b54cd9aec5f49566307df2b0cf23afcf6Craig Topper /// instruction that this IVStrideUse is representing. 56fed90b6d097d50881afb45e4d79f430db66dd741Dan Gohman Value *getOperandValToReplace() const { 57fed90b6d097d50881afb45e4d79f430db66dd741Dan Gohman return OperandValToReplace; 58fed90b6d097d50881afb45e4d79f430db66dd741Dan Gohman } 59fed90b6d097d50881afb45e4d79f430db66dd741Dan Gohman 60c3aae25116e66c177579b0b79182b09340b19753Chris Lattner /// setOperandValToReplace - Assign a new Value as the operand value 61bfdf7f38523bd38ae0538861a2bfd8bdc46e5c33Dale Johannesen /// to replace. 62bfdf7f38523bd38ae0538861a2bfd8bdc46e5c33Dale Johannesen void setOperandValToReplace(Value *Op) { 63bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng OperandValToReplace = Op; 64bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng } 65bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng 66fdb42fa5fe794cc2c89e2ed7f57a89ed24d9952aDale Johannesen /// getPostIncLoops - Return the set of loops for which the expression has 67fdb42fa5fe794cc2c89e2ed7f57a89ed24d9952aDale Johannesen /// been adjusted to use post-inc mode. 68fdb42fa5fe794cc2c89e2ed7f57a89ed24d9952aDale Johannesen const PostIncLoopSet &getPostIncLoops() const { 69fdb42fa5fe794cc2c89e2ed7f57a89ed24d9952aDale Johannesen return PostIncLoops; 70fdb42fa5fe794cc2c89e2ed7f57a89ed24d9952aDale Johannesen } 71fdb42fa5fe794cc2c89e2ed7f57a89ed24d9952aDale Johannesen 72bfdf7f38523bd38ae0538861a2bfd8bdc46e5c33Dale Johannesen /// transformToPostInc - Transform the expression to post-inc form for the 73bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng /// given loop. 74fdb42fa5fe794cc2c89e2ed7f57a89ed24d9952aDale Johannesen void transformToPostInc(const Loop *L); 75d4c6c3a7c3140ce487a805138b6f53f82ff6b783Devang Patel 76bfdf7f38523bd38ae0538861a2bfd8bdc46e5c33Dale Johannesenprivate: 77001d3dc976d7cda8a3dd8c7fd4020b0b96033f4eCraig Topper /// Parent - a pointer to the IVUsers that owns this IVStrideUse. 78001d3dc976d7cda8a3dd8c7fd4020b0b96033f4eCraig Topper IVUsers *Parent; 79bfdf7f38523bd38ae0538861a2bfd8bdc46e5c33Dale Johannesen 80bfdf7f38523bd38ae0538861a2bfd8bdc46e5c33Dale Johannesen /// OperandValToReplace - The Value of the operand in the user instruction 81bfdf7f38523bd38ae0538861a2bfd8bdc46e5c33Dale Johannesen /// that this IVStrideUse is representing. 82fdb42fa5fe794cc2c89e2ed7f57a89ed24d9952aDale Johannesen WeakVH OperandValToReplace; 83fdb42fa5fe794cc2c89e2ed7f57a89ed24d9952aDale Johannesen 84fdb42fa5fe794cc2c89e2ed7f57a89ed24d9952aDale Johannesen /// PostIncLoops - The set of loops for which Expr has been adjusted to 85fdb42fa5fe794cc2c89e2ed7f57a89ed24d9952aDale Johannesen /// use post-inc mode. This corresponds with SCEVExpander's post-inc concept. 86bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng PostIncLoopSet PostIncLoops; 87d4c6c3a7c3140ce487a805138b6f53f82ff6b783Devang Patel 88bfdf7f38523bd38ae0538861a2bfd8bdc46e5c33Dale Johannesen /// Deleted - Implementation of CallbackVH virtual function to 89bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng /// receive notification when the User is deleted. 90bfdf7f38523bd38ae0538861a2bfd8bdc46e5c33Dale Johannesen virtual void deleted(); 91d4c6c3a7c3140ce487a805138b6f53f82ff6b783Devang Patel}; 92bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng 93fdb42fa5fe794cc2c89e2ed7f57a89ed24d9952aDale Johannesentemplate<> struct ilist_traits<IVStrideUse> 94bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng : public ilist_default_traits<IVStrideUse> { 95bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng // createSentinel is used to get hold of a node that marks the end of 96bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng // the list... 97fdb42fa5fe794cc2c89e2ed7f57a89ed24d9952aDale Johannesen // The sentinel is relative to this instance, so we use a non-static 98bfdf7f38523bd38ae0538861a2bfd8bdc46e5c33Dale Johannesen // method. 99bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng IVStrideUse *createSentinel() const { 10022a54c1cd711afccd4558374918d12a939e1cca5Benjamin Kramer // since i(p)lists always publicly derive from the corresponding 10122a54c1cd711afccd4558374918d12a939e1cca5Benjamin Kramer // traits, placing a data member in this class will augment i(p)list. 10222a54c1cd711afccd4558374918d12a939e1cca5Benjamin Kramer // But since the NodeTy is expected to publicly derive from 10322a54c1cd711afccd4558374918d12a939e1cca5Benjamin Kramer // ilist_node<NodeTy>, there is a legal viable downcast from it 10422a54c1cd711afccd4558374918d12a939e1cca5Benjamin Kramer // to NodeTy. We use this trick to superpose i(p)list with a "ghostly" 10522a54c1cd711afccd4558374918d12a939e1cca5Benjamin Kramer // NodeTy, which becomes the sentinel. Dereferencing the sentinel is 106bfdf7f38523bd38ae0538861a2bfd8bdc46e5c33Dale Johannesen // forbidden (save the ilist_node<NodeTy>) so no one will ever notice 107bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng // the superposition. 108bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng return static_cast<IVStrideUse*>(&Sentinel); 109bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng } 110bfcb3051899b7141a946d769fcf6e8a8453bc530Evan Cheng static void destroySentinel(IVStrideUse*) {} 111fdb42fa5fe794cc2c89e2ed7f57a89ed24d9952aDale Johannesen 112fdb42fa5fe794cc2c89e2ed7f57a89ed24d9952aDale Johannesen IVStrideUse *provideInitialHead() const { return createSentinel(); } 113bfdf7f38523bd38ae0538861a2bfd8bdc46e5c33Dale Johannesen IVStrideUse *ensureHead(IVStrideUse*) const { return createSentinel(); } 114bfdf7f38523bd38ae0538861a2bfd8bdc46e5c33Dale Johannesen static void noteHead(IVStrideUse*, IVStrideUse*) {} 115cf495bc2e505e52ad018da55bed11c7b8bc97db5David Greene 116cf495bc2e505e52ad018da55bed11c7b8bc97db5David Greeneprivate: 117cf495bc2e505e52ad018da55bed11c7b8bc97db5David Greene mutable ilist_node<IVStrideUse> Sentinel; 118cf495bc2e505e52ad018da55bed11c7b8bc97db5David Greene}; 119c3aae25116e66c177579b0b79182b09340b19753Chris Lattner 120c3aae25116e66c177579b0b79182b09340b19753Chris Lattnerclass IVUsers : public LoopPass { 121c3aae25116e66c177579b0b79182b09340b19753Chris Lattner friend class IVStrideUse; 122c3aae25116e66c177579b0b79182b09340b19753Chris Lattner Loop *L; 123c3aae25116e66c177579b0b79182b09340b19753Chris Lattner LoopInfo *LI; 124c3aae25116e66c177579b0b79182b09340b19753Chris Lattner DominatorTree *DT; 125c3aae25116e66c177579b0b79182b09340b19753Chris Lattner ScalarEvolution *SE; 126c3aae25116e66c177579b0b79182b09340b19753Chris Lattner TargetData *TD; 127c3aae25116e66c177579b0b79182b09340b19753Chris Lattner SmallPtrSet<Instruction*,16> Processed; 128c3aae25116e66c177579b0b79182b09340b19753Chris Lattner 129cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner /// IVUses - A list of all tracked IV uses of induction variable expressions 130cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner /// we are interested in. 13150d2b1ac029d63500ea9b9347561b1454fa6ed6aDan Gohman ilist<IVStrideUse> IVUses; 132d858e90f039f5fcdc2fa93035e911a5a9505cc50Dan Gohman 133ff7a562751604a9fe13efc75bd59622244b54d35Dan Gohman virtual void getAnalysisUsage(AnalysisUsage &AU) const; 1347c3234c6be0dc0bdf4b5d6f848cd728a77f349d7Dan Gohman 135512063dd0f91a76b9dd904dfff72a52b4d09e89fChris Lattner virtual bool runOnLoop(Loop *L, LPPassManager &LPM); 1360508d047fefef36d4f943ee13c82c18cf3a943abDevang Patel 137cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner virtual void releaseMemory(); 138f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman 139f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohmanpublic: 140f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman static char ID; // Pass ID, replacement for typeid 141f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman IVUsers(); 142f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman 143cacf462915344c2af25eef1af1f3ee2c7280ff56Chris Lattner Loop *getLoop() const { return L; } 144213a16c637926bfc38ba373d3aba6778e181e3ecChris Lattner 145fed90b6d097d50881afb45e4d79f430db66dd741Dan Gohman /// AddUsersIfInteresting - Inspect the specified Instruction. If it is a 146fed90b6d097d50881afb45e4d79f430db66dd741Dan Gohman /// reducible SCEV, recursively add its users to the IVUsesByStride set and 147f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman /// return true. Otherwise, return false. 148f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman bool AddUsersIfInteresting(Instruction *I, 149f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman SmallPtrSet<Loop*,16> &SimpleLoopNests); 150f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman 151f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman IVStrideUse &AddUser(Instruction *User, Value *Operand); 152f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman 153f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman /// getReplacementExpr - Return a SCEV expression which computes the 154f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman /// value of the OperandValToReplace of the given IVStrideUse. 155691ef2ba066dda14ae4ac0ad645054fbc967785aAndrew Lenharth const SCEV *getReplacementExpr(const IVStrideUse &IU) const; 156213a16c637926bfc38ba373d3aba6778e181e3ecChris Lattner 157d23b33435ae722ff5aa5ab97135a4f31041959e2Bob Wilson /// getExpr - Return the expression for the use. 158583bd47f777fe3eb8305872fa0eadab31e833dffJim Laskey const SCEV *getExpr(const IVStrideUse &IU) const; 159213a16c637926bfc38ba373d3aba6778e181e3ecChris Lattner 160f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman const SCEV *getStride(const IVStrideUse &IU, const Loop *L) const; 161f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman 162f350b277f32d7d47f86c0e54f4aec4d470500618Dan Gohman typedef ilist<IVStrideUse>::iterator iterator; 163e8be6c63915e0389f1eef6b53c64300d13b2ce99Dan Gohman typedef ilist<IVStrideUse>::const_iterator const_iterator; 164e8be6c63915e0389f1eef6b53c64300d13b2ce99Dan Gohman iterator begin() { return IVUses.begin(); } 165e8be6c63915e0389f1eef6b53c64300d13b2ce99Dan Gohman iterator end() { return IVUses.end(); } 166e8be6c63915e0389f1eef6b53c64300d13b2ce99Dan Gohman const_iterator begin() const { return IVUses.begin(); } 167b4e6a5df5dada0cd919cc6e2717eb3118db9cc45Bill Wendling const_iterator end() const { return IVUses.end(); } 168b4e6a5df5dada0cd919cc6e2717eb3118db9cc45Bill Wendling bool empty() const { return IVUses.empty(); } 169b4e6a5df5dada0cd919cc6e2717eb3118db9cc45Bill Wendling 170819309efec6f11ba752bd7cbfe186495745f020bDaniel Dunbar bool isIVUserOrOperand(Instruction *Inst) const { 171bfdf7f38523bd38ae0538861a2bfd8bdc46e5c33Dale Johannesen return Processed.count(Inst); 172bfdf7f38523bd38ae0538861a2bfd8bdc46e5c33Dale Johannesen } 173bfdf7f38523bd38ae0538861a2bfd8bdc46e5c33Dale Johannesen 174bc7d448f242b1bbc1031fb87cd69c285ff9aaffaJakob Stoklund Olesen void print(raw_ostream &OS, const Module* = 0) const; 175bc7d448f242b1bbc1031fb87cd69c285ff9aaffaJakob Stoklund Olesen 176bc7d448f242b1bbc1031fb87cd69c285ff9aaffaJakob Stoklund Olesen /// dump - This method is used for debugging. 177bc7d448f242b1bbc1031fb87cd69c285ff9aaffaJakob Stoklund Olesen void dump() const; 178bc7d448f242b1bbc1031fb87cd69c285ff9aaffaJakob Stoklund Olesen}; 179bc7d448f242b1bbc1031fb87cd69c285ff9aaffaJakob Stoklund Olesen 180bc7d448f242b1bbc1031fb87cd69c285ff9aaffaJakob Stoklund OlesenPass *createIVUsersPass(); 181bc7d448f242b1bbc1031fb87cd69c285ff9aaffaJakob Stoklund Olesen 182bc7d448f242b1bbc1031fb87cd69c285ff9aaffaJakob Stoklund Olesen} 183bc7d448f242b1bbc1031fb87cd69c285ff9aaffaJakob Stoklund Olesen 184bc7d448f242b1bbc1031fb87cd69c285ff9aaffaJakob Stoklund Olesen#endif 185bc7d448f242b1bbc1031fb87cd69c285ff9aaffaJakob Stoklund Olesen