diff --git a/src/main/java/com/google/devtools/build/lib/bazel/rules/ninja/actions/NinjaActionsHelper.java b/src/main/java/com/google/devtools/build/lib/bazel/rules/ninja/actions/NinjaActionsHelper.java
index 3eae54d..e11511b 100644
--- a/src/main/java/com/google/devtools/build/lib/bazel/rules/ninja/actions/NinjaActionsHelper.java
+++ b/src/main/java/com/google/devtools/build/lib/bazel/rules/ninja/actions/NinjaActionsHelper.java
@@ -17,6 +17,7 @@
 import com.google.common.base.Preconditions;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableSortedMap;
+import com.google.common.collect.Sets;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.actions.Artifact.DerivedArtifact;
 import com.google.devtools.build.lib.actions.CommandLines;
@@ -36,7 +37,11 @@
 import com.google.devtools.build.lib.packages.TargetUtils;
 import com.google.devtools.build.lib.util.Pair;
 import com.google.devtools.build.lib.vfs.PathFragment;
+import java.util.ArrayDeque;
+import java.util.Collection;
 import java.util.List;
+import java.util.Set;
+import java.util.function.Consumer;
 import java.util.stream.Collectors;
 
 /**
@@ -48,12 +53,14 @@
   private final RuleContext ruleContext;
   private final List<String> outputRootInputs;
   private final ImmutableSortedMap<PathFragment, NinjaTarget> allUsualTargets;
-  private final ImmutableSortedMap<PathFragment, PhonyTarget<Artifact>> phonyTargets;
+  private final ImmutableSortedMap<PathFragment, PhonyTarget> phonyTargets;
 
   private final NinjaGraphArtifactsHelper artifactsHelper;
 
   private final PathFragment shellExecutable;
   private final ImmutableSortedMap<String, String> executionInfo;
+  private final PhonyTargetArtifacts phonyTargetArtifacts;
+  private final List<PathFragment> pathsToBuild;
 
   /**
    * Constructor
@@ -64,13 +71,18 @@
    *     paths under execroot/output_root.
    * @param allUsualTargets mapping of outputs to all non-phony Ninja targets from Ninja file
    * @param phonyTargets mapping of names to all phony Ninja actions from Ninja file
+   * @param phonyTargetArtifacts helper class for computing transitively included artifacts of phony
+   *     targets
+   * @param pathsToBuild paths requested by the user to be build (in output_groups attribute)
    */
   NinjaActionsHelper(
       RuleContext ruleContext,
       NinjaGraphArtifactsHelper artifactsHelper,
       List<String> outputRootInputs,
       ImmutableSortedMap<PathFragment, NinjaTarget> allUsualTargets,
-      ImmutableSortedMap<PathFragment, PhonyTarget<Artifact>> phonyTargets) {
+      ImmutableSortedMap<PathFragment, PhonyTarget> phonyTargets,
+      PhonyTargetArtifacts phonyTargetArtifacts,
+      List<PathFragment> pathsToBuild) {
     this.ruleContext = ruleContext;
     this.artifactsHelper = artifactsHelper;
     this.outputRootInputs = outputRootInputs;
@@ -78,6 +90,8 @@
     this.phonyTargets = phonyTargets;
     this.shellExecutable = ShToolchain.getPathOrError(ruleContext);
     this.executionInfo = createExecutionInfo(ruleContext);
+    this.phonyTargetArtifacts = phonyTargetArtifacts;
+    this.pathsToBuild = pathsToBuild;
   }
 
   void process() throws GenericParsingException {
@@ -113,8 +127,36 @@
   }
 
   private void createNinjaActions() throws GenericParsingException {
-    for (NinjaTarget target : allUsualTargets.values()) {
-      createNinjaAction(target);
+    // Traverse the action graph starting from the targets, specified by the user.
+    // Only create the required actions.
+    Set<PathFragment> visitedPaths = Sets.newHashSet();
+    Set<NinjaTarget> visitedTargets = Sets.newHashSet();
+    visitedPaths.addAll(pathsToBuild);
+    ArrayDeque<PathFragment> queue = new ArrayDeque<>(pathsToBuild);
+    Consumer<Collection<PathFragment>> enqueuer =
+        paths -> {
+          for (PathFragment input : paths) {
+            if (visitedPaths.add(input)) {
+              queue.add(input);
+            }
+          }
+        };
+    while (!queue.isEmpty()) {
+      PathFragment fragment = queue.remove();
+      NinjaTarget target = allUsualTargets.get(fragment);
+      if (target != null) {
+        if (visitedTargets.add(target)) {
+          createNinjaAction(target);
+        }
+        enqueuer.accept(target.getAllInputs());
+      } else {
+        PhonyTarget phonyTarget = phonyTargets.get(fragment);
+        // Phony target can be null, if the path in neither usual or phony target,
+        // but the source file.
+        if (phonyTarget != null) {
+          phonyTarget.visitUsualInputs(phonyTargets, enqueuer::accept);
+        }
+      }
     }
   }
 
@@ -158,9 +200,9 @@
       throws GenericParsingException {
     boolean isAlwaysDirty = false;
     for (PathFragment input : target.getAllInputs()) {
-      PhonyTarget<Artifact> phonyTarget = this.phonyTargets.get(input);
+      PhonyTarget phonyTarget = this.phonyTargets.get(input);
       if (phonyTarget != null) {
-        inputsBuilder.addTransitive(phonyTarget.getInputs());
+        inputsBuilder.addTransitive(phonyTargetArtifacts.getPhonyTargetArtifacts(input));
         isAlwaysDirty |= phonyTarget.isAlwaysDirty();
       } else {
         inputsBuilder.add(artifactsHelper.getInputArtifact(input));
diff --git a/src/main/java/com/google/devtools/build/lib/bazel/rules/ninja/actions/NinjaGraph.java b/src/main/java/com/google/devtools/build/lib/bazel/rules/ninja/actions/NinjaGraph.java
index cecfe2f..1555f9d 100644
--- a/src/main/java/com/google/devtools/build/lib/bazel/rules/ninja/actions/NinjaGraph.java
+++ b/src/main/java/com/google/devtools/build/lib/bazel/rules/ninja/actions/NinjaGraph.java
@@ -109,14 +109,13 @@
             outputRoot,
             workingDirectory,
             createSrcsMap(ruleContext),
-            createDepsMap(ruleContext),
-            pathsToBuild);
+            createDepsMap(ruleContext));
     if (ruleContext.hasErrors()) {
       return null;
     }
-    TargetsPreparer targetsPreparer = new TargetsPreparer();
 
     try {
+      TargetsPreparer targetsPreparer = new TargetsPreparer();
       List<Path> childNinjaFiles =
           ninjaSrcs.stream().map(Artifact::getPath).collect(Collectors.toList());
       Path workspace =
@@ -131,46 +130,51 @@
                   childNinjaFiles,
                   ownerTargetName)
               .pipeline(mainArtifact.getPath());
-      targetsPreparer.process(ninjaTargets, artifactsHelper);
+      targetsPreparer.process(ninjaTargets);
+      PhonyTargetArtifacts phonyTargetArtifacts =
+          new PhonyTargetArtifacts(targetsPreparer.getPhonyTargetsMap(), artifactsHelper);
       new NinjaActionsHelper(
               ruleContext,
               artifactsHelper,
               outputRootInputs,
               targetsPreparer.getUsualTargets(),
-              targetsPreparer.getPhonyTargetsMap())
+              targetsPreparer.getPhonyTargetsMap(),
+              phonyTargetArtifacts,
+              pathsToBuild)
           .process();
+
+      if (!checkOrphanArtifacts(ruleContext)) {
+        return null;
+      }
+
+      NestedSetBuilder<Artifact> filesToBuild = NestedSetBuilder.stableOrder();
+      TreeMap<String, NestedSet<Artifact>> groups = Maps.newTreeMap();
+      for (Map.Entry<String, List<String>> entry : outputGroupsMap.entrySet()) {
+        NestedSet<Artifact> artifacts =
+            getGroupArtifacts(
+                ruleContext,
+                entry.getValue(),
+                targetsPreparer.getPhonyTargetsMap(),
+                phonyTargetArtifacts,
+                artifactsHelper);
+        groups.put(entry.getKey(), artifacts);
+        filesToBuild.addTransitive(artifacts);
+      }
+
+      if (ruleContext.hasErrors()) {
+        return null;
+      }
+
+      return new RuleConfiguredTargetBuilder(ruleContext)
+          .addProvider(RunfilesProvider.class, RunfilesProvider.EMPTY)
+          .setFilesToBuild(filesToBuild.build())
+          .addOutputGroups(groups)
+          .build();
     } catch (GenericParsingException | IOException e) {
       // IOException is possible with reading Ninja file, describing the action graph.
       ruleContext.ruleError(e.getMessage());
       return null;
     }
