[InstCombine] Remove side effect of replaced constrained intrinsics

[sepavloff]

Summary

If a constrained intrinsic call was replaced by some value, it was not
removed in some cases. The dangling instruction resulted in useless
instructions executed in runtime. It happened because constrained
intrinsics usually have side effect, it is used to model the interaction
with floating point-environment. In some cases it is correct behavior
but often the side effect is actually absent or can be ignored.

This change adds specific treatment of constrained intrinsics so that
their side effect can be removed if it actually absents.

[efriedma]

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

3373

I'm not sure I understand the relevant invariant here. You're using SimplifyInstruction to assert that the simplified instruction has no side-effects? That isn't documented anywhere, but I guess it makes sense? Please confirm and add API documentation explaining this.

If it is safe, we should simplify all calls, not just for ConstrainedFPIntrinsic calls.

Also, you can just erase a call using eraseInstFromFunction; you don't need to mark it readnone and wait for another iteration of instcombine.

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

3373

If it is safe, we should simplify all calls, not just for ConstrainedFPIntrinsic calls.

This is definitely not safe in general -- obvious example being math libcalls that fold but are not dead due to errno. This needs to be constrained FP intrinsic specific contract.

[sepavloff]

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

3373

I admit the code is not obvious enough.

The key point here is that SimplifyInstruction does not return a replacement if the constrained intrinsic has side effect. So if control passed inside the if statement, we know that no actual side effect is associated with the intrinsic.

The next check if (CI.getNumUses() == 0) handles dangling instructions. They could not be removed due to the side effect but actually they have no such because SimplifyInstruction provided a replacement.

Also, you can just erase a call using eraseInstFromFunction;

InstCombiner will do it in the same iteration, if isInstructionTriviallyDead returns true for this instruction.

[sepavloff]

Small changes to the patch

• Add comments,
• Add checks that replacement value is different from the original one.

[sepavloff]

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

3373

If SimplifyInstruction returned a replacement even if side effect presents and the exception behavior is strict, the original instruction would not be deleted, because it is unknown if the side effect actually exists. SimplifyInstruction is an analysis, it cannot remove bogus side effect. To find out if the side effect actually absents the logic of SimplifyInstruction must be replayed, which is undesirable as it would increase compile time.

If SimplifyInstruction returns replacement only when it can replace the original expression without change of semantic, the useless code can be removed.

[sepavloff]

Does this patch require additional changes?

[sepavloff]

Ping.

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

1057

You can't use RAUW in InstCombine. This should be return replaceInstUsesWith(II, V).

...actually, as we already called SimplifyCall above, this situation can only happen if you have a constrained intrinsic with use_empty(). I'd suggest to check for use_empty() + simplify succeeds and directly erase the call in that case. I think that will be more obvious that adding a readnone attribute to get it erased in a separate iteration of InstCombine.

3375

Can you please add a comment to InstructionSimplify that documents this additional requirement? That is, that constrained intrinsics are only allowed to be folded if they do not side effect (which is different from the usual InstSimplify rules).

[sepavloff]

Get rid of call attribute manipulations

[sepavloff]

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

1057

You are right. As now all things happen in the same pass, tweaking attributes is not needed. Instead constrained intrinsics can be handled specially in the InstCombine code that removes unused instructions.

3375

Added relevant documentation to the declaration of SimplifyCall.

[sepavloff]

Ping.

[kpn]

I'm still not clear on why, when a transform pass knows an instruction can be deleted, we are required to keep that instruction around anyway. It seems like these dangling, useless instructions would interfere with subsequent optimizations until finally they might or might not get removed here. And constant folding isn't sufficient to duplicate the logic of the transform pass that determined the instruction could be deleted.

For example, here's a small test that I'm working on for InstSimplify:

; NOTE: The fsub instruction is expected to remain, but the result isn't used.
define float @nonneg_ebstrict(i32 %a) #0 {

