[Attributor] Derive AAFunctionReachability attribute.

[kuter]

Summary

This attribute uses Attributor's internal 'optimistic' call graph
information to answer queries about function call reachability.

Functions can become reachable over time as new call edges are
discovered.

[kuter]

Unit test added.

[kuter]

Added a test case for a unknown callee

[kuter]

clang-format :/

[kuter]

• Implement getAsStr()
• Naming Changes.

[jdoerfert]

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

8248

Move it down to the use. Also rename it to make clear what this is, e.g. NonConstThis.

8253

Eventually we don't want this. We want to check, for example, if an unknown callee can reach Fn at all.
We also want to encode domain knowledge about (some) GPU kernels as we know they can only be called "from the outside".
That is, you cannot reach one kernel from another one.

8272

I don't get why we do this conditionally. If we have an unreachable query already, and then a new one comes in, we still now depend on the state of all AAs we asked in the meantime.

8307

Swap the cases, and use continue to make it easier to read.

8344

Couldn't we add dependences here, maybe keep track of all the AAs above and then add dependences in the false case. removes complexity I think

[kuter]

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

8272

We should already have deps if the UnreachableQueries is not empty. I might remove this since this is a very tiny optimization.

[kuter]

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

8344

This is just for checking a single function. In the updateImpl method above we have a for loop that goes over unreachable queries.
moving the call to recieveUpdates here would cause us to call it multiple times which not needed.

[kuter]

• Simplify control flow
• Rename const_cast

[jdoerfert]

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

8344

The concept of "receiveUpdates" seems to be some optimization but I fear it will simply lead to errors.

Let's talk this through:
Adding a dependence is pretty cheap.
We should add dependences as we use AAs not at some point later somehow.
In this function we know what AAs we used to come up with a optimistic result, if any.
I fail to see what would be worse if we directly add dependences to those AAs before we return false, it certainly will make this easier to read as multiple implicit dependences will go away.

(FWIW, if you argue it's an optimization you might have to show how much it saves actually. I expect the result here to be well withing the noise so it's not worth making the code harder to read.)

[kuter]

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

8344

I agree that moving the contentes of receiveUpdates here should be ok since adding deps is fast.
I fear that things can get really slow if we are not careful about our dependencies.
Since we are doing this in a recursive way we are actually creating a lot of AAFunctionReachability attributes.

if all functions that where queried where reachable, we do not need any dependencies since functions can't become unreachable after we find that they are reachable.

[kuter]

remove the recieveUpdates

[jdoerfert]

LGTM

[jdoerfert]

remove the WIP tag before committing

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

struct DOTGraphTraits<AttributorCallGraph *> : public DefaultDOTGraphTraits {
 
   static bool isNodeHidden(const AACallGraphNode *Node,
                            const AttributorCallGraph *Graph) {
     // Hide the synth root.
     return static_cast<const AACallGraphNode *>(Graph) == Node;
   }
 };
 
+/// An abstract Attribute for computing reachability between functions.
+struct AAFunctionReachability
+    : public StateWrapper<BooleanState, AbstractAttribute> {
+  using Base = StateWrapper<BooleanState, AbstractAttribute>;
+
+  AAFunctionReachability(const IRPosition &IRP, Attributor &A) : Base(IRP) {}
+
+  /// If the function represented by this possition can reach \p Fn.
+  virtual bool canReach(Attributor &A, Function *Fn) const = 0;
+
+  /// Create an abstract attribute view for the position \p IRP.
+  static AAFunctionReachability &createForPosition(const IRPosition &IRP,
+                                                   Attributor &A);
+
+  /// See AbstractAttribute::getName()
+  const std::string getName() const override { return "AAFuncitonReacability"; }
+
+  /// See AbstractAttribute::getIdAddr()
+  const char *getIdAddr() const override { return &ID; }
+
+  /// This function should return true if the type of the \p AA is AACallEdges.
+  static bool classof(const AbstractAttribute *AA) {
+    return (AA->getIdAddr() == &ID);
+  }
+
+  /// Unique ID (due to the unique address)
+  static const char ID;
+
+private:
+  /// Can this function reach a call with unknown calee.
+  virtual bool canReachUnknownCallee() const = 0;
+};
+
 /// 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_ATTRIBUTOR_H

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

 PIPE_OPERATOR(AAMemoryBehavior)
 PIPE_OPERATOR(AAMemoryLocation)
 PIPE_OPERATOR(AAValueConstantRange)
 PIPE_OPERATOR(AAPrivatizablePtr)
 PIPE_OPERATOR(AAUndefinedBehavior)
 PIPE_OPERATOR(AAPotentialValues)
 PIPE_OPERATOR(AANoUndef)
 PIPE_OPERATOR(AACallEdges)
