diff options
| -rw-r--r-- | include/llvm/Analysis/PHITransAddr.h | 91 | ||||
| -rw-r--r-- | lib/Analysis/PHITransAddr.cpp | 71 |
2 files changed, 162 insertions, 0 deletions
diff --git a/include/llvm/Analysis/PHITransAddr.h b/include/llvm/Analysis/PHITransAddr.h new file mode 100644 index 0000000000..e19fb1c13f --- /dev/null +++ b/include/llvm/Analysis/PHITransAddr.h @@ -0,0 +1,91 @@ +//===- PHITransAddr.h - PHI Translation for Addresses -----------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file declares the PHITransAddr class. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ANALYSIS_PHITRANSADDR_H +#define LLVM_ANALYSIS_PHITRANSADDR_H + +#include "llvm/Instruction.h" +#include "llvm/ADT/SmallVector.h" + +namespace llvm { + class DominatorTree; + class TargetData; + +/// PHITransAddr - An address value which tracks and handles phi translation. +/// As we walk "up" the CFG through predecessors, we need to ensure that the +/// address we're tracking is kept up to date. For example, if we're analyzing +/// an address of "&A[i]" and walk through the definition of 'i' which is a PHI +/// node, we *must* phi translate i to get "&A[j]" or else we will analyze an +/// incorrect pointer in the predecessor block. +/// +/// This is designed to be a relatively small object that lives on the stack and +/// is copyable. +/// +class PHITransAddr { + /// Addr - The actual address we're analyzing. + Value *Addr; + + /// InstInputs - The inputs for our symbolic address. + SmallVector<Instruction*, 4> InstInputs; +public: + PHITransAddr(Value *addr) : Addr(addr) { + // If the address is an instruction, the whole thing is considered an input. + if (Instruction *I = dyn_cast<Instruction>(Addr)) + InstInputs.push_back(I); + } + + /// NeedsPHITranslationFromBlock - Return true if moving from the specified + /// BasicBlock to its predecessors requires PHI translation. + bool NeedsPHITranslationFromBlock(BasicBlock *BB) const { + // We do need translation if one of our input instructions is defined in + // this block. + for (unsigned i = 0, e = InstInputs.size(); i != e; ++i) + if (InstInputs[i]->getParent() == BB) + return true; + return false; + } + + /// IsPHITranslatable - If this needs PHI translation, return true if we have + /// some hope of doing it. This should be used as a filter to avoid calling + /// GetPHITranslatedValue in hopeless situations. + bool IsPHITranslatable() const; + + /// GetPHITranslatedValue - Given a computation that satisfied the + /// isPHITranslatable predicate, see if we can translate the computation into + /// the specified predecessor block. If so, return that value, otherwise + /// return null. + Value *GetPHITranslatedValue(Value *InVal, BasicBlock *CurBB, + BasicBlock *Pred, const TargetData *TD) const; + + /// GetAvailablePHITranslatePointer - Return the value computed by + /// PHITranslatePointer if it dominates PredBB, otherwise return null. + Value *GetAvailablePHITranslatedValue(Value *V, + BasicBlock *CurBB, BasicBlock *PredBB, + const TargetData *TD, + const DominatorTree &DT) const; + + /// InsertPHITranslatedPointer - Insert a computation of the PHI translated + /// version of 'V' for the edge PredBB->CurBB into the end of the PredBB + /// block. All newly created instructions are added to the NewInsts list. + /// This returns null on failure. + /// + Value *InsertPHITranslatedPointer(Value *InVal, BasicBlock *CurBB, + BasicBlock *PredBB, const TargetData *TD, + const DominatorTree &DT, + SmallVectorImpl<Instruction*> &NewInsts) const; + +}; + +} // end namespace llvm + +#endif diff --git a/lib/Analysis/PHITransAddr.cpp b/lib/Analysis/PHITransAddr.cpp new file mode 100644 index 0000000000..ce7eca5d27 --- /dev/null +++ b/lib/Analysis/PHITransAddr.cpp @@ -0,0 +1,71 @@ +//===- PHITransAddr.cpp - PHI Translation for Addresses -------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file implements the PHITransAddr class. +// +//===----------------------------------------------------------------------===// + +#include "llvm/Analysis/PHITransAddr.h" +#include "llvm/Analysis/Dominators.h" +using namespace llvm; + +/// IsPHITranslatable - If this needs PHI translation, return true if we have +/// some hope of doing it. This should be used as a filter to avoid calling +/// GetPHITranslatedValue in hopeless situations. +bool PHITransAddr::IsPHITranslatable() const { + return true; // not a good filter. +} + +/// GetPHITranslatedValue - Given a computation that satisfied the +/// isPHITranslatable predicate, see if we can translate the computation into +/// the specified predecessor block. If so, return that value, otherwise +/// return null. +Value *PHITransAddr::GetPHITranslatedValue(Value *InVal, BasicBlock *CurBB, + BasicBlock *Pred, + const TargetData *TD) const { + // Not a great implementation. + return 0; +} + +/// GetAvailablePHITranslatePointer - Return the value computed by +/// PHITranslatePointer if it dominates PredBB, otherwise return null. +Value *PHITransAddr:: +GetAvailablePHITranslatedValue(Value *V, + BasicBlock *CurBB, BasicBlock *PredBB, + const TargetData *TD, + const DominatorTree &DT) const { + // See if PHI translation succeeds. + V = GetPHITranslatedValue(V, CurBB, PredBB, TD); + if (V == 0) return 0; + + // Make sure the value is live in the predecessor. + if (Instruction *Inst = dyn_cast_or_null<Instruction>(V)) + if (!DT.dominates(Inst->getParent(), PredBB)) + return 0; + return V; +} + +/// InsertPHITranslatedPointer - Insert a computation of the PHI translated +/// version of 'V' for the edge PredBB->CurBB into the end of the PredBB +/// block. All newly created instructions are added to the NewInsts list. +/// This returns null on failure. +/// +Value *PHITransAddr:: +InsertPHITranslatedPointer(Value *InVal, BasicBlock *CurBB, + BasicBlock *PredBB, const TargetData *TD, + const DominatorTree &DT, + SmallVectorImpl<Instruction*> &NewInsts) const { + // See if we have a version of this value already available and dominating + // PredBB. If so, there is no need to insert a new copy. + if (Value *Res = GetAvailablePHITranslatedValue(InVal, CurBB, PredBB, TD, DT)) + return Res; + + // Not a great implementation. + return 0; +} |