diff --git a/src/IceCfg.cpp b/src/IceCfg.cpp
index a72671e..eaebd1e 100644
--- a/src/IceCfg.cpp
+++ b/src/IceCfg.cpp
@@ -617,7 +617,7 @@
           // the previous block, and if it is also assigned in the first
           // instruction of this block, the adjacent live ranges get merged.
           if (static_cast<class Inst *>(&Inst) != FirstInst &&
-              !Inst.isDestNonKillable() &&
+              !Inst.isDestRedefined() &&
               Dest->getLiveRange().containsValue(InstNumber - 1, IsDest))
             Invalid = true;
           if (Invalid) {
diff --git a/src/IceCfgNode.cpp b/src/IceCfgNode.cpp
index dbbfc18..a3f6dd5 100644
--- a/src/IceCfgNode.cpp
+++ b/src/IceCfgNode.cpp
@@ -681,6 +681,61 @@
   return Changed;
 }
 
+// Validate the integrity of the live ranges in this block.  If there are any
+// errors, it prints details and returns false.  On success, it returns true.
+bool CfgNode::livenessValidateIntervals(Liveness *Liveness) {
+  if (!BuildDefs::asserts())
+    return true;
+
+  // Verify there are no duplicates.
+  auto ComparePair =
+      [](const LiveBeginEndMapEntry &A, const LiveBeginEndMapEntry &B) {
+        return A.first == B.first;
+      };
+  LiveBeginEndMap &MapBegin = *Liveness->getLiveBegin(this);
+  LiveBeginEndMap &MapEnd = *Liveness->getLiveEnd(this);
+  if (std::adjacent_find(MapBegin.begin(), MapBegin.end(), ComparePair) ==
+          MapBegin.end() &&
+      std::adjacent_find(MapEnd.begin(), MapEnd.end(), ComparePair) ==
+          MapEnd.end())
+    return true;
+
+  // There is definitely a liveness error.  All paths from here return false.
+  if (!BuildDefs::dump())
+    return false;
+
+  // Print all the errors.
+  if (BuildDefs::dump()) {
+    GlobalContext *Ctx = Func->getContext();
+    OstreamLocker L(Ctx);
+    Ostream &Str = Ctx->getStrDump();
+    if (Func->isVerbose()) {
+      Str << "Live range errors in the following block:\n";
+      dump(Func);
+    }
+    for (auto Start = MapBegin.begin();
+         (Start = std::adjacent_find(Start, MapBegin.end(), ComparePair)) !=
+         MapBegin.end();
+         ++Start) {
+      auto Next = Start + 1;
+      Str << "Duplicate LR begin, block " << getName() << ", instructions "
+          << Start->second << " & " << Next->second << ", variable "
+          << Liveness->getVariable(Start->first, this)->getName(Func) << "\n";
+    }
+    for (auto Start = MapEnd.begin();
+         (Start = std::adjacent_find(Start, MapEnd.end(), ComparePair)) !=
+         MapEnd.end();
+         ++Start) {
+      auto Next = Start + 1;
+      Str << "Duplicate LR end,   block " << getName() << ", instructions "
+          << Start->second << " & " << Next->second << ", variable "
+          << Liveness->getVariable(Start->first, this)->getName(Func) << "\n";
+    }
+  }
+
+  return false;
+}
+
 // Once basic liveness is complete, compute actual live ranges. It is assumed
 // that within a single basic block, a live range begins at most once and ends
 // at most once. This is certainly true for pure SSA form. It is also true once
@@ -698,16 +753,11 @@
   LiveBeginEndMap &MapEnd = *Liveness->getLiveEnd(this);
   std::sort(MapBegin.begin(), MapBegin.end());
   std::sort(MapEnd.begin(), MapEnd.end());
-  // Verify there are no duplicates.
-  auto ComparePair =
-      [](const LiveBeginEndMapEntry &A, const LiveBeginEndMapEntry &B) {
-        return A.first == B.first;
-      };
-  (void)ComparePair;
-  assert(std::adjacent_find(MapBegin.begin(), MapBegin.end(), ComparePair) ==
-         MapBegin.end());
-  assert(std::adjacent_find(MapEnd.begin(), MapEnd.end(), ComparePair) ==
-         MapEnd.end());
+
+  if (!livenessValidateIntervals(Liveness)) {
+    llvm::report_fatal_error("livenessAddIntervals: Liveness error");
+    return;
+  }
 
   LivenessBV LiveInAndOut = LiveIn;
   LiveInAndOut &= LiveOut;
