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 e1b5f05..683cdd9f5 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
@@ -21,9 +21,12 @@
 import com.google.common.collect.LinkedHashMultimap;
 import com.google.common.collect.Multimap;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
+import com.google.devtools.build.lib.syntax.Label;
+import com.google.devtools.build.lib.util.BinaryPredicate;
 
 import java.util.LinkedHashMap;
 import java.util.LinkedHashSet;
+import java.util.List;
 import java.util.Map;
 import java.util.Set;
 
@@ -102,6 +105,53 @@
   }
 
   /**
+   * Returns the attribute -&gt; set of labels that are provided by aspects of attribute.
+   */
+  public static ImmutableMultimap<Attribute, Label> visitAspectsIfRequired(
+      Target from, Attribute attribute, Target to) {
+    ImmutableMultimap.Builder<Attribute, Label> labelBuilder = ImmutableMultimap.builder();
+    // Aspect can be declared only for Rules.
+    if (!(from instanceof Rule) || !(to instanceof Rule)) {
+      return labelBuilder.build();
+    }
+    RuleClass ruleClass = ((Rule) to).getRuleClassObject();
+    for (Class<? extends AspectFactory<?, ?, ?>> candidateClass : attribute.getAspects()) {
+      AspectFactory<?, ?, ?> candidate = AspectFactory.Util.create(candidateClass);
+      // Check if target satisfies condition for this aspect (has to provide all required
+      // TransitiveInfoProviders)
+      if (!ruleClass.getAdvertisedProviders().containsAll(
+          candidate.getDefinition().getRequiredProviders())) {
+        continue;
+      }
+      addAllAttributesOfAspect((Rule) from, labelBuilder, candidate.getDefinition(), Rule.ALL_DEPS);
+    }
+    return labelBuilder.build();
+  }
+
+  /**
+   * Collects all attribute labels from the specified aspectDefinition.
+   */
+  public static void addAllAttributesOfAspect(Rule from,
+      ImmutableMultimap.Builder<Attribute, Label> labelBuilder, AspectDefinition aspectDefinition,
+      BinaryPredicate<Rule, Attribute> predicate) {
+    ImmutableMap<String, Attribute> attributes = aspectDefinition.getAttributes();
+    for (Attribute aspectAttribute : attributes.values()) {
+      if (!predicate.apply(from, aspectAttribute)) {
+        continue;
+      }
+      if (aspectAttribute.getType() == Type.LABEL) {
+        Label label = Type.LABEL.cast(aspectAttribute.getDefaultValue(from));
+        if (label != null) {
+          labelBuilder.put(aspectAttribute, label);
+        }
+      } else if (aspectAttribute.getType() == Type.LABEL_LIST) {
+        List<Label> labelList = Type.LABEL_LIST.cast(aspectAttribute.getDefaultValue(from));
+        labelBuilder.putAll(aspectAttribute, labelList);
+      }
+    }
+  }
+
+  /**
    * Builder class for {@link AspectDefinition}.
    */
   public static final class Builder {
diff --git a/src/main/java/com/google/devtools/build/lib/packages/Rule.java b/src/main/java/com/google/devtools/build/lib/packages/Rule.java
index af7aa48..0b6c0ea 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/Rule.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/Rule.java
@@ -17,12 +17,15 @@
 import com.google.common.base.Preconditions;
 import com.google.common.base.Predicate;
 import com.google.common.base.Predicates;
+import com.google.common.collect.HashMultimap;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableListMultimap;
+import com.google.common.collect.ImmutableMultimap;
 import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.LinkedListMultimap;
 import com.google.common.collect.ListMultimap;
 import com.google.common.collect.Lists;
+import com.google.common.collect.Multimap;
 import com.google.devtools.build.lib.events.Event;
 import com.google.devtools.build.lib.events.EventHandler;
 import com.google.devtools.build.lib.events.Location;
@@ -36,7 +39,6 @@
 import com.google.devtools.build.lib.util.BinaryPredicate;
 
 import java.util.Collection;
-import java.util.HashSet;
 import java.util.LinkedHashSet;
 import java.util.List;
 import java.util.Set;
@@ -436,7 +438,21 @@
    *     result iff (the predicate returned {@code true} and the labels are not outputs)
    */
   public Collection<Label> getLabels(final BinaryPredicate<Rule, Attribute> predicate) {
-    final Set<Label> labels = new HashSet<>();
+    return getTransitions(predicate).values();
+  }
+
+  /**
+   * Returns a new Multimap containing all attributes that match a given Predicate and
+   * corresponding labels, not including outputs.
+   *
+   * @param predicate A binary predicate that determines if a label should be
+   *     included in the result. The predicate is evaluated with this rule and
+   *     the attribute that contains the label. The label will be contained in the
+   *     result iff (the predicate returned {@code true} and the labels are not outputs)
+   */
+  public Multimap<Attribute, Label> getTransitions(
+      final BinaryPredicate<Rule, Attribute> predicate) {
+    final Multimap<Attribute, Label> transitions = HashMultimap.create();
     // TODO(bazel-team): move this to AttributeMap, too. Just like visitLabels, which labels should
     // be visited may depend on the calling context. We shouldn't implicitly decide this for
     // the caller.
@@ -444,11 +460,11 @@
       @Override
       public void acceptLabelAttribute(Label label, Attribute attribute) {
         if (predicate.apply(Rule.this, attribute)) {
-          labels.add(label);
+          transitions.put(attribute, label);
         }
       }
     });
