[llvm-dev] How to add optimizations to InstCombine correctly?

[David Menendez via llvm-dev]

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).

In Alive, this would be:

Name: Factor
%y = shl %X, C
%r = add %y, %X
=>
%r = mul %X, (1<<C)+1

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:

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

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.

    https://www.cs.rutgers.edu/~sn349/papers/icse2016-alive-loops.pdf

The prototype can be downloaded from

    https://github.com/rutgers-apl/alive-loops

On Sep 13, 2017, at 1:18 PM, Craig Topper via llvm-dev <llvm-dev at lists.llvm.org<mailto:llvm-dev at 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, %a
  ret 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 at gmail.com<mailto:craig.topper at 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 at lists.llvm.org<mailto:llvm-dev at 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 at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev<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>


_______________________________________________
LLVM Developers mailing list
llvm-dev at lists.llvm.org<mailto:llvm-dev at 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

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170915/40105568/attachment.html>