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 
22 namespace panda::ecmascript::kungfu {
CopyLoopExit()23 void 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 
CopyLoopBody()57 void 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 
CopySelector(GateRef stateMerge, GateRef selector, size_t numLoopbacks)78 GateRef 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 
CopyLoopHeader()99 void 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 
Peel()135 void 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 
SetCopy(GateRef gate)165 void 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 
GetCopy(GateRef gate) const189 GateRef LoopPeeling::GetCopy(GateRef gate) const
190 {
191     if (copies_.count(gate)) {
192         return copies_.at(gate);
193     }
194     return gate;
195 }
196 
TryGetCopy(GateRef gate) const197 GateRef LoopPeeling::TryGetCopy(GateRef gate) const
198 {
199     if (copies_.count(gate) > 0) {
200         return copies_.at(gate);
201     }
202     return Circuit::NullGate();
203 }
204 
Print() const205 void 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