llvm dev - Sep 2005 - [LLVMdev] Re: dependence analyzer for machine code?

I was searching for the code could be factored out for a dependency
analyzer. The one written by Tanya for SparcV9.

The machine code dependency is necessary for some architecture which
the (efficient) instruction scheduling could not be possible without
the register allocation is done first. For example, the VLIW machines
(most DSP's are). For an efficient instruction scheduling, the
dependency information must be reconstructed after the register
allocation, something like the DAG generated during the code selection
phase (a graph-like data structure, with directed edges expliclitly
representing the depedencies), and instructions without data
dependency and structure hazard could be scheduled in a long
instruction word which contains several instructions.

The structure hazard, could be:
* a limited number of functional units - limited the combination
machine instructions (opcodes) be could be scheduled together
* a limited number of register read-ports - If the source registers
used by a group of instructions could be read out in parallel, these
instructions could be schedule together. In many DSP's , the
read-ports of the register file is usually limited. For example, some
registers are actually stored in the same memory bank, and they could
be read simultaneously.

The structure hazard is probably the reason why an efficient
instruction scheduling could not be possible done in the code
selection phase (SelectionDAG).

The information exposed by the TargetInstrInfo should be able to
engineered a target-indepent machine code dependency analyzer, right?
(actually this is what I am doing).

-- 
Tzu-Chien Chiu,
3D Graphics Hardware Architect
<URL:http://www.csie.nctu.edu.tw/~jwchiu>

On Tue, 6 Sep 2005, Tzu-Chien Chiu wrote:
> I was searching for the code could be factored out for a dependency
> analyzer. The one written by Tanya for SparcV9.
>
> The machine code dependency is necessary for some architecture which
> the (efficient) instruction scheduling could not be possible without
> the register allocation is done first. For example, the VLIW machines
> (most DSP's are). For an efficient instruction scheduling, the
> dependency information must be reconstructed after the register
> allocation, something like the DAG generated during the code selection
> phase (a graph-like data structure, with directed edges expliclitly
> representing the depedencies), and instructions without data
> dependency and structure hazard could be scheduled in a long
> instruction word which contains several instructions.
Ok, makes sense.
> The structure hazard is probably the reason why an efficient
> instruction scheduling could not be possible done in the code
> selection phase (SelectionDAG).
Yup, if you depend on the allocation of registers, doing this before 
register allocation won't make sense.
> The information exposed by the TargetInstrInfo should be able to
> engineered a target-indepent machine code dependency analyzer, right?
> (actually this is what I am doing).
Yup.  You'll have to build scheduling graphs that represent the 
dependencies between instructions (which the target instr info and 
register use/def properties can tell you) and use those to do a post-pass 
scheduler.

-Chris

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