[InlineFunction] update attributes during inlining

[anna]

Summary

When we inline a callee into a callsite that has attributes on return, we need to add the attributes on calls that feed into the return value in the callee definition.

Currently, we do this for only for calls feeding into the return.

A following patch, will do this also for loads feeding into the return, by adding it as a metadata on the load (i.e. loaded value is nonnull).

The analysis is added to handle the simple cases.

[reames]

This is not correct. You're modifying the callee function, not the copy of the callee inlined into the caller. The callee may continue to persist, and may have other callers for which this fact does not apply. You need to perform this transform on the inlined copy.

See AddAliasScopeMetadata for an example of the approach.

Also, I'd strongly prefer to see this phrased as merging all return attributes.

[jdoerfert]

In addition to @reames correctness concerns this is not valid for a different reason. You cannot backwards propagate information in the general case:

__attribute__((nonnull)) int *foo(int c) {
   int *A = unknown();
   int *B = unknown();
   do_sth_with_ptr_and_may_use_nonnull(A, B);
   return c ? A : B; // or if (C) return A; else return B;
}

Knowing foo returns a nonnull value cannot be used to annotate A or B.

I think this is generally problematic as it basically special cases a situation which we can handle in general just fine.
Let's assume we inline and keep the nonnull on the return values around, we run nonnull deduction on the caller and we get the nonnull where it is correct.
The benefit of doing it this way (D75825) is that it will also work with all other attributes as well without reinventing all the logic in the Attributor.

[reames]

In D76140#1922162, @jdoerfert wrote:

In addition to @reames correctness concerns this is not valid for a different reason. You cannot backwards propagate information in the general case:

__attribute__((nonnull)) int *foo(int c) {
   int *A = unknown();
   int *B = unknown();
   do_sth_with_ptr_and_may_use_nonnull(A, B);
   return c ? A : B; // or if (C) return A; else return B;
}

Knowing foo returns a nonnull value cannot be used to annotate A or B.

Good catch, I'd missed that.

I think this is generally problematic as it basically special cases a situation which we can handle in general just fine.
Let's assume we inline and keep the nonnull on the return values around, we run nonnull deduction on the caller and we get the nonnull where it is correct.
The benefit of doing it this way (D75825) is that it will also work with all other attributes as well without reinventing all the logic in the Attributor.

I disagree, mostly in the framing of this as an either/or. If we can cheaply match IR patterns during inlining and use attributes instead of assumes, we should. The other option requires IR churn for minimal value since we'll fold the inserted assumes back into attributes in the end anyway. We clearly should use assumes for the general case, but that doesn't mean we shouldn't specialize the common case.

[anna]

addressed review comments. This handles all attributes on the call and only done after the cloning of the inlined body.
Tests added for attributes and making sure the original callee does not have the attributes added within its body.

[anna]

In D76140#1922292, @reames wrote:

In D76140#1922162, @jdoerfert wrote:

In addition to @reames correctness concerns this is not valid for a different reason. You cannot backwards propagate information in the general case:

__attribute__((nonnull)) int *foo(int c) {
   int *A = unknown();
   int *B = unknown();
   do_sth_with_ptr_and_may_use_nonnull(A, B);
   return c ? A : B; // or if (C) return A; else return B;
}

Knowing foo returns a nonnull value cannot be used to annotate A or B.

Good catch, I'd missed that.

Just noticed this. I think we can special case this to: the return and def call are in the same basic block (it will take care of the if-else in the example) and has only one use which is the return. The latter takes care of avoiding incorrect semantics in that call do_sth_with_ptr_and_may_use_nonnull or any other use that depends on knowing which of the ptr is non-null.

I think this is generally problematic as it basically special cases a situation which we can handle in general just fine.
Let's assume we inline and keep the nonnull on the return values around, we run nonnull deduction on the caller and we get the nonnull where it is correct.
The benefit of doing it this way (D75825) is that it will also work with all other attributes as well without reinventing all the logic in the Attributor.

I disagree, mostly in the framing of this as an either/or. If we can cheaply match IR patterns during inlining and use attributes instead of assumes, we should. The other option requires IR churn for minimal value since we'll fold the inserted assumes back into attributes in the end anyway. We clearly should use assumes for the general case, but that doesn't mean we shouldn't specialize the common case.

The above restrictions (which makes it conservative, but we have cases like that) should allow us cleanly place all the return attributes on the calls within the body, I think.

[jdoerfert]

In D76140#1922328, @anna wrote:

In D76140#1922292, @reames wrote:

In D76140#1922162, @jdoerfert wrote:

In addition to @reames correctness concerns this is not valid for a different reason. You cannot backwards propagate information in the general case:

__attribute__((nonnull)) int *foo(int c) {
   int *A = unknown();
   int *B = unknown();
   do_sth_with_ptr_and_may_use_nonnull(A, B);
   return c ? A : B; // or if (C) return A; else return B;
}

Knowing foo returns a nonnull value cannot be used to annotate A or B.

Good catch, I'd missed that.

