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