[MachineOutliner] Fix liveness computing.

[yroux]

Summary

There are targets, such as ARM, where if-conversion can insert a predicated terminator when merging blocks. On ARM this instruction (BX_RET) doesn't contain the information that it uses the link register (this is handled by addLiveOuts which will add calle saved regtisters if needed), thus the current implementation might miss this link register usage wrongly insert an outlined call without saving it.

[efriedma]

I'm not really happy with this approach; if LiveRegUnits isn't producing correct results, we should fix it, not try to hack around it.

Maybe we should revive D40061...

[samparker]

I guess I just don't understand why the BX_RET wouldn't be marked with using the link register in the first place?

[yroux]

In D83313#2137190, @efriedma wrote:

I'm not really happy with this approach; if LiveRegUnits isn't producing correct results, we should fix it, not try to hack around it.

Maybe we should revive D40061...

My attempt wasn't to hack around it, but to calculate the LiveRegUnit accurately ;-) Sorry I wasn't working on LLVM when you proposed D40061, but it is indeed a better approach, can you re-open it ?

[yroux]

In D83313#2138334, @samparker wrote:

I guess I just don't understand why the BX_RET wouldn't be marked with using the link register in the first place?

Yes that's confusing and the first thing I tried was to add a USES = [LR] to its definition, but then LR will need to be livein everywhere my understanding is that it is handled as needed by prolog/epilog emission

[samparker]

@efriedma Was there much more to do on your original patch?

[efriedma]

I think the remaining issue was that IfConversion was producing messy code in some cases. We would stick a conditional return and an unconditional branch in the same block, and the ARM analyzeBranch couldn't understand that. That led to some weird consequences for block layout. So probably not too much more work. I think I just got distracted from it because it wasn't actually solving any practical issue when I wrote it.

[samparker]

@efriedma Would you have time/desire to look at the patch again? Or would you mind someone else taking a look? I'd really like to get the outliner enablement unblocked.

[efriedma]

I guess there are three possible paths forward here:

1. Someone revives D40061, so it's impossible to have a terminator in the middle of a block.
2. We fix LiveRegUnits to handle this.
3. We accumulate technical debt by repeatedly fixing the same issue in every user of LiveRegUnits.

It should be obvious why (3) isn't appealing.

I don't see any problem with the logic in this patch, in the sense that the result of the analysis should correctly reflect reality.

If someone else wants to take over D40061, I'd be fine with that; I probably won't have time to work on it in the next few weeks.

[samparker]

Okay, thanks - I will take a look at it then. It appears that the lingering unconditional branches, that you were concerned about, are no longer there. It looks like most of the work will be updating all the MIR tests...

[yroux]

Issue fixed by D40061

llvm/include/llvm/CodeGen/MachineOutliner.h

void initLRU(const TargetRegisterInfo &TRI) {
     // Only initialize once.
     if (LRUWasSet)
       return;
     LRUWasSet = true;
     LRU.init(TRI);
     LRU.addLiveOuts(*MBB);
 
     // Compute liveness from the end of the block up to the beginning of the
-    // outlining candidate.
+    // outlining candidate.  On some targets (such as ARM) If-conversion might
+    // have introduced predicated terminators when merging blocks, in such cases
+    // block's liveouts needs to be added again.
     std::for_each(MBB->rbegin(), (MachineBasicBlock::reverse_iterator)front(),
-                  [this](MachineInstr &MI) { LRU.stepBackward(MI); });
+                  [this](MachineInstr &MI) {
+                    if (MI.isTerminator())
+                      LRU.addLiveOuts(*MBB);
+                    LRU.stepBackward(MI);
+                  });
 
     // Walk over the sequence itself and figure out which registers were used
     // in the sequence.
     UsedInSequence.init(TRI);
     std::for_each(front(), std::next(back()),
                   [this](MachineInstr &MI) { UsedInSequence.accumulate(MI); });
   }
 };

llvm/test/CodeGen/ARM/machine-outliner-liveness.ll

