[LLVMdev] LLVM IR in DAG form

[David Chisnall]

> On 21 Feb 2015, at 05:59, Jeehoon Kang <jeehoon.kang at sf.snu.ac.kr> wrote:
> 
> this is Jeehoon Kang, a CS PhD student and a newbie to LLVM.
> 
> I am wondering why LLVM IR's basic block consists of a list of instructions,
> rather than a DAG of instruction as in the low level (ISelectionDAG).

SSA form is implicitly a DAG, defined by the uses relation (registers in LLVM can be thought of as edges between instructions).  It is not *solely* a DAG, however.  For example, in some places the order of two loads matters - particularly when they are atomic operations - it's only side-effect-free operations that can be represented entirely as a DAG.  In general, optimisations that work best with a DAG representation deal with use-def chains and are not explicitly aware of the sequence of instructions in the basic blocks unless they need to be.  

David