1 /*
2 * Copyright (c) 2013, 2015, 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.Iterator;
28 import java.util.Map;
29 import java.util.Map.Entry;
30
31 import org.graalvm.compiler.core.common.cfg.Loop;
32 import org.graalvm.compiler.debug.Debug;
33 import org.graalvm.compiler.debug.DebugCloseable;
34 import org.graalvm.compiler.debug.DebugCounter;
35 import org.graalvm.compiler.graph.Node;
36 import org.graalvm.compiler.nodes.AbstractBeginNode;
37 import org.graalvm.compiler.nodes.BeginNode;
38 import org.graalvm.compiler.nodes.DeoptimizeNode;
39 import org.graalvm.compiler.nodes.FixedWithNextNode;
40 import org.graalvm.compiler.nodes.GuardNode;
41 import org.graalvm.compiler.nodes.IfNode;
42 import org.graalvm.compiler.nodes.LogicNode;
43 import org.graalvm.compiler.nodes.LoopBeginNode;
44 import org.graalvm.compiler.nodes.LoopExitNode;
45 import org.graalvm.compiler.nodes.PiNode;
46 import org.graalvm.compiler.nodes.StateSplit;
47 import org.graalvm.compiler.nodes.StructuredGraph;
48 import org.graalvm.compiler.nodes.StructuredGraph.GuardsStage;
49 import org.graalvm.compiler.nodes.StructuredGraph.ScheduleResult;
50 import org.graalvm.compiler.nodes.ValueNode;
51 import org.graalvm.compiler.nodes.calc.IsNullNode;
52 import org.graalvm.compiler.nodes.cfg.Block;
53 import org.graalvm.compiler.nodes.memory.Access;
54 import org.graalvm.compiler.nodes.memory.FixedAccessNode;
55 import org.graalvm.compiler.nodes.memory.FloatingAccessNode;
56 import org.graalvm.compiler.nodes.memory.MemoryNode;
57 import org.graalvm.compiler.nodes.memory.address.OffsetAddressNode;
58 import org.graalvm.compiler.nodes.util.GraphUtil;
59 import org.graalvm.compiler.phases.BasePhase;
60 import org.graalvm.compiler.phases.graph.ScheduledNodeIterator;
61 import org.graalvm.compiler.phases.schedule.SchedulePhase;
62 import org.graalvm.compiler.phases.schedule.SchedulePhase.SchedulingStrategy;
63 import org.graalvm.compiler.phases.tiers.MidTierContext;
64
65 import jdk.vm.ci.meta.JavaConstant;
66
67 /**
68 * This phase lowers {@link GuardNode GuardNodes} into corresponding control-flow structure and
69 * {@link DeoptimizeNode DeoptimizeNodes}.
70 *
71 * This allow to enter the {@link GuardsStage#FIXED_DEOPTS FIXED_DEOPTS} stage of the graph where
72 * all node that may cause deoptimization are fixed.
73 * <p>
74 * It first makes a schedule in order to know where the control flow should be placed. Then, for
75 * each block, it applies two passes. The first one tries to replace null-check guards with implicit
76 * null checks performed by access to the objects that need to be null checked. The second phase
77 * does the actual control-flow expansion of the remaining {@link GuardNode GuardNodes}.
78 */
79 public class GuardLoweringPhase extends BasePhase<MidTierContext> {
80
81 private static final DebugCounter counterImplicitNullCheck = Debug.counter("ImplicitNullCheck");
82
83 private static class UseImplicitNullChecks extends ScheduledNodeIterator {
84
85 private final Map<ValueNode, ValueNode> nullGuarded = Node.newIdentityMap();
86 private final int implicitNullCheckLimit;
87
88 UseImplicitNullChecks(int implicitNullCheckLimit) {
89 this.implicitNullCheckLimit = implicitNullCheckLimit;
90 }
91
92 @Override
93 protected void processNode(Node node) {
94 if (node instanceof GuardNode) {
95 processGuard(node);
96 } else if (node instanceof Access) {
97 processAccess((Access) node);
98 } else if (node instanceof PiNode) {
99 processPi((PiNode) node);
100 }
101 if (node instanceof StateSplit && ((StateSplit) node).stateAfter() != null) {
102 nullGuarded.clear();
103 } else {
104 /*
105 * The OffsetAddressNode itself never forces materialization of a null check, even
106 * if its input is a PiNode. The null check will be folded into the first usage of
107 * the OffsetAddressNode, so we need to keep it in the nullGuarded map.
108 */
109 if (!(node instanceof OffsetAddressNode)) {
110 Iterator<Entry<ValueNode, ValueNode>> it = nullGuarded.entrySet().iterator();
111 while (it.hasNext()) {
112 Entry<ValueNode, ValueNode> entry = it.next();
113 ValueNode guard = entry.getValue();
114 if (guard.usages().contains(node)) {
115 it.remove();
116 } else if (guard instanceof PiNode && guard != node) {
117 PiNode piNode = (PiNode) guard;
118 if (piNode.getGuard().asNode().usages().contains(node)) {
119 it.remove();
120 }
121 }
122 }
123 }
124 }
125 }
126
127 private boolean processPi(PiNode node) {
128 ValueNode guardNode = nullGuarded.get(node.object());
129 if (guardNode != null && node.getGuard() == guardNode) {
130 nullGuarded.put(node, node);
131 return true;
132 }
133 return false;
134 }
135
136 private void processAccess(Access access) {
137 if (access.canNullCheck() && access.getAddress() instanceof OffsetAddressNode) {
138 OffsetAddressNode address = (OffsetAddressNode) access.getAddress();
139 check(access, address);
140 }
141 }
142
143 private void check(Access access, OffsetAddressNode address) {
144 ValueNode base = address.getBase();
145 ValueNode guard = nullGuarded.get(base);
146 if (guard != null && isImplicitNullCheck(address.getOffset())) {
147 if (guard instanceof PiNode) {
148 PiNode piNode = (PiNode) guard;
149 assert guard == address.getBase();
150 assert piNode.getGuard() instanceof GuardNode : piNode;
151 address.setBase(piNode.getOriginalNode());
152 } else {
153 assert guard instanceof GuardNode;
154 }
155 counterImplicitNullCheck.increment();
156 access.setGuard(null);
157 FixedAccessNode fixedAccess;
158 if (access instanceof FloatingAccessNode) {
159 FloatingAccessNode floatingAccessNode = (FloatingAccessNode) access;
160 MemoryNode lastLocationAccess = floatingAccessNode.getLastLocationAccess();
161 fixedAccess = floatingAccessNode.asFixedNode();
162 replaceCurrent(fixedAccess);
163 if (lastLocationAccess != null) {
164 // fixed accesses are not currently part of the memory graph
165 GraphUtil.tryKillUnused(lastLocationAccess.asNode());
166 }
167 } else {
168 fixedAccess = (FixedAccessNode) access;
169 }
170 fixedAccess.setNullCheck(true);
171 GuardNode guardNode = null;
172 if (guard instanceof GuardNode) {
173 guardNode = (GuardNode) guard;
174 } else {
175 PiNode piNode = (PiNode) guard;
176 guardNode = (GuardNode) piNode.getGuard();
177 }
178 LogicNode condition = guardNode.getCondition();
179 guardNode.replaceAndDelete(fixedAccess);
180 if (condition.hasNoUsages()) {
181 GraphUtil.killWithUnusedFloatingInputs(condition);
182 }
183 nullGuarded.remove(base);
184 }
185 }
186
187 private void processGuard(Node node) {
188 GuardNode guard = (GuardNode) node;
189 if (guard.isNegated() && guard.getCondition() instanceof IsNullNode && (guard.getSpeculation() == null || guard.getSpeculation().equals(JavaConstant.NULL_POINTER))) {
190 ValueNode obj = ((IsNullNode) guard.getCondition()).getValue();
191 nullGuarded.put(obj, guard);
192 }
193 }
194
195 private boolean isImplicitNullCheck(ValueNode offset) {
196 JavaConstant c = offset.asJavaConstant();
197 if (c != null) {
198 return c.asLong() < implicitNullCheckLimit;
199 } else {
200 return false;
201 }
202 }
203 }
204
205 private static class LowerGuards extends ScheduledNodeIterator {
206
207 private final Block block;
208 private boolean useGuardIdAsDebugId;
209
210 LowerGuards(Block block, boolean useGuardIdAsDebugId) {
211 this.block = block;
212 this.useGuardIdAsDebugId = useGuardIdAsDebugId;
213 }
214
215 @Override
216 protected void processNode(Node node) {
217 if (node instanceof GuardNode) {
218 GuardNode guard = (GuardNode) node;
219 FixedWithNextNode lowered = guard.lowerGuard();
220 if (lowered != null) {
221 replaceCurrent(lowered);
222 } else {
223 lowerToIf(guard);
224 }
225 }
226 }
227
228 @SuppressWarnings("try")
229 private void lowerToIf(GuardNode guard) {
230 try (DebugCloseable position = guard.withNodeSourcePosition()) {
231 StructuredGraph graph = guard.graph();
232 AbstractBeginNode fastPath = graph.add(new BeginNode());
233 @SuppressWarnings("deprecation")
234 int debugId = useGuardIdAsDebugId ? guard.getId() : DeoptimizeNode.DEFAULT_DEBUG_ID;
235 DeoptimizeNode deopt = graph.add(new DeoptimizeNode(guard.getAction(), guard.getReason(), debugId, guard.getSpeculation(), null));
236 AbstractBeginNode deoptBranch = BeginNode.begin(deopt);
237 AbstractBeginNode trueSuccessor;
238 AbstractBeginNode falseSuccessor;
239 insertLoopExits(deopt);
240 if (guard.isNegated()) {
241 trueSuccessor = deoptBranch;
242 falseSuccessor = fastPath;
243 } else {
244 trueSuccessor = fastPath;
245 falseSuccessor = deoptBranch;
246 }
247 IfNode ifNode = graph.add(new IfNode(guard.getCondition(), trueSuccessor, falseSuccessor, trueSuccessor == fastPath ? 1 : 0));
248 guard.replaceAndDelete(fastPath);
249 insert(ifNode, fastPath);
250 }
251 }
252
253 private void insertLoopExits(DeoptimizeNode deopt) {
254 Loop<Block> loop = block.getLoop();
255 StructuredGraph graph = deopt.graph();
256 while (loop != null) {
257 LoopExitNode exit = graph.add(new LoopExitNode((LoopBeginNode) loop.getHeader().getBeginNode()));
258 graph.addBeforeFixed(deopt, exit);
259 loop = loop.getParent();
260 }
261 }
262 }
263
264 @Override
265 protected void run(StructuredGraph graph, MidTierContext context) {
266 if (graph.getGuardsStage().allowsFloatingGuards()) {
267 SchedulePhase schedulePhase = new SchedulePhase(SchedulingStrategy.EARLIEST);
268 schedulePhase.apply(graph);
269 ScheduleResult schedule = graph.getLastSchedule();
270
271 for (Block block : schedule.getCFG().getBlocks()) {
272 processBlock(block, schedule, context != null ? context.getTarget().implicitNullCheckLimit : 0);
273 }
274 graph.setGuardsStage(GuardsStage.FIXED_DEOPTS);
275 }
276
277 assert assertNoGuardsLeft(graph);
278 }
279
280 private static boolean assertNoGuardsLeft(StructuredGraph graph) {
281 assert graph.getNodes().filter(GuardNode.class).isEmpty();
282 return true;
283 }
284
285 private static void processBlock(Block block, ScheduleResult schedule, int implicitNullCheckLimit) {
286 if (OptImplicitNullChecks.getValue() && implicitNullCheckLimit > 0) {
287 new UseImplicitNullChecks(implicitNullCheckLimit).processNodes(block, schedule);
288 }
289 new LowerGuards(block, Debug.isDumpEnabledForMethod() || Debug.isLogEnabledForMethod()).processNodes(block, schedule);
290 }
291 }