[DSE] Fall back to CFG scan for unreachable terminators.

[fhahn]

Summary

Blocks with UnreachableInst terminators are considered as root nodes in
the PDT. This pessimize DSE, if there are no aliasing reads from the
potentially dead store and the block with the unreachable terminator.

If the PDT has a virtual root node and any of the root nodes has
UnreachableInst as terminator, fall back to the CFG scan, even the
common dominator of all killing blocks does not post-dominate the block
with potentially dead store.

It looks like the compile-time impact for the extra scans is negligible.
https://llvm-compile-time-tracker.com/compare.php?from=779bbbf27fe631154bdfaac7a443f198d4654688&to=ac59945f1bec1c6a7d7f5590c8c69fd9c5369c53&stat=instructions

Fixes #53800.

[efriedma]

I'm not convinced this is right... what happens if you replace "exit" with something that throws an exception, or calls longjmp, or has an infinite loop? I'm not seeing any logic in this patch that actually reasons about the contents of the block that ends in "unreachable".

[fhahn]

In D119760#3320798, @efriedma wrote:

I'm not convinced this is right... what happens if you replace "exit" with something that throws an exception, or calls longjmp, or has an infinite loop? I'm not seeing any logic in this patch that actually reasons about the contents of the block that ends in "unreachable".

I think this part of the code should only be responsible for checking that the killed store is not visible after the function returns (= only done for objects visible to the caller around like 1496).

If there are any reads or throwing calls, those should be handled during the mem-ssa traversal earlier. If there's an infinite loop or a function that does not return, I don't think this would cause an issue, because we only need to check if there's a path to an exit that returns to the caller via a regular return. I'm not sure how the longjump case would be modeled exactly, but I think this would also need to be handled by the earlier checks before we reach this code.

There are a couple of extra tests (@unreachable_exit_with_may_unwind_call, @unreachable_exit_and_call_may_read) that should test some of the scenarios you mentioned.

[efriedma]

As long as you've thought about it, I guess...

I'm a little confused by the different traversals, though. Have you considered just treating "ret" as reading memory, instead of analyzing "ret" using a different codepath from unwinding?

[nikic]

Please rebase over https://github.com/llvm/llvm-project/commit/2460a2ce47873109e9b300f65e1bd2f4c4b86bfb.

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

813

The first check here looks redundant. Doesn't PDT always have virtual root?

[fhahn]

In D119760#3322493, @nikic wrote:

Please rebase over https://github.com/llvm/llvm-project/commit/2460a2ce47873109e9b300f65e1bd2f4c4b86bfb.

Done,thanks!

In D119760#3321039, @efriedma wrote:

As long as you've thought about it, I guess...

I'm a little confused by the different traversals, though. Have you considered just treating "ret" as reading memory, instead of analyzing "ret" using a different codepath from unwinding?

Initially one approach was to model reads at function exits through a special intrinsic (D73763), but in the end we went with the current approach of the extra checks.

I put up a new patch that introduces dummy loads just before exits to see how it would look in terms of compile-time, and it looks mostly neutral, with slightly more stores removed: D119879. One concern with the original patch was the use of a new intrinsic. This patch just adds dummy loads, not sure if there's a better way.

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

813

It's not needed! Removed.

[nikic]

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1522–1529

Should be sufficient to only change this branch?

if (!PDT.dominates(CommonPred, MaybeDeadAccess->getBlock())) {
  // Comment
  if (!AnyUnreachableExit)
    return None;
  CommonPred = nullptr;
}

[fhahn]

Removed unneeded branch as suggested, thanks!

[fhahn]

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1522–1529

Good point, updated as suggested, thanks!

[nikic]

LGTM

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

struct DSEState {
   SmallPtrSet<BasicBlock *, 16> ThrowingBlocks;
   // Post-order numbers for each basic block. Used to figure out if memory
   // accesses are executed before another access.
   DenseMap<BasicBlock *, unsigned> PostOrderNumbers;
 
   /// Keep track of instructions (partly) overlapping with killing MemoryDefs per
   /// basic block.
   MapVector<BasicBlock *, InstOverlapIntervalsTy> IOLs;
+  // Check if there are root nodes that are terminated by UnreachableInst.
+  // Those roots pessimize post-dominance queries. If there are such roots,
+  // fall back to CFG scan starting from all non-unreachable roots.
+  bool AnyUnreachableExit;
 
   // Class contains self-reference, make sure it's not copied/moved.
   DSEState(const DSEState &) = delete;
   DSEState &operator=(const DSEState &) = delete;
 
