[Attributor] Add flag for undef value to the state of AAPotentialValues

[okura]

Summary

Currently, an undef value is reduced to 0 when it is added to a set of potential values.
This patch introduces a flag for under values. By this, for example, we can merge two states {undef}, {1} to {1} (because we can reduce the undef to 1).

[okura]

• check the flag in ==operator

[okura]

• change operator<< for PotentialConstantIntValuesState

[jdoerfert]

Cool. I think the code is fine, one minor simplification to consider below. We need tests though.

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

3462–3464

[okura]

• Change to fit other landed patch

[okura]

In D85592#2205403, @jdoerfert wrote:

We need tests though.

It seems difficult for me to reflect this change in IR of tests because we have not implemented any updateImpl of AAPotentialValues and have not made any use of it yet.
Should I add test and land this after implementing them?

[jdoerfert]

In D85592#2205702, @okura wrote:

In D85592#2205403, @jdoerfert wrote:

We need tests though.

It seems difficult for me to reflect this change in IR of tests because we have not implemented any updateImpl of AAPotentialValues and have not made any use of it yet.
Should I add test and land this after implementing them?

I would prefer to land this with a test. If we need another patch first, so be it. However, I think AACallSiteReturnedFromReturned and AAReturnedFromReturnedValues could save us here.

What happens if you have

static int foo(int c) {
  int x;
  if (c == -2)
   return -2;
  if (c == 2)
   return 2;
  return x;
}
int bar(int c) {
  return foo(c) != 0;
}

With the patch I'd expect bar to just return 1. Is this the case?

[okura]

In D85592#2205744, @jdoerfert wrote:

However, I think AACallSiteReturnedFromReturned and AAReturnedFromReturnedValues could save us here.

What happens if you have

static int foo(int c) {
  int x;
  if (c == -2)
   return -2;
  if (c == 2)
   return 2;
  return x;
}
int bar(int c) {
  return foo(c) != 0;
}

With the patch I'd expect bar to just return 1. Is this the case?

Thank you for giving an example. We can calculate that the returned potential values are {2,-2} without another patch.
But I think we need to implement AAPotentialValuesFloating to calculate that the result of comparison in bar is 1.
Foremost, AAPotentialValues are not identified unless we connect AAPotentialValues with AAValueSimplify.
Therefore, I will upload another patch to do that soon.

[okura]

• handle undef in update functions
• add tests

[fhahn]

I am not sure if the following scenario is possible, but if it is it might be problematic when undef is unified with multiple values. E.g. we found that we have the following potential values 0, 1, undef. If we now assume this is 0, 1, we might simplify and %x, 3 to %x. But that is wrong, if %x is undef. Note that simplifications that result in a constant should be fine either way. As I said, not sure if the potential values could be used like that (possibly in the future).

[jdoerfert]

In D85592#2221557, @fhahn wrote:

I am not sure if the following scenario is possible, but if it is it might be problematic when undef is unified with multiple values. E.g. we found that we have the following potential values 0, 1, undef. If we now assume this is 0, 1, we might simplify and %x, 3 to %x. But that is wrong, if %x is undef. Note that simplifications that result in a constant should be fine either way. As I said, not sure if the potential values could be used like that (possibly in the future).

It doesn't seem to be a problem now. Two results from the IRC discussion:

1. We need a test for the above situation, to make sure we don't regress this.
2. We should make sure when we merge the possible values with undef properly, e.g., if you intersect two sets of possible values {0,1,undef} and {0, 7} then we should get {0, 7}.

[okura]

In D85592#2221775, @jdoerfert wrote:

In D85592#2221557, @fhahn wrote:

I am not sure if the following scenario is possible, but if it is it might be problematic when undef is unified with multiple values. E.g. we found that we have the following potential values 0, 1, undef. If we now assume this is 0, 1, we might simplify and %x, 3 to %x. But that is wrong, if %x is undef. Note that simplifications that result in a constant should be fine either way. As I said, not sure if the potential values could be used like that (possibly in the future).

It doesn't seem to be a problem now. Two results from the IRC discussion:

1. We need a test for the above situation, to make sure we don't regress this.
2. We should make sure when we merge the possible values with undef properly, e.g., if you intersect two sets of possible values {0,1,undef} and {0, 7} then we should get {0, 7}.

I'm not sure we have to take care of intersection. Currently, there is PotentialValueState::intersectWith but is not used anywhere. I am not able to come up with a case we need it, and I think it should be deleted.

[jdoerfert]

What happens if you have something like

int foo(int c0, int c1, int c2, int c3) {
   int undef;
   int x0 = c0 ? 0 : 1;
   int x1 = c1 ? x0 : undef;
   int y2 = c2 ? 0 : 7;
   int z3 = c3 ? x1 : y2;
   return z3 < 7;
}