@@ -875,11 +925,11 @@
   bool First = true;
   Variable *Dest = Instr->getDest();
   // Normally we increment the live count for the dest register. But we
-  // shouldn't if the instruction's IsDestNonKillable flag is set, because this
+  // shouldn't if the instruction's IsDestRedefined flag is set, because this
   // means that the target lowering created this instruction as a non-SSA
   // assignment; i.e., a different, previous instruction started the dest
   // variable's live range.
-  if (!Instr->isDestNonKillable() && Dest && Dest->hasReg())
+  if (!Instr->isDestRedefined() && Dest && Dest->hasReg())
     ++LiveRegCount[Dest->getRegNum()];
   FOREACH_VAR_IN_INST(Var, *Instr) {
     bool ShouldReport = Instr->isLastUse(Var);
diff --git a/src/IceCfgNode.h b/src/IceCfgNode.h
index c6aa729..6aae2b3 100644
--- a/src/IceCfgNode.h
+++ b/src/IceCfgNode.h
@@ -110,6 +110,7 @@
 
 private:
   CfgNode(Cfg *Func, SizeT LabelIndex);
+  bool livenessValidateIntervals(Liveness *Liveness);
   Cfg *const Func;
   SizeT Number;            /// invariant: Func->Nodes[Number]==this
   const SizeT LabelNumber; /// persistent number for label generation
diff --git a/src/IceInst.cpp b/src/IceInst.cpp
index 656ac17..4a5eb2f 100644
--- a/src/IceInst.cpp
+++ b/src/IceInst.cpp
@@ -170,7 +170,7 @@
   if (Dest) {
     SizeT VarNum = Liveness->getLiveIndex(Dest->getIndex());
     if (Live[VarNum]) {
-      if (!isDestNonKillable()) {
+      if (!isDestRedefined()) {
         Live[VarNum] = false;
         if (LiveBegin && Liveness->getRangeMask(Dest->getIndex())) {
           LiveBegin->push_back(std::make_pair(VarNum, InstNumber));
diff --git a/src/IceInst.h b/src/IceInst.h
index d68d201..a1e5161 100644
--- a/src/IceInst.h
+++ b/src/IceInst.h
@@ -92,8 +92,8 @@
 
   bool hasSideEffects() const { return HasSideEffects; }
 
-  bool isDestNonKillable() const { return IsDestNonKillable; }
-  void setDestNonKillable() { IsDestNonKillable = true; }
+  bool isDestRedefined() const { return IsDestRedefined; }
+  void setDestRedefined() { IsDestRedefined = true; }
 
   Variable *getDest() const { return Dest; }
 
@@ -192,10 +192,15 @@
   /// a volatile load that can't be removed even if its Dest variable is not
   /// live.
   bool HasSideEffects = false;
-  /// IsDestNonKillable means that liveness analysis shouldn't consider this
-  /// instruction to kill the Dest variable. This is used when lowering produces
-  /// two assignments to the same variable.
-  bool IsDestNonKillable = false;
+  /// IsDestRedefined indicates that this instruction is not the first
+  /// definition of Dest in the basic block.  The effect is that liveness
+  /// analysis shouldn't consider this instruction to be the start of Dest's
+  /// live range; rather, there is some other instruction earlier in the basic
+  /// block with the same Dest.  This is maintained because liveness analysis
+  /// has an invariant (primarily for performance reasons) that any Variable's
+  /// live range recorded in a basic block has at most one start and at most one
+  /// end.
+  bool IsDestRedefined = false;
 
   Variable *Dest;
   const SizeT MaxSrcs; // only used for assert
diff --git a/src/IceRegAlloc.cpp b/src/IceRegAlloc.cpp
index d9837d9..dacbc00 100644
--- a/src/IceRegAlloc.cpp
+++ b/src/IceRegAlloc.cpp
@@ -132,6 +132,35 @@
   }
 }
 
+// Validate the integrity of the live ranges.  If there are any errors, it
+// prints details and returns false.  On success, it returns true.
+bool LinearScan::livenessValidateIntervals(
+    const DefUseErrorList &DefsWithoutUses,
+    const DefUseErrorList &UsesBeforeDefs,
+    const CfgVector<InstNumberT> &LRBegin,
+    const CfgVector<InstNumberT> &LREnd) {
+  if (DefsWithoutUses.empty() && UsesBeforeDefs.empty())
+    return true;
+
+  if (!BuildDefs::dump())
+    return false;
+
+  const VarList &Vars = Func->getVariables();
+  OstreamLocker L(Ctx);
+  Ostream &Str = Ctx->getStrDump();
+  for (SizeT VarNum : DefsWithoutUses) {
+    Variable *Var = Vars[VarNum];
+    Str << "LR def without use, instruction " << LRBegin[VarNum]
+        << ", variable " << Var->getName(Func) << "\n";
+  }
+  for (SizeT VarNum : UsesBeforeDefs) {
+    Variable *Var = Vars[VarNum];
+    Str << "LR use before def, instruction " << LREnd[VarNum] << ", variable "
+        << Var->getName(Func) << "\n";
+  }
+  return false;
+}
+
 // Prepare for very simple register allocation of only infinite-weight
 // Variables while respecting pre-colored Variables. Some properties we take
 // advantage of:
@@ -168,10 +197,21 @@
   // range for each variable that is pre-colored or infinite weight.
   CfgVector<InstNumberT> LRBegin(Vars.size(), Inst::NumberSentinel);
   CfgVector<InstNumberT> LREnd(Vars.size(), Inst::NumberSentinel);
+  DefUseErrorList DefsWithoutUses, UsesBeforeDefs;
   for (CfgNode *Node : Func->getNodes()) {
     for (Inst &Inst : Node->getInsts()) {
       if (Inst.isDeleted())
         continue;
+      FOREACH_VAR_IN_INST(Var, Inst) {
+        if (Var->getIgnoreLiveness())
+          continue;
+        if (Var->hasReg() || Var->mustHaveReg()) {
+          SizeT VarNum = Var->getIndex();
+          LREnd[VarNum] = Inst.getNumber();
+          if (!Var->getIsArg() && LRBegin[VarNum] == Inst::NumberSentinel)
+            UsesBeforeDefs.push_back(VarNum);
+        }
+      }
       if (const Variable *Var = Inst.getDest()) {
         if (!Var->getIgnoreLiveness() &&
             (Var->hasReg() || Var->mustHaveReg())) {
@@ -181,12 +221,6 @@
           }
         }
       }
-      FOREACH_VAR_IN_INST(Var, Inst) {
-        if (Var->getIgnoreLiveness())
-          continue;
-        if (Var->hasReg() || Var->mustHaveReg())
-          LREnd[Var->getIndex()] = Inst.getNumber();
-      }
     }
   }
 
@@ -195,7 +229,10 @@
   for (SizeT i = 0; i < Vars.size(); ++i) {
     Variable *Var = Vars[i];
     if (LRBegin[i] != Inst::NumberSentinel) {
-      assert(LREnd[i] != Inst::NumberSentinel);
+      if (LREnd[i] == Inst::NumberSentinel) {
+        DefsWithoutUses.push_back(i);
+        continue;
+      }
       Unhandled.push_back(Var);
       Var->resetLiveRange();
       Var->addLiveRange(LRBegin[i], LREnd[i]);
@@ -208,6 +245,30 @@
       --NumVars;
     }
   }
+
+  if (!livenessValidateIntervals(DefsWithoutUses, UsesBeforeDefs, LRBegin,
+                                 LREnd)) {
+    llvm::report_fatal_error("initForInfOnly: Liveness error");
+    return;
+  }
+
+  if (!DefsWithoutUses.empty() || !UsesBeforeDefs.empty()) {
+    if (BuildDefs::dump()) {
+      OstreamLocker L(Ctx);
+      Ostream &Str = Ctx->getStrDump();
+      for (SizeT VarNum : DefsWithoutUses) {
+        Variable *Var = Vars[VarNum];
+        Str << "LR def without use, instruction " << LRBegin[VarNum]
+            << ", variable " << Var->getName(Func) << "\n";
+      }
+      for (SizeT VarNum : UsesBeforeDefs) {
+        Variable *Var = Vars[VarNum];
+        Str << "LR use before def, instruction " << LREnd[VarNum]
+            << ", variable " << Var->getName(Func) << "\n";
+      }
+    }
+    llvm::report_fatal_error("initForInfOnly: Liveness error");
+  }
   // This isn't actually a fatal condition, but it would be nice to know if we
   // somehow pre-calculated Unhandled's size wrong.
   assert(NumVars == 0);
diff --git a/src/IceRegAlloc.h b/src/IceRegAlloc.h
index 7742ad7..6508aa5 100644
--- a/src/IceRegAlloc.h
+++ b/src/IceRegAlloc.h
@@ -41,6 +41,7 @@
 private:
   using OrderedRanges = CfgVector<Variable *>;
   using UnorderedRanges = CfgVector<Variable *>;
+  using DefUseErrorList = llvm::SmallVector<SizeT, 10>;
 
   class IterationState {
     IterationState(const IterationState &) = delete;
@@ -58,6 +59,10 @@
     llvm::SmallVector<RegWeight, REGS_SIZE> Weights;
   };
 
+  bool livenessValidateIntervals(const DefUseErrorList &DefsWithoutUses,
+                                 const DefUseErrorList &UsesBeforeDefs,
+                                 const CfgVector<InstNumberT> &LRBegin,
+                                 const CfgVector<InstNumberT> &LREnd);
   void initForGlobal();
   void initForInfOnly();
   /// Move an item from the From set to the To set. From[Index] is pushed onto
diff --git a/src/IceTargetLowering.cpp b/src/IceTargetLowering.cpp
index 6920788..eb4a54d 100644
--- a/src/IceTargetLowering.cpp
+++ b/src/IceTargetLowering.cpp
@@ -246,17 +246,21 @@
   LinearScan.scan(RegMask, Ctx->getFlags().shouldRandomizeRegAlloc());
 }
 
-void TargetLowering::inferTwoAddress() {
-  // Find two-address non-SSA instructions where Dest==Src0, and set the
-  // DestNonKillable flag to keep liveness analysis consistent.
+void TargetLowering::markRedefinitions() {
+  // Find (non-SSA) instructions where the Dest variable appears in some source
+  // operand, and set the IsDestRedefined flag to keep liveness analysis
+  // consistent.
   for (auto Inst = Context.getCur(), E = Context.getNext(); Inst != E; ++Inst) {
     if (Inst->isDeleted())
       continue;
-    if (Variable *Dest = Inst->getDest()) {
-      // TODO(stichnot): We may need to consider all source operands, not just
-      // the first one, if using 3-address instructions.
-      if (Inst->getSrcSize() > 0 && Inst->getSrc(0) == Dest)
-        Inst->setDestNonKillable();
+    Variable *Dest = Inst->getDest();
+    if (Dest == nullptr)
+      continue;
+    FOREACH_VAR_IN_INST(Var, *Inst) {
+      if (Var == Dest) {
+        Inst->setDestRedefined();
+        break;
+      }
     }
   }
 }
diff --git a/src/IceTargetLowering.h b/src/IceTargetLowering.h
index 7f3eaa7..0095a39 100644
--- a/src/IceTargetLowering.h
+++ b/src/IceTargetLowering.h
@@ -287,9 +287,10 @@
   /// before returning.
   virtual void postLower() {}
 
-  /// Find two-address non-SSA instructions and set the DestNonKillable flag to
-  /// keep liveness analysis consistent.
-  void inferTwoAddress();
+  /// Find (non-SSA) instructions where the Dest variable appears in some source
+  /// operand, and set the IsDestRedefined flag.  This keeps liveness analysis
+  /// consistent.
+  void markRedefinitions();
 
   /// Make a pass over the Cfg to determine which variables need stack slots and
   /// place them in a sorted list (SortedSpilledVariables). Among those, vars,
@@ -348,9 +349,7 @@
     Context.insert(InstBundleLock::create(Func, BundleOption));
   }
   void _bundle_unlock() { Context.insert(InstBundleUnlock::create(Func)); }
-  void _set_dest_nonkillable() {
-    Context.getLastInserted()->setDestNonKillable();
-  }
+  void _set_dest_redefined() { Context.getLastInserted()->setDestRedefined(); }
 
   bool shouldOptimizeMemIntrins();
 
diff --git a/src/IceTargetLoweringARM32.cpp b/src/IceTargetLoweringARM32.cpp
index f92160b..b549501 100644
--- a/src/IceTargetLoweringARM32.cpp
+++ b/src/IceTargetLoweringARM32.cpp
@@ -1504,7 +1504,7 @@
       _sub(T2, Src1RLo, _32);
       _cmp(T2, _0);
       _lsl(TA_Hi, Src0RLo, T2, CondARM32::GE);
-      _set_dest_nonkillable();
+      _set_dest_redefined();
       _lsl(TA_Lo, Src0RLo, Src1RLo);
       _mov(DestLo, TA_Lo);
       _mov(DestHi, TA_Hi);
@@ -1555,11 +1555,11 @@
       _cmp(T2, _0);
       if (IsAshr) {
         _asr(TA_Lo, Src0RHi, T2, CondARM32::GE);
-        _set_dest_nonkillable();
+        _set_dest_redefined();
         _asr(TA_Hi, Src0RHi, Src1RLo);
       } else {
         _lsr(TA_Lo, Src0RHi, T2, CondARM32::GE);
-        _set_dest_nonkillable();
+        _set_dest_redefined();
         _lsr(TA_Hi, Src0RHi, Src1RLo);
       }
       _mov(DestLo, TA_Lo);
@@ -2304,7 +2304,7 @@
     case IceType_v16i8:
     case IceType_v4f32:
     case IceType_v4i32: {
-      // avoid cryptic liveness errors
+      // avoid liveness errors
       Variable *T = makeReg(DestType);
       Context.insert(InstFakeDef::create(Func, T, legalizeToReg(Src0)));
       _mov(Dest, T);
@@ -2388,15 +2388,17 @@
   if (CC0 != CondARM32::kNone) {
     _mov(T, One, CC0);
     // If this mov is not a maybe mov, but an actual mov (i.e., CC0 == AL), we
-    // don't want to set_dest_nonkillable so that liveness + dead-code
+    // don't want to _set_dest_redefined so that liveness + dead-code
     // elimination will get rid of the previous assignment (i.e., T = 0) above.
+    // TODO(stichnot,jpp): We should be able to conditionally create the "T=0"
+    // instruction based on CC0, instead of relying on DCE to remove it.
     if (CC0 != CondARM32::AL)
-      _set_dest_nonkillable();
+      _set_dest_redefined();
   }
   if (CC1 != CondARM32::kNone) {
     assert(CC0 != CondARM32::kNone);
     assert(CC1 != CondARM32::AL);
-    _mov_nonkillable(T, One, CC1);
+    _mov_redefined(T, One, CC1);
   }
   _mov(Dest, T);
 }
@@ -2475,7 +2477,7 @@
       _cmp(Src0Lo, Src1LoRF, CondARM32::EQ);
     }
     _mov(T, One, TableIcmp64[Index].C1);
-    _mov_nonkillable(T, Zero, TableIcmp64[Index].C2);
+    _mov_redefined(T, Zero, TableIcmp64[Index].C2);
     _mov(Dest, T);
     return;
   }
@@ -2531,7 +2533,7 @@
     Operand *Src1RF = legalize(Src1, Legal_Reg | Legal_Flex);
     _cmp(Src0R, Src1RF);
   }
