[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

185

StringRef

1083

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

186

We want an llvm::StringSwitch here.

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

723

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

758

You can directly get the AnchorScope

770

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

799

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

800

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.

802

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

Revert the condition for less indented code.

809

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

716

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

731

Comment and new line pls.

751

Comments please.

769

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

800

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.

971

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

769

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.

800

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

769

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)

800

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

454

Leftover comment.

[uenoku]

Add tests and check-all passed.

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/lib/Transforms/IPO/Attributor.cpp

 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()) {
+    StringRef 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 {
+public:
+  /// See AbstractAttribute::AbstractAttribute(...).
+  AANoFreeFunction(Function &F, InformationCache &InfoCache)
+      : AbstractAttribute(F, InfoCache) {}
+
+  /// 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"));
+  }
+
+  /// See AbstractAttribute::getAttrKind().
+  virtual Attribute::AttrKind getAttrKind() const override {
+    return Attribute::None;
+  }
+
+  bool isAssumedNoFree() const { return getAssumed(); }
+  bool isKnownNoFree() const { return getKnown(); }
+
+  // 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 = getAnchorScope();
+
+  // 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 (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);
+      auto *NoFreeAA = A.getAAFor<AANoFreeFunction>(*this, *I);
+      if ((!NoFreeAA || !NoFreeAA->isAssumedNoFree()) &&
+          !ICS.hasFnAttr("nofree")) {
+        indicatePessimisticFixpoint();
+        return ChangeStatus::CHANGED;
+      }
+    }
+  }
+  return ChangeStatus::UNCHANGED;
+}
+
 /// ----------------------------------------------------------------------------
 ///                               Attributor
 /// ----------------------------------------------------------------------------
 
 ChangeStatus Attributor::run() {
   // Initialize all abstract attributes.
   for (AbstractAttribute *AA : AllAbstractAttributes)
     AA->initialize(*this);
 
void Attributor::identifyDefaultAbstractAttributes(
   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));
+
   // 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);
   }
 }
PreservedAnalyses AttributorPass::run(LazyCallGraph::SCC &C,
   for (LazyCallGraph::Node &N : C) {
     Function &Fn = N.getFunction();
     if (!Fn.isDeclaration())
       SCCFunctions.push_back(&Fn);
   }
 
   if (runAttributorOnSCC(SCCFunctions))
     return PreservedAnalyses::none();
   return PreservedAnalyses::all();
 }
 
 namespace {
 
 struct AttributorLegacyPass : public CallGraphSCCPass {
   static char ID;
 
   AttributorLegacyPass() : CallGraphSCCPass(ID) {