Faster SimplifyInstructionsInBlock

[escha]

Summary

From the original RFC:

1. Use a worklist, not a recursive approach, to avoid needless revisitation and being repeatedly forced to jump back to the start of the BB if a handle is invalidated.
2. Only insert operands to the worklist if they become unused after a dead instruction is removed, so we don’t have to visit them again in most cases.
3. Use a SmallSetVector to track the worklist.
4. Instead of pre-initting the SmallSetVector like in DeadCodeEliminationPass, only put things into the worklist if they have to be revisited after the first run-through. This minimizes how much the actual SmallSetVector gets used, which saves a lot of time.

One small change since the original is fix a bug where we were adding the users to the list even if they were the current instruction, which is possible with phi nodes (and causes a crash).

[reames]

lib/Transforms/Utils/Local.cpp

427

You need to pass in TLI here or you have a regression over the previous code when handling target library routines.

432

Use a foreach operands loop here.

Actually, the style used in RecursivelyDeleteTriviallyDeadInstructions is probably preferable here. It doesn't need the extra Operands array.

461

I think this should just be an assert at the top of the function. Or at least, if you're going to handle this in one case, handle it in the dead instruction case as well.

495

This remove seems problematic. Isn't this potentially O(n^2) in the instructions in the BB? Or is the argument that we're walking through the BB in an order where they shouldn't generally be in the Worklist?

Would it be cleaner/safer to use a SmallSetVector of Weak Value Handles and then just skip the deleted nodes?

Or alternatively, just not visit the instruction here if it's already in the worklist?

[escha]

lib/Transforms/Utils/Local.cpp

427

Ah, right, I missed that. Will fix.

432

Ah, I see, that should work.

461

Okay, I was just matching the original code; I didn't quite understand what it's there for?

495

Removal from a SmallSetVector should be fast, shouldn't it?

Also, one of the main problems I encountered earlier is specifically that WeakVHs are *incredibly slow* and constructing them took a large portion of this function's time.

[escha]

Updated per comments.

[reames]

lib/Transforms/Utils/Local.cpp

461

I don't know. If the assert doesn't fail, it clearly wasn't tested or used.

495

Why would removing from a SmallSetVector be fast? It appears to be doing an erase on the underlying vector which is needed to preserve order.

Does simply skipping the instruction if it's already in the worklist work? That should be pretty fast.

[escha]

Avoiding using remove() on the setvector.

[reames]

LGTM w/one minor comment, but please give it a day or so in case anyone else spots something I've missed.

lib/Transforms/Utils/Local.cpp

488

please use std::prev instead of -- here. Makes it more clear what's going on.

[escha]

Committed.

lib/Transforms/Utils/Local.cpp

 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/Hashing.h"
 #include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/InstructionSimplify.h"

   return false;
 }
 
+static bool
+simplifyAndDCEInstruction(Instruction *I,
+                          SmallSetVector<Instruction *, 16> &WorkList,
+                          const DataLayout &DL,
+                          const TargetLibraryInfo *TLI) {
+  if (isInstructionTriviallyDead(I, TLI)) {
+    // Null out all of the instruction's operands to see if any operand becomes
+    // dead as we go.
+    for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
+      Value *OpV = I->getOperand(i);
+      I->setOperand(i, nullptr);
+
+      if (!OpV->use_empty() || I == OpV)
+        continue;
+
+      // If the operand is an instruction that became dead as we nulled out the
+      // operand, and if it is 'trivially' dead, delete it in a future loop
+      // iteration.
+      if (Instruction *OpI = dyn_cast<Instruction>(OpV))
+        if (isInstructionTriviallyDead(OpI, TLI))
+          WorkList.insert(OpI);
+    }
+
+    I->eraseFromParent();
+
+    return true;
+  }
+
+  if (Value *SimpleV = SimplifyInstruction(I, DL)) {
+    // Add the users to the worklist. CAREFUL: an instruction can use itself,
+    // in the case of a phi node.
+    for (User *U : I->users())
+      if (U != I)
+        WorkList.insert(cast<Instruction>(U));
+
+    // Replace the instruction with its simplified value.
+    I->replaceAllUsesWith(SimpleV);
+    I->eraseFromParent();
+    return true;
+  }
+  return false;
+}
+
 /// SimplifyInstructionsInBlock - Scan the specified basic block and try to
 /// simplify any instructions in it and recursively delete dead instructions.
 ///

 bool llvm::SimplifyInstructionsInBlock(BasicBlock *BB,
                                        const TargetLibraryInfo *TLI) {
   bool MadeChange = false;
+  const DataLayout &DL = BB->getModule()->getDataLayout();
 
 #ifndef NDEBUG
   // In debug builds, ensure that the terminator of the block is never replaced

   AssertingVH<Instruction> TerminatorVH(--BB->end());
 #endif
 
-  for (BasicBlock::iterator BI = BB->begin(), E = --BB->end(); BI != E; ) {
+  SmallSetVector<Instruction *, 16> WorkList;
+  // Iterate over the original function, only adding insts to the worklist
+  // if they actually need to be revisited. This avoids having to pre-init
+  // the worklist with the entire function's worth of instructions.
+  for (BasicBlock::iterator BI = BB->begin(), E = --BB->end(); BI != E;) {
     assert(!BI->isTerminator());
-    Instruction *Inst = BI++;
+    Instruction *I = &*BI;
+    ++BI;
 
-    WeakVH BIHandle(BI);
-    if (recursivelySimplifyInstruction(Inst, TLI)) {
-      MadeChange = true;
-      if (BIHandle != BI)
-        BI = BB->begin();
-      continue;
-    }
+    // We're visiting this instruction now, so make sure it's not in the
+    // worklist from an earlier visit.
+    if (!WorkList.count(I))
+      MadeChange |= simplifyAndDCEInstruction(I, WorkList, DL, TLI);
+  }
 
-    MadeChange |= RecursivelyDeleteTriviallyDeadInstructions(Inst, TLI);
-    if (BIHandle != BI)
-      BI = BB->begin();
+  while (!WorkList.empty()) {
+    Instruction *I = WorkList.pop_back_val();
+    MadeChange |= simplifyAndDCEInstruction(I, WorkList, DL, TLI);
   }
   return MadeChange;
 }