-  _mov_nonkillable(T, One, getIcmp32Mapping(Inst->getCondition()));
+  _mov_redefined(T, One, getIcmp32Mapping(Inst->getCondition()));
   _mov(Dest, T);
   return;
 }
@@ -2753,7 +2755,7 @@
   case Intrinsics::Stackrestore: {
     Variable *SP = getPhysicalRegister(RegARM32::Reg_sp);
     Operand *Val = legalize(Instr->getArg(0), Legal_Reg | Legal_Flex);
-    _mov_nonkillable(SP, Val);
+    _mov_redefined(SP, Val);
     return;
   }
   case Intrinsics::Trap:
@@ -2783,9 +2785,9 @@
     _add(T2, T, ThirtyTwo);
     _clz(T2, ValHiR, CondARM32::NE);
     // T2 is actually a source as well when the predicate is not AL (since it
-    // may leave T2 alone). We use set_dest_nonkillable to prolong the liveness
+    // may leave T2 alone). We use _set_dest_redefined to prolong the liveness
     // of T2 as if it was used as a source.
-    _set_dest_nonkillable();
+    _set_dest_redefined();
     _mov(DestLo, T2);
     Variable *T3 = makeReg(Zero->getType());
     _mov(T3, Zero);
@@ -2893,7 +2895,7 @@
     Variable *TLo = makeReg(SrcFLo->getType());
     _mov(TLo, SrcFLo);
     Operand *SrcTLo = legalize(loOperand(SrcT), Legal_Reg | Legal_Flex);
