[Attributor] Derive AACallEdges attribute

[kuter]

Summary

This attribute computes the optimistic live call edges using the attributor
liveness information. This attribute will be used for deriving a
inter-procedural function reachability attribute.

[kuter]

The way CallGraph handles callbacks doesn't make sense to me.
In the CallGraph::populateCallGraphNode callbacks are handled by the forEachCallbackFunction function.
like this:

// Add reference to callback functions.
forEachCallbackFunction(*Call, [=](Function *CB) {
    Node->addCalledFunction(nullptr, getOrInsertFunction(CB));
});

Which uses the AbstractCallSite::getCallbackUses and checks if the Use is a function.
The source of the AbstractCallSite::getCallbackUses is given below.

void AbstractCallSite::getCallbackUses(       
    const CallBase &CB, SmallVectorImpl<const Use *> &CallbackUses) { 
  const Function *Callee = CB.getCalledFunction(); 
  if (!Callee)                                                      
    return; 

   ....                                                              
}

CB.getCalledFunction returns null if the call is indirect. And a callback is indirect, right ?
Also the getCallbackUses uses the callback metadata which is intended for the function definitions rather than calls.

Am I misunderstanding something ?

[jdoerfert]

Can you please reupload after clang formatting the code :)

[kuter]

• Custom iterator for lazly creating AACallEdges
• GraphTraits implementation

[kuter]

In D104059#2811617, @jdoerfert wrote:

Can you please reupload after clang formatting the code :)

Sorry, I thought arcanist did that automatically.

[kuter]

• Added DOTGraphTraits implementation
• Added Test
• Small fix

[jdoerfert]

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

3877

Maybe call it AACallEdgeIterator?

3931

Don't store the Attributor instance, let the user pass it where needed.

3957

Same as above.

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

8176

Rather than asking for liveness, use a generic value traversal to visit all potential values of Val. Each of which is a potential callee. Also make sure to handle the case where a callee is not known, e.g., a function pointer call. We need to add them to the call graph as unknown callees too.

8181

checkForAllCallLikeInstructions

8192

Return at least the number as well.

[kuter]

• Reanme custom iterator
• Use checkForAllCallLikeInstructions

[kuter]

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

3931

I wanted not to but we need this to have a GraphTraits implementation.
GraphTraits::child_begin only takes the node itself and we need Attributor to create the AACallEdges.
I don't think there are any other way to inject the Attributor inside GraphTraits::child_begin

[jdoerfert]

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

3931

Then store it in AACallGraphNode I gues.

[kuter]

Move attributor instance to the AACallGraphNode

[kuter]

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

8176

Ok when I add the genericValueTraversal should we still keep the getCallbackUses function since it uses the callback metadata ?
There is also a callees meta data that is ment to annotate a call, it gurantees that the called function is one of the functions it specifies.
This seems useful for our purposes. getCallbackUses doesn't use it.

I was planning to add a flag to tell if there are any calls to a unknown function somethling like bool hasUnknownCallee()

Also for us to be able to say that function x can't reach function b, we need to make sure that we know all functions that function x might ever call. Meaning that if there are any functions that x can reach that has a unknown callee we can't tell for sure, right ?

[jdoerfert]

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

8176

I would have done getCallbackUses and then on the argument operands a genericValueTraversal. In the code above that means genericValueTraversal for Val. See also callees metadata below

If we have an unknown caller, we can reach any "visible" function. For now, you can assume any function but in reality you could exclude internal functions that don't have their address taken, for example.

So, how to use callees metadata is a good question. We want to expand what an AbstractCallSite is, I think. So first, an AbstractCallSite needs to get a new "kind", which is a direct call site with a "potential" callee. This is somewhat independent and we want to use it also as part of the checkForAllCallSites. To make this happen we'll need to either go through metadata uses (which is hard, IIRC) or use the AACallEdge in checkForAllCallSites. For the latter we also track in the AACallEdgeFunction node what all callers are, basically the callers should notify the AACallEdgeFunction of the Callee. If we do it that way, we can handle callee metadata here. I would suggest to have a new AbstractCallSite interface that allows you to iterate over a set of AbstractCallSites that a CallBase "exposes". For a direct call, that's just the direct callee. For a call with callees metadata, it will be one AbstractCallSite per callee node specified. And for all callbacks annotations, it would be one AbstractCallSite per callback annotation on the callee, basically line 8166-8168 above. This new interface would replace the getCallbackUses above and we could also (for now at least) ignore the genericValueTraversal thing. Certainly remove the isdead part.
Does this make sense?

