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
20 namespace panda::ecmascript::kungfu {
Initialize()21 void LexicalEnvSpecializationPass::Initialize()
22 {
23 dependChains_.resize(circuit_->GetMaxGateId() + 1, nullptr); // 1: +1 for size
24 GateRef entry = acc_.GetDependRoot();
25 VisitDependEntry(entry);
26 }
27
VisitDependEntry(GateRef gate)28 GateRef LexicalEnvSpecializationPass::VisitDependEntry(GateRef gate)
29 {
30 auto empty = new (chunk_) DependChains(chunk_);
31 return UpdateDependChain(gate, empty);
32 }
33
VisitGate(GateRef gate)34 GateRef 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
VisitOther(GateRef gate)55 GateRef 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
VisitDependSelector(GateRef gate)67 GateRef 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
UpdateDependChain(GateRef gate,DependChains * dependChain)98 GateRef 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
TrySpecializeLdLexVar(GateRef gate)109 GateRef 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
SearchStLexVar(GateRef gate,GateRef ldLexVar,GateRef & result)128 bool 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
CheckStLexVar(GateRef gate,GateRef ldldLexVar)157 bool LexicalEnvSpecializationPass::CheckStLexVar(GateRef gate, GateRef ldldLexVar)
158 {
159 int32_t ldLevel = acc_.TryGetValue(acc_.GetValueIn(ldldLexVar, 0));
160 int32_t ldSlot = acc_.TryGetValue(acc_.GetValueIn(ldldLexVar, 1)); // 1: slot
161
162 int32_t stLevel = acc_.TryGetValue(acc_.GetValueIn(gate, 0));
163 int32_t stSlot = 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
caclulateDistanceToTarget(GateRef startEnv,GateRef targetEnv,int32_t & dis)181 bool 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 curEnv = acc_.GetValueIn(curEnv, acc_.GetNumValueIn(curEnv) - 1); // 1: env value in
201 }
202 return false;
203 }
204
HasNotdomStLexVarOrCall(GateRef gate,GateRef next)205 void LexicalEnvSpecializationPass::HasNotdomStLexVarOrCall(GateRef gate, GateRef next)
206 {
207 ASSERT(acc_.GetOpCode(gate) == OpCode::DEPEND_SELECTOR);
208 ChunkVector<GateRef> vec(chunk_);
209 ChunkVector<GateRef> visited(chunk_);
210 vec.emplace_back(gate);
211 while (!vec.empty()) {
212 GateRef current = vec.back();
213 visited.emplace_back(current);
214 vec.pop_back();
215 if (current != next) {
216 if (acc_.GetOpCode(current) == OpCode::JS_BYTECODE) {
217 LookUpNotDomStLexVarOrCall(current, next);
218 }
219 for (size_t i = 0; i < acc_.GetDependCount(current); i++) {
220 GateRef dependIn = acc_.GetDep(current, i);
221 if (!std::count(visited.begin(), visited.end(), dependIn)) {
222 vec.emplace_back(dependIn);
223 }
224 }
225 }
226 }
227 }
228
LookUpNotDomStLexVarOrCall(GateRef current,GateRef next)229 void LexicalEnvSpecializationPass::LookUpNotDomStLexVarOrCall(GateRef current, GateRef next)
230 {
231 EcmaOpcode ecmaOpcode = acc_.GetByteCodeOpcode(current);
232 if (Bytecodes::IsStLexVarOp(ecmaOpcode)) {
233 if (current != next) {
234 auto iter = notdomStlexvar_.find(next);
235 if (iter == notdomStlexvar_.end()) {
236 notdomStlexvar_[next] = current;
237 }
238 }
239 }
240
241 if (Bytecodes::IsCallOrAccessorOp(ecmaOpcode)) {
242 if (current != next) {
243 auto iter = notDomCall_.find(next);
244 if (iter == notDomCall_.end()) {
245 notDomCall_[next] = current;
246 }
247 }
248 }
249 }
250
HasNotDomIllegalOp(GateRef gate)251 bool LexicalEnvSpecializationPass::HasNotDomIllegalOp(GateRef gate)
252 {
253 if (HasNotDomStLexvar(gate)) {
254 return true;
255 }
256
257 if (HasNotDomCall(gate)) {
258 return true;
259 }
260
261 return false;
262 }
263
HasNotDomStLexvar(GateRef gate)264 bool LexicalEnvSpecializationPass::HasNotDomStLexvar(GateRef gate)
265 {
266 auto iter = notdomStlexvar_.find(gate);
267 if (iter != notdomStlexvar_.end()) {
268 return true;
269 }
270 return false;
271 }
272
HasNotDomCall(GateRef gate)273 bool LexicalEnvSpecializationPass::HasNotDomCall(GateRef gate)
274 {
275 auto iter = notDomCall_.find(gate);
276 if (iter != notDomCall_.end()) {
277 return true;
278 }
279 return false;
280 }
281
LookupStLexvarNode(DependChains * dependChain,GateRef gate)282 GateRef LexicalEnvSpecializationPass::LookupStLexvarNode(DependChains* dependChain, GateRef gate)
283 {
284 GateRef result = Circuit::NullGate();
285 for (auto iter = dependChain->begin(); iter != dependChain->end(); ++iter) {
286 GateRef curGate = iter.GetCurrentGate();
287 if (SearchStLexVar(curGate, gate, result)) {
288 return curGate;
289 } else {
290 if (result == gate) {
291 return Circuit::NullGate();
292 }
293 }
294 }
295 return Circuit::NullGate();
296 }
297
PrintSpecializeId()298 void LexicalEnvSpecializationPass::PrintSpecializeId()
299 {
300 if (enableLog_) {
301 LOG_COMPILER(INFO) << "\033[34m" << "================="
302 << " specialize ldlexvar gate id "
303 << "=================" << "\033[0m";
304 for (auto id : specializeId_) {
305 LOG_COMPILER(INFO) << "ldlexvar id: " << id;
306 }
307 LOG_COMPILER(INFO) << "\033[34m" << "===========================================================" << "\033[0m";
308 }
309 }
310
VisitGate(GateRef gate)311 GateRef GetEnvSpecializationPass::VisitGate(GateRef gate)
312 {
313 auto opcode = acc_.GetOpCode(gate);
314 if (opcode == OpCode::GET_ENV && acc_.GetOpCode(acc_.GetValueIn(gate, 0)) != OpCode::ARG) {
315 GateRef func = acc_.GetValueIn(gate, 0);
316 if (acc_.GetOpCode(func) == OpCode::JS_BYTECODE) {
317 return TryGetReplaceEnv(func);
318 }
319 }
320 return Circuit::NullGate();
321 }
322
323
TryGetReplaceEnv(GateRef func)324 GateRef GetEnvSpecializationPass::TryGetReplaceEnv(GateRef func)
325 {
326 EcmaOpcode ecmaOpcode = acc_.GetByteCodeOpcode(func);
327 switch (ecmaOpcode) {
328 case EcmaOpcode::DEFINEFUNC_IMM8_ID16_IMM8:
329 case EcmaOpcode::DEFINEFUNC_IMM16_ID16_IMM8:
330 case EcmaOpcode::DEFINEMETHOD_IMM8_ID16_IMM8:
331 case EcmaOpcode::DEFINEMETHOD_IMM16_ID16_IMM8: {
332 GateRef replacement = acc_.GetValueIn(func, acc_.GetNumValueIn(func) - 1); // 1: last value in
333 return replacement;
334 }
335 default:
336 return Circuit::NullGate();
337 }
338 return Circuit::NullGate();
339 }
340 }