| Issue |
204136
|
| Summary |
[ISel] Implement known bits optimization for `@llvm.pext` and `@llvm.pdep`
|
| Labels |
new issue
|
| Assignees |
|
| Reporter |
eisenwave
|
This is a follow-up to https://github.com/llvm/llvm-project/issues/172857
#200570 already implemented known bits optimization on the initial PR, but it was yoinked to trim down the pull request size. I have a fully working implementation sitting somewhere on a backup branch.
https://github.com/llvm/llvm-project/pull/200570/changes/d07f81e181408e12d59fa5c6362647adb941822e
```cpp
KnownBits KnownBits::bext(const KnownBits &LHS, const KnownBits &RHS) {
// For each source position I where mask[I] could be set, the output index j
// lies in [M0, M1] where these track the range of possible set-bit counts
// seen so far in mask.
//
// The output bit j
// - can be 0 if any candidate LHS[I] could be zero or popcount(mask) could
// be <= j, and
// - can be 1 only if some candidate LHS[I] could be one and popcount(mask)
// is known > j.
unsigned BitWidth = LHS.getBitWidth();
KnownBits Res(BitWidth);
Res.setAllConflict();
unsigned M0 = 0, M1 = 0;
for (unsigned I = 0; I < BitWidth; ++I) {
if (!RHS.Zero[I]) {
APInt Range = APInt::getBitsSet(BitWidth, M0, M1 + 1);
if (!LHS.Zero[I])
Res.Zero &= ~Range; // some position in Range could be 1
if (!LHS.One[I])
Res.One &= ~Range; // some position in Range could be 0
}
if (RHS.One[I])
++M0, ++M1;
else if (!RHS.Zero[I])
++M1;
}
// Output positions j >= M0 may have no source (popcount(mask) <= j), in
// which case they default to zero.
Res.One &= APInt::getLowBitsSet(BitWidth, M0);
return Res;
}
KnownBits KnownBits::bdep(const KnownBits &LHS, const KnownBits &RHS) {
// For each output position I where mask[I] could be set, the source index j
// lies in [M0, M1] where these track possible counts of set mask bits < I.
//
// The output bit
// - can be 0 if mask[I] or any candidate LHS[j] could be zero, and
// - can be 1 only if both mask[I] and some candidate LHS[j] could be one.
unsigned BitWidth = LHS.getBitWidth();
KnownBits Res(BitWidth);
Res.setAllConflict();
unsigned M0 = 0, M1 = 0;
for (unsigned I = 0; I < BitWidth; ++I) {
if (!RHS.One[I])
Res.One.clearBit(I); // mask[I] could be 0 -> output[I] could be 0
if (!RHS.Zero[I]) {
APInt Range = APInt::getBitsSet(BitWidth, M0, M1 + 1);
if (!Range.isSubsetOf(LHS.One))
Res.One.clearBit(I); // some candidate could be 0
if (!Range.isSubsetOf(LHS.Zero))
Res.Zero.clearBit(I); // some candidate could be 1
}
if (RHS.One[I])
++M0, ++M1;
else if (!RHS.Zero[I])
++M1;
}
return Res;
}
```
```cpp
; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
; RUN: opt -passes=instcombine -S < %s | FileCheck %s
; bext(x, 0b00001111) produces a 4-bit result; bit 4 and above are always zero.
define i1 @bext_high_bits_zero(i8 %x) nounwind {
; CHECK-LABEL: @bext_high_bits_zero(
; CHECK-NEXT: ret i1 true
;
%bext = call i8 @llvm.bext.i8(i8 %x, i8 15)
%and = and i8 %bext, 240
%r = icmp eq i8 %and, 0
ret i1 %r
}
; bext(x, 0b11001100) can produce up to 4 bits; bits 4..7 are zero.
define i1 @bext_sparse_mask_high_zero(i8 %x) nounwind {
; CHECK-LABEL: @bext_sparse_mask_high_zero(
; CHECK-NEXT: ret i1 true
;
%bext = call i8 @llvm.bext.i8(i8 %x, i8 204)
%and = and i8 %bext, 240
%r = icmp eq i8 %and, 0
ret i1 %r
}
; bext(x, 0) -> all bits zero: the AND with any mask is always zero.
define i1 @bext_zero_mask_known_zero(i8 %x) nounwind {
; CHECK-LABEL: @bext_zero_mask_known_zero(
; CHECK-NEXT: ret i1 true
;
%bext = call i8 @llvm.bext.i8(i8 %x, i8 0)
%r = icmp eq i8 %bext, 0
ret i1 %r
}
; Negative: bext(x, 0b11001100) can have bits 0-3 set; can't prove bit 0 is zero.
define i1 @bext_low_bits_not_known(i8 %x) nounwind {
; CHECK-LABEL: @bext_low_bits_not_known(
; CHECK-NEXT: [[BEXT:%.*]] = call i8 @llvm.bext.i8(i8 [[X:%.*]], i8 -52)
; CHECK-NEXT: [[AND:%.*]] = and i8 [[BEXT]], 1
; CHECK-NEXT: [[R:%.*]] = icmp eq i8 [[AND]], 0
; CHECK-NEXT: ret i1 [[R]]
;
%bext = call i8 @llvm.bext.i8(i8 %x, i8 204)
%and = and i8 %bext, 1
%r = icmp eq i8 %and, 0
ret i1 %r
}
; bdep(x, 0b11110000): bits 0..3 of result are always zero.
define i1 @bdep_low_bits_zero(i8 %x) nounwind {
; CHECK-LABEL: @bdep_low_bits_zero(
; CHECK-NEXT: ret i1 true
;
%bdep = call i8 @llvm.bdep.i8(i8 %x, i8 240)
%and = and i8 %bdep, 15
%r = icmp eq i8 %and, 0
ret i1 %r
}
; bdep(x, 0b00001111): bits 4..7 of result are always zero.
define i1 @bdep_high_bits_zero(i8 %x) nounwind {
; CHECK-LABEL: @bdep_high_bits_zero(
; CHECK-NEXT: ret i1 true
;
%bdep = call i8 @llvm.bdep.i8(i8 %x, i8 15)
%and = and i8 %bdep, 240
%r = icmp eq i8 %and, 0
ret i1 %r
}
; bdep(x, 0) -> all bits zero.
define i1 @bdep_zero_mask_known_zero(i8 %x) nounwind {
; CHECK-LABEL: @bdep_zero_mask_known_zero(
; CHECK-NEXT: ret i1 true
;
%bdep = call i8 @llvm.bdep.i8(i8 %x, i8 0)
%r = icmp eq i8 %bdep, 0
ret i1 %r
}
; Negative: bdep(x, 0b11001100) can have bits 2,3,6,7 set.
define i1 @bdep_mask_bits_not_known(i8 %x) nounwind {
; CHECK-LABEL: @bdep_mask_bits_not_known(
; CHECK-NEXT: [[BDEP:%.*]] = call i8 @llvm.bdep.i8(i8 [[X:%.*]], i8 -52)
; CHECK-NEXT: [[R:%.*]] = icmp sgt i8 [[BDEP]], -1
; CHECK-NEXT: ret i1 [[R]]
;
%bdep = call i8 @llvm.bdep.i8(i8 %x, i8 204)
%and = and i8 %bdep, 128
%r = icmp eq i8 %and, 0
ret i1 %r
}
declare i8 @llvm.bext.i8(i8, i8)
declare i8 @llvm.bdep.i8(i8, i8)
```
![]()
_______________________________________________
llvm-bugs mailing list
[email protected]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-bugs
