Add bitwise ror, rol, operators alongside shr and shl

[andrew-wmg]

Circular shift (ror/rol )operators are extremely useful for bare metal programming. They are hardware supported by almost all current CPU and MCU. The lack of these operators in C causes a lot of headaches. I explained it in more detail here. It would be amazing to make them part of the language.

[jarroddavis68]

Hi Andrew, thanks for the suggestion. Here are my preliminary notes so I have it on record and can track it.

Yes, bitwise rotate operations (ROR and ROL) can be supported in the LLVM API, but they are implemented through funnel shift intrinsics rather than dedicated rotate instructions.

LLVM Funnel Shift Intrinsics

LLVM provides two key intrinsics for implementing rotates:

1. llvm.fshl.* (Funnel Shift Left) - for left rotates
2. llvm.fshr.* (Funnel Shift Right) - for right rotates

How Rotate Operations Work

When both input operands are the same value, funnel shift becomes a rotate:

; Left rotate (ROL): result = (value << amount) | (value >> (bitwidth - amount))
%result = call i32 @llvm.fshl.i32(i32 %value, i32 %value, i32 %amount)

; Right rotate (ROR): result = (value >> amount) | (value << (bitwidth - amount))  
%result = call i32 @llvm.fshr.i32(i32 %value, i32 %value, i32 %amount)

Based on my search initial API/web research, here's how you can implement bitwise rotate operations in LLVM:

Using LLVM C API Functions

To generate rotate operations using the LLVM C API, you'll use LLVMBuildCall with the funnel shift intrinsics:

// For rotate left (ROL)
function BuildRotateLeft(ABuilder: LLVMBuilderRef; AValue: LLVMValueRef; AAmount: LLVMValueRef; const AName: PAnsiChar): LLVMValueRef;
var
  LModule: LLVMModuleRef;
  LContext: LLVMContextRef;
  LIntrinsic: LLVMValueRef;
  LArgs: array[0..2] of LLVMValueRef;
  LValueType: LLVMTypeRef;
begin
  LValueType := LLVMTypeOf(AValue);
  LContext := LLVMGetBuilderContext(ABuilder);
  LModule := LLVMGetGlobalParent(LLVMGetBasicBlockParent(LLVMGetInsertBlock(ABuilder)));
  
  // Get the fshl intrinsic declaration
  LIntrinsic := LLVMGetIntrinsicDeclaration(LModule, 
    LLVMLookupIntrinsicID('llvm.fshl', 9), // 'llvm.fshl' = 9 chars
    @LValueType, 1);
  
  // Arguments: (value, value, amount) - same value twice for rotate
  LArgs[0] := AValue;
  LArgs[1] := AValue; 
  LArgs[2] := AAmount;
  
  Result := LLVMBuildCall2(ABuilder, LLVMGlobalGetValueType(LIntrinsic), 
    LIntrinsic, @LArgs[0], 3, AName);
end;

// For rotate right (ROR)  
function BuildRotateRight(ABuilder: LLVMBuilderRef; AValue: LLVMValueRef; AAmount: LLVMValueRef; const AName: PAnsiChar): LLVMValueRef;
var
  LModule: LLVMModuleRef;
  LContext: LLVMContextRef;
  LIntrinsic: LLVMValueRef;
  LArgs: array[0..2] of LLVMValueRef;
  LValueType: LLVMTypeRef;
begin
  LValueType := LLVMTypeOf(AValue);
  LContext := LLVMGetBuilderContext(ABuilder);
  LModule := LLVMGetGlobalParent(LLVMGetBasicBlockParent(LLVMGetInsertBlock(ABuilder)));
  
  // Get the fshr intrinsic declaration
  LIntrinsic := LLVMGetIntrinsicDeclaration(LModule,
    LLVMLookupIntrinsicID('llvm.fshr', 9), // 'llvm.fshr' = 9 chars
    @LValueType, 1);
  
  // Arguments: (value, value, amount) - same value twice for rotate
  LArgs[0] := AValue;
  LArgs[1] := AValue;
  LArgs[2] := AAmount;
  
  Result := LLVMBuildCall2(ABuilder, LLVMGlobalGetValueType(LIntrinsic),
    LIntrinsic, @LArgs[0], 3, AName);
