diff --git a/src/com/facebook/buck/android/AndroidBinaryGraphEnhancer.java b/src/com/facebook/buck/android/AndroidBinaryGraphEnhancer.java
new file mode 100644
index 0000000..4c2ff26
--- /dev/null
+++ b/src/com/facebook/buck/android/AndroidBinaryGraphEnhancer.java
@@ -0,0 +1,117 @@
+/*
+ * Copyright 2013-present Facebook, Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License"); you may
+ * not use this file except in compliance with the License. You may obtain
+ * a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+ * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+ * License for the specific language governing permissions and limitations
+ * under the License.
+ */
+
+package com.facebook.buck.android;
+
+import com.facebook.buck.java.AccumulateClassNames;
+import com.facebook.buck.java.Classpaths;
+import com.facebook.buck.java.JavaLibraryRule;
+import com.facebook.buck.model.BuildTarget;
+import com.facebook.buck.model.BuildTargetPattern;
+import com.facebook.buck.rules.AbstractBuildRuleBuilderParams;
+import com.facebook.buck.rules.BuildRule;
+import com.facebook.buck.rules.BuildRuleResolver;
+import com.facebook.buck.rules.DefaultBuildRuleBuilderParams;
+import com.facebook.buck.rules.RuleKeyBuilderFactory;
+import com.google.common.base.Function;
+import com.google.common.base.Preconditions;
+import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.ImmutableSortedSet;
+
+import java.nio.file.Path;
+
+public class AndroidBinaryGraphEnhancer {
+
+  private final ImmutableSortedSet<BuildRule> originalDeps;
+  private final ImmutableSet<BuildTarget> buildRulesToExcludeFromDex;
+  private final AbstractBuildRuleBuilderParams buildRuleBuilderParams;
+
+  AndroidBinaryGraphEnhancer(
+      ImmutableSortedSet<BuildRule> originalDeps,
+      ImmutableSet<BuildTarget> buildRulesToExcludeFromDex,
+      Function<String, Path> pathRelativizer,
+      RuleKeyBuilderFactory ruleKeyBuilderFactory) {
+    this.originalDeps = Preconditions.checkNotNull(originalDeps);
+    this.buildRulesToExcludeFromDex = Preconditions.checkNotNull(buildRulesToExcludeFromDex);
+    this.buildRuleBuilderParams = new DefaultBuildRuleBuilderParams(
+        pathRelativizer, ruleKeyBuilderFactory);
+  }
+
+  /**
+   * Creates/finds the set of build rules that correspond to pre-dex'd artifacts that should be
+   * merged to create the final classes.dex for the APK.
+   * <p>
+   * This method may modify {@code ruleResolver}, inserting new rules into its index.
+   */
+  ImmutableSet<IntermediateDexRule> createDepsForPreDexing(BuildRuleResolver ruleResolver) {
+    ImmutableSet.Builder<IntermediateDexRule> preDexDeps = ImmutableSet.builder();
+    ImmutableSet<JavaLibraryRule> transitiveJavaDeps = Classpaths
+        .getClasspathEntries(originalDeps).keySet();
+    for (JavaLibraryRule javaLibraryRule : transitiveJavaDeps) {
+      // If the rule has no output file (which happens when a java_library has no srcs or
+      // resources, but export_deps is true), then there will not be anything to dx.
+      if (javaLibraryRule.getPathToOutputFile() == null) {
+        continue;
+      }
+
+      // If the rule is in the no_dx list, then do not pre-dex it.
+      if (buildRulesToExcludeFromDex.contains(javaLibraryRule.getBuildTarget())) {
+        continue;
+      }
+
+      // See whether the corresponding IntermediateDexRule has already been added to the
+      // ruleResolver.
+      BuildTarget originalTarget = javaLibraryRule.getBuildTarget();
+      BuildTarget preDexTarget = createBuildTargetWithDexFlavor(originalTarget);
+      IntermediateDexRule preDexRule = (IntermediateDexRule) ruleResolver.get(preDexTarget);
+      if (preDexRule != null) {
+        preDexDeps.add(preDexRule);
+        continue;
+      }
+
+      // Create a rule to get the list of the classes in the JavaLibraryRule.
+      BuildTarget accumulateClassNamesBuildTarget = new BuildTarget(
+          originalTarget.getBaseName(), originalTarget.getShortName(), "class_names");
+      AccumulateClassNames.Builder accumulateClassNamesBuilder = AccumulateClassNames
+          .newAccumulateClassNamesBuilder(buildRuleBuilderParams)
+          .setBuildTarget(accumulateClassNamesBuildTarget)
+          .setJavaLibraryToDex(javaLibraryRule)
+          .addDep(originalTarget)
+          .addVisibilityPattern(BuildTargetPattern.MATCH_ALL);
+      BuildRule accumulateClassNamesRule = ruleResolver.buildAndAddToIndex(
+          accumulateClassNamesBuilder);
+      AccumulateClassNames accumulateClassNames =
+          (AccumulateClassNames) accumulateClassNamesRule.getBuildable();
+
+      // Create the IntermediateDexRule and add it to both the ruleResolver and preDexDeps.
+      IntermediateDexRule.Builder preDexBuilder = IntermediateDexRule
+          .newPreDexBuilder(buildRuleBuilderParams)
+          .setBuildTarget(preDexTarget)
+          .setAccumulateClassNamesDep(accumulateClassNames)
+          .addDep(accumulateClassNamesBuildTarget)
+          .addVisibilityPattern(BuildTargetPattern.MATCH_ALL);
+      IntermediateDexRule preDex = ruleResolver.buildAndAddToIndex(preDexBuilder);
+      preDexDeps.add(preDex);
+    }
+    return preDexDeps.build();
+  }
+
+  private static BuildTarget createBuildTargetWithDexFlavor(BuildTarget originalTarget) {
+    return new BuildTarget(originalTarget.getBaseName(),
+        originalTarget.getShortName(),
+        "dex");
+  }
+}
diff --git a/src/com/facebook/buck/android/AndroidBinaryRule.java b/src/com/facebook/buck/android/AndroidBinaryRule.java
index 28ae645..f6ece50 100644
--- a/src/com/facebook/buck/android/AndroidBinaryRule.java
+++ b/src/com/facebook/buck/android/AndroidBinaryRule.java
@@ -22,7 +22,6 @@
 import com.android.common.SdkConstants;
 import com.facebook.buck.android.FilterResourcesStep.ResourceFilter;
 import com.facebook.buck.dalvik.ZipSplitter;
