Mercurial > hg > truffle
changeset 20157:8ff9e165002b
canonicalize during PEA
line wrap: on
line diff
--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Graph.java Thu Apr 02 14:50:16 2015 +0200 +++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Graph.java Thu Apr 02 14:55:50 2015 +0200 @@ -297,7 +297,20 @@ return add(node); } + public <T extends Node> void addWithoutUniqueWithInputs(T node) { + addInputs(node); + addHelper(node); + } + public <T extends Node> T addOrUniqueWithInputs(T node) { + addInputs(node); + if (node.getNodeClass().valueNumberable()) { + return uniqueHelper(node, true); + } + return add(node); + } + + private <T extends Node> void addInputs(T node) { NodePosIterator iterator = node.inputs().iterator(); while (iterator.hasNext()) { Position pos = iterator.nextPosition(); @@ -307,10 +320,6 @@ pos.initialize(node, addOrUniqueWithInputs(input)); } } - if (node.getNodeClass().valueNumberable()) { - return uniqueHelper(node, true); - } - return add(node); } private <T extends Node> T addHelper(T node) {
--- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/EffectList.java Thu Apr 02 14:50:16 2015 +0200 +++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/EffectList.java Thu Apr 02 14:55:50 2015 +0200 @@ -41,6 +41,10 @@ return true; } + default boolean isCfgKill() { + return false; + } + void apply(StructuredGraph graph, ArrayList<Node> obsoleteNodes); } @@ -158,20 +162,22 @@ return size == 0; } - public void apply(StructuredGraph graph, ArrayList<Node> obsoleteNodes) { + public void apply(StructuredGraph graph, ArrayList<Node> obsoleteNodes, boolean cfgKills) { for (int i = 0; i < size(); i++) { Effect effect = effects[i]; - try { - effect.apply(graph, obsoleteNodes); - } catch (Throwable t) { - StringBuilder str = new StringBuilder(); - toString(str, i); - throw new GraalInternalError(t).addContext("effect", str); - } - if (effect.isVisible() && Debug.isLogEnabled()) { - StringBuilder str = new StringBuilder(); - toString(str, i); - Debug.log(" %s", str); + if (effect.isCfgKill() == cfgKills) { + try { + effect.apply(graph, obsoleteNodes); + } catch (Throwable t) { + StringBuilder str = new StringBuilder(); + toString(str, i); + throw new GraalInternalError(t).addContext("effect", str); + } + if (effect.isVisible() && Debug.isLogEnabled()) { + StringBuilder str = new StringBuilder(); + toString(str, i); + Debug.log(" %s", str); + } } } }
--- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/EffectsBlockState.java Thu Apr 02 14:50:16 2015 +0200 +++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/EffectsBlockState.java Thu Apr 02 14:55:50 2015 +0200 @@ -26,6 +26,19 @@ public abstract class EffectsBlockState<T extends EffectsBlockState<T>> { + /* + * This flag specifies whether this path that leads to this block is unreachable. + */ + private boolean dead; + + public EffectsBlockState() { + // emtpy + } + + public EffectsBlockState(EffectsBlockState<T> other) { + this.dead = other.dead; + } + @Override public String toString() { return ""; @@ -33,6 +46,14 @@ protected abstract boolean equivalentTo(T other); + public boolean isDead() { + return dead; + } + + public void markAsDead() { + this.dead = true; + } + protected static <K, V> boolean compareMaps(Map<K, V> left, Map<K, V> right) { if (left.size() != right.size()) { return false;
--- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/EffectsClosure.java Thu Apr 02 14:50:16 2015 +0200 +++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/EffectsClosure.java Thu Apr 02 14:55:50 2015 +0200 @@ -22,14 +22,14 @@ */ package com.oracle.graal.virtual.phases.ea; -import static com.oracle.graal.compiler.common.GraalOptions.*; - import java.util.*; import com.oracle.graal.compiler.common.*; import com.oracle.graal.compiler.common.cfg.*; +import com.oracle.graal.compiler.common.type.*; import com.oracle.graal.debug.*; import com.oracle.graal.graph.*; +import com.oracle.graal.graph.iterators.*; import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.cfg.*; import com.oracle.graal.nodes.util.*; @@ -48,6 +48,7 @@ protected final BlockMap<GraphEffectList> blockEffects; private final Map<Loop<Block>, GraphEffectList> loopMergeEffects = CollectionsFactory.newIdentityMap(); private final Map<LoopBeginNode, BlockT> loopEntryStates = Node.newIdentityMap(); + private final NodeBitMap hasScalarReplacedInputs; protected boolean changed; @@ -55,6 +56,7 @@ this.schedule = schedule; this.cfg = cfg; this.aliases = cfg.graph.createNodeMap(); + this.hasScalarReplacedInputs = cfg.graph.createNodeBitMap(); this.blockEffects = new BlockMap<>(cfg); for (Block block : cfg.getBlocks()) { blockEffects.put(block, new GraphEffectList()); @@ -67,9 +69,10 @@ } @Override - public void applyEffects() { + public final void applyEffects() { final StructuredGraph graph = cfg.graph; final ArrayList<Node> obsoleteNodes = new ArrayList<>(0); + final ArrayList<GraphEffectList> effectList = new ArrayList<>(); BlockIteratorClosure<Void> closure = new BlockIteratorClosure<Void>() { @Override @@ -77,19 +80,15 @@ return null; } - private void apply(GraphEffectList effects, Object context) { - if (!effects.isEmpty()) { - Debug.log(" ==== effects for %s", context); - effects.apply(graph, obsoleteNodes); - if (TraceEscapeAnalysis.getValue()) { - Debug.dump(5, graph, "After processing EffectsList for %s", context); - } + private void apply(GraphEffectList effects) { + if (effects != null && !effects.isEmpty()) { + effectList.add(effects); } } @Override protected Void processBlock(Block block, Void currentState) { - apply(blockEffects.get(block), block); + apply(blockEffects.get(block)); return currentState; } @@ -106,11 +105,20 @@ @Override protected List<Void> processLoop(Loop<Block> loop, Void initialState) { LoopInfo<Void> info = ReentrantBlockIterator.processLoop(this, loop, initialState); - apply(loopMergeEffects.get(loop), loop); + apply(loopMergeEffects.get(loop)); return info.exitStates; } }; ReentrantBlockIterator.apply(closure, cfg.getStartBlock()); + for (GraphEffectList effects : effectList) { + Debug.log(" ==== effects"); + effects.apply(graph, obsoleteNodes, false); + } + for (GraphEffectList effects : effectList) { + Debug.log(" ==== cfg kill effects"); + effects.apply(graph, obsoleteNodes, true); + } + Debug.dump(4, graph, "After applying effects"); assert VirtualUtil.assertNonReachable(graph, obsoleteNodes); for (Node node : obsoleteNodes) { if (node.isAlive()) { @@ -122,26 +130,45 @@ @Override protected BlockT processBlock(Block block, BlockT state) { - VirtualUtil.trace("\nBlock: %s, preds: %s, succ: %s (", block, block.getPredecessors(), block.getSuccessors()); + if (!state.isDead()) { + GraphEffectList effects = blockEffects.get(block); + + if (block.getBeginNode().predecessor() instanceof IfNode) { + IfNode ifNode = (IfNode) block.getBeginNode().predecessor(); + LogicNode condition = ifNode.condition(); + Node alias = getScalarAlias(condition); + if (alias instanceof LogicConstantNode) { + LogicConstantNode constant = (LogicConstantNode) alias; + boolean deadBranch = constant.getValue() != (block.getBeginNode() == ifNode.trueSuccessor()); + + if (deadBranch) { + state.markAsDead(); + effects.killIfBranch(ifNode, constant.getValue()); + return state; + } + } + } - GraphEffectList effects = blockEffects.get(block); - FixedWithNextNode lastFixedNode = block.getBeginNode().predecessor() instanceof FixedWithNextNode ? (FixedWithNextNode) block.getBeginNode().predecessor() : null; - Iterable<? extends Node> nodes = schedule != null ? schedule.getBlockToNodesMap().get(block) : block.getNodes(); - for (Node node : nodes) { - aliases.set(node, null); - if (node instanceof LoopExitNode) { - LoopExitNode loopExit = (LoopExitNode) node; - for (ProxyNode proxy : loopExit.proxies()) { - changed |= processNode(proxy, state, effects, lastFixedNode); + VirtualUtil.trace("\nBlock: %s, preds: %s, succ: %s (", block, block.getPredecessors(), block.getSuccessors()); + + FixedWithNextNode lastFixedNode = block.getBeginNode().predecessor() instanceof FixedWithNextNode ? (FixedWithNextNode) block.getBeginNode().predecessor() : null; + Iterable<? extends Node> nodes = schedule != null ? schedule.getBlockToNodesMap().get(block) : block.getNodes(); + for (Node node : nodes) { + aliases.set(node, null); + if (node instanceof LoopExitNode) { + LoopExitNode loopExit = (LoopExitNode) node; + for (ProxyNode proxy : loopExit.proxies()) { + changed |= processNode(proxy, state, effects, lastFixedNode); + } + processLoopExit(loopExit, loopEntryStates.get(loopExit.loopBegin()), state, blockEffects.get(block)); } - processLoopExit(loopExit, loopEntryStates.get(loopExit.loopBegin()), state, blockEffects.get(block)); + changed |= processNode(node, state, effects, lastFixedNode); + if (node instanceof FixedWithNextNode) { + lastFixedNode = (FixedWithNextNode) node; + } } - changed |= processNode(node, state, effects, lastFixedNode); - if (node instanceof FixedWithNextNode) { - lastFixedNode = (FixedWithNextNode) node; - } + VirtualUtil.trace(")\n end state: %s\n", state); } - VirtualUtil.trace(")\n end state: %s\n", state); return state; } @@ -151,7 +178,7 @@ protected BlockT merge(Block merge, List<BlockT> states) { assert blockEffects.get(merge).isEmpty(); MergeProcessor processor = createMergeProcessor(merge); - processor.merge(states); + doMergeWithoutDead(processor, states); processor.commitEnds(states); blockEffects.get(merge).addAll(processor.mergeEffects); blockEffects.get(merge).addAll(processor.afterMergeEffects); @@ -160,6 +187,14 @@ @Override protected final List<BlockT> processLoop(Loop<Block> loop, BlockT initialState) { + if (initialState.isDead()) { + ArrayList<BlockT> states = new ArrayList<>(); + for (int i = 0; i < loop.getExits().size(); i++) { + states.add(initialState); + } + return states; + } + BlockT loopEntryState = initialState; BlockT lastMergedState = cloneState(initialState); MergeProcessor mergeProcessor = createMergeProcessor(loop.getHeader()); @@ -169,7 +204,7 @@ List<BlockT> states = new ArrayList<>(); states.add(initialState); states.addAll(info.endStates); - mergeProcessor.merge(states); + doMergeWithoutDead(mergeProcessor, states); Debug.log("================== %s", loop.getHeader()); Debug.log("%s", mergeProcessor.newState); @@ -197,6 +232,36 @@ throw new GraalInternalError("too many iterations at %s", loop); } + private void doMergeWithoutDead(MergeProcessor mergeProcessor, List<BlockT> states) { + int alive = 0; + for (BlockT state : states) { + if (!state.isDead()) { + alive++; + } + } + if (alive == 0) { + mergeProcessor.setNewState(states.get(0)); + } else if (alive == states.size()) { + int[] stateIndexes = new int[states.size()]; + for (int i = 0; i < stateIndexes.length; i++) { + stateIndexes[i] = i; + } + mergeProcessor.setStateIndexes(stateIndexes); + mergeProcessor.merge(states); + } else { + ArrayList<BlockT> aliveStates = new ArrayList<>(alive); + int[] stateIndexes = new int[alive]; + for (int i = 0; i < states.size(); i++) { + if (!states.get(i).isDead()) { + stateIndexes[aliveStates.size()] = i; + aliveStates.add(states.get(i)); + } + } + mergeProcessor.setStateIndexes(stateIndexes); + mergeProcessor.merge(aliveStates); + } + } + private boolean assertExitStatesNonEmpty(Loop<Block> loop, LoopInfo<BlockT> info) { for (int i = 0; i < loop.getExits().size(); i++) { assert info.exitStates.get(i) != null : "no loop exit state at " + loop.getExits().get(i) + " / " + loop.getHeader(); @@ -210,11 +275,13 @@ protected class MergeProcessor { - protected final Block mergeBlock; - protected final AbstractMergeNode merge; + private final Block mergeBlock; + private final AbstractMergeNode merge; protected final GraphEffectList mergeEffects; protected final GraphEffectList afterMergeEffects; + + private int[] stateIndexes; protected BlockT newState; public MergeProcessor(Block mergeBlock) { @@ -228,15 +295,51 @@ * @param states the states that should be merged. */ protected void merge(List<BlockT> states) { - newState = getInitialState(); + setNewState(getInitialState()); + } + + private void setNewState(BlockT state) { + newState = state; mergeEffects.clear(); afterMergeEffects.clear(); } + private void setStateIndexes(int[] stateIndexes) { + this.stateIndexes = stateIndexes; + } + @SuppressWarnings("unused") protected void commitEnds(List<BlockT> states) { } + protected final Block getPredecessor(int index) { + return mergeBlock.getPredecessors().get(stateIndexes[index]); + } + + protected final NodeIterable<PhiNode> getPhis() { + return merge.phis(); + } + + protected final ValueNode getPhiValueAt(PhiNode phi, int index) { + return phi.valueAt(stateIndexes[index]); + } + + protected final ValuePhiNode createValuePhi(Stamp stamp) { + return new ValuePhiNode(stamp, merge, new ValueNode[mergeBlock.getPredecessorCount()]); + } + + protected final void setPhiInput(PhiNode phi, int index, ValueNode value) { + afterMergeEffects.initializePhiInput(phi, stateIndexes[index], value); + } + + protected final int getStateIndex(int i) { + return stateIndexes[i]; + } + + protected final StructuredGraph graph() { + return merge.graph(); + } + @Override public String toString() { return "MergeProcessor@" + merge; @@ -246,6 +349,15 @@ public void addScalarAlias(ValueNode node, ValueNode alias) { assert !(alias instanceof VirtualObjectNode); aliases.set(node, alias); + for (Node usage : node.usages()) { + if (!hasScalarReplacedInputs.isNew(usage)) { + hasScalarReplacedInputs.mark(usage); + } + } + } + + protected final boolean hasScalarReplacedInputs(Node node) { + return hasScalarReplacedInputs.isMarked(node); } public ValueNode getScalarAlias(ValueNode node) {
--- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/GraphEffectList.java Thu Apr 02 14:50:16 2015 +0200 +++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/GraphEffectList.java Thu Apr 02 14:55:50 2015 +0200 @@ -33,16 +33,16 @@ public class GraphEffectList extends EffectList { - public void addCounterBefore(final String group, final String name, final int increment, final boolean addContext, final FixedNode position) { + public void addCounterBefore(String group, String name, int increment, boolean addContext, FixedNode position) { add("add counter", graph -> DynamicCounterNode.addCounterBefore(group, name, increment, addContext, position)); } - public void addCounterAfter(final String group, final String name, final int increment, final boolean addContext, final FixedWithNextNode position) { + public void addCounterAfter(String group, String name, int increment, boolean addContext, FixedWithNextNode position) { FixedNode nextPosition = position.next(); add("add counter after", graph -> DynamicCounterNode.addCounterBefore(group, name, increment, addContext, nextPosition)); } - public void addWeakCounterCounterBefore(final String group, final String name, final int increment, final boolean addContext, final ValueNode checkedValue, final FixedNode position) { + public void addWeakCounterCounterBefore(String group, String name, int increment, boolean addContext, ValueNode checkedValue, FixedNode position) { add("add weak counter", graph -> WeakCounterNode.addCounterBefore(group, name, increment, addContext, checkedValue, position)); } @@ -53,36 +53,35 @@ * @param node The fixed node to be added to the graph. * @param position The fixed node before which the node should be added. */ - public void addFixedNodeBefore(final FixedWithNextNode node, final FixedNode position) { + public void addFixedNodeBefore(FixedWithNextNode node, FixedNode position) { add("add fixed node", graph -> { assert !node.isAlive() && !node.isDeleted() && position.isAlive(); graph.addBeforeFixed(position, graph.add(node)); }); } + public void ensureAdded(ValueNode node, FixedNode position) { + add("ensure added", graph -> { + assert position.isAlive(); + if (!node.isAlive()) { + graph.addWithoutUniqueWithInputs(node); + if (node instanceof FixedNode) { + graph.addBeforeFixed(position, (FixedWithNextNode) node); + } + } + }); + } + /** * Add the given floating node to the graph. * * @param node The floating node to be added. */ - public void addFloatingNode(final ValueNode node, @SuppressWarnings("unused") final String cause) { + public void addFloatingNode(ValueNode node, @SuppressWarnings("unused") String cause) { add("add floating node", graph -> graph.addWithoutUnique(node)); } /** - * Adds an value to the given phi node. - * - * @param node The phi node to which the value should be added. - * @param value The value that will be added to the phi node. - */ - public void addPhiInput(final PhiNode node, final ValueNode value) { - add("add phi input", graph -> { - assert node.isAlive() && value.isAlive() : node + " " + value; - node.addInput(value); - }); - } - - /** * Sets the phi node's input at the given index to the given value, adding new phi inputs as * needed. * @@ -90,7 +89,7 @@ * @param index The index of the phi input to be changed. * @param value The new value for the phi input. */ - public void initializePhiInput(final PhiNode node, final int index, final ValueNode value) { + public void initializePhiInput(PhiNode node, int index, ValueNode value) { add("set phi input", (graph, obsoleteNodes) -> { assert node.isAlive() && value.isAlive() && index >= 0; node.initializeValueAt(index, value); @@ -104,18 +103,20 @@ * @param node The frame state to which the state should be added. * @param state The virtual object state to add. */ - public void addVirtualMapping(final FrameState node, final EscapeObjectState state) { + public void addVirtualMapping(FrameState node, EscapeObjectState state) { add("add virtual mapping", new Effect() { @Override public void apply(StructuredGraph graph, ArrayList<Node> obsoleteNodes) { - assert node.isAlive() && !state.isDeleted(); - FrameState stateAfter = node; - for (int i = 0; i < stateAfter.virtualObjectMappingCount(); i++) { - if (stateAfter.virtualObjectMappingAt(i).object() == state.object()) { - stateAfter.virtualObjectMappings().remove(i); + if (node.isAlive()) { + assert !state.isDeleted(); + FrameState stateAfter = node; + for (int i = 0; i < stateAfter.virtualObjectMappingCount(); i++) { + if (stateAfter.virtualObjectMappingAt(i).object() == state.object()) { + stateAfter.virtualObjectMappings().remove(i); + } } + stateAfter.addVirtualObjectMapping(state.isAlive() ? state : graph.unique(state)); } - stateAfter.addVirtualObjectMapping(state.isAlive() ? state : graph.unique(state)); } @Override @@ -130,7 +131,7 @@ * * @param node The fixed node that should be deleted. */ - public void deleteNode(final Node node) { + public void deleteNode(Node node) { add("delete fixed node", (graph, obsoleteNodes) -> { if (node instanceof FixedWithNextNode) { GraphUtil.unlinkFixedNode((FixedWithNextNode) node); @@ -139,6 +140,18 @@ }); } + public void killIfBranch(IfNode ifNode, boolean constantCondition) { + add("kill if branch", new Effect() { + public void apply(StructuredGraph graph, ArrayList<Node> obsoleteNodes) { + graph.removeSplitPropagate(ifNode, ifNode.getSuccessor(constantCondition)); + } + + public boolean isCfgKill() { + return true; + } + }); + } + /** * Replaces the given node at its usages without deleting it. If the current node is a fixed * node it will be disconnected from the control flow, so that it will be deleted by a @@ -149,7 +162,7 @@ * non-connected {@link FixedWithNextNode} it will be added to the control flow. * */ - public void replaceAtUsages(final ValueNode node, final ValueNode replacement) { + public void replaceAtUsages(ValueNode node, ValueNode replacement) { add("replace at usages", (graph, obsoleteNodes) -> { assert node.isAlive() && replacement.isAlive(); if (replacement instanceof FixedWithNextNode && ((FixedWithNextNode) replacement).next() == null) { @@ -171,13 +184,15 @@ * @param oldInput The value to look for. * @param newInput The value to replace with. */ - public void replaceFirstInput(final Node node, final Node oldInput, final Node newInput) { + public void replaceFirstInput(Node node, Node oldInput, Node newInput) { assert node.isAlive() && oldInput.isAlive() && !newInput.isDeleted(); add("replace first input", new Effect() { @Override public void apply(StructuredGraph graph, ArrayList<Node> obsoleteNodes) { - assert node.isAlive() && oldInput.isAlive() && newInput.isAlive(); - node.replaceFirstInput(oldInput, newInput); + if (node.isAlive()) { + assert oldInput.isAlive() && newInput.isAlive(); + node.replaceFirstInput(oldInput, newInput); + } } @Override
--- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PEReadEliminationClosure.java Thu Apr 02 14:50:16 2015 +0200 +++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PEReadEliminationClosure.java Thu Apr 02 14:55:50 2015 +0200 @@ -272,29 +272,28 @@ PhiNode phiNode = getPhi(entry, value.stamp().unrestricted()); mergeEffects.addFloatingNode(phiNode, "mergeReadCache"); for (int i = 0; i < states.size(); i++) { - afterMergeEffects.addPhiInput(phiNode, states.get(i).getReadCache(key.object, key.identity, key.index, PEReadEliminationClosure.this)); + setPhiInput(phiNode, i, states.get(i).getReadCache(key.object, key.identity, key.index, PEReadEliminationClosure.this)); } newState.readCache.put(key, phiNode); } else if (value != null) { newState.readCache.put(key, value); } } - for (PhiNode phi : merge.phis()) { + for (PhiNode phi : getPhis()) { if (phi.getKind() == Kind.Object) { for (Map.Entry<ReadCacheEntry, ValueNode> entry : states.get(0).readCache.entrySet()) { - if (entry.getKey().object == phi.valueAt(0)) { + if (entry.getKey().object == getPhiValueAt(phi, 0)) { mergeReadCachePhi(phi, entry.getKey().identity, entry.getKey().index, states); } } - } } } private void mergeReadCachePhi(PhiNode phi, LocationIdentity identity, int index, List<PEReadEliminationBlockState> states) { - ValueNode[] values = new ValueNode[phi.valueCount()]; - for (int i = 0; i < phi.valueCount(); i++) { - ValueNode value = states.get(i).getReadCache(phi.valueAt(i), identity, index, PEReadEliminationClosure.this); + ValueNode[] values = new ValueNode[states.size()]; + for (int i = 0; i < states.size(); i++) { + ValueNode value = states.get(i).getReadCache(getPhiValueAt(phi, i), identity, index, PEReadEliminationClosure.this); if (value == null) { return; } @@ -304,7 +303,7 @@ PhiNode phiNode = getPhi(new ReadCacheEntry(identity, phi, index), values[0].stamp().unrestricted()); mergeEffects.addFloatingNode(phiNode, "mergeReadCachePhi"); for (int i = 0; i < values.length; i++) { - afterMergeEffects.addPhiInput(phiNode, values[i]); + setPhiInput(phiNode, i, values[i]); } newState.readCache.put(new ReadCacheEntry(identity, phi, index), phiNode); }
--- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PartialEscapeBlockState.java Thu Apr 02 14:50:16 2015 +0200 +++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PartialEscapeBlockState.java Thu Apr 02 14:55:50 2015 +0200 @@ -53,6 +53,7 @@ } protected PartialEscapeBlockState(PartialEscapeBlockState<T> other) { + super(other); for (Map.Entry<VirtualObjectNode, ObjectState> entry : other.objectStates.entrySet()) { objectStates.put(entry.getKey(), entry.getValue().cloneState()); }
--- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PartialEscapeClosure.java Thu Apr 02 14:50:16 2015 +0200 +++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PartialEscapeClosure.java Thu Apr 02 14:55:50 2015 +0200 @@ -30,6 +30,7 @@ import com.oracle.graal.compiler.common.util.*; import com.oracle.graal.debug.*; import com.oracle.graal.graph.*; +import com.oracle.graal.graph.spi.*; import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.VirtualState.NodeClosure; import com.oracle.graal.nodes.cfg.*; @@ -51,7 +52,7 @@ public static final DebugMetric METRIC_MEMORYCHECKPOINT = Debug.metric("MemoryCheckpoint"); - private final NodeBitMap usages; + private final NodeBitMap hasVirtualInputs; private final VirtualizerToolImpl tool; private final class CollectVirtualObjectsClosure extends NodeClosure<ValueNode> { @@ -109,7 +110,7 @@ public PartialEscapeClosure(SchedulePhase schedule, MetaAccessProvider metaAccess, ConstantReflectionProvider constantReflection) { super(schedule, schedule.getCFG()); - this.usages = schedule.getCFG().graph.createNodeBitMap(); + this.hasVirtualInputs = schedule.getCFG().graph.createNodeBitMap(); this.tool = new VirtualizerToolImpl(metaAccess, constantReflection, this); } @@ -118,43 +119,157 @@ */ @Override protected boolean processNode(Node node, BlockT state, GraphEffectList effects, FixedWithNextNode lastFixedNode) { - boolean isMarked = usages.isMarked(node); - if ((isMarked && node instanceof ValueNode) || node instanceof VirtualizableAllocation) { - VirtualUtil.trace("[[%s]] ", node); - FixedNode nextFixedNode = lastFixedNode == null ? null : lastFixedNode.next(); - return processNode((ValueNode) node, nextFixedNode, state, effects, isMarked); - } else { - VirtualUtil.trace("%s ", node); + /* + * These checks make up for the fact that an earliest schedule moves CallTargetNodes upwards + * and thus materializes virtual objects needlessly. Also, FrameStates and ConstantNodes are + * scheduled, but can safely be ignored. + */ + if (node instanceof CallTargetNode || node instanceof FrameState || node instanceof ConstantNode) { return false; + } else if (node instanceof Invoke) { + processNodeInternal(((Invoke) node).callTarget(), state, effects, lastFixedNode); } + return processNodeInternal(node, state, effects, lastFixedNode); + } + + private boolean processNodeInternal(Node node, BlockT state, GraphEffectList effects, FixedWithNextNode lastFixedNode) { + FixedNode nextFixedNode = lastFixedNode == null ? null : lastFixedNode.next(); + boolean significantChange = false; + VirtualUtil.trace("%s", node); + + if (node instanceof VirtualizableAllocation) { + significantChange |= processVirtualizable((ValueNode) node, nextFixedNode, state, effects); + if (tool.isDeleted()) { + VirtualUtil.trace("deleted virtualizable allocation %s", node); + return significantChange; + } + } + + if (hasVirtualInputs.isMarked(node) && node instanceof ValueNode) { + if (node instanceof Virtualizable) { + significantChange |= processVirtualizable((ValueNode) node, nextFixedNode, state, effects); + if (tool.isDeleted()) { + VirtualUtil.trace("deleted virtualizable node %s", node); + return significantChange; + } + } + processNodeInputs((ValueNode) node, nextFixedNode, state, effects); + } + + if (hasScalarReplacedInputs(node) && node instanceof ValueNode) { + significantChange |= processNodeWithScalarReplacedInputs((ValueNode) node, nextFixedNode, state, effects); + } + return significantChange; } - private boolean processNode(final ValueNode node, FixedNode insertBefore, final BlockT state, final GraphEffectList effects, boolean isMarked) { - tool.reset(state, node, insertBefore, effects); - if (node instanceof Virtualizable) { - ((Virtualizable) node).virtualize(tool); - } - if (tool.isDeleted()) { - return !(node instanceof CommitAllocationNode || node instanceof AllocatedObjectNode || node instanceof BoxNode); + private boolean processNodeWithScalarReplacedInputs(ValueNode node, FixedNode insertBefore, BlockT state, GraphEffectList effects) { + ValueNode canonicalizedValue = node; + if (node instanceof Canonicalizable.Unary<?>) { + @SuppressWarnings("unchecked") + Canonicalizable.Unary<ValueNode> canonicalizable = (Canonicalizable.Unary<ValueNode>) node; + ObjectState valueObj = getObjectState(state, canonicalizable.getValue()); + ValueNode valueAlias = valueObj != null ? valueObj.getMaterializedValue() : getScalarAlias(canonicalizable.getValue()); + if (valueAlias != canonicalizable.getValue()) { + canonicalizedValue = (ValueNode) canonicalizable.canonical(tool, valueAlias); + } + } else if (node instanceof Canonicalizable.Binary<?>) { + @SuppressWarnings("unchecked") + Canonicalizable.Binary<ValueNode> canonicalizable = (Canonicalizable.Binary<ValueNode>) node; + ObjectState xObj = getObjectState(state, canonicalizable.getX()); + ValueNode xAlias = xObj != null ? xObj.getMaterializedValue() : getScalarAlias(canonicalizable.getX()); + ObjectState yObj = getObjectState(state, canonicalizable.getY()); + ValueNode yAlias = yObj != null ? yObj.getMaterializedValue() : getScalarAlias(canonicalizable.getY()); + if (xAlias != canonicalizable.getX() || yAlias != canonicalizable.getY()) { + canonicalizedValue = (ValueNode) canonicalizable.canonical(tool, xAlias, yAlias); + } + } else { + return false; } - if (isMarked) { - for (Node input : node.inputs()) { - if (input instanceof ValueNode) { - ObjectState obj = getObjectState(state, (ValueNode) input); - if (obj != null) { - VirtualUtil.trace("replacing input %s at %s: %s", input, node, obj); - replaceWithMaterialized(input, node, insertBefore, state, obj, effects, METRIC_MATERIALIZATIONS_UNHANDLED); + if (canonicalizedValue != node && canonicalizedValue != null) { + if (canonicalizedValue.isAlive()) { + ObjectState obj = getObjectState(state, canonicalizedValue); + if (obj != null) { + if (obj.getState() == EscapeState.Virtual) { + addAndMarkAlias(obj.virtual, node); + effects.deleteNode(node); + } else { + effects.replaceAtUsages(node, obj.getMaterializedValue()); + addScalarAlias(node, obj.getMaterializedValue()); } + } else { + ValueNode alias = getScalarAlias(canonicalizedValue); + effects.replaceAtUsages(node, alias); + addScalarAlias(node, alias); } + } else { + if (!prepareCanonicalNode(canonicalizedValue, state, effects)) { + VirtualUtil.trace("replacement via canonicalization too complex: %s -> %s", node, canonicalizedValue); + return false; + } + effects.ensureAdded(canonicalizedValue, insertBefore); + effects.replaceAtUsages(node, canonicalizedValue); + addScalarAlias(node, canonicalizedValue); } - if (node instanceof NodeWithState) { - processNodeWithState((NodeWithState) node, state, effects); - } + VirtualUtil.trace("replaced via canonicalization: %s -> %s", node, canonicalizedValue); + return true; } return false; } - private void processNodeWithState(NodeWithState nodeWithState, final BlockT state, final GraphEffectList effects) { + private boolean prepareCanonicalNode(ValueNode node, BlockT state, GraphEffectList effects) { + assert !node.isAlive(); + NodePosIterator iter = node.inputs().iterator(); + while (iter.hasNext()) { + Position pos = iter.nextPosition(); + Node input = pos.get(node); + if (input instanceof ValueNode) { + if (input.isAlive()) { + ObjectState obj = getObjectState(state, (ValueNode) input); + if (obj != null) { + if (obj.getState() == EscapeState.Virtual) { + return false; + } else { + pos.initialize(node, obj.getMaterializedValue()); + } + } else { + pos.initialize(node, getScalarAlias((ValueNode) input)); + } + } else { + if (!prepareCanonicalNode((ValueNode) input, state, effects)) { + return false; + } + } + } + } + return true; + } + + private void processNodeInputs(ValueNode node, FixedNode insertBefore, BlockT state, GraphEffectList effects) { + VirtualUtil.trace("processing nodewithstate: %s", node); + for (Node input : node.inputs()) { + if (input instanceof ValueNode) { + ObjectState obj = getObjectState(state, (ValueNode) input); + if (obj != null) { + VirtualUtil.trace("replacing input %s at %s: %s", input, node, obj); + replaceWithMaterialized(input, node, insertBefore, state, obj, effects, METRIC_MATERIALIZATIONS_UNHANDLED); + } + } + } + if (node instanceof NodeWithState) { + processNodeWithState((NodeWithState) node, state, effects); + } + } + + private boolean processVirtualizable(ValueNode node, FixedNode insertBefore, BlockT state, GraphEffectList effects) { + tool.reset(state, node, insertBefore, effects); + ((Virtualizable) node).virtualize(tool); + if (tool.isDeleted()) { + return !(node instanceof CommitAllocationNode || node instanceof AllocatedObjectNode || node instanceof BoxNode); + } + return false; + } + + private void processNodeWithState(NodeWithState nodeWithState, BlockT state, GraphEffectList effects) { for (FrameState fs : nodeWithState.states()) { FrameState frameState = getUniqueFramestate(nodeWithState, fs); Set<ObjectState> virtual = new ArraySet<>(); @@ -317,7 +432,7 @@ if (needsCaching) { return getPhiCached(virtual, stamp); } else { - return new ValuePhiNode(stamp, merge); + return createValuePhi(stamp); } } @@ -327,7 +442,7 @@ } ValuePhiNode result = materializedPhis.get(virtual); if (result == null) { - result = new ValuePhiNode(stamp, merge); + result = createValuePhi(stamp); materializedPhis.put(virtual, result); } return result; @@ -425,18 +540,18 @@ for (int i = 0; i < objStates.length; i++) { ObjectState obj = objStates[i]; if (obj.isVirtual()) { - Block predecessor = mergeBlock.getPredecessors().get(i); + Block predecessor = getPredecessor(i); materialized |= ensureMaterialized(states.get(i), obj, predecessor.getEndNode(), blockEffects.get(predecessor), METRIC_MATERIALIZATIONS_MERGE); } - afterMergeEffects.addPhiInput(materializedValuePhi, obj.getMaterializedValue()); + setPhiInput(materializedValuePhi, i, obj.getMaterializedValue()); } newState.addObject(object, new ObjectState(object, materializedValuePhi, EscapeState.Materialized, null)); } } } - for (PhiNode phi : merge.phis()) { - if (usages.isMarked(phi) && phi instanceof ValuePhiNode) { + for (PhiNode phi : getPhis()) { + if (hasVirtualInputs.isMarked(phi) && phi instanceof ValuePhiNode) { materialized |= processPhi((ValuePhiNode) phi, states, virtualObjTemp); } } @@ -511,8 +626,8 @@ ValueNode nextValue = objStates[i].getEntry(valueIndex + 1); if (value.isConstant() && value.asConstant().equals(JavaConstant.INT_0) && nextValue.isConstant() && nextValue.asConstant().equals(JavaConstant.INT_0)) { // rewrite to a zero constant of the larger kind - objStates[i].setEntry(valueIndex, ConstantNode.defaultForKind(twoSlotKinds[valueIndex], merge.graph())); - objStates[i].setEntry(valueIndex + 1, ConstantNode.forConstant(JavaConstant.forIllegal(), tool.getMetaAccessProvider(), merge.graph())); + objStates[i].setEntry(valueIndex, ConstantNode.defaultForKind(twoSlotKinds[valueIndex], graph())); + objStates[i].setEntry(valueIndex + 1, ConstantNode.forConstant(JavaConstant.forIllegal(), tool.getMetaAccessProvider(), graph())); } else { compatible = false; break outer; @@ -529,19 +644,21 @@ int valueIndex = 0; while (valueIndex < values.length) { for (int i = 1; i < objStates.length; i++) { - ValueNode field = objStates[i].getEntry(valueIndex); - if (phis[valueIndex] == null && values[valueIndex] != field) { - phis[valueIndex] = new ValuePhiNode(values[valueIndex].stamp().unrestricted(), merge); + if (phis[valueIndex] == null) { + ValueNode field = objStates[i].getEntry(valueIndex); + if (values[valueIndex] != field) { + phis[valueIndex] = createValuePhi(values[valueIndex].stamp().unrestricted()); + } } } if (phis[valueIndex] != null && !phis[valueIndex].stamp().isCompatible(values[valueIndex].stamp())) { - phis[valueIndex] = new ValuePhiNode(values[valueIndex].stamp().unrestricted(), merge); + phis[valueIndex] = createValuePhi(values[valueIndex].stamp().unrestricted()); } if (twoSlotKinds != null && twoSlotKinds[valueIndex] != null) { // skip an entry after a long/double value that occupies two int slots valueIndex++; phis[valueIndex] = null; - values[valueIndex] = ConstantNode.forConstant(JavaConstant.forIllegal(), tool.getMetaAccessProvider(), merge.graph()); + values[valueIndex] = ConstantNode.forConstant(JavaConstant.forIllegal(), tool.getMetaAccessProvider(), graph()); } valueIndex++; } @@ -566,9 +683,9 @@ PhiNode materializedValuePhi = getPhi(object, StampFactory.forKind(Kind.Object)); for (int i = 0; i < blockStates.size(); i++) { ObjectState obj = objStates[i]; - Block predecessor = mergeBlock.getPredecessors().get(i); + Block predecessor = getPredecessor(i); ensureMaterialized(blockStates.get(i), obj, predecessor.getEndNode(), blockEffects.get(predecessor), METRIC_MATERIALIZATIONS_MERGE); - afterMergeEffects.addPhiInput(materializedValuePhi, obj.getMaterializedValue()); + setPhiInput(materializedValuePhi, i, obj.getMaterializedValue()); } newState.addObject(object, new ObjectState(object, materializedValuePhi, EscapeState.Materialized, null)); return true; @@ -590,13 +707,13 @@ ValueNode entry = objStates[i].getEntry(entryIndex); if (entry instanceof VirtualObjectNode) { ObjectState obj = blockStates.get(i).getObjectState((VirtualObjectNode) entry); - Block predecessor = mergeBlock.getPredecessors().get(i); + Block predecessor = getPredecessor(i); materialized |= ensureMaterialized(blockStates.get(i), obj, predecessor.getEndNode(), blockEffects.get(predecessor), METRIC_MATERIALIZATIONS_MERGE); if (objStates[i].isVirtual()) { objStates[i].setEntry(entryIndex, entry = obj.getMaterializedValue()); } } - afterMergeEffects.addPhiInput(phi, entry); + setPhiInput(phi, i, entry); } return materialized; } @@ -606,11 +723,12 @@ * object. */ private void mergePrimitiveEntry(ObjectState[] objStates, PhiNode phi, int entryIndex) { - for (ObjectState state : objStates) { + for (int i = 0; i < objStates.length; i++) { + ObjectState state = objStates[i]; if (!state.isVirtual()) { break; } - afterMergeEffects.addPhiInput(phi, state.getEntry(entryIndex)); + setPhiInput(phi, i, state.getEntry(entryIndex)); } } @@ -628,14 +746,13 @@ */ private boolean processPhi(ValuePhiNode phi, List<BlockT> states, Set<VirtualObjectNode> mergedVirtualObjects) { aliases.set(phi, null); - assert states.size() == phi.valueCount(); // determine how many inputs are virtual and if they're all the same virtual object int virtualInputs = 0; ObjectState[] objStates = new ObjectState[states.size()]; boolean uniqueVirtualObject = true; for (int i = 0; i < objStates.length; i++) { - ObjectState obj = objStates[i] = getObjectState(states.get(i), phi.valueAt(i)); + ObjectState obj = objStates[i] = getObjectState(states.get(i), getPhiValueAt(phi, i)); if (obj != null) { if (obj.isVirtual()) { if (objStates[0] == null || objStates[0].virtual != obj.virtual) { @@ -667,9 +784,9 @@ } if (compatible && hasIdentity) { // we still need to check whether this value is referenced by any other phi - outer: for (PhiNode otherPhi : merge.phis().filter(otherPhi -> otherPhi != phi)) { + outer: for (PhiNode otherPhi : getPhis().filter(otherPhi -> otherPhi != phi)) { for (int i = 0; i < objStates.length; i++) { - ObjectState otherPhiValueState = getObjectState(states.get(i), otherPhi.valueAt(i)); + ObjectState otherPhiValueState = getObjectState(states.get(i), getPhiValueAt(otherPhi, i)); if (Arrays.asList(objStates).contains(otherPhiValueState)) { compatible = false; break outer; @@ -679,7 +796,7 @@ } if (compatible) { - VirtualObjectNode virtual = getValueObjectVirtual(phi, getObjectState(states.get(0), phi.valueAt(0)).virtual); + VirtualObjectNode virtual = getValueObjectVirtual(phi, getObjectState(states.get(0), getPhiValueAt(phi, 0)).virtual); mergeEffects.addFloatingNode(virtual, "valueObjectNode"); mergeEffects.deleteNode(phi); @@ -696,9 +813,9 @@ for (int i = 0; i < objStates.length; i++) { ObjectState obj = objStates[i]; if (obj != null) { - Block predecessor = mergeBlock.getPredecessors().get(i); + Block predecessor = getPredecessor(i); materialized |= ensureMaterialized(states.get(i), obj, predecessor.getEndNode(), blockEffects.get(predecessor), METRIC_MATERIALIZATIONS_PHI); - afterMergeEffects.initializePhiInput(phi, i, obj.getMaterializedValue()); + setPhiInput(phi, i, obj.getMaterializedValue()); } } return materialized; @@ -730,12 +847,12 @@ } private void markVirtualUsages(Node node) { - if (!usages.isNew(node)) { - usages.mark(node); - } - if (node instanceof VirtualState) { - for (Node usage : node.usages()) { - markVirtualUsages(usage); + if (!hasVirtualInputs.isNew(node) && !hasVirtualInputs.isMarked(node)) { + hasVirtualInputs.mark(node); + if (node instanceof VirtualState) { + for (Node usage : node.usages()) { + markVirtualUsages(usage); + } } } }
--- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/ReadEliminationClosure.java Thu Apr 02 14:50:16 2015 +0200 +++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/ReadEliminationClosure.java Thu Apr 02 14:55:50 2015 +0200 @@ -203,7 +203,7 @@ protected <T> PhiNode getCachedPhi(T virtual, Stamp stamp) { ValuePhiNode result = materializedPhis.get(virtual); if (result == null) { - result = new ValuePhiNode(stamp, merge); + result = createValuePhi(stamp); materializedPhis.put(virtual, result); } return result; @@ -236,17 +236,17 @@ PhiNode phiNode = getCachedPhi(entry, value.stamp().unrestricted()); mergeEffects.addFloatingNode(phiNode, "mergeReadCache"); for (int i = 0; i < states.size(); i++) { - afterMergeEffects.addPhiInput(phiNode, states.get(i).getCacheEntry(key)); + setPhiInput(phiNode, i, states.get(i).getCacheEntry(key)); } newState.addCacheEntry(key, phiNode); } else if (value != null) { newState.addCacheEntry(key, value); } } - for (PhiNode phi : merge.phis()) { + for (PhiNode phi : getPhis()) { if (phi.getKind() == Kind.Object) { for (Map.Entry<CacheEntry<?>, ValueNode> entry : states.get(0).readCache.entrySet()) { - if (entry.getKey().object == phi.valueAt(0)) { + if (entry.getKey().object == getPhiValueAt(phi, 0)) { mergeReadCachePhi(phi, entry.getKey(), states); } } @@ -256,9 +256,9 @@ } private void mergeReadCachePhi(PhiNode phi, CacheEntry<?> identifier, List<ReadEliminationBlockState> states) { - ValueNode[] values = new ValueNode[phi.valueCount()]; - for (int i = 0; i < phi.valueCount(); i++) { - ValueNode value = states.get(i).getCacheEntry(identifier.duplicateWithObject(phi.valueAt(i))); + ValueNode[] values = new ValueNode[states.size()]; + for (int i = 0; i < states.size(); i++) { + ValueNode value = states.get(i).getCacheEntry(identifier.duplicateWithObject(getPhiValueAt(phi, i))); if (value == null) { return; } @@ -269,7 +269,7 @@ PhiNode phiNode = getCachedPhi(newIdentifier, values[0].stamp().unrestricted()); mergeEffects.addFloatingNode(phiNode, "mergeReadCachePhi"); for (int i = 0; i < values.length; i++) { - afterMergeEffects.addPhiInput(phiNode, values[i]); + setPhiInput(phiNode, i, values[i]); } newState.addCacheEntry(newIdentifier, phiNode); }
--- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/VirtualizerToolImpl.java Thu Apr 02 14:50:16 2015 +0200 +++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/VirtualizerToolImpl.java Thu Apr 02 14:55:50 2015 +0200 @@ -28,6 +28,7 @@ import com.oracle.graal.api.meta.*; import com.oracle.graal.graph.*; +import com.oracle.graal.graph.spi.*; import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.calc.*; import com.oracle.graal.nodes.java.*; @@ -36,7 +37,7 @@ import com.oracle.graal.nodes.spi.*; import com.oracle.graal.nodes.virtual.*; -class VirtualizerToolImpl implements VirtualizerTool { +class VirtualizerToolImpl implements VirtualizerTool, CanonicalizerTool { private final MetaAccessProvider metaAccess; private final ConstantReflectionProvider constantReflection; @@ -187,4 +188,16 @@ } } } + + public MetaAccessProvider getMetaAccess() { + return metaAccess; + } + + public ConstantReflectionProvider getConstantReflection() { + return constantReflection; + } + + public boolean canonicalizeReads() { + return false; + } }