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 GraphUtil.tryKillUnused(node);
157 }
158 }
159
160 @Override
161 protected boolean allowLazyPhis() {
162 /*
163 * We do not need to exactly reproduce the encoded graph, so we want to avoid unnecessary
164 * phi functions.
165 */
166 return true;
167 }
168
169 @Override
170 protected void handleMergeNode(MergeNode merge) {
171 /*
172 * All inputs of non-loop phi nodes are known by now. We can infer the stamp for the phi, so
173 * that parsing continues with more precise type information.
174 */
175 for (ValuePhiNode phi : merge.valuePhis()) {
176 phi.inferStamp();
177 }
178 }
179
180 @Override
181 protected void handleFixedNode(MethodScope methodScope, LoopScope loopScope, int nodeOrderId, FixedNode node) {
182 if (node instanceof IfNode) {
183 IfNode ifNode = (IfNode) node;
184 if (ifNode.condition() instanceof LogicNegationNode) {
185 ifNode.eliminateNegation();
186 }
187 if (ifNode.condition() instanceof LogicConstantNode) {
188 boolean condition = ((LogicConstantNode) ifNode.condition()).getValue();
189 AbstractBeginNode survivingSuccessor = ifNode.getSuccessor(condition);
190 AbstractBeginNode deadSuccessor = ifNode.getSuccessor(!condition);
191
192 methodScope.graph.removeSplit(ifNode, survivingSuccessor);
193 assert deadSuccessor.next() == null : "must not be parsed yet";
194 deadSuccessor.safeDelete();
195 }
196
197 } else if (node instanceof IntegerSwitchNode && ((IntegerSwitchNode) node).value().isConstant()) {
198 IntegerSwitchNode switchNode = (IntegerSwitchNode) node;
199 int value = switchNode.value().asJavaConstant().asInt();
200 AbstractBeginNode survivingSuccessor = switchNode.successorAtKey(value);
201 List<Node> allSuccessors = switchNode.successors().snapshot();
202
203 methodScope.graph.removeSplit(switchNode, survivingSuccessor);
204 for (Node successor : allSuccessors) {
205 if (successor != survivingSuccessor) {
206 assert ((AbstractBeginNode) successor).next() == null : "must not be parsed yet";
207 successor.safeDelete();
208 }
209 }
210
211 } else if (node instanceof FixedGuardNode) {
212 FixedGuardNode guard = (FixedGuardNode) node;
213 if (guard.getCondition() instanceof LogicConstantNode) {
214 LogicConstantNode condition = (LogicConstantNode) guard.getCondition();
215 Node canonical;
216 if (condition.getValue() == guard.isNegated()) {
217 DeoptimizeNode deopt = new DeoptimizeNode(guard.getAction(), guard.getReason(), guard.getSpeculation());
218 if (guard.stateBefore() != null) {
219 deopt.setStateBefore(guard.stateBefore());
220 }
221 canonical = deopt;
222 } else {
223 /*
224 * The guard is unnecessary, but we cannot remove the node completely yet
225 * because there might be nodes that use it as a guard input. Therefore, we
226 * replace it with a more lightweight node (which is floating and has no
227 * inputs).
228 */
229 canonical = new CanonicalizeToNullNode(node.stamp);
230 }
231 handleCanonicalization(methodScope, loopScope, nodeOrderId, node, canonical);
232 }
233
234 } else if (node instanceof Canonicalizable) {
235 Node canonical = ((Canonicalizable) node).canonical(new PECanonicalizerTool(methodScope.graph.getAssumptions()));
236 if (canonical != node) {
237 handleCanonicalization(methodScope, loopScope, nodeOrderId, node, canonical);
238 }
239 }
240 }
241
242 private void handleCanonicalization(MethodScope methodScope, LoopScope loopScope, int nodeOrderId, FixedNode node, Node c) {
243 Node canonical = c;
244
245 if (canonical == null) {
246 /*
247 * This is a possible return value of canonicalization. However, we might need to add
248 * additional usages later on for which we need a node. Therefore, we just do nothing
249 * and leave the node in place.
250 */
251 return;
252 }
253
254 if (!canonical.isAlive()) {
255 assert !canonical.isDeleted();
256 canonical = methodScope.graph.addOrUniqueWithInputs(canonical);
257 if (canonical instanceof FixedWithNextNode) {
258 methodScope.graph.addBeforeFixed(node, (FixedWithNextNode) canonical);
259 } else if (canonical instanceof ControlSinkNode) {
260 FixedWithNextNode predecessor = (FixedWithNextNode) node.predecessor();
261 predecessor.setNext((ControlSinkNode) canonical);
262 List<Node> successorSnapshot = node.successors().snapshot();
263 node.safeDelete();
264 for (Node successor : successorSnapshot) {
265 successor.safeDelete();
266 }
267
268 } else {
269 assert !(canonical instanceof FixedNode);
270 }
271 }
272 if (!node.isDeleted()) {
273 GraphUtil.unlinkFixedNode((FixedWithNextNode) node);
274 node.replaceAtUsagesAndDelete(canonical);
275 }
276 assert lookupNode(loopScope, nodeOrderId) == node;
277 registerNode(loopScope, nodeOrderId, canonical, true, false);
278 }
279
280 @Override
281 protected Node handleFloatingNodeBeforeAdd(MethodScope methodScope, LoopScope loopScope, Node node) {
282 if (node instanceof ValueNode) {
283 ((ValueNode) node).inferStamp();
284 }
285 if (node instanceof Canonicalizable) {
286 Node canonical = ((Canonicalizable) node).canonical(new PECanonicalizerTool(methodScope.graph.getAssumptions()));
287 if (canonical == null) {
288 /*
289 * This is a possible return value of canonicalization. However, we might need to
290 * add additional usages later on for which we need a node. Therefore, we just do
291 * nothing and leave the node in place.
292 */
293 } else if (canonical != node) {
294 if (!canonical.isAlive()) {
295 assert !canonical.isDeleted();
296 canonical = methodScope.graph.addOrUniqueWithInputs(canonical);
297 }
298 assert node.hasNoUsages();
299 // methodScope.graph.replaceFloating((FloatingNode) node, canonical);
300 return canonical;
301 }
302 }
303 return node;
304 }
305
306 @Override
307 protected Node addFloatingNode(MethodScope methodScope, Node node) {
308 /*
309 * In contrast to the base class implementation, we do not need to exactly reproduce the
310 * encoded graph. Since we do canonicalization, we also want nodes to be unique.
311 */
312 return methodScope.graph.addOrUnique(node);
313 }
314 }