Line data    Source code

       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     1403254 :       : Addr(addr), DL(DL), TLI(nullptr), AC(AC) {
      55             :     // If the address is an instruction, the whole thing is considered an input.
      56      354512 :     if (Instruction *I = dyn_cast<Instruction>(Addr))
      57      354512 :       InstInputs.push_back(I);
      58             :   }
      59             : 
      60           0 :   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     4391178 :     for (unsigned i = 0, e = InstInputs.size(); i != e; ++i)
      68      683138 :       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       19671 :     if (Instruction *VI = dyn_cast<Instruction>(V))
     120       19671 :       InstInputs.push_back(VI);
     121             :     return V;
     122             :   }
     123             : };
     124             : 
     125             : } // end namespace llvm
     126             : 
     127             : #endif