diff --git a/dev/core/src/com/google/gwt/dev/javac/CompilationState.java b/dev/core/src/com/google/gwt/dev/javac/CompilationState.java
index bdf9c2c..846c78c 100644
--- a/dev/core/src/com/google/gwt/dev/javac/CompilationState.java
+++ b/dev/core/src/com/google/gwt/dev/javac/CompilationState.java
@@ -22,6 +22,9 @@
 import com.google.gwt.dev.javac.impl.SourceFileCompilationUnit;
 import com.google.gwt.dev.js.ast.JsProgram;
 
+import org.eclipse.jdt.core.compiler.CharOperation;
+import org.eclipse.jdt.internal.compiler.ClassFile;
+
 import java.util.Collections;
 import java.util.HashMap;
 import java.util.HashSet;
@@ -67,10 +70,29 @@
    */
   public void compile(TreeLogger logger) throws UnableToCompleteException {
     JdtCompiler.compile(getCompilationUnits());
+    Set<String> validBinaryTypeNames = new HashSet<String>();
+    for (CompilationUnit unit : getCompilationUnits()) {
+      switch (unit.getState()) {
+        case COMPILED:
+          for (ClassFile classFile : unit.getJdtCud().compilationResult().getClassFiles()) {
+            char[] binaryName = CharOperation.concatWith(
+                classFile.getCompoundName(), '/');
+            validBinaryTypeNames.add(String.valueOf(binaryName));
+          }
+          break;
+        case CHECKED:
+          for (CompiledClass compiledClass : unit.getCompiledClasses()) {
+            validBinaryTypeNames.add(compiledClass.getBinaryName());
+          }
+          break;
+      }
+    }
     CompilationUnitInvalidator.validateCompilationUnits(getCompilationUnits(),
-        getClassFileMap());
+        validBinaryTypeNames);
 
-    // TODO: Move into validation & log errors?
+    CompilationUnitInvalidator.invalidateUnitsWithErrors(logger,
+        getCompilationUnits());
+
     JsniCollector.collectJsniMethods(logger, getCompilationUnits(),
         new JsProgram());
 
diff --git a/dev/core/src/com/google/gwt/dev/javac/CompilationUnitInvalidator.java b/dev/core/src/com/google/gwt/dev/javac/CompilationUnitInvalidator.java
index 8951234..9c01b74 100644
--- a/dev/core/src/com/google/gwt/dev/javac/CompilationUnitInvalidator.java
+++ b/dev/core/src/com/google/gwt/dev/javac/CompilationUnitInvalidator.java
@@ -24,11 +24,9 @@
 import org.eclipse.jdt.internal.compiler.CompilationResult;
 import org.eclipse.jdt.internal.compiler.ast.CompilationUnitDeclaration;
 
-import java.util.HashMap;
 import java.util.HashSet;
-import java.util.Map;
+import java.util.Iterator;
 import java.util.Set;
