[Attributor] Cache query results for isPotentiallyReachable in AAReachability

[okura]

Summary

This is the next patch of D76210.
This patch made a map in InformationCache for caching results.

[okura]

Added a comment

[jdoerfert]

I'm not sold on the liveness check. Do we have users of this function that would even try to call with a dead instruction? Usually, liveness is backed in so deep that all AAs actually see is assumed life.

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

729

Please add documentation and consider taking the instructions as references.

Nit: Move F after the first check to shorten the lifetime (and avoid confusion).

2397

Style: Most our interfaces take the Attributor first (I think).

[okura]

On second thoughts, I think so too about the licenses check.
Could you tell me where you think we can use the liveness information in this comment?

[okura]

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

729

Do you expect that I change interfaces of AAReachability to take instructions as references too?
Could you tell me the advantage of taking as references compared to taking as pointers? I don't mean I want to stick to pointers, just want to know about it.

[jdoerfert]

In D83246#2143962, @okura wrote:

On second thoughts, I think so too about the licenses check.
Could you tell me where you think we can use the liveness information in this comment?

Right. What I meant is we should use liveness when computing the entire reachability result, not only the endpoints. We can (reasonably) expect users to do the latter (for now).
If we compute reachability ourselves it is a different story as we can use the liveness of edges (eventually) to improve the result.

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

729

Yes, feel free to change the other interface as well.

There is no(t much) "functional benefit". In the Attributor we usually use references whenever we cannot pass null and pointers when we might (or have to use pointers). At the end of the day it is just a hint for the user that nullptr is not acceptable.

[okura]

fix according to review comments
change the purpose of this patch to caching query results only.

[jdoerfert]

Now that I look at this again, why don't we move everything into AAReachability, the map and such. It is the place we will eventually also compute things. The code looks good otherwise.

[okura]

I have difficulty in moving into AAReachability because a member should be const function. If the map move in AAReachability, the function that cache query results cannot be const. That's why I put the cache in InformationCache.

[jdoerfert]

In D83246#2163870, @okura wrote:

I have difficulty in moving into AAReachability because a member should be const function. If the map move in AAReachability, the function that cache query results cannot be const. That's why I put the cache in InformationCache.

Good point. Let's go with this :)

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

struct InformationCache {
   }
 
   /// Return datalayout used in the module.
   const DataLayout &getDL() { return DL; }
 
   /// Return the map conaining all the knowledge we have from `llvm.assume`s.
   const RetainedKnowledgeMap &getKnowledgeMap() const { return KnowledgeMap; }
 
+  /// Return if \p To is potentially reachable form \p From or not
+  /// If the same query was answered, return cached result
+  bool getPotentiallyReachable(const Instruction &From, const Instruction &To) {
+    auto KeyPair = std::make_pair(&From, &To);
+    auto Iter = PotentiallyReachableMap.find(KeyPair);
+    if (Iter != PotentiallyReachableMap.end())
+      return Iter->second;
+    const Function &F = *From.getFunction();
+    bool Result = isPotentiallyReachable(
+        &From, &To, nullptr, AG.getAnalysis<DominatorTreeAnalysis>(F),
+        AG.getAnalysis<LoopAnalysis>(F));
+    PotentiallyReachableMap.insert(std::make_pair(KeyPair, Result));
+    return Result;
+  }
+
 private:
   struct FunctionInfo {
     ~FunctionInfo();
 
     /// A nested map that remembers all instructions in a function with a
     /// certain instruction opcode (Instruction::getOpcode()).
     OpcodeInstMapTy OpcodeInstMap;
 
private:
   AnalysisGetter &AG;
 
   /// The underlying CGSCC, or null if not available.
   SetVector<Function *> *CGSCC;
 
   /// Set of inlineable functions
   SmallPtrSet<const Function *, 8> InlineableFunctions;
 
+  /// A map for caching results of queries for isPotentiallyReachable
+  DenseMap<std::pair<const Instruction *, const Instruction *>, bool>
+      PotentiallyReachableMap;
+
   /// Give the Attributor access to the members so
   /// Attributor::identifyDefaultAbstractAttributes(...) can initialize them.
   friend struct Attributor;
 };
 
 /// The fixpoint analysis framework that orchestrates the attribute deduction.
 ///
 /// The Attributor provides a general abstract analysis framework (guided

 /// An abstract interface to determine reachability of point A to B.
 struct AAReachability : public StateWrapper<BooleanState, AbstractAttribute> {
   using Base = StateWrapper<BooleanState, AbstractAttribute>;
   AAReachability(const IRPosition &IRP, Attributor &A) : Base(IRP) {}
 
   /// Returns true if 'From' instruction is assumed to reach, 'To' instruction.
   /// Users should provide two positions they are interested in, and the class
   /// determines (and caches) reachability.
-  bool isAssumedReachable(const Instruction *From,
-                          const Instruction *To) const {
-    return isPotentiallyReachable(From, To);
+  bool isAssumedReachable(Attributor &A, const Instruction &From,
+                          const Instruction &To) const {
+    return A.getInfoCache().getPotentiallyReachable(From, To);
   }
 
   /// Returns true if 'From' instruction is known to reach, 'To' instruction.
   /// Users should provide two positions they are interested in, and the class
   /// determines (and caches) reachability.
-  bool isKnownReachable(const Instruction *From, const Instruction *To) const {
-    return isPotentiallyReachable(From, To);
+  bool isKnownReachable(Attributor &A, const Instruction &From,
+                        const Instruction &To) const {
+    return A.getInfoCache().getPotentiallyReachable(From, To);
   }
 
   /// Create an abstract attribute view for the position \p IRP.
   static AAReachability &createForPosition(const IRPosition &IRP,
                                            Attributor &A);
 
   /// See AbstractAttribute::getName()
   const std::string getName() const override { return "AAReachability"; }

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

auto UsePred = [&](const Use &U, bool &Follow) -> bool {
       if (UserI == getCtxI() && UserI->hasOneUse())
         return true;
 
       const Function *ScopeFn = VIRP.getAnchorScope();
       if (ScopeFn) {
         const auto &ReachabilityAA =
             A.getAAFor<AAReachability>(*this, IRPosition::function(*ScopeFn));
 
-        if (!ReachabilityAA.isAssumedReachable(UserI, getCtxI()))
+        if (!ReachabilityAA.isAssumedReachable(A, *UserI, *getCtxI()))
           return true;
 
         if (auto *CB = dyn_cast<CallBase>(UserI)) {
           if (CB->isArgOperand(&U)) {
 
             unsigned ArgNo = CB->getArgOperandNo(&U);
 
             const auto &NoCaptureAA = A.getAAFor<AANoCapture>(