%fpa = call float @llvm.experimental.constrained.uitofp.f32.i32(i32 %a, metadata !"round.tonearest", metadata !"fpexcept.strict") #0
%sqra = call float @llvm.experimental.constrained.sqrt.f32(float %fpa, metadata !"round.tonearest", metadata !"fpexcept.strict") #0
%sub = call nnan float @llvm.experimental.constrained.fsub.f32(float %sqra, float -0.0, metadata !"round.tonearest", metadata !"fpexcept.strict") #0
ret float %sub

}

The input to the sqrt instruction will always be non-negative, so we know the output is valid, and we know the output will never be -0.0. This means the fsub can be safely eliminated. But the fsub will hang around forever, useless, because InstSimplify isn't allowed to tell anyone that it can be deleted, and nobody else can determine it again without duplicating InstSimplify.

[sepavloff]

In D118426#3337489, @kpn wrote:

I'm still not clear on why, when a transform pass knows an instruction can be deleted, we are required to keep that instruction around anyway.

Are we really required? Or the transform pass merely does not know that the instruction can be deleted? InstCombine is just this case, at least in constant folding.

It seems like these dangling, useless instructions would interfere with subsequent optimizations until finally they might or might not get removed here. And constant folding isn't sufficient to duplicate the logic of the transform pass that determined the instruction could be deleted.

InstCombine is called several times, it calls constant folding and instruction simplification functions. It looks like a good place to get rid of such useless instructions.

For example, here's a small test that I'm working on for InstSimplify:

; NOTE: The fsub instruction is expected to remain, but the result isn't used.
define float @nonneg_ebstrict(i32 %a) #0 {

%fpa = call float @llvm.experimental.constrained.uitofp.f32.i32(i32 %a, metadata !"round.tonearest", metadata !"fpexcept.strict") #0
%sqra = call float @llvm.experimental.constrained.sqrt.f32(float %fpa, metadata !"round.tonearest", metadata !"fpexcept.strict") #0
%sub = call nnan float @llvm.experimental.constrained.fsub.f32(float %sqra, float -0.0, metadata !"round.tonearest", metadata !"fpexcept.strict") #0
ret float %sub

}

The input to the sqrt instruction will always be non-negative, so we know the output is valid, and we know the output will never be -0.0. This means the fsub can be safely eliminated. But the fsub will hang around forever, useless, because InstSimplify isn't allowed to tell anyone that it can be deleted, and nobody else can determine it again without duplicating InstSimplify.

InstSimplify is not the only place where peephole transformations may occur. InstCombine can also do such transformations and it is less limited. The described transformation could be a part of it.

[kpn]

In D118426#3337963, @sepavloff wrote:

In D118426#3337489, @kpn wrote:

It seems like these dangling, useless instructions would interfere with subsequent optimizations until finally they might or might not get removed here. And constant folding isn't sufficient to duplicate the logic of the transform pass that determined the instruction could be deleted.

InstCombine is called several times, it calls constant folding and instruction simplification functions. It looks like a good place to get rid of such useless instructions.

My point is that it shouldn't be needed for eliminating dead constrained intrinsics that are still around only because the exception behavior is "strict" when a transform pass has proved to itself that no exception can ever take place.

We do run InstCombiner often enough that it is a decent place to eliminate useless instructions. I don't think it is ideal, but it's fine.

[sepavloff]

In D118426#3338322, @kpn wrote:

In D118426#3337963, @sepavloff wrote:

In D118426#3337489, @kpn wrote:

It seems like these dangling, useless instructions would interfere with subsequent optimizations until finally they might or might not get removed here. And constant folding isn't sufficient to duplicate the logic of the transform pass that determined the instruction could be deleted.

InstCombine is called several times, it calls constant folding and instruction simplification functions. It looks like a good place to get rid of such useless instructions.

My point is that it shouldn't be needed for eliminating dead constrained intrinsics that are still around only because the exception behavior is "strict" when a transform pass has proved to itself that no exception can ever take place.

