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 9a91c3c..12cb38c 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
@@ -173,6 +173,18 @@
   private final Label sourceLabel;
   private final Artifact optionalSourceFile;
   private final NestedSet<Artifact> mandatoryInputs;
+
+  /**
+   * The set of include files that we unconditionally add to the inputs of the action (but they
+   * may be pruned after execution).
+   *
+   * <p>This is necessary because the inputs that can be pruned by .d file parsing must be returned
+   * from {@link #discoverInputs(ActionExecutionContext)} and they cannot be in
+   * {@link #mandatoryInputs}. Thus, even with include scanning turned off, we pretend that we
+   * "discover" these headers.
+   */
+  private final NestedSet<Artifact> includesExemptFromDiscovery;
+
   private final boolean shouldScanIncludes;
   private final boolean shouldPruneModules;
   private final boolean usePic;
@@ -210,13 +222,13 @@
    * Set when the action prepares for execution. Used to preserve state between preparation and
    * execution.
    */
-  private Collection<Artifact> additionalInputs = null;
+  private Iterable<Artifact> additionalInputs = null;
 
   /** Set when a two-stage input discovery is used. */
   private Collection<Artifact> usedModules = null;
 
   /** Used modules that are not transitively used through other topLevelModules. */
-  private Collection<Artifact> topLevelModules = null;
+  private Iterable<Artifact> topLevelModules = null;
 
   private CcToolchainFeatures.Variables overwrittenVariables = null;
 
@@ -274,6 +286,7 @@
       boolean useHeaderModules,
       Label sourceLabel,
       NestedSet<Artifact> mandatoryInputs,
+      NestedSet<Artifact> includesExemptFromDiscovery,
       Artifact outputFile,
       DotdFile dotdFile,
       @Nullable Artifact gcnoFile,
@@ -335,6 +348,7 @@
     // We do not need to include the middleman artifact since it is a generated
     // artifact and will definitely exist prior to this action execution.
     this.mandatoryInputs = mandatoryInputs;
