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