Insert IMPLICIT_DEFS for undef uses in tail merging

[MatzeB]

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.

To enable this patch the computeLiveIns() function which used to
compute live-ins for a block and set them immediately is split into new
functions:

• computeLiveIns() just computes the live-ins in a LivePhysRegs set.
• addLiveIns() applies the live-ins to a block live-in list.
• computeAndAddLiveIns() is a convenience function combining the other two functions and behaving like computeLiveIns() before this patch.

Based on a patch by Krzysztof Parzyszek <[e-mail]>

[kparzysz]

lib/CodeGen/BranchFolding.cpp

379 ↗

(On Diff #112247)

This needs to calculate liveouts with the tail removed.

This testcase still fails:

# RUN: llc -march=hexagon -run-pass branch-folder %s -o - 
---
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
      %r1 = A2_tfrsi 1
      PS_storerhabs 0, undef %r0
      %r0 = A2_tfrsi 1
      J2_jump %bb.3, implicit-def %pc

  bb.2:
    successors: %bb.3
      %r0 = L2_loadruh_io undef %r1, 0
      PS_storerhabs 0, killed %r0
      %r0 = A2_tfrsi 1
      J2_jump %bb.3, implicit-def %pc

  bb.3:
      PS_jmpret killed %r31, implicit undef %r0, implicit-def %pc
...

The output is

body:             |
  bb.0:
    successors: %bb.1(0x40000000), %bb.2(0x40000000)
  
    J2_jumpt undef %p0, %bb.2, implicit-def %pc
  
  bb.1:
    successors: %bb.3(0x80000000)
  
    %r1 = A2_tfrsi 1
    J2_jump %bb.3, implicit-def %pc
  
  bb.2:
    successors: %bb.3(0x80000000)
  
    %r0 = L2_loadruh_io undef %r1, 0
  
  bb.3:
    liveins: %r0
  
    PS_storerhabs 0, killed %r0
    %r0 = A2_tfrsi 1
    PS_jmpret killed %r31, implicit undef %r0, implicit-def %pc

...

The path bb.0 -> bb.1 -> bb.3 does not define r0, but r0 is a live-in to bb.3.

[kparzysz]

lib/CodeGen/BranchFolding.cpp

379 ↗

(On Diff #112247)

In the original testcase, one of the blocks became the common tail. In this testcase, r1=... was added to that block to force a fresh block to be created for the tail. Then r0=... was added to both source blocks, but at the end so that it would be a part of the common tail. Because of how the live-outs in the code are calculated, this would prevent implicit defs from being added.

I had to change the order of the blocks to trigger the problem, since the traversal order for the predecessors may avoid exposing it.

[kparzysz]

Are there any new developments?

[MatzeB]

In D37034#858114, @kparzysz wrote:

Are there any new developments?

I should be able to get another stab at this today or tomorrow.

[MatzeB]

Rework branchfolding code to behave like this:

• Make sure all the undef flags are merged
• Compute new live-ins to NewDest (but do not set them yet)
• Insert IMP_DEFS into NewDest predecessors where LiveOuts mismatch the new live-ins
• Set new live-in of NewDest
• For all other blocks with common tail:
  • Compute liveness at the position where we will cut the common tail and place the branch.
  • Insert IMP_DEFS as necessary where liveness mismatches live-ins of NewDest
  • Replace common tail with branch

[kparzysz]

This is great. Thanks!

[alberto_magni]

Hi Matthias,

I have stumbled upon a problem related to this change while working on an out-of-tree target.
It reproduces with Hexagon too.

Is the insertion of the IMPLICIT_DEF legal if one of the two terminators of %bb.0 uses $r0 ?
(Here J2_jumpr uses $r0)

Consider this case:

---
name: func0
tracksRegLiveness: true

body: |
  bb.0:
    liveins: $r0, $r31
    successors: %bb.2
      J2_jumpt undef $p0, %bb.2, implicit-def $pc
      J2_jumpr killed $r0, implicit-def $pc

  bb.1:
    liveins: $r31
    successors: %bb.3
      $r0 = L2_loadruh_io undef $r1, 0
      PS_storerhabs 0, killed $r0
      J2_jump %bb.3, implicit-def $pc

  bb.2:
    liveins: $r31
    successors: %bb.3
      PS_storerhabs 0, undef $r0
      J2_jump %bb.3, implicit-def $pc

  bb.3:
    liveins: $r31
      PS_jmpret killed $r31, implicit-def $pc
...
---

Running llc -march=hexagon -run-pass branch-folder gives:

body:             |
  bb.0:
    successors: %bb.1(0x80000000)
    liveins: $r0, $r31

    $r0 = IMPLICIT_DEF
    J2_jumpt undef $p0, %bb.1, implicit-def $pc
    J2_jumpr killed $r0, implicit-def $pc

  bb.1:
    liveins: $r0

    PS_storerhabs 0, $r0
    PS_jmpret killed $r31, implicit-def $pc
...

Thus making $r0 undefined in bb.0, when originally it was not.

Thanks,
Alberto

[circYuan]

I have the same question with @alberto-magni.

[MatzeB]

Uh this is an old commit... Yes Albertos example does not look quite right, though I'm not sure how we would get there. The code does seem to compute liveness before inserting implicit defs (variants of LiveRegs.addLiveOuts(*Pred); LiveRegs.stepBackward() ... if (LiveRegs.available(...)) continue; BuildMI(IMPLICIT_DEF)) I would expect that when using stepBackward() over the jump instruction that uses r2 that it is marked as live and no IMPLICIT_DEF is inserted. If you want to debug this, you should probably start checking the computed liveness information there...

[circYuan]

Hi @MatzeB, thank you for replying for this very the long yeras ago commit!!
AFAIK, this patch computes the live-ins of the common tail block, and compute the live-out of the common tail predecessor block.
If any of the predecessor live-outs mismatches the common tail live-ins, we insert IMPLICIT_DEF before the first terminator instruction, so the predecessor can have that register as a live-out, is it correct?
One thing I'm confuse is that in function mergeCommonTails, LiveRegs doesn't call stepBackward, it would only be called in computeLiveIns which is used to compute the live-ins of the common tail block. The predecessor block only calls addLiveOuts which add the pristine registers and all successors old live-ins to LiveRegs, but function replaceTailWithBranchTo reverse-iterates the MI and call stepBackward. Does mergeCommonTails also need to call stepBackward to update register to LiveRegs?
Since the IMPLICIT_DEF is inserted from the function mergeCommonTails in my case.
Many Thanks!!!

llvm/trunk/include/llvm/CodeGen/LivePhysRegs.h

private:
   void addBlockLiveIns(const MachineBasicBlock &MBB);
 };
 
 inline raw_ostream &operator<<(raw_ostream &OS, const LivePhysRegs& LR) {
   LR.print(OS);
   return OS;
 }
 
-/// \brief Computes the live-in list for \p MBB assuming all of its successors
-/// live-in lists are up-to-date. Uses the given LivePhysReg instance \p
-/// LiveRegs; This is just here to avoid repeated heap allocations when calling
-/// this multiple times in a pass.
-void computeLiveIns(LivePhysRegs &LiveRegs, const MachineRegisterInfo &MRI,
+/// \brief Computes registers live-in to \p MBB assuming all of its successors
+/// live-in lists are up-to-date. Puts the result into the given LivePhysReg
+/// instance \p LiveRegs.
+void computeLiveIns(LivePhysRegs &LiveRegs, const MachineBasicBlock &MBB);
+
+/// Adds registers contained in \p LiveRegs to the block live-in list of \p MBB.
+/// Does not add reserved registers.
+void addLiveIns(MachineBasicBlock &MBB, const LivePhysRegs &LiveRegs);
+
+/// Convenience function combining computeLiveIns() and addLiveIns().
+void computeAndAddLiveIns(LivePhysRegs &LiveRegs,
                           MachineBasicBlock &MBB);
 
 } // end namespace llvm
 
 #endif // LLVM_CODEGEN_LIVEPHYSREGS_H

llvm/trunk/lib/CodeGen/BranchFolding.h

private:
     bool TailMergeBlocks(MachineFunction &MF);
     bool TryTailMergeBlocks(MachineBasicBlock* SuccBB,
                        MachineBasicBlock* PredBB,
                        unsigned MinCommonTailLength);
     void setCommonTailEdgeWeights(MachineBasicBlock &TailMBB);
 
     /// Delete the instruction OldInst and everything after it, replacing it
     /// with an unconditional branch to NewDest.
-    void ReplaceTailWithBranchTo(MachineBasicBlock::iterator OldInst,
-                                 MachineBasicBlock *NewDest);
+    void replaceTailWithBranchTo(MachineBasicBlock::iterator OldInst,
+                                 MachineBasicBlock &NewDest);
 
     /// Given a machine basic block and an iterator into it, split the MBB so
     /// that the part before the iterator falls into the part starting at the
     /// iterator.  This returns the new MBB.
     MachineBasicBlock *SplitMBBAt(MachineBasicBlock &CurMBB,
                                   MachineBasicBlock::iterator BBI1,
                                   const BasicBlock *BB);
 
private:
     /// None of the blocks to be tail-merged consist only of the common tail.
     /// Create a block that does by splitting one.
     bool CreateCommonTailOnlyBlock(MachineBasicBlock *&PredBB,
                                    MachineBasicBlock *SuccBB,
                                    unsigned maxCommonTailLength,
                                    unsigned &commonTailIndex);
 
     /// Create merged DebugLocs of identical instructions across SameTails and
-    /// assign it to the instruction in common tail.
-    void MergeCommonTailDebugLocs(unsigned commonTailIndex);
+    /// assign it to the instruction in common tail; merge MMOs and undef flags.
+    void mergeCommonTails(unsigned commonTailIndex);
 
     bool OptimizeBranches(MachineFunction &MF);
 
     /// Analyze and optimize control flow related to the specified block. This
     /// is never called on the entry block.
     bool OptimizeBlock(MachineBasicBlock *MBB);
 
     /// Remove the specified dead machine basic block from the function,

llvm/trunk/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"
while (I1->isDebugValue()) {
         return TailLen;
       --I1;
     }
     ++I1;
   }
   return TailLen;
 }
 
