----------------------------------------
define i3 @src(i3 %a, i3 %b, i3 %c) {
%0:
%or1 = or i3 %b, %c
%not1 = xor i3 %or1, 7
%and1 = and i3 %a, %not1
%xor1 = xor i3 %b, %c
%or2 = or i3 %xor1, %a
%not2 = xor i3 %or2, 7
%or3 = or i3 %and1, %not2
ret i3 %or3
}
=>
define i3 @tgt(i3 %a, i3 %b, i3 %c) {
%0:
%obc = or i3 %b, %c
%xbc = xor i3 %b, %c
%o = or i3 %a, %xbc
%and = and i3 %obc, %o
%r = xor i3 %and, 7
ret i3 %r
}
Transformation seems to be correct!Details
Details
Diff Detail
Diff Detail
Event Timeline
Comment Actions
A side note: a shorter form would be (~a & b & c) | ~(b | c) -> ~((a & b) | (b ^ c)), however it is only mathematically correct and does not verify since it is more undefined than the source:
----------------------------------------
define i4 @src(i4 %a, i4 %b, i4 %c) {
%0:
%or1 = or i4 %b, %c
%not1 = xor i4 %or1, 15
%and1 = and i4 %a, %not1
%xor1 = xor i4 %b, %c
%or2 = or i4 %xor1, %a
%not2 = xor i4 %or2, 15
%or3 = or i4 %and1, %not2
ret i4 %or3
}
=>
define i4 @tgt(i4 %a, i4 %b, i4 %c) {
%0:
%and = and i4 %a, %b
%not1 = xor i4 %b, %c
%or = or i4 %and, %not1
%not2 = xor i4 %or, 15
ret i4 %not2
}
Transformation doesn't verify!
ERROR: Target's return value is more undefined
Example:
i4 %a = #xf (15, -1)
i4 %b = undef
i4 %c = #xf (15, -1)
Source:
i4 %or1 = #xf (15, -1)
i4 %not1 = #x0 (0)
i4 %and1 = #x0 (0)
i4 %xor1 = any
i4 %or2 = #xf (15, -1)
i4 %not2 = #x0 (0)
i4 %or3 = #x0 (0)
Target:
i4 %and = #x6 (6)
i4 %not1 = #x8 (8, -8)
i4 %or = #xe (14, -2)
i4 %not2 = #x1 (1)
Source value: #x0 (0)
Target value: #x1 (1)| llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp | ||
|---|---|---|
| 2834 | I have realized it is essentially the same LHS as above. And then above is the same as another one above. Will combine these, the only real difference is one use counts, but that can be done inside the outer if statement. As the number of patterns grow I have to keep it under control somehow and factor. | |
Comment Actions
In the light of D113526 this needs to be rebased and handle inverted pattern:
(a | ~(b & c)) & ~(a & (b ^ c)) --> ~(a | b) | (a ^ b ^ c)
----------------------------------------
define i4 @src(i4 %a, i4 %b, i4 %c) {
%0:
%and1 = and i4 %b, %c
%not1 = xor i4 %and1, 15
%or1 = or i4 %not1, %a
%xor1 = xor i4 %b, %c
%and2 = and i4 %xor1, %a
%not2 = xor i4 %and2, 15
%and3 = and i4 %or1, %not2
ret i4 %and3
}
=>
define i4 @tgt(i4 %a, i4 %b, i4 %c) {
%0:
%xor1 = xor i4 %b, %c
%xor2 = xor i4 %xor1, %a
%or1 = or i4 %a, %b
%not1 = xor i4 %or1, 15
%or2 = or i4 %xor2, %not1
ret i4 %or2
}
Transformation seems to be correct!Comment Actions
Double-check that I'm getting the pattern right, but I don't think the 'or' side of this should have 6 instructions. There has to be a smarter way (!), but I worked this out on paper with a truth table:
https://alive2.llvm.org/ce/z/BP3ZZm
Comment Actions
Changed to shorter form as proposed by @spatel:
(~(a | b) & c) | ~(c | (a ^ b)) -> ~((a | b) & (c | (b ^ a)))
| llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp | ||
|---|---|---|
| 1797 | Both "A | B" and "(A ^ B) | C" are existing values in this expression. Does it not make sense to capture those instead of cloning them? Note: that also means we're only creating 2 instructions total ('and' + 'not'), so this transform only needs a single one-use constraint. | |
Comment Actions
Capture one more subexpression.
| llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp | ||
|---|---|---|
| 1797 | Thanks! A good catch. | |
Comment Actions
The patch was reverted since the flipped case produces more undefined result. I am not sure how did that sneak, but I am reopening it and limiting to only 'or' case.
Comment Actions
Ah, that is unfortunate. We may need to freeze the inputs if we're changing the number/order of uses:
https://alive2.llvm.org/ce/z/JXQ2Rn
I think it's worth leaving the tests in place in case we find some way around that limitation. Also, add a code comment about undef, so we remember why the 'and' sibling is not included.
Comment Actions
Retained the 'and' tests, but added comment why is it not done in both source and test.
Both "A | B" and "(A ^ B) | C" are existing values in this expression. Does it not make sense to capture those instead of cloning them?
Note: that also means we're only creating 2 instructions total ('and' + 'not'), so this transform only needs a single one-use constraint.