1// Copyright (c) 2018 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_OPT_REGISTER_PRESSURE_H_
16#define SOURCE_OPT_REGISTER_PRESSURE_H_
17
18#include <unordered_map>
19#include <unordered_set>
20#include <utility>
21#include <vector>
22
23#include "source/opt/function.h"
24#include "source/opt/types.h"
25
26namespace spvtools {
27namespace opt {
28
29class IRContext;
30class Loop;
31class LoopDescriptor;
32
33// Handles the register pressure of a function for different regions (function,
34// loop, basic block). It also contains some utilities to foresee the register
35// pressure following code transformations.
36class RegisterLiveness {
37 public:
38 // Classification of SSA registers.
39 struct RegisterClass {
40 analysis::Type* type_;
41 bool is_uniform_;
42
43 bool operator==(const RegisterClass& rhs) const {
44 return std::tie(type_, is_uniform_) ==
45 std::tie(rhs.type_, rhs.is_uniform_);
46 }
47 };
48
49 struct RegionRegisterLiveness {
50 using LiveSet = std::unordered_set<Instruction*>;
51 using RegClassSetTy = std::vector<std::pair<RegisterClass, size_t>>;
52
53 // SSA register live when entering the basic block.
54 LiveSet live_in_;
55 // SSA register live when exiting the basic block.
56 LiveSet live_out_;
57
58 // Maximum number of required registers.
59 size_t used_registers_;
60 // Break down of the number of required registers per class of register.
61 RegClassSetTy registers_classes_;
62
63 void Clear() {
64 live_out_.clear();
65 live_in_.clear();
66 used_registers_ = 0;
67 registers_classes_.clear();
68 }
69
70 void AddRegisterClass(const RegisterClass& reg_class) {
71 auto it = std::find_if(
72 registers_classes_.begin(), registers_classes_.end(),
73 [&reg_class](const std::pair<RegisterClass, size_t>& class_count) {
74 return class_count.first == reg_class;
75 });
76 if (it != registers_classes_.end()) {
77 it->second++;
78 } else {
79 registers_classes_.emplace_back(std::move(reg_class),
80 static_cast<size_t>(1));
81 }
82 }
83
84 void AddRegisterClass(Instruction* insn);
85 };
86
87 RegisterLiveness(IRContext* context, Function* f) : context_(context) {
88 Analyze(f);
89 }
90
91 // Returns liveness and register information for the basic block |bb|. If no
92 // entry exist for the basic block, the function returns null.
93 const RegionRegisterLiveness* Get(const BasicBlock* bb) const {
94 return Get(bb->id());
95 }
96
97 // Returns liveness and register information for the basic block id |bb_id|.
98 // If no entry exist for the basic block, the function returns null.
99 const RegionRegisterLiveness* Get(uint32_t bb_id) const {
100 RegionRegisterLivenessMap::const_iterator it = block_pressure_.find(bb_id);
101 if (it != block_pressure_.end()) {
102 return &it->second;
103 }
104 return nullptr;
105 }
106
107 IRContext* GetContext() const { return context_; }
108
109 // Returns liveness and register information for the basic block |bb|. If no
110 // entry exist for the basic block, the function returns null.
111 RegionRegisterLiveness* Get(const BasicBlock* bb) { return Get(bb->id()); }
112
113 // Returns liveness and register information for the basic block id |bb_id|.
114 // If no entry exist for the basic block, the function returns null.
115 RegionRegisterLiveness* Get(uint32_t bb_id) {
116 RegionRegisterLivenessMap::iterator it = block_pressure_.find(bb_id);
117 if (it != block_pressure_.end()) {
118 return &it->second;
119 }
120 return nullptr;
121 }
122
123 // Returns liveness and register information for the basic block id |bb_id| or
124 // create a new empty entry if no entry already existed.
125 RegionRegisterLiveness* GetOrInsert(uint32_t bb_id) {
126 return &block_pressure_[bb_id];
127 }
128
129 // Compute the register pressure for the |loop| and store the result into
130 // |reg_pressure|. The live-in set corresponds to the live-in set of the
131 // header block, the live-out set of the loop corresponds to the union of the
132 // live-in sets of each exit basic block.
133 void ComputeLoopRegisterPressure(const Loop& loop,
134 RegionRegisterLiveness* reg_pressure) const;
135
136 // Estimate the register pressure for the |l1| and |l2| as if they were making
137 // one unique loop. The result is stored into |simulation_result|.
138 void SimulateFusion(const Loop& l1, const Loop& l2,
139 RegionRegisterLiveness* simulation_result) const;
140
141 // Estimate the register pressure of |loop| after it has been fissioned
142 // according to |moved_instructions| and |copied_instructions|. The function
143 // assumes that the fission creates a new loop before |loop|, moves any
144 // instructions present inside |moved_instructions| and copies any
145 // instructions present inside |copied_instructions| into this new loop.
146 // The set |loop1_sim_result| store the simulation result of the loop with the
147 // moved instructions. The set |loop2_sim_result| store the simulation result
148 // of the loop with the removed instructions.
149 void SimulateFission(
150 const Loop& loop,
151 const std::unordered_set<Instruction*>& moved_instructions,
152 const std::unordered_set<Instruction*>& copied_instructions,
153 RegionRegisterLiveness* loop1_sim_result,
154 RegionRegisterLiveness* loop2_sim_result) const;
155
156 private:
157 using RegionRegisterLivenessMap =
158 std::unordered_map<uint32_t, RegionRegisterLiveness>;
159
160 IRContext* context_;
161 RegionRegisterLivenessMap block_pressure_;
162
163 void Analyze(Function* f);
164};
165
166// Handles the register pressure of a function for different regions (function,
167// loop, basic block). It also contains some utilities to foresee the register
168// pressure following code transformations.
169class LivenessAnalysis {
170 using LivenessAnalysisMap =
171 std::unordered_map<const Function*, RegisterLiveness>;
172
173 public:
174 LivenessAnalysis(IRContext* context) : context_(context) {}
175
176 // Computes the liveness analysis for the function |f| and cache the result.
177 // If the analysis was performed for this function, then the cached analysis
178 // is returned.
179 const RegisterLiveness* Get(Function* f) {
180 LivenessAnalysisMap::iterator it = analysis_cache_.find(f);
181 if (it != analysis_cache_.end()) {
182 return &it->second;
183 }
184 return &analysis_cache_.emplace(f, RegisterLiveness{context_, f})
185 .first->second;
186 }
187
188 private:
189 IRContext* context_;
190 LivenessAnalysisMap analysis_cache_;
191};
192
193} // namespace opt
194} // namespace spvtools
195
196#endif // SOURCE_OPT_REGISTER_PRESSURE_H_
197