Index: llvm/include/llvm/Transforms/IPO/Attributor.h
===================================================================
--- llvm/include/llvm/Transforms/IPO/Attributor.h
+++ llvm/include/llvm/Transforms/IPO/Attributor.h
@@ -97,6 +97,7 @@
 #ifndef LLVM_TRANSFORMS_IPO_ATTRIBUTOR_H
 #define LLVM_TRANSFORMS_IPO_ATTRIBUTOR_H
 
+#include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/SCCIterator.h"
 #include "llvm/ADT/SetVector.h"
@@ -2955,6 +2956,199 @@
   static const char ID;
 };
 
+static const APInt EmptyKey, TombstoneKey;
+
+// Provide DenseMapInfo for APInt.
+template <> struct DenseMapInfo<APInt> : DenseMapInfo<void *> {
+  static inline APInt getEmptyKey() { return EmptyKey; }
+  static inline APInt getTombstoneKey() { return TombstoneKey; }
+  static unsigned getHashValue(const APInt &Val) {
+    return (unsigned)Val.getLimitedValue();
+  }
+  static bool isEqual(const APInt &LHS, const APInt &RHS) { return LHS == RHS; }
+};
+
+struct PotentialValueSet {
+  using SetTy = DenseSet<APInt>;
+  PotentialValueSet(bool isFull) : isFull(isFull) {}
+  PotentialValueSet(const SetTy &PS) : isFull(false) { Set = PS; }
+  bool operator==(const PotentialValueSet &RHS) {
+    if (isFull && RHS.isFull)
+      return true;
+    return Set == RHS.Set;
+  }
+  void insert(const APInt &C) {
+    if (isFull)
+      return;
+    Set.insert(C);
+  }
+
+  /// take union of L and R
+  void unionWith(const PotentialValueSet &R) {
+    /// if this is a full set, do nothing
+    if (isFull)
+      return;
+    /// if R is full set, change L to a full set
+    if (R.isFull) {
+      isFull = true;
+      return;
+    }
+    for (auto &e : R.Set) {
+      Set.insert(e);
+    }
+  }
+
+  /// take intersection of L and R
+  void intersectWith(const PotentialValueSet &R) {
+    /// if R is a full set, do nothing
+    if (R.isFull)
+      return;
+    /// if this is a full set, change this to R
+    if (isFull) {
+      *this = R;
+      return;
+    }
+    SmallVector<APInt, 8> eraseList;
+    for (auto &e : Set) {
+      if (!R.Set.count(e))
+        eraseList.push_back(e);
+    }
+    for (auto &e : eraseList) {
+      Set.erase(e);
+    }
+  }
+  bool isFull;
+  SetTy Set;
+};
+
+struct PotentialValuesState : AbstractState {
+
+  using SetTy = DenseSet<APInt>;
+
+  // first boolean value indicates wheather the set is a full set or not
+  using StateTy = PotentialValueSet;
+
+  PotentialValuesState(uint32_t BitWidth)
+      : BitWidth(BitWidth), Known(true), Assumed(false) {}
+
+  PotentialValuesState(const StateTy &PS) : Known(true), Assumed(PS) {}
+
+  /// See AbstractState::isValidState()
+  /// If the number of potential values become no less than 7, we give up
+  bool isValidState() const override {
+    return BitWidth > 0 && !Assumed.isFull && Assumed.Set.size() < 7;
+  }
+
+  /// See AbstractState::isAtFixpoint()
+  bool isAtFixpoint() const override {
+    if (Known.isFull && Assumed.isFull)
+      return true;
+    if (Known.isFull || Assumed.isFull)
+      return false;
+    return Known.Set == Assumed.Set;
+  }
+
+  ChangeStatus indicateOptimisticFixpoint() override {
+    Known = Assumed;
+    return ChangeStatus::UNCHANGED;
+  }
+
+  ChangeStatus indicatePessimisticFixpoint() override {
+    Assumed = Known;
+    return ChangeStatus::CHANGED;
+  }
+
+  static StateTy getBestState() { return StateTy(/* isFull */ false); }
+  static StateTy getBestState(PotentialValuesState &PVS) {
+    return getBestState();
+  }
+
+  static StateTy getWorstState() { return StateTy(/* isFull */ true); }
+
+  /// Return the known state
+  StateTy getKnown() const { return Known; }
+
+  /// Return the assumed state
+  StateTy getAssumed() const { return Assumed; }
+
+  bool AssumedIsFull() const { return Assumed.isFull; }
+  bool KnownIsFull() const { return Known.isFull; }
+
+  SetTy getAssumedSet() const { return Assumed.Set; }
+
+  SetTy getKnownSet() const { return Known.Set; }
+
+  void unionAssumed(const APInt &C) {
+    Assumed.insert(C);
+    Assumed.intersectWith(Known);
+  }
+
+  void unionAssumed(const StateTy &R) {
+    Assumed.unionWith(R);
+    Assumed.unionWith(Known);
+  }
+
+  void unionAssumed(const PotentialValuesState &PVS) {
+    unionAssumed(PVS.getAssumed());
+  }
+
+  void unionKnown(const StateTy &R) {
+    Known.unionWith(R);
+    Assumed.unionWith(Known);
+  }
+
+  void unionKnown(const PotentialValuesState &PVS) {
+    unionKnown(PVS.getKnown());
+  }
+
+  PotentialValuesState operator^=(const PotentialValuesState &PVS) {
+    unionAssumed(PVS);
+    return *this;
+  }
+
+  PotentialValuesState operator&=(const PotentialValuesState &PVS) {
+    unionKnown(PVS);
+    unionAssumed(PVS);
+    return *this;
+  }
+
+  uint32_t BitWidth;
+  StateTy Known, Assumed;
+};
+
+/// An abstract interface for potential values analysis.
+struct AAPotentialValues
+    : public StateWrapper<PotentialValuesState, AbstractAttribute, uint32_t> {
+  using Base = StateWrapper<PotentialValuesState, AbstractAttribute, uint32_t>;
+  AAPotentialValues(const IRPosition &IRP, Attributor &A)
+      : Base(IRP, IRP.getAssociatedType()->getIntegerBitWidth()) {}
+
+  /// See AbstractAttribute::getState(...).
+  PotentialValuesState &getState() override { return *this; }
+  const AbstractState &getState() const override { return *this; }
+
+  /// Create an abstract attribute view for the position \p IRP.
+  static AAPotentialValues &createForPosition(const IRPosition &IRP,
+                                              Attributor &A);
+
+  /// virtual PotentialValuesState::SetTy &
+  /// getAssumedPotentialValues(Attributor &A,
+  ///                           const Instruction *CtxI = nullptr) const = 0;
+
+  /// virtual PotentialValuesState::SetTy &
+  /// getKnownPotentialValues(Attributor &A,
+  ///                         const Instruction *CtxI = nullptr) const = 0;
+
+  Optional<ConstantInt *>
+  getAssumedConstantInt(Attributor &A,
+                        const Instruction *CtxI = nullptr) const {
+    return nullptr;
+  }
+
+  /// Unique ID (due to the unique address)
+  static const char ID;
+};
+
 /// Run options, used by the pass manager.
 enum AttributorRunOption {
   NONE = 0,
Index: llvm/lib/Transforms/IPO/AttributorAttributes.cpp
===================================================================
--- llvm/lib/Transforms/IPO/AttributorAttributes.cpp
+++ llvm/lib/Transforms/IPO/AttributorAttributes.cpp
@@ -116,6 +116,7 @@
 PIPE_OPERATOR(AAValueConstantRange)
 PIPE_OPERATOR(AAPrivatizablePtr)
 PIPE_OPERATOR(AAUndefinedBehavior)
+PIPE_OPERATOR(AAPotentialValues)
 
 #undef PIPE_OPERATOR
 } // namespace llvm
