[NewGVN] Optimize processing as instructions don't get more trivially dead over time

[davide]

Summary

Don't call isTriviallyDeadInstructions() once we discover that an instruction is dead. Instead, set DFS number zero (as suggested by Danny) and forget about it (this also speeds up things as we won't try to reprocess that block).

[davide]

lib/Transforms/Scalar/NewGVN.cpp

241–243 ↗

(On Diff #85065)

This also adds a comment explaining what these array are for (in case it wasn't entirely obvious) and the special meaning of DFS number == 0

[davide]

This passes 3-stage bootstrap on Linux, FWIW

llvm/trunk/lib/Transforms/Scalar/NewGVN.cpp

DenseMap<const DomTreeNode *, std::pair<unsigned, unsigned>>
       DominatedInstRange;
 
 #ifndef NDEBUG
   // Debugging for how many times each block and instruction got processed.
   DenseMap<const Value *, unsigned> ProcessedCount;
 #endif
 
   // DFS info.
+  // This contains a mapping from Instructions to DFS numbers.
+  // The numbering starts at 1. An instruction with DFS number zero
+  // means that the instruction is dead.
   DenseMap<const Value *, unsigned> InstrDFS;
+
+  // This contains the mapping DFS numbers to instructions.
   SmallVector<Value *, 32> DFSToInstr;
 
   // Deletion info.
   SmallPtrSet<Instruction *, 8> InstructionsToErase;
 
 public:
   static char ID; // Pass identification, replacement for typeid.
   NewGVN() : FunctionPass(ID) {
void NewGVN::valueNumberMemoryPhi(MemoryPhi *MP) {
   if (setMemoryAccessEquivTo(MP, AllEqual ? AllSameValue : nullptr))
     markMemoryUsersTouched(MP);
 }
 
 // Value number a single instruction, symbolically evaluating, performing
 // congruence finding, and updating mappings.
 void NewGVN::valueNumberInstruction(Instruction *I) {
   DEBUG(dbgs() << "Processing instruction " << *I << "\n");
-  if (isInstructionTriviallyDead(I, TLI)) {
+
+  // There's no need to call isInstructionTriviallyDead more than once on
+  // an instruction. Therefore, once we know that an instruction is dead
+  // we change its DFS number so that it doesn't get numbered again.
+  if (InstrDFS[I] != 0 && isInstructionTriviallyDead(I, TLI)) {
+    InstrDFS[I] = 0;
     DEBUG(dbgs() << "Skipping unused instruction\n");
     markInstructionForDeletion(I);
     return;
   }
   if (!I->isTerminator()) {
     const auto *Symbolized = performSymbolicEvaluation(I, I->getParent());
     // If we couldn't come up with a symbolic expression, use the unknown
     // expression
bool NewGVN::runGVN(Function &F, DominatorTree *_DT, AssumptionCache *_AC,
   unsigned int Iterations = 0;
   // We start out in the entry block.
   BasicBlock *LastBlock = &F.getEntryBlock();
   while (TouchedInstructions.any()) {
     ++Iterations;
     // Walk through all the instructions in all the blocks in RPO.
     for (int InstrNum = TouchedInstructions.find_first(); InstrNum != -1;
          InstrNum = TouchedInstructions.find_next(InstrNum)) {
-      assert(InstrNum != 0 && "Bit 0 should never be set, something touched an "
-                              "instruction not in the lookup table");
+
+      // This instruction was found to be dead. We don't bother looking
+      // at it again.
+      if (InstrNum == 0) {
+        TouchedInstructions.reset(InstrNum);
+        continue;
+      }
+
       Value *V = DFSToInstr[InstrNum];
       BasicBlock *CurrBlock = nullptr;
 
       if (auto *I = dyn_cast<Instruction>(V))
         CurrBlock = I->getParent();
       else if (auto *MP = dyn_cast<MemoryPhi>(V))
         CurrBlock = MP->getBlock();
       else