1 /*
2 * Copyright (c) 2024 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/string_builder_optimizer.h"
17 #include "share_opcodes.h"
18
19 namespace panda::ecmascript::kungfu {
20
Run()21 void StringBuilderOptimizer::Run()
22 {
23 graphLinearizer_.SetScheduleJSOpcode();
24 graphLinearizer_.LinearizeGraph();
25 status_.resize(circuit_->GetMaxGateId() + 1, Status{INVALID_ID, State::UNVISITED}); // 1: max + 1 = size
26 VisitGraph();
27 }
28
VisitGraph()29 void StringBuilderOptimizer::VisitGraph()
30 {
31 std::vector<GateRef> gateList;
32 acc_.GetAllGates(gateList);
33 for (auto gate : gateList) {
34 FindBuilderBegin(gate);
35 }
36 currentIndex_ = 0;
37 for (auto &builder : stringBuilders_) {
38 FindInBuilder(builder.start);
39 currentIndex_++;
40 }
41 FinalizeStringBuilders();
42 for (auto gate : concatGates_) {
43 StatusTransfer(gate);
44 }
45 }
46
FindBuilderBegin(GateRef gate)47 void StringBuilderOptimizer::FindBuilderBegin(GateRef gate)
48 {
49 auto op = acc_.GetOpCode(gate);
50 if (op == OpCode::STRING_ADD) {
51 concatGates_.push_back(gate);
52 GateRef left = acc_.GetValueIn(gate, 0);
53 if (IsLiteralString(left)) {
54 if (HasConcatOrPhiUse(left)) {
55 SetStatus(gate, State::BEGIN_STRING_BUILDER, stringBuilderCount_);
56 stringBuilders_.push_back(StringBuilder{gate, static_cast<int>(stringBuilderCount_), false});
57 stringBuilderCount_++;
58 return;
59 }
60 SetStatus(gate, State::INVALID_OPT);
61 } else {
62 auto leftOp = acc_.GetOpCode(left);
63 if (leftOp == OpCode::VALUE_SELECTOR) {
64 SetStatus(gate, State::UNVISITED);
65 } else if (leftOp == OpCode::STRING_ADD) {
66 curStringAddId_ = acc_.GetId(gate);
67 if (CheckStringAddUses(left)) {
68 SetStatus(gate, State::UNVISITED);
69 } else {
70 SetStatus(gate, State::INVALID_OPT);
71 }
72 } else {
73 SetStatus(gate, State::INVALID_OPT);
74 }
75 }
76 } else if (op == OpCode::VALUE_SELECTOR && PhiInputsAreConcatsOrPhi(gate)) {
77 SetStatus(gate, State::UNVISITED);
78 } else {
79 SetStatus(gate, State::INVALID_OPT);
80 }
81 }
82
FindInBuilder(GateRef gate)83 void StringBuilderOptimizer::FindInBuilder(GateRef gate)
84 {
85 toVisit_.clear();
86 toVisit_.push_back(gate);
87 while (!toVisit_.empty()) {
88 GateRef curr = toVisit_.back();
89 toVisit_.pop_back();
90 auto uses = acc_.Uses(curr);
91 for (auto it = uses.begin(); it != uses.end(); it++) {
92 GateRef use = *it;
93 if (!acc_.IsValueIn(it)) {
94 continue;
95 }
96 VisitGateUse(use);
97 }
98 }
99 }
100
VisitGateUse(GateRef use)101 void StringBuilderOptimizer::VisitGateUse(GateRef use)
102 {
103 Status useStatus = GetStatus(use);
104 if (useStatus.state == State::INVALID_OPT || useStatus.state == State::IN_STRING_BUILDER) {
105 return;
106 }
107
108 auto useOpCode = acc_.GetOpCode(use);
109 if (useOpCode == OpCode::VALUE_SELECTOR && IsLoopHeader(use)) {
110 stringBuilders_[currentIndex_].has_loop_phi = true;
111 }
112
113 if (useOpCode == OpCode::VALUE_SELECTOR) {
114 UpdateStatus(use, State::IN_STRING_BUILDER);
115 toVisit_.push_back(use);
116 }
117
118 // if this use is string-add
119 // we need to determine whether to set the current use to IN_STRING_BUILDER
120 // by judging the type and uses of left child
121 if (useOpCode == OpCode::STRING_ADD) {
122 GateRef left = acc_.GetValueIn(use, 0);
123 auto leftOp = acc_.GetOpCode(left);
124 if (leftOp == OpCode::VALUE_SELECTOR) {
125 UpdateStatus(use, State::IN_STRING_BUILDER);
126 toVisit_.push_back(use);
127 } else if (leftOp == OpCode::STRING_ADD) {
128 curStringAddId_ = acc_.GetId(use);
129 if (CheckStringAddUses(left)) {
130 UpdateStatus(use, State::IN_STRING_BUILDER);
131 toVisit_.push_back(use);
132 } else {
133 SetStatus(use, State::INVALID_OPT);
134 }
135 } else {
136 SetStatus(use, State::INVALID_OPT);
137 }
138 }
139 }
140
FinalizeStringBuilders()141 void StringBuilderOptimizer::FinalizeStringBuilders()
142 {
143 for (uint32_t stringBuilderId = 0; stringBuilderId < stringBuilderCount_; stringBuilderId++) {
144 auto& stringBuilder = stringBuilders_[stringBuilderId];
145 GateRef start = stringBuilder.start;
146 if (!stringBuilder.has_loop_phi) {
147 continue;
148 }
149 toVisit_.clear();
150 ends_.clear();
151
152 toVisit_.push_back(start);
153 while (!toVisit_.empty()) {
154 GateRef curr = toVisit_.back();
155 toVisit_.pop_back();
156 auto currStatus = GetStatus(curr);
157 if (currStatus.state == State::CONFIRMED_IN_STRING_BUILDER) {
158 continue;
159 }
160 if (currStatus.state == State::IN_STRING_BUILDER) {
161 UpdateStatus(curr, State::CONFIRMED_IN_STRING_BUILDER);
162 }
163 bool isEnd = false;
164 bool currIsLoopHeader = IsLoopHeader(curr);
165 auto uses = acc_.Uses(curr);
166 for (auto it = uses.begin(); it != uses.end(); it++) {
167 GateRef use = *it;
168 if (!acc_.IsValueIn(it)) {
169 continue;
170 }
171 auto useStatus = GetStatus(use);
172 bool useIsInBuilder = useStatus.state == State::IN_STRING_BUILDER;
173 bool currAndUseBothInBuilder = useStatus.id == currStatus.id;
174 if (useIsInBuilder && currAndUseBothInBuilder) {
175 toVisit_.push_back(use);
176 }
177 if (currIsLoopHeader && !LoopContains(curr, use)) {
178 isEnd = true;
179 }
180 }
181 if (isEnd) {
182 ends_.push_back(curr);
183 }
184 }
185
186 for (auto &end : ends_) {
187 UpdateStatus(end, State::END_STRING_BUILDER);
188 }
189 }
190 }
191
StatusTransfer(GateRef gate)192 void StringBuilderOptimizer::StatusTransfer(GateRef gate)
193 {
194 Status status = GetStatus(gate);
195 switch (status.state) {
196 case State::BEGIN_STRING_BUILDER:
197 acc_.SetStringStatus(gate, EcmaString::BEGIN_STRING_ADD);
198 break;
199 case State::IN_STRING_BUILDER:
200 acc_.SetStringStatus(gate, EcmaString::IN_STRING_ADD);
201 break;
202 case State::CONFIRMED_IN_STRING_BUILDER:
203 acc_.SetStringStatus(gate, EcmaString::CONFIRMED_IN_STRING_ADD);
204 break;
205 case State::END_STRING_BUILDER:
206 acc_.SetStringStatus(gate, EcmaString::END_STRING_ADD);
207 break;
208 default: {
209 acc_.SetStringStatus(gate, EcmaString::INVALID_STRING_ADD);
210 break;
211 }
212 }
213 }
214
HasConcatOrPhiUse(GateRef gate)215 bool StringBuilderOptimizer::HasConcatOrPhiUse(GateRef gate)
216 {
217 auto uses = acc_.Uses(gate);
218 for (auto it = uses.begin(); it != uses.end(); it++) {
219 GateRef use = *it;
220 if (!acc_.IsValueIn(it)) {
221 continue;
222 }
223 auto op = acc_.GetOpCode(use);
224 if ((op == OpCode::STRING_ADD && HasConcatOrPhiUse(use)) || op == OpCode::VALUE_SELECTOR) {
225 return true;
226 }
227 }
228 return false;
229 }
230
CheckStringAddUses(GateRef gate)231 bool StringBuilderOptimizer::CheckStringAddUses(GateRef gate)
232 {
233 ASSERT(acc_.GetOpCode(gate) == OpCode::STRING_ADD || acc_.IsValueSelector(gate));
234 bool canBeOpt = true;
235 auto uses = acc_.Uses(gate);
236 for (auto it = uses.begin(); it != uses.end(); it++) {
237 GateRef use = *it;
238 if (!acc_.IsValueIn(it)) {
239 continue;
240 }
241 auto useOp = acc_.GetOpCode(use);
242 if (useOp == OpCode::STRING_ADD) {
243 // if this gate has multiple string-add uses
244 // or this gate has an invalid use
245 // we cannot set current gate to IN_STRING_BUILDER
246 if (curStringAddId_ != acc_.GetId(use) || IsInvalidGate(use)) {
247 canBeOpt = false;
248 break;
249 }
250 continue;
251 }
252 // this gate has a phi use, then check the phi use gate
253 if (useOp == OpCode::VALUE_SELECTOR && !CheckStringAddUses(use)) {
254 return false;
255 }
256 // this gate has the following types of uses is valid
257 if (useOp == OpCode::ECMA_STRING_CHECK || acc_.IsFrameValues(use) || acc_.IsValueSelector(use)) {
258 continue;
259 }
260 // all other uses are invalid
261 return false;
262 }
263 return canBeOpt;
264 }
265
IsLiteralString(GateRef gate)266 bool StringBuilderOptimizer::IsLiteralString(GateRef gate)
267 {
268 return acc_.IsConstString(gate) || acc_.GetOpCode(gate) == OpCode::STRING_FROM_SINGLE_CHAR_CODE;
269 }
270
IsLoopHeader(GateRef gate)271 bool StringBuilderOptimizer::IsLoopHeader(GateRef gate)
272 {
273 return acc_.GetOpCode(acc_.GetState(gate)) == OpCode::LOOP_BEGIN;
274 }
275
LoopContains(GateRef loopPhi,GateRef gate)276 bool StringBuilderOptimizer::LoopContains(GateRef loopPhi, GateRef gate)
277 {
278 ASSERT(IsLoopHeader(loopPhi));
279 while (gate != acc_.GetStateRoot()) {
280 if (gate == loopPhi) {
281 return true;
282 } else {
283 if (acc_.GetStateCount(gate) == 0) {
284 return false;
285 }
286 gate = acc_.GetState(gate, 0);
287 }
288 }
289 return false;
290 }
291
PhiInputsAreConcatsOrPhi(GateRef phi)292 bool StringBuilderOptimizer::PhiInputsAreConcatsOrPhi(GateRef phi)
293 {
294 return (acc_.GetOpCode(acc_.GetValueIn(phi, 0)) == OpCode::STRING_ADD ||
295 acc_.GetOpCode(acc_.GetValueIn(phi, 0)) == OpCode::VALUE_SELECTOR) &&
296 (acc_.GetOpCode(acc_.GetValueIn(phi, 1)) == OpCode::STRING_ADD ||
297 acc_.GetOpCode(acc_.GetValueIn(phi, 1)) == OpCode::VALUE_SELECTOR);
298 }
299 } // namespace panda::ecmascript::kungfu
300