blob: 76610f5be2af189ddda98f6cfac055b30f4bc8b8 [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),
Nicolas Geoffray2e7cd752015-07-10 11:38:52 +010057 can_use_baseline_for_string_init_(true),
Calin Juravle48c2b032014-12-09 18:11:36 +000058 compilation_stats_(compiler_stats) {}
Nicolas Geoffray7fb49da2014-10-06 09:12:41 +010059
60 // Only for unit testing.
David Brazdil5e8b1372015-01-23 14:39:08 +000061 HGraphBuilder(HGraph* graph, Primitive::Type return_type = Primitive::kPrimInt)
62 : arena_(graph->GetArena()),
63 branch_targets_(graph->GetArena(), 0),
64 locals_(graph->GetArena(), 0),
Nicolas Geoffray7fb49da2014-10-06 09:12:41 +010065 entry_block_(nullptr),
66 exit_block_(nullptr),
67 current_block_(nullptr),
David Brazdil5e8b1372015-01-23 14:39:08 +000068 graph_(graph),
Nicolas Geoffray7fb49da2014-10-06 09:12:41 +010069 dex_file_(nullptr),
70 dex_compilation_unit_(nullptr),
71 compiler_driver_(nullptr),
Nicolas Geoffraye53798a2014-12-01 10:31:54 +000072 outer_compilation_unit_(nullptr),
Nicolas Geoffraya3d05a42014-10-20 17:41:32 +010073 return_type_(return_type),
74 code_start_(nullptr),
Calin Juravle48c2b032014-12-09 18:11:36 +000075 latest_result_(nullptr),
Nicolas Geoffray2e7cd752015-07-10 11:38:52 +010076 can_use_baseline_for_string_init_(true),
Calin Juravle48c2b032014-12-09 18:11:36 +000077 compilation_stats_(nullptr) {}
Nicolas Geoffray818f2102014-02-18 16:43:35 +000078
David Brazdil5e8b1372015-01-23 14:39:08 +000079 bool BuildGraph(const DexFile::CodeItem& code);
Nicolas Geoffray818f2102014-02-18 16:43:35 +000080
Nicolas Geoffray2e7cd752015-07-10 11:38:52 +010081 bool CanUseBaselineForStringInit() const {
82 return can_use_baseline_for_string_init_;
83 }
84
Andreas Gampe7c3952f2015-02-19 18:21:24 -080085 static constexpr const char* kBuilderPassName = "builder";
86
Nicolas Geoffray818f2102014-02-18 16:43:35 +000087 private:
88 // Analyzes the dex instruction and adds HInstruction to the graph
89 // to execute that instruction. Returns whether the instruction can
90 // be handled.
Calin Juravle225ff812014-11-13 16:46:39 +000091 bool AnalyzeDexInstruction(const Instruction& instruction, uint32_t dex_pc);
Nicolas Geoffraybe9a92a2014-02-25 14:22:56 +000092
93 // Finds all instructions that start a new block, and populates branch_targets_ with
94 // the newly created blocks.
Nicolas Geoffray43a539f2014-12-02 10:19:51 +000095 // As a side effect, also compute the number of dex instructions, blocks, and
96 // branches.
Calin Juravle702d2602015-04-30 19:28:21 +010097 // Returns true if all the branches fall inside the method code, false otherwise.
98 // (In normal cases this should always return true but someone can artificially
99 // create a code unit in which branches fall-through out of it).
100 bool ComputeBranchTargets(const uint16_t* start,
Nicolas Geoffray43a539f2014-12-02 10:19:51 +0000101 const uint16_t* end,
Nicolas Geoffray43a539f2014-12-02 10:19:51 +0000102 size_t* number_of_branches);
David Brazdilfc6a86a2015-06-26 10:33:45 +0000103 void MaybeUpdateCurrentBlock(size_t dex_pc);
104 HBasicBlock* FindBlockStartingAt(int32_t dex_pc) const;
105 HBasicBlock* FindOrCreateBlockStartingAt(int32_t dex_pc);
David Brazdil56e1acc2015-06-30 15:41:36 +0100106
David Brazdil49bace12015-07-01 15:28:26 +0100107 // Adds new blocks to `branch_targets_` starting at the limits of TryItems and
108 // their exception handlers.
David Brazdilfc6a86a2015-06-26 10:33:45 +0000109 void CreateBlocksForTryCatch(const DexFile::CodeItem& code_item);
David Brazdil49bace12015-07-01 15:28:26 +0100110
111 // Splits edges which cross the boundaries of TryItems, inserts TryBoundary
112 // instructions and links them to the corresponding catch blocks.
David Brazdilfc6a86a2015-06-26 10:33:45 +0000113 void InsertTryBoundaryBlocks(const DexFile::CodeItem& code_item);
David Brazdil49bace12015-07-01 15:28:26 +0100114
115 // Splits a single edge, inserting a TryBoundary of given `kind` and linking
116 // it to exception handlers of `try_item`.
David Brazdil56e1acc2015-06-30 15:41:36 +0100117 void SplitTryBoundaryEdge(HBasicBlock* predecessor,
118 HBasicBlock* successor,
119 HTryBoundary::BoundaryKind kind,
120 const DexFile::CodeItem& code_item,
121 const DexFile::TryItem& try_item);
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000122
Nicolas Geoffrayf583e592014-04-07 13:20:42 +0100123 void InitializeLocals(uint16_t count);
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +0000124 HLocal* GetLocalAt(int register_index) const;
125 void UpdateLocal(int register_index, HInstruction* instruction) const;
Nicolas Geoffray01bc96d2014-04-11 17:43:50 +0100126 HInstruction* LoadLocal(int register_index, Primitive::Type type) const;
David Brazdil852eaff2015-02-02 15:23:05 +0000127 void PotentiallyAddSuspendCheck(HBasicBlock* target, uint32_t dex_pc);
Nicolas Geoffray52e832b2014-11-06 15:15:31 +0000128 void InitializeParameters(uint16_t number_of_parameters);
Nicolas Geoffraycb1b00a2015-01-28 14:50:01 +0000129 bool NeedsAccessCheck(uint32_t type_index) const;
Nicolas Geoffrayf583e592014-04-07 13:20:42 +0100130
Nicolas Geoffray01bc96d2014-04-11 17:43:50 +0100131 template<typename T>
Roland Levillain88cb1752014-10-20 16:36:47 +0100132 void Unop_12x(const Instruction& instruction, Primitive::Type type);
133
134 template<typename T>
Nicolas Geoffray412f10c2014-06-19 10:00:34 +0100135 void Binop_23x(const Instruction& instruction, Primitive::Type type);
Nicolas Geoffray01bc96d2014-04-11 17:43:50 +0100136
137 template<typename T>
Calin Juravled6fb6cf2014-11-11 19:07:44 +0000138 void Binop_23x(const Instruction& instruction, Primitive::Type type, uint32_t dex_pc);
139
140 template<typename T>
Calin Juravle9aec02f2014-11-18 23:06:35 +0000141 void Binop_23x_shift(const Instruction& instruction, Primitive::Type type);
142
Alexey Frunze4dda3372015-06-01 18:31:49 -0700143 void Binop_23x_cmp(const Instruction& instruction,
144 Primitive::Type type,
Mark Mendellc4701932015-04-10 13:18:51 -0400145 ComparisonBias bias,
Alexey Frunze4dda3372015-06-01 18:31:49 -0700146 uint32_t dex_pc);
Calin Juravleddb7df22014-11-25 20:56:51 +0000147
Calin Juravle9aec02f2014-11-18 23:06:35 +0000148 template<typename T>
Nicolas Geoffray01bc96d2014-04-11 17:43:50 +0100149 void Binop_12x(const Instruction& instruction, Primitive::Type type);
150
151 template<typename T>
Calin Juravled6fb6cf2014-11-11 19:07:44 +0000152 void Binop_12x(const Instruction& instruction, Primitive::Type type, uint32_t dex_pc);
153
154 template<typename T>
Calin Juravle9aec02f2014-11-18 23:06:35 +0000155 void Binop_12x_shift(const Instruction& instruction, Primitive::Type type);
156
157 template<typename T>
Nicolas Geoffray01bc96d2014-04-11 17:43:50 +0100158 void Binop_22b(const Instruction& instruction, bool reverse);
159
160 template<typename T>
161 void Binop_22s(const Instruction& instruction, bool reverse);
162
Calin Juravle225ff812014-11-13 16:46:39 +0000163 template<typename T> void If_21t(const Instruction& instruction, uint32_t dex_pc);
164 template<typename T> void If_22t(const Instruction& instruction, uint32_t dex_pc);
Nicolas Geoffrayf583e592014-04-07 13:20:42 +0100165
Roland Levillaindff1f282014-11-05 14:15:05 +0000166 void Conversion_12x(const Instruction& instruction,
167 Primitive::Type input_type,
Roland Levillain624279f2014-12-04 11:54:28 +0000168 Primitive::Type result_type,
169 uint32_t dex_pc);
Roland Levillaindff1f282014-11-05 14:15:05 +0000170
Calin Juravlebacfec32014-11-14 15:54:36 +0000171 void BuildCheckedDivRem(uint16_t out_reg,
172 uint16_t first_reg,
173 int64_t second_reg_or_constant,
174 uint32_t dex_pc,
175 Primitive::Type type,
176 bool second_is_lit,
177 bool is_div);
Calin Juravled0d48522014-11-04 16:40:20 +0000178
Nicolas Geoffray01bc96d2014-04-11 17:43:50 +0100179 void BuildReturn(const Instruction& instruction, Primitive::Type type);
180
Nicolas Geoffray19a19cf2014-10-22 16:07:05 +0100181 // Builds an instance field access node and returns whether the instruction is supported.
Calin Juravle225ff812014-11-13 16:46:39 +0000182 bool BuildInstanceFieldAccess(const Instruction& instruction, uint32_t dex_pc, bool is_put);
Nicolas Geoffray19a19cf2014-10-22 16:07:05 +0100183
184 // Builds a static field access node and returns whether the instruction is supported.
Calin Juravle225ff812014-11-13 16:46:39 +0000185 bool BuildStaticFieldAccess(const Instruction& instruction, uint32_t dex_pc, bool is_put);
Nicolas Geoffray19a19cf2014-10-22 16:07:05 +0100186
Nicolas Geoffray3c7bb982014-07-23 16:04:16 +0100187 void BuildArrayAccess(const Instruction& instruction,
Calin Juravle225ff812014-11-13 16:46:39 +0000188 uint32_t dex_pc,
Nicolas Geoffray3c7bb982014-07-23 16:04:16 +0100189 bool is_get,
190 Primitive::Type anticipated_type);
Nicolas Geoffraye5038322014-07-04 09:41:32 +0100191
Nicolas Geoffray01bc96d2014-04-11 17:43:50 +0100192 // Builds an invocation node and returns whether the instruction is supported.
193 bool BuildInvoke(const Instruction& instruction,
Calin Juravle225ff812014-11-13 16:46:39 +0000194 uint32_t dex_pc,
Nicolas Geoffray01bc96d2014-04-11 17:43:50 +0100195 uint32_t method_idx,
196 uint32_t number_of_vreg_arguments,
197 bool is_range,
198 uint32_t* args,
199 uint32_t register_index);
200
Nicolas Geoffraya3d05a42014-10-20 17:41:32 +0100201 // Builds a new array node and the instructions that fill it.
Calin Juravle225ff812014-11-13 16:46:39 +0000202 void BuildFilledNewArray(uint32_t dex_pc,
Nicolas Geoffraya3d05a42014-10-20 17:41:32 +0100203 uint32_t type_index,
204 uint32_t number_of_vreg_arguments,
205 bool is_range,
206 uint32_t* args,
207 uint32_t register_index);
208
Calin Juravle225ff812014-11-13 16:46:39 +0000209 void BuildFillArrayData(const Instruction& instruction, uint32_t dex_pc);
Calin Juravled0d48522014-11-04 16:40:20 +0000210
Nicolas Geoffraya3d05a42014-10-20 17:41:32 +0100211 // Fills the given object with data as specified in the fill-array-data
212 // instruction. Currently only used for non-reference and non-floating point
213 // arrays.
214 template <typename T>
215 void BuildFillArrayData(HInstruction* object,
216 const T* data,
217 uint32_t element_count,
218 Primitive::Type anticipated_type,
Calin Juravle225ff812014-11-13 16:46:39 +0000219 uint32_t dex_pc);
Nicolas Geoffraya3d05a42014-10-20 17:41:32 +0100220
221 // Fills the given object with data as specified in the fill-array-data
222 // instruction. The data must be for long and double arrays.
223 void BuildFillWideArrayData(HInstruction* object,
Nicolas Geoffray8d6ae522014-10-23 18:32:13 +0100224 const int64_t* data,
Nicolas Geoffraya3d05a42014-10-20 17:41:32 +0100225 uint32_t element_count,
Calin Juravle225ff812014-11-13 16:46:39 +0000226 uint32_t dex_pc);
Nicolas Geoffraya3d05a42014-10-20 17:41:32 +0100227
Nicolas Geoffray57a88d42014-11-10 15:09:21 +0000228 // Builds a `HInstanceOf`, or a `HCheckCast` instruction.
229 // Returns whether we succeeded in building the instruction.
230 bool BuildTypeCheck(const Instruction& instruction,
231 uint8_t destination,
232 uint8_t reference,
233 uint16_t type_index,
Calin Juravle225ff812014-11-13 16:46:39 +0000234 uint32_t dex_pc);
Nicolas Geoffray57a88d42014-11-10 15:09:21 +0000235
Andreas Gampee4d4d322014-12-04 09:09:57 -0800236 // Builds an instruction sequence for a packed switch statement.
Calin Juravle48c2b032014-12-09 18:11:36 +0000237 void BuildPackedSwitch(const Instruction& instruction, uint32_t dex_pc);
Andreas Gamped881df52014-11-24 23:28:39 -0800238
Andreas Gampee4d4d322014-12-04 09:09:57 -0800239 // Builds an instruction sequence for a sparse switch statement.
Calin Juravle48c2b032014-12-09 18:11:36 +0000240 void BuildSparseSwitch(const Instruction& instruction, uint32_t dex_pc);
Andreas Gampee4d4d322014-12-04 09:09:57 -0800241
242 void BuildSwitchCaseHelper(const Instruction& instruction, size_t index,
243 bool is_last_case, const SwitchTable& table,
244 HInstruction* value, int32_t case_value_int,
245 int32_t target_offset, uint32_t dex_pc);
246
David Brazdil1b498722015-03-31 11:37:18 +0100247 bool SkipCompilation(const DexFile::CodeItem& code_item, size_t number_of_branches);
Calin Juravle48c2b032014-12-09 18:11:36 +0000248
249 void MaybeRecordStat(MethodCompilationStat compilation_stat);
250
Nicolas Geoffray30451742015-06-19 13:32:41 +0100251 // Returns the outer-most compiling method's class.
Nicolas Geoffray9437b782015-03-25 10:08:51 +0000252 mirror::Class* GetOutermostCompilingClass() const;
253
Nicolas Geoffray30451742015-06-19 13:32:41 +0100254 // Returns the class whose method is being compiled.
255 mirror::Class* GetCompilingClass() const;
256
Nicolas Geoffraye53798a2014-12-01 10:31:54 +0000257 // Returns whether `type_index` points to the outer-most compiling method's class.
Nicolas Geoffray9437b782015-03-25 10:08:51 +0000258 bool IsOutermostCompilingClass(uint16_t type_index) const;
Nicolas Geoffraye53798a2014-12-01 10:31:54 +0000259
Nicolas Geoffray2e7cd752015-07-10 11:38:52 +0100260 void PotentiallySimplifyFakeString(uint16_t original_dex_register,
261 uint32_t dex_pc,
262 HInvoke* invoke);
263
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000264 ArenaAllocator* const arena_;
Nicolas Geoffraybe9a92a2014-02-25 14:22:56 +0000265
266 // A list of the size of the dex code holding block information for
267 // the method. If an entry contains a block, then the dex instruction
268 // starting at that entry is the first instruction of a new block.
269 GrowableArray<HBasicBlock*> branch_targets_;
270
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +0000271 GrowableArray<HLocal*> locals_;
272
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000273 HBasicBlock* entry_block_;
274 HBasicBlock* exit_block_;
275 HBasicBlock* current_block_;
David Brazdil5e8b1372015-01-23 14:39:08 +0000276 HGraph* const graph_;
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000277
Nicolas Geoffraye53798a2014-12-01 10:31:54 +0000278 // The dex file where the method being compiled is.
Nicolas Geoffray8ccc3f52014-03-19 10:34:11 +0000279 const DexFile* const dex_file_;
Nicolas Geoffraye53798a2014-12-01 10:31:54 +0000280
281 // The compilation unit of the current method being compiled. Note that
282 // it can be an inlined method.
Nicolas Geoffray01bc96d2014-04-11 17:43:50 +0100283 DexCompilationUnit* const dex_compilation_unit_;
Nicolas Geoffraye53798a2014-12-01 10:31:54 +0000284
Nicolas Geoffraye5038322014-07-04 09:41:32 +0100285 CompilerDriver* const compiler_driver_;
Nicolas Geoffraye53798a2014-12-01 10:31:54 +0000286
287 // The compilation unit of the outermost method being compiled. That is the
288 // method being compiled (and not inlined), and potentially inlining other
289 // methods.
290 const DexCompilationUnit* const outer_compilation_unit_;
291
292 // The return type of the method being compiled.
Nicolas Geoffray7fb49da2014-10-06 09:12:41 +0100293 const Primitive::Type return_type_;
Nicolas Geoffray8ccc3f52014-03-19 10:34:11 +0000294
Nicolas Geoffraya3d05a42014-10-20 17:41:32 +0100295 // The pointer in the dex file where the instructions of the code item
296 // being currently compiled start.
297 const uint16_t* code_start_;
298
299 // The last invoke or fill-new-array being built. Only to be
300 // used by move-result instructions.
301 HInstruction* latest_result_;
302
Nicolas Geoffray2e7cd752015-07-10 11:38:52 +0100303 // We need to know whether we have built a graph that has calls to StringFactory
304 // and hasn't gone through the verifier. If the following flag is `false`, then
305 // we cannot compile with baseline.
306 bool can_use_baseline_for_string_init_;
307
Calin Juravle48c2b032014-12-09 18:11:36 +0000308 OptimizingCompilerStats* compilation_stats_;
309
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000310 DISALLOW_COPY_AND_ASSIGN(HGraphBuilder);
311};
312
313} // namespace art
314
315#endif // ART_COMPILER_OPTIMIZING_BUILDER_H_