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