end;

Key Points

1. Funnel Shift Intrinsics: LLVM uses llvm.fshl.* (funnel shift left) and llvm.fshr.* (funnel shift right) intrinsics to implement rotates.

2. When both operands are the same: When you pass the same value as both the first and second arguments, it becomes a rotate operation.

3. Available since LLVM 7: These intrinsics were introduced in LLVM 7 specifically to provide reliable rotate operations.

4. Automatic optimization: LLVM will automatically recognize these patterns and generate optimal rotate instructions (like ROL/ROR on x86) when the target supports them.

5. Type support: The intrinsics work with any integer type (i8, i16, i32, i64, etc.) and vector types.

Benefits over manual implementation

Using these intrinsics instead of manually combining shifts and ORs provides several advantages:

• Guaranteed optimization: The backend will always recognize these as rotates
• Better code generation: Produces single rotate instructions when supported
• Handles edge cases: Properly handles variable-amount rotates that might be problematic with manual shift combinations
• Cross-platform: Works consistently across all LLVM targets

This approach ensures that the CPascal compiler will generate efficient rotate operations that take full advantage of the target platform's capabilities.

Thanks for the suggestion, I've now added the functionality to the TCPIRContext class, which is used by TCPCodeGen to emit LLVM IR.

Here are all the support features so far:

