[CodeGen] add rotate builtins

[spatel]

Summary

This exposes the LLVM funnel shift intrinsics as more familiar bit rotation functions in clang (when both halves of a funnel shift are the same value, it's a rotate).

I think we're free to name these as we want because we're not copying gcc, but if there's some other existing art that we want to replicate, let me know.

The funnel shift intrinsics were added here:
D49242

With improved codegen in:
rL337966
rL339359

And basic IR optimization added in:
rL338218
rL340022

...so I think these should produce asm output that's equal or better to the multi-instruction alternatives using primitive C/IR ops.

In the motivating loop example from PR37387:
https://bugs.llvm.org/show_bug.cgi?id=37387#c7
...we get the expected 'rolq' x86 instructions if we substitute the rotate builtin into the source.

[rnk]

Do you mind updating the _rotl* and _rotr* intrinsics to use the same codegen? They're right above in the switch.

[spatel]

Patch updated:
Fixed a docs typo.

[spatel]

In D50924#1204772, @rnk wrote:

Do you mind updating the _rotl* and _rotr* intrinsics to use the same codegen? They're right above in the switch.

Sure - I didn't know about those.

[spatel]

Patch updated:
Update the existing Microsoft rotate builtins to also use the LLVM funnel shift intrinsics.

[lebedev.ri]

Looks ok to me.

[rnk]

Thanks, looks good!

[spatel]

Reopening because I reverted at rL340136. Not sure yet what is causing the problem on those bots.

[spatel]

In D50924#1205310, @spatel wrote:

Reopening because I reverted at rL340136. Not sure yet what is causing the problem on those bots.

The common trait for those failures appears to be that the host compiler is:
gcc version 7.3.1 20180130 (Red Hat 7.3.1-2) (GCC)

...but that compiler is crashing while compiling a file that this patch does not actually touch. Anyone know what our commit policy suggests for this situation?

[spatel]

Reopening again because I reverted this again for the same reason at rL340138.

[spatel]

And the 3rd time is the charm...
I have no explanation for why this works, but I removed the microsoft diffs, and now gcc doesn't crash.
cc'ing @lei as owner of the bots that have this problem:
http://lab.llvm.org:8011/builders/clang-ppc64be-linux/builds/22826/steps/build%20stage%201/logs/stdio

I'm not sure if I can repro that crash locally (requires PPC?). Maybe there's something useful that can be recovered from the bots to repro and file a gcc bug?

cfe/trunk/docs/LanguageExtensions.rst

.. code-block:: c++
       uint64_t rev_z = __builtin_bitreverse64(z);
 
 **Description**:
 
 The '``__builtin_bitreverse``' family of builtins is used to reverse
 the bitpattern of an integer value; for example ``0b10110110`` becomes
 ``0b01101101``.
 
+``__builtin_rotateleft``
+------------------------
+
+* ``__builtin_rotateleft8``
+* ``__builtin_rotateleft16``
+* ``__builtin_rotateleft32``
+* ``__builtin_rotateleft64``
+
+**Syntax**:
+
+.. code-block:: c++
+
+     __builtin_rotateleft32(x, y)
+
+**Examples**:
+
+.. code-block:: c++
+
+      uint8_t rot_x = __builtin_rotateleft8(x, y);
+      uint16_t rot_x = __builtin_rotateleft16(x, y);
+      uint32_t rot_x = __builtin_rotateleft32(x, y);
+      uint64_t rot_x = __builtin_rotateleft64(x, y);
+
+**Description**:
+
+The '``__builtin_rotateleft``' family of builtins is used to rotate
+the bits in the first argument by the amount in the second argument. 
+For example, ``0b10000110`` rotated left by 11 becomes ``0b00110100``.
+The shift value is treated as an unsigned amount modulo the size of
+the arguments. Both arguments and the result have the bitwidth specified
+by the name of the builtin.
+
+``__builtin_rotateright``
+_------------------------
+
+* ``__builtin_rotateright8``
+* ``__builtin_rotateright16``
+* ``__builtin_rotateright32``
+* ``__builtin_rotateright64``
+
+**Syntax**:
+
+.. code-block:: c++
+
+     __builtin_rotateright32(x, y)
+
+**Examples**:
+
+.. code-block:: c++
+
+      uint8_t rot_x = __builtin_rotateright8(x, y);
+      uint16_t rot_x = __builtin_rotateright16(x, y);
+      uint32_t rot_x = __builtin_rotateright32(x, y);
+      uint64_t rot_x = __builtin_rotateright64(x, y);
+
+**Description**:
+
+The '``__builtin_rotateright``' family of builtins is used to rotate
+the bits in the first argument by the amount in the second argument. 
+For example, ``0b10000110`` rotated right by 3 becomes ``0b11010000``.
+The shift value is treated as an unsigned amount modulo the size of
+the arguments. Both arguments and the result have the bitwidth specified
+by the name of the builtin.
+
 ``__builtin_unreachable``
 -------------------------
 
 ``__builtin_unreachable`` is used to indicate that a specific point in the
 program cannot be reached, even if the compiler might otherwise think it can.
 This is useful to improve optimization and eliminates certain warnings.  For
 example, without the ``__builtin_unreachable`` in the example below, the
 compiler assumes that the inline asm can fall through and prints a "function

cfe/trunk/include/clang/Basic/Builtins.def

 BUILTIN(__builtin_bswap32, "UiUi", "nc")
 BUILTIN(__builtin_bswap64, "ULLiULLi", "nc")
 
 BUILTIN(__builtin_bitreverse8, "UcUc", "nc")
 BUILTIN(__builtin_bitreverse16, "UsUs", "nc")
 BUILTIN(__builtin_bitreverse32, "UiUi", "nc")
 BUILTIN(__builtin_bitreverse64, "ULLiULLi", "nc")
 
+BUILTIN(__builtin_rotateleft8, "UcUcUc", "nc")
+BUILTIN(__builtin_rotateleft16, "UsUsUs", "nc")
+BUILTIN(__builtin_rotateleft32, "UiUiUi", "nc")
+BUILTIN(__builtin_rotateleft64, "ULLiULLiULLi", "nc")
+BUILTIN(__builtin_rotateright8, "UcUcUc", "nc")
+BUILTIN(__builtin_rotateright16, "UsUsUs", "nc")
+BUILTIN(__builtin_rotateright32, "UiUiUi", "nc")
+BUILTIN(__builtin_rotateright64, "ULLiULLiULLi", "nc")
+
 // Random GCC builtins
 BUILTIN(__builtin_constant_p, "i.", "nctu")
 BUILTIN(__builtin_classify_type, "i.", "nctu")
 BUILTIN(__builtin___CFStringMakeConstantString, "FC*cC*", "nc")
 BUILTIN(__builtin___NSStringMakeConstantString, "FC*cC*", "nc")
 BUILTIN(__builtin_va_start, "vA.", "nt")
 BUILTIN(__builtin_va_end, "vA", "n")
 BUILTIN(__builtin_va_copy, "vAA", "n")

cfe/trunk/lib/CodeGen/CGBuiltin.cpp

static llvm::Value *dumpRecord(CodeGenFunction &CGF, QualType RType,
   }
 
   GString = CGF.Builder.CreateGlobalStringPtr(Pad + "}\n");
   Value *TmpRes = CGF.Builder.CreateCall(Func, {GString});
   Res = CGF.Builder.CreateAdd(Res, TmpRes);
   return Res;
 }
 
