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