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

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