<div dir="ltr"><div class="gmail_quote"><div dir="ltr" style="background-color:rgb(255,255,255)"><div dir="ltr" style="background-color:rgb(255,255,255)"><div style=""><div style=""><div style=""><font color="#000000" face="Calibri, Arial, Helvetica, sans-serif"><span style="font-size:16px">​Hi,</span></font></div><div style=""><font color="#000000" face="Calibri, Arial, Helvetica, sans-serif"><span style="font-size:16px"><br></span></font></div><div style=""><font color="#000000" face="Calibri, Arial, Helvetica, sans-serif"><span style="font-size:16px">Would you be able to kindly check and assist with the IndVarSimplify / SCEV problem I got in the latest LLVM, please?</span></font></div><div style=""><font color="#000000" face="Calibri, Arial, Helvetica, sans-serif"><span style="font-size:16px"><br></span></font></div><div style=""><font color="#000000" face="Calibri, Arial, Helvetica, sans-serif"><span style="font-size:16px">Sometimes IndVarSimplify may not eliminate narrow IV's when there actually exists such a possibility. This may affect other LLVM passes and result in inefficient code. The reproducing test 'indvar_test.cpp' is attached.</span></font></div><div style=""><font color="#000000" face="Calibri, Arial, Helvetica, sans-serif"><span style="font-size:16px"><br></span></font></div><div style=""><font color="#000000" face="Calibri, Arial, Helvetica, sans-serif"><span style="font-size:16px">The problem is with the second 'for' loop that accesses array elements with different indexes on each iteration.</span></font></div><div style=""><font color="#000000" face="Calibri, Arial, Helvetica, sans-serif"><span style="font-size:16px">The latest LLVM fails to reuse array element values from previous iterations and generates an unnecessary GEP. The generated IR is shown in the attached file '<a href="http://bad.ir">bad.ir</a>'.</span></font></div><div style=""><font color="#000000" face="Calibri, Arial, Helvetica, sans-serif"><span style="font-size:16px">This happens because IndVarSimplify fails to eliminate '%idxprom7' and '%idxprom10'. </span></font></div><div style=""><font color="#000000" face="Calibri, Arial, Helvetica, sans-serif"><span style="font-size:16px"><br></span></font></div><div style=""><font color="#000000" face="Calibri, Arial, Helvetica, sans-serif"><span style="font-size:16px">The clang command line we use:</span></font></div><div style=""><font color="#000000" face="Calibri, Arial, Helvetica, sans-serif"><span style="font-size:16px">    clang++ -mllvm -debug -S -emit-llvm -O3 --target=aarch64-linux-elf indvar_test.cpp -o <a href="http://bad.ir">bad.ir</a></span></font></div><div style=""><font color="#000000" face="Calibri, Arial, Helvetica, sans-serif"><span style="font-size:16px"><br></span></font></div><div style=""><font color="#000000" face="Calibri, Arial, Helvetica, sans-serif"><span style="font-size:16px">I found that 'WidenIV::widenIVUse' (IndVarSimplify.cpp) may fail to widen narrow IV uses.</span></font></div><div style=""><font color="#000000" face="Calibri, Arial, Helvetica, sans-serif"><span style="font-size:16px"><br></span></font></div><div style=""><font color="#000000" face="Calibri, Arial, Helvetica, sans-serif"><span style="font-size:16px">When the function gets a NarrowUse such as '{(-2 + %inc.lcssa),+,1}<nsw><%for.body3>', it first tries to get a wide recurrence for it via the 'getWideRecurrence' call.</span></font></div><div style=""><font color="#000000" face="Calibri, Arial, Helvetica, sans-serif"><span style="font-size:16px">'getWideRecurrence' returns recurrence like this: '{(sext i32 (-2 + %inc.lcssa) to i64),+,1}<nsw><%for.body3>', which is fine by itself.</span></font></div><div style=""><font color="#000000" face="Calibri, Arial, Helvetica, sans-serif"><span style="font-size:16px"><br></span></font></div><div style=""><font color="#000000" face="Calibri, Arial, Helvetica, sans-serif"><span style="font-size:16px">Then a wide use operation is generated by 'cloneIVUser'. The generated wide use is evaluated to '{(-2 + (sext i32 %inc.lcssa to i64))<nsw>,+,1}<nsw><%for.body3>', which is different from 'getWideRecurrence' result (please note the position of -2). 'cloneIVUser' sees the difference and returns nullptr.</span></font></div><div style=""><font color="#000000" face="Calibri, Arial, Helvetica, sans-serif"><span style="font-size:16px"><br></span></font></div><div style=""><font color="#000000" face="Calibri, Arial, Helvetica, sans-serif"><span style="font-size:16px">I attached a test patch 'indvar.patch', which is not correct for all cases, but it fixes the specific 'indvar_test.cpp' scenario to demonstrate the efficient code that could have been generated (<a href="http://good.ir">good.ir</a>).</span></font></div><div style=""><font color="#000000" face="Calibri, Arial, Helvetica, sans-serif"><span style="font-size:16px">It transforms expressions like '(sext i32 (-2 + %inc.lcssa) to i64)' into '-2 + (sext i32 %inc.lcssa to i64)' making expressions comparison succeed. IV's are successfully eliminated, which can be seen in the '-mllvm -debug' output.</span></font></div><div style=""><font color="#000000" face="Calibri, Arial, Helvetica, sans-serif"><span style="font-size:16px"><br></span></font></div><div style=""><font color="#000000" face="Calibri, Arial, Helvetica, sans-serif"><span style="font-size:16px">The problem with the patch is that it uses wrong extend logic for the '-2' operand. It must be sign or zero extended depending on the context.</span></font></div><div style=""><font color="#000000" face="Calibri, Arial, Helvetica, sans-serif"><span style="font-size:16px"><br></span></font></div><div style=""><font color="#000000" face="Calibri, Arial, Helvetica, sans-serif"><span style="font-size:16px">Could you check and confirm the problem, and give any hints how this might be fixed properly, please?</span></font></div><div style=""><font color="#000000" face="Calibri, Arial, Helvetica, sans-serif"><span style="font-size:16px"><br></span></font></div><div style=""><font color="#000000" face="Calibri, Arial, Helvetica, sans-serif"><span style="font-size:16px">Thank you.</span></font></div></div></div></div></div></div></div>