-void BranchFolder::ReplaceTailWithBranchTo(MachineBasicBlock::iterator OldInst,
-                                           MachineBasicBlock *NewDest) {
-  TII->ReplaceTailWithBranchTo(OldInst, NewDest);
-
+void BranchFolder::replaceTailWithBranchTo(MachineBasicBlock::iterator OldInst,
+                                           MachineBasicBlock &NewDest) {
   if (UpdateLiveIns) {
-    NewDest->clearLiveIns();
-    computeLiveIns(LiveRegs, *MRI, *NewDest);
+    // OldInst should always point to an instruction.
+    MachineBasicBlock &OldMBB = *OldInst->getParent();
+    LiveRegs.clear();
+    LiveRegs.addLiveOuts(OldMBB);
+    // Move backward to the place where will insert the jump.
+    MachineBasicBlock::iterator I = OldMBB.end();
+    do {
+      --I;
+      LiveRegs.stepBackward(*I);
+    } while (I != OldInst);
+
+    // Merging the tails may have switched some undef operand to non-undef ones.
+    // Add IMPLICIT_DEFS into OldMBB as necessary to have a definition of the
+    // register.
+    for (MachineBasicBlock::RegisterMaskPair P : NewDest.liveins()) {
+      // We computed the liveins with computeLiveIn earlier and should only see
+      // full registers:
+      assert(P.LaneMask == LaneBitmask::getAll() &&
+             "Can only handle full register.");
+      MCPhysReg Reg = P.PhysReg;
+      if (!LiveRegs.available(*MRI, Reg))
+        continue;
+      DebugLoc DL;
+      BuildMI(OldMBB, OldInst, DL, TII->get(TargetOpcode::IMPLICIT_DEF), Reg);
+    }
   }
 
+  TII->ReplaceTailWithBranchTo(OldInst, &NewDest);
   ++NumTailMerge;
 }
 
 MachineBasicBlock *BranchFolder::SplitMBBAt(MachineBasicBlock &CurMBB,
                                             MachineBasicBlock::iterator BBI1,
                                             const BasicBlock *BB) {
   if (!TII->isLegalToSplitMBBAt(CurMBB, BBI1))
     return nullptr;
MachineBasicBlock *BranchFolder::SplitMBBAt(MachineBasicBlock &CurMBB,
   if (MLI)
     if (MachineLoop *ML = MLI->getLoopFor(&CurMBB))
       ML->addBasicBlockToLoop(NewMBB, MLI->getBase());
 
   // NewMBB inherits CurMBB's block frequency.
   MBBFreqInfo.setBlockFreq(NewMBB, MBBFreqInfo.getBlockFreq(&CurMBB));
 
   if (UpdateLiveIns)
-    computeLiveIns(LiveRegs, *MRI, *NewMBB);
+    computeAndAddLiveIns(LiveRegs, *NewMBB);
 
   // Add the new block to the funclet.
   const auto &FuncletI = FuncletMembership.find(&CurMBB);
   if (FuncletI != FuncletMembership.end()) {
     auto n = FuncletI->second;
     FuncletMembership[NewMBB] = n;
   }
 
bool BranchFolder::CreateCommonTailOnlyBlock(MachineBasicBlock *&PredBB,
 
   // If we split PredBB, newMBB is the new predecessor.
   if (PredBB == MBB)
     PredBB = newMBB;
 
   return true;
 }
 
-void BranchFolder::MergeCommonTailDebugLocs(unsigned commonTailIndex) {
-  MachineBasicBlock *MBB = SameTails[commonTailIndex].getBlock();
-
-  std::vector<MachineBasicBlock::iterator> NextCommonInsts(SameTails.size());
-  for (unsigned int i = 0 ; i != SameTails.size() ; ++i) {
-    if (i != commonTailIndex)
-      NextCommonInsts[i] = SameTails[i].getTailStartPos();
-    else {
-      assert(SameTails[i].getTailStartPos() == MBB->begin() &&
-          "MBB is not a common tail only block");
-    }
-  }
-
-  for (auto &MI : *MBB) {
-    if (MI.isDebugValue())
-      continue;
-    DebugLoc DL = MI.getDebugLoc();
-    for (unsigned int i = 0 ; i < NextCommonInsts.size() ; i++) {
-      if (i == commonTailIndex)
-        continue;
-
-      auto &Pos = NextCommonInsts[i];
-      assert(Pos != SameTails[i].getBlock()->end() &&
-          "Reached BB end within common tail");
-      while (Pos->isDebugValue()) {
-        ++Pos;
-        assert(Pos != SameTails[i].getBlock()->end() &&
-            "Reached BB end within common tail");
-      }
-      assert(MI.isIdenticalTo(*Pos) && "Expected matching MIIs!");
-      DL = DILocation::getMergedLocation(DL, Pos->getDebugLoc());
-      NextCommonInsts[i] = ++Pos;
-    }
-    MI.setDebugLoc(DL);
-  }
-}
-
 static void
 mergeOperations(MachineBasicBlock::iterator MBBIStartPos,
                 MachineBasicBlock &MBBCommon) {
   MachineBasicBlock *MBB = MBBIStartPos->getParent();
   // Note CommonTailLen does not necessarily matches the size of
   // the common BB nor all its instructions because of debug
   // instructions differences.
   unsigned CommonTailLen = 0;
for (unsigned I = 0, E = MBBICommon->getNumOperands(); I != E; ++I) {
       }
     }
 
     ++MBBI;
     ++MBBICommon;
   }
 }
 
+void BranchFolder::mergeCommonTails(unsigned commonTailIndex) {
+  MachineBasicBlock *MBB = SameTails[commonTailIndex].getBlock();
+
+  std::vector<MachineBasicBlock::iterator> NextCommonInsts(SameTails.size());
+  for (unsigned int i = 0 ; i != SameTails.size() ; ++i) {
+    if (i != commonTailIndex) {
+      NextCommonInsts[i] = SameTails[i].getTailStartPos();
+      mergeOperations(SameTails[i].getTailStartPos(), *MBB);
+    } else {
+      assert(SameTails[i].getTailStartPos() == MBB->begin() &&
+          "MBB is not a common tail only block");
+    }
+  }
+
+  for (auto &MI : *MBB) {
+    if (MI.isDebugValue())
+      continue;
+    DebugLoc DL = MI.getDebugLoc();
+    for (unsigned int i = 0 ; i < NextCommonInsts.size() ; i++) {
+      if (i == commonTailIndex)
+        continue;
+
+      auto &Pos = NextCommonInsts[i];
+      assert(Pos != SameTails[i].getBlock()->end() &&
+          "Reached BB end within common tail");
+      while (Pos->isDebugValue()) {
+        ++Pos;
+        assert(Pos != SameTails[i].getBlock()->end() &&
+            "Reached BB end within common tail");
+      }
+      assert(MI.isIdenticalTo(*Pos) && "Expected matching MIIs!");
+      DL = DILocation::getMergedLocation(DL, Pos->getDebugLoc());
+      NextCommonInsts[i] = ++Pos;
+    }
+    MI.setDebugLoc(DL);
+  }
+
+  if (UpdateLiveIns) {
+    LivePhysRegs NewLiveIns(*TRI);
+    computeLiveIns(NewLiveIns, *MBB);
+
+    // The flag merging may lead to some register uses no longer using the
+    // <undef> flag, add IMPLICIT_DEFs in the predecessors as necessary.
+    for (MachineBasicBlock *Pred : MBB->predecessors()) {
+      LiveRegs.init(*TRI);
+      LiveRegs.addLiveOuts(*Pred);
+      MachineBasicBlock::iterator InsertBefore = Pred->getFirstTerminator();
+      for (unsigned Reg : NewLiveIns) {
+        if (!LiveRegs.available(*MRI, Reg))
+          continue;
+        DebugLoc DL;
+        BuildMI(*Pred, InsertBefore, DL, TII->get(TargetOpcode::IMPLICIT_DEF),
+                Reg);
+      }
+    }
+
+    MBB->clearLiveIns();
+    addLiveIns(*MBB, NewLiveIns);
+  }
+}
+
 // See if any of the blocks in MergePotentials (which all have SuccBB as a
 // successor, or all have no successor if it is null) can be tail-merged.
 // If there is a successor, any blocks in MergePotentials that are not
 // tail-merged and are not immediately before Succ must have an unconditional
 // branch to Succ added (but the predecessor/successor lists need no
 // adjustment). The lone predecessor of Succ that falls through into Succ,
 // if any, is given in PredBB.
 // MinCommonTailLength - Except for the special cases below, tail-merge if
if (commonTailIndex == SameTails.size() ||
       }
     }
 
     MachineBasicBlock *MBB = SameTails[commonTailIndex].getBlock();
 
     // Recompute common tail MBB's edge weights and block frequency.
     setCommonTailEdgeWeights(*MBB);
 
