llvm dev - Jun 2017 - Backend implementation for an architecture with only majority operation instruction

Hello everyone,

I was trying to create an LLVM backend for a processor with a very simple
architecture and that does all instructions like load, store, arithmetic and
logical instructions using a bunch of majority functions. The processor has only
one instruction(majority function) in its ISA and breaks down all other
instructions into a number of majority instructions depending on what
instruction it is. All the instructions have different combinations of majority
operations. Is there any way to implement this without creating a new Selection
DAG node for the majority operation?
I was thinking of creation of a new Selection DAG node and mapping all the other
instructions like loads, stores as pseudo instructions and breaking them up. Can
someone please help me with this?

Thanks!
Sreejita


Sent from Mail for Windows 10

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170601/2fd71477/attachment-0001.html>

I'm having a hard time grasping what this ISA actually looks like.

When you say that it has a single instruction that is a majority function,
I assume something like this:

MAJ rDst <- rSrc0, rSrc1, rSrc2
Semantics:
for (int i = 0; i < REGISTER_WIDTH; i++) {
  rDst[i] = maj(rSrc0[i], rSrc1[i], rSrc2[i]);
}
Where maj(a, b, c) = (a & b) | (a & c) | (b & c)

But that doesn't make sense given your question.

MAJ is a bitwise operation, so how do you implement arithmetic instructions
with it? You would need at least one other instruction (such as a bit
shift) to establish dependency chains between bits.

Also, how do you decompose load/store into majority functions? It's not
even clear to me what that would actually mean. You need to access the
memory/IO bus somehow, and if your only instruction only reads/writes to
registers, the only way to do that would be to have special registers that
interface to the IO bus?

-- Sean Silva

On Thu, Jun 1, 2017 at 8:13 PM, Sreejita saha via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> Hello everyone,
>
>
>
> I was trying to create an LLVM backend for a processor with a very simple
> architecture and that does all instructions like load, store, arithmetic
> and logical instructions using a bunch of majority functions. The processor
> has only one instruction(majority function) in its ISA and breaks down all
> other instructions into a number of majority instructions depending on what
> instruction it is. All the instructions have different combinations of
> majority operations. Is there any way to implement this without creating a
> new Selection DAG node for the majority operation?
>
> I was thinking of creation of a new Selection DAG node and mapping all the
> other instructions like loads, stores as pseudo instructions and breaking
> them up. Can someone please help me with this?
>
>
>
> Thanks!
>
> Sreejita
>
>
>
>
>
> Sent from Mail <https://go.microsoft.com/fwlink/?LinkId=550986> for
> Windows 10
>
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170604/791e625e/attachment.html>

Hey Sean,
So the processor does in-memory computing, it reads instructions and
operands from the memory array, performs the majority operations within the
memory array itself.
It does instructions using resistive majority which is AB'+B'C+AC
Like it does AND operation as
1: 0, 1, @C; //C=0
2: 0, 1, @Binv; //Binv=0
3: 1, @B, @Binv; //Binv=B
4: @A, @Binv, @C; //C=A.B
 where each operation is a resistive majority and operations are directly
performed on the storage of C.  It reads @A in a register , @B , reads A
and B and directly writes into the memory @C. There are shift operators as
well that are also performed in a similar way, loads, stores are also
performed like this. So I am trying to define this resistive majority
instruction in my ISA.

Thanks!
-Sreejita


