diff --git a/src/main/java/com/google/devtools/build/lib/actions/cache/MetadataHandler.java b/src/main/java/com/google/devtools/build/lib/actions/cache/MetadataHandler.java
index f7a2706..9838e03 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/cache/MetadataHandler.java
+++ b/src/main/java/com/google/devtools/build/lib/actions/cache/MetadataHandler.java
@@ -66,15 +66,6 @@
    */
   void markOmitted(ActionInput output);
 
-  /**
-   * Returns true iff artifact exists.
-   *
-   * <p>It is important to note that implementations may cache non-existence as a side effect of
-   * this method. If there is a possibility an artifact was intentionally omitted then {@link
-   * #artifactOmitted(Artifact)} should be checked first to avoid the side effect.
-   */
-  boolean artifactExists(Artifact artifact);
-
   /** Returns true iff artifact is a regular file. */
   boolean isRegularFile(Artifact artifact);
 
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ActionMetadataHandler.java b/src/main/java/com/google/devtools/build/lib/skyframe/ActionMetadataHandler.java
index a7230a6..9a82af3 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ActionMetadataHandler.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ActionMetadataHandler.java
@@ -26,7 +26,6 @@
 import com.google.devtools.build.lib.actions.cache.Md5Digest;
 import com.google.devtools.build.lib.actions.cache.Metadata;
 import com.google.devtools.build.lib.actions.cache.MetadataHandler;
-import com.google.devtools.build.lib.skyframe.TreeArtifactValue.TreeArtifactException;
 import com.google.devtools.build.lib.util.Preconditions;
 import com.google.devtools.build.lib.util.io.TimestampGranularityMonitor;
 import com.google.devtools.build.lib.vfs.FileStatus;
@@ -307,11 +306,7 @@
       // should be single threaded and there should be no race condition.
       // The current design of ActionMetadataHandler makes this hard to enforce.
       Set<PathFragment> paths = null;
-      try {
-        paths = TreeArtifactValue.explodeDirectory(artifact);
-      } catch (TreeArtifactException e) {
-        throw new IllegalStateException(e);
-      }
+      paths = TreeArtifactValue.explodeDirectory(artifact);
       Set<TreeFileArtifact> diskFiles = ActionInputHelper.asTreeFileArtifacts(artifact, paths);
       if (!diskFiles.equals(registeredContents)) {
         // There might be more than one error here. We first look for missing output files.
@@ -322,13 +317,13 @@
           // Currently it's hard to report this error without refactoring, since checkOutputs()
           // likes to substitute its own error messages upon catching IOException, and falls
           // through to unrecoverable error behavior on any other exception.
-          throw new IllegalStateException("Output file " + missingFiles.iterator().next()
+          throw new IOException("Output file " + missingFiles.iterator().next()
               + " was registered, but not present on disk");
         }
 
         Set<TreeFileArtifact> extraFiles = Sets.difference(diskFiles, registeredContents);
         // extraFiles cannot be empty
-        throw new IllegalStateException(
+        throw new IOException(
             "File " + extraFiles.iterator().next().getParentRelativePath()
             + ", present in TreeArtifact " + artifact + ", was not registered");
       }
@@ -381,11 +376,7 @@
     }
 
     Set<PathFragment> paths = null;
-    try {
-      paths = TreeArtifactValue.explodeDirectory(artifact);
-    } catch (TreeArtifactException e) {
-      throw new IllegalStateException(e);
-    }
+    paths = TreeArtifactValue.explodeDirectory(artifact);
     // If you're reading tree artifacts from disk while outputDirectoryListings are being injected,
     // something has gone terribly wrong.
     Object previousDirectoryListing =
@@ -482,12 +473,6 @@
   }
 
   @Override
-  public boolean artifactExists(Artifact artifact) {
-    Preconditions.checkState(!artifactOmitted(artifact), artifact);
-    return getMetadataMaybe(artifact) != null;
-  }
-
-  @Override
   public boolean isRegularFile(Artifact artifact) {
     // Currently this method is used only for genrule input directory checks. If we need to call
     // this on output artifacts too, this could be more efficient.
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/FilesystemValueChecker.java b/src/main/java/com/google/devtools/build/lib/skyframe/FilesystemValueChecker.java
index 4b9263e..9a94f3f 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/FilesystemValueChecker.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/FilesystemValueChecker.java
@@ -30,7 +30,6 @@
 import com.google.devtools.build.lib.profiler.AutoProfiler;
 import com.google.devtools.build.lib.profiler.AutoProfiler.ElapsedTimeReceiver;
 import com.google.devtools.build.lib.skyframe.SkyValueDirtinessChecker.DirtyResult;
-import com.google.devtools.build.lib.skyframe.TreeArtifactValue.TreeArtifactException;
 import com.google.devtools.build.lib.util.LoggingUtil;
 import com.google.devtools.build.lib.util.Pair;
 import com.google.devtools.build.lib.util.Preconditions;
@@ -376,7 +375,7 @@
       Set<PathFragment> currentDirectoryValue = TreeArtifactValue.explodeDirectory(artifact);
       Set<PathFragment> valuePaths = value.getChildPaths();
       return !currentDirectoryValue.equals(valuePaths);
-    } catch (IOException | TreeArtifactException e) {
+    } catch (IOException e) {
       return true;
     }
   }
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 d69e647..66ef70c 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
@@ -74,6 +74,7 @@
 import com.google.devtools.build.lib.vfs.Symlinks;
 import com.google.devtools.build.skyframe.SkyFunction.Environment;
 import com.google.protobuf.ByteString;
+import java.io.FileNotFoundException;
 import java.io.IOException;
 import java.util.Collection;
 import java.util.HashSet;
