[WIP][Attributor] AAReachability Attribute

[pgode]

Summary

Working towards Johannes's suggestion for fixme, in Attributor's Noalias attribute deduction.
(ii) Check whether the value is captured in the scope using AANoCapture.
FIXME: This is conservative though, it is better to look at CFG and
// check only uses possibly executed before this call site.

A Reachability abstract attribute answers the question "does execution at point A potentially reach point B". If this question is answered with false for all other uses of the value that might be captured, we know it is not *yet* captured and can continue with the noalias deduction. Currently, information AAReachability provides is completely pessimistic.

[jdoerfert]

Thanks for putting this in the open! I hope we can improve this and get it in!

---

Here are some high-level comments I had after looking over the patch:

I don't know how we would handle "reachability" as an actual IR-attribute. For now you might want to strip this to only the Attributor parts which can deal with it as an "abstract" attribute, like liveness or heaptostack.

We should start with AAReachabilityFunction only which answers the following questions:
Given two IRPositions, is one assumed/known reachable from another.
To this end, AAReachability will need to expose these query functions, e.g.,:
AAReachability::isAssumedReachable(const IRPosition &From, const IRPosition &To)
AAReachability::isKnownReachable(const IRPosition &From, const IRPosition &To)

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

1687

You don't need this to be an IRAttribute, an AbstractAttribute is sufficient. You will need to store the IRPosition in the class explicitly though.

llvm/lib/Transforms/IPO/Attributor.cpp

5480

I don't know if we need to create AAReachability or if we only want to "derive" it whenever another attribute requests the information. Since for now we cannot manifest it, I would not try to create it eagerly but only on demand. That means, remove these two getOrCreateAAFor calls but we later add getOrCreateAAFor<AAReachability> as part of the deduction (via updateImpl) in other attributes.

5826

We should start by a function only abstract attribute (like AAHeapToStack).
The macro for those is CREATE_FUNCTION_ONLY_ABSTRACT_ATTRIBUTE_FOR_POSITION
and you only need the AAReachabilityFunction derivation of AAReachability.
(See the main comment).

[sstefan1]

Nice to see other people working on this! :)

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

1687

I guess then we don't even need to have an actual IR attribute (and all the boilerplate that comes with it).

[uenoku]

I think reachability attribute is a good idea!

A Reachability abstract attribute answers the question "does execution at point A potentially reach point B". If this question is answered with false for all other uses of the value that might be captured, we know it is not *yet* captured and can continue with the noalias deduction. Currently, information AAReachability provides is completely pessimistic.

At the starting point, in AAReachability deduction, it might be a good idea to use AAIsDead to determine that "does execution at point A never reach point B" (because AAIsDead answers whether point B is dead).

Btw, I think AAIsDead is a strict subset of AAReachability. If we have AAReachability::isAssumedReachable(Instruction &From, Instruction &To), AAIsDead::isAssumedDead(Instruction &I) is equivalent to `!AAReachability::isAssumedReachable(EntryPointOfFunction, I).So you should probably extend AAIsDead.

Maybe you can refer must-be-executed-context which handles the similar property.

[jdoerfert]

In D70233#1746964, @uenoku wrote:

I think reachability attribute is a good idea!

A Reachability abstract attribute answers the question "does execution at point A potentially reach point B". If this question is answered with false for all other uses of the value that might be captured, we know it is not *yet* captured and can continue with the noalias deduction. Currently, information AAReachability provides is completely pessimistic.

At the starting point, it might be a good idea to use AAIsDead to determine that "does execution at point A never reach point B" (because AAIsDead answers whether point B is dead).

Btw, I think AAIsDead is a strict subset of AAReachability. If we have AAReachability::isAssumedReachable(Instruction &From, Instruction &To), AAIsDead::isAssumedDead(Instruction &I) is equivalent to `!AAReachability::isAssumedReachable(EntryPointOfFunction, I).So you should probably extend AAIsDead.

Maybe you can refer must-be-executed-context which handles the similar property.

I agree and this is certainly an option. At the end of the day, it should not matter if we keep it separate or merge them, we can always use on from the other.
Let's get the class skeleton in place with the right methods etc and we take it step by step from there.

[pgode]

Thank you @jdoerfert , @sstefan1 and @uenoku for your helpful comments.
Submitting updated patch with corrections.

[jdoerfert]

Thanks for the quick update.

You can (for now) remove the changes that are not in Attributor.{h,cpp} as they all relate to an IR attribute (which we might want to have but that is a different beast).
Other than that there is the query interface that needs to change to provide the positions the user is interested in (see below).

Once these two changes are done we can merge the skeleton code in.

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

1695

I would replace the two methods above by:

AAReachability::isAssumedReachable(const IRPosition &From, const IRPosition &To)
AAReachability::isKnownReachable(const IRPosition &From, const IRPosition &To)