-    return labels;
+    return transitions;
   }
 
   /**
@@ -680,4 +696,21 @@
     }
     return ruleTags;
   }
+
+  /**
+   * Computes labels of additional dependencies that can be provided by aspects that this rule
+   * can require from its direct dependencies.
+   */
+  public Collection<? extends Label> getAspectLabelsSuperset(
+      BinaryPredicate<Rule, Attribute> predicate) {
+    ImmutableMultimap.Builder<Attribute, Label> labelBuilder = ImmutableMultimap.builder();
+    for (Attribute attribute : this.getAttributes()) {
+      for (Class<? extends AspectFactory<?, ?, ?>> candidateClass : attribute.getAspects()) {
+        AspectFactory<?, ?, ?> candidate = AspectFactory.Util.create(candidateClass);
+        AspectDefinition.addAllAttributesOfAspect(Rule.this, labelBuilder,
+            candidate.getDefinition(), predicate);
+      }
+    }
+    return labelBuilder.build().values();
+  }
 }
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 fd3068f..e2cf9ea 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
@@ -18,18 +18,15 @@
 import com.google.common.base.Throwables;
 import com.google.common.collect.HashMultimap;
 import com.google.common.collect.ImmutableList;
-import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableMultimap;
 import com.google.common.collect.MapMaker;
 import com.google.common.collect.Multimaps;
 import com.google.common.collect.SetMultimap;
-import com.google.common.collect.Sets;
-import com.google.devtools.build.lib.analysis.ConfiguredAspectFactory;
 import com.google.devtools.build.lib.concurrent.AbstractQueueVisitor;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
 import com.google.devtools.build.lib.events.EventHandler;
 import com.google.devtools.build.lib.packages.AggregatingAttributeMapper;
-import com.google.devtools.build.lib.packages.AspectFactory;
+import com.google.devtools.build.lib.packages.AspectDefinition;
 import com.google.devtools.build.lib.packages.Attribute;
 import com.google.devtools.build.lib.packages.AttributeMap;
 import com.google.devtools.build.lib.packages.InputFile;
@@ -38,16 +35,13 @@
 import com.google.devtools.build.lib.packages.Package;
 import com.google.devtools.build.lib.packages.PackageGroup;
 import com.google.devtools.build.lib.packages.Rule;
-import com.google.devtools.build.lib.packages.RuleClass;
 import com.google.devtools.build.lib.packages.Target;
-import com.google.devtools.build.lib.packages.Type;
 import com.google.devtools.build.lib.pkgcache.PackageProvider;
 import com.google.devtools.build.lib.pkgcache.TargetEdgeObserver;
 import com.google.devtools.build.lib.syntax.Label;
 import com.google.devtools.build.lib.util.BinaryPredicate;
 
 import java.util.Collection;
-import java.util.List;
 import java.util.Map.Entry;
 import java.util.concurrent.ConcurrentMap;
 import java.util.concurrent.TimeUnit;
