[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

8691

Don't accumulate pointers to containers but content instead.

8835–8836

|=, also elsewhere
no braces.

[jdoerfert]

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

4360

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

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

8734

I don't get the backwards stuff.

[kuter]

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

8691

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

8835–8836

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

[jdoerfert]

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

8707

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.

8723

don't ignore the return value

8731

no braces.

llvm/unittests/Transforms/IPO/AttributorTest.cpp

204

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

8673

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.

8694–8695

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.

8702–8704

Why no range loop?

[kuter]

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

8702–8704

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

8702–8704

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

8673

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

8673

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

8710–8715

8801

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

8807

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

8824

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

8834

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

8670

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

8859

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

struct AAFunctionReachability
   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;
 
   /// Can \p CB reach \p Fn
   virtual bool canReach(Attributor &A, CallBase &CB, Function *Fn) const = 0;
 
+  /// Can  \p Inst reach \p Fn
+  virtual bool instCanReach(Attributor &A, Instruction &Inst,
+                            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

ChangeStatus update(Attributor &A, const AAFunctionReachability &AA,
         It++;
         if (isReachable(A, AA, AAEdgesList, Fn))
           Change = ChangeStatus::CHANGED;
       }
 
       return Change;
     }
 
+    void markReachable(Function &Fn) {
+      Reachable.insert(&Fn);
+      Unreachable.erase(&Fn);
+    }
+
     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;
 
       bool Result = checkIfReachable(A, AA, AAEdgesList, Fn);
       if (Result) {
-        Reachable.insert(Fn);
-        Unreachable.erase(Fn);
+        markReachable(*Fn);
       } else {
         Unreachable.insert(Fn);
       }
       return Result;
     }
 
     bool checkIfReachable(Attributor &A, const AAFunctionReachability &AA,
                           ArrayRef<const AACallEdges *> AAEdgesList,
bool checkIfReachable(Attributor &A, const AAFunctionReachability &AA,
       }
       return false;
     }
 
     /// 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;
   };
 
+  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, CBInst, Inst))
+        return true;
+
+      CallBase &CB = static_cast<CallBase &>(Inst);
+      const AACallEdges &AAEdges = A.getAAFor<AACallEdges>(
+          *this, IRPosition::callsite_function(CB), DepClassTy::REQUIRED);
+
+      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;
+    if (Set.Unreachable.empty())
+      return Change;
+
+    // For all remaining instruction queries, check
+    // callers. A call inside that function might satisfy the query.
+    auto CheckCallSite = [&](AbstractCallSite CallSite) {
+      Instruction *Inst =
+          CallSite.getInstruction()->getNextNonDebugInstruction();
+      const AAFunctionReachability &AA = A.getAAFor<AAFunctionReachability>(
+          *this, IRPosition::function(*Inst->getFunction()),
+          DepClassTy::REQUIRED);
+
+      for (auto It = Set.Unreachable.begin(); It != Set.Unreachable.end();) {
+        Function *Fn = *It;
+        It++;
+        if (AA.instCanReach(A, *Inst, Fn)) {
+          Set.markReachable(*Fn);
+          Change = ChangeStatus::CHANGED;
+        }
+      }
+      return true;
+    };
+    bool AllCallSitesKnown = false;
+    A.checkForAllCallSites(CheckCallSite, *this, true, AllCallSitesKnown);
+
+    // If we don't know all callsites we have to assume that we can reach
+    // fn.
+    if (!AllCallSitesKnown) {
+      for (auto &QueryPair : InstQueries) {
+        QueryPair.second.CanReachUnknownCallee = true;
+      }
+    }
+
+    return Change;
+  }
+
 public:
   AAFunctionReachabilityFunction(const IRPosition &IRP, Attributor &A)
       : AAFunctionReachability(IRP, A) {}
 
   bool canReach(Attributor &A, Function *Fn) const override {
     const AACallEdges &AAEdges =
         A.getAAFor<AACallEdges>(*this, getIRPosition(), DepClassTy::REQUIRED);
 
bool canReach(Attributor &A, CallBase &CB, Function *Fn) const override {
     auto *NonConstThis = const_cast<AAFunctionReachabilityFunction *>(this);
     QuerySet &CBQuery = NonConstThis->CBQueries[&CB];
 
     bool Result = CBQuery.isReachable(A, *this, {&AAEdges}, Fn);
 
     return Result;
   }
 
+  bool instCanReach(Attributor &A, Instruction &Inst,
+                    Function *Fn) const override {
+    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);
+    QuerySet &InstQuery = NonConstThis->InstQueries[&Inst];
+    if (!AllKnown)
+      InstQuery.CanReachUnknownCallee = true;
+
+    bool Result = InstQuery.isReachable(A, *this, CallEdges, Fn);
+    if (Result)
+      return true;
+
+    // Check backwards reachability.
+    NonConstThis->checkReachableBackwards(A, InstQuery);
+
+    return InstQuery.isReachable(A, *this, CallEdges, Fn);
+  }
+
   /// See AbstractAttribute::updateImpl(...).
   ChangeStatus updateImpl(Attributor &A) override {
     const AACallEdges &AAEdges =
         A.getAAFor<AACallEdges>(*this, getIRPosition(), DepClassTy::REQUIRED);
     ChangeStatus Change = ChangeStatus::UNCHANGED;
 
     Change = Change | WholeFunction.update(A, *this, {&AAEdges});
-
+    // Update the CallBaseQueries.
     for (auto CBPair : CBQueries) {
       const AACallEdges &AAEdges = A.getAAFor<AACallEdges>(
           *this, IRPosition::callsite_function(*CBPair.first),
           DepClassTy::REQUIRED);
 
       Change = 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 = Change | InstPair.second.update(A, *this, CallEdges);
+    }
+
+    for (auto QueryPair : InstQueries) {
+      Change = 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;
   }
 
   QuerySet WholeFunction;
   DenseMap<CallBase *, QuerySet> CBQueries;
+  DenseMap<Instruction *, QuerySet> InstQueries;
 };
 
 } // 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) {
 
   ASSERT_EQ(SFail, nullptr);
   ASSERT_TRUE(SSucc);
 }
 
 TEST_F(AttributorTestBase, AAReachabilityTest) {
   const char *ModuleString = R"(
     @x = global i32 0
-    define void @func4() {
+    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);
 
   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));
 
   const AAFunctionReachability &F6AA =
       A.getOrCreateAAFor<AAFunctionReachability>(IRPosition::function(*F6));
 
   const AAFunctionReachability &F7AA =
       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.instCanReach(A, F9FirstInst, F3);
+  F9AA.instCanReach(A, F9SecondInst, F3);
+  F9AA.instCanReach(A, F9FirstInst, F4);
 
   A.run();
 
   ASSERT_TRUE(F1AA.canReach(A, F3));
   ASSERT_TRUE(F7AA.canReach(A, F7FirstCB, 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));
+
+  // The second instruction of F9 can't reach the first call.
+  // FIXME: This happens due to backwards reachability.
+  ASSERT_TRUE(F9AA.instCanReach(A, F9SecondInst, F3));
+  // The first instruction of F9 can reach the first call.
+  ASSERT_TRUE(F9AA.instCanReach(A, F9FirstInst, F3));
+  // Because func10 calls the func4 after the call to func9 it is reachable.
+  ASSERT_TRUE(F9AA.instCanReach(A, F9FirstInst, F4));
 }
 
 } // namespace llvm