@@ -1051,9 +1052,10 @@
   // map, NewRVsMap.
   decltype(ReturnedValues) NewRVsMap;
 
-  auto HandleReturnValue = [&](Value *RV, SmallSetVector<ReturnInst *, 4> &RIs) {
-    LLVM_DEBUG(dbgs() << "[AAReturnedValues] Returned value: " << *RV
-                      << " by #" << RIs.size() << " RIs\n");
+  auto HandleReturnValue = [&](Value *RV,
+                               SmallSetVector<ReturnInst *, 4> &RIs) {
+    LLVM_DEBUG(dbgs() << "[AAReturnedValues] Returned value: " << *RV << " by #"
+                      << RIs.size() << " RIs\n");
     CallBase *CB = dyn_cast<CallBase>(RV);
     if (!CB || UnresolvedCalls.count(CB))
       return;
@@ -3424,7 +3426,6 @@
         T.GlobalState &= DS.GlobalState;
       }
 
-
       // For now we do not try to "increase" dereferenceability due to negative
       // indices as we first have to come up with code to deal with loops and
       // for overflows of the dereferenceable bytes.
@@ -4385,6 +4386,25 @@
     return true;
   }
 
+  bool askSimplifiedValueForAAPotentialValues(Attributor &A) {
+    if (!getAssociatedValue().getType()->isIntegerTy())
+      return false;
+
+    const auto &PotentialValuesAA =
+        A.getAAFor<AAPotentialValues>(*this, getIRPosition());
+
+    Optional<ConstantInt *> COpt = PotentialValuesAA.getAssumedConstantInt(A);
+    if (COpt.hasValue()) {
+      if (auto *C = COpt.getValue())
+        SimplifiedAssociatedValue = C;
+      else
+        return false;
+    } else {
+      SimplifiedAssociatedValue = llvm::None;
+    }
+    return true;
+  }
+
   /// See AbstractAttribute::manifest(...).
   ChangeStatus manifest(Attributor &A) override {
     ChangeStatus Changed = ChangeStatus::UNCHANGED;
@@ -7048,6 +7068,232 @@
     STATS_DECLTRACK_CSARG_ATTR(value_range)
   }
 };
