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/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 LOG_COMPILER(INFO) << acc_.GetId(gate) << ", ";
32 }
33 LOG_COMPILER(INFO) << "]";
34 LOG_COMPILER(INFO) << "Exit: [";
35 for (auto gate : loopInfo->loopExits) {
36 LOG_COMPILER(INFO) << acc_.GetId(gate) << ", ";
37 }
38 LOG_COMPILER(INFO) << "]";
39 LOG_COMPILER(INFO) << "--------------------------------- LoopInfo End ---------------------------------";
40 }
41
CollectLoopBody(LoopInfo * loopInfo)42 void LoopAnalysis::CollectLoopBody(LoopInfo* loopInfo)
43 {
44 ASSERT(acc_.IsLoopHead(loopInfo->loopHead));
45 ChunkUnorderedMap<GateRef, size_t> gateToDepth(chunk_);
46 ChunkQueue<GateRef> firstList(chunk_); // for state and depend edges
47 ChunkQueue<GateRef> secondList(chunk_); // for other edges
48 gateToDepth[loopInfo->loopHead] = 1;
49 firstList.push(loopInfo->loopHead);
50 while ((!firstList.empty()) || (!secondList.empty())) {
51 GateRef cur = Circuit::NullGate();
52 if (!firstList.empty()) {
53 cur = firstList.front();
54 firstList.pop();
55 } else {
56 cur = secondList.front();
57 secondList.pop();
58 }
59 ASSERT(gateToDepth.count(cur) > 0);
60 auto use = acc_.Uses(cur);
61 ASSERT(use.begin() != use.end());
62 for (auto it = use.begin(); it != use.end(); ++it) {
63 auto nex = *it;
64 if (acc_.IsLoopExit(cur) && (!acc_.IsFixed(*it))) {
65 continue;
66 } else if (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 return;
98 }
99
UpdateLoopInfo(LoopInfo * loopInfo,GateRef gate,size_t dep)100 void LoopAnalysis::UpdateLoopInfo(LoopInfo* loopInfo, GateRef gate, size_t dep)
101 {
102 auto op = acc_.GetOpCode(gate);
103 loopInfo->maxDepth = std::max(loopInfo->maxDepth, dep);
104 loopInfo->size++;
105 switch (op) {
106 case OpCode::LOOP_BACK: {
107 if (dep == 1) { // 1: depth of loop head
108 loopInfo->loopBacks.emplace_back(gate);
109 return;
110 }
111 break;
112 }
113 case OpCode::LOOP_EXIT: {
114 if (dep == 1) { // 1: depth of loop head
115 loopInfo->loopExits.emplace_back(gate);
116 return;
117 }
118 break;
119 }
120 case OpCode::LOOP_EXIT_DEPEND:
121 case OpCode::LOOP_EXIT_VALUE: {
122 if (dep == 1) {
123 return;
124 }
125 break;
126 }
127 default:
128 break;
129 }
130 if (acc_.HasFrameState(gate)) {
131 auto frameState = acc_.GetFrameState(gate);
132 if (acc_.GetOpCode(frameState) == OpCode::FRAME_STATE) {
133 loopInfo->size += 2; // 2: framestate and framevalues
134 loopInfo->loopBodys.emplace_back(frameState);
135 loopInfo->loopBodys.emplace_back(acc_.GetValueIn(frameState, 1));
136 }
137 }
138 loopInfo->loopBodys.emplace_back(gate);
139 }
140
141 // only receive state or depend edge (cur -> dep)
ComputeLoopDepth(GateRef cur,GateRef nex,size_t curDep)142 size_t LoopAnalysis::ComputeLoopDepth(GateRef cur, GateRef nex, size_t curDep)
143 {
144 if (acc_.IsLoopExitRelated(cur)) {
145 if ((!acc_.IsLoopExit(cur)) || (!acc_.IsFixed(nex))) {
146 // exit from some loop
147 ASSERT(curDep > 0);
148 curDep--;
149 }
150 }
151 auto nexOp = acc_.GetOpCode(nex);
152 switch (nexOp) {
153 case OpCode::LOOP_BEGIN: {
154 if (acc_.GetState(nex) == cur) {
155 // enter new loop by state edge
156 curDep++;
157 }
158 break;
159 }
160 case OpCode::DEPEND_SELECTOR: {
161 GateRef state = acc_.GetState(nex);
162 if (acc_.IsLoopHead(state) && (cur == acc_.GetDep(nex))) {
163 // enter new loop by depend edge
164 curDep++;
165 }
166 break;
167 }
168 default: {
169 break;
170 }
171 }
172 return curDep;
173 }
174
LoopExitElimination()175 void LoopAnalysis::LoopExitElimination()
176 {
177 std::vector<GateRef> gateList;
178 acc_.GetAllGates(gateList);
179 ChunkQueue<GateRef> workList(chunk_);
180 ChunkSet<GateRef> inList(chunk_);
181 for (auto gate : gateList) {
182 auto op = acc_.GetOpCode(gate);
183 switch (op) {
184 case OpCode::LOOP_EXIT: {
185 acc_.UpdateAllUses(gate, acc_.GetIn(gate, 0));
186 acc_.DeleteGate(gate);
187 break;
188 }
189 case OpCode::LOOP_EXIT_DEPEND:
190 case OpCode::LOOP_EXIT_VALUE: {
191 acc_.UpdateAllUses(gate, acc_.GetIn(gate, 1));
192 acc_.DeleteGate(gate);
193 break;
194 }
195 default:
196 break;
197 }
198 }
199 acc_.EliminateRedundantPhi();
200 }
201 } // namespace panda::ecmascript::kungfu