diff --git a/src/main/java/com/google/devtools/build/lib/packages/AspectDefinition.java b/src/main/java/com/google/devtools/build/lib/packages/AspectDefinition.java
index 9cf3a1a..8237982 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/AspectDefinition.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/AspectDefinition.java
@@ -17,13 +17,10 @@
 import com.google.common.base.Preconditions;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
-import com.google.common.collect.ImmutableMultimap;
 import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.Iterables;
-import com.google.common.collect.LinkedHashMultimap;
 import com.google.common.collect.Lists;
 import com.google.common.collect.Multimap;
-import com.google.common.collect.SetMultimap;
 import com.google.devtools.build.lib.analysis.config.transitions.ConfigurationTransition;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
@@ -38,6 +35,7 @@
 import java.util.LinkedHashSet;
 import java.util.List;
 import java.util.Map;
+import java.util.function.BiConsumer;
 import javax.annotation.Nullable;
 
 /**
@@ -172,38 +170,8 @@
     return applyToFiles;
   }
 
-  /** Returns the attribute -&gt; set of labels that are provided by aspects of attribute. */
-  public static ImmutableMultimap<Attribute, Label> visitAspectsIfRequired(
-      Target from,
-      ImmutableList<Aspect> aspectsOfAttribute,
-      Target to,
-      DependencyFilter dependencyFilter) {
-    // Aspect can be declared only for Rules.
-    if (!(from instanceof Rule) || !(to instanceof Rule)) {
-      return ImmutableMultimap.of();
-    }
-    RuleClass ruleClass = ((Rule) to).getRuleClassObject();
-    AdvertisedProviderSet providers = ruleClass.getAdvertisedProviders();
-    return visitAspectsIfRequired((Rule) from, aspectsOfAttribute, providers, dependencyFilter);
-  }
-
-  /** Returns the attribute -&gt; set of labels that are provided by aspects of attribute. */
-  public static ImmutableMultimap<Attribute, Label> visitAspectsIfRequired(
-      Rule from,
-      ImmutableList<Aspect> aspectsOfAttribute,
-      AdvertisedProviderSet advertisedProviders,
-      DependencyFilter dependencyFilter) {
-    SetMultimap<Attribute, Label> result = LinkedHashMultimap.create();
-    for (Aspect candidateClass : aspectsOfAttribute) {
-      // Check if target satisfies condition for this aspect (has to provide all required
-      // TransitiveInfoProviders)
-      RequiredProviders requiredProviders =
-          candidateClass.getDefinition().getRequiredProviders();
-      if (requiredProviders.isSatisfiedBy(advertisedProviders)) {
-        addAllAttributesOfAspect(from, result, candidateClass, dependencyFilter);
-      }
-    }
-    return ImmutableMultimap.copyOf(result);
+  public static boolean satisfies(Aspect aspect, AdvertisedProviderSet advertisedProviderSet) {
+    return aspect.getDefinition().getRequiredProviders().isSatisfiedBy(advertisedProviderSet);
   }
 
   @Nullable
@@ -219,16 +187,23 @@
       final Multimap<Attribute, Label> labelBuilder,
       Aspect aspect,
       DependencyFilter dependencyFilter) {
+    forEachLabelDepFromAllAttributesOfAspect(from, aspect, dependencyFilter, labelBuilder::put);
+  }
+
+  public static void forEachLabelDepFromAllAttributesOfAspect(
+      Rule from,
+      Aspect aspect,
+      DependencyFilter dependencyFilter,
+      BiConsumer<Attribute, Label> consumer) {
     LabelVisitor<Attribute> labelVisitor =
         (label, aspectAttribute) -> {
-          Label repositoryRelative = maybeGetRepositoryRelativeLabel(from, label);
-          if (repositoryRelative == null) {
+          Label repositoryRelativeLabel = maybeGetRepositoryRelativeLabel(from, label);
+          if (repositoryRelativeLabel == null) {
             return;
           }
-          labelBuilder.put(aspectAttribute, repositoryRelative);
+          consumer.accept(aspectAttribute, repositoryRelativeLabel);
         };
-    ImmutableMap<String, Attribute> attributes = aspect.getDefinition().getAttributes();
-    for (final Attribute aspectAttribute : attributes.values()) {
+    for (Attribute aspectAttribute : aspect.getDefinition().getAttributes().values()) {
       if (!dependencyFilter.apply(aspect, aspectAttribute)) {
         continue;
       }
diff --git a/src/main/java/com/google/devtools/build/lib/query2/LabelVisitor.java b/src/main/java/com/google/devtools/build/lib/query2/LabelVisitor.java
index 4cadef9..e1e982c 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/LabelVisitor.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/LabelVisitor.java
@@ -17,7 +17,6 @@
 import com.google.common.annotations.VisibleForTesting;
 import com.google.common.base.Throwables;
 import com.google.common.collect.ImmutableList;
-import com.google.common.collect.ImmutableMultimap;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.concurrent.AbstractQueueVisitor;
 import com.google.devtools.build.lib.concurrent.ErrorClassifier;
@@ -39,7 +38,6 @@
 import com.google.devtools.build.lib.pkgcache.TargetEdgeObserver;
 import com.google.devtools.build.lib.pkgcache.TargetProvider;
 import java.util.Collection;
-import java.util.Map;
 import java.util.concurrent.ConcurrentHashMap;
 import java.util.concurrent.ConcurrentMap;
 import java.util.concurrent.TimeUnit;
@@ -396,15 +394,26 @@
     private void visitAspectsIfRequired(
         Target from, Attribute attribute, final Target to, int depth, int count) {
       // TODO(bazel-team): The getAspects call below is duplicate work for each direct dep entailed
-      // by an attribute's value. Consider doing a slight refactor where we make this method call
-      // exactly once per Attribute.
-      ImmutableList<Aspect> aspectsOfAttribute =
-          (from instanceof Rule) ? attribute.getAspects((Rule) from) : ImmutableList.of();
-      ImmutableMultimap<Attribute, Label> labelsFromAspects =
-          AspectDefinition.visitAspectsIfRequired(from, aspectsOfAttribute, to, edgeFilter);
-      // Create an edge from target to the attribute value.
-      for (Map.Entry<Attribute, Label> entry : labelsFromAspects.entries()) {
-        enqueueTarget(from, entry.getKey(), entry.getValue(), depth, count);
+      // by an attribute's value. Additionally, we might end up enqueueing the same exact visitation
+      // multiple times: consider the case where the same direct dependency is entailed by aspects
+      // of *different* attributes. These visitations get culled later, but we still have to pay the
+      // overhead for all that.
+
+      if (!(from instanceof Rule) || !(to instanceof Rule)) {
+        return;
+      }
+      Rule fromRule = (Rule) from;
+      Rule toRule = (Rule) to;
+      for (Aspect aspect : attribute.getAspects(fromRule)) {
+        if (AspectDefinition.satisfies(
+            aspect, toRule.getRuleClassObject().getAdvertisedProviders())) {
+          AspectDefinition.forEachLabelDepFromAllAttributesOfAspect(
+              fromRule,
+              aspect,
+              edgeFilter,
+              (aspectAttribute, aspectLabel) ->
+                  enqueueTarget(from, aspectAttribute, aspectLabel, depth, count));
+        }
       }
     }
 
diff --git a/src/main/java/com/google/devtools/build/lib/query2/output/PreciseAspectResolver.java b/src/main/java/com/google/devtools/build/lib/query2/output/PreciseAspectResolver.java
index 8e0e8fb..5fd43d2 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/output/PreciseAspectResolver.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/output/PreciseAspectResolver.java
@@ -13,7 +13,6 @@
 // limitations under the License.
 package com.google.devtools.build.lib.query2.output;
 
-import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMultimap;
 import com.google.common.collect.LinkedListMultimap;
 import com.google.common.collect.Multimap;
@@ -50,25 +49,18 @@
   }
 
   @Override
-  public ImmutableMultimap<Attribute, Label> computeAspectDependencies(Target target,
-      DependencyFilter dependencyFilter) throws InterruptedException {
+  public ImmutableMultimap<Attribute, Label> computeAspectDependencies(
+      Target target, DependencyFilter dependencyFilter) throws InterruptedException {
     Multimap<Attribute, Label> result = LinkedListMultimap.create();
     if (target instanceof Rule) {
       Rule rule = (Rule) target;
       Multimap<Attribute, Label> transitions =
           rule.getTransitions(DependencyFilter.NO_NODEP_ATTRIBUTES);
       for (Attribute attribute : transitions.keySet()) {
-        ImmutableList<Aspect> aspects = attribute.getAspects(rule);
-        for (Label toLabel : transitions.get(attribute)) {
-          Target toTarget;
-          try {
-            toTarget = packageProvider.getTarget(eventHandler, toLabel);
-            result.putAll(
-                AspectDefinition.visitAspectsIfRequired(
-                    target, aspects, toTarget, dependencyFilter));
-          } catch (NoSuchThingException e) {
-            // Do nothing. One of target direct deps has an error. The dependency on the BUILD file
-            // (or one of the files included in it) will be reported in the query result of :BUILD.
+        for (Aspect aspect : attribute.getAspects(rule)) {
+          if (hasDepThatSatisfies(aspect, transitions.get(attribute))) {
+            AspectDefinition.forEachLabelDepFromAllAttributesOfAspect(
+                rule, aspect, dependencyFilter, result::put);
           }
         }
       }
@@ -76,6 +68,29 @@
     return ImmutableMultimap.copyOf(result);
   }
 
+  private boolean hasDepThatSatisfies(Aspect aspect, Iterable<Label> labelDeps)
+      throws InterruptedException {
+    for (Label toLabel : labelDeps) {
+      Target toTarget;
+      try {
+        toTarget = packageProvider.getTarget(eventHandler, toLabel);
+      } catch (NoSuchThingException e) {
+        // Do nothing interesting. One of target direct deps has an error. The dependency on the
+        // BUILD file (or one of the files included in it) will be reported in the query result of
+        // :BUILD.
+        continue;
+      }
+      if (!(toTarget instanceof Rule)) {
+        continue;
+      }
+      if (AspectDefinition.satisfies(
+          aspect, ((Rule) toTarget).getRuleClassObject().getAdvertisedProviders())) {
+        return true;
+      }
+    }
+    return false;
+  }
+
   @Override
   public Set<Label> computeBuildFileDependencies(Package pkg) throws InterruptedException {
     Set<Label> result = new LinkedHashSet<>();
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/TransitiveBaseTraversalFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/TransitiveBaseTraversalFunction.java
index 19bc9ec..1048fbc 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/TransitiveBaseTraversalFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/TransitiveBaseTraversalFunction.java
@@ -23,7 +23,9 @@
 import com.google.common.collect.Sets;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.events.EventHandler;
+import com.google.devtools.build.lib.packages.AdvertisedProviderSet;
 import com.google.devtools.build.lib.packages.Aspect;
+import com.google.devtools.build.lib.packages.AspectDefinition;
 import com.google.devtools.build.lib.packages.Attribute;
 import com.google.devtools.build.lib.packages.BuildFileContainsErrorsException;
 import com.google.devtools.build.lib.packages.DependencyFilter;
@@ -41,7 +43,6 @@
 import com.google.devtools.build.skyframe.SkyValue;
 import com.google.devtools.build.skyframe.ValueOrException2;
 import java.util.Collection;
-import java.util.HashMap;
 import java.util.HashSet;
 import java.util.List;
 import java.util.Map;
@@ -186,41 +187,53 @@
       Environment env)
       throws InterruptedException {
     if (!(target instanceof Rule)) {
+      // Aspects can be declared only for Rules.
       return ImmutableList.of();
     }
 
     Rule rule = (Rule) target;
-    Map<Label, ValueOrException2<NoSuchPackageException, NoSuchTargetException>> labelDepMap =
-        new HashMap<>(depMap.size());
-    for (Map.Entry<SkyKey, ValueOrException2<NoSuchPackageException, NoSuchTargetException>> entry :
-        depMap.entrySet()) {
-      labelDepMap.put(argumentFromKey(entry.getKey()), entry.getValue());
-    }
 
     List<SkyKey> depKeys = Lists.newArrayList();
     Multimap<Attribute, Label> transitions =
         rule.getTransitions(DependencyFilter.NO_NODEP_ATTRIBUTES);
     for (Attribute attribute : transitions.keySet()) {
-      ImmutableList<Aspect> aspects = attribute.getAspects(rule);
-      for (Label toLabel : transitions.get(attribute)) {
-        ValueOrException2<NoSuchPackageException, NoSuchTargetException> value =
-            labelDepMap.get(toLabel);
-        getAspectLabels(rule, aspects, toLabel, value, env)
-            .forEach(aspectLabel -> depKeys.add(getKey(aspectLabel)));
+      for (Aspect aspect : attribute.getAspects(rule)) {
+        if (hasDepThatSatisfies(aspect, transitions.get(attribute), depMap, env)) {
+          AspectDefinition.forEachLabelDepFromAllAttributesOfAspect(
+              rule,
+              aspect,
+              DependencyFilter.ALL_DEPS,
+              (aspectAttribute, aspectLabel) -> depKeys.add(getKey(aspectLabel)));
+        }
       }
     }
     return depKeys;
   }
 
-  /** Get the Aspect-related Label deps for the given edge. */
-  protected abstract Collection<Label> getAspectLabels(
-      Rule fromRule,
-      ImmutableList<Aspect> aspectsOfAttribute,
+  @Nullable
+  protected abstract AdvertisedProviderSet getAdvertisedProviderSet(
       Label toLabel,
-      ValueOrException2<NoSuchPackageException, NoSuchTargetException> toVal,
+      @Nullable ValueOrException2<NoSuchPackageException, NoSuchTargetException> toVal,
       Environment env)
       throws InterruptedException;
 
+  private final boolean hasDepThatSatisfies(
+      Aspect aspect,
+      Iterable<Label> depLabels,
+      Map<SkyKey, ValueOrException2<NoSuchPackageException, NoSuchTargetException>> fullDepMap,
+      Environment env)
+      throws InterruptedException {
+    for (Label depLabel : depLabels) {
+      AdvertisedProviderSet advertisedProviderSet =
+          getAdvertisedProviderSet(depLabel, fullDepMap.get(depLabel), env);
+      if (advertisedProviderSet != null
+          && AspectDefinition.satisfies(aspect, advertisedProviderSet)) {
+        return true;
+      }
+    }
+    return false;
+  }
+
   // TODO(bazel-team): Unify this logic with that in LabelVisitor, and possibly DependencyResolver.
   private static Collection<Label> getLabelDeps(Target target) throws InterruptedException {
     if (target instanceof OutputFile) {
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/TransitiveTargetFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/TransitiveTargetFunction.java
index 4366a0c..5f0be6d 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/TransitiveTargetFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/TransitiveTargetFunction.java
@@ -13,7 +13,6 @@
 // limitations under the License.
 package com.google.devtools.build.lib.skyframe;
 
-import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableSet;
 import com.google.devtools.build.lib.analysis.ConfiguredRuleClassProvider;
 import com.google.devtools.build.lib.analysis.config.BuildConfiguration;
@@ -24,11 +23,9 @@
 import com.google.devtools.build.lib.collect.nestedset.NestedSetBuilder;
 import com.google.devtools.build.lib.events.Event;
 import com.google.devtools.build.lib.events.EventHandler;
-import com.google.devtools.build.lib.packages.Aspect;
-import com.google.devtools.build.lib.packages.AspectDefinition;
+import com.google.devtools.build.lib.packages.AdvertisedProviderSet;
 import com.google.devtools.build.lib.packages.Attribute;
 import com.google.devtools.build.lib.packages.ConfigurationFragmentPolicy;
-import com.google.devtools.build.lib.packages.DependencyFilter;
 import com.google.devtools.build.lib.packages.NoSuchPackageException;
 import com.google.devtools.build.lib.packages.NoSuchTargetException;
 import com.google.devtools.build.lib.packages.NoSuchThingException;
@@ -219,36 +216,38 @@
     }
   }
 
+  @Nullable
   @Override
-  protected Collection<Label> getAspectLabels(
-      Rule fromRule,
-      ImmutableList<Aspect> aspectsOfAttribute,
+  protected AdvertisedProviderSet getAdvertisedProviderSet(
       Label toLabel,
-      ValueOrException2<NoSuchPackageException, NoSuchTargetException> toVal,
-      final Environment env)
+      @Nullable ValueOrException2<NoSuchPackageException, NoSuchTargetException> toVal,
+      Environment env)
       throws InterruptedException {
     SkyKey packageKey = PackageValue.key(toLabel.getPackageIdentifier());
+    Target toTarget;
     try {
       PackageValue pkgValue =
           (PackageValue) env.getValueOrThrow(packageKey, NoSuchPackageException.class);
       if (pkgValue == null) {
-        return ImmutableList.of();
+        return null;
       }
       Package pkg = pkgValue.getPackage();
       if (pkg.containsErrors()) {
-        // Do nothing. This error was handled when we computed the corresponding
+        // Do nothing interesting. This error was handled when we computed the corresponding
         // TransitiveTargetValue.
-        return ImmutableList.of();
+        return null;
       }
-      Target dependedTarget = pkgValue.getPackage().getTarget(toLabel.getName());
-      return AspectDefinition.visitAspectsIfRequired(
-              fromRule, aspectsOfAttribute, dependedTarget, DependencyFilter.ALL_DEPS)
-          .values();
+      toTarget = pkgValue.getPackage().getTarget(toLabel.getName());
     } catch (NoSuchThingException e) {
-      // Do nothing. This error was handled when we computed the corresponding
+      // Do nothing interesting. This error was handled when we computed the corresponding
       // TransitiveTargetValue.
-      return ImmutableList.of();
+      return null;
     }
+    if (!(toTarget instanceof Rule)) {
+      // Aspect can be declared only for Rules.
+      return null;
+    }
+    return ((Rule) toTarget).getRuleClassObject().getAdvertisedProviders();
   }
 
   @Override
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/TransitiveTraversalFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/TransitiveTraversalFunction.java
index 96cee0f..3f72cf9 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/TransitiveTraversalFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/TransitiveTraversalFunction.java
@@ -14,17 +14,13 @@
 package com.google.devtools.build.lib.skyframe;
 
 import com.google.common.base.Preconditions;
-import com.google.common.collect.ImmutableList;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.collect.nestedset.NestedSet;
 import com.google.devtools.build.lib.events.EventHandler;
-import com.google.devtools.build.lib.packages.Aspect;
-import com.google.devtools.build.lib.packages.AspectDefinition;
-import com.google.devtools.build.lib.packages.DependencyFilter;
+import com.google.devtools.build.lib.packages.AdvertisedProviderSet;
 import com.google.devtools.build.lib.packages.NoSuchPackageException;
 import com.google.devtools.build.lib.packages.NoSuchTargetException;
 import com.google.devtools.build.lib.packages.NoSuchThingException;
-import com.google.devtools.build.lib.packages.Rule;
 import com.google.devtools.build.lib.skyframe.TransitiveTraversalFunction.FirstErrorMessageAccumulator;
 import com.google.devtools.build.lib.util.GroupedList;
 import com.google.devtools.build.skyframe.SkyFunction;
@@ -89,30 +85,21 @@
     }
   }
 
+  @Nullable
   @Override
-  protected Collection<Label> getAspectLabels(
-      Rule fromRule,
-      ImmutableList<Aspect> aspectsOfAttribute,
+  protected AdvertisedProviderSet getAdvertisedProviderSet(
       Label toLabel,
-      ValueOrException2<NoSuchPackageException, NoSuchTargetException> toVal,
+      @Nullable ValueOrException2<NoSuchPackageException, NoSuchTargetException> toVal,
       Environment env) {
+    if (toVal == null) {
+      return null;
+    }
     try {
-      if (toVal == null) {
-        return ImmutableList.of();
-      }
-      TransitiveTraversalValue traversalVal = (TransitiveTraversalValue) toVal.get();
-      if (traversalVal == null || traversalVal.getProviders() == null) {
-        return ImmutableList.of();
-      }
-      // Retrieve the providers of the dep from the TransitiveTraversalValue, so we can avoid
-      // issuing a dep on its defining Package.
-      return AspectDefinition.visitAspectsIfRequired(
-              fromRule, aspectsOfAttribute, traversalVal.getProviders(), DependencyFilter.ALL_DEPS)
-          .values();
+      return ((TransitiveTraversalValue) toVal.get()).getProviders();
     } catch (NoSuchThingException e) {
-      // Do nothing. This error was handled when we computed the corresponding
+      // Do nothing interesting. This error was handled when we computed the corresponding
       // TransitiveTargetValue.
-      return ImmutableList.of();
+      return null;
     }
   }