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

Side by Side Diff: pkg/compiler/lib/src/ssa/nodes.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 unified diff | Download patch | Annotate | Revision Log
OLDNEW
(Empty)
1 // Copyright (c) 2012, 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 ssa;
6
7 abstract class HVisitor<R> {
8 R visitAdd(HAdd node);
9 R visitBitAnd(HBitAnd node);
10 R visitBitNot(HBitNot node);
11 R visitBitOr(HBitOr node);
12 R visitBitXor(HBitXor node);
13 R visitBoolify(HBoolify node);
14 R visitBoundsCheck(HBoundsCheck node);
15 R visitBreak(HBreak node);
16 R visitConstant(HConstant node);
17 R visitContinue(HContinue node);
18 R visitDivide(HDivide node);
19 R visitExit(HExit node);
20 R visitExitTry(HExitTry node);
21 R visitFieldGet(HFieldGet node);
22 R visitFieldSet(HFieldSet node);
23 R visitForeign(HForeign node);
24 R visitForeignNew(HForeignNew node);
25 R visitGoto(HGoto node);
26 R visitGreater(HGreater node);
27 R visitGreaterEqual(HGreaterEqual node);
28 R visitIdentity(HIdentity node);
29 R visitIf(HIf node);
30 R visitIndex(HIndex node);
31 R visitIndexAssign(HIndexAssign node);
32 R visitInterceptor(HInterceptor node);
33 R visitInvokeClosure(HInvokeClosure node);
34 R visitInvokeDynamicGetter(HInvokeDynamicGetter node);
35 R visitInvokeDynamicMethod(HInvokeDynamicMethod node);
36 R visitInvokeDynamicSetter(HInvokeDynamicSetter node);
37 R visitInvokeStatic(HInvokeStatic node);
38 R visitInvokeSuper(HInvokeSuper node);
39 R visitInvokeConstructorBody(HInvokeConstructorBody node);
40 R visitIs(HIs node);
41 R visitIsViaInterceptor(HIsViaInterceptor node);
42 R visitLazyStatic(HLazyStatic node);
43 R visitLess(HLess node);
44 R visitLessEqual(HLessEqual node);
45 R visitLiteralList(HLiteralList node);
46 R visitLocalGet(HLocalGet node);
47 R visitLocalSet(HLocalSet node);
48 R visitLocalValue(HLocalValue node);
49 R visitLoopBranch(HLoopBranch node);
50 R visitMultiply(HMultiply node);
51 R visitNegate(HNegate node);
52 R visitNot(HNot node);
53 R visitOneShotInterceptor(HOneShotInterceptor node);
54 R visitParameterValue(HParameterValue node);
55 R visitPhi(HPhi node);
56 R visitRangeConversion(HRangeConversion node);
57 R visitReadModifyWrite(HReadModifyWrite node);
58 R visitReturn(HReturn node);
59 R visitShiftLeft(HShiftLeft node);
60 R visitShiftRight(HShiftRight node);
61 R visitStatic(HStatic node);
62 R visitStaticStore(HStaticStore node);
63 R visitStringConcat(HStringConcat node);
64 R visitStringify(HStringify node);
65 R visitSubtract(HSubtract node);
66 R visitSwitch(HSwitch node);
67 R visitThis(HThis node);
68 R visitThrow(HThrow node);
69 R visitThrowExpression(HThrowExpression node);
70 R visitTruncatingDivide(HTruncatingDivide node);
71 R visitTry(HTry node);
72 R visitTypeConversion(HTypeConversion node);
73 R visitTypeKnown(HTypeKnown node);
74 R visitReadTypeVariable(HReadTypeVariable node);
75 R visitFunctionType(HFunctionType node);
76 R visitVoidType(HVoidType node);
77 R visitInterfaceType(HInterfaceType node);
78 R visitDynamicType(HDynamicType node);
79 }
80
81 abstract class HGraphVisitor {
82 visitDominatorTree(HGraph graph) {
83 void visitBasicBlockAndSuccessors(HBasicBlock block) {
84 visitBasicBlock(block);
85 List dominated = block.dominatedBlocks;
86 for (int i = 0; i < dominated.length; i++) {
87 visitBasicBlockAndSuccessors(dominated[i]);
88 }
89 }
90
91 visitBasicBlockAndSuccessors(graph.entry);
92 }
93
94 visitPostDominatorTree(HGraph graph) {
95 void visitBasicBlockAndSuccessors(HBasicBlock block) {
96 List dominated = block.dominatedBlocks;
97 for (int i = dominated.length - 1; i >= 0; i--) {
98 visitBasicBlockAndSuccessors(dominated[i]);
99 }
100 visitBasicBlock(block);
101 }
102
103 visitBasicBlockAndSuccessors(graph.entry);
104 }
105
106 visitBasicBlock(HBasicBlock block);
107 }
108
109 abstract class HInstructionVisitor extends HGraphVisitor {
110 HBasicBlock currentBlock;
111
112 visitInstruction(HInstruction node);
113
114 visitBasicBlock(HBasicBlock node) {
115 void visitInstructionList(HInstructionList list) {
116 HInstruction instruction = list.first;
117 while (instruction != null) {
118 visitInstruction(instruction);
119 instruction = instruction.next;
120 assert(instruction != list.first);
121 }
122 }
123
124 currentBlock = node;
125 visitInstructionList(node);
126 }
127 }
128
129 class HGraph {
130 HBasicBlock entry;
131 HBasicBlock exit;
132 HThis thisInstruction;
133 /// Receiver parameter, set for methods using interceptor calling convention.
134 HParameterValue explicitReceiverParameter;
135 bool isRecursiveMethod = false;
136 bool calledInLoop = false;
137 final List<HBasicBlock> blocks;
138
139 // We canonicalize all constants used within a graph so we do not
140 // have to worry about them for global value numbering.
141 Map<ConstantValue, HConstant> constants;
142
143 HGraph()
144 : blocks = new List<HBasicBlock>(),
145 constants = new Map<ConstantValue, HConstant>() {
146 entry = addNewBlock();
147 // The exit block will be added later, so it has an id that is
148 // after all others in the system.
149 exit = new HBasicBlock();
150 }
151
152 void addBlock(HBasicBlock block) {
153 int id = blocks.length;
154 block.id = id;
155 blocks.add(block);
156 assert(identical(blocks[id], block));
157 }
158
159 HBasicBlock addNewBlock() {
160 HBasicBlock result = new HBasicBlock();
161 addBlock(result);
162 return result;
163 }
164
165 HBasicBlock addNewLoopHeaderBlock(JumpTarget target,
166 List<LabelDefinition> labels) {
167 HBasicBlock result = addNewBlock();
168 result.loopInformation =
169 new HLoopInformation(result, target, labels);
170 return result;
171 }
172
173 HConstant addConstant(ConstantValue constant, Compiler compiler) {
174 HConstant result = constants[constant];
175 if (result == null) {
176 TypeMask type = constant.computeMask(compiler);
177 result = new HConstant.internal(constant, type);
178 entry.addAtExit(result);
179 constants[constant] = result;
180 } else if (result.block == null) {
181 // The constant was not used anymore.
182 entry.addAtExit(result);
183 }
184 return result;
185 }
186
187 HConstant addDeferredConstant(ConstantValue constant, PrefixElement prefix,
188 Compiler compiler) {
189 ConstantValue wrapper = new DeferredConstantValue(constant, prefix);
190 compiler.deferredLoadTask.registerConstantDeferredUse(wrapper, prefix);
191 return addConstant(wrapper, compiler);
192 }
193
194 HConstant addConstantInt(int i, Compiler compiler) {
195 return addConstant(compiler.backend.constantSystem.createInt(i), compiler);
196 }
197
198 HConstant addConstantDouble(double d, Compiler compiler) {
199 return addConstant(
200 compiler.backend.constantSystem.createDouble(d), compiler);
201 }
202
203 HConstant addConstantString(ast.DartString str,
204 Compiler compiler) {
205 return addConstant(
206 compiler.backend.constantSystem.createString(str),
207 compiler);
208 }
209
210 HConstant addConstantBool(bool value, Compiler compiler) {
211 return addConstant(
212 compiler.backend.constantSystem.createBool(value), compiler);
213 }
214
215 HConstant addConstantNull(Compiler compiler) {
216 return addConstant(compiler.backend.constantSystem.createNull(), compiler);
217 }
218
219 void finalize() {
220 addBlock(exit);
221 exit.open();
222 exit.close(new HExit());
223 assignDominators();
224 }
225
226 void assignDominators() {
227 // Run through the blocks in order of increasing ids so we are
228 // guaranteed that we have computed dominators for all blocks
229 // higher up in the dominator tree.
230 for (int i = 0, length = blocks.length; i < length; i++) {
231 HBasicBlock block = blocks[i];
232 List<HBasicBlock> predecessors = block.predecessors;
233 if (block.isLoopHeader()) {
234 block.assignCommonDominator(predecessors[0]);
235 } else {
236 for (int j = predecessors.length - 1; j >= 0; j--) {
237 block.assignCommonDominator(predecessors[j]);
238 }
239 }
240 }
241 }
242
243 bool isValid() {
244 HValidator validator = new HValidator();
245 validator.visitGraph(this);
246 return validator.isValid;
247 }
248 }
249
250 class HBaseVisitor extends HGraphVisitor implements HVisitor {
251 HBasicBlock currentBlock;
252
253 visitBasicBlock(HBasicBlock node) {
254 currentBlock = node;
255
256 HInstruction instruction = node.first;
257 while (instruction != null) {
258 instruction.accept(this);
259 instruction = instruction.next;
260 }
261 }
262
263 visitInstruction(HInstruction instruction) {}
264
265 visitBinaryArithmetic(HBinaryArithmetic node) => visitInvokeBinary(node);
266 visitBinaryBitOp(HBinaryBitOp node) => visitInvokeBinary(node);
267 visitInvoke(HInvoke node) => visitInstruction(node);
268 visitInvokeBinary(HInvokeBinary node) => visitInstruction(node);
269 visitInvokeDynamic(HInvokeDynamic node) => visitInvoke(node);
270 visitInvokeDynamicField(HInvokeDynamicField node) => visitInvokeDynamic(node);
271 visitInvokeUnary(HInvokeUnary node) => visitInstruction(node);
272 visitConditionalBranch(HConditionalBranch node) => visitControlFlow(node);
273 visitControlFlow(HControlFlow node) => visitInstruction(node);
274 visitFieldAccess(HFieldAccess node) => visitInstruction(node);
275 visitRelational(HRelational node) => visitInvokeBinary(node);
276
277 visitAdd(HAdd node) => visitBinaryArithmetic(node);
278 visitBitAnd(HBitAnd node) => visitBinaryBitOp(node);
279 visitBitNot(HBitNot node) => visitInvokeUnary(node);
280 visitBitOr(HBitOr node) => visitBinaryBitOp(node);
281 visitBitXor(HBitXor node) => visitBinaryBitOp(node);
282 visitBoolify(HBoolify node) => visitInstruction(node);
283 visitBoundsCheck(HBoundsCheck node) => visitCheck(node);
284 visitBreak(HBreak node) => visitJump(node);
285 visitContinue(HContinue node) => visitJump(node);
286 visitCheck(HCheck node) => visitInstruction(node);
287 visitConstant(HConstant node) => visitInstruction(node);
288 visitDivide(HDivide node) => visitBinaryArithmetic(node);
289 visitExit(HExit node) => visitControlFlow(node);
290 visitExitTry(HExitTry node) => visitControlFlow(node);
291 visitFieldGet(HFieldGet node) => visitFieldAccess(node);
292 visitFieldSet(HFieldSet node) => visitFieldAccess(node);
293 visitForeign(HForeign node) => visitInstruction(node);
294 visitForeignNew(HForeignNew node) => visitForeign(node);
295 visitGoto(HGoto node) => visitControlFlow(node);
296 visitGreater(HGreater node) => visitRelational(node);
297 visitGreaterEqual(HGreaterEqual node) => visitRelational(node);
298 visitIdentity(HIdentity node) => visitRelational(node);
299 visitIf(HIf node) => visitConditionalBranch(node);
300 visitIndex(HIndex node) => visitInstruction(node);
301 visitIndexAssign(HIndexAssign node) => visitInstruction(node);
302 visitInterceptor(HInterceptor node) => visitInstruction(node);
303 visitInvokeClosure(HInvokeClosure node)
304 => visitInvokeDynamic(node);
305 visitInvokeConstructorBody(HInvokeConstructorBody node)
306 => visitInvokeStatic(node);
307 visitInvokeDynamicMethod(HInvokeDynamicMethod node)
308 => visitInvokeDynamic(node);
309 visitInvokeDynamicGetter(HInvokeDynamicGetter node)
310 => visitInvokeDynamicField(node);
311 visitInvokeDynamicSetter(HInvokeDynamicSetter node)
312 => visitInvokeDynamicField(node);
313 visitInvokeStatic(HInvokeStatic node) => visitInvoke(node);
314 visitInvokeSuper(HInvokeSuper node) => visitInvokeStatic(node);
315 visitJump(HJump node) => visitControlFlow(node);
316 visitLazyStatic(HLazyStatic node) => visitInstruction(node);
317 visitLess(HLess node) => visitRelational(node);
318 visitLessEqual(HLessEqual node) => visitRelational(node);
319 visitLiteralList(HLiteralList node) => visitInstruction(node);
320 visitLocalAccess(HLocalAccess node) => visitInstruction(node);
321 visitLocalGet(HLocalGet node) => visitLocalAccess(node);
322 visitLocalSet(HLocalSet node) => visitLocalAccess(node);
323 visitLocalValue(HLocalValue node) => visitInstruction(node);
324 visitLoopBranch(HLoopBranch node) => visitConditionalBranch(node);
325 visitNegate(HNegate node) => visitInvokeUnary(node);
326 visitNot(HNot node) => visitInstruction(node);
327 visitOneShotInterceptor(HOneShotInterceptor node)
328 => visitInvokeDynamic(node);
329 visitPhi(HPhi node) => visitInstruction(node);
330 visitMultiply(HMultiply node) => visitBinaryArithmetic(node);
331 visitParameterValue(HParameterValue node) => visitLocalValue(node);
332 visitRangeConversion(HRangeConversion node) => visitCheck(node);
333 visitReadModifyWrite(HReadModifyWrite node) => visitInstruction(node);
334 visitReturn(HReturn node) => visitControlFlow(node);
335 visitShiftLeft(HShiftLeft node) => visitBinaryBitOp(node);
336 visitShiftRight(HShiftRight node) => visitBinaryBitOp(node);
337 visitSubtract(HSubtract node) => visitBinaryArithmetic(node);
338 visitSwitch(HSwitch node) => visitControlFlow(node);
339 visitStatic(HStatic node) => visitInstruction(node);
340 visitStaticStore(HStaticStore node) => visitInstruction(node);
341 visitStringConcat(HStringConcat node) => visitInstruction(node);
342 visitStringify(HStringify node) => visitInstruction(node);
343 visitThis(HThis node) => visitParameterValue(node);
344 visitThrow(HThrow node) => visitControlFlow(node);
345 visitThrowExpression(HThrowExpression node) => visitInstruction(node);
346 visitTruncatingDivide(HTruncatingDivide node) => visitBinaryArithmetic(node);
347 visitTry(HTry node) => visitControlFlow(node);
348 visitIs(HIs node) => visitInstruction(node);
349 visitIsViaInterceptor(HIsViaInterceptor node) => visitInstruction(node);
350 visitTypeConversion(HTypeConversion node) => visitCheck(node);
351 visitTypeKnown(HTypeKnown node) => visitCheck(node);
352 visitReadTypeVariable(HReadTypeVariable node) => visitInstruction(node);
353 visitFunctionType(HFunctionType node) => visitInstruction(node);
354 visitVoidType(HVoidType node) => visitInstruction(node);
355 visitInterfaceType(HInterfaceType node) => visitInstruction(node);
356 visitDynamicType(HDynamicType node) => visitInstruction(node);
357 }
358
359 class SubGraph {
360 // The first and last block of the sub-graph.
361 final HBasicBlock start;
362 final HBasicBlock end;
363
364 const SubGraph(this.start, this.end);
365
366 bool contains(HBasicBlock block) {
367 assert(start != null);
368 assert(end != null);
369 assert(block != null);
370 return start.id <= block.id && block.id <= end.id;
371 }
372 }
373
374 class SubExpression extends SubGraph {
375 const SubExpression(HBasicBlock start, HBasicBlock end)
376 : super(start, end);
377
378 /** Find the condition expression if this sub-expression is a condition. */
379 HInstruction get conditionExpression {
380 HInstruction last = end.last;
381 if (last is HConditionalBranch || last is HSwitch) return last.inputs[0];
382 return null;
383 }
384 }
385
386 class HInstructionList {
387 HInstruction first = null;
388 HInstruction last = null;
389
390 bool get isEmpty {
391 return first == null;
392 }
393
394 void internalAddAfter(HInstruction cursor, HInstruction instruction) {
395 if (cursor == null) {
396 assert(isEmpty);
397 first = last = instruction;
398 } else if (identical(cursor, last)) {
399 last.next = instruction;
400 instruction.previous = last;
401 last = instruction;
402 } else {
403 instruction.previous = cursor;
404 instruction.next = cursor.next;
405 cursor.next.previous = instruction;
406 cursor.next = instruction;
407 }
408 }
409
410 void internalAddBefore(HInstruction cursor, HInstruction instruction) {
411 if (cursor == null) {
412 assert(isEmpty);
413 first = last = instruction;
414 } else if (identical(cursor, first)) {
415 first.previous = instruction;
416 instruction.next = first;
417 first = instruction;
418 } else {
419 instruction.next = cursor;
420 instruction.previous = cursor.previous;
421 cursor.previous.next = instruction;
422 cursor.previous = instruction;
423 }
424 }
425
426 void detach(HInstruction instruction) {
427 assert(contains(instruction));
428 assert(instruction.isInBasicBlock());
429 if (instruction.previous == null) {
430 first = instruction.next;
431 } else {
432 instruction.previous.next = instruction.next;
433 }
434 if (instruction.next == null) {
435 last = instruction.previous;
436 } else {
437 instruction.next.previous = instruction.previous;
438 }
439 instruction.previous = null;
440 instruction.next = null;
441 }
442
443 void remove(HInstruction instruction) {
444 assert(instruction.usedBy.isEmpty);
445 detach(instruction);
446 }
447
448 /** Linear search for [instruction]. */
449 bool contains(HInstruction instruction) {
450 HInstruction cursor = first;
451 while (cursor != null) {
452 if (identical(cursor, instruction)) return true;
453 cursor = cursor.next;
454 }
455 return false;
456 }
457 }
458
459 class HBasicBlock extends HInstructionList {
460 // The [id] must be such that any successor's id is greater than
461 // this [id]. The exception are back-edges.
462 int id;
463
464 static const int STATUS_NEW = 0;
465 static const int STATUS_OPEN = 1;
466 static const int STATUS_CLOSED = 2;
467 int status = STATUS_NEW;
468
469 HInstructionList phis;
470
471 HLoopInformation loopInformation = null;
472 HBlockFlow blockFlow = null;
473 HBasicBlock parentLoopHeader = null;
474 bool isLive = true;
475
476 final List<HBasicBlock> predecessors;
477 List<HBasicBlock> successors;
478
479 HBasicBlock dominator = null;
480 final List<HBasicBlock> dominatedBlocks;
481
482 HBasicBlock() : this.withId(null);
483 HBasicBlock.withId(this.id)
484 : phis = new HInstructionList(),
485 predecessors = <HBasicBlock>[],
486 successors = const <HBasicBlock>[],
487 dominatedBlocks = <HBasicBlock>[];
488
489 int get hashCode => id;
490
491 bool isNew() => status == STATUS_NEW;
492 bool isOpen() => status == STATUS_OPEN;
493 bool isClosed() => status == STATUS_CLOSED;
494
495 bool isLoopHeader() {
496 return loopInformation != null;
497 }
498
499 void setBlockFlow(HBlockInformation blockInfo, HBasicBlock continuation) {
500 blockFlow = new HBlockFlow(blockInfo, continuation);
501 }
502
503 bool isLabeledBlock() =>
504 blockFlow != null &&
505 blockFlow.body is HLabeledBlockInformation;
506
507 HBasicBlock get enclosingLoopHeader {
508 if (isLoopHeader()) return this;
509 return parentLoopHeader;
510 }
511
512 void open() {
513 assert(isNew());
514 status = STATUS_OPEN;
515 }
516
517 void close(HControlFlow end) {
518 assert(isOpen());
519 addAfter(last, end);
520 status = STATUS_CLOSED;
521 }
522
523 void addAtEntry(HInstruction instruction) {
524 assert(instruction is !HPhi);
525 internalAddBefore(first, instruction);
526 instruction.notifyAddedToBlock(this);
527 }
528
529 void addAtExit(HInstruction instruction) {
530 assert(isClosed());
531 assert(last is HControlFlow);
532 assert(instruction is !HPhi);
533 internalAddBefore(last, instruction);
534 instruction.notifyAddedToBlock(this);
535 }
536
537 void moveAtExit(HInstruction instruction) {
538 assert(instruction is !HPhi);
539 assert(instruction.isInBasicBlock());
540 assert(isClosed());
541 assert(last is HControlFlow);
542 internalAddBefore(last, instruction);
543 instruction.block = this;
544 assert(isValid());
545 }
546
547 void add(HInstruction instruction) {
548 assert(instruction is !HControlFlow);
549 assert(instruction is !HPhi);
550 internalAddAfter(last, instruction);
551 instruction.notifyAddedToBlock(this);
552 }
553
554 void addPhi(HPhi phi) {
555 assert(phi.inputs.length == 0 || phi.inputs.length == predecessors.length);
556 assert(phi.block == null);
557 phis.internalAddAfter(phis.last, phi);
558 phi.notifyAddedToBlock(this);
559 }
560
561 void removePhi(HPhi phi) {
562 phis.remove(phi);
563 assert(phi.block == this);
564 phi.notifyRemovedFromBlock();
565 }
566
567 void addAfter(HInstruction cursor, HInstruction instruction) {
568 assert(cursor is !HPhi);
569 assert(instruction is !HPhi);
570 assert(isOpen() || isClosed());
571 internalAddAfter(cursor, instruction);
572 instruction.notifyAddedToBlock(this);
573 }
574
575 void addBefore(HInstruction cursor, HInstruction instruction) {
576 assert(cursor is !HPhi);
577 assert(instruction is !HPhi);
578 assert(isOpen() || isClosed());
579 internalAddBefore(cursor, instruction);
580 instruction.notifyAddedToBlock(this);
581 }
582
583 void remove(HInstruction instruction) {
584 assert(isOpen() || isClosed());
585 assert(instruction is !HPhi);
586 super.remove(instruction);
587 assert(instruction.block == this);
588 instruction.notifyRemovedFromBlock();
589 }
590
591 void addSuccessor(HBasicBlock block) {
592 if (successors.isEmpty) {
593 successors = [block];
594 } else {
595 successors.add(block);
596 }
597 block.predecessors.add(this);
598 }
599
600 void postProcessLoopHeader() {
601 assert(isLoopHeader());
602 // Only the first entry into the loop is from outside the
603 // loop. All other entries must be back edges.
604 for (int i = 1, length = predecessors.length; i < length; i++) {
605 loopInformation.addBackEdge(predecessors[i]);
606 }
607 }
608
609 /**
610 * Rewrites all uses of the [from] instruction to using the [to]
611 * instruction instead.
612 */
613 void rewrite(HInstruction from, HInstruction to) {
614 for (HInstruction use in from.usedBy) {
615 use.rewriteInput(from, to);
616 }
617 to.usedBy.addAll(from.usedBy);
618 from.usedBy.clear();
619 }
620
621 /**
622 * Rewrites all uses of the [from] instruction to using either the
623 * [to] instruction, or a [HCheck] instruction that has better type
624 * information on [to], and that dominates the user.
625 */
626 void rewriteWithBetterUser(HInstruction from, HInstruction to) {
627 // BUG(11841): Turn this method into a phase to be run after GVN phases.
628 Link<HCheck> better = const Link<HCheck>();
629 for (HInstruction user in to.usedBy) {
630 if (user == from || user is! HCheck) continue;
631 HCheck check = user;
632 if (check.checkedInput == to) {
633 better = better.prepend(user);
634 }
635 }
636
637 if (better.isEmpty) return rewrite(from, to);
638
639 L1: for (HInstruction user in from.usedBy) {
640 for (HCheck check in better) {
641 if (check.dominates(user)) {
642 user.rewriteInput(from, check);
643 check.usedBy.add(user);
644 continue L1;
645 }
646 }
647 user.rewriteInput(from, to);
648 to.usedBy.add(user);
649 }
650 from.usedBy.clear();
651 }
652
653 bool isExitBlock() {
654 return identical(first, last) && first is HExit;
655 }
656
657 void addDominatedBlock(HBasicBlock block) {
658 assert(isClosed());
659 assert(id != null && block.id != null);
660 assert(dominatedBlocks.indexOf(block) < 0);
661 // Keep the list of dominated blocks sorted such that if there are two
662 // succeeding blocks in the list, the predecessor is before the successor.
663 // Assume that we add the dominated blocks in the right order.
664 int index = dominatedBlocks.length;
665 while (index > 0 && dominatedBlocks[index - 1].id > block.id) {
666 index--;
667 }
668 if (index == dominatedBlocks.length) {
669 dominatedBlocks.add(block);
670 } else {
671 dominatedBlocks.insert(index, block);
672 }
673 assert(block.dominator == null);
674 block.dominator = this;
675 }
676
677 void removeDominatedBlock(HBasicBlock block) {
678 assert(isClosed());
679 assert(id != null && block.id != null);
680 int index = dominatedBlocks.indexOf(block);
681 assert(index >= 0);
682 if (index == dominatedBlocks.length - 1) {
683 dominatedBlocks.removeLast();
684 } else {
685 dominatedBlocks.removeRange(index, index + 1);
686 }
687 assert(identical(block.dominator, this));
688 block.dominator = null;
689 }
690
691 void assignCommonDominator(HBasicBlock predecessor) {
692 assert(isClosed());
693 if (dominator == null) {
694 // If this basic block doesn't have a dominator yet we use the
695 // given predecessor as the dominator.
696 predecessor.addDominatedBlock(this);
697 } else if (predecessor.dominator != null) {
698 // If the predecessor has a dominator and this basic block has a
699 // dominator, we find a common parent in the dominator tree and
700 // use that as the dominator.
701 HBasicBlock block0 = dominator;
702 HBasicBlock block1 = predecessor;
703 while (!identical(block0, block1)) {
704 if (block0.id > block1.id) {
705 block0 = block0.dominator;
706 } else {
707 block1 = block1.dominator;
708 }
709 assert(block0 != null && block1 != null);
710 }
711 if (!identical(dominator, block0)) {
712 dominator.removeDominatedBlock(this);
713 block0.addDominatedBlock(this);
714 }
715 }
716 }
717
718 void forEachPhi(void f(HPhi phi)) {
719 HPhi current = phis.first;
720 while (current != null) {
721 HInstruction saved = current.next;
722 f(current);
723 current = saved;
724 }
725 }
726
727 void forEachInstruction(void f(HInstruction instruction)) {
728 HInstruction current = first;
729 while (current != null) {
730 HInstruction saved = current.next;
731 f(current);
732 current = saved;
733 }
734 }
735
736 bool isValid() {
737 assert(isClosed());
738 HValidator validator = new HValidator();
739 validator.visitBasicBlock(this);
740 return validator.isValid;
741 }
742
743 Map<HBasicBlock, bool> dominatesCache;
744
745 bool dominates(HBasicBlock other) {
746 if (dominatesCache == null) {
747 dominatesCache = new Map<HBasicBlock, bool>();
748 } else {
749 bool res = dominatesCache[other];
750 if (res != null) return res;
751 }
752 do {
753 if (identical(this, other)) return dominatesCache[other] = true;
754 other = other.dominator;
755 } while (other != null && other.id >= id);
756 return dominatesCache[other] = false;
757 }
758 }
759
760 abstract class HInstruction implements Spannable {
761 Entity sourceElement;
762 SourceFileLocation sourcePosition;
763
764 final int id;
765 static int idCounter;
766
767 final List<HInstruction> inputs;
768 final List<HInstruction> usedBy;
769
770 HBasicBlock block;
771 HInstruction previous = null;
772 HInstruction next = null;
773
774 SideEffects sideEffects = new SideEffects.empty();
775 bool _useGvn = false;
776
777 // Type codes.
778 static const int UNDEFINED_TYPECODE = -1;
779 static const int BOOLIFY_TYPECODE = 0;
780 static const int TYPE_GUARD_TYPECODE = 1;
781 static const int BOUNDS_CHECK_TYPECODE = 2;
782 static const int INTEGER_CHECK_TYPECODE = 3;
783 static const int INTERCEPTOR_TYPECODE = 4;
784 static const int ADD_TYPECODE = 5;
785 static const int DIVIDE_TYPECODE = 6;
786 static const int MULTIPLY_TYPECODE = 7;
787 static const int SUBTRACT_TYPECODE = 8;
788 static const int SHIFT_LEFT_TYPECODE = 9;
789 static const int BIT_OR_TYPECODE = 10;
790 static const int BIT_AND_TYPECODE = 11;
791 static const int BIT_XOR_TYPECODE = 12;
792 static const int NEGATE_TYPECODE = 13;
793 static const int BIT_NOT_TYPECODE = 14;
794 static const int NOT_TYPECODE = 15;
795 static const int IDENTITY_TYPECODE = 16;
796 static const int GREATER_TYPECODE = 17;
797 static const int GREATER_EQUAL_TYPECODE = 18;
798 static const int LESS_TYPECODE = 19;
799 static const int LESS_EQUAL_TYPECODE = 20;
800 static const int STATIC_TYPECODE = 21;
801 static const int STATIC_STORE_TYPECODE = 22;
802 static const int FIELD_GET_TYPECODE = 23;
803 static const int TYPE_CONVERSION_TYPECODE = 24;
804 static const int TYPE_KNOWN_TYPECODE = 25;
805 static const int INVOKE_STATIC_TYPECODE = 26;
806 static const int INDEX_TYPECODE = 27;
807 static const int IS_TYPECODE = 28;
808 static const int INVOKE_DYNAMIC_TYPECODE = 29;
809 static const int SHIFT_RIGHT_TYPECODE = 30;
810 static const int READ_TYPE_VARIABLE_TYPECODE = 31;
811 static const int FUNCTION_TYPE_TYPECODE = 32;
812 static const int VOID_TYPE_TYPECODE = 33;
813 static const int INTERFACE_TYPE_TYPECODE = 34;
814 static const int DYNAMIC_TYPE_TYPECODE = 35;
815 static const int TRUNCATING_DIVIDE_TYPECODE = 36;
816 static const int IS_VIA_INTERCEPTOR_TYPECODE = 37;
817
818 HInstruction(this.inputs, this.instructionType)
819 : id = idCounter++, usedBy = <HInstruction>[] {
820 assert(inputs.every((e) => e != null));
821 }
822
823 int get hashCode => id;
824
825 bool useGvn() => _useGvn;
826 void setUseGvn() { _useGvn = true; }
827
828 bool get isMovable => useGvn();
829
830 /**
831 * A pure instruction is an instruction that does not have any side
832 * effect, nor any dependency. They can be moved anywhere in the
833 * graph.
834 */
835 bool isPure() {
836 return !sideEffects.hasSideEffects()
837 && !sideEffects.dependsOnSomething()
838 && !canThrow();
839 }
840
841 /// Overridden by [HCheck] to return the actual non-[HCheck]
842 /// instruction it checks against.
843 HInstruction nonCheck() => this;
844
845 /// Can this node throw an exception?
846 bool canThrow() => false;
847
848 /// Does this node potentially affect control flow.
849 bool isControlFlow() => false;
850
851 bool isExact() => instructionType.isExact || isNull();
852
853 bool canBeNull() => instructionType.isNullable;
854
855 bool isNull() => instructionType.isEmpty && instructionType.isNullable;
856 bool isConflicting() {
857 return instructionType.isEmpty && !instructionType.isNullable;
858 }
859
860 bool canBePrimitive(Compiler compiler) {
861 return canBePrimitiveNumber(compiler)
862 || canBePrimitiveArray(compiler)
863 || canBePrimitiveBoolean(compiler)
864 || canBePrimitiveString(compiler)
865 || isNull();
866 }
867
868 bool canBePrimitiveNumber(Compiler compiler) {
869 ClassWorld classWorld = compiler.world;
870 JavaScriptBackend backend = compiler.backend;
871 // TODO(sra): It should be possible to test only jsDoubleClass and
872 // jsUInt31Class, since all others are superclasses of these two.
873 return instructionType.contains(backend.jsNumberClass, classWorld)
874 || instructionType.contains(backend.jsIntClass, classWorld)
875 || instructionType.contains(backend.jsPositiveIntClass, classWorld)
876 || instructionType.contains(backend.jsUInt32Class, classWorld)
877 || instructionType.contains(backend.jsUInt31Class, classWorld)
878 || instructionType.contains(backend.jsDoubleClass, classWorld);
879 }
880
881 bool canBePrimitiveBoolean(Compiler compiler) {
882 ClassWorld classWorld = compiler.world;
883 JavaScriptBackend backend = compiler.backend;
884 return instructionType.contains(backend.jsBoolClass, classWorld);
885 }
886
887 bool canBePrimitiveArray(Compiler compiler) {
888 ClassWorld classWorld = compiler.world;
889 JavaScriptBackend backend = compiler.backend;
890 return instructionType.contains(backend.jsArrayClass, classWorld)
891 || instructionType.contains(backend.jsFixedArrayClass, classWorld)
892 || instructionType.contains(backend.jsExtendableArrayClass, classWorld);
893 }
894
895 bool isIndexablePrimitive(Compiler compiler) {
896 ClassWorld classWorld = compiler.world;
897 JavaScriptBackend backend = compiler.backend;
898 return instructionType.containsOnlyString(classWorld)
899 || instructionType.satisfies(backend.jsIndexableClass, classWorld);
900 }
901
902 bool isFixedArray(Compiler compiler) {
903 JavaScriptBackend backend = compiler.backend;
904 return instructionType.containsOnly(backend.jsFixedArrayClass);
905 }
906
907 bool isExtendableArray(Compiler compiler) {
908 JavaScriptBackend backend = compiler.backend;
909 return instructionType.containsOnly(backend.jsExtendableArrayClass);
910 }
911
912 bool isMutableArray(Compiler compiler) {
913 ClassWorld classWorld = compiler.world;
914 JavaScriptBackend backend = compiler.backend;
915 return instructionType.satisfies(backend.jsMutableArrayClass, classWorld);
916 }
917
918 bool isReadableArray(Compiler compiler) {
919 ClassWorld classWorld = compiler.world;
920 JavaScriptBackend backend = compiler.backend;
921 return instructionType.satisfies(backend.jsArrayClass, classWorld);
922 }
923
924 bool isMutableIndexable(Compiler compiler) {
925 ClassWorld classWorld = compiler.world;
926 JavaScriptBackend backend = compiler.backend;
927 return instructionType.satisfies(
928 backend.jsMutableIndexableClass, classWorld);
929 }
930
931 bool isArray(Compiler compiler) => isReadableArray(compiler);
932
933 bool canBePrimitiveString(Compiler compiler) {
934 ClassWorld classWorld = compiler.world;
935 JavaScriptBackend backend = compiler.backend;
936 return instructionType.contains(backend.jsStringClass, classWorld);
937 }
938
939 bool isInteger(Compiler compiler) {
940 ClassWorld classWorld = compiler.world;
941 return instructionType.containsOnlyInt(classWorld)
942 && !instructionType.isNullable;
943 }
944
945 bool isUInt32(Compiler compiler) {
946 ClassWorld classWorld = compiler.world;
947 JavaScriptBackend backend = compiler.backend;
948 return !instructionType.isNullable
949 && instructionType.satisfies(backend.jsUInt32Class, classWorld);
950 }
951
952 bool isUInt31(Compiler compiler) {
953 ClassWorld classWorld = compiler.world;
954 JavaScriptBackend backend = compiler.backend;
955 return !instructionType.isNullable
956 && instructionType.satisfies(backend.jsUInt31Class, classWorld);
957 }
958
959 bool isPositiveInteger(Compiler compiler) {
960 ClassWorld classWorld = compiler.world;
961 JavaScriptBackend backend = compiler.backend;
962 return !instructionType.isNullable
963 && instructionType.satisfies(backend.jsPositiveIntClass, classWorld);
964 }
965
966 bool isPositiveIntegerOrNull(Compiler compiler) {
967 ClassWorld classWorld = compiler.world;
968 JavaScriptBackend backend = compiler.backend;
969 return instructionType.satisfies(backend.jsPositiveIntClass, classWorld);
970 }
971
972 bool isIntegerOrNull(Compiler compiler) {
973 ClassWorld classWorld = compiler.world;
974 return instructionType.containsOnlyInt(classWorld);
975 }
976
977 bool isNumber(Compiler compiler) {
978 ClassWorld classWorld = compiler.world;
979 return instructionType.containsOnlyNum(classWorld)
980 && !instructionType.isNullable;
981 }
982
983 bool isNumberOrNull(Compiler compiler) {
984 ClassWorld classWorld = compiler.world;
985 return instructionType.containsOnlyNum(classWorld);
986 }
987
988 bool isDouble(Compiler compiler) {
989 ClassWorld classWorld = compiler.world;
990 return instructionType.containsOnlyDouble(classWorld)
991 && !instructionType.isNullable;
992 }
993
994 bool isDoubleOrNull(Compiler compiler) {
995 ClassWorld classWorld = compiler.world;
996 return instructionType.containsOnlyDouble(classWorld);
997 }
998
999 bool isBoolean(Compiler compiler) {
1000 ClassWorld classWorld = compiler.world;
1001 return instructionType.containsOnlyBool(classWorld)
1002 && !instructionType.isNullable;
1003 }
1004
1005 bool isBooleanOrNull(Compiler compiler) {
1006 ClassWorld classWorld = compiler.world;
1007 return instructionType.containsOnlyBool(classWorld);
1008 }
1009
1010 bool isString(Compiler compiler) {
1011 ClassWorld classWorld = compiler.world;
1012 return instructionType.containsOnlyString(classWorld)
1013 && !instructionType.isNullable;
1014 }
1015
1016 bool isStringOrNull(Compiler compiler) {
1017 ClassWorld classWorld = compiler.world;
1018 return instructionType.containsOnlyString(classWorld);
1019 }
1020
1021 bool isPrimitive(Compiler compiler) {
1022 return (isPrimitiveOrNull(compiler) && !instructionType.isNullable)
1023 || isNull();
1024 }
1025
1026 bool isPrimitiveOrNull(Compiler compiler) {
1027 return isIndexablePrimitive(compiler)
1028 || isNumberOrNull(compiler)
1029 || isBooleanOrNull(compiler)
1030 || isNull();
1031 }
1032
1033 /**
1034 * Type of the instruction.
1035 */
1036 TypeMask instructionType;
1037
1038 Selector get selector => null;
1039 HInstruction getDartReceiver(Compiler compiler) => null;
1040 bool onlyThrowsNSM() => false;
1041
1042 bool isInBasicBlock() => block != null;
1043
1044 bool gvnEquals(HInstruction other) {
1045 assert(useGvn() && other.useGvn());
1046 // Check that the type and the sideEffects match.
1047 bool hasSameType = typeEquals(other);
1048 assert(hasSameType == (typeCode() == other.typeCode()));
1049 if (!hasSameType) return false;
1050 if (sideEffects != other.sideEffects) return false;
1051 // Check that the inputs match.
1052 final int inputsLength = inputs.length;
1053 final List<HInstruction> otherInputs = other.inputs;
1054 if (inputsLength != otherInputs.length) return false;
1055 for (int i = 0; i < inputsLength; i++) {
1056 if (!identical(inputs[i].nonCheck(), otherInputs[i].nonCheck())) {
1057 return false;
1058 }
1059 }
1060 // Check that the data in the instruction matches.
1061 return dataEquals(other);
1062 }
1063
1064 int gvnHashCode() {
1065 int result = typeCode();
1066 int length = inputs.length;
1067 for (int i = 0; i < length; i++) {
1068 result = (result * 19) + (inputs[i].nonCheck().id) + (result >> 7);
1069 }
1070 return result;
1071 }
1072
1073 // These methods should be overwritten by instructions that
1074 // participate in global value numbering.
1075 int typeCode() => HInstruction.UNDEFINED_TYPECODE;
1076 bool typeEquals(HInstruction other) => false;
1077 bool dataEquals(HInstruction other) => false;
1078
1079 accept(HVisitor visitor);
1080
1081 void notifyAddedToBlock(HBasicBlock targetBlock) {
1082 assert(!isInBasicBlock());
1083 assert(block == null);
1084 // Add [this] to the inputs' uses.
1085 for (int i = 0; i < inputs.length; i++) {
1086 assert(inputs[i].isInBasicBlock());
1087 inputs[i].usedBy.add(this);
1088 }
1089 block = targetBlock;
1090 assert(isValid());
1091 }
1092
1093 void notifyRemovedFromBlock() {
1094 assert(isInBasicBlock());
1095 assert(usedBy.isEmpty);
1096
1097 // Remove [this] from the inputs' uses.
1098 for (int i = 0; i < inputs.length; i++) {
1099 inputs[i].removeUser(this);
1100 }
1101 this.block = null;
1102 assert(isValid());
1103 }
1104
1105 /// Do a in-place change of [from] to [to]. Warning: this function
1106 /// does not update [inputs] and [usedBy]. Use [changeUse] instead.
1107 void rewriteInput(HInstruction from, HInstruction to) {
1108 for (int i = 0; i < inputs.length; i++) {
1109 if (identical(inputs[i], from)) inputs[i] = to;
1110 }
1111 }
1112
1113 /** Removes all occurrences of [instruction] from [list]. */
1114 void removeFromList(List<HInstruction> list, HInstruction instruction) {
1115 int length = list.length;
1116 int i = 0;
1117 while (i < length) {
1118 if (instruction == list[i]) {
1119 list[i] = list[length - 1];
1120 length--;
1121 } else {
1122 i++;
1123 }
1124 }
1125 list.length = length;
1126 }
1127
1128 /** Removes all occurrences of [user] from [usedBy]. */
1129 void removeUser(HInstruction user) {
1130 removeFromList(usedBy, user);
1131 }
1132
1133 // Change all uses of [oldInput] by [this] to [newInput]. Also
1134 // updates the [usedBy] of [oldInput] and [newInput].
1135 void changeUse(HInstruction oldInput, HInstruction newInput) {
1136 assert(newInput != null && !identical(oldInput, newInput));
1137 for (int i = 0; i < inputs.length; i++) {
1138 if (identical(inputs[i], oldInput)) {
1139 inputs[i] = newInput;
1140 newInput.usedBy.add(this);
1141 }
1142 }
1143 removeFromList(oldInput.usedBy, this);
1144 }
1145
1146 // Compute the set of users of this instruction that is dominated by
1147 // [other]. If [other] is a user of [this], it is included in the
1148 // returned set.
1149 Setlet<HInstruction> dominatedUsers(HInstruction other) {
1150 // Keep track of all instructions that we have to deal with later
1151 // and count the number of them that are in the current block.
1152 Setlet<HInstruction> users = new Setlet<HInstruction>();
1153 int usersInCurrentBlock = 0;
1154
1155 // Run through all the users and see if they are dominated or
1156 // potentially dominated by [other].
1157 HBasicBlock otherBlock = other.block;
1158 for (int i = 0, length = usedBy.length; i < length; i++) {
1159 HInstruction current = usedBy[i];
1160 if (otherBlock.dominates(current.block)) {
1161 if (identical(current.block, otherBlock)) usersInCurrentBlock++;
1162 users.add(current);
1163 }
1164 }
1165
1166 // Run through all the phis in the same block as [other] and remove them
1167 // from the users set.
1168 if (usersInCurrentBlock > 0) {
1169 for (HPhi phi = otherBlock.phis.first; phi != null; phi = phi.next) {
1170 if (users.contains(phi)) {
1171 users.remove(phi);
1172 if (--usersInCurrentBlock == 0) break;
1173 }
1174 }
1175 }
1176
1177 // Run through all the instructions before [other] and remove them
1178 // from the users set.
1179 if (usersInCurrentBlock > 0) {
1180 HInstruction current = otherBlock.first;
1181 while (!identical(current, other)) {
1182 if (users.contains(current)) {
1183 users.remove(current);
1184 if (--usersInCurrentBlock == 0) break;
1185 }
1186 current = current.next;
1187 }
1188 }
1189
1190 return users;
1191 }
1192
1193 void replaceAllUsersDominatedBy(HInstruction cursor,
1194 HInstruction newInstruction) {
1195 Setlet<HInstruction> users = dominatedUsers(cursor);
1196 for (HInstruction user in users) {
1197 user.changeUse(this, newInstruction);
1198 }
1199 }
1200
1201 void moveBefore(HInstruction other) {
1202 assert(this is !HControlFlow);
1203 assert(this is !HPhi);
1204 assert(other is !HPhi);
1205 block.detach(this);
1206 other.block.internalAddBefore(other, this);
1207 block = other.block;
1208 }
1209
1210 bool isConstant() => false;
1211 bool isConstantBoolean() => false;
1212 bool isConstantNull() => false;
1213 bool isConstantNumber() => false;
1214 bool isConstantInteger() => false;
1215 bool isConstantString() => false;
1216 bool isConstantList() => false;
1217 bool isConstantMap() => false;
1218 bool isConstantFalse() => false;
1219 bool isConstantTrue() => false;
1220
1221 bool isInterceptor(Compiler compiler) => false;
1222
1223 bool isValid() {
1224 HValidator validator = new HValidator();
1225 validator.currentBlock = block;
1226 validator.visitInstruction(this);
1227 return validator.isValid;
1228 }
1229
1230 bool isCodeMotionInvariant() => false;
1231
1232 bool isJsStatement() => false;
1233
1234 bool dominates(HInstruction other) {
1235 // An instruction does not dominates itself.
1236 if (this == other) return false;
1237 if (block != other.block) return block.dominates(other.block);
1238
1239 HInstruction current = this.next;
1240 while (current != null) {
1241 if (current == other) return true;
1242 current = current.next;
1243 }
1244 return false;
1245 }
1246
1247 HInstruction convertType(Compiler compiler, DartType type, int kind) {
1248 if (type == null) return this;
1249 type = type.unalias(compiler);
1250 // Only the builder knows how to create [HTypeConversion]
1251 // instructions with generics. It has the generic type context
1252 // available.
1253 assert(type.kind != TypeKind.TYPE_VARIABLE);
1254 assert(type.treatAsRaw || type.isFunctionType);
1255 if (type.isDynamic) return this;
1256 // The type element is either a class or the void element.
1257 Element element = type.element;
1258 if (identical(element, compiler.objectClass)) return this;
1259 JavaScriptBackend backend = compiler.backend;
1260 if (type.kind != TypeKind.INTERFACE) {
1261 return new HTypeConversion(type, kind, backend.dynamicType, this);
1262 } else if (kind == HTypeConversion.BOOLEAN_CONVERSION_CHECK) {
1263 // Boolean conversion checks work on non-nullable booleans.
1264 return new HTypeConversion(type, kind, backend.boolType, this);
1265 } else if (kind == HTypeConversion.CHECKED_MODE_CHECK && !type.treatAsRaw) {
1266 throw 'creating compound check to $type (this = ${this})';
1267 } else {
1268 TypeMask subtype = new TypeMask.subtype(element.declaration,
1269 compiler.world);
1270 return new HTypeConversion(type, kind, subtype, this);
1271 }
1272 }
1273
1274 /**
1275 * Return whether the instructions do not belong to a loop or
1276 * belong to the same loop.
1277 */
1278 bool hasSameLoopHeaderAs(HInstruction other) {
1279 return block.enclosingLoopHeader == other.block.enclosingLoopHeader;
1280 }
1281 }
1282
1283 /**
1284 * Late instructions are used after the main optimization phases. They capture
1285 * codegen decisions just prior to generating JavaScript.
1286 */
1287 abstract class HLateInstruction extends HInstruction {
1288 HLateInstruction(List<HInstruction> inputs, TypeMask type)
1289 : super(inputs, type);
1290 }
1291
1292 class HBoolify extends HInstruction {
1293 HBoolify(HInstruction value, TypeMask type)
1294 : super(<HInstruction>[value], type) {
1295 setUseGvn();
1296 }
1297
1298 accept(HVisitor visitor) => visitor.visitBoolify(this);
1299 int typeCode() => HInstruction.BOOLIFY_TYPECODE;
1300 bool typeEquals(other) => other is HBoolify;
1301 bool dataEquals(HInstruction other) => true;
1302 }
1303
1304 /**
1305 * A [HCheck] instruction is an instruction that might do a dynamic
1306 * check at runtime on another instruction. To have proper instruction
1307 * dependencies in the graph, instructions that depend on the check
1308 * being done reference the [HCheck] instruction instead of the
1309 * instruction itself.
1310 */
1311 abstract class HCheck extends HInstruction {
1312 HCheck(inputs, type) : super(inputs, type) {
1313 setUseGvn();
1314 }
1315 HInstruction get checkedInput => inputs[0];
1316 bool isJsStatement() => true;
1317 bool canThrow() => true;
1318
1319 HInstruction nonCheck() => checkedInput.nonCheck();
1320 }
1321
1322 class HBoundsCheck extends HCheck {
1323 static const int ALWAYS_FALSE = 0;
1324 static const int FULL_CHECK = 1;
1325 static const int ALWAYS_ABOVE_ZERO = 2;
1326 static const int ALWAYS_BELOW_LENGTH = 3;
1327 static const int ALWAYS_TRUE = 4;
1328 /**
1329 * Details which tests have been done statically during compilation.
1330 * Default is that all checks must be performed dynamically.
1331 */
1332 int staticChecks = FULL_CHECK;
1333
1334 HBoundsCheck(length, index, array, type)
1335 : super(<HInstruction>[length, index, array], type);
1336
1337 HInstruction get length => inputs[1];
1338 HInstruction get index => inputs[0];
1339 HInstruction get array => inputs[2];
1340 bool isControlFlow() => true;
1341
1342 accept(HVisitor visitor) => visitor.visitBoundsCheck(this);
1343 int typeCode() => HInstruction.BOUNDS_CHECK_TYPECODE;
1344 bool typeEquals(other) => other is HBoundsCheck;
1345 bool dataEquals(HInstruction other) => true;
1346 }
1347
1348 abstract class HConditionalBranch extends HControlFlow {
1349 HConditionalBranch(inputs) : super(inputs);
1350 HInstruction get condition => inputs[0];
1351 HBasicBlock get trueBranch => block.successors[0];
1352 HBasicBlock get falseBranch => block.successors[1];
1353 }
1354
1355 abstract class HControlFlow extends HInstruction {
1356 HControlFlow(inputs) : super(inputs, const TypeMask.nonNullEmpty());
1357 bool isControlFlow() => true;
1358 bool isJsStatement() => true;
1359 }
1360
1361 abstract class HInvoke extends HInstruction {
1362 /**
1363 * The first argument must be the target: either an [HStatic] node, or
1364 * the receiver of a method-call. The remaining inputs are the arguments
1365 * to the invocation.
1366 */
1367 HInvoke(List<HInstruction> inputs, type) : super(inputs, type) {
1368 sideEffects.setAllSideEffects();
1369 sideEffects.setDependsOnSomething();
1370 }
1371 static const int ARGUMENTS_OFFSET = 1;
1372 bool canThrow() => true;
1373
1374 /**
1375 * Returns whether this call is on an intercepted method.
1376 */
1377 bool get isInterceptedCall {
1378 // We know it's a selector call if it follows the interceptor
1379 // calling convention, which adds the actual receiver as a
1380 // parameter to the call.
1381 return (selector != null) && (inputs.length - 2 == selector.argumentCount);
1382 }
1383 }
1384
1385 abstract class HInvokeDynamic extends HInvoke {
1386 final InvokeDynamicSpecializer specializer;
1387 Selector selector;
1388 Element element;
1389
1390 HInvokeDynamic(Selector selector,
1391 this.element,
1392 List<HInstruction> inputs,
1393 TypeMask type,
1394 [bool isIntercepted = false])
1395 : super(inputs, type),
1396 this.selector = selector,
1397 specializer = isIntercepted
1398 ? InvokeDynamicSpecializer.lookupSpecializer(selector)
1399 : const InvokeDynamicSpecializer();
1400 toString() => 'invoke dynamic: $selector';
1401 HInstruction get receiver => inputs[0];
1402 HInstruction getDartReceiver(Compiler compiler) {
1403 return isCallOnInterceptor(compiler) ? inputs[1] : inputs[0];
1404 }
1405
1406 /**
1407 * Returns whether this call is on an interceptor object.
1408 */
1409 bool isCallOnInterceptor(Compiler compiler) {
1410 return isInterceptedCall && receiver.isInterceptor(compiler);
1411 }
1412
1413 int typeCode() => HInstruction.INVOKE_DYNAMIC_TYPECODE;
1414 bool typeEquals(other) => other is HInvokeDynamic;
1415 bool dataEquals(HInvokeDynamic other) {
1416 // Use the name and the kind instead of [Selector.operator==]
1417 // because we don't need to check the arity (already checked in
1418 // [gvnEquals]), and the receiver types may not be in sync.
1419 return selector.name == other.selector.name
1420 && selector.kind == other.selector.kind;
1421 }
1422 }
1423
1424 class HInvokeClosure extends HInvokeDynamic {
1425 HInvokeClosure(Selector selector, List<HInstruction> inputs, TypeMask type)
1426 : super(selector, null, inputs, type) {
1427 assert(selector.isClosureCall);
1428 }
1429 accept(HVisitor visitor) => visitor.visitInvokeClosure(this);
1430 }
1431
1432 class HInvokeDynamicMethod extends HInvokeDynamic {
1433 HInvokeDynamicMethod(Selector selector,
1434 List<HInstruction> inputs,
1435 TypeMask type,
1436 [bool isIntercepted = false])
1437 : super(selector, null, inputs, type, isIntercepted);
1438
1439 String toString() => 'invoke dynamic method: $selector';
1440 accept(HVisitor visitor) => visitor.visitInvokeDynamicMethod(this);
1441 }
1442
1443 abstract class HInvokeDynamicField extends HInvokeDynamic {
1444 HInvokeDynamicField(
1445 Selector selector, Element element, List<HInstruction> inputs,
1446 TypeMask type)
1447 : super(selector, element, inputs, type);
1448 toString() => 'invoke dynamic field: $selector';
1449 }
1450
1451 class HInvokeDynamicGetter extends HInvokeDynamicField {
1452 HInvokeDynamicGetter(selector, element, inputs, type)
1453 : super(selector, element, inputs, type);
1454 toString() => 'invoke dynamic getter: $selector';
1455 accept(HVisitor visitor) => visitor.visitInvokeDynamicGetter(this);
1456 }
1457
1458 class HInvokeDynamicSetter extends HInvokeDynamicField {
1459 HInvokeDynamicSetter(selector, element, inputs, type)
1460 : super(selector, element, inputs, type);
1461 toString() => 'invoke dynamic setter: $selector';
1462 accept(HVisitor visitor) => visitor.visitInvokeDynamicSetter(this);
1463 }
1464
1465 class HInvokeStatic extends HInvoke {
1466 final Element element;
1467
1468 final bool targetCanThrow;
1469
1470 bool canThrow() => targetCanThrow;
1471
1472 /// If this instruction is a call to a constructor, [instantiatedTypes]
1473 /// contains the type(s) used in the (Dart) `New` expression(s). The
1474 /// [instructionType] of this node is not enough, because we also need the
1475 /// type arguments. See also [SsaFromAstMixin.currentInlinedInstantiations].
1476 List<DartType> instantiatedTypes;
1477
1478 /** The first input must be the target. */
1479 HInvokeStatic(this.element, inputs, TypeMask type,
1480 {this.targetCanThrow: true})
1481 : super(inputs, type);
1482
1483 toString() => 'invoke static: $element';
1484 accept(HVisitor visitor) => visitor.visitInvokeStatic(this);
1485 int typeCode() => HInstruction.INVOKE_STATIC_TYPECODE;
1486 }
1487
1488 class HInvokeSuper extends HInvokeStatic {
1489 /** The class where the call to super is being done. */
1490 final ClassElement caller;
1491 final bool isSetter;
1492 final Selector selector;
1493
1494 HInvokeSuper(Element element,
1495 this.caller,
1496 this.selector,
1497 inputs,
1498 type,
1499 {this.isSetter})
1500 : super(element, inputs, type);
1501
1502 HInstruction get receiver => inputs[0];
1503 HInstruction getDartReceiver(Compiler compiler) {
1504 return isCallOnInterceptor(compiler) ? inputs[1] : inputs[0];
1505 }
1506
1507 /**
1508 * Returns whether this call is on an interceptor object.
1509 */
1510 bool isCallOnInterceptor(Compiler compiler) {
1511 return isInterceptedCall && receiver.isInterceptor(compiler);
1512 }
1513
1514 toString() => 'invoke super: $element';
1515 accept(HVisitor visitor) => visitor.visitInvokeSuper(this);
1516
1517 HInstruction get value {
1518 assert(isSetter);
1519 // The 'inputs' are [receiver, value] or [interceptor, receiver, value].
1520 return inputs.last;
1521 }
1522 }
1523
1524 class HInvokeConstructorBody extends HInvokeStatic {
1525 // The 'inputs' are
1526 // [receiver, arg1, ..., argN] or
1527 // [interceptor, receiver, arg1, ... argN].
1528 HInvokeConstructorBody(element, inputs, type)
1529 : super(element, inputs, type);
1530
1531 String toString() => 'invoke constructor body: ${element.name}';
1532 accept(HVisitor visitor) => visitor.visitInvokeConstructorBody(this);
1533 }
1534
1535 abstract class HFieldAccess extends HInstruction {
1536 final Element element;
1537
1538 HFieldAccess(Element element, List<HInstruction> inputs, TypeMask type)
1539 : this.element = element, super(inputs, type);
1540
1541 HInstruction get receiver => inputs[0];
1542 }
1543
1544 class HFieldGet extends HFieldAccess {
1545 final bool isAssignable;
1546
1547 HFieldGet(Element element,
1548 HInstruction receiver,
1549 TypeMask type,
1550 {bool isAssignable})
1551 : this.isAssignable = (isAssignable != null)
1552 ? isAssignable
1553 : element.isAssignable,
1554 super(element, <HInstruction>[receiver], type) {
1555 sideEffects.clearAllSideEffects();
1556 sideEffects.clearAllDependencies();
1557 setUseGvn();
1558 if (this.isAssignable) {
1559 sideEffects.setDependsOnInstancePropertyStore();
1560 }
1561 }
1562
1563 bool isInterceptor(Compiler compiler) {
1564 if (sourceElement == null) return false;
1565 // In case of a closure inside an interceptor class, [:this:] is
1566 // stored in the generated closure class, and accessed through a
1567 // [HFieldGet].
1568 JavaScriptBackend backend = compiler.backend;
1569 if (sourceElement is ThisLocal) {
1570 ThisLocal thisLocal = sourceElement;
1571 return backend.isInterceptorClass(thisLocal.enclosingClass);
1572 }
1573 return false;
1574 }
1575
1576 bool canThrow() => receiver.canBeNull();
1577
1578 HInstruction getDartReceiver(Compiler compiler) => receiver;
1579 bool onlyThrowsNSM() => true;
1580 bool get isNullCheck => element == null;
1581
1582 accept(HVisitor visitor) => visitor.visitFieldGet(this);
1583
1584 int typeCode() => HInstruction.FIELD_GET_TYPECODE;
1585 bool typeEquals(other) => other is HFieldGet;
1586 bool dataEquals(HFieldGet other) => element == other.element;
1587 String toString() => "FieldGet $element";
1588 }
1589
1590 class HFieldSet extends HFieldAccess {
1591 HFieldSet(Element element,
1592 HInstruction receiver,
1593 HInstruction value)
1594 : super(element, <HInstruction>[receiver, value],
1595 const TypeMask.nonNullEmpty()) {
1596 sideEffects.clearAllSideEffects();
1597 sideEffects.clearAllDependencies();
1598 sideEffects.setChangesInstanceProperty();
1599 }
1600
1601 bool canThrow() => receiver.canBeNull();
1602
1603 HInstruction getDartReceiver(Compiler compiler) => receiver;
1604 bool onlyThrowsNSM() => true;
1605
1606 HInstruction get value => inputs[1];
1607 accept(HVisitor visitor) => visitor.visitFieldSet(this);
1608
1609 bool isJsStatement() => true;
1610 String toString() => "FieldSet $element";
1611 }
1612
1613 /**
1614 * HReadModifyWrite is a late stage instruction for a field (property) update
1615 * via an assignment operation or pre- or post-increment.
1616 */
1617 class HReadModifyWrite extends HLateInstruction {
1618 static const ASSIGN_OP = 0;
1619 static const PRE_OP = 1;
1620 static const POST_OP = 2;
1621 final Element element;
1622 final String jsOp;
1623 final int opKind;
1624
1625 HReadModifyWrite._(Element this.element, this.jsOp, this.opKind,
1626 List<HInstruction> inputs, TypeMask type)
1627 : super(inputs, type) {
1628 sideEffects.clearAllSideEffects();
1629 sideEffects.clearAllDependencies();
1630 sideEffects.setChangesInstanceProperty();
1631 sideEffects.setDependsOnInstancePropertyStore();
1632 }
1633
1634 HReadModifyWrite.assignOp(Element element, String jsOp,
1635 HInstruction receiver, HInstruction operand, TypeMask type)
1636 : this._(element, jsOp, ASSIGN_OP,
1637 <HInstruction>[receiver, operand], type);
1638
1639 HReadModifyWrite.preOp(Element element, String jsOp,
1640 HInstruction receiver, TypeMask type)
1641 : this._(element, jsOp, PRE_OP, <HInstruction>[receiver], type);
1642
1643 HReadModifyWrite.postOp(Element element, String jsOp,
1644 HInstruction receiver, TypeMask type)
1645 : this._(element, jsOp, POST_OP, <HInstruction>[receiver], type);
1646
1647 HInstruction get receiver => inputs[0];
1648
1649 bool get isPreOp => opKind == PRE_OP;
1650 bool get isPostOp => opKind == POST_OP;
1651 bool get isAssignOp => opKind == ASSIGN_OP;
1652
1653 bool canThrow() => receiver.canBeNull();
1654
1655 HInstruction getDartReceiver(Compiler compiler) => receiver;
1656 bool onlyThrowsNSM() => true;
1657
1658 HInstruction get value => inputs[1];
1659 accept(HVisitor visitor) => visitor.visitReadModifyWrite(this);
1660
1661 bool isJsStatement() => isAssignOp;
1662 String toString() => "ReadModifyWrite $jsOp $opKind $element";
1663 }
1664
1665 abstract class HLocalAccess extends HInstruction {
1666 final Local variable;
1667
1668 HLocalAccess(this.variable, List<HInstruction> inputs, TypeMask type)
1669 : super(inputs, type);
1670
1671 HInstruction get receiver => inputs[0];
1672 }
1673
1674 class HLocalGet extends HLocalAccess {
1675 // No need to use GVN for a [HLocalGet], it is just a local
1676 // access.
1677 HLocalGet(Local variable, HLocalValue local, TypeMask type)
1678 : super(variable, <HInstruction>[local], type);
1679
1680 accept(HVisitor visitor) => visitor.visitLocalGet(this);
1681
1682 HLocalValue get local => inputs[0];
1683 }
1684
1685 class HLocalSet extends HLocalAccess {
1686 HLocalSet(Local variable, HLocalValue local, HInstruction value)
1687 : super(variable, <HInstruction>[local, value],
1688 const TypeMask.nonNullEmpty());
1689
1690 accept(HVisitor visitor) => visitor.visitLocalSet(this);
1691
1692 HLocalValue get local => inputs[0];
1693 HInstruction get value => inputs[1];
1694 bool isJsStatement() => true;
1695 }
1696
1697 class HForeign extends HInstruction {
1698 final js.Template codeTemplate;
1699 final bool isStatement;
1700 final bool _canThrow;
1701 final native.NativeBehavior nativeBehavior;
1702
1703 HForeign(this.codeTemplate,
1704 TypeMask type,
1705 List<HInstruction> inputs,
1706 {this.isStatement: false,
1707 SideEffects effects,
1708 native.NativeBehavior nativeBehavior,
1709 canThrow: false})
1710 : this.nativeBehavior = nativeBehavior,
1711 this._canThrow = canThrow,
1712 super(inputs, type) {
1713 if (effects == null && nativeBehavior != null) {
1714 effects = nativeBehavior.sideEffects;
1715 }
1716 if (effects != null) sideEffects.add(effects);
1717 }
1718
1719 HForeign.statement(codeTemplate, List<HInstruction> inputs,
1720 SideEffects effects,
1721 native.NativeBehavior nativeBehavior,
1722 TypeMask type)
1723 : this(codeTemplate, type, inputs, isStatement: true,
1724 effects: effects, nativeBehavior: nativeBehavior);
1725
1726 accept(HVisitor visitor) => visitor.visitForeign(this);
1727
1728 bool isJsStatement() => isStatement;
1729 bool canThrow() {
1730 return _canThrow
1731 || sideEffects.hasSideEffects()
1732 || sideEffects.dependsOnSomething();
1733 }
1734 }
1735
1736 class HForeignNew extends HForeign {
1737 ClassElement element;
1738
1739 /// If this field is not `null`, this call is from an inlined constructor and
1740 /// we have to register the instantiated type in the code generator. The
1741 /// [instructionType] of this node is not enough, because we also need the
1742 /// type arguments. See also [SsaFromAstMixin.currentInlinedInstantiations].
1743 List<DartType> instantiatedTypes;
1744
1745 HForeignNew(this.element, TypeMask type, List<HInstruction> inputs,
1746 [this.instantiatedTypes])
1747 : super(null, type, inputs);
1748
1749 accept(HVisitor visitor) => visitor.visitForeignNew(this);
1750 }
1751
1752 abstract class HInvokeBinary extends HInstruction {
1753 final Selector selector;
1754 HInvokeBinary(HInstruction left, HInstruction right, this.selector, type)
1755 : super(<HInstruction>[left, right], type) {
1756 sideEffects.clearAllSideEffects();
1757 sideEffects.clearAllDependencies();
1758 setUseGvn();
1759 }
1760
1761 HInstruction get left => inputs[0];
1762 HInstruction get right => inputs[1];
1763
1764 BinaryOperation operation(ConstantSystem constantSystem);
1765 }
1766
1767 abstract class HBinaryArithmetic extends HInvokeBinary {
1768 HBinaryArithmetic(left, right, selector, type)
1769 : super(left, right, selector, type);
1770 BinaryOperation operation(ConstantSystem constantSystem);
1771 }
1772
1773 class HAdd extends HBinaryArithmetic {
1774 HAdd(left, right, selector, type) : super(left, right, selector, type);
1775 accept(HVisitor visitor) => visitor.visitAdd(this);
1776
1777 BinaryOperation operation(ConstantSystem constantSystem)
1778 => constantSystem.add;
1779 int typeCode() => HInstruction.ADD_TYPECODE;
1780 bool typeEquals(other) => other is HAdd;
1781 bool dataEquals(HInstruction other) => true;
1782 }
1783
1784 class HDivide extends HBinaryArithmetic {
1785 HDivide(left, right, selector, type) : super(left, right, selector, type);
1786 accept(HVisitor visitor) => visitor.visitDivide(this);
1787
1788 BinaryOperation operation(ConstantSystem constantSystem)
1789 => constantSystem.divide;
1790 int typeCode() => HInstruction.DIVIDE_TYPECODE;
1791 bool typeEquals(other) => other is HDivide;
1792 bool dataEquals(HInstruction other) => true;
1793 }
1794
1795 class HMultiply extends HBinaryArithmetic {
1796 HMultiply(left, right, selector, type) : super(left, right, selector, type);
1797 accept(HVisitor visitor) => visitor.visitMultiply(this);
1798
1799 BinaryOperation operation(ConstantSystem operations)
1800 => operations.multiply;
1801 int typeCode() => HInstruction.MULTIPLY_TYPECODE;
1802 bool typeEquals(other) => other is HMultiply;
1803 bool dataEquals(HInstruction other) => true;
1804 }
1805
1806 class HSubtract extends HBinaryArithmetic {
1807 HSubtract(left, right, selector, type) : super(left, right, selector, type);
1808 accept(HVisitor visitor) => visitor.visitSubtract(this);
1809
1810 BinaryOperation operation(ConstantSystem constantSystem)
1811 => constantSystem.subtract;
1812 int typeCode() => HInstruction.SUBTRACT_TYPECODE;
1813 bool typeEquals(other) => other is HSubtract;
1814 bool dataEquals(HInstruction other) => true;
1815 }
1816
1817 class HTruncatingDivide extends HBinaryArithmetic {
1818 HTruncatingDivide(left, right, selector, type)
1819 : super(left, right, selector, type);
1820 accept(HVisitor visitor) => visitor.visitTruncatingDivide(this);
1821
1822 BinaryOperation operation(ConstantSystem constantSystem)
1823 => constantSystem.truncatingDivide;
1824 int typeCode() => HInstruction.TRUNCATING_DIVIDE_TYPECODE;
1825 bool typeEquals(other) => other is HTruncatingDivide;
1826 bool dataEquals(HInstruction other) => true;
1827 }
1828
1829 /**
1830 * An [HSwitch] instruction has one input for the incoming
1831 * value, and one input per constant that it can switch on.
1832 * Its block has one successor per constant, and one for the default.
1833 */
1834 class HSwitch extends HControlFlow {
1835 HSwitch(List<HInstruction> inputs) : super(inputs);
1836
1837 HConstant constant(int index) => inputs[index + 1];
1838 HInstruction get expression => inputs[0];
1839
1840 /**
1841 * Provides the target to jump to if none of the constants match
1842 * the expression. If the switch had no default case, this is the
1843 * following join-block.
1844 */
1845 HBasicBlock get defaultTarget => block.successors.last;
1846
1847 accept(HVisitor visitor) => visitor.visitSwitch(this);
1848
1849 String toString() => "HSwitch cases = $inputs";
1850 }
1851
1852 abstract class HBinaryBitOp extends HInvokeBinary {
1853 HBinaryBitOp(left, right, selector, type)
1854 : super(left, right, selector, type);
1855 }
1856
1857 class HShiftLeft extends HBinaryBitOp {
1858 HShiftLeft(left, right, selector, type) : super(left, right, selector, type);
1859 accept(HVisitor visitor) => visitor.visitShiftLeft(this);
1860
1861 BinaryOperation operation(ConstantSystem constantSystem)
1862 => constantSystem.shiftLeft;
1863 int typeCode() => HInstruction.SHIFT_LEFT_TYPECODE;
1864 bool typeEquals(other) => other is HShiftLeft;
1865 bool dataEquals(HInstruction other) => true;
1866 }
1867
1868 class HShiftRight extends HBinaryBitOp {
1869 HShiftRight(left, right, selector, type) : super(left, right, selector, type);
1870 accept(HVisitor visitor) => visitor.visitShiftRight(this);
1871
1872 BinaryOperation operation(ConstantSystem constantSystem)
1873 => constantSystem.shiftRight;
1874 int typeCode() => HInstruction.SHIFT_RIGHT_TYPECODE;
1875 bool typeEquals(other) => other is HShiftRight;
1876 bool dataEquals(HInstruction other) => true;
1877 }
1878
1879 class HBitOr extends HBinaryBitOp {
1880 HBitOr(left, right, selector, type) : super(left, right, selector, type);
1881 accept(HVisitor visitor) => visitor.visitBitOr(this);
1882
1883 BinaryOperation operation(ConstantSystem constantSystem)
1884 => constantSystem.bitOr;
1885 int typeCode() => HInstruction.BIT_OR_TYPECODE;
1886 bool typeEquals(other) => other is HBitOr;
1887 bool dataEquals(HInstruction other) => true;
1888 }
1889
1890 class HBitAnd extends HBinaryBitOp {
1891 HBitAnd(left, right, selector, type) : super(left, right, selector, type);
1892 accept(HVisitor visitor) => visitor.visitBitAnd(this);
1893
1894 BinaryOperation operation(ConstantSystem constantSystem)
1895 => constantSystem.bitAnd;
1896 int typeCode() => HInstruction.BIT_AND_TYPECODE;
1897 bool typeEquals(other) => other is HBitAnd;
1898 bool dataEquals(HInstruction other) => true;
1899 }
1900
1901 class HBitXor extends HBinaryBitOp {
1902 HBitXor(left, right, selector, type) : super(left, right, selector, type);
1903 accept(HVisitor visitor) => visitor.visitBitXor(this);
1904
1905 BinaryOperation operation(ConstantSystem constantSystem)
1906 => constantSystem.bitXor;
1907 int typeCode() => HInstruction.BIT_XOR_TYPECODE;
1908 bool typeEquals(other) => other is HBitXor;
1909 bool dataEquals(HInstruction other) => true;
1910 }
1911
1912 abstract class HInvokeUnary extends HInstruction {
1913 final Selector selector;
1914 HInvokeUnary(HInstruction input, this.selector, type)
1915 : super(<HInstruction>[input], type) {
1916 sideEffects.clearAllSideEffects();
1917 sideEffects.clearAllDependencies();
1918 setUseGvn();
1919 }
1920
1921 HInstruction get operand => inputs[0];
1922
1923 UnaryOperation operation(ConstantSystem constantSystem);
1924 }
1925
1926 class HNegate extends HInvokeUnary {
1927 HNegate(input, selector, type) : super(input, selector, type);
1928 accept(HVisitor visitor) => visitor.visitNegate(this);
1929
1930 UnaryOperation operation(ConstantSystem constantSystem)
1931 => constantSystem.negate;
1932 int typeCode() => HInstruction.NEGATE_TYPECODE;
1933 bool typeEquals(other) => other is HNegate;
1934 bool dataEquals(HInstruction other) => true;
1935 }
1936
1937 class HBitNot extends HInvokeUnary {
1938 HBitNot(input, selector, type) : super(input, selector, type);
1939 accept(HVisitor visitor) => visitor.visitBitNot(this);
1940
1941 UnaryOperation operation(ConstantSystem constantSystem)
1942 => constantSystem.bitNot;
1943 int typeCode() => HInstruction.BIT_NOT_TYPECODE;
1944 bool typeEquals(other) => other is HBitNot;
1945 bool dataEquals(HInstruction other) => true;
1946 }
1947
1948 class HExit extends HControlFlow {
1949 HExit() : super(const <HInstruction>[]);
1950 toString() => 'exit';
1951 accept(HVisitor visitor) => visitor.visitExit(this);
1952 }
1953
1954 class HGoto extends HControlFlow {
1955 HGoto() : super(const <HInstruction>[]);
1956 toString() => 'goto';
1957 accept(HVisitor visitor) => visitor.visitGoto(this);
1958 }
1959
1960 abstract class HJump extends HControlFlow {
1961 final JumpTarget target;
1962 final LabelDefinition label;
1963 HJump(this.target) : label = null, super(const <HInstruction>[]);
1964 HJump.toLabel(LabelDefinition label)
1965 : label = label, target = label.target, super(const <HInstruction>[]);
1966 }
1967
1968 class HBreak extends HJump {
1969 /**
1970 * Signals that this is a special break instruction for the synthetic loop
1971 * generatedfor a switch statement with continue statements. See
1972 * [SsaFromAstMixin.buildComplexSwitchStatement] for detail.
1973 */
1974 final bool breakSwitchContinueLoop;
1975 HBreak(JumpTarget target, {bool this.breakSwitchContinueLoop: false})
1976 : super(target);
1977 HBreak.toLabel(LabelDefinition label)
1978 : breakSwitchContinueLoop = false, super.toLabel(label);
1979 toString() => (label != null) ? 'break ${label.labelName}' : 'break';
1980 accept(HVisitor visitor) => visitor.visitBreak(this);
1981 }
1982
1983 class HContinue extends HJump {
1984 HContinue(JumpTarget target) : super(target);
1985 HContinue.toLabel(LabelDefinition label) : super.toLabel(label);
1986 toString() => (label != null) ? 'continue ${label.labelName}' : 'continue';
1987 accept(HVisitor visitor) => visitor.visitContinue(this);
1988 }
1989
1990 class HTry extends HControlFlow {
1991 HLocalValue exception;
1992 HBasicBlock catchBlock;
1993 HBasicBlock finallyBlock;
1994 HTry() : super(const <HInstruction>[]);
1995 toString() => 'try';
1996 accept(HVisitor visitor) => visitor.visitTry(this);
1997 HBasicBlock get joinBlock => this.block.successors.last;
1998 }
1999
2000 // An [HExitTry] control flow node is used when the body of a try or
2001 // the body of a catch contains a return, break or continue. To build
2002 // the control flow graph, we explicitly mark the body that
2003 // leads to one of this instruction a predecessor of catch and
2004 // finally.
2005 class HExitTry extends HControlFlow {
2006 HExitTry() : super(const <HInstruction>[]);
2007 toString() => 'exit try';
2008 accept(HVisitor visitor) => visitor.visitExitTry(this);
2009 HBasicBlock get bodyTrySuccessor => block.successors[0];
2010 }
2011
2012 class HIf extends HConditionalBranch {
2013 HBlockFlow blockInformation = null;
2014 HIf(HInstruction condition) : super(<HInstruction>[condition]);
2015 toString() => 'if';
2016 accept(HVisitor visitor) => visitor.visitIf(this);
2017
2018 HBasicBlock get thenBlock {
2019 assert(identical(block.dominatedBlocks[0], block.successors[0]));
2020 return block.successors[0];
2021 }
2022
2023 HBasicBlock get elseBlock {
2024 assert(identical(block.dominatedBlocks[1], block.successors[1]));
2025 return block.successors[1];
2026 }
2027
2028 HBasicBlock get joinBlock => blockInformation.continuation;
2029 }
2030
2031 class HLoopBranch extends HConditionalBranch {
2032 static const int CONDITION_FIRST_LOOP = 0;
2033 static const int DO_WHILE_LOOP = 1;
2034
2035 final int kind;
2036 HLoopBranch(HInstruction condition, [this.kind = CONDITION_FIRST_LOOP])
2037 : super(<HInstruction>[condition]);
2038 toString() => 'loop-branch';
2039 accept(HVisitor visitor) => visitor.visitLoopBranch(this);
2040 }
2041
2042 class HConstant extends HInstruction {
2043 final ConstantValue constant;
2044 HConstant.internal(this.constant, TypeMask constantType)
2045 : super(<HInstruction>[], constantType);
2046
2047 toString() => 'literal: $constant';
2048 accept(HVisitor visitor) => visitor.visitConstant(this);
2049
2050 bool isConstant() => true;
2051 bool isConstantBoolean() => constant.isBool;
2052 bool isConstantNull() => constant.isNull;
2053 bool isConstantNumber() => constant.isNum;
2054 bool isConstantInteger() => constant.isInt;
2055 bool isConstantString() => constant.isString;
2056 bool isConstantList() => constant.isList;
2057 bool isConstantMap() => constant.isMap;
2058 bool isConstantFalse() => constant.isFalse;
2059 bool isConstantTrue() => constant.isTrue;
2060
2061 bool isInterceptor(Compiler compiler) => constant.isInterceptor;
2062
2063 // Maybe avoid this if the literal is big?
2064 bool isCodeMotionInvariant() => true;
2065
2066 set instructionType(type) {
2067 // Only lists can be specialized. The SSA builder uses the
2068 // inferrer for finding the type of a constant list. We should
2069 // have the constant know its type instead.
2070 if (!isConstantList()) return;
2071 super.instructionType = type;
2072 }
2073 }
2074
2075 class HNot extends HInstruction {
2076 HNot(HInstruction value, TypeMask type) : super(<HInstruction>[value], type) {
2077 setUseGvn();
2078 }
2079
2080 accept(HVisitor visitor) => visitor.visitNot(this);
2081 int typeCode() => HInstruction.NOT_TYPECODE;
2082 bool typeEquals(other) => other is HNot;
2083 bool dataEquals(HInstruction other) => true;
2084 }
2085
2086 /**
2087 * An [HLocalValue] represents a local. Unlike [HParameterValue]s its
2088 * first use must be in an HLocalSet. That is, [HParameterValue]s have a
2089 * value from the start, whereas [HLocalValue]s need to be initialized first.
2090 */
2091 class HLocalValue extends HInstruction {
2092 HLocalValue(Entity variable, TypeMask type)
2093 : super(<HInstruction>[], type) {
2094 sourceElement = variable;
2095 }
2096
2097 toString() => 'local ${sourceElement.name}';
2098 accept(HVisitor visitor) => visitor.visitLocalValue(this);
2099 }
2100
2101 class HParameterValue extends HLocalValue {
2102 HParameterValue(Entity variable, type) : super(variable, type);
2103
2104 toString() => 'parameter ${sourceElement.name}';
2105 accept(HVisitor visitor) => visitor.visitParameterValue(this);
2106 }
2107
2108 class HThis extends HParameterValue {
2109 HThis(ThisLocal element, TypeMask type) : super(element, type);
2110
2111 ThisLocal get sourceElement => super.sourceElement;
2112
2113 accept(HVisitor visitor) => visitor.visitThis(this);
2114
2115 bool isCodeMotionInvariant() => true;
2116
2117 bool isInterceptor(Compiler compiler) {
2118 JavaScriptBackend backend = compiler.backend;
2119 return backend.isInterceptorClass(sourceElement.enclosingClass);
2120 }
2121
2122 String toString() => 'this';
2123 }
2124
2125 class HPhi extends HInstruction {
2126 static const IS_NOT_LOGICAL_OPERATOR = 0;
2127 static const IS_AND = 1;
2128 static const IS_OR = 2;
2129
2130 int logicalOperatorType = IS_NOT_LOGICAL_OPERATOR;
2131
2132 // The order of the [inputs] must correspond to the order of the
2133 // predecessor-edges. That is if an input comes from the first predecessor
2134 // of the surrounding block, then the input must be the first in the [HPhi].
2135 HPhi(Local variable, List<HInstruction> inputs, TypeMask type)
2136 : super(inputs, type) {
2137 sourceElement = variable;
2138 }
2139 HPhi.noInputs(Local variable, TypeMask type)
2140 : this(variable, <HInstruction>[], type);
2141 HPhi.singleInput(Local variable, HInstruction input, TypeMask type)
2142 : this(variable, <HInstruction>[input], type);
2143 HPhi.manyInputs(Local variable,
2144 List<HInstruction> inputs,
2145 TypeMask type)
2146 : this(variable, inputs, type);
2147
2148 void addInput(HInstruction input) {
2149 assert(isInBasicBlock());
2150 inputs.add(input);
2151 assert(inputs.length <= block.predecessors.length);
2152 input.usedBy.add(this);
2153 }
2154
2155 toString() => 'phi';
2156 accept(HVisitor visitor) => visitor.visitPhi(this);
2157 }
2158
2159 abstract class HRelational extends HInvokeBinary {
2160 bool usesBoolifiedInterceptor = false;
2161 HRelational(left, right, selector, type) : super(left, right, selector, type);
2162 }
2163
2164 class HIdentity extends HRelational {
2165 // Cached codegen decision.
2166 String singleComparisonOp; // null, '===', '=='
2167
2168 HIdentity(left, right, selector, type) : super(left, right, selector, type);
2169 accept(HVisitor visitor) => visitor.visitIdentity(this);
2170
2171 BinaryOperation operation(ConstantSystem constantSystem)
2172 => constantSystem.identity;
2173 int typeCode() => HInstruction.IDENTITY_TYPECODE;
2174 bool typeEquals(other) => other is HIdentity;
2175 bool dataEquals(HInstruction other) => true;
2176 }
2177
2178 class HGreater extends HRelational {
2179 HGreater(left, right, selector, type) : super(left, right, selector, type);
2180 accept(HVisitor visitor) => visitor.visitGreater(this);
2181
2182 BinaryOperation operation(ConstantSystem constantSystem)
2183 => constantSystem.greater;
2184 int typeCode() => HInstruction.GREATER_TYPECODE;
2185 bool typeEquals(other) => other is HGreater;
2186 bool dataEquals(HInstruction other) => true;
2187 }
2188
2189 class HGreaterEqual extends HRelational {
2190 HGreaterEqual(left, right, selector, type)
2191 : super(left, right, selector, type);
2192 accept(HVisitor visitor) => visitor.visitGreaterEqual(this);
2193
2194 BinaryOperation operation(ConstantSystem constantSystem)
2195 => constantSystem.greaterEqual;
2196 int typeCode() => HInstruction.GREATER_EQUAL_TYPECODE;
2197 bool typeEquals(other) => other is HGreaterEqual;
2198 bool dataEquals(HInstruction other) => true;
2199 }
2200
2201 class HLess extends HRelational {
2202 HLess(left, right, selector, type) : super(left, right, selector, type);
2203 accept(HVisitor visitor) => visitor.visitLess(this);
2204
2205 BinaryOperation operation(ConstantSystem constantSystem)
2206 => constantSystem.less;
2207 int typeCode() => HInstruction.LESS_TYPECODE;
2208 bool typeEquals(other) => other is HLess;
2209 bool dataEquals(HInstruction other) => true;
2210 }
2211
2212 class HLessEqual extends HRelational {
2213 HLessEqual(left, right, selector, type) : super(left, right, selector, type);
2214 accept(HVisitor visitor) => visitor.visitLessEqual(this);
2215
2216 BinaryOperation operation(ConstantSystem constantSystem)
2217 => constantSystem.lessEqual;
2218 int typeCode() => HInstruction.LESS_EQUAL_TYPECODE;
2219 bool typeEquals(other) => other is HLessEqual;
2220 bool dataEquals(HInstruction other) => true;
2221 }
2222
2223 class HReturn extends HControlFlow {
2224 HReturn(value) : super(<HInstruction>[value]);
2225 toString() => 'return';
2226 accept(HVisitor visitor) => visitor.visitReturn(this);
2227 }
2228
2229 class HThrowExpression extends HInstruction {
2230 HThrowExpression(value)
2231 : super(<HInstruction>[value], const TypeMask.nonNullEmpty());
2232 toString() => 'throw expression';
2233 accept(HVisitor visitor) => visitor.visitThrowExpression(this);
2234 bool canThrow() => true;
2235 }
2236
2237 class HThrow extends HControlFlow {
2238 final bool isRethrow;
2239 HThrow(value, {this.isRethrow: false}) : super(<HInstruction>[value]);
2240 toString() => 'throw';
2241 accept(HVisitor visitor) => visitor.visitThrow(this);
2242 }
2243
2244 class HStatic extends HInstruction {
2245 final Element element;
2246 HStatic(this.element, type) : super(<HInstruction>[], type) {
2247 assert(element != null);
2248 assert(invariant(this, element.isDeclaration));
2249 sideEffects.clearAllSideEffects();
2250 sideEffects.clearAllDependencies();
2251 if (element.isAssignable) {
2252 sideEffects.setDependsOnStaticPropertyStore();
2253 }
2254 setUseGvn();
2255 }
2256 toString() => 'static ${element.name}';
2257 accept(HVisitor visitor) => visitor.visitStatic(this);
2258
2259 int gvnHashCode() => super.gvnHashCode() ^ element.hashCode;
2260 int typeCode() => HInstruction.STATIC_TYPECODE;
2261 bool typeEquals(other) => other is HStatic;
2262 bool dataEquals(HStatic other) => element == other.element;
2263 bool isCodeMotionInvariant() => !element.isAssignable;
2264 }
2265
2266 class HInterceptor extends HInstruction {
2267 // This field should originally be null to allow GVN'ing all
2268 // [HInterceptor] on the same input.
2269 Set<ClassElement> interceptedClasses;
2270 HInterceptor(HInstruction receiver, TypeMask type)
2271 : super(<HInstruction>[receiver], type) {
2272 sideEffects.clearAllSideEffects();
2273 sideEffects.clearAllDependencies();
2274 setUseGvn();
2275 }
2276 String toString() => 'interceptor on $interceptedClasses';
2277 accept(HVisitor visitor) => visitor.visitInterceptor(this);
2278 HInstruction get receiver => inputs[0];
2279 bool isInterceptor(Compiler compiler) => true;
2280
2281 int typeCode() => HInstruction.INTERCEPTOR_TYPECODE;
2282 bool typeEquals(other) => other is HInterceptor;
2283 bool dataEquals(HInterceptor other) {
2284 return interceptedClasses == other.interceptedClasses
2285 || (interceptedClasses.length == other.interceptedClasses.length
2286 && interceptedClasses.containsAll(other.interceptedClasses));
2287 }
2288 }
2289
2290 /**
2291 * A "one-shot" interceptor is a call to a synthetized method that
2292 * will fetch the interceptor of its first parameter, and make a call
2293 * on a given selector with the remaining parameters.
2294 *
2295 * In order to share the same optimizations with regular interceptor
2296 * calls, this class extends [HInvokeDynamic] and also has the null
2297 * constant as the first input.
2298 */
2299 class HOneShotInterceptor extends HInvokeDynamic {
2300 Set<ClassElement> interceptedClasses;
2301 HOneShotInterceptor(Selector selector,
2302 List<HInstruction> inputs,
2303 TypeMask type,
2304 this.interceptedClasses)
2305 : super(selector, null, inputs, type, true) {
2306 assert(inputs[0] is HConstant);
2307 assert(inputs[0].isNull());
2308 }
2309 bool isCallOnInterceptor(Compiler compiler) => true;
2310
2311 String toString() => 'one shot interceptor on $selector';
2312 accept(HVisitor visitor) => visitor.visitOneShotInterceptor(this);
2313 }
2314
2315 /** An [HLazyStatic] is a static that is initialized lazily at first read. */
2316 class HLazyStatic extends HInstruction {
2317 final Element element;
2318 HLazyStatic(this.element, type) : super(<HInstruction>[], type) {
2319 // TODO(4931): The first access has side-effects, but we afterwards we
2320 // should be able to GVN.
2321 sideEffects.setAllSideEffects();
2322 sideEffects.setDependsOnSomething();
2323 }
2324
2325 toString() => 'lazy static ${element.name}';
2326 accept(HVisitor visitor) => visitor.visitLazyStatic(this);
2327
2328 int typeCode() => 30;
2329 // TODO(4931): can we do better here?
2330 bool isCodeMotionInvariant() => false;
2331 bool canThrow() => true;
2332 }
2333
2334 class HStaticStore extends HInstruction {
2335 Element element;
2336 HStaticStore(this.element, HInstruction value)
2337 : super(<HInstruction>[value], const TypeMask.nonNullEmpty()) {
2338 sideEffects.clearAllSideEffects();
2339 sideEffects.clearAllDependencies();
2340 sideEffects.setChangesStaticProperty();
2341 }
2342 toString() => 'static store ${element.name}';
2343 accept(HVisitor visitor) => visitor.visitStaticStore(this);
2344
2345 int typeCode() => HInstruction.STATIC_STORE_TYPECODE;
2346 bool typeEquals(other) => other is HStaticStore;
2347 bool dataEquals(HStaticStore other) => element == other.element;
2348 bool isJsStatement() => true;
2349 }
2350
2351 class HLiteralList extends HInstruction {
2352 HLiteralList(List<HInstruction> inputs, TypeMask type) : super(inputs, type);
2353 toString() => 'literal list';
2354 accept(HVisitor visitor) => visitor.visitLiteralList(this);
2355 }
2356
2357 /**
2358 * The primitive array indexing operation. Note that this instruction
2359 * does not throw because we generate the checks explicitly.
2360 */
2361 class HIndex extends HInstruction {
2362 final Selector selector;
2363 HIndex(HInstruction receiver, HInstruction index, this.selector, type)
2364 : super(<HInstruction>[receiver, index], type) {
2365 sideEffects.clearAllSideEffects();
2366 sideEffects.clearAllDependencies();
2367 sideEffects.setDependsOnIndexStore();
2368 setUseGvn();
2369 }
2370
2371 String toString() => 'index operator';
2372 accept(HVisitor visitor) => visitor.visitIndex(this);
2373
2374 HInstruction get receiver => inputs[0];
2375 HInstruction get index => inputs[1];
2376
2377 HInstruction getDartReceiver(Compiler compiler) => receiver;
2378 bool onlyThrowsNSM() => true;
2379 bool canThrow() => receiver.canBeNull();
2380
2381 int typeCode() => HInstruction.INDEX_TYPECODE;
2382 bool typeEquals(HInstruction other) => other is HIndex;
2383 bool dataEquals(HIndex other) => true;
2384 }
2385
2386 /**
2387 * The primitive array assignment operation. Note that this instruction
2388 * does not throw because we generate the checks explicitly.
2389 */
2390 class HIndexAssign extends HInstruction {
2391 final Selector selector;
2392 HIndexAssign(HInstruction receiver,
2393 HInstruction index,
2394 HInstruction value,
2395 this.selector)
2396 : super(<HInstruction>[receiver, index, value],
2397 const TypeMask.nonNullEmpty()) {
2398 sideEffects.clearAllSideEffects();
2399 sideEffects.clearAllDependencies();
2400 sideEffects.setChangesIndex();
2401 }
2402 String toString() => 'index assign operator';
2403 accept(HVisitor visitor) => visitor.visitIndexAssign(this);
2404
2405 HInstruction get receiver => inputs[0];
2406 HInstruction get index => inputs[1];
2407 HInstruction get value => inputs[2];
2408
2409 HInstruction getDartReceiver(Compiler compiler) => receiver;
2410 bool onlyThrowsNSM() => true;
2411 bool canThrow() => receiver.canBeNull();
2412 }
2413
2414 class HIs extends HInstruction {
2415 /// A check against a raw type: 'o is int', 'o is A'.
2416 static const int RAW_CHECK = 0;
2417 /// A check against a type with type arguments: 'o is List<int>', 'o is C<T>'.
2418 static const int COMPOUND_CHECK = 1;
2419 /// A check against a single type variable: 'o is T'.
2420 static const int VARIABLE_CHECK = 2;
2421
2422 final DartType typeExpression;
2423 final int kind;
2424
2425 HIs.direct(DartType typeExpression,
2426 HInstruction expression,
2427 TypeMask type)
2428 : this.internal(typeExpression, [expression], RAW_CHECK, type);
2429
2430 HIs.raw(DartType typeExpression,
2431 HInstruction expression,
2432 HInterceptor interceptor,
2433 TypeMask type)
2434 : this.internal(
2435 typeExpression, [expression, interceptor], RAW_CHECK, type);
2436
2437 HIs.compound(DartType typeExpression,
2438 HInstruction expression,
2439 HInstruction call,
2440 TypeMask type)
2441 : this.internal(typeExpression, [expression, call], COMPOUND_CHECK, type);
2442
2443 HIs.variable(DartType typeExpression,
2444 HInstruction expression,
2445 HInstruction call,
2446 TypeMask type)
2447 : this.internal(typeExpression, [expression, call], VARIABLE_CHECK, type);
2448
2449 HIs.internal(this.typeExpression, List<HInstruction> inputs, this.kind, type)
2450 : super(inputs, type) {
2451 assert(kind >= RAW_CHECK && kind <= VARIABLE_CHECK);
2452 setUseGvn();
2453 }
2454
2455 HInstruction get expression => inputs[0];
2456
2457 HInstruction get interceptor {
2458 assert(kind == RAW_CHECK);
2459 return inputs.length > 1 ? inputs[1] : null;
2460 }
2461
2462 HInstruction get checkCall {
2463 assert(kind == VARIABLE_CHECK || kind == COMPOUND_CHECK);
2464 return inputs[1];
2465 }
2466
2467 bool get isRawCheck => kind == RAW_CHECK;
2468 bool get isVariableCheck => kind == VARIABLE_CHECK;
2469 bool get isCompoundCheck => kind == COMPOUND_CHECK;
2470
2471 accept(HVisitor visitor) => visitor.visitIs(this);
2472
2473 toString() => "$expression is $typeExpression";
2474
2475 int typeCode() => HInstruction.IS_TYPECODE;
2476
2477 bool typeEquals(HInstruction other) => other is HIs;
2478
2479 bool dataEquals(HIs other) {
2480 return typeExpression == other.typeExpression
2481 && kind == other.kind;
2482 }
2483 }
2484
2485 /**
2486 * HIsViaInterceptor is a late-stage instruction for a type test that can be
2487 * done entirely on an interceptor. It is not a HCheck because the checked
2488 * input is not one of the inputs.
2489 */
2490 class HIsViaInterceptor extends HLateInstruction {
2491 final DartType typeExpression;
2492 HIsViaInterceptor(this.typeExpression, HInstruction interceptor,
2493 TypeMask type)
2494 : super(<HInstruction>[interceptor], type) {
2495 setUseGvn();
2496 }
2497
2498 HInstruction get interceptor => inputs[0];
2499
2500 accept(HVisitor visitor) => visitor.visitIsViaInterceptor(this);
2501 toString() => "$interceptor is $typeExpression";
2502 int typeCode() => HInstruction.IS_VIA_INTERCEPTOR_TYPECODE;
2503 bool typeEquals(HInstruction other) => other is HIsViaInterceptor;
2504 bool dataEquals(HIs other) {
2505 return typeExpression == other.typeExpression;
2506 }
2507 }
2508
2509 class HTypeConversion extends HCheck {
2510 final DartType typeExpression;
2511 final int kind;
2512 final Selector receiverTypeCheckSelector;
2513 final bool contextIsTypeArguments;
2514 TypeMask checkedType; // Not final because we refine it.
2515
2516 static const int CHECKED_MODE_CHECK = 0;
2517 static const int ARGUMENT_TYPE_CHECK = 1;
2518 static const int CAST_TYPE_CHECK = 2;
2519 static const int BOOLEAN_CONVERSION_CHECK = 3;
2520 static const int RECEIVER_TYPE_CHECK = 4;
2521
2522 HTypeConversion(this.typeExpression, this.kind,
2523 TypeMask type, HInstruction input,
2524 [this.receiverTypeCheckSelector])
2525 : contextIsTypeArguments = false,
2526 checkedType = type,
2527 super(<HInstruction>[input], type) {
2528 assert(!isReceiverTypeCheck || receiverTypeCheckSelector != null);
2529 assert(typeExpression == null ||
2530 typeExpression.kind != TypeKind.TYPEDEF);
2531 sourceElement = input.sourceElement;
2532 }
2533
2534 HTypeConversion.withTypeRepresentation(this.typeExpression, this.kind,
2535 TypeMask type, HInstruction input,
2536 HInstruction typeRepresentation)
2537 : contextIsTypeArguments = false,
2538 checkedType = type,
2539 super(<HInstruction>[input, typeRepresentation],type),
2540 receiverTypeCheckSelector = null {
2541 assert(typeExpression.kind != TypeKind.TYPEDEF);
2542 sourceElement = input.sourceElement;
2543 }
2544
2545 HTypeConversion.withContext(this.typeExpression, this.kind,
2546 TypeMask type, HInstruction input,
2547 HInstruction context,
2548 {bool this.contextIsTypeArguments})
2549 : super(<HInstruction>[input, context], type),
2550 checkedType = type,
2551 receiverTypeCheckSelector = null {
2552 assert(typeExpression.kind != TypeKind.TYPEDEF);
2553 sourceElement = input.sourceElement;
2554 }
2555
2556 bool get hasTypeRepresentation {
2557 return typeExpression.isInterfaceType && inputs.length > 1;
2558 }
2559 HInstruction get typeRepresentation => inputs[1];
2560
2561 bool get hasContext {
2562 return typeExpression.isFunctionType && inputs.length > 1;
2563 }
2564 HInstruction get context => inputs[1];
2565
2566 HInstruction convertType(Compiler compiler, DartType type, int kind) {
2567 if (typeExpression == type) return this;
2568 return super.convertType(compiler, type, kind);
2569 }
2570
2571 bool get isCheckedModeCheck {
2572 return kind == CHECKED_MODE_CHECK
2573 || kind == BOOLEAN_CONVERSION_CHECK;
2574 }
2575 bool get isArgumentTypeCheck => kind == ARGUMENT_TYPE_CHECK;
2576 bool get isReceiverTypeCheck => kind == RECEIVER_TYPE_CHECK;
2577 bool get isCastTypeCheck => kind == CAST_TYPE_CHECK;
2578 bool get isBooleanConversionCheck => kind == BOOLEAN_CONVERSION_CHECK;
2579
2580 accept(HVisitor visitor) => visitor.visitTypeConversion(this);
2581
2582 bool isJsStatement() => isControlFlow();
2583 bool isControlFlow() => isArgumentTypeCheck || isReceiverTypeCheck;
2584
2585 int typeCode() => HInstruction.TYPE_CONVERSION_TYPECODE;
2586 bool typeEquals(HInstruction other) => other is HTypeConversion;
2587 bool isCodeMotionInvariant() => false;
2588
2589 bool dataEquals(HTypeConversion other) {
2590 return kind == other.kind
2591 && typeExpression == other.typeExpression
2592 && checkedType == other.checkedType
2593 && receiverTypeCheckSelector == other.receiverTypeCheckSelector;
2594 }
2595 }
2596
2597 /// The [HTypeKnown] instruction marks a value with a refined type.
2598 class HTypeKnown extends HCheck {
2599 TypeMask knownType;
2600 bool _isMovable;
2601
2602 HTypeKnown.pinned(TypeMask knownType, HInstruction input)
2603 : this.knownType = knownType,
2604 this._isMovable = false,
2605 super(<HInstruction>[input], knownType);
2606
2607 HTypeKnown.witnessed(TypeMask knownType, HInstruction input,
2608 HInstruction witness)
2609 : this.knownType = knownType,
2610 this._isMovable = true,
2611 super(<HInstruction>[input, witness], knownType);
2612
2613 toString() => 'TypeKnown $knownType';
2614 accept(HVisitor visitor) => visitor.visitTypeKnown(this);
2615
2616 bool isJsStatement() => false;
2617 bool isControlFlow() => false;
2618 bool canThrow() => false;
2619
2620 HInstruction get witness => inputs.length == 2 ? inputs[1] : null;
2621
2622 int typeCode() => HInstruction.TYPE_KNOWN_TYPECODE;
2623 bool typeEquals(HInstruction other) => other is HTypeKnown;
2624 bool isCodeMotionInvariant() => true;
2625 bool get isMovable => _isMovable && useGvn();
2626
2627 bool dataEquals(HTypeKnown other) {
2628 return knownType == other.knownType
2629 && instructionType == other.instructionType;
2630 }
2631 }
2632
2633 class HRangeConversion extends HCheck {
2634 HRangeConversion(HInstruction input, type)
2635 : super(<HInstruction>[input], type) {
2636 sourceElement = input.sourceElement;
2637 }
2638
2639 bool get isMovable => false;
2640
2641 accept(HVisitor visitor) => visitor.visitRangeConversion(this);
2642 }
2643
2644 class HStringConcat extends HInstruction {
2645 final ast.Node node;
2646 HStringConcat(HInstruction left, HInstruction right, this.node, TypeMask type)
2647 : super(<HInstruction>[left, right], type) {
2648 // TODO(sra): Until Issue 9293 is fixed, this false dependency keeps the
2649 // concats bunched with stringified inputs for much better looking code with
2650 // fewer temps.
2651 sideEffects.setDependsOnSomething();
2652 }
2653
2654 HInstruction get left => inputs[0];
2655 HInstruction get right => inputs[1];
2656
2657 accept(HVisitor visitor) => visitor.visitStringConcat(this);
2658 toString() => "string concat";
2659 }
2660
2661 /**
2662 * The part of string interpolation which converts and interpolated expression
2663 * into a String value.
2664 */
2665 class HStringify extends HInstruction {
2666 final ast.Node node;
2667 HStringify(HInstruction input, this.node, TypeMask type)
2668 : super(<HInstruction>[input], type) {
2669 sideEffects.setAllSideEffects();
2670 sideEffects.setDependsOnSomething();
2671 }
2672
2673 accept(HVisitor visitor) => visitor.visitStringify(this);
2674 toString() => "stringify";
2675 }
2676
2677 /** Non-block-based (aka. traditional) loop information. */
2678 class HLoopInformation {
2679 final HBasicBlock header;
2680 final List<HBasicBlock> blocks;
2681 final List<HBasicBlock> backEdges;
2682 final List<LabelDefinition> labels;
2683 final JumpTarget target;
2684
2685 /** Corresponding block information for the loop. */
2686 HLoopBlockInformation loopBlockInformation;
2687
2688 HLoopInformation(this.header, this.target, this.labels)
2689 : blocks = new List<HBasicBlock>(),
2690 backEdges = new List<HBasicBlock>();
2691
2692 void addBackEdge(HBasicBlock predecessor) {
2693 backEdges.add(predecessor);
2694 List<HBasicBlock> workQueue = <HBasicBlock>[predecessor];
2695 do {
2696 HBasicBlock current = workQueue.removeLast();
2697 addBlock(current, workQueue);
2698 } while (!workQueue.isEmpty);
2699 }
2700
2701 // Adds a block and transitively all its predecessors in the loop as
2702 // loop blocks.
2703 void addBlock(HBasicBlock block, List<HBasicBlock> workQueue) {
2704 if (identical(block, header)) return;
2705 HBasicBlock parentHeader = block.parentLoopHeader;
2706 if (identical(parentHeader, header)) {
2707 // Nothing to do in this case.
2708 } else if (parentHeader != null) {
2709 workQueue.add(parentHeader);
2710 } else {
2711 block.parentLoopHeader = header;
2712 blocks.add(block);
2713 workQueue.addAll(block.predecessors);
2714 }
2715 }
2716 }
2717
2718
2719 /**
2720 * Embedding of a [HBlockInformation] for block-structure based traversal
2721 * in a dominator based flow traversal by attaching it to a basic block.
2722 * To go back to dominator-based traversal, a [HSubGraphBlockInformation]
2723 * structure can be added in the block structure.
2724 */
2725 class HBlockFlow {
2726 final HBlockInformation body;
2727 final HBasicBlock continuation;
2728 HBlockFlow(this.body, this.continuation);
2729 }
2730
2731
2732 /**
2733 * Information about a syntactic-like structure.
2734 */
2735 abstract class HBlockInformation {
2736 HBasicBlock get start;
2737 HBasicBlock get end;
2738 bool accept(HBlockInformationVisitor visitor);
2739 }
2740
2741
2742 /**
2743 * Information about a statement-like structure.
2744 */
2745 abstract class HStatementInformation extends HBlockInformation {
2746 bool accept(HStatementInformationVisitor visitor);
2747 }
2748
2749
2750 /**
2751 * Information about an expression-like structure.
2752 */
2753 abstract class HExpressionInformation extends HBlockInformation {
2754 bool accept(HExpressionInformationVisitor visitor);
2755 HInstruction get conditionExpression;
2756 }
2757
2758
2759 abstract class HStatementInformationVisitor {
2760 bool visitLabeledBlockInfo(HLabeledBlockInformation info);
2761 bool visitLoopInfo(HLoopBlockInformation info);
2762 bool visitIfInfo(HIfBlockInformation info);
2763 bool visitTryInfo(HTryBlockInformation info);
2764 bool visitSwitchInfo(HSwitchBlockInformation info);
2765 bool visitSequenceInfo(HStatementSequenceInformation info);
2766 // Pseudo-structure embedding a dominator-based traversal into
2767 // the block-structure traversal. This will eventually go away.
2768 bool visitSubGraphInfo(HSubGraphBlockInformation info);
2769 }
2770
2771
2772 abstract class HExpressionInformationVisitor {
2773 bool visitAndOrInfo(HAndOrBlockInformation info);
2774 bool visitSubExpressionInfo(HSubExpressionBlockInformation info);
2775 }
2776
2777
2778 abstract class HBlockInformationVisitor
2779 implements HStatementInformationVisitor, HExpressionInformationVisitor {
2780 }
2781
2782
2783 /**
2784 * Generic class wrapping a [SubGraph] as a block-information until
2785 * all structures are handled properly.
2786 */
2787 class HSubGraphBlockInformation implements HStatementInformation {
2788 final SubGraph subGraph;
2789 HSubGraphBlockInformation(this.subGraph);
2790
2791 HBasicBlock get start => subGraph.start;
2792 HBasicBlock get end => subGraph.end;
2793
2794 bool accept(HStatementInformationVisitor visitor) =>
2795 visitor.visitSubGraphInfo(this);
2796 }
2797
2798 /**
2799 * Generic class wrapping a [SubExpression] as a block-information until
2800 * expressions structures are handled properly.
2801 */
2802 class HSubExpressionBlockInformation implements HExpressionInformation {
2803 final SubExpression subExpression;
2804 HSubExpressionBlockInformation(this.subExpression);
2805
2806 HBasicBlock get start => subExpression.start;
2807 HBasicBlock get end => subExpression.end;
2808
2809 HInstruction get conditionExpression => subExpression.conditionExpression;
2810
2811 bool accept(HExpressionInformationVisitor visitor) =>
2812 visitor.visitSubExpressionInfo(this);
2813 }
2814
2815 /** A sequence of separate statements. */
2816 class HStatementSequenceInformation implements HStatementInformation {
2817 final List<HStatementInformation> statements;
2818 HStatementSequenceInformation(this.statements);
2819
2820 HBasicBlock get start => statements[0].start;
2821 HBasicBlock get end => statements.last.end;
2822
2823 bool accept(HStatementInformationVisitor visitor) =>
2824 visitor.visitSequenceInfo(this);
2825 }
2826
2827 class HLabeledBlockInformation implements HStatementInformation {
2828 final HStatementInformation body;
2829 final List<LabelDefinition> labels;
2830 final JumpTarget target;
2831 final bool isContinue;
2832
2833 HLabeledBlockInformation(this.body,
2834 List<LabelDefinition> labels,
2835 {this.isContinue: false}) :
2836 this.labels = labels, this.target = labels[0].target;
2837
2838 HLabeledBlockInformation.implicit(this.body,
2839 this.target,
2840 {this.isContinue: false})
2841 : this.labels = const<LabelDefinition>[];
2842
2843 HBasicBlock get start => body.start;
2844 HBasicBlock get end => body.end;
2845
2846 bool accept(HStatementInformationVisitor visitor) =>
2847 visitor.visitLabeledBlockInfo(this);
2848 }
2849
2850 class LoopTypeVisitor extends ast.Visitor {
2851 const LoopTypeVisitor();
2852 int visitNode(ast.Node node) => HLoopBlockInformation.NOT_A_LOOP;
2853 int visitWhile(ast.While node) => HLoopBlockInformation.WHILE_LOOP;
2854 int visitFor(ast.For node) => HLoopBlockInformation.FOR_LOOP;
2855 int visitDoWhile(ast.DoWhile node) => HLoopBlockInformation.DO_WHILE_LOOP;
2856 int visitForIn(ast.ForIn node) => HLoopBlockInformation.FOR_IN_LOOP;
2857 int visitSwitchStatement(ast.SwitchStatement node) =>
2858 HLoopBlockInformation.SWITCH_CONTINUE_LOOP;
2859 }
2860
2861 class HLoopBlockInformation implements HStatementInformation {
2862 static const int WHILE_LOOP = 0;
2863 static const int FOR_LOOP = 1;
2864 static const int DO_WHILE_LOOP = 2;
2865 static const int FOR_IN_LOOP = 3;
2866 static const int SWITCH_CONTINUE_LOOP = 4;
2867 static const int NOT_A_LOOP = -1;
2868
2869 final int kind;
2870 final HExpressionInformation initializer;
2871 final HExpressionInformation condition;
2872 final HStatementInformation body;
2873 final HExpressionInformation updates;
2874 final JumpTarget target;
2875 final List<LabelDefinition> labels;
2876 final SourceFileLocation sourcePosition;
2877 final SourceFileLocation endSourcePosition;
2878
2879 HLoopBlockInformation(this.kind,
2880 this.initializer,
2881 this.condition,
2882 this.body,
2883 this.updates,
2884 this.target,
2885 this.labels,
2886 this.sourcePosition,
2887 this.endSourcePosition) {
2888 assert(
2889 (kind == DO_WHILE_LOOP ? body.start : condition.start).isLoopHeader());
2890 }
2891
2892 HBasicBlock get start {
2893 if (initializer != null) return initializer.start;
2894 if (kind == DO_WHILE_LOOP) {
2895 return body.start;
2896 }
2897 return condition.start;
2898 }
2899
2900 HBasicBlock get loopHeader {
2901 return kind == DO_WHILE_LOOP ? body.start : condition.start;
2902 }
2903
2904 HBasicBlock get end {
2905 if (updates != null) return updates.end;
2906 if (kind == DO_WHILE_LOOP && condition != null) {
2907 return condition.end;
2908 }
2909 return body.end;
2910 }
2911
2912 static int loopType(ast.Node node) {
2913 return node.accept(const LoopTypeVisitor());
2914 }
2915
2916 bool accept(HStatementInformationVisitor visitor) =>
2917 visitor.visitLoopInfo(this);
2918 }
2919
2920 class HIfBlockInformation implements HStatementInformation {
2921 final HExpressionInformation condition;
2922 final HStatementInformation thenGraph;
2923 final HStatementInformation elseGraph;
2924 HIfBlockInformation(this.condition,
2925 this.thenGraph,
2926 this.elseGraph);
2927
2928 HBasicBlock get start => condition.start;
2929 HBasicBlock get end => elseGraph == null ? thenGraph.end : elseGraph.end;
2930
2931 bool accept(HStatementInformationVisitor visitor) =>
2932 visitor.visitIfInfo(this);
2933 }
2934
2935 class HAndOrBlockInformation implements HExpressionInformation {
2936 final bool isAnd;
2937 final HExpressionInformation left;
2938 final HExpressionInformation right;
2939 HAndOrBlockInformation(this.isAnd,
2940 this.left,
2941 this.right);
2942
2943 HBasicBlock get start => left.start;
2944 HBasicBlock get end => right.end;
2945
2946 // We don't currently use HAndOrBlockInformation.
2947 HInstruction get conditionExpression {
2948 return null;
2949 }
2950 bool accept(HExpressionInformationVisitor visitor) =>
2951 visitor.visitAndOrInfo(this);
2952 }
2953
2954 class HTryBlockInformation implements HStatementInformation {
2955 final HStatementInformation body;
2956 final HLocalValue catchVariable;
2957 final HStatementInformation catchBlock;
2958 final HStatementInformation finallyBlock;
2959 HTryBlockInformation(this.body,
2960 this.catchVariable,
2961 this.catchBlock,
2962 this.finallyBlock);
2963
2964 HBasicBlock get start => body.start;
2965 HBasicBlock get end =>
2966 finallyBlock == null ? catchBlock.end : finallyBlock.end;
2967
2968 bool accept(HStatementInformationVisitor visitor) =>
2969 visitor.visitTryInfo(this);
2970 }
2971
2972 class HSwitchBlockInformation implements HStatementInformation {
2973 final HExpressionInformation expression;
2974 final List<HStatementInformation> statements;
2975 final JumpTarget target;
2976 final List<LabelDefinition> labels;
2977
2978 HSwitchBlockInformation(this.expression,
2979 this.statements,
2980 this.target,
2981 this.labels);
2982
2983 HBasicBlock get start => expression.start;
2984 HBasicBlock get end {
2985 // We don't create a switch block if there are no cases.
2986 assert(!statements.isEmpty);
2987 return statements.last.end;
2988 }
2989
2990 bool accept(HStatementInformationVisitor visitor) =>
2991 visitor.visitSwitchInfo(this);
2992 }
2993
2994 class HReadTypeVariable extends HInstruction {
2995 /// The type variable being read.
2996 final TypeVariableType dartType;
2997
2998 final bool hasReceiver;
2999
3000 HReadTypeVariable(this.dartType,
3001 HInstruction receiver,
3002 TypeMask instructionType)
3003 : hasReceiver = true,
3004 super(<HInstruction>[receiver], instructionType) {
3005 setUseGvn();
3006 }
3007
3008 HReadTypeVariable.noReceiver(this.dartType,
3009 HInstruction typeArgument,
3010 TypeMask instructionType)
3011 : hasReceiver = false,
3012 super(<HInstruction>[typeArgument], instructionType) {
3013 setUseGvn();
3014 }
3015
3016 accept(HVisitor visitor) => visitor.visitReadTypeVariable(this);
3017
3018 bool canThrow() => false;
3019
3020 int typeCode() => HInstruction.READ_TYPE_VARIABLE_TYPECODE;
3021 bool typeEquals(HInstruction other) => other is HReadTypeVariable;
3022
3023 bool dataEquals(HReadTypeVariable other) {
3024 return dartType.element == other.dartType.element
3025 && hasReceiver == other.hasReceiver;
3026 }
3027 }
3028
3029 abstract class HRuntimeType extends HInstruction {
3030 final DartType dartType;
3031
3032 HRuntimeType(List<HInstruction> inputs,
3033 this.dartType,
3034 TypeMask instructionType)
3035 : super(inputs, instructionType) {
3036 setUseGvn();
3037 }
3038
3039 bool canThrow() => false;
3040
3041 int typeCode() {
3042 throw 'abstract method';
3043 }
3044
3045 bool typeEquals(HInstruction other) {
3046 throw 'abstract method';
3047 }
3048
3049 bool dataEquals(HRuntimeType other) {
3050 return dartType == other.dartType;
3051 }
3052 }
3053
3054 class HFunctionType extends HRuntimeType {
3055 HFunctionType(List<HInstruction> inputs,
3056 FunctionType dartType,
3057 TypeMask instructionType)
3058 : super(inputs, dartType, instructionType);
3059
3060 accept(HVisitor visitor) => visitor.visitFunctionType(this);
3061
3062 int typeCode() => HInstruction.FUNCTION_TYPE_TYPECODE;
3063
3064 bool typeEquals(HInstruction other) => other is HFunctionType;
3065 }
3066
3067 class HVoidType extends HRuntimeType {
3068 HVoidType(VoidType dartType, TypeMask instructionType)
3069 : super(const <HInstruction>[], dartType, instructionType);
3070
3071 accept(HVisitor visitor) => visitor.visitVoidType(this);
3072
3073 int typeCode() => HInstruction.VOID_TYPE_TYPECODE;
3074
3075 bool typeEquals(HInstruction other) => other is HVoidType;
3076 }
3077
3078 class HInterfaceType extends HRuntimeType {
3079 HInterfaceType(List<HInstruction> inputs,
3080 InterfaceType dartType,
3081 TypeMask instructionType)
3082 : super(inputs, dartType, instructionType);
3083
3084 accept(HVisitor visitor) => visitor.visitInterfaceType(this);
3085
3086 int typeCode() => HInstruction.INTERFACE_TYPE_TYPECODE;
3087
3088 bool typeEquals(HInstruction other) => other is HInterfaceType;
3089 }
3090
3091 class HDynamicType extends HRuntimeType {
3092 HDynamicType(DynamicType dartType, TypeMask instructionType)
3093 : super(const <HInstruction>[], dartType, instructionType);
3094
3095 accept(HVisitor visitor) => visitor.visitDynamicType(this);
3096
3097 int typeCode() => HInstruction.DYNAMIC_TYPE_TYPECODE;
3098
3099 bool typeEquals(HInstruction other) => other is HDynamicType;
3100 }
OLDNEW
« no previous file with comments | « pkg/compiler/lib/src/ssa/invoke_dynamic_specializers.dart ('k') | pkg/compiler/lib/src/ssa/optimize.dart » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698