int bar(int c0, int c1 ) {
   int undef;
   int x0 = c0 ? 0 : 1;
   int x1 = c1 ? x0 : undef;
   return x1 == 7;
}
int bar(int c0, int c1 ) {
   int undef;
   int x0 = c0 ? 0 : undef;
   int x1 = c1 ? x0 : 1;
   return x1 == 7;
}

[okura]

In D85592#2236740, @jdoerfert wrote:

What happens if you have something like

int foo(int c0, int c1, int c2, int c3) {
   int undef;
   int x0 = c0 ? 0 : 1;
   int x1 = c1 ? x0 : undef;
   int y2 = c2 ? 0 : 7;
   int z3 = c3 ? x1 : y2;
   return z3 < 7;
}

int bar(int c0, int c1 ) {
   int undef;
   int x0 = c0 ? 0 : 1;
   int x1 = c1 ? x0 : undef;
   return x1 == 7;
}
int bar(int c0, int c1 ) {
   int undef;
   int x0 = c0 ? 0 : undef;
   int x1 = c1 ? x0 : 1;
   return x1 == 7;
}

I'm sorry, I don't understand what you expect. The following is my understanding. Could you point out where I'm wrong?

1. I don't understand the essential difference between the two bar functions. I think the potential values of x1 are {0,1}, and the returned value can be simplified to false in both cases.
2. As for foo, we cannot simplify the returned value because the potential value set of z3 is {0,1,7}. I'm not sure how we can take advantage of undef in these examples.

[jdoerfert]

LGTM.

In D85592#2240079, @okura wrote:

I'm sorry, I don't understand what you expect. The following is my understanding. Could you point out where I'm wrong?

1. I don't understand the essential difference between the two bar functions. I think the potential values of x1 are {0,1}, and the returned value can be simplified to false in both cases.
2. As for foo, we cannot simplify the returned value because the potential value set of z3 is {0,1,7}. I'm not sure how we can take advantage of undef in these examples.

I think you are correct. The examples do not show what I want (we should add them anyway).

[okura]

