21 * questions. |
21 * questions. |
22 */ |
22 */ |
23 |
23 |
24 package org.graalvm.compiler.core.amd64; |
24 package org.graalvm.compiler.core.amd64; |
25 |
25 |
26 import jdk.vm.ci.meta.JavaConstant; |
26 import org.graalvm.compiler.asm.amd64.AMD64Address.Scale; |
27 |
|
28 import org.graalvm.compiler.core.common.NumUtil; |
27 import org.graalvm.compiler.core.common.NumUtil; |
29 import org.graalvm.compiler.asm.amd64.AMD64Address.Scale; |
|
30 import org.graalvm.compiler.core.common.type.IntegerStamp; |
28 import org.graalvm.compiler.core.common.type.IntegerStamp; |
31 import org.graalvm.compiler.debug.DebugContext; |
29 import org.graalvm.compiler.debug.DebugContext; |
|
30 import org.graalvm.compiler.nodes.StructuredGraph; |
32 import org.graalvm.compiler.nodes.ValueNode; |
31 import org.graalvm.compiler.nodes.ValueNode; |
33 import org.graalvm.compiler.nodes.calc.AddNode; |
32 import org.graalvm.compiler.nodes.calc.AddNode; |
34 import org.graalvm.compiler.nodes.calc.LeftShiftNode; |
33 import org.graalvm.compiler.nodes.calc.LeftShiftNode; |
|
34 import org.graalvm.compiler.nodes.calc.NegateNode; |
35 import org.graalvm.compiler.nodes.calc.ZeroExtendNode; |
35 import org.graalvm.compiler.nodes.calc.ZeroExtendNode; |
36 import org.graalvm.compiler.nodes.memory.address.AddressNode; |
36 import org.graalvm.compiler.nodes.memory.address.AddressNode; |
37 import org.graalvm.compiler.phases.common.AddressLoweringPhase.AddressLowering; |
37 import org.graalvm.compiler.phases.common.AddressLoweringPhase.AddressLowering; |
38 |
38 |
|
39 import jdk.vm.ci.meta.JavaConstant; |
|
40 |
39 public class AMD64AddressLowering extends AddressLowering { |
41 public class AMD64AddressLowering extends AddressLowering { |
40 |
|
41 @Override |
42 @Override |
42 public AddressNode lower(ValueNode address) { |
43 public AddressNode lower(ValueNode address) { |
43 return lower(address, null); |
44 return lower(address, null); |
44 } |
45 } |
45 |
46 |
46 @Override |
47 @Override |
47 public AddressNode lower(ValueNode base, ValueNode offset) { |
48 public AddressNode lower(ValueNode base, ValueNode offset) { |
48 AMD64AddressNode ret = new AMD64AddressNode(base, offset); |
49 AMD64AddressNode ret = new AMD64AddressNode(base, offset); |
|
50 StructuredGraph graph = base.graph(); |
|
51 |
49 boolean changed; |
52 boolean changed; |
50 do { |
53 do { |
51 changed = improve(base.getDebug(), ret); |
54 changed = improve(graph, base.getDebug(), ret, false, false); |
52 } while (changed); |
55 } while (changed); |
53 return base.graph().unique(ret); |
56 |
|
57 return graph.unique(ret); |
54 } |
58 } |
55 |
59 |
56 /** |
60 /** |
57 * @param debug |
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 |
58 */ |
72 */ |
59 protected boolean improve(DebugContext debug, AMD64AddressNode ret) { |
73 protected boolean improve(StructuredGraph graph, DebugContext debug, AMD64AddressNode ret, boolean isBaseNegated, boolean isIndexNegated) { |
60 ValueNode newBase = improveInput(ret, ret.getBase(), 0); |
74 ValueNode newBase = improveInput(ret, ret.getBase(), 0, isBaseNegated); |
61 if (newBase != ret.getBase()) { |
75 if (newBase != ret.getBase()) { |
62 ret.setBase(newBase); |
76 ret.setBase(newBase); |
63 return true; |
77 return true; |
64 } |
78 } |
65 |
79 |
66 ValueNode newIdx = improveInput(ret, ret.getIndex(), ret.getScale().log2); |
80 ValueNode newIdx = improveInput(ret, ret.getIndex(), ret.getScale().log2, isIndexNegated); |
67 if (newIdx != ret.getIndex()) { |
81 if (newIdx != ret.getIndex()) { |
68 ret.setIndex(newIdx); |
82 ret.setIndex(newIdx); |
69 return true; |
83 return true; |
70 } |
84 } |
71 |
85 |
81 } |
95 } |
82 } |
96 } |
83 } |
97 } |
84 |
98 |
85 if (ret.getScale() == Scale.Times1) { |
99 if (ret.getScale() == Scale.Times1) { |
86 if (ret.getBase() == null || ret.getIndex() == null) { |
100 if (ret.getIndex() == null && ret.getBase() instanceof AddNode) { |
87 if (ret.getBase() instanceof AddNode) { |
101 AddNode add = (AddNode) ret.getBase(); |
88 AddNode add = (AddNode) ret.getBase(); |
102 ret.setBase(add.getX()); |
89 ret.setBase(add.getX()); |
103 ret.setIndex(considerNegation(graph, add.getY(), isBaseNegated)); |
90 ret.setIndex(add.getY()); |
104 return true; |
91 return true; |
105 } else if (ret.getBase() == null && ret.getIndex() instanceof AddNode) { |
92 } else if (ret.getIndex() instanceof AddNode) { |
106 AddNode add = (AddNode) ret.getIndex(); |
93 AddNode add = (AddNode) ret.getIndex(); |
107 ret.setBase(considerNegation(graph, add.getX(), isIndexNegated)); |
94 ret.setBase(add.getX()); |
108 ret.setIndex(add.getY()); |
95 ret.setIndex(add.getY()); |
109 return true; |
96 return true; |
|
97 } |
|
98 } |
110 } |
99 |
111 |
100 if (ret.getBase() instanceof LeftShiftNode && !(ret.getIndex() instanceof LeftShiftNode)) { |
112 if (ret.getBase() instanceof LeftShiftNode && !(ret.getIndex() instanceof LeftShiftNode)) { |
101 ValueNode tmp = ret.getBase(); |
113 ValueNode tmp = ret.getBase(); |
102 ret.setBase(ret.getIndex()); |
114 ret.setBase(considerNegation(graph, ret.getIndex(), isIndexNegated != isBaseNegated)); |
103 ret.setIndex(tmp); |
115 ret.setIndex(considerNegation(graph, tmp, isIndexNegated != isBaseNegated)); |
104 return true; |
116 return true; |
105 } |
117 } |
106 } |
118 } |
107 |
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 } |
108 return false; |
166 return false; |
109 } |
167 } |
110 |
168 |
111 private static ValueNode improveInput(AMD64AddressNode address, ValueNode node, int shift) { |
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) { |
112 if (node == null) { |
177 if (node == null) { |
113 return null; |
178 return null; |
114 } |
179 } |
115 |
180 |
116 JavaConstant c = node.asJavaConstant(); |
181 JavaConstant c = node.asJavaConstant(); |
117 if (c != null) { |
182 if (c != null) { |
118 return improveConstDisp(address, node, c, null, shift); |
183 return improveConstDisp(address, node, c, null, shift, negateExtractedDisplacement); |
119 } else { |
184 } else { |
120 if (node.stamp() instanceof IntegerStamp && ((IntegerStamp) node.stamp()).getBits() == 64) { |
185 if (node.stamp() instanceof IntegerStamp) { |
121 if (node instanceof ZeroExtendNode) { |
186 if (node instanceof ZeroExtendNode && (((ZeroExtendNode) node).getInputBits() == 32)) { |
122 if (((ZeroExtendNode) node).getInputBits() == 32) { |
187 /* |
123 /* |
188 * we can't just swallow all zero-extends as we might encounter something like |
124 * We can just swallow a zero-extend from 32 bit to 64 bit because the upper |
189 * the following: ZeroExtend(Add(negativeValue, positiveValue)). |
125 * half of the register will always be zero. |
190 * |
126 */ |
191 * if we swallow the zero-extend in this case and subsequently optimize the add, |
127 return ((ZeroExtendNode) node).getValue(); |
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; |
128 } |
207 } |
129 } else if (node instanceof AddNode) { |
208 } |
|
209 |
|
210 if (node instanceof AddNode) { |
130 AddNode add = (AddNode) node; |
211 AddNode add = (AddNode) node; |
131 if (add.getX().isConstant()) { |
212 if (add.getX().isConstant()) { |
132 return improveConstDisp(address, node, add.getX().asJavaConstant(), add.getY(), shift); |
213 return improveConstDisp(address, node, add.getX().asJavaConstant(), add.getY(), shift, negateExtractedDisplacement); |
133 } else if (add.getY().isConstant()) { |
214 } else if (add.getY().isConstant()) { |
134 return improveConstDisp(address, node, add.getY().asJavaConstant(), add.getX(), shift); |
215 return improveConstDisp(address, node, add.getY().asJavaConstant(), add.getX(), shift, negateExtractedDisplacement); |
135 } |
216 } |
136 } |
217 } |
137 } |
218 } |
138 } |
219 } |
139 |
220 |
140 return node; |
221 return node; |
141 } |
222 } |
142 |
223 |
143 private static ValueNode improveConstDisp(AMD64AddressNode address, ValueNode original, JavaConstant c, ValueNode other, int shift) { |
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) { |
144 if (c.getJavaKind().isNumericInteger()) { |
232 if (c.getJavaKind().isNumericInteger()) { |
145 long disp = address.getDisplacement(); |
233 long delta = c.asLong() << shift; |
146 disp += c.asLong() << shift; |
234 if (updateDisplacement(address, delta, negateExtractedDisplacement)) { |
147 if (NumUtil.isInt(disp)) { |
|
148 address.setDisplacement((int) disp); |
|
149 return other; |
235 return other; |
150 } |
236 } |
151 } |
237 } |
152 return original; |
238 return original; |
153 } |
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 } |
154 } |
250 } |