diff --git a/src/IceCfg.cpp b/src/IceCfg.cpp
index 847563c..58d7957 100644
--- a/src/IceCfg.cpp
+++ b/src/IceCfg.cpp
@@ -273,9 +273,6 @@
       InstNumberT FirstInstNum = getNextInstNumber();
       (*I)->renumberInstructions();
       InstNumberT LastInstNum = getNextInstNumber() - 1;
-      // TODO(stichnot): May be able to speed up liveness and live range
-      // calculation by having it consider only pre-colored or infinite-weight
-      // variables.  Could also simplify LinearScan::initForInfOnly() that way.
       (*I)->liveness(getLiveness());
       (*I)->livenessAddIntervals(getLiveness(), FirstInstNum, LastInstNum);
     }
diff --git a/src/IceCfgNode.cpp b/src/IceCfgNode.cpp
index f319041..44e9d3e 100644
--- a/src/IceCfgNode.cpp
+++ b/src/IceCfgNode.cpp
@@ -580,6 +580,8 @@
     Live |= Liveness->getLiveIn(Succ);
     // Mark corresponding argument of phis in successor as live.
     for (Inst &I : Succ->Phis) {
+      if (I.isDeleted())
+        continue;
       auto Phi = llvm::dyn_cast<InstPhi>(&I);
       Phi->livenessPhiOperand(Live, this, Liveness);
     }
@@ -698,6 +700,9 @@
     InstNumberT LE = i == i2 ? IEB->second : LastInstNum + 1;
 
     Variable *Var = Liveness->getVariable(i, this);
+    // TODO(stichnot): Push getIgnoreLiveness() into the initialization of
+    // Liveness::RangeMask so that LiveBegin and LiveEnd never even reference
+    // such variables.
     if (!Var->getIgnoreLiveness()) {
       if (LB > LE) {
         Var->addLiveRange(FirstInstNum, LE, 1);
@@ -720,7 +725,8 @@
   for (int i = LiveInAndOut.find_first(); i != -1;
        i = LiveInAndOut.find_next(i)) {
     Variable *Var = Liveness->getVariable(i, this);
-    Var->addLiveRange(FirstInstNum, LastInstNum + 1, 1);
+    if (Liveness->getRangeMask(Var->getIndex()))
+      Var->addLiveRange(FirstInstNum, LastInstNum + 1, 1);
   }
 }
 
diff --git a/src/IceInst.cpp b/src/IceInst.cpp
index 900b408..4b89eb7 100644
--- a/src/IceInst.cpp
+++ b/src/IceInst.cpp
@@ -183,7 +183,7 @@
     if (Live[VarNum]) {
       if (!isDestNonKillable()) {
         Live[VarNum] = false;
-        if (LiveBegin) {
+        if (LiveBegin && Liveness->getRangeMask(Dest->getIndex())) {
           LiveBegin->push_back(std::make_pair(VarNum, InstNumber));
         }
       }
@@ -223,7 +223,7 @@
           // when LiveEnd[VarNum]==0 (sentinel value).  Note that it's
           // OK to set LiveBegin multiple times because of the
           // backwards traversal.
-          if (LiveEnd) {
+          if (LiveEnd && Liveness->getRangeMask(Var->getIndex())) {
             // Ideally, we would verify that VarNum wasn't already
             // added in this block, but this can't be done very
             // efficiently with LiveEnd as a vector.  Instead,
diff --git a/src/IceLiveness.cpp b/src/IceLiveness.cpp
index da9b23d..a1de893 100644
--- a/src/IceLiveness.cpp
+++ b/src/IceLiveness.cpp
@@ -100,6 +100,17 @@
     // LiveBegin and LiveEnd are reinitialized before each pass over
     // the block.
   }
+
+  // Initialize the bitmask of which variables to track.
+  RangeMask.resize(NumVars);
+  RangeMask.set(0, NumVars);
+  if (!IsFullInit) {
+    // Reset initial variables that are not pre-colored or infinite-weight.
+    for (auto I = Func->getVariables().begin(); I != FirstVar; ++I) {
+      Variable *Var = *I;
+      RangeMask[Var->getIndex()] = (Var->hasReg() || Var->getWeight().isInf());
+    }
+  }
 }
 
 void Liveness::init() {
diff --git a/src/IceLiveness.h b/src/IceLiveness.h
index da2c52e..895138d 100644
--- a/src/IceLiveness.h
+++ b/src/IceLiveness.h
@@ -96,6 +96,7 @@
     resize(Index);
     return &Nodes[Index].LiveEnd;
   }
+  bool getRangeMask(SizeT Index) const { return RangeMask[Index]; }
 
 private:
   void initInternal(NodeList::const_iterator FirstNode,
@@ -116,6 +117,9 @@
   /// LiveToVarMap is analogous to LivenessNode::LiveToVarMap, but for
   /// non-local variables.
   std::vector<Variable *> LiveToVarMap;
+  /// RangeMask[Variable::Number] indicates whether we want to track that
+  /// Variable's live range.
+  llvm::BitVector RangeMask;
 };
 
 } // end of namespace Ice
diff --git a/src/IceRegAlloc.cpp b/src/IceRegAlloc.cpp
index fad3d01..c651ae2 100644
--- a/src/IceRegAlloc.cpp
+++ b/src/IceRegAlloc.cpp
@@ -107,10 +107,6 @@
     // it was never referenced.
     if (Var->getLiveRange().isEmpty())
       continue;
-    // Post phi lowering register allocation is only concerned with variables
-    // that are infinite-weight or pre-colored.
-    if (Kind == RAK_Phi && !Var->getWeight().isInf() && !Var->hasReg())
-      continue;
     Var->untrimLiveRange();
     Unhandled.push_back(Var);
     if (Var->hasReg()) {