1/*
2 * Copyright (c) 2021 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/scheduler.h"
17#include <cmath>
18#include <stack>
19#include "ecmascript/compiler/gate_accessor.h"
20#include "ecmascript/compiler/verifier.h"
21
22namespace panda::ecmascript::kungfu {
23size_t UnionFind(std::vector<size_t> &semiDom, std::vector<size_t> &parent, std::vector<size_t> &minIdx, size_t idx)
24{
25    std::stack<size_t> allIdxs;
26    allIdxs.emplace(idx);
27    size_t pIdx = parent[idx];
28    while (pIdx != allIdxs.top()) {
29        allIdxs.emplace(pIdx);
30        pIdx = parent[pIdx];
31    }
32    size_t unionFindSetRoot = pIdx;
33    while (!allIdxs.empty()) {
34        if (semiDom[minIdx[allIdxs.top()]] > semiDom[minIdx[pIdx]]) {
35            minIdx[allIdxs.top()] = minIdx[pIdx];
36        }
37        parent[allIdxs.top()] = unionFindSetRoot;
38        pIdx = allIdxs.top();
39        allIdxs.pop();
40    }
41    return unionFindSetRoot;
42}
43
44void Scheduler::CalculateDominatorTree(const Circuit *circuit,
45                                       std::vector<GateRef>& bbGatesList,
46                                       std::unordered_map<GateRef, size_t> &bbGatesAddrToIdx,
47                                       std::vector<size_t> &immDom)
48{
49    GateAccessor acc(const_cast<Circuit*>(circuit));
50    std::unordered_map<GateRef, size_t> dfsTimestamp;
51    std::unordered_map<GateRef, size_t> dfsFatherIdx;
52    circuit->AdvanceTime();
53    {
54        size_t timestamp = 0;
55        std::deque<GateRef> pendingList;
56        auto startGate = acc.GetStateRoot();
57        acc.SetMark(startGate, MarkCode::VISITED);
58        pendingList.push_back(startGate);
59        while (!pendingList.empty()) {
60            auto curGate = pendingList.back();
61            dfsTimestamp[curGate] = timestamp++;
62            pendingList.pop_back();
63            bbGatesList.push_back(curGate);
64            if (acc.GetOpCode(curGate) != OpCode::LOOP_BACK) {
65                auto uses = acc.Uses(curGate);
66                for (auto useIt = uses.begin(); useIt != uses.end(); useIt++) {
67                    if (useIt.GetIndex() < acc.GetStateCount(*useIt) &&
68                        acc.IsState(*useIt) && acc.GetMark(*useIt) == MarkCode::NO_MARK) {
69                        acc.SetMark(*useIt, MarkCode::VISITED);
70                        pendingList.push_back(*useIt);
71                        dfsFatherIdx[*useIt] = dfsTimestamp[curGate];
72                    }
73                }
74            }
75        }
76        for (size_t idx = 0; idx < bbGatesList.size(); idx++) {
77            bbGatesAddrToIdx[bbGatesList[idx]] = idx;
78        }
79    }
80    immDom.resize(bbGatesList.size());
81    std::vector<size_t> semiDom(bbGatesList.size());
82    std::vector<std::vector<size_t> > semiDomTree(bbGatesList.size());
83    {
84        std::vector<size_t> parent(bbGatesList.size());
85        std::iota(parent.begin(), parent.end(), 0);
86        std::vector<size_t> minIdx(bbGatesList.size());
87        auto merge = [&] (size_t fatherIdx, size_t sonIdx) -> void {
88            size_t parentFatherIdx = UnionFind(semiDom, parent, minIdx, fatherIdx);
89            size_t parentSonIdx = UnionFind(semiDom, parent, minIdx, sonIdx);
90            parent[parentSonIdx] = parentFatherIdx;
91        };
92        std::iota(semiDom.begin(), semiDom.end(), 0);
93        semiDom[0] = semiDom.size();
94        ASSERT(bbGatesList.size() > 0);
95        for (size_t idx = bbGatesList.size() - 1; idx >= 1; idx--) {
96            std::vector<GateRef> preGates;
97            acc.GetInStates(bbGatesList[idx], preGates);
98            for (const auto &predGate : preGates) {
99                if (bbGatesAddrToIdx.count(predGate) > 0) {
100                    size_t preGateIdx = bbGatesAddrToIdx[predGate];
101                    if (preGateIdx < idx) {
102                        semiDom[idx] = std::min(semiDom[idx], preGateIdx);
103                    } else {
104                        UnionFind(semiDom, parent, minIdx, preGateIdx);
105                        semiDom[idx] = std::min(semiDom[idx], semiDom[minIdx[preGateIdx]]);
106                    }
107                }
108            }
109            for (const auto &succDomIdx : semiDomTree[idx]) {
110                UnionFind(semiDom, parent, minIdx, succDomIdx);
111                if (idx == semiDom[minIdx[succDomIdx]]) {
112                    immDom[succDomIdx] = idx;
113                } else {
114                    immDom[succDomIdx] = minIdx[succDomIdx];
115                }
116            }
117            minIdx[idx] = idx;
118            merge(dfsFatherIdx[bbGatesList[idx]], idx);
119            semiDomTree[semiDom[idx]].push_back(idx);
120        }
121        for (size_t idx = 1; idx < bbGatesList.size(); idx++) {
122            if (immDom[idx] != semiDom[idx]) {
123                immDom[idx] = immDom[immDom[idx]];
124            }
125        }
126        semiDom[0] = 0;
127    }
128}
129
130void Scheduler::Run(const Circuit *circuit, ControlFlowGraph &result,
131                    [[maybe_unused]] const std::string& methodName, [[maybe_unused]] bool enableLog)
132{
133    GateAccessor acc(const_cast<Circuit*>(circuit));
134    std::vector<GateRef> bbGatesList;
135    std::unordered_map<GateRef, size_t> bbGatesAddrToIdx;
136    std::vector<size_t> immDom;
137    Scheduler::CalculateDominatorTree(circuit, bbGatesList, bbGatesAddrToIdx, immDom);
138    ASSERT(result.size() == 0);
139    result.resize(bbGatesList.size());
140    for (size_t idx = 0; idx < bbGatesList.size(); idx++) {
141        result[idx].push_back(bbGatesList[idx]);
142    }
143    // assuming CFG is always reducible
144    std::vector<std::vector<size_t>> sonList(result.size());
145    for (size_t idx = 1; idx < immDom.size(); idx++) {
146        sonList[immDom[idx]].push_back(idx);
147    }
148    const size_t sizeLog = std::ceil(std::log2(static_cast<double>(result.size())) + 1);
149    std::vector<size_t> timeIn(result.size());
150    std::vector<size_t> timeOut(result.size());
151    std::vector<std::vector<size_t>> jumpUp;
152    jumpUp.assign(result.size(), std::vector<size_t>(sizeLog + 1));
153    {
154        size_t timestamp = 0;
155        struct DFSState {
156            size_t cur;
157            std::vector<size_t> &succList;
158            size_t idx;
159        };
160        std::stack<DFSState> dfsStack;
161        size_t root = 0;
162        dfsStack.push({root, sonList[root], 0});
163        timeIn[root] = timestamp++;
164        jumpUp[root][0] = root;
165        for (size_t stepSize = 1; stepSize <= sizeLog; stepSize++) {
166            auto jumpUpHalf = jumpUp[root][stepSize - 1];
167            jumpUp[root][stepSize] = jumpUp[jumpUpHalf][stepSize - 1];
168        }
169        while (!dfsStack.empty()) {
170            auto &curState = dfsStack.top();
171            auto &cur = curState.cur;
172            auto &succList = curState.succList;
173            auto &idx = curState.idx;
174            if (idx == succList.size()) {
175                timeOut[cur] = timestamp++;
176                dfsStack.pop();
177                continue;
178            }
179            const auto &succ = succList[idx];
180            dfsStack.push({succ, sonList[succ], 0});
181            timeIn[succ] = timestamp++;
182            jumpUp[succ][0] = cur;
183            for (size_t stepSize = 1; stepSize <= sizeLog; stepSize++) {
184                auto jumpUpHalf = jumpUp[succ][stepSize - 1];
185                jumpUp[succ][stepSize] = jumpUp[jumpUpHalf][stepSize - 1];
186            }
187            idx++;
188        }
189    }
190    auto isAncestor = [&](size_t nodeA, size_t nodeB) -> bool {
191        return (timeIn[nodeA] <= timeIn[nodeB]) && (timeOut[nodeA] >= timeOut[nodeB]);
192    };
193    auto lowestCommonAncestor = [&](size_t nodeA, size_t nodeB) -> size_t {
194        if (isAncestor(nodeA, nodeB)) {
195            return nodeA;
196        }
197        if (isAncestor(nodeB, nodeA)) {
198            return nodeB;
199        }
200        for (size_t stepSize = sizeLog + 1; stepSize > 0; stepSize--) {
201            if (!isAncestor(jumpUp[nodeA][stepSize - 1], nodeB)) {
202                nodeA = jumpUp[nodeA][stepSize - 1];
203            }
204        }
205        return jumpUp[nodeA][0];
206    };
207    {
208        std::vector<GateRef> order;
209        std::unordered_map<GateRef, size_t> lowerBound;
210        Scheduler::CalculateSchedulingLowerBound(circuit, bbGatesAddrToIdx, lowestCommonAncestor, lowerBound, &order);
211        for (const auto &schedulableGate : order) {
212            result[lowerBound.at(schedulableGate)].push_back(schedulableGate);
213        }
214        std::vector<GateRef> argList;
215        acc.GetOuts(acc.GetArgRoot(), argList);
216        std::sort(argList.begin(), argList.end(), [&](const GateRef &lhs, const GateRef &rhs) -> bool {
217            return acc.TryGetValue(lhs) > acc.TryGetValue(rhs);
218        });
219        for (const auto &arg : argList) {
220            result.front().push_back(arg);
221        }
222        for (const auto &bbGate : bbGatesList) {
223            auto uses = acc.Uses(bbGate);
224            for (auto i = uses.begin(); i != uses.end(); i++) {
225                GateRef succGate = *i;
226                if (acc.IsFixed(succGate)) {
227                    result[bbGatesAddrToIdx.at(acc.GetIn(succGate, 0))].push_back(succGate);
228                }
229            }
230        }
231    }
232    if (enableLog) {
233        Print(&result, circuit);
234    }
235}
236
237bool Scheduler::CalculateSchedulingUpperBound(const Circuit *circuit,
238                                              const std::unordered_map<GateRef, size_t> &bbGatesAddrToIdx,
239                                              const std::function<bool(size_t, size_t)> &isAncestor,
240                                              const std::vector<GateRef> &schedulableGatesList,
241                                              std::unordered_map<GateRef, size_t> &upperBound)
242{
243    GateAccessor acc(const_cast<Circuit*>(circuit));
244    struct DFSState {
245        GateRef curGate = Circuit::NullGate();
246        std::vector<GateRef> predGates;
247        size_t idx = 0;
248        size_t curUpperBound = 0;
249    };
250    DFSState emptyState = {Circuit::NullGate(), std::vector<GateRef>(0), 0, 0};
251    bool getReturn = false;
252    std::optional<size_t> returnValue = 0;
253    std::stack<DFSState> dfsStack;
254    auto CheckUnschedulable = [&](GateRef gate) -> void {
255        if (upperBound.count(gate) > 0) {
256            returnValue = upperBound[gate];
257            getReturn = true;
258        } else if (acc.IsProlog(gate) || acc.IsRoot(gate) || acc.IsVirtualState(gate)) {
259            returnValue = 0;
260            getReturn = true;
261        } else if (acc.IsFixed(gate)) {
262            returnValue = bbGatesAddrToIdx.at(acc.GetIn(gate, 0));
263            getReturn = true;
264        } else if (acc.IsState(gate)) {
265            returnValue = bbGatesAddrToIdx.at(gate);
266            getReturn = true;
267        }
268        // then gate is schedulable
269    };
270    for (const auto &schedulableGate : schedulableGatesList) {
271        if (upperBound.count(schedulableGate) != 0) {
272            continue;
273        }
274        getReturn = false;
275        CheckUnschedulable(schedulableGate);
276        if (getReturn) {
277            continue;
278        }
279        dfsStack.push(emptyState);
280        auto &rootState = dfsStack.top();
281        auto &rootPredGates = rootState.predGates;
282        rootState.curGate = schedulableGate;
283        acc.GetIns(schedulableGate, rootPredGates);
284        while (!dfsStack.empty()) {
285            auto &curState = dfsStack.top();
286            auto &curGate = curState.curGate;
287            const auto &predGates = curState.predGates;
288            auto &idx = curState.idx;
289            auto &curUpperBound = curState.curUpperBound;
290            if (idx == predGates.size()) {
291                upperBound[curGate] = curUpperBound;
292                returnValue = curUpperBound;
293                dfsStack.pop();
294                getReturn = true;
295                continue;
296            }
297            if (getReturn) {
298                if (!returnValue.has_value()) {
299                    break;
300                }
301                auto predUpperBound = returnValue.value();
302                if (!isAncestor(curUpperBound, predUpperBound) && !isAncestor(predUpperBound, curUpperBound)) {
303                    PrintUpperBoundError(circuit, curGate, predUpperBound, curUpperBound);
304                    returnValue = std::nullopt;
305                    break;
306                }
307                if (isAncestor(curUpperBound, predUpperBound)) {
308                    curUpperBound = predUpperBound;
309                }
310                getReturn = false;
311                idx++;
312            } else {
313                const auto &predGate = predGates[idx];
314                CheckUnschedulable(predGate);
315                if (getReturn) {
316                    continue;
317                }
318                dfsStack.push(emptyState);
319                auto &newState = dfsStack.top();
320                auto &newPredGates = newState.predGates;
321                newState.curGate = predGate;
322                acc.GetIns(predGate, newPredGates);
323            }
324        }
325        if (!returnValue.has_value()) {
326            return false;
327        }
328    }
329    return true;
330}
331
332void Scheduler::PrintUpperBoundError(const Circuit *circuit, GateRef curGate,
333                                     GateRef predUpperBound, GateRef curUpperBound)
334{
335    GateAccessor ac(const_cast<Circuit*>(circuit));
336    LOG_COMPILER(ERROR) << "[Verifier][Error] Scheduling upper bound of gate (id="
337                        << ac.GetId(curGate)
338                        << ") does not exist, current-upper-bound = "
339                        << curUpperBound << ", pred-upper-bound = "
340                        << predUpperBound << ", there is no dominator relationship between them.";
341}
342
343void Scheduler::CalculateFixedGatesList(const Circuit *circuit,
344                                        const std::unordered_map<GateRef, size_t> &bbGatesAddrToIdx,
345                                        std::vector<GateRef> &bbAndFixedGatesList)
346{
347    GateAccessor acc(const_cast<Circuit*>(circuit));
348    for (const auto &item : bbGatesAddrToIdx) {
349        bbAndFixedGatesList.push_back(item.first);
350        auto uses = acc.Uses(item.first);
351        for (auto i = uses.begin(); i != uses.end(); i++) {
352            GateRef succGate = *i;
353            if (acc.IsFixed(succGate)) {
354                bbAndFixedGatesList.push_back(succGate);
355            }
356        }
357    }
358}
359
360void Scheduler::CalculateSchedulingLowerBound(const Circuit *circuit,
361                                              const std::unordered_map<GateRef, size_t> &bbGatesAddrToIdx,
362                                              const std::function<size_t(size_t, size_t)> &lowestCommonAncestor,
363                                              std::unordered_map<GateRef, size_t> &lowerBound,
364                                              std::vector<GateRef> *order)
365{
366    GateAccessor acc(const_cast<Circuit*>(circuit));
367    std::vector<GateRef> bbAndFixedGatesList;
368    CalculateFixedGatesList(circuit, bbGatesAddrToIdx, bbAndFixedGatesList);
369    std::unordered_map<GateRef, size_t> useCount;
370    struct DFSVisitState {
371        std::vector<GateRef> prevGates;
372        size_t idx = 0;
373    };
374    DFSVisitState emptyVisitState = {std::vector<GateRef>(0), 0};
375    std::stack<DFSVisitState> dfsVisitStack;
376    for (const auto &gate : bbAndFixedGatesList) {
377        dfsVisitStack.push(emptyVisitState);
378        auto &rootState = dfsVisitStack.top();
379        auto &rootPrevGates = rootState.prevGates;
380        acc.GetIns(gate, rootPrevGates);
381        while (!dfsVisitStack.empty()) {
382            auto &curState = dfsVisitStack.top();
383            auto &prevGates = curState.prevGates;
384            auto &idx = curState.idx;
385            if (idx == prevGates.size()) {
386                dfsVisitStack.pop();
387                continue;
388            }
389            const auto &prevGate = prevGates[idx];
390            if (!acc.IsSchedulable(prevGate)) {
391                ++idx;
392                continue;
393            }
394            useCount[prevGate]++;
395            if (useCount[prevGate] == 1) {
396                dfsVisitStack.push(emptyVisitState);
397                auto &newState = dfsVisitStack.top();
398                auto &newPrevGates = newState.prevGates;
399                acc.GetIns(prevGate, newPrevGates);
400            }
401            ++idx;
402        }
403    }
404    struct DFSFinishState {
405        GateRef curGate = Circuit::NullGate();
406        std::vector<GateRef> prevGates;
407        size_t idx = 0;
408    };
409    DFSFinishState emptyFinishState = {Circuit::NullGate(), std::vector<GateRef>(0), 0};
410    std::stack<DFSFinishState> dfsFinishStack;
411    for (const auto &gate : bbAndFixedGatesList) {
412        dfsFinishStack.push(emptyFinishState);
413        auto &rootState = dfsFinishStack.top();
414        auto &rootPrevGates = rootState.prevGates;
415        rootState.curGate = gate;
416        acc.GetIns(gate, rootPrevGates);
417        while (!dfsFinishStack.empty()) {
418            auto &curState = dfsFinishStack.top();
419            auto &curGate = curState.curGate;
420            auto &prevGates = curState.prevGates;
421            auto &idx = curState.idx;
422            if (idx == prevGates.size()) {
423                dfsFinishStack.pop();
424                continue;
425            }
426            const auto &prevGate = prevGates[idx];
427            if (!acc.IsSchedulable(prevGate)) {
428                ++idx;
429                continue;
430            }
431            useCount[prevGate]--;
432            size_t curLowerBound;
433            if (acc.IsState(curGate)) {  // cur_opcode would not be STATE_ENTRY
434                curLowerBound = bbGatesAddrToIdx.at(curGate);
435            } else if (acc.IsSelector(curGate)) {
436                ASSERT(idx > 0);
437                curLowerBound = bbGatesAddrToIdx.at(acc.GetIn(acc.GetIn(curGate, 0), idx - 1));
438            } else if (acc.IsFixed(curGate)) {
439                ASSERT(idx > 0);
440                curLowerBound = bbGatesAddrToIdx.at(acc.GetIn(curGate, 0));
441            } else {
442                curLowerBound = lowerBound.at(curGate);
443            }
444            if (lowerBound.count(prevGate) == 0) {
445                lowerBound[prevGate] = curLowerBound;
446            } else {
447                lowerBound[prevGate] = lowestCommonAncestor(lowerBound[prevGate], curLowerBound);
448            }
449            if (useCount[prevGate] == 0) {
450                if (order != nullptr) {
451                    order->push_back(prevGate);
452                }
453                dfsFinishStack.push(emptyFinishState);
454                auto &newState = dfsFinishStack.top();
455                auto &newPrevGates = newState.prevGates;
456                newState.curGate = prevGate;
457                acc.GetIns(prevGate, newPrevGates);
458            }
459            ++idx;
460        }
461    }
462}
463
464void Scheduler::Print(const std::vector<std::vector<GateRef>> *cfg, const Circuit *circuit)
465{
466    GateAccessor acc(const_cast<Circuit*>(circuit));
467    std::vector<GateRef> bbGatesList;
468    std::unordered_map<GateRef, size_t> bbGatesAddrToIdx;
469    std::vector<size_t> immDom;
470    Scheduler::CalculateDominatorTree(circuit, bbGatesList, bbGatesAddrToIdx, immDom);
471    LOG_COMPILER(INFO) << "==================================== Scheduling ==================================";
472    for (size_t bbIdx = 0; bbIdx < cfg->size(); bbIdx++) {
473        auto opcode = acc.GetOpCode((*cfg)[bbIdx].front());
474        LOG_COMPILER(INFO) << "B" << bbIdx << "_" << opcode << ":"
475                           << "  immDom=" << immDom[bbIdx];
476        LOG_COMPILER(INFO) << "  pred=[";
477        bool isFirst = true;
478        GateRef head = cfg->at(bbIdx).front();
479        auto ins = acc.Ins(head);
480        for (auto i = ins.begin(); i != ins.end(); i++) {
481            GateRef predState = *i;
482            if (acc.IsState(predState) ||
483                acc.GetOpCode(predState) == OpCode::STATE_ENTRY) {
484                LOG_COMPILER(INFO) << (isFirst ? "" : " ") << bbGatesAddrToIdx.at(predState);
485                isFirst = false;
486            }
487        }
488        LOG_COMPILER(INFO) << "]  succ=[";
489        isFirst = true;
490        GateRef h = cfg->at(bbIdx).front();
491        auto uses = acc.Uses(h);
492        for (auto i = uses.begin(); i != uses.end(); i++) {
493            GateRef succState = *i;
494            if (acc.IsState(succState) ||
495                acc.GetOpCode(succState) == OpCode::STATE_ENTRY) {
496                LOG_COMPILER(INFO) << (isFirst ? "" : " ") << bbGatesAddrToIdx.at(succState);
497                isFirst = false;
498            }
499        }
500        LOG_COMPILER(INFO) << "]";
501        for (size_t instIdx = (*cfg)[bbIdx].size(); instIdx > 0; instIdx--) {
502            acc.Print((*cfg)[bbIdx][instIdx - 1]);
503        }
504    }
505    LOG_COMPILER(INFO) << "==================================== Scheduling ==================================";
506}
507}  // namespace panda::ecmascript::kungfu
508