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 package org.graalvm.compiler.nodes;
26
27 import static org.graalvm.compiler.nodeinfo.InputType.Guard;
28 import static org.graalvm.compiler.nodeinfo.NodeCycles.CYCLES_IGNORED;
29 import static org.graalvm.compiler.nodeinfo.NodeSize.SIZE_IGNORED;
30
31 import java.util.List;
32
33 import org.graalvm.compiler.core.common.spi.ConstantFieldProvider;
34 import org.graalvm.compiler.core.common.type.Stamp;
35 import org.graalvm.compiler.debug.DebugCloseable;
36 import org.graalvm.compiler.graph.Node;
37 import org.graalvm.compiler.graph.NodeClass;
38 import org.graalvm.compiler.graph.spi.Canonicalizable;
39 import org.graalvm.compiler.graph.spi.CanonicalizerTool;
40 import org.graalvm.compiler.nodeinfo.NodeInfo;
41 import org.graalvm.compiler.nodes.calc.FloatingNode;
42 import org.graalvm.compiler.nodes.extended.GuardingNode;
43 import org.graalvm.compiler.nodes.extended.IntegerSwitchNode;
44 import org.graalvm.compiler.nodes.java.ArrayLengthNode;
45 import org.graalvm.compiler.nodes.java.LoadFieldNode;
46 import org.graalvm.compiler.nodes.java.LoadIndexedNode;
47 import org.graalvm.compiler.nodes.spi.StampProvider;
48 import org.graalvm.compiler.nodes.util.GraphUtil;
49 import org.graalvm.compiler.options.OptionValues;
50
51 import jdk.vm.ci.code.Architecture;
52 import jdk.vm.ci.meta.Assumptions;
53 import jdk.vm.ci.meta.ConstantReflectionProvider;
54 import jdk.vm.ci.meta.MetaAccessProvider;
55
56 /**
57 * Graph decoder that simplifies nodes during decoding. The standard
58 * {@link Canonicalizable#canonical node canonicalization} interface is used to canonicalize nodes
59 * during decoding. Additionally, {@link IfNode branches} and {@link IntegerSwitchNode switches}
60 * with constant conditions are simplified.
61 */
62 public class SimplifyingGraphDecoder extends GraphDecoder {
63
64 protected final MetaAccessProvider metaAccess;
65 protected final ConstantReflectionProvider constantReflection;
66 protected final ConstantFieldProvider constantFieldProvider;
67 protected final StampProvider stampProvider;
68 protected final boolean canonicalizeReads;
69 protected final CanonicalizerTool canonicalizerTool;
70
71 protected class PECanonicalizerTool implements CanonicalizerTool {
72
73 private final Assumptions assumptions;
74 private final OptionValues options;
75
76 public PECanonicalizerTool(Assumptions assumptions, OptionValues options) {
77 this.assumptions = assumptions;
78 this.options = options;
79 }
80
81 @Override
82 public OptionValues getOptions() {
83 return options;
84 }
85
86 @Override
87 public MetaAccessProvider getMetaAccess() {
88 return metaAccess;
89 }
90
91 @Override
92 public ConstantReflectionProvider getConstantReflection() {
93 return constantReflection;
94 }
95
96 @Override
97 public ConstantFieldProvider getConstantFieldProvider() {
98 return constantFieldProvider;
99 }
100
101 @Override
102 public boolean canonicalizeReads() {
103 return canonicalizeReads;
104 }
105
106 @Override
107 public boolean allUsagesAvailable() {
108 return false;
109 }
110
111 @Override
112 public Assumptions getAssumptions() {
113 return assumptions;
114 }
115
116 @Override
117 public Integer smallestCompareWidth() {
118 // to be safe, just report null here
119 // there will be more opportunities for this optimization later
120 return null;
121 }
122 }
123
124 @NodeInfo(cycles = CYCLES_IGNORED, size = SIZE_IGNORED, allowedUsageTypes = {Guard})
125 static class CanonicalizeToNullNode extends FloatingNode implements Canonicalizable, GuardingNode {
126 public static final NodeClass<CanonicalizeToNullNode> TYPE = NodeClass.create(CanonicalizeToNullNode.class);
127
128 protected CanonicalizeToNullNode(Stamp stamp) {
129 super(TYPE, stamp);
130 }
131
132 @Override
133 public Node canonical(CanonicalizerTool tool) {
134 return null;
135 }
136 }
137
138 public SimplifyingGraphDecoder(Architecture architecture, StructuredGraph graph, MetaAccessProvider metaAccess, ConstantReflectionProvider constantReflection,
139 ConstantFieldProvider constantFieldProvider, StampProvider stampProvider,
140 boolean canonicalizeReads) {
141 super(architecture, graph);
142 this.metaAccess = metaAccess;
143 this.constantReflection = constantReflection;
144 this.constantFieldProvider = constantFieldProvider;
145 this.stampProvider = stampProvider;
146 this.canonicalizeReads = canonicalizeReads;
147 this.canonicalizerTool = new PECanonicalizerTool(graph.getAssumptions(), graph.getOptions());
148 }
149
150 @Override
151 protected void cleanupGraph(MethodScope methodScope) {
152 GraphUtil.normalizeLoops(graph);
153 super.cleanupGraph(methodScope);
154
155 for (Node node : graph.getNewNodes(methodScope.methodStartMark)) {
156 if (node instanceof MergeNode) {
157 MergeNode mergeNode = (MergeNode) node;
158 if (mergeNode.forwardEndCount() == 1) {
159 graph.reduceTrivialMerge(mergeNode);
160 }
161 } else if (node instanceof BeginNode || node instanceof KillingBeginNode) {
162 if (!(node.predecessor() instanceof ControlSplitNode) && node.hasNoUsages()) {
163 GraphUtil.unlinkFixedNode((AbstractBeginNode) node);
164 node.safeDelete();
165 }
166 }
167 }
168
169 for (Node node : graph.getNewNodes(methodScope.methodStartMark)) {
170 GraphUtil.tryKillUnused(node);
171 }
172 }
173
174 @Override
175 protected boolean allowLazyPhis() {
176 /*
177 * We do not need to exactly reproduce the encoded graph, so we want to avoid unnecessary
178 * phi functions.
179 */
180 return true;
181 }
182
183 @Override
184 protected void handleMergeNode(MergeNode merge) {
185 /*
186 * All inputs of non-loop phi nodes are known by now. We can infer the stamp for the phi, so
187 * that parsing continues with more precise type information.
188 */
189 for (ValuePhiNode phi : merge.valuePhis()) {
190 phi.inferStamp();
191 }
192 }
193
194 @Override
195 protected void handleFixedNode(MethodScope methodScope, LoopScope loopScope, int nodeOrderId, FixedNode node) {
196 Node canonical = canonicalizeFixedNode(methodScope, node);
197 if (canonical != node) {
198 handleCanonicalization(loopScope, nodeOrderId, node, canonical);
199 }
200 }
201
202 /**
203 * Canonicalizes the provided node, which was originally a {@link FixedNode} but can already be
204 * canonicalized (and therefore be a non-fixed node).
205 *
206 * @param methodScope The current method.
207 * @param node The node to be canonicalized.
208 */
209 protected Node canonicalizeFixedNode(MethodScope methodScope, Node node) {
210 if (node instanceof LoadFieldNode) {
211 LoadFieldNode loadFieldNode = (LoadFieldNode) node;
212 return loadFieldNode.canonical(canonicalizerTool);
213 } else if (node instanceof FixedGuardNode) {
214 FixedGuardNode guard = (FixedGuardNode) node;
215 if (guard.getCondition() instanceof LogicConstantNode) {
216 LogicConstantNode condition = (LogicConstantNode) guard.getCondition();
217 if (condition.getValue() == guard.isNegated()) {
218 DeoptimizeNode deopt = new DeoptimizeNode(guard.getAction(), guard.getReason(), guard.getSpeculation());
219 if (guard.stateBefore() != null) {
220 deopt.setStateBefore(guard.stateBefore());
221 }
222 return deopt;
223 } else {
224 return null;
225 }
226 }
227 return node;
228 } else if (node instanceof IfNode) {
229 IfNode ifNode = (IfNode) node;
230 if (ifNode.condition() instanceof LogicNegationNode) {
231 ifNode.eliminateNegation();
232 }
233 if (ifNode.condition() instanceof LogicConstantNode) {
234 boolean condition = ((LogicConstantNode) ifNode.condition()).getValue();
235 AbstractBeginNode survivingSuccessor = ifNode.getSuccessor(condition);
236 AbstractBeginNode deadSuccessor = ifNode.getSuccessor(!condition);
237
238 graph.removeSplit(ifNode, survivingSuccessor);
239 assert deadSuccessor.next() == null : "must not be parsed yet";
240 deadSuccessor.safeDelete();
241 }
242 return node;
243 } else if (node instanceof LoadIndexedNode) {
244 LoadIndexedNode loadIndexedNode = (LoadIndexedNode) node;
245 return loadIndexedNode.canonical(canonicalizerTool);
246 } else if (node instanceof ArrayLengthNode) {
247 ArrayLengthNode arrayLengthNode = (ArrayLengthNode) node;
248 return arrayLengthNode.canonical(canonicalizerTool);
249 } else if (node instanceof IntegerSwitchNode && ((IntegerSwitchNode) node).value().isConstant()) {
250 IntegerSwitchNode switchNode = (IntegerSwitchNode) node;
251 int value = switchNode.value().asJavaConstant().asInt();
252 AbstractBeginNode survivingSuccessor = switchNode.successorAtKey(value);
253 List<Node> allSuccessors = switchNode.successors().snapshot();
254
255 graph.removeSplit(switchNode, survivingSuccessor);
256 for (Node successor : allSuccessors) {
257 if (successor != survivingSuccessor) {
258 assert ((AbstractBeginNode) successor).next() == null : "must not be parsed yet";
259 successor.safeDelete();
260 }
261 }
262 return node;
263 } else if (node instanceof Canonicalizable) {
264 return ((Canonicalizable) node).canonical(canonicalizerTool);
265 } else {
266 return node;
267 }
268 }
269
270 private static Node canonicalizeFixedNodeToNull(FixedNode node) {
271 /*
272 * When a node is unnecessary, we must not remove it right away because there might be nodes
273 * that use it as a guard input. Therefore, we replace it with a more lightweight node
274 * (which is floating and has no inputs).
275 */
276 return new CanonicalizeToNullNode(node.stamp);
277 }
278
279 @SuppressWarnings("try")
280 private void handleCanonicalization(LoopScope loopScope, int nodeOrderId, FixedNode node, Node c) {
281 assert c != node : "unnecessary call";
282 try (DebugCloseable position = graph.withNodeSourcePosition(node)) {
283 Node canonical = c == null ? canonicalizeFixedNodeToNull(node) : c;
284 if (!canonical.isAlive()) {
285 assert !canonical.isDeleted();
286 canonical = graph.addOrUniqueWithInputs(canonical);
287 if (canonical instanceof FixedWithNextNode) {
288 graph.addBeforeFixed(node, (FixedWithNextNode) canonical);
289 } else if (canonical instanceof ControlSinkNode) {
290 FixedWithNextNode predecessor = (FixedWithNextNode) node.predecessor();
291 predecessor.setNext((ControlSinkNode) canonical);
292 List<Node> successorSnapshot = node.successors().snapshot();
293 node.safeDelete();
294 for (Node successor : successorSnapshot) {
295 successor.safeDelete();
296 }
297 } else {
298 assert !(canonical instanceof FixedNode);
299 }
300 }
301 if (!node.isDeleted()) {
302 GraphUtil.unlinkFixedNode((FixedWithNextNode) node);
303 node.replaceAtUsagesAndDelete(canonical);
304 }
305 assert lookupNode(loopScope, nodeOrderId) == node;
306 registerNode(loopScope, nodeOrderId, canonical, true, false);
307 }
308 }
309
310 @Override
311 @SuppressWarnings("try")
312 protected Node handleFloatingNodeBeforeAdd(MethodScope methodScope, LoopScope loopScope, Node node) {
313 if (node instanceof ValueNode) {
314 ((ValueNode) node).inferStamp();
315 }
316 if (node instanceof Canonicalizable) {
317 try (DebugCloseable context = graph.withNodeSourcePosition(node)) {
318 Node canonical = ((Canonicalizable) node).canonical(canonicalizerTool);
319 if (canonical == null) {
320 /*
321 * This is a possible return value of canonicalization. However, we might need
322 * to add additional usages later on for which we need a node. Therefore, we
323 * just do nothing and leave the node in place.
324 */
325 } else if (canonical != node) {
326 if (!canonical.isAlive()) {
327 assert !canonical.isDeleted();
328 canonical = graph.addOrUniqueWithInputs(canonical);
329 }
330 assert node.hasNoUsages();
331 return canonical;
332 }
333 }
334 }
335 return node;
336 }
337
338 @Override
339 protected Node addFloatingNode(MethodScope methodScope, Node node) {
340 /*
341 * In contrast to the base class implementation, we do not need to exactly reproduce the
342 * encoded graph. Since we do canonicalization, we also want nodes to be unique.
343 */
344 return graph.addOrUnique(node);
345 }
346 }