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 101cc39..ad2148a 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 @@
     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 d490e6a..33b0b16 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 @@
    */
   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 497f96f..d4621ea 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 @@
 
   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 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 0000000..fea6d6d
--- /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 0000000..b8c105f
--- /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 b8bd981..8a49af4 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.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 @@
    * 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 @@
    * 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 @@
       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 a42d5b9..7474c7c 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 @@
   }
 
   @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 eb559ea..70b8e51 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.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 @@
    * 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 c9709ab..7c18968 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.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.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 @@
                 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 426b00f..ddf5b99 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 @@
   }
 
   @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 bd8f8cb..24b1ba0 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.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.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 @@
 
   // 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 @@
 
   @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 @@
     } 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 8c3a18e..84b3c85 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.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.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 @@
       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 @@
   }
 
   @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 fea9d72..00a69dc 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.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 @@
     // 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 353dcd4..73f32e4 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 @@
     // 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 86b7371..8808252 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 @@
 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 @@
   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 @@
     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 905c3a9..659e1bb 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.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 @@
   @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 @@
 
     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 @@
 
     // 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 @@
   }
 
   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 @@
               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 @@
       }
     }
     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 4c3c6a2..3d71d1b 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 @@
 @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 @@
   }
 
   /**
-   * @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 @@
 
   /**
    * @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;
   }
 
+  /**
+   * @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}.
+   */
   @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.
-   */
-  public static boolean isReportWorthyAction(Action action) {
-    return action.getActionType() == MiddlemanType.NORMAL;
+  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 f5aab9a..0000000
--- 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 3164f16..3967bb2 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 @@
  * 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 @@
       throw new ActionTemplateExpansionFunctionException(e);
     }
 
-    return new ActionTemplateExpansionValue(expandedActions);
+    return new ActionTemplateExpansionValue(expandedActions, removeActionsAfterEvaluation.get());
   }
 
   /** Exception thrown by {@link ActionTemplateExpansionFunction}. */
@@ -85,12 +93,14 @@
     }
   }
 
-  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 0ac6e60..22e9b7f 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 @@
 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 @@
  * 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 @@
     }
 
     @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 293f530..0020c3a 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.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.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.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 @@
       }
     }
 
-    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);
-      }
+    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);
-    } 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()) {
-        // 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)) {
-        return createAggregatingValue(artifact, action,
-            actionValue.getArtifactValue(artifact), env);
-      } else {
-        return createSimpleFileArtifactValue(artifact, actionValue);
+        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);
+    }
+    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);
+      }
+    }
+    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 @@
     // 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 @@
     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);
-    ActionLookupValue value = (ActionLookupValue) env.getValue(actionLookupKey);
-    if (value == null) {
-      Preconditions.checkState(artifactOwner == CoverageReportValue.ARTIFACT_OWNER,
-          "Not-yet-present artifact owner: %s", artifactOwner);
-      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);
+    return ActionLookupValue.key((ActionLookupKey) artifactOwner);
   }
 
-  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);
-      }
+  @Nullable
+  private static ActionLookupValue getActionLookupValue(
+      SkyKey actionLookupKey, SkyFunction.Environment env, Artifact artifact)
+      throws InterruptedException {
+    ActionLookupValue value = (ActionLookupValue) env.getValue(actionLookupKey);
+    if (value == null) {
+      ArtifactOwner artifactOwner = artifact.getArtifactOwner();
+      Preconditions.checkState(
+          artifactOwner == CoverageReportValue.ARTIFACT_OWNER,
+          "Not-yet-present artifact owner: %s (%s %s)",
+          artifactOwner,
+          artifact,
+          actionLookupKey);
+      return null;
     }
-    return matchingOutputs.build();
+    return value;
   }
 
   private static final class ArtifactFunctionException extends SkyFunctionException {
@@ -330,10 +365,6 @@
       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 8437ab9..2873ad1 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 @@
 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 @@
       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 @@
         originalTarget.getLocation(),
         ConfiguredAspect.forAlias(real.getConfiguredAspect()),
         ImmutableList.<ActionAnalysisMetadata>of(),
-        transitivePackages);
+        transitivePackages,
+        removeActionsAfterEvaluation.get());
   }
 
   @Nullable
@@ -466,7 +475,8 @@
         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 25d3873..0656d45 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.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.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 @@
     }
 
     @Override
-    SkyFunctionName getType() {
+    protected SkyFunctionName getType() {
       return SkyFunctions.ASPECT;
     }
 
@@ -240,7 +242,7 @@
     }
 
     @Override
-    SkyFunctionName getType() {
+    protected SkyFunctionName getType() {
       return SkyFunctions.LOAD_SKYLARK_ASPECT;
     }
 
@@ -321,9 +323,10 @@
       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 73b2854..79011a8 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.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 @@
 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 @@
       }
     };
 
-    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 05d6a7e..ee00e64 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 @@
 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 @@
 
   @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 @@
     }
 
     @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 b0eaf3c..d79f0db 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.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.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 @@
   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 @@
     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 @@
       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 f28ffbf..78459b4 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 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 @@
   }
 
   @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 1109570..2c2bb3d 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 @@
 
 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.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 @@
 
   @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 @@
   }
 
   @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 @@
 
   @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 47ce177..f31e21c 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 @@
  * 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 @@
       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 164b37e..3d63fe0 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 @@
 
 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 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 e48991b..aed5573 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.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 @@
 
   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 @@
   }
 
   @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 7c353ac..f2eb148 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.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 @@
   // 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 @@
     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 @@
    *
    * <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 @@
     }
     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 @@
         // 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 @@
   }
 
   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 @@
     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 @@
 
         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 @@
   }
 
   /**
-   * 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 @@
       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 @@
   /** 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 0c41884..2ddbf97 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.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 fd1b912..8734f3b 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.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.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 @@
   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 @@
     this.productName = productName;
     this.crossRepositoryLabelViolationStrategy = crossRepositoryLabelViolationStrategy;
     this.buildFilesByPriority = buildFilesByPriority;
+    this.removeActionsAfterEvaluation.set(false);
   }
 
   private ImmutableMap<SkyFunctionName, SkyFunction> skyFunctions(
@@ -407,8 +411,14 @@
     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 @@
     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 @@
     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 @@
   /**
    * 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 @@
           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 cc1aa44..e9ee29e 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 @@
 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 @@
       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 12b36a4..d665632 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 @@
 
 /** 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 @@
     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 62f7858..d2758c5 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 @@
   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 @@
 
   private static class BuildInfoKey extends ActionLookupKey {
     @Override
-    SkyFunctionName getType() {
+    protected SkyFunctionName getType() {
       throw new UnsupportedOperationException();
     }
 
     @Override
-    SkyKey getSkyKeyInternal() {
+    protected SkyKey getSkyKeyInternal() {
       return SKY_KEY;
     }
   }