[Attributor] Deduce "nofree" function attribute

[uenoku]

Summary

Deduce "nofree" function attribute. A more concise description of "nofree" is on D49165.

[lebedev.ri]

Are langref changes missing?
How do these attributes get documented there?

llvm/include/llvm/IR/Attributes.td

205

Can this please be more explanatory?
I can read this as "free() isn't being called", "all calls here are non-free (as in non-cheap)" etc

llvm/lib/Transforms/IPO/Attributor.cpp

186

StringRef

1089

Hm, there is no .empty() ?

[uenoku]

@lebedev.ri.

Are langref changes missing? How do these attributes get documented there?

Langref and concise description are on D49165. This patch goes on the assumption that D49165 will be rebased and upstreamed.
Please excuse my lack of explanation.

[jdoerfert]

Please make this depend on the no-free patch by @hfinkel. We should also see if we extract the definition from there or if he plans to work on that patch further.

Some comments inlined.

I don't know why we would need TLI here but could you split the addition of it so we have it for the future.

llvm/lib/Transforms/IPO/Attributor.cpp

187

We want an llvm::StringSwitch here.

We could also move the whole bookkeeping into the AbstractAttributes. That might actually be nicer.

724

Please add bool isAssumedNoFree() and bool isKnownNoFree().

759

You can directly get the AnchorScope

771

I don't see why we'd need this conditional (and the Realloc check).

800

No need for the assert, and if you want one, add a message.

801

You can make safe indention if you continue for nofree call sites. Though, I don't see why we should check the attribute in the first place. The following check is what we want.

803

Please add || !NoFreeAA->isAssumedNoFree() for concistency.

Revert the condition for less indented code.

810

There is no fixpoint reached here, at least not if getAAFor was called at least once! Just remove the line and let the framework determine this for you.

[uenoku]

Sorry, I was quite mistaken about Attributor. I removed TLI and followed comments.

[jdoerfert]

In D62687#1523832, @uenoku wrote:

Sorry, I was quite mistaken about Attributor. I removed TLI and followed comments.

You misunderstood, there is absolutely no need to apologize. I like the patch and it is totally normal that I have comments now.
This is the first patch to a new framework and I have a lot of thoughts in my head how the code should look like/interact with the rest.

The patch is almost ready as far as I can tell, I added some (mostly minor) comments though.

Did you actually run the pass and try it on the test case you have? The changes to the test case should be part of this patch (pretend the test cases are already in tree).

llvm/lib/Transforms/IPO/Attributor.cpp

717

If you make it a struct you don't need the public anymore.

732

Comment and new line pls.

752

Comments please.

770

Do we have any intrinsic that might free memory? I would need to double check but I don't think we have one.

801

My other two comments were confusing and I should have explained this better.

The idea (I have) is:
Information should be determined through other attributes if possible. That way we do not need to look at the IR in different places and also ask if an attribute exist and what the status is. That would mean do not look at the IR attributes (through the CallSite). I also confused you with the isAssumedNoFree as it seems. I did want that in addition to the two checks you had, so !NoFreeAA, !NoFreeAA->getState().hasValidState(), and !NoFreeAA->isAssumedNoFree(), even though the last two are equivalent it makes it easier to read and consistent with more complex attributes.

976

Please add an assert here to make sure we did not miss any CallBase instruction opcode.

[uenoku]

Assume that all intrinsic function wouldn't free memory.

[uenoku]

llvm/lib/Transforms/IPO/Attributor.cpp

770

I think so too. However, I have one concern. There are some intrinsic related to GC and I can not be sure whether these intrinsic wouldn't free memory.

801

I have a question about this.
As you said I changed not to look IR attributes. Then I don't know how to deal with a function declaration like this:

declare void @nofree_function() "nofree" 

define void @call_nofree_function() {
    tail call void @nofree_function()
    ret void
}

[jdoerfert]

Almost there, partially because I didn't think certain problems through, see inlined comments.

The test changes are still missing.

