[LICM] freeze instruction inhibits hoistng of invariants

[xortator]

Godbolt example:
https://godbolt.org/z/bTGT3Mdxn

opt -passes=licm -debug-only=licm -S

define void @test_01(i8 addrspace(1)* addrspace(1)* %arg, i32 %arg2) {
bb:
  %tmp103 = load atomic i8 addrspace(1)*, i8 addrspace(1)* addrspace(1)* %arg unordered, align 8, !dereferenceable_or_null !5, !align !6
  %tmp117 = icmp eq i8 addrspace(1)* %tmp103, null
  %tmp118 = getelementptr inbounds i8, i8 addrspace(1)* %tmp103, i64 8
  %tmp119 = bitcast i8 addrspace(1)* %tmp118 to i32 addrspace(1)*
  br i1 %tmp117, label %bb122, label %bb149

bb122:                                            ; preds = %bb
  ret void

bb149:                                            ; preds = %bb
  br label %bb150

bb150:                                            ; preds = %bb150, %bb149
  %tmp151 = phi i32 [ 0, %bb149 ], [ %tmp163, %bb150 ]
  %tmp152 = icmp ult i32 %tmp151, %arg2
  call void (i1, ...) @llvm.experimental.guard(i1 %tmp152, i32 12) [ "deopt"() ]
  %tmp157 = load atomic i32, i32 addrspace(1)* %tmp119 unordered, align 8
  %tmp158 = icmp ult i32 %tmp151, %tmp157
  call void (i1, ...) @llvm.experimental.guard(i1 %tmp158, i32 12) [ "deopt"() ]
  %tmp163 = add i32 %tmp151, 1
  br label %bb150
}

define void @test_02(i8 addrspace(1)* addrspace(1)* %arg, i32 %arg2) {
bb:
  %tmp103 = load atomic i8 addrspace(1)*, i8 addrspace(1)* addrspace(1)* %arg unordered, align 8, !dereferenceable_or_null !5, !align !6
  %tmp117 = icmp eq i8 addrspace(1)* %tmp103, null
  %tmp118 = getelementptr inbounds i8, i8 addrspace(1)* %tmp103, i64 8
  %tmp119 = bitcast i8 addrspace(1)* %tmp118 to i32 addrspace(1)*
  %freeze = freeze i1 %tmp117
  br i1 %freeze, label %bb122, label %bb149

bb122:                                            ; preds = %bb
  ret void

bb149:                                            ; preds = %bb
  br label %bb150

bb150:                                            ; preds = %bb150, %bb149
  %tmp151 = phi i32 [ 0, %bb149 ], [ %tmp163, %bb150 ]
  %tmp152 = icmp ult i32 %tmp151, %arg2
  call void (i1, ...) @llvm.experimental.guard(i1 %tmp152, i32 12) [ "deopt"() ]
  %tmp157 = load atomic i32, i32 addrspace(1)* %tmp119 unordered, align 8
  %tmp158 = icmp ult i32 %tmp151, %tmp157
  call void (i1, ...) @llvm.experimental.guard(i1 %tmp158, i32 12) [ "deopt"() ]
  %tmp163 = add i32 %tmp151, 1
  br label %bb150
}

; Function Attrs: nocallback nofree nosync willreturn
declare void @llvm.experimental.guard(i1, ...) #2

!5 = !{i64 16}
!6 = !{i64 8}

Output:

LICM hoisting to bb149:   %tmp157 = load atomic i32, i32 addrspace(1)* %tmp119 unordered, align 8
; ModuleID = 'reduced.ll'
source_filename = "reduced.ll"

define void @test_01(i8 addrspace(1)* addrspace(1)* %arg, i32 %arg2) {
bb:
  %tmp103 = load atomic i8 addrspace(1)*, i8 addrspace(1)* addrspace(1)* %arg unordered, align 8, !dereferenceable_or_null !0, !align !1
  %tmp117 = icmp eq i8 addrspace(1)* %tmp103, null
  %tmp118 = getelementptr inbounds i8, i8 addrspace(1)* %tmp103, i64 8
  %tmp119 = bitcast i8 addrspace(1)* %tmp118 to i32 addrspace(1)*
  br i1 %tmp117, label %bb122, label %bb149

bb122:                                            ; preds = %bb
  ret void

bb149:                                            ; preds = %bb
  %tmp157 = load atomic i32, i32 addrspace(1)* %tmp119 unordered, align 8
  br label %bb150

bb150:                                            ; preds = %bb150, %bb149
  %tmp151 = phi i32 [ 0, %bb149 ], [ %tmp163, %bb150 ]
  %tmp152 = icmp ult i32 %tmp151, %arg2
  call void (i1, ...) @llvm.experimental.guard(i1 %tmp152, i32 12) [ "deopt"() ]
  %tmp158 = icmp ult i32 %tmp151, %tmp157
  call void (i1, ...) @llvm.experimental.guard(i1 %tmp158, i32 12) [ "deopt"() ]
  %tmp163 = add i32 %tmp151, 1
  br label %bb150
}

