Generate efficient code for rotation patterns.
authorEugene Rozenfeld <erozen@microsoft.com>
Tue, 13 Oct 2015 01:36:25 +0000 (18:36 -0700)
committerEugene Rozenfeld <erozen@microsoft.com>
Thu, 22 Oct 2015 01:51:48 +0000 (18:51 -0700)
commit7b4508ba9419157570a9c47e4ebc8a79dcc53a11
treecf3feb736ff173462fc82b71633f2d66e75ee9cc
parent65b55ab02eba5fc71daadb0db9f4d4a424906dba
 Generate efficient code for rotation patterns.

     This change adds code to recognize rotation idioms and generate efficient instructions for them.

     Two new operators are added: GT_ROL and GT_ROR.

     The patterns recognized:
     (x << c1) | (x >>> c2) => x rol c1
     (x >>> c1) | (x << c2) => x ror c2

     where c1 and c2  are constant and c1 + c2 == bitsize(x)

     (x << y) | (x >>> (N - y)) => x rol y
     (x >>> y) | (x << (N - y)) => x ror y

     where N == bitsize(x)

     (x << y & M1) | (x >>> (N - y) & M2) => x rol y
     (x >>> y & M1) | (x << (N - y) & M2) => x ror y

     where N == bitsize(x)
     M1 & (N - 1) == N - 1
     M2 & (N - 1) == N - 1

     For a simple benchmark with 4 rotation patterns in a tight loop
     time goes from 7.324 to 2.600 (2.8 speedup).

     Rotations found and optimized in mscorlib:
     System.Security.Cryptography.SHA256Managed::RotateRight
     System.Security.Cryptography.SHA384Managed::RotateRight
     System.Security.Cryptography.SHA512Managed::RotateRight
     System.Security.Cryptography.RIPEMD160Managed:MDTransform (320 instances!)
     System.Diagnostics.Tracing.EventSource.Sha1ForNonSecretPurposes::Rol1
     System.Diagnostics.Tracing.EventSource.Sha1ForNonSecretPurposes::Rol5
     System.Diagnostics.Tracing.EventSource.Sha1ForNonSecretPurposes::Rol30
     System.Diagnostics.Tracing.EventSource.Sha1ForNonSecretPurposes::Drain
     (9 instances of Sha1ForNonSecretPurposes::Rol* inlined)

     Closes #1619.
21 files changed:
src/jit/codegenarm64.cpp
src/jit/codegenxarch.cpp
src/jit/compiler.h
src/jit/emitxarch.cpp
src/jit/gentree.cpp
src/jit/gentree.h
src/jit/gtlist.h
src/jit/instr.cpp
src/jit/instrsxarch.h
src/jit/lclvars.cpp
src/jit/lower.cpp
src/jit/lower.h
src/jit/lowerarm.cpp
src/jit/lowerarm64.cpp
src/jit/lowerxarch.cpp
src/jit/lsra.cpp
src/jit/morph.cpp
src/jit/optcse.cpp
src/jit/valuenum.cpp
tests/src/JIT/CodeGenBringUpTests/Rotate.cs [new file with mode: 0644]
tests/src/JIT/CodeGenBringUpTests/Rotate.csproj [new file with mode: 0644]