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_analysis.h"
17 #include "ecmascript/compiler/loop_peeling.h"
18 #include "ecmascript/compiler/bytecodes.h"
19 #include "ecmascript/compiler/share_gate_meta_data.h"
20 #include "ecmascript/log_wrapper.h"
21
22 namespace panda::ecmascript::kungfu {
PrintLoop(LoopInfo * loopInfo)23 void LoopAnalysis::PrintLoop(LoopInfo* loopInfo)
24 {
25 LOG_COMPILER(INFO) << "--------------------------------- LoopInfo Start ---------------------------------";
26 LOG_COMPILER(INFO) << "Head: " << acc_.GetId(loopInfo->loopHead);
27 LOG_COMPILER(INFO) << "Size: " << loopInfo->size;
28 LOG_COMPILER(INFO) << "MaxDepth: " << loopInfo->maxDepth;
29 LOG_COMPILER(INFO) << "Body: [";
30 for (auto gate : loopInfo->loopBodys) {
31 acc_.ShortPrint(gate);
32 }
33 LOG_COMPILER(INFO) << "]";
34 LOG_COMPILER(INFO) << "Exit: [";
35 for (auto gate : loopInfo->loopExits) {
36 acc_.ShortPrint(gate);
37 }
38 LOG_COMPILER(INFO) << "]";
39 LOG_COMPILER(INFO) << "--------------------------------- LoopInfo End ---------------------------------";
40 }
41
Run()42 void LoopAnalysis::Run()
43 {
44 ChunkVector<GateRef>& headerGates = bcBuilder_->GetLoopHeaderGates();
45 for (auto it = headerGates.rbegin(); it != headerGates.rend(); ++it) {
46 auto gate = *it;
47 if (gate == Circuit::NullGate()) {
48 continue;
49 }
50 auto loopInfo = chunk_->New<LoopInfo>(chunk_, gate);
51 loopInfos_.emplace_back(loopInfo);
52 }
53 }
54
CollectUseGate(ChunkUnorderedMap<GateRef,size_t> & gateToDepth,ChunkQueue<GateRef> & firstList,ChunkQueue<GateRef> & secondList,LoopInfo * loopInfo,GateRef cur)55 void LoopAnalysis::CollectUseGate(ChunkUnorderedMap<GateRef, size_t>& gateToDepth,
56 ChunkQueue<GateRef>& firstList, ChunkQueue<GateRef>& secondList,
57 LoopInfo* loopInfo, GateRef cur)
58 {
59 auto use = acc_.Uses(cur);
60 ASSERT(use.begin() != use.end());
61 bool isCurLoop = gateToDepth[cur] == 1; // 1: loopDepth
62 for (auto it = use.begin(); it != use.end(); ++it) {
63 auto nex = *it;
64 if (isCurLoop && acc_.IsLoopExit(cur) && (!acc_.IsFixed(*it))) {
65 continue;
66 } else if (isCurLoop && acc_.IsLoopExitRelated(cur) && acc_.IsFixed(cur)) {
67 continue;
68 } else if (acc_.GetDependCount(nex) == 0 && acc_.GetStateCount(nex) == 0) {
69 continue;
70 }
71 if (gateToDepth.count(nex)) {
72 // loop back
73 if (acc_.IsStateIn(it) || acc_.IsDependIn(it)) {
74 ASSERT(gateToDepth[nex] == ComputeLoopDepth(cur, nex, gateToDepth[cur]));
75 }
76 continue;
77 }
78 if (acc_.IsStateIn(it) || acc_.IsDependIn(it)) {
79 // only calculate loop depth for state & depend edges,
80 // since there is no phi of each value and each loop head.
81 gateToDepth[nex] = ComputeLoopDepth(cur, nex, gateToDepth[cur]);
82 if (acc_.HasFrameState(nex)) {
83 auto frameState = acc_.GetFrameState(nex);
84 if (acc_.GetOpCode(frameState) == OpCode::FRAME_STATE) {
85 gateToDepth[frameState] = gateToDepth[nex];
86 gateToDepth[acc_.GetValueIn(frameState, 1)] = gateToDepth[nex];
87 }
88 }
89 // state and depend edge should be visited first.
90 firstList.push(nex);
91 UpdateLoopInfo(loopInfo, nex, gateToDepth.at(nex));
92 } else {
93 secondList.push(nex);
94 }
95 }
96 }
97
CollectLoopBody(LoopInfo * loopInfo)98 void LoopAnalysis::CollectLoopBody(LoopInfo* loopInfo)
99 {
100 ASSERT(acc_.IsLoopHead(loopInfo->loopHead));
101 ChunkUnorderedMap<GateRef, size_t> gateToDepth(chunk_);
102 ChunkQueue<GateRef> firstList(chunk_); // for state and depend edges
103 ChunkQueue<GateRef> secondList(chunk_); // for other edges
104 gateToDepth[loopInfo->loopHead] = 1;
105 firstList.push(loopInfo->loopHead);
106 while ((!firstList.empty()) || (!secondList.empty())) {
107 GateRef cur = Circuit::NullGate();
108 if (!firstList.empty()) {
109 cur = firstList.front();
110 firstList.pop();
111 } else {
112 cur = secondList.front();
113 secondList.pop();
114 }
115 ASSERT(gateToDepth.count(cur) > 0);
116 CollectUseGate(gateToDepth, firstList, secondList, loopInfo, cur);
117 }
118 }
119
UpdateLoopInfo(LoopInfo * loopInfo,GateRef gate,size_t dep)120 void LoopAnalysis::UpdateLoopInfo(LoopInfo* loopInfo, GateRef gate, size_t dep)
121 {
122 auto op = acc_.GetOpCode(gate);
123 loopInfo->maxDepth = std::max(loopInfo->maxDepth, dep);
124 loopInfo->size++;
125 switch (op) {
126 case OpCode::LOOP_BACK: {
127 if (dep == 1) { // 1: depth of loop head
128 loopInfo->loopBacks.emplace_back(gate);
129 return;
130 }
131 break;
132 }
133 case OpCode::LOOP_EXIT: {
134 if (dep == 1) { // 1: depth of loop head
135 loopInfo->loopExits.emplace_back(gate);
136 return;
137 }
138 break;
139 }
140 case OpCode::LOOP_EXIT_DEPEND:
141 case OpCode::LOOP_EXIT_VALUE: {
142 if (dep == 1) {
143 return;
144 }
145 break;
146 }
147 default:
148 break;
149 }
150 if (acc_.HasFrameState(gate)) {
151 auto frameState = acc_.GetFrameState(gate);
152 if (acc_.GetOpCode(frameState) == OpCode::FRAME_STATE) {
153 loopInfo->size += 2; // 2: framestate and framevalues
154 loopInfo->loopBodys.emplace_back(frameState);
155 loopInfo->loopBodys.emplace_back(acc_.GetValueIn(frameState, 1));
156 }
157 }
158 loopInfo->loopBodys.emplace_back(gate);
159 }
160
161 // only receive state or depend edge (cur -> dep)
ComputeLoopDepth(GateRef cur,GateRef nex,size_t curDep)162 size_t LoopAnalysis::ComputeLoopDepth(GateRef cur, GateRef nex, size_t curDep)
163 {
164 if (acc_.IsLoopExitRelated(cur)) {
165 if ((!acc_.IsLoopExit(cur)) || (!acc_.IsFixed(nex))) {
166 // exit from some loop
167 ASSERT(curDep > 0);
168 curDep--;
169 }
170 }
171 auto nexOp = acc_.GetOpCode(nex);
172 switch (nexOp) {
173 case OpCode::LOOP_BEGIN: {
174 if (acc_.GetState(nex) == cur) {
175 // enter new loop by state edge
176 curDep++;
177 }
178 break;
179 }
180 case OpCode::DEPEND_SELECTOR: {
181 GateRef state = acc_.GetState(nex);
182 if (acc_.IsLoopHead(state) && (cur == acc_.GetDep(nex))) {
183 // enter new loop by depend edge
184 curDep++;
185 }
186 break;
187 }
188 default: {
189 break;
190 }
191 }
192 return curDep;
193 }
194
LoopExitElimination()195 void LoopAnalysis::LoopExitElimination()
196 {
197 std::vector<GateRef> gateList;
198 acc_.GetAllGates(gateList);
199 ChunkQueue<GateRef> workList(chunk_);
200 ChunkSet<GateRef> inList(chunk_);
201 for (auto gate : gateList) {
202 auto op = acc_.GetOpCode(gate);
203 switch (op) {
204 case OpCode::LOOP_EXIT: {
205 acc_.UpdateAllUses(gate, acc_.GetIn(gate, 0));
206 acc_.DeleteGate(gate);
207 break;
208 }
209 case OpCode::LOOP_EXIT_DEPEND:
210 case OpCode::LOOP_EXIT_VALUE: {
211 acc_.UpdateAllUses(gate, acc_.GetIn(gate, 1));
212 acc_.DeleteGate(gate);
213 break;
214 }
215 default:
216 break;
217 }
218 }
219 }
220 } // namespace panda::ecmascript::kungfu
221