[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

9739

Don't accumulate pointers to containers but content instead.

9837–9838

|=, also elsewhere
no braces.

[jdoerfert]

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

4632

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

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

9782

I don't get the backwards stuff.

[kuter]

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

9739

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

9837–9838

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

[jdoerfert]

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

9755

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.

9771

don't ignore the return value

9779

no braces.

llvm/unittests/Transforms/IPO/AttributorTest.cpp

209

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

9669

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.

9695–9696

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.

9703–9705

Why no range loop?

[kuter]

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

9703–9705

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

9703–9705

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

9669

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

9669

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

9711–9716

9791

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

9809

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

9826

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

9836

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

9672–9674

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

9866

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, const 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,
+                        const Function &Fn) const = 0;
+
+  /// Can  \p Inst reach \p Fn
+  virtual bool instructionCanReach(Attributor &A, const Instruction &Inst,
+                                   const 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 "AAFunctionReachability"; }
+  const std::string getName() const override {
+    return "AAFunctionReachability";
+  }
 
   /// 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);
   }

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

assert(this->getIRPosition().getPositionKind() ==
            "positions!");
     auto &S = this->getState();
 
     const Function *AssociatedFunction =
         this->getIRPosition().getAssociatedFunction();
     if (!AssociatedFunction)
       return S.indicatePessimisticFixpoint();
 
-    CallBase &CBContext = static_cast<CallBase &>(this->getAnchorValue());
+    CallBase &CBContext = cast<CallBase>(this->getAnchorValue());
     if (IntroduceCallBaseContext)
       LLVM_DEBUG(dbgs() << "[Attributor] Introducing call base context:"
                         << CBContext << "\n");
 
     IRPosition FnPos = IRPosition::returned(
         *AssociatedFunction, IntroduceCallBaseContext ? &CBContext : nullptr);
     const AAType &AA = A.getAAFor<AAType>(*this, FnPos, DepClassTy::REQUIRED);
     return clampStateAndIndicateChange(S, AA.getState());
if (A.checkForAllCallSites(CallSitePred, *this, true, AllCallSitesKnown)) {
       if (AllCallSitesKnown)
         indicateOptimisticFixpoint();
       return ChangeStatus::UNCHANGED;
     }
 
     const AAFunctionReachability &EdgeReachability =
         A.getAAFor<AAFunctionReachability>(*this, getIRPosition(),
                                            DepClassTy::REQUIRED);
-    if (EdgeReachability.canReach(A, getAnchorScope()))
+    if (EdgeReachability.canReach(A, *getAnchorScope()))
       return indicatePessimisticFixpoint();
     return ChangeStatus::UNCHANGED;
   }
 
   void trackStatistics() const override { STATS_DECLTRACK_FN_ATTR(norecurse) }
 };
 
 /// NoRecurse attribute deduction for a call sites.
auto ProcessCalledOperand = [&](Value *V) {
                                        DummyValue, VisitValue, nullptr,
                                        false)) {
         // If we haven't gone through all values, assume that there are unknown
         // callees.
         setHasUnknownCallee(true, Change);
       }
     };
 
