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 package org.graalvm.compiler.core.amd64;
25
26 import org.graalvm.compiler.asm.amd64.AMD64Address.Scale;
27 import org.graalvm.compiler.core.common.NumUtil;
28 import org.graalvm.compiler.core.common.type.IntegerStamp;
29 import org.graalvm.compiler.debug.DebugContext;
30 import org.graalvm.compiler.nodes.StructuredGraph;
31 import org.graalvm.compiler.nodes.ValueNode;
32 import org.graalvm.compiler.nodes.calc.AddNode;
33 import org.graalvm.compiler.nodes.calc.LeftShiftNode;
34 import org.graalvm.compiler.nodes.calc.NegateNode;
35 import org.graalvm.compiler.nodes.calc.ZeroExtendNode;
36 import org.graalvm.compiler.nodes.memory.address.AddressNode;
37 import org.graalvm.compiler.phases.common.AddressLoweringPhase.AddressLowering;
38
39 import jdk.vm.ci.meta.JavaConstant;
40
41 public class AMD64AddressLowering extends AddressLowering {
42 @Override
43 public AddressNode lower(ValueNode address) {
44 return lower(address, null);
45 }
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 return graph.unique(ret);
58 }
59
60 /**
61 * Tries to optimize addresses so that they match the AMD64-specific addressing mode better
62 * (base + index * scale + displacement).
63 *
64 * @param graph the current graph
65 * @param debug the current debug context
66 * @param ret the address that should be optimized
67 * @param isBaseNegated determines if the address base is negated. if so, all values that are
68 * extracted from the base will be negated as well
69 * @param isIndexNegated determines if the index is negated. if so, all values that are
70 * extracted from the index will be negated as well
71 * @return true if the address was modified
72 */
73 protected boolean improve(StructuredGraph graph, DebugContext debug, AMD64AddressNode ret, boolean isBaseNegated, boolean isIndexNegated) {
74 ValueNode newBase = improveInput(ret, ret.getBase(), 0, isBaseNegated);
75 if (newBase != ret.getBase()) {
76 ret.setBase(newBase);
77 return true;
78 }
79
80 ValueNode newIdx = improveInput(ret, ret.getIndex(), ret.getScale().log2, isIndexNegated);
81 if (newIdx != ret.getIndex()) {
82 ret.setIndex(newIdx);
83 return true;
84 }
85
86 if (ret.getIndex() instanceof LeftShiftNode) {
87 LeftShiftNode shift = (LeftShiftNode) ret.getIndex();
88 if (shift.getY().isConstant()) {
89 int amount = ret.getScale().log2 + shift.getY().asJavaConstant().asInt();
90 Scale scale = Scale.fromShift(amount);
91 if (scale != null) {
92 ret.setIndex(shift.getX());
93 ret.setScale(scale);
94 return true;
95 }
96 }
97 }
98
99 if (ret.getScale() == Scale.Times1) {
100 if (ret.getIndex() == null && ret.getBase() instanceof AddNode) {
101 AddNode add = (AddNode) ret.getBase();
102 ret.setBase(add.getX());
103 ret.setIndex(considerNegation(graph, add.getY(), isBaseNegated));
104 return true;
105 } else if (ret.getBase() == null && ret.getIndex() instanceof AddNode) {
106 AddNode add = (AddNode) ret.getIndex();
107 ret.setBase(considerNegation(graph, add.getX(), isIndexNegated));
108 ret.setIndex(add.getY());
109 return true;
110 }
111
112 if (ret.getBase() instanceof LeftShiftNode && !(ret.getIndex() instanceof LeftShiftNode)) {
113 ValueNode tmp = ret.getBase();
114 ret.setBase(considerNegation(graph, ret.getIndex(), isIndexNegated != isBaseNegated));
115 ret.setIndex(considerNegation(graph, tmp, isIndexNegated != isBaseNegated));
116 return true;
117 }
118 }
119
120 return improveNegation(graph, debug, ret, isBaseNegated, isIndexNegated);
121 }
122
123 private boolean improveNegation(StructuredGraph graph, DebugContext debug, AMD64AddressNode ret, boolean originalBaseNegated, boolean originalIndexNegated) {
124 boolean baseNegated = originalBaseNegated;
125 boolean indexNegated = originalIndexNegated;
126
127 ValueNode originalBase = ret.getBase();
128 ValueNode originalIndex = ret.getIndex();
129
130 if (ret.getBase() instanceof NegateNode) {
131 NegateNode negate = (NegateNode) ret.getBase();
132 ret.setBase(negate.getValue());
133 baseNegated = !baseNegated;
134 }
135
136 if (ret.getIndex() instanceof NegateNode) {
137 NegateNode negate = (NegateNode) ret.getIndex();
138 ret.setIndex(negate.getValue());
139 indexNegated = !indexNegated;
140 }
141
142 if (baseNegated != originalBaseNegated || indexNegated != originalIndexNegated) {
143 ValueNode base = ret.getBase();
144 ValueNode index = ret.getIndex();
145
146 boolean improved = improve(graph, debug, ret, baseNegated, indexNegated);
147 if (baseNegated != originalBaseNegated) {
148 if (base == ret.getBase()) {
149 ret.setBase(originalBase);
150 } else if (ret.getBase() != null) {
151 ret.setBase(graph.maybeAddOrUnique(NegateNode.create(ret.getBase())));
152 }
153 }
154
155 if (indexNegated != originalIndexNegated) {
156 if (index == ret.getIndex()) {
157 ret.setIndex(originalIndex);
158 } else if (ret.getIndex() != null) {
159 ret.setIndex(graph.maybeAddOrUnique(NegateNode.create(ret.getIndex())));
160 }
161 }
162 return improved;
163 } else {
164 assert ret.getBase() == originalBase && ret.getIndex() == originalIndex;
165 }
166 return false;
167 }
168
169 private static ValueNode considerNegation(StructuredGraph graph, ValueNode value, boolean negate) {
170 if (negate && value != null) {
171 return graph.maybeAddOrUnique(NegateNode.create(value));
172 }
173 return value;
174 }
175
176 private ValueNode improveInput(AMD64AddressNode address, ValueNode node, int shift, boolean negateExtractedDisplacement) {
177 if (node == null) {
178 return null;
179 }
180
181 JavaConstant c = node.asJavaConstant();
182 if (c != null) {
183 return improveConstDisp(address, node, c, null, shift, negateExtractedDisplacement);
184 } else {
185 if (node.stamp() instanceof IntegerStamp) {
186 if (node instanceof ZeroExtendNode && (((ZeroExtendNode) node).getInputBits() == 32)) {
187 /*
188 * we can't just swallow all zero-extends as we might encounter something like
189 * the following: ZeroExtend(Add(negativeValue, positiveValue)).
190 *
191 * if we swallow the zero-extend in this case and subsequently optimize the add,
192 * we might end up with a negative value that has less than 64 bits in base or
193 * index. such a value would require sign extension instead of zero-extension
194 * but the backend can only do zero-extension. if we ever want to optimize that
195 * further, we would also need to be careful about over-/underflows.
196 *
197 * furthermore, we also can't swallow zero-extends with less than 32 bits as
198 * most of these values are immediately sign-extended to 32 bit by the backend
199 * (therefore, the subsequent implicit zero-extension to 64 bit won't do what we
200 * expect).
201 */
202 ValueNode value = ((ZeroExtendNode) node).getValue();
203 if (!mightBeOptimized(value)) {
204 // if the value is not optimized further by the address lowering, then we
205 // can safely rely on the backend doing the implicitly zero-extension.
206 return value;
207 }
208 }
209
210 if (node instanceof AddNode) {
211 AddNode add = (AddNode) node;
212 if (add.getX().isConstant()) {
213 return improveConstDisp(address, node, add.getX().asJavaConstant(), add.getY(), shift, negateExtractedDisplacement);
214 } else if (add.getY().isConstant()) {
215 return improveConstDisp(address, node, add.getY().asJavaConstant(), add.getX(), shift, negateExtractedDisplacement);
216 }
217 }
218 }
219 }
220
221 return node;
222 }
223
224 /**
225 * This method returns true for all nodes that might be optimized by the address lowering.
226 */
227 protected boolean mightBeOptimized(ValueNode value) {
228 return value instanceof AddNode || value instanceof LeftShiftNode || value instanceof NegateNode || value instanceof ZeroExtendNode;
229 }
230
231 private static ValueNode improveConstDisp(AMD64AddressNode address, ValueNode original, JavaConstant c, ValueNode other, int shift, boolean negateExtractedDisplacement) {
232 if (c.getJavaKind().isNumericInteger()) {
233 long delta = c.asLong() << shift;
234 if (updateDisplacement(address, delta, negateExtractedDisplacement)) {
235 return other;
236 }
237 }
238 return original;
239 }
240
241 protected static boolean updateDisplacement(AMD64AddressNode address, long displacementDelta, boolean negateDelta) {
242 long sign = negateDelta ? -1 : 1;
243 long disp = address.getDisplacement() + displacementDelta * sign;
244 if (NumUtil.isInt(disp)) {
245 address.setDisplacement((int) disp);
246 return true;
247 }
248 return false;
249 }
250 }