llvm dev - Feb 2015 - [LLVMdev] LLVM IR in DAG form

Hi all,
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).

My gut feeling tells me that LLVM IR in DAG form may admit more
optimisations in a systematic manner. This is because data dependence is
more explicit in a DAG of instructions than in a list of those.

However, I found an exact opposite proposal: removing DAG structure at all (
http://lists.cs.uiuc.edu/pipermail/llvmdev/2013-April/061238.html). I am a
newbie to LLVM (and compiler in general), so I could not understand the
rationale behind the proposal.

Would you please give me some advice on this matter?

Thanks,
Jeehoon

-- 
Jeehoon Kang (Ph.D. student) <http://sf.snu.ac.kr/jeehoon.kang>
Software Foundations Laboratory <http://sf.snu.ac.kr>
Seoul National University <http://www.snu.ac.kr>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150221/3e55a74b/attachment.html>

> 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

On Sat, Feb 21, 2015 at 6:38 PM, David Chisnall <David.Chisnall at
cl.cam.ac.uk
> wrote:
>
> > 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.
>
> The order of loads is still essentially a directed graph. Currently that
information is implicit in the basic block order, and optimisations need to
know if it is safe to screw around with them. Perhaps these relationships
would be better represented explicitly instead, in which case the order of
instructions in a block would be less relevant.

Though of course machine instructions need to be ordered, -O0 shouldn't
mess with the order of operations for debugging purposes, and you do need
some deterministic way to iterate over instructions. So I'm not certain
there'd be much benefit in trying to remove the current ordering of
instructions. If you want to walk the instructions as a DAG you can, if you
want to walk them in execution order you can do that too.

> David
>
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150221/c6f14ce0/attachment.html>