Skip to content

Conversation

chaitanyav
Copy link
Contributor

@chaitanyav chaitanyav commented Sep 23, 2025

This patch adds type-generic rotate builtins that accept any unsigned integer
type. These builtins provide:

  • Support for all unsigned integer types, including _BitInt
  • Constexpr evaluation capability
  • Automatic normalization of rotation counts modulo the bit-width
  • Proper handling of negative rotation counts (converted to equivalent
    positive rotations in the opposite direction)
  • Implicit conversion support for both arguments, allowing bool, float, and
    types with conversion operators (not limited to record types)

The builtins follow C23 naming conventions.

Resolves #122819

@llvmbot llvmbot added clang Clang issues not falling into any other category clang:frontend Language frontend issues, e.g. anything involving "Sema" clang:codegen IR generation bugs: mangling, exceptions, etc. labels Sep 23, 2025
@llvmbot
Copy link
Member

llvmbot commented Sep 23, 2025

@llvm/pr-subscribers-clang

@llvm/pr-subscribers-clang-codegen

Author: NagaChaitanya Vellanki (chaitanyav)

Changes

Resolves #122819


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

4 Files Affected:

  • (modified) clang/include/clang/Basic/Builtins.td (+12)
  • (modified) clang/lib/CodeGen/CGBuiltin.cpp (+2)
  • (modified) clang/lib/Sema/SemaChecking.cpp (+48)
  • (modified) clang/test/CodeGen/builtin-rotate.c (+73)
diff --git a/clang/include/clang/Basic/Builtins.td b/clang/include/clang/Basic/Builtins.td
index 35d2c3e19fdf9..7044b48014e9d 100644
--- a/clang/include/clang/Basic/Builtins.td
+++ b/clang/include/clang/Basic/Builtins.td
@@ -767,12 +767,24 @@ def RotateLeft : BitInt8_16_32_64BuiltinsTemplate, Builtin {
   let Prototype = "T(T, T)";
 }
 
+def RotateLeftg : Builtin {
+  let Spellings = ["__builtin_rotateleftg"];
+  let Attributes = [NoThrow, Const, Constexpr, CustomTypeChecking];
+  let Prototype = "void(...)";
+}
+
 def RotateRight : BitInt8_16_32_64BuiltinsTemplate, Builtin {
   let Spellings = ["__builtin_rotateright"];
   let Attributes = [NoThrow, Const, Constexpr];
   let Prototype = "T(T, T)";
 }
 
+def RotateRightg : Builtin {
+  let Spellings = ["__builtin_rotaterightg"];
+  let Attributes = [NoThrow, Const, Constexpr, CustomTypeChecking];
+  let Prototype = "void(...)";
+}
+
 // Random GCC builtins
 // FIXME: The builtins marked FunctionWithBuiltinPrefix below should be
 //        merged with the library definitions. They are currently not because
