<div dir="ltr">Hello everyone,<div><br></div><div>I'm trying to find reduction variables in a loop and I have a couple of questions about it.</div><div><br></div><div>Is it necessary that a reduction variable should be associated with a Phi node?</div><div><br></div><div><div>For my purpose, I tried using isReductionPHI() from LoopUtils.cpp (that is used by LoopVectorizer) for a toy C program (find below) that has a clear reduction variable but it still returns false.</div></div><div><br></div><div>
<span></span>
<h2></h2>
<div class="gmail-highlight" style="background:rgb(248,248,248)"><pre style="line-height:125%"><span style="color:rgb(188,122,0)">// Toy program where "sum" is the reduction variable.</span></pre><pre style="line-height:125%"><span style="color:rgb(188,122,0)">#include <stdio.h></span>
<span style="color:rgb(176,0,64)">int</span> <span style="color:rgb(0,0,255)">main</span>(<span style="color:rgb(176,0,64)">int</span> argc, <span style="color:rgb(176,0,64)">char</span> <span style="color:rgb(0,128,0);font-weight:bold">const</span> <span style="color:rgb(102,102,102)">*</span>argv[])
{
<span style="color:rgb(176,0,64)">int</span> sum <span style="color:rgb(102,102,102)">=</span> <span style="color:rgb(102,102,102)">0</span>, a[<span style="color:rgb(102,102,102)">100</span>], i;
<span style="color:rgb(0,128,0);font-weight:bold">for</span>(i <span style="color:rgb(102,102,102)">=</span> <span style="color:rgb(102,102,102)">0</span>; i <span style="color:rgb(102,102,102)"><</span> <span style="color:rgb(102,102,102)">100</span>; i<span style="color:rgb(102,102,102)">++</span>)
sum <span style="color:rgb(102,102,102)">+=</span> a[i];
printf(<span style="color:rgb(186,33,33)">"sum: %d</span><span style="color:rgb(187,102,34);font-weight:bold">\n</span><span style="color:rgb(186,33,33)">"</span>, sum);
<span style="color:rgb(0,128,0);font-weight:bold">return</span> <span style="color:rgb(102,102,102)">0</span>;
}
</pre></div>
I generated LLVM IR (toy_reduction.ll) for the above program and then applied mem2reg on top of it (toy_reduction_mem2reg.ll). I have implemented a toy analysis pass which prints the phi nodes that are associated with reduction variables which is as under.</div><div><br></div><div>
<span></span>
<h2></h2>
<div class="gmail-highlight" style="background:rgb(248,248,248)"><pre style="line-height:125%"><span style="color:rgb(176,0,64)">void</span> <span style="color:rgb(0,0,255)">checkRedux</span>(Loop <span style="color:rgb(102,102,102)">*</span>L) {
<span style="color:rgb(0,128,0);font-weight:bold">for</span> (BasicBlock <span style="color:rgb(102,102,102)">*</span>BB <span style="color:rgb(102,102,102)">:</span> L<span style="color:rgb(102,102,102)">-></span>getBlocks()) {
<span style="color:rgb(0,128,0);font-weight:bold">for</span> (Instruction <span style="color:rgb(102,102,102)">&</span>I <span style="color:rgb(102,102,102)">:</span> <span style="color:rgb(102,102,102)">*</span>BB) {
<span style="color:rgb(0,128,0);font-weight:bold">if</span> (<span style="color:rgb(0,128,0);font-weight:bold">auto</span> <span style="color:rgb(102,102,102)">*</span>Phi <span style="color:rgb(102,102,102)">=</span> dyn_cast<span style="color:rgb(102,102,102)"><</span>PHINode<span style="color:rgb(102,102,102)">></span>(<span style="color:rgb(102,102,102)">&</span>I)) {
errs() <span style="color:rgb(102,102,102)"><<</span> <span style="color:rgb(102,102,102)">*</span>Phi <span style="color:rgb(102,102,102)"><<</span> <span style="color:rgb(186,33,33)">"</span><span style="color:rgb(187,102,34);font-weight:bold">\n</span><span style="color:rgb(186,33,33)">"</span>;
RecurrenceDescriptor RedDes;
<span style="color:rgb(0,128,0);font-weight:bold">if</span> (RecurrenceDescriptor<span style="color:rgb(102,102,102)">::</span>isReductionPHI(Phi, L, RedDes)) {
errs() <span style="color:rgb(102,102,102)"><<</span> <span style="color:rgb(186,33,33)">"Found reduction object</span><span style="color:rgb(187,102,34);font-weight:bold">\n</span><span style="color:rgb(186,33,33)">"</span>;
errs() <span style="color:rgb(102,102,102)"><<</span> <span style="color:rgb(102,102,102)">*</span>Phi <span style="color:rgb(102,102,102)"><<</span> <span style="color:rgb(186,33,33)">"</span><span style="color:rgb(187,102,34);font-weight:bold">\n</span><span style="color:rgb(186,33,33)">"</span>;
}
}
}
}
} </pre><pre style="line-height:125%"><div class="gmail-highlight" style="background:rgb(248,248,248)"><pre style="line-height:125%"><span style="color:rgb(176,0,64)">bool</span> <span style="color:rgb(0,0,255)">runOnFunction</span>(Function <span style="color:rgb(102,102,102)">&</span>F) override {
<span style="color:rgb(0,128,0);font-weight:bold">auto</span> <span style="color:rgb(102,102,102)">*</span>LI <span style="color:rgb(102,102,102)">=</span> <span style="color:rgb(102,102,102)">&</span>getAnalysis<span style="color:rgb(102,102,102)"><</span>LoopInfoWrapperPass<span style="color:rgb(102,102,102)">></span>().getLoopInfo();
<span style="color:rgb(0,128,0);font-weight:bold">for</span>(Loop <span style="color:rgb(102,102,102)">*</span>L <span style="color:rgb(102,102,102)">:</span> <span style="color:rgb(102,102,102)">*</span>LI){
checkRedux(L);
}
<span style="color:rgb(0,128,0);font-weight:bold">return</span> <span style="color:rgb(0,128,0)">false</span>;
}</pre></div></pre></div>
<br></div><div>
However, for the input file toy_reduction_mem2reg.ll, isReductionPHI() returns false every time the control reaches there thereby declaring that there are no reduction variables when clearly there is one (sum).</div><div><br></div><div>Find below a snippet of the LLVM IR after applying mem2reg.</div><div><br></div><div>
<span></span>
<h2></h2>
<div class="gmail-highlight" style="background:rgb(248,248,248)"><pre style="line-height:125%"><span style="color:rgb(0,128,0);font-weight:bold">define</span> <span style="color:rgb(0,128,0);font-weight:bold">i32</span> <span style="color:rgb(25,23,124)">@main</span>(<span style="color:rgb(0,128,0);font-weight:bold">i32</span> <span style="color:rgb(25,23,124)">%argc</span>, <span style="color:rgb(0,128,0);font-weight:bold">i8</span>** <span style="color:rgb(25,23,124)">%argv</span>) <span style="border:1px solid rgb(255,0,0)">#</span><span style="color:rgb(102,102,102)">0</span> {
<span style="color:rgb(160,160,0)">entry:</span>
<span style="color:rgb(25,23,124)">%a</span> = <span style="color:rgb(0,128,0);font-weight:bold">alloca</span> [<span style="color:rgb(102,102,102)">100</span> <span style="color:rgb(0,128,0);font-weight:bold">x</span> <span style="color:rgb(0,128,0);font-weight:bold">i32</span>], <span style="color:rgb(0,128,0);font-weight:bold">align</span> <span style="color:rgb(102,102,102)">16</span>
<span style="color:rgb(0,128,0);font-weight:bold">br</span> <span style="color:rgb(176,0,64)">label</span> <span style="color:rgb(25,23,124)">%for.cond</span>
<span style="color:rgb(160,160,0)">for.cond:</span> <span style="color:rgb(64,128,128);font-style:italic">; preds = %for.inc, %entry</span>
<span style="color:rgb(25,23,124)">%sum.0</span> = <span style="color:rgb(0,128,0);font-weight:bold">phi</span> <span style="color:rgb(0,128,0);font-weight:bold">i32</span> [ <span style="color:rgb(102,102,102)">0</span>, <span style="color:rgb(25,23,124)">%entry</span> ], [ <span style="color:rgb(25,23,124)">%add</span>, <span style="color:rgb(25,23,124)">%for.inc</span> ]
<span style="color:rgb(25,23,124)">%i.0</span> = <span style="color:rgb(0,128,0);font-weight:bold">phi</span> <span style="color:rgb(0,128,0);font-weight:bold">i32</span> [ <span style="color:rgb(102,102,102)">0</span>, <span style="color:rgb(25,23,124)">%entry</span> ], [ <span style="color:rgb(25,23,124)">%inc</span>, <span style="color:rgb(25,23,124)">%for.inc</span> ]
<span style="color:rgb(25,23,124)">%cmp</span> = <span style="color:rgb(0,128,0);font-weight:bold">icmp</span> <span style="color:rgb(0,128,0);font-weight:bold">slt</span> <span style="color:rgb(0,128,0);font-weight:bold">i32</span> <span style="color:rgb(25,23,124)">%i.0</span>, <span style="color:rgb(102,102,102)">100</span>
<span style="color:rgb(0,128,0);font-weight:bold">br</span> <span style="color:rgb(0,128,0);font-weight:bold">i1</span> <span style="color:rgb(25,23,124)">%cmp</span>, <span style="color:rgb(176,0,64)">label</span> <span style="color:rgb(25,23,124)">%for.body</span>, <span style="color:rgb(176,0,64)">label</span> <span style="color:rgb(25,23,124)">%for.end</span>
<span style="color:rgb(160,160,0)">for.body:</span> <span style="color:rgb(64,128,128);font-style:italic">; preds = %for.cond</span>
<span style="color:rgb(25,23,124)">%idxprom</span> = <span style="color:rgb(0,128,0);font-weight:bold">sext</span> <span style="color:rgb(0,128,0);font-weight:bold">i32</span> <span style="color:rgb(25,23,124)">%i.0</span> <span style="color:rgb(0,128,0);font-weight:bold">to</span> <span style="color:rgb(0,128,0);font-weight:bold">i64</span>
<span style="color:rgb(25,23,124)">%arrayidx</span> = <span style="color:rgb(0,128,0);font-weight:bold">getelementptr</span> <span style="color:rgb(0,128,0);font-weight:bold">inbounds</span> [<span style="color:rgb(102,102,102)">100</span> <span style="color:rgb(0,128,0);font-weight:bold">x</span> <span style="color:rgb(0,128,0);font-weight:bold">i32</span>], [<span style="color:rgb(102,102,102)">100</span> <span style="color:rgb(0,128,0);font-weight:bold">x</span> <span style="color:rgb(0,128,0);font-weight:bold">i32</span>]* <span style="color:rgb(25,23,124)">%a</span>, <span style="color:rgb(0,128,0);font-weight:bold">i64</span> <span style="color:rgb(102,102,102)">0</span>, <span style="color:rgb(0,128,0);font-weight:bold">i64</span> <span style="color:rgb(25,23,124)">%idxprom</span>
<span style="color:rgb(25,23,124)">%0</span> = <span style="color:rgb(0,128,0);font-weight:bold">load</span> <span style="color:rgb(0,128,0);font-weight:bold">i32</span>, <span style="color:rgb(0,128,0);font-weight:bold">i32</span>* <span style="color:rgb(25,23,124)">%arrayidx</span>, <span style="color:rgb(0,128,0);font-weight:bold">align</span> <span style="color:rgb(102,102,102)">4</span>
<span style="color:rgb(25,23,124)">%add</span> = <span style="color:rgb(0,128,0);font-weight:bold">add</span> <span style="color:rgb(0,128,0);font-weight:bold">nsw</span> <span style="color:rgb(0,128,0);font-weight:bold">i32</span> <span style="color:rgb(25,23,124)">%sum.0</span>, <span style="color:rgb(25,23,124)">%0</span>
<span style="color:rgb(0,128,0);font-weight:bold">br</span> <span style="color:rgb(176,0,64)">label</span> <span style="color:rgb(25,23,124)">%for.inc</span>
<span style="color:rgb(160,160,0)">for.inc:</span> <span style="color:rgb(64,128,128);font-style:italic">; preds = %for.body</span>
<span style="color:rgb(25,23,124)">%inc</span> = <span style="color:rgb(0,128,0);font-weight:bold">add</span> <span style="color:rgb(0,128,0);font-weight:bold">nsw</span> <span style="color:rgb(0,128,0);font-weight:bold">i32</span> <span style="color:rgb(25,23,124)">%i.0</span>, <span style="color:rgb(102,102,102)">1</span>
<span style="color:rgb(0,128,0);font-weight:bold">br</span> <span style="color:rgb(176,0,64)">label</span> <span style="color:rgb(25,23,124)">%for.cond</span>
<span style="color:rgb(160,160,0)">for.end:</span> <span style="color:rgb(64,128,128);font-style:italic">; preds = %for.cond</span>
<span style="color:rgb(25,23,124)">%call</span> = <span style="color:rgb(0,128,0);font-weight:bold">call</span> <span style="color:rgb(0,128,0);font-weight:bold">i32</span> (<span style="color:rgb(0,128,0);font-weight:bold">i8</span>*, ...) <span style="color:rgb(25,23,124)">@printf</span>(<span style="color:rgb(0,128,0);font-weight:bold">i8</span>* <span style="color:rgb(0,128,0);font-weight:bold">getelementptr</span> <span style="color:rgb(0,128,0);font-weight:bold">inbounds</span> ([<span style="color:rgb(102,102,102)">9</span> <span style="color:rgb(0,128,0);font-weight:bold">x</span> <span style="color:rgb(0,128,0);font-weight:bold">i8</span>], [<span style="color:rgb(102,102,102)">9</span> <span style="color:rgb(0,128,0);font-weight:bold">x</span> <span style="color:rgb(0,128,0);font-weight:bold">i8</span>]* <span style="color:rgb(25,23,124)">@.str</span>, <span style="color:rgb(0,128,0);font-weight:bold">i32</span> <span style="color:rgb(102,102,102)">0</span>, <span style="color:rgb(0,128,0);font-weight:bold">i32</span> <span style="color:rgb(102,102,102)">0</span>), <span style="color:rgb(0,128,0);font-weight:bold">i32</span> <span style="color:rgb(25,23,124)">%sum.0</span>)
<span style="color:rgb(0,128,0);font-weight:bold">ret</span> <span style="color:rgb(0,128,0);font-weight:bold">i32</span> <span style="color:rgb(102,102,102)">0</span>
}
<span style="color:rgb(0,128,0);font-weight:bold">declare</span> <span style="color:rgb(0,128,0);font-weight:bold">i32</span> <span style="color:rgb(25,23,124)">@printf</span>(<span style="color:rgb(0,128,0);font-weight:bold">i8</span>*, ...) <span style="border:1px solid rgb(255,0,0)">#</span></pre></div></div><div>
Do I need to run some passes other than mem2reg to obtain the desired result?</div><div><br></div><div>Is there a better way of finding reduction variables in LLVM?</div><div><br></div><div><br></div><div>Thank you.</div><div><br></div><div><br></div><div><br></div><div>Regards,</div><div>Malhar</div><div>
<br></div><div>
<br></div></div><div hspace="streak-pt-mark" style="max-height:1px"><img alt="" style="width:0px;max-height:0px;overflow:hidden" src="https://mailfoogae.appspot.com/t?sender=aY3MxM2IxMDMxQGlpdGguYWMuaW4%3D&type=zerocontent&guid=19168190-8381-4c46-b78c-e805d942e2eb"><font color="#ffffff" size="1">ᐧ</font></div>