llvm dev - Mar 2014 - [LLVMdev] Upstreaming PNaCl's IR simplification passes

On Tue, Mar 4, 2014 at 3:11 PM, Sean Silva <chisophugis at gmail.com>
wrote:
> On Tue, Mar 4, 2014 at 4:04 PM, Mark Seaborn <mseaborn at
chromium.org>wrote:
>
>> The PNaCl project has implemented various IR simplification passes that
>> simplify LLVM IR by lowering complex features to simpler features. 
We'd
>> like to upstream some of these IR passes to LLVM.  We'd like to
explore if
>> this acceptable, and if so, how we should go about doing this.
>>
>> The immediate reason is that Emscripten is reusing PNaCl's IR
passes for
>> its new "fastcomp" backend [1].  It would be really useful if
PNaCl and
>> Emscripten could collaborate via upstream LLVM rather than a branch.
>>
>> Some background:  There are two related use cases for these IR
>> simplification passes:
>>
>>  1) Simplifying the task of writing a new LLVM backend.  This is
>> Emscripten's use case.  The IR simplification passes reduce the
number of
>> cases a backend has to handle, so they would be useful for anyone else
>> creating a new backend.
>>
>
> FWIW, this sounds to me like a sufficiently compelling use case to support
> getting this in-tree.
>
Just in case it gets lost in my longer reply, I want to emphasize that if
these will be used to simplify the in-tree backends and those backend
maintainers are on board, then I am *totally* in favor of this going into
the tree. My concerns are heavily based on the fact that as proposed, none
of that seems likely to happen.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20140304/8bf9ab5a/attachment.html>

On 3/4/2014 5:18 PM, Chandler Carruth wrote:
>
> On Tue, Mar 4, 2014 at 3:11 PM, Sean Silva <chisophugis at gmail.com 
> <mailto:chisophugis at gmail.com>> wrote:
>
>     On Tue, Mar 4, 2014 at 4:04 PM, Mark Seaborn
>     <mseaborn at chromium.org <mailto:mseaborn at
chromium.org>> wrote:
>
>         The PNaCl project has implemented various IR simplification
>         passes that simplify LLVM IR by lowering complex features to
>         simpler features.  We'd like to upstream some of these IR
>         passes to LLVM.  We'd like to explore if this acceptable, and
>         if so, how we should go about doing this.
>
>         The immediate reason is that Emscripten is reusing PNaCl's IR
>         passes for its new "fastcomp" backend [1].  It would be
really
>         useful if PNaCl and Emscripten could collaborate via upstream
>         LLVM rather than a branch.
>
>         Some background:  There are two related use cases for these IR
>         simplification passes:
>
>          1) Simplifying the task of writing a new LLVM backend.  This
>         is Emscripten's use case.  The IR simplification passes reduce
>         the number of cases a backend has to handle, so they would be
>         useful for anyone else creating a new backend.
>
>
>     FWIW, this sounds to me like a sufficiently compelling use case to
>     support getting this in-tree.
>
>
> Just in case it gets lost in my longer reply, I want to emphasize that 
> if these will be used to simplify the in-tree backends and those 
> backend maintainers are on board, then I am *totally* in favor of this 
> going into the tree. My concerns are heavily based on the fact that as 
> proposed, none of that seems likely to happen.
Framing the problem differently, what I see is this:
PNaCl (and, by implication elsewhere in the thread, Emscripten and a 
hypothetical new C backend or MSIL backend) are basically backends that 
don't go through the SelectionDAG mechanism and largely bypass the 
current backend logic that legalizes IR for a backend. The problem is 
that basically all the targets in the LLVM tree use SelectionDAG and 
associated mechanisms. Arguably the NVPTX backend might benefit from 
such an approach (since it ultimately needs to allocate virtual 
registers), but I've never developed any backends, so I don't know what 
the tradeoffs are there. In any case, it's extremely unlikely that code 
which is only useful for IR-based backends instead of SelectionDAG-based 
backends could be useful for any in-tree targets.

In that frame of model, though, I do see a potential compromise: instead 
of proposing virtual clones of what is essentially IR legalization for 
an IR-based backend, why not attempt to generalize the current 
legalization logic to work for IR-based backends instead of only 
SelectionDAG-based backends?

-- 
Joshua Cranmer
Thunderbird and DXR developer
Source code archæologist

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20140305/6f7fe214/attachment.html>