with their implementation (initially always return true) in AAReachabilityImpl or AAReachabilityFunction.

The idea is that users provide the two positions they are interested in and the class determines (and caches) reachability.

llvm/lib/Transforms/IPO/Attributor.cpp

2074

If you keep two classes only one needs the trackStatistics

2082

For functions we use:
STATS_DECLTRACK_FN_ATTR

[pgode]

@jdoerfert Thank you suggesting the corrections.
Updating the corrected patch.

I think, function getAsStr() should be returning 'from' and 'to' position, but for that we need to store the From and To.
For now, I am returning 'reachable' by default.

[jdoerfert]

In D70233#1748026, @pgode wrote:

@jdoerfert Thank you suggesting the corrections.
Updating the corrected patch.

I think you still need to remove the other files from the patch, then it will be good to go in.
I'll accept the patch ones it is updated.

Btw., do you have commit access?

I think, function getAsStr() should be returning 'from' and 'to' position, but for that we need to store the From and To.
For now, I am returning 'reachable' by default.

That is fine for now. We do not have a concept of "attribute for pairs". Instead AAReachability is more like a container that computes and caches queries. You can return the number of cached queries in the getAsStr(), similar to what AAHeapToStack does.

---

Next step is to use AANoReachable at the capture todo we talked about. Even if it is captured, we can iterate over all uses of the pointer, skip the one in the call site we are looking at, and if the call site is not reachable from any of the uses, we can allow noalias still. Does that make sense?

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

1698

Nit Please update the comments of the functions.

[pgode]

Thanks @jdoerfert for the helpful corrections. I have removed the files. (I should have removed them in the last patch.)
I will start working on the next part.

[pgode]

Updated the function comments.

[pgode]

Btw., do you have commit access?

Yes, I have commit access. I had requested Tom Stellard for it.

[uenoku]

It seems a bit weird for me to use IRPosition as a program point. Therefore, I think it is better to use Instruction instead of IRPosition. So the interface will be

bool isAssumedReachable(const Instruction &From, const Instruction &To)

What do you think?

llvm/lib/Transforms/IPO/Attributor.cpp

2066

nit: You can call indicatePessimisticFixpoint directly.

[pgode]

In D70233#1753619, @uenoku wrote:

It seems a bit weird for me to use IRPosition as a program point. Therefore, I think it is better to use Instruction instead of IRPosition. So the interface will be

bool isAssumedReachable(const Instruction &From, const Instruction &To)

What do you think?

Thanks for reviewing. I think the IRPosition gives better information than Instruction, in the reachability context. I observe that IRPosition is created for Function, Argument, Callsite etc.
Nevertheless, if client tries to use Instruction instead of IRPosition then we need to overload.

[pgode]

Thanks for highlighting the nit. Corrected it.

[sstefan1]

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

1690

I kind of agree with @uenoku here. If you still want to stick with IRPosition, then you might want to change these comments.

[pgode]

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

1690

I looked at isKnownDead(Instruction*) and isAssumedDead(Instruction *) and I think we are expecting something similar.
I will make the changes and submit the updated patch.
Thanks for clarifying.

[pgode]

Updated the patch as per review comments.

[sstefan1]

This is LGTM from me now, but lets wait for Johaness as well.

[jdoerfert]

LGTM.

[jdoerfert]

We can merge this and then add a user as we talked about.

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

struct AAWillReturn
 
   /// Create an abstract attribute view for the position \p IRP.
   static AAWillReturn &createForPosition(const IRPosition &IRP, Attributor &A);
 
   /// Unique ID (due to the unique address)
   static const char ID;
 };
 
+/// An abstract interface to determine reachability of point A to B.
+struct AAReachability : public StateWrapper<BooleanState, AbstractAttribute>,
+                        public IRPosition {
+  AAReachability(const IRPosition &IRP) : IRPosition(IRP) {}
+
+  /// Returns true if 'From' instruction is assumed to reach, 'To' instruction.
+  /// Users should provide two positions they are interested in, and the class
+  /// determines (and caches) reachability.
+  bool isAssumedReachable(const Instruction *From,
+                          const Instruction *To) const {
+    return true;
+  }
+
+  /// Returns true if 'From' instruction is known to reach, 'To' instruction.
+  /// Users should provide two positions they are interested in, and the class
+  /// determines (and caches) reachability.
+  bool isKnownReachable(const Instruction *From, const Instruction *To) const {
+    return true;
+  }
+
+  /// Return an IR position, see struct IRPosition.
+  const IRPosition &getIRPosition() const override { return *this; }
+
+  /// Create an abstract attribute view for the position \p IRP.
+  static AAReachability &createForPosition(const IRPosition &IRP,
+                                           Attributor &A);
+
+  /// Unique ID (due to the unique address)
+  static const char ID;
+};
+
 /// An abstract interface for all noalias attributes.
 struct AANoAlias
     : public IRAttribute<Attribute::NoAlias,
                          StateWrapper<BooleanState, AbstractAttribute>> {
   AANoAlias(const IRPosition &IRP) : IRAttribute(IRP) {}
 
   /// Return true if we assume that the underlying value is alias.
   bool isAssumedNoAlias() const { return getAssumed(); }

llvm/lib/Transforms/IPO/Attributor.cpp

return clampStateAndIndicateChange(
         getState(),
         static_cast<const AAWillReturn::StateType &>(FnAA.getState()));
   }
 
   /// See AbstractAttribute::trackStatistics()
   void trackStatistics() const override { STATS_DECLTRACK_CS_ATTR(willreturn); }
 };
 
