[RFC] Instcombine pass goes into a loop

Hi,

I came across a corner case in instcombine pass in LLVM which creates an infinite loop and the compilation hangs. I was able to get a reduced test case using C-reduce for this scenario.

class a {
public:
a();
} extern b;
extern char c;
static long long d = (long)b;
a e;
void f() {
long h = d - (long)c;
for (long g = 0; g < h; ++g)
a();
}

Below is the summary of the problem.

After certain iterations in instcombine the IR snapshot formed looks like below:

%0 = call i32 @llvm.smax.i32(i32 Val1, i32 1)
%1 = call i32 @llvm.smax.i32(i32 Val2, i32 1)
%minmaxop = select i1 %.b, i32 Val1, i32 Val2
%2 = select i1 %.b, i32 %0, i32 %1
br label %for.body

Here Val1 and Val2 are abstracted away for better understanding.
At this state, the pass tries to reduce the select operation in order to do the transformation select C, (op X, Y), (op X, Z)) → (op X, (select C, Y, Z). Since “op” is a call instruction, the transformation looks like below. This transformation is done by InstCombinerImpl::visitSelectInst(…).

%minmaxop = select i1 %.b, i32 Val1, i32 Val2
%smax = call i32 @llvm.smax.i32(i32 %minmaxop, i32 1)
br label %for.body

At this instance, the call is folded back into select operation.
InstCombinerImpl::visitCallInst(…), checks if the arg1 is immediateConstant (here, i32 1) and calls InstCombinerImpl::FoldOpIntoSelect(…) to fold the intrinsic call into select. Following the transformation two new call instructions are created along with the select instruction in the process; and this loop repeats.

%0 = call i32 @llvm.smax.i32(i32 Val1, i32 1)
%1 = call i32 @llvm.smax.i32(i32 Val2, i32 1)
%minmaxop = select i1 %.b, i32 Val1, i32 Val2
%2 = select i1 %.b, i32 %0, i32 %1
br label %for.body

As for a solution, breaking out of the loop during the transformation from the call to the select instruction seems reasonable. If my understanding is correct, this transformation is costly since we are replacing an intrinsic call with two calls and a select.

Or, we could break up the loop by keeping a threshold in the InstCombinerImpl::run() loop where it loops indefinitely.

Please suggest :slight_smile:

Thanks,
Santanu

Hello!
Im quite intereted in contributing to llvm, and this sounds pretty cool. If someone proposes a solution, and if this isn’t something that should be done in a hurry, I’m setting up my development machine next Monday (problems with my disk), I’d be happy to implement whatever is written here. Does this sound reasonable?

Thanks for sharing the issue and the detailed analysis! Please go for fixing the issue if you would like. Just make sure the issue isn’t already fixed on the latest version of main when you start.

Thank you! Will do

Hi Florian,

Thanks for the response.
I will push a patch for this bug.

Hi ghostway,
I have been working on the bug for some time. Let me issue a fix this time :slight_smile:

Sure, will find another thing to work on, thanks for saying :slight_smile:

Please feel free to take a look at the bug tracker. There are many open issues, e.g. crashes in LLVM: Issues · llvm/llvm-project · GitHub