• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /*
2  * Copyright (c) 2021 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 #ifndef ECMASCRIPT_CLASS_LINKER_BYTECODE_CIRCUIT_IR_BUILDER_H
17 #define ECMASCRIPT_CLASS_LINKER_BYTECODE_CIRCUIT_IR_BUILDER_H
18 
19 #include <algorithm>
20 #include <numeric>
21 #include <tuple>
22 #include <utility>
23 #include <vector>
24 #include <variant>
25 
26 #include "ecmascript/compiler/argument_accessor.h"
27 #include "ecmascript/compiler/bytecode_info_collector.h"
28 #include "ecmascript/compiler/bytecodes.h"
29 #include "ecmascript/compiler/circuit.h"
30 #include "ecmascript/compiler/ecma_opcode_des.h"
31 #include "ecmascript/compiler/frame_states.h"
32 #include "ecmascript/compiler/type_recorder.h"
33 #include "ecmascript/interpreter/interpreter-inl.h"
34 #include "ecmascript/jspandafile/js_pandafile.h"
35 #include "ecmascript/jspandafile/method_literal.h"
36 #include "ecmascript/compiler/compiler_log.h"
37 
38 namespace panda::ecmascript::kungfu {
39 
40 enum class VisitState : uint8_t {
41     UNVISITED,
42     PENDING,
43     VISITED
44 };
45 
46 struct ExceptionItem {
47     uint8_t* startPc;
48     uint8_t* endPc;
49     std::vector<uint8_t*> catchs;
50 
ExceptionItemExceptionItem51     ExceptionItem(uint8_t* startPc, uint8_t* endPc, std::vector<uint8_t*> catchs)
52         : startPc(startPc), endPc(endPc), catchs(catchs) {}
53 };
54 
55 using ExceptionInfo = std::vector<ExceptionItem>;
56 
57 class RegionItem {
58 public:
59     static constexpr uint32_t INVALID_BC_INDEX = static_cast<uint32_t>(-1);
60     bool operator<(const RegionItem &rhs) const
61     {
62         return this->startBcIndex_ < rhs.startBcIndex_;
63     }
64 
65     bool operator>(const RegionItem &rhs) const
66     {
67         return this->startBcIndex_ > rhs.startBcIndex_;
68     }
69 
70     bool operator==(const RegionItem &rhs) const
71     {
72         return this->startBcIndex_ == rhs.startBcIndex_;
73     }
74 
RegionItem(uint32_t startBcIndex,bool isHeadBlock)75     RegionItem(uint32_t startBcIndex, bool isHeadBlock)
76         : startBcIndex_(startBcIndex), isHeadBlock_(isHeadBlock) {}
77 
GetStartBcIndex()78     uint32_t GetStartBcIndex() const
79     {
80         return startBcIndex_;
81     }
82 
IsHeadBlock()83     uint32_t IsHeadBlock() const
84     {
85         return isHeadBlock_;
86     }
87 private:
88     uint32_t startBcIndex_ { INVALID_BC_INDEX };
89     bool isHeadBlock_ { false };
90     friend class RegionsInfo;
91 };
92 
93 struct BytecodeSplitItem {
BytecodeSplitItemBytecodeSplitItem94     BytecodeSplitItem(uint32_t start, uint32_t pred)
95         : startBcIndex(start), predBcIndex(pred) {}
96     uint32_t startBcIndex { RegionItem::INVALID_BC_INDEX };
97     uint32_t predBcIndex { RegionItem::INVALID_BC_INDEX };
98 };
99 
100 class RegionsInfo {
101 public:
InsertJump(uint32_t bcIndex,uint32_t predBcIndex,bool isJumpImm)102     void InsertJump(uint32_t bcIndex, uint32_t predBcIndex, bool isJumpImm)
103     {
104         InsertBlockItem(bcIndex, false);
105         auto fallThrogth = bcIndex - 1; // 1: fall through
106         // isJumpImm will not generate fall through
107         if (isJumpImm || fallThrogth != predBcIndex) {
108             InsertSplitItem(bcIndex, predBcIndex);
109         }
110     }
111 
InsertHead(uint32_t bcIndex)112     void InsertHead(uint32_t bcIndex)
113     {
114         InsertBlockItem(bcIndex, true);
115     }
116 
InsertSplit(uint32_t bcIndex)117     void InsertSplit(uint32_t bcIndex)
118     {
119         InsertBlockItem(bcIndex, false);
120     }
121 
FindBBIndexByBcIndex(uint32_t bcIndex)122     size_t FindBBIndexByBcIndex(uint32_t bcIndex) const
123     {
124         auto findFunc = [] (uint32_t value, const RegionItem &item) {
125             return value < item.startBcIndex_;
126         };
127         const auto &it = std::upper_bound(blockItems_.begin(),
128             blockItems_.end(), bcIndex, findFunc);
129         if (it == blockItems_.end()) {
130             return blockItems_.size() - 1; // 1: last bb
131         }
132         // blockItems_[0]'s value is 0, bcIndex must be: bcIndex > blockItems_.begin()
133         return std::distance(blockItems_.begin(), it) - 1; // 1: -1 for bbIndx
134     }
135 
GetSplitItems()136     const std::vector<BytecodeSplitItem> &GetSplitItems() const
137     {
138         return splitItems_;
139     }
140 
GetBlockItems()141     const std::set<RegionItem> &GetBlockItems() const
142     {
143         return blockItems_;
144     }
145 private:
InsertBlockItem(uint32_t bcIndex,bool isHeadBlock)146     void InsertBlockItem(uint32_t bcIndex, bool isHeadBlock)
147     {
148         auto result = blockItems_.insert(RegionItem { bcIndex, isHeadBlock });
149         if (!result.second && isHeadBlock) {
150             blockItems_.erase(result.first);
151             blockItems_.insert(RegionItem { bcIndex, isHeadBlock });
152         }
153     }
154 
InsertSplitItem(uint32_t bcIndex,uint32_t predBcIndex)155     void InsertSplitItem(uint32_t bcIndex, uint32_t predBcIndex)
156     {
157         splitItems_.emplace_back(BytecodeSplitItem { bcIndex, predBcIndex });
158     }
159     std::set<RegionItem> blockItems_ {};
160     std::vector<BytecodeSplitItem> splitItems_ {};
161 };
162 
163 struct BytecodeRegion {
164     size_t id {0};
165     uint32_t start {0};
166     uint32_t end {0};
167     std::vector<BytecodeRegion *> preds {}; // List of predessesor blocks
168     std::vector<BytecodeRegion *> succs {}; // List of successors blocks
169     std::vector<BytecodeRegion *> trys {}; // List of trys blocks
170     std::vector<BytecodeRegion *> catchs {}; // List of catches blocks
171     std::vector<BytecodeRegion *> immDomBlocks {}; // List of dominated blocks
172     BytecodeRegion *iDominator {nullptr}; // Block that dominates the current block
173     std::vector<BytecodeRegion *> domFrontiers {}; // List of dominace frontiers
174     std::set<size_t> loopbackBlocks {}; // List of loopback block ids
175     bool isDead {false};
176     bool phiAcc {false};
177     std::set<uint16_t> phi {}; // phi node
178     size_t numOfStatePreds {0};
179     size_t numOfLoopBacks {0};
180     size_t statePredIndex {0};
181     size_t forwardIndex {0};
182     size_t loopBackIndex {0};
183     std::vector<std::tuple<size_t, size_t, bool>> expandedPreds {};
184     GateRef stateStart {Circuit::NullGate()};
185     GateRef dependStart {Circuit::NullGate()};
186     GateRef mergeForwardEdges {Circuit::NullGate()};
187     GateRef mergeLoopBackEdges {Circuit::NullGate()};
188     GateRef depForward {Circuit::NullGate()};
189     GateRef depLoopBack {Circuit::NullGate()};
190     std::unordered_map<uint16_t, GateRef> vregToValSelectorGate {}; // corresponding ValueSelector gates of vregs
191     GateRef valueSelectorAccGate {Circuit::NullGate()};
192     BytecodeIterator bytecodeIterator_ {};
193 
GetBytecodeIteratorBytecodeRegion194     BytecodeIterator &GetBytecodeIterator() {
195         return bytecodeIterator_;
196     }
197 
198     bool operator <(const BytecodeRegion &target) const
199     {
200         return id < target.id;
201     }
202 
SortCatchesBytecodeRegion203     void SortCatches()
204     {
205         if (catchs.size() > 1) {
206             std::sort(catchs.begin(), catchs.end(), [](BytecodeRegion *first, BytecodeRegion *second) {
207                 return first->start < second->start;
208             });
209         }
210     }
211 
UpdateTryCatchInfoForDeadBlockBytecodeRegion212     void UpdateTryCatchInfoForDeadBlock()
213     {
214         // Try-Catch infos of dead block should be cleared
215         UpdateTryCatchInfo();
216         isDead = true;
217     }
218 
UpdateRedundantTryCatchInfoBytecodeRegion219     void UpdateRedundantTryCatchInfo(bool noThrow)
220     {
221         // if block which can throw exception has serval catchs block, only the innermost catch block is useful
222         if (!noThrow && catchs.size() > 1) {
223             size_t innerMostIndex = 1;
224             UpdateTryCatchInfo(innerMostIndex);
225         }
226     }
227 
UpdateTryCatchInfoIfNoThrowBytecodeRegion228     void UpdateTryCatchInfoIfNoThrow(bool noThrow)
229     {
230         // if block has no general insts, try-catch infos of it should be cleared
231         if (noThrow && !catchs.empty()) {
232             UpdateTryCatchInfo();
233         }
234     }
235 
236 private:
237     void UpdateTryCatchInfo(size_t index = 0)
238     {
239         for (auto catchBlock = catchs.begin() + index; catchBlock != catchs.end(); catchBlock++) {
240             auto tryBlock = std::find((*catchBlock)->trys.begin(), (*catchBlock)->trys.end(), this);
241             if (tryBlock != (*catchBlock)->trys.end()) {
242                 (*catchBlock)->trys.erase(tryBlock);
243             }
244             if ((*catchBlock)->trys.size() == 0) {
245                 (*catchBlock)->isDead = true;
246             }
247         }
248         catchs.erase(catchs.begin() + index, catchs.end());
249     }
250 };
251 
252 using BytecodeGraph = std::vector<BytecodeRegion>;
253 
254 class BytecodeCircuitBuilder {
255 public:
BytecodeCircuitBuilder(const JSPandaFile * jsPandaFile,const MethodLiteral * methodLiteral,const MethodPcInfo & methodPCInfo,TSManager * tsManager,Circuit * circuit,Bytecodes * bytecodes,bool hasTypes,bool enableLog,bool enableTypeLowering,std::string name,const CString & recordName)256     explicit BytecodeCircuitBuilder(const JSPandaFile *jsPandaFile,
257                                     const MethodLiteral *methodLiteral,
258                                     const MethodPcInfo &methodPCInfo,
259                                     TSManager *tsManager,
260                                     Circuit *circuit,
261                                     Bytecodes *bytecodes,
262                                     bool hasTypes,
263                                     bool enableLog,
264                                     bool enableTypeLowering,
265                                     std::string name,
266                                     const CString &recordName)
267         : tsManager_(tsManager), circuit_(circuit), file_(jsPandaFile), pf_(jsPandaFile->GetPandaFile()),
268           method_(methodLiteral), gateAcc_(circuit), argAcc_(circuit, method_),
269           typeRecorder_(jsPandaFile, method_, tsManager, recordName), hasTypes_(hasTypes),
270           enableLog_(enableLog), enableTypeLowering_(enableTypeLowering),
271           pcOffsets_(methodPCInfo.pcOffsets),
272           frameStateBuilder_(this, circuit, methodLiteral), methodName_(name), recordName_(recordName),
273           bytecodes_(bytecodes)
274     {
275     }
276     ~BytecodeCircuitBuilder() = default;
277     NO_COPY_SEMANTIC(BytecodeCircuitBuilder);
278     NO_MOVE_SEMANTIC(BytecodeCircuitBuilder);
279     void PUBLIC_API BytecodeToCircuit();
280     int32_t GetJumpOffset(uint32_t bcIndex) const;
281     void CollectRegionInfo(uint32_t bcIndex);
282 
GetCircuit()283     [[nodiscard]] Circuit* GetCircuit() const
284     {
285         return circuit_;
286     }
287 
GetGateByBcIndex(uint32_t bcIndex)288     GateRef GetGateByBcIndex(uint32_t bcIndex) const
289     {
290         ASSERT(bcIndex < byteCodeToJSGate_.size());
291         return byteCodeToJSGate_[bcIndex];
292     }
293 
GetMethod()294     [[nodiscard]] const MethodLiteral* GetMethod() const
295     {
296         return method_;
297     }
298 
GetJSPandaFile()299     [[nodiscard]] const JSPandaFile* GetJSPandaFile() const
300     {
301         return file_;
302     }
303 
GetMethodName()304     const std::string& GetMethodName() const
305     {
306         return methodName_;
307     }
308 
IsLogEnabled()309     bool IsLogEnabled() const
310     {
311         return enableLog_;
312     }
313 
IsTypeLoweringEnabled()314     bool IsTypeLoweringEnabled() const
315     {
316         return enableTypeLowering_;
317     }
318 
GetAsyncRelatedGates()319     [[nodiscard]] const std::vector<GateRef>& GetAsyncRelatedGates() const
320     {
321         return suspendAndResumeGates_;
322     }
323 
HasTypes()324     inline bool HasTypes() const
325     {
326         return hasTypes_;
327     }
328 
329     template <class Callback>
EnumerateBlock(BytecodeRegion & bb,const Callback & cb)330     void EnumerateBlock(BytecodeRegion &bb, const Callback &cb)
331     {
332         auto &iterator = bb.GetBytecodeIterator();
333         for (iterator.GotoStart(); !iterator.Done(); ++iterator) {
334             auto &bytecodeInfo = iterator.GetBytecodeInfo();
335             bool ret = cb(bytecodeInfo);
336             if (!ret) {
337                 break;
338             }
339         }
340     }
341 
GetBasicBlockById(size_t id)342     BytecodeRegion &GetBasicBlockById(size_t id)
343     {
344         ASSERT(id < graph_.size());
345         return graph_[id];
346     }
347 
GetBasicBlockCount()348     size_t GetBasicBlockCount() const
349     {
350         return graph_.size();
351     }
352 
GetPcOffset(const uint8_t * pc)353     size_t GetPcOffset(const uint8_t *pc) const
354     {
355         return static_cast<size_t>(pc - method_->GetBytecodeArray());
356     }
357 
GetPcOffset(uint32_t bcIndex)358     size_t GetPcOffset(uint32_t bcIndex) const
359     {
360         const uint8_t* pc = GetPCByIndex(bcIndex);
361         return GetPcOffset(pc);
362     }
363 
GetNumberVRegs()364     size_t GetNumberVRegs() const
365     {
366         return static_cast<size_t>(method_->GetNumberVRegs());
367     }
368 
GetNumberVRegsWithEnv()369     size_t GetNumberVRegsWithEnv() const
370     {
371         return GetNumberVRegs() + 1; // 1: env variable
372     }
373 
GetEnvVregIdx()374     size_t GetEnvVregIdx() const
375     {
376         return GetNumberVRegs();
377     }
378 
GetBytecodes()379     Bytecodes *GetBytecodes() const
380     {
381         return bytecodes_;
382     }
383 
GetLastBcIndex()384     uint32_t GetLastBcIndex() const
385     {
386         return static_cast<uint32_t>(pcOffsets_.size() - 1);
387     }
388 
GetPCByIndex(uint32_t index)389     const uint8_t *GetPCByIndex(uint32_t index) const
390     {
391         ASSERT(index <= GetLastBcIndex());
392         return pcOffsets_[index];
393     }
394 
GetFirstPC()395     const uint8_t *GetFirstPC() const
396     {
397         return GetPCByIndex(0);
398     }
399 
GetLastPC()400     const uint8_t *GetLastPC() const
401     {
402         return GetPCByIndex(GetLastBcIndex());
403     }
404 
FindBcIndexByPc(const uint8_t * pc)405     uint32_t FindBcIndexByPc(const uint8_t *pc) const
406     {
407         auto begin = pcOffsets_.begin();
408         auto end = pcOffsets_.end();
409         auto it = std::lower_bound(begin, end, pc);
410         ASSERT(it != end);
411         ASSERT(*it == pc);
412         return std::distance(begin, it);
413     }
414 
GetBytecodeInfo(uint32_t index)415     const BytecodeInfo &GetBytecodeInfo(uint32_t index) const
416     {
417         return infoData_[index];
418     }
419 
HasTryCatch()420     bool HasTryCatch() const
421     {
422         return hasTryCatch_;
423     }
424 
425 private:
426     void CollectTryCatchBlockInfo(ExceptionInfo &Exception);
427     void BuildCatchBlocks(const ExceptionInfo &Exception);
428     void BuildRegions(const ExceptionInfo &Exception);
429     void ComputeDominatorTree();
430     void BuildImmediateDominator(const std::vector<size_t> &immDom);
431     void ComputeDomFrontiers(const std::vector<size_t> &immDom);
432     void RemoveDeadRegions(const std::unordered_map<size_t, size_t> &bbIdToDfsTimestamp);
433     void InsertPhi();
434     void InsertExceptionPhi(std::unordered_map<uint16_t, std::set<size_t>> &defsitesInfo);
435     void UpdateCFG();
436     bool ShouldBeDead(BytecodeRegion &curBlock);
437     // build circuit
438     void BuildCircuitArgs();
439     void CollectPredsInfo();
440     void NewMerge(GateRef &state, GateRef &depend, size_t numOfIns);
441     void NewLoopBegin(BytecodeRegion &bb);
442     void BuildBlockCircuitHead();
443     std::vector<GateRef> CreateGateInList(const BytecodeInfo &info, const GateMetaData *meta);
444     void SetBlockPred(BytecodeRegion &bbNext, const GateRef &state, const GateRef &depend, bool isLoopBack);
445     GateRef NewConst(const BytecodeInfo &info);
446     void NewJSGate(BytecodeRegion &bb, GateRef &state, GateRef &depend);
447     void NewJump(BytecodeRegion &bb, GateRef &state, GateRef &depend);
448     void NewReturn(BytecodeRegion &bb,  GateRef &state, GateRef &depend);
449     void NewByteCode(BytecodeRegion &bb, GateRef &state, GateRef &depend);
450     void BuildSubCircuit();
451     void NewPhi(BytecodeRegion &bb, uint16_t reg, bool acc, GateRef &currentPhi);
452     GateRef ResolveDef(const size_t bbId, int32_t bcId, const uint16_t reg, const bool acc);
453     void BuildCircuit();
454     GateRef GetExistingRestore(GateRef resumeGate, uint16_t tmpReg) const;
455     void SetExistingRestore(GateRef resumeGate, uint16_t tmpReg, GateRef restoreGate);
456     void PrintGraph();
457     void PrintBBInfo();
458     void PrintGraph(const char* title);
459     void PrintBytecodeInfo(BytecodeRegion& region);
460     void PrintDefsitesInfo(const std::unordered_map<uint16_t, std::set<size_t>> &defsitesInfo);
461     void BuildRegionInfo();
462 
IsEntryBlock(const size_t bbId)463     inline bool IsEntryBlock(const size_t bbId) const
464     {
465         return bbId == 0;
466     }
467 
IsFirstBCEnvIn(const size_t bbId,const size_t bcIndex,const uint16_t reg)468     inline bool IsFirstBCEnvIn(const size_t bbId, const size_t bcIndex, const uint16_t reg) const
469     {
470         return (IsEntryBlock(bbId) && bcIndex == 0 && reg == GetNumberVRegs());
471     }
472 
473     TSManager *tsManager_;
474     Circuit *circuit_;
475     std::vector<GateRef> byteCodeToJSGate_;
476     BytecodeGraph graph_;
477     const JSPandaFile *file_ {nullptr};
478     const panda_file::File *pf_ {nullptr};
479     const MethodLiteral *method_ {nullptr};
480     GateAccessor gateAcc_;
481     ArgumentAccessor argAcc_;
482     TypeRecorder typeRecorder_;
483     bool hasTypes_ {false};
484     bool enableLog_ {false};
485     bool enableTypeLowering_ {false};
486     std::vector<GateRef> suspendAndResumeGates_ {};
487     std::vector<const uint8_t*> pcOffsets_;
488     std::map<std::pair<kungfu::GateRef, uint16_t>, kungfu::GateRef> resumeRegToRestore_ {};
489     FrameStateBuilder frameStateBuilder_;
490     std::string methodName_;
491     const CString &recordName_;
492     Bytecodes *bytecodes_;
493     RegionsInfo regionsInfo_{};
494     std::vector<BytecodeInfo> infoData_ {};
495     bool hasTryCatch_ {false};
496 };
497 }  // namespace panda::ecmascript::kungfu
498 #endif  // ECMASCRIPT_CLASS_LINKER_BYTECODE_CIRCUIT_IR_BUILDER_H
499