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);
+
+    // Need to traverse all predecessors, because some of them may not be
+    // among the blocks in SameTails. This could happen, for example, if one
+    // of the blocks in SameTails is used as the common tail.
+    for (MachineBasicBlock *Pred : NewDest->predecessors()) {
+      LivePhysRegs LiveOuts(*TRI);
+      LiveOuts.addLiveIns(*Pred);
+
+      // Actually recalculate the live-outs in Pred. This is necessary because
+      // removing an <undef> flag in mergeOperations can make the liveness info
+      // incorrect. The purpose of this code is to identify such cases and
+      // patch it with IMPLICIT_DEFs.
+      SmallVector<std::pair<unsigned, const MachineOperand*>, 2> Clobbers;
+      for (const MachineInstr &MI : *Pred) {
+        LiveOuts.stepForward(MI, Clobbers);
+        for (auto C : Clobbers)
+          if (C.second->isReg() && C.second->isDef() && C.second->isDead())
+            LiveOuts.removeReg(C.first);
+        Clobbers.clear();
+      }
+
+      for (const MachineBasicBlock::RegisterMaskPair &LI : NewDest->liveins()) {
+        if (!LiveOuts.available(*MRI, LI.PhysReg))
+          continue;
+        MachineBasicBlock::iterator At = Pred->getFirstTerminator();
+        const DebugLoc &dl = Pred->findDebugLoc(At);
+        BuildMI(*Pred, At, dl, TII->get(TargetOpcode::IMPLICIT_DEF),
+                LI.PhysReg);
+      }
+    }
   }
 
   ++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