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

Side by Side Diff: pkg/compiler/lib/src/cps_ir/insert_refinements.dart

Issue 1330503003: dart2js cps: Add path-sensitive types by inserting refinement IR nodes. (Closed) Base URL: git@github.com:dart-lang/sdk.git@master
Patch Set: Use IterableBase and isEmpty Created 5 years, 3 months 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
OLDNEW
(Empty)
1 // Copyright (c) 2015, 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 library cps_ir.optimization.insert_refinements;
6
7 import 'optimizers.dart' show Pass;
8 import 'shrinking_reductions.dart' show ParentVisitor;
9 import 'cps_ir_nodes.dart';
10 import '../types/types.dart';
11 import '../types/constants.dart';
12 import '../constants/values.dart';
13 import '../world.dart';
14 import '../common/names.dart';
15 import '../universe/universe.dart';
16 import '../elements/elements.dart';
17
18 /// Inserts [Refinement] nodes in the IR to allow for sparse path-sensitive
19 /// type analysis in the [TypePropagator] pass.
20 ///
21 /// Refinement nodes are inserted at the arms of a [Branch] node with a
22 /// condition of form `x is T` or `x == null`.
23 ///
24 /// Refinement nodes are inserted after a method invocation to refine the
25 /// receiver to the types that can respond to the given selector.
26 class InsertRefinements extends RecursiveVisitor implements Pass {
27 String get passName => 'Insert refinement nodes';
28
29 final TypesTask types;
30 final World world;
31 final TypeMask nonNullType;
32 final TypeMask nullType;
33
34 /// Maps unrefined primitives to its refinement currently in scope (if any).
35 final Map<Primitive, Refinement> refinementFor = <Primitive, Refinement>{};
36
37 InsertRefinements(this.types, World world)
38 : this.world = world,
39 nonNullType = new TypeMask.nonNullSubtype(world.objectClass, world),
40 nullType = new TypeMask.empty();
41
42 void rewrite(FunctionDefinition node) {
43 new ParentVisitor().visit(node);
44 visit(node.body);
45 }
46
47 /// Updates references to the refer to the refinement currently in scope.
48 void processReference(Reference node) {
49 Refinement refined = refinementFor[node.definition];
50 if (refined != null) {
51 node.changeTo(refined);
52 }
53 }
54
55 /// Moves the binding of [cont] to before [use].
Kevin Millikin (Google) 2015/09/03 10:21:06 I'd reword this to use Sink instead of Move becaus
asgerf 2015/09/03 12:31:39 Changed to 'immediately above'.
56 ///
57 /// This is used to ensure that everything in scope at [use] is also in scope
58 /// inside [cont], so refinements can be inserted inside [cont] without
59 /// accidentally referencing a primitive out of scope.
60 ///
61 /// It is always safe to do this for single-use continuations, because
62 /// strictly more things are in scope at the use site, and there can't be any
63 /// other use of [cont] that might fall out of scope since there is only
64 /// that single use.
65 void sinkContinuationToUse(Continuation cont, Expression use) {
Kevin Millikin (Google) 2015/09/03 10:21:06 Just a comment: there are already a pair of functi
asgerf 2015/09/03 12:31:39 That would be great, but sadly I don't have high h
66 assert(cont.hasExactlyOneUse && cont.firstRef.parent == use);
67 LetCont let = cont.parent;
68 InteriorNode useParent = use.parent;
69 if (useParent == let) return;
70 if (let.continuations.length > 1) {
71 // Create a new LetCont binding only this continuation.
Kevin Millikin (Google) 2015/09/03 10:21:06 Safe because there are no mutually recursive conti
asgerf 2015/09/03 12:31:39 There is only one use, so it can't be mutually rec
72 let.continuations.remove(cont);
73 let = new LetCont(cont, null);
74 cont.parent = let;
75 } else {
76 // Remove LetCont from current position.
77 InteriorNode letParent = let.parent;
78 letParent.body = let.body;
79 let.body.parent = letParent;
80 }
81
82 // Insert LetCont before use.
83 useParent.body = let;
84 let.body = use;
85 use.parent = let;
86 let.parent = useParent;
87 }
88
89 Primitive unfoldInterceptor(Primitive prim) {
90 return prim is Interceptor ? prim.input.definition : prim;
91 }
92
93 /// Enqueues [cont] for processing in a context where [refined] is the
94 /// current refinement for its value.
95 void pushRefinement(Continuation cont, Refinement refined) {
96 Primitive value = refined.effectiveDefinition;
97 Primitive currentRefinement = refinementFor[value];
98 pushAction(() {
99 refinementFor[value] = currentRefinement;
100 if (refined.hasNoUses) {
101 // Clean up refinements that are not used.
102 refined.value.unlink();
103 } else {
104 cont.body = new LetPrim(refined, cont.body);
105 refined.parent = cont.body;
106 refined.value.parent = refined;
107 }
108 });
109 push(cont);
110 pushAction(() {
111 refinementFor[value] = refined;
112 });
113 }
114
115 void visitInvokeMethod(InvokeMethod node) {
116 Continuation cont = node.continuation.definition;
117
118 // Update references to their current refined values.
119 processReference(node.receiver);
120 node.arguments.forEach(processReference);
121
122 // If the call is intercepted, we want to refine the actual receiver,
123 // not the interceptor.
124 Primitive receiver = unfoldInterceptor(node.receiver.definition);
125
126 // Sink the continuation to the call to ensure everything in scope
127 // here is also in scope inside the continuations.
128 sinkContinuationToUse(cont, node);
129
130 if (node.selector.isClosureCall) {
131 // Do not try to refine the receiver of closure calls; the class world
132 // does not know about closure classes.
133 push(cont);
134 } else {
135 // Filter away receivers that throw on this selector.
136 TypeMask type = world.allFunctions.receiverType(node.selector, node.mask);
137 pushRefinement(cont, new Refinement(receiver, type));
138 }
139 }
140
141 CallExpression getCallWithResult(Primitive prim) {
142 if (prim is Parameter && prim.parent is Continuation) {
143 Continuation cont = prim.parent;
144 if (cont.hasExactlyOneUse && cont.firstRef.parent is CallExpression) {
145 return cont.firstRef.parent;
146 }
147 }
148 return null;
149 }
150
151 bool isTrue(Primitive prim) {
152 return prim is Constant && prim.value.isTrue;
153 }
154
155 TypeMask getTypeOf(ConstantValue constant) {
156 return computeTypeMask(types.compiler, constant);
157 }
158
159 void visitBranch(Branch node) {
160 processReference(node.condition);
161 Primitive condition = node.condition.definition;
162 CallExpression call = getCallWithResult(condition);
163
164 Continuation trueCont = node.trueContinuation.definition;
165 Continuation falseCont = node.falseContinuation.definition;
166
167 // Sink both continuations to the Branch to ensure everything in scope
168 // here is also in scope inside the continuations.
169 sinkContinuationToUse(trueCont, node);
170 sinkContinuationToUse(falseCont, node);
171
172 // If the condition is an 'is' check, promote the checked value.
173 if (condition is TypeTest && condition.type.element is ClassElement) {
174 Primitive value = condition.value.definition;
175 ClassElement classElement = condition.type.element;
176 TypeMask type = new TypeMask.nonNullSubtype(classElement, world);
177 Primitive refinedValue = new Refinement(value, type);
178 pushRefinement(trueCont, refinedValue);
179 push(falseCont);
180 return;
181 }
182
183 // If the condition is comparison with a constant, promote the other value.
184 if (call is InvokeMethod && call.selector == Selectors.equals) {
185 Primitive first = call.arguments[0].definition;
186 Primitive second = call.arguments[1].definition;
187 if (second is Constant && second.value.isNull) {
188 Refinement refinedTrue = new Refinement(first, nullType);
189 Refinement refinedFalse = new Refinement(first, nonNullType);
190 pushRefinement(trueCont, refinedTrue);
191 pushRefinement(falseCont, refinedFalse);
192 return;
193 }
194 if (first is Constant && first.value.isNull) {
195 Refinement refinedTrue = new Refinement(second, nullType);
196 Refinement refinedFalse = new Refinement(second, nonNullType);
197 pushRefinement(trueCont, refinedTrue);
198 pushRefinement(falseCont, refinedFalse);
199 return;
200 }
201 }
202
203 push(trueCont);
204 push(falseCont);
205 }
206
207 @override
208 Expression traverseLetCont(LetCont node) {
209 for (Continuation cont in node.continuations) {
210 if (cont.hasExactlyOneUse &&
Kevin Millikin (Google) 2015/09/03 10:21:06 This algorithm doesn't really work if the continua
asgerf 2015/09/03 12:31:39 It's being asserted when we sink them to their use
211 (cont.firstRef.parent is InvokeMethod ||
212 cont.firstRef.parent is Branch)) {
213 // Do not push the continuation here.
214 // visitInvokeMethod and visitBranch will do that.
215 } else {
216 push(cont);
217 }
218 }
219 return node.body;
220 }
221 }
OLDNEW

Powered by Google App Engine
This is Rietveld 408576698