diff --git a/src/main/java/com/google/devtools/build/skyframe/AbstractExceptionalParallelEvaluator.java b/src/main/java/com/google/devtools/build/skyframe/AbstractExceptionalParallelEvaluator.java
index b3d5324..b200e95 100644
--- a/src/main/java/com/google/devtools/build/skyframe/AbstractExceptionalParallelEvaluator.java
+++ b/src/main/java/com/google/devtools/build/skyframe/AbstractExceptionalParallelEvaluator.java
@@ -671,19 +671,18 @@
       Preconditions.checkState(
           newState != DependencyState.ALREADY_EVALUATING, "%s %s", key, prevEntry);
       if (prevEntry.isDirty()) {
+        // Get the node in the state where it is able to accept a value.
         Preconditions.checkState(
             newState == DependencyState.NEEDS_SCHEDULING, "%s %s", key, prevEntry);
-        // There was an existing entry for this key in the graph.
-        // Get the node in the state where it is able to accept a value.
-
-        // Check that the previous node has no dependencies. Overwriting a value with deps with an
-        // injected value (which is by definition deps-free) needs a little additional bookkeeping
-        // (removing reverse deps from the dependencies), but more importantly it's something that
-        // we want to avoid, because it indicates confusion of input values and derived values.
+        // If there was a node in the graph before, check that the previous node has no
+        // dependencies. Overwriting a value with deps with an injected value (which is by
+        // definition deps-free) needs a little additional bookkeeping (removing reverse deps from
+        // the dependencies), but more importantly it's something that we want to avoid, because it
+        // indicates confusion of input values and derived values.
         Preconditions.checkState(
             prevEntry.noDepsLastBuild(), "existing entry for %s has deps: %s", key, prevEntry);
-        prevEntry.markRebuilding();
       }
