Page MenuHomePhabricator

[InstCombine] Missed optimization in math expression: pow multiplications
Needs ReviewPublic

Authored by Quolyk on Dec 27 2017, 11:30 PM.

Details

Summary

This patch enables folding following expressions under -ffast-math flag:
pow(a, b) * a -> pow(a, b+1)
(1/a) * pow(a, b) -> pow(a, b-1)
pow(a, b) * pow(c, b) -> pow(a*c, b)
pow(a, b) * pow(a, c) -> pow(a, b+c)
Motivation: https://bugs.llvm.org/show_bug.cgi?id=35595.

Diff Detail

Event Timeline

Quolyk created this revision.Dec 27 2017, 11:30 PM

I'm slightly worried about all this bunch of missing instcombines added, as InstCombine is already really really slow.

That said, this one is probably one we really want. I skimmed the code quickly and I think it's correct, but please wait for somebody else to take a look

Why is this patch WIP? The mentioned case of 'pow(a, x) * a * a * a * a -> pow(a, x+4)' is handled already by this patch.

lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
389–392

You mentioned that you see warnings without explicitly setting these to nullptr in Xcode. I use Xcode as an IDE too, but I don't see any warnings like that when I remove the nullptrs.

If this is really a problem, then you must be getting hundreds of these warnings for existing code that does not initialize things like this? I'd prefer not to bloat the code unnecessarily.

397

Need to handle commuted versions too (please add a test):

define double @pow_ab_x_a_fast_commute(double %a, double %b)  {
  %c = fdiv double 1.0, %a  ; defeat complexity-based canonicalization of operands
  %p = call fast double @llvm.pow.f64(double %a, double %b)
  %mul = fmul fast double %c, %p
  ret double %mul
}
398–399

Here and below: use m_Specific instead of the trailing check for equality?

407–408

Please use variable names that match the formulas in the code comments for better readability.

Quolyk updated this revision to Diff 128876.Jan 7 2018, 9:53 AM

pow(a, x) * a * a * a * a emits to

define double @pow_ab_x_aaaa_fast(double %a, double %x) {
  %1 = call fast double @llvm.pow.f64(double %a, double %x)
  %2 = fmul fast double %a, %a
  %3 = fmul fast double %2, %2
  %mul4 = fmul fast double %3, %1
  ret double %mul4
}

I don't see obvious ways to fold these instructions. I Would appreciate if somebody could help me with this.

Quolyk marked 4 inline comments as done.Jan 7 2018, 9:54 AM
Quolyk retitled this revision from [WIP][InstCombine] Missed optimization in math expression: aggressive optimization with pow to [InstCombine] Missed optimization in math expression: aggressive optimization with pow.Jan 14 2018, 11:58 PM
Quolyk added a reviewer: efriedma.

pow(a, x) * a * a * a * a emits to

define double @pow_ab_x_aaaa_fast(double %a, double %x) {
  %1 = call fast double @llvm.pow.f64(double %a, double %x)
  %2 = fmul fast double %a, %a
  %3 = fmul fast double %2, %2
  %mul4 = fmul fast double %3, %1
  ret double %mul4
}

I don't see obvious ways to fold these instructions. I Would appreciate if somebody could help me with this.

This looks like it went through -reassociate first? I was checking with a straight IR translation, so we're just multiplying by 'a' over and over. This would require more complex logic, so that's a different patch (and I'm not sure where it would belong).

lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
397

This comment was marked 'Done', but I don't see code to account for this or the test that I suggested.

Quolyk marked an inline comment as not done.Jan 17 2018, 11:01 AM
Quolyk added inline comments.
lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
397

My bad, I thought fdiv_pow_ab_a test would be enough.

Quolyk updated this revision to Diff 185021.Feb 4 2019, 3:33 AM

Update tests. Apply patch only for pow multiplications. Pow divisions will be considered in different patch.

Herald added a project: Restricted Project. · View Herald TranscriptFeb 4 2019, 3:33 AM
Quolyk retitled this revision from [InstCombine] Missed optimization in math expression: aggressive optimization with pow to [InstCombine] Missed optimization in math expression: pow multiplications.Feb 4 2019, 3:34 AM
Quolyk edited the summary of this revision. (Show Details)
Quolyk added a reviewer: lebedev.ri.
Quolyk removed rL LLVM as the repository for this revision.
spatel added a comment.Feb 4 2019, 6:29 AM

This patch is trying to do too many things at once. Please split only the 1st transform (pow(X, Y) * X -> pow(X, Y+1)) into its own patch, and let's continue looking at that alone as a 1st step. You should consider (and include tests for) these variations:

  1. Commuted operands for fmul.
  2. Extra uses of the pow result.
  3. Vector types.
  4. Additional FMF.

We don't necessarily need tests for every permutation of those, but there needs to be more coverage than what we see here currently.

test/Transforms/InstCombine/fmul-pow.ll
28–29

This is a misleading test name. This isn't the commuted version of the previous test - the fmul does not have a common operand with the pow().

I think you want something like this:

declare double @call_f64(double)
define double @pow_ab_a_reassoc(double %p, double %b) {
  %a = call double @call_f64(double %p)  ; thwart complexity-based canonicalization
  %pow = call double @llvm.pow.f64(double %a, double %b)
  %mul = fmul reassoc double %a, %pow
  ret double %mul
}
davide removed a reviewer: davide.Feb 4 2019, 7:16 AM