1 // Copyright (c) 2023 Google Inc. 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_OPT_DEDUPE_INTERLOCK_INVOCATION_PASS_H_ 16 #define SOURCE_OPT_DEDUPE_INTERLOCK_INVOCATION_PASS_H_ 17 18 #include <algorithm> 19 #include <array> 20 #include <functional> 21 #include <optional> 22 #include <unordered_map> 23 #include <unordered_set> 24 25 #include "source/enum_set.h" 26 #include "source/extensions.h" 27 #include "source/opt/ir_context.h" 28 #include "source/opt/module.h" 29 #include "source/opt/pass.h" 30 #include "source/spirv_target_env.h" 31 32 namespace spvtools { 33 namespace opt { 34 35 // This pass will ensure that an entry point will only have at most one 36 // OpBeginInterlockInvocationEXT and one OpEndInterlockInvocationEXT, in that 37 // order 38 class InvocationInterlockPlacementPass : public Pass { 39 public: InvocationInterlockPlacementPass()40 InvocationInterlockPlacementPass() {} 41 InvocationInterlockPlacementPass(const InvocationInterlockPlacementPass&) = 42 delete; 43 InvocationInterlockPlacementPass(InvocationInterlockPlacementPass&&) = delete; 44 name()45 const char* name() const override { return "dedupe-interlock-invocation"; } 46 Status Process() override; 47 48 private: 49 using BlockSet = std::unordered_set<uint32_t>; 50 51 // Specifies whether a function originally had a begin or end instruction. 52 struct ExtractionResult { 53 bool had_begin : 1; 54 bool had_end : 2; 55 }; 56 57 // Check if a block has only a single next block, depending on the directing 58 // that we are traversing the CFG. If reverse_cfg is true, we are walking 59 // forward through the CFG, and will return if the block has only one 60 // successor. Otherwise, we are walking backward through the CFG, and will 61 // return if the block has only one predecessor. 62 bool hasSingleNextBlock(uint32_t block_id, bool reverse_cfg); 63 64 // Iterate over each of a block's predecessors or successors, depending on 65 // direction. If reverse_cfg is true, we are walking forward through the CFG, 66 // and need to iterate over the successors. Otherwise, we are walking backward 67 // through the CFG, and need to iterate over the predecessors. 68 void forEachNext(uint32_t block_id, bool reverse_cfg, 69 std::function<void(uint32_t)> f); 70 71 // Add either a begin or end instruction to the edge of the basic block. If 72 // at_end is true, add the instruction to the end of the block; otherwise add 73 // the instruction to the beginning of the basic block. 74 void addInstructionAtBlockBoundary(BasicBlock* block, spv::Op opcode, 75 bool at_end); 76 77 // Remove every OpBeginInvocationInterlockEXT instruction in block after the 78 // first. Returns whether any instructions were removed. 79 bool killDuplicateBegin(BasicBlock* block); 80 // Remove every OpBeginInvocationInterlockEXT instruction in block before the 81 // last. Returns whether any instructions were removed. 82 bool killDuplicateEnd(BasicBlock* block); 83 84 // Records whether a function will potentially execute a begin or end 85 // instruction. 86 void recordBeginOrEndInFunction(Function* func); 87 88 // Recursively removes any begin or end instructions from func and any 89 // function func calls. Returns whether any instructions were removed. 90 bool removeBeginAndEndInstructionsFromFunction(Function* func); 91 92 // For every function call in any of the passed blocks, move any begin or end 93 // instructions outside of the function call. Returns whether any extractions 94 // occurred. 95 bool extractInstructionsFromCalls(std::vector<BasicBlock*> blocks); 96 97 // Finds the sets of blocks that contain OpBeginInvocationInterlockEXT and 98 // OpEndInvocationInterlockEXT, storing them in the member variables begin_ 99 // and end_ respectively. 100 void recordExistingBeginAndEndBlock(std::vector<BasicBlock*> blocks); 101 102 // Compute the set of blocks including or after the barrier instruction, and 103 // the set of blocks with any previous blocks inside the barrier instruction. 104 // If reverse_cfg is true, move forward through the CFG, computing 105 // after_begin_ and predecessors_after_begin_computing after_begin_ and 106 // predecessors_after_begin_, otherwise, move backward through the CFG, 107 // computing before_end_ and successors_before_end_. 108 BlockSet computeReachableBlocks(BlockSet& in_set, 109 const BlockSet& starting_nodes, 110 bool reverse_cfg); 111 112 // Remove unneeded begin and end instructions in block. 113 bool removeUnneededInstructions(BasicBlock* block); 114 115 // Given a block which branches to multiple successors, and a specific 116 // successor, creates a new empty block, and update the branch instruction to 117 // branch to the new block instead. 118 BasicBlock* splitEdge(BasicBlock* block, uint32_t succ_id); 119 120 // For the edge from block to next_id, places a begin or end instruction on 121 // the edge, based on the direction we are walking the CFG, specified in 122 // reverse_cfg. 123 bool placeInstructionsForEdge(BasicBlock* block, uint32_t next_id, 124 BlockSet& inside, BlockSet& previous_inside, 125 spv::Op opcode, bool reverse_cfg); 126 // Calls placeInstructionsForEdge for each edge in block. 127 bool placeInstructions(BasicBlock* block); 128 129 // Processes a single fragment shader entry function. 130 bool processFragmentShaderEntry(Function* entry_func); 131 132 // Returns whether the module has the SPV_EXT_fragment_shader_interlock 133 // extension and one of the FragmentShader*InterlockEXT capabilities. 134 bool isFragmentShaderInterlockEnabled(); 135 136 // Maps a function to whether that function originally held a begin or end 137 // instruction. 138 std::unordered_map<Function*, ExtractionResult> extracted_functions_; 139 140 // The set of blocks which have an OpBeginInvocationInterlockEXT instruction. 141 BlockSet begin_; 142 // The set of blocks which have an OpEndInvocationInterlockEXT instruction. 143 BlockSet end_; 144 // The set of blocks which either have a begin instruction, or have a 145 // predecessor which has a begin instruction. 146 BlockSet after_begin_; 147 // The set of blocks which either have an end instruction, or have a successor 148 // which have an end instruction. 149 BlockSet before_end_; 150 // The set of blocks which have a predecessor in after_begin_. 151 BlockSet predecessors_after_begin_; 152 // The set of blocks which have a successor in before_end_. 153 BlockSet successors_before_end_; 154 }; 155 156 } // namespace opt 157 } // namespace spvtools 158 #endif // SOURCE_OPT_DEDUPE_INTERLOCK_INVOCATION_PASS_H_ 159