[WIP][Attributor] AAPotentialValues Attribute

[okura]

Summary

As discussed in D68934, an abstract attribute which collects all potential values for each value is planned to be introduced. Ultimately, it is expected that functionalities of AAValueSimplify and AAReturnedValues are unified and replaced by this AA, and that value simplification is improved. But we implement it separately from those AAs at first.

This AA collects potential values for each IR position. Currently, only integer values are supported.
The state for this AA is a set. An assumed set is initialized with the empty set (the best state).
To save time and space, we give up collecting potential values when the number of potential values is no less than the given threshold (command line option MaxPotentialValues).

[jdoerfert]

llvm/test/Transforms/Attributor/potential.ll

2

We need RUN lines and use the update test script to get check lines.

[okura]

Add boilerplates and some implementation (but still in progress)

[okura]

• I didn't know what I should use to maintain potential values uniformly for integer type and floating point number type. So I consulted implementation of AAConstantRange and implemented it for integer type only at first. (by using a set of APInt)
• We have to represent a full set (which contains arbitrary possible elements). Because we actually cannot make the set, I represented an internal state by using a pair of boolean variable, which indicates whether the corresponding set is full or not, and a set of APInt.
• Logic in Initialize and updateImpl of each kind of IRPositions is quite incomplete and I haven't made any use of the new AA yet.

[fhahn]

Interesting! Do you have an idea how often this leads to further simplifications? Might be interesting to collect stats on the impact on the test-suite and compile-time/memory impact, as this potentially could be quite expensive to maintain.

[jdoerfert]

In D80991#2079013, @fhahn wrote:

Interesting! Do you have an idea how often this leads to further simplifications? Might be interesting to collect stats on the impact on the test-suite and compile-time/memory impact, as this potentially could be quite expensive to maintain.

Fair point, not trivial to do "right now" though as the real users are missing.

First, the good thing is, this can easily be opt-on, if you blacklist this AA, or not seed it initially, you will never spend any time tracking stuff.
The are two benefits of this I imagine, (1) liveness, (2) versioning. The advanced liveness + value simplification patch is pending and there is even more opportunities once this is in.
Versioning is something we are just now exploring and we will need to wait for some (deep) wrapper stuff and call site specific liveness first.

Long story short, we should do some memory and compile time tracking now but before we get more users the results might not be too interesting.

[okura]

• generate CHECK lines for tests
• implement updateImpl and tried to make use of it from AAValueSimplify

From debug output, I think new AA collects potential values correctly, but I was not able to achieve expected simplification in some tests.
In this week, I spent most of time debugging, but I have not found the cause yet.

[okura]

I found why it doesn't work. In 'AAValueSimplify::updateImpl' , sometimes 'askSimplifiedValueForAAPotentialValues' is not called and the dependency between them is not recorded. So I changed it to always call 'askSimplifiedValueForAAPotentialValues'.
I will add logic for binary operators to 'AAPotentialValues::updateImpl'

[jdoerfert]

In D80991#2095399, @okura wrote:

I found why it doesn't work. In 'AAValueSimplify::updateImpl' , sometimes 'askSimplifiedValueForAAPotentialValues' is not called and the dependency between them is not recorded. So I changed it to always call 'askSimplifiedValueForAAPotentialValues'.
I will add logic for binary operators to 'AAPotentialValues::updateImpl'

So you'll update this shortly, right?

llvm/test/Transforms/Attributor/potential.ll

2

^ The different RUN lines are still missing. See the other tests :)

[okura]

In D80991#2096230, @jdoerfert wrote:

In D80991#2095399, @okura wrote:

I found why it doesn't work. In 'AAValueSimplify::updateImpl' , sometimes 'askSimplifiedValueForAAPotentialValues' is not called and the dependency between them is not recorded. So I changed it to always call 'askSimplifiedValueForAAPotentialValues'.
I will add logic for binary operators to 'AAPotentialValues::updateImpl'

So you'll update this shortly, right?

Yes, I'll update this patch soon.

[okura]

I'm sorry for the delayed update. When I add logic for binary operators, I had a new problem and It took me a while to settle.

• add logic for binary operators in AAPotentialValueFloating::updateImpl
• fix fatal mistakes in a method of PotentialValueState
• change whole logic in AAPotentialValuesCallSiteArgument
• confirmed all expected value simplification were achieved by above changes

There remain some unnecessary print statements for debugging. I'll delete it.

[jdoerfert]

llvm/include/llvm/Transforms/IPO/Attributor.h

2980

What is 100 and 101 here? I think the declarations should go into the class below so they are not in global namespace.

2994

Unsure if you need/want to inherit from the void* specialization.

2996

You might want to make this a template class parametrized with MemberTy. Below you can specialize it struct PotentialConstantValueSet : public PotentialValueSet<APInt> {};

3027

Style: replace auto & with const APInt & and e with C maybe. Also no braces.
Check if the set doesn't have a union member already.

3047

This doesn't actually do intersect, I think. If there is no intersect member collect all new value not the ones to be erased. That way it should work more easily. See also set comments above.

3051

Add documentation here. Also explain in the class comment or here what it means for a set to be full.

3069

7 needs to be replaced by a command line option

3144

Do you really need the known state or would a boolean suffice to track if the state is fix and valid? If it's the latter, you can use a BooleanState member for that.

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

3428–3429

Formatting changes should be moved to an [NFC] commit before the patch.

4436

Can we try to merge this function and the one above. Maybe use a template for the type for the queried AA, i mean AAPotentialValues.

4494

We should not eagerly call these but instead try value simplify first. Maybe wrap the two functions above in a wrapper that is called below (line 4539) or merge the two functions above if that makes sense.

4543

Same comment as last.

4627

Same comment as last.

7125

not needed.

7421

Put these large conditionals in separate helper functions please.

llvm/test/Transforms/Attributor/potential.ll

25

YaY! :)

[okura]

• change PotentialValuesSet
• handle division by zero in calculateBinaryOperator
• call askSimplifiedValueFor after value simplifying
• delete unnecessary debug prints
• add comments
• add test for PHINode

I add the threshold as a command-line option, but I got the following error message when I run it.
I don't know the cause and I got stuck. Could you tell me where my mistake is?

: CommandLine Error: Option 'attributor-max-potential-values' registered more than once!
LLVM ERROR: inconsistency in registered CommandLine options

[uenoku]

MaxPotentialValues is defined multiple times if you put the definition to the header.
You have to make it an external variable or declare in AttributorAttributes.cpp

[jdoerfert]

Some high-level comments. I need to go over the logic later on.

llvm/include/llvm/Transforms/IPO/Attributor.h

3071

What you can do is:

1. Put the static value as non-const into the PotentialValueState class below.
2. put the command line option into the cpp file.
3. use the static location as the "location" of the command line option, that is the place the value is put. Search the code for cl::location for examples.

3185

I'm not sure if we really want/need to track the known set here. Maybe I just don't understand what we currently track in it. Feel free to explain :)
If it is "just" to match the design of other states, don't worry. Take the full set as the worst state and remove the known stuff.

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

4400

Could you explain how we could end up with conflicting values? I was expecting we define an order here, ask the first pass, if that fails the second.

The design to put it all in the template helper is very nice!

4708

This looks like something we need to split off. If you add this stand-alone, do we see an effect in the tests, or could you create a test for this?

7118

This looks like the abstract state print code I saw before. Can we reuse it to print the state here?

[okura]

I was able to add MaxPotentialValues as command-line option successfully. Thank you for helpful comments, Hideto and Johannes.

added some comments.

[okura]

llvm/include/llvm/Transforms/IPO/Attributor.h

3185

Known.IsFull is always true in the current implementation, But when the bit width of an value is 1 or 2, we can initialize known set as actual full-set (isFull is false).
By this, the fixpoint state can be reached faster and we may be able to reduce the number of iterations. That's why I left known in here. Is this a bad idea?

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