• fix initialization at callsite argument position (value-simplify.ll is affected)
• add tests

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

 /// contains every possible value (i.e. we cannot in any way limit the value
 /// that the target position can take). That never happens naturally, we only
 /// force it. As for the conditions under which we force it, see
 /// AAPotentialValues.
 template <typename MemberTy, typename KeyInfo = DenseMapInfo<MemberTy>>
 struct PotentialValuesState : AbstractState {
   using SetTy = DenseSet<MemberTy, KeyInfo>;
 
-  PotentialValuesState() : IsValidState(true) {}
+  PotentialValuesState() : IsValidState(true), UndefIsContained(false) {}
 
-  PotentialValuesState(bool IsValid) : IsValidState(IsValid) {}
+  PotentialValuesState(bool IsValid)
+      : IsValidState(IsValid), UndefIsContained(false) {}
 
   /// See AbstractState::isValidState(...)
   bool isValidState() const { return IsValidState.isValidState(); }
 
   /// See AbstractState::isAtFixpoint(...)
   bool isAtFixpoint() const { return IsValidState.isAtFixpoint(); }
 
   /// See AbstractState::indicatePessimisticFixpoint(...)
struct PotentialValuesState : AbstractState {
 
   /// Return this set. We should check whether this set is valid or not by
   /// isValidState() before calling this function.
   const SetTy &getAssumedSet() const {
     assert(isValidState() && "This set shoud not be used when it is invalid!");
     return Set;
   }
 
+  /// Returns whether this state contains an undef value or not.
+  bool undefIsContained() const {
+    assert(isValidState() && "This flag shoud not be used when it is invalid!");
+    return UndefIsContained;
+  }
+
   bool operator==(const PotentialValuesState &RHS) const {
     if (isValidState() != RHS.isValidState())
       return false;
     if (!isValidState() && !RHS.isValidState())
       return true;
+    if (undefIsContained() != RHS.undefIsContained())
+      return false;
     return Set == RHS.getAssumedSet();
   }
 
   /// Maximum number of potential values to be tracked.
   /// This is set by -attributor-max-potential-values command line option
   static unsigned MaxPotentialValues;
 
   /// Return empty set as the best state of potential values.
struct PotentialValuesState : AbstractState {
   }
 
   /// Union assumed set with the passed value.
   void unionAssumed(const MemberTy &C) { insert(C); }
 
   /// Union assumed set with assumed set of the passed state \p PVS.
   void unionAssumed(const PotentialValuesState &PVS) { unionWith(PVS); }
 
+  /// Union assumed set with an undef value.
+  void unionAssumedWithUndef() { unionWithUndef(); }
+
   /// "Clamp" this state with \p PVS.
   PotentialValuesState operator^=(const PotentialValuesState &PVS) {
     unionAssumed(PVS);
     return *this;
   }
 
   PotentialValuesState operator&=(const PotentialValuesState &PVS) {
     unionAssumed(PVS);
     return *this;
   }
 
 private:
   /// Check the size of this set, and invalidate when the size is no
   /// less than \p MaxPotentialValues threshold.
   void checkAndInvalidate() {
     if (Set.size() >= MaxPotentialValues)
       indicatePessimisticFixpoint();
   }
 
+  /// If this state contains both undef and not undef, we can reduce
+  /// undef to the not undef value.
+  void reduceUndefValue() { UndefIsContained = UndefIsContained & Set.empty(); }
+
   /// Insert an element into this set.
   void insert(const MemberTy &C) {
     if (!isValidState())
       return;
     Set.insert(C);
     checkAndInvalidate();
   }
 
   /// Take union with R.
   void unionWith(const PotentialValuesState &R) {
     /// If this is a full set, do nothing.;
     if (!isValidState())
       return;
     /// If R is full set, change L to a full set.
     if (!R.isValidState()) {
       indicatePessimisticFixpoint();
       return;
     }
     for (const MemberTy &C : R.Set)
       Set.insert(C);
+    UndefIsContained |= R.undefIsContained();
+    reduceUndefValue();
     checkAndInvalidate();
   }
 
+  /// Take union with an undef value.
+  void unionWithUndef() {
+    UndefIsContained = true;
+    reduceUndefValue();
+  }
+
   /// Take intersection with R.
   void intersectWith(const PotentialValuesState &R) {
     /// If R is a full set, do nothing.
     if (!R.isValidState())
       return;
     /// If this is a full set, change this to R.
     if (!isValidState()) {
       *this = R;
       return;
     }
     SetTy IntersectSet;
     for (const MemberTy &C : Set) {
       if (R.Set.count(C))
         IntersectSet.insert(C);
     }
     Set = IntersectSet;
+    UndefIsContained &= R.undefIsContained();
+    reduceUndefValue();
   }
 
   /// A helper state which indicate whether this state is valid or not.
   BooleanState IsValidState;
 
   /// Container for potential values
   SetTy Set;
+
+  /// Flag for undef value
+  bool UndefIsContained;
 };
 
 using PotentialConstantIntValuesState = PotentialValuesState<APInt>;
 
 raw_ostream &operator<<(raw_ostream &OS,
                         const PotentialConstantIntValuesState &R);
 
 /// An abstract interface for potential values analysis.
struct AAPotentialValues
   Optional<ConstantInt *>
   getAssumedConstantInt(Attributor &A,
                         const Instruction *CtxI = nullptr) const {
     if (!isValidState())
       return nullptr;
     if (getAssumedSet().size() == 1)
       return cast<ConstantInt>(ConstantInt::get(getAssociatedValue().getType(),
                                                 *(getAssumedSet().begin())));
-    if (getAssumedSet().size() == 0)
+    if (getAssumedSet().size() == 0) {
+      if (undefIsContained())
+        return cast<ConstantInt>(
+            ConstantInt::get(getAssociatedValue().getType(), 0));
       return llvm::None;
+    }
 
     return nullptr;
   }
 
   /// See AbstractAttribute::getName()
   const std::string getName() const override { return "AAPotentialValues"; }
 
   /// See AbstractAttribute::getIdAddr()

llvm/lib/Transforms/IPO/Attributor.cpp

raw_ostream &llvm::operator<<(raw_ostream &OS, const AbstractAttribute &AA) {
   return OS;
 }
 
 raw_ostream &llvm::operator<<(raw_ostream &OS,
                               const PotentialConstantIntValuesState &S) {
   OS << "set-state(< {";
   if (!S.isValidState())
     OS << "full-set";
-  else
+  else {
     for (auto &it : S.getAssumedSet())
       OS << it << ", ";
+    if (S.undefIsContained())
+      OS << "undef ";
+  }
   OS << "} >)";
 
   return OS;
 }
 
 void AbstractAttribute::print(raw_ostream &OS) const {
   OS << "[";
   OS << getName();

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

void initialize(Attributor &A) override {
 
     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));
+      unionAssumedWithUndef();
       indicateOptimisticFixpoint();
       return;
     }
 
     if (isa<BinaryOperator>(&V) || isa<ICmpInst>(&V) || isa<CastInst>(&V))
       return;
 
     if (isa<SelectInst>(V) || isa<PHINode>(V))