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 "common.h"
20 #include "code_ir.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