[Attributor] Implement AAPotentialValues

[okura]

Summary

This patch provides an implementation of AAPotentialValues.

[okura]

add updateImpl implementation and update tests

[okura]

• fix operators in PotentialValuesState (merged from D85639)

[jdoerfert]

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

3490 ↗

(On Diff #284340)

I failed to determine why this cannot be private anymore.

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

4513

Can you split this off into an NFC patch. Will make this one much simpler.

[jdoerfert]

I think we should limit the "entry point" for this AA. It seems we can only improve AAValueSimplify when the instruction we look at is a conditional, right? So if it is, we ask AAPotentialValues, otherwise we do not. Other users of AAPotentialValues will emerge but for this use we can restrict it to the case we can actually fold the multiple values in to a single constant. Other users might be OK with multiple values, e.g., to determine a common property.

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

7343

Add a TODO that we should look at nsw and nuw to help, e.g., to exclude certain results that cannot happen without creating undef. Similarly, division by undef should not make the result invalid but simply skip this operand pair.

7358

Why do we have the copy sometimes and sometimes not? Are the operators missing in the APInt class? If so, we should fix that in a pre-patch first.

7406

Here and below we should avoid looking at RHS if LHSAA is invalid.

7412

Please add a type here, and (or at least) make it a const reference. Also other places.

7420

We should give up once both are true.

[okura]

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

3490 ↗

(On Diff #284340)

I thought PVS.IsValidState in operators violate access specifier but that was my mistake, sorry.
I'll fix this.

[okura]

• fix access specifier of IsValidState
• split patch into D85668 (Connecting part)

[okura]

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

7343

I understand you mean that we can assume the operation result is not a poison value or undef and that we can ignore such operand pair. Is that right?
I'm thinking of adding a new argument bool &Unsupported to this to distinguish the above case from the case opcode is unsupported.
In the former case we skip the operand pair, and in the latter case we give up (i.e. call indicatePessimisticFixpoint).

[jdoerfert]

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

7343

Yes and no. So there are two things.

1. If the operation would be poison or undef, we can add undef to the set instead of something else. Undef is strictly better than any other APInt. This is the case for the nuw/nsw binary ops but I would not go there right now. A TODO makes more sense and a follow up patch.
2. If the operation would be UB, that is it can actually not happen, we can ignore the result. Think of a division in which the RHS is {0, 1}. Since division by 0 is UB, we can ignore that result and only take the 1 result.

Have such a bool reference argument makes sense, maybe call it "SkipOperation" or something and pass it through to the caller so we can just go ahead and ignore this combination of LHS/RHS.

[okura]

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

7358

Are the operators missing in the APInt class?

Yes, there are only compound assignment operators for some opcodes. I'll make a new patch for this.

[okura]

• fix the places that were pointed out

[jdoerfert]

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

7358

Why do we want the assignment operators? Why not just LHS + RHS?

[okura]

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

7343

I understand. I'll rename Valid with SkipOperation and add Unsupported.

7358

Sorry, I read doxygen of APInt and mistakenly thought there is not operator+. I'll fix this.

[okura]

• fix calculateBinaryOperator

[jdoerfert]

I think this patch is good. We should try to limit the queries to useful ones. We can do that after though. Maybe we check the instruction opcode in getAssumedConstantInt to make sure we only run this for Instructions that can fold multiple values into a single one, so far probably only compare instructions. We could also add a separate method that determines if this AAValueSimplify-like AA is good for a certain position or not. Either way, that should result in way less iterations without loosing any optimizations. Feel free to give it a try :)

LGTM.

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

7426

You can indicate a pessimistic fixpoint here. It's an i1 which can be true and false :)

[okura]

• update diff to fit D85668

[okura]

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

7426

If I indicate a pessimistic fixpoint, the state becomes invalid. If not, the state becomes {0,1}. I think this difference makes the deduction weaker. For example, the expected value simplification is not achieved in the case @potential_test3 in potential.ll.
I think I should handle known (the worst) state for values that have a very small bit width.
In the following example, the returned value's state becomes an invalid state with current implementation. But it should be {0,1}, I think.

define i32 @foo(i1 %c) {
  %ret = zext i1 %c to i32
  ret i32 %ret
}

[okura]

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

7426

I thought about this again and I noticed that this kind of analysis can (should) be done by AAValueConstantRange.
However, value simplification does not work expectedly in the current implementation as we can see with @potential_test3.
I investigated the cause of this and I found out the cause is bugs in AAConstantRange.
I will make a new patch for it.

[okura]

• fix updateWithICmpInst
• modify test

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

static bool checkAndUpdate(Attributor &A, const AbstractAttribute &QueryingAA,
     LLVM_DEBUG(dbgs() << "[ValueSimplify] " << QueryingValue
                       << " is assumed to be "
                       << QueryingValueSimplifiedUnwrapped << "\n");
 
     AccumulatedSimplifiedValue = QueryingValueSimplified;
     return true;
   }
 
-  bool askSimplifiedValueForAAValueConstantRange(Attributor &A) {
+  /// Returns a candidate is found or not
+  /// \p failAll is true when nullptr is returned by all other AAs
+  /// If at least one AA returns llvm::None, a candidate may be found in later
+  /// iteration.
+  template <typename AAType>
+  bool askSimplifiedValueFor(Attributor &A, bool &failAll) {
     if (!getAssociatedValue().getType()->isIntegerTy())
       return false;
 
-    const auto &ValueConstantRangeAA =
-        A.getAAFor<AAValueConstantRange>(*this, getIRPosition());
+    const auto &AA =
+        A.getAAFor<AAType>(*this, getIRPosition(), /* TrackDependence */ true,
+                           DepClassTy::OPTIONAL);
 
-    Optional<ConstantInt *> COpt =
-        ValueConstantRangeAA.getAssumedConstantInt(A);
-    if (COpt.hasValue()) {
-      if (auto *C = COpt.getValue())
-        SimplifiedAssociatedValue = C;
-      else
-        return false;
+    Optional<ConstantInt *> COpt = AA.getAssumedConstantInt(A);
+
+    if (!COpt.hasValue()) {
+      failAll = false;
     } else {
-      SimplifiedAssociatedValue = llvm::None;
-    }
+      if (auto *C = COpt.getValue()) {
+        SimplifiedAssociatedValue = C;
+        return true;
+      } else {
+        return false;
+      }
+    }
+
+  bool askSimplifiedValueForOtherAAs(Attributor &A) {
+    bool failAll = true;
+    SimplifiedAssociatedValue = llvm::None;
+    if (askSimplifiedValueFor<AAValueConstantRange>(A, failAll))
+      return true;
+    if (askSimplifiedValueFor<AAPotentialValues>(A, failAll))
       return true;
+    return !failAll;
   }
 
   /// See AbstractAttribute::manifest(...).
   ChangeStatus manifest(Attributor &A) override {
     ChangeStatus Changed = ChangeStatus::UNCHANGED;
 
     if (SimplifiedAssociatedValue.hasValue() &&
         !SimplifiedAssociatedValue.getValue())
       return Changed;
auto PredForCallSite = [&](AbstractCallSite ACS) {
           if (C->isThreadDependent())
             return false;
       return checkAndUpdate(A, *this, ArgOp, SimplifiedAssociatedValue);
     };
 
     bool AllCallSitesKnown;
     if (!A.checkForAllCallSites(PredForCallSite, *this, true,
                                 AllCallSitesKnown))
-      if (!askSimplifiedValueForAAValueConstantRange(A))
+      if (!askSimplifiedValueForOtherAAs(A))
         return indicatePessimisticFixpoint();
 
     // If a candicate was found in this update, return CHANGED.
     return HasValueBefore == SimplifiedAssociatedValue.hasValue()
                ? ChangeStatus::UNCHANGED
                : ChangeStatus ::CHANGED;
   }
 
struct AAValueSimplifyReturned : AAValueSimplifyImpl {
   ChangeStatus updateImpl(Attributor &A) override {
     bool HasValueBefore = SimplifiedAssociatedValue.hasValue();
 
     auto PredForReturned = [&](Value &V) {
       return checkAndUpdate(A, *this, V, SimplifiedAssociatedValue);
     };
 
     if (!A.checkForAllReturnedValues(PredForReturned, *this))
-      if (!askSimplifiedValueForAAValueConstantRange(A))
+      if (!askSimplifiedValueForOtherAAs(A))
         return indicatePessimisticFixpoint();
 
     // If a candicate was found in this update, return CHANGED.
     return HasValueBefore == SimplifiedAssociatedValue.hasValue()
                ? ChangeStatus::UNCHANGED
                : ChangeStatus ::CHANGED;
   }
 
auto VisitValueCB = [&](Value &V, const Instruction *CtxI, bool &,
       }
       return checkAndUpdate(A, *this, V, SimplifiedAssociatedValue);
     };
 
     bool Dummy = false;
     if (!genericValueTraversal<AAValueSimplify, bool>(
             A, getIRPosition(), *this, Dummy, VisitValueCB, getCtxI(),
             /* UseValueSimplify */ false))
-      if (!askSimplifiedValueForAAValueConstantRange(A))
+      if (!askSimplifiedValueForOtherAAs(A))
         return indicatePessimisticFixpoint();
 
     // If a candicate was found in this update, return CHANGED.
 
     return HasValueBefore == SimplifiedAssociatedValue.hasValue()
                ? ChangeStatus::UNCHANGED
                : ChangeStatus ::CHANGED;
   }
struct AAPotentialValuesCallSiteReturned
   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;
switch (IRP.getPositionKind()) {                                           \
       SWITCH_PK_CREATE(CLASS, IRP, IRP_FUNCTION, Function)                     \
       SWITCH_PK_CREATE(CLASS, IRP, IRP_CALL_SITE, CallSite)                    \
     }                                                                          \
     return *AA;                                                                \
   }
 
 #define CREATE_VALUE_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_FUNCTION, "function")                           \
       SWITCH_PK_INV(CLASS, IRP_CALL_SITE, "call site")                         \
       SWITCH_PK_CREATE(CLASS, IRP, IRP_FLOAT, Floating)                        \
       SWITCH_PK_CREATE(CLASS, IRP, IRP_ARGUMENT, Argument)                     \
       SWITCH_PK_CREATE(CLASS, IRP, IRP_RETURNED, Returned)                     \
       SWITCH_PK_CREATE(CLASS, IRP, IRP_CALL_SITE_RETURNED, CallSiteReturned)   \
       SWITCH_PK_CREATE(CLASS, IRP, IRP_CALL_SITE_ARGUMENT, CallSiteArgument)   \
     }                                                                          \
     return *AA;                                                                \
   }
 
 #define CREATE_ALL_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_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_RETURNED, Returned)                     \
       SWITCH_PK_CREATE(CLASS, IRP, IRP_CALL_SITE_RETURNED, CallSiteReturned)   \
       SWITCH_PK_CREATE(CLASS, IRP, IRP_CALL_SITE_ARGUMENT, CallSiteArgument)   \
     }                                                                          \
     return *AA;                                                                \
   }