[unroll] Rather than an operand set, use a setvector for the worklist.

We don't just want to handle duplicate operands within an instruction,
but also duplicates across operands of different instructions. I should
have gone straight to this, but I had convinced myself that it wasn't
going to be necessary briefly. I've come to my senses after chatting
more with Nick, and am now happier here.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@229054 91177308-0d34-0410-b5e6-96231b3b80d8

diff --git a/lib/Transforms/Scalar/LoopUnrollPass.cpp b/lib/Transforms/Scalar/LoopUnrollPass.cpp
index 63d3cc6f628353af4318e7058880e921c09893e7..d1daaa684ad1954d5a08652e77246c72d2c27651 100644 (file)
--- a/lib/Transforms/Scalar/LoopUnrollPass.cpp
+++ b/lib/Transforms/Scalar/LoopUnrollPass.cpp
@@ -13,6 +13,7 @@
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Scalar.h"
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Scalar.h"

+#include "llvm/ADT/SetVector.h"

 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/CodeMetrics.h"
 #include "llvm/Analysis/LoopPass.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/CodeMetrics.h"
 #include "llvm/Analysis/LoopPass.h"


@@ -500,22 +501,25 @@ public:
   // instructions that would become dead if we do perform the simplification.
   unsigned estimateNumberOfDeadInstructions() {
     NumberOfOptimizedInstructions = 0;
   // instructions that would become dead if we do perform the simplification.
   unsigned estimateNumberOfDeadInstructions() {
     NumberOfOptimizedInstructions = 0;

-    SmallVector<Instruction *, 8> Worklist;
-    SmallPtrSet<Instruction *, 16> DeadInstructions;

 
 

-    // We keep a very small set of operands that we use to de-duplicate things
-    // when inserting into the worklist. This lets us handle duplicates within
-    // a single instruction's operands without buring lots of memory on the
-    // worklist.
-    SmallPtrSet<Instruction *, 4> OperandSet;
+    // We keep a set vector for the worklist so that we don't wast space in the
+    // worklist queuing up the same instruction repeatedly. This can happen due
+    // to multiple operands being the same instruction or due to the same
+    // instruction being an operand of lots of things that end up dead or
+    // simplified.
+    SmallSetVector<Instruction *, 8> Worklist;
+
+    // The dead instructions are held in a separate set. This is used to
+    // prevent us from re-examining instructions and make sure we only count
+    // the benifit once. The worklist's internal set handles insertion
+    // deduplication.
+    SmallPtrSet<Instruction *, 16> DeadInstructions;

 
     // Lambda to enque operands onto the worklist.
     auto EnqueueOperands = [&](Instruction &I) {
 
     // Lambda to enque operands onto the worklist.
     auto EnqueueOperands = [&](Instruction &I) {

-      OperandSet.clear();

       for (auto *Op : I.operand_values())
         if (auto *OpI = dyn_cast<Instruction>(Op))
       for (auto *Op : I.operand_values())
         if (auto *OpI = dyn_cast<Instruction>(Op))

-          if (OperandSet.insert(OpI).second)
-            Worklist.push_back(OpI);
+          Worklist.insert(OpI);

     };
 
     // Start by initializing worklist with simplified instructions.
     };
 
     // Start by initializing worklist with simplified instructions.