<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 15 (filtered medium)">
<style><!--
/* Font Definitions */
@font-face
{font-family:Helvetica;
panose-1:2 11 5 4 2 2 2 2 2 4;}
@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;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
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;}
span.EmailStyle17
{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]-->
</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">The term for what you are trying to do in general is known as “control-flow graph structuring,” and you can find a bevy of papers on the topic. As David pointed
out already, you can’t necessarily structure a generic CFG using goto, but I will caution that there are some constructs that are basically gotos for the purpose of structuring, namely break and continue (indeed, with multilevel break and continue statements,
you can structure any non-irreducible graph without a goto). Figuring out which edges should be handled as gotos/breaks/continues and which edges should not is something that is not yet settled research.<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">As for your actual goal, you might have a better time of things if you start by generating an infinite loop, with breaks for exiting edges and continues for backedges,
and then try to remove those via refinement steps (which might work better to handle situations such as loop conditions involving short-circuiting operators). In the case of loops with exactly one exiting block terminating with a conditional branch, the exiting
condition is exactly the branch condition (up to negation) of that basic block. In general, doing this sort of analysis safely for generic CFGs is quite difficult, and you should approach the problem from the perspective that you might only sometimes be able
to get this information.<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"><a name="_MailEndCompose"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"><o:p> </o:p></span></a></p>
<div>
<div style="border:none;border-top:solid #E1E1E1 1.0pt;padding:3.0pt 0in 0in 0in">
<p class="MsoNormal" style="margin-left:.5in"><a name="_____replyseparator"></a><b><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">From:</span></b><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"> llvm-dev [mailto:llvm-dev-bounces@lists.llvm.org]
<b>On Behalf Of </b>Ejjeh, Adel via llvm-dev<br>
<b>Sent:</b> Tuesday, August 7, 2018 12:52<br>
<b>To:</b> llvm-dev@lists.llvm.org<br>
<b>Subject:</b> [llvm-dev] Generating a loop from llvm bitcode<o:p></o:p></span></p>
</div>
</div>
<p class="MsoNormal" style="margin-left:.5in"><o:p> </o:p></p>
<p class="MsoNormal" style="margin-left:.5in">Hello <o:p></o:p></p>
<div>
<p class="MsoNormal" style="margin-left:.5in"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:.5in">I am developing a backend that generates OpenCL from llvm bitcode. I start with a revived fork of the original LLVM C-Backend and have been modifying it. One thing that the backend lacked was generating proper loop
structures; instead it relied on labels and goto statements. Therefore, I am trying to find a way to identify the loop structure and print it out in the backend. So far, the main issue I’ve been having trouble with is identifying the loop induction variable
in a straight forward manner; getCanonicalInductionVariable doesn’t always succeed, and I’ve tried using InductionDescriptor, but it fails in cases where the CFG doesn’t include a loop preheader. Also, in both cases, I couldn’t find a direct way of determining
the loop exit condition. I am wondering if there are any passes or data structures that would be able to help me accomplish what I am trying to do that I might be missing? Or does the community have any other ideas as to how I should approach this issue?<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:.5in"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:.5in">Any input is much appreciated.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:.5in"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:.5in">Regards<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:.5in">Adel<o:p></o:p></p>
<div>
<div>
<p class="MsoNormal" style="margin-left:.5in"><span style="font-size:9.0pt;font-family:"Helvetica",sans-serif;color:black">--<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:.5in"><b><span style="font-size:18.0pt;font-family:"Helvetica",sans-serif;color:#0433FF">Adel Ejjeh</span></b><span style="font-size:9.0pt;font-family:"Helvetica",sans-serif;color:black"><br>
PhD Candidate | Computer Science<br>
University of Illinois at Urbana-Champaign<br>
Siebel Center for Computer Science<br>
201 N Goodwin Ave, Urbana, IL 61801<br>
<a href="mailto:aejjeh@illinois.edu">aejjeh@illinois.edu</a> | <a href="mailto:adel.ejjeh@gmail.com">adel.ejjeh@gmail.com</a><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:.5in"><span style="font-size:9.0pt;font-family:"Helvetica",sans-serif;color:black"><o:p> </o:p></span></p>
</div>
<p class="MsoNormal" style="margin-left:.5in"><o:p> </o:p></p>
</div>
<p class="MsoNormal" style="margin-left:.5in"><o:p> </o:p></p>
</div>
</div>
</body>
</html>