How to traverse llvm DAG for analysis

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 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?


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.

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.


John Criswell

please see comments below

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.

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.