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/early_elimination.h"
17
18namespace panda::ecmascript::kungfu {
19
20void EarlyElimination::Initialize()
21{
22    dependChains_.resize(circuit_->GetMaxGateId() + 1, nullptr); // 1: +1 for size
23    renames_.resize(circuit_->GetMaxGateId() + 1, Circuit::NullGate()); // 1: +1 for size
24    GateRef entry = acc_.GetDependRoot();
25    VisitDependEntry(entry);
26}
27
28DependInfoNode* EarlyElimination::GetLoopDependInfo(GateRef depend)
29{
30    auto depIn = acc_.GetDep(depend);
31    auto dependChain = GetDependChain(depIn);
32    if (dependChain == nullptr) {
33        return nullptr;
34    }
35    auto newChain = new (chunk_) DependInfoNode(chunk_);
36    newChain->CopyFrom(dependChain);
37    ChunkSet<GateRef> visited(chunk_);
38    ChunkQueue<GateRef> workList(chunk_);
39    workList.push(depend);
40    visited.insert(acc_.GetDep(depend));
41    while (!workList.empty()) {
42        auto curDep = workList.front();
43        workList.pop();
44        if (visited.count(curDep)) {
45            continue;
46        }
47        if (!acc_.IsNotWrite(curDep)) {
48            newChain = UpdateWrite(curDep, newChain);
49        }
50        visited.insert(curDep);
51        auto depCount = acc_.GetDependCount(curDep);
52        for (size_t i = 0; i < depCount; ++i) {
53            workList.push(acc_.GetDep(curDep, i));
54        }
55    }
56    return newChain;
57}
58
59GateRef EarlyElimination::VisitDependEntry(GateRef gate)
60{
61    auto empty = new (chunk_) DependInfoNode(chunk_);
62    return UpdateDependChain(gate, empty);
63}
64
65GateRef EarlyElimination::VisitGate(GateRef gate)
66{
67    auto opcode = acc_.GetOpCode(gate);
68    switch (opcode) {
69        case OpCode::LOAD_PROPERTY:
70        case OpCode::LOAD_ELEMENT:
71        case OpCode::LOAD_ARRAY_LENGTH:
72        case OpCode::LOAD_TYPED_ARRAY_LENGTH:
73        case OpCode::TYPED_ARRAY_CHECK:
74        case OpCode::OBJECT_TYPE_CHECK:
75        case OpCode::STABLE_ARRAY_CHECK:
76        case OpCode::INDEX_CHECK:
77        case OpCode::ELEMENTSKIND_CHECK:
78        case OpCode::TYPED_CALL_CHECK:
79        case OpCode::LOAD_CONST_OFFSET:
80        case OpCode::LOAD_HCLASS_FROM_CONSTPOOL:
81        case OpCode::TYPED_BINARY_OP:
82        case OpCode::TYPED_UNARY_OP:
83        case OpCode::JSINLINETARGET_TYPE_CHECK:
84        case OpCode::PROTOTYPE_CHECK:
85        case OpCode::LOAD_GETTER:
86        case OpCode::LOAD_SETTER:
87        case OpCode::ECMA_STRING_CHECK:
88        case OpCode::BUILTIN_PROTOTYPE_HCLASS_CHECK:
89        case OpCode::TYPE_OF_CHECK:
90        case OpCode::ARRAY_CONSTRUCTOR_CHECK:
91        case OpCode::FLOAT32_ARRAY_CONSTRUCTOR_CHECK:
92        case OpCode::OBJECT_CONSTRUCTOR_CHECK:
93        case OpCode::BOOLEAN_CONSTRUCTOR_CHECK:
94        case OpCode::PROTO_CHANGE_MARKER_CHECK:
95        case OpCode::MONO_LOAD_PROPERTY_ON_PROTO:
96        case OpCode::LOAD_BUILTIN_OBJECT:
97        case OpCode::LOOK_UP_HOLDER:
98        case OpCode::IS_CALLABLE_CHECK:
99            return TryEliminateGate(gate);
100        case OpCode::STATE_SPLIT:
101            if (enableFrameStateElimination_) {
102                return TryEliminateFrameState(gate);
103            }
104            break;
105        case OpCode::DEPEND_SELECTOR:
106            return TryEliminateDependSelector(gate);
107        default:
108            if (acc_.GetDependCount(gate) == 1) { // 1: depend in is 1
109                return TryEliminateOther(gate);
110            }
111            break;
112    }
113    return Circuit::NullGate();
114}
115
116GateRef EarlyElimination::TryEliminateOther(GateRef gate)
117{
118    ASSERT(acc_.GetDependCount(gate) >= 1);
119    auto depIn = acc_.GetDep(gate);
120    auto dependChain = GetDependChain(depIn);
121    if (dependChain == nullptr) {
122        return Circuit::NullGate();
123    }
124
125    if (!acc_.IsNotWrite(gate)) {
126        dependChain = UpdateWrite(gate, dependChain);
127    }
128
129    return UpdateDependChain(gate, dependChain);
130}
131
132GateRef EarlyElimination::TryEliminateGate(GateRef gate)
133{
134    ASSERT(acc_.GetDependCount(gate) == 1);
135    auto depIn = acc_.GetDep(gate);
136    auto dependChain = GetDependChain(depIn);
137    // dependChain is null
138    if (dependChain == nullptr) {
139        return Circuit::NullGate();
140    }
141
142    if (!acc_.IsNotWrite(gate)) {
143        dependChain = UpdateWrite(gate, dependChain);
144        return UpdateDependChain(gate, dependChain);
145    }
146
147    auto numIns = acc_.GetNumValueIn(gate);
148    for (size_t i = 0; i < numIns; ++i) {
149        auto origin = acc_.GetValueIn(gate, i);
150        auto checkd = dependChain->LookupCheckedNode(this, origin);
151        if (origin != checkd) {
152            acc_.ReplaceValueIn(gate, checkd, i);
153        }
154    }
155
156    // lookup gate, replace
157    auto preGate = dependChain->LookupNode(this, gate);
158    if (preGate != Circuit::NullGate()) {
159        return preGate;
160    }
161    // update gate, for others elimination
162    dependChain = dependChain->UpdateNode(gate);
163    return UpdateDependChain(gate, dependChain);
164}
165
166GateRef EarlyElimination::TryEliminateFrameState(GateRef gate)
167{
168    ASSERT(acc_.GetOpCode(gate) == OpCode::STATE_SPLIT);
169    auto depIn = acc_.GetDep(gate);
170    auto dependChain = GetDependChain(depIn);
171    // dependChain is null
172    if (dependChain == nullptr) {
173        return Circuit::NullGate();
174    }
175    // lookup gate, replace
176    auto preFrame = dependChain->LookupFrameState();
177    auto curFrame = acc_.GetFrameState(gate);
178    if ((preFrame != Circuit::NullGate()) && (preFrame != curFrame) &&
179        acc_.GetFrameState(preFrame) == acc_.GetFrameState(curFrame)) {
180        acc_.UpdateAllUses(curFrame, preFrame);
181        auto frameValues = acc_.GetValueIn(curFrame, 1); // 1: frameValues
182        acc_.DeleteGate(frameValues);
183        acc_.DeleteGate(curFrame);
184        return depIn;
185    } else {
186        dependChain = dependChain->UpdateFrameState(curFrame);
187    }
188    // update gate, for others elimination
189
190    return UpdateDependChain(gate, dependChain);
191}
192
193GateRef EarlyElimination::TryEliminateDependSelector(GateRef gate)
194{
195    auto state = acc_.GetState(gate);
196    if (acc_.IsLoopHead(state)) {
197        auto dependChain = GetLoopDependInfo(gate);
198        if (dependChain == nullptr) {
199            return Circuit::NullGate();
200        }
201        return UpdateDependChain(gate, dependChain);
202    }
203
204    auto dependCount = acc_.GetDependCount(gate);
205    for (size_t i = 0; i < dependCount; ++i) {
206        auto depend = acc_.GetDep(gate, i);
207        auto dependChain = GetDependChain(depend);
208        if (dependChain == nullptr) {
209            return Circuit::NullGate();
210        }
211    }
212
213    // all depend done.
214    auto depend = acc_.GetDep(gate);
215    auto dependChain = GetDependChain(depend);
216    DependInfoNode* copy = new (chunk_) DependInfoNode(chunk_);
217    copy->CopyFrom(dependChain);
218    for (size_t i = 1; i < dependCount; ++i) { // 1: second in
219        auto dependIn = acc_.GetDep(gate, i);
220        auto tempChain = GetDependChain(dependIn);
221        copy->Merge(this, tempChain);
222    }
223    return UpdateDependChain(gate, copy);
224}
225
226GateRef EarlyElimination::UpdateDependChain(GateRef gate, DependInfoNode* dependChain)
227{
228    ASSERT(dependChain != nullptr);
229    auto oldDependChain = GetDependChain(gate);
230    if (dependChain->Equals(oldDependChain)) {
231        return Circuit::NullGate();
232    }
233    dependChains_[acc_.GetId(gate)] = dependChain;
234    return gate;
235}
236
237DependInfoNode* EarlyElimination::UpdateWrite(GateRef gate, DependInfoNode* dependInfo)
238{
239    if (!enableMemoryAnalysis_) {
240        return new (chunk_) DependInfoNode(chunk_);
241    }
242    auto op = acc_.GetOpCode(gate);
243    switch (op) {
244        case OpCode::STORE_PROPERTY:
245        case OpCode::STORE_PROPERTY_NO_BARRIER:
246        case OpCode::STORE_CONST_OFFSET:
247        case OpCode::STORE_ELEMENT:
248        case OpCode::STORE_MEMORY:
249        case OpCode::MIGRATE_ARRAY_WITH_KIND:
250        case OpCode::MONO_STORE_PROPERTY_LOOK_UP_PROTO:
251        case OpCode::MONO_STORE_PROPERTY:
252            return dependInfo->UpdateStoreProperty(this, gate);
253        default:
254            return new (chunk_) DependInfoNode(chunk_);
255    }
256}
257
258bool EarlyElimination::MayAccessOneMemory(GateRef lhs, GateRef rhs)
259{
260    auto rop = acc_.GetOpCode(rhs);
261    auto lop = acc_.GetOpCode(lhs);
262    switch (rop) {
263        case OpCode::STORE_MEMORY:
264            ASSERT(acc_.GetMemoryType(rhs) == MemoryType::ELEMENT_TYPE);
265            return acc_.GetOpCode(lhs) == OpCode::LOAD_ELEMENT;
266        case OpCode::MIGRATE_ARRAY_WITH_KIND: {
267            if (lop == OpCode::LOAD_ELEMENT) {
268                GateRef lopValueIn = acc_.GetValueIn(lhs, 0); // loadelement receiver
269                GateRef ropValueIn = acc_.GetValueIn(rhs, 0); // migrate receiver
270                return lopValueIn == ropValueIn;
271            }
272            return false;
273        }
274        case OpCode::STORE_ELEMENT: {
275            if (lop == OpCode::LOAD_ELEMENT) {
276                bool lopIsTypedArray = acc_.TypedOpIsTypedArray(lhs, TypedOpKind::TYPED_LOAD_OP);
277                bool ropIsTypedArray = acc_.TypedOpIsTypedArray(rhs, TypedOpKind::TYPED_STORE_OP);
278                return lopIsTypedArray == ropIsTypedArray;
279            }
280            return false;
281        }
282        case OpCode::STORE_PROPERTY:
283        case OpCode::STORE_PROPERTY_NO_BARRIER: {
284            if (lop == OpCode::LOAD_PROPERTY) {
285                auto loff = acc_.GetValueIn(lhs, 1);
286                auto roff = acc_.GetValueIn(rhs, 1);
287                ASSERT(acc_.GetOpCode(loff) == OpCode::CONSTANT);
288                ASSERT(acc_.GetOpCode(roff) == OpCode::CONSTANT);
289                return loff == roff;
290            } else if (lop == OpCode::PROTOTYPE_CHECK) {
291                auto lindex = acc_.GetHClassIndex(lhs);
292                auto rindex = acc_.GetHClassIndex(rhs);
293                return (lindex == 0) || (rindex == 0) || (lindex != rindex);
294            }
295            break;
296        }
297        case OpCode::STORE_CONST_OFFSET: {
298            if (lop == OpCode::LOAD_CONST_OFFSET) {
299                auto loff = acc_.GetOffset(lhs);
300                auto roff = acc_.GetOffset(rhs);
301                return loff == roff;
302            }
303            break;
304        }
305        case OpCode::LOAD_PROPERTY:
306        case OpCode::MONO_LOAD_PROPERTY_ON_PROTO:
307            if (acc_.GetGateType(lhs).Value() != acc_.GetGateType(rhs).Value()) {
308                return false;
309            }
310            break;
311        default:
312            break;
313    }
314    return false;
315}
316
317bool EarlyElimination::CompareOrder(GateRef lhs, GateRef rhs)
318{
319    return visitor_->GetGateOrder(lhs) < visitor_->GetGateOrder(rhs);
320}
321
322bool EarlyElimination::CheckReplacement(GateRef lhs, GateRef rhs)
323{
324    if (!acc_.MetaDataEqu(lhs, rhs)) {
325        if (acc_.GetOpCode(lhs) != acc_.GetOpCode(rhs)) {
326            return false;
327        }
328    }
329
330    size_t valueCount = acc_.GetNumValueIn(lhs);
331    for (size_t i = 0; i < valueCount; i++) {
332        if (Rename(acc_.GetValueIn(lhs, i)) != Rename(acc_.GetValueIn(rhs, i))) {
333            return false;
334        }
335    }
336
337    auto opcode = acc_.GetOpCode(lhs);
338    switch (opcode) {
339        case OpCode::LOAD_ELEMENT: {
340            if (acc_.GetTypedLoadOp(lhs) != acc_.GetTypedLoadOp(rhs)) {
341                return false;
342            }
343            break;
344        }
345        case OpCode::TYPED_BINARY_OP: {
346            auto lhsOp = acc_.GetTypedBinaryOp(lhs);
347            auto rhsOp = acc_.GetTypedBinaryOp(rhs);
348            if (lhsOp != rhsOp) {
349                return false;
350            }
351            break;
352        }
353        case OpCode::TYPED_UNARY_OP: {
354            auto lhsOp = acc_.GetTypedUnAccessor(lhs).GetTypedUnOp();
355            auto rhsOp = acc_.GetTypedUnAccessor(rhs).GetTypedUnOp();
356            if (lhsOp != rhsOp) {
357                return false;
358            }
359            break;
360        }
361        case OpCode::TYPED_ARRAY_CHECK: {
362            TypedArrayMetaDataAccessor lhsAccessor = acc_.GetTypedArrayMetaDataAccessor(lhs);
363            TypedArrayMetaDataAccessor rhsAccessor = acc_.GetTypedArrayMetaDataAccessor(rhs);
364            if ((lhsAccessor.GetParamType() != rhsAccessor.GetParamType()) ||
365                (lhsAccessor.GetOnHeapMode() != rhsAccessor.GetOnHeapMode())) {
366                return false;
367            }
368            break;
369        }
370        case OpCode::TYPE_OF_CHECK: {
371            if (acc_.GetParamType(lhs) != acc_.GetParamType(rhs)) {
372                return false;
373            }
374            break;
375        }
376        case OpCode::PROTOTYPE_CHECK: {
377            if (acc_.GetHClassIndex(lhs) != acc_.GetHClassIndex(rhs)) {
378                return false;
379            }
380            break;
381        }
382        case OpCode::LOAD_CONST_OFFSET: {
383            if (acc_.GetOffset(lhs) != acc_.GetOffset(rhs)) {
384                return false;
385            }
386            if (acc_.GetMachineType(lhs) != acc_.GetMachineType(rhs)) {
387                return false;
388            }
389            if (acc_.GetMemoryAttribute(lhs).Value() != acc_.GetMemoryAttribute(rhs).Value()) {
390                return false;
391            }
392            break;
393        }
394        case OpCode::LOAD_HCLASS_FROM_CONSTPOOL: {
395            if (acc_.GetIndex(lhs) != acc_.GetIndex(rhs)) {
396                return false;
397            }
398            break;
399        }
400        case OpCode::JSINLINETARGET_TYPE_CHECK: {
401            if (acc_.GetFuncGT(lhs) != acc_.GetFuncGT(rhs)) {
402                return false;
403            }
404            break;
405        }
406        case OpCode::ARRAY_CONSTRUCTOR_CHECK:
407        case OpCode::FLOAT32_ARRAY_CONSTRUCTOR_CHECK:
408        case OpCode::OBJECT_CONSTRUCTOR_CHECK:
409        case OpCode::BOOLEAN_CONSTRUCTOR_CHECK: {
410            if (acc_.GetValueIn(lhs) != acc_.GetValueIn(rhs)) {
411                return false;
412            }
413            break;
414        }
415        case OpCode::LOAD_BUILTIN_OBJECT: {
416            if (acc_.GetIndex(lhs) != acc_.GetIndex(rhs)) {
417                return false;
418            }
419            break;
420        }
421        default:
422            break;
423    }
424    return true;
425}
426
427bool EarlyElimination::CheckRenameReplacement(GateRef lhs, GateRef rhs)
428{
429    auto opcode = acc_.GetOpCode(lhs);
430    switch (opcode) {
431        case OpCode::INDEX_CHECK: {
432            auto index = acc_.GetValueIn(lhs, 1);
433            if (Rename(index) == Rename(rhs)) {
434                return true;
435            }
436            break;
437        }
438        default:
439            break;
440    }
441    return false;
442}
443
444GateRef EarlyElimination::Rename(GateRef gate)
445{
446    ChunkStack<GateRef> gateStack(chunk_);
447    while (true) {
448        auto op = acc_.GetOpCode(gate);
449        bool renamed = false;
450        switch (op) {
451            case OpCode::INDEX_CHECK: {
452                GateRef ans = renames_[acc_.GetId(gate)];
453                if (ans == Circuit::NullGate()) {
454                    renamed = true;
455                    gateStack.push(gate);
456                    gate = acc_.GetValueIn(gate, 1);
457                } else {
458                    gate = ans;
459                }
460                break;
461            }
462            default:
463                break;
464        }
465        if (!renamed) {
466            break;
467        }
468    }
469    while (!gateStack.empty()) {
470        auto topGate = gateStack.top();
471        gateStack.pop();
472        renames_[acc_.GetId(topGate)] = gate;
473    }
474    return gate;
475}
476
477void DependInfoNode::Merge(EarlyElimination* elimination, DependInfoNode* that)
478{
479    auto siz = this->size_; // size of lhs-chain
480    auto lhs = this->head_;
481    auto rhs = that->head_;
482    ChunkStack<GateRef> gateStack(chunk_);
483    while (lhs != rhs) {
484        if (lhs == nullptr || rhs == nullptr) {
485            siz = 0;
486            lhs = nullptr;
487            break;
488        } else if (lhs->gate == rhs->gate) {
489            gateStack.push(lhs->gate);
490            siz--;
491            lhs = lhs->next;
492            rhs = rhs->next;
493        } else if (elimination->CompareOrder(lhs->gate, rhs->gate)) {
494            rhs = rhs->next;
495        } else {
496            siz--;
497            lhs = lhs->next;
498        }
499    }
500    // lhs : common suffix of lhs-chain and rhs-chain
501    this->head_ = lhs;
502    this->size_ = siz;
503    while (!gateStack.empty()) {
504        Node* node = chunk_->New<Node>(gateStack.top(), head_);
505        gateStack.pop();
506        this->size_++;
507        this->head_ = node;
508    }
509    if (this->frameState_ != that->frameState_) {
510        this->frameState_ = Circuit::NullGate();
511    }
512}
513
514bool DependInfoNode::Equals(DependInfoNode* that)
515{
516    if (that == nullptr) {
517        return false;
518    }
519    if (size_ != that->size_ || frameState_ != that->frameState_) {
520        return false;
521    }
522    auto lhs = this->head_;
523    auto rhs = that->head_;
524    while (lhs != rhs) {
525        if (lhs->gate != rhs->gate) {
526            return false;
527        }
528        lhs = lhs->next;
529        rhs = rhs->next;
530    }
531    return true;
532}
533
534GateRef DependInfoNode::LookupFrameState() const
535{
536    return frameState_;
537}
538
539GateRef DependInfoNode::LookupCheckedNode(EarlyElimination* elimination, GateRef gate)
540{
541    for (Node* node = head_; node != nullptr; node = node->next) {
542        if (elimination->CheckRenameReplacement(node->gate, gate)) {
543            return node->gate;
544        }
545    }
546    return gate;
547}
548
549void DependInfoNode::GetGates(std::vector<GateRef>& gates) const
550{
551    ChunkStack<GateRef> st(chunk_);
552    for (Node* node = head_; node != nullptr; node = node->next) {
553        st.push(node->gate);
554    }
555    while (!st.empty()) {
556        gates.emplace_back(st.top());
557        st.pop();
558    }
559}
560
561GateRef DependInfoNode::LookupNode(EarlyElimination* elimination, GateRef gate)
562{
563    for (Node* node = head_; node != nullptr; node = node->next) {
564        if (elimination->CheckReplacement(node->gate, gate)) {
565            return node->gate;
566        }
567    }
568    return Circuit::NullGate();
569}
570
571DependInfoNode* DependInfoNode::UpdateNode(GateRef gate)
572{
573    // assign node->next to head
574    Node* node = chunk_->New<Node>(gate, head_);
575    DependInfoNode* that = new (chunk_) DependInfoNode(chunk_);
576    // assign head to node
577    that->head_ = node;
578    that->size_ = size_ + 1;
579    that->frameState_ = frameState_;
580    return that;
581}
582
583DependInfoNode* DependInfoNode::UpdateFrameState(GateRef framestate)
584{
585    // assign node->next to head
586    DependInfoNode* that = new (chunk_) DependInfoNode(chunk_);
587    // assign head to node
588    that->head_ = head_;
589    that->size_ = size_;
590    that->frameState_ = framestate;
591    return that;
592}
593
594DependInfoNode* DependInfoNode::UpdateStoreProperty(EarlyElimination* elimination, GateRef gate)
595{
596    DependInfoNode* that = new (chunk_) DependInfoNode(chunk_);
597    ChunkStack<GateRef> gateStack(chunk_);
598    for (Node* node = head_; node != nullptr; node = node->next) {
599        if (!elimination->MayAccessOneMemory(node->gate, gate)) {
600            gateStack.push(node->gate);
601        }
602    }
603    while (!gateStack.empty()) {
604        that = that->UpdateNode(gateStack.top());
605        gateStack.pop();
606    }
607    return that;
608}
609}  // namespace panda::ecmascript::kungfu
610