Just noticed this. I think we can special case this to: the return and def call are in the same basic block (it will take care of the if-else in the example) and has only one use which is the return. The latter takes care of avoiding incorrect semantics in that call do_sth_with_ptr_and_may_use_nonnull or any other use that depends on knowing which of the ptr is non-null.

None of this is sufficient. We are repeating a lot of deduction logic here now...

Take:

__attribute__((nonnull)) int *foo() {
    int *Base = unknown();
    do_sth_with_ptr_and_may_use_nonnull(Base);
    int *A = return_arg(/* returned */ Base);
    exit();
    return A;
}

Return and call are in the same block, only a single use of A exists, however, backwards propagating nonnull to A is wrong and will be problematic if it is used to optimize Base.

[anna]

hmm. yes, I can see this getting complicated for design and correctness. Thanks for the example @jdoerfert.

Basically, the usecase I'm interested in is the following:

callee(i8* %arg) {
  %r = call i8* @foo(i8* %arg)
   ret i8* %r
}

And a follow-on example:

callee(i8** %arg) {
  %r = load i8*, i8** %arg <-- here we can add the !nonnull metadata if callsite for callee has nonnull return attr
   ret i8* %r
}

The caller is:

caller {
  ...
  call nonnull i8* @callee(i8** %arg) 
}

AFAICT, this should be fine because the only operations in callee context is the load and return. We are not backward propagating something incorrect into the callee context. W.r.t the caller context, what was true before inlining, remains true after inlining as well.

[jdoerfert]

In D76140#1922417, @anna wrote:

hmm. yes, I can see this getting complicated for design and correctness. Thanks for the example @jdoerfert.

These things are unfortunately never as easy as we want them to be, believe me I learned the hard way ;)

Basically, the usecase I'm interested in is the following:

callee(i8* %arg) {
  %r = call i8* @foo(i8* %arg)
   ret i8* %r
}

And a follow-on example:

callee(i8** %arg) {
  %r = load i8*, i8** %arg <-- here we can add the !nonnull metadata if callsite for callee has nonnull return attr
   ret i8* %r
}

The caller is:

caller {
  ...
  call nonnull i8* @callee(i8** %arg) 
}

AFAICT, this should be fine because the only operations in callee context is the load and return. We are not backward propagating something incorrect into the callee context. W.r.t the caller context, what was true before inlining, remains true after inlining as well.

1. If callee is internal and all call site are non-null we can easily make sure the Attributor catches this (if it does not already).
2. If callee is non-internal or not all call site are non-null we could introduce an internal copy of callee for all "good" call sites (the Attributor issue on this is here: https://github.com/llvm/llvm-project/issues/172)
3. If your use case is 2) but very restricted, you can walk the successors of the call/load and make sure they are all "OK", e.g., use MustBeExecutedContextExplorer::findInContextOf.

[reames]

Anna, I'd encourage you to go very narrow here. We can resolve the correlated throw case with the following: require operand of return to be call instruction which is less than small constant window of non-trapping instructions before the return. (i.e. start with previous node) If we allow bitcasts, that provides reasonable coverage. We can always fallback to assumes as noted.

We don't need to be hugely general analysis wise to be very useful. Calls in tail positions or loads in analogous are very common. We should handle that obvious case.

[anna]

In D76140#1922555, @reames wrote:

Anna, I'd encourage you to go very narrow here. We can resolve the correlated throw case with the following: require operand of return to be call instruction which is less than small constant window of non-trapping instructions before the return. (i.e. start with previous node) If we allow bitcasts, that provides reasonable coverage. We can always fallback to assumes as noted.

We don't need to be hugely general analysis wise to be very useful. Calls in tail positions or loads in analogous are very common. We should handle that obvious case.

Philip, I think we need to be even more conservative. I don't see how this will handle the parameter of the call instruction being incorrectly optimized away (second example with "returned" attribute on the parameter). IIUC, these are the two restrictions we need:

1. no throwing instructions between the call (i.e. the operand of the return) and the returnInstruction - possible restrict to small constant window like you described.
2. the arguments for the call should feed directly from the arguments in the callee (we can have bitcasts/geps here - i.e. use stripAndAccumulateConstantOffsets). This avoids possible incorrect propagation to the argument of the call

[anna]

talked with Philip offline. We just need the check for non-trapping instructions between the return value (i.e. the call) and the return instruction. In other cases, it is either correct to propagate the nonnull-ness or it showcased a UB that already existed in the program.

[anna]

will update patch and place for review.

[anna]

addressed review comments. The analysis is conservative and test cases added show the negative cases where we should not backward propagate the attribute to the call (i.e. return value operand).

[anna]

the test failures are related to attributes now being added to the calls in clang tests. All of these tests are using llvm intrinsics. Should we just disable this for intrinsic calls for now? Not sure how to update clang tests in the same patch as llvm project. Should be doable though.

[reames]

In D76140#1927909, @anna wrote:

the test failures are related to attributes now being added to the calls in clang tests. All of these tests are using llvm intrinsics. Should we just disable this for intrinsic calls for now? Not sure how to update clang tests in the same patch as llvm project. Should be doable though.

