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
16 #include "compiler_logger.h"
17 #include "optimizer/analysis/alias_analysis.h"
18 #include "optimizer/analysis/dominators_tree.h"
19 #include "optimizer/analysis/countable_loop_parser.h"
20 #include "optimizer/optimizations/loop_idioms.h"
21
22 // CC-OFFNXT(G.PRE.02) necessary macro
23 // NOLINTNEXTLINE(cppcoreguidelines-macro-usage)
24 #define LOG_ARRAYMOVE(level) COMPILER_LOG(level, LOOP_TRANSFORM) << "[Arraymove] "
25
26 namespace ark::compiler {
RunImpl()27 bool LoopIdioms::RunImpl()
28 {
29 if (GetGraph()->GetArch() == Arch::AARCH32) {
30 // Supported idioms and intrinsics emitted for them could not be encoded on Arm32.
31 return false;
32 }
33 GetGraph()->RunPass<LoopAnalyzer>();
34 RunLoopsVisitor();
35 return isApplied_;
36 }
37
InvalidateAnalyses()38 void LoopIdioms::InvalidateAnalyses()
39 {
40 GetGraph()->InvalidateAnalysis<LoopAnalyzer>();
41 InvalidateBlocksOrderAnalyzes(GetGraph());
42 }
43
TransformLoop(Loop * loop)44 bool LoopIdioms::TransformLoop(Loop *loop)
45 {
46 if (loop->GetInnerLoops().empty()) {
47 if (TryTransformArrayInitIdiom(loop) || TryTransformArrayMoveIdiom(loop)) {
48 isApplied_ = true;
49 }
50 }
51 return false;
52 }
53
FindStoreForArrayInit(BasicBlock * block)54 StoreInst *FindStoreForArrayInit(BasicBlock *block)
55 {
56 StoreInst *store {nullptr};
57 for (auto inst : block->Insts()) {
58 if (inst->GetOpcode() != Opcode::StoreArray) {
59 continue;
60 }
61 if (store != nullptr) {
62 return nullptr;
63 }
64 store = inst->CastToStoreArray();
65 }
66 // should be a loop invariant
67 if (store != nullptr && store->GetStoredValue()->GetBasicBlock()->GetLoop() == block->GetLoop()) {
68 return nullptr;
69 }
70 return store;
71 }
72
ExtractArrayInitInitialIndexValue(PhiInst * index)73 Inst *ExtractArrayInitInitialIndexValue(PhiInst *index)
74 {
75 auto block = index->GetBasicBlock();
76 BasicBlock *pred = block->GetPredsBlocks().front();
77 if (pred == block) {
78 pred = block->GetPredsBlocks().back();
79 }
80 return index->GetPhiInput(pred);
81 }
82
AllUsesWithinLoop(Inst * inst,const Loop * loop)83 bool AllUsesWithinLoop(Inst *inst, const Loop *loop)
84 {
85 for (auto &user : inst->GetUsers()) {
86 if (user.GetInst()->GetBasicBlock()->GetLoop() != loop) {
87 return false;
88 }
89 }
90 return true;
91 }
92
CanReplaceLoop(Loop * loop,Marker marker)93 bool CanReplaceLoop(Loop *loop, Marker marker)
94 {
95 ASSERT(loop->GetBlocks().size() == 1);
96 auto block = loop->GetHeader();
97 for (auto inst : block->AllInsts()) {
98 if (inst->IsMarked(marker)) {
99 continue;
100 }
101 auto opcode = inst->GetOpcode();
102 if (opcode != Opcode::NOP && opcode != Opcode::SaveState && opcode != Opcode::SafePoint) {
103 return false;
104 }
105 }
106 return true;
107 }
108
IsLoopContainsArrayInitIdiom(StoreInst * store,Loop * loop,CountableLoopInfo & loopInfo)109 bool IsLoopContainsArrayInitIdiom(StoreInst *store, Loop *loop, CountableLoopInfo &loopInfo)
110 {
111 auto storeIdx = store->GetIndex();
112
113 return loopInfo.constStep == 1UL && loopInfo.index == storeIdx && loopInfo.normalizedCc == ConditionCode::CC_LT &&
114 AllUsesWithinLoop(storeIdx, loop) && AllUsesWithinLoop(loopInfo.update, loop) &&
115 AllUsesWithinLoop(loopInfo.ifImm->GetInput(0).GetInst(), loop);
116 }
117
IsLoopContainsArrayMoveIdiom(StoreInst * store,Loop * loop,CountableLoopInfo & loopInfo)118 bool IsLoopContainsArrayMoveIdiom(StoreInst *store, Loop *loop, CountableLoopInfo &loopInfo)
119 {
120 auto storeIdx = store->GetIndex();
121
122 return loopInfo.constStep == 1UL && loopInfo.index == storeIdx && loopInfo.normalizedCc == ConditionCode::CC_LT &&
123 AllUsesWithinLoop(storeIdx, loop) && AllUsesWithinLoop(loopInfo.update, loop) &&
124 AllUsesWithinLoop(loopInfo.ifImm->GetInput(0).GetInst(), loop);
125 }
126
127 // NOLINTNEXTLINE(fuchsia-multiple-inheritance)
128 class ArrayMoveParser : private CountableLoopParser, private MarkerHolder {
129 public:
ArrayMoveParser(Loop * loop)130 explicit ArrayMoveParser(Loop *loop) : CountableLoopParser(*loop), MarkerHolder(loop->GetHeader()->GetGraph()) {}
131
Parse()132 bool Parse()
133 {
134 // Check loop shape:
135 if (!CountableLoopParser::Parse() || loopInfo_.constStep != 1) {
136 LOG_ARRAYMOVE(DEBUG) << "Loop shape doesn't match";
137 return false;
138 }
139
140 if (!FindStoreLoad() || !CheckOffsets() || !CheckLoopIsolation()) {
141 LOG_ARRAYMOVE(DEBUG) << "Dataflow pattern doesn't match";
142 return false;
143 }
144
145 return true;
146 }
147
FindStoreLoad()148 bool FindStoreLoad()
149 {
150 for (auto inst : loop_.GetHeader()->Insts()) {
151 if (inst->GetOpcode() != Opcode::StoreArray) {
152 continue;
153 }
154 auto store = inst->CastToStoreArray();
155 auto storedValue = store->GetStoredValue();
156 if (storedValue->GetOpcode() != Opcode::LoadArray || storedValue->GetBasicBlock() != loop_.GetHeader()) {
157 return false;
158 }
159 store_.inst = store;
160 load_.inst = storedValue->CastToLoadArray();
161 return DataType::GetTypeSize(store_.inst->GetType(), GetGraph()->GetArch()) ==
162 DataType::GetTypeSize(load_.inst->GetType(), GetGraph()->GetArch());
163 }
164 return false;
165 }
166
167 // Check and extract `Add/Sub(loopIndex, loopInvariant)` combination:
168 template <typename T>
ExtractInductionVariableOffset(T * desc)169 bool ExtractInductionVariableOffset(T *desc)
170 {
171 auto inductionVar = desc->inst->GetIndex();
172 if (inductionVar == loopInfo_.index) {
173 desc->idxOffset = inductionVar->GetBasicBlock()->GetGraph()->FindOrCreateConstant(0);
174 return true;
175 }
176
177 auto chkInputs = [inductionVar, this](size_t i0, size_t i1) {
178 return (inductionVar->GetInput(i0).GetInst() == loopInfo_.index) &&
179 (inductionVar->GetInput(i1).GetInst()->GetBasicBlock()->GetLoop() != &loop_);
180 };
181
182 if (inductionVar->GetOpcode() == Opcode::Add) {
183 for (size_t i = 0; i < 2U; i++) {
184 if (chkInputs(i, 1 - i)) {
185 desc->idxOffset = inductionVar->GetInput(1 - i).GetInst();
186 return true;
187 }
188 }
189 }
190
191 if (inductionVar->GetOpcode() == Opcode::Sub) {
192 if (chkInputs(0, 1)) {
193 desc->idxOffset = inductionVar->GetInput(1).GetInst();
194 desc->idxOffsetNegate = true;
195 return true;
196 }
197 }
198 return false;
199 }
200
CheckOffsets()201 bool CheckOffsets()
202 {
203 if (!ExtractInductionVariableOffset(&store_)) {
204 return false;
205 }
206 if (!ExtractInductionVariableOffset(&load_)) {
207 return false;
208 }
209 ASSERT(store_.idxOffset->GetBasicBlock()->GetLoop() != &loop_);
210 ASSERT(load_.idxOffset->GetBasicBlock()->GetLoop() != &loop_);
211 return true;
212 }
213
CheckLoopIsolation()214 bool CheckLoopIsolation()
215 {
216 auto compare = loopInfo_.ifImm->GetInput(0).GetInst();
217 ASSERT(compare->GetOpcode() == Opcode::Compare);
218 std::array<Inst *, 8U> matched = {
219 loopInfo_.ifImm, compare, loopInfo_.update, loopInfo_.index, load_.inst,
220 load_.inst->GetIndex(), store_.inst, store_.inst->GetIndex()};
221
222 for (Inst *inst : matched) {
223 ASSERT(inst->GetBasicBlock()->GetLoop() == &loop_);
224 if (!AllUsesWithinLoop(inst, &loop_)) {
225 LOG_ARRAYMOVE(DEBUG) << "Inst '" << inst->GetId() << ".' used outside";
226 return false;
227 }
228 inst->SetMarker(GetMarker());
229 }
230
231 for (auto inst : loop_.GetHeader()->AllInsts()) {
232 if (inst->IsMarked(GetMarker())) {
233 continue;
234 }
235 if ((inst->IsCall() && static_cast<CallInst *>(inst)->IsInlined()) ||
236 inst->GetOpcode() == Opcode::ReturnInlined) {
237 continue;
238 }
239 auto opcode = inst->GetOpcode();
240 if (opcode == Opcode::NOP || opcode == Opcode::SaveState || opcode == Opcode::SafePoint) {
241 continue;
242 }
243 LOG_ARRAYMOVE(DEBUG) << "Inst '" << inst->GetId() << ".' breaks pattern";
244 return false;
245 }
246 return true;
247 }
248
249 template <RuntimeInterface::IntrinsicId ID = RuntimeInterface::IntrinsicId::INVALID>
CreateIntrinsic()250 IntrinsicInst *CreateIntrinsic()
251 {
252 if constexpr (ID == RuntimeInterface::IntrinsicId::LIB_CALL_MEM_COPY) {
253 return GetGraph()->CreateInstIntrinsic(DataType::VOID, store_.inst->GetPc(), ID);
254 } else {
255 auto id = RuntimeInterface::IntrinsicId::INVALID;
256 switch (store_.inst->GetType()) {
257 case DataType::BOOL:
258 case DataType::INT8:
259 case DataType::UINT8:
260 id = RuntimeInterface::IntrinsicId::INTRINSIC_COMPILER_MEMMOVE_UNCHECKED_1_BYTE;
261 break;
262 case DataType::INT16:
263 case DataType::UINT16:
264 id = RuntimeInterface::IntrinsicId::INTRINSIC_COMPILER_MEMMOVE_UNCHECKED_2_BYTE;
265 break;
266 case DataType::INT32:
267 case DataType::UINT32:
268 case DataType::FLOAT32:
269 id = RuntimeInterface::IntrinsicId::INTRINSIC_COMPILER_MEMMOVE_UNCHECKED_4_BYTE;
270 break;
271 case DataType::INT64:
272 case DataType::UINT64:
273 case DataType::FLOAT64:
274 id = RuntimeInterface::IntrinsicId::INTRINSIC_COMPILER_MEMMOVE_UNCHECKED_8_BYTE;
275 break;
276 default:
277 LOG_ARRAYMOVE(DEBUG) << "Store has unsupported type " << store_.inst->GetType();
278 return nullptr;
279 }
280 return GetGraph()->CreateInstIntrinsic(DataType::VOID, store_.inst->GetPc(), id);
281 }
282 UNREACHABLE();
283 }
284
TryReplaceLoop()285 bool TryReplaceLoop()
286 {
287 auto aliasType = CheckRefAlias();
288 if (aliasType == NO_ALIAS) {
289 return ReplaceLoopCompletely();
290 }
291 LOG_ARRAYMOVE(DEBUG) << "Overlapping regions are not supported";
292 return false;
293 }
294
CheckRefAlias()295 AliasType CheckRefAlias()
296 {
297 auto src = load_.inst->GetDataFlowInput(0);
298 auto dst = store_.inst->GetDataFlowInput(0);
299 auto &aa = GetGraph()->GetValidAnalysis<AliasAnalysis>();
300 auto aliasType = aa.CheckRefAlias(src, dst);
301 if ((aliasType == MAY_ALIAS) && (dst->GetOpcode() == Opcode::NewArray) &&
302 (src->GetOpcode() == Opcode::Parameter)) {
303 aliasType = NO_ALIAS;
304 }
305 return aliasType;
306 }
307
308 template <typename T>
NegateIfNeeded(T * desc,BasicBlock * b)309 void NegateIfNeeded(T *desc, BasicBlock *b)
310 {
311 if (desc->idxOffsetNegate) {
312 auto offset = desc->idxOffset;
313 auto neg = GetGraph()->CreateInstNeg(offset->GetType(), offset->GetPc(), offset);
314 b->AppendInst(neg);
315 desc->idxOffset = neg;
316 }
317 }
318
PatchRange(Inst ** srcStart,Inst ** srcEnd,BasicBlock * newB)319 void PatchRange(Inst **srcStart, Inst **srcEnd, BasicBlock *newB)
320 {
321 auto one = GetGraph()->FindOrCreateConstant(1);
322 switch (loopInfo_.normalizedCc) {
323 case CC_GE: {
324 // Transform interval [e,s] to [e, s + 1)
325 ASSERT(!loopInfo_.isInc);
326 std::swap(*srcStart, *srcEnd);
327 auto add = GetGraph()->CreateInstAdd((*srcEnd)->GetType(), (*srcEnd)->GetPc(), (*srcEnd), one);
328 newB->AppendInst(add);
329 *srcEnd = add;
330 break;
331 }
332 case CC_GT: {
333 // Transform interval (e,s] to [e + 1, s + 1)
334 ASSERT(!loopInfo_.isInc);
335 std::swap(*srcStart, *srcEnd);
336 auto addStart =
337 GetGraph()->CreateInstAdd((*srcStart)->GetType(), (*srcStart)->GetPc(), (*srcStart), one);
338 auto addEnd = GetGraph()->CreateInstAdd((*srcEnd)->GetType(), (*srcEnd)->GetPc(), (*srcEnd), one);
339 newB->AppendInst(addStart);
340 newB->AppendInst(addEnd);
341 *srcStart = addStart;
342 *srcEnd = addEnd;
343 break;
344 }
345 case CC_LE: {
346 // Transform interval [s,e] to [s, e + 1)
347 ASSERT(loopInfo_.isInc);
348 auto add = GetGraph()->CreateInstAdd((*srcEnd)->GetType(), (*srcEnd)->GetPc(), (*srcEnd), one);
349 newB->AppendInst(add);
350 *srcEnd = add;
351 break;
352 }
353 case CC_LT: {
354 // [s,e) => s' = s, e' = e;
355 ASSERT(loopInfo_.isInc);
356 break;
357 }
358 default:
359 UNREACHABLE();
360 }
361 }
362
ReplaceLoopCompletely()363 bool ReplaceLoopCompletely()
364 {
365 auto mmove = CreateIntrinsic();
366 if (mmove == nullptr) {
367 return false;
368 }
369 auto newB = GetGraph()->CreateEmptyBlock(store_.inst->GetPc());
370 // 1. Normalize 'load_index/store_index == Sub(idx, c)' -> 'load_index/store_index == Add(idx, Neg(c))':
371 NegateIfNeeded(&load_, newB);
372 NegateIfNeeded(&store_, newB);
373 // 2. Calculate start/end value of load_index:
374 // i.e. define [s,e) or [s,e] or [e,s] or (e,s]
375 Inst *srcStart =
376 GetGraph()->CreateInstAdd(DataType::INT32, load_.inst->GetPc(), loopInfo_.init, load_.idxOffset);
377 newB->AppendInst(srcStart);
378 Inst *srcEnd = GetGraph()->CreateInstAdd(DataType::INT32, load_.inst->GetPc(), loopInfo_.test, load_.idxOffset);
379 newB->AppendInst(srcEnd);
380 // 3. Handle cases of 'srcStart > srcEnd' and patch range enclosing.
381 // i.e. normalize [s,e), [s,e], [e,s], (e,s] -> [s',e').
382 PatchRange(&srcStart, &srcEnd, newB);
383
384 // 4. Calculate 'dstStart' based on 'srcStart' and idxOffsets' diff:
385 auto offsDiff =
386 GetGraph()->CreateInstSub(DataType::INT32, store_.inst->GetPc(), store_.idxOffset, load_.idxOffset);
387 newB->AppendInst(offsDiff);
388 auto dstStart = GetGraph()->CreateInstAdd(DataType::INT32, store_.inst->GetPc(), srcStart, offsDiff);
389 newB->AppendInst(dstStart);
390
391 newB->AppendInst(mmove);
392 mmove->ClearFlag(inst_flags::Flags::REQUIRE_STATE);
393 mmove->ClearFlag(inst_flags::Flags::RUNTIME_CALL);
394 mmove->ClearFlag(inst_flags::Flags::CAN_THROW);
395 mmove->SetInputs(GetGraph()->GetAllocator(), {{load_.inst->GetArray(), DataType::REFERENCE},
396 {store_.inst->GetArray(), DataType::REFERENCE},
397 {dstStart, dstStart->GetType()},
398 {srcStart, srcStart->GetType()},
399 {srcEnd, srcEnd->GetType()}});
400 auto header = loop_.GetHeader();
401 auto preheader = loop_.GetPreHeader();
402 auto outside = header->GetSuccessor(0) != header ? header->GetSuccessor(0) : header->GetSuccessor(1);
403 preheader->SetNextLoop(nullptr);
404 preheader->ReplaceSucc(header, newB);
405 outside->ReplacePred(header, newB);
406 header->Clear();
407 GetGraph()->EraseBlock(header);
408 LOG_ARRAYMOVE(DEBUG) << "Replaced loop " << loop_.GetId();
409
410 return true;
411 }
412
GetGraph()413 Graph *GetGraph()
414 {
415 return loop_.GetHeader()->GetGraph();
416 }
417
418 private:
419 template <typename T>
420 struct ArrayAccessDescr {
421 T *inst {};
422 Inst *idxOffset {};
423 bool idxOffsetNegate {false};
424 };
425
426 ArrayAccessDescr<LoadInst> load_;
427 ArrayAccessDescr<StoreInst> store_;
428 };
429
TryTransformArrayMoveIdiom(Loop * loop)430 bool LoopIdioms::TryTransformArrayMoveIdiom(Loop *loop)
431 {
432 ASSERT(loop->GetInnerLoops().empty());
433 if (loop->GetBlocks().size() != 1) {
434 return false;
435 }
436
437 LOG_ARRAYMOVE(DEBUG) << "Check loop " << loop->GetId();
438 ArrayMoveParser arrayMoveParser(loop);
439 if (!arrayMoveParser.Parse()) {
440 return false;
441 }
442 LOG_ARRAYMOVE(DEBUG) << "Found in loop " << loop->GetId();
443
444 return arrayMoveParser.TryReplaceLoop();
445 }
446
TryTransformArrayInitIdiom(Loop * loop)447 bool LoopIdioms::TryTransformArrayInitIdiom(Loop *loop)
448 {
449 if (loop->GetBlocks().size() != 1) {
450 return false;
451 }
452 ASSERT(loop->GetInnerLoops().empty());
453
454 auto store = FindStoreForArrayInit(loop->GetHeader());
455 if (store == nullptr) {
456 return false;
457 }
458
459 auto loopInfoOpt = CountableLoopParser {*loop}.Parse();
460 if (!loopInfoOpt.has_value()) {
461 return false;
462 }
463 auto loopInfo = *loopInfoOpt;
464 if (!IsLoopContainsArrayInitIdiom(store, loop, loopInfo)) {
465 return false;
466 }
467 ASSERT(loopInfo.isInc);
468
469 MarkerHolder holder {GetGraph()};
470 Marker marker = holder.GetMarker();
471 store->SetMarker(marker);
472 loopInfo.update->SetMarker(marker);
473 loopInfo.index->SetMarker(marker);
474 loopInfo.ifImm->SetMarker(marker);
475 loopInfo.ifImm->GetInput(0).GetInst()->SetMarker(marker);
476
477 if (!CanReplaceLoop(loop, marker)) {
478 return false;
479 }
480
481 COMPILER_LOG(DEBUG, LOOP_TRANSFORM) << "Array init idiom found in loop: " << loop->GetId()
482 << "\n\tarray: " << *store->GetArray()
483 << "\n\tvalue: " << *store->GetStoredValue()
484 << "\n\tinitial index: " << *loopInfo.init << "\n\ttest: " << *loopInfo.test
485 << "\n\tupdate: " << *loopInfo.update << "\n\tstep: " << loopInfo.constStep
486 << "\n\tindex: " << *loopInfo.index;
487
488 bool alwaysJump = false;
489 if (loopInfo.init->IsConst() && loopInfo.test->IsConst()) {
490 auto iterations =
491 loopInfo.test->CastToConstant()->GetIntValue() - loopInfo.init->CastToConstant()->GetIntValue();
492 if (iterations <= ITERATIONS_THRESHOLD) {
493 COMPILER_LOG(DEBUG, LOOP_TRANSFORM)
494 << "Loop will have " << iterations << " iterations, so intrinsics will not be generated";
495 return false;
496 }
497 alwaysJump = true;
498 }
499
500 return ReplaceArrayInitLoop(loop, &loopInfo, store, alwaysJump);
501 }
502
CreateArrayInitIntrinsic(StoreInst * store,CountableLoopInfo * info)503 Inst *LoopIdioms::CreateArrayInitIntrinsic(StoreInst *store, CountableLoopInfo *info)
504 {
505 auto type = store->GetType();
506 RuntimeInterface::IntrinsicId intrinsicId;
507 switch (type) {
508 case DataType::BOOL:
509 case DataType::INT8:
510 case DataType::UINT8:
511 intrinsicId = RuntimeInterface::IntrinsicId::LIB_CALL_MEMSET_8;
512 break;
513 case DataType::INT16:
514 case DataType::UINT16:
515 intrinsicId = RuntimeInterface::IntrinsicId::LIB_CALL_MEMSET_16;
516 break;
517 case DataType::INT32:
518 case DataType::UINT32:
519 intrinsicId = RuntimeInterface::IntrinsicId::LIB_CALL_MEMSET_32;
520 break;
521 case DataType::INT64:
522 case DataType::UINT64:
523 intrinsicId = RuntimeInterface::IntrinsicId::LIB_CALL_MEMSET_64;
524 break;
525 case DataType::FLOAT32:
526 intrinsicId = RuntimeInterface::IntrinsicId::LIB_CALL_MEMSET_F32;
527 break;
528 case DataType::FLOAT64:
529 intrinsicId = RuntimeInterface::IntrinsicId::LIB_CALL_MEMSET_F64;
530 break;
531 default:
532 return nullptr;
533 }
534
535 auto fillArray = GetGraph()->CreateInstIntrinsic(DataType::VOID, store->GetPc(), intrinsicId);
536 fillArray->ClearFlag(inst_flags::Flags::REQUIRE_STATE);
537 fillArray->ClearFlag(inst_flags::Flags::RUNTIME_CALL);
538 fillArray->ClearFlag(inst_flags::Flags::CAN_THROW);
539 fillArray->SetInputs(GetGraph()->GetAllocator(), {{store->GetArray(), DataType::REFERENCE},
540 {store->GetStoredValue(), type},
541 {info->init, DataType::INT32},
542 {info->test, DataType::INT32}});
543 return fillArray;
544 }
545
ReplaceArrayInitLoop(Loop * loop,CountableLoopInfo * loopInfo,StoreInst * store,bool alwaysJump)546 bool LoopIdioms::ReplaceArrayInitLoop(Loop *loop, CountableLoopInfo *loopInfo, StoreInst *store, bool alwaysJump)
547 {
548 auto inst = CreateArrayInitIntrinsic(store, loopInfo);
549 if (inst == nullptr) {
550 return false;
551 }
552 auto header = loop->GetHeader();
553 auto preHeader = loop->GetPreHeader();
554
555 auto loopSucc = header->GetSuccessor(0) == header ? header->GetSuccessor(1) : header->GetSuccessor(0);
556 if (alwaysJump) {
557 ASSERT(loop->GetBlocks().size() == 1);
558 // insert block before disconnecting header to properly handle Phi in loop_succ
559 auto block = header->InsertNewBlockToSuccEdge(loopSucc);
560 preHeader->ReplaceSucc(header, block, true);
561 GetGraph()->DisconnectBlock(header, false, false);
562 block->AppendInst(inst);
563
564 COMPILER_LOG(INFO, LOOP_TRANSFORM) << "Replaced loop " << loop->GetId() << " with the instruction " << *inst
565 << " inserted into the new block " << block->GetId();
566 } else {
567 auto guardBlock = preHeader->InsertNewBlockToSuccEdge(header);
568 auto sub = GetGraph()->CreateInstSub(DataType::INT32, inst->GetPc(), loopInfo->test, loopInfo->init);
569 auto cmp = GetGraph()->CreateInstCompare(DataType::BOOL, inst->GetPc(), sub,
570 GetGraph()->FindOrCreateConstant(ITERATIONS_THRESHOLD),
571 DataType::INT32, ConditionCode::CC_LE);
572 auto ifImm =
573 GetGraph()->CreateInstIfImm(DataType::NO_TYPE, inst->GetPc(), cmp, 0, DataType::BOOL, ConditionCode::CC_NE);
574 guardBlock->AppendInst(sub);
575 guardBlock->AppendInst(cmp);
576 guardBlock->AppendInst(ifImm);
577
578 auto mergeBlock = header->InsertNewBlockToSuccEdge(loopSucc);
579 auto intrinsicBlock = GetGraph()->CreateEmptyBlock();
580
581 guardBlock->AddSucc(intrinsicBlock);
582 intrinsicBlock->AddSucc(mergeBlock);
583 intrinsicBlock->AppendInst(inst);
584
585 COMPILER_LOG(INFO, LOOP_TRANSFORM) << "Inserted conditional jump into intinsic " << *inst << " before loop "
586 << loop->GetId() << ", inserted blocks: " << intrinsicBlock->GetId() << ", "
587 << guardBlock->GetId() << ", " << mergeBlock->GetId();
588 }
589 return true;
590 }
591
592 } // namespace ark::compiler
593