dependence analyzer for machine code?

why there is no general dependency analysis for the "machin code"?
perhaps it's because the instruction scheduling is only implemented
for sparcv9?

i am going to implement a dependency analysis pass for machine code
block. the result will be returned in a boost graph
(Table of Contents: Boost Graph Library - 1.80.0).

just to check if it has already been implemented. it seems to be a
very common used pass (for instruction scheduling).

Most backends use the SelectionDAG infastructure to do this kind of
thing. (Simplifying things a bit) Each basic block is selected to a DAG
based IR. Then instruction selection is done, which transforms this DAG
to a DAG with machine instructions as nodes. At this point all
dependencies are explicit as edges in the graph. The DAG is then
scheduled to a machine basic block.

Hope this helps. The PowerPC backend is furthest along in being
implemented in this way.

Andrew

I believe Tzu-Chien is referring to array (and pointer) dependence analysis. There is a simple dependence analyzer written by Tanya Lattner in the SparcV9 back-end , which (I believe) is actually Sparc-independent and perhaps could be factored out.

--Vikram Adve

FWIW, starting in this week, two projects of interest are being worked on:

1. A real live scheduler for the target independent code generator is
    being started, by Jim Laskey.
2. I'm going to be working on autogenerating the instruction selector from
    the .td files, which should significantly reduce the amount of C++ code
    you have to write for your target. This will also make it harder to
    "do things wrong".

Once #2 is complete, I intend to write some real documentation on the code generator as well. :slight_smile:

If you're looking at implementing scheduling yourself, and need to find out if two machine instructions have dependencies, you need to be aware of whether the instructions have side effects (these properties are exposed through TargetInstrInfo (e.g. isLoad), and what registers are loaded and stored by the instruction. The registers are a union of the operand register in the machine instructions (isUse operands are reads, isDef operands are written) and the implicit def/use information (see TargetInstrInfo again).

If you're looking for higher level dependence info in the backend (e.g. loop carried dependences), you'll need to do some work, we don't have anything that works out of the box.

-Chris

I believe Tzu-Chien is referring to array (and pointer) dependence analysis. There is a simple dependence analyzer written by Tanya Lattner in the SparcV9 back-end , which (I believe) is actually Sparc-independent and perhaps could be factored out.

It is sparc independent and could be factored out. However, it operates on LLVM instructions (not machine instructions). There is no alias analysis or scalar evolution on machine instructions available (which is what my dependent analysis uses).

However, given a mapping of LLVM to machine instructions.. you can do it (as gross as that is). The stuff Chris is working on now is the better way of doing this.

-Tanya