TCPIRContext = class
public
  constructor Create(const AModuleName: string; const AContext: LLVMContextRef = nil);
  destructor Destroy; override;
  
  // Module Configuration
  function ModuleName(const AName: string): TCPIRContext;
  function TargetTriple(const ATriple: string): TCPIRContext;
  function DataLayout(const ALayout: string): TCPIRContext;

  // Type Creation Methods
  function VoidType: LLVMTypeRef;
  function BoolType: LLVMTypeRef;
  function Int1Type: LLVMTypeRef;
  function Int8Type: LLVMTypeRef;
  function Int16Type: LLVMTypeRef;
  function Int32Type: LLVMTypeRef;
  function Int64Type: LLVMTypeRef;
  function FloatType: LLVMTypeRef;
  function DoubleType: LLVMTypeRef;
  function IntPtrType: LLVMTypeRef;
  function PointerType(const APointedType: LLVMTypeRef): LLVMTypeRef;
  function ArrayType(const AElementType: LLVMTypeRef; const ASize: Cardinal): LLVMTypeRef;
  function StructType(const AFields: array of LLVMTypeRef; const APacked: Boolean = False): LLVMTypeRef;
  function FunctionType(const AReturnType: LLVMTypeRef; const AParams: array of LLVMTypeRef; const AVarArgs: Boolean = False): LLVMTypeRef;

  // Constant Creation Methods
  function ConstNull(const AType: LLVMTypeRef): LLVMValueRef;
  function ConstUndef(const AType: LLVMTypeRef): LLVMValueRef;
  function ConstBool(const AValue: Boolean): LLVMValueRef;
  function ConstInt1(const AValue: Boolean): LLVMValueRef;
  function ConstInt8(const AValue: Byte): LLVMValueRef;
  function ConstInt16(const AValue: Word): LLVMValueRef;
  function ConstInt32(const AValue: Integer): LLVMValueRef;
  function ConstInt64(const AValue: Int64): LLVMValueRef;
  function ConstFloat(const AValue: Single): LLVMValueRef;
  function ConstDouble(const AValue: Double): LLVMValueRef;
  function ConstString(const AValue: string): LLVMValueRef;
  function ConstArray(const AType: LLVMTypeRef; const AElements: array of LLVMValueRef): LLVMValueRef;
  function ConstStruct(const AElements: array of LLVMValueRef; const APacked: Boolean = False): LLVMValueRef;

  // Global Declaration Methods
  function DeclareGlobal(const AName: string; const AType: LLVMTypeRef; const AInitializer: LLVMValueRef = nil; 
    const ALinkage: LLVMLinkage = LLVMPrivateLinkage): LLVMValueRef;
  function DeclareFunction(const AName: string; const AFunctionType: LLVMTypeRef; 
    const ACallingConv: LLVMCallConv = LLVMCCallConv; const ALinkage: LLVMLinkage = LLVMExternalLinkage): LLVMValueRef;
  function DeclareExternalFunction(const AName: string; const AReturnType: LLVMTypeRef; const ALibrary: string; 
    const AParams: array of LLVMTypeRef; const ACallingConv: LLVMCallConv = LLVMCCallConv;
    const AVarArgs: Boolean = False): LLVMValueRef;

  // Function Building Methods
  function BeginFunction(const AName: string; const AFunctionType: LLVMTypeRef;
    const ACallingConv: LLVMCallConv = LLVMCCallConv; const ALinkage: LLVMLinkage = LLVMExternalLinkage): TCPIRContext;
  function AddFunctionAttribute(const AAttribute: LLVMAttributeRef): TCPIRContext;
  function EndFunction: TCPIRContext;

  // Basic Block Methods
  function BasicBlock(const AName: string): TCPIRContext;
  function CreateLabel(const APrefix: string = 'bb'): string;

  // Memory Operations
  function Alloca(const AType: LLVMTypeRef; const AArraySize: LLVMValueRef = nil; const AAlignment: Integer = 0): LLVMValueRef;
  function Load(const APtr: LLVMValueRef; const AType: LLVMTypeRef): LLVMValueRef;
  function Store(const AValue: LLVMValueRef; const APtr: LLVMValueRef; const AAlignment: Integer = 0): TCPIRContext;
  function GEP(const APtr: LLVMValueRef; const AIndices: array of LLVMValueRef): LLVMValueRef;
  function ExtractValue(const AValue: LLVMValueRef; const AIndices: array of Integer): LLVMValueRef;
  function InsertValue(const AAggregate: LLVMValueRef; const AValue: LLVMValueRef; const AIndices: array of Integer): LLVMValueRef;

  // Arithmetic Operations
  function Add(const ALeft: LLVMValueRef; const ARight: LLVMValueRef): LLVMValueRef;
  function Sub(const ALeft: LLVMValueRef; const ARight: LLVMValueRef): LLVMValueRef;
  function Mul(const ALeft: LLVMValueRef; const ARight: LLVMValueRef): LLVMValueRef;
  function UDiv(const ALeft: LLVMValueRef; const ARight: LLVMValueRef): LLVMValueRef;
  function SDiv(const ALeft: LLVMValueRef; const ARight: LLVMValueRef): LLVMValueRef;
  function URem(const ALeft: LLVMValueRef; const ARight: LLVMValueRef): LLVMValueRef;
  function SRem(const ALeft: LLVMValueRef; const ARight: LLVMValueRef): LLVMValueRef;
  function FAdd(const ALeft: LLVMValueRef; const ARight: LLVMValueRef): LLVMValueRef;
  function FSub(const ALeft: LLVMValueRef; const ARight: LLVMValueRef): LLVMValueRef;
  function FMul(const ALeft: LLVMValueRef; const ARight: LLVMValueRef): LLVMValueRef;
  function FDiv(const ALeft: LLVMValueRef; const ARight: LLVMValueRef): LLVMValueRef;
  function FRem(const ALeft: LLVMValueRef; const ARight: LLVMValueRef): LLVMValueRef;

  // Bitwise Operations
  function BitwiseAnd(const ALeft: LLVMValueRef; const ARight: LLVMValueRef): LLVMValueRef;
  function BitwiseOr(const ALeft: LLVMValueRef; const ARight: LLVMValueRef): LLVMValueRef;
  function BitwiseXor(const ALeft: LLVMValueRef; const ARight: LLVMValueRef): LLVMValueRef;
  function ShiftLeft(const ALeft: LLVMValueRef; const ARight: LLVMValueRef): LLVMValueRef;
  function LShr(const ALeft: LLVMValueRef; const ARight: LLVMValueRef): LLVMValueRef;
  function AShr(const ALeft: LLVMValueRef; const ARight: LLVMValueRef): LLVMValueRef;
  function ROL(const AValue: LLVMValueRef; const AAmount: LLVMValueRef): LLVMValueRef;
  function ROR(const AValue: LLVMValueRef; const AAmount: LLVMValueRef): LLVMValueRef;

  // Comparison Operations
  function ICmp(const ACondition: LLVMIntPredicate; const ALeft: LLVMValueRef; const ARight: LLVMValueRef): LLVMValueRef;
  function FCmp(const ACondition: LLVMRealPredicate; const ALeft: LLVMValueRef; const ARight: LLVMValueRef): LLVMValueRef;

  // Type Conversion Operations
  function Trunc(const AValue: LLVMValueRef; const ATargetType: LLVMTypeRef): LLVMValueRef;
  function ZExt(const AValue: LLVMValueRef; const ATargetType: LLVMTypeRef): LLVMValueRef;
  function SExt(const AValue: LLVMValueRef; const ATargetType: LLVMTypeRef): LLVMValueRef;
  function FPTrunc(const AValue: LLVMValueRef; const ATargetType: LLVMTypeRef): LLVMValueRef;
  function FPExt(const AValue: LLVMValueRef; const ATargetType: LLVMTypeRef): LLVMValueRef;
  function FPToUI(const AValue: LLVMValueRef; const ATargetType: LLVMTypeRef): LLVMValueRef;
  function FPToSI(const AValue: LLVMValueRef; const ATargetType: LLVMTypeRef): LLVMValueRef;
  function UIToFP(const AValue: LLVMValueRef; const ATargetType: LLVMTypeRef): LLVMValueRef;
  function SIToFP(const AValue: LLVMValueRef; const ATargetType: LLVMTypeRef): LLVMValueRef;
  function PtrToInt(const AValue: LLVMValueRef; const ATargetType: LLVMTypeRef): LLVMValueRef;
  function IntToPtr(const AValue: LLVMValueRef; const ATargetType: LLVMTypeRef): LLVMValueRef;
  function BitCast(const AValue: LLVMValueRef; const ATargetType: LLVMTypeRef): LLVMValueRef;

  // Control Flow Operations
  function Br(const ATarget: LLVMBasicBlockRef): TCPIRContext;
  function CondBr(const ACondition: LLVMValueRef; const ATrueTarget: LLVMBasicBlockRef; const AFalseTarget: LLVMBasicBlockRef): TCPIRContext;
  function Switch(const AValue: LLVMValueRef; const ADefaultTarget: LLVMBasicBlockRef): LLVMValueRef;
  function AddSwitchCase(const ASwitchInst: LLVMValueRef; const AValue: LLVMValueRef; const ATarget: LLVMBasicBlockRef): TCPIRContext;
  function Ret(const AValue: LLVMValueRef = nil): TCPIRContext;
  function RetVoid: TCPIRContext;

  // PHI Nodes
  function Phi(const AType: LLVMTypeRef): LLVMValueRef;
  function AddPhiIncoming(const APhiNode: LLVMValueRef; const AValue: LLVMValueRef; const ABlock: LLVMBasicBlockRef): TCPIRContext;

  // Function Calls
  function Call(const AFunction: LLVMValueRef; const AArgs: array of LLVMValueRef; 
    const ACallingConv: LLVMCallConv = LLVMCCallConv): LLVMValueRef;
  function CallVoid(const AFunction: LLVMValueRef; const AArgs: array of LLVMValueRef; 
    const ACallingConv: LLVMCallConv = LLVMCCallConv): TCPIRContext;
  function IndirectCall(const AFunctionPtr: LLVMValueRef; const AFunctionType: LLVMTypeRef; const AArgs: array of LLVMValueRef; 
    const ACallingConv: LLVMCallConv = LLVMCCallConv): LLVMValueRef;

  // Miscellaneous Operations
  function Select(const ACondition: LLVMValueRef; const ATrueValue: LLVMValueRef; const AFalseValue: LLVMValueRef): LLVMValueRef;
  function InlineAsm(const AFunctionType: LLVMTypeRef; const AAsmCode: string; const AConstraints: string; 
    const AHasSideEffects: Boolean = True; const AIsAlignStack: Boolean = False): LLVMValueRef;

  // Memory Intrinsics
  function MemCpy(const ADest: LLVMValueRef; const ASource: LLVMValueRef; const ASize: LLVMValueRef; const AAlign: Integer = 1): TCPIRContext;
  function MemSet(const ADest: LLVMValueRef; const AValue: LLVMValueRef; const ASize: LLVMValueRef; const AAlign: Integer = 1): TCPIRContext;
  function MemMove(const ADest: LLVMValueRef; const ASource: LLVMValueRef; const ASize: LLVMValueRef; const AAlign: Integer = 1): TCPIRContext;

  // Utility Methods
  function Comment(const AComment: string): TCPIRContext;
  function GetStringReference(const AValue: string): LLVMValueRef;
  function CreateBasicBlock(const AName: string; const AFunction: LLVMValueRef = nil): LLVMBasicBlockRef;
  function GetFunctionType(const AFunction: LLVMValueRef): LLVMTypeRef;

  // Module Access
  function GetModule: LLVMModuleRef;
  function ExtractModule: LLVMModuleRef;
  function Clear: TCPIRContext;

  // Properties
  property Module: LLVMModuleRef read FModule;
  property Context: LLVMContextRef read FContext;
  property Builder: LLVMBuilderRef read FBuilder;
  property CurrentFunction: LLVMValueRef read FCurrentFunction;
  property CurrentBlock: LLVMBasicBlockRef read FCurrentBlock;
