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,37 @@
     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 (unsigned i = 0; i < WorkListVec.size(); i++) {
+    Instruction *I = WorkListVec[i];
+    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);