llvm dev - Sep 2005 - [LLVMdev] 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
(http://www.boost.org/libs/graph/doc/table_of_contents.html).

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

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

On Mon, 2005-09-05 at 14:45 +0800, Tzu-Chien Chiu wrote:
> why there is no general dependency analysis for the "machin
code"?
> perhaps it's because the instruction scheduling is only implemented
> for sparcv9?
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

On Sep 5, 2005, at 10:21 AM, Andrew Lenharth wrote:
> On Mon, 2005-09-05 at 14:45 +0800, Tzu-Chien Chiu wrote:
>
>> why there is no general dependency analysis for the "machin
code"?
>> perhaps it's because the instruction scheduling is only implemented
>> for sparcv9?
>>
>
> 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

----------------------------------------------------------------------
  VIKRAM S. ADVE
  Associate Professor, Computer Science       E-MAIL: vadve at cs.uiuc.edu
  Siebel Center for Computer Science           PHONE:    (217) 244-2016
  Univ. of Illinois at Urbana-Champaign          FAX:    (217) 265-6582
  201 N. Goodwin Ave.                     http://www.cs.uiuc.edu/~vadve
  Urbana IL 61801-2302.                        http://llvm.cs.uiuc.edu/
----------------------------------------------------------------------

On Mon, 5 Sep 2005, Andrew Lenharth wrote:
> On Mon, 2005-09-05 at 14:45 +0800, Tzu-Chien Chiu wrote:
>> why there is no general dependency analysis for the "machin
code"?
>> perhaps it's because the instruction scheduling is only implemented
>> for sparcv9?
>
> 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.
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.  :)

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

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