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

Side by Side Diff: pkg/compiler/lib/src/inferrer/inferrer_visitor.dart

Issue 2619723003: Rename inference files and classes post refactor (Closed)
Patch Set: Created 3 years, 11 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) 2013, 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 inferrer_visitor;
6
7 import 'dart:collection' show IterableMixin;
8
9 import '../common.dart';
10 import '../options.dart' show CompilerOptions;
11 import '../compiler.dart' show Compiler;
12 import '../constants/constant_system.dart';
13 import '../constants/expressions.dart';
14 import '../elements/resolution_types.dart';
15 import '../elements/elements.dart';
16 import '../resolution/operators.dart';
17 import '../resolution/semantic_visitor.dart';
18 import '../resolution/tree_elements.dart' show TreeElements;
19 import '../tree/tree.dart';
20 import '../types/constants.dart' show computeTypeMask;
21 import '../types/types.dart' show TypeMask;
22 import '../universe/call_structure.dart' show CallStructure;
23 import '../universe/selector.dart' show Selector;
24 import '../util/util.dart';
25 import '../world.dart' show ClosedWorld;
26 import 'inferrer_engine.dart';
27 import 'type_graph_nodes.dart';
28 import 'type_system.dart';
29
30 /**
31 * A variable scope holds types for variables. It has a link to a
32 * parent scope, but never changes the types in that parent. Instead,
33 * updates to locals of a parent scope are put in the current scope.
34 * The inferrer makes sure updates get merged into the parent scope,
35 * once the control flow block has been visited.
36 */
37 class VariableScope {
38 Map<Local, TypeInformation> variables;
39
40 /// The parent of this scope. Null for the root scope.
41 final VariableScope parent;
42
43 /// The [Node] that created this scope.
44 final Node block;
45
46 VariableScope(this.block, [parent])
47 : this.variables = null,
48 this.parent = parent;
49
50 VariableScope.deepCopyOf(VariableScope other)
51 : variables = other.variables == null
52 ? null
53 : new Map<Local, TypeInformation>.from(other.variables),
54 block = other.block,
55 parent = other.parent == null
56 ? null
57 : new VariableScope.deepCopyOf(other.parent);
58
59 VariableScope.topLevelCopyOf(VariableScope other)
60 : variables = other.variables == null
61 ? null
62 : new Map<Local, TypeInformation>.from(other.variables),
63 block = other.block,
64 parent = other.parent;
65
66 TypeInformation operator [](Local variable) {
67 TypeInformation result;
68 if (variables == null || (result = variables[variable]) == null) {
69 return parent == null ? null : parent[variable];
70 }
71 return result;
72 }
73
74 void operator []=(Local variable, TypeInformation mask) {
75 assert(mask != null);
76 if (variables == null) {
77 variables = new Map<Local, TypeInformation>();
78 }
79 variables[variable] = mask;
80 }
81
82 void forEachOwnLocal(void f(Local variable, TypeInformation type)) {
83 if (variables == null) return;
84 variables.forEach(f);
85 }
86
87 void forEachLocalUntilNode(
88 Node node, void f(Local variable, TypeInformation type),
89 [Setlet<Local> seenLocals]) {
90 if (seenLocals == null) seenLocals = new Setlet<Local>();
91 if (variables != null) {
92 variables.forEach((variable, type) {
93 if (seenLocals.contains(variable)) return;
94 seenLocals.add(variable);
95 f(variable, type);
96 });
97 }
98 if (block == node) return;
99 if (parent != null) parent.forEachLocalUntilNode(node, f, seenLocals);
100 }
101
102 void forEachLocal(void f(Local variable, TypeInformation type)) {
103 forEachLocalUntilNode(null, f);
104 }
105
106 bool updates(Local variable) {
107 if (variables == null) return false;
108 return variables.containsKey(variable);
109 }
110
111 String toString() {
112 String rest = parent == null ? "null" : parent.toString();
113 return '$variables $rest';
114 }
115 }
116
117 class FieldInitializationScope {
118 final TypeSystem types;
119 Map<Element, TypeInformation> fields;
120 bool isThisExposed;
121
122 FieldInitializationScope(this.types) : isThisExposed = false;
123
124 FieldInitializationScope.internalFrom(FieldInitializationScope other)
125 : types = other.types,
126 isThisExposed = other.isThisExposed;
127
128 factory FieldInitializationScope.from(FieldInitializationScope other) {
129 if (other == null) return null;
130 return new FieldInitializationScope.internalFrom(other);
131 }
132
133 void updateField(Element field, TypeInformation type) {
134 if (isThisExposed) return;
135 if (fields == null) fields = new Map<Element, TypeInformation>();
136 fields[field] = type;
137 }
138
139 TypeInformation readField(Element field) {
140 return fields == null ? null : fields[field];
141 }
142
143 void forEach(void f(Element element, TypeInformation type)) {
144 if (fields == null) return;
145 fields.forEach(f);
146 }
147
148 void mergeDiamondFlow(
149 FieldInitializationScope thenScope, FieldInitializationScope elseScope) {
150 // Quick bailout check. If [isThisExposed] is true, we know the
151 // code following won'TypeInformation do anything.
152 if (isThisExposed) return;
153 if (elseScope == null || elseScope.fields == null) {
154 elseScope = this;
155 }
156
157 thenScope.forEach((Element field, TypeInformation type) {
158 TypeInformation otherType = elseScope.readField(field);
159 if (otherType == null) return;
160 updateField(field, types.allocateDiamondPhi(type, otherType));
161 });
162 isThisExposed = thenScope.isThisExposed || elseScope.isThisExposed;
163 }
164 }
165
166 /**
167 * Placeholder for inferred arguments types on sends.
168 */
169 class ArgumentsTypes extends IterableMixin<TypeInformation> {
170 final List<TypeInformation> positional;
171 final Map<String, TypeInformation> named;
172 ArgumentsTypes(this.positional, named)
173 : this.named = (named == null || named.isEmpty) ? const {} : named {
174 assert(this.positional.every((TypeInformation type) => type != null));
175 assert(this.named.values.every((TypeInformation type) => type != null));
176 }
177
178 ArgumentsTypes.empty()
179 : positional = const [],
180 named = const {};
181
182 int get length => positional.length + named.length;
183
184 Iterator<TypeInformation> get iterator => new ArgumentsTypesIterator(this);
185
186 String toString() => "{ positional = $positional, named = $named }";
187
188 bool operator ==(other) {
189 if (positional.length != other.positional.length) return false;
190 if (named.length != other.named.length) return false;
191 for (int i = 0; i < positional.length; i++) {
192 if (positional[i] != other.positional[i]) return false;
193 }
194 named.forEach((name, type) {
195 if (other.named[name] != type) return false;
196 });
197 return true;
198 }
199
200 int get hashCode => throw new UnsupportedError('ArgumentsTypes.hashCode');
201
202 bool hasNoArguments() => positional.isEmpty && named.isEmpty;
203
204 void forEach(void f(TypeInformation type)) {
205 positional.forEach(f);
206 named.values.forEach(f);
207 }
208
209 bool every(bool f(TypeInformation type)) {
210 return positional.every(f) && named.values.every(f);
211 }
212
213 bool contains(TypeInformation type) {
214 return positional.contains(type) || named.containsValue(type);
215 }
216 }
217
218 class ArgumentsTypesIterator implements Iterator<TypeInformation> {
219 final Iterator<TypeInformation> positional;
220 final Iterator<TypeInformation> named;
221 bool _iteratePositional = true;
222
223 ArgumentsTypesIterator(ArgumentsTypes iteratee)
224 : positional = iteratee.positional.iterator,
225 named = iteratee.named.values.iterator;
226
227 Iterator<TypeInformation> get _currentIterator =>
228 _iteratePositional ? positional : named;
229
230 TypeInformation get current => _currentIterator.current;
231
232 bool moveNext() {
233 if (_iteratePositional && positional.moveNext()) {
234 return true;
235 }
236 _iteratePositional = false;
237 return named.moveNext();
238 }
239 }
240
241 /**
242 * Placeholder for inferred types of local variables.
243 */
244 class LocalsHandler {
245 final CompilerOptions options;
246 final TypeSystem types;
247 final InferrerEngine inferrer;
248 final VariableScope locals;
249 final Map<Local, Element> captured;
250 final Map<Local, Element> capturedAndBoxed;
251 final FieldInitializationScope fieldScope;
252 LocalsHandler tryBlock;
253 bool seenReturnOrThrow = false;
254 bool seenBreakOrContinue = false;
255
256 bool get aborts {
257 return seenReturnOrThrow || seenBreakOrContinue;
258 }
259
260 bool get inTryBlock => tryBlock != null;
261
262 LocalsHandler(this.inferrer, this.types, this.options, Node block,
263 [this.fieldScope])
264 : locals = new VariableScope(block),
265 captured = new Map<Local, Element>(),
266 capturedAndBoxed = new Map<Local, Element>(),
267 tryBlock = null;
268
269 LocalsHandler.from(LocalsHandler other, Node block,
270 {bool useOtherTryBlock: true})
271 : locals = new VariableScope(block, other.locals),
272 fieldScope = new FieldInitializationScope.from(other.fieldScope),
273 captured = other.captured,
274 capturedAndBoxed = other.capturedAndBoxed,
275 types = other.types,
276 inferrer = other.inferrer,
277 options = other.options {
278 tryBlock = useOtherTryBlock ? other.tryBlock : this;
279 }
280
281 LocalsHandler.deepCopyOf(LocalsHandler other)
282 : locals = new VariableScope.deepCopyOf(other.locals),
283 fieldScope = new FieldInitializationScope.from(other.fieldScope),
284 captured = other.captured,
285 capturedAndBoxed = other.capturedAndBoxed,
286 tryBlock = other.tryBlock,
287 types = other.types,
288 inferrer = other.inferrer,
289 options = other.options;
290
291 LocalsHandler.topLevelCopyOf(LocalsHandler other)
292 : locals = new VariableScope.topLevelCopyOf(other.locals),
293 fieldScope = new FieldInitializationScope.from(other.fieldScope),
294 captured = other.captured,
295 capturedAndBoxed = other.capturedAndBoxed,
296 tryBlock = other.tryBlock,
297 types = other.types,
298 inferrer = other.inferrer,
299 options = other.options;
300
301 TypeInformation use(Local local) {
302 if (capturedAndBoxed.containsKey(local)) {
303 return inferrer.typeOfElement(capturedAndBoxed[local]);
304 } else {
305 if (captured.containsKey(local)) {
306 inferrer.recordCapturedLocalRead(local);
307 }
308 return locals[local];
309 }
310 }
311
312 void update(LocalElement local, TypeInformation type, Node node) {
313 assert(type != null);
314 if (options.trustTypeAnnotations || options.enableTypeAssertions) {
315 type = types.narrowType(type, local.type);
316 }
317 updateLocal() {
318 TypeInformation currentType = locals[local];
319
320 SendSet send = node != null ? node.asSendSet() : null;
321 if (send != null && send.isIfNullAssignment && currentType != null) {
322 // If-null assignments may return either the new or the original value
323 // narrowed to non-null.
324 type = types.addPhiInput(
325 local,
326 types.allocatePhi(
327 locals.block, local, types.narrowNotNull(currentType)),
328 type);
329 }
330 locals[local] = type;
331 if (currentType != type) {
332 inferrer.recordLocalUpdate(local, type);
333 }
334 }
335
336 if (capturedAndBoxed.containsKey(local)) {
337 inferrer.recordTypeOfNonFinalField(node, capturedAndBoxed[local], type);
338 } else if (inTryBlock) {
339 // We don'TypeInformation know if an assignment in a try block
340 // will be executed, so all assigments in that block are
341 // potential types after we have left it. We update the parent
342 // of the try block so that, at exit of the try block, we get
343 // the right phi for it.
344 TypeInformation existing = tryBlock.locals.parent[local];
345 if (existing != null) {
346 TypeInformation phiType =
347 types.allocatePhi(tryBlock.locals.block, local, existing);
348 TypeInformation inputType = types.addPhiInput(local, phiType, type);
349 tryBlock.locals.parent[local] = inputType;
350 }
351 // Update the current handler unconditionnally with the new
352 // type.
353 updateLocal();
354 } else {
355 updateLocal();
356 }
357 }
358
359 void setCaptured(Local local, Element field) {
360 captured[local] = field;
361 }
362
363 void setCapturedAndBoxed(Local local, Element field) {
364 capturedAndBoxed[local] = field;
365 }
366
367 void mergeDiamondFlow(LocalsHandler thenBranch, LocalsHandler elseBranch) {
368 if (fieldScope != null && elseBranch != null) {
369 fieldScope.mergeDiamondFlow(thenBranch.fieldScope, elseBranch.fieldScope);
370 }
371 seenReturnOrThrow = thenBranch.seenReturnOrThrow &&
372 elseBranch != null &&
373 elseBranch.seenReturnOrThrow;
374 seenBreakOrContinue = thenBranch.seenBreakOrContinue &&
375 elseBranch != null &&
376 elseBranch.seenBreakOrContinue;
377 if (aborts) return;
378
379 void mergeOneBranch(LocalsHandler other) {
380 other.locals.forEachOwnLocal((Local local, TypeInformation type) {
381 TypeInformation myType = locals[local];
382 if (myType == null) return; // Variable is only defined in [other].
383 if (type == myType) return;
384 locals[local] = types.allocateDiamondPhi(myType, type);
385 });
386 }
387
388 void inPlaceUpdateOneBranch(LocalsHandler other) {
389 other.locals.forEachOwnLocal((Local local, TypeInformation type) {
390 TypeInformation myType = locals[local];
391 if (myType == null) return; // Variable is only defined in [other].
392 if (type == myType) return;
393 locals[local] = type;
394 });
395 }
396
397 if (thenBranch.aborts) {
398 if (elseBranch == null) return;
399 inPlaceUpdateOneBranch(elseBranch);
400 } else if (elseBranch == null) {
401 mergeOneBranch(thenBranch);
402 } else if (elseBranch.aborts) {
403 inPlaceUpdateOneBranch(thenBranch);
404 } else {
405 void mergeLocal(Local local) {
406 TypeInformation myType = locals[local];
407 if (myType == null) return;
408 TypeInformation elseType = elseBranch.locals[local];
409 TypeInformation thenType = thenBranch.locals[local];
410 if (thenType == elseType) {
411 locals[local] = thenType;
412 } else {
413 locals[local] = types.allocateDiamondPhi(thenType, elseType);
414 }
415 }
416
417 thenBranch.locals.forEachOwnLocal((Local local, _) {
418 mergeLocal(local);
419 });
420 elseBranch.locals.forEachOwnLocal((Local local, _) {
421 // Discard locals we already processed when iterating over
422 // [thenBranch]'s locals.
423 if (!thenBranch.locals.updates(local)) mergeLocal(local);
424 });
425 }
426 }
427
428 /**
429 * Merge all [LocalsHandler] in [handlers] into [:this:].
430 *
431 * If [keepOwnLocals] is true, the types of locals in this
432 * [LocalsHandler] are being used in the merge. [keepOwnLocals]
433 * should be true if this [LocalsHandler], the dominator of
434 * all [handlers], also direclty flows into the join point,
435 * that is the code after all [handlers]. For example, consider:
436 *
437 * [: switch (...) {
438 * case 1: ...; break;
439 * }
440 * :]
441 *
442 * The [LocalsHandler] at entry of the switch also flows into the
443 * exit of the switch, because there is no default case. So the
444 * types of locals at entry of the switch have to take part to the
445 * merge.
446 *
447 * The above situation is also true for labeled statements like
448 *
449 * [: L: {
450 * if (...) break;
451 * ...
452 * }
453 * :]
454 *
455 * where [:this:] is the [LocalsHandler] for the paths through the
456 * labeled statement that do not break out.
457 */
458 void mergeAfterBreaks(List<LocalsHandler> handlers,
459 {bool keepOwnLocals: true}) {
460 Node level = locals.block;
461 // Use a separate locals handler to perform the merge in, so that Phi
462 // creation does not invalidate previous type knowledge while we might
463 // still look it up.
464 LocalsHandler merged = new LocalsHandler.from(this, level);
465 Set<Local> seenLocals = new Setlet<Local>();
466 bool allBranchesAbort = true;
467 // Merge all other handlers.
468 for (LocalsHandler handler in handlers) {
469 allBranchesAbort = allBranchesAbort && handler.seenReturnOrThrow;
470 merged.mergeHandler(handler, seenLocals);
471 }
472 // If we want to keep own locals, we merge [seenLocals] from [this] into
473 // [merged] to update the Phi nodes with original values.
474 if (keepOwnLocals && !seenReturnOrThrow) {
475 for (Local variable in seenLocals) {
476 TypeInformation originalType = locals[variable];
477 if (originalType != null) {
478 merged.locals[variable] = types.addPhiInput(
479 variable, merged.locals[variable], originalType);
480 }
481 }
482 }
483 // Clean up Phi nodes with single input and store back result into
484 // actual locals handler.
485 merged.locals.forEachOwnLocal((Local variable, TypeInformation type) {
486 locals[variable] = types.simplifyPhi(level, variable, type);
487 });
488 seenReturnOrThrow =
489 allBranchesAbort && (!keepOwnLocals || seenReturnOrThrow);
490 }
491
492 /**
493 * Merge [other] into this handler. Returns whether a local in this
494 * has changed. If [seen] is not null, we allocate new Phi nodes
495 * unless the local is already present in the set [seen]. This effectively
496 * overwrites the current type knowledge in this handler.
497 */
498 bool mergeHandler(LocalsHandler other, [Set<Local> seen]) {
499 if (other.seenReturnOrThrow) return false;
500 bool changed = false;
501 other.locals.forEachLocalUntilNode(locals.block, (local, otherType) {
502 TypeInformation myType = locals[local];
503 if (myType == null) return;
504 TypeInformation newType;
505 if (seen != null && !seen.contains(local)) {
506 newType = types.allocatePhi(locals.block, local, otherType);
507 seen.add(local);
508 } else {
509 newType = types.addPhiInput(local, myType, otherType);
510 }
511 if (newType != myType) {
512 changed = true;
513 locals[local] = newType;
514 }
515 });
516 return changed;
517 }
518
519 /**
520 * Merge all [LocalsHandler] in [handlers] into this handler.
521 * Returns whether a local in this handler has changed.
522 */
523 bool mergeAll(List<LocalsHandler> handlers) {
524 bool changed = false;
525 assert(!seenReturnOrThrow);
526 handlers.forEach((other) {
527 changed = mergeHandler(other) || changed;
528 });
529 return changed;
530 }
531
532 void startLoop(Node loop) {
533 locals.forEachLocal((Local variable, TypeInformation type) {
534 TypeInformation newType = types.allocateLoopPhi(loop, variable, type);
535 if (newType != type) {
536 locals[variable] = newType;
537 }
538 });
539 }
540
541 void endLoop(Node loop) {
542 locals.forEachLocal((Local variable, TypeInformation type) {
543 TypeInformation newType = types.simplifyPhi(loop, variable, type);
544 if (newType != type) {
545 locals[variable] = newType;
546 }
547 });
548 }
549
550 void updateField(Element element, TypeInformation type) {
551 fieldScope.updateField(element, type);
552 }
553 }
OLDNEW
« no previous file with comments | « pkg/compiler/lib/src/inferrer/inferrer_engine.dart ('k') | pkg/compiler/lib/src/inferrer/locals_handler.dart » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698