Strip undef implying attributes when moving calls

[anna]

Summary

When hoisting/moving calls to locations, we strip unknown metadata. Such calls are usually marked speculatable, i.e. they are guaranteed to not cause undefined behaviour when run anywhere. So, we should strip attributes that can cause immediate undefined behaviour if those attributes are not valid in the context where the call is moved to.

Fix for PR50744.

[anna]

updated comments

[lebedev.ri]

Should this not be integrated into Instruction::hasMetadataOtherThanDebugLoc()/Instruction::dropUnknownNonDebugMetadata() ?

[anna]

In D104641#2830481, @lebedev.ri wrote:

Should this not be integrated into Instruction::hasMetadataOtherThanDebugLoc()/Instruction::dropUnknownNonDebugMetadata() ?

I'm not too sure frankly. There's two differences, so if we integrate it, we will need something to reflect that in the name:

1. Attribute stripping is only for calls. On other instructions, attributes are needed for correctness (while metadata is just for performance and can be stripped without any impact on correctness).
2. As mentioned in #1, there are attributes that are needed for correctness. So, we keep a whitelist of attributes we can legally strip from the call parameters.

On the other hand though, it makes sense to strip such attributes not just in hoisting, but also when instructions are "moved"/cloned to another location (such as stripping metadata done in SimplifyCFG). So, I can see a case for integrating this into the functionality where we drop unknown metadata.

[asbirlea]

It may be too much to overload the existing APIs, since this applies only to calls (e.g. in GVNHoist, metadata is dropped for geps, this would be unnecessary). So either doing the two calls independently as in this patch or add another API that does both.
I don't have strong opinions either way.

Is it possible this patch applies at the call in SimplifyCFG.cpp:1092 and :2487 and at hoistAllInstructionsInto in Local.cpp (also used by SimplifyCFG)? If the number of use cases is large enough, an API with both might make sense.

Side note, I believe there are cases where metadata must be dropped for correctness as well.

[anna]

In D104641#2831539, @asbirlea wrote:

It may be too much to overload the existing APIs, since this applies only to calls (e.g. in GVNHoist, metadata is dropped for geps, this would be unnecessary). So either doing the two calls independently as in this patch or add another API that does both.
I don't have strong opinions either way.

Is it possible this patch applies at the call in SimplifyCFG.cpp:1092 and :2487 and at hoistAllInstructionsInto in Local.cpp (also used by SimplifyCFG)? If the number of use cases is large enough, an API with both might make sense.

It looks like both cases in SimplifyCFG and hoistAllInstructionsInto are applicable (will try constructing test cases). Also, another spot is makeLoopInvariant in Analysis/LoopInfo.cpp. There we can make a readnone speculatable call loop-invariant (and hoist it to specified point outside loop).

Side note, I believe there are cases where metadata must be dropped for correctness as well.

Ah, I meant metadata can be dropped unconditionally and that will not impact correctness. Performance can be affected if we dropped metadata that could be retained.
Whereas for attributes, if we drop them unconditionally, it can affect correctness.

I agree to your point - actually, in most cases, we drop metadata to preserve correctness.

[nikic]

llvm/lib/IR/Instructions.cpp

353

We already have removeParamUndefImplyingAttributes() with a similar but not same list of attributes. I'm not sure if the desired semantics line up, but if they do it would be good to extend/reuse that.

[jdoerfert]

llvm/lib/IR/Instructions.cpp

350

We got rid of "whitelist". It is also weird to call it that as we actually remove those. I'm not sure having a list here is great. Should we have a Attribute::isABIrelated() instead?

[anna]

llvm/lib/IR/Instructions.cpp

350

Yeah. I think isABIRelated is a good choice here. I'll add that function and use it here, instead of a list. It also tests the theory that only ABI related attributes is illegal to strip.

353

Looking at that code piece, I don't think they line up for what's required here. Specifically, it is for updating attributes if a given parameter has undefined/poison behaviour in it.

[anna]

addressed review comments. Strip attributes whenever a call is moved (either through hoisting or simplifyCFG).
See updated tests.

[nikic]

