1 /*
2 * Copyright (c) 2014, 2017, 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.phases.common;
24
25 import static org.graalvm.compiler.core.common.GraalOptions.OptImplicitNullChecks;
26
27 import java.util.List;
28
29 import org.graalvm.compiler.debug.CounterKey;
30 import org.graalvm.compiler.debug.DebugContext;
31 import org.graalvm.compiler.graph.Node;
32 import org.graalvm.compiler.nodeinfo.InputType;
33 import org.graalvm.compiler.nodes.AbstractBeginNode;
34 import org.graalvm.compiler.nodes.AbstractDeoptimizeNode;
35 import org.graalvm.compiler.nodes.AbstractEndNode;
36 import org.graalvm.compiler.nodes.AbstractMergeNode;
37 import org.graalvm.compiler.nodes.BeginNode;
38 import org.graalvm.compiler.nodes.DeoptimizeNode;
39 import org.graalvm.compiler.nodes.DeoptimizingFixedWithNextNode;
40 import org.graalvm.compiler.nodes.DynamicDeoptimizeNode;
41 import org.graalvm.compiler.nodes.FixedNode;
42 import org.graalvm.compiler.nodes.IfNode;
43 import org.graalvm.compiler.nodes.LogicNode;
44 import org.graalvm.compiler.nodes.StructuredGraph;
45 import org.graalvm.compiler.nodes.ValueNode;
46 import org.graalvm.compiler.nodes.ValuePhiNode;
47 import org.graalvm.compiler.nodes.calc.IsNullNode;
48 import org.graalvm.compiler.nodes.extended.NullCheckNode;
49 import org.graalvm.compiler.nodes.memory.FixedAccessNode;
50 import org.graalvm.compiler.nodes.memory.address.AddressNode;
51 import org.graalvm.compiler.nodes.util.GraphUtil;
52 import org.graalvm.compiler.phases.BasePhase;
53 import org.graalvm.compiler.phases.tiers.LowTierContext;
54
55 import jdk.vm.ci.meta.DeoptimizationReason;
56 import jdk.vm.ci.meta.JavaConstant;
57 import jdk.vm.ci.meta.MetaAccessProvider;
58
59 public class UseTrappingNullChecksPhase extends BasePhase<LowTierContext> {
60
61 private static final CounterKey counterTrappingNullCheck = DebugContext.counter("TrappingNullCheck");
62 private static final CounterKey counterTrappingNullCheckExistingRead = DebugContext.counter("TrappingNullCheckExistingRead");
63 private static final CounterKey counterTrappingNullCheckUnreached = DebugContext.counter("TrappingNullCheckUnreached");
64 private static final CounterKey counterTrappingNullCheckDynamicDeoptimize = DebugContext.counter("TrappingNullCheckDynamicDeoptimize");
65
66 @Override
67 protected void run(StructuredGraph graph, LowTierContext context) {
68 if (context.getTarget().implicitNullCheckLimit <= 0) {
69 return;
70 }
71 assert graph.getGuardsStage().areFrameStatesAtDeopts();
72
73 long implicitNullCheckLimit = context.getTarget().implicitNullCheckLimit;
74 for (DeoptimizeNode deopt : graph.getNodes(DeoptimizeNode.TYPE)) {
75 tryUseTrappingNullCheck(deopt, deopt.predecessor(), deopt.reason(), deopt.getSpeculation(), implicitNullCheckLimit);
76 }
77 for (DynamicDeoptimizeNode deopt : graph.getNodes(DynamicDeoptimizeNode.TYPE)) {
78 tryUseTrappingNullCheck(context.getMetaAccess(), deopt, implicitNullCheckLimit);
79 }
80
81 }
82
83 private static void tryUseTrappingNullCheck(MetaAccessProvider metaAccessProvider, DynamicDeoptimizeNode deopt, long implicitNullCheckLimit) {
84 Node predecessor = deopt.predecessor();
85 if (predecessor instanceof AbstractMergeNode) {
86 AbstractMergeNode merge = (AbstractMergeNode) predecessor;
87
88 // Process each predecessor at the merge, unpacking the reasons and speculations as
89 // needed.
90 ValueNode reason = deopt.getActionAndReason();
91 ValuePhiNode reasonPhi = null;
92 List<ValueNode> reasons = null;
93 int expectedPhis = 0;
94
95 if (reason instanceof ValuePhiNode) {
96 reasonPhi = (ValuePhiNode) reason;
97 if (reasonPhi.merge() != merge) {
98 return;
99 }
100 reasons = reasonPhi.values().snapshot();
101 expectedPhis++;
102 } else if (!reason.isConstant()) {
103 return;
104 }
105
106 ValueNode speculation = deopt.getSpeculation();
107 ValuePhiNode speculationPhi = null;
108 List<ValueNode> speculations = null;
109 if (speculation instanceof ValuePhiNode) {
110 speculationPhi = (ValuePhiNode) speculation;
111 if (speculationPhi.merge() != merge) {
112 return;
113 }
114 speculations = speculationPhi.values().snapshot();
115 expectedPhis++;
116 }
117
118 if (merge.phis().count() != expectedPhis) {
119 return;
120 }
121
122 int index = 0;
123 for (AbstractEndNode end : merge.cfgPredecessors().snapshot()) {
124 ValueNode thisReason = reasons != null ? reasons.get(index) : reason;
125 ValueNode thisSpeculation = speculations != null ? speculations.get(index++) : speculation;
126 if (!thisReason.isConstant() || !thisSpeculation.isConstant() || !thisSpeculation.asConstant().equals(JavaConstant.NULL_POINTER)) {
127 continue;
128 }
129 DeoptimizationReason deoptimizationReason = metaAccessProvider.decodeDeoptReason(thisReason.asJavaConstant());
130 tryUseTrappingNullCheck(deopt, end.predecessor(), deoptimizationReason, null, implicitNullCheckLimit);
131 }
132 }
133 }
134
135 private static void tryUseTrappingNullCheck(AbstractDeoptimizeNode deopt, Node predecessor, DeoptimizationReason deoptimizationReason, JavaConstant speculation, long implicitNullCheckLimit) {
136 if (deoptimizationReason != DeoptimizationReason.NullCheckException && deoptimizationReason != DeoptimizationReason.UnreachedCode) {
137 return;
138 }
139 if (speculation != null && !speculation.equals(JavaConstant.NULL_POINTER)) {
140 return;
141 }
142 if (predecessor instanceof AbstractMergeNode) {
143 AbstractMergeNode merge = (AbstractMergeNode) predecessor;
144 if (merge.phis().isEmpty()) {
145 for (AbstractEndNode end : merge.cfgPredecessors().snapshot()) {
146 checkPredecessor(deopt, end.predecessor(), deoptimizationReason, implicitNullCheckLimit);
147 }
148 }
149 } else if (predecessor instanceof AbstractBeginNode) {
150 checkPredecessor(deopt, predecessor, deoptimizationReason, implicitNullCheckLimit);
151 }
152 }
153
154 private static void checkPredecessor(AbstractDeoptimizeNode deopt, Node predecessor, DeoptimizationReason deoptimizationReason, long implicitNullCheckLimit) {
155 Node current = predecessor;
156 AbstractBeginNode branch = null;
157 while (current instanceof AbstractBeginNode) {
158 branch = (AbstractBeginNode) current;
159 if (branch.anchored().isNotEmpty()) {
160 // some input of the deopt framestate is anchored to this branch
161 return;
162 }
163 current = current.predecessor();
164 }
165 if (current instanceof IfNode) {
166 IfNode ifNode = (IfNode) current;
167 if (branch != ifNode.trueSuccessor()) {
168 return;
169 }
170 LogicNode condition = ifNode.condition();
171 if (condition instanceof IsNullNode) {
172 replaceWithTrappingNullCheck(deopt, ifNode, condition, deoptimizationReason, implicitNullCheckLimit);
173 }
174 }
175 }
176
177 private static void replaceWithTrappingNullCheck(AbstractDeoptimizeNode deopt, IfNode ifNode, LogicNode condition, DeoptimizationReason deoptimizationReason, long implicitNullCheckLimit) {
178 DebugContext debug = deopt.getDebug();
179 counterTrappingNullCheck.increment(debug);
180 if (deopt instanceof DynamicDeoptimizeNode) {
181 counterTrappingNullCheckDynamicDeoptimize.increment(debug);
182 }
183 if (deoptimizationReason == DeoptimizationReason.UnreachedCode) {
184 counterTrappingNullCheckUnreached.increment(debug);
185 }
186 IsNullNode isNullNode = (IsNullNode) condition;
187 AbstractBeginNode nonTrappingContinuation = ifNode.falseSuccessor();
188 AbstractBeginNode trappingContinuation = ifNode.trueSuccessor();
189
190 DeoptimizingFixedWithNextNode trappingNullCheck = null;
191 FixedNode nextNonTrapping = nonTrappingContinuation.next();
192 ValueNode value = isNullNode.getValue();
193 if (OptImplicitNullChecks.getValue(ifNode.graph().getOptions()) && implicitNullCheckLimit > 0) {
194 if (nextNonTrapping instanceof FixedAccessNode) {
195 FixedAccessNode fixedAccessNode = (FixedAccessNode) nextNonTrapping;
196 if (fixedAccessNode.canNullCheck()) {
197 AddressNode address = fixedAccessNode.getAddress();
198 ValueNode base = address.getBase();
199 ValueNode index = address.getIndex();
200 if (((base == value && index == null) || (base == null && index == value)) && address.getMaxConstantDisplacement() < implicitNullCheckLimit) {
201 // Opportunity for implicit null check as part of an existing read found!
202 fixedAccessNode.setStateBefore(deopt.stateBefore());
203 fixedAccessNode.setNullCheck(true);
204 deopt.graph().removeSplit(ifNode, nonTrappingContinuation);
205 trappingNullCheck = fixedAccessNode;
206 counterTrappingNullCheckExistingRead.increment(debug);
207 }
208 }
209 }
210 }
211
212 if (trappingNullCheck == null) {
213 // Need to add a null check node.
214 trappingNullCheck = deopt.graph().add(new NullCheckNode(value));
215 deopt.graph().replaceSplit(ifNode, trappingNullCheck, nonTrappingContinuation);
216 }
217
218 trappingNullCheck.setStateBefore(deopt.stateBefore());
219
220 /*
221 * We now have the pattern NullCheck/BeginNode/... It's possible some node is using the
222 * BeginNode as a guard input, so replace guard users of the Begin with the NullCheck and
223 * then remove the Begin from the graph.
224 */
225 nonTrappingContinuation.replaceAtUsages(InputType.Guard, trappingNullCheck);
226
227 if (nonTrappingContinuation instanceof BeginNode) {
228 GraphUtil.unlinkFixedNode(nonTrappingContinuation);
229 nonTrappingContinuation.safeDelete();
230 }
231
232 GraphUtil.killCFG(trappingContinuation);
233 GraphUtil.tryKillUnused(isNullNode);
234 }
235 }