[LoopRotate] Fix lifetime handling.

[fhahn]

Summary

Currently LoopRotate ends up duplicating lifetime starts/ends in the
preheader, which creates invalid lifetimes.

This patch adds support for extending the lifetimes when hoisting
instructions: lifetime.start gets hoisted to the preheader and
lifetime.end gets sunk to the exit block. This extends the lifetime of
the memory location.

[fhahn]

I think this fixes a longstanding bug report PR15376.

[fhahn]

Move the lifetime handling before cloning the instruction. The cases where we delete the clone do not apply to lifetime intrinsics anyways, so there is no need to clone it in that case.

[efriedma]

Duplicating lifetime.start and lifetime.end intrinsics isn't fundamentally a problem, as long as they stay correctly paired. What is this supposed to solve?

[fhahn]

In D52307#1240955, @efriedma wrote:

Duplicating lifetime.start and lifetime.end intrinsics isn't fundamentally a problem, as long as they stay correctly paired. What is this supposed to solve?

My understanding from the LangRef was that having 2 set of lifetimes for the same memory location may lead to unexpected behaviour. For lifetime.start, the semantics are described as

This intrinsic indicates that before this point in the code, the value of the memory pointed to by ptr is dead. This means that it is known to never be used and has an undefined value. A load from the pointer that precedes this intrinsic can be replaced with 'undef'.

So if we duplicate lifetimes and say we have

  %tmp = bitcast i32* %m to i8*
  call void @llvm.lifetime.start.p0i8(i64 4, i8* nonnull %tmp)
  %v1 = load i32* %m
  call void @llvm.lifetime.end.p0i8(i64 4, i8* nonnull %tmp)
  br label %bb2
.....
bb3:
  call void @llvm.lifetime.start.p0i8(i64 4, i8* nonnull %tmp)
  %v1 = load i32* %m
  call void @llvm.lifetime.end.p0i8(i64 4, i8* nonnull %tmp)
  br label %exit

Now when visiting bb3, we see the lifetime.start and can replace any loads that precedes it (%v1) with undef. lifetime.end says something similar about stores after lifetime.end. Maybe I am missing something from the LangRef?

This seems to be causing a runtime failure in our internal benchmarks.

[efriedma]

An alloca can have multiple associated lifetime start/ends. Inlining routinely generates code like that, unrolling generates code like that, etc. And stack coloring knows how to handle such code.

Granted, the way the intrinsic is specified makes everything related to it pretty confusing.

[fhahn]

In D52307#1241165, @efriedma wrote:

An alloca can have multiple associated lifetime start/ends. Inlining routinely generates code like that, unrolling generates code like that, etc. And stack coloring knows how to handle such code.

Granted, the way the intrinsic is specified makes everything related to it pretty confusing.

Right! If everything is working as intended currently, I'd be happy to clarify the LangRef and track down where things go wrong with those lifetimes later.

I guess both interpretations of the lifetime behavior make sense, what's in the LangRef currently seems to make using the info provided by the intrinsics easier to use (no need to check for other lifetime markers to the same location), having multiple distinct ranges for the same location increases precision.

[mkazantsev]

Sorry, I don't think I can give any useful input on that.

[fhahn]

I won't be able to follow up on this in the near future unfortunately.

lib/Transforms/Utils/LoopRotationUtils.cpp

while (I != E) {
     // memory (without proving that the loop doesn't write).
     if (L->hasLoopInvariantOperands(Inst) && !Inst->mayReadFromMemory() &&
         !Inst->mayWriteToMemory() && !Inst->isTerminator() &&
         !isa<DbgInfoIntrinsic>(Inst) && !isa<AllocaInst>(Inst)) {
       Inst->moveBefore(LoopEntryBranch);
       continue;
     }
 
+    // Duplicating lifetimes will create invalid lifetimes. Instead we can
+    // extend the lifetime of the memory location by hoisting the start to
+    // the loop entry and sinking ends to the loop exit.
+    if (auto *IntrInst = dyn_cast<IntrinsicInst>(Inst)) {
+      if (IntrInst->getIntrinsicID() == Intrinsic::lifetime_start) {
+        Inst->moveBefore(LoopEntryBranch);
+        continue;
+      } else if (IntrInst->getIntrinsicID() == Intrinsic::lifetime_end) {
+        Inst->moveBefore(Exit->getFirstNonPHI());
+        continue;
+      }
+    }
+
     // Otherwise, create a duplicate of the instruction.
     Instruction *C = Inst->clone();
 
     // Eagerly remap the operands of the instruction.
     RemapInstruction(C, ValueMap,
                      RF_NoModuleLevelChanges | RF_IgnoreMissingLocals);
 
     // Avoid inserting the same intrinsic twice.

test/Transforms/LoopRotate/lifetimes.ll

+; RUN: opt -S -loop-rotate < %s -verify-loop-info -verify-dom-info | FileCheck %s
+
+; Make sure we extend lifetimes properly.
+
+; CHECK-LABEL: @test(
+; CHECK-LABEL: entry:
+; CHECK:         call void @llvm.lifetime.start.p0i8(i64 4, i8* nonnull %tmp)
+
+; CHECK-LABEL: for.body.lr.ph:
+; CHECK-NOT:     call void @llvm.lifetime.start.p0i8
+; CHECK-NOT:     call void @llvm.lifetime.end.p0i8
+
+; CHECK-LABEL: return.loopexit:
+; CHECK-NEXT:    call void @llvm.lifetime.end.p0i8(i64 4, i8* nonnull %tmp)
+
+define void @test(i32 %x) nounwind {
+entry:
+  %m = alloca i32, align 4
+  br label %for.cond
+
+for.cond:                                         ; preds = %if.end, %entry
+  %i.0 = phi i32 [ 0, %entry ], [ %inc, %if.end ]
+  %cmp = icmp eq i32 %i.0, %x
+  %tmp = bitcast i32* %m to i8*
+  call void @llvm.lifetime.start.p0i8(i64 4, i8* nonnull %tmp)
+  store i32 1, i32* %m
+  call void @llvm.lifetime.end.p0i8(i64 4, i8* nonnull %tmp)
+  br i1 %cmp, label %return.loopexit, label %for.body
+
+for.body:                                         ; preds = %for.cond
+  %call = tail call i32 @foo(i32 %i.0)
+  %tobool = icmp eq i32 %call, 0
+  br i1 %tobool, label %if.end, label %a
+
+if.end:                                           ; preds = %for.body
+  %inc = add i32 %i.0, 1
+  br label %for.cond
+
+a:                                                ; preds = %for.body
+  br label %return
+
+return.loopexit:                                  ; preds = %for.cond
+  br label %return
+
+return:                                           ; preds = %return.loopexit, %a
+  ret void
+}
+
+declare  void @llvm.lifetime.start.p0i8(i64, i8*)
+declare  void @llvm.lifetime.end.p0i8(i64, i8*)
+
+declare i32 @foo(i32)