1210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner//===- PHITransAddr.h - PHI Translation for Addresses -----------*- C++ -*-===// 2210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner// 3210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner// The LLVM Compiler Infrastructure 4210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner// 5210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner// This file is distributed under the University of Illinois Open Source 6210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner// License. See LICENSE.TXT for details. 7210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner// 8210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner//===----------------------------------------------------------------------===// 9210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner// 10210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner// This file declares the PHITransAddr class. 11210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner// 12210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner//===----------------------------------------------------------------------===// 13210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner 14210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner#ifndef LLVM_ANALYSIS_PHITRANSADDR_H 15210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner#define LLVM_ANALYSIS_PHITRANSADDR_H 16210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner 17210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner#include "llvm/ADT/SmallVector.h" 180b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Instruction.h" 19210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner 20210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattnernamespace llvm { 21210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner class DominatorTree; 223574eca1b02600bac4e625297f4ecf745f4c4f32Micah Villmow class DataLayout; 23618c1dbd293d15ee19f61b1156ab8086ad28311aChad Rosier class TargetLibraryInfo; 24618c1dbd293d15ee19f61b1156ab8086ad28311aChad Rosier 25210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner/// PHITransAddr - An address value which tracks and handles phi translation. 26210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner/// As we walk "up" the CFG through predecessors, we need to ensure that the 27210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner/// address we're tracking is kept up to date. For example, if we're analyzing 28210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner/// an address of "&A[i]" and walk through the definition of 'i' which is a PHI 29210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner/// node, we *must* phi translate i to get "&A[j]" or else we will analyze an 30210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner/// incorrect pointer in the predecessor block. 31210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner/// 32210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner/// This is designed to be a relatively small object that lives on the stack and 33210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner/// is copyable. 34210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner/// 35210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattnerclass PHITransAddr { 36210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner /// Addr - The actual address we're analyzing. 37210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner Value *Addr; 38210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner 3936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// The DataLayout we are playing with if known, otherwise null. 4036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const DataLayout *DL; 41618c1dbd293d15ee19f61b1156ab8086ad28311aChad Rosier 42618c1dbd293d15ee19f61b1156ab8086ad28311aChad Rosier /// TLI - The target library info if known, otherwise null. 43618c1dbd293d15ee19f61b1156ab8086ad28311aChad Rosier const TargetLibraryInfo *TLI; 449a8641201b2db8427be2a6531c043f384562c081Chris Lattner 45210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner /// InstInputs - The inputs for our symbolic address. 46210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner SmallVector<Instruction*, 4> InstInputs; 47210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattnerpublic: 48dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines PHITransAddr(Value *addr, const DataLayout *DL) 49dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines : Addr(addr), DL(DL), TLI(nullptr) { 50210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner // If the address is an instruction, the whole thing is considered an input. 51210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner if (Instruction *I = dyn_cast<Instruction>(Addr)) 52210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner InstInputs.push_back(I); 53210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner } 54210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner 55e05a188cd630448cc25143ee8e69a36ab2e69544Chris Lattner Value *getAddr() const { return Addr; } 56e05a188cd630448cc25143ee8e69a36ab2e69544Chris Lattner 57210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner /// NeedsPHITranslationFromBlock - Return true if moving from the specified 58210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner /// BasicBlock to its predecessors requires PHI translation. 59210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner bool NeedsPHITranslationFromBlock(BasicBlock *BB) const { 60210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner // We do need translation if one of our input instructions is defined in 61210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner // this block. 62210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner for (unsigned i = 0, e = InstInputs.size(); i != e; ++i) 63210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner if (InstInputs[i]->getParent() == BB) 64210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner return true; 65210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner return false; 66210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner } 67210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner 689a8641201b2db8427be2a6531c043f384562c081Chris Lattner /// IsPotentiallyPHITranslatable - If this needs PHI translation, return true 699a8641201b2db8427be2a6531c043f384562c081Chris Lattner /// if we have some hope of doing it. This should be used as a filter to 709a8641201b2db8427be2a6531c043f384562c081Chris Lattner /// avoid calling PHITranslateValue in hopeless situations. 719a8641201b2db8427be2a6531c043f384562c081Chris Lattner bool IsPotentiallyPHITranslatable() const; 729a8641201b2db8427be2a6531c043f384562c081Chris Lattner 739a8641201b2db8427be2a6531c043f384562c081Chris Lattner /// PHITranslateValue - PHI translate the current address up the CFG from 746d8f2ca646bc283c31f48b6816d5194c836dfec6Daniel Dunbar /// CurBB to Pred, updating our state to reflect any needed changes. If the 756d8f2ca646bc283c31f48b6816d5194c836dfec6Daniel Dunbar /// dominator tree DT is non-null, the translated value must dominate 766d8f2ca646bc283c31f48b6816d5194c836dfec6Daniel Dunbar /// PredBB. This returns true on failure and sets Addr to null. 776d8f2ca646bc283c31f48b6816d5194c836dfec6Daniel Dunbar bool PHITranslateValue(BasicBlock *CurBB, BasicBlock *PredBB, 786d8f2ca646bc283c31f48b6816d5194c836dfec6Daniel Dunbar const DominatorTree *DT); 799a8641201b2db8427be2a6531c043f384562c081Chris Lattner 809a8641201b2db8427be2a6531c043f384562c081Chris Lattner /// PHITranslateWithInsertion - PHI translate this value into the specified 819a8641201b2db8427be2a6531c043f384562c081Chris Lattner /// predecessor block, inserting a computation of the value if it is 829a8641201b2db8427be2a6531c043f384562c081Chris Lattner /// unavailable. 839a8641201b2db8427be2a6531c043f384562c081Chris Lattner /// 849a8641201b2db8427be2a6531c043f384562c081Chris Lattner /// All newly created instructions are added to the NewInsts list. This 859a8641201b2db8427be2a6531c043f384562c081Chris Lattner /// returns null on failure. 869a8641201b2db8427be2a6531c043f384562c081Chris Lattner /// 879a8641201b2db8427be2a6531c043f384562c081Chris Lattner Value *PHITranslateWithInsertion(BasicBlock *CurBB, BasicBlock *PredBB, 889a8641201b2db8427be2a6531c043f384562c081Chris Lattner const DominatorTree &DT, 899a8641201b2db8427be2a6531c043f384562c081Chris Lattner SmallVectorImpl<Instruction*> &NewInsts); 907dedbf4ce3e1b62b4e0b000b38d244b50029c315Chris Lattner 917dedbf4ce3e1b62b4e0b000b38d244b50029c315Chris Lattner void dump() const; 927dedbf4ce3e1b62b4e0b000b38d244b50029c315Chris Lattner 93af50315a29600188a6ff8b935beca6f1b59edf48Chris Lattner /// Verify - Check internal consistency of this data structure. If the 94af50315a29600188a6ff8b935beca6f1b59edf48Chris Lattner /// structure is valid, it returns true. If invalid, it prints errors and 95af50315a29600188a6ff8b935beca6f1b59edf48Chris Lattner /// returns false. 967dedbf4ce3e1b62b4e0b000b38d244b50029c315Chris Lattner bool Verify() const; 979a8641201b2db8427be2a6531c043f384562c081Chris Lattnerprivate: 986d8f2ca646bc283c31f48b6816d5194c836dfec6Daniel Dunbar Value *PHITranslateSubExpr(Value *V, BasicBlock *CurBB, BasicBlock *PredBB, 996d8f2ca646bc283c31f48b6816d5194c836dfec6Daniel Dunbar const DominatorTree *DT); 100210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner 1019a8641201b2db8427be2a6531c043f384562c081Chris Lattner /// InsertPHITranslatedSubExpr - Insert a computation of the PHI translated 102210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner /// version of 'V' for the edge PredBB->CurBB into the end of the PredBB 103210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner /// block. All newly created instructions are added to the NewInsts list. 104210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner /// This returns null on failure. 105210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner /// 1069a8641201b2db8427be2a6531c043f384562c081Chris Lattner Value *InsertPHITranslatedSubExpr(Value *InVal, BasicBlock *CurBB, 1079a8641201b2db8427be2a6531c043f384562c081Chris Lattner BasicBlock *PredBB, const DominatorTree &DT, 1089a8641201b2db8427be2a6531c043f384562c081Chris Lattner SmallVectorImpl<Instruction*> &NewInsts); 10943678f41a37c077f28517c2e4889cca88cada6ceChris Lattner 1106200e53f55536f812153ad910e6a69139592301bChris Lattner /// AddAsInput - If the specified value is an instruction, add it as an input. 1116200e53f55536f812153ad910e6a69139592301bChris Lattner Value *AddAsInput(Value *V) { 1126200e53f55536f812153ad910e6a69139592301bChris Lattner // If V is an instruction, it is now an input. 1136200e53f55536f812153ad910e6a69139592301bChris Lattner if (Instruction *VI = dyn_cast<Instruction>(V)) 1146200e53f55536f812153ad910e6a69139592301bChris Lattner InstInputs.push_back(VI); 1156200e53f55536f812153ad910e6a69139592301bChris Lattner return V; 1166200e53f55536f812153ad910e6a69139592301bChris Lattner } 1177dedbf4ce3e1b62b4e0b000b38d244b50029c315Chris Lattner 118210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner}; 119210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner 120210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner} // end namespace llvm 121210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner 122210e45af3a579beeefb001c8f13c94e80407aad5Chris Lattner#endif 123