blob: 7098eb86a57746f2081d3f75d8330431f98104f1 [file] [log] [blame]
Nicolas Geoffray818f2102014-02-18 16:43:35 +00001/*
2 * Copyright (C) 2014 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 ART_COMPILER_OPTIMIZING_BUILDER_H_
18#define ART_COMPILER_OPTIMIZING_BUILDER_H_
19
Mathieu Chartierb666f482015-02-18 14:33:14 -080020#include "base/arena_object.h"
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +000021#include "dex_file.h"
Nicolas Geoffray7fb49da2014-10-06 09:12:41 +010022#include "dex_file-inl.h"
Nicolas Geoffraye5038322014-07-04 09:41:32 +010023#include "driver/compiler_driver.h"
Nicolas Geoffray8ccc3f52014-03-19 10:34:11 +000024#include "driver/dex_compilation_unit.h"
Calin Juravle48c2b032014-12-09 18:11:36 +000025#include "optimizing_compiler_stats.h"
Nicolas Geoffray01bc96d2014-04-11 17:43:50 +010026#include "primitive.h"
Nicolas Geoffraybe9a92a2014-02-25 14:22:56 +000027#include "utils/growable_array.h"
Dave Allison20dfc792014-06-16 20:44:29 -070028#include "nodes.h"
Nicolas Geoffray818f2102014-02-18 16:43:35 +000029
30namespace art {
31
Nicolas Geoffray818f2102014-02-18 16:43:35 +000032class Instruction;
Andreas Gampee4d4d322014-12-04 09:09:57 -080033class SwitchTable;
Nicolas Geoffray818f2102014-02-18 16:43:35 +000034
35class HGraphBuilder : public ValueObject {
36 public:
David Brazdil5e8b1372015-01-23 14:39:08 +000037 HGraphBuilder(HGraph* graph,
Nicolas Geoffray7fb49da2014-10-06 09:12:41 +010038 DexCompilationUnit* dex_compilation_unit,
Nicolas Geoffraye53798a2014-12-01 10:31:54 +000039 const DexCompilationUnit* const outer_compilation_unit,
Nicolas Geoffray7fb49da2014-10-06 09:12:41 +010040 const DexFile* dex_file,
Calin Juravle48c2b032014-12-09 18:11:36 +000041 CompilerDriver* driver,
42 OptimizingCompilerStats* compiler_stats)
David Brazdil5e8b1372015-01-23 14:39:08 +000043 : arena_(graph->GetArena()),
44 branch_targets_(graph->GetArena(), 0),
45 locals_(graph->GetArena(), 0),
Nicolas Geoffray818f2102014-02-18 16:43:35 +000046 entry_block_(nullptr),
47 exit_block_(nullptr),
48 current_block_(nullptr),
David Brazdil5e8b1372015-01-23 14:39:08 +000049 graph_(graph),
Nicolas Geoffray8ccc3f52014-03-19 10:34:11 +000050 dex_file_(dex_file),
Nicolas Geoffraye5038322014-07-04 09:41:32 +010051 dex_compilation_unit_(dex_compilation_unit),
Nicolas Geoffray7fb49da2014-10-06 09:12:41 +010052 compiler_driver_(driver),
Nicolas Geoffraye53798a2014-12-01 10:31:54 +000053 outer_compilation_unit_(outer_compilation_unit),
Nicolas Geoffraya3d05a42014-10-20 17:41:32 +010054 return_type_(Primitive::GetType(dex_compilation_unit_->GetShorty()[0])),
55 code_start_(nullptr),
Calin Juravle48c2b032014-12-09 18:11:36 +000056 latest_result_(nullptr),
57 compilation_stats_(compiler_stats) {}
Nicolas Geoffray7fb49da2014-10-06 09:12:41 +010058
59 // Only for unit testing.
David Brazdil5e8b1372015-01-23 14:39:08 +000060 HGraphBuilder(HGraph* graph, Primitive::Type return_type = Primitive::kPrimInt)
61 : arena_(graph->GetArena()),
62 branch_targets_(graph->GetArena(), 0),
63 locals_(graph->GetArena(), 0),
Nicolas Geoffray7fb49da2014-10-06 09:12:41 +010064 entry_block_(nullptr),
65 exit_block_(nullptr),
66 current_block_(nullptr),
David Brazdil5e8b1372015-01-23 14:39:08 +000067 graph_(graph),
Nicolas Geoffray7fb49da2014-10-06 09:12:41 +010068 dex_file_(nullptr),
69 dex_compilation_unit_(nullptr),
70 compiler_driver_(nullptr),
Nicolas Geoffraye53798a2014-12-01 10:31:54 +000071 outer_compilation_unit_(nullptr),
Nicolas Geoffraya3d05a42014-10-20 17:41:32 +010072 return_type_(return_type),
73 code_start_(nullptr),
Calin Juravle48c2b032014-12-09 18:11:36 +000074 latest_result_(nullptr),
75 compilation_stats_(nullptr) {}
Nicolas Geoffray818f2102014-02-18 16:43:35 +000076
David Brazdil5e8b1372015-01-23 14:39:08 +000077 bool BuildGraph(const DexFile::CodeItem& code);
Nicolas Geoffray818f2102014-02-18 16:43:35 +000078
Andreas Gampe7c3952f2015-02-19 18:21:24 -080079 static constexpr const char* kBuilderPassName = "builder";
80
Nicolas Geoffray818f2102014-02-18 16:43:35 +000081 private:
82 // Analyzes the dex instruction and adds HInstruction to the graph
83 // to execute that instruction. Returns whether the instruction can
84 // be handled.
Calin Juravle225ff812014-11-13 16:46:39 +000085 bool AnalyzeDexInstruction(const Instruction& instruction, uint32_t dex_pc);
Nicolas Geoffraybe9a92a2014-02-25 14:22:56 +000086
87 // Finds all instructions that start a new block, and populates branch_targets_ with
88 // the newly created blocks.
Nicolas Geoffray43a539f2014-12-02 10:19:51 +000089 // As a side effect, also compute the number of dex instructions, blocks, and
90 // branches.
Calin Juravle702d2602015-04-30 19:28:21 +010091 // Returns true if all the branches fall inside the method code, false otherwise.
92 // (In normal cases this should always return true but someone can artificially
93 // create a code unit in which branches fall-through out of it).
94 bool ComputeBranchTargets(const uint16_t* start,
Nicolas Geoffray43a539f2014-12-02 10:19:51 +000095 const uint16_t* end,
Nicolas Geoffray43a539f2014-12-02 10:19:51 +000096 size_t* number_of_branches);
David Brazdilfc6a86a2015-06-26 10:33:45 +000097 void MaybeUpdateCurrentBlock(size_t dex_pc);
98 HBasicBlock* FindBlockStartingAt(int32_t dex_pc) const;
99 HBasicBlock* FindOrCreateBlockStartingAt(int32_t dex_pc);
David Brazdil56e1acc2015-06-30 15:41:36 +0100100
David Brazdil49bace12015-07-01 15:28:26 +0100101 // Adds new blocks to `branch_targets_` starting at the limits of TryItems and
102 // their exception handlers.
David Brazdilfc6a86a2015-06-26 10:33:45 +0000103 void CreateBlocksForTryCatch(const DexFile::CodeItem& code_item);
David Brazdil49bace12015-07-01 15:28:26 +0100104
105 // Splits edges which cross the boundaries of TryItems, inserts TryBoundary
106 // instructions and links them to the corresponding catch blocks.
David Brazdilfc6a86a2015-06-26 10:33:45 +0000107 void InsertTryBoundaryBlocks(const DexFile::CodeItem& code_item);
David Brazdil49bace12015-07-01 15:28:26 +0100108
109 // Splits a single edge, inserting a TryBoundary of given `kind` and linking
110 // it to exception handlers of `try_item`.
David Brazdil56e1acc2015-06-30 15:41:36 +0100111 void SplitTryBoundaryEdge(HBasicBlock* predecessor,
112 HBasicBlock* successor,
113 HTryBoundary::BoundaryKind kind,
114 const DexFile::CodeItem& code_item,
115 const DexFile::TryItem& try_item);
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000116
Nicolas Geoffrayf583e592014-04-07 13:20:42 +0100117 void InitializeLocals(uint16_t count);
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +0000118 HLocal* GetLocalAt(int register_index) const;
119 void UpdateLocal(int register_index, HInstruction* instruction) const;
Nicolas Geoffray01bc96d2014-04-11 17:43:50 +0100120 HInstruction* LoadLocal(int register_index, Primitive::Type type) const;
David Brazdil852eaff2015-02-02 15:23:05 +0000121 void PotentiallyAddSuspendCheck(HBasicBlock* target, uint32_t dex_pc);
Nicolas Geoffray52e832b2014-11-06 15:15:31 +0000122 void InitializeParameters(uint16_t number_of_parameters);
Nicolas Geoffraycb1b00a2015-01-28 14:50:01 +0000123 bool NeedsAccessCheck(uint32_t type_index) const;
Nicolas Geoffrayf583e592014-04-07 13:20:42 +0100124
Nicolas Geoffray01bc96d2014-04-11 17:43:50 +0100125 template<typename T>
Roland Levillain88cb1752014-10-20 16:36:47 +0100126 void Unop_12x(const Instruction& instruction, Primitive::Type type);
127
128 template<typename T>
Nicolas Geoffray412f10c2014-06-19 10:00:34 +0100129 void Binop_23x(const Instruction& instruction, Primitive::Type type);
Nicolas Geoffray01bc96d2014-04-11 17:43:50 +0100130
131 template<typename T>
Calin Juravled6fb6cf2014-11-11 19:07:44 +0000132 void Binop_23x(const Instruction& instruction, Primitive::Type type, uint32_t dex_pc);
133
134 template<typename T>
Calin Juravle9aec02f2014-11-18 23:06:35 +0000135 void Binop_23x_shift(const Instruction& instruction, Primitive::Type type);
136
Alexey Frunze4dda3372015-06-01 18:31:49 -0700137 void Binop_23x_cmp(const Instruction& instruction,
138 Primitive::Type type,
Mark Mendellc4701932015-04-10 13:18:51 -0400139 ComparisonBias bias,
Alexey Frunze4dda3372015-06-01 18:31:49 -0700140 uint32_t dex_pc);
Calin Juravleddb7df22014-11-25 20:56:51 +0000141
Calin Juravle9aec02f2014-11-18 23:06:35 +0000142 template<typename T>
Nicolas Geoffray01bc96d2014-04-11 17:43:50 +0100143 void Binop_12x(const Instruction& instruction, Primitive::Type type);
144
145 template<typename T>
Calin Juravled6fb6cf2014-11-11 19:07:44 +0000146 void Binop_12x(const Instruction& instruction, Primitive::Type type, uint32_t dex_pc);
147
148 template<typename T>
Calin Juravle9aec02f2014-11-18 23:06:35 +0000149 void Binop_12x_shift(const Instruction& instruction, Primitive::Type type);
150
151 template<typename T>
Nicolas Geoffray01bc96d2014-04-11 17:43:50 +0100152 void Binop_22b(const Instruction& instruction, bool reverse);
153
154 template<typename T>
155 void Binop_22s(const Instruction& instruction, bool reverse);
156
Calin Juravle225ff812014-11-13 16:46:39 +0000157 template<typename T> void If_21t(const Instruction& instruction, uint32_t dex_pc);
158 template<typename T> void If_22t(const Instruction& instruction, uint32_t dex_pc);
Nicolas Geoffrayf583e592014-04-07 13:20:42 +0100159
Roland Levillaindff1f282014-11-05 14:15:05 +0000160 void Conversion_12x(const Instruction& instruction,
161 Primitive::Type input_type,
Roland Levillain624279f2014-12-04 11:54:28 +0000162 Primitive::Type result_type,
163 uint32_t dex_pc);
Roland Levillaindff1f282014-11-05 14:15:05 +0000164
Calin Juravlebacfec32014-11-14 15:54:36 +0000165 void BuildCheckedDivRem(uint16_t out_reg,
166 uint16_t first_reg,
167 int64_t second_reg_or_constant,
168 uint32_t dex_pc,
169 Primitive::Type type,
170 bool second_is_lit,
171 bool is_div);
Calin Juravled0d48522014-11-04 16:40:20 +0000172
Nicolas Geoffray01bc96d2014-04-11 17:43:50 +0100173 void BuildReturn(const Instruction& instruction, Primitive::Type type);
174
Nicolas Geoffray19a19cf2014-10-22 16:07:05 +0100175 // Builds an instance field access node and returns whether the instruction is supported.
Calin Juravle225ff812014-11-13 16:46:39 +0000176 bool BuildInstanceFieldAccess(const Instruction& instruction, uint32_t dex_pc, bool is_put);
Nicolas Geoffray19a19cf2014-10-22 16:07:05 +0100177
178 // Builds a static field access node and returns whether the instruction is supported.
Calin Juravle225ff812014-11-13 16:46:39 +0000179 bool BuildStaticFieldAccess(const Instruction& instruction, uint32_t dex_pc, bool is_put);
Nicolas Geoffray19a19cf2014-10-22 16:07:05 +0100180
Nicolas Geoffray3c7bb982014-07-23 16:04:16 +0100181 void BuildArrayAccess(const Instruction& instruction,
Calin Juravle225ff812014-11-13 16:46:39 +0000182 uint32_t dex_pc,
Nicolas Geoffray3c7bb982014-07-23 16:04:16 +0100183 bool is_get,
184 Primitive::Type anticipated_type);
Nicolas Geoffraye5038322014-07-04 09:41:32 +0100185
Nicolas Geoffray01bc96d2014-04-11 17:43:50 +0100186 // Builds an invocation node and returns whether the instruction is supported.
187 bool BuildInvoke(const Instruction& instruction,
Calin Juravle225ff812014-11-13 16:46:39 +0000188 uint32_t dex_pc,
Nicolas Geoffray01bc96d2014-04-11 17:43:50 +0100189 uint32_t method_idx,
190 uint32_t number_of_vreg_arguments,
191 bool is_range,
192 uint32_t* args,
193 uint32_t register_index);
194
Nicolas Geoffraya3d05a42014-10-20 17:41:32 +0100195 // Builds a new array node and the instructions that fill it.
Calin Juravle225ff812014-11-13 16:46:39 +0000196 void BuildFilledNewArray(uint32_t dex_pc,
Nicolas Geoffraya3d05a42014-10-20 17:41:32 +0100197 uint32_t type_index,
198 uint32_t number_of_vreg_arguments,
199 bool is_range,
200 uint32_t* args,
201 uint32_t register_index);
202
Calin Juravle225ff812014-11-13 16:46:39 +0000203 void BuildFillArrayData(const Instruction& instruction, uint32_t dex_pc);
Calin Juravled0d48522014-11-04 16:40:20 +0000204
Nicolas Geoffraya3d05a42014-10-20 17:41:32 +0100205 // Fills the given object with data as specified in the fill-array-data
206 // instruction. Currently only used for non-reference and non-floating point
207 // arrays.
208 template <typename T>
209 void BuildFillArrayData(HInstruction* object,
210 const T* data,
211 uint32_t element_count,
212 Primitive::Type anticipated_type,
Calin Juravle225ff812014-11-13 16:46:39 +0000213 uint32_t dex_pc);
Nicolas Geoffraya3d05a42014-10-20 17:41:32 +0100214
215 // Fills the given object with data as specified in the fill-array-data
216 // instruction. The data must be for long and double arrays.
217 void BuildFillWideArrayData(HInstruction* object,
Nicolas Geoffray8d6ae522014-10-23 18:32:13 +0100218 const int64_t* data,
Nicolas Geoffraya3d05a42014-10-20 17:41:32 +0100219 uint32_t element_count,
Calin Juravle225ff812014-11-13 16:46:39 +0000220 uint32_t dex_pc);
Nicolas Geoffraya3d05a42014-10-20 17:41:32 +0100221
Nicolas Geoffray57a88d42014-11-10 15:09:21 +0000222 // Builds a `HInstanceOf`, or a `HCheckCast` instruction.
223 // Returns whether we succeeded in building the instruction.
224 bool BuildTypeCheck(const Instruction& instruction,
225 uint8_t destination,
226 uint8_t reference,
227 uint16_t type_index,
Calin Juravle225ff812014-11-13 16:46:39 +0000228 uint32_t dex_pc);
Nicolas Geoffray57a88d42014-11-10 15:09:21 +0000229
Andreas Gampee4d4d322014-12-04 09:09:57 -0800230 // Builds an instruction sequence for a packed switch statement.
Calin Juravle48c2b032014-12-09 18:11:36 +0000231 void BuildPackedSwitch(const Instruction& instruction, uint32_t dex_pc);
Andreas Gamped881df52014-11-24 23:28:39 -0800232
Andreas Gampee4d4d322014-12-04 09:09:57 -0800233 // Builds an instruction sequence for a sparse switch statement.
Calin Juravle48c2b032014-12-09 18:11:36 +0000234 void BuildSparseSwitch(const Instruction& instruction, uint32_t dex_pc);
Andreas Gampee4d4d322014-12-04 09:09:57 -0800235
236 void BuildSwitchCaseHelper(const Instruction& instruction, size_t index,
237 bool is_last_case, const SwitchTable& table,
238 HInstruction* value, int32_t case_value_int,
239 int32_t target_offset, uint32_t dex_pc);
240
David Brazdil1b498722015-03-31 11:37:18 +0100241 bool SkipCompilation(const DexFile::CodeItem& code_item, size_t number_of_branches);
Calin Juravle48c2b032014-12-09 18:11:36 +0000242
243 void MaybeRecordStat(MethodCompilationStat compilation_stat);
244
Nicolas Geoffray30451742015-06-19 13:32:41 +0100245 // Returns the outer-most compiling method's class.
Nicolas Geoffray9437b782015-03-25 10:08:51 +0000246 mirror::Class* GetOutermostCompilingClass() const;
247
Nicolas Geoffray30451742015-06-19 13:32:41 +0100248 // Returns the class whose method is being compiled.
249 mirror::Class* GetCompilingClass() const;
250
Nicolas Geoffraye53798a2014-12-01 10:31:54 +0000251 // Returns whether `type_index` points to the outer-most compiling method's class.
Nicolas Geoffray9437b782015-03-25 10:08:51 +0000252 bool IsOutermostCompilingClass(uint16_t type_index) const;
Nicolas Geoffraye53798a2014-12-01 10:31:54 +0000253
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000254 ArenaAllocator* const arena_;
Nicolas Geoffraybe9a92a2014-02-25 14:22:56 +0000255
256 // A list of the size of the dex code holding block information for
257 // the method. If an entry contains a block, then the dex instruction
258 // starting at that entry is the first instruction of a new block.
259 GrowableArray<HBasicBlock*> branch_targets_;
260
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +0000261 GrowableArray<HLocal*> locals_;
262
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000263 HBasicBlock* entry_block_;
264 HBasicBlock* exit_block_;
265 HBasicBlock* current_block_;
David Brazdil5e8b1372015-01-23 14:39:08 +0000266 HGraph* const graph_;
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000267
Nicolas Geoffraye53798a2014-12-01 10:31:54 +0000268 // The dex file where the method being compiled is.
Nicolas Geoffray8ccc3f52014-03-19 10:34:11 +0000269 const DexFile* const dex_file_;
Nicolas Geoffraye53798a2014-12-01 10:31:54 +0000270
271 // The compilation unit of the current method being compiled. Note that
272 // it can be an inlined method.
Nicolas Geoffray01bc96d2014-04-11 17:43:50 +0100273 DexCompilationUnit* const dex_compilation_unit_;
Nicolas Geoffraye53798a2014-12-01 10:31:54 +0000274
Nicolas Geoffraye5038322014-07-04 09:41:32 +0100275 CompilerDriver* const compiler_driver_;
Nicolas Geoffraye53798a2014-12-01 10:31:54 +0000276
277 // The compilation unit of the outermost method being compiled. That is the
278 // method being compiled (and not inlined), and potentially inlining other
279 // methods.
280 const DexCompilationUnit* const outer_compilation_unit_;
281
282 // The return type of the method being compiled.
Nicolas Geoffray7fb49da2014-10-06 09:12:41 +0100283 const Primitive::Type return_type_;
Nicolas Geoffray8ccc3f52014-03-19 10:34:11 +0000284
Nicolas Geoffraya3d05a42014-10-20 17:41:32 +0100285 // The pointer in the dex file where the instructions of the code item
286 // being currently compiled start.
287 const uint16_t* code_start_;
288
289 // The last invoke or fill-new-array being built. Only to be
290 // used by move-result instructions.
291 HInstruction* latest_result_;
292
Calin Juravle48c2b032014-12-09 18:11:36 +0000293 OptimizingCompilerStats* compilation_stats_;
294
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000295 DISALLOW_COPY_AND_ASSIGN(HGraphBuilder);
296};
297
298} // namespace art
299
300#endif // ART_COMPILER_OPTIMIZING_BUILDER_H_