Page MenuHomePhabricator

Implementing missing trigonometric optimizations
Needs ReviewPublic

Authored by cs15btech11041 on Jan 2 2018, 12:53 AM.

Details

Summary

Here we have implemented the following missing trigonometric optimizations.

  1. tan(x)*cos(x)=sin(x)
  2. sin(x)*cos(x) = sin(2*x)/2
  3. sin(x)/tan(x)=cos(x);
  4. tan(x)/sin(x)=1/cos(x);

Here is the reference to the missing optimization reported on bugzilla.

https://bugs.llvm.org/show_bug.cgi?id=35602

Diff Detail

Repository
rL LLVM

Event Timeline

cs15btech11041 created this revision.Jan 2 2018, 12:53 AM
asb added a subscriber: asb.

As mentioned in llvm-dev, it looks like David Majnemer and Craig Topper might be appropriate reviewers for this patch (or can perhaps help to suggest other reviewers).

It looks like you've run clang-format on the entire lib/Transforms/InstCombine/InstructionCombining.cpp file. This makes it harder to review the changes you've made. Best practice is to only clang-format lines that you touch. I use the git-clang-format helper script for this, and it looks like clang-format-diff.py can help if you're using SVN:

https://github.com/llvm-mirror/clang/blob/master/tools/clang-format/git-clang-format
https://github.com/llvm-mirror/clang/blob/master/tools/clang-format/clang-format-diff.py

fhahn added a subscriber: fhahn.Jan 2 2018, 3:06 AM

Thanks for your patch!

Usually it is easier to review smaller patches. Splitting it up into 4 patches for the 4 different cases you implemented would make it slightly easier to reason about the 4 unrelated transformation in isolation.

This may need special guard with fast-math flags (precision, etc), no?

davide requested changes to this revision.Jan 2 2018, 3:21 AM
davide added a subscriber: davide.

Meta point: It's unclear to me whether this is something profitable to implement.
Sure, you can probably take a textbook and implement all the possible identities written there, but, what's the point?

I looked and it seems other compilers (most notably, GCC) don't implement at least the first transformation you implemented (I didn't bother to check the others).
https://godbolt.org/g/kKP5PW

tl;dr: what's your motivation?

This revision now requires changes to proceed.Jan 2 2018, 3:21 AM
davide added a subscriber: scanon.Jan 2 2018, 3:22 AM

Something else you may want to keep in mind is that these transformations may introduce dramatic rounding errors, so they need some thoughts/analysis before they can go in (cc: @scanon), even under -ffast-math.

spatel added a subscriber: spatel.Jan 2 2018, 7:50 AM
aprantl added a subscriber: aprantl.Jan 2 2018, 9:54 AM
aprantl added inline comments.
lib/Transforms/InstCombine/InstructionCombining.cpp
1431

Please remove the \brief, it is redundant.

1442

Please always use full sentences in documentation:
// Return nullptr if argument to calls are not same.

cs15btech11041 updated this revision to Diff 128488.EditedJan 2 2018, 9:11 PM
cs15btech11041 edited the summary of this revision. (Show Details)

Updates made:

  1. Made the test cases more modular as mentioned in the comments.
  2. Instead of clang format on entire InstructionCombine.cpp clang-formatted only the modified/inserted code for better understanding.

3.Comments improved.

In D41659#965688, @asb wrote:

As mentioned in llvm-dev, it looks like David Majnemer and Craig Topper might be appropriate reviewers for this patch (or can perhaps help to suggest other reviewers).

Hi, thanks for the comment. Thanks for adding appropriate reviewers for the patch.

It looks like you've run clang-format on the entire lib/Transforms/InstCombine/InstructionCombining.cpp file. This makes it harder to review the changes you've made. Best practice is to only clang-format lines that you touch. I use the git-clang-format helper script for this, and it looks like clang-format-diff.py can help if you're using SVN:

As suggested, I have updated the diff file with clang format only on the section of code modified/inserted. Hopefully it is easier for the review. Thanks for the suggestion.

https://github.com/llvm-mirror/clang/blob/master/tools/clang-format/git-clang-format
https://github.com/llvm-mirror/clang/blob/master/tools/clang-format/clang-format-diff.py

Thanks for your patch!

Usually it is easier to review smaller patches. Splitting it up into 4 patches for the 4 different cases you implemented would make it slightly easier to reason about the 4 unrelated transformation in isolation.

Yes. Thank you for the suggestions. I have updated the diff to incorporate the changes you suggested. And submitted different test case for each optimization in isolation. Hope it has made it easier to review the patch.

This may need special guard with fast-math flags (precision, etc), no?

I have added FastMathFlagGuard Guard to the IRBuilder. And also copied the ffast-math flags of the division/multiplication instruction. To the new trigonometric/multiplication/division instruction inserted. As for precision, we are replacing two trigonometric functions with single equivalent trigonometric function with fast math flag guards. Also the type which we are specifying in CreateCall is same as that of the division/multiplication instruction. Hence would have the same type and precision. Please let me know if I did not answer your question.

Meta point: It's unclear to me whether this is something profitable to implement.
Sure, you can probably take a textbook and implement all the possible identities written there, but, what's the point?

I looked and it seems other compilers (most notably, GCC) don't implement at least the first transformation you implemented (I didn't bother to check the others).
https://godbolt.org/g/kKP5PW

tl;dr: what's your motivation?

Hi, thanks for the comments. the motivation for taking this up were two things.
First was missing optimization reported on bugzilla. However it mentions only the first optimization implemented. I have implemented for other similar cases as well.

https://bugs.llvm.org/show_bug.cgi?id=35602

Second, replacing two trigonometric operations with single trigonometric operation or with a mul/div instruction would save considerable clock cycles. It says trigonometric operations require almost five time the clock cycles needed by multiplication/division.Also to add we are reducing the code size. As one could see from the test cases, the number of instructions after transformations <= number of instructions before. And to that we are also saving clock cycles.

https://stackoverflow.com/questions/2479517/is-trigonometry-computationally-expensive

Added the right file for sin_div_tan.ll test case (incorrect was added in previous commit).

spatel added a comment.Jan 3 2018, 6:49 AM

Thanks for your patch!

Usually it is easier to review smaller patches. Splitting it up into 4 patches for the 4 different cases you implemented would make it slightly easier to reason about the 4 unrelated transformation in isolation.

Strongly agree. I understand there's a common theme here, but it will save time making redundant comments if we start with a patch for just one of these transforms.

The structure of the patch is not correct. We don't need a trig helper function because it's impossible for an integer op like mul or udiv to have an FP operand like llvm.sin.
Please have a look at these patches for the correct way to match intrinsics and libcalls:
D41322
D41283
D41389

fhahn added a comment.Jan 3 2018, 7:49 AM

In D41659#966397, @cs15btech11041 wrote:
Yes. Thank you for the suggestions. I have updated the diff to incorporate the changes you suggested. And submitted different test case for each optimization in isolation. Hope it has made it easier to review the patch.

I think I wasn't too clear, sorry. I meant splitting up the whole patch into 4 different patches and submitting them as separate reviewss, i.e. one review only including the code & test for tan(x)*cos(x)=sin(x), one for sin(x)*cos(x) = sin(2*x)/2 and so on.

This also makes it slightly easier to decide if each transform is beneficial on a case-by-case basis.