[llvm-dev] [RFC] Propeller: A frame work for Post Link Optimizations

[Eli Friedman via llvm-dev]

From: Xinliang David Li <xinliangli at gmail.com>
Sent: Wednesday, September 25, 2019 5:58 PM
To: Eli Friedman <efriedma at quicinc.com>
Cc: Sriraman Tallam <tmsriram at google.com>; llvm-dev <llvm-dev at lists.llvm.org>
Subject: [EXT] Re: [llvm-dev] [RFC] Propeller: A frame work for Post Link Optimizations



On Wed, Sep 25, 2019 at 5:02 PM Eli Friedman via llvm-dev <llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>> wrote:
My biggest question about this architecture is about when propeller runs basic block reordering within a function.  It seems like a lot of the complexity comes from using the proposed -fbasicblock-sections to generated mangled ELF, and then re-parsing the mangled ELF as a separate step.  I'm not sure that's the right approach, long-term.

Splitting every basic block into its own section introduces overhead, like you described.  And it's likely more complex on non-x86 targets, which have a greater variety of conditional branches.  And the reordering itself involves a bunch of x86 and ELF-specific code.

I'd like to suggest an alternative: instead of perform basic block reordering and function splitting by manipulating the ELF files, you could perform reordering and splitting as part of link-time code generation, as an MIR pass that runs just before the assembly printer.  MIR is almost exactly the form you want for this sort of manipulation: it has basic blocks which correspond closely to the final binary, and a high-level representation of branch instructions.

This was considered for Propeller.  This  is currently being explored in a similar way as an alternative of CSFDO which uses PMU samples.

Makes sense.

And it's before the DWARF/CFI emission, so you don't need to worry about fixing them afterwards.  This should take less code overall, and much less target-specific code. And infrastructure for function splitting would be useful for non-Propeller workflows.

There are some minor downsides to this approach I can think of.  You lose a little flexibility, in that you can't mix blocks from different functions together, but you aren't doing that anyway, from your description?

One of the main design objectives of Propeller is to have the capability to do interprocedural code transformations (reordering, cloning, dedupping etc), so this won't be a minor downside. Function/block alignment (for branch misprediction reduction etc) will also need to be done as a global optimization in the future.

Okay, so my suggestion doesn’t work. I’m still concerned the proposed design is going to push us in a direction we don’t want to go.  Particularly, if you’re going to attempt more complicated transforms, the problems caused by the limited information available in an ELF file will become more prominent.  I mean, yes, you can come up with a more complicated implicit contract between the compiler and Propeller about the exact format of Propeller basic blocks, and add additional symbol annotations, and eventually come up with an “IR” that allows Propeller to perform arbitrary code transforms.  But that’s inevitably going to be more complicated, and harder to understand, than a compiler IR designed for optimizations.

If we are going to stick with ELF-as-compiler-IR, I’d like to see more careful documentation of the contract between the compiler and the Propeller linker, so it’s clear what the compiler is/is not allowed to emit at compile-time, and so other compilers could be made compatible in the future.  The current Propeller implementation is doing some code rewrites that can’t be justified by just standard ELF section reordering.

-Eli
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20190926/0e5f508e/attachment.html>