+    this.includesExemptFromDiscovery = includesExemptFromDiscovery;
     this.builtinIncludeFiles = CppHelper.getToolchain(ruleContext).getBuiltinIncludeFiles();
     this.cppSemantics = cppSemantics;
     if (cppSemantics.needsIncludeValidation()) {
@@ -466,8 +480,8 @@
    * and clears the stored list. {@link #prepare} must be called before this method is called, on
    * each action execution.
    */
-  public Collection<? extends ActionInput> getAdditionalInputs() {
-    Collection<? extends ActionInput> result = Preconditions.checkNotNull(additionalInputs);
+  public Iterable<? extends ActionInput> getAdditionalInputs() {
+    Iterable<? extends ActionInput> result = Preconditions.checkNotNull(additionalInputs);
     additionalInputs = null;
     return result;
   }
@@ -482,12 +496,18 @@
     return true;
   }
 
+  @VisibleForTesting  // productionVisibility = Visibility.PRIVATE
+  public Iterable<Artifact> getPossibleInputsForTesting() {
+    return Iterables.concat(getInputs(), includesExemptFromDiscovery);
+  }
+
   @Nullable
   @Override
   public Iterable<Artifact> discoverInputs(ActionExecutionContext actionExecutionContext)
       throws ActionExecutionException, InterruptedException {
     Executor executor = actionExecutionContext.getExecutor();
     Collection<Artifact> initialResult;
+
     try {
       initialResult = executor.getContext(actionContext)
           .findAdditionalInputs(this, actionExecutionContext);
@@ -502,8 +522,9 @@
       return null;
     }
 
+    Set<Artifact> initialResultSet = Sets.newLinkedHashSet(initialResult);
+    Iterables.addAll(initialResultSet, includesExemptFromDiscovery);
     if (shouldPruneModules) {
-      Set<Artifact> initialResultSet = Sets.newLinkedHashSet(initialResult);
       usedModules = Sets.newLinkedHashSet();
       topLevelModules = null;
       for (CppCompilationContext.TransitiveModuleHeaders usedModule :
@@ -511,9 +532,9 @@
         usedModules.add(usedModule.getModule());
       }
       initialResultSet.addAll(usedModules);
-      initialResult = initialResultSet;
     }
 
+    initialResult = initialResultSet;
     this.additionalInputs = initialResult;
     // In some cases, execution backends need extra files for each included file. Add them
     // to the set of inputs the caller may need to be aware of.
@@ -579,14 +600,16 @@
 
   @Override
   public Iterable<Artifact> getInputsWhenSkippingInputDiscovery() {
+    NestedSetBuilder<Artifact> result = NestedSetBuilder.stableOrder();
     if (useHeaderModules) {
-      additionalInputs = Sets.newLinkedHashSet(context.getTransitiveModules(usePic).toCollection());
       // Here, we cannot really know what the top-level modules are, so we just mark all
       // transitive modules as "top level".
-      topLevelModules = additionalInputs;
-      return additionalInputs;
+      topLevelModules = Sets.newLinkedHashSet(context.getTransitiveModules(usePic).toCollection());
+      result.addTransitive(context.getTransitiveModules(usePic));
     }
-    return null;
+    result.addTransitive(includesExemptFromDiscovery);
+    additionalInputs = result.build();
+    return result.build();
   }
 
   @Override
@@ -856,7 +879,7 @@
     IncludeProblems errors = new IncludeProblems();
     IncludeProblems warnings = new IncludeProblems();
     Set<Artifact> allowedIncludes = new HashSet<>();
-    for (Artifact input : mandatoryInputs) {
+    for (Artifact input : Iterables.concat(mandatoryInputs, includesExemptFromDiscovery)) {
       if (input.isMiddlemanArtifact() || input.isTreeArtifact()) {
         artifactExpander.expand(input, allowedIncludes);
       }
@@ -1114,6 +1137,7 @@
   protected Map<PathFragment, Artifact> getAllowedDerivedInputsMap() {
     Map<PathFragment, Artifact> allowedDerivedInputMap = new HashMap<>();
     addToMap(allowedDerivedInputMap, mandatoryInputs);
+    addToMap(allowedDerivedInputMap, includesExemptFromDiscovery);
     addToMap(allowedDerivedInputMap, getDeclaredIncludeSrcs());
     addToMap(allowedDerivedInputMap, context.getTransitiveCompilationPrerequisites());
     addToMap(allowedDerivedInputMap, context.getTransitiveModules(usePic));
@@ -1223,6 +1247,10 @@
     for (Artifact input : getMandatoryInputs()) {
       f.addPath(input.getExecPath());
     }
+    f.addInt(0);
+    for (Artifact input : includesExemptFromDiscovery) {
+      f.addPath(input.getExecPath());
+    }
     return f.hexDigestAndReset();
   }
 
@@ -1253,18 +1281,7 @@
 
     // Post-execute "include scanning", which modifies the action inputs to match what the compile
     // action actually used by incorporating the results of .d file parsing.
-    //
-    // We enable this when "include scanning" itself is enabled, or when hdrs_check is set to loose
-    // or warn, as otherwise the action might be missing inputs that the compiler used and rebuilds
-    // become incorrect.
-    //
-    // Note that this effectively disables post-execute "include scanning" in Bazel, because
-    // hdrs_check is forced to "strict" and "include scanning" is forced to off.
-    boolean usesStrictHdrsChecks = context.getDeclaredIncludeDirs().isEmpty()
-        && context.getDeclaredIncludeWarnDirs().isEmpty();
-    if (shouldScanIncludes() || !usesStrictHdrsChecks) {
-      updateActionInputs(discoveredInputs);
-    }
+    updateActionInputs(discoveredInputs);
 
     // hdrs_check: This cannot be switched off, because doing so would allow for incorrect builds.
     validateInclusions(
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/CppCompileActionBuilder.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppCompileActionBuilder.java
index 63a0ec1..60ed762 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CppCompileActionBuilder.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppCompileActionBuilder.java
@@ -30,6 +30,7 @@
 import com.google.devtools.build.lib.cmdline.Label;
 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.rules.cpp.CcToolchainFeatures.FeatureConfiguration;
 import com.google.devtools.build.lib.rules.cpp.CppCompileAction.DotdFile;
 import com.google.devtools.build.lib.rules.cpp.CppCompileAction.SpecialInputsHandler;
@@ -256,13 +257,9 @@
             && featureConfiguration.isEnabled(CppRuleClasses.USE_HEADER_MODULES);
 
     boolean fake = tempOutputFile != null;
-
     // Configuration can be null in tests.
     NestedSetBuilder<Artifact> realMandatoryInputsBuilder = NestedSetBuilder.compileOrder();
     realMandatoryInputsBuilder.addTransitive(mandatoryInputsBuilder.build());
-    if (!fake && !shouldScanIncludes) {
-      realMandatoryInputsBuilder.addTransitive(context.getDeclaredIncludeSrcs());
-    }
     boolean shouldPruneModules =
         cppConfiguration.getPruneCppModules() && shouldScanIncludes && useHeaderModules;
     if (useHeaderModules && !shouldPruneModules) {
@@ -281,6 +278,12 @@
           featureConfiguration.getToolForAction(getActionName()).getExecutionRequirements();
     }
 
+    NestedSet<Artifact> realMandatoryInputs = realMandatoryInputsBuilder.build();
+
+    NestedSet<Artifact> includesExemptFromDiscovery = shouldScanIncludes
+        ? NestedSetBuilder.<Artifact>emptySet(Order.STABLE_ORDER)
+        : context.getDeclaredIncludeSrcs();
+
     // Copying the collections is needed to make the builder reusable.
     if (fake) {
       return new FakeCppCompileAction(
@@ -294,7 +297,8 @@
           usePic,
           useHeaderModules,
           sourceLabel,
-          realMandatoryInputsBuilder.build(),
+          realMandatoryInputs,
+          includesExemptFromDiscovery,
           outputFile,
           tempOutputFile,
           dotdFile,
@@ -307,8 +311,6 @@
           ruleContext,
           cppSemantics);
     } else {
-      NestedSet<Artifact> realMandatoryInputs = realMandatoryInputsBuilder.build();
-
       return new CppCompileAction(
           owner,
           ImmutableList.copyOf(features),
@@ -321,6 +323,7 @@
           useHeaderModules,
           sourceLabel,
           realMandatoryInputs,
+          includesExemptFromDiscovery,
           outputFile,
           dotdFile,
           gcnoFile,
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/FakeCppCompileAction.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/FakeCppCompileAction.java
index 3e99af5..a1b55f2 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/FakeCppCompileAction.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/FakeCppCompileAction.java
@@ -72,6 +72,7 @@
       boolean useHeaderModules,
       Label sourceLabel,
       NestedSet<Artifact> mandatoryInputs,
+      NestedSet<Artifact> includesExemptFromDiscovery,
       Artifact outputFile,
       PathFragment tempOutputFile,
       DotdFile dotdFile,
@@ -95,6 +96,7 @@
         useHeaderModules,
         sourceLabel,
         mandatoryInputs,
+        includesExemptFromDiscovery,
         outputFile,
         dotdFile,
         null,
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/SpawnGccStrategy.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/SpawnGccStrategy.java
index 24daa88..1025068 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/SpawnGccStrategy.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/SpawnGccStrategy.java
@@ -15,7 +15,10 @@
 package com.google.devtools.build.lib.rules.cpp;
 
 import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.Iterables;
 import com.google.devtools.build.lib.actions.ActionExecutionContext;
+import com.google.devtools.build.lib.actions.ActionInput;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.actions.BaseSpawn;
 import com.google.devtools.build.lib.actions.ExecException;
@@ -24,11 +27,10 @@
 import com.google.devtools.build.lib.actions.ResourceSet;
 import com.google.devtools.build.lib.actions.Spawn;
 import com.google.devtools.build.lib.actions.SpawnActionContext;
-
 import java.util.Collection;
 
 /**
- * A cpp strategy that simply passes everything through to the default spawn action strategy.
+ * A context for C++ compilation that calls into a {@link SpawnActionContext}.
  */
 @ExecutionStrategy(
   contextType = CppCompileActionContext.class,
@@ -36,6 +38,25 @@
 )
 public class SpawnGccStrategy implements CppCompileActionContext {
 
+  /**
+   * A {@link Spawn} that wraps a {@link CppCompileAction} and adds its
+   * {@code additionalInputs} (potential files included) to its inputs.
+   */
+  private static class GccSpawn extends BaseSpawn {
+    private final Iterable<? extends ActionInput> inputs;
+
+    public GccSpawn(CppCompileAction action, ResourceSet resources) {
+      super(action.getArgv(), action.getEnvironment(), action.getExecutionInfo(), action,
+          resources);
+      this.inputs = Iterables.concat(action.getInputs(), action.getAdditionalInputs());
+    }
+
+    @Override
+    public Iterable<? extends ActionInput> getInputFiles() {
+      return ImmutableSet.copyOf(inputs);
+    }
+  }
+
   @Override
   public Collection<Artifact> findAdditionalInputs(
       CppCompileAction action, ActionExecutionContext actionExecutionContext)
@@ -49,13 +70,7 @@
       throws ExecException, InterruptedException {
     Executor executor = actionExecutionContext.getExecutor();
     SpawnActionContext spawnActionContext = executor.getSpawnActionContext(action.getMnemonic());
-    Spawn spawn =
-        new BaseSpawn(
-            action.getArgv(),
-            action.getEnvironment(),
-            action.getExecutionInfo(),
-            action,
-            estimateResourceConsumption(action));
+    Spawn spawn = new GccSpawn(action, estimateResourceConsumption(action));
     spawnActionContext.exec(spawn, actionExecutionContext);
     return null;
   }
diff --git a/src/main/java/com/google/devtools/build/lib/sandbox/SpawnHelpers.java b/src/main/java/com/google/devtools/build/lib/sandbox/SpawnHelpers.java
index 0abf331..b5b920c 100644
--- a/src/main/java/com/google/devtools/build/lib/sandbox/SpawnHelpers.java
+++ b/src/main/java/com/google/devtools/build/lib/sandbox/SpawnHelpers.java
@@ -14,6 +14,7 @@
 
 package com.google.devtools.build.lib.sandbox;
 
+import com.google.common.collect.Iterables;
 import com.google.common.io.Files;
 import com.google.devtools.build.lib.actions.ActionExecutionContext;
 import com.google.devtools.build.lib.actions.ActionInput;
@@ -184,7 +185,7 @@
     if (spawn.getResourceOwner() instanceof CppCompileAction) {
       CppCompileAction action = (CppCompileAction) spawn.getResourceOwner();
       if (action.shouldScanIncludes()) {
-        inputs.addAll(action.getAdditionalInputs());
+        Iterables.addAll(inputs, action.getAdditionalInputs());
       }
     }
 
diff --git a/src/test/shell/integration/BUILD b/src/test/shell/integration/BUILD
index 6f1bb7f..ac8f037 100644
--- a/src/test/shell/integration/BUILD
+++ b/src/test/shell/integration/BUILD
@@ -192,6 +192,13 @@
 )
 
 sh_test(
+    name = "cpp_test",
+    size = "large",
+    srcs = ["cpp_test.sh"],
+    data = [":test-deps"],
+)
+
+sh_test(
     name = "action_env_test",
     size = "large",
     srcs = ["action_env_test.sh"],
diff --git a/src/test/shell/integration/cpp_test.sh b/src/test/shell/integration/cpp_test.sh
new file mode 100755
index 0000000..0e8fd3a
--- /dev/null
+++ b/src/test/shell/integration/cpp_test.sh
@@ -0,0 +1,93 @@
+#!/bin/bash
+#
+# Copyright 2016 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.
+#
+# Load the test setup defined in the parent directory
+CURRENT_DIR="$(cd "$(dirname "${BASH_SOURCE[0]}")" && pwd)"
+source "${CURRENT_DIR}/../integration_test_setup.sh" \
+  || { echo "integration_test_setup.sh not found!" >&2; exit 1; }
+
+#### SETUP #############################################################
+
+set -e
+
+#### TESTS #############################################################
+
+function test_no_rebuild_on_irrelevant_header_change() {
+  mkdir -p a
+  cat > a/BUILD <<EOF
+cc_binary(name="a", srcs=["a.cc"], deps=["b"])
+cc_library(name="b", srcs=["b1.h", "b2.h"])
+EOF
+
+  cat > a/a.cc <<EOF
+#include "a/b1.h"
+
+int main(void) {
+  return B_RETURN_VALUE;
+}
+EOF
+
+  cat > a/b1.h <<EOF
+#define B_RETURN_VALUE 31
+EOF
+
+  cat > a/b2.h <<EOF
+=== BANANA ===
+EOF
+
+  bazel build //a || fail "build failed"
+  echo "CHERRY" > a/b2.h
+  bazel build //a >& $TEST_log || fail "build failed"
+  expect_not_log "Compiling a/a.cc"
+}
+
+function test_new_header_is_required() {
+  mkdir -p a
+  cat > a/BUILD <<EOF
+cc_binary(name="a", srcs=["a.cc"], deps=[":b"])
+cc_library(name="b", srcs=["b1.h", "b2.h"])
+EOF
+
+  cat > a/a.cc << EOF
+#include "a/b1.h"
+
+int main(void) {
+    return B1;
+}
+EOF
+
+  cat > a/b1.h <<EOF
+#define B1 3
+EOF
+
+  cat > a/b2.h <<EOF
+#define B2 4
+EOF
+
+  bazel build //a || fail "build failed"
+  cat > a/a.cc << EOF
+#include "a/b1.h"
+#include "a/b2.h"
+
+int main(void) {
+    return B1 + B2;
+}
+EOF
+
+  bazel build //a || fail "build failled"
+}
+
+run_suite "Tests for Bazel's C++ rules"