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