1 /*
2 * Copyright (c) 2015, 2016, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 */
23
24
25
26 package org.graalvm.compiler.core.amd64;
27
28 import org.graalvm.compiler.asm.amd64.AMD64Address.Scale;
29 import org.graalvm.compiler.core.common.NumUtil;
30 import org.graalvm.compiler.core.common.type.AbstractPointerStamp;
31 import org.graalvm.compiler.core.common.type.IntegerStamp;
32 import org.graalvm.compiler.debug.DebugContext;
33 import org.graalvm.compiler.nodes.NodeView;
34 import org.graalvm.compiler.nodes.StructuredGraph;
35 import org.graalvm.compiler.nodes.ValueNode;
36 import org.graalvm.compiler.nodes.calc.AddNode;
37 import org.graalvm.compiler.nodes.calc.LeftShiftNode;
38 import org.graalvm.compiler.nodes.calc.NegateNode;
39 import org.graalvm.compiler.nodes.memory.address.AddressNode;
40 import org.graalvm.compiler.phases.common.AddressLoweringPhase.AddressLowering;
41
42 import jdk.vm.ci.meta.JavaConstant;
43
44 public class AMD64AddressLowering extends AddressLowering {
45 private static final int ADDRESS_BITS = 64;
46
47 @Override
48 public AddressNode lower(ValueNode base, ValueNode offset) {
49 AMD64AddressNode ret = new AMD64AddressNode(base, offset);
50 StructuredGraph graph = base.graph();
51
52 boolean changed;
53 do {
54 changed = improve(graph, base.getDebug(), ret, false, false);
55 } while (changed);
56
57 assert checkAddressBitWidth(ret.getBase());
58 assert checkAddressBitWidth(ret.getIndex());
59 return graph.unique(ret);
60 }
61
62 private static boolean checkAddressBitWidth(ValueNode value) {
63 return value == null || value.stamp(NodeView.DEFAULT) instanceof AbstractPointerStamp || IntegerStamp.getBits(value.stamp(NodeView.DEFAULT)) == ADDRESS_BITS;
64 }
65
66 /**
67 * Tries to optimize addresses so that they match the AMD64-specific addressing mode better
68 * (base + index * scale + displacement).
69 *
70 * @param graph the current graph
71 * @param debug the current debug context
72 * @param ret the address that should be optimized
73 * @param isBaseNegated determines if the address base is negated. if so, all values that are
74 * extracted from the base will be negated as well
75 * @param isIndexNegated determines if the index is negated. if so, all values that are
76 * extracted from the index will be negated as well
77 * @return true if the address was modified
78 */
79 protected boolean improve(StructuredGraph graph, DebugContext debug, AMD64AddressNode ret, boolean isBaseNegated, boolean isIndexNegated) {
80 ValueNode newBase = improveInput(ret, ret.getBase(), 0, isBaseNegated);
81 if (newBase != ret.getBase()) {
82 ret.setBase(newBase);
83 return true;
84 }
85
86 ValueNode newIdx = improveInput(ret, ret.getIndex(), ret.getScale().log2, isIndexNegated);
87 if (newIdx != ret.getIndex()) {
88 ret.setIndex(newIdx);
89 return true;
90 }
91
92 if (ret.getIndex() instanceof LeftShiftNode) {
93 LeftShiftNode shift = (LeftShiftNode) ret.getIndex();
94 if (shift.getY().isConstant()) {
95 int amount = ret.getScale().log2 + shift.getY().asJavaConstant().asInt();
96 Scale scale = Scale.fromShift(amount);
97 if (scale != null) {
98 ret.setIndex(shift.getX());
99 ret.setScale(scale);
100 return true;
101 }
102 }
103 }
104
105 if (ret.getScale() == Scale.Times1) {
106 if (ret.getIndex() == null && ret.getBase() instanceof AddNode) {
107 AddNode add = (AddNode) ret.getBase();
108 ret.setBase(add.getX());
109 ret.setIndex(considerNegation(graph, add.getY(), isBaseNegated));
110 return true;
111 }
112
113 if (ret.getBase() == null && ret.getIndex() instanceof AddNode) {
114 AddNode add = (AddNode) ret.getIndex();
115 ret.setBase(considerNegation(graph, add.getX(), isIndexNegated));
116 ret.setIndex(add.getY());
117 return true;
118 }
119
120 if (ret.getBase() instanceof LeftShiftNode && !(ret.getIndex() instanceof LeftShiftNode)) {
121 ValueNode tmp = ret.getBase();
122 ret.setBase(considerNegation(graph, ret.getIndex(), isIndexNegated != isBaseNegated));
123 ret.setIndex(considerNegation(graph, tmp, isIndexNegated != isBaseNegated));
124 return true;
125 }
126 }
127
128 return improveNegation(graph, debug, ret, isBaseNegated, isIndexNegated);
129 }
130
131 private boolean improveNegation(StructuredGraph graph, DebugContext debug, AMD64AddressNode ret, boolean originalBaseNegated, boolean originalIndexNegated) {
132 boolean baseNegated = originalBaseNegated;
133 boolean indexNegated = originalIndexNegated;
134
135 ValueNode originalBase = ret.getBase();
136 ValueNode originalIndex = ret.getIndex();
137
138 if (ret.getBase() instanceof NegateNode) {
139 NegateNode negate = (NegateNode) ret.getBase();
140 ret.setBase(negate.getValue());
141 baseNegated = !baseNegated;
142 }
143
144 if (ret.getIndex() instanceof NegateNode) {
145 NegateNode negate = (NegateNode) ret.getIndex();
146 ret.setIndex(negate.getValue());
147 indexNegated = !indexNegated;
148 }
149
150 if (baseNegated != originalBaseNegated || indexNegated != originalIndexNegated) {
151 ValueNode base = ret.getBase();
152 ValueNode index = ret.getIndex();
153
154 boolean improved = improve(graph, debug, ret, baseNegated, indexNegated);
155 if (baseNegated != originalBaseNegated) {
156 if (base == ret.getBase()) {
157 ret.setBase(originalBase);
158 } else if (ret.getBase() != null) {
159 ret.setBase(graph.maybeAddOrUnique(NegateNode.create(ret.getBase(), NodeView.DEFAULT)));
160 }
161 }
162
163 if (indexNegated != originalIndexNegated) {
164 if (index == ret.getIndex()) {
165 ret.setIndex(originalIndex);
166 } else if (ret.getIndex() != null) {
167 ret.setIndex(graph.maybeAddOrUnique(NegateNode.create(ret.getIndex(), NodeView.DEFAULT)));
168 }
169 }
170 return improved;
171 } else {
172 assert ret.getBase() == originalBase && ret.getIndex() == originalIndex;
173 }
174 return false;
175 }
176
177 private static ValueNode considerNegation(StructuredGraph graph, ValueNode value, boolean negate) {
178 if (negate && value != null) {
179 return graph.maybeAddOrUnique(NegateNode.create(value, NodeView.DEFAULT));
180 }
181 return value;
182 }
183
184 private static ValueNode improveInput(AMD64AddressNode address, ValueNode node, int shift, boolean negateExtractedDisplacement) {
185 if (node == null) {
186 return null;
187 }
188
189 JavaConstant c = node.asJavaConstant();
190 if (c != null) {
191 return improveConstDisp(address, node, c, null, shift, negateExtractedDisplacement);
192 } else {
193 if (node.stamp(NodeView.DEFAULT) instanceof IntegerStamp) {
194 assert IntegerStamp.getBits(node.stamp(NodeView.DEFAULT)) == ADDRESS_BITS;
195
196 /*
197 * we can't swallow zero-extends because of multiple reasons:
198 *
199 * a) we might encounter something like the following: ZeroExtend(Add(negativeValue,
200 * positiveValue)). if we swallow the zero-extend in this case and subsequently
201 * optimize the add, we might end up with a negative value that has less than 64
202 * bits in base or index. such a value would require sign extension instead of
203 * zero-extension but the backend can only do (implicit) zero-extension by using a
204 * larger register (e.g., rax instead of eax).
205 *
206 * b) our backend does not guarantee that the upper half of a 64-bit register equals
207 * 0 if a 32-bit value is stored in there.
208 *
209 * c) we also can't swallow zero-extends with less than 32 bits as most of these
210 * values are immediately sign-extended to 32 bit by the backend (therefore, the
211 * subsequent implicit zero-extension to 64 bit won't do what we expect).
212 */
213
214 if (node instanceof AddNode) {
215 AddNode add = (AddNode) node;
216 if (add.getX().isConstant()) {
217 return improveConstDisp(address, node, add.getX().asJavaConstant(), add.getY(), shift, negateExtractedDisplacement);
218 } else if (add.getY().isConstant()) {
219 return improveConstDisp(address, node, add.getY().asJavaConstant(), add.getX(), shift, negateExtractedDisplacement);
220 }
221 }
222 }
223 }
224
225 return node;
226 }
227
228 private static ValueNode improveConstDisp(AMD64AddressNode address, ValueNode original, JavaConstant c, ValueNode other, int shift, boolean negateExtractedDisplacement) {
229 if (c.getJavaKind().isNumericInteger()) {
230 long delta = c.asLong() << shift;
231 if (updateDisplacement(address, delta, negateExtractedDisplacement)) {
232 return other;
233 }
234 }
235 return original;
236 }
237
238 protected static boolean updateDisplacement(AMD64AddressNode address, long displacementDelta, boolean negateDelta) {
239 long sign = negateDelta ? -1 : 1;
240 long disp = address.getDisplacement() + displacementDelta * sign;
241 if (NumUtil.isInt(disp)) {
242 address.setDisplacement((int) disp);
243 return true;
244 }
245 return false;
246 }
247 }