1 //===- UniformityAnalysis.cpp ---------------------------------------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 9 #include "llvm/Analysis/UniformityAnalysis.h" 10 #include "llvm/ADT/GenericUniformityImpl.h" 11 #include "llvm/Analysis/CycleAnalysis.h" 12 #include "llvm/Analysis/TargetTransformInfo.h" 13 #include "llvm/IR/Constants.h" 14 #include "llvm/IR/Dominators.h" 15 #include "llvm/IR/InstIterator.h" 16 #include "llvm/IR/Instructions.h" 17 #include "llvm/InitializePasses.h" 18 19 using namespace llvm; 20 21 template <> 22 bool llvm::GenericUniformityAnalysisImpl<SSAContext>::hasDivergentDefs( 23 const Instruction &I) const { 24 return isDivergent((const Value *)&I); 25 } 26 27 template <> 28 bool llvm::GenericUniformityAnalysisImpl<SSAContext>::markDefsDivergent( 29 const Instruction &Instr) { 30 return markDivergent(cast<Value>(&Instr)); 31 } 32 33 template <> void llvm::GenericUniformityAnalysisImpl<SSAContext>::initialize() { 34 for (auto &I : instructions(F)) { 35 if (TTI->isSourceOfDivergence(&I)) 36 markDivergent(I); 37 else if (TTI->isAlwaysUniform(&I)) 38 addUniformOverride(I); 39 } 40 for (auto &Arg : F.args()) { 41 if (TTI->isSourceOfDivergence(&Arg)) { 42 markDivergent(&Arg); 43 } 44 } 45 } 46 47 template <> 48 void llvm::GenericUniformityAnalysisImpl<SSAContext>::pushUsers( 49 const Value *V) { 50 for (const auto *User : V->users()) { 51 if (const auto *UserInstr = dyn_cast<const Instruction>(User)) { 52 markDivergent(*UserInstr); 53 } 54 } 55 } 56 57 template <> 58 void llvm::GenericUniformityAnalysisImpl<SSAContext>::pushUsers( 59 const Instruction &Instr) { 60 assert(!isAlwaysUniform(Instr)); 61 if (Instr.isTerminator()) 62 return; 63 pushUsers(cast<Value>(&Instr)); 64 } 65 66 template <> 67 bool llvm::GenericUniformityAnalysisImpl<SSAContext>::usesValueFromCycle( 68 const Instruction &I, const Cycle &DefCycle) const { 69 assert(!isAlwaysUniform(I)); 70 for (const Use &U : I.operands()) { 71 if (auto *I = dyn_cast<Instruction>(&U)) { 72 if (DefCycle.contains(I->getParent())) 73 return true; 74 } 75 } 76 return false; 77 } 78 79 template <> 80 void llvm::GenericUniformityAnalysisImpl< 81 SSAContext>::propagateTemporalDivergence(const Instruction &I, 82 const Cycle &DefCycle) { 83 if (isDivergent(I)) 84 return; 85 for (auto *User : I.users()) { 86 auto *UserInstr = cast<Instruction>(User); 87 if (DefCycle.contains(UserInstr->getParent())) 88 continue; 89 markDivergent(*UserInstr); 90 } 91 } 92 93 template <> 94 bool llvm::GenericUniformityAnalysisImpl<SSAContext>::isDivergentUse( 95 const Use &U) const { 96 const auto *V = U.get(); 97 if (isDivergent(V)) 98 return true; 99 if (const auto *DefInstr = dyn_cast<Instruction>(V)) { 100 const auto *UseInstr = cast<Instruction>(U.getUser()); 101 return isTemporalDivergent(*UseInstr->getParent(), *DefInstr); 102 } 103 return false; 104 } 105 106 // This ensures explicit instantiation of 107 // GenericUniformityAnalysisImpl::ImplDeleter::operator() 108 template class llvm::GenericUniformityInfo<SSAContext>; 109 template struct llvm::GenericUniformityAnalysisImplDeleter< 110 llvm::GenericUniformityAnalysisImpl<SSAContext>>; 111 112 //===----------------------------------------------------------------------===// 113 // UniformityInfoAnalysis and related pass implementations 114 //===----------------------------------------------------------------------===// 115 116 llvm::UniformityInfo UniformityInfoAnalysis::run(Function &F, 117 FunctionAnalysisManager &FAM) { 118 auto &DT = FAM.getResult<DominatorTreeAnalysis>(F); 119 auto &TTI = FAM.getResult<TargetIRAnalysis>(F); 120 auto &CI = FAM.getResult<CycleAnalysis>(F); 121 UniformityInfo UI{DT, CI, &TTI}; 122 // Skip computation if we can assume everything is uniform. 123 if (TTI.hasBranchDivergence(&F)) 124 UI.compute(); 125 126 return UI; 127 } 128 129 AnalysisKey UniformityInfoAnalysis::Key; 130 131 UniformityInfoPrinterPass::UniformityInfoPrinterPass(raw_ostream &OS) 132 : OS(OS) {} 133 134 PreservedAnalyses UniformityInfoPrinterPass::run(Function &F, 135 FunctionAnalysisManager &AM) { 136 OS << "UniformityInfo for function '" << F.getName() << "':\n"; 137 AM.getResult<UniformityInfoAnalysis>(F).print(OS); 138 139 return PreservedAnalyses::all(); 140 } 141 142 //===----------------------------------------------------------------------===// 143 // UniformityInfoWrapperPass Implementation 144 //===----------------------------------------------------------------------===// 145 146 char UniformityInfoWrapperPass::ID = 0; 147 148 UniformityInfoWrapperPass::UniformityInfoWrapperPass() : FunctionPass(ID) { 149 initializeUniformityInfoWrapperPassPass(*PassRegistry::getPassRegistry()); 150 } 151 152 INITIALIZE_PASS_BEGIN(UniformityInfoWrapperPass, "uniformity", 153 "Uniformity Analysis", true, true) 154 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) 155 INITIALIZE_PASS_DEPENDENCY(CycleInfoWrapperPass) 156 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass) 157 INITIALIZE_PASS_END(UniformityInfoWrapperPass, "uniformity", 158 "Uniformity Analysis", true, true) 159 160 void UniformityInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { 161 AU.setPreservesAll(); 162 AU.addRequired<DominatorTreeWrapperPass>(); 163 AU.addRequiredTransitive<CycleInfoWrapperPass>(); 164 AU.addRequired<TargetTransformInfoWrapperPass>(); 165 } 166 167 bool UniformityInfoWrapperPass::runOnFunction(Function &F) { 168 auto &cycleInfo = getAnalysis<CycleInfoWrapperPass>().getResult(); 169 auto &domTree = getAnalysis<DominatorTreeWrapperPass>().getDomTree(); 170 auto &targetTransformInfo = 171 getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F); 172 173 m_function = &F; 174 m_uniformityInfo = UniformityInfo{domTree, cycleInfo, &targetTransformInfo}; 175 176 // Skip computation if we can assume everything is uniform. 177 if (targetTransformInfo.hasBranchDivergence(m_function)) 178 m_uniformityInfo.compute(); 179 180 return false; 181 } 182 183 void UniformityInfoWrapperPass::print(raw_ostream &OS, const Module *) const { 184 OS << "UniformityInfo for function '" << m_function->getName() << "':\n"; 185 } 186 187 void UniformityInfoWrapperPass::releaseMemory() { 188 m_uniformityInfo = UniformityInfo{}; 189 m_function = nullptr; 190 } 191