[LLVMdev] instruction scheduling for stack machines

[Chris Lattner]

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/