[AMDGPU]Add+GEP->GEP commit performance degradation on AMDGPU

[lfmeadow]

AMD have traced some significant (8-20%) slowdowns on several of AMD's rocFFT kernels to the commit mentioned in #78214 . The llvm commit is e13bed4.
Briefly, we have identified two problems:

1. The commit causes simplifycfg to bail out for fear of creating too many PHI nodes (even though they don't really get created). This has cascade effects on the backend register allocation pipeline, causing the kernel to use many more Vector GPRs (VGPRS) on AMD CDNA architecture GPUs. This in turn drops occupancy with a corresponding decrease in performance. See simplifycfg-repro
2. A more subtle effect occurs when the transformation results in more CSE opportunities. This ends up increasing the VGPR usage as well, similarly dropping the occupancy. The performance loss is less severe but is still in the 8% range. See regalloc-repro
   There are a lot of details on github as noted above. I will briefly summarize.
   For issue 1, simplifycfg bails with SINK: stopping here, too many PHIs would be created!. I hacked a tunable for simplifycfg as shown in the patch thus allowing 4 PHI nodes, and the resulting code regains the performance.
   For issue 2, there is no obvious smoking gun; as far as I can tell it just puts more pressure on the register allocation path to put partial address expressions in registers, with no obvious benefit.

Ideally the GEP rewrite commit would be withdrawn. I don't see any way to fix this otherwise.
I do not understand why simplifycfg is failing to restructure this code.

Thanks for your consideration

[llvmbot]

@llvm/issue-subscribers-backend-amdgpu

Author: Larry Meadows (lfmeadow)

AMD have traced some significant (8-20%) slowdowns on several of AMD's rocFFT kernels to the commit mentioned in #https://github.com//issues/78214 . The specific commit is

[dtcxzyw]

cc @nikic

[nikic]

For SimplifyCFG the problem is basically that, when considering sinking for each instruction individually, it would create many phi nodes. However, if we sink multiple instructions, it turns out that most of the phi nodes are actually not needed (because the phi operands are also sunk instructions). It should be possible to teach SimplifyCFG about that.

[nikic]

Hm actually it looks like there's already a check for this here:

llvm-project/llvm/lib/Transforms/Utils/SimplifyCFG.cpp

Line 2342 in 86bb5c8

if (!InstructionsToSink.contains(V))

So the issue must be something else...

[nikic]

I think the actual problem may be the one-use check in:

llvm-project/llvm/lib/Transforms/Utils/SimplifyCFG.cpp

Lines 1957 to 1961 in 86bb5c8

	// Each instruction must have zero or one use.
	if (HasUse && !I->hasOneUse())
	return false;
	if (!HasUse && !I->user_empty())
	return false;

Some of the instructions also have an extra use in a phi node in the sink block, so they'll not be considered sinking candidates. Not immediately obvious to me why we need the one-use restriction.

[nikic]

Reduced test case to illustrate the problem: https://llvm.godbolt.org/z/q6Eqdj8K7

define ptr @test(i1 %c, ptr %p, i64 %a, i64 %b) {
    br i1 %c, label %if, label %else
if:
    call void @dummy()
    %gep1.a = getelementptr i8, ptr %p, i64 %a
    %gep2.a = getelementptr i8, ptr %gep1.a, i64 %b
    br label %join
else:
    %gep1.b = getelementptr i8, ptr %p, i64 %a
    %gep2.b = getelementptr i8, ptr %gep1.b, i64 %b
    br label %join
join:
    %phi1 = phi ptr [ %gep1.a, %if ], [ %gep1.b, %else ]
    %phi2 = phi ptr [ %gep2.a, %if ], [ %gep2.b, %else ]
    call void @use(ptr %phi1)
    ret ptr %phi2
}

declare void @dummy()
declare void @use(ptr)

Produces:

define ptr @test(i1 %c, ptr %p, i64 %a, i64 %b) {
  br i1 %c, label %if, label %else

if:                                               ; preds = %0
  call void @dummy()
  %gep1.a = getelementptr i8, ptr %p, i64 %a
  br label %join

else:                                             ; preds = %0
  %gep1.b = getelementptr i8, ptr %p, i64 %a
  br label %join

join:                                             ; preds = %else, %if
  %gep1.b.sink = phi ptr [ %gep1.b, %else ], [ %gep1.a, %if ]
  %phi1 = phi ptr [ %gep1.a, %if ], [ %gep1.b, %else ]
  %gep2.b = getelementptr i8, ptr %gep1.b.sink, i64 %b
  call void @use(ptr %phi1)
  ret ptr %gep2.b
}

This one is even extra bad because we end up with two identical phis that block the sinking that would remove those phis...

[nikic]

Preparatory PR: #94462 Once that lands, I have another patch to enable sinking of instructions with multiple uses.

[lfmeadow]

FYI The preparatory PR did not fix the problem in the real code; it also still complains about 'too many PHI' .
I'd be glad to test your second patch when I can get it.