Line data Source code
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 :
10 : #include "llvm/CodeGen/SelectionDAGAddressAnalysis.h"
11 : #include "llvm/CodeGen/ISDOpcodes.h"
12 : #include "llvm/CodeGen/MachineFrameInfo.h"
13 : #include "llvm/CodeGen/MachineFunction.h"
14 : #include "llvm/CodeGen/SelectionDAG.h"
15 : #include "llvm/CodeGen/SelectionDAGNodes.h"
16 : #include "llvm/CodeGen/TargetLowering.h"
17 : #include "llvm/Support/Casting.h"
18 : #include <cstdint>
19 :
20 : using namespace llvm;
21 :
22 11119950 : bool BaseIndexOffset::equalBaseIndex(BaseIndexOffset &Other,
23 : const SelectionDAG &DAG, int64_t &Off) {
24 : // Conservatively fail if we a match failed..
25 11119950 : if (!Base.getNode() || !Other.Base.getNode())
26 : return false;
27 : // Initial Offset difference.
28 11119950 : Off = Other.Offset - Offset;
29 :
30 21810425 : 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 3290537 : if (A->getGlobal() == B->getGlobal()) {
39 12456 : Off += B->getOffset() - A->getOffset();
40 12456 : 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 0 : A->isMachineConstantPoolEntry() == B->isMachineConstantPoolEntry();
48 0 : if (IsMatch) {
49 0 : if (A->isMachineConstantPoolEntry())
50 0 : IsMatch = A->getMachineCPVal() == B->getMachineCPVal();
51 : else
52 0 : IsMatch = A->getConstVal() == B->getConstVal();
53 : }
54 0 : if (IsMatch) {
55 0 : Off += B->getOffset() - A->getOffset();
56 0 : return true;
57 : }
58 : }
59 :
60 5399093 : const MachineFrameInfo &MFI = DAG.getMachineFunction().getFrameInfo();
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 66985 : if (MFI.isFixedObjectIndex(A->getIndex()) &&
68 17865 : MFI.isFixedObjectIndex(B->getIndex())) {
69 17708 : Off += MFI.getObjectOffset(B->getIndex()) -
70 : MFI.getObjectOffset(A->getIndex());
71 17708 : return true;
72 : }
73 : }
74 : return false;
75 : }
76 :
77 : /// Parses tree in Ptr for base, index, offset addresses.
78 21189902 : BaseIndexOffset BaseIndexOffset::match(LSBaseSDNode *N,
79 : const SelectionDAG &DAG) {
80 21189902 : SDValue Ptr = N->getBasePtr();
81 :
82 : // (((B + I*M) + c)) + c ...
83 21189902 : SDValue Base = DAG.getTargetLoweringInfo().unwrapAddress(Ptr);
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 21189902 : if (N->getAddressingMode() == ISD::PRE_INC) {
90 : if (auto *C = dyn_cast<ConstantSDNode>(N->getOffset()))
91 111 : Offset += C->getSExtValue();
92 : else // If unknown, give up now.
93 : return BaseIndexOffset(SDValue(), SDValue(), 0, false);
94 21189775 : } else if (N->getAddressingMode() == ISD::PRE_DEC) {
95 : if (auto *C = dyn_cast<ConstantSDNode>(N->getOffset()))
96 0 : 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 76666374 : switch (Base->getOpcode()) {
104 433064 : case ISD::OR:
105 : // Only consider ORs which act as adds.
106 433064 : if (auto *C = dyn_cast<ConstantSDNode>(Base->getOperand(1)))
107 789698 : if (DAG.MaskedValueIsZero(Base->getOperand(0), C->getAPIntValue())) {
108 394847 : Offset += C->getSExtValue();
109 394847 : Base = Base->getOperand(0);
110 394847 : continue;
111 : }
112 : break;
113 18193506 : case ISD::ADD:
114 18193506 : if (auto *C = dyn_cast<ConstantSDNode>(Base->getOperand(1))) {
115 16742187 : Offset += C->getSExtValue();
116 16742187 : Base = Base->getOperand(0);
117 16742187 : continue;
118 : }
119 : break;
120 642406 : case ISD::LOAD:
121 : case ISD::STORE: {
122 : auto *LSBase = cast<LSBaseSDNode>(Base.getNode());
123 642406 : unsigned int IndexResNo = (Base->getOpcode() == ISD::LOAD) ? 1 : 0;
124 642406 : if (LSBase->isIndexed() && Base.getResNo() == IndexResNo)
125 : if (auto *C = dyn_cast<ConstantSDNode>(LSBase->getOffset())) {
126 6267 : auto Off = C->getSExtValue();
127 6267 : if (LSBase->getAddressingMode() == ISD::PRE_DEC ||
128 : LSBase->getAddressingMode() == ISD::POST_DEC)
129 0 : Offset -= Off;
130 : else
131 6267 : Offset += Off;
132 6267 : Base = LSBase->getBasePtr();
133 6267 : continue;
134 : }
135 : break;
136 : }
137 : }
138 : // If we get here break out of the loop.
139 : break;
140 : }
141 :
142 21189886 : 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 2902638 : if (Base->getOperand(1)->getOpcode() == ISD::MUL)
152 1449894 : return BaseIndexOffset(Base, Index, Offset, IsIndexSignExt);
153 :
154 : // Look at Base + Index + Offset cases.
155 1404420 : Index = Base->getOperand(1);
156 1404420 : SDValue PotentialBase = Base->getOperand(0);
157 :
158 : // Skip signextends.
159 1404420 : if (Index->getOpcode() == ISD::SIGN_EXTEND) {
160 514 : Index = Index->getOperand(0);
161 : IsIndexSignExt = true;
162 : }
163 :
164 : // Check if Index Offset pattern
165 1404420 : if (Index->getOpcode() != ISD::ADD ||
166 1644 : !isa<ConstantSDNode>(Index->getOperand(1)))
167 1402995 : return BaseIndexOffset(PotentialBase, Index, Offset, IsIndexSignExt);
168 :
169 1425 : Offset += cast<ConstantSDNode>(Index->getOperand(1))->getSExtValue();
170 1425 : Index = Index->getOperand(0);
171 1425 : if (Index->getOpcode() == ISD::SIGN_EXTEND) {
172 74 : Index = Index->getOperand(0);
173 : IsIndexSignExt = true;
174 : } else
175 : IsIndexSignExt = false;
176 1425 : Base = PotentialBase;
177 : }
178 19739992 : return BaseIndexOffset(Base, Index, Offset, IsIndexSignExt);
179 : }
|
