[GVN] Avoid replacing uniforms with non-uniforms in propagateEquality

[bogner]

Summary

When propagating equality, avoid replacing values that are known to be
uniform when that will lead to information loss, since that's very
likely to pessimize performance.

[bogner]

A couple of things I'm not 100% sure about:

• Are we okay with adding the TTI dependency on GVN? We already depend on TLI so I think it's probably okay.
• Is this testable at all without the AMDGPU backend? I don't think there's a way to imply uniformity generically

[bogner]

Fix legacy pass manager deps

[foad]

If we're going to do this I think we ought to do it properly, by querying UniformityAnalysis. TTI->isAlwaysUniform will only catch a small fraction of the values that are provably uniform.

llvm/test/Transforms/GVN/uniform-values.ll

2

Maybe this should go in test/Transforms/GVN/AMDGPU/? That's what we've done for lots of other test/Transforms/*/AMDGPU/ tests.

[Pierre-vh]

In D146823#4223352, @foad wrote:

If we're going to do this I think we ought to do it properly, by querying UniformityAnalysis. TTI->isAlwaysUniform will only catch a small fraction of the values that are provably uniform.

I agree, but most targets don't care about uniformity so I don't think we can make GVN depend on UA unless we find a way to avoid running the analysis for those targets. No?
Does UA bail out early for non-GPU targets? (It'd be nice if it did that and just returned an empty UniformityInfo instance for those targets, we could then use UA in more places in the middle-end without worrying about performance)

[sameerds]

In D146823#4223421, @Pierre-vh wrote:

In D146823#4223352, @foad wrote:

If we're going to do this I think we ought to do it properly, by querying UniformityAnalysis. TTI->isAlwaysUniform will only catch a small fraction of the values that are provably uniform.

I agree, but most targets don't care about uniformity so I don't think we can make GVN depend on UA unless we find a way to avoid running the analysis for those targets. No?
Does UA bail out early for non-GPU targets? (It'd be nice if it did that and just returned an empty UniformityInfo instance for those targets, we could then use UA in more places in the middle-end without worrying about performance)

When UA or DA initialize, they query TTI for sources of divergence. On a target with no divergence, they won't find any and hence the analysis should be trivial anyway. The only cost is one O(N) pass over the entire function. We could in principle eliminate that by just querying for TTI.hasBranchDivergence(). But there have been philosophical objections to taking that approach in the past. In general, one day, we would like to move to an implementation where source of divergence are inferred from IR semantics rather than TTI.

[sameerds]

In D146823#4219970, @bogner wrote:

A couple of things I'm not 100% sure about:

• Are we okay with adding the TTI dependency on GVN? We already depend on TLI so I think it's probably okay.
• Is this testable at all without the AMDGPU backend? I don't think there's a way to imply uniformity generically

In general divergence exists only on targets that have branch divergence, which is why this change matters on those targets such as AMDGPU. On a CPU target, everything is always uniform. So any test needs a GPU target.

[bogner]

In D146823#4223645, @sameerds wrote:

In D146823#4219970, @bogner wrote:

A couple of things I'm not 100% sure about:

• Are we okay with adding the TTI dependency on GVN? We already depend on TLI so I think it's probably okay.
• Is this testable at all without the AMDGPU backend? I don't think there's a way to imply uniformity generically

In general divergence exists only on targets that have branch divergence, which is why this change matters on those targets such as AMDGPU. On a CPU target, everything is always uniform. So any test needs a GPU target.

Yep, that's all clear. I was thinking more along the lines of if there's some attribute or something that the base handles generically for testing purposes. If there's nothing like that today that's fine.

[bogner]

In D146823#4223630, @sameerds wrote:

In D146823#4223421, @Pierre-vh wrote:

In D146823#4223352, @foad wrote:

If we're going to do this I think we ought to do it properly, by querying UniformityAnalysis. TTI->isAlwaysUniform will only catch a small fraction of the values that are provably uniform.

I agree, but most targets don't care about uniformity so I don't think we can make GVN depend on UA unless we find a way to avoid running the analysis for those targets. No?
Does UA bail out early for non-GPU targets? (It'd be nice if it did that and just returned an empty UniformityInfo instance for those targets, we could then use UA in more places in the middle-end without worrying about performance)

When UA or DA initialize, they query TTI for sources of divergence. On a target with no divergence, they won't find any and hence the analysis should be trivial anyway. The only cost is one O(N) pass over the entire function. We could in principle eliminate that by just querying for TTI.hasBranchDivergence(). But there have been philosophical objections to taking that approach in the past. In general, one day, we would like to move to an implementation where source of divergence are inferred from IR semantics rather than TTI.

The cost of UA will also include pulling in the cost of dependencies, so using UA here would also introduce the cost of at least CycleAnalysis. I don't think we can just dismiss the compile time concern for non-gpu targets without measuring it unfortunately.

[sameerds]

In D146823#4224606, @bogner wrote:

In D146823#4223630, @sameerds wrote:

When UA or DA initialize, they query TTI for sources of divergence. On a target with no divergence, they won't find any and hence the analysis should be trivial anyway. The only cost is one O(N) pass over the entire function. We could in principle eliminate that by just querying for TTI.hasBranchDivergence(). But there have been philosophical objections to taking that approach in the past. In general, one day, we would like to move to an implementation where source of divergence are inferred from IR semantics rather than TTI.

The cost of UA will also include pulling in the cost of dependencies, so using UA here would also introduce the cost of at least CycleAnalysis. I don't think we can just dismiss the compile time concern for non-gpu targets without measuring it unfortunately.

Right. I had not thought of that. But then again, on the new pass manager, we can eliminate this cost by ensuring that CycleAnalysis is retrieved only if any divergence is found.

[bogner]

Use UniformityAnalysis instead of TTI.

TODO:

• Still need to measure compile time impact, especially on non-gpu/non-divergent targets. This might lead to making some changes to make uniformity analysis as cheap as possible on those targets.
• I'll also add a couple more tests for slightly more complicated cases.

[arsenm]

llvm/test/Transforms/GVN/uniform-values.ll

27

no typed pointers in tests

[bogner]

Add new test case and incorporate review feedback

[nikic]

Compile-time: http://llvm-compile-time-tracker.com/compare.php?from=712dfec1781db8aa92782b98cac5517db548b7f9&to=406639396dd168f459ffb5efcac9eaa1db881f56&stat=instructions:u Would certainly be good if UniformityAnalysis were free for non-GPU targets.

llvm/test/Transforms/GVN/AMDGPU/uniform-values.ll

1 ↗

(On Diff #510952)

Use update_test_checks.py.

[foad]

Patch looks good to me modulo the compile time concerns.

[arsenm]

Could another pass undo this instead?

[sameerds]

In D146823#4253084, @arsenm wrote:

Could another pass undo this instead?

I assume you mean "undo" in a good way? That is, instead of depending on uniformity here, have another pass that replaces divergent values with uniform values, specific to targets that have divergence? Would that be like a "uniformity aware" GVN in MIR?

[sameerds]

In D146823#4245264, @nikic wrote:

Compile-time: http://llvm-compile-time-tracker.com/compare.php?from=712dfec1781db8aa92782b98cac5517db548b7f9&to=406639396dd168f459ffb5efcac9eaa1db881f56&stat=instructions:u Would certainly be good if UniformityAnalysis were free for non-GPU targets.

Is this running-time impact a serious enough concern to fix? UniformityAnalysis is special in the sense that it has to be recomputed every time the code changes, at least for now. And it already depends on TTI. So it's not too wrong to just query TTI and immediately return if the target does not have divergence.

llvm/include/llvm/Transforms/Scalar/GVN.h

 class MemoryDependenceResults;
 class MemorySSA;
 class MemorySSAUpdater;
 class NonLocalDepResult;
 class OptimizationRemarkEmitter;
 class PHINode;
 class TargetLibraryInfo;
 class Value;
+
+template <typename _FunctionT> class GenericSSAContext;
+using SSAContext = GenericSSAContext<Function>;
+template <typename ContextT> class GenericUniformityInfo;
+using UniformityInfo = GenericUniformityInfo<SSAContext>;
+
 /// A private "module" namespace for types and utilities used by GVN. These
 /// are implementation details and should not be used by clients.
 namespace gvn LLVM_LIBRARY_VISIBILITY {
 
 struct AvailableValue;
 struct AvailableValueInBlock;
 class GVNLegacyPass;
 

 
 private:
   friend class gvn::GVNLegacyPass;
   friend struct DenseMapInfo<Expression>;
 
   MemoryDependenceResults *MD = nullptr;
   DominatorTree *DT = nullptr;
   const TargetLibraryInfo *TLI = nullptr;
+  const UniformityInfo *UI = nullptr;
   AssumptionCache *AC = nullptr;
   SetVector<BasicBlock *> DeadBlocks;
   OptimizationRemarkEmitter *ORE = nullptr;
   ImplicitControlFlowTracking *ICF = nullptr;
   LoopInfo *LI = nullptr;
   MemorySSAUpdater *MSSAU = nullptr;
 
   ValueTable VN;
private:
   // of BlockRPONumber prior to accessing the contents of BlockRPONumber.
   bool InvalidBlockRPONumbers = true;
 
   using LoadDepVect = SmallVector<NonLocalDepResult, 64>;
   using AvailValInBlkVect = SmallVector<gvn::AvailableValueInBlock, 64>;
   using UnavailBlkVect = SmallVector<BasicBlock *, 64>;
 
   bool runImpl(Function &F, AssumptionCache &RunAC, DominatorTree &RunDT,
-               const TargetLibraryInfo &RunTLI, AAResults &RunAA,
-               MemoryDependenceResults *RunMD, LoopInfo *LI,
+               const TargetLibraryInfo &RunTLI, const UniformityInfo &RunUI,
+               AAResults &RunAA, MemoryDependenceResults *RunMD, LoopInfo *LI,
                OptimizationRemarkEmitter *ORE, MemorySSA *MSSA = nullptr);
 
   /// Push a new Value to the LeaderTable onto the list for its value number.
   void addToLeaderTable(uint32_t N, Value *V, const BasicBlock *BB) {
     LeaderTableEntry &Curr = LeaderTable[N];
     if (!Curr.Val) {
       Curr.Val = V;
       Curr.BB = BB;

llvm/lib/Transforms/Scalar/GVN.cpp

 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/MemoryBuiltins.h"
 #include "llvm/Analysis/MemoryDependenceAnalysis.h"
 #include "llvm/Analysis/MemorySSA.h"
 #include "llvm/Analysis/MemorySSAUpdater.h"
 #include "llvm/Analysis/OptimizationRemarkEmitter.h"
 #include "llvm/Analysis/PHITransAddr.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
+#include "llvm/Analysis/UniformityAnalysis.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/Attributes.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/Constant.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DebugLoc.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"

 PreservedAnalyses GVNPass::run(Function &F, FunctionAnalysisManager &AM) {
   // FIXME: The order of evaluation of these 'getResult' calls is very
   // significant! Re-ordering these variables will cause GVN when run alone to
   // be less effective! We should fix memdep and basic-aa to not exhibit this
   // behavior, but until then don't change the order here.
   auto &AC = AM.getResult<AssumptionAnalysis>(F);
   auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
   auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
+  auto &UI = AM.getResult<UniformityInfoAnalysis>(F);
   auto &AA = AM.getResult<AAManager>(F);
   auto *MemDep =
       isMemDepEnabled() ? &AM.getResult<MemoryDependenceAnalysis>(F) : nullptr;
   auto *LI = AM.getCachedResult<LoopAnalysis>(F);
   auto *MSSA = AM.getCachedResult<MemorySSAAnalysis>(F);
   auto &ORE = AM.getResult<OptimizationRemarkEmitterAnalysis>(F);
-  bool Changed = runImpl(F, AC, DT, TLI, AA, MemDep, LI, &ORE,
+  bool Changed = runImpl(F, AC, DT, TLI, UI, AA, MemDep, LI, &ORE,
                          MSSA ? &MSSA->getMSSA() : nullptr);
   if (!Changed)
     return PreservedAnalyses::all();
   PreservedAnalyses PA;
   PA.preserve<DominatorTreeAnalysis>();
   PA.preserve<TargetLibraryAnalysis>();
+  PA.preserve<UniformityInfoAnalysis>();
   if (MSSA)
     PA.preserve<MemorySSAAnalysis>();
   if (LI)
     PA.preserve<LoopAnalysis>();
   return PA;
 }
 
 void GVNPass::printPipeline(

 
     // If there is no obvious reason to prefer the left-hand side over the
     // right-hand side, ensure the longest lived term is on the right-hand side,
     // so the shortest lived term will be replaced by the longest lived.
     // This tends to expose more simplifications.
     uint32_t LVN = VN.lookupOrAdd(LHS);
     if ((isa<Argument>(LHS) && isa<Argument>(RHS)) ||
         (isa<Instruction>(LHS) && isa<Instruction>(RHS))) {
-      // Move the 'oldest' value to the right-hand side, using the value number
-      // as a proxy for age.
-      uint32_t RVN = VN.lookupOrAdd(RHS);
-      if (LVN < RVN) {
-        std::swap(LHS, RHS);
-        LVN = RVN;
+      // Avoid replacing uniform values with non-uniform values.
+      if (!UI->isUniform(RHS) || UI->isUniform(LHS)) {
+        // Move the 'oldest' value to the right-hand side, using the value
+        // number as a proxy for age.
+        uint32_t RVN = VN.lookupOrAdd(RHS);
+        if (LVN < RVN) {
+          std::swap(LHS, RHS);
+          LVN = RVN;
+        }
       }
     }
 
     // If value numbering later sees that an instruction in the scope is equal
     // to 'LHS' then ensure it will be turned into 'RHS'.  In order to preserve
     // the invariant that instructions only occur in the leader table for their
     // own value number (this is used by removeFromLeaderTable), do not do this
     // if RHS is an instruction (if an instruction in the scope is morphed into

   if (MD && Repl->getType()->isPtrOrPtrVectorTy())
     MD->invalidateCachedPointerInfo(Repl);
   markInstructionForDeletion(I);
   return true;
 }
 
 /// runOnFunction - This is the main transformation entry point for a function.
 bool GVNPass::runImpl(Function &F, AssumptionCache &RunAC, DominatorTree &RunDT,
-                      const TargetLibraryInfo &RunTLI, AAResults &RunAA,
+                      const TargetLibraryInfo &RunTLI,
+                      const UniformityInfo &RunUI, AAResults &RunAA,
                       MemoryDependenceResults *RunMD, LoopInfo *LI,
                       OptimizationRemarkEmitter *RunORE, MemorySSA *MSSA) {
   AC = &RunAC;
   DT = &RunDT;
   VN.setDomTree(DT);
   TLI = &RunTLI;
+  UI = &RunUI;
   VN.setAliasAnalysis(&RunAA);
   MD = RunMD;
   ImplicitControlFlowTracking ImplicitCFT;
   ICF = &ImplicitCFT;
   this->LI = LI;
   VN.setMemDep(MD);
   ORE = RunORE;
   InvalidBlockRPONumbers = true;

 
     auto *LIWP = getAnalysisIfAvailable<LoopInfoWrapperPass>();
 
     auto *MSSAWP = getAnalysisIfAvailable<MemorySSAWrapperPass>();
     return Impl.runImpl(
         F, getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F),
         getAnalysis<DominatorTreeWrapperPass>().getDomTree(),
         getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F),
+        getAnalysis<UniformityInfoWrapperPass>().getUniformityInfo(),
         getAnalysis<AAResultsWrapperPass>().getAAResults(),
         Impl.isMemDepEnabled()
             ? &getAnalysis<MemoryDependenceWrapperPass>().getMemDep()
             : nullptr,
         LIWP ? &LIWP->getLoopInfo() : nullptr,
         &getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE(),
         MSSAWP ? &MSSAWP->getMSSA() : nullptr);
   }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.addRequired<AssumptionCacheTracker>();
     AU.addRequired<DominatorTreeWrapperPass>();
     AU.addRequired<TargetLibraryInfoWrapperPass>();
+    AU.addRequired<UniformityInfoWrapperPass>();
     AU.addRequired<LoopInfoWrapperPass>();
     if (Impl.isMemDepEnabled())
       AU.addRequired<MemoryDependenceWrapperPass>();
     AU.addRequired<AAResultsWrapperPass>();
     AU.addPreserved<DominatorTreeWrapperPass>();
     AU.addPreserved<GlobalsAAWrapperPass>();
     AU.addPreserved<TargetLibraryInfoWrapperPass>();
+    AU.addPreserved<UniformityInfoWrapperPass>();
     AU.addPreserved<LoopInfoWrapperPass>();
     AU.addRequired<OptimizationRemarkEmitterWrapperPass>();
     AU.addPreserved<MemorySSAWrapperPass>();
   }
 
 private:
   GVNPass Impl;
 };
 
 char GVNLegacyPass::ID = 0;
 
 INITIALIZE_PASS_BEGIN(GVNLegacyPass, "gvn", "Global Value Numbering", false, false)
 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
 INITIALIZE_PASS_DEPENDENCY(MemoryDependenceWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(UniformityInfoWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(OptimizationRemarkEmitterWrapperPass)
 INITIALIZE_PASS_END(GVNLegacyPass, "gvn", "Global Value Numbering", false, false)
 
 // The public interface to this file...
 FunctionPass *llvm::createGVNPass(bool NoMemDepAnalysis) {
   return new GVNLegacyPass(NoMemDepAnalysis);
 }

llvm/test/Transforms/GVN/uniform-values.ll

+; REQUIRES: amdgpu-registered-target
+; RUN: opt < %s -mtriple=amdgcn -passes=gvn -S | FileCheck %s
+
+; CHECK-LABEL: @no_replace_uniform_with_non
+define void @no_replace_uniform_with_non(i32* %buf) {
+  %v1 = load i32, i32* %buf
+  %v2 = call i32 @llvm.amdgcn.readfirstlane(i32 %v1)
+  %cond = icmp eq i32 %v1, %v2
+  br i1 %cond, label %matches, label %end
+
+; Make sure we don't replace %v2 with %v1 when %v2 is known to be uniform
+; CHECK-LABEL: matches:
+; CHECK: call void @opaque(i32 %v2)
+matches:
+  call void @opaque(i32 %v2)
+  br label %end
+
+; CHECK-LABEL: end:
+; CHECK: call void @opaque(i32 %v1)
+end:
+  call void @opaque(i32 %v1)
+  ret void
+}
+
+; CHECK-LABEL: @replace_non_uniform_with_uniform
+define void @replace_non_uniform_with_uniform(i32* %buf, i32* %buf2) {
+  %v1 = load i32, i32* %buf
+  %v2 = call i32 @llvm.amdgcn.readfirstlane(i32 %v1)
+  %v3 = load i32, i32* %buf2
+  %cond = icmp eq i32 %v2, %v3
+  br i1 %cond, label %matches, label %end
+
+; CHECK-LABEL: matches:
+; CHECK: call void @opaque(i32 %v2)
+matches:
+  call void @opaque(i32 %v3)
+  br label %end
+
+; CHECK-LABEL: end:
+; CHECK: call void @opaque(i32 %v3)
+end:
+  call void @opaque(i32 %v3)
+  ret void
+}
+
+
+declare i32 @llvm.amdgcn.readfirstlane(i32) nounwind readnone
+declare void @opaque(i32)