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 "deoptimize_elimination.h"
18 #include "optimizer/analysis/alias_analysis.h"
19 #include "optimizer/analysis/dominators_tree.h"
20 #include "optimizer/ir/analysis.h"
21
22 namespace ark::compiler {
23
RunImpl()24 bool DeoptimizeElimination::RunImpl()
25 {
26 GetGraph()->RunPass<LoopAnalyzer>();
27
28 VisitGraph();
29
30 ReplaceDeoptimizeIfByUnconditionalDeoptimize();
31
32 if (IsLoopDeleted() && GetGraph()->IsOsrMode()) {
33 CleanupGraphSaveStateOSR(GetGraph());
34 }
35 return IsApplied();
36 }
37
ReplaceDeoptimizeIfByUnconditionalDeoptimize()38 void DeoptimizeElimination::ReplaceDeoptimizeIfByUnconditionalDeoptimize()
39 {
40 for (auto &inst : deoptimizeMustThrow_) {
41 auto block = inst->GetBasicBlock();
42 if (block != nullptr) {
43 block->ReplaceInstByDeoptimize(inst);
44 SetApplied();
45 SetLoopDeleted();
46 }
47 }
48 }
49
VisitDeoptimizeIf(GraphVisitor * v,Inst * inst)50 void DeoptimizeElimination::VisitDeoptimizeIf(GraphVisitor *v, Inst *inst)
51 {
52 auto input = inst->GetInput(0).GetInst();
53 auto block = inst->GetBasicBlock();
54 auto graph = block->GetGraph();
55 auto visitor = static_cast<DeoptimizeElimination *>(v);
56 if (input->IsConst()) {
57 if (input->CastToConstant()->GetIntValue() == 0) {
58 visitor->RemoveDeoptimizeIf(inst);
59 } else {
60 visitor->PushNewDeoptimizeIf(inst);
61 }
62 } else if (input->GetOpcode() == Opcode::IsMustDeoptimize) {
63 if (visitor->CanRemoveGuard(input)) {
64 visitor->RemoveGuard(input);
65 }
66 } else {
67 for (auto &user : input->GetUsers()) {
68 auto userInst = user.GetInst();
69 if (userInst != inst && userInst->GetOpcode() == Opcode::DeoptimizeIf &&
70 !(graph->IsOsrMode() && block->GetLoop() != userInst->GetBasicBlock()->GetLoop()) &&
71 inst->InSameBlockOrDominate(userInst)) {
72 ASSERT(inst->IsDominate(userInst));
73 visitor->RemoveDeoptimizeIf(userInst);
74 }
75 }
76 }
77 }
78
CanRemoveGuard(Inst * guard)79 bool DeoptimizeElimination::CanRemoveGuard(Inst *guard)
80 {
81 auto guardBlock = guard->GetBasicBlock();
82 auto it = InstSafeIterator<IterationType::INST, IterationDirection::BACKWARD>(*guardBlock, guard);
83 for (++it; it != guardBlock->InstsSafeReverse().end(); ++it) {
84 auto inst = *it;
85 if (inst->IsRuntimeCall()) {
86 return false;
87 }
88 if (inst->GetOpcode() == Opcode::IsMustDeoptimize) {
89 return true;
90 }
91 }
92 auto mrk = guardBlock->GetGraph()->NewMarker();
93 auto removeMrk = guardBlock->GetGraph()->NewMarker();
94
95 /*
96 * Run search recursively from current block to start block.
97 * We can remove guard, if guard is met in all ways and there should be no call instructions between current
98 * guard and found guards.
99 */
100 bool canRemove = true;
101 for (auto succBlock : guardBlock->GetPredsBlocks()) {
102 canRemove &= CanRemoveGuardRec(succBlock, guard, mrk, removeMrk);
103 if (!canRemove) {
104 break;
105 }
106 }
107 guardBlock->GetGraph()->EraseMarker(mrk);
108 guardBlock->GetGraph()->EraseMarker(removeMrk);
109 return canRemove;
110 }
111
CanRemoveGuardRec(BasicBlock * block,Inst * guard,const Marker & mrk,const Marker & removeMrk)112 bool DeoptimizeElimination::CanRemoveGuardRec(BasicBlock *block, Inst *guard, const Marker &mrk,
113 const Marker &removeMrk)
114 {
115 if (block->IsStartBlock()) {
116 return false;
117 }
118 auto blockType = GetBlockType(block);
119 if (block->SetMarker(mrk)) {
120 return block->IsMarked(removeMrk);
121 }
122 if (blockType == BlockType::INVALID) {
123 for (auto inst : block->InstsSafeReverse()) {
124 if (inst->IsRuntimeCall()) {
125 PushNewBlockType(block, BlockType::RUNTIME_CALL);
126 return false;
127 }
128 if (inst->GetOpcode() == Opcode::IsMustDeoptimize) {
129 [[maybe_unused]] auto result = block->SetMarker(removeMrk);
130 ASSERT(!result);
131 PushNewBlockType(block, BlockType::GUARD);
132 return true;
133 }
134 }
135 PushNewBlockType(block, BlockType::NOTHING);
136 } else if (blockType != BlockType::NOTHING) {
137 if (blockType == BlockType::GUARD) {
138 [[maybe_unused]] auto result = block->SetMarker(removeMrk);
139 ASSERT(!result);
140 return true;
141 }
142 return false;
143 }
144 for (const auto &succBlock : block->GetPredsBlocks()) {
145 if (!CanRemoveGuardRec(succBlock, guard, mrk, removeMrk)) {
146 return false;
147 }
148 }
149 [[maybe_unused]] auto result = block->SetMarker(removeMrk);
150 ASSERT(!result);
151 return true;
152 }
153
RemoveGuard(Inst * guard)154 void DeoptimizeElimination::RemoveGuard(Inst *guard)
155 {
156 ASSERT(guard->GetOpcode() == Opcode::IsMustDeoptimize);
157 ASSERT(guard->HasSingleUser());
158
159 auto deopt = guard->GetNext();
160 ASSERT(deopt->GetOpcode() == Opcode::DeoptimizeIf);
161 auto block = guard->GetBasicBlock();
162 auto graph = block->GetGraph();
163 guard->RemoveInputs();
164 block->ReplaceInst(guard, graph->CreateInstNOP());
165
166 COMPILER_LOG(DEBUG, DEOPTIMIZE_ELIM) << "Dublicated Guard " << guard->GetId() << " is deleted";
167 graph->GetEventWriter().EventDeoptimizeElimination(GetOpcodeString(guard->GetOpcode()), guard->GetId(),
168 guard->GetPc());
169 RemoveDeoptimizeIf(deopt);
170 }
171
RemoveDeoptimizeIf(Inst * inst)172 void DeoptimizeElimination::RemoveDeoptimizeIf(Inst *inst)
173 {
174 auto block = inst->GetBasicBlock();
175 auto graph = block->GetGraph();
176 auto savestate = inst->GetInput(1).GetInst();
177
178 inst->RemoveInputs();
179 block->ReplaceInst(inst, graph->CreateInstNOP());
180
181 COMPILER_LOG(DEBUG, DEOPTIMIZE_ELIM) << "Dublicated or redundant DeoptimizeIf " << inst->GetId() << " is deleted";
182 graph->GetEventWriter().EventDeoptimizeElimination(GetOpcodeString(inst->GetOpcode()), inst->GetId(),
183 inst->GetPc());
184
185 if (savestate->GetUsers().Empty()) {
186 savestate->GetBasicBlock()->ReplaceInst(savestate, graph->CreateInstNOP());
187 savestate->RemoveInputs();
188
189 COMPILER_LOG(DEBUG, DEOPTIMIZE_ELIM) << "SaveState " << savestate->GetId() << " without users is deleted";
190 graph->GetEventWriter().EventDeoptimizeElimination(GetOpcodeString(savestate->GetOpcode()), savestate->GetId(),
191 savestate->GetPc());
192 }
193 SetApplied();
194 }
195
InvalidateAnalyses()196 void DeoptimizeElimination::InvalidateAnalyses()
197 {
198 // Before in "CleanupGraphSaveStateOSR" already run "LoopAnalyzer"
199 // in case (IsLoopDeleted() && GetGraph()->IsOsrMode())
200 if (!(IsLoopDeleted() && GetGraph()->IsOsrMode())) {
201 GetGraph()->InvalidateAnalysis<LoopAnalyzer>();
202 }
203 GetGraph()->InvalidateAnalysis<DominatorsTree>();
204 GetGraph()->InvalidateAnalysis<BoundsAnalysis>();
205 GetGraph()->InvalidateAnalysis<AliasAnalysis>();
206 }
207 } // namespace ark::compiler
208