Let FuncAttrs infer the 'returned' argument attribute

[hfinkel]

Summary

A function can have one argument with the 'returned' attribute, indicating that the associated argument is always the return value of the function. Add FuncAttrs inference logic.

I intend to make the optimizer smarter about looking through functions with a returned parameter (in support of the llvm.noalias intrinsic). We might as well let generic functions with this property benefit as well.

[jmolloy]

LGTM!

[majnemer]

I'd update the langref, it currently says:

This is an optimization hint to the code generator when generating the caller

lib/Transforms/IPO/FunctionAttrs.cpp

494–495 ↗

(On Diff #63431)

Is this comment correct?

508 ↗

(On Diff #63431)

auto *Ret

[hfinkel]

In D22202#479680, @majnemer wrote:

I'd update the langref, it currently says:

This is an optimization hint to the code generator when generating the caller

Yes; that part is actually already out-of-date. I'll post a separate patch for that.

[hfinkel]

In D22202#479687, @hfinkel wrote:

In D22202#479680, @majnemer wrote:

I'd update the langref, it currently says:

This is an optimization hint to the code generator when generating the caller

Yes; that part is actually already out-of-date. I'll post a separate patch for that.

Posted D22203 for the LangRef update.

[hfinkel]

Updated per review comments.

[majnemer]

LGTM

lib/Transforms/IPO/FunctionAttrs.cpp

506–515 ↗

(On Diff #63434)

Hmm, should we skip the function when RetArgs.size() > 1?

[hfinkel]

lib/Transforms/IPO/FunctionAttrs.cpp

506–515 ↗

(On Diff #63434)

Yes, because we can only mark one attribute as returned (i.e. it is otherwise uncertain which argument will be returned, so we can mark neither).

llvm/trunk/lib/Transforms/IPO/FunctionAttrs.cpp

 #include "llvm/Analysis/TargetLibraryInfo.h"
 using namespace llvm;
 
 #define DEBUG_TYPE "functionattrs"
 
 STATISTIC(NumReadNone, "Number of functions marked readnone");
 STATISTIC(NumReadOnly, "Number of functions marked readonly");
 STATISTIC(NumNoCapture, "Number of arguments marked nocapture");
+STATISTIC(NumReturned, "Number of arguments marked returned");
 STATISTIC(NumReadNoneArg, "Number of arguments marked readnone");
 STATISTIC(NumReadOnlyArg, "Number of arguments marked readonly");
 STATISTIC(NumNoAlias, "Number of function returns marked noalias");
 STATISTIC(NumNonNullReturn, "Number of function returns marked nonnull");
 STATISTIC(NumNoRecurse, "Number of functions marked as norecurse");
 
 namespace {
 typedef SmallSetVector<Function *, 8> SCCNodeSet;
while (!Worklist.empty()) {
     default:
       return Attribute::None;
     }
   }
 
   return IsRead ? Attribute::ReadOnly : Attribute::ReadNone;
 }
 
+/// Deduce returned attributes for the SCC.
+static bool addArgumentReturnedAttrs(const SCCNodeSet &SCCNodes) {
+  bool Changed = false;
+
+  AttrBuilder B;
+  B.addAttribute(Attribute::Returned);
+
+  // Check each function in turn, determining if an argument is always returned.
+  for (Function *F : SCCNodes) {
+    // We can infer and propagate function attributes only when we know that the
+    // definition we'll get at link time is *exactly* the definition we see now.
+    // For more details, see GlobalValue::mayBeDerefined.
+    if (!F->hasExactDefinition())
+      continue;
+
+    if (F->getReturnType()->isVoidTy())
+      continue;
+
+    SmallPtrSet<Value *, 2> RetArgs;
+    for (BasicBlock &BB : *F)
+      if (auto *Ret = dyn_cast<ReturnInst>(BB.getTerminator())) {
+        // Note that stripPointerCasts should look through functions with
+        // returned arguments.
+        Value *RetVal = Ret->getReturnValue()->stripPointerCasts();
+        if (RetVal->getType() == F->getReturnType() && isa<Argument>(RetVal))
+          RetArgs.insert(RetVal);
+      }
+
+    if (RetArgs.size() == 1) {
+      auto *A = cast<Argument>(*RetArgs.begin());
+      A->addAttr(AttributeSet::get(F->getContext(), A->getArgNo() + 1, B));
+      ++NumReturned;
+      Changed = true;
+    }
+  }
+
+  return Changed;
+}
+
 /// Deduce nocapture attributes for the SCC.
 static bool addArgumentAttrs(const SCCNodeSet &SCCNodes) {
   bool Changed = false;
 
   ArgumentGraph AG;
 
   AttrBuilder B;
   B.addAttribute(Attribute::NoCapture);
if (!HasUnknownCall)
             HasUnknownCall = true;
             break;
           }
 
     SCCNodes.insert(&F);
   }
 
   bool Changed = false;
+  Changed |= addArgumentReturnedAttrs(SCCNodes);
   Changed |= addReadAttrs(SCCNodes, AARGetter);
   Changed |= addArgumentAttrs(SCCNodes);
 
   // If we have no external nodes participating in the SCC, we can deduce some
   // more precise attributes as well.
   if (!HasUnknownCall) {
     Changed |= addNoAliasAttrs(SCCNodes);
     Changed |= addNonNullAttrs(SCCNodes);
if (!F || F->hasFnAttribute(Attribute::OptimizeNone)) {
       // transform them and avoid leveraging information they provide.
       ExternalNode = true;
       continue;
     }
 
     SCCNodes.insert(F);
   }
 
+  Changed |= addArgumentReturnedAttrs(SCCNodes);
   Changed |= addReadAttrs(SCCNodes, AARGetter);
   Changed |= addArgumentAttrs(SCCNodes);
 
   // If we have no external nodes participating in the SCC, we can deduce some
   // more precise attributes as well.
   if (!ExternalNode) {
     Changed |= addNoAliasAttrs(SCCNodes);
     Changed |= addNonNullAttrs(SCCNodes);

llvm/trunk/test/Transforms/FunctionAttrs/2009-01-02-LocalStores.ll

 ; RUN: opt < %s -functionattrs -S | FileCheck %s
 
 ; CHECK: define i32* @a(i32** nocapture readonly %p)
 define i32* @a(i32** %p) {
   %tmp = load i32*, i32** %p
   ret i32* %tmp
 }
 
 ; CHECK: define i32* @b(i32* %q)
 define i32* @b(i32 *%q) {
   %mem = alloca i32*
   store i32* %q, i32** %mem
   %tmp = call i32* @a(i32** %mem)
   ret i32* %tmp
 }
 
-; CHECK: define i32* @c(i32* readnone %r)
+; CHECK: define i32* @c(i32* readnone returned %r)
 @g = global i32 0
 define i32* @c(i32 *%r) {
   %a = icmp eq i32* %r, null
   store i32 1, i32* @g
   ret i32* %r
 }

llvm/trunk/test/Transforms/FunctionAttrs/nocapture.ll

 ; RUN: opt < %s -functionattrs -S | FileCheck %s
 @g = global i32* null   ; <i32**> [#uses=1]
 
-; CHECK: define i32* @c1(i32* readnone %q)
+; CHECK: define i32* @c1(i32* readnone returned %q)
 define i32* @c1(i32* %q) {
   ret i32* %q
 }
 
 ; CHECK: define void @c2(i32* %q)
 ; It would also be acceptable to mark %q as readnone. Update @c3 too.
 define void @c2(i32* %q) {
   store i32* %q, i32** @g

 ; CHECK: define void @test1_1(i8* nocapture readnone %x1_1, i8* %y1_1)
 ; It would be acceptable to add readnone to %y1_1 and %y1_2.
 define void @test1_1(i8* %x1_1, i8* %y1_1) {
   call i8* @test1_2(i8* %x1_1, i8* %y1_1)
   store i32* null, i32** @g
   ret void
 }
 
-; CHECK: define i8* @test1_2(i8* nocapture readnone %x1_2, i8* %y1_2)
+; CHECK: define i8* @test1_2(i8* nocapture readnone %x1_2, i8* returned %y1_2)
 define i8* @test1_2(i8* %x1_2, i8* %y1_2) {
   call void @test1_1(i8* %x1_2, i8* %y1_2)
   store i32* null, i32** @g
   ret i8* %y1_2
 }
 
 ; CHECK: define void @test2(i8* nocapture readnone %x2)
 define void @test2(i8* %x2) {

 
 ; CHECK: define void @test4_1(i8* %x4_1)
 define void @test4_1(i8* %x4_1) {
   call i8* @test4_2(i8* %x4_1, i8* %x4_1, i8* %x4_1)
   store i32* null, i32** @g
   ret void
 }
 
-; CHECK: define i8* @test4_2(i8* nocapture readnone %x4_2, i8* readnone %y4_2, i8* nocapture readnone %z4_2)
+; CHECK: define i8* @test4_2(i8* nocapture readnone %x4_2, i8* readnone returned %y4_2, i8* nocapture readnone %z4_2)
 define i8* @test4_2(i8* %x4_2, i8* %y4_2, i8* %z4_2) {
   call void @test4_1(i8* null)
   store i32* null, i32** @g
   ret i8* %y4_2
 }
 
 declare i8* @test5_1(i8* %x5_1)
 

llvm/trunk/test/Transforms/FunctionAttrs/readattrs.ll

 ; RUN: opt < %s -functionattrs -S | FileCheck %s
 ; RUN: opt < %s -aa-pipeline=basic-aa -passes='cgscc(function-attrs)' -S | FileCheck %s
 @x = global i32 0
 
 declare void @test1_1(i8* %x1_1, i8* readonly %y1_1, ...)
 
 ; CHECK: define void @test1_2(i8* %x1_2, i8* readonly %y1_2, i8* %z1_2)
 define void @test1_2(i8* %x1_2, i8* %y1_2, i8* %z1_2) {
   call void (i8*, i8*, ...) @test1_1(i8* %x1_2, i8* %y1_2, i8* %z1_2)
   store i32 0, i32* @x
   ret void
 }
 
-; CHECK: define i8* @test2(i8* readnone %p)
+; CHECK: define i8* @test2(i8* readnone returned %p)
 define i8* @test2(i8* %p) {
   store i32 0, i32* @x
   ret i8* %p
 }
 
 ; CHECK: define i1 @test3(i8* readnone %p, i8* readnone %q)
 define i1 @test3(i8* %p, i8* %q) {
   %A = icmp ult i8* %p, %q

 }
 
 ; CHECK: define void @test7_1(i32* inalloca nocapture %a)
 ; inalloca parameters are always considered written
 define void @test7_1(i32* inalloca %a) {
   ret void
 }
 
-; CHECK: define i32* @test8_1(i32* readnone %p)
+; CHECK: define i32* @test8_1(i32* readnone returned %p)
 define i32* @test8_1(i32* %p) {
 entry:
   ret i32* %p
 }
 
 ; CHECK: define void @test8_2(i32* %p)
 define void @test8_2(i32* %p) {
 entry: