1 /** 2 * Copyright (c) 2025 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 ES2PANDA_COMPILER_CORE_CFG_H 17 #define ES2PANDA_COMPILER_CORE_CFG_H 18 19 #include "ir/astNode.h" 20 #include "ir/expressions/literals/booleanLiteral.h" 21 22 namespace ark::es2panda::public_lib { 23 struct Context; 24 } // namespace ark::es2panda::public_lib 25 26 namespace ark::es2panda::compiler { 27 using ENUMBITOPS_OPERATORS; 28 29 class CFG { 30 public: 31 enum class BasicBlockFlags : uint8_t { 32 NONE = 0, 33 ENTRY = 1U << 0U, 34 EXIT = 1U << 1U, 35 CONDITION = 1U << 2U, 36 LOOP = 1U << 3U 37 }; 38 class BasicBlock { 39 public: 40 std::pair<size_t, size_t> AddSuccessor(BasicBlock *successor); 41 std::pair<size_t, size_t> AddPredecessor(BasicBlock *predecessor); 42 43 [[nodiscard]] size_t GetIndex() const; 44 [[nodiscard]] BasicBlockFlags GetFlags() const; 45 46 bool HasFlag(BasicBlockFlags flag) const; 47 void SetFlag(BasicBlockFlags flag); 48 void ClearFlag(BasicBlockFlags flag); 49 50 [[nodiscard]] const ArenaVector<BasicBlock *> &GetSuccessors() const; 51 [[nodiscard]] const ArenaVector<BasicBlock *> &GetPredecessors() const; 52 [[nodiscard]] const ArenaVector<ir::AstNode *> &GetNodes() const; 53 [[nodiscard]] ir::AstNode *GetLastNode() const; 54 [[nodiscard]] size_t GetSize() const; 55 friend class CFG; 56 BasicBlock(ArenaAllocator *allocator, size_t index) noexcept; 57 58 private: 59 size_t AddNode(ir::AstNode *node); 60 size_t index_; 61 ArenaVector<ir::AstNode *> nodes_; 62 ArenaVector<BasicBlock *> succs_; 63 ArenaVector<BasicBlock *> preds_; 64 BasicBlockFlags flags_ {BasicBlockFlags::NONE}; 65 }; 66 67 struct VisitResult { 68 ArenaList<const CFG::BasicBlock *> &orderedList; 69 ArenaSet<const CFG::BasicBlock *> &visitedBlocks; 70 ArenaSet<const CFG::BasicBlock *> &markedBlocks; 71 }; 72 73 explicit CFG(ArenaAllocator *allocator); 74 75 BasicBlock *Build(ir::ScriptFunction *scriptFunctionNode); 76 void MergeEmptyBlocks(); 77 bool DumpDot(const char *filename) const; 78 79 using BBTraverser = std::function<bool(const BasicBlock *)>; 80 81 [[nodiscard]] const ArenaSet<BasicBlock *> &GetBasicBlocks() const; 82 // NOTE: We could make them faster by adding markers to the basic blocks. 83 void IterateForwardDepthFirst(const BBTraverser &traverser, const BasicBlock *start = nullptr, 84 bool allPath = false) const; 85 [[nodiscard]] ArenaList<const BasicBlock *> GetForwardDepthFirstOrder(const BasicBlock *start = nullptr, 86 bool allPath = false) const; 87 void IterateBackwardDepthFirst(const BBTraverser &traverser, const BasicBlock *start = nullptr, 88 bool allPath = false) const; 89 [[nodiscard]] ArenaList<const BasicBlock *> GetBackwardDepthFirstOrder(const BasicBlock *start = nullptr, 90 bool allPath = false) const; 91 void IterateForwardTopologicalOrder(const BBTraverser &traverser, const BasicBlock *start = nullptr, 92 bool closeLoop = false) const; 93 [[nodiscard]] ArenaList<const BasicBlock *> GetForwardTopologicalOrder(const BasicBlock *start = nullptr, 94 bool closeLoop = false) const; 95 void IterateBackwardTopologicalOrder(const BBTraverser &traverser, const BasicBlock *start = nullptr, 96 bool closeLoop = false) const; 97 98 [[nodiscard]] ArenaList<const BasicBlock *> GetBackwardTopologicalOrder(const BasicBlock *start = nullptr, 99 bool closeLoop = false) const; 100 101 [[nodiscard]] std::pair<BasicBlock *, size_t> FindBasicBlock(ir::AstNode *node) const; 102 [[nodiscard]] BasicBlock *FindEntryBasicBlock(ir::ScriptFunction *function) const; 103 [[nodiscard]] const ir::AstNode *GetBBPredEdgeLabel(const BasicBlock *bb, size_t index) const; 104 /* pair<condition, label> */ 105 [[nodiscard]] std::pair<ir::AstNode *, const ir::AstNode *> GetBBPredCondition(const BasicBlock *bb, 106 size_t index) const; 107 108 [[nodiscard]] const ir::AstNode *GetBBSuccEdgeLabel(const BasicBlock *bb, size_t index) const; 109 [[nodiscard]] ArenaAllocator *Allocator() const; 110 [[nodiscard]] const ArenaUnorderedMap<ir::ScriptFunction *, BasicBlock *> &GetFunctionEntries() const; 111 112 [[nodiscard]] const util::UString *GetAnnotation(const BasicBlock *bb) const; 113 114 [[nodiscard]] const ArenaUnorderedMap<ir::AstNode *, ir::AstNode *> &GetSwitchCaseMap() const; 115 116 private: 117 [[nodiscard]] BasicBlock *CreateNewBB(const std::vector<BasicBlock *> &&preds, 118 const std::vector<const ir::AstNode *> &&labels = {}); 119 120 BasicBlock *Build(ir::AstNode *node, BasicBlock *bb); 121 BasicBlock *Build(ir::ArrayExpression *arrayExpressionNode, BasicBlock *bb); 122 BasicBlock *Build(ir::ArrowFunctionExpression *arrowFunctionExpressionNode, BasicBlock *bb); 123 BasicBlock *Build(ir::AssignmentExpression *assignmentExpressionNode, BasicBlock *bb); 124 BasicBlock *Build(ir::BinaryExpression *binaryExpressionNode, BasicBlock *bb); 125 BasicBlock *Build(ir::BlockExpression *blockExpressionNode, BasicBlock *bb); 126 BasicBlock *Build(ir::BlockStatement *blockStatementNode, BasicBlock *bb); 127 BasicBlock *Build(ir::BreakStatement *breakStatementNode, BasicBlock *bb); 128 BasicBlock *Build(ir::CallExpression *callExpressionNode, BasicBlock *bb); 129 BasicBlock *Build(ir::CatchClause *catchClauseNode, BasicBlock *bb); 130 BasicBlock *Build(ir::ChainExpression *chainExpressionNode, BasicBlock *bb); 131 BasicBlock *Build(ir::ConditionalExpression *conditionalExpressionNode, BasicBlock *bb); 132 BasicBlock *Build(ir::ContinueStatement *continueStatementNode, BasicBlock *bb); 133 BasicBlock *Build(ir::DoWhileStatement *doWhileStatementNode, BasicBlock *bb); 134 BasicBlock *Build(ir::ExpressionStatement *expressionStatementNode, BasicBlock *bb); 135 BasicBlock *Build(ir::ETSNewClassInstanceExpression *etsNewClassInstanceExpressionNode, BasicBlock *bb); 136 BasicBlock *Build(ir::ForOfStatement *forOfStatementNode, BasicBlock *bb); 137 BasicBlock *Build(ir::ForUpdateStatement *forUpdateStatementNode, BasicBlock *bb); 138 BasicBlock *Build(ir::IfStatement *ifStatementNode, BasicBlock *bb); 139 BasicBlock *Build(ir::LabelledStatement *labelledStatementNode, BasicBlock *bb); 140 BasicBlock *Build(ir::MemberExpression *memberExpressionNode, BasicBlock *bb); 141 BasicBlock *Build(ir::ReturnStatement *returnStatementNode, BasicBlock *bb); 142 BasicBlock *Build(ir::SwitchStatement *switchStatementNode, BasicBlock *bb); 143 BasicBlock *Build(ir::ThrowStatement *throwStatementNode, BasicBlock *bb); 144 BasicBlock *Build(ir::TryStatement *tryStatementNode, BasicBlock *bb); 145 BasicBlock *Build(ir::TSAsExpression *asExpressionNode, BasicBlock *bb); 146 BasicBlock *Build(ir::TSNonNullExpression *tsNonNullExpressionNode, BasicBlock *bb); 147 BasicBlock *Build(ir::TypeofExpression *typeofExpressionNode, BasicBlock *bb); 148 BasicBlock *Build(ir::UnaryExpression *unaryExpressionNode, BasicBlock *bb); 149 BasicBlock *Build(ir::UpdateExpression *updateExpressionNode, BasicBlock *bb); 150 BasicBlock *Build(ir::VariableDeclaration *variableDeclarationNode, BasicBlock *bb); 151 BasicBlock *Build(ir::WhileStatement *whileStatementNode, BasicBlock *bb); 152 153 size_t AddNodeToBB(ir::AstNode *node, BasicBlock *bb); 154 155 void AddBBEdge(BasicBlock *from, BasicBlock *to, const ir::AstNode *label = nullptr); 156 void SetBBPredEdgeLabel(const BasicBlock *bb, size_t index, const ir::AstNode *label); 157 void SetBBSuccEdgeLabel(const BasicBlock *bb, size_t index, const ir::AstNode *label); 158 159 bool VisitDepthFirst(const CFG::BBTraverser &traverser, const CFG::BasicBlock *bb, 160 ArenaSet<const CFG::BasicBlock *> &visitedBlocks, 161 ArenaVector<BasicBlock *> CFG::BasicBlock::*edges, bool allPath) const; 162 163 void VisitTopOrder(VisitResult &visitResult, const CFG::BasicBlock *bb, 164 ArenaVector<BasicBlock *> CFG::BasicBlock::*edges, bool closeLoop) const; 165 166 void DumpSuccessorEdges(std::ofstream &ofs, BasicBlock *const bb) const; 167 void DumpPredecessorEdges(std::ofstream &ofs, BasicBlock *const bb) const; 168 void RedirectEmptyBBEdges(CFG::BasicBlock *bb) const; 169 170 BasicBlock *BuildExpressions(ir::AstNode *node, CFG::BasicBlock *bb); 171 BasicBlock *BuildETSExpressions(ir::AstNode *node, CFG::BasicBlock *bb); 172 BasicBlock *BuildStatements(ir::AstNode *node, CFG::BasicBlock *bb); 173 174 private: 175 size_t basicBlockIdx_ {0}; 176 ArenaAllocator *allocator_; 177 ArenaSet<BasicBlock *> blocks_; 178 ArenaUnorderedMap<ir::AstNode *, std::pair<BasicBlock *, size_t>> nodeBBMap_; 179 ArenaUnorderedMap<ir::ScriptFunction *, BasicBlock *> functionNodeBBMap_; 180 ArenaUnorderedMap<const BasicBlock *, util::UString> bbAnnotationMap_; 181 ArenaUnorderedMap<ir::AstNode *, ir::AstNode *> switchCaseMap_; 182 ArenaDoubleUnorderedMap<const BasicBlock *, size_t, const ir::AstNode *> bbSuccLabelMap_; 183 ArenaDoubleUnorderedMap<const BasicBlock *, size_t, const ir::AstNode *> bbPredLabelMap_; 184 /* Pair of <Continue target, Break target> */ 185 ArenaUnorderedMap<const ir::AstNode *, std::pair<BasicBlock *, BasicBlock *>> loopStmtJumpTargetMap_; 186 size_t inLoop_ {0}; 187 const ir::BooleanLiteral trueLabel_; 188 const ir::BooleanLiteral falseLabel_; 189 }; 190 191 } // namespace ark::es2panda::compiler 192 193 namespace enumbitops { 194 195 template <> 196 struct IsAllowedType<ark::es2panda::compiler::CFG::BasicBlockFlags> : std::true_type { 197 }; 198 199 } // namespace enumbitops 200 201 #endif 202