Er, git is monorepo. Those tests should be checked out alongside your LLVM copy. You just need to build clang. You can and should simply update the tests in the same patch.

[anna]

In D76140#1930078, @reames wrote:

In D76140#1927909, @anna wrote:

the test failures are related to attributes now being added to the calls in clang tests. All of these tests are using llvm intrinsics. Should we just disable this for intrinsic calls for now? Not sure how to update clang tests in the same patch as llvm project. Should be doable though.

Er, git is monorepo. Those tests should be checked out alongside your LLVM copy. You just need to build clang. You can and should simply update the tests in the same patch.

ah yes, I'd build llvm within it's own subdir without enabling any other projects. Build worked. thanks.

[anna]

fixed clang tests. rot-intrinsics.c testcase has 5 different RUNs with 3 prefixes. Depending on target-triple, the attribute is added to the caller, so I've disabled the optimization for that specific test with -update-return-attrs=false

[jdoerfert]

llvm/lib/Transforms/Utils/InlineFunction.cpp

1172

mayThrow is not sufficient. As with my earlier example, a potential exit is sufficient to break this, thus you need willreturn as well.

[anna]

llvm/lib/Transforms/Utils/InlineFunction.cpp

1172

What we need is just isGuaranteedToTransferExecutionToSuccessor. That handles mayThrow, exits/pthread_exit and willreturn.

Just to note, an unconditional exit in the callee itself is not an issue here. The problem is something like this:

;nothrow
foo(i8* %arg) {
if (%arg == null)
  exit;
ret %arg
}
callee() {
  %r = call i8* @bar
  %v = call i8* @foo(i8* %r)
   ret i8* %r
}
caller() {
  call nonnull i8* @callee
}

Here propagating nonnull to callsite bar is incorrect since if %r is null, the program exits.

[anna]

use isGuaranteedToTransferExecutionToSuccessor instead of MayThrow

[jdoerfert]

I'm unsure about the zeroext and signext on the call sites now but other than that I think this is good. wait for @reames OK though.

[anna]

llvm/lib/Transforms/Utils/InlineFunction.cpp

1172

Noticed while adding couple more tests, there are 2 bugs here:

1. the isGuaranteedToTransferExecutionToSuccessor check should be inverted
2. make_range should be until the return instruction - so we do not want std::prev on the returnInstruction. what's needed is: make_range(RVal->getIterator(), RInst->getIterator())

This means that from the callsite until (and excluding) the return instruction should be guaranteed to transfer execution to successor - only then we can backward propagate the attribute to that callsite.

[lebedev.ri]

llvm/lib/Transforms/Utils/InlineFunction.cpp

1172

Are you aware of llvm::isValidAssumeForContext()?
All this (including pitfalls) sound awfully close to that function.

[anna]

Noticed while adding couple more tests, there were 2 bugs:

1 the isGuaranteedToTransferExecutionToSuccessor check should be inverted

2. make_range should be until the return instruction - so we do not want std::prev on the returnInstruction. what's needed is: make_range(RVal->getIterator(), RInst->getIterator())

This means that from the callsite until (and excluding) the return instruction should be guaranteed to transfer execution to successor - only then we can backward propagate the attribute to that callsite.
Updated patch and added test cases.

[anna]

llvm/lib/Transforms/Utils/InlineFunction.cpp

1172

