[MachineLICM] delete dead flag if the duplicated def outside of loop is dead.

[shchenz]

Summary

Some definitions may be dead before entering the MachineLICM pass. For example, LiveIntervals pass will mark some definition as dead if there is no user of a virtual register. Before the dead definition is eliminated, it is CSE-ed in machineLICM pass, but the dead flag in the duplicated instruction outside of loop is not cleaned, so we get verify error: Virtual register defs don't dominate all uses. (use after it is set to dead)

Create this patch to fix that issue.

[shchenz]

gentle ping...

[shchenz]

update the comments and gentle ping

[arsenm]

llvm/lib/CodeGen/MachineLICM.cpp

1470

Really should not be using const_cast here

llvm/test/CodeGen/PowerPC/machinelicm-cse-dead-flag.mir

5

Add a comment explaining the test

[shchenz]

llvm/lib/CodeGen/MachineLICM.cpp

1470

Thanks for your comments. Do you mean we should make LookForDuplicate() return MachineInstr * instead of return const MachineInstr *?

llvm/test/CodeGen/PowerPC/machinelicm-cse-dead-flag.mir

5

will do this later.

[arsenm]

llvm/lib/CodeGen/MachineLICM.cpp

1470

Either that, or there's a different place to make this change (I do think this is probably the right place though)

[shchenz]

address @arsenm comments:
1: do not use const_cast
2: add comments for the test point in test case.

[arsenm]

llvm/test/CodeGen/PowerPC/machinelicm-cse-dead-flag.mir

46

Can you add another case where both of the defs are dead?

[shchenz]

address @arsenm comments:
1: handle the case when hoisted and dup registers are both dead.

llvm/test/CodeGen/PowerPC/machinelicm-cse-dead-flag.mir

46

Good catch!

llvm/lib/CodeGen/MachineLICM.cpp

class MachineLICMBase : public MachineFunctionPass {
     // Register pressure "limit" per register pressure set. If the pressure
     // is higher than the limit, then it's considered high.
     SmallVector<unsigned, 8> RegLimit;
 
     // Register pressure on path leading from loop preheader to current BB.
     SmallVector<SmallVector<unsigned, 8>, 16> BackTrace;
 
     // For each opcode, keep a list of potential CSE instructions.
-    DenseMap<unsigned, std::vector<const MachineInstr *>> CSEMap;
+    DenseMap<unsigned, std::vector<MachineInstr *>> CSEMap;
 
     enum {
       SpeculateFalse   = 0,
       SpeculateTrue    = 1,
       SpeculateUnknown = 2
     };
 
     // If a MBB does not dominate loop exiting blocks then it may not safe
DenseMap<unsigned, int> calcRegisterCost(const MachineInstr *MI,
                                              bool ConsiderSeen,
                                              bool ConsiderUnseenAsDef);
 
     void UpdateRegPressure(const MachineInstr *MI,
                            bool ConsiderUnseenAsDef = false);
 
     MachineInstr *ExtractHoistableLoad(MachineInstr *MI);
 
-    const MachineInstr *
-    LookForDuplicate(const MachineInstr *MI,
-                     std::vector<const MachineInstr *> &PrevMIs);
+    MachineInstr *LookForDuplicate(const MachineInstr *MI,
+                                   std::vector<MachineInstr *> &PrevMIs);
 
-    bool EliminateCSE(
-        MachineInstr *MI,
-        DenseMap<unsigned, std::vector<const MachineInstr *>>::iterator &CI);
+    bool
+    EliminateCSE(MachineInstr *MI,
+                 DenseMap<unsigned, std::vector<MachineInstr *>>::iterator &CI);
 
     bool MayCSE(MachineInstr *MI);
 
     bool Hoist(MachineInstr *MI, MachineBasicBlock *Preheader);
 
     void InitCSEMap(MachineBasicBlock *BB);
 
     bool isTgtHotterThanSrc(MachineBasicBlock *SrcBlock,

 /// out of the loop.
 void MachineLICMBase::InitCSEMap(MachineBasicBlock *BB) {
   for (MachineInstr &MI : *BB)
     CSEMap[MI.getOpcode()].push_back(&MI);
 }
 
 /// Find an instruction amount PrevMIs that is a duplicate of MI.
 /// Return this instruction if it's found.
-const MachineInstr*
+MachineInstr *
 MachineLICMBase::LookForDuplicate(const MachineInstr *MI,
-                                  std::vector<const MachineInstr*> &PrevMIs) {
-  for (const MachineInstr *PrevMI : PrevMIs)
+                                  std::vector<MachineInstr *> &PrevMIs) {
+  for (MachineInstr *PrevMI : PrevMIs)
     if (TII->produceSameValue(*MI, *PrevMI, (PreRegAlloc ? MRI : nullptr)))
       return PrevMI;
 
   return nullptr;
 }
 
 /// Given a LICM'ed instruction, look for an instruction on the preheader that
 /// computes the same value. If it's found, do a RAU on with the definition of
 /// the existing instruction rather than hoisting the instruction to the
 /// preheader.
-bool MachineLICMBase::EliminateCSE(MachineInstr *MI,
-    DenseMap<unsigned, std::vector<const MachineInstr *>>::iterator &CI) {
+bool MachineLICMBase::EliminateCSE(
+    MachineInstr *MI,
+    DenseMap<unsigned, std::vector<MachineInstr *>>::iterator &CI) {
   // Do not CSE implicit_def so ProcessImplicitDefs can properly propagate
   // the undef property onto uses.
   if (CI == CSEMap.end() || MI->isImplicitDef())
     return false;
 
-  if (const MachineInstr *Dup = LookForDuplicate(MI, CI->second)) {
+  if (MachineInstr *Dup = LookForDuplicate(MI, CI->second)) {
     LLVM_DEBUG(dbgs() << "CSEing " << *MI << " with " << *Dup);
 
     // Replace virtual registers defined by MI by their counterparts defined
     // by Dup.
     SmallVector<unsigned, 2> Defs;
     for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
       const MachineOperand &MO = MI->getOperand(i);
 
for (unsigned i = 0, e = Defs.size(); i != e; ++i) {
       }
     }
 
     for (unsigned Idx : Defs) {
       Register Reg = MI->getOperand(Idx).getReg();
       Register DupReg = Dup->getOperand(Idx).getReg();
       MRI->replaceRegWith(Reg, DupReg);
       MRI->clearKillFlags(DupReg);
+      // Clear Dup dead flag if any, we reuse it for Reg.
+      if (!MRI->use_nodbg_empty(DupReg))
+        Dup->getOperand(Idx).setIsDead(false);
     }
 
     MI->eraseFromParent();
     ++NumCSEed;
     return true;
   }
   return false;
 }
 
 /// Return true if the given instruction will be CSE'd if it's hoisted out of
 /// the loop.
 bool MachineLICMBase::MayCSE(MachineInstr *MI) {
   unsigned Opcode = MI->getOpcode();
-  DenseMap<unsigned, std::vector<const MachineInstr *>>::iterator
-    CI = CSEMap.find(Opcode);
+  DenseMap<unsigned, std::vector<MachineInstr *>>::iterator CI =
+      CSEMap.find(Opcode);
   // Do not CSE implicit_def so ProcessImplicitDefs can properly propagate
   // the undef property onto uses.
   if (CI == CSEMap.end() || MI->isImplicitDef())
     return false;
 
   return LookForDuplicate(MI, CI->second) != nullptr;
 }
 
bool MachineLICMBase::Hoist(MachineInstr *MI, MachineBasicBlock *Preheader) {
   // initialize the CSE map with potential common expressions.
   if (FirstInLoop) {
     InitCSEMap(Preheader);
     FirstInLoop = false;
   }
 
   // Look for opportunity to CSE the hoisted instruction.
   unsigned Opcode = MI->getOpcode();
-  DenseMap<unsigned, std::vector<const MachineInstr *>>::iterator
-    CI = CSEMap.find(Opcode);
+  DenseMap<unsigned, std::vector<MachineInstr *>>::iterator CI =
+      CSEMap.find(Opcode);
   if (!EliminateCSE(MI, CI)) {
     // Otherwise, splice the instruction to the preheader.
     Preheader->splice(Preheader->getFirstTerminator(),MI->getParent(),MI);
 
     // Since we are moving the instruction out of its basic block, we do not
     // retain its debug location. Doing so would degrade the debugging
     // experience and adversely affect the accuracy of profiling information.
     assert(!MI->isDebugInstr() && "Should not hoist debug inst");

llvm/test/CodeGen/PowerPC/machinelicm-cse-dead-flag.mir

+# NOTE: Assertions have been autogenerated by utils/update_mir_test_checks.py
+# RUN: llc -run-pass early-machinelicm -mtriple=powerpc64le-unknown-linux-gnu \
+# RUN:   -verify-machineinstrs %s -o - | FileCheck %s
+---
+name: deadFlagAfterCSE
+# This case tests that after the dead %3 is CSE-ed with hoisted %5 in MachineLICM
+# pass, the dead flag will be cleared for %3 if %5 has users.
+tracksRegLiveness: true
+body: |
+  ; CHECK-LABEL: name: deadFlagAfterCSE
+  ; CHECK: bb.0:
+  ; CHECK:   successors: %bb.1(0x80000000)
+  ; CHECK:   liveins: $x3, $x4
+  ; CHECK:   [[COPY:%[0-9]+]]:g8rc = COPY $x3
+  ; CHECK:   [[COPY1:%[0-9]+]]:g8rc = COPY $x4
+  ; CHECK:   [[ADD8_:%[0-9]+]]:g8rc_and_g8rc_nox0 = ADD8 [[COPY]], [[COPY1]]
+  ; CHECK:   [[ADDI8_:%[0-9]+]]:g8rc_and_g8rc_nox0 = ADDI8 [[ADD8_]], 100
+  ; CHECK:   B %bb.1
+  ; CHECK: bb.1:
+  ; CHECK:   successors: %bb.1(0x80000000)
+  ; CHECK:   [[PHI:%[0-9]+]]:g8rc_and_g8rc_nox0 = PHI [[ADD8_]], %bb.0, %5, %bb.1
+  ; CHECK:   STDX [[PHI]], [[ADDI8_]], [[ADD8_]]
+  ; CHECK:   [[ADDI8_1:%[0-9]+]]:g8rc = nuw ADDI8 [[PHI]], 1
+  ; CHECK:   B %bb.1
+  ; CHECK: bb.2:
+  ; CHECK:   BLR8 implicit $lr8, implicit $rm
+  bb.0:
+    liveins: $x3, $x4
+    %0:g8rc = COPY $x3
+    %1:g8rc = COPY $x4
+    %2:g8rc_and_g8rc_nox0 = ADD8 %0, %1
+    dead %3:g8rc_and_g8rc_nox0 = ADDI8 %2, 100
+    B %bb.1
+
+  bb.1:
+    %4:g8rc_and_g8rc_nox0 = PHI %2, %bb.0, %6, %bb.1
+    %5:g8rc_and_g8rc_nox0 = ADDI8 %2, 100
+    STDX %4, %5, %2
+    %6:g8rc = nuw ADDI8 %4, 1
+    B %bb.1
+
+  bb.2:
+    BLR8 implicit $lr8, implicit $rm
+...
+---
+name: deadFlagAfterCSE2
+# This case tests that after the dead %3 is CSE-ed with hoisted dead %5 in
+# MachineLICM pass, the dead flag will be kept.
+tracksRegLiveness: true
+body: |
+  ; CHECK-LABEL: name: deadFlagAfterCSE2
+  ; CHECK: bb.0:
+  ; CHECK:   successors: %bb.1(0x80000000)
+  ; CHECK:   liveins: $x3, $x4
+  ; CHECK:   [[COPY:%[0-9]+]]:g8rc = COPY $x3
+  ; CHECK:   [[COPY1:%[0-9]+]]:g8rc = COPY $x4
+  ; CHECK:   [[ADD8_:%[0-9]+]]:g8rc_and_g8rc_nox0 = ADD8 [[COPY]], [[COPY1]]
+  ; CHECK:   dead %3:g8rc_and_g8rc_nox0 = ADDI8 [[ADD8_]], 100
+  ; CHECK:   B %bb.1
+  ; CHECK: bb.1:
+  ; CHECK:   successors: %bb.1(0x80000000)
+  ; CHECK:   [[PHI:%[0-9]+]]:g8rc_and_g8rc_nox0 = PHI [[ADD8_]], %bb.0, %5, %bb.1
+  ; CHECK:   [[ADDI8_:%[0-9]+]]:g8rc = nuw ADDI8 [[PHI]], 1
+  ; CHECK:   B %bb.1
+  ; CHECK: bb.2:
+  ; CHECK:   BLR8 implicit $lr8, implicit $rm
+  bb.0:
+    liveins: $x3, $x4
+    %0:g8rc = COPY $x3
+    %1:g8rc = COPY $x4
+    %2:g8rc_and_g8rc_nox0 = ADD8 %0, %1
+    dead %3:g8rc_and_g8rc_nox0 = ADDI8 %2, 100
+    B %bb.1
+
+  bb.1:
+    %4:g8rc_and_g8rc_nox0 = PHI %2, %bb.0, %6, %bb.1
+    dead %5:g8rc_and_g8rc_nox0 = ADDI8 %2, 100
+    %6:g8rc = nuw ADDI8 %4, 1
+    B %bb.1
+
+  bb.2:
+    BLR8 implicit $lr8, implicit $rm
+...
+