@@ -427,42 +421,11 @@
 
     private void visitAspectsIfRequired(
         Target from, Attribute attribute, final Target to, int depth, int count) {
-      // Aspect can be declared only for Rules.
-      if (!(from instanceof Rule) || !(to instanceof Rule)) {
-        return;
-      }
-
-      ImmutableMultimap.Builder<Attribute, Label> labelBuilder = ImmutableMultimap.builder();
-      RuleClass ruleClass = ((Rule) to).getRuleClassObject();
-
-      for (Class<? extends AspectFactory<?, ?, ?>> candidateClass : attribute.getAspects()) {
-        ConfiguredAspectFactory candidate =
-            (ConfiguredAspectFactory) AspectFactory.Util.create(candidateClass);
-        // Check if target satisfies condition for this aspect (has to provide all required
-        // TransitiveInfoProviders)
-        if (!Sets.difference(
-            candidate.getDefinition().getRequiredProviders(),
-            ruleClass.getAdvertisedProviders()).isEmpty()) {
-          continue;
-        }
-        ImmutableMap<String, Attribute> attributes = candidate.getDefinition().getAttributes();
-        for (Attribute aspectAttribute : attributes.values()) {
-          if (aspectAttribute.getType() == Type.LABEL) {
-            Label label = Type.LABEL.cast(aspectAttribute.getDefaultValue((Rule) from));
-            if (label != null) {
-              labelBuilder.put(aspectAttribute, label);
-            }
-          } else if (attribute.getType() == Type.LABEL_LIST) {
-            List<Label> labelList = Type.LABEL_LIST.cast(attribute.getDefaultValue((Rule) from));
-            labelBuilder.putAll(aspectAttribute, labelList);
-          }
-        }
-      }
-
-      ImmutableMultimap<Attribute, Label> labelsFromAspects = labelBuilder.build();
+      ImmutableMultimap<Attribute, Label> labelsFromAspects =
+          AspectDefinition.visitAspectsIfRequired(from, attribute, to);
       // Create an edge from target to the attribute value.
       for (Entry<Attribute, Label> entry : labelsFromAspects.entries()) {
-        enqueueTarget(to, entry.getKey(), entry.getValue(), depth, count);
+        enqueueTarget(from, entry.getKey(), entry.getValue(), depth, count);
       }
     }
 
diff --git a/src/main/java/com/google/devtools/build/lib/query2/SkyQueryEnvironment.java b/src/main/java/com/google/devtools/build/lib/query2/SkyQueryEnvironment.java
index dfe805e..deb2d08 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/SkyQueryEnvironment.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/SkyQueryEnvironment.java
@@ -144,6 +144,8 @@
   private Set<Label> getAllowedDeps(Rule rule) {
     Set<Label> allowedLabels = new HashSet<>(rule.getLabels(dependencyFilter));
     allowedLabels.addAll(rule.getVisibility().getDependencyLabels());
+    // We should add deps from aspects, otherwise they are going to be filtered out.
+    allowedLabels.addAll(rule.getAspectLabelsSuperset(dependencyFilter));
     return allowedLabels;
   }
 
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 339e431..8e818f3 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
@@ -14,10 +14,13 @@
 package com.google.devtools.build.lib.skyframe;
 
 import com.google.common.collect.Lists;
+import com.google.common.collect.Multimap;
 import com.google.devtools.build.lib.collect.nestedset.NestedSet;
 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.AspectDefinition;
+import com.google.devtools.build.lib.packages.Attribute;
 import com.google.devtools.build.lib.packages.InputFile;
 import com.google.devtools.build.lib.packages.NoSuchPackageException;
 import com.google.devtools.build.lib.packages.NoSuchTargetException;
@@ -35,9 +38,10 @@
 import com.google.devtools.build.skyframe.SkyValue;
 import com.google.devtools.build.skyframe.ValueOrException;
 
+import java.util.Collection;
 import java.util.HashSet;
 import java.util.List;
