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 "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 panda::compiler {
23
RunImpl()24 bool DeoptimizeElimination::RunImpl()
25 {
26 GetGraph()->RunPass<LoopAnalyzer>();
27
28 uint64_t instsNumber = VisitGraphAndCount();
29
30 ReplaceDeoptimizeIfByUnconditionalDeoptimize();
31
32 if (!HaveCalls() && instsNumber <= g_options.GetCompilerSafepointEliminationLimit()) {
33 RemoveSafePoints();
34 }
35 if (IsLoopDeleted() && GetGraph()->IsOsrMode()) {
36 CleanupGraphSaveStateOSR(GetGraph());
37 }
38 return IsApplied();
39 }
40
ReplaceDeoptimizeIfByUnconditionalDeoptimize()41 void DeoptimizeElimination::ReplaceDeoptimizeIfByUnconditionalDeoptimize()
42 {
43 for (auto &inst : deoptimizeMustThrow_) {
44 auto block = inst->GetBasicBlock();
45 if (block != nullptr) {
46 block->ReplaceInstByDeoptimize(inst);
47 SetApplied();
48 SetLoopDeleted();
49 }
50 }
51 }
52
RemoveSafePoints()53 void DeoptimizeElimination::RemoveSafePoints()
54 {
55 auto block = GetGraph()->GetStartBlock();
56 ASSERT(block != nullptr && block->IsStartBlock());
57 for (auto sp : block->Insts()) {
58 if (sp->GetOpcode() == Opcode::SafePoint) {
59 sp->ClearFlag(inst_flags::NO_DCE);
60 SetApplied();
61 COMPILER_LOG(DEBUG, DEOPTIMIZE_ELIM) << "SafePoint " << sp->GetId() << " is deleted from start block";
62 block->GetGraph()->GetEventWriter().EventDeoptimizeElimination(GetOpcodeString(sp->GetOpcode()),
63 sp->GetId(), sp->GetPc());
64 }
65 }
66 }
67
RequireRegMap(Inst * inst)68 bool DeoptimizeElimination::RequireRegMap(Inst *inst)
69 {
70 for (auto &user : inst->GetUsers()) {
71 auto userInst = user.GetInst();
72 if (userInst->RequireRegMap()) {
73 return true;
74 }
75 auto opcode = userInst->GetOpcode();
76 if (opcode == Opcode::CallStatic || opcode == Opcode::CallVirtual || opcode == Opcode::CallResolvedVirtual ||
77 opcode == Opcode::CallDynamic || opcode == Opcode::CallResolvedStatic) {
78 // Inlined method can contain Deoptimize or DeoptimizeIf
79 if (static_cast<CallInst *>(userInst)->IsInlined()) {
80 return true;
81 }
82 }
83 }
84 return false;
85 }
86
VisitDefault(Inst * inst)87 void DeoptimizeElimination::VisitDefault(Inst *inst)
88 {
89 if (inst->GetType() != DataType::REFERENCE) {
90 return;
91 }
92 for (auto &user : inst->GetUsers()) {
93 auto userInst = user.GetInst();
94 if (!userInst->IsSaveState()) {
95 return;
96 }
97 if (userInst->GetOpcode() == Opcode::SafePoint) {
98 if (g_options.IsCompilerSafePointsRequireRegMap()) {
99 return;
100 }
101 continue;
102 }
103 if (RequireRegMap(userInst)) {
104 return;
105 }
106 }
107
108 inst->RemoveUsers<true>();
109
110 SetApplied();
111 COMPILER_LOG(DEBUG, DEOPTIMIZE_ELIM) << "All users the instructions " << inst->GetId() << " are SaveStates";
112 inst->GetBasicBlock()->GetGraph()->GetEventWriter().EventDeoptimizeElimination(GetOpcodeString(inst->GetOpcode()),
113 inst->GetId(), inst->GetPc());
114 }
115
VisitSaveState(GraphVisitor * v,Inst * inst)116 void DeoptimizeElimination::VisitSaveState(GraphVisitor *v, Inst *inst)
117 {
118 auto visitor = static_cast<DeoptimizeElimination *>(v);
119 if (visitor->TryToRemoveRedundantSaveState(inst)) {
120 return;
121 }
122
123 if (visitor->RequireRegMap(inst)) {
124 return;
125 }
126
127 auto ss = inst->CastToSaveState();
128 if (ss->RemoveNumericInputs()) {
129 visitor->SetApplied();
130 COMPILER_LOG(DEBUG, DEOPTIMIZE_ELIM) << "SaveState " << ss->GetId() << " numeric inputs were deleted";
131 ss->GetBasicBlock()->GetGraph()->GetEventWriter().EventDeoptimizeElimination(GetOpcodeString(ss->GetOpcode()),
132 ss->GetId(), ss->GetPc());
133 #ifndef NDEBUG
134 ss->SetInputsWereDeleted();
135 #endif
136 }
137 }
138
VisitSaveStateDeoptimize(GraphVisitor * v,Inst * inst)139 void DeoptimizeElimination::VisitSaveStateDeoptimize(GraphVisitor *v, Inst *inst)
140 {
141 static_cast<DeoptimizeElimination *>(v)->TryToRemoveRedundantSaveState(inst);
142 }
143
VisitDeoptimizeIf(GraphVisitor * v,Inst * inst)144 void DeoptimizeElimination::VisitDeoptimizeIf(GraphVisitor *v, Inst *inst)
145 {
146 auto input = inst->GetInput(0).GetInst();
147 auto block = inst->GetBasicBlock();
148 auto graph = block->GetGraph();
149 auto visitor = static_cast<DeoptimizeElimination *>(v);
150 if (input->IsConst()) {
151 if (input->CastToConstant()->GetIntValue() == 0) {
152 visitor->RemoveDeoptimizeIf(inst);
153 } else {
154 visitor->PushNewDeoptimizeIf(inst);
155 }
156 } else if (input->GetOpcode() == Opcode::IsMustDeoptimize) {
157 if (visitor->CanRemoveGuard(input)) {
158 visitor->RemoveGuard(input);
159 }
160 } else {
161 for (auto &user : input->GetUsers()) {
162 auto userInst = user.GetInst();
163 if (userInst != inst && userInst->GetOpcode() == Opcode::DeoptimizeIf &&
164 !(graph->IsOsrMode() && block->GetLoop() != userInst->GetBasicBlock()->GetLoop()) &&
165 inst->InSameBlockOrDominate(userInst)) {
166 ASSERT(inst->IsDominate(userInst));
167 visitor->RemoveDeoptimizeIf(userInst);
168 }
169 }
170 }
171 }
172
TryToRemoveRedundantSaveState(Inst * inst)173 bool DeoptimizeElimination::TryToRemoveRedundantSaveState(Inst *inst)
174 {
175 if (inst->GetUsers().Empty()) {
176 auto block = inst->GetBasicBlock();
177 block->ReplaceInst(inst, block->GetGraph()->CreateInstNOP());
178 inst->RemoveInputs();
179 SetApplied();
180 COMPILER_LOG(DEBUG, DEOPTIMIZE_ELIM) << "SaveState " << inst->GetId() << " without users is deleted";
181 block->GetGraph()->GetEventWriter().EventDeoptimizeElimination(GetOpcodeString(inst->GetOpcode()),
182 inst->GetId(), inst->GetPc());
183 return true;
184 }
185 return false;
186 }
187
CanRemoveGuard(Inst * guard)188 bool DeoptimizeElimination::CanRemoveGuard(Inst *guard)
189 {
190 auto guardBlock = guard->GetBasicBlock();
191 auto it = InstSafeIterator<IterationType::INST, IterationDirection::BACKWARD>(*guardBlock, guard);
192 for (++it; it != guardBlock->InstsSafeReverse().end(); ++it) {
193 auto inst = *it;
194 if (inst->IsRuntimeCall()) {
195 return false;
196 }
197 if (inst->GetOpcode() == Opcode::IsMustDeoptimize) {
198 return true;
199 }
200 }
201 auto mrk = guardBlock->GetGraph()->NewMarker();
202 auto removeMrk = guardBlock->GetGraph()->NewMarker();
203
204 /*
205 * Run search recursively from current block to start block.
206 * We can remove guard, if guard is met in all ways and there should be no call instructions between current
207 * guard and found guards.
208 */
209 bool canRemove = true;
210 for (auto succBlock : guardBlock->GetPredsBlocks()) {
211 canRemove &= CanRemoveGuardRec(succBlock, guard, mrk, removeMrk);
212 if (!canRemove) {
213 break;
214 }
215 }
216 guardBlock->GetGraph()->EraseMarker(mrk);
217 guardBlock->GetGraph()->EraseMarker(removeMrk);
218 return canRemove;
219 }
220
CanRemoveGuardRec(BasicBlock * block,Inst * guard,const Marker & mrk,const Marker & removeMrk)221 bool DeoptimizeElimination::CanRemoveGuardRec(BasicBlock *block, Inst *guard, const Marker &mrk,
222 const Marker &removeMrk)
223 {
224 if (block->IsStartBlock()) {
225 return false;
226 }
227 auto blockType = GetBlockType(block);
228 if (block->SetMarker(mrk)) {
229 return block->IsMarked(removeMrk);
230 }
231 if (blockType == BlockType::INVALID) {
232 for (auto inst : block->InstsSafeReverse()) {
233 if (inst->IsRuntimeCall()) {
234 PushNewBlockType(block, BlockType::RUNTIME_CALL);
235 return false;
236 }
237 if (inst->GetOpcode() == Opcode::IsMustDeoptimize) {
238 [[maybe_unused]] auto result = block->SetMarker(removeMrk);
239 ASSERT(!result);
240 PushNewBlockType(block, BlockType::GUARD);
241 return true;
242 }
243 }
244 PushNewBlockType(block, BlockType::NOTHING);
245 } else if (blockType != BlockType::NOTHING) {
246 if (blockType == BlockType::GUARD) {
247 [[maybe_unused]] auto result = block->SetMarker(removeMrk);
248 ASSERT(!result);
249 return true;
250 }
251 return false;
252 }
253 for (const auto &succBlock : block->GetPredsBlocks()) {
254 if (!CanRemoveGuardRec(succBlock, guard, mrk, removeMrk)) {
255 return false;
256 }
257 }
258 [[maybe_unused]] auto result = block->SetMarker(removeMrk);
259 ASSERT(!result);
260 return true;
261 }
262
RemoveGuard(Inst * guard)263 void DeoptimizeElimination::RemoveGuard(Inst *guard)
264 {
265 ASSERT(guard->GetOpcode() == Opcode::IsMustDeoptimize);
266 ASSERT(guard->HasSingleUser());
267
268 auto deopt = guard->GetNext();
269 ASSERT(deopt->GetOpcode() == Opcode::DeoptimizeIf);
270 auto block = guard->GetBasicBlock();
271 auto graph = block->GetGraph();
272 guard->RemoveInputs();
273 block->ReplaceInst(guard, graph->CreateInstNOP());
274
275 COMPILER_LOG(DEBUG, DEOPTIMIZE_ELIM) << "Dublicated Guard " << guard->GetId() << " is deleted";
276 graph->GetEventWriter().EventDeoptimizeElimination(GetOpcodeString(guard->GetOpcode()), guard->GetId(),
277 guard->GetPc());
278 RemoveDeoptimizeIf(deopt);
279 }
280
RemoveDeoptimizeIf(Inst * inst)281 void DeoptimizeElimination::RemoveDeoptimizeIf(Inst *inst)
282 {
283 auto block = inst->GetBasicBlock();
284 auto graph = block->GetGraph();
285 auto savestate = inst->GetInput(1).GetInst();
286
287 inst->RemoveInputs();
288 block->ReplaceInst(inst, graph->CreateInstNOP());
289
290 COMPILER_LOG(DEBUG, DEOPTIMIZE_ELIM) << "Dublicated or redundant DeoptimizeIf " << inst->GetId() << " is deleted";
291 graph->GetEventWriter().EventDeoptimizeElimination(GetOpcodeString(inst->GetOpcode()), inst->GetId(),
292 inst->GetPc());
293
294 if (savestate->GetUsers().Empty()) {
295 savestate->GetBasicBlock()->ReplaceInst(savestate, graph->CreateInstNOP());
296 savestate->RemoveInputs();
297
298 COMPILER_LOG(DEBUG, DEOPTIMIZE_ELIM) << "SaveState " << savestate->GetId() << " without users is deleted";
299 graph->GetEventWriter().EventDeoptimizeElimination(GetOpcodeString(savestate->GetOpcode()), savestate->GetId(),
300 savestate->GetPc());
301 }
302 SetApplied();
303 }
304
InvalidateAnalyses()305 void DeoptimizeElimination::InvalidateAnalyses()
306 {
307 // Before in "CleanupGraphSaveStateOSR" already run "LoopAnalyzer"
308 // in case (IsLoopDeleted() && GetGraph()->IsOsrMode())
309 if (!(IsLoopDeleted() && GetGraph()->IsOsrMode())) {
310 GetGraph()->InvalidateAnalysis<LoopAnalyzer>();
311 }
312 GetGraph()->InvalidateAnalysis<DominatorsTree>();
313 GetGraph()->InvalidateAnalysis<BoundsAnalysis>();
314 GetGraph()->InvalidateAnalysis<AliasAnalysis>();
315 }
316 } // namespace panda::compiler
317