-import java.util.Map.Entry;
 
 /**
  * Helper class to invalidate units in a set based on errors or references to
@@ -45,11 +43,10 @@
     // Start by removing units with a known problem.
     boolean anyRemoved = false;
     for (CompilationUnit unit : units) {
-      CompilationUnitDeclaration cud = unit.getJdtCud();
-      if (cud == null) {
+      if (unit.getState() != State.COMPILED) {
         continue;
       }
-      CompilationResult result = cud.compilationResult();
+      CompilationResult result = unit.getJdtCud().compilationResult();
       if (result.hasErrors()) {
         anyRemoved = true;
 
@@ -92,63 +89,50 @@
 
   public static void invalidateUnitsWithInvalidRefs(TreeLogger logger,
       Set<CompilationUnit> units) {
-    logger = logger.branch(TreeLogger.TRACE, "Removing invalidate units");
+    logger = logger.branch(TreeLogger.TRACE, "Removing invalidated units");
 
-    // Map all units by file name.
-    Map<String, CompilationUnit> unitsByFileName = new HashMap<String, CompilationUnit>();
+    // Assume all compiled units are valid at first.
+    boolean changed;
+    Set<CompilationUnit> validUnits = new HashSet<CompilationUnit>();
     for (CompilationUnit unit : units) {
-      unitsByFileName.put(unit.getDisplayLocation(), unit);
+      if (unit.isCompiled()) {
+        validUnits.add(unit);
+      }
     }
-    // First, compute a map from all targets all referents.
-    Map<CompilationUnit, Set<CompilationUnit>> refTargetToReferents = new HashMap<CompilationUnit, Set<CompilationUnit>>();
-    for (CompilationUnit referentUnit : units) {
-      if (referentUnit.isCompiled()) {
-        Set<String> fileNameRefs = referentUnit.getFileNameRefs();
-        for (String fileNameRef : fileNameRefs) {
-          CompilationUnit targetUnit = unitsByFileName.get(fileNameRef);
-          if (targetUnit != null) {
-            Set<CompilationUnit> referents = refTargetToReferents.get(targetUnit);
-            if (referents == null) {
-              referents = new HashSet<CompilationUnit>();
-              refTargetToReferents.put(targetUnit, referents);
+    do {
+      changed = false;
+      Set<String> validRefs = new HashSet<String>();
+      for (CompilationUnit unit : validUnits) {
+        validRefs.add(unit.getDisplayLocation());
+      }
+      for (Iterator<CompilationUnit> it = validUnits.iterator(); it.hasNext();) {
+        CompilationUnit unit = it.next();
+        TreeLogger branch = null;
+        for (String ref : unit.getFileNameRefs()) {
+          if (!validRefs.contains(ref)) {
+            if (branch == null) {
+              branch = logger.branch(TreeLogger.WARN, "Compilation unit '"
+                  + unit + "' is removed due to invalid reference(s):");
+              it.remove();
+              changed = true;
+              unit.setState(State.FRESH);
             }
-            // Add myself as a referent.
-            referents.add(referentUnit);
+            branch.log(TreeLogger.WARN, ref);
           }
         }
       }
-    }
-
-    // Now use the map to transitively blow away invalid units.
-    for (Entry<CompilationUnit, Set<CompilationUnit>> entry : refTargetToReferents.entrySet()) {
-      CompilationUnit maybeInvalidUnit = entry.getKey();
-      if (!maybeInvalidUnit.isCompiled()) {
-        // Invalidate all dependent units.
-        Set<CompilationUnit> invalidReferentUnits = entry.getValue();
-        TreeLogger branch = logger.branch(TreeLogger.TRACE,
-            "Compilation unit '" + maybeInvalidUnit + "' is invalid");
-        State why = maybeInvalidUnit.getState();
-        for (CompilationUnit invalidReferentUnit : invalidReferentUnits) {
-          if (invalidReferentUnit.isCompiled()) {
-            // Set it to the same state as the unit it depends on.
-            invalidReferentUnit.setState(why);
-            branch.log(TreeLogger.TRACE, "Removing dependent unit '"
-                + invalidReferentUnit + "'");
-          }
-        }
-      }
-    }
+    } while (changed);
   }
 
   public static void validateCompilationUnits(Set<CompilationUnit> units,
-      Map<String, CompiledClass> compiledClasses) {
+      Set<String> validBinaryTypeNames) {
     for (CompilationUnit unit : units) {
       if (unit.getState() == State.COMPILED) {
         CompilationUnitDeclaration jdtCud = unit.getJdtCud();
         JSORestrictionsChecker.check(jdtCud);
         LongFromJSNIChecker.check(jdtCud);
         BinaryTypeReferenceRestrictionsChecker.check(jdtCud,
-            compiledClasses.keySet());
+            validBinaryTypeNames);
       }
     }
   }
diff --git a/dev/core/test/com/google/gwt/dev/javac/TypeOracleTestingUtils.java b/dev/core/test/com/google/gwt/dev/javac/TypeOracleTestingUtils.java
index dd71e22..2a08394 100644
--- a/dev/core/test/com/google/gwt/dev/javac/TypeOracleTestingUtils.java
+++ b/dev/core/test/com/google/gwt/dev/javac/TypeOracleTestingUtils.java
@@ -21,9 +21,7 @@
 import com.google.gwt.dev.javac.impl.SourceFileCompilationUnit;
 
 import java.util.Collections;
-import java.util.HashMap;
 import java.util.HashSet;
-import java.util.Map;
 import java.util.Set;
 
 /**
@@ -52,13 +50,14 @@
   public static TypeOracle buildTypeOracle(TreeLogger logger,
       Set<CompilationUnit> units) throws UnableToCompleteException {
     JdtCompiler.compile(units);
-    Map<String, CompiledClass> classMap = new HashMap<String, CompiledClass>();
+    Set<String> validBinaryTypeNames = new HashSet<String>();
     for (CompilationUnit unit : units) {
       for (CompiledClass compiledClass : unit.getCompiledClasses()) {
-        classMap.put(compiledClass.getBinaryName(), compiledClass);
+        validBinaryTypeNames.add(compiledClass.getBinaryName());
       }
     }
-    CompilationUnitInvalidator.validateCompilationUnits(units, classMap);
+    CompilationUnitInvalidator.validateCompilationUnits(units,
+        validBinaryTypeNames);
     CompilationUnitInvalidator.invalidateUnitsWithErrors(logger, units);
     TypeOracleMediator mediator = new TypeOracleMediator();
     mediator.refresh(logger, units);