[LLVMdev] LLVM IR in DAG form

[Philip Reames]

I don't want to get into the debate w.r.t. which IR style is better - 
ask me over beer if you care about my opinions - but as an FYI, there 
are serious proposals being worked on to introduce some notion of memory 
def-use edges to help in analysing memory operations.  I don't think 
we've settled on a concrete proposal yet, but I wouldn't be surprised to 
see something in the form of an analysis pass which produces 'def-use' 
information for memory operations.

Philip

On 02/22/2015 07:47 PM, Jeehoon Kang wrote:
> Thank you David and Jeremy!
>
> I am quite convinced that LLVM IR in SSA form already expresses data 
> dependence quite well, as said David and Jeremy. Expressing IR in DAG 
> may enable more optimizations on memory operations, but the benefit 
> seems to be not so much.
>
> Furthermore, I strongly agree with Jeremy in that instruction orders 
> should be preserved for -O1 for debugging purposes.
>
> Thank you,
> Jeehoon
>
>
> 2015-02-21 21:41 GMT+09:00 Jeremy Lakeman <Jeremy.Lakeman at gmail.com 
> <mailto:Jeremy.Lakeman at gmail.com>>:
>
>
>
>     On Sat, Feb 21, 2015 at 6:38 PM, David Chisnall
>     <David.Chisnall at cl.cam.ac.uk <mailto:David.Chisnall at cl.cam.ac.uk>>
>     wrote:
>
>
>         > On 21 Feb 2015, at 05:59, Jeehoon Kang
>         <jeehoon.kang at sf.snu.ac.kr <mailto: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 <mailto:LLVMdev at cs.uiuc.edu>
>         http://llvm.cs.uiuc.edu
>         http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
>
>
>
>
> -- 
> 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>
>
>
> _______________________________________________
> 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/20150223/1663dc8f/attachment.html>