Don't unroll loops.

[ruiu]

Summary

Don't unroll loops.

[inglorion]

What goal does this patch accomplish? Looks like you introduced the unrolled loops in r287473, where you make the llvm-sha1 tool faster - what is the performance impact of this patch?

[ruiu]

This is for https://llvm.org/bugs/show_bug.cgi?id=31075. I just used Phabricator as a pastebin.

[inglorion]

Thanks!

lib/Support/SHA1.cpp

void SHA1::init() {
   InternalState.State[1] = SEED_1;
   InternalState.State[2] = SEED_2;
   InternalState.State[3] = SEED_3;
   InternalState.State[4] = SEED_4;
   InternalState.ByteCount = 0;
   InternalState.BufferOffset = 0;
 }
 
+static LLVM_ATTRIBUTE_ALWAYS_INLINE void
+rotate(uint32_t &A, uint32_t &B, uint32_t &C, uint32_t &D, uint32_t &E) {
+  uint32_t T = E;
+  E = D;
+  D = C;
+  C = B;
+  B = A;
+  A = T;
+}
+
 void SHA1::hashBlock() {
   uint32_t A = InternalState.State[0];
   uint32_t B = InternalState.State[1];
   uint32_t C = InternalState.State[2];
   uint32_t D = InternalState.State[3];
   uint32_t E = InternalState.State[4];
+  int I = 0;
+
+  for (; I < 16; ++I) {
+    E += ((B & (C ^ D)) ^ D) + blk0(InternalState.Buffer.L, I) + 0x5A827999 + rol(A, 5);
+    B = rol(B, 30);
+    rotate(A, B, C, D, E);
+  }
+
+  for (; I < 20; ++I) {
+    E += ((B & (C ^ D)) ^ D) + blk(InternalState.Buffer.L, I) + 0x5A827999 + rol(A, 5);
+    B = rol(B, 30);
+    rotate(A, B, C, D, E);
+  }
 
-  // 4 rounds of 20 operations each. Loop unrolled.
-  r0(A, B, C, D, E, 0, InternalState.Buffer.L);
-  r0(E, A, B, C, D, 1, InternalState.Buffer.L);
-  r0(D, E, A, B, C, 2, InternalState.Buffer.L);
-  r0(C, D, E, A, B, 3, InternalState.Buffer.L);
-  r0(B, C, D, E, A, 4, InternalState.Buffer.L);
-  r0(A, B, C, D, E, 5, InternalState.Buffer.L);
-  r0(E, A, B, C, D, 6, InternalState.Buffer.L);
-  r0(D, E, A, B, C, 7, InternalState.Buffer.L);
-  r0(C, D, E, A, B, 8, InternalState.Buffer.L);
-  r0(B, C, D, E, A, 9, InternalState.Buffer.L);
-  r0(A, B, C, D, E, 10, InternalState.Buffer.L);
-  r0(E, A, B, C, D, 11, InternalState.Buffer.L);
-  r0(D, E, A, B, C, 12, InternalState.Buffer.L);
-  r0(C, D, E, A, B, 13, InternalState.Buffer.L);
-  r0(B, C, D, E, A, 14, InternalState.Buffer.L);
-  r0(A, B, C, D, E, 15, InternalState.Buffer.L);
-  r1(E, A, B, C, D, 16, InternalState.Buffer.L);
-  r1(D, E, A, B, C, 17, InternalState.Buffer.L);
-  r1(C, D, E, A, B, 18, InternalState.Buffer.L);
-  r1(B, C, D, E, A, 19, InternalState.Buffer.L);
-
-  r2(A, B, C, D, E, 20, InternalState.Buffer.L);
-  r2(E, A, B, C, D, 21, InternalState.Buffer.L);
-  r2(D, E, A, B, C, 22, InternalState.Buffer.L);
-  r2(C, D, E, A, B, 23, InternalState.Buffer.L);
-  r2(B, C, D, E, A, 24, InternalState.Buffer.L);
-  r2(A, B, C, D, E, 25, InternalState.Buffer.L);
-  r2(E, A, B, C, D, 26, InternalState.Buffer.L);
-  r2(D, E, A, B, C, 27, InternalState.Buffer.L);
-  r2(C, D, E, A, B, 28, InternalState.Buffer.L);
-  r2(B, C, D, E, A, 29, InternalState.Buffer.L);
-  r2(A, B, C, D, E, 30, InternalState.Buffer.L);
-  r2(E, A, B, C, D, 31, InternalState.Buffer.L);
-  r2(D, E, A, B, C, 32, InternalState.Buffer.L);
-  r2(C, D, E, A, B, 33, InternalState.Buffer.L);
-  r2(B, C, D, E, A, 34, InternalState.Buffer.L);
-  r2(A, B, C, D, E, 35, InternalState.Buffer.L);
-  r2(E, A, B, C, D, 36, InternalState.Buffer.L);
-  r2(D, E, A, B, C, 37, InternalState.Buffer.L);
-  r2(C, D, E, A, B, 38, InternalState.Buffer.L);
-  r2(B, C, D, E, A, 39, InternalState.Buffer.L);
-
-  r3(A, B, C, D, E, 40, InternalState.Buffer.L);
-  r3(E, A, B, C, D, 41, InternalState.Buffer.L);
-  r3(D, E, A, B, C, 42, InternalState.Buffer.L);
-  r3(C, D, E, A, B, 43, InternalState.Buffer.L);
-  r3(B, C, D, E, A, 44, InternalState.Buffer.L);
-  r3(A, B, C, D, E, 45, InternalState.Buffer.L);
-  r3(E, A, B, C, D, 46, InternalState.Buffer.L);
-  r3(D, E, A, B, C, 47, InternalState.Buffer.L);
-  r3(C, D, E, A, B, 48, InternalState.Buffer.L);
-  r3(B, C, D, E, A, 49, InternalState.Buffer.L);
-  r3(A, B, C, D, E, 50, InternalState.Buffer.L);
-  r3(E, A, B, C, D, 51, InternalState.Buffer.L);
-  r3(D, E, A, B, C, 52, InternalState.Buffer.L);
-  r3(C, D, E, A, B, 53, InternalState.Buffer.L);
-  r3(B, C, D, E, A, 54, InternalState.Buffer.L);
-  r3(A, B, C, D, E, 55, InternalState.Buffer.L);
-  r3(E, A, B, C, D, 56, InternalState.Buffer.L);
-  r3(D, E, A, B, C, 57, InternalState.Buffer.L);
-  r3(C, D, E, A, B, 58, InternalState.Buffer.L);
-  r3(B, C, D, E, A, 59, InternalState.Buffer.L);
-
-  r4(A, B, C, D, E, 60, InternalState.Buffer.L);
-  r4(E, A, B, C, D, 61, InternalState.Buffer.L);
-  r4(D, E, A, B, C, 62, InternalState.Buffer.L);
-  r4(C, D, E, A, B, 63, InternalState.Buffer.L);
-  r4(B, C, D, E, A, 64, InternalState.Buffer.L);
-  r4(A, B, C, D, E, 65, InternalState.Buffer.L);
-  r4(E, A, B, C, D, 66, InternalState.Buffer.L);
-  r4(D, E, A, B, C, 67, InternalState.Buffer.L);
-  r4(C, D, E, A, B, 68, InternalState.Buffer.L);
-  r4(B, C, D, E, A, 69, InternalState.Buffer.L);
-  r4(A, B, C, D, E, 70, InternalState.Buffer.L);
-  r4(E, A, B, C, D, 71, InternalState.Buffer.L);
-  r4(D, E, A, B, C, 72, InternalState.Buffer.L);
-  r4(C, D, E, A, B, 73, InternalState.Buffer.L);
-  r4(B, C, D, E, A, 74, InternalState.Buffer.L);
-  r4(A, B, C, D, E, 75, InternalState.Buffer.L);
-  r4(E, A, B, C, D, 76, InternalState.Buffer.L);
-  r4(D, E, A, B, C, 77, InternalState.Buffer.L);
-  r4(C, D, E, A, B, 78, InternalState.Buffer.L);
-  r4(B, C, D, E, A, 79, InternalState.Buffer.L);
+  for (; I < 40; ++I) {
+    E += (B ^ C ^ D) + blk(InternalState.Buffer.L, I) + 0x6ED9EBA1 + rol(A, 5);
+    B = rol(B, 30);
+    rotate(A, B, C, D, E);
+  }
+
+  for (; I < 60; ++I) {
+    E += (((B | C) & D) | (B & C)) + blk(InternalState.Buffer.L, I) + 0x8F1BBCDC + rol(A, 5);
+    B = rol(B, 30);
+    rotate(A, B, C, D, E);
+  }
+
+  for (; I < 80; ++I) {
+    E += (B ^ C ^ D) + blk(InternalState.Buffer.L, I) + 0xCA62C1D6 + rol(A, 5);
+    B = rol(B, 30);
+    rotate(A, B, C, D, E);
+  }
 
   InternalState.State[0] += A;
   InternalState.State[1] += B;
   InternalState.State[2] += C;
   InternalState.State[3] += D;
   InternalState.State[4] += E;
 }
 

