Revert r272045 since GCC doesn't know how to compile it.

llvm-svn: 272048

1 files changed, 507 insertions, 449 deletions

diff --git a/llvm/lib/Target/Hexagon/HexagonExpandCondsets.cpp b/llvm/lib/Target/Hexagon/HexagonExpandCondsets.cpp
index 15445ddbb06..b5f709241f2 100644
--- a/llvm/lib/Target/Hexagon/HexagonExpandCondsets.cpp
+++ b/llvm/lib/Target/Hexagon/HexagonExpandCondsets.cpp
@@ -17,10 +17,10 @@
 //
 // Liveness tracking aside, the main functionality of this pass is divided
 // into two steps. The first step is to replace an instruction
-//   vreg0 = C2_mux vreg1, vreg2, vreg3
+//   vreg0 = C2_mux vreg0, vreg1, vreg2
 // with a pair of conditional transfers
-//   vreg0 = A2_tfrt vreg1, vreg2
-//   vreg0 = A2_tfrf vreg1, vreg3
+//   vreg0 = A2_tfrt vreg0, vreg1
+//   vreg0 = A2_tfrf vreg0, vreg2
 // It is the intention that the execution of this pass could be terminated
 // after this step, and the code generated would be functionally correct.
 //
@@ -60,92 +60,12 @@
 //   vreg3 = A2_tfrf vreg0, vreg2
 //
 
-// Splitting a definition of a register into two predicated transfers
-// creates a complication in liveness tracking. Live interval computation
-// will see both instructions as actual definitions, and will mark the
-// first one as dead. The definition is not actually dead, and this
-// situation will need to be fixed. For example:
-//   vreg1<def,dead> = A2_tfrt ...  ; marked as dead
-//   vreg1<def> = A2_tfrf ...
-//
-// Since any of the individual predicated transfers may end up getting
-// removed (in case it is an identity copy), some pre-existing def may
-// be marked as dead after live interval recomputation:
-//   vreg1<def,dead> = ...          ; marked as dead
-//   ...
-//   vreg1<def> = A2_tfrf ...       ; if A2_tfrt is removed
-// This case happens if vreg1 was used as a source in A2_tfrt, which means
-// that is it actually live at the A2_tfrf, and so the now dead definition
-// of vreg1 will need to be updated to non-dead at some point.
-//
-// This issue could be remedied by adding implicit uses to the predicated
-// transfers, but this will create a problem with subsequent predication,
-// since the transfers will no longer be possible to reorder. To avoid
-// that, the initial splitting will not add any implicit uses. These
-// implicit uses will be added later, after predication. The extra price,
-// however, is that finding the locations where the implicit uses need
-// to be added, and updating the live ranges will be more involved.
-//
-// An additional problem appears when subregister liveness tracking is
-// enabled. In such a scenario, the live interval for the super-register
-// will have live ranges for each subregister (i.e. subranges). This sub-
-// range contains all liveness information about the subregister, except
-// for one case: a "read-undef" flag from another subregister will not
-// be reflected: given
-//   vreg1:subreg_hireg<def,read-undef> = ...  ; "undefines" subreg_loreg
-// the subrange for subreg_loreg will not have any indication that it is
-// undefined at this point. Calculating subregister liveness based only
-// on the information from the subrange may create a segment which spans
-// over such a "read-undef" flag. This would create inconsistencies in
-// the liveness data, resulting in assertions or incorrect code.
-// Example:
-//   vreg1:subreg_loreg<def> = ...
-//   vreg1:subreg_hireg<def, read-undef> = ... ; "undefines" subreg_loreg
-//   ...
-//   vreg1:subreg_loreg<def> = A2_tfrt ...     ; may end up with imp-use
-//                                             ; of subreg_loreg
-// The remedy takes advantage of the fact, that at this point we have
-// an unconditional definition of the subregister. What this means is
-// that any preceding value in this subregister will be overwritten,
-// or in other words, the last use before this def is a kill. This also
-// implies that the first of the predicated transfers at this location
-// should not have any implicit uses.
-// Assume for a moment that no part of the corresponding super-register
-// is used as a source. In such case, the entire super-register can be
-// considered undefined immediately before this instruction. Because of
-// that, we can insert an IMPLICIT_DEF of the super-register at this
-// location, which will cause it to be reflected in all the associated
-// subranges. What is important here is that if an IMPLICIT_DEF of
-// subreg_loreg was used, we would lose the indication that subreg_hireg
-// is also considered undefined. This could lead to having implicit uses
-// incorrectly added.
-//
-// What is left is the two cases when the super-register is used as a
-// source.
-// * Case 1: the used part is the same as the one that is defined:
-//   vreg1<def> = ...
-//   ...
-//   vreg1:subreg_loreg<def,read-undef> = C2_mux ..., vreg1:subreg_loreg
-// In the end, the subreg_loreg should be marked as live at the point of
-// the splitting:
-//   vreg1:subreg_loreg<def,read-undef> = A2_tfrt ; should have imp-use
-//   vreg1:subreg_loreg<def,read-undef> = A2_tfrf ; should have imp-use
-// Hence, an IMPLICIT_DEF of only vreg1:subreg_hireg would be sufficient.
-// * Case 2: the used part does not overlap the part being defined:
-//   vreg1<def> = ...
-//   ...
-//   vreg1:subreg_loreg<def,read-undef> = C2_mux ..., vreg1:subreg_hireg
-// For this case, we insert an IMPLICIT_DEF of vreg1:subreg_hireg after
-// the C2_mux.
-
 #define DEBUG_TYPE "expand-condsets"
-
 #include "HexagonTargetMachine.h"
-#include "llvm/ADT/SetVector.h"
+
 #include "llvm/CodeGen/Passes.h"
 #include "llvm/CodeGen/LiveInterval.h"
 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
