[Attributor] IPO across definition boundary of a function marked alwaysinline

[bbn]

Summary

If a function has alwaysinline attribute and can be inlined, we can treat the function as it has exact definition and perform fix-point analysis on it

[uenoku]

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

1728

Is FnScope always nonnull here?

[bbn]

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

1728

I think so, because the outer if has judgement: if(!FnScope || !FnScope->hasExactDefinition())

[jdoerfert]

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

1730

If !FnScope is true, FnScope is null. We need to cache the isInlineViable result.

llvm/test/Transforms/Attributor/alwaysinline.ll

79

You need check and check-not lines to make sure we do not derive function attributes where we should not.

[bbn]

I have fixed the problem that FnScope may be null and cached the result of isInlineViable. I have also updated my test file to check the attributes.

[jdoerfert]

In D75590#1906851, @bbn wrote:

I have fixed the problem that FnScope may be null and cached the result of isInlineViable. I have also updated my test file to check the attributes.

When I said "cache the result" I meant that we should ensure to call isInlineViable for each function at most once. Maybe at the beginning of the Attributor::run method we can go over all the functions and categorize them. If they have exact linkage *or* are alwaysinline and and viable to be inlined, we say they are "IPO amendable" and we put them in a set. We can then lookup in the set if the function is fine w/o the need to look for all criteria again. Does that make sense?

llvm/test/Transforms/Attributor/alwaysinline.ll

10

What do you mean by "removed safely" here?

22

is this one not readnone?

34

We analyze and annotate it because it is an exact definition, see Function::hasExactDefinition(). Make the function linkonce (or add another pair with linkonce) to see the difference.

[bbn]

1. Use InlineableFunctions ptr set to track functions that can be inlined
2. As the ptr set is a private variable for Attributor, so in AA.initialize(), we cannot determine if the inexactly defined function can be inlined or not, so all inexactly defined functions that have alwayinline attribute will keep its state unchanged (just return from the function)
3. In CreateAAFor function, search the ptr set for the function, if the function has alwayinline attribute but cannot be inlined, we cannot analyze it (indicatePessimisticFixpoint)

[bbn]

llvm/test/Transforms/Attributor/alwaysinline.ll

22

I think it should be readnone, but I tried opt without the patch with the following example:

define void @inner1() alwaysinline {
[...]
}

and the outer1 function does not have the readnone attribute, either.
But when the function does not have alwayinline attribute:

define void @inner1() {
[....]
}

The outer1 function will have the readnone attribute

[uenoku]

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

1203

This and all other helpers should be in InformationCache.

1728

style: no brace for one line if-expr

[bbn]

Move InlineableFunctions set to InfoCache

[baziotis]

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

1113

Nit: You can use !InfoCache.InlineableFunctions.count(FnScope) (it is shorter)

[jdoerfert]

In the initialize method in question, ask the Attributor if a function is "IPO amendable". We need a new helper method for that in the Attributor. It will look at the position, linkage (via the isexact definition), and alwaysinline + inlinable "attributes". This way it we have a single location to do the lookup. It is reusable and easier to understand.

llvm/lib/Transforms/IPO/Attributor.cpp

8216

Only check this if the alwaysinline attribute is set, it is not free and otherwise not needed.

llvm/test/Transforms/Attributor/alwaysinline.ll

22

I'm confused. Take a look at https://godbolt.org/z/EsQWyN . without the linkonce we determine readnone in either case.

[bbn]

Created a helper function in Attributor which determines whether the function is IPO amendable and replaced hasExactDefinition with this helper function.

[jdoerfert]

I think this is all good, two minor comments below. Once fixed I commit it

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

641

make it const function, and appropriate below.

804

Nit: return InfoCache.InlineableFunctions.count(&F) (no braces)
or even:
return F.hasExactDefinition() || InfoCache.InlineableFunctions.count(&F);

[bbn]

• Added const for InlineableFunctions
• updated isFunctionIPOAmendable()

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

 #define LLVM_TRANSFORMS_IPO_ATTRIBUTOR_H
 
 #include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/SCCIterator.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/CGSCCPassManager.h"
 #include "llvm/Analysis/CallGraph.h"