as stated in a previous comment (https://reviews.llvm.org/D76140#1922292), adding Assumes here for simple cases seems like an overkill. It has significant IR churn and it also adds a use for something which can be easily inferred.
Consider optimizations that depend on facts such as hasOneUse or a limited number of uses. We will now be inhibiting those optimizations.

[lebedev.ri]

llvm/lib/Transforms/Utils/InlineFunction.cpp

1172

While i venomously disagree with the avoidance of the usage of one versatile interface
and hope things will change once there's more progress on attributor & assume bundles,
in this case, as it can be seen even from the signature of the isValidAssumeForContext() function,
it implies/forces nothing about using assumes, but only performs a validity checking,
similar to the MayContainThrowingOrExitingCall()

https://github.com/llvm/llvm-project/blob/ca04d0c8fd269978be1c13fe1241172cdfe6a6ea/llvm/lib/Analysis/ValueTracking.cpp#L603

That being said, i haven't reviewed this code so maybe there's some differences here
that make that function unapplicable here.

[anna]

llvm/lib/Transforms/Utils/InlineFunction.cpp

1172

isValidAssumeForContext(Inv, CxtI, DT) does not force anything about assumes, but AFAICT all code which uses this function either has some sort of guard in the caller that the instruction is an assume. Also, the comments in the code state that it is for an assume. In fact, I believe if we intend to use that function more widely for other purposes, we should rename the function before using it (just a thought), and currently we should assert that Inv is an assume. It captures the intent of the function.

That being said, I checked the code in isValidAssumeForContext and it does not fit the bill here for multiple reasons. We either do:

1. isValidAssumeForContext(RVal /* Inv */, RInst /* CxtI */) which fails when we do not have DT and just return true when RVal comes before RInst - this is always the case, since RVal will come before RInst.
2. isValidAssumeForContext(RInst /* Inv*/, RVal /* CxtI*/) and it fails at the !isEphemeralValueOf(Inv /* RI */, CxtI /* RV*/) check.

(By fail here, I mean, it does not have the same behaviour as MayContainThrowingOrExitingCall).

[anna]

ping.

[anna]

NFC w.r.t prev diff. Use VMap.lookup instead of a lambda which does the same.

[reames]

LGTM, but with two specific required follow ups. If you're not comfortable committing to both, please don't land this one.

llvm/lib/Transforms/Utils/InlineFunction.cpp

89

I'd suggest a name change here. Maybe: "inliner-attribute-window"?

1159

Pull this out as a static helper instead of a lambda, add an assert internally that the two instructions are in the same block.

Why? Because I'm 80% sure the state capture on the lambda isn't needed, and having it as a separate function forces that discipline.

1175

Ok, after staring at it a bit, I've convinced myself the code here is correct, just needlessly conservative.

What you're doing is:
If the callees return instruction and returned call both map to the same instructions once inlined, determine whether there's a possible exit between the inlined copy.

What you could be doing:
If the callee returns a call, check if *in the callee* there's a possible exit between call and return, then apply attribute to cloned call.

The key difference is when the caller directly returns the result vs uses it locally. The result here is that your transform is much more narrow in applicability than it first appears.

llvm/test/Transforms/Inline/ret_attr_update.ll

113

There's a critical missing test case here:

• Callee and caller have the same attributes w/different values (i.e. deref)

And thinking through the code, I think there might be a bug here. It's not a serious one, but the if the callee specifies a larger deref than the caller, it looks like the the smaller value is being written over the larger.

Actually, digging through the attribute code, I think I'm wrong about the bug. However, you should definitely write the test to confirm and document merging behaviour!

If it does turn out I'm correct, I'm fine with this being addressed in a follow up patch provided that the test is added in this one and isn't a functional issue.

[anna]

llvm/lib/Transforms/Utils/InlineFunction.cpp

1159

agreed. I'll do that in this change itself before landing. I am using this static helper in followon change D76792.

1175

yes, thanks for pointing it out. I realized it after our offline discussion :)
For now, I will add a FIXME testcase which showcases the difference in code and handle that testcase in a followon change.

llvm/test/Transforms/Inline/ret_attr_update.ll

113

will check this.

[anna]

addressed review comments. Added two test cases: deref value being different, inlined callee body better optimized compared to callee.

[anna]

llvm/lib/Transforms/Utils/InlineFunction.cpp

1175

The key difference is when the caller directly returns the result vs uses it locally. The result here is that your transform is much more narrow in applicability than it first appears.

I tried multiple test cases to showcase the difference between the two ideas above but failed. Specifically, simplifyInstruction used during inlining the callee is not too great at optimizing the body. For example, see added testcase test7.

I also tried the less restrictive version (check the safety of the optimization in the callee itself, and do the attribute update on the cloned instruction), but didn't see any testcases in clang that needed update. Of course, that doesn't mean anything :)

llvm/test/Transforms/Inline/ret_attr_update.ll

113

added test case and documented merge behaviour. No bug in code, since we use the already existing value on attribute.

[anna]

I got a failure in one of the binaryFormats:
lib/BinaryFormat/CMakeFiles/LLVMBinaryFormat.dir/MsgPackReader.cpp

Attributes 'zeroext and signext' are incompatible!
  %rev.i.i.i.i.i.i.i.i = tail call signext zeroext i16 @llvm.bswap.i16(i16 %ret.0.copyload.i.i.i.i) #6
in function _ZN4llvm7msgpack6Reader7readIntIsEENS_8ExpectedIbEERNS0_6ObjectE
fatal error: error in backend: Broken function found, compilation aborted!

I believe this just showcases undefined behaviour since we were having a returnValue (i.e. call) with an incomptable attribute compared to the return attribute on the callsite.

[anna]

In D76140#1953201, @anna wrote:

I got a failure in one of the binaryFormats:
lib/BinaryFormat/CMakeFiles/LLVMBinaryFormat.dir/MsgPackReader.cpp

Attributes 'zeroext and signext' are incompatible!
  %rev.i.i.i.i.i.i.i.i = tail call signext zeroext i16 @llvm.bswap.i16(i16 %ret.0.copyload.i.i.i.i) #6
in function _ZN4llvm7msgpack6Reader7readIntIsEENS_8ExpectedIbEERNS0_6ObjectE
fatal error: error in backend: Broken function found, compilation aborted!

I believe this just showcases undefined behaviour since we were having a returnValue (i.e. call) with an incomptable attribute compared to the return attribute on the callsite.

The last statement is not true. Had a discussion offline with Philip and he pointed out that we missed the fact that attributes such as signext and zeroext are part of the *call* itself. We cannot propagate these attributes into the callee since such attributes are part of the ABI for the call it is attached to.
I'm reopening this review to fix this issue.

[anna]

see above comment.

[anna]

llvm/lib/Transforms/Utils/InlineFunction.cpp

1175

