Index: test/BugPoint/func-attrs-none.ll
===================================================================
--- /dev/null
+++ test/BugPoint/func-attrs-none.ll
@@ -0,0 +1,12 @@
+; Test that reducing function attributes on functions with no attributes works.
+; RUN: bugpoint -load %llvmshlibdir/BugpointPasses%shlibext %s -output-prefix %t -bugpoint-crashcalls -silence-passes
+; REQUIRES: loadable_module
+
+define dso_local i32 @bar() {
+  ret i32 42
+}
+
+define dso_local i32 @foo() {
+  %1 = call i32 @bar()
+  ret i32 %1
+}
Index: test/BugPoint/func-attrs-zero.ll
===================================================================
--- /dev/null
+++ test/BugPoint/func-attrs-zero.ll
@@ -0,0 +1,21 @@
+; RUN: bugpoint -load %llvmshlibdir/BugpointPasses%shlibext %s -output-prefix %t -bugpoint-crashcalls -silence-passes
+; RUN: llvm-dis %t-reduced-simplified.bc -o - | FileCheck %s
+; REQUIRES: loadable_module
+
+; Check that all function attributes on bar have been eliminated,
+; since they have nothing to do with the crash.
+; CHECK: bar(){{[^#0-9]*$}}
+define dso_local i32 @bar() #0 {
+  ret i32 42
+}
+
+; Same goes for foo: all attributes should be removed.
+; CHECK: foo(){{[^#0-9]*$}}
+define dso_local i32 @foo() #1 {
+  %1 = call i32 @bar()
+  ret i32 %1
+}
+
+; CHECK-NOT: attributes #
+attributes #0 = { uwtable nounwind "no-frame-pointer-elim-non-leaf" "disable-tail-calls"="false" }
+attributes #1 = { optnone noinline "my-custom-attribute" "no-infs-fp-math"="false" }
Index: tools/bugpoint/CrashDebugger.cpp
===================================================================
--- tools/bugpoint/CrashDebugger.cpp
+++ tools/bugpoint/CrashDebugger.cpp
@@ -327,13 +327,13 @@
 public:
   ReduceCrashingFunctionAttributes(BugDriver &bd, const std::string &FnName,
                                    BugTester testFn)
-      : BD(bd), FnName(FnName), TestFn(testFn) {}
+      : ListReducer(Zero), BD(bd), FnName(FnName), TestFn(testFn) {}
 
   Expected<TestResult> doTest(std::vector<Attribute> &Prefix,
                               std::vector<Attribute> &Kept) override {
-    if (!Kept.empty() && TestFuncAttrs(Kept))
+    if (TestFuncAttrs(Kept))
       return KeepSuffix;
-    if (!Prefix.empty() && TestFuncAttrs(Prefix))
+    if (TestFuncAttrs(Prefix))
       return KeepPrefix;
     return NoFailure;
   }
Index: tools/bugpoint/ListReducer.h
===================================================================
--- tools/bugpoint/ListReducer.h
+++ tools/bugpoint/ListReducer.h
@@ -33,6 +33,14 @@
     KeepPrefix  // The prefix alone satisfies the predicate
   };
 
+  enum ReductionLimit {
+    Zero, // Keep reducing list elements until none are left.
+    One   // Keep reducing list elements until only one is left.
+  };
+  ReductionLimit ReduceLimit;
+
+  ListReducer(ReductionLimit Limit = One) : ReduceLimit(Limit) {}
+
   virtual ~ListReducer() {}
 
   /// This virtual function should be overriden by subclasses to implement the
@@ -48,20 +56,37 @@
   Expected<bool> reduceList(std::vector<ElTy> &TheList) {
     std::vector<ElTy> empty;
     std::mt19937 randomness(0x6e5ea738);  // Seed the random number generator
+    unsigned Limit;
+    switch (ReduceLimit) {
+    case One:
+      Limit = 1;
+      break;
+    case Zero:
+      Limit = 0;
+      break;
+    }
+
     Expected<TestResult> Result = doTest(TheList, empty);
     if (Error E = Result.takeError())
       return std::move(E);
     switch (*Result) {
     case KeepPrefix:
-      if (TheList.size() == 1) // we are done, it's the base case and it fails
+      if (TheList.size() == Limit) // we are done, it's the base case and it fails
         return true;
       else
         break; // there's definitely an error, but we need to narrow it down
 
     case KeepSuffix:
-      // cannot be reached!
-      llvm_unreachable("bugpoint ListReducer internal error: "
-                       "selected empty set.");
+      if (Limit > 0)
+        llvm_unreachable("bugpoint ListReducer internal error: "
+                         "selected empty set.");
+      else {
+        // If we are reducing to zero, then we're happy to select the empty set,
+        // because that means we're done reducing!
+        TheList.swap(empty);
+        return true;
+      }
+
 
     case NoFailure:
       return false; // there is no failure with the full set of passes/funcs!
@@ -81,17 +106,21 @@
     unsigned MidTop = TheList.size();
     unsigned MaxIterations = MaxIterationsWithoutProgress;
     unsigned NumOfIterationsWithoutProgress = 0;
-    while (MidTop > 1) { // Binary split reduction loop
+    while (MidTop > Limit) { // Binary split reduction loop
       // Halt if the user presses ctrl-c.
       if (BugpointIsInterrupted) {
         errs() << "\n\n*** Reduction Interrupted, cleaning up...\n\n";
         return true;
       }
 
+      if (NumOfIterationsWithoutProgress > MaxIterations)
+        break;
+
       // If the loop doesn't make satisfying progress, try shuffling.
       // The purpose of shuffling is to avoid the heavy tails of the
       // distribution (improving the speed of convergence).
-      if (ShufflingEnabled && NumOfIterationsWithoutProgress > MaxIterations) {
+      if (ShufflingEnabled && TheList.size() > 1 &&
+          NumOfIterationsWithoutProgress > MaxIterations) {
         std::vector<ElTy> ShuffledList(TheList);
         std::shuffle(ShuffledList.begin(), ShuffledList.end(), randomness);
         errs() << "\n\n*** Testing shuffled set...\n\n";
@@ -126,13 +155,17 @@
         return std::move(E);
       switch (*Result) {
       case KeepSuffix:
-        // The property still holds.  We can just drop the prefix elements, and
-        // shorten the list to the "kept" elements.
-        TheList.swap(Suffix);
+        // The property still holds.  We can drop the prefix elements, and
+        // choose the "kept" elements instead. If the number of kept elements
+        // is smaller than our previous number of elements, we've made progress
+        // in reducing the list.
         MidTop = TheList.size();
-        // Reset progress treshold and progress counter
-        MaxIterations = MaxIterationsWithoutProgress;
-        NumOfIterationsWithoutProgress = 0;
+        if (Suffix.size() < TheList.size()) {
+          TheList.swap(Suffix);
+          MaxIterations = MaxIterationsWithoutProgress;
+          NumOfIterationsWithoutProgress = 0;
+        } else
+          NumOfIterationsWithoutProgress++;
         break;
       case KeepPrefix:
         // The predicate still holds, shorten the list to the prefix elements.