On Sun, Jun 4, 2017 at 8:22 PM, Sean Silva <chisophugis at gmail.com>
wrote:
> I'm having a hard time grasping what this ISA actually looks like.
>
> When you say that it has a single instruction that is a majority function,
> I assume something like this:
>
> MAJ rDst <- rSrc0, rSrc1, rSrc2
> Semantics:
> for (int i = 0; i < REGISTER_WIDTH; i++) {
>   rDst[i] = maj(rSrc0[i], rSrc1[i], rSrc2[i]);
> }
> Where maj(a, b, c) = (a & b) | (a & c) | (b & c)
>
> But that doesn't make sense given your question.
>
> MAJ is a bitwise operation, so how do you implement arithmetic
> instructions with it? You would need at least one other instruction (such
> as a bit shift) to establish dependency chains between bits.
>
> Also, how do you decompose load/store into majority functions? It's not
> even clear to me what that would actually mean. You need to access the
> memory/IO bus somehow, and if your only instruction only reads/writes to
> registers, the only way to do that would be to have special registers that
> interface to the IO bus?
>
> -- Sean Silva
>
> On Thu, Jun 1, 2017 at 8:13 PM, Sreejita saha via llvm-dev <
> llvm-dev at lists.llvm.org> wrote:
>
>> Hello everyone,
>>
>>
>>
>> I was trying to create an LLVM backend for a processor with a very
simple
>> architecture and that does all instructions like load, store,
arithmetic
>> and logical instructions using a bunch of majority functions. The
processor
>> has only one instruction(majority function) in its ISA and breaks down
all
>> other instructions into a number of majority instructions depending on
what
>> instruction it is. All the instructions have different combinations of
>> majority operations. Is there any way to implement this without
creating a
>> new Selection DAG node for the majority operation?
>>
>> I was thinking of creation of a new Selection DAG node and mapping all
>> the other instructions like loads, stores as pseudo instructions and
>> breaking them up. Can someone please help me with this?
>>
>>
>>
>> Thanks!
>>
>> Sreejita
>>
>>
>>
>>
>>
>> Sent from Mail <https://go.microsoft.com/fwlink/?LinkId=550986>
for
>> Windows 10
>>
>>
>>
>> _______________________________________________
>> LLVM Developers mailing list
>> llvm-dev at lists.llvm.org
>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170605/5433f9c9/attachment.html>

> On Jun 1, 2017, at 8:13 PM, Sreejita saha via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
> 
> Hello everyone,
>  
> I was trying to create an LLVM backend for a processor with a very simple
architecture and that does all instructions like load, store, arithmetic and
logical instructions using a bunch of majority functions. The processor has only
one instruction(majority function) in its ISA and breaks down all other
instructions into a number of majority instructions depending on what
instruction it is. All the instructions have different combinations of majority
operations. Is there any way to implement this without creating a new Selection
DAG node for the majority operation?
> I was thinking of creation of a new Selection DAG node and mapping all the
other instructions like loads, stores as pseudo instructions and breaking them
up. Can someone please help me with this?
If your architecture is alien enough (and so far this sounds pretty alien to me)
it may make sense to just create a custom backend that goes from the IR
representation to whatever machine format/assembly you are using.
While CodeGen gives you a lot of infrastructure that fits "normal"
CPUs well (ABI lowering, instruction selection, register allocation, scheduling,
object file formats, debug info). On the other hand if your target is a
hypothetical CPU (just making guesses from what little you wrote) you may not
need all that:
- Register allocation usually only makes sense if you have a bounded number of
registers or special constraints.
- Scheduling usually only makes sense if you have a machine model with different
latencies or want to optimize register pressure to minimize spill reloads (for
bounded number of regs).
- If your object file format isn't ELF/macho/coff then you won't gain
much from the MC infrastructure and debug generation infrastructure.

If you don't need most of these things then you are probably better off
manually implementing a TargetMachine without using CodeGen (instead of
implementing an LLVMTargetMachine with all the CodeGen utilities).

- Matthias
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170605/f5cbcc53/attachment.html>

Hey Can you refer me to some documentation on manually creating a backend
without codegen?

