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