   DSEState(Function &F, AliasAnalysis &AA, MemorySSA &MSSA, DominatorTree &DT,
            PostDominatorTree &PDT, const TargetLibraryInfo &TLI,
            const LoopInfo &LI)
DSEState(Function &F, AliasAnalysis &AA, MemorySSA &MSSA, DominatorTree &DT,
     // Treat byval or inalloca arguments the same as Allocas, stores to them are
     // dead at the end of the function.
     for (Argument &AI : F.args())
       if (AI.hasPassPointeeByValueCopyAttr())
         InvisibleToCallerAfterRet.insert({&AI, true});
 
     // Collect whether there is any irreducible control flow in the function.
     ContainsIrreducibleLoops = mayContainIrreducibleControl(F, &LI);
+
+    AnyUnreachableExit = any_of(PDT.roots(), [](const BasicBlock *E) {
+      return isa<UnreachableInst>(E->getTerminator());
+    });
   }
 
   /// Return 'OW_Complete' if a store to the 'KillingLoc' location (by \p
   /// KillingI instruction) completely overwrites a store to the 'DeadLoc'
   /// location (by \p DeadI instruction).
   /// Return OW_MaybePartial if \p KillingI does not completely overwrite
   /// \p DeadI, but they both write to the same underlying object. In that
   /// case, use isPartialOverwrite to check if \p KillingI partially overwrites
if (!isInvisibleToCallerAfterRet(KillingUndObj)) {
         if (!CommonPred)
           break;
         CommonPred = PDT.findNearestCommonDominator(CommonPred, BB);
       }
 
       // If the common post-dominator does not post-dominate MaybeDeadAccess,
       // there is a path from MaybeDeadAccess to an exit not going through a
       // killing block.
-      if (!PDT.dominates(CommonPred, MaybeDeadAccess->getBlock()))
+      if (!PDT.dominates(CommonPred, MaybeDeadAccess->getBlock())) {
+        if (!AnyUnreachableExit)
           return None;
 
+        // Fall back to CFG scan starting at all non-unreachable roots if not
+        // all paths to the exit go through CommonPred.
+        CommonPred = nullptr;
+      }
+
       // If CommonPred itself is in the set of killing blocks, we're done.
       if (KillingBlocks.count(CommonPred))
         return {MaybeDeadAccess};
 
       SetVector<BasicBlock *> WorkList;
-
       // If CommonPred is null, there are multiple exits from the function.
       // They all have to be added to the worklist.
       if (CommonPred)
         WorkList.insert(CommonPred);
       else
-        for (BasicBlock *R : PDT.roots())
+        for (BasicBlock *R : PDT.roots()) {
+          if (!isa<UnreachableInst>(R->getTerminator()))
             WorkList.insert(R);
+        }
 
       NumCFGTries++;
       // Check if all paths starting from an exit node go through one of the
       // killing blocks before reaching MaybeDeadAccess.
       for (unsigned I = 0; I < WorkList.size(); I++) {
         NumCFGChecks++;
         BasicBlock *Current = WorkList[I];
         if (KillingBlocks.count(Current))

llvm/test/Transforms/DeadStoreElimination/multiblock-unreachable.ll

bb53:                                             ; preds = %bb53, %bb50, %bb22, %bb
   br label %bb53
 }
 
 declare void @exit()
 
 define void @unreachable_exit_with_no_call(i64* noalias %ptr, i1 %c.1) {
 ; CHECK-LABEL: @unreachable_exit_with_no_call(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    store i64 1, i64* [[PTR:%.*]], align 8
 ; CHECK-NEXT:    br i1 [[C_1:%.*]], label [[IF_THEN:%.*]], label [[IF_END:%.*]]
 ; CHECK:       if.then:
 ; CHECK-NEXT:    unreachable
 ; CHECK:       if.end:
-; CHECK-NEXT:    store i64 0, i64* [[PTR]], align 8
+; CHECK-NEXT:    store i64 0, i64* [[PTR:%.*]], align 8
 ; CHECK-NEXT:    ret void
 ;
 entry:
   store i64 1, i64* %ptr, align 8
   br i1 %c.1, label %if.then, label %if.end
 
 if.then:
   unreachable
 
 if.end:
   store i64 0, i64* %ptr, align 8
   ret void
 }
 
 ; Test for PR53800.
 define void @unreachable_exit_with_nounwind_call_pr53800(i64* noalias %ptr, i1 %c.1) {
 ; CHECK-LABEL: @unreachable_exit_with_nounwind_call_pr53800(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    store i64 1, i64* [[PTR:%.*]], align 8
 ; CHECK-NEXT:    br i1 [[C_1:%.*]], label [[IF_THEN:%.*]], label [[IF_END:%.*]]
 ; CHECK:       if.then:
 ; CHECK-NEXT:    tail call void @exit() #[[ATTR0:[0-9]+]]
 ; CHECK-NEXT:    unreachable
 ; CHECK:       if.end:
-; CHECK-NEXT:    store i64 0, i64* [[PTR]], align 8
+; CHECK-NEXT:    store i64 0, i64* [[PTR:%.*]], align 8
 ; CHECK-NEXT:    ret void
 ;
 entry:
   store i64 1, i64* %ptr, align 8
   br i1 %c.1, label %if.then, label %if.end
 
 if.then:
   tail call void @exit() nounwind