LLVM  14.0.0git
SelectionDAGAddressAnalysis.h
Go to the documentation of this file.
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 
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)))))
33 private:
34  SDValue Base;
35  SDValue Index;
36  Optional<int64_t> Offset;
37  bool IsIndexSignExt = false;
38 
39 public:
40  BaseIndexOffset() = default;
41  BaseIndexOffset(SDValue Base, SDValue Index, bool IsIndexSignExt)
42  : Base(Base), Index(Index), Offset(), IsIndexSignExt(IsIndexSignExt) {}
43  BaseIndexOffset(SDValue Base, SDValue Index, int64_t Offset,
44  bool IsIndexSignExt)
45  : Base(Base), Index(Index), Offset(Offset),
46  IsIndexSignExt(IsIndexSignExt) {}
47 
48  SDValue getBase() { return Base; }
49  SDValue getBase() const { return Base; }
50  SDValue getIndex() { return Index; }
51  SDValue getIndex() const { return Index; }
52  bool hasValidOffset() const { return Offset.hasValue(); }
53  int64_t getOffset() const { return *Offset; }
54 
55  // Returns true if `Other` and `*this` are both some offset from the same base
56  // pointer. In that case, `Off` is set to the offset between `*this` and
57  // `Other` (negative if `Other` is before `*this`).
58  bool equalBaseIndex(const BaseIndexOffset &Other, const SelectionDAG &DAG,
59  int64_t &Off) const;
60 
61  bool equalBaseIndex(const BaseIndexOffset &Other,
62  const SelectionDAG &DAG) const {
63  int64_t Off;
64  return equalBaseIndex(Other, DAG, Off);
65  }
66 
67  // Returns true if `Other` (with size `OtherSize`) can be proven to be fully
68  // contained in `*this` (with size `Size`).
69  bool contains(const SelectionDAG &DAG, int64_t BitSize,
70  const BaseIndexOffset &Other, int64_t OtherBitSize,
71  int64_t &BitOffset) const;
72 
73  bool contains(const SelectionDAG &DAG, int64_t BitSize,
74  const BaseIndexOffset &Other, int64_t OtherBitSize) const {
75  int64_t BitOffset;
76  return contains(DAG, BitSize, Other, OtherBitSize, BitOffset);
77  }
78 
79  // Returns true `Op0` and `Op1` can be proven to alias/not alias, in
80  // which case `IsAlias` is set to true/false.
81  static bool computeAliasing(const SDNode *Op0,
82  const Optional<int64_t> NumBytes0,
83  const SDNode *Op1,
84  const Optional<int64_t> NumBytes1,
85  const SelectionDAG &DAG, bool &IsAlias);
86 
87  /// Parses tree in N for base, index, offset addresses.
88  static BaseIndexOffset match(const SDNode *N, const SelectionDAG &DAG);
89 
90  void print(raw_ostream& OS) const;
91  void dump() const;
92 };
93 
94 } // end namespace llvm
95 
96 #endif // LLVM_CODEGEN_SELECTIONDAGADDRESSANALYSIS_H
llvm::BaseIndexOffset::print
void print(raw_ostream &OS) const
Definition: SelectionDAGAddressAnalysis.cpp:315
llvm
This file implements support for optimizing divisions by a constant.
Definition: AllocatorList.h:23
llvm::BaseIndexOffset::BaseIndexOffset
BaseIndexOffset(SDValue Base, SDValue Index, bool IsIndexSignExt)
Definition: SelectionDAGAddressAnalysis.h:41
llvm::BaseIndexOffset::equalBaseIndex
bool equalBaseIndex(const BaseIndexOffset &Other, const SelectionDAG &DAG) const
Definition: SelectionDAGAddressAnalysis.h:61
llvm::SDNode
Represents one node in the SelectionDAG.
Definition: SelectionDAGNodes.h:455
llvm::BaseIndexOffset::getBase
SDValue getBase()
Definition: SelectionDAGAddressAnalysis.h:48
llvm::Optional< int64_t >
llvm::BaseIndexOffset::contains
bool contains(const SelectionDAG &DAG, int64_t BitSize, const BaseIndexOffset &Other, int64_t OtherBitSize, int64_t &BitOffset) const
Definition: SelectionDAGAddressAnalysis.cpp:172
llvm::BaseIndexOffset::dump
void dump() const
Definition: SelectionDAGAddressAnalysis.cpp:311
llvm::SelectionDAG
This is used to represent a portion of an LLVM function in a low-level Data Dependence DAG representa...
Definition: SelectionDAG.h:216
SelectionDAGNodes.h
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:53
llvm::BaseIndexOffset::match
static BaseIndexOffset match(const SDNode *N, const SelectionDAG &DAG)
Parses tree in N for base, index, offset addresses.
Definition: SelectionDAGAddressAnalysis.cpp:296
llvm::BaseIndexOffset::computeAliasing
static bool computeAliasing(const SDNode *Op0, const Optional< int64_t > NumBytes0, const SDNode *Op1, const Optional< int64_t > NumBytes1, const SelectionDAG &DAG, bool &IsAlias)
Definition: SelectionDAGAddressAnalysis.cpp:87
llvm::BaseIndexOffset::getBase
SDValue getBase() const
Definition: SelectionDAGAddressAnalysis.h:49
llvm::BaseIndexOffset::getOffset
int64_t getOffset() const
Definition: SelectionDAGAddressAnalysis.h:53
llvm::BaseIndexOffset::equalBaseIndex
bool equalBaseIndex(const BaseIndexOffset &Other, const SelectionDAG &DAG, int64_t &Off) const
Definition: SelectionDAGAddressAnalysis.cpp:24
llvm::BaseIndexOffset::contains
bool contains(const SelectionDAG &DAG, int64_t BitSize, const BaseIndexOffset &Other, int64_t OtherBitSize) const
Definition: SelectionDAGAddressAnalysis.h:73
llvm::BaseIndexOffset::getIndex
SDValue getIndex()
Definition: SelectionDAGAddressAnalysis.h:50
llvm::SDValue
Unlike LLVM values, Selection DAG nodes may return multiple values as the result of a computation.
Definition: SelectionDAGNodes.h:138
llvm::BaseIndexOffset::hasValidOffset
bool hasValidOffset() const
Definition: SelectionDAGAddressAnalysis.h:52
llvm::BaseIndexOffset
Helper struct to parse and store a memory address as base + index + offset.
Definition: SelectionDAGAddressAnalysis.h:32
llvm::BaseIndexOffset::BaseIndexOffset
BaseIndexOffset()=default
N
#define N
llvm::BaseIndexOffset::BaseIndexOffset
BaseIndexOffset(SDValue Base, SDValue Index, int64_t Offset, bool IsIndexSignExt)
Definition: SelectionDAGAddressAnalysis.h:43
llvm::BaseIndexOffset::getIndex
SDValue getIndex() const
Definition: SelectionDAGAddressAnalysis.h:51
llvm::sampleprof::Base
@ Base
Definition: Discriminator.h:58
Other
Optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:1184