Clarified this with Philip offline. The current patch is not restrictive. In fact, now that I think of it, sometimes, it may be better - simplifyInstruction can fold away instructions and reduce the "window size" between the RV and the ReturnInst.

[anna]

whitelist valid return attributes and only add those. Added testcase for signext.

[anna]

fixed buildbot failure. see above comments and added testcase test8.

[anna]

fixed missing code left out during rebase.

[reames]

LGTM again, with minor change.

p.s. Sorry for missing the functional issue the first time. All of the test changes should have made the issue obvious, but despite reading the LangRef description of signext, I somehow managed to miss the separation between ABI and optimization attributes.

llvm/lib/Transforms/Utils/InlineFunction.cpp

1177

I'm not sure that pulling out the helper for two cases actually helps readability. Can you drop this and just do the two cases directly please?

[anna]

In D76140#1957416, @reames wrote:

LGTM again, with minor change.

will update it.

p.s. Sorry for missing the functional issue the first time. All of the test changes should have made the issue obvious, but despite reading the LangRef description of signext, I somehow managed to miss the separation between ABI and optimization attributes.

thanks for the review Philip and pointing out the problem. All of us had missed the functional issue the first time around.

llvm/lib/Transforms/Utils/InlineFunction.cpp

 //===- InlineFunction.cpp - Code to perform function inlining -------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
EnableNoAliasConversion("enable-noalias-to-md-conversion", cl::init(true),
   cl::Hidden,
   cl::desc("Convert noalias attributes to metadata during inlining."));
 
 static cl::opt<bool>
 PreserveAlignmentAssumptions("preserve-alignment-assumptions-during-inlining",
   cl::init(true), cl::Hidden,
   cl::desc("Convert align attributes to assumptions during inlining."));
 
+static cl::opt<bool> UpdateReturnAttributes(
+        "update-return-attrs", cl::init(true), cl::Hidden,
+            cl::desc("Update return attributes on calls within inlined body"));
+
+static cl::opt<unsigned> InlinerAttributeWindow(
+    "max-inst-checked-for-throw-during-inlining", cl::Hidden,
+    cl::desc("the maximum number of instructions analyzed for may throw during "
+             "attribute inference in inlined body"),
+    cl::init(4));
+
 llvm::InlineResult llvm::InlineFunction(CallBase *CB, InlineFunctionInfo &IFI,
                                         AAResults *CalleeAAR,
                                         bool InsertLifetime) {
   return InlineFunction(CallSite(CB), IFI, CalleeAAR, InsertLifetime);
 }
 
 namespace {
 
if (const Instruction *I = dyn_cast<Instruction>(VMI->first)) {
         NI->setMetadata(
             LLVMContext::MD_alias_scope,
             MDNode::concatenate(NI->getMetadata(LLVMContext::MD_alias_scope),
                                 MDNode::get(CalledFunc->getContext(), Scopes)));
     }
   }
 }
 