-    _mov_nonkillable(TLo, SrcTLo, Cond);
+    _mov_redefined(TLo, SrcTLo, Cond);
     _mov(DestLo, TLo);
     // Set the high portion.
     Variable *DestHi = llvm::cast<Variable>(hiOperand(Dest));
@@ -2901,7 +2903,7 @@
     Variable *THi = makeReg(SrcFHi->getType());
     _mov(THi, SrcFHi);
     Operand *SrcTHi = legalize(hiOperand(SrcT), Legal_Reg | Legal_Flex);
-    _mov_nonkillable(THi, SrcTHi, Cond);
+    _mov_redefined(THi, SrcTHi, Cond);
     _mov(DestHi, THi);
     return;
   }
@@ -2914,7 +2916,7 @@
     SrcT = legalizeToReg(SrcT);
     assert(DestTy == SrcT->getType());
     _mov(T, SrcT, Cond);
-    _set_dest_nonkillable();
+    _set_dest_redefined();
     _mov(Dest, T);
     return;
   }
@@ -2923,7 +2925,7 @@
   Variable *T = makeReg(SrcF->getType());
   _mov(T, SrcF);
   SrcT = legalize(SrcT, Legal_Reg | Legal_Flex);
-  _mov_nonkillable(T, SrcT, Cond);
+  _mov_redefined(T, SrcT, Cond);
   _mov(Dest, T);
 }
 
