Make dropTriviallyDeadConstantArrays not quadratic

d0k · d0k · commit 81f385b0c6ea · 2020-01-21T16:06:46.000+01:00
Only look at the operands of dead constant arrays instead of all
constant arrays again.
diff --git a/llvm/lib/IR/LLVMContextImpl.cpp b/llvm/lib/IR/LLVMContextImpl.cpp
@@ -11,6 +11,7 @@
 //===----------------------------------------------------------------------===//
 
 #include "LLVMContextImpl.h"
+#include "llvm/ADT/SetVector.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/OptBisect.h"
 #include "llvm/IR/Type.h"
@@ -142,18 +143,19 @@ LLVMContextImpl::~LLVMContextImpl() {
 }
 
 void LLVMContextImpl::dropTriviallyDeadConstantArrays() {
-  bool Changed;
-  do {
-    Changed = false;
-
-    for (auto I = ArrayConstants.begin(), E = ArrayConstants.end(); I != E;) {
-      auto *C = *I++;
-      if (C->use_empty()) {
-        Changed = true;
-        C->destroyConstant();
+  SmallSetVector<ConstantArray *, 4> WorkList(ArrayConstants.begin(),
+                                              ArrayConstants.end());
+
+  while (!WorkList.empty()) {
+    ConstantArray *C = WorkList.pop_back_val();
+    if (C->use_empty()) {
+      for (const Use &Op : C->operands()) {
+        if (auto *COp = dyn_cast<ConstantArray>(Op))
+          WorkList.insert(COp);
       }
+      C->destroyConstant();
     }
-  } while (Changed);
+  }
 }
 
 void Module::dropTriviallyDeadConstantArrays() {