diff --git a/clang/lib/CodeGen/CGBuiltin.cpp b/clang/lib/CodeGen/CGBuiltin.cpp
index f7c3dea257d50..d5e107c91854e 100644
--- a/clang/lib/CodeGen/CGBuiltin.cpp
+++ b/clang/lib/CodeGen/CGBuiltin.cpp
@@ -3642,6 +3642,7 @@ RValue CodeGenFunction::EmitBuiltinExpr(const GlobalDecl GD, unsigned BuiltinID,
   case Builtin::BI__builtin_rotateleft16:
   case Builtin::BI__builtin_rotateleft32:
   case Builtin::BI__builtin_rotateleft64:
+  case Builtin::BI__builtin_rotateleftg:
   case Builtin::BI_rotl8: // Microsoft variants of rotate left
   case Builtin::BI_rotl16:
   case Builtin::BI_rotl:
@@ -3653,6 +3654,7 @@ RValue CodeGenFunction::EmitBuiltinExpr(const GlobalDecl GD, unsigned BuiltinID,
   case Builtin::BI__builtin_rotateright16:
   case Builtin::BI__builtin_rotateright32:
   case Builtin::BI__builtin_rotateright64:
+  case Builtin::BI__builtin_rotaterightg:
   case Builtin::BI_rotr8: // Microsoft variants of rotate right
   case Builtin::BI_rotr16:
   case Builtin::BI_rotr:
diff --git a/clang/lib/Sema/SemaChecking.cpp b/clang/lib/Sema/SemaChecking.cpp
index 740b472b0eb16..959f7b055149f 100644
--- a/clang/lib/Sema/SemaChecking.cpp
+++ b/clang/lib/Sema/SemaChecking.cpp
@@ -2267,6 +2267,48 @@ static bool BuiltinCountZeroBitsGeneric(Sema &S, CallExpr *TheCall) {
   return false;
 }
 
+/// Checks that __builtin_{rotateleftg,rotaterightg} was called with two
+/// arguments, that the first argument is an unsigned integer type, and that
+/// the second argument is an integer type.
+static bool BuiltinRotateGeneric(Sema &S, CallExpr *TheCall) {
+  if (S.checkArgCount(TheCall, 2))
+    return true;
+
+  ExprResult Arg0Res = S.DefaultLvalueConversion(TheCall->getArg(0));
+  if (Arg0Res.isInvalid())
+    return true;
+
+  Expr *Arg0 = Arg0Res.get();
+  TheCall->setArg(0, Arg0);
+
+  QualType Arg0Ty = Arg0->getType();
+
+  if (!Arg0Ty->isUnsignedIntegerType()) {
+    S.Diag(Arg0->getBeginLoc(), diag::err_builtin_invalid_arg_type)
+        << 1 << /* scalar */ 1 << /* unsigned integer ty */ 3 << /* no fp */ 0
+        << Arg0Ty;
+    return true;
+  }
+
+  ExprResult Arg1Res = S.DefaultLvalueConversion(TheCall->getArg(1));
+  if (Arg1Res.isInvalid())
+    return true;
+
+  Expr *Arg1 = Arg1Res.get();
+  TheCall->setArg(1, Arg1);
+
+  QualType Arg1Ty = Arg1->getType();
+
+  if (!Arg1Ty->isIntegerType()) {
+    S.Diag(Arg1->getBeginLoc(), diag::err_builtin_invalid_arg_type)
+        << 2 << /* scalar */ 1 << /* integer ty */ 2 << /* no fp */ 0 << Arg1Ty;
+    return true;
+  }
+
+  TheCall->setType(Arg0Ty);
+  return false;
+}
+
 static bool CheckMaskedBuiltinArgs(Sema &S, Expr *MaskArg, Expr *PtrArg,
                                    unsigned Pos, bool Vector = true) {
   QualType MaskTy = MaskArg->getType();
@@ -3416,6 +3458,12 @@ Sema::CheckBuiltinFunctionCall(FunctionDecl *FDecl, unsigned BuiltinID,
       return ExprError();
     break;
 
+  case Builtin::BI__builtin_rotateleftg:
+  case Builtin::BI__builtin_rotaterightg:
+    if (BuiltinRotateGeneric(*this, TheCall))
+      return ExprError();
+    break;
+
   case Builtin::BI__builtin_allow_runtime_check: {
     Expr *Arg = TheCall->getArg(0);
     // Check if the argument is a string literal.
diff --git a/clang/test/CodeGen/builtin-rotate.c b/clang/test/CodeGen/builtin-rotate.c
index 8fc1701c6c9bb..7a0343158f1ba 100644
--- a/clang/test/CodeGen/builtin-rotate.c
+++ b/clang/test/CodeGen/builtin-rotate.c
@@ -32,6 +32,43 @@ unsigned long long rotl64(unsigned long long x, long long y) {
   return __builtin_rotateleft64(x, y);
 }
 
+// CHECK-LABEL: test_builtin_rotateleftg
+void test_builtin_rotateleftg(unsigned char uc, unsigned short us,
+                               unsigned int ui, unsigned long ul,
+                               unsigned long long ull, unsigned __int128 ui128,
+                               unsigned _BitInt(128) ubi128) {
+
+volatile unsigned char result_uc;
+volatile unsigned int result_ui;
+volatile unsigned short result_us;
+volatile unsigned long result_ul;
+volatile unsigned long long result_ull;
+volatile unsigned __int128 result_ui128;
+volatile unsigned _BitInt(128) result_ubi128;
+
+  // CHECK: call i8 @llvm.fshl.i8(i8 %{{.*}}, i8 %{{.*}}, i8 3)
+  result_uc = __builtin_rotateleftg(uc, 3);
+
+  // CHECK: call i16 @llvm.fshl.i16(i16 %{{.*}}, i16 %{{.*}}, i16 5)
+  result_us = __builtin_rotateleftg(us, 5);
+
+  // CHECK: call i32 @llvm.fshl.i32(i32 %{{.*}}, i32 %{{.*}}, i32 8)
+  result_ui = __builtin_rotateleftg(ui, 8);
+
+  // CHECK: call i64 @llvm.fshl.i64(i64 %{{.*}}, i64 %{{.*}}, i64 8)
+  result_ul = __builtin_rotateleftg(ul, 8);
+
+  // CHECK: call i64 @llvm.fshl.i64(i64 %{{.*}}, i64 %{{.*}}, i64 16)
+  result_ull = __builtin_rotateleftg(ull, 16);
+
+  // CHECK: call i128 @llvm.fshl.i128(i128 %{{.*}}, i128 %{{.*}}, i128 32)
+  result_ui128 = __builtin_rotateleftg(ui128, 32);
+
+  // CHECK: call i128 @llvm.fshl.i128(i128 %{{.*}}, i128 %{{.*}}, i128 64)
+  result_ubi128 = __builtin_rotateleftg(ubi128, 64);
+
+}
+
 char rotr8(char x, char y) {
 // CHECK-LABEL: rotr8
 // CHECK: [[F:%.*]] = call i8 @llvm.fshr.i8(i8 [[X:%.*]], i8 [[X]], i8 [[Y:%.*]])
@@ -64,3 +101,39 @@ long long rotr64(long long x, unsigned long long y) {
   return __builtin_rotateright64(x, y);
 }
 
+// CHECK-LABEL: test_builtin_rotaterightg
+void test_builtin_rotaterightg(unsigned char uc, unsigned short us,
+                               unsigned int ui, unsigned long ul,
+                               unsigned long long ull, unsigned __int128 ui128,
+                               unsigned _BitInt(128) ubi128) {
+
+  volatile unsigned char result_uc;
+  volatile unsigned int result_ui;
+  volatile unsigned short result_us;
+  volatile unsigned long result_ul;
+  volatile unsigned long long result_ull;
+  volatile unsigned __int128 result_ui128;
+  volatile unsigned _BitInt(128) result_ubi128;
+
+  // CHECK: call i8 @llvm.fshr.i8(i8 %{{.*}}, i8 %{{.*}}, i8 3)
+  result_uc = __builtin_rotaterightg(uc, 3);
+
+  // CHECK: call i16 @llvm.fshr.i16(i16 %{{.*}}, i16 %{{.*}}, i16 5)
+  result_us = __builtin_rotaterightg(us, 5);
+
+  // CHECK: call i32 @llvm.fshr.i32(i32 %{{.*}}, i32 %{{.*}}, i32 8)
+  result_ui = __builtin_rotaterightg(ui, 8);
+
+  // CHECK: call i64 @llvm.fshr.i64(i64 %{{.*}}, i64 %{{.*}}, i64 8)
+  result_ul = __builtin_rotaterightg(ul, 8);
+
+  // CHECK: call i64 @llvm.fshr.i64(i64 %{{.*}}, i64 %{{.*}}, i64 16)
+  result_ull = __builtin_rotaterightg(ull, 16);
+
+  // CHECK: call i128 @llvm.fshr.i128(i128 %{{.*}}, i128 %{{.*}}, i128 32)
+  result_ui128 = __builtin_rotaterightg(ui128, 32);
+
+  // CHECK: call i128 @llvm.fshr.i128(i128 %{{.*}}, i128 %{{.*}}, i128 64)
+  result_ubi128 = __builtin_rotaterightg(ubi128, 64);
+
+}
\ No newline at end of file

@chaitanyav chaitanyav force-pushed the enhance_122819 branch 3 times, most recently from 4fc9bde to 01dfddd Compare September 23, 2025 15:29
@chaitanyav chaitanyav self-assigned this Sep 24, 2025
Copy link
Contributor

@philnik777 philnik777 left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Oh, you should also update the title.

@chaitanyav chaitanyav changed the title [clang] Implement __builtin_rotate{left,right}g [clang] Implement __builtin_stdc_rotate_left, __builtin_stdc_rotate_right Sep 24, 2025
Copy link
Contributor

@philnik777 philnik777 left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

LGTM, but let's wait for one of the Clang people to take another look.

accept any unsigned integer type, including ``_BitInt`` types. The rotation
count is treated as an unsigned value and taken modulo the bit-width of the
value being rotated. Negative rotation counts are converted to their unsigned
equivalent before the modulo operation. These builtins can be used within
Copy link
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Does "converted to their unsigned equivalent" mean reinterpreting the two's-complement representation as unsigned? Or is it the absolute value? Or something else? I'm confused by what you're doing here.

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

please let me update that, i am normalizing the negative numbers to be in [0, bitwidth - 1] range.

Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Wouldn't it make more sense to simply reject signed types?

Copy link
Contributor Author

@chaitanyav chaitanyav Sep 27, 2025

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Tested it thoroughly

test_rotate_1.txt

Testing edge cases for __builtin_stdc_rotate_{left,right}
=======================================================
Testing large _BitInt types...
_BitInt(64) rotate left by 63: PASS
_BitInt(96) rotate left by 95: PASS
_BitInt(128) rotate left by 127: PASS

Testing odd bit widths...
_BitInt(37) rotate left by 36: PASS
_BitInt(73) rotate left by 72: PASS
_BitInt(127) rotate left by 126: PASS

Testing extreme rotation amounts...
Rotate by UINT_MAX: PASS
Rotate by INT_MIN: PASS
Rotate by 10000: PASS

Testing boundary rotations...
Rotate by 0: PASS
Rotate by bit width (32): PASS
Rotate by 2x bit width (64): PASS
Rotate left by -1 vs rotate right by 1: PASS

Testing small _BitInt types...
_BitInt(1) rotate: PASS
_BitInt(2) rotate left by 1: PASS
_BitInt(3) rotate left by 2: PASS

Testing pattern verification...
Alternating pattern rotate: PASS
All-ones pattern rotate: PASS
Single bit walking: PASS

Testing left/right rotation consistency...
Left/right consistency: PASS
Left/right equivalence: PASS

Running performance stress test...
Performance stress test (10000 rotations): PASS

Testing maximum _BitInt(128) values...
_BitInt(128) high bit rotate: PASS
_BitInt(128) lower bits rotate: PASS

Testing zero and minimal bit cases...
Large shift on small type: PASS
Negative rotation on small type: PASS

=======================================================
All tests completed.

__BitInt tests

test_rotate_2.txt

Testing both compile-time (static assertions) and runtime paths
Static assertions passed - compile-time evaluation works!

=== Runtime Edge Case Tests ===
PASS: Large shift: 341 << 1000
PASS: Large negative: 341 << -1000
PASS: Max value rotate
PASS: Zero rotate

=== Different Bit Widths Runtime Tests ===
PASS: 3-bit rotate
PASS: 5-bit rotate
PASS: 7-bit rotate
PASS: 10-bit rotate
PASS: 13-bit rotate

=== Comprehensive Negative Shift Tests ===
rotate_left(341, -1) = 426
rotate_left(341, -2) = 213
rotate_left(341, -3) = 362
rotate_left(341, -4) = 181
rotate_left(341, -5) = 346
rotate_left(341, -6) = 173
rotate_left(341, -7) = 342
rotate_left(341, -8) = 171
rotate_left(341, -9) = 341
rotate_left(341, -10) = 426
rotate_left(341, -11) = 213
rotate_left(341, -12) = 362
rotate_left(341, -13) = 181
rotate_left(341, -14) = 346
rotate_left(341, -15) = 173
rotate_left(341, -16) = 342
rotate_left(341, -17) = 171
rotate_left(341, -18) = 341
rotate_left(341, -19) = 426
rotate_left(341, -20) = 213

=== Comprehensive Modulo Reduction Tests ===
rotate_left(341, 100) = 171 (reduced: 1)
rotate_left(341, 1000) = 171 (reduced: 1)
rotate_left(341, 10000) = 171 (reduced: 1)
rotate_left(341, 50000) = 181 (reduced: 5)
rotate_left(341, 1073741823) = 341 (reduced: 0)

=== Cross-Direction Equivalence Tests ===
rotate_left(341, -1) = 426, rotate_right(341, 1) = 426
rotate_left(341, -2) = 213, rotate_right(341, 2) = 213
rotate_left(341, -3) = 362, rotate_right(341, 3) = 362
rotate_left(341, -4) = 181, rotate_right(341, 4) = 181
rotate_left(341, -5) = 346, rotate_right(341, 5) = 346
rotate_left(341, -6) = 173, rotate_right(341, 6) = 173
rotate_left(341, -7) = 342, rotate_right(341, 7) = 342
rotate_left(341, -8) = 171, rotate_right(341, 8) = 171
rotate_left(341, -9) = 341, rotate_right(341, 9) = 341
rotate_left(341, -10) = 426, rotate_right(341, 10) = 426
rotate_left(341, -11) = 213, rotate_right(341, 11) = 213
rotate_left(341, -12) = 362, rotate_right(341, 12) = 362
rotate_left(341, -13) = 181, rotate_right(341, 13) = 181
rotate_left(341, -14) = 346, rotate_right(341, 14) = 346
rotate_left(341, -15) = 173, rotate_right(341, 15) = 173
rotate_left(341, -16) = 342, rotate_right(341, 16) = 342
rotate_left(341, -17) = 171, rotate_right(341, 17) = 171
rotate_left(341, -18) = 341, rotate_right(341, 18) = 341
rotate_left(341, -19) = 426, rotate_right(341, 19) = 426
rotate_left(341, -20) = 213, rotate_right(341, 20) = 213

=== Large Bit Width Stress Tests ===
PASS: 37-bit large value
PASS: 61-bit large value
37-bit rotate by 10000: result computed

=== Large Shifts on Small Bit Widths ===
PASS: 8-bit by 64
PASS: 8-bit by 65
PASS: 8-bit by 1000
PASS: 3-bit by 64
PASS: 3-bit by 1000
PASS: 16-bit by 65536
PASS: 16-bit by 65537
PASS: 8-bit by -64
PASS: 8-bit by -1000
Testing shift amounts much larger than bit widths: PASSED

🎉 ALL COMPREHENSIVE TESTS PASSED! 🎉
Both compile-time and runtime rotation implementations are correct!
Tested bit widths: 3, 5, 6, 7, 8, 9, 10, 11, 12, 13, 16, 37, 61
Tested shift ranges: -50000 to +65537
Tested edge cases: zero, max values, power-of-2, boundary conditions

@github-actions
Copy link

github-actions bot commented Sep 26, 2025

✅ With the latest revision this PR passed the C/C++ code formatter.

@chaitanyav chaitanyav force-pushed the enhance_122819 branch 3 times, most recently from db50769 to 6c5c34c Compare September 27, 2025 04:04
@chaitanyav chaitanyav force-pushed the enhance_122819 branch 2 times, most recently from 24cf397 to 258cb5d Compare October 1, 2025 18:22
let Attributes = [NoThrow, Const, Constexpr, CustomTypeChecking];
let Prototype = "void(...)";
}

Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

@pinskia Did these name ship in gcc already? the "stdc" is a bit novel and does not add much

Copy link

@pinskia pinskia Oct 2, 2025

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Yes it shipped with GCC 15.1.0: https://gcc.gnu.org/onlinedocs/gcc-15.1.0/gcc/Bit-Operation-Builtins.html#index-_005f_005fbuiltin_005fstdc_005frotate_005fleft

stdc is there because that are the function names in specified in C23's stdbit.h header. GCC just added _builtin in front of them here. The GCC builtins in this case is supposed to be exactly the same constaints as the C23's builtins except for allowing for any unsigned integer (standard, extended or bit-precise).

Comment on lines +14146 to +14733
case Builtin::BI__builtin_stdc_rotate_left:
case Builtin::BI__builtin_stdc_rotate_right:
case Builtin::BI_rotl8: // Microsoft variants of rotate left
case Builtin::BI_rotl16:
case Builtin::BI_rotl:
case Builtin::BI_lrotl:
case Builtin::BI_rotl64:
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

We are changing the behavior of existing builtins, is that intended?

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

i thought these generics will also use (unsigned, unsigned), but they evolved during the review. Those functions will still work as expected. I understand the concern (now that we are allowing more types) please let me know if we have to separate them out.

@cor3ntin cor3ntin requested a review from erichkeane October 2, 2025 14:08
Copy link
Collaborator

@erichkeane erichkeane left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Needs:

  • Better commit message (in github top-thing)
  • Release note

@chaitanyav chaitanyav force-pushed the enhance_122819 branch 2 times, most recently from c07ba37 to 6c9b801 Compare October 4, 2025 03:29
Copy link
Collaborator

@erichkeane erichkeane left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

1 question in docs, else this is going to be fine for me.

@chaitanyav
Copy link
Contributor Author

@erichkeane, the compiler is issuing a warning. I will use a better example

test_doc_example.cpp:4:38: warning: implicit conversion from 'unsigned int' to 'unsigned _BitInt(17)' changes value from 3504544 to 96672
      [-Wconstant-conversion]
    4 |   unsigned _BitInt(17) rotated_odd = __builtin_stdc_rotate_left(0x1ABCD, 5);
      |                        ~~~~~~~~~~~   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

@chaitanyav chaitanyav force-pushed the enhance_122819 branch 2 times, most recently from 26d8f53 to 0fccdce Compare October 9, 2025 02:07
return __builtin_rotateright64(x, y);
}

// CHECK-LABEL: test_builtin_stdc_rotate_left
Copy link
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

The CHECK lines here seem to miss some important bits. A lot of the patch is dedicated to converting the shift amounts into the proper form; we should have some checks showing that we generate appropriate code.

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

@efriedma-quic modified the CHECK lines to make sure that we verify the Shift value. Please let me know if any changes are needed.

@chaitanyav chaitanyav force-pushed the enhance_122819 branch 2 times, most recently from 379a5ac to 54cf4cc Compare October 11, 2025 03:25
@chaitanyav
Copy link
Contributor Author

Please let me know if any changes are needed. Also, I don't have write access. I need help merging this if no changes are needed.

…e_right

This patch adds type-generic rotate builtins that accept any unsigned integer
type. These builtins provide:

- Support for all unsigned integer types, including _BitInt
- Constexpr evaluation capability
- Automatic normalization of rotation counts modulo the bit-width
- Proper handling of negative rotation counts (converted to equivalent
  positive rotations in the opposite direction)
- Implicit conversion support for both arguments, allowing bool, float, and
  types with conversion operators (not limited to record types)

The builtins follow C23 naming conventions.

Resolves llvm#122819
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

clang:codegen IR generation bugs: mangling, exceptions, etc. clang:frontend Language frontend issues, e.g. anything involving "Sema" clang Clang issues not falling into any other category

Projects

None yet

Development

Successfully merging this pull request may close these issues.

[Clang] Consider adding __builtin_rotate{left,right}g

8 participants