llvm/lib/Transforms/IPO/Attributor.cpp

770

That is a good point. Let's do the following:

• Do not look at intrinsic here as at all so we are sound for sure (we should have a test for that!)
• Annotate intrinsics in their ".td" file definition (different patch later on)

801

Good point, very good point. Let's agree that I was wrong for now and you add back the ImmutableCallSite attribute check.

[uenoku]

Assume that all intrinsic would free memory and use IR Attribute.

[uenoku]

The test changes are still missing.

Oh, I missed it. I'm now writing this but I'm in trouble.

In D62313, you said that it is preferable to write a test like this:

; CHECK:       Function Attrs: noinline norecurse nounwind readnone uwtable
; CHECK-NEXT:     define double* @ret_undef_arg_undef(i32* readnone %b)

However, I think this format would not work for string attribute, isn't it?

[jdoerfert]

In D62687#1526078, @uenoku wrote:

The test changes are still missing.

Oh, I missed it. I'm now writing this but I'm in trouble.

In D62313, you said that it is preferable to write a test like this:

; CHECK:       Function Attrs: noinline norecurse nounwind readnone uwtable
; CHECK-NEXT:     define double* @ret_undef_arg_undef(i32* readnone %b)

However, I think this format would not work for string attribute, isn't it?

I honestly do not know, if it is not, you need to choose a way that works. If you find that difficult, let me know. (Do not delete the checks but remove the CHECK part or rename it).

[uenoku]

Add test changes. A few test cases are added.

[uenoku]

Fix patch.

[jdoerfert]

Last comments wrt the test cases. I hope D62784 is uncontroversial and we can use the Function Attr: check lines. That is the last change I'd like to see.

llvm/test/Transforms/FunctionAttrs/nofree.ll

32 ↗

(On Diff #202553)

Assuming I can land D62784, you can check for "nofree" as you do for the FNATTR attributes.

Use -NEXT: for the define lines so you make sure that you check the attributes of that definition.

Use -NOT: nofree for the negative test cases to make sure we do not derive it.

174 ↗

(On Diff #202553)

Great!

[uenoku]

Fix test format and some typo.

[uenoku]

I hope D62784 is uncontroversial and we can use the Function Attr: check lines.

Thanks. It works.

[jdoerfert]

This depends on three other patches now but once they are in, this one can go in as well. LGTM.

[jdoerfert]

Why does this depend on D63046?

[uenoku]

Why does this depend on D63046?

I included "nofree" attribute in D63046 test change for now(I thought it is convenient for merging). So I regarded this as a parent just in case.

[jdoerfert]

Can you make the test use an enum version, thus nofree not "nofree".

llvm/include/llvm/IR/Attributes.td

206

Remove this line please.

[uenoku]

• use enum attribute
• rename test file

[uenoku]

This comment was removed by uenoku.

[jdoerfert]

Once the test file is in, rebase this one and make sure ninja check-all works before you commit it. Also, there is a leftover FIXME in the code.

llvm/lib/Transforms/IPO/Attributor.cpp

455

Leftover comment.

[uenoku]

Add tests and check-all passed.

llvm/include/llvm/Analysis/MemoryBuiltins.h

 bool isMallocOrCallocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
                             bool LookThroughBitCast = false);
 
 /// Tests if a value is a call or invoke to a library function that
 /// allocates memory (either malloc, calloc, or strdup like).
 bool isAllocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
                    bool LookThroughBitCast = false);
 
+/// Tests if a value is a call or invoke to a library function that
+/// reallocates memory (e.g., realloc).
+bool isReallocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
+                     bool LookThroughBitCast = false);
+
 //===----------------------------------------------------------------------===//
 //  malloc Call Utility Functions.
 //
 
 /// extractMallocCall - Returns the corresponding CallInst if the instruction
 /// is a malloc call.  Since CallInst::CreateMalloc() only creates calls, we
 /// ignore InvokeInst here.
 const CallInst *extractMallocCall(const Value *I, const TargetLibraryInfo *TLI);