-
-    if (!checkOrphanArtifacts(ruleContext)) {
-      return null;
-    }
-
-    NestedSetBuilder<Artifact> filesToBuild = NestedSetBuilder.stableOrder();
-    TreeMap<String, NestedSet<Artifact>> groups = Maps.newTreeMap();
-    for (Map.Entry<String, List<String>> entry : outputGroupsMap.entrySet()) {
-      NestedSet<Artifact> artifacts =
-          getGroupArtifacts(
-              ruleContext,
-              entry.getValue(),
-              targetsPreparer.getPhonyTargetsMap(),
-              artifactsHelper.getOutputsMap());
-      groups.put(entry.getKey(), artifacts);
-      filesToBuild.addTransitive(artifacts);
-    }
-
-    if (ruleContext.hasErrors()) {
-      return null;
-    }
-
-    return new RuleConfiguredTargetBuilder(ruleContext)
-        .addProvider(RunfilesProvider.class, RunfilesProvider.EMPTY)
-        .setFilesToBuild(filesToBuild.build())
-        .addOutputGroups(groups)
-        .build();
   }
 
   private static boolean checkOrphanArtifacts(RuleContext ruleContext) {
@@ -189,27 +193,24 @@
 
   private static class TargetsPreparer {
     private ImmutableSortedMap<PathFragment, NinjaTarget> usualTargets;
-    private ImmutableSortedMap<PathFragment, PhonyTarget<Artifact>> phonyTargetsMap;
+    private ImmutableSortedMap<PathFragment, PhonyTarget> phonyTargetsMap;
 
     public ImmutableSortedMap<PathFragment, NinjaTarget> getUsualTargets() {
       return usualTargets;
     }
 
-    public ImmutableSortedMap<PathFragment, PhonyTarget<Artifact>> getPhonyTargetsMap() {
+    public ImmutableSortedMap<PathFragment, PhonyTarget> getPhonyTargetsMap() {
       return phonyTargetsMap;
     }
 
-    void process(List<NinjaTarget> ninjaTargets, NinjaGraphArtifactsHelper artifactsHelper)
-        throws GenericParsingException {
+    void process(List<NinjaTarget> ninjaTargets) throws GenericParsingException {
       ImmutableSortedMap.Builder<PathFragment, NinjaTarget> usualTargetsBuilder =
           ImmutableSortedMap.naturalOrder();
       ImmutableSortedMap.Builder<PathFragment, NinjaTarget> phonyTargetsBuilder =
           ImmutableSortedMap.naturalOrder();
       separatePhonyTargets(ninjaTargets, usualTargetsBuilder, phonyTargetsBuilder);
       usualTargets = usualTargetsBuilder.build();
-      phonyTargetsMap =
-          NinjaPhonyTargetsUtil.getPhonyPathsMap(
-              phonyTargetsBuilder.build(), artifactsHelper::getInputArtifact);
+      phonyTargetsMap = NinjaPhonyTargetsUtil.getPhonyPathsMap(phonyTargetsBuilder.build());
     }
 
     private static void separatePhonyTargets(
@@ -268,16 +269,18 @@
   private static NestedSet<Artifact> getGroupArtifacts(
       RuleContext ruleContext,
       List<String> targets,
-      ImmutableSortedMap<PathFragment, PhonyTarget<Artifact>> phonyTargetsMap,
-      ImmutableSortedMap<PathFragment, Artifact> outputsMap) {
+      ImmutableSortedMap<PathFragment, PhonyTarget> phonyTargetsMap,
+      PhonyTargetArtifacts phonyTargetsArtifacts,
+      NinjaGraphArtifactsHelper artifactsHelper)
+      throws GenericParsingException {
     NestedSetBuilder<Artifact> nestedSetBuilder = NestedSetBuilder.stableOrder();
     for (String target : targets) {
       PathFragment path = PathFragment.create(target);
-      PhonyTarget<Artifact> phonyTarget = phonyTargetsMap.get(path);
-      if (phonyTarget != null) {
-        nestedSetBuilder.addTransitive(phonyTarget.getInputs());
+      if (phonyTargetsMap.containsKey(path)) {
+        NestedSet<Artifact> artifacts = phonyTargetsArtifacts.getPhonyTargetArtifacts(path);
+        nestedSetBuilder.addTransitive(artifacts);
       } else {
-        Artifact usualArtifact = outputsMap.get(path);
+        Artifact usualArtifact = artifactsHelper.createOutputArtifact(path);
         if (usualArtifact == null) {
           ruleContext.ruleError(
               String.format("Required target '%s' is not created in ninja_graph.", path));
diff --git a/src/main/java/com/google/devtools/build/lib/bazel/rules/ninja/actions/NinjaGraphArtifactsHelper.java b/src/main/java/com/google/devtools/build/lib/bazel/rules/ninja/actions/NinjaGraphArtifactsHelper.java
index 7d2455c..51a2674 100644
--- a/src/main/java/com/google/devtools/build/lib/bazel/rules/ninja/actions/NinjaGraphArtifactsHelper.java
+++ b/src/main/java/com/google/devtools/build/lib/bazel/rules/ninja/actions/NinjaGraphArtifactsHelper.java
@@ -17,7 +17,6 @@
 
 import com.google.common.base.Preconditions;
 import com.google.common.collect.ImmutableSortedMap;
-import com.google.common.collect.Maps;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.actions.Artifact.DerivedArtifact;
 import com.google.devtools.build.lib.actions.ArtifactRoot;
@@ -26,8 +25,6 @@
 import com.google.devtools.build.lib.vfs.Path;
 import com.google.devtools.build.lib.vfs.PathFragment;
 import com.google.devtools.build.lib.vfs.Root;
-import java.util.List;
-import java.util.SortedMap;
 
 /**
  * Helper class to create artifacts for {@link NinjaAction} to be used from {@link NinjaGraphRule}.
@@ -40,7 +37,6 @@
  */
 class NinjaGraphArtifactsHelper {
   private final RuleContext ruleContext;
-  private final List<PathFragment> pathsToBuild;
   private final Path outputRootInSources;
   private final PathFragment outputRootPath;
   private final PathFragment workingDirectory;
@@ -48,7 +44,6 @@
 
   private final ImmutableSortedMap<PathFragment, Artifact> depsNameToArtifact;
   private final ImmutableSortedMap<PathFragment, Artifact> srcsMap;
-  private final SortedMap<PathFragment, Artifact> outputsMap;
 
   /**
    * Constructor
@@ -61,7 +56,6 @@
    * @param srcsMap mapping between the path fragment and artifact for the files passed in 'srcs'
    *     attribute
    * @param depsNameToArtifact mapping between the path fragment in the Ninja file and prebuilt
-   * @param pathsToBuild list of paths to files required in output groups
    */
   NinjaGraphArtifactsHelper(
       RuleContext ruleContext,
@@ -69,15 +63,12 @@
       PathFragment outputRootPath,
       PathFragment workingDirectory,
       ImmutableSortedMap<PathFragment, Artifact> srcsMap,
-      ImmutableSortedMap<PathFragment, Artifact> depsNameToArtifact,
-      List<PathFragment> pathsToBuild) {
+      ImmutableSortedMap<PathFragment, Artifact> depsNameToArtifact) {
     this.ruleContext = ruleContext;
-    this.pathsToBuild = pathsToBuild;
     this.outputRootInSources =
         Preconditions.checkNotNull(sourceRoot.asPath()).getRelative(outputRootPath);
     this.outputRootPath = outputRootPath;
     this.workingDirectory = workingDirectory;
-    this.outputsMap = Maps.newTreeMap();
     this.srcsMap = srcsMap;
     this.depsNameToArtifact = depsNameToArtifact;
     Path execRoot =
@@ -105,9 +96,6 @@
     DerivedArtifact derivedArtifact =
         ruleContext.getDerivedArtifact(
             pathRelativeToWorkspaceRoot.relativeTo(outputRootPath), derivedOutputRoot);
-    if (pathsToBuild.contains(pathRelativeToWorkingDirectory)) {
-      outputsMap.put(pathRelativeToWorkingDirectory, derivedArtifact);
-    }
     return derivedArtifact;
   }
 
@@ -140,8 +128,4 @@
   public PathFragment getWorkingDirectory() {
     return workingDirectory;
   }
-
-  public ImmutableSortedMap<PathFragment, Artifact> getOutputsMap() {
-    return ImmutableSortedMap.copyOf(outputsMap);
-  }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/bazel/rules/ninja/actions/NinjaPhonyTargetsUtil.java b/src/main/java/com/google/devtools/build/lib/bazel/rules/ninja/actions/NinjaPhonyTargetsUtil.java
index d8c1933..e632836 100644
--- a/src/main/java/com/google/devtools/build/lib/bazel/rules/ninja/actions/NinjaPhonyTargetsUtil.java
+++ b/src/main/java/com/google/devtools/build/lib/bazel/rules/ninja/actions/NinjaPhonyTargetsUtil.java
@@ -18,6 +18,7 @@
 
 import com.google.common.annotations.VisibleForTesting;
 import com.google.common.base.Preconditions;
+import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableSortedMap;
 import com.google.common.collect.Iterables;
 import com.google.common.collect.Lists;
@@ -25,8 +26,6 @@
 import com.google.common.collect.Sets;
 import com.google.devtools.build.lib.bazel.rules.ninja.file.GenericParsingException;
 import com.google.devtools.build.lib.bazel.rules.ninja.parser.NinjaTarget;
-import com.google.devtools.build.lib.collect.nestedset.NestedSetBuilder;
-import com.google.devtools.build.lib.collect.nestedset.Order;
 import com.google.devtools.build.lib.util.Pair;
 import com.google.devtools.build.lib.vfs.PathFragment;
 import java.util.ArrayDeque;
@@ -35,7 +34,6 @@
 import java.util.Map;
 import java.util.Set;
 import java.util.SortedMap;
-import javax.annotation.Nullable;
 
 /**
  * An utility class for gathering non-phony input dependencies of phony {@link NinjaTarget} objects
@@ -48,10 +46,8 @@
   private NinjaPhonyTargetsUtil() {}
 
   @VisibleForTesting
-  public static <T> ImmutableSortedMap<PathFragment, PhonyTarget<T>> getPhonyPathsMap(
-      ImmutableSortedMap<PathFragment, NinjaTarget> phonyTargets,
-      InputArtifactCreator<T> artifactsHelper)
-      throws GenericParsingException {
+  public static ImmutableSortedMap<PathFragment, PhonyTarget> getPhonyPathsMap(
+      ImmutableSortedMap<PathFragment, NinjaTarget> phonyTargets) throws GenericParsingException {
     // There is always a DAG (or forest) of phony targets (as item can be included into several
     // phony targets).
     // This gives us the idea that we can compute any subgraph in the DAG independently, and
@@ -71,30 +67,30 @@
 
     checkState(topoOrderedTargets.size() == phonyTargets.size());
 
-    SortedMap<PathFragment, PhonyTarget<T>> result = Maps.newTreeMap();
+    SortedMap<PathFragment, PhonyTarget> result = Maps.newTreeMap();
     for (NinjaTarget target : topoOrderedTargets) {
       PathFragment onlyOutput = Iterables.getOnlyElement(target.getAllOutputs());
-      NestedSetBuilder<T> builder = new NestedSetBuilder<>(Order.STABLE_ORDER);
+      ImmutableList.Builder<PathFragment> phonyNames = ImmutableList.builder();
+      ImmutableList.Builder<PathFragment> directInputs = ImmutableList.builder();
       Collection<PathFragment> allInputs = target.getAllInputs();
       boolean isAlwaysDirty = allInputs.isEmpty();
       for (PathFragment input : allInputs) {
         NinjaTarget phonyInput = phonyTargets.get(input);
         if (phonyInput != null) {
           // The input is the other phony target.
-          // Add the corresponding already computed NestedSet as transitive.
           // Phony target must have only one output (alias); it is checked during parsing.
           PathFragment phonyName = Iterables.getOnlyElement(phonyInput.getAllOutputs());
-          PhonyTarget<T> alreadyComputed = result.get(phonyName);
+          PhonyTarget alreadyComputed = result.get(phonyName);
           Preconditions.checkNotNull(alreadyComputed);
           isAlwaysDirty |= alreadyComputed.isAlwaysDirty();
-          builder.addTransitive(alreadyComputed.getInputs());
+          phonyNames.add(Iterables.getOnlyElement(phonyInput.getAllOutputs()));
         } else {
           // The input is the usual file.
-          // We do not check for the duplicates, this would make NestedSet optimization senseless.
-          builder.add(artifactsHelper.createArtifact(input));
+          directInputs.add(input);
         }
       }
-      result.put(onlyOutput, new PhonyTarget<>(builder.build(), isAlwaysDirty));
+      result.put(
+          onlyOutput, new PhonyTarget(phonyNames.build(), directInputs.build(), isAlwaysDirty));
     }
 
     return ImmutableSortedMap.copyOf(result);
@@ -154,13 +150,4 @@
     }
     return fragment;
   }
-
-  /**
-   * Helper interface for artifact creation. We do not pass NinjaArtifactsHelper directly to keep
-   * tests simpler.
-   */
-  public interface InputArtifactCreator<T> {
-    @Nullable
-    T createArtifact(PathFragment pathFragment) throws GenericParsingException;
-  }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/bazel/rules/ninja/actions/PhonyTarget.java b/src/main/java/com/google/devtools/build/lib/bazel/rules/ninja/actions/PhonyTarget.java
index 462d985..1d7e969 100644
--- a/src/main/java/com/google/devtools/build/lib/bazel/rules/ninja/actions/PhonyTarget.java
+++ b/src/main/java/com/google/devtools/build/lib/bazel/rules/ninja/actions/PhonyTarget.java
@@ -14,14 +14,20 @@
 
 package com.google.devtools.build.lib.bazel.rules.ninja.actions;
 
-import com.google.devtools.build.lib.collect.nestedset.NestedSet;
+import com.google.common.base.Preconditions;
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableSortedMap;
+import com.google.common.collect.Sets;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
+import com.google.devtools.build.lib.vfs.PathFragment;
+import java.util.ArrayDeque;
+import java.util.Set;
+import java.util.function.Consumer;
 
 /**
- * Helper class to represent "evaluated" phony target: it contains the NestedSet with all non-phony
- * inputs to the phony target (with Artifacts for the real computation, and PathFragments for the
- * tests); and it contains the flag whether this phony target is always dirty, i.e. must be rebuild
- * each time.
+ * Helper class to represent "evaluated" phony target: it contains the List with direct non-phony
+ * inputs to the phony target (PathFragments), the list with direct phony inputs; and it contains
+ * the flag whether this phony target is always dirty, i.e. must be rebuild each time.
  *
  * <p>Always-dirty phony targets are those which do not have any inputs: "build alias: phony". All
  * usual direct dependants of those actions automatically also always-dirty (but not the transitive
@@ -30,24 +36,48 @@
  * themselves always-dirty.</b> That is why we can compute the always-dirty flag for the phony
  * targets, and use it for marking their direct non-phony dependants as actions to be executed
  * unconditionally.
- *
- * @param <T> either Artifact or PathFragment
  */
 @Immutable
-public final class PhonyTarget<T> {
-  private final NestedSet<T> inputs;
+public final class PhonyTarget {
+  private final ImmutableList<PathFragment> phonyNames;
+  private final ImmutableList<PathFragment> directUsualInputs;
   private final boolean isAlwaysDirty;
 
-  public PhonyTarget(NestedSet<T> inputs, boolean isAlwaysDirty) {
-    this.inputs = inputs;
+  public PhonyTarget(
+      ImmutableList<PathFragment> phonyNames,
+      ImmutableList<PathFragment> directUsualInputs,
+      boolean isAlwaysDirty) {
+    this.phonyNames = phonyNames;
+    this.directUsualInputs = directUsualInputs;
     this.isAlwaysDirty = isAlwaysDirty;
   }
 
-  public NestedSet<T> getInputs() {
-    return inputs;
+  public ImmutableList<PathFragment> getPhonyNames() {
+    return phonyNames;
+  }
+
+  public ImmutableList<PathFragment> getDirectUsualInputs() {
+    return directUsualInputs;
   }
 
   public boolean isAlwaysDirty() {
     return isAlwaysDirty;
   }
+
+  public void visitUsualInputs(
+      ImmutableSortedMap<PathFragment, PhonyTarget> phonyTargetsMap,
+      Consumer<ImmutableList<PathFragment>> consumer) {
+    consumer.accept(directUsualInputs);
+
+    ArrayDeque<PathFragment> queue = new ArrayDeque<>(phonyNames);
+    Set<PathFragment> visited = Sets.newHashSet();
+    while (!queue.isEmpty()) {
+      PathFragment fragment = queue.remove();
+      if (visited.add(fragment)) {
+        PhonyTarget phonyTarget = Preconditions.checkNotNull(phonyTargetsMap.get(fragment));
+        consumer.accept(phonyTarget.getDirectUsualInputs());
+        queue.addAll(phonyTarget.getPhonyNames());
+      }
+    }
+  }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/bazel/rules/ninja/actions/PhonyTargetArtifacts.java b/src/main/java/com/google/devtools/build/lib/bazel/rules/ninja/actions/PhonyTargetArtifacts.java
new file mode 100644
index 0000000..ef6d12c
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/bazel/rules/ninja/actions/PhonyTargetArtifacts.java
@@ -0,0 +1,69 @@
+// Copyright 2020 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.bazel.rules.ninja.actions;
+
+import com.google.common.base.Preconditions;
+import com.google.common.collect.ImmutableSortedMap;
+import com.google.common.collect.Maps;
+import com.google.devtools.build.lib.actions.Artifact;
+import com.google.devtools.build.lib.bazel.rules.ninja.file.GenericParsingException;
+import com.google.devtools.build.lib.collect.nestedset.NestedSet;
+import com.google.devtools.build.lib.collect.nestedset.NestedSetBuilder;
+import com.google.devtools.build.lib.vfs.PathFragment;
+import java.util.Map;
+import javax.annotation.concurrent.ThreadSafe;
+
+/**
+ * Helper class for caching computation of transitive inclusion of usual targets into phony. (We can
+ * not compute all artifacts for all phony targets because some of them may not be created by a
+ * subgraph of required actions.)
+ */
+@ThreadSafe
+public class PhonyTargetArtifacts {
+  private final Map<PathFragment, NestedSet<Artifact>> cache;
+  private final ImmutableSortedMap<PathFragment, PhonyTarget> phonyTargetsMap;
+  private final NinjaGraphArtifactsHelper artifactsHelper;
+
+  public PhonyTargetArtifacts(
+      ImmutableSortedMap<PathFragment, PhonyTarget> phonyTargetsMap,
+      NinjaGraphArtifactsHelper artifactsHelper) {
+    this.phonyTargetsMap = phonyTargetsMap;
+    this.artifactsHelper = artifactsHelper;
+    cache = Maps.newHashMap();
+  }
+
+  NestedSet<Artifact> getPhonyTargetArtifacts(PathFragment name) throws GenericParsingException {
+    NestedSet<Artifact> existing = cache.get(name);
+    if (existing != null) {
+      return existing;
+    }
+    PhonyTarget phonyTarget = phonyTargetsMap.get(name);
+    Preconditions.checkNotNull(phonyTarget);
+    NestedSetBuilder<Artifact> builder = NestedSetBuilder.stableOrder();
+    for (PathFragment input : phonyTarget.getDirectUsualInputs()) {
+      builder.add(artifactsHelper.getInputArtifact(input));
+    }
+    for (PathFragment phonyName : phonyTarget.getPhonyNames()) {
+      // We already checked for cycles during loading.
+      NestedSet<Artifact> nestedSet = getPhonyTargetArtifacts(phonyName);
+      builder.addTransitive(nestedSet);
+    }
+    NestedSet<Artifact> value = builder.build();
+    // We do not hold the lock during the computation, so deadlocks are not possible,
+    // however duplicate computations are possible.
+    cache.put(name, value);
+    return value;
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/bazel/rules/ninja/parser/NinjaTarget.java b/src/main/java/com/google/devtools/build/lib/bazel/rules/ninja/parser/NinjaTarget.java
index b18192b5..1bcd12e 100644
--- a/src/main/java/com/google/devtools/build/lib/bazel/rules/ninja/parser/NinjaTarget.java
+++ b/src/main/java/com/google/devtools/build/lib/bazel/rules/ninja/parser/NinjaTarget.java
@@ -21,6 +21,7 @@
 import com.google.errorprone.annotations.Immutable;
 import java.util.Collection;
 import java.util.List;
+import java.util.Objects;
 import java.util.stream.Collectors;
 
 /** Ninja target (build statement) representation. */
@@ -182,6 +183,25 @@
         + prettyPrintPaths("\n|| ", getOrderOnlyInputs());
   }
 
+  @Override
+  public boolean equals(Object o) {
+    if (this == o) {
+      return true;
+    }
+    if (o == null || getClass() != o.getClass()) {
+      return false;
+    }
+    NinjaTarget that = (NinjaTarget) o;
+    // Note: NinjaScope is compared with default Object#equals; it is enough
+    // because we do not do any copies of NinjaScope.
+    return offset == that.offset && scope.equals(that.scope);
+  }
+
+  @Override
+  public int hashCode() {
+    return Objects.hash(scope, offset);
+  }
+
   private static String prettyPrintPaths(String startDelimiter, Collection<PathFragment> paths) {
     if (paths.isEmpty()) {
       return "";
diff --git a/src/test/java/com/google/devtools/build/lib/bazel/rules/ninja/NinjaGraphTest.java b/src/test/java/com/google/devtools/build/lib/bazel/rules/ninja/NinjaGraphTest.java
index 6563072..f4c805e 100644
--- a/src/test/java/com/google/devtools/build/lib/bazel/rules/ninja/NinjaGraphTest.java
+++ b/src/test/java/com/google/devtools/build/lib/bazel/rules/ninja/NinjaGraphTest.java
@@ -75,7 +75,8 @@
             "graph",
             "ninja_graph(name = 'graph', output_root = 'build_config',",
             " main = 'build_config/build.ninja',",
-            " output_root_inputs = ['input.txt'])");
+            " output_root_inputs = ['input.txt'],",
+            " output_groups= {'main': ['build_config/hello.txt']})");
     assertThat(configuredTarget).isInstanceOf(RuleConfiguredTarget.class);
     RuleConfiguredTarget ninjaConfiguredTarget = (RuleConfiguredTarget) configuredTarget;
     ImmutableList<ActionAnalysisMetadata> actions = ninjaConfiguredTarget.getActions();
@@ -128,7 +129,7 @@
             "ninja_graph(name = 'graph', output_root = 'build_config',",
             " working_directory = 'build_config',",
             " main = 'build_config/build.ninja',",
-            " output_root_inputs = ['input.txt'])");
+            " output_root_inputs = ['input.txt'], output_groups= {'main': ['alias']})");
     assertThat(configuredTarget).isInstanceOf(RuleConfiguredTarget.class);
     RuleConfiguredTarget ninjaConfiguredTarget = (RuleConfiguredTarget) configuredTarget;
     ImmutableList<ActionAnalysisMetadata> actions = ninjaConfiguredTarget.getActions();
@@ -198,7 +199,8 @@
             "ninja_graph(name = 'graph', output_root = 'build_config',",
             " working_directory = 'build_config',",
             " main = 'build_config/build.ninja',",
-            " output_root_inputs = ['a.txt', 'b.txt', 'c.txt', 'd.txt', 'e.txt'])");
+            " output_root_inputs = ['a.txt', 'b.txt', 'c.txt', 'd.txt', 'e.txt'],",
+            " output_groups= {'main': ['alias']})");
     assertThat(configuredTarget).isInstanceOf(RuleConfiguredTarget.class);
     RuleConfiguredTarget ninjaConfiguredTarget = (RuleConfiguredTarget) configuredTarget;
     ImmutableList<ActionAnalysisMetadata> actions = ninjaConfiguredTarget.getActions();
@@ -290,7 +292,8 @@
             "ninja_graph(name = 'graph', output_root = 'build_config',",
             " working_directory = 'build_config',",
             " main = 'build_config/build.ninja',",
-            " deps_mapping = {'placeholder': ':input.txt'})");
+            " deps_mapping = {'placeholder': ':input.txt'},",
+            " output_groups= {'main': ['hello.txt']})");
     assertThat(configuredTarget).isInstanceOf(RuleConfiguredTarget.class);
     RuleConfiguredTarget ninjaConfiguredTarget = (RuleConfiguredTarget) configuredTarget;
     ImmutableList<ActionAnalysisMetadata> actions = ninjaConfiguredTarget.getActions();
@@ -308,4 +311,62 @@
     assertThat(ninjaAction.getPrimaryOutput().getExecPathString())
         .isEqualTo("build_config/hello.txt");
   }
+
+  @Test
+  public void testOnlySubGraphIsCreated() throws Exception {
+    rewriteWorkspace(
+        "workspace(name = 'test')",
+        "dont_symlink_directories_in_execroot(paths = ['build_config'])");
+
+    scratch.file("build_config/a.txt", "A");
+    scratch.file("build_config/b.txt", "B");
+    scratch.file("build_config/c.txt", "C");
+    scratch.file("build_config/d.txt", "D");
+    scratch.file("build_config/e.txt", "E");
+
+    scratch.file(
+        "build_config/build.ninja",
+        "rule cat",
+        "  command = cat ${in} > ${out}",
+        "rule echo",
+        "  command = echo \"Hello $$(cat ${in} | tr '\\r\\n' ' ')!\" > ${out}",
+        "build a: cat a.txt",
+        "build b: cat b.txt",
+        "build c: cat c.txt",
+        "build d: cat d.txt",
+        "build e: cat e.txt",
+        "build group1: phony a b c",
+        "build group2: phony d e",
+        "build inputs_alias: phony group1 group2",
+        "build hello.txt: echo inputs_alias",
+        "build alias: phony hello.txt");
+
+    ConfiguredTarget configuredTarget =
+        scratchConfiguredTarget(
+            "",
+            "graph",
+            "ninja_graph(name = 'graph', output_root = 'build_config',",
+            " working_directory = 'build_config',",
+            " main = 'build_config/build.ninja',",
+            " output_root_inputs = ['a.txt', 'b.txt', 'c.txt', 'd.txt', 'e.txt'],",
+            " output_groups= {'main': ['group1']})");
+    assertThat(configuredTarget).isInstanceOf(RuleConfiguredTarget.class);
+    RuleConfiguredTarget ninjaConfiguredTarget = (RuleConfiguredTarget) configuredTarget;
+    ImmutableList<ActionAnalysisMetadata> actions = ninjaConfiguredTarget.getActions();
+    assertThat(actions).hasSize(8);
+    List<String> outputs = Lists.newArrayList();
+    actions.forEach(a -> outputs.add(Iterables.getOnlyElement(a.getOutputs()).getExecPathString()));
+    assertThat(outputs)
+        .containsExactlyElementsIn(
+            new String[] {
+              "build_config/a.txt",
+              "build_config/b.txt",
+              "build_config/c.txt",
+              "build_config/d.txt",
+              "build_config/e.txt",
+              "build_config/a",
+              "build_config/b",
+              "build_config/c",
+            });
+  }
 }
diff --git a/src/test/java/com/google/devtools/build/lib/bazel/rules/ninja/NinjaPhonyTargetsUtilTest.java b/src/test/java/com/google/devtools/build/lib/bazel/rules/ninja/NinjaPhonyTargetsUtilTest.java
index 49e5f31..059bfea 100644
--- a/src/test/java/com/google/devtools/build/lib/bazel/rules/ninja/NinjaPhonyTargetsUtilTest.java
+++ b/src/test/java/com/google/devtools/build/lib/bazel/rules/ninja/NinjaPhonyTargetsUtilTest.java
@@ -19,6 +19,7 @@
 
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableSortedMap;
+import com.google.common.collect.ImmutableSortedSet;
 import com.google.common.collect.Iterables;
 import com.google.devtools.build.lib.bazel.rules.ninja.actions.NinjaPhonyTargetsUtil;
 import com.google.devtools.build.lib.bazel.rules.ninja.actions.PhonyTarget;
@@ -52,8 +53,8 @@
             "build alias3: phony alias4 direct4 direct5",
             "build alias4: phony alias2");
 
-    ImmutableSortedMap<PathFragment, PhonyTarget<PathFragment>> pathsMap =
-        NinjaPhonyTargetsUtil.getPhonyPathsMap(buildPhonyTargets(targetTexts), pf -> pf);
+    ImmutableSortedMap<PathFragment, PhonyTarget> pathsMap =
+        NinjaPhonyTargetsUtil.getPhonyPathsMap(buildPhonyTargets(targetTexts));
 
     assertThat(pathsMap).hasSize(4);
     checkMapping(pathsMap, "alias9", "direct1", "direct2", "direct3", "direct4", "direct5");
@@ -72,8 +73,8 @@
             "build deep1: phony leaf1",
             "build deep2: phony leaf2 alias1");
 
-    ImmutableSortedMap<PathFragment, PhonyTarget<PathFragment>> pathsMap =
-        NinjaPhonyTargetsUtil.getPhonyPathsMap(buildPhonyTargets(targetTexts), pf -> pf);
+    ImmutableSortedMap<PathFragment, PhonyTarget> pathsMap =
+        NinjaPhonyTargetsUtil.getPhonyPathsMap(buildPhonyTargets(targetTexts));
 
     assertThat(pathsMap).hasSize(5);
     checkMapping(pathsMap, "_alias9", "leaf1", "leaf2");
@@ -93,8 +94,8 @@
             // alias4 is always-dirty
             "build alias4: phony");
 
-    ImmutableSortedMap<PathFragment, PhonyTarget<PathFragment>> pathsMap =
-        NinjaPhonyTargetsUtil.getPhonyPathsMap(buildPhonyTargets(targetTexts), pf -> pf);
+    ImmutableSortedMap<PathFragment, PhonyTarget> pathsMap =
+        NinjaPhonyTargetsUtil.getPhonyPathsMap(buildPhonyTargets(targetTexts));
 
     assertThat(pathsMap).hasSize(4);
     // alias4 and its transitive closure is always-dirty
@@ -105,23 +106,24 @@
   }
 
   private static void checkMapping(
-      ImmutableSortedMap<PathFragment, PhonyTarget<PathFragment>> pathsMap,
-      String key,
-      String... values) {
+      ImmutableSortedMap<PathFragment, PhonyTarget> pathsMap, String key, String... values) {
     checkMapping(pathsMap, key, false, values);
   }
 
   private static void checkMapping(
-      ImmutableSortedMap<PathFragment, PhonyTarget<PathFragment>> pathsMap,
+      ImmutableSortedMap<PathFragment, PhonyTarget> pathsMap,
       String key,
       boolean isAlwaysDirty,
       String... values) {
     Set<PathFragment> expectedPaths =
         Arrays.stream(values).map(PathFragment::create).collect(Collectors.toSet());
-    PhonyTarget<PathFragment> phonyTarget = pathsMap.get(PathFragment.create(key));
+    PhonyTarget phonyTarget = pathsMap.get(PathFragment.create(key));
     assertThat(phonyTarget).isNotNull();
     assertThat(phonyTarget.isAlwaysDirty()).isEqualTo(isAlwaysDirty);
-    assertThat(phonyTarget.getInputs().toSet()).containsExactlyElementsIn(expectedPaths);
+
+    ImmutableSortedSet.Builder<PathFragment> paths = ImmutableSortedSet.naturalOrder();
+    pathsMap.get(PathFragment.create(key)).visitUsualInputs(pathsMap, paths::addAll);
+    assertThat(paths.build()).containsExactlyElementsIn(expectedPaths);
   }
 
   private static ImmutableSortedMap<PathFragment, NinjaTarget> buildPhonyTargets(
@@ -137,7 +139,7 @@
 
   @Test
   public void testEmptyMap() throws Exception {
-    assertThat(NinjaPhonyTargetsUtil.getPhonyPathsMap(ImmutableSortedMap.of(), pf -> pf)).isEmpty();
+    assertThat(NinjaPhonyTargetsUtil.getPhonyPathsMap(ImmutableSortedMap.of())).isEmpty();
   }
 
   @Test
@@ -149,7 +151,7 @@
     GenericParsingException exception =
         assertThrows(
             GenericParsingException.class,
-            () -> NinjaPhonyTargetsUtil.getPhonyPathsMap(buildPhonyTargets(targetTexts), pf -> pf));
+            () -> NinjaPhonyTargetsUtil.getPhonyPathsMap(buildPhonyTargets(targetTexts)));
     assertThat(exception)
         .hasMessageThat()
         .isEqualTo("Detected a dependency cycle involving the phony target 'alias1'");