1 // Copyright (c) 2021 Google LLC. 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); 4 // you may not use this file except in compliance with the License. 5 // You may obtain a copy of the License at 6 // 7 // http://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS IS" BASIS, 11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 // See the License for the specific language governing permissions and 13 // limitations under the License. 14 15 #ifndef SOURCE_LINT_DIVERGENCE_ANALYSIS_H_ 16 #define SOURCE_LINT_DIVERGENCE_ANALYSIS_H_ 17 18 #include <cstdint> 19 #include <ostream> 20 #include <unordered_map> 21 22 #include "source/opt/basic_block.h" 23 #include "source/opt/control_dependence.h" 24 #include "source/opt/dataflow.h" 25 #include "source/opt/function.h" 26 #include "source/opt/instruction.h" 27 28 namespace spvtools { 29 namespace lint { 30 31 // Computes the static divergence level for blocks (control flow) and values. 32 // 33 // A value is uniform if all threads that execute it are guaranteed to have the 34 // same value. Similarly, a value is partially uniform if this is true only 35 // within each derivative group. If neither apply, it is divergent. 36 // 37 // Control flow through a block is uniform if for any possible execution and 38 // point in time, all threads are executing it, or no threads are executing it. 39 // In particular, it is never possible for some threads to be inside the block 40 // and some threads not executing. 41 // TODO(kuhar): Clarify the difference between uniform, divergent, and 42 // partially-uniform execution in this analysis. 43 // 44 // Caveat: 45 // As we use control dependence to determine how divergence is propagated, this 46 // analysis can be overly permissive when the merge block for a conditional 47 // branch or switch is later than (strictly postdominates) the expected merge 48 // block, which is the immediate postdominator. However, this is not expected to 49 // be a problem in practice, given that SPIR-V is generally output by compilers 50 // and other automated tools, which would assign the earliest possible merge 51 // block, rather than written by hand. 52 // TODO(kuhar): Handle late merges. 53 class DivergenceAnalysis : public opt::ForwardDataFlowAnalysis { 54 public: 55 // The tightest (most uniform) level of divergence that can be determined 56 // statically for a value or control flow for a block. 57 // 58 // The values are ordered such that A > B means that A is potentially more 59 // divergent than B. 60 // TODO(kuhar): Rename |PartiallyUniform' to something less confusing. For 61 // example, the enum could be based on scopes. 62 enum class DivergenceLevel { 63 // The value or control flow is uniform across the entire invocation group. 64 kUniform = 0, 65 // The value or control flow is uniform across the derivative group, but not 66 // the invocation group. 67 kPartiallyUniform = 1, 68 // The value or control flow is not statically uniform. 69 kDivergent = 2, 70 }; 71 DivergenceAnalysis(opt::IRContext & context)72 DivergenceAnalysis(opt::IRContext& context) 73 : ForwardDataFlowAnalysis(context, LabelPosition::kLabelsAtEnd) {} 74 75 // Returns the divergence level for the given value (non-label instructions), 76 // or control flow for the given block. GetDivergenceLevel(uint32_t id)77 DivergenceLevel GetDivergenceLevel(uint32_t id) { 78 auto it = divergence_.find(id); 79 if (it == divergence_.end()) { 80 return DivergenceLevel::kUniform; 81 } 82 return it->second; 83 } 84 85 // Returns the divergence source for the given id. The following types of 86 // divergence flows from A to B are possible: 87 // 88 // data -> data: A is used as an operand in the definition of B. 89 // data -> control: B is control-dependent on a branch with condition A. 90 // control -> data: B is a OpPhi instruction in which A is a block operand. 91 // control -> control: B is control-dependent on A. GetDivergenceSource(uint32_t id)92 uint32_t GetDivergenceSource(uint32_t id) { 93 auto it = divergence_source_.find(id); 94 if (it == divergence_source_.end()) { 95 return 0; 96 } 97 return it->second; 98 } 99 100 // Returns the dependence source for the control dependence for the given id. 101 // This only exists for data -> control edges. 102 // 103 // In other words, if block 2 is dependent on block 1 due to value 3 (e.g. 104 // block 1 terminates with OpBranchConditional %3 %2 %4): 105 // * GetDivergenceSource(2) = 3 106 // * GetDivergenceDependenceSource(2) = 1 107 // 108 // Returns 0 if not applicable. GetDivergenceDependenceSource(uint32_t id)109 uint32_t GetDivergenceDependenceSource(uint32_t id) { 110 auto it = divergence_dependence_source_.find(id); 111 if (it == divergence_dependence_source_.end()) { 112 return 0; 113 } 114 return it->second; 115 } 116 InitializeWorklist(opt::Function * function,bool is_first_iteration)117 void InitializeWorklist(opt::Function* function, 118 bool is_first_iteration) override { 119 // Since |EnqueueSuccessors| is complete, we only need one pass. 120 if (is_first_iteration) { 121 Setup(function); 122 opt::ForwardDataFlowAnalysis::InitializeWorklist(function, true); 123 } 124 } 125 126 void EnqueueSuccessors(opt::Instruction* inst) override; 127 128 VisitResult Visit(opt::Instruction* inst) override; 129 130 private: 131 VisitResult VisitBlock(uint32_t id); 132 VisitResult VisitInstruction(opt::Instruction* inst); 133 134 // Computes the divergence level for the result of the given instruction 135 // based on the current state of the analysis. This is always an 136 // underapproximation, which will be improved as the analysis proceeds. 137 DivergenceLevel ComputeInstructionDivergence(opt::Instruction* inst); 138 139 // Computes the divergence level for a variable, which is used for loads. 140 DivergenceLevel ComputeVariableDivergence(opt::Instruction* var); 141 142 // Initializes data structures for performing dataflow on the given function. 143 void Setup(opt::Function* function); 144 145 std::unordered_map<uint32_t, DivergenceLevel> divergence_; 146 std::unordered_map<uint32_t, uint32_t> divergence_source_; 147 std::unordered_map<uint32_t, uint32_t> divergence_dependence_source_; 148 149 // Stores the result of following unconditional branches starting from the 150 // given block. This is used to detect when reconvergence needs to be 151 // accounted for. 152 std::unordered_map<uint32_t, uint32_t> follow_unconditional_branches_; 153 154 opt::ControlDependenceAnalysis cd_; 155 }; 156 157 std::ostream& operator<<(std::ostream& os, 158 DivergenceAnalysis::DivergenceLevel level); 159 160 } // namespace lint 161 } // namespace spvtools 162 163 #endif // SOURCE_LINT_DIVERGENCE_ANALYSIS_H_ 164