Absolutely. It requires that transformations that may remove intrinsic calls be aware about constrained intrinsics. Removing unneeded instruction in separate pass still might make sense in some cases, similar to separate DCE passes.

We do run InstCombiner often enough that it is a decent place to eliminate useless instructions. I don't think it is ideal, but it's fine.

It is not ideal, but InstCombiner would be a transformation pass that would know about constrained intrinsics. It calls SimplifyCall (and consequently calls ConstantFoldCall), so it already has all necessary information to make removal of constfolded intrinsics, no need to reevaluate them. At least removal of unneeded intrinsic call here wouldn't cost much.

[sepavloff]

Ping.

[sepavloff]

Does something prevent this change from accepting?

Now replaced instructions remain in the generated code, which makes their constant folding useless.

[sepavloff]

Ping.

[andrew.w.kaylor]

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

1057

Relying on SimplifyCall() here to determine whether the call has side effects is still more restrictive than necessary. For example, if the exception behavior argument is not fp::ExceptionBehavior::ebStrict and the call has no users, it can be removed even if the arguments are non-constant or the operation would raise an exception.

[sepavloff]

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

1057

Actually there is no additional restrictions. wouldInstructionBeTriviallyDead already recognizes that a constrained intrinsic calls with the exception behavior argument other than ebStrict may be removed. So if such call result is not used, it is removed in prepareICWorklistFromFunction and does not participate in instruction combining. If such call is replaced by SimplifyCall, it is removed due to the same reason. The test f_eval_maytrap demonstrates this case.

[sepavloff]

Ping.

[efriedma]

llvm/include/llvm/Analysis/InstructionSimplify.h

305 ↗