tools/CMakeLists.txt

 # Add LTO, llvm-ar, llvm-config, and llvm-profdata before clang, ExternalProject
 # requires targets specified in DEPENDS to exist before the call to
 # ExternalProject_Add.
 add_llvm_tool_subdirectory(lto)
 add_llvm_tool_subdirectory(gold)
 add_llvm_tool_subdirectory(llvm-ar)
 add_llvm_tool_subdirectory(llvm-config)
 add_llvm_tool_subdirectory(llvm-lto)
+add_llvm_tool_subdirectory(llvm-sha1)
 add_llvm_tool_subdirectory(llvm-profdata)
 
 # Projects supported via LLVM_EXTERNAL_*_SOURCE_DIR need to be explicitly
 # specified.
 add_llvm_external_project(clang)
 add_llvm_external_project(llgo)
 add_llvm_external_project(lld)
 add_llvm_external_project(lldb)

tools/llvm-sha1/CMakeLists.txt

+set(LLVM_LINK_COMPONENTS Core Support)
+add_llvm_tool(llvm-sha1 llvm-sha1.cpp)

tools/llvm-sha1/llvm-sha1.cpp

+//===-- llvm-sha1.cpp -----------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/ADT/StringRef.h"
+#include "llvm/Support/SHA1.h"
+#include "llvm/Support/MemoryBuffer.h"
+#include "llvm/Support/raw_ostream.h"
+#include <cstdlib>
+
+using namespace llvm;
+
+static void usage() {
+  llvm::errs() << "llvm-sha1 <file>\n";
+  exit(0);
+}
+
+static std::string toHex(StringRef Input) {
+  static const char *const LUT = "0123456789ABCDEF";
+  size_t Length = Input.size();
+
+  std::string Output;
+  Output.reserve(2 * Length);
+  for (size_t i = 0; i < Length; ++i) {
+    const unsigned char c = Input[i];
+    Output.push_back(LUT[c >> 4]);
+    Output.push_back(LUT[c & 15]);
+  }
+  return Output;
+}
+
+int main(int Argc, char **Argv) {
+  if (Argc != 2)
+    usage();
+
+  StringRef File = Argv[1];
+  auto MBOrErr = MemoryBuffer::getFile(File);
+  if (auto EC = MBOrErr.getError()) {
+    llvm::errs() << "cannot open " + File << "\n";
+    return 1;
+  }
+  MemoryBufferRef MB = (*MBOrErr)->getMemBufferRef();
+
+  SHA1 Hash;
+  Hash.update(MB.getBuffer());
+  llvm::outs() << toHex(Hash.final()) << "\n";
+  return 0;
+}