• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /**
2  * Copyright (c) 2021-2022 Huawei Device Co., Ltd.
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 
16 #include "optimizer/ir/inst.h"
17 #include "optimizer/ir/basicblock.h"
18 #include "optimizer/ir/graph.h"
19 #include "liveness_analyzer.h"
20 #include "optimizer/analysis/dominators_tree.h"
21 #include "optimizer/analysis/loop_analyzer.h"
22 
23 namespace panda::compiler {
LivenessAnalyzer(Graph * graph)24 LivenessAnalyzer::LivenessAnalyzer(Graph *graph)
25     : Analysis(graph),
26       allocator_(graph->GetAllocator()),
27       linear_blocks_(graph->GetAllocator()->Adapter()),
28       inst_life_numbers_(graph->GetAllocator()->Adapter()),
29       inst_life_intervals_(graph->GetAllocator()->Adapter()),
30       insts_by_life_number_(graph->GetAllocator()->Adapter()),
31       block_live_ranges_(graph->GetAllocator()->Adapter()),
32       block_live_sets_(graph->GetLocalAllocator()->Adapter()),
33       pending_catch_phi_inputs_(graph->GetAllocator()->Adapter()),
34       physical_general_intervals_(graph->GetAllocator()->Adapter()),
35       physical_vector_intervals_(graph->GetAllocator()->Adapter())
36 {
37 }
38 
RunImpl()39 bool LivenessAnalyzer::RunImpl()
40 {
41     GetGraph()->RunPass<DominatorsTree>();
42     GetGraph()->RunPass<LoopAnalyzer>();
43     ResetLiveness();
44     BuildBlocksLinearOrder();
45     BuildInstLifeNumbers();
46     BuildInstLifeIntervals();
47     if (!pending_catch_phi_inputs_.empty()) {
48         COMPILER_LOG(ERROR, LIVENESS_ANALYZER)
49             << "Graph contains CatchPhi instructions whose inputs were not processed";
50         return false;
51     }
52     std::copy_if(physical_general_intervals_.begin(), physical_general_intervals_.end(),
53                  std::back_inserter(inst_life_intervals_), [](auto li) { return li != nullptr; });
54     std::copy_if(physical_vector_intervals_.begin(), physical_vector_intervals_.end(),
55                  std::back_inserter(inst_life_intervals_), [](auto li) { return li != nullptr; });
56     COMPILER_LOG(DEBUG, LIVENESS_ANALYZER) << "Liveness analysis is constructed";
57     return true;
58 }
59 
ResetLiveness()60 void LivenessAnalyzer::ResetLiveness()
61 {
62     inst_life_numbers_.clear();
63     inst_life_intervals_.clear();
64     block_live_sets_.clear();
65     block_live_ranges_.clear();
66     physical_general_intervals_.clear();
67     physical_vector_intervals_.clear();
68     if (GetGraph()->GetArch() != Arch::NONE) {
69         physical_general_intervals_.resize(REGISTERS_NUM);
70         physical_vector_intervals_.resize(VREGISTERS_NUM);
71     }
72 }
73 
74 /*
75  * Linear blocks order means:
76  * - all dominators of a block are visiting before this block;
77  * - all blocks belonging to the same loop are contiguous;
78  */
BuildBlocksLinearOrder()79 void LivenessAnalyzer::BuildBlocksLinearOrder()
80 {
81     ASSERT_PRINT(GetGraph()->IsAnalysisValid<DominatorsTree>(), "Liveness Analyzer needs valid Dom Tree");
82     auto size = GetGraph()->GetBlocksRPO().size();
83     linear_blocks_.reserve(size);
84     linear_blocks_.clear();
85     marker_ = GetGraph()->NewMarker();
86     ASSERT_PRINT(marker_ != UNDEF_MARKER, "There are no free markers");
87     if (GetGraph()->IsBytecodeOptimizer() && !GetGraph()->GetTryBeginBlocks().empty()) {
88         LinearizeBlocks<true>();
89     } else {
90         LinearizeBlocks<false>();
91     }
92     ASSERT(linear_blocks_.size() == size);
93     GetGraph()->EraseMarker(marker_);
94     ASSERT_PRINT(CheckLinearOrder(), "Linear block order isn't correct");
95 
96     block_live_sets_.resize(GetGraph()->GetVectorBlocks().size());
97     block_live_ranges_.resize(GetGraph()->GetVectorBlocks().size());
98 }
99 
100 /*
101  * Check if all forward edges of loop header were visited to get the resulting block order in RPO.
102  * Predecessors which are not in the same loop with a header - are forward edges.
103  */
AllForwardEdgesVisited(BasicBlock * block)104 bool LivenessAnalyzer::AllForwardEdgesVisited(BasicBlock *block)
105 {
106     if (!block->IsLoopHeader()) {
107         for (auto pred : block->GetPredsBlocks()) {
108             if (!pred->IsMarked(marker_)) {
109                 return false;
110             }
111         }
112     } else {
113         // Head of irreducible loop can not dominate other blocks in the loop
114         if (block->GetLoop()->IsIrreducible()) {
115             return true;
116         }
117         // Predecessors which are not dominated - are forward edges,
118         for (auto pred : block->GetPredsBlocks()) {
119             if (!block->IsDominate(pred) && !pred->IsMarked(marker_)) {
120                 return false;
121             }
122         }
123     }
124     return true;
125 }
126 
127 template <bool use_pc_order>
LinearizeBlocks()128 void LivenessAnalyzer::LinearizeBlocks()
129 {
130     ArenaList<BasicBlock *> pending {GetGraph()->GetLocalAllocator()->Adapter()};
131     pending.push_back(GetGraph()->GetStartBlock());
132 
133     while (!pending.empty()) {
134         auto current = pending.front();
135         pending.pop_front();
136 
137         linear_blocks_.push_back(current);
138         current->SetMarker(marker_);
139 
140         auto succs = current->GetSuccsBlocks();
141         // Each block is inserted into pending list before all already inserted blocks
142         // from the same loop. To process edges forwarding to a "true" branches successors
143         // should be processed in reversed order.
144         for (auto it = succs.rbegin(); it != succs.rend(); ++it) {
145             auto succ = *it;
146             if (succ->IsMarked(marker_) || !AllForwardEdgesVisited(succ)) {
147                 continue;
148             }
149 
150             if constexpr (use_pc_order) {  // NOLINT(readability-braces-around-statements)
151                 auto pc_compare = [succ](auto block) { return block->GetGuestPc() > succ->GetGuestPc(); };
152                 auto insert_before = std::find_if(pending.begin(), pending.end(), pc_compare);
153                 pending.insert(insert_before, succ);
154             } else {  // NOLINT(readability-misleading-indentation)
155                 // Insert successor right before a block from the same loop, outer loop's block
156                 // or before a block from the root loop.
157                 // Such ordering guarantee that a loop and all it's inner loops will be processed
158                 // before following edges leading to outer loop blocks.
159                 auto is_same_or_inner_loop = [succ](auto block) {
160                     return succ->GetLoop() == block->GetLoop() || block->GetLoop()->IsRoot() ||
161                            succ->GetLoop()->IsInside(block->GetLoop());
162                 };
163                 auto insert_before = std::find_if(pending.begin(), pending.end(), is_same_or_inner_loop);
164                 pending.insert(insert_before, succ);
165             }
166         }
167     }
168 }
169 
170 /*
171  * Check linear order correctness, using dominators tree
172  */
CheckLinearOrder()173 bool LivenessAnalyzer::CheckLinearOrder()
174 {
175     ArenaVector<size_t> block_pos(GetGraph()->GetVectorBlocks().size(), 0, GetAllocator()->Adapter());
176     size_t position = 0;
177     for (auto block : linear_blocks_) {
178         block_pos[block->GetId()] = position++;
179     }
180 
181     for (auto block : linear_blocks_) {
182         if (block->GetDominator() != nullptr) {
183             ASSERT_PRINT(block_pos[block->GetDominator()->GetId()] < block_pos[block->GetId()],
184                          "Each block should be visited after its dominator");
185         }
186         if (!block->IsTryEnd()) {
187             continue;
188         }
189         ASSERT(block->GetTryId() != INVALID_ID);
190         for (auto bb : linear_blocks_) {
191             if (bb->IsTry() && bb->GetTryId() == block->GetTryId()) {
192                 ASSERT_PRINT(block_pos[bb->GetId()] < block_pos[block->GetId()],
193                              "Each try-block should be visited before its try-end block");
194             }
195         }
196     }
197 
198     return true;
199 }
200 
201 /*
202  * Set lifetime number and visiting number for each instruction
203  */
BuildInstLifeNumbers()204 void LivenessAnalyzer::BuildInstLifeNumbers()
205 {
206     LifeNumber block_begin;
207     LifeNumber life_number = 0;
208     LinearNumber linear_number = 0;
209 
210     for (auto block : GetLinearizedBlocks()) {
211         block_begin = life_number;
212         // set the same number for each phi in the block
213         for (auto phi : block->PhiInsts()) {
214             phi->SetLinearNumber(linear_number++);
215             SetInstLifeNumber(phi, life_number);
216             CreateLifeIntervals(phi);
217         }
218         // ignore PHI instructions
219         insts_by_life_number_.push_back(nullptr);
220         // set a unique number for each instruction in the block, differing by 2
221         // for the reason of adding spill/fill instructions
222         for (auto inst : block->Insts()) {
223             inst->SetLinearNumber(linear_number++);
224             CreateLifeIntervals(inst);
225             life_number += LIFE_NUMBER_GAP;
226             SetInstLifeNumber(inst, life_number);
227             insts_by_life_number_.push_back(inst);
228         }
229         life_number += LIFE_NUMBER_GAP;
230         SetBlockLiveRange(block, {block_begin, life_number});
231     }
232 }
233 
234 /*
235  * Get lifetime intervals for each instruction
236  */
BuildInstLifeIntervals()237 void LivenessAnalyzer::BuildInstLifeIntervals()
238 {
239     for (auto it = GetLinearizedBlocks().rbegin(); it != GetLinearizedBlocks().rend(); it++) {
240         auto block = *it;
241         auto live_set = GetInitInstLiveSet(block);
242         ProcessBlockLiveInstructions(block, live_set);
243     }
244 }
245 
246 /*
247  * The initial set of live instructions in the `block` is the the union of all live instructions at the beginning of
248  * the block's successors.
249  * Also for each phi-instruction of the successors: input corresponding to the `block` is added to the live set.
250  */
GetInitInstLiveSet(BasicBlock * block)251 InstLiveSet *LivenessAnalyzer::GetInitInstLiveSet(BasicBlock *block)
252 {
253     unsigned instruction_count = inst_life_intervals_.size();
254     auto live_set = GetAllocator()->New<InstLiveSet>(instruction_count, GetAllocator());
255     for (auto succ : block->GetSuccsBlocks()) {
256         // catch-begin is pseudo successor, its live set will be processed for blocks with throwable instructions
257         if (succ->IsCatchBegin()) {
258             continue;
259         }
260         live_set->Union(GetBlockLiveSet(succ));
261         for (auto phi : succ->PhiInsts()) {
262             auto phi_input = phi->CastToPhi()->GetPhiDataflowInput(block);
263             live_set->Add(phi_input->GetLinearNumber());
264         }
265     }
266 
267     // if basic block contains throwable instruction, all instucrions live in the catch-handlers should be live in this
268     // block
269     if (auto inst = block->GetFistThrowableInst(); inst != nullptr) {
270         auto handlers = GetGraph()->GetThrowableInstHandlers(inst);
271         for (auto catch_handler : handlers) {
272             live_set->Union(GetBlockLiveSet(catch_handler));
273         }
274     }
275     return live_set;
276 }
277 
GetLoopEnd(Loop * loop)278 LifeNumber LivenessAnalyzer::GetLoopEnd(Loop *loop)
279 {
280     LifeNumber loop_end = 0;
281     // find max LifeNumber of inner loops
282     for (auto inner : loop->GetInnerLoops()) {
283         loop_end = std::max(loop_end, GetLoopEnd(inner));
284     }
285     // find max LifeNumber of back_edges
286     for (auto back_edge : loop->GetBackEdges()) {
287         loop_end = std::max(loop_end, GetBlockLiveRange(back_edge).GetEnd());
288     }
289     return loop_end;
290 }
291 
292 /*
293  * Append and adjust the lifetime intervals for each instruction live in the block and for their inputs
294  */
ProcessBlockLiveInstructions(BasicBlock * block,InstLiveSet * live_set)295 void LivenessAnalyzer::ProcessBlockLiveInstructions(BasicBlock *block, InstLiveSet *live_set)
296 {
297     // For each live instruction set initial life range equals to the block life range
298     for (auto &interval : inst_life_intervals_) {
299         if (live_set->IsSet(interval->GetInst()->GetLinearNumber())) {
300             interval->AppendRange(GetBlockLiveRange(block));
301         }
302     }
303 
304     for (Inst *inst : block->InstsSafeReverse()) {
305         // Shorten instruction lifetime to the position where its defined
306         // and remove from the block's live set
307         auto inst_life_number = GetInstLifeNumber(inst);
308         auto interval = GetInstLifeIntervals(inst);
309         interval->StartFrom(inst_life_number);
310         live_set->Remove(inst->GetLinearNumber());
311         if (inst->IsCatchPhi()) {
312             // catch-phi's liveness should overlap all linked try blocks' livenesses
313             for (auto pred : inst->GetBasicBlock()->GetPredsBlocks()) {
314                 inst_life_number = std::min(inst_life_number, GetBlockLiveRange(pred).GetBegin());
315             }
316             interval->StartFrom(inst_life_number);
317             AdjustCatchPhiInputsLifetime(inst);
318         } else {
319             auto current_live_range = LiveRange {GetBlockLiveRange(block).GetBegin(), inst_life_number};
320             AdjustInputsLifetime(inst, current_live_range, live_set);
321         }
322     }
323 
324     // The lifetime interval of phis instructions starts at the beginning of the block
325     for (auto phi : block->PhiInsts()) {
326         live_set->Remove(phi->GetLinearNumber());
327     }
328 
329     // All instructions live at the beginning ot the loop header
330     // must be live for the entire loop
331     if (block->IsLoopHeader()) {
332         LifeNumber loop_end_position = GetLoopEnd(block->GetLoop());
333 
334         for (auto &interval : inst_life_intervals_) {
335             if (live_set->IsSet(interval->GetInst()->GetLinearNumber())) {
336                 interval->AppendGroupRange({GetBlockLiveRange(block).GetBegin(), loop_end_position});
337             }
338         }
339     }
340     SetBlockLiveSet(block, live_set);
341 }
342 
343 /* static */
GetPropagatedLiveRange(Inst * inst,LiveRange live_range)344 LiveRange LivenessAnalyzer::GetPropagatedLiveRange(Inst *inst, LiveRange live_range)
345 {
346     /*
347      * We need to propagate liveness for instruction with CallRuntime to save registers before call;
348      * Otherwise, we will not be able to restore the value of the virtual registers
349      */
350     if (inst->IsPropagateLiveness()) {
351         live_range.SetEnd(live_range.GetEnd() + 1);
352     }
353     return live_range;
354 }
355 
356 /*
357  * Adjust instruction inputs lifetime and add them to the block's live set
358  */
AdjustInputsLifetime(Inst * inst,LiveRange live_range,InstLiveSet * live_set)359 void LivenessAnalyzer::AdjustInputsLifetime(Inst *inst, LiveRange live_range, InstLiveSet *live_set)
360 {
361     for (auto input : inst->GetInputs()) {
362         auto input_inst = inst->GetDataFlowInput(input.GetInst());
363         live_set->Add(input_inst->GetLinearNumber());
364         SetInputRange(inst, input_inst, live_range);
365     }
366 
367     // Extend SaveState inputs lifetime to the end of SaveState's lifetime
368     if (inst->RequireState()) {
369         auto save_state = inst->GetSaveState();
370         ASSERT(save_state != nullptr);
371         auto propagated_range = GetPropagatedLiveRange(inst, live_range);
372         for (auto ss_input : save_state->GetInputs()) {
373             auto input_inst = save_state->GetDataFlowInput(ss_input.GetInst());
374             live_set->Add(input_inst->GetLinearNumber());
375             GetInstLifeIntervals(input_inst)->AppendRange(propagated_range);
376         }
377     }
378 
379     // Handle CatchPhi inputs associated with inst
380     auto range = pending_catch_phi_inputs_.equal_range(inst);
381     for (auto it = range.first; it != range.second; ++it) {
382         auto throwable_input = it->second;
383         auto throwable_input_interval = GetInstLifeIntervals(throwable_input);
384         live_set->Add(throwable_input->GetLinearNumber());
385         throwable_input_interval->AppendRange(live_range);
386     }
387     pending_catch_phi_inputs_.erase(inst);
388 }
389 
390 /*
391  * Increase ref-input liveness in the 'no-async-jit' mode, since GC can be triggered and delete ref during callee-method
392  * compilation
393  */
SetInputRange(const Inst * inst,const Inst * input,LiveRange live_range) const394 void LivenessAnalyzer::SetInputRange([[maybe_unused]] const Inst *inst, const Inst *input, LiveRange live_range) const
395 {
396     GetInstLifeIntervals(input)->AppendRange(live_range);
397 }
398 
399 /*
400  * CatchPhi does not handle inputs as regular instructions - instead of performing
401  * some action at CatchPhi's definition copy instruction are added before throwable instructions.
402  * Instead of extending input life interval until CatchPhi it is extended until throwable instruction.
403  */
AdjustCatchPhiInputsLifetime(Inst * inst)404 void LivenessAnalyzer::AdjustCatchPhiInputsLifetime(Inst *inst)
405 {
406     auto catch_phi = inst->CastToCatchPhi();
407 
408     for (ssize_t input_idx = catch_phi->GetInputsCount() - 1; input_idx >= 0; input_idx--) {
409         auto input_inst = catch_phi->GetDataFlowInput(input_idx);
410         auto throwable_inst = const_cast<Inst *>(catch_phi->GetThrowableInst(input_idx));
411 
412         pending_catch_phi_inputs_.insert({throwable_inst, input_inst});
413     }
414 }
415 
SetInstLifeNumber(const Inst * inst,LifeNumber number)416 void LivenessAnalyzer::SetInstLifeNumber([[maybe_unused]] const Inst *inst, LifeNumber number)
417 {
418     ASSERT(inst_life_numbers_.size() == inst->GetLinearNumber());
419     inst_life_numbers_.push_back(number);
420 }
421 
GetInstLifeNumber(Inst * inst) const422 LifeNumber LivenessAnalyzer::GetInstLifeNumber(Inst *inst) const
423 {
424     return inst_life_numbers_[inst->GetLinearNumber()];
425 }
426 
427 /*
428  * Create new lifetime intervals for instruction, check that instruction linear number is equal to intervals
429  * position in vector
430  */
CreateLifeIntervals(Inst * inst)431 void LivenessAnalyzer::CreateLifeIntervals(Inst *inst)
432 {
433     ASSERT(inst->GetLinearNumber() == inst_life_intervals_.size());
434     inst_life_intervals_.push_back(GetAllocator()->New<LifeIntervals>(GetAllocator(), inst));
435 }
436 
GetInstLifeIntervals(const Inst * inst) const437 LifeIntervals *LivenessAnalyzer::GetInstLifeIntervals(const Inst *inst) const
438 {
439     ASSERT(inst->GetLinearNumber() != INVALID_LINEAR_NUM);
440     return inst_life_intervals_[inst->GetLinearNumber()];
441 }
442 
SetBlockLiveRange(BasicBlock * block,LiveRange life_range)443 void LivenessAnalyzer::SetBlockLiveRange(BasicBlock *block, LiveRange life_range)
444 {
445     block_live_ranges_[block->GetId()] = life_range;
446 }
447 
GetBlockLiveRange(const BasicBlock * block) const448 LiveRange LivenessAnalyzer::GetBlockLiveRange(const BasicBlock *block) const
449 {
450     return block_live_ranges_[block->GetId()];
451 }
452 
SetBlockLiveSet(BasicBlock * block,InstLiveSet * live_set)453 void LivenessAnalyzer::SetBlockLiveSet(BasicBlock *block, InstLiveSet *live_set)
454 {
455     block_live_sets_[block->GetId()] = live_set;
456 }
457 
GetBlockLiveSet(BasicBlock * block) const458 InstLiveSet *LivenessAnalyzer::GetBlockLiveSet(BasicBlock *block) const
459 {
460     return block_live_sets_[block->GetId()];
461 }
462 
DumpLifeIntervals(std::ostream & out) const463 void LivenessAnalyzer::DumpLifeIntervals(std::ostream &out) const
464 {
465     for (auto bb : GetGraph()->GetBlocksRPO()) {
466         if (bb->GetId() >= GetBlocksCount()) {
467             continue;
468         }
469         auto block_range = GetBlockLiveRange(bb);
470         out << "BB " << bb->GetId() << "\t" << block_range.ToString() << std::endl;
471 
472         for (auto inst : bb->AllInsts()) {
473             if (inst->GetLinearNumber() == INVALID_LINEAR_NUM) {
474                 continue;
475             }
476             auto interval = GetInstLifeIntervals(inst);
477 
478             out << "v" << inst->GetId() << "\t";
479             for (auto sibling = interval; sibling != nullptr; sibling = sibling->GetSibling()) {
480                 out << sibling->ToString<false>() << "@ " << sibling->GetLocation().ToString(GetGraph()->GetArch())
481                     << "; ";
482             }
483             out << std::endl;
484         }
485     }
486     DumpLocationsUsage(out);
487 }
488 
DumpLocationsUsage(std::ostream & out) const489 void LivenessAnalyzer::DumpLocationsUsage(std::ostream &out) const
490 {
491     std::map<Register, std::vector<LifeIntervals *>> regs_intervals;
492     std::map<Register, std::vector<LifeIntervals *>> vregs_intervals;
493     std::map<Register, std::vector<LifeIntervals *>> slots_intervals;
494     for (auto &interval : inst_life_intervals_) {
495         for (auto sibling = interval; sibling != nullptr; sibling = sibling->GetSibling()) {
496             auto location = sibling->GetLocation();
497             if (location.IsFpRegister()) {
498                 ASSERT(DataType::IsFloatType(interval->GetType()));
499                 vregs_intervals[location.GetValue()].push_back(sibling);
500             } else if (location.IsRegister()) {
501                 regs_intervals[location.GetValue()].push_back(sibling);
502             } else if (location.IsStack()) {
503                 slots_intervals[location.GetValue()].push_back(sibling);
504             }
505         }
506     }
507 
508     for (auto intervals_map : {&regs_intervals, &vregs_intervals, &slots_intervals}) {
509         std::string loc_symbol;
510         if (intervals_map == &regs_intervals) {
511             out << std::endl << "Registers intervals" << std::endl;
512             loc_symbol = "r";
513         } else if (intervals_map == &vregs_intervals) {
514             out << std::endl << "Vector registers intervals" << std::endl;
515             loc_symbol = "vr";
516         } else {
517             ASSERT(intervals_map == &slots_intervals);
518             out << std::endl << "Stack slots intervals" << std::endl;
519             loc_symbol = "s";
520         }
521 
522         if (intervals_map->empty()) {
523             out << "-" << std::endl;
524             continue;
525         }
526         for (auto &[reg, intervals] : *intervals_map) {
527             std::sort(intervals.begin(), intervals.end(),
528                       [](const auto &lhs, const auto &rhs) { return lhs->GetBegin() < rhs->GetBegin(); });
529             out << loc_symbol << std::to_string(reg) << ": ";
530             auto delim = "";
531             for (auto &interval : intervals) {
532                 out << delim << interval->ToString<false>();
533                 delim = "; ";
534             }
535             out << std::endl;
536         }
537     }
538 }
539 
540 template <bool is_fp>
BlockPhysicalRegisters(LifeNumber block_from)541 void LivenessAnalyzer::BlockPhysicalRegisters(LifeNumber block_from)
542 {
543     auto arch = GetGraph()->GetArch();
544     RegMask caller_regs {GetCallerRegsMask(arch, is_fp)};
545     for (auto reg = GetFirstCallerReg(arch, is_fp); reg <= GetLastCallerReg(arch, is_fp); ++reg) {
546         if (caller_regs.test(reg)) {
547             BlockReg<is_fp>(reg, block_from);
548         }
549     }
550 }
551 
BlockFixedLocationRegister(Location location,LifeNumber ln)552 void LivenessAnalyzer::BlockFixedLocationRegister(Location location, LifeNumber ln)
553 {
554     if (location.IsRegister() && location.IsRegisterValid()) {
555         BlockReg<false>(location.GetValue(), ln);
556     } else if (location.IsFpRegister() && location.IsRegisterValid()) {
557         BlockReg<true>(location.GetValue(), ln);
558     }
559 }
560 
561 template <bool is_fp>
BlockReg(Register reg,LifeNumber block_from)562 void LivenessAnalyzer::BlockReg(Register reg, LifeNumber block_from)
563 {
564     auto &intervals = is_fp ? physical_vector_intervals_ : physical_general_intervals_;
565     auto interval = intervals.at(reg);
566     if (interval == nullptr) {
567         interval = GetGraph()->GetAllocator()->New<LifeIntervals>(GetGraph()->GetAllocator());
568         interval->SetPhysicalReg(reg, is_fp ? DataType::FLOAT64 : DataType::UINT64);
569         intervals.at(reg) = interval;
570     }
571     interval->AppendRange(block_from, block_from + 1U);
572     interval->AddUsePosition(block_from);
573 }
574 
IsCallBlockingRegisters(Inst * inst) const575 bool LivenessAnalyzer::IsCallBlockingRegisters(Inst *inst) const
576 {
577     if (inst->IsCall()) {
578         return true;
579     }
580     if (inst->IsIntrinsic() && inst->CastToIntrinsic()->IsNativeCall()) {
581         return true;
582     }
583     return false;
584 }
585 
SplitAt(LifeNumber ln,ArenaAllocator * alloc)586 LifeIntervals *LifeIntervals::SplitAt(LifeNumber ln, ArenaAllocator *alloc)
587 {
588     ASSERT(!IsPhysical());
589     ASSERT(ln > GetBegin() && ln <= GetEnd());
590     auto split_child = alloc->New<LifeIntervals>(alloc, GetInst());
591     if (sibling_ != nullptr) {
592         split_child->sibling_ = sibling_;
593     }
594     split_child->is_split_sibling_ = true;
595 
596     sibling_ = split_child;
597     split_child->SetType(GetType());
598 
599     for (auto &range = live_ranges_.back(); range.GetEnd() > ln; range = live_ranges_.back()) {
600         live_ranges_.pop_back();
601         if (range.GetBegin() > ln) {
602             split_child->AppendRange(range);
603         } else {
604             split_child->AppendRange(ln, range.GetEnd());
605             range.SetEnd(ln);
606             if (range.GetBegin() != range.GetEnd()) {
607                 live_ranges_.push_back(range);
608             }
609 
610             break;
611         }
612     }
613 
614     // Move use positions to the child
615     auto it = use_positions_.lower_bound(ln);
616     split_child->use_positions_.insert(it, use_positions_.end());
617     use_positions_.erase(it, use_positions_.end());
618 
619     return split_child;
620 }
621 
MergeSibling()622 void LifeIntervals::MergeSibling()
623 {
624     ASSERT(sibling_ != nullptr);
625     while (!live_ranges_.empty()) {
626         sibling_->AppendRange(live_ranges_.back());
627         live_ranges_.pop_back();
628     }
629     live_ranges_ = std::move(sibling_->live_ranges_);
630 
631     for (auto &use_pos : sibling_->use_positions_) {
632         AddUsePosition(use_pos);
633     }
634     sibling_ = nullptr;
635 }
636 
FindSiblingAt(LifeNumber ln)637 LifeIntervals *LifeIntervals::FindSiblingAt(LifeNumber ln)
638 {
639     ASSERT(!IsSplitSibling());
640     for (auto head = this; head != nullptr; head = head->GetSibling()) {
641         if (head->GetBegin() <= ln && ln <= head->GetEnd()) {
642             return head;
643         }
644     }
645     return nullptr;
646 }
647 
Intersects(const LiveRange & range) const648 bool LifeIntervals::Intersects(const LiveRange &range) const
649 {
650     return  // the interval starts within the range
651         (range.GetBegin() <= GetBegin() && GetBegin() <= range.GetEnd()) ||
652         // the interval ends within the range
653         (range.GetBegin() <= GetEnd() && GetEnd() <= range.GetEnd()) ||
654         // the range is fully covered by the interval
655         (GetBegin() <= range.GetBegin() && range.GetEnd() <= GetEnd());
656 }
657 
GetFirstIntersectionWith(const LifeIntervals * other,LifeNumber search_from) const658 LifeNumber LifeIntervals::GetFirstIntersectionWith(const LifeIntervals *other, LifeNumber search_from) const
659 {
660     for (auto range : GetRanges()) {
661         if (range.GetEnd() <= search_from) {
662             continue;
663         }
664         for (auto other_range : other->GetRanges()) {
665             if (other_range.GetEnd() <= search_from) {
666                 continue;
667             }
668             auto range_begin = std::max<LifeNumber>(search_from, range.GetBegin());
669             auto other_range_begin = std::max<LifeNumber>(search_from, other_range.GetBegin());
670             if (range_begin <= other_range_begin) {
671                 if (other_range_begin < range.GetEnd()) {
672                     // [range]
673                     //    [other]
674                     return other_range_begin;
675                 }
676                 ASSERT(other_range_begin >= range.GetEnd());
677             } else {
678                 //     [range]
679                 // [other]
680                 if (range_begin < other_range.GetEnd()) {
681                     return range_begin;
682                 }
683                 ASSERT(range_begin >= other_range.GetEnd());
684             }
685         }
686     }
687     return INVALID_LIFE_NUMBER;
688 }
689 
IntersectsWith(const LifeIntervals * other) const690 bool LifeIntervals::IntersectsWith(const LifeIntervals *other) const
691 {
692     return GetFirstIntersectionWith(other) != INVALID_LIFE_NUMBER;
693 }
694 
695 }  // namespace panda::compiler
696