[AMDGPU] Replace LegacyDA with Uniformity Analysis in AnnotateUniformValues

[sameerds]

llvm/test/CodeGen/AMDGPU/divergent-branch-uniform-condition.ll

85 ↗

(On Diff #497880)

The comment at the start of this test says the following:

11 ; This module creates a divergent branch in block Flow2. The branch is
12 ; marked as divergent by the divergence analysis but the condition is
13 ; not. This test ensures that the divergence of the branch is tested,
14 ; not its condition, so that branch is correctly emitted as divergent.

It seems that the proposed change completely fails the intention of this test?

[ruiling]

I think for this specific case, we should report %8 as uniform, and the branch should also be uniform. But there seems something wrong in the uniform analysis, if you try opt -passes='print<uniformity>' with the test here. We will see both the condition %8 and the conditional branch br i1 %8,... are reported as divergent. but the isUniform() query return true for the branch instruction. I think there should be something wrong in uniform analysis. If the condition is divergent, I think the branch should also be divergent. Another issue I want to point out that the uniform analysis has a subtle difference with divergence analysis. There is some comment in https://github.com/llvm/llvm-project/blob/main/llvm/lib/Target/AMDGPU/AMDGPURewriteUndefForPHI.cpp#L13 to explain the issue. I think we need to fill the gap to switch to uniform analysis, otherwise we will regress code generation. The last time we discussed this, I think we want some target specific option in uniform analysis to match this behavior with divergence analysis.

[sameerds]

In D144162#4134296, @ruiling wrote:

I think for this specific case, we should report %8 as uniform, and the branch should also be uniform. But there seems something wrong in the uniform analysis, if you try opt -passes='print<uniformity>' with the test here. We will see both the condition %8 and the conditional branch br i1 %8,... are reported as divergent. but the isUniform() query return true for the branch instruction. I think there should be something wrong in uniform analysis. If the condition is divergent, I think the branch should also be divergent. Another issue I want to point out that the uniform analysis has a subtle difference with divergence analysis. There is some comment in https://github.com/llvm/llvm-project/blob/main/llvm/lib/Target/AMDGPU/AMDGPURewriteUndefForPHI.cpp#L13 to explain the issue. I think we need to fill the gap to switch to uniform analysis, otherwise we will regress code generation. The last time we discussed this, I think we want some target specific option in uniform analysis to match this behavior with divergence analysis.

I agree with that assessment, and pretty much found the same thing myself by comparing with the output of "print<divergence>". The uniformity analysis assumes a phi is divergent if it has an undef argument, but the divergence analysis does not make that assumption. The difference is in the call to PHINode::hasConstantValue() for divergence analysis and PHINode::hasConstantOrUndefValue() for uniformity analysis.

I think we should just fix the uniformity analysis to match the existing behaviour and revisit the issue later. I can have the patch ready by Monday EOD IST.

[sameerds]

The failing test should pass after D144254 lands.

[ruiling]

I think it is reasonable to match divergent analysis behavior regarding to undef. The other problem that isUniform() return true for a divergent branch instruction makes me wonder: is it the best way to replace use of divergence analysis with uniform analysis one by one? Although I am optimistic about the quality of uniform analysis, I think it may be more helpful to replace all the occurrences of divergence analysis and fix all the bugs uncovered. Ideally, we would have very little test changes. The reason is that one specific pass may not have enough test coverage. Fixing the bugs after switching all the uses of divergence analysis to uniform analysis will make us more confident that we will less likely cause regression. Any different idea?

[gandhi21299]

In D144162#4138003, @ruiling wrote:

I think it is reasonable to match divergent analysis behavior regarding to undef. The other problem that isUniform() return true for a divergent branch instruction makes me wonder: is it the best way to replace use of divergence analysis with uniform analysis one by one? Although I am optimistic about the quality of uniform analysis, I think it may be more helpful to replace all the occurrences of divergence analysis and fix all the bugs uncovered. Ideally, we would have very little test changes. The reason is that one specific pass may not have enough test coverage. Fixing the bugs after switching all the uses of divergence analysis to uniform analysis will make us more confident that we will less likely cause regression. Any different idea?

I tried replacing the analysis in AMDGPUUnifyDivergentExitNodes pass, it causes 20 tests to fail including a few fatal errors. I could imagine a lot more failures may occur after replacing in 8 or so other middle-end passes. Replacing all the occurences in a single patch will be massive. I prefer the one pass at a time approach (like the approach with this patch).

[sameerds]

I agree with @gandhi21299 ... it's best to work through the passes one at a time. But maybe we should not enable each change as it happens. We could put the changes behind a command-line option to switch between DA and UA. One single option that switches whatever passes have been updated, until all passes are updated and we are ready to flip the switch permanently.

[gandhi21299]

In D144162#4140550, @sameerds wrote:

I agree with @gandhi21299 ... it's best to work through the passes one at a time. But maybe we should not enable each change as it happens. We could put the changes behind a command-line option to switch between DA and UA. One single option that switches whatever passes have been updated, until all passes are updated and we are ready to flip the switch permanently.

Do you mean a single option that determines the analysis to use and all transformations use analysis depending on the option value? Something like --enable-uniformity-analysis=1?

[arsenm]

In D144162#4138003, @ruiling wrote:

Fixing the bugs after switching all the uses of divergence analysis to uniform analysis will make us more confident that we will less likely cause regression. Any different idea?

I think changing them one at a time is fine, this shouldn't be a long drawn out process.

[ruiling]

In D144162#4140550, @sameerds wrote:

I agree with @gandhi21299 ... it's best to work through the passes one at a time. But maybe we should not enable each change as it happens. We could put the changes behind a command-line option to switch between DA and UA. One single option that switches whatever passes have been updated, until all passes are updated and we are ready to flip the switch permanently.

Another possible way may be do the replacement one pass by one pass, but we only submit all the changes until all the passes have switched to uniform analysis.

[sameerds]

In D144162#4141978, @gandhi21299 wrote:

In D144162#4140550, @sameerds wrote:

I agree with @gandhi21299 ... it's best to work through the passes one at a time. But maybe we should not enable each change as it happens. We could put the changes behind a command-line option to switch between DA and UA. One single option that switches whatever passes have been updated, until all passes are updated and we are ready to flip the switch permanently.

Do you mean a single option that determines the analysis to use and all transformations use analysis depending on the option value? Something like --enable-uniformity-analysis=1?

Not exactly like that. We can make the UA a wrapper over the DA, and update the passes to use only the UA. Depending on the commandline, the UA will actually compute its own results, or simply hand off to a DA stored internally. This is how the legacy DA and the DA are currently arranged.

Once we are ready to shift to UA for good, we can eliminate all this. And we should.

[gandhi21299]

• Instead of checking uniformity of a branch instruction in the pass, check whether its parent basic block is not divergent.
• Update test checks.

[sameerds]

llvm/lib/Target/AMDGPU/AMDGPUAnnotateUniformValues.cpp

81

I am not sure we should be doing this. Smells like a bug in the UA!

[sameerds]

llvm/lib/Target/AMDGPU/AMDGPUAnnotateUniformValues.cpp

81

D144699 allows the original "isUniform()" call to work as expected on a BranchInst.

[gandhi21299]

Rebased against main

[sameerds]

LGTM! But please ensure this passes internal builds before submitting upstream.

[gandhi21299]

• Corrected branch-uniformity.ll and i1-copy-from-loop.ll

[foad]

llvm/lib/Target/AMDGPU/AMDGPUAnnotateUniformValues.cpp

81

Did you mean to change this back to isUniform? (I don't really mind either way.)

llvm/test/CodeGen/AMDGPU/branch-uniformity.ll

12 ↗

(On Diff #501047)

This looks like it might be the same kind of regression as i1-copy-from-loop.ll

llvm/test/CodeGen/AMDGPU/divergent-branch-uniform-condition.ll

46 ↗

(On Diff #501047)

Same kind of regression here I think (the s_cselect_b64 -1, 0 is a bad smell).

llvm/test/CodeGen/AMDGPU/i1-copy-from-loop.ll

28 ↗

(On Diff #501047)

This is a regression.

[gandhi21299]

llvm/lib/Target/AMDGPU/AMDGPUAnnotateUniformValues.cpp

81

Yea I meant to change this back, great catch!

llvm/test/CodeGen/AMDGPU/i1-copy-from-loop.ll

28 ↗

(On Diff #501047)

Should I handle all the regressions in a seperate patch?

[foad]

llvm/test/CodeGen/AMDGPU/i1-copy-from-loop.ll

28 ↗

(On Diff #501047)

Normally you would not commit a patch that causes regressions, unless you can explain them and get agreement that they are acceptable.

[gandhi21299]

Reverted back to isUniform, fixes all the regressions.

llvm/lib/Target/AMDGPU/AMDGPUAnnotateUniformValues.cpp

 /// can be used during instruction selection.
 //
 //===----------------------------------------------------------------------===//
 
 #include "AMDGPU.h"
 #include "Utils/AMDGPUBaseInfo.h"
 #include "Utils/AMDGPUMemoryUtils.h"
 #include "llvm/Analysis/AliasAnalysis.h"
-#include "llvm/Analysis/LegacyDivergenceAnalysis.h"
 #include "llvm/Analysis/MemorySSA.h"
+#include "llvm/Analysis/UniformityAnalysis.h"
 #include "llvm/IR/InstVisitor.h"
 #include "llvm/InitializePasses.h"
 
 #define DEBUG_TYPE "amdgpu-annotate-uniform"
 
 using namespace llvm;
 
 namespace {
 
 class AMDGPUAnnotateUniformValues : public FunctionPass,
                        public InstVisitor<AMDGPUAnnotateUniformValues> {
-  LegacyDivergenceAnalysis *DA;
+  UniformityInfo *UA;
   MemorySSA *MSSA;
   AliasAnalysis *AA;
   bool isEntryFunc;
   bool Changed;
 
   void setUniformMetadata(Instruction *I) {
     I->setMetadata("amdgpu.uniform", MDNode::get(I->getContext(), {}));
     Changed = true;
public:
   AMDGPUAnnotateUniformValues() :
     FunctionPass(ID) { }
   bool doInitialization(Module &M) override;
   bool runOnFunction(Function &F) override;
   StringRef getPassName() const override {
     return "AMDGPU Annotate Uniform Values";
   }
   void getAnalysisUsage(AnalysisUsage &AU) const override {
-    AU.addRequired<LegacyDivergenceAnalysis>();
+    AU.addRequired<UniformityInfoWrapperPass>();
     AU.addRequired<MemorySSAWrapperPass>();
     AU.addRequired<AAResultsWrapperPass>();
     AU.setPreservesAll();
  }
 
   void visitBranchInst(BranchInst &I);
   void visitLoadInst(LoadInst &I);
 };
 
 } // End anonymous namespace
 
 INITIALIZE_PASS_BEGIN(AMDGPUAnnotateUniformValues, DEBUG_TYPE,
                       "Add AMDGPU uniform metadata", false, false)
-INITIALIZE_PASS_DEPENDENCY(LegacyDivergenceAnalysis)
+INITIALIZE_PASS_DEPENDENCY(UniformityInfoWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(MemorySSAWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
 INITIALIZE_PASS_END(AMDGPUAnnotateUniformValues, DEBUG_TYPE,
                     "Add AMDGPU uniform metadata", false, false)
 
 char AMDGPUAnnotateUniformValues::ID = 0;
 
 void AMDGPUAnnotateUniformValues::visitBranchInst(BranchInst &I) {
-  if (DA->isUniform(&I))
+  if (UA->isUniform(&I))
     setUniformMetadata(&I);
 }
 
 void AMDGPUAnnotateUniformValues::visitLoadInst(LoadInst &I) {
   Value *Ptr = I.getPointerOperand();
-  if (!DA->isUniform(Ptr))
+  if (!UA->isUniform(Ptr))
     return;
   Instruction *PtrI = dyn_cast<Instruction>(Ptr);
   if (PtrI)
     setUniformMetadata(PtrI);
 
   // We're tracking up to the Function boundaries, and cannot go beyond because
   // of FunctionPass restrictions. We can ensure that is memory not clobbered
   // for memory operations that are live in to entry points only.
   if (!isEntryFunc)
     return;
   bool GlobalLoad = I.getPointerAddressSpace() == AMDGPUAS::GLOBAL_ADDRESS;
   if (GlobalLoad && !AMDGPU::isClobberedInFunction(&I, MSSA, AA))
     setNoClobberMetadata(&I);
 }
 
 bool AMDGPUAnnotateUniformValues::doInitialization(Module &M) {
   return false;
 }
 
 bool AMDGPUAnnotateUniformValues::runOnFunction(Function &F) {
   if (skipFunction(F))
     return false;
 
-  DA = &getAnalysis<LegacyDivergenceAnalysis>();
+  UA = &getAnalysis<UniformityInfoWrapperPass>().getUniformityInfo();
   MSSA = &getAnalysis<MemorySSAWrapperPass>().getMSSA();
   AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
   isEntryFunc = AMDGPU::isEntryFunctionCC(F.getCallingConv());
 
   Changed = false;
   visit(F);
   return Changed;
 }
 
 FunctionPass *
 llvm::createAMDGPUAnnotateUniformValues() {
   return new AMDGPUAnnotateUniformValues();
 }

llvm/test/CodeGen/AMDGPU/llc-pipeline.ll

 ; GCN-O0-NEXT:        Natural Loop Information
 ; GCN-O0-NEXT:        Convert irreducible control-flow into natural loops
 ; GCN-O0-NEXT:        Fixup each natural loop to have a single exit block
 ; GCN-O0-NEXT:        Post-Dominator Tree Construction
 ; GCN-O0-NEXT:        Dominance Frontier Construction
 ; GCN-O0-NEXT:        Detect single entry single exit regions
 ; GCN-O0-NEXT:        Region Pass Manager
 ; GCN-O0-NEXT:          Structurize control flow
-; GCN-O0-NEXT:        Post-Dominator Tree Construction
-; GCN-O0-NEXT:        Natural Loop Information
-; GCN-O0-NEXT:        Legacy Divergence Analysis
+; GCN-O0-NEXT:        Cycle Info Analysis
+; GCN-O0-NEXT:        Uniformity Analysis
 ; GCN-O0-NEXT:        Basic Alias Analysis (stateless AA impl)
 ; GCN-O0-NEXT:        Function Alias Analysis Results
 ; GCN-O0-NEXT:        Memory SSA
 ; GCN-O0-NEXT:        AMDGPU Annotate Uniform Values
+; GCN-O0-NEXT:        Natural Loop Information
+; GCN-O0-NEXT:        Post-Dominator Tree Construction
+; GCN-O0-NEXT:        Legacy Divergence Analysis
 ; GCN-O0-NEXT:        SI annotate control flow
 ; GCN-O0-NEXT:        Post-Dominator Tree Construction
 ; GCN-O0-NEXT:        Legacy Divergence Analysis
 ; GCN-O0-NEXT:        AMDGPU Rewrite Undef for PHI
 ; GCN-O0-NEXT:        LCSSA Verifier
 ; GCN-O0-NEXT:        Loop-Closed SSA Form Pass
 ; GCN-O0-NEXT:      DummyCGSCCPass
 ; GCN-O0-NEXT:      FunctionPass Manager

 ; GCN-O1-NEXT:        Natural Loop Information
 ; GCN-O1-NEXT:        Convert irreducible control-flow into natural loops
 ; GCN-O1-NEXT:        Fixup each natural loop to have a single exit block
 ; GCN-O1-NEXT:        Post-Dominator Tree Construction
 ; GCN-O1-NEXT:        Dominance Frontier Construction
 ; GCN-O1-NEXT:        Detect single entry single exit regions
 ; GCN-O1-NEXT:        Region Pass Manager
 ; GCN-O1-NEXT:          Structurize control flow
-; GCN-O1-NEXT:        Post-Dominator Tree Construction
-; GCN-O1-NEXT:        Natural Loop Information
-; GCN-O1-NEXT:        Legacy Divergence Analysis
+; GCN-O1-NEXT:        Cycle Info Analysis
+; GCN-O1-NEXT:        Uniformity Analysis
 ; GCN-O1-NEXT:        Basic Alias Analysis (stateless AA impl)
 ; GCN-O1-NEXT:        Function Alias Analysis Results
 ; GCN-O1-NEXT:        Memory SSA
 ; GCN-O1-NEXT:        AMDGPU Annotate Uniform Values
+; GCN-O1-NEXT:        Natural Loop Information
+; GCN-O1-NEXT:        Post-Dominator Tree Construction
+; GCN-O1-NEXT:        Legacy Divergence Analysis
 ; GCN-O1-NEXT:        SI annotate control flow
 ; GCN-O1-NEXT:        Post-Dominator Tree Construction
 ; GCN-O1-NEXT:        Legacy Divergence Analysis
 ; GCN-O1-NEXT:        AMDGPU Rewrite Undef for PHI
 ; GCN-O1-NEXT:        LCSSA Verifier
 ; GCN-O1-NEXT:        Loop-Closed SSA Form Pass
 ; GCN-O1-NEXT:      DummyCGSCCPass
 ; GCN-O1-NEXT:      FunctionPass Manager

 ; GCN-O1-OPTS-NEXT:        Natural Loop Information
 ; GCN-O1-OPTS-NEXT:        Convert irreducible control-flow into natural loops
 ; GCN-O1-OPTS-NEXT:        Fixup each natural loop to have a single exit block
 ; GCN-O1-OPTS-NEXT:        Post-Dominator Tree Construction
 ; GCN-O1-OPTS-NEXT:        Dominance Frontier Construction
 ; GCN-O1-OPTS-NEXT:        Detect single entry single exit regions
 ; GCN-O1-OPTS-NEXT:        Region Pass Manager
 ; GCN-O1-OPTS-NEXT:          Structurize control flow
-; GCN-O1-OPTS-NEXT:        Post-Dominator Tree Construction
-; GCN-O1-OPTS-NEXT:        Natural Loop Information
-; GCN-O1-OPTS-NEXT:        Legacy Divergence Analysis
+; GCN-O1-OPTS-NEXT:        Cycle Info Analysis
+; GCN-O1-OPTS-NEXT:        Uniformity Analysis
 ; GCN-O1-OPTS-NEXT:        Basic Alias Analysis (stateless AA impl)
 ; GCN-O1-OPTS-NEXT:        Function Alias Analysis Results
 ; GCN-O1-OPTS-NEXT:        Memory SSA
 ; GCN-O1-OPTS-NEXT:        AMDGPU Annotate Uniform Values
+; GCN-O1-OPTS-NEXT:        Natural Loop Information
+; GCN-O1-OPTS-NEXT:        Post-Dominator Tree Construction
+; GCN-O1-OPTS-NEXT:        Legacy Divergence Analysis
 ; GCN-O1-OPTS-NEXT:        SI annotate control flow
 ; GCN-O1-OPTS-NEXT:        Post-Dominator Tree Construction
 ; GCN-O1-OPTS-NEXT:        Legacy Divergence Analysis
 ; GCN-O1-OPTS-NEXT:        AMDGPU Rewrite Undef for PHI
 ; GCN-O1-OPTS-NEXT:        LCSSA Verifier
 ; GCN-O1-OPTS-NEXT:        Loop-Closed SSA Form Pass
 ; GCN-O1-OPTS-NEXT:      DummyCGSCCPass
 ; GCN-O1-OPTS-NEXT:      FunctionPass Manager

 ; GCN-O2-NEXT:        Natural Loop Information
 ; GCN-O2-NEXT:        Convert irreducible control-flow into natural loops
 ; GCN-O2-NEXT:        Fixup each natural loop to have a single exit block
 ; GCN-O2-NEXT:        Post-Dominator Tree Construction
 ; GCN-O2-NEXT:        Dominance Frontier Construction
 ; GCN-O2-NEXT:        Detect single entry single exit regions
 ; GCN-O2-NEXT:        Region Pass Manager
 ; GCN-O2-NEXT:          Structurize control flow
-; GCN-O2-NEXT:        Post-Dominator Tree Construction
-; GCN-O2-NEXT:        Natural Loop Information
-; GCN-O2-NEXT:        Legacy Divergence Analysis
+; GCN-O2-NEXT:        Cycle Info Analysis
+; GCN-O2-NEXT:        Uniformity Analysis
 ; GCN-O2-NEXT:        Basic Alias Analysis (stateless AA impl)
 ; GCN-O2-NEXT:        Function Alias Analysis Results
 ; GCN-O2-NEXT:        Memory SSA
 ; GCN-O2-NEXT:        AMDGPU Annotate Uniform Values
+; GCN-O2-NEXT:        Natural Loop Information
+; GCN-O2-NEXT:        Post-Dominator Tree Construction
+; GCN-O2-NEXT:        Legacy Divergence Analysis
 ; GCN-O2-NEXT:        SI annotate control flow
 ; GCN-O2-NEXT:        Post-Dominator Tree Construction
 ; GCN-O2-NEXT:        Legacy Divergence Analysis
 ; GCN-O2-NEXT:        AMDGPU Rewrite Undef for PHI
 ; GCN-O2-NEXT:        LCSSA Verifier
 ; GCN-O2-NEXT:        Loop-Closed SSA Form Pass
 ; GCN-O2-NEXT:      Analysis if a function is memory bound
 ; GCN-O2-NEXT:      DummyCGSCCPass

 ; GCN-O3-NEXT:        Natural Loop Information
 ; GCN-O3-NEXT:        Convert irreducible control-flow into natural loops
 ; GCN-O3-NEXT:        Fixup each natural loop to have a single exit block
 ; GCN-O3-NEXT:        Post-Dominator Tree Construction
 ; GCN-O3-NEXT:        Dominance Frontier Construction
 ; GCN-O3-NEXT:        Detect single entry single exit regions
 ; GCN-O3-NEXT:        Region Pass Manager
 ; GCN-O3-NEXT:          Structurize control flow
-; GCN-O3-NEXT:        Post-Dominator Tree Construction
-; GCN-O3-NEXT:        Natural Loop Information
-; GCN-O3-NEXT:        Legacy Divergence Analysis
+; GCN-O3-NEXT:        Cycle Info Analysis
+; GCN-O3-NEXT:        Uniformity Analysis
 ; GCN-O3-NEXT:        Basic Alias Analysis (stateless AA impl)
 ; GCN-O3-NEXT:        Function Alias Analysis Results
 ; GCN-O3-NEXT:        Memory SSA
 ; GCN-O3-NEXT:        AMDGPU Annotate Uniform Values
+; GCN-O3-NEXT:        Natural Loop Information
+; GCN-O3-NEXT:        Post-Dominator Tree Construction
+; GCN-O3-NEXT:        Legacy Divergence Analysis
 ; GCN-O3-NEXT:        SI annotate control flow
 ; GCN-O3-NEXT:        Post-Dominator Tree Construction
 ; GCN-O3-NEXT:        Legacy Divergence Analysis
 ; GCN-O3-NEXT:        AMDGPU Rewrite Undef for PHI
 ; GCN-O3-NEXT:        LCSSA Verifier
 ; GCN-O3-NEXT:        Loop-Closed SSA Form Pass
 ; GCN-O3-NEXT:      Analysis if a function is memory bound
 ; GCN-O3-NEXT:      DummyCGSCCPass