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 #include "slicer/control_flow_graph.h"
18
19 namespace lir {
20
Finish()21 std::vector<BasicBlock> BasicBlocksVisitor::Finish() {
22 // the .dex format specification has the following constraint:
23 //
24 // B17 The last reachable instruction of a method must either be a
25 // backwards goto or branch, a return, or a throw instruction. It must not
26 // be possible to leave the insns array at the bottom. 4.8.2.20
27 //
28 // NOTE: this is a very aggressive check though since in the LIR we also
29 // have labels, annotations, directives, etc. For example it's possible to have
30 // debug annotations (.line, .endlocal, ...) after the last bytecode.
31 //
32 SLICER_WEAK_CHECK(state_ == State::Outside);
33 SLICER_CHECK(state_ != State::BlockBody);
34 current_block_.region = {};
35 state_ = State::Outside;
36 return std::move(basic_blocks_);
37 }
38
Visit(Bytecode * bytecode)39 bool BasicBlocksVisitor::Visit(Bytecode* bytecode) {
40 switch (state_) {
41 case State::Outside:
42 StartBlock(bytecode);
43 state_ = State::BlockBody;
44 break;
45 case State::BlockHeader:
46 state_ = State::BlockBody;
47 break;
48 case State::BlockBody:
49 // inside basic block body, nothing to do.
50 break;
51 }
52
53 // terminate the current block?
54 bool terminate_block = false;
55 const auto flags = dex::GetFlagsFromOpcode(bytecode->opcode);
56 if (model_exceptions_) {
57 constexpr auto exit_instr_flags =
58 dex::kBranch |
59 dex::kSwitch |
60 dex::kThrow |
61 dex::kReturn;
62 terminate_block = (flags & exit_instr_flags) != 0;
63 } else {
64 constexpr auto exit_instr_flags =
65 dex::kBranch |
66 dex::kSwitch |
67 dex::kReturn;
68 terminate_block = bytecode->opcode == dex::OP_THROW || (flags & exit_instr_flags) != 0;
69 }
70 if (terminate_block) {
71 EndBlock(bytecode);
72 }
73
74 return true;
75 }
76
Visit(Label * label)77 bool BasicBlocksVisitor::Visit(Label* label) {
78 switch (state_) {
79 case State::Outside:
80 StartBlock(label);
81 break;
82 case State::BlockBody:
83 EndBlock(label->prev);
84 StartBlock(label);
85 break;
86 case State::BlockHeader:
87 break;
88 }
89 return true;
90 }
91
HandleAnnotation(Instruction * instr)92 bool BasicBlocksVisitor::HandleAnnotation(Instruction* instr) {
93 if (state_ == State::Outside) {
94 StartBlock(instr);
95 }
96 return true;
97 }
98
SkipInstruction(Instruction * instr)99 bool BasicBlocksVisitor::SkipInstruction(Instruction* instr) {
100 if (state_ != State::Outside) {
101 EndBlock(instr->prev);
102 }
103 return true;
104 }
105
StartBlock(Instruction * instr)106 void BasicBlocksVisitor::StartBlock(Instruction* instr) {
107 assert(instr != nullptr);
108 assert(state_ == State::Outside);
109 // mark the location of the "first" instruction,
110 // "last" will be set when we end the basic block.
111 current_block_.region.first = instr;
112 current_block_.region.last = nullptr;
113 state_ = State::BlockHeader;
114 }
115
EndBlock(Instruction * instr)116 void BasicBlocksVisitor::EndBlock(Instruction* instr) {
117 assert(instr != nullptr);
118 if (state_ == State::BlockBody) {
119 ++current_block_.id;
120 assert(current_block_.region.first != nullptr);
121 current_block_.region.last = instr;
122 basic_blocks_.push_back(current_block_);
123 } else {
124 assert(state_ == State::BlockHeader);
125 }
126 current_block_.region = {};
127 state_ = State::Outside;
128 }
129
CreateBasicBlocks(bool model_exceptions)130 void ControlFlowGraph::CreateBasicBlocks(bool model_exceptions) {
131 BasicBlocksVisitor visitor(model_exceptions);
132 for (auto instr : code_ir->instructions) {
133 instr->Accept(&visitor);
134 }
135 basic_blocks = visitor.Finish();
136 }
137
138 } // namespace lir
139