UniformityAnalysis: Skip computation with no branch divergence

[arsenm]

Summary

Check TTI before bothering to run the computation. Everything
will be assumed uniform by default.

[arsenm]

Machine uniformity tests are broken, TTI seems to not work with -run-pass

[arsenm]

Move initialize

[sameerds]

llvm/lib/CodeGen/MachineUniformityAnalysis.cpp

225

Perhaps this magic constant "true" can be the result of calling NoTTI::hasBranchDivergence()?

[yassingh]

llvm/lib/CodeGen/MachineUniformityAnalysis.cpp

223

Can this issue be related to the compiler's inability to construct a Target object when the target is specified using "-march"? This was causing UA to produce incorrect results. https://godbolt.org/z/hqeGovefe

225

That will return false I think.

[arsenm]

llvm/lib/CodeGen/MachineUniformityAnalysis.cpp

223

I think this is more of a pass manager issue with -run-pass. It's probably not dealing with IR pass dependencies

[foad]

llvm/include/llvm/ADT/GenericUniformityImpl.h

46

I don't see why this is needed here. It's already included in lib/Analysis/UniformityAnalysis.cpp.

[arsenm]

d61cba6de24a2f59c975c23d5945b2dd4421173b

llvm/include/llvm/ADT/GenericUniformityImpl.h

 #ifndef LLVM_ADT_GENERICUNIFORMITYIMPL_H
 #define LLVM_ADT_GENERICUNIFORMITYIMPL_H
 
 #include "llvm/ADT/GenericUniformityInfo.h"
 
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SparseBitVector.h"
 #include "llvm/ADT/StringExtras.h"
