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