[Attributor][WIP] Cost interface for function internalization

[bbn]

Summary

Introduce a cost interface which determines whether internalizing a function is worthwhile.

[bbn]

For now the patch only contains the interface and is still WIP. I will update it with more detailed algorithm later.

[jdoerfert]

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

145

Make the names more descriptive and add plenty doxygen documentation for all of them. Maybe put them all in a struct so the user could modify the values by changing the struct members.

llvm/lib/Transforms/IPO/Attributor.cpp

2212

I somehow think the method called here should be "shouldInternalize" or something. The problem here is that it "looks" like we internalize if there is an associated cost, e.g., the cost is not zero.

[bbn]

• Cache the InternalizeCost for every function

What I am thinking is that we need to calculate the cost after all dependencies between
AAs become clear. So I think we need to do the cost analysis after the fix point
iteration (or after the first update is done).

[bbn]

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

145

Sure, I will add docs once I figure out the when to do such cost analysis and what
can increase the cost of internalization (for now I can only think of the number of
instructions) and what can be the "bonus".

[bbn]

Changed some function names.

[jdoerfert]

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

195

There is no need for dynamic allocation here. Let's just return a value, it's only 16 bytes on most systems so easy to copy and with the advantage that we don't leak memory ;)

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

 struct AADepGraph;
 struct Attributor;
 struct AbstractAttribute;
 struct InformationCache;
 struct AAIsDead;
 
 class Function;
 
+namespace InternalizeConstants {
+/// Default threshold
+const int DefaultThreshold = 100;
+
+// Various magic constants used to adjust heuristics
+const int InstrCost = 5;
+const int DepBonus = 5;
+
+} // namespace InternalizeConstants
+
 /// Simple enum classes that forces properties to be spelled out explicitly.
 ///
 ///{
 enum class ChangeStatus {
   CHANGED,
   UNCHANGED,
 };
 
 ChangeStatus operator|(ChangeStatus l, ChangeStatus r);
 ChangeStatus operator&(ChangeStatus l, ChangeStatus r);
 
 enum class DepClassTy {
   REQUIRED,
   OPTIONAL,
 };
 ///}
 
