Use a fast path when initializing LineOffsetMapping

[serge-sans-paille]

Summary

Use the fact that the number of line break is lower than printable characters to
guide the optimization process. Also use a fuzzy test that catches both \n and
\r in a single check to speedup the computation.

[lattner]

Interesting optimization! How much speedup does this provide?

[serge-sans-paille]

In D97320#2585515, @lattner wrote:

Interesting optimization! How much speedup does this provide?

When running perf stat -e instructions ./bin/clang -O0 -fsyntax-only sqlite3.c -o/dev/null -w before / after the patch, I get:

1,929,024,335 instructions before
1,905,625,961 instructions after

That's roughly a 1% speedup ;-)

[lattner]

Nice, it would be worth checking to see if something like this (duplicating the ++I) would be faster or if it codegens the same:

while (I < BufLen) {

// Use a fast check to catch both newlines
if (LLVM_UNLIKELY(Buf[I] > std::max('\n', '\r'))) {
  ++I;
  continue;
}
other stuff

}

[serge-sans-paille]

Same generated assembly:

┌─→movzbl 0x0(%r13,%rbp,1),%ecx
│  cmp    $0xd,%cl
│↑ jbe    61
│  add    $0x1,%ebp
├──cmp    %rbp,%rbx
└──ja     110

[lattner]

Nice, thanks!

clang/lib/Basic/SourceManager.cpp

LineOffsetMapping LineOffsetMapping::get(llvm::MemoryBufferRef Buffer,
   // 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;
   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)