diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/rewinding/RewindableGraphInconsistencyReceiver.java b/src/main/java/com/google/devtools/build/lib/skyframe/rewinding/RewindableGraphInconsistencyReceiver.java
index 1e4e24e..bd2167c 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/rewinding/RewindableGraphInconsistencyReceiver.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/rewinding/RewindableGraphInconsistencyReceiver.java
@@ -95,18 +95,11 @@
             key, childrenAsString);
         return;
 
-      case PARENT_FORCE_REBUILD_OF_MISSING_CHILD:
-      case DIRTY_PARENT_HAD_MISSING_CHILD:
-      case ALREADY_DECLARED_CHILD_MISSING:
+      default:
         throw new IllegalStateException(
             String.format(
                 "Unexpected inconsistency %s, key = %s, otherKeys = %s ",
                 inconsistency, key, childrenAsString));
-      default: // Needed because protobuf creates additional enum values.
-        throw new IllegalStateException(
-            String.format(
-                "Unknown inconsistency %s, key = %s, otherKeys = %s ",
-                inconsistency, key, childrenAsString));
     }
   }
 
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 01e1f6b..b49c2cf 100644
--- a/src/main/java/com/google/devtools/build/skyframe/AbstractParallelEvaluator.java
+++ b/src/main/java/com/google/devtools/build/skyframe/AbstractParallelEvaluator.java
@@ -13,9 +13,12 @@
 // limitations under the License.
 package com.google.devtools.build.skyframe;
 
+import static com.google.common.base.Preconditions.checkArgument;
+import static com.google.common.base.Preconditions.checkNotNull;
+import static com.google.common.base.Preconditions.checkState;
+
 import com.github.benmanes.caffeine.cache.Cache;
 import com.github.benmanes.caffeine.cache.Caffeine;
-import com.google.common.base.Preconditions;
 import com.google.common.base.Throwables;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
@@ -51,7 +54,6 @@
 import com.google.devtools.build.skyframe.proto.GraphInconsistency.Inconsistency;
 import java.io.IOException;
 import java.time.Duration;
-import java.util.ArrayList;
 import java.util.Collection;
 import java.util.Iterator;
 import java.util.List;