+; NOTE: Assertions have been autogenerated by utils/update_mir_test_checks.py
+; RUN: llc -enable-machine-outliner -verify-machineinstrs -mtriple=armv8-- \
+; RUN: --stop-after=machine-outliner < %s | FileCheck %s
+
+target triple = "armv8-unknown-linux-gnueabihf"
+
+%"mtype" = type { i32, i8*, i32 }
+
+; Function Attrs: nounwind
+declare i32 @foo(i8*, i32) local_unnamed_addr #0
+
+; Function Attrs: noreturn nounwind
+declare void @bar() local_unnamed_addr #1
+
+; Function Attrs: nounwind
+define %"mtype"* @f1(%"mtype"* readonly returned %this) unnamed_addr #0 align 2 {
+  ; CHECK-LABEL: name: f1
+  ; CHECK: bb.0.entry:
+  ; CHECK:   liveins: $r0, $r4, $lr
+  ; CHECK:   BL @OUTLINED_FUNCTION_0
+  ; CHECK:   Bcc %bb.2, 0 /* CC::eq */, killed $cpsr
+  ; CHECK: bb.1.if.then:
+  ; CHECK:   liveins: $r0, $r4
+  ; CHECK:   BL @OUTLINED_FUNCTION_2
+  ; CHECK: bb.2.if.end:
+  ; CHECK:   liveins: $r4
+  ; CHECK:   TAILJMPd @OUTLINED_FUNCTION_1
+entry:
+  %Mapping = getelementptr inbounds %"mtype", %"mtype"* %this, i32 0, i32 1
+  %0 = load i8*, i8** %Mapping, align 4
+  %tobool = icmp eq i8* %0, null
+  br i1 %tobool, label %if.end, label %if.then
+
+if.then:                                          ; preds = %entry
+  %Size = getelementptr inbounds %"mtype", %"mtype"* %this, i32 0, i32 0
+  %1 = load i32, i32* %Size, align 4
+  %call = tail call i32 @foo(i8* nonnull %0, i32 %1) #25
+  br label %if.end
+
+if.end:                                           ; preds = %entry, %if.then
+  ret %"mtype"* %this
+}
+
+; Function Attrs: nounwind
+define %"mtype"* @f2(%"mtype"* readonly returned %this) unnamed_addr #0 align 2 {
+  ; CHECK-LABEL: name: f2
+  ; CHECK: bb.0.entry:
+  ; CHECK:   liveins: $r0, $r4, $lr
+  ; CHECK:   BL @OUTLINED_FUNCTION_0
+  ; CHECK:   Bcc %bb.2, 0 /* CC::eq */, killed $cpsr
+  ; CHECK: bb.1.if.then:
+  ; CHECK:   liveins: $r0, $r4
+  ; CHECK:   BL @OUTLINED_FUNCTION_2
+  ; CHECK: bb.2.if.end:
+  ; CHECK:   liveins: $r4
+  ; CHECK:   TAILJMPd @OUTLINED_FUNCTION_1
+entry:
+  %Mapping = getelementptr inbounds %"mtype", %"mtype"* %this, i32 0, i32 1
+  %0 = load i8*, i8** %Mapping, align 4
+  %tobool = icmp eq i8* %0, null
+  br i1 %tobool, label %if.end, label %if.then
+
+if.then:                                          ; preds = %entry
+  %Size = getelementptr inbounds %"mtype", %"mtype"* %this, i32 0, i32 0
+  %1 = load i32, i32* %Size, align 4
+  %call = tail call i32 @foo(i8* nonnull %0, i32 %1) #25
+  br label %if.end
+
+if.end:                                           ; preds = %entry, %if.then
+  ret %"mtype"* %this
+}
+
+; Function Attrs: nounwind
+define %"mtype"* @f3(%"mtype"* readonly returned %this) unnamed_addr #0 align 2 {
+  ; CHECK-LABEL: name: f3
+  ; CHECK: bb.0.entry:
+  ; CHECK:   liveins: $r0, $r4, $lr
+  ; CHECK:   BL @OUTLINED_FUNCTION_0
+  ; CHECK:   Bcc %bb.2, 0 /* CC::eq */, killed $cpsr
+  ; CHECK: bb.1.if.then:
+  ; CHECK:   liveins: $r0, $r4
+  ; CHECK:   BL @OUTLINED_FUNCTION_2
+  ; CHECK: bb.2.if.end:
+  ; CHECK:   liveins: $r4
+  ; CHECK:   TAILJMPd @OUTLINED_FUNCTION_1
+entry:
+  %Mapping = getelementptr inbounds %"mtype", %"mtype"* %this, i32 0, i32 1
+  %0 = load i8*, i8** %Mapping, align 4
+  %tobool = icmp eq i8* %0, null
+  br i1 %tobool, label %if.end, label %if.then
+
+if.then:                                          ; preds = %entry
+  %Size = getelementptr inbounds %"mtype", %"mtype"* %this, i32 0, i32 0
+  %1 = load i32, i32* %Size, align 4
+  %call = tail call i32 @foo(i8* nonnull %0, i32 %1) #25
+  br label %if.end
+
+if.end:                                           ; preds = %entry, %if.then
+  ret %"mtype"* %this
+}
+
+; Function Attrs: nounwind
+define i8* @f4(%"mtype"* nocapture readonly %this) local_unnamed_addr #0 align 2 {
+  ; CHECK-LABEL: name: f4
+  ; CHECK: bb.0.entry:
+  ; CHECK:   liveins: $r0
+  ; CHECK:   renamable $r0 = LDRi12 killed renamable $r0, 4, 14 /* CC::al */, $noreg
+  ; CHECK:   CMPri renamable $r0, 0, 14 /* CC::al */, $noreg, implicit-def $cpsr
+  ; CHECK:   BX_RET 1 /* CC::ne */, killed $cpsr, implicit killed $r0
+  ; CHECK:   BL @bar, csr_aapcs, implicit-def dead $lr, implicit $sp, implicit-def $sp
+entry:
+  %Mapping = getelementptr inbounds %"mtype", %"mtype"* %this, i32 0, i32 1
+  %0 = load i8*, i8** %Mapping, align 4
+  %tobool = icmp eq i8* %0, null
+  br i1 %tobool, label %cond.false, label %cond.end
+
+cond.false:                                       ; preds = %entry
+  tail call void @bar()
+  unreachable
+
+cond.end:                                         ; preds = %entry
+  ret i8* %0
+}
+
+; Function Attrs: nounwind
+define i8* @f5(%"mtype"* nocapture readonly %this) local_unnamed_addr #0 align 2 {
+  ; CHECK-LABEL: name: f5
+  ; CHECK: bb.0.entry:
+  ; CHECK:   liveins: $r0
+  ; CHECK:   renamable $r0 = LDRi12 killed renamable $r0, 4, 14 /* CC::al */, $noreg
+  ; CHECK:   CMPri renamable $r0, 0, 14 /* CC::al */, $noreg, implicit-def $cpsr
+  ; CHECK:   BX_RET 1 /* CC::ne */, killed $cpsr, implicit killed $r0
+  ; CHECK:   BL @bar, csr_aapcs, implicit-def dead $lr, implicit $sp, implicit-def $sp
+entry:
+  %Mapping = getelementptr inbounds %"mtype", %"mtype"* %this, i32 0, i32 1
+  %0 = load i8*, i8** %Mapping, align 4
+  %tobool = icmp eq i8* %0, null
+  br i1 %tobool, label %cond.false, label %cond.end
+
+cond.false:                                       ; preds = %entry
+  tail call void @bar()
+  unreachable
+
+cond.end:                                         ; preds = %entry
+  ret i8* %0
+}
+
+attributes #0 = { nounwind "target-cpu"="generic" "target-features"="+armv8-a,-thumb-mode" }
+attributes #1 = { noreturn nounwind "target-cpu"="generic" "target-features"="+armv8-a,-thumb-mode"  }
+attributes #2 = { noreturn nounwind }