Do I understand correctly that a function declaration like declare void @test(i32 noundef) speculatable is illegal, because the parameter attributes can result in UB? So if the speculatable attribute is present, we can assume that all attributes present on the function declaration are also safe to speculate, and the only thing we have to worry about are additional non-speculatable attributes on the call-site?

llvm/include/llvm/IR/Instruction.h

397 ↗

(On Diff #356538)

nit: moves -> move

llvm/lib/IR/Attributes.cpp

279 ↗

(On Diff #356538)

Shouldn't this also include at least inreg, byval, byref, preallocated, inalloca, sret? Possibly also swiftself/swiftasync and alignstack?

Might make sense to update LangRef with a clearer distinction between ABI and optimization attributes for arguments.

279 ↗

(On Diff #356538)

Though generally, I'm not convinced that we should treat this as dropping all non-abi attributes.

I think we should only be dropping attributes for which passing an invalid value results in immediate undefined behavior. Dropping nonnull for example should not be needed, as that just results in a poison argument, and the speculatable attribute promises that the function must deal with that just fine.

The only attributes we need to drop are things like noundef, dereferenceable and dereferenceable_or_null. Which is pretty much what removeParamUndefImplyingAttributes() is doing (modulo implementation bugs).

llvm/lib/IR/Instruction.cpp

185 ↗

(On Diff #356538)

What about return attributes? Aren't they also affected?

[anna]

In D104641#2858546, @nikic wrote:

Do I understand correctly that a function declaration like declare void @test(i32 noundef) speculatable is illegal, because the parameter attributes can result in UB?

Yes, that's right.

So if the speculatable attribute is present, we can assume that all attributes present on the function declaration are also safe to speculate, and the only thing we have to worry about are additional non-speculatable attributes on the call-site?

That's one way to reason about it. So, basically we do not need to be as restrictive as the current patch. For example, if we have the speculatable attribute on the function declaration and non null only on the parameter at the callsite, we should be able to run this call anywhere even if the parameter maybe null at the location the call is moved to. The only attributes we should strip are those that cause immediate UB. As Artur pointed out offline, it looks like nonnull behaviour was also changed recently to return poison instead of causing UB (if the pointer is indeed null). Given the speculatable attribute, we should never have UB within that function if we were to pass in a poison argument.

llvm/lib/IR/Attributes.cpp

279 ↗

(On Diff #356538)

agreed. Thanks for the clarification.

llvm/lib/IR/Instruction.cpp

185 ↗

(On Diff #356538)

Yes, that's right. We could move the call anywhere (not just hoist it above conditions affecting the parameter attributes).

[anna]

addressed review comments from @nikic.

[anna]

llvm/lib/IR/Attributes.cpp

279 ↗

(On Diff #356538)

Note that removeParamUndefImplyingAttributes does have Nonnull in it currently and the comment states that it removes attributes that imply both UB and poison.
The API was added here: https://reviews.llvm.org/D98899 and there's a comment stating that removing nonnull is strictly not necessary but doesn't hurt either. After all, we are propagating poison in that speculatable call.

My updated tests also state the same - we need not remove nonnull. I have also added tests to show where we should strictly remove attributes (such as dereferenceable).

[anna]

address typo in failing testcase.

[anna]

ping

[nikic]

I pushed https://github.com/llvm/llvm-project/commit/99f869c8f00a36dac3c774178b69d05876a29a31 and https://github.com/llvm/llvm-project/commit/087a8eea359a4d8ef22c42fddca3b09833928c6a as some preliminary cleanup, could you please rebase? Generally this looks good to me though.

[jdoerfert]

Rebase on 087a8eea359a should make it a bit smaller. I'm unsure why the nonnull is listed in PopulateUndefImplyingAttributes I guess after the rebase it will be gone and the tests that drop it won't anymore.

seems there are no more real concerns, so LGTM if the rebase works out as expected.

llvm/test/Transforms/LICM/call-hoisting.ll

28

[jdoerfert]

In D104641#2903134, @nikic wrote:

I pushed https://github.com/llvm/llvm-project/commit/99f869c8f00a36dac3c774178b69d05876a29a31 and https://github.com/llvm/llvm-project/commit/087a8eea359a4d8ef22c42fddca3b09833928c6a as some preliminary cleanup, could you please rebase? Generally this looks good to me though.

I was looking at the code and missed one of the patches and your comment. Does look like you agree and we can go ahead here though.

[anna]

rebased over landed changes. Use getUBImplyingAttributes API.

[anna]

llvm/lib/Analysis/IVDescriptors.cpp

202 ↗

(On Diff #361787)

Ah. ignore stale comment for fixing another bug.

[anna]

In D104641#2903135, @jdoerfert wrote:

Rebase on 087a8eea359a should make it a bit smaller. I'm unsure why the nonnull is listed in PopulateUndefImplyingAttributes I guess after the rebase it will be gone and the tests that drop it won't anymore.

seems there are no more real concerns, so LGTM if the rebase works out as expected.

Thanks @jdoerfert. I'll give it a day if anyone has concerns over the rebased code.

[anna]

removed unrelated change.

[lebedev.ri]

LGTM, thank you.
Looks like my original design comment was essentially addressed, so i really like this.

It would be best to land this within next ~12 hours or so, before branching happens,
i.e. i'd maybe suggesting landing how.

llvm/include/llvm/IR/Instruction.h

331–334 ↗

(On Diff #361787)

dropUnknownNonDebugMetadata()'s documentation really needs an update
to point out that dropUndefImplyingAttrsAndUnknownMetadata() likely should be used instead.

398–401 ↗

(On Diff #361787)

Wouldn't

void dropUndefImplyingAttrsAndUnknownMetadata(ArrayRef<unsigned> KnownIDs = {});

suffice?

[nikic]

LG from my side as well.

[anna]

llvm/include/llvm/IR/Instruction.h

398–401 ↗

(On Diff #361787)

agreed, done.

llvm/include/llvm/IR/InstrTypes.h

public:
   /// `undef` or `poison` value is passed from the given argument.
   void removeParamUndefImplyingAttrs(unsigned ArgNo) {
     assert(ArgNo < getNumArgOperands() && "Out of bounds");
     AttributeList PAL = getAttributes();
     PAL = PAL.removeParamUndefImplyingAttributes(getContext(), ArgNo);
     setAttributes(PAL);
   }
 
+  void stripParamAttrAfterHoist();
+
   /// adds the dereferenceable attribute to the list of attributes.
   void addDereferenceableAttr(unsigned i, uint64_t Bytes) {
     AttributeList PAL = getAttributes();
     PAL = PAL.addDereferenceableAttr(getContext(), i, Bytes);
     setAttributes(PAL);
   }
 
   /// adds the dereferenceable_or_null attribute to the list of

llvm/lib/IR/Instructions.cpp

Value *CallBase::getReturnedArgOperand() const {
   if (const Function *F = getCalledFunction())
     if (F->getAttributes().hasAttrSomewhere(Attribute::Returned, &Index) &&
         Index)
       return getArgOperand(Index - AttributeList::FirstArgIndex);
 
   return nullptr;
 }
 
+void CallBase::stripParamAttrAfterHoist() {
+  AttributeList AL = getAttributes();
+  if (AL.isEmpty())
+    return;
+  // Whitelist the set of attributes we should strip from the call, if these
+  // are present. We do not need to worry if these are global properties that is
+  // being stripped, i.e. valid everywhere since they are present on function
+  // declaration. We always check for these parameter attributes on function
+  // declaration if they are not present at call. 
+  // We use a list to avoid illegally stripping attributes that are ABI related, such
+  // as signext and zeroext.
+  
+  // Whitelist attributes we should strip.
+  static constexpr Attribute::AttrKind ParamAttrsToStrip[] = {
+            Attribute::NonNull, Attribute::Alignment, Attribute::NoAlias,
+            Attribute::Dereferenceable};
+  for (unsigned ArgNo = 0; ArgNo < getNumArgOperands(); ArgNo++) {
+    auto PAttr = AL.getParamAttributes(ArgNo); 
+    // List of attributes that are present in parameter that we need to remove.
+    AttrBuilder R;
+    auto Index = ArgNo + AttributeList::FirstArgIndex;
+    for (auto Attr : ParamAttrsToStrip)
+      if (AL.hasAttribute(Index, Attr))
+       R.addAttribute(Attr);
+    setAttributes(getAttributes().removeAttributes(getContext(), Index, R));
+  }
+}
+
 /// Determine whether the argument or parameter has the given attribute.
 bool CallBase::paramHasAttr(unsigned ArgNo, Attribute::AttrKind Kind) const {
   assert(ArgNo < getNumArgOperands() && "Param index out of bounds!");
 
   if (Attrs.hasParamAttribute(ArgNo, Kind))
     return true;
   if (const Function *F = getCalledFunction())
     return F->getAttributes().hasParamAttribute(ArgNo, Kind);

llvm/lib/Transforms/Scalar/LICM.cpp

static void hoist(Instruction &I, const DominatorTree *DT, const Loop *CurLoop,
   // is valid in the loop preheader.
   if (I.hasMetadataOtherThanDebugLoc() &&
       // The check on hasMetadataOtherThanDebugLoc is to prevent us from burning
       // time in isGuaranteedToExecute if we don't actually have anything to
       // drop.  It is a compile time optimization, not required for correctness.
       !SafetyInfo->isGuaranteedToExecute(I, DT, CurLoop))
     I.dropUnknownNonDebugMetadata();
 
+  // If I is a call and it is not guaranteed to execute in the loop, then moving
+  // to the preheader means we should strip parameter attributes on the call
+  // since we may be hoisting above conditions that allowed inferring those
+  // attributes. They may not be valid at the preheader.
+  // Anna
+  if (isa<CallInst>(I) && !SafetyInfo->isGuaranteedToExecute(I, DT, CurLoop))
+    cast<CallInst>(&I)->stripParamAttrAfterHoist();
+
   if (isa<PHINode>(I))
     // Move the new node to the end of the phi list in the destination block.
     moveInstructionBefore(I, *Dest->getFirstNonPHI(), *SafetyInfo, MSSAU, SE);
   else
     // Move the new node to the destination block, before its terminator.
     moveInstructionBefore(I, *Dest->getTerminator(), *SafetyInfo, MSSAU, SE);
 
   I.updateLocationAfterHoist();

llvm/test/Transforms/LICM/call-hoisting.ll

loop:
   %iv.next = add i32 %iv, 1
   %cmp = icmp slt i32 %iv, 200
   br i1 %cmp, label %loop, label %exit
 
 exit:
   ret void
 }
 
+declare i32 @spec(i32* %p) readonly argmemonly nounwind speculatable
+
+; We should strip the nonnull callsite attribute on spec call's argument since it is
+; may not be valid when hoisted to preheader.
+define void @test_strip_attribute(i32* noalias %loc, i32* noalias %sink, i32* %q) {
+; CHECK-LABEL: test_strip_attribute
+; CHECK-LABEL: entry
+; CHECK-NEXT:   %ret = call i32 @load(i32* %loc)
+; CHECK-NEXT:   %nullchk = icmp eq i32* %q, null
+; CHECK-NEXT:   %ret2 = call i32 @spec(i32* %q)
+entry:
+  br label %loop
+
+loop:
+  %iv = phi i32 [0, %entry], [%iv.next, %isnull ]
+  %ret = call i32 @load(i32* %loc)
+  %nullchk = icmp eq i32* %q, null
+  br i1 %nullchk, label %isnull, label %nonnullbb
+
+nonnullbb:  
+  %ret2 = call i32 @spec(i32* nonnull %q)
+  br label %isnull
+
+isnull:  
+  store volatile i32 %ret, i32* %sink
+  %iv.next = add i32 %iv, 1
+  %cmp = icmp slt i32 %iv, 200
+  br i1 %cmp, label %loop, label %exit
+
+exit:
+  ret void
+}
 
 declare void @store(i32 %val, i32* %p) argmemonly writeonly nounwind
 
 define void @test(i32* %loc) {
 ; CHECK-LABEL: @test
 ; CHECK-LABEL: loop:
 ; CHECK: call void @store
 ; CHECK-LABEL: exit: