[Attributor] AAFunctionReachability, Instruction reachability.

[kuter]

Summary

This patch implement instruction reachability for AAFunctionReachability
attribute. It is used to tell if a certain instruction can reach a function
transitively.

[kuter]

Don't ignore the return value of checkForAllCallLikeInstructions

[jdoerfert]

Add doxygen docu to the functions to describe what they do.

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

9684

Don't accumulate pointers to containers but content instead.

9780–9781

|=, also elsewhere
no braces.

[jdoerfert]

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

4467

Spell inst out in the function name, pass function as reference, (or is a nullptr ok?)

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

9727

I don't get the backwards stuff.

[kuter]

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

9684

I tried using references here. But I couldn't pass SmallVector<const AACallEdges &> as a ArrayRef.

9780–9781

Oh great. I am happy to hear that someone finally added that operator.

[jdoerfert]

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

9700

I think this is a problem if you have invokes.
Dies the instCanReach include the instruction or not? If it's the latter we can just pass the call site.

9716

don't ignore the return value

9724

no braces.

llvm/unittests/Transforms/IPO/AttributorTest.cpp

207

can we have a negative instcanreach test?

[kuter]

Use the new |= operator for change tracking.

[kuter]

• Explicitly handle InvokeInst.
• Add a option to note use backwards reachability.
• Don't use backwards reachability for transative queries (fixes the fixme)
• Address misc review.

[jdoerfert]

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

9614

Is this the right way? I would have thought we ignore CB if CBInst is not reachable from Inst, not the other way around. We need a test I suppose.

9640–9641

At least add a TODO. To fix it proper you can look at the two successors blocks and the first non-debug instruction in them.

9648–9650

Why no range loop?

[kuter]

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

9648–9650

markReachable call below erases Fn from the set we are iterating right now.
I increment the iterator before processing Fn in case Fn gets removed from the Unreachable set.

It would be invalid to increment the iterator if Fn was already deleted right ? I think we have to do that before.

[jdoerfert]

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

9648–9650

I see. We have a special iterator + range loop for that, maybe you want to look at make_early_inc_range and it's uses.

[kuter]

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

9614

We are doing an early return if the CB is not assumed reachable. If not we add it into the Result Vector. We later use the result of this function for QueryResolver::update or QueryResolver::isReachable.

So the return true here doesn't mean anything.

[jdoerfert]

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

9614

I was not clear. My concern is that we check if CBInst may reach Inst while we want to know if Inst may reach CBInst, no?
So if (!Reachability.isAssumedReachable(A, Inst, CBInst)) instead?

[kuter]

Address review.

[jdoerfert]

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

9656–9661

9735

Reachable is not updated if CanReachUnknownCallee is set true. We also never check for a cached value here.

9752

One of these caused a copy and only the copy QuerySet got updated causing it never to find a fixpoint.

9769

One of these caused a copy and only the copy QuerySet got updated causing it never to find a fixpoint.

9779

One of these caused a copy and only the copy QuerySet got updated causing it never to find a fixpoint.

[kuter]

Address review.

[jdoerfert]

Two comments below, otherwise LG.

As we add users we will need to extend/adjust some thing but conceptually this should be OK.

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

9617

Replace static cast with cast<CallBase> and it is not Inst but CBInst you want to cast here.

9808

Documentation.

[jdoerfert]

Testing it more I see this crashing and the backwards stuff not working properly. Probably easiest for me to put a fix up here.

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

 /// 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;
+  virtual bool canReach(Attributor &A, Function &Fn) const = 0;
 
   /// Can \p CB reach \p Fn
