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