[CGP] Remove operand of llvm.assume more aggressively.

[skatkov]

Summary

At the moment CGP recursively removes operand of llvm.assume but
it does it only for instructions has no more than one use.

This is not enough for some induction variable which is used only
in llvm.assume.

As soon as there is no any dead code elimination passes between
CGP and instruction selector it makes sense to apply more efforts
at CGP to remove dead code.

[skatkov]

Fix comments.

[skatkov]

ping

[anna]

llvm/lib/CodeGen/CodeGenPrepare.cpp

807

Nit: change the order of declarations so that the comment is clearer?

814

assert that I is already in ToRemove set?

[anna]

LGTM (maybe wait for other reviewers for couple of days) with added tests.

llvm/test/Transforms/CodeGenPrepare/X86/delete-assume-dead-code.ll

48

Pls add couple of tests:

• positive test: %iv2.inc is used in another cmp which feeds into another assume
• negative test: %iv2 is used in a cmp3 which is used as a sub condition in the branch (and i1 %cmp, %cmp3)

[xbolva00]

llvm/lib/CodeGen/CodeGenPrepare.cpp

803

Maybe extract to smaller function(s)?

Readibility if this new part is not ideal, so many nesting levels, ..

[skatkov]

is it better?

[skatkov]

Test are updated. Code re-factored. Anything I can do to land this?

[arsenm]

llvm/lib/CodeGen/CodeGenPrepare.cpp

716

sentence sounds like it's missing a word here?

720

Start with lowercase

720

I'm not sure what closure means in this context

724

Do this after the early exit?

748–749

How is this different from RecursivelyDeleteTriviallyDeadInstructions?

[skatkov]

Thanks a lot for review. I'll update a patch as soon as we agreed on terminology (Closure) and description of FindClosureOfWouldBeTriviallyDeadInstructions function.

llvm/lib/CodeGen/CodeGenPrepare.cpp

716

Well.. Let me try to re-phrase it as follows, please review is it better?

The utility function collects all transitively reachable users of I. If all users would be trivially dead in case they
would not have users then this function returns true and Closure contains I with all found users.
Otherwise function returns false and Closure content is not specified.
For the purpose of this function llvm.assume is considered ad trivially dead instruction.

720

Will do.

Closure means transitive closure of users of instruction I In other words I, its users, users of users and so on.

Any suggestion for better term?

724

No, early exit is a simple case when there is no users, so closure consists of 1 instruction I and I should return it in Closure for further erasing.

748–749

RecursivelyDeleteTriviallyDeadInstructions will delete instruction only if has no users, while this patch will find group of instructions which is connected to each other (see tests below, induction variable case) and remove them together is none of these instructions has users outside of this group and all of them would be trivially dead.

Also this function consider llvm.assume as trivially dead instruction. This is for the case when induction variable is used in two different assumes.

[skatkov]

please, take a look.

[skatkov]

one more function renamed to start with lower symbol.

[skatkov]

Comment update.

[skatkov]

Friendly ping...

[nikic]

Our longer term plan was to stop removing assumes in CGP, so they remain available during codegen, in particular for AA purposes. Instead, we would drop assumes more aggressively earlier if they keep control flow alive.

It seems pretty likely that assumes that keep alive otherwise dead IVs are also blocking optimizations in earlier parts of the pipeline, and we would be better of dropping such assumes earlier. I'm not entirely sure what the right heuristic for that would be, but "ephemeral values of the assume include a phi node" is probably a pretty good one.

[skatkov]

In D152358#4454950, @nikic wrote:

Our longer term plan was to stop removing assumes in CGP, so they remain available during codegen, in particular for AA purposes. Instead, we would drop assumes more aggressively earlier if they keep control flow alive.

It seems pretty likely that assumes that keep alive otherwise dead IVs are also blocking optimizations in earlier parts of the pipeline, and we would be better of dropping such assumes earlier. I'm not entirely sure what the right heuristic for that would be, but "ephemeral values of the assume include a phi node" is probably a pretty good one.

The current stage: remove but not everything looks the worst way. In my understanding, let's remove all the dead code together or keep it alive.
So I propose to land this up to the point CGP get rid of this code.

What do you think?

[anna]

Just to give more input here - we have seen many cases where the loop vectorizer generates a lot of code with a bunch of extracts for each assume operand. Basically we do not have "vectorized assumes". We were looking at two options - we drop such assumes before loop vectorizer or teach CodeGenPrepare to be more aggressive.