llvm/include/llvm/IR/Attributes.td

 def UWTable : EnumAttr<"uwtable">;
 
 /// Function only writes to memory.
 def WriteOnly : EnumAttr<"writeonly">;
 
 /// Zero extended before/after call.
 def ZExt : EnumAttr<"zeroext">;
 
+/// No Free Call
+/// This is an experimental attribute.
+def NoFree : StrBoolAttr<"nofree">;
+
 /// Target-independent string attributes.
 def LessPreciseFPMAD : StrBoolAttr<"less-precise-fpmad">;
 def NoInfsFPMath : StrBoolAttr<"no-infs-fp-math">;
 def NoNansFPMath : StrBoolAttr<"no-nans-fp-math">;
 def UnsafeFPMath : StrBoolAttr<"unsafe-fp-math">;
 def NoJumpTables : StrBoolAttr<"no-jump-tables">;
 def ProfileSampleAccurate : StrBoolAttr<"profile-sample-accurate">;
 

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

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, InformationCache &InfoCache,
-      DenseSet</* Attribute::AttrKind */ unsigned> *Whitelist = nullptr);
+      TargetLibraryInfo & ,
+      DenseSet</* Attribute::AttrKind */ unsigned> *Whitelist = nullptr
+      );
 
 private:
   /// The set of all abstract attributes.
   ///{
   using AAVector = SmallVector<AbstractAttribute *, 64>;
   AAVector AllAbstractAttributes;
   ///}
 

llvm/lib/Analysis/MemoryBuiltins.cpp

 
 /// Tests if a value is a call or invoke to a library function that
 /// allocates memory (either malloc, calloc, or strdup like).
 bool llvm::isAllocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
                          bool LookThroughBitCast) {
   return getAllocationData(V, AllocLike, TLI, LookThroughBitCast).hasValue();
 }
 
+/// Tests if a value is a call or invoke to a library function that
+/// reallocates memory (e.g., realloc).
+bool llvm::isReallocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
+                           bool LookThroughBitCast) {
+  return getAllocationData(V, ReallocLike, TLI, LookThroughBitCast).hasValue();
+}
+
 /// extractMallocCall - Returns the corresponding CallInst if the instruction
 /// is a malloc call.  Since CallInst::CreateMalloc() only creates calls, we
 /// ignore InvokeInst here.
 const CallInst *llvm::extractMallocCall(const Value *I,
                                         const TargetLibraryInfo *TLI) {
   return isMallocLikeFn(I, TLI) ? dyn_cast<CallInst>(I) : nullptr;
 }
 

llvm/lib/Transforms/IPO/Attributor.cpp

 #include "llvm/Transforms/IPO/Attributor.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/CallGraph.h"
 #include "llvm/Analysis/CallGraphSCCPass.h"
 #include "llvm/Analysis/GlobalsModRef.h"
+#include "llvm/Analysis/MemoryBuiltins.h"
 #include "llvm/IR/Argument.h"
 #include "llvm/IR/Attributes.h"
 #include "llvm/IR/InstIterator.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 #include <cassert>

 STATISTIC(NumAttributesManifested,
           "Number of abstract attributes manifested in IR");
 
 STATISTIC(NumFnUniqueReturned, "Number of function with unique return");
 STATISTIC(NumFnKnownReturns, "Number of function with known return values");
 STATISTIC(NumFnArgumentReturned,
           "Number of function arguments marked returned");
 
