diff --git a/src/main/java/com/google/devtools/build/skyframe/DelegatingWalkableGraph.java b/src/main/java/com/google/devtools/build/skyframe/DelegatingWalkableGraph.java
index 7a584ec..b6c5825 100644
--- a/src/main/java/com/google/devtools/build/skyframe/DelegatingWalkableGraph.java
+++ b/src/main/java/com/google/devtools/build/skyframe/DelegatingWalkableGraph.java
@@ -18,7 +18,7 @@
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.Maps;
 import com.google.devtools.build.lib.util.Preconditions;
-
+import com.google.devtools.build.skyframe.QueryableGraph.Reason;
 import java.util.EnumSet;
 import java.util.HashMap;
 import java.util.Map;
@@ -39,7 +39,8 @@
   private NodeEntry getEntry(SkyKey key) {
     NodeEntry entry =
         Preconditions.checkNotNull(
-            graph.getBatchWithFieldHints(ImmutableList.of(key), NodeEntryField.VALUE_ONLY).get(key),
+            graph.getBatchWithFieldHints(
+                null, Reason.OTHER, ImmutableList.of(key), NodeEntryField.VALUE_ONLY).get(key),
             key);
     Preconditions.checkState(entry.isDone(), "%s %s", key, entry);
     return entry;
@@ -48,7 +49,8 @@
   @Override
   public boolean exists(SkyKey key) {
     NodeEntry entry =
-        graph.getBatchWithFieldHints(ImmutableList.of(key), NodeEntryField.NO_FIELDS).get(key);
+        graph.getBatchWithFieldHints(
+            null, Reason.OTHER, ImmutableList.of(key), NodeEntryField.NO_FIELDS).get(key);
     return entry != null && entry.isDone();
   }
 
@@ -71,7 +73,8 @@
   public Map<SkyKey, SkyValue> getSuccessfulValues(Iterable<SkyKey> keys) {
     return Maps.filterValues(
         Maps.transformValues(
-            graph.getBatchWithFieldHints(keys, NodeEntryField.VALUE_ONLY), GET_SKY_VALUE_FUNCTION),
+            graph.getBatchWithFieldHints(null, Reason.OTHER, keys, NodeEntryField.VALUE_ONLY),
+            GET_SKY_VALUE_FUNCTION),
         Predicates.notNull());
   }
 
