diff --git a/src/main/java/com/google/devtools/build/lib/packages/AggregatingAttributeMapper.java b/src/main/java/com/google/devtools/build/lib/packages/AggregatingAttributeMapper.java
index afc4b7d..dff87be 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/AggregatingAttributeMapper.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/AggregatingAttributeMapper.java
@@ -16,6 +16,8 @@
 import com.google.common.base.Preconditions;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
+import com.google.common.collect.ImmutableSet;
+import com.google.devtools.build.lib.collect.CollectionUtils;
 import com.google.devtools.build.lib.syntax.Label;
 
 import java.util.ArrayList;
@@ -23,6 +25,7 @@
 import java.util.LinkedList;
 import java.util.List;
 import java.util.Map;
+import java.util.Set;
 
 import javax.annotation.Nullable;
 
@@ -68,6 +71,11 @@
    */
   @Override
   protected void visitLabels(Attribute attribute, AcceptsLabelAttribute observer) {
+    visitLabels(attribute, true, observer);
+  }
+
+  private void visitLabels(Attribute attribute, boolean includeSelectKeys,
+    AcceptsLabelAttribute observer) {
     Type<?> type = attribute.getType();
     Type.SelectorList<?> selectorList = getSelectorList(attribute.getName(), type);
     if (selectorList == null) {
@@ -87,7 +95,7 @@
     } else {
       for (Type.Selector<?> selector : selectorList.getSelectors()) {
         for (Map.Entry<Label, ?> selectorEntry : selector.getEntries().entrySet()) {
-          if (!Type.Selector.isReservedLabel(selectorEntry.getKey())) {
+          if (includeSelectKeys && !Type.Selector.isReservedLabel(selectorEntry.getKey())) {
             observer.acceptLabelAttribute(selectorEntry.getKey(), attribute);
           }
           for (Label value : type.getLabels(selectorEntry.getValue())) {
@@ -99,23 +107,57 @@
   }
 
   /**
-   * Returns all labels reachable via the given attribute.
+   * Returns all labels reachable via the given attribute. If a label is listed multiple times,
+   * each instance appears in the returned list.
    *
-   * <p>Use this over {@link #visitAttribute} when this is sufficient, since the latter grows
-   * exponentially with respect to the number of selects in the attribute.
+   * @param includeSelectKeys whether to include config_setting keys for configurable attributes
    */
-  public Iterable<Label> getReachableLabels(String attributeName) {
+  public List<Label> getReachableLabels(String attributeName, boolean includeSelectKeys) {
     final ImmutableList.Builder<Label> builder = ImmutableList.builder();
-    visitLabels(getAttributeDefinition(attributeName), new AcceptsLabelAttribute() {
-      @Override
-      public void acceptLabelAttribute(Label label, Attribute attribute) {
-        builder.add(label);
-      }
-    });
+    visitLabels(getAttributeDefinition(attributeName), includeSelectKeys,
+        new AcceptsLabelAttribute() {
+          @Override
+          public void acceptLabelAttribute(Label label, Attribute attribute) {
+            builder.add(label);
+          }
+        });
     return builder.build();
   }
 
   /**
+   * Returns the labels that might appear multiple times in the same attribute value.
+   */
+  public Set<Label> checkForDuplicateLabels(Attribute attribute) {
+    String attrName = attribute.getName();
+    Type<?> attrType = attribute.getType();
+
+    Type.SelectorList<?> selectorList = getSelectorList(attribute.getName(), attrType);
+    if (selectorList == null || selectorList.getSelectors().size() == 1) {
+      // Three possible scenarios:
+      //  1) Plain old attribute (no selects). Without selects, visitAttribute runs efficiently.
+      //  2) Computed default, possibly depending on other attributes using select. In this case,
+      //     visitAttribute might be inefficient. But we have no choice but to iterate over all
+      //     possible values (since we have to compute them), so we take the efficiency hit.
+      //  3) "attr = select({...})". With just a single select, visitAttribute runs efficiently.
+      ImmutableSet.Builder<Label> duplicates = ImmutableSet.builder();
+      for (Object value : visitAttribute(attrName, attrType)) {
+        if (value != null) {
+          duplicates.addAll(CollectionUtils.duplicatedElementsOf(
+              ImmutableList.copyOf(attrType.getLabels(value))));
+        }
+      }
+      return duplicates.build();
+    } else {
+      // Multiple selects concatenated together. It's expensive to iterate over every possible
+      // value, so instead collect all labels across all the selects and check for duplicates.
+      // This is overly strict, since this counts duplicates across values. We can presumably
+      // relax this if necessary, but doing so would incur the value iteration expense this
+      // code path avoids.
+      return CollectionUtils.duplicatedElementsOf(getReachableLabels(attrName, false));
+    }
+  }
+
+  /**
    * Returns a list of all possible values an attribute can take for this rule.
    *
    * <p>Note that when an attribute uses multiple selects, it can potentially take on many
diff --git a/src/main/java/com/google/devtools/build/lib/packages/RuleClass.java b/src/main/java/com/google/devtools/build/lib/packages/RuleClass.java
index 4521b33..c06b06b 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/RuleClass.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/RuleClass.java
@@ -26,7 +26,6 @@
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.Ordering;
-import com.google.devtools.build.lib.collect.CollectionUtils;
 import com.google.devtools.build.lib.events.EventHandler;
 import com.google.devtools.build.lib.events.Location;
 import com.google.devtools.build.lib.syntax.Argument;
@@ -1345,19 +1344,11 @@
    */
   private static void checkForDuplicateLabels(Rule rule, Attribute attribute,
        EventHandler eventHandler) {
-    final String attrName = attribute.getName();
-    // This attribute may be selectable, so iterate over each selection possibility in turn.
-    // TODO(bazel-team): merge '*' condition into all lists when implemented.
-    AggregatingAttributeMapper attributeMap = AggregatingAttributeMapper.of(rule);
-    for (List<Label> labels : attributeMap.visitAttribute(attrName, Type.LABEL_LIST)) {
-      if (!labels.isEmpty()) {
-        Set<Label> duplicates = CollectionUtils.duplicatedElementsOf(labels);
-        for (Label label : duplicates) {
-          rule.reportError(
-              String.format("Label '%s' is duplicated in the '%s' attribute of rule '%s'",
-              label, attrName, rule.getName()), eventHandler);
-        }
-      }
+    Set<Label> duplicates = AggregatingAttributeMapper.of(rule).checkForDuplicateLabels(attribute);
+    for (Label label : duplicates) {
+      rule.reportError(
+          String.format("Label '%s' is duplicated in the '%s' attribute of rule '%s'",
+          label, attribute.getName(), rule.getName()), eventHandler);
     }
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/query2/BlazeTargetAccessor.java b/src/main/java/com/google/devtools/build/lib/query2/BlazeTargetAccessor.java
index bc1689b..7e59731 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/BlazeTargetAccessor.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/BlazeTargetAccessor.java
@@ -83,16 +83,12 @@
       // Return an empty list if the attribute isn't defined for this rule.
       return ImmutableList.of();
     }
-    for (Object value : attrMap.visitAttribute(attrName, attrType)) {
-      // Computed defaults may have null values.
-      if (value != null) {
-        for (Label label : attrType.getLabels(value)) {
-          try {
-            result.add(queryEnvironment.getTarget(label));
-          } catch (TargetNotFoundException e) {
-            queryEnvironment.reportBuildFileError(caller, errorMsgPrefix + e.getMessage());
-          }
-        }
+
+    for (Label label : attrMap.getReachableLabels(attrName, false)) {
+      try {
+        result.add(queryEnvironment.getTarget(label));
+      } catch (TargetNotFoundException e) {
+        queryEnvironment.reportBuildFileError(caller, errorMsgPrefix + e.getMessage());
       }
     }