-    // Merge debug locations across identical instructions for common tail.
-    MergeCommonTailDebugLocs(commonTailIndex);
+    // Merge debug locations, MMOs and undef flags across identical instructions
+    // for common tail.
+    mergeCommonTails(commonTailIndex);
 
     // MBB is common tail.  Adjust all other BB's to jump to this one.
     // Traversal must be forwards so erases work.
     DEBUG(dbgs() << "\nUsing common tail in BB#" << MBB->getNumber()
                  << " for ");
     for (unsigned int i=0, e = SameTails.size(); i != e; ++i) {
       if (commonTailIndex == i)
         continue;
       DEBUG(dbgs() << "BB#" << SameTails[i].getBlock()->getNumber()
                    << (i == e-1 ? "" : ", "));
-      // Merge operations (MMOs, undef flags)
-      mergeOperations(SameTails[i].getTailStartPos(), *MBB);
       // Hack the end off BB i, making it jump to BB commonTailIndex instead.
-      ReplaceTailWithBranchTo(SameTails[i].getTailStartPos(), MBB);
+      replaceTailWithBranchTo(SameTails[i].getTailStartPos(), *MBB);
       // BB i is no longer a predecessor of SuccBB; remove it from the worklist.
       MergePotentials.erase(SameTails[i].getMPIter());
     }
     DEBUG(dbgs() << "\n");
     // We leave commonTailIndex in the worklist in case there are other blocks
     // that match it with a smaller number of instructions.
     MadeChange = true;
   }

