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 "assembler/assembly-literals.h"
17 #include "const_array_resolver.h"
18 #include "compiler/optimizer/ir/basicblock.h"
19 #include "compiler/optimizer/optimizations/peepholes.h"
20
21 namespace ark::bytecodeopt {
22
23 static constexpr size_t STOREARRAY_INPUTS_NUM = 3;
24 static constexpr size_t SINGLE_DIM_ARRAY_RANK = 1;
25 static constexpr size_t MIN_ARRAY_ELEMENTS_AMOUNT = 2;
26
RunImpl()27 bool ConstArrayResolver::RunImpl()
28 {
29 if (irInterface_ == nullptr) {
30 return false;
31 }
32
33 if (!FindConstantArrays()) {
34 return false;
35 }
36
37 // delete instructions for storing array elements
38 RemoveArraysFill();
39
40 // replace old NewArray instructions with new SaveState + LoadConst instructions
41 InsertLoadConstArrayInsts();
42
43 return true;
44 }
45
IsPatchAllowedOpcode(Opcode opcode)46 static bool IsPatchAllowedOpcode(Opcode opcode)
47 {
48 switch (opcode) {
49 case Opcode::StoreArray:
50 case Opcode::LoadString:
51 case Opcode::Constant:
52 case Opcode::Cast:
53 case Opcode::SaveState:
54 return true;
55 default:
56 return false;
57 }
58 }
59
GetConstantIfPossible(Inst * inst)60 static std::optional<compiler::ConstantInst *> GetConstantIfPossible(Inst *inst)
61 {
62 if (inst->GetOpcode() == Opcode::Cast) {
63 auto input = inst->GetInput(0U).GetInst();
64 if ((input->GetOpcode() == Opcode::NullPtr) || !input->IsConst()) {
65 return std::nullopt;
66 }
67 auto constantInst = compiler::ConstFoldingCastConst(inst, input, true);
68 if (constantInst != nullptr) {
69 return constantInst;
70 }
71 }
72 if (inst->IsConst()) {
73 return inst->CastToConstant();
74 }
75 return std::nullopt;
76 }
77
FillLiteralArray(Inst * inst,size_t size)78 std::optional<std::vector<pandasm::LiteralArray::Literal>> ConstArrayResolver::FillLiteralArray(Inst *inst, size_t size)
79 {
80 std::vector<pandasm::LiteralArray::Literal> literals {size};
81 std::vector<Inst *> storeInsts;
82
83 auto next = inst->GetNext();
84 size_t realSize = 0;
85
86 // are looking for instructions for uninterrupted filling the array
87 while (next != nullptr) {
88 // check whether the instruction is allowed inside the filling patch
89 if (!IsPatchAllowedOpcode(next->GetOpcode())) {
90 break;
91 }
92
93 // find instructions for storing array elements
94 if (next->GetOpcode() != Opcode::StoreArray) {
95 next = next->GetNext();
96 continue;
97 }
98
99 auto storeArrayInst = next->CastToStoreArray();
100 if (storeArrayInst == nullptr || storeArrayInst->GetArray() != inst) {
101 break;
102 }
103
104 // get an index of the inserted element if possible
105 auto indexInst = storeArrayInst->GetIndex();
106 auto indexConstInst = GetConstantIfPossible(indexInst);
107 if (!indexConstInst) {
108 return std::nullopt;
109 }
110 auto index = static_cast<size_t>((*indexConstInst)->GetIntValue());
111 if (index >= size) {
112 return std::nullopt;
113 }
114
115 pandasm::LiteralArray::Literal literal {};
116 // create a literal from the array element, if possible
117 if (!FillLiteral(storeArrayInst, &literal)) {
118 // if not, then we can't create a constant literal array
119 return std::nullopt;
120 }
121
122 // checks if there is free space on the [index] position in the vector
123 pandasm::LiteralArray::Literal defaultLiteral {};
124 if (literals[index] == defaultLiteral) {
125 realSize++;
126 }
127
128 literals[index] = literal;
129 storeInsts.push_back(next);
130 next = next->GetNext();
131 }
132
133 // save the literal array only if it is completely filled
134 // or its size exceeds the minimum number of elements to save
135 if (realSize != size || storeInsts.size() < MIN_ARRAY_ELEMENTS_AMOUNT) {
136 return std::nullopt;
137 }
138
139 // save the store instructions for deleting them later
140 constArraysFill_.emplace(inst, std::move(storeInsts));
141 return std::optional<std::vector<pandasm::LiteralArray::Literal>> {std::move(literals)};
142 }
143
AddIntroLiterals(pandasm::LiteralArray * ltAr)144 void ConstArrayResolver::AddIntroLiterals(pandasm::LiteralArray *ltAr)
145 {
146 // add an element that stores the array size (it will be stored in the first element)
147 pandasm::LiteralArray::Literal lenLit;
148 lenLit.tag = panda_file::LiteralTag::INTEGER;
149 lenLit.value = static_cast<uint32_t>(ltAr->literals.size());
150 ltAr->literals.insert(ltAr->literals.begin(), lenLit);
151
152 // add an element that stores the array type (it will be stored in the zero element)
153 pandasm::LiteralArray::Literal tagLit;
154 tagLit.tag = panda_file::LiteralTag::TAGVALUE;
155 tagLit.value = static_cast<uint8_t>(ltAr->literals.back().tag);
156 ltAr->literals.insert(ltAr->literals.begin(), tagLit);
157 }
158
IsMultidimensionalArray(compiler::NewArrayInst * inst)159 bool ConstArrayResolver::IsMultidimensionalArray(compiler::NewArrayInst *inst)
160 {
161 auto arrayType = pandasm::Type::FromName(irInterface_->GetTypeIdByOffset(inst->GetTypeId()));
162 return arrayType.GetRank() > SINGLE_DIM_ARRAY_RANK;
163 }
164
IsSameBB(Inst * inst1,Inst * inst2)165 static bool IsSameBB(Inst *inst1, Inst *inst2)
166 {
167 return inst1->GetBasicBlock() == inst2->GetBasicBlock();
168 }
169
IsSameBB(Inst * inst,compiler::BasicBlock * bb)170 static bool IsSameBB(Inst *inst, compiler::BasicBlock *bb)
171 {
172 return inst->GetBasicBlock() == bb;
173 }
174
FindConstantArrays()175 bool ConstArrayResolver::FindConstantArrays()
176 {
177 size_t initSize = irInterface_->GetLiteralArrayTableSize();
178
179 for (auto bb : GetGraph()->GetBlocksRPO()) {
180 // go through the instructions of the basic block in reverse order
181 // until we meet the instruction for storing an array element
182 auto inst = bb->GetLastInst();
183 while ((inst != nullptr) && IsSameBB(inst, bb)) {
184 if (inst->GetOpcode() != Opcode::StoreArray) {
185 inst = inst->GetPrev();
186 continue;
187 }
188
189 // the patch for creating and filling an array should start with the NewArray instruction
190 auto arrayInst = inst->CastToStoreArray()->GetArray();
191 if (arrayInst->GetOpcode() != Opcode::NewArray) {
192 inst = inst->GetPrev();
193 continue;
194 }
195 auto newArrayInst = arrayInst->CastToNewArray();
196 // the instructions included in the patch must be in one basic block
197 if (!IsSameBB(inst, newArrayInst)) {
198 inst = inst->GetPrev();
199 continue;
200 }
201
202 // NOTE(aantipina): add the ability to save multidimensional arrays
203 if (IsMultidimensionalArray(newArrayInst)) {
204 inst = IsSameBB(inst, newArrayInst) ? newArrayInst->GetPrev() : inst->GetPrev();
205 continue;
206 }
207
208 auto arraySizeInst =
209 GetConstantIfPossible(newArrayInst->GetInput(compiler::NewArrayInst::INDEX_SIZE).GetInst());
210 if (arraySizeInst == std::nullopt) {
211 inst = newArrayInst->GetPrev();
212 continue;
213 }
214 auto arraySize = (*arraySizeInst)->CastToConstant()->GetIntValue();
215 if (arraySize < MIN_ARRAY_ELEMENTS_AMOUNT) {
216 inst = newArrayInst->GetPrev();
217 continue;
218 }
219
220 // creating a literal array, if possible
221 auto rawLiteralArray = FillLiteralArray(newArrayInst, arraySize);
222 if (rawLiteralArray == std::nullopt) {
223 inst = newArrayInst->GetPrev();
224 continue;
225 }
226
227 pandasm::LiteralArray literalArray(*rawLiteralArray);
228
229 // save the type and length of the array in the first two elements
230 AddIntroLiterals(&literalArray);
231 auto id = irInterface_->GetLiteralArrayTableSize();
232 irInterface_->StoreLiteralArray(std::to_string(id), std::move(literalArray));
233
234 // save the NewArray instructions for replacing them with LoadConst instructions later
235 constArraysInit_.emplace(id, newArrayInst);
236
237 inst = newArrayInst->GetPrev();
238 }
239 }
240
241 // the pass worked if the size of the literal array table increased
242 return initSize < irInterface_->GetLiteralArrayTableSize();
243 }
244
RemoveArraysFill()245 void ConstArrayResolver::RemoveArraysFill()
246 {
247 for (const auto &it : constArraysFill_) {
248 for (const auto &storeInst : it.second) {
249 storeInst->GetBasicBlock()->RemoveInst(storeInst);
250 }
251 }
252 }
253
InsertLoadConstArrayInsts()254 void ConstArrayResolver::InsertLoadConstArrayInsts()
255 {
256 for (const auto &[id, start_inst] : constArraysInit_) {
257 auto method = GetGraph()->GetMethod();
258 compiler::LoadConstArrayInst *newInst = GetGraph()->CreateInstLoadConstArray(REFERENCE, start_inst->GetPc());
259 newInst->SetTypeId(id);
260 newInst->SetMethod(method);
261
262 start_inst->ReplaceUsers(newInst);
263 start_inst->RemoveInputs();
264
265 compiler::SaveStateInst *saveState = GetGraph()->CreateInstSaveState();
266 saveState->SetPc(start_inst->GetPc());
267 saveState->SetMethod(method);
268 saveState->ReserveInputs(0U);
269
270 newInst->SetInput(0U, saveState);
271 start_inst->InsertBefore(saveState);
272 start_inst->GetBasicBlock()->ReplaceInst(start_inst, newInst);
273 }
274 }
275
FillPrimitiveLiteral(pandasm::LiteralArray::Literal * literal,panda_file::Type::TypeId type,compiler::ConstantInst * valueInst)276 static bool FillPrimitiveLiteral(pandasm::LiteralArray::Literal *literal, panda_file::Type::TypeId type,
277 compiler::ConstantInst *valueInst)
278 {
279 auto tag = pandasm::LiteralArray::GetArrayTagFromComponentType(type);
280 literal->tag = tag;
281 switch (tag) {
282 case panda_file::LiteralTag::ARRAY_U1:
283 literal->value = static_cast<bool>(valueInst->GetInt32Value());
284 return true;
285 case panda_file::LiteralTag::ARRAY_U8:
286 case panda_file::LiteralTag::ARRAY_I8:
287 literal->value = static_cast<uint8_t>(valueInst->GetInt32Value());
288 return true;
289 case panda_file::LiteralTag::ARRAY_U16:
290 case panda_file::LiteralTag::ARRAY_I16:
291 literal->value = static_cast<uint16_t>(valueInst->GetInt32Value());
292 return true;
293 case panda_file::LiteralTag::ARRAY_U32:
294 case panda_file::LiteralTag::ARRAY_I32:
295 literal->value = valueInst->GetInt32Value();
296 return true;
297 case panda_file::LiteralTag::ARRAY_U64:
298 case panda_file::LiteralTag::ARRAY_I64:
299 literal->value = valueInst->GetInt64Value();
300 return true;
301 case panda_file::LiteralTag::ARRAY_F32:
302 literal->value = valueInst->GetFloatValue();
303 return true;
304 case panda_file::LiteralTag::ARRAY_F64:
305 literal->value = valueInst->GetDoubleValue();
306 return true;
307 default:
308 UNREACHABLE();
309 }
310 return false;
311 }
312
FillLiteral(compiler::StoreInst * storeArrayInst,pandasm::LiteralArray::Literal * literal)313 bool ConstArrayResolver::FillLiteral(compiler::StoreInst *storeArrayInst, pandasm::LiteralArray::Literal *literal)
314 {
315 if (storeArrayInst->GetInputsCount() > STOREARRAY_INPUTS_NUM) {
316 return false;
317 }
318 auto rawElemInst = storeArrayInst->GetStoredValue();
319 auto newArrayInst = storeArrayInst->GetArray();
320
321 auto arrayType =
322 pandasm::Type::FromName(irInterface_->GetTypeIdByOffset(newArrayInst->CastToNewArray()->GetTypeId()));
323 auto componentType = arrayType.GetComponentType();
324
325 if (arrayType.IsArrayContainsPrimTypes()) {
326 auto valueInst = GetConstantIfPossible(rawElemInst);
327 if (valueInst == std::nullopt) {
328 return false;
329 }
330 return FillPrimitiveLiteral(literal, componentType.GetId(), *valueInst);
331 }
332
333 auto componentTypeDescriptor = componentType.GetDescriptor();
334 auto stringDescriptor = ark::panda_file::GetStringClassDescriptor(irInterface_->GetSourceLang());
335 if ((rawElemInst->GetOpcode() == Opcode::LoadString) && (componentTypeDescriptor == stringDescriptor)) {
336 literal->tag = panda_file::LiteralTag::ARRAY_STRING;
337 std::string stringValue = irInterface_->GetStringIdByOffset(rawElemInst->CastToLoadString()->GetTypeId());
338 literal->value = stringValue;
339 return true;
340 }
341
342 return false;
343 }
344
345 } // namespace ark::bytecodeopt
346