[GlobalISel] Add `G_FSHL` and `G_FSHR` to computeKnownBits by def3r · Pull Request #191260 · llvm/llvm-project

def3r · 2026-04-09T18:00:45Z

Ported impl from SelectionDAG::computeKnownBits.

Tests are based on AArch64/GlobalISel/knownbits-shl.mir

github-actions · 2026-04-09T18:01:03Z

Thank you for submitting a Pull Request (PR) to the LLVM Project!

This PR will be automatically labeled and the relevant teams will be notified.

If you wish to, you can add reviewers by using the "Reviewers" section on this page.

If this is not working for you, it is probably because you do not have write permissions for the repository. In which case you can instead tag reviewers by name in a comment by using @ followed by their GitHub username.

If you have received no comments on your PR for a week, you can request a review by "ping"ing the PR by adding a comment “Ping”. The common courtesy "ping" rate is once a week. Please remember that you are asking for valuable time from other developers.

If you have further questions, they may be answered by the LLVM GitHub User Guide.

You can also ask questions in a comment on this PR, on the LLVM Discord or on the forums.

llvmbot · 2026-04-09T18:01:39Z

@llvm/pr-subscribers-llvm-support
@llvm/pr-subscribers-backend-aarch64

@llvm/pr-subscribers-llvm-globalisel

Author: Ayaan (def3r)

Changes

Ported impl from SelectionDAG::computeKnownBits.

Tests are based on AArch64/GlobalISel/knownbits-shl.mir

Ref: #150515

Full diff: https://github.com/llvm/llvm-project/pull/191260.diff

2 Files Affected:

(modified) llvm/lib/CodeGen/GlobalISel/GISelValueTracking.cpp (+34)
(added) llvm/test/CodeGen/AArch64/GlobalISel/knownbits-fshl-fshr.mir (+295)

diff --git a/llvm/lib/CodeGen/GlobalISel/GISelValueTracking.cpp b/llvm/lib/CodeGen/GlobalISel/GISelValueTracking.cpp
index f0b455fbdc7d0..cb1a46abdd086 100644
--- a/llvm/lib/CodeGen/GlobalISel/GISelValueTracking.cpp
+++ b/llvm/lib/CodeGen/GlobalISel/GISelValueTracking.cpp
@@ -560,6 +560,40 @@ void GISelValueTracking::computeKnownBitsImpl(Register R, KnownBits &Known,
     Known.One = Known.One.rotr(Amt);
     break;
   }
+  case TargetOpcode::G_FSHL:
+  case TargetOpcode::G_FSHR: {
+    MachineInstr *AmtOpMI = MRI.getVRegDef(MI.getOperand(3).getReg());
+    auto MaybeAmtOp = isConstantOrConstantSplatVector(*AmtOpMI, MRI);
+    if (!MaybeAmtOp)
+      break;
+
+    unsigned Amt = MaybeAmtOp->urem(BitWidth);
+
+    // For fshl, 0-shift returns the 1st arg.
+    // For fshr, 0-shift returns the 2nd arg.
+    if (Amt == 0) {
+      computeKnownBitsImpl(
+          MI.getOperand(Opcode == TargetOpcode::G_FSHL ? 1 : 2).getReg(), Known,
+          DemandedElts, Depth + 1);
+      break;
+    }
+
+    // fshl: (X << (Z % BW)) | (Y >> (BW - (Z % BW)))
+    // fshr: (X << (BW - (Z % BW))) | (Y >> (Z % BW))
+    computeKnownBitsImpl(MI.getOperand(1).getReg(), Known, DemandedElts,
+                         Depth + 1);
+    computeKnownBitsImpl(MI.getOperand(2).getReg(), Known2, DemandedElts,
+                         Depth + 1);
+    if (Opcode == TargetOpcode::G_FSHL) {
+      Known <<= Amt;
+      Known2 >>= BitWidth - Amt;
+    } else {
+      Known <<= BitWidth - Amt;
+      Known2 >>= Amt;
+    }
+    Known = Known.unionWith(Known2);
+    break;
+  }
   case TargetOpcode::G_INTTOPTR:
   case TargetOpcode::G_PTRTOINT:
     if (DstTy.isVector())
