[llvm-dev] How to traverse llvm DAG for analysis

[Xing Su via llvm-dev]

please see comments below


On Jun 27, 2016, at 23:36, John Criswell via llvm-dev <llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>> wrote:

Dear Raul,

Instruction selection and instruction scheduling is, to the best of my knowledge, done at the MachineInstr (MI) IR level.  The documentation you've read is on the target independent LLVM IR.

Instruction selection is done on SelectionDAG, which is build from LLVM IR. After instruction selection, target-independent IR is turned into
machine instructions (MI). At this time, MI is still in SSA form. Then LLVM backend do PHI elimination, then machine instruction scheduling.
LLVM uses a list scheduler to perform both pre-RA and post-RA scheduling.


You will probably need to read the documentation on LLVM's code generator.  The documents on Writing an LLVM Backend, the LLVM Target Independent Code Generator, and Machine IR Format Reference Manual is probably what you need to read if you want to work with the SelectionDAG and the machine code that is generated by LLVM during code generation.

If you just want to analyze LLVM IR, then all the virtual register values are in SSA form and therefore have explicit def-use chains over which you can iterate (see the LLVM Programmer's Guide).  If you want a DAG for memory dependencies, then you should send a follow-up email to the list as that is its own whole topic.

Regards,

John Criswell

On 6/27/16 10:03 AM, Raul Garcia via llvm-dev wrote:
Hello All,

I would like your help to learn how to traverse an LLVM DAG and perform some analysis. I know that llc can be used to view a DAG, but I would like to manipulate them. In particular I'm interested in the instruction selection and the scheduling DAGs.


I’m not familiar with instruction selection. Schedule DAG  is build from machine instructions. see class ScheduleDAG and its subclasses ScheduleDAGInstrs, ScheduleDAGMI, ScheduleDAGMIList. The building of schedule DAG is done in ScheduleDAGInstrs::buildSchedGraph.

see class MachineScheduler defines the list scheduler. MachineScheduler use an instance of ScheduleDAGInstrs to schedule machine instructions.


I have read the documentation about writing an analysis pass and I know how to traverse a basic block on a LLVM IR assembly file, but I don't know how to do the same for a scheduled DAG.

Could you tell me:

-How are the DAGs generated? Where is the source code that implement this functionality?
-Is there an example to traverse a DAG with selected/scheduled instructions?


Regards,
Raul.



_______________________________________________
LLVM Developers mailing list
llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev




--
John Criswell
Assistant Professor
Department of Computer Science, University of Rochester
http://www.cs.rochester.edu/u/criswell

_______________________________________________
LLVM Developers mailing list
llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160627/4566448e/attachment-0001.html>