Index: include/llvm/Transforms/Utils/PredicateInfo.h
===================================================================
--- include/llvm/Transforms/Utils/PredicateInfo.h
+++ include/llvm/Transforms/Utils/PredicateInfo.h
@@ -53,6 +53,7 @@
 
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseSet.h"
+#include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/ilist.h"
@@ -227,10 +228,10 @@
 
 private:
   void buildPredicateInfo();
-  void processAssume(IntrinsicInst *, BasicBlock *, SmallPtrSetImpl<Value *> &);
-  void processBranch(BranchInst *, BasicBlock *, SmallPtrSetImpl<Value *> &);
-  void processSwitch(SwitchInst *, BasicBlock *, SmallPtrSetImpl<Value *> &);
-  void renameUses(SmallPtrSetImpl<Value *> &);
+  void processAssume(IntrinsicInst *, BasicBlock *, SmallSetVector<Value *, 8> &);
+  void processBranch(BranchInst *, BasicBlock *, SmallSetVector<Value *, 8> &);
+  void processSwitch(SwitchInst *, BasicBlock *, SmallSetVector<Value *, 8> &);
+  void renameUses(SmallSetVector<Value *, 8> &);
   using ValueDFS = PredicateInfoClasses::ValueDFS;
   typedef SmallVectorImpl<ValueDFS> ValueDFSStack;
   void convertUsesToDFSOrdered(Value *, SmallVectorImpl<ValueDFS> &);
@@ -238,7 +239,7 @@
   bool stackIsInScope(const ValueDFSStack &, const ValueDFS &) const;
   void popStackUntilDFSScope(ValueDFSStack &, const ValueDFS &);
   ValueInfo &getOrCreateValueInfo(Value *);
-  void addInfoFor(SmallPtrSetImpl<Value *> &OpsToRename, Value *Op,
+  void addInfoFor(SmallSetVector<Value *, 8> &OpsToRename, Value *Op,
                   PredicateBase *PB);
   const ValueInfo &getValueInfo(Value *) const;
   Function &F;
Index: lib/Transforms/Utils/PredicateInfo.cpp
===================================================================
--- lib/Transforms/Utils/PredicateInfo.cpp
+++ lib/Transforms/Utils/PredicateInfo.cpp
@@ -303,7 +303,7 @@
 }
 
 // Add Op, PB to the list of value infos for Op, and mark Op to be renamed.
-void PredicateInfo::addInfoFor(SmallPtrSetImpl<Value *> &OpsToRename, Value *Op,
+void PredicateInfo::addInfoFor(SmallSetVector<Value *, 8> &OpsToRename, Value *Op,
                                PredicateBase *PB) {
   OpsToRename.insert(Op);
   auto &OperandInfo = getOrCreateValueInfo(Op);
@@ -314,7 +314,7 @@
 // Process an assume instruction and place relevant operations we want to rename
 // into OpsToRename.
 void PredicateInfo::processAssume(IntrinsicInst *II, BasicBlock *AssumeBB,
-                                  SmallPtrSetImpl<Value *> &OpsToRename) {
+                                  SmallSetVector<Value *, 8> &OpsToRename) {
   // See if we have a comparison we support
   SmallVector<Value *, 8> CmpOperands;
   SmallVector<Value *, 2> ConditionsToProcess;
@@ -354,7 +354,7 @@
 // Process a block terminating branch, and place relevant operations to be
 // renamed into OpsToRename.
 void PredicateInfo::processBranch(BranchInst *BI, BasicBlock *BranchBB,
-                                  SmallPtrSetImpl<Value *> &OpsToRename) {
+                                  SmallSetVector<Value *, 8> &OpsToRename) {
   BasicBlock *FirstBB = BI->getSuccessor(0);
   BasicBlock *SecondBB = BI->getSuccessor(1);
   SmallVector<BasicBlock *, 2> SuccsToProcess;
@@ -424,7 +424,7 @@
 // Process a block terminating switch, and place relevant operations to be
 // renamed into OpsToRename.
 void PredicateInfo::processSwitch(SwitchInst *SI, BasicBlock *BranchBB,
-                                  SmallPtrSetImpl<Value *> &OpsToRename) {
+                                  SmallSetVector<Value *, 8> &OpsToRename) {
   Value *Op = SI->getCondition();
   if ((!isa<Instruction>(Op) && !isa<Argument>(Op)) || Op->hasOneUse())
     return;
@@ -454,7 +454,7 @@
   DT.updateDFSNumbers();
   // Collect operands to rename from all conditional branch terminators, as well
   // as assume statements.
-  SmallPtrSet<Value *, 8> OpsToRename;
+  SmallSetVector<Value *, 8> OpsToRename;
   for (auto DTN : depth_first(DT.getRootNode())) {
     BasicBlock *BranchBB = DTN->getBlock();
     if (auto *BI = dyn_cast<BranchInst>(BranchBB->getTerminator())) {
@@ -541,7 +541,7 @@
 //
 // TODO: Use this algorithm to perform fast single-variable renaming in
 // promotememtoreg and memoryssa.
-void PredicateInfo::renameUses(SmallPtrSetImpl<Value *> &OpsToRename) {
+void PredicateInfo::renameUses(SmallSetVector<Value *, 8> &OpsToRename) {
   ValueDFS_Compare Compare(OBBMap);
   // Compute liveness, and rename in O(uses) per Op.
   for (auto *Op : OpsToRename) {
Index: test/Transforms/Util/PredicateInfo/condprop.ll
===================================================================
--- test/Transforms/Util/PredicateInfo/condprop.ll
+++ test/Transforms/Util/PredicateInfo/condprop.ll
@@ -1,5 +1,6 @@
 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -print-predicateinfo -analyze  < %s 2>&1 | FileCheck %s
+; RUN: opt -print-predicateinfo -analyze -reverse-iterate  < %s 2>&1 | FileCheck %s
 
 @a = external global i32		; <i32*> [#uses=7]
 
Index: test/Transforms/Util/PredicateInfo/testandor.ll
===================================================================
--- test/Transforms/Util/PredicateInfo/testandor.ll
+++ test/Transforms/Util/PredicateInfo/testandor.ll
@@ -1,5 +1,6 @@
 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -print-predicateinfo < %s 2>&1 | FileCheck %s
+; RUN: opt -print-predicateinfo -reverse-iterate < %s 2>&1 | FileCheck %s
 
 declare void @foo(i1)
 declare void @bar(i32)