This is an archive of the discontinued LLVM Phabricator instance.

[Reassociate] Cleanup minor missed optimizations
ClosedPublic

Authored by wristow on Jul 12 2022, 6:17 PM.

Details

Summary

In analyzing issue #56483, it was noticed that running opt with
-reassociate was missing some minor optimizations. For example,
there were cases where the running opt on IR with floating-point
instructions that have the fast flags applied, sometimes resulted in
less efficient code than the input IR (things like dead instructions
left behind, and missed reassociations). These were sometimes noted
in the test-files with TODOs, to investigate further. This commit
fixes some of these problems, removing some TODOs in the process.

FTR, I refer to these as "minor" missed optimizations, because when
running a full clang/llvm compilation, these inefficiencies are not
happening, as other passes clean that residue up. Regardless, having
cleaner IR produced by opt, makes assessing the quality of fixes done
in opt easier.

Diff Detail

Unit TestsFailed

Event Timeline

wristow created this revision.Jul 12 2022, 6:17 PM
Herald added a project: Restricted Project. · View Herald TranscriptJul 12 2022, 6:17 PM
Herald added a subscriber: hiraditya. · View Herald Transcript
wristow requested review of this revision.Jul 12 2022, 6:17 PM
Herald added a project: Restricted Project. · View Herald TranscriptJul 12 2022, 6:17 PM

To add some context to make it easier to review, the approach taken here of adding a ReassociatePass::OrderedSet parameter (named ToRedo) to the function LinearizeExprTree , is the same technique already used in two other functions in "Reassociate.cpp": NegateValue and BreakUpSubtract.

Is it possible to create an integer (mul and sub) test that also has this problem?

llvm/lib/Transforms/Scalar/Reassociate.cpp
580–581

I know this is existing code, but for readability, I'd rename this "Neg" instead of "Tmp" and remove the partially-braced nested-ifs:

Instruction *Neg;
if ((Opcode == Instruction::Mul && match(Op, m_Neg(m_Value()))) ||
    (Opcode == Instruction::FMul && match(Op, m_FNeg(m_Value()))) &&
    match(Op, m_Instruction(Neg)) {
580–581

NI -> Mul ?

580–581

Add a line to this comment to explain why we add users of the negate to the redo list?

584

UTmp -> UserBO

Is it possible to create an integer (mul and sub) test that also has this problem?

I expect so. I'll look into creating one.

llvm/lib/Transforms/Scalar/Reassociate.cpp
580–581

Will do.

580–581

Sounds good.

580–581

Will do.

584

Will do.

wristow updated this revision to Diff 444461.Jul 13 2022, 5:20 PM

Addressed review comments from @spatel , except for adding an integer test.

If I take a similar integer test:

; (-X)*Y + Z -> Z-X*Y
define i32 @int_test7(i32 %X, i32 %Y, i32 %Z) {
  %A = sub i32 0, %X
  %B = mul i32 %A, %Y
  %C = add i32 %B, %Z
  ret i32 %C
}

the change does clean the results up somewhat, but not as completely as the floating-point version. Specifically, without the change, the above test is reassociated to:

define i32 @int_test7(i32 %X, i32 %Y, i32 %Z) {
  %1 = sub i32 0, 0
  %A = mul i32 %Y, %X
  %B = mul i32 %A, -1
  %C = add i32 %B, %Z
  ret i32 %C
}

So it has the unused instruction %1 = sub i32 0, 0 remaining.

And with the change, that instruction is deleted:

define i32 @int_test7(i32 %X, i32 %Y, i32 %Z) {
  %A = mul i32 %Y, %X
  %B = mul i32 %A, -1
  %C = add i32 %B, %Z
  ret i32 %C
}

The equivalent FP version transforms the computation of %B into a multiply of positive 1 (which is then optimized away), and %C is then computed with a subtraction, rather than an addition. So the FP version has only two arithmetic instructions (multiply and subtract), whereas the integer version ends up as above (multiply, multiply (by negative 1), addition).

Looking into this difference, I see it's because the routine ReassociatePass::OptimizeInst has:

// Canonicalize negative constants out of expressions.
if (Instruction *Res = canonicalizeNegFPConstants(I))
  I = Res;

which nicely handles this multiply by -1.0 for the floating-point case, but there isn't an equivalent canonicalizeNegIntConstants concept.

wristow marked 3 inline comments as done.Jul 13 2022, 5:21 PM
spatel accepted this revision.Jul 14 2022, 7:38 AM

Addressed review comments from @spatel , except for adding an integer test.

...

the change does clean the results up somewhat, but not as completely as the floating-point version. Specifically, without the change, the above test is reassociated to:

I'd prefer to have that test, so we have coverage for the integer path added with this patch. It's still an improvement even if it's not as big as the FP side.
Other than that, LGTM.

This revision is now accepted and ready to land.Jul 14 2022, 7:38 AM

I'd prefer to have that test, so we have coverage for the integer path added with this patch. It's still an improvement even if it's not as big as the FP side.
Other than that, LGTM.

I was just thinking the same thing and adding that test (with a TODO)!

wristow updated this revision to Diff 444659.Jul 14 2022, 7:48 AM

Added an integer version of a reassociation test, including a TODO of a possible further improvement.

Thanks for the review @spatel !

wristow closed this revision.Jul 14 2022, 8:33 AM

Committed at 230c8c56f21cfe4e23a24793f3137add1af1d1f0.

Manually closing this (forgot to add the "Differential Revision" note to the commit message).