diff --git a/src/main/java/com/google/devtools/build/lib/bazel/rules/ninja/actions/NinjaAction.java b/src/main/java/com/google/devtools/build/lib/bazel/rules/ninja/actions/NinjaAction.java
index d28fda7..ff3efc2 100644
--- a/src/main/java/com/google/devtools/build/lib/bazel/rules/ninja/actions/NinjaAction.java
+++ b/src/main/java/com/google/devtools/build/lib/bazel/rules/ninja/actions/NinjaAction.java
@@ -44,7 +44,8 @@
       CommandLines commandLines,
       ActionEnvironment env,
       ImmutableMap<String, String> executionInfo,
-      RunfilesSupplier runfilesSupplier) {
+      RunfilesSupplier runfilesSupplier,
+      boolean executeUnconditionally) {
     super(
         /* owner= */ owner,
         /* tools= */ tools,
@@ -60,7 +61,7 @@
         /* progressMessage= */ createProgressMessage(outputs),
         /* runfilesSupplier= */ runfilesSupplier,
         /* mnemonic= */ MNEMONIC,
-        /* executeUnconditionally= */ false,
+        /* executeUnconditionally= */ executeUnconditionally,
         /* extraActionInfoSupplier= */ null,
         /* resultConsumer= */ null);
   }
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 5fa8af8..48b3915 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
@@ -31,7 +31,6 @@
 import com.google.devtools.build.lib.bazel.rules.ninja.parser.NinjaScope;
 import com.google.devtools.build.lib.bazel.rules.ninja.parser.NinjaTarget;
 import com.google.devtools.build.lib.bazel.rules.ninja.parser.NinjaVariableValue;
-import com.google.devtools.build.lib.collect.nestedset.NestedSet;
 import com.google.devtools.build.lib.collect.nestedset.NestedSetBuilder;
 import com.google.devtools.build.lib.collect.nestedset.Order;
 import com.google.devtools.build.lib.packages.TargetUtils;
@@ -49,7 +48,7 @@
   private final RuleContext ruleContext;
   private final List<String> outputRootInputs;
   private final ImmutableSortedMap<PathFragment, NinjaTarget> allUsualTargets;
-  private final ImmutableSortedMap<PathFragment, NestedSet<Artifact>> phonyTargets;
+  private final ImmutableSortedMap<PathFragment, PhonyTarget<Artifact>> phonyTargets;
 
   private final NinjaGraphArtifactsHelper artifactsHelper;
 
@@ -71,7 +70,7 @@
       NinjaGraphArtifactsHelper artifactsHelper,
       List<String> outputRootInputs,
       ImmutableSortedMap<PathFragment, NinjaTarget> allUsualTargets,
-      ImmutableSortedMap<PathFragment, NestedSet<Artifact>> phonyTargets) {
+      ImmutableSortedMap<PathFragment, PhonyTarget<Artifact>> phonyTargets) {
     this.ruleContext = ruleContext;
     this.artifactsHelper = artifactsHelper;
     this.outputRootInputs = outputRootInputs;
@@ -117,7 +116,7 @@
 
     NestedSetBuilder<Artifact> inputsBuilder = NestedSetBuilder.stableOrder();
     ImmutableList.Builder<Artifact> outputsBuilder = ImmutableList.builder();
-    fillArtifacts(target, inputsBuilder, outputsBuilder);
+    boolean isAlwaysDirty = fillArtifacts(target, inputsBuilder, outputsBuilder);
 
     NinjaScope targetScope = createTargetScope(target);
     int targetOffset = target.getOffset();
@@ -140,18 +139,22 @@
             commandLines,
             Preconditions.checkNotNull(ruleContext.getConfiguration()).getActionEnvironment(),
             executionInfo,
-            EmptyRunfilesSupplier.INSTANCE));
+            EmptyRunfilesSupplier.INSTANCE,
+            isAlwaysDirty));
   }
 