@@ -3259,7 +3261,7 @@
 void TargetARM32::postLower() {
   if (Ctx->getFlags().getOptLevel() == Opt_m1)
     return;
-  inferTwoAddress();
+  markRedefinitions();
 }
 
 void TargetARM32::makeRandomRegisterPermutation(
diff --git a/src/IceTargetLoweringARM32.h b/src/IceTargetLoweringARM32.h
index a1f37a6..91db6bc 100644
--- a/src/IceTargetLoweringARM32.h
+++ b/src/IceTargetLoweringARM32.h
@@ -282,10 +282,10 @@
     assert(Dest != nullptr);
     Context.insert(InstARM32Mov::create(Func, Dest, Src0, Pred));
   }
-  void _mov_nonkillable(Variable *Dest, Operand *Src0,
-                        CondARM32::Cond Pred = CondARM32::AL) {
+  void _mov_redefined(Variable *Dest, Operand *Src0,
+                      CondARM32::Cond Pred = CondARM32::AL) {
     Inst *NewInst = InstARM32Mov::create(Func, Dest, Src0, Pred);
-    NewInst->setDestNonKillable();
+    NewInst->setDestRedefined();
     Context.insert(NewInst);
   }
   /// The Operand can only be a 16-bit immediate or a ConstantRelocatable (with
diff --git a/src/IceTargetLoweringMIPS32.cpp b/src/IceTargetLoweringMIPS32.cpp
index 22c3743..98a698c 100644
--- a/src/IceTargetLoweringMIPS32.cpp
+++ b/src/IceTargetLoweringMIPS32.cpp
@@ -658,7 +658,7 @@
   if (Ctx->getFlags().getOptLevel() == Opt_m1)
     return;
   // Find two-address non-SSA instructions where Dest==Src0, and set the
-  // DestNonKillable flag to keep liveness analysis consistent.
+  // IsDestRedefined flag to keep liveness analysis consistent.
   UnimplementedError(Func->getContext()->getFlags());
 }
 
