Remove stale live-ins in the branch folder

[kparzysz]

Summary

Hoisting common code can cause registers that live-in in the successor blocks to no longer be live-in. The live-in information needs to be updated to reflect this, or otherwise incorrect code can be generated later on.

[kparzysz]

Ping.

[MatzeB]

I would consider it okay if the live-in lists contain more registers. I consider it a code-quality/optimization problem but in principle I don't think passes should fail because of it, so there would be a bug in IfConversion when it creates invalid code because of extra live-in registers.

Having said that: We should go ahead with this patch: It increases precision of the live-in lists.

lib/CodeGen/BranchFolding.cpp

bool BranchFolder::HoistCommonCodeInSuccs(MachineBasicBlock *MBB) {
   // point to the end of the block.
   SmallSet<unsigned, 4> Uses, Defs;
   MachineBasicBlock::iterator Loc =
     findHoistingInsertPosAndDeps(MBB, TII, TRI, Uses, Defs);
   if (Loc == MBB->end())
     return false;
 
   bool HasDups = false;
-  SmallVector<unsigned, 4> LocalDefs;
-  SmallSet<unsigned, 4> LocalDefsSet;
+  SmallVector<unsigned, 4> LocalDefs, LocalKills;
+  SmallSet<unsigned, 4> ActiveDefsSet, AllDefsSet;
   MachineBasicBlock::iterator TIB = TBB->begin();
   MachineBasicBlock::iterator FIB = FBB->begin();
   MachineBasicBlock::iterator TIE = TBB->end();
   MachineBasicBlock::iterator FIE = FBB->end();
   while (TIB != TIE && FIB != FIE) {
     // Skip dbg_value instructions. These do not count.
     TIB = skipDebugInstructionsForward(TIB, TIE);
     FIB = skipDebugInstructionsForward(FIB, FIE);
for (MachineOperand &MO : TIB->operands()) {
           // brcc eflag
           //
           // BB2:
           // r1 = op2, ...
           //    = op3, r1<kill>
           IsSafe = false;
           break;
         }
-      } else if (!LocalDefsSet.count(Reg)) {
+      } else if (!ActiveDefsSet.count(Reg)) {
         if (Defs.count(Reg)) {
           // Use is defined by the instruction at the point of insertion.
           IsSafe = false;
           break;
         }
 
         if (MO.isKill() && Uses.count(Reg))
           // Kills a register that's read by the instruction at the point of
           // insertion. Remove the kill marker.
           MO.setIsKill(false);
       }
     }
     if (!IsSafe)
       break;
 
     bool DontMoveAcrossStore = true;
     if (!TIB->isSafeToMove(nullptr, DontMoveAcrossStore))
       break;
 
-    // Remove kills from LocalDefsSet, these registers had short live ranges.
+    // Remove kills from ActiveDefsSet, these registers had short live ranges.
     for (const MachineOperand &MO : TIB->operands()) {
       if (!MO.isReg() || !MO.isUse() || !MO.isKill())
         continue;
       unsigned Reg = MO.getReg();
-      if (!Reg || !LocalDefsSet.count(Reg))
+      if (!Reg)
+        continue;
+      if (!AllDefsSet.count(Reg)) {
+        LocalKills.push_back(Reg);
         continue;
+      }
       if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
         for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI)
-          LocalDefsSet.erase(*AI);
+          ActiveDefsSet.erase(*AI);
       } else {
-        LocalDefsSet.erase(Reg);
+        ActiveDefsSet.erase(Reg);
       }
     }
 
     // Track local defs so we can update liveins.
     for (const MachineOperand &MO : TIB->operands()) {
       if (!MO.isReg() || !MO.isDef() || MO.isDead())
         continue;
       unsigned Reg = MO.getReg();
       if (!Reg || TargetRegisterInfo::isVirtualRegister(Reg))
         continue;
       LocalDefs.push_back(Reg);
-      addRegAndItsAliases(Reg, TRI, LocalDefsSet);
+      addRegAndItsAliases(Reg, TRI, ActiveDefsSet);
+      addRegAndItsAliases(Reg, TRI, AllDefsSet);
     }
 
     HasDups = true;
     ++TIB;
     ++FIB;
   }
 
   if (!HasDups)
     return false;
 
   MBB->splice(Loc, TBB, TBB->begin(), TIB);
   FBB->erase(FBB->begin(), FIB);
 
   // Update livein's.