+/// -------------------AAReachability Attribute--------------------------
+
+struct AAReachabilityImpl : AAReachability {
+  AAReachabilityImpl(const IRPosition &IRP) : AAReachability(IRP) {}
+
+  const std::string getAsStr() const override {
+    // TODO: Return the number of reachable queries.
+    return "reachable";
+  }
+
+  /// See AbstractAttribute::initialize(...).
+  void initialize(Attributor &A) override {
+    indicatePessimisticFixpoint();
+  }
+
+  /// See AbstractAttribute::updateImpl(...).
+  ChangeStatus updateImpl(Attributor &A) override {
+    return indicatePessimisticFixpoint();
+  }
+};
+
+struct AAReachabilityFunction final : public AAReachabilityImpl {
+  AAReachabilityFunction(const IRPosition &IRP) : AAReachabilityImpl(IRP) {}
+
+  /// See AbstractAttribute::trackStatistics()
+  void trackStatistics() const override { STATS_DECLTRACK_FN_ATTR(reachable); }
+};
+
 /// ------------------------ NoAlias Argument Attribute ------------------------
 
 struct AANoAliasImpl : AANoAlias {
   AANoAliasImpl(const IRPosition &IRP) : AANoAlias(IRP) {}
 
   const std::string getAsStr() const override {
     return getAssumed() ? "noalias" : "may-alias";
   }
 };
if (Arg.getType()->isPointerTy()) {
       // Every argument with pointer type might be marked nonnull.
       getOrCreateAAFor<AANonNull>(ArgPos);
 
       // Every argument with pointer type might be marked noalias.
       getOrCreateAAFor<AANoAlias>(ArgPos);
 
       // Every argument with pointer type might be marked dereferenceable.
       getOrCreateAAFor<AADereferenceable>(ArgPos);
 
       // Every argument with pointer type might be marked align.
       getOrCreateAAFor<AAAlign>(ArgPos);
 
       // Every argument with pointer type might be marked nocapture.
       getOrCreateAAFor<AANoCapture>(ArgPos);
 
       // Every argument with pointer type might be marked
       // "readnone/readonly/writeonly/..."

 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 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 AAMemoryBehavior::ID = 0;

 CREATE_FUNCTION_ABSTRACT_ATTRIBUTE_FOR_POSITION(AANoSync)
 CREATE_FUNCTION_ABSTRACT_ATTRIBUTE_FOR_POSITION(AANoRecurse)
 CREATE_FUNCTION_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAWillReturn)
 CREATE_FUNCTION_ABSTRACT_ATTRIBUTE_FOR_POSITION(AANoReturn)
 CREATE_FUNCTION_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAReturnedValues)
 
 CREATE_VALUE_ABSTRACT_ATTRIBUTE_FOR_POSITION(AANonNull)
 CREATE_VALUE_ABSTRACT_ATTRIBUTE_FOR_POSITION(AANoAlias)
 CREATE_VALUE_ABSTRACT_ATTRIBUTE_FOR_POSITION(AADereferenceable)
 CREATE_VALUE_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAAlign)
 CREATE_VALUE_ABSTRACT_ATTRIBUTE_FOR_POSITION(AANoCapture)
 
 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_NON_RET_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAMemoryBehavior)
 
 #undef CREATE_FUNCTION_ONLY_ABSTRACT_ATTRIBUTE_FOR_POSITION
 #undef CREATE_FUNCTION_ABSTRACT_ATTRIBUTE_FOR_POSITION
 #undef CREATE_NON_RET_ABSTRACT_ATTRIBUTE_FOR_POSITION
 #undef CREATE_VALUE_ABSTRACT_ATTRIBUTE_FOR_POSITION
 #undef CREATE_ALL_ABSTRACT_ATTRIBUTE_FOR_POSITION
 #undef SWITCH_PK_CREATE
 #undef SWITCH_PK_INV
 
 INITIALIZE_PASS_BEGIN(AttributorLegacyPass, "attributor",
                       "Deduce and propagate attributes", false, false)
 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
 INITIALIZE_PASS_END(AttributorLegacyPass, "attributor",
                     "Deduce and propagate attributes", false, false)