1 /*
2 * Copyright (c) 2021-2023 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 (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 if (outsideSucc == nullptr) {
44 outsideSucc = succ;
45 loopExit_ = block;
46 } else {
47 return nullptr;
48 }
49 }
50 }
51 // check that loop doesn't contains not redundant insts
52 for (auto inst : block->AllInsts()) {
53 if (inst->IsNotRemovable() && inst->GetOpcode() != Opcode::IfImm &&
54 inst->GetOpcode() != Opcode::SafePoint) {
55 return nullptr;
56 }
57 for (auto &user : inst->GetUsers()) {
58 if (user.GetInst()->GetBasicBlock()->GetLoop() != loop) {
59 return nullptr;
60 }
61 }
62 }
63 }
64 // Check that loop is finite.
65 // We can remove only loops that is always finite.
66 if (!CountableLoopParser(*loop).Parse().has_value()) {
67 return nullptr;
68 }
69 return outsideSucc;
70 }
71
DeleteLoop(Loop * loop,BasicBlock * outsideSucc) const72 void RedundantLoopElimination::DeleteLoop(Loop *loop, BasicBlock *outsideSucc) const
73 {
74 auto header = loop->GetHeader();
75 auto preHeader = loop->GetPreHeader();
76 ASSERT(loop->GetBackEdges().size() == 1);
77 ASSERT(preHeader != nullptr);
78
79 preHeader->ReplaceSucc(header, outsideSucc, true);
80 ASSERT(outsideSucc->GetPredsBlocks().back() == preHeader);
81 // replace loop_exit_ by pre_header in pred_blocks of outside_succ
82 // (important when outside_succ has Phi instructions)
83 outsideSucc->RemovePred(loopExit_);
84 // prevent trying to remove loop_exit_ from outside_succ preds again in DisconnectBlock
85 loopExit_->RemoveSucc(outsideSucc);
86
87 for (auto block : loop->GetBlocks()) {
88 GetGraph()->DisconnectBlock(block, false, false);
89 }
90 }
91
TransformLoop(Loop * loop)92 bool RedundantLoopElimination::TransformLoop(Loop *loop)
93 {
94 COMPILER_LOG(DEBUG, RLE_OPT) << "Visit loop with id = " << loop->GetId();
95 auto outsideSucc = IsRedundant(loop);
96 if (outsideSucc != nullptr) {
97 DeleteLoop(loop, outsideSucc);
98 isApplied_ = true;
99 COMPILER_LOG(DEBUG, RLE_OPT) << "Loop with id = " << loop->GetId() << " is removed";
100 GetGraph()->GetEventWriter().EventRedundantLoopElimination(loop->GetId(), loop->GetHeader()->GetGuestPc());
101 return true;
102 }
103 return false;
104 }
105
InvalidateAnalyses()106 void RedundantLoopElimination::InvalidateAnalyses()
107 {
108 GetGraph()->InvalidateAnalysis<BoundsAnalysis>();
109 GetGraph()->InvalidateAnalysis<AliasAnalysis>();
110 GetGraph()->InvalidateAnalysis<DominatorsTree>();
111 GetGraph()->InvalidateAnalysis<LoopAnalyzer>();
112 InvalidateBlocksOrderAnalyzes(GetGraph());
113 }
114 } // namespace panda::compiler
115