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