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