Page MenuHomePhabricator

[InstrSimplify] fold sdiv if two operands are negatived and non-overflow
ClosedPublic

Authored by shchenz on Jul 16 2018, 8:42 AM.

Details

Summary

We add folding support for add instruction in D49216. Test cases are added at rL337179.

we should also fold for sdiv instruction if sdiv's two operands are negatived leverage new added interface isKnownNegation() in D49216. for example:

define i32 @negated_operand(i32 %x) {
  %negx = sub nsw i32 0, %x
  %div = sdiv i32 %negx, %x
  ret i32 %div
}

can be folded to

define i32 @negated_operand(i32 %x) {
  ret i32 -1
}

Note: we must ensure sdiv two operands are non-overflow. Otherwise, the optimization is not right.
Result from Alive:
testing transform:

%sub = sub i8 0, %x
%div = sdiv i8 %x, %sub

=>

%div = i8 -1

testing result:
ERROR: Mismatch in values of i8 %div
Example:
%x i8 = 0x80 (128, -128)
%sub i8 = 0x80 (128, -128)
Source value: 0x01 (1)
Target value: 0xFF (255, -1)

Diff Detail

Repository
rL LLVM

Event Timeline

shchenz created this revision.Jul 16 2018, 8:42 AM

Should we generalize this, so we can include 'srem' (doesn't need 'nsw')?
https://rise4fun.com/Alive/tme

It's probably better to make that a separate patch in any case.

I'm going to take a break for a few days, so I may not be able to continue the review promptly. Adding Roman as a potential reviewer.

llvm/lib/Analysis/InstructionSimplify.cpp
1087 ↗(On Diff #155693)

This is not the right place to add logic. It should go in here instead:
static Value *SimplifySDivInst()
...because that is called internally when the external user makes a call to llvm::SimplifyBinOp()

1092–1100 ↗(On Diff #155693)

I don't think this behaves as you're expecting. Please add a test like this:

define i32 @irrelevant_sub(i32 %t) {
  %x = sub i32 %t, 5
  %negx = sub nsw i32 0, %x
  %div = sdiv i32 %x, %negx
  ret i32 %div
}

It would be better to match the patterns with m_Neg separately from the case with (x-y)/(y-x).

shchenz updated this revision to Diff 155822.Jul 17 2018, 2:28 AM

fix Sanjay's comments

@spatel Hi Sanjay, thanks for your comments. I have updated accordingly. For srem instruction, I will make another patch for it. Have a good break^-^

In general looks sane, but a few notes.

This fold does require nsw on sub, but i'm not seeing tests for that.

define i32 @negated_operand_bad(i32 %x) {
  %negx = sub i32 0, %x ; not nsw
  %div = sdiv i32 %negx, %x
  ret i32 %div
}
define i32 @knownnegation_bad(i32 %x, i32 %y) {
  %xy = sub nsw i32 %x, %y
  %yx = sub i32 %y, %x ; not nsw
  %div = sdiv i32 %xy, %yx
  ret i32 %div
}
define i32 @knownnegation_bad(i32 %x, i32 %y) {
  %xy = sub i32 %x, %y ; not nsw
  %yx = sub nsw i32 %y, %x
  %div = sdiv i32 %xy, %yx
  ret i32 %div
}
define i32 @knownnegation_bad(i32 %x, i32 %y) {
  %xy = sub i32 %x, %y ; not nsw
  %yx = sub i32 %y, %x ; not nsw
  %div = sdiv i32 %xy, %yx
  ret i32 %div
}
llvm/test/Transforms/InstSimplify/sdiv.ll
40 ↗(On Diff #155822)

Same as with D49423, i'd like to see a bit more tests:

define <3 x i32> @negated_operand_vec_undef(<3 x i32> %x) {
  %negx = sub nsw <3 x i32> <i32 0, i32 undef, i32 0>, %x
  %rem = sdiv <3 x i32> %negx, %x
  ret <3 x i32> %rem
}
define <2 x i32> @negated_operand_vec_nonsplat(<2 x i32> %x) {
  %negx = sub nsw <2 x i32> <i32 0, 1>, %x ; not 0, don't fold
  %rem = sdiv <2 x i32> %negx, %x
  ret <2 x i32> %rem
}

@lebedev.ri Hi Roman, thanks very much for your comments. I wrongly assumed we only need the cases which are truly transformed by code patch. I will add the cases you point out.

shchenz updated this revision to Diff 156433.Jul 19 2018, 11:37 PM

fix Roman's comments.

lebedev.ri accepted this revision.Jul 20 2018, 1:45 AM

Hmm, if this has issues, then i'm not seeing them.
Please commit tests now, wait 24h just in case anyone else wants to comment, and then feel free to land this.

llvm/include/llvm/Analysis/ValueTracking.h
105 ↗(On Diff #156433)

s/checkNSW/NeedNSW/

105 ↗(On Diff #156433)

Also maybe add a comment showing two examples that are handled?

llvm/lib/Analysis/InstructionSimplify.cpp
1085 ↗(On Diff #156433)

This is also valid with NUW https://rise4fun.com/Alive/zb6
But we do not care because that is 0 https://godbolt.org/g/G55Np1

This revision is now accepted and ready to land.Jul 20 2018, 1:45 AM
shchenz marked 2 inline comments as done.Jul 20 2018, 6:45 AM

@lebedev.ri Hi Roman, thanks for your comments. Testcases are committed. And waiting for other reviewer's comment.

@lebedev.ri Hi Roman, thanks for your comments. Testcases are committed.

(You most likely want to rebase this to signify that)

shchenz updated this revision to Diff 156482.Jul 20 2018, 7:06 AM

Fix Roman's comments

new testcases are added at rL337549

This revision was automatically updated to reflect the committed changes.