dart2js cps: Maintain parent pointers instead of recomputing them.

pkg/compiler/lib/src/cps_ir/cps_ir_integrity.dart

 library dart2js.cps_ir_integrity;
 
 import 'cps_ir_nodes.dart';
 import 'cps_ir_nodes_sexpr.dart';
 import '../tracer.dart' as tracer;
 
 /// Dump S-expressions on error if the tracer is enabled.
 ///
 /// Technically this has nothing to do with the tracer, but if you want one
 /// enabled, you typically want the other as well, so we use the same flag.
 const bool ENABLE_DUMP = tracer.TRACE_FILTER_PATTERN != null;
 
 /// Performs integrity checks on the CPS IR.
 ///
 /// To be run for debugging purposes, not for use in production.
 ///
 /// The following integrity checks are performed:
 ///
 /// - References are in scope of their definitions.
 /// - Recursive Continuations and InvokeContinuations are marked as recursive.
 /// - InvokeContinuations have the same arity as their target.
 /// - Reference chains are valid doubly-linked lists.
 /// - Reference chains contain exactly the references that are in the IR.
 /// - Each definition object occurs only once in the IR (no redeclaring).
 /// - Each reference object occurs only once in the IR (no sharing).
 ///
-class CheckCpsIntegrity extends RecursiveVisitor {
+class CheckCpsIntegrity extends TrampolineRecursiveVisitor {
 
   FunctionDefinition topLevelNode;
+  String previousPass;
 
   Set<Definition> seenDefinitions = new Set<Definition>();
   Map<Definition, Set<Reference>> seenReferences =
       <Definition, Set<Reference>>{};
 
   Set<Definition> inScope = new Set<Definition>();
   Set<Continuation> insideContinuations = new Set<Continuation>();
 
   void markAsSeen(Definition def) {
     if (!seenDefinitions.add(def)) {
       error('Redeclared $def', def);
     }
     seenReferences[def] = new Set<Reference>();
   }
 
   void enterScope(Iterable<Definition> definitions) {
     inScope.addAll(definitions);
     pushAction(() => inScope.removeAll(definitions));
   }
 
   void enterContinuation(Continuation cont) {
     insideContinuations.add(cont);
     pushAction(() => insideContinuations.remove(cont));
   }
 
-  void check(FunctionDefinition node) {
+  void check(FunctionDefinition node, String previousPass) {
     topLevelNode = node;
+    this.previousPass = previousPass;
+    ParentChecker.checkParents(node, this);
     visit(node);
     // Check for broken reference chains. We check this last, so out-of-scope
     // references are not classified as a broken reference chain.
     seenDefinitions.forEach(checkReferenceChain);
   }
 
   @override
   Expression traverseLetCont(LetCont node) {
     node.continuations.forEach(markAsSeen);
     node.continuations.forEach(push);
@@ skipping 107 matching lines @@
       error('Reference chain for $def contains orphaned references', def);
     }
   }
 
   error(String message, node) {
     String sexpr;
     if (ENABLE_DUMP) {
       try {
         Decorator decorator = (n, String s) => n == node ? '**$s**' : s;
         sexpr = new SExpressionStringifier(decorator).visit(topLevelNode);
+        sexpr = 'SExpr dump (offending node marked with **):\n\n$sexpr';
       } catch (e) {
         sexpr = '(Exception thrown by SExpressionStringifier: $e)';
       }
     } else {
-      sexpr = '(Set DUMP_IR flag to enable)';
+      sexpr = '(Set DUMP_IR flag to enable SExpr dump)';
     }
-    throw 'CPS integrity violation in ${topLevelNode.element}:\n'
+    throw 'CPS integrity violation\n'
+          'After $previousPass on ${topLevelNode.element}\n'
           '$message\n\n'
-          'SExpr dump (offending node marked with **):\n\n'
           '$sexpr\n';
   }
+}
 
+/// Traverses the CPS term and checks that node.parent is correctly set
+/// for each visited node.
+class ParentChecker extends DeepRecursiveVisitor {
+  static void checkParents(Node node, CheckCpsIntegrity main) {
+    ParentChecker visitor = new ParentChecker._make(main);
+    visitor._worklist.add(node);
+    visitor.trampoline();
+  }
+
+  ParentChecker._make(this.main);
+
+  Node _parent;
+  final List<Node> _worklist = <Node>[];
+  final CheckCpsIntegrity main;
+
+  void trampoline() {
+    while (_worklist.isNotEmpty) {
+      _parent = _worklist.removeLast();
+      _parent.accept(this);
+    }
+  }
+
+  error(String message, node) => main.error(message, node);
+
+  @override
+  visit(Node node) {
+    _worklist.add(node);
+    if (node.parent != _parent) {
+      error('Parent pointer on $node is ${node.parent} but should be $_parent',
+            node);
+    }
+  }
+
+  @override
+  processReference(Reference node) {
+    if (node.parent != _parent) {
+      error('Parent pointer on $node is ${node.parent} but should be $_parent',
+            node);
+    }
+  }
 }