1 /* 2 * Copyright (C) 2023 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 #ifndef BERBERIS_BACKEND_X86_64_MACHINE_IR_ANALYSIS_H_ 18 #define BERBERIS_BACKEND_X86_64_MACHINE_IR_ANALYSIS_H_ 19 20 #include "berberis/backend/x86_64/machine_ir.h" 21 #include "berberis/base/arena_alloc.h" 22 #include "berberis/base/arena_vector.h" 23 #include "berberis/base/logging.h" 24 25 namespace berberis::x86_64 { 26 27 using Loop = ArenaVector<MachineBasicBlock*>; 28 using LoopVector = ArenaVector<Loop*>; 29 30 class LoopTreeNode { 31 public: loop_(loop)32 LoopTreeNode(MachineIR* ir, Loop* loop = nullptr) : loop_(loop), innerloop_nodes_(ir->arena()) {} 33 loop()34 Loop* loop() const { return loop_; } NumInnerloops()35 size_t NumInnerloops() const { return innerloop_nodes_.size(); }; GetInnerloopNode(size_t i)36 LoopTreeNode* GetInnerloopNode(size_t i) const { return innerloop_nodes_.at(i); } 37 AddInnerloopNode(LoopTreeNode * node)38 void AddInnerloopNode(LoopTreeNode* node) { innerloop_nodes_.push_back(node); } 39 40 private: 41 Loop* loop_; // null if the node is the root of the tree. 42 ArenaVector<LoopTreeNode*> innerloop_nodes_; 43 }; 44 45 class LoopTree { 46 public: LoopTree(MachineIR * ir)47 LoopTree(MachineIR* ir) : ir_(ir), root_(NewInArena<LoopTreeNode>(ir->arena(), ir)) {} 48 root()49 LoopTreeNode* root() const { return root_; } 50 51 // This function requires that loops are inserted in the order of 52 // non-increasing loop size, because the function assumes the loop in which 53 // the current loop is nested in is already inserted. InsertLoop(Loop * loop)54 void InsertLoop(Loop* loop) { 55 bool success = TryInsertLoopAtNode(root(), loop); 56 CHECK(success); 57 } 58 59 private: 60 bool TryInsertLoopAtNode(LoopTreeNode* node, Loop* loop); 61 62 MachineIR* ir_; 63 LoopTreeNode* root_; 64 }; 65 66 LoopVector FindLoops(MachineIR* ir); 67 LoopTree BuildLoopTree(MachineIR* ir); 68 69 MachineBasicBlockList GetReversePostOrderBBList(MachineIR* ir); 70 71 } // namespace berberis::x86_64 72 73 #endif // BERBERIS_BACKEND_X86_64_MACHINE_IR_ANALYSIS_H_ 74