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