<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<meta name="Generator" content="Microsoft Word 14 (filtered medium)">
<style><!--
/* Font Definitions */
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
@font-face
{font-family:Tahoma;
panose-1:2 11 6 4 3 5 4 4 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0cm;
margin-bottom:.0001pt;
font-size:12.0pt;
font-family:"Times New Roman","serif";}
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;}
p
{mso-style-priority:99;
mso-margin-top-alt:auto;
margin-right:0cm;
mso-margin-bottom-alt:auto;
margin-left:0cm;
font-size:12.0pt;
font-family:"Times New Roman","serif";}
span.EmailStyle18
{mso-style-type:personal-reply;
font-family:"Calibri","sans-serif";
color:#1F497D;}
.MsoChpDefault
{mso-style-type:export-only;
font-family:"Calibri","sans-serif";}
@page WordSection1
{size:612.0pt 792.0pt;
margin:72.0pt 72.0pt 72.0pt 72.0pt;}
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]-->
</head>
<body lang="EN-US" link="blue" vlink="purple">
<div class="WordSection1">
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D">Hi Anirudh,<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">I hope these lecture slides about SSA and the dominance frontier will help you with SSA and control flow analysis:<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"><a href="https://urldefense.proofpoint.com/v2/url?u=http-3A__www.seas.harvard.edu_courses_cs252_2011sp_slides_Lec04-2DSSA.pdf&d=AwMGaQ&c=8hUWFZcy2Z-Za5rBPlktOQ&r=Mfk2qtn1LTDThVkh6-oGglNfMADXfJdty4_bhmuhMHA&m=KFXICLzXhhfG4M1sxcsZ50rFeTSU8bedZgmjeYaZAtM&s=v3jN_Nt0eWOrh4rvee3fatFgEU852cslo_kwxi0oVC0&e=">http://www.seas.harvard.edu/courses/cs252/2011sp/slides/Lec04-SSA.pdf</a><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">Unfortunately a use of DominanceFrontierBase is deprecated in LLVM.<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>>Thank you for your response. Going by your definition, x is control dependent on y.<o:p></o:p></p>
<p>> To extract this control dependency, do I need to maintain path conditions for each basic block or can I do something simpler?<o:p></o:p></p>
<p>>Also, I feel like this should be a recurring problem. Could you point me to any code example that identifies all dependencies (control and data) for phi instructions?<o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D">You won’t have any of this problems if you build dominance frontiers in the reverse CFG (ReverseDominanceFrontiers).<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D">Then for a phi-function you get its basic block A and for the basic block A you get RDF(A). Your phi-function depends on conditions in basic blocks from RDF(A).<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">Kind regards,<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D">Evgeny Astigeevich<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"><o:p> </o:p></span></p>
<p class="MsoNormal"><b><span style="font-size:10.0pt;font-family:"Tahoma","sans-serif"">From:</span></b><span style="font-size:10.0pt;font-family:"Tahoma","sans-serif""> Anirudh Sivaraman [mailto:sk.anirudh@gmail.com]
<br>
<b>Sent:</b> 29 June 2015 15:22<br>
<b>To:</b> Evgeny Astigeevich<br>
<b>Cc:</b> LLVM Developers Mailing List<br>
<b>Subject:</b> RE: [LLVMdev] Inferring dependencies in phi instructions<o:p></o:p></span></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p><br>
On Jun 29, 2015 3:16 AM, "Evgeny Astigeevich" <<a href="mailto:evgeny.astigeevich@arm.com">evgeny.astigeevich@arm.com</a>> wrote:<br>
><br>
> Hi Anirudh,<br>
><br>
> 'x' has a control dependency on 'y' because the value assigned to 'x'<br>
> depends on a path selected. This dependency can be converted into a data<br>
> dependency by means of a 'select' instruction because the control flow is<br>
> simple.<br>
> What is the problem with using phi-functions in DFG? Yes they require more<br>
> work to find out what they depend on.<br>
><o:p></o:p></p>
<p>Thank you for your response. Going by your definition, x is control dependent on y. To extract this control dependency, do I need to maintain path conditions for each basic block or can I do something simpler?<o:p></o:p></p>
<p>Also, I feel like this should be a recurring problem. Could you point me to any code example that identifies all dependencies (control and data) for phi instructions?<o:p></o:p></p>
<p>> Kind regards,<br>
> Evgeny Astigeevich<br>
><br>
> -----Original Message-----<br>
> From: <a href="mailto:llvmdev-bounces@cs.uiuc.edu">llvmdev-bounces@cs.uiuc.edu</a> [mailto:<a href="mailto:llvmdev-bounces@cs.uiuc.edu">llvmdev-bounces@cs.uiuc.edu</a>] On<br>
> Behalf Of Anirudh Sivaraman<br>
> Sent: 29 June 2015 07:25<br>
> To: LLVM Developers Mailing List<br>
> Subject: [LLVMdev] Inferring dependencies in phi instructions<br>
><br>
> I am trying to infer data dependencies using LLVM's def-use chains and I am<br>
> having trouble dealing with 'phi' instructions. Specifically,<br>
><br>
> If I am given the code snippet:<br>
><br>
> int foo() {<br>
> int y = 1;<br>
> int x;<br>
> if (y) {<br>
> x = 2;<br>
> } else {<br>
> x = 3;<br>
> }<br>
> return x;<br>
> }<br>
><br>
> Here, x has a data dependence on y (not control because x is assigned in<br>
> both halves), but LLVM expresses 'x' as: %x.0 = phi i32 [ 2, %2 ], [ 3, %3 ]<br>
> using phi-nodes, omitting the dependence on y.<br>
><br>
> If I write the function as:<br>
><br>
> int foo() {<br>
> int y = 1;<br>
> int x = y ? 2 : 3;<br>
> return x;<br>
> },<br>
><br>
> the dependencies work out alright because LLVM now uses a select<br>
> instruction, where the dependence on y is explicit:<br>
><br>
> %y = select i1 %x, i32 2, i32 3<br>
><br>
> In general, I don't think I can convert phi nodes into select statements<br>
> (because a phi node can refer to values from more than two paths in general,<br>
> while select statements permit only two options, one each for a true and a<br>
> false branch). Any thoughts on how this is handled in practice would be very<br>
> helpful.<br>
><br>
> Anirudh<br>
> _______________________________________________<br>
> LLVM Developers mailing list<br>
> <a href="mailto:LLVMdev@cs.uiuc.edu">LLVMdev@cs.uiuc.edu</a> <a href="http://llvm.cs.uiuc.edu">http://llvm.cs.uiuc.edu</a><br>
> <a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br>
><br>
><br>
><o:p></o:p></p>
</div>
<br>
<font face="Arial" color="Black" size="2">-- IMPORTANT NOTICE: The contents of this email and any attachments are confidential and may also be privileged. If you are not the intended recipient, please notify the sender immediately and do not disclose the contents
to any other person, use it for any purpose, or store or copy the information in any medium. Thank you.<br>
<br>
ARM Limited, Registered office 110 Fulbourn Road, Cambridge CB1 9NJ, Registered in England & Wales, Company No: 2557590<br>
ARM Holdings plc, Registered office 110 Fulbourn Road, Cambridge CB1 9NJ, Registered in England & Wales, Company No: 2548782<br>
</font>
</body>
</html>