diff --git a/src/main/java/com/google/devtools/build/lib/packages/GlobCache.java b/src/main/java/com/google/devtools/build/lib/packages/GlobCache.java
index 31b36ab..a968c4e 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/GlobCache.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/GlobCache.java
@@ -17,7 +17,6 @@
 import com.google.common.base.Preconditions;
 import com.google.common.base.Predicate;
 import com.google.common.base.Throwables;
-import com.google.common.collect.Iterables;
 import com.google.common.collect.Lists;
 import com.google.common.util.concurrent.SettableFuture;
 import com.google.devtools.build.lib.cmdline.PackageIdentifier;
@@ -241,22 +240,17 @@
     // Start globbing all patterns in parallel. The getGlob() calls below will
     // block on an individual pattern's results, but the other globs can
     // continue in the background.
-    for (String pattern : Iterables.concat(includes, excludes)) {
+    for (String pattern : includes) {
       @SuppressWarnings("unused") 
       Future<?> possiblyIgnoredError = getGlobUnsortedAsync(pattern, excludeDirs);
     }
 
     HashSet<String> results = new HashSet<>();
+    Preconditions.checkState(!results.contains(null), "glob returned null");
     for (String pattern : includes) {
       results.addAll(getGlobUnsorted(pattern, excludeDirs));
     }
-    for (String pattern : excludes) {
-      for (String excludeMatch : getGlobUnsorted(pattern, excludeDirs)) {
-        results.remove(excludeMatch);
-      }
-    }
-
-    Preconditions.checkState(!results.contains(null), "glob returned null");
+    UnixGlob.removeExcludes(results, excludes);
     return new ArrayList<>(results);
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/packages/PackageFactory.java b/src/main/java/com/google/devtools/build/lib/packages/PackageFactory.java
index 0d11eac..1e181e8 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/PackageFactory.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/PackageFactory.java
@@ -20,7 +20,6 @@
 import com.google.common.base.Preconditions;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
-import com.google.common.collect.Iterables;
 import com.google.common.util.concurrent.ThreadFactoryBuilder;
 import com.google.devtools.build.lib.analysis.skylark.BazelStarlarkContext;
 import com.google.devtools.build.lib.analysis.skylark.SymbolGenerator;
@@ -300,7 +299,7 @@
     @Override
     public Token runAsync(List<String> includes, List<String> excludes, boolean excludeDirs)
         throws BadGlobException {
-      for (String pattern : Iterables.concat(includes, excludes)) {
+      for (String pattern : includes) {
         @SuppressWarnings("unused")
         Future<?> possiblyIgnoredError = globCache.getGlobUnsortedAsync(pattern, excludeDirs);
       }
@@ -1732,11 +1731,13 @@
           }
           continue;
         }
-        if (arg.getValue() instanceof ListLiteral) {
-          ListLiteral list = (ListLiteral) arg.getValue();
-          for (Expression elem : list.getElements()) {
-            if (elem instanceof StringLiteral) {
-              globStrings.add(((StringLiteral) elem).getValue());
+        if (arg.getIdentifier() == null || arg.getIdentifier().getName().equals("include")) {
+          if (arg.getValue() instanceof ListLiteral) {
+            ListLiteral list = (ListLiteral) arg.getValue();
+            for (Expression elem : list.getElements()) {
+              if (elem instanceof StringLiteral) {
+                globStrings.add(((StringLiteral) elem).getValue());
+              }
             }
           }
         }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/PackageFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/PackageFunction.java
index bd473e8..f6783ec 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/PackageFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/PackageFunction.java
@@ -68,6 +68,7 @@
 import com.google.devtools.build.lib.vfs.PathFragment;
 import com.google.devtools.build.lib.vfs.Root;
 import com.google.devtools.build.lib.vfs.RootedPath;
+import com.google.devtools.build.lib.vfs.UnixGlob;
 import com.google.devtools.build.skyframe.SkyFunction;
 import com.google.devtools.build.skyframe.SkyFunctionException;
 import com.google.devtools.build.skyframe.SkyFunctionException.Transience;
@@ -879,56 +880,34 @@
     @Override
     public Token runAsync(List<String> includes, List<String> excludes, boolean excludeDirs)
         throws BadGlobException, InterruptedException {
-      List<SkyKey> globKeys = new ArrayList<>(includes.size() + excludes.size());
-      LinkedHashSet<SkyKey> includesKeys = Sets.newLinkedHashSetWithExpectedSize(includes.size());
-      LinkedHashSet<SkyKey> excludesKeys = Sets.newLinkedHashSetWithExpectedSize(excludes.size());
-      Map<SkyKey, String> globKeyToIncludeStringMap =
-          Maps.newHashMapWithExpectedSize(includes.size());
-      Map<SkyKey, String> globKeyToExcludeStringMap =
-          Maps.newHashMapWithExpectedSize(excludes.size());
+      LinkedHashSet<SkyKey> globKeys = Sets.newLinkedHashSetWithExpectedSize(includes.size());
+      Map<SkyKey, String> globKeyToPatternMap = Maps.newHashMapWithExpectedSize(includes.size());
 
       for (String pattern : includes) {
         SkyKey globKey = getGlobKey(pattern, excludeDirs);
         globKeys.add(globKey);
-        includesKeys.add(globKey);
-        globKeyToIncludeStringMap.put(globKey, pattern);
+        globKeyToPatternMap.put(globKey, pattern);
       }
-      for (String pattern : excludes) {
-        SkyKey globKey = getGlobKey(pattern, excludeDirs);
-        globKeys.add(globKey);
-        excludesKeys.add(globKey);
-        globKeyToExcludeStringMap.put(globKey, pattern);
-      }
+
       globDepsRequested.addAll(globKeys);
 
       Map<SkyKey, ValueOrException2<IOException, BuildFileNotFoundException>> globValueMap =
           env.getValuesOrThrow(globKeys, IOException.class, BuildFileNotFoundException.class);
 
-      // For each missing glob, evaluate it asychronously via the delegate.
+      // For each missing glob, evaluate it asynchronously via the delegate.
       Collection<SkyKey> missingKeys = getMissingKeys(globKeys, globValueMap);
-      List<String> includesToDelegate = new ArrayList<>(missingKeys.size());
-      List<String> excludesToDelegate = new ArrayList<>(missingKeys.size());
+      List<String> globsToDelegate = new ArrayList<>(missingKeys.size());
       for (SkyKey missingKey : missingKeys) {
-        String missingIncludePattern = globKeyToIncludeStringMap.get(missingKey);
-        if (missingIncludePattern != null) {
-          includesToDelegate.add(missingIncludePattern);
-          includesKeys.remove(missingKey);
-        }
-        String missingExcludePattern = globKeyToExcludeStringMap.get(missingKey);
-        if (missingExcludePattern != null) {
-          excludesToDelegate.add(missingExcludePattern);
-          excludesKeys.remove(missingKey);
+        String missingPattern = globKeyToPatternMap.get(missingKey);
+        if (missingPattern != null) {
+          globsToDelegate.add(missingPattern);
+          globKeys.remove(missingKey);
         }
       }
       Token legacyIncludesToken =
-          legacyGlobber.runAsync(includesToDelegate, ImmutableList.<String>of(), excludeDirs);
-      // See the HybridToken class-comment for why we pass excludesToDelegate as the includes
-      // parameter here.
-      Token legacyExcludesToken =
-          legacyGlobber.runAsync(excludesToDelegate, ImmutableList.<String>of(), excludeDirs);
+          legacyGlobber.runAsync(globsToDelegate, ImmutableList.of(), excludeDirs);
 
-      return new HybridToken(globValueMap, includesKeys, excludesKeys,
-          legacyIncludesToken, legacyExcludesToken);
+      return new HybridToken(globValueMap, globKeys, legacyIncludesToken, excludes);
     }
 
     private Collection<SkyKey> getMissingKeys(Collection<SkyKey> globKeys,
@@ -969,33 +948,9 @@
 
     /**
      * A {@link Globber.Token} that encapsulates the result of a single {@link Globber#runAsync}
-     * call via the fetching of some globs from skyframe, and some other globs via a
-     * {@link PackageFactory.LegacyGlobber}. We take care to properly handle 'includes' vs
-     * 'excludes'.
-     *
-     * <p>That is, we evaluate {@code glob(includes, excludes)} by partitioning {@code includes} and
-     * {@code excludes}.
-     *
-     * <pre>
-     * {@code
-     * includes = includes_sky U includes_leg
-     * excludes = excludes_sky U excludes_leg
-     * }
-     * </pre>
-     *
-     * <p>and then noting
-     *
-     * <pre>
-     * {@code
-     * glob(includes, excludes) =
-     *     (glob(includes_sky, []) U glob(includes_leg, []))
-     *   - (glob(excludes_sky, []) U glob(excludes_leg, []))
-     * }
-     * </pre>
-     *
-     * <p>Importantly, we pass excludes=[] in all cases; otherwise we'd be incorrectly not
-     * subtracting excluded glob matches from the overall list of matches. In other words, we
-     * implement the subtractive nature of excludes ourselves in {@link #resolve}.
+     * call via the fetching of some globs from skyframe, and some other globs via a{@link
+     * PackageFactory.LegacyGlobber}. 'exclude' patterns are evaluated using {@link
+     * UnixGlob#removeExcludes} after merging legacy and skyframe glob results in {@link #resolve}.
      */
     private static class HybridToken extends Globber.Token {
       // The result of the Skyframe lookup for all the needed glob patterns.
@@ -1004,25 +959,20 @@
       // The skyframe keys corresponding to the 'includes' patterns fetched from Skyframe
       // (this is includes_sky above).
       private final Iterable<SkyKey> includesGlobKeys;
-      // The skyframe keys corresponding to the 'excludes' patterns fetched from Skyframe
-      // (this is excludes_sky above).
-      private final Iterable<SkyKey> excludesGlobKeys;
-      // A token for computing includes_leg.
+      // A token for computing legacy globs.
       private final Token legacyIncludesToken;
-      // A token for computing excludes_leg.
-      private final Token legacyExcludesToken;
+
+      private final List<String> excludes;
 
       private HybridToken(
           Map<SkyKey, ValueOrException2<IOException, BuildFileNotFoundException>> globValueMap,
           Iterable<SkyKey> includesGlobKeys,
-          Iterable<SkyKey> excludesGlobKeys,
           Token delegateIncludesToken,
-          Token delegateExcludesToken) {
+          List<String> excludes) {
         this.globValueMap = globValueMap;
         this.includesGlobKeys = includesGlobKeys;
-        this.excludesGlobKeys = excludesGlobKeys;
         this.legacyIncludesToken = delegateIncludesToken;
-        this.legacyExcludesToken = delegateExcludesToken;
+        this.excludes = excludes;
       }
 
       private List<String> resolve(Globber delegate) throws IOException, InterruptedException {
@@ -1034,14 +984,7 @@
           }
         }
         matches.addAll(delegate.fetch(legacyIncludesToken));
-        for (SkyKey excludeGlobKey : excludesGlobKeys) {
-          for (PathFragment match : getGlobMatches(excludeGlobKey, globValueMap)) {
-            matches.remove(match.getPathString());
-          }
-        }
-        for (String delegateExcludeMatch : delegate.fetch(legacyExcludesToken)) {
-          matches.remove(delegateExcludeMatch);
-        }
+        UnixGlob.removeExcludes(matches, excludes);
         List<String> result = new ArrayList<>(matches);
         // Skyframe glob results are unsorted. And we used a LegacyGlobber that doesn't sort.
         // Therefore, we want to unconditionally sort here.
diff --git a/src/main/java/com/google/devtools/build/lib/vfs/UnixGlob.java b/src/main/java/com/google/devtools/build/lib/vfs/UnixGlob.java
index 8a17188..f38e5ae 100644
--- a/src/main/java/com/google/devtools/build/lib/vfs/UnixGlob.java
+++ b/src/main/java/com/google/devtools/build/lib/vfs/UnixGlob.java
@@ -34,9 +34,12 @@
 import com.google.devtools.build.lib.profiler.ProfilerTask;
 import com.google.devtools.build.lib.profiler.SilentCloseable;
 import java.io.IOException;
+import java.util.ArrayList;
 import java.util.Collection;
 import java.util.Collections;
+import java.util.HashMap;
 import java.util.List;
+import java.util.Map;
 import java.util.Objects;
 import java.util.Set;
 import java.util.concurrent.ConcurrentHashMap;
@@ -143,24 +146,21 @@
     return null;
   }
 
-  /**
-   * Calls {@link #matches(String, String, ConcurrentHashMap) matches(pattern, str, null)}
-   */
+  /** Calls {@link #matches(String, String, Map) matches(pattern, str, null)} */
   public static boolean matches(String pattern, String str) {
     return matches(pattern, str, null);
   }
 
   /**
-   * Returns whether {@code str} matches the glob pattern {@code pattern}. This
-   * method may use the {@code patternCache} to speed up the matching process.
+   * Returns whether {@code str} matches the glob pattern {@code pattern}. This method may use the
+   * {@code patternCache} to speed up the matching process.
    *
    * @param pattern a glob pattern
    * @param str the string to match
-   * @param patternCache a cache from patterns to compiled Pattern objects, or
-   *        {@code null} to skip caching
+   * @param patternCache a cache from patterns to compiled Pattern objects, or {@code null} to skip
+   *     caching
    */
-  public static boolean matches(String pattern, String str,
-      ConcurrentHashMap<String, Pattern> patternCache) {
+  public static boolean matches(String pattern, String str, Map<String, Pattern> patternCache) {
     if (pattern.length() == 0 || str.length() == 0) {
       return false;
     }
@@ -840,4 +840,64 @@
       }
     }
   }
+
+  /**
+   * Filters out exclude patterns from a Set of paths. Common cases such as wildcard-free patterns
+   * or suffix patterns are special-cased to make this function efficient.
+   */
+  public static void removeExcludes(Set<String> paths, Collection<String> excludes) {
+    ArrayList<String> complexPatterns = new ArrayList<>(excludes.size());
+    for (String exclude : excludes) {
+      if (isWildcardFree(exclude)) {
+        paths.remove(exclude);
+        continue;
+      }
+      if (exclude.startsWith("**/*")) {
+        String tail = exclude.substring(4);
+        if (isWildcardFree(tail)) {
+          paths.removeIf(path -> path.endsWith(tail));
+          continue;
+        }
+      }
+      complexPatterns.add(exclude);
+    }
+    if (complexPatterns.isEmpty()) {
+      return;
+    }
+    List<String[]> splitPatterns = checkAndSplitPatterns(complexPatterns);
+    HashMap<String, Pattern> patternCache = new HashMap<>();
+    paths.removeIf(
+        path -> {
+          String[] segments = Iterables.toArray(Splitter.on('/').split(path), String.class);
+          for (String[] splitPattern : splitPatterns) {
+            if (matchesPattern(splitPattern, segments, 0, 0, patternCache)) {
+              return true;
+            }
+          }
+          return false;
+        });
+  }
+
+  /** Returns true if {@code pattern} matches {@code path} starting from the given segments. */
+  private static boolean matchesPattern(
+      String[] pattern, String[] path, int i, int j, Map<String, Pattern> patternCache) {
+    if (i == pattern.length) {
+      return j == path.length;
+    }
+    if (pattern[i].equals("**")) {
+      return matchesPattern(pattern, path, i + 1, j, patternCache)
+          || (j < path.length && matchesPattern(pattern, path, i, j + 1, patternCache));
+    }
+    if (j == path.length) {
+      return false;
+    }
+    if (matches(pattern[i], path[j], patternCache)) {
+      return matchesPattern(pattern, path, i + 1, j + 1, patternCache);
+    }
+    return false;
+  }
+
+  private static boolean isWildcardFree(String pattern) {
+    return !pattern.contains("*") && !pattern.contains("?");
+  }
 }
diff --git a/src/test/java/com/google/devtools/build/lib/packages/PackageFactoryTest.java b/src/test/java/com/google/devtools/build/lib/packages/PackageFactoryTest.java
index 94b47ca..354fb0c 100644
--- a/src/test/java/com/google/devtools/build/lib/packages/PackageFactoryTest.java
+++ b/src/test/java/com/google/devtools/build/lib/packages/PackageFactoryTest.java
@@ -1250,7 +1250,7 @@
             "other_variable = glob(include = ['a'], exclude = ['b'])",
             "third_variable = glob(['c'], exclude_directories = 0)"));
     assertThat(globPatternExtractor.getExcludeDirectoriesPatterns())
-        .containsExactly("ab", "a", "b", "**/*");
+        .containsExactly("ab", "a", "**/*");
     assertThat(globPatternExtractor.getIncludeDirectoriesPatterns()).containsExactly("c");
   }
 }