-#include "llvm/CodeGen/MachineDominators.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
@@ -156,11 +76,6 @@
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 
-#include <algorithm>
-#include <iterator>
-#include <set>
-#include <utility>
-
 using namespace llvm;
 
 static cl::opt<unsigned> OptTfrLimit("expand-condsets-tfr-limit",
@@ -188,26 +103,23 @@ namespace {
       initializeHexagonExpandCondsetsPass(*PassRegistry::getPassRegistry());
     }
 
-    const char *getPassName() const override {
+    virtual const char *getPassName() const {
       return "Hexagon Expand Condsets";
     }
-    void getAnalysisUsage(AnalysisUsage &AU) const override {
+    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
       AU.addRequired<LiveIntervals>();
       AU.addPreserved<LiveIntervals>();
       AU.addPreserved<SlotIndexes>();
-      AU.addRequired<MachineDominatorTree>();
-      AU.addPreserved<MachineDominatorTree>();
+      AU.addPreservedID(MachineDominatorsID);
       MachineFunctionPass::getAnalysisUsage(AU);
     }
-    bool runOnMachineFunction(MachineFunction &MF) override;
+    virtual bool runOnMachineFunction(MachineFunction &MF);
 
   private:
     const HexagonInstrInfo *HII;
     const TargetRegisterInfo *TRI;
-    MachineDominatorTree *MDT;
     MachineRegisterInfo *MRI;
     LiveIntervals *LIS;
-    std::set<MachineInstr*> LocalImpDefs;
 
     bool CoaLimitActive, TfrLimitActive;
     unsigned CoaLimit, TfrLimit, CoaCounter, TfrCounter;
@@ -220,9 +132,6 @@ namespace {
         return Reg == RR.Reg && Sub == RR.Sub;
       }
       bool operator!= (RegisterRef RR) const { return !operator==(RR); }
-      bool operator< (RegisterRef RR) const {
-        return Reg < RR.Reg || (Reg == RR.Reg && Sub < RR.Sub);
-      }
       unsigned Reg, Sub;
     };
 
@@ -231,43 +140,44 @@ namespace {
     enum { Exec_Then = 0x10, Exec_Else = 0x20 };
     unsigned getMaskForSub(unsigned Sub);
     bool isCondset(const MachineInstr *MI);
-    LaneBitmask getLaneMask(unsigned Reg, unsigned Sub);
 
     void addRefToMap(RegisterRef RR, ReferenceMap &Map, unsigned Exec);
     bool isRefInMap(RegisterRef, ReferenceMap &Map, unsigned Exec);
 
-    void removeImpDefSegments(LiveRange &Range);
-    void updateDeadsInRange(unsigned Reg, LaneBitmask LM, LiveRange &Range);
-    void updateKillFlags(unsigned Reg);
-    void updateDeadFlags(unsigned Reg);
-    void recalculateLiveInterval(unsigned Reg);
-    void removeInstr(MachineInstr *MI);
-    void updateLiveness(std::set<unsigned> &RegSet, bool Recalc,
-        bool UpdateKills, bool UpdateDeads);
+    LiveInterval::iterator nextSegment(LiveInterval &LI, SlotIndex S);
+    LiveInterval::iterator prevSegment(LiveInterval &LI, SlotIndex S);
+    void makeDefined(unsigned Reg, SlotIndex S, bool SetDef);
+    void makeUndead(unsigned Reg, SlotIndex S);
+    void shrinkToUses(unsigned Reg, LiveInterval &LI);
+    void updateKillFlags(unsigned Reg, LiveInterval &LI);
+    void terminateSegment(LiveInterval::iterator LT, SlotIndex S,
+        LiveInterval &LI);
+    void addInstrToLiveness(MachineInstr *MI);
+    void removeInstrFromLiveness(MachineInstr *MI);
 
     unsigned getCondTfrOpcode(const MachineOperand &SO, bool Cond);
-    MachineInstr *genCondTfrFor(MachineOperand &SrcOp,
-        MachineBasicBlock::iterator At, unsigned DstR,
-        unsigned DstSR, const MachineOperand &PredOp, bool PredSense,
-        bool ReadUndef, bool ImpUse);
-    bool split(MachineInstr *MI, std::set<unsigned> &UpdRegs);
-    bool splitInBlock(MachineBasicBlock &B, std::set<unsigned> &UpdRegs);
+    MachineInstr *genTfrFor(MachineOperand &SrcOp, unsigned DstR,
+        unsigned DstSR, const MachineOperand &PredOp, bool Cond);
+    bool split(MachineInstr *MI);
+    bool splitInBlock(MachineBasicBlock &B);
 
     bool isPredicable(MachineInstr *MI);
     MachineInstr *getReachingDefForPred(RegisterRef RD,
         MachineBasicBlock::iterator UseIt, unsigned PredR, bool Cond);
     bool canMoveOver(MachineInstr *MI, ReferenceMap &Defs, ReferenceMap &Uses);
     bool canMoveMemTo(MachineInstr *MI, MachineInstr *ToI, bool IsDown);
-    void predicateAt(const MachineOperand &DefOp, MachineInstr *MI,
-        MachineBasicBlock::iterator Where, const MachineOperand &PredOp,
-        bool Cond, std::set<unsigned> &UpdRegs);
+    void predicateAt(RegisterRef RD, MachineInstr *MI,
+        MachineBasicBlock::iterator Where, unsigned PredR, bool Cond,
+        bool PredUndef);
     void renameInRange(RegisterRef RO, RegisterRef RN, unsigned PredR,
         bool Cond, MachineBasicBlock::iterator First,
         MachineBasicBlock::iterator Last);
-    bool predicate(MachineInstr *TfrI, bool Cond,
-        std::set<unsigned> &UpdRegs);
-    bool predicateInBlock(MachineBasicBlock &B,
-        std::set<unsigned> &UpdRegs);
+    bool predicate(MachineInstr *TfrI, bool Cond);
+    bool predicateInBlock(MachineBasicBlock &B);
+
+    void postprocessUndefImplicitUses(MachineBasicBlock &B);
+    void removeImplicitUses(MachineInstr *MI);
+    void removeImplicitUses(MachineBasicBlock &B);
 
     bool isIntReg(RegisterRef RR, unsigned &BW);
     bool isIntraBlocks(LiveInterval &LI);
@@ -314,13 +224,6 @@ bool HexagonExpandCondsets::isCondset(const MachineInstr *MI) {
 }
 
 
-LaneBitmask HexagonExpandCondsets::getLaneMask(unsigned Reg, unsigned Sub) {
-  assert(TargetRegisterInfo::isVirtualRegister(Reg));
-  return Sub != 0 ? TRI->getSubRegIndexLaneMask(Sub)
-                  : MRI->getMaxLaneMaskForVReg(Reg);
-}
-
-
 void HexagonExpandCondsets::addRefToMap(RegisterRef RR, ReferenceMap &Map,
       unsigned Exec) {
   unsigned Mask = getMaskForSub(RR.Sub) | Exec;
@@ -344,227 +247,408 @@ bool HexagonExpandCondsets::isRefInMap(RegisterRef RR, ReferenceMap &Map,
 }
 
 
-void HexagonExpandCondsets::updateKillFlags(unsigned Reg) {
-  auto KillAt = [this,Reg] (SlotIndex K, LaneBitmask LM) -> void {
-    MachineInstr *MI = LIS->getInstructionFromIndex(K);
-    for (auto &Op : MI->operands()) {
-      if (!Op.isReg() || !Op.isUse() || Op.getReg() != Reg)
-        continue;
-      LaneBitmask SLM = getLaneMask(Reg, Op.getSubReg());
-      if (SLM & LM) {
-        // Only set the kill flag on the first encountered use of Reg in this
-        // instruction.
-        Op.setIsKill(true);
-        break;
-      }
-    }
-  };
-
-  LiveInterval &LI = LIS->getInterval(Reg);
-  for (auto I = LI.begin(), E = LI.end(); I != E; ++I) {
-    if (!I->end.isRegister())
-      continue;
-    // Do not mark the end of the segment as <kill>, if the next segment
-    // starts with a predicated instruction.
-    auto NextI = std::next(I);
-    if (NextI != E && NextI->start.isRegister()) {
-      MachineInstr *DefI = LIS->getInstructionFromIndex(NextI->start);
-      if (HII->isPredicated(*DefI))
-        continue;
-    }
-    bool WholeReg = true;
-    if (LI.hasSubRanges()) {
-      auto EndsAtI = [I] (LiveInterval::SubRange &S) -> bool {
-        return S.find(I->end) != S.end();
-      };
-      if (!std::all_of(LI.subrange_begin(), LI.subrange_end(), EndsAtI)) {
-        WholeReg = false;
-        for (LiveInterval::SubRange &S : LI.subranges())
-          KillAt(I->end, S.LaneMask);
-      }
-    }
-    if (WholeReg)
-      KillAt(I->end, MRI->getMaxLaneMaskForVReg(Reg));
+LiveInterval::iterator HexagonExpandCondsets::nextSegment(LiveInterval &LI,
+      SlotIndex S) {
+  for (LiveInterval::iterator I = LI.begin(), E = LI.end(); I != E; ++I) {
+    if (I->start >= S)
+      return I;
   }
+  return LI.end();
 }
 
 
-void HexagonExpandCondsets::removeImpDefSegments(LiveRange &Range) {
-  auto StartImpDef = [this] (LiveRange::Segment &S) -> bool {
-    return S.start.isRegister() &&
-           LocalImpDefs.count(LIS->getInstructionFromIndex(S.start));
-  };
-  Range.segments.erase(std::remove_if(Range.begin(), Range.end(), StartImpDef),
-                       Range.end());
+LiveInterval::iterator HexagonExpandCondsets::prevSegment(LiveInterval &LI,
+      SlotIndex S) {
+  LiveInterval::iterator P = LI.end();
+  for (LiveInterval::iterator I = LI.begin(), E = LI.end(); I != E; ++I) {
+    if (I->end > S)
+      return P;
+    P = I;
+  }
+  return P;
 }
 
-void HexagonExpandCondsets::updateDeadsInRange(unsigned Reg, LaneBitmask LM,
-      LiveRange &Range) {
-  assert(TargetRegisterInfo::isVirtualRegister(Reg));
-  if (Range.empty())
-    return;
 
-  auto IsRegDef = [this,Reg,LM] (MachineOperand &Op) -> bool {
-    if (!Op.isReg() || !Op.isDef())
-      return false;
-    unsigned DR = Op.getReg(), DSR = Op.getSubReg();
-    if (!TargetRegisterInfo::isVirtualRegister(DR) || DR != Reg)
-      return false;
-    LaneBitmask SLM = getLaneMask(DR, DSR);
-    return (SLM & LM) != 0;
-  };
+/// Find the implicit use of register Reg in slot index S, and make sure
+/// that the "defined" flag is set to SetDef. While the mux expansion is
+/// going on, predicated instructions will have implicit uses of the
+/// registers that are being defined. This is to keep any preceding
+/// definitions live. If there is no preceding definition, the implicit
+/// use will be marked as "undef", otherwise it will be "defined". This
+/// function is used to update the flag.
+void HexagonExpandCondsets::makeDefined(unsigned Reg, SlotIndex S,
+      bool SetDef) {
+  if (!S.isRegister())
+    return;
+  MachineInstr *MI = LIS->getInstructionFromIndex(S);
+  assert(MI && "Expecting instruction");
+  for (auto &Op : MI->operands()) {
+    if (!Op.isReg() || !Op.isUse() || Op.getReg() != Reg)
+      continue;
+    bool IsDef = !Op.isUndef();
+    if (Op.isImplicit() && IsDef != SetDef)
+      Op.setIsUndef(!SetDef);
+  }
+}
 
-  // The splitting step will create pairs of predicated definitions without
-  // any implicit uses (since implicit uses would interfere with predication).
-  // This can cause the reaching defs to become dead after live range
-  // recomputation, even though they are not really dead.
-  // We need to identify predicated defs that need implicit uses, and
-  // dead defs that are not really dead, and correct both problems.
-
-  SetVector<MachineBasicBlock*> Defs;
-  auto Dominate = [this] (SetVector<MachineBasicBlock*> &Defs,
-                          MachineBasicBlock *Dest) -> bool {
-    for (MachineBasicBlock *D : Defs)
-      if (D != Dest && MDT->dominates(D, Dest))
-        return true;
 
-    MachineBasicBlock *Entry = &Dest->getParent()->front();
-    SetVector<MachineBasicBlock*> Work(Dest->pred_begin(), Dest->pred_end());
-    for (unsigned i = 0; i < Work.size(); ++i) {
-      MachineBasicBlock *B = Work[i];
-      if (Defs.count(B))
+void HexagonExpandCondsets::makeUndead(unsigned Reg, SlotIndex S) {
+  // If S is a block boundary, then there can still be a dead def reaching
+  // this point. Instead of traversing the CFG, queue start points of all
+  // live segments that begin with a register, and end at a block boundary.
+  // This may "resurrect" some truly dead definitions, but doing so is
+  // harmless.
+  SmallVector<MachineInstr*,8> Defs;
+  if (S.isBlock()) {
+    LiveInterval &LI = LIS->getInterval(Reg);
+    for (LiveInterval::iterator I = LI.begin(), E = LI.end(); I != E; ++I) {
+      if (!I->start.isRegister() || !I->end.isBlock())
         continue;
-      if (B == Entry)
-        return false;
-      for (auto *P : B->predecessors())
-        Work.insert(P);
+      MachineInstr *MI = LIS->getInstructionFromIndex(I->start);
+      Defs.push_back(MI);
     }
-    return true;
-  };
-
-  // First, try to extend live range within individual basic blocks. This
-  // will leave us only with dead defs that do not reach any predicated
-  // defs in the same block.
-  SmallVector<SlotIndex,4> PredDefs;
-  for (auto &Seg : Range) {
-    if (!Seg.start.isRegister())
-      continue;
-    MachineInstr *DefI = LIS->getInstructionFromIndex(Seg.start);
-    if (LocalImpDefs.count(DefI))
-      continue;
-    Defs.insert(DefI->getParent());
-    if (HII->isPredicated(*DefI))
-      PredDefs.push_back(Seg.start);
+  } else if (S.isRegister()) {
+    MachineInstr *MI = LIS->getInstructionFromIndex(S);
+    Defs.push_back(MI);
   }
-  for (auto &SI : PredDefs) {
-    MachineBasicBlock *BB = LIS->getMBBFromIndex(SI);
-    if (Range.extendInBlock(LIS->getMBBStartIdx(BB), SI))
-      SI = SlotIndex();
+
+  for (unsigned i = 0, n = Defs.size(); i < n; ++i) {
+    MachineInstr *MI = Defs[i];
+    for (auto &Op : MI->operands()) {
+      if (!Op.isReg() || !Op.isDef() || Op.getReg() != Reg)
+        continue;
+      Op.setIsDead(false);
+    }
   }
+}
 
-  // Calculate reachability for those predicated defs that were not handled
-  // by the in-block extension.
-  SmallVector<SlotIndex,4> ExtTo;
-  for (auto &SI : PredDefs) {
-    if (!SI.isValid())
-      continue;
-    MachineBasicBlock *BB = LIS->getMBBFromIndex(SI);
-    if (BB->pred_empty())
-      continue;
-    // If the defs from this range reach SI via all predecessors, it is live.
-    if (Dominate(Defs, BB))
-      ExtTo.push_back(SI);
+
+/// Shrink the segments in the live interval for a given register to the last
+/// use before each subsequent def. Unlike LiveIntervals::shrinkToUses, this
+/// function will not mark any definitions of Reg as dead. The reason for this
+/// is that this function is used while a MUX instruction is being expanded,
+/// or while a conditional copy is undergoing predication. During these
+/// processes, there may be defs present in the instruction sequence that have
+/// not yet been removed, or there may be missing uses that have not yet been
+/// added. We want to utilize LiveIntervals::shrinkToUses as much as possible,
+/// but since it does not extend any intervals that are too short, we need to
+/// pre-emptively extend them here in anticipation of further changes.
+void HexagonExpandCondsets::shrinkToUses(unsigned Reg, LiveInterval &LI) {
+  SmallVector<MachineInstr*,4> Deads;
+  LIS->shrinkToUses(&LI, &Deads);
+  // Need to undo the deadification made by "shrinkToUses". It's easier to
+  // do it here, since we have a list of all instructions that were just
+  // marked as dead.
+  for (unsigned i = 0, n = Deads.size(); i < n; ++i) {
+    MachineInstr *MI = Deads[i];
+    // Clear the "dead" flag.
+    for (auto &Op : MI->operands()) {
+      if (!Op.isReg() || !Op.isDef() || Op.getReg() != Reg)
+        continue;
+      Op.setIsDead(false);
+    }
+    // Extend the live segment to the beginning of the next one.
+    LiveInterval::iterator End = LI.end();
+    SlotIndex S = LIS->getInstructionIndex(*MI).getRegSlot();
+    LiveInterval::iterator T = LI.FindSegmentContaining(S);
+    assert(T != End);
+    LiveInterval::iterator N = std::next(T);
+    if (N != End)
+      T->end = N->start;
+    else
+      T->end = LIS->getMBBEndIdx(MI->getParent());
   }
-  LIS->extendToIndices(Range, ExtTo);
-
-  // Remove <dead> flags from all defs that are not dead after live range
-  // extension, and collect all def operands. They will be used to generate
-  // the necessary implicit uses.
-  std::set<RegisterRef> DefRegs;
-  for (auto &Seg : Range) {
-    if (!Seg.start.isRegister())
-      continue;
-    MachineInstr *DefI = LIS->getInstructionFromIndex(Seg.start);
-    if (LocalImpDefs.count(DefI))
+  updateKillFlags(Reg, LI);
+}
+
+
+/// Given an updated live interval LI for register Reg, update the kill flags
+/// in instructions using Reg to reflect the liveness changes.
+void HexagonExpandCondsets::updateKillFlags(unsigned Reg, LiveInterval &LI) {
+  MRI->clearKillFlags(Reg);
+  for (LiveInterval::iterator I = LI.begin(), E = LI.end(); I != E; ++I) {
+    SlotIndex EX = I->end;
+    if (!EX.isRegister())
       continue;
-    for (auto &Op : DefI->operands()) {
-      if (Seg.start.isDead() || !IsRegDef(Op))
+    MachineInstr *MI = LIS->getInstructionFromIndex(EX);
+    for (auto &Op : MI->operands()) {
+      if (!Op.isReg() || !Op.isUse() || Op.getReg() != Reg)
         continue;
-      DefRegs.insert(Op);
-      Op.setIsDead(false);
+      // Only set the kill flag on the first encountered use of Reg in this
+      // instruction.
+      Op.setIsKill(true);
+      break;
     }
   }
+}
 
 
-  // Finally, add implicit uses to each predicated def that is reached
-  // by other defs. Remove segments started by implicit-defs first, since
-  // they do not define registers.
-  removeImpDefSegments(Range);
+/// When adding a new instruction to liveness, the newly added definition
+/// will start a new live segment. This may happen at a position that falls
+/// within an existing live segment. In such case that live segment needs to
+/// be truncated to make room for the new segment. Ultimately, the truncation
+/// will occur at the last use, but for now the segment can be terminated
+/// right at the place where the new segment will start. The segments will be
+/// shrunk-to-uses later.
+void HexagonExpandCondsets::terminateSegment(LiveInterval::iterator LT,
+      SlotIndex S, LiveInterval &LI) {
+  // Terminate the live segment pointed to by LT within a live interval LI.
+  if (LT == LI.end())
+    return;
 
-  for (auto &Seg : Range) {
-    if (!Seg.start.isRegister() || !Range.liveAt(Seg.start.getPrevSlot()))
-      continue;
-    MachineInstr *DefI = LIS->getInstructionFromIndex(Seg.start);
-    if (!HII->isPredicated(*DefI))
+  VNInfo *OldVN = LT->valno;
+  SlotIndex EX = LT->end;
+  LT->end = S;
+  // If LT does not end at a block boundary, the termination is done.
+  if (!EX.isBlock())
+    return;
+
+  // If LT ended at a block boundary, it's possible that its value number
+  // is picked up at the beginning other blocks. Create a new value number
+  // and change such blocks to use it instead.
+  VNInfo *NewVN = 0;
+  for (LiveInterval::iterator I = LI.begin(), E = LI.end(); I != E; ++I) {
+    if (!I->start.isBlock() || I->valno != OldVN)
       continue;
-    MachineFunction &MF = *DefI->getParent()->getParent();
-    // Construct the set of all necessary implicit uses, based on the def
-    // operands in the instruction.
-    std::set<RegisterRef> ImpUses;
-    for (auto &Op : DefI->operands())
-      if (Op.isReg() && Op.isDef() && DefRegs.count(Op))
-        ImpUses.insert(Op);
-    for (RegisterRef R : ImpUses)
-      MachineInstrBuilder(MF, DefI).addReg(R.Reg, RegState::Implicit, R.Sub);
+    // Generate on-demand a new value number that is defined by the
+    // block beginning (i.e. -phi).
+    if (!NewVN)
+      NewVN = LI.getNextValue(I->start, LIS->getVNInfoAllocator());
+    I->valno = NewVN;
   }
 }
 
 
-void HexagonExpandCondsets::updateDeadFlags(unsigned Reg) {
-  LiveInterval &LI = LIS->getInterval(Reg);
-  if (LI.hasSubRanges()) {
-    for (LiveInterval::SubRange &S : LI.subranges()) {
-      updateDeadsInRange(Reg, S.LaneMask, S);
-      LIS->shrinkToUses(S, Reg);
-      // LI::shrinkToUses will add segments started by implicit-defs.
-      // Remove them again.
-      removeImpDefSegments(S);
+/// Add the specified instruction to live intervals. This function is used
+/// to update the live intervals while the program code is being changed.
+/// Neither the expansion of a MUX, nor the predication are atomic, and this
+/// function is used to update the live intervals while these transformations
+/// are being done.
+void HexagonExpandCondsets::addInstrToLiveness(MachineInstr *MI) {
+  SlotIndex MX = LIS->isNotInMIMap(*MI) ? LIS->InsertMachineInstrInMaps(*MI)
+                                        : LIS->getInstructionIndex(*MI);
+  DEBUG(dbgs() << "adding liveness info for instr\n  " << MX << "  " << *MI);
+
+  MX = MX.getRegSlot();
+  bool Predicated = HII->isPredicated(*MI);
+  MachineBasicBlock *MB = MI->getParent();
+
+  // Strip all implicit uses from predicated instructions. They will be
+  // added again, according to the updated information.
+  if (Predicated)
+    removeImplicitUses(MI);
+
+  // For each def in MI we need to insert a new live segment starting at MX
+  // into the interval. If there already exists a live segment in the interval
+  // that contains MX, we need to terminate it at MX.
+  SmallVector<RegisterRef,2> Defs;
+  for (auto &Op : MI->operands())
+    if (Op.isReg() && Op.isDef())
+      Defs.push_back(RegisterRef(Op));
+
+  for (unsigned i = 0, n = Defs.size(); i < n; ++i) {
+    unsigned DefR = Defs[i].Reg;
+    LiveInterval &LID = LIS->getInterval(DefR);
+    DEBUG(dbgs() << "adding def " << PrintReg(DefR, TRI)
+                 << " with interval\n  " << LID << "\n");
+    // If MX falls inside of an existing live segment, terminate it.
+    LiveInterval::iterator LT = LID.FindSegmentContaining(MX);
+    if (LT != LID.end())
+      terminateSegment(LT, MX, LID);
+    DEBUG(dbgs() << "after terminating segment\n  " << LID << "\n");
+
+    // Create a new segment starting from MX.
+    LiveInterval::iterator P = prevSegment(LID, MX), N = nextSegment(LID, MX);
+    SlotIndex EX;
+    VNInfo *VN = LID.getNextValue(MX, LIS->getVNInfoAllocator());
+    if (N == LID.end()) {
+      // There is no live segment after MX. End this segment at the end of
+      // the block.
+      EX = LIS->getMBBEndIdx(MB);
+    } else {
+      // If the next segment starts at the block boundary, end the new segment
+      // at the boundary of the preceding block (i.e. the previous index).
+      // Otherwise, end the segment at the beginning of the next segment. In
+      // either case it will be "shrunk-to-uses" later.
+      EX = N->start.isBlock() ? N->start.getPrevIndex() : N->start;
+    }
+    if (Predicated) {
+      // Predicated instruction will have an implicit use of the defined
+      // register. This is necessary so that this definition will not make
+      // any previous definitions dead. If there are no previous live
+      // segments, still add the implicit use, but make it "undef".
+      // Because of the implicit use, the preceding definition is not
+      // dead. Mark is as such (if necessary).
+      MachineOperand ImpUse = MachineOperand::CreateReg(DefR, false, true);
+      ImpUse.setSubReg(Defs[i].Sub);
+      bool Undef = false;
+      if (P == LID.end())
+        Undef = true;
+      else {
+        // If the previous segment extends to the end of the previous block,
+        // the end index may actually be the beginning of this block. If
+        // the previous segment ends at a block boundary, move it back by one,
+        // to get the proper block for it.
+        SlotIndex PE = P->end.isBlock() ? P->end.getPrevIndex() : P->end;
+        MachineBasicBlock *PB = LIS->getMBBFromIndex(PE);
+        if (PB != MB && !LIS->isLiveInToMBB(LID, MB))
+          Undef = true;
+      }
+      if (!Undef) {
+        makeUndead(DefR, P->valno->def);
+        // We are adding a live use, so extend the previous segment to
+        // include it.
+        P->end = MX;
+      } else {
+        ImpUse.setIsUndef(true);
+      }
+
+      if (!MI->readsRegister(DefR))
+        MI->addOperand(ImpUse);
+      if (N != LID.end())
+        makeDefined(DefR, N->start, true);
     }
-    LI.clear();
-    LIS->constructMainRangeFromSubranges(LI);
-  } else {
-    updateDeadsInRange(Reg, MRI->getMaxLaneMaskForVReg(Reg), LI);
+    LiveRange::Segment NR = LiveRange::Segment(MX, EX, VN);
+    LID.addSegment(NR);
+    DEBUG(dbgs() << "added a new segment " << NR << "\n  " << LID << "\n");
+    shrinkToUses(DefR, LID);
+    DEBUG(dbgs() << "updated imp-uses: " << *MI);
+    LID.verify();
+  }
+
+  // For each use in MI:
+  // - If there is no live segment that contains MX for the used register,
+  //   extend the previous one. Ignore implicit uses.
+  for (auto &Op : MI->operands()) {
+    if (!Op.isReg() || !Op.isUse() || Op.isImplicit() || Op.isUndef())
+      continue;
+    unsigned UseR = Op.getReg();
+    LiveInterval &LIU = LIS->getInterval(UseR);
+    // Find the last segment P that starts before MX.
+    LiveInterval::iterator P = LIU.FindSegmentContaining(MX);
+    if (P == LIU.end())
+      P = prevSegment(LIU, MX);
+
+    assert(P != LIU.end() && "MI uses undefined register?");
+    SlotIndex EX = P->end;
+    // If P contains MX, there is not much to do.
+    if (EX > MX) {
+      Op.setIsKill(false);
+      continue;
+    }
+    // Otherwise, extend P to "next(MX)".
+    P->end = MX.getNextIndex();
+    Op.setIsKill(true);
+    // Get the old "kill" instruction, and remove the kill flag.
+    if (MachineInstr *KI = LIS->getInstructionFromIndex(MX))
+      KI->clearRegisterKills(UseR, nullptr);
+    shrinkToUses(UseR, LIU);
+    LIU.verify();
   }
 }
 
 
-void HexagonExpandCondsets::recalculateLiveInterval(unsigned Reg) {
-  LIS->removeInterval(Reg);
-  LIS->createAndComputeVirtRegInterval(Reg);
-}
+/// Update the live interval information to reflect the removal of the given
+/// instruction from the program. As with "addInstrToLiveness", this function
+/// is called while the program code is being changed.
+void HexagonExpandCondsets::removeInstrFromLiveness(MachineInstr *MI) {
+  SlotIndex MX = LIS->getInstructionIndex(*MI).getRegSlot();
+  DEBUG(dbgs() << "removing instr\n  " << MX << "  " << *MI);
 
+  // For each def in MI:
+  // If MI starts a live segment, merge this segment with the previous segment.
+  //
+  for (auto &Op : MI->operands()) {
+    if (!Op.isReg() || !Op.isDef())
+      continue;
+    unsigned DefR = Op.getReg();
+    LiveInterval &LID = LIS->getInterval(DefR);
+    LiveInterval::iterator LT = LID.FindSegmentContaining(MX);
+    assert(LT != LID.end() && "Expecting live segments");
+    DEBUG(dbgs() << "removing def at " << MX << " of " << PrintReg(DefR, TRI)
+                 << " with interval\n  " << LID << "\n");
+    if (LT->start != MX)
+      continue;
 
-void HexagonExpandCondsets::removeInstr(MachineInstr *MI) {
-  LIS->RemoveMachineInstrFromMaps(*MI);
-  MI->eraseFromParent();
-}
+    VNInfo *MVN = LT->valno;
+    if (LT != LID.begin()) {
+      // If the current live segment is not the first, the task is easy. If
+      // the previous segment continues into the current block, extend it to
+      // the end of the current one, and merge the value numbers.
+      // Otherwise, remove the current segment, and make the end of it "undef".
+      LiveInterval::iterator P = std::prev(LT);
+      SlotIndex PE = P->end.isBlock() ? P->end.getPrevIndex() : P->end;
+      MachineBasicBlock *MB = MI->getParent();
+      MachineBasicBlock *PB = LIS->getMBBFromIndex(PE);
+      if (PB != MB && !LIS->isLiveInToMBB(LID, MB)) {
+        makeDefined(DefR, LT->end, false);
+        LID.removeSegment(*LT);
+      } else {
+        // Make the segments adjacent, so that merge-vn can also merge the
+        // segments.
+        P->end = LT->start;
+        makeUndead(DefR, P->valno->def);
+        LID.MergeValueNumberInto(MVN, P->valno);
+      }
+    } else {
+      LiveInterval::iterator N = std::next(LT);
+      LiveInterval::iterator RmB = LT, RmE = N;
+      while (N != LID.end()) {
+        // Iterate until the first register-based definition is found
+        // (i.e. skip all block-boundary entries).
+        LiveInterval::iterator Next = std::next(N);
+        if (N->start.isRegister()) {
+          makeDefined(DefR, N->start, false);
+          break;
+        }
+        if (N->end.isRegister()) {
+          makeDefined(DefR, N->end, false);
+          RmE = Next;
+          break;
+        }
+        RmE = Next;
+        N = Next;
+      }
+      // Erase the segments in one shot to avoid invalidating iterators.
+      LID.segments.erase(RmB, RmE);
+    }
+
+    bool VNUsed = false;
+    for (LiveInterval::iterator I = LID.begin(), E = LID.end(); I != E; ++I) {
+      if (I->valno != MVN)
+        continue;
+      VNUsed = true;
+      break;
+    }
+    if (!VNUsed)
+      MVN->markUnused();
 
+    DEBUG(dbgs() << "new interval: ");
+    if (!LID.empty()) {
+      DEBUG(dbgs() << LID << "\n");
+      LID.verify();
+    } else {
+      DEBUG(dbgs() << "<empty>\n");
+      LIS->removeInterval(DefR);
+    }
+  }
 
-void HexagonExpandCondsets::updateLiveness(std::set<unsigned> &RegSet,
-      bool Recalc, bool UpdateKills, bool UpdateDeads) {
-  UpdateKills |= UpdateDeads;
-  for (auto R : RegSet) {
-    if (Recalc)
-      recalculateLiveInterval(R);
-    if (UpdateKills)
-      MRI->clearKillFlags(R);
-    if (UpdateDeads)
-      updateDeadFlags(R);
-    // Fixing <dead> flags may extend live ranges, so reset <kill> flags
-    // after that.
-    if (UpdateKills)
-      updateKillFlags(R);
-    LIS->getInterval(R).verify();
+  // For uses there is nothing to do. The intervals will be updated via
+  // shrinkToUses.
+  SmallVector<unsigned,4> Uses;
+  for (auto &Op : MI->operands()) {
+    if (!Op.isReg() || !Op.isUse())
+      continue;
+    unsigned R = Op.getReg();
+    if (!TargetRegisterInfo::isVirtualRegister(R))
+      continue;
+    Uses.push_back(R);
+  }
+  LIS->RemoveMachineInstrFromMaps(*MI);
+  MI->eraseFromParent();
+  for (unsigned i = 0, n = Uses.size(); i < n; ++i) {
+    LiveInterval &LI = LIS->getInterval(Uses[i]);
+    shrinkToUses(Uses[i], LI);
   }
 }
 
@@ -572,7 +656,7 @@ void HexagonExpandCondsets::updateLiveness(std::set<unsigned> &RegSet,
 /// Get the opcode for a conditional transfer of the value in SO (source
 /// operand). The condition (true/false) is given in Cond.
 unsigned HexagonExpandCondsets::getCondTfrOpcode(const MachineOperand &SO,
-      bool IfTrue) {
+      bool Cond) {
   using namespace Hexagon;
   if (SO.isReg()) {
     unsigned PhysR;
@@ -589,14 +673,14 @@ unsigned HexagonExpandCondsets::getCondTfrOpcode(const MachineOperand &SO,
     const TargetRegisterClass *RC = TRI->getMinimalPhysRegClass(PhysS);
     switch (RC->getSize()) {
       case 4:
-        return IfTrue ? A2_tfrt : A2_tfrf;
+        return Cond ? A2_tfrt : A2_tfrf;
       case 8:
-        return IfTrue ? A2_tfrpt : A2_tfrpf;
+        return Cond ? A2_tfrpt : A2_tfrpf;
     }
     llvm_unreachable("Invalid register operand");
   }
   if (SO.isImm() || SO.isFPImm())
-    return IfTrue ? C2_cmoveit : C2_cmoveif;
+    return Cond ? C2_cmoveit : C2_cmoveif;
   llvm_unreachable("Unexpected source operand");
 }
 
@@ -605,12 +689,11 @@ unsigned HexagonExpandCondsets::getCondTfrOpcode(const MachineOperand &SO,
 /// destination register DstR:DstSR, and using the predicate register from
 /// PredOp. The Cond argument specifies whether the predicate is to be
 /// if(PredOp), or if(!PredOp).
-MachineInstr *HexagonExpandCondsets::genCondTfrFor(MachineOperand &SrcOp,
-      MachineBasicBlock::iterator At,
-      unsigned DstR, unsigned DstSR, const MachineOperand &PredOp,
-      bool PredSense, bool ReadUndef, bool ImpUse) {
+MachineInstr *HexagonExpandCondsets::genTfrFor(MachineOperand &SrcOp,
+      unsigned DstR, unsigned DstSR, const MachineOperand &PredOp, bool Cond) {
   MachineInstr *MI = SrcOp.getParent();
-  MachineBasicBlock &B = *At->getParent();
+  MachineBasicBlock &B = *MI->getParent();
+  MachineBasicBlock::iterator At = MI;
   DebugLoc DL = MI->getDebugLoc();
 
   // Don't avoid identity copies here (i.e. if the source and the destination
@@ -619,24 +702,21 @@ MachineInstr *HexagonExpandCondsets::genCondTfrFor(MachineOperand &SrcOp,
   // step. The predication will remove such a copy if it is unable to
   /// predicate.
 
-  unsigned Opc = getCondTfrOpcode(SrcOp, PredSense);
-  unsigned State = RegState::Define | (ReadUndef ? RegState::Undef : 0);
-  MachineInstrBuilder MIB = BuildMI(B, At, DL, HII->get(Opc))
-        .addReg(DstR, State, DstSR)
+  unsigned Opc = getCondTfrOpcode(SrcOp, Cond);
+  MachineInstr *TfrI = BuildMI(B, At, DL, HII->get(Opc))
+        .addReg(DstR, RegState::Define, DstSR)
         .addOperand(PredOp)
         .addOperand(SrcOp);
-
   // We don't want any kills yet.
-  MIB->clearKillInfo();
-  DEBUG(dbgs() << "created an initial copy: " << *MIB);
-  return &*MIB;
+  TfrI->clearKillInfo();
+  DEBUG(dbgs() << "created an initial copy: " << *TfrI);
+  return TfrI;
 }
 
 
 /// Replace a MUX instruction MI with a pair A2_tfrt/A2_tfrf. This function
 /// performs all necessary changes to complete the replacement.
-bool HexagonExpandCondsets::split(MachineInstr *MI,
-      std::set<unsigned> &UpdRegs) {
+bool HexagonExpandCondsets::split(MachineInstr *MI) {
   if (TfrLimitActive) {
     if (TfrCounter >= TfrLimit)
       return false;
@@ -644,69 +724,33 @@ bool HexagonExpandCondsets::split(MachineInstr *MI,
   }
   DEBUG(dbgs() << "\nsplitting BB#" << MI->getParent()->getNumber()
                << ": " << *MI);
-  MachineOperand &MD  = MI->getOperand(0); // Definition
-  MachineOperand &MP  = MI->getOperand(1); // Predicate register
-  MachineOperand &MS1 = MI->getOperand(2); // Source value #1
-  MachineOperand &MS2 = MI->getOperand(3); // Source value #2
+  MachineOperand &MD = MI->getOperand(0); // Definition
+  MachineOperand &MP = MI->getOperand(1); // Predicate register
   assert(MD.isDef());
   unsigned DR = MD.getReg(), DSR = MD.getSubReg();
-  bool ReadUndef = MD.isUndef();
-  MachineBasicBlock::iterator At = MI;
-
-  if (ReadUndef && DSR != 0 && MRI->shouldTrackSubRegLiveness(DR)) {
-    unsigned NewSR = 0;
-    MachineBasicBlock::iterator DefAt = At;
-    bool SameReg = (MS1.isReg() && DR == MS1.getReg()) ||
-                   (MS2.isReg() && DR == MS2.getReg());
-    if (SameReg) {
-      NewSR = (DSR == Hexagon::subreg_loreg) ? Hexagon::subreg_hireg
-                                             : Hexagon::subreg_loreg;
-      // Advance the insertion point if the subregisters differ between
-      // the source and the target (with the same super-register).
-      // Note: this case has never occured during tests.
-      if ((MS1.isReg() && NewSR == MS1.getSubReg()) ||
-          (MS2.isReg() && NewSR == MS2.getSubReg()))
-        ++DefAt;
-    }
-    // Use "At", since "DefAt" may be end().
-    MachineBasicBlock &B = *At->getParent();
-    DebugLoc DL = At->getDebugLoc();
-    auto ImpD = BuildMI(B, DefAt, DL, HII->get(TargetOpcode::IMPLICIT_DEF))
-                  .addReg(DR, RegState::Define, NewSR);
-    LIS->InsertMachineInstrInMaps(*ImpD);
-    LocalImpDefs.insert(&*ImpD);
-  }
 
   // First, create the two invididual conditional transfers, and add each
   // of them to the live intervals information. Do that first and then remove
   // the old instruction from live intervals.
-  MachineInstr *TfrT = genCondTfrFor(MI->getOperand(2), At, DR, DSR, MP, true,
-                                     ReadUndef, false);
-  MachineInstr *TfrF = genCondTfrFor(MI->getOperand(3), At, DR, DSR, MP, false,
-                                     ReadUndef, true);
-  LIS->InsertMachineInstrInMaps(*TfrT);
-  LIS->InsertMachineInstrInMaps(*TfrF);
-
-  // Will need to recalculate live intervals for all registers in MI.
-  for (auto &Op : MI->operands())
-    if (Op.isReg())
-      UpdRegs.insert(Op.getReg());
+  if (MachineInstr *TfrT = genTfrFor(MI->getOperand(2), DR, DSR, MP, true))
+    addInstrToLiveness(TfrT);
+  if (MachineInstr *TfrF = genTfrFor(MI->getOperand(3), DR, DSR, MP, false))
+    addInstrToLiveness(TfrF);
+  removeInstrFromLiveness(MI);
 
-  removeInstr(MI);
   return true;
 }
 
 
-/// Split all MUX instructions in the given block into pairs of conditional
+/// Split all MUX instructions in the given block into pairs of contitional
 /// transfers.
-bool HexagonExpandCondsets::splitInBlock(MachineBasicBlock &B,
-      std::set<unsigned> &UpdRegs) {
+bool HexagonExpandCondsets::splitInBlock(MachineBasicBlock &B) {
   bool Changed = false;
   MachineBasicBlock::iterator I, E, NextI;
   for (I = B.begin(), E = B.end(); I != E; I = NextI) {
     NextI = std::next(I);
     if (isCondset(I))
-      Changed |= split(I, UpdRegs);
+      Changed |= split(I);
   }
   return Changed;
 }
@@ -848,9 +892,9 @@ bool HexagonExpandCondsets::canMoveMemTo(MachineInstr *TheI, MachineInstr *ToI,
 
 /// Generate a predicated version of MI (where the condition is given via
 /// PredR and Cond) at the point indicated by Where.
-void HexagonExpandCondsets::predicateAt(const MachineOperand &DefOp,
-      MachineInstr *MI, MachineBasicBlock::iterator Where,
-      const MachineOperand &PredOp, bool Cond, std::set<unsigned> &UpdRegs) {
+void HexagonExpandCondsets::predicateAt(RegisterRef RD, MachineInstr *MI,
+      MachineBasicBlock::iterator Where, unsigned PredR, bool Cond,
+      bool PredUndef) {
   // The problem with updating live intervals is that we can move one def
   // past another def. In particular, this can happen when moving an A2_tfrt
   // over an A2_tfrf defining the same register. From the point of view of
@@ -877,9 +921,8 @@ void HexagonExpandCondsets::predicateAt(const MachineOperand &DefOp,
   }
   // Add the new def, then the predicate register, then the rest of the
   // operands.
-  MB.addReg(DefOp.getReg(), getRegState(DefOp), DefOp.getSubReg());
-  MB.addReg(PredOp.getReg(), PredOp.isUndef() ? RegState::Undef : 0,
-            PredOp.getSubReg());
+  MB.addReg(RD.Reg, RegState::Define, RD.Sub);
+  MB.addReg(PredR, PredUndef ? RegState::Undef : 0);
   while (Ox < NP) {
     MachineOperand &MO = MI->getOperand(Ox);
     if (!MO.isReg() || !MO.isImplicit())
@@ -897,11 +940,7 @@ void HexagonExpandCondsets::predicateAt(const MachineOperand &DefOp,
 
   MachineInstr *NewI = MB;
   NewI->clearKillInfo();
-  LIS->InsertMachineInstrInMaps(*NewI);
-
-  for (auto &Op : NewI->operands())
-    if (Op.isReg())
-      UpdRegs.insert(Op.getReg());
+  addInstrToLiveness(NewI);
 }
 
 
@@ -936,8 +975,7 @@ void HexagonExpandCondsets::renameInRange(RegisterRef RO, RegisterRef RN,
 /// For a given conditional copy, predicate the definition of the source of
 /// the copy under the given condition (using the same predicate register as
 /// the copy).
-bool HexagonExpandCondsets::predicate(MachineInstr *TfrI, bool Cond,
-      std::set<unsigned> &UpdRegs) {
+bool HexagonExpandCondsets::predicate(MachineInstr *TfrI, bool Cond) {
   // TfrI - A2_tfr[tf] Instruction (not A2_tfrsi).
   unsigned Opc = TfrI->getOpcode();
   (void)Opc;
@@ -953,9 +991,10 @@ bool HexagonExpandCondsets::predicate(MachineInstr *TfrI, bool Cond,
   // some registers, which would complicate the transformation considerably.
   if (!MS.isKill())
     return false;
-  // Avoid predicating instructions that define a subregister if subregister
-  // liveness tracking is not enabled.
-  if (MD.getSubReg() && !MRI->shouldTrackSubRegLiveness(MD.getReg()))
+  // Avoid predicating instructions that define a subregister. The code
+  // does not handle correctly cases where both subregisters of a register
+  // are defined by a condset.
+  if (MD.getSubReg())
     return false;
 
   RegisterRef RT(MS);
@@ -1046,42 +1085,37 @@ bool HexagonExpandCondsets::predicate(MachineInstr *TfrI, bool Cond,
                << ", can move down: " << (CanDown ? "yes\n" : "no\n"));
   MachineBasicBlock::iterator PastDefIt = std::next(DefIt);
   if (CanUp)
-    predicateAt(MD, DefI, PastDefIt, MP, Cond, UpdRegs);
+    predicateAt(RD, DefI, PastDefIt, PredR, Cond, MP.isUndef());
   else if (CanDown)
-    predicateAt(MD, DefI, TfrIt, MP, Cond, UpdRegs);
+    predicateAt(RD, DefI, TfrIt, PredR, Cond, MP.isUndef());
   else
     return false;
 
-  if (RT != RD) {
+  if (RT != RD)
     renameInRange(RT, RD, PredR, Cond, PastDefIt, TfrIt);
-    UpdRegs.insert(RT.Reg);
-  }
 
-  removeInstr(TfrI);
-  removeInstr(DefI);
+  // Delete the user of RT first (it should work either way, but this order
+  // of deleting is more natural).
+  removeInstrFromLiveness(TfrI);
+  removeInstrFromLiveness(DefI);
   return true;
 }
 
 
 /// Predicate all cases of conditional copies in the specified block.
-bool HexagonExpandCondsets::predicateInBlock(MachineBasicBlock &B,
-      std::set<unsigned> &UpdRegs) {
+bool HexagonExpandCondsets::predicateInBlock(MachineBasicBlock &B) {
   bool Changed = false;
   MachineBasicBlock::iterator I, E, NextI;
   for (I = B.begin(), E = B.end(); I != E; I = NextI) {
     NextI = std::next(I);
     unsigned Opc = I->getOpcode();
     if (Opc == Hexagon::A2_tfrt || Opc == Hexagon::A2_tfrf) {
-      bool Done = predicate(I, (Opc == Hexagon::A2_tfrt), UpdRegs);
+      bool Done = predicate(I, (Opc == Hexagon::A2_tfrt));
       if (!Done) {
         // If we didn't predicate I, we may need to remove it in case it is
         // an "identity" copy, e.g.  vreg1 = A2_tfrt vreg2, vreg1.
-        if (RegisterRef(I->getOperand(0)) == RegisterRef(I->getOperand(2))) {
-          for (auto &Op : I->operands())
-            if (Op.isReg())
-              UpdRegs.insert(Op.getReg());
-          removeInstr(&*I);
-        }
+        if (RegisterRef(I->getOperand(0)) == RegisterRef(I->getOperand(2)))
+          removeInstrFromLiveness(I);
       }
       Changed |= Done;
     }
@@ -1090,6 +1124,49 @@ bool HexagonExpandCondsets::predicateInBlock(MachineBasicBlock &B,
 }
 
 
+void HexagonExpandCondsets::removeImplicitUses(MachineInstr *MI) {
+  for (unsigned i = MI->getNumOperands(); i > 0; --i) {
+    MachineOperand &MO = MI->getOperand(i-1);
+    if (MO.isReg() && MO.isUse() && MO.isImplicit())
+      MI->RemoveOperand(i-1);
+  }
+}
+
+
+void HexagonExpandCondsets::removeImplicitUses(MachineBasicBlock &B) {
+  for (MachineInstr &MI : B)
+    if (HII->isPredicated(MI))
+      removeImplicitUses(&MI);
+}
+
+
+void HexagonExpandCondsets::postprocessUndefImplicitUses(MachineBasicBlock &B) {
+  // Implicit uses that are "undef" are only meaningful (outside of the
+  // internals of this pass) when the instruction defines a subregister,
+  // and the implicit-undef use applies to the defined register. In such
+  // cases, the proper way to record the information in the IR is to mark
+  // the definition as "undef", which will be interpreted as "read-undef".
+  typedef SmallSet<unsigned,2> RegisterSet;
+  for (MachineBasicBlock::iterator I = B.begin(), E = B.end(); I != E; ++I) {
+    MachineInstr *MI = &*I;
+    RegisterSet Undefs;
+    for (unsigned i = MI->getNumOperands(); i > 0; --i) {
+      MachineOperand &MO = MI->getOperand(i-1);
+      if (MO.isReg() && MO.isUse() && MO.isImplicit() && MO.isUndef()) {
+        MI->RemoveOperand(i-1);
+        Undefs.insert(MO.getReg());
+      }
+    }
+    for (auto &Op : MI->operands()) {
+      if (!Op.isReg() || !Op.isDef() || !Op.getSubReg())
+        continue;
+      if (Undefs.count(Op.getReg()))
+        Op.setIsUndef(true);
+    }
+  }
+}
+
+
 bool HexagonExpandCondsets::isIntReg(RegisterRef RR, unsigned &BW) {
   if (!TargetRegisterInfo::isVirtualRegister(RR.Reg))
     return false;
@@ -1172,7 +1249,7 @@ bool HexagonExpandCondsets::coalesceRegisters(RegisterRef R1, RegisterRef R2) {
   while (L2.begin() != L2.end())
     L2.removeSegment(*L2.begin());
 
-  updateKillFlags(R1.Reg);
+  updateKillFlags(R1.Reg, L1);
   DEBUG(dbgs() << "coalesced: " << L1 << "\n");
   L1.verify();
 
@@ -1247,53 +1324,34 @@ bool HexagonExpandCondsets::runOnMachineFunction(MachineFunction &MF) {
 
   HII = static_cast<const HexagonInstrInfo*>(MF.getSubtarget().getInstrInfo());
   TRI = MF.getSubtarget().getRegisterInfo();
-  MDT = &getAnalysis<MachineDominatorTree>();
   LIS = &getAnalysis<LiveIntervals>();
   MRI = &MF.getRegInfo();
-  LocalImpDefs.clear();
-
-  DEBUG(LIS->print(dbgs() << "Before expand-condsets\n",
-                   MF.getFunction()->getParent()));
+  DEBUG(MF.print(dbgs() << "Before expand-condsets\n", LIS->getSlotIndexes()));
 
   bool Changed = false;
-  std::set<unsigned> SplitUpd, PredUpd;
 
   // Try to coalesce the target of a mux with one of its sources.
   // This could eliminate a register copy in some circumstances.
   Changed |= coalesceSegments(MF);
 
-  // First, simply split all muxes into a pair of conditional transfers
-  // and update the live intervals to reflect the new arrangement. The
-  // goal is to update the kill flags, since predication will rely on
-  // them.
-  for (auto &B : MF)
-    Changed |= splitInBlock(B, SplitUpd);
-  updateLiveness(SplitUpd, true, true, false);
-
-  // Traverse all blocks and collapse predicable instructions feeding
-  // conditional transfers into predicated instructions.
-  // Walk over all the instructions again, so we may catch pre-existing
-  // cases that were not created in the previous step.
-  for (auto &B : MF)
-    Changed |= predicateInBlock(B, PredUpd);
-
-  updateLiveness(PredUpd, true, true, true);
-  // Remove from SplitUpd all registers contained in PredUpd to avoid
-  // unnecessary liveness recalculation.
-  std::set<unsigned> Diff;
-  std::set_difference(SplitUpd.begin(), SplitUpd.end(),
-                      PredUpd.begin(), PredUpd.end(),
-                      std::inserter(Diff, Diff.begin()));
-  updateLiveness(Diff, false, false, true);
-
-  for (auto *ImpD : LocalImpDefs)
-    removeInstr(ImpD);
-
-  DEBUG({
-    if (Changed)
-      LIS->print(dbgs() << "After expand-condsets\n",
-                 MF.getFunction()->getParent());
-  });
+  for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) {
+    // First, simply split all muxes into a pair of conditional transfers
+    // and update the live intervals to reflect the new arrangement.
+    // This is done mainly to make the live interval update simpler, than it
+    // would be while trying to predicate instructions at the same time.
+    Changed |= splitInBlock(*I);
+    // Traverse all blocks and collapse predicable instructions feeding
+    // conditional transfers into predicated instructions.
+    // Walk over all the instructions again, so we may catch pre-existing
+    // cases that were not created in the previous step.
+    Changed |= predicateInBlock(*I);
+  }
+
+  for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I)
+    postprocessUndefImplicitUses(*I);
+
+  if (Changed)
+    DEBUG(MF.print(dbgs() << "After expand-condsets\n", LIS->getSlotIndexes()));
 
   return Changed;
 }