+PIPE_OPERATOR(AAFunctionReachability)
 
 #undef PIPE_OPERATOR
 } // namespace llvm
 
 namespace {
 
 /// Get pointer operand of memory accessing instruction. If \p I is
 /// not a memory accessing instruction, return nullptr. If \p AllowVolatile,
struct AACallEdgesFunction : public AACallEdges {
 
   /// Optimistic set of functions that might be called by this function.
   SetVector<Function *> CalledFunctions;
 
   /// Does this function have a call to a function that we don't know about.
   bool HasUnknownCallee;
 };
 
+struct AAFunctionReachabilityFunction : public AAFunctionReachability {
+  AAFunctionReachabilityFunction(const IRPosition &IRP, Attributor &A)
+      : AAFunctionReachability(IRP, A) {}
+
+  bool canReach(Attributor &A, Function *Fn) const override {
+    // Attributor returns attributes as const, so this function has to be
+    // const for users of this attribute to use it without having to do
+    // a const_cast.
+    // This is a hack for us to be able to cache queries.
+    auto *This = const_cast<AAFunctionReachabilityFunction *>(this);
+
+    // Assume that we can reach any function if we can reach a call with
+    // unknown callee.
+    if (CanReachUnknownCallee)
+      return true;
+
+    if (ReachableQueries.count(Fn))
+      return true;
+
+    if (UnreachableQueries.count(Fn))
+      return false;
+
+    const AACallEdges &AAEdges =
+        A.getAAFor<AACallEdges>(*this, getIRPosition(), DepClassTy::REQUIRED);
+
+    const SetVector<Function *> &Edges = AAEdges.getOptimisticEdges();
+    bool Result = checkIfReachable(A, Edges, Fn);
+
+    if (Result) {
+      This->ReachableQueries.insert(Fn);
+    } else {
+      // If a queried function was unreachable, we have to add dependencies.
+      if (UnreachableQueries.empty())
+        recieveUpdates(A, Edges);
+
+      This->UnreachableQueries.insert(Fn);
+    }
+
+    return Result;
+  }
+
+  /// See AbstractAttribute::updateImpl(...).
+  ChangeStatus updateImpl(Attributor &A) override {
+    if (CanReachUnknownCallee)
+      return ChangeStatus::UNCHANGED;
+
+    const AACallEdges &AAEdges =
+        A.getAAFor<AACallEdges>(*this, getIRPosition(), DepClassTy::REQUIRED);
+    const SetVector<Function *> &Edges = AAEdges.getOptimisticEdges();
+    ChangeStatus Change = ChangeStatus::UNCHANGED;
+
+    if (AAEdges.hasUnknownCallee()) {
+      bool OldCanReachUnknown = CanReachUnknownCallee;
+      CanReachUnknownCallee = true;
+      return OldCanReachUnknown ? ChangeStatus::UNCHANGED
+                                : ChangeStatus::CHANGED;
+    }
+
+    // Check if any of the unreachable functions become reachable.
+    for (auto Current = UnreachableQueries.begin();
+         Current != UnreachableQueries.end();) {
+      if (checkIfReachable(A, Edges, *Current)) {
+        ReachableQueries.insert(*Current);
+        UnreachableQueries.erase(*Current++);
+
+        Change = ChangeStatus::CHANGED;
+      } else {
+        Current++;
+      }
+    }
+
+    // If there are unreachable functions we should set a dependencies to all
+    // called functions.
+    if (!UnreachableQueries.empty())
+      recieveUpdates(A, Edges);
+
+    return Change;
+  }
+
+  const std::string getAsStr() const override {
+    size_t QueryCount = ReachableQueries.size() + UnreachableQueries.size();
+
+    return "FunctionReachability [" + std::to_string(ReachableQueries.size()) +
+           "," + std::to_string(QueryCount) + "]";
+  }
+
+  void trackStatistics() const override {}
+
+private:
+  bool canReachUnknownCallee() const override { return CanReachUnknownCallee; }
+
+  bool checkIfReachable(Attributor &A, const SetVector<Function *> &Edges,
+                        Function *Fn) const {
+    if (Edges.count(Fn))
+      return true;
+
+    for (Function *Edge : Edges) {
+      // We don't need a dependency if the result is reachable.
+      const AAFunctionReachability &EdgeReachability =
+          A.getAAFor<AAFunctionReachability>(*this, IRPosition::function(*Edge),
+                                             DepClassTy::NONE);
+
+      if (EdgeReachability.canReach(A, Fn))
+        return true;
+    }
+    return false;
+  }
+
+  /// This function is for adding dependencies to call edge reachability
+  /// attributes when needed.
+  void recieveUpdates(Attributor &A, const SetVector<Function *> &Edges) const {
+    for (Function *Fn : Edges)
+      A.getAAFor<AAFunctionReachability>(*this, IRPosition::function(*Fn),
+                                         DepClassTy::REQUIRED);
+  }
+
+  /// Set of functions that we know for sure is reachable.
+  SmallPtrSet<Function *, 8> ReachableQueries;
+
+  /// Set of functions that are unreachable, but might become reachable.
+  SmallPtrSet<Function *, 8> UnreachableQueries;
+
+  /// If we can reach a function with a call to a unknown function we assume
+  /// that we can reach any function.
+  bool CanReachUnknownCallee = false;
+};
+
 } // namespace
 
 AACallGraphNode *AACallEdgeIterator::operator*() const {
   return static_cast<AACallGraphNode *>(const_cast<AACallEdges *>(
       &A.getOrCreateAAFor<AACallEdges>(IRPosition::function(**I))));
 }
 
 void AttributorCallGraph::print() {

 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;
 const char AANoUndef::ID = 0;
 const char AACallEdges::ID = 0;
+const char AAFunctionReachability::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_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)
 CREATE_FUNCTION_ONLY_ABSTRACT_ATTRIBUTE_FOR_POSITION(AACallEdges)
