1 /*
2 * Copyright (c) 2014, 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.phases.common;
26
27 import static org.graalvm.compiler.core.common.GraalOptions.OptImplicitNullChecks;
28
29 import java.util.List;
30
31 import org.graalvm.compiler.debug.CounterKey;
32 import org.graalvm.compiler.debug.DebugContext;
33 import org.graalvm.compiler.graph.Node;
34 import org.graalvm.compiler.nodeinfo.InputType;
35 import org.graalvm.compiler.nodes.AbstractBeginNode;
36 import org.graalvm.compiler.nodes.AbstractDeoptimizeNode;
37 import org.graalvm.compiler.nodes.AbstractEndNode;
38 import org.graalvm.compiler.nodes.AbstractMergeNode;
39 import org.graalvm.compiler.nodes.BeginNode;
40 import org.graalvm.compiler.nodes.CompressionNode;
41 import org.graalvm.compiler.nodes.DeoptimizeNode;
42 import org.graalvm.compiler.nodes.DeoptimizingFixedWithNextNode;
43 import org.graalvm.compiler.nodes.DynamicDeoptimizeNode;
44 import org.graalvm.compiler.nodes.EndNode;
45 import org.graalvm.compiler.nodes.FixedNode;
46 import org.graalvm.compiler.nodes.IfNode;
47 import org.graalvm.compiler.nodes.LogicNode;
48 import org.graalvm.compiler.nodes.StructuredGraph;
49 import org.graalvm.compiler.nodes.ValueNode;
50 import org.graalvm.compiler.nodes.ValuePhiNode;
51 import org.graalvm.compiler.nodes.calc.IsNullNode;
52 import org.graalvm.compiler.nodes.extended.NullCheckNode;
53 import org.graalvm.compiler.nodes.memory.FixedAccessNode;
54 import org.graalvm.compiler.nodes.memory.address.AddressNode;
55 import org.graalvm.compiler.nodes.util.GraphUtil;
56 import org.graalvm.compiler.options.Option;
57 import org.graalvm.compiler.options.OptionKey;
58 import org.graalvm.compiler.options.OptionType;
59 import org.graalvm.compiler.phases.BasePhase;
60 import org.graalvm.compiler.phases.tiers.LowTierContext;
61
62 import jdk.vm.ci.meta.DeoptimizationReason;
63 import jdk.vm.ci.meta.MetaAccessProvider;
64 import jdk.vm.ci.meta.SpeculationLog;
65 import jdk.vm.ci.meta.SpeculationLog.Speculation;
66
67 public class UseTrappingNullChecksPhase extends BasePhase<LowTierContext> {
68
69 private static final CounterKey counterTrappingNullCheck = DebugContext.counter("TrappingNullCheck");
70 private static final CounterKey counterTrappingNullCheckExistingRead = DebugContext.counter("TrappingNullCheckExistingRead");
71 private static final CounterKey counterTrappingNullCheckUnreached = DebugContext.counter("TrappingNullCheckUnreached");
72 private static final CounterKey counterTrappingNullCheckDynamicDeoptimize = DebugContext.counter("TrappingNullCheckDynamicDeoptimize");
73
74 public static class Options {
75
76 // @formatter:off
77 @Option(help = "Use traps for null checks instead of explicit null-checks", type = OptionType.Expert)
78 public static final OptionKey<Boolean> UseTrappingNullChecks = new OptionKey<>(true);
79 // @formatter:on
80 }
81
82 @Override
83 protected void run(StructuredGraph graph, LowTierContext context) {
84 if (!Options.UseTrappingNullChecks.getValue(graph.getOptions()) || context.getTarget().implicitNullCheckLimit <= 0) {
85 return;
86 }
87 assert graph.getGuardsStage().areFrameStatesAtDeopts();
88
89 long implicitNullCheckLimit = context.getTarget().implicitNullCheckLimit;
90 for (DeoptimizeNode deopt : graph.getNodes(DeoptimizeNode.TYPE)) {
91 tryUseTrappingNullCheck(deopt, deopt.predecessor(), deopt.getReason(), deopt.getSpeculation(), implicitNullCheckLimit);
92 }
93 for (DynamicDeoptimizeNode deopt : graph.getNodes(DynamicDeoptimizeNode.TYPE)) {
94 tryUseTrappingNullCheck(context.getMetaAccess(), deopt, implicitNullCheckLimit);
95 }
96
97 }
98
99 private static void tryUseTrappingNullCheck(MetaAccessProvider metaAccessProvider, DynamicDeoptimizeNode deopt, long implicitNullCheckLimit) {
100 Node predecessor = deopt.predecessor();
101 if (predecessor instanceof AbstractMergeNode) {
102 AbstractMergeNode merge = (AbstractMergeNode) predecessor;
103
104 // Process each predecessor at the merge, unpacking the reasons and speculations as
105 // needed.
106 ValueNode reason = deopt.getActionAndReason();
107 ValuePhiNode reasonPhi = null;
108 List<ValueNode> reasons = null;
109 int expectedPhis = 0;
110
111 if (reason instanceof ValuePhiNode) {
112 reasonPhi = (ValuePhiNode) reason;
113 if (reasonPhi.merge() != merge) {
114 return;
115 }
116 reasons = reasonPhi.values().snapshot();
117 expectedPhis++;
118 } else if (!reason.isConstant()) {
119 merge.getDebug().log("Non constant reason %s", merge);
120 return;
121 }
122
123 ValueNode speculation = deopt.getSpeculation();
124 ValuePhiNode speculationPhi = null;
125 List<ValueNode> speculations = null;
126 if (speculation instanceof ValuePhiNode) {
127 speculationPhi = (ValuePhiNode) speculation;
128 if (speculationPhi.merge() != merge) {
129 return;
130 }
131 speculations = speculationPhi.values().snapshot();
132 expectedPhis++;
133 }
134
135 if (merge.phis().count() != expectedPhis) {
136 return;
137 }
138
139 int index = 0;
140 List<EndNode> predecessors = merge.cfgPredecessors().snapshot();
141 for (AbstractEndNode end : predecessors) {
142 Node endPredecesssor = end.predecessor();
143 ValueNode thisReason = reasons != null ? reasons.get(index) : reason;
144 ValueNode thisSpeculation = speculations != null ? speculations.get(index) : speculation;
145 if (!merge.isAlive()) {
146 // When evacuating a merge the last successor simplfies the merge away so it
147 // must be handled specially.
148 assert predecessors.get(predecessors.size() - 1) == end : "must be last end";
149 endPredecesssor = deopt.predecessor();
150 thisSpeculation = deopt.getSpeculation();
151 thisReason = deopt.getActionAndReason();
152 }
153
154 index++;
155 if (!thisReason.isConstant() || !thisSpeculation.isConstant()) {
156 end.getDebug().log("Non constant deopt %s", end);
157 continue;
158 }
159 DeoptimizationReason deoptimizationReason = metaAccessProvider.decodeDeoptReason(thisReason.asJavaConstant());
160 Speculation speculationConstant = metaAccessProvider.decodeSpeculation(thisSpeculation.asJavaConstant(), deopt.graph().getSpeculationLog());
161 tryUseTrappingNullCheck(deopt, endPredecesssor, deoptimizationReason, speculationConstant, implicitNullCheckLimit);
162 }
163 }
164 }
165
166 private static void tryUseTrappingNullCheck(AbstractDeoptimizeNode deopt, Node predecessor, DeoptimizationReason deoptimizationReason, Speculation speculation, long implicitNullCheckLimit) {
167 assert predecessor != null;
168 if (deoptimizationReason != DeoptimizationReason.NullCheckException && deoptimizationReason != DeoptimizationReason.UnreachedCode) {
169 deopt.getDebug().log(DebugContext.INFO_LEVEL, "Not a null check or unreached %s", predecessor);
170 return;
171 }
172 assert speculation != null;
173 if (!speculation.equals(SpeculationLog.NO_SPECULATION)) {
174 deopt.getDebug().log(DebugContext.INFO_LEVEL, "Has a speculation %s", predecessor);
175 return;
176 }
177 if (predecessor instanceof AbstractMergeNode) {
178 AbstractMergeNode merge = (AbstractMergeNode) predecessor;
179 if (merge.phis().isEmpty()) {
180 for (AbstractEndNode end : merge.cfgPredecessors().snapshot()) {
181 checkPredecessor(deopt, end.predecessor(), deoptimizationReason, implicitNullCheckLimit);
182 }
183 }
184 } else if (predecessor instanceof AbstractBeginNode) {
185 checkPredecessor(deopt, predecessor, deoptimizationReason, implicitNullCheckLimit);
186 } else {
187 deopt.getDebug().log(DebugContext.INFO_LEVEL, "Not a Begin or Merge %s", predecessor);
188 }
189 }
190
191 private static void checkPredecessor(AbstractDeoptimizeNode deopt, Node predecessor, DeoptimizationReason deoptimizationReason, long implicitNullCheckLimit) {
192 Node current = predecessor;
193 AbstractBeginNode branch = null;
194 while (current instanceof AbstractBeginNode) {
195 branch = (AbstractBeginNode) current;
196 if (branch.anchored().isNotEmpty()) {
197 // some input of the deopt framestate is anchored to this branch
198 return;
199 }
200 current = current.predecessor();
201 }
202 if (current instanceof IfNode) {
203 IfNode ifNode = (IfNode) current;
204 if (branch != ifNode.trueSuccessor()) {
205 return;
206 }
207 LogicNode condition = ifNode.condition();
208 if (condition instanceof IsNullNode) {
209 replaceWithTrappingNullCheck(deopt, ifNode, condition, deoptimizationReason, implicitNullCheckLimit);
210 }
211 }
212 }
213
214 private static void replaceWithTrappingNullCheck(AbstractDeoptimizeNode deopt, IfNode ifNode, LogicNode condition, DeoptimizationReason deoptimizationReason, long implicitNullCheckLimit) {
215 DebugContext debug = deopt.getDebug();
216 counterTrappingNullCheck.increment(debug);
217 if (deopt instanceof DynamicDeoptimizeNode) {
218 counterTrappingNullCheckDynamicDeoptimize.increment(debug);
219 }
220 if (deoptimizationReason == DeoptimizationReason.UnreachedCode) {
221 counterTrappingNullCheckUnreached.increment(debug);
222 }
223 IsNullNode isNullNode = (IsNullNode) condition;
224 AbstractBeginNode nonTrappingContinuation = ifNode.falseSuccessor();
225 AbstractBeginNode trappingContinuation = ifNode.trueSuccessor();
226
227 DeoptimizingFixedWithNextNode trappingNullCheck = null;
228 FixedNode nextNonTrapping = nonTrappingContinuation.next();
229 ValueNode value = isNullNode.getValue();
230 if (OptImplicitNullChecks.getValue(ifNode.graph().getOptions()) && implicitNullCheckLimit > 0) {
231 if (nextNonTrapping instanceof FixedAccessNode) {
232 FixedAccessNode fixedAccessNode = (FixedAccessNode) nextNonTrapping;
233 if (fixedAccessNode.canNullCheck()) {
234 AddressNode address = fixedAccessNode.getAddress();
235 ValueNode base = address.getBase();
236 ValueNode index = address.getIndex();
237 // allow for architectures which cannot fold an
238 // intervening uncompress out of the address chain
239 if (base != null && base instanceof CompressionNode) {
240 base = ((CompressionNode) base).getValue();
241 }
242 if (index != null && index instanceof CompressionNode) {
243 index = ((CompressionNode) index).getValue();
244 }
245 if (((base == value && index == null) || (base == null && index == value)) && address.getMaxConstantDisplacement() < implicitNullCheckLimit) {
246 // Opportunity for implicit null check as part of an existing read found!
247 fixedAccessNode.setStateBefore(deopt.stateBefore());
248 fixedAccessNode.setNullCheck(true);
249 deopt.graph().removeSplit(ifNode, nonTrappingContinuation);
250 trappingNullCheck = fixedAccessNode;
251 counterTrappingNullCheckExistingRead.increment(debug);
252 deopt.getDebug().log("Added implicit null check to %s", fixedAccessNode);
253 }
254 }
255 }
256 }
257
258 if (trappingNullCheck == null) {
259 // Need to add a null check node.
260 trappingNullCheck = deopt.graph().add(new NullCheckNode(value));
261 deopt.graph().replaceSplit(ifNode, trappingNullCheck, nonTrappingContinuation);
262 deopt.getDebug().log("Inserted NullCheckNode %s", trappingNullCheck);
263 }
264
265 trappingNullCheck.setStateBefore(deopt.stateBefore());
266
267 /*
268 * We now have the pattern NullCheck/BeginNode/... It's possible some node is using the
269 * BeginNode as a guard input, so replace guard users of the Begin with the NullCheck and
270 * then remove the Begin from the graph.
271 */
272 nonTrappingContinuation.replaceAtUsages(InputType.Guard, trappingNullCheck);
273
274 if (nonTrappingContinuation instanceof BeginNode) {
275 GraphUtil.unlinkFixedNode(nonTrappingContinuation);
276 nonTrappingContinuation.safeDelete();
277 }
278
279 GraphUtil.killCFG(trappingContinuation);
280 GraphUtil.tryKillUnused(isNullNode);
281 }
282 }