Mercurial > hg > graal-compiler
changeset 7684:bbf97d6688d3
cleanup for the inlining policies
added devirtualization of invokes
line wrap: on
line diff
--- a/graal/com.oracle.graal.api.meta/src/com/oracle/graal/api/meta/DeoptimizationReason.java Wed Jan 16 10:19:09 2013 +0100 +++ b/graal/com.oracle.graal.api.meta/src/com/oracle/graal/api/meta/DeoptimizationReason.java Fri Feb 01 16:57:40 2013 +0100 @@ -38,5 +38,5 @@ Unresolved, JavaSubroutineMismatch, ArithmeticException, - RuntimeConstraint, + RuntimeConstraint }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/IfNode.java Wed Jan 16 10:19:09 2013 +0100 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/IfNode.java Fri Feb 01 16:57:40 2013 +0100 @@ -25,6 +25,7 @@ import java.util.*; import com.oracle.graal.api.meta.*; +import com.oracle.graal.debug.*; import com.oracle.graal.graph.*; import com.oracle.graal.graph.iterators.*; import com.oracle.graal.nodes.PhiNode.PhiType; @@ -324,6 +325,7 @@ } } assert !ends.hasNext(); + assert falseEnds.size() + trueEnds.size() == xs.length; connectEnds(falseEnds, phiValues, oldFalseSuccessor, merge, tool); connectEnds(trueEnds, phiValues, oldTrueSuccessor, merge, tool); @@ -348,6 +350,9 @@ * @param phiValues the values of the phi at the merge, keyed by the merge ends */ private void connectEnds(List<EndNode> ends, Map<EndNode, ValueNode> phiValues, BeginNode successor, MergeNode oldMerge, SimplifierTool tool) { + // TEMP: + Debug.dump(this.graph(), "Before connectEnds"); + if (ends.isEmpty()) { GraphUtil.killCFG(successor); } else { @@ -381,6 +386,9 @@ } tool.addToWorkList(successor); } + + // TEMP: + Debug.dump(this.graph(), "After connectEnds"); } /**
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/java/MethodCallTargetNode.java Wed Jan 16 10:19:09 2013 +0100 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/java/MethodCallTargetNode.java Fri Feb 01 16:57:40 2013 +0100 @@ -141,6 +141,10 @@ } } + public JavaType returnType() { + return returnType; + } + @Override public String targetName() { if (targetMethod() == null) {
--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/CanonicalizerPhase.java Wed Jan 16 10:19:09 2013 +0100 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/CanonicalizerPhase.java Fri Feb 01 16:57:40 2013 +0100 @@ -119,6 +119,7 @@ for (Node n : workList) { processNode(n, graph); + Debug.dump(graph, "After processing %s", n); } graph.stopTrackingInputChange();
--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/ComputeProbabilityPhase.java Wed Jan 16 10:19:09 2013 +0100 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/ComputeProbabilityPhase.java Fri Feb 01 16:57:40 2013 +0100 @@ -55,63 +55,9 @@ computeLoopFactors(); Debug.dump(graph, "After computeLoopFactors"); new PropagateLoopFrequency(graph.start()).apply(); - - if (GraalOptions.LoopFrequencyPropagationPolicy < 0) { - ControlFlowGraph cfg = ControlFlowGraph.compute(graph, true, true, false, false); - BitSet visitedBlocks = new BitSet(cfg.getBlocks().length); - for (Loop loop : cfg.getLoops()) { - if (loop.parent == null) { - correctLoopFrequencies(loop, 1, visitedBlocks); - } - } - } - new ComputeInliningRelevanceIterator(graph).apply(); } - private void correctLoopFrequencies(Loop loop, double parentFrequency, BitSet visitedBlocks) { - LoopBeginNode loopBegin = ((LoopBeginNode) loop.header.getBeginNode()); - double frequency = parentFrequency * loopBegin.loopFrequency(); - if (frequency < 1) { - frequency = 1; - } - for (Loop child : loop.children) { - correctLoopFrequencies(child, frequency, visitedBlocks); - } - - double factor = getCorrectionFactor(loopBegin.probability(), frequency); - for (Block block : loop.blocks) { - int blockId = block.getId(); - if (!visitedBlocks.get(blockId)) { - visitedBlocks.set(blockId); - - FixedNode node = block.getBeginNode(); - while (node != block.getEndNode()) { - node.setProbability(node.probability() * factor); - node = ((FixedWithNextNode) node).next(); - } - node.setProbability(node.probability() * factor); - } - } - } - - private static double getCorrectionFactor(double probability, double frequency) { - switch (GraalOptions.LoopFrequencyPropagationPolicy) { - case -1: - return 1 / frequency; - case -2: - return (1 / frequency) * (Math.log(Math.E + frequency) - 1); - case -3: - double originalProbability = probability / frequency; - assert isRelativeProbability(originalProbability); - return (1 / frequency) * Math.max(1, Math.pow(originalProbability, 1.5) * Math.log10(frequency)); - case -4: - return 1 / probability; - default: - throw GraalInternalError.shouldNotReachHere(); - } - } - private void computeLoopFactors() { for (LoopInfo info : loopInfos) { double frequency = info.loopFrequency(); @@ -321,98 +267,110 @@ } private class PropagateLoopFrequency extends PostOrderNodeIterator<LoopCount> { - - private final FrequencyPropagationPolicy policy; - public PropagateLoopFrequency(FixedNode start) { super(start, new LoopCount(1d)); - this.policy = createFrequencyPropagationPolicy(); } @Override protected void node(FixedNode node) { - node.setProbability(policy.compute(node.probability(), state.count)); + node.setProbability(node.probability() * state.count); } } - private static FrequencyPropagationPolicy createFrequencyPropagationPolicy() { - switch (GraalOptions.LoopFrequencyPropagationPolicy) { - case -4: - case -3: - case -2: - case -1: - case 0: - return new FullFrequencyPropagation(); - case 1: - return new NoFrequencyPropagation(); - default: - throw GraalInternalError.shouldNotReachHere(); - } - } - - private interface FrequencyPropagationPolicy { - - double compute(double probability, double frequency); - } - - private static class FullFrequencyPropagation implements FrequencyPropagationPolicy { - - @Override - public double compute(double probability, double frequency) { - return probability * frequency; - } - } - - private static class NoFrequencyPropagation implements FrequencyPropagationPolicy { - - @Override - public double compute(double probability, double frequency) { - return probability; - } - } - private static class ComputeInliningRelevanceIterator extends ScopedPostOrderNodeIterator { - private final HashMap<FixedNode, Double> lowestPathProbabilities; + private final HashMap<FixedNode, Scope> scopes; private double currentProbability; + private double parentRelevance; public ComputeInliningRelevanceIterator(StructuredGraph graph) { super(graph); - this.lowestPathProbabilities = computeLowestPathProbabilities(graph); + this.scopes = computeLowestPathProbabilities(computeScopeInformation(graph)); } @Override protected void initializeScope() { - currentProbability = lowestPathProbabilities.get(currentScope); + Scope scope = scopes.get(currentScopeStart); + parentRelevance = getParentScopeRelevance(scope); + currentProbability = scope.minPathProbability; + } + + private static double getParentScopeRelevance(Scope scope) { + if (scope.start instanceof LoopBeginNode) { + assert scope.parent != null; + double parentProbability = 0; + for (EndNode end: ((LoopBeginNode) scope.start).forwardEnds()) { + parentProbability += end.probability(); + } + return parentProbability / scope.parent.minPathProbability; + } else { + assert scope.parent == null; + return 1.0; + } } @Override protected void invoke(Invoke invoke) { assert !Double.isNaN(invoke.probability()); - invoke.setInliningRelevance(invoke.probability() / currentProbability); + invoke.setInliningRelevance((invoke.probability() / currentProbability) * Math.min(1.0, parentRelevance)); + assert !Double.isNaN(invoke.inliningRelevance()); } - private HashMap<FixedNode, Double> computeLowestPathProbabilities(StructuredGraph graph) { - HashMap<FixedNode, Double> result = new HashMap<>(); - Deque<FixedNode> scopes = getScopes(graph); + private static Scope[] computeScopeInformation(StructuredGraph graph) { + ControlFlowGraph cfg = ControlFlowGraph.compute(graph, true, true, false, false); + + Loop[] loops = cfg.getLoops(); + HashMap<Loop, Scope> processedScopes = new HashMap<>(); + Scope[] scopes = new Scope[loops.length + 1]; + Scope methodScope = new Scope(graph.start(), null); + processedScopes.put(null, methodScope); + + scopes[0] = methodScope; + for (int i = 0; i < loops.length; i++) { + scopes[i + 1] = createScope(loops[i], processedScopes); + } + + return scopes; + } - while (!scopes.isEmpty()) { - FixedNode scopeBegin = scopes.pop(); - double probability = computeLowestPathProbability(scopeBegin); - result.put(scopeBegin, probability); + private static Scope createScope(Loop loop, HashMap<Loop, Scope> processedLoops) { + Scope parent = processedLoops.get(loop.parent); + if (parent == null) { + parent = createScope(loop, processedLoops); + } + Scope result = new Scope(loop.loopBegin(), parent); + processedLoops.put(loop, result); + return result; + } + + private static HashMap<FixedNode, Scope> computeLowestPathProbabilities(Scope[] scopes) { + HashMap<FixedNode, Scope> result = new HashMap<>(); + + for (Scope scope: scopes) { + double lowestPathProbability = computeLowestPathProbability(scope); + scope.minPathProbability = Math.max(EPSILON, lowestPathProbability); + result.put(scope.start, scope); } return result; } - private static double computeLowestPathProbability(FixedNode scopeStart) { + private static double computeLowestPathProbability(Scope scope) { + FixedNode scopeStart = scope.start; + Node current = scopeStart; double minPathProbability = scopeStart.probability(); - Node current = scopeStart; + boolean isLoopScope = scopeStart instanceof LoopBeginNode; while (current != null) { - if (current instanceof ControlSplitNode) { - ControlSplitNode controlSplit = (ControlSplitNode) current; - current = getMaxProbabilitySux(controlSplit); + if (isLoopScope && current instanceof LoopExitNode && ((LoopBeginNode) scopeStart).loopExits().contains((LoopExitNode) current)) { + return minPathProbability; + } else if (current instanceof LoopBeginNode && current != scopeStart) { + current = getMaxProbabilityLoopExit((LoopBeginNode) current); + if (((FixedNode) current).probability() < minPathProbability) { + minPathProbability = ((FixedNode) current).probability(); + } + } else if (current instanceof ControlSplitNode) { + current = getMaxProbabilitySux((ControlSplitNode) current); if (((FixedNode) current).probability() < minPathProbability) { minPathProbability = ((FixedNode) current).probability(); } @@ -429,7 +387,7 @@ Node maxSux = null; double maxProbability = 0.0; - // TODO: process recursively if we have multiple successors with same probability + // TODO (chaeubl): process recursively if we have multiple successors with same probability for (Node sux: controlSplit.successors()) { double probability = controlSplit.probability((BeginNode) sux); if (probability > maxProbability) { @@ -440,5 +398,32 @@ return maxSux; } + + private static Node getMaxProbabilityLoopExit(LoopBeginNode loopBegin) { + Node maxSux = null; + double maxProbability = 0.0; + + // TODO (chaeubl): process recursively if we have multiple successors with same probability + for (LoopExitNode sux: loopBegin.loopExits()) { + double probability = sux.probability(); + if (probability > maxProbability) { + maxProbability = probability; + maxSux = sux; + } + } + + return maxSux; + } + } + + private static class Scope { + public final FixedNode start; + public final Scope parent; + public double minPathProbability; + + public Scope(FixedNode start, Scope parent) { + this.start = start; + this.parent = parent; + } } }
--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/InliningPhase.java Wed Jan 16 10:19:09 2013 +0100 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/InliningPhase.java Fri Feb 01 16:57:40 2013 +0100 @@ -32,9 +32,11 @@ import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.spi.*; import com.oracle.graal.phases.*; -import com.oracle.graal.phases.PhasePlan.*; +import com.oracle.graal.phases.PhasePlan.PhasePosition; import com.oracle.graal.phases.common.CanonicalizerPhase.CustomCanonicalizer; -import com.oracle.graal.phases.common.InliningUtil.*; +import com.oracle.graal.phases.common.InliningUtil.InlineInfo; +import com.oracle.graal.phases.common.InliningUtil.InliningCallback; +import com.oracle.graal.phases.common.InliningUtil.InliningPolicy; public class InliningPhase extends Phase implements InliningCallback { /* @@ -50,6 +52,7 @@ private final Assumptions assumptions; private final GraphCache cache; private final InliningPolicy inliningPolicy; + private final OptimisticOptimizations optimisticOpts; private CustomCanonicalizer customCanonicalizer; // Metrics @@ -59,20 +62,21 @@ private static final DebugMetric metricInliningRuns = Debug.metric("Runs"); public InliningPhase(TargetDescription target, GraalCodeCacheProvider runtime, Collection<Invoke> hints, Assumptions assumptions, GraphCache cache, PhasePlan plan, OptimisticOptimizations optimisticOpts) { - this(target, runtime, assumptions, cache, plan, createInliningPolicy(assumptions, optimisticOpts, hints)); + this(target, runtime, assumptions, cache, plan, createInliningPolicy(runtime, assumptions, optimisticOpts, hints), optimisticOpts); } public void setCustomCanonicalizer(CustomCanonicalizer customCanonicalizer) { this.customCanonicalizer = customCanonicalizer; } - public InliningPhase(TargetDescription target, GraalCodeCacheProvider runtime, Assumptions assumptions, GraphCache cache, PhasePlan plan, InliningPolicy inliningPolicy) { + public InliningPhase(TargetDescription target, GraalCodeCacheProvider runtime, Assumptions assumptions, GraphCache cache, PhasePlan plan, InliningPolicy inliningPolicy, OptimisticOptimizations optimisticOpts) { this.target = target; this.runtime = runtime; this.assumptions = assumptions; this.cache = cache; this.plan = plan; this.inliningPolicy = inliningPolicy; + this.optimisticOpts = optimisticOpts; } @Override @@ -93,12 +97,11 @@ candidate.inline(graph, runtime, this, assumptions); Debug.dump(graph, "after %s", candidate); Iterable<Node> newNodes = graph.getNewNodes(mark); + inliningPolicy.scanInvokes(newNodes); if (GraalOptions.OptCanonicalizer) { new CanonicalizerPhase(target, runtime, assumptions, invokeUsages, mark, customCanonicalizer).apply(graph); } metricInliningPerformed.increment(); - - inliningPolicy.scanInvokes(newNodes); } catch (BailoutException bailout) { // TODO determine if we should really bail out of the whole compilation. throw bailout; @@ -109,6 +112,8 @@ } catch (GraalInternalError e) { throw e.addContext(candidate.toString()); } + } else if (optimisticOpts.devirtualizeInvokes()) { + candidate.tryToDevirtualizeInvoke(graph, runtime, assumptions); } } } @@ -149,161 +154,187 @@ boolean isWorthInlining(InlineInfo info); } - private abstract static class AbstractInliningDecision implements InliningDecision { - protected static boolean decideSizeBasedInlining(InlineInfo info, double maxSize) { - assert !Double.isNaN(info.weight()) && !Double.isNaN(maxSize); - boolean success = info.weight() <= maxSize; - if (GraalOptions.Debug) { - String formatterString = success ? "(size %f <= %f)" : "(too large %f > %f)"; - InliningUtil.logInliningDecision(info, success, formatterString, info.weight(), maxSize); - } - return success; - } + private static class GreedySizeBasedInliningDecision implements InliningDecision { + private final GraalCodeCacheProvider runtime; + private final Collection<Invoke> hints; - protected static boolean checkCompiledCodeSize(InlineInfo info) { - if (GraalOptions.SmallCompiledCodeSize >= 0 && info.compiledCodeSize() > GraalOptions.SmallCompiledCodeSize) { - InliningUtil.logNotInlinedMethod(info, "(CompiledCodeSize %d > %d)", info.compiledCodeSize(), GraalOptions.SmallCompiledCodeSize); - return false; - } - return true; + public GreedySizeBasedInliningDecision(GraalCodeCacheProvider runtime, Collection<Invoke> hints) { + this.runtime = runtime; + this.hints = hints; } - protected static double getRelevance(Invoke invoke) { - if (GraalOptions.UseRelevanceBasedInlining) { - return invoke.inliningRelevance(); - } else { - return invoke.probability(); - } - } - } - - private static class C1StaticSizeBasedInliningDecision extends AbstractInliningDecision { - @Override - public boolean isWorthInlining(InlineInfo info) { - double maxSize = Math.max(GraalOptions.MaximumTrivialSize, Math.pow(GraalOptions.NestedInliningSizeRatio, info.level()) * GraalOptions.MaximumInlineSize); - return decideSizeBasedInlining(info, maxSize); - } - } - - private static class MinimumCodeSizeBasedInliningDecision extends AbstractInliningDecision { - @Override - public boolean isWorthInlining(InlineInfo info) { - assert GraalOptions.ProbabilityAnalysis; - if (!checkCompiledCodeSize(info)) { - return false; - } - - double inlineWeight = Math.min(GraalOptions.RatioCapForInlining, getRelevance(info.invoke())); - double maxSize = Math.pow(GraalOptions.NestedInliningSizeRatio, info.level()) * GraalOptions.MaximumInlineSize * inlineWeight; - maxSize = Math.max(GraalOptions.MaximumTrivialSize, maxSize); - - return decideSizeBasedInlining(info, maxSize); - } - } - - private static class DynamicSizeBasedInliningDecision extends AbstractInliningDecision { - @Override - public boolean isWorthInlining(InlineInfo info) { - assert GraalOptions.ProbabilityAnalysis; - if (!checkCompiledCodeSize(info)) { - return false; - } - - double relevance = getRelevance(info.invoke()); - double inlineBoost = Math.min(GraalOptions.RatioCapForInlining, relevance) + Math.log10(Math.max(1, relevance - GraalOptions.RatioCapForInlining + 1)); - double maxSize = Math.pow(GraalOptions.NestedInliningSizeRatio, info.level()) * GraalOptions.MaximumInlineSize; - maxSize = maxSize + maxSize * inlineBoost; - maxSize = Math.min(GraalOptions.MaximumGreedyInlineSize, Math.max(GraalOptions.MaximumTrivialSize, maxSize)); - - return decideSizeBasedInlining(info, maxSize); - } - } - - private static class GreedySizeBasedInliningDecision extends AbstractInliningDecision { @Override public boolean isWorthInlining(InlineInfo info) { +// assert GraalOptions.ProbabilityAnalysis; +// if (compiledCodeSize(info) > GraalOptions.SmallCompiledCodeSize) { +// return false; +// } +// +// double maxSize = GraalOptions.NormalComplexity; +// Signature signature = info.invoke().methodCallTarget().targetMethod().getSignature(); +// int transferredValues = signature.getParameterCount(!Modifier.isStatic(info.invoke().methodCallTarget().targetMethod().getModifiers())); +// if (signature.getReturnKind() != Kind.Void) { +// transferredValues++; +// } +// maxSize += transferredValues * 10; +// +// maxSize = Math.min(GraalOptions.RelevanceCapForInlining, info.invoke().inliningRelevance()) * maxSize; +// maxSize = Math.max(maxSize, GraalOptions.TrivialComplexity); +// +// return compilationComplexity(info) < maxSize; + assert GraalOptions.ProbabilityAnalysis; - if (!checkCompiledCodeSize(info)) { - return false; + // TODO (chaeubl): invoked methods that are on important paths but not yet compiled -> will be compiled anyways and it is likely that we are the only caller... + // might be useful to inline those methods but increases bootstrap time (maybe those methods are also getting queued in the compilation queue concurrently) + + if (GraalOptions.AlwaysInlineIntrinsics && onlyIntrinsics(info)) { + return InliningUtil.logInlinedMethod(info, "intrinsic"); } - double maxSize = GraalOptions.MaximumGreedyInlineSize; - if (GraalOptions.InliningBonusPerTransferredValue != 0) { - Signature signature = info.invoke().methodCallTarget().targetMethod().getSignature(); - int transferredValues = signature.getParameterCount(!Modifier.isStatic(info.invoke().methodCallTarget().targetMethod().getModifiers())); - if (signature.getReturnKind() != Kind.Void) { - transferredValues++; + int bytecodeSize = bytecodeCodeSize(info); + int complexity = compilationComplexity(info); + int compiledCodeSize = compiledCodeSize(info); + double relevance = info.invoke().inliningRelevance(); + + // as long as the compiled code size is small enough (or the method was not yet compiled), we can do a pretty general inlining that suits most situations + if (compiledCodeSize < GraalOptions.SmallCompiledCodeSize) { + if (isTrivialInlining(bytecodeSize, complexity, compiledCodeSize)) { + return InliningUtil.logInlinedMethod(info, "trivial (bytecodes=%d, complexity=%d, codeSize=%d)", bytecodeSize, complexity, compiledCodeSize); } - maxSize += transferredValues * GraalOptions.InliningBonusPerTransferredValue; + + if (canInlineRelevanceBased(relevance, bytecodeSize, complexity, compiledCodeSize)) { + return InliningUtil.logInlinedMethod(info, "relevance-based (relevance=%f, bytecodes=%d, complexity=%d, codeSize=%d)", relevance, bytecodeSize, complexity, compiledCodeSize); + } } - double inlineRatio = Math.min(GraalOptions.RatioCapForInlining, getRelevance(info.invoke())); - maxSize = Math.pow(GraalOptions.NestedInliningSizeRatio, info.level()) * maxSize * inlineRatio; - maxSize = Math.max(maxSize, GraalOptions.MaximumTrivialSize); + // the normal inlining did not fit this invoke, so check if we have any reason why we should still do the inlining + double probability = info.invoke().probability(); + int transferredValues = numberOfTransferredValues(info); + int invokeUsages = countInvokeUsages(info); + int moreSpecificArguments = countMoreSpecificArgumentInfo(info); + int level = info.level(); + boolean preferredInvoke = hints != null && hints.contains(info.invoke()); - return decideSizeBasedInlining(info, maxSize); + // TODO (chaeubl): compute metric that is used to check if this method should be inlined anyways. also use the relevance somehow... +// double metric = (moreSpecificArguments * 5 + transferredValues + invokeUsages) * (preferredInvoke ? 1 : GraalOptions.BoostInliningForEscapeAnalysis); +// if (metric > 50) { +// // TEMP: +// TTY.println("Inlined special method (relevance=%f, bytecodes=%d, complexity=%d, codeSize=%d, probability=%f, transferredValues=%d, invokeUsages=%d, moreSpecificArguments=%d, level=%d, preferred=%b)", +// relevance, bytecodeSize, complexity, compiledCodeSize, probability, transferredValues, invokeUsages, moreSpecificArguments, level, preferredInvoke); +// return InliningUtil.logInlinedMethod(info, "(relevance=%f, bytecodes=%d, complexity=%d, codeSize=%d, probability=%f, transferredValues=%d, invokeUsages=%d, moreSpecificArguments=%d, level=%d, preferred=%b)", +// relevance, bytecodeSize, complexity, compiledCodeSize, probability, transferredValues, invokeUsages, moreSpecificArguments, level, preferredInvoke); +// } + + + return InliningUtil.logNotInlinedMethod(info, "(relevance=%f, bytecodes=%d, complexity=%d, codeSize=%d, probability=%f, transferredValues=%d, invokeUsages=%d, moreSpecificArguments=%d, level=%d, preferred=%b)", + relevance, bytecodeSize, complexity, compiledCodeSize, probability, transferredValues, invokeUsages, moreSpecificArguments, level, preferredInvoke); } - } + + private static boolean isTrivialInlining(int bytecodeSize, int complexity, int compiledCodeSize) { + return bytecodeSize < GraalOptions.TrivialBytecodeSize || + complexity < GraalOptions.TrivialComplexity || + compiledCodeSize > 0 && compiledCodeSize < GraalOptions.TrivialCompiledCodeSize; + } - private static class GreedyMachineCodeInliningDecision extends AbstractInliningDecision { - @Override - public boolean isWorthInlining(InlineInfo info) { - assert GraalOptions.ProbabilityAnalysis; + private static boolean canInlineRelevanceBased(double relevance, int bytecodeSize, int complexity, int compiledCodeSize) { + return bytecodeSize < computeMaximumSize(relevance, GraalOptions.NormalBytecodeSize) || + complexity < computeMaximumSize(relevance, GraalOptions.NormalComplexity) || + compiledCodeSize > 0 && compiledCodeSize < computeMaximumSize(relevance, GraalOptions.NormalCompiledCodeSize); + } + + private static double computeMaximumSize(double relevance, int configuredMaximum) { + double inlineRatio = Math.min(GraalOptions.RelevanceCapForInlining, relevance); + return configuredMaximum * inlineRatio; + } - double maxSize = GraalOptions.MaximumGreedyInlineSize; - double inlineRatio = Math.min(GraalOptions.RatioCapForInlining, getRelevance(info.invoke())); - maxSize = Math.pow(GraalOptions.NestedInliningSizeRatio, info.level()) * maxSize * inlineRatio; - maxSize = Math.max(maxSize, GraalOptions.MaximumTrivialSize); + private static int numberOfTransferredValues(InlineInfo info) { + Signature signature = info.invoke().methodCallTarget().targetMethod().getSignature(); + int transferredValues = signature.getParameterCount(!Modifier.isStatic(info.invoke().methodCallTarget().targetMethod().getModifiers())); + if (signature.getReturnKind() != Kind.Void) { + transferredValues++; + } + return transferredValues; + } - return decideSizeBasedInlining(info, maxSize); + private static int countInvokeUsages(InlineInfo info) { + // inlining calls with lots of usages simplifies the caller + int usages = 0; + for (Node n: info.invoke().node().usages()) { + if (!(n instanceof FrameState)) { + usages++; + } + } + return usages; } - } + + private int countMoreSpecificArgumentInfo(InlineInfo info) { + // inlining invokes where the caller has very specific information about the passed argument simplifies the callee + int moreSpecificArgumentInfo = 0; + boolean isStatic = info.invoke().methodCallTarget().isStatic(); + int signatureOffset = isStatic ? 0 : 1; + NodeInputList arguments = info.invoke().methodCallTarget().arguments(); + ResolvedJavaMethod targetMethod = info.invoke().methodCallTarget().targetMethod(); + ResolvedJavaType methodHolderClass = targetMethod.getDeclaringClass(); + Signature signature = targetMethod.getSignature(); - private static class BytecodeSizeBasedWeightComputationPolicy implements WeightComputationPolicy { - @Override - public double computeWeight(ResolvedJavaMethod caller, ResolvedJavaMethod method, Invoke invoke, boolean preferredInvoke) { - if (GraalOptions.AlwaysInlineIntrinsics && InliningUtil.canIntrinsify(method)) { - return 0; + for (int i = 0; i < arguments.size(); i++) { + Node n = arguments.get(i); + if (n instanceof ConstantNode) { + moreSpecificArgumentInfo++; + } else if (n instanceof ValueNode && !((ValueNode) n).kind().isPrimitive()) { + ResolvedJavaType actualType = ((ValueNode) n).stamp().javaType(runtime); + JavaType declaredType; + if (i == 0 && !isStatic) { + declaredType = methodHolderClass; + } else { + declaredType = signature.getParameterType(i - signatureOffset, methodHolderClass); + } + + if (declaredType instanceof ResolvedJavaType && !actualType.equals(declaredType) && ((ResolvedJavaType) declaredType).isAssignableFrom(actualType)) { + moreSpecificArgumentInfo++; + } + } } - double codeSize = method.getCodeSize(); - if (preferredInvoke) { - codeSize = codeSize / GraalOptions.BoostInliningForEscapeAnalysis; - } - return codeSize; + return moreSpecificArgumentInfo; } - } - private static class ComplexityBasedWeightComputationPolicy implements WeightComputationPolicy { - @Override - public double computeWeight(ResolvedJavaMethod caller, ResolvedJavaMethod method, Invoke invoke, boolean preferredInvoke) { - if (GraalOptions.AlwaysInlineIntrinsics && InliningUtil.canIntrinsify(method)) { - return 0; + private static int bytecodeCodeSize(InlineInfo info) { + int result = 0; + for (int i = 0; i < info.numberOfMethods(); i++) { + result += info.methodAt(i).getCodeSize(); } + return result; + } - double complexity = method.getCompilationComplexity(); - if (preferredInvoke) { - complexity = complexity / GraalOptions.BoostInliningForEscapeAnalysis; + private static int compilationComplexity(InlineInfo info) { + int result = 0; + for (int i = 0; i < info.numberOfMethods(); i++) { + result += info.methodAt(i).getCompilationComplexity(); } - return complexity; + return result; } - } - private static class CompiledCodeSizeWeightComputationPolicy implements WeightComputationPolicy { - @Override - public double computeWeight(ResolvedJavaMethod caller, ResolvedJavaMethod method, Invoke invoke, boolean preferredInvoke) { - if (GraalOptions.AlwaysInlineIntrinsics && InliningUtil.canIntrinsify(method)) { - return 0; + private static int compiledCodeSize(InlineInfo info) { + int result = 0; + for (int i = 0; i < info.numberOfMethods(); i++) { + result += info.methodAt(i).getCompiledCodeSize(); } + return result; + } - int compiledCodeSize = method.getCompiledCodeSize(); - return compiledCodeSize > 0 ? compiledCodeSize : method.getCodeSize() * 10; + private static boolean onlyIntrinsics(InlineInfo info) { + for (int i = 0; i < info.numberOfMethods(); i++) { + if (!InliningUtil.canIntrinsify(info.methodAt(i))) { + return false; + } + } + return true; } } private static class CFInliningPolicy implements InliningPolicy { private final InliningDecision inliningDecision; - private final WeightComputationPolicy weightComputationPolicy; private final Collection<Invoke> hints; private final Assumptions assumptions; private final OptimisticOptimizations optimisticOpts; @@ -311,10 +342,9 @@ private NodeBitMap visitedFixedNodes; private FixedNode invokePredecessor; - public CFInliningPolicy(InliningDecision inliningPolicy, WeightComputationPolicy weightComputationPolicy, Collection<Invoke> hints, + public CFInliningPolicy(InliningDecision inliningPolicy, Collection<Invoke> hints, Assumptions assumptions, OptimisticOptimizations optimisticOpts) { this.inliningDecision = inliningPolicy; - this.weightComputationPolicy = weightComputationPolicy; this.hints = hints; this.assumptions = assumptions; this.optimisticOpts = optimisticOpts; @@ -333,7 +363,7 @@ public InlineInfo next() { Invoke invoke = sortedInvokes.pop(); - InlineInfo info = InliningUtil.getInlineInfo(invoke, assumptions, this, optimisticOpts); + InlineInfo info = InliningUtil.getInlineInfo(invoke, assumptions, optimisticOpts); if (info != null) { invokePredecessor = (FixedNode) info.invoke().predecessor(); assert invokePredecessor.isAlive(); @@ -354,169 +384,103 @@ } public void scanInvokes(Iterable<? extends Node> newNodes) { - scanGraphForInvokes(invokePredecessor); + assert invokePredecessor.isAlive(); + int invokes = scanGraphForInvokes(invokePredecessor); + assert invokes == countInvokes(newNodes); } - private void scanGraphForInvokes(FixedNode start) { + private int scanGraphForInvokes(FixedNode start) { ArrayList<Invoke> invokes = new InliningIterator(start, visitedFixedNodes).apply(); // insert the newly found invokes in their correct control-flow order for (int i = invokes.size() - 1; i >= 0; i--) { - sortedInvokes.addFirst(invokes.get(i)); - } - } - - public double inliningWeight(ResolvedJavaMethod caller, ResolvedJavaMethod method, Invoke invoke) { - boolean preferredInvoke = hints != null && hints.contains(invoke); - return weightComputationPolicy.computeWeight(caller, method, invoke, preferredInvoke); - } - } - - private static class PriorityInliningPolicy implements InliningPolicy { - private final InliningDecision inliningDecision; - private final WeightComputationPolicy weightComputationPolicy; - private final Collection<Invoke> hints; - private final Assumptions assumptions; - private final OptimisticOptimizations optimisticOpts; - private final PriorityQueue<InlineInfo> sortedCandidates; - - public PriorityInliningPolicy(InliningDecision inliningPolicy, WeightComputationPolicy weightComputationPolicy, Collection<Invoke> hints, - Assumptions assumptions, OptimisticOptimizations optimisticOpts) { - this.inliningDecision = inliningPolicy; - this.weightComputationPolicy = weightComputationPolicy; - this.hints = hints; - this.assumptions = assumptions; - this.optimisticOpts = optimisticOpts; - sortedCandidates = new PriorityQueue<>(); - } - - public boolean continueInlining(StructuredGraph graph) { - if (graph.getNodeCount() >= GraalOptions.MaximumDesiredSize) { - InliningUtil.logInliningDecision("inlining is cut off by MaximumDesiredSize"); - metricInliningStoppedByMaxDesiredSize.increment(); - return false; + Invoke invoke = invokes.get(i); + assert !sortedInvokes.contains(invoke); + sortedInvokes.addFirst(invoke); } - return !sortedCandidates.isEmpty(); + return invokes.size(); } - public InlineInfo next() { - // refresh cached info before using it (it might have been in the queue for a long time) - InlineInfo info = sortedCandidates.remove(); - return InliningUtil.getInlineInfo(info.invoke(), assumptions, this, optimisticOpts); - } - - @Override - public boolean isWorthInlining(InlineInfo info) { - return inliningDecision.isWorthInlining(info); - } - - @SuppressWarnings("unchecked") - public void initialize(StructuredGraph graph) { - if (hints == null) { - scanInvokes(graph.getNodes(InvokeNode.class)); - scanInvokes(graph.getNodes(InvokeWithExceptionNode.class)); - } else { - scanInvokes((Iterable<? extends Node>) (Iterable<?>) hints); - } - } - - public void scanInvokes(Iterable<? extends Node> nodes) { - for (Node node: nodes) { - if (node != null) { - if (node instanceof Invoke) { - Invoke invoke = (Invoke) node; - scanInvoke(invoke); - } - for (Node usage : node.usages().filterInterface(Invoke.class).snapshot()) { - scanInvoke((Invoke) usage); - } + private static int countInvokes(Iterable<? extends Node> nodes) { + int count = 0; + for (Node n: nodes) { + if (n instanceof Invoke) { + count++; } } - } - - private void scanInvoke(Invoke invoke) { - InlineInfo info = InliningUtil.getInlineInfo(invoke, assumptions, this, optimisticOpts); - if (info != null) { - sortedCandidates.add(info); - } - } - - @Override - public double inliningWeight(ResolvedJavaMethod caller, ResolvedJavaMethod method, Invoke invoke) { - boolean preferredInvoke = hints != null && hints.contains(invoke); - return weightComputationPolicy.computeWeight(caller, method, invoke, preferredInvoke); + return count; } } private static class InliningIterator { private final FixedNode start; - private final NodeBitMap processedNodes; - private final Deque<FixedNode> nodeQueue; private final NodeBitMap queuedNodes; public InliningIterator(FixedNode start, NodeBitMap visitedFixedNodes) { this.start = start; - this.processedNodes = visitedFixedNodes; - this.nodeQueue = new ArrayDeque<>(); - this.queuedNodes = visitedFixedNodes.copy(); - + this.queuedNodes = visitedFixedNodes; assert start.isAlive(); } public ArrayList<Invoke> apply() { ArrayList<Invoke> invokes = new ArrayList<>(); - FixedNode current = start; - do { + FixedNode current; + forcedQueue(start); + + while ((current = nextQueuedNode()) != null) { assert current.isAlive(); - processedNodes.mark(current); - if (current instanceof InvokeWithExceptionNode || current instanceof InvokeNode) { - invokes.add((Invoke) current); + if (current instanceof Invoke) { + if (current != start) { + invokes.add((Invoke) current); + } queueSuccessors(current); - current = nextQueuedNode(); } else if (current instanceof LoopBeginNode) { - current = ((LoopBeginNode) current).next(); - assert current != null; + queueSuccessors(current); } else if (current instanceof LoopEndNode) { - current = nextQueuedNode(); + // nothing todo } else if (current instanceof MergeNode) { - current = ((MergeNode) current).next(); - assert current != null; + queueSuccessors(current); } else if (current instanceof FixedWithNextNode) { queueSuccessors(current); - current = nextQueuedNode(); } else if (current instanceof EndNode) { queueMerge((EndNode) current); - current = nextQueuedNode(); } else if (current instanceof DeoptimizeNode) { - current = nextQueuedNode(); + // nothing todo } else if (current instanceof ReturnNode) { - current = nextQueuedNode(); + // nothing todo } else if (current instanceof UnwindNode) { - current = nextQueuedNode(); + // nothing todo } else if (current instanceof ControlSplitNode) { queueSuccessors(current); - current = nextQueuedNode(); } else { assert false : current; } - } while(current != null); + } return invokes; } private void queueSuccessors(FixedNode x) { for (Node node : x.successors()) { - if (node != null && !queuedNodes.isMarked(node)) { - queuedNodes.mark(node); - nodeQueue.addFirst((FixedNode) node); - } + queue(node); } } + private void queue(Node node) { + if (node != null && !queuedNodes.isMarked(node)) { + forcedQueue(node); + } + } + + private void forcedQueue(Node node) { + queuedNodes.mark(node); + nodeQueue.addFirst((FixedNode) node); + } + private FixedNode nextQueuedNode() { if (nodeQueue.isEmpty()) { return null; @@ -537,7 +501,7 @@ private boolean visitedAllEnds(MergeNode merge) { for (int i = 0; i < merge.forwardEndCount(); i++) { - if (!processedNodes.isMarked(merge.forwardEndAt(i))) { + if (!queuedNodes.isMarked(merge.forwardEndAt(i))) { return false; } } @@ -545,38 +509,8 @@ } } - private static InliningPolicy createInliningPolicy(Assumptions assumptions, OptimisticOptimizations optimisticOpts, Collection<Invoke> hints) { - switch(GraalOptions.InliningPolicy) { - case 0: return new CFInliningPolicy(createInliningDecision(), createWeightComputationPolicy(), hints, assumptions, optimisticOpts); - case 1: return new PriorityInliningPolicy(createInliningDecision(), createWeightComputationPolicy(), hints, assumptions, optimisticOpts); - default: - GraalInternalError.shouldNotReachHere(); - return null; - } - } - - private static InliningDecision createInliningDecision() { - switch(GraalOptions.InliningDecision) { - case 1: return new C1StaticSizeBasedInliningDecision(); - case 2: return new MinimumCodeSizeBasedInliningDecision(); - case 3: return new DynamicSizeBasedInliningDecision(); - case 4: return new GreedySizeBasedInliningDecision(); - case 5: return new GreedyMachineCodeInliningDecision(); - default: - GraalInternalError.shouldNotReachHere(); - return null; - } - } - - private static WeightComputationPolicy createWeightComputationPolicy() { - switch(GraalOptions.WeightComputationPolicy) { - case 0: throw new GraalInternalError("removed because of invokation counter changes"); - case 1: return new BytecodeSizeBasedWeightComputationPolicy(); - case 2: return new ComplexityBasedWeightComputationPolicy(); - case 3: return new CompiledCodeSizeWeightComputationPolicy(); - default: - GraalInternalError.shouldNotReachHere(); - return null; - } + private static InliningPolicy createInliningPolicy(GraalCodeCacheProvider runtime, Assumptions assumptions, OptimisticOptimizations optimisticOpts, Collection<Invoke> hints) { + InliningDecision inliningDecision = new GreedySizeBasedInliningDecision(runtime, hints); + return new CFInliningPolicy(inliningDecision, hints, assumptions, optimisticOpts); } }
--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/InliningUtil.java Wed Jan 16 10:19:09 2013 +0100 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/InliningUtil.java Fri Feb 01 16:57:40 2013 +0100 @@ -56,16 +56,12 @@ boolean continueInlining(StructuredGraph graph); InlineInfo next(); void scanInvokes(Iterable<? extends Node> newNodes); - double inliningWeight(ResolvedJavaMethod caller, ResolvedJavaMethod method, Invoke invoke); boolean isWorthInlining(InlineInfo info); } - public interface WeightComputationPolicy { - double computeWeight(ResolvedJavaMethod caller, ResolvedJavaMethod method, Invoke invoke, boolean preferredInvoke); - } - - public static void logNotInlinedMethod(InlineInfo info, String msg, Object... args) { + public static boolean logNotInlinedMethod(InlineInfo info, String msg, Object... args) { logInliningDecision(info, false, msg, args); + return false; } public static void logInliningDecision(InlineInfo info, boolean success, String msg, final Object... args) { @@ -82,6 +78,11 @@ }); } + public static boolean logInlinedMethod(InlineInfo info, String string, Object... args) { + logInliningDecision(info, true, string, args); + return true; + } + private static boolean logNotInlinedMethodAndReturnFalse(Invoke invoke, String msg) { if (shouldLogInliningDecision()) { String methodString = invoke.toString() + (invoke.callTarget() == null ? " callTarget=null" : invoke.callTarget().targetName()); @@ -118,7 +119,7 @@ logInliningDecision(inliningMsg, args); } - private static boolean shouldLogInliningDecision() { + public static boolean shouldLogInliningDecision() { return Debug.scope(inliningDecisionsScopeString, new Callable<Boolean>() { public Boolean call() { return Debug.isLogEnabled(); @@ -160,42 +161,38 @@ * The weight is the amortized weight of the additional code - so smaller is better. * The level is the number of nested inlinings that lead to this invoke. */ - public interface InlineInfo extends Comparable<InlineInfo> { + public interface InlineInfo { Invoke invoke(); - double weight(); int level(); - int compiledCodeSize(); - int compareTo(InlineInfo o); + + int numberOfMethods(); + ResolvedJavaMethod methodAt(int index); /** * Performs the inlining described by this object and returns the node that represents the return value of the * inlined method (or null for void methods and methods that have no non-exceptional exit). */ void inline(StructuredGraph graph, GraalCodeCacheProvider runtime, InliningCallback callback, Assumptions assumptions); + + /** + * Try to make the call static bindable to avoid interface and virtual method calls. + */ + void tryToDevirtualizeInvoke(StructuredGraph graph, GraalCodeCacheProvider runtime, Assumptions assumptions); } public abstract static class AbstractInlineInfo implements InlineInfo { protected final Invoke invoke; - protected final double weight; - public AbstractInlineInfo(Invoke invoke, double weight) { + public AbstractInlineInfo(Invoke invoke) { this.invoke = invoke; - this.weight = weight; } @Override - public int compareTo(InlineInfo o) { - return (weight < o.weight()) ? -1 : (weight > o.weight()) ? 1 : 0; - } - public Invoke invoke() { return invoke; } - public double weight() { - return weight; - } - + @Override public int level() { return computeInliningLevel(invoke); } @@ -213,6 +210,12 @@ } }); } + + protected void replaceInvokeCallTarget(StructuredGraph graph, InvokeKind invokeKind, ResolvedJavaMethod targetMethod) { + MethodCallTargetNode oldCallTarget = invoke.methodCallTarget(); + MethodCallTargetNode newCallTarget = graph.add(new MethodCallTargetNode(invokeKind, targetMethod, oldCallTarget.arguments().toArray(new ValueNode[0]), oldCallTarget.returnType())); + invoke.node().replaceFirstInput(oldCallTarget, newCallTarget); + } } /** @@ -222,8 +225,8 @@ private static class ExactInlineInfo extends AbstractInlineInfo { public final ResolvedJavaMethod concrete; - public ExactInlineInfo(Invoke invoke, double weight, ResolvedJavaMethod concrete) { - super(invoke, weight); + public ExactInlineInfo(Invoke invoke, ResolvedJavaMethod concrete) { + super(invoke); this.concrete = concrete; } @@ -235,8 +238,19 @@ } @Override - public int compiledCodeSize() { - return InliningUtil.compiledCodeSize(concrete); + public void tryToDevirtualizeInvoke(StructuredGraph graph, GraalCodeCacheProvider runtime, Assumptions assumptions) { + // nothing todo, can already be bound statically + } + + @Override + public int numberOfMethods() { + return 1; + } + + @Override + public ResolvedJavaMethod methodAt(int index) { + assert index == 0; + return concrete; } @Override @@ -253,20 +267,39 @@ public final ResolvedJavaMethod concrete; public final ResolvedJavaType type; - public TypeGuardInlineInfo(Invoke invoke, double weight, ResolvedJavaMethod concrete, ResolvedJavaType type) { - super(invoke, weight); + public TypeGuardInlineInfo(Invoke invoke, ResolvedJavaMethod concrete, ResolvedJavaType type) { + super(invoke); this.concrete = concrete; this.type = type; } @Override - public int compiledCodeSize() { - return InliningUtil.compiledCodeSize(concrete); + public int numberOfMethods() { + return 1; + } + + @Override + public ResolvedJavaMethod methodAt(int index) { + assert index == 0; + return concrete; } @Override public void inline(StructuredGraph graph, GraalCodeCacheProvider runtime, InliningCallback callback, Assumptions assumptions) { - // receiver null check must be before the type check + createGuard(graph, runtime); + + StructuredGraph calleeGraph = getGraph(concrete, callback); + assumptions.recordMethodContents(concrete); + InliningUtil.inline(invoke, calleeGraph, false); + } + + @Override + public void tryToDevirtualizeInvoke(StructuredGraph graph, GraalCodeCacheProvider runtime, Assumptions assumptions) { + createGuard(graph, runtime); + replaceInvokeCallTarget(graph, InvokeKind.Special, concrete); + } + + private void createGuard(StructuredGraph graph, GraalCodeCacheProvider runtime) { InliningUtil.receiverNullCheck(invoke); ValueNode receiver = invoke.methodCallTarget().receiver(); ConstantNode typeHub = ConstantNode.forConstant(type.getEncoding(Representation.ObjectHub), runtime, graph); @@ -282,10 +315,6 @@ graph.addBeforeFixed(invoke.node(), receiverHub); graph.addBeforeFixed(invoke.node(), guard); graph.addBeforeFixed(invoke.node(), anchor); - - StructuredGraph calleeGraph = getGraph(concrete, callback); - assumptions.recordMethodContents(concrete); - InliningUtil.inline(invoke, calleeGraph, false); } @Override @@ -304,9 +333,9 @@ public final int[] typesToConcretes; public final double notRecordedTypeProbability; - public MultiTypeGuardInlineInfo(Invoke invoke, double weight, ArrayList<ResolvedJavaMethod> concretes, ArrayList<ProfiledType> ptypes, + public MultiTypeGuardInlineInfo(Invoke invoke, ArrayList<ResolvedJavaMethod> concretes, ArrayList<ProfiledType> ptypes, int[] typesToConcretes, double notRecordedTypeProbability) { - super(invoke, weight); + super(invoke); assert concretes.size() > 0 && concretes.size() <= ptypes.size() : "must have at least one method but no more than types methods"; assert ptypes.size() == typesToConcretes.length : "array lengths must match"; @@ -317,33 +346,37 @@ } @Override - public int compiledCodeSize() { - int result = 0; - for (ResolvedJavaMethod m: concretes) { - result += InliningUtil.compiledCodeSize(m); - } - return result; + public int numberOfMethods() { + return concretes.size(); + } + + @Override + public ResolvedJavaMethod methodAt(int index) { + assert index >= 0 && index < concretes.size(); + return concretes.get(index); } @Override public void inline(StructuredGraph graph, GraalCodeCacheProvider runtime, InliningCallback callback, Assumptions assumptions) { - int numberOfMethods = concretes.size(); - boolean hasReturnValue = invoke.node().kind() != Kind.Void; - // receiver null check must be the first node InliningUtil.receiverNullCheck(invoke); - if (numberOfMethods > 1 || shouldFallbackToInvoke()) { - inlineMultipleMethods(graph, callback, assumptions, numberOfMethods, hasReturnValue); + if (hasSingleMethod()) { + inlineSingleMethod(graph, callback, assumptions); } else { - inlineSingleMethod(graph, callback, assumptions); + inlineMultipleMethods(graph, callback, assumptions); } } + private boolean hasSingleMethod() { + return concretes.size() == 1 && !shouldFallbackToInvoke(); + } + private boolean shouldFallbackToInvoke() { return notRecordedTypeProbability > 0; } - private void inlineMultipleMethods(StructuredGraph graph, InliningCallback callback, Assumptions assumptions, int numberOfMethods, boolean hasReturnValue) { + private void inlineMultipleMethods(StructuredGraph graph, InliningCallback callback, Assumptions assumptions) { + int numberOfMethods = concretes.size(); FixedNode continuation = invoke.next(); ValueNode originalReceiver = invoke.methodCallTarget().receiver(); @@ -353,7 +386,7 @@ returnMerge.setStateAfter(invoke.stateAfter().duplicate(invoke.stateAfter().bci)); PhiNode returnValuePhi = null; - if (hasReturnValue) { + if (invoke.node().kind() != Kind.Void) { returnValuePhi = graph.unique(new PhiNode(invoke.node().kind(), returnMerge)); } @@ -415,16 +448,13 @@ } // replace the invoke with a switch on the type of the actual receiver - Kind hubKind = invoke.methodCallTarget().targetMethod().getDeclaringClass().getEncoding(Representation.ObjectHub).getKind(); - LoadHubNode receiverHub = graph.add(new LoadHubNode(invoke.methodCallTarget().receiver(), hubKind)); - graph.addBeforeFixed(invoke.node(), receiverHub); - FixedNode dispatchOnType = createDispatchOnType(graph, receiverHub, successors); + createDispatchOnTypeBeforeInvoke(graph, successors, false); assert invoke.next() == continuation; invoke.setNext(null); returnMerge.setNext(continuation); invoke.node().replaceAtUsages(returnValuePhi); - invoke.node().replaceAndDelete(dispatchOnType); + invoke.node().replaceAndDelete(null); ArrayList<PiNode> replacements = new ArrayList<>(); @@ -494,21 +524,24 @@ return commonType; } + private ResolvedJavaType getLeastCommonType() { + ResolvedJavaType result = getLeastCommonType(0); + for (int i = 1; i < concretes.size(); i++) { + result = result.findLeastCommonAncestor(getLeastCommonType(i)); + } + return result; + } + private void inlineSingleMethod(StructuredGraph graph, InliningCallback callback, Assumptions assumptions) { assert concretes.size() == 1 && ptypes.size() > 1 && !shouldFallbackToInvoke() && notRecordedTypeProbability == 0; BeginNode calleeEntryNode = graph.add(new BeginNode()); calleeEntryNode.setProbability(invoke.probability()); - Kind hubKind = invoke.methodCallTarget().targetMethod().getDeclaringClass().getEncoding(Representation.ObjectHub).getKind(); - LoadHubNode receiverHub = graph.add(new LoadHubNode(invoke.methodCallTarget().receiver(), hubKind)); - graph.addBeforeFixed(invoke.node(), receiverHub); - BeginNode unknownTypeSux = BeginNode.begin(graph.add(new DeoptimizeNode(DeoptimizationAction.InvalidateReprofile, DeoptimizationReason.TypeCheckedInliningViolated, invoke.leafGraphId()))); + BeginNode unknownTypeSux = createUnknownTypeSuccessor(graph); BeginNode[] successors = new BeginNode[] {calleeEntryNode, unknownTypeSux}; - FixedNode dispatchOnType = createDispatchOnType(graph, receiverHub, successors); + createDispatchOnTypeBeforeInvoke(graph, successors, false); - FixedWithNextNode pred = (FixedWithNextNode) invoke.node().predecessor(); - pred.setNext(dispatchOnType); calleeEntryNode.setNext(invoke.node()); ResolvedJavaMethod concrete = concretes.get(0); @@ -517,16 +550,20 @@ InliningUtil.inline(invoke, calleeGraph, false); } - private FixedNode createDispatchOnType(StructuredGraph graph, LoadHubNode hub, BeginNode[] successors) { + private void createDispatchOnTypeBeforeInvoke(StructuredGraph graph, BeginNode[] successors, boolean invokeIsOnlySuccessor) { assert ptypes.size() > 1; + Kind hubKind = invoke.methodCallTarget().targetMethod().getDeclaringClass().getEncoding(Representation.ObjectHub).getKind(); + LoadHubNode hub = graph.add(new LoadHubNode(invoke.methodCallTarget().receiver(), hubKind)); + graph.addBeforeFixed(invoke.node(), hub); + ResolvedJavaType[] keys = new ResolvedJavaType[ptypes.size()]; double[] keyProbabilities = new double[ptypes.size() + 1]; int[] keySuccessors = new int[ptypes.size() + 1]; for (int i = 0; i < ptypes.size(); i++) { keys[i] = ptypes.get(i).getType(); keyProbabilities[i] = ptypes.get(i).getProbability(); - keySuccessors[i] = typesToConcretes[i]; + keySuccessors[i] = invokeIsOnlySuccessor ? 0 : typesToConcretes[i]; assert keySuccessors[i] < successors.length - 1 : "last successor is the unknownTypeSux"; } keyProbabilities[keyProbabilities.length - 1] = notRecordedTypeProbability; @@ -534,8 +571,8 @@ double[] successorProbabilities = SwitchNode.successorProbabilites(successors.length, keySuccessors, keyProbabilities); TypeSwitchNode typeSwitch = graph.add(new TypeSwitchNode(hub, successors, successorProbabilities, keys, keyProbabilities, keySuccessors)); - - return typeSwitch; + FixedWithNextNode pred = (FixedWithNextNode) invoke.node().predecessor(); + pred.setNext(typeSwitch); } private static BeginNode createInvocationBlock(StructuredGraph graph, Invoke invoke, MergeNode returnMerge, PhiNode returnValuePhi, @@ -598,6 +635,55 @@ } @Override + public void tryToDevirtualizeInvoke(StructuredGraph graph, GraalCodeCacheProvider runtime, Assumptions assumptions) { + if (hasSingleMethod()) { + tryToDevirtualizeSingleMethod(graph); + } else { + tryToDevirtualizeMultipleMethods(graph); + } + } + + private void tryToDevirtualizeSingleMethod(StructuredGraph graph) { + devirtualizeWithTypeSwitch(graph, InvokeKind.Special, concretes.get(0)); + } + + private void tryToDevirtualizeMultipleMethods(StructuredGraph graph) { + MethodCallTargetNode methodCallTarget = invoke.methodCallTarget(); + if (methodCallTarget.invokeKind() == InvokeKind.Interface) { + ResolvedJavaMethod targetMethod = methodCallTarget.targetMethod(); + ResolvedJavaType leastCommonType = getLeastCommonType(); + // check if we have a common base type that implements the interface -> in that case we have a vtable entry for the interface method and can use a less expensive virtual call + if (!leastCommonType.isInterface() && targetMethod.getDeclaringClass().isAssignableFrom(leastCommonType)) { + ResolvedJavaMethod baseClassTargetMethod = leastCommonType.resolveMethod(targetMethod); + if (baseClassTargetMethod != null) { + devirtualizeWithTypeSwitch(graph, InvokeKind.Virtual, leastCommonType.resolveMethod(targetMethod)); + } + } + } + } + + private void devirtualizeWithTypeSwitch(StructuredGraph graph, InvokeKind kind, ResolvedJavaMethod target) { + InliningUtil.receiverNullCheck(invoke); + + BeginNode invocationEntry = graph.add(new BeginNode()); + invocationEntry.setProbability(invoke.probability()); + + BeginNode unknownTypeSux = createUnknownTypeSuccessor(graph); + BeginNode[] successors = new BeginNode[] {invocationEntry, unknownTypeSux}; + createDispatchOnTypeBeforeInvoke(graph, successors, true); + + invocationEntry.setNext(invoke.node()); + ValueNode receiver = invoke.methodCallTarget().receiver(); + PiNode anchoredReceiver = createAnchoredReceiver(graph, invocationEntry, target.getDeclaringClass(), receiver, false); + invoke.callTarget().replaceFirstInput(receiver, anchoredReceiver); + replaceInvokeCallTarget(graph, kind, target); + } + + private BeginNode createUnknownTypeSuccessor(StructuredGraph graph) { + return BeginNode.begin(graph.add(new DeoptimizeNode(DeoptimizationAction.InvalidateReprofile, DeoptimizationReason.TypeCheckedInliningViolated, invoke.leafGraphId()))); + } + + @Override public String toString() { StringBuilder builder = new StringBuilder(shouldFallbackToInvoke() ? "megamorphic" : "polymorphic"); builder.append(", "); @@ -627,8 +713,8 @@ private static class AssumptionInlineInfo extends ExactInlineInfo { private final Assumption takenAssumption; - public AssumptionInlineInfo(Invoke invoke, double weight, ResolvedJavaMethod concrete, Assumption takenAssumption) { - super(invoke, weight, concrete); + public AssumptionInlineInfo(Invoke invoke, ResolvedJavaMethod concrete, Assumption takenAssumption) { + super(invoke, concrete); this.takenAssumption = takenAssumption; } @@ -641,6 +727,12 @@ } @Override + public void tryToDevirtualizeInvoke(StructuredGraph graph, GraalCodeCacheProvider runtime, Assumptions assumptions) { + assumptions.record(takenAssumption); + replaceInvokeCallTarget(graph, InvokeKind.Special, concrete); + } + + @Override public String toString() { return "assumption " + MetaUtil.format("%H.%n(%p):%r", concrete); } @@ -649,10 +741,9 @@ /** * Determines if inlining is possible at the given invoke node. * @param invoke the invoke that should be inlined - * @param inliningPolicy used to determine the weight of a specific inlining * @return an instance of InlineInfo, or null if no inlining is possible at the given invoke */ - public static InlineInfo getInlineInfo(Invoke invoke, Assumptions assumptions, InliningPolicy inliningPolicy, OptimisticOptimizations optimisticOpts) { + public static InlineInfo getInlineInfo(Invoke invoke, Assumptions assumptions, OptimisticOptimizations optimisticOpts) { if (!checkInvokeConditions(invoke)) { return null; } @@ -661,7 +752,7 @@ ResolvedJavaMethod targetMethod = callTarget.targetMethod(); if (callTarget.invokeKind() == InvokeKind.Special || targetMethod.canBeStaticallyBound()) { - return getExactInlineInfo(invoke, inliningPolicy, optimisticOpts, caller, targetMethod); + return getExactInlineInfo(invoke, optimisticOpts, targetMethod); } assert callTarget.invokeKind() == InvokeKind.Virtual || callTarget.invokeKind() == InvokeKind.Interface; @@ -675,56 +766,52 @@ holder = receiverType; if (receiverStamp.isExactType()) { assert targetMethod.getDeclaringClass().isAssignableFrom(holder) : holder + " subtype of " + targetMethod.getDeclaringClass() + " for " + targetMethod; - return getExactInlineInfo(invoke, inliningPolicy, optimisticOpts, caller, holder.resolveMethod(targetMethod)); + return getExactInlineInfo(invoke, optimisticOpts, holder.resolveMethod(targetMethod)); } } } if (holder.isArray()) { // arrays can be treated as Objects - return getExactInlineInfo(invoke, inliningPolicy, optimisticOpts, caller, holder.resolveMethod(targetMethod)); + return getExactInlineInfo(invoke, optimisticOpts, holder.resolveMethod(targetMethod)); } // TODO (chaeubl): we could also use the type determined after assumptions for the type-checked inlining case as it might have an effect on type filtering if (assumptions.useOptimisticAssumptions()) { ResolvedJavaType uniqueSubtype = holder.findUniqueConcreteSubtype(); if (uniqueSubtype != null) { - return getAssumptionInlineInfo(invoke, inliningPolicy, optimisticOpts, caller, uniqueSubtype.resolveMethod(targetMethod), new Assumptions.ConcreteSubtype(holder, uniqueSubtype)); + return getAssumptionInlineInfo(invoke, optimisticOpts, uniqueSubtype.resolveMethod(targetMethod), new Assumptions.ConcreteSubtype(holder, uniqueSubtype)); } ResolvedJavaMethod concrete = holder.findUniqueConcreteMethod(targetMethod); if (concrete != null) { - return getAssumptionInlineInfo(invoke, inliningPolicy, optimisticOpts, caller, concrete, new Assumptions.ConcreteMethod(targetMethod, holder, concrete)); + return getAssumptionInlineInfo(invoke, optimisticOpts, concrete, new Assumptions.ConcreteMethod(targetMethod, holder, concrete)); } // TODO (chaeubl): C1 has one more assumption in the case of interfaces } // type check based inlining - return getTypeCheckedInlineInfo(invoke, inliningPolicy, caller, holder, targetMethod, optimisticOpts); + return getTypeCheckedInlineInfo(invoke, caller, holder, targetMethod, optimisticOpts); } - private static InlineInfo getAssumptionInlineInfo(Invoke invoke, InliningPolicy inliningPolicy, OptimisticOptimizations optimisticOpts, - ResolvedJavaMethod caller, ResolvedJavaMethod concrete, Assumption takenAssumption) { + private static InlineInfo getAssumptionInlineInfo(Invoke invoke, OptimisticOptimizations optimisticOpts, ResolvedJavaMethod concrete, Assumption takenAssumption) { assert !Modifier.isAbstract(concrete.getModifiers()); if (!checkTargetConditions(invoke, concrete, optimisticOpts)) { return null; } - double weight = inliningPolicy.inliningWeight(caller, concrete, invoke); - return new AssumptionInlineInfo(invoke, weight, concrete, takenAssumption); + return new AssumptionInlineInfo(invoke, concrete, takenAssumption); } - private static InlineInfo getExactInlineInfo(Invoke invoke, InliningPolicy inliningPolicy, OptimisticOptimizations optimisticOpts, - ResolvedJavaMethod caller, ResolvedJavaMethod targetMethod) { + private static InlineInfo getExactInlineInfo(Invoke invoke, OptimisticOptimizations optimisticOpts, ResolvedJavaMethod targetMethod) { assert !Modifier.isAbstract(targetMethod.getModifiers()); if (!checkTargetConditions(invoke, targetMethod, optimisticOpts)) { return null; } - double weight = inliningPolicy.inliningWeight(caller, targetMethod, invoke); - return new ExactInlineInfo(invoke, weight, targetMethod); + return new ExactInlineInfo(invoke, targetMethod); } - private static InlineInfo getTypeCheckedInlineInfo(Invoke invoke, InliningPolicy inliningPolicy, ResolvedJavaMethod caller, + private static InlineInfo getTypeCheckedInlineInfo(Invoke invoke, ResolvedJavaMethod caller, ResolvedJavaType holder, ResolvedJavaMethod targetMethod, OptimisticOptimizations optimisticOpts) { ProfilingInfo profilingInfo = caller.getProfilingInfo(); JavaTypeProfile typeProfile = profilingInfo.getTypeProfile(invoke.bci()); @@ -749,8 +836,7 @@ if (!checkTargetConditions(invoke, concrete, optimisticOpts)) { return null; } - double weight = inliningPolicy.inliningWeight(caller, concrete, invoke); - return new TypeGuardInlineInfo(invoke, weight, concrete, type); + return new TypeGuardInlineInfo(invoke, concrete, type); } else { invoke.setPolymorphic(true); @@ -783,14 +869,12 @@ typesToConcretes[i] = index; } - double totalWeight = 0; for (ResolvedJavaMethod concrete: concreteMethods) { if (!checkTargetConditions(invoke, concrete, optimisticOpts)) { return logNotInlinedMethodAndReturnNull(invoke, targetMethod, "it is a polymorphic method call and at least one invoked method cannot be inlined"); } - totalWeight += inliningPolicy.inliningWeight(caller, concrete, invoke); } - return new MultiTypeGuardInlineInfo(invoke, totalWeight, concreteMethods, ptypes, typesToConcretes, notRecordedTypeProbability); + return new MultiTypeGuardInlineInfo(invoke, concreteMethods, ptypes, typesToConcretes, notRecordedTypeProbability); } } @@ -979,7 +1063,7 @@ if (node instanceof Invoke) { Invoke newInvoke = (Invoke) node; double newRelevance = newInvoke.inliningRelevance() * invoke.inliningRelevance(); - if (GraalOptions.LimitInlinedProbability) { + if (GraalOptions.LimitInlinedRelevance) { newRelevance = Math.min(newRelevance, invoke.inliningRelevance()); } newInvoke.setInliningRelevance(newRelevance); @@ -1050,12 +1134,4 @@ public static StructuredGraph getIntrinsicGraph(ResolvedJavaMethod target) { return (StructuredGraph) target.getCompilerStorage().get(Graph.class); } - - private static int compiledCodeSize(ResolvedJavaMethod target) { - if (GraalOptions.AlwaysInlineIntrinsics && canIntrinsify(target)) { - return 0; - } else { - return target.getCompiledCodeSize(); - } - } }
--- a/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/GraalOptions.java Wed Jan 16 10:19:09 2013 +0100 +++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/GraalOptions.java Fri Feb 01 16:57:40 2013 +0100 @@ -44,30 +44,24 @@ static boolean InlineMonomorphicCalls = true; static boolean InlinePolymorphicCalls = true; static boolean InlineMegamorphicCalls = ____; - public static int InliningPolicy = 1; - public static int InliningDecision = 4; - public static int WeightComputationPolicy = 2; - public static int MaximumTrivialSize = 10; public static int MaximumInlineLevel = 30; - public static int MaximumDesiredSize = 3000; + public static int MaximumDesiredSize = 5000; public static int MaximumRecursiveInlining = 1; - public static int SmallCompiledCodeSize = 2200; public static boolean LimitInlinedProbability = ____; - public static boolean UseRelevanceBasedInlining = ____; - // WeightBasedInliningPolicy (0) - public static float InliningSizePenaltyExp = 20; - public static float MaximumInlineWeight = 1.25f; - public static float InliningSizePenalty = 1; - // StaticSizeBasedInliningPolicy (1), MinimumCodeSizeBasedInlining (2), - // DynamicSizeBasedInliningPolicy (3) - public static int MaximumInlineSize = 35; - // GreedySizeBasedInlining (4) - public static int MaximumGreedyInlineSize = 100; - public static int InliningBonusPerTransferredValue = 10; - // Common options for inlining policies 1 to 4 - public static float NestedInliningSizeRatio = 1f; + public static boolean LimitInlinedRelevance = true; public static float BoostInliningForEscapeAnalysis = 2f; - public static float RatioCapForInlining = 1f; + public static float RelevanceCapForInlining = 1f; + + public static int TrivialBytecodeSize = 10; + public static int NormalBytecodeSize = 100; + public static int MaximumBytecodeSize = 500; + public static int TrivialComplexity = 10; + public static int NormalComplexity = 40; + public static int MaximumComplexity = 400; + public static int TrivialCompiledCodeSize = 150; + public static int NormalCompiledCodeSize = 500; + public static int MaximumCompiledCodeSize = 4000; + public static int SmallCompiledCodeSize = 1000; // escape analysis settings public static boolean PartialEscapeAnalysis = true; @@ -80,7 +74,6 @@ // absolute probability analysis public static boolean ProbabilityAnalysis = true; - public static int LoopFrequencyPropagationPolicy = -2; // profiling information public static int DeoptsToDisableOptimisticOptimization = 40; @@ -202,6 +195,7 @@ public static boolean OptTailDuplication = true; public static boolean OptEliminatePartiallyRedundantGuards = true; public static boolean OptFilterProfiledTypes = true; + public static boolean OptDevirtualizeInvokesOptimistically = true; // Intrinsification settings public static boolean IntrinsifyArrayCopy = true;
--- a/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/OptimisticOptimizations.java Wed Jan 16 10:19:09 2013 +0100 +++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/OptimisticOptimizations.java Fri Feb 01 16:57:40 2013 +0100 @@ -86,6 +86,10 @@ return GraalOptions.InlineMegamorphicCalls && enabledOpts.contains(Optimization.UseTypeCheckedInlining); } + public boolean devirtualizeInvokes() { + return GraalOptions.OptDevirtualizeInvokesOptimistically && enabledOpts.contains(Optimization.UseTypeCheckedInlining); + } + public boolean useExceptionProbability() { return GraalOptions.UseExceptionProbability && enabledOpts.contains(Optimization.UseExceptionProbability); }
--- a/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/graph/ScopedPostOrderNodeIterator.java Wed Jan 16 10:19:09 2013 +0100 +++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/graph/ScopedPostOrderNodeIterator.java Fri Feb 01 16:57:40 2013 +0100 @@ -29,15 +29,13 @@ import com.oracle.graal.nodes.*; public abstract class ScopedPostOrderNodeIterator { - private final NodeBitMap processedNodes; private final Deque<FixedNode> nodeQueue; private final NodeBitMap queuedNodes; private final Deque<FixedNode> scopes; - protected FixedNode currentScope; + protected FixedNode currentScopeStart; public ScopedPostOrderNodeIterator(StructuredGraph graph) { - this.processedNodes = graph.createNodeBitMap(); this.queuedNodes = graph.createNodeBitMap(); this.nodeQueue = new ArrayDeque<>(); this.scopes = getScopes(graph); @@ -45,64 +43,57 @@ public void apply() { while (!scopes.isEmpty()) { - processedNodes.clearAll(); queuedNodes.clearAll(); - this.currentScope = scopes.pop(); + this.currentScopeStart = scopes.pop(); initializeScope(); processScope(); } } public void processScope() { - FixedNode current = currentScope; - do { + FixedNode current; + queue(currentScopeStart); + + while ((current = nextQueuedNode()) != null) { assert current.isAlive(); - processedNodes.mark(current); if (current instanceof Invoke) { invoke((Invoke) current); queueSuccessors(current); - current = nextQueuedNode(); } else if (current instanceof LoopBeginNode) { queueLoopBeginSuccessors((LoopBeginNode) current); - current = nextQueuedNode(); } else if (current instanceof LoopExitNode) { queueLoopExitSuccessors((LoopExitNode) current); - current = nextQueuedNode(); } else if (current instanceof LoopEndNode) { - current = nextQueuedNode(); + // nothing todo } else if (current instanceof MergeNode) { - current = ((MergeNode) current).next(); - assert current != null; + queueSuccessors(current); } else if (current instanceof FixedWithNextNode) { queueSuccessors(current); - current = nextQueuedNode(); } else if (current instanceof EndNode) { queueMerge((EndNode) current); - current = nextQueuedNode(); } else if (current instanceof DeoptimizeNode) { - current = nextQueuedNode(); + // nothing todo } else if (current instanceof ReturnNode) { - current = nextQueuedNode(); + // nothing todo } else if (current instanceof UnwindNode) { - current = nextQueuedNode(); + // nothing todo } else if (current instanceof ControlSplitNode) { queueSuccessors(current); - current = nextQueuedNode(); } else { assert false : current; } - } while(current != null); + } } protected void queueLoopBeginSuccessors(LoopBeginNode node) { - if (currentScope == node) { + if (currentScopeStart == node) { queue(node.next()); - } else if (currentScope instanceof LoopBeginNode) { + } else if (currentScopeStart instanceof LoopBeginNode) { // so we are currently processing loop A and found another loop B // -> queue all loop exits of B except those that also exit loop A for (LoopExitNode loopExit: node.loopExits()) { - if (!((LoopBeginNode) currentScope).loopExits().contains(loopExit)) { + if (!((LoopBeginNode) currentScopeStart).loopExits().contains(loopExit)) { queue(loopExit); } } @@ -112,7 +103,7 @@ } protected void queueLoopExitSuccessors(LoopExitNode node) { - if (!(currentScope instanceof LoopBeginNode) || !((LoopBeginNode) currentScope).loopExits().contains(node)) { + if (!(currentScopeStart instanceof LoopBeginNode) || !((LoopBeginNode) currentScopeStart).loopExits().contains(node)) { queueSuccessors(node); } } @@ -156,14 +147,13 @@ private void queueMerge(EndNode end) { MergeNode merge = end.merge(); if (!queuedNodes.isMarked(merge) && visitedAllEnds(merge)) { - queuedNodes.mark(merge); - nodeQueue.add(merge); + queue(merge); } } private boolean visitedAllEnds(MergeNode merge) { for (int i = 0; i < merge.forwardEndCount(); i++) { - if (!processedNodes.isMarked(merge.forwardEndAt(i))) { + if (!queuedNodes.isMarked(merge.forwardEndAt(i))) { return false; } }
--- a/src/share/vm/runtime/compilationPolicy.cpp Wed Jan 16 10:19:09 2013 +0100 +++ b/src/share/vm/runtime/compilationPolicy.cpp Fri Feb 01 16:57:40 2013 +0100 @@ -492,7 +492,7 @@ int hot_count = m->backedge_count(); const char* comment = "backedge_count"; - if (is_compilation_enabled() && !m->is_not_osr_compilable() && can_be_compiled(m)) { + if (is_compilation_enabled() && !m->is_not_osr_compilable() && can_be_compiled(m) && !m->queued_for_compilation() && m->code() == NULL) { if (TraceCompilationPolicy) { tty->print("backedge invocation trigger: "); m->print_short_name(tty);