[Attributor] AAPotentialValues Interface

[okura]

Summary

This is a split patch of D80991.
This patch introduces AAPotentialValues and its interface only.
For more detail of AAPotentialValues abstract attribute, see the original patch.

[baziotis]

Nit comments, I haven't yet digested the whole patch.

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

3056

Is there an APInt constructor that takes a pointer and an int ? I think the only such constructor is a private one.

3057

I also think that this U member is private.

[okura]

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

3056

Sorry for the delayed response. This struct is a friend struct of APInt. So Member functions can access the private functions of APInt. (c.f. https://llvm.org/doxygen/APInt_8h_source.html#l00099)
On the other hand, the same struct is defined in "/lib/IR/LLVMContextImpl.h" and I want to include it but I failed to do that.

[baziotis]

A nit comment is to please start comments with caps.

In general, this is good I think.

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

3056

Yes, my bad, thank you. If you want to include that, I guess that the problem is that an #include "looks" in llvm/include. You want to go one dir back and to lib. So, ../lib/IR/.... Have you tried that?

3131

Please change this to isAtWorstState for the reasons discussed in the other review (in which though I was wrong to suggest isTop since it is ambiguous whether top is the worst or best state). And add a doc that e.g. the worst state is when the potential values are all the possible values and thus, we know nothing.

3190

Nit: "Unite" -> "Union" (it works as a verb as well). Same for other parts.

llvm/test/Transforms/Attributor/potential.ll

60

I may be missing something here but how do you see the potential values in the output IR ? (Only) through ranges ?
I mean except for e.g. simplifying (e.g. that due to potential values, we deduce that the return value is in fact a constant, like in another test case).

Btw, we have different results that the test in the other diff right (this one: https://reviews.llvm.org/differential/changeset/?ref=2038557) ?
Why is that?

(I'll have to check the tests again).

[okura]

• Add documents (mainly AAPotentialValues struct)
• rename isFull in PotentialValuesState struct to isAtWorstState

[okura]

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

3056

Yes, I tried to do it in that way, but I got many warnings like "DEBUG_TYPE is redefined" when I built. So I gave up and redefine the struct here.

llvm/test/Transforms/Attributor/potential.ll

60

We cannot see the potential values in IR. Potential values are collected just for stronger value simplification for now.
Unlike the original patch, updateImpl has not implemented yet in this patch. So expected value simplification was not achieved and we have different results.

[baziotis]

The code is quite good and clean. Most comments are on the doc so that we can make it good and clean too and move to the full patch.

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

177

Nit: Maximum

191

Nit: Worst.
Good comment btw. Note that there are another 2 reasons that we might go to worst state. I would change it as follows:
"If the number of ... to a full set (the worse state)" -> "The set might (only) be forced to worst state, that is, to contain
every possible value (which effectively means that practically we know nothing about this IR position) in 3 cases:

1. We surpassed the \p MaxPotentialValues threshold.
2. We tried to initialize on a Value that we can't handle (e.g. an operator we don't currently handle)
3. During the iterations, this Value was affected (e.g. because of an operation) by a Value that is in

worst state.

I'm sure about the first 2, I have to think a little bit about whether the 3rd is good. What do you think for this
as a doc comment?

[baziotis]

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

94

We need to add a clearer comment here because it is still not clear what isAtWorstState means. Add sth like: "The worst state is when the set, theoretically, contains every possible value. That never happens naturally, we only force it". With that, the doc below will make sense.

188

"will grow while iteration". That doesn't make much sense. You can change it to "will grow monotonically as we find more potential values for this position". Or sth.

3056

Yes, I tried to do it in that way, but I got many warnings like "DEBUG_TYPE is redefined" when I built. So I gave up and redefine the struct here.

Hmm, ok I don't have a way to resolve that. Maybe someone else has some idea.

llvm/test/Transforms/Attributor/potential.ll

60

You are correct, thanks for updating me. You know, we might be able to see the potential values on some tests from the ranges...
Anyway, those tests look good, we'll take a closer look to them on the other patch.

[okura]

This comment was removed by okura.

[okura]

replace full context diff

[okura]

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

191

Thank you for the great suggestion. I think this comment explains the AA succinctly and accurately. As for case 3, we can regard that many potential values are found and we surpass the threshold. So I think the first 2 cases are sufficient.

[baziotis]

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

191

Glad you liked it. I think that the third is important, because it lays out how different Values affect one another. For example,
if the current Value is in an operation with a Value that is in worst state, then the current also goes into worst state but not because of the threshold.

[okura]

• add document
• eliminate an unnecessary include statement

[jdoerfert]

Apologies for the long wait. Here are some more comments.

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

3156

Make the two members private please, we can access them via getters.

3182

I would prefer if we update isAtWorstState as soon as we modify the set and reach the number of allowed values. So after each (potential) increase we check and update isAtWorstState. That way it is clear that "isValid" always equals "isAtWorstState". (We can also name isAtWorstState IsValid.)

3185

This "tracks" only the worst state fixpoint but not any other one, e.g., if it is a known constant. Are you sure we don't need a separate boolean to track this. I would have assumes so to avoid calling update on the AA after we used indicateOptimisticFixpoint.

One way to handle this is to replace isAtWorstState with a BooleanState which handles the fixpoint and the valid bit. You can probably even derive from that class to minimize the code you need to type, e.g., a lot of functions provided by BooleanState might then just be good enough. Only once you need to inspect or touch the Set you have to provide functions here.

3211

We might want to add an assertion here. no point in handing out meaningless data. (I guess other types lack such an assertion as well.)

3278

We should not have a variable like this but use !Assumed.isValid() for this.

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

7250

Would it make sense to let AAPotentialValuesCallSiteArgument derive from AAPotentialValuesFloating? We often do that.

[okura]

• change PotentialValueSet to inherit BooleanState
• change access specifier for some members
• add documents

[okura]

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

3185

I do not notice that it became unable to track fixpoint in the optimistic case by eliminating Known state. I changed this to derive from BooleanState as you suggest.
By this, I feel that PotentialValuesState becomes a simple (unnecessary) wrapper for PotentialValueSet. Do you think I have to merge two structs together?

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

7250

I will probably override both initialize and updateImpl in AAPotentialValuesCallSiteArgument. Even so, is deriving from AAPotentialValuesFloating better than from AAPotentialValuesImpl ?

[jdoerfert]

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

3185

If there is no reason (right now) to keep them separate, merge them. Keep it a template though, I think.

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

7250

The benefit usually is that initialize and/or updateImpl are the same or we want to do something special for the call site argument case and fall back to the floating case if it didn't work. So basically, if you can/want to reuse the floating logic somehow, it makes sense to inherit from the floating AA.

Take struct AAValueSimplifyCallSiteArgument : AAValueSimplifyFloating as an example. The "value" is derived the same regardless but the floating algorithm can use the CtxI which is set for the call site argument case.

[okura]

• merge PotentialValueSet and PotentialValuesState together
• derive AAPotentialValuesCallsiteArgument from AAPotentialValuesFloating

[jdoerfert]

Last set of minor comments. I think this is ready in after.

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

3076

Make this

template<>
struct DenseMapInfo<APInt> {

3110

The default state should not force the boolean state to "invalid". Just keep the default behavior which is to create an optimistic state by default.

3114

Do we need this?

3121

Make the return type const SetTy &. No need to copy the set always, if the caller wants to do that they still can.

3150

APInt should be MemberTy, right?

3197

Just check at the end once.

3211

Nit: IntersectSet

3242

Nit: TODO: Support values other than constant integers.

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

7099

I guess something like this should be the default implementation in AbstractAttribute already. We could probably remove quite a lot of duplication. Follow up ;)

7244

We don't need this method (for now). The one in AAPotentialValuesFloating will do fine (for now).

llvm/test/Transforms/Attributor/potential.ll

386

Manually add check lines for the ranges please.

[okura]

• remove AAPotentialValuesCallSiteArgument::initialize
• rename key info struct for APInt (and register it as friend of APInt)
• add check lines for range

I ran whole tests and I found tools/llvm-cov/universal_bin_wrapping_archives.test failed. I investigate the cause of it now.

[okura]

I built latest master branch and ran test, but that test failed again.

[okura]

@jdoerfert Could you give me feedback for this?

[jdoerfert]

Don't worry about the other test, master is sometimes broken as well. I left one comment for a follow up patch and one comment for a cleanup to avoid code duplication we have now.
Assuming that can be done without problems prior to committing this, the patch looks good to me :)

llvm/include/llvm/ADT/APInt.h

102 ↗

(On Diff #279116)

This is the same thing as DenseMapAPIntKeyInfo right? We should for sure avoid duplication. Let's just move the implementation into this header, call it DenseMapInfo<APInt>, and use it instead of DenseMapAPIntKeyInfo in LLVMContextImpl.h. That way everyone else can put an APInt into a DenseMap as well.

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

7165

In a follow up we should add a flag to the state to indicate it is not empty but contains undef. That would allow us to merge such a state with for example 7 and get 7.

[fhahn]

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

3276

nit: unnecessary ()

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

53

Why not just use MaxPotentialValues directly and keep it as a global? There might be a reason for doing so that I am missing, but it seems like similar options (e.g. MaxHeapToStackSize) are also just using the global directly.

[okura]

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

3276

These brackets are unnecessary indeed, but this function is one of the boilerplate functions of AbstactAttributes and the other AAs have the same implementation. So I think we don't need to remove them.

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

53

AAPotentialValues support only integer values now, and similar AA for pointer values or floating values might be introduced. To implement them, we can use the template class PotentialValuesState. I think it is better to be able to set a different threshold for each of them. That is why I keep it as a member variable of PotentialValuesState.

[okura]

• move DenseMapInfo<APInt> to APInt.h

[fhahn]

llvm/include/llvm/ADT/APInt.h

2293 ↗

(On Diff #282434)

I am not sure this is the right place. Shouldn't that go into DenseMapInfo.h? Also, if this gets added there, it should probably be split off from this patch.

[fhahn]

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

3276

FWIW, I think this is very uncommon in most parts of the llvm codebase.

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

53

But if you want to set them separately, you'd need separate options?

[thakis]

This causes:

llvm/lib/Transforms/IPO/AttributorAttributes.cpp:56:49: error: explicit specialization of 'MaxPotentialValues' after instantiation
unsigned llvm::PotentialConstantIntValuesState::MaxPotentialValues = 0;

^

../../llvm/lib/Transforms/IPO/AttributorAttributes.cpp:52:57: note: implicit instantiation first required here

cl::location(llvm::PotentialConstantIntValuesState::MaxPotentialValues),
                                                    ^

[okura]

llvm/include/llvm/ADT/APInt.h

2293 ↗

(On Diff #282434)

I'm sorry. I will move this into DenseMapInfo.h in a new patch.

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

3276

I think so too. I will make a new patch to remove these brackets in all AbstractAttriutes.

[okura]

In D83283#2189444, @thakis wrote:

This causes:

llvm/lib/Transforms/IPO/AttributorAttributes.cpp:56:49: error: explicit specialization of 'MaxPotentialValues' after instantiation
unsigned llvm::PotentialConstantIntValuesState::MaxPotentialValues = 0;

^

../../llvm/lib/Transforms/IPO/AttributorAttributes.cpp:52:57: note: implicit instantiation first required here

cl::location(llvm::PotentialConstantIntValuesState::MaxPotentialValues),
                                                    ^

I confirmed that I can build successfully with g++ but fail with clang.
Should I revert the commit right away?

[thakis]

If the fix is quick (< 15 min), you can fix too.

[fhahn]

In D83283#2189481, @okura wrote:

In D83283#2189444, @thakis wrote:

This causes:

llvm/lib/Transforms/IPO/AttributorAttributes.cpp:56:49: error: explicit specialization of 'MaxPotentialValues' after instantiation
unsigned llvm::PotentialConstantIntValuesState::MaxPotentialValues = 0;

^

../../llvm/lib/Transforms/IPO/AttributorAttributes.cpp:52:57: note: implicit instantiation first required here

cl::location(llvm::PotentialConstantIntValuesState::MaxPotentialValues),
                                                    ^

I confirmed that I can build successfully with g++ but fail with clang.
Should I revert the commit right away?

I'd just make the option a 'regular' global for now. This will avoid this problem. If the extra complexity is needed in the future, it can always be added back.

[okura]

I reverted the commit.

[okura]

• move DenseMapInfo<APInt> into DenseMapInfo.
• fix MaxPotentialValues and confirmed that I could build with both clang and g++.

[okura]

In D83283#2189485, @fhahn wrote:

In D83283#2189481, @okura wrote:

In D83283#2189444, @thakis wrote:

This causes:

llvm/lib/Transforms/IPO/AttributorAttributes.cpp:56:49: error: explicit specialization of 'MaxPotentialValues' after instantiation
unsigned llvm::PotentialConstantIntValuesState::MaxPotentialValues = 0;

^

../../llvm/lib/Transforms/IPO/AttributorAttributes.cpp:52:57: note: implicit instantiation first required here

cl::location(llvm::PotentialConstantIntValuesState::MaxPotentialValues),
                                                    ^

I confirmed that I can build successfully with g++ but fail with clang.
Should I revert the commit right away?

I'd just make the option a 'regular' global for now. This will avoid this problem. If the extra complexity is needed in the future, it can always be added back.

Now I'm trying to make it global.

[okura]

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

53

Yes, but if we give a different name for each threshold (e.g. MaxPotentialConstantIntValues, MaxPotentialFloatingValues, etc.), I think it is difficult to commonize implementations into PotentialValuesState. I tried to make PotentialValuesState take threshold as a template parameter, but I failed to do that because MaxPotentialValue cannot be a const variable.
FWIW, this option is used in Attributor.h unlike the other options declared in here and we need external storage. Due to this, MaxPotentialValue cannot be const.

If you have an idea, could you tell me that?

OTOH, I confirmed that I could successfully build the current patch with both clang and g++. If we don't necessarily have to change implementation, I can land this anytime.

[sstefan1]

llvm/include/llvm/ADT/DenseMapInfo.h

351 ↗

(On Diff #282488)

As @fhahn already mentioned, I guess you can commit DenseMapInfo part separately, as a NFC.

llvm/test/Transforms/Attributor/potential.ll

2

Can you run the update script with --check-attributes to keep it in sync with other attributor tests?

[okura]

llvm/include/llvm/ADT/DenseMapInfo.h

351 ↗

(On Diff #282488)

Sorry, I misunderstood the comment. I split the part. (D85131)

[okura]

• update tests with --check-attributes
• split patch into D85131

[okura]

• remove unnecessary change in APInt.h

[okura]

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

53

@fhahn Could you give me your opinion?

If there is no response for a while, I will land this.

[fhahn]

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

53

Oh right, now I see what you mean I think. I still think it would be better to only add the extra complexity once it is needed, but if it builds now I guess it's fine.

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

 // - Add a Statistics object for bookkeeping. If it is a simple (set of)
 //   attribute(s) manifested through the Attributor manifestation framework, see
 //   the bookkeeping function in Attributor.cpp.
 // - If instructions with a certain opcode are interesting to the attribute, add
 //   that opcode to the switch in `Attributor::identifyAbstractAttributes`. This
 //   will make it possible to query all those instructions through the
 //   `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;
enum Kind : char {
     IRP_ARGUMENT,           ///< An attribute for a function argument.
     IRP_CALL_SITE_ARGUMENT, ///< An attribute for a call site argument.
   };
 
   /// Default constructor available to create invalid positions implicitly. All
   /// other positions need to be created explicitly through the appropriate
   /// static member function.
   IRPosition() : Enc(nullptr, ENC_VALUE) { verify(); }
 
   /// Create a position describing the value of \p V.
   static const IRPosition value(const Value &V) {
     if (auto *Arg = dyn_cast<Argument>(&V))
       return IRPosition::argument(*Arg);
     if (auto *CB = dyn_cast<CallBase>(&V))
       return IRPosition::callsite_returned(*CB);
     return IRPosition(const_cast<Value &>(V), IRP_FLOAT);
   }
 
   /// Create a position describing the function scope of \p F.
   static const IRPosition function(const Function &F) {
     return IRPosition(const_cast<Function &>(F), IRP_FUNCTION);
   }
 
   /// Create a position describing the returned value of \p F.
   static const IRPosition returned(const Function &F) {
     return IRPosition(const_cast<Function &>(F), IRP_RETURNED);
   }
 
   /// Create a position describing the argument \p Arg.
   static const IRPosition argument(const Argument &Arg) {
     return IRPosition(const_cast<Argument &>(Arg), IRP_ARGUMENT);
struct AAValueConstantRange
   /// Return a known range for the assocaited value at a program point \p CtxI.
   /// If \p I is nullptr, simply return a known range.
   virtual ConstantRange
   getKnownConstantRange(Attributor &A,
                         const Instruction *CtxI = nullptr) const = 0;
 
   /// Return an assumed constant for the assocaited value a program point \p
   /// CtxI.
   Optional<ConstantInt *>
   getAssumedConstantInt(Attributor &A,
                         const Instruction *CtxI = nullptr) const {
     ConstantRange RangeV = getAssumedConstantRange(A, CtxI);
     if (auto *C = RangeV.getSingleElement())
       return cast<ConstantInt>(
           ConstantInt::get(getAssociatedValue().getType(), *C));
     if (RangeV.isEmptySet())
       return llvm::None;
     return nullptr;
   }
 
   /// See AbstractAttribute::getName()
   const std::string getName() const override { return "AAValueConstantRange"; }
 
   /// 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 isAtWorstState) : isAtWorstState(isAtWorstState) {}
+
+  PotentialValueSet(const SetTy &PS) : isAtWorstState(false) { Set = PS; }
+
+  bool operator==(const PotentialValueSet &RHS) const {
+    if (isAtWorstState != RHS.isAtWorstState)
+      return false;
+    return Set == RHS.Set;
+  }
+
+  void insert(const MemberTy &C) {
+    if (isAtWorstState)
+      return;
+    Set.insert(C);
+  }
+
+  /// Take union with R.
+  void unionWith(const PotentialValueSet &R) {
+    /// If this is a full set, do nothing.;
+    if (isAtWorstState)
+      return;
+    /// If R is full set, change L to a full set.
+    if (R.isAtWorstState) {
+      isAtWorstState = 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.isAtWorstState)
+      return;
+    /// If this is a full set, change this to R.
+    if (isAtWorstState) {
+      *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 isAtWorstState;
+
+  /// When \p isAtWorstState is false, this corresponds to the actual set.
+  SetTy Set;
+};
+
+using PotentialConstantIntValueSet =
+    PotentialValueSet<APInt, DenseMapAPIntKeyInfo>;
+
+/// State for potential values.
+struct PotentialValuesState : AbstractState {
+
+  using SetTy = PotentialConstantIntValueSet::SetTy;
+
+  using StateTy = PotentialConstantIntValueSet;
+
+  PotentialValuesState() : Assumed(false) {}
+
+  PotentialValuesState(const StateTy &PS) : 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.isAtWorstState && Assumed.Set.size() < MaxPotentialValues;
+  }
+
+  /// See AbstractState::isAtFixpoint()
+  bool isAtFixpoint() const override { return Assumed.isAtWorstState; }
+
+  /// See AbstractState::indicateOptimisticFixpoint(...)
+  ChangeStatus indicateOptimisticFixpoint() override {
+    return ChangeStatus::UNCHANGED;
+  }
+
+  /// See AbstractState::indicatePessimisticFixpoint(...)
+  ChangeStatus indicatePessimisticFixpoint() override {
+    Assumed.isAtWorstState = true;
+    return ChangeStatus::CHANGED;
+  }
+
+  /// Return empty set as the best state of potential values.
+  static StateTy getBestState() { return StateTy(/* isAtWorstState */ false); }
+  static StateTy getBestState(PotentialValuesState &PVS) {
+    return getBestState();
+  }
+
+  /// Return full set as the worst state of potential values.
+  static StateTy getWorstState() { return StateTy(/* isAtWorstState */ true); }
+
+  /// Return the assumed state.
+  StateTy getAssumed() const { return Assumed; }
+
+  /// Note: If Assumed.isAtWorstState is true, this is meaningless.
+  SetTy getAssumedSet() const { return Assumed.Set; }
+
+  /// Union assumed set with the passed value.
+  void unionAssumed(const APInt &C) { Assumed.insert(C); }
+
+  /// Union assumed set with the passed state.
+  void unionAssumed(const StateTy &R) { Assumed.unionWith(R); }
+
+  /// Union assumed set with assumed set of the passed state \p PVS.
+  void unionAssumed(const PotentialValuesState &PVS) {
+    unionAssumed(PVS.getAssumed());
+  }
+
+  /// "Clamp" this state with \p PVS.
+  PotentialValuesState operator^=(const PotentialValuesState &PVS) {
+    unionAssumed(PVS);
+    return *this;
+  }
+
+  PotentialValuesState operator&=(const PotentialValuesState &PVS) {
+    unionAssumed(PVS);
+    return *this;
+  }
+
+  /// A set representing assumed set of potential values.
+  StateTy Assumed;
+
+  /// Maximal number of potential values to be tracked.
+  /// This is set by -attributor-max-potential-values command line option
+  static unsigned MaxPotentialValues;
+};
+
+raw_ostream &operator<<(raw_ostream &OS, const PotentialValuesState &R);
+
+/// An abstract interface for potential values analysis.
+///
+/// This AA collects potential values for each IR position.
+/// An assumed set of potential values is initialized with the empty set (the
+/// best state) and it will grow while iteration. If the number of
+/// potential values become no less than the threshold \p MaxPotentialValues
+/// (this is given as command line option), we give up and the assumed set is
+/// set to a full set (the worse state).
+///
+/// TODO: Support other values than integers as well.
+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 (Assumed.isAtWorstState)
+      return nullptr;
+    if (getAssumedSet().size() == 1)
+      return cast<ConstantInt>(ConstantInt::get(getAssociatedValue().getType(),
+                                                *(getAssumedSet().begin())));
+    if (getAssumedSet().size() == 0)
+      return llvm::None;
+
+    return nullptr;
+  }
+
+  /// See AbstractAttribute::getName()
+  const std::string getName() const override { return "AAPotentialValues"; }
+
+  /// 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.Assumed.isAtWorstState)
+    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

 static cl::opt<bool> ManifestInternal(
     "attributor-manifest-internal", cl::Hidden,
     cl::desc("Manifest Attributor internal string attributes."),
     cl::init(false));
 
 static cl::opt<int> MaxHeapToStackSize("max-heap-to-stack-size", cl::init(128),
                                        cl::Hidden);
 
+static cl::opt<unsigned, true> MaxPotentialValues(
+    "attributor-max-potential-values", cl::Hidden,
+    cl::desc("Maximal number of potential values to be "
+             "tracked for each position."),
+    cl::location(llvm::PotentialValuesState::MaxPotentialValues), cl::init(7));
+unsigned llvm::PotentialValuesState::MaxPotentialValues;
+
 STATISTIC(NumAAs, "Number of abstract attributes created");
 
 // Some helper macros to deal with statistics tracking.
 //
 // Usage:
 // For simple IR attribute tracking overload trackStatistics in the abstract
 // attribute and choose the right STATS_DECLTRACK_********* macro,
 // e.g.,:
 //  void trackStatistics() const override {
 //    STATS_DECLTRACK_ARG_ATTR(returned)

 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,
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 << getState();
+    return OS.str();
+  }
+
+  /// See AbstractAttribute::updateImpl(...).
+  ChangeStatus updateImpl(Attributor &A) override {
+    return indicatePessimisticFixpoint();
+  }
+};
+
+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");
+  }
+
+  /// 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::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=9 -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=7 -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) {
+; CHECK-LABEL: define {{[^@]+}}@iszero1
+; CHECK-SAME: (i32 [[C:%.*]])
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[C]], 0
+; CHECK-NEXT:    ret i1 [[CMP]]
+;
+  %cmp = icmp eq i32 %c, 0
+  ret i1 %cmp
+}
+
+define i1 @potential_test1(i1 %c) {
+; CHECK-LABEL: define {{[^@]+}}@potential_test1
+; CHECK-SAME: (i1 [[C:%.*]])
+; CHECK-NEXT:    [[ARG:%.*]] = select i1 [[C]], i32 -1, i32 1
+; CHECK-NEXT:    [[RET:%.*]] = call i1 @iszero1(i32 [[ARG]])
+; CHECK-NEXT:    ret i1 [[RET]]
+;
+  %arg = select i1 %c, i32 -1, i32 1
+  %ret = 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) {
+; CHECK-LABEL: define {{[^@]+}}@iszero2
+; CHECK-SAME: (i32 [[C:%.*]])
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[C]], 0
+; CHECK-NEXT:    [[RET:%.*]] = zext i1 [[CMP]] to i32
+; CHECK-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__TUNIT____-LABEL: define {{[^@]+}}@call_with_two_values
+; IS__TUNIT____-SAME: (i32 [[C:%.*]])
+; IS__TUNIT____-NEXT:    [[CSRET1:%.*]] = call i32 @iszero2(i32 [[C]]) #0, !range !0
+; IS__TUNIT____-NEXT:    [[MINUSC:%.*]] = sub i32 0, [[C]]
+; IS__TUNIT____-NEXT:    [[CSRET2:%.*]] = call i32 @iszero2(i32 [[MINUSC]]) #0, !range !0
+; IS__TUNIT____-NEXT:    [[RET:%.*]] = add i32 [[CSRET1]], [[CSRET2]]
+; IS__TUNIT____-NEXT:    ret i32 [[RET]]
+;
+; 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 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 = call i32 @iszero2(i32 %c)
+  %minusc = sub i32 0, %c
+  %csret2 = call i32 @iszero2(i32 %minusc)
+  %ret = add 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:    [[CSRET1:%.*]] = call i32 @call_with_two_values(i32 1) #0, !range !1
+; IS__TUNIT____-NEXT:    [[CSRET2:%.*]] = call i32 @call_with_two_values(i32 -1) #1, !range !1
+; IS__TUNIT____-NEXT:    [[RET:%.*]] = add i32 [[CSRET1]], [[CSRET2]]
+; IS__TUNIT____-NEXT:    ret i32 [[RET]]
+;
+; 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:%.*]] = add i32 [[CSRET1]], [[CSRET2]]
+; IS__CGSCC____-NEXT:    ret i32 [[RET]]
+;
+  %csret1 = call i32 @call_with_two_values(i32 1)
+  %csret2 = call i32 @call_with_two_values(i32 -1)
+  %ret = add 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) {
+; CHECK-LABEL: define {{[^@]+}}@iszero3
+; CHECK-SAME: (i32 [[C:%.*]])
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[C]], 0
+; CHECK-NEXT:    [[RET:%.*]] = zext i1 [[CMP]] to i32
+; CHECK-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) {
+; CHECK-LABEL: define {{[^@]+}}@less_than_two
+; CHECK-SAME: (i32 [[C:%.*]])
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[C]], 2
+; CHECK-NEXT:    [[RET:%.*]] = zext i1 [[CMP]] to i32
+; CHECK-NEXT:    ret i32 [[RET]]
+;
+  %cmp = icmp slt i32 %c, 2
+  %ret = zext i1 %cmp to i32
+  ret i32 %ret
+}
+
+define i32 @potential_test3() {
+; NOT_TUNIT_NPM-LABEL: define {{[^@]+}}@potential_test3()
+; NOT_TUNIT_NPM-NEXT:    [[CMP1:%.*]] = call i32 @iszero3(i32 0)
+; NOT_TUNIT_NPM-NEXT:    [[TRUE1:%.*]] = call i32 @less_than_two(i32 [[CMP1]])
+; NOT_TUNIT_NPM-NEXT:    [[CMP2:%.*]] = call i32 @iszero3(i32 1)
+; NOT_TUNIT_NPM-NEXT:    [[TRUE2:%.*]] = call i32 @less_than_two(i32 [[CMP2]])
+; NOT_TUNIT_NPM-NEXT:    [[RET:%.*]] = add i32 [[TRUE1]], [[TRUE2]]
+; NOT_TUNIT_NPM-NEXT:    ret i32 [[RET]]
+;
+; IS__TUNIT_NPM-LABEL: define {{[^@]+}}@potential_test3()
+; IS__TUNIT_NPM-NEXT:    [[CMP1:%.*]] = call i32 @iszero3(i32 0) #0, !range !0
+; IS__TUNIT_NPM-NEXT:    [[TRUE1:%.*]] = call i32 @less_than_two(i32 [[CMP1]]) #0, !range !0
+; IS__TUNIT_NPM-NEXT:    [[CMP2:%.*]] = call i32 @iszero3(i32 1) #0, !range !0
+; IS__TUNIT_NPM-NEXT:    [[TRUE2:%.*]] = call i32 @less_than_two(i32 [[CMP2]]) #0, !range !0
+; IS__TUNIT_NPM-NEXT:    [[RET:%.*]] = add i32 [[TRUE1]], [[TRUE2]]
+; IS__TUNIT_NPM-NEXT:    ret i32 [[RET]]
+;
+  %cmp1 = call i32 @iszero3(i32 0)
+  %true1 = call i32 @less_than_two(i32 %cmp1)
+  %cmp2 = call i32 @iszero3(i32 1)
+  %true2 = call i32 @less_than_two(i32 %cmp2)
+  %ret = add i32 %true1, %true2
+  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:    [[CSRET:%.*]] = call i32 @return1or3(i32 [[C]]) #0, !range !2
+; IS__TUNIT____-NEXT:    [[FALSE:%.*]] = icmp eq i32 [[CSRET]], 2
+; IS__TUNIT____-NEXT:    [[RET:%.*]] = zext i1 [[FALSE]] to i32
+; IS__TUNIT____-NEXT:    ret i32 [[RET]]
+;
+; 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 = 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:    [[CSRET1:%.*]] = call i32 @return1or3(i32 [[C]]) #0, !range !2
+; IS__TUNIT____-NEXT:    [[CSRET2:%.*]] = call i32 @return2or4(i32 [[C]]) #0, !range !3
+; IS__TUNIT____-NEXT:    [[FALSE:%.*]] = icmp eq i32 [[CSRET1]], [[CSRET2]]
+; IS__TUNIT____-NEXT:    [[RET:%.*]] = zext i1 [[FALSE]] to i32
+; IS__TUNIT____-NEXT:    ret i32 [[RET]]
+;
+; 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 = call i32 @return1or3(i32 %c)
+  %csret2 = 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 !2
+; 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 !2
+; IS__TUNIT____-NEXT:    [[CSRET2:%.*]] = call i32 @return3or4(i32 [[C]]) #0, !range !4
+; 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) {
+; CHECK-LABEL: define {{[^@]+}}@return2or4
+; CHECK-SAME: (i32 [[C:%.*]])
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[C]], 0
+; CHECK-NEXT:    [[RET:%.*]] = select i1 [[CMP]], i32 2, i32 4
+; CHECK-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) {
+; CHECK-LABEL: define {{[^@]+}}@cmp_with_four
+; CHECK-SAME: (i32 [[C:%.*]])
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[C]], 4
+; CHECK-NEXT:    ret i1 [[CMP]]
+;
+  %cmp = icmp eq i32 %c, 4
+  ret i1 %cmp
+}
+
+define internal i1 @wrapper(i32 %c) {
+; CHECK-LABEL: define {{[^@]+}}@wrapper
+; CHECK-SAME: (i32 [[C:%.*]])
+; CHECK-NEXT:    [[RET:%.*]] = call i1 @cmp_with_four(i32 [[C]])
+; CHECK-NEXT:    ret i1 [[RET]]
+;
+  %ret = call i1 @cmp_with_four(i32 %c)
+  ret i1 %ret
+}
+
+define i1 @potential_test8() {
+; CHECK-LABEL: define {{[^@]+}}@potential_test8()
+; CHECK-NEXT:    [[RES1:%.*]] = call i1 @wrapper(i32 1)
+; CHECK-NEXT:    [[RES3:%.*]] = call i1 @wrapper(i32 3)
+; CHECK-NEXT:    [[RES5:%.*]] = call i1 @wrapper(i32 5)
+; CHECK-NEXT:    [[RES13:%.*]] = or i1 [[RES1]], [[RES3]]
+; CHECK-NEXT:    [[RES135:%.*]] = or i1 [[RES13]], [[RES5]]
+; CHECK-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() {
+; IS________OPM-LABEL: define {{[^@]+}}@potential_test9()
+; IS________OPM-NEXT:  entry:
+; IS________OPM-NEXT:    br label [[COND:%.*]]
+; IS________OPM:       cond:
+; IS________OPM-NEXT:    [[I_0:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[I_1:%.*]], [[INC:%.*]] ]
+; IS________OPM-NEXT:    [[C_0:%.*]] = phi i32 [ 1, [[ENTRY]] ], [ [[C_1:%.*]], [[INC]] ]
+; IS________OPM-NEXT:    [[CMP:%.*]] = icmp slt i32 [[I_0]], 10
+; IS________OPM-NEXT:    br i1 [[CMP]], label [[BODY:%.*]], label [[END:%.*]]
+; IS________OPM:       body:
+; IS________OPM-NEXT:    [[C_1]] = mul i32 [[C_0]], -1
+; IS________OPM-NEXT:    br label [[INC]]
+; IS________OPM:       inc:
+; IS________OPM-NEXT:    [[I_1]] = add i32 [[I_0]], 1
+; IS________OPM-NEXT:    br label [[COND]]
+; IS________OPM:       end:
+; IS________OPM-NEXT:    [[RET:%.*]] = icmp eq i32 [[C_0]], 0
+; IS________OPM-NEXT:    ret i1 [[RET]]
+;
+; IS________NPM-LABEL: define {{[^@]+}}@potential_test9()
+; IS________NPM-NEXT:  entry:
+; IS________NPM-NEXT:    br label [[COND:%.*]]
+; IS________NPM:       cond:
+; IS________NPM-NEXT:    [[I_0:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[I_1:%.*]], [[INC:%.*]] ]
+; IS________NPM-NEXT:    [[C_0:%.*]] = phi i32 [ 1, [[ENTRY]] ], [ [[C_1:%.*]], [[INC]] ]
+; IS________NPM-NEXT:    [[CMP:%.*]] = icmp slt i32 [[I_0]], 10
+; IS________NPM-NEXT:    br i1 [[CMP]], label [[BODY:%.*]], label [[END:%.*]]
+; IS________NPM:       body:
+; IS________NPM-NEXT:    [[C_1]] = mul i32 [[C_0]], -1
+; IS________NPM-NEXT:    br label [[INC]]
+; IS________NPM:       inc:
+; IS________NPM-NEXT:    [[I_1]] = add i32 [[I_0]], 1
+; IS________NPM-NEXT:    br label [[COND]]
+; IS________NPM:       end:
+; IS________NPM-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
+}