Index: include/llvm/Analysis/ValueTracking.h
===================================================================
--- include/llvm/Analysis/ValueTracking.h
+++ include/llvm/Analysis/ValueTracking.h
@@ -232,6 +232,22 @@
                             const DataLayout &DL, LoopInfo *LI = nullptr,
                             unsigned MaxLookup = 6);
 
+  /// Trace a value through selects and PHIs, returning the set of possible
+  /// values that V could be. Unlike GetUnderlyingObjects, this does not strip
+  /// away any information - if this returns a single value in Values, that
+  /// value can be used as a replacement for V. For example, given this
+  /// expression (which is the equivalent of a GEP, which GetUnderlyingObjects
+  /// would skip over):
+  ///
+  ///    %1 = add i32 %2, 1
+  ///
+  /// GetUnderlyingValues would return %1, or if %2 was found to be constant,
+  /// %2+1.  This function can recurse through binary operators such as the \c
+  /// add above if the operator has a constant as its right hand operand. It
+  /// will only recurse to a depth of \c MaxRecurse.
+  void GetUnderlyingValues(Value *V, SmallVectorImpl<Value *> &Values,
+                           const DataLayout &DL, unsigned MaxRecurse = 2);
+
   /// onlyUsedByLifetimeMarkers - Return true if the only users of this pointer
   /// are lifetime markers.
   bool onlyUsedByLifetimeMarkers(const Value *V);
Index: lib/Analysis/ValueTracking.cpp
===================================================================
--- lib/Analysis/ValueTracking.cpp
+++ lib/Analysis/ValueTracking.cpp
@@ -3031,6 +3031,71 @@
   return true;
 }
 
+void llvm::GetUnderlyingValues(Value *V, SmallVectorImpl<Value *> &Objects,
+                               const DataLayout &DL, unsigned MaxRecurse) {
+  if (MaxRecurse == 0) {
+    Objects.push_back(V);
+    return;
+  }
+
+  SmallPtrSet<Value *, 4> Visited;
+  SmallVector<Value *, 4> Worklist;
+  Worklist.push_back(V);
+  do {
+    Value *P = Worklist.pop_back_val();
+    if (!Visited.insert(P).second)
+      continue;
+
+    if (auto *SI = dyn_cast<SelectInst>(P)) {
+      Worklist.push_back(SI->getTrueValue());
+      Worklist.push_back(SI->getFalseValue());
+      continue;
+    }
+
+    if (auto *PN = dyn_cast<PHINode>(P)) {
+      for (Value *IncValue : PN->incoming_values())
+        Worklist.push_back(IncValue);
+      continue;
+    }
+
+    if (MaxRecurse > 1)
+      if (auto *BO = dyn_cast<BinaryOperator>(P))
+        // If this operator has a RHS of a constant int, we can possibly
+        // constant fold it if the LHS turns out also to be a constant.
+        if (auto *RHS = dyn_cast<ConstantInt>(BO->getOperand(1))) {
+          SmallVector<Value *, 4> Vs;
+          GetUnderlyingValues(BO->getOperand(0), Vs, DL, MaxRecurse - 1);
+          if (std::all_of(Vs.begin(), Vs.end(), [](const Value *V) {
+                return isa<ConstantInt>(V);
+              })) {
+            SmallVector<Value *, 4> NewVs;
+            for (auto *V : Vs) {
+              auto *C =
+                  ConstantFoldInstOperands(BO->getOpcode(), V->getType(),
+                                           {cast<ConstantInt>(V), RHS}, DL);
+              if (!C)
+                break;
+              NewVs.push_back(C);
+            }
+            if (NewVs.size() == Vs.size()) {
+              Worklist.insert(Worklist.end(), NewVs.begin(), NewVs.end());
+              continue;
+            }
+          }
+        }
+
+    // See if InstructionSimplify knows any relevant tricks.
+    if (auto *I = dyn_cast<Instruction>(P))
+      // TODO: Acquire a DominatorTree and AssumptionCache and use them.
+      if (auto *Simplified = SimplifyInstruction(I, DL, nullptr)) {
+        Worklist.push_back(Simplified);
+        continue;
+      }
+
+    Objects.push_back(P);
+  } while (!Worklist.empty());
+}
+
 Value *llvm::GetUnderlyingObject(Value *V, const DataLayout &DL,
                                  unsigned MaxLookup) {
   if (!V->getType()->isPointerTy())
Index: lib/Transforms/InstCombine/InstCombineCompares.cpp
===================================================================
--- lib/Transforms/InstCombine/InstCombineCompares.cpp
+++ lib/Transforms/InstCombine/InstCombineCompares.cpp
@@ -2759,9 +2759,29 @@
   }
 
   if (Value *V =
-          SimplifyICmpInst(I.getPredicate(), Op0, Op1, DL, TLI, DT, AC, &I))
+      SimplifyICmpInst(I.getPredicate(), Op0, Op1, DL, TLI, DT, AC, &I))
     return ReplaceInstUsesWith(I, V);
 
+  // If one operand of the compare is constant, can we determine the set of
+  // values the other operand can take? if so, and they're all constant,
+  // fold the compare.
+  if (auto *CRHS = dyn_cast<ConstantInt>(Op1)) {
+    SmallVector<Value *, 4> Values;
+    GetUnderlyingValues(Op0, Values, DL);
+    if (!Values.empty() &&
+        std::all_of(Values.begin(), Values.end(),
+                    [](const Value *V) { return isa<ConstantInt>(V); })) {
+      SmallVector<Constant *, 4> Cs;
+      for (auto *V : Values)
+        Cs.push_back(ConstantFoldCompareInstOperands(
+            I.getPredicate(), cast<Constant>(V), CRHS, DL, TLI));
+
+      if (std::all_of(Cs.begin(), Cs.end(),
+                      [&](const Constant *C) { return C == Cs[0]; }))
+        return ReplaceInstUsesWith(I, Cs[0]);
+    }
+  }
+
   // comparing -val or val with non-zero is the same as just comparing val
   // ie, abs(val) != 0 -> val != 0
   if (I.getPredicate() == ICmpInst::ICMP_NE && match(Op1, m_Zero()))
Index: test/Transforms/InstCombine/icmp.ll
===================================================================
--- test/Transforms/InstCombine/icmp.ll
+++ test/Transforms/InstCombine/icmp.ll
@@ -1672,3 +1672,44 @@
   %cmp = icmp slt i32 %conv, %inc
   ret i1 %cmp
 }
+
+; CHECK-LABEL: @cmp_select
+; CHECK: ret i1 true
+define i1 @cmp_select(i1 %i, i1 %j) {
+entry:
+  br i1 %j, label %one, label %two
+
+one:
+  br label %three
+
+two:
+  br label %three
+  
+three:
+  %z = phi i32 [ 67, %one ], [ 111, %two ]
+  %a = select i1 %i, i32 %z, i32 200
+  %b = add i32 %a, 5
+  %c = icmp slt i32 %b, 256
+  ret i1 %c
+}
+
+; CHECK-LABEL: @cmp_select_negative
+; CHECK-NOT: ret i1 {{true|false}}
+; CHECK: }
+define i1 @cmp_select_negative(i1 %i, i1 %j) {
+entry:
+  br i1 %j, label %one, label %two
+
+one:
+  br label %three
+
+two:
+  br label %three
+  
+three:
+  %z = phi i32 [ 251, %one ], [ 111, %two ]
+  %a = select i1 %i, i32 %z, i32 200
+  %b = add i32 %a, 5
+  %c = icmp slt i32 %b, 256
+  ret i1 %c
+}