+/// Represents the cost of internalizing a function.
+///
+/// The cost represents a unitless amount; smaller values increase the
+/// likelihood of the function being internalized.
+class InternalizeCost {
+  enum SentinelValues {
+    AlwaysInternalizeCost = INT_MIN,
+    NeverInternalizeCost = INT_MAX
+  };
+
+  /// The function to be internalized
+  Function &F;
+
+  /// The estimated cost of internalizing a function
+  int Cost = 0;
+
+  /// The threshold against which this cost is computed.
+  int Threshold = 0;
+
+  /// Trivial constructor
+  InternalizeCost(Function &F, int Cost, int Threshold)
+      : F(F), Cost(Cost), Threshold(Threshold) {}
+
+public:
+  static InternalizeCost &get(int Cost, int Threshold, Function &F) {
+    return *new InternalizeCost(F, Cost, Threshold);
+  }
+  static InternalizeCost &getNever(Function &F) {
+    return *new InternalizeCost(F, NeverInternalizeCost, 0);
+  }
+  static InternalizeCost &getAlways(Function &F) {
+    return *new InternalizeCost(F, AlwaysInternalizeCost, 0);
+  }
+
+  /// Test whether the internalize cost is low enough for internalizing
+  explicit operator bool() const { return Cost < Threshold; }
+  bool shouldInternalize() const { return Cost < Threshold; }
+
+  /// Get the function this cost corresponds to
+  Function &getFunction() const { return F; }
+
+  /// Get the internalize cost estimate.
+  int getCost() const { return Cost; }
+
+  /// Get the threshold against which the cost was computed.
+  int getThreshold() const { return Threshold; }
+
+  /// Get the cost delta from the threshold for internalizing.
+  /// Returns a negative value if the cost is too high to internalize
+  int getCostDelta() const { return Threshold - getCost(); }
+};
+
 /// The data structure for the nodes of a dependency graph
 struct AADepGraphNode {
 public:
   virtual ~AADepGraphNode(){};
   using DepTy = PointerIntPair<AADepGraphNode *, 1>;
 
 protected:
   /// Set of dependency graph nodes which this one depends on.
struct Attributor {
   ///
   /// Note that abstract attribute instances are generally created even if the
   /// IR already contains the information they would deduce. The most important
   /// reason for this is the single interface, the one of the abstract attribute
   /// instance, which can be queried without the need to look at the IR in
   /// various places.
   void identifyDefaultAbstractAttributes(Function &F);
 
+  /// Determine whether the function \p F can be internalized
+  bool shouldInternalizeFunction(Function &F);
+
   /// Determine whether the function \p F is IPO amendable
   ///
   /// If a function is exactly defined or it has alwaysinline attribute
   /// and is viable to be inlined, we say it is IPO amendable
   bool isFunctionIPOAmendable(const Function &F) {
     return F.hasExactDefinition() || InfoCache.InlineableFunctions.count(&F);
   }
 
private:
   SmallVector<DependenceVector *, 16> DependenceStack;
 
   /// If not null, a set limiting the attribute opportunities.
   const DenseSet<const char *> *Allowed;
 
   /// A set to remember the functions we already assume to be live and visited.
   DenseSet<const Function *> VisitedFunctions;
 
+  /// A map for caching results of queries for getInternalizeCost
+  DenseMap<const Function *, InternalizeCost *> InternalizationMap;
+
   /// Uses we replace with a new value after manifest is done. We will remove
   /// then trivially dead instructions as well.
   DenseMap<Use *, Value *> ToBeChangedUses;
 
   /// Instructions we replace with `unreachable` insts after manifest is done.
   SmallDenseSet<WeakVH, 16> ToBeChangedToUnreachableInsts;
 
   /// Invoke instructions with at least a single dead successor block.

llvm/lib/Transforms/IPO/Attributor.cpp

if (Attr.isIntAttribute()) {
     Attrs = Attrs.removeAttribute(Ctx, AttrIdx, Kind);
     Attrs = Attrs.addAttribute(Ctx, AttrIdx, Attr);
     return true;
   }
 
   llvm_unreachable("Expected enum or string attribute!");
 }
 
+/// Calculate the cost of internalizing the function \p F and determine whether
+/// internalizing such function could be beneficial.
+static InternalizeCost &getInternalizeCost(Function &F) {
+  /// TODO: for now we only rule out situations where the function cannot be
+  ///       internalized. The detailed algorithm will be implemented later.
+  if (F.isDeclaration() || F.hasExactDefinition() || !F.getNumUses() ||
+      F.getLinkage() == GlobalValue::LinkOnceAnyLinkage ||
+      F.getLinkage() == GlobalValue::WeakAnyLinkage) {
+    return InternalizeCost::getNever(F);
+  }
+
+  return InternalizeCost::getAlways(F);
+}
+
 Argument *IRPosition::getAssociatedArgument() const {
   if (getPositionKind() == IRP_ARGUMENT)
     return cast<Argument>(&getAnchorValue());
 
   // Not an Argument and no argument number means this is not a call site
   // argument, thus we cannot find a callback argument to return.
   int ArgNo = getArgNo();
   if (ArgNo < 0)
void Attributor::identifyDefaultAbstractAttributes(Function &F) {
   };
   Success = checkForAllInstructionsImpl(
       nullptr, OpcodeInstMap, LoadStorePred, nullptr, nullptr,
       {(unsigned)Instruction::Load, (unsigned)Instruction::Store});
   (void)Success;
   assert(Success && "Expected the check call to be successful!");
 }
 
+bool Attributor::shouldInternalizeFunction(Function &F) {
+  if (auto *IC = InternalizationMap[&F])
+    return IC->shouldInternalize();
+  else {
+    InternalizationMap[&F] = &getInternalizeCost(F);
+    return InternalizationMap[&F]->shouldInternalize();
+  }
+}
+
 /// Helpers to ease debugging through output streams and print calls.
 ///
 ///{
 raw_ostream &llvm::operator<<(raw_ostream &OS, ChangeStatus S) {
   return OS << (S == ChangeStatus::CHANGED ? "changed" : "unchanged");
 }
 
 raw_ostream &llvm::operator<<(raw_ostream &OS, IRPosition::Kind AP) {
for (Function *F : Functions)
         createShallowWrapper(*F);
 
   // Internalize non-exact functions
   // TODO: for now we eagerly internalize functions without calculating the
   //       cost, we need a cost interface to determine whether internalizing
   //       a function is "benefitial"
   if (AllowDeepWrapper)
     for (Function *F : Functions)
-      if (!F->hasExactDefinition() && F->getNumUses() &&
-          F->getLinkage() != llvm::GlobalValue::LinkOnceAnyLinkage &&
-          F->getLinkage() != llvm::GlobalValue::WeakAnyLinkage) {
+      if (A.shouldInternalizeFunction(*F)) {
         Function *NewF = internalizeFunction(*F);
         Functions.insert(NewF);
 
         // Update call graph
         CGUpdater.registerOutlinedFunction(*NewF);
         for (const Use &U : NewF->uses())
           if (CallBase *CB = dyn_cast<CallBase>(U.getUser())) {
             auto *CallerF = CB->getCaller();