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/state_split_linearizer.h"
17#include "ecmascript/compiler/scheduler.h"
18
19namespace panda::ecmascript::kungfu {
20void StateSplitLinearizer::Run()
21{
22    graphLinearizer_.SetScheduleJSOpcode();
23    graphLinearizer_.LinearizeGraph();
24    LinearizeStateSplit();
25    if (IsLogEnabled()) {
26        LOG_COMPILER(INFO) << "";
27        LOG_COMPILER(INFO) << "\033[34m"
28                           << "===================="
29                           << " After state split linearizer "
30                           << "[" << GetMethodName() << "]"
31                           << "===================="
32                           << "\033[0m";
33        circuit_->PrintAllGatesWithBytecode();
34        LOG_COMPILER(INFO) << "\033[34m" << "========================= End ==========================" << "\033[0m";
35    }
36#ifndef NDEBUG
37    graphLinearizer_.Reset();
38    graphLinearizer_.EnableScheduleUpperBound();
39    graphLinearizer_.SetScheduleJSOpcode();
40    graphLinearizer_.LinearizeGraph();
41    if (IsLogEnabled()) {
42        LOG_COMPILER(INFO) << "";
43        LOG_COMPILER(INFO) << "\033[34m"
44                           << "===================="
45                           << " verify split linearizer "
46                           << "[" << GetMethodName() << "]"
47                           << "===================="
48                           << "\033[0m";
49        graphLinearizer_.PrintGraph("Build Basic Block");
50        LOG_COMPILER(INFO) << "\033[34m" << "========================= End ==========================" << "\033[0m";
51    }
52#endif
53}
54
55struct RegionEdge {
56    GateRef stateOut {Circuit::NullGate()};
57    GateRef dependOut {Circuit::NullGate()};
58    GateRef frameStateOut {Circuit::NullGate()};
59};
60
61struct PendingGateRegionEdge {
62    explicit PendingGateRegionEdge(GateRegion* from, GateRegion* to,
63        GateRef dependStart, size_t index) : from(from), to(to),
64        dependStart(dependStart), index(index) {}
65
66    GateRegion* from;
67    GateRegion* to;
68    GateRef dependStart;
69    size_t index;
70};
71
72class RegionStateDependMap {
73public:
74    explicit RegionStateDependMap(Chunk* chunk) : regionMap_(chunk) {}
75    RegionEdge& GetEdge(GateRegion* from, GateRegion* to)
76    {
77        return regionMap_[std::make_pair(from->GetId(), to->GetId())];
78    }
79private:
80    ChunkMap<std::pair<size_t, size_t>, RegionEdge> regionMap_;
81};
82
83class StateDependBuilder {
84public:
85    explicit StateDependBuilder(StateSplitLinearizer* linearizer, Chunk* chunk)
86        : linearizer_(linearizer), pendingList_(chunk),
87        acc_(linearizer->circuit_), map_(chunk), pendingEdges_(chunk) {}
88
89    void Run(ChunkVector<GateRegion*>& regionList)
90    {
91        maxGateId_ = acc_.GetCircuit()->GetMaxGateId();
92        replacement_.SetDepend(acc_.GetDependRoot());
93        dependStart_ = replacement_.Depend();
94        auto entry = regionList.front();
95        acc_.GetCircuit()->AdvanceTime();
96        entry->SetVisited(acc_);
97        ASSERT(pendingList_.empty());
98        pendingList_.emplace_back(entry);
99        while (!pendingList_.empty()) {
100            auto curRegion = pendingList_.back();
101            pendingList_.pop_back();
102            VisitRegion(curRegion);
103            for (auto succ : curRegion->succs_) {
104                if (!succ->IsVisited(acc_)) {
105                    succ->SetVisited(acc_);
106                    pendingList_.emplace_back(succ);
107                }
108            }
109        }
110        ConnectPendingRegionEdges();
111        DeleteUnusedGates();
112    }
113
114    void DeleteUnusedGates()
115    {
116        std::vector<GateRef> gateList;
117        auto circuit = acc_.GetCircuit();
118        circuit->GetAllGates(gateList);
119
120        for (const auto &gate : gateList) {
121            if (acc_.GetMark(gate) == MarkCode::NO_MARK &&
122                !acc_.IsProlog(gate) && !acc_.IsRoot(gate) &&
123                acc_.GetId(gate) <= maxGateId_) {
124                acc_.DeleteGate(gate);
125            }
126        }
127    }
128
129    void TryFindDependStart(GateRegion* curRegion)
130    {
131        // 0: is state
132        for (; currentIndex_ > 0; currentIndex_--) {
133            auto curGate = curRegion->gateList_[currentIndex_];
134            auto op = acc_.GetOpCode(curGate);
135            if (op == OpCode::DEPEND_SELECTOR || op == OpCode::DEPEND_RELAY) {
136                replacement_.SetDepend(curGate);
137                dependStart_ = curGate;
138                acc_.SetMark(curGate, MarkCode::VISITED);
139            } else {
140                VisitGate(curGate);
141            }
142            if (dependStart_ != Circuit::NullGate()) {
143                currentIndex_--;
144                break;
145            }
146        }
147    }
148
149    void VisitRegion(GateRegion* curRegion)
150    {
151        ASSERT(curRegion->gateList_.size() > 0);
152        replacement_.SetState(curRegion->GetState());
153        currentIndex_ = static_cast<int32_t>(curRegion->gateList_.size() - 1); // 1: -1 for size
154        TryLoadDependStart(curRegion);
155        if (dependStart_ == Circuit::NullGate()) {
156            TryFindDependStart(curRegion);
157        }
158        ConnectStateDepend(curRegion);
159        for (; currentIndex_ > 0; currentIndex_--) {
160            auto curGate = curRegion->gateList_[currentIndex_];
161            VisitGate(curGate);
162        }
163        StoreStateDepend(curRegion);
164    }
165
166    void ProcessStateDepend(GateRef currentGate)
167    {
168        auto currentState = replacement_.State();
169        auto currentDepend = replacement_.Depend();
170        if (acc_.GetStateCount(currentGate) > 0) {
171            ASSERT(acc_.GetStateCount(currentGate) == 1);
172            auto stateInput = acc_.GetState(currentGate);
173            if (currentState != stateInput) {
174                acc_.ReplaceStateIn(currentGate, currentState);
175            }
176            if (!acc_.IsVirtualState(currentGate) && !acc_.IsFixed(currentGate)) {
177                replacement_.SetState(currentGate);
178            }
179        }
180        if (acc_.GetDependCount(currentGate) > 0) {
181            ASSERT(acc_.GetDependCount(currentGate) == 1);
182            auto dependInput = acc_.GetDep(currentGate);
183            if (currentDepend != dependInput) {
184                acc_.ReplaceDependIn(currentGate, currentDepend);
185            }
186            replacement_.SetDepend(currentGate);
187        }
188    }
189
190    void VisitGate(GateRef gate)
191    {
192        acc_.SetMark(gate, MarkCode::VISITED);
193        auto& lowering = linearizer_->lcrLowering_;
194        auto op = acc_.GetOpCode(gate);
195        switch (op) {
196            case OpCode::FRAME_STATE:
197                frameState_ = gate;
198                break;
199            case OpCode::STATE_SPLIT:
200            case OpCode::DEPEND_RELAY:
201                acc_.DeleteGate(gate);
202                return;
203            case OpCode::CONVERT:
204                ASSERT(replacement_.State() != Circuit::NullGate());
205                replacement_ = lowering.LowerConvert(replacement_, gate);
206                break;
207            default:
208                break;
209        }
210        ProcessStateDepend(gate);
211    }
212
213    void TryInsertRelay(GateRegion* curRegion)
214    {
215        auto currentState = curRegion->GetState();
216        auto curGate = curRegion->gateList_[currentIndex_];
217        if (acc_.GetOpCode(curGate) != OpCode::DEPEND_RELAY ||
218            acc_.GetState(curGate) != currentState) {
219            auto circuit = acc_.GetCircuit();
220            auto dependRelay = circuit->NewGate(
221                circuit->DependRelay(), { currentState, Circuit::NullGate() });
222            replacement_.SetDepend(dependRelay);
223            ASSERT(dependStart_ == Circuit::NullGate());
224            acc_.SetMark(dependRelay, MarkCode::VISITED);
225            dependStart_ = dependRelay;
226        }
227    }
228
229    void TryLoadDependStart(GateRegion* curRegion)
230    {
231        auto currentState = curRegion->GetState();
232        if (dependStart_ == Circuit::NullGate()) {
233            if (curRegion->preds_.size() == 1) {
234                auto &edge = map_.GetEdge(curRegion->preds_[0], curRegion);
235                ASSERT(edge.dependOut != Circuit::NullGate());
236                replacement_.SetDepend(edge.dependOut);
237                frameState_ = edge.frameStateOut;
238            }
239
240            auto opcode = acc_.GetOpCode(currentState);
241            switch (opcode) {
242                case OpCode::IF_EXCEPTION:
243                    dependStart_ = currentState;
244                    replacement_.SetDepend(dependStart_);
245                    break;
246                case OpCode::IF_TRUE:
247                case OpCode::IF_FALSE:
248                    TryInsertRelay(curRegion);
249                    break;
250                default:
251                    break;
252            }
253        }
254    }
255
256    void ConnectStateDepend(GateRegion* curRegion)
257    {
258        auto currentState = curRegion->GetState();
259        ASSERT(dependStart_ == Circuit::NullGate() ||
260               curRegion->preds_.size() == acc_.GetDependCount(dependStart_));
261        ASSERT(curRegion->preds_.size() == acc_.GetStateCount(currentState));
262        for (size_t i = 0; i < curRegion->preds_.size(); i++) {
263            auto pred = curRegion->preds_[i];
264            auto &edge = map_.GetEdge(pred, curRegion);
265            auto stateInput = acc_.GetState(currentState, i);
266            if (edge.stateOut == Circuit::NullGate()) {
267                ASSERT(edge.dependOut == Circuit::NullGate());
268                pendingEdges_.emplace_back(PendingGateRegionEdge(pred, curRegion, dependStart_, i));
269            } else {
270                ConnectEdge(edge, currentState, stateInput, i);
271            }
272        }
273    }
274
275    void ConnectEdge(RegionEdge& edge, GateRef currentState, GateRef stateInput, size_t i)
276    {
277        if (edge.stateOut != stateInput) {
278            acc_.ReplaceStateIn(currentState, edge.stateOut, i);
279        }
280        if (frameState_ == Circuit::NullGate()) {
281            frameState_ = edge.frameStateOut;
282        }
283        if (dependStart_ != Circuit::NullGate()) {
284            auto dependInput = acc_.GetDep(dependStart_, i);
285            if (edge.dependOut != dependInput) {
286                acc_.ReplaceOrNewDependIn(dependStart_, edge.dependOut, i);
287            }
288        }
289    }
290
291    void ConnectPendingRegionEdges()
292    {
293        for (auto regionEdge : pendingEdges_) {
294            auto currentState = regionEdge.to->GetState();
295            auto stateInput = acc_.GetState(currentState, regionEdge.index);
296            auto &edge = map_.GetEdge(regionEdge.from, regionEdge.to);
297            if (edge.stateOut != stateInput) {
298                acc_.ReplaceStateIn(currentState, edge.stateOut, regionEdge.index);
299            }
300            auto dependInput = acc_.GetDep(regionEdge.dependStart, regionEdge.index);
301            if (edge.dependOut != dependInput) {
302                acc_.ReplaceDependIn(regionEdge.dependStart, edge.dependOut, regionEdge.index);
303            }
304        }
305    }
306
307    void StoreStateDepend(GateRegion* curRegion)
308    {
309        for (auto succ : curRegion->succs_) {
310            auto &edge = map_.GetEdge(curRegion, succ);
311            if (edge.stateOut == Circuit::NullGate()) {
312                edge.stateOut = replacement_.State();
313            }
314            if (edge.dependOut == Circuit::NullGate()) {
315                edge.dependOut = replacement_.Depend();
316            }
317            if (edge.frameStateOut == Circuit::NullGate()) {
318                edge.frameStateOut = frameState_;
319            }
320        }
321        replacement_.Reset();
322        frameState_ = Circuit::NullGate();
323        dependStart_ = Circuit::NullGate();
324        currentIndex_ = -1;
325    }
326
327private:
328    GateRef dependStart_ {Circuit::NullGate()};
329    GateRef frameState_ {Circuit::NullGate()};
330    StateDepend replacement_;
331    int32_t currentIndex_ {-1};
332    StateSplitLinearizer* linearizer_ {nullptr};
333    ChunkDeque<GateRegion*> pendingList_;
334    GateAccessor acc_;
335    RegionStateDependMap map_;
336    ChunkVector<PendingGateRegionEdge> pendingEdges_;
337    size_t maxGateId_ {0};
338};
339
340void StateSplitLinearizer::LinearizeStateSplit()
341{
342    StateDependBuilder builder(this, graphLinearizer_.chunk_);
343    builder.Run(graphLinearizer_.regionList_);
344}
345
346}  // namespace panda::ecmascript::kungfu
347