1 // Copyright (c) 2018 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 #include "operand_to_dominating_id_reduction_pass.h" 16 #include "change_operand_reduction_opportunity.h" 17 #include "source/opt/instruction.h" 18 19 namespace spvtools { 20 namespace reduce { 21 22 using namespace opt; 23 24 std::vector<std::unique_ptr<ReductionOpportunity>> 25 OperandToDominatingIdReductionPass::GetAvailableOpportunities( 26 opt::IRContext* context) const { 27 std::vector<std::unique_ptr<ReductionOpportunity>> result; 28 29 // Go through every instruction in every block, considering it as a potential 30 // dominator of other instructions. We choose this order for two reasons: 31 // 32 // (1) it is profitable for multiple opportunities to replace the same id x by 33 // different dominating ids y and z to be discontiguous, as they are 34 // incompatible. 35 // 36 // (2) We want to prioritise opportunities to replace an id with a more 37 // distant dominator. Intuitively, in a human-readable programming language 38 // if we have a complex expression e with many sub-expressions, we would like 39 // to prioritise replacing e with its smallest sub-expressions; generalising 40 // this idea to dominating ids this roughly corresponds to more distant 41 // dominators. 42 for (auto& function : *context->module()) { 43 for (auto dominating_block = function.begin(); 44 dominating_block != function.end(); ++dominating_block) { 45 for (auto& dominating_inst : *dominating_block) { 46 if (dominating_inst.HasResultId() && dominating_inst.type_id()) { 47 // Consider replacing any operand with matching type in a dominated 48 // instruction with the id generated by this instruction. 49 GetOpportunitiesForDominatingInst( 50 &result, &dominating_inst, dominating_block, &function, context); 51 } 52 } 53 } 54 } 55 return result; 56 } 57 58 void OperandToDominatingIdReductionPass::GetOpportunitiesForDominatingInst( 59 std::vector<std::unique_ptr<ReductionOpportunity>>* opportunities, 60 opt::Instruction* candidate_dominator, 61 opt::Function::iterator candidate_dominator_block, opt::Function* function, 62 opt::IRContext* context) const { 63 assert(candidate_dominator->HasResultId()); 64 assert(candidate_dominator->type_id()); 65 auto dominator_analysis = context->GetDominatorAnalysis(function); 66 // SPIR-V requires a block to precede all blocks it dominates, so it suffices 67 // to search from the candidate dominator block onwards. 68 for (auto block = candidate_dominator_block; block != function->end(); 69 ++block) { 70 if (!dominator_analysis->Dominates(&*candidate_dominator_block, &*block)) { 71 // If the candidate dominator block doesn't dominate this block then there 72 // cannot be any of the desired reduction opportunities in this block. 73 continue; 74 } 75 for (auto& inst : *block) { 76 // We iterate through the operands using an explicit index (rather 77 // than using a lambda) so that we use said index in the construction 78 // of a ChangeOperandReductionOpportunity 79 for (uint32_t index = 0; index < inst.NumOperands(); index++) { 80 const auto& operand = inst.GetOperand(index); 81 if (spvIsInIdType(operand.type)) { 82 const auto id = operand.words[0]; 83 auto def = context->get_def_use_mgr()->GetDef(id); 84 assert(def); 85 if (!context->get_instr_block(def)) { 86 // The definition does not come from a block; e.g. it might be a 87 // constant. It is thus not relevant to this pass. 88 continue; 89 } 90 // Sanity check that we don't get here if the argument is a constant. 91 assert(!context->get_constant_mgr()->GetConstantFromInst(def)); 92 if (def->type_id() != candidate_dominator->type_id()) { 93 // The types need to match. 94 continue; 95 } 96 if (candidate_dominator != def && 97 dominator_analysis->Dominates(candidate_dominator, def)) { 98 // A hit: the candidate dominator strictly dominates the definition. 99 opportunities->push_back( 100 MakeUnique<ChangeOperandReductionOpportunity>( 101 &inst, index, candidate_dominator->result_id())); 102 } 103 } 104 } 105 } 106 } 107 } 108 109 std::string OperandToDominatingIdReductionPass::GetName() const { 110 return "OperandToDominatingIdReductionPass"; 111 } 112 113 } // namespace reduce 114 } // namespace spvtools 115
