[InstCombine] Remove trivially empty ranges from end

[nikic]

Summary

InstCombine removes pairs of start+end intrinsics that don't have anything in between them. Currently this is done by starting at the start intrinsic and scanning forwards. This patch changes it to start at the end intrinsic and scan backwards.

The motivation here is as follows: When we process the start intrinsic, we have not yet looked at the following instructions, which may still get folded/removed. If they do, we will only be able to remove the start/end pair on the next iteration. When we process the end intrinsic, all the instructions before it have already been visited, and we don't run into this problem.

The highlighted test case drops from 4 to 2 iterations, because we can pick up all four start/end pairs in one pass, instead of doing one on each iteration.

[nikic]

Handle interleaving of start/end intrinsics with different args better. This reduces iterations on the lifetime.ll test.

[grandinj]

Nice. Makes me wonder what other loops in clang would work better backwards :-)

[spatel]

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

1482

Add a comment to explain why we're using the end instruction and reverse_iterator (can copy/adapt text from this patch description).

1488–1489

Is there a logic change from 'if &&' to 'if, if ...continue'? If so, that deserves a code comment.

If it's just a matter of taste, it would be better to make that + a partial function signature change as a preliminary NFC commit. (Trying to limit patch risk here because I'm not very familiar with these transforms.)

[nikic]

Add comments.

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

1488–1489

There is a logic change: This skips start intrinsics that don't pair with the end intrinsic (I've added a comment to that effect below).

This doesn't affect the final behavior (due to the existing skipping for the end intrinsic), but avoids doing extra iterations, for example:

start(0) <- erase
start(1) <- skip
end(0) <- I
end(1)

Without this change, we'd not do anything for end(0), but then

start(0)
start(1) <- erase
end(0) <- skip
end(1) <- I

and would collect end(0) on the next InstCombine iteration.

[spatel]

LGTM

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

static bool haveSameOperands(const IntrinsicInst &I, const IntrinsicInst &E,
   return true;
 }
 
 // Remove trivially empty start/end intrinsic ranges, i.e. a start
 // immediately followed by an end (ignoring debuginfo or other
 // start/end intrinsics in between). As this handles only the most trivial
 // cases, tracking the nesting level is not needed:
 //
-//   call @llvm.foo.start(i1 0) ; &I
 //   call @llvm.foo.start(i1 0)
-//   call @llvm.foo.end(i1 0) ; This one will not be skipped: it will be removed
+//   call @llvm.foo.start(i1 0) ; This one won't be skipped: it will be removed
 //   call @llvm.foo.end(i1 0)
