<div dir="ltr">Thank you David and Jeremy!<div><br></div><div>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.</div><div><br></div><div>Furthermore, I strongly agree with Jeremy in that instruction orders should be preserved for -O1 for debugging purposes.</div><div><br></div><div>Thank you,<br></div><div>Jeehoon</div><div><br></div></div><div class="gmail_extra"><br><div class="gmail_quote">2015-02-21 21:41 GMT+09:00 Jeremy Lakeman <span dir="ltr"><<a href="mailto:Jeremy.Lakeman@gmail.com" target="_blank">Jeremy.Lakeman@gmail.com</a>></span>:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote"><div><div class="h5">On Sat, Feb 21, 2015 at 6:38 PM, David Chisnall <span dir="ltr"><<a href="mailto:David.Chisnall@cl.cam.ac.uk" target="_blank">David.Chisnall@cl.cam.ac.uk</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span><br>
> On 21 Feb 2015, at 05:59, Jeehoon Kang <<a href="mailto:jeehoon.kang@sf.snu.ac.kr" target="_blank">jeehoon.kang@sf.snu.ac.kr</a>> wrote:<br>
><br>
> this is Jeehoon Kang, a CS PhD student and a newbie to LLVM.<br>
><br>
> I am wondering why LLVM IR's basic block consists of a list of instructions,<br>
> rather than a DAG of instruction as in the low level (ISelectionDAG).<br>
<br>
</span>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.<br>
<br></blockquote></div></div><div>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. <br><br></div><div>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.<br></div><div> <br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
David<br>
<br>
<br>
_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:LLVMdev@cs.uiuc.edu" target="_blank">LLVMdev@cs.uiuc.edu</a>         <a href="http://llvm.cs.uiuc.edu" target="_blank">http://llvm.cs.uiuc.edu</a><br>
<a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br>
</blockquote></div><br></div></div>
</blockquote></div><br><br clear="all"><div><br></div>-- <br><div class="gmail_signature"><div dir="ltr"><a href="http://sf.snu.ac.kr/jeehoon.kang" target="_blank">Jeehoon Kang (Ph.D. student)</a><div><a href="http://sf.snu.ac.kr" target="_blank">Software Foundations Laboratory</a><div><a href="http://www.snu.ac.kr" target="_blank">Seoul National University</a></div></div></div></div>
</div>