LoopIdiom regression: ctlz no longer recognized

[davidbolvansky]

Bugzilla Link	51722
Version	trunk
OS	Linux
Blocks	#50580 #51489
CC	@topperc,@LebedevRI,@RKSimon,@nikic,@rotateright,@tstellar

Extended Description

unsigned long long FIO_highbit64(unsigned long long v)
{
unsigned count = 0;
v >>= 1;
while (v) { v >>= 1; count++; }
return count;
}

Since LLVM 13, we lost recognized "@llvm.ctlz.i64".

https://godbolt.org/z/nodKdfab4

[davidbolvansky]

Looks like before LLVM 13, this was input for loop idiom

define dso_local i64 @​_Z13FIO_highbit64y(i64 %0) local_unnamed_addr #​0 {
br label %2

2: ; preds = %2, %1
%3 = phi i64 [ %0, %1 ], [ %5, %2 ]
%4 = phi i32 [ 0, %1 ], [ %7, %2 ]
%5 = lshr i64 %3, 1
%6 = icmp eq i64 %5, 0
%7 = add i32 %4, 1
br i1 %6, label %8, label %2

8: ; preds = %2
%9 = phi i32 [ %4, %2 ]
%10 = zext i32 %9 to i64
ret i64 %10
}

And this is fine: https://godbolt.org/z/cf1of6eY9

IR in LLVM 13 +:

define dso_local i64 @​_Z13FIO_highbit64y(i64 %0) local_unnamed_addr #​0 {
%2 = icmp ult i64 %0, 2
br i1 %2, label %12, label %3

3: ; preds = %1
br label %4

4: ; preds = %3, %4
%5 = phi i32 [ %8, %4 ], [ 0, %3 ]
%6 = phi i64 [ %7, %4 ], [ %0, %3 ]
%7 = lshr i64 %6, 1
%8 = add i32 %5, 1
%9 = icmp ult i64 %6, 4
br i1 %9, label %10, label %4, !llvm.loop !​3

10: ; preds = %4
%11 = phi i32 [ %8, %4 ]
br label %12

12: ; preds = %10, %1
%13 = phi i32 [ 0, %1 ], [ %11, %10 ]
%14 = zext i32 %13 to i64
ret i64 %14
}

[davidbolvansky]

Even very simple pattern is lost in LLVM 13:

unsigned r1(unsigned v)
{
unsigned r = 0;

while (v >>= 1)
    r++;

return r;

}

https://godbolt.org/z/39r8437ds

[davidbolvansky]

Plus one more:

static inline unsigned int_log2_rec(unsigned x)
{
return x == 0 ? 0 : int_log2_rec(x >> 1) + 1;
}

unsigned int_log2(unsigned x)
{
return x == 0 ? 0 : int_log2_rec(x) - 1;
}

[llvmbot]

Regarding r1 loop since LLVM 13 LIR doesn't obtain 'shifting until zero' idiom from previous passes and transformation fails:

define i32 @​r1_llvm_13_nok(i32 %0) #​0 {
%2 = icmp ult i32 %0, 2
br i1 %2, label %12, label %3

3: ; preds = %1
br label %4

4: ; preds = %3, %4
%5 = phi i32 [ %8, %4 ], [ 0, %3 ]
%6 = phi i32 [ %7, %4 ], [ %0, %3 ]
%7 = lshr i32 %6, 1
%8 = add i32 %5, 1
%9 = icmp ult i32 %6, 4
br i1 %9, label %10, label %4

10: ; preds = %4
%11 = phi i32 [ %8, %4 ]
br label %12

12: ; preds = %10, %1
%13 = phi i32 [ 0, %1 ], [ %11, %10 ]
ret i32 %13
}

That's how properly recognized idiom should look like (shift + icmp 0) to poke LIR:

define i32 @​r1_llvm_12_ok(i32 %0) #​0 {
br label %2

2: ; preds = %2, %1
%3 = phi i32 [ %0, %1 ], [ %5, %2 ]
%4 = phi i32 [ 0, %1 ], [ %7, %2 ]
%5 = lshr i32 %3, 1
%6 = icmp eq i32 %5, 0
%7 = add i32 %4, 1
br i1 %6, label %8, label %2

8: ; preds = %2
%9 = phi i32 [ %4, %2 ]
ret i32 %9
}

[davidbolvansky]

Root issue found. InstCombine's new tranformation:

; ModuleID = ''
source_filename = ""
target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"