@@ -293,7 +295,7 @@
         int childEvaluationPriority,
         boolean enqueueParentIfReady)
         throws InterruptedException {
-      Preconditions.checkState(!entry.isDone(), "%s %s", skyKey, entry);
+      checkState(!entry.isDone(), "%s %s", skyKey, entry);
       DependencyState dependencyState;
       try {
         dependencyState =
@@ -423,7 +425,7 @@
               nodeEntry.signalDep(MinimalVersion.INSTANCE, /*childForDebugging=*/ null);
         }
         if (needsScheduling) {
-          Preconditions.checkState(
+          checkState(
               unknownStatusDeps.isEmpty(),
               "Ready without all deps checked? %s %s %s",
               skyKey,
@@ -543,9 +545,8 @@
     public void run() {
       SkyFunctionEnvironment env = null;
       try {
-        NodeEntry nodeEntry =
-            Preconditions.checkNotNull(graph.get(null, Reason.EVALUATION, skyKey), skyKey);
-        Preconditions.checkState(nodeEntry.isReady(), "%s %s", skyKey, nodeEntry);
+        NodeEntry nodeEntry = checkNotNull(graph.get(null, Reason.EVALUATION, skyKey), skyKey);
+        checkState(nodeEntry.isReady(), "%s %s", skyKey, nodeEntry);
         try {
           evaluatorContext.getProgressReceiver().stateStarting(skyKey, NodeState.CHECK_DIRTY);
           if (maybeHandleDirtyNode(nodeEntry) == DirtyOutcome.ALREADY_PROCESSED) {
@@ -576,7 +577,7 @@
         }
         SkyFunctionName functionName = skyKey.functionName();
         SkyFunction skyFunction =
-            Preconditions.checkNotNull(
+            checkNotNull(
                 evaluatorContext.getSkyFunctions().get(functionName),
                 "Unable to find SkyFunction '%s' for node with key %s, %s",
                 functionName,
@@ -683,7 +684,7 @@
         if (value != null) {
           stateCache.invalidate(skyKey);
 
-          Preconditions.checkState(
+          checkState(
               !env.valuesMissing(),
               "Evaluation of %s returned non-null value but requested dependencies that weren't "
                   + "computed yet (one of %s), NodeEntry: %s",
@@ -711,14 +712,13 @@
 
         SkyKey childErrorKey = env.getDepErrorKey();
         if (childErrorKey != null) {
-          Preconditions.checkState(
-              !evaluatorContext.keepGoing(), "%s %s %s", skyKey, nodeEntry, childErrorKey);
+          checkState(!evaluatorContext.keepGoing(), "%s %s %s", skyKey, nodeEntry, childErrorKey);
           // We encountered a child error in noKeepGoing mode, so we want to fail fast. But we first
           // need to add the edge between the current node and the child error it requested so that
           // error bubbling can occur. Note that this edge will subsequently be removed during graph
           // cleaning (since the current node will never be committed to the graph).
           NodeEntry childErrorEntry =
-              Preconditions.checkNotNull(
+              checkNotNull(
                   graph.get(skyKey, Reason.OTHER, childErrorKey),
                   "skyKey: %s, nodeEntry: %s childErrorKey: %s",
                   skyKey,
@@ -750,13 +750,13 @@
             }
           }
           SkyValue childErrorInfoMaybe =
-              Preconditions.checkNotNull(
+              checkNotNull(
                   env.maybeGetValueFromErrorOrDeps(childErrorKey),
                   "dep error found but then lost while building: %s %s",
                   skyKey,
                   childErrorKey);
           ErrorInfo childErrorInfo =
-              Preconditions.checkNotNull(
+              checkNotNull(
                   ValueWithMetadata.getMaybeErrorInfo(childErrorInfoMaybe),
                   "dep error found but then wasn't an error while building: %s %s %s",
                   skyKey,
@@ -788,12 +788,12 @@
         // we just order it to be built.
         if (uniqueNewDeps.isEmpty() && externalDeps == null) {
           // TODO(bazel-team): This means a bug in the SkyFunction. What to do?
-          Preconditions.checkState(
+          checkState(
               !env.getChildErrorInfos().isEmpty(),
               "Evaluation of SkyKey failed and no dependencies were requested: %s %s",
               skyKey,
               nodeEntry);
-          Preconditions.checkState(
+          checkState(
               evaluatorContext.keepGoing(),
               "nokeep_going evaluation should have failed on first child error: %s %s %s",
               skyKey,
@@ -967,7 +967,7 @@
       restart(key, entry);
       return true;
     }
-    Preconditions.checkArgument(
+    checkArgument(
         rewindGraph.nodes().contains(key),
         "rewindGraph must contain the key for the failed evaluation if it's not empty. key: %s, "
             + "rewindGraph: %s",
@@ -980,43 +980,32 @@
         builder.add(k);
       }
     }
-    ImmutableList<SkyKey> additionalKeysToRestart = builder.build();
-    if (!additionalKeysToRestart.isEmpty()) {
+    ImmutableList<SkyKey> childrenToRestart = builder.build();
+    if (!childrenToRestart.isEmpty()) {
       evaluatorContext
           .getGraphInconsistencyReceiver()
           .noteInconsistencyAndMaybeThrow(
-              key, additionalKeysToRestart, Inconsistency.PARENT_FORCE_REBUILD_OF_CHILD);
-    }
+              key, childrenToRestart, Inconsistency.PARENT_FORCE_REBUILD_OF_CHILD);
 
-    Map<SkyKey, ? extends NodeEntry> additionalNodesToRestart =
-        evaluatorContext.getBatchValues(key, Reason.REWINDING, additionalKeysToRestart);
+      Map<SkyKey, ? extends NodeEntry> children =
+          evaluatorContext.getBatchValues(key, Reason.REWINDING, childrenToRestart);
 
-    ArrayList<SkyKey> missingNodes = null;
-    for (SkyKey keyToRestart : additionalKeysToRestart) {
-      NodeEntry restartEntry = additionalNodesToRestart.get(keyToRestart);
+      for (SkyKey childToRestart : childrenToRestart) {
+        NodeEntry childEntry =
+            checkNotNull(
+                children.get(childToRestart),
+                "Missing child for rewinding: %s (parent=%s)",
+                childToRestart,
+                key);
 
-      if (restartEntry == null) {
-        if (missingNodes == null) {
-          missingNodes = new ArrayList<>();
+        // Nodes are marked "force-rebuild" to ensure that they run, and to allow them to evaluate
+        // to a different value than before, even if their versions remain the same.
+        if (childEntry.markDirty(DirtyType.FORCE_REBUILD) != null) {
+          evaluatorContext
+              .getProgressReceiver()
+              .invalidated(childToRestart, EvaluationProgressReceiver.InvalidationState.DIRTY);
         }
-        missingNodes.add(keyToRestart);
-        continue;
       }
-
-      // Nodes are marked "force-rebuild" to ensure that they run, and to allow them to evaluate to
-      // a different value than before, even if their versions remain the same.
-      if (restartEntry.markDirty(DirtyType.FORCE_REBUILD) != null) {
-        evaluatorContext
-            .getProgressReceiver()
-            .invalidated(keyToRestart, EvaluationProgressReceiver.InvalidationState.DIRTY);
-      }
-    }
-
-    if (missingNodes != null) {
-      evaluatorContext
-          .getGraphInconsistencyReceiver()
-          .noteInconsistencyAndMaybeThrow(
-              key, missingNodes, Inconsistency.PARENT_FORCE_REBUILD_OF_MISSING_CHILD);
     }
 
     // TODO(b/19539699): rdeps of children have to be handled here. If the graph does not keep
@@ -1042,8 +1031,7 @@
       evaluatorContext
           .getReporter()
           .handle(Event.error("Crashes detected: " + evaluatorContext.getVisitor().getCrashes()));
-      throw Preconditions.checkNotNull(
-          Iterables.getFirst(evaluatorContext.getVisitor().getCrashes(), null));
+      throw checkNotNull(Iterables.getFirst(evaluatorContext.getVisitor().getCrashes(), null));
     }
   }
 
@@ -1146,7 +1134,7 @@
       }
     }
 
-    Preconditions.checkState(
+    checkState(
         selfSignalled || dirtyDepFound || uniqueNewDeps.isEmpty(),
         "%s %s %s %s",
         skyKey,
@@ -1175,8 +1163,7 @@
           .noteInconsistencyAndMaybeThrow(
               depKey, missing, Inconsistency.ALREADY_DECLARED_CHILD_MISSING);
       depEntry =
-          Preconditions.checkNotNull(
-              graph.createIfAbsentBatch(requestor, reason, missing).get(depKey), depKey);
+          checkNotNull(graph.createIfAbsentBatch(requestor, reason, missing).get(depKey), depKey);
     }
     return depEntry;
   }
diff --git a/src/main/java/com/google/devtools/build/skyframe/graph_inconsistency.proto b/src/main/java/com/google/devtools/build/skyframe/graph_inconsistency.proto
index f391bdd..6724022 100644
--- a/src/main/java/com/google/devtools/build/skyframe/graph_inconsistency.proto
+++ b/src/main/java/com/google/devtools/build/skyframe/graph_inconsistency.proto
@@ -26,7 +26,10 @@
   RESET_REQUESTED = 1;
   DIRTY_PARENT_HAD_MISSING_CHILD = 2;
   PARENT_FORCE_REBUILD_OF_CHILD = 3;
-  PARENT_FORCE_REBUILD_OF_MISSING_CHILD = 4;
+  // Deprecated: children requested for rewinding should be created if absent.
+  // A missing child is not tolerated and results in a crash, so this
+  // inconsistency will not appear in InconsistencyStats.
+  PARENT_FORCE_REBUILD_OF_MISSING_CHILD = 4 [deprecated = true];
   BUILDING_PARENT_FOUND_UNDONE_CHILD = 5;
   ALREADY_DECLARED_CHILD_MISSING = 6;
 }