[InstCombine] Fix worklist management in DSE (PR44552)

[nikic]

Summary

Fixes https://bugs.llvm.org/show_bug.cgi?id=44552. We need to make sure that the store is reprocessed, because performing DSE may expose more DSE opportunities.

There is a slight caveat here though: We need to make sure that we add back the store the worklist first, because that means it will be processed after the operands of the removed store have been processed. This is a general bug in InstCombine worklist management that I hope to address at some point, but for now it means we need to do this manually rather than just returning the instruction as changed.

[nikic]

I've added the complete original test case with -instcombine-infinite-loop-threshold=2. It would also be possible to reduce it (it just wouldn't need the full 1000 iterations that trigger the default threshold), but as the test now runs quickly even on a debug build, I figured keeping the original is fine.

llvm/lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

1447

Technically this could stay continue, but I'm uncomfortable with the fact that this just falls through to potentially doing other transforms below. I think it's better to DCE things here and let the instruction be reprocessed.

[spatel]

In D72807#1822794, @nikic wrote:

I've added the complete original test case with -instcombine-infinite-loop-threshold=2. It would also be possible to reduce it (it just wouldn't need the full 1000 iterations that trigger the default threshold), but as the test now runs quickly even on a debug build, I figured keeping the original is fine.

I think it would be better to shrink the test based on size if not speed. The current 1000 limit is arbitrary, and we can control when we hit the assert with the threshold flag, right?

llvm/lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

1447

I agree it's probably better to return here. But that means we should remove the unnecessary loop increment: ++BBI.

[nikic]

Remove unnecessary iterator increment. Reduce test case to use 100 instead of 1000 iterations.

[spatel]

I would've taken the test down to 5 or 10 to make it easier to see without scrolling, but this is fine. LGTM.

[hans]

Cherry-picked to 10.x in 7adf83beece381d153f8b4a67fa341d13f9c4ba2
Please let me know if there are any follow-ups.

llvm/lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

if (isa<DbgInfoIntrinsic>(BBI) ||
       continue;
     }
 
     if (StoreInst *PrevSI = dyn_cast<StoreInst>(BBI)) {
       // Prev store isn't volatile, and stores to the same location?
       if (PrevSI->isUnordered() && equivalentAddressValues(PrevSI->getOperand(1),
                                                         SI.getOperand(1))) {
         ++NumDeadStore;
-        ++BBI;
+        // Manually add back the original store to the worklist now, so it will
+        // be processed after the operands of the removed store, as this may
+        // expose additional DSE opportunities.
+        Worklist.Add(&SI);
         eraseInstFromFunction(*PrevSI);
-        continue;
+        return nullptr;
       }
       break;
     }
 
     // If this is a load, we have to stop.  However, if the loaded value is from
     // the pointer we're loading and is producing the pointer we're storing,
     // then *this* store is dead (X = load P; store X -> P).
     if (LoadInst *LI = dyn_cast<LoadInst>(BBI)) {

llvm/test/Transforms/InstCombine/pr44552.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -S -instcombine -instcombine-infinite-loop-threshold=2 < %s | FileCheck %s
+
+; This used to require 10 instcombine iterations to fully optimize.
+; The number of iterations grew linearly with the number of DSEd stores,
+; resulting in overall quadratic runtime.
+
+%struct.S3 = type { i64 }
+
+@csmith_sink_ = dso_local global i64 0, align 1
+@g_302_7 = internal constant i32 0, align 1
+@g_313_0 = internal global i16 0, align 1
+@g_313_1 = internal global i32 0, align 1
+@g_313_2 = internal global i32 0, align 1
+@g_313_3 = internal global i32 0, align 1
+@g_313_4 = internal global i16 0, align 1
+@g_313_5 = internal global i16 0, align 1
+@g_313_6 = internal global i16 0, align 1
+@g_316 = internal global %struct.S3 zeroinitializer, align 1
+@g_316_1_0 = internal global i16 0, align 1
+
+define i16 @main() {
+; CHECK-LABEL: @main(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    store i64 0, i64* @csmith_sink_, align 8
+; CHECK-NEXT:    ret i16 0
+;
+entry:
+  store i64 0, i64* @csmith_sink_, align 1
+  %0 = load i16, i16* @g_313_0, align 1
+  %conv2 = sext i16 %0 to i64
+  store i64 %conv2, i64* @csmith_sink_, align 1
+  %1 = load i32, i32* @g_313_1, align 1
+  %conv3 = zext i32 %1 to i64
+  store i64 %conv3, i64* @csmith_sink_, align 1
+  %2 = load i32, i32* @g_313_2, align 1
+  %conv4 = sext i32 %2 to i64
+  store i64 %conv4, i64* @csmith_sink_, align 1
+  %3 = load i32, i32* @g_313_3, align 1
+  %conv5 = zext i32 %3 to i64
+  store i64 %conv5, i64* @csmith_sink_, align 1
+  %4 = load i16, i16* @g_313_4, align 1
+  %conv6 = sext i16 %4 to i64
+  store i64 %conv6, i64* @csmith_sink_, align 1
+  %5 = load i16, i16* @g_313_5, align 1
+  %conv7 = sext i16 %5 to i64
+  store i64 %conv7, i64* @csmith_sink_, align 1
+  %6 = load i16, i16* @g_313_6, align 1
+  %conv8 = sext i16 %6 to i64
+  store i64 %conv8, i64* @csmith_sink_, align 1
+  %7 = load i64, i64* getelementptr inbounds (%struct.S3, %struct.S3* @g_316, i32 0, i32 0), align 1
+  store i64 %7, i64* @csmith_sink_, align 1
+  %8 = load i16, i16* @g_316_1_0, align 1
+  %conv9 = sext i16 %8 to i64
+  store i64 %conv9, i64* @csmith_sink_, align 1
+  store i64 0, i64* @csmith_sink_, align 1
+  ret i16 0
+}
+