end;

[andrew-wmg]

All due respect. There may have been some misunderstanding.

My original proposal was to add the operators ror and rol to the language specification as keywords.

The benefit of this solution is that it is more future-proof.
This will allow programmers to write universal code for different compilers and compiler creators to use optimal implementation of these operators for specific targets. For example, an LLVM-based compiler could use llvm.fshl/llvm.fshr as you suggest. In the embedded world, there are many compilers for the C language. Compiler-specific intrinsics (or inline ASM) is exactly what I hope to avoid. It's something that's giving people a lot of headaches right now. And to be honest these LLVM intrinsics look terrible. Much worse than the ones in GCC and Clang.

For a new system "Better C" language, it makes sense to fix C design issues right away than to build library wrappers or invent workarounds later.

P.S. I am always happy to see new low-level languages. Nowadays it is not easy to find languages that prioritize zero-runtime and no RTTI.

[jarroddavis68]

Yes, I understand what you wanted. But how do you think those keywords, along with any keyword or feature in the language gets implemented and turned into machine code? All of what I describe is how its done. The code is tokenized via the lexer, parsed to create an AST (abstract syntax tree) then the code generator will walk the AST tree, using IRConext class to create the IR code for the target. In the case, codegen will call IRContext.ROL/ROL to generate the actuall machine code (IR intermediate representaion, which LLVM will generate optimized machine code) for the feature.

