[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

2960

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

2974

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

2976

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

3007

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.

3027

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.

3031

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

3049

7 needs to be replaced by a command line option

3124

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

3427

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

4422

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.

4499

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.

4548

Same comment as last.

4632

Same comment as last.

7108

not needed.

7404

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

3051

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.

3165

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

4395

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!

4714

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?

7101

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

3165

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

4395

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

4714

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

3037

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 ?

3165

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"
if (RangeV.isEmptySet())
       return llvm::None;
     return nullptr;
   }
 
   /// Unique ID (due to the unique address)
   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,
   MODULE = 1 << 0,
   CGSCC = 1 << 1,
   ALL = MODULE | CGSCC
 };
 
 } // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_IPO_FUNCTIONATTRS_H

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,
if (!A.checkForAllInstructions(CheckReturnInst, *this, {Instruction::Ret}))
     return indicatePessimisticFixpoint();
 
   // Once returned values "directly" present in the code are handled we try to
   // resolve returned calls. To avoid modifications to the ReturnedValues map
   // while we iterate over it we kept record of potential new entries in a copy
   // 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;
 
     if (!CB->getCalledFunction()) {
       LLVM_DEBUG(dbgs() << "[AAReturnedValues] Unresolved call: " << *CB
                         << "\n");
       UnresolvedCalls.insert(CB);
auto VisitValueCB = [&](const Value &V, const Instruction *, DerefState &T,
         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(
if (COpt.hasValue()) {
       else
         return false;
     } else {
       SimplifiedAssociatedValue = llvm::None;
     }
     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;
 
     if (SimplifiedAssociatedValue.hasValue() &&
         !SimplifiedAssociatedValue.getValue())
       return Changed;
 
     Value &V = getAssociatedValue();
     auto *C = SimplifiedAssociatedValue.hasValue()
                   ? dyn_cast<Constant>(SimplifiedAssociatedValue.getValue())
                   : UndefValue::get(V.getType());
     if (C) {
       // We can replace the AssociatedValue with the constant.
       if (!V.user_empty() && &V != C && V.getType() == C->getType()) {
         LLVM_DEBUG(dbgs() << "[ValueSimplify] " << V << " -> " << *C
                           << " :: " << *this << "\n");
         if (A.changeValueAfterManifest(V, *C))
           Changed = ChangeStatus::CHANGED;
       }
     }
 
     return Changed | AAValueSimplify::manifest(A);
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);
     };
if (!A.checkForAllReturnedValues(PredForReturned, *this))
       if (!askSimplifiedValueForAAValueConstantRange(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();
ChangeStatus updateImpl(Attributor &A) override {
     };
 
     bool Dummy = false;
     if (!genericValueTraversal<AAValueSimplify, bool>(
             A, getIRPosition(), *this, Dummy, VisitValueCB, getCtxI(),
             /* UseValueSimplify */ false))
       if (!askSimplifiedValueForAAValueConstantRange(A))
         return indicatePessimisticFixpoint();
 
     // If a candicate was found in this update, return CHANGED.
 
     return HasValueBefore == SimplifiedAssociatedValue.hasValue()
                ? ChangeStatus::UNCHANGED
                : ChangeStatus ::CHANGED;
   }
 
   /// See AbstractAttribute::trackStatistics()
struct AAHeapToStackImpl : public AAHeapToStack {
   ChangeStatus manifest(Attributor &A) override {
     assert(getState().isValidState() &&
            "Attempted to manifest an invalid state!");
 
     ChangeStatus HasChanged = ChangeStatus::UNCHANGED;
     Function *F = getAnchorScope();
     const auto *TLI = A.getInfoCache().getTargetLibraryInfoForFunction(*F);
 
     for (Instruction *MallocCall : MallocCalls) {
       // This malloc cannot be replaced.
       if (BadMallocCalls.count(MallocCall))
         continue;
 
       for (Instruction *FreeCall : FreesForMalloc[MallocCall]) {
         LLVM_DEBUG(dbgs() << "H2S: Removing free call: " << *FreeCall << "\n");
         A.deleteAfterManifest(*FreeCall);
         HasChanged = ChangeStatus::CHANGED;
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 << "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;
 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!");
 
CLASS &CLASS::createForPosition(const IRPosition &IRP, Attributor &A) {      \
     return *AA;                                                                \
   }
 
 #define CREATE_NON_RET_ABSTRACT_ATTRIBUTE_FOR_POSITION(CLASS)                  \
   CLASS &CLASS::createForPosition(const IRPosition &IRP, Attributor &A) {      \
     CLASS *AA = nullptr;                                                       \
     switch (IRP.getPositionKind()) {                                           \
       SWITCH_PK_INV(CLASS, IRP_INVALID, "invalid")                             \
       SWITCH_PK_INV(CLASS, IRP_RETURNED, "returned")                           \
       SWITCH_PK_CREATE(CLASS, IRP, IRP_FUNCTION, Function)                     \
       SWITCH_PK_CREATE(CLASS, IRP, IRP_CALL_SITE, CallSite)                    \
       SWITCH_PK_CREATE(CLASS, IRP, IRP_FLOAT, Floating)                        \
       SWITCH_PK_CREATE(CLASS, IRP, IRP_ARGUMENT, Argument)                     \
       SWITCH_PK_CREATE(CLASS, IRP, IRP_CALL_SITE_RETURNED, CallSiteReturned)   \
       SWITCH_PK_CREATE(CLASS, IRP, IRP_CALL_SITE_ARGUMENT, CallSiteArgument)   \
     }                                                                          \
     return *AA;                                                                \

 
 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

+; 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
+}
+