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