dart2js cps: Speed up CPS IR integrity checker.

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;
 
+enum ScopeType { InScope, InDefinition, NotInScope }
+
 /// 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 TrampolineRecursiveVisitor {
 
   FunctionDefinition topLevelNode;
+  final Map<Definition, ScopeType> inScope = <Definition, ScopeType>{};
+  final List<Definition> definitions = [];
   String previousPass;
 
-  Set<Definition> seenDefinitions = new Set<Definition>();
-  Map<Definition, Set<Reference>> seenReferences =
-      <Definition, Set<Reference>>{};
+  void setScope(Iterable<Definition> defs, ScopeType scope) {
+    for (Definition def in defs) {
+      inScope[def] = scope;
+    }
+  }
 
-  Set<Definition> inScope = new Set<Definition>();
-  Set<Continuation> insideContinuations = new Set<Continuation>();
-
-  void markAsSeen(Definition def) {
-    if (!seenDefinitions.add(def)) {
-      error('Redeclared $def', def);
+  void handleDeclaration(Definition def) {
+    definitions.add(def);
+    // Check the reference chain for cycles broken links.
+    Reference anchor = null;
+    int i = 0;
+    for (Reference ref = def.firstRef; ref != null; ref = ref.next) {
+      if (ref.definition != def) {
+        error('Reference to ${ref.definition} found in '
+              'reference chain for $def', def);
+      }
+      if (ref == anchor) {
+        error('Cyclic reference chain for $def', def);
+      }
+      if (i & ++i == 0) { // Move the anchor every 2^Nth step.
+        anchor = ref;
+      }
     }
-    seenReferences[def] = new Set<Reference>();
   }
 
   void enterScope(Iterable<Definition> definitions) {
-    inScope.addAll(definitions);
-    pushAction(() => inScope.removeAll(definitions));
+    for (Definition def in definitions) {
+      inScope[def] = ScopeType.InScope;
+    }
+    pushAction(() {
+      for (Definition def in definitions) {
+        inScope[def] = ScopeType.NotInScope;
+      }
+    });
   }
 
   void enterContinuation(Continuation cont) {
-    insideContinuations.add(cont);
-    pushAction(() => insideContinuations.remove(cont));
+    inScope[cont] = ScopeType.InDefinition;
+    pushAction(() {
+      inScope[cont] = ScopeType.NotInScope;
+    });
   }
 
   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);
+    definitions.forEach(checkReferenceChain);
   }
 
   @override
   Expression traverseLetCont(LetCont node) {
-    node.continuations.forEach(markAsSeen);
+    node.continuations.forEach(handleDeclaration);
     node.continuations.forEach(push);
 
     // Put all continuations in scope when visiting the body.
     enterScope(node.continuations);
 
     return node.body;
   }
 
   @override
   Expression traverseLetPrim(LetPrim node) {
-    markAsSeen(node.primitive);
+    handleDeclaration(node.primitive);
 
     // Process references in the primitive.
     visit(node.primitive);
 
     // Put the primitive in scope when visiting the body.
     enterScope([node.primitive]);
 
     return node.body;
   }
 
   @override
   Expression traverseLetMutable(LetMutable node) {
-    markAsSeen(node.variable);
+    handleDeclaration(node.variable);
     processReference(node.value);
-    
+
     // Put the primitive in scope when visiting the body.
     enterScope([node.variable]);
 
     return node.body;
   }
 
   @override
   Expression traverseContinuation(Continuation cont) {
     if (cont.isReturnContinuation) {
       error('Non-return continuation missing body', cont);
     }
-    cont.parameters.forEach(markAsSeen);
+    cont.parameters.forEach(handleDeclaration);
     enterScope(cont.parameters);
     // Put every continuation in scope at its own body. The isRecursive
     // flag is checked explicitly using [insideContinuations].
     enterScope([cont]);
     enterContinuation(cont);
     return cont.body;
   }
 
   @override
   visitFunctionDefinition(FunctionDefinition node) {
     if (node.thisParameter != null) {
-      markAsSeen(node.thisParameter);
+      handleDeclaration(node.thisParameter);
       enterScope([node.thisParameter]);
     }
-    node.parameters.forEach(markAsSeen);
+    node.parameters.forEach(handleDeclaration);
     enterScope(node.parameters);
-    markAsSeen(node.returnContinuation);
+    handleDeclaration(node.returnContinuation);
     enterScope([node.returnContinuation]);
     if (!node.returnContinuation.isReturnContinuation) {
       error('Return continuation with a body', node);
     }
     visit(node.body);
   }
 
   @override
-  processReference(Reference reference) {
-    if (!inScope.contains(reference.definition)) {
-      error('Referenced out of scope: ${reference.definition}', reference);
+  processReference(Reference ref) {
+    Definition def = ref.definition;
+    if (inScope[def] == ScopeType.NotInScope) {
+      error('Referenced out of scope: $def', ref);
     }
-    if (!seenReferences[reference.definition].add(reference)) {
-      error('Duplicate use of Reference to ${reference.definition}', reference);
+    if (ref.previous == null && def.firstRef != ref ||
+        ref.previous != null && ref.previous.next != ref) {
+      error('Broken .previous link in reference to $def', def);
     }
+    ref.previous = ref; // Mark reference as "seen". We will repair it later.
   }
 
   @override
   processInvokeContinuation(InvokeContinuation node) {
     Continuation target = node.continuation.definition;
-    if (node.isRecursive && !insideContinuations.contains(target)) {
+    if (node.isRecursive && inScope[target] == ScopeType.InScope) {
       error('Non-recursive InvokeContinuation marked as recursive', node);
     }
-    if (!node.isRecursive && insideContinuations.contains(target)) {
+    if (!node.isRecursive && inScope[target] == ScopeType.InDefinition) {
       error('Recursive InvokeContinuation marked as non-recursive', node);
     }
     if (node.isRecursive && !target.isRecursive) {
       error('Recursive Continuation was not marked as recursive', node);
     }
     if (node.arguments.length != target.parameters.length) {
       error('Arity mismatch in InvokeContinuation', node);
     }
   }
 
   void checkReferenceChain(Definition def) {
-    Set<Reference> chainedReferences = new Set<Reference>();
-    Reference prev = null;
+    Reference previous = null;
     for (Reference ref = def.firstRef; ref != null; ref = ref.next) {
-      if (ref.definition != def) {
-        error('Reference in chain for $def points to ${ref.definition}', def);
+      if (ref.previous != ref) {
+        // Reference was not seen during IR traversal, so it is orphaned.
+        error('Orphaned reference in reference chain for $def', def);
       }
-      if (ref.previous != prev) {
-        error('Broken .previous link in reference to $def', def);
-      }
-      prev = ref;
-      if (!chainedReferences.add(ref)) {
-        error('Cyclic reference chain for $def', def);
-      }
-    }
-    if (!chainedReferences.containsAll(seenReferences[def])) {
-      error('Seen reference to $def not in reference chain', def);
-    }
-    if (!seenReferences[def].containsAll(chainedReferences)) {
-      error('Reference chain for $def contains orphaned references', def);
+      // Repair the .previous link that was used for marking.
+      ref.previous = previous;
+      previous = ref;
     }
   }
 
   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';
@@ skipping 44 matching lines @@
   }
 
   @override
   processReference(Reference node) {
     if (node.parent != _parent) {
       error('Parent pointer on $node is ${node.parent} but should be $_parent',
             node);
     }
   }
 }