diff --git a/src/test/java/com/google/devtools/build/lib/packages/util/PackageFactoryTestBase.java b/src/test/java/com/google/devtools/build/lib/packages/util/PackageFactoryTestBase.java
index 24d9eb0..edfac88 100644
--- a/src/test/java/com/google/devtools/build/lib/packages/util/PackageFactoryTestBase.java
+++ b/src/test/java/com/google/devtools/build/lib/packages/util/PackageFactoryTestBase.java
@@ -215,8 +215,6 @@
     // Ensure all of the patterns are recorded against this package:
     assertThat(globCache.getKeySet().containsAll(createGlobCacheKeys(includes, excludeDirs)))
         .isTrue();
-    assertThat(globCache.getKeySet().containsAll(createGlobCacheKeys(excludes, excludeDirs)))
-        .isTrue();
     assertThat(pkg.containsErrors()).isFalse();
   }
 
diff --git a/src/test/java/com/google/devtools/build/lib/vfs/GlobTest.java b/src/test/java/com/google/devtools/build/lib/vfs/GlobTest.java
index 4c608c9..ad62a0f 100644
--- a/src/test/java/com/google/devtools/build/lib/vfs/GlobTest.java
+++ b/src/test/java/com/google/devtools/build/lib/vfs/GlobTest.java
@@ -442,4 +442,28 @@
     assertThat(executor.awaitTermination(TestUtils.WAIT_TIMEOUT_SECONDS, TimeUnit.SECONDS))
         .isTrue();
   }