4400

I noticed that even if the current assumptions contradict, the assumption must be broken eventually. So I'll fix this.

4708

When I modified failed tests, I figured out the cause of unexpected simplification is here. The problem is not directly related to AAPotentialValues, I will split.
(actually related to AAConstantRange). I have a test in which inappropriate simplification occurs. I will make a new patch.

[okura]

This patch is too large and hard to review. So I split off this patch. D83283

[baziotis]

First of all, great patch. Reading the description and the referenced diff, I can't find an explanation about what this patch tries to do, it would be good if you added that. My assumption is:

You try to deduce what potential values can an IR position value get. Currently, it supports only ints (with that assumption I wrote the comments above). Correct?

(Even if you agree with that, please add some explanation about the method you're following)

llvm/include/llvm/Transforms/IPO/Attributor.h

3057

This is something that Johannes can give more insight and also a description for the patch might help but: I guess that what you mean here by "full" is the "top" (or "bottom", depending on how you see it) of a lattice in a data-flow analysis.

Point being, "top" pretty much means "I don't know, it could be anything" and it's a common knowledge for people.

"Full" OTOH, especially without further explanation about what it means, is not that clear IMHO. e.g. can I insert stuff up to a certain point ? When does something becomes full if the set can grow infinitely large ?

3185

I agree with Johannes. OTOH, I'm sorry but I did not understand your comment. First of all, regarding the bit-width, do you mean that e.g. if I have a bit-width of 1, then I know I have only two possible values and so I know the full set ? But what is the "actual" full set ? Even in that case, if you don't know which of the values you have, you still then have pessimistic fix-point (i.e. both values, i.e. isFull = true). No?

[okura]

This patch was split into D83283 and D85632.

llvm/include/llvm/Transforms/IPO/Attributor.h

 //   `InformationCache::getOpcodeInstMapForFunction` interface and eliminate the
 //   need to traverse the IR repeatedly.
 //
 //===----------------------------------------------------------------------===//
 
 #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"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/AssumeBundleQueries.h"
 #include "llvm/Analysis/CFG.h"
 #include "llvm/Analysis/CGSCCPassManager.h"
 #include "llvm/Analysis/CallGraph.h"
 #include "llvm/Analysis/InlineCost.h"
 #include "llvm/Analysis/LazyCallGraph.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/MustExecute.h"
 #include "llvm/Analysis/PostDominators.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/IR/AbstractCallSite.h"
 #include "llvm/IR/ConstantRange.h"
 #include "llvm/IR/PassManager.h"
 #include "llvm/Support/Allocator.h"
+#include "llvm/Support/CommandLine.h"
 #include "llvm/Transforms/Utils/CallGraphUpdater.h"
 
 namespace llvm {
 
 struct Attributor;
 struct AbstractAttribute;
 struct InformationCache;
 struct AAIsDead;
if (RangeV.isEmptySet())
       return llvm::None;
     return nullptr;
   }
 
   /// Unique ID (due to the unique address)
   static const char ID;
 };
 
+/// Provide DenseMapInfo for APInt.
+struct DenseMapAPIntKeyInfo {
+  static inline APInt getEmptyKey() {
+    APInt V(nullptr, 0);
+    V.U.VAL = 0;
+    return V;
+  }
+
+  static inline APInt getTombstoneKey() {
+    APInt V(nullptr, 0);
+    V.U.VAL = 1;
+    return V;
+  }
+
+  static unsigned getHashValue(const APInt &Key) {
+    return static_cast<unsigned>(hash_value(Key));
+  }
+
+  static bool isEqual(const APInt &LHS, const APInt &RHS) {
+    return LHS.getBitWidth() == RHS.getBitWidth() && LHS == RHS;
+  }
+};
+
+/// A class for a set that the size of it can be infinitely large.
+template <typename MemberTy, typename KeyInfo = DenseMapInfo<MemberTy>>
+struct PotentialValueSet {
+  using SetTy = DenseSet<MemberTy, KeyInfo>;
+
+  PotentialValueSet(bool isFull) : isFull(isFull) {}
+
+  PotentialValueSet(const SetTy &PS) : isFull(false) { Set = PS; }
+
+  bool operator==(const PotentialValueSet &RHS) const {
+    if (isFull != RHS.isFull)
+      return false;
+    return Set == RHS.Set;
+  }
+
+  void insert(const MemberTy &C) {
+    if (isFull)
+      return;
+    Set.insert(C);
+  }
+
+  /// take union with 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 (const MemberTy &C : R.Set)
+      Set.insert(C);
+  }
+
+  /// take intersection with 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;
+    }
+    SetTy intersectSet;
+    for (const MemberTy &C : Set) {
+      if (R.Set.count(C))
+        intersectSet.insert(C);
+    }
+    Set = intersectSet;
+  }
+
+  /// This indicates whether the corresponding set is full set or not.
+  /// If this is true, the value of \p Set is meaningless.
+  bool isFull;
+
+  /// When \p isFull is false, this corresponds to the actual set.
+  SetTy Set;
+};
+
+using PotentialConstantIntValueSet =
+    PotentialValueSet<APInt, DenseMapAPIntKeyInfo>;
+
+// static cl::opt<unsigned>
+//     MaxPotentialValues("attributor-max-potential-values", cl::Hidden,
+//                        cl::desc("Maximal number of potential values to be "
+//                                 "tracked for each position."),
+//                        cl::init(7));
+static const unsigned MaxPotentialValues = 7;
+
+/// State for potential values.
+struct PotentialValuesState : AbstractState {
+
+  using SetTy = PotentialConstantIntValueSet::SetTy;
+
+  using StateTy = PotentialConstantIntValueSet;
+
+  PotentialValuesState() : 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 threshold, we give
+  /// up.
+  bool isValidState() const override {
+    return !Assumed.isFull && Assumed.Set.size() < MaxPotentialValues;
+  }
+
+  /// See AbstractState::isAtFixpoint()
+  bool isAtFixpoint() const override { return Assumed == Known; }
+
+  /// See AbstractState::indicateOptimisticFixpoint(...)
+  ChangeStatus indicateOptimisticFixpoint() override {
+    Known = Assumed;
+    return ChangeStatus::UNCHANGED;
+  }
+
+  /// See AbstractState::indicatePessimisticFixpoint(...)
+  ChangeStatus indicatePessimisticFixpoint() override {
+    Assumed = Known;
+    return ChangeStatus::CHANGED;
+  }
+
+  /// Return empty set as the best state of potential values.
+  static StateTy getBestState() { return StateTy(/* isFull */ false); }
+  static StateTy getBestState(PotentialValuesState &PVS) {
+    return getBestState();
+  }
+
+  /// Return full set as the worst state of potential values.
+  static StateTy getWorstState() { return StateTy(/* isFull */ true); }
+
+  /// Return the assumed state.
+  StateTy getAssumed() const { return Assumed; }
+
+  /// Return the known state.
+  StateTy getKnown() const { return Known; }
+
+  /// Return the assumed set is full set or not.
+  bool AssumedIsFull() const { return Assumed.isFull; }
+
+  /// Return the known set is full set or not.
+  bool KnownIsFull() const { return Known.isFull; }
+
+  /// Return the assumed set.
+  /// Note: If AssumedIsFull() is true, this is meaningless.
+  SetTy getAssumedSet() const { return Assumed.Set; }
+
+  /// Return the known set.
+  /// Note: If KnownIsFull() is true, this is meaningless.
+  SetTy getKnownSet() const { return Known.Set; }
+
+  /// Unite assumed set with the passed value.
+  void unionAssumed(const APInt &C) {
+    Assumed.insert(C);
+    Assumed.intersectWith(Known);
+  }
+
+  /// Unite assumed set with the passed state.
+  void unionAssumed(const StateTy &R) {
+    Assumed.unionWith(R);
+    Assumed.intersectWith(Known);
+  }
+
+  /// Unite assumed set with assumed set of the passed state \p PVS.
+  void unionAssumed(const PotentialValuesState &PVS) {
+    unionAssumed(PVS.getAssumed());
+  }
+
+  /// Unite known set with the passed state.
+  void unionKnown(const StateTy &R) {
+    Known.unionWith(R);
+    Assumed.intersectWith(Known);
+  }
+
+  /// Unite known set with known set of the passed state \p PVS.
+  void unionKnown(const PotentialValuesState &PVS) {
+    unionKnown(PVS.getKnown());
+  }
+
+  /// Intersect known set with the passed state.
+  void intersectKnown(const StateTy &R) {
+    Assumed.intersectWith(R);
+    Known.intersectWith(R);
+  }
+
+  /// "Clamp" this state with \p PVS.
+  PotentialValuesState operator^=(const PotentialValuesState &PVS) {
+    unionAssumed(PVS);
+    return *this;
+  }
+
+  PotentialValuesState operator&=(const PotentialValuesState &PVS) {
+    unionKnown(PVS);
+    unionAssumed(PVS);
+    return *this;
+  }
+
+  /// Set representing known set of potential values.
+  StateTy Known;
+
+  /// Set representing assumed set of potential values.
+  StateTy Assumed;
+};
+
+raw_ostream &operator<<(raw_ostream &OS, const PotentialValuesState &R);
+
+/// An abstract interface for potential values analysis.
+struct AAPotentialValues
+    : public StateWrapper<PotentialValuesState, AbstractAttribute> {
+  using Base = StateWrapper<PotentialValuesState, AbstractAttribute>;
+  AAPotentialValues(const IRPosition &IRP, Attributor &A) : Base(IRP) {}
+
+  /// See AbstractAttribute::getState(...).
+  PotentialValuesState &getState() override { return *this; }
+  const PotentialValuesState &getState() const override { return *this; }
+
+  /// Create an abstract attribute view for the position \p IRP.
+  static AAPotentialValues &createForPosition(const IRPosition &IRP,
+                                              Attributor &A);
+
+  /// Return assumed constant for the associated value
+  Optional<ConstantInt *>
+  getAssumedConstantInt(Attributor &A,
+                        const Instruction *CtxI = nullptr) const {
+    if (AssumedIsFull())
+      return nullptr;
+    if (getAssumedSet().size() == 1)
+      return cast<ConstantInt>(
+          ConstantInt::get(getAssociatedType(), *(getAssumedSet().begin())));
+    if (getAssumedSet().size() == 0)
+      return llvm::None;
+
+    return nullptr;
+  }
+
+  /// Unique ID (due to the unique address)
+  static const char ID;
+};
+
 /// Run options, used by the pass manager.
 enum AttributorRunOption {
   NONE = 0,
   MODULE = 1 << 0,
   CGSCC = 1 << 1,
   ALL = MODULE | CGSCC
 };
 
 } // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_IPO_FUNCTIONATTRS_H

