[clang] Speedup line offset mapping computation

[serge-sans-paille]

Summary

Instead of scanning byte after byte, scan words after words and rely on a bithack to perform the scan efficiently.

[tschuett]

Would it help readability and portability to change unsigned long to either uintptr_t, uint32_t, or uint64_t?

[lattner]

Very cool. Please follow clang-format's requests. Does this measurably speed things up?

clang used to have hand-vectorized code for SSE and Altivec, but it looks like someone removed it. The

#ifdef __SSE2__
#include <emmintrin.h>
#endif

is a remnant of that, it looks like you could drop that now, or investigate why it was removed and see if it is worth doing something related but updated to newer processors. You might also be interested in checking out llvm/lib/Support/SourceMgr.cpp which has similar algorithms and can also be sped up. It is widely used by mlir and other LLVM ecosystem projects.

-Chris

[lattner]

Looks like it was deleted here:
https://github.com/llvm/llvm-project/commit/d906e731ece9942260df4097ed8e8b4cbfa70d32#diff-81963619e10845105426b4071463347e3af6addea3fc4a9a31ceb207c7986fd3

[serge-sans-paille]

Thanks for pointing me at the former SSE implementation. This got me into deep thoughts, I've been trying various approaches, among which:

• sequential optimization, basically the one currently in main
• various optimization involving casting to uint64_t and doing various bit twiddling (damn, bit hacks are fun)
• SSE / AVX optimization, based on the 2012 version.

So far, vectorization is the fastest one, I derived from the 2012 version a bit, leading to relatively simple and explicit bitcode.

My test bed is the following: computing the average (over 1000 runs) time run spent the following command: ./bin/clang -w -o/dev/null sqlite3.c -E

former sse version: 0.123s
trunk version: 0.122s
bithacked version: 0.118s
new sse version: 0.115s

the bithacked version is arch-agnostic but more complex to follow, the sse version is very easy to read and faster.

bithacked version: https://github.com/serge-sans-paille/llvm-project/blob/feature/line-offset-bithack/clang/lib/Basic/SourceManager.cpp#L1285
sse version: https://github.com/serge-sans-paille/llvm-project/blob/feature/faster-line-offset-init/clang/lib/Basic/SourceManager.cpp#L1296
(it also contains an AVX implementation, which is slightly... slower)

so what do you think? I'd advocate for the new sse version, maybe @MaskRay has an opinion on this?

[lattner]

Since the target independent version is almost as fast, I'd go with it. Does it help to use LLVM_UNLIKELY with likelyhasbetween ?

[dexonsmith]

Drive-by question:

In D99409#2658848, @serge-sans-paille wrote:

former sse version: 0.123s
trunk version: 0.122s
bithacked version: 0.118s
new sse version: 0.115ms

The units are different for the new SSE version, indicating that it's ~1000x faster than the others. Is that a typo?

[MaskRay]

In D99409#2659627, @lattner wrote:

Since the target independent version is almost as fast, I'd go with it. Does it help to use LLVM_UNLIKELY with likelyhasbetween ?

+1

clang/lib/Basic/SourceManager.cpp

1281

Capitalize comments.

1283