[andrew-wmg]

Yes, I understand what you wanted. But how do you think those keywords, along with any keyword or feature in the language gets implemented and turned into machine code? All of what I describe is how its done. The code is tokenized via the lexer, parsed to create an AST (abstract syntax tree) then the code generator will walk the AST tree, using IRConext class to create the IR code for the target. In the case, codegen will call IRContext.ROL/ROL to generate the actuall machine code (IR intermediate representaion, which LLVM will generate optimized machine code) for the feature.

Yes, I am familiar with the LLVM architecture, but not with your codebase yet. Just reading the language specification for now. This phrase confused me:

To generate rotate operations using the LLVM C API, you'll use LLVMBuildCall with the funnel shift intrinsics:

That's the approach I have to use now. So I decided to double check that I was understood correctly. Since English is not my native language. I apologize if that seems rude.

[jarroddavis68]

Understanding Rotate Operations in LLVM

What are Rotate Operations?

Rotate operations (ROL/ROR) are bitwise operations that shift bits in a circular manner:

• ROL (Rotate Left): Bits shifted left wrap around to the right side
• ROR (Rotate Right): Bits shifted right wrap around to the left side

Example: ROL 8-bit value 0b10110010 by 3 positions
Original:  1 0 1 1 0 0 1 0
Result:    1 0 0 1 0 1 0 1
           └─┘ wrapped around

Why Funnel Shift Intrinsics?

LLVM doesn't provide direct rotate instructions. Instead, it uses funnel shift intrinsics because:

1. Generality: Funnel shift is more general than rotate
2. Optimization: LLVM can optimize funnel shifts into rotates when appropriate
3. Reliability: Guarantees the operation reaches the backend intact

How Funnel Shift Works

A funnel shift concatenates two values and shifts the result:

fshl(A, B, amount) = (A << amount) | (B >> (bitwidth - amount))
fshr(A, B, amount) = (A << (bitwidth - amount)) | (B >> amount)

For rotates, use the same value for both A and B:

ROL(value, amount) = fshl(value, value, amount)  
ROR(value, amount) = fshr(value, value, amount)

Implementation with LLVM C API

// Rotate Left using LLVM C API
LLVMValueRef build_rotate_left(LLVMBuilderRef builder, 
                               LLVMValueRef value, 
                               LLVMValueRef amount) {
    // 1. Get the module and value type
    LLVMModuleRef module = /* get current module */;
    LLVMTypeRef value_type = LLVMTypeOf(value);
    
    // 2. Get the fshl intrinsic declaration
    unsigned intrinsic_id = LLVMLookupIntrinsicID("llvm.fshl", 9);
    LLVMValueRef intrinsic = LLVMGetIntrinsicDeclaration(
        module, intrinsic_id, &value_type, 1);
    
    // 3. Set up arguments: (value, value, amount)
    LLVMValueRef args[3] = {value, value, amount};
    
    // 4. Generate the call
    return LLVMBuildCall2(builder, 
                         LLVMGlobalGetValueType(intrinsic),
                         intrinsic, args, 3, "rotate_left");
}

Key Benefits

1. Automatic Optimization: LLVM recognizes this pattern and generates optimal code
2. Cross-Platform: Works on all targets, generating rotate instructions when available
3. Type Agnostic: Works with any integer type (i8, i16, i32, i64, vectors)
4. Guaranteed Recognition: Unlike manual shift+OR combinations that might not optimize

Example Generated Assembly

On x86-64, this generates efficient rotate instructions:

; ROL by constant amount
rol eax, 4

; ROL by variable amount  
mov ecx, edx
rol eax, cl

Why Not Manual Implementation?

Manual rotate using shifts and OR can break during optimization:

// This might NOT generate a rotate instruction
result = (value << amount) | (value >> (32 - amount));

The funnel shift intrinsic guarantees the rotate operation survives all optimization passes and generates optimal machine code.

This approach provides the best of both worlds: high-level expressiveness with low-level performance guarantees.

[jarroddavis68]

rol/ror will be added to the language, I wanted to document my technical findings so I can track what is needed to implement the feature.

[jarroddavis68]

And to be honest these LLVM intrinsics look terrible. Much worse than the ones in GCC and Clang.

You know Clang uses LLVM right?

When you made the proposal, as a developer, my thoughts went to, “Okay, how are they implemented in LLVM?” My initial research led me to this finding. The fact that we now have a plan for getting them into the language is a very important step. Often, wanting a feature and figuring out how to implement it become the limiting factor.

We tend to take for granted that we can simply do this in the langauge:

program RotateExample;

function SimpleHash(Value: UInt32): UInt32;
begin
  // ROL/ROR as built-in operators (like shl/shr)
  Result := Value rol 7 xor $A5A5A5A5;
end;

function Encrypt(Data: UInt32): UInt32;
begin
  Result := Data;
  Result := Result rol 5;      // Rotate left 5 bits
  Result := Result xor $12345678;
  Result := Result ror 3;      // Rotate right 3 bits  
  Result := Result + $DEADBEEF;
end;

begin
  WriteLn('Hash: $', IntToHex(SimpleHash($ABCDEF01)));
  WriteLn('Encrypted: $', IntToHex(Encrypt($12345678)));
end.

But behind the scenes, it will take the aforementioned technical details to be implemented in order for you to be able to even do that.

[andrew-wmg]

You know Clang uses LLVM right?

Of course. As I said, this is a misunderstanding. I wrongly thought you were suggesting using intrinsics in cPascal. As we now have to do in C. My bad. It doesn't matter anymore. I checked the compiler code and now I understand how you plan to implement ror/rol.