llvm/lib/Transforms/IPO/Attributor.cpp

raw_ostream &llvm::operator<<(raw_ostream &OS, const AbstractState &S) {
   return OS << (!S.isValidState() ? "top" : (S.isAtFixpoint() ? "fix" : ""));
 }
 
 raw_ostream &llvm::operator<<(raw_ostream &OS, const AbstractAttribute &AA) {
   AA.print(OS);
   return OS;
 }
 
+raw_ostream &llvm::operator<<(raw_ostream &OS, const PotentialValuesState &S) {
+  OS << "set-state(< {";
+  if (S.KnownIsFull())
+    OS << "full-set";
+  else
+    for (auto &it : S.getKnownSet())
+      OS << it << ", ";
+  OS << "} / {";
+  if (S.AssumedIsFull())
+    OS << "full-set";
+  else
+    for (auto &it : S.getAssumedSet())
+      OS << it << ", ";
+  OS << "} >)";
+
+  return OS;
+}
+
 void AbstractAttribute::print(raw_ostream &OS) const {
   OS << "[P: " << getIRPosition() << "][" << getAsStr() << "][S: " << getState()
      << "]";
 }
 ///}
 
 /// ----------------------------------------------------------------------------
 ///                       Pass (Manager) Boilerplate

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

 PIPE_OPERATOR(AANoFree)
 PIPE_OPERATOR(AAHeapToStack)
 PIPE_OPERATOR(AAReachability)
 PIPE_OPERATOR(AAMemoryBehavior)
 PIPE_OPERATOR(AAMemoryLocation)
 PIPE_OPERATOR(AAValueConstantRange)
 PIPE_OPERATOR(AAPrivatizablePtr)
 PIPE_OPERATOR(AAUndefinedBehavior)
