[LoopSimplifyCFG] Pay respect to LCSSA when removing dead blocks

[mkazantsev]

Summary

Utility function that we use for blocks deletion always unconditionally removes
one-input Phis. In LoopSimplifyCFG, it can lead to breach of LCSSA form.
This patch alters this function to keep them if needed.

[fhahn]

I think ideally we would just avoid deleting LCSSA PHI nodes (PHI nodes with a single incoming value in loop exit blocks), but maybe it is too much effort with the info available.

include/llvm/Transforms/Utils/BasicBlockUtils.h

44

nit: How about KeepUselessPHIs, or KeepSingleValuePHIs, which is a bit more descriptive.

test/Transforms/LoopSimplifyCFG/lcssa.ll

2

I think the relevant -verify-loop-lcssa & co are available without asserts as well, so we should be able to drop REQUIRE: asserts.

[mkazantsev]

include/llvm/Transforms/Utils/BasicBlockUtils.h

44

I used exactly the same name as existing function removePredecessor has. We can make a follow-up refactoring to change them all, but so far I'd prefer to keep things uniform.

test/Transforms/LoopSimplifyCFG/lcssa.ll

2

I didn't check that. We can do it as follow-up if it works.

[mkazantsev]

Ping?

[fedor.sergeev]

LGTM, but please, schedule those followups discussed here.

include/llvm/Transforms/Utils/BasicBlockUtils.h

44

I also find this name very confusing...

[mkazantsev]

include/llvm/Transforms/Utils/BasicBlockUtils.h

44

I will rename all its occurrences in a follow-up.

[mkazantsev]

I'll split out changes in basic block utils as separate NFC, then submit change in LoopSimplifyCFG separately.

[mkazantsev]

include/llvm/Transforms/Utils/BasicBlockUtils.h

44

https://reviews.llvm.org/rL353801

[fedor.sergeev]

In D57231#1394232, @mkazantsev wrote:

I'll split out changes in basic block utils as separate NFC, then submit change in LoopSimplifyCFG separately.

Thanks, your effort is really appreciated!

include/llvm/Transforms/Utils/BasicBlockUtils.h

 class MDNode;
 class MemoryDependenceResults;
 class MemorySSAUpdater;
 class ReturnInst;
 class TargetLibraryInfo;
 class Value;
 
 /// Delete the specified block, which must have no predecessors.
-void DeleteDeadBlock(BasicBlock *BB, DomTreeUpdater *DTU = nullptr);
+void DeleteDeadBlock(BasicBlock *BB, DomTreeUpdater *DTU = nullptr,
+                     bool DontDeleteUselessPHIs = false);
 
 /// Delete the specified blocks from \p BB. The set of deleted blocks must have
 /// no predecessors that are not being deleted themselves. \p BBs must have no
 /// duplicating blocks. If there are loops among this set of blocks, all
 /// relevant loop info updates should be done before this function is called.
+/// If \p DontDeleteUselessPHIs is true, one-input Phis in successors of blocks
+/// being deleted will be preserved.
 void DeleteDeadBlocks(SmallVectorImpl <BasicBlock *> &BBs,
-                      DomTreeUpdater *DTU = nullptr);
+                      DomTreeUpdater *DTU = nullptr,
+                      bool DontDeleteUselessPHIs = false);
 
 /// We know that BB has one predecessor. If there are any single-entry PHI nodes
 /// in it, fold them away. This handles the case when all entries to the PHI
 /// nodes in a block are guaranteed equal, such as when the block has exactly
 /// one predecessor.
 void FoldSingleEntryPHINodes(BasicBlock *BB,
                              MemoryDependenceResults *MemDep = nullptr);
 

lib/Transforms/Scalar/LoopSimplifyCFG.cpp

