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#include "ecmascript/compiler/later_elimination.h"
16
17namespace panda::ecmascript::kungfu {
18
19void LaterElimination::Initialize()
20{
21    dependChains_.resize(circuit_->GetMaxGateId() + 1, nullptr); // 1: +1 for size
22    GateRef entry = acc_.GetDependRoot();
23    VisitDependEntry(entry);
24}
25
26GateRef LaterElimination::VisitDependEntry(GateRef gate)
27{
28    auto empty = new (chunk_) DependChains(chunk_);
29    return UpdateDependChain(gate, empty);
30}
31
32GateRef LaterElimination::VisitGate(GateRef gate)
33{
34    auto opcode = acc_.GetOpCode(gate);
35    switch (opcode) {
36        case OpCode::GET_ENV:
37        case OpCode::GET_GLOBAL_ENV:
38        case OpCode::GET_GLOBAL_ENV_OBJ:
39        case OpCode::GET_GLOBAL_ENV_OBJ_HCLASS:
40        case OpCode::GET_GLOBAL_CONSTANT_VALUE:
41        case OpCode::ARRAY_GUARDIAN_CHECK:
42        case OpCode::HCLASS_STABLE_ARRAY_CHECK:
43        case OpCode::HEAP_OBJECT_CHECK:
44        case OpCode::ECMA_OBJECT_CHECK:
45        case OpCode::INT32_UNSIGNED_UPPER_BOUND_CHECK:
46        case OpCode::OVERFLOW_CHECK:
47        case OpCode::VALUE_CHECK_NEG_OVERFLOW:
48        case OpCode::FLOAT64_CHECK_RIGHT_IS_ZERO:
49        case OpCode::INT32_CHECK_RIGHT_IS_ZERO:
50        case OpCode::INT32_DIV_WITH_CHECK:
51        case OpCode::LEX_VAR_IS_HOLE_CHECK:
52        case OpCode::COW_ARRAY_CHECK:
53        case OpCode::FLATTEN_TREE_STRING_CHECK:
54        case OpCode::CHECK_AND_CONVERT:
55        case OpCode::TAGGED_IS_HEAP_OBJECT:
56        case OpCode::IS_MARKER_CELL_VALID:
57        case OpCode::IS_SPECIFIC_OBJECT_TYPE:
58            return TryEliminateGate(gate);
59        case OpCode::DEPEND_SELECTOR:
60            return TryEliminateDependSelector(gate);
61        default:
62            if (acc_.GetDependCount(gate) == 1) { // 1: depend in is 1
63                return TryEliminateOther(gate);
64            }
65    }
66    return Circuit::NullGate();
67}
68
69GateRef LaterElimination::TryEliminateOther(GateRef gate)
70{
71    ASSERT(acc_.GetDependCount(gate) >= 1);
72    auto depIn = acc_.GetDep(gate);
73    auto dependChain = GetDependChain(depIn);
74    if (dependChain == nullptr) {
75        return Circuit::NullGate();
76    }
77    return UpdateDependChain(gate, dependChain);
78}
79
80GateRef LaterElimination::TryEliminateGate(GateRef gate)
81{
82    ASSERT(acc_.GetDependCount(gate) == 1);
83    auto depIn = acc_.GetDep(gate);
84    auto dependChain = GetDependChain(depIn);
85    // dependChain is null
86    if (dependChain == nullptr) {
87        return Circuit::NullGate();
88    }
89    // lookup gate, replace
90    auto preGate = LookupNode(dependChain, gate);
91    if (preGate != Circuit::NullGate()) {
92        return preGate;
93    }
94    // update gate, for others elimination
95    dependChain = dependChain->UpdateNode(gate);
96    return UpdateDependChain(gate, dependChain);
97}
98
99GateRef LaterElimination::TryEliminateDependSelector(GateRef gate)
100{
101    auto state = acc_.GetState(gate);
102    if (acc_.IsLoopHead(state)) {
103        // use loop head as depend chain
104        return TryEliminateOther(gate);
105    }
106
107    auto dependCount = acc_.GetDependCount(gate);
108    for (size_t i = 0; i < dependCount; ++i) {
109        auto depend = acc_.GetDep(gate, i);
110        auto dependChain = GetDependChain(depend);
111        if (dependChain == nullptr) {
112            return Circuit::NullGate();
113        }
114    }
115
116    // all depend done.
117    auto depend = acc_.GetDep(gate);
118    auto dependChain = GetDependChain(depend);
119    DependChains* copy = new (chunk_) DependChains(chunk_);
120    copy->CopyFrom(dependChain);
121    for (size_t i = 1; i < dependCount; ++i) { // 1: second in
122        auto dependIn = acc_.GetDep(gate, i);
123        auto tempChain = GetDependChain(dependIn);
124        copy->Merge(tempChain);
125    }
126    return UpdateDependChain(gate, copy);
127}
128
129GateRef LaterElimination::UpdateDependChain(GateRef gate, DependChains* dependChain)
130{
131    ASSERT(dependChain != nullptr);
132    auto oldDependChain = GetDependChain(gate);
133    if (dependChain->Equals(oldDependChain)) {
134        return Circuit::NullGate();
135    }
136    dependChains_[acc_.GetId(gate)] = dependChain;
137    return gate;
138}
139
140bool LaterElimination::CheckReplacement(GateRef lhs, GateRef rhs)
141{
142    if (!acc_.MetaDataEqu(lhs, rhs)) {
143        if (acc_.GetOpCode(lhs) != acc_.GetOpCode(rhs)) {
144            return false;
145        }
146    }
147    size_t valueCount = acc_.GetNumValueIn(lhs);
148    for (size_t i = 0; i < valueCount; i++) {
149        if (acc_.GetValueIn(lhs, i) != acc_.GetValueIn(rhs, i)) {
150            return false;
151        }
152    }
153    auto opcode = acc_.GetOpCode(lhs);
154    switch (opcode) {
155        case OpCode::GET_GLOBAL_ENV_OBJ:
156        case OpCode::GET_GLOBAL_ENV_OBJ_HCLASS:
157        case OpCode::GET_GLOBAL_CONSTANT_VALUE: {
158            if (acc_.GetIndex(lhs) != acc_.GetIndex(rhs)) {
159                return false;
160            }
161            break;
162        }
163        case OpCode::IS_SPECIFIC_OBJECT_TYPE: {
164            if (acc_.GetJSType(lhs) != acc_.GetJSType(rhs)) {
165                return false;
166            }
167            break;
168        }
169        case OpCode::CHECK_AND_CONVERT: {
170            if (acc_.GetSrcType(lhs) != acc_.GetSrcType(rhs)) {
171                return false;
172            }
173            if (acc_.GetDstType(lhs) != acc_.GetDstType(rhs)) {
174                return false;
175            }
176            break;
177        }
178        default:
179            break;
180    }
181    return true;
182}
183}  // namespace panda::ecmascript::kungfu
184