x86 Instruction Scheduling

Hi,


I have a project swShader (http://sw-shader.sourceforge.net) which
could benefit a lot from instruction scheduling. Basically it's a
compiler for DirectX 9 pixel shader instructions. Every shader
instruction gets substituted by MMX/SSE instructions, and register
allocation is handled automatically. Because of this substitution,
dependent instructions are close together, causing inefficiencies. The
ps 2.0 specifications do not have jumps or calls, so I often have more
than a hundred instructions that could be scheduled as one block.


My first attempts were not very successful. I tried swapping
instruction orders one pair at a time, and measuring the performance
difference to determine if it was a good move. Unfortunately it's hard
to do accurate timings, and this brute-force method takes minutes to
days to find a near-optimal order. This is unacceptable since I have
to compile multiple shaders at run-time in less than a second.


So what kind of fast heuristics should 'always work'? I'm also looking
for more than one heuristic, or a very configurable one so the optimal
can be manually selected after benchmarking so it's more or less
system independent. Because of the out-of-order execution and many
unknown parameters I think it's hard to solve this perfectly, but what
is considered a good method for MMX/SSE instruction sheduling?


Thanks,


Nicolas Capens

Return to the comp.compilers page.
Search the comp.compilers archives again.