llvm dev - Aug 2006 - [LLVMdev] instruction scheduling for stack machines

Hi!

I'm working on an LLVM back-end for a processor with a stack machine
architecture. After experimenting with code generation directly from the LLVM
representation, I'm studying the target-independant code generator.

As far as I understand, there currently exists a target-independant
infrastructure for legalization, instruction selection, scheduling and register
allocation. It is clear that a stack machine, having no architecturally visible
registers, can't use the register allocator, so I'll have to implement
target-specific code instead. As for instruction scheduling, register and stack
machines appear to have opposite "preferences". On a register machine,
the aim is to avoid data hazards and so it is best to schedule independant
instructions to adjacent positions. On a stack machine, there is no
operand selection and result writeback overhead, so the aim is to avoid stack
manipulation; it is thus best to schedule dependant instructions to adjacent
positions. The analogue of the simplest scheduling algorithm listed in
SelectionDAGISel.cpp - breadth first sequencing - for a stack machine
would probably be depth first sequencing.

Is there a way to configure an existing instruction scheduler to use a policy
suitable for a stack machine, or is it best to write target-specific code
instead?

TIA,
Yossi

On Fri, 11 Aug 2006, Yossi Kreinin wrote:
> I'm working on an LLVM back-end for a processor with a stack machine 
> architecture. After experimenting with code generation directly from the
LLVM
> representation, I'm studying the target-independant code generator.
ok
> As far as I understand, there currently exists a target-independant 
> infrastructure for legalization, instruction selection, scheduling and 
> register allocation. It is clear that a stack machine, having no 
> architecturally visible registers, can't use the register allocator, so
I'll
> have to implement target-specific code instead.
Sounds good.
> As for instruction scheduling, register and stack machines appear to 
> have opposite "preferences". On a register machine, the aim is to
avoid
> data hazards and so it is best to schedule independant instructions to 
> adjacent positions. On a stack machine, there is no operand selection 
> and result writeback overhead, so the aim is to avoid stack 
> manipulation; it is thus best to schedule dependant instructions to 
> adjacent positions. The analogue of the simplest scheduling algorithm 
> listed in SelectionDAGISel.cpp - breadth first sequencing - for a stack 
> machine would probably be depth first sequencing.
>
> Is there a way to configure an existing instruction scheduler to use a
policy
> suitable for a stack machine, or is it best to write target-specific code 
> instead?
Your best bet are to use the "register pressure reducing" schedulers,
like
-list-tdrr.  These attempt to schedule uses as close to definitions as 
possible.

-Chris

-- 
http://nondot.org/sabre/
http://llvm.org/