diff --git a/src/IceTargetLoweringX86Base.h b/src/IceTargetLoweringX86Base.h
index d96aa4f..4875e65 100644
--- a/src/IceTargetLoweringX86Base.h
+++ b/src/IceTargetLoweringX86Base.h
@@ -374,7 +374,7 @@
     // Mark eax as possibly modified by cmpxchg.
     Context.insert(
         InstFakeDef::create(Func, Eax, llvm::dyn_cast<Variable>(DestOrAddr)));
-    _set_dest_nonkillable();
+    _set_dest_redefined();
     Context.insert(InstFakeUse::create(Func, Eax));
   }
   void _cmpxchg8b(typename Traits::X86OperandMem *Addr, Variable *Edx,
@@ -383,10 +383,10 @@
                                                     Ebx, Locked));
     // Mark edx, and eax as possibly modified by cmpxchg8b.
     Context.insert(InstFakeDef::create(Func, Edx));
-    _set_dest_nonkillable();
+    _set_dest_redefined();
     Context.insert(InstFakeUse::create(Func, Edx));
     Context.insert(InstFakeDef::create(Func, Eax));
-    _set_dest_nonkillable();
+    _set_dest_redefined();
     Context.insert(InstFakeUse::create(Func, Eax));
   }
   void _cvt(Variable *Dest, Operand *Src0,
@@ -447,9 +447,9 @@
       Dest = makeReg(Src0->getType(), RegNum);
     Context.insert(Traits::Insts::Mov::create(Func, Dest, Src0));
   }