+PIPE_OPERATOR(AAPotentialValues)
 
 #undef PIPE_OPERATOR
 } // namespace llvm
 
 namespace {
 
 static Optional<ConstantInt *>
 getAssumedConstantInt(Attributor &A, const Value &V,
auto VisitValueCB = [&](const Value &V, const Instruction *, DerefState &T,
         bool CanBeNull;
         DerefBytes = Base->getPointerDereferenceableBytes(DL, CanBeNull);
         T.GlobalState.indicatePessimisticFixpoint();
       } else {
         const DerefState &DS = static_cast<const DerefState &>(AA.getState());
         DerefBytes = DS.DerefBytesState.getAssumed();
         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.
       int64_t OffsetSExt = Offset.getSExtValue();
       if (OffsetSExt < 0)
         OffsetSExt = 0;
 
       T.takeAssumedDerefBytesMinimum(
           std::max(int64_t(0), DerefBytes - OffsetSExt));
static bool checkAndUpdate(Attributor &A, const AbstractAttribute &QueryingAA,
     LLVM_DEBUG(dbgs() << "[ValueSimplify] " << QueryingValue
                       << " is assumed to be "
                       << QueryingValueSimplifiedUnwrapped << "\n");
 
     AccumulatedSimplifiedValue = QueryingValueSimplified;
     return true;
   }
 
-  bool askSimplifiedValueForAAValueConstantRange(Attributor &A) {
-    if (!getAssociatedValue().getType()->isIntegerTy())
-      return false;
+  template <typename AAType>
+  void askSimplifiedValueFor(Attributor &A, bool &failAll,
+                             bool &conflictAssumedConstantInt) {
+    if (!getAssociatedType()->isIntegerTy())
+      return;
+
+    const auto &AA =
+        A.getAAFor<AAType>(*this, getIRPosition(), /* TrackDependence */ true,
+                           DepClassTy::OPTIONAL);
 
-    const auto &ValueConstantRangeAA =
-        A.getAAFor<AAValueConstantRange>(*this, getIRPosition());
+    Optional<ConstantInt *> COpt = AA.getAssumedConstantInt(A);
 
-    Optional<ConstantInt *> COpt =
-        ValueConstantRangeAA.getAssumedConstantInt(A);
-    if (COpt.hasValue()) {
-      if (auto *C = COpt.getValue())
-        SimplifiedAssociatedValue = C;
-      else
-        return false;
-    } else {
-      SimplifiedAssociatedValue = llvm::None;
+    if (!COpt.hasValue())
+      failAll = false;
+    else if (auto *C = COpt.getValue()) {
+      if (SimplifiedAssociatedValue.hasValue())
+        conflictAssumedConstantInt |=
+            (C != SimplifiedAssociatedValue.getValue());
+      failAll = false;
     }
-    return true;
+  }
+
+  bool askSimplifiedValueForOtherAAs(Attributor &A) {
+    bool failAll = true;
+    bool conflictAssumedConstantInt = false;
+    askSimplifiedValueFor<AAValueConstantRange>(A, failAll,
+                                                conflictAssumedConstantInt);
+    askSimplifiedValueFor<AAPotentialValues>(A, failAll,
+                                             conflictAssumedConstantInt);
+    return !conflictAssumedConstantInt && !failAll;
   }
 
   /// See AbstractAttribute::manifest(...).
   ChangeStatus manifest(Attributor &A) override {
     ChangeStatus Changed = ChangeStatus::UNCHANGED;
 
     if (SimplifiedAssociatedValue.hasValue() &&
         !SimplifiedAssociatedValue.getValue())
struct AAValueSimplifyImpl : AAValueSimplify {
   /// See AbstractState::indicatePessimisticFixpoint(...).
   ChangeStatus indicatePessimisticFixpoint() override {
     // NOTE: Associated value will be returned in a pessimistic fixpoint and is
     // regarded as known. That's why`indicateOptimisticFixpoint` is called.
     SimplifiedAssociatedValue = &getAssociatedValue();
     indicateOptimisticFixpoint();
     return ChangeStatus::CHANGED;
   }
 
 protected:
   // An assumed simplified value. Initially, it is set to Optional::None, which
   // means that the value is not clear under current assumption. If in the
   // pessimistic state, getAssumedSimplifiedValue doesn't return this value but
   // returns orignal associated value.
   Optional<Value *> SimplifiedAssociatedValue;
 };
 
auto PredForCallSite = [&](AbstractCallSite ACS) {
       // Check if a coresponding argument was found or if it is on not
       // associated (which can happen for callback calls).
       if (ACSArgPos.getPositionKind() == IRPosition::IRP_INVALID)
         return false;
 
       // We can only propagate thread independent values through callbacks.
       // This is different to direct/indirect call sites because for them we
       // know the thread executing the caller and callee is the same. For
       // callbacks this is not guaranteed, thus a thread dependent value could
       // be different for the caller and callee, making it invalid to propagate.
       Value &ArgOp = ACSArgPos.getAssociatedValue();
       if (ACS.isCallbackCall())
         if (auto *C = dyn_cast<Constant>(&ArgOp))
           if (C->isThreadDependent())
             return false;
       return checkAndUpdate(A, *this, ArgOp, SimplifiedAssociatedValue);
     };
 
     bool AllCallSitesKnown;
     if (!A.checkForAllCallSites(PredForCallSite, *this, true,
                                 AllCallSitesKnown))
-      if (!askSimplifiedValueForAAValueConstantRange(A))
+      if (!askSimplifiedValueForOtherAAs(A))
         return indicatePessimisticFixpoint();
 
     // If a candicate was found in this update, return CHANGED.
     return HasValueBefore == SimplifiedAssociatedValue.hasValue()
                ? ChangeStatus::UNCHANGED
                : ChangeStatus ::CHANGED;
   }
 
struct AAValueSimplifyReturned : AAValueSimplifyImpl {
   ChangeStatus updateImpl(Attributor &A) override {
     bool HasValueBefore = SimplifiedAssociatedValue.hasValue();
 
     auto PredForReturned = [&](Value &V) {
       return checkAndUpdate(A, *this, V, SimplifiedAssociatedValue);
     };
 
     if (!A.checkForAllReturnedValues(PredForReturned, *this))
-      if (!askSimplifiedValueForAAValueConstantRange(A))
+      if (!askSimplifiedValueForOtherAAs(A))
         return indicatePessimisticFixpoint();
 
     // If a candicate was found in this update, return CHANGED.
     return HasValueBefore == SimplifiedAssociatedValue.hasValue()
                ? ChangeStatus::UNCHANGED
                : ChangeStatus ::CHANGED;
   }
 
   ChangeStatus manifest(Attributor &A) override {
     ChangeStatus Changed = ChangeStatus::UNCHANGED;
 
     if (SimplifiedAssociatedValue.hasValue() &&
         !SimplifiedAssociatedValue.getValue())
       return Changed;
 
     Value &V = getAssociatedValue();
auto VisitValueCB = [&](Value &V, const Instruction *CtxI, bool &,
       }
       return checkAndUpdate(A, *this, V, SimplifiedAssociatedValue);
     };
 
     bool Dummy = false;
     if (!genericValueTraversal<AAValueSimplify, bool>(
             A, getIRPosition(), *this, Dummy, VisitValueCB, getCtxI(),
             /* UseValueSimplify */ false))
-      if (!askSimplifiedValueForAAValueConstantRange(A))
+      if (!askSimplifiedValueForOtherAAs(A))
         return indicatePessimisticFixpoint();
 
     // If a candicate was found in this update, return CHANGED.
-
     return HasValueBefore == SimplifiedAssociatedValue.hasValue()
                ? ChangeStatus::UNCHANGED
                : ChangeStatus ::CHANGED;
   }
 
   /// See AbstractAttribute::trackStatistics()
   void trackStatistics() const override {
     STATS_DECLTRACK_FLOATING_ATTR(value_simplify)
struct AAValueSimplifyCallSiteReturned : AAValueSimplifyReturned {
   void trackStatistics() const override {
     STATS_DECLTRACK_CSRET_ATTR(value_simplify)
   }
 };
 struct AAValueSimplifyCallSiteArgument : AAValueSimplifyFloating {
   AAValueSimplifyCallSiteArgument(const IRPosition &IRP, Attributor &A)
       : AAValueSimplifyFloating(IRP, A) {}
 
+  ChangeStatus manifest(Attributor &A) override {
+    ChangeStatus Changed = ChangeStatus::UNCHANGED;
+
+    if (SimplifiedAssociatedValue.hasValue() &&
+        !SimplifiedAssociatedValue.getValue())
+      return Changed;
+
+    Value &V = getAssociatedValue();
+    auto *C = SimplifiedAssociatedValue.hasValue()
+                  ? dyn_cast<Constant>(SimplifiedAssociatedValue.getValue())
+                  : UndefValue::get(V.getType());
+    Use &U = cast<CallBase>(&getAnchorValue())->getArgOperandUse(getArgNo());
+    if (C) {
+      // We can replace the AssociatedValue with the constant.
+      if (&V != C && V.getType() == C->getType()) {
+        if (A.changeUseAfterManifest(U, *C))
+          Changed = ChangeStatus::CHANGED;
+      }
+    }
+
+    return Changed | AAValueSimplify::manifest(A);
+  }
+
   void trackStatistics() const override {
     STATS_DECLTRACK_CSARG_ATTR(value_simplify)
   }
 };
 
 /// ----------------------- Heap-To-Stack Conversion ---------------------------
 struct AAHeapToStackImpl : public AAHeapToStack {
   AAHeapToStackImpl(const IRPosition &IRP, Attributor &A)
struct AAValueConstantRangeCallSiteArgument : AAValueConstantRangeFloating {
   AAValueConstantRangeCallSiteArgument(const IRPosition &IRP, Attributor &A)
       : AAValueConstantRangeFloating(IRP, A) {}
 
   /// See AbstractAttribute::trackStatistics()
   void trackStatistics() const override {
     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 << "set-state < {";
+    if (getKnown().isFull) {
+      OS << "full-set";
+    } else {
+      for (auto &it : getKnown().Set) {
+        OS << it << " , ";
+      }
+    }
+    OS << "} / {";
+    if (getAssumed().isFull) {
+      OS << "full-set";
+    } else {
+      for (auto &it : getAssumed().Set) {
+        OS << it << " , ";
+      }
+    }
+    OS << "} >";
+    return OS.str();
+  }
+};
+
+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::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 {
+    Value &V = getAssociatedValue();
+
+    if (auto *C = dyn_cast<ConstantInt>(&V)) {
+      unionAssumed(C->getValue());
+      indicateOptimisticFixpoint();
+      return;
+    }
+
+    if (isa<UndefValue>(&V)) {
+      // Collapse the undef state to 0.
+      unionAssumed(
+          APInt(/* numBits */ getAssociatedType()->getIntegerBitWidth(),
+                /* val */ 0));
+      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");
+  }
+
+  static bool calculateICmpInst(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!");
+    }
+  }
+
+  static APInt calculateCastInst(const CastInst *CI, APInt &Src,
+                                 uint32_t ResultBitWidth) {
+    Instruction::CastOps CastOp = CI->getOpcode();
+    switch (CastOp) {
+    default:
+      llvm_unreachable("unsupported or not integer cast");
+    case Instruction::Trunc:
+      return Src.trunc(ResultBitWidth);
+    case Instruction::SExt:
+      return Src.sext(ResultBitWidth);
+    case Instruction::ZExt:
+      return Src.zext(ResultBitWidth);
+    case Instruction::BitCast:
+      return Src;
+    }
+  }
+
+  static APInt calculateBinaryOperator(const BinaryOperator *BinOp,
+                                       const APInt &LHS, const APInt &RHS,
+                                       bool &Valid) {
+    Instruction::BinaryOps BinOpcode = BinOp->getOpcode();
+    // Valid is set to false when the binary operator is not supported or
+    // division by zero occur.
+    Valid = true;
+    APInt LHSCopy = LHS;
+    switch (BinOpcode) {
+    default:
+      Valid = false;
+      return LHS;
+    case Instruction::Add:
+      return (LHSCopy += RHS);
+    case Instruction::Sub:
+      return (LHSCopy -= RHS);
+    case Instruction::Mul:
+      return LHS * RHS;
+    case Instruction::UDiv:
+      if (RHS.isNullValue()) {
+        Valid = false;
+        return LHS;
+      }
+      return LHS.udiv(RHS);
+    case Instruction::SDiv:
+      if (RHS.isNullValue()) {
+        Valid = false;
+        return LHS;
+      }
+      return LHS.sdiv(RHS);
+    case Instruction::URem:
+      if (RHS.isNullValue()) {
+        Valid = false;
+        return LHS;
+      }
+      return LHS.urem(RHS);
+    case Instruction::SRem:
+      if (RHS.isNullValue()) {
+        Valid = false;
+        return LHS;
+      }
+      return LHS.srem(RHS);
+    case Instruction::Shl:
+      return LHS.shl(RHS);
+    case Instruction::LShr:
+      return LHS.lshr(RHS);
+    case Instruction::AShr:
+      return LHS.ashr(RHS);
+    case Instruction::And:
+      return (LHSCopy &= RHS);
+    case Instruction::Or:
+      return (LHSCopy |= RHS);
+    case Instruction::Xor:
+      return (LHSCopy ^= RHS);
+    }
+  }
+
+  ChangeStatus updateWithICmpInst(Attributor &A, ICmpInst *ICI) {
+    auto AssumedBefore = getAssumed();
+    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.isValidState() || !RHSAA.isValidState())
+      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 = calculateICmpInst(ICI, L, R);
+        MaybeTrue |= CmpResult;
+        MaybeFalse |= !CmpResult;
+      }
+    }
+    if (MaybeTrue)
+      unionAssumed(APInt(/* numBits */ 1, /* val */ 1));
+    if (MaybeFalse)
+      unionAssumed(APInt(/* numBits */ 1, /* val */ 0));
+    return AssumedBefore == getAssumed() ? ChangeStatus::UNCHANGED
+                                         : ChangeStatus::CHANGED;
+  }
+
+  ChangeStatus updateWithSelectInst(Attributor &A, SelectInst *SI) {
+    auto AssumedBefore = getAssumed();
+    Value *LHS = SI->getTrueValue();
+    Value *RHS = SI->getFalseValue();
+    if (!LHS->getType()->isIntegerTy() || !RHS->getType()->isIntegerTy())
+      return indicatePessimisticFixpoint();
+
+    // TODO: consider simplified condition value
+    auto &LHSAA = A.getAAFor<AAPotentialValues>(*this, IRPosition::value(*LHS));
+    auto &RHSAA = A.getAAFor<AAPotentialValues>(*this, IRPosition::value(*RHS));
+
+    if (!LHSAA.isValidState() || !RHSAA.isValidState())
+      return indicatePessimisticFixpoint();
+
+    unionAssumed(LHSAA);
+    unionAssumed(RHSAA);
+    return AssumedBefore == getAssumed() ? ChangeStatus::UNCHANGED
+                                         : ChangeStatus::CHANGED;
+  }
+
+  ChangeStatus updateWithCastInst(Attributor &A, CastInst *CI) {
+    auto AssumedBefore = getAssumed();
+    if (!CI->isIntegerCast())
+      return indicatePessimisticFixpoint();
+    assert(CI->getNumOperands() == 1 && "Expected cast to be unary!");
+    uint32_t ResultBitWidth = CI->getDestTy()->getIntegerBitWidth();
+    Value *Src = CI->getOperand(0);
+    auto &SrcAA = A.getAAFor<AAPotentialValues>(*this, IRPosition::value(*Src));
+    if (!SrcAA.isValidState())
+      return indicatePessimisticFixpoint();
+    auto SrcAAPVS = SrcAA.getAssumedSet();
+    for (APInt &S : SrcAAPVS) {
+      APInt T = calculateCastInst(CI, S, ResultBitWidth);
+      unionAssumed(T);
+    }
+    return AssumedBefore == getAssumed() ? ChangeStatus::UNCHANGED
+                                         : ChangeStatus::CHANGED;
+  }
+
+  ChangeStatus updateWithBinaryOperator(Attributor &A, BinaryOperator *BinOp) {
+    auto AssumedBefore = getAssumed();
+    Value *LHS = BinOp->getOperand(0);
+    Value *RHS = BinOp->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.isValidState() || !RHSAA.isValidState())
+      return indicatePessimisticFixpoint();
+
+    auto LHSAAPVS = LHSAA.getAssumedSet();
+    auto RHSAAPVS = RHSAA.getAssumedSet();
+
+    for (auto &L : LHSAAPVS) {
+      for (auto &R : RHSAAPVS) {
+        bool Valid = true;
+        APInt Result = calculateBinaryOperator(BinOp, L, R, Valid);
+        if (!Valid)
+          return indicatePessimisticFixpoint();
+        unionAssumed(Result);
+      }
+    }
+    return AssumedBefore == getAssumed() ? ChangeStatus::UNCHANGED
+                                         : ChangeStatus::CHANGED;
+  }
+
+  ChangeStatus updateWithPHINode(Attributor &A, PHINode *PHI) {
+    auto AssumedBefore = getAssumed();
+    for (unsigned u = 0, e = PHI->getNumIncomingValues(); u < e; u++) {
+      Value *IncomingValue = PHI->getIncomingValue(u);
+      auto &PotentialValuesAA = A.getAAFor<AAPotentialValues>(
+          *this, IRPosition::value(*IncomingValue));
+      if (!PotentialValuesAA.isValidState())
+        return indicatePessimisticFixpoint();
+      unionAssumed(PotentialValuesAA.getAssumed());
+    }
+    return AssumedBefore == getAssumed() ? ChangeStatus::UNCHANGED
+                                         : ChangeStatus::CHANGED;
+  }
+
+  /// See AbstractAttribute::updateImpl(...).
+  ChangeStatus updateImpl(Attributor &A) override {
+    Value &V = getAssociatedValue();
+    Instruction *I = dyn_cast<Instruction>(&V);
+
+    if (auto *ICI = dyn_cast<ICmpInst>(I))
+      return updateWithICmpInst(A, ICI);
+
+    if (auto *SI = dyn_cast<SelectInst>(I))
+      return updateWithSelectInst(A, SI);
+
+    if (auto *CI = dyn_cast<CastInst>(I))
+      return updateWithCastInst(A, CI);
+
+    if (auto *BinOp = dyn_cast<BinaryOperator>(I))
+      return updateWithBinaryOperator(A, BinOp);
+
+    if (auto *PHI = dyn_cast<PHINode>(I))
+      return updateWithPHINode(A, PHI);
+
+    return indicatePessimisticFixpoint();
+  }
+
+  /// 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::trackStatistics()
+  void trackStatistics() const override {
+    STATS_DECLTRACK_CSRET_ATTR(potential_values)
+  }
+};
+
+struct AAPotentialValuesCallSiteArgument : AAPotentialValuesImpl {
+  AAPotentialValuesCallSiteArgument(const IRPosition &IRP, Attributor &A)
+      : AAPotentialValuesImpl(IRP, A) {}
+
+  /// See AbstractAttribute::initialize(...).
+  void initialize(Attributor &A) override {
+    Value &V = getAssociatedValue();
+
+    if (auto *C = dyn_cast<ConstantInt>(&V)) {
+      unionAssumed(C->getValue());
+      indicateOptimisticFixpoint();
+      return;
+    }
+
+    if (isa<UndefValue>(&V)) {
+      unionAssumed(
+          APInt(/* numBits */ getAssociatedType()->getIntegerBitWidth(),
+                /* val */ 0));
+      indicateOptimisticFixpoint();
+      return;
+    }
+  }
+
+  /// See AbstractAttribute::updateImpl(...).
+  ChangeStatus updateImpl(Attributor &A) override {
+    Value &V = getAssociatedValue();
+    auto AssumedBefore = getAssumed();
+    auto &AA = A.getAAFor<AAPotentialValues>(*this, IRPosition::value(V));
+    const auto &S = AA.getAssumed();
+    unionAssumed(S);
+    return AssumedBefore == getAssumed() ? ChangeStatus::UNCHANGED
+                                         : ChangeStatus::CHANGED;
+  }
+
+  /// See AbstractAttribute::trackStatistics()
+  void trackStatistics() const override {
+    STATS_DECLTRACK_CSARG_ATTR(potential_values)
+  }
+};
+
 } // namespace
 
 const char AAReturnedValues::ID = 0;
 const char AANoUnwind::ID = 0;
 const char AANoSync::ID = 0;
 const char AANoFree::ID = 0;
 const char AANonNull::ID = 0;
 const char AANoRecurse::ID = 0;
 const char AAWillReturn::ID = 0;
 const char AAUndefinedBehavior::ID = 0;
 const char AANoAlias::ID = 0;
 const char AAReachability::ID = 0;
 const char AANoReturn::ID = 0;
 const char AAIsDead::ID = 0;
 const char AADereferenceable::ID = 0;
 const char AAAlign::ID = 0;
 const char AANoCapture::ID = 0;
 const char AAValueSimplify::ID = 0;
 const char AAHeapToStack::ID = 0;
 const char AAPrivatizablePtr::ID = 0;
 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.
 
 #define SWITCH_PK_INV(CLASS, PK, POS_NAME)                                     \
   case IRPosition::PK:                                                         \
     llvm_unreachable("Cannot create " #CLASS " for a " POS_NAME " position!");
 

 
 CREATE_VALUE_ABSTRACT_ATTRIBUTE_FOR_POSITION(AANonNull)
 CREATE_VALUE_ABSTRACT_ATTRIBUTE_FOR_POSITION(AANoAlias)
 CREATE_VALUE_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAPrivatizablePtr)
 CREATE_VALUE_ABSTRACT_ATTRIBUTE_FOR_POSITION(AADereferenceable)
 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)
 CREATE_ALL_ABSTRACT_ATTRIBUTE_FOR_POSITION(AANoFree)
 
 CREATE_FUNCTION_ONLY_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAHeapToStack)
 CREATE_FUNCTION_ONLY_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAReachability)
 CREATE_FUNCTION_ONLY_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAUndefinedBehavior)

