<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=Windows-1252">
<style type="text/css" style="display:none;"> P {margin-top:0;margin-bottom:0;} </style>
</head>
<body dir="ltr">
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
I don't know about SystemZ's instructions, but what you described sounded exactly like a hardware loop construct to me. <span style="color: rgb(0, 0, 0); font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt;">That's why I am wondering why using
the hardware loop pass (and some friends) isn't working for you, that wasn't entirely clear to me. </span><span style="color: rgb(0, 0, 0); font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt;">After the HardwareLoop pass we have something
like this:</span></div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<span style="color: rgb(0, 0, 0); font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt;"><br>
</span></div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<span style="color: rgb(0, 0, 0); font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt;"> @set.loop.iterations</span></div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<span style="color: rgb(0, 0, 0); font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt;"> hwloop:</span></div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<span style="color: rgb(0, 0, 0); font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt;"> ..</span></div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<span style="color: rgb(0, 0, 0); font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt;"> @loop.decrement.reg</span></div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<span style="color: rgb(0, 0, 0); font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt;"> icmp</span></div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<span style="color: rgb(0, 0, 0); font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt;"> br hwloop</span></div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<span style="color: rgb(0, 0, 0); font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt;"><br>
</span></div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<span style="color: rgb(0, 0, 0); font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt;">For ARM we indeed then have something like this using pseudos after isel:</span></div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<span style="color: rgb(0, 0, 0); font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt;"><br>
</span></div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<span style="color: rgb(0, 0, 0); font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt;">t2DoLoopStart<br>
</span></div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<span style="color: rgb(0, 0, 0); font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt;">hwloop:</span></div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<span style="color: rgb(0, 0, 0); font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt;"> ..</span></div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<span style="color: rgb(0, 0, 0); font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt;"> $lr = t2LoopDec $lr</span></div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<span style="color: rgb(0, 0, 0); font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt;"> t2LoopEnd $lr, ...</span></div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<span style="color: rgb(0, 0, 0); font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt;"> tB %bb.2, ...<br>
</span></div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<span style="color: rgb(0, 0, 0); font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt;"><br>
</span></div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<span style="color: rgb(0, 0, 0); font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt;"><br>
</span></div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<span style="color: rgb(0, 0, 0); font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt;">These pseudos do a decrement of the register holding the hwloop counter, which is consumed by branch instruction. This seems to match the semantics that
you described: " which takes a register, decrements it, and branches if the register is nonzero", unless I miss something of course... </span><span style="color: rgb(0, 0, 0); font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt;">Very late
in the optimisation pipeline we have an ARM hardware loop pass that converts this in a hwloop and we just have something like this left:</span></div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<span style="color: rgb(0, 0, 0); font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt;"><br>
</span></div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<span style="color: rgb(0, 0, 0); font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt;">$lr = DLS $r2</span></div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<span style="color: rgb(0, 0, 0); font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt;">hwloop:</span></div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<span style="color: rgb(0, 0, 0); font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt;"> ..</span></div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<span style="color: rgb(0, 0, 0); font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt;"> $lr = LE $lr</span></div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<span style="color: rgb(0, 0, 0); font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt;"><br>
</span></div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<span style="color: rgb(0, 0, 0); font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt;">And while I think the semantics of our LE instructions is slightly different I think, I don't think it matters (again, unless I miss something).</span></div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<span style="color: rgb(0, 0, 0); font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt;"><br>
</span></div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<span style="color: rgb(0, 0, 0); font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt;">Sorry for not answering your actual isel question. Can't answer that without digging into it, perhaps someone else can.</span></div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<span style="color: rgb(0, 0, 0); font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt;"><br>
</span></div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<span style="color: rgb(0, 0, 0); font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt;">Cheers,</span></div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<span style="color: rgb(0, 0, 0); font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt;">Sjoerd.</span></div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<span style="color: rgb(0, 0, 0); font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt;"><br>
</span></div>
<div id="appendonsend"></div>
<hr style="display:inline-block;width:98%" tabindex="-1">
<div id="divRplyFwdMsg" dir="ltr"><font face="Calibri, sans-serif" style="font-size:11pt" color="#000000"><b>From:</b> llvm-dev <llvm-dev-bounces@lists.llvm.org> on behalf of Nagurne, James via llvm-dev <llvm-dev@lists.llvm.org><br>
<b>Sent:</b> 07 August 2020 23:57<br>
<b>To:</b> llvm-dev@lists.llvm.org <llvm-dev@lists.llvm.org><br>
<b>Subject:</b> [llvm-dev] Branches which return values in SelectionDAG</font>
<div> </div>
</div>
<style>
<!--
@font-face
{font-family:Wingdings}
@font-face
{font-family:Wingdings}
@font-face
{font-family:Calibri}
p.x_MsoNormal, li.x_MsoNormal, div.x_MsoNormal
{margin:0in;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri","sans-serif"}
a:link, span.x_MsoHyperlink
{color:blue;
text-decoration:underline}
a:visited, span.x_MsoHyperlinkFollowed
{color:purple;
text-decoration:underline}
p.x_MsoListParagraph, li.x_MsoListParagraph, div.x_MsoListParagraph
{margin-top:0in;
margin-right:0in;
margin-bottom:0in;
margin-left:.5in;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri","sans-serif"}
span.x_EmailStyle17
{font-family:"Calibri","sans-serif";
color:windowtext}
.x_MsoChpDefault
{font-family:"Calibri","sans-serif"}
@page WordSection1
{margin:1.0in 1.0in 1.0in 1.0in}
div.x_WordSection1
{}
ol
{margin-bottom:0in}
ul
{margin-bottom:0in}
-->
</style>
<div lang="EN-US" link="blue" vlink="purple">
<div class="x_WordSection1">
<p class="x_MsoNormal">Hi all,</p>
<p class="x_MsoNormal"> </p>
<p class="x_MsoNormal">I am working on modeling an instruction similar to SystemZ’s ‘BRCT’, which takes a register, decrements it, and branches if the register is nonzero. I saw that the LLVM backend for SystemZ generates the instruction in a MachineFunctionPass
as part of a pass intended to eliminate or combine compares.</p>
<p class="x_MsoNormal"> </p>
<p class="x_MsoNormal">I then looked at ARM, where it uses the HardwareLoops pass first, and then a combine that occurs in the ARM ISel stage. It replaces branch instructions with special ‘WLS’ and ‘LE’ nodes that are custom selected into t2WhileLoopStart and
t2LoopEnd pseudo instructions with isBranch and isTerminator set. These pseudo instructions are finalized in a later MachineFunctionPass.</p>
<p class="x_MsoNormal"> </p>
<p class="x_MsoNormal">I had originally intended to use the HardwareLoops pass to do most of the initial transformation and bookkeeping, allowing me to utilize the generated intrinsics in my own pass to further transform and customize the loop.</p>
<p class="x_MsoNormal">What I found out, however, is that I don’t know enough about the SelectionDAG to know if this is possible.</p>
<p class="x_MsoNormal">Trying to combine the two concepts (Value-returning branches and handling them in the selection DAG), I wrote my backend to generate:</p>
<p class="x_MsoNormal"> </p>
<p class="x_MsoNormal">header:</p>
<p class="x_MsoNormal"> %InitialVal = N</p>
<p class="x_MsoNormal">body:</p>
<p class="x_MsoNormal" style="text-indent:.5in">%IndVar = PHI(%InitialVal, %header, %DecVal, %body)</p>
<p class="x_MsoNormal" style="text-indent:.5in">…</p>
<p class="x_MsoNormal" style="text-indent:.5in">%MultipleReturns = call {i32, i1} compare_and_maybe_decrement(%IndVar, 1)</p>
<p class="x_MsoNormal" style="text-indent:.5in">%DecVal = extract {i32, i1} %MultipleReturns 0</p>
<p class="x_MsoNormal" style="text-indent:.5in">%Cond = extract {i32, i1} %MultipleReturns 1</p>
<p class="x_MsoNormal" style="text-indent:.5in">br %Cond, body, exit</p>
<p class="x_MsoNormal">exit:</p>
<p class="x_MsoNormal"> …</p>
<p class="x_MsoNormal"> </p>
<p class="x_MsoNormal">Then, I attempted to combine the intrinsic, extractions, and branch together in the SelectionDAG.</p>
<p class="x_MsoNormal">What I found, however, is that this concept, which seems fine in the LLVM IR, is not fine in the DAG.</p>
<p class="x_MsoNormal"> </p>
<p class="x_MsoNormal">Specifically, there is a CopyToReg in the DAG that occurs between the intrinsic and the branch that saves off %DecVal. I presume it’s there because the value is leaving the DAG (to be copied from in the next iteration). With the branch
node returning that value instead, it seems like there’s no legal location in which to place this necessary CopyToReg. If you order it after the fused branch, I believe it’s illegal because it’s logically incorrect (only copy if we’re terminating the loop?).
If you order it before, I don’t think the DAG makes sense anymore:</p>
<p class="x_MsoNormal"> </p>
<p class="x_MsoNormal"> t1 = CopyToReg %1, t2 ; Copying a value before it’s defined???</p>
<p class="x_MsoNormal"> t2 = Target::BR_DEC …</p>
<p class="x_MsoNormal"> </p>
<p class="x_MsoNormal">Indeed, I get the abort “Operand not processed?” for the CopyToReg when I tried it, indicating something was amiss.</p>
<p class="x_MsoNormal">I’m more than willing to provide more context such as DAG dumps if people have ideas, I just didn’t want to fill this email with debug.</p>
<p class="x_MsoNormal"> </p>
<p class="x_MsoNormal">Is what I’m doing possible? Or does it make sense to keep the special and separate compare_and_maybe_decrement operation until after selection is finished so that I can fuse using MachineInstrs instead?</p>
<p class="x_MsoNormal"> </p>
<p class="x_MsoNormal">Thanks for any help!</p>
<p class="x_MsoNormal">J.B. Nagurne</p>
<p class="x_MsoNormal">Code Generation</p>
<p class="x_MsoNormal">Texas Instruments</p>
</div>
</div>
</body>
</html>