-static bool removeTriviallyEmptyRange(IntrinsicInst &I, unsigned StartID,
-                                      unsigned EndID, InstCombiner &IC) {
-  assert(I.getIntrinsicID() == StartID &&
-         "Start intrinsic does not have expected ID");
-  BasicBlock::iterator BI(I), BE(I.getParent()->end());
+//   call @llvm.foo.end(i1 0) ; &I
+static bool removeTriviallyEmptyRange(
+    IntrinsicInst &EndI, InstCombiner &IC,
+    std::function<bool(const IntrinsicInst &)> IsStart) {
+  BasicBlock::reverse_iterator BI(EndI), BE(EndI.getParent()->rend());
   for (++BI; BI != BE; ++BI) {
-    if (auto *E = dyn_cast<IntrinsicInst>(BI)) {
-      if (isa<DbgInfoIntrinsic>(E) || E->getIntrinsicID() == StartID)
+    if (auto *I = dyn_cast<IntrinsicInst>(&*BI)) {
+      if (isa<DbgInfoIntrinsic>(I) ||
+          I->getIntrinsicID() == EndI.getIntrinsicID())
         continue;
-      if (E->getIntrinsicID() == EndID &&
-          haveSameOperands(I, *E, E->getNumArgOperands())) {
-        IC.eraseInstFromFunction(*E);
-        IC.eraseInstFromFunction(I);
+      if (IsStart(*I) && haveSameOperands(EndI, *I, EndI.getNumArgOperands())) {
+        IC.eraseInstFromFunction(*I);
+        IC.eraseInstFromFunction(EndI);
         return true;
       }
     }
     break;
   }
 
   return false;
 }
case SPC_Reciprocal:
     // Simplify reciprocal.
     return BinaryOperator::Create(
         Instruction::FDiv, ConstantFP::get(II->getArgOperand(0)->getType(), 1),
         II->getArgOperand(0), II->getName());
   }
   llvm_unreachable("All SpecialCase enumerators should be handled in switch.");
 }
 
-Instruction *InstCombiner::visitVAStartInst(VAStartInst &I) {
-  removeTriviallyEmptyRange(I, Intrinsic::vastart, Intrinsic::vaend, *this);
-  return nullptr;
-}
-
-Instruction *InstCombiner::visitVACopyInst(VACopyInst &I) {
-  removeTriviallyEmptyRange(I, Intrinsic::vacopy, Intrinsic::vaend, *this);
+Instruction *InstCombiner::visitVAEndInst(VAEndInst &I) {
+  removeTriviallyEmptyRange(I, *this, [](const IntrinsicInst &I) {
+    return I.getIntrinsicID() == Intrinsic::vastart ||
+           I.getIntrinsicID() == Intrinsic::vacopy;
+  });
   return nullptr;
 }
 
 static Instruction *canonicalizeConstantArg0ToArg1(CallInst &Call) {
   assert(Call.getNumArgOperands() > 1 && "Need at least 2 args to swap");
   Value *Arg0 = Call.getArgOperand(0), *Arg1 = Call.getArgOperand(1);
   if (isa<Constant>(Arg0) && !isa<Constant>(Arg1)) {
     Call.setArgOperand(0, Arg1);
case Intrinsic::stackrestore: {
 
     // If the stack restore is in a return, resume, or unwind block and if there
     // are no allocas or calls between the restore and the return, nuke the
     // restore.
     if (!CannotRemove && (isa<ReturnInst>(TI) || isa<ResumeInst>(TI)))
       return eraseInstFromFunction(CI);
     break;
   }
-  case Intrinsic::lifetime_start:
+  case Intrinsic::lifetime_end:
     // Asan needs to poison memory to detect invalid access which is possible
     // even for empty lifetime range.
     if (II->getFunction()->hasFnAttribute(Attribute::SanitizeAddress) ||
         II->getFunction()->hasFnAttribute(Attribute::SanitizeMemory) ||
         II->getFunction()->hasFnAttribute(Attribute::SanitizeHWAddress))
       break;
 
-    if (removeTriviallyEmptyRange(*II, Intrinsic::lifetime_start,
-                                  Intrinsic::lifetime_end, *this))
+    if (removeTriviallyEmptyRange(*II, *this, [](const IntrinsicInst &I) {
+          return I.getIntrinsicID() == Intrinsic::lifetime_start;
+        }))
       return nullptr;
     break;
   case Intrinsic::assume: {
     Value *IIOperand = II->getArgOperand(0);
     // Remove an assume if it is followed by an identical assume.
     // TODO: Do we need this? Unless there are conflicting assumptions, the
     // computeKnownBits(IIOperand) below here eliminates redundant assumes.
     Instruction *Next = II->getNextNonDebugInstruction();

llvm/lib/Transforms/InstCombine/InstCombineInternal.h

public:
   Instruction *visitSwitchInst(SwitchInst &SI);
   Instruction *visitReturnInst(ReturnInst &RI);
   Instruction *visitInsertValueInst(InsertValueInst &IV);
   Instruction *visitInsertElementInst(InsertElementInst &IE);
   Instruction *visitExtractElementInst(ExtractElementInst &EI);
   Instruction *visitShuffleVectorInst(ShuffleVectorInst &SVI);
   Instruction *visitExtractValueInst(ExtractValueInst &EV);
   Instruction *visitLandingPadInst(LandingPadInst &LI);
-  Instruction *visitVAStartInst(VAStartInst &I);
-  Instruction *visitVACopyInst(VACopyInst &I);
+  Instruction *visitVAEndInst(VAEndInst &I);
   Instruction *visitFreeze(FreezeInst &I);
 
   /// Specify what to return for unhandled instructions.
   Instruction *visitInstruction(Instruction &I) { return nullptr; }
 
   /// True when DB dominates all uses of DI except UI.
   /// UI must be in the same block as DI.
   /// The routine checks that the DI parent and DB are different.

llvm/test/Transforms/InstCombine/vararg.ll

-; RUN: opt < %s -instcombine -S | FileCheck %s
+; RUN: opt < %s -instcombine -instcombine-infinite-loop-threshold=2 -S | FileCheck %s
 
 %struct.__va_list = type { i8*, i8*, i8*, i32, i32 }
 
 declare void @llvm.lifetime.start.p0i8(i64, i8* nocapture)
 declare void @llvm.lifetime.end.p0i8(i64, i8* nocapture)
 declare void @llvm.va_start(i8*)
 declare void @llvm.va_end(i8*)
 declare void @llvm.va_copy(i8*, i8*)