-import java.util.Map;
+import java.util.Map.Entry;
 import java.util.Set;
 
 /**
@@ -97,8 +101,43 @@
       transitiveUnsuccessfulPkgs.add(packageId);
     }
     transitiveTargets.add(target.getLabel());
-    for (Map.Entry<SkyKey, ValueOrException<NoSuchThingException>> entry :
-        env.getValuesOrThrow(getLabelDepKeys(target), NoSuchThingException.class).entrySet()) {
+
+    // Process deps from attributes of current target.
+    Iterable<SkyKey> depKeys = getLabelDepKeys(target);
+    successfulTransitiveLoading &= processDeps(env, target, transitiveRootCauses,
+        transitiveSuccessfulPkgs, transitiveUnsuccessfulPkgs, transitiveTargets, depKeys);
+    if (env.valuesMissing()) {
+      return null;
+    }
+    // Process deps from aspects.
+    depKeys = getLabelAspectKeys(target, env);
+    successfulTransitiveLoading &= processDeps(env, target, transitiveRootCauses,
+        transitiveSuccessfulPkgs, transitiveUnsuccessfulPkgs, transitiveTargets, depKeys);
+    if (env.valuesMissing()) {
+      return null;
+    }
+
+    NestedSet<PackageIdentifier> successfullyLoadedPackages = transitiveSuccessfulPkgs.build();
+    NestedSet<PackageIdentifier> unsuccessfullyLoadedPackages = transitiveUnsuccessfulPkgs.build();
+    NestedSet<Label> loadedTargets = transitiveTargets.build();
+    if (successfulTransitiveLoading) {
+      return TransitiveTargetValue.successfulTransitiveLoading(successfullyLoadedPackages,
+          unsuccessfullyLoadedPackages, loadedTargets);
+    } else {
+      NestedSet<Label> rootCauses = transitiveRootCauses.build();
+      return TransitiveTargetValue.unsuccessfulTransitiveLoading(successfullyLoadedPackages,
+          unsuccessfullyLoadedPackages, loadedTargets, rootCauses, errorLoadingTarget);
+    }
+  }
+
+  private boolean processDeps(Environment env, Target target,
+      NestedSetBuilder<Label> transitiveRootCauses,
+      NestedSetBuilder<PackageIdentifier> transitiveSuccessfulPkgs,
+      NestedSetBuilder<PackageIdentifier> transitiveUnsuccessfulPkgs,
+      NestedSetBuilder<Label> transitiveTargets, Iterable<SkyKey> depKeys) {
+    boolean successfulTransitiveLoading = true;
+    for (Entry<SkyKey, ValueOrException<NoSuchThingException>> entry :
+        env.getValuesOrThrow(depKeys, NoSuchThingException.class).entrySet()) {
       Label depLabel = (Label) entry.getKey().argument();
       TransitiveTargetValue transitiveTargetValue;
       try {
@@ -129,22 +168,7 @@
         }
       }
     }
-
-    if (env.valuesMissing()) {
-      return null;
-    }
-
-    NestedSet<PackageIdentifier> successfullyLoadedPackages = transitiveSuccessfulPkgs.build();
-    NestedSet<PackageIdentifier> unsuccessfullyLoadedPackages = transitiveUnsuccessfulPkgs.build();
-    NestedSet<Label> loadedTargets = transitiveTargets.build();
-    if (successfulTransitiveLoading) {
-      return TransitiveTargetValue.successfulTransitiveLoading(successfullyLoadedPackages,
-          unsuccessfullyLoadedPackages, loadedTargets);
-    } else {
-      NestedSet<Label> rootCauses = transitiveRootCauses.build();
-      return TransitiveTargetValue.unsuccessfulTransitiveLoading(successfullyLoadedPackages,
-          unsuccessfullyLoadedPackages, loadedTargets, rootCauses, errorLoadingTarget);
-    }
+    return successfulTransitiveLoading;
   }
 
   @Override
@@ -169,6 +193,33 @@
     }
   }
 
+  private static Iterable<SkyKey> getLabelAspectKeys(Target target, Environment env) {
+    List<SkyKey> depKeys = Lists.newArrayList();
+    if (target instanceof Rule) {
+      Multimap<Attribute, Label> transitions =
+          ((Rule) target).getTransitions(Rule.NO_NODEP_ATTRIBUTES);
+      for (Entry<Attribute, Label> entry : transitions.entries()) {
+        SkyKey packageKey = PackageValue.key(entry.getValue().getPackageIdentifier());
+        try {
+          PackageValue pkgValue = (PackageValue) env.getValueOrThrow(packageKey,
+              NoSuchThingException.class);
+          if (pkgValue == null) {
+            continue;
+          }
+          Collection<Label> labels = AspectDefinition.visitAspectsIfRequired(target, entry.getKey(),
+              pkgValue.getPackage().getTarget(entry.getValue().getName())).values();
+          for (Label label : labels) {
+            depKeys.add(TransitiveTargetValue.key(label));
+          }
+        } catch (NoSuchThingException e) {
+          // Do nothing. This error was handled when we computed the corresponding
+          // TransitiveTargetValue.
+        }
+      }
+    }
+    return depKeys;
+  }
+
   private static Iterable<SkyKey> getLabelDepKeys(Target target) {
     List<SkyKey> depKeys = Lists.newArrayList();
     for (Label depLabel : getLabelDeps(target)) {
@@ -188,13 +239,17 @@
       visitTargetVisibility(target, labels);
     } else if (target instanceof Rule) {
       visitTargetVisibility(target, labels);
-      labels.addAll(((Rule) target).getLabels(Rule.NO_NODEP_ATTRIBUTES));
+      visitRule(target, labels);
     } else if (target instanceof PackageGroup) {
       visitPackageGroup((PackageGroup) target, labels);
     }
     return labels;
   }
 
+  private static void visitRule(Target target, Set<Label> labels) {
+    labels.addAll(((Rule) target).getLabels(Rule.NO_NODEP_ATTRIBUTES));
+  }
+
   private static void visitTargetVisibility(Target target, Set<Label> labels) {
     labels.addAll(target.getVisibility().getDependencyLabels());
   }