define void @test_02(i8 addrspace(1)* addrspace(1)* %arg, i32 %arg2) {
bb:
  %tmp103 = load atomic i8 addrspace(1)*, i8 addrspace(1)* addrspace(1)* %arg unordered, align 8, !dereferenceable_or_null !0, !align !1
  %tmp117 = icmp eq i8 addrspace(1)* %tmp103, null
  %tmp118 = getelementptr inbounds i8, i8 addrspace(1)* %tmp103, i64 8
  %tmp119 = bitcast i8 addrspace(1)* %tmp118 to i32 addrspace(1)*
  %freeze = freeze i1 %tmp117
  br i1 %freeze, label %bb122, label %bb149

bb122:                                            ; preds = %bb
  ret void

bb149:                                            ; preds = %bb
  br label %bb150

bb150:                                            ; preds = %bb150, %bb149
  %tmp151 = phi i32 [ 0, %bb149 ], [ %tmp163, %bb150 ]
  %tmp152 = icmp ult i32 %tmp151, %arg2
  call void (i1, ...) @llvm.experimental.guard(i1 %tmp152, i32 12) [ "deopt"() ]
  %tmp157 = load atomic i32, i32 addrspace(1)* %tmp119 unordered, align 8
  %tmp158 = icmp ult i32 %tmp151, %tmp157
  call void (i1, ...) @llvm.experimental.guard(i1 %tmp158, i32 12) [ "deopt"() ]
  %tmp163 = add i32 %tmp151, 1
  br label %bb150
}

; Function Attrs: nocallback nofree nosync willreturn
declare void @llvm.experimental.guard(i1, ...) #0

attributes #0 = { nocallback nofree nosync willreturn }

!0 = !{i64 16}
!1 = !{i64 8}

The only difference between test_01 and test_02 is freeze on loop-invariant condition. In former case invariant load gets hoisted, while in presence of freeze it doesn't. For us, it causes massive negative performance impact after freeze instructions started generated with -freeze-loop-unswitch-cond set to true.

[xortator]

I think we have tons of optimizations that work with branch conditions and they don't expect freeze there. My first guesses would be IndVars, IRCE, Loop Predication and maybe others. Going to each and every place and teaching them that freeze is a noop might be expensive. Can we think of some relatively easy way to handle that?

[xortator]

@fhahn @nikic WDYT? To me, arbitrary insertion of freeze to conditions just looks unsafe from performance perspective.

[xortator]

Just thinking more of it, we may have a demon optimizer pass inserting freeze for each instruction and RAUWing it with it, and this should break each and every optimization we have.

[nikic]

I think there is three issues in this example:

1. You are running LICM on non-canonical IR. Normally the freeze should be on the load, not the icmp, see https://godbolt.org/z/396dMzPef. There may be a phase ordering problem.
2. In the canonical form, isDereferenceableAndAlignedPointer() still doesn't recognize that the pointer is dereferenceable, because the != null check is on the frozen pointer, but we call isKnownNonZero() on the unfrozen pointer. This shouldn't be hard to fix.
3. I think we may make an argument that the result of a !dereferenceable_or_null load cannot be poison, in which case the freeze instruction and this entire problem would go away. This is because poison is not dereferenceable.

I think 3 is probably the best way to get this particular case fixed. It requires that !dereferenceable_or_null violation is immediate UB, but I believe that this is a reasonable assumption given that it is also immediate UB for the attribute variant.

[nikic]

I've put up https://reviews.llvm.org/D126296.

[aqjune]

It would be helpful if your frontend attaches the noundef to function arguments as well as !noundef metadata to loads.
Since freeze x is x if x is noundef, freeze will be automatically optimized away.
Clang has been updated a few months ago to attach noundef to function arguments as well.

[xortator]

Thanks Nikita! This fixed my original performance problem