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