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 "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 panda::compiler {
RunImpl()25 bool RedundantLoopElimination::RunImpl()
26 {
27 COMPILER_LOG(DEBUG, RLE_OPT) << "Run " << GetPassName();
28 RunLoopsVisitor();
29
30 if (is_applied_) {
31 COMPILER_LOG(DEBUG, RLE_OPT) << GetPassName() << " is applied";
32 }
33 return is_applied_;
34 }
35
IsRedundant(Loop * loop) const36 BasicBlock *RedundantLoopElimination::IsRedundant(Loop *loop) const
37 {
38 BasicBlock *outside_succ = 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 if (outside_succ == nullptr) {
44 outside_succ = succ;
45 } else {
46 return nullptr;
47 }
48 }
49 }
50 // check that loop doesn't contains not redundant insts
51 for (auto inst : block->AllInsts()) {
52 if (inst->IsNotRemovable() && inst->GetOpcode() != Opcode::IfImm &&
53 inst->GetOpcode() != Opcode::SafePoint) {
54 return nullptr;
55 }
56 for (auto &user : inst->GetUsers()) {
57 if (user.GetInst()->GetBasicBlock()->GetLoop() != loop) {
58 return nullptr;
59 }
60 }
61 }
62 }
63 // Check that loop is finite.
64 // We can remove only loops that is always finite.
65 if (!CountableLoopParser(*loop).Parse().has_value()) {
66 return nullptr;
67 }
68 return outside_succ;
69 }
70
DeleteLoop(Loop * loop,BasicBlock * outside_succ) const71 void RedundantLoopElimination::DeleteLoop(Loop *loop, BasicBlock *outside_succ) const
72 {
73 auto header = loop->GetHeader();
74 auto pre_header = loop->GetPreHeader();
75 ASSERT(loop->GetBackEdges().size() == 1);
76 ASSERT(pre_header != nullptr);
77
78 pre_header->ReplaceSucc(header, outside_succ, true);
79 for (auto block : loop->GetBlocks()) {
80 GetGraph()->DisconnectBlock(block, false, false);
81 }
82 }
83
TransformLoop(Loop * loop)84 bool RedundantLoopElimination::TransformLoop(Loop *loop)
85 {
86 COMPILER_LOG(DEBUG, RLE_OPT) << "Visit loop with id = " << loop->GetId();
87 auto outside_succ = IsRedundant(loop);
88 if (outside_succ != nullptr) {
89 DeleteLoop(loop, outside_succ);
90 is_applied_ = true;
91 COMPILER_LOG(DEBUG, RLE_OPT) << "Loop with id = " << loop->GetId() << " is removed";
92 GetGraph()->GetEventWriter().EventRedundantLoopElimination(loop->GetId(), loop->GetHeader()->GetGuestPc());
93 return true;
94 }
95 return false;
96 }
97
InvalidateAnalyses()98 void RedundantLoopElimination::InvalidateAnalyses()
99 {
100 GetGraph()->InvalidateAnalysis<BoundsAnalysis>();
101 GetGraph()->InvalidateAnalysis<AliasAnalysis>();
102 GetGraph()->InvalidateAnalysis<DominatorsTree>();
103 GetGraph()->InvalidateAnalysis<LoopAnalyzer>();
104 InvalidateBlocksOrderAnalyzes(GetGraph());
105 }
106 } // namespace panda::compiler
107