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#include "source/opt/register_pressure.h"
16
17#include <algorithm>
18#include <iterator>
19
20#include "source/opt/cfg.h"
21#include "source/opt/def_use_manager.h"
22#include "source/opt/dominator_tree.h"
23#include "source/opt/function.h"
24#include "source/opt/ir_context.h"
25#include "source/opt/iterator.h"
26
27namespace spvtools {
28namespace opt {
29
30namespace {
31// Predicate for the FilterIterator to only consider instructions that are not
32// phi instructions defined in the basic block |bb|.
33class ExcludePhiDefinedInBlock {
34 public:
35 ExcludePhiDefinedInBlock(IRContext* context, const BasicBlock* bb)
36 : context_(context), bb_(bb) {}
37
38 bool operator()(Instruction* insn) const {
39 return !(insn->opcode() == SpvOpPhi &&
40 context_->get_instr_block(insn) == bb_);
41 }
42
43 private:
44 IRContext* context_;
45 const BasicBlock* bb_;
46};
47
48// Returns true if |insn| generates a SSA register that is likely to require a
49// physical register.
50bool CreatesRegisterUsage(Instruction* insn) {
51 if (!insn->HasResultId()) return false;
52 if (insn->opcode() == SpvOpUndef) return false;
53 if (IsConstantInst(insn->opcode())) return false;
54 if (insn->opcode() == SpvOpLabel) return false;
55 return true;
56}
57
58// Compute the register liveness for each basic block of a function. This also
59// fill-up some information about the pick register usage and a break down of
60// register usage. This implements: "A non-iterative data-flow algorithm for
61// computing liveness sets in strict ssa programs" from Boissinot et al.
62class ComputeRegisterLiveness {
63 public:
64 ComputeRegisterLiveness(RegisterLiveness* reg_pressure, Function* f)
65 : reg_pressure_(reg_pressure),
66 context_(reg_pressure->GetContext()),
67 function_(f),
68 cfg_(*reg_pressure->GetContext()->cfg()),
69 def_use_manager_(*reg_pressure->GetContext()->get_def_use_mgr()),
70 dom_tree_(
71 reg_pressure->GetContext()->GetDominatorAnalysis(f)->GetDomTree()),
72 loop_desc_(*reg_pressure->GetContext()->GetLoopDescriptor(f)) {}
73
74 // Computes the register liveness for |function_| and then estimate the
75 // register usage. The liveness algorithm works in 2 steps:
76 // - First, compute the liveness for each basic blocks, but will ignore any
77 // back-edge;
78 // - Second, walk loop forest to propagate registers crossing back-edges
79 // (add iterative values into the liveness set).
80 void Compute() {
81 for (BasicBlock& start_bb : *function_) {
82 if (reg_pressure_->Get(start_bb.id()) != nullptr) {
83 continue;
84 }
85 cfg_.ForEachBlockInPostOrder(&start_bb, [this](BasicBlock* bb) {
86 if (reg_pressure_->Get(bb->id()) == nullptr) {
87 ComputePartialLiveness(bb);
88 }
89 });
90 }
91 DoLoopLivenessUnification();
92 EvaluateRegisterRequirements();
93 }
94
95 private:
96 // Registers all SSA register used by successors of |bb| in their phi
97 // instructions.
98 void ComputePhiUses(const BasicBlock& bb,
99 RegisterLiveness::RegionRegisterLiveness::LiveSet* live) {
100 uint32_t bb_id = bb.id();
101 bb.ForEachSuccessorLabel([live, bb_id, this](uint32_t sid) {
102 BasicBlock* succ_bb = cfg_.block(sid);
103 succ_bb->ForEachPhiInst([live, bb_id, this](const Instruction* phi) {
104 for (uint32_t i = 0; i < phi->NumInOperands(); i += 2) {
105 if (phi->GetSingleWordInOperand(i + 1) == bb_id) {
106 Instruction* insn_op =
107 def_use_manager_.GetDef(phi->GetSingleWordInOperand(i));
108 if (CreatesRegisterUsage(insn_op)) {
109 live->insert(insn_op);
110 break;
111 }
112 }
113 }
114 });
115 });
116 }
117
118 // Computes register liveness for each basic blocks but ignores all
119 // back-edges.
120 void ComputePartialLiveness(BasicBlock* bb) {
121 assert(reg_pressure_->Get(bb) == nullptr &&
122 "Basic block already processed");
123
124 RegisterLiveness::RegionRegisterLiveness* live_inout =
125 reg_pressure_->GetOrInsert(bb->id());
126 ComputePhiUses(*bb, &live_inout->live_out_);
127
128 const BasicBlock* cbb = bb;
129 cbb->ForEachSuccessorLabel([&live_inout, bb, this](uint32_t sid) {
130 // Skip back edges.
131 if (dom_tree_.Dominates(sid, bb->id())) {
132 return;
133 }
134
135 BasicBlock* succ_bb = cfg_.block(sid);
136 RegisterLiveness::RegionRegisterLiveness* succ_live_inout =
137 reg_pressure_->Get(succ_bb);
138 assert(succ_live_inout &&
139 "Successor liveness analysis was not performed");
140
141 ExcludePhiDefinedInBlock predicate(context_, succ_bb);
142 auto filter =
143 MakeFilterIteratorRange(succ_live_inout->live_in_.begin(),
144 succ_live_inout->live_in_.end(), predicate);
145 live_inout->live_out_.insert(filter.begin(), filter.end());
146 });
147
148 live_inout->live_in_ = live_inout->live_out_;
149 for (Instruction& insn : make_range(bb->rbegin(), bb->rend())) {
150 if (insn.opcode() == SpvOpPhi) {
151 live_inout->live_in_.insert(&insn);
152 break;
153 }
154 live_inout->live_in_.erase(&insn);
155 insn.ForEachInId([live_inout, this](uint32_t* id) {
156 Instruction* insn_op = def_use_manager_.GetDef(*id);
157 if (CreatesRegisterUsage(insn_op)) {
158 live_inout->live_in_.insert(insn_op);
159 }
160 });
161 }
162 }
163
164 // Propagates the register liveness information of each loop iterators.
165 void DoLoopLivenessUnification() {
166 for (const Loop* loop : *loop_desc_.GetDummyRootLoop()) {
167 DoLoopLivenessUnification(*loop);
168 }
169 }
170
171 // Propagates the register liveness information of loop iterators trough-out
172 // the loop body.
173 void DoLoopLivenessUnification(const Loop& loop) {
174 auto blocks_in_loop = MakeFilterIteratorRange(
175 loop.GetBlocks().begin(), loop.GetBlocks().end(),
176 [&loop, this](uint32_t bb_id) {
177 return bb_id != loop.GetHeaderBlock()->id() &&
178 loop_desc_[bb_id] == &loop;
179 });
180
181 RegisterLiveness::RegionRegisterLiveness* header_live_inout =
182 reg_pressure_->Get(loop.GetHeaderBlock());
183 assert(header_live_inout &&
184 "Liveness analysis was not performed for the current block");
185
186 ExcludePhiDefinedInBlock predicate(context_, loop.GetHeaderBlock());
187 auto live_loop =
188 MakeFilterIteratorRange(header_live_inout->live_in_.begin(),
189 header_live_inout->live_in_.end(), predicate);
190
191 for (uint32_t bb_id : blocks_in_loop) {
192 BasicBlock* bb = cfg_.block(bb_id);
193
194 RegisterLiveness::RegionRegisterLiveness* live_inout =
195 reg_pressure_->Get(bb);
196 live_inout->live_in_.insert(live_loop.begin(), live_loop.end());
197 live_inout->live_out_.insert(live_loop.begin(), live_loop.end());
198 }
199
200 for (const Loop* inner_loop : loop) {
201 RegisterLiveness::RegionRegisterLiveness* live_inout =
202 reg_pressure_->Get(inner_loop->GetHeaderBlock());
203 live_inout->live_in_.insert(live_loop.begin(), live_loop.end());
204 live_inout->live_out_.insert(live_loop.begin(), live_loop.end());
205
206 DoLoopLivenessUnification(*inner_loop);
207 }
208 }
209
210 // Get the number of required registers for this each basic block.
211 void EvaluateRegisterRequirements() {
212 for (BasicBlock& bb : *function_) {
213 RegisterLiveness::RegionRegisterLiveness* live_inout =
214 reg_pressure_->Get(bb.id());
215 assert(live_inout != nullptr && "Basic block not processed");
216
217 size_t reg_count = live_inout->live_out_.size();
218 for (Instruction* insn : live_inout->live_out_) {
219 live_inout->AddRegisterClass(insn);
220 }
221 live_inout->used_registers_ = reg_count;
222
223 std::unordered_set<uint32_t> die_in_block;
224 for (Instruction& insn : make_range(bb.rbegin(), bb.rend())) {
225 // If it is a phi instruction, the register pressure will not change
226 // anymore.
227 if (insn.opcode() == SpvOpPhi) {
228 break;
229 }
230
231 insn.ForEachInId(
232 [live_inout, &die_in_block, &reg_count, this](uint32_t* id) {
233 Instruction* op_insn = def_use_manager_.GetDef(*id);
234 if (!CreatesRegisterUsage(op_insn) ||
235 live_inout->live_out_.count(op_insn)) {
236 // already taken into account.
237 return;
238 }
239 if (!die_in_block.count(*id)) {
240 live_inout->AddRegisterClass(def_use_manager_.GetDef(*id));
241 reg_count++;
242 die_in_block.insert(*id);
243 }
244 });
245 live_inout->used_registers_ =
246 std::max(live_inout->used_registers_, reg_count);
247 if (CreatesRegisterUsage(&insn)) {
248 reg_count--;
249 }
250 }
251 }
252 }
253
254 RegisterLiveness* reg_pressure_;
255 IRContext* context_;
256 Function* function_;
257 CFG& cfg_;
258 analysis::DefUseManager& def_use_manager_;
259 DominatorTree& dom_tree_;
260 LoopDescriptor& loop_desc_;
261};
262} // namespace
263
264// Get the number of required registers for each basic block.
265void RegisterLiveness::RegionRegisterLiveness::AddRegisterClass(
266 Instruction* insn) {
267 assert(CreatesRegisterUsage(insn) && "Instruction does not use a register");
268 analysis::Type* type =
269 insn->context()->get_type_mgr()->GetType(insn->type_id());
270
271 RegisterLiveness::RegisterClass reg_class{type, false};
272
273 insn->context()->get_decoration_mgr()->WhileEachDecoration(
274 insn->result_id(), SpvDecorationUniform,
275 [&reg_class](const Instruction&) {
276 reg_class.is_uniform_ = true;
277 return false;
278 });
279
280 AddRegisterClass(reg_class);
281}
282
283void RegisterLiveness::Analyze(Function* f) {
284 block_pressure_.clear();
285 ComputeRegisterLiveness(this, f).Compute();
286}
287
288void RegisterLiveness::ComputeLoopRegisterPressure(
289 const Loop& loop, RegionRegisterLiveness* loop_reg_pressure) const {
290 loop_reg_pressure->Clear();
291
292 const RegionRegisterLiveness* header_live_inout = Get(loop.GetHeaderBlock());
293 loop_reg_pressure->live_in_ = header_live_inout->live_in_;
294
295 std::unordered_set<uint32_t> exit_blocks;
296 loop.GetExitBlocks(&exit_blocks);
297
298 for (uint32_t bb_id : exit_blocks) {
299 const RegionRegisterLiveness* live_inout = Get(bb_id);
300 loop_reg_pressure->live_out_.insert(live_inout->live_in_.begin(),
301 live_inout->live_in_.end());
302 }
303
304 std::unordered_set<uint32_t> seen_insn;
305 for (Instruction* insn : loop_reg_pressure->live_out_) {
306 loop_reg_pressure->AddRegisterClass(insn);
307 seen_insn.insert(insn->result_id());
308 }
309 for (Instruction* insn : loop_reg_pressure->live_in_) {
310 if (!seen_insn.count(insn->result_id())) {
311 continue;
312 }
313 loop_reg_pressure->AddRegisterClass(insn);
314 seen_insn.insert(insn->result_id());
315 }
316
317 loop_reg_pressure->used_registers_ = 0;
318
319 for (uint32_t bb_id : loop.GetBlocks()) {
320 BasicBlock* bb = context_->cfg()->block(bb_id);
321
322 const RegionRegisterLiveness* live_inout = Get(bb_id);
323 assert(live_inout != nullptr && "Basic block not processed");
324 loop_reg_pressure->used_registers_ = std::max(
325 loop_reg_pressure->used_registers_, live_inout->used_registers_);
326
327 for (Instruction& insn : *bb) {
328 if (insn.opcode() == SpvOpPhi || !CreatesRegisterUsage(&insn) ||
329 seen_insn.count(insn.result_id())) {
330 continue;
331 }
332 loop_reg_pressure->AddRegisterClass(&insn);
333 }
334 }
335}
336
337void RegisterLiveness::SimulateFusion(
338 const Loop& l1, const Loop& l2, RegionRegisterLiveness* sim_result) const {
339 sim_result->Clear();
340
341 // Compute the live-in state:
342 // sim_result.live_in = l1.live_in U l2.live_in
343 // This assumes that |l1| does not generated register that is live-out for
344 // |l1|.
345 const RegionRegisterLiveness* l1_header_live_inout = Get(l1.GetHeaderBlock());
346 sim_result->live_in_ = l1_header_live_inout->live_in_;
347
348 const RegionRegisterLiveness* l2_header_live_inout = Get(l2.GetHeaderBlock());
349 sim_result->live_in_.insert(l2_header_live_inout->live_in_.begin(),
350 l2_header_live_inout->live_in_.end());
351
352 // The live-out set of the fused loop is the l2 live-out set.
353 std::unordered_set<uint32_t> exit_blocks;
354 l2.GetExitBlocks(&exit_blocks);
355
356 for (uint32_t bb_id : exit_blocks) {
357 const RegionRegisterLiveness* live_inout = Get(bb_id);
358 sim_result->live_out_.insert(live_inout->live_in_.begin(),
359 live_inout->live_in_.end());
360 }
361
362 // Compute the register usage information.
363 std::unordered_set<uint32_t> seen_insn;
364 for (Instruction* insn : sim_result->live_out_) {
365 sim_result->AddRegisterClass(insn);
366 seen_insn.insert(insn->result_id());
367 }
368 for (Instruction* insn : sim_result->live_in_) {
369 if (!seen_insn.count(insn->result_id())) {
370 continue;
371 }
372 sim_result->AddRegisterClass(insn);
373 seen_insn.insert(insn->result_id());
374 }
375
376 sim_result->used_registers_ = 0;
377
378 // The loop fusion is injecting the l1 before the l2, the latch of l1 will be
379 // connected to the header of l2.
380 // To compute the register usage, we inject the loop live-in (union of l1 and
381 // l2 live-in header blocks) into the the live in/out of each basic block of
382 // l1 to get the peak register usage. We then repeat the operation to for l2
383 // basic blocks but in this case we inject the live-out of the latch of l1.
384 auto live_loop = MakeFilterIteratorRange(
385 sim_result->live_in_.begin(), sim_result->live_in_.end(),
386 [&l1, &l2](Instruction* insn) {
387 BasicBlock* bb = insn->context()->get_instr_block(insn);
388 return insn->HasResultId() &&
389 !(insn->opcode() == SpvOpPhi &&
390 (bb == l1.GetHeaderBlock() || bb == l2.GetHeaderBlock()));
391 });
392
393 for (uint32_t bb_id : l1.GetBlocks()) {
394 BasicBlock* bb = context_->cfg()->block(bb_id);
395
396 const RegionRegisterLiveness* live_inout_info = Get(bb_id);
397 assert(live_inout_info != nullptr && "Basic block not processed");
398 RegionRegisterLiveness::LiveSet live_out = live_inout_info->live_out_;
399 live_out.insert(live_loop.begin(), live_loop.end());
400 sim_result->used_registers_ =
401 std::max(sim_result->used_registers_,
402 live_inout_info->used_registers_ + live_out.size() -
403 live_inout_info->live_out_.size());
404
405 for (Instruction& insn : *bb) {
406 if (insn.opcode() == SpvOpPhi || !CreatesRegisterUsage(&insn) ||
407 seen_insn.count(insn.result_id())) {
408 continue;
409 }
410 sim_result->AddRegisterClass(&insn);
411 }
412 }
413
414 const RegionRegisterLiveness* l1_latch_live_inout_info =
415 Get(l1.GetLatchBlock()->id());
416 assert(l1_latch_live_inout_info != nullptr && "Basic block not processed");
417 RegionRegisterLiveness::LiveSet l1_latch_live_out =
418 l1_latch_live_inout_info->live_out_;
419 l1_latch_live_out.insert(live_loop.begin(), live_loop.end());
420
421 auto live_loop_l2 =
422 make_range(l1_latch_live_out.begin(), l1_latch_live_out.end());
423
424 for (uint32_t bb_id : l2.GetBlocks()) {
425 BasicBlock* bb = context_->cfg()->block(bb_id);
426
427 const RegionRegisterLiveness* live_inout_info = Get(bb_id);
428 assert(live_inout_info != nullptr && "Basic block not processed");
429 RegionRegisterLiveness::LiveSet live_out = live_inout_info->live_out_;
430 live_out.insert(live_loop_l2.begin(), live_loop_l2.end());
431 sim_result->used_registers_ =
432 std::max(sim_result->used_registers_,
433 live_inout_info->used_registers_ + live_out.size() -
434 live_inout_info->live_out_.size());
435
436 for (Instruction& insn : *bb) {
437 if (insn.opcode() == SpvOpPhi || !CreatesRegisterUsage(&insn) ||
438 seen_insn.count(insn.result_id())) {
439 continue;
440 }
441 sim_result->AddRegisterClass(&insn);
442 }
443 }
444}
445
446void RegisterLiveness::SimulateFission(
447 const Loop& loop, const std::unordered_set<Instruction*>& moved_inst,
448 const std::unordered_set<Instruction*>& copied_inst,
449 RegionRegisterLiveness* l1_sim_result,
450 RegionRegisterLiveness* l2_sim_result) const {
451 l1_sim_result->Clear();
452 l2_sim_result->Clear();
453
454 // Filter predicates: consider instructions that only belong to the first and
455 // second loop.
456 auto belong_to_loop1 = [&moved_inst, &copied_inst, &loop](Instruction* insn) {
457 return moved_inst.count(insn) || copied_inst.count(insn) ||
458 !loop.IsInsideLoop(insn);
459 };
460 auto belong_to_loop2 = [&moved_inst](Instruction* insn) {
461 return !moved_inst.count(insn);
462 };
463
464 const RegionRegisterLiveness* header_live_inout = Get(loop.GetHeaderBlock());
465 // l1 live-in
466 {
467 auto live_loop = MakeFilterIteratorRange(
468 header_live_inout->live_in_.begin(), header_live_inout->live_in_.end(),
469 belong_to_loop1);
470 l1_sim_result->live_in_.insert(live_loop.begin(), live_loop.end());
471 }
472 // l2 live-in
473 {
474 auto live_loop = MakeFilterIteratorRange(
475 header_live_inout->live_in_.begin(), header_live_inout->live_in_.end(),
476 belong_to_loop2);
477 l2_sim_result->live_in_.insert(live_loop.begin(), live_loop.end());
478 }
479
480 std::unordered_set<uint32_t> exit_blocks;
481 loop.GetExitBlocks(&exit_blocks);
482
483 // l2 live-out.
484 for (uint32_t bb_id : exit_blocks) {
485 const RegionRegisterLiveness* live_inout = Get(bb_id);
486 l2_sim_result->live_out_.insert(live_inout->live_in_.begin(),
487 live_inout->live_in_.end());
488 }
489 // l1 live-out.
490 {
491 auto live_out = MakeFilterIteratorRange(l2_sim_result->live_out_.begin(),
492 l2_sim_result->live_out_.end(),
493 belong_to_loop1);
494 l1_sim_result->live_out_.insert(live_out.begin(), live_out.end());
495 }
496 {
497 auto live_out =
498 MakeFilterIteratorRange(l2_sim_result->live_in_.begin(),
499 l2_sim_result->live_in_.end(), belong_to_loop1);
500 l1_sim_result->live_out_.insert(live_out.begin(), live_out.end());
501 }
502 // Lives out of l1 are live out of l2 so are live in of l2 as well.
503 l2_sim_result->live_in_.insert(l1_sim_result->live_out_.begin(),
504 l1_sim_result->live_out_.end());
505
506 for (Instruction* insn : l1_sim_result->live_in_) {
507 l1_sim_result->AddRegisterClass(insn);
508 }
509 for (Instruction* insn : l2_sim_result->live_in_) {
510 l2_sim_result->AddRegisterClass(insn);
511 }
512
513 l1_sim_result->used_registers_ = 0;
514 l2_sim_result->used_registers_ = 0;
515
516 for (uint32_t bb_id : loop.GetBlocks()) {
517 BasicBlock* bb = context_->cfg()->block(bb_id);
518
519 const RegisterLiveness::RegionRegisterLiveness* live_inout = Get(bb_id);
520 assert(live_inout != nullptr && "Basic block not processed");
521 auto l1_block_live_out =
522 MakeFilterIteratorRange(live_inout->live_out_.begin(),
523 live_inout->live_out_.end(), belong_to_loop1);
524 auto l2_block_live_out =
525 MakeFilterIteratorRange(live_inout->live_out_.begin(),
526 live_inout->live_out_.end(), belong_to_loop2);
527
528 size_t l1_reg_count =
529 std::distance(l1_block_live_out.begin(), l1_block_live_out.end());
530 size_t l2_reg_count =
531 std::distance(l2_block_live_out.begin(), l2_block_live_out.end());
532
533 std::unordered_set<uint32_t> die_in_block;
534 for (Instruction& insn : make_range(bb->rbegin(), bb->rend())) {
535 if (insn.opcode() == SpvOpPhi) {
536 break;
537 }
538
539 bool does_belong_to_loop1 = belong_to_loop1(&insn);
540 bool does_belong_to_loop2 = belong_to_loop2(&insn);
541 insn.ForEachInId([live_inout, &die_in_block, &l1_reg_count, &l2_reg_count,
542 does_belong_to_loop1, does_belong_to_loop2,
543 this](uint32_t* id) {
544 Instruction* op_insn = context_->get_def_use_mgr()->GetDef(*id);
545 if (!CreatesRegisterUsage(op_insn) ||
546 live_inout->live_out_.count(op_insn)) {
547 // already taken into account.
548 return;
549 }
550 if (!die_in_block.count(*id)) {
551 if (does_belong_to_loop1) {
552 l1_reg_count++;
553 }
554 if (does_belong_to_loop2) {
555 l2_reg_count++;
556 }
557 die_in_block.insert(*id);
558 }
559 });
560 l1_sim_result->used_registers_ =
561 std::max(l1_sim_result->used_registers_, l1_reg_count);
562 l2_sim_result->used_registers_ =
563 std::max(l2_sim_result->used_registers_, l2_reg_count);
564 if (CreatesRegisterUsage(&insn)) {
565 if (does_belong_to_loop1) {
566 if (!l1_sim_result->live_in_.count(&insn)) {
567 l1_sim_result->AddRegisterClass(&insn);
568 }
569 l1_reg_count--;
570 }
571 if (does_belong_to_loop2) {
572 if (!l2_sim_result->live_in_.count(&insn)) {
573 l2_sim_result->AddRegisterClass(&insn);
574 }
575 l2_reg_count--;
576 }
577 }
578 }
579 }
580}
581
582} // namespace opt
583} // namespace spvtools
584