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