LLVM  7.0.0svn
SelectionDAGAddressAnalysis.cpp
Go to the documentation of this file.
1 //==- llvm/CodeGen/SelectionDAGAddressAnalysis.cpp - DAG Address Analysis --==//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 
17 #include "llvm/Support/Casting.h"
18 #include <cstdint>
19 
20 using namespace llvm;
21 
23  const SelectionDAG &DAG, int64_t &Off) {
24  // Conservatively fail if we a match failed..
25  if (!Base.getNode() || !Other.Base.getNode())
26  return false;
27  // Initial Offset difference.
28  Off = Other.Offset - Offset;
29 
30  if ((Other.Index == Index) && (Other.IsIndexSignExt == IsIndexSignExt)) {
31  // Trivial match.
32  if (Other.Base == Base)
33  return true;
34 
35  // Match GlobalAddresses
36  if (auto *A = dyn_cast<GlobalAddressSDNode>(Base))
37  if (auto *B = dyn_cast<GlobalAddressSDNode>(Other.Base))
38  if (A->getGlobal() == B->getGlobal()) {
39  Off += B->getOffset() - A->getOffset();
40  return true;
41  }
42 
43  // Match Constants
44  if (auto *A = dyn_cast<ConstantPoolSDNode>(Base))
45  if (auto *B = dyn_cast<ConstantPoolSDNode>(Other.Base)) {
46  bool IsMatch =
47  A->isMachineConstantPoolEntry() == B->isMachineConstantPoolEntry();
48  if (IsMatch) {
49  if (A->isMachineConstantPoolEntry())
50  IsMatch = A->getMachineCPVal() == B->getMachineCPVal();
51  else
52  IsMatch = A->getConstVal() == B->getConstVal();
53  }
54  if (IsMatch) {
55  Off += B->getOffset() - A->getOffset();
56  return true;
57  }
58  }
59 
61 
62  // Match non-equal FrameIndexes - If both frame indices are fixed
63  // we know their relative offsets and can compare them. Otherwise
64  // we must be conservative.
65  if (auto *A = dyn_cast<FrameIndexSDNode>(Base))
66  if (auto *B = dyn_cast<FrameIndexSDNode>(Other.Base))
67  if (MFI.isFixedObjectIndex(A->getIndex()) &&
68  MFI.isFixedObjectIndex(B->getIndex())) {
69  Off += MFI.getObjectOffset(B->getIndex()) -
70  MFI.getObjectOffset(A->getIndex());
71  return true;
72  }
73  }
74  return false;
75 }
76 
77 /// Parses tree in Ptr for base, index, offset addresses.
79  const SelectionDAG &DAG) {
80  SDValue Ptr = N->getBasePtr();
81 
82  // (((B + I*M) + c)) + c ...
84  SDValue Index = SDValue();
85  int64_t Offset = 0;
86  bool IsIndexSignExt = false;
87 
88  // pre-inc/pre-dec ops are components of EA.
89  if (N->getAddressingMode() == ISD::PRE_INC) {
90  if (auto *C = dyn_cast<ConstantSDNode>(N->getOffset()))
91  Offset += C->getSExtValue();
92  else // If unknown, give up now.
93  return BaseIndexOffset(SDValue(), SDValue(), 0, false);
94  } else if (N->getAddressingMode() == ISD::PRE_DEC) {
95  if (auto *C = dyn_cast<ConstantSDNode>(N->getOffset()))
96  Offset -= C->getSExtValue();
97  else // If unknown, give up now.
98  return BaseIndexOffset(SDValue(), SDValue(), 0, false);
99  }
100 
101  // Consume constant adds & ors with appropriate masking.
102  while (true) {
103  switch (Base->getOpcode()) {
104  case ISD::OR:
105  // Only consider ORs which act as adds.
106  if (auto *C = dyn_cast<ConstantSDNode>(Base->getOperand(1)))
107  if (DAG.MaskedValueIsZero(Base->getOperand(0), C->getAPIntValue())) {
108  Offset += C->getSExtValue();
109  Base = Base->getOperand(0);
110  continue;
111  }
112  break;
113  case ISD::ADD:
114  if (auto *C = dyn_cast<ConstantSDNode>(Base->getOperand(1))) {
115  Offset += C->getSExtValue();
116  Base = Base->getOperand(0);
117  continue;
118  }
119  break;
120  case ISD::LOAD:
121  case ISD::STORE: {
122  auto *LSBase = cast<LSBaseSDNode>(Base.getNode());
123  unsigned int IndexResNo = (Base->getOpcode() == ISD::LOAD) ? 1 : 0;
124  if (LSBase->isIndexed() && Base.getResNo() == IndexResNo)
125  if (auto *C = dyn_cast<ConstantSDNode>(LSBase->getOffset())) {
126  auto Off = C->getSExtValue();
127  if (LSBase->getAddressingMode() == ISD::PRE_DEC ||
128  LSBase->getAddressingMode() == ISD::POST_DEC)
129  Offset -= Off;
130  else
131  Offset += Off;
132  Base = LSBase->getBasePtr();
133  continue;
134  }
135  break;
136  }
137  }
138  // If we get here break out of the loop.
139  break;
140  }
141 
142  if (Base->getOpcode() == ISD::ADD) {
143  // TODO: The following code appears to be needless as it just
144  // bails on some Ptrs early, reducing the cases where we
145  // find equivalence. We should be able to remove this.
146  // Inside a loop the current BASE pointer is calculated using an ADD and a
147  // MUL instruction. In this case Base is the actual BASE pointer.
148  // (i64 add (i64 %array_ptr)
149  // (i64 mul (i64 %induction_var)
150  // (i64 %element_size)))
151  if (Base->getOperand(1)->getOpcode() == ISD::MUL)
152  return BaseIndexOffset(Base, Index, Offset, IsIndexSignExt);
153 
154  // Look at Base + Index + Offset cases.
155  Index = Base->getOperand(1);
156  SDValue PotentialBase = Base->getOperand(0);
157 
158  // Skip signextends.
159  if (Index->getOpcode() == ISD::SIGN_EXTEND) {
160  Index = Index->getOperand(0);
161  IsIndexSignExt = true;
162  }
163 
164  // Check if Index Offset pattern
165  if (Index->getOpcode() != ISD::ADD ||
166  !isa<ConstantSDNode>(Index->getOperand(1)))
167  return BaseIndexOffset(PotentialBase, Index, Offset, IsIndexSignExt);
168 
169  Offset += cast<ConstantSDNode>(Index->getOperand(1))->getSExtValue();
170  Index = Index->getOperand(0);
171  if (Index->getOpcode() == ISD::SIGN_EXTEND) {
172  Index = Index->getOperand(0);
173  IsIndexSignExt = true;
174  } else
175  IsIndexSignExt = false;
176  Base = PotentialBase;
177  }
178  return BaseIndexOffset(Base, Index, Offset, IsIndexSignExt);
179 }
uint64_t CallInst * C
unsigned getOpcode() const
Return the SelectionDAG opcode value for this node.
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
ISD::MemIndexedMode getAddressingMode() const
Return the addressing mode for this load or store: unindexed, pre-inc, pre-dec, post-inc, or post-dec.
SDNode * getNode() const
get the SDNode which holds the desired result
bool equalBaseIndex(BaseIndexOffset &Other, const SelectionDAG &DAG)
Base class for LoadSDNode and StoreSDNode.
int64_t getObjectOffset(int ObjectIdx) const
Return the assigned stack offset of the specified object from the incoming stack pointer.
The MachineFrameInfo class represents an abstract stack frame until prolog/epilog code is inserted...
static BaseIndexOffset match(LSBaseSDNode *N, const SelectionDAG &DAG)
Parses tree in Ptr for base, index, offset addresses.
MachineFunction & getMachineFunction() const
Definition: SelectionDAG.h:395
Simple integer binary arithmetic operators.
Definition: ISDOpcodes.h:201
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
MachineFrameInfo & getFrameInfo()
getFrameInfo - Return the frame info object for the current function.
const SDValue & getOperand(unsigned Num) const
bool isFixedObjectIndex(int ObjectIdx) const
Returns true if the specified index corresponds to a fixed stack object.
virtual SDValue unwrapAddress(SDValue N) const
const TargetLowering & getTargetLoweringInfo() const
Definition: SelectionDAG.h:401
Helper struct to parse and store a memory address as base + index + offset.
This is used to represent a portion of an LLVM function in a low-level Data Dependence DAG representa...
Definition: SelectionDAG.h:222
const SDValue & getOffset() const
LOAD and STORE have token chains as their first operand, then the same operands as an LLVM load/store...
Definition: ISDOpcodes.h:575
#define N
bool MaskedValueIsZero(SDValue Op, const APInt &Mask, unsigned Depth=0) const
Return true if &#39;Op & Mask&#39; is known to be zero.
unsigned getResNo() const
get the index which selects a specific result in the SDNode
Conversion operators.
Definition: ISDOpcodes.h:435
Unlike LLVM values, Selection DAG nodes may return multiple values as the result of a computation...
const SDValue & getBasePtr() const
This file describes how to lower LLVM code to machine code.