1 /* 2 * Copyright (C) 2017 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 #pragma once 18 19 #include "code_ir.h" 20 #include "common.h" 21 22 #include <vector> 23 24 namespace lir { 25 26 // Represents a contiguous code "region" 27 struct Region { 28 Instruction* first = nullptr; 29 Instruction* last = nullptr; 30 }; 31 32 struct BasicBlock { 33 int id = 0; // real basic blocks have id > 0 34 Region region; 35 }; 36 37 // LIR visitor used to build the list of basic blocks 38 class BasicBlocksVisitor : public Visitor { 39 enum class State { Outside, BlockHeader, BlockBody }; 40 41 public: BasicBlocksVisitor(bool model_exceptions)42 explicit BasicBlocksVisitor(bool model_exceptions) : model_exceptions_(model_exceptions) { 43 current_block_.id = 0; 44 } 45 ~BasicBlocksVisitor()46 ~BasicBlocksVisitor() { 47 assert(state_ == State::Outside); 48 } 49 50 // Used to mark the end of instruction stream 51 // Returns the list of basic blocks 52 std::vector<BasicBlock> Finish(); 53 54 private: 55 bool Visit(Bytecode* bytecode) override; 56 bool Visit(Label* label) override; 57 58 // Debug info annotations Visit(DbgInfoHeader * dbg_header)59 bool Visit(DbgInfoHeader* dbg_header) override { return HandleAnnotation(dbg_header); } Visit(DbgInfoAnnotation * dbg_annotation)60 bool Visit(DbgInfoAnnotation* dbg_annotation) override { return HandleAnnotation(dbg_annotation); } 61 62 // EH annotations Visit(TryBlockBegin * try_begin)63 bool Visit(TryBlockBegin* try_begin) override { return SkipInstruction(try_begin); } Visit(TryBlockEnd * try_end)64 bool Visit(TryBlockEnd* try_end) override { return SkipInstruction(try_end); } 65 66 // data payload Visit(PackedSwitchPayload * packed_switch)67 bool Visit(PackedSwitchPayload* packed_switch) override { return SkipInstruction(packed_switch); } Visit(SparseSwitchPayload * sparse_switch)68 bool Visit(SparseSwitchPayload* sparse_switch) override { return SkipInstruction(sparse_switch); } Visit(ArrayData * array_data)69 bool Visit(ArrayData* array_data) override { return SkipInstruction(array_data); } 70 71 bool HandleAnnotation(Instruction* instr); 72 bool SkipInstruction(Instruction* instr); 73 74 // Starts a new basic block starting with the specified instruction 75 void StartBlock(Instruction* instr); 76 77 // Ends the current basic block at the specified instruction 78 void EndBlock(Instruction* instr); 79 80 private: 81 State state_ = State::Outside; 82 BasicBlock current_block_; 83 std::vector<BasicBlock> basic_blocks_; 84 const bool model_exceptions_; 85 }; 86 87 // The Control Flow Graph (CFG) for the specified method LIR 88 struct ControlFlowGraph { 89 // The list of basic blocks, as non-overlapping regions, 90 // sorted by the byte offset of the region start 91 std::vector<BasicBlock> basic_blocks; 92 93 const CodeIr* code_ir; 94 95 public: ControlFlowGraphControlFlowGraph96 ControlFlowGraph(const CodeIr* code_ir, bool model_exceptions) : code_ir(code_ir) { 97 CreateBasicBlocks(model_exceptions); 98 } 99 100 private: 101 void CreateBasicBlocks(bool model_exceptions); 102 }; 103 104 } // namespace lir 105