-import com.facebook.buck.java.AccumulateClassNames;
 import com.facebook.buck.java.Classpaths;
 import com.facebook.buck.java.HasClasspathEntries;
 import com.facebook.buck.java.JavaLibraryRule;
@@ -39,13 +38,11 @@
 import com.facebook.buck.rules.Buildable;
 import com.facebook.buck.rules.BuildableContext;
 import com.facebook.buck.rules.BuildableProperties;
-import com.facebook.buck.rules.DefaultBuildRuleBuilderParams;
 import com.facebook.buck.rules.DependencyGraph;
 import com.facebook.buck.rules.DoNotUseAbstractBuildable;
 import com.facebook.buck.rules.FileSourcePath;
 import com.facebook.buck.rules.InstallableBuildRule;
 import com.facebook.buck.rules.RuleKey;
-import com.facebook.buck.rules.RuleKeyBuilderFactory;
 import com.facebook.buck.rules.SourcePath;
 import com.facebook.buck.shell.AbstractGenruleStep;
 import com.facebook.buck.shell.EchoStep;
@@ -78,7 +75,6 @@
 import com.google.common.collect.ImmutableSetMultimap;
 import com.google.common.collect.ImmutableSortedSet;
 import com.google.common.collect.Iterables;
-import com.google.common.collect.Sets;
 import com.google.common.io.Files;
 
 import java.io.File;
@@ -198,7 +194,7 @@
 
   private final FilterResourcesStep.ResourceFilter resourceFilter;
   private final ImmutableSet<TargetCpuType> cpuFilters;
-  private final ImmutableSet<DexProducedFromJavaLibraryThatContainsClassFiles> preDexDeps;
+  private final ImmutableSet<IntermediateDexRule> preDexDeps;
   private final ImmutableSortedSet<BuildRule> preprocessJavaClassesDeps;
   private final Optional<String> preprocessJavaClassesBash;
   private final AndroidTransitiveDependencyGraph transitiveDependencyGraph;
@@ -228,7 +224,7 @@
       Optional<SourcePath> primaryDexClassesFile,
       FilterResourcesStep.ResourceFilter resourceFilter,
       Set<TargetCpuType> cpuFilters,
-      Set<DexProducedFromJavaLibraryThatContainsClassFiles> preDexDeps,
+      Set<IntermediateDexRule> preDexDeps,
       Set<BuildRule> preprocessJavaClassesDeps,
       Optional<String> preprocessJavaClassesBash) {
     super(buildRuleParams);
@@ -333,7 +329,7 @@
     return this.cpuFilters;
   }
 
