<html>
<head>
<meta content="text/html; charset=windows-1252"
http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
I'd suggest you start a new thread with this question. It's
unlikely to get much attention here. Its gone from being a very
abstract question to a "how do I represent X" question. You'll
probably also need to provide more information about the sequencing
rules for your source language. Are there aliasing guarantees?
Restrictions on the functions called? etc...<br>
<br>
<div class="moz-cite-prefix">On 02/23/2015 01:14 PM, Colin LeMahieu
wrote:<br>
</div>
<blockquote
cite="mid:080201d04fad$a6fb7be0$f4f273a0$@codeaurora.org"
type="cite">
<meta http-equiv="Content-Type" content="text/html;
charset=windows-1252">
<meta name="Generator" content="Microsoft Word 15 (filtered
medium)">
<style><!--
/* Font Definitions */
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
@font-face
{font-family:Consolas;
panose-1:2 11 6 9 2 2 4 3 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
margin-bottom:.0001pt;
font-size:12.0pt;
font-family:"Times New Roman",serif;
color:black;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:purple;
text-decoration:underline;}
pre
{mso-style-priority:99;
mso-style-link:"HTML Preformatted Char";
margin:0in;
margin-bottom:.0001pt;
font-size:10.0pt;
font-family:"Courier New";
color:black;}
span.HTMLPreformattedChar
{mso-style-name:"HTML Preformatted Char";
mso-style-priority:99;
mso-style-link:"HTML Preformatted";
font-family:Consolas;
color:black;}
span.EmailStyle19
{mso-style-type:personal-reply;
font-family:"Calibri",sans-serif;
color:#1F497D;}
.MsoChpDefault
{mso-style-type:export-only;
font-size:10.0pt;}
@page WordSection1
{size:8.5in 11.0in;
margin:1.0in 1.0in 1.0in 1.0in;}
div.WordSection1
{page:WordSection1;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]-->
<div class="WordSection1">
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">I’ve
noticed this subtle issue before as well when building a
frontend language that takes DAGs of function calls rather
than lists. While an optimizer would be able to make good
use of this information from the frontend, I have to
topo-sort flatten this information out when outputting IR or
build my own optimization pass concepts.<o:p></o:p></span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">In
the frontend we add the idea of nested-but-not-passed
function arguments. This allows something like “store (i32
a, i32* b, sequenced (store(i32c, i32*d)))”<o:p></o:p></span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">Where
things inside “sequenced” are performed in a nested format
but the return values are discarded and not passed to the
enclosing expression.<o:p></o:p></span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">Perhaps
something like this could spawn some ideas.<o:p></o:p></span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"><o:p> </o:p></span></p>
<div>
<div style="border:none;border-top:solid #E1E1E1
1.0pt;padding:3.0pt 0in 0in 0in">
<p class="MsoNormal"><b><span
style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:windowtext">From:</span></b><span
style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:windowtext">
<a class="moz-txt-link-abbreviated" href="mailto:llvmdev-bounces@cs.uiuc.edu">llvmdev-bounces@cs.uiuc.edu</a>
[<a class="moz-txt-link-freetext" href="mailto:llvmdev-bounces@cs.uiuc.edu">mailto:llvmdev-bounces@cs.uiuc.edu</a>] <b>On Behalf Of </b>Philip
Reames<br>
<b>Sent:</b> Monday, February 23, 2015 1:48 PM<br>
<b>To:</b> Jeehoon Kang; Jeremy Lakeman<br>
<b>Cc:</b> LLVM Developers Mailing List<br>
<b>Subject:</b> Re: [LLVMdev] LLVM IR in DAG form<o:p></o:p></span></p>
</div>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal" style="margin-bottom:12.0pt">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. <br>
<br>
Philip<o:p></o:p></p>
<div>
<p class="MsoNormal">On 02/22/2015 07:47 PM, Jeehoon Kang
wrote:<o:p></o:p></p>
</div>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<div>
<p class="MsoNormal">Thank you David and Jeremy! <o:p></o:p></p>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">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.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">Furthermore, I strongly agree with
Jeremy in that instruction orders should be preserved
for -O1 for debugging purposes.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">Thank you,<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">Jeehoon<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<p class="MsoNormal">2015-02-21 21:41 GMT+09:00 Jeremy
Lakeman <<a moz-do-not-send="true"
href="mailto:Jeremy.Lakeman@gmail.com" target="_blank">Jeremy.Lakeman@gmail.com</a>>:<o:p></o:p></p>
<blockquote style="border:none;border-left:solid #CCCCCC
1.0pt;padding:0in 0in 0in
6.0pt;margin-left:4.8pt;margin-right:0in">
<div>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<div>
<div>
<p class="MsoNormal">On Sat, Feb 21, 2015 at
6:38 PM, David Chisnall <<a
moz-do-not-send="true"
href="mailto:David.Chisnall@cl.cam.ac.uk"
target="_blank">David.Chisnall@cl.cam.ac.uk</a>>
wrote:<o:p></o:p></p>
<blockquote
style="border:none;border-left:solid #CCCCCC
1.0pt;padding:0in 0in 0in
6.0pt;margin-left:4.8pt;margin-right:0in">
<p class="MsoNormal"
style="margin-bottom:12.0pt"><br>
> On 21 Feb 2015, at 05:59, Jeehoon
Kang <<a moz-do-not-send="true"
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>
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.<o:p></o:p></p>
</blockquote>
</div>
</div>
<div>
<p class="MsoNormal"
style="margin-bottom:12.0pt">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. <o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">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.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> <o:p></o:p></p>
</div>
<blockquote style="border:none;border-left:solid
#CCCCCC 1.0pt;padding:0in 0in 0in
6.0pt;margin-left:4.8pt;margin-right:0in">
<p class="MsoNormal">David<br>
<br>
<br>
_______________________________________________<br>
LLVM Developers mailing list<br>
<a moz-do-not-send="true"
href="mailto:LLVMdev@cs.uiuc.edu"
target="_blank">LLVMdev@cs.uiuc.edu</a>
<a moz-do-not-send="true"
href="http://llvm.cs.uiuc.edu"
target="_blank">http://llvm.cs.uiuc.edu</a><br>
<a moz-do-not-send="true"
href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev"
target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><o:p></o:p></p>
</blockquote>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
</div>
</blockquote>
</div>
<p class="MsoNormal"><br>
<br clear="all">
<o:p></o:p></p>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<p class="MsoNormal">-- <o:p></o:p></p>
<div>
<div>
<p class="MsoNormal"><a moz-do-not-send="true"
href="http://sf.snu.ac.kr/jeehoon.kang"
target="_blank">Jeehoon Kang (Ph.D. student)</a> <o:p></o:p></p>
<div>
<p class="MsoNormal"><a moz-do-not-send="true"
href="http://sf.snu.ac.kr" target="_blank">Software
Foundations Laboratory</a> <o:p></o:p></p>
<div>
<p class="MsoNormal"><a moz-do-not-send="true"
href="http://www.snu.ac.kr" target="_blank">Seoul
National University</a><o:p></o:p></p>
</div>
</div>
</div>
</div>
</div>
<p class="MsoNormal"><br>
<br>
<br>
<o:p></o:p></p>
<pre>_______________________________________________<o:p></o:p></pre>
<pre>LLVM Developers mailing list<o:p></o:p></pre>
<pre><a moz-do-not-send="true" href="mailto:LLVMdev@cs.uiuc.edu">LLVMdev@cs.uiuc.edu</a> <a moz-do-not-send="true" href="http://llvm.cs.uiuc.edu">http://llvm.cs.uiuc.edu</a><o:p></o:p></pre>
<pre><a moz-do-not-send="true" href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><o:p></o:p></pre>
</blockquote>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
</blockquote>
<br>
</body>
</html>