+CREATE_FUNCTION_ONLY_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAFunctionReachability)
 
 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

llvm/unittests/Transforms/IPO/AttributorTest.cpp

TEST_F(AttributorTestBase, TestCast) {
 
   const auto *SFail = dyn_cast<AAAlign>(AA);
   const auto *SSucc = dyn_cast<AAIsDead>(AA);
 
   ASSERT_EQ(SFail, nullptr);
   ASSERT_TRUE(SSucc);
 }
 
+TEST_F(AttributorTestBase, AAReachabilityTest) {
+  const char *ModuleString = R"(
+    declare void @func4()
+    declare void @func3()
+
+    define void @func2() {
+    entry:
+      call void @func3()
+      ret void
+    }
+
+    define void @func1() {
+    entry:
+      call void @func2()
+      ret void
+    }
+
+    define void @func5(void ()* %unknown) {
+    entry:
+      call void %unknown()
+      ret void
+    }
+
+    define void @func6() {
+    entry:
+      call void @func5(void ()* @func3)
+      ret void
+    }
+  )";
+
+  Module &M = parseModule(ModuleString);
+
+  SetVector<Function *> Functions;
+  AnalysisGetter AG;
+  for (Function &F : M)
+    Functions.insert(&F);
+
+  CallGraphUpdater CGUpdater;
+  BumpPtrAllocator Allocator;
+  InformationCache InfoCache(M, AG, Allocator, nullptr);
+  Attributor A(Functions, InfoCache, CGUpdater);
+
+  Function *F1 = M.getFunction("func1");
+  Function *F3 = M.getFunction("func3");
+  Function *F4 = M.getFunction("func4");
+  Function *F6 = M.getFunction("func6");
+
+  const AAFunctionReachability &F1AA =
+      A.getOrCreateAAFor<AAFunctionReachability>(IRPosition::function(*F1));
+
+  const AAFunctionReachability &F6AA =
+      A.getOrCreateAAFor<AAFunctionReachability>(IRPosition::function(*F6));
+
+  F1AA.canReach(A, F3);
+  F1AA.canReach(A, F4);
+  F6AA.canReach(A, F4);
+
+  A.run();
+
+  ASSERT_TRUE(F1AA.canReach(A, F3));
+  ASSERT_FALSE(F1AA.canReach(A, F4));
+
+  // Assumed to be reacahable, since F6 can reach a function with
+  // a unknown callee.
+  ASSERT_TRUE(F6AA.canReach(A, F4));
+}
+
 } // namespace llvm