[AMDGPU] Run '' after isel to simplify PHIs.

[hliao]

Summary

• As LCSSA is turned on just before isel, it may create PHI of the flow, which is consumed by pseudo structurized CFG instructions. When that PHIs are eliminated in O0, COPY may be placed wrongly as the these pseudo structurized CFG instructions are considering prologue of MBB.
• Run extra unreachable-mbb-elimination at the end of isel to clean up PHIs.

[arsenm]

I don't follow how eliminating unreachable blocks fixes this.

In general expecting code placement with the block "prolog" instructions isn't reliable. I had fixed this in rL357634, except it was reverted

llvm/test/CodeGen/AMDGPU/lcssa-optnone.ll

1–3 ↗

(On Diff #208446)

Generate check lines

[hliao]

revise commit message.

[hliao]

In D64353#1573837, @arsenm wrote:

I don't follow how eliminating unreachable blocks fixes this.

In general expecting code placement with the block "prolog" instructions isn't reliable. I had fixed this in rL357634, except it was reverted

LCSSA created PHI of flow used by cf.end. These PHIs (due to LCSSA) are unnecessary. unreachable-mbb-elimination could remove them.

[hliao]

In D64353#1573837, @arsenm wrote:

I don't follow how eliminating unreachable blocks fixes this.

In general expecting code placement with the block "prolog" instructions isn't reliable. I had fixed this in rL357634, except it was reverted

BTW, the flow created by CFG structurizer should not have PHI at all by design.

[arsenm]

I'm still confused. When I try your testcase, I see an earlier iterator crash in SILowerControlFlow

[hliao]

llvm/test/CodeGen/AMDGPU/lcssa-optnone.ll

1–3 ↗

(On Diff #208446)

that test case crash with the fix. I added CHECK-LABEL to check codegen could pass. Checking the code generated seems unnecessary to me.

[hliao]

In D64353#1573858, @arsenm wrote:

I'm still confused. When I try your testcase, I see an earlier iterator crash in SILowerControlFlow

SILowerControlFlow runs after PHIElim, which converts PHI to COPY and could generate code like this in the last MBB

END_CF %v0, ....
%v0 = COPY %vX

the use (END_CF) is before the def (COPY).
the iterator in SILowereControlFlow starts from that def (COPY) to its use (END_CF). But, as they misplaced, it reaches the end of MBB first and triggers the assertion of illegal iterator access.

[arsenm]

I think you should probably fix SILowerControlFlow

llvm/test/CodeGen/AMDGPU/lcssa-optnone.ll

1–3 ↗

(On Diff #208446)

Tests with no checks are bad form. I think any tests related to control flow handling should probably just be generated

[hliao]

In D64353#1573922, @arsenm wrote:

I think you should probably fix SILowerControlFlow

the misplacement of def/use is not the fault of SILowerControlFlow but PHIEliminate. However, even PHIEliminate should not be blamed as cf.end is part of MBB prologue. cf.end should not take any input from PHI.

In O2 compilation, there won't be such issue as, in optimized RA, livevariable is used to eliminate PHI better. LiveVariables depends on unreachable-mbb-elimin, which remove the PHI to cf.end.

[hliao]

revise test case

[arsenm]

In D64353#1573974, @hliao wrote:

In D64353#1573922, @arsenm wrote:

I think you should probably fix SILowerControlFlow

the misplacement of def/use is not the fault of SILowerControlFlow but PHIEliminate. However, even PHIEliminate should not be blamed as cf.end is part of MBB prologue. cf.end should not take any input from PHI.

In O2 compilation, there won't be such issue as, in optimized RA, livevariable is used to eliminate PHI better. LiveVariables depends on unreachable-mbb-elimin, which remove the PHI to cf.end.

This isn't a property the pass should rely on. SILowerControlFlow should defend against unexpected iteration order and unreachable blocks

[hliao]

In D64353#1574004, @arsenm wrote:

In D64353#1573974, @hliao wrote:

In D64353#1573922, @arsenm wrote:

I think you should probably fix SILowerControlFlow

the misplacement of def/use is not the fault of SILowerControlFlow but PHIEliminate. However, even PHIEliminate should not be blamed as cf.end is part of MBB prologue. cf.end should not take any input from PHI.

In O2 compilation, there won't be such issue as, in optimized RA, livevariable is used to eliminate PHI better. LiveVariables depends on unreachable-mbb-elimin, which remove the PHI to cf.end.

This isn't a property the pass should rely on. SILowerControlFlow should defend against unexpected iteration order and unreachable blocks

any use before def is invalid MIR, right?

[hliao]

cf.end and related MBB prologue instructions should not take PHIs as input. Before LCSSA is turned on, we won't have that IR. After LCSSA, the only possible PHI input is the one from non-latch loop single exit. That PHI is unnecessary and should be removed early to assure that the later passes could relies on the fact they cf.end and etc. won't take PHI as input.

[arsenm]

In D64353#1574005, @hliao wrote:

In D64353#1574004, @arsenm wrote:

In D64353#1573974, @hliao wrote:

In D64353#1573922, @arsenm wrote:

I think you should probably fix SILowerControlFlow

the misplacement of def/use is not the fault of SILowerControlFlow but PHIEliminate. However, even PHIEliminate should not be blamed as cf.end is part of MBB prologue. cf.end should not take any input from PHI.

In O2 compilation, there won't be such issue as, in optimized RA, livevariable is used to eliminate PHI better. LiveVariables depends on unreachable-mbb-elimin, which remove the PHI to cf.end.

This isn't a property the pass should rely on. SILowerControlFlow should defend against unexpected iteration order and unreachable blocks

any use before def is invalid MIR, right?

So the MIR is valid before phi elimination, and then becomes invalid after. Removing unreachable blocks earlier to avoid this happening is a workaround. It seems to me like we need to fix PHI elimination or avoid relying on the prolog instructions

[hliao]

In D64353#1574073, @arsenm wrote:

In D64353#1574005, @hliao wrote:

In D64353#1574004, @arsenm wrote:

In D64353#1573974, @hliao wrote:

In D64353#1573922, @arsenm wrote:

I think you should probably fix SILowerControlFlow

the misplacement of def/use is not the fault of SILowerControlFlow but PHIEliminate. However, even PHIEliminate should not be blamed as cf.end is part of MBB prologue. cf.end should not take any input from PHI.

In O2 compilation, there won't be such issue as, in optimized RA, livevariable is used to eliminate PHI better. LiveVariables depends on unreachable-mbb-elimin, which remove the PHI to cf.end.

This isn't a property the pass should rely on. SILowerControlFlow should defend against unexpected iteration order and unreachable blocks

any use before def is invalid MIR, right?

So the MIR is valid before phi elimination, and then becomes invalid after. Removing unreachable blocks earlier to avoid this happening is a workaround. It seems to me like we need to fix PHI elimination or avoid relying on the prolog instructions

my understanding is that MBB prologue instructions are designed NOT to take PHI as input. Like these pseudo instructions for structurized CFG, by design, they don't take any PHI as input. As an alternative approach (not workaround), we could ensure these instructions not taking PHI as input before PHIElim instead of teaching PHIElim to under them, more or less very target-specific stuff.

[arsenm]

No matter what, running UnreachableMachineBlockElim is not a fix for this.

In D64353#1574085, @hliao wrote:

In D64353#1574073, @arsenm wrote:

In D64353#1574005, @hliao wrote:

In D64353#1574004, @arsenm wrote:

In D64353#1573974, @hliao wrote:

In D64353#1573922, @arsenm wrote:

I think you should probably fix SILowerControlFlow

the misplacement of def/use is not the fault of SILowerControlFlow but PHIEliminate. However, even PHIEliminate should not be blamed as cf.end is part of MBB prologue. cf.end should not take any input from PHI.

In O2 compilation, there won't be such issue as, in optimized RA, livevariable is used to eliminate PHI better. LiveVariables depends on unreachable-mbb-elimin, which remove the PHI to cf.end.

This isn't a property the pass should rely on. SILowerControlFlow should defend against unexpected iteration order and unreachable blocks

any use before def is invalid MIR, right?

So the MIR is valid before phi elimination, and then becomes invalid after. Removing unreachable blocks earlier to avoid this happening is a workaround. It seems to me like we need to fix PHI elimination or avoid relying on the prolog instructions

my understanding is that MBB prologue instructions are designed NOT to take PHI as input. Like these pseudo instructions for structurized CFG, by design, they don't take any PHI as input. As an alternative approach (not workaround), we could ensure these instructions not taking PHI as input before PHIElim instead of teaching PHIElim to under them, more or less very target-specific stuff.

The verifier should probably check this. We definitely should not hack around this by deleting unreachable blocks that happens to run into this

[hliao]

In D64353#1590037, @arsenm wrote:

No matter what, running UnreachableMachineBlockElim is not a fix for this.

In D64353#1574085, @hliao wrote:

In D64353#1574073, @arsenm wrote:

In D64353#1574005, @hliao wrote:

In D64353#1574004, @arsenm wrote:

In D64353#1573974, @hliao wrote:

In D64353#1573922, @arsenm wrote:

I think you should probably fix SILowerControlFlow

the misplacement of def/use is not the fault of SILowerControlFlow but PHIEliminate. However, even PHIEliminate should not be blamed as cf.end is part of MBB prologue. cf.end should not take any input from PHI.

In O2 compilation, there won't be such issue as, in optimized RA, livevariable is used to eliminate PHI better. LiveVariables depends on unreachable-mbb-elimin, which remove the PHI to cf.end.

This isn't a property the pass should rely on. SILowerControlFlow should defend against unexpected iteration order and unreachable blocks

any use before def is invalid MIR, right?

So the MIR is valid before phi elimination, and then becomes invalid after. Removing unreachable blocks earlier to avoid this happening is a workaround. It seems to me like we need to fix PHI elimination or avoid relying on the prolog instructions

my understanding is that MBB prologue instructions are designed NOT to take PHI as input. Like these pseudo instructions for structurized CFG, by design, they don't take any PHI as input. As an alternative approach (not workaround), we could ensure these instructions not taking PHI as input before PHIElim instead of teaching PHIElim to under them, more or less very target-specific stuff.

The verifier should probably check this. We definitely should not hack around this by deleting unreachable blocks that happens to run into this

But, the verifier so far doesn't change that. For your concerns, I'd like to take the following approach:

• Add target checker to assert those instructions with direct PHI input.
• Add a special pass after isel to canonicalize these pseudo CFG instructions by removing PHI inputs.

Does that sound to be acceptable?

[arsenm]

I think PHIElimination::LowerPHINode needs to be taught to look for prolog instructions

In D64353#1590052, @hliao wrote:

In D64353#1590037, @arsenm wrote:

No matter what, running UnreachableMachineBlockElim is not a fix for this.

In D64353#1574085, @hliao wrote:

In D64353#1574073, @arsenm wrote:

In D64353#1574005, @hliao wrote:

In D64353#1574004, @arsenm wrote:

In D64353#1573974, @hliao wrote:

In D64353#1573922, @arsenm wrote:

I think you should probably fix SILowerControlFlow

the misplacement of def/use is not the fault of SILowerControlFlow but PHIEliminate. However, even PHIEliminate should not be blamed as cf.end is part of MBB prologue. cf.end should not take any input from PHI.

In O2 compilation, there won't be such issue as, in optimized RA, livevariable is used to eliminate PHI better. LiveVariables depends on unreachable-mbb-elimin, which remove the PHI to cf.end.

This isn't a property the pass should rely on. SILowerControlFlow should defend against unexpected iteration order and unreachable blocks

any use before def is invalid MIR, right?

So the MIR is valid before phi elimination, and then becomes invalid after. Removing unreachable blocks earlier to avoid this happening is a workaround. It seems to me like we need to fix PHI elimination or avoid relying on the prolog instructions

my understanding is that MBB prologue instructions are designed NOT to take PHI as input. Like these pseudo instructions for structurized CFG, by design, they don't take any PHI as input. As an alternative approach (not workaround), we could ensure these instructions not taking PHI as input before PHIElim instead of teaching PHIElim to under them, more or less very target-specific stuff.

The verifier should probably check this. We definitely should not hack around this by deleting unreachable blocks that happens to run into this

But, the verifier so far doesn't change that. For your concerns, I'd like to take the following approach:

• Add target checker to assert those instructions with direct PHI input.
• Add a special pass after isel to canonicalize these pseudo CFG instructions by removing PHI inputs.

Does that sound to be acceptable?

[hliao]

Please review https://reviews.llvm.org/D64946 following your suggestion.

In D64353#1590117, @arsenm wrote:

I think PHIElimination::LowerPHINode needs to be taught to look for prolog instructions

In D64353#1590052, @hliao wrote:

In D64353#1590037, @arsenm wrote:

No matter what, running UnreachableMachineBlockElim is not a fix for this.

In D64353#1574085, @hliao wrote:

In D64353#1574073, @arsenm wrote:

In D64353#1574005, @hliao wrote:

In D64353#1574004, @arsenm wrote:

In D64353#1573974, @hliao wrote:

In D64353#1573922, @arsenm wrote:

I think you should probably fix SILowerControlFlow

the misplacement of def/use is not the fault of SILowerControlFlow but PHIEliminate. However, even PHIEliminate should not be blamed as cf.end is part of MBB prologue. cf.end should not take any input from PHI.

In O2 compilation, there won't be such issue as, in optimized RA, livevariable is used to eliminate PHI better. LiveVariables depends on unreachable-mbb-elimin, which remove the PHI to cf.end.

This isn't a property the pass should rely on. SILowerControlFlow should defend against unexpected iteration order and unreachable blocks

any use before def is invalid MIR, right?

So the MIR is valid before phi elimination, and then becomes invalid after. Removing unreachable blocks earlier to avoid this happening is a workaround. It seems to me like we need to fix PHI elimination or avoid relying on the prolog instructions

my understanding is that MBB prologue instructions are designed NOT to take PHI as input. Like these pseudo instructions for structurized CFG, by design, they don't take any PHI as input. As an alternative approach (not workaround), we could ensure these instructions not taking PHI as input before PHIElim instead of teaching PHIElim to under them, more or less very target-specific stuff.

The verifier should probably check this. We definitely should not hack around this by deleting unreachable blocks that happens to run into this

But, the verifier so far doesn't change that. For your concerns, I'd like to take the following approach:

• Add target checker to assert those instructions with direct PHI input.
• Add a special pass after isel to canonicalize these pseudo CFG instructions by removing PHI inputs.

Does that sound to be acceptable?

[arsenm]

llvm/lib/Target/AMDGPU/AMDGPUTargetMachine.cpp

885 ↗

(On Diff #208460)

Can you add a fixme that this is a workaround and should be removed

[arsenm]

Given that D65141 may avoid the source of this problem, I think we can go with this as a quick workaround for now. Once LCSSA is no longer required, we can add a verifier check that a phi is not used as the intrinsic source

[hliao]

Add fixme.

[foad]

Can we revert this now that D67101 has landed? I have tried locally reverting your change to addInstSelector and your lcssa-optnone.ll test case still passes.

[foad]

In D64353#1701489, @foad wrote:

Can we revert this now that D67101 has landed? I have tried locally reverting your change to addInstSelector and your lcssa-optnone.ll test case still passes.

See D68769.

llvm/trunk/lib/Target/AMDGPU/AMDGPUTargetMachine.cpp

 }
 
 bool GCNPassConfig::addInstSelector() {
   AMDGPUPassConfig::addInstSelector();
   addPass(&SIFixSGPRCopiesID);
   addPass(createSILowerI1CopiesPass());
   addPass(createSIFixupVectorISelPass());
   addPass(createSIAddIMGInitPass());
+  // FIXME: Remove this once the phi on CF_END is cleaned up by either removing
+  // LCSSA or other ways.
+  addPass(&UnreachableMachineBlockElimID);
   return false;
 }
 
 bool GCNPassConfig::addIRTranslator() {
   addPass(new IRTranslator());
   return false;
 }
 

llvm/trunk/test/CodeGen/AMDGPU/lcssa-optnone.ll

+; RUN: llc -march=amdgcn -O0 -o - %s | FileCheck %s
+
+; CHECK-LABEL: non_uniform_loop
+; CHECK: s_endpgm
+define amdgpu_kernel void @non_uniform_loop(float addrspace(1)* %array) {
+entry:
+  %w = tail call i32 @llvm.amdgcn.workitem.id.x()
+  br label %for.cond
+
+for.cond:
+  %i = phi i32 [0, %entry], [%i.next, %for.inc]
+  %cmp = icmp ult i32 %i, %w
+  br i1 %cmp, label %for.body, label %for.end
+
+for.body:
+  br label %for.inc
+
+for.inc:
+  %i.next = add i32 %i, 1
+  br label %for.cond
+
+for.end:
+  ret void
+}
+
+declare i32 @llvm.amdgcn.workitem.id.x()