1 /*
2 * Copyright (c) 2022 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/frame_states.h"
17
18 #include "ecmascript/compiler/bytecode_circuit_builder.h"
19
20 namespace panda::ecmascript::kungfu {
FrameStateBuilder(BytecodeCircuitBuilder * builder,Circuit * circuit,const MethodLiteral * literal)21 FrameStateBuilder::FrameStateBuilder(BytecodeCircuitBuilder *builder,
22 Circuit *circuit, const MethodLiteral *literal)
23 : bcBuilder_(builder),
24 pgoTypeRecorder_(builder->GetPGOTypeRecorder()),
25 numVregs_(literal->GetNumberVRegs() + FIXED_ARGS),
26 accumulatorIndex_(literal->GetNumberVRegs() + 1), // 1: acc
27 envIndex_(literal->GetNumberVRegs()),
28 circuit_(circuit),
29 acc_(circuit),
30 bcEndStateLiveouts_(circuit->chunk()),
31 bbBeginStateLiveouts_(circuit->chunk()),
32 bbFrameContext_(circuit->chunk()),
33 loops_(circuit->chunk()),
34 rpoList_(circuit->chunk()),
35 postOrderList_(circuit->chunk())
36 {
37 }
38
~FrameStateBuilder()39 FrameStateBuilder::~FrameStateBuilder()
40 {
41 liveOutResult_ = nullptr;
42 bcEndStateLiveouts_.clear();
43 bbBeginStateLiveouts_.clear();
44 bbFrameContext_.clear();
45 bcBuilder_ = nullptr;
46 }
47
BuildPostOrderList(size_t size)48 void FrameStateBuilder::BuildPostOrderList(size_t size)
49 {
50 postOrderList_.clear();
51 std::deque<size_t> pendingList;
52 std::vector<bool> visited(size, false);
53 // entry block (bbid=0) is a empty block, need skip
54 auto firstBlockId = 1;
55 pendingList.emplace_back(firstBlockId);
56
57 while (!pendingList.empty()) {
58 size_t curBlockId = pendingList.back();
59 visited[curBlockId] = true;
60
61 bool change = false;
62 auto &bb = bcBuilder_->GetBasicBlockById(curBlockId);
63 for (const auto &succBlock: bb.succs) {
64 if (!visited[succBlock->id]) {
65 pendingList.emplace_back(succBlock->id);
66 change = true;
67 break;
68 }
69 }
70 if (change) {
71 continue;
72 }
73 for (const auto &succBlock: bb.catches) {
74 if (!visited[succBlock->id]) {
75 pendingList.emplace_back(succBlock->id);
76 change = true;
77 break;
78 }
79 }
80 if (!change) {
81 postOrderList_.emplace_back(curBlockId);
82 pendingList.pop_back();
83 }
84 }
85 }
86
MergeIntoPredBC(uint32_t predPc)87 bool FrameStateBuilder::MergeIntoPredBC(uint32_t predPc)
88 {
89 // liveout next
90 auto liveout = GetOrOCreateBCEndLiveOut(predPc);
91 FrameLiveOut *predliveOut = liveOutResult_;
92 return liveout->MergeLiveout(predliveOut);
93 }
94
MergeFromSuccBB(size_t bbId)95 bool FrameStateBuilder::MergeFromSuccBB(size_t bbId)
96 {
97 // liveout next
98 auto liveout = GetOrOCreateBBLiveOut(bbId);
99 return liveOutResult_->MergeLiveout(liveout);
100 }
101
MergeFromCatchBB(size_t bbId)102 void FrameStateBuilder::MergeFromCatchBB(size_t bbId)
103 {
104 // liveout next
105 bool accumulatorIsLive = liveOutResult_->TestBit(accumulatorIndex_);
106 auto liveout = GetOrOCreateBBLiveOut(bbId);
107 liveOutResult_->MergeLiveout(liveout);
108 // accumulatorIndex_ is exeception object
109 if (!accumulatorIsLive) {
110 liveOutResult_->ClearBit(accumulatorIndex_);
111 }
112 }
113
ComputeLiveOut(size_t bbId)114 bool FrameStateBuilder::ComputeLiveOut(size_t bbId)
115 {
116 auto &bb = bcBuilder_->GetBasicBlockById(bbId);
117 bool changed = false;
118 // iterator bc
119 auto &iterator = bb.GetBytecodeIterator();
120 iterator.GotoEnd();
121 ASSERT(bb.end == iterator.Index());
122 auto bbLiveout = GetOrOCreateBBLiveOut(bb.id);
123 auto liveout = GetOrOCreateBCEndLiveOut(bb.end);
124 liveOutResult_->CopyFrom(liveout);
125 // init frameContext
126 currentBBliveOut_ = bbLiveout;
127 while (true) {
128 auto &bytecodeInfo = iterator.GetBytecodeInfo();
129 if (!bb.catches.empty() && !bytecodeInfo.NoThrow()) {
130 ASSERT(bb.catches.size() == 1); // 1: one catch
131 MergeFromCatchBB(bb.catches.at(0)->id);
132 }
133 ComputeLiveOutBC(bytecodeInfo);
134 --iterator;
135 if (iterator.Done()) {
136 break;
137 }
138 auto prevPc = iterator.Index();
139 changed |= MergeIntoPredBC(prevPc);
140 }
141 if (!bb.trys.empty()) {
142 // clear GET_EXCEPTION gate if this is a catch block
143 liveOutResult_->ClearBit(accumulatorIndex_);
144 }
145 bbLiveout->CopyFrom(liveOutResult_);
146 // merge current into pred bb
147 for (auto bbPred : bb.preds) {
148 changed |= MergeIntoPredBC(bbPred->end);
149 }
150
151 return changed;
152 }
153
ComputeLiveState()154 void FrameStateBuilder::ComputeLiveState()
155 {
156 // recompute liveout
157 bool changed = true;
158 while (changed) {
159 changed = false;
160 for (size_t i = 0; i < postOrderList_.size(); i++) {
161 changed |= ComputeLiveOut(postOrderList_[i]);
162 }
163 }
164 }
165
DoBytecodeAnalysis()166 void FrameStateBuilder::DoBytecodeAnalysis()
167 {
168 ComputeLoopInfo();
169 }
170
UpdateCatchState(uint32_t bcId,FrameLiveOut * liveout)171 void FrameStateBuilder::UpdateCatchState(uint32_t bcId, FrameLiveOut* liveout)
172 {
173 GateRef state = GetCurrentState();
174 GateRef depend = GetCurrentDepend();
175 auto getException = circuit_->NewGate(circuit_->GetException(),
176 MachineType::I64, {state, depend}, GateType::AnyType());
177 UpdateAccumulator(getException);
178 UpdateStateDepend(state, getException);
179 BuildStateSplitBeforeCatch(bcId, liveout);
180 }
181
BuildStateSplitBeforeCatch(uint32_t bcId,FrameLiveOut * liveout)182 void FrameStateBuilder::BuildStateSplitBeforeCatch(uint32_t bcId, FrameLiveOut* liveout)
183 {
184 auto stateSplit = BuildStateSplit(liveContext_, liveout, bcId);
185 auto frameState = acc_.GetFrameState(stateSplit);
186 auto frameValues = acc_.GetFrameValue(frameState);
187 // in catch bb, we def exception as acc, we should add exception to frameValues.
188 acc_.ReplaceValueIn(frameValues, liveContext_->ValuesAt(accumulatorIndex_), accumulatorIndex_);
189 liveContext_->currentDepend_ = stateSplit;
190 }
191
AnalyzeLiveness()192 void FrameStateBuilder::AnalyzeLiveness()
193 {
194 auto bcSize = bcBuilder_->GetLastBcIndex() + 1; // 1: +1 pcOffsets size
195 auto bbSize = bcBuilder_->GetBasicBlockCount();
196 bcEndStateLiveouts_.resize(bcSize, nullptr);
197 bbBeginStateLiveouts_.resize(bbSize, nullptr);
198 auto chunk = circuit_->chunk();
199 liveOutResult_ = chunk->New<FrameLiveOut>(chunk, numVregs_);
200 bbFrameContext_.resize(bbSize, nullptr);
201 BuildPostOrderList(bbSize);
202 ComputeLiveState();
203 if (bcBuilder_->IsLogEnabled()) {
204 DumpLiveState();
205 }
206 }
207
ComputeLiveOutBC(const BytecodeInfo & bytecodeInfo)208 void FrameStateBuilder::ComputeLiveOutBC(const BytecodeInfo &bytecodeInfo)
209 {
210 if (bytecodeInfo.GetOpcode() == EcmaOpcode::RESUMEGENERATOR) {
211 currentBBliveOut_->defRegisters_.Union(liveOutResult_->liveout_);
212 }
213 // variable kill
214 if (bytecodeInfo.AccOut()) {
215 liveOutResult_->ClearBit(accumulatorIndex_);
216 currentBBliveOut_->defRegisters_.SetBit(accumulatorIndex_);
217 }
218 for (const auto &out: bytecodeInfo.vregOut) {
219 liveOutResult_->ClearBit(out);
220 currentBBliveOut_->defRegisters_.SetBit(out);
221 }
222
223 // variable use
224 if (bytecodeInfo.AccIn()) {
225 liveOutResult_->SetBit(accumulatorIndex_);
226 }
227 for (size_t i = 0; i < bytecodeInfo.inputs.size(); i++) {
228 auto in = bytecodeInfo.inputs[i];
229 if (std::holds_alternative<VirtualRegister>(in)) {
230 auto vreg = std::get<VirtualRegister>(in).GetId();
231 liveOutResult_->SetBit(vreg);
232 }
233 }
234 }
235
GetOrOCreateBCEndLiveOut(uint32_t bcIndex)236 FrameLiveOut *FrameStateBuilder::GetOrOCreateBCEndLiveOut(uint32_t bcIndex)
237 {
238 auto liveout = bcEndStateLiveouts_[bcIndex];
239 if (liveout == nullptr) {
240 auto chunk = circuit_->chunk();
241 liveout = chunk->New<FrameLiveOut>(chunk, numVregs_);
242 bcEndStateLiveouts_[bcIndex] = liveout;
243 }
244 return liveout;
245 }
246
GetOrOCreateBBLiveOut(size_t bbIndex)247 FrameLiveOut *FrameStateBuilder::GetOrOCreateBBLiveOut(size_t bbIndex)
248 {
249 // As BB0 is empty, its bbBeginStateLiveouts is the same as BB1.
250 if (bbIndex == 0) {
251 if (bcBuilder_->IsOSR()) {
252 bbIndex = GetOsrLoopHeadBBId();
253 } else {
254 bbIndex = 1;
255 }
256 }
257 auto liveout = bbBeginStateLiveouts_[bbIndex];
258 if (liveout == nullptr) {
259 auto chunk = circuit_->chunk();
260 liveout = chunk->New<FrameLiveOut>(chunk, numVregs_);
261 bbBeginStateLiveouts_[bbIndex] = liveout;
262 }
263 return liveout;
264 }
265
GetOrOCreateMergedContext(uint32_t bbIndex)266 FrameContext *FrameStateBuilder::GetOrOCreateMergedContext(uint32_t bbIndex)
267 {
268 if (bbIndex >= bbFrameContext_.size()) {
269 LOG_COMPILER(FATAL) << "bbIndex of FrameStateBuilder::GetOrOCreateMergedContext exceeds the limit.";
270 }
271 auto context = bbFrameContext_[bbIndex];
272 if (context == nullptr) {
273 auto chunk = circuit_->chunk();
274 context = chunk->New<FrameContext>(chunk, numVregs_);
275 for (size_t i = 0; i < numVregs_; i++) {
276 context->SetValuesAt(i, Circuit::NullGate());
277 }
278 bbFrameContext_[bbIndex] = context;
279 }
280 return context;
281 }
282
FillBcInputs(const BytecodeInfo & bytecodeInfo,GateRef gate)283 void FrameStateBuilder::FillBcInputs(const BytecodeInfo &bytecodeInfo, GateRef gate)
284 {
285 auto pgoType = pgoTypeRecorder_->GetPGOType(acc_.TryGetPcOffset(gate));
286 acc_.TrySetPGOType(gate, pgoType);
287
288 auto valueCount = acc_.GetInValueCount(gate);
289 [[maybe_unused]] size_t numValueInputs = bytecodeInfo.ComputeValueInputCount();
290 [[maybe_unused]] size_t numValueOutputs = bytecodeInfo.ComputeOutCount();
291 // RETURNUNDEFINED has value input, but not from acc
292 ASSERT(numValueInputs == valueCount || bytecodeInfo.GetOpcode() == EcmaOpcode::RETURNUNDEFINED);
293 ASSERT(numValueOutputs <= 1 + (bytecodeInfo.EnvOut() ? 1 : 0));
294 auto valueStarts = acc_.GetInValueStarts(gate);
295 for (size_t valueIdx = 0; valueIdx < valueCount; valueIdx++) {
296 auto inIdx = valueIdx + valueStarts;
297 if (!acc_.IsInGateNull(gate, inIdx)) {
298 continue;
299 }
300 if (valueIdx < bytecodeInfo.inputs.size()) {
301 auto vregId = std::get<VirtualRegister>(bytecodeInfo.inputs.at(valueIdx)).GetId();
302 GateRef defVreg = liveContext_->ValuesAt(vregId);
303 acc_.NewIn(gate, inIdx, defVreg);
304 } else {
305 GateRef defAcc = liveContext_->ValuesAt(accumulatorIndex_);
306 acc_.NewIn(gate, inIdx, defAcc);
307 }
308 }
309 }
310
AdvanceToNextBc(const BytecodeInfo & bytecodeInfo,FrameLiveOut * liveout,uint32_t bcId)311 void FrameStateBuilder::AdvanceToNextBc(const BytecodeInfo &bytecodeInfo, FrameLiveOut* liveout, uint32_t bcId)
312 {
313 if (bytecodeInfo.IsGeneral()) {
314 BuildFrameStateBefore(bytecodeInfo, liveout, bcId);
315 if (bytecodeInfo.GetOpcode() == EcmaOpcode::SUSPENDGENERATOR_V8 ||
316 bytecodeInfo.GetOpcode() == EcmaOpcode::ASYNCGENERATORRESOLVE_V8_V8_V8) {
317 auto hole = circuit_->GetConstantGate(MachineType::I64,
318 JSTaggedValue::VALUE_HOLE,
319 GateType::TaggedValue());
320 uint32_t numRegs = accumulatorIndex_;
321 std::vector<GateRef> vec(numRegs + 1, hole);
322 vec[0] = liveContext_->currentDepend_;
323 // accumulator is res
324 for (size_t i = 0; i < numRegs; i++) {
325 if (liveout->TestBit(i)) {
326 vec[i + 1] = liveContext_->ValuesAt(i); // 1: skip dep
327 } else {
328 vec[i + 1] = hole; // 1: skip dep
329 }
330 }
331 auto res = circuit_->NewGate(circuit_->SaveRegister(numRegs), vec);
332 liveContext_->currentDepend_ = res;
333 }
334 }
335 }
336
UpdateStateDepend(GateRef state,GateRef depend)337 void FrameStateBuilder::UpdateStateDepend(GateRef state, GateRef depend)
338 {
339 liveContext_->currentState_ = state;
340 liveContext_->currentDepend_ = depend;
341 }
342
UpdateMoveValues(const BytecodeInfo & bytecodeInfo)343 void FrameStateBuilder::UpdateMoveValues(const BytecodeInfo &bytecodeInfo)
344 {
345 GateRef gate = Circuit::NullGate();
346 if (bytecodeInfo.AccIn()) {
347 gate = liveContext_->ValuesAt(accumulatorIndex_);
348 } else if (bytecodeInfo.inputs.size() != 0) {
349 auto vreg = std::get<VirtualRegister>(bytecodeInfo.inputs.at(0)).GetId();
350 gate = liveContext_->ValuesAt(vreg);
351 }
352 // variable kill
353 if (bytecodeInfo.AccOut()) {
354 liveContext_->SetValuesAt(accumulatorIndex_, gate);
355 } else if (bytecodeInfo.vregOut.size() != 0) {
356 auto vreg = bytecodeInfo.vregOut[0];
357 liveContext_->SetValuesAt(vreg, gate);
358 }
359 }
360
UpdateFrameValues(const BytecodeInfo & bytecodeInfo,uint32_t bcId,GateRef gate)361 void FrameStateBuilder::UpdateFrameValues(const BytecodeInfo &bytecodeInfo,
362 uint32_t bcId, GateRef gate)
363 {
364 ASSERT(!bytecodeInfo.IsDiscarded() && !bytecodeInfo.IsMov());
365 if (bytecodeInfo.IsSetConstant()) {
366 liveContext_->SetValuesAt(accumulatorIndex_, gate);
367 return;
368 }
369 // jump gate is null
370 if (IsGateNotEmpty(gate)) {
371 FillBcInputs(bytecodeInfo, gate);
372 }
373 auto liveout = GetFrameLiveoutAfter(bcId);
374 // variable kill
375 if (bytecodeInfo.AccOut()) {
376 liveContext_->SetValuesAt(accumulatorIndex_, gate);
377 }
378 for (const auto &out: bytecodeInfo.vregOut) {
379 liveContext_->SetValuesAt(out, gate);
380 }
381 if (bytecodeInfo.GetOpcode() == EcmaOpcode::RESUMEGENERATOR) {
382 // accumulator is generator object
383 for (size_t i = 0; i < accumulatorIndex_; i++) {
384 if (liveout->TestBit(i)) {
385 auto restore = circuit_->NewGate(circuit_->RestoreRegister(i),
386 MachineType::I64, { gate }, GateType::AnyType());
387 liveContext_->SetValuesAt(i, restore);
388 }
389 }
390 }
391 BindFrameStateAndStateSplitAfter(bytecodeInfo, bcId, gate);
392 }
393
SetOsrLoopHeadBB(const BytecodeRegion & osrLoopBodyBB)394 void FrameStateBuilder::SetOsrLoopHeadBB(const BytecodeRegion &osrLoopBodyBB)
395 {
396 auto *loopInfo = GetLoopInfoByLoopBody(osrLoopBodyBB);
397 if (loopInfo == nullptr) {
398 loopHeadOfOSR_ = nullptr;
399 } else {
400 loopHeadOfOSR_ = &(bcBuilder_->GetBasicBlockById(loopInfo->loopHeadId));
401 }
402 return;
403 }
404
IsOsrLoopExit(const BytecodeRegion & curBB)405 bool FrameStateBuilder::IsOsrLoopExit(const BytecodeRegion &curBB)
406 {
407 if (loopHeadOfOSR_ == nullptr) {
408 return false;
409 }
410 auto *loopInfo = GetLoopInfoByLoopBody(*loopHeadOfOSR_);
411 if (!loopInfo || !loopInfo->loopExits) {
412 return false;
413 }
414 for (auto *exit : *loopInfo->loopExits) {
415 if (exit == &curBB) {
416 return true;
417 }
418 }
419 return false;
420 }
421
OutOfOsrLoop(const BytecodeRegion & curBB)422 bool FrameStateBuilder::OutOfOsrLoop(const BytecodeRegion &curBB)
423 {
424 if (loopHeadOfOSR_ == nullptr) {
425 return false;
426 }
427 const LoopInfo &loopInfoOfOSR = GetLoopInfo(*loopHeadOfOSR_);
428 const LoopInfo *curLoop = GetLoopInfoByLoopBody(curBB);
429 while (curLoop != nullptr) {
430 if (curLoop == &loopInfoOfOSR) {
431 return false;
432 }
433 curLoop = curLoop->parentInfo;
434 }
435 return true;
436 }
437
GetOsrLoopHeadBBId() const438 size_t FrameStateBuilder::GetOsrLoopHeadBBId() const
439 {
440 if (loopHeadOfOSR_ == nullptr) {
441 return -1;
442 }
443 return loopHeadOfOSR_->id;
444 }
445
InitEntryBB(const BytecodeRegion & bb)446 void FrameStateBuilder::InitEntryBB(const BytecodeRegion &bb)
447 {
448 auto frameContext = GetOrOCreateMergedContext(bb.id);
449 frameContext->currentState_ = circuit_->GetStateRoot();
450 frameContext->currentDepend_ = circuit_->GetDependRoot();
451 frameContext->needStateSplit_ = true;
452 // initialize argumnets
453 ASSERT(bcBuilder_->IsFirstBasicBlock(1)); // 1: is firstBlock
454 auto liveout = GetFrameLiveoutBefore(1); // 1: is firstBlock
455 GateRef frameArgs = bcBuilder_->GetFrameArgs();
456 GateRef lexicalEnv = Circuit::NullGate();
457 if (liveout->TestBit(envIndex_)) {
458 GateRef jsFunc = acc_.GetValueIn(frameArgs, static_cast<size_t>(FrameArgIdx::FUNC));
459 lexicalEnv = acc_.GetInitialEnvGate(frameContext->currentDepend_, jsFunc);
460 frameContext->SetValuesAt(envIndex_, lexicalEnv);
461 frameContext->currentDepend_ = lexicalEnv;
462 }
463 if (circuit_->GetGlobalEnvCache() == Circuit::NullGate()) {
464 GateRef globalEnv = Circuit::NullGate();
465 if (lexicalEnv != Circuit::NullGate()) {
466 globalEnv = circuit_->NewGate(circuit_->GetGlobalEnvByLexicalEnv(), MachineType::I64,
467 {frameContext->currentDepend_, lexicalEnv}, GateType::AnyType());
468 } else {
469 globalEnv = circuit_->NewGate(
470 circuit_->GetGlobalEnvByFunc(), MachineType::I64,
471 {frameContext->currentDepend_, acc_.GetValueIn(frameArgs, static_cast<size_t>(FrameArgIdx::FUNC))},
472 GateType::AnyType());
473 }
474 circuit_->SetGlobalEnvCache(globalEnv);
475 frameContext->currentDepend_ = globalEnv;
476 }
477 auto holeGate = circuit_->GetConstantGate(MachineType::I64,
478 JSTaggedValue::VALUE_HOLE,
479 GateType::TaggedValue());
480 for (size_t i = 0; i < envIndex_; i++) {
481 if (liveout->TestBit(i)) {
482 if (bcBuilder_->ArgGateNotExisted(i)) {
483 frameContext->SetValuesAt(i, holeGate);
484 } else {
485 GateRef arg = bcBuilder_->GetArgGate(i);
486 frameContext->SetValuesAt(i, arg);
487 }
488 }
489 }
490
491 // init live interpreter registers
492 if (!bcBuilder_->IsOSR()) {
493 return;
494 }
495 auto *liveOut = GetFrameLiveoutBefore(GetOsrLoopHeadBBId());
496 for (size_t i = 0; i < envIndex_; i++) {
497 if (!liveOut->TestBit(i)) {
498 continue;
499 }
500 GateRef init = circuit_->NewGate(circuit_->GetMetaBuilder()->InitVreg(i), MachineType::I64,
501 {circuit_->GetArgRoot()}, GateType::TaggedValue());
502 frameContext->SetValuesAt(i, init);
503 }
504 if (liveOut->TestBit(envIndex_)) {
505 // -7: env
506 GateRef env = circuit_->NewGate(circuit_->GetMetaBuilder()->InitVreg(INIT_VRGE_ENV), MachineType::I64,
507 {circuit_->GetArgRoot()}, GateType::TaggedValue());
508 frameContext->SetValuesAt(envIndex_, env);
509 }
510 }
511
IsLoopHead(const BytecodeRegion & bb)512 bool FrameStateBuilder::IsLoopHead(const BytecodeRegion &bb)
513 {
514 return !(bcBuilder_->IsOSR() && OutOfOsrLoop(bb)) && bb.loopNumber > 0;
515 }
516
IfLoopNeedMerge(const BytecodeRegion & bb) const517 bool FrameStateBuilder::IfLoopNeedMerge(const BytecodeRegion &bb) const
518 {
519 return !bcBuilder_->IsOSR() && bb.numOfStatePreds - bb.numOfLoopBack != 1; // 1: loop in
520 }
521
InitMerge(size_t numOfIns,bool isLoop)522 GateRef FrameStateBuilder::InitMerge(size_t numOfIns, bool isLoop)
523 {
524 const GateMetaData *metaData = isLoop ? circuit_->LoopBegin(numOfIns) : circuit_->Merge(numOfIns);
525 return circuit_->NewGate(metaData, std::vector<GateRef>(numOfIns, Circuit::NullGate()));
526 }
527
IsGateNotEmpty(GateRef gate) const528 bool FrameStateBuilder::IsGateNotEmpty(GateRef gate) const
529 {
530 return gate != Circuit::NullGate();
531 }
532
NewMerge(const BytecodeRegion & bbNext)533 void FrameStateBuilder::NewMerge(const BytecodeRegion &bbNext)
534 {
535 auto frameContext = GetMergedBbContext(bbNext.id);
536 size_t numOfIns = bbNext.numOfStatePreds;
537 if (IsOsrLoopExit(bbNext)) {
538 // Only the precursor within the OSR loop is required.
539 numOfIns = 0;
540 for (const BytecodeRegion *bb : bbNext.preds) {
541 if (OutOfOsrLoop(*bb)) {
542 continue;
543 }
544 numOfIns++;
545 }
546 }
547
548 bool isLoopHead = IsLoopHead(bbNext);
549 GateRef merge;
550 GateRef dependMerge;
551 if (isLoopHead) {
552 if (!IfLoopNeedMerge(bbNext)) {
553 // only generate loop begin
554 merge = InitMerge(numOfIns, true);
555 dependMerge = circuit_->NewGate(circuit_->DependSelector(numOfIns),
556 std::vector<GateRef>(numOfIns + 1, Circuit::NullGate())); // 1: merge
557 } else {
558 // generate both loop begin and merge
559 ASSERT(numOfIns - bbNext.numOfLoopBack > 1); // 1: loop in
560 size_t numOfLoopIns = bbNext.numOfLoopBack + 1; // 1: loop in
561 merge = InitMerge(numOfLoopIns, true);
562 dependMerge = circuit_->NewGate(circuit_->DependSelector(numOfLoopIns),
563 std::vector<GateRef>(numOfLoopIns + 1, Circuit::NullGate())); // 1: merge
564 size_t numOfMergeIns = numOfIns - bbNext.numOfLoopBack;
565 frameContext->mergeState_ = InitMerge(numOfMergeIns, false);
566 frameContext->mergeDepend_ = circuit_->NewGate(circuit_->DependSelector(numOfMergeIns),
567 std::vector<GateRef>(numOfMergeIns + 1, Circuit::NullGate())); // 1: merge
568 acc_.NewIn(frameContext->mergeDepend_, 0, frameContext->mergeState_);
569 acc_.NewIn(dependMerge, 1, frameContext->mergeDepend_); // 1: phi of merge
570 acc_.NewIn(merge, 0, frameContext->mergeState_);
571 frameContext->loopBackIndex_++;
572 }
573 frameContext->loopBackDepend_ = dependMerge;
574 frameContext->loopBackState_ = merge;
575 } else {
576 // only merge
577 merge = InitMerge(numOfIns, false);
578 dependMerge = circuit_->NewGate(circuit_->DependSelector(numOfIns),
579 std::vector<GateRef>(numOfIns + 1, Circuit::NullGate())); // 1: merge
580 frameContext->mergeDepend_ = dependMerge;
581 frameContext->mergeState_ = merge;
582 }
583 acc_.NewIn(dependMerge, 0, merge); // 0: is state
584 // reset current state and depend
585 frameContext->currentState_ = merge;
586 frameContext->currentDepend_ = dependMerge;
587
588 if (isLoopHead) {
589 ChunkVector<GateRef>& headerGates = bcBuilder_->GetLoopHeaderGates();
590 auto& loopInfo = GetLoopInfo(bbNext);
591 headerGates[loopInfo.sortIndx] = merge;
592 }
593 }
594
MergeStateDepend(const BytecodeRegion & bb,const BytecodeRegion & bbNext)595 void FrameStateBuilder::MergeStateDepend(const BytecodeRegion &bb, const BytecodeRegion &bbNext)
596 {
597 GateRef entryState = liveContext_->currentState_;
598 GateRef entryDepend = liveContext_->currentDepend_;
599 auto mergedContext = GetMergedBbContext(bbNext.id);
600 if (bbNext.numOfStatePreds == 1) { // 1: one entry edge
601 mergedContext->currentState_ = liveContext_->currentState_;
602 mergedContext->currentDepend_ = liveContext_->currentDepend_;
603 return;
604 }
605 auto index = mergedContext->currentIndex_;
606 // lazy first edge
607 if (index == 0) {
608 NewMerge(bbNext);
609 }
610 if (IsLoopBackEdge(bb, bbNext)) {
611 if (!(bcBuilder_->IsOSR() && IsOsrLoopExit(bbNext))) {
612 ASSERT(index != 0);
613 }
614 entryState = circuit_->NewGate(circuit_->LoopBack(), { entryState });
615 }
616 auto mergeInfo = GetCorrespondingState(bb, bbNext);
617 acc_.NewIn(mergeInfo.state, mergeInfo.index, entryState);
618 acc_.NewIn(mergeInfo.depend, mergeInfo.index + 1, entryDepend); // 1: skip state
619 mergedContext->needStateSplit_ = true;
620 }
621
GetNumOfStatePreds(const BytecodeRegion & bb)622 size_t FrameStateBuilder::GetNumOfStatePreds(const BytecodeRegion &bb)
623 {
624 size_t numOfIns = bb.numOfStatePreds;
625 if (bcBuilder_->IsOSR() && IsOsrLoopExit(bb)) {
626 numOfIns = 0;
627 for (const BytecodeRegion *b : bb.preds) {
628 if (OutOfOsrLoop(*b)) {
629 continue;
630 }
631 numOfIns++;
632 }
633 }
634 return numOfIns;
635 }
636
MergeValue(const BytecodeRegion & bb,GateRef currentValue,GateRef nextValue,bool isLoopBack,bool changedInLoop)637 GateRef FrameStateBuilder::MergeValue(const BytecodeRegion &bb,
638 GateRef currentValue, GateRef nextValue, bool isLoopBack, bool changedInLoop)
639 {
640 ASSERT(IsGateNotEmpty(currentValue));
641 auto mergedContext = GetMergedBbContext(bb.id);
642 GateRef result = currentValue;
643 GateRef mergeValueSelector;
644 // When next is empty, if next has not changed within the loop, there is no need to merge;
645 bool skipMergeValues = !changedInLoop && !IsGateNotEmpty(nextValue);
646
647 // if already a merged gate
648 if (IsGateNotEmpty(nextValue) &&
649 (acc_.GetOpCode(nextValue) == OpCode::VALUE_SELECTOR &&
650 acc_.GetState(nextValue) == mergedContext->currentState_)) {
651 ASSERT(IsGateNotEmpty(currentValue));
652 if (isLoopBack) {
653 ASSERT(IsGateNotEmpty(mergedContext->loopBackState_));
654 acc_.NewIn(nextValue, mergedContext->loopBackIndex_ + 1, currentValue); // 1: merge
655 } else {
656 ASSERT(IsGateNotEmpty(mergedContext->mergeState_));
657 if (!IsGateNotEmpty(mergedContext->loopBackState_)) {
658 acc_.NewIn(nextValue, mergedContext->mergeIndex_ + 1, currentValue); // 1: merge
659 } else {
660 mergeValueSelector = acc_.GetIn(nextValue, 1); // 1: index of phi of merge
661 acc_.NewIn(mergeValueSelector, mergedContext->mergeIndex_ + 1, currentValue); // 1: merge
662 }
663 }
664 result = nextValue;
665 } else if (skipMergeValues) {
666 // simply assign the value of current.
667 } else if (currentValue != nextValue) {
668 bool needMergeValues = IsGateNotEmpty(mergedContext->mergeState_);
669 // build value selector for merge.
670 if (needMergeValues) {
671 size_t numOfIns = acc_.GetNumIns(mergedContext->mergeState_);
672 auto inList = std::vector<GateRef>(numOfIns + 1, Circuit::NullGate()); // 1: state
673 auto phi = circuit_->NewGate(
674 circuit_->ValueSelector(numOfIns), MachineType::I64, inList.size(), inList.data(),
675 GateType::AnyType());
676 acc_.NewIn(phi, 0, mergedContext->mergeState_);
677 for (size_t i = 0; i < mergedContext->mergeIndex_; i++) {
678 acc_.NewIn(phi, i + 1, nextValue); // 1: merge
679 }
680 if (!isLoopBack) {
681 acc_.NewIn(phi, mergedContext->mergeIndex_ + 1, currentValue); // 1: merge
682 }
683 mergeValueSelector = result = phi;
684 }
685 // build value selector for loop begin.
686 // If the register value of the corresponding bit is changed in the loop or
687 // there is a state that needs to be merged (e.g.Multiple values or branches need to be merged into a phi node)
688 // need to create or update the phi node.
689 if (IsGateNotEmpty(mergedContext->loopBackState_) && (changedInLoop || needMergeValues)) {
690 size_t numOfIns = acc_.GetNumIns(mergedContext->loopBackState_);
691 auto inList = std::vector<GateRef>(numOfIns + 1, Circuit::NullGate()); // 1: state
692 auto phi = circuit_->NewGate(
693 circuit_->ValueSelector(numOfIns), MachineType::I64, inList.size(), inList.data(),
694 GateType::AnyType());
695 acc_.NewIn(phi, 0, mergedContext->loopBackState_);
696 if (IsGateNotEmpty(mergedContext->mergeState_)) {
697 acc_.NewIn(phi, 1, mergeValueSelector); // 1: merge
698 }
699 if (IsGateNotEmpty(nextValue)) {
700 for (size_t i = 1; i < mergedContext->loopBackIndex_; i++) {
701 acc_.NewIn(phi, i + 1, nextValue); // 1: merge
702 }
703 }
704 if (isLoopBack || !IsGateNotEmpty(mergedContext->mergeState_)) {
705 acc_.NewIn(phi, mergedContext->loopBackIndex_ + 1, currentValue); // 1: merge
706 }
707 result = phi;
708 }
709 }
710 return result;
711 }
712
GetCorrespondingState(const BytecodeRegion & bb,const BytecodeRegion & bbNext)713 MergeStateDependInfo FrameStateBuilder::GetCorrespondingState(const BytecodeRegion &bb, const BytecodeRegion &bbNext)
714 {
715 auto mergedContext = GetMergedBbContext(bbNext.id);
716 if (IsLoopHead(bbNext)) {
717 if (!IfLoopNeedMerge(bbNext)) { // 1: only one loop in
718 ASSERT(!IsGateNotEmpty(mergedContext->mergeState_));
719 ASSERT(!IsGateNotEmpty(mergedContext->mergeDepend_));
720 return {mergedContext->loopBackState_, mergedContext->loopBackDepend_, mergedContext->loopBackIndex_};
721 }
722 if (bbNext.IsLoopBack(bb)) {
723 return {mergedContext->loopBackState_, mergedContext->loopBackDepend_, mergedContext->loopBackIndex_};
724 } else {
725 return {mergedContext->mergeState_, mergedContext->mergeDepend_, mergedContext->mergeIndex_};
726 }
727 } else {
728 ASSERT(!IsGateNotEmpty(mergedContext->loopBackState_));
729 ASSERT(!IsGateNotEmpty(mergedContext->loopBackDepend_));
730 return {mergedContext->mergeState_, mergedContext->mergeDepend_, mergedContext->mergeIndex_};
731 }
732 }
733
MergeAssignment(const BytecodeRegion & bb,const BytecodeRegion & bbNext)734 void FrameStateBuilder::MergeAssignment(const BytecodeRegion &bb, const BytecodeRegion &bbNext)
735 {
736 auto mergedContext = GetMergedBbContext(bbNext.id);
737 [[maybe_unused]] auto mergeInfo = GetCorrespondingState(bb, bbNext);
738 ASSERT(acc_.IsCFGMerge(mergeInfo.state));
739 auto liveout = GetFrameLiveoutBefore(bbNext.id);
740 auto *loopAssignment = GetLoopAssignment(bbNext);
741 for (size_t i = 0; i < numVregs_; i++) {
742 if (liveout->TestBit(i)) {
743 auto current = liveContext_->ValuesAt(i);
744 auto next = mergedContext->ValuesAt(i);
745 GateRef value = Circuit::NullGate();
746 #ifndef NDEBUG
747 if (loopAssignment == nullptr) {
748 ASSERT(IsGateNotEmpty(current) && IsGateNotEmpty(next));
749 } else if (loopAssignment->TestBit(i)) {
750 // next is null or phi
751 ASSERT(!IsGateNotEmpty(next) ||
752 ((acc_.GetOpCode(next) == OpCode::VALUE_SELECTOR) &&
753 acc_.GetState(next) == mergedContext->currentState_));
754 } else if (!IsGateNotEmpty(mergedContext->mergeState_)) {
755 ASSERT(!IsGateNotEmpty(next) || current == next);
756 }
757 #endif
758 bool changedInLoop = loopAssignment != nullptr && loopAssignment->TestBit(i);
759 value = MergeValue(bbNext, current, next, bbNext.IsLoopBack(bb), changedInLoop);
760 mergedContext->SetValuesAt(i, value);
761 }
762 }
763 }
764
CopyLiveoutValues(const BytecodeRegion & bbNext,FrameContext * dest,FrameContext * src)765 void FrameStateBuilder::CopyLiveoutValues(const BytecodeRegion &bbNext,
766 FrameContext* dest, FrameContext* src)
767 {
768 auto liveout = GetFrameLiveoutBefore(bbNext.id);
769 for (size_t i = 0; i < numVregs_; i++) {
770 if (liveout->TestBit(i)) {
771 auto value = src->ValuesAt(i);
772 dest->SetValuesAt(i, value);
773 } else {
774 dest->SetValuesAt(i, Circuit::NullGate());
775 }
776 }
777 }
778
GetCachedContext()779 FrameContext *FrameStateBuilder::GetCachedContext()
780 {
781 // lazy init cachedContext
782 if (cachedContext_ == nullptr) {
783 auto chunk = circuit_->chunk();
784 cachedContext_ = chunk->New<FrameContext>(chunk, numVregs_);
785 }
786 auto result = cachedContext_;
787 if (cachedContext_ == liveContext_) {
788 if (cachedContextBackup_ == nullptr) {
789 auto chunk = circuit_->chunk();
790 cachedContextBackup_ = chunk->New<FrameContext>(chunk, numVregs_);
791 }
792 result = cachedContextBackup_;
793 }
794 return result;
795 }
796
SaveCurrentContext(const BytecodeRegion & bb)797 void FrameStateBuilder::SaveCurrentContext(const BytecodeRegion &bb)
798 {
799 auto newContext = GetCachedContext();
800 ASSERT(newContext != liveContext_);
801 newContext->CopyCurrentStatus(liveContext_);
802 CopyLiveoutValues(bb, newContext, liveContext_);
803 liveContext_ = newContext;
804 }
805
NewLoopExit(const BytecodeRegion & bbNext,BitSet * loopAssignment)806 void FrameStateBuilder::NewLoopExit(const BytecodeRegion &bbNext, BitSet *loopAssignment)
807 {
808 auto state = liveContext_->currentState_;
809 auto depend = liveContext_->currentDepend_;
810 auto loopExit = circuit_->NewGate(circuit_->LoopExit(), { state });
811 auto loopExitDepend = circuit_->NewGate(circuit_->LoopExitDepend(),
812 { loopExit, depend });
813 auto liveout = GetFrameLiveoutBefore(bbNext.id);
814 for (size_t i = 0; i < numVregs_; i++) {
815 if (liveout->TestBit(i)) {
816 auto current = liveContext_->ValuesAt(i);
817 if (loopAssignment->TestBit(i)) {
818 current = circuit_->NewGate(circuit_->LoopExitValue(), acc_.GetMachineType(current),
819 {loopExit, current}, acc_.GetGateType(current));
820 }
821 liveContext_->SetValuesAt(i, current);
822 } else {
823 ASSERT(!IsGateNotEmpty(liveContext_->ValuesAt(i)));
824 }
825 }
826 liveContext_->currentState_ = loopExit;
827 liveContext_->currentDepend_ = loopExitDepend;
828 auto stateSplit = BuildStateSplit(liveContext_, liveout, bbNext.start);
829 liveContext_->currentDepend_ = stateSplit;
830 }
831
TryInsertLoopExit(const BytecodeRegion & bb,const BytecodeRegion & bbNext)832 void FrameStateBuilder::TryInsertLoopExit(const BytecodeRegion &bb, const BytecodeRegion &bbNext)
833 {
834 if (!bcBuilder_->EnableLoopOptimization() && !bcBuilder_->IsOSR()) {
835 return;
836 }
837 if (bcBuilder_->IsOSR() && bcBuilder_->IsCacheBBOfOSRLoop(bbNext)) {
838 return;
839 }
840 auto currentLoop = GetLoopInfoByLoopBody(bb);
841 if (currentLoop != nullptr && !currentLoop->loopBodys->TestBit(bbNext.id)) {
842 // use bbNext as merged values
843 SaveCurrentContext(bbNext);
844 }
845 while (currentLoop != nullptr && !currentLoop->loopBodys->TestBit(bbNext.id)) {
846 ASSERT(currentLoop->loopExits != nullptr);
847 #ifndef NDEBUG
848 bool found = false;
849 for (auto current : *currentLoop->loopExits) {
850 if (current->id == bbNext.id) {
851 found = true;
852 break;
853 }
854 }
855 ASSERT(found);
856 #endif
857 NewLoopExit(bbNext, currentLoop->loopAssignment);
858 currentLoop = currentLoop->parentInfo;
859 }
860 }
861
AdvanceToNextBB(const BytecodeRegion & bb,bool isOsrLoopExit)862 void FrameStateBuilder::AdvanceToNextBB(const BytecodeRegion &bb, bool isOsrLoopExit)
863 {
864 liveContext_ = GetMergedBbContext(bb.id);
865 ASSERT(liveContext_ != nullptr);
866 if (bb.loopNumber > 0) {
867 // use bb as merged values
868 SaveCurrentContext(bb);
869 } else if (!isOsrLoopExit) {
870 // all input merged
871 ASSERT(liveContext_->currentIndex_ == bb.numOfStatePreds);
872 }
873 if (liveContext_->needStateSplit_) {
874 liveContext_->needStateSplit_ = false;
875 auto liveout = GetOrOCreateBBLiveOut(bb.id);
876 auto stateSplit = BuildStateSplit(liveContext_, liveout, bb.start);
877 liveContext_->currentDepend_ = stateSplit;
878 }
879 if (!bb.trys.empty()) {
880 auto liveout = GetOrOCreateBBLiveOut(bb.id);
881 UpdateCatchState(bb.start, liveout);
882 }
883 }
884
885 class SubContextScope {
886 public:
SubContextScope(FrameStateBuilder * frameBuilder)887 explicit SubContextScope(FrameStateBuilder* frameBuilder)
888 : frameBuilder_(frameBuilder)
889 {
890 originContext_ = frameBuilder->liveContext_;
891 }
892
~SubContextScope()893 ~SubContextScope()
894 {
895 frameBuilder_->liveContext_ = originContext_;
896 }
897 private:
898 FrameContext* originContext_ {nullptr};
899 FrameStateBuilder* frameBuilder_ {nullptr};
900 };
901
MergeIntoSuccessor(const BytecodeRegion & bb,const BytecodeRegion & bbNext)902 void FrameStateBuilder::MergeIntoSuccessor(const BytecodeRegion &bb, const BytecodeRegion &bbNext)
903 {
904 [[maybe_unused]] SubContextScope scope(this);
905 TryInsertLoopExit(bb, bbNext);
906 auto mergedContext = GetOrOCreateMergedContext(bbNext.id);
907 MergeStateDepend(bb, bbNext);
908 if (mergedContext->currentIndex_ == 0) {
909 if (bbNext.loopNumber > 0) {
910 MergeAssignment(bb, bbNext);
911 } else {
912 CopyLiveoutValues(bbNext, mergedContext, liveContext_);
913 }
914 } else {
915 MergeAssignment(bb, bbNext);
916 }
917 // We should connect this gate to loop begin although it's not a loop back edge
918 // if there is no merge state, which means it's the sole loop in.
919 if (bbNext.IsLoopBack(bb) || !IsGateNotEmpty(mergedContext->mergeState_)) {
920 mergedContext->loopBackIndex_++;
921 } else {
922 mergedContext->mergeIndex_++;
923 }
924 mergedContext->currentIndex_++;
925 }
926
IsLoopBackEdge(const BytecodeRegion & bb,const BytecodeRegion & bbNext)927 bool FrameStateBuilder::IsLoopBackEdge(const BytecodeRegion &bb, const BytecodeRegion &bbNext)
928 {
929 if (bcBuilder_->IsOSR() && OutOfOsrLoop(bbNext)) {
930 return false;
931 } else if (bbNext.loopNumber > 0) {
932 auto& loopInfo = GetLoopInfo(bbNext);
933 return loopInfo.loopBodys->TestBit(bb.id);
934 }
935 return false;
936 }
937
GetLoopInfo(const BytecodeRegion & bb)938 FrameStateBuilder::LoopInfo& FrameStateBuilder::GetLoopInfo(const BytecodeRegion &bb)
939 {
940 ASSERT(bb.loopNumber > 0);
941 return loops_[bb.loopNumber - 1]; // -1: for index
942 }
943
GetLoopInfo(BytecodeRegion & bb)944 FrameStateBuilder::LoopInfo& FrameStateBuilder::GetLoopInfo(BytecodeRegion &bb)
945 {
946 ASSERT(bb.loopNumber > 0);
947 return loops_[bb.loopNumber - 1]; // -1: for index
948 }
949
GetLoopInfoByLoopBody(const BytecodeRegion & bb)950 FrameStateBuilder::LoopInfo* FrameStateBuilder::GetLoopInfoByLoopBody(const BytecodeRegion &bb)
951 {
952 if (bb.loopIndex == 0) {
953 return nullptr;
954 }
955 auto& loopInfo = loops_[bb.loopIndex - 1];
956 ASSERT(loopInfo.loopBodys->TestBit(bb.id));
957 return &loopInfo;
958 }
959
GetLoopAssignment(const BytecodeRegion & bb)960 BitSet *FrameStateBuilder::GetLoopAssignment(const BytecodeRegion &bb)
961 {
962 if (bb.loopNumber > 0) {
963 auto& loopInfo = GetLoopInfo(bb);
964 return loopInfo.loopAssignment;
965 }
966 return nullptr;
967 }
968
AddEmptyBlock(BytecodeRegion * bb)969 void FrameStateBuilder::AddEmptyBlock(BytecodeRegion* bb)
970 {
971 bbBeginStateLiveouts_.emplace_back(nullptr);
972 bbFrameContext_.emplace_back(nullptr);
973 auto liveout = GetOrOCreateBBLiveOut(bb->id);
974 liveout->CopyFrom(liveOutResult_);
975 GetOrOCreateMergedContext(bb->id);
976 bcBuilder_->AddBasicBlock(bb);
977 }
978
979 class BlockLoopAnalysis {
980 public:
BlockLoopAnalysis(FrameStateBuilder * builder,Chunk * chunk)981 explicit BlockLoopAnalysis(FrameStateBuilder *builder, Chunk* chunk)
982 : frameBuilder_(builder), bcBuilder_(builder->bcBuilder_),
983 pendingList_(chunk), loopbacks_(chunk),
984 dfsStack_(chunk), visitState_(chunk), chunk_(chunk) {}
985
Run()986 void Run()
987 {
988 ComputeLoopBack();
989 if (bcBuilder_->TerminateAnalysis()) {
990 return;
991 }
992 TryClearDeadBlock();
993 bcBuilder_->ComputeNumOfLoopBack();
994 frameBuilder_->numLoops_ = numLoops_;
995 if (numLoops_ > 0) {
996 ComputeLoopInfo();
997 if (bcBuilder_->IsLogEnabled()) {
998 for (size_t i = 0; i < numLoops_; i++) {
999 auto& loopInfo = frameBuilder_->loops_[i];
1000 PrintLoop(loopInfo);
1001 }
1002 }
1003 }
1004 }
1005
CountLoopBackEdge(size_t fromId,size_t toId)1006 void CountLoopBackEdge(size_t fromId, size_t toId)
1007 {
1008 loopbacks_.push_back({fromId, toId});
1009 auto &toBlock = bcBuilder_->GetBasicBlockById(toId);
1010 toBlock.loopBacks.insert(fromId);
1011 if (toBlock.loopNumber == 0) {
1012 toBlock.loopNumber = ++numLoops_;
1013 }
1014 }
1015
CheckDominance()1016 void CheckDominance()
1017 {
1018 for (size_t i = 0; i < loopbacks_.size(); i++) {
1019 auto loopBackinfo = loopbacks_[i];
1020 bool isDom = bcBuilder_->IsAncestor(loopBackinfo.toId, loopBackinfo.fromId);
1021 if (!isDom) {
1022 bcBuilder_->SetIrreducibleLoop();
1023 LOG_COMPILER(INFO) << "CFG is not reducible. Compilation aborted.";
1024 break;
1025 }
1026 }
1027 }
1028
ComputeLoopBack()1029 void ComputeLoopBack()
1030 {
1031 auto size = bcBuilder_->GetBasicBlockCount();
1032 visitState_.resize(size, MarkState::UNVISITED);
1033 size_t entryId = 0; // entry id
1034 VisitedInfo info = {0, false};
1035 visitedInfo_.resize(size, info);
1036 pendingList_.emplace_back(entryId);
1037 while (!pendingList_.empty()) {
1038 size_t bbId = pendingList_.back();
1039 auto &bb = bcBuilder_->GetBasicBlockById(bbId);
1040 bool allVisited = true;
1041 visitState_[bbId] = MarkState::PENDING;
1042 BytecodeRegion* catchBlock = bb.catches.empty() ? nullptr : bb.catches.at(0);
1043 for (size_t i = visitedInfo_[bbId].needVisitIndex; i < bb.succs.size(); i++) {
1044 BytecodeRegion* succBlock = bb.succs[i];
1045 size_t succId = succBlock->id;
1046 visitedInfo_[bbId].needVisitIndex = i + 1;
1047 if (visitState_[succId] == MarkState::UNVISITED) {
1048 pendingList_.emplace_back(succId);
1049 visitState_[succId] = MarkState::ON_STACK;
1050 allVisited = false;
1051 break;
1052 } else if (visitState_[succId] == MarkState::PENDING) {
1053 // back edge
1054 CountLoopBackEdge(bbId, succId);
1055 }
1056 }
1057 // we consider catchBlock as a special succ, which means if we have visited a succ,
1058 // visiting catchBlock is not allowed due to the rule of RPO.
1059 if (allVisited && catchBlock != nullptr && !visitedInfo_[bbId].isVisitedCatchBlock) {
1060 size_t catchId = catchBlock->id;
1061 visitedInfo_[bbId].isVisitedCatchBlock = true;
1062 if (visitState_[catchId] == MarkState::UNVISITED) {
1063 pendingList_.emplace_back(catchId);
1064 visitState_[catchId] = MarkState::ON_STACK;
1065 allVisited = false;
1066 } else if (visitState_[catchId] == MarkState::PENDING) {
1067 // back edge
1068 CountLoopBackEdge(bbId, catchId);
1069 }
1070 }
1071 if (allVisited) {
1072 visitState_[bbId] = MarkState::VISITED;
1073 pendingList_.pop_back();
1074 frameBuilder_->rpoList_.push_front(bbId);
1075 }
1076 }
1077
1078 if (bcBuilder_->NeedIrreducibleLoopCheck()) {
1079 CheckDominance();
1080 }
1081 }
1082
TryClearDeadBlock()1083 void TryClearDeadBlock()
1084 {
1085 if (frameBuilder_->rpoList_.size() == bcBuilder_->NumberOfLiveBlock()) {
1086 return;
1087 }
1088 auto size = bcBuilder_->GetBasicBlockCount();
1089 for (size_t i = 0; i < size; i++) {
1090 auto &bb = bcBuilder_->GetBasicBlockById(i);
1091 if (bb.numOfStatePreds != 0 && visitState_[i] == MarkState::UNVISITED) {
1092 bb.numOfStatePreds = 0;
1093 }
1094 }
1095 bcBuilder_->RemoveUnreachableRegion();
1096 }
1097
CountLoopBody(FrameStateBuilder::LoopInfo & loopInfo,size_t bbId)1098 void CountLoopBody(FrameStateBuilder::LoopInfo& loopInfo, size_t bbId)
1099 {
1100 if (bbId != loopInfo.loopHeadId && !loopInfo.loopBodys->TestBit(bbId)) {
1101 loopInfo.loopBodys->SetBit(bbId);
1102 pendingList_.emplace_back(bbId);
1103 auto liveout = frameBuilder_->GetOrOCreateBBLiveOut(bbId);
1104 ASSERT(liveout != nullptr);
1105 loopInfo.loopAssignment->Union(liveout->defRegisters_);
1106 }
1107 }
1108
PropagateLoopBody(FrameStateBuilder::LoopInfo & loopInfo)1109 void PropagateLoopBody(FrameStateBuilder::LoopInfo& loopInfo)
1110 {
1111 while (!pendingList_.empty()) {
1112 auto cur = pendingList_.back();
1113 auto &curBlock = bcBuilder_->GetBasicBlockById(cur);
1114 pendingList_.pop_back();
1115 for (auto pred : curBlock.preds) {
1116 CountLoopBody(loopInfo, pred->id);
1117 }
1118 for (auto pred : curBlock.trys) {
1119 CountLoopBody(loopInfo, pred->id);
1120 }
1121 }
1122 }
1123
InitLoopInfo(FrameStateBuilder::LoopInfo & loopInfo,BytecodeRegion & loopHeader,size_t backId)1124 void InitLoopInfo(FrameStateBuilder::LoopInfo& loopInfo, BytecodeRegion& loopHeader, size_t backId)
1125 {
1126 if (loopInfo.loopHeadId == 0) {
1127 auto size = bcBuilder_->GetBasicBlockCount();
1128 loopInfo.loopHeadId = loopHeader.id;
1129 loopInfo.loopIndex = loopHeader.loopNumber;
1130 loopInfo.loopBodys = chunk_->New<BitSet>(chunk_, size);
1131 loopInfo.loopAssignment = chunk_->New<BitSet>(chunk_, frameBuilder_->numVregs_);
1132 loopHeader.loopIndex = loopInfo.loopIndex;
1133 loopInfo.loopBodys->SetBit(loopInfo.loopHeadId);
1134 auto liveout = frameBuilder_->GetOrOCreateBBLiveOut(loopInfo.loopHeadId);
1135 loopInfo.loopAssignment->Union(liveout->defRegisters_);
1136 loopInfo.numLoopBacks = 1;
1137 loopInfo.loopBodys->SetBit(backId);
1138 } else {
1139 if (!loopInfo.loopBodys->TestBit(backId)) {
1140 loopInfo.loopBodys->SetBit(backId);
1141 }
1142 loopInfo.numLoopBacks++;
1143 }
1144 }
1145
ComputeLoopInfo()1146 void ComputeLoopInfo()
1147 {
1148 frameBuilder_->loops_.resize(numLoops_, FrameStateBuilder::LoopInfo());
1149 for (auto& info : loopbacks_) {
1150 auto& toBlock = bcBuilder_->GetBasicBlockById(info.toId);
1151 auto& loopInfo = frameBuilder_->GetLoopInfo(toBlock);
1152 InitLoopInfo(loopInfo, toBlock, info.fromId);
1153 }
1154 TryMergeLoopEntry();
1155 ResizeLoopBody(); // tryMerge will insert region, need resize loop body.
1156 for (auto& info : loopbacks_) {
1157 auto& toBlock = bcBuilder_->GetBasicBlockById(info.toId);
1158 auto& loopInfo = frameBuilder_->GetLoopInfo(toBlock);
1159 CountLoopBody(loopInfo, info.fromId);
1160 PropagateLoopBody(loopInfo);
1161 }
1162
1163 if (!bcBuilder_->EnableLoopOptimization() && !bcBuilder_->IsOSR()) {
1164 return;
1165 }
1166
1167 auto size = bcBuilder_->GetBasicBlockCount();
1168 dfsStack_.resize(size, DFSState(0, 0));
1169 ComputeLoopTree();
1170 }
1171
InsertEmptyBytecodeRegion(FrameStateBuilder::LoopInfo & loopInfo,BytecodeRegion & loopHeader,size_t numOfEntries)1172 void InsertEmptyBytecodeRegion(FrameStateBuilder::LoopInfo& loopInfo,
1173 BytecodeRegion& loopHeader, size_t numOfEntries)
1174 {
1175 auto size = bcBuilder_->GetBasicBlockCount();
1176 auto block = chunk_->New<BytecodeRegion>(chunk_);
1177 block->id = size;
1178 block->numOfStatePreds = numOfEntries;
1179 block->start = loopHeader.start;
1180 ASSERT(loopHeader.start != 0);
1181 block->end = BytecodeIterator::INVALID_INDEX;
1182 block->bytecodeIterator_.Reset(bcBuilder_, block->start, block->end);
1183
1184 frameBuilder_->liveOutResult_->Reset();
1185 for (auto it = loopHeader.preds.begin(); it != loopHeader.preds.end();) {
1186 auto bbPred = *it;
1187 // not loop back
1188 if (!loopInfo.loopBodys->TestBit(bbPred->id)) {
1189 it = loopHeader.preds.erase(it);
1190 std::replace(bbPred->succs.begin(), bbPred->succs.end(), &loopHeader, block);
1191 block->preds.emplace_back(bbPred);
1192 } else {
1193 it++;
1194 }
1195 }
1196 frameBuilder_->MergeFromSuccBB(loopHeader.id);
1197 block->succs.emplace_back(&loopHeader);
1198 loopHeader.preds.insert(loopHeader.preds.begin(), block);
1199 frameBuilder_->AddEmptyBlock(block);
1200
1201 ASSERT(loopHeader.trys.empty() && numOfEntries > 0);
1202 loopHeader.numOfStatePreds -= (numOfEntries - 1); // 1: one entry
1203 auto it = std::find(frameBuilder_->rpoList_.begin(), frameBuilder_->rpoList_.end(), loopHeader.id);
1204 ASSERT(it != frameBuilder_->rpoList_.end());
1205 frameBuilder_->rpoList_.insert(it, block->id);
1206 visitState_.emplace_back(MarkState::UNVISITED1);
1207 }
1208
TryMergeLoopEntry()1209 void TryMergeLoopEntry()
1210 {
1211 for (size_t i = 0; i < numLoops_; i++) {
1212 auto& loopInfo = frameBuilder_->loops_[i];
1213 auto& loopHeader = bcBuilder_->GetBasicBlockById(loopInfo.loopHeadId);
1214 ASSERT(loopHeader.numOfStatePreds > loopInfo.numLoopBacks);
1215 size_t numOfEntries = static_cast<size_t>(loopHeader.numOfStatePreds - loopInfo.numLoopBacks);
1216 if (numOfEntries > 1 && loopHeader.trys.size() == 0) {
1217 InsertEmptyBytecodeRegion(loopInfo, loopHeader, numOfEntries);
1218 }
1219 // clear loopback bits for visit body
1220 loopInfo.loopBodys->Reset();
1221 loopInfo.loopBodys->SetBit(loopInfo.loopHeadId);
1222 }
1223 }
1224
ResizeLoopBody()1225 void ResizeLoopBody()
1226 {
1227 for (auto& info : loopbacks_) {
1228 auto size = bcBuilder_->GetBasicBlockCount();
1229 auto& toBlock = bcBuilder_->GetBasicBlockById(info.toId);
1230 auto& loopInfo = frameBuilder_->GetLoopInfo(toBlock);
1231 if (loopInfo.loopBodys->ShouldExpand(size)) {
1232 auto tmp = loopInfo.loopBodys;
1233 loopInfo.loopBodys = chunk_->New<BitSet>(chunk_, size);
1234 loopInfo.loopBodys->CopyDataFrom(*tmp);
1235 }
1236 }
1237 }
1238
EnterInnerLoop(FrameStateBuilder::LoopInfo * loopInfo,size_t bbId)1239 FrameStateBuilder::LoopInfo* EnterInnerLoop(FrameStateBuilder::LoopInfo* loopInfo, size_t bbId)
1240 {
1241 auto &bb = bcBuilder_->GetBasicBlockById(bbId);
1242 if (bb.loopNumber > 0) {
1243 auto &innerInfo = frameBuilder_->GetLoopInfo(bb);
1244 ASSERT(innerInfo.parentInfo == nullptr);
1245 innerInfo.parentInfo = loopInfo;
1246 innerInfo.sortIndx = frameBuilder_->sortIndx_++;
1247 loopInfo = &innerInfo;
1248 } else if (loopInfo != nullptr) {
1249 bb.loopIndex = loopInfo->loopIndex;
1250 }
1251 return loopInfo;
1252 }
1253
ComputeLoopTree()1254 void ComputeLoopTree()
1255 {
1256 FrameStateBuilder::LoopInfo* loopInfo = nullptr;
1257 auto currentDepth = Push(0, 0); // entry id
1258 while (currentDepth > 0) {
1259 auto &curState = dfsStack_[currentDepth - 1]; // -1: for current
1260 auto const &bb = bcBuilder_->GetBasicBlockById(curState.bbId);
1261 if (!bcBuilder_->IsOSR()) {
1262 ASSERT(bb.catches.empty());
1263 }
1264 auto index = curState.index;
1265 BytecodeRegion* bbNext = nullptr;
1266 if (index >= bb.succs.size()) {
1267 if (bb.loopNumber > 0) {
1268 if (visitState_[curState.bbId] == MarkState::ON_STACK) {
1269 if (loopInfo == nullptr) {
1270 continue;
1271 }
1272 ASSERT(loopInfo->loopHeadId == curState.bbId);
1273 loopInfo = loopInfo->parentInfo;
1274 visitState_[curState.bbId] = MarkState::VISITED1;
1275 }
1276 bbNext = PushLoopExist(bb, currentDepth);
1277 }
1278 } else {
1279 bbNext = bb.succs[curState.index++]; // 1: goto next
1280 }
1281 if (bbNext != nullptr) {
1282 if (loopInfo != nullptr && !loopInfo->loopBodys->TestBit(bbNext->id)) {
1283 AddLoopExit(bbNext, loopInfo);
1284 } else if (visitState_[bbNext->id] == MarkState::UNVISITED1) {
1285 currentDepth = Push(bbNext->id, currentDepth);
1286 loopInfo = EnterInnerLoop(loopInfo, bbNext->id);
1287 }
1288 } else {
1289 if (bb.loopNumber == 0) {
1290 visitState_[curState.bbId] = MarkState::VISITED1;
1291 }
1292 currentDepth--;
1293 }
1294 }
1295 }
1296
Push(size_t bbId,size_t depth)1297 size_t Push(size_t bbId, size_t depth)
1298 {
1299 if (visitState_[bbId] == MarkState::UNVISITED1) {
1300 dfsStack_[depth].bbId = bbId;
1301 dfsStack_[depth].index = 0;
1302 visitState_[bbId] = MarkState::ON_STACK;
1303 return depth + 1;
1304 }
1305 return depth;
1306 }
1307
PushLoopExist(const BytecodeRegion & bb,size_t depth)1308 BytecodeRegion* PushLoopExist(const BytecodeRegion& bb, size_t depth)
1309 {
1310 ASSERT(depth > 0);
1311 auto &curState = dfsStack_[depth - 1]; // -1: for current
1312 auto loopExitIndex = curState.index - bb.succs.size();
1313 auto& currentInfo = frameBuilder_->GetLoopInfo(bb);
1314 BytecodeRegion* bbNext = nullptr;
1315 if (currentInfo.loopExits != nullptr && loopExitIndex < currentInfo.loopExits->size()) {
1316 bbNext = currentInfo.loopExits->at(loopExitIndex);
1317 curState.index++; // 1: goto next
1318 }
1319 return bbNext;
1320 }
1321
AddLoopExit(BytecodeRegion * bb,FrameStateBuilder::LoopInfo * loopInfo)1322 void AddLoopExit(BytecodeRegion *bb, FrameStateBuilder::LoopInfo *loopInfo)
1323 {
1324 if (loopInfo->loopExits == nullptr) {
1325 loopInfo->loopExits = chunk_->New<ChunkVector<BytecodeRegion*>>(chunk_);
1326 }
1327 loopInfo->loopExits->emplace_back(bb);
1328 }
1329
PrintLoop(FrameStateBuilder::LoopInfo & loopInfo)1330 void PrintLoop(FrameStateBuilder::LoopInfo& loopInfo)
1331 {
1332 auto size = bcBuilder_->GetBasicBlockCount();
1333 LOG_COMPILER(INFO) << "--------------------------------- LoopInfo Start ---------------------------------";
1334 LOG_COMPILER(INFO) << "LoopHead: " << loopInfo.loopHeadId;
1335 if (loopInfo.parentInfo != nullptr) {
1336 LOG_COMPILER(INFO) << "ParentLoopHead: " << loopInfo.parentInfo->loopHeadId;
1337 }
1338 std::string log = "Body: [";
1339 for (size_t i = 0; i < size; i++) {
1340 if (loopInfo.loopBodys->TestBit(i)) {
1341 log += std::to_string(i) + ", ";
1342 }
1343 }
1344 LOG_COMPILER(INFO) << log << "]";
1345 std::string log1 = "Exit: [";
1346 if (loopInfo.loopExits != nullptr) {
1347 for (auto bb : *loopInfo.loopExits) {
1348 log1 += std::to_string(bb->id) + ", ";
1349 }
1350 }
1351 LOG_COMPILER(INFO) << log1 << "]";
1352 std::string log2 = "LoopAssignment [";
1353 bool firset = true;
1354 for (size_t i = 0; i < frameBuilder_->numVregs_; i++) {
1355 if (loopInfo.loopAssignment->TestBit(i)) {
1356 if (!firset) {
1357 log2 += ",";
1358 }
1359 firset = false;
1360 log2 += std::to_string(i);
1361 }
1362 }
1363 LOG_COMPILER(INFO) << log2 << "]";
1364 LOG_COMPILER(INFO) << "--------------------------------- LoopInfo End ---------------------------------";
1365 }
1366
1367 private:
1368 struct EndToHead {
1369 size_t fromId;
1370 size_t toId;
1371 };
1372 struct DFSState {
DFSStatepanda::ecmascript::kungfu::BlockLoopAnalysis::DFSState1373 DFSState(size_t bbId, size_t index)
1374 : bbId(bbId), index(index) {}
1375
1376 size_t bbId;
1377 size_t index;
1378 };
1379 struct VisitedInfo {
1380 size_t needVisitIndex;
1381 bool isVisitedCatchBlock = false;
1382 };
1383 enum class MarkState : uint8_t {
1384 UNVISITED = 0,
1385 ON_STACK,
1386 PENDING,
1387 VISITED,
1388 VISITED1,
1389 UNVISITED1 = VISITED
1390 };
1391 FrameStateBuilder* frameBuilder_ {nullptr};
1392 BytecodeCircuitBuilder *bcBuilder_ {nullptr};
1393 ChunkDeque<size_t> pendingList_;
1394 ChunkVector<EndToHead> loopbacks_;
1395 ChunkVector<DFSState> dfsStack_;
1396 ChunkVector<MarkState> visitState_;
1397 Chunk* chunk_ {nullptr};
1398 size_t numLoops_ {0};
1399 std::vector<VisitedInfo> visitedInfo_;
1400 };
1401
ComputeLoopInfo()1402 void FrameStateBuilder::ComputeLoopInfo()
1403 {
1404 BlockLoopAnalysis loopAnalysis(this, circuit_->chunk());
1405 loopAnalysis.Run();
1406 if (numLoops_ != 0 && !bcBuilder_->HasIrreducibleLoop()) {
1407 ChunkVector<GateRef>& headerGates = bcBuilder_->GetLoopHeaderGates();
1408 headerGates.resize(numLoops_, Circuit::NullGate());
1409 }
1410 }
1411
DumpLiveState()1412 void FrameStateBuilder::DumpLiveState()
1413 {
1414 LOG_COMPILER(INFO) << "DumpLiveState";
1415 for (size_t i = 0; i < bcEndStateLiveouts_.size(); i++) {
1416 auto liveout = GetFrameLiveoutAfter(i);
1417 if (liveout == nullptr) {
1418 continue;
1419 }
1420 std::string log = "BC: " + std::to_string(i) + " {";
1421 bool firset = true;
1422 for (size_t j = 0; j < numVregs_; j++) {
1423 if (liveout->TestBit(j)) {
1424 if (!firset) {
1425 log += ",";
1426 }
1427 firset = false;
1428 log += std::to_string(j);
1429 }
1430 }
1431 log += "}";
1432 LOG_COMPILER(INFO) << log;
1433 }
1434 for (size_t i = 1; i < bbBeginStateLiveouts_.size(); i++) { // 1: skip entry
1435 auto liveout = GetFrameLiveoutBefore(i);
1436 if (liveout == nullptr) {
1437 continue;
1438 }
1439 std::string log = "BB: " + std::to_string(i) + " {";
1440 bool firset = true;
1441 for (size_t j = 0; j < numVregs_; j++) {
1442 if (liveout->TestBit(j)) {
1443 if (!firset) {
1444 log += ",";
1445 }
1446 firset = false;
1447 log += std::to_string(j);
1448 }
1449 }
1450 log += "}";
1451 LOG_COMPILER(INFO) << log;
1452 }
1453 }
1454
BuildFrameState(FrameContext * frameContext,FrameLiveOut * liveout,size_t bcIndex)1455 GateRef FrameStateBuilder::BuildFrameState(FrameContext* frameContext, FrameLiveOut* liveout, size_t bcIndex)
1456 {
1457 auto pcOffset = bcBuilder_->GetPcOffset(bcIndex);
1458 GateRef gateValues = BuildFrameValues(frameContext, liveout);
1459
1460 GateRef frameArgs = bcBuilder_->GetFrameArgs();
1461 GateRef preFrameState = bcBuilder_->GetPreFrameState();
1462 UInt32PairAccessor accessor(static_cast<uint32_t>(pcOffset),
1463 FrameStateOutput::Invalid().GetValue());
1464 auto frameState = circuit_->NewGate(circuit_->FrameState(accessor.ToValue()),
1465 {frameArgs, gateValues, preFrameState});
1466 return frameState;
1467 }
1468
BuildStateSplit(FrameContext * frameContext,FrameLiveOut * liveout,size_t bcIndex)1469 GateRef FrameStateBuilder::BuildStateSplit(FrameContext* frameContext, FrameLiveOut* liveout, size_t bcIndex)
1470 {
1471 auto frameState = BuildFrameState(frameContext, liveout, bcIndex);
1472 auto state = frameContext->currentState_;
1473 auto depend = frameContext->currentDepend_;
1474 ASSERT(IsGateNotEmpty(state));
1475 ASSERT(IsGateNotEmpty(depend));
1476 return circuit_->NewGate(circuit_->StateSplit(), {state, depend, frameState});
1477 }
1478
BuildFrameStateBefore(const BytecodeInfo & bytecodeInfo,FrameLiveOut * liveout,uint32_t bcId)1479 void FrameStateBuilder::BuildFrameStateBefore(const BytecodeInfo &bytecodeInfo, FrameLiveOut* liveout, uint32_t bcId)
1480 {
1481 if (bytecodeInfo.NeedFrameStateInPlace()) {
1482 frameStateCache_ = BuildFrameState(liveContext_, liveout, bcId);
1483 }
1484 ASSERT(!liveContext_->needStateSplit_);
1485 }
1486
BindFrameStateAndStateSplitAfter(const BytecodeInfo & bytecodeInfo,uint32_t bcId,GateRef gate)1487 void FrameStateBuilder::BindFrameStateAndStateSplitAfter(const BytecodeInfo &bytecodeInfo,
1488 uint32_t bcId, GateRef gate)
1489 {
1490 if (bytecodeInfo.NeedFrameStateInPlace()) {
1491 auto frameState = GetBcFrameStateCache();
1492 acc_.ReplaceFrameStateIn(gate, frameState);
1493 }
1494 if (!bytecodeInfo.NoSideEffects() && !bytecodeInfo.IsThrow()) {
1495 auto stateSplit = BuildStateSplit(liveContext_, GetOrOCreateBCEndLiveOut(bcId), bcId + 1); // 1: for after
1496 liveContext_->currentDepend_ = stateSplit;
1497 }
1498 }
1499
BuildFrameValues(FrameContext * frameContext,FrameLiveOut * liveout)1500 GateRef FrameStateBuilder::BuildFrameValues(FrameContext* frameContext, FrameLiveOut* liveout)
1501 {
1502 size_t frameStateInputs = numVregs_;
1503 std::vector<GateRef> inList(frameStateInputs, Circuit::NullGate());
1504 auto optimizedGate = circuit_->GetConstantGate(MachineType::I64,
1505 JSTaggedValue::VALUE_OPTIMIZED_OUT,
1506 GateType::TaggedValue());
1507 for (size_t i = 0; i < numVregs_; i++) {
1508 auto value = frameContext->ValuesAt(i);
1509 if (!IsGateNotEmpty(value) || !liveout->TestBit(i)) {
1510 value = optimizedGate;
1511 }
1512 inList[i] = value;
1513 }
1514 return circuit_->NewGate(circuit_->FrameValues(frameStateInputs), inList);
1515 }
1516 }
1517