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>>
GetAvailableOpportunities(opt::IRContext * context) const25 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
GetOpportunitiesForDominatingInst(std::vector<std::unique_ptr<ReductionOpportunity>> * opportunities,opt::Instruction * candidate_dominator,opt::Function::iterator candidate_dominator_block,opt::Function * function,opt::IRContext * context) const58 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
GetName() const109 std::string OperandToDominatingIdReductionPass::GetName() const {
110 return "OperandToDominatingIdReductionPass";
111 }
112
113 } // namespace reduce
114 } // namespace spvtools
115