[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

1717

Is FnScope always nonnull here?

[bbn]

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

1717

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

[jdoerfert]

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

1726

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

llvm/test/Transforms/Attributor/alwaysinline.ll

78

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

1192

This and all other helpers should be in InformationCache.

1717

style: no brace for one line if-expr

[bbn]

Move InlineableFunctions set to InfoCache

[baziotis]

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

1102

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 ↗

(On Diff #248708)

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.

801

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:
 
   /// Getters for analysis.
   AnalysisGetter &AG;
 
   /// The underlying CGSCC, or null if not available.
   SetVector<Function *> *CGSCC;
 
   /// 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
 /// fixpoint iteration) as well as helper functions for the deduction of
 /// (LLVM-IR) attributes. However, also other code properties can be deduced,
struct Attributor {
   /// 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));
   }
 
   /// Record that \p U is to be replaces with \p NV after information was
   /// manifested. This also triggers deletion of trivially dead istructions.
   bool changeUseAfterManifest(Use &U, Value &NV) {
     Value *&V = ToBeChangedUses[&U];
     if (V && (V->stripPointerCasts() == NV.stripPointerCasts() ||
               isa_and_nonnull<UndefValue>(V)))
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;
struct IRAttribute : public IRPosition, public Base {
   virtual void initialize(Attributor &A) override {
     const IRPosition &IRP = this->getIRPosition();
     if (isa<UndefValue>(IRP.getAssociatedValue()) || hasAttr(getAttrKind())) {
       this->getState().indicateOptimisticFixpoint();
       return;
     }
 
     bool IsFnInterface = IRP.isFnInterfaceKind();
-    const Function *FnScope = IRP.getAnchorScope();
+    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 || !FnScope->hasExactDefinition())) {
+      if (FnScope->hasFnAttribute(Attribute::AlwaysInline)) {
+        // check if it is OK to inline, if so, do fix-point analysis for the
+        // function
+        if (isInlineViable(*FnScope).isSuccess())
+          return;
+      }
       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/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=ATTRIBUTOR
+;
+; When a function is marked `alwaysinline` and is able to be inlined,
+; we can IPO its boundaries
+
+; The function can be removed safely because it has external linkage
+; so this will be inlined, although the function is not exactly
+; defined.
+; ATTRIBUTOR: Function Attrs: alwaysinline nofree nosync nounwind readnone
+define linkonce void @inner1() alwaysinline {
+; ATTRIBUTOR-LABEL: @inner1(
+; ATTRIBUTOR-NEXT:  entry:
+; ATTRIBUTOR-NEXT:    ret void
+;
+entry:
+  ret void
+}
+
+; ATTRIBUTOR: Function Attrs: nofree nosync nounwind
+define void @outer1() {
+; ATTRIBUTOR-LABEL: @outer1(
+; ATTRIBUTOR-NEXT:  entry:
+; ATTRIBUTOR-NEXT:    ret void
+;
+entry:
+  call void @inner1()
+  ret void
+}
+
+; The function is not alwaysinline and is external
+define i32 @inner2() {
+; ATTRIBUTOR-LABEL: @inner2(
+; ATTRIBUTOR-NEXT:  entry:
+; ATTRIBUTOR-NEXT:    ret i32 1
+;
+entry:
+  ret i32 1
+}
+
+define i32 @outer2() {
+; ATTRIBUTOR-LABEL: @outer2(
+; ATTRIBUTOR-NEXT:  entry:
+; ATTRIBUTOR-NEXT:    ret i32 1
+;
+entry:
+  %r = call i32 @inner2() alwaysinline
+  ret i32 %r
+}
+
+; This function cannot be inlined although it is marked alwaysinline
+declare i32 @a() returns_twice
+
+define internal i32 @inner3() alwaysinline {
+; ATTRIBUTOR-LABEL: @inner3(
+; ATTRIBUTOR-NEXT:  entry:
+; ATTRIBUTOR-NEXT:    [[CALL:%.*]] = call i32 @a() #3
+; ATTRIBUTOR-NEXT:    [[ADD:%.*]] = add nsw i32 1, [[CALL]]
+; ATTRIBUTOR-NEXT:    ret i32 [[ADD]]
+;
+entry:
+  %call = call i32 @a() returns_twice
+  %add = add nsw i32 1, %call
+  ret i32 %add
+}
+
+define i32 @outer3() {
+; ATTRIBUTOR-LABEL: @outer3(
+; ATTRIBUTOR-NEXT:  entry:
+; ATTRIBUTOR-NEXT:    [[CALL:%.*]] = call i32 @inner3()
+; ATTRIBUTOR-NEXT:    [[ADD:%.*]] = add nsw i32 1, [[CALL]]
+; ATTRIBUTOR-NEXT:    ret i32 [[ADD]]
+;
+entry:
+  %call = call i32 @inner3()
+  %add = add nsw i32 1, %call
+  ret i32 %add
+}