-  bool AddedLiveIns = false;
+  bool ChangedLiveIns = false;
   for (unsigned i = 0, e = LocalDefs.size(); i != e; ++i) {
     unsigned Def = LocalDefs[i];
-    if (LocalDefsSet.count(Def)) {
+    if (ActiveDefsSet.count(Def)) {
       TBB->addLiveIn(Def);
       FBB->addLiveIn(Def);
-      AddedLiveIns = true;
-    }
+      ChangedLiveIns = true;
+    }
+  for (unsigned K : LocalKills) {
+    TBB->removeLiveIn(K);
+    FBB->removeLiveIn(K);
+    ChangedLiveIns = true;
   }
 
-  if (AddedLiveIns) {
+  if (ChangedLiveIns) {
     TBB->sortUniqueLiveIns();
     FBB->sortUniqueLiveIns();
   }
 
   ++NumHoist;
   return true;
 }

test/CodeGen/Hexagon/branch-folder-hoist-kills.mir

+# RUN: llc -march=hexagon -run-pass branch-folder -run-pass if-converter -verify-machineinstrs %s -o - | FileCheck %s
+
+# The hoisting of common instructions from successors could cause registers
+# to no longer be live-in in the successor blocks. The liveness was updated
+# to include potential new live-in registres, but not to remove registers
+# that were no longer live-in.
+# This could cause if-converter to generate incorrect code.
+#
+# In this testcase, the "r1 = A2_sxth r0<kill>" was hoisted, and since r0
+# was killed, it was no longer live-in in either successor. The if-converter
+# then created code, where the first predicated instruction has incorrect
+# implicit use of r0:
+#
+# BB#0:
+#     Live Ins: %R0
+#         %R1<def> = A2_sxth %R0<kill>               ; hoisted, kills r0
+#         A2_nop %P0<imp-def>
+#         %R0<def> = C2_cmoveit %P0, 2, %R0<imp-use> ; predicated A2_tfrsi
+#         %R0<def> = C2_cmoveif %P0, 1, %R0<imp-use> ; predicated A2_tfrsi
+#         %R0<def> = A2_add %R0<kill>, %R1<kill>
+#         J2_jumpr %R31, %PC<imp-def,dead>
+#
+
+# CHECK: %r1 = A2_sxth killed %r0
+# CHECK: %r0 = C2_cmoveit %p0, 2
+# CHECK-NOT: implicit-def %r0
+# CHECK: %r0 = C2_cmoveif %p0, 1, implicit %r0
+
+---
+name: fred
+tracksRegLiveness: true
+
+body: |
+  bb.0:
+    liveins: %r0
+    successors: %bb.1, %bb.2
+
+    A2_nop implicit-def %p0
+    J2_jumpt killed %p0, %bb.2, implicit-def dead %pc
+
+  bb.1:
+    successors: %bb.3
+    liveins: %r0
+    %r1 = A2_sxth killed %r0
+    %r0 = A2_tfrsi 1
+    J2_jump %bb.3, implicit-def %pc
+
+  bb.2:
+    successors: %bb.3
+    liveins: %r0
+    %r1 = A2_sxth killed %r0
+    %r0 = A2_tfrsi 2
+
+  bb.3:
+    liveins: %r0, %r1
+    %r0 = A2_add killed %r0, killed %r1
+    J2_jumpr %r31, implicit-def dead %pc
+...
+