001/*
002 * Copyright (c) 2013, 2015, Oracle and/or its affiliates. All rights reserved.
003 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
004 *
005 * This code is free software; you can redistribute it and/or modify it
006 * under the terms of the GNU General Public License version 2 only, as
007 * published by the Free Software Foundation.
008 *
009 * This code is distributed in the hope that it will be useful, but WITHOUT
010 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
011 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
012 * version 2 for more details (a copy is included in the LICENSE file that
013 * accompanied this code).
014 *
015 * You should have received a copy of the GNU General Public License version
016 * 2 along with this work; if not, write to the Free Software Foundation,
017 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
018 *
019 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
020 * or visit www.oracle.com if you need additional information or have any
021 * questions.
022 */
023package com.oracle.graal.phases.common;
024
025import static com.oracle.graal.compiler.common.GraalOptions.*;
026
027import java.util.*;
028import java.util.Map.Entry;
029
030import com.oracle.graal.debug.*;
031import jdk.internal.jvmci.meta.*;
032
033import com.oracle.graal.compiler.common.cfg.*;
034import com.oracle.graal.graph.*;
035import com.oracle.graal.nodes.*;
036import com.oracle.graal.nodes.StructuredGraph.GuardsStage;
037import com.oracle.graal.nodes.calc.*;
038import com.oracle.graal.nodes.cfg.*;
039import com.oracle.graal.nodes.memory.*;
040import com.oracle.graal.nodes.memory.address.*;
041import com.oracle.graal.nodes.util.*;
042import com.oracle.graal.phases.*;
043import com.oracle.graal.phases.graph.*;
044import com.oracle.graal.phases.schedule.*;
045import com.oracle.graal.phases.schedule.SchedulePhase.SchedulingStrategy;
046import com.oracle.graal.phases.tiers.*;
047
048/**
049 * This phase lowers {@link GuardNode GuardNodes} into corresponding control-flow structure and
050 * {@link DeoptimizeNode DeoptimizeNodes}.
051 *
052 * This allow to enter the {@link GuardsStage#FIXED_DEOPTS FIXED_DEOPTS} stage of the graph where
053 * all node that may cause deoptimization are fixed.
054 * <p>
055 * It first makes a schedule in order to know where the control flow should be placed. Then, for
056 * each block, it applies two passes. The first one tries to replace null-check guards with implicit
057 * null checks performed by access to the objects that need to be null checked. The second phase
058 * does the actual control-flow expansion of the remaining {@link GuardNode GuardNodes}.
059 */
060public class GuardLoweringPhase extends BasePhase<MidTierContext> {
061
062    private static final DebugMetric metricImplicitNullCheck = Debug.metric("ImplicitNullCheck");
063
064    private static class UseImplicitNullChecks extends ScheduledNodeIterator {
065
066        private final Map<ValueNode, ValueNode> nullGuarded = Node.newIdentityMap();
067        private final int implicitNullCheckLimit;
068
069        UseImplicitNullChecks(int implicitNullCheckLimit) {
070            this.implicitNullCheckLimit = implicitNullCheckLimit;
071        }
072
073        @Override
074        protected void processNode(Node node) {
075            if (node instanceof GuardNode) {
076                processGuard(node);
077            } else if (node instanceof Access) {
078                processAccess((Access) node);
079            } else if (node instanceof PiNode) {
080                processPi((PiNode) node);
081            }
082            if (node instanceof StateSplit && ((StateSplit) node).stateAfter() != null) {
083                nullGuarded.clear();
084            } else {
085                /*
086                 * The OffsetAddressNode itself never forces materialization of a null check, even
087                 * if its input is a PiNode. The null check will be folded into the first usage of
088                 * the OffsetAddressNode, so we need to keep it in the nullGuarded map.
089                 */
090                if (!(node instanceof OffsetAddressNode)) {
091                    Iterator<Entry<ValueNode, ValueNode>> it = nullGuarded.entrySet().iterator();
092                    while (it.hasNext()) {
093                        Entry<ValueNode, ValueNode> entry = it.next();
094                        ValueNode guard = entry.getValue();
095                        if (guard.usages().contains(node)) {
096                            it.remove();
097                        } else if (guard instanceof PiNode && guard != node) {
098                            PiNode piNode = (PiNode) guard;
099                            if (piNode.getGuard().asNode().usages().contains(node)) {
100                                it.remove();
101                            }
102                        }
103                    }
104                }
105            }
106        }
107
108        private boolean processPi(PiNode node) {
109            ValueNode guardNode = nullGuarded.get(node.object());
110            if (guardNode != null && node.getGuard() == guardNode) {
111                nullGuarded.put(node, node);
112                return true;
113            }
114            return false;
115        }
116
117        private void processAccess(Access access) {
118            if (access.canNullCheck() && access.getAddress() instanceof OffsetAddressNode) {
119                OffsetAddressNode address = (OffsetAddressNode) access.getAddress();
120                check(access, address);
121            }
122        }
123
124        private void check(Access access, OffsetAddressNode address) {
125            ValueNode base = address.getBase();
126            ValueNode guard = nullGuarded.get(base);
127            if (guard != null && isImplicitNullCheck(address.getOffset())) {
128                if (guard instanceof PiNode) {
129                    PiNode piNode = (PiNode) guard;
130                    assert guard == address.getBase();
131                    assert piNode.getGuard() instanceof GuardNode : piNode;
132                    address.setBase(piNode.getOriginalNode());
133                } else {
134                    assert guard instanceof GuardNode;
135                }
136                metricImplicitNullCheck.increment();
137                access.setGuard(null);
138                FixedAccessNode fixedAccess;
139                if (access instanceof FloatingAccessNode) {
140                    FloatingAccessNode floatingAccessNode = (FloatingAccessNode) access;
141                    MemoryNode lastLocationAccess = floatingAccessNode.getLastLocationAccess();
142                    fixedAccess = floatingAccessNode.asFixedNode();
143                    replaceCurrent(fixedAccess);
144                    if (lastLocationAccess != null) {
145                        // fixed accesses are not currently part of the memory graph
146                        GraphUtil.tryKillUnused(lastLocationAccess.asNode());
147                    }
148                } else {
149                    fixedAccess = (FixedAccessNode) access;
150                }
151                fixedAccess.setNullCheck(true);
152                GuardNode guardNode = null;
153                if (guard instanceof GuardNode) {
154                    guardNode = (GuardNode) guard;
155                } else {
156                    PiNode piNode = (PiNode) guard;
157                    guardNode = (GuardNode) piNode.getGuard();
158                }
159                LogicNode condition = guardNode.condition();
160                guardNode.replaceAndDelete(fixedAccess);
161                if (condition.hasNoUsages()) {
162                    GraphUtil.killWithUnusedFloatingInputs(condition);
163                }
164                nullGuarded.remove(base);
165            }
166        }
167
168        private void processGuard(Node node) {
169            GuardNode guard = (GuardNode) node;
170            if (guard.isNegated() && guard.condition() instanceof IsNullNode && (guard.getSpeculation() == null || guard.getSpeculation().equals(JavaConstant.NULL_POINTER))) {
171                ValueNode obj = ((IsNullNode) guard.condition()).getValue();
172                nullGuarded.put(obj, guard);
173            }
174        }
175
176        private boolean isImplicitNullCheck(ValueNode offset) {
177            JavaConstant c = offset.asJavaConstant();
178            if (c != null) {
179                return c.asLong() < implicitNullCheckLimit;
180            } else {
181                return false;
182            }
183        }
184    }
185
186    private static class LowerGuards extends ScheduledNodeIterator {
187
188        private final Block block;
189        private boolean useGuardIdAsDebugId;
190
191        public LowerGuards(Block block, boolean useGuardIdAsDebugId) {
192            this.block = block;
193            this.useGuardIdAsDebugId = useGuardIdAsDebugId;
194        }
195
196        @Override
197        protected void processNode(Node node) {
198            if (node instanceof GuardNode) {
199                GuardNode guard = (GuardNode) node;
200                FixedWithNextNode lowered = guard.lowerGuard();
201                if (lowered != null) {
202                    replaceCurrent(lowered);
203                } else {
204                    lowerToIf(guard);
205                }
206            }
207        }
208
209        private void lowerToIf(GuardNode guard) {
210            StructuredGraph graph = guard.graph();
211            AbstractBeginNode fastPath = graph.add(new BeginNode());
212            @SuppressWarnings("deprecation")
213            int debugId = useGuardIdAsDebugId ? guard.getId() : DeoptimizeNode.DEFAULT_DEBUG_ID;
214            DeoptimizeNode deopt = graph.add(new DeoptimizeNode(guard.action(), guard.reason(), debugId, guard.getSpeculation(), null));
215            AbstractBeginNode deoptBranch = BeginNode.begin(deopt);
216            AbstractBeginNode trueSuccessor;
217            AbstractBeginNode falseSuccessor;
218            insertLoopExits(deopt);
219            if (guard.isNegated()) {
220                trueSuccessor = deoptBranch;
221                falseSuccessor = fastPath;
222            } else {
223                trueSuccessor = fastPath;
224                falseSuccessor = deoptBranch;
225            }
226            IfNode ifNode = graph.add(new IfNode(guard.condition(), trueSuccessor, falseSuccessor, trueSuccessor == fastPath ? 1 : 0));
227            guard.replaceAndDelete(fastPath);
228            insert(ifNode, fastPath);
229        }
230
231        private void insertLoopExits(DeoptimizeNode deopt) {
232            Loop<Block> loop = block.getLoop();
233            StructuredGraph graph = deopt.graph();
234            while (loop != null) {
235                LoopExitNode exit = graph.add(new LoopExitNode((LoopBeginNode) loop.getHeader().getBeginNode()));
236                graph.addBeforeFixed(deopt, exit);
237                loop = loop.getParent();
238            }
239        }
240    }
241
242    @Override
243    protected void run(StructuredGraph graph, MidTierContext context) {
244        if (graph.getGuardsStage().allowsFloatingGuards()) {
245            SchedulePhase schedule = new SchedulePhase(SchedulingStrategy.EARLIEST);
246            schedule.apply(graph);
247
248            for (Block block : schedule.getCFG().getBlocks()) {
249                processBlock(block, schedule, context != null ? context.getTarget().implicitNullCheckLimit : 0);
250            }
251            graph.setGuardsStage(GuardsStage.FIXED_DEOPTS);
252        }
253
254        assert assertNoGuardsLeft(graph);
255    }
256
257    private static boolean assertNoGuardsLeft(StructuredGraph graph) {
258        assert graph.getNodes().filter(GuardNode.class).isEmpty();
259        return true;
260    }
261
262    private static void processBlock(Block block, SchedulePhase schedule, int implicitNullCheckLimit) {
263        if (OptImplicitNullChecks.getValue() && implicitNullCheckLimit > 0) {
264            new UseImplicitNullChecks(implicitNullCheckLimit).processNodes(block, schedule);
265        }
266        new LowerGuards(block, Debug.isDumpEnabledForMethod() || Debug.isLogEnabledForMethod()).processNodes(block, schedule);
267    }
268}