+static bool MayContainThrowingOrExitingCall(Instruction *Begin,
+                                            Instruction *End) {
+
+  assert(Begin->getParent() == End->getParent() &&
+         "Expected to be in same basic block!");
+  unsigned NumInstChecked = 0;
+  // Check that all instructions in the range [Begin, End) are guaranteed to
+  // transfer execution to successor.
+  for (auto &I : make_range(Begin->getIterator(), End->getIterator()))
+    if (NumInstChecked++ > InlinerAttributeWindow ||
+        !isGuaranteedToTransferExecutionToSuccessor(&I))
+      return true;
+  return false;
+}
+
+static AttrBuilder IdentifyValidAttributes(CallSite CS) {
+
+  AttrBuilder AB(CS.getAttributes(), AttributeList::ReturnIndex);
+  if (AB.empty())
+    return AB;
+  AttrBuilder Valid;
+  // Only allow these white listed attributes to be propagated back to the
+  // callee. This is because other attributes may only be valid on the call
+  // itself, i.e. attributes such as signext and zeroext.
+  if (auto DerefBytes = AB.getDereferenceableBytes())
+    Valid.addDereferenceableAttr(DerefBytes);
+  if (auto DerefOrNullBytes = AB.getDereferenceableOrNullBytes())
+    Valid.addDereferenceableOrNullAttr(DerefOrNullBytes);
+  auto AddAttrWithoutValues =
+      [&](SmallVectorImpl<Attribute::AttrKind> &Kinds) -> void {
+    for (Attribute::AttrKind Kind : Kinds)
+      if (AB.contains(Kind))
+        Valid.addAttribute(Kind);
+  };
+  SmallVector<Attribute::AttrKind, 2> AttrsWithoutVal = {Attribute::NoAlias,
+                                                         Attribute::NonNull};
+  AddAttrWithoutValues(AttrsWithoutVal);
+  return Valid;
+}
+
+static void AddReturnAttributes(CallSite CS, ValueToValueMapTy &VMap) {
+  if (!UpdateReturnAttributes)
+    return;
+
+  AttrBuilder Valid = IdentifyValidAttributes(CS);
+  if (Valid.empty())
+    return;
+  auto *CalledFunction = CS.getCalledFunction();
+  auto &Context = CalledFunction->getContext();
+
+  for (auto &BB : *CalledFunction) {
+    auto *RI = dyn_cast<ReturnInst>(BB.getTerminator());
+    if (!RI || !isa<CallBase>(RI->getOperand(0)))
+      continue;
+    auto *RetVal = cast<CallBase>(RI->getOperand(0));
+    // Sanity check that the cloned RetVal exists and is a call, otherwise we
+    // cannot add the attributes on the cloned RetVal.
+    // Simplification during inlining could have transformed the cloned
+    // instruction.
+    auto *NewRetVal = dyn_cast_or_null<CallBase>(VMap.lookup(RetVal));
+    if (!NewRetVal)
+      continue;
+    // Backward propagation of attributes to the returned value may be incorrect
+    // if it is control flow dependent.
+    // Consider:
+    // @callee {
+    //  %rv = call @foo()
+    //  %rv2 = call @bar()
+    //  if (%rv2 != null)
+    //    return %rv2
+    //  if (%rv == null)
+    //    exit()
+    //  return %rv
+    // }
+    // caller() {
+    //   %val = call nonnull @callee()
+    // }
+    // Here we cannot add the nonnull attribute on either foo or bar. So, we
+    // limit the check to both RetVal and RI are in the same basic block and
+    // there are no throwing/exiting instructions between these instructions.
+    if (RI->getParent() != RetVal->getParent() ||
+        MayContainThrowingOrExitingCall(RetVal, RI))
+      continue;
+    // Add to the existing attributes of NewRetVal, i.e. the cloned call
+    // instruction.
+    // NB! When we have the same attribute already existing on NewRetVal, but
+    // with a differing value, the AttributeList's merge API honours the already
+    // existing attribute value (i.e. attributes such as dereferenceable,
+    // dereferenceable_or_null etc). See AttrBuilder::merge for more details.
+    AttributeList AL = NewRetVal->getAttributes();
+    AttributeList NewAL =
+        AL.addAttributes(Context, AttributeList::ReturnIndex, Valid);
+    NewRetVal->setAttributes(NewAL);
+  }
+}
+
 /// If the inlined function has non-byval align arguments, then
 /// add @llvm.assume-based alignment assumptions to preserve this information.
 static void AddAlignmentAssumptions(CallSite CS, InlineFunctionInfo &IFI) {
   if (!PreserveAlignmentAssumptions || !IFI.GetAssumptionCache)
     return;
 
   AssumptionCache *AC = &(*IFI.GetAssumptionCache)(*CS.getCaller());
   auto &DL = CS.getCaller()->getParent()->getDataLayout();
fixupLineNumbers(Caller, FirstNewBlock, TheCall,
                      CalledFunc->getSubprogram() != nullptr);
 
     // Clone existing noalias metadata if necessary.
     CloneAliasScopeMetadata(CS, VMap);
 
     // Add noalias metadata if necessary.
     AddAliasScopeMetadata(CS, VMap, DL, CalleeAAR);
 
+    // Clone return attributes on the callsite into the calls within the inlined
+    // function which feed into its return value.
+    AddReturnAttributes(CS, VMap);
+
     // Propagate llvm.mem.parallel_loop_access if necessary.
     PropagateParallelLoopAccessMetadata(CS, VMap);
 
     // Register any cloned assumptions.
     if (IFI.GetAssumptionCache)
       for (BasicBlock &NewBlock :
            make_range(FirstNewBlock->getIterator(), Caller->end()))
         for (Instruction &I : NewBlock) {

llvm/test/Transforms/Inline/ret_attr_update.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -inline-threshold=0 -always-inline -S | FileCheck %s
+; RUN: opt < %s -passes=always-inline -S | FileCheck %s
+
+declare i8* @foo(i8*) argmemonly nounwind
+
+define i8* @callee(i8 *%p) alwaysinline {
+; CHECK-LABEL: @callee(
+; CHECK-NEXT:    [[R:%.*]] = call i8* @foo(i8* noalias [[P:%.*]])
+; CHECK-NEXT:    ret i8* [[R]]
+;
+  %r = call i8* @foo(i8* noalias %p)
+  ret i8* %r
+}
+
+define i8* @caller(i8* %ptr, i64 %x) {
+; CHECK-LABEL: @caller(
+; CHECK-NEXT:    [[GEP:%.*]] = getelementptr inbounds i8, i8* [[PTR:%.*]], i64 [[X:%.*]]
+; CHECK-NEXT:    [[R_I:%.*]] = call nonnull i8* @foo(i8* noalias [[GEP]])
+; CHECK-NEXT:    ret i8* [[R_I]]
+;
+  %gep = getelementptr inbounds i8, i8* %ptr, i64 %x
+  %p = call nonnull i8* @callee(i8* %gep)
+  ret i8* %p
+}
+
+declare void @llvm.experimental.guard(i1,...)
+; Cannot add nonnull attribute to foo
+; because the guard is a throwing call
+define internal i8* @callee_with_throwable(i8* %p) alwaysinline {
+  %r = call i8* @foo(i8* %p)
+  %cond = icmp ne i8* %r, null
+  call void (i1, ...) @llvm.experimental.guard(i1 %cond) [ "deopt"() ]
+  ret i8* %r
+}
+
+declare i8* @bar(i8*) readonly nounwind
+; Here also we cannot add nonnull attribute to the call bar.
+define internal i8* @callee_with_explicit_control_flow(i8* %p) alwaysinline {
+  %r = call i8* @bar(i8* %p)
+  %cond = icmp ne i8* %r, null
+  br i1 %cond, label %ret, label %orig
+
+ret:
+  ret i8* %r
+
+orig:
+  ret i8* %p
+}
+
+define i8* @caller2(i8* %ptr, i64 %x, i1 %cond) {
+; CHECK-LABEL: @caller2(
+; CHECK-NEXT:    [[GEP:%.*]] = getelementptr inbounds i8, i8* [[PTR:%.*]], i64 [[X:%.*]]
+; CHECK-NEXT:    [[R_I:%.*]] = call i8* @foo(i8* [[GEP]])
+; CHECK-NEXT:    [[COND_I:%.*]] = icmp ne i8* [[R_I]], null
+; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 [[COND_I]]) [ "deopt"() ]
+; CHECK-NEXT:    [[R_I1:%.*]] = call i8* @bar(i8* [[GEP]])
+; CHECK-NEXT:    [[COND_I2:%.*]] = icmp ne i8* [[R_I1]], null
+; CHECK-NEXT:    br i1 [[COND_I2]], label [[RET_I:%.*]], label [[ORIG_I:%.*]]
+; CHECK:       ret.i:
+; CHECK-NEXT:    br label [[CALLEE_WITH_EXPLICIT_CONTROL_FLOW_EXIT:%.*]]
+; CHECK:       orig.i:
+; CHECK-NEXT:    br label [[CALLEE_WITH_EXPLICIT_CONTROL_FLOW_EXIT]]
+; CHECK:       callee_with_explicit_control_flow.exit:
+; CHECK-NEXT:    [[Q3:%.*]] = phi i8* [ [[R_I1]], [[RET_I]] ], [ [[GEP]], [[ORIG_I]] ]
+; CHECK-NEXT:    br i1 [[COND:%.*]], label [[PRET:%.*]], label [[QRET:%.*]]
+; CHECK:       pret:
+; CHECK-NEXT:    ret i8* [[R_I]]
+; CHECK:       qret:
+; CHECK-NEXT:    ret i8* [[Q3]]
+;
+  %gep = getelementptr inbounds i8, i8* %ptr, i64 %x
+  %p = call nonnull i8* @callee_with_throwable(i8* %gep)
+  %q = call nonnull i8* @callee_with_explicit_control_flow(i8* %gep)
+  br i1 %cond, label %pret, label %qret
+
+pret:
+  ret i8* %p
+
+qret:
+  ret i8* %q
+}
+
+define internal i8* @callee3(i8 *%p) alwaysinline {
+  %r = call noalias i8* @foo(i8* %p)
+  ret i8* %r
+}
+
+; add the deref attribute to the existing attributes on foo.
+define i8* @caller3(i8* %ptr, i64 %x) {
+; CHECK-LABEL: @caller3(
+; CHECK-NEXT:    [[GEP:%.*]] = getelementptr inbounds i8, i8* [[PTR:%.*]], i64 [[X:%.*]]
+; CHECK-NEXT:    [[R_I:%.*]] = call noalias dereferenceable_or_null(12) i8* @foo(i8* [[GEP]])
+; CHECK-NEXT:    ret i8* [[R_I]]
+;
+  %gep = getelementptr inbounds i8, i8* %ptr, i64 %x
+  %p = call dereferenceable_or_null(12) i8* @callee3(i8* %gep)
+  ret i8* %p
+}
+
+declare i8* @inf_loop_call(i8*) nounwind
+; We cannot propagate attributes to foo because we do not know whether inf_loop_call
+; will return execution.
+define internal i8* @callee_with_sideeffect_callsite(i8* %p) alwaysinline {
+  %r = call i8* @foo(i8* %p)
+  %v = call i8* @inf_loop_call(i8* %p)
+  ret i8* %r
+}
+
+; do not add deref attribute to foo
+define i8* @test4(i8* %ptr, i64 %x) {
+; CHECK-LABEL: @test4(
+; CHECK-NEXT:    [[GEP:%.*]] = getelementptr inbounds i8, i8* [[PTR:%.*]], i64 [[X:%.*]]
+; CHECK-NEXT:    [[R_I:%.*]] = call i8* @foo(i8* [[GEP]])
+; CHECK-NEXT:    [[V_I:%.*]] = call i8* @inf_loop_call(i8* [[GEP]])
+; CHECK-NEXT:    ret i8* [[R_I]]
+;
+  %gep = getelementptr inbounds i8, i8* %ptr, i64 %x
+  %p = call dereferenceable_or_null(12) i8* @callee_with_sideeffect_callsite(i8* %gep)
+  ret i8* %p
+}
+
+declare i8* @baz(i8*) nounwind readonly
+define internal i8* @callee5(i8* %p) alwaysinline {
+  %r = call i8* @foo(i8* %p)
+  %v = call i8* @baz(i8* %p)
+  ret i8* %r
+}
+
+; add the deref attribute to foo.
+define i8* @test5(i8* %ptr, i64 %x) {
+; CHECK-LABEL: @test5(
+; CHECK-NEXT:    [[GEP:%.*]] = getelementptr inbounds i8, i8* [[PTR:%.*]], i64 [[X:%.*]]
+; CHECK-NEXT:    [[R_I:%.*]] = call dereferenceable_or_null(12) i8* @foo(i8* [[GEP]])
+; CHECK-NEXT:    [[V_I:%.*]] = call i8* @baz(i8* [[GEP]])
+; CHECK-NEXT:    ret i8* [[R_I]]
+;
+  %gep = getelementptr inbounds i8, i8* %ptr, i64 %x
+  %s = call dereferenceable_or_null(12) i8* @callee5(i8* %gep)
+  ret i8* %s
+}
+
+; deref attributes have different values on the callee and the call feeding into
+; the return.
+; AttrBuilder chooses the already existing value and does not overwrite it.
+define internal i8* @callee6(i8* %p) alwaysinline {
+  %r = call dereferenceable_or_null(16) i8* @foo(i8* %p)
+  %v = call i8* @baz(i8* %p)
+  ret i8* %r
+}
+
+
+define i8* @test6(i8* %ptr, i64 %x) {
+; CHECK-LABEL: @test6(
+; CHECK-NEXT:    [[GEP:%.*]] = getelementptr inbounds i8, i8* [[PTR:%.*]], i64 [[X:%.*]]
+; CHECK-NEXT:    [[R_I:%.*]] = call dereferenceable_or_null(16) i8* @foo(i8* [[GEP]])
+; CHECK-NEXT:    [[V_I:%.*]] = call i8* @baz(i8* [[GEP]])
+; CHECK-NEXT:    ret i8* [[R_I]]
+;
+  %gep = getelementptr inbounds i8, i8* %ptr, i64 %x
+  %s = call dereferenceable_or_null(12) i8* @callee6(i8* %gep)
+  ret i8* %s
+}
+
+; We add the attributes from the callee to both the calls below.
+define internal i8* @callee7(i8 *%ptr, i1 %cond) alwaysinline {
+  br i1 %cond, label %pass, label %fail
+
+pass:
+  %r = call i8* @foo(i8* noalias %ptr)
+  ret i8* %r
+
+fail:
+  %s = call i8* @baz(i8* %ptr)
+  ret i8* %s
+}
+
+define void @test7(i8* %ptr, i64 %x, i1 %cond) {
+; CHECK-LABEL: @test7(
+; CHECK-NEXT:    [[GEP:%.*]] = getelementptr inbounds i8, i8* [[PTR:%.*]], i64 [[X:%.*]]
+; CHECK-NEXT:    br i1 [[COND:%.*]], label [[PASS_I:%.*]], label [[FAIL_I:%.*]]
+; CHECK:       pass.i:
+; CHECK-NEXT:    [[R_I:%.*]] = call nonnull i8* @foo(i8* noalias [[GEP]])
+; CHECK-NEXT:    br label [[CALLEE7_EXIT:%.*]]
+; CHECK:       fail.i:
+; CHECK-NEXT:    [[S_I:%.*]] = call nonnull i8* @baz(i8* [[GEP]])
+; CHECK-NEXT:    br label [[CALLEE7_EXIT]]
+; CHECK:       callee7.exit:
+; CHECK-NEXT:    [[T1:%.*]] = phi i8* [ [[R_I]], [[PASS_I]] ], [ [[S_I]], [[FAIL_I]] ]
+; CHECK-NEXT:    call void @snort(i8* [[T1]])
+; CHECK-NEXT:    ret void
+;
+
+  %gep = getelementptr inbounds i8, i8* %ptr, i64 %x
+  %t = call nonnull i8* @callee7(i8* %gep, i1 %cond)
+  call void @snort(i8* %t)
+  ret void
+}
+declare void @snort(i8*)
+
+declare i32 @intrinsic(i8*) nounwind argmemonly
+
+define internal i32 @callee8(i8* %ptr) alwaysinline {
+  %r = call i32 @intrinsic(i8* noalias %ptr)
+  ret i32 %r
+}
+
+
+; signext is an attribute specific to the target ABI and not the
+; callee/callsite.
+; We cannot propagate that attribute to another call since it can be invalid at
+; that call.
+define i32 @test8(i8* %ptr, i64 %x) {
+; CHECK-LABEL: @test8(
+; CHECK-NEXT:    [[GEP:%.*]] = getelementptr inbounds i8, i8* [[PTR:%.*]], i64 [[X:%.*]]
+; CHECK-NEXT:    [[R_I:%.*]] = call i32 @intrinsic(i8* noalias [[GEP]])
+; CHECK-NEXT:    ret i32 [[R_I]]
+;
+
+  %gep = getelementptr inbounds i8, i8* %ptr, i64 %x
+  %t = call signext i32 @callee8(i8* %gep)
+  ret i32 %t
+}