+#include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/Support/raw_ostream.h"
 
 #include <set>
 
 #define DEBUG_TYPE "uniformity"
 
 using namespace llvm;
 

 }
 
 template <typename ContextT>
 GenericUniformityInfo<ContextT>::GenericUniformityInfo(
     FunctionT &Func, const DominatorTreeT &DT, const CycleInfoT &CI,
     const TargetTransformInfo *TTI)
     : F(&Func) {
   DA.reset(new ImplT{Func, DT, CI, TTI});
-  DA->initialize();
-  DA->compute();
 }
 
 template <typename ContextT>
 void GenericUniformityAnalysisImpl<ContextT>::print(raw_ostream &OS) const {
   bool haveDivergentArgs = false;
 
   // Control flow instructions may be divergent even if their inputs are
   // uniform. Thus, although exceedingly rare, it is possible to have a program

llvm/include/llvm/ADT/GenericUniformityInfo.h

public:
 
   GenericUniformityInfo(FunctionT &F, const DominatorTreeT &DT,
                         const CycleInfoT &CI,
                         const TargetTransformInfo *TTI = nullptr);
   GenericUniformityInfo() = default;
   GenericUniformityInfo(GenericUniformityInfo &&) = default;
   GenericUniformityInfo &operator=(GenericUniformityInfo &&) = default;
 
+  void compute() {
+    DA->initialize();
+    DA->compute();
+  }
+
   /// Whether any divergence was detected.
   bool hasDivergence() const;
 
   /// The GPU kernel this analysis result is for
   const FunctionT &getFunction() const { return *F; }
 
   /// Whether \p V is divergent at its definition.
   bool isDivergent(ConstValueRefT V) const;

llvm/include/llvm/CodeGen/MachineUniformityAnalysis.h

 #include "llvm/CodeGen/MachineSSAContext.h"
 
 namespace llvm {
 
 extern template class GenericUniformityInfo<MachineSSAContext>;
 using MachineUniformityInfo = GenericUniformityInfo<MachineSSAContext>;
 
 /// \brief Compute uniformity information for a Machine IR function.
-MachineUniformityInfo
-computeMachineUniformityInfo(MachineFunction &F,
-                             const MachineCycleInfo &cycleInfo,
-                             const MachineDomTree &domTree);
+///
+/// If \p HasBranchDivergence is false, produces a dummy result which assumes
+/// everything is uniform.
+MachineUniformityInfo computeMachineUniformityInfo(
+    MachineFunction &F, const MachineCycleInfo &cycleInfo,
+    const MachineDomTree &domTree, bool HasBranchDivergence);
 
 } // namespace llvm
 
 #endif // LLVM_CODEGEN_MACHINEUNIFORMITYANALYSIS_H

llvm/lib/Analysis/UniformityAnalysis.cpp

 //  UniformityInfoAnalysis and related pass implementations
 //===----------------------------------------------------------------------===//
 
 llvm::UniformityInfo UniformityInfoAnalysis::run(Function &F,
                                                  FunctionAnalysisManager &FAM) {
   auto &DT = FAM.getResult<DominatorTreeAnalysis>(F);
   auto &TTI = FAM.getResult<TargetIRAnalysis>(F);
   auto &CI = FAM.getResult<CycleAnalysis>(F);
-  return UniformityInfo{F, DT, CI, &TTI};
+  UniformityInfo UI{F, DT, CI, &TTI};
+  // Skip computation if we can assume everything is uniform.
+  if (TTI.hasBranchDivergence())
+    UI.compute();
+
+  return UI;
 }
 
 AnalysisKey UniformityInfoAnalysis::Key;
 
 UniformityInfoPrinterPass::UniformityInfoPrinterPass(raw_ostream &OS)
     : OS(OS) {}
 
 PreservedAnalyses UniformityInfoPrinterPass::run(Function &F,
bool UniformityInfoWrapperPass::runOnFunction(Function &F) {
   auto &cycleInfo = getAnalysis<CycleInfoWrapperPass>().getResult();
   auto &domTree = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
   auto &targetTransformInfo =
       getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
 
   m_function = &F;
   m_uniformityInfo =
       UniformityInfo{F, domTree, cycleInfo, &targetTransformInfo};
+
+  // Skip computation if we can assume everything is uniform.
+  if (targetTransformInfo.hasBranchDivergence())
+    m_uniformityInfo.compute();
+
   return false;
 }
 
 void UniformityInfoWrapperPass::print(raw_ostream &OS, const Module *) const {
   OS << "UniformityInfo for function '" << m_function->getName() << "':\n";
 }
 
 void UniformityInfoWrapperPass::releaseMemory() {
   m_uniformityInfo = UniformityInfo{};
   m_function = nullptr;
 }

llvm/lib/CodeGen/MachineUniformityAnalysis.cpp

 }
 
 // This ensures explicit instantiation of
 // GenericUniformityAnalysisImpl::ImplDeleter::operator()
 template class llvm::GenericUniformityInfo<MachineSSAContext>;
 template struct llvm::GenericUniformityAnalysisImplDeleter<
     llvm::GenericUniformityAnalysisImpl<MachineSSAContext>>;
 
-MachineUniformityInfo
-llvm::computeMachineUniformityInfo(MachineFunction &F,
-                                   const MachineCycleInfo &cycleInfo,
-                                   const MachineDomTree &domTree) {
+MachineUniformityInfo llvm::computeMachineUniformityInfo(
+    MachineFunction &F, const MachineCycleInfo &cycleInfo,
+    const MachineDomTree &domTree, bool HasBranchDivergence) {
   assert(F.getRegInfo().isSSA() && "Expected to be run on SSA form!");
-  return MachineUniformityInfo(F, domTree, cycleInfo);
+  MachineUniformityInfo UI(F, domTree, cycleInfo);
+  if (HasBranchDivergence)
+    UI.compute();
+  return UI;
 }
 
 namespace {
 
 /// Legacy analysis pass which computes a \ref MachineUniformityInfo.
 class MachineUniformityAnalysisPass : public MachineFunctionPass {
   MachineUniformityInfo UI;
 
void MachineUniformityAnalysisPass::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.addRequired<MachineCycleInfoWrapperPass>();
   AU.addRequired<MachineDominatorTree>();
   MachineFunctionPass::getAnalysisUsage(AU);
 }
 
 bool MachineUniformityAnalysisPass::runOnMachineFunction(MachineFunction &MF) {
   auto &DomTree = getAnalysis<MachineDominatorTree>().getBase();
   auto &CI = getAnalysis<MachineCycleInfoWrapperPass>().getCycleInfo();
-  UI = computeMachineUniformityInfo(MF, CI, DomTree);
+  // FIXME: Query TTI::hasBranchDivergence. -run-pass seems to end up with a
+  // default NoTTI
+  UI = computeMachineUniformityInfo(MF, CI, DomTree, true);
   return false;
 }
 
 void MachineUniformityAnalysisPass::print(raw_ostream &OS,
                                           const Module *) const {
   OS << "MachineUniformityInfo for function: " << UI.getFunction().getName()
      << "\n";
   UI.print(OS);

llvm/lib/Target/AMDGPU/AMDGPURegBankSelect.cpp

bool AMDGPURegBankSelect::runOnMachineFunction(MachineFunction &MF) {
   init(MF);
 
   assert(checkFunctionIsLegal(MF));
 
   MachineCycleInfo &CycleInfo =
       getAnalysis<MachineCycleInfoWrapperPass>().getCycleInfo();
   MachineDominatorTree &DomTree = getAnalysis<MachineDominatorTree>();
 
+  // TODO: Check for single lane execution.
   MachineUniformityInfo Uniformity =
-      computeMachineUniformityInfo(MF, CycleInfo, DomTree.getBase());
+      computeMachineUniformityInfo(MF, CycleInfo, DomTree.getBase(), true);
   (void)Uniformity; // TODO: Use this
 
   assignRegisterBanks(MF);
 
   OptMode = SaveOptMode;
   return false;
 }