From fdd6e1b2e5e139a574f19788c71ae44dfaafa404 Mon Sep 17 00:00:00 2001 From: James Molloy Date: Thu, 12 Nov 2015 12:29:09 +0000 Subject: [PATCH] [SDAG] Introduce a new BITREVERSE node along with a corresponding LLVM intrinsic Several backends have instructions to reverse the order of bits in an integer. Conceptually matching such patterns is similar to @llvm.bswap, and it was mentioned in http://reviews.llvm.org/D14234 that it would be best if these patterns were matched in InstCombine instead of reimplemented in every different target. This patch introduces an intrinsic @llvm.bitreverse.i* that operates similarly to @llvm.bswap. For plumbing purposes there is also a new ISD node ISD::BITREVERSE, with simple expansion and promotion support. The intention is that InstCombine's BSWAP detection logic will be extended to support BITREVERSE too, and @llvm.bitreverse intrinsics emitted (if the backend supports lowering it efficiently). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@252878 91177308-0d34-0410-b5e6-96231b3b80d8 --- docs/LangRef.rst | 28 +++++++++++++++++++++++ include/llvm/CodeGen/ISDOpcodes.h | 2 +- include/llvm/IR/Intrinsics.td | 1 + lib/CodeGen/SelectionDAG/LegalizeDAG.cpp | 27 ++++++++++++++++++++++ lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp | 23 +++++++++++++++++++ lib/CodeGen/SelectionDAG/LegalizeTypes.h | 2 ++ lib/CodeGen/SelectionDAG/LegalizeVectorTypes.cpp | 3 +++ lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp | 5 ++++ lib/CodeGen/SelectionDAG/SelectionDAGDumper.cpp | 3 ++- lib/CodeGen/TargetLoweringBase.cpp | 3 ++- test/CodeGen/AArch64/bitreverse.ll | 23 +++++++++++++++++++ test/CodeGen/PowerPC/bitreverse.ll | 23 +++++++++++++++++++ test/CodeGen/X86/bitreverse.ll | 22 ++++++++++++++++++ 13 files changed, 162 insertions(+), 3 deletions(-) create mode 100644 test/CodeGen/AArch64/bitreverse.ll create mode 100644 test/CodeGen/PowerPC/bitreverse.ll create mode 100644 test/CodeGen/X86/bitreverse.ll diff --git a/docs/LangRef.rst b/docs/LangRef.rst index 0e4eae0df80..5273bf0ac11 100644 --- a/docs/LangRef.rst +++ b/docs/LangRef.rst @@ -10417,6 +10417,34 @@ Bit Manipulation Intrinsics LLVM provides intrinsics for a few important bit manipulation operations. These allow efficient code generation for some algorithms. +'``llvm.bitreverse.*``' Intrinsics +^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ + +Syntax: +""""""" + +This is an overloaded intrinsic function. You can use bitreverse on any +integer type. + +:: + + declare i16 @llvm.bitreverse.i16(i16 ) + declare i32 @llvm.bitreverse.i32(i32 ) + declare i64 @llvm.bitreverse.i64(i64 ) + +Overview: +""""""""" + +The '``llvm.bitreverse``' family of intrinsics is used to reverse the +bitpattern of an integer value; for example ``0b1234567`` becomes +``0b7654321``. + +Semantics: +"""""""""" + +The ``llvm.bitreverse.iN`` intrinsic returns an i16 value that has bit +``M`` in the input moved to bit ``N-M`` in the output. + '``llvm.bswap.*``' Intrinsics ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ diff --git a/include/llvm/CodeGen/ISDOpcodes.h b/include/llvm/CodeGen/ISDOpcodes.h index 4ca73914b72..c7f54655f84 100644 --- a/include/llvm/CodeGen/ISDOpcodes.h +++ b/include/llvm/CodeGen/ISDOpcodes.h @@ -336,7 +336,7 @@ namespace ISD { SHL, SRA, SRL, ROTL, ROTR, /// Byte Swap and Counting operators. - BSWAP, CTTZ, CTLZ, CTPOP, + BSWAP, CTTZ, CTLZ, CTPOP, BITREVERSE, /// [SU]ABSDIFF - Signed/Unsigned absolute difference of two input integer /// vector. These nodes are generated from llvm.*absdiff* intrinsics. diff --git a/include/llvm/IR/Intrinsics.td b/include/llvm/IR/Intrinsics.td index 6eade5d0a91..66ef6fb1e5e 100644 --- a/include/llvm/IR/Intrinsics.td +++ b/include/llvm/IR/Intrinsics.td @@ -400,6 +400,7 @@ let Properties = [IntrNoMem] in { def int_ctpop: Intrinsic<[llvm_anyint_ty], [LLVMMatchType<0>]>; def int_ctlz : Intrinsic<[llvm_anyint_ty], [LLVMMatchType<0>, llvm_i1_ty]>; def int_cttz : Intrinsic<[llvm_anyint_ty], [LLVMMatchType<0>, llvm_i1_ty]>; + def int_bitreverse : Intrinsic<[llvm_anyint_ty], [LLVMMatchType<0>]>; } //===------------------------ Debugger Intrinsics -------------------------===// diff --git a/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp b/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp index 8fae6e2dacd..186697d3d02 100644 --- a/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp +++ b/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp @@ -145,6 +145,7 @@ private: SDValue PromoteLegalFP_TO_INT(SDValue LegalOp, EVT DestVT, bool isSigned, SDLoc dl); + SDValue ExpandBITREVERSE(SDValue Op, SDLoc dl); SDValue ExpandBSWAP(SDValue Op, SDLoc dl); SDValue ExpandBitCount(unsigned Opc, SDValue Op, SDLoc dl); @@ -2775,6 +2776,29 @@ SDValue SelectionDAGLegalize::PromoteLegalFP_TO_INT(SDValue LegalOp, return DAG.getNode(ISD::TRUNCATE, dl, DestVT, Operation); } +/// Open code the operations for BITREVERSE. +SDValue SelectionDAGLegalize::ExpandBITREVERSE(SDValue Op, SDLoc dl) { + EVT VT = Op.getValueType(); + EVT SHVT = TLI.getShiftAmountTy(VT, DAG.getDataLayout()); + unsigned Sz = VT.getSizeInBits(); + + SDValue Tmp, Tmp2; + Tmp = DAG.getConstant(0, dl, VT); + for (unsigned I = 0, J = Sz-1; I < Sz; ++I, --J) { + if (I < J) + Tmp2 = + DAG.getNode(ISD::SHL, dl, VT, Op, DAG.getConstant(J - I, dl, SHVT)); + else + Tmp2 = + DAG.getNode(ISD::SRL, dl, VT, Op, DAG.getConstant(I - J, dl, SHVT)); + Tmp2 = + DAG.getNode(ISD::AND, dl, VT, Tmp2, DAG.getConstant(1U << J, dl, VT)); + Tmp = DAG.getNode(ISD::OR, dl, VT, Tmp, Tmp2); + } + + return Tmp; +} + /// Open code the operations for BSWAP of the specified operation. SDValue SelectionDAGLegalize::ExpandBSWAP(SDValue Op, SDLoc dl) { EVT VT = Op.getValueType(); @@ -2941,6 +2965,9 @@ bool SelectionDAGLegalize::ExpandNode(SDNode *Node) { Tmp1 = ExpandBitCount(Node->getOpcode(), Node->getOperand(0), dl); Results.push_back(Tmp1); break; + case ISD::BITREVERSE: + Results.push_back(ExpandBITREVERSE(Node->getOperand(0), dl)); + break; case ISD::BSWAP: Results.push_back(ExpandBSWAP(Node->getOperand(0), dl)); break; diff --git a/lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp b/lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp index 108c07d3303..3c7586db0ab 100644 --- a/lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp +++ b/lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp @@ -53,6 +53,7 @@ void DAGTypeLegalizer::PromoteIntegerResult(SDNode *N, unsigned ResNo) { case ISD::AssertSext: Res = PromoteIntRes_AssertSext(N); break; case ISD::AssertZext: Res = PromoteIntRes_AssertZext(N); break; case ISD::BITCAST: Res = PromoteIntRes_BITCAST(N); break; + case ISD::BITREVERSE: Res = PromoteIntRes_BITREVERSE(N); break; case ISD::BSWAP: Res = PromoteIntRes_BSWAP(N); break; case ISD::BUILD_PAIR: Res = PromoteIntRes_BUILD_PAIR(N); break; case ISD::Constant: Res = PromoteIntRes_Constant(N); break; @@ -320,6 +321,19 @@ SDValue DAGTypeLegalizer::PromoteIntRes_BSWAP(SDNode *N) { TLI.getShiftAmountTy(NVT, DAG.getDataLayout()))); } +SDValue DAGTypeLegalizer::PromoteIntRes_BITREVERSE(SDNode *N) { + SDValue Op = GetPromotedInteger(N->getOperand(0)); + EVT OVT = N->getValueType(0); + EVT NVT = Op.getValueType(); + SDLoc dl(N); + + unsigned DiffBits = NVT.getScalarSizeInBits() - OVT.getScalarSizeInBits(); + return DAG.getNode( + ISD::SRL, dl, NVT, DAG.getNode(ISD::BITREVERSE, dl, NVT, Op), + DAG.getConstant(DiffBits, dl, + TLI.getShiftAmountTy(NVT, DAG.getDataLayout()))); +} + SDValue DAGTypeLegalizer::PromoteIntRes_BUILD_PAIR(SDNode *N) { // The pair element type may be legal, or may not promote to the same type as // the result, for example i14 = BUILD_PAIR (i7, i7). Handle all cases. @@ -1263,6 +1277,7 @@ void DAGTypeLegalizer::ExpandIntegerResult(SDNode *N, unsigned ResNo) { case ISD::ANY_EXTEND: ExpandIntRes_ANY_EXTEND(N, Lo, Hi); break; case ISD::AssertSext: ExpandIntRes_AssertSext(N, Lo, Hi); break; case ISD::AssertZext: ExpandIntRes_AssertZext(N, Lo, Hi); break; + case ISD::BITREVERSE: ExpandIntRes_BITREVERSE(N, Lo, Hi); break; case ISD::BSWAP: ExpandIntRes_BSWAP(N, Lo, Hi); break; case ISD::Constant: ExpandIntRes_Constant(N, Lo, Hi); break; case ISD::CTLZ_ZERO_UNDEF: @@ -1833,6 +1848,14 @@ void DAGTypeLegalizer::ExpandIntRes_AssertZext(SDNode *N, } } +void DAGTypeLegalizer::ExpandIntRes_BITREVERSE(SDNode *N, + SDValue &Lo, SDValue &Hi) { + SDLoc dl(N); + GetExpandedInteger(N->getOperand(0), Hi, Lo); // Note swapped operands. + Lo = DAG.getNode(ISD::BITREVERSE, dl, Lo.getValueType(), Lo); + Hi = DAG.getNode(ISD::BITREVERSE, dl, Hi.getValueType(), Hi); +} + void DAGTypeLegalizer::ExpandIntRes_BSWAP(SDNode *N, SDValue &Lo, SDValue &Hi) { SDLoc dl(N); diff --git a/lib/CodeGen/SelectionDAG/LegalizeTypes.h b/lib/CodeGen/SelectionDAG/LegalizeTypes.h index 5d8e46b142e..7f4501e4b67 100644 --- a/lib/CodeGen/SelectionDAG/LegalizeTypes.h +++ b/lib/CodeGen/SelectionDAG/LegalizeTypes.h @@ -234,6 +234,7 @@ private: SDValue PromoteIntRes_CONCAT_VECTORS(SDNode *N); SDValue PromoteIntRes_BITCAST(SDNode *N); SDValue PromoteIntRes_BSWAP(SDNode *N); + SDValue PromoteIntRes_BITREVERSE(SDNode *N); SDValue PromoteIntRes_BUILD_PAIR(SDNode *N); SDValue PromoteIntRes_Constant(SDNode *N); SDValue PromoteIntRes_CONVERT_RNDSAT(SDNode *N); @@ -330,6 +331,7 @@ private: void ExpandIntRes_ADDSUB (SDNode *N, SDValue &Lo, SDValue &Hi); void ExpandIntRes_ADDSUBC (SDNode *N, SDValue &Lo, SDValue &Hi); void ExpandIntRes_ADDSUBE (SDNode *N, SDValue &Lo, SDValue &Hi); + void ExpandIntRes_BITREVERSE (SDNode *N, SDValue &Lo, SDValue &Hi); void ExpandIntRes_BSWAP (SDNode *N, SDValue &Lo, SDValue &Hi); void ExpandIntRes_MUL (SDNode *N, SDValue &Lo, SDValue &Hi); void ExpandIntRes_SDIV (SDNode *N, SDValue &Lo, SDValue &Hi); diff --git a/lib/CodeGen/SelectionDAG/LegalizeVectorTypes.cpp b/lib/CodeGen/SelectionDAG/LegalizeVectorTypes.cpp index dffcaaa14d9..96b8cc065f5 100644 --- a/lib/CodeGen/SelectionDAG/LegalizeVectorTypes.cpp +++ b/lib/CodeGen/SelectionDAG/LegalizeVectorTypes.cpp @@ -67,6 +67,7 @@ void DAGTypeLegalizer::ScalarizeVectorResult(SDNode *N, unsigned ResNo) { case ISD::UNDEF: R = ScalarizeVecRes_UNDEF(N); break; case ISD::VECTOR_SHUFFLE: R = ScalarizeVecRes_VECTOR_SHUFFLE(N); break; case ISD::ANY_EXTEND: + case ISD::BITREVERSE: case ISD::BSWAP: case ISD::CTLZ: case ISD::CTLZ_ZERO_UNDEF: @@ -616,6 +617,7 @@ void DAGTypeLegalizer::SplitVectorResult(SDNode *N, unsigned ResNo) { SplitVecRes_VECTOR_SHUFFLE(cast(N), Lo, Hi); break; + case ISD::BITREVERSE: case ISD::BSWAP: case ISD::CONVERT_RNDSAT: case ISD::CTLZ: @@ -2027,6 +2029,7 @@ void DAGTypeLegalizer::WidenVectorResult(SDNode *N, unsigned ResNo) { Res = WidenVecRes_Convert(N); break; + case ISD::BITREVERSE: case ISD::BSWAP: case ISD::CTLZ: case ISD::CTPOP: diff --git a/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp b/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp index 5090bfbfb14..63b5d02a65a 100644 --- a/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp +++ b/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp @@ -4872,6 +4872,11 @@ SelectionDAGBuilder::visitIntrinsicCall(const CallInst &I, unsigned Intrinsic) { DAG.setRoot(Res.getValue(1)); return nullptr; } + case Intrinsic::bitreverse: + setValue(&I, DAG.getNode(ISD::BITREVERSE, sdl, + getValue(I.getArgOperand(0)).getValueType(), + getValue(I.getArgOperand(0)))); + return nullptr; case Intrinsic::bswap: setValue(&I, DAG.getNode(ISD::BSWAP, sdl, getValue(I.getArgOperand(0)).getValueType(), diff --git a/lib/CodeGen/SelectionDAG/SelectionDAGDumper.cpp b/lib/CodeGen/SelectionDAG/SelectionDAGDumper.cpp index 8034634d530..541cb367902 100644 --- a/lib/CodeGen/SelectionDAG/SelectionDAGDumper.cpp +++ b/lib/CodeGen/SelectionDAG/SelectionDAGDumper.cpp @@ -311,13 +311,14 @@ std::string SDNode::getOperationName(const SelectionDAG *G) const { case ISD::GC_TRANSITION_END: return "gc_transition.end"; // Bit manipulation + case ISD::BITREVERSE: return "bitreverse"; case ISD::BSWAP: return "bswap"; case ISD::CTPOP: return "ctpop"; case ISD::CTTZ: return "cttz"; case ISD::CTTZ_ZERO_UNDEF: return "cttz_zero_undef"; case ISD::CTLZ: return "ctlz"; case ISD::CTLZ_ZERO_UNDEF: return "ctlz_zero_undef"; - + // Trampolines case ISD::INIT_TRAMPOLINE: return "init_trampoline"; case ISD::ADJUST_TRAMPOLINE: return "adjust_trampoline"; diff --git a/lib/CodeGen/TargetLoweringBase.cpp b/lib/CodeGen/TargetLoweringBase.cpp index 45c6c9e4b2a..e348095aa8f 100644 --- a/lib/CodeGen/TargetLoweringBase.cpp +++ b/lib/CodeGen/TargetLoweringBase.cpp @@ -828,7 +828,8 @@ void TargetLoweringBase::initActions() { setOperationAction(ISD::UMULO, VT, Expand); setOperationAction(ISD::UABSDIFF, VT, Expand); setOperationAction(ISD::SABSDIFF, VT, Expand); - + setOperationAction(ISD::BITREVERSE, VT, Expand); + // These library functions default to expand. setOperationAction(ISD::FROUND, VT, Expand); diff --git a/test/CodeGen/AArch64/bitreverse.ll b/test/CodeGen/AArch64/bitreverse.ll new file mode 100644 index 00000000000..b780412f765 --- /dev/null +++ b/test/CodeGen/AArch64/bitreverse.ll @@ -0,0 +1,23 @@ +; RUN: llc -mtriple=aarch64-eabi %s -o - | FileCheck %s + +; These tests just check that the plumbing is in place for @llvm.bitreverse. The +; actual output is massive at the moment as llvm.bitreverse is not yet legal. + +declare <2 x i16> @llvm.bitreverse.v2i16(<2 x i16>) readnone + +define <2 x i16> @f(<2 x i16> %a) { +; CHECK-LABEL: f: +; CHECK: ushr + %b = call <2 x i16> @llvm.bitreverse.v2i16(<2 x i16> %a) + ret <2 x i16> %b +} + +declare i8 @llvm.bitreverse.i8(i8) readnone + +define i8 @g(i8 %a) { +; CHECK-LABEL: g: +; CHECK: lsl +; CHECK: and + %b = call i8 @llvm.bitreverse.i8(i8 %a) + ret i8 %b +} diff --git a/test/CodeGen/PowerPC/bitreverse.ll b/test/CodeGen/PowerPC/bitreverse.ll new file mode 100644 index 00000000000..1c3741a9a69 --- /dev/null +++ b/test/CodeGen/PowerPC/bitreverse.ll @@ -0,0 +1,23 @@ +; RUN: llc -march=ppc64 %s -o - | FileCheck %s + +; These tests just check that the plumbing is in place for @llvm.bitreverse. The +; actual output is massive at the moment as llvm.bitreverse is not yet legal. + +declare <2 x i16> @llvm.bitreverse.v2i16(<2 x i16>) readnone + +define <2 x i16> @f(<2 x i16> %a) { +; CHECK-LABEL: f: +; CHECK: rlwinm + %b = call <2 x i16> @llvm.bitreverse.v2i16(<2 x i16> %a) + ret <2 x i16> %b +} + +declare i8 @llvm.bitreverse.i8(i8) readnone + +define i8 @g(i8 %a) { +; CHECK-LABEL: g: +; CHECK: rlwinm +; CHECK: rlwimi + %b = call i8 @llvm.bitreverse.i8(i8 %a) + ret i8 %b +} diff --git a/test/CodeGen/X86/bitreverse.ll b/test/CodeGen/X86/bitreverse.ll new file mode 100644 index 00000000000..e3bc8ace38a --- /dev/null +++ b/test/CodeGen/X86/bitreverse.ll @@ -0,0 +1,22 @@ +; RUN: llc -march=x86 %s -o - | FileCheck %s + +; These tests just check that the plumbing is in place for @llvm.bitreverse. The +; actual output is massive at the moment as llvm.bitreverse is not yet legal. + +declare <2 x i16> @llvm.bitreverse.v2i16(<2 x i16>) readnone + +define <2 x i16> @f(<2 x i16> %a) { +; CHECK-LABEL: f: +; CHECK: shll + %b = call <2 x i16> @llvm.bitreverse.v2i16(<2 x i16> %a) + ret <2 x i16> %b +} + +declare i8 @llvm.bitreverse.i8(i8) readnone + +define i8 @g(i8 %a) { +; CHECK-LABEL: g: +; CHECK: shlb + %b = call i8 @llvm.bitreverse.i8(i8 %a) + ret i8 %b +} -- 2.11.0