This is an archive of the discontinued LLVM Phabricator instance.

[InstCombine] Fold overflow bit of [u|s]mul.with.overflow in a poison-safe way
ClosedPublic

Authored by aqjune on Apr 27 2021, 7:42 PM.

Details

Summary

As discussed in D101191, this patch adds a poison-safe folding of overflow bit check:

  %Op0 = icmp ne i4 %X, 0
  %Agg = call { i4, i1 } @llvm.[us]mul.with.overflow.i4(i4 %X, i4 %Y)
  %Op1 = extractvalue { i4, i1 } %Agg, 1
  %ret = select i1 %Op0, i1 %Op1, i1 false
=>
  %Y.fr = freeze %Y
  %Agg = call { i4, i1 } @llvm.[us]mul.with.overflow.i4(i4 %X, i4 %Y.fr)
  %Op1 = extractvalue { i4, i1 } %Agg, 1
  %ret = %Op1

https://alive2.llvm.org/ce/z/zgPUGT
https://alive2.llvm.org/ce/z/h2gZ_6

Note that there are cases where inserting freeze is not necessary: e.g. %Y is noundef.
In this case, LLVM is already good because %ret is already successfully folded into and,
triggering the pre-existing optimization in InstSimplify: https://godbolt.org/z/v6qena15K

Diff Detail

Event Timeline

aqjune created this revision.Apr 27 2021, 7:42 PM
aqjune requested review of this revision.Apr 27 2021, 7:42 PM
Herald added a project: Restricted Project. · View Herald TranscriptApr 27 2021, 7:42 PM
aqjune added inline comments.Apr 27 2021, 7:43 PM
llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp
2588

The function below is based on InstSimplify's version.

llvm/test/Transforms/PhaseOrdering/unsigned-multiply-overflow-check.ll
8 ↗(On Diff #341062)

-instcombine-unsafe-select-transform=0 is added to show the impact of this patch.

spatel added inline comments.Apr 28 2021, 5:53 AM
llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp
2588

Duplicating so much code feels wrong. Could we just call the simplify code from here with something like:

// Simulate a bitwise logic op for a select with a constant operand. 
if (match(FalseVal, m_Zero())) {
  if (Value *Simplified =
          SimplifyAndInst(CondVal, TrueVal, SQ.getWithInstruction(&SI))) {
    // create freeze and return
  }
}
if (match(TrueVal, m_One())) {
  if (Value *Simplified =
          SimplifyOrInst(CondVal, FalseVal, SQ.getWithInstruction(&SI))) {
    // create freeze and return
  }
}
llvm/test/Transforms/PhaseOrdering/unsigned-multiply-overflow-check.ll
8 ↗(On Diff #341062)

I would prefer to leave this file unchanged with this patch, so we still have an indicator to represent the overall behavior of the optimizer.

We should add minimal tests for this patch under test/Transforms/InstCombine. These could be based on the test files from D65150 / D65151 - just replace the and/or logic instructions with select?

aqjune added inline comments.Apr 28 2021, 10:03 AM
llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp
2588

I think we still need to look into the expression because we should determine which variable to freeze.

If there is a header file that InstSimplify and InstCombine can share would be a great place for this function?

llvm/test/Transforms/PhaseOrdering/unsigned-multiply-overflow-check.ll
8 ↗(On Diff #341062)

No problem, I'll make tests like those in the next iteration.

spatel added inline comments.Apr 28 2021, 1:04 PM
llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp
2588

Don't we only need to freeze the operand that is not in the icmp expression? That is, CondVal of the select must match as an icmp with a non-zero operand, and it's the other value that must be frozen.

I don't know of a shared header in Analysis for general logic. We do have things like VectorUtils and CmpInstAnalysis, so we could invent some new place.

I have a really 'are you nuts' proposal.
How about we canonicalize all i1 and/or's into select form?
Then that instsimplify code becomes dead, and we can simply port it here.
And we'll weed out all the remaining patterns that still only handle the and/or forms/

I have a really 'are you nuts' proposal.
How about we canonicalize all i1 and/or's into select form?
Then that instsimplify code becomes dead, and we can simply port it here.
And we'll weed out all the remaining patterns that still only handle the and/or forms/

This will reduce a lot of complexity between having both select and or/and i1, but one concern is that select isn't commutative. :(
I mean, and i1 %a, %b == and i1 %b, %a, but in case of select select i1 %a, %b, false != select i1 %b, %a, false due to poison.
So we'll have to carefully choose which form to use, which can be a hard problem.

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp
2588

Don't we only need to freeze the operand that is not in the icmp expression? That is, CondVal of the select must match as an icmp with a non-zero operand, and it's the other value that must be frozen.

Yep, the variable is the one to freeze.
My concern was about code duplication: the pattern matching code should still be copied here to pick the variable...

I don't know of a shared header in Analysis for general logic. We do have things like VectorUtils and CmpInstAnalysis, so we could invent some new place.

Actually to me having a separate header like CmpInstAnalysis and VectorUtil looks great.
Would creating something like OverflowInstAnalysis make sense?
If it is too much, having InstSimplifyUtils.h in llvm/lib/Analysis & including it from InstCombineSelect.cpp?

spatel added inline comments.Apr 29 2021, 4:47 AM
llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp
2588

An Overflow analysis file sounds good. At this point, I think there's only the mul code that would go in there, but we might find other common code later.

aqjune updated this revision to Diff 341760.Apr 29 2021, 8:52 PM
  • Move the function into the new header file
  • Update ValueTracking's impliesPoison to convert select to and/or if valid.

This avoids redundant freeze insertion (see div-by-0-guard-before-smul_ov-not.ll 's t1_commutative)

aqjune updated this revision to Diff 341761.Apr 29 2021, 8:53 PM

clang-format

aqjune marked an inline comment as done.Apr 29 2021, 8:57 PM
aqjune added inline comments.
llvm/lib/Analysis/ValueTracking.cpp
5023

This update adds an inferences that if a is poison, extract(mul_with_overflow(a, _), _) is also poison.

This enables transformation

select(extract(mul_with_overflow(a, _), _), (a == 0), false)
=>
and(extract(mul_with_overflow(a, _), _), (a == 0))
```.
spatel accepted this revision.Apr 30 2021, 5:28 AM

LGTM - see inline for some small improvements.

llvm/include/llvm/Analysis/OverflowInstAnalysis.h
34

This is confusing if we do not have the context of the callers that we can see in this patch.
The comment should say something like: "Match one of the patterns up to the select/logic op. Callers are expected to align that with the operands of the select/logic op user."

36

"is used" -> "are used"

37

"is one" -> "match one"

llvm/lib/Analysis/ValueTracking.cpp
5024

Use "is_contained" ?
Is it possible to separate this change (with an independent test)?

This revision is now accepted and ready to land.Apr 30 2021, 5:28 AM
This revision was landed with ongoing or failed builds.May 1 2021, 7:55 PM
This revision was automatically updated to reflect the committed changes.
aqjune marked 4 inline comments as done.May 1 2021, 8:04 PM