void deleteDeadLoopBlocks() {
     for (auto *BB : DeadLoopBlocks) {
       assert(BB != L.getHeader() &&
              "Header of the current loop cannot be dead!");
       LLVM_DEBUG(dbgs() << "Deleting dead loop block " << BB->getName()
                         << "\n");
       LI.removeBlock(BB);
     }
 
-    DeleteDeadBlocks(DeadLoopBlocks, &DTU);
+    DeleteDeadBlocks(DeadLoopBlocks, &DTU, /*DontDeleteUselessPHIs */ true);
     NumLoopBlocksDeleted += DeadLoopBlocks.size();
   }
 
   /// Constant-fold terminators of blocks acculumated in FoldCandidates into the
   /// unconditional branches.
   void foldTerminators() {
     DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
 

lib/Transforms/Utils/BasicBlockUtils.cpp

 #include <cassert>
 #include <cstdint>
 #include <string>
 #include <utility>
 #include <vector>
 
 using namespace llvm;
 
-void llvm::DeleteDeadBlock(BasicBlock *BB, DomTreeUpdater *DTU) {
+void llvm::DeleteDeadBlock(BasicBlock *BB, DomTreeUpdater *DTU,
+                           bool DontDeleteUselessPHIs) {
   SmallVector<BasicBlock *, 1> BBs = {BB};
-  DeleteDeadBlocks(BBs, DTU);
+  DeleteDeadBlocks(BBs, DTU, DontDeleteUselessPHIs);
 }
 
 void llvm::DeleteDeadBlocks(SmallVectorImpl <BasicBlock *> &BBs,
-                            DomTreeUpdater *DTU) {
+                            DomTreeUpdater *DTU, bool DontDeleteUselessPHIs) {
 #ifndef NDEBUG
   // Make sure that all predecessors of each dead block is also dead.
   SmallPtrSet<BasicBlock *, 4> Dead(BBs.begin(), BBs.end());
   assert(Dead.size() == BBs.size() && "Duplicating blocks?");
   for (auto *BB : Dead)
     for (BasicBlock *Pred : predecessors(BB))
       assert(Dead.count(Pred) && "All predecessors must be dead!");
 #endif
 
   SmallVector<DominatorTree::UpdateType, 4> Updates;
   for (auto *BB : BBs) {
     // Loop through all of our successors and make sure they know that one
     // of their predecessors is going away.
     for (BasicBlock *Succ : successors(BB)) {
-      Succ->removePredecessor(BB);
+      Succ->removePredecessor(BB, DontDeleteUselessPHIs);
       if (DTU)
         Updates.push_back({DominatorTree::Delete, BB, Succ});
     }
 
     // Zap all the instructions in the block.
     while (!BB->empty()) {
       Instruction &I = BB->back();
       // If this instruction is used, replace uses with an arbitrary value.

test/Transforms/LoopSimplifyCFG/lcssa.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
-; XFAIL: *
 ; REQUIRES: asserts
 ; RUN: opt -S -enable-loop-simplifycfg-term-folding=true -loop-simplifycfg -verify-loop-info -verify-dom-info -verify-loop-lcssa < %s | FileCheck %s
 ; RUN: opt -S -enable-loop-simplifycfg-term-folding=true -passes='require<domtree>,loop(simplify-cfg)' -verify-loop-info -verify-dom-info -verify-loop-lcssa < %s | FileCheck %s
 ; RUN: opt -S -enable-loop-simplifycfg-term-folding=true -loop-simplifycfg -enable-mssa-loop-dependency=true -verify-memoryssa -verify-loop-info -verify-dom-info -verify-loop-lcssa < %s | FileCheck %s
 
 target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128"
 
 define void @c() {
 ; CHECK-LABEL: @c(
while.cond:                                       ; preds = %while.body, %for.cond
   br i1 true, label %while.body, label %for.cond.loopexit
 
 while.body:                                       ; preds = %while.cond
   %inc4 = add nsw i16 %inc41, 1
   br label %while.cond
 }
 
 define void @bar() {
-
-; CHECK-LABEL: @bar
+; CHECK-LABEL: @bar(
+; CHECK-NEXT:  bb:
+; CHECK-NEXT:    switch i32 0, label [[BB_SPLIT:%.*]] [
+; CHECK-NEXT:    i32 1, label [[BB10:%.*]]
+; CHECK-NEXT:    ]
+; CHECK:       bb-split:
+; CHECK-NEXT:    br label [[BB1:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    [[TMP:%.*]] = phi i32 [ [[TMP7:%.*]], [[BB6:%.*]] ], [ undef, [[BB_SPLIT]] ]
+; CHECK-NEXT:    switch i32 undef, label [[BB5:%.*]] [
+; CHECK-NEXT:    i32 0, label [[BB6]]
+; CHECK-NEXT:    i32 1, label [[BB8:%.*]]
+; CHECK-NEXT:    ]
+; CHECK:       bb5:
+; CHECK-NEXT:    ret void
+; CHECK:       bb6:
+; CHECK-NEXT:    [[TMP7]] = add i32 undef, 123
+; CHECK-NEXT:    br label [[BB1]]
+; CHECK:       bb8:
+; CHECK-NEXT:    [[TMP9:%.*]] = phi i32 [ [[TMP]], [[BB1]] ]
+; CHECK-NEXT:    [[USE:%.*]] = add i32 [[TMP9]], 1
+; CHECK-NEXT:    ret void
+; CHECK:       bb10:
+; CHECK-NEXT:    ret void
+;
 
 bb:
   br label %bb1
 
 bb1:                                              ; preds = %bb6, %bb
   %tmp = phi i32 [ %tmp7, %bb6 ], [ undef, %bb ]
   br i1 false, label %bb2, label %bb4
 
 bb2:                                              ; preds = %bb1
   switch i32 undef, label %bb10 [
-    i32 0, label %bb3
-    i32 1, label %bb8
   ]
 
 bb3:                                              ; preds = %bb2
   br label %bb6
 
 bb4:                                              ; preds = %bb1
   switch i32 undef, label %bb5 [
-    i32 0, label %bb6
-    i32 1, label %bb8
   ]
 
 bb5:                                              ; preds = %bb4
   ret void
 
 bb6:                                              ; preds = %bb4, %bb3
   %tmp7 = add i32 undef, 123
   br label %bb1