-  public ImmutableSet<DexProducedFromJavaLibraryThatContainsClassFiles> getPreDexDeps() {
+  public ImmutableSet<IntermediateDexRule> getPreDexDeps() {
     return preDexDeps;
   }
 
@@ -772,10 +768,12 @@
     } else {
       Iterable<Path> filesToDex = FluentIterable.from(preDexDeps)
           .transform(
-              new Function<DexProducedFromJavaLibraryThatContainsClassFiles, Path>() {
+              new Function<IntermediateDexRule, Path>() {
                   @Override
                   @Nullable
-                  public Path apply(DexProducedFromJavaLibraryThatContainsClassFiles preDex) {
+                  public Path apply(IntermediateDexRule preDexDep) {
+                    DexProducedFromJavaLibraryThatContainsClassFiles preDex = preDexDep
+                        .getBuildable();
                     if (preDex.hasOutput()) {
                       return preDex.getPathToDex();
                     } else {
@@ -1239,7 +1237,8 @@
 
     private BuildTarget keystoreTarget;
     private PackageType packageType = DEFAULT_PACKAGE_TYPE;
-    private Set<BuildTarget> buildRulesToExcludeFromDex = Sets.newHashSet();
+    private ImmutableSet.Builder<BuildTarget> buildRulesToExcludeFromDexBuilder =
+        ImmutableSet.builder();
     private boolean disablePreDex = false;
     private DexSplitMode dexSplitMode = new DexSplitMode(
         /* shouldSplitDex */ false,
@@ -1278,28 +1277,22 @@
 
       BuildRuleParams originalParams = createBuildRuleParams(ruleResolver);
       ImmutableSortedSet<BuildRule> originalDeps = originalParams.getDeps();
-      ImmutableSet<BuildRule> preDexDepsAsBuildRules;
-      ImmutableSet<DexProducedFromJavaLibraryThatContainsClassFiles> preDexDeps;
+      ImmutableSet<IntermediateDexRule> preDexDeps;
+      ImmutableSet<BuildTarget> buildRulesToExcludeFromDex =
+          buildRulesToExcludeFromDexBuilder.build();
       if (!disablePreDex
           && PackageType.DEBUG.equals(packageType)
           && !dexSplitMode.isShouldSplitDex() // TODO(mbolin): Support predex for split dex.
           && !preprocessJavaClassesBash.isPresent() // TODO(mbolin): Support predex post-preprocess.
           ) {
-        preDexDepsAsBuildRules = enhanceGraphToLeveragePreDexing(originalDeps,
+        AndroidBinaryGraphEnhancer graphEnhancer = new AndroidBinaryGraphEnhancer(
+            originalDeps,
             buildRulesToExcludeFromDex,
-            ruleResolver,
             originalParams.getPathRelativizer(),
             originalParams.getRuleKeyBuilderFactory());
-        ImmutableSet.Builder<DexProducedFromJavaLibraryThatContainsClassFiles> preDexDepsBuilder =
-            ImmutableSet.builder();
-        for (BuildRule preDexDepBuildRule : preDexDepsAsBuildRules) {
-          preDexDepsBuilder.add(
-              (DexProducedFromJavaLibraryThatContainsClassFiles) preDexDepBuildRule.getBuildable());
-        }
-        preDexDeps = preDexDepsBuilder.build();
+        preDexDeps = graphEnhancer.createDepsForPreDexing(ruleResolver);
       } else {
-        preDexDepsAsBuildRules = ImmutableSet.of();
-        preDexDeps = ImmutableSortedSet.of();
+        preDexDeps = ImmutableSet.of();
       }
 
       boolean allowNonExistentRule =
@@ -1309,7 +1302,7 @@
       // createBuildRuleParams(ruleResolver).
       ImmutableSortedSet<BuildRule> totalDeps = ImmutableSortedSet.<BuildRule>naturalOrder()
           .addAll(originalDeps)
-          .addAll(preDexDepsAsBuildRules)
+          .addAll(preDexDeps)
           .build();
       BuildRuleParams finalParams = new BuildRuleParams(getBuildTarget(),
           totalDeps,
@@ -1341,75 +1334,6 @@
           preprocessJavaClassesBash);
     }
 
-    /**
-     * @return The set of build rules that correspond to pre-dex'd artifacts that should be merged
-     *     to create the final classes.dex for the APK. For every element in the set, its
-     *     {@link BuildRule#getBuildable()} method will return an instance of
-     *     {@link DexProducedFromJavaLibraryThatContainsClassFiles}.
-     */
-    private ImmutableSet<BuildRule> enhanceGraphToLeveragePreDexing(
-            ImmutableSortedSet<BuildRule> originalDeps,
-            Set<BuildTarget> buildRulesToExcludeFromDex,
-            BuildRuleResolver ruleResolver,
-            Function<String, Path> pathRelativizer,
-            RuleKeyBuilderFactory ruleKeyBuilderFactory) {
-      ImmutableSet.Builder<BuildRule> preDexDeps = ImmutableSet.builder();
-      ImmutableSet<JavaLibraryRule> transitiveJavaDeps = Classpaths
-          .getClasspathEntries(originalDeps).keySet();
-      for (JavaLibraryRule javaLibraryRule : transitiveJavaDeps) {
-        // If the rule has no output file (which happens when a java_library has no srcs or
-        // resources, but export_deps is true), then there will not be anything to dx.
-        if (javaLibraryRule.getPathToOutputFile() == null) {
-          continue;
-        }
-
-        // If the rule is in the no_dx list, then do not pre-dex it.
-        if (buildRulesToExcludeFromDex.contains(javaLibraryRule.getBuildTarget())) {
-          continue;
-        }
-
-        // See whether the corresponding PreDex has already been added to the ruleResolver.
-        BuildTarget originalTarget = javaLibraryRule.getBuildTarget();
-        BuildTarget preDexTarget = new BuildTarget(originalTarget.getBaseName(),
-            originalTarget.getShortName(),
-            "dex");
-        BuildRule preDexRule = ruleResolver.get(preDexTarget);
-        if (preDexRule != null) {
-          preDexDeps.add(preDexRule);
-          continue;
-        }
-
-        // Create a rule to get the list of the classes in the JavaLibraryRule.
-        AccumulateClassNames.Builder accumulateClassNamesBuilder = AccumulateClassNames
-            .newAccumulateClassNamesBuilder(new DefaultBuildRuleBuilderParams(
-                pathRelativizer, ruleKeyBuilderFactory));
-        BuildTarget accumulateClassNamesBuildTarget = new BuildTarget(
-            originalTarget.getBaseName(), originalTarget.getShortName(), "class_names");
-        accumulateClassNamesBuilder.setBuildTarget(accumulateClassNamesBuildTarget);
-        accumulateClassNamesBuilder.setJavaLibraryToDex(javaLibraryRule);
-        accumulateClassNamesBuilder.addDep(originalTarget);
-        accumulateClassNamesBuilder.addVisibilityPattern(BuildTargetPattern.MATCH_ALL);
-        BuildRule accumulateClassNamesRule = ruleResolver.buildAndAddToIndex(
-            accumulateClassNamesBuilder);
-        AccumulateClassNames accumulateClassNames =
-            (AccumulateClassNames) accumulateClassNamesRule.getBuildable();
-
-        // Create the PreDex and add it to both the ruleResolver and preDexDeps.
-        IntermediateDexRule.Builder preDexBuilder =
-            IntermediateDexRule.newPreDexBuilder(
-                new DefaultBuildRuleBuilderParams(
-                    pathRelativizer,
-                    ruleKeyBuilderFactory));
-        preDexBuilder.setBuildTarget(preDexTarget);
-        preDexBuilder.setAccumulateClassNamesDep(accumulateClassNames);
-        preDexBuilder.addDep(accumulateClassNamesBuildTarget);
-        preDexBuilder.addVisibilityPattern(BuildTargetPattern.MATCH_ALL);
-        BuildRule preDex = ruleResolver.buildAndAddToIndex(preDexBuilder);
-        preDexDeps.add(preDex);
-      }
-      return preDexDeps.build();
-    }
-
     @Override
     public Builder setBuildTarget(BuildTarget buildTarget) {
       super.setBuildTarget(buildTarget);
@@ -1460,7 +1384,7 @@
     }
 
     public Builder addBuildRuleToExcludeFromDex(BuildTarget entry) {
-      this.buildRulesToExcludeFromDex.add(entry);
+      this.buildRulesToExcludeFromDexBuilder.add(entry);
       return this;
     }
 
diff --git a/src/com/facebook/buck/android/BUCK b/src/com/facebook/buck/android/BUCK
index 7270ae2..a807bee 100644
--- a/src/com/facebook/buck/android/BUCK
+++ b/src/com/facebook/buck/android/BUCK
@@ -41,6 +41,7 @@
 
 RULES_SRCS = [
   'AndroidBinaryBuildRuleFactory.java',
+  'AndroidBinaryGraphEnhancer.java',
   'AndroidBinaryRule.java',
   'AndroidDexTransitiveDependencies.java',
   'AndroidInstrumentationApk.java',
diff --git a/src/com/facebook/buck/android/IntermediateDexRule.java b/src/com/facebook/buck/android/IntermediateDexRule.java
index 8d5b301..cdd2bc9 100644
--- a/src/com/facebook/buck/android/IntermediateDexRule.java
+++ b/src/com/facebook/buck/android/IntermediateDexRule.java
@@ -17,6 +17,8 @@
 package com.facebook.buck.android;
 
 import com.facebook.buck.java.AccumulateClassNames;
+import com.facebook.buck.model.BuildTarget;
+import com.facebook.buck.model.BuildTargetPattern;
 import com.facebook.buck.rules.AbiRule;
 import com.facebook.buck.rules.AbstractBuildRuleBuilder;
 import com.facebook.buck.rules.AbstractBuildRuleBuilderParams;
@@ -24,7 +26,6 @@
 import com.facebook.buck.rules.BuildRuleParams;
 import com.facebook.buck.rules.BuildRuleResolver;
 import com.facebook.buck.rules.BuildRuleType;
-import com.facebook.buck.rules.Buildable;
 import com.facebook.buck.rules.Sha1HashCode;
 import com.google.common.base.Preconditions;
 
@@ -39,7 +40,7 @@
   }
 
   @Override
-  public Buildable getBuildable() {
+  public DexProducedFromJavaLibraryThatContainsClassFiles getBuildable() {
     return buildable;
   }
 
@@ -82,5 +83,23 @@
       this.javaLibraryWithClassesList = javaLibraryWithClassesList;
       return this;
     }
+
+    @Override
+    public Builder setBuildTarget(BuildTarget buildTarget) {
+      super.setBuildTarget(buildTarget);
+      return this;
+    }
+
+    @Override
+    public Builder addDep(BuildTarget buildTarget) {
+      super.addDep(buildTarget);
+      return this;
+    }
+
+    @Override
+    public Builder addVisibilityPattern(BuildTargetPattern visibilityPattern) {
+      super.addVisibilityPattern(visibilityPattern);
+      return this;
+    }
   }
 }
diff --git a/src/com/facebook/buck/java/AccumulateClassNames.java b/src/com/facebook/buck/java/AccumulateClassNames.java
index a0069cc..0f9d6ff 100644
--- a/src/com/facebook/buck/java/AccumulateClassNames.java
+++ b/src/com/facebook/buck/java/AccumulateClassNames.java
@@ -17,6 +17,7 @@
 package com.facebook.buck.java;
 
 import com.facebook.buck.model.BuildTarget;
+import com.facebook.buck.model.BuildTargetPattern;
 import com.facebook.buck.rules.AbiRule;
 import com.facebook.buck.rules.AbstractBuildRuleBuilderParams;
 import com.facebook.buck.rules.AbstractBuildable;
@@ -214,5 +215,22 @@
       return this;
     }
 
+    @Override
+    public Builder setBuildTarget(BuildTarget buildTarget) {
+      super.setBuildTarget(buildTarget);
+      return this;
+    }
+
+    @Override
+    public Builder addDep(BuildTarget buildTarget) {
+      super.addDep(buildTarget);
+      return this;
+    }
+
+    @Override
+    public Builder addVisibilityPattern(BuildTargetPattern visibilityPattern) {
+      super.addVisibilityPattern(visibilityPattern);
+      return this;
+    }
   }
 }
diff --git a/test/com/facebook/buck/android/AndroidBinaryGraphEnhancerTest.java b/test/com/facebook/buck/android/AndroidBinaryGraphEnhancerTest.java
new file mode 100644
index 0000000..dcea3ff
--- /dev/null
+++ b/test/com/facebook/buck/android/AndroidBinaryGraphEnhancerTest.java
@@ -0,0 +1,102 @@
+/*
+ * Copyright 2013-present Facebook, Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License"); you may
+ * not use this file except in compliance with the License. You may obtain
+ * a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+ * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+ * License for the specific language governing permissions and limitations
+ * under the License.
+ */
+
+package com.facebook.buck.android;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertNotNull;
+
+import com.facebook.buck.java.DefaultJavaLibraryRule;
+import com.facebook.buck.model.BuildTarget;
+import com.facebook.buck.rules.BuildRule;
+import com.facebook.buck.rules.BuildRuleResolver;
+import com.facebook.buck.rules.DefaultBuildRuleBuilderParams;
+import com.facebook.buck.rules.FakeRuleKeyBuilderFactory;
+import com.facebook.buck.rules.RuleKeyBuilderFactory;
+import com.google.common.base.Function;
+import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.ImmutableSortedSet;
+
+import org.junit.Test;
+
+import java.nio.file.Path;
+import java.nio.file.Paths;
+import java.util.Iterator;
+
+public class AndroidBinaryGraphEnhancerTest {
+
+  @Test
+  public void testCreateDepsForPreDexing() {
+    BuildRuleResolver ruleResolver = new BuildRuleResolver();
+    Function<String, Path> pathRelativizer = new Function<String, Path>() {
+      @Override
+      public Path apply(String input) {
+        return Paths.get(input);
+      }
+    };
+    RuleKeyBuilderFactory ruleKeyBuilderFactory = new FakeRuleKeyBuilderFactory();
+
+    // Create three Java rules, :dep1, :dep2, and :lib. :lib depends on :dep1 and :dep2.
+    BuildTarget javaDep1BuildTarget = new BuildTarget("//java/com/example", "dep1");
+    ruleResolver.buildAndAddToIndex(
+        DefaultJavaLibraryRule.newJavaLibraryRuleBuilder(
+            new DefaultBuildRuleBuilderParams(pathRelativizer, ruleKeyBuilderFactory))
+            .setBuildTarget(javaDep1BuildTarget)
+            .addSrc("java/com/example/Dep1.java"));
+
+    BuildTarget javaDep2BuildTarget = new BuildTarget("//java/com/example", "dep2");
+    ruleResolver.buildAndAddToIndex(
+        DefaultJavaLibraryRule.newJavaLibraryRuleBuilder(
+            new DefaultBuildRuleBuilderParams(pathRelativizer, ruleKeyBuilderFactory))
+            .setBuildTarget(javaDep2BuildTarget)
+            .addSrc("java/com/example/Dep2.java"));
+
+    BuildTarget javaLibBuildTarget = new BuildTarget("//java/com/example", "lib");
+    DefaultJavaLibraryRule javaLib = ruleResolver.buildAndAddToIndex(
+        DefaultJavaLibraryRule.newJavaLibraryRuleBuilder(
+            new DefaultBuildRuleBuilderParams(pathRelativizer, ruleKeyBuilderFactory))
+            .setBuildTarget(javaLibBuildTarget)
+            .addSrc("java/com/example/Lib.java")
+            .addDep(javaDep1BuildTarget)
+            .addDep(javaDep2BuildTarget));
+
+    // Assume we are enhancing an android_binary rule whose only dep
+    // is //java/com/example:lib, and that //java/com/example:dep2 is in its no_dx list.
+    ImmutableSortedSet<BuildRule> originalDeps = ImmutableSortedSet.<BuildRule>of(javaLib);
+    ImmutableSet<BuildTarget> buildRulesToExcludeFromDex = ImmutableSet.of(javaDep2BuildTarget);
+    AndroidBinaryGraphEnhancer graphEnhancer = new AndroidBinaryGraphEnhancer(
+        originalDeps,
+        buildRulesToExcludeFromDex,
+        pathRelativizer,
+        ruleKeyBuilderFactory);
+    ImmutableSet<IntermediateDexRule> depsForPreDexing = graphEnhancer.createDepsForPreDexing(
+        ruleResolver);
+    assertEquals(
+        "There should be a #dex rule for dep1 and lib, but not dep2 because it is in the no_dx " +
+            "list.",
+        2,
+    		depsForPreDexing.size());
+
+    Iterator<IntermediateDexRule> depsForPreDexingIter = depsForPreDexing.iterator();
+    BuildRule preDexRule1 = depsForPreDexingIter.next();
+    assertEquals("//java/com/example:dep1#dex", preDexRule1.getBuildTarget().toString());
+    assertNotNull(ruleResolver.get(preDexRule1.getBuildTarget()));
+
+    BuildRule preDexRule2 = depsForPreDexingIter.next();
+    assertEquals("//java/com/example:lib#dex", preDexRule2.getBuildTarget().toString());
+    assertNotNull(ruleResolver.get(preDexRule2.getBuildTarget()));
+  }
+}