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