+
+/// ------------------ Potential Values Attribute -------------------------
+
+struct AAPotentialValuesImpl : AAPotentialValues {
+  using StateType = PotentialValuesState;
+  AAPotentialValuesImpl(const IRPosition &IRP, Attributor &A)
+      : AAPotentialValues(IRP, A) {}
+  /// See AbstractAttribute::getAsStr().
+  const std::string getAsStr() const override {
+    std::string Str;
+    llvm::raw_string_ostream OS(Str);
+    OS << "potential values<";
+    /// OS << getKnownPotentialValues()->size();
+    OS << " / ";
+    /// OS << getAssumedPotentialValues()->size();
+    OS << ">";
+    return OS.str();
+  }
+  /// See AbstractAttribute::initialize(..).
+  void initialize(Attributor &A) override {}
+
+  static bool calcICmpInst(const ICmpInst *ICI, APInt &LHS, APInt &RHS) {
+    ICmpInst::Predicate Pred = ICI->getPredicate();
+    switch (Pred) {
+    case ICmpInst::ICMP_UGT:
+      return LHS.ugt(RHS);
+    case ICmpInst::ICMP_SGT:
+      return LHS.sgt(RHS);
+    case ICmpInst::ICMP_EQ:
+      return LHS.eq(RHS);
+    case ICmpInst::ICMP_UGE:
+      return LHS.uge(RHS);
+    case ICmpInst::ICMP_SGE:
+      return LHS.sge(RHS);
+    case ICmpInst::ICMP_ULT:
+      return LHS.ult(RHS);
+    case ICmpInst::ICMP_SLT:
+      return LHS.slt(RHS);
+    case ICmpInst::ICMP_NE:
+      return LHS.ne(RHS);
+    case ICmpInst::ICMP_ULE:
+      return LHS.ule(RHS);
+    case ICmpInst::ICMP_SLE:
+      return LHS.sle(RHS);
+    default:
+      llvm_unreachable("Invalid ICmp predicate!");
+    }
+  }
+};
+
+struct AAPotentialValuesArgument final
+    : AAArgumentFromCallSiteArguments<AAPotentialValues, AAPotentialValuesImpl,
+                                      PotentialValuesState> {
+  using Base =
+      AAArgumentFromCallSiteArguments<AAPotentialValues, AAPotentialValuesImpl,
+                                      PotentialValuesState>;
+  AAPotentialValuesArgument(const IRPosition &IRP, Attributor &A)
+      : Base(IRP, A) {}
+
+  /// See AbstractAttribute::initialize(..).
+  void initialize(Attributor &A) override {
+    if (!getAnchorScope() || getAnchorScope()->isDeclaration()) {
+      indicatePessimisticFixpoint();
+    } else {
+      Base::initialize(A);
+    }
+  }
+
+  /// See AbstractAttribute::trackStatistics()
+  void trackStatistics() const override {
+    STATS_DECLTRACK_ARG_ATTR(potential_values)
+  }
+};
+
+struct AAPotentialValuesReturned
+    : AAReturnedFromReturnedValues<AAPotentialValues, AAPotentialValuesImpl> {
+  using Base =
+      AAReturnedFromReturnedValues<AAPotentialValues, AAPotentialValuesImpl>;
+  AAPotentialValuesReturned(const IRPosition &IRP, Attributor &A)
+      : Base(IRP, A) {}
+
+  /// See AbstractAttribute::initialize(...).
+  void initialize(Attributor &A) override {}
+
+  /// See AbstractAttribute::trackStatistics()
+  void trackStatistics() const override {
+    STATS_DECLTRACK_FNRET_ATTR(potential_values)
+  }
+};
+
+struct AAPotentialValuesFloating : AAPotentialValuesImpl {
+  AAPotentialValuesFloating(const IRPosition &IRP, Attributor &A)
+      : AAPotentialValuesImpl(IRP, A) {}
+
+  /// See AbstractAttribute::initialize(..).
+  void initialize(Attributor &A) override {
+    LLVM_DEBUG(dbgs() << "[AAPotentialValues] initialize "
+                      << getAssociatedValue() << "\n");
+    Value &V = getAssociatedValue();
+
+    if (auto *C = dyn_cast<ConstantInt>(&V)) {
+      unionAssumed(C->getValue());
+      indicateOptimisticFixpoint();
+      return;
+    }
+
+    if (isa<UndefValue>(&V)) {
+      indicateOptimisticFixpoint();
+      return;
+    }
+
+    if (isa<BinaryOperator>(&V) || isa<ICmpInst>(&V) || isa<CastInst>(&V))
+      return;
+
+    if (isa<SelectInst>(V) || isa<PHINode>(V))
+      return;
+
+    indicatePessimisticFixpoint();
+
+    LLVM_DEBUG(dbgs() << "[AAPotentialValues] We give up: "
+                      << getAssociatedValue() << "\n");
+  }
+
+  ChangeStatus updateImpl(Attributor &A) override {
+
+    Value &V = getAssociatedValue();
+    Instruction *I = dyn_cast<Instruction>(&V);
+
+    if (auto *ICI = dyn_cast<ICmpInst>(I)) {
+      Value *LHS = ICI->getOperand(0);
+      Value *RHS = ICI->getOperand(1);
+      // TODO: Allow non integers as well.
+      if (!LHS->getType()->isIntegerTy() || !RHS->getType()->isIntegerTy())
+        return indicatePessimisticFixpoint();
+
+      auto &LHSAA =
+          A.getAAFor<AAPotentialValues>(*this, IRPosition::value(*LHS));
+      auto &RHSAA =
+          A.getAAFor<AAPotentialValues>(*this, IRPosition::value(*RHS));
+
+      if (LHSAA.AssumedIsFull() || RHSAA.AssumedIsFull())
+        return indicatePessimisticFixpoint();
+
+      auto LHSAAPVS = LHSAA.getAssumedSet();
+      auto RHSAAPVS = RHSAA.getAssumedSet();
+      bool MaybeTrue = false, MaybeFalse = false;
+      for (auto &L : LHSAAPVS) {
+        for (auto &R : RHSAAPVS) {
+          bool CmpResult = calcICmpInst(ICI, L, R);
+          MaybeTrue |= CmpResult;
+          MaybeFalse |= !CmpResult;
+        }
+      }
+      auto AssumedBefore = getAssumed();
+      if (MaybeTrue)
+        unionAssumed(APInt(/* numBits */ 1, /* val */ 1));
+      if (MaybeFalse)
+        unionAssumed(APInt(/* numBits */ 1, /* val */ 0));
+      return AssumedBefore == getAssumed() ? ChangeStatus::UNCHANGED
+                                           : ChangeStatus::CHANGED;
+    }
+
+    indicatePessimisticFixpoint();
+
+    return ChangeStatus::CHANGED;
+  }
+
+  /// See AbstractAttribute::trackStatistics()
+  void trackStatistics() const override {
+    STATS_DECLTRACK_FLOATING_ATTR(potential_values)
+  }
+};
+
+struct AAPotentialValuesFunction : AAPotentialValuesImpl {
+  AAPotentialValuesFunction(const IRPosition &IRP, Attributor &A)
+      : AAPotentialValuesImpl(IRP, A) {}
+
+  /// See AbstractAttribute::initialize(...).
+  ChangeStatus updateImpl(Attributor &A) override {
+    llvm_unreachable("AAPotentialValues(Function|CallSite)::updateImpl will "
+                     "not be called");
+  }
+
+  /// See AbstractAttribute::trackStatistics()
+  void trackStatistics() const override {
+    STATS_DECLTRACK_FN_ATTR(potential_values)
+  }
+};
+
+struct AAPotentialValuesCallSite : AAPotentialValuesFunction {
+  AAPotentialValuesCallSite(const IRPosition &IRP, Attributor &A)
+      : AAPotentialValuesFunction(IRP, A) {}
+
+  /// See AbstractAttribute::trackStatistics()
+  void trackStatistics() const override {
+    STATS_DECLTRACK_CS_ATTR(potential_values)
+  }
+};
+
+struct AAPotentialValuesCallSiteReturned
+    : AACallSiteReturnedFromReturned<AAPotentialValues, AAPotentialValuesImpl> {
+  AAPotentialValuesCallSiteReturned(const IRPosition &IRP, Attributor &A)
+      : AACallSiteReturnedFromReturned<AAPotentialValues,
+                                       AAPotentialValuesImpl>(IRP, A) {}
+
+  /// See AbstractAttribute::initialize(...).
+  void initialize(Attributor &A) override {
+    AAPotentialValuesImpl::initialize(A);
+  }
+
+  /// See AbstractAttribute::trackStatistics()
+  void trackStatistics() const override {
+    STATS_DECLTRACK_CSRET_ATTR(potential_values)
+  }
+};
+
+struct AAPotentialValuesCallSiteArgument : AAPotentialValuesFloating {
+  AAPotentialValuesCallSiteArgument(const IRPosition &IRP, Attributor &A)
+      : AAPotentialValuesFloating(IRP, A) {}
+
+  /// See AbstractAttribute::trackStatistics()
+  void trackStatistics() const override {
+    STATS_DECLTRACK_CSARG_ATTR(potential_values)
+  }
+};
+
 } // namespace
 
 const char AAReturnedValues::ID = 0;
