1 /*
2 * Copyright (c) 2023-2024 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 #include "compiler_logger.h"
16 #include "optimizer/analysis/alias_analysis.h"
17 #include "optimizer/analysis/bounds_analysis.h"
18 #include "optimizer/analysis/loop_analyzer.h"
19 #include "optimizer/analysis/dominators_tree.h"
20 #include "licm_conditions.h"
21
22 namespace ark::compiler {
RunImpl()23 bool LicmConditions::RunImpl()
24 {
25 conditionChainManager_.Reset();
26 MarkerHolder hoistableInstMh(GetGraph());
27 MarkerHolder processedBlocksMh(GetGraph());
28 hoistableInstMarker_ = hoistableInstMh.GetMarker();
29 processedBlocksMarker_ = processedBlocksMh.GetMarker();
30 COMPILER_LOG(DEBUG, LOOP_TRANSFORM) << "Run " << GetPassName();
31 GetGraph()->RunPass<DominatorsTree>();
32 MarkHoistableInst();
33 RunLoopsVisitor();
34 COMPILER_LOG(DEBUG, LOOP_TRANSFORM) << GetPassName() << " complete";
35 return isApplied_;
36 }
37
MarkHoistableInst()38 void LicmConditions::MarkHoistableInst()
39 {
40 for (auto bb : GetGraph()->GetBlocksRPO()) {
41 if (!bb->IsLoopValid()) {
42 continue;
43 }
44 auto loop = bb->GetLoop();
45 if (loop->IsRoot() || loop->IsIrreducible()) {
46 continue;
47 }
48 for (auto inst : bb->PhiInsts()) {
49 if (AllInputsDominate(inst, loop)) {
50 inst->SetMarker(hoistableInstMarker_);
51 }
52 }
53 if (bb->GetSuccsBlocks().size() == MAX_SUCCS_NUM) {
54 auto lastInst = bb->GetLastInst();
55 if (AllInputsDominate(lastInst, loop)) {
56 lastInst->SetMarker(hoistableInstMarker_);
57 }
58 }
59 }
60 }
61
TransformLoop(Loop * loop)62 bool LicmConditions::TransformLoop(Loop *loop)
63 {
64 samePhiInput_.clear();
65 conditionChainsCache_.Clear();
66 FindHoistableConditionChains(loop);
67 HoistConditionChains(loop);
68 return true;
69 }
70
FindHoistableConditionChains(Loop * loop)71 void LicmConditions::FindHoistableConditionChains(Loop *loop)
72 {
73 conditionChainsCtx_.clear();
74 for (auto block : loop->GetBlocks()) {
75 auto chain = conditionChainManager_.FindConditionChain(block);
76 if (chain == nullptr) {
77 continue;
78 }
79 auto multiplePredsSucc = chain->GetMultiplePredecessorsSuccessor();
80 auto singlePredSucc = chain->GetSinglePredecessorSuccessor();
81 COMPILER_LOG(DEBUG, LICM_COND_OPT)
82 << "Found conditions chain " << chain->GetFirstBlock()->GetId() << "->" << chain->GetLastBlock()->GetId()
83 << ", succs: " << multiplePredsSucc->GetId() << ", " << singlePredSucc->GetId();
84 if (!IsHoistable(chain)) {
85 COMPILER_LOG(DEBUG, LICM_COND_OPT) << "Skip not hoistable chain";
86 continue;
87 }
88 auto hoistPhiAvailable = IsHoistPhiAvailable(chain, multiplePredsSucc->GetPredsBlocks(), singlePredSucc);
89 if (!AllPhiAllowConditionChainHoisting(chain, multiplePredsSucc, hoistPhiAvailable)) {
90 COMPILER_LOG(DEBUG, LICM_COND_OPT) << "Skip not all phi are suitable";
91 continue;
92 }
93 conditionChainsCtx_.emplace_back(chain, multiplePredsSucc, singlePredSucc, hoistPhiAvailable);
94 }
95 std::sort(conditionChainsCtx_.begin(), conditionChainsCtx_.end(),
96 [](auto a, auto b) { return a.GetChain()->GetSize() > b.GetChain()->GetSize(); });
97 }
98
IsHoistable(const ConditionChain * chain)99 bool LicmConditions::IsHoistable(const ConditionChain *chain)
100 {
101 auto last = chain->GetEnd();
102 for (auto bbIt = chain->GetBegin(); bbIt != last; ++bbIt) {
103 auto bb = *bbIt;
104 auto lastInst = bb->GetLastInst();
105 if (lastInst->GetOpcode() != Opcode::IfImm) {
106 return false;
107 }
108 if (!lastInst->IsMarked(hoistableInstMarker_)) {
109 return false;
110 }
111 }
112 return true;
113 }
114
115 // After LICM pass all hoistable inputs should be moved out from loop
AllInputsDominate(const Inst * inst,const Loop * loop)116 bool LicmConditions::AllInputsDominate(const Inst *inst, const Loop *loop)
117 {
118 auto preheader = loop->GetPreHeader();
119 for (size_t i = 0; i < inst->GetInputsCount(); i++) {
120 if (!inst->GetInput(i).GetInst()->GetBasicBlock()->IsDominate(preheader)) {
121 return false;
122 }
123 }
124 return true;
125 }
126
IsHoistPhiAvailable(const ConditionChain * chain,ArenaVector<BasicBlock * > & preds,const BasicBlock * singlePredSucc)127 bool LicmConditions::IsHoistPhiAvailable(const ConditionChain *chain, ArenaVector<BasicBlock *> &preds,
128 const BasicBlock *singlePredSucc)
129 {
130 for (auto pred : preds) {
131 if (!chain->Contains(pred) && pred != singlePredSucc) {
132 return false;
133 }
134 }
135 return true;
136 }
137
AllPhiAllowConditionChainHoisting(const ConditionChain * chain,const BasicBlock * multiplePredsSucc,bool hoistPhiAvailable)138 bool LicmConditions::AllPhiAllowConditionChainHoisting(const ConditionChain *chain, const BasicBlock *multiplePredsSucc,
139 bool hoistPhiAvailable)
140 {
141 for (auto phi : multiplePredsSucc->PhiInsts()) {
142 if (hoistPhiAvailable && phi->IsMarked(hoistableInstMarker_)) {
143 continue;
144 }
145 auto sameInput = SamePhiInputFromChain(phi, chain);
146 if (sameInput == nullptr) {
147 return false;
148 }
149 samePhiInput_.insert({std::make_pair(chain, phi), sameInput});
150 }
151 return true;
152 }
153
SamePhiInputFromChain(Inst * phi,const ConditionChain * chain)154 Inst *LicmConditions::SamePhiInputFromChain(Inst *phi, const ConditionChain *chain)
155 {
156 Inst *savedInput = nullptr;
157 auto bb = phi->GetBasicBlock();
158 for (auto pred : bb->GetPredsBlocks()) {
159 if (!chain->Contains(pred)) {
160 continue;
161 }
162 auto predIndex = bb->GetPredBlockIndex(pred);
163 auto input = phi->GetInput(predIndex).GetInst();
164 if (savedInput == nullptr) {
165 savedInput = input;
166 } else if (savedInput != input) {
167 return nullptr;
168 } else {
169 continue;
170 }
171 }
172 return savedInput;
173 }
174
175 /*
176 * Move condition chains which look like
177 *
178 * | |
179 * v v
180 * [A]------\
181 * | |
182 * | v
183 * |<-----[B]
184 * | |
185 * v v
186 * -->[S0] [S1]<--
187 * | |
188 * v v
189 *
190 * out of the loop if possible.
191 * After whole chain is moved out it looks like
192 *
193 * |
194 * v
195 * [A]------\
196 * | |
197 * | v
198 * |<-----[B]
199 * | |
200 * | v
201 * | [empty_block]
202 * | |
203 * v v
204 * [phi_block]
205 * |
206 * v
207 * [loop preheader]
208 *
209 * phi_block contains either new phi instructions which is result of condition chain
210 * (single_condition_block uses it) or phi which was hoisted from `multiple_predecessors successor.
211 * Condition chain is replaced in loop with single_condition_block
212 *
213 * |
214 * v
215 * [single_condition_block]
216 * | |
217 * v v
218 * -->[S0] [S1]<--
219 * | |
220 * v v
221 */
HoistConditionChains(Loop * loop)222 void LicmConditions::HoistConditionChains(Loop *loop)
223 {
224 auto appendBb = loop->GetPreHeader();
225 for (auto chainCtx : conditionChainsCtx_) {
226 auto chain = chainCtx.GetChain();
227 auto chainFirstBlock = chain->GetFirstBlock();
228 if (chainFirstBlock->IsMarked(processedBlocksMarker_)) {
229 COMPILER_LOG(DEBUG, LICM_COND_OPT)
230 << "Skip chain with first block #" << chainFirstBlock->GetId() << ", longer chain was processed";
231 continue;
232 }
233
234 auto multiplePredsSucc = chain->GetMultiplePredecessorsSuccessor();
235 auto singlePredSucc = chain->GetSinglePredecessorSuccessor();
236
237 COMPILER_LOG(DEBUG, LICM_COND_OPT)
238 << "Process conditions chain " << chainFirstBlock->GetId() << "->" << chain->GetLastBlock()->GetId()
239 << ", succs: " << multiplePredsSucc->GetId() << ", " << singlePredSucc->GetId();
240
241 SaveProcessedBlocks(chain);
242 SplitChainFirstBasicBlock(chain);
243
244 // update chain successors because they can be changed during previous transformations
245 chainCtx.SetMultiplePredecessorsSuccessor(multiplePredsSucc);
246 chainCtx.SetSingleSPredecessorSuccessor(singlePredSucc);
247
248 appendBb = ReplaceChainWithSingleBlock(appendBb, chainCtx);
249
250 isApplied_ = true;
251 }
252 }
253
SaveProcessedBlocks(const ConditionChain * chain)254 void LicmConditions::SaveProcessedBlocks(const ConditionChain *chain)
255 {
256 std::for_each(chain->GetBegin(), chain->GetEnd(),
257 [this](BasicBlock *bb) { bb->SetMarker(processedBlocksMarker_); });
258 }
259
SaveMulitplePredecessorsSuccessorPreds(const BasicBlock * bb)260 void LicmConditions::SaveMulitplePredecessorsSuccessorPreds(const BasicBlock *bb)
261 {
262 multiplePredecessorsSuccessorPreds_.clear();
263 std::copy(bb->GetPredsBlocks().begin(), bb->GetPredsBlocks().end(),
264 std::back_inserter(multiplePredecessorsSuccessorPreds_));
265 }
266
SplitChainFirstBasicBlock(ConditionChain * chain)267 void LicmConditions::SplitChainFirstBasicBlock(ConditionChain *chain)
268 {
269 auto chainFirstBb = chain->GetFirstBlock();
270 auto prelastInst = chainFirstBb->GetLastInst()->GetPrev();
271 if (prelastInst == nullptr) {
272 return;
273 }
274 auto newFirstBb = chainFirstBb->SplitBlockAfterInstruction(prelastInst, true);
275 chain->SetFirstBlock(newFirstBb);
276 COMPILER_LOG(DEBUG, LICM_COND_OPT) << "Split first chain block " << chainFirstBb->GetId() << "->"
277 << newFirstBb->GetId();
278 }
279
ReplaceChainWithSingleBlock(BasicBlock * appendBb,const ConditionChainContext & chainCtx)280 BasicBlock *LicmConditions::ReplaceChainWithSingleBlock(BasicBlock *appendBb, const ConditionChainContext &chainCtx)
281 {
282 auto chain = chainCtx.GetChain();
283 // try to find condition chain which is looking like this
284 auto cachedPhi = conditionChainsCache_.FindPhi(chain);
285 auto multiplePredsSucc = chainCtx.GetMultiplePredecessorsSuccessor();
286 auto singlePredSucc = chainCtx.GetSinglePredecessorSuccessor();
287 SaveMulitplePredecessorsSuccessorPreds(multiplePredsSucc);
288
289 auto singleConditionBlock = GetGraph()->CreateEmptyBlock();
290 AdjustPredecessorEdges(chain->GetFirstBlock(), singleConditionBlock);
291
292 singleConditionBlock->AddSucc(multiplePredsSucc);
293 // NOTE: multiple_preds_succ preds are not fixed
294 auto chainLastBlock = chain->GetLastBlock();
295 singlePredSucc->ReplacePred(chainLastBlock, singleConditionBlock);
296
297 auto phiBlock = GetGraph()->CreateEmptyBlock();
298 auto appendBbSucc = appendBb->GetSuccessor(0);
299 appendBb->ReplaceSucc(appendBbSucc, chain->GetFirstBlock());
300 appendBbSucc->ReplacePred(appendBb, phiBlock);
301
302 auto emptyBlock = GetGraph()->CreateEmptyBlock();
303 chainLastBlock->ReplaceSucc(singlePredSucc, emptyBlock, true);
304
305 UpdateMultiplePredecessorsSuccessorsPreds(chainCtx, phiBlock, emptyBlock);
306 UpdatePhis(chain, multiplePredsSucc, phiBlock, chainCtx.IsHoistPhiAvailable());
307
308 Inst *phiInst;
309 if (cachedPhi != nullptr) {
310 phiInst = cachedPhi;
311 } else {
312 phiInst = AddPhiInst(phiBlock, chain);
313 conditionChainsCache_.Insert(chain, phiInst);
314 }
315 AddSingleIfImmInst(singleConditionBlock, chain, phiInst);
316 return phiBlock;
317 }
318
AddPhiInst(BasicBlock * bb,const ConditionChain * chain)319 PhiInst *LicmConditions::AddPhiInst(BasicBlock *bb, const ConditionChain *chain)
320 {
321 auto graph = bb->GetGraph();
322 auto oneCnst = graph->FindOrCreateConstant(1);
323 auto zeroCnst = graph->FindOrCreateConstant(0);
324 auto phiInst = graph->CreateInstPhi(DataType::BOOL, INVALID_PC);
325 bb->AppendPhi(phiInst);
326 for (auto pred : bb->GetPredsBlocks()) {
327 phiInst->AppendInput(chain->Contains(pred) ? oneCnst : zeroCnst);
328 }
329 return phiInst;
330 }
331
AddSingleIfImmInst(BasicBlock * bb,const ConditionChain * chain,Inst * input)332 void LicmConditions::AddSingleIfImmInst(BasicBlock *bb, const ConditionChain *chain, Inst *input)
333 {
334 auto origIfInst = chain->GetLastBlock()->GetLastInst()->CastToIfImm();
335 auto ifInst = bb->GetGraph()->CreateInstIfImm(DataType::NO_TYPE, 0, input, 0, DataType::BOOL, ConditionCode::CC_NE,
336 origIfInst->GetMethod());
337 bb->AppendInst(ifInst);
338 }
339
AdjustPredecessorEdges(BasicBlock * chainFirstBb,BasicBlock * bb)340 void LicmConditions::AdjustPredecessorEdges(BasicBlock *chainFirstBb, BasicBlock *bb)
341 {
342 for (auto pred : chainFirstBb->GetPredsBlocks()) {
343 pred->ReplaceSucc(chainFirstBb, bb);
344 }
345 chainFirstBb->GetPredsBlocks().clear();
346 }
347
UpdateMultiplePredecessorsSuccessorsPreds(const ConditionChainContext & chainCtx,BasicBlock * phiBlock,BasicBlock * emptyBlock)348 void LicmConditions::UpdateMultiplePredecessorsSuccessorsPreds(const ConditionChainContext &chainCtx,
349 BasicBlock *phiBlock, BasicBlock *emptyBlock)
350 {
351 auto chain = chainCtx.GetChain();
352 auto multiplePredsSucc = chainCtx.GetMultiplePredecessorsSuccessor();
353 auto singlePredSucc = chainCtx.GetSinglePredecessorSuccessor();
354 multiplePredecessorsSuccessorRemovedPredIndices_.clear();
355 // keep predecessors order in phi_block
356 for (auto bb : multiplePredecessorsSuccessorPreds_) {
357 if (chain->Contains(bb)) {
358 COMPILER_LOG(DEBUG, LICM_COND_OPT)
359 << "Update chain block " << bb->GetId() << " successor: " << multiplePredsSucc->GetId() << "->"
360 << phiBlock->GetId();
361 bb->ReplaceSucc(multiplePredsSucc, phiBlock, true);
362 auto predIndex = multiplePredsSucc->GetPredBlockIndex(bb);
363 multiplePredsSucc->RemovePred(predIndex);
364 multiplePredecessorsSuccessorRemovedPredIndices_.push_back(predIndex);
365 } else if (bb == singlePredSucc) {
366 COMPILER_LOG(DEBUG, LICM_COND_OPT)
367 << "Add new edge to phi_block corresponding to edge between chain successors";
368 emptyBlock->AddSucc(phiBlock, true);
369 } else {
370 COMPILER_LOG(DEBUG, LICM_COND_OPT) << "Skip predecessor " << bb->GetId();
371 }
372 }
373 if (emptyBlock->GetSuccsBlocks().empty()) {
374 COMPILER_LOG(DEBUG, LICM_COND_OPT) << "Add last edge to phi_block";
375 emptyBlock->AddSucc(phiBlock, true);
376 }
377 }
378
UpdatePhis(const ConditionChain * chain,BasicBlock * multiplePredsSucc,BasicBlock * phiBlock,bool hoistPhiAvailable)379 void LicmConditions::UpdatePhis(const ConditionChain *chain, BasicBlock *multiplePredsSucc, BasicBlock *phiBlock,
380 bool hoistPhiAvailable)
381 {
382 for (auto phi : multiplePredsSucc->PhiInstsSafe()) {
383 if (hoistPhiAvailable && phi->IsMarked(hoistableInstMarker_)) {
384 COMPILER_LOG(DEBUG, LICM_COND_OPT) << "Hoist phi " << phi->GetId();
385 multiplePredsSucc->EraseInst(phi);
386 // preds order was preserved
387 phiBlock->AppendPhi(phi);
388 if (phi->GetInputsCount() >= phiBlock->GetPredsBlocks().size()) {
389 ASSERT(phi->GetInputsCount() == phiBlock->GetPredsBlocks().size());
390 continue;
391 }
392 COMPILER_LOG(DEBUG, LICM_COND_OPT) << "Add dummy input";
393 if (DataType::IsReference(phi->GetType())) {
394 phi->AppendInput(GetGraph()->GetOrCreateNullPtr());
395 } else {
396 phi->AppendInput(GetGraph()->FindOrCreateConstant(0));
397 }
398 ASSERT(phi->GetInputsCount() == phiBlock->GetPredsBlocks().size());
399 } else {
400 COMPILER_LOG(DEBUG, LICM_COND_OPT) << "Update inputs for phi " << phi->GetId();
401 auto key = std::make_pair(chain, phi);
402 ASSERT(samePhiInput_.count(key) != 0);
403 phi->AppendInput(samePhiInput_[key]);
404 for (size_t i : multiplePredecessorsSuccessorRemovedPredIndices_) {
405 phi->RemoveInput(i);
406 }
407 }
408 }
409 }
410
InvalidateAnalyses()411 void LicmConditions::InvalidateAnalyses()
412 {
413 GetGraph()->InvalidateAnalysis<BoundsAnalysis>();
414 GetGraph()->InvalidateAnalysis<AliasAnalysis>();
415 GetGraph()->InvalidateAnalysis<LoopAnalyzer>();
416 InvalidateBlocksOrderAnalyzes(GetGraph());
417 }
418 } // namespace ark::compiler
419