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 auto users = inst->GetUsers();
59 auto it = std::find_if(users.begin(), users.end(),
60 [loop](auto &user) { return user.GetInst()->GetBasicBlock()->GetLoop() != loop; });
61 if (it != users.end()) {
62 return nullptr;
63 }
64 }
65 }
66 // Check that loop is finite.
67 // We can remove only loops that is always finite.
68 if (!CountableLoopParser(*loop).Parse().has_value()) {
69 return nullptr;
70 }
71 return outsideSucc;
72 }
73
DeleteLoop(Loop * loop,BasicBlock * outsideSucc) const74 void RedundantLoopElimination::DeleteLoop(Loop *loop, BasicBlock *outsideSucc) const
75 {
76 auto header = loop->GetHeader();
77 auto preHeader = loop->GetPreHeader();
78 ASSERT(loop->GetBackEdges().size() == 1);
79 ASSERT(preHeader != nullptr);
80
81 preHeader->ReplaceSucc(header, outsideSucc, true);
82 ASSERT(outsideSucc->GetPredsBlocks().back() == preHeader);
83 // replace loop_exit_ by pre_header in pred_blocks of outside_succ
84 // (important when outside_succ has Phi instructions)
85 outsideSucc->RemovePred(loopExit_);
86 // prevent trying to remove loop_exit_ from outside_succ preds again in DisconnectBlock
87 loopExit_->RemoveSucc(outsideSucc);
88
89 for (auto block : loop->GetBlocks()) {
90 GetGraph()->DisconnectBlock(block, false, false);
91 }
92 }
93
TransformLoop(Loop * loop)94 bool RedundantLoopElimination::TransformLoop(Loop *loop)
95 {
96 COMPILER_LOG(DEBUG, RLE_OPT) << "Visit loop with id = " << loop->GetId();
97 auto outsideSucc = IsRedundant(loop);
98 if (outsideSucc != nullptr) {
99 DeleteLoop(loop, outsideSucc);
100 isApplied_ = true;
101 COMPILER_LOG(DEBUG, RLE_OPT) << "Loop with id = " << loop->GetId() << " is removed";
102 GetGraph()->GetEventWriter().EventRedundantLoopElimination(loop->GetId(), loop->GetHeader()->GetGuestPc());
103 return true;
104 }
105 return false;
106 }
107
InvalidateAnalyses()108 void RedundantLoopElimination::InvalidateAnalyses()
109 {
110 GetGraph()->InvalidateAnalysis<BoundsAnalysis>();
111 GetGraph()->InvalidateAnalysis<AliasAnalysis>();
112 GetGraph()->InvalidateAnalysis<DominatorsTree>();
113 GetGraph()->InvalidateAnalysis<LoopAnalyzer>();
114 InvalidateBlocksOrderAnalyzes(GetGraph());
115 }
116 } // namespace ark::compiler
117