1 //===- PHITransAddr.h - PHI Translation for Addresses -----------*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file declares the PHITransAddr class. 10 // 11 //===----------------------------------------------------------------------===// 12 13 #ifndef LLVM_ANALYSIS_PHITRANSADDR_H 14 #define LLVM_ANALYSIS_PHITRANSADDR_H 15 16 #include "llvm/ADT/SmallVector.h" 17 #include "llvm/IR/Instruction.h" 18 19 namespace llvm { 20 class AssumptionCache; 21 class DominatorTree; 22 class DataLayout; 23 class TargetLibraryInfo; 24 25 /// PHITransAddr - An address value which tracks and handles phi translation. 26 /// As we walk "up" the CFG through predecessors, we need to ensure that the 27 /// address we're tracking is kept up to date. For example, if we're analyzing 28 /// an address of "&A[i]" and walk through the definition of 'i' which is a PHI 29 /// node, we *must* phi translate i to get "&A[j]" or else we will analyze an 30 /// incorrect pointer in the predecessor block. 31 /// 32 /// This is designed to be a relatively small object that lives on the stack and 33 /// is copyable. 34 /// 35 class PHITransAddr { 36 /// Addr - The actual address we're analyzing. 37 Value *Addr; 38 39 /// The DataLayout we are playing with. 40 const DataLayout &DL; 41 42 /// TLI - The target library info if known, otherwise null. 43 const TargetLibraryInfo *TLI = nullptr; 44 45 /// A cache of \@llvm.assume calls used by SimplifyInstruction. 46 AssumptionCache *AC; 47 48 /// InstInputs - The inputs for our symbolic address. 49 SmallVector<Instruction*, 4> InstInputs; 50 51 public: PHITransAddr(Value * Addr,const DataLayout & DL,AssumptionCache * AC)52 PHITransAddr(Value *Addr, const DataLayout &DL, AssumptionCache *AC) 53 : Addr(Addr), DL(DL), AC(AC) { 54 // If the address is an instruction, the whole thing is considered an input. 55 addAsInput(Addr); 56 } 57 getAddr()58 Value *getAddr() const { return Addr; } 59 60 /// needsPHITranslationFromBlock - Return true if moving from the specified 61 /// BasicBlock to its predecessors requires PHI translation. needsPHITranslationFromBlock(BasicBlock * BB)62 bool needsPHITranslationFromBlock(BasicBlock *BB) const { 63 // We do need translation if one of our input instructions is defined in 64 // this block. 65 return any_of(InstInputs, [BB](const auto &InstInput) { 66 return InstInput->getParent() == BB; 67 }); 68 } 69 70 /// isPotentiallyPHITranslatable - If this needs PHI translation, return true 71 /// if we have some hope of doing it. This should be used as a filter to 72 /// avoid calling PHITranslateValue in hopeless situations. 73 bool isPotentiallyPHITranslatable() const; 74 75 /// translateValue - PHI translate the current address up the CFG from 76 /// CurBB to Pred, updating our state to reflect any needed changes. If 77 /// 'MustDominate' is true, the translated value must dominate PredBB. 78 Value *translateValue(BasicBlock *CurBB, BasicBlock *PredBB, 79 const DominatorTree *DT, bool MustDominate); 80 81 /// translateWithInsertion - PHI translate this value into the specified 82 /// predecessor block, inserting a computation of the value if it is 83 /// unavailable. 84 /// 85 /// All newly created instructions are added to the NewInsts list. This 86 /// returns null on failure. 87 /// 88 Value *translateWithInsertion(BasicBlock *CurBB, BasicBlock *PredBB, 89 const DominatorTree &DT, 90 SmallVectorImpl<Instruction *> &NewInsts); 91 92 void dump() const; 93 94 /// verify - Check internal consistency of this data structure. If the 95 /// structure is valid, it returns true. If invalid, it prints errors and 96 /// returns false. 97 bool verify() const; 98 99 private: 100 Value *translateSubExpr(Value *V, BasicBlock *CurBB, BasicBlock *PredBB, 101 const DominatorTree *DT); 102 103 /// insertTranslatedSubExpr - Insert a computation of the PHI translated 104 /// version of 'V' for the edge PredBB->CurBB into the end of the PredBB 105 /// block. All newly created instructions are added to the NewInsts list. 106 /// This returns null on failure. 107 /// 108 Value *insertTranslatedSubExpr(Value *InVal, BasicBlock *CurBB, 109 BasicBlock *PredBB, const DominatorTree &DT, 110 SmallVectorImpl<Instruction *> &NewInsts); 111 112 /// addAsInput - If the specified value is an instruction, add it as an input. addAsInput(Value * V)113 Value *addAsInput(Value *V) { 114 // If V is an instruction, it is now an input. 115 if (Instruction *VI = dyn_cast<Instruction>(V)) 116 InstInputs.push_back(VI); 117 return V; 118 } 119 }; 120 121 } // end namespace llvm 122 123 #endif 124