1 // Copyright (c) 2019 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 #include "source/reduce/remove_block_reduction_opportunity_finder.h"
16
17 #include "source/reduce/remove_block_reduction_opportunity.h"
18
19 namespace spvtools {
20 namespace reduce {
21
GetName() const22 std::string RemoveBlockReductionOpportunityFinder::GetName() const {
23 return "RemoveBlockReductionOpportunityFinder";
24 }
25
26 std::vector<std::unique_ptr<ReductionOpportunity>>
GetAvailableOpportunities(opt::IRContext * context,uint32_t target_function) const27 RemoveBlockReductionOpportunityFinder::GetAvailableOpportunities(
28 opt::IRContext* context, uint32_t target_function) const {
29 std::vector<std::unique_ptr<ReductionOpportunity>> result;
30
31 // Consider every block in every relevant function.
32 for (auto* function : GetTargetFunctions(context, target_function)) {
33 for (auto bi = function->begin(); bi != function->end(); ++bi) {
34 if (IsBlockValidOpportunity(context, function, &bi)) {
35 result.push_back(MakeUnique<RemoveBlockReductionOpportunity>(
36 context, function, &*bi));
37 }
38 }
39 }
40 return result;
41 }
42
IsBlockValidOpportunity(opt::IRContext * context,opt::Function * function,opt::Function::iterator * bi)43 bool RemoveBlockReductionOpportunityFinder::IsBlockValidOpportunity(
44 opt::IRContext* context, opt::Function* function,
45 opt::Function::iterator* bi) {
46 assert(*bi != function->end() && "Block iterator was out of bounds");
47
48 // Don't remove first block; we don't want to end up with no blocks.
49 if (*bi == function->begin()) {
50 return false;
51 }
52
53 // Don't remove blocks with references.
54 if (context->get_def_use_mgr()->NumUsers((*bi)->id()) > 0) {
55 return false;
56 }
57
58 // Don't remove blocks whose instructions have outside references.
59 if (!BlockInstructionsHaveNoOutsideReferences(context, *bi)) {
60 return false;
61 }
62
63 return true;
64 }
65
66 bool RemoveBlockReductionOpportunityFinder::
BlockInstructionsHaveNoOutsideReferences(opt::IRContext * context,const opt::Function::iterator & bi)67 BlockInstructionsHaveNoOutsideReferences(
68 opt::IRContext* context, const opt::Function::iterator& bi) {
69 // Get all instructions in block.
70 std::unordered_set<uint32_t> instructions_in_block;
71 for (const opt::Instruction& instruction : *bi) {
72 instructions_in_block.insert(instruction.unique_id());
73 }
74
75 // For each instruction...
76 for (const opt::Instruction& instruction : *bi) {
77 // For each use of the instruction...
78 bool no_uses_outside_block = context->get_def_use_mgr()->WhileEachUser(
79 &instruction, [&instructions_in_block](opt::Instruction* user) -> bool {
80 // If the use is in this block, continue (return true). Otherwise, we
81 // found an outside use; return false (and stop).
82 return instructions_in_block.find(user->unique_id()) !=
83 instructions_in_block.end();
84 });
85
86 if (!no_uses_outside_block) {
87 return false;
88 }
89 }
90
91 return true;
92 }
93
94 } // namespace reduce
95 } // namespace spvtools
96