[DemandedBits] Use SetVector for Worklist

[nikic]

Summary

DemandedBits currently uses a simple vector for the worklist, which means that instructions may be inserted multiple times into it. Especially in combination with the deep lattice, this may cause instructions too be recomputed very often. To avoid this, switch to a SetVector.

Here's two debug traces for a very simple example before and after this change: https://gist.github.com/nikic/83ea77186f1b873725135299b31aff3c Notice that %x is recomputed 31 times before and once after.

[hfinkel]

LGTM

[nikic]

Aaand reverted :/ Assertion failure in clang CodeGen/builtins-systemz-zvector.c:

clang: /srv/llvm-buildbot-srcatch/llvm-build-dir/clang-x86_64-debian-fast/llvm.src/include/llvm/ADT/DenseMap.h:1167: llvm::SmallDenseMap::LargeRep llvm::SmallDenseMap<llvm::Instruction *, llvm::detail::DenseSetEmpty, 128, llvm::DenseMapInfo<llvm::Instruction *>, llvm::detail::DenseSetPair<llvm::Instruction *> >::allocateBuckets(unsigned int) [KeyT = llvm::Instruction *, ValueT = llvm::detail::DenseSetEmpty, InlineBuckets = 128, KeyInfoT = llvm::DenseMapInfo<llvm::Instruction *>, BucketT = llvm::detail::DenseSetPair<llvm::Instruction *>]: Assertion `Num > InlineBuckets && "Must allocate more buckets than are inline"' failed.

[nikic]

Use less inline elements in SmallSetVector.

[nikic]

I've submitted D56455 to fix the SmallDenseMap bug this triggered. Also reduced this to use 16 instead of 128 inline elements. That seems to be a more typical value and also sidesteps the issue :)

lib/Analysis/DemandedBits.cpp

 //
 // Only the lowest 16 bits of %1 are demanded; the rest are removed by the
 // trunc.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Analysis/DemandedBits.h"
 #include "llvm/ADT/APInt.h"
-#include "llvm/ADT/SmallPtrSet.h"
-#include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/Dominators.h"
if (Analyzed)
     // Analysis already completed for this function.
     return;
   Analyzed = true;
 
   Visited.clear();
   AliveBits.clear();
   DeadUses.clear();
 
-  SmallVector<Instruction*, 128> Worklist;
+  SmallSetVector<Instruction*, 128> Worklist;
 
   // Collect the set of "root" instructions that are known live.
   for (Instruction &I : instructions(F)) {
     if (!isAlwaysLive(&I))
       continue;
 
     LLVM_DEBUG(dbgs() << "DemandedBits: Root: " << I << "\n");
     // For integer-valued instructions, set up an initial empty set of alive
     // bits and add the instruction to the work list. For other instructions
     // add their operands to the work list (for integer values operands, mark
     // all bits as live).
     Type *T = I.getType();
     if (T->isIntOrIntVectorTy()) {
       if (AliveBits.try_emplace(&I, T->getScalarSizeInBits(), 0).second)
-        Worklist.push_back(&I);
+        Worklist.insert(&I);
 
       continue;
     }
 
     // Non-integer-typed instructions...
     for (Use &OI : I.operands()) {
       if (Instruction *J = dyn_cast<Instruction>(OI)) {
         Type *T = J->getType();
         if (T->isIntOrIntVectorTy())
           AliveBits[J] = APInt::getAllOnesValue(T->getScalarSizeInBits());
-        Worklist.push_back(J);
+        Worklist.insert(J);
       }
     }
     // To save memory, we don't add I to the Visited set here. Instead, we
     // check isAlwaysLive on every instruction when searching for dead
     // instructions later (we need to check isAlwaysLive for the
     // integer-typed instructions anyway).
   }
 
for (Use &OI : UserI->operands()) {
           APInt ABPrev(BitWidth, 0);
           auto ABI = AliveBits.find(I);
           if (ABI != AliveBits.end())
             ABPrev = ABI->second;
 
           APInt ABNew = AB | ABPrev;
           if (ABNew != ABPrev || ABI == AliveBits.end()) {
             AliveBits[I] = std::move(ABNew);
-            Worklist.push_back(I);
+            Worklist.insert(I);
           }
         }
       } else if (I && !Visited.count(I)) {
-        Worklist.push_back(I);
+        Worklist.insert(I);
       }
     }
   }
 }
 
 APInt DemandedBits::getDemandedBits(Instruction *I) {
   performAnalysis();