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

Side by Side Diff: sdk/lib/_internal/compiler/implementation/cps_ir/constant_propagation.dart

Issue 694353007: 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 unified diff | Download patch | Annotate | Revision Log
OLDNEW
(Empty)
1 // Copyright (c) 2014, the Dart project authors. Please see the AUTHORS file
2 // for details. All rights reserved. Use of this source code is governed by a
3 // BSD-style license that can be found in the LICENSE file.
4
5 part of dart2js.optimizers;
6
7 /**
8 * Propagates constants throughout the IR, and replaces branches with fixed
9 * jumps as well as side-effect free expressions with known constant results.
10 * Should be followed by the [ShrinkingReducer] pass.
11 *
12 * Implemented according to 'Constant Propagation with Conditional Branches'
13 * by Wegman, Zadeck.
14 */
15 class ConstantPropagator implements Pass {
16
17 // Required for type determination in analysis of TypeOperator expressions.
18 final dart2js.Compiler _compiler;
19
20 // The constant system is used for evaluation of expressions with constant
21 // arguments.
22 final dart2js.ConstantSystem _constantSystem;
23
24 ConstantPropagator(this._compiler, this._constantSystem);
25
26 void rewrite(FunctionDefinition root) {
27 if (root.isAbstract) return;
28
29 // Set all parent pointers.
30
31 new _ParentVisitor().visit(root);
32
33 // Analyze. In this phase, the entire term is analyzed for reachability
34 // and the constant status of each expression.
35
36 _ConstPropagationVisitor analyzer =
37 new _ConstPropagationVisitor(_compiler, _constantSystem);
38 analyzer.analyze(root);
39
40 // Transform. Uses the data acquired in the previous analysis phase to
41 // replace branches with fixed targets and side-effect-free expressions
42 // with constant results.
43
44 _TransformingVisitor transformer = new _TransformingVisitor(
45 analyzer.reachableNodes, analyzer.node2value);
46 transformer.transform(root);
47 }
48 }
49
50 /**
51 * Uses the information from a preceding analysis pass in order to perform the
52 * actual transformations on the CPS graph.
53 */
54 class _TransformingVisitor extends RecursiveVisitor {
55
56 final Set<Node> reachable;
57 final Map<Node, _ConstnessLattice> node2value;
58
59 _TransformingVisitor(this.reachable, this.node2value);
60
61 void transform(FunctionDefinition root) {
62 visitFunctionDefinition(root);
63 }
64
65 /// Given an expression with a known constant result and a continuation,
66 /// replaces the expression by a new LetPrim / InvokeContinuation construct.
67 /// `unlink` is a closure responsible for unlinking all removed references.
68 LetPrim constifyExpression(Expression node,
69 Continuation continuation,
70 void unlink()) {
71 _ConstnessLattice cell = node2value[node];
72 if (cell == null || !cell.isConstant) {
73 return null;
74 }
75
76 assert(continuation.parameters.length == 1);
77
78 // Set up the replacement structure.
79
80 PrimitiveConstantValue primitiveConstant = cell.constant;
81 ConstantExpression constExp =
82 new PrimitiveConstantExpression(primitiveConstant);
83 Constant constant = new Constant(constExp);
84 LetPrim letPrim = new LetPrim(constant);
85 InvokeContinuation invoke =
86 new InvokeContinuation(continuation, <Definition>[constant]);
87
88 invoke.parent = constant.parent = letPrim;
89 letPrim.body = invoke;
90
91 // Replace the method invocation.
92
93 InteriorNode parent = node.parent;
94 letPrim.parent = parent;
95 parent.body = letPrim;
96
97 unlink();
98
99 return letPrim;
100 }
101
102 // A branch can be eliminated and replaced by an invocation if only one of
103 // the possible continuations is reachable. Removal often leads to both dead
104 // primitives (the condition variable) and dead continuations (the unreachable
105 // branch), which are both removed by the shrinking reductions pass.
106 //
107 // (Branch (IsTrue true) k0 k1) -> (InvokeContinuation k0)
108 void visitBranch(Branch node) {
109 bool trueReachable = reachable.contains(node.trueContinuation.definition);
110 bool falseReachable = reachable.contains(node.falseContinuation.definition);
111 bool bothReachable = (trueReachable && falseReachable);
112 bool noneReachable = !(trueReachable || falseReachable);
113
114 if (bothReachable || noneReachable) {
115 // Nothing to do, shrinking reductions take care of the unreachable case.
116 super.visitBranch(node);
117 return;
118 }
119
120 Continuation successor = (trueReachable) ?
121 node.trueContinuation.definition : node.falseContinuation.definition;
122
123 // Replace the branch by a continuation invocation.
124
125 assert(successor.parameters.isEmpty);
126 InvokeContinuation invoke =
127 new InvokeContinuation(successor, <Definition>[]);
128
129 InteriorNode parent = node.parent;
130 invoke.parent = parent;
131 parent.body = invoke;
132
133 // Unlink all removed references.
134
135 node.trueContinuation.unlink();
136 node.falseContinuation.unlink();
137 IsTrue isTrue = node.condition;
138 isTrue.value.unlink();
139
140 visitInvokeContinuation(invoke);
141 }
142
143 // Side-effect free method calls with constant results can be replaced by
144 // a LetPrim / InvokeContinuation pair. May lead to dead primitives which
145 // are removed by the shrinking reductions pass.
146 //
147 // (InvokeMethod v0 == v1 k0)
148 // -> (assuming the result is a constant `true`)
149 // (LetPrim v2 (Constant true))
150 // (InvokeContinuation k0 v2)
151 void visitInvokeMethod(InvokeMethod node) {
152 Continuation cont = node.continuation.definition;
153 LetPrim letPrim = constifyExpression(node, cont, () {
154 node.receiver.unlink();
155 node.continuation.unlink();
156 node.arguments.forEach((Reference ref) => ref.unlink());
157 });
158
159 if (letPrim == null) {
160 super.visitInvokeMethod(node);
161 } else {
162 visitLetPrim(letPrim);
163 }
164 }
165
166 // See [visitInvokeMethod].
167 void visitConcatenateStrings(ConcatenateStrings node) {
168 Continuation cont = node.continuation.definition;
169 LetPrim letPrim = constifyExpression(node, cont, () {
170 node.continuation.unlink();
171 node.arguments.forEach((Reference ref) => ref.unlink());
172 });
173
174 if (letPrim == null) {
175 super.visitConcatenateStrings(node);
176 } else {
177 visitLetPrim(letPrim);
178 }
179 }
180
181 // See [visitInvokeMethod].
182 void visitTypeOperator(TypeOperator node) {
183 Continuation cont = node.continuation.definition;
184 LetPrim letPrim = constifyExpression(node, cont, () {
185 node.receiver.unlink();
186 node.continuation.unlink();
187 });
188
189 if (letPrim == null) {
190 super.visitTypeOperator(node);
191 } else {
192 visitLetPrim(letPrim);
193 }
194 }
195 }
196
197 /**
198 * Runs an analysis pass on the given function definition in order to detect
199 * const-ness as well as reachability, both of which are used in the subsequent
200 * transformation pass.
201 */
202 class _ConstPropagationVisitor extends Visitor {
203 // The node worklist stores nodes that are both reachable and need to be
204 // processed, but have not been processed yet. Using a worklist avoids deep
205 // recursion.
206 // The node worklist and the reachable set operate in concert: nodes are
207 // only ever added to the worklist when they have not yet been marked as
208 // reachable, and adding a node to the worklist is always followed by marking
209 // it reachable.
210 // TODO(jgruber): Storing reachability per-edge instead of per-node would
211 // allow for further optimizations.
212 final List<Node> nodeWorklist = <Node>[];
213 final Set<Node> reachableNodes = new Set<Node>();
214
215 // The definition workset stores all definitions which need to be reprocessed
216 // since their lattice value has changed.
217 final Set<Definition> defWorkset = new Set<Definition>();
218
219 final dart2js.Compiler compiler;
220 final dart2js.ConstantSystem constantSystem;
221
222 // Stores the current lattice value for nodes. Note that it contains not only
223 // definitions as keys, but also expressions such as method invokes.
224 // Access through [getValue] and [setValue].
225 final Map<Node, _ConstnessLattice> node2value = <Node, _ConstnessLattice>{};
226
227 _ConstPropagationVisitor(this.compiler, this.constantSystem);
228
229 void analyze(FunctionDefinition root) {
230 reachableNodes.clear();
231 defWorkset.clear();
232 nodeWorklist.clear();
233
234 // Initially, only the root node is reachable.
235 setReachable(root);
236
237 while (true) {
238 if (nodeWorklist.isNotEmpty) {
239 // Process a new reachable expression.
240 Node node = nodeWorklist.removeLast();
241 visit(node);
242 } else if (defWorkset.isNotEmpty) {
243 // Process all usages of a changed definition.
244 Definition def = defWorkset.first;
245 defWorkset.remove(def);
246
247 // Visit all uses of this definition. This might add new entries to
248 // [nodeWorklist], for example by visiting a newly-constant usage within
249 // a branch node.
250 for (Reference ref = def.firstRef; ref != null; ref = ref.next) {
251 visit(ref.parent);
252 }
253 } else {
254 break; // Both worklists empty.
255 }
256 }
257 }
258
259 /// If the passed node is not yet reachable, mark it reachable and add it
260 /// to the work list.
261 void setReachable(Node node) {
262 if (!reachableNodes.contains(node)) {
263 reachableNodes.add(node);
264 nodeWorklist.add(node);
265 }
266 }
267
268 /// Returns the lattice value corresponding to [node], defaulting to unknown.
269 ///
270 /// Never returns null.
271 _ConstnessLattice getValue(Node node) {
272 _ConstnessLattice value = node2value[node];
273 return (value == null) ? _ConstnessLattice.Unknown : value;
274 }
275
276 /// Joins the passed lattice [updateValue] to the current value of [node],
277 /// and adds it to the definition work set if it has changed and [node] is
278 /// a definition.
279 void setValue(Node node, _ConstnessLattice updateValue) {
280 _ConstnessLattice oldValue = getValue(node);
281 _ConstnessLattice newValue = updateValue.join(oldValue);
282 if (oldValue == newValue) {
283 return;
284 }
285
286 // Values may only move in the direction UNKNOWN -> CONSTANT -> NONCONST.
287 assert(newValue.kind >= oldValue.kind);
288
289 node2value[node] = newValue;
290 if (node is Definition) {
291 defWorkset.add(node);
292 }
293 }
294
295 // -------------------------- Visitor overrides ------------------------------
296
297 void visitNode(Node node) {
298 compiler.internalError(NO_LOCATION_SPANNABLE,
299 "_ConstPropagationVisitor is stale, add missing visit overrides");
300 }
301
302 void visitFunctionDefinition(FunctionDefinition node) {
303 node.parameters.forEach(visitParameter);
304 setReachable(node.body);
305 }
306
307 // Expressions.
308
309 void visitLetPrim(LetPrim node) {
310 visit(node.primitive); // No reason to delay visits to primitives.
311 setReachable(node.body);
312 }
313
314 void visitLetCont(LetCont node) {
315 // The continuation is only marked as reachable on use.
316 setReachable(node.body);
317 }
318
319 void visitInvokeStatic(InvokeStatic node) {
320 Continuation cont = node.continuation.definition;
321 setReachable(cont);
322
323 assert(cont.parameters.length == 1);
324 Parameter returnValue = cont.parameters[0];
325 setValue(returnValue, _ConstnessLattice.NonConst);
326 }
327
328 void visitInvokeContinuation(InvokeContinuation node) {
329 Continuation cont = node.continuation.definition;
330 setReachable(cont);
331
332 // Forward the constant status of all continuation invokes to the
333 // continuation. Note that this is effectively a phi node in SSA terms.
334 for (int i = 0; i < node.arguments.length; i++) {
335 Definition def = node.arguments[i].definition;
336 _ConstnessLattice cell = getValue(def);
337 setValue(cont.parameters[i], cell);
338 }
339 }
340
341 void visitInvokeMethod(InvokeMethod node) {
342 Continuation cont = node.continuation.definition;
343 setReachable(cont);
344
345 /// Sets the value of both the current node and the target continuation
346 /// parameter.
347 void setValues(_ConstnessLattice updateValue) {
348 setValue(node, updateValue);
349 Parameter returnValue = cont.parameters[0];
350 setValue(returnValue, updateValue);
351 }
352
353 _ConstnessLattice lhs = getValue(node.receiver.definition);
354 if (lhs.isUnknown) {
355 // This may seem like a missed opportunity for evaluating short-circuiting
356 // boolean operations; we are currently skipping these intentionally since
357 // expressions such as `(new Foo() || true)` may introduce type errors
358 // and thus evaluation to `true` would not be correct.
359 // TODO(jgruber): Handle such cases while ensuring that new Foo() and
360 // a type-check (in checked mode) are still executed.
361 return; // And come back later.
362 } else if (lhs.isNonConst) {
363 setValues(_ConstnessLattice.NonConst);
364 return;
365 } else if (!node.selector.isOperator) {
366 // TODO(jgruber): Handle known methods on constants such as String.length.
367 setValues(_ConstnessLattice.NonConst);
368 return;
369 }
370
371 // Calculate the resulting constant if possible.
372 ConstantValue result;
373 String opname = node.selector.name;
374 if (node.selector.argumentCount == 0) {
375 // Unary operator.
376
377 if (opname == "unary-") {
378 opname = "-";
379 }
380 dart2js.UnaryOperation operation = constantSystem.lookupUnary(opname);
381 if (operation != null) {
382 result = operation.fold(lhs.constant);
383 }
384 } else if (node.selector.argumentCount == 1) {
385 // Binary operator.
386
387 _ConstnessLattice rhs = getValue(node.arguments[0].definition);
388 if (!rhs.isConstant) {
389 setValues(rhs);
390 return;
391 }
392
393 dart2js.BinaryOperation operation = constantSystem.lookupBinary(opname);
394 if (operation != null) {
395 result = operation.fold(lhs.constant, rhs.constant);
396 }
397 }
398
399 // Update value of the continuation parameter. Again, this is effectively
400 // a phi.
401
402 setValues((result == null) ?
403 _ConstnessLattice.NonConst : new _ConstnessLattice(result));
404 }
405
406 void visitInvokeSuperMethod(InvokeSuperMethod node) {
407 Continuation cont = node.continuation.definition;
408 setReachable(cont);
409
410 assert(cont.parameters.length == 1);
411 Parameter returnValue = cont.parameters[0];
412 setValue(returnValue, _ConstnessLattice.NonConst);
413 }
414
415 void visitInvokeConstructor(InvokeConstructor node) {
416 Continuation cont = node.continuation.definition;
417 setReachable(cont);
418
419 assert(cont.parameters.length == 1);
420 Parameter returnValue = cont.parameters[0];
421 setValue(returnValue, _ConstnessLattice.NonConst);
422 }
423
424 void visitConcatenateStrings(ConcatenateStrings node) {
425 Continuation cont = node.continuation.definition;
426 setReachable(cont);
427
428 void setValues(_ConstnessLattice updateValue) {
429 setValue(node, updateValue);
430 Parameter returnValue = cont.parameters[0];
431 setValue(returnValue, updateValue);
432 }
433
434 // TODO(jgruber): Currently we only optimize if all arguments are string
435 // constants, but we could also handle cases such as "foo${42}".
436 bool allStringConstants = node.arguments.every((Reference ref) {
437 if (!(ref.definition is Constant)) {
438 return false;
439 }
440 Constant constant = ref.definition;
441 return constant != null && constant.value.isString;
442 });
443
444 assert(cont.parameters.length == 1);
445 if (allStringConstants) {
446 // All constant, we can concatenate ourselves.
447 Iterable<String> allStrings = node.arguments.map((Reference ref) {
448 Constant constant = ref.definition;
449 StringConstantValue stringConstant = constant.value;
450 return stringConstant.primitiveValue.slowToString();
451 });
452 LiteralDartString dartString = new LiteralDartString(allStrings.join());
453 ConstantValue constant = new StringConstantValue(dartString);
454 setValues(new _ConstnessLattice(constant));
455 } else {
456 setValues(_ConstnessLattice.NonConst);
457 }
458 }
459
460 void visitBranch(Branch node) {
461 IsTrue isTrue = node.condition;
462 _ConstnessLattice conditionCell = getValue(isTrue.value.definition);
463
464 if (conditionCell.isUnknown) {
465 return; // And come back later.
466 } else if (conditionCell.isNonConst) {
467 setReachable(node.trueContinuation.definition);
468 setReachable(node.falseContinuation.definition);
469 } else if (conditionCell.isConstant &&
470 !(conditionCell.constant.isBool)) {
471 // Treat non-bool constants in condition as non-const since they result
472 // in type errors in checked mode.
473 // TODO(jgruber): Default to false in unchecked mode.
474 setReachable(node.trueContinuation.definition);
475 setReachable(node.falseContinuation.definition);
476 setValue(isTrue.value.definition, _ConstnessLattice.NonConst);
477 } else if (conditionCell.isConstant &&
478 conditionCell.constant.isBool) {
479 BoolConstantValue boolConstant = conditionCell.constant;
480 setReachable((boolConstant.isTrue) ?
481 node.trueContinuation.definition : node.falseContinuation.definition);
482 }
483 }
484
485 void visitTypeOperator(TypeOperator node) {
486 Continuation cont = node.continuation.definition;
487 setReachable(cont);
488
489 void setValues(_ConstnessLattice updateValue) {
490 setValue(node, updateValue);
491 Parameter returnValue = cont.parameters[0];
492 setValue(returnValue, updateValue);
493 }
494
495 if (node.isTypeCast) {
496 // TODO(jgruber): Add support for `as` casts.
497 setValues(_ConstnessLattice.NonConst);
498 }
499
500 _ConstnessLattice cell = getValue(node.receiver.definition);
501 if (cell.isUnknown) {
502 return; // And come back later.
503 } else if (cell.isNonConst) {
504 setValues(_ConstnessLattice.NonConst);
505 } else if (node.type.kind == types.TypeKind.INTERFACE) {
506 // Receiver is a constant, perform is-checks at compile-time.
507
508 types.InterfaceType checkedType = node.type;
509 ConstantValue constant = cell.constant;
510 types.DartType constantType = constant.computeType(compiler);
511
512 _ConstnessLattice result = _ConstnessLattice.NonConst;
513 if (constant.isNull &&
514 checkedType.element != compiler.nullClass &&
515 checkedType.element != compiler.objectClass) {
516 // `(null is Type)` is true iff Type is in { Null, Object }.
517 result = new _ConstnessLattice(new FalseConstantValue());
518 } else {
519 // Otherwise, perform a standard subtype check.
520 result = new _ConstnessLattice(
521 constantSystem.isSubtype(compiler, constantType, checkedType)
522 ? new TrueConstantValue()
523 : new FalseConstantValue());
524 }
525
526 setValues(result);
527 }
528 }
529
530 void visitSetClosureVariable(SetClosureVariable node) {
531 setReachable(node.body);
532 }
533
534 void visitDeclareFunction(DeclareFunction node) {
535 setReachable(node.definition);
536 setReachable(node.body);
537 }
538
539 // Definitions.
540 void visitLiteralList(LiteralList node) {
541 // Constant lists are translated into (Constant ListConstant(...)) IR nodes,
542 // and thus LiteralList nodes are NonConst.
543 setValue(node, _ConstnessLattice.NonConst);
544 }
545
546 void visitLiteralMap(LiteralMap node) {
547 // Constant maps are translated into (Constant MapConstant(...)) IR nodes,
548 // and thus LiteralMap nodes are NonConst.
549 setValue(node, _ConstnessLattice.NonConst);
550 }
551
552 void visitConstant(Constant node) {
553 setValue(node, new _ConstnessLattice(node.value));
554 }
555
556 void visitThis(This node) {
557 setValue(node, _ConstnessLattice.NonConst);
558 }
559
560 void visitReifyTypeVar(ReifyTypeVar node) {
561 setValue(node, _ConstnessLattice.NonConst);
562 }
563
564 void visitCreateFunction(CreateFunction node) {
565 setReachable(node.definition);
566 ConstantValue constant =
567 new FunctionConstantValue(node.definition.element);
568 setValue(node, new _ConstnessLattice(constant));
569 }
570
571 void visitGetClosureVariable(GetClosureVariable node) {
572 setValue(node, _ConstnessLattice.NonConst);
573 }
574
575 void visitParameter(Parameter node) {
576 if (node.parent is FunctionDefinition) {
577 // Functions may escape and thus their parameters must be initialized to
578 // NonConst.
579 setValue(node, _ConstnessLattice.NonConst);
580 } else if (node.parent is Continuation) {
581 // Continuations on the other hand are local, and parameters are
582 // initialized to Unknown.
583 setValue(node, _ConstnessLattice.Unknown);
584 } else {
585 compiler.internalError(node.hint, "Unexpected parent of Parameter");
586 }
587 }
588
589 void visitContinuation(Continuation node) {
590 node.parameters.forEach((Parameter p) {
591 setValue(p, _ConstnessLattice.Unknown);
592 defWorkset.add(p);
593 });
594
595 if (node.body != null) {
596 setReachable(node.body);
597 }
598 }
599
600 // Conditions.
601
602 void visitIsTrue(IsTrue node) {
603 Branch branch = node.parent;
604 visitBranch(branch);
605 }
606 }
607
608 /// Represents the constant-state of a variable at some point in the program.
609 /// UNKNOWN: may be some as yet undetermined constant.
610 /// CONSTANT: is a constant as stored in the local field.
611 /// NONCONST: not a constant.
612 class _ConstnessLattice {
613 static const int UNKNOWN = 0;
614 static const int CONSTANT = 1;
615 static const int NONCONST = 2;
616
617 final int kind;
618 final ConstantValue constant;
619
620 static final _ConstnessLattice Unknown =
621 new _ConstnessLattice._internal(UNKNOWN, null);
622 static final _ConstnessLattice NonConst =
623 new _ConstnessLattice._internal(NONCONST, null);
624
625 _ConstnessLattice._internal(this.kind, this.constant);
626 _ConstnessLattice(this.constant) : kind = CONSTANT {
627 assert(this.constant != null);
628 }
629
630 bool get isUnknown => (kind == UNKNOWN);
631 bool get isConstant => (kind == CONSTANT);
632 bool get isNonConst => (kind == NONCONST);
633
634 int get hashCode => kind | (constant.hashCode << 2);
635 bool operator==(_ConstnessLattice that) =>
636 (that.kind == this.kind && that.constant == this.constant);
637
638 String toString() {
639 switch (kind) {
640 case UNKNOWN: return "Unknown";
641 case CONSTANT: return "Constant: $constant";
642 case NONCONST: return "Non-constant";
643 default: assert(false);
644 }
645 return null;
646 }
647
648 /// Compute the join of two values in the lattice.
649 _ConstnessLattice join(_ConstnessLattice that) {
650 assert(that != null);
651
652 if (this.isNonConst || that.isUnknown) {
653 return this;
654 }
655
656 if (this.isUnknown || that.isNonConst) {
657 return that;
658 }
659
660 if (this.constant == that.constant) {
661 return this;
662 }
663
664 return NonConst;
665 }
666 }
OLDNEW

Powered by Google App Engine
This is Rietveld 408576698