+
+  private Collection<String> removeExcludes(ImmutableList<String> paths, String... excludes) {
+    HashSet<String> pathSet = new HashSet<>(paths);
+    UnixGlob.removeExcludes(pathSet, ImmutableList.copyOf(excludes));
+    return pathSet;
+  }
+
+  @Test
+  public void testExcludeFiltering() {
+    ImmutableList<String> paths = ImmutableList.of("a/A.java", "a/B.java", "a/b/C.java", "c.cc");
+    assertThat(removeExcludes(paths, "**/*.java")).containsExactly("c.cc");
+    assertThat(removeExcludes(paths, "**/nomatch.*")).containsAllIn(paths);
+    assertThat(removeExcludes(paths, "a/A.java")).containsExactly("a/B.java", "a/b/C.java", "c.cc");
+    assertThat(removeExcludes(paths, "a/?.java")).containsExactly("a/b/C.java", "c.cc");
+    assertThat(removeExcludes(paths, "a/*/C.java")).containsExactly("a/A.java", "a/B.java", "c.cc");
+    assertThat(removeExcludes(paths, "**")).isEmpty();
+    assertThat(removeExcludes(paths, "**/**")).isEmpty();
+
+    // Test filenames that look like code patterns.
+    paths = ImmutableList.of("a/A.java", "a/B.java", "a/b/*.java", "a/b/C.java", "c.cc");
+    assertThat(removeExcludes(paths, "**/*.java")).containsExactly("c.cc");
+    assertThat(removeExcludes(paths, "**/A.java", "**/B.java", "**/C.java"))
+        .containsExactly("a/b/*.java", "c.cc");
+  }
 }