1 /**
2 * Copyright (c) 2023-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 "simplify_string_builder.h"
17
18 #include "compiler_logger.h"
19
20 #include "optimizer/analysis/alias_analysis.h"
21 #include "optimizer/analysis/bounds_analysis.h"
22 #include "optimizer/analysis/dominators_tree.h"
23 #include "optimizer/ir/analysis.h"
24 #include "optimizer/ir/basicblock.h"
25 #include "optimizer/ir/inst.h"
26
27 #include "optimizer/optimizations/cleanup.h"
28
29 namespace ark::compiler {
30
SimplifyStringBuilder(Graph * graph)31 SimplifyStringBuilder::SimplifyStringBuilder(Graph *graph)
32 : Optimization(graph),
33 instructionsStack_ {graph->GetLocalAllocator()->Adapter()},
34 instructionsVector_ {graph->GetLocalAllocator()->Adapter()},
35 inputDescriptors_ {graph->GetLocalAllocator()->Adapter()},
36 usages_ {graph->GetLocalAllocator()->Adapter()},
37 matches_ {graph->GetLocalAllocator()->Adapter()},
38 stringBuilderCalls_ {graph->GetLocalAllocator()->Adapter()},
39 stringBuilderFirstLastCalls_ {graph->GetLocalAllocator()->Adapter()}
40 {
41 }
42
HasTryCatchBlocks(Graph * graph)43 bool HasTryCatchBlocks(Graph *graph)
44 {
45 for (auto block : graph->GetBlocksRPO()) {
46 if (block->IsTryCatch()) {
47 return true;
48 }
49 }
50 return false;
51 }
52
RunImpl()53 bool SimplifyStringBuilder::RunImpl()
54 {
55 isApplied_ = false;
56
57 if (!GetGraph()->IsAnalysisValid<DominatorsTree>()) {
58 GetGraph()->RunPass<DominatorsTree>();
59 }
60
61 ASSERT(GetGraph()->GetRootLoop() != nullptr);
62
63 // Loops with try-catch block and OSR mode are not supported in current implementation
64 if (!HasTryCatchBlocks(GetGraph()) && !GetGraph()->IsOsrMode()) {
65 for (auto loop : GetGraph()->GetRootLoop()->GetInnerLoops()) {
66 OptimizeStringConcatenation(loop);
67 }
68 }
69
70 // Cleanup should be done before block optimizations, to erase instruction marked as dead
71 GetGraph()->RunPass<compiler::Cleanup>();
72
73 OptimizeStringBuilderChain();
74
75 // Cleanup should be done before block optimizations, to erase instruction marked as dead
76 GetGraph()->RunPass<compiler::Cleanup>();
77
78 for (auto block : GetGraph()->GetBlocksRPO()) {
79 if (block->IsEmpty()) {
80 continue;
81 }
82 OptimizeStringBuilderToString(block);
83 OptimizeStringConcatenation(block);
84 OptimizeStringBuilderAppendChain(block);
85 }
86
87 COMPILER_LOG(DEBUG, SIMPLIFY_SB) << "Simplify StringBuilder complete";
88
89 // Remove save state inserted in loop post exit block at IR builder
90 for (auto block : GetGraph()->GetBlocksRPO()) {
91 for (auto inst : block->Insts()) {
92 if (inst->GetOpcode() != Opcode::SaveState) {
93 continue;
94 }
95 inst->ClearFlag(inst_flags::NO_DCE);
96 }
97 }
98
99 // Cleanup should be done inside pass, to satisfy GraphChecker
100 GetGraph()->RunPass<compiler::Cleanup>();
101
102 return isApplied_;
103 }
104
InvalidateAnalyses()105 void SimplifyStringBuilder::InvalidateAnalyses()
106 {
107 GetGraph()->InvalidateAnalysis<BoundsAnalysis>();
108 GetGraph()->InvalidateAnalysis<AliasAnalysis>();
109 }
110
SkipToStringBuilderConstructorWithStringArg(InstIter begin,InstIter end)111 InstIter SimplifyStringBuilder::SkipToStringBuilderConstructorWithStringArg(InstIter begin, InstIter end)
112 {
113 return std::find_if(std::move(begin), std::move(end),
114 [](auto inst) { return IsMethodStringBuilderConstructorWithStringArg(inst); });
115 }
116
IsDataFlowInput(Inst * inst,Inst * input)117 bool IsDataFlowInput(Inst *inst, Inst *input)
118 {
119 for (size_t i = 0; i < inst->GetInputsCount(); ++i) {
120 if (inst->GetDataFlowInput(i) == input) {
121 return true;
122 }
123 }
124 return false;
125 }
126
OptimizeStringBuilderToString(BasicBlock * block)127 void SimplifyStringBuilder::OptimizeStringBuilderToString(BasicBlock *block)
128 {
129 // Removes unnecessary String Builder instances
130
131 ASSERT(block != nullptr);
132 ASSERT(block->GetGraph() == GetGraph());
133
134 // Walk through a basic block, find every StringBuilder instance and constructor call,
135 // and check it we can remove/replace them
136 InstIter inst = block->Insts().begin();
137 while ((inst = SkipToStringBuilderConstructorWithStringArg(inst, block->Insts().end())) != block->Insts().end()) {
138 ASSERT((*inst)->IsStaticCall());
139 auto ctorCall = (*inst)->CastToCallStatic();
140
141 // void StringBuilder::<ctor> instance, arg, save_state
142 ASSERT(ctorCall->GetInputsCount() == ARGS_NUM_3);
143 auto instance = ctorCall->GetInput(0).GetInst();
144 auto arg = ctorCall->GetInput(1).GetInst();
145
146 // Look for StringBuilder usages within current basic block
147 auto nextInst = block->Insts().end();
148 bool removeInstance = true;
149 for (++inst; inst != block->Insts().end(); ++inst) {
150 // Skip SaveState instructions
151 if ((*inst)->IsSaveState()) {
152 continue;
153 }
154
155 // Skip check instructions, like NullCheck, RefTypeCheck, etc.
156 if ((*inst)->IsCheck()) {
157 continue;
158 }
159
160 // Continue (outer loop) with the next StringBuilder constructor,
161 // in case we met one in inner loop
162 if (IsMethodStringBuilderConstructorWithStringArg(*inst)) {
163 nextInst = nextInst != block->Insts().end() ? nextInst : inst;
164 }
165
166 if (!IsDataFlowInput(*inst, instance)) {
167 continue;
168 }
169
170 // Process usages of StringBuilder instance:
171 // replace toString()-calls until we met something else
172 if (IsStringBuilderToString(*inst)) {
173 (*inst)->ReplaceUsers(arg);
174 (*inst)->ClearFlag(compiler::inst_flags::NO_DCE);
175 COMPILER_LOG(DEBUG, SIMPLIFY_SB)
176 << "Remove StringBuilder toString()-call (id=" << (*inst)->GetId() << ")";
177 isApplied_ = true;
178 } else {
179 removeInstance = false;
180 break;
181 }
182 }
183
184 // Remove StringBuilder instance unless it has usages
185 if (removeInstance && !IsUsedOutsideBasicBlock(instance, instance->GetBasicBlock())) {
186 RemoveStringBuilderInstance(instance);
187 isApplied_ = true;
188 }
189
190 // Proceed to the next StringBuilder constructor
191 inst = nextInst != block->Insts().end() ? nextInst : inst;
192 }
193 }
194
SkipToStringBuilderDefaultConstructor(InstIter begin,InstIter end)195 InstIter SimplifyStringBuilder::SkipToStringBuilderDefaultConstructor(InstIter begin, InstIter end)
196 {
197 return std::find_if(std::move(begin), std::move(end),
198 [](auto inst) { return IsMethodStringBuilderDefaultConstructor(inst); });
199 }
200
CreateConcatIntrinsic(const std::array<IntrinsicInst *,ARGS_NUM_4> & appendIntrinsics,size_t appendCount,DataType::Type type,SaveStateInst * saveState)201 IntrinsicInst *SimplifyStringBuilder::CreateConcatIntrinsic(
202 const std::array<IntrinsicInst *, ARGS_NUM_4> &appendIntrinsics, size_t appendCount, DataType::Type type,
203 SaveStateInst *saveState)
204 {
205 auto concatIntrinsic =
206 GetGraph()->CreateInstIntrinsic(GetGraph()->GetRuntime()->GetStringConcatStringsIntrinsicId(appendCount));
207 ASSERT(concatIntrinsic->RequireState());
208
209 concatIntrinsic->SetType(type);
210 // Allocate input types (+1 input for save state)
211 concatIntrinsic->AllocateInputTypes(GetGraph()->GetAllocator(), appendCount + 1);
212
213 for (size_t index = 0; index < appendCount; ++index) {
214 auto arg = appendIntrinsics[index]->GetInput(1).GetInst();
215 concatIntrinsic->AppendInput(arg);
216 concatIntrinsic->AddInputType(arg->GetType());
217 }
218
219 auto saveStateClone = CopySaveState(GetGraph(), saveState);
220 concatIntrinsic->AppendInput(saveStateClone);
221 concatIntrinsic->AddInputType(saveStateClone->GetType());
222
223 return concatIntrinsic;
224 }
225
CheckUnsupportedCases(Inst * instance)226 bool CheckUnsupportedCases(Inst *instance)
227 {
228 if (IsUsedOutsideBasicBlock(instance, instance->GetBasicBlock())) {
229 return false; // Unsupported case: doesn't look like concatenation pattern
230 }
231
232 auto toStringCount = CountUsers(instance, [](auto &user) { return IsStringBuilderToString(user.GetInst()); });
233 if (toStringCount != 1) {
234 return false; // Unsupported case: doesn't look like concatenation pattern
235 }
236
237 auto appendCount = CountUsers(instance, [](auto &user) { return IsStringBuilderAppend(user.GetInst()); });
238 auto appendStringCount =
239 CountUsers(instance, [](auto &user) { return IsIntrinsicStringBuilderAppendString(user.GetInst()); });
240 if (appendCount != appendStringCount) {
241 return false; // Unsupported case: arguments must be strings
242 }
243 if (appendCount <= 1 || appendCount > ARGS_NUM_4) {
244 return false; // Unsupported case: too many strings concatenated
245 }
246
247 return true;
248 }
249
MatchConcatenation(InstIter & begin,const InstIter & end,ConcatenationMatch & match)250 bool SimplifyStringBuilder::MatchConcatenation(InstIter &begin, const InstIter &end, ConcatenationMatch &match)
251 {
252 auto instance = match.instance;
253 if (!CheckUnsupportedCases(instance)) {
254 return false;
255 }
256
257 // Walk instruction range [begin, end) and fill the match structure with StringBuilder usage instructions found
258 for (; begin != end; ++begin) {
259 if ((*begin)->IsSaveState()) {
260 continue;
261 }
262
263 // Skip instruction having nothing to do with current instance
264 if (!IsDataFlowInput(*begin, instance)) {
265 continue;
266 }
267
268 // Walk through NullChecks
269 auto inst = *begin;
270 if (inst->IsNullCheck()) {
271 if (!inst->HasSingleUser()) {
272 return false; // Unsupported case: doesn't look like concatenation pattern
273 }
274 inst = inst->GetUsers().Front().GetInst();
275 if (inst->GetBasicBlock() != instance->GetBasicBlock()) {
276 return false; // Unsupported case: doesn't look like concatenation pattern
277 }
278 continue;
279 }
280
281 if (IsIntrinsicStringBuilderAppendString(inst)) {
282 auto intrinsic = inst->CastToIntrinsic();
283 match.appendIntrinsics[match.appendCount++] = intrinsic;
284 } else if (IsStringBuilderToString(inst)) {
285 match.toStringCall = *begin;
286 } else {
287 break;
288 }
289 }
290
291 for (size_t index = 0; index < match.appendCount; ++index) {
292 if (!match.appendIntrinsics[index]->IsDominate(match.toStringCall)) {
293 return false;
294 }
295 }
296
297 // Supported case: number of toString calls is one,
298 // number of append calls is between 2 and 4,
299 // toString call is dominated by all append calls.
300 return true;
301 }
302
FixBrokenSaveStates(Inst * source,Inst * target)303 void SimplifyStringBuilder::FixBrokenSaveStates(Inst *source, Inst *target)
304 {
305 if (source->IsMovableObject()) {
306 ssb_.SearchAndCreateMissingObjInSaveState(GetGraph(), source, target);
307 }
308 }
309
Check(const ConcatenationMatch & match)310 void SimplifyStringBuilder::Check(const ConcatenationMatch &match)
311 {
312 // NOLINTBEGIN(readability-magic-numbers)
313 [[maybe_unused]] auto &appendIntrinsics = match.appendIntrinsics;
314 ASSERT(match.appendCount > 1);
315 ASSERT(appendIntrinsics[0U] != nullptr);
316 ASSERT(appendIntrinsics[0U]->GetInputsCount() > 1);
317 ASSERT(appendIntrinsics[1U] != nullptr);
318 ASSERT(appendIntrinsics[1U]->GetInputsCount() > 1);
319
320 switch (match.appendCount) {
321 case ARGS_NUM_2:
322 break;
323 case ARGS_NUM_3: {
324 ASSERT(appendIntrinsics[2U] != nullptr);
325 ASSERT(appendIntrinsics[2U]->GetInputsCount() > 1);
326 break;
327 }
328 case ARGS_NUM_4: {
329 ASSERT(appendIntrinsics[2U] != nullptr);
330 ASSERT(appendIntrinsics[2U]->GetInputsCount() > 1);
331 ASSERT(appendIntrinsics[3U] != nullptr);
332 ASSERT(appendIntrinsics[3U]->GetInputsCount() > 1);
333 break;
334 }
335 default:
336 UNREACHABLE();
337 }
338 // NOLINTEND(readability-magic-numbers)
339 }
340
InsertIntrinsicAndFixSaveStates(IntrinsicInst * concatIntrinsic,const std::array<IntrinsicInst *,ARGS_NUM_4> & appendIntrinsics,size_t appendCount,Inst * before)341 void SimplifyStringBuilder::InsertIntrinsicAndFixSaveStates(
342 IntrinsicInst *concatIntrinsic, const std::array<IntrinsicInst *, ARGS_NUM_4> &appendIntrinsics, size_t appendCount,
343 Inst *before)
344 {
345 InsertBeforeWithSaveState(concatIntrinsic, before);
346 for (size_t index = 0; index < appendCount; ++index) {
347 auto arg = appendIntrinsics[index]->GetDataFlowInput(1);
348 FixBrokenSaveStates(arg, concatIntrinsic);
349 }
350 }
351
ReplaceWithConcatIntrinsic(const ConcatenationMatch & match)352 void SimplifyStringBuilder::ReplaceWithConcatIntrinsic(const ConcatenationMatch &match)
353 {
354 auto &appendIntrinsics = match.appendIntrinsics;
355 auto toStringCall = match.toStringCall;
356
357 auto concatIntrinsic = CreateConcatIntrinsic(appendIntrinsics, match.appendCount, toStringCall->GetType(),
358 toStringCall->GetSaveState());
359 InsertIntrinsicAndFixSaveStates(concatIntrinsic, appendIntrinsics, match.appendCount, toStringCall);
360 toStringCall->ReplaceUsers(concatIntrinsic);
361
362 COMPILER_LOG(DEBUG, SIMPLIFY_SB) << "Replace StringBuilder (id=" << match.ctorCall->GetId()
363 << ") append-intrinsics with concat intrinsic (id=" << concatIntrinsic->GetId()
364 << ")";
365 }
366
Cleanup(const ConcatenationMatch & match)367 void SimplifyStringBuilder::Cleanup(const ConcatenationMatch &match)
368 {
369 RemoveStringBuilderInstance(match.instance);
370 }
371
OptimizeStringConcatenation(BasicBlock * block)372 void SimplifyStringBuilder::OptimizeStringConcatenation(BasicBlock *block)
373 {
374 // Replace String Builder usage with string concatenation whenever optimal
375
376 ASSERT(block != nullptr);
377 ASSERT(block->GetGraph() == GetGraph());
378
379 MarkerHolder visitedMarker {GetGraph()};
380 Marker visited = visitedMarker.GetMarker();
381
382 bool isAppliedLocal;
383 do {
384 isAppliedLocal = false;
385
386 // Walk through a basic block, find every String concatenation pattern,
387 // and check if we can optimize them
388 InstIter inst = block->Insts().begin();
389 while ((inst = SkipToStringBuilderDefaultConstructor(inst, block->Insts().end())) != block->Insts().end()) {
390 ASSERT((*inst)->IsStaticCall());
391 auto ctorCall = (*inst)->CastToCallStatic();
392
393 ASSERT(ctorCall->GetInputsCount() > 0);
394 auto instance = ctorCall->GetInput(0).GetInst();
395
396 ++inst;
397 if (instance->IsMarked(visited)) {
398 continue;
399 }
400
401 ConcatenationMatch match {instance, ctorCall};
402 // Check if current StringBuilder instance can be optimized
403 if (MatchConcatenation(inst, block->Insts().end(), match)) {
404 Check(match);
405 ReplaceWithConcatIntrinsic(match);
406 Cleanup(match);
407
408 instance->SetMarker(visited);
409
410 isAppliedLocal = true;
411 isApplied_ = true;
412 }
413 }
414 } while (isAppliedLocal);
415 }
416
Clear()417 void SimplifyStringBuilder::ConcatenationLoopMatch::TemporaryInstructions::Clear()
418 {
419 intermediateValue = nullptr;
420 toStringCall = nullptr;
421 instance = nullptr;
422 ctorCall = nullptr;
423 appendAccValue = nullptr;
424 }
425
IsEmpty() const426 bool SimplifyStringBuilder::ConcatenationLoopMatch::TemporaryInstructions::IsEmpty() const
427 {
428 return toStringCall == nullptr || intermediateValue == nullptr || instance == nullptr || ctorCall == nullptr ||
429 appendAccValue == nullptr;
430 }
431
Clear()432 void SimplifyStringBuilder::ConcatenationLoopMatch::Clear()
433 {
434 block = nullptr;
435 accValue = nullptr;
436 initialValue = nullptr;
437
438 preheader.instance = nullptr;
439 preheader.ctorCall = nullptr;
440 preheader.appendAccValue = nullptr;
441
442 loop.appendInstructions.clear();
443 temp.clear();
444 exit.toStringCall = nullptr;
445 }
446
HasAppendUsersOnly(Inst * inst) const447 bool SimplifyStringBuilder::HasAppendUsersOnly(Inst *inst) const
448 {
449 MarkerHolder visited {inst->GetBasicBlock()->GetGraph()};
450 bool found = HasUserPhiRecursively(inst, visited.GetMarker(), [inst](auto &user) {
451 bool sameLoop = user.GetInst()->GetBasicBlock()->GetLoop() == inst->GetBasicBlock()->GetLoop();
452 bool isSaveState = user.GetInst()->IsSaveState();
453 bool isPhi = user.GetInst()->IsPhi();
454 bool isAppendInstruction = IsStringBuilderAppend(user.GetInst());
455 return sameLoop && !isSaveState && !isPhi && !isAppendInstruction;
456 });
457 ResetUserMarkersRecursively(inst, visited.GetMarker());
458 return !found;
459 }
460
IsCheckCastWithoutUsers(Inst * inst)461 bool IsCheckCastWithoutUsers(Inst *inst)
462 {
463 return inst->GetOpcode() == Opcode::CheckCast && !inst->HasUsers();
464 }
465
HasPhiOrAppendUsersOnly(Inst * inst,Marker appendInstructionVisited) const466 bool SimplifyStringBuilder::HasPhiOrAppendUsersOnly(Inst *inst, Marker appendInstructionVisited) const
467 {
468 MarkerHolder phiVisited {GetGraph()};
469 bool found = HasUserPhiRecursively(
470 inst, phiVisited.GetMarker(), [loop = inst->GetBasicBlock()->GetLoop(), appendInstructionVisited](auto &user) {
471 bool sameLoop = user.GetInst()->GetBasicBlock()->GetLoop() == loop;
472 bool isSaveState = user.GetInst()->IsSaveState();
473 bool isCheckCast = IsCheckCastWithoutUsers(user.GetInst());
474 bool isPhi = user.GetInst()->IsPhi();
475 bool isVisited = user.GetInst()->IsMarked(appendInstructionVisited);
476 bool isAppendInstruction = IsStringBuilderAppend(user.GetInst());
477 return sameLoop && !isSaveState && !isCheckCast && !isPhi && !(isAppendInstruction && isVisited);
478 });
479 return !found;
480 }
481
IsInstanceHoistable() const482 bool SimplifyStringBuilder::ConcatenationLoopMatch::IsInstanceHoistable() const
483 {
484 if (block == nullptr || accValue == nullptr || initialValue == nullptr) {
485 return false;
486 }
487
488 if (preheader.instance == nullptr || preheader.ctorCall == nullptr || preheader.appendAccValue == nullptr) {
489 return false;
490 }
491
492 if (block != preheader.instance->GetBasicBlock() || block != preheader.ctorCall->GetBasicBlock() ||
493 block != preheader.appendAccValue->GetBasicBlock()) {
494 return false;
495 }
496
497 if ((block->IsTry() || block->IsCatch()) && block->GetTryId() != block->GetLoop()->GetPreHeader()->GetTryId()) {
498 return false;
499 }
500
501 if (loop.appendInstructions.empty()) {
502 return false;
503 }
504
505 if (exit.toStringCall == nullptr) {
506 return false;
507 }
508
509 return true;
510 }
511
IsInstanceHoistable(const ConcatenationLoopMatch & match) const512 bool SimplifyStringBuilder::IsInstanceHoistable(const ConcatenationLoopMatch &match) const
513 {
514 return match.IsInstanceHoistable() && HasAppendUsersOnly(match.accValue);
515 }
516
IsToStringHoistable(const ConcatenationLoopMatch & match,Marker appendInstructionVisited) const517 bool SimplifyStringBuilder::IsToStringHoistable(const ConcatenationLoopMatch &match,
518 Marker appendInstructionVisited) const
519 {
520 return HasPhiOrAppendUsersOnly(match.exit.toStringCall, appendInstructionVisited);
521 }
522
FindPreHeaderSaveState(Loop * loop)523 SaveStateInst *FindPreHeaderSaveState(Loop *loop)
524 {
525 for (const auto &inst : loop->GetPreHeader()->InstsReverse()) {
526 if (inst->GetOpcode() == Opcode::SaveState) {
527 return inst->CastToSaveState();
528 }
529 }
530 return nullptr;
531 }
532
CountOuterLoopSuccs(BasicBlock * block)533 size_t CountOuterLoopSuccs(BasicBlock *block)
534 {
535 return std::count_if(block->GetSuccsBlocks().begin(), block->GetSuccsBlocks().end(),
536 [block](auto succ) { return succ->GetLoop() == block->GetLoop()->GetOuterLoop(); });
537 }
538
GetOuterLoopSucc(BasicBlock * block)539 BasicBlock *GetOuterLoopSucc(BasicBlock *block)
540 {
541 auto found = std::find_if(block->GetSuccsBlocks().begin(), block->GetSuccsBlocks().end(),
542 [block](auto succ) { return succ->GetLoop() == block->GetLoop()->GetOuterLoop(); });
543 return found != block->GetSuccsBlocks().end() ? *found : nullptr;
544 }
545
GetLoopPostExit(Loop * loop)546 BasicBlock *GetLoopPostExit(Loop *loop)
547 {
548 // Find a block immediately following after loop
549 // Supported case:
550 // 1. Preheader block exists
551 // 2. Loop has exactly one block with exactly one successor outside a loop (post exit block)
552 // 3. Preheader dominates post exit block found
553 // Loop structures different from the one described above are not supported in current implementation
554
555 BasicBlock *postExit = nullptr;
556 for (auto block : loop->GetBlocks()) {
557 size_t count = CountOuterLoopSuccs(block);
558 if (count == 0) {
559 continue;
560 }
561 if (count == 1 && postExit == nullptr) {
562 postExit = GetOuterLoopSucc(block);
563 continue;
564 }
565 // Unsupported case
566 return nullptr;
567 }
568
569 // Supported case
570 if (postExit != nullptr && postExit->GetPredsBlocks().size() == 1 && loop->GetPreHeader() != nullptr &&
571 loop->GetPreHeader()->IsDominate(postExit)) {
572 return postExit;
573 }
574
575 // Unsupported case
576 return nullptr;
577 }
578
CreateIntrinsic(Graph * graph,RuntimeInterface::IntrinsicId intrinsicId,DataType::Type type,const std::initializer_list<std::pair<Inst *,DataType::Type>> & args)579 IntrinsicInst *CreateIntrinsic(Graph *graph, RuntimeInterface::IntrinsicId intrinsicId, DataType::Type type,
580 const std::initializer_list<std::pair<Inst *, DataType::Type>> &args)
581 {
582 auto intrinsic = graph->CreateInstIntrinsic(intrinsicId);
583
584 intrinsic->SetType(type);
585 intrinsic->SetInputs(graph->GetAllocator(), args);
586
587 return intrinsic;
588 }
589
CreateIntrinsicStringBuilderAppendString(Inst * instance,Inst * arg,SaveStateInst * saveState)590 IntrinsicInst *SimplifyStringBuilder::CreateIntrinsicStringBuilderAppendString(Inst *instance, Inst *arg,
591 SaveStateInst *saveState)
592 {
593 return CreateIntrinsic(GetGraph(), GetGraph()->GetRuntime()->GetStringBuilderAppendStringsIntrinsicId(1U),
594 DataType::REFERENCE,
595 {{instance, instance->GetType()}, {arg, arg->GetType()}, {saveState, saveState->GetType()}});
596 }
597
NormalizeStringBuilderAppendInstructionUsers(Inst * instance,SaveStateInst * saveState)598 void SimplifyStringBuilder::NormalizeStringBuilderAppendInstructionUsers(Inst *instance, SaveStateInst *saveState)
599 {
600 [[maybe_unused]] Inst *ctorCall = nullptr;
601
602 for (auto &user : instance->GetUsers()) {
603 auto userInst = SkipSingleUserCheckInstruction(user.GetInst());
604 // Make additional append-call out of constructor argument (if present)
605 if (IsMethodStringBuilderConstructorWithStringArg(userInst)) {
606 ASSERT(ctorCall == nullptr);
607 ctorCall = userInst;
608 auto ctorArg = ctorCall->GetInput(1).GetInst();
609 CreateIntrinsicStringBuilderAppendString(instance, ctorArg, CopySaveState(GetGraph(), saveState));
610 } else if (IsMethodStringBuilderDefaultConstructor(userInst)) {
611 ASSERT(ctorCall == nullptr);
612 ctorCall = userInst;
613 } else if (IsStringBuilderAppend(userInst)) {
614 // StringBuilder append-call returns 'this' (instance)
615 // Replace all users of append-call by instance for simplicity
616 userInst->ReplaceUsers(instance);
617 }
618 }
619 ASSERT(ctorCall != nullptr);
620 }
621
FindStringBuilderAppendInstructions(Inst * instance)622 ArenaVector<Inst *> SimplifyStringBuilder::FindStringBuilderAppendInstructions(Inst *instance)
623 {
624 ArenaVector<Inst *> appendInstructions {GetGraph()->GetAllocator()->Adapter()};
625 for (auto &user : instance->GetUsers()) {
626 auto userInst = SkipSingleUserCheckInstruction(user.GetInst());
627 if (IsStringBuilderAppend(userInst)) {
628 appendInstructions.push_back(userInst);
629 }
630 }
631
632 return appendInstructions;
633 }
634
RemoveFromSaveStateInputs(Inst * inst)635 void SimplifyStringBuilder::RemoveFromSaveStateInputs(Inst *inst)
636 {
637 inputDescriptors_.clear();
638
639 for (auto &user : inst->GetUsers()) {
640 if (!user.GetInst()->IsSaveState()) {
641 continue;
642 }
643 inputDescriptors_.emplace_back(user.GetInst(), user.GetIndex());
644 }
645
646 RemoveFromInstructionInputs(inputDescriptors_);
647 }
648
RemoveFromAllExceptPhiInputs(Inst * inst)649 void SimplifyStringBuilder::RemoveFromAllExceptPhiInputs(Inst *inst)
650 {
651 inputDescriptors_.clear();
652
653 for (auto &user : inst->GetUsers()) {
654 if (user.GetInst()->IsPhi()) {
655 continue;
656 }
657 inputDescriptors_.emplace_back(user.GetInst(), user.GetIndex());
658 }
659
660 RemoveFromInstructionInputs(inputDescriptors_);
661 }
662
RemoveStringBuilderInstance(Inst * instance)663 void SimplifyStringBuilder::RemoveStringBuilderInstance(Inst *instance)
664 {
665 ASSERT(!HasUser(instance, [](auto &user) {
666 auto userInst = SkipSingleUserCheckInstruction(user.GetInst());
667 auto hasUsers = userInst->HasUsers();
668 auto isSaveState = userInst->IsSaveState();
669 auto isCtorCall = IsMethodStringBuilderDefaultConstructor(userInst) ||
670 IsMethodStringBuilderConstructorWithStringArg(userInst) ||
671 IsMethodStringBuilderConstructorWithCharArrayArg(userInst);
672 auto isAppendInstruction = IsStringBuilderAppend(userInst);
673 auto isToStringCall = IsStringBuilderToString(userInst);
674 return !(isSaveState || isCtorCall || ((isAppendInstruction || isToStringCall) && !hasUsers));
675 }));
676
677 RemoveFromSaveStateInputs(instance);
678
679 for (auto &user : instance->GetUsers()) {
680 auto userInst = user.GetInst();
681 if (userInst->IsCheck()) {
682 auto checkUserInst = SkipSingleUserCheckInstruction(userInst);
683 checkUserInst->GetBasicBlock()->RemoveInst(checkUserInst);
684 COMPILER_LOG(DEBUG, SIMPLIFY_SB)
685 << "Remove StringBuilder user instruction (id=" << checkUserInst->GetId() << ")";
686 }
687
688 userInst->GetBasicBlock()->RemoveInst(userInst);
689 COMPILER_LOG(DEBUG, SIMPLIFY_SB) << "Remove StringBuilder user instruction (id=" << userInst->GetId() << ")";
690 }
691
692 ASSERT(!instance->HasUsers());
693 instance->GetBasicBlock()->RemoveInst(instance);
694 COMPILER_LOG(DEBUG, SIMPLIFY_SB) << "Remove StringBuilder instance (id=" << instance->GetId() << ")";
695 }
696
ReconnectStringBuilderCascade(Inst * instance,Inst * inputInst,Inst * appendInstruction,SaveStateInst * saveState)697 void SimplifyStringBuilder::ReconnectStringBuilderCascade(Inst *instance, Inst *inputInst, Inst *appendInstruction,
698 SaveStateInst *saveState)
699 {
700 // Reconnect all append-calls of input_instance to instance instruction
701
702 // Check if input of append-call is toString-call
703 if (inputInst->GetBasicBlock() != appendInstruction->GetBasicBlock() || !IsStringBuilderToString(inputInst)) {
704 return;
705 }
706
707 // Get cascading instance of input toString-call
708 auto inputToStringCall = inputInst;
709 ASSERT(inputToStringCall->GetInputsCount() > 0);
710 auto inputInstance = inputToStringCall->GetDataFlowInput(0);
711 if (inputInstance == instance) {
712 return;
713 }
714
715 instructionsStack_.push(inputInstance);
716
717 NormalizeStringBuilderAppendInstructionUsers(inputInstance, saveState);
718 for (auto inputAppendInstruction : FindStringBuilderAppendInstructions(inputInstance)) {
719 COMPILER_LOG(DEBUG, SIMPLIFY_SB) << "Retarget append instrisic (id=" << inputAppendInstruction->GetId()
720 << ") to instance (id=" << instance->GetId() << ")";
721
722 inputAppendInstruction->SetInput(0, instance);
723 inputAppendInstruction->SetSaveState(saveState);
724
725 if (inputAppendInstruction->GetBasicBlock() != nullptr) {
726 inputAppendInstruction->GetBasicBlock()->EraseInst(inputAppendInstruction, true);
727 }
728 appendInstruction->InsertAfter(inputAppendInstruction);
729
730 for (auto &input : inputAppendInstruction->GetInputs()) {
731 if (input.GetInst()->IsSaveState()) {
732 continue;
733 }
734 FixBrokenSaveStates(input.GetInst(), inputAppendInstruction);
735 }
736 }
737
738 // Erase input_instance constructor from block
739 for (auto &user : inputInstance->GetUsers()) {
740 auto userInst = SkipSingleUserCheckInstruction(user.GetInst());
741 if (IsMethodStringBuilderConstructorWithStringArg(userInst) ||
742 IsMethodStringBuilderDefaultConstructor(userInst)) {
743 userInst->ClearFlag(compiler::inst_flags::NO_DCE);
744 }
745 }
746
747 // Cleanup save states
748 RemoveFromSaveStateInputs(inputInstance);
749 // Erase input_instance itself
750 inputInstance->ClearFlag(compiler::inst_flags::NO_DCE);
751
752 // Cleanup instructions we don't need anymore
753 appendInstruction->GetBasicBlock()->RemoveInst(appendInstruction);
754 RemoveFromSaveStateInputs(inputToStringCall);
755 inputToStringCall->ClearFlag(compiler::inst_flags::NO_DCE);
756 }
757
ReconnectStringBuilderCascades(const ConcatenationLoopMatch & match)758 void SimplifyStringBuilder::ReconnectStringBuilderCascades(const ConcatenationLoopMatch &match)
759 {
760 // Consider the following code:
761 // str += a + b + c + ...
762 // StringBuilder equivalent view:
763 // sb_abc.append(a)
764 // sb_abc.append(b)
765 // sb_abc.append(c)
766 // sb_str.append(sb_abc.toString())
767 //
768 // We call StringBuilder cascading to be calls like sb_str.append(sb_abc.toString()), i.e output of one SB used as
769 // input of another SB
770 //
771 // The code below transforms this into:
772 // sb_str.append(a)
773 // sb_str.append(b)
774 // sb_str.append(c)
775 // i.e appending args directly to string 'str', w/o the use of intermediate SB
776
777 ASSERT(instructionsStack_.empty());
778 instructionsStack_.push(match.preheader.instance);
779
780 while (!instructionsStack_.empty()) {
781 auto instance = instructionsStack_.top();
782 instructionsStack_.pop();
783
784 // For each append-call of current StringBuilder instance
785 for (auto appendInstruction : FindStringBuilderAppendInstructions(instance)) {
786 for (auto &input : appendInstruction->GetInputs()) {
787 auto inputInst = input.GetInst();
788
789 // Reconnect append-calls of cascading instance
790 ReconnectStringBuilderCascade(instance, inputInst, appendInstruction,
791 appendInstruction->GetSaveState());
792 }
793 }
794 }
795 }
796
ReconnectInstructions(const ConcatenationLoopMatch & match)797 void SimplifyStringBuilder::ReconnectInstructions(const ConcatenationLoopMatch &match)
798 {
799 // Make StringBuilder append-call hoisted point to an instance hoisted and initialize it with string initial value
800 match.preheader.appendAccValue->SetInput(0, match.preheader.instance);
801 match.preheader.appendAccValue->SetInput(1, match.initialValue);
802
803 // Make temporary instance users point to an instance hoisted
804 for (auto &temp : match.temp) {
805 instructionsVector_.clear();
806 for (auto &user : temp.instance->GetUsers()) {
807 auto userInst = user.GetInst();
808 if (userInst->IsSaveState()) {
809 continue;
810 }
811 instructionsVector_.push_back(userInst);
812 }
813 for (auto userInst : instructionsVector_) {
814 userInst->ReplaceInput(temp.instance, match.preheader.instance);
815
816 COMPILER_LOG(DEBUG, SIMPLIFY_SB)
817 << "Replace input of instruction "
818 << "id=" << userInst->GetId() << " (" << GetOpcodeString(userInst->GetOpcode())
819 << ") old id=" << temp.instance->GetId() << " (" << GetOpcodeString(temp.instance->GetOpcode())
820 << ") new id=" << match.preheader.instance->GetId() << " ("
821 << GetOpcodeString(match.preheader.instance->GetOpcode()) << ")";
822 }
823 }
824
825 // Replace users of accumulated value outside the loop by toString-call hoisted to post exit block
826 instructionsVector_.clear();
827 for (auto &user : match.accValue->GetUsers()) {
828 auto userInst = user.GetInst();
829 if (userInst->IsSaveState()) {
830 continue;
831 }
832 if (userInst->GetBasicBlock() != match.block) {
833 instructionsVector_.push_back(userInst);
834 }
835 }
836
837 for (auto userInst : instructionsVector_) {
838 userInst->ReplaceInput(match.accValue, match.exit.toStringCall);
839
840 COMPILER_LOG(DEBUG, SIMPLIFY_SB) << "Replace input of instruction "
841 << "id=" << userInst->GetId() << " (" << GetOpcodeString(userInst->GetOpcode())
842 << ") old id=" << match.accValue->GetId() << " ("
843 << GetOpcodeString(match.accValue->GetOpcode())
844 << ") new id=" << match.exit.toStringCall->GetId() << " ("
845 << GetOpcodeString(match.exit.toStringCall->GetOpcode()) << ")";
846 }
847
848 ReconnectStringBuilderCascades(match);
849 }
850
AllInstructionInputsDominate(Inst * inst,Inst * other)851 bool AllInstructionInputsDominate(Inst *inst, Inst *other)
852 {
853 return !HasInput(inst, [other](auto &input) { return !input.GetInst()->IsDominate(other); });
854 }
855
HoistInstructionToPreHeader(BasicBlock * preHeader,Inst * lastInst,Inst * inst,SaveStateInst * saveState)856 Inst *SimplifyStringBuilder::HoistInstructionToPreHeader(BasicBlock *preHeader, Inst *lastInst, Inst *inst,
857 SaveStateInst *saveState)
858 {
859 // Based on similar code in LICM-pass
860
861 COMPILER_LOG(DEBUG, SIMPLIFY_SB) << "Hoist instruction id=" << inst->GetId() << " ("
862 << GetOpcodeString(inst->GetOpcode()) << ")"
863 << " from loop block id=" << inst->GetBasicBlock()->GetId()
864 << " to preheader block id=" << preHeader->GetId();
865
866 Inst *target = nullptr;
867 if (inst->IsMovableObject()) {
868 target = inst->GetPrev();
869 if (target == nullptr) {
870 target = inst->GetNext();
871 }
872 if (target == nullptr) {
873 target = GetGraph()->CreateInstNOP();
874 inst->InsertAfter(target);
875 }
876 }
877 inst->GetBasicBlock()->EraseInst(inst, true);
878 if (lastInst == nullptr || lastInst->IsPhi()) {
879 preHeader->AppendInst(inst);
880 lastInst = inst;
881 } else {
882 ASSERT(lastInst->GetBasicBlock() == preHeader);
883 Inst *saveStateDeoptimize = preHeader->FindSaveStateDeoptimize();
884 if (saveStateDeoptimize != nullptr && AllInstructionInputsDominate(inst, saveStateDeoptimize)) {
885 saveStateDeoptimize->InsertBefore(inst);
886 } else {
887 lastInst->InsertAfter(inst);
888 lastInst = inst;
889 }
890 }
891
892 if (inst->RequireState()) {
893 ASSERT(saveState != nullptr);
894 auto saveStateClone = CopySaveState(GetGraph(), saveState);
895 if (saveStateClone->GetBasicBlock() == nullptr) {
896 inst->InsertBefore(saveStateClone);
897 }
898 inst->SetSaveState(saveStateClone);
899 inst->SetPc(saveStateClone->GetPc());
900 }
901
902 FixBrokenSaveStates(inst, target);
903
904 return lastInst;
905 }
906
HoistInstructionToPreHeaderRecursively(BasicBlock * preHeader,Inst * lastInst,Inst * inst,SaveStateInst * saveState)907 Inst *SimplifyStringBuilder::HoistInstructionToPreHeaderRecursively(BasicBlock *preHeader, Inst *lastInst, Inst *inst,
908 SaveStateInst *saveState)
909 {
910 // Hoist all non-SaveState instruction inputs first
911 for (auto &input : inst->GetInputs()) {
912 auto inputInst = input.GetInst();
913 if (inputInst->IsSaveState()) {
914 continue;
915 }
916
917 if (inputInst->GetBasicBlock() == preHeader) {
918 continue;
919 }
920
921 lastInst = HoistInstructionToPreHeaderRecursively(preHeader, lastInst, inputInst, saveState);
922 if (lastInst->RequireState()) {
923 saveState = lastInst->GetSaveState();
924 }
925 }
926
927 // Hoist instruction itself
928 return HoistInstructionToPreHeader(preHeader, lastInst, inst, saveState);
929 }
930
HoistInstructionsToPreHeader(const ConcatenationLoopMatch & match,SaveStateInst * initSaveState)931 void SimplifyStringBuilder::HoistInstructionsToPreHeader(const ConcatenationLoopMatch &match,
932 SaveStateInst *initSaveState)
933 {
934 // Move StringBuilder construction and initialization from inside loop to preheader block
935
936 auto loop = match.block->GetLoop();
937 auto preHeader = loop->GetPreHeader();
938
939 HoistInstructionToPreHeaderRecursively(preHeader, preHeader->GetLastInst(), match.preheader.ctorCall,
940 initSaveState);
941
942 ASSERT(match.preheader.ctorCall->RequireState());
943 HoistInstructionToPreHeader(preHeader, match.preheader.ctorCall, match.preheader.appendAccValue,
944 match.preheader.ctorCall->GetSaveState());
945
946 for (auto &input : match.preheader.appendAccValue->GetInputs()) {
947 auto inputInst = input.GetInst();
948 if (inputInst->IsSaveState()) {
949 continue;
950 }
951
952 FixBrokenSaveStates(inputInst, match.preheader.appendAccValue);
953 }
954 }
955
HoistCheckInsturctionInputs(Inst * inst,BasicBlock * loopBlock,BasicBlock * postExit)956 void HoistCheckInsturctionInputs(Inst *inst, BasicBlock *loopBlock, BasicBlock *postExit)
957 {
958 for (auto &input : inst->GetInputs()) {
959 auto inputInst = input.GetInst();
960 if (inputInst->GetBasicBlock() == loopBlock && inputInst->IsCheck()) {
961 inputInst->GetBasicBlock()->EraseInst(inputInst, true);
962 if (inputInst->RequireState()) {
963 inputInst->SetSaveState(CopySaveState(loopBlock->GetGraph(), inst->GetSaveState()));
964 }
965 InsertBeforeWithSaveState(inputInst, inst);
966
967 COMPILER_LOG(DEBUG, SIMPLIFY_SB)
968 << "Hoist instruction id=" << inputInst->GetId() << " (" << GetOpcodeString(inputInst->GetOpcode())
969 << ") from loop block id=" << loopBlock->GetId() << " to post exit block id=" << postExit->GetId();
970 }
971 }
972 }
973
HoistCheckCastInstructionUsers(Inst * inst,BasicBlock * loopBlock,BasicBlock * postExit)974 void SimplifyStringBuilder::HoistCheckCastInstructionUsers(Inst *inst, BasicBlock *loopBlock, BasicBlock *postExit)
975 {
976 // Hoist CheckCast instruction to post exit block
977
978 // Start with CheckCast instruction itself
979 ASSERT(instructionsStack_.empty());
980 for (auto &user : inst->GetUsers()) {
981 auto userInst = user.GetInst();
982 if (userInst->GetBasicBlock() == loopBlock && IsCheckCastWithoutUsers(userInst)) {
983 instructionsStack_.push(userInst);
984 }
985 }
986
987 // Collect all the inputs of CheckCast instruction as well
988 instructionsVector_.clear();
989 while (!instructionsStack_.empty()) {
990 auto userInst = instructionsStack_.top();
991 instructionsStack_.pop();
992 for (auto &input : userInst->GetInputs()) {
993 auto inputInst = input.GetInst();
994 if (inputInst->IsSaveState()) {
995 continue;
996 }
997 if (inputInst->GetBasicBlock() != loopBlock) {
998 continue;
999 }
1000
1001 instructionsStack_.push(inputInst);
1002 }
1003 instructionsVector_.push_back(userInst);
1004 }
1005
1006 // Hoist collected instructions
1007 for (auto userInst : instructionsVector_) {
1008 userInst->GetBasicBlock()->EraseInst(userInst, true);
1009 if (userInst->RequireState()) {
1010 userInst->SetSaveState(CopySaveState(GetGraph(), inst->GetSaveState()));
1011 }
1012 InsertAfterWithSaveState(userInst, inst);
1013
1014 COMPILER_LOG(DEBUG, SIMPLIFY_SB) << "Hoist instruction id=" << userInst->GetId() << " ("
1015 << GetOpcodeString(userInst->GetOpcode())
1016 << ") from loop block id=" << loopBlock->GetId()
1017 << " to post exit block id=" << postExit->GetId();
1018 }
1019 }
1020
HoistInstructionsToPostExit(const ConcatenationLoopMatch & match,SaveStateInst * saveState)1021 void SimplifyStringBuilder::HoistInstructionsToPostExit(const ConcatenationLoopMatch &match, SaveStateInst *saveState)
1022 {
1023 // Move toString()-call and its inputs/users (null-checks, etc) out of the loop
1024 // and place them in the loop exit successor block
1025
1026 auto postExit = GetLoopPostExit(match.block->GetLoop());
1027 ASSERT(postExit != nullptr);
1028 ASSERT(!postExit->IsEmpty());
1029 ASSERT(saveState->GetBasicBlock() == postExit);
1030 ASSERT(match.exit.toStringCall->RequireState());
1031
1032 auto loopBlock = match.exit.toStringCall->GetBasicBlock();
1033 loopBlock->EraseInst(match.exit.toStringCall, true);
1034
1035 if (!saveState->HasUsers()) {
1036 // First use of save state, insert toString-call after it
1037 match.exit.toStringCall->SetSaveState(saveState);
1038 saveState->InsertAfter(match.exit.toStringCall);
1039 } else {
1040 // Duplicate save state and prepend both instructions
1041 match.exit.toStringCall->SetSaveState(CopySaveState(GetGraph(), saveState));
1042 InsertBeforeWithSaveState(match.exit.toStringCall, postExit->GetFirstInst());
1043 }
1044
1045 COMPILER_LOG(DEBUG, SIMPLIFY_SB) << "Hoist toString()-call instruction id=" << match.exit.toStringCall->GetId()
1046 << " from loop block id=" << loopBlock->GetId()
1047 << " to post exit block id=" << postExit->GetId();
1048
1049 // Hoist all the toString-call Check instructions inputs
1050 HoistCheckInsturctionInputs(match.exit.toStringCall, loopBlock, postExit);
1051
1052 // Hoist toString-call instructions users
1053 HoistCheckCastInstructionUsers(match.exit.toStringCall, loopBlock, postExit);
1054 }
1055
Cleanup(const ConcatenationLoopMatch & match)1056 void SimplifyStringBuilder::Cleanup(const ConcatenationLoopMatch &match)
1057 {
1058 // Remove temporary instructions
1059
1060 for (auto &temp : match.temp) {
1061 temp.toStringCall->ClearFlag(compiler::inst_flags::NO_DCE);
1062 for (auto &user : temp.toStringCall->GetUsers()) {
1063 auto userInst = user.GetInst();
1064 if (IsCheckCastWithoutUsers(userInst)) {
1065 userInst->ClearFlag(compiler::inst_flags::NO_DCE);
1066 }
1067 }
1068 temp.intermediateValue->ClearFlag(compiler::inst_flags::NO_DCE);
1069 temp.instance->ReplaceUsers(match.preheader.instance);
1070 temp.instance->ClearFlag(compiler::inst_flags::NO_DCE);
1071 temp.ctorCall->ClearFlag(compiler::inst_flags::NO_DCE);
1072 temp.appendAccValue->ClearFlag(compiler::inst_flags::NO_DCE);
1073 }
1074 }
1075
NeedRemoveInputFromSaveStateInstruction(Inst * inputInst)1076 bool SimplifyStringBuilder::NeedRemoveInputFromSaveStateInstruction(Inst *inputInst)
1077 {
1078 for (auto &match : matches_) {
1079 // If input is hoisted toString-call or accumulated phi instruction mark it for removal
1080 if (inputInst == match.exit.toStringCall || inputInst == match.accValue) {
1081 return true;
1082 }
1083
1084 // If input is removed toString-call (temporary instruction) mark it for removal
1085 bool isIntermediateValue = std::find_if(match.temp.begin(), match.temp.end(), [inputInst](auto &temp) {
1086 return inputInst == temp.toStringCall;
1087 }) != match.temp.end();
1088 if (isIntermediateValue) {
1089 return true;
1090 }
1091 }
1092 return false;
1093 }
1094
CollectSaveStateInputsForRemoval(Inst * inst)1095 void SimplifyStringBuilder::CollectSaveStateInputsForRemoval(Inst *inst)
1096 {
1097 ASSERT(inst->IsSaveState());
1098
1099 for (size_t i = 0; i < inst->GetInputsCount(); ++i) {
1100 auto inputInst = inst->GetInput(i).GetInst();
1101 if (NeedRemoveInputFromSaveStateInstruction(inputInst)) {
1102 inputDescriptors_.emplace_back(inst, i);
1103 }
1104 }
1105 }
1106
CleanupSaveStateInstructionInputs(Loop * loop)1107 void SimplifyStringBuilder::CleanupSaveStateInstructionInputs(Loop *loop)
1108 {
1109 // StringBuilder toString-call is either hoisted to post exit block or erased from loop, accumulated value is erased
1110 // from loop, so this instructions need to be removed from the inputs of save state instructions within current loop
1111
1112 inputDescriptors_.clear();
1113 for (auto block : loop->GetBlocks()) {
1114 for (auto inst : block->Insts()) {
1115 if (!inst->IsSaveState()) {
1116 continue;
1117 }
1118 CollectSaveStateInputsForRemoval(inst);
1119 }
1120 }
1121 RemoveFromInstructionInputs(inputDescriptors_);
1122 }
1123
FindHoistedToStringCallInput(Inst * phi)1124 Inst *SimplifyStringBuilder::FindHoistedToStringCallInput(Inst *phi)
1125 {
1126 for (auto &match : matches_) {
1127 auto toStringCall = match.exit.toStringCall;
1128 if (HasInput(phi, [toStringCall](auto &input) { return input.GetInst() == toStringCall; })) {
1129 return toStringCall;
1130 }
1131 }
1132
1133 return nullptr;
1134 }
1135
CleanupPhiInstructionInputs(Inst * phi)1136 void SimplifyStringBuilder::CleanupPhiInstructionInputs(Inst *phi)
1137 {
1138 ASSERT(phi->IsPhi());
1139
1140 auto toStringCall = FindHoistedToStringCallInput(phi);
1141 if (toStringCall != nullptr) {
1142 RemoveFromSaveStateInputs(phi);
1143 phi->ReplaceUsers(toStringCall);
1144 phi->GetBasicBlock()->RemoveInst(phi);
1145 }
1146 }
1147
CleanupPhiInstructionInputs(Loop * loop)1148 void SimplifyStringBuilder::CleanupPhiInstructionInputs(Loop *loop)
1149 {
1150 // Remove toString()-call from accumulated value phi-instruction inputs,
1151 // replace accumulated value users with toString()-call, and remove accumulated value itself
1152 for (auto block : loop->GetBlocks()) {
1153 for (auto phi : block->PhiInstsSafe()) {
1154 CleanupPhiInstructionInputs(phi);
1155 }
1156 }
1157 }
1158
HasNotHoistedUser(PhiInst * phi)1159 bool SimplifyStringBuilder::HasNotHoistedUser(PhiInst *phi)
1160 {
1161 return HasUser(phi, [phi](auto &user) {
1162 auto userInst = user.GetInst();
1163 bool isSelf = userInst == phi;
1164 bool isSaveState = userInst->IsSaveState();
1165 bool isRemovedAppendInstruction =
1166 IsStringBuilderAppend(userInst) && !userInst->GetFlag(compiler::inst_flags::NO_DCE);
1167 return !isSelf && !isSaveState && !isRemovedAppendInstruction;
1168 });
1169 }
1170
RemoveUnusedPhiInstructions(Loop * loop)1171 void SimplifyStringBuilder::RemoveUnusedPhiInstructions(Loop *loop)
1172 {
1173 // Remove instructions having no users, or instruction with all users hoisted out of the loop
1174 for (auto block : loop->GetBlocks()) {
1175 for (auto phi : block->PhiInstsSafe()) {
1176 if (HasNotHoistedUser(phi->CastToPhi())) {
1177 continue;
1178 }
1179
1180 RemoveFromAllExceptPhiInputs(phi);
1181 block->RemoveInst(phi);
1182
1183 COMPILER_LOG(DEBUG, SIMPLIFY_SB)
1184 << "Remove unused instruction id=" << phi->GetId() << " (" << GetOpcodeString(phi->GetOpcode())
1185 << ") from header block id=" << block->GetId();
1186 }
1187 }
1188 }
1189
FixBrokenSaveStates(Loop * loop)1190 void SimplifyStringBuilder::FixBrokenSaveStates(Loop *loop)
1191 {
1192 ssb_.FixSaveStatesInBB(loop->GetPreHeader());
1193 ssb_.FixSaveStatesInBB(GetLoopPostExit(loop));
1194 }
1195
Cleanup(Loop * loop)1196 void SimplifyStringBuilder::Cleanup(Loop *loop)
1197 {
1198 if (!isApplied_) {
1199 return;
1200 }
1201
1202 FixBrokenSaveStates(loop);
1203 CleanupSaveStateInstructionInputs(loop);
1204 CleanupPhiInstructionInputs(loop);
1205 RemoveUnusedPhiInstructions(loop);
1206 }
1207
MatchStringBuilderUsage(Inst * instance,StringBuilderUsage & usage)1208 void SimplifyStringBuilder::MatchStringBuilderUsage(Inst *instance, StringBuilderUsage &usage)
1209 {
1210 // Find all the usages of a given StringBuilder instance, and pack them into StringBuilderUsage structure:
1211 // i.e instance itself, constructor-call, all append-calls, all toString-calls
1212
1213 usage.instance = instance;
1214
1215 for (auto &user : instance->GetUsers()) {
1216 auto userInst = SkipSingleUserCheckInstruction(user.GetInst());
1217 if (IsMethodStringBuilderConstructorWithStringArg(userInst)) {
1218 usage.ctorCall = userInst;
1219 } else if (IsMethodStringBuilderDefaultConstructor(userInst)) {
1220 usage.ctorCall = userInst;
1221 } else if (IsStringBuilderAppend(userInst)) {
1222 // StringBuilder append-call returns 'this' (instance)
1223 // Replace all users of append-call by instance for simplicity
1224 userInst->ReplaceUsers(instance);
1225 }
1226 }
1227 ASSERT(usage.ctorCall != nullptr);
1228
1229 for (auto &user : instance->GetUsers()) {
1230 auto userInst = SkipSingleUserCheckInstruction(user.GetInst());
1231 if (IsStringBuilderAppend(userInst)) {
1232 usage.appendInstructions.push_back(userInst);
1233 } else if (IsStringBuilderToString(userInst)) {
1234 usage.toStringCalls.push_back(userInst);
1235 }
1236 }
1237 }
1238
HasInputFromPreHeader(PhiInst * phi) const1239 bool SimplifyStringBuilder::HasInputFromPreHeader(PhiInst *phi) const
1240 {
1241 auto preHeader = phi->GetBasicBlock()->GetLoop()->GetPreHeader();
1242 for (size_t i = 0; i < phi->GetInputsCount(); ++i) {
1243 if (phi->GetPhiInputBb(i) == preHeader) {
1244 return true;
1245 }
1246 }
1247 return false;
1248 }
1249
HasToStringCallInput(PhiInst * phi) const1250 bool SimplifyStringBuilder::HasToStringCallInput(PhiInst *phi) const
1251 {
1252 // Returns true if
1253 // (1) 'phi' has StringBuilder.toString call as one of its inputs, and
1254 // (2) StringBuilder.toString call has no effective usages except this 'phi' itself.
1255 // Users being save states, check casts, and not used users are skipped.
1256
1257 MarkerHolder visited {GetGraph()};
1258
1259 // (1)
1260 bool hasToStringCallInput = HasInputPhiRecursively(
1261 phi, visited.GetMarker(), [](auto &input) { return IsStringBuilderToString(input.GetInst()); });
1262
1263 // (2)
1264 bool toStringCallInputUsedAnywhereExceptPhi = HasInput(phi, [phi](auto &input) {
1265 return IsStringBuilderToString(input.GetInst()) && HasUser(input.GetInst(), [phi](auto &user) {
1266 auto userInst = user.GetInst();
1267 bool isPhi = userInst == phi;
1268 bool isSaveState = userInst->IsSaveState();
1269 bool isCheckCast = IsCheckCastWithoutUsers(userInst);
1270 bool hasUsers = userInst->HasUsers();
1271 return !isPhi && !isSaveState && !isCheckCast && hasUsers;
1272 });
1273 });
1274 ResetInputMarkersRecursively(phi, visited.GetMarker());
1275 return hasToStringCallInput && !toStringCallInputUsedAnywhereExceptPhi;
1276 }
1277
HasInputInst(Inst * inputInst,Inst * inst) const1278 bool SimplifyStringBuilder::HasInputInst(Inst *inputInst, Inst *inst) const
1279 {
1280 MarkerHolder visited {GetGraph()};
1281 bool found = HasInputPhiRecursively(inst, visited.GetMarker(),
1282 [inputInst](auto &input) { return inputInst == input.GetInst(); });
1283 ResetInputMarkersRecursively(inst, visited.GetMarker());
1284 return found;
1285 }
1286
HasAppendInstructionUser(Inst * inst) const1287 bool SimplifyStringBuilder::HasAppendInstructionUser(Inst *inst) const
1288 {
1289 Loop *instLoop = inst->GetBasicBlock()->GetLoop();
1290 for (auto &user : inst->GetUsers()) {
1291 auto appendInst = SkipSingleUserCheckInstruction(user.GetInst());
1292 if (!IsStringBuilderAppend(appendInst) || appendInst->GetDataFlowInput(1) != inst ||
1293 appendInst->GetBasicBlock()->GetLoop() != instLoop) {
1294 continue;
1295 }
1296
1297 auto instance = appendInst->GetDataFlowInput(0);
1298 if (!IsStringBuilderInstance(instance) || instance->GetBasicBlock() != appendInst->GetBasicBlock()) {
1299 continue;
1300 }
1301
1302 // Cycle through instructions from appendInst to sb (backwards) and make sure no other appends in between
1303 auto currentInst = appendInst->GetPrev();
1304 while (currentInst != nullptr && currentInst != instance) {
1305 if (IsStringBuilderAppend(currentInst) && currentInst->GetDataFlowInput(0) == instance) {
1306 return false;
1307 }
1308 currentInst = currentInst->GetPrev();
1309 }
1310 return true;
1311 }
1312
1313 return false;
1314 }
1315
IsPhiAccumulatedValue(PhiInst * phi) const1316 bool SimplifyStringBuilder::IsPhiAccumulatedValue(PhiInst *phi) const
1317 {
1318 // Phi-instruction is accumulated value, if it is used in the following way:
1319 // bb_preheader:
1320 // 0 LoadString ...
1321 // ...
1322 // bb_header:
1323 // 10p Phi v0(bb_preheader), v20(bb_back_edge)
1324 // ...
1325 // bb_back_edge:
1326 // ...
1327 // 15 Intrinsic.StdCoreSbAppendString sb, v10p, ss
1328 // ...
1329 // 20 CallStatic std.core.StringBuilder::toString sb, ss
1330 // ...
1331
1332 return HasInputFromPreHeader(phi) && HasToStringCallInput(phi) && HasAppendInstructionUser(phi);
1333 }
1334
GetPhiAccumulatedValues(Loop * loop)1335 ArenaVector<Inst *> SimplifyStringBuilder::GetPhiAccumulatedValues(Loop *loop)
1336 {
1337 // Search loop for all accumulated values
1338 // Phi accumulated value is an instruction used to store string concatenation result between loop iterations
1339
1340 instructionsVector_.clear();
1341
1342 for (auto inst : loop->GetHeader()->PhiInsts()) {
1343 if (IsPhiAccumulatedValue(inst->CastToPhi())) {
1344 instructionsVector_.push_back(inst);
1345 }
1346 }
1347
1348 for (auto backEdge : loop->GetBackEdges()) {
1349 if (backEdge == loop->GetHeader()) {
1350 // Already processed above
1351 continue;
1352 }
1353
1354 for (auto inst : backEdge->PhiInsts()) {
1355 if (IsPhiAccumulatedValue(inst->CastToPhi())) {
1356 instructionsVector_.push_back(inst);
1357 }
1358 }
1359 }
1360
1361 return instructionsVector_;
1362 }
1363
StringBuilderUsagesDFS(Inst * inst,Loop * loop,Marker visited)1364 void SimplifyStringBuilder::StringBuilderUsagesDFS(Inst *inst, Loop *loop, Marker visited)
1365 {
1366 // Recursively traverse current instruction users, and collect all the StringBuilder usages met
1367
1368 ASSERT(inst != nullptr);
1369 if (inst->GetBasicBlock()->GetLoop() != loop || inst->IsMarked(visited)) {
1370 return;
1371 }
1372
1373 inst->SetMarker(visited);
1374
1375 for (auto &user : inst->GetUsers()) {
1376 auto userInst = user.GetInst();
1377 if (userInst->IsPhi() && !userInst->IsMarked(visited)) {
1378 StringBuilderUsagesDFS(userInst, loop, visited);
1379 }
1380
1381 if (!IsStringBuilderAppend(userInst)) {
1382 continue;
1383 }
1384
1385 auto appendInstruction = userInst;
1386 ASSERT(appendInstruction->GetInputsCount() > 1);
1387 auto instance = appendInstruction->GetDataFlowInput(0);
1388 if (instance->GetBasicBlock()->GetLoop() == loop) {
1389 StringBuilderUsage usage {nullptr, nullptr, GetGraph()->GetAllocator()};
1390 MatchStringBuilderUsage(instance, usage);
1391
1392 if (usage.toStringCalls.size() != 1) {
1393 continue;
1394 }
1395
1396 if (!usage.toStringCalls[0]->IsMarked(visited)) {
1397 StringBuilderUsagesDFS(usage.toStringCalls[0], loop, visited);
1398 usages_.push_back(usage);
1399 }
1400 }
1401 }
1402 }
1403
GetStringBuilderUsagesPO(Inst * accValue)1404 const ArenaVector<SimplifyStringBuilder::StringBuilderUsage> &SimplifyStringBuilder::GetStringBuilderUsagesPO(
1405 Inst *accValue)
1406 {
1407 // Get all the StringBuilder usages under the phi accumulated value instruction data flow graph in post order (PO)
1408
1409 usages_.clear();
1410
1411 MarkerHolder usageMarker {GetGraph()};
1412 Marker visited = usageMarker.GetMarker();
1413
1414 StringBuilderUsagesDFS(accValue, accValue->GetBasicBlock()->GetLoop(), visited);
1415
1416 return usages_;
1417 }
1418
AllUsersAreVisitedAppendInstructions(Inst * inst,Marker appendInstructionVisited)1419 bool SimplifyStringBuilder::AllUsersAreVisitedAppendInstructions(Inst *inst, Marker appendInstructionVisited)
1420 {
1421 bool allUsersVisited = true;
1422 for (auto &user : inst->GetUsers()) {
1423 auto userInst = user.GetInst();
1424 if (userInst->IsSaveState()) {
1425 continue;
1426 }
1427 if (IsCheckCastWithoutUsers(userInst)) {
1428 continue;
1429 }
1430 allUsersVisited &= IsStringBuilderAppend(userInst);
1431 allUsersVisited &= userInst->IsMarked(appendInstructionVisited);
1432 }
1433 return allUsersVisited;
1434 }
1435
UpdateIntermediateValue(const StringBuilderUsage & usage,Inst * intermediateValue,Marker appendInstructionVisited)1436 Inst *SimplifyStringBuilder::UpdateIntermediateValue(const StringBuilderUsage &usage, Inst *intermediateValue,
1437 Marker appendInstructionVisited)
1438 {
1439 // Update intermediate value with toString-call of the current StringBuilder usage, if all its append-call users
1440 // were already visited
1441
1442 size_t usersCount = 0;
1443 bool allUsersVisited = true;
1444
1445 for (auto &user : intermediateValue->GetUsers()) {
1446 auto userInst = user.GetInst();
1447 if (userInst->IsSaveState()) {
1448 continue;
1449 }
1450
1451 if (userInst->IsPhi() && !userInst->HasUsers()) {
1452 continue;
1453 }
1454
1455 if (userInst->IsPhi() && !userInst->HasUsers()) {
1456 continue;
1457 }
1458
1459 if (userInst->IsPhi()) {
1460 ++usersCount;
1461 allUsersVisited &= AllUsersAreVisitedAppendInstructions(userInst, appendInstructionVisited);
1462 } else if (IsStringBuilderAppend(userInst)) {
1463 ++usersCount;
1464 allUsersVisited &= userInst->IsMarked(appendInstructionVisited);
1465 } else {
1466 break;
1467 }
1468 }
1469
1470 ASSERT(usage.toStringCalls.size() == 1);
1471 if (usersCount == 1) {
1472 intermediateValue = usage.toStringCalls[0];
1473 } else if (usersCount > 1 && allUsersVisited) {
1474 intermediateValue = usage.toStringCalls[0];
1475 for (auto &user : usage.toStringCalls[0]->GetUsers()) {
1476 auto userInst = user.GetInst();
1477 if (userInst->IsPhi() && userInst->HasUsers()) {
1478 intermediateValue = userInst;
1479 break;
1480 }
1481 }
1482 }
1483
1484 return intermediateValue;
1485 }
1486
MatchTemporaryInstruction(ConcatenationLoopMatch & match,ConcatenationLoopMatch::TemporaryInstructions & temp,Inst * appendInstruction,const Inst * accValue,Marker appendInstructionVisited)1487 bool SimplifyStringBuilder::MatchTemporaryInstruction(ConcatenationLoopMatch &match,
1488 ConcatenationLoopMatch::TemporaryInstructions &temp,
1489 Inst *appendInstruction, const Inst *accValue,
1490 Marker appendInstructionVisited)
1491 {
1492 // Arrange single append instruction to one of the two groups (substructures of ConcatenationLoopMatch):
1493 // 'temp' group - temporary instructions to be erased from loop
1494 // 'loop' group - append-call instructions to be kept inside loop
1495
1496 ASSERT(appendInstruction->GetInputsCount() > 1);
1497 auto appendArg = appendInstruction->GetDataFlowInput(1);
1498 if ((appendArg->IsPhi() && IsDataFlowInput(appendArg, temp.intermediateValue)) ||
1499 appendArg == temp.intermediateValue || appendArg == accValue) {
1500 // Append-call needs to be removed, if its argument is either accumulated value, or intermediate value;
1501 // or intermediate value is data flow input of argument
1502
1503 if (temp.appendAccValue == nullptr) {
1504 temp.appendAccValue = appendInstruction;
1505 } else {
1506 // Does not look like string concatenation pattern
1507 temp.Clear();
1508 return false;
1509 }
1510 appendInstruction->SetMarker(appendInstructionVisited);
1511 } else {
1512 if (temp.appendAccValue != nullptr) {
1513 // First appendee should be acc value
1514 temp.Clear();
1515 return false;
1516 }
1517 // Keep append-call inside loop otherwise
1518 match.loop.appendInstructions.push_back(appendInstruction);
1519 }
1520 return true;
1521 }
1522
MatchTemporaryInstructions(const StringBuilderUsage & usage,ConcatenationLoopMatch & match,Inst * accValue,Inst * intermediateValue,Marker appendInstructionVisited)1523 void SimplifyStringBuilder::MatchTemporaryInstructions(const StringBuilderUsage &usage, ConcatenationLoopMatch &match,
1524 Inst *accValue, Inst *intermediateValue,
1525 Marker appendInstructionVisited)
1526 {
1527 // Split all the instructions of a given StringBuilder usage into groups (substructures of ConcatenationLoopMatch):
1528 // 'temp' group - temporary instructions to be erased from loop
1529 // 'loop' group - append-call instructions to be kept inside loop
1530
1531 ConcatenationLoopMatch::TemporaryInstructions temp {};
1532 temp.intermediateValue = intermediateValue;
1533 temp.toStringCall = usage.toStringCalls[0];
1534 temp.instance = usage.instance;
1535 temp.ctorCall = usage.ctorCall;
1536
1537 for (auto appendInstruction : usage.appendInstructions) {
1538 bool isMatchStillValid =
1539 MatchTemporaryInstruction(match, temp, appendInstruction, accValue, appendInstructionVisited);
1540 if (!isMatchStillValid) {
1541 // Doesn't look like concatenation pattern. Clean entire match
1542 match.Clear();
1543 return;
1544 }
1545 }
1546
1547 if (!temp.IsEmpty()) {
1548 match.temp.push_back(temp);
1549 }
1550 }
1551
1552 // CC-OFFNXT(huge_depth) false positive
MatchHoistableInstructions(const StringBuilderUsage & usage,ConcatenationLoopMatch & match,Marker appendInstructionVisited)1553 Inst *SimplifyStringBuilder::MatchHoistableInstructions(const StringBuilderUsage &usage, ConcatenationLoopMatch &match,
1554 Marker appendInstructionVisited)
1555 {
1556 // Split all the instructions of a given StringBuilder usage into groups (substructures of ConcatenationLoopMatch):
1557 // 'preheader' group - instructions to be hoisted to preheader block
1558 // 'loop' group - append-call instructions to be kept inside loop
1559 // 'exit' group - instructions to be hoisted to post exit block
1560
1561 match.block = usage.instance->GetBasicBlock();
1562
1563 ASSERT(usage.instance->GetInputsCount() > 0);
1564 match.preheader.instance = usage.instance;
1565 match.preheader.ctorCall = usage.ctorCall;
1566 ASSERT(usage.toStringCalls.size() == 1);
1567 match.exit.toStringCall = usage.toStringCalls[0];
1568
1569 for (auto &user : usage.instance->GetUsers()) {
1570 auto userInst = SkipSingleUserCheckInstruction(user.GetInst());
1571 if (userInst->IsSaveState()) {
1572 continue;
1573 }
1574
1575 if (!IsStringBuilderAppend(userInst)) {
1576 continue;
1577 }
1578
1579 // Check if append-call needs to be hoisted or kept inside loop
1580 auto appendInstruction = userInst;
1581 ASSERT(appendInstruction->GetInputsCount() > 1);
1582 auto appendArg = appendInstruction->GetDataFlowInput(1);
1583 if (appendArg->IsPhi() && IsPhiAccumulatedValue(appendArg->CastToPhi())) {
1584 // Append-call needs to be hoisted, if its argument is accumulated value
1585 auto phiAppendArg = appendArg->CastToPhi();
1586 auto initialValue =
1587 phiAppendArg->GetPhiDataflowInput(usage.instance->GetBasicBlock()->GetLoop()->GetPreHeader());
1588 if (match.initialValue != nullptr || match.accValue != nullptr ||
1589 match.preheader.appendAccValue != nullptr) {
1590 // Does not look like string concatenation pattern
1591 match.Clear();
1592 break;
1593 }
1594
1595 match.initialValue = initialValue;
1596 match.accValue = phiAppendArg;
1597 match.preheader.appendAccValue = appendInstruction;
1598
1599 appendInstruction->SetMarker(appendInstructionVisited);
1600 } else {
1601 // Keep append-call inside loop otherwise
1602 match.loop.appendInstructions.push_back(appendInstruction);
1603 }
1604 }
1605
1606 // Initialize intermediate value with toString-call to be hoisted to post exit block
1607 return match.exit.toStringCall;
1608 }
1609
MatchLoopConcatenation(Loop * loop)1610 const ArenaVector<SimplifyStringBuilder::ConcatenationLoopMatch> &SimplifyStringBuilder::MatchLoopConcatenation(
1611 Loop *loop)
1612 {
1613 // Search loop for string concatenation patterns like the following:
1614 // > let str = initial_value: String
1615 // > for (...) {
1616 // > str += a0 + b0 + ...
1617 // > str += a1 + b2 + ...
1618 // > ...
1619 // > }
1620 // And fill ConcatenationLoopMatch structure with instructions from the pattern found
1621
1622 matches_.clear();
1623
1624 MarkerHolder appendInstructionMarker {GetGraph()};
1625 Marker appendInstructionVisited = appendInstructionMarker.GetMarker();
1626
1627 // Accumulated value (acc_value) is a phi-instruction holding concatenation result between loop iterations, and
1628 // final result after loop completes
1629 for (auto accValue : GetPhiAccumulatedValues(loop)) {
1630 // Intermediate value is an instruction holding concatenation result during loop iteration execution.
1631 // It is initialized with acc_value, and updated with either toString-calls, or other phi-instructions
1632 // (depending on the loop control flow and data flow)
1633 Inst *intermediateValue = accValue;
1634 ConcatenationLoopMatch match {GetGraph()->GetAllocator()};
1635
1636 // Get all the StringBuilders used to calculate current accumulated value (in PO)
1637 auto &usages = GetStringBuilderUsagesPO(accValue);
1638 // RPO traversal: walk through PO usages backwards
1639 for (auto usage = usages.rbegin(); usage != usages.rend(); ++usage) {
1640 if (usage->toStringCalls.size() != 1) {
1641 continue; // Unsupported: doesn't look like string concatenation pattern
1642 }
1643
1644 if (match.preheader.instance == nullptr) {
1645 // First StringBuilder instance are set to be hoisted
1646 intermediateValue = MatchHoistableInstructions(*usage, match, appendInstructionVisited);
1647 } else {
1648 // All other StringBuilder instances are set to be removed as temporary
1649 MatchTemporaryInstructions(*usage, match, accValue, intermediateValue, appendInstructionVisited);
1650 intermediateValue = UpdateIntermediateValue(*usage, intermediateValue, appendInstructionVisited);
1651 }
1652 }
1653
1654 if (IsInstanceHoistable(match) && IsToStringHoistable(match, appendInstructionVisited)) {
1655 matches_.push_back(match);
1656 }
1657
1658 // Reset markers
1659 if (match.preheader.appendAccValue != nullptr) {
1660 match.preheader.appendAccValue->ResetMarker(appendInstructionVisited);
1661 }
1662 for (auto &temp : match.temp) {
1663 if (temp.appendAccValue != nullptr) {
1664 temp.appendAccValue->ResetMarker(appendInstructionVisited);
1665 }
1666 }
1667 }
1668
1669 return matches_;
1670 }
1671
OptimizeStringConcatenation(Loop * loop)1672 void SimplifyStringBuilder::OptimizeStringConcatenation(Loop *loop)
1673 {
1674 // Optimize String Builder concatenation loops
1675
1676 // Process inner loops first
1677 for (auto innerLoop : loop->GetInnerLoops()) {
1678 OptimizeStringConcatenation(innerLoop);
1679 }
1680
1681 // Check if basic block for instructions to hoist exist
1682 // Alternative way maybe to create one
1683 if (loop->GetPreHeader() == nullptr) {
1684 return;
1685 }
1686
1687 auto preHeaderSaveState = FindPreHeaderSaveState(loop);
1688 if (preHeaderSaveState == nullptr) {
1689 return;
1690 }
1691
1692 // Check if basic block for instructions to hoist exist
1693 // Alternative way maybe to create one
1694 auto postExit = GetLoopPostExit(loop);
1695 if (postExit == nullptr) {
1696 return;
1697 }
1698
1699 auto postExitSaveState = FindFirstSaveState(postExit);
1700 ASSERT(postExitSaveState); // IR Builder must create empty save states for loop exits
1701
1702 for (auto &match : MatchLoopConcatenation(loop)) {
1703 ReconnectInstructions(match);
1704 HoistInstructionsToPreHeader(match, preHeaderSaveState);
1705 HoistInstructionsToPostExit(match, postExitSaveState);
1706 Cleanup(match);
1707
1708 isApplied_ = true;
1709 }
1710 Cleanup(loop);
1711 }
1712
CreateIntrinsicStringBuilderAppendStrings(const ConcatenationMatch & match,SaveStateInst * saveState)1713 IntrinsicInst *SimplifyStringBuilder::CreateIntrinsicStringBuilderAppendStrings(const ConcatenationMatch &match,
1714 SaveStateInst *saveState)
1715 {
1716 auto arg0 = match.appendIntrinsics[0U]->GetInput(1U).GetInst();
1717 auto arg1 = match.appendIntrinsics[1U]->GetInput(1U).GetInst();
1718
1719 switch (match.appendCount) {
1720 case 2U: {
1721 return CreateIntrinsic(
1722 GetGraph(), GetGraph()->GetRuntime()->GetStringBuilderAppendStringsIntrinsicId(match.appendCount),
1723 DataType::REFERENCE,
1724 {{match.instance, match.instance->GetType()},
1725 {arg0, arg0->GetType()},
1726 {arg1, arg1->GetType()},
1727 {saveState, saveState->GetType()}});
1728 }
1729 case 3U: {
1730 auto arg2 = match.appendIntrinsics[2U]->GetInput(1U).GetInst();
1731
1732 return CreateIntrinsic(
1733 GetGraph(), GetGraph()->GetRuntime()->GetStringBuilderAppendStringsIntrinsicId(match.appendCount),
1734 DataType::REFERENCE,
1735 {{match.instance, match.instance->GetType()},
1736 {arg0, arg0->GetType()},
1737 {arg1, arg1->GetType()},
1738 {arg2, arg2->GetType()},
1739 {saveState, saveState->GetType()}});
1740 }
1741 case 4U: {
1742 auto arg2 = match.appendIntrinsics[2U]->GetInput(1U).GetInst();
1743 auto arg3 = match.appendIntrinsics[3U]->GetInput(1U).GetInst();
1744
1745 return CreateIntrinsic(
1746 GetGraph(), GetGraph()->GetRuntime()->GetStringBuilderAppendStringsIntrinsicId(match.appendCount),
1747 DataType::REFERENCE,
1748 {{match.instance, match.instance->GetType()},
1749 {arg0, arg0->GetType()},
1750 {arg1, arg1->GetType()},
1751 {arg2, arg2->GetType()},
1752 {arg3, arg3->GetType()},
1753 {saveState, saveState->GetType()}});
1754 }
1755 default:
1756 UNREACHABLE();
1757 }
1758 }
1759
ReplaceWithAppendIntrinsic(const ConcatenationMatch & match)1760 void SimplifyStringBuilder::ReplaceWithAppendIntrinsic(const ConcatenationMatch &match)
1761 {
1762 COMPILER_LOG(DEBUG, SIMPLIFY_SB) << match.appendCount << " consecutive append string intrinsics found IDs: ";
1763 for (size_t index = 0; index < match.appendCount; ++index) {
1764 COMPILER_LOG(DEBUG, SIMPLIFY_SB) << "\t" << match.appendIntrinsics[index]->GetId();
1765 }
1766 COMPILER_LOG(DEBUG, SIMPLIFY_SB) << "for instance id=" << match.instance->GetId() << " ("
1767 << GetOpcodeString(match.instance->GetOpcode()) << "), applying";
1768
1769 auto lastAppendIntrinsic = match.appendIntrinsics[match.appendCount - 1U];
1770 auto appendNIntrinsic = CreateIntrinsicStringBuilderAppendStrings(
1771 match, CopySaveState(GetGraph(), lastAppendIntrinsic->GetSaveState()));
1772
1773 InsertBeforeWithSaveState(appendNIntrinsic, lastAppendIntrinsic);
1774
1775 for (size_t index = 0; index < match.appendCount; ++index) {
1776 auto appendIntrinsic = match.appendIntrinsics[index];
1777 FixBrokenSaveStates(appendIntrinsic->GetDataFlowInput(1), appendNIntrinsic);
1778 appendIntrinsic->ClearFlag(inst_flags::NO_DCE);
1779 }
1780
1781 COMPILER_LOG(DEBUG, SIMPLIFY_SB) << "Replaced with append" << match.appendCount
1782 << " intrinsic id=" << appendNIntrinsic->GetId();
1783
1784 isApplied_ = true;
1785 }
1786
HasPhiOfStringBuilders(BasicBlock * block)1787 bool HasPhiOfStringBuilders(BasicBlock *block)
1788 {
1789 for (auto phi : block->PhiInsts()) {
1790 MarkerHolder visited {block->GetGraph()};
1791 if (HasInputPhiRecursively(phi, visited.GetMarker(),
1792 [](auto &input) { return IsStringBuilderInstance(input.GetInst()); })) {
1793 return true;
1794 }
1795 }
1796 return false;
1797 }
1798
1799 // CC-OFFNXT(huge_depth) false positive
CollectStringBuilderCalls(BasicBlock * block)1800 const SimplifyStringBuilder::StringBuilderCallsMap &SimplifyStringBuilder::CollectStringBuilderCalls(BasicBlock *block)
1801 {
1802 auto &calls = stringBuilderCalls_;
1803 calls.clear();
1804
1805 // Skip blocks with Phi of String Builders
1806 if (HasPhiOfStringBuilders(block)) {
1807 return calls;
1808 }
1809
1810 auto current = calls.end();
1811 for (auto inst : block->Insts()) {
1812 if (inst->IsSaveState() || inst->IsCheck()) {
1813 continue;
1814 }
1815
1816 for (size_t index = 0; index < inst->GetInputsCount(); ++index) {
1817 auto instance = inst->GetDataFlowInput(index);
1818 if (!IsStringBuilderInstance(instance)) {
1819 continue;
1820 }
1821
1822 if (current->first != instance) {
1823 current = calls.find(instance);
1824 }
1825 if (current == calls.end()) {
1826 current = calls.emplace(instance, InstVector {GetGraph()->GetLocalAllocator()->Adapter()}).first;
1827 }
1828 current->second.push_back(inst);
1829 }
1830 }
1831 return calls;
1832 }
1833
CountStringBuilderAppendString(const InstVector & calls,size_t from)1834 size_t CountStringBuilderAppendString(const InstVector &calls, size_t from)
1835 {
1836 auto to = std::min(from + SB_APPEND_STRING_MAX_ARGS, calls.size());
1837 for (auto index = from; index < to; ++index) {
1838 if (IsIntrinsicStringBuilderAppendString(calls[index])) {
1839 continue;
1840 }
1841 return index;
1842 }
1843 return to;
1844 }
1845
ReplaceWithAppendIntrinsic(Inst * instance,const InstVector & calls,size_t from,size_t to)1846 void SimplifyStringBuilder::ReplaceWithAppendIntrinsic(Inst *instance, const InstVector &calls, size_t from, size_t to)
1847 {
1848 auto appendCount = to - from;
1849 ASSERT(0 < appendCount && appendCount <= SB_APPEND_STRING_MAX_ARGS);
1850 if (appendCount == 1) {
1851 COMPILER_LOG(DEBUG, SIMPLIFY_SB) << "One consecutive append string intrinsic found id=" << calls[from]->GetId()
1852 << " for instance id=" << instance->GetId() << " ("
1853 << GetOpcodeString(instance->GetOpcode()) << "), skipping";
1854 } else {
1855 ConcatenationMatch match {instance, nullptr, nullptr, appendCount};
1856 for (size_t index = 0; index < appendCount; ++index) {
1857 match.appendIntrinsics[index] = calls[from + index]->CastToIntrinsic();
1858 }
1859 ReplaceWithAppendIntrinsic(match);
1860 }
1861 }
1862
OptimizeStringBuilderAppendChain(BasicBlock * block)1863 void SimplifyStringBuilder::OptimizeStringBuilderAppendChain(BasicBlock *block)
1864 {
1865 // StringBuilder::append(s0, s1, ...) implemented with Irtoc functions with number of arguments more than 4, and
1866 // requires pre/post-write barriers to be supported. AARCH32 does not support neither barriers, nor so much
1867 // arguments in Irtoc functions.
1868 if (!GetGraph()->SupportsIrtocBarriers()) {
1869 return;
1870 }
1871
1872 isApplied_ |= BreakStringBuilderAppendChains(block);
1873
1874 for (auto &[instance, calls] : CollectStringBuilderCalls(block)) {
1875 for (size_t from = 0; from < calls.size();) {
1876 if (!IsIntrinsicStringBuilderAppendString(calls[from])) {
1877 ++from;
1878 continue;
1879 }
1880
1881 size_t to = CountStringBuilderAppendString(calls, from);
1882 ReplaceWithAppendIntrinsic(instance, calls, from, to);
1883
1884 ASSERT(from < to);
1885 from = to;
1886 }
1887 }
1888 }
1889
1890 // CC-OFFNXT(huge_depth) false positive
CollectStringBuilderFirstCalls(BasicBlock * block)1891 void SimplifyStringBuilder::CollectStringBuilderFirstCalls(BasicBlock *block)
1892 {
1893 Inst *instance = nullptr;
1894 auto calls = stringBuilderFirstLastCalls_.end();
1895 for (auto inst : block->Insts()) {
1896 if (IsStringBuilderInstance(inst)) {
1897 instance = inst;
1898 calls = stringBuilderFirstLastCalls_.find(instance);
1899 if (calls == stringBuilderFirstLastCalls_.end()) {
1900 calls = stringBuilderFirstLastCalls_.emplace(instance, InstPair {}).first;
1901 }
1902 }
1903
1904 if (IsStringBuilderAppend(inst) && inst->GetDataFlowInput(0) == instance) {
1905 auto &firstCall = calls->second.first;
1906 if (firstCall == nullptr) {
1907 firstCall = inst;
1908 }
1909 }
1910 }
1911 }
1912
1913 // CC-OFFNXT(huge_depth) false positive
CollectStringBuilderLastCalls(BasicBlock * block)1914 void SimplifyStringBuilder::CollectStringBuilderLastCalls(BasicBlock *block)
1915 {
1916 for (auto inst : block->InstsReverse()) {
1917 if (inst->IsSaveState() || inst->IsCheck()) {
1918 continue;
1919 }
1920
1921 if (!IsStringBuilderToString(inst)) {
1922 continue;
1923 }
1924
1925 auto inputInst = inst->GetDataFlowInput(0);
1926 if (inputInst->IsSaveState()) {
1927 continue;
1928 }
1929
1930 auto instance = inputInst;
1931 if (!IsStringBuilderInstance(instance)) {
1932 continue;
1933 }
1934
1935 auto calls = stringBuilderFirstLastCalls_.find(instance);
1936 if (calls == stringBuilderFirstLastCalls_.end()) {
1937 calls = stringBuilderFirstLastCalls_.emplace(instance, InstPair {}).first;
1938 }
1939 auto &lastCall = calls->second.second;
1940 if (lastCall == nullptr) {
1941 lastCall = inst;
1942 }
1943 }
1944 }
1945
CollectStringBuilderFirstLastCalls()1946 void SimplifyStringBuilder::CollectStringBuilderFirstLastCalls()
1947 {
1948 // For each SB in graph, find its first (append) call and last (toString) call
1949 stringBuilderFirstLastCalls_.clear();
1950
1951 // Traverse CFG in RPO
1952 for (auto block : GetGraph()->GetBlocksRPO()) {
1953 isApplied_ |= BreakStringBuilderAppendChains(block);
1954 CollectStringBuilderFirstCalls(block);
1955 CollectStringBuilderLastCalls(block);
1956 }
1957 }
1958
CanMergeStringBuilders(Inst * instance,const InstPair & instanceCalls,Inst * inputInstance)1959 bool SimplifyStringBuilder::CanMergeStringBuilders(Inst *instance, const InstPair &instanceCalls, Inst *inputInstance)
1960 {
1961 if (instance == inputInstance) {
1962 return false; // Skip instance.append(instance.toString()) case
1963 }
1964
1965 auto inputInstanceCalls = stringBuilderFirstLastCalls_.find(inputInstance);
1966 if (inputInstanceCalls == stringBuilderFirstLastCalls_.end()) {
1967 return false;
1968 }
1969
1970 auto &[inputInstanceFirstAppendCall, inputInstanceLastToStringCall] = inputInstanceCalls->second;
1971 if (inputInstanceFirstAppendCall == nullptr || inputInstanceLastToStringCall == nullptr) {
1972 return false; // Unsupported case: doesn't look like concatenation pattern
1973 }
1974
1975 for (auto &user : instance->GetUsers()) {
1976 auto userInst = user.GetInst();
1977 if (IsMethodStringBuilderConstructorWithCharArrayArg(userInst) ||
1978 IsMethodStringBuilderConstructorWithStringArg(userInst)) {
1979 // Does not look like string concatenation pattern
1980 return false;
1981 }
1982 }
1983
1984 auto instanceFirstCall = instanceCalls.first;
1985
1986 if (instance->GetBasicBlock() != instanceFirstCall->GetBasicBlock()) {
1987 // Does not look like string concatenation pattern
1988 return false;
1989 }
1990
1991 // Check if 'inputInstance' toString call comes after any 'inputInstance' append call
1992 for (auto &user : inputInstance->GetUsers()) {
1993 auto userInst = SkipSingleUserCheckInstruction(user.GetInst());
1994 if (!IsStringBuilderAppend(userInst)) {
1995 continue;
1996 }
1997
1998 if (inputInstanceLastToStringCall->IsDominate(userInst)) {
1999 return false;
2000 }
2001 }
2002
2003 // Check if all 'inputInstance' calls comes before any 'instance' call
2004 return inputInstanceLastToStringCall->IsDominate(instanceFirstCall);
2005 }
2006
Cleanup(Inst * instance,Inst * instanceFirstAppendCall,Inst * inputInstanceToStringCall)2007 void SimplifyStringBuilder::Cleanup(Inst *instance, Inst *instanceFirstAppendCall, Inst *inputInstanceToStringCall)
2008 {
2009 // Mark 'instance' constructor as dead
2010 for (auto &user : instance->GetUsers()) {
2011 auto userInst = user.GetInst();
2012 if (!IsMethodStringBuilderDefaultConstructor(userInst)) {
2013 continue;
2014 }
2015 userInst->ClearFlag(inst_flags::NO_DCE);
2016 }
2017
2018 // Mark 'instance' append call as dead
2019 instanceFirstAppendCall->ClearFlag(inst_flags::NO_DCE);
2020
2021 // Mark 'inputInstance' toString call as dead
2022 inputInstanceToStringCall->ClearFlag(inst_flags::NO_DCE);
2023 for (auto &user : inputInstanceToStringCall->GetUsers()) {
2024 auto userInst = user.GetInst();
2025 if (!IsCheckCastWithoutUsers(userInst)) {
2026 continue;
2027 }
2028 userInst->ClearFlag(inst_flags::NO_DCE);
2029 }
2030
2031 // Mark 'instance' itself as dead
2032 instance->ClearFlag(inst_flags::NO_DCE);
2033
2034 // Remove instructions marked dead from save states
2035 RemoveFromSaveStateInputs(instance);
2036 RemoveFromSaveStateInputs(instanceFirstAppendCall);
2037
2038 // Remove inputInstance.toString() call from save states only if it is not used anywhere else
2039 if (!HasUser(inputInstanceToStringCall, [instanceFirstAppendCall](auto &user) {
2040 auto userInst = user.GetInst();
2041 auto isSaveState = userInst->IsSaveState();
2042 auto isAppend = userInst == instanceFirstAppendCall;
2043 return !isSaveState && !isAppend;
2044 })) {
2045 RemoveFromSaveStateInputs(inputInstanceToStringCall);
2046 }
2047 }
2048
FixBrokenSaveStatesForStringBuilderCalls(Inst * instance)2049 void SimplifyStringBuilder::FixBrokenSaveStatesForStringBuilderCalls(Inst *instance)
2050 {
2051 for (auto &user : instance->GetUsers()) {
2052 auto userInst = SkipSingleUserCheckInstruction(user.GetInst());
2053 if (userInst->IsSaveState()) {
2054 continue;
2055 }
2056
2057 if (IsStringBuilderAppend(userInst)) {
2058 ASSERT(userInst->GetInputsCount() > 1U);
2059 auto appendArg = userInst->GetDataFlowInput(1U);
2060 FixBrokenSaveStates(appendArg, userInst);
2061 }
2062
2063 FixBrokenSaveStates(instance, userInst);
2064 }
2065 }
2066
CollectStringBuilderChainCalls(Inst * instance,Inst * inputInstance)2067 void SimplifyStringBuilder::CollectStringBuilderChainCalls(Inst *instance, Inst *inputInstance)
2068 {
2069 ASSERT(stringBuilderCalls_.find(inputInstance) == stringBuilderCalls_.end());
2070
2071 // Check if 'instance' already in calls map
2072 auto calls = stringBuilderCalls_.find(instance);
2073 if (calls == stringBuilderCalls_.end()) {
2074 // If not, add 'inputInstance' with empty instructions vector to a map
2075 calls = stringBuilderCalls_
2076 .insert(std::make_pair(inputInstance, InstVector {GetGraph()->GetAllocator()->Adapter()}))
2077 .first;
2078 } else {
2079 // If yes, do the following:
2080 // 1. Add 'inputInstance' with instructions vector taken from 'instance'
2081 // 2. Remove 'instance' from a map
2082 calls = stringBuilderCalls_.insert(std::make_pair(inputInstance, std::move(calls->second))).first;
2083 stringBuilderCalls_.erase(instance);
2084 }
2085
2086 // Map 'instance' users to 'inputInstance'
2087 for (auto &user : instance->GetUsers()) {
2088 auto userInst = user.GetInst();
2089 // Skip save states
2090 if (userInst->IsSaveState()) {
2091 continue;
2092 }
2093
2094 // Skip StringBuilder constructors
2095 if (IsMethodStringBuilderDefaultConstructor(userInst) ||
2096 IsMethodStringBuilderConstructorWithStringArg(userInst) ||
2097 IsMethodStringBuilderConstructorWithCharArrayArg(userInst)) {
2098 continue;
2099 }
2100
2101 calls->second.push_back(userInst);
2102 }
2103 }
2104
CollectStringBuilderChainCalls()2105 SimplifyStringBuilder::StringBuilderCallsMap &SimplifyStringBuilder::CollectStringBuilderChainCalls()
2106 {
2107 CollectStringBuilderFirstLastCalls();
2108 stringBuilderCalls_.clear();
2109
2110 // Traverse CFG in PO
2111 auto &blocksRPO = GetGraph()->GetBlocksRPO();
2112 for (auto block = blocksRPO.rbegin(); block != blocksRPO.rend(); ++block) {
2113 // Traverse 'block' backwards
2114 for (auto instance : (*block)->InstsReverse()) {
2115 if (!IsStringBuilderInstance(instance)) {
2116 continue;
2117 }
2118
2119 auto instanceCalls = stringBuilderFirstLastCalls_.find(instance);
2120 if (instanceCalls == stringBuilderFirstLastCalls_.end()) {
2121 continue;
2122 }
2123
2124 auto &instanceFirstLastCalls = instanceCalls->second;
2125 auto &[instanceFirstAppendCall, instanceLastToStringCall] = instanceFirstLastCalls;
2126 if (instanceFirstAppendCall == nullptr || instanceLastToStringCall == nullptr) {
2127 continue; // Unsupported case: doesn't look like concatenation pattern
2128 }
2129
2130 if (!IsStringBuilderAppend(instanceFirstAppendCall)) {
2131 continue;
2132 }
2133
2134 auto inputInstanceToStringCall = instanceFirstAppendCall->GetDataFlowInput(1);
2135 if (!IsStringBuilderToString(inputInstanceToStringCall)) {
2136 continue;
2137 }
2138
2139 if (instanceFirstAppendCall->GetDataFlowInput(1) != inputInstanceToStringCall) {
2140 continue; // Allow only cases like: instance.append(inputInstace.toString())
2141 }
2142
2143 ASSERT(inputInstanceToStringCall->GetInputsCount() > 1);
2144 auto inputInstance = inputInstanceToStringCall->GetDataFlowInput(0);
2145 if (!IsStringBuilderInstance(inputInstance)) {
2146 continue;
2147 }
2148
2149 if (!CanMergeStringBuilders(instance, instanceFirstLastCalls, inputInstance)) {
2150 continue;
2151 }
2152
2153 Cleanup(instance, instanceFirstAppendCall, inputInstanceToStringCall);
2154 CollectStringBuilderChainCalls(instance, inputInstance);
2155 }
2156 }
2157
2158 return stringBuilderCalls_;
2159 }
2160
OptimizeStringBuilderChain()2161 void SimplifyStringBuilder::OptimizeStringBuilderChain()
2162 {
2163 /*
2164 Merges consecutive String Builders into one String Builder if possible
2165 Example of string concatenation (TS):
2166 let a: String = ...
2167 a += ...;
2168 a += ...;
2169 let result = a;
2170
2171 Frontend generates the following SB-equivalent code for the example above:
2172 let inputInstance = new StringBuilder()
2173 inputInstance.append(...) // append calls for 'inputInstance'
2174 ...
2175 let instance = new StringBuilder()
2176 instance.append(inputInstance.toString()) // first call to append for 'instance'
2177 // 'inputInstance' not used beyond this point
2178 instance.append(...) // append calls for 'instance'
2179 ...
2180 let result = instance.toString()
2181
2182 The algorithm transforms it into:
2183 let inputInstance = new StringBuilder()
2184 inputInstance.append(...) // append calls for 'inputInstance'
2185 ...
2186 inputInstance.append(...) // append calls for 'instance' replaced by 'inputInstance'
2187 ...
2188 let result = inputInstance.toString()
2189
2190 Note: arbirtary length of String Builder chain supported
2191
2192 The algorithm works on SBs, but not on strings themselves, thus the following limitations assumed:
2193 1) all SBs must be created via default constructor,
2194 2) call to append for 'instance' SB with the input of inputInstance.toString() must be the first,
2195 3) 'inputInstance' must not be used after instance.append(inputInstance.toString()) call.
2196 Those limitations fully match SB patterns of string concatenation.
2197 */
2198
2199 for (auto &instanceCalls : CollectStringBuilderChainCalls()) {
2200 auto inputInstance = instanceCalls.first;
2201 auto &calls = instanceCalls.second;
2202
2203 for (auto call : calls) {
2204 // Switch call to new instance only if it is not marked for removal
2205 if (call->GetFlag(inst_flags::NO_DCE)) {
2206 call->SetInput(0U, inputInstance);
2207 }
2208 }
2209
2210 FixBrokenSaveStatesForStringBuilderCalls(inputInstance);
2211
2212 isApplied_ = true;
2213 }
2214 }
2215
2216 } // namespace ark::compiler
2217