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
15namespace llvm {
16
17class 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)))))
32class BaseIndexOffset {
33private:
34  SDValue Base;
35  SDValue Index;
36  Optional<int64_t> Offset;
37  bool IsIndexSignExt = false;
38
39public:
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
54  // Returns true if `Other` and `*this` are both some offset from the same base
55  // pointer. In that case, `Off` is set to the offset between `*this` and
56  // `Other` (negative if `Other` is before `*this`).
57  bool equalBaseIndex(const BaseIndexOffset &Other, const SelectionDAG &DAG,
58                      int64_t &Off) const;
59
60  bool equalBaseIndex(const BaseIndexOffset &Other,
61                      const SelectionDAG &DAG) const {
62    int64_t Off;
63    return equalBaseIndex(Other, DAG, Off);
64  }
65
66  // Returns true if `Other` (with size `OtherSize`) can be proven to be fully
67  // contained in `*this` (with size `Size`).
68  bool contains(const SelectionDAG &DAG, int64_t BitSize,
69                const BaseIndexOffset &Other, int64_t OtherBitSize,
70                int64_t &BitOffset) const;
71
72  bool contains(const SelectionDAG &DAG, int64_t BitSize,
73                const BaseIndexOffset &Other, int64_t OtherBitSize) const {
74    int64_t BitOffset;
75    return contains(DAG, BitSize, Other, OtherBitSize, BitOffset);
76  }
77
78  // Returns true `Op0` and `Op1` can be proven to alias/not alias, in
79  // which case `IsAlias` is set to true/false.
80  static bool computeAliasing(const SDNode *Op0,
81                              const Optional<int64_t> NumBytes0,
82                              const SDNode *Op1,
83                              const Optional<int64_t> NumBytes1,
84                              const SelectionDAG &DAG, bool &IsAlias);
85
86  /// Parses tree in N for base, index, offset addresses.
87  static BaseIndexOffset match(const SDNode *N, const SelectionDAG &DAG);
88
89  void print(raw_ostream& OS) const;
90  void dump() const;
91};
92
93} // end namespace llvm
94
95#endif // LLVM_CODEGEN_SELECTIONDAGADDRESSANALYSIS_H
96