Insert IMPLICIT_DEFS for undef uses in tail merging

[kparzysz]

Summary

Tail merging can convert an undef use into a normal one when creating a common tail. Doing so can make the register live out from a block which previously contained the undef use. To keep the liveness up-to-date, insert IMPLICIT_DEFs in such blocks when necessary.

[MatzeB]

lib/CodeGen/BranchFolding.cpp

385–398

I'm confused: Don't you need to compare the live-outs of Pred with the live-ins of NewDest? Adding the liveouts of Pred and stepping backwards over the instructions gives you the live-ins of Pred, but I don't see what they are good for.

I would have expected this to look like this:

PredLiveOuts.init(*TRI);
PrevLiveOuts.addLiveOutsNoPristines(*Pred);
// Add implicit defs for NewDest live-in values not available at end of Pred.
for (const MachineBasicBlock::RegisterMaskPair &LI : NewDest->liveins()) {
  // computeLiveIn() currently doesn't add partial live-ins so we are fine with an assert.
  assert(LI.LaneMask == LaneBitmask::getAll() && "found partial live-in");
  if (PredLiveOuts.available(*MRI, LI.PhysReg)) {
    BuildMI ...
  }
}

[kparzysz]

lib/CodeGen/BranchFolding.cpp

385–398

You're right, this won't work. Still, we need to traverse the block, and it will have to use stepForward. Consider this case:

MBB:
  liveins: R0
  R0<def,dead> = ... R0<kill>    ; stays in MBB
  ... = R0<undef>                ; goes into common tail, but no longer <undef>

We need to add R0<def> = IMPLICIT_DEF here.

We can't rely on addLiveOuts from LivePhysRegs, because NewDest->liveins() will (by definition) be a subset of Pred->addLiveOuts.

[kparzysz]

Changed how the liveness inconsistencies are detected. Added comments with explanations.

[kparzysz]

Remove an accidental change in BranchFolding.h.

[kparzysz]

Ping.

[kparzysz]

Ping.

[MatzeB]

lib/CodeGen/BranchFolding.cpp

385–398

We can't rely on addLiveOuts from LivePhysRegs, because NewDest->liveins() will (by definition) be a subset of Pred->addLiveOuts.

Fair point. This is trickier than it seemed at first. I'm still convinced though that it can be done, and I really want to avoid stepForward(). I'll have a shot at implementing it.

[MatzeB]

This should fix the problem without using stepForward: https://reviews.llvm.org/D37034

[kparzysz]

Replaced by D37034.

lib/CodeGen/BranchFolding.cpp

 #include "llvm/ADT/STLExtras.h"
 #include "llvm/CodeGen/Analysis.h"
 #include "llvm/CodeGen/MachineBasicBlock.h"
 #include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
 #include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/MachineInstr.h"
