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_TYPED_ARRAY_LENGTH:
63 return VisitLoadTypedArrayLength(gate);
64 case OpCode::RANGE_GUARD:
65 return VisitRangeGuard(gate);
66 default:
67 return VisitOthers(gate);
68 }
69 }
70
VisitPhi(GateRef gate)71 GateRef RangeAnalysis::VisitPhi(GateRef gate)
72 {
73 if (!IsInt32Type(gate)) {
74 return Circuit::NullGate();
75 }
76 auto range = RangeInfo::NONE();
77 auto numIn = acc_.GetInValueCount(gate);
78 for (size_t i = 0; i < numIn; ++i) {
79 auto valueIn = acc_.GetValueIn(gate, i);
80 range = range.Union(GetRange(valueIn));
81 }
82 return UpdateRange(gate, range);
83 }
84
VisitOthers(GateRef gate)85 GateRef RangeAnalysis::VisitOthers(GateRef gate)
86 {
87 if (!IsInt32Type(gate)) {
88 return Circuit::NullGate();
89 }
90 return UpdateRange(gate, RangeInfo::ANY());
91 }
92
VisitConstant(GateRef gate)93 GateRef RangeAnalysis::VisitConstant(GateRef gate)
94 {
95 if (!IsInt32Type(gate)) {
96 return Circuit::NullGate();
97 }
98 auto value = acc_.GetInt32FromConstant(gate);
99 return UpdateRange(gate, RangeInfo(value, value));
100 }
101
VisitTypedUnaryOp(GateRef gate)102 GateRef RangeAnalysis::VisitTypedUnaryOp(GateRef gate)
103 {
104 if (!IsInt32Type(gate)) {
105 return Circuit::NullGate();
106 }
107 auto op = acc_.GetTypedUnAccessor(gate).GetTypedUnOp();
108 auto range = GetRange(acc_.GetValueIn(gate, 0));
109 if (range.IsNone()) {
110 return Circuit::NullGate();
111 }
112 switch (op) {
113 case TypedUnOp::TYPED_INC:
114 range = range + RangeInfo(1, 1);
115 break;
116 case TypedUnOp::TYPED_DEC:
117 range = range - RangeInfo(1, 1);
118 break;
119 case TypedUnOp::TYPED_NEG:
120 range = RangeInfo(0, 0) - range;
121 break;
122 default:
123 break;
124 }
125 return UpdateRange(gate, range);
126 }
127
VisitTypedBinaryOp(GateRef gate)128 GateRef RangeAnalysis::VisitTypedBinaryOp(GateRef gate)
129 {
130 if (!IsInt32Type(gate)) {
131 return Circuit::NullGate();
132 }
133 auto op = acc_.GetTypedBinaryOp(gate);
134 auto range = RangeInfo::ANY();
135 switch (op) {
136 case TypedBinOp::TYPED_ADD:
137 range = GetRangeOfCalculate<TypedBinOp::TYPED_ADD>(gate);
138 break;
139 case TypedBinOp::TYPED_SUB:
140 range = GetRangeOfCalculate<TypedBinOp::TYPED_SUB>(gate);
141 break;
142 case TypedBinOp::TYPED_SHR:
143 range = GetRangeOfShift<TypedBinOp::TYPED_SHR>(gate);
144 break;
145 case TypedBinOp::TYPED_ASHR:
146 range = GetRangeOfShift<TypedBinOp::TYPED_ASHR>(gate);
147 break;
148 default:
149 break;
150 }
151 return UpdateRange(gate, range);
152 }
153
VisitIndexCheck(GateRef gate)154 GateRef RangeAnalysis::VisitIndexCheck(GateRef gate)
155 {
156 ASSERT(IsInt32Type(gate));
157 auto value = GetRange(acc_.GetValueIn(gate, 0));
158 auto largerRange = RangeInfo(0, INT32_MAX - 1);
159 auto intersected = value.intersection(largerRange);
160 return UpdateRange(gate, intersected);
161 }
162
VisitLoadArrayLength(GateRef gate)163 GateRef RangeAnalysis::VisitLoadArrayLength(GateRef gate)
164 {
165 ASSERT(IsInt32Type(gate));
166 return UpdateRange(gate, RangeInfo(0, INT32_MAX));
167 }
168
VisitLoadTypedArrayLength(GateRef gate)169 GateRef RangeAnalysis::VisitLoadTypedArrayLength(GateRef gate)
170 {
171 return UpdateRange(gate, RangeInfo(0, RangeInfo::TYPED_ARRAY_ONHEAP_MAX));
172 }
173
VisitRangeGuard(GateRef gate)174 GateRef RangeAnalysis::VisitRangeGuard(GateRef gate)
175 {
176 auto left = acc_.GetFirstValue(gate);
177 auto right = acc_.GetSecondValue(gate);
178 return UpdateRange(gate, RangeInfo(left, right));
179 }
180
181 template<TypedBinOp Op>
GetRangeOfCalculate(GateRef gate)182 RangeInfo RangeAnalysis::GetRangeOfCalculate(GateRef gate)
183 {
184 ASSERT((Op == TypedBinOp::TYPED_ADD) || (Op == TypedBinOp::TYPED_SUB));
185 auto left = GetRange(acc_.GetValueIn(gate, 0));
186 auto right = GetRange(acc_.GetValueIn(gate, 1));
187 if (left.IsNone() || right.IsNone()) {
188 return RangeInfo::NONE();
189 }
190 switch (Op) {
191 case TypedBinOp::TYPED_ADD:
192 return left + right;
193 case TypedBinOp::TYPED_SUB:
194 return left - right;
195 default:
196 return RangeInfo::ANY();
197 }
198 }
199
200 template<TypedBinOp Op>
GetRangeOfShift(GateRef gate)201 RangeInfo RangeAnalysis::GetRangeOfShift(GateRef gate)
202 {
203 ASSERT((Op == TypedBinOp::TYPED_SHR) || (Op == TypedBinOp::TYPED_ASHR));
204 auto value = GetRange(acc_.GetValueIn(gate, 0));
205 auto shift = GetRange(acc_.GetValueIn(gate, 1));
206 if (value.IsNone() || shift.IsNone()) {
207 return RangeInfo::NONE();
208 }
209 if (shift.GetMin() != shift.GetMax()) {
210 return RangeInfo::ANY();
211 }
212 switch (Op) {
213 case TypedBinOp::TYPED_SHR:
214 return value.SHR(shift);
215 case TypedBinOp::TYPED_ASHR:
216 return value.ASHR(shift);
217 default:
218 return RangeInfo::ANY();
219 }
220 }
221
TryGetRangeOfBranch(GateRef state,GateRef value)222 RangeInfo RangeAnalysis::TryGetRangeOfBranch(GateRef state, GateRef value)
223 {
224 auto jmp = acc_.GetState(state);
225 if (acc_.GetOpCode(jmp) == OpCode::JS_BYTECODE) {
226 return GetRange(value);
227 }
228 ASSERT((acc_.GetOpCode(jmp) == OpCode::IF_BRANCH) || (acc_.GetOpCode(jmp) == OpCode::TYPED_CONDITION_JUMP));
229 auto condition = acc_.GetValueIn(jmp);
230 auto range = GetRange(value);
231 if (acc_.GetOpCode(condition) != OpCode::TYPED_BINARY_OP) {
232 return range;
233 }
234 if ((acc_.GetValueIn(condition, 0) != value) && (acc_.GetValueIn(condition, 1) != value)) {
235 return range;
236 }
237
238 // flag = !(jnez ^ if_false) = jnez ^ if_true
239 bool flag = acc_.GetOpCode(state) == OpCode::IF_TRUE;
240 if (acc_.GetOpCode(jmp) == OpCode::TYPED_CONDITION_JUMP) {
241 flag = flag != (acc_.GetTypedJumpAccessor(jmp).GetTypedJumpOp() == TypedJumpOp::TYPED_JNEZ);
242 }
243 return range.intersection(GetRangeOfCompare(condition, value, flag));
244 }
245
GetRangeOfCompare(GateRef gate,GateRef value,bool flag)246 RangeInfo RangeAnalysis::GetRangeOfCompare(GateRef gate, GateRef value, bool flag)
247 {
248 auto op = acc_.GetTypedBinaryOp(gate);
249 auto left = acc_.GetValueIn(gate, 0);
250 auto right = acc_.GetValueIn(gate, 1);
251 ASSERT((left == value) || (right == value));
252 bool swap = right == value;
253 if (flag) {
254 op = GateMetaData::GetRevCompareOp(op);
255 }
256 if (swap) {
257 op = GateMetaData::GetSwapCompareOp(op);
258 }
259 auto range = GetRange(swap ? left : right);
260 if (range.IsNone()) {
261 // provide no info for branch range infer.
262 return RangeInfo::ANY();
263 }
264 switch (op) {
265 case TypedBinOp::TYPED_LESS:
266 return RangeInfo(INT32_MIN, range.GetMax() - 1);
267 case TypedBinOp::TYPED_LESSEQ:
268 return RangeInfo(INT32_MIN, range.GetMax());
269 case TypedBinOp::TYPED_GREATER:
270 return RangeInfo(range.GetMin() + 1, INT32_MAX);
271 case TypedBinOp::TYPED_GREATEREQ:
272 return RangeInfo(range.GetMin(), INT32_MAX);
273 case TypedBinOp::TYPED_EQ:
274 return range;
275 case TypedBinOp::TYPED_NOTEQ:
276 return RangeInfo::ANY();
277 default:
278 UNREACHABLE();
279 return RangeInfo::ANY();
280 }
281 }
282
Run()283 void RangeAnalysis::Run()
284 {
285 // visit gate in RPO, propagate range info
286 VisitGraph();
287 }
288
PrintRangeInfo() const289 void RangeAnalysis::PrintRangeInfo() const
290 {
291 std::vector<GateRef> gateList;
292 acc_.GetAllGates(gateList);
293 std::string log = "";
294 for (auto gate : gateList) {
295 if (!IsInt32Type(gate)) {
296 continue;
297 }
298 log = "id:" + std::to_string(acc_.GetId(gate));
299 auto op = acc_.GetOpCode(gate);
300 switch (op) {
301 case OpCode::CONSTANT: {
302 log += " constant";
303 break;
304 }
305 case OpCode::VALUE_SELECTOR: {
306 log += " phi";
307 break;
308 }
309 case OpCode::TYPED_BINARY_OP: {
310 auto binOp = acc_.GetTypedBinaryOp(gate);
311 switch (binOp) {
312 case TypedBinOp::TYPED_ADD:
313 log += " add";
314 break;
315 case TypedBinOp::TYPED_SUB:
316 log += " sub";
317 break;
318 case TypedBinOp::TYPED_SHR:
319 log += " shr";
320 break;
321 case TypedBinOp::TYPED_ASHR:
322 log += " ashr";
323 break;
324 default:
325 log += " other";
326 break;
327 }
328 break;
329 }
330 case OpCode::TYPED_UNARY_OP: {
331 auto unOp = acc_.GetTypedUnAccessor(gate).GetTypedUnOp();
332 switch (unOp) {
333 case TypedUnOp::TYPED_INC:
334 log += " inc";
335 break;
336 case TypedUnOp::TYPED_DEC:
337 log += " dec";
338 break;
339 case TypedUnOp::TYPED_NEG:
340 log += " neg";
341 break;
342 default:
343 log += " other";
344 break;
345 }
346 break;
347 }
348 case OpCode::INDEX_CHECK: {
349 log += " index check";
350 break;
351 }
352 case OpCode::LOAD_ARRAY_LENGTH: {
353 log += " array length";
354 break;
355 }
356 default: {
357 log += " other";
358 break;
359 }
360 }
361 auto range = GetRange(gate);
362 log += " range = [" + std::to_string(range.GetMin()) + "," + std::to_string(range.GetMax()) + "]";
363 LOG_COMPILER(INFO) << log;
364 }
365 }
366 } // namespace panda::ecmascript::kungfu
367