@@ -79,7 +82,7 @@
   public Map<SkyKey, Exception> getMissingAndExceptions(Iterable<SkyKey> keys) {
     Map<SkyKey, Exception> result = new HashMap<>();
     Map<SkyKey, NodeEntry> graphResult =
-        graph.getBatchWithFieldHints(keys, NodeEntryField.VALUE_ONLY);
+        graph.getBatchWithFieldHints(null, Reason.OTHER, keys, NodeEntryField.VALUE_ONLY);
     for (SkyKey key : keys) {
       NodeEntry nodeEntry = graphResult.get(key);
       if (nodeEntry == null || !nodeEntry.isDone()) {
@@ -103,8 +106,8 @@
 
   @Override
   public Map<SkyKey, Iterable<SkyKey>> getDirectDeps(Iterable<SkyKey> keys) {
-    Map<SkyKey, NodeEntry> entries =
-        graph.getBatchWithFieldHints(keys, EnumSet.of(NodeEntryField.DIRECT_DEPS));
+    Map<SkyKey, NodeEntry> entries = graph.getBatchWithFieldHints(
+        null, Reason.OTHER, keys, EnumSet.of(NodeEntryField.DIRECT_DEPS));
     Map<SkyKey, Iterable<SkyKey>> result = new HashMap<>(entries.size());
     for (Entry<SkyKey, NodeEntry> entry : entries.entrySet()) {
       Preconditions.checkState(entry.getValue().isDone(), entry);
@@ -115,8 +118,8 @@
 
   @Override
   public Map<SkyKey, Iterable<SkyKey>> getReverseDeps(Iterable<SkyKey> keys) {
-    Map<SkyKey, NodeEntry> entries =
-        graph.getBatchWithFieldHints(keys, EnumSet.of(NodeEntryField.REVERSE_DEPS));
+    Map<SkyKey, NodeEntry> entries = graph.getBatchWithFieldHints(
+        null, Reason.OTHER, keys, EnumSet.of(NodeEntryField.REVERSE_DEPS));
     Map<SkyKey, Iterable<SkyKey>> result = new HashMap<>(entries.size());
     for (Entry<SkyKey, NodeEntry> entry : entries.entrySet()) {
       Preconditions.checkState(entry.getValue().isDone(), entry);
diff --git a/src/main/java/com/google/devtools/build/skyframe/EvaluableGraph.java b/src/main/java/com/google/devtools/build/skyframe/EvaluableGraph.java
index a9c067d..0db7dad 100644
--- a/src/main/java/com/google/devtools/build/skyframe/EvaluableGraph.java
+++ b/src/main/java/com/google/devtools/build/skyframe/EvaluableGraph.java
@@ -14,8 +14,8 @@
 package com.google.devtools.build.skyframe;
 
 import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
-
 import java.util.Map;
+import javax.annotation.Nullable;
 
 /**
  * Interface between a single version of the graph and the evaluator. Supports mutation of that
@@ -27,6 +27,11 @@
    * Like {@link QueryableGraph#getBatchWithFieldHints}, except it creates a new node for each key
    * not already present in the graph. Thus, the returned map will have an entry for each key in
    * {@code keys}.
+   *
+   * @param requestor if non-{@code null}, the node on behalf of which the given {@code keys} are
+   *     being requested.
+   * @param reason the reason the nodes are being requested.
    */
-  Map<SkyKey, NodeEntry> createIfAbsentBatch(Iterable<SkyKey> keys);
+  Map<SkyKey, NodeEntry> createIfAbsentBatch(
+      @Nullable SkyKey requestor, Reason reason, Iterable<SkyKey> keys);
 }
diff --git a/src/main/java/com/google/devtools/build/skyframe/InMemoryGraph.java b/src/main/java/com/google/devtools/build/skyframe/InMemoryGraph.java
index 6f25093..9eee52e 100644
--- a/src/main/java/com/google/devtools/build/skyframe/InMemoryGraph.java
+++ b/src/main/java/com/google/devtools/build/skyframe/InMemoryGraph.java
@@ -18,7 +18,7 @@
 /** {@link ProcessableGraph} that exposes the contents of the entire graph. */
 interface InMemoryGraph extends ProcessableGraph, InvalidatableGraph {
   @Override
-  Map<SkyKey, NodeEntry> getBatch(Iterable<SkyKey> keys);
+  Map<SkyKey, NodeEntry> getBatchForInvalidation(Iterable<SkyKey> keys);
 
   /**
    * Returns a read-only live view of the nodes in the graph. All node are included. Dirty values
diff --git a/src/main/java/com/google/devtools/build/skyframe/InMemoryGraphImpl.java b/src/main/java/com/google/devtools/build/skyframe/InMemoryGraphImpl.java
index ef6e24b..e068c3f 100644
--- a/src/main/java/com/google/devtools/build/skyframe/InMemoryGraphImpl.java
+++ b/src/main/java/com/google/devtools/build/skyframe/InMemoryGraphImpl.java
@@ -19,11 +19,11 @@
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.MapMaker;
 import com.google.common.collect.Maps;
-
 import java.util.Collections;
 import java.util.EnumSet;
 import java.util.Map;
 import java.util.concurrent.ConcurrentMap;
+import javax.annotation.Nullable;
 
 /**
  * An in-memory graph implementation. All operations are thread-safe with ConcurrentMap semantics.
@@ -51,15 +51,15 @@
   }
 
   @Override
-  public NodeEntry get(SkyKey skyKey) {
+  public NodeEntry get(@Nullable SkyKey requestor, Reason reason, SkyKey skyKey) {
     return nodeMap.get(skyKey);
   }
 
   @Override
-  public Map<SkyKey, NodeEntry> getBatch(Iterable<SkyKey> keys) {
+  public Map<SkyKey, NodeEntry> getBatchForInvalidation(Iterable<SkyKey> keys) {
     ImmutableMap.Builder<SkyKey, NodeEntry> builder = ImmutableMap.builder();
     for (SkyKey key : keys) {
-      NodeEntry entry = get(key);
+      NodeEntry entry = get(null, Reason.OTHER, key);
       if (entry != null) {
         builder.put(key, entry);
       }
@@ -69,8 +69,8 @@
 
   @Override
   public Map<SkyKey, NodeEntry> getBatchWithFieldHints(
-      Iterable<SkyKey> keys, EnumSet<NodeEntryField> fields) {
-    return getBatch(keys);
+      SkyKey requestor, Reason reason, Iterable<SkyKey> keys, EnumSet<NodeEntryField> fields) {
+    return getBatchForInvalidation(keys);
   }
 
   protected NodeEntry createIfAbsent(SkyKey key) {
@@ -80,7 +80,8 @@
   }
 
   @Override
-  public Map<SkyKey, NodeEntry> createIfAbsentBatch(Iterable<SkyKey> keys) {
+  public Map<SkyKey, NodeEntry> createIfAbsentBatch(
+      @Nullable SkyKey requestor, Reason reason, Iterable<SkyKey> keys) {
     ImmutableMap.Builder<SkyKey, NodeEntry> builder = ImmutableMap.builder();
     for (SkyKey key : keys) {
       builder.put(key, createIfAbsent(key));
diff --git a/src/main/java/com/google/devtools/build/skyframe/InMemoryMemoizingEvaluator.java b/src/main/java/com/google/devtools/build/skyframe/InMemoryMemoizingEvaluator.java
index 5d853b7..38604ed 100644
--- a/src/main/java/com/google/devtools/build/skyframe/InMemoryMemoizingEvaluator.java
+++ b/src/main/java/com/google/devtools/build/skyframe/InMemoryMemoizingEvaluator.java
@@ -29,7 +29,7 @@
 import com.google.devtools.build.skyframe.InvalidatingNodeVisitor.InvalidationState;
 import com.google.devtools.build.skyframe.ParallelEvaluator.EventFilter;
 import com.google.devtools.build.skyframe.ParallelEvaluator.Receiver;
-
+import com.google.devtools.build.skyframe.QueryableGraph.Reason;
 import java.io.PrintStream;
 import java.util.Collection;
 import java.util.HashMap;
@@ -129,7 +129,7 @@
         Sets.filter(dirtyKeyTracker.getDirtyKeys(), new Predicate<SkyKey>() {
           @Override
           public boolean apply(SkyKey skyKey) {
-            NodeEntry entry = graph.get(skyKey);
+            NodeEntry entry = graph.get(null, Reason.OTHER, skyKey);
             Preconditions.checkNotNull(entry, skyKey);
             Preconditions.checkState(entry.isDirty(), skyKey);
             return entry.getVersion().atMost(threshold);
@@ -207,7 +207,7 @@
       Entry<SkyKey, SkyValue> entry = it.next();
       SkyKey key = entry.getKey();
       SkyValue newValue = entry.getValue();
-      NodeEntry prevEntry = graph.get(key);
+      NodeEntry prevEntry = graph.get(null, Reason.OTHER, key);
       if (prevEntry != null && prevEntry.isDone()) {
         Iterable<SkyKey> directDeps = prevEntry.getDirectDeps();
         Preconditions.checkState(Iterables.isEmpty(directDeps),
@@ -280,7 +280,7 @@
   @Nullable
   @Override
   public NodeEntry getExistingEntryForTesting(SkyKey key) {
-    return graph.get(key);
+    return graph.get(null, Reason.OTHER, key);
   }
 
   @Override
diff --git a/src/main/java/com/google/devtools/build/skyframe/InvalidatableGraph.java b/src/main/java/com/google/devtools/build/skyframe/InvalidatableGraph.java
index 2437407..8abdae6 100644
--- a/src/main/java/com/google/devtools/build/skyframe/InvalidatableGraph.java
+++ b/src/main/java/com/google/devtools/build/skyframe/InvalidatableGraph.java
@@ -30,5 +30,5 @@
    * {@code keys}, {@code m.get(k).equals(e)} iff {@code get(k) == e} and {@code e != null}, and
    * {@code !m.containsKey(k)} iff {@code get(k) == null}.
    */
-  Map<SkyKey, ? extends ThinNodeEntry> getBatch(Iterable<SkyKey> keys);
+  Map<SkyKey, ? extends ThinNodeEntry> getBatchForInvalidation(Iterable<SkyKey> keys);
 }
diff --git a/src/main/java/com/google/devtools/build/skyframe/InvalidatingNodeVisitor.java b/src/main/java/com/google/devtools/build/skyframe/InvalidatingNodeVisitor.java
index 1fe90d1..c8dd68a 100644
--- a/src/main/java/com/google/devtools/build/skyframe/InvalidatingNodeVisitor.java
+++ b/src/main/java/com/google/devtools/build/skyframe/InvalidatingNodeVisitor.java
@@ -269,7 +269,7 @@
       for (SkyKey key : unvisitedKeys) {
         pendingVisitations.add(Pair.of(key, InvalidationType.DELETED));
       }
-      final Map<SkyKey, NodeEntry> entries = graph.getBatch(unvisitedKeys);
+      final Map<SkyKey, NodeEntry> entries = graph.getBatchForInvalidation(unvisitedKeys);
       for (final SkyKey key : unvisitedKeys) {
         executor.execute(
             new Runnable() {
@@ -305,7 +305,7 @@
                       entry.isDone()
                           ? entry.getDirectDeps()
                           : entry.getAllDirectDepsForIncompleteNode();
-                  Map<SkyKey, NodeEntry> depMap = graph.getBatch(directDeps);
+                  Map<SkyKey, NodeEntry> depMap = graph.getBatchForInvalidation(directDeps);
                   for (Map.Entry<SkyKey, NodeEntry> directDepEntry : depMap.entrySet()) {
                     NodeEntry dep = directDepEntry.getValue();
                     if (dep != null) {
@@ -432,7 +432,7 @@
           pendingVisitations.add(Pair.of(key, invalidationType));
         }
       }
-      final Map<SkyKey, ? extends ThinNodeEntry> entries = graph.getBatch(keysToGet);
+      final Map<SkyKey, ? extends ThinNodeEntry> entries = graph.getBatchForInvalidation(keysToGet);
       if (enqueueingKeyForExistenceCheck != null && entries.size() != keysToGet.size()) {
         Set<SkyKey> missingKeys = Sets.difference(ImmutableSet.copyOf(keysToGet), entries.keySet());
         throw new IllegalStateException(
diff --git a/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluator.java b/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluator.java
index 8cd502d..61c93cb 100644
--- a/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluator.java
+++ b/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluator.java
@@ -49,6 +49,7 @@
 import com.google.devtools.build.skyframe.MemoizingEvaluator.EmittedEventState;
 import com.google.devtools.build.skyframe.NodeEntry.DependencyState;
 import com.google.devtools.build.skyframe.NodeEntry.DirtyState;
+import com.google.devtools.build.skyframe.QueryableGraph.Reason;
 import com.google.devtools.build.skyframe.SkyFunctionException.ReifiedSkyFunctionException;
 
 import java.util.ArrayDeque;
@@ -222,8 +223,11 @@
     this.errorHandler = errorHandler;
   }
 
-  private Map<SkyKey, NodeEntry> getBatchValues(Iterable<SkyKey> keys) {
-    return graph.getBatchWithFieldHints(keys, NodeEntryField.VALUE_ONLY);
+  private Map<SkyKey, NodeEntry> getBatchValues(
+      SkyKey parent,
+      Reason reason,
+      Iterable<SkyKey> keys) {
+    return graph.getBatchWithFieldHints(parent, reason, keys, NodeEntryField.VALUE_ONLY);
   }
 
   /** Receives the events from the NestedSet and delegates to the reporter. */
@@ -312,8 +316,8 @@
         ValueVisitor visitor) {
       this.skyKey = skyKey;
       this.oldDeps = oldDeps;
-      this.directDeps = Collections.unmodifiableMap(
-          batchPrefetch(directDeps, oldDeps, /*assertDone=*/bubbleErrorInfo == null, skyKey));
+      this.directDeps = Collections.unmodifiableMap(batchPrefetch(
+          skyKey, directDeps, oldDeps, /*assertDone=*/bubbleErrorInfo == null, skyKey));
       this.bubbleErrorInfo = bubbleErrorInfo;
       this.visitor = visitor;
       Preconditions.checkState(
@@ -323,7 +327,7 @@
     }
 
     private Map<SkyKey, NodeEntry> batchPrefetch(
-        GroupedList<SkyKey> depKeys, Set<SkyKey> oldDeps, boolean assertDone,
+        SkyKey requestor, GroupedList<SkyKey> depKeys, Set<SkyKey> oldDeps, boolean assertDone,
         SkyKey keyForDebugging) {
       Iterable<SkyKey> depKeysAsIterable = Iterables.concat(depKeys);
       Iterable<SkyKey> keysToPrefetch = depKeysAsIterable;
@@ -332,7 +336,7 @@
         keysToPrefetchBuilder.addAll(depKeysAsIterable).addAll(oldDeps);
         keysToPrefetch = keysToPrefetchBuilder.build();
       }
-      Map<SkyKey, NodeEntry> batchMap = getBatchValues(keysToPrefetch);
+      Map<SkyKey, NodeEntry> batchMap = getBatchValues(requestor, Reason.PREFETCH, keysToPrefetch);
       if (PREFETCH_OLD_DEPS) {
         batchMap = ImmutableMap.copyOf(
             Maps.filterKeys(batchMap, Predicates.in(ImmutableSet.copyOf(depKeysAsIterable))));
@@ -357,7 +361,7 @@
       Preconditions.checkState(building, skyKey);
     }
 
-    private NestedSet<TaggedEvents> buildEvents(boolean missingChildren) {
+    private NestedSet<TaggedEvents> buildEvents(NodeEntry entry, boolean missingChildren) {
       // Aggregate the nested set of events from the direct deps, also adding the events from
       // building this value.
       NestedSetBuilder<TaggedEvents> eventBuilder = NestedSetBuilder.stableOrder();
@@ -367,10 +371,10 @@
       }
       if (storedEventFilter.storeEvents()) {
         // Only do the work of processing children if we're going to store events.
-        GroupedList<SkyKey> depKeys = graph.get(skyKey).getTemporaryDirectDeps();
+        GroupedList<SkyKey> depKeys = entry.getTemporaryDirectDeps();
         Map<SkyKey, SkyValue> deps =
             getValuesMaybeFromError(
-                Iterables.concat(depKeys), bubbleErrorInfo, depKeys.numElements());
+                null, Iterables.concat(depKeys), bubbleErrorInfo, depKeys.numElements());
         if (!missingChildren && depKeys.numElements() != deps.size()) {
           throw new IllegalStateException(
               "Missing keys for "
@@ -378,7 +382,7 @@
                   + ": "
                   + Sets.difference(depKeys.toSet(), deps.keySet())
                   + ", "
-                  + graph.get(skyKey));
+                  + entry);
         }
         for (SkyValue value : deps.values()) {
           if (value == NULL_MARKER) {
@@ -425,13 +429,14 @@
      * dependencies of this node <i>must</i> already have been registered, since this method may
      * register a dependence on the error transience node, which should always be the last dep.
      */
-    private void setError(ErrorInfo errorInfo, boolean isDirectlyTransient) {
+    private void setError(NodeEntry state, ErrorInfo errorInfo, boolean isDirectlyTransient) {
       Preconditions.checkState(value == null, "%s %s %s", skyKey, value, errorInfo);
       Preconditions.checkState(this.errorInfo == null,
           "%s %s %s", skyKey, this.errorInfo, errorInfo);
 
       if (isDirectlyTransient) {
-        NodeEntry errorTransienceNode = graph.get(ErrorTransienceValue.KEY);
+        NodeEntry errorTransienceNode =
+            graph.get(skyKey, Reason.RDEP_ADDITION, ErrorTransienceValue.KEY);
         DependencyState triState;
         if (oldDeps.contains(ErrorTransienceValue.KEY)) {
           triState = errorTransienceNode.checkIfDoneForDirtyReverseDep(skyKey);
@@ -440,8 +445,6 @@
         }
         Preconditions.checkState(triState == DependencyState.DONE,
             "%s %s %s", skyKey, triState, errorInfo);
-
-        final NodeEntry state = graph.get(skyKey);
         state.addTemporaryDirectDeps(
             GroupedListHelper.create(ImmutableList.of(ErrorTransienceValue.KEY)));
         state.signalDep();
@@ -451,6 +454,7 @@
     }
 
     private Map<SkyKey, SkyValue> getValuesMaybeFromError(
+        @Nullable SkyKey requestor,
         Iterable<SkyKey> keys,
         @Nullable Map<SkyKey, ValueWithMetadata> bubbleErrorInfo,
         int keySize) {
@@ -467,7 +471,8 @@
           missingKeys.add(key);
         }
       }
-      Map<SkyKey, NodeEntry> missingEntries = getBatchValues(missingKeys);
+      Map<SkyKey, NodeEntry> missingEntries =
+          getBatchValues(requestor, Reason.DEP_REQUESTED, missingKeys);
       for (SkyKey key : missingKeys) {
         builder.put(key, maybeGetValueFromError(key, missingEntries.get(key), bubbleErrorInfo));
       }
@@ -483,7 +488,7 @@
           "Error transience key cannot be in requested deps of %s",
           skyKey);
       Map<SkyKey, SkyValue> values =
-          getValuesMaybeFromError(depKeys, bubbleErrorInfo, depKeys.size());
+          getValuesMaybeFromError(skyKey, depKeys, bubbleErrorInfo, depKeys.size());
       for (Map.Entry<SkyKey, SkyValue> depEntry : values.entrySet()) {
         SkyKey depKey = depEntry.getKey();
         SkyValue depValue = depEntry.getValue();
@@ -495,9 +500,9 @@
                     + " was already in deps of "
                     + skyKey
                     + "( dep: "
-                    + graph.get(depKey)
+                    + graph.get(skyKey, Reason.OTHER, depKey)
                     + ", parent: "
-                    + graph.get(skyKey));
+                    + graph.get(null, Reason.OTHER, skyKey));
           }
           valuesMissing = true;
           addDep(depKey);
@@ -636,8 +641,7 @@
      * <p>The node entry is informed if the node's value and error are definitive via the flag
      * {@code completeValue}.
      */
-    void commit(boolean enqueueParents) {
-      NodeEntry primaryEntry = Preconditions.checkNotNull(graph.get(skyKey), skyKey);
+    void commit(NodeEntry primaryEntry, boolean enqueueParents) {
       // Construct the definitive error info, if there is one.
       finalizeErrorInfo();
 
@@ -648,7 +652,7 @@
       // (2) value == null && enqueueParents happens for values that are found to have errors
       // during a --keep_going build.
 
-      NestedSet<TaggedEvents> events = buildEvents(/*missingChildren=*/false);
+      NestedSet<TaggedEvents> events = buildEvents(primaryEntry, /*missingChildren=*/false);
       Version valueVersion;
       SkyValue valueWithMetadata;
       if (value == null) {
@@ -663,11 +667,12 @@
         // Remove the rdep on this entry for each of its old deps that is no longer a direct dep.
         Set<SkyKey> depsToRemove =
             Sets.difference(oldDeps, primaryEntry.getTemporaryDirectDeps().toSet());
-        for (NodeEntry oldDepEntry :
-            graph
-                .getBatchWithFieldHints(
-                    depsToRemove, EnumSet.of(NodeEntryField.INDIVIDUAL_REVERSE_DEPS))
-                .values()) {
+        Collection<NodeEntry> oldDepEntries = graph.getBatchWithFieldHints(
+            skyKey,
+            Reason.RDEP_REMOVAL,
+            depsToRemove,
+            EnumSet.of(NodeEntryField.INDIVIDUAL_REVERSE_DEPS)).values();
+        for (NodeEntry oldDepEntry : oldDepEntries) {
           oldDepEntry.removeReverseDep(skyKey);
         }
       }
@@ -694,7 +699,11 @@
         progressReceiver.evaluated(skyKey, new SkyValueSupplier(primaryEntry),
             valueVersion.equals(graphVersion) ? EvaluationState.BUILT : EvaluationState.CLEAN);
       }
-      signalValuesAndEnqueueIfReady(enqueueParents ? visitor : null, reverseDeps, valueVersion);
+      signalValuesAndEnqueueIfReady(
+          enqueueParents ? visitor : null,
+              skyKey,
+              reverseDeps,
+              valueVersion);
 
       visitor.notifyDone(skyKey);
       replayingNestedSetEventVisitor.visit(events);
@@ -878,7 +887,8 @@
     private boolean invalidatedByErrorTransience(Collection<SkyKey> depGroup, NodeEntry entry) {
       return depGroup.size() == 1
           && depGroup.contains(ErrorTransienceValue.KEY)
-          && !graph.get(ErrorTransienceValue.KEY).getVersion().atMost(entry.getVersion());
+          && !graph.get(
+              null, Reason.OTHER, ErrorTransienceValue.KEY).getVersion().atMost(entry.getVersion());
     }
 
     private DirtyOutcome maybeHandleDirtyNode(NodeEntry state) {
@@ -912,7 +922,8 @@
             // usual, but we can't, because then the ErrorTransienceValue would remain as a dep,
             // which would be incorrect if, for instance, the value re-evaluated to a non-error.
             state.forceRebuild();
-            graph.get(ErrorTransienceValue.KEY).removeReverseDep(skyKey);
+            graph.get(
+                skyKey, Reason.RDEP_REMOVAL, ErrorTransienceValue.KEY).removeReverseDep(skyKey);
             return DirtyOutcome.NEEDS_EVALUATION;
           }
           if (!keepGoing) {
@@ -925,6 +936,8 @@
             // a child error.
             Map<SkyKey, NodeEntry> entriesToCheck =
                 graph.getBatchWithFieldHints(
+                    skyKey,
+                    Reason.EVALUATION,
                     directDepsToCheck,
                     EnumSet.of(NodeEntryField.VALUE, NodeEntryField.INDIVIDUAL_REVERSE_DEPS));
             for (Map.Entry<SkyKey, NodeEntry> entry : entriesToCheck.entrySet()) {
@@ -960,8 +973,8 @@
 
           // TODO(bazel-team): If this signals the current node, consider falling through to the
           // VERIFIED_CLEAN case below directly, without scheduling a new Evaluate().
-          for (Map.Entry<SkyKey, NodeEntry> e
-              : graph.createIfAbsentBatch(directDepsToCheck).entrySet()) {
+          for (Map.Entry<SkyKey, NodeEntry> e : graph.createIfAbsentBatch(
+              skyKey, Reason.ENQUEUING_CHILD, directDepsToCheck).entrySet()) {
             SkyKey directDep = e.getKey();
             NodeEntry directDepEntry = e.getValue();
             enqueueChild(skyKey, state, directDep, directDepEntry, /*depAlreadyExists=*/ true);
@@ -982,7 +995,7 @@
             }
             throw SchedulerException.ofError(state.getErrorInfo(), skyKey);
           }
-          signalValuesAndEnqueueIfReady(visitor, reverseDeps, state.getVersion());
+          signalValuesAndEnqueueIfReady(visitor, skyKey, reverseDeps, state.getVersion());
           return DirtyOutcome.ALREADY_PROCESSED;
         case NEEDS_REBUILDING:
           maybeMarkRebuilding(state);
@@ -996,7 +1009,9 @@
 
     @Override
     public void run() {
-      NodeEntry state = Preconditions.checkNotNull(graph.get(skyKey), skyKey);
+      NodeEntry state = Preconditions.checkNotNull(
+          graph.get(null, Reason.EVALUATION, skyKey),
+          skyKey);
       Preconditions.checkState(state.isReady(), "%s %s", skyKey, state);
       if (maybeHandleDirtyNode(state) == DirtyOutcome.ALREADY_PROCESSED) {
         return;
@@ -1036,7 +1051,8 @@
             }
           }
 
-          Map<SkyKey, NodeEntry> newlyRequestedDeps = getBatchValues(env.newlyRequestedDeps);
+          Map<SkyKey, NodeEntry> newlyRequestedDeps =
+              getBatchValues(skyKey, Reason.RDEP_ADDITION, env.newlyRequestedDeps);
           boolean isTransitivelyTransient = reifiedBuilderException.isTransient();
           for (NodeEntry depEntry
               : Iterables.concat(env.directDeps.values(), newlyRequestedDeps.values())) {
@@ -1051,8 +1067,11 @@
           ErrorInfo errorInfo = ErrorInfo.fromException(reifiedBuilderException,
               isTransitivelyTransient);
           registerNewlyDiscoveredDepsForDoneEntry(skyKey, state, newlyRequestedDeps, oldDeps, env);
-          env.setError(errorInfo, /*isDirectlyTransient=*/ reifiedBuilderException.isTransient());
-          env.commit(/*enqueueParents=*/keepGoing);
+          env.setError(
+              state,
+              errorInfo,
+              /*isDirectlyTransient=*/ reifiedBuilderException.isTransient());
+          env.commit(state, /*enqueueParents=*/keepGoing);
           if (!shouldFailFast) {
             return;
           }
@@ -1093,10 +1112,13 @@
             skyKey,
             state,
             graph.getBatchWithFieldHints(
-                env.newlyRequestedDeps, EnumSet.of(NodeEntryField.INDIVIDUAL_REVERSE_DEPS)),
+                skyKey,
+                Reason.RDEP_ADDITION,
+                env.newlyRequestedDeps,
+                EnumSet.of(NodeEntryField.INDIVIDUAL_REVERSE_DEPS)),
             oldDeps,
             env);
-        env.commit(/*enqueueParents=*/true);
+        env.commit(state, /*enqueueParents=*/true);
         return;
       }
 
@@ -1107,8 +1129,12 @@
         // 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).
         SkyKey childErrorKey = env.getDepErrorKey();
-        NodeEntry childErrorEntry = Preconditions.checkNotNull(graph.get(childErrorKey),
-            "skyKey: %s, state: %s childErrorKey: %s", skyKey, state, childErrorKey);
+        NodeEntry childErrorEntry = Preconditions.checkNotNull(
+            graph.get(skyKey, Reason.OTHER, childErrorKey),
+            "skyKey: %s, state: %s childErrorKey: %s",
+            skyKey,
+            state,
+            childErrorKey);
         Preconditions.checkState(
             !state.getTemporaryDirectDeps().expensiveContains(childErrorKey),
             "Done error was already known: %s %s %s %s",
@@ -1162,11 +1188,12 @@
         // If the child error was catastrophic, committing this parent to the graph is not
         // necessary, but since we don't do error bubbling in catastrophes, it doesn't violate any
         // invariants either.
-        env.commit(/*enqueueParents=*/ true);
+        env.commit(state, /*enqueueParents=*/ true);
         return;
       }
 
-      for (Map.Entry<SkyKey, NodeEntry> e : graph.createIfAbsentBatch(newDirectDeps).entrySet()) {
+      for (Map.Entry<SkyKey, NodeEntry> e
+          : graph.createIfAbsentBatch(skyKey, Reason.ENQUEUING_CHILD, newDirectDeps).entrySet()) {
         SkyKey newDirectDep = e.getKey();
         NodeEntry newDirectDepEntry = e.getValue();
         enqueueChild(
@@ -1209,11 +1236,12 @@
    * cycles).
    */
   private void signalValuesAndEnqueueIfReady(
-      @Nullable ValueVisitor visitor, Iterable<SkyKey> keys, Version version) {
+      @Nullable ValueVisitor visitor, SkyKey skyKey, Iterable<SkyKey> keys, Version version) {
     // No fields of the entry are needed here, since we're just enqueuing for evaluation, but more
     // importantly, these hints are not respected for not-done nodes. If they are, we may need to
     // alter this hint.
-    Map<SkyKey, NodeEntry> batch = graph.getBatchWithFieldHints(keys, NodeEntryField.NO_FIELDS);
+    Map<SkyKey, NodeEntry> batch =
+        graph.getBatchWithFieldHints(skyKey, Reason.SIGNAL_DEP, keys, NodeEntryField.NO_FIELDS);
     if (visitor != null) {
       for (SkyKey key : keys) {
         NodeEntry entry = Preconditions.checkNotNull(batch.get(key), key);
@@ -1236,8 +1264,8 @@
    * If child is not done, removes {@param inProgressParent} from {@param child}'s reverse deps.
    * Returns whether child should be removed from inProgressParent's entry's direct deps.
    */
-  private boolean removeIncompleteChild(SkyKey inProgressParent, SkyKey child) {
-    NodeEntry childEntry = graph.get(child);
+  private boolean removeIncompleteChildForCycle(SkyKey inProgressParent, SkyKey child) {
+    NodeEntry childEntry = graph.get(inProgressParent, Reason.CYCLE_CHECKING, child);
     if (!isDoneForBuild(childEntry)) {
       childEntry.removeInProgressReverseDep(inProgressParent);
       return true;
@@ -1311,7 +1339,7 @@
     // directly without launching the heavy machinery, spawning threads, etc.
     // Inform progressReceiver that these nodes are done to be consistent with the main code path.
     boolean allAreDone = true;
-    Map<SkyKey, NodeEntry> batch = getBatchValues(skyKeySet);
+    Map<SkyKey, NodeEntry> batch = getBatchValues(null, Reason.EVALUATION, skyKeySet);
     for (SkyKey key : skyKeySet) {
       if (!isDoneForBuild(batch.get(key))) {
         allAreDone = false;
@@ -1330,7 +1358,7 @@
     if (!keepGoing) {
       Set<SkyKey> cachedErrorKeys = new HashSet<>();
       for (SkyKey skyKey : skyKeySet) {
-        NodeEntry entry = graph.get(skyKey);
+        NodeEntry entry = graph.get(null, Reason.EVALUATION, skyKey);
         if (entry == null) {
           continue;
         }
@@ -1375,7 +1403,8 @@
     // in the graph, by the time that it is needed. Creating it on demand in a parallel context sets
     // up a race condition, because there is no way to atomically create a node and set its value.
     NodeEntry errorTransienceEntry = Iterables.getOnlyElement(
-        graph.createIfAbsentBatch(ImmutableList.of(ErrorTransienceValue.KEY)).values());
+        graph.createIfAbsentBatch(
+            null, Reason.EVALUATION, ImmutableList.of(ErrorTransienceValue.KEY)).values());
     if (!errorTransienceEntry.isDone()) {
       injectValues(
           ImmutableMap.of(ErrorTransienceValue.KEY, (SkyValue) ErrorTransienceValue.INSTANCE),
@@ -1383,7 +1412,8 @@
           graph,
           dirtyKeyTracker);
     }
-    for (Map.Entry<SkyKey, NodeEntry> e : graph.createIfAbsentBatch(skyKeys).entrySet()) {
+    for (Map.Entry<SkyKey, NodeEntry> e
+        : graph.createIfAbsentBatch(null, Reason.EVALUATION, skyKeys).entrySet()) {
       SkyKey skyKey = e.getKey();
       NodeEntry entry = e.getValue();
       // This must be equivalent to the code in enqueueChild above, in order to be thread-safe.
@@ -1447,7 +1477,7 @@
             ImmutableMap.of(
                 errorKey,
                 ValueWithMetadata.wrapWithMetadata(
-                    graph.get(errorKey).getValueMaybeWithMetadata()));
+                    graph.get(null, Reason.ERROR_BUBBLING, errorKey).getValueMaybeWithMetadata()));
       }
     }
     Preconditions.checkState(visitor.getCrashes().isEmpty(), visitor.getCrashes());
@@ -1494,7 +1524,9 @@
     Map<SkyKey, ValueWithMetadata> bubbleErrorInfo = new HashMap<>();
     boolean externalInterrupt = false;
     while (true) {
-      NodeEntry errorEntry = Preconditions.checkNotNull(graph.get(errorKey), errorKey);
+      NodeEntry errorEntry = Preconditions.checkNotNull(
+          graph.get(null, Reason.ERROR_BUBBLING, errorKey),
+          errorKey);
       Iterable<SkyKey> reverseDeps = errorEntry.isDone()
           ? errorEntry.getReverseDeps()
           : errorEntry.getInProgressReverseDeps();
@@ -1511,8 +1543,11 @@
           // We are in a cycle. Don't try to bubble anything up -- cycle detection will kick in.
           return null;
         }
-        NodeEntry bubbleParentEntry = Preconditions.checkNotNull(graph.get(bubbleParent),
-            "parent %s of %s not in graph", bubbleParent, errorKey);
+        NodeEntry bubbleParentEntry = Preconditions.checkNotNull(
+            graph.get(errorKey, Reason.ERROR_BUBBLING, bubbleParent),
+            "parent %s of %s not in graph",
+            bubbleParent,
+            errorKey);
         // Might be the parent that requested the error.
         if (bubbleParentEntry.isDone()) {
           // This parent is cached from a previous evaluate call. We shouldn't bubble up to it
@@ -1604,7 +1639,7 @@
               /*isTransitivelyTransient=*/ false);
           bubbleErrorInfo.put(errorKey,
               ValueWithMetadata.error(ErrorInfo.fromChildErrors(errorKey, ImmutableSet.of(error)),
-                  env.buildEvents(/*missingChildren=*/true)));
+                  env.buildEvents(parentEntry, /*missingChildren=*/true)));
           continue;
         }
       } finally {
@@ -1614,7 +1649,7 @@
       // Builder didn't throw an exception, so just propagate this one up.
       bubbleErrorInfo.put(errorKey,
           ValueWithMetadata.error(ErrorInfo.fromChildErrors(errorKey, ImmutableSet.of(error)),
-              env.buildEvents(/*missingChildren=*/true)));
+              env.buildEvents(parentEntry, /*missingChildren=*/true)));
     }
 
     // Reset the interrupt bit if there was an interrupt from outside this evaluator interrupt.
@@ -1649,7 +1684,10 @@
     EvaluationResult.Builder<T> result = EvaluationResult.builder();
     List<SkyKey> cycleRoots = new ArrayList<>();
     for (SkyKey skyKey : skyKeys) {
-      SkyValue unwrappedValue = maybeGetValueFromError(skyKey, graph.get(skyKey), bubbleErrorInfo);
+      SkyValue unwrappedValue = maybeGetValueFromError(
+          skyKey,
+          graph.get(null, Reason.EVALUATION, skyKey),
+          bubbleErrorInfo);
       ValueWithMetadata valueWithMetadata =
           unwrappedValue == NULL_MARKER ? null : ValueWithMetadata.wrapWithMetadata(unwrappedValue);
       // Cycle checking: if there is a cycle, evaluation cannot progress, therefore,
@@ -1782,7 +1820,7 @@
         // A marker node means we are done with all children of a node. Since all nodes have
         // errors, we must have found errors in the children when that happens.
         key = graphPath.remove(graphPath.size() - 1);
-        entry = Preconditions.checkNotNull(graph.get(key), key);
+        entry = Preconditions.checkNotNull(graph.get(null, Reason.CYCLE_CHECKING, key), key);
         pathSet.remove(key);
         // Skip this node if it was first/last node of a cycle, and so has already been processed.
         if (entry.isDone()) {
@@ -1807,7 +1845,7 @@
         maybeMarkRebuilding(entry);
         GroupedList<SkyKey> directDeps = entry.getTemporaryDirectDeps();
         // Find out which children have errors. Similar logic to that in Evaluate#run().
-        List<ErrorInfo> errorDeps = getChildrenErrorsForCycle(Iterables.concat(directDeps));
+        List<ErrorInfo> errorDeps = getChildrenErrorsForCycle(key, Iterables.concat(directDeps));
         Preconditions.checkState(!errorDeps.isEmpty(),
             "Value %s was not successfully evaluated, but had no child errors. ValueEntry: %s", key,
             entry);
@@ -1817,10 +1855,11 @@
                 directDeps,
                 Sets.difference(entry.getAllRemainingDirtyDirectDeps(), removedDeps),
                 visitor);
-        env.setError(ErrorInfo.fromChildErrors(key, errorDeps), /*isDirectlyTransient=*/false);
-        env.commit(/*enqueueParents=*/false);
+        env.setError(
+            entry, ErrorInfo.fromChildErrors(key, errorDeps), /*isDirectlyTransient=*/false);
+        env.commit(entry, /*enqueueParents=*/false);
       } else {
-        entry = graph.get(key);
+        entry = graph.get(null, Reason.CYCLE_CHECKING, key);
       }
 
       Preconditions.checkNotNull(entry, key);
@@ -1870,14 +1909,14 @@
           // Construct error info for this node. Get errors from children, which are all done
           // except possibly for the cycleChild.
           List<ErrorInfo> allErrors =
-              getChildrenErrors(
+              getChildrenErrorsForCycleChecking(
                   Iterables.concat(entry.getTemporaryDirectDeps()),
                   /*unfinishedChild=*/ cycleChild);
           CycleInfo cycleInfo = new CycleInfo(cycle);
           // Add in this cycle.
           allErrors.add(ErrorInfo.fromCycle(cycleInfo));
-          env.setError(ErrorInfo.fromChildErrors(key, allErrors), /*isTransient=*/false);
-          env.commit(/*enqueueParents=*/false);
+          env.setError(entry, ErrorInfo.fromChildErrors(key, allErrors), /*isTransient=*/false);
+          env.commit(entry, /*enqueueParents=*/false);
           continue;
         } else {
           // We need to return right away in the noKeepGoing case, so construct the cycle (with the
@@ -1898,8 +1937,8 @@
       // out.
       // TODO(janakr): If graph implementations start using these hints for not-done nodes, we may
       // have to change this.
-      Map<SkyKey, NodeEntry> childrenNodes =
-          graph.getBatchWithFieldHints(children, NodeEntryField.NO_FIELDS);
+      Map<SkyKey, NodeEntry> childrenNodes = graph.getBatchWithFieldHints(
+          key, Reason.CYCLE_CHECKING, children, NodeEntryField.NO_FIELDS);
       Preconditions.checkState(childrenNodes.size() == Iterables.size(children), childrenNodes);
       children = Maps.filterValues(childrenNodes, new Predicate<NodeEntry>() {
         @Override
@@ -1917,7 +1956,7 @@
         toVisit.push(nextValue);
       }
     }
-    return keepGoing ? getAndCheckDone(root).getErrorInfo() : null;
+    return keepGoing ? getAndCheckDoneForCycle(root).getErrorInfo() : null;
   }
 
   /**
@@ -1934,10 +1973,10 @@
    * @param children child nodes to query for errors.
    * @return List of ErrorInfos from all children that had errors.
    */
-  private List<ErrorInfo> getChildrenErrorsForCycle(Iterable<SkyKey> children) {
+  private List<ErrorInfo> getChildrenErrorsForCycle(SkyKey parent, Iterable<SkyKey> children) {
     List<ErrorInfo> allErrors = new ArrayList<>();
     boolean foundCycle = false;
-    for (NodeEntry childNode : getAndCheckDoneBatch(children).values()) {
+    for (NodeEntry childNode : getAndCheckDoneBatchForCycle(parent, children).values()) {
       ErrorInfo errorInfo = childNode.getErrorInfo();
       if (errorInfo != null) {
         foundCycle |= !Iterables.isEmpty(errorInfo.getCycleInfo());
@@ -1955,9 +1994,12 @@
    * @param unfinishedChild child which is allowed to not be done.
    * @return List of ErrorInfos from all children that had errors.
    */
-  private List<ErrorInfo> getChildrenErrors(Iterable<SkyKey> children, SkyKey unfinishedChild) {
+  private List<ErrorInfo> getChildrenErrorsForCycleChecking(
+      Iterable<SkyKey> children, SkyKey unfinishedChild) {
     List<ErrorInfo> allErrors = new ArrayList<>();
-    for (Entry<SkyKey, NodeEntry> childMapEntry : getBatchValues(children).entrySet()) {
+    Set<Entry<SkyKey, NodeEntry>> childEntries =
+        getBatchValues(null, Reason.CYCLE_CHECKING, children).entrySet();
+    for (Entry<SkyKey, NodeEntry> childMapEntry : childEntries) {
       SkyKey childKey = childMapEntry.getKey();
       NodeEntry childNodeEntry = childMapEntry.getValue();
       ErrorInfo errorInfo = getErrorMaybe(childKey, childNodeEntry,
@@ -2041,7 +2083,7 @@
       SkyKey key, NodeEntry entry, Iterable<SkyKey> children) {
     Set<SkyKey> unfinishedDeps = new HashSet<>();
     for (SkyKey child : children) {
-      if (removeIncompleteChild(key, child)) {
+      if (removeIncompleteChildForCycle(key, child)) {
         unfinishedDeps.add(child);
       }
     }
@@ -2049,18 +2091,19 @@
     return unfinishedDeps;
   }
 
-  private NodeEntry getAndCheckDone(SkyKey key) {
-    return checkDone(key, graph.get(key));
-  }
-
   private static NodeEntry checkDone(SkyKey key, NodeEntry entry) {
     Preconditions.checkNotNull(entry, key);
     Preconditions.checkState(entry.isDone(), "%s %s", key, entry);
     return entry;
   }
 
-  private Map<SkyKey, NodeEntry> getAndCheckDoneBatch(Iterable<SkyKey> keys) {
-    Map<SkyKey, NodeEntry> nodes = getBatchValues(keys);
+  private NodeEntry getAndCheckDoneForCycle(SkyKey key) {
+    return checkDone(key, graph.get(null, Reason.CYCLE_CHECKING, key));
+  }
+
+  private Map<SkyKey, NodeEntry> getAndCheckDoneBatchForCycle(
+      SkyKey parent, Iterable<SkyKey> keys) {
+    Map<SkyKey, NodeEntry> nodes = getBatchValues(parent, Reason.CYCLE_CHECKING, keys);
     for (Map.Entry<SkyKey, NodeEntry> nodeEntryMapEntry : nodes.entrySet()) {
       checkDone(nodeEntryMapEntry.getKey(), nodeEntryMapEntry.getValue());
     }
@@ -2096,7 +2139,8 @@
       Version version,
       EvaluableGraph graph,
       DirtyKeyTracker dirtyKeyTracker) {
-    Map<SkyKey, NodeEntry> prevNodeEntries = graph.createIfAbsentBatch(injectionMap.keySet());
+    Map<SkyKey, NodeEntry> prevNodeEntries =
+        graph.createIfAbsentBatch(null, Reason.OTHER, injectionMap.keySet());
     for (Map.Entry<SkyKey, SkyValue> injectionEntry : injectionMap.entrySet()) {
       SkyKey key = injectionEntry.getKey();
       SkyValue value = injectionEntry.getValue();
diff --git a/src/main/java/com/google/devtools/build/skyframe/QueryableGraph.java b/src/main/java/com/google/devtools/build/skyframe/QueryableGraph.java
index 2703802..75ce05c 100644
--- a/src/main/java/com/google/devtools/build/skyframe/QueryableGraph.java
+++ b/src/main/java/com/google/devtools/build/skyframe/QueryableGraph.java
@@ -23,9 +23,15 @@
 /** A graph that exposes its entries and structure, for use by classes that must traverse it. */
 @ThreadSafe
 public interface QueryableGraph {
-  /** Returns the node with the given name, or {@code null} if the node does not exist. */
+  /**
+   * Returns the node with the given {@code key}, or {@code null} if the node does not exist.
+   *
+   * @param requestor if non-{@code null}, the node on behalf of which {@code key} is being
+   *     requested.
+   * @param reason the reason the node is being requested.
+   */
   @Nullable
-  NodeEntry get(SkyKey key);
+  NodeEntry get(@Nullable SkyKey requestor, Reason reason, SkyKey key);
 
   /**
    * Fetches all the given nodes. Returns a map {@code m} such that, for all {@code k} in {@code
@@ -34,7 +40,65 @@
    * QueryableGraph implementation that allows it to possibly construct certain fields of the
    * returned node entries more lazily. Hints may only be applied to nodes in a certain state, like
    * done nodes.
+   * 
+   * @param requestor if non-{@code null}, the node on behalf of which the given {@code keys} are
+   *     being requested.
+   * @param reason the reason the nodes are being requested.
    */
   Map<SkyKey, NodeEntry> getBatchWithFieldHints(
-      Iterable<SkyKey> keys, EnumSet<NodeEntryField> fields);
+      @Nullable SkyKey requestor,
+      Reason reason,
+      Iterable<SkyKey> keys,
+      EnumSet<NodeEntryField> fields);
+
+  /**
+   * The reason that a node is being looked up in the Skyframe graph.
+   *
+   * <p>Alternate graph implementations may wish to make use of this information.
+   */
+  enum Reason {
+    /**
+     * The node is being looked up as part of the prefetch step before evaluation of a SkyFunction.
+     */
+    PREFETCH,
+
+    /**
+     * The node is being fetched because it is about to be evaluated or it has already been
+     * evaluated, but *not* because it was just requested during evaluation of a SkyFunction (see
+     * DEP_REQUESTED).
+     */
+    EVALUATION,
+
+    /** The node is being looked up because it was requested during evaluation of a SkyFunction. */
+    DEP_REQUESTED,
+
+    /** The node is being looked up during the invalidation phase of Skyframe evaluation. */
+    INVALIDATION,
+
+    /** The node is being looked up during the cycle checking phase of Skyframe evaluation. */
+    CYCLE_CHECKING,
+
+    /** The node is being looked up so that an rdep can be added to it. */
+    RDEP_ADDITION,
+
+    /** The node is being looked up so that an rdep can be removed from it. */
+    RDEP_REMOVAL,
+
+    /** The node is being looked up so it can be enqueued for evaluation or change pruning. */
+    ENQUEUING_CHILD,
+
+    /**
+     * The node is being looked up so that it can be signaled that a dependency is now complete.
+     */
+    SIGNAL_DEP,
+
+    /**
+     * The node is being looking up as part of the error bubbling phase of fail-fast Skyframe
+     * evaluation.
+     */
+    ERROR_BUBBLING,
+
+    /** Some other reason than one of the above. */
+    OTHER,
+  }
 }
diff --git a/src/main/java/com/google/devtools/build/skyframe/QueryableGraphBackedSkyFunctionEnvironment.java b/src/main/java/com/google/devtools/build/skyframe/QueryableGraphBackedSkyFunctionEnvironment.java
index ed38be3..6aaadcd 100644
--- a/src/main/java/com/google/devtools/build/skyframe/QueryableGraphBackedSkyFunctionEnvironment.java
+++ b/src/main/java/com/google/devtools/build/skyframe/QueryableGraphBackedSkyFunctionEnvironment.java
@@ -19,7 +19,7 @@
 import com.google.common.collect.Sets;
 import com.google.devtools.build.lib.events.EventHandler;
 import com.google.devtools.build.lib.util.Preconditions;
-
+import com.google.devtools.build.skyframe.QueryableGraph.Reason;
 import java.util.HashMap;
 import java.util.Map;
 import java.util.Set;
@@ -70,8 +70,8 @@
 
   @Override
   protected Map<SkyKey, ValueOrUntypedException> getValueOrUntypedExceptions(Set<SkyKey> depKeys) {
-    Map<SkyKey, NodeEntry> resultMap =
-        queryableGraph.getBatchWithFieldHints(depKeys, NodeEntryField.VALUE_ONLY);
+    Map<SkyKey, NodeEntry> resultMap = queryableGraph.getBatchWithFieldHints(
+        null, Reason.DEP_REQUESTED, depKeys, NodeEntryField.VALUE_ONLY);
     Map<SkyKey, NodeEntry> resultWithMissingKeys = new HashMap<>(resultMap);
     for (SkyKey missingDep : Sets.difference(depKeys, resultMap.keySet())) {
       resultWithMissingKeys.put(missingDep, null);
diff --git a/src/test/java/com/google/devtools/build/skyframe/DeterministicHelper.java b/src/test/java/com/google/devtools/build/skyframe/DeterministicHelper.java
index 50bd380..fe7c76f 100644
--- a/src/test/java/com/google/devtools/build/skyframe/DeterministicHelper.java
+++ b/src/test/java/com/google/devtools/build/skyframe/DeterministicHelper.java
@@ -14,7 +14,6 @@
 package com.google.devtools.build.skyframe;
 
 import com.google.common.collect.Iterables;
-
 import java.util.Collection;
 import java.util.Comparator;
 import java.util.EnumSet;
@@ -91,8 +90,8 @@
     }
 
     @Override
-    public Map<SkyKey, NodeEntry> getBatch(Iterable<SkyKey> keys) {
-      return makeDeterministic(super.getBatch(keys));
+    public Map<SkyKey, NodeEntry> getBatchForInvalidation(Iterable<SkyKey> keys) {
+      return makeDeterministic(super.getBatchForInvalidation(keys));
     }
   }
 
@@ -111,14 +110,18 @@
     }
 
     @Override
-    public Map<SkyKey, NodeEntry> createIfAbsentBatch(Iterable<SkyKey> keys) {
-      return makeDeterministic(super.createIfAbsentBatch(keys));
+    public Map<SkyKey, NodeEntry> createIfAbsentBatch(
+        @Nullable SkyKey requestor, Reason reason, Iterable<SkyKey> keys) {
+      return makeDeterministic(super.createIfAbsentBatch(requestor, reason, keys));
     }
 
     @Override
     public Map<SkyKey, NodeEntry> getBatchWithFieldHints(
-        Iterable<SkyKey> keys, EnumSet<NodeEntryField> fields) {
-      return makeDeterministic(super.getBatchWithFieldHints(keys, fields));
+        @Nullable SkyKey requestor,
+        Reason reason,
+        Iterable<SkyKey> keys,
+        EnumSet<NodeEntryField> fields) {
+      return makeDeterministic(super.getBatchWithFieldHints(requestor, reason, keys, fields));
     }
   }
 
diff --git a/src/test/java/com/google/devtools/build/skyframe/DeterministicInMemoryGraph.java b/src/test/java/com/google/devtools/build/skyframe/DeterministicInMemoryGraph.java
index bb61d0f..0cbc91c 100644
--- a/src/test/java/com/google/devtools/build/skyframe/DeterministicInMemoryGraph.java
+++ b/src/test/java/com/google/devtools/build/skyframe/DeterministicInMemoryGraph.java
@@ -27,8 +27,8 @@
   }
 
   @Override
-  public Map<SkyKey, NodeEntry> getBatch(Iterable<SkyKey> keys) {
-    return getBatchWithFieldHints(keys, NodeEntryField.ALL_FIELDS);
+  public Map<SkyKey, NodeEntry> getBatchForInvalidation(Iterable<SkyKey> keys) {
+    return getBatchWithFieldHints(null, Reason.INVALIDATION, keys, NodeEntryField.ALL_FIELDS);
   }
 
   @Override
diff --git a/src/test/java/com/google/devtools/build/skyframe/EagerInvalidatorTest.java b/src/test/java/com/google/devtools/build/skyframe/EagerInvalidatorTest.java
index dbc418f..fb3058c1 100644
--- a/src/test/java/com/google/devtools/build/skyframe/EagerInvalidatorTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/EagerInvalidatorTest.java
@@ -39,7 +39,7 @@
 import com.google.devtools.build.skyframe.InvalidatingNodeVisitor.DirtyingNodeVisitor;
 import com.google.devtools.build.skyframe.InvalidatingNodeVisitor.InvalidationState;
 import com.google.devtools.build.skyframe.InvalidatingNodeVisitor.InvalidationType;
-
+import com.google.devtools.build.skyframe.QueryableGraph.Reason;
 import org.junit.After;
 import org.junit.Before;
 import org.junit.Test;
@@ -93,7 +93,7 @@
   boolean gcExpected() { throw new UnsupportedOperationException(); }
 
   private boolean isInvalidated(SkyKey key) {
-    NodeEntry entry = graph.get(key);
+    NodeEntry entry = graph.get(null, Reason.OTHER, key);
     if (gcExpected()) {
       return entry == null;
     } else {
@@ -102,7 +102,7 @@
   }
 
   private void assertChanged(SkyKey key) {
-    NodeEntry entry = graph.get(key);
+    NodeEntry entry = graph.get(null, Reason.OTHER, key);
     if (gcExpected()) {
       assertNull(entry);
     } else {
@@ -111,7 +111,7 @@
   }
 
   private void assertDirtyAndNotChanged(SkyKey key) {
-    NodeEntry entry = graph.get(key);
+    NodeEntry entry = graph.get(null, Reason.OTHER, key);
     if (gcExpected()) {
       assertNull(entry);
     } else {
@@ -344,10 +344,12 @@
         .setComputedValue(CONCATENATE);
     eval(false, skyKey("ab_c"), skyKey("bc"));
 
-    assertThat(graph.get(skyKey("a")).getReverseDeps()).containsExactly(skyKey("ab"));
-    assertThat(graph.get(skyKey("b")).getReverseDeps()).containsExactly(skyKey("ab"), skyKey("bc"));
-    assertThat(graph.get(skyKey("c")).getReverseDeps()).containsExactly(skyKey("ab_c"),
-        skyKey("bc"));
+    assertThat(graph.get(null, Reason.OTHER, skyKey("a"))
+        .getReverseDeps()).containsExactly(skyKey("ab"));
+    assertThat(graph.get(null, Reason.OTHER, skyKey("b"))
+        .getReverseDeps()).containsExactly(skyKey("ab"), skyKey("bc"));
+    assertThat(graph.get(null, Reason.OTHER, skyKey("c"))
+        .getReverseDeps()).containsExactly(skyKey("ab_c"), skyKey("bc"));
 
     invalidateWithoutError(null, skyKey("ab"));
     eval(false);
@@ -361,15 +363,18 @@
     if (reverseDepsPresent()) {
       reverseDeps.add(skyKey("ab"));
     }
-    assertThat(graph.get(skyKey("a")).getReverseDeps()).containsExactlyElementsIn(reverseDeps);
+    assertThat(graph.get(null, Reason.OTHER, skyKey("a"))
+        .getReverseDeps()).containsExactlyElementsIn(reverseDeps);
     reverseDeps.add(skyKey("bc"));
-    assertThat(graph.get(skyKey("b")).getReverseDeps()).containsExactlyElementsIn(reverseDeps);
+    assertThat(graph.get(null, Reason.OTHER, skyKey("b"))
+        .getReverseDeps()).containsExactlyElementsIn(reverseDeps);
     reverseDeps.clear();
     if (reverseDepsPresent()) {
       reverseDeps.add(skyKey("ab_c"));
     }
     reverseDeps.add(skyKey("bc"));
-    assertThat(graph.get(skyKey("c")).getReverseDeps()).containsExactlyElementsIn(reverseDeps);
+    assertThat(graph.get(null, Reason.OTHER, skyKey("c"))
+        .getReverseDeps()).containsExactlyElementsIn(reverseDeps);
   }
 
   @Test
@@ -438,7 +443,7 @@
     assertFalse(state.isEmpty());
     final Set<SkyKey> invalidated = Sets.newConcurrentHashSet();
     assertFalse(isInvalidated(parent));
-    assertNotNull(graph.get(parent).getValue());
+    assertNotNull(graph.get(null, Reason.OTHER, parent).getValue());
     receiver = new EvaluationProgressReceiver() {
       @Override
       public void invalidated(SkyKey skyKey, InvalidationState state) {
diff --git a/src/test/java/com/google/devtools/build/skyframe/GraphConcurrencyTest.java b/src/test/java/com/google/devtools/build/skyframe/GraphConcurrencyTest.java
index 73e42ea..df6f99c 100644
--- a/src/test/java/com/google/devtools/build/skyframe/GraphConcurrencyTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/GraphConcurrencyTest.java
@@ -30,7 +30,7 @@
 import com.google.devtools.build.lib.util.Preconditions;
 import com.google.devtools.build.skyframe.GraphTester.StringValue;
 import com.google.devtools.build.skyframe.NodeEntry.DependencyState;
-
+import com.google.devtools.build.skyframe.QueryableGraph.Reason;
 import org.junit.Before;
 import org.junit.Test;
 
@@ -77,7 +77,7 @@
 
   @Test
   public void createIfAbsentBatchSanity() {
-    graph.createIfAbsentBatch(ImmutableList.of(key("cat"), key("dog")));
+    graph.createIfAbsentBatch(null, Reason.OTHER, ImmutableList.of(key("cat"), key("dog")));
   }
 
   @Test
@@ -91,11 +91,11 @@
                   new Runnable() {
                     @Override
                     public void run() {
-                      graph.get(key);
+                      graph.get(null, Reason.OTHER, key);
                     }
                   }));
       t.start();
-      assertThat(graph.createIfAbsentBatch(ImmutableList.of(key))).isNotEmpty();
+      assertThat(graph.createIfAbsentBatch(null, Reason.OTHER, ImmutableList.of(key))).isNotEmpty();
       graph.remove(key);
     }
   }
@@ -111,7 +111,7 @@
           public void run() {
             TrackingAwaiter.INSTANCE.awaitLatchAndTrackExceptions(
                 startThreads, "threads not started");
-            graph.createIfAbsentBatch(ImmutableList.of(key));
+            graph.createIfAbsentBatch(null, Reason.OTHER, ImmutableList.of(key));
           }
         };
     Runnable noCreateRunnable =
@@ -120,7 +120,7 @@
           public void run() {
             TrackingAwaiter.INSTANCE.awaitLatchAndTrackExceptions(
                 startThreads, "threads not started");
-            graph.get(key);
+            graph.get(null, Reason.OTHER, key);
           }
         };
     List<Thread> threads = new ArrayList<>(2 * numThreads);
@@ -144,7 +144,7 @@
   public void testAddRemoveRdeps() throws Exception {
     SkyKey key = key("foo");
     final NodeEntry entry = Iterables.getOnlyElement(
-        graph.createIfAbsentBatch(ImmutableList.of(key)).values());
+        graph.createIfAbsentBatch(null, Reason.OTHER, ImmutableList.of(key)).values());
     // These numbers are arbitrary.
     int numThreads = 50;
     int numKeys = numThreads;
@@ -169,7 +169,7 @@
     for (int i = 0; i < numKeys; i++) {
       rdepKeys.add(key("rdep" + i));
     }
-    graph.createIfAbsentBatch(rdepKeys);
+    graph.createIfAbsentBatch(null, Reason.OTHER, rdepKeys);
     for (int i = 0; i < numKeys; i++) {
       final int j = i;
       Runnable r =
@@ -200,18 +200,18 @@
     waitForSetValue.countDown();
     wrapper.waitForTasksAndMaybeThrow();
     assertFalse(ExecutorUtil.interruptibleShutdown(pool));
-    assertEquals(new StringValue("foo1"), graph.get(key).getValue());
-    assertEquals(numKeys + 1, Iterables.size(graph.get(key).getReverseDeps()));
+    assertEquals(new StringValue("foo1"), graph.get(null, Reason.OTHER, key).getValue());
+    assertEquals(numKeys + 1, Iterables.size(graph.get(null, Reason.OTHER, key).getReverseDeps()));
 
     graph = getGraph(getNextVersion(startingVersion));
-    NodeEntry sameEntry = Preconditions.checkNotNull(graph.get(key));
+    NodeEntry sameEntry = Preconditions.checkNotNull(graph.get(null, Reason.OTHER, key));
     // Mark the node as dirty again and check that the reverse deps have been preserved.
     sameEntry.markDirty(true);
     startEvaluation(sameEntry);
     sameEntry.markRebuilding();
     sameEntry.setValue(new StringValue("foo2"), getNextVersion(startingVersion));
-    assertEquals(new StringValue("foo2"), graph.get(key).getValue());
-    assertEquals(numKeys + 1, Iterables.size(graph.get(key).getReverseDeps()));
+    assertEquals(new StringValue("foo2"), graph.get(null, Reason.OTHER, key).getValue());
+    assertEquals(numKeys + 1, Iterables.size(graph.get(null, Reason.OTHER, key).getReverseDeps()));
   }
 
   // Tests adding inflight nodes with a given key while an existing node with the same key
@@ -236,12 +236,13 @@
               new Runnable() {
                 public void run() {
                   for (SkyKey key : keys) {
-                    NodeEntry entry = graph.get(key);
+                    NodeEntry entry = graph.get(null, Reason.OTHER, key);
                     if (entry == null) {
                       nodeCreated.add(key);
                     }
                   }
-                  Map<SkyKey, NodeEntry> entries = graph.createIfAbsentBatch(keys);
+                  Map<SkyKey, NodeEntry> entries =
+                      graph.createIfAbsentBatch(null, Reason.OTHER, keys);
                   for (Integer keyNum : ImmutableList.of(keyNum1, keyNum2)) {
                     SkyKey key = key("foo" + keyNum);
                     NodeEntry entry = entries.get(key);
@@ -255,7 +256,7 @@
                     }
                   }
                   // This shouldn't cause any problems from the other threads.
-                  graph.createIfAbsentBatch(keys);
+                  graph.createIfAbsentBatch(null, Reason.OTHER, keys);
                 }
               };
           pool.execute(wrapper.wrap(r));
@@ -269,8 +270,9 @@
       SkyKey key = key("foo" + i);
       assertTrue(nodeCreated.contains(key));
       assertTrue(valuesSet.contains(key));
-      assertThat(graph.get(key).getValue()).isEqualTo(new StringValue("bar" + i));
-      assertThat(graph.get(key).getVersion()).isEqualTo(startingVersion);
+      assertThat(graph.get(null, Reason.OTHER, key).getValue())
+          .isEqualTo(new StringValue("bar" + i));
+      assertThat(graph.get(null, Reason.OTHER, key).getVersion()).isEqualTo(startingVersion);
     }
   }
 
@@ -289,16 +291,16 @@
     for (int i = 0; i < numKeys; i++) {
       keys.add(key("foo" + i));
     }
-    Map<SkyKey, NodeEntry> entries = graph.createIfAbsentBatch(keys);
+    Map<SkyKey, NodeEntry> entries = graph.createIfAbsentBatch(null, Reason.OTHER, keys);
     for (int i = 0; i < numKeys; i++) {
       NodeEntry entry = entries.get(key("foo" + i));
       startEvaluation(entry);
       entry.setValue(new StringValue("bar"), startingVersion);
     }
 
-    assertNotNull(graph.get(key("foo" + 0)));
+    assertNotNull(graph.get(null, Reason.OTHER, key("foo" + 0)));
     graph = getGraph(getNextVersion(startingVersion));
-    assertNotNull(graph.get(key("foo" + 0)));
+    assertNotNull(graph.get(null, Reason.OTHER, key("foo" + 0)));
     ExecutorService pool1 = Executors.newFixedThreadPool(numThreads);
     ExecutorService pool2 = Executors.newFixedThreadPool(numThreads);
     ExecutorService pool3 = Executors.newFixedThreadPool(numThreads);
@@ -323,7 +325,7 @@
               } catch (InterruptedException e) {
                 throw new AssertionError(e);
               }
-              NodeEntry entry = graph.get(key("foo" + keyNum));
+              NodeEntry entry = graph.get(null, Reason.OTHER, key("foo" + keyNum));
               entry.markDirty(true);
               // Make some changes, like adding a dep and rdep.
               entry.addReverseDepAndCheckIfDone(key("rdep"));
@@ -345,7 +347,7 @@
               } catch (InterruptedException e) {
                 throw new AssertionError(e);
               }
-              NodeEntry entry = graph.get(key("foo" + keyNum));
+              NodeEntry entry = graph.get(null, Reason.OTHER, key("foo" + keyNum));
               assertNotNull(entry);
               // Requests for the value are made at the same time that the version increments from
               // the base. Check that there is no problem in requesting the version and that the
@@ -379,7 +381,7 @@
                 throw new AssertionError(e);
               }
               Map<SkyKey, NodeEntry> batchMap =
-                  graph.getBatchWithFieldHints(batch, NodeEntryField.NO_FIELDS);
+                  graph.getBatchWithFieldHints(null, Reason.OTHER, batch, NodeEntryField.NO_FIELDS);
               getBatchCountDownLatch.countDown();
               assertThat(batchMap).hasSize(batch.size());
               for (NodeEntry entry : batchMap.values()) {
@@ -398,7 +400,7 @@
     assertFalse(ExecutorUtil.interruptibleShutdown(pool2));
     assertFalse(ExecutorUtil.interruptibleShutdown(pool3));
     for (int i = 0; i < numKeys; i++) {
-      NodeEntry entry = graph.get(key("foo" + i));
+      NodeEntry entry = graph.get(null, Reason.OTHER, key("foo" + i));
       assertThat(entry.getValue()).isEqualTo(new StringValue("bar" + i));
       assertThat(entry.getVersion()).isEqualTo(getNextVersion(startingVersion));
       for (SkyKey key : entry.getReverseDeps()) {
diff --git a/src/test/java/com/google/devtools/build/skyframe/NotifyingHelper.java b/src/test/java/com/google/devtools/build/skyframe/NotifyingHelper.java
index 711e9e7..af0049b 100644
--- a/src/test/java/com/google/devtools/build/skyframe/NotifyingHelper.java
+++ b/src/test/java/com/google/devtools/build/skyframe/NotifyingHelper.java
@@ -19,7 +19,6 @@
 import com.google.common.collect.Maps.EntryTransformer;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
 import com.google.devtools.build.lib.util.GroupedList;
-
 import java.util.EnumSet;
 import java.util.Map;
 import java.util.Set;
@@ -89,8 +88,10 @@
     }
 
     @Override
-    public Map<SkyKey, NodeEntry> getBatch(Iterable<SkyKey> keys) {
-      return Maps.transformEntries(delegate.getBatch(keys), notifyingHelper.wrapEntry);
+    public Map<SkyKey, NodeEntry> getBatchForInvalidation(Iterable<SkyKey> keys) {
+      return Maps.transformEntries(
+          delegate.getBatchForInvalidation(keys),
+          notifyingHelper.wrapEntry);
     }
   }
 
@@ -114,24 +115,31 @@
     }
 
     @Override
-    public Map<SkyKey, NodeEntry> createIfAbsentBatch(Iterable<SkyKey> keys) {
+    public Map<SkyKey, NodeEntry> createIfAbsentBatch(
+        @Nullable SkyKey requestor, Reason reason, Iterable<SkyKey> keys) {
       for (SkyKey key : keys) {
         notifyingHelper.graphListener.accept(key, EventType.CREATE_IF_ABSENT, Order.BEFORE, null);
       }
-      return Maps.transformEntries(delegate.createIfAbsentBatch(keys), notifyingHelper.wrapEntry);
+      return Maps.transformEntries(
+          delegate.createIfAbsentBatch(requestor, reason, keys),
+          notifyingHelper.wrapEntry);
     }
 
     @Override
     public Map<SkyKey, NodeEntry> getBatchWithFieldHints(
-        Iterable<SkyKey> keys, EnumSet<NodeEntryField> fields) {
+        @Nullable SkyKey requestor,
+        Reason reason,
+        Iterable<SkyKey> keys,
+        EnumSet<NodeEntryField> fields) {
       return Maps.transformEntries(
-          delegate.getBatchWithFieldHints(keys, fields), notifyingHelper.wrapEntry);
+          delegate.getBatchWithFieldHints(requestor, reason, keys, fields),
+          notifyingHelper.wrapEntry);
     }
 
     @Nullable
     @Override
-    public NodeEntry get(SkyKey key) {
-      return notifyingHelper.wrapEntry(key, delegate.get(key));
+    public NodeEntry get(@Nullable SkyKey requestor, Reason reason, SkyKey key) {
+      return notifyingHelper.wrapEntry(key, delegate.get(requestor, reason, key));
     }
   }
 
diff --git a/src/test/java/com/google/devtools/build/skyframe/NotifyingInMemoryGraph.java b/src/test/java/com/google/devtools/build/skyframe/NotifyingInMemoryGraph.java
index 1689440..d6d3ab0 100644
--- a/src/test/java/com/google/devtools/build/skyframe/NotifyingInMemoryGraph.java
+++ b/src/test/java/com/google/devtools/build/skyframe/NotifyingInMemoryGraph.java
@@ -23,8 +23,8 @@
   }
 
   @Override
-  public Map<SkyKey, NodeEntry> getBatch(Iterable<SkyKey> keys) {
-    return getBatchWithFieldHints(keys, NodeEntryField.ALL_FIELDS);
+  public Map<SkyKey, NodeEntry> getBatchForInvalidation(Iterable<SkyKey> keys) {
+    return getBatchWithFieldHints(null, Reason.INVALIDATION, keys, NodeEntryField.ALL_FIELDS);
   }
 
   @Override