if( -> if (

1296

replace tabs with spaces

[serge-sans-paille]

On a personnal note, I consider the SSE2 version easier to read and maintain, and SSE2 is a *very* widespread instruction set. The way I've split the implementation and the architectural detail should make it easy to port it to other architecture - I can do it for NEON if needs be.

@MaskRay / @lattner can you confirm you want to stay with the « bit hack » version? Note that I don't have strong opinion on this choice, but I still had one I wanted to share ;-)

[serge-sans-paille]

[EDIT] I updated the bithack link on github, it wasn't the latest version I had, and not the one I benchmarked.

[lattner]

Yeah, I'd stay with the bithack version, but i'd recommend refactoring it to use some helper functions with evocative names.

[serge-sans-paille]

Thanks @lattner for the feedback. I wasn't super happy with the stability of the performance, so I isolated the function in a standalone file, and benchmarked several implementations. All the sources are available there: https://github.com/serge-sans-paille/mapping-line-to-offset

I get different result depending on how I configure my CPU (basically enabling Turbo-Boost or not).
With Turbo-boost (in ms):

ref: 11.01
seq: 10.86
bithack: 5.01
sse_align: 5
sse: 3

Without Turbo-boost (still in ms)

ref: 23.01
seq: 22.04
bithack: 11.02
sse_align: 10
sse: 6

Does it make you change your mind ? ;-)
I'll happily gather more data, it should be as simple as running make perf -C src once the repo above is cloned.

[serge-sans-paille]

For complentess, I must mention another optimization: run a first memchr(Buf, BufLen, '\r') and if it finds nothing, use a fast path. That brings interesting speedup for the ref and seq version, but not for the SSE one. And it makes the code more difficult to read.

[lattner]

Ok, I don't care very strongly one way or the other. The appeal of the bithack version was that it works on non-x86 systems.

[serge-sans-paille]

After a great deal of benchmarking on different architectures, I finally settled for the bithack version, as advised by @lattner . The usage of llvm::countTrailingZeros makes the implementation faster than the previous version and it's easier to read.

[lattner]

nice! There is something weird going on with the diff above, please make sure 'git diff' shows something reasonable before pushing. Thanks!

[serge-sans-paille]

Fix handling of final character

[MaskRay]

clang/lib/Basic/SourceManager.cpp

1259

Drop unneeded parentheses. This is not a macro

1290

It might be good converting the function into a closed internal form to avoid -1/+1 at call sites.

[serge-sans-paille]

Take @MaskRay comments into account

[RKSimon]

@serge-sans-paille Please can you look at the clang-ppc buildbot breakages: http://lab.llvm.org:8011/#/builders/52/builds/6108

[thakis]

Looks like this breaks tests on Windows: http://45.33.8.238/win/36495/step_7.txt (takes a bit to load, since many tests are broken)

Please take a look, and please revert for now if it takes a while to fix.

[thakis]

Here too: http://lab.llvm.org:8011/#/builders/127

[thakis]

Oh, looks like someone already reported a breakage over an hour ago. I'll revert for now...

[serge-sans-paille]

Thanks @thakis, inestigating the issue is likely to take some time as it seems to be arch or system dependent

[thakis]

clang/lib/Basic/SourceManager.cpp

1262

UL is 32-bit on windows but 64-bit on linux/mac in 64-bit builds (LP64 vs LLP64). Maybe you want 0ULL here?

If so, then you should be able to repro this on linux by building a 32-bit clang binary there.

[serge-sans-paille]

clang/lib/Basic/SourceManager.cpp

1262

That + some endianess issue on ppc64be, resubmit coming soon once I validate locally :-)

[probinson]

clang/lib/Basic/SourceManager.cpp

1255

Typo: multi-byte. Also, I think "inclusive" rather than "included" assuming you mean the range [m, n] rather than (m, n).

clang/lib/Basic/SourceManager.cpp

 
 unsigned SourceManager::getPresumedColumnNumber(SourceLocation Loc,
                                                 bool *Invalid) const {
   PresumedLoc PLoc = getPresumedLoc(Loc);
   if (isInvalid(PLoc, Invalid)) return 0;
   return PLoc.getColumn();
 }
 
