Mercurial > hg > truffle
changeset 15512:d968c2db220b
Merge ([flow-sensitive] refactoring, factor out evidence-search)
| author | Lukas Stadler <lukas.stadler@oracle.com> |
|---|---|
| date | Mon, 05 May 2014 18:39:29 +0200 |
| parents | ef1342e0f9f2 (current diff) 49a917f9fa07 (diff) |
| children | 130e0183b7e2 |
| files | |
| diffstat | 6 files changed, 355 insertions(+), 159 deletions(-) [+] |
line wrap: on
line diff
--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/EquationalReasoner.java Mon May 05 18:39:09 2014 +0200 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/EquationalReasoner.java Mon May 05 18:39:29 2014 +0200 @@ -267,6 +267,10 @@ } if (FlowUtil.hasLegalObjectStamp(v)) { + if (state.isNull(v)) { + // it's ok to return nullConstant in deverbosify unlike in downcast + return nullConstant; + } return downcast(v); } @@ -441,6 +445,8 @@ return baseCaseIsNullNode((IsNullNode) condition); } else if (condition instanceof ObjectEqualsNode) { return baseCaseObjectEqualsNode((ObjectEqualsNode) condition); + } else if (condition instanceof ShortCircuitOrNode) { + return baseCaseShortCircuitOrNode((ShortCircuitOrNode) condition); } } return condition; @@ -483,7 +489,7 @@ return isNull; } ValueNode scrutinee = GraphUtil.unproxify(isNull.object()); - GuardingNode evidence = nonTrivialNullAnchor(scrutinee); + GuardingNode evidence = state.nonTrivialNullAnchor(scrutinee); if (evidence != null) { metricNullCheckRemoved.increment(); return trueConstant; @@ -515,6 +521,38 @@ } /** + * The following is tried: + * + * <ol> + * <li> + * A {@link com.oracle.graal.phases.common.cfs.Witness} that is at check-cast level level + * doesn't entail {@link com.oracle.graal.nodes.calc.IsNullNode} (on its own) nor + * {@link com.oracle.graal.nodes.java.InstanceOfNode} (also on its own) but of course it entails + * <code>(IsNull || IsInstanceOf)</code>. Good thing + * {@link com.oracle.graal.phases.common.cfs.CastCheckExtractor} detects that very pattern.</li> + * <li> + * Otherwise return the unmodified argument (later on, + * {@link #deverbosifyFloatingNode(com.oracle.graal.nodes.calc.FloatingNode)} will attempt to + * simplify the {@link com.oracle.graal.nodes.ShortCircuitOrNode}).</li> + * </ol> + * + * @return a {@link com.oracle.graal.nodes.LogicConstantNode}, in case a reduction was made; + * otherwise the unmodified argument. + */ + private LogicNode baseCaseShortCircuitOrNode(ShortCircuitOrNode orNode) { + CastCheckExtractor cast = CastCheckExtractor.extract(orNode); + if (cast != null) { + if (state.knownToConform(cast.subject, cast.type)) { + return trueConstant; + } else if (state.knownNotToConform(cast.subject, cast.type)) { + return falseConstant; + } + return orNode; + } + return orNode; + } + + /** * It's always ok to use "<code>downcast(object)</code>" instead of " <code>object</code>" * because this method re-wraps the argument in a {@link com.oracle.graal.nodes.PiNode} only if * the new stamp is strictly more refined than the original. @@ -646,24 +684,6 @@ } /** - * <p> - * If the argument is known null due to its stamp, there's no need to have an anchor for that - * fact and this method returns null. - * </p> - * - * <p> - * Otherwise, if an anchor is found it is returned, null otherwise. - * </p> - */ - public GuardingNode nonTrivialNullAnchor(ValueNode object) { - assert FlowUtil.hasLegalObjectStamp(object); - if (StampTool.isObjectAlwaysNull(object)) { - return null; - } - return state.knownNull.get(GraphUtil.unproxify(object)); - } - - /** * * This method returns: * <ul> @@ -680,7 +700,7 @@ */ public PiNode nonTrivialNull(ValueNode object) { assert FlowUtil.hasLegalObjectStamp(object); - GuardingNode anchor = nonTrivialNullAnchor(object); + GuardingNode anchor = state.nonTrivialNullAnchor(object); if (anchor == null) { return null; }
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/Evidence.java Mon May 05 18:39:29 2014 +0200 @@ -0,0 +1,61 @@ +/* + * Copyright (c) 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.phases.common.cfs; + +import com.oracle.graal.nodes.extended.GuardingNode; + +public class Evidence { + + public final GuardingNode success; + public final boolean failure; + + public Evidence(GuardingNode success, boolean failure) { + this.success = success; + this.failure = failure; + assert repOK(); + } + + public Evidence(GuardingNode success) { + this(success, false); + } + + private Evidence(boolean failure) { + this(null, failure); + } + + public boolean isPositive() { + return success != null; + } + + public boolean isNegative() { + return failure; + } + + private boolean repOK() { + // either success or failure, ie boolean-XOR + return (success != null) != failure; + } + + public static Evidence COUNTEREXAMPLE = new Evidence(true); + +}
--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/FixedGuardReduction.java Mon May 05 18:39:09 2014 +0200 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/FixedGuardReduction.java Mon May 05 18:39:29 2014 +0200 @@ -23,9 +23,7 @@ package com.oracle.graal.phases.common.cfs; import com.oracle.graal.nodes.*; -import com.oracle.graal.nodes.calc.IsNullNode; import com.oracle.graal.nodes.extended.GuardingNode; -import com.oracle.graal.nodes.java.*; import com.oracle.graal.phases.tiers.PhaseContext; /** @@ -99,118 +97,33 @@ return; } - /* - * Attempt to eliminate the current FixedGuardNode by using another GuardingNode already in - * scope and with equivalent condition. - */ + final boolean isTrue = !f.isNegated(); + final Evidence evidence = state.outcome(isTrue, f.condition()); - GuardingNode existingGuard = f.isNegated() ? state.falseFacts.get(f.condition()) : state.trueFacts.get(f.condition()); - if (existingGuard != null) { - // assert existingGuard instanceof FixedGuardNode; - metricFixedGuardNodeRemoved.increment(); - f.replaceAtUsages(existingGuard.asNode()); - graph.removeFixed(f); + // can't produce evidence, must be information gain + if (evidence == null) { + state.addFact(isTrue, f.condition(), f); return; } - final LogicNode cond = f.condition(); - final boolean isTrue = !f.isNegated(); - - /* - * A FixedGuardNode can only be removed provided a replacement anchor is found (so called - * "evidence"), ie an anchor that amounts to the same combination of (negated, condition) as - * for the FixedGuardNode at hand. Just deverbosifying the condition in place isn't - * semantics-preserving. - */ - - // TODO what about isDependencyTainted - - if (cond instanceof IsNullNode) { - final IsNullNode isNullNode = (IsNullNode) cond; - if (isTrue) { - // grab an anchor attesting nullness - final GuardingNode replacement = reasoner.nonTrivialNullAnchor(isNullNode.object()); - if (replacement != null) { - removeFixedGuardNode(f, replacement); - return; - } - if (state.isNonNull(isNullNode.object())) { - markFixedGuardNodeAlwaysFails(f); - return; - } - // can't produce evidence, fall-through to addFact - } else { - // grab an anchor attesting non-nullness - final Witness w = state.typeInfo(isNullNode.object()); - if (w != null && w.isNonNull()) { - removeFixedGuardNode(f, w.guard()); - return; - } - if (state.isNull(isNullNode.object())) { - markFixedGuardNodeAlwaysFails(f); - return; - } - // can't produce evidence, fall-through to addFact - } - } else if (cond instanceof InstanceOfNode) { - final InstanceOfNode iOf = (InstanceOfNode) cond; - final Witness w = state.typeInfo(iOf.object()); - if (isTrue) { - // grab an anchor attesting instanceof - if (w != null) { - if (w.isNonNull() && w.type() != null) { - if (iOf.type().isAssignableFrom(w.type())) { - removeFixedGuardNode(f, w.guard()); - return; - } - if (State.knownNotToConform(w.type(), iOf.type())) { - markFixedGuardNodeAlwaysFails(f); - return; - } - } - } - if (state.isNull(iOf.object())) { - markFixedGuardNodeAlwaysFails(f); - return; - } - // can't produce evidence, fall-through to addFact - } else { - // grab an anchor attesting not-instanceof - // (1 of 2) attempt determining nullness - final GuardingNode nullGuard = reasoner.nonTrivialNullAnchor(iOf.object()); - if (nullGuard != null) { - removeFixedGuardNode(f, nullGuard); - return; - } - // (2 of 2) attempt determining known-not-to-conform - if (w != null && !w.cluelessAboutType()) { - if (State.knownNotToConform(w.type(), iOf.type())) { - removeFixedGuardNode(f, w.guard()); - return; - } - } - // can't produce evidence, fall-through to addFact - } - } else if (isTrue && cond instanceof ShortCircuitOrNode) { - CastCheckExtractor cce = CastCheckExtractor.extract(cond); - if (cce != null && !State.isDependencyTainted(cce.subject, f)) { - // grab an anchor attesting check-cast - Witness w = state.typeInfo(cce.subject); - if (w != null && w.type() != null) { - if (cce.type.isAssignableFrom(w.type())) { - removeFixedGuardNode(f, w.guard()); - return; - } - if (State.knownNotToConform(w.type(), cce.type)) { - markFixedGuardNodeAlwaysFails(f); - return; - } - } - } - // can't produce evidence, fall-through to addFact + if (evidence.isPositive()) { + /* + * A FixedGuardNode can only be removed provided a replacement anchor is found (so + * called "evidence"), ie an anchor that amounts to the same combination of (negated, + * condition) as for the FixedGuardNode at hand. Just deverbosifying the condition in + * place isn't semantics-preserving. + * + * Eliminate the current FixedGuardNode by using another GuardingNode already in scope, + * a GuardingNode that guards a condition that is at least as strong as that of the + * FixedGuardNode. + */ + removeFixedGuardNode(f, evidence.success); + return; } - state.addFact(isTrue, cond, f); + assert evidence.isNegative(); + markFixedGuardNodeAlwaysFails(f); + } /** @@ -232,9 +145,7 @@ * </p> */ private void removeFixedGuardNode(FixedGuardNode old, GuardingNode replacement) { - if (replacement == null) { - return; - } + assert replacement != null; metricFixedGuardNodeRemoved.increment(); old.replaceAtUsages(replacement.asNode()); graph.removeFixed(old);
--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/State.java Mon May 05 18:39:09 2014 +0200 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/State.java Mon May 05 18:39:29 2014 +0200 @@ -423,6 +423,11 @@ assert !to.isPrimitive(); final ValueNode scrutinee = GraphUtil.unproxify(object); if (isNull(scrutinee)) { + // known-null means it conforms to whatever `to` + return false; + } + if (!isNonNull(scrutinee)) { + // unless `null` can be ruled out, a positive answer isn't safe return false; } ResolvedJavaType stampType = StampTool.typeOrNull(object); @@ -813,4 +818,178 @@ falseFacts.clear(); } + /** + * <p> + * If the argument is known null due to its stamp, there's no need to have an anchor for that + * fact and this method returns null. + * </p> + * + * <p> + * Otherwise, if an anchor is found it is returned, null otherwise. + * </p> + */ + public GuardingNode nonTrivialNullAnchor(ValueNode object) { + assert FlowUtil.hasLegalObjectStamp(object); + if (StampTool.isObjectAlwaysNull(object)) { + return null; + } + return knownNull.get(GraphUtil.unproxify(object)); + } + + /** + * This method: + * <ul> + * <li> + * attempts to find an existing {@link com.oracle.graal.nodes.extended.GuardingNode} that + * implies the property stated by the arguments. If found, returns it as positive evidence.</li> + * <li> + * otherwise, if the property of interest is known not to hold, negative evidence is returned.</li> + * <li> + * otherwise, null is returned.</li> + * </ul> + */ + public Evidence outcome(boolean isTrue, LogicNode cond) { + + // attempt to find an anchor for the condition of interest, verbatim + if (isTrue) { + GuardingNode existingGuard = trueFacts.get(cond); + if (existingGuard != null) { + return new Evidence(existingGuard); + } + if (falseFacts.containsKey(cond)) { + return Evidence.COUNTEREXAMPLE; + } + } else { + GuardingNode existingGuard = falseFacts.get(cond); + if (existingGuard != null) { + return new Evidence(existingGuard); + } + if (trueFacts.containsKey(cond)) { + return Evidence.COUNTEREXAMPLE; + } + } + + if (cond instanceof IsNullNode) { + return outcomeIsNullNode(isTrue, (IsNullNode) cond); + } + + if (cond instanceof InstanceOfNode) { + return outcomeInstanceOfNode(isTrue, (InstanceOfNode) cond); + } + + if (cond instanceof ShortCircuitOrNode) { + return outcomeShortCircuitOrNode(isTrue, (ShortCircuitOrNode) cond); + } + + // can't produce evidence + return null; + } + + /** + * Utility method for {@link #outcome(boolean, com.oracle.graal.nodes.LogicNode)} + */ + private Evidence outcomeIsNullNode(boolean isTrue, IsNullNode isNullNode) { + if (isTrue) { + // grab an anchor attesting nullness + final GuardingNode replacement = nonTrivialNullAnchor(isNullNode.object()); + if (replacement != null) { + return new Evidence(replacement); + } + if (isNonNull(isNullNode.object())) { + return Evidence.COUNTEREXAMPLE; + } + } else { + // grab an anchor attesting non-nullness + final Witness w = typeInfo(isNullNode.object()); + if (w != null && w.isNonNull()) { + return new Evidence(w.guard()); + } + if (isNull(isNullNode.object())) { + return Evidence.COUNTEREXAMPLE; + } + } + // can't produce evidence + return null; + } + + /** + * Utility method for {@link #outcome(boolean, com.oracle.graal.nodes.LogicNode)} + */ + private Evidence outcomeInstanceOfNode(boolean isTrue, InstanceOfNode iOf) { + final Witness w = typeInfo(iOf.object()); + if (isTrue) { + if (isNull(iOf.object())) { + return Evidence.COUNTEREXAMPLE; + } + // grab an anchor attesting instanceof + if ((w != null) && (w.type() != null)) { + if (w.isNonNull()) { + if (iOf.type().isAssignableFrom(w.type())) { + return new Evidence(w.guard()); + } + } + if (State.knownNotToConform(w.type(), iOf.type())) { + // null -> fails instanceof + // non-null but non-conformant -> also fails instanceof + return Evidence.COUNTEREXAMPLE; + } + } + } else { + // grab an anchor attesting not-instanceof + // (1 of 2) attempt determining nullness + final GuardingNode nullGuard = nonTrivialNullAnchor(iOf.object()); + if (nullGuard != null) { + return new Evidence(nullGuard); + } + // (2 of 2) attempt determining known-not-to-conform + if (w != null && !w.cluelessAboutType()) { + if (State.knownNotToConform(w.type(), iOf.type())) { + return new Evidence(w.guard()); + } + } + } + // can't produce evidence + return null; + } + + /** + * Utility method for {@link #outcome(boolean, com.oracle.graal.nodes.LogicNode)} + */ + private Evidence outcomeShortCircuitOrNode(boolean isTrue, ShortCircuitOrNode orNode) { + if (!isTrue) { + // too tricky to reason about + return null; + } + CastCheckExtractor cce = CastCheckExtractor.extract(orNode); + if (cce != null) { + // grab an anchor attesting check-cast + Witness w = typeInfo(cce.subject); + if (w != null && w.type() != null) { + if (cce.type.isAssignableFrom(w.type())) { + return new Evidence(w.guard()); + } + if (isNonNull(cce.subject) && State.knownNotToConform(w.type(), cce.type)) { + return Evidence.COUNTEREXAMPLE; + } + } + } + // search for positive-evidence for the first or-input + Evidence evidenceX = outcome(!orNode.isXNegated(), orNode.getX()); + if (evidenceX != null && evidenceX.isPositive()) { + return evidenceX; + } + // search for positive-evidence for the second or-input + Evidence evidenceY = outcome(!orNode.isYNegated(), orNode.getY()); + if (evidenceY != null && evidenceY.isPositive()) { + return evidenceY; + } + // check for contradictions on both or-inputs + if (evidenceX != null && evidenceY != null) { + assert evidenceX.isNegative() && evidenceY.isNegative(); + return Evidence.COUNTEREXAMPLE; + } + // can't produce evidence + return null; + } + }
--- a/mxtool/mx.py Mon May 05 18:39:09 2014 +0200 +++ b/mxtool/mx.py Mon May 05 18:39:29 2014 +0200 @@ -1300,8 +1300,21 @@ time.sleep(delay) # Makes the current subprocess accessible to the abort() function -# This is a tuple of the Popen object and args. -_currentSubprocess = (None, None) +# This is a list of tuples of the subprocess.Popen or +# multiprocessing.Process object and args. +_currentSubprocesses = [] + +def _addSubprocess(p, args): + entry = (p, args) + _currentSubprocesses.append(entry) + return entry + +def _removeSubprocess(entry): + if entry and entry in _currentSubprocesses: + try: + _currentSubprocesses.remove(entry) + except: + pass def waitOn(p): if get_os() == 'windows': @@ -1340,8 +1353,7 @@ if timeout is None and _opts.ptimeout != 0: timeout = _opts.ptimeout - global _currentSubprocess - + sub = None try: # On Unix, the new subprocess should be in a separate group so that a timeout alarm # can use os.killpg() to kill the whole subprocess group @@ -1359,7 +1371,7 @@ stdout = out if not callable(out) else subprocess.PIPE stderr = err if not callable(err) else subprocess.PIPE p = subprocess.Popen(args, cwd=cwd, stdout=stdout, stderr=stderr, preexec_fn=preexec_fn, creationflags=creationflags, env=env) - _currentSubprocess = (p, args) + sub = _addSubprocess(p, args) if callable(out): t = Thread(target=redirect, args=(p.stdout, out)) t.daemon = True # thread dies with the program @@ -1382,7 +1394,7 @@ except KeyboardInterrupt: abort(1) finally: - _currentSubprocess = (None, None) + _removeSubprocess(sub) if retcode and nonZeroIsFatal: if _opts.verbose: @@ -1663,21 +1675,20 @@ return result def _send_sigquit(): - p, args = _currentSubprocess - - def _isJava(): - if args: - name = args[0].split(os.sep)[-1] - return name == "java" - return False - - if p is not None and _isJava(): - if get_os() == 'windows': - log("mx: implement me! want to send SIGQUIT to my child process") - else: - _kill_process_group(p.pid, sig=signal.SIGQUIT) - time.sleep(0.1) - + for p, args in _currentSubprocesses: + + def _isJava(): + if args: + name = args[0].split(os.sep)[-1] + return name == "java" + return False + + if p is not None and _isJava(): + if get_os() == 'windows': + log("mx: implement me! want to send SIGQUIT to my child process") + else: + _kill_process_group(p.pid, sig=signal.SIGQUIT) + time.sleep(0.1) def abort(codeOrMessage): """ @@ -1692,12 +1703,14 @@ # import traceback # traceback.print_stack() - p, _ = _currentSubprocess - if p is not None: - if get_os() == 'windows': - p.kill() - else: - _kill_process_group(p.pid, signal.SIGKILL) + for p, args in _currentSubprocesses: + try: + if get_os() == 'windows': + p.terminate() + else: + _kill_process_group(p.pid, signal.SIGKILL) + except BaseException as e: + log('error while killing subprocess {} "{}": {}'.format(p.pid, ' '.join(args), e)) raise SystemExit(codeOrMessage) @@ -2113,6 +2126,7 @@ if t.proc.is_alive(): active.append(t) else: + _removeSubprocess(t.sub) if t.proc.exitcode != 0: return ([], joinTasks(tasks)) return (active, []) @@ -2126,10 +2140,18 @@ task._d = max([remainingDepsDepth(t) for t in incompleteDeps]) + 1 return task._d + def compareTasks(t1, t2): + d = remainingDepsDepth(t1) - remainingDepsDepth(t2) + if d == 0: + d = len(t1.proj.annotation_processors()) - len(t2.proj.annotation_processors()) + if d == 0: + d = len(t1.javafilelist) - len(t2.javafilelist) + return d + def sortWorklist(tasks): for t in tasks: t._d = None - return sorted(tasks, lambda x, y: remainingDepsDepth(x) - remainingDepsDepth(y)) + return sorted(tasks, compareTasks) import multiprocessing cpus = multiprocessing.cpu_count() @@ -2162,6 +2184,7 @@ task.proc = multiprocessing.Process(target=executeTask, args=(task,)) task.proc.start() active.append(task) + task.sub = _addSubprocess(task.proc, ['JavaCompileTask', str(task)]) if len(active) == cpus: break