[Attributor] Use internalized versions of non-exact functions

[jdoerfert]

Summary

As already described in D63312, ~67% of all function declarations in the
LLVM test suite and SPEC2006 are non-exact, thus they can be replaced at
link-time. D63312 introduced shallow wrappers to allows self-recursive
deduction and the manifestation of attributes even in the case of
non-exact definitions. In this patch we go further and completely
replace the use of non-exact functions in a module by their internalized
version. This can come with increased cost, e.g., when the internalized
version is inlined in the wrapper, but it also allows to perform actual
inter-procedural reasoning.

The changes in the statistics output (>1%) for the LLVM-TS and SPEC2006
can be found here: https://gist.github.com/jdoerfert/fd70dd44a365f5c3c33ec856464cf1cb
There were multiple runtime performance improvements (~3-30%), some of
which came with compile time costs. I will provide more data once we
have attributes in the tree.

As with D63315 and D63317, tests will be added once an attribute is
deduced in the trunk.

[arsenm]

Is this still testless?

[jdoerfert]

I have to revisit this. Haven't done that since June, need to figure out when I'll find the time though.

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

private:
   /// We cannot use information from non-exact definitions to improve other
   /// definitions as the non-exact ones might be redefined at link-time which
   /// could invalidate the result.
   ///
   /// We can, however, use information from non-exact definitions to improve
   /// themselves as they are either replaced as a whole or not at all.
   ///
   /// \param AA The abstract attribute checked.
-  /// \param WrappedFunctions Functions now enclosed in a shallow wrapper.
   /// \param DepMap A map from abstract attributes to others they depend on.
-  /// \param Cache A cache with known results.
-  bool mayDependOnNonExactDefinition(
-      AbstractAttribute &AA, SmallPtrSetImpl<Function *> &WrappedFunctions,
-      QueryMapTy &DepMap, DenseMap<AbstractAttribute *, Optional<bool>> &Cache);
+  bool mayDependOnNonExactDefinition(AbstractAttribute &AA, QueryMapTy &DepMap);
 };
 
 /// Data structure to hold cached (LLVM-IR) information.
 ///
 /// All attributes are given an InformationCache object at creation time to
 /// avoid inspection of the IR by all of them individually. This default
 /// InformationCache will hold information required by 'default' attributes,
 /// thus the ones deduced when Attributor::identifyDefaultAbstractAttributes(..)

llvm/lib/Transforms/IPO/Attributor.cpp

 using namespace llvm;
 
 #define DEBUG_TYPE "attributor"
 
 STATISTIC(NumFnWithExactDefinition,
           "Number of function with exact definitions");
 STATISTIC(NumFnWithoutExactDefinition,
           "Number of function without exact definitions");
-STATISTIC(NumFnShallowWrapperCreated, "Number of shallow wrappers created");
-STATISTIC(NumAttrsRequiredDeepWrapper,
-          "Number of non-trivial attributes requiring a deep wrapper");
+STATISTIC(NumFnWrapperCreated, "Number of wrappers created");
 STATISTIC(NumAttributesTimedOut,
           "Number of abstract attributes timed out before fixpoint");
 STATISTIC(NumAttributesValidFixpoint,
           "Number of abstract attributes in a valid fixpoint state");
 STATISTIC(NumAttributesManifested,
           "Number of abstract attributes manifested in IR");
 
 STATISTIC(NumFnUniqueReturned, "Number of function with unique return");
ChangeStatus Attributor::run() {
   }
 
   LLVM_DEBUG({
     if (!Visited.empty())
       dbgs() << "\n[Attributor] Finalized " << Visited.size()
              << " abstract attributes.\n";
   });
 