[kuter]

• Add genericValueTraveral
• Add test a test for call with select (Doesn't work :/)
• Track if there are any unknown callees.

[kuter]

llvm/test/Transforms/Attributor/callgraph.ll

62 ↗

(On Diff #352471)

This edge is missing. genericValueTraversal doesn't seem to be returning the func4.

[jdoerfert]

More comments, also, please fix the clang tidy warnings, they make it hard to read.

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

8151

8169

You need to bail if the return value is false, IIRC.

8172

8191

You need to bail if the return value is false.

llvm/test/Transforms/Attributor/callgraph.ll

62 ↗

(On Diff #352471)

That would be a problem, can you try to figure out what's going on?

[kuter]

Fix code styling.

there is not much I can do with the clang tidy since.

• I can't rename nodes_begin, it is needed for GraphTraits.
• And you should never desconstruct a AACallGraphNode.

[kuter]

Fix the problem with the missing edge.

[kuter]

Asume that there are unknown callees if we haven't looked at all values/instructions.

[kuter]

clang-format

[jdoerfert]

Can you add a test case with a callback and one with an unknown function pointer call. Maybe also one with a function pointer and callee metadata + a FIXME.

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

8157

[kuter]

• Handle callees metadata..
• Added test cases for callees and callback attributes.
• Small fix

[kuter]

clang-format

[kuter]

small fix

[jdoerfert]

LGTM, some nits. Thanks for fixing this up so quickly.

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

8178

We should not do this if we have callee metadata. Except maybe (later) if we can improve the callee metadata.

8191

No cast, a Function is a Value.

8223

Documentation.

[hokein]

I encountered two issues while integrating this patch to our internal codebase -- And the fixes look like trivial, I landed them directly to unblock my integration. Feel free to improve them if they don't suit.

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

8145

undefined behavior detected by asan: HasUnknownCallee value might be undefined, fixed in 3f5d53a525c62c507a482fd5f4c08451835b342d.

8212

hard-coding a filename looks like not a common pattern in LLVM AFAIK, and the test might fail on some sandbox environment. I landed 7670938bbad8755a34a282febc852651255c69b3 to improve this behavior.

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

struct AANoUndef
   static bool classof(const AbstractAttribute *AA) {
     return (AA->getIdAddr() == &ID);
   }
 
   /// Unique ID (due to the unique address)
   static const char ID;
 };
 
+/// An abstract state for querying live call edges.
+/// This interface uses the Attributor's optimistic liveness
+/// information to compute the edges that are alive.
+struct AACallEdges: public StateWrapper<BooleanState, AbstractAttribute> {
+  using Base = StateWrapper<BooleanState, AbstractAttribute>;
+
+  AACallEdges(const IRPosition &IRP, Attributor &A) : Base(IRP) {}
+
+  /// Create an abstract attribute view for the position \p IRP.
+  static AACallEdges &createForPosition(const IRPosition &IRP, Attributor &A);
+
+  /// See AbstractAttribute::getName()
+  const std::string getName() const override { return "AACallEdges"; }
+
+  /// See AbstractAttribute::getIdAddr()
+  const char *getIdAddr() const override { return &ID; }
+
+  virtual const DenseSet<Function*>& getOptimisticEdges() const = 0;
+
+  /// 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;
+};
+
+
+
 /// 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(AAReachability)
 PIPE_OPERATOR(AAMemoryBehavior)
 PIPE_OPERATOR(AAMemoryLocation)
 PIPE_OPERATOR(AAValueConstantRange)
 PIPE_OPERATOR(AAPrivatizablePtr)
 PIPE_OPERATOR(AAUndefinedBehavior)
 PIPE_OPERATOR(AAPotentialValues)
 PIPE_OPERATOR(AANoUndef)
+PIPE_OPERATOR(AACallEdges)
 
 #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 AANoUndefCallSiteReturned final
     : AACallSiteReturnedFromReturned<AANoUndef, AANoUndefImpl> {
   AANoUndefCallSiteReturned(const IRPosition &IRP, Attributor &A)
       : AACallSiteReturnedFromReturned<AANoUndef, AANoUndefImpl>(IRP, A) {}
 
   /// See AbstractAttribute::trackStatistics()
   void trackStatistics() const override { STATS_DECLTRACK_CSRET_ATTR(noundef) }
 };
+
+//TODO: Implement GraphTraits ?
+struct AACallEdgesFunction : public AACallEdges {
+  AACallEdgesFunction(const IRPosition &IRP, Attributor &A)
+   : AACallEdges(IRP, A) {}
+
+  /// See AbstractAttribute::updateImpl(...).
+  ChangeStatus updateImpl(Attributor &A) override {
+    ChangeStatus Change = ChangeStatus::UNCHANGED;
+
+    // A dependency will be added if the information is used.
+    const AAIsDead &LivenessAA = A.getAAFor<AAIsDead>(*this,
+                                              getIRPosition(),
+                                              DepClassTy::NONE);
+
+    // Opcodes of callable instructions. These all ineherit from CallBase.
+    auto Opcodes = {
+        (unsigned)Instruction::Invoke, (unsigned)Instruction::CallBr,
+        (unsigned)Instruction::Call
+    };
+
+    auto AddCalledFunction = [&](Function *Fn) {
+      // Track the changes.
+      if (CalledFunctions.insert(Fn).second)
+        Change = Change | ChangeStatus::CHANGED;
+    };
+
+    auto ProcessCallInst = [&](Instruction &Inst) {
+      CallBase &CB = static_cast<CallBase&>(Inst);
+      Function *Callee = CB.getCalledFunction();
+      // The most simple case.
+      if (Callee)
+        AddCalledFunction(Callee);
+
+      //Process callback functions.
+      SmallVector<const Use *, 4u> CallbackUses;
+      AbstractCallSite::getCallbackUses(CB, CallbackUses);
+      for (const Use *U : CallbackUses) {
+        AbstractCallSite ACS(U);
+        Function *Fn = ACS.getCalledFunction();
+        Value *Val = U->get();
+        // Ask the attributor if the value is alive.
+        if (Fn && !A.isAssumedDead(IRPosition::value(*Val), this, &LivenessAA))
+          AddCalledFunction(Fn);
+      }
+      return true;
+    };
+    // Visit all callable instructions.
+    A.checkForAllInstructions(ProcessCallInst, *this, Opcodes);
+
+    return Change;
+  }
+
+  virtual const DenseSet<Function*>& getOptimisticEdges() const override {
+     return CalledFunctions;
+  };
+
+  const std::string getAsStr() const override {
+    //TODO: Be more informative.
+    return "CallEdges";
+  }
+
+  void trackStatistics() const override {}
+
+  DenseSet<Function*> CalledFunctions;
+};
+
 } // namespace
 
 const char AAReturnedValues::ID = 0;
 const char AANoUnwind::ID = 0;
 const char AANoSync::ID = 0;
 const char AANoFree::ID = 0;
 const char AANonNull::ID = 0;
 const char AANoRecurse::ID = 0;
 const char AAWillReturn::ID = 0;
 const char AAUndefinedBehavior::ID = 0;
 const char AANoAlias::ID = 0;
 const char AAReachability::ID = 0;
 const char AANoReturn::ID = 0;
 const char AAIsDead::ID = 0;
 const char AADereferenceable::ID = 0;
 const char AAAlign::ID = 0;
 const char AANoCapture::ID = 0;
 const char AAValueSimplify::ID = 0;
 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;
 
 // 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_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