(original) (raw)
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<
On Sep 13, 2017, at 1:18 PM, Craig Topper via llvm-dev <llvm-dev@lists.llvm.org> wrote:
In Alive, this would be:
Name: Factor
%y = shl %X, C
%r = add %y, %X
=>
%r = mul %X, (1<
Name: (Factor;Plus)
Pre: isPowerOf2((((1 << C) + 1) - 1))
%y = shl %X, C
%r = add %y, %X
\=>
%y1 = shl %X, log2((((1 << C) + 1) - 1))
%r = add %y1, %X
The two variations of the proposed optimization are,
Name: Plus
Pre: isPowerOf2(C+1)
%r = mul %X, C
=>
%y = shl %X, log2(C+1)
%r = sub %y, %X
Name: Minus
Pre: isPowerOf2(C-1)
%r = mul %X, C
=>
%y = shl %X, log2(C-1)
%r = add %y, %X
The Alive-Loops tool confirms that these can cause InstCombine to loop.
Specifically, it finds this transformation, which applies Factor and then Plus:
Pre: isPowerOf2((((1 << C) + 1) - 1))
%y = shl %X, C
%r = add %y, %X
\=>
%y1 = shl %X, log2((((1 << C) + 1) - 1))
%r = add %y1, %X
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.
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.
The prototype can be downloaded from
On Sep 13, 2017, at 1:18 PM, Craig Topper via llvm-dev <llvm-dev@lists.llvm.org> wrote:
There is in fact a transform out there somewhere that reverses yours.
define i64 @foo(i64 %a) {%b = shl i64 %a, 5%c = add i64 %b, %aret i64 %c}
becomes
define i64 @foo(i64 %a) {
%c = mul i64 %a, 33
ret i64 %c
}
\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_
\~Craig
On Wed, Sep 13, 2017 at 10:11 AM, Craig Topper <craig.topper@gmail.com> wrote:
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?
\~Craig
On Wed, Sep 13, 2017 at 10:01 AM, Haidl, Michael via llvm-dev <llvm-dev@lists.llvm.org> wrote:
Hi,
I am working on PR34474 and try to add a new optimization to
InstCombine. Like in other parts of the visitMul function I add a Shl
through the IR builder and create a new BinaryOp which I return from
visitMul. If I understand correctly the new BinaryOp returned from
visitMul should replace the original Instruction in the Worklist.
However, I end up in an infinite loop and the Instruction I try to
replace gets scheduled again and again. What is wrong in my code?
// Replace X \* (2^C+/-1) with (X << C) -/+ X
APInt Plus1 = \*IVal + 1;
APInt Minus1 = \*IVal - 1;
int isPow2 = Plus1.isPowerOf2() ? 1 : Minus1.isPowerOf2() ? -1 : 0;
if (isPow2) {
APInt &Pow2 = isPow2 > 0 ? Plus1 : Minus1;
Value \*Shl = Builder.CreateShl(Op0, Pow2.logBase2());
return BinaryOperator::Create(isPow2 > 0 ? BinaryOperator::Sub :
BinaryOperator::Add, Shl, Op0);
}
Thanks,
Michael
\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_
LLVM Developers mailing list
llvm-dev@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
LLVM Developers mailing list
llvm-dev@lists.llvm.org
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