[TypePromotion] Use SetVectors instead of PtrSets

Remove the chance of non-deterministic insertion of zexts of the
sources by using a SetVector instead of SmallPtrSet. Do the same for
sinks for consistency and to negate the small issue from possibly
happening. The SafeWrap instructions are now also stored in a
SmallVector. The IRPromoter members of these structures have been
changed to references.

Differential Revision: https://reviews.llvm.org/D72322

1 files changed, 30 insertions, 40 deletions

diff --git a/llvm/lib/CodeGen/TypePromotion.cpp b/llvm/lib/CodeGen/TypePromotion.cpp
index c547a23f93f..4522484222f 100644
--- a/llvm/lib/CodeGen/TypePromotion.cpp
+++ b/llvm/lib/CodeGen/TypePromotion.cpp
@@ -107,16 +107,15 @@ class IRPromoter {
   LLVMContext &Ctx;
   IntegerType *OrigTy = nullptr;
   unsigned PromotedWidth = 0;
+  SetVector<Value*> &Visited;
+  SetVector<Value*> &Sources;
+  SetVector<Instruction*> &Sinks;
+  SmallVectorImpl<Instruction*> &SafeWrap;
   IntegerType *ExtTy = nullptr;
   SmallPtrSet<Value*, 8> NewInsts;
   SmallPtrSet<Instruction*, 4> InstsToRemove;
   DenseMap<Value*, SmallVector<Type*, 4>> TruncTysMap;
   SmallPtrSet<Value*, 8> Promoted;
-  SetVector<Value*> *Visited;
-  SmallPtrSetImpl<Value*> *Sources;
-  SmallPtrSetImpl<Instruction*> *Sinks;
-  SmallPtrSetImpl<Instruction*> *SafeToPromote;
-  SmallPtrSetImpl<Instruction*> *SafeWrap;
 
   void ReplaceAllUsersOfWith(Value *From, Value *To);
   void PrepareWrappingAdds(void);
@@ -127,18 +126,18 @@ class IRPromoter {
   void Cleanup(void);
 
 public:
-  IRPromoter(LLVMContext &C, IntegerType *Ty, unsigned Width) :
-    Ctx(C), OrigTy(Ty), PromotedWidth(Width) {
+  IRPromoter(LLVMContext &C, IntegerType *Ty, unsigned Width,
+             SetVector<Value*> &visited, SetVector<Value*> &sources,
+             SetVector<Instruction*> &sinks,
+             SmallVectorImpl<Instruction*> &wrap) :
+    Ctx(C), OrigTy(Ty), PromotedWidth(Width), Visited(visited),
+    Sources(sources), Sinks(sinks), SafeWrap(wrap) {
     ExtTy = IntegerType::get(Ctx, PromotedWidth);
     assert(OrigTy->getPrimitiveSizeInBits() < ExtTy->getPrimitiveSizeInBits()
            && "Original type not smaller than extended type");
   }
 
-  void Mutate(SetVector<Value*> &Visited,
-              SmallPtrSetImpl<Value*> &Sources,
-              SmallPtrSetImpl<Instruction*> &Sinks,
-              SmallPtrSetImpl<Instruction*> &SafeToPromote,
-              SmallPtrSetImpl<Instruction*> &SafeWrap);
+  void Mutate();
 };
 
 class TypePromotion : public FunctionPass {
@@ -147,7 +146,7 @@ class TypePromotion : public FunctionPass {
   unsigned RegisterBitWidth = 0;
   SmallPtrSet<Value*, 16> AllVisited;
   SmallPtrSet<Instruction*, 8> SafeToPromote;
-  SmallPtrSet<Instruction*, 4> SafeWrap;
+  SmallVector<Instruction*, 4> SafeWrap;
 
   // Does V have the same size result type as TypeSize.
   bool EqualTypeSize(Value *V);
@@ -382,7 +381,7 @@ bool TypePromotion::isSafeWrap(Instruction *I) {
 
   LLVM_DEBUG(dbgs() << "IR Promotion: Allowing safe overflow for "
              << *I << "\n");
-  SafeWrap.insert(I);
+  SafeWrap.push_back(I);
   return true;
 }
 
@@ -451,7 +450,7 @@ void IRPromoter::PrepareWrappingAdds() {
   // create an equivalent instruction using a positive immediate.
   // That positive immediate can then be zext along with all the other
   // immediates later.
-  for (auto *I : *SafeWrap) {
+  for (auto *I : SafeWrap) {
     if (I->getOpcode() != Instruction::Add)
       continue;
 
@@ -473,7 +472,7 @@ void IRPromoter::PrepareWrappingAdds() {
     LLVM_DEBUG(dbgs() << "IR Promotion: New equivalent: " << *NewVal << "\n");
   }
   for (auto *I : NewInsts)
-    Visited->insert(I);
+    Visited.insert(I);
 }
 
 void IRPromoter::ExtendSources() {
@@ -500,7 +499,7 @@ void IRPromoter::ExtendSources() {
 
   // Now, insert extending instructions between the sources and their users.
   LLVM_DEBUG(dbgs() << "IR Promotion: Promoting sources:\n");
-  for (auto V : *Sources) {
+  for (auto V : Sources) {
     LLVM_DEBUG(dbgs() << " - " << *V << "\n");
     if (auto *I = dyn_cast<Instruction>(V))
       InsertZExt(I, I);
@@ -521,12 +520,12 @@ void IRPromoter::PromoteTree() {
 
   // Mutate the types of the instructions within the tree. Here we handle
   // constant operands.
-  for (auto *V : *Visited) {
-    if (Sources->count(V))
+  for (auto *V : Visited) {
+    if (Sources.count(V))
       continue;
 
     auto *I = cast<Instruction>(V);
-    if (Sinks->count(I))
+    if (Sinks.count(I))
       continue;
 
     for (unsigned i = 0, e = I->getNumOperands(); i < e; ++i) {
@@ -558,7 +557,7 @@ void IRPromoter::TruncateSinks() {
     if (!isa<Instruction>(V) || !isa<IntegerType>(V->getType()))
       return nullptr;
 
-    if ((!Promoted.count(V) && !NewInsts.count(V)) || Sources->count(V))
+    if ((!Promoted.count(V) && !NewInsts.count(V)) || Sources.count(V))
       return nullptr;
 
     LLVM_DEBUG(dbgs() << "IR Promotion: Creating " << *TruncTy << " Trunc for "
@@ -572,7 +571,7 @@ void IRPromoter::TruncateSinks() {
 
   // Fix up any stores or returns that use the results of the promoted
   // chain.
-  for (auto I : *Sinks) {
+  for (auto I : Sinks) {
     LLVM_DEBUG(dbgs() << "IR Promotion: For Sink: " << *I << "\n");
 
     // Handle calls separately as we need to iterate over arg operands.
@@ -613,7 +612,7 @@ void IRPromoter::Cleanup() {
   LLVM_DEBUG(dbgs() << "IR Promotion: Cleanup..\n");
   // Some zexts will now have become redundant, along with their trunc
   // operands, so remove them
-  for (auto V : *Visited) {
+  for (auto V : Visited) {
     if (!isa<ZExtInst>(V))
       continue;
 
@@ -652,8 +651,8 @@ void IRPromoter::ConvertTruncs() {
   LLVM_DEBUG(dbgs() << "IR Promotion: Converting truncs..\n");
   IRBuilder<> Builder{Ctx};
 
-  for (auto *V : *Visited) {
-    if (!isa<TruncInst>(V) || Sources->count(V))
+  for (auto *V : Visited) {
+    if (!isa<TruncInst>(V) || Sources.count(V))
       continue;
 
     auto *Trunc = cast<TruncInst>(V);
@@ -673,20 +672,10 @@ void IRPromoter::ConvertTruncs() {
   }
 }
 
-void IRPromoter::Mutate(SetVector<Value*> &Visited,
-                        SmallPtrSetImpl<Value*> &Sources,
-                        SmallPtrSetImpl<Instruction*> &Sinks,
-                        SmallPtrSetImpl<Instruction*> &SafeToPromote,
-                        SmallPtrSetImpl<Instruction*> &SafeWrap) {
+void IRPromoter::Mutate() {
   LLVM_DEBUG(dbgs() << "IR Promotion: Promoting use-def chains from "
              << OrigTy->getBitWidth() << " to " << PromotedWidth << "-bits\n");
 
-  this->Visited = &Visited;
-  this->Sources = &Sources;
-  this->Sinks = &Sinks;
-  this->SafeToPromote = &SafeToPromote;
-  this->SafeWrap = &SafeWrap;
-
   // Cache original types of the values that will likely need truncating
   for (auto *I : Sinks) {
     if (auto *Call = dyn_cast<CallInst>(I)) {
@@ -830,8 +819,8 @@ bool TypePromotion::TryToPromote(Value *V, unsigned PromotedWidth) {
              << TypeSize << " bits to " << PromotedWidth << "\n");
 
   SetVector<Value*> WorkList;
-  SmallPtrSet<Value*, 8> Sources;
-  SmallPtrSet<Instruction*, 4> Sinks;
+  SetVector<Value*> Sources;
+  SetVector<Instruction*> Sinks;
   SetVector<Value*> CurrentVisited;
   WorkList.insert(V);
 
@@ -936,8 +925,9 @@ bool TypePromotion::TryToPromote(Value *V, unsigned PromotedWidth) {
   if (ToPromote < 2)
     return false;
 
-  IRPromoter Promoter(*Ctx, cast<IntegerType>(OrigTy), PromotedWidth);
-  Promoter.Mutate(CurrentVisited, Sources, Sinks, SafeToPromote, SafeWrap);
+  IRPromoter Promoter(*Ctx, cast<IntegerType>(OrigTy), PromotedWidth,
+                      CurrentVisited, Sources, Sinks, SafeWrap);
+  Promoter.Mutate();
   return true;
 }