1 /*
2  * Copyright (c) 2015, 2018, 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 
AMD64HotSpotAddressLowering(GraalHotSpotVMConfig config, Register heapBaseRegister, OptionValues options)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
improveUncompression(AMD64AddressNode addr, CompressionNode compression, ValueNode other)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
preProcess(StructuredGraph graph)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
postProcess(AddressNode lowered)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 
tryOptimize(OffsetAddressNode offsetAddress, LoopEx loop)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      */
optimizeAdd(ZeroExtendNode zeroExtendNode, ConstantNode constant, ValueNode other, LoopEx loop)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      */
signExtend(ValueNode input, LoopEx loop)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() && countedLoopInfo.counterNeverOverflows()) {
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 &&
215                                     inductionVariable.direction() == InductionVariable.Direction.Up &&
216                                     (countedLoopInfo.getOverFlowGuard() != null || countedLoopInfo.counterNeverOverflows())) {
217                         return graph.unique(new ZeroExtendNode(input, INT_BITS, ADDRESS_BITS, true));
218                     }
219                 }
220             }
221         }
222         return input.graph().maybeAddOrUnique(SignExtendNode.create(input, ADDRESS_BITS, NodeView.DEFAULT));
223     }
224 
applicableToImplicitZeroExtend(ZeroExtendNode zeroExtendNode)225     private static boolean applicableToImplicitZeroExtend(ZeroExtendNode zeroExtendNode) {
226         return zeroExtendNode.isInputAlwaysPositive() && zeroExtendNode.getInputBits() == INT_BITS && zeroExtendNode.getResultBits() == ADDRESS_BITS;
227     }
228 
tryImplicitZeroExtend(ValueNode input)229     private static ValueNode tryImplicitZeroExtend(ValueNode input) {
230         if (input instanceof ZeroExtendNode) {
231             ZeroExtendNode zeroExtendNode = (ZeroExtendNode) input;
232             if (applicableToImplicitZeroExtend(zeroExtendNode)) {
233                 return zeroExtendNode.getValue();
234             }
235         }
236         return input;
237     }
238 
239 }
240