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 */
23package org.graalvm.compiler.phases.common;
24
25import static org.graalvm.compiler.core.common.GraalOptions.OptImplicitNullChecks;
26
27import java.util.Iterator;
28import java.util.Map;
29import java.util.Map.Entry;
30
31import org.graalvm.compiler.core.common.cfg.Loop;
32import org.graalvm.compiler.debug.Debug;
33import org.graalvm.compiler.debug.DebugCloseable;
34import org.graalvm.compiler.debug.DebugCounter;
35import org.graalvm.compiler.graph.Node;
36import org.graalvm.compiler.nodes.AbstractBeginNode;
37import org.graalvm.compiler.nodes.BeginNode;
38import org.graalvm.compiler.nodes.DeoptimizeNode;
39import org.graalvm.compiler.nodes.FixedWithNextNode;
40import org.graalvm.compiler.nodes.GuardNode;
41import org.graalvm.compiler.nodes.IfNode;
42import org.graalvm.compiler.nodes.LogicNode;
43import org.graalvm.compiler.nodes.LoopBeginNode;
44import org.graalvm.compiler.nodes.LoopExitNode;
45import org.graalvm.compiler.nodes.PiNode;
46import org.graalvm.compiler.nodes.StateSplit;
47import org.graalvm.compiler.nodes.StructuredGraph;
48import org.graalvm.compiler.nodes.StructuredGraph.GuardsStage;
49import org.graalvm.compiler.nodes.StructuredGraph.ScheduleResult;
50import org.graalvm.compiler.nodes.ValueNode;
51import org.graalvm.compiler.nodes.calc.IsNullNode;
52import org.graalvm.compiler.nodes.cfg.Block;
53import org.graalvm.compiler.nodes.memory.Access;
54import org.graalvm.compiler.nodes.memory.FixedAccessNode;
55import org.graalvm.compiler.nodes.memory.FloatingAccessNode;
56import org.graalvm.compiler.nodes.memory.MemoryNode;
57import org.graalvm.compiler.nodes.memory.address.OffsetAddressNode;
58import org.graalvm.compiler.nodes.util.GraphUtil;
59import org.graalvm.compiler.phases.BasePhase;
60import org.graalvm.compiler.phases.graph.ScheduledNodeIterator;
61import org.graalvm.compiler.phases.schedule.SchedulePhase;
62import org.graalvm.compiler.phases.schedule.SchedulePhase.SchedulingStrategy;
63import org.graalvm.compiler.phases.tiers.MidTierContext;
64
65import 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 */
79public 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}
292