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. > > AndrewI 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/