+RValue CodeGenFunction::emitRotate(const CallExpr *E, bool IsRotateRight) {
+  llvm::Value *Src = EmitScalarExpr(E->getArg(0));
+  llvm::Value *ShiftAmt = EmitScalarExpr(E->getArg(1));
+
+  // The builtin's shift arg may have a different type than the source arg and
+  // result, but the LLVM intrinsic uses the same type for all values.
+  llvm::Type *Ty = Src->getType();
+  ShiftAmt = Builder.CreateIntCast(ShiftAmt, Ty, false);
+
+  // Rotate is a special case of LLVM funnel shift - 1st 2 args are the same.
+  unsigned IID = IsRotateRight ? Intrinsic::fshr : Intrinsic::fshl;
+  Value *F = CGM.getIntrinsic(IID, Ty);
+  return RValue::get(Builder.CreateCall(F, { Src, Src, ShiftAmt }));
+}
+
 RValue CodeGenFunction::EmitBuiltinExpr(const FunctionDecl *FD,
                                         unsigned BuiltinID, const CallExpr *E,
                                         ReturnValueSlot ReturnValue) {
   // See if we can constant fold this builtin.  If so, don't emit it at all.
   Expr::EvalResult Result;
   if (E->EvaluateAsRValue(Result, CGM.getContext()) &&
       !Result.hasSideEffects()) {
     if (Result.Val.isInt())
case Builtin::BI__builtin_bswap64: {
     return RValue::get(emitUnaryBuiltin(*this, E, Intrinsic::bswap));
   }
   case Builtin::BI__builtin_bitreverse8:
   case Builtin::BI__builtin_bitreverse16:
   case Builtin::BI__builtin_bitreverse32:
   case Builtin::BI__builtin_bitreverse64: {
     return RValue::get(emitUnaryBuiltin(*this, E, Intrinsic::bitreverse));
   }
+  case Builtin::BI__builtin_rotateleft8:
+  case Builtin::BI__builtin_rotateleft16:
+  case Builtin::BI__builtin_rotateleft32:
+  case Builtin::BI__builtin_rotateleft64:
+    return emitRotate(E, false);
+
+  case Builtin::BI__builtin_rotateright8:
+  case Builtin::BI__builtin_rotateright16:
+  case Builtin::BI__builtin_rotateright32:
+  case Builtin::BI__builtin_rotateright64:
+    return emitRotate(E, true);
+
   case Builtin::BI__builtin_object_size: {
     unsigned Type =
         E->getArg(1)->EvaluateKnownConstInt(getContext()).getZExtValue();
     auto *ResType = cast<llvm::IntegerType>(ConvertType(E->getType()));
 
     // We pass this builtin onto the optimizer so that it can figure out the
     // object size in more complex cases.
     return RValue::get(emitBuiltinObjectSize(E->getArg(0), Type, ResType,

cfe/trunk/lib/CodeGen/CodeGenFunction.h

public:
 
   RValue EmitNVPTXDevicePrintfCallExpr(const CallExpr *E,
                                        ReturnValueSlot ReturnValue);
 
   RValue EmitBuiltinExpr(const FunctionDecl *FD,
                          unsigned BuiltinID, const CallExpr *E,
                          ReturnValueSlot ReturnValue);
 
+  RValue emitRotate(const CallExpr *E, bool IsRotateRight);
+
   /// Emit IR for __builtin_os_log_format.
   RValue emitBuiltinOSLogFormat(const CallExpr &E);
 
   llvm::Function *generateBuiltinOSLogHelperFunction(
       const analyze_os_log::OSLogBufferLayout &Layout,
       CharUnits BufferAlignment);
 
   RValue EmitBlockCallExpr(const CallExpr *E, ReturnValueSlot ReturnValue);