@@ -7071,6 +7317,7 @@
 const char AAMemoryBehavior::ID = 0;
 const char AAMemoryLocation::ID = 0;
 const char AAValueConstantRange::ID = 0;
+const char AAPotentialValues::ID = 0;
 
 // Macro magic to create the static generator function for attributes that
 // follow the naming scheme.
@@ -7180,6 +7427,7 @@
 CREATE_VALUE_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAAlign)
 CREATE_VALUE_ABSTRACT_ATTRIBUTE_FOR_POSITION(AANoCapture)
 CREATE_VALUE_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAValueConstantRange)
+CREATE_VALUE_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAPotentialValues)
 
 CREATE_ALL_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAValueSimplify)
 CREATE_ALL_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAIsDead)
Index: llvm/test/Transforms/Attributor/potential.ll
===================================================================
--- /dev/null
+++ llvm/test/Transforms/Attributor/potential.ll
@@ -0,0 +1,130 @@
+; RUN: opt -attributor -S < %s | FileCheck %s --check-prefixes=CHECK
+;
+; Test for multiple potential values
+;
+; potential-test 1
+; int iszero(int c) { return c == 0; }
+; int potential_test1(int c) { return iszero(c ? 1 : -1); }
+
+define i32 @potential_test1(i1 %c) {
+; CHECK-LABEL: define i32 @potential_test1
+  %arg = select i1 %c, i32 -1, i32 1
+  %ret = tail call i32 @iszero(i32 %arg)
+  ret i32 %ret
+}
+
+define internal i32 @iszero(i32 %c) {
+  %cmp = icmp eq i32 %c, 0
+  %ret = zext i1 %cmp to i32
+  ret i32 %ret
+}
+
+; potential-test 2
+; 
+; potential values of argument of iszero are {1,-1}
+; potential value of returned value of iszero is 0
+;
+; int call_with_two_values(int x) { return iszero(x) + iszero(-x); }
+; int potential_test2(int x) { return call_with_two_values(1) + call_with_two_values(-1); }
+
+define i32 @potential_test2() {
+  %csret1 = tail call i32 @call_with_two_values(i32 1)
+  %csret2 = tail call i32 @call_with_two_values(i32 -1)
+  %ret = add nsw i32 %csret1, %csret2
+  ret i32 %ret
+}
+
+define internal i32 @call_with_two_values(i32 %c) {
+  %csret1 = tail call i32 @iszero(i32 %c)
+  %minusc = sub nsw i32 0, %c
+  %csret2 = tail call i32 @iszero(i32 %minusc)
+  %ret = add nsw i32 %csret1, %csret2
+  ret i32 %ret
+}
+
+
+; potential-test 3
+;
+; potential values of returned value of f are {0,1}
+; potential values of argument of g are {0,1}
+; potential value of returned value of g is 1
+; then returned value of g can be simplified
+;
+; int zero_or_one(int c) { return c < 2; }
+; int potential_test3() { return zero_or_one(iszero(0))+zero_or_one(iszero(1)); }
+
+
+define i32 @potential_test3(i32 %0) {
+  %2 = tail call i32 @iszero(i32 0)
+  %3 = tail call i32 @zero_or_one(i32 %2)
+  %4 = tail call i32 @iszero(i32 1)
+  %5 = tail call i32 @zero_or_one(i32 %4)
+  %6 = add nsw i32 %5, %3
+  ret i32 %6
+}
+
+define internal i32 @zero_or_one(i32 %0) {
+  %2 = icmp slt i32 %0, 2
+  %3 = zext i1 %2 to i32
+  ret i32 %3
+}
+
+
+; potential-test 4,5
+; 
+; simplified
+; int potential_test4(int c) { return return1or3(c) == 2; }
+; int potential_test5(int c) { return return1or3(c) == return2or4(c); }
+;
+; not simplified
+; int potential_test6(int c) { return return1or3(c) == 3; }
+; int potential_test7(int c) { return return1or3(c) == return3or4(c); }
+
+define i32 @potential_test4(i32 %0) {
+  %2 = tail call i32 @return1or3(i32 %0)
+  %3 = icmp eq i32 %2, 2
+  %4 = zext i1 %3 to i32
+  ret i32 %4
+}
+
+define i32 @potential_test5(i32 %0) {
+  %2 = tail call i32 @return1or3(i32 %0)
+  %3 = tail call i32 @return2or4(i32 %0)
+  %4 = icmp eq i32 %2, %3
+  %5 = zext i1 %4 to i32
+  ret i32 %5
+}
+
+define i32 @potential_test6(i32 %0) {
+  %2 = tail call i32 @return1or3(i32 %0)
+  %3 = icmp eq i32 %2, 3
+  %4 = zext i1 %3 to i32
+  ret i32 %4
+}
+
+define i32 @potential_test7(i32 %0) {
+  %2 = tail call i32 @return1or3(i32 %0)
+  %3 = tail call i32 @return3or4(i32 %0)
+  %4 = icmp eq i32 %2, %3
+  %5 = zext i1 %4 to i32
+  ret i32 %5
+}
+
+define internal i32 @return1or3(i32 %0) {
+  %2 = icmp eq i32 %0, 0
+  %3 = select i1 %2, i32 1, i32 3
+  ret i32 %3
+}
+
+define internal i32 @return2or4(i32 %0) {
+  %2 = icmp eq i32 %0, 0
+  %3 = select i1 %2, i32 2, i32 4
+  ret i32 %3
+}
+
+define internal i32 @return3or4(i32 %0) {
+  %2 = icmp eq i32 %0, 0
+  %3 = select i1 %2, i32 3, i32 4
+  ret i32 %3
+}
+