LLVM merges machine function splitter for reduction in TLB misses

There's actually a compiler that does all these things and allows debugging of optimised code whilst seeing the unoptimised form - Sulong.

Sulong is an LLVM JIT-compiling engine that runs on GraalVM. So it uses the same infrastructure of the JVM, but without JVM bytecode getting into the picture. Instead the JVM runs LLVM bitcode directly. But it does so in the standard way which gives many benefits:

• Splitting of hot/cold paths, as in this work.

• Cross-function optimisation and inlining regardless of visibility, as requested above.

• Ability to debug an optimised program, because the JVM can 'deoptimize' the parts being inspected or debugged.

• Run the Linux version of the bitcode cross-platform.

• In "Managed Sulong" (which is an enhanced payware version), all allocations are garbage collected and bounds checked. Yes even for C/C++ programs, just needing a recompile. It's just about possible to do this within the rules of well defined C/C++, as long as the program doesn't try to do non-portable or non-defined things like pass stack pointers between threads. Managed Sulong can also sandbox LLVM code modules, and redirect IO back into the JVM for mapping via the pluggable socket/filesystem layers.

• Cross-language interop, including recent experimental support for e.g. casting Java or Ruby or Python objects to C++ objects and calling methods on them.

• All the same compiler optimisations as LLVM does still apply.

It's a pretty amazing and under-appreciated project. On the other hand the code being run inherits the limits of the JVM, e.g. you shouldn't try and fork the process (of course, lots of runtimes don't like being forked and on Windows you can't do it at all).

The issue is basically that tail-recursive functions need to have this information recorded in their signature (for external interfaces), but this is not recorded in C and thus you can't provide this guarantee at the interface boundaries.

I'd recommend "Lambda, the ultimate GOTO" https://dspace.mit.edu/handle/1721.1/5753

What part of the detection is giving you trouble? Detecting whether a call is recursive, or whether it is a tail call that can be optimized? The first part is relatively easy, you typically have some sort of data structure representing calls and their targets, and you know what function you're currently compiling. If the function you're compiling is the same as a call's target, you have recursion.

LLVM's code is at https://llvm.org/doxygen/TailRecursionElimination_8cpp_sourc...

The core of this detection is in findTRECandidate. It iterates backwards over a basic block, looking for call instructions whose call target is the current function F:

    CallInst *CI = nullptr;
    BasicBlock::iterator BBI(TI);
    while (true) {
      CI = dyn_cast<CallInst>(BBI);
      if (CI && CI->getCalledFunction() == &F)
        break;
  
      if (BBI == BB->begin())
        return nullptr;          // Didn't find a potential tail call.
      --BBI;
    }

The harder part is detecting whether calls are in fact tail calls that you can replace by jumps. There are all sorts of special cases, like whether alloca() might be called by the function.

As I said, tail-recursion is just a particular use of tail calls. Tail calls are very simple: anything of the form 'return foo(...)'; or, in languages without 'return', a function call which is the at the end of the definition (i.e. the last step).

All we require is that the current function is calling some other function, and passing on its return value unchanged. For example, let's take a simple function:

    int foo(int x) {
      return bar(x);
    }

'return bar(x);' is a tail-call, since 'foo' isn't doing anything with the result; calling 'foo' is equivalent to calling 'bar'. In this case the compiler could actually replace every occurrence of 'foo' with 'bar' (e.g. inlining it), but we can't do that in general. However, when we call 'bar' we certainly don't need to keep any of 'foo's machinery around (stack frames, local variables, register contents, etc.); we can just start executing the code for 'bar' (i.e. a jump instruction).

More realistically, 'foo' and 'bar' might not be equivalent, e.g.

    int foo(int x) {
      int y = baz(x);
      return bar(x + 3 * y);
    }

Here we can't just replace calls to 'foo' with calls to 'bar', since they do different things. However, notice the order that things will run in: (1) 'baz(x)' will be called, (2) 'x + 3 * y' will be calculated, (3) 'bar' will be called. Even though these 'foo' and 'bar' functions are very different to begin with, once we reach step three (the call to 'bar') the remaining instructions are the same (since 'foo' is calling 'bar' and returning its result unchanged; i.e. the definition of a tail-call!). Hence we can still discard 'foo's machinery and just jump to 'bar' (e.g. we can throw away 'y'; and the compiler can ensure the result of (2) is put where 'bar' expects its argument).

If 'foo' and 'bar' are the same function then we happen to have tail recursion. For example:

    uint fac(uint n) {
      if (n) return fac(n-1);
      return 1;
    }

Here 'return fac(n-1)' is a tail-call; it also happens to be tail-recursion, since it's calling the 'fac' function from within the 'fac' function. We don't need to keep the stack frame for 'fac(n)' around, we can just overwrite it with the stack frame of 'fac(n-1)', and so on.

We can also have mutually tail-recursive functions, e.g.

    uint even(uint n) {
      if (n) odd(n-1);
      return 1;
    }

    uint odd(uint n) {
      if (n) even(n-1);
      return 0;
    }