+#include "llvm/Analysis/InlineCost.h"
 #include "llvm/Analysis/LazyCallGraph.h"
 #include "llvm/Analysis/MustExecute.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/IR/CallSite.h"
 #include "llvm/IR/ConstantRange.h"
 #include "llvm/IR/PassManager.h"
 #include "llvm/Transforms/Utils/CallGraphUpdater.h"
private:
   MustBeExecutedContextExplorer Explorer;
 
   /// Getters for analysis.
   AnalysisGetter &AG;
 
   /// The underlying CGSCC, or null if not available.
   SetVector<Function *> *CGSCC;
 
+  /// Set of inlineable functions
+  SmallPtrSet<const Function *, 8> InlineableFunctions;
+
   /// 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
struct Attributor {
   void identifyDefaultAbstractAttributes(Function &F);
 
   /// Initialize the information cache for queries regarding function \p F.
   ///
   /// This method needs to be called for all function that might be looked at
   /// through the information cache interface *prior* to looking at them.
   void initializeInformationCache(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);
+  }
+
   /// Mark the internal function \p F as live.
   ///
   /// This will trigger the identification and initialization of attributes for
   /// \p F.
   void markLiveInternalFunction(const Function &F) {
     assert(F.hasLocalLinkage() &&
            "Only local linkage is assumed dead initially.");
 
     identifyDefaultAbstractAttributes(const_cast<Function &>(F));
if (Invalidate) {
       return AA;
     }
 
     AA.initialize(*this);
 
     // We can initialize (=look at) code outside the current function set but
     // not call update because that would again spawn new abstract attributes in
     // potentially unconnected code regions (=SCCs).
     if (FnScope && !Functions.count(const_cast<Function *>(FnScope))) {
       AA.getState().indicatePessimisticFixpoint();
       return AA;
     }
 
     AA.update(*this);
 
     if (TrackDependence && AA.getState().isValidState())
       recordDependence(AA, const_cast<AbstractAttribute &>(*QueryingAA),
private:
 
   /// The information cache that holds pre-processed (LLVM-IR) information.
   InformationCache &InfoCache;
 
   /// Helper to update an underlying call graph.
   CallGraphUpdater &CGUpdater;
 
   /// Set of functions for which we modified the content such that it might
   /// impact the call graph.
   SmallPtrSet<Function *, 8> CGModifiedFunctions;
 
   /// Set if the attribute currently updated did query a non-fix attribute.
   bool QueriedNonFixAA;
 
   /// Number of iterations until the dependences between abstract attributes are
   /// recomputed.
   const unsigned DepRecomputeInterval;
virtual void initialize(Attributor &A) override {
     const Function *FnScope = IRP.getAnchorScope();
     // TODO: Not all attributes require an exact definition. Find a way to
     //       enable deduction for some but not all attributes in case the
     //       definition might be changed at runtime, see also
     //       http://lists.llvm.org/pipermail/llvm-dev/2018-February/121275.html.
     // TODO: We could always determine abstract attributes and if sufficient
     //       information was found we could duplicate the functions that do not
     //       have an exact definition.
-    if (IsFnInterface && (!FnScope || !FnScope->hasExactDefinition()))
+    if (IsFnInterface && (!FnScope || !A.isFunctionIPOAmendable(*FnScope)))
       this->getState().indicatePessimisticFixpoint();
   }
 
   /// See AbstractAttribute::manifest(...).
   ChangeStatus manifest(Attributor &A) override {
     if (isa<UndefValue>(getIRPosition().getAssociatedValue()))
       return ChangeStatus::UNCHANGED;
     SmallVector<Attribute, 4> DeducedAttrs;
     getDeducedAttributes(getAnchorValue().getContext(), DeducedAttrs);
     return IRAttributeManifest::manifestAttrs(A, getIRPosition(), DeducedAttrs);
   }
struct AAValueConstantRange : public IntegerRangeState,
   /// If \p I is nullptr, simply return a known range.
   virtual ConstantRange
   getKnownConstantRange(Attributor &A,
                         const Instruction *CtxI = nullptr) const = 0;
 
   /// Return an assumed constant for the assocaited value a program point \p
   /// CtxI.
   Optional<ConstantInt *>
-  getAssumedConstantInt(Attributor &A, const Instruction *CtxI = nullptr) const {
+  getAssumedConstantInt(Attributor &A,
+                        const Instruction *CtxI = nullptr) const {
     ConstantRange RangeV = getAssumedConstantRange(A, CtxI);
     if (auto *C = RangeV.getSingleElement())
       return cast<ConstantInt>(
           ConstantInt::get(getAssociatedValue().getType(), *C));
     if (RangeV.isEmptySet())
       return llvm::None;
     return nullptr;
   }
 
   /// Unique ID (due to the unique address)
   static const char ID;
 };
 
 } // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_IPO_FUNCTIONATTRS_H

llvm/lib/Transforms/IPO/Attributor.cpp

for (Argument &Arg : F->args()) {
         for (Instruction *RI : OpcodeInstMap[Instruction::Ret])
           ReturnInstSet.insert(cast<ReturnInst>(RI));
 
         indicateOptimisticFixpoint();
         return;
       }
     }
 
-    if (!F->hasExactDefinition())
+    if (!A.isFunctionIPOAmendable(*F))
       indicatePessimisticFixpoint();
   }
 
   /// See AbstractAttribute::manifest(...).
   ChangeStatus manifest(Attributor &A) override;
 
   /// See AbstractAttribute::getState(...).
   AbstractState &getState() override { return *this; }
static bool containsCycle(Function &F) {
   return false;
 }
 
 // Helper function that checks the function have a loop which might become an
 // endless loop
 // FIXME: Any cycle is regarded as endless loop for now.
 //        We have to allow some patterns.
 static bool containsPossiblyEndlessLoop(Function *F) {
-  return !F || !F->hasExactDefinition() || containsCycle(*F);
+  return containsCycle(*F);
 }
 
 struct AAWillReturnImpl : public AAWillReturn {
   AAWillReturnImpl(const IRPosition &IRP) : AAWillReturn(IRP) {}
 
   /// See AbstractAttribute::initialize(...).
   void initialize(Attributor &A) override {
     AAWillReturn::initialize(A);
 
     Function *F = getAssociatedFunction();
-    if (containsPossiblyEndlessLoop(F))
+    if (!F || !A.isFunctionIPOAmendable(*F) || containsPossiblyEndlessLoop(F))
       indicatePessimisticFixpoint();
   }
 
   /// See AbstractAttribute::updateImpl(...).
   ChangeStatus updateImpl(Attributor &A) override {
     auto CheckForWillReturn = [&](Instruction &I) {
       IRPosition IPos = IRPosition::callsite_function(ImmutableCallSite(&I));
       const auto &WillReturnAA = A.getAAFor<AAWillReturn>(*this, IPos);
struct AAIsDeadFloating : public AAIsDeadValueImpl {
   }
 };
 
 struct AAIsDeadArgument : public AAIsDeadFloating {
   AAIsDeadArgument(const IRPosition &IRP) : AAIsDeadFloating(IRP) {}
 
   /// See AbstractAttribute::initialize(...).
   void initialize(Attributor &A) override {
-    if (!getAssociatedFunction()->hasExactDefinition())
+    if (!A.isFunctionIPOAmendable(*getAssociatedFunction()))
       indicatePessimisticFixpoint();
   }
 
   /// See AbstractAttribute::manifest(...).
   ChangeStatus manifest(Attributor &A) override {
     ChangeStatus Changed = AAIsDeadFloating::manifest(A);
     Argument &Arg = *getAssociatedArgument();
     if (A.isValidFunctionSignatureRewrite(Arg, /* ReplacementTypes */ {}))
void initialize(Attributor &A) override {
     for (const Attribute &Attr : Attrs)
       takeKnownDerefBytesMaximum(Attr.getValueAsInt());
 
     NonNullAA = &A.getAAFor<AANonNull>(*this, getIRPosition(),
                                        /* TrackDependence */ false);
 
     const IRPosition &IRP = this->getIRPosition();
     bool IsFnInterface = IRP.isFnInterfaceKind();
-    const Function *FnScope = IRP.getAnchorScope();
-    if (IsFnInterface && (!FnScope || !FnScope->hasExactDefinition()))
+    Function *FnScope = IRP.getAnchorScope();
+    if (IsFnInterface && (!FnScope || !A.isFunctionIPOAmendable(*FnScope)))
       indicatePessimisticFixpoint();
   }
 
   /// See AbstractAttribute::getState()
   /// {
   StateType &getState() override { return *this; }
   const StateType &getState() const override { return *this; }
   /// }
struct AAAlignImpl : AAAlign {
   void initialize(Attributor &A) override {
     SmallVector<Attribute, 4> Attrs;
     getAttrs({Attribute::Alignment}, Attrs);
     for (const Attribute &Attr : Attrs)
       takeKnownMaximum(Attr.getValueAsInt());
 
     if (getIRPosition().isFnInterfaceKind() &&
         (!getAssociatedFunction() ||
-         !getAssociatedFunction()->hasExactDefinition()))
+         !A.isFunctionIPOAmendable(*getAssociatedFunction())))
       indicatePessimisticFixpoint();
   }
 
   /// See AbstractAttribute::manifest(...).
   ChangeStatus manifest(Attributor &A) override {
     ChangeStatus LoadStoreChanged = ChangeStatus::UNCHANGED;
 
     // Check for users that allow alignment annotations.
struct AANoCaptureImpl : public AANoCapture {
   /// See AbstractAttribute::initialize(...).
   void initialize(Attributor &A) override {
     if (hasAttr(getAttrKind(), /* IgnoreSubsumingPositions */ true)) {
       indicateOptimisticFixpoint();
       return;
     }
     Function *AnchorScope = getAnchorScope();
     if (isFnInterfaceKind() &&
-        (!AnchorScope || !AnchorScope->hasExactDefinition())) {
+        (!AnchorScope || !A.isFunctionIPOAmendable(*AnchorScope))) {
       indicatePessimisticFixpoint();
       return;
     }
 
     // You cannot "capture" null in the default address space.
     if (isa<ConstantPointerNull>(getAssociatedValue()) &&
         getAssociatedValue().getType()->getPointerAddressSpace() == 0) {
       indicateOptimisticFixpoint();
void initialize(Attributor &A) override {
     // initialize of the base class here.
     bool HasByVal =
         IRP.hasAttr({Attribute::ByVal}, /* IgnoreSubsumingPositions */ true);
     getKnownStateFromValue(IRP, getState(),
                            /* IgnoreSubsumingPositions */ HasByVal);
 
     // Initialize the use vector with all direct uses of the associated value.
     Argument *Arg = getAssociatedArgument();
-    if (!Arg || !Arg->getParent()->hasExactDefinition()) {
+    if (!Arg || !A.isFunctionIPOAmendable(*(Arg->getParent()))) {
       indicatePessimisticFixpoint();
     } else {
       // Initialize the use vector with all direct uses of the associated value.
       for (const Use &U : Arg->uses())
         Uses.insert(&U);
     }
   }
 

 /// AAMemoryBehavior attribute for call sites.
 struct AAMemoryBehaviorCallSite final : AAMemoryBehaviorImpl {
   AAMemoryBehaviorCallSite(const IRPosition &IRP) : AAMemoryBehaviorImpl(IRP) {}
 
   /// See AbstractAttribute::initialize(...).
   void initialize(Attributor &A) override {
     AAMemoryBehaviorImpl::initialize(A);
     Function *F = getAssociatedFunction();
-    if (!F || !F->hasExactDefinition())
+    if (!F || !A.isFunctionIPOAmendable(*F))
       indicatePessimisticFixpoint();
   }
 
   /// See AbstractAttribute::updateImpl(...).
   ChangeStatus updateImpl(Attributor &A) override {
     // TODO: Once we have call site specific value information we can provide
     //       call site specific liveness liveness information and then it makes
     //       sense to specialize attributes for call sites arguments instead of

 /// AAMemoryLocation attribute for call sites.
 struct AAMemoryLocationCallSite final : AAMemoryLocationImpl {
   AAMemoryLocationCallSite(const IRPosition &IRP) : AAMemoryLocationImpl(IRP) {}
 
   /// See AbstractAttribute::initialize(...).
   void initialize(Attributor &A) override {
     AAMemoryLocationImpl::initialize(A);
     Function *F = getAssociatedFunction();
-    if (!F || !F->hasExactDefinition())
+    if (!F || !A.isFunctionIPOAmendable(*F))
       indicatePessimisticFixpoint();
   }
 
   /// See AbstractAttribute::updateImpl(...).
   ChangeStatus updateImpl(Attributor &A) override {
     // TODO: Once we have call site specific value information we can provide
     //       call site specific liveness liveness information and then it makes
     //       sense to specialize attributes for call sites arguments instead of
for (Instruction &I : instructions(&F)) {
     case Instruction::Ret:
       IsInterestingOpcode = true;
     }
     if (IsInterestingOpcode)
       InstOpcodeMap[I.getOpcode()].push_back(&I);
     if (I.mayReadOrWriteMemory())
       ReadOrWriteInsts.push_back(&I);
   }
+
+  if (F.hasFnAttribute(Attribute::AlwaysInline) &&
+      isInlineViable(F).isSuccess())
+    InfoCache.InlineableFunctions.insert(&F);
 }
 
 void Attributor::recordDependence(const AbstractAttribute &FromAA,
                                   const AbstractAttribute &ToAA,
                                   DepClassTy DepClass) {
   if (FromAA.getState().isAtFixpoint())
     return;
 

llvm/test/Transforms/Attributor/alwaysinline.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -attributor -attributor-disable=false -attributor-annotate-decl-cs -attributor-max-iterations=5 -S < %s | FileCheck %s --check-prefix=CHECK
+;
+; When a function is marked `alwaysinline` and is able to be inlined,
+; we can IPO its boundaries
+
+; the function is not exactly defined, and marked alwaysinline and can be inlined,
+; so the function can be analyzed
+; CHECK: Function Attrs: alwaysinline nofree nosync nounwind readnone willreturn
+define linkonce void @inner1() alwaysinline {
+; CHECK-LABEL: @inner1(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    ret void
+;
+entry:
+  ret void
+}
+
+; CHECK: Function Attrs: nofree nosync nounwind readnone willreturn
+define void @outer1() {
+; CHECK-LABEL: @outer1(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    ret void
+;
+entry:
+  call void @inner1()
+  ret void
+}
+
+; The function is not alwaysinline and is not exactly defined
+; so it will not be analyzed
+; CHECK-NOT: Function Attrs:
+define linkonce i32 @inner2() {
+; CHECK-LABEL: @inner2(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    ret i32 1
+;
+entry:
+  ret i32 1
+}
+
+; CHECK-NOT: Function Attrs
+define i32 @outer2() {
+; CHECK-LABEL: @outer2(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[R:%.*]] = call i32 @inner2() #2
+; CHECK-NEXT:    ret i32 [[R]]
+;
+entry:
+  %r = call i32 @inner2() alwaysinline
+  ret i32 %r
+}
+
+; This function cannot be inlined although it is marked alwaysinline
+; it is `unexactly defined` and alwaysinline but cannot be inlined.
+; so it will not be analyzed
+; CHECK: Function Attrs:
+; CHECK-NOT: nofree nosync nounwind readnone
+define linkonce i32 @inner3(i8* %addr) alwaysinline {
+; CHECK-LABEL: @inner3(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    indirectbr i8* [[ADDR:%.*]], [label [[ONE:%.*]], label %two]
+; CHECK:       one:
+; CHECK-NEXT:    ret i32 42
+; CHECK:       two:
+; CHECK-NEXT:    ret i32 44
+;
+entry:
+  indirectbr i8* %addr, [ label %one, label %two ]
+
+one:
+  ret i32 42
+
+two:
+  ret i32 44
+}
+
+; CHECK-NOT: Function Attrs:
+define i32 @outer3(i32 %x) {
+; CHECK-LABEL: @outer3(
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[X:%.*]], 42
+; CHECK-NEXT:    [[ADDR:%.*]] = select i1 [[CMP]], i8* blockaddress(@inner3, [[ONE:%.*]]), i8* blockaddress(@inner3, [[TWO:%.*]])
+; CHECK-NEXT:    [[CALL:%.*]] = call i32 @inner3(i8* [[ADDR]])
+; CHECK-NEXT:    ret i32 [[CALL]]
+;
+  %cmp = icmp slt i32 %x, 42
+  %addr = select i1 %cmp, i8* blockaddress(@inner3, %one), i8* blockaddress(@inner3, %two)
+  %call = call i32 @inner3(i8* %addr)
+  ret i32 %call
+}