• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 
27 namespace spvtools {
28 namespace opt {
29 
30 namespace {
31 // Predicate for the FilterIterator to only consider instructions that are not
32 // phi instructions defined in the basic block |bb|.
33 class ExcludePhiDefinedInBlock {
34  public:
ExcludePhiDefinedInBlock(IRContext * context,const BasicBlock * bb)35   ExcludePhiDefinedInBlock(IRContext* context, const BasicBlock* bb)
36       : context_(context), bb_(bb) {}
37 
operator ()(Instruction * insn) const38   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.
CreatesRegisterUsage(Instruction * insn)50 bool 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.
62 class ComputeRegisterLiveness {
63  public:
ComputeRegisterLiveness(RegisterLiveness * reg_pressure,Function * f)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).
Compute()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.
ComputePhiUses(const BasicBlock & bb,RegisterLiveness::RegionRegisterLiveness::LiveSet * live)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.
ComputePartialLiveness(BasicBlock * bb)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.
DoLoopLivenessUnification()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.
DoLoopLivenessUnification(const Loop & loop)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.
EvaluateRegisterRequirements()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.
AddRegisterClass(Instruction * insn)265 void 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 
Analyze(Function * f)283 void RegisterLiveness::Analyze(Function* f) {
284   block_pressure_.clear();
285   ComputeRegisterLiveness(this, f).Compute();
286 }
287 
ComputeLoopRegisterPressure(const Loop & loop,RegionRegisterLiveness * loop_reg_pressure) const288 void 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 
SimulateFusion(const Loop & l1,const Loop & l2,RegionRegisterLiveness * sim_result) const337 void 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 
SimulateFission(const Loop & loop,const std::unordered_set<Instruction * > & moved_inst,const std::unordered_set<Instruction * > & copied_inst,RegionRegisterLiveness * l1_sim_result,RegionRegisterLiveness * l2_sim_result) const446 void 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