llvm/trunk/lib/CodeGen/BranchRelaxation.cpp

MachineBasicBlock *BranchRelaxation::splitBlockBeforeInstr(MachineInstr &MI,
   // block, it may contain a tablejump.
   BlockInfo[NewBB->getNumber()].Size = computeBlockSize(*NewBB);
 
   // All BBOffsets following these blocks must be modified.
   adjustBlockOffsets(*OrigBB);
 
   // Need to fix live-in lists if we track liveness.
   if (TRI->trackLivenessAfterRegAlloc(*MF))
-    computeLiveIns(LiveRegs, MF->getRegInfo(), *NewBB);
+    computeAndAddLiveIns(LiveRegs, *NewBB);
 
   ++NumSplit;
 
   return NewBB;
 }
 
 /// isBlockInRange - Returns true if the distance between specific MI and
 /// specific BB can fit in MI's displacement field.
if (FBB && isBlockInRange(MI, *FBB)) {
 
     // Update the successor lists according to the transformation to follow.
     // Do it here since if there's no split, no update is needed.
     MBB->replaceSuccessor(FBB, &NewBB);
     NewBB.addSuccessor(FBB);
 
     // Need to fix live-in lists if we track liveness.
     if (TRI->trackLivenessAfterRegAlloc(*MF))
-      computeLiveIns(LiveRegs, MF->getRegInfo(), NewBB);
+      computeAndAddLiveIns(LiveRegs, NewBB);
   }
 
   // We now have an appropriate fall-through block in place (either naturally or
   // just created), so we can invert the condition.
   MachineBasicBlock &NextBB = *std::next(MachineFunction::iterator(MBB));
 
   DEBUG(dbgs() << "  Insert B to BB#" << TBB->getNumber()
                << ", invert condition and change dest. to BB#"

llvm/trunk/lib/CodeGen/LivePhysRegs.cpp

 
 void LivePhysRegs::addLiveIns(const MachineBasicBlock &MBB) {
   const MachineFunction &MF = *MBB.getParent();
   addPristines(*this, MF);
   addBlockLiveIns(MBB);
 }
 
 void llvm::computeLiveIns(LivePhysRegs &LiveRegs,
-                          const MachineRegisterInfo &MRI,
-                          MachineBasicBlock &MBB) {
+                          const MachineBasicBlock &MBB) {
+  const MachineFunction &MF = *MBB.getParent();
+  const MachineRegisterInfo &MRI = MF.getRegInfo();
   const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
-  assert(MBB.livein_empty());
   LiveRegs.init(TRI);
   LiveRegs.addLiveOutsNoPristines(MBB);
-  for (MachineInstr &MI : make_range(MBB.rbegin(), MBB.rend()))
+  for (const MachineInstr &MI : make_range(MBB.rbegin(), MBB.rend()))
     LiveRegs.stepBackward(MI);
+}
 
-  for (unsigned Reg : LiveRegs) {
+void llvm::addLiveIns(MachineBasicBlock &MBB, const LivePhysRegs &LiveRegs) {
+  assert(MBB.livein_empty() && "Expected empty live-in list");
+  const MachineFunction &MF = *MBB.getParent();
+  const MachineRegisterInfo &MRI = MF.getRegInfo();
+  const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
+  for (MCPhysReg Reg : LiveRegs) {
     if (MRI.isReserved(Reg))
       continue;
     // Skip the register if we are about to add one of its super registers.
     bool ContainsSuperReg = false;
     for (MCSuperRegIterator SReg(Reg, &TRI); SReg.isValid(); ++SReg) {
       if (LiveRegs.contains(*SReg) && !MRI.isReserved(*SReg)) {
         ContainsSuperReg = true;
         break;
       }
     }
     if (ContainsSuperReg)
       continue;
     MBB.addLiveIn(Reg);
   }
 }
+
+void llvm::computeAndAddLiveIns(LivePhysRegs &LiveRegs,
+                                MachineBasicBlock &MBB) {
+  computeLiveIns(LiveRegs, MBB);
+  addLiveIns(MBB, LiveRegs);
+}

llvm/trunk/lib/Target/AArch64/AArch64ExpandPseudoInsts.cpp

bool AArch64ExpandPseudo::expandCMP_SWAP(
   DoneBB->transferSuccessors(&MBB);
 
   MBB.addSuccessor(LoadCmpBB);
 
   NextMBBI = MBB.end();
   MI.eraseFromParent();
 
   // Recompute livein lists.
-  const MachineRegisterInfo &MRI = MBB.getParent()->getRegInfo();
   LivePhysRegs LiveRegs;
-  computeLiveIns(LiveRegs, MRI, *DoneBB);
-  computeLiveIns(LiveRegs, MRI, *StoreBB);
-  computeLiveIns(LiveRegs, MRI, *LoadCmpBB);
+  computeAndAddLiveIns(LiveRegs, *DoneBB);
+  computeAndAddLiveIns(LiveRegs, *StoreBB);
+  computeAndAddLiveIns(LiveRegs, *LoadCmpBB);
   // Do an extra pass around the loop to get loop carried registers right.
   StoreBB->clearLiveIns();
-  computeLiveIns(LiveRegs, MRI, *StoreBB);
+  computeAndAddLiveIns(LiveRegs, *StoreBB);
   LoadCmpBB->clearLiveIns();
-  computeLiveIns(LiveRegs, MRI, *LoadCmpBB);
+  computeAndAddLiveIns(LiveRegs, *LoadCmpBB);
 
   return true;
 }
 
 bool AArch64ExpandPseudo::expandCMP_SWAP_128(
     MachineBasicBlock &MBB, MachineBasicBlock::iterator MBBI,
     MachineBasicBlock::iterator &NextMBBI) {
   MachineInstr &MI = *MBBI;
bool AArch64ExpandPseudo::expandCMP_SWAP_128(
   DoneBB->transferSuccessors(&MBB);
 
   MBB.addSuccessor(LoadCmpBB);
 
   NextMBBI = MBB.end();
   MI.eraseFromParent();
 
   // Recompute liveness bottom up.
-  const MachineRegisterInfo &MRI = MBB.getParent()->getRegInfo();
   LivePhysRegs LiveRegs;
-  computeLiveIns(LiveRegs, MRI, *DoneBB);
-  computeLiveIns(LiveRegs, MRI, *StoreBB);
-  computeLiveIns(LiveRegs, MRI, *LoadCmpBB);
+  computeAndAddLiveIns(LiveRegs, *DoneBB);
+  computeAndAddLiveIns(LiveRegs, *StoreBB);
+  computeAndAddLiveIns(LiveRegs, *LoadCmpBB);
   // Do an extra pass in the loop to get the loop carried dependencies right.
   StoreBB->clearLiveIns();
-  computeLiveIns(LiveRegs, MRI, *StoreBB);
+  computeAndAddLiveIns(LiveRegs, *StoreBB);
   LoadCmpBB->clearLiveIns();
-  computeLiveIns(LiveRegs, MRI, *LoadCmpBB);
+  computeAndAddLiveIns(LiveRegs, *LoadCmpBB);
 
   return true;
 }
 
 /// \brief If MBBI references a pseudo instruction that should be expanded here,
 /// do the expansion and return true.  Otherwise return false.
 bool AArch64ExpandPseudo::expandMI(MachineBasicBlock &MBB,
                                    MachineBasicBlock::iterator MBBI,

llvm/trunk/lib/Target/ARM/ARMExpandPseudoInsts.cpp

bool ARMExpandPseudo::ExpandCMP_SWAP(MachineBasicBlock &MBB,
   DoneBB->transferSuccessors(&MBB);
 
   MBB.addSuccessor(LoadCmpBB);
 
   NextMBBI = MBB.end();
   MI.eraseFromParent();
 
   // Recompute livein lists.
-  const MachineRegisterInfo &MRI = MBB.getParent()->getRegInfo();
   LivePhysRegs LiveRegs;
-  computeLiveIns(LiveRegs, MRI, *DoneBB);
-  computeLiveIns(LiveRegs, MRI, *StoreBB);
-  computeLiveIns(LiveRegs, MRI, *LoadCmpBB);
+  computeAndAddLiveIns(LiveRegs, *DoneBB);
+  computeAndAddLiveIns(LiveRegs, *StoreBB);
+  computeAndAddLiveIns(LiveRegs, *LoadCmpBB);
   // Do an extra pass around the loop to get loop carried registers right.
   StoreBB->clearLiveIns();
-  computeLiveIns(LiveRegs, MRI, *StoreBB);
+  computeAndAddLiveIns(LiveRegs, *StoreBB);
   LoadCmpBB->clearLiveIns();
-  computeLiveIns(LiveRegs, MRI, *LoadCmpBB);
+  computeAndAddLiveIns(LiveRegs, *LoadCmpBB);
 
   return true;
 }
 
 /// ARM's ldrexd/strexd take a consecutive register pair (represented as a
 /// single GPRPair register), Thumb's take two separate registers so we need to
 /// extract the subregs from the pair.
 static void addExclusiveRegPair(MachineInstrBuilder &MIB, MachineOperand &Reg,
bool ARMExpandPseudo::ExpandCMP_SWAP_64(MachineBasicBlock &MBB,
   DoneBB->transferSuccessors(&MBB);
 
   MBB.addSuccessor(LoadCmpBB);
 
   NextMBBI = MBB.end();
   MI.eraseFromParent();
 
   // Recompute livein lists.
-  const MachineRegisterInfo &MRI = MBB.getParent()->getRegInfo();
   LivePhysRegs LiveRegs;
-  computeLiveIns(LiveRegs, MRI, *DoneBB);
-  computeLiveIns(LiveRegs, MRI, *StoreBB);
-  computeLiveIns(LiveRegs, MRI, *LoadCmpBB);
+  computeAndAddLiveIns(LiveRegs, *DoneBB);
+  computeAndAddLiveIns(LiveRegs, *StoreBB);
+  computeAndAddLiveIns(LiveRegs, *LoadCmpBB);
   // Do an extra pass around the loop to get loop carried registers right.
   StoreBB->clearLiveIns();
-  computeLiveIns(LiveRegs, MRI, *StoreBB);
+  computeAndAddLiveIns(LiveRegs, *StoreBB);
   LoadCmpBB->clearLiveIns();
-  computeLiveIns(LiveRegs, MRI, *LoadCmpBB);
+  computeAndAddLiveIns(LiveRegs, *LoadCmpBB);
 
   return true;
 }
 
 
 bool ARMExpandPseudo::ExpandMI(MachineBasicBlock &MBB,
                                MachineBasicBlock::iterator MBBI,
                                MachineBasicBlock::iterator &NextMBBI) {

llvm/trunk/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: name: func0
+# 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: func0
+tracksRegLiveness: true
+
+body: |
+  bb.0:
+    liveins: %r31
+    successors: %bb.1, %bb.2
+      J2_jumpt undef %p0, %bb.2, implicit-def %pc
+      J2_jump %bb.1, implicit-def %pc
+
+  bb.1:
+    liveins: %r31
+    successors: %bb.3
+      %r0 = L2_loadruh_io undef %r1, 0
+      PS_storerhabs 0, killed %r0
+      J2_jump %bb.3, implicit-def %pc
+
+  bb.2:
+    liveins: %r31
+    successors: %bb.3
+      PS_storerhabs 0, undef %r0
+      J2_jump %bb.3, implicit-def %pc
+
+  bb.3:
+    liveins: %r31
+      PS_jmpret killed %r31, implicit-def %pc
+...
+---
+# CHECK-LABEL: name: func1
+# CHECK-LABEL: bb.1:
+# CHECK: %r0 = IMPLICIT_DEF
+# CHECK-LABEL: bb.2:
+# CHECK-LABEL: bb.3:
+# CHECK: liveins: %r0
+# CHECK: PS_storerhabs 0, killed %r0
+# CHECK: PS_jmpret
+
+name: func1
+tracksRegLiveness: true
+
+body: |
+  bb.0:
+    liveins: %r31
+    successors: %bb.1, %bb.2
+      J2_jumpt undef %p0, %bb.2, implicit-def %pc
+      J2_jump %bb.1, implicit-def %pc
+
+  bb.1:
+    liveins: %r31
+    successors: %bb.3
+      %r1 = A2_tfrsi 1
+      PS_storerhabs 0, undef %r0
+      %r0 = A2_tfrsi 1
+      J2_jump %bb.3, implicit-def %pc
+
+  bb.2:
+    liveins: %r31
+    successors: %bb.3
+      %r0 = L2_loadruh_io undef %r1, 0
+      PS_storerhabs 0, killed %r0
+      %r0 = A2_tfrsi 1
+      J2_jump %bb.3, implicit-def %pc
+
+  bb.3:
+    liveins: %r31
+      PS_jmpret killed %r31, implicit undef %r0, implicit-def %pc
+...

llvm/trunk/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