[WIP] Don't delete all llvm.assume instructions in codegenprepare

[markus]

Summary

Only delete those @llvm.assumes that including their predecessors (with no other successors) are the sole occupants of a block.

The rationale is that whenever possible we need to preserve the @llvm.assumes in IR during codegen as they help guide AA during instruction scheduling.

[markus]

Abandoned in favor of D103316.

llvm/lib/CodeGen/CodeGenPrepare.cpp

while (BB != nullptr) {
       BasicBlock* Next = BB->getNextNode();
       // F.hasOptSize is already checked in the outer if statement.
       if (!llvm::shouldOptimizeForSize(BB, PSI, BFI.get()))
         EverMadeChange |= bypassSlowDivision(BB, BypassWidths);
       BB = Next;
     }
   }
 
-  // Get rid of @llvm.assume builtins before attempting to eliminate empty
+  // Get rid of @llvm.assume builtins (if they and their predecessors are the
+  // only real occupants of a block) before attempting to eliminate empty
   // blocks, since there might be blocks that only contain @llvm.assume calls
   // (plus arguments that we can get rid of).
   EverMadeChange |= eliminateAssumptions(F);
 
   // Eliminate blocks that contain only PHI nodes and an
   // unconditional branch.
   EverMadeChange |= eliminateMostlyEmptyBlocks(F);
 
if (VerifyBFIUpdates)
     verifyBFIUpdates(F);
 #endif
 
   return EverMadeChange;
 }
 
 bool CodeGenPrepare::eliminateAssumptions(Function &F) {
   bool MadeChange = false;
-  for (BasicBlock &BB : F) {
-    CurInstIterator = BB.begin();
-    while (CurInstIterator != BB.end()) {
+
+  auto allSuccsInSet = [](auto V, auto &Set) {
+    for (auto U : V->users())
+      if (!Set.count(cast<Instruction>(U)))
+        return false;
+    return true;
+  };
+
+  auto getNumPHIs = [](auto *BB) {
+    unsigned NumPHIs = 0;
+    for (auto &PN : BB->phis()) {
+      (void)PN;
+      ++NumPHIs;
+    }
+    return NumPHIs;
+  };
+
+  ReversePostOrderTraversal<BasicBlock *> RPOT(&F.getEntryBlock());
+  for (auto *BB : RPOT) {
+    // Find the set of non-PHI instruction in BB made up of @llvm.assumes and
+    // their predecessors.
+    SmallSet<Instruction *, 8> AssumesAndPreds;
+    auto CurInstIterator = BB->rbegin();
+    while (CurInstIterator != BB->rend()) {
       Instruction *I = &*(CurInstIterator++);
       if (auto *Assume = dyn_cast<AssumeInst>(I)) {
-        MadeChange = true;
-        Value *Operand = Assume->getOperand(0);
+        SmallVector<Instruction *, 8> WorkList;
+        WorkList.push_back(Assume);
+        while (WorkList.size() > 0) {
+          auto W = WorkList.back();
+          WorkList.pop_back();
+          if (W->getParent() == BB && !isa<PHINode>(W) &&
+              allSuccsInSet(W, AssumesAndPreds) &&
+              (Assume == W || wouldInstructionBeTriviallyDead(W, TLInfo))) {
+            AssumesAndPreds.insert(W);
+            // Insert all operands of W in WorkList.
+            for (unsigned I = 0, E = W->getNumOperands(); I < E; ++I)
+              if (auto O = dyn_cast<Instruction>(W->getOperand(I)))
+                WorkList.push_back(O);
+          }
+        }
+      }
+    }
+    // If that set was the entire contents of BB except for PHI-nodes and a
+    // terminator then go ahead and delete those @llvm.assume and their
+    // predecessors.
+    if (AssumesAndPreds.size() > 0 &&
+        AssumesAndPreds.size() == BB->size() - 1 - getNumPHIs(BB)) {
+      for (auto T : AssumesAndPreds) {
+        if (auto *Assume = dyn_cast<AssumeInst>(T)) {
+          auto *Operand = Assume->getOperand(0);
           Assume->eraseFromParent();
-
-        resetIteratorIfInvalidatedWhileCalling(&BB, [&]() {
           RecursivelyDeleteTriviallyDeadInstructions(Operand, TLInfo, nullptr);
-        });
         }
       }
+      MadeChange = true;
+    }
   }
   return MadeChange;
 }
 
 /// An instruction is about to be deleted, so remove all references to it in our
 /// GEP-tracking data strcutures.
 void CodeGenPrepare::removeAllAssertingVHReferences(Value *V) {
   LargeOffsetGEPMap.erase(V);
for (auto &Arg : CI->arg_operands()) {
       unsigned AS = Arg->getType()->getPointerAddressSpace();
       return optimizeMemoryInst(CI, Arg, Arg->getType(), AS);
     }
 
   IntrinsicInst *II = dyn_cast<IntrinsicInst>(CI);
   if (II) {
     switch (II->getIntrinsicID()) {
     default: break;
-    case Intrinsic::assume:
-      llvm_unreachable("llvm.assume should have been removed already");
     case Intrinsic::experimental_widenable_condition: {
       // Give up on future widening oppurtunties so that we can fold away dead
       // paths and merge blocks before going into block-local instruction
       // selection.
       if (II->use_empty()) {
         II->eraseFromParent();
         return true;
       }

llvm/test/Transforms/CodeGenPrepare/X86/recursively-delete-dead-instructions.ll

-; RUN: opt -codegenprepare -S -mtriple=x86_64-linux < %s | FileCheck %s
-
-declare void @llvm.assume(i1 noundef) nounwind willreturn
-
-; Recursively deleting dead operands of assume() may result in its next
-; instruction deleted and the iterator pointing to the next instruction
-; invalidated. This prevents the following simple loop in
-; CodeGenPrepare::optimizeBlock() unless CurInstIterator is fixed:
-;
-;   CurInstIterator = BB.begin();
-;   while (CurInstIterator != BB.end())
-;     optimizeInst(&*CurInstIterator++, ModifiedDT);
-;
-define i32 @test_assume_in_loop(i1 %cond1, i1 %cond2) {
-; CHECK-LABEL: @test_assume_in_loop(
-; CHECK-NEXT:  entry:
-entry:
-  br label %loop
-
-; CHECK: loop:
-; CHECK-NEXT:  br label %loop
-loop:
-  %cond3 = phi i1 [%cond1, %entry], [%cond4, %loop]
-  call void @llvm.assume(i1 %cond3)
-  %cond4 = icmp ult i1 %cond1, %cond2
-  br label %loop
-}