-  void _mov_nonkillable(Variable *Dest, Operand *Src0) {
+  void _mov_redefined(Variable *Dest, Operand *Src0) {
     Inst *NewInst = Traits::Insts::Mov::create(Func, Dest, Src0);
-    NewInst->setDestNonKillable();
+    NewInst->setDestRedefined();
     Context.insert(NewInst);
   }
   void _movd(Variable *Dest, Operand *Src0) {
@@ -618,7 +618,7 @@
     // a FakeDef followed by a FakeUse.
     Context.insert(
         InstFakeDef::create(Func, Src, llvm::dyn_cast<Variable>(Dest)));
-    _set_dest_nonkillable();
+    _set_dest_redefined();
     Context.insert(InstFakeUse::create(Func, Src));
   }
   void _xchg(Operand *Dest, Variable *Src) {
@@ -627,7 +627,7 @@
     // FakeDef/FakeUse.
     Context.insert(
         InstFakeDef::create(Func, Src, llvm::dyn_cast<Variable>(Dest)));
-    _set_dest_nonkillable();
+    _set_dest_redefined();
     Context.insert(InstFakeUse::create(Func, Src));
   }
   void _xor(Variable *Dest, Operand *Src0) {
diff --git a/src/IceTargetLoweringX86BaseImpl.h b/src/IceTargetLoweringX86BaseImpl.h
index ebdfb1e..477c9f6 100644
--- a/src/IceTargetLoweringX86BaseImpl.h
+++ b/src/IceTargetLoweringX86BaseImpl.h
@@ -525,20 +525,19 @@
       //   x = FakeDef
       //   RMW <op>, addr, other, x
       //   b = Store b, addr, x
-      // Note that inferTwoAddress() makes sure setDestNonKillable() gets
-      // called on the updated Store instruction, to avoid liveness problems
-      // later.
+      // Note that inferTwoAddress() makes sure setDestRedefined() gets called
+      // on the updated Store instruction, to avoid liveness problems later.
       //
       // With this transformation, the Store instruction acquires a Dest
       // variable and is now subject to dead code elimination if there are no
-      // more uses of "b".  Variable "x" is a beacon for determining whether
-      // the Store instruction gets dead-code eliminated.  If the Store
-      // instruction is eliminated, then it must be the case that the RMW
-      // instruction ends x's live range, and therefore the RMW instruction
-      // will be retained and later lowered.  On the other hand, if the RMW
-      // instruction does not end x's live range, then the Store instruction
-      // must still be present, and therefore the RMW instruction is ignored
-      // during lowering because it is redundant with the Store instruction.
+      // more uses of "b".  Variable "x" is a beacon for determining whether the
+      // Store instruction gets dead-code eliminated.  If the Store instruction
+      // is eliminated, then it must be the case that the RMW instruction ends
+      // x's live range, and therefore the RMW instruction will be retained and
+      // later lowered.  On the other hand, if the RMW instruction does not end
+      // x's live range, then the Store instruction must still be present, and
+      // therefore the RMW instruction is ignored during lowering because it is
+      // redundant with the Store instruction.
       //
       // Note that if "a" has further uses, the RMW transformation may still
       // trigger, resulting in two loads and one store, which is worse than the
@@ -1034,19 +1033,16 @@
     const uint16_t Shift = 3; // log2(9-1)
     _lea(T,
          Traits::X86OperandMem::create(Func, IceType_void, T, Zero, T, Shift));
-    _set_dest_nonkillable();
   }
   for (uint32_t i = 0; i < Count5; ++i) {
     const uint16_t Shift = 2; // log2(5-1)
     _lea(T,
          Traits::X86OperandMem::create(Func, IceType_void, T, Zero, T, Shift));
-    _set_dest_nonkillable();
   }
   for (uint32_t i = 0; i < Count3; ++i) {
     const uint16_t Shift = 1; // log2(3-1)
     _lea(T,
          Traits::X86OperandMem::create(Func, IceType_void, T, Zero, T, Shift));
-    _set_dest_nonkillable();
   }
   if (Count2) {
     _shl(T, Ctx->getConstantInt(Ty, Count2));
@@ -1216,11 +1212,10 @@
       _shl(T_2, T_1);
       _test(T_1, BitTest);
       _br(Traits::Cond::Br_e, Label);
-      // T_2 and T_3 are being assigned again because of the intra-block
-      // control flow, so we need the _mov_nonkillable variant to avoid
-      // liveness problems.
-      _mov_nonkillable(T_3, T_2);
-      _mov_nonkillable(T_2, Zero);
+      // T_2 and T_3 are being assigned again because of the intra-block control
+      // flow, so we need the _mov_redefined variant to avoid liveness problems.
+      _mov_redefined(T_3, T_2);
+      _mov_redefined(T_2, Zero);
     } break;
     case InstArithmetic::Lshr: {
       // a=b>>c (unsigned) ==>
@@ -1235,11 +1230,10 @@
       _shr(T_3, T_1);
       _test(T_1, BitTest);
       _br(Traits::Cond::Br_e, Label);
-      // T_2 and T_3 are being assigned again because of the intra-block
-      // control flow, so we need the _mov_nonkillable variant to avoid
-      // liveness problems.
-      _mov_nonkillable(T_2, T_3);
-      _mov_nonkillable(T_3, Zero);
+      // T_2 and T_3 are being assigned again because of the intra-block control
+      // flow, so we need the _mov_redefined variant to avoid liveness problems.
+      _mov_redefined(T_2, T_3);
+      _mov_redefined(T_3, Zero);
     } break;
     case InstArithmetic::Ashr: {
       // a=b>>c (signed) ==>
@@ -1255,11 +1249,11 @@
       _sar(T_3, T_1);
       _test(T_1, BitTest);
       _br(Traits::Cond::Br_e, Label);
-      // T_2 and T_3 are being assigned again because of the intra-block
-      // control flow, so T_2 needs the _mov_nonkillable variant to avoid
-      // liveness problems. T_3 doesn't need special treatment because it is
-      // reassigned via _sar instead of _mov.
-      _mov_nonkillable(T_2, T_3);
+      // T_2 and T_3 are being assigned again because of the intra-block control
+      // flow, so T_2 needs the _mov_redefined variant to avoid liveness
+      // problems. T_3 doesn't need special treatment because it is reassigned
+      // via _sar instead of _mov.
+      _mov_redefined(T_2, T_3);
       _sar(T_3, SignExtend);
     } break;
     }