-  virtual bool canReach(Attributor &A, CallBase &CB, Function *Fn) const = 0;
+  virtual bool canReach(Attributor &A, CallBase &CB, Function &Fn) const = 0;
+
+  /// Can  \p Inst reach \p Fn
+  virtual bool instructionCanReach(Attributor &A, Instruction &Inst,
+                                   Function &Fn,
+                                   bool UseBackwards = true) 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;
 };
 
 /// An abstract interface for struct information.
 struct AAPointerInfo : public AbstractAttribute {
   AAPointerInfo(const IRPosition &IRP) : AbstractAttribute(IRP) {}

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

 struct AAFunctionReachabilityFunction : public AAFunctionReachability {
 private:
   struct QuerySet {
     void markReachable(Function *Fn) {
       Reachable.insert(Fn);
       Unreachable.erase(Fn);
     }
 
+    /// If there is no information about the function None is returned.
+    Optional<bool> isCachedReachable(Function &Fn) {
+      // Assume that we can reach the function.
+      // TODO: Be more specific with the unknown callee.
+      if (CanReachUnknownCallee)
+        return true;
+
+      if (Reachable.count(&Fn))
+        return true;
+
+      if (Unreachable.count(&Fn))
+        return false;
+
+      return llvm::None;
+    }
+
+    /// Set of functions that we know for sure is reachable.
+    DenseSet<Function *> Reachable;
+
+    /// Set of functions that are unreachable, but might become reachable.
+    DenseSet<Function *> Unreachable;
+
+    /// If we can reach a function with a call to a unknown function we assume
+    /// that we can reach any function.
+    bool CanReachUnknownCallee = false;
+  };
+
+  struct QueryResolver : public QuerySet {
     ChangeStatus update(Attributor &A, const AAFunctionReachability &AA,
                         ArrayRef<const AACallEdges *> AAEdgesList) {
       ChangeStatus Change = ChangeStatus::UNCHANGED;
 
       for (auto *AAEdges : AAEdgesList) {
         if (AAEdges->hasUnknownCallee()) {
           if (!CanReachUnknownCallee)
             Change = ChangeStatus::CHANGED;
           CanReachUnknownCallee = true;
           return Change;
         }
       }
 
       for (Function *Fn : make_early_inc_range(Unreachable)) {
         if (checkIfReachable(A, AA, AAEdgesList, Fn)) {
           Change = ChangeStatus::CHANGED;
           markReachable(Fn);
         }
       }
       return Change;
     }
 
     bool isReachable(Attributor &A, const AAFunctionReachability &AA,
                      ArrayRef<const AACallEdges *> AAEdgesList, Function *Fn) {
-      // Assume that we can reach the function.
-      // TODO: Be more specific with the unknown callee.
-      if (CanReachUnknownCallee)
-        return true;
-
-      if (Reachable.count(Fn))
-        return true;
-
-      if (Unreachable.count(Fn))
-        return false;
+      Optional<bool> Cached = isCachedReachable(*Fn);
+      if (Cached.hasValue())
+        return Cached.getValue();
 
       // We need to assume that this function can't reach Fn to prevent
       // an infinite loop if this function is recursive.
       Unreachable.insert(Fn);
 
       bool Result = checkIfReachable(A, AA, AAEdgesList, Fn);
       if (Result)
         markReachable(Fn);
bool checkIfReachable(Attributor &A, const AAFunctionReachability &AA,
 
         for (Function *Edge : Edges) {
           // We don't need a dependency if the result is reachable.
           const AAFunctionReachability &EdgeReachability =
               A.getAAFor<AAFunctionReachability>(
                   AA, IRPosition::function(*Edge), DepClassTy::NONE);
           Deps.push_back(&EdgeReachability);
 
-          if (EdgeReachability.canReach(A, Fn))
+          if (EdgeReachability.canReach(A, *Fn))
             return true;
         }
       }
 
       // The result is false for now, set dependencies and leave.
       for (auto Dep : Deps)
         A.recordDependence(AA, *Dep, DepClassTy::REQUIRED);
 
       return false;
     }
+  };
 
-    /// Set of functions that we know for sure is reachable.
-    DenseSet<Function *> Reachable;
+  /// Get call edges that can be reached by this instruction.
+  bool getReachableCallEdges(Attributor &A, const AAReachability &Reachability,
+                             Instruction &Inst,
+                             SmallVector<const AACallEdges *> &Result) const {
+    // Determine call like instructions that we can reach from the inst.
+    auto CheckCallBase = [&](Instruction &CBInst) {
+      if (!Reachability.isAssumedReachable(A, Inst, CBInst))
+        return true;
 
-    /// Set of functions that are unreachable, but might become reachable.
-    DenseSet<Function *> Unreachable;
+      CallBase &CB = static_cast<CallBase &>(Inst);
+      const AACallEdges &AAEdges = A.getAAFor<AACallEdges>(
+          *this, IRPosition::callsite_function(CB), DepClassTy::REQUIRED);
 
-    /// If we can reach a function with a call to a unknown function we assume
-    /// that we can reach any function.
-    bool CanReachUnknownCallee = false;
+      Result.push_back(&AAEdges);
+      return true;
+    };
+
+    bool UsedAssumedInformation = false;
+    return A.checkForAllCallLikeInstructions(CheckCallBase, *this,
+                                             UsedAssumedInformation);
+  }
+
+  ChangeStatus checkReachableBackwards(Attributor &A, QuerySet &Set) {
+    ChangeStatus Change = ChangeStatus::UNCHANGED;
+
+    // For all remaining instruction queries, check
+    // callers. A call inside that function might satisfy the query.
+    auto CheckCallSite = [&](AbstractCallSite CallSite) {
+      CallBase *CB = CallSite.getInstruction();
+      if (!CB)
+        return false;
+
+      if (isa<InvokeInst>(CB))
+        return false;
+
+      Instruction *Inst = CB->getNextNonDebugInstruction();
+      const AAFunctionReachability &AA = A.getAAFor<AAFunctionReachability>(
+          *this, IRPosition::function(*Inst->getFunction()),
+          DepClassTy::REQUIRED);
+      for (Function *Fn : make_early_inc_range(Set.Unreachable)) {
+        if (AA.instructionCanReach(A, *Inst, *Fn, /* UseBackwards */ false)) {
+          Set.markReachable(Fn);
+          Change = ChangeStatus::CHANGED;
+        }
+      }
+      return true;
     };
 
+    bool NoUnknownCall = true;
+    if (A.checkForAllCallSites(CheckCallSite, *this, true, NoUnknownCall))
+      return Change;
+
+    // If we don't know all callsites we have to assume that we can reach fn.
+    for (auto &QSet : InstQueriesBackwards) {
+      if (!QSet.second.CanReachUnknownCallee)
+        Change = ChangeStatus::CHANGED;
+      QSet.second.CanReachUnknownCallee = true;
+    }
+
+    return Change;
+  }
+
 public:
   AAFunctionReachabilityFunction(const IRPosition &IRP, Attributor &A)
       : AAFunctionReachability(IRP, A) {}
 
-  bool canReach(Attributor &A, Function *Fn) const override {
+  bool canReach(Attributor &A, Function &Fn) const override {
     const AACallEdges &AAEdges =
         A.getAAFor<AACallEdges>(*this, getIRPosition(), DepClassTy::REQUIRED);
 
     // 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 *NonConstThis = const_cast<AAFunctionReachabilityFunction *>(this);
     bool Result =
-        NonConstThis->WholeFunction.isReachable(A, *this, {&AAEdges}, Fn);
+        NonConstThis->WholeFunction.isReachable(A, *this, {&AAEdges}, &Fn);
 
     return Result;
   }
 
   /// Can \p CB reach \p Fn
-  bool canReach(Attributor &A, CallBase &CB, Function *Fn) const override {
+  bool canReach(Attributor &A, CallBase &CB, Function &Fn) const override {
     const AACallEdges &AAEdges = A.getAAFor<AACallEdges>(
         *this, IRPosition::callsite_function(CB), DepClassTy::REQUIRED);
 
     // 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 *NonConstThis = const_cast<AAFunctionReachabilityFunction *>(this);
-    QuerySet &CBQuery = NonConstThis->CBQueries[&CB];
+    QueryResolver &CBQuery = NonConstThis->CBQueries[&CB];
 
-    bool Result = CBQuery.isReachable(A, *this, {&AAEdges}, Fn);
+    bool Result = CBQuery.isReachable(A, *this, {&AAEdges}, &Fn);
 
     return Result;
   }
 
+  bool instructionCanReach(Attributor &A, Instruction &Inst, Function &Fn,
+                           bool UseBackwards) const override {
+    const auto &Reachability = &A.getAAFor<AAReachability>(
+        *this, IRPosition::function(*getAssociatedFunction()),
+        DepClassTy::REQUIRED);
+
+    SmallVector<const AACallEdges *> CallEdges;
+    bool AllKnown = getReachableCallEdges(A, *Reachability, Inst, CallEdges);
+    // 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 *NonConstThis = const_cast<AAFunctionReachabilityFunction *>(this);
+    QueryResolver &InstQSet = NonConstThis->InstQueries[&Inst];
+    if (!AllKnown)
+      InstQSet.CanReachUnknownCallee = true;
+
+    bool ForwardsResult = InstQSet.isReachable(A, *this, CallEdges, &Fn);
+    if (ForwardsResult)
+      return true;
+    // We are done.
+    if (!UseBackwards)
+      return false;
+
+    QuerySet &InstBackwardsQSet = NonConstThis->InstQueriesBackwards[&Inst];
+
+    Optional<bool> BackwardsCached = InstBackwardsQSet.isCachedReachable(Fn);
+    if (BackwardsCached.hasValue())
+      return BackwardsCached.getValue();
+
+    // Assume unreachable, to prevent problems.
+    InstBackwardsQSet.Unreachable.insert(&Fn);
+
+    // Check backwards reachability.
+    NonConstThis->checkReachableBackwards(A, InstBackwardsQSet);
+    return InstBackwardsQSet.isCachedReachable(Fn).getValue();
+  }
+
   /// See AbstractAttribute::updateImpl(...).
   ChangeStatus updateImpl(Attributor &A) override {
     const AACallEdges &AAEdges =
         A.getAAFor<AACallEdges>(*this, getIRPosition(), DepClassTy::REQUIRED);
     ChangeStatus Change = ChangeStatus::UNCHANGED;
 
     Change |= WholeFunction.update(A, *this, {&AAEdges});
 
-    for (auto CBPair : CBQueries) {
+    for (auto &CBPair : CBQueries) {
       const AACallEdges &AAEdges = A.getAAFor<AACallEdges>(
           *this, IRPosition::callsite_function(*CBPair.first),
           DepClassTy::REQUIRED);
 
       Change |= CBPair.second.update(A, *this, {&AAEdges});
     }
 
+    // Update the Instruction queries.
+    const AAReachability *Reachability;
+    if (!InstQueries.empty()) {
+      Reachability = &A.getAAFor<AAReachability>(
+          *this, IRPosition::function(*getAssociatedFunction()),
+          DepClassTy::REQUIRED);
+    }
+
+    // Check for local callbases first.
+    for (auto &InstPair : InstQueries) {
+      SmallVector<const AACallEdges *> CallEdges;
+      bool AllKnown =
+          getReachableCallEdges(A, *Reachability, *InstPair.first, CallEdges);
+      // Update will return change if we this effects any queries.
+      if (!AllKnown)
+        InstPair.second.CanReachUnknownCallee = true;
+      Change |= InstPair.second.update(A, *this, CallEdges);
+    }
+
+    // Update backwards queries.
+    for (auto &QueryPair : InstQueriesBackwards)
+      Change |= checkReachableBackwards(A, QueryPair.second);
+
     return Change;
   }
 
   const std::string getAsStr() const override {
     size_t QueryCount =
         WholeFunction.Reachable.size() + WholeFunction.Unreachable.size();
 
     return "FunctionReachability [" +
            std::to_string(WholeFunction.Reachable.size()) + "," +
            std::to_string(QueryCount) + "]";
   }
 
   void trackStatistics() const override {}
 private:
   bool canReachUnknownCallee() const override {
     return WholeFunction.CanReachUnknownCallee;
   }
 
   /// Used to answer if a the whole function can reacha a specific function.
-  QuerySet WholeFunction;
+  QueryResolver WholeFunction;
 
   /// Used to answer if a call base inside this function can reach a specific
   /// function.
-  DenseMap<CallBase *, QuerySet> CBQueries;
+  DenseMap<CallBase *, QueryResolver> CBQueries;
+
+  DenseMap<Instruction *, QueryResolver> InstQueries;
+
+  // This is for instruction queries than scan backwards.
+  DenseMap<Instruction *, QuerySet> InstQueriesBackwards;
 };
 
 } // namespace
 
 AACallGraphNode *AACallEdgeIterator::operator*() const {
   return static_cast<AACallGraphNode *>(const_cast<AACallEdges *>(
       &A.getOrCreateAAFor<AACallEdges>(IRPosition::function(**I))));
 }

llvm/unittests/Transforms/IPO/AttributorTest.cpp

TEST_F(AttributorTestBase, TestCast) {
   const auto *SSucc = dyn_cast<AAIsDead>(AA);
 
   ASSERT_EQ(SFail, nullptr);
   ASSERT_TRUE(SSucc);
 }
 
 TEST_F(AttributorTestBase, AAReachabilityTest) {
   const char *ModuleString = R"(
-    @x = global i32 0
-    define void @func4() {
+    @x = external global i32
+    define internal void @func4() {
       store i32 0, i32* @x
       ret void
     }
 
-    define void @func3() {
+    define internal void @func3() {
       store i32 0, i32* @x
       ret void
     }
 
-    define void @func2() {
+    define internal void @func8() {
+      store i32 0, i32* @x
+      ret void
+    }
+
+    define internal void @func2() {
     entry:
       call void @func3()
       ret void
     }
 
-    define void @func1() {
+    define internal void @func1() {
     entry:
       call void @func2()
       ret void
     }
 
-    define void @func5(void ()* %unknown) {
+    define internal void @func5(void ()* %unknown) {
     entry:
       call void %unknown()
       ret void
     }
 
-    define void @func6() {
+    define internal void @func6() {
     entry:
       call void @func5(void ()* @func3)
       ret void
     }
 
-    define void @func7() {
+    define internal void @func7() {
     entry:
       call void @func2()
       call void @func4()
       ret void
     }
+
+    define internal void @func9() {
+    entry:
+      call void @func2()
+      call void @func8()
+      ret void
+    }
+
+    define internal void @func10() {
+    entry:
+      call void @func9()
+      call void @func4()
+      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);
+  Attributor A(Functions, InfoCache, CGUpdater, /* Allowed */ nullptr,
+               /*DeleteFns*/ false);
 
-  Function *F1 = M.getFunction("func1");
-  Function *F3 = M.getFunction("func3");
-  Function *F4 = M.getFunction("func4");
-  Function *F6 = M.getFunction("func6");
-  Function *F7 = M.getFunction("func7");
+  Function &F1 = *M.getFunction("func1");
+  Function &F3 = *M.getFunction("func3");
+  Function &F4 = *M.getFunction("func4");
+  Function &F6 = *M.getFunction("func6");
+  Function &F7 = *M.getFunction("func7");
+  Function &F9 = *M.getFunction("func9");
 
   // call void @func2()
-  CallBase &F7FirstCB =
-      *static_cast<CallBase *>(F7->getEntryBlock().getFirstNonPHI());
+  CallBase &F7FirstCB = static_cast<CallBase &>(*F7.getEntryBlock().begin());
+  // call void @func2()
+  Instruction &F9FirstInst = *F9.getEntryBlock().begin();
+  // call void @func8
+  Instruction &F9SecondInst = *++(F9.getEntryBlock().begin());
 
   const AAFunctionReachability &F1AA =
-      A.getOrCreateAAFor<AAFunctionReachability>(IRPosition::function(*F1));
+      A.getOrCreateAAFor<AAFunctionReachability>(IRPosition::function(F1));
 
   const AAFunctionReachability &F6AA =
-      A.getOrCreateAAFor<AAFunctionReachability>(IRPosition::function(*F6));
+      A.getOrCreateAAFor<AAFunctionReachability>(IRPosition::function(F6));
 
   const AAFunctionReachability &F7AA =
-      A.getOrCreateAAFor<AAFunctionReachability>(IRPosition::function(*F7));
+      A.getOrCreateAAFor<AAFunctionReachability>(IRPosition::function(F7));
+
+  const AAFunctionReachability &F9AA =
+      A.getOrCreateAAFor<AAFunctionReachability>(IRPosition::function(F9));
 
   F1AA.canReach(A, F3);
   F1AA.canReach(A, F4);
   F6AA.canReach(A, F4);
   F7AA.canReach(A, F7FirstCB, F3);
   F7AA.canReach(A, F7FirstCB, F4);
+  F9AA.instructionCanReach(A, F9FirstInst, F3);
+  F9AA.instructionCanReach(A, F9SecondInst, F3, false);
+  F9AA.instructionCanReach(A, F9FirstInst, F4);
 
   A.run();
 
   ASSERT_TRUE(F1AA.canReach(A, F3));
   ASSERT_FALSE(F1AA.canReach(A, F4));
 
   ASSERT_TRUE(F7AA.canReach(A, F7FirstCB, F3));
   ASSERT_FALSE(F7AA.canReach(A, F7FirstCB, F4));
 
   // Assumed to be reacahable, since F6 can reach a function with
   // a unknown callee.
   ASSERT_TRUE(F6AA.canReach(A, F4));
+
+  // The second instruction of F9 can't reach the first call.
+  ASSERT_FALSE(F9AA.instructionCanReach(A, F9SecondInst, F3, false));
+  ASSERT_FALSE(F9AA.instructionCanReach(A, F9SecondInst, F3, true));
+
+  // The first instruction of F9 can reach the first call.
+  ASSERT_TRUE(F9AA.instructionCanReach(A, F9FirstInst, F3));
+  // Because func10 calls the func4 after the call to func9 it is reachable.
+  ASSERT_TRUE(F9AA.instructionCanReach(A, F9FirstInst, F4));
 }
 
 } // namespace llvm