-  SmallPtrSet<Function *, 32> WrappedFunctions;
-  DenseMap<AbstractAttribute *, Optional<bool>> NonExactDefinitionCache;
   QueryMapTy DepMap;
   for (auto &It : QueryMap)
     for (AbstractAttribute *QuerriedAA : It.second)
       DepMap[QuerriedAA].insert(It.first);
 
   unsigned NumManifested = 0;
   unsigned NumAtFixpoint = 0;
   ChangeStatus ManifestChange = ChangeStatus::UNCHANGED;
   for (AbstractAttribute *AA : AllAbstractAttributes) {
     AbstractState &State = AA->getState();
 
     // If there is not already a fixpoint reached, we can now take the
     // optimistic state. This is correct because we enforced a pessimistic one
     // on abstract attributes that were transitively dependent on a changed one
     // already above.
     if (!State.isAtFixpoint())
       State.indicateOptimisticFixpoint();
 
     // If the state is invalid, we do not try to manifest it.
     if (!State.isValidState())
       continue;
 
     // We cannot manifest the state if it maybe dependent on non-exact
     // definitions that could be replaced at link-time.
-    if (mayDependOnNonExactDefinition(*AA, WrappedFunctions, DepMap,
-                                      NonExactDefinitionCache))
+    if (mayDependOnNonExactDefinition(*AA, DepMap))
       continue;
 
     // Manifest the state and record if we changed the IR.
     ChangeStatus LocalChange = AA->manifest(*this);
     ManifestChange = ManifestChange | LocalChange;
 
     NumAtFixpoint++;
     NumManifested += (LocalChange == ChangeStatus::CHANGED);

 /// Assuming the declaration of looks like:
 ///   rty F(aty0 arg0, ..., atyN argN);
 ///
 /// The wrapper will then look as follows:
 ///   rty wrapper(aty0 arg0, ..., atyN argN) {
 ///     return F(arg0, ..., argN);
 ///   }
 ///
-static void createShallowWrapper(Function &F) {
-  assert(AllowShallowWrappers &&
-         "Cannot create a wrapper if it is not allowed!");
+static void createWrapper(Function &F) {
   assert(!F.isDeclaration() && "Cannot create a wrapper around a declaration!");
 
   Module &M = *F.getParent();
   LLVMContext &Ctx = M.getContext();
   FunctionType *FnTy = F.getFunctionType();
 
   StringRef Prefix = "__internal_";
   F.setName(Prefix + F.getName());
   Function *Wrapper =
       Function::Create(FnTy, F.getLinkage(), F.getAddressSpace(),
                        F.getName().substr(Prefix.size()));
   M.getFunctionList().insert(F.getIterator(), Wrapper);
 
   F.setLinkage(GlobalValue::InternalLinkage);
 
-  F.replaceAllUsesWith(Wrapper);
-  assert(F.getNumUses() == 0 && "Uses remained after wrapper was created!");
-
   // Move the COMDAT section to the wrapper.
   // TODO: Check if we need to keep it for F as well.
   Wrapper->setComdat(F.getComdat());
   F.setComdat(nullptr);
 
   // Copy all metadata and attributes but keep them on F as well.
   SmallVector<std::pair<unsigned, MDNode *>, 1> MDs;
   F.getAllMetadata(MDs);
for (Argument &Arg : Wrapper->args()) {
     Args.push_back(&Arg);
     Arg.setName((FArgIt++)->getName());
   }
 
   CallInst *CI = CallInst::Create(&F, Args, "", EntryBB);
   CI->setTailCall(true);
   ReturnInst::Create(Ctx, CI->getType()->isVoidTy() ? nullptr : CI, EntryBB);
 
-  NumFnShallowWrapperCreated++;
+  NumFnWrapperCreated++;
 }
 
-bool Attributor::mayDependOnNonExactDefinition(
-    AbstractAttribute &AA, SmallPtrSetImpl<Function *> &WrappedFunctions,
-    QueryMapTy &DepMap, DenseMap<AbstractAttribute *, Optional<bool>> &Cache) {
+bool Attributor::mayDependOnNonExactDefinition(AbstractAttribute &AA,
+                                               QueryMapTy &DepMap) {
   Function &AnchorScope = AA.getAnchorScope();
-  bool MayDepend = false;
-  bool NeedShallowWrapper = false;
 
-  // Even if this attribute does not depend on another one, we require a shallow
+  // Even if this attribute does not depend on another one, we require a
   // wrapper if manifesting it will modify the interface of a non-exact
   // definition.
   if (!AnchorScope.hasExactDefinition() &&
       AA.getManifestPosition() != AbstractAttribute::MP_CALL_SITE_ARGUMENT)
-    NeedShallowWrapper = true;
-
-  // Pre-initialize the cache for recursive dependences.
-  Cache[&AA] = false;
+    createWrapper(AnchorScope);
 
   auto &SourceAAs = DepMap[&AA];
   for (AbstractAttribute *SourceAA : SourceAAs) {
     // Self dependences and dependences on an invalid abstract attribute are OK.
     if (SourceAA == &AA || !SourceAA->getState().isValidState())
       continue;
 
-    // If the anchor scope (=surrounding function) is different and the queried
-    // abstract attribute is in an non-exact definition the current abstract
-    // attribute may depend on that non-exact definition.
+    // If the queried abstract attribute is in an non-exact definition the
+    // current abstract attribute may depend on that non-exact definition.
     Function &QuerriedAnchorScope = SourceAA->getAnchorScope();
-    if (&QuerriedAnchorScope != &AnchorScope &&
-        (WrappedFunctions.count(&QuerriedAnchorScope) ||
-         !QuerriedAnchorScope.hasExactDefinition())) {
-      MayDepend = true;
-      break;
-    }
-
-    // Check the cache or recurs if necessary to determine if the queried
-    // abstract attribute might be dependent on non-exact definitions.
-    Optional<bool> QuerriedAARes = Cache[SourceAA];
-    if (!QuerriedAARes.hasValue())
-      QuerriedAARes = mayDependOnNonExactDefinition(*SourceAA, WrappedFunctions,
-                                                    DepMap, Cache);
-
-    assert(QuerriedAARes.hasValue());
-    if (QuerriedAARes.getValue()) {
-      MayDepend = true;
-      break;
-    }
-
-    // We can depend on call site attributes. Note that we set
-    // NeedShallowWrapper already in the beginning if this is a function level
-    // attribute in a non-exact definition.
-    if (SourceAA->getManifestPosition() ==
-        AbstractAttribute::MP_CALL_SITE_ARGUMENT)
+    if (QuerriedAnchorScope.hasExactDefinition())
       continue;
 
-    // A dependence to an abstract attribute in this function was found. This
-    // means we need to create a shallow wrapper if the function does not have
-    // an exact definition.
-    NeedShallowWrapper = !AnchorScope.hasExactDefinition();
-  }
-
-  if (NeedShallowWrapper && !AllowShallowWrappers)
-    MayDepend = true;
-
-  if (!MayDepend && NeedShallowWrapper) {
-    WrappedFunctions.insert(&AnchorScope);
-    createShallowWrapper(AnchorScope);
+    mayDependOnNonExactDefinition(*SourceAA, DepMap);
+    createWrapper(QuerriedAnchorScope);
   }
 
-  if (MayDepend)
-    NumAttrsRequiredDeepWrapper++;
-
-  Cache[&AA] = MayDepend;
-  return MayDepend;
+  return false;
 }
 
 void Attributor::identifyDefaultAbstractAttributes(
     Function &F, InformationCache &InfoCache,
     DenseSet</* Attribute::AttrKind */ unsigned> *Whitelist) {
 
   auto OnWhiteList = [Whitelist](unsigned ID) -> bool {
     return Whitelist ? Whitelist->count(ID) : true;