diff --git a/llvm/test/CodeGen/AArch64/GlobalISel/knownbits-fshl-fshr.mir b/llvm/test/CodeGen/AArch64/GlobalISel/knownbits-fshl-fshr.mir
new file mode 100644
index 0000000000000..202a40831145e
--- /dev/null
+++ b/llvm/test/CodeGen/AArch64/GlobalISel/knownbits-fshl-fshr.mir
@@ -0,0 +1,295 @@
+# NOTE: Assertions have been autogenerated by utils/update_givaluetracking_test_checks.py UTC_ARGS: --version 6
+# RUN: llc -mtriple aarch64 -passes="print<gisel-value-tracking>" %s -o - 2>&1 | FileCheck %s
+
+---
+name:            Cst
+body:             |
+  bb.1:
+  ; CHECK-LABEL: name: @Cst
+  ; CHECK-NEXT: %0:_ KnownBits:11100000 SignBits:3
+  ; CHECK-NEXT: %1:_ KnownBits:00001111 SignBits:4
+  ; CHECK-NEXT: %2:_ KnownBits:00000010 SignBits:6
+  ; CHECK-NEXT: %3:_ KnownBits:10000000 SignBits:1
+    %0:_(s8) = G_CONSTANT i8 224
+    %1:_(s8) = G_CONSTANT i8 15
+    %2:_(s8) = G_CONSTANT i8 2
+    %3:_(s8) = G_FSHL %0, %1, %2
+...
+---
+name:            CstBig
+body:             |
+  bb.1:
+  ; CHECK-LABEL: name: @CstBig
+  ; CHECK-NEXT: %0:_ KnownBits:11111001 SignBits:5
+  ; CHECK-NEXT: %1:_ KnownBits:11100000 SignBits:3
+  ; CHECK-NEXT: %2:_ KnownBits:00000110 SignBits:5
+  ; CHECK-NEXT: %3:_ KnownBits:01111000 SignBits:1
+    %0:_(s8) = G_CONSTANT i8 249
+    %1:_(s8) = G_CONSTANT i8 224
+    %2:_(s8) = G_CONSTANT i8 6
+    %3:_(s8) = G_FSHL %0, %1, %2
+...
+---
+name:            CstSext
+body:             |
+  bb.1:
+  ; CHECK-LABEL: name: @CstSext
+  ; CHECK-NEXT: %0:_ KnownBits:10000001 SignBits:1
+  ; CHECK-NEXT: %1:_ KnownBits:00000100 SignBits:5
+  ; CHECK-NEXT: %2:_ KnownBits:11111000 SignBits:5
+  ; CHECK-NEXT: %3:_ KnownBits:11100000 SignBits:3
+  ; CHECK-NEXT: %4:_ KnownBits:00000011 SignBits:6
+  ; CHECK-NEXT: %5:_ KnownBits:11000111 SignBits:2
+    %0:_(s8) = G_CONSTANT i8 129
+    %1:_(s8) = G_CONSTANT i8 4
+    %2:_(s8) = G_ASHR %0, %1
+    %3:_(s8) = G_CONSTANT i8 224
+    %4:_(s8) = G_CONSTANT i8 3
+    %5:_(s8) = G_FSHL %2, %3, %4
+...
+---
+name:            CstSextBig
+body:             |
+  bb.1:
+  ; CHECK-LABEL: name: @CstSextBig
+  ; CHECK-NEXT: %0:_ KnownBits:10000001 SignBits:1
+  ; CHECK-NEXT: %1:_ KnownBits:00000100 SignBits:5
+  ; CHECK-NEXT: %2:_ KnownBits:11111000 SignBits:5
+  ; CHECK-NEXT: %3:_ KnownBits:11100000 SignBits:3
+  ; CHECK-NEXT: %4:_ KnownBits:00000110 SignBits:5
+  ; CHECK-NEXT: %5:_ KnownBits:00111000 SignBits:2
+    %0:_(s8) = G_CONSTANT i8 129
+    %1:_(s8) = G_CONSTANT i8 4
+    %2:_(s8) = G_ASHR %0, %1
+    %3:_(s8) = G_CONSTANT i8 224
+    %4:_(s8) = G_CONSTANT i8 6
+    %5:_(s8) = G_FSHL %2, %3, %4
+...
+---
+name:            ScalarVar
+body:             |
+  bb.1:
+  ; CHECK-LABEL: name: @ScalarVar
+  ; CHECK-NEXT: %0:_ KnownBits:???????? SignBits:1
+  ; CHECK-NEXT: %1:_ KnownBits:???????? SignBits:1
+  ; CHECK-NEXT: %2:_ KnownBits:???????? SignBits:1
+    %0:_(s8) = COPY $b0
+    %1:_(s8) = COPY $b1
+    %2:_(s8) = G_FSHL %0, %0, %1
+...
+---
+name:            ScalarCst
+body:             |
+  bb.1:
+  ; CHECK-LABEL: name: @ScalarCst
+  ; CHECK-NEXT: %0:_ KnownBits:???????? SignBits:1
+  ; CHECK-NEXT: %1:_ KnownBits:???????? SignBits:1
+  ; CHECK-NEXT: %2:_ KnownBits:00000011 SignBits:6
+  ; CHECK-NEXT: %3:_ KnownBits:???????? SignBits:1
+    %0:_(s8) = COPY $b0
+    %1:_(s8) = COPY $b1
+    %2:_(s8) = G_CONSTANT i8 3
+    %3:_(s8) = G_FSHL %0, %1, %2
+...
+---
+name:            VectorSimple
+body:             |
+  bb.1:
+  ; CHECK-LABEL: name: @VectorSimple
+  ; CHECK-NEXT: %0:_ KnownBits:0000000000010011 SignBits:11
+  ; CHECK-NEXT: %1:_ KnownBits:1111111100000000 SignBits:8
+  ; CHECK-NEXT: %2:_ KnownBits:0000000000000011 SignBits:14
+  ; CHECK-NEXT: %3:_ KnownBits:0000000000010011 SignBits:11
+  ; CHECK-NEXT: %4:_ KnownBits:1111111100000000 SignBits:8
+  ; CHECK-NEXT: %5:_ KnownBits:0000000000000011 SignBits:14
+  ; CHECK-NEXT: %6:_ KnownBits:0000000010011111 SignBits:8
+    %0:_(s16) = G_CONSTANT i16 19
+    %1:_(s16) = G_CONSTANT i16 65280
+    %2:_(s16) = G_CONSTANT i16 3
+    %3:_(<4 x s16>) = G_BUILD_VECTOR %0, %0, %0, %0
+    %4:_(<4 x s16>) = G_BUILD_VECTOR %1, %1, %1, %1
+    %5:_(<4 x s16>) = G_BUILD_VECTOR %2, %2, %2, %2
+    %6:_(<4 x s16>) = G_FSHL %3, %4, %5
+...
+---
+name:            VectorCst
+body:             |
+  bb.1:
+  ; CHECK-LABEL: name: @VectorCst
+  ; CHECK-NEXT: %0:_ KnownBits:???????????????? SignBits:1
+  ; CHECK-NEXT: %1:_ KnownBits:???????????????? SignBits:1
+  ; CHECK-NEXT: %2:_ KnownBits:0000000000000011 SignBits:14
+  ; CHECK-NEXT: %3:_ KnownBits:0000000000000011 SignBits:14
+  ; CHECK-NEXT: %4:_ KnownBits:???????????????? SignBits:1
+    %0:_(<4 x s16>) = COPY $d0
+    %1:_(<4 x s16>) = COPY $d1
+    %2:_(s16) = G_CONSTANT i16 3
+    %3:_(<4 x s16>) = G_BUILD_VECTOR %2, %2, %2, %2
+    %4:_(<4 x s16>) = G_FSHL %0, %1, %3
+...
+---
+name:            VectorCst36
+body:             |
+  bb.1:
+  ; CHECK-LABEL: name: @VectorCst36
+  ; CHECK-NEXT: %0:_ KnownBits:0000000000000011 SignBits:14
+  ; CHECK-NEXT: %1:_ KnownBits:0000000000000110 SignBits:13
+  ; CHECK-NEXT: %2:_ KnownBits:0000000000000?1? SignBits:13
+  ; CHECK-NEXT: %3:_ KnownBits:0000000000000?1? SignBits:13
+  ; CHECK-NEXT: %4:_ KnownBits:???????????????? SignBits:1
+    %0:_(s16) = G_CONSTANT i16 3
+    %1:_(s16) = G_CONSTANT i16 6
+    %2:_(<4 x s16>) = G_BUILD_VECTOR %0, %1, %1, %0
+    %3:_(<4 x s16>) = G_BUILD_VECTOR %0, %1, %1, %0
+    %4:_(<4 x s16>) = G_FSHL %2, %2, %3
+...
+---
+name:            VectorCst3unknown
+body:             |
+  bb.1:
+  ; CHECK-LABEL: name: @VectorCst3unknown
+  ; CHECK-NEXT: %0:_ KnownBits:???????????????? SignBits:1
+  ; CHECK-NEXT: %1:_ KnownBits:???????????????? SignBits:1
+  ; CHECK-NEXT: %2:_ KnownBits:???????????????? SignBits:1
+  ; CHECK-NEXT: %3:_ KnownBits:0000000000000011 SignBits:14
+  ; CHECK-NEXT: %4:_ KnownBits:???????????????? SignBits:1
+  ; CHECK-NEXT: %5:_ KnownBits:???????????????? SignBits:1
+    %0:_(<4 x s16>) = COPY $d0
+    %1:_(<4 x s16>) = COPY $d1
+    %2:_(s16) = COPY $h0
+    %3:_(s16) = G_CONSTANT i16 3
+    %4:_(<4 x s16>) = G_BUILD_VECTOR %2, %3, %3, %2
+    %5:_(<4 x s16>) = G_FSHL %0, %1, %4
+...
+---
+name:            VectorSext
+body:             |
+  bb.1:
+  ; CHECK-LABEL: name: @VectorSext
+  ; CHECK-NEXT: %0:_ KnownBits:11101110 SignBits:3
+  ; CHECK-NEXT: %1:_ KnownBits:00001111 SignBits:4
+  ; CHECK-NEXT: %2:_ KnownBits:1111111111101110 SignBits:11
+  ; CHECK-NEXT: %3:_ KnownBits:0000000000001111 SignBits:12
+  ; CHECK-NEXT: %4:_ KnownBits:1111111111101110 SignBits:11
+  ; CHECK-NEXT: %5:_ KnownBits:0000000000001111 SignBits:12
+  ; CHECK-NEXT: %6:_ KnownBits:0000000000000011 SignBits:14
+  ; CHECK-NEXT: %7:_ KnownBits:0000000000000110 SignBits:13
+  ; CHECK-NEXT: %8:_ KnownBits:0000000000000?1? SignBits:13
+  ; CHECK-NEXT: %9:_ KnownBits:???????????????? SignBits:1
+    %0:_(s8) = G_CONSTANT i8 238
+    %1:_(s8) = G_CONSTANT i8 15
+    %2:_(s16) = G_SEXT %0(s8)
+    %3:_(s16) = G_SEXT %1(s8)
+    %4:_(<4 x s16>) = G_BUILD_VECTOR %2, %2, %2, %2
+    %5:_(<4 x s16>) = G_BUILD_VECTOR %3, %3, %3, %3
+    %6:_(s16) = G_CONSTANT i16 3
+    %7:_(s16) = G_CONSTANT i16 6
+    %8:_(<4 x s16>) = G_BUILD_VECTOR %6, %7, %7, %6
+    %9:_(<4 x s16>) = G_FSHL %4, %5, %8
+...
+---
+name:            FSHLless
+body:             |
+  bb.1:
+  ; CHECK-LABEL: name: @FSHLless
+  ; CHECK-NEXT: %0:_ KnownBits:???????? SignBits:1
+  ; CHECK-NEXT: %1:_ KnownBits:???????? SignBits:1
+  ; CHECK-NEXT: %2:_ KnownBits:???????????????? SignBits:9
+  ; CHECK-NEXT: %3:_ KnownBits:???????????????? SignBits:9
+  ; CHECK-NEXT: %4:_ KnownBits:0000000000000011 SignBits:14
+  ; CHECK-NEXT: %5:_ KnownBits:???????????????? SignBits:1
+    %0:_(s8) = COPY $b0
+    %1:_(s8) = COPY $b1
+    %2:_(s16) = G_SEXT %0(s8)
+    %3:_(s16) = G_SEXT %1(s8)
+    %4:_(s16) = G_CONSTANT i16 3
+    %5:_(s16) = G_FSHL %2, %3, %4
+...
+---
+name:            FSHLeq
+body:             |
+  bb.1:
+  ; CHECK-LABEL: name: @FSHLeq
+  ; CHECK-NEXT: %0:_ KnownBits:???????? SignBits:1
+  ; CHECK-NEXT: %1:_ KnownBits:???????? SignBits:1
+  ; CHECK-NEXT: %2:_ KnownBits:???????????????? SignBits:9
+  ; CHECK-NEXT: %3:_ KnownBits:???????????????? SignBits:9
+  ; CHECK-NEXT: %4:_ KnownBits:0000000000001000 SignBits:12
+  ; CHECK-NEXT: %5:_ KnownBits:???????????????? SignBits:1
+    %0:_(s8) = COPY $b0
+    %1:_(s8) = COPY $b1
+    %2:_(s16) = G_SEXT %0(s8)
+    %3:_(s16) = G_SEXT %1(s8)
+    %4:_(s16) = G_CONSTANT i16 8
+    %5:_(s16) = G_FSHL %2, %3, %4
+...
+---
+name:            FSHLmore
+body:             |
+  bb.1:
+  ; CHECK-LABEL: name: @FSHLmore
+  ; CHECK-NEXT: %0:_ KnownBits:???????? SignBits:1
+  ; CHECK-NEXT: %1:_ KnownBits:???????? SignBits:1
+  ; CHECK-NEXT: %2:_ KnownBits:???????????????? SignBits:9
+  ; CHECK-NEXT: %3:_ KnownBits:???????????????? SignBits:9
+  ; CHECK-NEXT: %4:_ KnownBits:0000000000001101 SignBits:12
+  ; CHECK-NEXT: %5:_ KnownBits:???????????????? SignBits:1
+    %0:_(s8) = COPY $b0
+    %1:_(s8) = COPY $b1
+    %2:_(s16) = G_SEXT %0(s8)
+    %3:_(s16) = G_SEXT %1(s8)
+    %4:_(s16) = G_CONSTANT i16 13
+    %5:_(s16) = G_FSHL %2, %3, %4
+...
+---
+name:            SignBitsThroughZext
+body:             |
+  bb.1:
+  ; CHECK-LABEL: name: @SignBitsThroughZext
+  ; CHECK-NEXT: %0:_ KnownBits:???????? SignBits:1
+  ; CHECK-NEXT: %1:_ KnownBits:???????? SignBits:1
+  ; CHECK-NEXT: %2:_ KnownBits:0000000000000011 SignBits:14
+  ; CHECK-NEXT: %3:_ KnownBits:???????? SignBits:4
+  ; CHECK-NEXT: %4:_ KnownBits:???????? SignBits:4
+  ; CHECK-NEXT: %5:_ KnownBits:00000000???????? SignBits:8
+  ; CHECK-NEXT: %6:_ KnownBits:00000000???????? SignBits:8
+  ; CHECK-NEXT: %7:_ KnownBits:0000000000001000 SignBits:12
+  ; CHECK-NEXT: %8:_ KnownBits:????????00000000 SignBits:1
+    %0:_(s8) = COPY $b0
+    %1:_(s8) = COPY $b1
+    %2:_(s16) = G_CONSTANT i16 3
+    %3:_(s8) = G_ASHR %0, %2
+    %4:_(s8) = G_ASHR %1, %2
+    %5:_(s16) = G_ZEXT %3
+    %6:_(s16) = G_ZEXT %4
+    %7:_(s16) = G_CONSTANT i16 8
+    %8:_(s16) = G_FSHL %5, %6, %7
+...
+---
+name:            FSHLZeroAmt
+body:             |
+  bb.1:
+  ; CHECK-LABEL: name: @FSHLZeroAmt
+  ; CHECK-NEXT: %0:_ KnownBits:11100010 SignBits:3
+  ; CHECK-NEXT: %1:_ KnownBits:00001111 SignBits:4
+  ; CHECK-NEXT: %2:_ KnownBits:00000000 SignBits:8
+  ; CHECK-NEXT: %3:_ KnownBits:11100010 SignBits:3
+    %0:_(s8) = G_CONSTANT i8 226
+    %1:_(s8) = G_CONSTANT i8 15
+    %2:_(s8) = G_CONSTANT i8 0
+    %3:_(s8) = G_FSHL %0, %1, %2
+...
+---
+name:            FSHRZeroAmt
+body:             |
+  bb.1:
+  ; CHECK-LABEL: name: @FSHRZeroAmt
+  ; CHECK-NEXT: %0:_ KnownBits:11100010 SignBits:3
+  ; CHECK-NEXT: %1:_ KnownBits:00001111 SignBits:4
+  ; CHECK-NEXT: %2:_ KnownBits:00000000 SignBits:8
+  ; CHECK-NEXT: %3:_ KnownBits:00001111 SignBits:4
+    %0:_(s8) = G_CONSTANT i8 226
+    %1:_(s8) = G_CONSTANT i8 15
+    %2:_(s8) = G_CONSTANT i8 0
+    %3:_(s8) = G_FSHR %0, %1, %2
+...

