AMDGPU: In determining load clobbering in AnnotateUniform, don't scan if there are too many blocks.

[cfang]

Summary

The algorithm to find load clobbering in function is in the order of O^2.
The compilation becomes very slow if there are too many blocks ( ~3000).
To limit the compile time, we introduce a threshold (default 2500) of the
number of basic blocks.

[arsenm]

Does MemorySSA have the same problem? Could we just switch this to use MemorySSA?

[arsenm]

llvm/lib/Target/AMDGPU/AMDGPUAnnotateUniformValues.cpp

145–146

The logic here should be fixed first. This is checking if the load was clobbered, before the trivial check for isGlobalLoad. The expensive check should be reordered last

145–146

Actually it can go even deep,r under the isa<Argument> || GlobalValue check

[asbirlea]

In D84873#2182544, @arsenm wrote:

Does MemorySSA have the same problem? Could we just switch this to use MemorySSA?

Disclaimer: I know nothing about this pass or the purpose of this patch, just trying to answer this question.
MemorySSA has its own internal threshold limiting the number of memory instructions that are traversed upwards. It does not care at how many blocks those memory instructions are spread over.

[cfang]

llvm/lib/Target/AMDGPU/AMDGPUAnnotateUniformValues.cpp

145–146

Done in https://reviews.llvm.org/D84890.
Actually we have to do the expensive function call for the case PitI != NULL anyway.
So it won't resolve the issue we encountered (this this current patch is still needed).

[cfang]

In D84873#2182944, @asbirlea wrote:

In D84873#2182544, @arsenm wrote:

Does MemorySSA have the same problem? Could we just switch this to use MemorySSA?

Disclaimer: I know nothing about this pass or the purpose of this patch, just trying to answer this question.
MemorySSA has its own internal threshold limiting the number of memory instructions that are traversed upwards. It does not care at how many blocks those memory instructions are spread over.

Thanks for the comments! I see that in MemorySSA, it scans 100 memory instructions upwards to find whether it is clobbered.
In our case, we essentially check every basic block, and a max of also 100 instructions in each block to find the pointer dependence:
MDR->getPointerDependencyFrom(MemoryLocation(Ptr), true, StartIt, BB, Load);
At this moment, I am not clear how can we use the existing functionality in MemorySSA for our purpose.

[cfang]

Rebase after https://reviews.llvm.org/D84890

[arsenm]

How much improvement does D84890 give vs. this?

[cfang]

In D84873#2186018, @arsenm wrote:

How much improvement does D84890 give vs. this?

For the test case I have, D84890 did not show a measurable improvement,
while this can reduce the time from 2m30s to 13 seconds.

[arsenm]

llvm/lib/Target/AMDGPU/AMDGPUAnnotateUniformValues.cpp

118–126

This seems like a pretty stupid way of using this analysis. This is going to be re-scanning the same instructions many times. My quick look at MemoryDependenceAnalysis suggests the way you should use it is to use a combination of getDependency and getNonLocalPointeDependency, which has a cache and internally calls getPointerDependencyFrom. You would then have to walk up the chain of dependencies until you find no clobbers?

[cfang]

llvm/lib/Target/AMDGPU/AMDGPUAnnotateUniformValues.cpp

118–126

You are right. We need to come out with a better memory dependence analysis algorithm to avoid redundant searching. Before that, we should live with the current approach, which is a correct one.
As a result, we have to restrict the search to control the compile time.

[cfang]

Ping!

Should we commit this patch to fix the compilation time for now? Then we may look at the possibility to replace
MemoryDependenceAnaysis in AnnotateUniform pass?

[arsenm]

In D84873#2357528, @cfang wrote:

Ping!

Should we commit this patch to fix the compilation time for now? Then we may look at the possibility to replace
MemoryDependenceAnaysis in AnnotateUniform pass?

This doesn't sound like a commitment to me

[cfang]

In D84873#2358999, @arsenm wrote:

In D84873#2357528, @cfang wrote:

Ping!

Should we commit this patch to fix the compilation time for now? Then we may look at the possibility to replace
MemoryDependenceAnaysis in AnnotateUniform pass?

This doesn't sound like a commitment to me

Do you mean we need to open a bug (new task) to redesign load clobbering in AnnotateUniform pass?
Given the current implementation, I think this proposal is an effective cut-off to an expensive searching (without caching).

[arsenm]

In D84873#2427066, @cfang wrote:

In D84873#2358999, @arsenm wrote:

In D84873#2357528, @cfang wrote:

Ping!

Should we commit this patch to fix the compilation time for now? Then we may look at the possibility to replace
MemoryDependenceAnaysis in AnnotateUniform pass?

This doesn't sound like a commitment to me

Do you mean we need to open a bug (new task) to redesign load clobbering in AnnotateUniform pass?
Given the current implementation, I think this proposal is an effective cut-off to an expensive searching (without caching).

Yes, I don't like that this is just putting off a real fix

[cfang]

The issue has been workarounded by https://reviews.llvm.org/D94107
So abandon this one.

llvm/lib/Target/AMDGPU/AMDGPUAnnotateUniformValues.cpp

 #include "Utils/AMDGPUBaseInfo.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/Analysis/LegacyDivergenceAnalysis.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/MemoryDependenceAnalysis.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/InstVisitor.h"
 #include "llvm/InitializePasses.h"
+#include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 
 #define DEBUG_TYPE "amdgpu-annotate-uniform"
 
 using namespace llvm;
 
+static cl::opt<size_t> BasicBlockScanLimit("amdgpu-annotate-uniform-bb-limit",
+                    cl::Hidden, cl::init(2500),
+                    cl::desc("Max num BBs to scan in uniform annotation"));
+
 namespace {
 
 class AMDGPUAnnotateUniformValues : public FunctionPass,
                        public InstVisitor<AMDGPUAnnotateUniformValues> {
   LegacyDivergenceAnalysis *DA;
   MemoryDependenceResults *MDR;
   LoopInfo *LI;
   DenseMap<Value*, GetElementPtrInst*> noClobberClones;

       L = P;
       P = P->getParentLoop();
     } while (P);
     Checklist.insert(L->block_begin(), L->block_end());
     Start = L->getHeader();
   }
 
   DFS(Start, Checklist);
+
+  // To impove compilation, don't scan if there are too many BBS.
+  if (Checklist.size() > BasicBlockScanLimit)
+    return true;
+
   for (auto &BB : Checklist) {
     BasicBlock::iterator StartIt = (!L && (BB == Load->getParent())) ?
       BasicBlock::iterator(Load) : BB->end();
     auto Q = MDR->getPointerDependencyFrom(MemoryLocation(Ptr), true,
                                            StartIt, BB, Load);
     if (Q.isClobber() || Q.isUnknown())
       return true;
   }
   return false;
 }
 
 void AMDGPUAnnotateUniformValues::visitBranchInst(BranchInst &I) {
   if (DA->isUniform(&I))
     setUniformMetadata(I.getParent()->getTerminator());
 }
 
 void AMDGPUAnnotateUniformValues::visitLoadInst(LoadInst &I) {
   Value *Ptr = I.getPointerOperand();
   if (!DA->isUniform(Ptr))
     return;
   auto isGlobalLoad = [&](LoadInst &Load)->bool {
     return Load.getPointerAddressSpace() == AMDGPUAS::GLOBAL_ADDRESS;
   };
   // 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.
   Instruction *PtrI = dyn_cast<Instruction>(Ptr);
 
   if (!isEntryFunc) {
     if (PtrI)