If --batch, --keep_going, --discard_analysis_cache, and the new --noexperimental_enable_critical_path_profiling flags are all specified, then Bazel will delete Actions from ActionLookupValues as they are executed in order to save memory.

Because an already-run action may output an artifact that is only requested later in the build, we need to maintain a way for the artifact to look up the action. But in most cases we don't need to keep the action itself, just its output metadata.

Some actions unfortunately are needed post-execution, and so we special-case them.

Also includes dependency change with description:
Move action out of key. This keeps action references from polluting the graph -- actions are just stored in one SkyValue, instead of being present in SkyKeys.

This does mean additional memory used: we have a separate ActionLookupData object per Action executed. That may reach ~24M for million-action builds.

PiperOrigin-RevId: 151756383

51 files changed, 1102 insertions, 506 deletions

diff --git a/src/main/java/com/google/devtools/build/lib/actions/AbstractAction.java b/src/main/java/com/google/devtools/build/lib/actions/AbstractAction.java
index 101cc3932a..ad2148a089 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/AbstractAction.java
+++ b/src/main/java/com/google/devtools/build/lib/actions/AbstractAction.java
@@ -439,6 +439,11 @@ public abstract class AbstractAction implements Action, SkylarkValue {
     return MiddlemanType.NORMAL;
   }
 
+  @Override
+  public boolean canRemoveAfterExecution() {
+    return true;
+  }
+
   /**
    * If the action might create directories as outputs this method must be called.
    */
