[Builtins] Improve the IR emitted for MSVC compatible rotr/rotl builtins to match what the middle and backends understand

[craig.topper]

Summary

Currently we emit something like

rotl(x, n) {
n &= bitwidth -1;
return n != 0 ? ((x << n) | (x >> (bitwidth - n)) : x;
}

We use a select to avoid the undefined behavior on the (bitwidth - n) shift.

The middle and backend don't really recognize this as a rotate and end up emitting a cmov or control flow because of the select.

A better pattern is (x << (n & mask)) | (x << (-n & mask)) where mask is bitwidth - 1.

Fixes the main complaint in PR37387. There's still some work to be done if the user writes that sequence directly on a short or char where type promotion rules can prevent it from being recognized. The builtin is emitting direct IR with unpromoted types so that isn't a problem for it.

[spatel]

LGTM - thanks!

[rnk]

Thanks!

cfe/trunk/lib/CodeGen/CGBuiltin.cpp

RValue CodeGenFunction::EmitBuiltinExpr(const FunctionDecl *FD,
   case Builtin::BI_rotr:
   case Builtin::BI_lrotr:
   case Builtin::BI_rotr64: {
     Value *Val = EmitScalarExpr(E->getArg(0));
     Value *Shift = EmitScalarExpr(E->getArg(1));
 
     llvm::Type *ArgType = Val->getType();
     Shift = Builder.CreateIntCast(Shift, ArgType, false);
-    unsigned ArgWidth = cast<llvm::IntegerType>(ArgType)->getBitWidth();
-    Value *ArgTypeSize = llvm::ConstantInt::get(ArgType, ArgWidth);
-    Value *ArgZero = llvm::Constant::getNullValue(ArgType);
-
+    unsigned ArgWidth = ArgType->getIntegerBitWidth();
     Value *Mask = llvm::ConstantInt::get(ArgType, ArgWidth - 1);
-    Shift = Builder.CreateAnd(Shift, Mask);
-    Value *LeftShift = Builder.CreateSub(ArgTypeSize, Shift);
-
-    Value *RightShifted = Builder.CreateLShr(Val, Shift);
-    Value *LeftShifted = Builder.CreateShl(Val, LeftShift);
-    Value *Rotated = Builder.CreateOr(LeftShifted, RightShifted);
 
-    Value *ShiftIsZero = Builder.CreateICmpEQ(Shift, ArgZero);
-    Value *Result = Builder.CreateSelect(ShiftIsZero, Val, Rotated);
+    Value *RightShiftAmt = Builder.CreateAnd(Shift, Mask);
+    Value *RightShifted = Builder.CreateLShr(Val, RightShiftAmt);
+    Value *LeftShiftAmt = Builder.CreateAnd(Builder.CreateNeg(Shift), Mask);
+    Value *LeftShifted = Builder.CreateShl(Val, LeftShiftAmt);
+    Value *Result = Builder.CreateOr(LeftShifted, RightShifted);
     return RValue::get(Result);
   }
   case Builtin::BI_rotl8:
   case Builtin::BI_rotl16:
   case Builtin::BI_rotl:
   case Builtin::BI_lrotl:
   case Builtin::BI_rotl64: {
     Value *Val = EmitScalarExpr(E->getArg(0));
     Value *Shift = EmitScalarExpr(E->getArg(1));
 
     llvm::Type *ArgType = Val->getType();
     Shift = Builder.CreateIntCast(Shift, ArgType, false);
-    unsigned ArgWidth = cast<llvm::IntegerType>(ArgType)->getBitWidth();
-    Value *ArgTypeSize = llvm::ConstantInt::get(ArgType, ArgWidth);
-    Value *ArgZero = llvm::Constant::getNullValue(ArgType);
-
+    unsigned ArgWidth = ArgType->getIntegerBitWidth();
     Value *Mask = llvm::ConstantInt::get(ArgType, ArgWidth - 1);
-    Shift = Builder.CreateAnd(Shift, Mask);
-    Value *RightShift = Builder.CreateSub(ArgTypeSize, Shift);
-
-    Value *LeftShifted = Builder.CreateShl(Val, Shift);
-    Value *RightShifted = Builder.CreateLShr(Val, RightShift);
-    Value *Rotated = Builder.CreateOr(LeftShifted, RightShifted);
 
-    Value *ShiftIsZero = Builder.CreateICmpEQ(Shift, ArgZero);
-    Value *Result = Builder.CreateSelect(ShiftIsZero, Val, Rotated);
+    Value *LeftShiftAmt = Builder.CreateAnd(Shift, Mask);
+    Value *LeftShifted = Builder.CreateShl(Val, LeftShiftAmt);
+    Value *RightShiftAmt = Builder.CreateAnd(Builder.CreateNeg(Shift), Mask);
+    Value *RightShifted = Builder.CreateLShr(Val, RightShiftAmt);
+    Value *Result = Builder.CreateOr(LeftShifted, RightShifted);
     return RValue::get(Result);
   }
   case Builtin::BI__builtin_unpredictable: {
     // Always return the argument of __builtin_unpredictable. LLVM does not
     // handle this builtin. Metadata for this builtin should be added directly
     // to instructions such as branches or switches that use it.
     return RValue::get(EmitScalarExpr(E->getArg(0)));
   }

cfe/trunk/test/CodeGen/ms-intrinsics-rotations.c

 #endif
 
 // rotate left
 
 unsigned char test_rotl8(unsigned char value, unsigned char shift) {
   return _rotl8(value, shift);
 }
 // CHECK: i8 @test_rotl8
-// CHECK:   [[SHIFT:%[0-9]+]] = and i8 %{{[0-9]+}}, 7
-// CHECK:   [[NEGSHIFT:%[0-9]+]] = sub i8 8, [[SHIFT]]
-// CHECK:   [[HIGH:%[0-9]+]] = shl i8 [[VALUE:%[0-9]+]], [[SHIFT]]
-// CHECK:   [[LOW:%[0-9]+]] = lshr i8 [[VALUE]], [[NEGSHIFT]]
-// CHECK:   [[ROTATED:%[0-9]+]] = or i8 [[HIGH]], [[LOW]]
-// CHECK:   [[ISZERO:%[0-9]+]] = icmp eq i8 [[SHIFT]], 0
-// CHECK:   [[RESULT:%[0-9]+]] = select i1 [[ISZERO]], i8 [[VALUE]], i8 [[ROTATED]]
+// CHECK:   [[LSHIFT:%[0-9]+]] = and i8 [[SHIFT:%[0-9]+]], 7
+// CHECK:   [[HIGH:%[0-9]+]] = shl i8 [[VALUE:%[0-9]+]], [[LSHIFT]]
+// CHECK:   [[NEGATE:%[0-9]+]] = sub i8 0, [[SHIFT]]
+// CHECK:   [[RSHIFT:%[0-9]+]] = and i8 [[NEGATE]], 7
+// CHECK:   [[LOW:%[0-9]+]] = lshr i8 [[VALUE]], [[RSHIFT]]
+// CHECK:   [[RESULT:%[0-9]+]] = or i8 [[HIGH]], [[LOW]]
 // CHECK:   ret i8 [[RESULT]]
 // CHECK  }
 
 unsigned short test_rotl16(unsigned short value, unsigned char shift) {
   return _rotl16(value, shift);
 }
 // CHECK: i16 @test_rotl16
-// CHECK:   [[SHIFT:%[0-9]+]] = and i16 %{{[0-9]+}}, 15
-// CHECK:   [[NEGSHIFT:%[0-9]+]] = sub i16 16, [[SHIFT]]
-// CHECK:   [[HIGH:%[0-9]+]] = shl i16 [[VALUE:%[0-9]+]], [[SHIFT]]
-// CHECK:   [[LOW:%[0-9]+]] = lshr i16 [[VALUE]], [[NEGSHIFT]]
-// CHECK:   [[ROTATED:%[0-9]+]] = or i16 [[HIGH]], [[LOW]]
-// CHECK:   [[ISZERO:%[0-9]+]] = icmp eq i16 [[SHIFT]], 0
-// CHECK:   [[RESULT:%[0-9]+]] = select i1 [[ISZERO]], i16 [[VALUE]], i16 [[ROTATED]]
+// CHECK:   [[LSHIFT:%[0-9]+]] = and i16 [[SHIFT:%[0-9]+]], 15
+// CHECK:   [[HIGH:%[0-9]+]] = shl i16 [[VALUE:%[0-9]+]], [[LSHIFT]]
+// CHECK:   [[NEGATE:%[0-9]+]] = sub i16 0, [[SHIFT]]
+// CHECK:   [[RSHIFT:%[0-9]+]] = and i16 [[NEGATE]], 15
+// CHECK:   [[LOW:%[0-9]+]] = lshr i16 [[VALUE]], [[RSHIFT]]
+// CHECK:   [[RESULT:%[0-9]+]] = or i16 [[HIGH]], [[LOW]]
 // CHECK:   ret i16 [[RESULT]]
 // CHECK  }
 
 unsigned int test_rotl(unsigned int value, int shift) {
   return _rotl(value, shift);
 }
 // CHECK: i32 @test_rotl
-// CHECK:   [[SHIFT:%[0-9]+]] = and i32 %{{[0-9]+}}, 31
-// CHECK:   [[NEGSHIFT:%[0-9]+]] = sub i32 32, [[SHIFT]]
-// CHECK:   [[HIGH:%[0-9]+]] = shl i32 [[VALUE:%[0-9]+]], [[SHIFT]]
-// CHECK:   [[LOW:%[0-9]+]] = lshr i32 [[VALUE]], [[NEGSHIFT]]
-// CHECK:   [[ROTATED:%[0-9]+]] = or i32 [[HIGH]], [[LOW]]
-// CHECK:   [[ISZERO:%[0-9]+]] = icmp eq i32 [[SHIFT]], 0
-// CHECK:   [[RESULT:%[0-9]+]] = select i1 [[ISZERO]], i32 [[VALUE]], i32 [[ROTATED]]
+// CHECK:   [[LSHIFT:%[0-9]+]] = and i32 [[SHIFT:%[0-9]+]], 31
+// CHECK:   [[HIGH:%[0-9]+]] = shl i32 [[VALUE:%[0-9]+]], [[LSHIFT]]
+// CHECK:   [[NEGATE:%[0-9]+]] = sub i32 0, [[SHIFT]]
+// CHECK:   [[RSHIFT:%[0-9]+]] = and i32 [[NEGATE]], 31
+// CHECK:   [[LOW:%[0-9]+]] = lshr i32 [[VALUE]], [[RSHIFT]]
+// CHECK:   [[RESULT:%[0-9]+]] = or i32 [[HIGH]], [[LOW]]
 // CHECK:   ret i32 [[RESULT]]
 // CHECK  }
 
 unsigned LONG test_lrotl(unsigned LONG value, int shift) {
   return _lrotl(value, shift);
 }
 // CHECK-32BIT-LONG: i32 @test_lrotl
-// CHECK-32BIT-LONG:   [[SHIFT:%[0-9]+]] = and i32 %{{[0-9]+}}, 31
-// CHECK-32BIT-LONG:   [[NEGSHIFT:%[0-9]+]] = sub i32 32, [[SHIFT]]
-// CHECK-32BIT-LONG:   [[HIGH:%[0-9]+]] = shl i32 [[VALUE:%[0-9]+]], [[SHIFT]]
-// CHECK-32BIT-LONG:   [[LOW:%[0-9]+]] = lshr i32 [[VALUE]], [[NEGSHIFT]]
-// CHECK-32BIT-LONG:   [[ROTATED:%[0-9]+]] = or i32 [[HIGH]], [[LOW]]
-// CHECK-32BIT-LONG:   [[ISZERO:%[0-9]+]] = icmp eq i32 [[SHIFT]], 0
-// CHECK-32BIT-LONG:   [[RESULT:%[0-9]+]] = select i1 [[ISZERO]], i32 [[VALUE]], i32 [[ROTATED]]
+// CHECK-32BIT-LONG:   [[LSHIFT:%[0-9]+]] = and i32 [[SHIFT:%[0-9]+]], 31
+// CHECK-32BIT-LONG:   [[HIGH:%[0-9]+]] = shl i32 [[VALUE:%[0-9]+]], [[LSHIFT]]
+// CHECK-32BIT-LONG:   [[NEGATE:%[0-9]+]] = sub i32 0, [[SHIFT]]
+// CHECK-32BIT-LONG:   [[RSHIFT:%[0-9]+]] = and i32 [[NEGATE]], 31
+// CHECK-32BIT-LONG:   [[LOW:%[0-9]+]] = lshr i32 [[VALUE]], [[RSHIFT]]
+// CHECK-32BIT-LONG:   [[RESULT:%[0-9]+]] = or i32 [[HIGH]], [[LOW]]
 // CHECK-32BIT-LONG:   ret i32 [[RESULT]]
 // CHECK-32BIT-LONG  }
 
 unsigned __int64 test_rotl64(unsigned __int64 value, int shift) {
   return _rotl64(value, shift);
 }
 // CHECK: i64 @test_rotl64
-// CHECK:   [[SHIFT:%[0-9]+]] = and i64 %{{[0-9]+}}, 63
-// CHECK:   [[NEGSHIFT:%[0-9]+]] = sub i64 64, [[SHIFT]]
-// CHECK:   [[HIGH:%[0-9]+]] = shl i64 [[VALUE:%[0-9]+]], [[SHIFT]]
-// CHECK:   [[LOW:%[0-9]+]] = lshr i64 [[VALUE]], [[NEGSHIFT]]
-// CHECK:   [[ROTATED:%[0-9]+]] = or i64 [[HIGH]], [[LOW]]
-// CHECK:   [[ISZERO:%[0-9]+]] = icmp eq i64 [[SHIFT]], 0
-// CHECK:   [[RESULT:%[0-9]+]] = select i1 [[ISZERO]], i64 [[VALUE]], i64 [[ROTATED]]
+// CHECK:   [[LSHIFT:%[0-9]+]] = and i64 [[SHIFT:%[0-9]+]], 63
+// CHECK:   [[HIGH:%[0-9]+]] = shl i64 [[VALUE:%[0-9]+]], [[LSHIFT]]
+// CHECK:   [[NEGATE:%[0-9]+]] = sub i64 0, [[SHIFT]]
+// CHECK:   [[RSHIFT:%[0-9]+]] = and i64 [[NEGATE]], 63
+// CHECK:   [[LOW:%[0-9]+]] = lshr i64 [[VALUE]], [[RSHIFT]]
+// CHECK:   [[RESULT:%[0-9]+]] = or i64 [[HIGH]], [[LOW]]
 // CHECK:   ret i64 [[RESULT]]
 // CHECK  }
 
 // rotate right
 
 unsigned char test_rotr8(unsigned char value, unsigned char shift) {
   return _rotr8(value, shift);
 }
 // CHECK: i8 @test_rotr8
-// CHECK:   [[SHIFT:%[0-9]+]] = and i8 %{{[0-9]+}}, 7
-// CHECK:   [[NEGSHIFT:%[0-9]+]] = sub i8 8, [[SHIFT]]
-// CHECK:   [[LOW:%[0-9]+]] = lshr i8 [[VALUE:%[0-9]+]], [[SHIFT]]
-// CHECK:   [[HIGH:%[0-9]+]] = shl i8 [[VALUE]], [[NEGSHIFT]]
-// CHECK:   [[ROTATED:%[0-9]+]] = or i8 [[HIGH]], [[LOW]]
-// CHECK:   [[ISZERO:%[0-9]+]] = icmp eq i8 [[SHIFT]], 0
-// CHECK:   [[RESULT:%[0-9]+]] = select i1 [[ISZERO]], i8 [[VALUE]], i8 [[ROTATED]]
-// CHECK:   ret i8 [[RESULT]]
+// CHECK:   [[RSHIFT:%[0-9]+]] = and i8 [[SHIFT:%[0-9]+]], 7
+// CHECK:   [[LOW:%[0-9]+]] = lshr i8 [[VALUE:%[0-9]+]], [[RSHIFT]]
+// CHECK:   [[NEGATE:%[0-9]+]] = sub i8 0, [[SHIFT]]
+// CHECK:   [[LSHIFT:%[0-9]+]] = and i8 [[NEGATE]], 7
+// CHECK:   [[HIGH:%[0-9]+]] = shl i8 [[VALUE]], [[LSHIFT]]
+// CHECK:   [[RESULT:%[0-9]+]] = or i8 [[HIGH]], [[LOW]]
 // CHECK  }
 
 unsigned short test_rotr16(unsigned short value, unsigned char shift) {
   return _rotr16(value, shift);
 }
 // CHECK: i16 @test_rotr16
-// CHECK:   [[SHIFT:%[0-9]+]] = and i16 %{{[0-9]+}}, 15
-// CHECK:   [[NEGSHIFT:%[0-9]+]] = sub i16 16, [[SHIFT]]
-// CHECK:   [[LOW:%[0-9]+]] = lshr i16 [[VALUE:%[0-9]+]], [[SHIFT]]
-// CHECK:   [[HIGH:%[0-9]+]] = shl i16 [[VALUE]], [[NEGSHIFT]]
-// CHECK:   [[ROTATED:%[0-9]+]] = or i16 [[HIGH]], [[LOW]]
-// CHECK:   [[ISZERO:%[0-9]+]] = icmp eq i16 [[SHIFT]], 0
-// CHECK:   [[RESULT:%[0-9]+]] = select i1 [[ISZERO]], i16 [[VALUE]], i16 [[ROTATED]]
-// CHECK:   ret i16 [[RESULT]]
+// CHECK:   [[RSHIFT:%[0-9]+]] = and i16 [[SHIFT:%[0-9]+]], 15
+// CHECK:   [[LOW:%[0-9]+]] = lshr i16 [[VALUE:%[0-9]+]], [[RSHIFT]]
+// CHECK:   [[NEGATE:%[0-9]+]] = sub i16 0, [[SHIFT]]
+// CHECK:   [[LSHIFT:%[0-9]+]] = and i16 [[NEGATE]], 15
+// CHECK:   [[HIGH:%[0-9]+]] = shl i16 [[VALUE]], [[LSHIFT]]
+// CHECK:   [[RESULT:%[0-9]+]] = or i16 [[HIGH]], [[LOW]]
 // CHECK  }
 
 unsigned int test_rotr(unsigned int value, int shift) {
   return _rotr(value, shift);
 }
 // CHECK: i32 @test_rotr
-// CHECK:   [[SHIFT:%[0-9]+]] = and i32 %{{[0-9]+}}, 31
-// CHECK:   [[NEGSHIFT:%[0-9]+]] = sub i32 32, [[SHIFT]]
-// CHECK:   [[LOW:%[0-9]+]] = lshr i32 [[VALUE:%[0-9]+]], [[SHIFT]]
-// CHECK:   [[HIGH:%[0-9]+]] = shl i32 [[VALUE]], [[NEGSHIFT]]
-// CHECK:   [[ROTATED:%[0-9]+]] = or i32 [[HIGH]], [[LOW]]
-// CHECK:   [[ISZERO:%[0-9]+]] = icmp eq i32 [[SHIFT]], 0
-// CHECK:   [[RESULT:%[0-9]+]] = select i1 [[ISZERO]], i32 [[VALUE]], i32 [[ROTATED]]
+// CHECK:   [[RSHIFT:%[0-9]+]] = and i32 [[SHIFT:%[0-9]+]], 31
+// CHECK:   [[LOW:%[0-9]+]] = lshr i32 [[VALUE:%[0-9]+]], [[RSHIFT]]
+// CHECK:   [[NEGATE:%[0-9]+]] = sub i32 0, [[SHIFT]]
+// CHECK:   [[LSHIFT:%[0-9]+]] = and i32 [[NEGATE]], 31
+// CHECK:   [[HIGH:%[0-9]+]] = shl i32 [[VALUE]], [[LSHIFT]]
+// CHECK:   [[RESULT:%[0-9]+]] = or i32 [[HIGH]], [[LOW]]
 // CHECK:   ret i32 [[RESULT]]
 // CHECK  }
 
 unsigned LONG test_lrotr(unsigned LONG value, int shift) {
   return _lrotr(value, shift);
 }
 // CHECK-32BIT-LONG: i32 @test_lrotr
-// CHECK-32BIT-LONG:   [[SHIFT:%[0-9]+]] = and i32 %{{[0-9]+}}, 31
-// CHECK-32BIT-LONG:   [[NEGSHIFT:%[0-9]+]] = sub i32 32, [[SHIFT]]
-// CHECK-32BIT-LONG:   [[LOW:%[0-9]+]] = lshr i32 [[VALUE:%[0-9]+]], [[SHIFT]]
-// CHECK-32BIT-LONG:   [[HIGH:%[0-9]+]] = shl i32 [[VALUE]], [[NEGSHIFT]]
-// CHECK-32BIT-LONG:   [[ROTATED:%[0-9]+]] = or i32 [[HIGH]], [[LOW]]
-// CHECK-32BIT-LONG:   [[ISZERO:%[0-9]+]] = icmp eq i32 [[SHIFT]], 0
-// CHECK-32BIT-LONG:   [[RESULT:%[0-9]+]] = select i1 [[ISZERO]], i32 [[VALUE]], i32 [[ROTATED]]
+// CHECK-32BIT-LONG:   [[RSHIFT:%[0-9]+]] = and i32 [[SHIFT:%[0-9]+]], 31
+// CHECK-32BIT-LONG:   [[LOW:%[0-9]+]] = lshr i32 [[VALUE:%[0-9]+]], [[RSHIFT]]
+// CHECK-32BIT-LONG:   [[NEGATE:%[0-9]+]] = sub i32 0, [[SHIFT]]
+// CHECK-32BIT-LONG:   [[LSHIFT:%[0-9]+]] = and i32 [[NEGATE]], 31
+// CHECK-32BIT-LONG:   [[HIGH:%[0-9]+]] = shl i32 [[VALUE]], [[LSHIFT]]
+// CHECK-32BIT-LONG:   [[RESULT:%[0-9]+]] = or i32 [[HIGH]], [[LOW]]
 // CHECK-32BIT-LONG:   ret i32 [[RESULT]]
 // CHECK-32BIT-LONG  }
 
 unsigned __int64 test_rotr64(unsigned __int64 value, int shift) {
   return _rotr64(value, shift);
 }
 // CHECK: i64 @test_rotr64
-// CHECK:   [[SHIFT:%[0-9]+]] = and i64 %{{[0-9]+}}, 63
-// CHECK:   [[NEGSHIFT:%[0-9]+]] = sub i64 64, [[SHIFT]]
-// CHECK:   [[LOW:%[0-9]+]] = lshr i64 [[VALUE:%[0-9]+]], [[SHIFT]]
-// CHECK:   [[HIGH:%[0-9]+]] = shl i64 [[VALUE]], [[NEGSHIFT]]
-// CHECK:   [[ROTATED:%[0-9]+]] = or i64 [[HIGH]], [[LOW]]
-// CHECK:   [[ISZERO:%[0-9]+]] = icmp eq i64 [[SHIFT]], 0
-// CHECK:   [[RESULT:%[0-9]+]] = select i1 [[ISZERO]], i64 [[VALUE]], i64 [[ROTATED]]
+// CHECK:   [[RSHIFT:%[0-9]+]] = and i64 [[SHIFT:%[0-9]+]], 63
+// CHECK:   [[LOW:%[0-9]+]] = lshr i64 [[VALUE:%[0-9]+]], [[RSHIFT]]
+// CHECK:   [[NEGATE:%[0-9]+]] = sub i64 0, [[SHIFT]]
+// CHECK:   [[LSHIFT:%[0-9]+]] = and i64 [[NEGATE]], 63
+// CHECK:   [[HIGH:%[0-9]+]] = shl i64 [[VALUE]], [[LSHIFT]]
+// CHECK:   [[RESULT:%[0-9]+]] = or i64 [[HIGH]], [[LOW]]
 // CHECK:   ret i64 [[RESULT]]
 // CHECK  }