This is harder to spot than direct tail-recursion, but it doesn't matter since tail-recursion isn't particularly special. As long as we implement tail-calls efficiently, then the benefits apply to tail-recursive functions (like 'fac') and mutually tail-recursive functions (like 'even' and 'odd'), as well as many other places which just-so-happen to use tail-calls.

Intuitively, any time we find ourselves using a "main loop", or "driver loop", etc. which just calls out to a sequence of functions, possibly passing the return values of one into arguments of the next, that's equivalent to having each of those functions make a tail-call to the next one (i.e. such loops are "trampolines").

> that is not possible when an object is allocated in that frame and its address passed to the target function

Ah of course, I hadn't thought about live aliases to stack-allocated data.

You're right about destructors; I agree that they're not really tail-calls (since we're processing results).

> C/C++ compilers can and do eliminate tail calls where possible, but there's no guarantee like you get from a compiler for a functional language.

Yes, I tend to say "tail-call optimisation" when it's opportunistic (e.g. GCC/Clang), and "tail-call elimination" when it's guaranteed (e.g. Scheme/ML).

The "old" groups UI (URLs like https://groups.google.com/forum/#!topic/llvm-dev) doesn't require a login right now. It briefly did, and the Golang team complained and got the change rolled back (probably temporarily). The "new" UI (URLs like https://groups.google.com/g/llvm-dev/) has always needed to be logged into google afaik.

This link + Safari Reader Mode is good

Can I create profile data by running the instrumented binaries through testcases? Perhaps integration test cases which represent typical end to end functionality of my application.

Yes --- the collection of cold basic blocks gets named "<origfunc>.cold". But it's nevertheless not really an independent function from a code POV.

They are the same thing. The GP makes a distinction which does not exist. Witness the fact that two different compilers refer to the exact same feedback technique as either AutoFDO or SamplePGO.

> especially on a 64-bit architecture

Pointer size has little impact on code size. amd64 code can even be smaller than x86 in some cases.

I think you could easily get past a megabyte with auto-generated parser code. That would be stuff like lex, yacc, bison, antlr, flex, etc.

Anything with a big switch would qualify too, such as an emulator.

That google paper has a nice observation on glibc’s memcmp:

“memcmp clearly stands out of the correlation between call frequency and function size in Figure 8. It is both extremely frequent, and, at almost 6 KiB of code, 10× larger than memcpy which is conceptually of similar complexity. Examining its layout and execution patterns (Figure 13) suggests that it does suffer from the high amount of fragmentation we observed fleetwide in the previous section. While covering 90% of executed instructions in memcmp only requires two cache lines, getting up to 99% coverage requires 41 lines, or 2.6 KiB of cache capacity. Not only is more than 50% of code cold, but it is also interspersed between the relatively hot regions, and likely unnecessarily brought in by prefetchers. Such bloat is costly – performance counter data collected by GWP indicates that 8.2% of all i-cache misses among the 100 hottest functions are from memcmp alone.

A closer look at the actual code from glibc can explain the execution patterns in Figure 13. It is hand-written in assembly and precompiled, with extensive manual loop unrolling, many conditional cases for the various alignments of the two source arrays, and large jump tables.

In our experience, code usually evolves into similar state from over-reliance on micro-optimization and micro-benchmarking. While writing in assembly can in rare cases be a necessary evil, it prevents the compiler from doing even the most basic feedback-directed code layout optimizations.

[…]

We tested this hypothesis by macro-benchmarking a version of memcmp that is specifically optimized for code size (only 2 i-cache lines) and locality. In short, it only special-cases very small string sizes (to aid the compiler in inlining very fast cases) and falls back to rep cmps for larger compares. Even though it achieves slightly lower throughput numbers than the glibc version in micro-benchmarks, this simple proof-of-concept showed an overall 0.5%-1% end-to-end performance improvement on large-footprint workloads like web search.”

I would guess the assembly version can be improved by moving those cold blocks out of the cache lines of the hot code.

All dyn_cast does is move runtime polymorphism to compile time polymorphism.

OWL and MFC come to mind.

There are a ton of great books out there! If you're looking for a bit of the whole shebang, check out Compilers: Principles, Techniques, and Tools (aka, The Dragon Book). It's an older book, but a lot of what is described in there is still very relevant and good info. If you want a more high level overview at first, I'd recommend Crafting Interpreters [0] and Writing a Compiler/Interpreter in Go [1]. The latter two focus more on lexing, parsing, and intermediate code generation.

[0] https://craftinginterpreters.com/ [1] https://compilerbook.com/

Yes, I'm referring to this particular version.

The technique itself isn't new in clang either. This is about a new implementation of it, where the difference to the existing implementation is that this happens later in the process (it's deferred to the machine-specific code generation phase, whereas the existing implementation happens in the middle-end and is target-agnostic).

this was a common practice at Microsoft in the mid 90s, maybe 95-97ish. the set of apps involved were called BBT: "Basic Block Tools". Windows, SQL Server, among others, were post processed with profiling data. it also deduped basic blocks, reducing binary bloat from inlining even without profiling data. just needed some additional info in the debug symbols to work.

Yes. And it was implemented relatively widely e.g. https://docs.oracle.com/cd/E19205-01/820-4379/index.html which IIRC was published before 2010.