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/loop_peeling.h"
17#include "ecmascript/compiler/circuit.h"
18#include "ecmascript/compiler/share_gate_meta_data.h"
19#include "ecmascript/compiler/number_gate_info.h"
20#include "ecmascript/compiler/type.h"
21
22namespace panda::ecmascript::kungfu {
23void LoopPeeling::CopyLoopExit()
24{
25    for (auto exit : loopInfo_->loopExits) {
26        ASSERT(acc_.GetOpCode(exit) == OpCode::LOOP_EXIT);
27        GateRef numIns = 2; // 2: num ins
28        GateRef copyExit = GetCopy(acc_.GetState(exit));
29        GateRef merge = circuit_->NewGate(circuit_->Merge(numIns), {exit, copyExit});
30        auto exitUse = acc_.Uses(exit);
31        for (auto it = exitUse.begin(); it != exitUse.end();) {
32            if (acc_.GetOpCode(*it) == OpCode::LOOP_EXIT_DEPEND) {
33                GateRef depend = *it;
34                GateRef copyDepend = GetCopy(acc_.GetDep(depend));
35                GateRef selector = circuit_->NewGate(circuit_->DependSelector(numIns), {merge, depend, copyDepend});
36                acc_.UpdateAllUses(depend, selector);
37                acc_.ReplaceIn(selector, 1, depend);    // 0: index of exit depend
38                ++it;
39            } else if (acc_.GetOpCode(*it) == OpCode::LOOP_EXIT_VALUE) {
40                GateRef value = *it;
41                GateRef copyValue = GetCopy(acc_.GetValueIn(value));
42                ASSERT(acc_.GetMachineType(value) == acc_.GetMachineType(copyValue));
43                GateRef selector = circuit_->NewGate(circuit_->ValueSelector(numIns), acc_.GetMachineType(value),
44                                                     {merge, value, copyValue}, acc_.GetGateType(value));
45                acc_.UpdateAllUses(value, selector);
46                acc_.ReplaceIn(selector, 1, value);    // 0: index of exit depend
47                ++it;
48            } else if ((*it) == merge) {
49                ++it;
50            } else {
51                it = acc_.ReplaceIn(it, merge);
52            }
53        }
54    }
55}
56
57void LoopPeeling::CopyLoopBody()
58{
59    for (auto gate : loopInfo_->loopBodys) {
60        if ((gate == loopInfo_->loopHead) ||
61            (acc_.IsSelector(gate) && acc_.GetState(gate) == loopInfo_->loopHead)) {
62            continue;
63        }
64        GateRef copy = GetCopy(gate);
65        size_t numIns = acc_.GetNumIns(gate);
66        for (size_t i = 0; i < numIns; ++i) {
67            GateRef in = acc_.GetIn(gate, i);
68            GateRef copyIn = TryGetCopy(in);
69            if (copyIn != Circuit::NullGate()) {
70                acc_.NewIn(copy, i, copyIn);
71            } else {
72                acc_.NewIn(copy, i, in);
73            }
74        }
75    }
76}
77
78GateRef LoopPeeling::CopySelector(GateRef stateMerge, GateRef selector, size_t numLoopbacks)
79{
80    GateRef newGate = Circuit::NullGate();
81    auto inList = std::vector<GateRef>(1 + numLoopbacks, Circuit::NullGate()); // 1: state
82    if (acc_.IsValueSelector(selector)) {
83        newGate = circuit_->NewGate(circuit_->ValueSelector(numLoopbacks),
84            MachineType::I64, inList.size(), inList.data(), GateType::AnyType());
85    } else {
86        newGate = circuit_->NewGate(circuit_->DependSelector(numLoopbacks), inList);
87    }
88    acc_.NewIn(newGate, 0, stateMerge); // 0: is state
89    auto numOfIns = acc_.GetNumIns(selector);
90    const size_t skipValue = 2; // 2: state & entry value
91    ASSERT(numOfIns == numLoopbacks + skipValue);
92    for (size_t i = skipValue; i < numOfIns; i++) {
93        auto input = acc_.GetIn(selector, i);
94        acc_.NewIn(newGate, i - 1, GetCopy(input)); // 1: is state
95    }
96    return newGate;
97}
98
99void LoopPeeling::CopyLoopHeader()
100{
101    auto numLoopbacks = loopInfo_->loopBacks.size();
102    if (numLoopbacks > 1) {
103        const size_t skipValue = 1; // 1: entry state
104        auto numOfIns = acc_.GetNumIns(loopInfo_->loopHead);
105        ASSERT(numOfIns == numLoopbacks + skipValue);
106        std::vector<GateRef> inList(numLoopbacks, Circuit::NullGate());
107        auto merge = circuit_->NewGate(circuit_->Merge(numLoopbacks), inList);
108        for (size_t i = skipValue; i < numOfIns; i++) { // 1: skip entry
109            auto input = acc_.GetIn(loopInfo_->loopHead, i);
110            acc_.NewIn(merge, i - skipValue, GetCopy(input));
111        }
112
113        auto use = acc_.Uses(loopInfo_->loopHead);
114        for (auto it = use.begin(); it != use.end(); ++it) {
115            if (acc_.IsSelector(*it)) {
116                auto selector = CopySelector(merge, *it, numLoopbacks);
117                acc_.ReplaceIn(*it, 1, selector);
118            }
119        }
120        acc_.ReplaceIn(loopInfo_->loopHead, 0, merge);  // 0: index of state forward
121    } else {
122        // replace origin forwards with peeled loop back.
123        GateRef stateBack = acc_.GetState(loopInfo_->loopHead, 1); // 1: index of state back
124        acc_.ReplaceIn(loopInfo_->loopHead, 0, GetCopy(stateBack));  // 0: index of state forward
125        auto use = acc_.Uses(loopInfo_->loopHead);
126        for (auto it = use.begin(); it != use.end(); ++it) {
127            if (acc_.IsSelector(*it)) {
128                GateRef backward = acc_.GetIn(*it, 2);  // 2: index of depend or value back
129                acc_.ReplaceIn(*it, 1, GetCopy(backward)); // 1: index of depend or value forward
130            }
131        }
132    }
133}
134
135void LoopPeeling::Peel()
136{
137    SetCopy(loopInfo_->loopHead);
138    for (auto gate : loopInfo_->loopBodys) {
139        SetCopy(gate);
140    }
141    for (auto gate : loopInfo_->loopBacks) {
142        copies_[gate] = GetCopy(acc_.GetState(gate));
143    }
144    CopyLoopBody();
145    CopyLoopHeader();
146    CopyLoopExit();
147
148    if (bcBuilder_) {
149        auto asyncList = bcBuilder_->GetAsyncRelatedGates();
150        ChunkVector<GateRef> list(chunk_);
151        for (auto gate : asyncList) {
152            auto copyAsync = TryGetCopy(gate);
153            if (copyAsync == Circuit::NullGate()) {
154                list.emplace_back(copyAsync);
155            }
156        }
157        for (auto gate : asyncList) {
158            bcBuilder_->UpdateAsyncRelatedGate(gate);
159        }
160    }
161
162    Print();
163}
164
165void LoopPeeling::SetCopy(GateRef gate)
166{
167    ASSERT(copies_.count(gate) == 0);
168    if (gate == loopInfo_->loopHead) {
169        // copy of head is forward
170        copies_[gate] = acc_.GetState(gate);
171        return;
172    }
173    if (acc_.IsSelector(gate) && acc_.GetState(gate) == loopInfo_->loopHead) {
174        // copy of head is forward
175        copies_[gate] = acc_.GetIn(gate, 1); // 1: index of forward
176        return;
177    }
178
179    std::vector<GateRef> inList(acc_.GetNumIns(gate), Circuit::NullGate());
180    GateRef newGate = circuit_->NewGate(acc_.GetMetaData(gate), inList);
181    acc_.SetGateType(newGate, acc_.GetGateType(gate));
182    acc_.SetMachineType(newGate, acc_.GetMachineType(gate));
183    copies_[gate] = newGate;
184    if (acc_.GetOpCode(gate) == OpCode::JS_BYTECODE) {
185        bcBuilder_->UpdateBcIndexGate(newGate, bcBuilder_->GetBcIndexByGate(gate));
186    }
187}
188
189GateRef LoopPeeling::GetCopy(GateRef gate) const
190{
191    if (copies_.count(gate)) {
192        return copies_.at(gate);
193    }
194    return gate;
195}
196
197GateRef LoopPeeling::TryGetCopy(GateRef gate) const
198{
199    if (copies_.count(gate) > 0) {
200        return copies_.at(gate);
201    }
202    return Circuit::NullGate();
203}
204
205void LoopPeeling::Print() const
206{
207    if (IsLogEnabled()) {
208        LOG_COMPILER(INFO) << "";
209        LOG_COMPILER(INFO) << "\033[34m"
210                           << "===================="
211                           << " After loop peeling "
212                           << "[" << GetMethodName() << "]"
213                           << "===================="
214                           << "\033[0m";
215        circuit_->PrintAllGatesWithBytecode();
216        LOG_COMPILER(INFO) << "\033[34m" << "========================= End ==========================" << "\033[0m";
217    }
218}
219}  // namespace panda::ecmascript::kungfu