[InstCombine] Remove trivially empty lifetime start/end ranges.

[aadg]

Summary

Some passes may open up opportunities for optimizations, leaving empty
lifetime start/end ranges. For example, with the following code:

void foo(char *, char *);
void bar(int Size, bool flag) {
  for (int i = 0; i < Size; ++i) {
    char text[1];
    char buff[1];
    if (flag)
      foo(text, buff); // BBFoo
  }
}

the loop unswitch pass will create 2 versions of the loop, one with
flag==true, and the other one with flag==false, but always leaving
the BBFoo basic block, with lifetime ranges covering the scope of the for
loop. Simplify CFG will then remove BBFoo in the case where flag==false,
but will leave the lifetime markers.

This patch teaches InstCombine to remove trivially empty lifetime marker
ranges, that is ranges ending right after they were started (ignoring
debug info in the range).

This fixes PR24598: excessive compile time after r234581.

[manmanren]

LGTM otherwise

test/Transforms/InstCombine/lifetime.ll

2 ↗

(On Diff #36141)

It is probably better to just check the 6 occurrences with a single RUN command.

[chandlerc]

LGTM with the fixes suggested inline.

I wonder if we should do something more aggressive to kill pointless lifetime ranges though. This handles the trivial case but non-trivial cases might be very interesting.

For example, even non-strictly-nested ranges won't be caught by this.

lib/Transforms/InstCombine/InstCombineCalls.cpp

1398 ↗

(On Diff #36141)

These should be loop variables.

test/Transforms/InstCombine/lifetime.ll

2 ↗

(On Diff #36141)

This already is checked by the FileCheck line. I think this can just be deleted.

[aadg]

I intended to catch another trivially empty ranges in a follow-up patch: the non strictly nested ones you refer to. The goal was to quickly fix an issue (PR24598), then improve the lifetime markers cleanup.

I think we should teach this cleanup to address less trivial cases, especially the one where the start dominates the end (garanteed by design) and the end post-dominate the start and the alloca is not used in between. I think this would catch lots of cases. But that's for another patch.

And the loop unroller probably needs to learn how not to mess to badly with the lifetime markers :).

Thanks for the reviews !

I'll fix and push this patch.

lib/Transforms/InstCombine/InstCombineCalls.cpp

1398 ↗

(On Diff #36141)

I agree on the principle, but BI needs to be incremented before entering the loop.

test/Transforms/InstCombine/lifetime.ll

2 ↗

(On Diff #36141)

Those 2 RUN lines were a very clumsy way of making sure the "if" basic block has been emptied, and the "else" was not modified. One RUN line is enough indeed, and I will add 2 checks:

CHECK: if:
CHECK-NEXT: br label %fin

llvm/trunk/lib/Transforms/InstCombine/InstCombineCalls.cpp

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: {
+    // Remove trivially empty lifetime_start/end ranges, i.e. a start
+    // immediately followed by an end (ignoring debuginfo or other
+    // lifetime markers in between).
+    BasicBlock::iterator BI = II, BE = II->getParent()->end();
+    for (++BI; BI != BE; ++BI) {
+      if (IntrinsicInst *LTE = dyn_cast<IntrinsicInst>(BI)) {
+        if (isa<DbgInfoIntrinsic>(LTE) ||
+            LTE->getIntrinsicID() == Intrinsic::lifetime_start)
+          continue;
+        if (LTE->getIntrinsicID() == Intrinsic::lifetime_end) {
+          if (II->getOperand(0) == LTE->getOperand(0) &&
+              II->getOperand(1) == LTE->getOperand(1)) {
+            EraseInstFromFunction(*LTE);
+            return EraseInstFromFunction(*II);
+          }
+          continue;
+        }
+      }
+      break;
+    }
+    break;
+  }
   case Intrinsic::assume: {
     // Canonicalize assume(a && b) -> assume(a); assume(b);
     // Note: New assumption intrinsics created here are registered by
     // the InstCombineIRInserter object.
     Value *IIOperand = II->getArgOperand(0), *A, *B,
           *AssumeIntrinsic = II->getCalledValue();
     if (match(IIOperand, m_And(m_Value(A), m_Value(B)))) {
       Builder->CreateCall(AssumeIntrinsic, A, II->getName());

llvm/trunk/test/Transforms/InstCombine/lifetime.ll

+; RUN: opt < %s -instcombine -S | FileCheck %s
+
+declare void @llvm.dbg.declare(metadata, metadata, metadata)
+declare void @llvm.lifetime.start(i64, i8* nocapture)
+declare void @llvm.lifetime.end(i64, i8* nocapture)
+declare void @foo(i8* nocapture, i8* nocapture)
+
+define void @bar(i1 %flag) {
+entry:
+; CHECK-LABEL: @bar(
+; CHECK: %[[T:[^ ]+]] = getelementptr inbounds [1 x i8], [1 x i8]* %text
+; CHECK: %[[B:[^ ]+]] = getelementptr inbounds [1 x i8], [1 x i8]* %buff
+; CHECK: if:
+; CHECK-NEXT: br label %bb2
+; CHECK: bb2:
+; CHECK-NEXT: br label %bb3
+; CHECK: bb3:
+; CHECK-NEXT: call void @llvm.dbg.declare
+; CHECK-NEXT: br label %fin
+; CHECK: call void @llvm.lifetime.start(i64 1, i8* %[[T]])
+; CHECK-NEXT: call void @llvm.lifetime.start(i64 1, i8* %[[B]])
+; CHECK-NEXT: call void @foo(i8* %[[B]], i8* %[[T]])
+; CHECK-NEXT: call void @llvm.lifetime.end(i64 1, i8* %[[B]])
+; CHECK-NEXT: call void @llvm.lifetime.end(i64 1, i8* %[[T]])
+  %text = alloca [1 x i8], align 1
+  %buff = alloca [1 x i8], align 1
+  %0 = getelementptr inbounds [1 x i8], [1 x i8]* %text, i64 0, i64 0
+  %1 = getelementptr inbounds [1 x i8], [1 x i8]* %buff, i64 0, i64 0
+  br i1 %flag, label %if, label %else
+
+if:
+  call void @llvm.lifetime.start(i64 1, i8* %0)
+  call void @llvm.lifetime.start(i64 1, i8* %1)
+  call void @llvm.lifetime.end(i64 1, i8* %1)
+  call void @llvm.lifetime.end(i64 1, i8* %0)
+  br label %bb2
+
+bb2:
+  call void @llvm.lifetime.start(i64 1, i8* %0)
+  call void @llvm.lifetime.start(i64 1, i8* %1)
+  call void @llvm.lifetime.end(i64 1, i8* %0)
+  call void @llvm.lifetime.end(i64 1, i8* %1)
+  br label %bb3
+
+bb3:
+  call void @llvm.lifetime.start(i64 1, i8* %0)
+  call void @llvm.dbg.declare(metadata [1 x i8]* %text, metadata !14, metadata !25), !dbg !26
+  call void @llvm.lifetime.end(i64 1, i8* %0)
+  br label %fin
+
+else:
+  call void @llvm.lifetime.start(i64 1, i8* %0)
+  call void @llvm.lifetime.start(i64 1, i8* %1)
+  call void @foo(i8* %1, i8* %0)
+  call void @llvm.lifetime.end(i64 1, i8* %1)
+  call void @llvm.lifetime.end(i64 1, i8* %0)
+  br  label %fin
+
+fin:
+  ret void
+}
+
+!llvm.dbg.cu = !{!0}
+!llvm.module.flags = !{!22, !23}
+!llvm.ident = !{!24}
+
+!0 = distinct !DICompileUnit(language: DW_LANG_C_plus_plus, file: !1, producer: "clang version 3.8.0 (trunk 248826) (llvm/trunk 248827)", isOptimized: true, runtimeVersion: 0, emissionKind: 1, enums: !2, subprograms: !3)
+!1 = !DIFile(filename: "test.cpp", directory: "/home/user")
+!2 = !{}
+!3 = !{!4}
+!4 = distinct !DISubprogram(name: "bar", linkageName: "bar", scope: !1, file: !1, line: 2, type: !5, isLocal: false, isDefinition: true, scopeLine: 2, flags: DIFlagPrototyped, isOptimized: true, function: void (i1)* @bar, variables: !8)
+!5 = !DISubroutineType(types: !6)
+!6 = !{null, !7}
+!7 = !DIBasicType(name: "bool", size: 8, align: 8, encoding: DW_ATE_boolean)
+!8 = !{!9, !11, !12, !14, !21}
+!9 = !DILocalVariable(name: "Size", arg: 1, scope: !4, file: !1, line: 2, type: !10)
+!10 = !DIBasicType(name: "int", size: 32, align: 32, encoding: DW_ATE_signed)
+!11 = !DILocalVariable(name: "flag", arg: 2, scope: !4, file: !1, line: 2, type: !7)
+!12 = !DILocalVariable(name: "i", scope: !13, file: !1, line: 3, type: !10)
+!13 = distinct !DILexicalBlock(scope: !4, file: !1, line: 3, column: 3)
+!14 = !DILocalVariable(name: "text", scope: !15, file: !1, line: 4, type: !17)
+!15 = distinct !DILexicalBlock(scope: !16, file: !1, line: 3, column: 30)
+!16 = distinct !DILexicalBlock(scope: !13, file: !1, line: 3, column: 3)
+!17 = !DICompositeType(tag: DW_TAG_array_type, baseType: !18, size: 8, align: 8, elements: !19)
+!18 = !DIBasicType(name: "char", size: 8, align: 8, encoding: DW_ATE_signed_char)
+!19 = !{!20}
+!20 = !DISubrange(count: 1)
+!21 = !DILocalVariable(name: "buff", scope: !15, file: !1, line: 5, type: !17)
+!22 = !{i32 2, !"Dwarf Version", i32 4}
+!23 = !{i32 2, !"Debug Info Version", i32 3}
+!24 = !{!"clang version 3.8.0 (trunk 248826) (llvm/trunk 248827)"}
+!25 = !DIExpression()
+!26 = !DILocation(line: 4, column: 10, scope: !15)