IVUsers.h revision f85092c25525f75eef6982ffa40c9b48b87da987
1//===- llvm/Analysis/IVUsers.h - Induction Variable Users -------*- C++ -*-===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file implements bookkeeping for "interesting" users of expressions 11// computed from induction variables. 12// 13//===----------------------------------------------------------------------===// 14 15#ifndef LLVM_ANALYSIS_IVUSERS_H 16#define LLVM_ANALYSIS_IVUSERS_H 17 18#include "llvm/Analysis/LoopPass.h" 19#include "llvm/Analysis/ScalarEvolutionNormalization.h" 20#include "llvm/Support/ValueHandle.h" 21 22namespace llvm { 23 24class DominatorTree; 25class Instruction; 26class Value; 27class IVUsers; 28class ScalarEvolution; 29class SCEV; 30class IVUsers; 31class TargetData; 32 33/// IVStrideUse - Keep track of one use of a strided induction variable. 34/// The Expr member keeps track of the expression, User is the actual user 35/// instruction of the operand, and 'OperandValToReplace' is the operand of 36/// the User that is the use. 37class IVStrideUse : public CallbackVH, public ilist_node<IVStrideUse> { 38 friend class IVUsers; 39public: 40 IVStrideUse(IVUsers *P, Instruction* U, Value *O, Value *PN) 41 : CallbackVH(U), Parent(P), OperandValToReplace(O), Phi(PN) { 42 } 43 44 /// getUser - Return the user instruction for this use. 45 Instruction *getUser() const { 46 return cast<Instruction>(getValPtr()); 47 } 48 49 /// setUser - Assign a new user instruction for this use. 50 void setUser(Instruction *NewUser) { 51 setValPtr(NewUser); 52 } 53 54 /// getPhi - Return the phi node that represents this IV. 55 PHINode *getPhi() const { 56 return cast<PHINode>(Phi); 57 } 58 59 /// getOperandValToReplace - Return the Value of the operand in the user 60 /// instruction that this IVStrideUse is representing. 61 Value *getOperandValToReplace() const { 62 return OperandValToReplace; 63 } 64 65 /// setOperandValToReplace - Assign a new Value as the operand value 66 /// to replace. 67 void setOperandValToReplace(Value *Op) { 68 OperandValToReplace = Op; 69 } 70 71 /// getPostIncLoops - Return the set of loops for which the expression has 72 /// been adjusted to use post-inc mode. 73 const PostIncLoopSet &getPostIncLoops() const { 74 return PostIncLoops; 75 } 76 77 /// transformToPostInc - Transform the expression to post-inc form for the 78 /// given loop. 79 void transformToPostInc(const Loop *L); 80 81private: 82 /// Parent - a pointer to the IVUsers that owns this IVStrideUse. 83 IVUsers *Parent; 84 85 /// OperandValToReplace - The Value of the operand in the user instruction 86 /// that this IVStrideUse is representing. 87 WeakVH OperandValToReplace; 88 89 /// Phi - The loop header phi that represents this IV. 90 WeakVH Phi; 91 92 /// PostIncLoops - The set of loops for which Expr has been adjusted to 93 /// use post-inc mode. This corresponds with SCEVExpander's post-inc concept. 94 PostIncLoopSet PostIncLoops; 95 96 /// Deleted - Implementation of CallbackVH virtual function to 97 /// receive notification when the User is deleted. 98 virtual void deleted(); 99}; 100 101template<> struct ilist_traits<IVStrideUse> 102 : public ilist_default_traits<IVStrideUse> { 103 // createSentinel is used to get hold of a node that marks the end of 104 // the list... 105 // The sentinel is relative to this instance, so we use a non-static 106 // method. 107 IVStrideUse *createSentinel() const { 108 // since i(p)lists always publicly derive from the corresponding 109 // traits, placing a data member in this class will augment i(p)list. 110 // But since the NodeTy is expected to publicly derive from 111 // ilist_node<NodeTy>, there is a legal viable downcast from it 112 // to NodeTy. We use this trick to superpose i(p)list with a "ghostly" 113 // NodeTy, which becomes the sentinel. Dereferencing the sentinel is 114 // forbidden (save the ilist_node<NodeTy>) so no one will ever notice 115 // the superposition. 116 return static_cast<IVStrideUse*>(&Sentinel); 117 } 118 static void destroySentinel(IVStrideUse*) {} 119 120 IVStrideUse *provideInitialHead() const { return createSentinel(); } 121 IVStrideUse *ensureHead(IVStrideUse*) const { return createSentinel(); } 122 static void noteHead(IVStrideUse*, IVStrideUse*) {} 123 124private: 125 mutable ilist_node<IVStrideUse> Sentinel; 126}; 127 128class IVUsers : public LoopPass { 129 friend class IVStrideUse; 130 Loop *L; 131 LoopInfo *LI; 132 DominatorTree *DT; 133 ScalarEvolution *SE; 134 TargetData *TD; 135 SmallPtrSet<Instruction*,16> Processed; 136 137 /// IVUses - A list of all tracked IV uses of induction variable expressions 138 /// we are interested in. 139 ilist<IVStrideUse> IVUses; 140 141 virtual void getAnalysisUsage(AnalysisUsage &AU) const; 142 143 virtual bool runOnLoop(Loop *L, LPPassManager &LPM); 144 145 virtual void releaseMemory(); 146 147public: 148 static char ID; // Pass ID, replacement for typeid 149 IVUsers(); 150 151 /// AddUsersIfInteresting - Inspect the specified Instruction. If it is a 152 /// reducible SCEV, recursively add its users to the IVUsesByStride set and 153 /// return true. Otherwise, return false. 154 bool AddUsersIfInteresting(Instruction *I, PHINode *Phi); 155 156 IVStrideUse &AddUser(Instruction *User, Value *Operand, PHINode *Phi); 157 158 /// getReplacementExpr - Return a SCEV expression which computes the 159 /// value of the OperandValToReplace of the given IVStrideUse. 160 const SCEV *getReplacementExpr(const IVStrideUse &IU) const; 161 162 /// getExpr - Return the expression for the use. 163 const SCEV *getExpr(const IVStrideUse &IU) const; 164 165 const SCEV *getStride(const IVStrideUse &IU, const Loop *L) const; 166 167 typedef ilist<IVStrideUse>::iterator iterator; 168 typedef ilist<IVStrideUse>::const_iterator const_iterator; 169 iterator begin() { return IVUses.begin(); } 170 iterator end() { return IVUses.end(); } 171 const_iterator begin() const { return IVUses.begin(); } 172 const_iterator end() const { return IVUses.end(); } 173 bool empty() const { return IVUses.empty(); } 174 175 void print(raw_ostream &OS, const Module* = 0) const; 176 177 /// dump - This method is used for debugging. 178 void dump() const; 179}; 180 181Pass *createIVUsersPass(); 182 183} 184 185#endif 186