1 /* 2 * Copyright (c) 2011, 2020, 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.virtual.phases.ea; 26 27 import java.util.ArrayList; 28 import java.util.BitSet; 29 import java.util.Iterator; 30 import java.util.List; 31 import java.util.function.IntUnaryOperator; 32 33 import jdk.internal.vm.compiler.collections.EconomicMap; 34 import jdk.internal.vm.compiler.collections.EconomicSet; 35 import jdk.internal.vm.compiler.collections.Equivalence; 36 import org.graalvm.compiler.core.common.GraalOptions; 37 import org.graalvm.compiler.core.common.cfg.Loop; 38 import org.graalvm.compiler.core.common.type.Stamp; 39 import org.graalvm.compiler.core.common.type.StampFactory; 40 import org.graalvm.compiler.debug.CounterKey; 41 import org.graalvm.compiler.debug.DebugContext; 42 import org.graalvm.compiler.graph.Node; 43 import org.graalvm.compiler.graph.NodeBitMap; 44 import org.graalvm.compiler.graph.Position; 45 import org.graalvm.compiler.graph.spi.Canonicalizable; 46 import org.graalvm.compiler.nodes.AbstractEndNode; 47 import org.graalvm.compiler.nodes.CallTargetNode; 48 import org.graalvm.compiler.nodes.ConstantNode; 49 import org.graalvm.compiler.nodes.ControlSinkNode; 50 import org.graalvm.compiler.nodes.FixedNode; 51 import org.graalvm.compiler.nodes.FixedWithNextNode; 52 import org.graalvm.compiler.nodes.FrameState; 53 import org.graalvm.compiler.nodes.Invoke; 54 import org.graalvm.compiler.nodes.LoopBeginNode; 55 import org.graalvm.compiler.nodes.LoopExitNode; 56 import org.graalvm.compiler.nodes.NodeView; 57 import org.graalvm.compiler.nodes.PhiNode; 58 import org.graalvm.compiler.nodes.ProxyNode; 59 import org.graalvm.compiler.nodes.StructuredGraph; 60 import org.graalvm.compiler.nodes.StructuredGraph.ScheduleResult; 61 import org.graalvm.compiler.nodes.UnwindNode; 62 import org.graalvm.compiler.nodes.ValueNode; 63 import org.graalvm.compiler.nodes.ValuePhiNode; 64 import org.graalvm.compiler.nodes.ValueProxyNode; 65 import org.graalvm.compiler.nodes.VirtualState; 66 import org.graalvm.compiler.nodes.cfg.Block; 67 import org.graalvm.compiler.nodes.spi.CoreProviders; 68 import org.graalvm.compiler.nodes.spi.NodeWithState; 69 import org.graalvm.compiler.nodes.spi.Virtualizable; 70 import org.graalvm.compiler.nodes.spi.VirtualizableAllocation; 71 import org.graalvm.compiler.nodes.spi.VirtualizerTool; 72 import org.graalvm.compiler.nodes.virtual.AllocatedObjectNode; 73 import org.graalvm.compiler.nodes.virtual.VirtualObjectNode; 74 import org.graalvm.compiler.virtual.nodes.VirtualObjectState; 75 76 import jdk.vm.ci.meta.JavaConstant; 77 import jdk.vm.ci.meta.JavaKind; 78 79 public abstract class PartialEscapeClosure<BlockT extends PartialEscapeBlockState<BlockT>> extends EffectsClosure<BlockT> { 80 81 public static final CounterKey COUNTER_MATERIALIZATIONS = DebugContext.counter("Materializations"); 82 public static final CounterKey COUNTER_MATERIALIZATIONS_PHI = DebugContext.counter("MaterializationsPhi"); 83 public static final CounterKey COUNTER_MATERIALIZATIONS_MERGE = DebugContext.counter("MaterializationsMerge"); 84 public static final CounterKey COUNTER_MATERIALIZATIONS_UNHANDLED = DebugContext.counter("MaterializationsUnhandled"); 85 public static final CounterKey COUNTER_MATERIALIZATIONS_LOOP_REITERATION = DebugContext.counter("MaterializationsLoopReiteration"); 86 public static final CounterKey COUNTER_MATERIALIZATIONS_LOOP_END = DebugContext.counter("MaterializationsLoopEnd"); 87 public static final CounterKey COUNTER_ALLOCATION_REMOVED = DebugContext.counter("AllocationsRemoved"); 88 public static final CounterKey COUNTER_MEMORYCHECKPOINT = DebugContext.counter("MemoryCheckpoint"); 89 90 /** 91 * Nodes with inputs that were modified during analysis are marked in this bitset - this way 92 * nodes that are not influenced at all by analysis can be rejected quickly. 93 */ 94 private final NodeBitMap hasVirtualInputs; 95 96 /** 97 * This is handed out to implementers of {@link Virtualizable}. 98 */ 99 protected final VirtualizerToolImpl tool; 100 101 /** 102 * The indexes into this array correspond to {@link VirtualObjectNode#getObjectId()}. 103 */ 104 public final ArrayList<VirtualObjectNode> virtualObjects = new ArrayList<>(); 105 106 @Override needsApplyEffects()107 public boolean needsApplyEffects() { 108 if (hasChanged()) { 109 return true; 110 } 111 /* 112 * If there is a mismatch between the number of materializations and the number of 113 * virtualizations, we need to apply effects, even if there were no other significant 114 * changes to the graph. This applies to each block, since moving from one block to the 115 * other can also be important (if the probabilities of the block differ). 116 */ 117 for (Block block : cfg.getBlocks()) { 118 GraphEffectList effects = blockEffects.get(block); 119 if (effects != null) { 120 if (effects.getVirtualizationDelta() != 0) { 121 return true; 122 } 123 } 124 } 125 return false; 126 } 127 128 private final class CollectVirtualObjectsClosure2 extends VirtualState.NodePositionClosure<Node> { 129 private final EconomicSet<VirtualObjectNode> virtual; 130 private final GraphEffectList effects; 131 private final BlockT state; 132 CollectVirtualObjectsClosure2(EconomicSet<VirtualObjectNode> virtual, GraphEffectList effects, BlockT state)133 private CollectVirtualObjectsClosure2(EconomicSet<VirtualObjectNode> virtual, GraphEffectList effects, BlockT state) { 134 this.virtual = virtual; 135 this.effects = effects; 136 this.state = state; 137 } 138 139 @Override apply(Node from, Position p)140 public void apply(Node from, Position p) { 141 ValueNode value = (ValueNode) p.get(from); 142 Node usage = from; 143 if (value instanceof VirtualObjectNode) { 144 VirtualObjectNode object = (VirtualObjectNode) value; 145 if (object.getObjectId() != -1 && state.getObjectStateOptional(object) != null) { 146 virtual.add(object); 147 } 148 } else { 149 ValueNode alias = getAlias(value); 150 if (alias instanceof VirtualObjectNode) { 151 VirtualObjectNode object = (VirtualObjectNode) alias; 152 virtual.add(object); 153 effects.replaceFirstInput(usage, value, object); 154 } 155 } 156 } 157 158 } 159 160 /** 161 * Final subclass of PartialEscapeClosure, for performance and to make everything behave nicely 162 * with generics. 163 */ 164 public static final class Final extends PartialEscapeClosure<PartialEscapeBlockState.Final> { 165 Final(ScheduleResult schedule, CoreProviders providers)166 public Final(ScheduleResult schedule, CoreProviders providers) { 167 super(schedule, providers); 168 } 169 170 @Override getInitialState()171 protected PartialEscapeBlockState.Final getInitialState() { 172 return new PartialEscapeBlockState.Final(tool.getOptions(), tool.getDebug()); 173 } 174 175 @Override cloneState(PartialEscapeBlockState.Final oldState)176 protected PartialEscapeBlockState.Final cloneState(PartialEscapeBlockState.Final oldState) { 177 return new PartialEscapeBlockState.Final(oldState); 178 } 179 } 180 PartialEscapeClosure(ScheduleResult schedule, CoreProviders providers)181 public PartialEscapeClosure(ScheduleResult schedule, CoreProviders providers) { 182 super(schedule, schedule.getCFG()); 183 StructuredGraph graph = schedule.getCFG().graph; 184 this.hasVirtualInputs = graph.createNodeBitMap(); 185 this.tool = new VirtualizerToolImpl(providers, this, graph.getAssumptions(), graph.getOptions(), debug); 186 } 187 188 /** 189 * @return true if the node was deleted, false otherwise 190 */ 191 @Override processNode(Node node, BlockT state, GraphEffectList effects, FixedWithNextNode lastFixedNode)192 protected boolean processNode(Node node, BlockT state, GraphEffectList effects, FixedWithNextNode lastFixedNode) { 193 /* 194 * These checks make up for the fact that an earliest schedule moves CallTargetNodes upwards 195 * and thus materializes virtual objects needlessly. Also, FrameStates and ConstantNodes are 196 * scheduled, but can safely be ignored. 197 */ 198 if (node instanceof CallTargetNode || node instanceof FrameState || node instanceof ConstantNode) { 199 return false; 200 } else if (node instanceof Invoke) { 201 processNodeInternal(((Invoke) node).callTarget(), state, effects, lastFixedNode); 202 } 203 return processNodeInternal(node, state, effects, lastFixedNode); 204 } 205 processNodeInternal(Node node, BlockT state, GraphEffectList effects, FixedWithNextNode lastFixedNode)206 private boolean processNodeInternal(Node node, BlockT state, GraphEffectList effects, FixedWithNextNode lastFixedNode) { 207 FixedNode nextFixedNode = lastFixedNode == null ? null : lastFixedNode.next(); 208 VirtualUtil.trace(node.getOptions(), debug, "%s", node); 209 210 if (requiresProcessing(node)) { 211 if (processVirtualizable((ValueNode) node, nextFixedNode, state, effects) == false) { 212 return false; 213 } 214 if (tool.isDeleted()) { 215 VirtualUtil.trace(node.getOptions(), debug, "deleted virtualizable allocation %s", node); 216 return true; 217 } 218 } 219 if (hasVirtualInputs.isMarked(node) && node instanceof ValueNode) { 220 if (node instanceof Virtualizable) { 221 if (processVirtualizable((ValueNode) node, nextFixedNode, state, effects) == false) { 222 return false; 223 } 224 if (tool.isDeleted()) { 225 VirtualUtil.trace(node.getOptions(), debug, "deleted virtualizable node %s", node); 226 return true; 227 } 228 } 229 processNodeInputs((ValueNode) node, nextFixedNode, state, effects); 230 } 231 232 if (hasScalarReplacedInputs(node) && node instanceof ValueNode) { 233 if (processNodeWithScalarReplacedInputs((ValueNode) node, nextFixedNode, state, effects)) { 234 return true; 235 } 236 } 237 return false; 238 } 239 requiresProcessing(Node node)240 protected boolean requiresProcessing(Node node) { 241 return node instanceof VirtualizableAllocation; 242 } 243 processVirtualizable(ValueNode node, FixedNode insertBefore, BlockT state, GraphEffectList effects)244 private boolean processVirtualizable(ValueNode node, FixedNode insertBefore, BlockT state, GraphEffectList effects) { 245 tool.reset(state, node, insertBefore, effects); 246 return virtualize(node, tool); 247 } 248 virtualize(ValueNode node, VirtualizerTool vt)249 protected boolean virtualize(ValueNode node, VirtualizerTool vt) { 250 ((Virtualizable) node).virtualize(vt); 251 return true; // request further processing 252 } 253 254 /** 255 * This tries to canonicalize the node based on improved (replaced) inputs. 256 */ 257 @SuppressWarnings("unchecked") processNodeWithScalarReplacedInputs(ValueNode node, FixedNode insertBefore, BlockT state, GraphEffectList effects)258 private boolean processNodeWithScalarReplacedInputs(ValueNode node, FixedNode insertBefore, BlockT state, GraphEffectList effects) { 259 ValueNode canonicalizedValue = node; 260 if (node instanceof Canonicalizable.Unary<?>) { 261 Canonicalizable.Unary<ValueNode> canonicalizable = (Canonicalizable.Unary<ValueNode>) node; 262 ObjectState valueObj = getObjectState(state, canonicalizable.getValue()); 263 ValueNode valueAlias = valueObj != null ? valueObj.getMaterializedValue() : getScalarAlias(canonicalizable.getValue()); 264 if (valueAlias != canonicalizable.getValue()) { 265 canonicalizedValue = (ValueNode) canonicalizable.canonical(tool, valueAlias); 266 } 267 } else if (node instanceof Canonicalizable.Binary<?>) { 268 Canonicalizable.Binary<ValueNode> canonicalizable = (Canonicalizable.Binary<ValueNode>) node; 269 ObjectState xObj = getObjectState(state, canonicalizable.getX()); 270 ValueNode xAlias = xObj != null ? xObj.getMaterializedValue() : getScalarAlias(canonicalizable.getX()); 271 ObjectState yObj = getObjectState(state, canonicalizable.getY()); 272 ValueNode yAlias = yObj != null ? yObj.getMaterializedValue() : getScalarAlias(canonicalizable.getY()); 273 if (xAlias != canonicalizable.getX() || yAlias != canonicalizable.getY()) { 274 canonicalizedValue = (ValueNode) canonicalizable.canonical(tool, xAlias, yAlias); 275 } 276 } else { 277 return false; 278 } 279 if (canonicalizedValue != node && canonicalizedValue != null) { 280 if (canonicalizedValue.isAlive()) { 281 ValueNode alias = getAliasAndResolve(state, canonicalizedValue); 282 if (alias instanceof VirtualObjectNode) { 283 addVirtualAlias((VirtualObjectNode) alias, node); 284 effects.deleteNode(node); 285 } else { 286 effects.replaceAtUsages(node, alias, insertBefore); 287 addScalarAlias(node, alias); 288 } 289 } else { 290 if (!prepareCanonicalNode(canonicalizedValue, state, effects)) { 291 VirtualUtil.trace(node.getOptions(), debug, "replacement via canonicalization too complex: %s -> %s", node, canonicalizedValue); 292 return false; 293 } 294 if (canonicalizedValue instanceof ControlSinkNode) { 295 effects.replaceWithSink((FixedWithNextNode) node, (ControlSinkNode) canonicalizedValue); 296 state.markAsDead(); 297 } else { 298 effects.replaceAtUsages(node, canonicalizedValue, insertBefore); 299 addScalarAlias(node, canonicalizedValue); 300 } 301 } 302 VirtualUtil.trace(node.getOptions(), debug, "replaced via canonicalization: %s -> %s", node, canonicalizedValue); 303 return true; 304 } 305 return false; 306 } 307 308 /** 309 * Nodes created during canonicalizations need to be scanned for values that were replaced. 310 */ prepareCanonicalNode(ValueNode node, BlockT state, GraphEffectList effects)311 private boolean prepareCanonicalNode(ValueNode node, BlockT state, GraphEffectList effects) { 312 assert !node.isAlive(); 313 for (Position pos : node.inputPositions()) { 314 Node input = pos.get(node); 315 if (input instanceof ValueNode) { 316 if (input.isAlive()) { 317 if (!(input instanceof VirtualObjectNode)) { 318 ObjectState obj = getObjectState(state, (ValueNode) input); 319 if (obj != null) { 320 if (obj.isVirtual()) { 321 return false; 322 } else { 323 pos.initialize(node, obj.getMaterializedValue()); 324 } 325 } else { 326 pos.initialize(node, getScalarAlias((ValueNode) input)); 327 } 328 } 329 } else { 330 if (!prepareCanonicalNode((ValueNode) input, state, effects)) { 331 return false; 332 } 333 } 334 } 335 } 336 return true; 337 } 338 339 /** 340 * This replaces all inputs that point to virtual or materialized values with the actual value, 341 * materializing if necessary. Also takes care of frame states, adding the necessary 342 * {@link VirtualObjectState}. 343 */ processNodeInputs(ValueNode node, FixedNode insertBefore, BlockT state, GraphEffectList effects)344 private void processNodeInputs(ValueNode node, FixedNode insertBefore, BlockT state, GraphEffectList effects) { 345 VirtualUtil.trace(node.getOptions(), debug, "processing nodewithstate: %s", node); 346 for (Node input : node.inputs()) { 347 if (input instanceof ValueNode) { 348 ValueNode alias = getAlias((ValueNode) input); 349 if (alias instanceof VirtualObjectNode) { 350 int id = ((VirtualObjectNode) alias).getObjectId(); 351 ensureMaterialized(state, id, insertBefore, effects, COUNTER_MATERIALIZATIONS_UNHANDLED); 352 effects.replaceFirstInput(node, input, state.getObjectState(id).getMaterializedValue()); 353 VirtualUtil.trace(node.getOptions(), debug, "replacing input %s at %s", input, node); 354 } 355 } 356 } 357 if (node instanceof NodeWithState) { 358 processNodeWithState((NodeWithState) node, state, effects); 359 } 360 } 361 processNodeWithState(NodeWithState nodeWithState, BlockT state, GraphEffectList effects)362 private void processNodeWithState(NodeWithState nodeWithState, BlockT state, GraphEffectList effects) { 363 for (FrameState fs : nodeWithState.states()) { 364 FrameState frameState = getUniqueFramestate(nodeWithState, fs); 365 EconomicSet<VirtualObjectNode> virtual = EconomicSet.create(Equivalence.IDENTITY_WITH_SYSTEM_HASHCODE); 366 frameState.applyToNonVirtual(new CollectVirtualObjectsClosure2(virtual, effects, state)); 367 collectLockedVirtualObjects(state, virtual); 368 collectReferencedVirtualObjects(state, virtual); 369 addVirtualMappings(frameState, virtual, state, effects); 370 } 371 } 372 getUniqueFramestate(NodeWithState nodeWithState, FrameState frameState)373 private static FrameState getUniqueFramestate(NodeWithState nodeWithState, FrameState frameState) { 374 if (frameState.hasMoreThanOneUsage()) { 375 // Can happen for example from inlined snippets with multiple state split nodes. 376 FrameState copy = (FrameState) frameState.copyWithInputs(); 377 nodeWithState.asNode().replaceFirstInput(frameState, copy); 378 return copy; 379 } 380 return frameState; 381 } 382 addVirtualMappings(FrameState frameState, EconomicSet<VirtualObjectNode> virtual, BlockT state, GraphEffectList effects)383 private void addVirtualMappings(FrameState frameState, EconomicSet<VirtualObjectNode> virtual, BlockT state, GraphEffectList effects) { 384 for (VirtualObjectNode obj : virtual) { 385 effects.addVirtualMapping(frameState, state.getObjectState(obj).createEscapeObjectState(debug, tool.getMetaAccessExtensionProvider(), obj)); 386 } 387 } 388 collectReferencedVirtualObjects(BlockT state, EconomicSet<VirtualObjectNode> virtual)389 private void collectReferencedVirtualObjects(BlockT state, EconomicSet<VirtualObjectNode> virtual) { 390 Iterator<VirtualObjectNode> iterator = virtual.iterator(); 391 while (iterator.hasNext()) { 392 VirtualObjectNode object = iterator.next(); 393 int id = object.getObjectId(); 394 if (id != -1) { 395 ObjectState objState = state.getObjectStateOptional(id); 396 if (objState != null && objState.isVirtual()) { 397 for (ValueNode entry : objState.getEntries()) { 398 if (entry instanceof VirtualObjectNode) { 399 VirtualObjectNode entryVirtual = (VirtualObjectNode) entry; 400 if (!virtual.contains(entryVirtual)) { 401 virtual.add(entryVirtual); 402 } 403 } 404 } 405 } 406 } 407 } 408 } 409 collectLockedVirtualObjects(BlockT state, EconomicSet<VirtualObjectNode> virtual)410 private void collectLockedVirtualObjects(BlockT state, EconomicSet<VirtualObjectNode> virtual) { 411 for (int i = 0; i < state.getStateCount(); i++) { 412 ObjectState objState = state.getObjectStateOptional(i); 413 if (objState != null && objState.isVirtual() && objState.hasLocks()) { 414 virtual.add(virtualObjects.get(i)); 415 } 416 } 417 } 418 419 /** 420 * @return true if materialization happened, false if not. 421 */ ensureMaterialized(PartialEscapeBlockState<?> state, int object, FixedNode materializeBefore, GraphEffectList effects, CounterKey counter)422 protected boolean ensureMaterialized(PartialEscapeBlockState<?> state, int object, FixedNode materializeBefore, GraphEffectList effects, CounterKey counter) { 423 if (state.getObjectState(object).isVirtual()) { 424 counter.increment(debug); 425 VirtualObjectNode virtual = virtualObjects.get(object); 426 state.materializeBefore(materializeBefore, virtual, effects); 427 assert !updateStatesForMaterialized(state, virtual, state.getObjectState(object).getMaterializedValue()) : "method must already have been called before"; 428 return true; 429 } else { 430 return false; 431 } 432 } 433 updateStatesForMaterialized(PartialEscapeBlockState<?> state, VirtualObjectNode virtual, ValueNode materializedValue)434 public static boolean updateStatesForMaterialized(PartialEscapeBlockState<?> state, VirtualObjectNode virtual, ValueNode materializedValue) { 435 // update all existing states with the newly materialized object 436 boolean change = false; 437 for (int i = 0; i < state.getStateCount(); i++) { 438 ObjectState objState = state.getObjectStateOptional(i); 439 if (objState != null && objState.isVirtual()) { 440 ValueNode[] entries = objState.getEntries(); 441 for (int i2 = 0; i2 < entries.length; i2++) { 442 if (entries[i2] == virtual) { 443 state.setEntry(i, i2, materializedValue); 444 change = true; 445 } 446 } 447 } 448 } 449 return change; 450 } 451 452 @Override stripKilledLoopLocations(Loop<Block> loop, BlockT originalInitialState)453 protected BlockT stripKilledLoopLocations(Loop<Block> loop, BlockT originalInitialState) { 454 BlockT initialState = super.stripKilledLoopLocations(loop, originalInitialState); 455 if (loop.getDepth() > GraalOptions.EscapeAnalysisLoopCutoff.getValue(cfg.graph.getOptions())) { 456 /* 457 * After we've reached the maximum loop nesting, we'll simply materialize everything we 458 * can to make sure that the loops only need to be iterated one time. Care is taken here 459 * to not materialize virtual objects that have the "ensureVirtualized" flag set. 460 */ 461 LoopBeginNode loopBegin = (LoopBeginNode) loop.getHeader().getBeginNode(); 462 AbstractEndNode end = loopBegin.forwardEnd(); 463 Block loopPredecessor = loop.getHeader().getFirstPredecessor(); 464 assert loopPredecessor.getEndNode() == end; 465 int length = initialState.getStateCount(); 466 467 boolean change; 468 BitSet ensureVirtualized = new BitSet(length); 469 for (int i = 0; i < length; i++) { 470 ObjectState state = initialState.getObjectStateOptional(i); 471 if (state != null && state.isVirtual() && state.getEnsureVirtualized()) { 472 ensureVirtualized.set(i); 473 } 474 } 475 do { 476 // propagate "ensureVirtualized" flag 477 change = false; 478 for (int i = 0; i < length; i++) { 479 if (!ensureVirtualized.get(i)) { 480 ObjectState state = initialState.getObjectStateOptional(i); 481 if (state != null && state.isVirtual()) { 482 for (ValueNode entry : state.getEntries()) { 483 if (entry instanceof VirtualObjectNode) { 484 if (ensureVirtualized.get(((VirtualObjectNode) entry).getObjectId())) { 485 change = true; 486 ensureVirtualized.set(i); 487 break; 488 } 489 } 490 } 491 } 492 } 493 } 494 } while (change); 495 496 for (int i = 0; i < length; i++) { 497 ObjectState state = initialState.getObjectStateOptional(i); 498 if (state != null && state.isVirtual() && !ensureVirtualized.get(i)) { 499 initialState.materializeBefore(end, virtualObjects.get(i), blockEffects.get(loopPredecessor)); 500 } 501 } 502 } 503 return initialState; 504 } 505 506 @Override processInitialLoopState(Loop<Block> loop, BlockT initialState)507 protected void processInitialLoopState(Loop<Block> loop, BlockT initialState) { 508 for (PhiNode phi : ((LoopBeginNode) loop.getHeader().getBeginNode()).phis()) { 509 if (phi.valueAt(0) != null) { 510 ValueNode alias = getAliasAndResolve(initialState, phi.valueAt(0)); 511 if (alias instanceof VirtualObjectNode) { 512 VirtualObjectNode virtual = (VirtualObjectNode) alias; 513 addVirtualAlias(virtual, phi); 514 } else { 515 aliases.set(phi, null); 516 } 517 } 518 } 519 } 520 521 @Override processLoopExit(LoopExitNode exitNode, BlockT initialState, BlockT exitState, GraphEffectList effects)522 protected void processLoopExit(LoopExitNode exitNode, BlockT initialState, BlockT exitState, GraphEffectList effects) { 523 if (exitNode.graph().hasValueProxies()) { 524 EconomicMap<Integer, ProxyNode> proxies = EconomicMap.create(Equivalence.DEFAULT); 525 for (ProxyNode proxy : exitNode.proxies()) { 526 ValueNode alias = getAlias(proxy.value()); 527 if (alias instanceof VirtualObjectNode) { 528 VirtualObjectNode virtual = (VirtualObjectNode) alias; 529 proxies.put(virtual.getObjectId(), proxy); 530 } 531 } 532 for (int i = 0; i < exitState.getStateCount(); i++) { 533 ObjectState exitObjState = exitState.getObjectStateOptional(i); 534 if (exitObjState != null) { 535 ObjectState initialObjState = initialState.getObjectStateOptional(i); 536 537 if (exitObjState.isVirtual()) { 538 processVirtualAtLoopExit(exitNode, effects, i, exitObjState, initialObjState, exitState); 539 } else { 540 processMaterializedAtLoopExit(exitNode, effects, proxies, i, exitObjState, initialObjState, exitState); 541 } 542 } 543 } 544 } 545 } 546 processMaterializedAtLoopExit(LoopExitNode exitNode, GraphEffectList effects, EconomicMap<Integer, ProxyNode> proxies, int object, ObjectState exitObjState, ObjectState initialObjState, PartialEscapeBlockState<?> exitState)547 private static void processMaterializedAtLoopExit(LoopExitNode exitNode, GraphEffectList effects, EconomicMap<Integer, ProxyNode> proxies, int object, ObjectState exitObjState, 548 ObjectState initialObjState, PartialEscapeBlockState<?> exitState) { 549 if (initialObjState == null || initialObjState.isVirtual()) { 550 ProxyNode proxy = proxies.get(object); 551 if (proxy == null) { 552 proxy = new ValueProxyNode(exitObjState.getMaterializedValue(), exitNode); 553 effects.addFloatingNode(proxy, "proxy"); 554 } else { 555 effects.replaceFirstInput(proxy, proxy.value(), exitObjState.getMaterializedValue()); 556 // nothing to do - will be handled in processNode 557 } 558 exitState.updateMaterializedValue(object, proxy); 559 } else { 560 if (initialObjState.getMaterializedValue() != exitObjState.getMaterializedValue()) { 561 exitNode.getDebug().log("materialized value changes within loop: %s vs. %s at %s", initialObjState.getMaterializedValue(), exitObjState.getMaterializedValue(), exitNode); 562 } 563 } 564 } 565 processVirtualAtLoopExit(LoopExitNode exitNode, GraphEffectList effects, int object, ObjectState exitObjState, ObjectState initialObjState, PartialEscapeBlockState<?> exitState)566 private static void processVirtualAtLoopExit(LoopExitNode exitNode, GraphEffectList effects, int object, ObjectState exitObjState, ObjectState initialObjState, 567 PartialEscapeBlockState<?> exitState) { 568 for (int i = 0; i < exitObjState.getEntries().length; i++) { 569 ValueNode value = exitState.getObjectState(object).getEntry(i); 570 if (!(value instanceof VirtualObjectNode || value.isConstant())) { 571 if (exitNode.loopBegin().isPhiAtMerge(value) || initialObjState == null || !initialObjState.isVirtual() || initialObjState.getEntry(i) != value) { 572 ProxyNode proxy = new ValueProxyNode(value, exitNode); 573 exitState.setEntry(object, i, proxy); 574 effects.addFloatingNode(proxy, "virtualProxy"); 575 } 576 } 577 } 578 } 579 580 @Override createMergeProcessor(Block merge)581 protected MergeProcessor createMergeProcessor(Block merge) { 582 return new MergeProcessor(merge); 583 } 584 585 protected class MergeProcessor extends EffectsClosure<BlockT>.MergeProcessor { 586 587 private EconomicMap<Object, ValuePhiNode> materializedPhis; 588 private EconomicMap<ValueNode, ValuePhiNode[]> valuePhis; 589 private EconomicMap<ValuePhiNode, VirtualObjectNode> valueObjectVirtuals; 590 private final boolean needsCaching; 591 MergeProcessor(Block mergeBlock)592 public MergeProcessor(Block mergeBlock) { 593 super(mergeBlock); 594 // merge will only be called multiple times for loop headers 595 needsCaching = mergeBlock.isLoopHeader(); 596 } 597 getPhi(T virtual, Stamp stamp)598 protected <T> PhiNode getPhi(T virtual, Stamp stamp) { 599 if (needsCaching) { 600 return getPhiCached(virtual, stamp); 601 } else { 602 return createValuePhi(stamp); 603 } 604 } 605 getPhiCached(T virtual, Stamp stamp)606 private <T> PhiNode getPhiCached(T virtual, Stamp stamp) { 607 if (materializedPhis == null) { 608 materializedPhis = EconomicMap.create(Equivalence.DEFAULT); 609 } 610 ValuePhiNode result = materializedPhis.get(virtual); 611 if (result == null) { 612 result = createValuePhi(stamp); 613 materializedPhis.put(virtual, result); 614 } 615 return result; 616 } 617 getValuePhis(ValueNode key, int entryCount)618 private PhiNode[] getValuePhis(ValueNode key, int entryCount) { 619 if (needsCaching) { 620 return getValuePhisCached(key, entryCount); 621 } else { 622 return new ValuePhiNode[entryCount]; 623 } 624 } 625 getValuePhisCached(ValueNode key, int entryCount)626 private PhiNode[] getValuePhisCached(ValueNode key, int entryCount) { 627 if (valuePhis == null) { 628 valuePhis = EconomicMap.create(Equivalence.IDENTITY_WITH_SYSTEM_HASHCODE); 629 } 630 ValuePhiNode[] result = valuePhis.get(key); 631 if (result == null) { 632 result = new ValuePhiNode[entryCount]; 633 valuePhis.put(key, result); 634 } 635 assert result.length == entryCount; 636 return result; 637 } 638 getValueObjectVirtual(ValuePhiNode phi, VirtualObjectNode virtual)639 private VirtualObjectNode getValueObjectVirtual(ValuePhiNode phi, VirtualObjectNode virtual) { 640 if (needsCaching) { 641 return getValueObjectVirtualCached(phi, virtual); 642 } else { 643 VirtualObjectNode duplicate = virtual.duplicate(); 644 duplicate.setNodeSourcePosition(virtual.getNodeSourcePosition()); 645 return duplicate; 646 } 647 } 648 getValueObjectVirtualCached(ValuePhiNode phi, VirtualObjectNode virtual)649 private VirtualObjectNode getValueObjectVirtualCached(ValuePhiNode phi, VirtualObjectNode virtual) { 650 if (valueObjectVirtuals == null) { 651 valueObjectVirtuals = EconomicMap.create(Equivalence.IDENTITY); 652 } 653 VirtualObjectNode result = valueObjectVirtuals.get(phi); 654 if (result == null) { 655 result = virtual.duplicate(); 656 result.setNodeSourcePosition(virtual.getNodeSourcePosition()); 657 valueObjectVirtuals.put(phi, result); 658 } 659 return result; 660 } 661 662 /** 663 * Merge all predecessor block states into one block state. This is an iterative process, 664 * because merging states can lead to materializations which make previous parts of the 665 * merging operation invalid. The merging process is executed until a stable state has been 666 * reached. This method needs to be careful to place the effects of the merging operation 667 * into the correct blocks. 668 * 669 * @param statesList the predecessor block states of the merge 670 */ 671 @Override merge(List<BlockT> statesList)672 protected void merge(List<BlockT> statesList) { 673 674 PartialEscapeBlockState<?>[] states = new PartialEscapeBlockState<?>[statesList.size()]; 675 for (int i = 0; i < statesList.size(); i++) { 676 states[i] = statesList.get(i); 677 } 678 679 // calculate the set of virtual objects that exist in all predecessors 680 int[] virtualObjTemp = intersectVirtualObjects(states); 681 682 boolean forceMaterialization = false; 683 ValueNode forcedMaterializationValue = null; 684 FrameState frameState = merge.stateAfter(); 685 if (frameState != null && frameState.isExceptionHandlingBCI()) { 686 // We can not go below merges with an exception handling bci 687 // it could create allocations whose slow-path has an invalid framestate 688 forceMaterialization = true; 689 // check if we can reduce the scope of forced materialization to one phi node 690 if (frameState.stackSize() == 1 && merge.next() instanceof UnwindNode) { 691 assert frameState.outerFrameState() == null; 692 UnwindNode unwind = (UnwindNode) merge.next(); 693 if (unwind.exception() == frameState.stackAt(0)) { 694 boolean nullLocals = true; 695 for (int i = 0; i < frameState.localsSize(); i++) { 696 if (frameState.localAt(i) != null) { 697 nullLocals = false; 698 break; 699 } 700 } 701 if (nullLocals) { 702 // We found that the merge is directly followed by an unwind 703 // the Framestate only has the thrown value on the stack and no locals 704 forcedMaterializationValue = unwind.exception(); 705 } 706 } 707 } 708 } 709 710 boolean materialized; 711 do { 712 materialized = false; 713 714 if (!forceMaterialization && PartialEscapeBlockState.identicalObjectStates(states)) { 715 newState.adoptAddObjectStates(states[0]); 716 } else { 717 718 for (int object : virtualObjTemp) { 719 if (!forceMaterialization && PartialEscapeBlockState.identicalObjectStates(states, object)) { 720 newState.addObject(object, states[0].getObjectState(object).share()); 721 continue; 722 } 723 724 // determine if all inputs are virtual or the same materialized value 725 int virtualCount = 0; 726 ObjectState startObj = states[0].getObjectState(object); 727 boolean locksMatch = true; 728 boolean ensureVirtual = true; 729 ValueNode uniqueMaterializedValue = startObj.isVirtual() ? null : startObj.getMaterializedValue(); 730 for (int i = 0; i < states.length; i++) { 731 ObjectState obj = states[i].getObjectState(object); 732 ensureVirtual &= obj.getEnsureVirtualized(); 733 if (forceMaterialization) { 734 if (forcedMaterializationValue == null) { 735 uniqueMaterializedValue = null; 736 continue; 737 } else { 738 ValueNode value = forcedMaterializationValue; 739 if (merge.isPhiAtMerge(value)) { 740 value = ((ValuePhiNode) value).valueAt(i); 741 } 742 ValueNode alias = getAlias(value); 743 if (alias instanceof VirtualObjectNode && ((VirtualObjectNode) alias).getObjectId() == object) { 744 uniqueMaterializedValue = null; 745 continue; 746 } 747 } 748 } 749 if (obj.isVirtual()) { 750 virtualCount++; 751 uniqueMaterializedValue = null; 752 locksMatch &= obj.locksEqual(startObj); 753 } else if (obj.getMaterializedValue() != uniqueMaterializedValue) { 754 uniqueMaterializedValue = null; 755 } 756 } 757 758 if (virtualCount == states.length && locksMatch) { 759 materialized |= mergeObjectStates(object, null, states); 760 } else { 761 if (uniqueMaterializedValue != null) { 762 newState.addObject(object, new ObjectState(uniqueMaterializedValue, null, ensureVirtual)); 763 } else { 764 PhiNode materializedValuePhi = getPhi(object, StampFactory.forKind(JavaKind.Object)); 765 mergeEffects.addFloatingNode(materializedValuePhi, "materializedPhi"); 766 for (int i = 0; i < states.length; i++) { 767 ObjectState obj = states[i].getObjectState(object); 768 if (obj.isVirtual()) { 769 Block predecessor = getPredecessor(i); 770 if (!ensureVirtual && obj.isVirtual()) { 771 // we can materialize if not all inputs are 772 // "ensureVirtualized" 773 obj.setEnsureVirtualized(false); 774 } 775 materialized |= ensureMaterialized(states[i], object, predecessor.getEndNode(), blockEffects.get(predecessor), COUNTER_MATERIALIZATIONS_MERGE); 776 obj = states[i].getObjectState(object); 777 } 778 setPhiInput(materializedValuePhi, i, obj.getMaterializedValue()); 779 } 780 newState.addObject(object, new ObjectState(materializedValuePhi, null, false)); 781 } 782 } 783 } 784 } 785 786 for (PhiNode phi : getPhis()) { 787 aliases.set(phi, null); 788 if (hasVirtualInputs.isMarked(phi) && phi instanceof ValuePhiNode) { 789 materialized |= processPhi((ValuePhiNode) phi, states); 790 } 791 } 792 if (materialized) { 793 newState.resetObjectStates(virtualObjects.size()); 794 mergeEffects.clear(); 795 afterMergeEffects.clear(); 796 } 797 } while (materialized); 798 } 799 intersectVirtualObjects(PartialEscapeBlockState<?>[] states)800 private int[] intersectVirtualObjects(PartialEscapeBlockState<?>[] states) { 801 int length = states[0].getStateCount(); 802 for (int i = 1; i < states.length; i++) { 803 length = Math.min(length, states[i].getStateCount()); 804 } 805 806 int count = 0; 807 for (int objectIndex = 0; objectIndex < length; objectIndex++) { 808 if (intersectObjectState(states, objectIndex)) { 809 count++; 810 } 811 } 812 813 int index = 0; 814 int[] resultInts = new int[count]; 815 for (int objectIndex = 0; objectIndex < length; objectIndex++) { 816 if (intersectObjectState(states, objectIndex)) { 817 resultInts[index++] = objectIndex; 818 } 819 } 820 assert index == count; 821 return resultInts; 822 } 823 intersectObjectState(PartialEscapeBlockState<?>[] states, int objectIndex)824 private boolean intersectObjectState(PartialEscapeBlockState<?>[] states, int objectIndex) { 825 for (int i = 0; i < states.length; i++) { 826 PartialEscapeBlockState<?> state = states[i]; 827 if (state.getObjectStateOptional(objectIndex) == null) { 828 return false; 829 } 830 } 831 return true; 832 } 833 834 /** 835 * Try to merge multiple virtual object states into a single object state. If the incoming 836 * object states are compatible, then this method will create PhiNodes for the object's 837 * entries where needed. If they are incompatible, then all incoming virtual objects will be 838 * materialized, and a PhiNode for the materialized values will be created. Object states 839 * can be incompatible if they contain {@code long} or {@code double} values occupying two 840 * {@code int} slots in such a way that that their values cannot be merged using PhiNodes. 841 * The states may also be incompatible if they contain escaped large writes to byte arrays 842 * in such a way that they cannot be merged using PhiNodes. 843 * 844 * @param states the predecessor block states of the merge 845 * @return true if materialization happened during the merge, false otherwise 846 */ mergeObjectStates(int resultObject, int[] sourceObjects, PartialEscapeBlockState<?>[] states)847 private boolean mergeObjectStates(int resultObject, int[] sourceObjects, PartialEscapeBlockState<?>[] states) { 848 boolean compatible = true; 849 boolean ensureVirtual = true; 850 IntUnaryOperator getObject = index -> sourceObjects == null ? resultObject : sourceObjects[index]; 851 852 VirtualObjectNode virtual = virtualObjects.get(resultObject); 853 int entryCount = virtual.entryCount(); 854 855 // determine all entries that have a two-slot value 856 JavaKind[] twoSlotKinds = null; 857 858 // Determine all entries that span multiple slots. 859 int[] virtualByteCount = null; 860 JavaKind[] virtualKinds = null; 861 862 outer: for (int i = 0; i < states.length; i++) { 863 ObjectState objectState = states[i].getObjectState(getObject.applyAsInt(i)); 864 ValueNode[] entries = objectState.getEntries(); 865 int valueIndex = 0; 866 ensureVirtual &= objectState.getEnsureVirtualized(); 867 while (valueIndex < entryCount) { 868 JavaKind otherKind = entries[valueIndex].getStackKind(); 869 JavaKind entryKind = virtual.entryKind(tool.getMetaAccessExtensionProvider(), valueIndex); 870 if (entryKind == JavaKind.Int && otherKind.needsTwoSlots()) { 871 if (twoSlotKinds == null) { 872 twoSlotKinds = new JavaKind[entryCount]; 873 } 874 if (twoSlotKinds[valueIndex] != null && twoSlotKinds[valueIndex] != otherKind) { 875 compatible = false; 876 break outer; 877 } 878 twoSlotKinds[valueIndex] = otherKind; 879 // skip the next entry 880 valueIndex++; 881 } else if (virtual.isVirtualByteArray(tool.getMetaAccessExtensionProvider())) { 882 int bytecount = tool.getVirtualByteCount(entries, valueIndex); 883 // @formatter:off 884 /* 885 * Having a bytecount of 1 here can mean two things: 886 * - This was a regular byte array access 887 * - This is an uninitialized value (ie: default) 888 * 889 * In the first case, we want to be able to merge regular accesses without 890 * issues. But in the second case, if one of the branch has escaped a write 891 * (while other branches did not touch the array), we want to be able to 892 * propagate the escape to the merge. 893 * 894 * However, the semantics of virtual object creation in PEA puts a default 895 * (0) byte value on all entries. As such, the merging is done in two steps: 896 * - For each virtual entry, know if there is an escaped write in one of the 897 * branch, and store its byte count, unless it is 1. 898 * - Now that we know the byte count, we can escape multiple writes for the 899 * default values from branches that did nothing on the entry in question to 900 * a default write of a bigger kind. 901 * 902 * for example, consider: 903 * 904 * b = new byte[8]; 905 * if (...) {b[0] <- 1L} 906 * else {} 907 * 908 * for escape analysis purposes, it can be seen as: 909 * 910 * b = new byte[8]; 911 * if (...) {b[0] <- 1L} 912 * else {b[0] <- 0L} 913 */ 914 // @formatter:on 915 if (bytecount > 1) { 916 if (virtualByteCount == null) { 917 virtualByteCount = new int[entryCount]; 918 } 919 if (virtualKinds == null) { 920 virtualKinds = new JavaKind[entryCount]; 921 } 922 if (virtualByteCount[valueIndex] != 0 && virtualByteCount[valueIndex] != bytecount) { 923 compatible = false; 924 break outer; 925 } 926 // Disallow merging ints with floats. Allows merging shorts with chars 927 // (working with stack kinds). 928 if (virtualKinds[valueIndex] != null && virtualKinds[valueIndex] != otherKind) { 929 compatible = false; 930 break outer; 931 } 932 virtualByteCount[valueIndex] = bytecount; 933 virtualKinds[valueIndex] = otherKind; 934 // skip illegals. 935 valueIndex = valueIndex + bytecount - 1; 936 } 937 } else { 938 assert entryKind.getStackKind() == otherKind.getStackKind() || (entryKind == JavaKind.Int && otherKind == JavaKind.Illegal) || 939 entryKind.getBitCount() >= otherKind.getBitCount() : entryKind + " vs " + otherKind; 940 } 941 valueIndex++; 942 } 943 } 944 if (compatible && twoSlotKinds != null) { 945 // if there are two-slot values then make sure the incoming states can be merged 946 outer: for (int valueIndex = 0; valueIndex < entryCount; valueIndex++) { 947 if (twoSlotKinds[valueIndex] != null) { 948 assert valueIndex < virtual.entryCount() - 1 && virtual.entryKind(tool.getMetaAccessExtensionProvider(), valueIndex) == JavaKind.Int && 949 virtual.entryKind(tool.getMetaAccessExtensionProvider(), valueIndex + 1) == JavaKind.Int; 950 for (int i = 0; i < states.length; i++) { 951 int object = getObject.applyAsInt(i); 952 ObjectState objectState = states[i].getObjectState(object); 953 ValueNode value = objectState.getEntry(valueIndex); 954 JavaKind valueKind = value.getStackKind(); 955 if (valueKind != twoSlotKinds[valueIndex]) { 956 ValueNode nextValue = objectState.getEntry(valueIndex + 1); 957 if (value.isConstant() && value.asConstant().equals(JavaConstant.INT_0) && nextValue.isConstant() && nextValue.asConstant().equals(JavaConstant.INT_0)) { 958 // rewrite to a zero constant of the larger kind 959 debug.log("Rewriting entry %s to constant of larger size", valueIndex); 960 states[i].setEntry(object, valueIndex, ConstantNode.defaultForKind(twoSlotKinds[valueIndex], graph())); 961 states[i].setEntry(object, valueIndex + 1, tool.getIllegalConstant()); 962 } else { 963 compatible = false; 964 break outer; 965 } 966 } 967 } 968 } 969 } 970 } 971 if (compatible && virtualByteCount != null) { 972 assert twoSlotKinds == null; 973 outer: // 974 for (int valueIndex = 0; valueIndex < entryCount; valueIndex++) { 975 if (virtualByteCount[valueIndex] != 0) { 976 int byteCount = virtualByteCount[valueIndex]; 977 for (int i = 0; i < states.length; i++) { 978 int object = getObject.applyAsInt(i); 979 ObjectState objectState = states[i].getObjectState(object); 980 if (tool.isEntryDefaults(objectState, byteCount, valueIndex)) { 981 // Interpret uninitialized as a corresponding large access. 982 states[i].setEntry(object, valueIndex, ConstantNode.defaultForKind(virtualKinds[valueIndex])); 983 for (int illegalIndex = valueIndex + 1; illegalIndex < valueIndex + byteCount; illegalIndex++) { 984 states[i].setEntry(object, illegalIndex, tool.getIllegalConstant()); 985 } 986 } else { 987 if (tool.getVirtualByteCount(objectState.getEntries(), valueIndex) != byteCount) { 988 compatible = false; 989 break outer; 990 } 991 } 992 } 993 } 994 } 995 } 996 997 if (compatible) { 998 // virtual objects are compatible: create phis for all entries that need them 999 ValueNode[] values = states[0].getObjectState(getObject.applyAsInt(0)).getEntries().clone(); 1000 PhiNode[] phis = getValuePhis(virtual, virtual.entryCount()); 1001 int valueIndex = 0; 1002 while (valueIndex < values.length) { 1003 for (int i = 1; i < states.length; i++) { 1004 if (phis[valueIndex] == null) { 1005 ValueNode field = states[i].getObjectState(getObject.applyAsInt(i)).getEntry(valueIndex); 1006 if (values[valueIndex] != field) { 1007 phis[valueIndex] = createValuePhi(values[valueIndex].stamp(NodeView.DEFAULT).unrestricted()); 1008 } 1009 } 1010 } 1011 if (phis[valueIndex] != null && !phis[valueIndex].stamp(NodeView.DEFAULT).isCompatible(values[valueIndex].stamp(NodeView.DEFAULT))) { 1012 phis[valueIndex] = createValuePhi(values[valueIndex].stamp(NodeView.DEFAULT).unrestricted()); 1013 } 1014 if (twoSlotKinds != null && twoSlotKinds[valueIndex] != null) { 1015 // skip an entry after a long/double value that occupies two int slots 1016 valueIndex++; 1017 phis[valueIndex] = null; 1018 values[valueIndex] = tool.getIllegalConstant(); 1019 } 1020 valueIndex++; 1021 } 1022 1023 boolean materialized = false; 1024 for (int i = 0; i < values.length; i++) { 1025 PhiNode phi = phis[i]; 1026 if (phi != null) { 1027 mergeEffects.addFloatingNode(phi, "virtualMergePhi"); 1028 if (virtual.entryKind(tool.getMetaAccessExtensionProvider(), i) == JavaKind.Object) { 1029 materialized |= mergeObjectEntry(getObject, states, phi, i); 1030 } else { 1031 for (int i2 = 0; i2 < states.length; i2++) { 1032 ObjectState state = states[i2].getObjectState(getObject.applyAsInt(i2)); 1033 if (!state.isVirtual()) { 1034 break; 1035 } 1036 setPhiInput(phi, i2, state.getEntry(i)); 1037 } 1038 } 1039 values[i] = phi; 1040 } 1041 } 1042 newState.addObject(resultObject, new ObjectState(values, states[0].getObjectState(getObject.applyAsInt(0)).getLocks(), ensureVirtual)); 1043 return materialized; 1044 } else { 1045 // not compatible: materialize in all predecessors 1046 PhiNode materializedValuePhi = getPhi(resultObject, StampFactory.forKind(JavaKind.Object)); 1047 for (int i = 0; i < states.length; i++) { 1048 Block predecessor = getPredecessor(i); 1049 if (!ensureVirtual && states[i].getObjectState(getObject.applyAsInt(i)).isVirtual()) { 1050 // we can materialize if not all inputs are "ensureVirtualized" 1051 states[i].getObjectState(getObject.applyAsInt(i)).setEnsureVirtualized(false); 1052 } 1053 ensureMaterialized(states[i], getObject.applyAsInt(i), predecessor.getEndNode(), blockEffects.get(predecessor), COUNTER_MATERIALIZATIONS_MERGE); 1054 setPhiInput(materializedValuePhi, i, states[i].getObjectState(getObject.applyAsInt(i)).getMaterializedValue()); 1055 } 1056 newState.addObject(resultObject, new ObjectState(materializedValuePhi, null, ensureVirtual)); 1057 return true; 1058 } 1059 } 1060 1061 /** 1062 * Fill the inputs of the PhiNode corresponding to one {@link JavaKind#Object} entry in the 1063 * virtual object. 1064 * 1065 * @return true if materialization happened during the merge, false otherwise 1066 */ 1067 private boolean mergeObjectEntry(IntUnaryOperator objectIdFunc, PartialEscapeBlockState<?>[] states, PhiNode phi, int entryIndex) { 1068 boolean materialized = false; 1069 for (int i = 0; i < states.length; i++) { 1070 int object = objectIdFunc.applyAsInt(i); 1071 ObjectState objectState = states[i].getObjectState(object); 1072 if (!objectState.isVirtual()) { 1073 break; 1074 } 1075 ValueNode entry = objectState.getEntry(entryIndex); 1076 if (entry instanceof VirtualObjectNode) { 1077 VirtualObjectNode entryVirtual = (VirtualObjectNode) entry; 1078 Block predecessor = getPredecessor(i); 1079 materialized |= ensureMaterialized(states[i], entryVirtual.getObjectId(), predecessor.getEndNode(), blockEffects.get(predecessor), COUNTER_MATERIALIZATIONS_MERGE); 1080 objectState = states[i].getObjectState(object); 1081 if (objectState.isVirtual()) { 1082 states[i].setEntry(object, entryIndex, entry = states[i].getObjectState(entryVirtual.getObjectId()).getMaterializedValue()); 1083 } 1084 } 1085 setPhiInput(phi, i, entry); 1086 } 1087 return materialized; 1088 } 1089 1090 /** 1091 * Examine a PhiNode and try to replace it with merging of virtual objects if all its inputs 1092 * refer to virtual object states. In order for the merging to happen, all incoming object 1093 * states need to be compatible and without object identity (meaning that their object 1094 * identity if not used later on). 1095 * 1096 * @param phi the PhiNode that should be processed 1097 * @param states the predecessor block states of the merge 1098 * @return true if materialization happened during the merge, false otherwise 1099 */ 1100 private boolean processPhi(ValuePhiNode phi, PartialEscapeBlockState<?>[] states) { 1101 1102 // determine how many inputs are virtual and if they're all the same virtual object 1103 int virtualInputs = 0; 1104 boolean uniqueVirtualObject = true; 1105 boolean ensureVirtual = true; 1106 VirtualObjectNode[] virtualObjs = new VirtualObjectNode[states.length]; 1107 for (int i = 0; i < states.length; i++) { 1108 ValueNode alias = getAlias(getPhiValueAt(phi, i)); 1109 if (alias instanceof VirtualObjectNode) { 1110 VirtualObjectNode virtual = (VirtualObjectNode) alias; 1111 virtualObjs[i] = virtual; 1112 ObjectState objectState = states[i].getObjectStateOptional(virtual); 1113 if (objectState == null) { 1114 assert getPhiValueAt(phi, i) instanceof PhiNode : "this should only happen for phi nodes"; 1115 return false; 1116 } 1117 if (objectState.isVirtual()) { 1118 if (virtualObjs[0] != alias) { 1119 uniqueVirtualObject = false; 1120 } 1121 ensureVirtual &= objectState.getEnsureVirtualized(); 1122 virtualInputs++; 1123 } 1124 } 1125 } 1126 if (virtualInputs == states.length) { 1127 if (uniqueVirtualObject) { 1128 // all inputs refer to the same object: just make the phi node an alias 1129 addVirtualAlias(virtualObjs[0], phi); 1130 mergeEffects.deleteNode(phi); 1131 return false; 1132 } else { 1133 // all inputs are virtual: check if they're compatible and without identity 1134 boolean compatible = true; 1135 VirtualObjectNode firstVirtual = virtualObjs[0]; 1136 for (int i = 0; i < states.length; i++) { 1137 VirtualObjectNode virtual = virtualObjs[i]; 1138 1139 if (!firstVirtual.type().equals(virtual.type()) || firstVirtual.entryCount() != virtual.entryCount()) { 1140 compatible = false; 1141 break; 1142 } 1143 if (!states[0].getObjectState(firstVirtual).locksEqual(states[i].getObjectState(virtual))) { 1144 compatible = false; 1145 break; 1146 } 1147 } 1148 if (compatible) { 1149 for (int i = 0; i < states.length; i++) { 1150 VirtualObjectNode virtual = virtualObjs[i]; 1151 /* 1152 * check whether we trivially see that this is the only reference to 1153 * this allocation 1154 */ 1155 if (virtual.hasIdentity() && !isSingleUsageAllocation(getPhiValueAt(phi, i), virtualObjs, states[i])) { 1156 compatible = false; 1157 break; 1158 } 1159 } 1160 } 1161 if (compatible) { 1162 VirtualObjectNode virtual = getValueObjectVirtual(phi, virtualObjs[0]); 1163 mergeEffects.addFloatingNode(virtual, "valueObjectNode"); 1164 mergeEffects.deleteNode(phi); 1165 if (virtual.getObjectId() == -1) { 1166 int id = virtualObjects.size(); 1167 virtualObjects.add(virtual); 1168 virtual.setObjectId(id); 1169 } 1170 1171 int[] virtualObjectIds = new int[states.length]; 1172 for (int i = 0; i < states.length; i++) { 1173 virtualObjectIds[i] = virtualObjs[i].getObjectId(); 1174 } 1175 boolean materialized = mergeObjectStates(virtual.getObjectId(), virtualObjectIds, states); 1176 addVirtualAlias(virtual, virtual); 1177 addVirtualAlias(virtual, phi); 1178 return materialized; 1179 } 1180 } 1181 } 1182 1183 // otherwise: materialize all phi inputs 1184 boolean materialized = false; 1185 if (virtualInputs > 0) { 1186 for (int i = 0; i < states.length; i++) { 1187 VirtualObjectNode virtual = virtualObjs[i]; 1188 if (virtual != null) { 1189 Block predecessor = getPredecessor(i); 1190 if (!ensureVirtual && states[i].getObjectState(virtual).isVirtual()) { 1191 // we can materialize if not all inputs are "ensureVirtualized" 1192 states[i].getObjectState(virtual).setEnsureVirtualized(false); 1193 } 1194 materialized |= ensureMaterialized(states[i], virtual.getObjectId(), predecessor.getEndNode(), blockEffects.get(predecessor), COUNTER_MATERIALIZATIONS_PHI); 1195 } 1196 } 1197 } 1198 for (int i = 0; i < states.length; i++) { 1199 VirtualObjectNode virtual = virtualObjs[i]; 1200 if (virtual != null) { 1201 setPhiInput(phi, i, getAliasAndResolve(states[i], virtual)); 1202 } 1203 } 1204 return materialized; 1205 } 1206 1207 private boolean isSingleUsageAllocation(ValueNode value, VirtualObjectNode[] virtualObjs, PartialEscapeBlockState<?> state) { 1208 /* 1209 * If the phi input is an allocation, we know that it is a "fresh" value, i.e., that 1210 * this is a value that will only appear through this source, and cannot appear anywhere 1211 * else. If the phi is also the only usage of this input, we know that no other place 1212 * can check object identity against it, so it is safe to lose the object identity here. 1213 */ 1214 if (!(value instanceof AllocatedObjectNode && value.hasExactlyOneUsage())) { 1215 return false; 1216 } 1217 1218 /* 1219 * Check that the state only references the one virtual object from the Phi. 1220 */ 1221 VirtualObjectNode singleVirtual = null; 1222 for (int v = 0; v < virtualObjs.length; v++) { 1223 if (state.contains(virtualObjs[v])) { 1224 if (singleVirtual == null) { 1225 singleVirtual = virtualObjs[v]; 1226 } else if (singleVirtual != virtualObjs[v]) { 1227 /* 1228 * More than one virtual object is visible in the object state. 1229 */ 1230 return false; 1231 } 1232 } 1233 } 1234 return true; 1235 } 1236 } 1237 1238 public ObjectState getObjectState(PartialEscapeBlockState<?> state, ValueNode value) { 1239 if (value == null) { 1240 return null; 1241 } 1242 if (value.isAlive() && !aliases.isNew(value)) { 1243 ValueNode object = aliases.get(value); 1244 return object instanceof VirtualObjectNode ? state.getObjectStateOptional((VirtualObjectNode) object) : null; 1245 } else { 1246 if (value instanceof VirtualObjectNode) { 1247 return state.getObjectStateOptional((VirtualObjectNode) value); 1248 } 1249 return null; 1250 } 1251 } 1252 1253 public ValueNode getAlias(ValueNode value) { 1254 if (value != null && !(value instanceof VirtualObjectNode)) { 1255 if (value.isAlive() && !aliases.isNew(value)) { 1256 ValueNode result = aliases.get(value); 1257 if (result != null) { 1258 return result; 1259 } 1260 } 1261 } 1262 return value; 1263 } 1264 1265 public ValueNode getAliasAndResolve(PartialEscapeBlockState<?> state, ValueNode value) { 1266 ValueNode result = getAlias(value); 1267 if (result instanceof VirtualObjectNode) { 1268 int id = ((VirtualObjectNode) result).getObjectId(); 1269 if (id != -1 && !state.getObjectState(id).isVirtual()) { 1270 result = state.getObjectState(id).getMaterializedValue(); 1271 } 1272 } 1273 return result; 1274 } 1275 1276 void addVirtualAlias(VirtualObjectNode virtual, ValueNode node) { 1277 if (node.isAlive()) { 1278 aliases.set(node, virtual); 1279 for (Node usage : node.usages()) { 1280 markVirtualUsages(usage); 1281 } 1282 } 1283 } 1284 1285 private void markVirtualUsages(Node node) { 1286 if (!hasVirtualInputs.isNew(node) && !hasVirtualInputs.isMarked(node)) { 1287 hasVirtualInputs.mark(node); 1288 if (node instanceof VirtualState) { 1289 for (Node usage : node.usages()) { 1290 markVirtualUsages(usage); 1291 } 1292 } 1293 } 1294 } 1295 } 1296