The issue is knowing *which assumes* would need to be kept until end of opt at least (@nikic heuristic may work here). I believe Serguei's proposal is to use this patch as a short term fix.
As a long term approach, I think if we do plan to keep assumes in CodeGen, we would need to figure out a "drop assumes" pass with some good heuristics and appopriate position in pipeline?

[jdoerfert]

We have ephemeral value trackers and other helpers, we should use those, assuming this is going forward.

[skatkov]

In D152358#4456534, @jdoerfert wrote:

We have ephemeral value trackers and other helpers, we should use those, assuming this is going forward.

EphemeralValueTracker does not recognize the group of instructions which combines to llvm.assume all together as well due to for each particular instruction it checks that all its users should be already marked as ephemeral value.
So for the tests below for phi node representing induction variable it will not recognize it as ephemeral one.

[skatkov]

I've taken a look at CodeMetrics::collectEphemeralValues. It does not recognize loops with phi node as well. I can extend its detector, however it collects ephemeral values basing on conditions "I->mayHaveSideEffects() || I->isTerminator()".

It is less than RecursivelyDeleteTriviallyDeadInstructions which is used currently in CodeGenPrepare. For example, RDTDI can remove allocations...

So, let's decide in what direction should I move.

The idea to remove it earlier.... Not sure at what moment we should do it. It might be useful one if some one will use it properly.

[skatkov]

In D152358#4456534, @jdoerfert wrote:

We have ephemeral value trackers and other helpers, we should use those, assuming this is going forward.

Please take a look at alternative https://reviews.llvm.org/D154584.

llvm/lib/CodeGen/CodeGenPrepare.cpp

 #ifndef NDEBUG
   if (VerifyBFIUpdates)
     verifyBFIUpdates(F);
 #endif
 
   return EverMadeChange;
 }
 
+// The utility function collects all transitively reachable users of I.
+// If all users would be trivially dead in case they would not have users then
+// this function returns true and Closure contains I with all found users.
+// Otherwise function returns false and Closure content is not specified.
+// For the purpose of this function llvm.assume is considered as
+// trivially dead instruction.
+static bool findClosureOfWouldBeTriviallyDeadInstructions(
+    Instruction *I, SmallPtrSetImpl<Instruction *> &Closure,
+    const TargetLibraryInfo *TLInfo) {
+  assert(wouldInstructionBeTriviallyDead(I, TLInfo) && "expect trivially dead");
+  Closure.insert(I);
+  // Simple Case. no users.
+  if (I->use_empty())
+    return true;
+
+  SmallVector<Instruction *, 4> Worklist;
+  Worklist.push_back(I);
+  while (!Worklist.empty()) {
+    Instruction *Curr = Worklist.pop_back_val();
+    for (auto *U : Curr->users()) {
+      auto *UI = dyn_cast<Instruction>(U);
+      if (!UI)
+        return false;
+      if (!Closure.insert(UI).second)
+        continue;
+      if (isa<AssumeInst>(UI) || wouldInstructionBeTriviallyDead(UI, TLInfo))
+        Worklist.push_back(UI);
+      else
+        return false;
+    }
+  }
+  return true;
+}
+
+// For the given trivially dead instruction if no uses, collect all instructions
+// which can be removed together with it.
+static void findInstructionsToRemoveWithAssumeOperand(
+    Instruction *OperandInst, SmallPtrSetImpl<Instruction *> &ToRemove,
+    const TargetLibraryInfo *TLInfo) {
+  // Keeps the operands of already marked to remove instructions.
+  // Contains only instructions would be trivial dead if no uses.
+  SmallPtrSet<Instruction *, 4> Candidates;
+  Candidates.insert(OperandInst);
+
+  // For a given set of instructions, mark them to be removed, their operands
+  // are erased from instructions and are added to Candidates set if they
+  // would be trivially dead if no uses.
+  auto AddToRemove = [&](SmallPtrSetImpl<Instruction *> &ISet) {
+    ToRemove.insert(ISet.begin(), ISet.end());
+    for (auto *I : ISet) {
+      for (Use &OpU : I->operands()) {
+        if (Value *OpV = OpU.get()) {
+          OpU.set(nullptr);
+          if (auto *OpI = dyn_cast<Instruction>(OpV))
+            if (!ToRemove.count(OpI) &&
+                wouldInstructionBeTriviallyDead(OpI, TLInfo))
+              Candidates.insert(OpI);
+        }
+      }
+    }
+  };
+
+  SmallPtrSet<Instruction *, 8> ClosureOfDeadInstructions;
+  while (!Candidates.empty()) {
+    Instruction *Cand = *Candidates.begin();
+    Candidates.erase(Cand);
+    if (findClosureOfWouldBeTriviallyDeadInstructions(
+            Cand, ClosureOfDeadInstructions, TLInfo))
+      AddToRemove(ClosureOfDeadInstructions);
+    ClosureOfDeadInstructions.clear();
+  }
+}
+
 bool CodeGenPrepare::eliminateAssumptions(Function &F) {
   bool MadeChange = false;
   for (BasicBlock &BB : F) {
     CurInstIterator = BB.begin();
     while (CurInstIterator != BB.end()) {
       Instruction *I = &*(CurInstIterator++);
       if (auto *Assume = dyn_cast<AssumeInst>(I)) {
         MadeChange = true;
         Value *Operand = Assume->getOperand(0);
         Assume->eraseFromParent();
 
         resetIteratorIfInvalidatedWhileCalling(&BB, [&]() {
-          RecursivelyDeleteTriviallyDeadInstructions(Operand, TLInfo, nullptr);
+          auto *OperandInst = dyn_cast<Instruction>(Operand);
+          if (!OperandInst ||
+              !wouldInstructionBeTriviallyDead(OperandInst, TLInfo))
+            return;
+          // Set of dead instructions after assume has been erased.
+          SmallPtrSet<Instruction *, 4> ToRemove;
+          findInstructionsToRemoveWithAssumeOperand(OperandInst, ToRemove,
+                                                    TLInfo);
+          // Remove everything we found.
+          for (auto *TR : ToRemove) {
+            assert(TR->use_empty() && "Expected no uses!");
+            salvageDebugInfo(*TR);
+            TR->eraseFromParent();
+          }
         });
       }
     }
   }
   return MadeChange;
 }
 
 /// An instruction is about to be deleted, so remove all references to it in our