(On Diff #408942)

"is actually absent".

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

4134 ↗

(On Diff #408942)

It's not clear to me this is the only reason a constrained FP intrinsic can be returned. And even if it were, it's a fragile invariant.

Would it make sense to just have isInstructionTriviallyDead() do the right thing here? We already do something similar with isMathLibCallNoop().

[kpn]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

4134 ↗

(On Diff #408942)

With "strict" exception behavior we are not allowed to eliminate any run-time traps. I still do not know how isInstructionTriviallyDead() can trivially know that an instruction will never trap and thus can know that removing the instruction is trivially safe.

[efriedma]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

4134 ↗

(On Diff #408942)

It can prove it exactly the same way this patch is trying to do: by constant-folding the operation.

[sepavloff]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

4134 ↗

(On Diff #408942)

Would it make sense to just have isInstructionTriviallyDead() do the right thing here? We already do something similar with isMathLibCallNoop().

It can prove it exactly the same way this patch is trying to do: by constant-folding the operation.

It could but it seems to be impractical. isInstructionTriviallyDead is called very often, so it must work enough fast. Making constant evaluations in every invocation of it would substantially increase compile time. The evaluation is made using APFloat, so even for simple operations like llvm.experimental.constrained.fadd it involves enough heavy computations. And for functions like llvm.experimental.constrained.fptosi or llvm.experimental.constrained.cos execution time would be definitely large.

Of course, most users wouldn't suffer from this, because the do not use 'strict' exception behavior. However in strict mode compile time may be unexplainably large and it eventually be noticed and considered as a bug.

Also isInstructionTriviallyDead is already overloaded with various checks and attempt adding constant evaluation to it may be considered as undesirable.

On the other hand, the assumption described in this comment is actually obvious and natural. If the code that simplifies IR constructs decides that this constrained intrinsic call may be replaced by some other constructs, we may ignore the side effect of this call. In other words the simplifying code is responsible for taking into account the side effect of the intrinsic.

[kpn]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

4134 ↗

(On Diff #408942)

Personally, I would like to see isInstructionTriviallyDead() do the right thing. But the current plan to call back in to see if we can constant fold doesn't scale. Look at my changes to InstSimplify to see simplification cases that aren't constant folding.

In other words the simplifying code is responsible for taking into account the side effect of the intrinsic.

Yes. Serge hit the nail on the head.

If we go the route of having isInstructionTriviallyDead() re-derive the fact that an instruction can be eliminated by re-running code to determine it is safe then we need to also re-determine that the non-constant folding simplifications are safe. We would also need to re-run any other transformation-handling code that comes up in the future. That seems terribly heavyweight, and bad layering as well.

In an earlier ticket we saw Serge's suggestion of having transformation passes annotate instructions so the existing isInstructionTriviallyDead() implementation will recognize they can be trivially deleted. This suggestion was rejected for reasons I never saw explained. I'd love to understand the issues with that proposed solution at least.

That leaves us with options like this ticket, where instructions to be deleted hang around for multiple passes until InstCombine gets run. This solution also has, to a lesser extent I think, some of the scalability issues outlined above on top of being fragile as @efriedma pointed out.

Does anyone have any other suggestions that would solve the problem without creating new ones? Anyone?

[sepavloff]

Fixed comment and rebased

[efriedma]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

4134 ↗

(On Diff #408942)

In an earlier ticket we saw Serge's suggestion of having transformation passes annotate instructions so the existing isInstructionTriviallyDead() implementation will recognize they can be trivially deleted

Which is this? Don't recall seeing this.

---

I think to avoid the issue with hacking at InstCombinerImpl::run, you can do something like the following in visitCallInst:

if (CI.use_empty() && isa<ConstrainedFPIntrinsic>(CI)) {
  if (SimplifyCall(&CI, SQ.getWithInstruction(&CI))) {
    eraseInstFromFunction(CI);
    return nullptr;
  }
}

[sepavloff]

Simplify code

[sepavloff]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

4134 ↗

(On Diff #408942)

In an earlier ticket we saw Serge's suggestion of having transformation passes annotate instructions so the existing isInstructionTriviallyDead() implementation will recognize they can be trivially deleted

Which is this? Don't recall seeing this.

Such idea was proposed some time ago but was never implemented. Actually it looks like a complex solution because it requires some mechanism to detect points when intrinsic must be reevaluated because its arguments are changed. It increases cost of using constant evaluator in isInstructionTriviallyDead.

I think to avoid the issue with hacking at InstCombinerImpl::run, you can do something like the following in visitCallInst:

Indeed, it make the patch even more compact. Thank you!

[efriedma]

LGTM

[sepavloff]

Thanks!

[sepavloff]

See the discussion in https://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20220502/1034841.html.

[sepavloff]

Updated the patch according to the discussion

• function SimplifyConstrainedFPCall was added,
• simplified code in InstCombineCalls.cpp

[reames]

LGTM w/suggest comment change applied.

llvm/include/llvm/Analysis/InstructionSimplify.h

307 ↗

(On Diff #427589)

Suggested wording change:

Unlike other SimplifyX routines, this function provides an additional contract. Specifically, it guarantees that if simplification succeeds that the intrinsic is side effect free. As a result, successful simplification can be used to delete the intrinsic not just replace its result.

[sepavloff]

Thanks!

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

if (auto *IIFVTy = dyn_cast<FixedVectorType>(II->getType())) {
     }
   }
 
   if (II->isCommutative()) {
     if (CallInst *NewCall = canonicalizeConstantArg0ToArg1(CI))
       return NewCall;
   }
 
+  if (auto *ConstrainedIntr = dyn_cast<ConstrainedFPIntrinsic>(II)) {
+    if (Value *V = transformConstrainedCall(*ConstrainedIntr)) {
+      CI.replaceAllUsesWith(V);
+      return ConstrainedIntr;
+    }
+  }
+
   Intrinsic::ID IID = II->getIntrinsicID();
   switch (IID) {
   case Intrinsic::objectsize:
     if (Value *V = lowerObjectSizeCall(II, DL, &TLI, /*MustSucceed=*/false))
       return replaceInstUsesWith(CI, V);
     return nullptr;
   case Intrinsic::abs: {
     Value *IIOperand = II->getArgOperand(0);
InstCombinerImpl::transformCallThroughTrampoline(CallBase &Call,
 
   // Replace the trampoline call with a direct call.  Since there is no 'nest'
   // parameter, there is no need to adjust the argument list.  Let the generic
   // code sort out any function type mismatches.
   Constant *NewCallee = ConstantExpr::getBitCast(NestF, CalleeTy);
   Call.setCalledFunction(FTy, NewCallee);
   return &Call;
 }
+
+Value *InstCombinerImpl::transformConstrainedCall(ConstrainedFPIntrinsic &CI) {
+  if (Value *Res = SimplifyInstruction(&CI, SQ.getWithInstruction(&CI))) {
+    if (CI.getNumUses() == 0)
+      CI.addFnAttr(Attribute::ReadNone);
+    return Res;
+  }
+  return nullptr;
+}

llvm/lib/Transforms/InstCombine/InstCombineInternal.h

bool OptimizeOverflowCheck(Instruction::BinaryOps BinaryOp, bool IsSigned,
                              Instruction &CtxI, Value *&OperationResult,
                              Constant *&OverflowResult);
 
   Instruction *visitCallBase(CallBase &Call);
   Instruction *tryOptimizeCall(CallInst *CI);
   bool transformConstExprCastCall(CallBase &Call);
   Instruction *transformCallThroughTrampoline(CallBase &Call,
                                               IntrinsicInst &Tramp);
+  Value *transformConstrainedCall(ConstrainedFPIntrinsic &CI);
 
   Value *simplifyMaskedLoad(IntrinsicInst &II);
   Instruction *simplifyMaskedStore(IntrinsicInst &II);
   Instruction *simplifyMaskedGather(IntrinsicInst &II);
   Instruction *simplifyMaskedScatter(IntrinsicInst &II);
 
   /// Transform (zext icmp) to bitwise / integer operations in order to
   /// eliminate it.

llvm/test/Transforms/InstCombine/constrained.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -S -instcombine %s | FileCheck %s
+
+; Treatment of operation with unused result.
+
+; If operation does not raise exceptions, it may be removed even in strict mode.
+define float @f_unused_precise() #0 {
+; CHECK-LABEL: @f_unused_precise(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    ret float 1.000000e+00
+;
+entry:
+  %result = call float @llvm.experimental.constrained.fadd.f32(float 1.0, float 1.0, metadata !"round.upward", metadata !"fpexcept.strict") #0
+  ret float 1.0
+}
+
+; If operation raises exceptions, it cannot be removed in strict mode.
+define float @f_unused_strict() #0 {
+; CHECK-LABEL: @f_unused_strict(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[RESULT:%.*]] = call float @llvm.experimental.constrained.fdiv.f32(float 1.000000e+00, float 3.000000e+00, metadata !"round.tonearest", metadata !"fpexcept.strict") #[[ATTR0:[0-9]+]]
+; CHECK-NEXT:    ret float 1.000000e+00
+;
+entry:
+  %result = call float @llvm.experimental.constrained.fdiv.f32(float 1.0, float 3.0, metadata !"round.tonearest", metadata !"fpexcept.strict") #0
+  ret float 1.0
+}
+
+; If operation raises exceptions, it can be removed in non-strict mode.
+define float @f_unused_ignore() #0 {
+; CHECK-LABEL: @f_unused_ignore(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    ret float 1.000000e+00
+;
+entry:
+  %result = call float @llvm.experimental.constrained.fdiv.f32(float 1.0, float 3.0, metadata !"round.towardzero", metadata !"fpexcept.ignore") #0
+  ret float 1.0
+}
+
+; If operation raises exceptions, it can be removed in non-strict mode even if rounding mode is dynamic.
+define float @f_unused_dynamic_ignore() #0 {
+; CHECK-LABEL: @f_unused_dynamic_ignore(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    ret float 1.000000e+00
+;
+entry:
+  %result = call float @llvm.experimental.constrained.fdiv.f32(float 1.0, float 3.0, metadata !"round.dynamic", metadata !"fpexcept.ignore") #0
+  ret float 1.0
+}
+
+; If operation raises exceptions, it can be removed in "maytrap" mode.
+define float @f_unused_maytrap() #0 {
+; CHECK-LABEL: @f_unused_maytrap(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    ret float 1.000000e+00
+;
+entry:
+  %result = call float @llvm.experimental.constrained.fdiv.f32(float 1.0, float 3.0, metadata !"round.tonearest", metadata !"fpexcept.maytrap") #0
+  ret float 1.0
+}
+
+; Constant evaluation.
+
+; If operation does not raise exceptions, it may be folded even in strict mode.
+define float @f_eval_precise() #0 {
+; CHECK-LABEL: @f_eval_precise(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    ret float 2.000000e+00
+;
+entry:
+  %result = call float @llvm.experimental.constrained.fadd.f32(float 1.0, float 1.0, metadata !"round.upward", metadata !"fpexcept.strict") #0
+  ret float %result
+}
+
+; If operation raises exceptions, it cannot be folded in strict mode.
+define float @f_eval_strict() #0 {
+; CHECK-LABEL: @f_eval_strict(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[RESULT:%.*]] = call float @llvm.experimental.constrained.fdiv.f32(float 1.000000e+00, float 3.000000e+00, metadata !"round.upward", metadata !"fpexcept.strict") #[[ATTR0]]
+; CHECK-NEXT:    ret float [[RESULT]]
+;
+entry:
+  %result = call float @llvm.experimental.constrained.fdiv.f32(float 1.0, float 3.0, metadata !"round.upward", metadata !"fpexcept.strict") #0
+  ret float %result
+}
+
+; If operation raises exceptions, it can be folded in non-strict mode.
+define float @f_eval_ignore() #0 {
+; CHECK-LABEL: @f_eval_ignore(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    ret float 0x3FD5555540000000
+;
+entry:
+  %result = call float @llvm.experimental.constrained.fdiv.f32(float 1.0, float 3.0, metadata !"round.downward", metadata !"fpexcept.ignore") #0
+  ret float %result
+}
+
+; if result is imprecise, it cannot be folded if rounding mode is dynamic.
+define float @f_eval_dynamic_ignore() #0 {
+; CHECK-LABEL: @f_eval_dynamic_ignore(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[RESULT:%.*]] = call float @llvm.experimental.constrained.fdiv.f32(float 1.000000e+00, float 3.000000e+00, metadata !"round.dynamic", metadata !"fpexcept.ignore") #[[ATTR0]]
+; CHECK-NEXT:    ret float [[RESULT]]
+;
+entry:
+  %result = call float @llvm.experimental.constrained.fdiv.f32(float 1.0, float 3.0, metadata !"round.dynamic", metadata !"fpexcept.ignore") #0
+  ret float %result
+}
+
+; If result is imprecise and rounding mode is not dynamic, operation can be folded in "maytrap" mode.
+define float @f_eval_maytrap() #0 {
+; CHECK-LABEL: @f_eval_maytrap(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    ret float 0x3FD5555560000000
+;
+entry:
+  %result = call float @llvm.experimental.constrained.fdiv.f32(float 1.0, float 3.0, metadata !"round.tonearest", metadata !"fpexcept.maytrap") #0
+  ret float %result
+}
+
+
+declare float @llvm.experimental.constrained.fadd.f32(float, float, metadata, metadata)
+declare float @llvm.experimental.constrained.fdiv.f32(float, float, metadata, metadata)
+
+attributes #0 = { strictfp }