1 /*
2 * Copyright (c) 2023 Huawei Device Co., Ltd.
3 * Licensed under the Apache License, Version 2.0 (the "License");
4 * you may not use this file except in compliance with the License.
5 * You may obtain a copy of the License at
6 *
7 * http://www.apache.org/licenses/LICENSE-2.0
8 *
9 * Unless required by applicable law or agreed to in writing, software
10 * distributed under the License is distributed on an "AS IS" BASIS,
11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 * See the License for the specific language governing permissions and
13 * limitations under the License.
14 */
15
16 #include "ecmascript/compiler/range_analysis.h"
17
18 namespace panda::ecmascript::kungfu {
19
UpdateRange(GateRef gate,const RangeInfo & info)20 GateRef RangeAnalysis::UpdateRange(GateRef gate, const RangeInfo& info)
21 {
22 auto &range = rangeInfos_[acc_.GetId(gate)];
23 if (range != info) {
24 range = info;
25 return gate;
26 } else {
27 return Circuit::NullGate();
28 }
29 }
30
GetRange(GateRef gate) const31 RangeInfo RangeAnalysis::GetRange(GateRef gate) const
32 {
33 ASSERT(acc_.GetId(gate) < rangeInfos_.size());
34 return rangeInfos_[acc_.GetId(gate)];
35 }
36
IsInt32Type(GateRef gate) const37 bool RangeAnalysis::IsInt32Type(GateRef gate) const
38 {
39 auto id = acc_.GetId(gate);
40 if (id >= typeInfos_.size()) {
41 return acc_.GetMachineType(gate) == MachineType::I32;
42 }
43 return typeInfos_[id] == TypeInfo::INT32;
44 }
45
VisitGate(GateRef gate)46 GateRef RangeAnalysis::VisitGate(GateRef gate)
47 {
48 auto op = acc_.GetOpCode(gate);
49 switch (op) {
50 case OpCode::CONSTANT:
51 return VisitConstant(gate);
52 case OpCode::VALUE_SELECTOR:
53 return VisitPhi(gate);
54 case OpCode::TYPED_BINARY_OP:
55 return VisitTypedBinaryOp(gate);
56 case OpCode::TYPED_UNARY_OP:
57 return VisitTypedUnaryOp(gate);
58 case OpCode::INDEX_CHECK:
59 return VisitIndexCheck(gate);
60 case OpCode::LOAD_ARRAY_LENGTH:
61 return VisitLoadArrayLength(gate);
62 case OpCode::LOAD_STRING_LENGTH:
63 return VisitLoadStringLength(gate);
64 case OpCode::LOAD_MAP_SIZE:
65 return VisitLoadMapSize(gate);
66 case OpCode::LOAD_TYPED_ARRAY_LENGTH:
67 return VisitLoadTypedArrayLength(gate);
68 case OpCode::RANGE_GUARD:
69 return VisitRangeGuard(gate);
70 default:
71 return VisitOthers(gate);
72 }
73 }
74
VisitPhi(GateRef gate)75 GateRef RangeAnalysis::VisitPhi(GateRef gate)
76 {
77 if (!IsInt32Type(gate)) {
78 return Circuit::NullGate();
79 }
80 auto range = RangeInfo::NONE();
81 auto numIn = acc_.GetInValueCount(gate);
82 for (size_t i = 0; i < numIn; ++i) {
83 auto valueIn = acc_.GetValueIn(gate, i);
84 range = range.Union(GetRange(valueIn));
85 }
86 return UpdateRange(gate, range);
87 }
88
VisitOthers(GateRef gate)89 GateRef RangeAnalysis::VisitOthers(GateRef gate)
90 {
91 if (!IsInt32Type(gate)) {
92 return Circuit::NullGate();
93 }
94 return UpdateRange(gate, RangeInfo::ANY());
95 }
96
VisitConstant(GateRef gate)97 GateRef RangeAnalysis::VisitConstant(GateRef gate)
98 {
99 if (!IsInt32Type(gate)) {
100 return Circuit::NullGate();
101 }
102 auto value = acc_.GetInt32FromConstant(gate);
103 return UpdateRange(gate, RangeInfo(value, value));
104 }
105
VisitTypedUnaryOp(GateRef gate)106 GateRef RangeAnalysis::VisitTypedUnaryOp(GateRef gate)
107 {
108 if (!IsInt32Type(gate)) {
109 return Circuit::NullGate();
110 }
111 auto op = acc_.GetTypedUnAccessor(gate).GetTypedUnOp();
112 auto range = GetRange(acc_.GetValueIn(gate, 0));
113 if (range.IsNone()) {
114 return Circuit::NullGate();
115 }
116 switch (op) {
117 case TypedUnOp::TYPED_INC:
118 range = range + RangeInfo(1, 1);
119 break;
120 case TypedUnOp::TYPED_DEC:
121 range = range - RangeInfo(1, 1);
122 break;
123 case TypedUnOp::TYPED_NEG:
124 range = RangeInfo(0, 0) - range;
125 break;
126 case TypedUnOp::TYPED_NOT:
127 range = ~ range;
128 break;
129 default:
130 break;
131 }
132 return UpdateRange(gate, range);
133 }
134
VisitTypedBinaryOp(GateRef gate)135 GateRef RangeAnalysis::VisitTypedBinaryOp(GateRef gate)
136 {
137 if (!IsInt32Type(gate)) {
138 return Circuit::NullGate();
139 }
140 auto op = acc_.GetTypedBinaryOp(gate);
141 auto range = RangeInfo::ANY();
142 switch (op) {
143 case TypedBinOp::TYPED_ADD:
144 range = GetRangeOfCalculate<TypedBinOp::TYPED_ADD>(gate);
145 break;
146 case TypedBinOp::TYPED_SUB:
147 range = GetRangeOfCalculate<TypedBinOp::TYPED_SUB>(gate);
148 break;
149 case TypedBinOp::TYPED_MOD:
150 range = GetRangeOfCalculate<TypedBinOp::TYPED_MOD>(gate);
151 break;
152 case TypedBinOp::TYPED_MUL:
153 range = GetRangeOfCalculate<TypedBinOp::TYPED_MUL>(gate);
154 break;
155 case TypedBinOp::TYPED_SHR:
156 range = GetRangeOfShift<TypedBinOp::TYPED_SHR>(gate);
157 break;
158 case TypedBinOp::TYPED_ASHR:
159 range = GetRangeOfShift<TypedBinOp::TYPED_ASHR>(gate);
160 break;
161 default:
162 break;
163 }
164 return UpdateRange(gate, range);
165 }
166
VisitIndexCheck(GateRef gate)167 GateRef RangeAnalysis::VisitIndexCheck(GateRef gate)
168 {
169 ASSERT(IsInt32Type(gate));
170 auto value = GetRange(acc_.GetValueIn(gate, 0));
171 auto largerRange = RangeInfo(0, INT32_MAX - 1);
172 auto intersected = value.intersection(largerRange);
173 return UpdateRange(gate, intersected);
174 }
175
VisitLoadArrayLength(GateRef gate)176 GateRef RangeAnalysis::VisitLoadArrayLength(GateRef gate)
177 {
178 ASSERT(IsInt32Type(gate));
179 return UpdateRange(gate, RangeInfo(0, INT32_MAX));
180 }
181
VisitLoadStringLength(GateRef gate)182 GateRef RangeAnalysis::VisitLoadStringLength(GateRef gate)
183 {
184 ASSERT(IsInt32Type(gate));
185 return UpdateRange(gate, RangeInfo(0, INT32_MAX));
186 }
187
VisitLoadMapSize(GateRef gate)188 GateRef RangeAnalysis::VisitLoadMapSize(GateRef gate)
189 {
190 ASSERT(IsInt32Type(gate));
191 return UpdateRange(gate, RangeInfo(0, INT32_MAX));
192 }
193
VisitLoadTypedArrayLength(GateRef gate)194 GateRef RangeAnalysis::VisitLoadTypedArrayLength(GateRef gate)
195 {
196 TypedArrayMetaDataAccessor accessor = acc_.GetTypedArrayMetaDataAccessor(gate);
197 OnHeapMode onHeap = accessor.GetOnHeapMode();
198 int32_t max = onHeap == OnHeapMode::ON_HEAP ? RangeInfo::TYPED_ARRAY_ONHEAP_MAX : INT32_MAX;
199 return UpdateRange(gate, RangeInfo(0, max));
200 }
201
VisitRangeGuard(GateRef gate)202 GateRef RangeAnalysis::VisitRangeGuard(GateRef gate)
203 {
204 auto left = acc_.GetFirstValue(gate);
205 auto right = acc_.GetSecondValue(gate);
206 return UpdateRange(gate, RangeInfo(left, right));
207 }
208
209 template<TypedBinOp Op>
GetRangeOfCalculate(GateRef gate)210 RangeInfo RangeAnalysis::GetRangeOfCalculate(GateRef gate)
211 {
212 auto left = GetRange(acc_.GetValueIn(gate, 0));
213 auto right = GetRange(acc_.GetValueIn(gate, 1));
214 if (left.IsNone() || right.IsNone()) {
215 return RangeInfo::NONE();
216 }
217 switch (Op) {
218 case TypedBinOp::TYPED_ADD:
219 return left + right;
220 case TypedBinOp::TYPED_SUB:
221 return left - right;
222 case TypedBinOp::TYPED_MOD:
223 return left % right;
224 case TypedBinOp::TYPED_MUL:
225 return left * right;
226 default:
227 return RangeInfo::ANY();
228 }
229 }
230
231 template<TypedBinOp Op>
GetRangeOfShift(GateRef gate)232 RangeInfo RangeAnalysis::GetRangeOfShift(GateRef gate)
233 {
234 ASSERT((Op == TypedBinOp::TYPED_SHR) || (Op == TypedBinOp::TYPED_ASHR));
235 auto value = GetRange(acc_.GetValueIn(gate, 0));
236 auto shift = GetRange(acc_.GetValueIn(gate, 1));
237 if (value.IsNone() || shift.IsNone()) {
238 return RangeInfo::NONE();
239 }
240 if (shift.GetMin() != shift.GetMax()) {
241 return RangeInfo::ANY();
242 }
243 switch (Op) {
244 case TypedBinOp::TYPED_SHR:
245 return value.SHR(shift);
246 case TypedBinOp::TYPED_ASHR:
247 return value.ASHR(shift);
248 default:
249 return RangeInfo::ANY();
250 }
251 }
252
TryGetRangeOfBranch(GateRef state,GateRef value)253 RangeInfo RangeAnalysis::TryGetRangeOfBranch(GateRef state, GateRef value)
254 {
255 auto jmp = acc_.GetState(state);
256 if (acc_.GetOpCode(jmp) == OpCode::JS_BYTECODE) {
257 return GetRange(value);
258 }
259 ASSERT((acc_.GetOpCode(jmp) == OpCode::IF_BRANCH) || (acc_.GetOpCode(jmp) == OpCode::TYPED_CONDITION_JUMP));
260 auto condition = acc_.GetValueIn(jmp);
261 auto range = GetRange(value);
262 if (acc_.GetOpCode(condition) != OpCode::TYPED_BINARY_OP) {
263 return range;
264 }
265 if ((acc_.GetValueIn(condition, 0) != value) && (acc_.GetValueIn(condition, 1) != value)) {
266 return range;
267 }
268
269 // flag = !(jnez ^ if_false) = jnez ^ if_true
270 bool flag = acc_.GetOpCode(state) == OpCode::IF_TRUE;
271 if (acc_.GetOpCode(jmp) == OpCode::TYPED_CONDITION_JUMP) {
272 flag = flag != (acc_.GetTypedJumpAccessor(jmp).GetTypedJumpOp() == TypedJumpOp::TYPED_JNEZ);
273 }
274 return range.intersection(GetRangeOfCompare(condition, value, flag));
275 }
276
GetRangeOfCompare(GateRef gate,GateRef value,bool flag)277 RangeInfo RangeAnalysis::GetRangeOfCompare(GateRef gate, GateRef value, bool flag)
278 {
279 auto op = acc_.GetTypedBinaryOp(gate);
280 auto left = acc_.GetValueIn(gate, 0);
281 auto right = acc_.GetValueIn(gate, 1);
282 ASSERT((left == value) || (right == value));
283 bool swap = right == value;
284 if (flag) {
285 op = acc_.GetRevCompareOpForTypedBinOp(op);
286 }
287 if (swap) {
288 op = acc_.GetSwapCompareOpForTypedBinOp(op);
289 }
290 auto range = GetRange(swap ? left : right);
291 if (range.IsNone()) {
292 // provide no info for branch range infer.
293 return RangeInfo::ANY();
294 }
295 switch (op) {
296 case TypedBinOp::TYPED_LESS:
297 return RangeInfo(INT32_MIN, range.GetMax() - 1);
298 case TypedBinOp::TYPED_LESSEQ:
299 return RangeInfo(INT32_MIN, range.GetMax());
300 case TypedBinOp::TYPED_GREATER:
301 return RangeInfo(range.GetMin() + 1, INT32_MAX);
302 case TypedBinOp::TYPED_GREATEREQ:
303 return RangeInfo(range.GetMin(), INT32_MAX);
304 case TypedBinOp::TYPED_EQ:
305 return range;
306 case TypedBinOp::TYPED_NOTEQ:
307 return RangeInfo::ANY();
308 default:
309 UNREACHABLE();
310 return RangeInfo::ANY();
311 }
312 }
313
PrintRangeInfo() const314 void RangeAnalysis::PrintRangeInfo() const
315 {
316 std::vector<GateRef> gateList;
317 acc_.GetAllGates(gateList);
318 std::string log = "";
319 for (auto gate : gateList) {
320 if (!IsInt32Type(gate)) {
321 continue;
322 }
323 log = "id:" + std::to_string(acc_.GetId(gate));
324 auto op = acc_.GetOpCode(gate);
325 switch (op) {
326 case OpCode::CONSTANT: {
327 log += " constant";
328 break;
329 }
330 case OpCode::VALUE_SELECTOR: {
331 log += " phi";
332 break;
333 }
334 case OpCode::TYPED_BINARY_OP: {
335 auto binOp = acc_.GetTypedBinaryOp(gate);
336 switch (binOp) {
337 case TypedBinOp::TYPED_ADD:
338 log += " add";
339 break;
340 case TypedBinOp::TYPED_SUB:
341 log += " sub";
342 break;
343 case TypedBinOp::TYPED_SHR:
344 log += " shr";
345 break;
346 case TypedBinOp::TYPED_ASHR:
347 log += " ashr";
348 break;
349 case TypedBinOp::TYPED_MOD:
350 log += " mod";
351 break;
352 case TypedBinOp::TYPED_MUL:
353 log += " mul";
354 break;
355 default:
356 log += " other";
357 break;
358 }
359 break;
360 }
361 case OpCode::TYPED_UNARY_OP: {
362 auto unOp = acc_.GetTypedUnAccessor(gate).GetTypedUnOp();
363 switch (unOp) {
364 case TypedUnOp::TYPED_INC:
365 log += " inc";
366 break;
367 case TypedUnOp::TYPED_DEC:
368 log += " dec";
369 break;
370 case TypedUnOp::TYPED_NEG:
371 log += " neg";
372 break;
373 default:
374 log += " other";
375 break;
376 }
377 break;
378 }
379 case OpCode::INDEX_CHECK: {
380 log += " index check";
381 break;
382 }
383 case OpCode::LOAD_ARRAY_LENGTH: {
384 log += " array length";
385 break;
386 }
387 default: {
388 log += " other";
389 break;
390 }
391 }
392 auto range = GetRange(gate);
393 log += " range = [" + std::to_string(range.GetMin()) + "," + std::to_string(range.GetMax()) + "]";
394 LOG_COMPILER(INFO) << log;
395 }
396 }
397 } // namespace panda::ecmascript::kungfu
398