<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
</head>
<body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class="">
<div>The relevant transformation appears to be in SimplifyUsingDistributiveLaws. When trying to optimize an add, it treats left shifts as multiplies, so (X << C) + X becomes (X * (1<<C)) + (X * 1) which factorizes to X * ((1 << C) + 1).</div>
<div><br class="">
</div>
<div>In Alive, this would be:</div>
<div><br class="">
</div>
<div>Name: Factor</div>
<div>
<div>%y = shl %X, C</div>
<div>%r = add %y, %X</div>
<div>=></div>
<div>%r = mul %X, (1<<C)+1</div>
<div><br class="">
</div>
<div>The two variations of the proposed optimization are,</div>
<div><br class="">
</div>
<div>
<div>Name: Plus</div>
<div>Pre: isPowerOf2(C+1)</div>
<div>%r = mul %X, C</div>
<div>=></div>
<div>%y = shl %X, log2(C+1)</div>
<div>%r = sub %y, %X</div>
<div><br class="">
</div>
<div>Name: Minus</div>
<div>Pre: isPowerOf2(C-1)</div>
<div>%r = mul %X, C</div>
<div>=></div>
<div>%y = shl %X, log2(C-1)</div>
<div>%r = add %y, %X</div>
<div class=""><br class="">
</div>
<div class="">The Alive-Loops tool confirms that these can cause InstCombine to loop.</div>
<div class=""><br class="">
</div>
<div class="">Specifically, it finds this transformation, which applies Factor and then Plus:</div>
<div class=""><br class="">
</div>
Name: (Factor;Plus)<br class="">
Pre: isPowerOf2((((1 << C) + 1) - 1))<br class="">
%y = shl %X, C<br class="">
%r = add %y, %X<br class="">
=><br class="">
%y1 = shl %X, log2((((1 << C) + 1) - 1))<br class="">
%r = add %y1, %X<br class="">
<br class="">
<div class="">Note that its precondition is trivial and its source and target code are identical (aside from renaming). Barring interference from other transformations, this will cause InstCombine to apply this transformation endlessly.</div>
<div class=""><br class="">
</div>
<div class="">There’s a more complete discussion of InstCombine non-termination in the paper “Termination checking for LLVM peephole optimizations” (ICSE 2016), by Santosh Nagarakatte and me.</div>
<div class=""><br class="">
</div>
<div class=""> <a href="https://www.cs.rutgers.edu/~sn349/papers/icse2016-alive-loops.pdf" class="">
https://www.cs.rutgers.edu/~sn349/papers/icse2016-alive-loops.pdf</a></div>
<div class=""><br class="">
</div>
<div class="">The prototype can be downloaded from</div>
<div class=""><br class="">
</div>
<div class=""> <a href="https://github.com/rutgers-apl/alive-loops" class="">https://github.com/rutgers-apl/alive-loops</a></div>
</div>
</div>
<div><br class="">
On Sep 13, 2017, at 1:18 PM, Craig Topper via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" class="">llvm-dev@lists.llvm.org</a>> wrote:<br class="">
<blockquote type="cite" class=""><br class="Apple-interchange-newline">
<div class="">
<div dir="ltr" class="">There is in fact a transform out there somewhere that reverses yours.
<div class=""><br class="">
</div>
<div class="">
<div class="">define i64 @foo(i64 %a) {</div>
<div class=""> %b = shl i64 %a, 5</div>
<div class=""> %c = add i64 %b, %a</div>
<div class=""> ret i64 %c</div>
<div class="">}</div>
</div>
<div class=""><br class="">
</div>
<div class="">becomes</div>
<div class=""><br class="">
</div>
<div class="">
<p class="gmail-p1"><span class="gmail-s1">define i64 @foo(i64 %a) {</span></p>
<p class="gmail-p1"><span class="gmail-Apple-converted-space"> </span>%c = mul i64 %a, 33</p>
<p class="gmail-p1"><span class="gmail-s1"><span class="gmail-Apple-converted-space">
</span>ret i64 %c</span></p>
<p class="gmail-p1"><span class="gmail-s1">}</span></p>
</div>
</div>
<div class="gmail_extra"><br clear="all" class="">
<div class="">
<div class="gmail_signature" data-smartmail="gmail_signature">~Craig</div>
</div>
<br class="">
<div class="gmail_quote">On Wed, Sep 13, 2017 at 10:11 AM, Craig Topper <span dir="ltr" class="">
<<a href="mailto:craig.topper@gmail.com" target="_blank" class="">craig.topper@gmail.com</a>></span> wrote:<br class="">
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div dir="ltr" class="">Your code seems fine. InstCombine can infinite loop if some other transform is reversing your transform. Can you send the whole patch and a test case?</div>
<div class="gmail_extra"><span class="HOEnZb"><font color="#888888" class=""><br clear="all" class="">
<div class="">
<div class="m_7470635396692210463gmail_signature" data-smartmail="gmail_signature">
~Craig</div>
</div>
</font></span>
<div class="">
<div class="h5"><br class="">
<div class="gmail_quote">On Wed, Sep 13, 2017 at 10:01 AM, Haidl, Michael via llvm-dev
<span dir="ltr" class=""><<a href="mailto:llvm-dev@lists.llvm.org" target="_blank" class="">llvm-dev@lists.llvm.org</a>></span> wrote:<br class="">
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Hi,<br class="">
<br class="">
I am working on PR34474 and try to add a new optimization to<br class="">
InstCombine. Like in other parts of the visitMul function I add a Shl<br class="">
through the IR builder and create a new BinaryOp which I return from<br class="">
visitMul. If I understand correctly the new BinaryOp returned from<br class="">
visitMul should replace the original Instruction in the Worklist.<br class="">
However, I end up in an infinite loop and the Instruction I try to<br class="">
replace gets scheduled again and again. What is wrong in my code?<br class="">
<br class="">
// Replace X * (2^C+/-1) with (X << C) -/+ X<br class="">
APInt Plus1 = *IVal + 1;<br class="">
APInt Minus1 = *IVal - 1;<br class="">
int isPow2 = Plus1.isPowerOf2() ? 1 : Minus1.isPowerOf2() ? -1 : 0;<br class="">
<br class="">
if (isPow2) {<br class="">
APInt &Pow2 = isPow2 > 0 ? Plus1 : Minus1;<br class="">
Value *Shl = Builder.CreateShl(Op0, Pow2.logBase2());<br class="">
return BinaryOperator::Create(isPow2 > 0 ? BinaryOperator::Sub :<br class="">
BinaryOperator::Add, Shl, Op0);<br class="">
}<br class="">
<br class="">
Thanks,<br class="">
Michael<br class="">
______________________________<wbr class="">_________________<br class="">
LLVM Developers mailing list<br class="">
<a href="mailto:llvm-dev@lists.llvm.org" target="_blank" class="">llvm-dev@lists.llvm.org</a><br class="">
<a href="https://na01.safelinks.protection.outlook.com/?url=http%3A%2F%2Flists.llvm.org%2Fcgi-bin%2Fmailman%2Flistinfo%2Fllvm-dev&data=02%7C01%7Cdavemm%40cs.rutgers.edu%7C594c390a062c47fb24ca08d4facb7f42%7Cb92d2b234d35447093ff69aca6632ffe%7C1%7C0%7C636409199301439466&sdata=liiyqDyCdRjljCAcZ0NhC3zi%2BvbdzN0E5%2BZ2iY4QYPM%3D&reserved=0" rel="noreferrer" target="_blank" class="">http://lists.llvm.org/cgi-bin/<wbr class="">mailman/listinfo/llvm-dev</a><br class="">
</blockquote>
</div>
<br class="">
</div>
</div>
</div>
</blockquote>
</div>
<br class="">
</div>
_______________________________________________<br class="">
LLVM Developers mailing list<br class="">
<a href="mailto:llvm-dev@lists.llvm.org" class="">llvm-dev@lists.llvm.org</a><br class="">
https://na01.safelinks.protection.outlook.com/?url=http%3A%2F%2Flists.llvm.org%2Fcgi-bin%2Fmailman%2Flistinfo%2Fllvm-dev&data=02%7C01%7Cdavemm%40cs.rutgers.edu%7C594c390a062c47fb24ca08d4facb7f42%7Cb92d2b234d35447093ff69aca6632ffe%7C1%7C0%7C636409199301439466&sdata=liiyqDyCdRjljCAcZ0NhC3zi%2BvbdzN0E5%2BZ2iY4QYPM%3D&reserved=0<br class="">
</div>
</blockquote>
</div>
<br class="">
</body>
</html>