-#ifdef __SSE2__
-#include <emmintrin.h>
-#endif
+// Check if mutli-byte word x has bytes between m and n, included. This may also
+// catch bytes equal to n + 1.
+// The returned value holds a 0x80 at each byte position that holds a match.
+// see http://graphics.stanford.edu/~seander/bithacks.html#HasBetweenInWord
+template <class T>
+static constexpr inline T likelyhasbetween(T x, unsigned char m,
+                                           unsigned char n) {
+  return ((x - ~0UL / 255 * (n + 1)) & ~x &
+          (x & ~0UL / 255 * 127) + ~0UL / 255 * (127 - (m - 1))) &
+         ~0UL / 255 * 128;
+}
 
 LineOffsetMapping LineOffsetMapping::get(llvm::MemoryBufferRef Buffer,
                                          llvm::BumpPtrAllocator &Alloc) {
+
   // Find the file offsets of all of the *physical* source lines.  This does
   // not look at trigraphs, escaped newlines, or anything else tricky.
   SmallVector<unsigned, 256> LineOffsets;
 
   // Line #1 starts at char 0.
   LineOffsets.push_back(0);
 
   const unsigned char *Buf = (const unsigned char *)Buffer.getBufferStart();
   const unsigned char *End = (const unsigned char *)Buffer.getBufferEnd();
   const std::size_t BufLen = End - Buf;
+
   unsigned I = 0;
+  uint64_t Word;
+
+  // scan sizeof(Word) bytes at a time for new lines.
+  // This is much faster than scanning each byte independently.
+  if (BufLen > sizeof(Word)) {
+    do {
+      memcpy(&Word, Buf + I, sizeof(Word));
+      // no new line => jump over sizeof(Word) bytes.
+      auto Mask = likelyhasbetween(Word, '\n', '\r');
+      if (!Mask) {
+        I += sizeof(Word);
+        continue;
+      }
+
+      // At that point, Mask contains 0x80 set at each byte that holds a value
+      // in [\n, \r + 1 [
+
+      // Scan for the next newline - it's very likely there's one.
+      unsigned N =
+          llvm::countTrailingZeros(Mask) - 7; // -7 because 0x80 is the marker
+      Word >>= N;
+      I += N / 8 + 1;
+      unsigned char Byte = Word;
+      if (Byte == '\n') {
+        LineOffsets.push_back(I);
+      } else if (Byte == '\r') {
+        // If this is \r\n, skip both characters.
+        if (Buf[I] == '\n')
+          ++I;
+        LineOffsets.push_back(I);
+      }
+    } while (I < BufLen - sizeof(Word) - 1);
+  }
+
+  // Handle tail using a regular check.
   while (I < BufLen) {
-    // Use a fast check to catch both newlines
-    if (LLVM_UNLIKELY(Buf[I] <= std::max('\n', '\r'))) {
-      if (Buf[I] == '\n') {
-        LineOffsets.push_back(I + 1);
-      } else if (Buf[I] == '\r') {
-        // If this is \r\n, skip both characters.
-        if (I + 1 < BufLen && Buf[I + 1] == '\n')
-          ++I;
-        LineOffsets.push_back(I + 1);
-      }
-    }
     ++I;
   }
 
   return LineOffsetMapping(LineOffsets, Alloc);
 }
 
 LineOffsetMapping::LineOffsetMapping(ArrayRef<unsigned> LineOffsets,
                                      llvm::BumpPtrAllocator &Alloc)

llvm/test/tools/llvm-objdump/X86/source-interleave-prefix.test

 ;; Test --prefix option.
 
 ;; Separators change from platform to platform. In POSIX the full path for the
 ;; directory './Inputs' appended with the file 'source-interleave-x86_64.c' is
 ;; './Inputs/source-interleave-x86_64.c'. For Windows it is
 ;; './Inputs\source-interleave-x86_64.c'. Platform specific tests are needed
 ;; since '\' may or may not be a separator.
 
 ;; Test prefix option ignored for relative paths.
 ;; For the test below it is possible to accept both '/' and '\' as a separator.
 
 ; RUN: sed -e "s,SRC_COMPDIR,./Inputs,g" %p/Inputs/source-interleave.ll > %t-relative-path.ll
 ; RUN: llc -o %t-relative-path.o -filetype=obj -mtriple=x86_64-pc-linux %t-relative-path.ll
-; RUN: llvm-objdump --prefix myprefix --source %t-relative-path.o 2>&1 | \
+; RUN: mkdir -p %t0 && cd %t0 && llvm-objdump --prefix myprefix --source %t-relative-path.o 2>&1 | \
 ; RUN:   FileCheck %s --check-prefix=CHECK-BROKEN-PREFIX -DFILE=%t-relative-path.o -DPREFIX=. -DCOMPDIR=/Inputs
 ; CHECK-BROKEN-PREFIX: warning: '[[FILE]]': failed to find source [[PREFIX]][[COMPDIR]]{{[/\\]}}source-interleave-x86_64.c
 
 ;; Test invalid source interleave fixed by adding the correct prefix.
 
 ; RUN: sed -e "s,SRC_COMPDIR,/Inputs,g" %p/Inputs/source-interleave.ll > %t-missing-prefix.ll
 ; RUN: llc -o %t-missing-prefix.o -filetype=obj -mtriple=x86_64-pc-linux %t-missing-prefix.ll
 ; RUN: llvm-objdump --prefix %p --source %t-missing-prefix.o 2>&1 | \