+STATISTIC(NumFnNoFree, "Number of function marked nofree");
+
 // TODO: Determine a good default value.
 //
 // In the LLVM-TS and SPEC2006, 32 seems to not induce compile time overheads
 // (when run with the first 5 abstract attributes). The results also indicate
 // that we never reach 32 iterations but always find a fixpoint sooner.
 //
 // This will become more evolved once we perform two interleaved fixpoint
 // iterations: bottom-up and top-down.

 };
 
 /// Helper to adjust the statistics.
 static void bookkeeping(AbstractAttribute::ManifestPosition MP,
                         const Attribute &Attr) {
   if (!AreStatisticsEnabled())
     return;
 
+  if (Attr.isStringAttribute()) {
+    auto StringAttr = Attr.getKindAsString();
+    if (StringAttr == "nofree") {
+      NumFnNoFree++;
+    }
+    return;
+  }
+
   if (!Attr.isEnumAttribute())
     return;
   switch (Attr.getKindAsEnum()) {
   case Attribute::Returned:
     NumFnArgumentReturned++;
     return;
   default:
     return;
static void collectValuesRecursively(
     gernericValueTraversal(V, UnusedBool, FollowValueCB, VisitValueCB);
   }
 
 public:
   /// See AbstractAttribute::AbstractAttribute(...).
   AAReturnedValuesImpl(Function &F, InformationCache &InfoCache)
       : AAReturnedValues(F, InfoCache) {
     // We do not have an associated argument yet.
     AssociatedVal = nullptr;
   }
 
   /// See AbstractAttribute::initialize(...).
   void initialize(Attributor &A) override {
     Function &F = cast<Function>(getAnchoredValue());
 
     // The map from instruction opcodes to those instructions in the function.
     auto &OpcodeInstMap = InfoCache.getOpcodeInstMapForFunction(F);
ChangeStatus AAReturnedValuesImpl::updateImpl(Attributor &A) {
   if (!HasCallSite) {
     indicateOptimisticFixpoint();
     return ChangeStatus::CHANGED;
   }
 
   return Changed;
 }
 
+/// ------------------------ No-Free Attributes ----------------------------
+
+class AANoFreeFunction final : public AbstractAttribute, BooleanState {
+  TargetLibraryInfo &TLI;
+
+public:
+  /// See AbstractAttribute::AbstractAttribute(...).
+  AANoFreeFunction(Function &F, InformationCache &InfoCache,
+                   TargetLibraryInfo &TLI)
+      : AbstractAttribute(F, InfoCache), TLI(TLI) {}
+
+  /// See AbstractAttribute::getState()
+  ///{
+  AbstractState &getState() override { return *this; }
+  const AbstractState &getState() const override { return *this; }
+  ///}
+
+  /// See AbstractAttribute::getManifestPosition().
+  virtual ManifestPosition getManifestPosition() const override {
+    return MP_FUNCTION;
+  }
+  virtual const std::string getAsStr() const override {
+    return getAssumed() ? "nofree" : "may-free";
+  }
+
+  /// See AbstractAttribute::updateImpl(...).
+  virtual ChangeStatus updateImpl(Attributor &A) override;
+
+  /// Return the deduced attributes in \p Attrs.
+  virtual void
+  getDeducedAttributes(SmallVectorImpl<Attribute> &Attrs) const override {
+    LLVMContext &Ctx = AnchoredVal.getContext();
+    Attrs.emplace_back(Attribute::get(Ctx, "nofree"));
+  }
+
+  virtual Attribute::AttrKind getAttrKind() const override {
+    return Attribute::None;
+  }
+
+  // FIXME: I tried ((AttrKind) - 2) for ID but I got exception so I use Attribute::None + 1 for now.
+  static constexpr Attribute::AttrKind ID =
+      Attribute::AttrKind(Attribute::None + 1);
+};
+
+ChangeStatus AANoFreeFunction::updateImpl(Attributor &A) {
+    Function &F = cast<Function>(getAnchoredValue());
+
+    // The map from instruction opcodes to those instructions in the function.
+    auto &OpcodeInstMap = InfoCache.getOpcodeInstMapForFunction(F);
+
+    for (unsigned Opcode :
+         {(unsigned)Instruction::Invoke, (unsigned)Instruction::CallBr,
+          (unsigned)Instruction::Call}) {
+      for (Instruction *I : OpcodeInstMap[Opcode]) {
+        if (isFreeCall(I, &TLI) || isReallocLikeFn(I, &TLI)) {
+          indicatePessimisticFixpoint();
+          return ChangeStatus::CHANGED;
+        }
+        if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
+          switch (II->getIntrinsicID()) {
+          // TODO: Enumerate all nofree intrinsic functions.
+          //       I think we need to deal with intrinsic function in a more appropriate way.
+
+          case Intrinsic::cos:
+          case Intrinsic::donothing:
+          case Intrinsic::exp:
+          case Intrinsic::exp2:
+          case Intrinsic::expect:
+          case Intrinsic::fabs:
+          case Intrinsic::floor:
+          case Intrinsic::log:
+          case Intrinsic::log10:
+          case Intrinsic::log2:
+          case Intrinsic::memset:
+          case Intrinsic::memcpy:
+          case Intrinsic::memmove:
+          case Intrinsic::pow:
+          case Intrinsic::powi:
+          case Intrinsic::sin:
+          case Intrinsic::sqrt:
+            continue;
+          default:
+            break;
+          }
+        }
+        ImmutableCallSite ICS(I);
+        assert(ICS);
+        if (!ICS.hasFnAttr("nofree")) {
+          auto *NoFreeAA = A.getAAFor<AANoFreeFunction>(*this, *I);
+          if (!NoFreeAA || !NoFreeAA->isValidState()) {
+            indicatePessimisticFixpoint();
+            return ChangeStatus::CHANGED;
+          }
+        }
+      }
+    }
+    indicateOptimisticFixpoint();
+    return ChangeStatus::UNCHANGED;
+  }
+
 /// ----------------------------------------------------------------------------
 ///                               Attributor
 /// ----------------------------------------------------------------------------
 
 ChangeStatus Attributor::run() {
   // Initialize all abstract attributes.
   for (AbstractAttribute *AA : AllAbstractAttributes)
     AA->initialize(*this);
ChangeStatus Attributor::run() {
 
   NumAttributesManifested += NumManifested;
   NumAttributesValidFixpoint += NumAtFixpoint;
 
   return ManifestChange;
 }
 
 void Attributor::identifyDefaultAbstractAttributes(
-    Function &F, InformationCache &InfoCache,
+    Function &F, InformationCache &InfoCache, TargetLibraryInfo &TLI,
     DenseSet</* Attribute::AttrKind */ unsigned> *Whitelist) {
 
   // Return attributes are only appropriate if the return type is non void.
   Type *ReturnType = F.getReturnType();
   if (!ReturnType->isVoidTy()) {
     // Argument attribute "returned" --- Create only one per function even
     // though it is an argument attribute.
     if (!Whitelist || Whitelist->count(AAReturnedValues::ID))
       registerAA(*new AAReturnedValuesImpl(F, InfoCache));
   }
 
+  // Every function might be "no-free".
+  registerAA(*new AANoFreeFunction(F, InfoCache, TLI));
+
   // Walk all instructions to find more attribute opportunities and also
   // interesting instructions that might be queried by abstract attributes
   // during their initialization or update.
   auto &ReadOrWriteInsts = InfoCache.FuncRWInstsMap[&F];
   auto &InstOpcodeMap = InfoCache.FuncInstOpcodeMap[&F];
 
   for (Instruction &I : instructions(&F)) {
     bool IsInterestingOpcode = false;
 
     switch (I.getOpcode()) {
     default:
       break;
     case Instruction::Ret: // ReturnInst are interesting for AAReturnedValues.
+    case Instruction::Call:
+    case Instruction::CallBr:
+    case Instruction::Invoke:
       IsInterestingOpcode = true;
     }
     if (IsInterestingOpcode)
       InstOpcodeMap[I.getOpcode()].push_back(&I);
     if (I.mayReadOrWriteMemory())
       ReadOrWriteInsts.push_back(&I);
   }
 }
OS << "[" << getManifestPosition() << "][" << getAsStr() << "]["
      << AnchoredVal.getName() << "]";
 }
 ///}
 
 /// ----------------------------------------------------------------------------
 ///                       Pass (Manager) Boilerplate
 /// ----------------------------------------------------------------------------
 
-static bool runAttributorOnSCC(SmallVectorImpl<Function *> &SCC) {
+static bool runAttributorOnSCC(SmallVectorImpl<Function *> &SCC,
+                               TargetLibraryInfo &TLI) {
   if (DisableAttributor)
     return false;
 
   LLVM_DEBUG(dbgs() << "[Attributor] Run on SCC with " << SCC.size()
                     << " functions.\n");
 
   // Create an Attributor and initially empty information cache that is filled
   // while we identify default attribute opportunities.
if (F->hasFnAttribute(Attribute::Naked) ||
       continue;
 
     NumFnWithExactDefinition++;
 
     assert(!F->isDeclaration() && "Expected a definition not a declaration!");
 
     // Populate the Attributor with abstract attribute opportunities in the
     // function and the information cache with IR information.
-    A.identifyDefaultAbstractAttributes(*F, InfoCache);
+    A.identifyDefaultAbstractAttributes(*F, InfoCache, TLI);
   }
 
   return A.run() == ChangeStatus::CHANGED;
 }
 
 PreservedAnalyses AttributorPass::run(LazyCallGraph::SCC &C,
-                                      CGSCCAnalysisManager &, LazyCallGraph &,
-                                      CGSCCUpdateResult &) {
+                                      CGSCCAnalysisManager &AM,
+                                      LazyCallGraph &CG, CGSCCUpdateResult &) {
 
   SmallVector<Function *, 16> SCCFunctions;
   for (LazyCallGraph::Node &N : C) {
     Function &Fn = N.getFunction();
     if (!Fn.isDeclaration())
       SCCFunctions.push_back(&Fn);
   }
 
-  if (runAttributorOnSCC(SCCFunctions))
+  const ModuleAnalysisManager &MAM =
+      AM.getResult<ModuleAnalysisManagerCGSCCProxy>(C, CG).getManager();
+  assert(C.size() > 0 && "Cannot handle an empty SCC!");
+  Module &M = *C.begin()->getFunction().getParent();
+  auto &TLI = *MAM.getCachedResult<TargetLibraryAnalysis>(M);
+
+  if (runAttributorOnSCC(SCCFunctions, TLI))
     return PreservedAnalyses::none();
   return PreservedAnalyses::all();
 }
 
 namespace {
 
 struct AttributorLegacyPass : public CallGraphSCCPass {
   static char ID;
 
   AttributorLegacyPass() : CallGraphSCCPass(ID) {
     initializeAttributorLegacyPassPass(*PassRegistry::getPassRegistry());
   }
 
   bool runOnSCC(CallGraphSCC &SCC) override {
     if (skipSCC(SCC))
       return false;
 
     SmallVector<Function *, 16> SCCFunctions;
     for (CallGraphNode *I : SCC)
       if (Function *Fn = I->getFunction())
         if (!Fn->isDeclaration())
           SCCFunctions.push_back(Fn);
 
-    return runAttributorOnSCC(SCCFunctions);
+    auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
+
+    return runAttributorOnSCC(SCCFunctions, TLI);
   }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.setPreservesCFG();
     AU.addPreserved<CallGraphWrapperPass>();
+    AU.addRequired<TargetLibraryInfoWrapperPass>();
     CallGraphSCCPass::getAnalysisUsage(AU);
   }
 };
 
 } // end anonymous namespace
 
 Pass *llvm::createAttributorLegacyPass() { return new AttributorLegacyPass(); }
 
 char AttributorLegacyPass::ID = 0;
 INITIALIZE_PASS_BEGIN(AttributorLegacyPass, "attributor",
                       "Deduce and propagate attributes", false, false)
+INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
 INITIALIZE_PASS_END(AttributorLegacyPass, "attributor",
                     "Deduce and propagate attributes", false, false)