-    CallBase *CB = static_cast<CallBase *>(getCtxI());
+    CallBase *CB = cast<CallBase>(getCtxI());
 
     if (CB->isInlineAsm()) {
       setHasUnknownCallee(false, Change);
       return Change;
     }
 
     // Process callee metadata if available.
     if (auto *MD = getCtxI()->getMetadata(LLVMContext::MD_callees)) {
struct AACallEdgesFunction : public AACallEdgesImpl {
   AACallEdgesFunction(const IRPosition &IRP, Attributor &A)
       : AACallEdgesImpl(IRP, A) {}
 
   /// See AbstractAttribute::updateImpl(...).
   ChangeStatus updateImpl(Attributor &A) override {
     ChangeStatus Change = ChangeStatus::UNCHANGED;
 
     auto ProcessCallInst = [&](Instruction &Inst) {
-      CallBase &CB = static_cast<CallBase &>(Inst);
+      CallBase &CB = cast<CallBase>(Inst);
 
       auto &CBEdges = A.getAAFor<AACallEdges>(
           *this, IRPosition::callsite_function(CB), DepClassTy::REQUIRED);
       if (CBEdges.hasNonAsmUnknownCallee())
         setHasUnknownCallee(true, Change);
       if (CBEdges.hasUnknownCallee())
         setHasUnknownCallee(false, Change);
 
ChangeStatus updateImpl(Attributor &A) override {
 
     return Change;
   }
 };
 
 struct AAFunctionReachabilityFunction : public AAFunctionReachability {
 private:
   struct QuerySet {
-    void markReachable(Function *Fn) {
-      Reachable.insert(Fn);
-      Unreachable.erase(Fn);
+    void markReachable(const Function &Fn) {
+      Reachable.insert(&Fn);
+      Unreachable.erase(&Fn);
     }
 
+    /// If there is no information about the function None is returned.
+    Optional<bool> isCachedReachable(const 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<const Function *> Reachable;
+
+    /// Set of functions that are unreachable, but might become reachable.
+    DenseSet<const 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)) {
+      for (const Function *Fn : make_early_inc_range(Unreachable)) {
+        if (checkIfReachable(A, AA, AAEdgesList, *Fn)) {
           Change = ChangeStatus::CHANGED;
-          markReachable(Fn);
+          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;
+                     ArrayRef<const AACallEdges *> AAEdgesList,
+                     const Function &Fn) {
+      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);
+      Unreachable.insert(&Fn);
 
       bool Result = checkIfReachable(A, AA, AAEdgesList, Fn);
       if (Result)
         markReachable(Fn);
       return Result;
     }
 
     bool checkIfReachable(Attributor &A, const AAFunctionReachability &AA,
                           ArrayRef<const AACallEdges *> AAEdgesList,
-                          Function *Fn) const {
+                          const Function &Fn) const {
 
       // Handle the most trivial case first.
       for (auto *AAEdges : AAEdgesList) {
         const SetVector<Function *> &Edges = AAEdges->getOptimisticEdges();
 
-        if (Edges.count(Fn))
+        if (Edges.count(const_cast<Function *>(&Fn)))
           return true;
       }
 
       SmallVector<const AAFunctionReachability *, 8> Deps;
       for (auto &AAEdges : AAEdgesList) {
         const SetVector<Function *> &Edges = AAEdges->getOptimisticEdges();
 
         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))
             return true;
         }
       }
 
       // The result is false for now, set dependencies and leave.
-      for (auto Dep : Deps)
-        A.recordDependence(AA, *Dep, DepClassTy::REQUIRED);
+      for (auto *Dep : Deps)
+        A.recordDependence(*Dep, AA, 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,
+                             const 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;
+      const auto &CB = cast<CallBase>(CBInst);
+      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 (const 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, const 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);
 
     return Result;
   }
 
   /// Can \p CB reach \p Fn
-  bool canReach(Attributor &A, CallBase &CB, Function *Fn) const override {
+  bool canReach(Attributor &A, CallBase &CB,
+                const 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);
 
     return Result;
   }
 
+  bool instructionCanReach(Attributor &A, const Instruction &Inst,
+                           const 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<const CallBase *, QueryResolver> CBQueries;
+
+  /// This is for instruction queries than scan "forward".
+  DenseMap<const Instruction *, QueryResolver> InstQueries;
+
+  /// This is for instruction queries than scan "backward".
+  DenseMap<const Instruction *, QuerySet> InstQueriesBackwards;
 };
 
 /// ---------------------- Assumption Propagation ------------------------------
 struct AAAssumptionInfoImpl : public AAAssumptionInfo {
   AAAssumptionInfoImpl(const IRPosition &IRP, Attributor &A,
                        const DenseSet<StringRef> &Known)
       : AAAssumptionInfo(IRP, A, Known) {}
 

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) {
+    declare void @unknown()
+    define internal void @func5(void ()* %ptr) {
     entry:
-      call void %unknown()
+      call void %ptr()
+      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 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