1 //===- SelectionDAGAddressAnalysis.h - DAG Address Analysis -----*- 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 #ifndef LLVM_CODEGEN_SELECTIONDAGADDRESSANALYSIS_H 10 #define LLVM_CODEGEN_SELECTIONDAGADDRESSANALYSIS_H 11 12 #include "llvm/Analysis/MemoryLocation.h" 13 #include "llvm/CodeGen/SelectionDAGNodes.h" 14 #include <cstdint> 15 16 namespace llvm { 17 18 class SelectionDAG; 19 20 /// Helper struct to parse and store a memory address as base + index + offset. 21 /// We ignore sign extensions when it is safe to do so. 22 /// The following two expressions are not equivalent. To differentiate we need 23 /// to store whether there was a sign extension involved in the index 24 /// computation. 25 /// (load (i64 add (i64 copyfromreg %c) 26 /// (i64 signextend (add (i8 load %index) 27 /// (i8 1)))) 28 /// vs 29 /// 30 /// (load (i64 add (i64 copyfromreg %c) 31 /// (i64 signextend (i32 add (i32 signextend (i8 load %index)) 32 /// (i32 1))))) 33 class BaseIndexOffset { 34 private: 35 SDValue Base; 36 SDValue Index; 37 std::optional<int64_t> Offset; 38 bool IsIndexSignExt = false; 39 40 public: 41 BaseIndexOffset() = default; BaseIndexOffset(SDValue Base,SDValue Index,bool IsIndexSignExt)42 BaseIndexOffset(SDValue Base, SDValue Index, bool IsIndexSignExt) 43 : Base(Base), Index(Index), IsIndexSignExt(IsIndexSignExt) {} BaseIndexOffset(SDValue Base,SDValue Index,int64_t Offset,bool IsIndexSignExt)44 BaseIndexOffset(SDValue Base, SDValue Index, int64_t Offset, 45 bool IsIndexSignExt) 46 : Base(Base), Index(Index), Offset(Offset), 47 IsIndexSignExt(IsIndexSignExt) {} 48 getBase()49 SDValue getBase() { return Base; } getBase()50 SDValue getBase() const { return Base; } getIndex()51 SDValue getIndex() { return Index; } getIndex()52 SDValue getIndex() const { return Index; } addToOffset(int64_t VectorOff)53 void addToOffset(int64_t VectorOff) { 54 Offset = Offset.value_or(0) + VectorOff; 55 } hasValidOffset()56 bool hasValidOffset() const { return Offset.has_value(); } getOffset()57 int64_t getOffset() const { return *Offset; } 58 59 // Returns true if `Other` and `*this` are both some offset from the same base 60 // pointer. In that case, `Off` is set to the offset between `*this` and 61 // `Other` (negative if `Other` is before `*this`). 62 bool equalBaseIndex(const BaseIndexOffset &Other, const SelectionDAG &DAG, 63 int64_t &Off) const; 64 equalBaseIndex(const BaseIndexOffset & Other,const SelectionDAG & DAG)65 bool equalBaseIndex(const BaseIndexOffset &Other, 66 const SelectionDAG &DAG) const { 67 int64_t Off; 68 return equalBaseIndex(Other, DAG, Off); 69 } 70 71 // Returns true if `Other` (with size `OtherSize`) can be proven to be fully 72 // contained in `*this` (with size `Size`). 73 bool contains(const SelectionDAG &DAG, int64_t BitSize, 74 const BaseIndexOffset &Other, int64_t OtherBitSize, 75 int64_t &BitOffset) const; 76 contains(const SelectionDAG & DAG,int64_t BitSize,const BaseIndexOffset & Other,int64_t OtherBitSize)77 bool contains(const SelectionDAG &DAG, int64_t BitSize, 78 const BaseIndexOffset &Other, int64_t OtherBitSize) const { 79 int64_t BitOffset; 80 return contains(DAG, BitSize, Other, OtherBitSize, BitOffset); 81 } 82 83 // Returns true `Op0` and `Op1` can be proven to alias/not alias, in 84 // which case `IsAlias` is set to true/false. 85 static bool computeAliasing(const SDNode *Op0, const LocationSize NumBytes0, 86 const SDNode *Op1, const LocationSize NumBytes1, 87 const SelectionDAG &DAG, bool &IsAlias); 88 89 /// Parses tree in N for base, index, offset addresses. 90 static BaseIndexOffset match(const SDNode *N, const SelectionDAG &DAG); 91 92 void print(raw_ostream& OS) const; 93 void dump() const; 94 }; 95 96 } // end namespace llvm 97 98 #endif // LLVM_CODEGEN_SELECTIONDAGADDRESSANALYSIS_H 99