From 2b248849aecbfd726348f320e80e12a3b91c9f48 Mon Sep 17 00:00:00 2001 From: Craig Topper Date: Thu, 10 May 2018 00:05:13 +0000 Subject: [PATCH] [Builtins] Improve the IR emitted for MSVC compatible rotr/rotl builtins to match what the middle and backends understand Previously we emitted 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. Differential Revision: https://reviews.llvm.org/D46656 llvm-svn: 331943 --- clang/lib/CodeGen/CGBuiltin.cpp | 36 +++----- clang/test/CodeGen/ms-intrinsics-rotations.c | 132 ++++++++++++--------------- 2 files changed, 72 insertions(+), 96 deletions(-) diff --git a/clang/lib/CodeGen/CGBuiltin.cpp b/clang/lib/CodeGen/CGBuiltin.cpp index 6879187..dfb9370 100644 --- a/clang/lib/CodeGen/CGBuiltin.cpp +++ b/clang/lib/CodeGen/CGBuiltin.cpp @@ -1409,20 +1409,14 @@ RValue CodeGenFunction::EmitBuiltinExpr(const FunctionDecl *FD, llvm::Type *ArgType = Val->getType(); Shift = Builder.CreateIntCast(Shift, ArgType, false); - unsigned ArgWidth = cast(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: @@ -1435,20 +1429,14 @@ RValue CodeGenFunction::EmitBuiltinExpr(const FunctionDecl *FD, llvm::Type *ArgType = Val->getType(); Shift = Builder.CreateIntCast(Shift, ArgType, false); - unsigned ArgWidth = cast(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: { diff --git a/clang/test/CodeGen/ms-intrinsics-rotations.c b/clang/test/CodeGen/ms-intrinsics-rotations.c index 9533e6c..735de6e 100644 --- a/clang/test/CodeGen/ms-intrinsics-rotations.c +++ b/clang/test/CodeGen/ms-intrinsics-rotations.c @@ -30,13 +30,12 @@ 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 } @@ -44,13 +43,12 @@ 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 } @@ -58,13 +56,12 @@ 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 } @@ -72,13 +69,12 @@ 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 } @@ -86,13 +82,12 @@ 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 } @@ -102,41 +97,36 @@ 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 } @@ -144,13 +134,12 @@ 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 } @@ -158,12 +147,11 @@ 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 } -- 2.7.4