OLD | NEW |
---|---|
(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 } | |
OLD | NEW |