[SCCPSolver] Speed up SCCPSolver by avoiding repeated work list elements

[tdanyluk]

Summary

If a value is already the last element of the worklist, then I think that we don't have to add it again, it is not needed to process it repeatedly.

For some long Triton-generated LLVM IR, this can cause a ~100x speedup.

[fhahn]

LGTM, but please a bit before landing in case there are additional comments.

[nikic]

llvm/lib/Transforms/Utils/SCCPSolver.cpp

850

Redundant braces here and above.

llvm/lib/Transforms/Utils/SCCPSolver.cpp

bool SCCPInstVisitor::markBlockExecutable(BasicBlock *BB) {
   if (!BBExecutable.insert(BB).second)
     return false;
   LLVM_DEBUG(dbgs() << "Marking Block Executable: " << BB->getName() << '\n');
   BBWorkList.push_back(BB); // Add the block to the work list!
   return true;
 }
 
 void SCCPInstVisitor::pushToWorkList(ValueLatticeElement &IV, Value *V) {
-  if (IV.isOverdefined())
-    return OverdefinedInstWorkList.push_back(V);
+  if (IV.isOverdefined()) {
+    if (OverdefinedInstWorkList.empty() || OverdefinedInstWorkList.back() != V)
+      OverdefinedInstWorkList.push_back(V);
+    return;
+  }
+  if (InstWorkList.empty() || InstWorkList.back() != V)
     InstWorkList.push_back(V);
 }
 
 void SCCPInstVisitor::pushToWorkListMsg(ValueLatticeElement &IV, Value *V) {
   LLVM_DEBUG(dbgs() << "updated " << IV << ": " << *V << '\n');
   pushToWorkList(IV, V);
 }
 
 bool SCCPInstVisitor::markConstant(ValueLatticeElement &IV, Value *V,
                                    Constant *C, bool MayIncludeUndef) {
   if (!IV.markConstant(C, MayIncludeUndef))
     return false;