@@ -2615,7 +2609,7 @@
     }
     Constant *NonDefault =
         Ctx->getConstantInt32(!Traits::TableFcmp[Index].Default);
-    _mov_nonkillable(Dest, NonDefault);
+    _mov_redefined(Dest, NonDefault);
     Context.insert(Label);
   }
 }
@@ -2776,7 +2770,7 @@
   _cmp(Src0LoRM, Src1LoRI);
   _br(Traits::TableIcmp64[Index].C3, LabelTrue);
   Context.insert(LabelFalse);
-  _mov_nonkillable(Dest, Zero);
+  _mov_redefined(Dest, Zero);
   Context.insert(LabelTrue);
 }
 
@@ -3249,7 +3243,7 @@
   case Intrinsics::Stackrestore: {
     Variable *esp =
         Func->getTarget()->getPhysicalRegister(Traits::RegisterSet::Reg_esp);
-    _mov_nonkillable(esp, Instr->getArg(0));
+    _mov_redefined(esp, Instr->getArg(0));
     return;
   }
   case Intrinsics::Trap:
@@ -4388,7 +4382,7 @@
     _mov(Dest, SrcT);
     _br(Cond, Label);
     SrcF = legalize(SrcF, Legal_Reg | Legal_Imm);
-    _mov_nonkillable(Dest, SrcF);
+    _mov_redefined(Dest, SrcF);
     Context.insert(Label);
     return;
   }
@@ -5224,7 +5218,7 @@
 template <class Machine> void TargetX86Base<Machine>::postLower() {
   if (Ctx->getFlags().getOptLevel() == Opt_m1)
     return;
-  inferTwoAddress();
+  markRedefinitions();
 }
 
 template <class Machine>
@@ -5311,9 +5305,6 @@
       Constant *Offset = Ctx->getConstantInt(IceType_i32, 0 - Cookie);
       _lea(Reg, Traits::X86OperandMem::create(Func, IceType_i32, Reg, Offset,
                                               nullptr, 0));
-      // make sure liveness analysis won't kill this variable, otherwise a
-      // liveness assertion will be triggered.
-      _set_dest_nonkillable();
       if (Immediate->getType() != IceType_i32) {
         Variable *TruncReg = makeReg(Immediate->getType(), RegNum);
         _mov(TruncReg, Reg);
@@ -5400,11 +5391,6 @@
         // use-def chain. So we add RegNum argument here.
         Variable *RegTemp = makeReg(MemOperand->getOffset()->getType(), RegNum);
         _lea(RegTemp, TempMemOperand);
-        // As source operand doesn't use the dstreg, we don't need to add
-        // _set_dest_nonkillable(). But if we use the same Dest Reg, that is,
-        // with RegNum assigned, we should add this _set_dest_nonkillable()
-        if (RegNum != Variable::NoRegister)
-          _set_dest_nonkillable();
 
         typename Traits::X86OperandMem *NewMemOperand =
             Traits::X86OperandMem::create(Func, MemOperand->getType(), RegTemp,
@@ -5457,7 +5443,6 @@
                   Func, MemOperand->getType(), MemOperand->getBase(), nullptr,
                   RegTemp, 0, MemOperand->getSegmentRegister());
           _lea(RegTemp, CalculateOperand);
-          _set_dest_nonkillable();
         }
         typename Traits::X86OperandMem *NewMemOperand =
             Traits::X86OperandMem::create(Func, MemOperand->getType(), RegTemp,