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/lexical_env_specialization_pass.h"
17#include "ecmascript/compiler/bytecodes.h"
18#include "ecmascript/compiler/scheduler.h"
19
20namespace panda::ecmascript::kungfu {
21void LexicalEnvSpecializationPass::Initialize()
22{
23    dependChains_.resize(circuit_->GetMaxGateId() + 1, nullptr); // 1: +1 for size
24    GateRef entry = acc_.GetDependRoot();
25    VisitDependEntry(entry);
26}
27
28GateRef LexicalEnvSpecializationPass::VisitDependEntry(GateRef gate)
29{
30    auto empty = new (chunk_) DependChains(chunk_);
31    return UpdateDependChain(gate, empty);
32}
33
34GateRef LexicalEnvSpecializationPass::VisitGate(GateRef gate)
35{
36    auto opcode = acc_.GetOpCode(gate);
37    switch (opcode) {
38        case OpCode::JS_BYTECODE: {
39            EcmaOpcode ecmaOpcode = acc_.GetByteCodeOpcode(gate);
40            if (Bytecodes::IsLdLexVarOp(ecmaOpcode)) {
41                return TrySpecializeLdLexVar(gate);
42            }
43            return VisitOther(gate);
44        }
45        case OpCode::DEPEND_SELECTOR:
46            return VisitDependSelector(gate);
47        default:
48            if (acc_.GetDependCount(gate) == 1) { // 1: depend in is 1
49                return VisitOther(gate);
50            }
51    }
52    return Circuit::NullGate();
53}
54
55GateRef LexicalEnvSpecializationPass::VisitOther(GateRef gate)
56{
57    ASSERT(acc_.GetDependCount(gate) >= 1);
58    auto depIn = acc_.GetDep(gate);
59    auto dependChain = GetDependChain(depIn);
60    if (dependChain == nullptr) {
61        return Circuit::NullGate();
62    }
63    dependChain = dependChain->UpdateNode(gate);
64    return UpdateDependChain(gate, dependChain);
65}
66
67GateRef LexicalEnvSpecializationPass::VisitDependSelector(GateRef gate)
68{
69    auto state = acc_.GetState(gate);
70    if (acc_.IsLoopHead(state)) {
71        // use loop head as depend chain
72        return VisitOther(gate);
73    }
74
75    auto dependCount = acc_.GetDependCount(gate);
76    for (size_t i = 0; i < dependCount; ++i) {
77        auto depend = acc_.GetDep(gate, i);
78        auto dependChain = GetDependChain(depend);
79        if (dependChain == nullptr) {
80            return Circuit::NullGate();
81        }
82    }
83
84    // all depend done.
85    auto depend = acc_.GetDep(gate);
86    auto dependChain = GetDependChain(depend);
87    DependChains* copy = new (chunk_) DependChains(chunk_);
88    copy->CopyFrom(dependChain);
89    for (size_t i = 1; i < dependCount; ++i) { // 1: second in
90        auto dependIn = acc_.GetDep(gate, i);
91        auto tempChain = GetDependChain(dependIn);
92        copy->Merge(tempChain);
93    }
94    HasNotdomStLexVarOrCall(gate, copy->GetHeadGate());
95    return UpdateDependChain(gate, copy);
96}
97
98GateRef LexicalEnvSpecializationPass::UpdateDependChain(GateRef gate, DependChains* dependChain)
99{
100    ASSERT(dependChain != nullptr);
101    auto oldDependChain = GetDependChain(gate);
102    if (dependChain->Equals(oldDependChain)) {
103        return Circuit::NullGate();
104    }
105    dependChains_[acc_.GetId(gate)] = dependChain;
106    return gate;
107}
108
109GateRef LexicalEnvSpecializationPass::TrySpecializeLdLexVar(GateRef gate)
110{
111    ASSERT(acc_.GetDependCount(gate) == 1);
112    auto depIn = acc_.GetDep(gate);
113    auto dependChain = GetDependChain(depIn);
114    // dependChain is null
115    if (dependChain == nullptr) {
116        return Circuit::NullGate();
117    }
118    auto stlexvarGate = LookupStLexvarNode(dependChain, gate);
119    if (stlexvarGate != Circuit::NullGate()) {
120        return acc_.GetValueIn(stlexvarGate, 3); // 3: stlexvar value in
121    }
122
123    // update gate, for others elimination
124    dependChain = dependChain->UpdateNode(gate);
125    return UpdateDependChain(gate, dependChain);
126}
127
128bool LexicalEnvSpecializationPass::SearchStLexVar(GateRef gate, GateRef ldLexVar, GateRef &result)
129{
130    if (HasNotDomIllegalOp(gate)) {
131        result = ldLexVar;
132        return false;
133    }
134
135    if (acc_.GetOpCode(gate) != OpCode::JS_BYTECODE) {
136        return false;
137    }
138
139    EcmaOpcode ecmaOpcode = acc_.GetByteCodeOpcode(gate);
140    if (Bytecodes::IsStLexVarOp(ecmaOpcode)) {
141        if (CheckStLexVar(gate, ldLexVar)) {
142            result = gate;
143            specializeId_.emplace_back(acc_.GetId(ldLexVar));
144            return true;
145        }
146        return false;
147    }
148
149    if (Bytecodes::IsCallOrAccessorOp(ecmaOpcode)) {
150        result = ldLexVar;
151        return false;
152    }
153
154    return false;
155}
156
157bool LexicalEnvSpecializationPass::CheckStLexVar(GateRef gate, GateRef ldldLexVar)
158{
159    int32_t ldLevel = static_cast<int32_t>(acc_.TryGetValue(acc_.GetValueIn(ldldLexVar, 0)));
160    int32_t ldSlot = static_cast<int32_t>(acc_.TryGetValue(acc_.GetValueIn(ldldLexVar, 1))); // 1: slot
161
162    int32_t stLevel = static_cast<int32_t>(acc_.TryGetValue(acc_.GetValueIn(gate, 0)));
163    int32_t stSlot = static_cast<int32_t>(acc_.TryGetValue(acc_.GetValueIn(gate, 1))); // 1: slot
164    if (stSlot != ldSlot) {
165        return false;
166    }
167    int32_t depth = 0;
168    GateRef ldEnv = acc_.GetValueIn(ldldLexVar, 2);
169    GateRef stEnv = acc_.GetValueIn(gate, 2);
170    if (caclulateDistanceToTarget(ldEnv, stEnv, depth)) {
171        return (ldLevel == stLevel + depth);
172    }
173
174    depth = 0;
175    if (caclulateDistanceToTarget(stEnv, ldEnv, depth)) {
176        return (ldLevel + depth == stLevel);
177    }
178    return false;
179}
180
181bool LexicalEnvSpecializationPass::caclulateDistanceToTarget(GateRef startEnv, GateRef targetEnv, int32_t &dis)
182{
183    GateRef curEnv = startEnv;
184    while (true) {
185        if (curEnv == targetEnv) {
186            return true;
187        }
188        if (acc_.GetOpCode(curEnv) == OpCode::GET_ENV) {
189            return false;
190        }
191        if (acc_.GetOpCode(curEnv) != OpCode::JS_BYTECODE) {
192            return false;
193        }
194        EcmaOpcode ecmaOpcode = acc_.GetByteCodeOpcode(curEnv);
195        if (ecmaOpcode != EcmaOpcode::POPLEXENV) {
196            ++dis;
197        } else {
198            --dis;
199        }
200        ASSERT(acc_.GetNumValueIn(curEnv) > 0);
201        curEnv = acc_.GetValueIn(curEnv, acc_.GetNumValueIn(curEnv) - 1); // 1: env value in
202    }
203    return false;
204}
205
206void LexicalEnvSpecializationPass::HasNotdomStLexVarOrCall(GateRef gate, GateRef next)
207{
208    ASSERT(acc_.GetOpCode(gate) == OpCode::DEPEND_SELECTOR);
209    ChunkVector<GateRef> vec(chunk_);
210    ChunkVector<GateRef> visited(chunk_);
211    vec.emplace_back(gate);
212    while (!vec.empty()) {
213        GateRef current = vec.back();
214        visited.emplace_back(current);
215        vec.pop_back();
216        if (current != next) {
217            if (acc_.GetOpCode(current) == OpCode::JS_BYTECODE) {
218                LookUpNotDomStLexVarOrCall(current, next);
219            }
220            for (size_t i = 0; i < acc_.GetDependCount(current); i++) {
221                GateRef dependIn = acc_.GetDep(current, i);
222                if (!std::count(visited.begin(), visited.end(), dependIn)) {
223                    vec.emplace_back(dependIn);
224                }
225            }
226        }
227    }
228}
229
230void LexicalEnvSpecializationPass::LookUpNotDomStLexVarOrCall(GateRef current, GateRef next)
231{
232    EcmaOpcode ecmaOpcode = acc_.GetByteCodeOpcode(current);
233    if (Bytecodes::IsStLexVarOp(ecmaOpcode)) {
234        if (current != next) {
235            auto iter = notdomStlexvar_.find(next);
236            if (iter == notdomStlexvar_.end()) {
237                notdomStlexvar_[next] = current;
238            }
239        }
240    }
241
242    if (Bytecodes::IsCallOrAccessorOp(ecmaOpcode)) {
243        if (current != next) {
244            auto iter = notDomCall_.find(next);
245            if (iter == notDomCall_.end()) {
246                notDomCall_[next] = current;
247            }
248        }
249    }
250}
251
252bool LexicalEnvSpecializationPass::HasNotDomIllegalOp(GateRef gate)
253{
254    if (HasNotDomStLexvar(gate)) {
255        return true;
256    }
257
258    if (HasNotDomCall(gate)) {
259        return true;
260    }
261
262    return false;
263}
264
265bool LexicalEnvSpecializationPass::HasNotDomStLexvar(GateRef gate)
266{
267    auto iter = notdomStlexvar_.find(gate);
268    if (iter != notdomStlexvar_.end()) {
269        return true;
270    }
271    return false;
272}
273
274bool LexicalEnvSpecializationPass::HasNotDomCall(GateRef gate)
275{
276    auto iter = notDomCall_.find(gate);
277    if (iter != notDomCall_.end()) {
278        return true;
279    }
280    return false;
281}
282
283GateRef LexicalEnvSpecializationPass::LookupStLexvarNode(DependChains* dependChain, GateRef gate)
284{
285    GateRef result = Circuit::NullGate();
286    for (auto iter = dependChain->begin(); iter != dependChain->end(); ++iter) {
287        GateRef curGate = iter.GetCurrentGate();
288        if (SearchStLexVar(curGate, gate, result)) {
289            return curGate;
290        } else {
291            if (result == gate) {
292                return Circuit::NullGate();
293            }
294        }
295    }
296    return Circuit::NullGate();
297}
298
299void LexicalEnvSpecializationPass::PrintSpecializeId()
300{
301    if (enableLog_) {
302        LOG_COMPILER(INFO) << "\033[34m" << "================="
303                           << " specialize ldlexvar gate id "
304                           << "=================" << "\033[0m";
305        for (auto id : specializeId_) {
306            LOG_COMPILER(INFO) << "ldlexvar id: " << id;
307        }
308        LOG_COMPILER(INFO) << "\033[34m" << "===========================================================" << "\033[0m";
309    }
310}
311
312GateRef GetEnvSpecializationPass::VisitGate(GateRef gate)
313{
314    auto opcode = acc_.GetOpCode(gate);
315    if (opcode == OpCode::GET_ENV && acc_.GetOpCode(acc_.GetValueIn(gate, 0)) != OpCode::ARG) {
316        GateRef func = acc_.GetValueIn(gate, 0);
317        if (acc_.GetOpCode(func) == OpCode::JS_BYTECODE) {
318            return TryGetReplaceEnv(func);
319        }
320    }
321    return Circuit::NullGate();
322}
323
324
325GateRef GetEnvSpecializationPass::TryGetReplaceEnv(GateRef func)
326{
327    ASSERT(acc_.GetNumValueIn(func) >= 1);
328    EcmaOpcode ecmaOpcode = acc_.GetByteCodeOpcode(func);
329    switch (ecmaOpcode) {
330        case EcmaOpcode::DEFINEFUNC_IMM8_ID16_IMM8:
331        case EcmaOpcode::DEFINEFUNC_IMM16_ID16_IMM8:
332        case EcmaOpcode::DEFINEMETHOD_IMM8_ID16_IMM8:
333        case EcmaOpcode::DEFINEMETHOD_IMM16_ID16_IMM8: {
334            GateRef replacement = acc_.GetValueIn(func, acc_.GetNumValueIn(func) - 1); // 1: last value in
335            return replacement;
336        }
337        default:
338            return Circuit::NullGate();
339    }
340    return Circuit::NullGate();
341}
342}