Mercurial > hg > truffle
changeset 8548:51d5999900e2
simple iterative inlining, simple read elimination in PEA
line wrap: on
line diff
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java Mon Mar 25 11:09:40 2013 +0100 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java Thu Mar 07 13:47:09 2013 +0100 @@ -121,7 +121,11 @@ } if (GraalOptions.Inline && !plan.isPhaseDisabled(InliningPhase.class)) { - new InliningPhase(runtime, null, assumptions, cache, plan, optimisticOpts).apply(graph); + if (GraalOptions.IterativeInlining) { + new IterativeInliningPhase(runtime, assumptions, cache, plan, optimisticOpts).apply(graph); + } else { + new InliningPhase(runtime, null, assumptions, cache, plan, optimisticOpts).apply(graph); + } new DeadCodeEliminationPhase().apply(graph); if (GraalOptions.ConditionalElimination && GraalOptions.OptCanonicalizer) {
--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/InliningPhase.java Mon Mar 25 11:09:40 2013 +0100 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/InliningPhase.java Thu Mar 07 13:47:09 2013 +0100 @@ -57,6 +57,10 @@ private final OptimisticOptimizations optimisticOpts; private CustomCanonicalizer customCanonicalizer; + private int inliningCount; + + private int maxMethodPerInlining = Integer.MAX_VALUE; + // Metrics private static final DebugMetric metricInliningPerformed = Debug.metric("InliningPerformed"); private static final DebugMetric metricInliningConsidered = Debug.metric("InliningConsidered"); @@ -71,6 +75,10 @@ this.customCanonicalizer = customCanonicalizer; } + public void setMaxMethodsPerInlining(int max) { + maxMethodPerInlining = max; + } + public InliningPhase(GraalCodeCacheProvider runtime, Assumptions assumptions, GraphCache cache, PhasePlan plan, InliningPolicy inliningPolicy, OptimisticOptimizations optimisticOpts) { this.runtime = runtime; this.assumptions = assumptions; @@ -80,6 +88,10 @@ this.optimisticOpts = optimisticOpts; } + public int getInliningCount() { + return inliningCount; + } + @Override protected void run(final StructuredGraph graph) { inliningPolicy.initialize(graph); @@ -89,6 +101,7 @@ if (candidate != null) { boolean isWorthInlining = inliningPolicy.isWorthInlining(candidate); + isWorthInlining &= candidate.numberOfMethods() <= maxMethodPerInlining; metricInliningConsidered.increment(); if (isWorthInlining) { @@ -102,6 +115,7 @@ if (GraalOptions.OptCanonicalizer) { new CanonicalizerPhase(runtime, assumptions, invokeUsages, mark, customCanonicalizer).apply(graph); } + inliningCount++; metricInliningPerformed.increment(); } catch (BailoutException bailout) { throw bailout; @@ -185,9 +199,12 @@ return InliningUtil.logInlinedMethod(info, "intrinsic"); } - int bytecodeSize = bytecodeCodeSize(info); - int complexity = compilationComplexity(info); - int compiledCodeSize = compiledCodeSize(info); + boolean preferredInvoke = hints != null && hints.contains(info.invoke()); + int bonus = preferredInvoke ? 2 : 1; + + int bytecodeSize = bytecodeCodeSize(info) / bonus; + int complexity = compilationComplexity(info) / bonus; + int compiledCodeSize = compiledCodeSize(info) / bonus; double relevance = info.invoke().inliningRelevance(); /* @@ -213,7 +230,6 @@ int invokeUsages = countInvokeUsages(info); int moreSpecificArguments = countMoreSpecificArgumentInfo(info); int level = info.level(); - boolean preferredInvoke = hints != null && hints.contains(info.invoke()); // TODO (chaeubl): compute metric that is used to check if this method should be inlined
--- a/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/GraalOptions.java Mon Mar 25 11:09:40 2013 +0100 +++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/GraalOptions.java Thu Mar 07 13:47:09 2013 +0100 @@ -49,6 +49,7 @@ public static boolean LimitInlinedRelevance = true; public static float BoostInliningForEscapeAnalysis = 2f; public static float RelevanceCapForInlining = 1f; + public static boolean IterativeInlining = true; public static int TrivialBytecodeSize = 10; public static int NormalBytecodeSize = 150; @@ -67,6 +68,7 @@ public static int EscapeAnalysisIterations = 2; public static String EscapeAnalyzeOnly = null; public static int MaximumEscapeAnalysisArrayLength = 32; + public static boolean PEAReadCache = true; public static double TailDuplicationProbability = 0.5; public static int TailDuplicationTrivialSize = 1;
--- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/BlockState.java Mon Mar 25 11:09:40 2013 +0100 +++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/BlockState.java Thu Mar 07 13:47:09 2013 +0100 @@ -30,6 +30,7 @@ import com.oracle.graal.api.meta.*; import com.oracle.graal.graph.*; import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.extended.*; import com.oracle.graal.nodes.spi.Virtualizable.EscapeState; import com.oracle.graal.nodes.virtual.*; import com.oracle.graal.virtual.nodes.*; @@ -40,6 +41,32 @@ private final HashMap<ValueNode, VirtualObjectNode> objectAliases = new HashMap<>(); private final HashMap<ValueNode, ValueNode> scalarAliases = new HashMap<>(); + private static class ReadCacheEntry { + + public final Object identity; + public final ValueNode object; + + public ReadCacheEntry(Object identity, ValueNode object) { + this.identity = identity; + this.object = object; + } + + @Override + public int hashCode() { + int result = 31 + ((identity == null) ? 0 : identity.hashCode()); + return 31 * result + ((object == null) ? 0 : object.hashCode()); + } + + @Override + public boolean equals(Object obj) { + ReadCacheEntry other = (ReadCacheEntry) obj; + return identity == other.identity && object == other.object; + } + + } + + private final HashMap<ReadCacheEntry, ValueNode> readCache = new HashMap<>(); + public BlockState() { } @@ -55,6 +82,28 @@ } } + public void addReadCache(ValueNode object, Object identity, ValueNode value) { + readCache.put(new ReadCacheEntry(identity, object), value); + } + + public ValueNode getReadCache(ValueNode object, Object identity) { + return readCache.get(new ReadCacheEntry(identity, object)); + } + + public void killReadCache(Object identity) { + if (identity == LocationNode.ANY_LOCATION) { + readCache.clear(); + } else { + Iterator<Map.Entry<ReadCacheEntry, ValueNode>> iter = readCache.entrySet().iterator(); + while (iter.hasNext()) { + Map.Entry<ReadCacheEntry, ValueNode> entry = iter.next(); + if (entry.getKey().identity == identity) { + iter.remove(); + } + } + } + } + public ObjectState getObjectState(VirtualObjectNode object) { assert objectStates.containsKey(object); return objectStates.get(object); @@ -175,7 +224,7 @@ return objectStates.toString(); } - public static BlockState meetAliases(List<BlockState> states) { + public static BlockState meetAliasesAndCache(List<BlockState> states) { BlockState newState = new BlockState(); newState.objectAliases.putAll(states.get(0).objectAliases); @@ -201,6 +250,22 @@ } } } + + for (Map.Entry<ReadCacheEntry, ValueNode> entry : states.get(0).readCache.entrySet()) { + ReadCacheEntry key = entry.getKey(); + ValueNode value = entry.getValue(); + for (int i = 1; i < states.size(); i++) { + ValueNode otherValue = states.get(i).readCache.get(key); + if (otherValue == null || otherValue != value) { + value = null; + break; + } + } + if (value != null) { + newState.readCache.put(key, value); + } + } + return newState; } }
--- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/EffectList.java Mon Mar 25 11:09:40 2013 +0100 +++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/EffectList.java Thu Mar 07 13:47:09 2013 +0100 @@ -193,7 +193,7 @@ for (int i2 = 0; i2 < levelAt(i); i2++) { str.append(" "); } - str.append(effect).toString(); + str.append(effect).append('\n'); } } return str.toString();
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/IterativeInliningPhase.java Thu Mar 07 13:47:09 2013 +0100 @@ -0,0 +1,127 @@ +/* + * Copyright (c) 2011, 2012, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.virtual.phases.ea; + +import java.util.*; +import java.util.concurrent.*; + +import com.oracle.graal.api.code.*; +import com.oracle.graal.debug.*; +import com.oracle.graal.graph.*; +import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.spi.*; +import com.oracle.graal.phases.*; +import com.oracle.graal.phases.common.*; +import com.oracle.graal.phases.common.CanonicalizerPhase.CustomCanonicalizer; +import com.oracle.graal.phases.graph.*; +import com.oracle.graal.phases.schedule.*; +import com.oracle.graal.virtual.phases.ea.EffectList.Effect; + +public class IterativeInliningPhase extends Phase { + + private final PhasePlan plan; + + private final GraalCodeCacheProvider runtime; + private final Assumptions assumptions; + private final GraphCache cache; + private final OptimisticOptimizations optimisticOpts; + private CustomCanonicalizer customCanonicalizer; + + public IterativeInliningPhase(GraalCodeCacheProvider runtime, Assumptions assumptions, GraphCache cache, PhasePlan plan, OptimisticOptimizations optimisticOpts) { + this.runtime = runtime; + this.assumptions = assumptions; + this.cache = cache; + this.plan = plan; + this.optimisticOpts = optimisticOpts; + } + + public void setCustomCanonicalizer(CustomCanonicalizer customCanonicalizer) { + this.customCanonicalizer = customCanonicalizer; + } + + public static final void trace(String format, Object... obj) { + if (GraalOptions.TraceEscapeAnalysis) { + Debug.log(format, obj); + } + } + + public static final void error(String format, Object... obj) { + System.out.print(String.format(format, obj)); + } + + @Override + protected void run(final StructuredGraph graph) { + runIterations(graph, true); + runIterations(graph, false); + } + + private void runIterations(final StructuredGraph graph, final boolean simple) { + Boolean continueIteration = true; + for (int iteration = 0; iteration < GraalOptions.EscapeAnalysisIterations && continueIteration; iteration++) { + continueIteration = Debug.scope("iteration " + iteration, new Callable<Boolean>() { + + @Override + public Boolean call() { + SchedulePhase schedule = new SchedulePhase(); + schedule.apply(graph, false); + PartialEscapeClosure closure = new PartialEscapeClosure(graph.createNodeBitMap(), schedule, runtime, assumptions); + ReentrantBlockIterator.apply(closure, schedule.getCFG().getStartBlock(), new BlockState(), null); + + if (closure.getNewVirtualObjectCount() != 0) { + // apply the effects collected during the escape analysis iteration + ArrayList<Node> obsoleteNodes = new ArrayList<>(); + for (Effect effect : closure.getEffects()) { + effect.apply(graph, obsoleteNodes); + } + trace("%s\n", closure.getEffects()); + + Debug.dump(graph, "after PartialEscapeAnalysis"); + assert PartialEscapeAnalysisPhase.noObsoleteNodes(graph, obsoleteNodes); + + new DeadCodeEliminationPhase().apply(graph); + if (GraalOptions.OptCanonicalizer) { + new CanonicalizerPhase(runtime, assumptions, null, customCanonicalizer).apply(graph); + } + } + + InliningPhase inlining = new InliningPhase(runtime, closure.getHints(), assumptions, cache, plan, optimisticOpts); + if (simple) { + inlining.setMaxMethodsPerInlining(1); + } + inlining.apply(graph); + new DeadCodeEliminationPhase().apply(graph); + + if (GraalOptions.ConditionalElimination && GraalOptions.OptCanonicalizer) { + new CanonicalizerPhase(runtime, assumptions).apply(graph); + new IterativeConditionalEliminationPhase(runtime, assumptions).apply(graph); + } + + if (!simple && closure.getNewVirtualObjectCount() == 0 && inlining.getInliningCount() == 0) { + return false; + } + return true; + } + }); + } + } +}
--- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PartialEscapeAnalysisPhase.java Mon Mar 25 11:09:40 2013 +0100 +++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PartialEscapeAnalysisPhase.java Thu Mar 07 13:47:09 2013 +0100 @@ -128,7 +128,7 @@ return true; } - private static boolean noObsoleteNodes(StructuredGraph graph, ArrayList<Node> obsoleteNodes) { + static boolean noObsoleteNodes(StructuredGraph graph, ArrayList<Node> obsoleteNodes) { // helper code that determines the paths that keep obsolete nodes alive: NodeFlood flood = graph.createNodeFlood(); @@ -153,7 +153,7 @@ for (Node node : obsoleteNodes) { if (node instanceof FixedNode) { - assert !flood.isMarked(node); + assert !flood.isMarked(node) : node; } }
--- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PartialEscapeClosure.java Mon Mar 25 11:09:40 2013 +0100 +++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PartialEscapeClosure.java Thu Mar 07 13:47:09 2013 +0100 @@ -34,9 +34,12 @@ import com.oracle.graal.nodes.PhiNode.PhiType; import com.oracle.graal.nodes.VirtualState.NodeClosure; import com.oracle.graal.nodes.cfg.*; +import com.oracle.graal.nodes.extended.*; +import com.oracle.graal.nodes.java.*; import com.oracle.graal.nodes.spi.*; -import com.oracle.graal.nodes.spi.Virtualizable.EscapeState; +import com.oracle.graal.nodes.spi.Virtualizable.*; import com.oracle.graal.nodes.virtual.*; +import com.oracle.graal.phases.*; import com.oracle.graal.phases.graph.*; import com.oracle.graal.phases.graph.ReentrantBlockIterator.BlockIteratorClosure; import com.oracle.graal.phases.graph.ReentrantBlockIterator.LoopInfo; @@ -53,6 +56,11 @@ public static final DebugMetric METRIC_MATERIALIZATIONS_LOOP_END = Debug.metric("MaterializationsLoopEnd"); public static final DebugMetric METRIC_ALLOCATION_REMOVED = Debug.metric("AllocationsRemoved"); + public static final DebugMetric METRIC_STOREFIELD_RECORDED = Debug.metric("StoreFieldRecorded"); + public static final DebugMetric METRIC_LOADFIELD_ELIMINATED = Debug.metric("LoadFieldEliminated"); + public static final DebugMetric METRIC_LOADFIELD_NOT_ELIMINATED = Debug.metric("LoadFieldNotEliminated"); + public static final DebugMetric METRIC_MEMORYCHECKOINT = Debug.metric("MemoryCheckpoint"); + private final NodeBitMap usages; private final SchedulePhase schedule; @@ -60,6 +68,8 @@ private final VirtualizerToolImpl tool; + private final List<Invoke> hints = new ArrayList<>(); + public PartialEscapeClosure(NodeBitMap usages, SchedulePhase schedule, MetaAccessProvider metaAccess, Assumptions assumptions) { this.usages = usages; this.schedule = schedule; @@ -74,6 +84,10 @@ return tool.getNewVirtualObjectCount(); } + public Collection<Invoke> getHints() { + return hints; + } + @Override protected void processBlock(Block block, BlockState state) { trace("\nBlock: %s (", block); @@ -81,27 +95,59 @@ FixedWithNextNode lastFixedNode = null; for (Node node : nodeList) { + boolean deleted; if (usages.isMarked(node) || node instanceof VirtualizableAllocation) { trace("[[%s]] ", node); - processNode((ValueNode) node, lastFixedNode == null ? null : lastFixedNode.next(), state); + deleted = processNode((ValueNode) node, lastFixedNode == null ? null : lastFixedNode.next(), state); } else { trace("%s ", node); + deleted = false; } - - if (node instanceof FixedWithNextNode && node.isAlive()) { + if (GraalOptions.PEAReadCache) { + if (!deleted) { + if (node instanceof StoreFieldNode) { + METRIC_STOREFIELD_RECORDED.increment(); + StoreFieldNode store = (StoreFieldNode) node; + ValueNode value = store.value(); + ObjectState obj = state.getObjectState(value); + if (obj != null) { + assert !obj.isVirtual(); + value = obj.getMaterializedValue(); + } + value = state.getScalarAlias(value); + state.addReadCache(store.object(), store.field(), value); + } else if (node instanceof LoadFieldNode) { + LoadFieldNode load = (LoadFieldNode) node; + ValueNode cachedValue = state.getReadCache(load.object(), load.field()); + if (cachedValue != null) { + METRIC_LOADFIELD_ELIMINATED.increment(); + effects.replaceAtUsages(load, cachedValue); + state.addScalarAlias(load, cachedValue); + } else { + METRIC_LOADFIELD_NOT_ELIMINATED.increment(); + state.addReadCache(load.object(), load.field(), load); + } + } else if (node instanceof MemoryCheckpoint) { + METRIC_MEMORYCHECKOINT.increment(); + MemoryCheckpoint checkpoint = (MemoryCheckpoint) node; + state.killReadCache(checkpoint.getLocationIdentity()); + } + } + } + if (node instanceof FixedWithNextNode) { lastFixedNode = (FixedWithNextNode) node; } } trace(")\n end state: %s\n", state); } - private void processNode(final ValueNode node, FixedNode insertBefore, final BlockState state) { + private boolean processNode(final ValueNode node, FixedNode insertBefore, final BlockState state) { tool.reset(state, node); if (node instanceof Virtualizable) { ((Virtualizable) node).virtualize(tool); } if (tool.isDeleted()) { - return; + return true; } if (node instanceof StateSplit) { StateSplit split = (StateSplit) node; @@ -178,15 +224,20 @@ } } if (tool.isCustomAction()) { - return; + return false; } for (ValueNode input : node.inputs().filter(ValueNode.class)) { ObjectState obj = state.getObjectState(input); if (obj != null) { + if (obj.isVirtual() && node instanceof MethodCallTargetNode) { + Invoke invoke = ((MethodCallTargetNode) node).invoke(); + hints.add(invoke); + } trace("replacing input %s at %s: %s", input, node, obj); replaceWithMaterialized(input, node, insertBefore, state, obj, METRIC_MATERIALIZATIONS_UNHANDLED); } } + return false; } private void ensureMaterialized(BlockState state, ObjectState obj, FixedNode materializeBefore, DebugMetric metric) { @@ -207,8 +258,7 @@ @Override protected BlockState merge(MergeNode merge, List<BlockState> states) { - - BlockState newState = BlockState.meetAliases(states); + BlockState newState = BlockState.meetAliasesAndCache(states); // Iterative processing: // Merging the materialized/virtual state of virtual objects can lead to new