1 /*
2 * Copyright (c) 2021-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/bounds_analysis.h"
19 #include "optimizer/analysis/countable_loop_parser.h"
20 #include "optimizer/analysis/dominators_tree.h"
21 #include "redundant_loop_elimination.h"
22
23 #include "optimizer/ir/basicblock.h"
24 namespace ark::compiler {
RunImpl()25 bool RedundantLoopElimination::RunImpl()
26 {
27 COMPILER_LOG(DEBUG, RLE_OPT) << "Run " << GetPassName();
28 RunLoopsVisitor();
29
30 if (isApplied_) {
31 COMPILER_LOG(DEBUG, RLE_OPT) << GetPassName() << " is applied";
32 }
33 return isApplied_;
34 }
35
IsRedundant(Loop * loop)36 BasicBlock *RedundantLoopElimination::IsRedundant(Loop *loop)
37 {
38 BasicBlock *outsideSucc = nullptr;
39 for (auto block : loop->GetBlocks()) {
40 // check that loop have only one exit and one outside blocks
41 for (auto succ : block->GetSuccsBlocks()) {
42 if (succ->GetLoop() == loop) {
43 continue;
44 }
45 if (outsideSucc == nullptr) {
46 outsideSucc = succ;
47 loopExit_ = block;
48 } else {
49 return nullptr;
50 }
51 }
52 // check that loop doesn't contains not redundant insts
53 for (auto inst : block->AllInsts()) {
54 if (inst->IsNotRemovable() && inst->GetOpcode() != Opcode::IfImm &&
55 inst->GetOpcode() != Opcode::SafePoint) {
56 return nullptr;
57 }
58 for (auto &user : inst->GetUsers()) {
59 if (user.GetInst()->GetBasicBlock()->GetLoop() != loop) {
60 return nullptr;
61 }
62 }
63 }
64 }
65 // Check that loop is finite.
66 // We can remove only loops that is always finite.
67 if (!CountableLoopParser(*loop).Parse().has_value()) {
68 return nullptr;
69 }
70 return outsideSucc;
71 }
72
DeleteLoop(Loop * loop,BasicBlock * outsideSucc) const73 void RedundantLoopElimination::DeleteLoop(Loop *loop, BasicBlock *outsideSucc) const
74 {
75 auto header = loop->GetHeader();
76 auto preHeader = loop->GetPreHeader();
77 ASSERT(loop->GetBackEdges().size() == 1);
78 ASSERT(preHeader != nullptr);
79
80 preHeader->ReplaceSucc(header, outsideSucc, true);
81 ASSERT(outsideSucc->GetPredsBlocks().back() == preHeader);
82 // replace loop_exit_ by pre_header in pred_blocks of outside_succ
83 // (important when outside_succ has Phi instructions)
84 outsideSucc->RemovePred(loopExit_);
85 // prevent trying to remove loop_exit_ from outside_succ preds again in DisconnectBlock
86 loopExit_->RemoveSucc(outsideSucc);
87
88 for (auto block : loop->GetBlocks()) {
89 GetGraph()->DisconnectBlock(block, false, false);
90 }
91 }
92
TransformLoop(Loop * loop)93 bool RedundantLoopElimination::TransformLoop(Loop *loop)
94 {
95 COMPILER_LOG(DEBUG, RLE_OPT) << "Visit loop with id = " << loop->GetId();
96 auto outsideSucc = IsRedundant(loop);
97 if (outsideSucc != nullptr) {
98 DeleteLoop(loop, outsideSucc);
99 isApplied_ = true;
100 COMPILER_LOG(DEBUG, RLE_OPT) << "Loop with id = " << loop->GetId() << " is removed";
101 GetGraph()->GetEventWriter().EventRedundantLoopElimination(loop->GetId(), loop->GetHeader()->GetGuestPc());
102 return true;
103 }
104 return false;
105 }
106
InvalidateAnalyses()107 void RedundantLoopElimination::InvalidateAnalyses()
108 {
109 GetGraph()->InvalidateAnalysis<BoundsAnalysis>();
110 GetGraph()->InvalidateAnalysis<AliasAnalysis>();
111 GetGraph()->InvalidateAnalysis<DominatorsTree>();
112 GetGraph()->InvalidateAnalysis<LoopAnalyzer>();
113 InvalidateBlocksOrderAnalyzes(GetGraph());
114 }
115 } // namespace ark::compiler
116