-  private void fillArtifacts(
+  /** Returns true is the action shpould be marked as always dirty. */
+  private boolean fillArtifacts(
       NinjaTarget target,
       NestedSetBuilder<Artifact> inputsBuilder,
       ImmutableList.Builder<Artifact> outputsBuilder)
       throws GenericParsingException {
+    boolean isAlwaysDirty = false;
     for (PathFragment input : target.getAllInputs()) {
-      NestedSet<Artifact> nestedSet = this.phonyTargets.get(input);
-      if (nestedSet != null) {
-        inputsBuilder.addTransitive(nestedSet);
+      PhonyTarget<Artifact> phonyTarget = this.phonyTargets.get(input);
+      if (phonyTarget != null) {
+        inputsBuilder.addTransitive(phonyTarget.getInputs());
+        isAlwaysDirty |= phonyTarget.isAlwaysDirty();
       } else {
         inputsBuilder.add(artifactsHelper.getInputArtifact(input));
       }
@@ -160,6 +163,7 @@
     for (PathFragment output : target.getAllOutputs()) {
       outputsBuilder.add(artifactsHelper.createOutputArtifact(output));
     }
+    return isAlwaysDirty;
   }
 
   private void maybeCreateRspFile(
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 9c049a6..cecfe2f 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
@@ -189,13 +189,13 @@
 
   private static class TargetsPreparer {
     private ImmutableSortedMap<PathFragment, NinjaTarget> usualTargets;
-    private ImmutableSortedMap<PathFragment, NestedSet<Artifact>> phonyTargetsMap;
+    private ImmutableSortedMap<PathFragment, PhonyTarget<Artifact>> phonyTargetsMap;
 
     public ImmutableSortedMap<PathFragment, NinjaTarget> getUsualTargets() {
       return usualTargets;
     }
 
-    public ImmutableSortedMap<PathFragment, NestedSet<Artifact>> getPhonyTargetsMap() {
+    public ImmutableSortedMap<PathFragment, PhonyTarget<Artifact>> getPhonyTargetsMap() {
       return phonyTargetsMap;
     }
 
@@ -268,14 +268,14 @@
   private static NestedSet<Artifact> getGroupArtifacts(
       RuleContext ruleContext,
       List<String> targets,
-      ImmutableSortedMap<PathFragment, NestedSet<Artifact>> phonyTargetsMap,
+      ImmutableSortedMap<PathFragment, PhonyTarget<Artifact>> phonyTargetsMap,
       ImmutableSortedMap<PathFragment, Artifact> outputsMap) {
     NestedSetBuilder<Artifact> nestedSetBuilder = NestedSetBuilder.stableOrder();
     for (String target : targets) {
       PathFragment path = PathFragment.create(target);
-      NestedSet<Artifact> artifacts = phonyTargetsMap.get(path);
-      if (artifacts != null) {
-        nestedSetBuilder.addTransitive(artifacts);
+      PhonyTarget<Artifact> phonyTarget = phonyTargetsMap.get(path);
+      if (phonyTarget != null) {
+        nestedSetBuilder.addTransitive(phonyTarget.getInputs());
       } else {
         Artifact usualArtifact = outputsMap.get(path);
         if (usualArtifact == null) {
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 9a40bea..d8c1933 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
@@ -25,12 +25,12 @@
 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.NestedSet;
 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;
+import java.util.Collection;
 import java.util.List;
 import java.util.Map;
 import java.util.Set;
@@ -48,7 +48,7 @@
   private NinjaPhonyTargetsUtil() {}
 
   @VisibleForTesting
-  public static <T> ImmutableSortedMap<PathFragment, NestedSet<T>> getPhonyPathsMap(
+  public static <T> ImmutableSortedMap<PathFragment, PhonyTarget<T>> getPhonyPathsMap(
       ImmutableSortedMap<PathFragment, NinjaTarget> phonyTargets,
       InputArtifactCreator<T> artifactsHelper)
       throws GenericParsingException {
@@ -71,26 +71,30 @@
 
     checkState(topoOrderedTargets.size() == phonyTargets.size());
 
-    SortedMap<PathFragment, NestedSet<T>> result = Maps.newTreeMap();
+    SortedMap<PathFragment, PhonyTarget<T>> result = Maps.newTreeMap();
     for (NinjaTarget target : topoOrderedTargets) {
+      PathFragment onlyOutput = Iterables.getOnlyElement(target.getAllOutputs());
       NestedSetBuilder<T> builder = new NestedSetBuilder<>(Order.STABLE_ORDER);
-      for (PathFragment input : target.getAllInputs()) {
+      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());
-          NestedSet<T> alreadyComputedSet = result.get(phonyName);
-          Preconditions.checkNotNull(alreadyComputedSet);
-          builder.addTransitive(alreadyComputedSet);
+          PhonyTarget<T> alreadyComputed = result.get(phonyName);
+          Preconditions.checkNotNull(alreadyComputed);
+          isAlwaysDirty |= alreadyComputed.isAlwaysDirty();
+          builder.addTransitive(alreadyComputed.getInputs());
         } 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));
         }
       }
-      result.put(Iterables.getOnlyElement(target.getAllOutputs()), builder.build());
+      result.put(onlyOutput, new PhonyTarget<>(builder.build(), isAlwaysDirty));
     }
 
     return ImmutableSortedMap.copyOf(result);
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
new file mode 100644
index 0000000..462d985
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/bazel/rules/ninja/actions/PhonyTarget.java
@@ -0,0 +1,53 @@
+// 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.devtools.build.lib.collect.nestedset.NestedSet;
+import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
+
+/**
+ * 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.
+ *
+ * <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
+ * dependants: they should check whether their computed inputs have changed). As phony targets are
+ * not performing any actions, <b>all phony transitive dependants of always-dirty phony targets are
+ * 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;
+  private final boolean isAlwaysDirty;
+
+  public PhonyTarget(NestedSet<T> inputs, boolean isAlwaysDirty) {
+    this.inputs = inputs;
+    this.isAlwaysDirty = isAlwaysDirty;
+  }
+
+  public NestedSet<T> getInputs() {
+    return inputs;
+  }
+
+  public boolean isAlwaysDirty() {
+    return isAlwaysDirty;
+  }
+}
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 79460f6..09703f4 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
@@ -182,7 +182,9 @@
         "build b: cat b.txt",
         "build c: cat c.txt",
         "build d: cat d.txt",
-        "build e: cat e.txt",
+        // e should be executed unconditionally as it depends on always-dirty phony action
+        "build e: cat e.txt always_dirty",
+        "build always_dirty: phony",
         "build group1: phony a b c",
         "build group2: phony d e",
         "build inputs_alias: phony group1 group2",
@@ -255,6 +257,15 @@
         assertThat(execRootPath.getParentDirectory())
             .isEqualTo(PathFragment.create("build_config"));
         assertThat(execRootPath.getFileExtension()).isEqualTo("txt");
+      } else if ("e".equals(artifact.getFilename())) {
+        assertThat(action).isInstanceOf(NinjaAction.class);
+        NinjaAction ninjaAction = (NinjaAction) action;
+        List<CommandLineAndParamFileInfo> commandLines =
+            ninjaAction.getCommandLines().getCommandLines();
+        assertThat(commandLines).hasSize(1);
+        assertThat(commandLines.get(0).commandLine.toString())
+            .endsWith("cd build_config && cat e.txt always_dirty > e");
+        assertThat(ninjaAction.executeUnconditionally()).isTrue();
       }
     }
   }
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 39fdcb8..49e5f31 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
@@ -21,13 +21,13 @@
 import com.google.common.collect.ImmutableSortedMap;
 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;
 import com.google.devtools.build.lib.bazel.rules.ninja.file.ByteBufferFragment;
 import com.google.devtools.build.lib.bazel.rules.ninja.file.GenericParsingException;
 import com.google.devtools.build.lib.bazel.rules.ninja.lexer.NinjaLexer;
 import com.google.devtools.build.lib.bazel.rules.ninja.parser.NinjaParserStep;
 import com.google.devtools.build.lib.bazel.rules.ninja.parser.NinjaScope;
 import com.google.devtools.build.lib.bazel.rules.ninja.parser.NinjaTarget;
-import com.google.devtools.build.lib.collect.nestedset.NestedSet;
 import com.google.devtools.build.lib.vfs.PathFragment;
 import java.nio.ByteBuffer;
 import java.nio.charset.StandardCharsets;
@@ -52,7 +52,7 @@
             "build alias3: phony alias4 direct4 direct5",
             "build alias4: phony alias2");
 
-    ImmutableSortedMap<PathFragment, NestedSet<PathFragment>> pathsMap =
+    ImmutableSortedMap<PathFragment, PhonyTarget<PathFragment>> pathsMap =
         NinjaPhonyTargetsUtil.getPhonyPathsMap(buildPhonyTargets(targetTexts), pf -> pf);
 
     assertThat(pathsMap).hasSize(4);
@@ -72,7 +72,7 @@
             "build deep1: phony leaf1",
             "build deep2: phony leaf2 alias1");
 
-    ImmutableSortedMap<PathFragment, NestedSet<PathFragment>> pathsMap =
+    ImmutableSortedMap<PathFragment, PhonyTarget<PathFragment>> pathsMap =
         NinjaPhonyTargetsUtil.getPhonyPathsMap(buildPhonyTargets(targetTexts), pf -> pf);
 
     assertThat(pathsMap).hasSize(5);
@@ -83,14 +83,45 @@
     checkMapping(pathsMap, "deep2", "leaf1", "leaf2");
   }
 
+  @Test
+  public void testAlwaysDirty() throws Exception {
+    ImmutableList<String> targetTexts =
+        ImmutableList.of(
+            "build alias9: phony alias2 alias3 direct1 direct2",
+            "build alias2: phony direct3 direct4",
+            "build alias3: phony alias4 direct4 direct5",
+            // alias4 is always-dirty
+            "build alias4: phony");
+
+    ImmutableSortedMap<PathFragment, PhonyTarget<PathFragment>> pathsMap =
+        NinjaPhonyTargetsUtil.getPhonyPathsMap(buildPhonyTargets(targetTexts), pf -> pf);
+
+    assertThat(pathsMap).hasSize(4);
+    // alias4 and its transitive closure is always-dirty
+    checkMapping(pathsMap, "alias9", true, "direct1", "direct2", "direct3", "direct4", "direct5");
+    checkMapping(pathsMap, "alias2", false, "direct3", "direct4");
+    checkMapping(pathsMap, "alias3", true, "direct4", "direct5");
+    checkMapping(pathsMap, "alias4", true);
+  }
+
   private static void checkMapping(
-      ImmutableSortedMap<PathFragment, NestedSet<PathFragment>> pathsMap,
+      ImmutableSortedMap<PathFragment, PhonyTarget<PathFragment>> pathsMap,
       String key,
       String... values) {
+    checkMapping(pathsMap, key, false, values);
+  }
+
+  private static void checkMapping(
+      ImmutableSortedMap<PathFragment, PhonyTarget<PathFragment>> pathsMap,
+      String key,
+      boolean isAlwaysDirty,
+      String... values) {
     Set<PathFragment> expectedPaths =
         Arrays.stream(values).map(PathFragment::create).collect(Collectors.toSet());
-    assertThat(pathsMap.get(PathFragment.create(key)).toSet())
-        .containsExactlyElementsIn(expectedPaths);
+    PhonyTarget<PathFragment> phonyTarget = pathsMap.get(PathFragment.create(key));
+    assertThat(phonyTarget).isNotNull();
+    assertThat(phonyTarget.isAlwaysDirty()).isEqualTo(isAlwaysDirty);
+    assertThat(phonyTarget.getInputs().toSet()).containsExactlyElementsIn(expectedPaths);
   }
 
   private static ImmutableSortedMap<PathFragment, NinjaTarget> buildPhonyTargets(