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 right = acc_.GetValueIn(gate, 1);
53 if (!IsLiteralString(right)) {
54 SetStatus(gate, State::INVALID_OPT);
55 return;
56 }
57 GateRef left = acc_.GetValueIn(gate, 0);
58 if (IsLiteralString(left)) {
59 if (HasConcatOrPhiUse(left)) {
60 SetStatus(gate, State::BEGIN_STRING_BUILDER, stringBuilderCount_);
61 stringBuilders_.push_back(StringBuilder{gate, static_cast<int>(stringBuilderCount_), false});
62 stringBuilderCount_++;
63 return;
64 }
65 SetStatus(gate, State::INVALID_OPT);
66 } else {
67 auto leftOp = acc_.GetOpCode(left);
68 if (leftOp == OpCode::VALUE_SELECTOR) {
69 SetStatus(gate, State::UNVISITED);
70 } else if (leftOp == OpCode::STRING_ADD) {
71 curStringAddId_ = acc_.GetId(gate);
72 if (CheckStringAddUses(left)) {
73 SetStatus(gate, State::UNVISITED);
74 } else {
75 SetStatus(gate, State::INVALID_OPT);
76 }
77 } else {
78 SetStatus(gate, State::INVALID_OPT);
79 }
80 }
81 } else if (op == OpCode::VALUE_SELECTOR && PhiInputsAreConcatsOrPhi(gate)) {
82 SetStatus(gate, State::UNVISITED);
83 } else {
84 SetStatus(gate, State::INVALID_OPT);
85 }
86 }
87
FindInBuilder(GateRef gate)88 void StringBuilderOptimizer::FindInBuilder(GateRef gate)
89 {
90 toVisit_.clear();
91 toVisit_.push_back(gate);
92 while (!toVisit_.empty()) {
93 GateRef curr = toVisit_.back();
94 toVisit_.pop_back();
95 auto uses = acc_.Uses(curr);
96 for (auto it = uses.begin(); it != uses.end(); it++) {
97 GateRef use = *it;
98 if (!acc_.IsValueIn(it)) {
99 continue;
100 }
101 VisitGateUse(use);
102 }
103 }
104 }
105
VisitGateUse(GateRef use)106 void StringBuilderOptimizer::VisitGateUse(GateRef use)
107 {
108 Status useStatus = GetStatus(use);
109 if (useStatus.state == State::INVALID_OPT || useStatus.state == State::IN_STRING_BUILDER) {
110 return;
111 }
112
113 auto useOpCode = acc_.GetOpCode(use);
114 if (useOpCode == OpCode::VALUE_SELECTOR && IsLoopHeader(use)) {
115 stringBuilders_[currentIndex_].has_loop_phi = true;
116 }
117
118 if (useOpCode == OpCode::VALUE_SELECTOR) {
119 UpdateStatus(use, State::IN_STRING_BUILDER);
120 toVisit_.push_back(use);
121 }
122
123 // if this use is string-add
124 // we need to determine whether to set the current use to IN_STRING_BUILDER
125 // by judging the type and uses of left child
126 if (useOpCode == OpCode::STRING_ADD) {
127 GateRef left = acc_.GetValueIn(use, 0);
128 auto leftOp = acc_.GetOpCode(left);
129 if (leftOp == OpCode::VALUE_SELECTOR) {
130 UpdateStatus(use, State::IN_STRING_BUILDER);
131 toVisit_.push_back(use);
132 } else if (leftOp == OpCode::STRING_ADD) {
133 curStringAddId_ = acc_.GetId(use);
134 if (CheckStringAddUses(left)) {
135 UpdateStatus(use, State::IN_STRING_BUILDER);
136 toVisit_.push_back(use);
137 } else {
138 SetStatus(use, State::INVALID_OPT);
139 }
140 } else {
141 SetStatus(use, State::INVALID_OPT);
142 }
143 }
144 }
145
FinalizeStringBuilders()146 void StringBuilderOptimizer::FinalizeStringBuilders()
147 {
148 for (uint32_t stringBuilderId = 0; stringBuilderId < stringBuilderCount_; stringBuilderId++) {
149 auto& stringBuilder = stringBuilders_[stringBuilderId];
150 GateRef start = stringBuilder.start;
151 if (!stringBuilder.has_loop_phi) {
152 continue;
153 }
154 toVisit_.clear();
155 ends_.clear();
156
157 toVisit_.push_back(start);
158 while (!toVisit_.empty()) {
159 GateRef curr = toVisit_.back();
160 toVisit_.pop_back();
161 auto currStatus = GetStatus(curr);
162 if (currStatus.state == State::CONFIRMED_IN_STRING_BUILDER) {
163 continue;
164 }
165 if (currStatus.state == State::IN_STRING_BUILDER) {
166 UpdateStatus(curr, State::CONFIRMED_IN_STRING_BUILDER);
167 }
168 bool isEnd = false;
169 bool currIsLoopHeader = IsLoopHeader(curr);
170 auto uses = acc_.Uses(curr);
171 for (auto it = uses.begin(); it != uses.end(); it++) {
172 GateRef use = *it;
173 if (!acc_.IsValueIn(it)) {
174 continue;
175 }
176 auto useStatus = GetStatus(use);
177 bool useIsInBuilder = useStatus.state == State::IN_STRING_BUILDER;
178 bool currAndUseBothInBuilder = useStatus.id == currStatus.id;
179 if (useIsInBuilder && currAndUseBothInBuilder) {
180 toVisit_.push_back(use);
181 }
182 if (currIsLoopHeader && !LoopContains(curr, use)) {
183 isEnd = true;
184 }
185 }
186 if (isEnd) {
187 ends_.push_back(curr);
188 }
189 }
190
191 for (auto &end : ends_) {
192 UpdateStatus(end, State::END_STRING_BUILDER);
193 }
194 }
195 }
196
StatusTransfer(GateRef gate)197 void StringBuilderOptimizer::StatusTransfer(GateRef gate)
198 {
199 Status status = GetStatus(gate);
200 switch (status.state) {
201 case State::BEGIN_STRING_BUILDER:
202 acc_.SetStringStatus(gate, EcmaString::BEGIN_STRING_ADD);
203 break;
204 case State::IN_STRING_BUILDER:
205 acc_.SetStringStatus(gate, EcmaString::IN_STRING_ADD);
206 break;
207 case State::CONFIRMED_IN_STRING_BUILDER:
208 acc_.SetStringStatus(gate, EcmaString::CONFIRMED_IN_STRING_ADD);
209 break;
210 case State::END_STRING_BUILDER:
211 acc_.SetStringStatus(gate, EcmaString::END_STRING_ADD);
212 break;
213 default: {
214 acc_.SetStringStatus(gate, EcmaString::INVALID_STRING_ADD);
215 break;
216 }
217 }
218 }
219
HasConcatOrPhiUse(GateRef gate)220 bool StringBuilderOptimizer::HasConcatOrPhiUse(GateRef gate)
221 {
222 auto uses = acc_.Uses(gate);
223 for (auto it = uses.begin(); it != uses.end(); it++) {
224 GateRef use = *it;
225 if (!acc_.IsValueIn(it)) {
226 continue;
227 }
228 auto op = acc_.GetOpCode(use);
229 if ((op == OpCode::STRING_ADD && HasConcatOrPhiUse(use)) || op == OpCode::VALUE_SELECTOR) {
230 return true;
231 }
232 }
233 return false;
234 }
235
CheckStringAddUses(GateRef gate)236 bool StringBuilderOptimizer::CheckStringAddUses(GateRef gate)
237 {
238 ASSERT(acc_.GetOpCode(gate) == OpCode::STRING_ADD || acc_.IsValueSelector(gate));
239 bool canBeOpt = true;
240 auto uses = acc_.Uses(gate);
241 for (auto it = uses.begin(); it != uses.end(); it++) {
242 GateRef use = *it;
243 if (!acc_.IsValueIn(it)) {
244 continue;
245 }
246 auto useOp = acc_.GetOpCode(use);
247 if (useOp == OpCode::STRING_ADD) {
248 // if this gate has multiple string-add uses
249 // or this gate has an invalid use
250 // we cannot set current gate to IN_STRING_BUILDER
251 if (curStringAddId_ != acc_.GetId(use) || IsInvalidGate(use)) {
252 canBeOpt = false;
253 break;
254 }
255 continue;
256 }
257 // this gate has a phi use, then check the phi use gate
258 if (useOp == OpCode::VALUE_SELECTOR && !CheckStringAddUses(use)) {
259 return false;
260 }
261 // this gate has the following types of uses is valid
262 if (useOp == OpCode::ECMA_STRING_CHECK || 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