@@ -717,8 +718,7 @@
         handle = resourceManager.acquireResources(action, estimate);
       }
       boolean outputDumped = executeActionTask(action, context);
-      completeAction(action, context.getMetadataHandler(),
-          context.getFileOutErr(), outputDumped);
+      completeAction(action, context.getMetadataHandler(), context.getFileOutErr(), outputDumped);
     } finally {
       if (handle != null) {
         handle.close();
@@ -797,8 +797,8 @@
     return false;
   }
 
-  private void completeAction(Action action, MetadataHandler metadataHandler,
-      FileOutErr fileOutErr, boolean outputAlreadyDumped) throws ActionExecutionException {
+  private void completeAction(Action action, MetadataHandler metadataHandler, FileOutErr fileOutErr,
+      boolean outputAlreadyDumped) throws ActionExecutionException {
     try {
       Preconditions.checkState(action.inputsKnown(),
           "Action %s successfully executed, but inputs still not known", action);
@@ -806,7 +806,7 @@
       profiler.startTask(ProfilerTask.ACTION_COMPLETE, action);
       try {
         if (!checkOutputs(action, metadataHandler)) {
-          reportError("not all outputs were created", null, action,
+          reportError("not all outputs were created or valid", null, action,
               outputAlreadyDumped ? null : fileOutErr);
         }
         // Prevent accidental stomping on files.
@@ -922,6 +922,19 @@
     }
   }
 
+  private void reportOutputTreeArtifactErrors(Action action, Artifact output, Reporter reporter,
+      IOException e) {
+    String errorMessage;
+    if (e instanceof FileNotFoundException) {
+      errorMessage = String.format("TreeArtifact %s was not created", output.prettyPrint());
+    } else {
+      errorMessage = String.format(
+          "Error while validating output TreeArtifact %s : %s", output, e.getMessage());
+    }
+
+    reporter.handle(Event.error(action.getOwner().getLocation(), errorMessage));
+  }
+
   /**
    * Validates that all action outputs were created or intentionally omitted.
    *
@@ -933,9 +946,18 @@
       // artifactExists has the side effect of potentially adding the artifact to the cache,
       // therefore we only call it if we know the artifact is indeed not omitted to avoid any
       // unintended side effects.
-      if (!(metadataHandler.artifactOmitted(output) || metadataHandler.artifactExists(output))) {
-        reportMissingOutputFile(action, output, reporter, output.getPath().isSymbolicLink());
-        success = false;
+      if (!(metadataHandler.artifactOmitted(output))) {
+        try {
+          metadataHandler.getMetadata(output);
+        } catch (IOException e) {
+          success = false;
+          if (output.isTreeArtifact()) {
+            reportOutputTreeArtifactErrors(action, output, reporter, e);
+          } else {
+            // Are all exceptions caught due to missing files?
+            reportMissingOutputFile(action, output, reporter, output.getPath().isSymbolicLink());
+          }
+        }
       }
     }
     return success;
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/TreeArtifactValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/TreeArtifactValue.java
index e37be07..b523c92 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/TreeArtifactValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/TreeArtifactValue.java
@@ -180,29 +180,18 @@
     }
   };
 
-  /**
-   * Exception used when the contents of a directory do not form a valid SetArtifact.
-   * (We cannot use IOException because ActionMetadataHandler, in some code paths,
-   * interprets IOExceptions as missing files.)
-   */
-  static class TreeArtifactException extends Exception {
-    TreeArtifactException(String message) {
-      super(message);
-    }
-  }
-
-  private static void explodeDirectory(Artifact rootArtifact,
+  private static void explodeDirectory(Artifact treeArtifact,
       PathFragment pathToExplode, ImmutableSet.Builder<PathFragment> valuesBuilder)
-      throws IOException, TreeArtifactException {
-    for (Path subpath : rootArtifact.getPath().getRelative(pathToExplode).getDirectoryEntries()) {
+      throws IOException {
+    for (Path subpath : treeArtifact.getPath().getRelative(pathToExplode).getDirectoryEntries()) {
       PathFragment canonicalSubpathFragment =
           pathToExplode.getChild(subpath.getBaseName()).normalize();
       if (subpath.isDirectory()) {
-        explodeDirectory(rootArtifact,
+        explodeDirectory(treeArtifact,
             pathToExplode.getChild(subpath.getBaseName()), valuesBuilder);
       } else if (subpath.isSymbolicLink()) {
-        throw new TreeArtifactException(
-            "A SetArtifact may not contain a symlink, found " + subpath);
+        throw new IOException(
+            "A TreeArtifact may not contain a symlink, found " + subpath);
       } else if (subpath.isFile()) {
         valuesBuilder.add(canonicalSubpathFragment);
       } else {
@@ -215,13 +204,12 @@
   /**
    * Recursively get all child files in a directory
    * (excluding child directories themselves, but including all files in them).
-   * @throws IOException if one was thrown reading directory contents from disk.
-   * @throws TreeArtifactException if the on-disk directory is not a valid TreeArtifact.
+   * @throws IOException if there is any problem reading or validating outputs under the given
+   *     tree artifact.
    */
-  static Set<PathFragment> explodeDirectory(Artifact rootArtifact)
-      throws IOException, TreeArtifactException {
+  static Set<PathFragment> explodeDirectory(Artifact treeArtifact) throws IOException {
     ImmutableSet.Builder<PathFragment> explodedDirectory = ImmutableSet.builder();
-    explodeDirectory(rootArtifact, PathFragment.EMPTY_FRAGMENT, explodedDirectory);
+    explodeDirectory(treeArtifact, PathFragment.EMPTY_FRAGMENT, explodedDirectory);
     return explodedDirectory.build();
   }
 }