; Function Attrs: mustprogress nounwind uwtable
define dso_local i64 @​_Z13FIO_highbit64y(i64 %0) local_unnamed_addr #​0 {
%2 = lshr i64 %0, 1
br label %3

3: ; preds = %7, %1
%4 = phi i64 [ %2, %1 ], [ %8, %7 ]
%5 = phi i32 [ 0, %1 ], [ %9, %7 ]
%6 = icmp ne i64 %4, 0
br i1 %6, label %7, label %10

7: ; preds = %3
%8 = lshr i64 %4, 1
%9 = add i32 %5, 1
br label %3, !llvm.loop !​3

10: ; preds = %3
%11 = zext i32 %5 to i64
ret i64 %11
}

attributes #​0 = { mustprogress nounwind uwtable "frame-pointer"="none" "min-legal-vector-width"="0" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" }

!llvm.module.flags = !{#0, !​1}
!llvm.ident = !{#2}

!​0 = !{i32 1, !"wchar_size", i32 4}
!​1 = !{i32 7, !"uwtable", i32 1}
!​2 = !{!"clang version 14.0.0 (https://github.com/llvm/llvm-project.git fa69ccd)"}
!​3 = distinct !{#3, !​4, !​5}
!​4 = !{!"llvm.loop.mustprogress"}
!​5 = !{!"llvm.loop.unroll.disable"}

LLVM 12:
define dso_local i64 @​_Z13FIO_highbit64y(i64 %0) local_unnamed_addr #​0 {
br label %2

2: ; preds = %5, %1
%.in = phi i64 [ %0, %1 ], [ %4, %5 ]
%3 = phi i32 [ 0, %1 ], [ %6, %5 ]
%4 = lshr i64 %.in, 1
%.not = icmp eq i64 %4, 0 *****************
br i1 %.not, label %7, label %5

5: ; preds = %2
%6 = add i32 %3, 1
br label %2, !llvm.loop !​3

7: ; preds = %2
%8 = zext i32 %3 to i64
ret i64 %8
}

LLVM 13+:
define dso_local i64 @​_Z13FIO_highbit64y(i64 %0) local_unnamed_addr #​0 {
br label %2

2: ; preds = %4, %1
%.in = phi i64 [ %0, %1 ], [ %5, %4 ]
%3 = phi i32 [ 0, %1 ], [ %6, %4 ] *****************
%.not = icmp ult i64 %.in, 2
br i1 %.not, label %7, label %4

4: ; preds = %2
%5 = lshr i64 %.in, 1
%6 = add i32 %3, 1
br label %2, !llvm.loop !​3

7: ; preds = %2
%8 = zext i32 %3 to i64
ret i64 %8
}

@​spatel?

[nikic]

I think this is due to 9a9421a?

I don't think there's anything wrong with the fold, LIR just needs to be adjusted for the new canonical pattern.

[davidbolvansky]

For this case from comment #​2

unsigned int_log2(unsigned x)
{
return x == 0 ? 0 : int_log2_rec(x) - 1;
}

checking for %9 = icmp ult i32 %5, 2 instead of %9 = icmp eq i32 %7, 0 would work.

But for motivating case, that will be worse, as we have:

%2 = icmp ult i64 %0, 2
br i1 %2, label %11, label %3

3: ; preds = %1, %3
%4 = phi i32 [ %7, %3 ], [ 0, %1 ]
%5 = phi i64 [ %6, %3 ], [ %0, %1 ]
%6 = lshr i64 %5, 1
%7 = add nuw nsw i32 %4, 1
%8 = icmp ult i64 %5, 4

[davidbolvansky]

Sadly, test/Transforms/PhaseOrdering/X86/ctlz-loop.ll (as we see that this test file was changed by your patch) would catch this (broken idiom detection), but this test is very useless now:

; This test ensures we are able to optimize the following loop to an llvm.abs
; followed by an llvm.ctlz.
; FIXME: LoopIdiom recongize is not forming llvm.ctlz.

[davidbolvansky]

@​nikic: any plans to implement simple fix to make basic case working as since your patch “Reapply [InstCombine] Fold multiuse shr eq zero” we have this regression.. ?

[tstellar]

mentioned in issue #51489

[tstellar]

The deadline for requesting fixes for the release has passed. This bug is being removed from the LLVM 13.0.1 release milestone. If you have a fix or think this bug is important enough to block the release, please explain why in a comment and add the bug back to the LLVM 13.0.1 release milestone.