1 /**
2 * Copyright (c) 2024-2025 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 "optimize_string_concat.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/datatype.h"
25 #include "optimizer/ir/graph.h"
26 #include "optimizer/ir/inst.h"
27
28 #include "optimizer/ir/runtime_interface.h"
29 #include "optimizer/optimizations/cleanup.h"
30 #include "optimizer/optimizations/string_builder_utils.h"
31
32 namespace ark::compiler {
33
OptimizeStringConcat(Graph * graph)34 OptimizeStringConcat::OptimizeStringConcat(Graph *graph)
35 : Optimization(graph), arrayElements_ {graph->GetAllocator()->Adapter()}
36 {
37 }
38
GetStringBuilderClassId(Graph * graph)39 RuntimeInterface::IdType GetStringBuilderClassId(Graph *graph)
40 {
41 auto runtime = graph->GetRuntime();
42 auto klass = runtime->GetStringBuilderClass();
43 return klass == nullptr ? 0 : runtime->GetClassIdWithinFile(graph->GetMethod(), klass);
44 }
45
RunImpl()46 bool OptimizeStringConcat::RunImpl()
47 {
48 bool isApplied = false;
49
50 if (GetStringBuilderClassId(GetGraph()) == 0) {
51 COMPILER_LOG(WARNING, OPTIMIZE_STRING_CONCAT) << "StringBuilder class not found";
52 return isApplied;
53 }
54
55 if (GetGraph()->IsAotMode()) {
56 // NOTE(mivanov): Creating StringBuilder.ctor calls in AOT mode not yet supported
57 return isApplied;
58 }
59
60 for (auto block : GetGraph()->GetBlocksRPO()) {
61 for (auto inst : block->Insts()) {
62 if (!IsMethodStringConcat(inst)) {
63 continue;
64 }
65
66 ReplaceStringConcatWithStringBuilderAppend(inst);
67 isApplied = true;
68 }
69 }
70
71 COMPILER_LOG(DEBUG, OPTIMIZE_STRING_CONCAT) << "Optimize String.concat complete";
72
73 if (isApplied) {
74 GetGraph()->RunPass<compiler::Cleanup>();
75 }
76
77 return isApplied;
78 }
79
InvalidateAnalyses()80 void OptimizeStringConcat::InvalidateAnalyses()
81 {
82 GetGraph()->InvalidateAnalysis<BoundsAnalysis>();
83 GetGraph()->InvalidateAnalysis<AliasAnalysis>();
84 }
85
CreateInstructionStringBuilderInstance(Graph * graph,uint32_t pc,SaveStateInst * saveState)86 Inst *CreateInstructionStringBuilderInstance(Graph *graph, uint32_t pc, SaveStateInst *saveState)
87 {
88 auto runtime = graph->GetRuntime();
89 auto method = graph->GetMethod();
90
91 auto classId = GetStringBuilderClassId(graph);
92 ASSERT(classId != 0);
93 auto loadClass =
94 graph->CreateInstLoadAndInitClass(DataType::REFERENCE, pc, CopySaveState(graph, saveState),
95 TypeIdMixin {classId, method}, runtime->ResolveType(method, classId));
96 auto newObject = graph->CreateInstNewObject(DataType::REFERENCE, pc, loadClass, CopySaveState(graph, saveState),
97 TypeIdMixin {classId, method});
98
99 return newObject;
100 }
101
CreateStringBuilderAppendStringIntrinsic(Graph * graph,Inst * instance,Inst * arg,SaveStateInst * saveState)102 IntrinsicInst *CreateStringBuilderAppendStringIntrinsic(Graph *graph, Inst *instance, Inst *arg,
103 SaveStateInst *saveState)
104 {
105 auto appendIntrinsic = graph->CreateInstIntrinsic(graph->GetRuntime()->GetStringBuilderAppendStringsIntrinsicId(1));
106 ASSERT(appendIntrinsic->RequireState());
107
108 appendIntrinsic->SetType(DataType::REFERENCE);
109 auto saveStateClone = CopySaveState(graph, saveState);
110 appendIntrinsic->SetInputs(
111 graph->GetAllocator(),
112 {{instance, instance->GetType()}, {arg, arg->GetType()}, {saveStateClone, saveStateClone->GetType()}});
113
114 return appendIntrinsic;
115 }
116
CreateStringBuilderToStringIntrinsic(Graph * graph,Inst * instance,SaveStateInst * saveState)117 IntrinsicInst *CreateStringBuilderToStringIntrinsic(Graph *graph, Inst *instance, SaveStateInst *saveState)
118 {
119 auto toStringCall = graph->CreateInstIntrinsic(graph->GetRuntime()->GetStringBuilderToStringIntrinsicId());
120 ASSERT(toStringCall->RequireState());
121
122 toStringCall->SetType(DataType::REFERENCE);
123 auto saveStateClone = CopySaveState(graph, saveState);
124 toStringCall->SetInputs(graph->GetAllocator(),
125 {{instance, instance->GetType()}, {saveStateClone, saveStateClone->GetType()}});
126
127 return toStringCall;
128 }
129
CreateStringBuilderDefaultConstructorCall(Graph * graph,Inst * instance,SaveStateInst * saveState)130 CallInst *CreateStringBuilderDefaultConstructorCall(Graph *graph, Inst *instance, SaveStateInst *saveState)
131 {
132 auto runtime = graph->GetRuntime();
133 auto method = runtime->GetStringBuilderDefaultConstructor();
134 auto methodId = runtime->GetMethodId(method);
135
136 auto ctorCall = graph->CreateInstCallStatic(DataType::VOID, instance->GetPc(), methodId, method);
137 ASSERT(ctorCall->RequireState());
138
139 auto saveStateClone = CopySaveState(graph, saveState);
140 ctorCall->SetInputs(graph->GetAllocator(),
141 {{instance, instance->GetType()}, {saveStateClone, saveStateClone->GetType()}});
142
143 return ctorCall;
144 }
145
CreateLoadArray(Graph * graph,Inst * array,Inst * index)146 Inst *CreateLoadArray(Graph *graph, Inst *array, Inst *index)
147 {
148 return graph->CreateInstLoadArray(DataType::REFERENCE, array->GetPc(), array, index);
149 }
150
CreateLoadArray(Graph * graph,Inst * array,uint64_t index)151 Inst *CreateLoadArray(Graph *graph, Inst *array, uint64_t index)
152 {
153 return CreateLoadArray(graph, array, graph->FindOrCreateConstant(index));
154 }
155
CreateLenArray(Graph * graph,Inst * newArray)156 Inst *CreateLenArray(Graph *graph, Inst *newArray)
157 {
158 return graph->CreateInstLenArray(DataType::INT32, newArray->GetPc(), newArray);
159 }
160
FixBrokenSaveStates(Inst * source,Inst * target)161 void OptimizeStringConcat::FixBrokenSaveStates(Inst *source, Inst *target)
162 {
163 if (source->IsMovableObject()) {
164 ssb_.SearchAndCreateMissingObjInSaveState(GetGraph(), source, target);
165 }
166 }
167
CreateAppendArgsIntrinsic(Inst * instance,Inst * arg,SaveStateInst * saveState)168 void OptimizeStringConcat::CreateAppendArgsIntrinsic(Inst *instance, Inst *arg, SaveStateInst *saveState)
169 {
170 auto appendIntrinsic = CreateStringBuilderAppendStringIntrinsic(GetGraph(), instance, arg, saveState);
171 InsertBeforeWithInputs(appendIntrinsic, saveState);
172
173 FixBrokenSaveStates(arg, appendIntrinsic);
174 FixBrokenSaveStates(instance, appendIntrinsic);
175
176 COMPILER_LOG(DEBUG, OPTIMIZE_STRING_CONCAT)
177 << "Insert StringBuilder.append intrinsic (id=" << appendIntrinsic->GetId() << ")";
178 }
179
CreateAppendArgsIntrinsics(Inst * instance,SaveStateInst * saveState)180 void OptimizeStringConcat::CreateAppendArgsIntrinsics(Inst *instance, SaveStateInst *saveState)
181 {
182 for (auto arg : arrayElements_) {
183 CreateAppendArgsIntrinsic(instance, arg, saveState);
184 }
185 }
186
CreateAppendArgsIntrinsics(Inst * instance,Inst * args,uint64_t arrayLengthValue,SaveStateInst * saveState)187 void OptimizeStringConcat::CreateAppendArgsIntrinsics(Inst *instance, Inst *args, uint64_t arrayLengthValue,
188 SaveStateInst *saveState)
189 {
190 for (uint64_t index = 0; index < arrayLengthValue; ++index) {
191 auto arg = CreateLoadArray(GetGraph(), args, index);
192 CreateAppendArgsIntrinsic(instance, arg, saveState);
193 }
194 }
195
CreateSafePoint(Graph * graph,uint32_t pc,SaveStateInst * saveState)196 Inst *CreateSafePoint(Graph *graph, uint32_t pc, SaveStateInst *saveState)
197 {
198 ASSERT(saveState != nullptr);
199 auto safePoint =
200 graph->CreateInstSafePoint(pc, graph->GetMethod(), saveState->GetCallerInst(), saveState->GetInliningDepth());
201
202 for (size_t index = 0; index < saveState->GetInputsCount(); ++index) {
203 safePoint->AppendInput(saveState->GetInput(index));
204 safePoint->SetVirtualRegister(index, saveState->GetVirtualRegister(index));
205 }
206
207 return safePoint;
208 }
209
CreateAppendArgsLoop(Inst * instance,Inst * str,Inst * args,LengthMethodInst * arrayLength,Inst * concatCall)210 BasicBlock *OptimizeStringConcat::CreateAppendArgsLoop(Inst *instance, Inst *str, Inst *args,
211 LengthMethodInst *arrayLength, Inst *concatCall)
212 {
213 auto preHeader = concatCall->GetBasicBlock();
214 auto postExit = preHeader->SplitBlockAfterInstruction(concatCall, false);
215 auto saveState = concatCall->GetSaveState();
216
217 // Create loop CFG
218 auto header = GetGraph()->CreateEmptyBlock(preHeader);
219 auto backEdge = GetGraph()->CreateEmptyBlock(preHeader);
220 preHeader->AddSucc(header);
221 header->AddSucc(postExit);
222 header->AddSucc(backEdge);
223 backEdge->AddSucc(header);
224
225 // Declare loop variables
226 auto start = GetGraph()->FindOrCreateConstant(0);
227 auto stop = arrayLength;
228 auto step = GetGraph()->FindOrCreateConstant(1);
229
230 auto pc = instance->GetPc();
231
232 // Build header
233 auto induction = GetGraph()->CreateInstPhi(DataType::INT32, pc);
234 auto safePoint = CreateSafePoint(GetGraph(), pc, saveState);
235 auto compare =
236 GetGraph()->CreateInstCompare(DataType::BOOL, pc, stop, induction, DataType::INT32, ConditionCode::CC_LE);
237 auto ifImm = GetGraph()->CreateInstIfImm(DataType::BOOL, pc, compare, 0, DataType::BOOL, ConditionCode::CC_NE);
238 header->AppendPhi(induction);
239 header->AppendInsts({
240 safePoint,
241 compare,
242 ifImm,
243 });
244
245 // Build back edge
246 auto arg = CreateLoadArray(GetGraph(), args, induction);
247 auto appendIntrinsic = CreateStringBuilderAppendStringIntrinsic(GetGraph(), instance, arg, saveState);
248 auto add = GetGraph()->CreateInstAdd(DataType::INT32, pc, induction, step);
249 backEdge->AppendInsts({
250 arg,
251 appendIntrinsic->GetSaveState(),
252 appendIntrinsic,
253 add,
254 });
255
256 // Connect loop induction variable inputs
257 induction->AppendInput(start);
258 induction->AppendInput(add);
259
260 FixBrokenSaveStates(str, appendIntrinsic);
261 FixBrokenSaveStates(args, appendIntrinsic);
262 FixBrokenSaveStates(arg, appendIntrinsic);
263 FixBrokenSaveStates(instance, appendIntrinsic);
264
265 COMPILER_LOG(DEBUG, OPTIMIZE_STRING_CONCAT)
266 << "Insert StringBuilder.append intrinsic (id=" << appendIntrinsic->GetId() << ")";
267
268 return postExit;
269 }
270
HasStoreArrayUsersOnly(Inst * newArray,Inst * removable)271 bool OptimizeStringConcat::HasStoreArrayUsersOnly(Inst *newArray, Inst *removable)
272 {
273 ASSERT(newArray->GetOpcode() == Opcode::NewArray);
274
275 MarkerHolder visited {newArray->GetBasicBlock()->GetGraph()};
276 bool found = HasUserRecursively(newArray, visited.GetMarker(), [newArray, removable](auto &user) {
277 auto userInst = user.GetInst();
278 auto isSaveState = userInst->IsSaveState();
279 auto isCheck = userInst->IsCheck();
280 auto isStoreArray = userInst->GetOpcode() == Opcode::StoreArray && userInst->GetDataFlowInput(0) == newArray;
281 bool isRemovable = userInst == removable;
282 return !isSaveState && !isCheck && !isStoreArray && !isRemovable;
283 });
284
285 ResetUserMarkersRecursively(newArray, visited.GetMarker());
286 return !found;
287 }
288
ReplaceStringConcatWithStringBuilderAppend(Inst * concatCall)289 void OptimizeStringConcat::ReplaceStringConcatWithStringBuilderAppend(Inst *concatCall)
290 {
291 // Input:
292 // let result = str.concat(...args)
293 //
294 // Output:
295 // let instance = new StringBuilder(str)
296 // instance.append(args[0])
297 // ...
298 // instance.append(args[args.length-1])
299 // let result = instance.toString()
300
301 ASSERT(concatCall->GetInputsCount() > 1);
302
303 auto str = concatCall->GetDataFlowInput(0);
304 auto args = concatCall->GetDataFlowInput(1);
305
306 auto instance = CreateInstructionStringBuilderInstance(GetGraph(), concatCall->GetPc(), concatCall->GetSaveState());
307 InsertBeforeWithInputs(instance, concatCall->GetSaveState());
308
309 auto ctorCall = CreateStringBuilderDefaultConstructorCall(GetGraph(), instance, concatCall->GetSaveState());
310 InsertBeforeWithSaveState(ctorCall, concatCall->GetSaveState());
311 auto appendArgIntrinsic =
312 CreateStringBuilderAppendStringIntrinsic(GetGraph(), instance, str, concatCall->GetSaveState());
313 InsertBeforeWithSaveState(appendArgIntrinsic, concatCall->GetSaveState());
314 FixBrokenSaveStates(instance, appendArgIntrinsic);
315 FixBrokenSaveStates(str, appendArgIntrinsic);
316
317 COMPILER_LOG(DEBUG, OPTIMIZE_STRING_CONCAT)
318 << "Insert StringBuilder.append intrinsic (id=" << appendArgIntrinsic->GetId() << ")";
319
320 auto toStringCall = CreateStringBuilderToStringIntrinsic(GetGraph(), instance, concatCall->GetSaveState());
321
322 auto arrayLength = GetArrayLengthConstant(args);
323 bool collected = args->GetOpcode() == Opcode::NewArray && CollectArrayElements(args, arrayElements_);
324 if (collected) {
325 CreateAppendArgsIntrinsics(instance, concatCall->GetSaveState());
326 InsertBeforeWithSaveState(toStringCall, concatCall->GetSaveState());
327 } else if (args->GetOpcode() == Opcode::NewArray && arrayLength != nullptr) {
328 CreateAppendArgsIntrinsics(instance, args, arrayLength->CastToConstant()->GetIntValue(),
329 concatCall->GetSaveState());
330 InsertBeforeWithSaveState(toStringCall, concatCall->GetSaveState());
331 } else {
332 arrayLength = CreateLenArray(GetGraph(), args);
333 concatCall->GetSaveState()->InsertBefore(arrayLength);
334 auto postExit = CreateAppendArgsLoop(instance, str, args, arrayLength->CastToLenArray(), concatCall);
335
336 postExit->PrependInst(toStringCall);
337 postExit->PrependInst(toStringCall->GetSaveState());
338
339 InvalidateBlocksOrderAnalyzes(GetGraph());
340 GetGraph()->InvalidateAnalysis<LoopAnalyzer>();
341 }
342 COMPILER_LOG(DEBUG, OPTIMIZE_STRING_CONCAT) << "Replace String.concat call (id=" << concatCall->GetId()
343 << ") with StringBuilder instance (id=" << instance->GetId() << ")";
344
345 FixBrokenSaveStates(instance, toStringCall);
346
347 concatCall->ReplaceUsers(toStringCall);
348
349 concatCall->ClearFlag(inst_flags::NO_DCE);
350 if (concatCall->GetInput(0).GetInst()->IsCheck()) {
351 concatCall->GetInput(0).GetInst()->ClearFlag(inst_flags::NO_DCE);
352 }
353
354 if (collected && HasStoreArrayUsersOnly(args, concatCall)) {
355 CleanupStoreArrayInstructions(args);
356 args->ClearFlag(inst_flags::NO_DCE);
357 }
358 }
359
360 } // namespace ark::compiler
361