Home | History | Annotate | Download | only in Analysis 
      1 //===- PHITransAddr.h - PHI Translation for Addresses -----------*- 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 declares the PHITransAddr class.
     11 //
     12 //===----------------------------------------------------------------------===//
     13 
     14 #ifndef LLVM_ANALYSIS_PHITRANSADDR_H
     15 #define LLVM_ANALYSIS_PHITRANSADDR_H
     16 
     17 #include "llvm/ADT/SmallVector.h"
     18 #include "llvm/IR/Instruction.h"
     19 
     20 namespace llvm {
     21   class AssumptionCache;
     22   class DominatorTree;
     23   class DataLayout;
     24   class TargetLibraryInfo;
     25 
     26 /// PHITransAddr - An address value which tracks and handles phi translation.
     27 /// As we walk "up" the CFG through predecessors, we need to ensure that the
     28 /// address we're tracking is kept up to date.  For example, if we're analyzing
     29 /// an address of "&A[i]" and walk through the definition of 'i' which is a PHI
     30 /// node, we *must* phi translate i to get "&A[j]" or else we will analyze an
     31 /// incorrect pointer in the predecessor block.
     32 ///
     33 /// This is designed to be a relatively small object that lives on the stack and
     34 /// is copyable.
     35 ///
     36 class PHITransAddr {
     37   /// Addr - The actual address we're analyzing.
     38   Value *Addr;
     39 
     40   /// The DataLayout we are playing with.
     41   const DataLayout &DL;
     42 
     43   /// TLI - The target library info if known, otherwise null.
     44   const TargetLibraryInfo *TLI;
     45 
     46   /// A cache of @llvm.assume calls used by SimplifyInstruction.
     47   AssumptionCache *AC;
     48 
     49   /// InstInputs - The inputs for our symbolic address.
     50   SmallVector<Instruction*, 4> InstInputs;
     51 
     52 public:
     53   PHITransAddr(Value *addr, const DataLayout &DL, AssumptionCache *AC)
     54       : Addr(addr), DL(DL), TLI(nullptr), AC(AC) {
     55     // If the address is an instruction, the whole thing is considered an input.
     56     if (Instruction *I = dyn_cast<Instruction>(Addr))
     57       InstInputs.push_back(I);
     58   }
     59 
     60   Value *getAddr() const { return Addr; }
     61 
     62   /// NeedsPHITranslationFromBlock - Return true if moving from the specified
     63   /// BasicBlock to its predecessors requires PHI translation.
     64   bool NeedsPHITranslationFromBlock(BasicBlock *BB) const {
     65     // We do need translation if one of our input instructions is defined in
     66     // this block.
     67     for (unsigned i = 0, e = InstInputs.size(); i != e; ++i)
     68       if (InstInputs[i]->getParent() == BB)
     69         return true;
     70     return false;
     71   }
     72 
     73   /// IsPotentiallyPHITranslatable - If this needs PHI translation, return true
     74   /// if we have some hope of doing it.  This should be used as a filter to
     75   /// avoid calling PHITranslateValue in hopeless situations.
     76   bool IsPotentiallyPHITranslatable() const;
     77 
     78   /// PHITranslateValue - PHI translate the current address up the CFG from
     79   /// CurBB to Pred, updating our state to reflect any needed changes.  If
     80   /// 'MustDominate' is true, the translated value must dominate
     81   /// PredBB.  This returns true on failure and sets Addr to null.
     82   bool PHITranslateValue(BasicBlock *CurBB, BasicBlock *PredBB,
     83                          const DominatorTree *DT, bool MustDominate);
     84 
     85   /// PHITranslateWithInsertion - PHI translate this value into the specified
     86   /// predecessor block, inserting a computation of the value if it is
     87   /// unavailable.
     88   ///
     89   /// All newly created instructions are added to the NewInsts list.  This
     90   /// returns null on failure.
     91   ///
     92   Value *PHITranslateWithInsertion(BasicBlock *CurBB, BasicBlock *PredBB,
     93                                    const DominatorTree &DT,
     94                                    SmallVectorImpl<Instruction *> &NewInsts);
     95 
     96   void dump() const;
     97 
     98   /// Verify - Check internal consistency of this data structure.  If the
     99   /// structure is valid, it returns true.  If invalid, it prints errors and
    100   /// returns false.
    101   bool Verify() const;
    102 
    103 private:
    104   Value *PHITranslateSubExpr(Value *V, BasicBlock *CurBB, BasicBlock *PredBB,
    105                              const DominatorTree *DT);
    106 
    107   /// InsertPHITranslatedSubExpr - Insert a computation of the PHI translated
    108   /// version of 'V' for the edge PredBB->CurBB into the end of the PredBB
    109   /// block.  All newly created instructions are added to the NewInsts list.
    110   /// This returns null on failure.
    111   ///
    112   Value *InsertPHITranslatedSubExpr(Value *InVal, BasicBlock *CurBB,
    113                                     BasicBlock *PredBB, const DominatorTree &DT,
    114                                     SmallVectorImpl<Instruction *> &NewInsts);
    115 
    116   /// AddAsInput - If the specified value is an instruction, add it as an input.
    117   Value *AddAsInput(Value *V) {
    118     // If V is an instruction, it is now an input.
    119     if (Instruction *VI = dyn_cast<Instruction>(V))
    120       InstInputs.push_back(VI);
    121     return V;
    122   }
    123 };
    124 
    125 } // end namespace llvm
    126 
    127 #endif
    128