+      prevEntry.markRebuilding();
       prevEntry.setValue(
           value,
           version,
diff --git a/src/main/java/com/google/devtools/build/skyframe/AbstractParallelEvaluator.java b/src/main/java/com/google/devtools/build/skyframe/AbstractParallelEvaluator.java
index 84e5ff7..7115951 100644
--- a/src/main/java/com/google/devtools/build/skyframe/AbstractParallelEvaluator.java
+++ b/src/main/java/com/google/devtools/build/skyframe/AbstractParallelEvaluator.java
@@ -199,9 +199,6 @@
     }
 
     private DirtyOutcome maybeHandleDirtyNode(NodeEntry state) throws InterruptedException {
-      if (!state.isDirty()) {
-        return DirtyOutcome.NEEDS_EVALUATION;
-      }
       while (state.getDirtyState().equals(DirtyState.CHECK_DEPENDENCIES)) {
         // Evaluating a dirty node for the first time, and checking its children to see if any
         // of them have changed. Note that there must be dirty children for this to happen.
diff --git a/src/main/java/com/google/devtools/build/skyframe/DirtyBuildingState.java b/src/main/java/com/google/devtools/build/skyframe/DirtyBuildingState.java
index b110ab0..977f31f 100644
--- a/src/main/java/com/google/devtools/build/skyframe/DirtyBuildingState.java
+++ b/src/main/java/com/google/devtools/build/skyframe/DirtyBuildingState.java
@@ -21,6 +21,7 @@
 import com.google.devtools.build.skyframe.ThinNodeEntry.DirtyType;
 import java.util.List;
 import java.util.Set;
+import javax.annotation.Nullable;
 
 /**
  * State for a node that has been dirtied, and will be checked to see if it needs re-evaluation, and
@@ -30,6 +31,17 @@
  * package.
  */
 public abstract class DirtyBuildingState {
+  private static final int NOT_EVALUATING_SENTINEL = -1;
+
+  static DirtyBuildingState create(
+      DirtyType dirtyType, GroupedList<SkyKey> lastBuildDirectDeps, SkyValue lastBuildValue) {
+    return new FullDirtyBuildingState(dirtyType, lastBuildDirectDeps, lastBuildValue);
+  }
+
+  static DirtyBuildingState createNew() {
+    return new FullDirtyBuildingState(DirtyType.CHANGE, null, null);
+  }
+
   /**
    * The state of a dirty node. A node is marked dirty in the DirtyBuildingState constructor, and
    * goes into either the state {@link DirtyState#CHECK_DEPENDENCIES} or {@link
@@ -39,6 +51,29 @@
   private DirtyState dirtyState;
 
   /**
+   * The number of dependencies that are known to be done in a {@link NodeEntry}.
+   *
+   * <p>There is a potential check-then-act race here during evaluation, so we need to make sure
+   * that when this is increased, we always check if the new value is equal to the number of
+   * required dependencies, and if so, we must re-schedule the node for evaluation.
+   *
+   * <p>There are two potential pitfalls here: 1) If multiple dependencies signal this node in close
+   * succession, this node should be scheduled exactly once. 2) If a thread is still working on this
+   * node, it should not be scheduled.
+   *
+   * <p>To solve the first problem, the {@link NodeEntry#signalDep} method also returns if the node
+   * needs to be re-scheduled, and ensures that only one thread gets a true return value.
+   *
+   * <p>The second problem is solved by first adding the newly discovered deps to a node's {@link
+   * InMemoryNodeEntry#directDeps}, and then looping through the direct deps and registering this
+   * node as a reverse dependency. This ensures that the signaledDeps counter can only reach {@link
+   * InMemoryNodeEntry#directDeps#numElements} on the very last iteration of the loop, i.e., the
+   * thread is not working on the node anymore. Note that this requires that there is no code after
+   * the loop in {@link ParallelEvaluator.Evaluate#run}.
+   */
+  private int signaledDeps = NOT_EVALUATING_SENTINEL;
+
+  /**
    * The dependencies requested (with group markers) last time the node was built (and below, the
    * value last time the node was built). They will be compared to dependencies requested on this
    * build to check whether this node has changed in {@link NodeEntry#setValue}. If they are null,
@@ -47,6 +82,7 @@
    *
    * <p>Public only for the use of alternative graph implementations.
    */
+  @Nullable
   public abstract GroupedList<SkyKey> getLastBuildDirectDeps() throws InterruptedException;
 
   /**
@@ -64,12 +100,13 @@
    *
    * <p>Public only for the use of alternative graph implementations.
    */
+  @Nullable
   public abstract SkyValue getLastBuildValue() throws InterruptedException;
 
   /**
    * Group of children to be checked next in the process of determining if this entry needs to be
    * re-evaluated. Used by {@link DirtyBuildingState#getNextDirtyDirectDeps} and {@link
-   * #signalDepInternal}.
+   * #signalDepPostProcess}.
    */
   protected int dirtyDirectDepIndex;
 
@@ -80,10 +117,8 @@
     dirtyDirectDepIndex = 0;
   }
 
-  static DirtyBuildingState create(
-      DirtyType dirtyType, GroupedList<SkyKey> lastBuildDirectDeps, SkyValue lastBuildValue) {
-    return new FullDirtyBuildingState(dirtyType, lastBuildDirectDeps, lastBuildValue);
-  }
+  /** Returns true if this state does have information about a previously built version. */
+  protected abstract boolean isDirty();
 
   final void markChanged() {
     Preconditions.checkState(dirtyState == DirtyState.CHECK_DEPENDENCIES, this);
@@ -97,7 +132,8 @@
     }
   }
 
-  final void forceRebuild() {
+  final void forceRebuild(int numTemporaryDirectDeps) {
+    Preconditions.checkState(numTemporaryDirectDeps == signaledDeps, this);
     Preconditions.checkState(
         (dirtyState == DirtyState.CHECK_DEPENDENCIES
                 && getNumOfGroupsInLastBuildDirectDeps() == dirtyDirectDepIndex)
@@ -106,6 +142,10 @@
     dirtyState = DirtyState.FORCED_REBUILDING;
   }
 
+  final boolean isEvaluating() {
+    return signaledDeps > NOT_EVALUATING_SENTINEL;
+  }
+
   final boolean isChanged() {
     return dirtyState == DirtyState.NEEDS_REBUILDING
         || dirtyState == DirtyState.NEEDS_FORCED_REBUILDING
@@ -122,6 +162,11 @@
         this);
   }
 
+  final void signalDep() {
+    Preconditions.checkState(isEvaluating());
+    signaledDeps++;
+  }
+
   /**
    * If this node is not yet known to need rebuilding, sets {@link #dirtyState} to {@link
    * DirtyState#NEEDS_REBUILDING} if the child has changed, and {@link DirtyState#VERIFIED_CLEAN} if
@@ -129,7 +174,7 @@
    * isReady} and comparing {@link #dirtyDirectDepIndex} and {@link
    * DirtyBuildingState#getNumOfGroupsInLastBuildDirectDeps()}.
    */
-  final void signalDepInternal(boolean childChanged, boolean isReady) {
+  final void signalDepPostProcess(boolean childChanged, int numTemporaryDirectDeps) {
     Preconditions.checkState(
         isChanged() || (dirtyState == DirtyState.CHECK_DEPENDENCIES && dirtyDirectDepIndex > 0),
         "Unexpected not evaluating: %s",
@@ -140,7 +185,7 @@
       if (childChanged) {
         dirtyState = DirtyState.NEEDS_REBUILDING;
       } else if (dirtyState == DirtyState.CHECK_DEPENDENCIES
-          && isReady
+          && isReady(numTemporaryDirectDeps)
           && getNumOfGroupsInLastBuildDirectDeps() == dirtyDirectDepIndex) {
         // No other dep already marked this as NEEDS_REBUILDING, no deps outstanding, and this was
         // the last block of deps to be checked.
@@ -167,7 +212,9 @@
    */
   public final boolean unchangedFromLastBuild(SkyValue newValue) throws InterruptedException {
     checkFinishedBuildingWhenAboutToSetValue();
-    return !(newValue instanceof NotComparableSkyValue) && getLastBuildValue().equals(newValue);
+    return !(newValue instanceof NotComparableSkyValue)
+        && getLastBuildValue() != null
+        && getLastBuildValue().equals(newValue);
   }
 
   /**
@@ -206,8 +253,10 @@
    * process the returned set, and so subsequent calls to this method will return the empty set.
    */
   Set<SkyKey> getAllRemainingDirtyDirectDeps(boolean preservePosition) throws InterruptedException {
+    if (getLastBuildDirectDeps() == null) {
+      return ImmutableSet.of();
+    }
     ImmutableSet.Builder<SkyKey> result = ImmutableSet.builder();
-
     for (int ind = dirtyDirectDepIndex; ind < getNumOfGroupsInLastBuildDirectDeps(); ind++) {
       result.addAll(getLastBuildDirectDeps().get(ind));
     }
@@ -220,6 +269,7 @@
   final void resetForRestartFromScratch() {
     Preconditions.checkState(
         dirtyState == DirtyState.REBUILDING || dirtyState == DirtyState.FORCED_REBUILDING, this);
+    signaledDeps = 0;
     dirtyDirectDepIndex = 0;
   }
 
@@ -228,13 +278,29 @@
     dirtyState = DirtyState.REBUILDING;
   }
 
+  void startEvaluating() {
+    Preconditions.checkState(!isEvaluating(), this);
+    signaledDeps = 0;
+  }
+
   public int getLastDirtyDirectDepIndex() {
     return dirtyDirectDepIndex - 1;
   }
 
+  public int getSignaledDeps() {
+    return signaledDeps;
+  }
+
+  /** Returns whether all known children of this node have signaled that they are done. */
+  boolean isReady(int numDirectDeps) {
+    Preconditions.checkState(signaledDeps <= numDirectDeps, "%s %s", numDirectDeps, this);
+    return signaledDeps == numDirectDeps;
+  }
+
   protected MoreObjects.ToStringHelper getStringHelper() {
     return MoreObjects.toStringHelper(this)
         .add("dirtyState", dirtyState)
+        .add("signaledDeps", signaledDeps)
         .add("dirtyDirectDepIndex", dirtyDirectDepIndex);
   }
 
@@ -259,6 +325,11 @@
     }
 
     @Override
+    protected boolean isDirty() {
+      return lastBuildDirectDeps != null;
+    }
+
+    @Override
     public SkyValue getLastBuildValue() {
       return lastBuildValue;
     }
@@ -270,7 +341,7 @@
 
     @Override
     protected int getNumOfGroupsInLastBuildDirectDeps() {
-      return lastBuildDirectDeps.listSize();
+      return lastBuildDirectDeps == null ? 0 : lastBuildDirectDeps.listSize();
     }
 
     @Override
diff --git a/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java b/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java
index bf76f6d..058a3dc 100644
--- a/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java
+++ b/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java
@@ -44,14 +44,9 @@
  *
  * <ol>
  *   <li>Non-existent
- *   <li>Just created ({@link #isEvaluating} is false)
- *   <li>Evaluating ({@link #isEvaluating} is true)
- *   <li>Done ({@link #isDone} is true)
- *   <li>Just created (when it is dirtied: {@link #dirtyBuildingState} is not null)
- *   <li>Reset (just before it is re-evaluated: {@link #dirtyBuildingState#getDirtyState} returns
- *       {@link DirtyState#NEEDS_REBUILDING})
- *   <li>Evaluating
- *   <li>Done
+ *   <li>Just created or marked as affected ({@link #isDone} is false; {@link #isDirty} is false)
+ *   <li>Evaluating ({@link #isDone} is false; {@link #isDirty} is true)
+ *   <li>Done ({@link #isDone} is true; {@link #isDirty} is false)
  * </ol>
  *
  * <p>The "just created" state is there to allow the {@link EvaluableGraph#createIfAbsentBatch} and
@@ -65,6 +60,8 @@
  * that is never actually built (for instance, a dirty node that is verified as clean) is in the
  * "evaluating" state until it is done.
  *
+ * <p>From the "Done" state, the node can go back to the "marked as affected" state.
+ *
  * <p>This class is public only for the benefit of alternative graph implementations outside of the
  * package.
  */
@@ -141,31 +138,6 @@
    */
   @Nullable protected volatile DirtyBuildingState dirtyBuildingState = null;
 
-  private static final int NOT_EVALUATING_SENTINEL = -1;
-
-  /**
-   * The number of dependencies that are known to be done in a {@link NodeEntry} if it is already
-   * evaluating, and a sentinel (-1) indicating that it has not yet started evaluating otherwise.
-   * There is a potential check-then-act race here during evaluation, so we need to make sure that
-   * when this is increased, we always check if the new value is equal to the number of required
-   * dependencies, and if so, we must re-schedule the node for evaluation.
-   *
-   * <p>There are two potential pitfalls here: 1) If multiple dependencies signal this node in close
-   * succession, this node should be scheduled exactly once. 2) If a thread is still working on this
-   * node, it should not be scheduled.
-   *
-   * <p>The first problem is solved by the {@link #signalDep} method, which also returns if the node
-   * needs to be re-scheduled, and ensures that only one thread gets a true return value.
-   *
-   * <p>The second problem is solved by first adding the newly discovered deps to a node's {@link
-   * #directDeps}, and then looping through the direct deps and registering this node as a reverse
-   * dependency. This ensures that the signaledDeps counter can only reach {@link
-   * #directDeps#numElements} on the very last iteration of the loop, i.e., the thread is not
-   * working on the node anymore. Note that this requires that there is no code after the loop in
-   * {@code ParallelEvaluator.Evaluate#run}.
-   */
-  private int signaledDeps = NOT_EVALUATING_SENTINEL;
-
   /**
    * Construct a InMemoryNodeEntry. Use ONLY in Skyframe evaluation and graph implementations.
    */
@@ -181,9 +153,30 @@
     return keepEdges() == KeepEdgesPolicy.ALL;
   }
 
+  private boolean isEvaluating() {
+    return dirtyBuildingState != null;
+  }
+
   @Override
   public boolean isDone() {
-    return value != null && !isEvaluating();
+    return value != null && dirtyBuildingState == null;
+  }
+
+  @Override
+  public synchronized boolean isReady() {
+    Preconditions.checkState(!isDone(), "can't be ready if done: %s", this);
+    Preconditions.checkState(isEvaluating(), this);
+    return dirtyBuildingState.isReady(getNumTemporaryDirectDeps());
+  }
+
+  @Override
+  public synchronized boolean isDirty() {
+    return !isDone() && dirtyBuildingState != null;
+  }
+
+  @Override
+  public synchronized boolean isChanged() {
+    return !isDone() && dirtyBuildingState != null && dirtyBuildingState.isChanged();
   }
 
   @Override
@@ -205,7 +198,7 @@
     } else if (isChanged() || isDirty()) {
       SkyValue lastBuildValue = null;
       try {
-        lastBuildValue = getDirtyBuildingState().getLastBuildValue();
+        lastBuildValue = dirtyBuildingState.getLastBuildValue();
       } catch (InterruptedException e) {
         throw new IllegalStateException("Interruption unexpected: " + this, e);
       }
@@ -243,17 +236,12 @@
     return ValueWithMetadata.getMaybeErrorInfo(value);
   }
 
-  protected DirtyBuildingState getDirtyBuildingState() {
-    return Preconditions.checkNotNull(dirtyBuildingState, "Didn't have state: %s", this);
-  }
-
   /**
    * Puts entry in "done" state, as checked by {@link #isDone}. Subclasses that override one may
    * need to override the other.
    */
   protected void markDone() {
     dirtyBuildingState = null;
-    signaledDeps = NOT_EVALUATING_SENTINEL;
   }
 
   protected final synchronized Set<SkyKey> setStateFinishedAndReturnReverseDepsToSignal() {
@@ -311,13 +299,12 @@
     if (!isEligibleForChangePruningOnUnchangedValue()) {
       this.lastChangedVersion = version;
       this.value = value;
-    } else if (isDirty() && getDirtyBuildingState().unchangedFromLastBuild(value)) {
+    } else if (dirtyBuildingState.unchangedFromLastBuild(value)) {
       // If the value is the same as before, just use the old value. Note that we don't use the new
       // value, because preserving == equality is even better than .equals() equality.
-      this.value = getDirtyBuildingState().getLastBuildValue();
+      this.value = dirtyBuildingState.getLastBuildValue();
     } else {
-      boolean forcedRebuild =
-          isDirty() && getDirtyBuildingState().getDirtyState() == DirtyState.FORCED_REBUILDING;
+      boolean forcedRebuild = dirtyBuildingState.getDirtyState() == DirtyState.FORCED_REBUILDING;
       if (!forcedRebuild && this.lastChangedVersion.equals(version)) {
         logError(
             new ChangedValueAtSameVersionException(this.lastChangedVersion, version, value, this));
@@ -378,8 +365,9 @@
 
   @Override
   public synchronized DependencyState addReverseDepAndCheckIfDone(SkyKey reverseDep) {
+    boolean done = isDone();
     if (reverseDep != null) {
-      if (isDone()) {
+      if (done) {
         if (keepReverseDeps()) {
           ReverseDepsUtility.addReverseDeps(this, ImmutableList.of(reverseDep));
         }
@@ -387,12 +375,15 @@
         appendToReverseDepOperations(reverseDep, Op.ADD);
       }
     }
-    if (isDone()) {
+    if (done) {
       return DependencyState.DONE;
     }
-    boolean result = !isEvaluating();
+    if (dirtyBuildingState == null) {
+      dirtyBuildingState = DirtyBuildingState.createNew();
+    }
+    boolean result = !dirtyBuildingState.isEvaluating();
     if (result) {
-      signaledDeps = 0;
+      dirtyBuildingState.startEvaluating();
     }
     return result ? DependencyState.NEEDS_SCHEDULING : DependencyState.ALREADY_EVALUATING;
   }
@@ -431,8 +422,15 @@
     reverseDepsDataToConsolidate.add(KeyToConsolidate.create(reverseDep, op, getOpToStoreBare()));
   }
 
+  /**
+   * In order to reduce memory consumption, we want to store reverse deps 'bare', i.e., without
+   * wrapping them in a KeyToConsolidate object. To that end, we define a bare op that is used for
+   * both storing and retrieving the deps. This method returns said op, and may adjust it depending
+   * on whether this is a new node entry (where all deps must be new) or an existing node entry
+   * (which most likely checks deps rather than adding new deps).
+   */
   protected OpToStoreBare getOpToStoreBare() {
-    return isDirty() ? OpToStoreBare.CHECK : OpToStoreBare.ADD;
+    return isDirty() && dirtyBuildingState.isDirty() ? OpToStoreBare.CHECK : OpToStoreBare.ADD;
   }
 
   @Override
@@ -494,26 +492,15 @@
   public synchronized boolean signalDep(Version childVersion, @Nullable SkyKey childForDebugging) {
     Preconditions.checkState(
         !isDone(), "Value must not be done in signalDep %s child=%s", this, childForDebugging);
-    Preconditions.checkState(isEvaluating(), "%s %s", this, childForDebugging);
-    signaledDeps++;
-    if (isDirty()) {
-      dirtyBuildingState.signalDepInternal(
-          childCausesReevaluation(lastEvaluatedVersion, childVersion, childForDebugging),
-          isReady());
-    }
+    Preconditions.checkNotNull(dirtyBuildingState, "%s %s", this, childForDebugging);
+    Preconditions.checkState(dirtyBuildingState.isEvaluating(), "%s %s", this, childForDebugging);
+    dirtyBuildingState.signalDep();
+    dirtyBuildingState.signalDepPostProcess(
+        childCausesReevaluation(lastEvaluatedVersion, childVersion, childForDebugging),
+        getNumTemporaryDirectDeps());
     return isReady();
   }
 
-  @Override
-  public synchronized boolean isDirty() {
-    return !isDone() && dirtyBuildingState != null;
-  }
-
-  @Override
-  public synchronized boolean isChanged() {
-    return !isDone() && dirtyBuildingState != null && dirtyBuildingState.isChanged();
-  }
-
   /** Checks that a caller is not trying to access not-stored graph edges. */
   private void assertKeepDeps() {
     Preconditions.checkState(keepEdges() != KeepEdgesPolicy.NONE, "Not keeping deps: %s", this);
@@ -536,7 +523,8 @@
       return new MarkedDirtyResult(ReverseDepsUtility.getReverseDeps(this));
     }
     if (dirtyType.equals(DirtyType.FORCE_REBUILD)) {
-      getDirtyBuildingState().markForceRebuild();
+      Preconditions.checkNotNull(dirtyBuildingState, this);
+      dirtyBuildingState.markForceRebuild();
       return null;
     }
     // The caller may be simultaneously trying to mark this node dirty and changed, and the dirty
@@ -549,19 +537,21 @@
         this);
     Preconditions.checkState(value == null, "Value should have been reset already %s", this);
     if (dirtyType.equals(DirtyType.CHANGE)) {
+      Preconditions.checkNotNull(dirtyBuildingState);
       // If the changed marker lost the race, we just need to mark changed in this method -- all
       // other work was done by the dirty marker.
-      getDirtyBuildingState().markChanged();
+      dirtyBuildingState.markChanged();
     }
     return null;
   }
 
   @Override
   public synchronized Set<SkyKey> markClean() throws InterruptedException {
-    this.value = getDirtyBuildingState().getLastBuildValue();
+    Preconditions.checkNotNull(dirtyBuildingState, this);
+    this.value = Preconditions.checkNotNull(dirtyBuildingState.getLastBuildValue());
     Preconditions.checkState(isReady(), "Should be ready when clean: %s", this);
     Preconditions.checkState(
-        getDirtyBuildingState().depsUnchangedFromLastBuild(getTemporaryDirectDeps()),
+        dirtyBuildingState.depsUnchangedFromLastBuild(getTemporaryDirectDeps()),
         "Direct deps must be the same as those found last build for node to be marked clean: %s",
         this);
     Preconditions.checkState(isDirty(), this);
@@ -571,8 +561,9 @@
 
   @Override
   public synchronized void forceRebuild() {
-    Preconditions.checkState(getNumTemporaryDirectDeps() == signaledDeps, this);
-    getDirtyBuildingState().forceRebuild();
+    Preconditions.checkNotNull(dirtyBuildingState, this);
+    Preconditions.checkState(isEvaluating(), this);
+    dirtyBuildingState.forceRebuild(getNumTemporaryDirectDeps());
   }
 
   @Override
@@ -582,16 +573,18 @@
 
   @Override
   public synchronized NodeEntry.DirtyState getDirtyState() {
-    Preconditions.checkState(isEvaluating(), "Not evaluating for dirty state? %s", this);
-    return getDirtyBuildingState().getDirtyState();
+    Preconditions.checkNotNull(dirtyBuildingState, this);
+    return dirtyBuildingState.getDirtyState();
   }
 
   /** @see DirtyBuildingState#getNextDirtyDirectDeps() */
   @Override
   public synchronized List<SkyKey> getNextDirtyDirectDeps() throws InterruptedException {
     Preconditions.checkState(isReady(), this);
-    Preconditions.checkState(isEvaluating(), "Not evaluating during getNextDirty? %s", this);
-    return getDirtyBuildingState().getNextDirtyDirectDeps();
+    Preconditions.checkNotNull(dirtyBuildingState, this);
+    Preconditions.checkState(
+        dirtyBuildingState.isEvaluating(), "Not evaluating during getNextDirty? %s", this);
+    return dirtyBuildingState.getNextDirtyDirectDeps();
   }
 
   @Override
@@ -606,20 +599,21 @@
       for (Iterable<SkyKey> group : getTemporaryDirectDeps()) {
         result.addAll(group);
       }
-      result.addAll(
-          getDirtyBuildingState().getAllRemainingDirtyDirectDeps(/*preservePosition=*/ false));
+      result.addAll(dirtyBuildingState.getAllRemainingDirtyDirectDeps(/*preservePosition=*/ false));
       return result.build();
     }
   }
 
   @Override
   public synchronized Set<SkyKey> getAllRemainingDirtyDirectDeps() throws InterruptedException {
-    Preconditions.checkState(isEvaluating(), "Not evaluating for remaining dirty? %s", this);
+    Preconditions.checkNotNull(dirtyBuildingState, this);
+    Preconditions.checkState(
+        dirtyBuildingState.isEvaluating(), "Not evaluating for remaining dirty? %s", this);
     if (isDirty()) {
-      DirtyState dirtyState = getDirtyBuildingState().getDirtyState();
+      DirtyState dirtyState = dirtyBuildingState.getDirtyState();
       Preconditions.checkState(
           dirtyState == DirtyState.REBUILDING || dirtyState == DirtyState.FORCED_REBUILDING, this);
-      return getDirtyBuildingState().getAllRemainingDirtyDirectDeps(/*preservePosition=*/ true);
+      return dirtyBuildingState.getAllRemainingDirtyDirectDeps(/*preservePosition=*/ true);
     } else {
       return ImmutableSet.of();
     }
@@ -655,7 +649,8 @@
 
   @Override
   public synchronized void markRebuilding() {
-    getDirtyBuildingState().markRebuilding(isEligibleForChangePruningOnUnchangedValue());
+    Preconditions.checkNotNull(dirtyBuildingState, this);
+    dirtyBuildingState.markRebuilding(isEligibleForChangePruningOnUnchangedValue());
   }
 
   @SuppressWarnings("unchecked")
@@ -675,7 +670,8 @@
 
   @Override
   public synchronized boolean noDepsLastBuild() {
-    return getDirtyBuildingState().noDepsLastBuild();
+    Preconditions.checkState(isEvaluating(), this);
+    return dirtyBuildingState.noDepsLastBuild();
   }
 
   /**
@@ -693,11 +689,9 @@
   @Override
   public synchronized void resetForRestartFromScratch() {
     Preconditions.checkState(!isDone(), "Reset entry can't be done: %s", this);
+    Preconditions.checkState(isEvaluating());
     directDeps = null;
-    signaledDeps = 0;
-    if (dirtyBuildingState != null) {
-      dirtyBuildingState.resetForRestartFromScratch();
-    }
+    dirtyBuildingState.resetForRestartFromScratch();
   }
 
   @Override
@@ -712,18 +706,6 @@
     getTemporaryDirectDeps().appendGroup(group);
   }
 
-  @Override
-  public synchronized boolean isReady() {
-    Preconditions.checkState(!isDone(), "can't be ready if done: %s", this);
-    return isReady(getNumTemporaryDirectDeps());
-  }
-
-  /** Returns whether all known children of this node have signaled that they are done. */
-  private boolean isReady(int numDirectDeps) {
-    Preconditions.checkState(signaledDeps <= numDirectDeps, "%s %s", numDirectDeps, this);
-    return signaledDeps == numDirectDeps;
-  }
-
   /** True if the child should cause re-evaluation of this node. */
   protected boolean childCausesReevaluation(
       Version lastEvaluatedVersion,
@@ -733,18 +715,10 @@
     return !childVersion.atMost(lastEvaluatedVersion);
   }
 
-  protected int getSignaledDeps() {
-    return signaledDeps;
-  }
-
   protected void logError(RuntimeException error) {
     throw error;
   }
 
-  private boolean isEvaluating() {
-    return signaledDeps > NOT_EVALUATING_SENTINEL;
-  }
-
   protected synchronized MoreObjects.ToStringHelper toStringHelper() {
     return MoreObjects.toStringHelper(this)
         .add("identity", System.identityHashCode(this))
@@ -756,7 +730,6 @@
             isDone() && keepEdges() != KeepEdgesPolicy.NONE
                 ? GroupedList.create(directDeps)
                 : directDeps)
-        .add("signaledDeps", signaledDeps)
         .add("reverseDeps", ReverseDepsUtility.toString(this))
         .add("dirtyBuildingState", dirtyBuildingState);
   }
diff --git a/src/main/java/com/google/devtools/build/skyframe/ThinNodeEntry.java b/src/main/java/com/google/devtools/build/skyframe/ThinNodeEntry.java
index 4e11b93..cffbc22 100644
--- a/src/main/java/com/google/devtools/build/skyframe/ThinNodeEntry.java
+++ b/src/main/java/com/google/devtools/build/skyframe/ThinNodeEntry.java
@@ -32,8 +32,8 @@
   boolean isDone();
 
   /**
-   * Returns true if the entry is marked dirty, meaning that at least one of its transitive
-   * dependencies is marked changed.
+   * Returns true if the entry is new or marked as dirty. This includes the case where its deps are
+   * still being checked for up-to-dateness.
    */
   @ThreadSafe
   boolean isDirty();
diff --git a/src/test/java/com/google/devtools/build/skyframe/GraphTest.java b/src/test/java/com/google/devtools/build/skyframe/GraphTest.java
index 216d077..e541316 100644
--- a/src/test/java/com/google/devtools/build/skyframe/GraphTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/GraphTest.java
@@ -210,6 +210,7 @@
     }
     waitForStart.countDown();
     waitForAddedRdep.await(TestUtils.WAIT_TIMEOUT_SECONDS, TimeUnit.SECONDS);
+    entry.markRebuilding();
     entry.setValue(new StringValue("foo1"), startingVersion, null);
     waitForSetValue.countDown();
     wrapper.waitForTasksAndMaybeThrow();
@@ -280,6 +281,7 @@
                     // NEEDS_SCHEDULING at most once.
                     try {
                       if (startEvaluation(entry).equals(DependencyState.NEEDS_SCHEDULING)) {
+                        entry.markRebuilding();
                         assertThat(valuesSet.add(key)).isTrue();
                         // Set to done.
                         entry.setValue(new StringValue("bar" + keyNum), startingVersion, null);
@@ -332,6 +334,7 @@
     for (int i = 0; i < numKeys; i++) {
       NodeEntry entry = entries.get(key("foo" + i));
       startEvaluation(entry);
+      entry.markRebuilding();
       entry.setValue(new StringValue("bar"), startingVersion, null);
     }
 
diff --git a/src/test/java/com/google/devtools/build/skyframe/InMemoryNodeEntryTest.java b/src/test/java/com/google/devtools/build/skyframe/InMemoryNodeEntryTest.java
index 6e8fb52..a344ab2 100644
--- a/src/test/java/com/google/devtools/build/skyframe/InMemoryNodeEntryTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/InMemoryNodeEntryTest.java
@@ -61,8 +61,8 @@
     entry.addReverseDepAndCheckIfDone(null); // Start evaluation.
     assertThat(entry.isDone()).isFalse();
     assertThat(entry.isReady()).isTrue();
-    assertThat(entry.isDirty()).isFalse();
-    assertThat(entry.isChanged()).isFalse();
+    assertThat(entry.isDirty()).isTrue();
+    assertThat(entry.isChanged()).isTrue();
     assertThat(entry.getTemporaryDirectDeps()).isEmpty();
   }
 
@@ -73,6 +73,7 @@
   public void signalEntry() throws InterruptedException {
     NodeEntry entry = new InMemoryNodeEntry();
     entry.addReverseDepAndCheckIfDone(null); // Start evaluation.
+    entry.markRebuilding();
     SkyKey dep1 = key("dep1");
     addTemporaryDirectDep(entry, dep1);
     assertThat(entry.isReady()).isFalse();
@@ -106,6 +107,7 @@
         .isEqualTo(DependencyState.ALREADY_EVALUATING);
     assertThat(entry.addReverseDepAndCheckIfDone(father))
         .isEqualTo(DependencyState.ALREADY_EVALUATING);
+    entry.markRebuilding();
     assertThat(setValue(entry, new SkyValue() {},
         /*errorInfo=*/null, /*graphVersion=*/0L)).containsExactly(mother, father);
     assertThat(entry.getReverseDepsForDoneEntry()).containsExactly(mother, father);
@@ -118,6 +120,7 @@
   public void errorValue() throws InterruptedException {
     NodeEntry entry = new InMemoryNodeEntry();
     entry.addReverseDepAndCheckIfDone(null); // Start evaluation.
+    entry.markRebuilding();
     ReifiedSkyFunctionException exception = new ReifiedSkyFunctionException(
         new GenericFunctionException(new SomeErrorException("oops"), Transience.PERSISTENT),
         key("cause"));
@@ -132,6 +135,7 @@
   public void errorAndValue() throws InterruptedException {
     NodeEntry entry = new InMemoryNodeEntry();
     entry.addReverseDepAndCheckIfDone(null); // Start evaluation.
+    entry.markRebuilding();
     ReifiedSkyFunctionException exception = new ReifiedSkyFunctionException(
         new GenericFunctionException(new SomeErrorException("oops"), Transience.PERSISTENT),
         key("cause"));
@@ -145,6 +149,7 @@
   public void crashOnNullErrorAndValue() throws InterruptedException {
     NodeEntry entry = new InMemoryNodeEntry();
     entry.addReverseDepAndCheckIfDone(null); // Start evaluation.
+    entry.markRebuilding();
     try {
       setValue(entry, /*value=*/null, /*errorInfo=*/null, /*graphVersion=*/0L);
       fail();
@@ -157,6 +162,7 @@
   public void crashOnTooManySignals() {
     InMemoryNodeEntry entry = new InMemoryNodeEntry();
     entry.addReverseDepAndCheckIfDone(null); // Start evaluation.
+    entry.markRebuilding();
     try {
       entry.signalDep(ZERO_VERSION, null);
       fail();
@@ -169,6 +175,7 @@
   public void crashOnSetValueWhenDone() throws InterruptedException {
     NodeEntry entry = new InMemoryNodeEntry();
     entry.addReverseDepAndCheckIfDone(null); // Start evaluation.
+    entry.markRebuilding();
     setValue(entry, new SkyValue() {}, /*errorInfo=*/ null, /*graphVersion=*/ 0L);
     assertThat(entry.isDone()).isTrue();
     try {
@@ -183,6 +190,7 @@
   public void crashOnChangedValueAtSameVersion() throws InterruptedException {
     NodeEntry entry = new InMemoryNodeEntry();
     entry.addReverseDepAndCheckIfDone(null);
+    entry.markRebuilding();
     setValue(entry, new IntegerValue(1), /*errorInfo=*/ null, /*graphVersion=*/ 0L);
     entry.markDirty(DirtyType.CHANGE);
     entry.addReverseDepAndCheckIfDone(null);
@@ -199,6 +207,7 @@
   public void dirtyLifecycle() throws InterruptedException {
     NodeEntry entry = new InMemoryNodeEntry();
     entry.addReverseDepAndCheckIfDone(null); // Start evaluation.
+    entry.markRebuilding();
     SkyKey dep = key("dep");
     addTemporaryDirectDep(entry, dep);
     entry.signalDep(ZERO_VERSION, dep);
@@ -223,14 +232,15 @@
     assertThatNodeEntry(entry).hasTemporaryDirectDepsThat().containsExactly(dep);
     assertThat(entry.isReady()).isTrue();
     entry.markRebuilding();
-    assertThat(setValue(entry, new SkyValue() {}, /*errorInfo=*/null,
-        /*graphVersion=*/1L)).containsExactly(parent);
+    assertThat(setValue(entry, new SkyValue() {}, /*errorInfo=*/ null, /*graphVersion=*/ 1L))
+        .containsExactly(parent);
   }
 
   @Test
   public void changedLifecycle() throws InterruptedException {
     NodeEntry entry = new InMemoryNodeEntry();
     entry.addReverseDepAndCheckIfDone(null); // Start evaluation.
+    entry.markRebuilding();
     SkyKey dep = key("dep");
     addTemporaryDirectDep(entry, dep);
     entry.signalDep(ZERO_VERSION, dep);
@@ -260,6 +270,7 @@
   public void forceRebuildLifecycle() throws InterruptedException {
     NodeEntry entry = new InMemoryNodeEntry();
     entry.addReverseDepAndCheckIfDone(null); // Start evaluation.
+    entry.markRebuilding();
     SkyKey dep = key("dep");
     addTemporaryDirectDep(entry, dep);
     entry.signalDep(ZERO_VERSION, dep);
@@ -295,6 +306,7 @@
   public void markDirtyThenChanged() throws InterruptedException {
     NodeEntry entry = new InMemoryNodeEntry();
     entry.addReverseDepAndCheckIfDone(null); // Start evaluation.
+    entry.markRebuilding();
     SkyKey dep = key("dep");
     addTemporaryDirectDep(entry, dep);
     entry.signalDep(ZERO_VERSION, dep);
@@ -320,6 +332,7 @@
   public void markChangedThenDirty() throws InterruptedException {
     NodeEntry entry = new InMemoryNodeEntry();
     entry.addReverseDepAndCheckIfDone(null); // Start evaluation.
+    entry.markRebuilding();
     SkyKey dep = key("dep");
     addTemporaryDirectDep(entry, dep);
     entry.signalDep(ZERO_VERSION, dep);
@@ -344,6 +357,7 @@
   public void crashOnTwiceMarkedChanged() throws InterruptedException {
     NodeEntry entry = new InMemoryNodeEntry();
     entry.addReverseDepAndCheckIfDone(null); // Start evaluation.
+    entry.markRebuilding();
     setValue(entry, new SkyValue() {}, /*errorInfo=*/ null, /*graphVersion=*/ 0L);
     assertThat(entry.isDirty()).isFalse();
     assertThat(entry.isDone()).isTrue();
@@ -360,6 +374,7 @@
   public void crashOnTwiceMarkedDirty() throws InterruptedException {
     NodeEntry entry = new InMemoryNodeEntry();
     entry.addReverseDepAndCheckIfDone(null); // Start evaluation.
+    entry.markRebuilding();
     SkyKey dep = key("dep");
     addTemporaryDirectDep(entry, dep);
     entry.signalDep(ZERO_VERSION, dep);
@@ -377,6 +392,7 @@
   public void allowTwiceMarkedForceRebuild() throws InterruptedException {
     NodeEntry entry = new InMemoryNodeEntry();
     entry.addReverseDepAndCheckIfDone(null); // Start evaluation.
+    entry.markRebuilding();
     setValue(entry, new SkyValue() {}, /*errorInfo=*/ null, /*graphVersion=*/ 0L);
     assertThat(entry.isDirty()).isFalse();
     assertThat(entry.isDone()).isTrue();
@@ -395,6 +411,7 @@
         .isEqualTo(DependencyState.NEEDS_SCHEDULING);
     try {
       entry.addReverseDepAndCheckIfDone(parent);
+      entry.markRebuilding();
       assertThat(setValue(entry, new SkyValue() {}, /*errorInfo=*/null, /*graphVersion=*/0L))
           .containsExactly(parent);
       fail("Cannot add same dep twice");
@@ -407,6 +424,7 @@
   public void crashOnAddReverseDepTwiceAfterDone() throws InterruptedException {
     NodeEntry entry = new InMemoryNodeEntry();
     entry.addReverseDepAndCheckIfDone(null); // Start evaluation.
+    entry.markRebuilding();
     setValue(entry, new SkyValue() {}, /*errorInfo=*/null, /*graphVersion=*/0L);
     SkyKey parent = key("parent");
     assertThat(entry.addReverseDepAndCheckIfDone(parent)).isEqualTo(DependencyState.DONE);
@@ -426,6 +444,7 @@
     SkyKey parent = key("parent");
     assertThat(entry.addReverseDepAndCheckIfDone(parent))
         .isEqualTo(DependencyState.NEEDS_SCHEDULING);
+    entry.markRebuilding();
     setValue(entry, new SkyValue() {}, /*errorInfo=*/null, /*graphVersion=*/0L);
     try {
       entry.addReverseDepAndCheckIfDone(parent);
@@ -442,6 +461,7 @@
     NodeEntry entry = new InMemoryNodeEntry();
     SkyKey dep = key("dep");
     entry.addReverseDepAndCheckIfDone(null); // Start evaluation.
+    entry.markRebuilding();
     addTemporaryDirectDep(entry, dep);
     entry.signalDep(ZERO_VERSION, dep);
     setValue(entry, new SkyValue() {}, /*errorInfo=*/null, /*graphVersion=*/0L);
@@ -489,6 +509,7 @@
   public void pruneAfterBuild() throws InterruptedException {
     NodeEntry entry = new InMemoryNodeEntry();
     entry.addReverseDepAndCheckIfDone(null); // Start evaluation.
+    entry.markRebuilding();
     SkyKey dep = key("dep");
     addTemporaryDirectDep(entry, dep);
     entry.signalDep(ZERO_VERSION, dep);
@@ -512,6 +533,7 @@
   public void noPruneWhenDetailsChange() throws InterruptedException {
     NodeEntry entry = new InMemoryNodeEntry();
     entry.addReverseDepAndCheckIfDone(null); // Start evaluation.
+    entry.markRebuilding();
     SkyKey dep = key("dep");
     addTemporaryDirectDep(entry, dep);
     entry.signalDep(ZERO_VERSION, dep);
@@ -550,6 +572,7 @@
   public void pruneWhenDepGroupReordered() throws InterruptedException {
     NodeEntry entry = new InMemoryNodeEntry();
     entry.addReverseDepAndCheckIfDone(null); // Start evaluation.
+    entry.markRebuilding();
     SkyKey dep = key("dep");
     SkyKey dep1InGroup = key("dep1InGroup");
     SkyKey dep2InGroup = key("dep2InGroup");
@@ -591,6 +614,7 @@
   public void errorInfoCannotBePruned() throws InterruptedException {
     NodeEntry entry = new InMemoryNodeEntry();
     entry.addReverseDepAndCheckIfDone(null); // Start evaluation.
+    entry.markRebuilding();
     SkyKey dep = key("dep");
     addTemporaryDirectDep(entry, dep);
     entry.signalDep(ZERO_VERSION, dep);
@@ -636,6 +660,7 @@
   public void getDependencyGroup() throws InterruptedException {
     NodeEntry entry = new InMemoryNodeEntry();
     entry.addReverseDepAndCheckIfDone(null); // Start evaluation.
+    entry.markRebuilding();
     SkyKey dep = key("dep");
     SkyKey dep2 = key("dep2");
     SkyKey dep3 = key("dep3");
@@ -660,6 +685,7 @@
   public void maintainDependencyGroupAfterRemoval() throws InterruptedException {
     NodeEntry entry = new InMemoryNodeEntry();
     entry.addReverseDepAndCheckIfDone(null); // Start evaluation.
+    entry.markRebuilding();
     SkyKey dep = key("dep");
     SkyKey dep2 = key("dep2");
     SkyKey dep3 = key("dep3");
@@ -690,6 +716,7 @@
   public void pruneWhenDepsChange() throws InterruptedException {
     NodeEntry entry = new InMemoryNodeEntry();
     entry.addReverseDepAndCheckIfDone(null); // Start evaluation.
+    entry.markRebuilding();
     SkyKey dep = key("dep");
     addTemporaryDirectDep(entry, dep);
     entry.signalDep(ZERO_VERSION, dep);
@@ -714,6 +741,7 @@
   public void checkDepsOneByOne() throws InterruptedException {
     NodeEntry entry = new InMemoryNodeEntry();
     entry.addReverseDepAndCheckIfDone(null); // Start evaluation.
+    entry.markRebuilding();
     List<SkyKey> deps = new ArrayList<>();
     for (int ii = 0; ii < 10; ii++) {
       SkyKey dep = key(Integer.toString(ii));
@@ -741,12 +769,14 @@
   public void signalOnlyNewParents() throws InterruptedException {
     NodeEntry entry = new InMemoryNodeEntry();
     entry.addReverseDepAndCheckIfDone(key("parent"));
+    entry.markRebuilding();
     setValue(entry, new SkyValue() {}, /*errorInfo=*/null, /*graphVersion=*/0L);
     entry.markDirty(DirtyType.CHANGE);
     SkyKey newParent = key("new parent");
     entry.addReverseDepAndCheckIfDone(newParent);
     assertThat(entry.getDirtyState()).isEqualTo(NodeEntry.DirtyState.NEEDS_REBUILDING);
     entry.markRebuilding();
+    assertThat(entry.getDirtyState()).isEqualTo(NodeEntry.DirtyState.REBUILDING);
     assertThat(setValue(entry, new SkyValue() {}, /*errorInfo=*/null,
         /*graphVersion=*/1L)).containsExactly(newParent);
   }
@@ -760,6 +790,7 @@
     assertThatNodeEntry(entry)
         .addReverseDepAndCheckIfDone(null)
         .isEqualTo(DependencyState.NEEDS_SCHEDULING);
+    entry.markRebuilding();
     addTemporaryDirectDep(entry, originalChild);
     entry.signalDep(ZERO_VERSION, originalChild);
     entry.setValue(originalValue, version, null);
@@ -806,6 +837,7 @@
     assertThatNodeEntry(entry)
         .addReverseDepAndCheckIfDone(null)
         .isEqualTo(DependencyState.NEEDS_SCHEDULING);
+    entry.markRebuilding();
     for (Set<SkyKey> depGroup : groupedDirectDeps) {
       GroupedListHelper<SkyKey> helper = new GroupedListHelper<>();
       helper.startGroup();