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 "split_resolver.h"
17 #include "compiler/optimizer/ir/inst.h"
18 #include "compiler/optimizer/ir/graph.h"
19 #include "compiler/optimizer/ir/basicblock.h"
20 #include "compiler/optimizer/analysis/dominators_tree.h"
21 #include "compiler/optimizer/analysis/loop_analyzer.h"
22 #include "compiler/optimizer/optimizations/regalloc/reg_alloc_base.h"
23
24 namespace panda::compiler {
25
Run()26 void SplitResolver::Run()
27 {
28 for (auto interval : liveness_->GetLifeIntervals()) {
29 if (interval->GetSibling() == nullptr) {
30 continue;
31 }
32 ASSERT(!interval->IsPhysical());
33
34 // Connect siblings within the same block.
35 ConnectSiblings(interval);
36 }
37 // Resolve locations between basic blocks.
38 for (auto block : liveness_->GetLinearizedBlocks()) {
39 ASSERT(block != nullptr);
40 if (!block->IsEndBlock()) {
41 ProcessBlock(block);
42 }
43 }
44 }
45
ConnectSiblings(LifeIntervals * interval)46 void SplitResolver::ConnectSiblings(LifeIntervals *interval)
47 {
48 for (auto prev = interval, curr = interval->GetSibling(); curr != nullptr; prev = curr, curr = curr->GetSibling()) {
49 if (prev->GetEnd() != curr->GetBegin() || prev->GetLocation() == curr->GetLocation() ||
50 curr->GetLocation().IsConstant()) {
51 continue;
52 }
53 COMPILER_LOG(DEBUG, SPLIT_RESOLVER)
54 << "Connect siblings for inst v" << interval->GetInst()->GetId() << " at point: " << curr->GetBegin();
55
56 ASSERT(curr->IsSplitSibling());
57 auto inst = liveness_->GetInstByLifeNumber(curr->GetBegin() + 1U);
58 // inst == nullptr means that life number corresponds to some PHI instruction (== corresponds to start of
59 // some block), so the SpillFill should be placed at the end of predecessor block.
60 if (inst == nullptr) {
61 continue;
62 }
63
64 auto spill_fill = CreateSpillFillForSiblings(inst);
65 ConnectIntervals(spill_fill, prev, curr);
66 }
67 }
68
ProcessBlock(BasicBlock * block)69 void SplitResolver::ProcessBlock(BasicBlock *block)
70 {
71 auto succ_begin = liveness_->GetBlockLiveRange(block).GetBegin();
72 for (auto interval : liveness_->GetLifeIntervals()) {
73 // PHI and its inputs can be considered as one interval, which was split,
74 // so that the logic is equivalent to the logic of connecting split intervals
75 if (interval->GetBegin() == succ_begin) {
76 auto phi = interval->GetInst();
77 if (!phi->IsPhi() || phi->GetDstReg() == ACC_REG_ID) {
78 continue;
79 }
80 ASSERT(phi->IsPhi());
81 for (size_t i = 0; i < phi->GetInputsCount(); i++) {
82 auto input_inst = phi->GetDataFlowInput(i);
83 auto input_bb = phi->CastToPhi()->GetPhiInputBb(i);
84 auto input_liveness = liveness_->GetInstLifeIntervals(input_inst);
85 ConnectSpiltFromPredBlock(input_bb, input_liveness, block, interval);
86 }
87 continue;
88 }
89
90 // Skip not-splitted instruction
91 if (interval->GetSibling() == nullptr) {
92 continue;
93 }
94 ASSERT(!interval->IsPhysical());
95 auto succ_split = interval->FindSiblingAt(succ_begin);
96 if (succ_split == nullptr || succ_split->GetLocation().IsConstant() || !succ_split->SplitCover(succ_begin)) {
97 continue;
98 }
99 for (auto pred : block->GetPredsBlocks()) {
100 ConnectSpiltFromPredBlock(pred, interval, block, succ_split);
101 }
102 }
103 }
104
ConnectSpiltFromPredBlock(BasicBlock * src_bb,LifeIntervals * src_interval,BasicBlock * target_bb,LifeIntervals * target_split)105 void SplitResolver::ConnectSpiltFromPredBlock(BasicBlock *src_bb, LifeIntervals *src_interval, BasicBlock *target_bb,
106 LifeIntervals *target_split)
107 {
108 BasicBlock *resolver {nullptr};
109 // It's a resolver block inserted during register allocation
110 if (src_bb->GetId() >= liveness_->GetBlocksCount()) {
111 ASSERT(src_bb->GetSuccsBlocks().size() == 1 && src_bb->GetPredsBlocks().size() == 1);
112 resolver = src_bb;
113 src_bb = src_bb->GetPredecessor(0);
114 }
115 auto src_liveness = liveness_->GetBlockLiveRange(src_bb);
116 // Find sibling at the 'end - LIFE_NUMBER_GAP' position to connect siblings that were split at the end of the
117 // 'src_bb'
118 auto src_split = src_interval->FindSiblingAt(src_liveness.GetEnd() - 1U);
119 // Instruction was not defined at predecessor or has the same location there
120 if (src_split == nullptr || src_split->GetLocation() == target_split->GetLocation()) {
121 return;
122 }
123
124 COMPILER_LOG(DEBUG, SPLIT_RESOLVER) << "Resolve split move for inst v" << src_interval->GetInst()->GetId()
125 << " between blocks: BB" << src_bb->GetId() << " -> BB" << target_bb->GetId();
126
127 if (resolver == nullptr) {
128 if (src_bb->GetSuccsBlocks().size() == 1U) {
129 resolver = src_bb;
130 } else {
131 // Get rid of critical edge by inserting a new block and append SpillFill into it.
132 resolver = src_bb->InsertNewBlockToSuccEdge(target_bb);
133 // Fix Dominators info
134 auto &dom_tree = graph_->GetAnalysis<DominatorsTree>();
135 dom_tree.UpdateAfterResolverInsertion(src_bb, target_bb, resolver);
136 graph_->InvalidateAnalysis<LoopAnalyzer>();
137 }
138 }
139 auto spill_fill = CreateSpillFillForSplitMove(resolver);
140 ConnectIntervals(spill_fill, src_split, target_split);
141 }
142
CreateSpillFillForSplitMove(BasicBlock * source_block)143 SpillFillInst *SplitResolver::CreateSpillFillForSplitMove(BasicBlock *source_block)
144 {
145 auto iter = source_block->InstsReverse().begin();
146 while (iter != iter.end() && (*iter)->IsControlFlow() && !(*iter)->IsPhi()) {
147 ++iter;
148 }
149
150 if (iter == iter.end()) {
151 auto spill_fill = graph_->CreateInstSpillFill();
152 spill_fill->SetSpillFillType(SpillFillType::SPLIT_MOVE);
153 source_block->PrependInst(spill_fill);
154 return spill_fill;
155 }
156
157 auto inst = *iter;
158 // Don't reuse CONNECT_SPLIT_SIBLINGS SpillFills to avoid insertion of two opposite spill fill
159 // moves in case when an interval was split after last basic block's instruction and then
160 // it should moved back to original location for successor block:
161 //
162 // BB0:
163 // 2. Add v0, v1 -> r0
164 // BB1:
165 // 4. Sub v0, v2 -> ...
166 // <Split 2's interval and spill to stack slot s0>
167 // <jump to BB1>
168 //
169 // Without CONNECT_SPLIT_SIBLINGS single SpillFillInst would be inserted at the end of BB1
170 // with following moves: r0 -> s0 (to connect siblings), s0 -> r0 (as 2 has different location
171 // at the beginning of BB1). RegAllocResolver may not handle such moves so it should be
172 // avoided.
173 if (inst->IsSpillFill() && !Is<SpillFillType::CONNECT_SPLIT_SIBLINGS>(inst)) {
174 return inst->CastToSpillFill();
175 }
176
177 ASSERT(!inst->IsPhi());
178 auto spill_fill = graph_->CreateInstSpillFill();
179 spill_fill->SetSpillFillType(SpillFillType::SPLIT_MOVE);
180 source_block->InsertAfter(spill_fill, inst);
181 return spill_fill;
182 }
183
CreateSpillFillForSiblings(Inst * connect_at)184 SpillFillInst *SplitResolver::CreateSpillFillForSiblings(Inst *connect_at)
185 {
186 // Try to reuse existing CONNECT_SPLIT_SIBLINGS spill-fill-inst
187 auto prev = connect_at->GetPrev();
188 while (prev != nullptr && prev->IsSpillFill()) {
189 if (Is<SpillFillType::CONNECT_SPLIT_SIBLINGS>(prev)) {
190 return prev->CastToSpillFill();
191 }
192 ASSERT(Is<SpillFillType::INPUT_FILL>(prev));
193 connect_at = prev;
194 prev = prev->GetPrev();
195 }
196 auto spill_fill = graph_->CreateInstSpillFill();
197 spill_fill->SetSpillFillType(SpillFillType::CONNECT_SPLIT_SIBLINGS);
198 connect_at->InsertBefore(spill_fill);
199 return spill_fill;
200 }
201
202 } // namespace panda::compiler
203