Page MenuHomePhabricator

[DAGcombine] Teach the combiner about -a = ~a + 1
ClosedPublic

Authored by deadalnix on May 6 2018, 11:56 AM.

Details

Summary

This include variant for add, uaddo and addcarry. usubo and subcarry require the carry to be flipped to preserve semantic, but we chose to do the transform anyway in that case as to push the transform down the carry chain.

Diff Detail

Repository
rL LLVM

Event Timeline

deadalnix created this revision.May 6 2018, 11:56 AM
RKSimon added inline comments.May 9 2018, 8:18 AM
lib/CodeGen/SelectionDAG/DAGCombiner.cpp
2199 ↗(On Diff #145406)

Move this inside flipBoolean() ?

2263 ↗(On Diff #145406)

full stop: // fold (uaddo (xor a, -1), 1) -> (usub 0, a) and flip carry.

spatel added a comment.May 9 2018, 8:30 AM

We should have minimal dedicated tests for these patterns. Something like this:

; simple fold - no overflow intrinsic/node
define i32 @inc_not(i32 %a) {
  %nota = xor i32 %a, -1
  %r = add i32 %nota, 1
  ret i32 %r
}

%ov32 = type { i32, i1 }
declare %ov32 @llvm.uadd.with.overflow.i32(i32, i32)

define void @uaddo1_not(i32 %a, i32* %p0, i1* %p1) {
  %nota = xor i32 %a, -1
  %uaddo = call %ov32 @llvm.uadd.with.overflow.i32(i32 %nota, i32 1)
  %r0 = extractvalue %ov32 %uaddo, 0
  %r1 = extractvalue %ov32 %uaddo, 1
  store i32 %r0, i32* %p0
  store i1 %r1, i1* %p1
  ret void
}

; another test for addcarry
lib/CodeGen/SelectionDAG/DAGCombiner.cpp
2057–2059 ↗(On Diff #145406)

Use llvm::isBitwiseNot()? I don't think we care about vectors in the motivating cases, but you could extend that to handle a vector constant if it matters.

On 2nd thought, do we need this? It's not necessary for the test shown here, and instcombine already does that transform. If the pattern is created here in the DAG, it should have its own test (ie, this could be an independent patch).

2264–2266 ↗(On Diff #145406)

Same as above - use isBitwiseNot()?

deadalnix added inline comments.May 26 2018, 4:57 AM
lib/CodeGen/SelectionDAG/DAGCombiner.cpp
2057–2059 ↗(On Diff #145406)

You are correct that my motivation example doesn't require this. However, it seemed weird tome to to it for uaddo and addcarry, but not plain old add.

deadalnix updated this revision to Diff 148713.May 26 2018, 5:37 AM

Use isBitwiseNot
Merge flipBooleanConstant into flipBoolean
Add more specific test cases.

spatel accepted this revision.Jun 4 2018, 10:10 AM

LGTM.

This revision is now accepted and ready to land.Jun 4 2018, 10:10 AM
This revision was automatically updated to reflect the committed changes.