1 /*
2 * Copyright (c) 2015, 2017, 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.hotspot.amd64;
27
28 import static org.graalvm.compiler.core.common.GraalOptions.GeneratePIC;
29
30 import jdk.internal.vm.compiler.collections.EconomicMap;
31 import org.graalvm.compiler.asm.amd64.AMD64Address.Scale;
32 import org.graalvm.compiler.core.amd64.AMD64AddressNode;
33 import org.graalvm.compiler.core.amd64.AMD64CompressAddressLowering;
34 import org.graalvm.compiler.core.common.CompressEncoding;
35 import org.graalvm.compiler.core.common.type.IntegerStamp;
36 import org.graalvm.compiler.core.common.type.ObjectStamp;
37 import org.graalvm.compiler.graph.Node;
38 import org.graalvm.compiler.hotspot.GraalHotSpotVMConfig;
39 import org.graalvm.compiler.hotspot.nodes.GraalHotSpotVMConfigNode;
40 import org.graalvm.compiler.hotspot.nodes.type.KlassPointerStamp;
41 import org.graalvm.compiler.loop.BasicInductionVariable;
42 import org.graalvm.compiler.loop.CountedLoopInfo;
43 import org.graalvm.compiler.loop.DerivedInductionVariable;
44 import org.graalvm.compiler.loop.InductionVariable;
45 import org.graalvm.compiler.loop.LoopEx;
46 import org.graalvm.compiler.loop.LoopsData;
47 import org.graalvm.compiler.nodes.CompressionNode;
48 import org.graalvm.compiler.nodes.ConstantNode;
49 import org.graalvm.compiler.nodes.NodeView;
50 import org.graalvm.compiler.nodes.PhiNode;
51 import org.graalvm.compiler.nodes.StructuredGraph;
52 import org.graalvm.compiler.nodes.ValueNode;
53 import org.graalvm.compiler.nodes.calc.AddNode;
54 import org.graalvm.compiler.nodes.calc.SignExtendNode;
55 import org.graalvm.compiler.nodes.calc.ZeroExtendNode;
56 import org.graalvm.compiler.nodes.memory.address.AddressNode;
57 import org.graalvm.compiler.nodes.memory.address.OffsetAddressNode;
58 import org.graalvm.compiler.options.OptionValues;
59
60 import jdk.vm.ci.code.Register;
61 import jdk.vm.ci.meta.JavaKind;
62
63 public class AMD64HotSpotAddressLowering extends AMD64CompressAddressLowering {
64
65 private static final int ADDRESS_BITS = 64;
66 private static final int INT_BITS = 32;
67
68 private final long heapBase;
69 private final Register heapBaseRegister;
70 private final GraalHotSpotVMConfig config;
71 private final boolean generatePIC;
72
73 public AMD64HotSpotAddressLowering(GraalHotSpotVMConfig config, Register heapBaseRegister, OptionValues options) {
74 this.heapBase = config.getOopEncoding().getBase();
75 this.config = config;
76 this.generatePIC = GeneratePIC.getValue(options);
77 if (heapBase == 0 && !generatePIC) {
78 this.heapBaseRegister = null;
79 } else {
80 this.heapBaseRegister = heapBaseRegister;
81 }
82 }
83
84 @Override
85 protected final boolean improveUncompression(AMD64AddressNode addr, CompressionNode compression, ValueNode other) {
86 CompressEncoding encoding = compression.getEncoding();
87 Scale scale = Scale.fromShift(encoding.getShift());
88 if (scale == null) {
89 return false;
90 }
91
92 if (heapBaseRegister != null && encoding.getBase() == heapBase) {
93 if ((!generatePIC || compression.stamp(NodeView.DEFAULT) instanceof ObjectStamp) && other == null) {
94 // With PIC it is only legal to do for oops since the base value may be
95 // different at runtime.
96 ValueNode base = compression.graph().unique(new HeapBaseNode(heapBaseRegister));
97 addr.setBase(base);
98 } else {
99 return false;
100 }
101 } else if (encoding.getBase() != 0 || (generatePIC && compression.stamp(NodeView.DEFAULT) instanceof KlassPointerStamp)) {
102 if (generatePIC) {
103 if (other == null) {
104 ValueNode base = compression.graph().unique(new GraalHotSpotVMConfigNode(config, config.MARKID_NARROW_KLASS_BASE_ADDRESS, JavaKind.Long));
105 addr.setBase(base);
106 } else {
107 return false;
108 }
109 } else {
110 if (updateDisplacement(addr, encoding.getBase(), false)) {
111 addr.setBase(other);
112 } else {
113 return false;
114 }
115 }
116 } else {
117 addr.setBase(other);
118 }
119
120 addr.setScale(scale);
121 addr.setIndex(compression.getValue());
122 return true;
123 }
124
125 @Override
126 public void preProcess(StructuredGraph graph) {
127 if (graph.hasLoops()) {
128 LoopsData loopsData = new LoopsData(graph);
129 loopsData.detectedCountedLoops();
130 for (LoopEx loop : loopsData.countedLoops()) {
131 for (OffsetAddressNode offsetAdressNode : loop.whole().nodes().filter(OffsetAddressNode.class)) {
132 tryOptimize(offsetAdressNode, loop);
133 }
134 }
135 }
136 }
137
138 @Override
139 public void postProcess(AddressNode lowered) {
140 // Allow implicit zero extend for always positive input. This
141 // assumes that the upper bits of the operand is zero out by
142 // the backend.
143 AMD64AddressNode address = (AMD64AddressNode) lowered;
144 address.setBase(tryImplicitZeroExtend(address.getBase()));
145 address.setIndex(tryImplicitZeroExtend(address.getIndex()));
146 }
147
148 private static void tryOptimize(OffsetAddressNode offsetAddress, LoopEx loop) {
149 EconomicMap<Node, InductionVariable> ivs = loop.getInductionVariables();
150 InductionVariable currentIV = ivs.get(offsetAddress.getOffset());
151 while (currentIV != null) {
152 if (!(currentIV instanceof DerivedInductionVariable)) {
153 break;
154 }
155 ValueNode currentValue = currentIV.valueNode();
156 if (currentValue.isDeleted()) {
157 break;
158 }
159
160 if (currentValue instanceof ZeroExtendNode) {
161 ZeroExtendNode zeroExtendNode = (ZeroExtendNode) currentValue;
162 if (applicableToImplicitZeroExtend(zeroExtendNode)) {
163 ValueNode input = zeroExtendNode.getValue();
164 if (input instanceof AddNode) {
165 AddNode add = (AddNode) input;
166 if (add.getX().isConstant()) {
167 optimizeAdd(zeroExtendNode, (ConstantNode) add.getX(), add.getY(), loop);
168 } else if (add.getY().isConstant()) {
169 optimizeAdd(zeroExtendNode, (ConstantNode) add.getY(), add.getX(), loop);
170 }
171 }
172 }
173 }
174
175 currentIV = ((DerivedInductionVariable) currentIV).getBase();
176 }
177 }
178
179 /**
180 * Given that Add(a, cst) is always positive, performs the following: ZeroExtend(Add(a, cst)) ->
181 * Add(SignExtend(a), SignExtend(cst)).
182 */
183 private static void optimizeAdd(ZeroExtendNode zeroExtendNode, ConstantNode constant, ValueNode other, LoopEx loop) {
184 StructuredGraph graph = zeroExtendNode.graph();
185 AddNode addNode = graph.unique(new AddNode(signExtend(other, loop), ConstantNode.forLong(constant.asJavaConstant().asInt(), graph)));
186 zeroExtendNode.replaceAtUsages(addNode);
187 }
188
189 /**
190 * Create a sign extend for {@code input}, or zero extend if {@code input} can be proven
191 * positive.
192 */
193 private static ValueNode signExtend(ValueNode input, LoopEx loop) {
194 StructuredGraph graph = input.graph();
195 if (input instanceof PhiNode) {
196 EconomicMap<Node, InductionVariable> ivs = loop.getInductionVariables();
197 InductionVariable inductionVariable = ivs.get(input);
198 if (inductionVariable != null && inductionVariable instanceof BasicInductionVariable) {
199 CountedLoopInfo countedLoopInfo = loop.counted();
200 IntegerStamp initStamp = (IntegerStamp) inductionVariable.initNode().stamp(NodeView.DEFAULT);
201 if (initStamp.isPositive()) {
202 if (inductionVariable.isConstantExtremum()) {
203 long init = inductionVariable.constantInit();
204 long stride = inductionVariable.constantStride();
205 long extremum = inductionVariable.constantExtremum();
206
207 if (init >= 0 && extremum >= 0) {
208 long shortestTrip = (extremum - init) / stride + 1;
209 if (countedLoopInfo.constantMaxTripCount().equals(shortestTrip)) {
210 return graph.unique(new ZeroExtendNode(input, INT_BITS, ADDRESS_BITS, true));
211 }
212 }
213 }
214 if (countedLoopInfo.getCounter() == inductionVariable && inductionVariable.direction() == InductionVariable.Direction.Up && countedLoopInfo.getOverFlowGuard() != null) {
215 return graph.unique(new ZeroExtendNode(input, INT_BITS, ADDRESS_BITS, true));
216 }
217 }
218 }
219 }
220 return input.graph().maybeAddOrUnique(SignExtendNode.create(input, ADDRESS_BITS, NodeView.DEFAULT));
221 }
222
223 private static boolean applicableToImplicitZeroExtend(ZeroExtendNode zeroExtendNode) {
224 return zeroExtendNode.isInputAlwaysPositive() && zeroExtendNode.getInputBits() == INT_BITS && zeroExtendNode.getResultBits() == ADDRESS_BITS;
225 }
226
227 private static ValueNode tryImplicitZeroExtend(ValueNode input) {
228 if (input instanceof ZeroExtendNode) {
229 ZeroExtendNode zeroExtendNode = (ZeroExtendNode) input;
230 if (applicableToImplicitZeroExtend(zeroExtendNode)) {
231 return zeroExtendNode.getValue();
232 }
233 }
234 return input;
235 }
236
237 }