llvm/test/Transforms/CodeGenPrepare/X86/delete-assume-dead-code.ll

 }
 
 define i32 @test2(i32 %N) nounwind {
 ; CHECK-LABEL: @test2(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[HEADER:%.*]]
 ; CHECK:       header:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_INC:%.*]], [[HEADER]] ]
-; CHECK-NEXT:    [[IV2:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[IV2_INC:%.*]], [[HEADER]] ]
 ; CHECK-NEXT:    [[IV_INC]] = add i32 [[IV]], 1
-; CHECK-NEXT:    [[IV2_INC]] = add i32 [[IV2]], 1
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[IV]], [[N:%.*]]
 ; CHECK-NEXT:    br i1 [[CMP]], label [[EXIT:%.*]], label [[HEADER]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret i32 [[IV]]
 ;
 entry:
   br label %header
 
 header:
   %iv = phi i32 [0, %entry], [%iv.inc, %header]
   %iv2 = phi i32 [0, %entry], [%iv2.inc, %header]
   %iv.inc = add i32 %iv, 1
   %iv2.inc = add i32 %iv2, 1
   %cmp = icmp eq i32 %iv, %N
   %cmp2 = icmp sle i32 %iv2, %N
   call void @llvm.assume(i1 %cmp2)
   br i1 %cmp, label %exit, label %header
 
 exit:
   ret i32 %iv
 }
 
 define i32 @test3(i32 %N) nounwind {
 ; CHECK-LABEL: @test3(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[HEADER:%.*]]
 ; CHECK:       header:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_INC:%.*]], [[HEADER]] ]
-; CHECK-NEXT:    [[IV2:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[IV2_INC:%.*]], [[HEADER]] ]
 ; CHECK-NEXT:    [[IV_INC]] = add i32 [[IV]], 1
-; CHECK-NEXT:    [[IV2_INC]] = add i32 [[IV2]], 1
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[IV]], [[N:%.*]]
 ; CHECK-NEXT:    br i1 [[CMP]], label [[EXIT:%.*]], label [[HEADER]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret i32 [[IV]]
 ;
 entry:
   br label %header
 

 
 ; Two assumes case.
 define i32 @test4(i32 %N) nounwind {
 ; CHECK-LABEL: @test4(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[HEADER:%.*]]
 ; CHECK:       header:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_INC:%.*]], [[HEADER]] ]
-; CHECK-NEXT:    [[IV2:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[IV2_INC:%.*]], [[HEADER]] ]
 ; CHECK-NEXT:    [[IV_INC]] = add i32 [[IV]], 1
-; CHECK-NEXT:    [[IV2_INC]] = add i32 [[IV2]], 1
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[IV]], [[N:%.*]]
 ; CHECK-NEXT:    br i1 [[CMP]], label [[EXIT:%.*]], label [[HEADER]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret i32 [[IV]]
 ;
 entry:
   br label %header