diff --git a/src/main/java/com/google/devtools/build/lib/actions/Action.java b/src/main/java/com/google/devtools/build/lib/actions/Action.java
index d490e6a258..33b0b16658 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/Action.java
+++ b/src/main/java/com/google/devtools/build/lib/actions/Action.java
@@ -185,6 +185,8 @@ public interface Action extends ActionExecutionMetadata, Describable {
    */
   boolean showsOutputUnconditionally();
 
+  boolean canRemoveAfterExecution();
+
   /**
    * Returns true if an {@link com.google.devtools.build.lib.rules.extra.ExtraAction} action can be
    * attached to this action. If not, extra actions should not be attached to this action.
diff --git a/src/main/java/com/google/devtools/build/lib/actions/ActionCompletionEvent.java b/src/main/java/com/google/devtools/build/lib/actions/ActionCompletionEvent.java
index 497f96f7b8..d4621ea827 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/ActionCompletionEvent.java
+++ b/src/main/java/com/google/devtools/build/lib/actions/ActionCompletionEvent.java
@@ -20,10 +20,13 @@ public final class ActionCompletionEvent {
 
   private final long relativeActionStartTime;
   private final Action action;
+  private final ActionLookupData actionLookupData;
 
-  public ActionCompletionEvent(long relativeActionStartTime, Action action) {
+  public ActionCompletionEvent(
+      long relativeActionStartTime, Action action, ActionLookupData actionLookupData) {
     this.relativeActionStartTime = relativeActionStartTime;
     this.action = action;
+    this.actionLookupData = actionLookupData;
   }
 
   /**
@@ -36,4 +39,8 @@ public final class ActionCompletionEvent {
   public long getRelativeActionStartTime() {
     return relativeActionStartTime;
   }
+
+  public ActionLookupData getActionLookupData() {
+    return actionLookupData;
+  }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/actions/ActionLookupData.java b/src/main/java/com/google/devtools/build/lib/actions/ActionLookupData.java
new file mode 100644
index 0000000000..fea6d6d357
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/actions/ActionLookupData.java
@@ -0,0 +1,74 @@
+// Copyright 2017 The Bazel Authors. All rights reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//    http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+package com.google.devtools.build.lib.actions;
+
+import com.google.common.base.MoreObjects;
+import com.google.devtools.build.lib.cmdline.Label;
+import com.google.devtools.build.lib.util.Preconditions;
+import com.google.devtools.build.skyframe.SkyKey;
+
+/** Data that uniquely identifies an action. */
+public class ActionLookupData {
+  private final SkyKey actionLookupNode;
+  private final int actionIndex;
+
+  public ActionLookupData(SkyKey actionLookupNode, int actionIndex) {
+    Preconditions.checkState(
+        actionLookupNode.argument() instanceof ActionLookupValue.ActionLookupKey, actionLookupNode);
+    this.actionLookupNode = actionLookupNode;
+    this.actionIndex = actionIndex;
+  }
+
+  public SkyKey getActionLookupNode() {
+    return actionLookupNode;
+  }
+
+  /**
+   * Index of the action in question in the node keyed by {@link #getActionLookupNode}. Should be
+   * passed to {@link ActionLookupValue#getAction}.
+   */
+  public int getActionIndex() {
+    return actionIndex;
+  }
+
+  public Label getLabelForErrors() {
+    return ((ActionLookupValue.ActionLookupKey) actionLookupNode.argument()).getLabel();
+  }
+
+  @Override
+  public int hashCode() {
+    return 37 * actionLookupNode.hashCode() + actionIndex;
+  }
+
+  @Override
+  public boolean equals(Object obj) {
+    if (this == obj) {
+      return true;
+    }
+    if (!(obj instanceof ActionLookupData)) {
+      return false;
+    }
+    ActionLookupData that = (ActionLookupData) obj;
+    return this.actionIndex == that.actionIndex
+        && this.actionLookupNode.equals(that.actionLookupNode);
+  }
+
+  @Override
+  public String toString() {
+    return MoreObjects.toStringHelper(this)
+        .add("actionLookupNode", actionLookupNode)
+        .add("actionIndex", actionIndex)
+        .toString();
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/actions/ActionLookupValue.java b/src/main/java/com/google/devtools/build/lib/actions/ActionLookupValue.java
new file mode 100644
index 0000000000..b8c105f7b5
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/actions/ActionLookupValue.java
@@ -0,0 +1,232 @@
+// Copyright 2014 The Bazel Authors. All rights reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//    http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+package com.google.devtools.build.lib.actions;
+
+import com.google.common.annotations.VisibleForTesting;
+import com.google.common.base.Function;
+import com.google.common.base.MoreObjects;
+import com.google.common.base.MoreObjects.ToStringHelper;
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableMap;
+import com.google.common.collect.Maps;
+import com.google.devtools.build.lib.actions.MutableActionGraph.ActionConflictException;
+import com.google.devtools.build.lib.cmdline.Label;
+import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
+import com.google.devtools.build.lib.util.Preconditions;
+import com.google.devtools.build.skyframe.SkyFunctionName;
+import com.google.devtools.build.skyframe.SkyKey;
+import com.google.devtools.build.skyframe.SkyValue;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Map;
+import javax.annotation.Nullable;
+
+/**
+ * Base class for all values which can provide the generating action of an artifact. The primary
+ * instance of such lookup values is {@code ConfiguredTargetValue}. Values that hold the generating
+ * actions of target completion values and build info artifacts also fall into this category.
+ */
+public class ActionLookupValue implements SkyValue {
+  protected final List<ActionAnalysisMetadata> actions;
+  private final ImmutableMap<Artifact, Integer> generatingActionIndex;
+
+  private static Actions.GeneratingActions filterSharedActionsAndThrowRuntimeIfConflict(
+      List<ActionAnalysisMetadata> actions) {
+    try {
+      return Actions.filterSharedActionsAndThrowActionConflict(actions);
+    } catch (ActionConflictException e) {
+      // Programming bug.
+      throw new IllegalStateException(e);
+    }
+  }
+
+  @VisibleForTesting
+  public ActionLookupValue(
+      List<ActionAnalysisMetadata> actions, boolean removeActionsAfterEvaluation) {
+    this(filterSharedActionsAndThrowRuntimeIfConflict(actions), removeActionsAfterEvaluation);
+  }
+
+  protected ActionLookupValue(ActionAnalysisMetadata action, boolean removeActionAfterEvaluation) {
+    this(ImmutableList.of(action), removeActionAfterEvaluation);
+  }
+
+  protected ActionLookupValue(
+      Actions.GeneratingActions generatingActions, boolean removeActionsAfterEvaluation) {
+    if (removeActionsAfterEvaluation) {
+      this.actions = new ArrayList<>(generatingActions.getActions());
+    } else {
+      this.actions = ImmutableList.copyOf(generatingActions.getActions());
+    }
+    this.generatingActionIndex = generatingActions.getGeneratingActionIndex();
+  }
+
+  /**
+   * Returns the action that generates {@code artifact}, if known to this value, or null. This
+   * method should be avoided. Call it only when the action is really needed, and it is known to be
+   * present, either because the execution phase has not started, or because {@link
+   * Action#canRemoveAfterExecution} is known to be false for the action being requested.
+   */
+  @Nullable
+  public ActionAnalysisMetadata getGeneratingActionDangerousReadJavadoc(Artifact artifact) {
+    Integer actionIndex = getGeneratingActionIndex(artifact);
+    if (actionIndex == null) {
+      return null;
+    }
+    return getActionAnalysisMetadata(actionIndex);
+  }
+
+  /**
+   * Returns the index of the action that generates {@code artifact} in this value, or null if this
+   * value does not have a generating action for this artifact. The index together with the key for
+   * this {@link ActionLookupValue} uniquely identifies the action.
+   *
+   * <p>Unlike {@link #getAction}, this may be called after action execution.
+   */
+  @Nullable
+  public Integer getGeneratingActionIndex(Artifact artifact) {
+    return generatingActionIndex.get(artifact);
+  }
+
+  /**
+   * Returns the {@link Action} with index {@code index} in this value. Never null. Should only be
+   * called during action execution by {@code ArtifactFunction} and {@code ActionExecutionFunction}
+   * -- after an action has executed, calling this with its index may crash.
+   */
+  @SuppressWarnings("unchecked") // We test to make sure it's an Action.
+  public Action getAction(int index) {
+    ActionAnalysisMetadata result = getActionAnalysisMetadata(index);
+    Preconditions.checkState(result instanceof Action, "Not action: %s %s %s", result, index, this);
+    return (Action) result;
+  }
+
+  private ActionAnalysisMetadata getActionAnalysisMetadata(int index) {
+    return Preconditions.checkNotNull(actions.get(index), "null action: %s %s", index, this);
+  }
+
+  /**
+   * Returns the {@link ActionAnalysisMetadata} at index {@code index} if it is present and
+   * <i>not</i> an {@link Action}. Tree artifacts need their {@code ActionTemplate}s in order to
+   * generate the correct actions, but in general most actions are not needed after they are
+   * executed and may not even be available.
+   */
+  public ActionAnalysisMetadata getIfPresentAndNotAction(int index) {
+    ActionAnalysisMetadata actionAnalysisMetadata = actions.get(index);
+    if (!(actionAnalysisMetadata instanceof Action)) {
+      return actionAnalysisMetadata;
+    }
+    return null;
+  }
+
+  /** To be used only when checking consistency of the action graph -- not by other values. */
+  public Map<Artifact, ActionAnalysisMetadata> getMapForConsistencyCheck() {
+    return getMapForConsistencyCheck(generatingActionIndex, actions);
+  }
+
+  protected ToStringHelper getStringHelper() {
+    return MoreObjects.toStringHelper(this)
+        .add("actions", actions)
+        .add("generatingActionIndex", generatingActionIndex);
+  }
+
+  @Override
+  public String toString() {
+    return getStringHelper().toString();
+  }
+
+  @VisibleForTesting
+  public static SkyKey key(ActionLookupKey ownerKey) {
+    return ownerKey.getSkyKey();
+  }
+
+  public int getNumActions() {
+    return actions.size();
+  }
+
+  public static Map<Artifact, ActionAnalysisMetadata> getMapForConsistencyCheck(
+      Map<Artifact, Integer> generatingActionIndex,
+      final List<? extends ActionAnalysisMetadata> actions) {
+    return Maps.transformValues(
+        generatingActionIndex,
+        new Function<Integer, ActionAnalysisMetadata>() {
+          @Override
+          public ActionAnalysisMetadata apply(Integer index) {
+            return actions.get(index);
+          }
+        });
+  }
+
+  /**
+   * If this object was initialized with {@code removeActionsAfterEvaluation} and {@link
+   * Action#canRemoveAfterExecution()} is true for {@code action}, then remove this action from this
+   * object's index as a memory-saving measure. The {@code artifact -> index} mapping remains
+   * intact, so this action's execution value can still be addressed by its inputs.
+   */
+  @ThreadSafe
+  public void actionEvaluated(int actionIndex, Action action) {
+    if (!action.canRemoveAfterExecution()) {
+      return;
+    }
+    if (actions instanceof ArrayList) {
+      // This method may concurrently mutate an ArrayList, which is unsafe on its face. However,
+      // ArrayList mutation on different indices that does not affect the size of the ArrayList is
+      // safe, and that is what does this code does.
+      ArrayList<ActionAnalysisMetadata> actionArrayList =
+          (ArrayList<ActionAnalysisMetadata>) actions;
+      ActionAnalysisMetadata oldAction = actionArrayList.set(actionIndex, null);
+      Preconditions.checkState(
+          action.equals(oldAction), "Not same: %s %s %s %s", action, oldAction, this, actionIndex);
+    }
+  }
+
+  /**
+   * ArtifactOwner is not a SkyKey, but we wish to convert any ArtifactOwner into a SkyKey as simply
+   * as possible. To that end, all subclasses of ActionLookupValue "own" artifacts with
+   * ArtifactOwners that are subclasses of ActionLookupKey. This allows callers to easily find the
+   * value key, while remaining agnostic to what ActionLookupValues actually exist.
+   *
+   * <p>The methods of this class should only be called by {@link ActionLookupValue#key}.
+   */
+  public abstract static class ActionLookupKey implements ArtifactOwner {
+    @Override
+    public Label getLabel() {
+      return null;
+    }
+
+    /**
+     * Subclasses must override this to specify their specific value type, unless they override
+     * {@link #getSkyKey}, in which case they are free not to implement this method.
+     */
+    protected abstract SkyFunctionName getType();
+
+    protected SkyKey getSkyKeyInternal() {
+      return SkyKey.create(getType(), this);
+    }
+
+    /**
+     * Prefer {@link ActionLookupValue#key} to calling this method directly.
+     *
+     * <p>Subclasses may override {@link #getSkyKeyInternal} if the {@link SkyKey} argument should
+     * not be this {@link ActionLookupKey} itself.
+     */
+    public final SkyKey getSkyKey() {
+      SkyKey result = getSkyKeyInternal();
+      Preconditions.checkState(
+          result.argument() instanceof ActionLookupKey,
+          "Not ActionLookupKey for %s: %s",
+          this,
+          result);
+      return result;
+    }
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/actions/Actions.java b/src/main/java/com/google/devtools/build/lib/actions/Actions.java
index b8bd981156..8a49af4bad 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/Actions.java
+++ b/src/main/java/com/google/devtools/build/lib/actions/Actions.java
@@ -14,6 +14,7 @@
 
 package com.google.devtools.build.lib.actions;
 
+import com.google.common.annotations.VisibleForTesting;
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.Iterables;
 import com.google.common.escape.Escaper;
@@ -23,14 +24,13 @@ import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
 import com.google.devtools.build.lib.util.Preconditions;
 import com.google.devtools.build.lib.vfs.PathFragment;
-
 import java.util.HashMap;
 import java.util.Iterator;
 import java.util.LinkedHashMap;
+import java.util.List;
 import java.util.Map;
 import java.util.SortedMap;
 import java.util.TreeMap;
-
 import javax.annotation.Nullable;
 
 /**
@@ -85,12 +85,12 @@ public final class Actions {
    * artifact. Shared actions are tolerated. See {@link #canBeShared} for details.
    *
    * @param actions a list of actions to check for action conflicts
-   * @return a map between generated artifacts and their associated generating actions. If there is
-   *     more than one action generating the same output artifact, only one action is chosen.
+   * @return a structure giving the mapping between artifacts and generating actions, with a level
+   *     of indirection.
    * @throws ActionConflictException iff there are two actions generate the same output
    */
-  public static ImmutableMap<Artifact, ActionAnalysisMetadata> findAndThrowActionConflict(
-      Iterable<ActionAnalysisMetadata> actions) throws ActionConflictException {
+  public static GeneratingActions findAndThrowActionConflict(List<ActionAnalysisMetadata> actions)
+      throws ActionConflictException {
     return Actions.maybeFilterSharedActionsAndThrowIfConflict(
         actions, /*allowSharedAction=*/ false);
   }
@@ -100,34 +100,34 @@ public final class Actions {
    * artifact. Shared actions are tolerated. See {@link #canBeShared} for details.
    *
    * @param actions a list of actions to check for action conflicts
-   * @return a map between generated artifacts and their associated generating actions. If there is
-   *     more than one action generating the same output artifact, only one action is chosen.
+   * @return a structure giving the mapping between artifacts and generating actions, with a level
+   *     of indirection.
    * @throws ActionConflictException iff there are two unshareable actions generating the same
    *     output
    */
-  public static ImmutableMap<Artifact, ActionAnalysisMetadata>
-      filterSharedActionsAndThrowActionConflict(
-      Iterable<? extends ActionAnalysisMetadata> actions) throws ActionConflictException {
+  public static GeneratingActions filterSharedActionsAndThrowActionConflict(
+      List<ActionAnalysisMetadata> actions) throws ActionConflictException {
     return Actions.maybeFilterSharedActionsAndThrowIfConflict(
         actions, /*allowSharedAction=*/ true);
   }
 
-  private static ImmutableMap<Artifact, ActionAnalysisMetadata>
-      maybeFilterSharedActionsAndThrowIfConflict(
-      Iterable<? extends ActionAnalysisMetadata> actions, boolean allowSharedAction)
+  private static GeneratingActions maybeFilterSharedActionsAndThrowIfConflict(
+      List<ActionAnalysisMetadata> actions, boolean allowSharedAction)
       throws ActionConflictException {
-    Map<Artifact, ActionAnalysisMetadata> generatingActions = new HashMap<>();
+    Map<Artifact, Integer> generatingActions = new HashMap<>();
+    int actionIndex = 0;
     for (ActionAnalysisMetadata action : actions) {
       for (Artifact artifact : action.getOutputs()) {
-        ActionAnalysisMetadata previousAction = generatingActions.put(artifact, action);
-        if (previousAction != null && previousAction != action) {
-          if (!allowSharedAction || !Actions.canBeShared(previousAction, action)) {
-            throw new ActionConflictException(artifact, previousAction, action);
+        Integer previousIndex = generatingActions.put(artifact, actionIndex);
+        if (previousIndex != null && previousIndex != actionIndex) {
+          if (!allowSharedAction || !Actions.canBeShared(actions.get(previousIndex), action)) {
+            throw new ActionConflictException(artifact, actions.get(previousIndex), action);
           }
         }
       }
+      actionIndex++;
     }
-    return ImmutableMap.copyOf(generatingActions);
+    return new GeneratingActions(actions, ImmutableMap.copyOf(generatingActions));
   }
 
   /**
@@ -252,4 +252,27 @@ public final class Actions {
       return generatingActions.get(artifact);
     }
   }
+
+  /** Container class for actions and the artifacts they generate. */
+  @VisibleForTesting
+  public static class GeneratingActions {
+    private final List<ActionAnalysisMetadata> actions;
+    private final ImmutableMap<Artifact, Integer> generatingActionIndex;
+
+    @VisibleForTesting
+    public GeneratingActions(
+        List<ActionAnalysisMetadata> actions,
+        ImmutableMap<Artifact, Integer> generatingActionIndex) {
+      this.actions = actions;
+      this.generatingActionIndex = generatingActionIndex;
+    }
+
+    public ImmutableMap<Artifact, Integer> getGeneratingActionIndex() {
+      return generatingActionIndex;
+    }
+
+    public List<ActionAnalysisMetadata> getActions() {
+      return actions;
+    }
+  }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/actions/MiddlemanAction.java b/src/main/java/com/google/devtools/build/lib/actions/MiddlemanAction.java
index a42d5b958d..7474c7c13d 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/MiddlemanAction.java
+++ b/src/main/java/com/google/devtools/build/lib/actions/MiddlemanAction.java
@@ -73,6 +73,13 @@ public final class MiddlemanAction extends AbstractAction {
   }
 
   @Override
+  public boolean canRemoveAfterExecution() {
+    // Aggregating middleman actions' inputs are needed by their output artifacts, and the type of
+    // the middleman isn't known without having the action, so we just make sure it stays.
+    return false;
+  }
+
+  @Override
   protected String getRawProgressMessage() {
     return null; // users don't really want to know about Middlemen.
   }
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/AnalysisEnvironment.java b/src/main/java/com/google/devtools/build/lib/analysis/AnalysisEnvironment.java
index eb559ea81e..70b8e51967 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/AnalysisEnvironment.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/AnalysisEnvironment.java
@@ -27,6 +27,7 @@ import com.google.devtools.build.lib.analysis.config.BuildConfiguration;
 import com.google.devtools.build.lib.events.ExtendedEventHandler;
 import com.google.devtools.build.lib.vfs.PathFragment;
 import com.google.devtools.build.skyframe.SkyFunction;
+import java.util.List;
 
 /**
  * The set of services that are provided to {@link ConfiguredTarget} objects
@@ -106,7 +107,7 @@ public interface AnalysisEnvironment extends ActionRegistry {
    * Returns the actions that were registered so far with this analysis environment, that is, all
    * the actions that were created by the current target being analyzed.
    */
-  Iterable<ActionAnalysisMetadata> getRegisteredActions();
+  List<ActionAnalysisMetadata> getRegisteredActions();
 
   /**
    * Returns the Skyframe SkyFunction.Environment if available. Otherwise, null.
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/BuildView.java b/src/main/java/com/google/devtools/build/lib/analysis/BuildView.java
index c9709ab4ef..7c18968f6b 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/BuildView.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/BuildView.java
@@ -31,6 +31,7 @@ import com.google.common.collect.Sets;
 import com.google.common.eventbus.EventBus;
 import com.google.devtools.build.lib.actions.ActionAnalysisMetadata;
 import com.google.devtools.build.lib.actions.ActionGraph;
+import com.google.devtools.build.lib.actions.ActionLookupValue;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.actions.ArtifactFactory;
 import com.google.devtools.build.lib.actions.ArtifactOwner;
@@ -71,7 +72,6 @@ import com.google.devtools.build.lib.pkgcache.LoadingResult;
 import com.google.devtools.build.lib.rules.test.CoverageReportActionFactory;
 import com.google.devtools.build.lib.rules.test.CoverageReportActionFactory.CoverageReportActionsWrapper;
 import com.google.devtools.build.lib.rules.test.InstrumentedFilesProvider;
-import com.google.devtools.build.lib.skyframe.ActionLookupValue;
 import com.google.devtools.build.lib.skyframe.AspectValue;
 import com.google.devtools.build.lib.skyframe.AspectValue.AspectKey;
 import com.google.devtools.build.lib.skyframe.AspectValue.AspectValueKey;
@@ -641,7 +641,7 @@ public class BuildView {
                 throw new IllegalStateException(
                     "Interruption not expected from this graph: " + key, e);
               }
-              return val == null ? null : val.getGeneratingAction(artifact);
+              return val == null ? null : val.getGeneratingActionDangerousReadJavadoc(artifact);
             }
             return null;
           }
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/CachingAnalysisEnvironment.java b/src/main/java/com/google/devtools/build/lib/analysis/CachingAnalysisEnvironment.java
index 426b00fcf0..ddf5b99fe4 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/CachingAnalysisEnvironment.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/CachingAnalysisEnvironment.java
@@ -270,8 +270,8 @@ public class CachingAnalysisEnvironment implements AnalysisEnvironment {
   }
 
   @Override
-  public Collection<ActionAnalysisMetadata> getRegisteredActions() {
-    return Collections.unmodifiableCollection(actions);
+  public List<ActionAnalysisMetadata> getRegisteredActions() {
+    return Collections.unmodifiableList(actions);
   }
 
   @Override
diff --git a/src/main/java/com/google/devtools/build/lib/buildtool/ExecutionProgressReceiver.java b/src/main/java/com/google/devtools/build/lib/buildtool/ExecutionProgressReceiver.java
index bd8f8cb7a8..24b1ba0a43 100644
--- a/src/main/java/com/google/devtools/build/lib/buildtool/ExecutionProgressReceiver.java
+++ b/src/main/java/com/google/devtools/build/lib/buildtool/ExecutionProgressReceiver.java
@@ -17,7 +17,9 @@ import com.google.common.base.Supplier;
 import com.google.common.collect.Sets;
 import com.google.common.eventbus.EventBus;
 import com.google.devtools.build.lib.actions.Action;
+import com.google.devtools.build.lib.actions.ActionAnalysisMetadata.MiddlemanType;
 import com.google.devtools.build.lib.actions.ActionExecutionStatusReporter;
+import com.google.devtools.build.lib.actions.ActionLookupData;
 import com.google.devtools.build.lib.analysis.AspectCompleteEvent;
 import com.google.devtools.build.lib.analysis.ConfiguredTarget;
 import com.google.devtools.build.lib.analysis.TargetCompleteEvent;
@@ -25,7 +27,6 @@ import com.google.devtools.build.lib.analysis.TopLevelArtifactContext;
 import com.google.devtools.build.lib.analysis.TopLevelArtifactHelper;
 import com.google.devtools.build.lib.analysis.TopLevelArtifactHelper.ArtifactsToBuild;
 import com.google.devtools.build.lib.skyframe.ActionExecutionInactivityWatchdog;
-import com.google.devtools.build.lib.skyframe.ActionExecutionValue;
 import com.google.devtools.build.lib.skyframe.AspectCompletionValue;
 import com.google.devtools.build.lib.skyframe.AspectValue;
 import com.google.devtools.build.lib.skyframe.SkyFunctions;
@@ -53,8 +54,10 @@ public final class ExecutionProgressReceiver
 
   // Must be thread-safe!
   private final Set<ConfiguredTarget> builtTargets;
-  private final Set<SkyKey> enqueuedActions = Sets.newConcurrentHashSet();
-  private final Set<Action> completedActions = Sets.newConcurrentHashSet();
+  private final Set<ActionLookupData> enqueuedActions = Sets.newConcurrentHashSet();
+  private final Set<ActionLookupData> completedActions = Sets.newConcurrentHashSet();
+  private final Set<ActionLookupData> ignoredActions = Sets.newConcurrentHashSet();
+
   private final Object activityIndicator = new Object();
   /** Number of exclusive tests. To be accounted for in progress messages. */
   private final int exclusiveTestsCount;
@@ -89,12 +92,25 @@ public final class ExecutionProgressReceiver
 
   @Override
   public void enqueueing(SkyKey skyKey) {
-    if (ActionExecutionValue.isReportWorthyAction(skyKey)) {
-      // Remember all enqueued actions for the benefit of progress reporting.
-      // We discover most actions early in the build, well before we start executing them.
-      // Some of these will be cache hits and won't be executed, so we'll need to account for them
-      // in the evaluated method too.
-      enqueuedActions.add(skyKey);
+    if (skyKey.functionName().equals(SkyFunctions.ACTION_EXECUTION)) {
+      ActionLookupData actionLookupData = (ActionLookupData) skyKey.argument();
+      if (!ignoredActions.contains(actionLookupData)) {
+        // Remember all enqueued actions for the benefit of progress reporting.
+        // We discover most actions early in the build, well before we start executing them.
+        // Some of these will be cache hits and won't be executed, so we'll need to account for them
+        // in the evaluated method too.
+        enqueuedActions.add(actionLookupData);
+      }
+    }
+  }
+
+  @Override
+  public void noteActionEvaluationStarted(ActionLookupData actionLookupData, Action action) {
+    if (!isActionReportWorthy(action)) {
+      ignoredActions.add(actionLookupData);
+      // There is no race here because this is called synchronously during action execution, so no
+      // other thread can concurrently enqueue the action for execution under the Skyframe model.
+      enqueuedActions.remove(actionLookupData);
     }
   }
 
@@ -129,33 +145,37 @@ public final class ExecutionProgressReceiver
     } else if (type.equals(SkyFunctions.ACTION_EXECUTION)) {
       // Remember all completed actions, even those in error, regardless of having been cached or
       // really executed.
-      actionCompleted((Action) skyKey.argument());
+      actionCompleted((ActionLookupData) skyKey.argument());
     }
   }
 
   /**
    * {@inheritDoc}
    *
-   * <p>This method adds the action to {@link #completedActions} and notifies the
-   * {@link #activityIndicator}.
+   * <p>This method adds the action lookup data to {@link #completedActions} and notifies the {@link
+   * #activityIndicator}.
    *
    * <p>We could do this only in the {@link #evaluated} method too, but as it happens the action
    * executor tells the reporter about the completed action before the node is inserted into the
-   * graph, so the reporter would find out about the completed action sooner than we could
-   * have updated {@link #completedActions}, which would result in incorrect numbers on the
-   * progress messages. However we have to store completed actions in {@link #evaluated} too,
-   * because that's the only place we get notified about completed cached actions.
+   * graph, so the reporter would find out about the completed action sooner than we could have
+   * updated {@link #completedActions}, which would result in incorrect numbers on the progress
+   * messages. However we have to store completed actions in {@link #evaluated} too, because that's
+   * the only place we get notified about completed cached actions.
    */
   @Override
-  public void actionCompleted(Action a) {
-    if (ActionExecutionValue.isReportWorthyAction(a)) {
-      completedActions.add(a);
+  public void actionCompleted(ActionLookupData actionLookupData) {
+    if (!ignoredActions.contains(actionLookupData)) {
+      completedActions.add(actionLookupData);
       synchronized (activityIndicator) {
         activityIndicator.notifyAll();
       }
     }
   }
 
+  private static boolean isActionReportWorthy(Action action) {
+    return action.getActionType() == MiddlemanType.NORMAL;
+  }
+
   @Override
   public String getProgressString() {
     return String.format(
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/CppCompileAction.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppCompileAction.java
index 8c3a18e83c..84b3c85a93 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CppCompileAction.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppCompileAction.java
@@ -24,6 +24,8 @@ import com.google.common.collect.Sets;
 import com.google.devtools.build.lib.actions.AbstractAction;
 import com.google.devtools.build.lib.actions.ActionExecutionContext;
 import com.google.devtools.build.lib.actions.ActionExecutionException;
+import com.google.devtools.build.lib.actions.ActionLookupValue;
+import com.google.devtools.build.lib.actions.ActionLookupValue.ActionLookupKey;
 import com.google.devtools.build.lib.actions.ActionOwner;
 import com.google.devtools.build.lib.actions.ActionStatusMessage;
 import com.google.devtools.build.lib.actions.Artifact;
@@ -51,8 +53,6 @@ import com.google.devtools.build.lib.profiler.ProfilerTask;
 import com.google.devtools.build.lib.rules.cpp.CcToolchainFeatures.FeatureConfiguration;
 import com.google.devtools.build.lib.rules.cpp.CppCompileActionContext.Reply;
 import com.google.devtools.build.lib.rules.cpp.CppConfiguration.Tool;
-import com.google.devtools.build.lib.skyframe.ActionLookupValue;
-import com.google.devtools.build.lib.skyframe.ActionLookupValue.ActionLookupKey;
 import com.google.devtools.build.lib.util.DependencySet;
 import com.google.devtools.build.lib.util.FileType;
 import com.google.devtools.build.lib.util.Fingerprint;
@@ -513,7 +513,15 @@ public class CppCompileAction extends AbstractAction
       ActionLookupValue value = (ActionLookupValue) skyValues.get(skyKey);
       Preconditions.checkNotNull(
           value, "Owner %s of %s not in graph %s", artifact.getArtifactOwner(), artifact, skyKey);
-      CppCompileAction action = (CppCompileAction) value.getGeneratingAction(artifact);
+      // We can get the generating action here because #canRemoveAfterExecution is overridden.
+      Preconditions.checkState(
+          CppFileTypes.CPP_MODULE.matches(artifact.getFilename()),
+          "Non-module? %s (%s %s)",
+          artifact,
+          this,
+          value);
+      CppCompileAction action =
+          (CppCompileAction) value.getGeneratingActionDangerousReadJavadoc(artifact);
       for (Artifact input : action.getInputs()) {
         if (CppFileTypes.CPP_MODULE.matches(input.getFilename())) {
           additionalModules.add(input);
@@ -734,6 +742,13 @@ public class CppCompileAction extends AbstractAction
   }
 
   @Override
+  public boolean canRemoveAfterExecution() {
+    // Module-generating actions are needed because the action may be retrieved in
+    // #discoverInputsStage2.
+    return !CppFileTypes.CPP_MODULE.matches(getPrimaryOutput().getFilename());
+  }
+
+  @Override
   public boolean extraActionCanAttach() {
     return cppConfiguration.alwaysAttachExtraActions()
         || !specialInputsHandler.isSpecialFile(getPrimaryInput());
diff --git a/src/main/java/com/google/devtools/build/lib/runtime/CommandEnvironment.java b/src/main/java/com/google/devtools/build/lib/runtime/CommandEnvironment.java
index fea9d72b1d..00a69dc5d0 100644
--- a/src/main/java/com/google/devtools/build/lib/runtime/CommandEnvironment.java
+++ b/src/main/java/com/google/devtools/build/lib/runtime/CommandEnvironment.java
@@ -32,6 +32,7 @@ import com.google.devtools.build.lib.analysis.config.DefaultsPackage;
 import com.google.devtools.build.lib.analysis.config.InvalidConfigurationException;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.events.Reporter;
+import com.google.devtools.build.lib.exec.ExecutionOptions;
 import com.google.devtools.build.lib.exec.OutputService;
 import com.google.devtools.build.lib.packages.NoSuchThingException;
 import com.google.devtools.build.lib.packages.Target;
@@ -567,7 +568,8 @@ public final class CommandEnvironment {
     // Let skyframe figure out if it needs to store graph edges for this build.
     skyframeExecutor.decideKeepIncrementalState(
         runtime.getStartupOptionsProvider().getOptions(BlazeServerStartupOptions.class).batch,
-        optionsParser.getOptions(BuildView.Options.class));
+        optionsParser.getOptions(BuildView.Options.class),
+        optionsParser.getOptions(ExecutionOptions.class));
 
     // Start the performance and memory profilers.
     runtime.beforeCommand(this, options, execStartTimeNanos);
diff --git a/src/main/java/com/google/devtools/build/lib/runtime/ExperimentalStateTracker.java b/src/main/java/com/google/devtools/build/lib/runtime/ExperimentalStateTracker.java
index 353dcd4a46..73f32e493c 100644
--- a/src/main/java/com/google/devtools/build/lib/runtime/ExperimentalStateTracker.java
+++ b/src/main/java/com/google/devtools/build/lib/runtime/ExperimentalStateTracker.java
@@ -260,7 +260,7 @@ class ExperimentalStateTracker {
     // informed of an action completion, we need to make sure the progress receiver is aware of the
     // completion, even though it might be called later on the event bus.
     if (executionProgressReceiver != null) {
-      executionProgressReceiver.actionCompleted(action);
+      executionProgressReceiver.actionCompleted(event.getActionLookupData());
     }
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ActionArtifactCycleReporter.java b/src/main/java/com/google/devtools/build/lib/skyframe/ActionArtifactCycleReporter.java
index 86b7371c47..8808252848 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ActionArtifactCycleReporter.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ActionArtifactCycleReporter.java
@@ -17,7 +17,7 @@ package com.google.devtools.build.lib.skyframe;
 import com.google.common.base.Predicate;
 import com.google.common.base.Predicates;
 import com.google.common.collect.Iterables;
-import com.google.devtools.build.lib.actions.Action;
+import com.google.devtools.build.lib.actions.ActionLookupData;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.pkgcache.PackageProvider;
 import com.google.devtools.build.lib.skyframe.ArtifactSkyKey.OwnedArtifact;
@@ -50,8 +50,8 @@ public class ActionArtifactCycleReporter extends AbstractLabelCycleReporter {
   private String prettyPrint(SkyFunctionName skyFunctionName, Object arg) {
     if (arg instanceof OwnedArtifact) {
       return "file: " + ((OwnedArtifact) arg).getArtifact().getRootRelativePathString();
-    } else if (arg instanceof Action) {
-      return "action: " + ((Action) arg).getMnemonic();
+    } else if (arg instanceof ActionLookupData) {
+      return "action from: " + arg;
     } else if (arg instanceof TargetCompletionKey
         && skyFunctionName.equals(SkyFunctions.TARGET_COMPLETION)) {
       return "configured target: " + ((TargetCompletionKey) arg).labelAndConfiguration().getLabel();
@@ -68,8 +68,8 @@ public class ActionArtifactCycleReporter extends AbstractLabelCycleReporter {
     Object arg = key.argument();
     if (arg instanceof OwnedArtifact) {
       return ((OwnedArtifact) arg).getArtifact().getOwner();
-    } else if (arg instanceof Action) {
-      return ((Action) arg).getOwner().getLabel();
+    } else if (arg instanceof ActionLookupData) {
+      return ((ActionLookupData) arg).getLabelForErrors();
     } else if (arg instanceof TargetCompletionKey
         && key.functionName().equals(SkyFunctions.TARGET_COMPLETION)) {
       return ((TargetCompletionKey) arg).labelAndConfiguration().getLabel();
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ActionExecutionFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/ActionExecutionFunction.java
index 905c3a93cf..659e1bb14e 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ActionExecutionFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ActionExecutionFunction.java
@@ -24,6 +24,8 @@ import com.google.devtools.build.lib.actions.Action;
 import com.google.devtools.build.lib.actions.ActionCacheChecker.Token;
 import com.google.devtools.build.lib.actions.ActionExecutionContext;
 import com.google.devtools.build.lib.actions.ActionExecutionException;
+import com.google.devtools.build.lib.actions.ActionLookupData;
+import com.google.devtools.build.lib.actions.ActionLookupValue;
 import com.google.devtools.build.lib.actions.AlreadyReportedActionExecutionException;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.actions.MissingInputFileException;
@@ -98,8 +100,12 @@ public class ActionExecutionFunction implements SkyFunction, CompletionReceiver
   @Override
   public SkyValue compute(SkyKey skyKey, Environment env) throws ActionExecutionFunctionException,
       InterruptedException {
-    Preconditions.checkArgument(skyKey.argument() instanceof Action);
-    Action action = (Action) skyKey.argument();
+    ActionLookupData actionLookupData = (ActionLookupData) skyKey.argument();
+    ActionLookupValue actionLookupValue =
+        (ActionLookupValue) env.getValue(actionLookupData.getActionLookupNode());
+    int actionIndex = actionLookupData.getActionIndex();
+    Action action = actionLookupValue.getAction(actionIndex);
+    skyframeActionExecutor.noteActionEvaluationStarted(actionLookupData, action);
     // TODO(bazel-team): Non-volatile NotifyOnActionCacheHit actions perform worse in Skyframe than
     // legacy when they are not at the top of the action graph. In legacy, they are stored
     // separately, so notifying non-dirty actions is cheap. In Skyframe, they depend on the
@@ -193,7 +199,7 @@ public class ActionExecutionFunction implements SkyFunction, CompletionReceiver
 
     ActionExecutionValue result;
     try {
-      result = checkCacheAndExecuteIfNeeded(action, state, env, clientEnv);
+      result = checkCacheAndExecuteIfNeeded(action, state, env, clientEnv, actionLookupData);
     } catch (ActionExecutionException e) {
       // Remove action from state map in case it's there (won't be unless it discovers inputs).
       stateMap.remove(action);
@@ -211,6 +217,7 @@ public class ActionExecutionFunction implements SkyFunction, CompletionReceiver
 
     // Remove action from state map in case it's there (won't be unless it discovers inputs).
     stateMap.remove(action);
+    actionLookupValue.actionEvaluated(actionIndex, action);
     return result;
   }
 
@@ -356,12 +363,16 @@ public class ActionExecutionFunction implements SkyFunction, CompletionReceiver
   }
 
   private ActionExecutionValue checkCacheAndExecuteIfNeeded(
-      Action action, ContinuationState state, Environment env, Map<String, String> clientEnv)
+      Action action,
+      ContinuationState state,
+      Environment env,
+      Map<String, String> clientEnv,
+      ActionLookupData actionLookupData)
       throws ActionExecutionException, InterruptedException {
     // If this is a shared action and the other action is the one that executed, we must use that
     // other action's value, provided here, since it is populated with metadata for the outputs.
     if (!state.hasArtifactData()) {
-      return skyframeActionExecutor.executeAction(action, null, -1, null);
+      return skyframeActionExecutor.executeAction(action, null, -1, null, actionLookupData);
     }
     // This may be recreated if we discover inputs.
     ActionMetadataHandler metadataHandler = new ActionMetadataHandler(state.inputArtifactData,
@@ -437,8 +448,9 @@ public class ActionExecutionFunction implements SkyFunction, CompletionReceiver
               metadataHandler,
               Collections.unmodifiableMap(state.expandedArtifacts));
       if (!state.hasExecutedAction()) {
-        state.value = skyframeActionExecutor.executeAction(action,
-            metadataHandler, actionStartTime, actionExecutionContext);
+        state.value =
+            skyframeActionExecutor.executeAction(
+                action, metadataHandler, actionStartTime, actionExecutionContext, actionLookupData);
       }
     } finally {
       if (actionExecutionContext != null) {
@@ -474,7 +486,8 @@ public class ActionExecutionFunction implements SkyFunction, CompletionReceiver
       }
     }
     Preconditions.checkState(!env.valuesMissing(), action);
-    skyframeActionExecutor.afterExecution(action, metadataHandler, state.token, clientEnv);
+    skyframeActionExecutor.afterExecution(
+        action, metadataHandler, state.token, clientEnv, actionLookupData);
     return state.value;
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ActionExecutionValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/ActionExecutionValue.java
index 4c3c6a2c93..3d71d1b8cd 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ActionExecutionValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ActionExecutionValue.java
@@ -14,22 +14,17 @@
 package com.google.devtools.build.lib.skyframe;
 
 import com.google.common.annotations.VisibleForTesting;
-import com.google.common.base.Function;
 import com.google.common.base.MoreObjects;
 import com.google.common.base.Objects;
 import com.google.common.collect.ImmutableMap;
-import com.google.common.collect.Iterables;
-import com.google.devtools.build.lib.actions.Action;
-import com.google.devtools.build.lib.actions.ActionAnalysisMetadata.MiddlemanType;
+import com.google.devtools.build.lib.actions.ActionLookupData;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
 import com.google.devtools.build.lib.util.Preconditions;
 import com.google.devtools.build.skyframe.SkyKey;
 import com.google.devtools.build.skyframe.SkyValue;
-
 import java.util.Map;
-
 import javax.annotation.Nullable;
 
 /**
@@ -38,15 +33,6 @@ import javax.annotation.Nullable;
 @Immutable
 @ThreadSafe
 public class ActionExecutionValue implements SkyValue {
-
-  private static final Function<Action, SkyKey> TO_KEY =
-      new Function<Action, SkyKey>() {
-        @Override
-        public SkyKey apply(Action action) {
-          return key(action);
-        }
-      };
-
   /*
   Concerning the data in this class:
 
@@ -120,8 +106,9 @@ public class ActionExecutionValue implements SkyValue {
   }
 
   /**
-   * @return The map from {@link Artifact}s to the corresponding {@link FileValue}s that would
-   * be returned by {@link #getData}. Should only be needed by {@link FilesystemValueChecker}.
+   * @return The map from {@link Artifact}s to the corresponding {@link FileValue}s that would be
+   *     returned by {@link #getData}. Primarily needed by {@link FilesystemValueChecker}, also
+   *     called by {@link ArtifactFunction} when aggregating a {@link TreeArtifactValue}.
    */
   ImmutableMap<Artifact, FileValue> getAllFileValues() {
     return artifactData;
@@ -129,44 +116,23 @@ public class ActionExecutionValue implements SkyValue {
 
   /**
    * @return The map from {@link Artifact}s to the corresponding {@link TreeArtifactValue}s that
-   * would be returned by {@link #getTreeArtifactValue}. Should only be needed by
-   * {@link FilesystemValueChecker}.
+   *     would be returned by {@link #getTreeArtifactValue}. Should only be needed by {@link
+   *     FilesystemValueChecker}.
    */
   ImmutableMap<Artifact, TreeArtifactValue> getAllTreeArtifactValues() {
     return treeArtifactData;
   }
 
-  @ThreadSafe
-  @VisibleForTesting
-  public static SkyKey key(Action action) {
-    return SkyKey.create(SkyFunctions.ACTION_EXECUTION, action);
-  }
-
-  static Iterable<SkyKey> keys(Iterable<Action> actions) {
-    return Iterables.transform(actions, TO_KEY);
-  }
-
-  /**
-   * Returns whether the key corresponds to a ActionExecutionValue worth reporting status about.
-   *
-   * <p>If an action can do real work, it's probably worth counting and reporting status about.
-   * Actions that don't really do any work (typically middleman actions) should not be counted
-   * towards enqueued and completed actions.
-   */
-  public static boolean isReportWorthyAction(SkyKey key) {
-    return key.functionName().equals(SkyFunctions.ACTION_EXECUTION)
-        && isReportWorthyAction((Action) key.argument());
-  }
-
   /**
-   * Returns whether the action is worth reporting status about.
-   *
-   * <p>If an action can do real work, it's probably worth counting and reporting status about.
-   * Actions that don't really do any work (typically middleman actions) should not be counted
-   * towards enqueued and completed actions.
+   * @param lookupKey A {@link SkyKey} whose argument is an {@code ActionLookupKey}, whose
+   *     corresponding {@code ActionLookupValue} contains the action to be executed.
+   * @param index the index of the action to be executed in the {@code ActionLookupValue}, to be
+   *     passed to {@code ActionLookupValue#getAction}.
    */
-  public static boolean isReportWorthyAction(Action action) {
-    return action.getActionType() == MiddlemanType.NORMAL;
+  @ThreadSafe
+  @VisibleForTesting
+  public static SkyKey key(SkyKey lookupKey, int index) {
+    return SkyKey.create(SkyFunctions.ACTION_EXECUTION, new ActionLookupData(lookupKey, index));
   }
 
   @Override
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ActionLookupValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/ActionLookupValue.java
deleted file mode 100644
index f5aab9a825..0000000000
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ActionLookupValue.java
+++ /dev/null
@@ -1,116 +0,0 @@
-// Copyright 2014 The Bazel Authors. All rights reserved.
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-//    http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-package com.google.devtools.build.lib.skyframe;
-
-import com.google.common.annotations.VisibleForTesting;
-import com.google.common.collect.ImmutableList;
-import com.google.common.collect.ImmutableMap;
-import com.google.devtools.build.lib.actions.ActionAnalysisMetadata;
-import com.google.devtools.build.lib.actions.Actions;
-import com.google.devtools.build.lib.actions.Artifact;
-import com.google.devtools.build.lib.actions.ArtifactOwner;
-import com.google.devtools.build.lib.actions.MutableActionGraph.ActionConflictException;
-import com.google.devtools.build.lib.cmdline.Label;
-import com.google.devtools.build.lib.util.Preconditions;
-import com.google.devtools.build.skyframe.SkyFunctionName;
-import com.google.devtools.build.skyframe.SkyKey;
-import com.google.devtools.build.skyframe.SkyValue;
-import java.util.Map;
-
-/**
- * Base class for all values which can provide the generating action of an artifact. The primary
- * instance of such lookup values is {@link ConfiguredTargetValue}. Values that hold the generating
- * actions of target completion values and build info artifacts also fall into this category.
- */
-public class ActionLookupValue implements SkyValue {
-  protected final ImmutableMap<Artifact, ActionAnalysisMetadata> generatingActionMap;
-
-  private static ImmutableMap<Artifact, ActionAnalysisMetadata>
-      filterSharedActionsAndThrowRuntimeIfConflict(
-      Iterable<ActionAnalysisMetadata> actions) {
-    try {
-      return Actions.filterSharedActionsAndThrowActionConflict(actions);
-    } catch (ActionConflictException e) {
-      // Programming bug.
-      throw new IllegalStateException(e);
-    }
-  }
-
-  ActionLookupValue(Iterable<ActionAnalysisMetadata> actions) {
-    this(filterSharedActionsAndThrowRuntimeIfConflict(actions));
-  }
-
-  ActionLookupValue(ActionAnalysisMetadata action) {
-    this(ImmutableList.of(action));
-  }
-
-  ActionLookupValue(Map<Artifact, ActionAnalysisMetadata> generatingActionMap) {
-    this.generatingActionMap = ImmutableMap.copyOf(generatingActionMap);
-  }
-
-  public ActionAnalysisMetadata getGeneratingAction(Artifact artifact) {
-    return generatingActionMap.get(artifact);
-  }
-
-  /** To be used only when checking consistency of the action graph -- not by other values. */
-  ImmutableMap<Artifact, ActionAnalysisMetadata> getMapForConsistencyCheck() {
-    return generatingActionMap;
-  }
-
-  @VisibleForTesting
-  public static SkyKey key(ActionLookupKey ownerKey) {
-    return ownerKey.getSkyKey();
-  }
-
-  /**
-   * ArtifactOwner is not a SkyKey, but we wish to convert any ArtifactOwner into a SkyKey as
-   * simply as possible. To that end, all subclasses of ActionLookupValue "own" artifacts with
-   * ArtifactOwners that are subclasses of ActionLookupKey. This allows callers to easily find the
-   * value key, while remaining agnostic to what ActionLookupValues actually exist.
-   *
-   * <p>The methods of this class should only be called by {@link ActionLookupValue#key}.
-   */
-  public abstract static class ActionLookupKey implements ArtifactOwner {
-    @Override
-    public Label getLabel() {
-      return null;
-    }
-
-    /**
-     * Subclasses must override this to specify their specific value type, unless they override
-     * {@link #getSkyKey}, in which case they are free not to implement this method.
-     */
-    abstract SkyFunctionName getType();
-
-    SkyKey getSkyKeyInternal() {
-      return SkyKey.create(getType(), this);
-    }
-
-    /**
-     * Prefer {@link ActionLookupValue#key} to calling this method directly.
-     *
-     * <p>Subclasses may override {@link #getSkyKeyInternal} if the {@link SkyKey} argument should
-     * not be this {@link ActionLookupKey} itself.
-     */
-    final SkyKey getSkyKey() {
-      SkyKey result = getSkyKeyInternal();
-      Preconditions.checkState(
-          result.argument() instanceof ActionLookupKey,
-          "Not ActionLookupKey for %s: %s",
-          this,
-          result);
-      return result;
-    }
-  }
-}
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ActionTemplateExpansionFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/ActionTemplateExpansionFunction.java
index 3164f16973..3967bb22dc 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ActionTemplateExpansionFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ActionTemplateExpansionFunction.java
@@ -13,17 +13,20 @@
 // limitations under the License.
 package com.google.devtools.build.lib.skyframe;
 
+import com.google.common.base.Supplier;
 import com.google.common.collect.ImmutableList;
 import com.google.devtools.build.lib.actions.Action;
 import com.google.devtools.build.lib.actions.ActionAnalysisMetadata;
+import com.google.devtools.build.lib.actions.ActionLookupValue;
 import com.google.devtools.build.lib.actions.Actions;
-import com.google.devtools.build.lib.actions.Artifact;
+import com.google.devtools.build.lib.actions.Actions.GeneratingActions;
 import com.google.devtools.build.lib.actions.Artifact.TreeFileArtifact;
 import com.google.devtools.build.lib.actions.ArtifactPrefixConflictException;
 import com.google.devtools.build.lib.actions.MutableActionGraph.ActionConflictException;
 import com.google.devtools.build.lib.analysis.actions.ActionTemplate;
 import com.google.devtools.build.lib.events.Event;
 import com.google.devtools.build.lib.skyframe.ActionTemplateExpansionValue.ActionTemplateExpansionKey;
+import com.google.devtools.build.lib.util.Preconditions;
 import com.google.devtools.build.skyframe.SkyFunction;
 import com.google.devtools.build.skyframe.SkyFunctionException;
 import com.google.devtools.build.skyframe.SkyKey;
@@ -39,6 +42,11 @@ import javax.annotation.Nullable;
  * input TreeArtifact.
  */
 public class ActionTemplateExpansionFunction implements SkyFunction {
+  private final Supplier<Boolean> removeActionsAfterEvaluation;
+
+  ActionTemplateExpansionFunction(Supplier<Boolean> removeActionsAfterEvaluation) {
+    this.removeActionsAfterEvaluation = Preconditions.checkNotNull(removeActionsAfterEvaluation);
+  }
 
   @Override
   public SkyValue compute(SkyKey skyKey, Environment env)
@@ -71,7 +79,7 @@ public class ActionTemplateExpansionFunction implements SkyFunction {
       throw new ActionTemplateExpansionFunctionException(e);
     }
 
-    return new ActionTemplateExpansionValue(expandedActions);
+    return new ActionTemplateExpansionValue(expandedActions, removeActionsAfterEvaluation.get());
   }
 
   /** Exception thrown by {@link ActionTemplateExpansionFunction}. */
@@ -85,12 +93,14 @@ public class ActionTemplateExpansionFunction implements SkyFunction {
     }
   }
 
-  private static void checkActionAndArtifactConflicts(Iterable<Action> actions)
-      throws ActionConflictException,  ArtifactPrefixConflictException {
-    Map<Artifact, ActionAnalysisMetadata> generatingActions =
+  private void checkActionAndArtifactConflicts(Iterable<Action> actions)
+      throws ActionConflictException, ArtifactPrefixConflictException {
+    GeneratingActions generatingActions =
         Actions.findAndThrowActionConflict(ImmutableList.<ActionAnalysisMetadata>copyOf(actions));
     Map<ActionAnalysisMetadata, ArtifactPrefixConflictException> artifactPrefixConflictMap =
-        Actions.findArtifactPrefixConflicts(generatingActions);
+        Actions.findArtifactPrefixConflicts(
+            ActionLookupValue.getMapForConsistencyCheck(
+                generatingActions.getGeneratingActionIndex(), generatingActions.getActions()));
 
     if (!artifactPrefixConflictMap.isEmpty()) {
       throw artifactPrefixConflictMap.values().iterator().next();
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ActionTemplateExpansionValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/ActionTemplateExpansionValue.java
index 0ac6e600fe..22e9b7f631 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ActionTemplateExpansionValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ActionTemplateExpansionValue.java
@@ -16,9 +16,9 @@ package com.google.devtools.build.lib.skyframe;
 import com.google.common.collect.ImmutableList;
 import com.google.devtools.build.lib.actions.Action;
 import com.google.devtools.build.lib.actions.ActionAnalysisMetadata;
+import com.google.devtools.build.lib.actions.ActionLookupValue;
 import com.google.devtools.build.lib.analysis.actions.ActionTemplate;
 import com.google.devtools.build.lib.cmdline.Label;
-import com.google.devtools.build.lib.skyframe.ActionLookupValue.ActionLookupKey;
 import com.google.devtools.build.lib.util.Preconditions;
 import com.google.devtools.build.skyframe.SkyFunctionName;
 import com.google.devtools.build.skyframe.SkyKey;
@@ -27,15 +27,12 @@ import com.google.devtools.build.skyframe.SkyKey;
  * Value that stores expanded actions from ActionTemplate.
  */
 public final class ActionTemplateExpansionValue extends ActionLookupValue {
-  private final Iterable<Action> expandedActions;
 
-  ActionTemplateExpansionValue(Iterable<Action> expandedActions) {
-    super(ImmutableList.<ActionAnalysisMetadata>copyOf(expandedActions));
-    this.expandedActions = ImmutableList.copyOf(expandedActions);
-  }
-
-  Iterable<Action> getExpandedActions() {
-    return expandedActions;
+  ActionTemplateExpansionValue(
+      Iterable<Action> expandedActions, boolean removeActionsAfterEvaluation) {
+    super(
+        ImmutableList.<ActionAnalysisMetadata>copyOf(expandedActions),
+        removeActionsAfterEvaluation);
   }
 
   static SkyKey key(ActionTemplate<?> actionTemplate) {
@@ -62,7 +59,7 @@ public final class ActionTemplateExpansionValue extends ActionLookupValue {
     }
 
     @Override
-    SkyFunctionName getType() {
+    protected SkyFunctionName getType() {
       return SkyFunctions.ACTION_TEMPLATE_EXPANSION;
     }
 
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ArtifactFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/ArtifactFunction.java
index 293f53083b..0020c3a3cd 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ArtifactFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ArtifactFunction.java
@@ -13,6 +13,8 @@
 // limitations under the License.
 package com.google.devtools.build.lib.skyframe;
 
+import com.google.common.annotations.VisibleForTesting;
+import com.google.common.base.Function;
 import com.google.common.base.Predicate;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
@@ -20,7 +22,8 @@ import com.google.common.collect.Iterables;
 import com.google.devtools.build.lib.actions.Action;
 import com.google.devtools.build.lib.actions.ActionAnalysisMetadata;
 import com.google.devtools.build.lib.actions.ActionAnalysisMetadata.MiddlemanType;
-import com.google.devtools.build.lib.actions.ActionExecutionException;
+import com.google.devtools.build.lib.actions.ActionLookupValue;
+import com.google.devtools.build.lib.actions.ActionLookupValue.ActionLookupKey;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.actions.Artifact.TreeFileArtifact;
 import com.google.devtools.build.lib.actions.ArtifactOwner;
@@ -29,7 +32,6 @@ import com.google.devtools.build.lib.analysis.actions.ActionTemplate;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.events.Event;
 import com.google.devtools.build.lib.events.EventHandler;
-import com.google.devtools.build.lib.skyframe.ActionLookupValue.ActionLookupKey;
 import com.google.devtools.build.lib.skyframe.ArtifactSkyKey.OwnedArtifact;
 import com.google.devtools.build.lib.util.Pair;
 import com.google.devtools.build.lib.util.Preconditions;
@@ -42,7 +44,10 @@ import com.google.devtools.build.skyframe.SkyFunctionException.Transience;
 import com.google.devtools.build.skyframe.SkyKey;
 import com.google.devtools.build.skyframe.SkyValue;
 import java.io.IOException;
+import java.util.ArrayList;
+import java.util.List;
 import java.util.Map;
+import javax.annotation.Nullable;
 
 /** A builder of values for {@link ArtifactSkyKey} keys. */
 class ArtifactFunction implements SkyFunction {
@@ -69,69 +74,90 @@ class ArtifactFunction implements SkyFunction {
       }
     }
 
-    ActionAnalysisMetadata actionMetadata = extractActionFromArtifact(artifact, env);
-    if (actionMetadata == null) {
+    SkyKey actionLookupKey = getActionLookupKey(artifact);
+    ActionLookupValue actionLookupValue = getActionLookupValue(actionLookupKey, env, artifact);
+    if (actionLookupValue == null) {
       return null;
     }
+    Integer actionIndex = actionLookupValue.getGeneratingActionIndex(artifact);
+    if (artifact.hasParent() && actionIndex == null) {
+      // If a TreeFileArtifact is created by a templated action, then it should have the proper
+      // reference to its owner. However, if it was created as part of a directory, by the first
+      // TreeArtifact-generating action in a chain, then its parent's generating action also
+      // generated it. This catches that case.
+      actionIndex = actionLookupValue.getGeneratingActionIndex(artifact.getParent());
+    }
+    Preconditions.checkNotNull(
+        actionIndex, "%s %s %s", artifact, actionLookupKey, actionLookupValue);
 
     // If the action is an ActionTemplate, we need to expand the ActionTemplate into concrete
     // actions, execute those actions in parallel and then aggregate the action execution results.
-    if (artifact.isTreeArtifact() && actionMetadata instanceof ActionTemplate) {
-      // Create the directory structures for the output TreeArtifact first.
-      try {
-        FileSystemUtils.createDirectoryAndParents(artifact.getPath());
-      } catch (IOException e) {
-        env.getListener().handle(
-            Event.error(
-                String.format(
-                    "Failed to create output directory for TreeArtifact %s: %s",
-                    artifact,
-                    e.getMessage())));
-        throw new ArtifactFunctionException(e, Transience.TRANSIENT);
-      }
-
-      return createTreeArtifactValueFromActionTemplate(
-          (ActionTemplate) actionMetadata, artifact, env);
-    } else {
-      Preconditions.checkState(
-          actionMetadata instanceof Action,
-          "%s is not a proper Action object and therefore cannot be executed",
-          actionMetadata);
-      Action action = (Action) actionMetadata;
-      ActionExecutionValue actionValue =
-        (ActionExecutionValue) env.getValue(ActionExecutionValue.key(action));
-      if (actionValue == null) {
-        return null;
+    if (artifact.isTreeArtifact()) {
+      ActionAnalysisMetadata actionMetadata =
+          actionLookupValue.getIfPresentAndNotAction(actionIndex);
+      if (actionMetadata instanceof ActionTemplate) {
+        // Create the directory structures for the output TreeArtifact first.
+        try {
+          FileSystemUtils.createDirectoryAndParents(artifact.getPath());
+        } catch (IOException e) {
+          env.getListener()
+              .handle(
+                  Event.error(
+                      String.format(
+                          "Failed to create output directory for TreeArtifact %s: %s",
+                          artifact, e.getMessage())));
+          throw new ArtifactFunctionException(e, Transience.TRANSIENT);
+        }
+
+        return createTreeArtifactValueFromActionTemplate(
+            (ActionTemplate) actionMetadata, artifact, env);
       }
+    }
+    ActionExecutionValue actionValue =
+        (ActionExecutionValue) env.getValue(ActionExecutionValue.key(actionLookupKey, actionIndex));
+    if (actionValue == null) {
+      return null;
+    }
 
-      if (artifact.isTreeArtifact()) {
-        // We get a request for the whole tree artifact. We can just return the associated
-        // TreeArtifactValue.
-        return Preconditions.checkNotNull(actionValue.getTreeArtifactValue(artifact), artifact);
-      } else if (isAggregatingValue(action)) {
+    if (artifact.isTreeArtifact()) {
+      // We get a request for the whole tree artifact. We can just return the associated
+      // TreeArtifactValue.
+      return Preconditions.checkNotNull(actionValue.getTreeArtifactValue(artifact), artifact);
+    }
+    if (artifact.isMiddlemanArtifact()) {
+      Action action =
+          Preconditions.checkNotNull(
+              actionLookupValue.getAction(actionIndex),
+              "Null middleman action? %s %s %s %s",
+              artifact,
+              actionLookupKey,
+              actionLookupValue,
+              actionIndex);
+      if (isAggregatingValue(action)) {
         return createAggregatingValue(artifact, action,
             actionValue.getArtifactValue(artifact), env);
-      } else {
-        return createSimpleFileArtifactValue(artifact, actionValue);
       }
     }
+    return createSimpleFileArtifactValue(artifact, actionValue);
   }
 
   private static TreeArtifactValue createTreeArtifactValueFromActionTemplate(
-      ActionTemplate actionTemplate, Artifact treeArtifact, Environment env)
+      final ActionTemplate actionTemplate, final Artifact treeArtifact, Environment env)
       throws ArtifactFunctionException, InterruptedException {
     // Request the list of expanded actions from the ActionTemplate.
-    ActionTemplateExpansionValue expansionValue = (ActionTemplateExpansionValue) env.getValue(
-        ActionTemplateExpansionValue.key(actionTemplate));
+    SkyKey templateKey = ActionTemplateExpansionValue.key(actionTemplate);
+    ActionTemplateExpansionValue expansionValue =
+        (ActionTemplateExpansionValue) env.getValue(templateKey);
 
     // The expanded actions are not yet available.
     if (env.valuesMissing()) {
       return null;
     }
 
-    // Execute the expanded actions in parallel.
-    Iterable<SkyKey> expandedActionExecutionKeys = ActionExecutionValue.keys(
-        expansionValue.getExpandedActions());
+    List<SkyKey> expandedActionExecutionKeys = new ArrayList<>(expansionValue.getNumActions());
+    for (int i = 0; i < expansionValue.getNumActions(); i++) {
+      expandedActionExecutionKeys.add(ActionExecutionValue.key(templateKey, i));
+    }
     Map<SkyKey, SkyValue> expandedActionValueMap = env.getValues(expandedActionExecutionKeys);
 
     // The execution values of the expanded actions are not yet all available.
@@ -142,18 +168,45 @@ class ArtifactFunction implements SkyFunction {
     // Aggregate the ArtifactValues for individual TreeFileArtifacts into a TreeArtifactValue for
     // the parent TreeArtifact.
     ImmutableMap.Builder<TreeFileArtifact, FileArtifactValue> map = ImmutableMap.builder();
-    for (Map.Entry<SkyKey, SkyValue> entry : expandedActionValueMap.entrySet()) {
-      SkyKey expandedActionExecutionKey = entry.getKey();
-      ActionExecutionValue actionExecutionValue = (ActionExecutionValue) entry.getValue();
-      Action expandedAction = (Action) expandedActionExecutionKey.argument();
-
-      Iterable<TreeFileArtifact> treeFileArtifacts = findActionOutputsWithMatchingParent(
-          expandedAction, treeArtifact);
+    for (int i = 0; i < expansionValue.getNumActions(); i++) {
+      final ActionExecutionValue actionExecutionValue =
+          (ActionExecutionValue)
+              Preconditions.checkNotNull(
+                  expandedActionValueMap.get(expandedActionExecutionKeys.get(i)),
+                  "Missing tree value: %s %s %s %s %s",
+                  treeArtifact,
+                  actionTemplate,
+                  expansionValue,
+                  expandedActionValueMap,
+                  expandedActionExecutionKeys);
+      Iterable<TreeFileArtifact> treeFileArtifacts =
+          Iterables.transform(
+              Iterables.filter(
+                  actionExecutionValue.getAllFileValues().keySet(),
+                  new Predicate<Artifact>() {
+                    @Override
+                    public boolean apply(Artifact artifact) {
+                      Preconditions.checkState(
+                          artifact.hasParent(),
+                          "No parent: %s %s %s %s",
+                          artifact,
+                          treeArtifact,
+                          actionExecutionValue,
+                          actionTemplate);
+                      return artifact.getParent().equals(treeArtifact);
+                    }
+                  }),
+              new Function<Artifact, TreeFileArtifact>() {
+                @Override
+                public TreeFileArtifact apply(Artifact artifact) {
+                  return (TreeFileArtifact) artifact;
+                }
+              });
 
       Preconditions.checkState(
           !Iterables.isEmpty(treeFileArtifacts),
-          "Action %s does not output TreeFileArtifact under %s",
-          expandedAction,
+          "Action denoted by %s does not output TreeFileArtifact under %s",
+          expandedActionExecutionKeys.get(i),
           treeArtifact);
 
       for (TreeFileArtifact treeFileArtifact : treeFileArtifacts) {
@@ -281,48 +334,30 @@ class ArtifactFunction implements SkyFunction {
     return Label.print(((OwnedArtifact) skyKey.argument()).getArtifact().getOwner());
   }
 
-  private static ActionAnalysisMetadata extractActionFromArtifact(
-      Artifact artifact, SkyFunction.Environment env) throws InterruptedException {
+  @VisibleForTesting
+  static SkyKey getActionLookupKey(Artifact artifact) {
     ArtifactOwner artifactOwner = artifact.getArtifactOwner();
 
     Preconditions.checkState(artifactOwner instanceof ActionLookupKey, "", artifact, artifactOwner);
-    SkyKey actionLookupKey = ActionLookupValue.key((ActionLookupKey) artifactOwner);
+    return ActionLookupValue.key((ActionLookupKey) artifactOwner);
+  }
+
+  @Nullable
+  private static ActionLookupValue getActionLookupValue(
+      SkyKey actionLookupKey, SkyFunction.Environment env, Artifact artifact)
+      throws InterruptedException {
     ActionLookupValue value = (ActionLookupValue) env.getValue(actionLookupKey);
     if (value == null) {
-      Preconditions.checkState(artifactOwner == CoverageReportValue.ARTIFACT_OWNER,
-          "Not-yet-present artifact owner: %s", artifactOwner);
+      ArtifactOwner artifactOwner = artifact.getArtifactOwner();
+      Preconditions.checkState(
+          artifactOwner == CoverageReportValue.ARTIFACT_OWNER,
+          "Not-yet-present artifact owner: %s (%s %s)",
+          artifactOwner,
+          artifact,
+          actionLookupKey);
       return null;
     }
-    // The value should already exist (except for the coverage report action output artifacts):
-    // ConfiguredTargetValues were created during the analysis phase, and BuildInfo*Values
-    // were created during the first analysis of a configured target.
-    Preconditions.checkNotNull(value,
-        "Owner %s of %s not in graph %s", artifactOwner, artifact, actionLookupKey);
-
-    ActionAnalysisMetadata action = value.getGeneratingAction(artifact);
-    if (artifact.hasParent()) {
-      // We are trying to resolve the generating action for a TreeFileArtifact. It may not have
-      // a generating action in the action graph at analysis time. In that case, we get the
-      // generating action for its parent TreeArtifact, which contains this TreeFileArtifact.
-      if (action == null) {
-        action = value.getGeneratingAction(artifact.getParent());
-      }
-    }
-
-    return Preconditions.checkNotNull(action,
-        "Value %s does not contain generating action of %s", value, artifact);
-  }
-
-  private static Iterable<TreeFileArtifact> findActionOutputsWithMatchingParent(
-      Action action, Artifact treeArtifact) {
-    ImmutableList.Builder<TreeFileArtifact> matchingOutputs = ImmutableList.builder();
-    for (Artifact output : action.getOutputs()) {
-      Preconditions.checkState(output.hasParent(), "%s must be a TreeFileArtifact", output);
-      if (output.getParent().equals(treeArtifact)) {
-        matchingOutputs.add((TreeFileArtifact) output);
-      }
-    }
-    return matchingOutputs.build();
+    return value;
   }
 
   private static final class ArtifactFunctionException extends SkyFunctionException {
@@ -330,10 +365,6 @@ class ArtifactFunction implements SkyFunction {
       super(e, transience);
     }
 
-    ArtifactFunctionException(ActionExecutionException e, Transience transience) {
-      super(e, transience);
-    }
-
     ArtifactFunctionException(IOException e, Transience transience) {
       super(e, transience);
     }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/AspectFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/AspectFunction.java
index 8437ab91bf..2873ad1143 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/AspectFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/AspectFunction.java
@@ -14,9 +14,11 @@
 
 package com.google.devtools.build.lib.skyframe;
 
+import com.google.common.base.Supplier;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
 import com.google.devtools.build.lib.actions.ActionAnalysisMetadata;
+import com.google.devtools.build.lib.actions.ActionLookupValue;
 import com.google.devtools.build.lib.analysis.CachingAnalysisEnvironment;
 import com.google.devtools.build.lib.analysis.ConfiguredAspect;
 import com.google.devtools.build.lib.analysis.ConfiguredAspectFactory;
@@ -87,10 +89,15 @@ import javax.annotation.Nullable;
 public final class AspectFunction implements SkyFunction {
   private final BuildViewProvider buildViewProvider;
   private final RuleClassProvider ruleClassProvider;
+  private final Supplier<Boolean> removeActionsAfterEvaluation;
 
-  public AspectFunction(BuildViewProvider buildViewProvider, RuleClassProvider ruleClassProvider) {
+  AspectFunction(
+      BuildViewProvider buildViewProvider,
+      RuleClassProvider ruleClassProvider,
+      Supplier<Boolean> removeActionsAfterEvaluation) {
     this.buildViewProvider = buildViewProvider;
     this.ruleClassProvider = ruleClassProvider;
+    this.removeActionsAfterEvaluation = Preconditions.checkNotNull(removeActionsAfterEvaluation);
   }
 
   /**
@@ -368,12 +375,13 @@ public final class AspectFunction implements SkyFunction {
       buildSkyKeys(baseKey, result);
     }
   }
-  private static SkyValue createAliasAspect(
+  private SkyValue createAliasAspect(
       Environment env,
       Target originalTarget,
       Aspect aspect,
       AspectKey originalKey,
-      ConfiguredTarget configuredTarget) throws InterruptedException {
+      ConfiguredTarget configuredTarget)
+      throws InterruptedException {
     ImmutableList<Label> aliasChain = configuredTarget.getProvider(AliasProvider.class)
         .getAliasChain();
     // Find the next alias in the chain: either the next alias (if there are two) or the name of
@@ -401,7 +409,8 @@ public final class AspectFunction implements SkyFunction {
         originalTarget.getLocation(),
         ConfiguredAspect.forAlias(real.getConfiguredAspect()),
         ImmutableList.<ActionAnalysisMetadata>of(),
-        transitivePackages);
+        transitivePackages,
+        removeActionsAfterEvaluation.get());
   }
 
   @Nullable
@@ -466,7 +475,8 @@ public final class AspectFunction implements SkyFunction {
         associatedTarget.getTarget().getLocation(),
         configuredAspect,
         ImmutableList.copyOf(analysisEnvironment.getRegisteredActions()),
-        transitivePackages.build());
+        transitivePackages.build(),
+        removeActionsAfterEvaluation.get());
   }
 
   @Override
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/AspectValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/AspectValue.java
index 25d38737d5..0656d45dfb 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/AspectValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/AspectValue.java
@@ -18,6 +18,7 @@ import com.google.common.base.Objects;
 import com.google.common.base.Preconditions;
 import com.google.common.collect.ImmutableList;
 import com.google.devtools.build.lib.actions.ActionAnalysisMetadata;
+import com.google.devtools.build.lib.actions.ActionLookupValue;
 import com.google.devtools.build.lib.analysis.ConfiguredAspect;
 import com.google.devtools.build.lib.analysis.config.BuildConfiguration;
 import com.google.devtools.build.lib.cmdline.Label;
@@ -30,6 +31,7 @@ import com.google.devtools.build.lib.packages.AspectParameters;
 import com.google.devtools.build.lib.packages.Package;
 import com.google.devtools.build.lib.syntax.SkylarkImport;
 import com.google.devtools.build.skyframe.SkyFunctionName;
+import java.util.List;
 import javax.annotation.Nullable;
 
 /**
@@ -68,7 +70,7 @@ public final class AspectValue extends ActionLookupValue {
     }
 
     @Override
-    SkyFunctionName getType() {
+    protected SkyFunctionName getType() {
       return SkyFunctions.ASPECT;
     }
 
@@ -240,7 +242,7 @@ public final class AspectValue extends ActionLookupValue {
     }
 
     @Override
-    SkyFunctionName getType() {
+    protected SkyFunctionName getType() {
       return SkyFunctions.LOAD_SKYLARK_ASPECT;
     }
 
@@ -321,9 +323,10 @@ public final class AspectValue extends ActionLookupValue {
       Label label,
       Location location,
       ConfiguredAspect configuredAspect,
-      Iterable<ActionAnalysisMetadata> actions,
-      NestedSet<Package> transitivePackages) {
-    super(actions);
+      List<ActionAnalysisMetadata> actions,
+      NestedSet<Package> transitivePackages,
+      boolean removeActionsAfterEvaluation) {
+    super(actions, removeActionsAfterEvaluation);
     this.label = Preconditions.checkNotNull(label, actions);
     this.aspect = Preconditions.checkNotNull(aspect, label);
     this.location = Preconditions.checkNotNull(location, label);
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/BuildInfoCollectionFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/BuildInfoCollectionFunction.java
index 73b28549dd..79011a82a9 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/BuildInfoCollectionFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/BuildInfoCollectionFunction.java
@@ -23,6 +23,7 @@ import com.google.devtools.build.lib.analysis.buildinfo.BuildInfoFactory.BuildIn
 import com.google.devtools.build.lib.analysis.buildinfo.BuildInfoFactory.BuildInfoType;
 import com.google.devtools.build.lib.cmdline.RepositoryName;
 import com.google.devtools.build.lib.skyframe.BuildInfoCollectionValue.BuildInfoKeyAndConfig;
+import com.google.devtools.build.lib.util.Preconditions;
 import com.google.devtools.build.lib.vfs.PathFragment;
 import com.google.devtools.build.skyframe.SkyFunction;
 import com.google.devtools.build.skyframe.SkyKey;
@@ -37,9 +38,12 @@ import java.util.Map;
 public class BuildInfoCollectionFunction implements SkyFunction {
   // Supplier only because the artifact factory has not yet been created at constructor time.
   private final Supplier<ArtifactFactory> artifactFactory;
+  private final Supplier<Boolean> removeActionsAfterEvaluation;
 
-  BuildInfoCollectionFunction(Supplier<ArtifactFactory> artifactFactory) {
+  BuildInfoCollectionFunction(
+      Supplier<ArtifactFactory> artifactFactory, Supplier<Boolean> removeActionsAfterEvaluation) {
     this.artifactFactory = artifactFactory;
+    this.removeActionsAfterEvaluation = Preconditions.checkNotNull(removeActionsAfterEvaluation);
   }
 
   @Override
@@ -73,9 +77,16 @@ public class BuildInfoCollectionFunction implements SkyFunction {
       }
     };
 
-    return new BuildInfoCollectionValue(buildInfoFactories.get(keyAndConfig.getInfoKey()).create(
-        context, keyAndConfig.getConfig(), infoArtifactValue.getStableArtifact(),
-        infoArtifactValue.getVolatileArtifact(), repositoryName));
+    return new BuildInfoCollectionValue(
+        buildInfoFactories
+            .get(keyAndConfig.getInfoKey())
+            .create(
+                context,
+                keyAndConfig.getConfig(),
+                infoArtifactValue.getStableArtifact(),
+                infoArtifactValue.getVolatileArtifact(),
+                repositoryName),
+        removeActionsAfterEvaluation.get());
   }
 
   @Override
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/BuildInfoCollectionValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/BuildInfoCollectionValue.java
index 05d6a7e93f..ee00e641ab 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/BuildInfoCollectionValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/BuildInfoCollectionValue.java
@@ -13,13 +13,13 @@
 // limitations under the License.
 package com.google.devtools.build.lib.skyframe;
 
+import com.google.devtools.build.lib.actions.ActionLookupValue;
 import com.google.devtools.build.lib.analysis.buildinfo.BuildInfoCollection;
 import com.google.devtools.build.lib.analysis.buildinfo.BuildInfoFactory;
 import com.google.devtools.build.lib.analysis.config.BuildConfiguration;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.util.Preconditions;
 import com.google.devtools.build.skyframe.SkyFunctionName;
-
 import java.util.Objects;
 
 /**
@@ -29,8 +29,8 @@ import java.util.Objects;
 public class BuildInfoCollectionValue extends ActionLookupValue {
   private final BuildInfoCollection collection;
 
-  BuildInfoCollectionValue(BuildInfoCollection collection) {
-    super(collection.getActions());
+  BuildInfoCollectionValue(BuildInfoCollection collection, boolean removeActionsAfterEvaluation) {
+    super(collection.getActions(), removeActionsAfterEvaluation);
     this.collection = collection;
   }
 
@@ -40,9 +40,7 @@ public class BuildInfoCollectionValue extends ActionLookupValue {
 
   @Override
   public String toString() {
-    return com.google.common.base.MoreObjects.toStringHelper(getClass())
-        .add("collection", collection)
-        .add("generatingActionMap", generatingActionMap).toString();
+    return getStringHelper().add("collection", collection).toString();
   }
 
   /** Key for BuildInfoCollectionValues. */
@@ -56,7 +54,7 @@ public class BuildInfoCollectionValue extends ActionLookupValue {
     }
 
     @Override
-    SkyFunctionName getType() {
+    protected SkyFunctionName getType() {
       return SkyFunctions.BUILD_INFO_COLLECTION;
     }
 
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ConfiguredTargetFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/ConfiguredTargetFunction.java
index b0eaf3c0a1..d79f0dbf4c 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ConfiguredTargetFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ConfiguredTargetFunction.java
@@ -17,6 +17,7 @@ import com.google.common.annotations.VisibleForTesting;
 import com.google.common.base.Function;
 import com.google.common.base.Joiner;
 import com.google.common.base.Predicate;
+import com.google.common.base.Supplier;
 import com.google.common.base.Verify;
 import com.google.common.base.VerifyException;
 import com.google.common.collect.ImmutableList;
@@ -27,9 +28,8 @@ import com.google.common.collect.LinkedListMultimap;
 import com.google.common.collect.Maps;
 import com.google.common.collect.Multimap;
 import com.google.common.collect.Sets;
-import com.google.devtools.build.lib.actions.ActionAnalysisMetadata;
 import com.google.devtools.build.lib.actions.Actions;
-import com.google.devtools.build.lib.actions.Artifact;
+import com.google.devtools.build.lib.actions.Actions.GeneratingActions;
 import com.google.devtools.build.lib.actions.MutableActionGraph.ActionConflictException;
 import com.google.devtools.build.lib.analysis.AspectCollection;
 import com.google.devtools.build.lib.analysis.AspectCollection.AspectDeps;
@@ -143,14 +143,17 @@ final class ConfiguredTargetFunction implements SkyFunction {
   private final BuildViewProvider buildViewProvider;
   private final RuleClassProvider ruleClassProvider;
   private final Semaphore cpuBoundSemaphore;
+  private final Supplier<Boolean> removeActionsAfterEvaluation;
 
   ConfiguredTargetFunction(
       BuildViewProvider buildViewProvider,
       RuleClassProvider ruleClassProvider,
-      Semaphore cpuBoundSemaphore) {
+      Semaphore cpuBoundSemaphore,
+      Supplier<Boolean> removeActionsAfterEvaluation) {
     this.buildViewProvider = buildViewProvider;
     this.ruleClassProvider = ruleClassProvider;
     this.cpuBoundSemaphore = cpuBoundSemaphore;
+    this.removeActionsAfterEvaluation = Preconditions.checkNotNull(removeActionsAfterEvaluation);
   }
 
   private static boolean useDynamicConfigurations(BuildConfiguration config) {
@@ -1141,7 +1144,7 @@ final class ConfiguredTargetFunction implements SkyFunction {
     analysisEnvironment.disable(target);
     Preconditions.checkNotNull(configuredTarget, target);
 
-    ImmutableMap<Artifact, ActionAnalysisMetadata> generatingActions;
+    GeneratingActions generatingActions;
     // Check for conflicting actions within this configured target (that indicates a bug in the
     // rule implementation).
     try {
@@ -1151,7 +1154,10 @@ final class ConfiguredTargetFunction implements SkyFunction {
       throw new ConfiguredTargetFunctionException(e);
     }
     return new ConfiguredTargetValue(
-        configuredTarget, generatingActions, transitivePackages.build());
+        configuredTarget,
+        generatingActions,
+        transitivePackages.build(),
+        removeActionsAfterEvaluation.get());
   }
 
   /**
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ConfiguredTargetKey.java b/src/main/java/com/google/devtools/build/lib/skyframe/ConfiguredTargetKey.java
index f28ffbf5a2..78459b4ad2 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ConfiguredTargetKey.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ConfiguredTargetKey.java
@@ -14,6 +14,7 @@
 
 package com.google.devtools.build.lib.skyframe;
 
+import com.google.devtools.build.lib.actions.ActionLookupValue.ActionLookupKey;
 import com.google.devtools.build.lib.analysis.ConfiguredTarget;
 import com.google.devtools.build.lib.analysis.config.BuildConfiguration;
 import com.google.devtools.build.lib.cmdline.Label;
@@ -23,12 +24,12 @@ import java.util.Objects;
 import javax.annotation.Nullable;
 
 /**
- *  A (Label, Configuration) pair. Note that this pair may be used to look up the generating action
+ * A (Label, Configuration) pair. Note that this pair may be used to look up the generating action
  * of an artifact. Callers may want to ensure that they have the correct configuration for this
  * purpose by passing in {@link BuildConfiguration#getArtifactOwnerConfiguration} in preference to
  * the raw configuration.
  */
-public class ConfiguredTargetKey extends ActionLookupValue.ActionLookupKey {
+public class ConfiguredTargetKey extends ActionLookupKey {
   private final Label label;
   @Nullable
   private final BuildConfiguration configuration;
@@ -48,7 +49,7 @@ public class ConfiguredTargetKey extends ActionLookupValue.ActionLookupKey {
   }
 
   @Override
-  SkyFunctionName getType() {
+  protected SkyFunctionName getType() {
     return SkyFunctions.CONFIGURED_TARGET;
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ConfiguredTargetValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/ConfiguredTargetValue.java
index 110957009f..2c2bb3deb2 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ConfiguredTargetValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ConfiguredTargetValue.java
@@ -15,9 +15,9 @@ package com.google.devtools.build.lib.skyframe;
 
 import com.google.common.annotations.VisibleForTesting;
 import com.google.common.collect.ImmutableList;
-import com.google.common.collect.Iterables;
 import com.google.devtools.build.lib.actions.ActionAnalysisMetadata;
-import com.google.devtools.build.lib.actions.Artifact;
+import com.google.devtools.build.lib.actions.ActionLookupValue;
+import com.google.devtools.build.lib.actions.Actions.GeneratingActions;
 import com.google.devtools.build.lib.analysis.ConfiguredTarget;
 import com.google.devtools.build.lib.analysis.config.BuildConfiguration;
 import com.google.devtools.build.lib.cmdline.Label;
@@ -27,7 +27,7 @@ import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
 import com.google.devtools.build.lib.packages.Package;
 import com.google.devtools.build.lib.util.Preconditions;
 import com.google.devtools.build.skyframe.SkyKey;
-import java.util.Map;
+import java.util.List;
 import javax.annotation.Nullable;
 
 /**
@@ -44,12 +44,14 @@ public final class ConfiguredTargetValue extends ActionLookupValue {
 
   @Nullable private NestedSet<Package> transitivePackages;
 
-  ConfiguredTargetValue(ConfiguredTarget configuredTarget,
-      Map<Artifact, ActionAnalysisMetadata> generatingActionMap,
-      NestedSet<Package> transitivePackages) {
-    super(generatingActionMap);
-    this.configuredTarget = Preconditions.checkNotNull(configuredTarget, generatingActionMap);
-    this.transitivePackages = Preconditions.checkNotNull(transitivePackages, generatingActionMap);
+  ConfiguredTargetValue(
+      ConfiguredTarget configuredTarget,
+      GeneratingActions generatingActions,
+      NestedSet<Package> transitivePackages,
+      boolean removeActionsAfterEvaluation) {
+    super(generatingActions, removeActionsAfterEvaluation);
+    this.configuredTarget = Preconditions.checkNotNull(configuredTarget, generatingActions);
+    this.transitivePackages = Preconditions.checkNotNull(transitivePackages, generatingActions);
   }
 
   @VisibleForTesting
@@ -59,9 +61,9 @@ public final class ConfiguredTargetValue extends ActionLookupValue {
   }
 
   @VisibleForTesting
-  public Iterable<ActionAnalysisMetadata> getActions() {
-    Preconditions.checkNotNull(configuredTarget);
-    return generatingActionMap.values();
+  public List<ActionAnalysisMetadata> getActions() {
+    Preconditions.checkNotNull(configuredTarget, this);
+    return actions;
   }
 
   public NestedSet<Package> getTransitivePackages() {
@@ -114,7 +116,6 @@ public final class ConfiguredTargetValue extends ActionLookupValue {
 
   @Override
   public String toString() {
-    return "ConfiguredTargetValue: " + configuredTarget + ", actions: "
-        + (configuredTarget == null ? null : Iterables.toString(getActions()));
+    return getStringHelper().add("configuredTarget", configuredTarget).toString();
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/CoverageReportFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/CoverageReportFunction.java
index 47ce1774c7..f31e21c5e1 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/CoverageReportFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/CoverageReportFunction.java
@@ -14,6 +14,7 @@
 
 package com.google.devtools.build.lib.skyframe;
 
+import com.google.common.base.Supplier;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableSet;
 import com.google.devtools.build.lib.actions.ActionAnalysisMetadata;
@@ -27,7 +28,11 @@ import com.google.devtools.build.skyframe.SkyValue;
  * A Skyframe function to calculate the coverage report Action and Artifacts.
  */
 public class CoverageReportFunction implements SkyFunction {
-  CoverageReportFunction() {}
+  private final Supplier<Boolean> removeActionsAfterEvaluation;
+
+  CoverageReportFunction(Supplier<Boolean> removeActionsAfterEvaluation) {
+    this.removeActionsAfterEvaluation = Preconditions.checkNotNull(removeActionsAfterEvaluation);
+  }
 
   @Override
   public SkyValue compute(SkyKey skyKey, Environment env) throws InterruptedException {
@@ -46,7 +51,7 @@ public class CoverageReportFunction implements SkyFunction {
       outputs.addAll(action.getOutputs());
     }
 
-    return new CoverageReportValue(actions);
+    return new CoverageReportValue(actions, removeActionsAfterEvaluation.get());
   }
 
   @Override
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/CoverageReportValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/CoverageReportValue.java
index 164b37e16e..3d63fe04ad 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/CoverageReportValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/CoverageReportValue.java
@@ -16,6 +16,7 @@ package com.google.devtools.build.lib.skyframe;
 
 import com.google.common.collect.ImmutableList;
 import com.google.devtools.build.lib.actions.ActionAnalysisMetadata;
+import com.google.devtools.build.lib.actions.ActionLookupValue;
 import com.google.devtools.build.lib.actions.ArtifactOwner;
 import com.google.devtools.build.skyframe.SkyFunctionName;
 import com.google.devtools.build.skyframe.SkyKey;
@@ -29,18 +30,20 @@ public class CoverageReportValue extends ActionLookupValue {
   public static final ArtifactOwner ARTIFACT_OWNER = new CoverageReportKey();
   static final SkyKey SKY_KEY = SkyKey.create(SkyFunctions.COVERAGE_REPORT, ARTIFACT_OWNER);
 
-  CoverageReportValue(ImmutableList<ActionAnalysisMetadata> coverageReportActions) {
-    super(coverageReportActions);
+  CoverageReportValue(
+      ImmutableList<ActionAnalysisMetadata> coverageReportActions,
+      boolean removeActionsAfterEvaluation) {
+    super(coverageReportActions, removeActionsAfterEvaluation);
   }
 
   private static class CoverageReportKey extends ActionLookupKey {
     @Override
-    SkyFunctionName getType() {
+    protected SkyFunctionName getType() {
       throw new UnsupportedOperationException();
     }
 
     @Override
-    SkyKey getSkyKeyInternal() {
+    protected SkyKey getSkyKeyInternal() {
       return SKY_KEY;
     }
   }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SequencedSkyframeExecutor.java b/src/main/java/com/google/devtools/build/lib/skyframe/SequencedSkyframeExecutor.java
index e48991b97e..aed5573cdf 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SequencedSkyframeExecutor.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SequencedSkyframeExecutor.java
@@ -35,6 +35,7 @@ import com.google.devtools.build.lib.analysis.config.BinTools;
 import com.google.devtools.build.lib.cmdline.PackageIdentifier;
 import com.google.devtools.build.lib.concurrent.Uninterruptibles;
 import com.google.devtools.build.lib.events.ExtendedEventHandler;
+import com.google.devtools.build.lib.exec.ExecutionOptions;
 import com.google.devtools.build.lib.packages.Package;
 import com.google.devtools.build.lib.packages.PackageFactory;
 import com.google.devtools.build.lib.packages.Preprocessor;
@@ -94,9 +95,17 @@ public final class SequencedSkyframeExecutor extends SkyframeExecutor {
 
   private boolean lastAnalysisDiscarded = false;
 
-  // Can only be set once (to false) over the lifetime of this object. If false, the graph will not
-  // store edges, saving memory but making incremental builds impossible.
-  private boolean keepGraphEdges = true;
+  private enum IncrementalState {
+    NORMAL,
+    CLEAR_EDGES,
+    CLEAR_EDGES_AND_ACTIONS
+  }
+
+  // Can only be set once over the lifetime of this object. If CLEAR_EDGES or
+  // CLEAR_EDGES_AND_ACTIONS, the graph will not store edges, saving memory but making incremental
+  // builds impossible. If CLEAR_EDGES_AND_ACTIONS, each action will be dereferenced once it is
+  // executed, saving memory.
+  private IncrementalState incrementalState = IncrementalState.NORMAL;
 
   private RecordingDifferencer recordingDiffer;
   private final DiffAwarenessManager diffAwarenessManager;
@@ -541,24 +550,33 @@ public final class SequencedSkyframeExecutor extends SkyframeExecutor {
   }
 
   @Override
-  public void decideKeepIncrementalState(boolean batch, BuildView.Options viewOptions) {
+  public void decideKeepIncrementalState(
+      boolean batch, BuildView.Options viewOptions, ExecutionOptions executionOptions) {
     Preconditions.checkState(!active);
     if (viewOptions == null) {
       // Some blaze commands don't include the view options. Don't bother with them.
       return;
     }
     if (batch && viewOptions.keepGoing && viewOptions.discardAnalysisCache) {
-      Preconditions.checkState(keepGraphEdges, "May only be called once if successful");
-      keepGraphEdges = false;
+      Preconditions.checkState(
+          incrementalState == IncrementalState.NORMAL,
+          "May only be called once if successful: %s",
+          incrementalState);
+      incrementalState =
+          executionOptions.enableCriticalPathProfiling
+              ? IncrementalState.CLEAR_EDGES
+              : IncrementalState.CLEAR_EDGES_AND_ACTIONS;
       // Graph will be recreated on next sync.
+      LOG.info("Set incremental state to " + incrementalState);
     }
+    removeActionsAfterEvaluation.set(incrementalState == IncrementalState.CLEAR_EDGES_AND_ACTIONS);
   }
 
   @Override
   public boolean hasIncrementalState() {
     // TODO(bazel-team): Combine this method with clearSkyframeRelevantCaches() once legacy
     // execution is removed [skyframe-execution].
-    return keepGraphEdges;
+    return incrementalState == IncrementalState.NORMAL;
   }
 
   @Override
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeActionExecutor.java b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeActionExecutor.java
index 7c353ac3f3..f2eb148f47 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeActionExecutor.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeActionExecutor.java
@@ -35,6 +35,8 @@ import com.google.devtools.build.lib.actions.ActionInput;
 import com.google.devtools.build.lib.actions.ActionInputFileCache;
 import com.google.devtools.build.lib.actions.ActionInputHelper;
 import com.google.devtools.build.lib.actions.ActionLogBufferPathGenerator;
+import com.google.devtools.build.lib.actions.ActionLookupData;
+import com.google.devtools.build.lib.actions.ActionLookupValue;
 import com.google.devtools.build.lib.actions.ActionMiddlemanEvent;
 import com.google.devtools.build.lib.actions.ActionStartedEvent;
 import com.google.devtools.build.lib.actions.ActionStatusMessage;
@@ -122,7 +124,8 @@ public final class SkyframeActionExecutor implements ActionExecutionContextFacto
   // We don't want to execute the action again on the second entry to the SkyFunction.
   // In both cases, we store the already-computed ActionExecutionValue to avoid having to compute it
   // again.
-  private ConcurrentMap<Artifact, Pair<Action, FutureTask<ActionExecutionValue>>> buildActionMap;
+  private ConcurrentMap<Artifact, Pair<ActionLookupData, FutureTask<ActionExecutionValue>>>
+      buildActionMap;
 
   // Errors found when examining all actions in the graph are stored here, so that they can be
   // thrown when execution of the action is requested. This field is set during each call to
@@ -345,10 +348,15 @@ public final class SkyframeActionExecutor implements ActionExecutionContextFacto
     return buildActionMap.containsKey(action.getPrimaryOutput());
   }
 
-  private boolean actionReallyExecuted(Action action) {
-    Pair<Action, ?> cachedRun = Preconditions.checkNotNull(
-        buildActionMap.get(action.getPrimaryOutput()), action);
-    return action == cachedRun.first;
+  private boolean actionReallyExecuted(Action action, ActionLookupData actionLookupData) {
+    Pair<ActionLookupData, ?> cachedRun =
+        Preconditions.checkNotNull(
+            buildActionMap.get(action.getPrimaryOutput()), "%s %s", action, actionLookupData);
+    return actionLookupData.equals(cachedRun.getFirst());
+  }
+
+  void noteActionEvaluationStarted(ActionLookupData actionLookupData, Action action) {
+    this.completionReceiver.noteActionEvaluationStarted(actionLookupData, action);
   }
 
   /**
@@ -357,9 +365,12 @@ public final class SkyframeActionExecutor implements ActionExecutionContextFacto
    *
    * <p>For use from {@link ArtifactFunction} only.
    */
-  ActionExecutionValue executeAction(Action action, ActionMetadataHandler metadataHandler,
+  ActionExecutionValue executeAction(
+      Action action,
+      ActionMetadataHandler metadataHandler,
       long actionStartTime,
-      ActionExecutionContext actionExecutionContext)
+      ActionExecutionContext actionExecutionContext,
+      ActionLookupData actionLookupData)
       throws ActionExecutionException, InterruptedException {
     Exception exception = badActionMap.get(action);
     if (exception != null) {
@@ -368,18 +379,20 @@ public final class SkyframeActionExecutor implements ActionExecutionContextFacto
     }
     Artifact primaryOutput = action.getPrimaryOutput();
     FutureTask<ActionExecutionValue> actionTask =
-        new FutureTask<>(new ActionRunner(action, metadataHandler,
-            actionStartTime, actionExecutionContext));
+        new FutureTask<>(
+            new ActionRunner(
+                action,
+                metadataHandler,
+                actionStartTime,
+                actionExecutionContext,
+                actionLookupData));
     // Check to see if another action is already executing/has executed this value.
-    Pair<Action, FutureTask<ActionExecutionValue>> oldAction =
-        buildActionMap.putIfAbsent(primaryOutput, Pair.of(action, actionTask));
+    Pair<ActionLookupData, FutureTask<ActionExecutionValue>> oldAction =
+        buildActionMap.putIfAbsent(primaryOutput, Pair.of(actionLookupData, actionTask));
 
     if (oldAction == null) {
       actionTask.run();
     } else {
-      Preconditions.checkState(action != oldAction.first, action);
-      Preconditions.checkState(Actions.canBeShared(oldAction.first, action),
-          "Actions cannot be shared: %s %s", oldAction.first, action);
       // Wait for other action to finish, so any actions that depend on its outputs can execute.
       actionTask = oldAction.second;
     }
@@ -395,7 +408,7 @@ public final class SkyframeActionExecutor implements ActionExecutionContextFacto
         // Tell the receiver that the action has completed *before* telling the reporter.
         // This way the latter will correctly show the number of completed actions when task
         // completion messages are enabled (--show_task_finish).
-        completionReceiver.actionCompleted(action);
+        completionReceiver.actionCompleted(actionLookupData);
         reporter.finishTask(null, prependExecPhaseStats(message));
       }
     }
@@ -488,8 +501,12 @@ public final class SkyframeActionExecutor implements ActionExecutionContextFacto
   }
 
   void afterExecution(
-      Action action, MetadataHandler metadataHandler, Token token, Map<String, String> clientEnv) {
-    if (!actionReallyExecuted(action)) {
+      Action action,
+      MetadataHandler metadataHandler,
+      Token token,
+      Map<String, String> clientEnv,
+      ActionLookupData actionLookupData) {
+    if (!actionReallyExecuted(action, actionLookupData)) {
       // If an action shared with this one executed, then we need not update the action cache, since
       // the other action will do it. Moreover, this action is not aware of metadata acquired
       // during execution, so its metadata handler is likely unusable anyway.
@@ -568,14 +585,19 @@ public final class SkyframeActionExecutor implements ActionExecutionContextFacto
     private final ActionMetadataHandler metadataHandler;
     private long actionStartTime;
     private ActionExecutionContext actionExecutionContext;
+    private final ActionLookupData actionLookupData;
 
-    ActionRunner(Action action, ActionMetadataHandler metadataHandler,
+    ActionRunner(
+        Action action,
+        ActionMetadataHandler metadataHandler,
         long actionStartTime,
-        ActionExecutionContext actionExecutionContext) {
+        ActionExecutionContext actionExecutionContext,
+        ActionLookupData actionLookupData) {
       this.action = action;
       this.metadataHandler = metadataHandler;
       this.actionStartTime = actionStartTime;
       this.actionExecutionContext = actionExecutionContext;
+      this.actionLookupData = actionLookupData;
     }
 
     @Override
@@ -601,7 +623,8 @@ public final class SkyframeActionExecutor implements ActionExecutionContextFacto
 
         Preconditions.checkState(actionExecutionContext.getMetadataHandler() == metadataHandler,
             "%s %s", actionExecutionContext.getMetadataHandler(), metadataHandler);
-        prepareScheduleExecuteAndCompleteAction(action, actionExecutionContext, actionStartTime);
+        prepareScheduleExecuteAndCompleteAction(
+            action, actionExecutionContext, actionStartTime, actionLookupData);
         return new ActionExecutionValue(
             metadataHandler.getOutputArtifactData(),
             metadataHandler.getOutputTreeArtifactData(),
@@ -664,23 +687,25 @@ public final class SkyframeActionExecutor implements ActionExecutionContextFacto
   }
 
   /**
-   * Prepare, schedule, execute, and then complete the action.
-   * When this function is called, we know that this action needs to be executed.
-   * This function will prepare for the action's execution (i.e. delete the outputs);
-   * schedule its execution; execute the action;
-   * and then do some post-execution processing to complete the action:
-   * set the outputs readonly and executable, and insert the action results in the
-   * action cache.
+   * Prepare, schedule, execute, and then complete the action. When this function is called, we know
+   * that this action needs to be executed. This function will prepare for the action's execution
+   * (i.e. delete the outputs); schedule its execution; execute the action; and then do some
+   * post-execution processing to complete the action: set the outputs readonly and executable, and
+   * insert the action results in the action cache.
    *
-   * @param action  The action to execute
+   * @param action The action to execute
    * @param context services in the scope of the action
    * @param actionStartTime time when we started the first phase of the action execution.
-   * @throws ActionExecutionException if the execution of the specified action
-   *   failed for any reason.
+   * @param actionLookupData key for action
+   * @throws ActionExecutionException if the execution of the specified action failed for any
+   *     reason.
    * @throws InterruptedException if the thread was interrupted.
    */
-  private void prepareScheduleExecuteAndCompleteAction(Action action,
-      ActionExecutionContext context, long actionStartTime)
+  private void prepareScheduleExecuteAndCompleteAction(
+      Action action,
+      ActionExecutionContext context,
+      long actionStartTime,
+      ActionLookupData actionLookupData)
       throws ActionExecutionException, InterruptedException {
     // Delete the metadataHandler's cache of the action's outputs, since they are being deleted.
     context.getMetadataHandler().discardOutputMetadata();
@@ -702,7 +727,7 @@ public final class SkyframeActionExecutor implements ActionExecutionContextFacto
       completeAction(action, context.getMetadataHandler(), context.getFileOutErr(), outputDumped);
     } finally {
       statusReporter.remove(action);
-      postEvent(new ActionCompletionEvent(actionStartTime, action));
+      postEvent(new ActionCompletionEvent(actionStartTime, action, actionLookupData));
     }
   }
 
@@ -1101,7 +1126,9 @@ public final class SkyframeActionExecutor implements ActionExecutionContextFacto
   /** An object that can be notified about action completion. */
   public interface ActionCompletedReceiver {
     /** Receives a completed action. */
-    void actionCompleted(Action action);
+    void actionCompleted(ActionLookupData actionLookupData);
+    /** Notes that an action has started, giving the key. */
+    void noteActionEvaluationStarted(ActionLookupData actionLookupData, Action action);
   }
 
   public void setActionExecutionProgressReportingObjects(
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeBuildView.java b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeBuildView.java
index 0c418841a7..2ddbf975d1 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeBuildView.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeBuildView.java
@@ -24,6 +24,7 @@ import com.google.common.collect.Maps;
 import com.google.common.collect.Sets;
 import com.google.common.eventbus.EventBus;
 import com.google.devtools.build.lib.actions.ActionAnalysisMetadata;
+import com.google.devtools.build.lib.actions.ActionLookupValue;
 import com.google.devtools.build.lib.actions.ArtifactFactory;
 import com.google.devtools.build.lib.actions.ArtifactOwner;
 import com.google.devtools.build.lib.actions.ArtifactPrefixConflictException;
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java
index fd1b912024..8734f3b34b 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java
@@ -42,6 +42,7 @@ import com.google.devtools.build.lib.actions.ActionExecutionStatusReporter;
 import com.google.devtools.build.lib.actions.ActionGraph;
 import com.google.devtools.build.lib.actions.ActionInputFileCache;
 import com.google.devtools.build.lib.actions.ActionLogBufferPathGenerator;
+import com.google.devtools.build.lib.actions.ActionLookupValue;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.actions.ArtifactFactory;
 import com.google.devtools.build.lib.actions.ArtifactOwner;
@@ -79,6 +80,7 @@ import com.google.devtools.build.lib.concurrent.ThreadSafety;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadCompatible;
 import com.google.devtools.build.lib.events.ExtendedEventHandler;
 import com.google.devtools.build.lib.events.Reporter;
+import com.google.devtools.build.lib.exec.ExecutionOptions;
 import com.google.devtools.build.lib.exec.OutputService;
 import com.google.devtools.build.lib.packages.AspectDescriptor;
 import com.google.devtools.build.lib.packages.Attribute;
@@ -274,6 +276,7 @@ public abstract class SkyframeExecutor implements WalkableGraphFactory {
   protected SkyframeIncrementalBuildMonitor incrementalBuildMonitor =
       new SkyframeIncrementalBuildMonitor();
 
+  protected final MutableSupplier<Boolean> removeActionsAfterEvaluation = new MutableSupplier<>();
   private MutableSupplier<ConfigurationFactory> configurationFactory = new MutableSupplier<>();
   private MutableSupplier<ImmutableList<ConfigurationFragmentFactory>> configurationFragments =
       new MutableSupplier<>();
@@ -339,6 +342,7 @@ public abstract class SkyframeExecutor implements WalkableGraphFactory {
     this.productName = productName;
     this.crossRepositoryLabelViolationStrategy = crossRepositoryLabelViolationStrategy;
     this.buildFilesByPriority = buildFilesByPriority;
+    this.removeActionsAfterEvaluation.set(false);
   }
 
   private ImmutableMap<SkyFunctionName, SkyFunction> skyFunctions(
@@ -407,8 +411,14 @@ public abstract class SkyframeExecutor implements WalkableGraphFactory {
     map.put(
         SkyFunctions.CONFIGURED_TARGET,
         new ConfiguredTargetFunction(
-            new BuildViewProvider(), ruleClassProvider, cpuBoundSemaphore));
-    map.put(SkyFunctions.ASPECT, new AspectFunction(new BuildViewProvider(), ruleClassProvider));
+            new BuildViewProvider(),
+            ruleClassProvider,
+            cpuBoundSemaphore,
+            removeActionsAfterEvaluation));
+    map.put(
+        SkyFunctions.ASPECT,
+        new AspectFunction(
+            new BuildViewProvider(), ruleClassProvider, removeActionsAfterEvaluation));
     map.put(SkyFunctions.LOAD_SKYLARK_ASPECT, new ToplevelSkylarkAspectFunction());
     map.put(SkyFunctions.POST_CONFIGURED_TARGET,
         new PostConfiguredTargetFunction(new BuildViewProvider(), ruleClassProvider));
@@ -428,9 +438,11 @@ public abstract class SkyframeExecutor implements WalkableGraphFactory {
     map.put(SkyFunctions.ASPECT_COMPLETION, CompletionFunction.aspectCompletionFunction(eventBus));
     map.put(SkyFunctions.TEST_COMPLETION, new TestCompletionFunction());
     map.put(SkyFunctions.ARTIFACT, new ArtifactFunction(allowedMissingInputs));
-    map.put(SkyFunctions.BUILD_INFO_COLLECTION, new BuildInfoCollectionFunction(artifactFactory));
-    map.put(SkyFunctions.BUILD_INFO, new WorkspaceStatusFunction());
-    map.put(SkyFunctions.COVERAGE_REPORT, new CoverageReportFunction());
+    map.put(
+        SkyFunctions.BUILD_INFO_COLLECTION,
+        new BuildInfoCollectionFunction(artifactFactory, removeActionsAfterEvaluation));
+    map.put(SkyFunctions.BUILD_INFO, new WorkspaceStatusFunction(removeActionsAfterEvaluation));
+    map.put(SkyFunctions.COVERAGE_REPORT, new CoverageReportFunction(removeActionsAfterEvaluation));
     ActionExecutionFunction actionExecutionFunction =
         new ActionExecutionFunction(skyframeActionExecutor, tsgm);
     map.put(SkyFunctions.ACTION_EXECUTION, actionExecutionFunction);
@@ -438,7 +450,9 @@ public abstract class SkyframeExecutor implements WalkableGraphFactory {
     map.put(SkyFunctions.RECURSIVE_FILESYSTEM_TRAVERSAL,
         new RecursiveFilesystemTraversalFunction());
     map.put(SkyFunctions.FILESET_ENTRY, new FilesetEntryFunction());
-    map.put(SkyFunctions.ACTION_TEMPLATE_EXPANSION, new ActionTemplateExpansionFunction());
+    map.put(
+        SkyFunctions.ACTION_TEMPLATE_EXPANSION,
+        new ActionTemplateExpansionFunction(removeActionsAfterEvaluation));
     map.put(SkyFunctions.LOCAL_REPOSITORY_LOOKUP, new LocalRepositoryLookupFunction());
     map.putAll(extraSkyFunctions);
     return map.build();
@@ -637,12 +651,16 @@ public abstract class SkyframeExecutor implements WalkableGraphFactory {
   /**
    * Decides if graph edges should be stored for this build. If not, re-creates the graph to not
    * store graph edges. Necessary conditions to not store graph edges are:
-   * (1) batch (since incremental builds are not possible);
-   * (2) skyframe build (since otherwise the memory savings are too slight to bother);
-   * (3) keep-going (since otherwise bubbling errors up may require edges of done nodes);
-   * (4) discard_analysis_cache (since otherwise user isn't concerned about saving memory this way).
+   *
+   * <ol>
+   *   <li>batch (since incremental builds are not possible);
+   *   <li>keep-going (since otherwise bubbling errors up may require edges of done nodes);
+   *   <li>discard_analysis_cache (since otherwise user isn't concerned about saving memory this
+   *       way).
+   * </ol>
    */
-  public void decideKeepIncrementalState(boolean batch, Options viewOptions) {
+  public void decideKeepIncrementalState(
+      boolean batch, Options viewOptions, ExecutionOptions executionOptions) {
     // Assume incrementality.
   }
 
@@ -1635,7 +1653,7 @@ public abstract class SkyframeExecutor implements WalkableGraphFactory {
           eventHandler);
       return result.hasError()
           ? null
-          : result.get(actionLookupKey).getGeneratingAction(artifact);
+          : result.get(actionLookupKey).getGeneratingActionDangerousReadJavadoc(artifact);
     }
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ToplevelSkylarkAspectFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/ToplevelSkylarkAspectFunction.java
index cc1aa442fe..e9ee29ed7c 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ToplevelSkylarkAspectFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ToplevelSkylarkAspectFunction.java
@@ -17,6 +17,7 @@ package com.google.devtools.build.lib.skyframe;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.Iterables;
+import com.google.devtools.build.lib.actions.ActionLookupValue;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.events.Event;
 import com.google.devtools.build.lib.packages.AspectDescriptor;
@@ -106,4 +107,4 @@ public class ToplevelSkylarkAspectFunction implements SkyFunction {
       super(cause, Transience.PERSISTENT);
     }
   }
-}
\ No newline at end of file
+}
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/WorkspaceStatusFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/WorkspaceStatusFunction.java
index 12b36a4a31..d665632beb 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/WorkspaceStatusFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/WorkspaceStatusFunction.java
@@ -13,6 +13,7 @@
 // limitations under the License.
 package com.google.devtools.build.lib.skyframe;
 
+import com.google.common.base.Supplier;
 import com.google.devtools.build.lib.analysis.WorkspaceStatusAction;
 import com.google.devtools.build.lib.util.Preconditions;
 import com.google.devtools.build.skyframe.SkyFunction;
@@ -21,7 +22,10 @@ import com.google.devtools.build.skyframe.SkyValue;
 
 /** Creates the workspace status artifacts and action. */
 public class WorkspaceStatusFunction implements SkyFunction {
-  WorkspaceStatusFunction() {
+  private final Supplier<Boolean> removeActionAfterEvaluation;
+
+  WorkspaceStatusFunction(Supplier<Boolean> removeActionAfterEvaluation) {
+    this.removeActionAfterEvaluation = Preconditions.checkNotNull(removeActionAfterEvaluation);
   }
 
   @Override
@@ -37,7 +41,8 @@ public class WorkspaceStatusFunction implements SkyFunction {
     return new WorkspaceStatusValue(
         action.getStableStatus(),
         action.getVolatileStatus(),
-        action);
+        action,
+        removeActionAfterEvaluation.get());
   }
 
   @Override
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/WorkspaceStatusValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/WorkspaceStatusValue.java
index 62f7858190..d2758c5c2d 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/WorkspaceStatusValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/WorkspaceStatusValue.java
@@ -13,6 +13,7 @@
 // limitations under the License.
 package com.google.devtools.build.lib.skyframe;
 
+import com.google.devtools.build.lib.actions.ActionLookupValue;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.actions.ArtifactOwner;
 import com.google.devtools.build.lib.analysis.WorkspaceStatusAction;
@@ -33,9 +34,12 @@ public class WorkspaceStatusValue extends ActionLookupValue {
   static final ArtifactOwner ARTIFACT_OWNER = new BuildInfoKey();
   public static final SkyKey SKY_KEY = SkyKey.create(SkyFunctions.BUILD_INFO, ARTIFACT_OWNER);
 
-  public WorkspaceStatusValue(Artifact stableArtifact, Artifact volatileArtifact,
-      WorkspaceStatusAction action) {
-    super(action);
+  WorkspaceStatusValue(
+      Artifact stableArtifact,
+      Artifact volatileArtifact,
+      WorkspaceStatusAction action,
+      boolean removeActionAfterEvaluation) {
+    super(action, removeActionAfterEvaluation);
     this.stableArtifact = stableArtifact;
     this.volatileArtifact = volatileArtifact;
   }
@@ -50,12 +54,12 @@ public class WorkspaceStatusValue extends ActionLookupValue {
 
   private static class BuildInfoKey extends ActionLookupKey {
     @Override
-    SkyFunctionName getType() {
+    protected SkyFunctionName getType() {
       throw new UnsupportedOperationException();
     }
 
     @Override
-    SkyKey getSkyKeyInternal() {
+    protected SkyKey getSkyKeyInternal() {
       return SKY_KEY;
     }
   }
diff --git a/src/test/java/com/google/devtools/build/lib/actions/ActionLookupValueTest.java b/src/test/java/com/google/devtools/build/lib/actions/ActionLookupValueTest.java
new file mode 100644
index 0000000000..f7392e20bd
--- /dev/null
+++ b/src/test/java/com/google/devtools/build/lib/actions/ActionLookupValueTest.java
@@ -0,0 +1,87 @@
+// Copyright 2017 The Bazel Authors. All rights reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//    http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+package com.google.devtools.build.lib.actions;
+
+import static com.google.common.truth.Truth.assertThat;
+import static org.junit.Assert.fail;
+import static org.mockito.Mockito.mock;
+import static org.mockito.Mockito.when;
+
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableSet;
+import com.google.devtools.build.lib.vfs.FileSystem;
+import com.google.devtools.build.lib.vfs.PathFragment;
+import com.google.devtools.build.lib.vfs.inmemoryfs.InMemoryFileSystem;
+import org.junit.Before;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.JUnit4;
+
+/** Basic tests for {@link ActionLookupValue}. */
+@RunWith(JUnit4.class)
+public class ActionLookupValueTest {
+
+  private FileSystem fs;
+
+  @Before
+  public void setUp() {
+    fs = new InMemoryFileSystem();
+  }
+
+  @Test
+  public void testActionPresentAfterEvaluation() {
+    Action action = mock(Action.class);
+    Artifact artifact = mock(Artifact.class);
+    when(action.getOutputs()).thenReturn(ImmutableSet.of(artifact));
+    when(action.canRemoveAfterExecution()).thenReturn(true);
+    ActionLookupValue underTest = new ActionLookupValue(action, false);
+    assertThat(underTest.getGeneratingActionIndex(artifact)).isEqualTo(0);
+    assertThat(underTest.getAction(0)).isSameAs(action);
+    underTest.actionEvaluated(0, action);
+    assertThat(underTest.getAction(0)).isSameAs(action);
+  }
+
+  @Test
+  public void testActionNotPresentAfterEvaluation() {
+    Root root = Root.asDerivedRoot(fs.getRootDirectory());
+    Action normalAction = mock(Action.class);
+    Artifact normalArtifact = new Artifact(new PathFragment("normal"), root);
+    when(normalAction.getOutputs()).thenReturn(ImmutableSet.of(normalArtifact));
+    when(normalAction.canRemoveAfterExecution()).thenReturn(true);
+    Action persistentAction = mock(Action.class);
+    Artifact persistentOutput = new Artifact(new PathFragment("persistent"), root);
+    when(persistentAction.getOutputs()).thenReturn(ImmutableSet.of(persistentOutput));
+    when(persistentAction.canRemoveAfterExecution()).thenReturn(false);
+    ActionLookupValue underTest =
+        new ActionLookupValue(
+            ImmutableList.<ActionAnalysisMetadata>of(normalAction, persistentAction), true);
+    assertThat(underTest.getGeneratingActionIndex(normalArtifact)).isEqualTo(0);
+    assertThat(underTest.getAction(0)).isSameAs(normalAction);
+    assertThat(underTest.getGeneratingActionIndex(persistentOutput)).isEqualTo(1);
+    assertThat(underTest.getAction(1)).isSameAs(persistentAction);
+    underTest.actionEvaluated(0, normalAction);
+    try {
+      underTest.getAction(0);
+      fail();
+    } catch (NullPointerException e) {
+      // Expected.
+    }
+    assertThat(underTest.getGeneratingActionIndex(persistentOutput)).isEqualTo(1);
+    assertThat(underTest.getAction(1)).isSameAs(persistentAction);
+    underTest.actionEvaluated(1, persistentAction);
+    // Action that said not to clear it won't be cleared.
+    assertThat(underTest.getGeneratingActionIndex(persistentOutput)).isEqualTo(1);
+    assertThat(underTest.getAction(1)).isSameAs(persistentAction);
+  }
+}
diff --git a/src/test/java/com/google/devtools/build/lib/analysis/AspectValueTest.java b/src/test/java/com/google/devtools/build/lib/analysis/AspectValueTest.java
index 0714a0d253..4b71f8121a 100644
--- a/src/test/java/com/google/devtools/build/lib/analysis/AspectValueTest.java
+++ b/src/test/java/com/google/devtools/build/lib/analysis/AspectValueTest.java
@@ -15,6 +15,7 @@ package com.google.devtools.build.lib.analysis;
 
 import com.google.common.collect.ImmutableList;
 import com.google.common.testing.EqualsTester;
+import com.google.devtools.build.lib.actions.ActionLookupValue;
 import com.google.devtools.build.lib.analysis.config.BuildConfiguration;
 import com.google.devtools.build.lib.analysis.util.AnalysisTestCase;
 import com.google.devtools.build.lib.analysis.util.TestAspects;
@@ -24,7 +25,6 @@ import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.packages.AspectDescriptor;
 import com.google.devtools.build.lib.packages.AspectParameters;
 import com.google.devtools.build.lib.packages.NativeAspectClass;
-import com.google.devtools.build.lib.skyframe.ActionLookupValue;
 import com.google.devtools.build.lib.skyframe.AspectValue;
 import com.google.devtools.build.lib.skyframe.AspectValue.AspectKey;
 import com.google.devtools.build.skyframe.SkyKey;
diff --git a/src/test/java/com/google/devtools/build/lib/analysis/util/AnalysisTestUtil.java b/src/test/java/com/google/devtools/build/lib/analysis/util/AnalysisTestUtil.java
index de1247e846..f821e467a7 100644
--- a/src/test/java/com/google/devtools/build/lib/analysis/util/AnalysisTestUtil.java
+++ b/src/test/java/com/google/devtools/build/lib/analysis/util/AnalysisTestUtil.java
@@ -147,7 +147,7 @@ public final class AnalysisTestUtil {
     }
 
     @Override
-    public Iterable<ActionAnalysisMetadata> getRegisteredActions() {
+    public List<ActionAnalysisMetadata> getRegisteredActions() {
       return original.getRegisteredActions();
     }
 
@@ -329,7 +329,7 @@ public final class AnalysisTestUtil {
     }
 
     @Override
-    public Iterable<ActionAnalysisMetadata> getRegisteredActions() {
+    public List<ActionAnalysisMetadata> getRegisteredActions() {
       return ImmutableList.of();
     }
 
diff --git a/src/test/java/com/google/devtools/build/lib/analysis/util/BuildViewTestCase.java b/src/test/java/com/google/devtools/build/lib/analysis/util/BuildViewTestCase.java
index e8271372d2..576a312c85 100644
--- a/src/test/java/com/google/devtools/build/lib/analysis/util/BuildViewTestCase.java
+++ b/src/test/java/com/google/devtools/build/lib/analysis/util/BuildViewTestCase.java
@@ -37,6 +37,7 @@ import com.google.devtools.build.lib.actions.Action;
 import com.google.devtools.build.lib.actions.ActionAnalysisMetadata;
 import com.google.devtools.build.lib.actions.ActionGraph;
 import com.google.devtools.build.lib.actions.ActionInput;
+import com.google.devtools.build.lib.actions.ActionLookupValue;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.actions.ArtifactOwner;
 import com.google.devtools.build.lib.actions.MapBasedActionGraph;
@@ -120,7 +121,6 @@ import com.google.devtools.build.lib.pkgcache.PathPackageLocator;
 import com.google.devtools.build.lib.rules.extra.ExtraAction;
 import com.google.devtools.build.lib.rules.test.BaselineCoverageAction;
 import com.google.devtools.build.lib.rules.test.InstrumentedFilesProvider;
-import com.google.devtools.build.lib.skyframe.ActionLookupValue;
 import com.google.devtools.build.lib.skyframe.AspectValue;
 import com.google.devtools.build.lib.skyframe.ConfiguredTargetKey;
 import com.google.devtools.build.lib.skyframe.DiffAwareness;
@@ -1656,7 +1656,7 @@ public abstract class BuildViewTestCase extends FoundationTestCase {
     }
 
     @Override
-    public Iterable<ActionAnalysisMetadata> getRegisteredActions() {
+    public List<ActionAnalysisMetadata> getRegisteredActions() {
       throw new UnsupportedOperationException();
     }
 
diff --git a/src/test/java/com/google/devtools/build/lib/runtime/ExperimentalStateTrackerTest.java b/src/test/java/com/google/devtools/build/lib/runtime/ExperimentalStateTrackerTest.java
index 5954f43aa8..ef482198a7 100644
--- a/src/test/java/com/google/devtools/build/lib/runtime/ExperimentalStateTrackerTest.java
+++ b/src/test/java/com/google/devtools/build/lib/runtime/ExperimentalStateTrackerTest.java
@@ -23,6 +23,7 @@ import com.google.common.collect.ImmutableSet;
 import com.google.devtools.build.lib.actions.Action;
 import com.google.devtools.build.lib.actions.ActionCompletionEvent;
 import com.google.devtools.build.lib.actions.ActionExecutionMetadata;
+import com.google.devtools.build.lib.actions.ActionLookupData;
 import com.google.devtools.build.lib.actions.ActionOwner;
 import com.google.devtools.build.lib.actions.ActionStartedEvent;
 import com.google.devtools.build.lib.actions.ActionStatusMessage;
@@ -145,7 +146,8 @@ public class ExperimentalStateTrackerTest extends FoundationTestCase {
     ExperimentalStateTracker stateTracker = new ExperimentalStateTracker(clock);
     stateTracker.actionStarted(new ActionStartedEvent(fastAction, 123456789));
     stateTracker.actionStarted(new ActionStartedEvent(slowAction, 123456999));
-    stateTracker.actionCompletion(new ActionCompletionEvent(20, fastAction));
+    stateTracker.actionCompletion(
+        new ActionCompletionEvent(20, fastAction, Mockito.mock(ActionLookupData.class)));
 
     LoggingTerminalWriter terminalWriter = new LoggingTerminalWriter(/*discardHighlight=*/ true);
     stateTracker.writeProgressBar(terminalWriter);
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/ActionTemplateExpansionFunctionTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/ActionTemplateExpansionFunctionTest.java
index 1b725b367a..d24647af26 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/ActionTemplateExpansionFunctionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/ActionTemplateExpansionFunctionTest.java
@@ -16,6 +16,7 @@ package com.google.devtools.build.lib.skyframe;
 import static com.google.common.truth.Truth.assertThat;
 import static org.junit.Assert.fail;
 
+import com.google.common.base.Suppliers;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.Iterables;
@@ -74,9 +75,10 @@ public final class ActionTemplateExpansionFunctionTest extends FoundationTestCas
     MemoizingEvaluator evaluator =
         new InMemoryMemoizingEvaluator(
             ImmutableMap.<SkyFunctionName, SkyFunction>builder()
-                .put(SkyFunctions.ARTIFACT,
-                    new DummyArtifactFunction(artifactValueMap))
-                .put(SkyFunctions.ACTION_TEMPLATE_EXPANSION, new ActionTemplateExpansionFunction())
+                .put(SkyFunctions.ARTIFACT, new DummyArtifactFunction(artifactValueMap))
+                .put(
+                    SkyFunctions.ACTION_TEMPLATE_EXPANSION,
+                    new ActionTemplateExpansionFunction(Suppliers.ofInstance(false)))
                 .build(),
             differencer);
     driver = new SequentialBuildDriver(evaluator);
@@ -188,7 +190,12 @@ public final class ActionTemplateExpansionFunctionTest extends FoundationTestCas
     if (result.hasError()) {
       throw result.getError().getException();
     }
-    return ImmutableList.copyOf(result.get(skyKey).getExpandedActions());
+    ActionTemplateExpansionValue actionTemplateExpansionValue = result.get(skyKey);
+    ImmutableList.Builder<Action> actionList = ImmutableList.builder();
+    for (int i = 0; i < actionTemplateExpansionValue.getNumActions(); i++) {
+      actionList.add(actionTemplateExpansionValue.getAction(i));
+    }
+    return actionList.build();
   }
 
   private Artifact createTreeArtifact(String path) {
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/ArtifactFunctionTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/ArtifactFunctionTest.java
index 71bb32abbc..c729fc6b6a 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/ArtifactFunctionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/ArtifactFunctionTest.java
@@ -32,6 +32,8 @@ import com.google.devtools.build.lib.actions.Action;
 import com.google.devtools.build.lib.actions.ActionAnalysisMetadata;
 import com.google.devtools.build.lib.actions.ActionAnalysisMetadata.MiddlemanType;
 import com.google.devtools.build.lib.actions.ActionInputHelper;
+import com.google.devtools.build.lib.actions.ActionLookupData;
+import com.google.devtools.build.lib.actions.ActionLookupValue;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.actions.Artifact.SpecialArtifact;
 import com.google.devtools.build.lib.actions.Artifact.SpecialArtifactType;
@@ -464,9 +466,10 @@ public class ArtifactFunctionTest extends ArtifactFunctionTestCase {
 
   private void setGeneratingActions() {
     if (evaluator.getExistingValueForTesting(OWNER_KEY) == null) {
-      differencer.inject(ImmutableMap.of(
-          OWNER_KEY,
-          new ActionLookupValue(ImmutableList.<ActionAnalysisMetadata>copyOf(actions))));
+      differencer.inject(
+          ImmutableMap.of(
+              OWNER_KEY,
+              new ActionLookupValue(ImmutableList.<ActionAnalysisMetadata>copyOf(actions), false)));
     }
   }
 
@@ -483,11 +486,14 @@ public class ArtifactFunctionTest extends ArtifactFunctionTestCase {
   /** Value Builder for actions that just stats and stores the output file (which must exist). */
   private static class SimpleActionExecutionFunction implements SkyFunction {
     @Override
-    public SkyValue compute(SkyKey skyKey, Environment env) {
+    public SkyValue compute(SkyKey skyKey, Environment env) throws InterruptedException {
       Map<Artifact, FileValue> artifactData = new HashMap<>();
       Map<Artifact, TreeArtifactValue> treeArtifactData = new HashMap<>();
       Map<Artifact, FileArtifactValue> additionalOutputData = new HashMap<>();
-      Action action = (Action) skyKey.argument();
+      ActionLookupData actionLookupData = (ActionLookupData) skyKey.argument();
+      ActionLookupValue actionLookupValue =
+          (ActionLookupValue) env.getValue(actionLookupData.getActionLookupNode());
+      Action action = actionLookupValue.getAction(actionLookupData.getActionIndex());
       Artifact output = Iterables.getOnlyElement(action.getOutputs());
 
       try {
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/ArtifactFunctionTestCase.java b/src/test/java/com/google/devtools/build/lib/skyframe/ArtifactFunctionTestCase.java
index a5989761a8..36320171b9 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/ArtifactFunctionTestCase.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/ArtifactFunctionTestCase.java
@@ -15,12 +15,13 @@ package com.google.devtools.build.lib.skyframe;
 
 import com.google.common.base.Predicate;
 import com.google.common.base.Predicates;
+import com.google.common.base.Suppliers;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
 import com.google.devtools.build.lib.actions.ActionAnalysisMetadata;
+import com.google.devtools.build.lib.actions.ActionLookupValue.ActionLookupKey;
 import com.google.devtools.build.lib.analysis.BlazeDirectories;
 import com.google.devtools.build.lib.pkgcache.PathPackageLocator;
-import com.google.devtools.build.lib.skyframe.ActionLookupValue.ActionLookupKey;
 import com.google.devtools.build.lib.skyframe.ExternalFilesHelper.ExternalFileAction;
 import com.google.devtools.build.lib.skyframe.PackageLookupFunction.CrossRepositoryLabelViolationStrategy;
 import com.google.devtools.build.lib.skyframe.PackageLookupValue.BuildFileName;
@@ -110,7 +111,9 @@ abstract class ArtifactFunctionTestCase {
                             TestRuleClassProvider.getRuleClassProvider(), root.getFileSystem()),
                         directories))
                 .put(SkyFunctions.EXTERNAL_PACKAGE, new ExternalPackageFunction())
-                .put(SkyFunctions.ACTION_TEMPLATE_EXPANSION, new ActionTemplateExpansionFunction())
+                .put(
+                    SkyFunctions.ACTION_TEMPLATE_EXPANSION,
+                    new ActionTemplateExpansionFunction(Suppliers.ofInstance(false)))
                 .build(),
             differencer);
     driver = new SequentialBuildDriver(evaluator);
@@ -149,12 +152,12 @@ abstract class ArtifactFunctionTestCase {
 
   private static class SingletonActionLookupKey extends ActionLookupKey {
     @Override
-    SkyKey getSkyKeyInternal() {
+    protected SkyKey getSkyKeyInternal() {
       return OWNER_KEY;
     }
 
     @Override
-    SkyFunctionName getType() {
+    protected SkyFunctionName getType() {
       throw new UnsupportedOperationException();
     }
   }
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/FilesystemValueCheckerTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/FilesystemValueCheckerTest.java
index 3f42663cbc..0dba1d9db9 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/FilesystemValueCheckerTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/FilesystemValueCheckerTest.java
@@ -25,6 +25,8 @@ import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSet;
 import com.google.common.util.concurrent.Runnables;
 import com.google.devtools.build.lib.actions.Action;
+import com.google.devtools.build.lib.actions.ActionLookupValue;
+import com.google.devtools.build.lib.actions.ActionLookupValue.ActionLookupKey;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.actions.Artifact.SpecialArtifact;
 import com.google.devtools.build.lib.actions.Artifact.SpecialArtifactType;
@@ -352,14 +354,16 @@ public class FilesystemValueCheckerTest {
     FileSystemUtils.writeContentAsLatin1(out1.getPath(), "hello");
     FileSystemUtils.writeContentAsLatin1(out2.getPath(), "fizzlepop");
 
-    Action action1 =
-        new TestAction(
-            Runnables.doNothing(), ImmutableSet.<Artifact>of(), ImmutableSet.of(out1));
-    Action action2 =
-        new TestAction(
-            Runnables.doNothing(), ImmutableSet.<Artifact>of(), ImmutableSet.of(out2));
-    SkyKey actionKey1 = ActionExecutionValue.key(action1);
-    SkyKey actionKey2 = ActionExecutionValue.key(action2);
+    SkyKey actionLookupKey =
+        ActionLookupValue.key(
+            new ActionLookupKey() {
+              @Override
+              protected SkyFunctionName getType() {
+                return SkyFunctionName.FOR_TESTING;
+              }
+            });
+    SkyKey actionKey1 = ActionExecutionValue.key(actionLookupKey, 0);
+    SkyKey actionKey2 = ActionExecutionValue.key(actionLookupKey, 1);
     differencer.inject(
         ImmutableMap.<SkyKey, SkyValue>of(
             actionKey1,
@@ -429,27 +433,19 @@ public class FilesystemValueCheckerTest {
     Artifact last = createTreeArtifact("zzzzzzzzzz");
     FileSystemUtils.createDirectoryAndParents(last.getPath());
 
-    Action action1 =
-        new TestAction(
-            Runnables.doNothing(), ImmutableSet.<Artifact>of(), ImmutableSet.of(out1));
-    Action action2 =
-        new TestAction(
-            Runnables.doNothing(), ImmutableSet.<Artifact>of(), ImmutableSet.of(out2));
-    Action actionEmpty =
-        new TestAction(
-            Runnables.doNothing(), ImmutableSet.<Artifact>of(), ImmutableSet.of(outEmpty));
-    Action actionUnchanging =
-        new TestAction(
-            Runnables.doNothing(), ImmutableSet.<Artifact>of(), ImmutableSet.of(outUnchanging));
-    Action lastAction =
-        new TestAction(
-            Runnables.doNothing(), ImmutableSet.<Artifact>of(), ImmutableSet.of(last));
-
-    SkyKey actionKey1 = ActionExecutionValue.key(action1);
-    SkyKey actionKey2 = ActionExecutionValue.key(action2);
-    SkyKey actionKeyEmpty = ActionExecutionValue.key(actionEmpty);
-    SkyKey actionKeyUnchanging = ActionExecutionValue.key(actionUnchanging);
-    SkyKey actionKeyLast = ActionExecutionValue.key(lastAction);
+    SkyKey actionLookupKey =
+        ActionLookupValue.key(
+            new ActionLookupKey() {
+              @Override
+              protected SkyFunctionName getType() {
+                return SkyFunctionName.FOR_TESTING;
+              }
+            });
+    SkyKey actionKey1 = ActionExecutionValue.key(actionLookupKey, 0);
+    SkyKey actionKey2 = ActionExecutionValue.key(actionLookupKey, 1);
+    SkyKey actionKeyEmpty = ActionExecutionValue.key(actionLookupKey, 2);
+    SkyKey actionKeyUnchanging = ActionExecutionValue.key(actionLookupKey, 3);
+    SkyKey actionKeyLast = ActionExecutionValue.key(actionLookupKey, 4);
     differencer.inject(
         ImmutableMap.<SkyKey, SkyValue>of(
             actionKey1,
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/SkyframeAwareActionTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/SkyframeAwareActionTest.java
index 02c2b41a26..66c469d5f0 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/SkyframeAwareActionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/SkyframeAwareActionTest.java
@@ -388,7 +388,7 @@ public class SkyframeAwareActionTest extends TimestampBuilderTestCase {
         null);
 
     // Sanity check that our invalidation receiver is working correctly. We'll rely on it again.
-    SkyKey actionKey = ActionExecutionValue.key(action);
+    SkyKey actionKey = ActionExecutionValue.key(OWNER_KEY, 0);
     TrackingEvaluationProgressReceiver.EvaluatedEntry evaluatedAction =
         progressReceiver.getEvalutedEntry(actionKey);
     assertThat(evaluatedAction).isNotNull();
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/TimestampBuilderTestCase.java b/src/test/java/com/google/devtools/build/lib/skyframe/TimestampBuilderTestCase.java
index 2ca64ea0c3..8caead9e87 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/TimestampBuilderTestCase.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/TimestampBuilderTestCase.java
@@ -17,6 +17,7 @@ import static com.google.devtools.build.lib.actions.util.ActionCacheTestHelper.A
 
 import com.google.common.base.Predicate;
 import com.google.common.base.Predicates;
+import com.google.common.base.Suppliers;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSet;
@@ -32,6 +33,8 @@ import com.google.devtools.build.lib.actions.ActionExecutionException;
 import com.google.devtools.build.lib.actions.ActionExecutionStatusReporter;
 import com.google.devtools.build.lib.actions.ActionInputFileCache;
 import com.google.devtools.build.lib.actions.ActionLogBufferPathGenerator;
+import com.google.devtools.build.lib.actions.ActionLookupData;
+import com.google.devtools.build.lib.actions.ActionLookupValue;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.actions.BuildFailedException;
 import com.google.devtools.build.lib.actions.Executor;
@@ -101,7 +104,7 @@ import org.junit.Before;
 public abstract class TimestampBuilderTestCase extends FoundationTestCase {
   protected static final ActionLookupValue.ActionLookupKey ALL_OWNER =
       new SingletonActionLookupKey();
-  private static final SkyKey OWNER_KEY = SkyKey.create(SkyFunctions.ACTION_LOOKUP, ALL_OWNER);
+  protected static final SkyKey OWNER_KEY = SkyKey.create(SkyFunctions.ACTION_LOOKUP, ALL_OWNER);
   protected static final Predicate<Action> ALWAYS_EXECUTE_FILTER = Predicates.alwaysTrue();
   protected static final String CYCLE_MSG = "Yarrrr, there be a cycle up in here";
 
@@ -118,7 +121,8 @@ public abstract class TimestampBuilderTestCase extends FoundationTestCase {
     tsgm = new TimestampGranularityMonitor(clock);
     ResourceManager.instance().setAvailableResources(ResourceSet.createWithRamCpuIo(100, 1, 1));
     actions = new HashSet<>();
-    actionTemplateExpansionFunction = new ActionTemplateExpansionFunction();
+    actionTemplateExpansionFunction =
+        new ActionTemplateExpansionFunction(Suppliers.ofInstance(false));
   }
 
   protected void clearActions() {
@@ -218,7 +222,8 @@ public abstract class TimestampBuilderTestCase extends FoundationTestCase {
       private void setGeneratingActions() {
         if (evaluator.getExistingValueForTesting(OWNER_KEY) == null) {
           differencer.inject(
-              ImmutableMap.of(OWNER_KEY, new ActionLookupValue(ImmutableList.copyOf(actions))));
+              ImmutableMap.of(
+                  OWNER_KEY, new ActionLookupValue(ImmutableList.copyOf(actions), false)));
         }
       }
 
@@ -443,12 +448,12 @@ public abstract class TimestampBuilderTestCase extends FoundationTestCase {
 
   private static class SingletonActionLookupKey extends ActionLookupValue.ActionLookupKey {
     @Override
-    SkyKey getSkyKeyInternal() {
+    protected SkyKey getSkyKeyInternal() {
       return OWNER_KEY;
     }
 
     @Override
-    SkyFunctionName getType() {
+    protected SkyFunctionName getType() {
       throw new UnsupportedOperationException();
     }
   }
@@ -477,6 +482,9 @@ public abstract class TimestampBuilderTestCase extends FoundationTestCase {
   private static final ActionCompletedReceiver EMPTY_COMPLETION_RECEIVER =
       new ActionCompletedReceiver() {
         @Override
-        public void actionCompleted(Action action) {}
+        public void actionCompleted(ActionLookupData actionLookupData) {}
+
+        @Override
+        public void noteActionEvaluationStarted(ActionLookupData actionLookupData, Action action) {}
       };
 }
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/TreeArtifactBuildTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/TreeArtifactBuildTest.java
index 099b307116..99da8b961b 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/TreeArtifactBuildTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/TreeArtifactBuildTest.java
@@ -1217,7 +1217,7 @@ public class TreeArtifactBuildTest extends TimestampBuilderTestCase {
       ActionTemplateExpansionKey key = (ActionTemplateExpansionKey) skyKey.argument();
       ActionTemplate<?> actionTemplate = key.getActionTemplate();
       return new ActionTemplateExpansionValue(
-          Preconditions.checkNotNull(actionTemplateToActionMap.get(actionTemplate)));
+          Preconditions.checkNotNull(actionTemplateToActionMap.get(actionTemplate)), false);
     }
 
     @Override
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/TreeArtifactMetadataTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/TreeArtifactMetadataTest.java
index 6817ccf4ea..03d661867a 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/TreeArtifactMetadataTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/TreeArtifactMetadataTest.java
@@ -26,6 +26,8 @@ import com.google.common.collect.Iterables;
 import com.google.devtools.build.lib.actions.Action;
 import com.google.devtools.build.lib.actions.ActionAnalysisMetadata;
 import com.google.devtools.build.lib.actions.ActionInputHelper;
+import com.google.devtools.build.lib.actions.ActionLookupData;
+import com.google.devtools.build.lib.actions.ActionLookupValue;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.actions.Artifact.SpecialArtifact;
 import com.google.devtools.build.lib.actions.Artifact.SpecialArtifactType;
@@ -221,9 +223,10 @@ public class TreeArtifactMetadataTest extends ArtifactFunctionTestCase {
 
   private void setGeneratingActions() {
     if (evaluator.getExistingValueForTesting(OWNER_KEY) == null) {
-      differencer.inject(ImmutableMap.of(
-          OWNER_KEY,
-          new ActionLookupValue(ImmutableList.<ActionAnalysisMetadata>copyOf(actions))));
+      differencer.inject(
+          ImmutableMap.of(
+              OWNER_KEY,
+              new ActionLookupValue(ImmutableList.<ActionAnalysisMetadata>copyOf(actions), false)));
     }
   }
 
@@ -239,10 +242,14 @@ public class TreeArtifactMetadataTest extends ArtifactFunctionTestCase {
 
   private class TreeArtifactExecutionFunction implements SkyFunction {
     @Override
-    public SkyValue compute(SkyKey skyKey, Environment env) throws SkyFunctionException {
+    public SkyValue compute(SkyKey skyKey, Environment env)
+        throws SkyFunctionException, InterruptedException {
       Map<Artifact, FileValue> fileData = new HashMap<>();
       Map<TreeFileArtifact, FileArtifactValue> treeArtifactData = new HashMap<>();
-      Action action = (Action) skyKey.argument();
+      ActionLookupData actionLookupData = (ActionLookupData) skyKey.argument();
+      ActionLookupValue actionLookupValue =
+          (ActionLookupValue) env.getValue(actionLookupData.getActionLookupNode());
+      Action action = actionLookupValue.getAction(actionLookupData.getActionIndex());
       Artifact output = Iterables.getOnlyElement(action.getOutputs());
       for (PathFragment subpath : testTreeArtifactContents) {
         try {
diff --git a/src/test/shell/integration/discard_graph_edges_test.sh b/src/test/shell/integration/discard_graph_edges_test.sh
index 74284c34ea..c034da862c 100755
--- a/src/test/shell/integration/discard_graph_edges_test.sh
+++ b/src/test/shell/integration/discard_graph_edges_test.sh
@@ -152,7 +152,7 @@ genrule(name = 'histodump',
         srcs = glob(["*.in"]),
         outs = ['histo.txt'],
         local = 1,
-        cmd = 'set -x; ${bazel_javabase}/bin/jmap -histo:live \$\$(cat $server_pid_fifo) > \$(location histo.txt)'
+        cmd = '${bazel_javabase}/bin/jmap -histo:live \$\$(cat $server_pid_fifo) > \$(location histo.txt)'
        )
 EOF
   rm -f "$server_pid_fifo"
@@ -197,6 +197,61 @@ function test_packages_cleared() {
       || fail "env extension count $env_count too high"
 }
 
+function test_actions_deleted_after_execution() {
+  if [[ "$BUILD_FLAGS" != *"--noexperimental_enable_critical_path_profiling"* ]]; then
+    # Actions are only deleted if critical_path_profiling is disabled.
+    return
+  fi
+  rm -rf histodump
+  mkdir -p histodump || fail "Couldn't create directory"
+  readonly local wait_fifo="$TEST_TMPDIR/wait_fifo"
+  readonly local server_pid_file="$TEST_TMPDIR/server_pid.txt"
+  cat > histodump/BUILD <<EOF || fail "Couldn't create BUILD file"
+genrule(name = 'action0',
+        outs = ['wait.out'],
+        local = 1,
+        cmd = 'cat $wait_fifo > /dev/null; touch \$@'
+        )
+EOF
+  for i in $(seq 1 3); do
+    iminus=$((i-1))
+    cat >> histodump/BUILD <<EOF || fail "Couldn't append"
+genrule(name = 'action${i}',
+        srcs = [':action${iminus}'],
+        outs = ['histo.${i}'],
+        local = 1,
+        cmd = '${bazel_javabase}/bin/jmap -histo:live '
+              + '\$\$(cat ${server_pid_file}) > \$(location histo.${i})'
+       )
+EOF
+  done
+  mkfifo "$wait_fifo"
+  local readonly histo_root="$(bazel info "${PRODUCT_NAME}-genfiles" \
+      2> /dev/null)/histodump/histo."
+  bazel clean >& "$TEST_log" || fail "Couldn't clean"
+  bazel $STARTUP_FLAGS build $BUILD_FLAGS //histodump:action3 >& "$TEST_log" &
+  server_pid=$!
+  echo "$server_pid" > "$server_pid_file"
+  echo "" > "$wait_fifo"
+  # Wait for previous command to finish.
+  wait "$server_pid" || fail "Bazel command failed"
+  local genrule_action_count=100
+  for i in $(seq 1 3); do
+    local histo_file="$histo_root$i"
+    local new_genrule_action_count="$(extract_histogram_count "$histo_file" \
+        "GenRuleAction$")"
+    if [[ "$new_genrule_action_count" -ge "$genrule_action_count" ]]; then
+      cat "$histo_file" >> "$TEST_log"
+      fail "Number of genrule actions did not decrease: $new_genrule_action_count vs. $genrule_action_count"
+    fi
+    if [[ -z "$new_genrule_action_count" ]]; then
+      cat "$histo_file" >> "$TEST_log"
+      fail "No genrule actions? Class may have been renamed"
+    fi
+    genrule_action_count="$new_genrule_action_count"
+  done
+}
+
 # Action conflicts can cause deletion of nodes, and deletion is tricky with no edges.
 function test_action_conflict() {
   mkdir -p conflict || fail "Couldn't create directory"
@@ -218,6 +273,30 @@ EOF
   expect_log "mytest *PASSED"
 }
 
+function test_remove_actions() {
+  bazel "$STARTUP_FLAGS" test $BUILD_FLAGS \
+      --noexperimental_enable_critical_path_profiling //testing:mytest \
+      >& $TEST_log || fail "Expected success"
+}
+
+function test_modules() {
+  mkdir -p foo || fail "mkdir failed"
+  cat > foo/BUILD <<EOF || fail "BUILD file creation failed"
+package(features=['prune_header_modules','header_modules','use_header_modules'])
+cc_library(name = 'a', hdrs = ['a.h'])
+cc_library(name = 'b', hdrs = ['b.h'], deps = [':a'])
+cc_library(name = 'c', deps = [':b'], srcs = ['c.cc'])
+EOF
+  touch foo/a.h || fail "touch a.h failed"
+  touch foo/b.h || fail "touch b.h failed"
+  echo '#include "foo/b.h"' > foo/c.cc || fail "c.cc creation failed"
+
+  bazel "$STARTUP_FLAGS" build $BUILD_FLAGS \
+      --noexperimental_enable_critical_path_profiling \
+      //foo:c --experimental_skip_unused_modules \
+    --experimental_prune_more_modules >& "$TEST_log" || fail "Build failed"
+}
+
 # The following tests are not expected to exercise codepath -- make sure nothing bad happens.
 
 function test_no_batch() {