llvm/test/Transforms/Attributor/potential.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --function-signature --scrub-attributes
+; RUN: opt -attributor -attributor-manifest-internal  -attributor-max-iterations-verify -attributor-annotate-decl-cs -attributor-max-iterations=20 -S < %s | FileCheck %s --check-prefixes=CHECK,NOT_CGSCC_NPM,NOT_CGSCC_OPM,NOT_TUNIT_NPM,IS__TUNIT____,IS________OPM,IS__TUNIT_OPM
+; RUN: opt -aa-pipeline=basic-aa -passes=attributor -attributor-manifest-internal  -attributor-max-iterations-verify -attributor-annotate-decl-cs -attributor-max-iterations=19 -S < %s | FileCheck %s --check-prefixes=CHECK,NOT_CGSCC_OPM,NOT_CGSCC_NPM,NOT_TUNIT_OPM,IS__TUNIT____,IS________NPM,IS__TUNIT_NPM
+; RUN: opt -attributor-cgscc -attributor-manifest-internal  -attributor-annotate-decl-cs -S < %s | FileCheck %s --check-prefixes=CHECK,NOT_TUNIT_NPM,NOT_TUNIT_OPM,NOT_CGSCC_NPM,IS__CGSCC____,IS________OPM,IS__CGSCC_OPM
+; RUN: opt -aa-pipeline=basic-aa -passes=attributor-cgscc -attributor-manifest-internal  -attributor-annotate-decl-cs -S < %s | FileCheck %s --check-prefixes=CHECK,NOT_TUNIT_NPM,NOT_TUNIT_OPM,NOT_CGSCC_OPM,IS__CGSCC____,IS________NPM,IS__CGSCC_NPM
+;
+; Test for multiple potential values
+;
+; potential-test 1
+; bool iszero(int c) { return c == 0; }
+; bool potential_test1(bool c) { return iszero(c ? 1 : -1); }
+
+define internal i1 @iszero1(i32 %c) {
+; IS__CGSCC____-LABEL: define {{[^@]+}}@iszero1
+; IS__CGSCC____-SAME: (i32 [[C:%.*]])
+; IS__CGSCC____-NEXT:    [[CMP:%.*]] = icmp eq i32 [[C]], 0
+; IS__CGSCC____-NEXT:    ret i1 [[CMP]]
+;
+  %cmp = icmp eq i32 %c, 0
+  ret i1 %cmp
+}
+
+define i1 @potential_test1(i1 %c) {
+; IS__TUNIT____-LABEL: define {{[^@]+}}@potential_test1
+; IS__TUNIT____-SAME: (i1 [[C:%.*]])
+; IS__TUNIT____-NEXT:    ret i1 false
+;
+; IS__CGSCC____-LABEL: define {{[^@]+}}@potential_test1
+; IS__CGSCC____-SAME: (i1 [[C:%.*]])
+; IS__CGSCC____-NEXT:    [[ARG:%.*]] = select i1 [[C]], i32 -1, i32 1
+; IS__CGSCC____-NEXT:    [[RET:%.*]] = tail call i1 @iszero1(i32 [[ARG]])
+; IS__CGSCC____-NEXT:    ret i1 [[RET]]
+;
+  %arg = select i1 %c, i32 -1, i32 1
+  %ret = tail call i1 @iszero1(i32 %arg)
+  ret i1 %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 internal i32 @iszero2(i32 %c) {
+; IS__CGSCC____-LABEL: define {{[^@]+}}@iszero2
+; IS__CGSCC____-SAME: (i32 [[C:%.*]])
+; IS__CGSCC____-NEXT:    [[CMP:%.*]] = icmp eq i32 [[C]], 0
+; IS__CGSCC____-NEXT:    [[RET:%.*]] = zext i1 [[CMP]] to i32
+; IS__CGSCC____-NEXT:    ret i32 [[RET]]
+;
+  %cmp = icmp eq i32 %c, 0
+  %ret = zext i1 %cmp to i32
+  ret i32 %ret
+}
+
+define internal i32 @call_with_two_values(i32 %c) {
+; IS__CGSCC____-LABEL: define {{[^@]+}}@call_with_two_values
+; IS__CGSCC____-SAME: (i32 [[C:%.*]])
+; IS__CGSCC____-NEXT:    [[CSRET1:%.*]] = call i32 @iszero2(i32 [[C]])
+; IS__CGSCC____-NEXT:    [[MINUSC:%.*]] = sub nsw i32 0, [[C]]
+; IS__CGSCC____-NEXT:    [[CSRET2:%.*]] = call i32 @iszero2(i32 [[MINUSC]])
+; IS__CGSCC____-NEXT:    [[RET:%.*]] = add i32 [[CSRET1]], [[CSRET2]]
+; IS__CGSCC____-NEXT:    ret i32 [[RET]]
+;
+  %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 i32 @potential_test2(i1 %c) {
+; IS__TUNIT____-LABEL: define {{[^@]+}}@potential_test2
+; IS__TUNIT____-SAME: (i1 [[C:%.*]])
+; IS__TUNIT____-NEXT:    ret i32 0
+;
+; IS__CGSCC____-LABEL: define {{[^@]+}}@potential_test2
+; IS__CGSCC____-SAME: (i1 [[C:%.*]])
+; IS__CGSCC____-NEXT:    [[CSRET1:%.*]] = call i32 @call_with_two_values(i32 1)
+; IS__CGSCC____-NEXT:    [[CSRET2:%.*]] = call i32 @call_with_two_values(i32 -1)
+; IS__CGSCC____-NEXT:    [[RET:%.*]] = select i1 [[C]], i32 [[CSRET1]], i32 [[CSRET2]]
+; IS__CGSCC____-NEXT:    ret i32 [[RET]]
+;
+  %csret1 = tail call i32 @iszero2(i32 %c)
+  %minusc = sub nsw i32 0, %c
+  %csret2 = tail call i32 @iszero2(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 internal i32 @iszero3(i32 %c) {
+; IS__CGSCC____-LABEL: define {{[^@]+}}@iszero3
+; IS__CGSCC____-SAME: (i32 [[C:%.*]])
+; IS__CGSCC____-NEXT:    [[CMP:%.*]] = icmp eq i32 [[C]], 0
+; IS__CGSCC____-NEXT:    [[RET:%.*]] = zext i1 [[CMP]] to i32
+; IS__CGSCC____-NEXT:    ret i32 [[RET]]
+;
+  %cmp = icmp eq i32 %c, 0
+  %ret = zext i1 %cmp to i32
+  ret i32 %ret
+}
+
+define internal i32 @less_than_two(i32 %c) {
+; IS__CGSCC____-LABEL: define {{[^@]+}}@less_than_two
+; IS__CGSCC____-SAME: (i32 [[C:%.*]])
+; IS__CGSCC____-NEXT:    [[CMP:%.*]] = icmp slt i32 [[C]], 2
+; IS__CGSCC____-NEXT:    [[RET:%.*]] = zext i1 [[CMP]] to i32
+; IS__CGSCC____-NEXT:    ret i32 [[RET]]
+;
+  %cmp1 = tail call i32 @iszero3(i32 0)
+  %true1 = tail call i32 @zero_or_one(i32 %cmp1)
+  %cmp2 = tail call i32 @iszero3(i32 1)
+  %true2 = tail call i32 @zero_or_one(i32 %cmp2)
+  %ret = add nsw i32 %true1, %true2
+  ret i32 %ret
+}
+
+define i32 @potential_test3() {
+; IS__TUNIT____-LABEL: define {{[^@]+}}@potential_test3()
+; IS__TUNIT____-NEXT:    ret i32 2
+;
+; IS__CGSCC____-LABEL: define {{[^@]+}}@potential_test3()
+; IS__CGSCC____-NEXT:    [[CMP1:%.*]] = call i32 @iszero3(i32 0)
+; IS__CGSCC____-NEXT:    [[TRUE1:%.*]] = call i32 @less_than_two(i32 [[CMP1]])
+; IS__CGSCC____-NEXT:    [[CMP2:%.*]] = call i32 @iszero3(i32 1)
+; IS__CGSCC____-NEXT:    [[TRUE2:%.*]] = call i32 @less_than_two(i32 [[CMP2]])
+; IS__CGSCC____-NEXT:    [[RET:%.*]] = add i32 [[TRUE1]], [[TRUE2]]
+; IS__CGSCC____-NEXT:    ret i32 [[RET]]
+;
+  %cmp = icmp slt i32 %c, 2
+  %ret = zext i1 %cmp to i32
+  ret i32 %ret
+}
+
+
+; 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 %c) {
+; IS__TUNIT____-LABEL: define {{[^@]+}}@potential_test4
+; IS__TUNIT____-SAME: (i32 [[C:%.*]])
+; IS__TUNIT____-NEXT:    ret i32 0
+;
+; IS__CGSCC____-LABEL: define {{[^@]+}}@potential_test4
+; IS__CGSCC____-SAME: (i32 [[C:%.*]])
+; IS__CGSCC____-NEXT:    [[CSRET:%.*]] = call i32 @return1or3(i32 [[C]])
+; IS__CGSCC____-NEXT:    [[FALSE:%.*]] = icmp eq i32 [[CSRET]], 2
+; IS__CGSCC____-NEXT:    [[RET:%.*]] = zext i1 [[FALSE]] to i32
+; IS__CGSCC____-NEXT:    ret i32 [[RET]]
+;
+  %csret = tail call i32 @return1or3(i32 %c)
+  %false = icmp eq i32 %csret, 2
+  %ret = zext i1 %false to i32
+  ret i32 %ret
+}
+
+define i32 @potential_test5(i32 %c) {
+; IS__TUNIT____-LABEL: define {{[^@]+}}@potential_test5
+; IS__TUNIT____-SAME: (i32 [[C:%.*]])
+; IS__TUNIT____-NEXT:    ret i32 0
+;
+; IS__CGSCC____-LABEL: define {{[^@]+}}@potential_test5
+; IS__CGSCC____-SAME: (i32 [[C:%.*]])
+; IS__CGSCC____-NEXT:    [[CSRET1:%.*]] = call i32 @return1or3(i32 [[C]])
+; IS__CGSCC____-NEXT:    [[CSRET2:%.*]] = call i32 @return2or4(i32 [[C]])
+; IS__CGSCC____-NEXT:    [[FALSE:%.*]] = icmp eq i32 [[CSRET1]], [[CSRET2]]
+; IS__CGSCC____-NEXT:    [[RET:%.*]] = zext i1 [[FALSE]] to i32
+; IS__CGSCC____-NEXT:    ret i32 [[RET]]
+;
+  %csret1 = tail call i32 @return1or3(i32 %c)
+  %csret2 = tail call i32 @return2or4(i32 %c)
+  %false = icmp eq i32 %csret1, %csret2
+  %ret = zext i1 %false to i32
+  ret i32 %ret
+}
+
+define i1 @potential_test6(i32 %c) {
+; IS__TUNIT____-LABEL: define {{[^@]+}}@potential_test6
+; IS__TUNIT____-SAME: (i32 [[C:%.*]])
+; IS__TUNIT____-NEXT:    [[CSRET1:%.*]] = call i32 @return1or3(i32 [[C]]) #0, !range !0
+; IS__TUNIT____-NEXT:    [[RET:%.*]] = icmp eq i32 [[CSRET1]], 3
+; IS__TUNIT____-NEXT:    ret i1 [[RET]]
+;
+; IS__CGSCC____-LABEL: define {{[^@]+}}@potential_test6
+; IS__CGSCC____-SAME: (i32 [[C:%.*]])
+; IS__CGSCC____-NEXT:    [[CSRET1:%.*]] = call i32 @return1or3(i32 [[C]])
+; IS__CGSCC____-NEXT:    [[RET:%.*]] = icmp eq i32 [[CSRET1]], 3
+; IS__CGSCC____-NEXT:    ret i1 [[RET]]
+;
+  %csret1 = call i32 @return1or3(i32 %c)
+  %ret = icmp eq i32 %csret1, 3
+  ret i1 %ret
+}
+
+define i1 @potential_test7(i32 %c) {
+; IS__TUNIT____-LABEL: define {{[^@]+}}@potential_test7
+; IS__TUNIT____-SAME: (i32 [[C:%.*]])
+; IS__TUNIT____-NEXT:    [[CSRET1:%.*]] = call i32 @return1or3(i32 [[C]]) #0, !range !0
+; IS__TUNIT____-NEXT:    [[CSRET2:%.*]] = call i32 @return3or4(i32 [[C]]) #0, !range !1
+; IS__TUNIT____-NEXT:    [[RET:%.*]] = icmp eq i32 [[CSRET1]], [[CSRET2]]
+; IS__TUNIT____-NEXT:    ret i1 [[RET]]
+;
+; IS__CGSCC____-LABEL: define {{[^@]+}}@potential_test7
+; IS__CGSCC____-SAME: (i32 [[C:%.*]])
+; IS__CGSCC____-NEXT:    [[CSRET1:%.*]] = call i32 @return1or3(i32 [[C]])
+; IS__CGSCC____-NEXT:    [[CSRET2:%.*]] = call i32 @return3or4(i32 [[C]])
+; IS__CGSCC____-NEXT:    [[RET:%.*]] = icmp eq i32 [[CSRET1]], [[CSRET2]]
+; IS__CGSCC____-NEXT:    ret i1 [[RET]]
+;
+  %csret1 = call i32 @return1or3(i32 %c)
+  %csret2 = call i32 @return3or4(i32 %c)
+  %ret = icmp eq i32 %csret1, %csret2
+  ret i1 %ret
+}
+
+define internal i32 @return1or3(i32 %c) {
+; CHECK-LABEL: define {{[^@]+}}@return1or3
+; CHECK-SAME: (i32 [[C:%.*]])
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[C]], 0
+; CHECK-NEXT:    [[RET:%.*]] = select i1 [[CMP]], i32 1, i32 3
+; CHECK-NEXT:    ret i32 [[RET]]
+;
+  %cmp = icmp eq i32 %c, 0
+  %ret = select i1 %cmp, i32 1, i32 3
+  ret i32 %ret
+}
+
+define internal i32 @return2or4(i32 %c) {
+; IS__CGSCC____-LABEL: define {{[^@]+}}@return2or4
+; IS__CGSCC____-SAME: (i32 [[C:%.*]])
+; IS__CGSCC____-NEXT:    [[CMP:%.*]] = icmp eq i32 [[C]], 0
+; IS__CGSCC____-NEXT:    [[RET:%.*]] = select i1 [[CMP]], i32 2, i32 4
+; IS__CGSCC____-NEXT:    ret i32 [[RET]]
+;
+  %cmp = icmp eq i32 %c, 0
+  %ret = select i1 %cmp, i32 2, i32 4
+  ret i32 %ret
+}
+
+define internal i32 @return3or4(i32 %c) {
+; CHECK-LABEL: define {{[^@]+}}@return3or4
+; CHECK-SAME: (i32 [[C:%.*]])
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[C]], 0
+; CHECK-NEXT:    [[RET:%.*]] = select i1 [[CMP]], i32 3, i32 4
+; CHECK-NEXT:    ret i32 [[RET]]
+;
+  %cmp = icmp eq i32 %c, 0
+  %ret = select i1 %cmp, i32 3, i32 4
+  ret i32 %ret
+}
+
+; potential-test 8
+;
+; propagate argument to callsite argument
+
+define internal i1 @cmp_with_four(i32 %c) {
+; IS__CGSCC____-LABEL: define {{[^@]+}}@cmp_with_four
+; IS__CGSCC____-SAME: (i32 [[C:%.*]])
+; IS__CGSCC____-NEXT:    [[CMP:%.*]] = icmp eq i32 [[C]], 4
+; IS__CGSCC____-NEXT:    ret i1 [[CMP]]
+;
+  %cmp = icmp eq i32 %c, 4
+  ret i1 %cmp
+}
+
+define internal i1 @wrapper(i32 %c) {
+; IS__CGSCC____-LABEL: define {{[^@]+}}@wrapper
+; IS__CGSCC____-SAME: (i32 [[C:%.*]])
+; IS__CGSCC____-NEXT:    [[RET:%.*]] = call i1 @cmp_with_four(i32 [[C]])
+; IS__CGSCC____-NEXT:    ret i1 [[RET]]
+;
+  %ret = call i1 @cmp_with_four(i32 %c)
+  ret i1 %ret
+}
+
+define i1 @potential_test8() {
+; IS__TUNIT____-LABEL: define {{[^@]+}}@potential_test8()
+; IS__TUNIT____-NEXT:    ret i1 false
+;
+; IS__CGSCC____-LABEL: define {{[^@]+}}@potential_test8()
+; IS__CGSCC____-NEXT:    [[RES1:%.*]] = call i1 @wrapper(i32 1)
+; IS__CGSCC____-NEXT:    [[RES3:%.*]] = call i1 @wrapper(i32 3)
+; IS__CGSCC____-NEXT:    [[RES5:%.*]] = call i1 @wrapper(i32 5)
+; IS__CGSCC____-NEXT:    [[RES13:%.*]] = or i1 [[RES1]], [[RES3]]
+; IS__CGSCC____-NEXT:    [[RES135:%.*]] = or i1 [[RES13]], [[RES5]]
+; IS__CGSCC____-NEXT:    ret i1 [[RES135]]
+;
+  %res1 = call i1 @wrapper(i32 1)
+  %res3 = call i1 @wrapper(i32 3)
+  %res5 = call i1 @wrapper(i32 5)
+  %res13 = or i1 %res1, %res3
+  %res135 =  or i1 %res13, %res5
+  ret i1 %res135
+}
+
+define i1 @potential_test9() {
+; CHECK-LABEL: define {{[^@]+}}@potential_test9()
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[COND:%.*]]
+; CHECK:       cond:
+; CHECK-NEXT:    [[I_0:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[I_1:%.*]], [[INC:%.*]] ]
+; CHECK-NEXT:    [[C_0:%.*]] = phi i32 [ 1, [[ENTRY]] ], [ [[C_1:%.*]], [[INC]] ]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[I_0]], 10
+; CHECK-NEXT:    br i1 [[CMP]], label [[BODY:%.*]], label [[END:%.*]]
+; CHECK:       body:
+; CHECK-NEXT:    [[C_1]] = mul i32 [[C_0]], -1
+; CHECK-NEXT:    br label [[INC]]
+; CHECK:       inc:
+; CHECK-NEXT:    [[I_1]] = add i32 [[I_0]], 1
+; CHECK-NEXT:    br label [[COND]]
+; CHECK:       end:
+; CHECK-NEXT:    ret i1 false
+;
+entry:
+  br label %cond
+cond:
+  %i.0 = phi i32 [0, %entry], [%i.1, %inc]
+  %c.0 = phi i32 [1, %entry], [%c.1, %inc]
+  %cmp = icmp slt i32 %i.0, 10
+  br i1 %cmp, label %body, label %end
+body:
+  %c.1 = mul i32 %c.0, -1
+  br label %inc
+inc:
+  %i.1 = add i32 %i.0, 1
+  br label %cond
+end:
+  %ret = icmp eq i32 %c.0, 0
+  ret i1 %ret
+}