On Mon, Jun 5, 2017 at 3:08 PM, Matthias Braun <mbraun at apple.com>
wrote:
>
> On Jun 1, 2017, at 8:13 PM, Sreejita saha via llvm-dev <
> llvm-dev at lists.llvm.org> wrote:
>
> Hello everyone,
>
> I was trying to create an LLVM backend for a processor with a very simple
> architecture and that does all instructions like load, store, arithmetic
> and logical instructions using a bunch of majority functions. The processor
> has only one instruction(majority function) in its ISA and breaks down all
> other instructions into a number of majority instructions depending on what
> instruction it is. All the instructions have different combinations of
> majority operations. Is there any way to implement this without creating a
> new Selection DAG node for the majority operation?
> I was thinking of creation of a new Selection DAG node and mapping all the
> other instructions like loads, stores as pseudo instructions and breaking
> them up. Can someone please help me with this?
>
>
> If your architecture is alien enough (and so far this sounds pretty alien
> to me) it may make sense to just create a custom backend that goes from the
> IR representation to whatever machine format/assembly you are using.
> While CodeGen gives you a lot of infrastructure that fits
"normal" CPUs
> well (ABI lowering, instruction selection, register allocation, scheduling,
> object file formats, debug info). On the other hand if your target is a
> hypothetical CPU (just making guesses from what little you wrote) you may
> not need all that:
> - Register allocation usually only makes sense if you have a bounded
> number of registers or special constraints.
> - Scheduling usually only makes sense if you have a machine model with
> different latencies or want to optimize register pressure to minimize spill
> reloads (for bounded number of regs).
> - If your object file format isn't ELF/macho/coff then you won't
gain much
> from the MC infrastructure and debug generation infrastructure.
>
> If you don't need most of these things then you are probably better off
> manually implementing a TargetMachine without using CodeGen (instead of
> implementing an LLVMTargetMachine with all the CodeGen utilities).
>
> - Matthias
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170605/3a2b4990/attachment.html>

I guess this is relevant here:
https://en.wikipedia.org/wiki/One_instruction_set_computer
> On Jun 4, 2017, at 7:22 PM, Sean Silva via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
> 
> I'm having a hard time grasping what this ISA actually looks like.
> 
> When you say that it has a single instruction that is a majority function,
I assume something like this:
> 
> MAJ rDst <- rSrc0, rSrc1, rSrc2
> Semantics:
> for (int i = 0; i < REGISTER_WIDTH; i++) {
>   rDst[i] = maj(rSrc0[i], rSrc1[i], rSrc2[i]);
> }
> Where maj(a, b, c) = (a & b) | (a & c) | (b & c)
> 
> But that doesn't make sense given your question.
> 
> MAJ is a bitwise operation, so how do you implement arithmetic instructions
with it? You would need at least one other instruction (such as a bit shift) to
establish dependency chains between bits.
> 
> Also, how do you decompose load/store into majority functions? It's not
even clear to me what that would actually mean. You need to access the memory/IO
bus somehow, and if your only instruction only reads/writes to registers, the
only way to do that would be to have special registers that interface to the IO
bus?
> 
> -- Sean Silva
> 
> On Thu, Jun 1, 2017 at 8:13 PM, Sreejita saha via llvm-dev <llvm-dev at
lists.llvm.org <mailto:llvm-dev at lists.llvm.org>> wrote:
> Hello everyone,
> 
>  
> 
> I was trying to create an LLVM backend for a processor with a very simple
architecture and that does all instructions like load, store, arithmetic and
logical instructions using a bunch of majority functions. The processor has only
one instruction(majority function) in its ISA and breaks down all other
instructions into a number of majority instructions depending on what
instruction it is. All the instructions have different combinations of majority
operations. Is there any way to implement this without creating a new Selection
DAG node for the majority operation?
> 
> I was thinking of creation of a new Selection DAG node and mapping all the
other instructions like loads, stores as pseudo instructions and breaking them
up. Can someone please help me with this?
> 
>  
> 
> Thanks!
> 
> Sreejita
> 
>  
> 
>  
> 
> Sent from Mail <https://go.microsoft.com/fwlink/?LinkId=550986> for
Windows 10
> 
>  
> 
> 
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
<http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev>
> 
> 
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170605/9b9df769/attachment.html>