>
> Just in case it gets lost in my longer reply, I want to emphasize that if
> these will be used to simplify the in-tree backends and those backend
> maintainers are on board, then I am *totally* in favor of this going into
> the tree. My concerns are heavily based on the fact that as proposed, none
> of that seems likely to happen.
>
>
> Framing the problem differently, what I see is this:
> PNaCl (and, by implication elsewhere in the thread, Emscripten and a
> hypothetical new C backend or MSIL backend) are basically backends that
> don't go through the SelectionDAG mechanism and largely bypass the
current
> backend logic that legalizes IR for a backend. The problem is that
basically
> all the targets in the LLVM tree use SelectionDAG and associated
mechanisms.
> Arguably the NVPTX backend might benefit from such an approach (since it
> ultimately needs to allocate virtual registers), but I've never
developed
> any backends, so I don't know what the tradeoffs are there. In any
case,
> it's extremely unlikely that code which is only useful for IR-based
backends
> instead of SelectionDAG-based backends could be useful for any in-tree
> targets.
>
> In that frame of model, though, I do see a potential compromise: instead of
> proposing virtual clones of what is essentially IR legalization for an
> IR-based backend, why not attempt to generalize the current legalization
> logic to work for IR-based backends instead of only SelectionDAG-based
> backends?
>
I agree that is should be a lot easier to create a backend.
See the below comment describing a virtual machine architecture.
A complete CPU definition in 54 lines of text!!!
For those interested, the 54 lines is taken from GCHQ.
I think it would be useful to maybe use the below as an example
backend template.

I would also welcome more IR passes in the LLVM tree, even if the
current backends don't use them.
I can probably re-use them in my project.
So long as there were tests for them, and an interested party could
claim "MAINTAINER" for each one.
A similar model to that of the Linux kernel MAINTAINER.
Anyone can submit a device driver to the linux kernel and it will go
into upstream mainline, so long as a "MAINTAINER" is identified.
If the MAINTAINER becomes absent for a period of time, and no one else
claims it, the driver is then removed again.
A single LLVM IR pass is a relatively unobtrusive piece of the LLVM code base.
How would adding a new LLVM IR pass into the upstream LLVM code base
cause problems for the core MAINTAINERS?

Kind Regards

James



 exec: function()
  {
    // virtual machine architecture
    // ++++++++++++++++++++++++++++
    //
    // segmented memory model with 16-byte segment size (notation seg:offset)
    //
    // 4 general-purpose registers (r0-r3)
    // 2 segment registers (cs, ds equiv. to r4, r5)
    // 1 flags register (fl)
    //
    // instruction encoding
    // ++++++++++++++++++++
    //
    //           byte 1               byte 2 (optional)
    // bits      [ 7 6 5 4 3 2 1 0 ]  [ 7 6 5 4 3 2 1 0 ]
    // opcode      - - -
    // mod               -
    // operand1            - - - -
    // operand2                         - - - - - - - -
    //
    // operand1 is always a register index
    // operand2 is optional, depending upon the instruction set specified below
    // the value of mod alters the meaning of any operand2
    //   0: operand2 = reg ix
    //   1: operand2 = fixed immediate value or target segment
(depending on instruction)
    //
    // instruction set
    // +++++++++++++++
    //
    // Notes:
    //   * r1, r2 => operand 1 is register 1, operand 2 is register 2
    //   * movr r1, r2 => move contents of register r2 into register r1
    //
    // opcode | instruction | operands (mod 0) | operands (mod 1)
    // -------+-------------+------------------+-----------------
    // 0x00   | jmp         | r1               | r2:r1
    // 0x01   | movr        | r1, r2           | rx,   imm
    // 0x02   | movm        | r1, [ds:r2]      | [ds:r1], r2
    // 0x03   | add         | r1, r2           | r1,   imm
    // 0x04   | xor         | r1, r2           | r1,   imm
    // 0x05   | cmp         | r1, r2           | r1,   imm
    // 0x06   | jmpe        | r1               | r2:r1
    // 0x07   | hlt         | N/A              | N/A
    //
    // flags
    // +++++
    //
    // cmp r1, r2 instruction results in:
    //   r1 == r2 => fl = 0
    //   r1 < r2  => fl = 0xff
    //   r1 > r2  => fl = 1
    //
    // jmpe r1
    //   => if (fl == 0) jmp r1
    //      else nop

    throw "VM.exec not yet implemented";
  }