• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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