Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(19)

Unified Diff: pkg/compiler/lib/src/cps_ir/constant_propagation.dart

Issue 693183006: Revert "Move dart2js from sdk/lib/_internal/compiler to pkg/compiler" (Closed) Base URL: https://dart.googlecode.com/svn/branches/bleeding_edge/dart
Patch Set: Created 6 years, 1 month ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
« no previous file with comments | « pkg/compiler/lib/src/constants/values.dart ('k') | pkg/compiler/lib/src/cps_ir/cps_ir_builder.dart » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: pkg/compiler/lib/src/cps_ir/constant_propagation.dart
diff --git a/pkg/compiler/lib/src/cps_ir/constant_propagation.dart b/pkg/compiler/lib/src/cps_ir/constant_propagation.dart
deleted file mode 100644
index 985cd279b8153b3c396327869f3f6a48c1013c5b..0000000000000000000000000000000000000000
--- a/pkg/compiler/lib/src/cps_ir/constant_propagation.dart
+++ /dev/null
@@ -1,666 +0,0 @@
-// Copyright (c) 2014, the Dart project authors. Please see the AUTHORS file
-// for details. All rights reserved. Use of this source code is governed by a
-// BSD-style license that can be found in the LICENSE file.
-
-part of dart2js.optimizers;
-
-/**
- * Propagates constants throughout the IR, and replaces branches with fixed
- * jumps as well as side-effect free expressions with known constant results.
- * Should be followed by the [ShrinkingReducer] pass.
- *
- * Implemented according to 'Constant Propagation with Conditional Branches'
- * by Wegman, Zadeck.
- */
-class ConstantPropagator implements Pass {
-
- // Required for type determination in analysis of TypeOperator expressions.
- final dart2js.Compiler _compiler;
-
- // The constant system is used for evaluation of expressions with constant
- // arguments.
- final dart2js.ConstantSystem _constantSystem;
-
- ConstantPropagator(this._compiler, this._constantSystem);
-
- void rewrite(FunctionDefinition root) {
- if (root.isAbstract) return;
-
- // Set all parent pointers.
-
- new _ParentVisitor().visit(root);
-
- // Analyze. In this phase, the entire term is analyzed for reachability
- // and the constant status of each expression.
-
- _ConstPropagationVisitor analyzer =
- new _ConstPropagationVisitor(_compiler, _constantSystem);
- analyzer.analyze(root);
-
- // Transform. Uses the data acquired in the previous analysis phase to
- // replace branches with fixed targets and side-effect-free expressions
- // with constant results.
-
- _TransformingVisitor transformer = new _TransformingVisitor(
- analyzer.reachableNodes, analyzer.node2value);
- transformer.transform(root);
- }
-}
-
-/**
- * Uses the information from a preceding analysis pass in order to perform the
- * actual transformations on the CPS graph.
- */
-class _TransformingVisitor extends RecursiveVisitor {
-
- final Set<Node> reachable;
- final Map<Node, _ConstnessLattice> node2value;
-
- _TransformingVisitor(this.reachable, this.node2value);
-
- void transform(FunctionDefinition root) {
- visitFunctionDefinition(root);
- }
-
- /// Given an expression with a known constant result and a continuation,
- /// replaces the expression by a new LetPrim / InvokeContinuation construct.
- /// `unlink` is a closure responsible for unlinking all removed references.
- LetPrim constifyExpression(Expression node,
- Continuation continuation,
- void unlink()) {
- _ConstnessLattice cell = node2value[node];
- if (cell == null || !cell.isConstant) {
- return null;
- }
-
- assert(continuation.parameters.length == 1);
-
- // Set up the replacement structure.
-
- PrimitiveConstantValue primitiveConstant = cell.constant;
- ConstantExpression constExp =
- new PrimitiveConstantExpression(primitiveConstant);
- Constant constant = new Constant(constExp);
- LetPrim letPrim = new LetPrim(constant);
- InvokeContinuation invoke =
- new InvokeContinuation(continuation, <Definition>[constant]);
-
- invoke.parent = constant.parent = letPrim;
- letPrim.body = invoke;
-
- // Replace the method invocation.
-
- InteriorNode parent = node.parent;
- letPrim.parent = parent;
- parent.body = letPrim;
-
- unlink();
-
- return letPrim;
- }
-
- // A branch can be eliminated and replaced by an invocation if only one of
- // the possible continuations is reachable. Removal often leads to both dead
- // primitives (the condition variable) and dead continuations (the unreachable
- // branch), which are both removed by the shrinking reductions pass.
- //
- // (Branch (IsTrue true) k0 k1) -> (InvokeContinuation k0)
- void visitBranch(Branch node) {
- bool trueReachable = reachable.contains(node.trueContinuation.definition);
- bool falseReachable = reachable.contains(node.falseContinuation.definition);
- bool bothReachable = (trueReachable && falseReachable);
- bool noneReachable = !(trueReachable || falseReachable);
-
- if (bothReachable || noneReachable) {
- // Nothing to do, shrinking reductions take care of the unreachable case.
- super.visitBranch(node);
- return;
- }
-
- Continuation successor = (trueReachable) ?
- node.trueContinuation.definition : node.falseContinuation.definition;
-
- // Replace the branch by a continuation invocation.
-
- assert(successor.parameters.isEmpty);
- InvokeContinuation invoke =
- new InvokeContinuation(successor, <Definition>[]);
-
- InteriorNode parent = node.parent;
- invoke.parent = parent;
- parent.body = invoke;
-
- // Unlink all removed references.
-
- node.trueContinuation.unlink();
- node.falseContinuation.unlink();
- IsTrue isTrue = node.condition;
- isTrue.value.unlink();
-
- visitInvokeContinuation(invoke);
- }
-
- // Side-effect free method calls with constant results can be replaced by
- // a LetPrim / InvokeContinuation pair. May lead to dead primitives which
- // are removed by the shrinking reductions pass.
- //
- // (InvokeMethod v0 == v1 k0)
- // -> (assuming the result is a constant `true`)
- // (LetPrim v2 (Constant true))
- // (InvokeContinuation k0 v2)
- void visitInvokeMethod(InvokeMethod node) {
- Continuation cont = node.continuation.definition;
- LetPrim letPrim = constifyExpression(node, cont, () {
- node.receiver.unlink();
- node.continuation.unlink();
- node.arguments.forEach((Reference ref) => ref.unlink());
- });
-
- if (letPrim == null) {
- super.visitInvokeMethod(node);
- } else {
- visitLetPrim(letPrim);
- }
- }
-
- // See [visitInvokeMethod].
- void visitConcatenateStrings(ConcatenateStrings node) {
- Continuation cont = node.continuation.definition;
- LetPrim letPrim = constifyExpression(node, cont, () {
- node.continuation.unlink();
- node.arguments.forEach((Reference ref) => ref.unlink());
- });
-
- if (letPrim == null) {
- super.visitConcatenateStrings(node);
- } else {
- visitLetPrim(letPrim);
- }
- }
-
- // See [visitInvokeMethod].
- void visitTypeOperator(TypeOperator node) {
- Continuation cont = node.continuation.definition;
- LetPrim letPrim = constifyExpression(node, cont, () {
- node.receiver.unlink();
- node.continuation.unlink();
- });
-
- if (letPrim == null) {
- super.visitTypeOperator(node);
- } else {
- visitLetPrim(letPrim);
- }
- }
-}
-
-/**
- * Runs an analysis pass on the given function definition in order to detect
- * const-ness as well as reachability, both of which are used in the subsequent
- * transformation pass.
- */
-class _ConstPropagationVisitor extends Visitor {
- // The node worklist stores nodes that are both reachable and need to be
- // processed, but have not been processed yet. Using a worklist avoids deep
- // recursion.
- // The node worklist and the reachable set operate in concert: nodes are
- // only ever added to the worklist when they have not yet been marked as
- // reachable, and adding a node to the worklist is always followed by marking
- // it reachable.
- // TODO(jgruber): Storing reachability per-edge instead of per-node would
- // allow for further optimizations.
- final List<Node> nodeWorklist = <Node>[];
- final Set<Node> reachableNodes = new Set<Node>();
-
- // The definition workset stores all definitions which need to be reprocessed
- // since their lattice value has changed.
- final Set<Definition> defWorkset = new Set<Definition>();
-
- final dart2js.Compiler compiler;
- final dart2js.ConstantSystem constantSystem;
-
- // Stores the current lattice value for nodes. Note that it contains not only
- // definitions as keys, but also expressions such as method invokes.
- // Access through [getValue] and [setValue].
- final Map<Node, _ConstnessLattice> node2value = <Node, _ConstnessLattice>{};
-
- _ConstPropagationVisitor(this.compiler, this.constantSystem);
-
- void analyze(FunctionDefinition root) {
- reachableNodes.clear();
- defWorkset.clear();
- nodeWorklist.clear();
-
- // Initially, only the root node is reachable.
- setReachable(root);
-
- while (true) {
- if (nodeWorklist.isNotEmpty) {
- // Process a new reachable expression.
- Node node = nodeWorklist.removeLast();
- visit(node);
- } else if (defWorkset.isNotEmpty) {
- // Process all usages of a changed definition.
- Definition def = defWorkset.first;
- defWorkset.remove(def);
-
- // Visit all uses of this definition. This might add new entries to
- // [nodeWorklist], for example by visiting a newly-constant usage within
- // a branch node.
- for (Reference ref = def.firstRef; ref != null; ref = ref.next) {
- visit(ref.parent);
- }
- } else {
- break; // Both worklists empty.
- }
- }
- }
-
- /// If the passed node is not yet reachable, mark it reachable and add it
- /// to the work list.
- void setReachable(Node node) {
- if (!reachableNodes.contains(node)) {
- reachableNodes.add(node);
- nodeWorklist.add(node);
- }
- }
-
- /// Returns the lattice value corresponding to [node], defaulting to unknown.
- ///
- /// Never returns null.
- _ConstnessLattice getValue(Node node) {
- _ConstnessLattice value = node2value[node];
- return (value == null) ? _ConstnessLattice.Unknown : value;
- }
-
- /// Joins the passed lattice [updateValue] to the current value of [node],
- /// and adds it to the definition work set if it has changed and [node] is
- /// a definition.
- void setValue(Node node, _ConstnessLattice updateValue) {
- _ConstnessLattice oldValue = getValue(node);
- _ConstnessLattice newValue = updateValue.join(oldValue);
- if (oldValue == newValue) {
- return;
- }
-
- // Values may only move in the direction UNKNOWN -> CONSTANT -> NONCONST.
- assert(newValue.kind >= oldValue.kind);
-
- node2value[node] = newValue;
- if (node is Definition) {
- defWorkset.add(node);
- }
- }
-
- // -------------------------- Visitor overrides ------------------------------
-
- void visitNode(Node node) {
- compiler.internalError(NO_LOCATION_SPANNABLE,
- "_ConstPropagationVisitor is stale, add missing visit overrides");
- }
-
- void visitFunctionDefinition(FunctionDefinition node) {
- node.parameters.forEach(visitParameter);
- setReachable(node.body);
- }
-
- // Expressions.
-
- void visitLetPrim(LetPrim node) {
- visit(node.primitive); // No reason to delay visits to primitives.
- setReachable(node.body);
- }
-
- void visitLetCont(LetCont node) {
- // The continuation is only marked as reachable on use.
- setReachable(node.body);
- }
-
- void visitInvokeStatic(InvokeStatic node) {
- Continuation cont = node.continuation.definition;
- setReachable(cont);
-
- assert(cont.parameters.length == 1);
- Parameter returnValue = cont.parameters[0];
- setValue(returnValue, _ConstnessLattice.NonConst);
- }
-
- void visitInvokeContinuation(InvokeContinuation node) {
- Continuation cont = node.continuation.definition;
- setReachable(cont);
-
- // Forward the constant status of all continuation invokes to the
- // continuation. Note that this is effectively a phi node in SSA terms.
- for (int i = 0; i < node.arguments.length; i++) {
- Definition def = node.arguments[i].definition;
- _ConstnessLattice cell = getValue(def);
- setValue(cont.parameters[i], cell);
- }
- }
-
- void visitInvokeMethod(InvokeMethod node) {
- Continuation cont = node.continuation.definition;
- setReachable(cont);
-
- /// Sets the value of both the current node and the target continuation
- /// parameter.
- void setValues(_ConstnessLattice updateValue) {
- setValue(node, updateValue);
- Parameter returnValue = cont.parameters[0];
- setValue(returnValue, updateValue);
- }
-
- _ConstnessLattice lhs = getValue(node.receiver.definition);
- if (lhs.isUnknown) {
- // This may seem like a missed opportunity for evaluating short-circuiting
- // boolean operations; we are currently skipping these intentionally since
- // expressions such as `(new Foo() || true)` may introduce type errors
- // and thus evaluation to `true` would not be correct.
- // TODO(jgruber): Handle such cases while ensuring that new Foo() and
- // a type-check (in checked mode) are still executed.
- return; // And come back later.
- } else if (lhs.isNonConst) {
- setValues(_ConstnessLattice.NonConst);
- return;
- } else if (!node.selector.isOperator) {
- // TODO(jgruber): Handle known methods on constants such as String.length.
- setValues(_ConstnessLattice.NonConst);
- return;
- }
-
- // Calculate the resulting constant if possible.
- ConstantValue result;
- String opname = node.selector.name;
- if (node.selector.argumentCount == 0) {
- // Unary operator.
-
- if (opname == "unary-") {
- opname = "-";
- }
- dart2js.UnaryOperation operation = constantSystem.lookupUnary(opname);
- if (operation != null) {
- result = operation.fold(lhs.constant);
- }
- } else if (node.selector.argumentCount == 1) {
- // Binary operator.
-
- _ConstnessLattice rhs = getValue(node.arguments[0].definition);
- if (!rhs.isConstant) {
- setValues(rhs);
- return;
- }
-
- dart2js.BinaryOperation operation = constantSystem.lookupBinary(opname);
- if (operation != null) {
- result = operation.fold(lhs.constant, rhs.constant);
- }
- }
-
- // Update value of the continuation parameter. Again, this is effectively
- // a phi.
-
- setValues((result == null) ?
- _ConstnessLattice.NonConst : new _ConstnessLattice(result));
- }
-
- void visitInvokeSuperMethod(InvokeSuperMethod node) {
- Continuation cont = node.continuation.definition;
- setReachable(cont);
-
- assert(cont.parameters.length == 1);
- Parameter returnValue = cont.parameters[0];
- setValue(returnValue, _ConstnessLattice.NonConst);
- }
-
- void visitInvokeConstructor(InvokeConstructor node) {
- Continuation cont = node.continuation.definition;
- setReachable(cont);
-
- assert(cont.parameters.length == 1);
- Parameter returnValue = cont.parameters[0];
- setValue(returnValue, _ConstnessLattice.NonConst);
- }
-
- void visitConcatenateStrings(ConcatenateStrings node) {
- Continuation cont = node.continuation.definition;
- setReachable(cont);
-
- void setValues(_ConstnessLattice updateValue) {
- setValue(node, updateValue);
- Parameter returnValue = cont.parameters[0];
- setValue(returnValue, updateValue);
- }
-
- // TODO(jgruber): Currently we only optimize if all arguments are string
- // constants, but we could also handle cases such as "foo${42}".
- bool allStringConstants = node.arguments.every((Reference ref) {
- if (!(ref.definition is Constant)) {
- return false;
- }
- Constant constant = ref.definition;
- return constant != null && constant.value.isString;
- });
-
- assert(cont.parameters.length == 1);
- if (allStringConstants) {
- // All constant, we can concatenate ourselves.
- Iterable<String> allStrings = node.arguments.map((Reference ref) {
- Constant constant = ref.definition;
- StringConstantValue stringConstant = constant.value;
- return stringConstant.primitiveValue.slowToString();
- });
- LiteralDartString dartString = new LiteralDartString(allStrings.join());
- ConstantValue constant = new StringConstantValue(dartString);
- setValues(new _ConstnessLattice(constant));
- } else {
- setValues(_ConstnessLattice.NonConst);
- }
- }
-
- void visitBranch(Branch node) {
- IsTrue isTrue = node.condition;
- _ConstnessLattice conditionCell = getValue(isTrue.value.definition);
-
- if (conditionCell.isUnknown) {
- return; // And come back later.
- } else if (conditionCell.isNonConst) {
- setReachable(node.trueContinuation.definition);
- setReachable(node.falseContinuation.definition);
- } else if (conditionCell.isConstant &&
- !(conditionCell.constant.isBool)) {
- // Treat non-bool constants in condition as non-const since they result
- // in type errors in checked mode.
- // TODO(jgruber): Default to false in unchecked mode.
- setReachable(node.trueContinuation.definition);
- setReachable(node.falseContinuation.definition);
- setValue(isTrue.value.definition, _ConstnessLattice.NonConst);
- } else if (conditionCell.isConstant &&
- conditionCell.constant.isBool) {
- BoolConstantValue boolConstant = conditionCell.constant;
- setReachable((boolConstant.isTrue) ?
- node.trueContinuation.definition : node.falseContinuation.definition);
- }
- }
-
- void visitTypeOperator(TypeOperator node) {
- Continuation cont = node.continuation.definition;
- setReachable(cont);
-
- void setValues(_ConstnessLattice updateValue) {
- setValue(node, updateValue);
- Parameter returnValue = cont.parameters[0];
- setValue(returnValue, updateValue);
- }
-
- if (node.isTypeCast) {
- // TODO(jgruber): Add support for `as` casts.
- setValues(_ConstnessLattice.NonConst);
- }
-
- _ConstnessLattice cell = getValue(node.receiver.definition);
- if (cell.isUnknown) {
- return; // And come back later.
- } else if (cell.isNonConst) {
- setValues(_ConstnessLattice.NonConst);
- } else if (node.type.kind == types.TypeKind.INTERFACE) {
- // Receiver is a constant, perform is-checks at compile-time.
-
- types.InterfaceType checkedType = node.type;
- ConstantValue constant = cell.constant;
- types.DartType constantType = constant.computeType(compiler);
-
- _ConstnessLattice result = _ConstnessLattice.NonConst;
- if (constant.isNull &&
- checkedType.element != compiler.nullClass &&
- checkedType.element != compiler.objectClass) {
- // `(null is Type)` is true iff Type is in { Null, Object }.
- result = new _ConstnessLattice(new FalseConstantValue());
- } else {
- // Otherwise, perform a standard subtype check.
- result = new _ConstnessLattice(
- constantSystem.isSubtype(compiler, constantType, checkedType)
- ? new TrueConstantValue()
- : new FalseConstantValue());
- }
-
- setValues(result);
- }
- }
-
- void visitSetClosureVariable(SetClosureVariable node) {
- setReachable(node.body);
- }
-
- void visitDeclareFunction(DeclareFunction node) {
- setReachable(node.definition);
- setReachable(node.body);
- }
-
- // Definitions.
- void visitLiteralList(LiteralList node) {
- // Constant lists are translated into (Constant ListConstant(...)) IR nodes,
- // and thus LiteralList nodes are NonConst.
- setValue(node, _ConstnessLattice.NonConst);
- }
-
- void visitLiteralMap(LiteralMap node) {
- // Constant maps are translated into (Constant MapConstant(...)) IR nodes,
- // and thus LiteralMap nodes are NonConst.
- setValue(node, _ConstnessLattice.NonConst);
- }
-
- void visitConstant(Constant node) {
- setValue(node, new _ConstnessLattice(node.value));
- }
-
- void visitThis(This node) {
- setValue(node, _ConstnessLattice.NonConst);
- }
-
- void visitReifyTypeVar(ReifyTypeVar node) {
- setValue(node, _ConstnessLattice.NonConst);
- }
-
- void visitCreateFunction(CreateFunction node) {
- setReachable(node.definition);
- ConstantValue constant =
- new FunctionConstantValue(node.definition.element);
- setValue(node, new _ConstnessLattice(constant));
- }
-
- void visitGetClosureVariable(GetClosureVariable node) {
- setValue(node, _ConstnessLattice.NonConst);
- }
-
- void visitParameter(Parameter node) {
- if (node.parent is FunctionDefinition) {
- // Functions may escape and thus their parameters must be initialized to
- // NonConst.
- setValue(node, _ConstnessLattice.NonConst);
- } else if (node.parent is Continuation) {
- // Continuations on the other hand are local, and parameters are
- // initialized to Unknown.
- setValue(node, _ConstnessLattice.Unknown);
- } else {
- compiler.internalError(node.hint, "Unexpected parent of Parameter");
- }
- }
-
- void visitContinuation(Continuation node) {
- node.parameters.forEach((Parameter p) {
- setValue(p, _ConstnessLattice.Unknown);
- defWorkset.add(p);
- });
-
- if (node.body != null) {
- setReachable(node.body);
- }
- }
-
- // Conditions.
-
- void visitIsTrue(IsTrue node) {
- Branch branch = node.parent;
- visitBranch(branch);
- }
-}
-
-/// Represents the constant-state of a variable at some point in the program.
-/// UNKNOWN: may be some as yet undetermined constant.
-/// CONSTANT: is a constant as stored in the local field.
-/// NONCONST: not a constant.
-class _ConstnessLattice {
- static const int UNKNOWN = 0;
- static const int CONSTANT = 1;
- static const int NONCONST = 2;
-
- final int kind;
- final ConstantValue constant;
-
- static final _ConstnessLattice Unknown =
- new _ConstnessLattice._internal(UNKNOWN, null);
- static final _ConstnessLattice NonConst =
- new _ConstnessLattice._internal(NONCONST, null);
-
- _ConstnessLattice._internal(this.kind, this.constant);
- _ConstnessLattice(this.constant) : kind = CONSTANT {
- assert(this.constant != null);
- }
-
- bool get isUnknown => (kind == UNKNOWN);
- bool get isConstant => (kind == CONSTANT);
- bool get isNonConst => (kind == NONCONST);
-
- int get hashCode => kind | (constant.hashCode << 2);
- bool operator==(_ConstnessLattice that) =>
- (that.kind == this.kind && that.constant == this.constant);
-
- String toString() {
- switch (kind) {
- case UNKNOWN: return "Unknown";
- case CONSTANT: return "Constant: $constant";
- case NONCONST: return "Non-constant";
- default: assert(false);
- }
- return null;
- }
-
- /// Compute the join of two values in the lattice.
- _ConstnessLattice join(_ConstnessLattice that) {
- assert(that != null);
-
- if (this.isNonConst || that.isUnknown) {
- return this;
- }
-
- if (this.isUnknown || that.isNonConst) {
- return that;
- }
-
- if (this.constant == that.constant) {
- return this;
- }
-
- return NonConst;
- }
-}
« no previous file with comments | « pkg/compiler/lib/src/constants/values.dart ('k') | pkg/compiler/lib/src/cps_ir/cps_ir_builder.dart » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698