PHITransAddr.h revision 7dedbf4ce3e1b62b4e0b000b38d244b50029c315
15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//===- PHITransAddr.h - PHI Translation for Addresses -----------*- C++ -*-===// 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// The LLVM Compiler Infrastructure 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// This file is distributed under the University of Illinois Open Source 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// License. See LICENSE.TXT for details. 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 8c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)//===----------------------------------------------------------------------===// 9c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)// 10c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)// This file declares the PHITransAddr class. 11c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)// 12c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)//===----------------------------------------------------------------------===// 13c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 142a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#ifndef LLVM_ANALYSIS_PHITRANSADDR_H 155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define LLVM_ANALYSIS_PHITRANSADDR_H 165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "llvm/Instruction.h" 185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "llvm/ADT/SmallVector.h" 195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 20c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)namespace llvm { 21c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) class DominatorTree; 22c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) class TargetData; 23c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 24c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)/// PHITransAddr - An address value which tracks and handles phi translation. 25c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)/// As we walk "up" the CFG through predecessors, we need to ensure that the 26c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)/// address we're tracking is kept up to date. For example, if we're analyzing 27c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)/// an address of "&A[i]" and walk through the definition of 'i' which is a PHI 28c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)/// node, we *must* phi translate i to get "&A[j]" or else we will analyze an 29c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)/// incorrect pointer in the predecessor block. 30c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)/// 31c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)/// This is designed to be a relatively small object that lives on the stack and 32c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)/// is copyable. 33c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)/// 34c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)class PHITransAddr { 35c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) /// Addr - The actual address we're analyzing. 36c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) Value *Addr; 37c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 38c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) /// TD - The target data we are playing with if known, otherwise null. 39c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) const TargetData *TD; 40c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 41c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) /// InstInputs - The inputs for our symbolic address. 42c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) SmallVector<Instruction*, 4> InstInputs; 43c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)public: 44c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) PHITransAddr(Value *addr, const TargetData *td) : Addr(addr), TD(td) { 45c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // If the address is an instruction, the whole thing is considered an input. 46c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) if (Instruction *I = dyn_cast<Instruction>(Addr)) 47c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) InstInputs.push_back(I); 48c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) } 49c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 50c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) Value *getAddr() const { return Addr; } 51c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 52c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) /// NeedsPHITranslationFromBlock - Return true if moving from the specified 53c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) /// BasicBlock to its predecessors requires PHI translation. 54c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) bool NeedsPHITranslationFromBlock(BasicBlock *BB) const { 55c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // We do need translation if one of our input instructions is defined in 56c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // this block. 57c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) for (unsigned i = 0, e = InstInputs.size(); i != e; ++i) 58c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) if (InstInputs[i]->getParent() == BB) 59c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) return true; 60c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) return false; 61c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) } 62c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 63c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) /// IsPotentiallyPHITranslatable - If this needs PHI translation, return true 645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// if we have some hope of doing it. This should be used as a filter to 655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// avoid calling PHITranslateValue in hopeless situations. 665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool IsPotentiallyPHITranslatable() const; 67c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 68c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) /// PHITranslateValue - PHI translate the current address up the CFG from 695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// CurBB to Pred, updating our state the reflect any needed changes. This 705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /// 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. Though it 87 /// claims to return a bool, it actually aborts on error and always returns 88 /// true. 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