jayfoad · 2026-04-10T09:52:16Z


+KnownBits KnownBits::fshl(KnownBits LHS, KnownBits RHS, unsigned Amt) {
+  // fshl: (X << (Z % BW)) | (Y >> (BW - (Z % BW)))
+  if (Amt == 0)


These are general purpose utility functions so you need to do the Amt %= BitWidth here. Also please add some unit testing in unittests/Support/KnownBitsTest.cpp.

jayfoad · 2026-04-10T11:03:08Z

@@ -673,6 +673,25 @@ TEST(KnownBitsTest, UnaryExhaustive) {
      [](const APInt &N) { return N * N; }, /*CheckOptimality=*/false);
 }

+TEST(KnownBitsTest, FunnelShift) {


Exhaustive testing would be even better. But I guess this is OK to start with.

def3r · 2026-04-21T03:41:38Z

ping

arsenm · 2026-04-21T11:26:04Z

+  Known.setAllConflict();
+
+  for (unsigned ShiftAmt = MinAmt; ShiftAmt <= MaxAmt; ++ShiftAmt) {
+    if ((ShiftAmtZeroMask & ShiftAmt) != 0 ||


Suggested change

if ((ShiftAmtZeroMask & ShiftAmt) != 0 ||

if (ShiftAmtZeroMask.intersects(ShiftAmt) ||

arsenm · 2026-04-21T11:27:03Z

+
+  for (unsigned ShiftAmt = MinAmt; ShiftAmt <= MaxAmt; ++ShiftAmt) {
+    if ((ShiftAmtZeroMask & ShiftAmt) != 0 ||
+        (ShiftAmtOneMask | ShiftAmt) != ShiftAmt)


Suggested change

(ShiftAmtOneMask | ShiftAmt) != ShiftAmt)

(!ShiftAmtOneMask.isSubsetOf(ShiftAmt))

Not sure I got this exactly right, but something like this

The masks are unsigned, and this is consistent with KnownBits::shl and KnownBits::lshr

llvm-project/llvm/lib/Support/KnownBits.cpp

Lines 470 to 483 in 980ddce

// Find the common bits from all possible shifts.

unsigned ShiftAmtZeroMask = RHS.Zero.zextOrTrunc(32).getZExtValue();

unsigned ShiftAmtOneMask = RHS.One.zextOrTrunc(32).getZExtValue();

Known.setAllConflict();

for (unsigned ShiftAmt = MinShiftAmount; ShiftAmt <= MaxShiftAmount;

++ShiftAmt) {

// Skip if the shift amount is impossible.

if ((ShiftAmtZeroMask & ShiftAmt) != 0 ||

(ShiftAmtOneMask | ShiftAmt) != ShiftAmt)

continue;

Known = Known.intersectWith(ShiftByConst(LHS, ShiftAmt));

if (Known.isUnknown())

break;

}

Should I instead use APInt for it?

ShiftAmt can generally be a unsigned for shifts (types don't get that big, out of range shifts produce poison for shifts), but that isn't always true for funnel shifts. APInts will protect against converting i128 or other types larger than 64bits, and the shift amount is taken modulo the bitwidth.

arsenm · 2026-04-21T11:27:45Z

@@ -603,6 +603,60 @@ KnownBits KnownBits::ashr(const KnownBits &LHS, const KnownBits &RHS,
  return Known;
 }

+KnownBits KnownBits::fshl(const KnownBits &LHS, const KnownBits &RHS,


I'm assuming this was moved code from the IR copy, so any cleanups here would maybe be better done separately. However, I don't see the removal of the IR copy?

I did not port this impl from anywhere (I'm not aware if there exists an impl to be ported for KnownBits). After adding exhaustive unit test for funnel shift, multiple tests failed. So I looked for impl similar to fshl. This is based on how KnownBits::shl and KnownBits::lshr are handled.

There is a SDAG version in

llvm-project/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp

Line 3855 in 57409d7

case ISD::FSHL:

And a ValueTracking/IR version in

llvm-project/llvm/lib/Analysis/ValueTracking.cpp

Line 2079 in 6c5b4a7

case Intrinsic::fshr:

Could they use this new logic? It might be simpler to keep just the constant shift amount version as a first addition.

llvm-project/llvm/lib/Analysis/ValueTracking.cpp

Line 2079 in 10f8205

case Intrinsic::fshr:

We should only have one implementation here, not develop one for each of the 3 IRs

I have updated both to use KnownBits::fshl and fshr, and kept only const shift amount impl in KnownBits.

github-actions · 2026-04-21T13:19:14Z

🐧 Linux x64 Test Results

172455 tests passed
3138 tests skipped
2 tests failed

Failed Tests

(click on a test name to see its output)

LLVM

LLVM.CodeGen/AMDGPU/GlobalISel/fshl.ll

Exit Code: -9
Timeout: Reached timeout of 1200 seconds

Command Output (stdout):
--
# RUN: at line 2
/home/gha/actions-runner/_work/llvm-project/llvm-project/build/bin/llc -global-isel -mtriple=amdgcn-amd-amdpal -mcpu=tahiti -o - /home/gha/actions-runner/_work/llvm-project/llvm-project/llvm/test/CodeGen/AMDGPU/GlobalISel/fshl.ll | /home/gha/actions-runner/_work/llvm-project/llvm-project/build/bin/FileCheck -check-prefixes=GCN,GFX6 /home/gha/actions-runner/_work/llvm-project/llvm-project/llvm/test/CodeGen/AMDGPU/GlobalISel/fshl.ll
# executed command: /home/gha/actions-runner/_work/llvm-project/llvm-project/build/bin/llc -global-isel -mtriple=amdgcn-amd-amdpal -mcpu=tahiti -o - /home/gha/actions-runner/_work/llvm-project/llvm-project/llvm/test/CodeGen/AMDGPU/GlobalISel/fshl.ll
# note: command had no output on stdout or stderr
# error: command failed with exit status: -9
# error: command reached timeout: True
# executed command: /home/gha/actions-runner/_work/llvm-project/llvm-project/build/bin/FileCheck -check-prefixes=GCN,GFX6 /home/gha/actions-runner/_work/llvm-project/llvm-project/llvm/test/CodeGen/AMDGPU/GlobalISel/fshl.ll
# note: command had no output on stdout or stderr
# error: command failed with exit status: -9
# error: command reached timeout: True

--

LLVM.CodeGen/AMDGPU/GlobalISel/fshr.ll

Exit Code: -9
Timeout: Reached timeout of 1200 seconds

Command Output (stdout):
--
# RUN: at line 2
/home/gha/actions-runner/_work/llvm-project/llvm-project/build/bin/llc -global-isel -new-reg-bank-select -mtriple=amdgcn-amd-amdpal -mcpu=tahiti -o - /home/gha/actions-runner/_work/llvm-project/llvm-project/llvm/test/CodeGen/AMDGPU/GlobalISel/fshr.ll | /home/gha/actions-runner/_work/llvm-project/llvm-project/build/bin/FileCheck -check-prefixes=GCN,GFX6 /home/gha/actions-runner/_work/llvm-project/llvm-project/llvm/test/CodeGen/AMDGPU/GlobalISel/fshr.ll
# executed command: /home/gha/actions-runner/_work/llvm-project/llvm-project/build/bin/llc -global-isel -new-reg-bank-select -mtriple=amdgcn-amd-amdpal -mcpu=tahiti -o - /home/gha/actions-runner/_work/llvm-project/llvm-project/llvm/test/CodeGen/AMDGPU/GlobalISel/fshr.ll
# note: command had no output on stdout or stderr
# error: command failed with exit status: -9
# error: command reached timeout: True
# executed command: /home/gha/actions-runner/_work/llvm-project/llvm-project/build/bin/FileCheck -check-prefixes=GCN,GFX6 /home/gha/actions-runner/_work/llvm-project/llvm-project/llvm/test/CodeGen/AMDGPU/GlobalISel/fshr.ll
# note: command had no output on stdout or stderr
# error: command failed with exit status: -9
# error: command reached timeout: True

--

If these failures are unrelated to your changes (for example tests are broken or flaky at HEAD), please open an issue at https://github.com/llvm/llvm-project/issues and add the infrastructure label.

github-actions · 2026-04-21T13:19:14Z

🪟 Windows x64 Test Results

133335 tests passed
3083 tests skipped
2 tests failed

Failed Tests

(click on a test name to see its output)

LLVM

LLVM.CodeGen/AMDGPU/GlobalISel/fshl.ll

Exit Code: 15
Timeout: Reached timeout of 1200 seconds

Command Output (stdout):
--
# RUN: at line 2
c:\_work\llvm-project\llvm-project\build\bin\llc.exe -global-isel -mtriple=amdgcn-amd-amdpal -mcpu=tahiti -o - C:\_work\llvm-project\llvm-project\llvm\test\CodeGen\AMDGPU\GlobalISel\fshl.ll | c:\_work\llvm-project\llvm-project\build\bin\filecheck.exe -check-prefixes=GCN,GFX6 C:\_work\llvm-project\llvm-project\llvm\test\CodeGen\AMDGPU\GlobalISel\fshl.ll
# executed command: 'c:\_work\llvm-project\llvm-project\build\bin\llc.exe' -global-isel -mtriple=amdgcn-amd-amdpal -mcpu=tahiti -o - 'C:\_work\llvm-project\llvm-project\llvm\test\CodeGen\AMDGPU\GlobalISel\fshl.ll'
# note: command had no output on stdout or stderr
# error: command failed with exit status: 15
# error: command reached timeout: True
# executed command: 'c:\_work\llvm-project\llvm-project\build\bin\filecheck.exe' -check-prefixes=GCN,GFX6 'C:\_work\llvm-project\llvm-project\llvm\test\CodeGen\AMDGPU\GlobalISel\fshl.ll'
# .---command stderr------------
# | C:\_work\llvm-project\llvm-project\llvm\test\CodeGen\AMDGPU\GlobalISel\fshl.ll:1439:15: error: GFX6-LABEL: expected string not found in input
# | ; GFX6-LABEL: s_fshl_i24:
# |               ^
# | <stdin>:557:13: note: scanning from here
# | v_fshl_v4i8: ; @v_fshl_v4i8
# |             ^
# | <stdin>:557:16: note: possible intended match here
# | v_fshl_v4i8: ; @v_fshl_v4i8
# |                ^
# | 
# | Input file: <stdin>
# | Check file: C:\_work\llvm-project\llvm-project\llvm\test\CodeGen\AMDGPU\GlobalISel\fshl.ll
# | 
# | -dump-input=help explains the following input dump.
# | 
# | Input was:
# | <<<<<<
# |               .
# |               .
# |               .
# |             552: ; COMPUTE_PGM_RSRC2:TIDIG_COMP_CNT: 0 
# |             553:  .text 
# |             554:  .globl v_fshl_v4i8 ; -- Begin function v_fshl_v4i8 
# |             555:  .p2align 6 
# |             556:  .type v_fshl_v4i8,@function 
# |             557: v_fshl_v4i8: ; @v_fshl_v4i8 
# | label:1439'0                 X~~~~~~~~~~~~~~~ error: no match found
# | label:1439'1                    ?             possible intended match
# |             558: ; %bb.0: 
# | label:1439'0     ~~~~~~~~~
# |             559:  s_waitcnt vmcnt(0) expcnt(0) lgkmcnt(0) 
# | label:1439'0     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |             560:  v_and_b32_e32 v9, 7, v2 
# | label:1439'0     ~~~~~~~~~~~~~~~~~~~~~~~~~
# |             561:  v_lshrrev_b32_e32 v3, 8, v0 
# | label:1439'0     ~~~~~~~~~~~~
# `-----------------------------
# error: command failed with exit status: 15
# error: command reached timeout: True

--

LLVM.CodeGen/AMDGPU/GlobalISel/fshr.ll

Exit Code: 15
Timeout: Reached timeout of 1200 seconds

Command Output (stdout):
--
# RUN: at line 2
c:\_work\llvm-project\llvm-project\build\bin\llc.exe -global-isel -new-reg-bank-select -mtriple=amdgcn-amd-amdpal -mcpu=tahiti -o - C:\_work\llvm-project\llvm-project\llvm\test\CodeGen\AMDGPU\GlobalISel\fshr.ll | c:\_work\llvm-project\llvm-project\build\bin\filecheck.exe -check-prefixes=GCN,GFX6 C:\_work\llvm-project\llvm-project\llvm\test\CodeGen\AMDGPU\GlobalISel\fshr.ll
# executed command: 'c:\_work\llvm-project\llvm-project\build\bin\llc.exe' -global-isel -new-reg-bank-select -mtriple=amdgcn-amd-amdpal -mcpu=tahiti -o - 'C:\_work\llvm-project\llvm-project\llvm\test\CodeGen\AMDGPU\GlobalISel\fshr.ll'
# note: command had no output on stdout or stderr
# error: command failed with exit status: 15
# error: command reached timeout: True
# executed command: 'c:\_work\llvm-project\llvm-project\build\bin\filecheck.exe' -check-prefixes=GCN,GFX6 'C:\_work\llvm-project\llvm-project\llvm\test\CodeGen\AMDGPU\GlobalISel\fshr.ll'
# .---command stderr------------
# | C:\_work\llvm-project\llvm-project\llvm\test\CodeGen\AMDGPU\GlobalISel\fshr.ll:1248:15: error: GFX6-LABEL: expected string not found in input
# | ; GFX6-LABEL: v_fshr_v4i8:
# |               ^
# | <stdin>:485:13: note: scanning from here
# | s_fshr_v4i8: ; @s_fshr_v4i8
# |             ^
# `-----------------------------
# error: command failed with exit status: 15
# error: command reached timeout: True

--

If these failures are unrelated to your changes (for example tests are broken or flaky at HEAD), please open an issue at https://github.com/llvm/llvm-project/issues and add the infrastructure label.

davemgreen · 2026-04-21T16:34:29Z

+
+  for (unsigned ShiftAmt = MinAmt; ShiftAmt <= MaxAmt; ++ShiftAmt) {
+    if ((ShiftAmtZeroMask & ShiftAmt) != 0 ||
+        (ShiftAmtOneMask | ShiftAmt) != ShiftAmt)


ShiftAmt can generally be a unsigned for shifts (types don't get that big, out of range shifts produce poison for shifts), but that isn't always true for funnel shifts. APInts will protect against converting i128 or other types larger than 64bits, and the shift amount is taken modulo the bitwidth.

davemgreen · 2026-04-21T16:34:36Z

+    return KnownBits(APIntOps::fshl(LHS.Zero, RHS.Zero, ShAmt),
+                     APIntOps::fshl(LHS.One, RHS.One, ShAmt));
+  }
+  unsigned BitWidth = LHS.getBitWidth();


Is this code is current inaccessible, outside of the unit test? As the Amt is always a constant.

Yup, I added it for unit tests, and GISel passes a const shift Amt

davemgreen · 2026-04-21T16:37:19Z

@@ -603,6 +603,60 @@ KnownBits KnownBits::ashr(const KnownBits &LHS, const KnownBits &RHS,
  return Known;
 }

+KnownBits KnownBits::fshl(const KnownBits &LHS, const KnownBits &RHS,


There is a SDAG version in

llvm-project/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp

Line 3855 in 57409d7

case ISD::FSHL:

And a ValueTracking/IR version in

llvm-project/llvm/lib/Analysis/ValueTracking.cpp

Line 2079 in 6c5b4a7

case Intrinsic::fshr:

Could they use this new logic? It might be simpler to keep just the constant shift amount version as a first addition.

jayfoad · 2026-04-27T09:03:41Z

Nit: move this outside the ShAmt loop?

arsenm · 2026-04-27T12:50:47Z

Shouldn't have lost this comment?

Since computation was moved, I thought it made sense to remove the comment as well. Restored it now.

arsenm · 2026-04-27T16:44:57Z

It might work out simpler to just make this be const APInt &Amt to start with

github-actions · 2026-04-27T18:45:07Z

@def3r Congratulations on having your first Pull Request (PR) merged into the LLVM Project!

Your changes will be combined with recent changes from other authors, then tested by our build bots. If there is a problem with a build, you may receive a report in an email or a comment on this PR.

Please check whether problems have been caused by your change specifically, as the builds can include changes from many authors. It is not uncommon for your change to be included in a build that fails due to someone else's changes, or infrastructure issues.

How to do this, and the rest of the post-merge process, is covered in detail here.

If your change does cause a problem, it may be reverted, or you can revert it yourself. This is a normal part of LLVM development. You can fix your changes and open a new PR to merge them again.

If you don't get any reports, no action is required from you. Your changes are working as expected, well done!

Ported impl from `SelectionDAG::computeKnownBits`. Tests are based on `AArch64/GlobalISel/knownbits-shl.mir` Ref: llvm#150515

[GlobalISel] Add G_FSHL and G_FSHR to computeKnownBits

2c6c8d9

llvmbot added backend:AArch64 llvm:globalisel labels Apr 9, 2026

arsenm reviewed Apr 9, 2026

View reviewed changes

Comment thread llvm/lib/CodeGen/GlobalISel/GISelValueTracking.cpp Outdated

Add fshl and fshr to KnownBits

df9789a

llvmbot added the llvm:support label Apr 9, 2026

def3r requested a review from arsenm April 10, 2026 05:00

jayfoad reviewed Apr 10, 2026

View reviewed changes

Improve impl and add unittest

d950804

def3r requested a review from jayfoad April 10, 2026 10:52

jayfoad reviewed Apr 10, 2026

View reviewed changes

Comment thread llvm/lib/Support/KnownBits.cpp Outdated

jayfoad reviewed Apr 10, 2026

View reviewed changes

Use fshl and fshr from APIntOps

f7a1002

arsenm reviewed Apr 10, 2026

View reviewed changes

Comment thread llvm/lib/Support/KnownBits.cpp Outdated

arsenm reviewed Apr 10, 2026

View reviewed changes

Comment thread llvm/lib/Support/KnownBits.cpp Outdated

def3r marked this pull request as draft April 11, 2026 05:23

def3r added 2 commits April 11, 2026 12:34

Improve impl + exhaustive testing

226aca5

const ref args

52d0f8d

def3r marked this pull request as ready for review April 11, 2026 07:26

def3r requested a review from jayfoad April 11, 2026 07:27

clean up

368018d

davemgreen mentioned this pull request Apr 11, 2026

[GlobalISel] Port known-bit and known-sign-bits for all operations #150515

Open

def3r force-pushed the gisel-fshl-fshr branch from 30e1f70 to 368018d Compare April 11, 2026 07:33

arsenm reviewed Apr 21, 2026

View reviewed changes

davemgreen reviewed Apr 21, 2026

View reviewed changes

def3r added 3 commits April 21, 2026 23:09

update AMDGPU test + fix impl

62d3702

use APInt for shift amt

1fe209e

only const shift amt impl

2e2c13d

def3r requested a review from nikic as a code owner April 26, 2026 07:19

def3r force-pushed the gisel-fshl-fshr branch from e76a0a7 to 7f6c708 Compare April 26, 2026 07:38

jayfoad reviewed Apr 27, 2026

View reviewed changes

clean up

ba00b05

def3r force-pushed the gisel-fshl-fshr branch from 7f6c708 to ba00b05 Compare April 27, 2026 12:04

arsenm approved these changes Apr 27, 2026

View reviewed changes

arg as APInt amt

0ab8595

arsenm approved these changes Apr 27, 2026

View reviewed changes

arsenm enabled auto-merge (squash) April 27, 2026 18:07

arsenm merged commit fce06e9 into llvm:main Apr 27, 2026
9 of 10 checks passed

	if ((ShiftAmtZeroMask & ShiftAmt) != 0 \|\|
	if (ShiftAmtZeroMask.intersects(ShiftAmt) \|\|

	(ShiftAmtOneMask \| ShiftAmt) != ShiftAmt)
	(!ShiftAmtOneMask.isSubsetOf(ShiftAmt))

	// Find the common bits from all possible shifts.
	unsigned ShiftAmtZeroMask = RHS.Zero.zextOrTrunc(32).getZExtValue();
	unsigned ShiftAmtOneMask = RHS.One.zextOrTrunc(32).getZExtValue();
	Known.setAllConflict();
	for (unsigned ShiftAmt = MinShiftAmount; ShiftAmt <= MaxShiftAmount;
	++ShiftAmt) {
	// Skip if the shift amount is impossible.
	if ((ShiftAmtZeroMask & ShiftAmt) != 0 \|\|
	(ShiftAmtOneMask \| ShiftAmt) != ShiftAmt)
	continue;
	Known = Known.intersectWith(ShiftByConst(LHS, ShiftAmt));
	if (Known.isUnknown())
	break;
	}

Uh oh!

Conversation

def3r commented Apr 9, 2026

Uh oh!

github-actions Bot commented Apr 9, 2026

Uh oh!

llvmbot commented Apr 9, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

def3r commented Apr 21, 2026

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

github-actions Bot commented Apr 21, 2026

🐧 Linux x64 Test Results

Failed Tests

LLVM

Uh oh!

github-actions Bot commented Apr 21, 2026

🪟 Windows x64 Test Results

Failed Tests

LLVM

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

github-actions Bot commented Apr 27, 2026

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

5 participants

llvmbot commented Apr 9, 2026 •

edited

Loading