GuardLoweringPhase.java revision 12651:6ef01bd40ce2
1254721Semaste/* 2254721Semaste * Copyright (c) 2013, 2015, Oracle and/or its affiliates. All rights reserved. 3254721Semaste * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4254721Semaste * 5254721Semaste * This code is free software; you can redistribute it and/or modify it 6254721Semaste * under the terms of the GNU General Public License version 2 only, as 7254721Semaste * published by the Free Software Foundation. 8254721Semaste * 9254721Semaste * This code is distributed in the hope that it will be useful, but WITHOUT 10254721Semaste * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 11254721Semaste * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 12254721Semaste * version 2 for more details (a copy is included in the LICENSE file that 13254721Semaste * accompanied this code). 14254721Semaste * 15254721Semaste * You should have received a copy of the GNU General Public License version 16254721Semaste * 2 along with this work; if not, write to the Free Software Foundation, 17254721Semaste * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 18254721Semaste * 19254721Semaste * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 20254721Semaste * or visit www.oracle.com if you need additional information or have any 21254721Semaste * questions. 22254721Semaste */ 23254721Semastepackage org.graalvm.compiler.phases.common; 24254721Semaste 25254721Semasteimport static org.graalvm.compiler.core.common.GraalOptions.OptImplicitNullChecks; 26254721Semaste 27254721Semasteimport java.util.Iterator; 28254721Semasteimport java.util.Map; 29254721Semasteimport java.util.Map.Entry; 30254721Semaste 31254721Semasteimport org.graalvm.compiler.core.common.cfg.Loop; 32254721Semasteimport org.graalvm.compiler.debug.Debug; 33254721Semasteimport org.graalvm.compiler.debug.DebugCloseable; 34254721Semasteimport org.graalvm.compiler.debug.DebugCounter; 35254721Semasteimport org.graalvm.compiler.graph.Node; 36254721Semasteimport org.graalvm.compiler.nodes.AbstractBeginNode; 37254721Semasteimport org.graalvm.compiler.nodes.BeginNode; 38254721Semasteimport org.graalvm.compiler.nodes.DeoptimizeNode; 39254721Semasteimport org.graalvm.compiler.nodes.FixedWithNextNode; 40254721Semasteimport org.graalvm.compiler.nodes.GuardNode; 41254721Semasteimport org.graalvm.compiler.nodes.IfNode; 42254721Semasteimport org.graalvm.compiler.nodes.LogicNode; 43254721Semasteimport org.graalvm.compiler.nodes.LoopBeginNode; 44254721Semasteimport org.graalvm.compiler.nodes.LoopExitNode; 45254721Semasteimport org.graalvm.compiler.nodes.PiNode; 46254721Semasteimport org.graalvm.compiler.nodes.StateSplit; 47254721Semasteimport org.graalvm.compiler.nodes.StructuredGraph; 48254721Semasteimport org.graalvm.compiler.nodes.StructuredGraph.GuardsStage; 49254721Semasteimport org.graalvm.compiler.nodes.StructuredGraph.ScheduleResult; 50254721Semasteimport org.graalvm.compiler.nodes.ValueNode; 51254721Semasteimport org.graalvm.compiler.nodes.calc.IsNullNode; 52254721Semasteimport org.graalvm.compiler.nodes.cfg.Block; 53254721Semasteimport org.graalvm.compiler.nodes.memory.Access; 54254721Semasteimport org.graalvm.compiler.nodes.memory.FixedAccessNode; 55254721Semasteimport org.graalvm.compiler.nodes.memory.FloatingAccessNode; 56254721Semasteimport org.graalvm.compiler.nodes.memory.MemoryNode; 57254721Semasteimport org.graalvm.compiler.nodes.memory.address.OffsetAddressNode; 58254721Semasteimport org.graalvm.compiler.nodes.util.GraphUtil; 59254721Semasteimport org.graalvm.compiler.phases.BasePhase; 60254721Semasteimport org.graalvm.compiler.phases.graph.ScheduledNodeIterator; 61254721Semasteimport org.graalvm.compiler.phases.schedule.SchedulePhase; 62254721Semasteimport org.graalvm.compiler.phases.schedule.SchedulePhase.SchedulingStrategy; 63254721Semasteimport org.graalvm.compiler.phases.tiers.MidTierContext; 64254721Semaste 65254721Semasteimport jdk.vm.ci.meta.JavaConstant; 66254721Semaste 67254721Semaste/** 68254721Semaste * This phase lowers {@link GuardNode GuardNodes} into corresponding control-flow structure and 69254721Semaste * {@link DeoptimizeNode DeoptimizeNodes}. 70254721Semaste * 71254721Semaste * This allow to enter the {@link GuardsStage#FIXED_DEOPTS FIXED_DEOPTS} stage of the graph where 72254721Semaste * all node that may cause deoptimization are fixed. 73254721Semaste * <p> 74254721Semaste * It first makes a schedule in order to know where the control flow should be placed. Then, for 75254721Semaste * each block, it applies two passes. The first one tries to replace null-check guards with implicit 76254721Semaste * null checks performed by access to the objects that need to be null checked. The second phase 77254721Semaste * does the actual control-flow expansion of the remaining {@link GuardNode GuardNodes}. 78254721Semaste */ 79254721Semastepublic class GuardLoweringPhase extends BasePhase<MidTierContext> { 80254721Semaste 81254721Semaste private static final DebugCounter counterImplicitNullCheck = Debug.counter("ImplicitNullCheck"); 82254721Semaste 83254721Semaste private static class UseImplicitNullChecks extends ScheduledNodeIterator { 84254721Semaste 85254721Semaste private final Map<ValueNode, ValueNode> nullGuarded = Node.newIdentityMap(); 86254721Semaste private final int implicitNullCheckLimit; 87263363Semaste 88263363Semaste UseImplicitNullChecks(int implicitNullCheckLimit) { 89263363Semaste this.implicitNullCheckLimit = implicitNullCheckLimit; 90263363Semaste } 91263363Semaste 92263363Semaste @Override 93263363Semaste protected void processNode(Node node) { 94263363Semaste if (node instanceof GuardNode) { 95263363Semaste processGuard(node); 96263363Semaste } else if (node instanceof Access) { 97263363Semaste processAccess((Access) node); 98263363Semaste } else if (node instanceof PiNode) { 99263363Semaste processPi((PiNode) node); 100263363Semaste } 101263363Semaste if (node instanceof StateSplit && ((StateSplit) node).stateAfter() != null) { 102254721Semaste nullGuarded.clear(); 103254721Semaste } else { 104254721Semaste /* 105254721Semaste * The OffsetAddressNode itself never forces materialization of a null check, even 106254721Semaste * if its input is a PiNode. The null check will be folded into the first usage of 107254721Semaste * the OffsetAddressNode, so we need to keep it in the nullGuarded map. 108254721Semaste */ 109254721Semaste if (!(node instanceof OffsetAddressNode)) { 110254721Semaste Iterator<Entry<ValueNode, ValueNode>> it = nullGuarded.entrySet().iterator(); 111254721Semaste while (it.hasNext()) { 112254721Semaste Entry<ValueNode, ValueNode> entry = it.next(); 113254721Semaste ValueNode guard = entry.getValue(); 114254721Semaste if (guard.usages().contains(node)) { 115254721Semaste it.remove(); 116254721Semaste } else if (guard instanceof PiNode && guard != node) { 117254721Semaste PiNode piNode = (PiNode) guard; 118254721Semaste if (piNode.getGuard().asNode().usages().contains(node)) { 119254721Semaste it.remove(); 120254721Semaste } 121254721Semaste } 122254721Semaste } 123254721Semaste } 124254721Semaste } 125254721Semaste } 126254721Semaste 127254721Semaste private boolean processPi(PiNode node) { 128254721Semaste ValueNode guardNode = nullGuarded.get(node.object()); 129254721Semaste if (guardNode != null && node.getGuard() == guardNode) { 130254721Semaste nullGuarded.put(node, node); 131254721Semaste return true; 132254721Semaste } 133254721Semaste return false; 134254721Semaste } 135254721Semaste 136254721Semaste private void processAccess(Access access) { 137254721Semaste if (access.canNullCheck() && access.getAddress() instanceof OffsetAddressNode) { 138254721Semaste OffsetAddressNode address = (OffsetAddressNode) access.getAddress(); 139254721Semaste check(access, address); 140254721Semaste } 141254721Semaste } 142254721Semaste 143254721Semaste private void check(Access access, OffsetAddressNode address) { 144254721Semaste ValueNode base = address.getBase(); 145254721Semaste ValueNode guard = nullGuarded.get(base); 146254721Semaste if (guard != null && isImplicitNullCheck(address.getOffset())) { 147254721Semaste if (guard instanceof PiNode) { 148254721Semaste PiNode piNode = (PiNode) guard; 149254721Semaste assert guard == address.getBase(); 150254721Semaste assert piNode.getGuard() instanceof GuardNode : piNode; 151254721Semaste address.setBase(piNode.getOriginalNode()); 152254721Semaste } else { 153254721Semaste assert guard instanceof GuardNode; 154254721Semaste } 155254721Semaste counterImplicitNullCheck.increment(); 156254721Semaste access.setGuard(null); 157254721Semaste FixedAccessNode fixedAccess; 158254721Semaste if (access instanceof FloatingAccessNode) { 159254721Semaste FloatingAccessNode floatingAccessNode = (FloatingAccessNode) access; 160254721Semaste MemoryNode lastLocationAccess = floatingAccessNode.getLastLocationAccess(); 161254721Semaste fixedAccess = floatingAccessNode.asFixedNode(); 162254721Semaste replaceCurrent(fixedAccess); 163254721Semaste 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