[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

5482

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.

5828

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/Bitcode/LLVMBitCodes.h

enum AttributeKindCodes {
   ATTR_KIND_OPT_FOR_FUZZING = 57,
   ATTR_KIND_SHADOWCALLSTACK = 58,
   ATTR_KIND_SPECULATIVE_LOAD_HARDENING = 59,
   ATTR_KIND_IMMARG = 60,
   ATTR_KIND_WILLRETURN = 61,
   ATTR_KIND_NOFREE = 62,
   ATTR_KIND_NOSYNC = 63,
   ATTR_KIND_SANITIZE_MEMTAG = 64,
+  ATTR_KIND_REACHABILITY = 65,
 };
 
 enum ComdatSelectionKindCodes {
   COMDAT_SELECTION_KIND_ANY = 1,
   COMDAT_SELECTION_KIND_EXACT_MATCH = 2,
   COMDAT_SELECTION_KIND_LARGEST = 3,
   COMDAT_SELECTION_KIND_NO_DUPLICATES = 4,
   COMDAT_SELECTION_KIND_SAME_SIZE = 5,

llvm/include/llvm/IR/Attributes.td

 def OptForFuzzing : EnumAttr<"optforfuzzing">;
 
 /// opt_size.
 def OptimizeForSize : EnumAttr<"optsize">;
 
 /// Function must not be optimized.
 def OptimizeNone : EnumAttr<"optnone">;
 
+/// Reachability from point A to B.
+def Reachability: EnumAttr<"reachable">;
+
 /// Function does not access memory.
 def ReadNone : EnumAttr<"readnone">;
 
 /// Function only reads from memory.
 def ReadOnly : EnumAttr<"readonly">;
 
 /// Return value is always equal to this argument.
 def Returned : EnumAttr<"returned">;

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 instruction is assumed reachable.
+  bool isAssumedReachable(const IRPosition &From, const IRPosition &To) const {
+    return true;
+  }
+
+  /// Returns true if instruction is known reachable.
+  bool isKnownReachable(const IRPosition &From, const IRPosition &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/Bitcode/Reader/BitcodeReader.cpp

case Attribute::ArgMemOnly:
     llvm_unreachable("argmemonly attribute not supported in raw format");
     break;
   case Attribute::AllocSize:
     llvm_unreachable("allocsize not supported in raw format");
     break;
   case Attribute::SanitizeMemTag:
     llvm_unreachable("sanitize_memtag attribute not supported in raw format");
     break;
+  case Attribute::Reachability:
+    llvm_unreachable("reachable attribute not supported in raw format");
+    break;
+
   }
   llvm_unreachable("Unsupported attribute type");
 }
 
 static void addRawAttributeValue(AttrBuilder &B, uint64_t Val) {
   if (!Val) return;
 
   for (Attribute::AttrKind I = Attribute::None; I != Attribute::EndAttrKinds;
        I = Attribute::AttrKind(I + 1)) {
     if (I == Attribute::SanitizeMemTag ||
         I == Attribute::Dereferenceable ||
         I == Attribute::DereferenceableOrNull ||
         I == Attribute::ArgMemOnly ||
         I == Attribute::AllocSize ||
-        I == Attribute::NoSync)
+        I == Attribute::NoSync ||
+        I == Attribute::Reachability)
       continue;
     if (uint64_t A = (Val & getRawAttributeMask(I))) {
       if (I == Attribute::Alignment)
         B.addAlignmentAttr(1ULL << ((A >> 16) - 1));
       else if (I == Attribute::StackAlignment)
         B.addStackAlignmentAttr(1ULL << ((A >> 26)-1));
       else
         B.addAttribute(I);
static Attribute::AttrKind getAttrFromCode(uint64_t Code) {
   case bitc::ATTR_KIND_WRITEONLY:
     return Attribute::WriteOnly;
   case bitc::ATTR_KIND_Z_EXT:
     return Attribute::ZExt;
   case bitc::ATTR_KIND_IMMARG:
     return Attribute::ImmArg;
   case bitc::ATTR_KIND_SANITIZE_MEMTAG:
     return Attribute::SanitizeMemTag;
+  case bitc::ATTR_KIND_REACHABILITY:
+    return Attribute::Reachability;
   }
 }
 
 Error BitcodeReader::parseAlignmentValue(uint64_t Exponent,
                                          MaybeAlign &Alignment) {
   // Note: Alignment in bitcode files is incremented by 1, so that zero
   // can be used for default alignment.
   if (Exponent > Value::MaxAlignmentExponent + 1)

llvm/lib/Bitcode/Writer/BitcodeWriter.cpp

static uint64_t getAttrKindEncoding(Attribute::AttrKind Kind) {
   case Attribute::WriteOnly:
     return bitc::ATTR_KIND_WRITEONLY;
   case Attribute::ZExt:
     return bitc::ATTR_KIND_Z_EXT;
   case Attribute::ImmArg:
     return bitc::ATTR_KIND_IMMARG;
   case Attribute::SanitizeMemTag:
     return bitc::ATTR_KIND_SANITIZE_MEMTAG;
+  case Attribute::Reachability:
+    return bitc::ATTR_KIND_REACHABILITY;
   case Attribute::EndAttrKinds:
     llvm_unreachable("Can not encode end-attribute kinds marker.");
   case Attribute::None:
     llvm_unreachable("Can not encode none-attribute.");
   }
 
   llvm_unreachable("Trying to encode unknown attribute");
 }

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: Add 'From' IRPosition and 'To' IRPosition in return.
+    return "reachable";
+  }
+
+  /// See AbstractAttribute::initialize(...).
+  void initialize(Attributor &A) override {
+    getState().indicatePessimisticFixpoint();
+  }
+
+  /// See AbstractAttribute::updateImpl(...).
+  ChangeStatus updateImpl(Attributor &A) override {
+    return getState().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)

llvm/lib/Transforms/Utils/CodeExtractor.cpp

if (Attr.isStringAttribute()) {
       case Attribute::Nest:
       case Attribute::NoAlias:
       case Attribute::NoBuiltin:
       case Attribute::NoCapture:
       case Attribute::NoReturn:
       case Attribute::NoSync:
       case Attribute::None:
       case Attribute::NonNull:
+      case Attribute::Reachability:
       case Attribute::ReadNone:
       case Attribute::ReadOnly:
       case Attribute::Returned:
       case Attribute::ReturnsTwice:
       case Attribute::SExt:
       case Attribute::Speculatable:
       case Attribute::StackAlignment:
       case Attribute::StructRet: