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
18namespace panda::ecmascript::kungfu {
19
20GateRef 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
31RangeInfo RangeAnalysis::GetRange(GateRef gate) const
32{
33    ASSERT(acc_.GetId(gate) < rangeInfos_.size());
34    return rangeInfos_[acc_.GetId(gate)];
35}
36
37bool 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
46GateRef 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
75GateRef 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
89GateRef RangeAnalysis::VisitOthers(GateRef gate)
90{
91    if (!IsInt32Type(gate)) {
92        return Circuit::NullGate();
93    }
94    return UpdateRange(gate, RangeInfo::ANY());
95}
96
97GateRef 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
106GateRef 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
135GateRef 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
167GateRef 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
176GateRef RangeAnalysis::VisitLoadArrayLength(GateRef gate)
177{
178    ASSERT(IsInt32Type(gate));
179    return UpdateRange(gate, RangeInfo(0, INT32_MAX));
180}
181
182GateRef RangeAnalysis::VisitLoadStringLength(GateRef gate)
183{
184    ASSERT(IsInt32Type(gate));
185    return UpdateRange(gate, RangeInfo(0, INT32_MAX));
186}
187
188GateRef RangeAnalysis::VisitLoadMapSize(GateRef gate)
189{
190    ASSERT(IsInt32Type(gate));
191    return UpdateRange(gate, RangeInfo(0, INT32_MAX));
192}
193
194GateRef 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
202GateRef 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
209template<TypedBinOp Op>
210RangeInfo 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
231template<TypedBinOp Op>
232RangeInfo 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
253RangeInfo 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
277RangeInfo 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
314void 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