+#include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/MachineJumpTableInfo.h"
 #include "llvm/CodeGen/MachineLoopInfo.h"
 #include "llvm/CodeGen/MachineModuleInfo.h"
 #include "llvm/CodeGen/MachineOperand.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/TargetPassConfig.h"
 #include "llvm/IR/DebugInfoMetadata.h"
 #include "llvm/IR/DebugLoc.h"

 
 void BranchFolder::ReplaceTailWithBranchTo(MachineBasicBlock::iterator OldInst,
                                            MachineBasicBlock *NewDest) {
   TII->ReplaceTailWithBranchTo(OldInst, NewDest);
 
   if (UpdateLiveIns) {
     NewDest->clearLiveIns();
     computeLiveIns(LiveRegs, *MRI, *NewDest);
+
+    LivePhysRegs CalcLiveIns;
+    for (MachineBasicBlock *Pred : NewDest->predecessors()) {
+      // Check if all live-ins of NewDest are live-on-exit from Pred.
+      // If not, add an IMPLICIT_DEF.
+      // Normally, this should check if for each live-in to NewDest there
+      // exists a downward-exposed def in Pred. To avoid using stepForward
+      // in LivePhysRegs, scan the block backward instead, and then check
+      // if we would need to add a new live-in to Pred.
+      CalcLiveIns.init(*TRI);
+      CalcLiveIns.addLiveOutsNoPristines(*Pred);
+      for (const MachineInstr &MI : llvm::reverse(*Pred))
+        CalcLiveIns.stepBackward(MI);
+
+      LivePhysRegs LiveIns(*TRI);
+      LiveIns.addLiveIns(*Pred);
+      for (MCPhysReg R : CalcLiveIns) {
+        if (!LiveIns.available(*MRI, R))
+          continue;
+        MachineBasicBlock::iterator At = Pred->getFirstTerminator();
+        const DebugLoc &dl = Pred->findDebugLoc(At);
+        BuildMI(*Pred, At, dl, TII->get(TargetOpcode::IMPLICIT_DEF), R);
+      }
+    }
   }
 
   ++NumTailMerge;
 }
 
 MachineBasicBlock *BranchFolder::SplitMBBAt(MachineBasicBlock &CurMBB,
                                             MachineBasicBlock::iterator BBI1,
                                             const BasicBlock *BB) {

test/CodeGen/Hexagon/branchfolder-insert-impdef.mir

+# RUN: llc -march=hexagon -run-pass branch-folder %s -o - -verify-machineinstrs | FileCheck %s
+
+# Branch folding will perform tail merging of bb.1 and bb.2, and bb.2 will
+# become the common tail. The use of R0 in bb.2 is <undef> while the
+# corresponding use in bb.1 is not. The common tail will have the <undef>
+# flag removed, which will cause R0 to become a live-in to bb.2. The problem
+# is that R0 is not live-out from all predecessors of bb.2, namely is not
+# live-out from bb.0. To remedy that, the branch folder should add an
+# IMPLICIT_DEF to that block.
+
+# CHECK-LABEL: bb.0:
+# CHECK: %r0 = IMPLICIT_DEF
+# CHECK-LABEL: bb.1:
+# CHECK-LABEL: bb.2:
+# CHECK: liveins: %r0
+# CHECK: PS_storerhabs 0, %r0
+# CHECK: PS_jmpret
+
+---
+name: fred
+tracksRegLiveness: true
+
+body: |
+  bb.0:
+    successors: %bb.1, %bb.2
+      J2_jumpt undef %p0, %bb.2, implicit-def %pc
+      J2_jump %bb.1, implicit-def %pc
+
+  bb.1:
+    successors: %bb.3
+      %r0 = L2_loadruh_io undef %r1, 0
+      PS_storerhabs 0, killed %r0
+      J2_jump %bb.3, implicit-def %pc
+
+  bb.2:
+    successors: %bb.3
+      PS_storerhabs 0, undef %r0
+      J2_jump %bb.3, implicit-def %pc
+
+  bb.3:
+      PS_jmpret killed %r31, implicit-def %pc
+...
+

test/CodeGen/Hexagon/livephysregs-lane-masks2.mir

 # RUN: llc -march=hexagon -verify-machineinstrs -run-pass branch-folder -o - %s | FileCheck %s
 
 # CHECK-LABEL: name: fred
 
 --- |
   define void @fred() { ret void }
 
 ...
 ---
 
 name: fred
 tracksRegLiveness: true
 
 body: |
   bb.0:
-    liveins: %p2, %r0
+    liveins: %p0:0x1, %p2, %r0
     successors: %bb.1, %bb.2
         J2_jumpt killed %p2, %bb.1, implicit-def %pc
         J2_jump %bb.2, implicit-def %pc
 
   bb.1:
-    liveins: %r0, %r19
+    liveins: %p0:0x1, %r0, %r19
     successors: %bb.3
         %r2 = A2_tfrsi 4
         %r1 = COPY %r19
         %r0 = S2_asl_r_r killed %r0, killed %r2
         %r0 = A2_asrh killed %r0
         J2_jump %bb.3, implicit-def %pc
 
   bb.2:
-    liveins: %r0, %r18
+    liveins: %p0:0x1, %r0, %r18
     successors: %bb.3
         %r2 = A2_tfrsi 5
         %r1 = L2_loadrh_io %r18, 0
         %r0 = S2_asl_r_r killed %r0, killed %r2
         %r0 = A2_asrh killed %r0
 
   bb.3:
     ; A live-in register without subregs, but with a lane mask that is not ~0