Index: lib/Transforms/Scalar/ConstantProp.cpp
===================================================================
--- lib/Transforms/Scalar/ConstantProp.cpp
+++ lib/Transforms/Scalar/ConstantProp.cpp
@@ -18,21 +18,25 @@
 //
 //===----------------------------------------------------------------------===//
 
+#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/ConstantFolding.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
-#include "llvm/Transforms/Utils/Local.h"
 #include "llvm/IR/Constant.h"
 #include "llvm/IR/InstIterator.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/Pass.h"
+#include "llvm/Support/DebugCounter.h"
 #include "llvm/Transforms/Scalar.h"
-#include <set>
+#include "llvm/Transforms/Utils/Local.h"
 using namespace llvm;
 
 #define DEBUG_TYPE "constprop"
 
 STATISTIC(NumInstKilled, "Number of instructions killed");
+DEBUG_COUNTER(CPCounter, "constprop-transform",
+              "Controls which instructions are killed");
 
 namespace {
   struct ConstantPropagation : public FunctionPass {
@@ -66,25 +70,38 @@
     return false;
 
   // Initialize the worklist to all of the instructions ready to process...
-  std::set<Instruction*> WorkList;
-  for (Instruction &I: instructions(&F))
+  SmallPtrSet<Instruction *, 16> WorkList;
+  // The SmallVector of WorkList ensures that we do iteration at stable order.
+  // We use two containers rather than one SetVector, since remove is
+  // linear-time, and we don't care enough to remove from Vec.
+  SmallVector<Instruction *, 16> WorkListVec;
+  for (Instruction &I : instructions(&F)) {
     WorkList.insert(&I);
+    WorkListVec.push_back(&I);
+  }
 
   bool Changed = false;
   const DataLayout &DL = F.getParent()->getDataLayout();
   TargetLibraryInfo *TLI =
       &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
 
-  while (!WorkList.empty()) {
-    Instruction *I = *WorkList.begin();
-    WorkList.erase(WorkList.begin());    // Get an element from the worklist...
+  for (auto Begin = WorkListVec.begin(), End = WorkListVec.end(); Begin != End;
+       ++Begin) {
+    Instruction *I = *Begin;
+    WorkList.erase(I); // Remove element from the worklist...
 
-    if (!I->use_empty())                 // Don't muck with dead instructions...
+    if (!I->use_empty()) // Don't muck with dead instructions...
       if (Constant *C = ConstantFoldInstruction(I, DL, TLI)) {
+        if (!DebugCounter::shouldExecute(CPCounter))
+          continue;
+
         // Add all of the users of this instruction to the worklist, they might
         // be constant propagatable now...
-        for (User *U : I->users())
-          WorkList.insert(cast<Instruction>(U));
+        for (User *U : I->users()) {
+          // If user not in the set, then add it to the vector.
+          if (WorkList.insert(cast<Instruction>(U)).second)
+            WorkListVec.push_back(cast<Instruction>(U));
+        }
 
         // Replace all of the uses of a variable with uses of the constant.
         I->replaceAllUsesWith(C);
Index: test/Other/debugcounter-constprop.ll
===================================================================
--- /dev/null
+++ test/Other/debugcounter-constprop.ll
@@ -0,0 +1,20 @@
+; REQUIRES: asserts
+; RUN: opt < %s -constprop -S -debug-counter=constprop-transform-skip=1,constprop-transform-count=1 | FileCheck %s
+;; Test that, with debug counters on, we will skip the first constprop optimization opportunity, perform next 1,
+;; and ignore all the others left.
+
+; CHECK-LABEL: @test(
+; CHECK-NEXT:  %add1 = add i32 1, 2
+; CHECK-NEXT:  %add2 = add i32 %add1, 2
+; CHECK-NEXT:  %add4 = add i32 4, 2
+; CHECK-NEXT:  %add5 = add i32 3, 2
+; CHECK-NEXT:  %add6 = add i32 %add5, 2
+define void @test() {
+    %add1 = add i32 1, 2
+    %add2 = add i32 %add1, 2
+    %add3 = add i32 2, 2
+    %add4 = add i32 %add3, 2
+    %add5 = add i32 3, 2
+    %add6 = add i32 %add5, 2
+    ret void
+}
\ No newline at end of file