blob: fc67486267b4050bc3e4d7804b1027a16d73a32e [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_NODES_H_
18#define ART_COMPILER_OPTIMIZING_NODES_H_
19
20#include "utils/allocation.h"
Nicolas Geoffray0e336432014-02-26 18:24:38 +000021#include "utils/arena_bit_vector.h"
Nicolas Geoffray818f2102014-02-18 16:43:35 +000022#include "utils/growable_array.h"
23
24namespace art {
25
26class HBasicBlock;
27class HInstruction;
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +000028class HIntConstant;
Nicolas Geoffray818f2102014-02-18 16:43:35 +000029class HGraphVisitor;
Nicolas Geoffraybab4ed72014-03-11 17:53:17 +000030class LocationSummary;
Nicolas Geoffray818f2102014-02-18 16:43:35 +000031
32static const int kDefaultNumberOfBlocks = 8;
33static const int kDefaultNumberOfSuccessors = 2;
34static const int kDefaultNumberOfPredecessors = 2;
Nicolas Geoffraybe9a92a2014-02-25 14:22:56 +000035static const int kDefaultNumberOfBackEdges = 1;
Nicolas Geoffray818f2102014-02-18 16:43:35 +000036
37// Control-flow graph of a method. Contains a list of basic blocks.
38class HGraph : public ArenaObject {
39 public:
40 explicit HGraph(ArenaAllocator* arena)
41 : arena_(arena),
Nicolas Geoffraybe9a92a2014-02-25 14:22:56 +000042 blocks_(arena, kDefaultNumberOfBlocks),
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +000043 dominator_order_(arena, kDefaultNumberOfBlocks),
44 current_instruction_id_(0) { }
Nicolas Geoffray818f2102014-02-18 16:43:35 +000045
Nicolas Geoffray787c3072014-03-17 10:20:19 +000046 ArenaAllocator* GetArena() const { return arena_; }
47 const GrowableArray<HBasicBlock*>* GetBlocks() const { return &blocks_; }
Nicolas Geoffray818f2102014-02-18 16:43:35 +000048
Nicolas Geoffray787c3072014-03-17 10:20:19 +000049 HBasicBlock* GetEntryBlock() const { return entry_block_; }
50 HBasicBlock* GetExitBlock() const { return exit_block_; }
Nicolas Geoffrayd4dd2552014-02-28 10:23:58 +000051
Nicolas Geoffray787c3072014-03-17 10:20:19 +000052 void SetEntryBlock(HBasicBlock* block) { entry_block_ = block; }
53 void SetExitBlock(HBasicBlock* block) { exit_block_ = block; }
Nicolas Geoffrayd4dd2552014-02-28 10:23:58 +000054
Nicolas Geoffray818f2102014-02-18 16:43:35 +000055 void AddBlock(HBasicBlock* block);
Nicolas Geoffraybe9a92a2014-02-25 14:22:56 +000056 void BuildDominatorTree();
Nicolas Geoffray818f2102014-02-18 16:43:35 +000057
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +000058 int GetNextInstructionId() {
59 return current_instruction_id_++;
60 }
61
Nicolas Geoffray818f2102014-02-18 16:43:35 +000062 private:
Nicolas Geoffraybe9a92a2014-02-25 14:22:56 +000063 HBasicBlock* FindCommonDominator(HBasicBlock* first, HBasicBlock* second) const;
64 void VisitBlockForDominatorTree(HBasicBlock* block,
65 HBasicBlock* predecessor,
66 GrowableArray<size_t>* visits);
67 void FindBackEdges(ArenaBitVector* visited) const;
68 void VisitBlockForBackEdges(HBasicBlock* block,
69 ArenaBitVector* visited,
70 ArenaBitVector* visiting) const;
71 void RemoveDeadBlocks(const ArenaBitVector& visited) const;
72
Nicolas Geoffray818f2102014-02-18 16:43:35 +000073 ArenaAllocator* const arena_;
Nicolas Geoffraybe9a92a2014-02-25 14:22:56 +000074
75 // List of blocks in insertion order.
Nicolas Geoffray818f2102014-02-18 16:43:35 +000076 GrowableArray<HBasicBlock*> blocks_;
77
Nicolas Geoffraybe9a92a2014-02-25 14:22:56 +000078 // List of blocks to perform a pre-order dominator tree traversal.
79 GrowableArray<HBasicBlock*> dominator_order_;
80
Nicolas Geoffrayd4dd2552014-02-28 10:23:58 +000081 HBasicBlock* entry_block_;
82 HBasicBlock* exit_block_;
83
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +000084 // The current id to assign to a newly added instruction. See HInstruction.id_.
85 int current_instruction_id_;
86
Nicolas Geoffray818f2102014-02-18 16:43:35 +000087 DISALLOW_COPY_AND_ASSIGN(HGraph);
88};
89
Nicolas Geoffraybe9a92a2014-02-25 14:22:56 +000090class HLoopInformation : public ArenaObject {
91 public:
92 HLoopInformation(HBasicBlock* header, HGraph* graph)
93 : header_(header),
Nicolas Geoffray787c3072014-03-17 10:20:19 +000094 back_edges_(graph->GetArena(), kDefaultNumberOfBackEdges) { }
Nicolas Geoffraybe9a92a2014-02-25 14:22:56 +000095
96 void AddBackEdge(HBasicBlock* back_edge) {
97 back_edges_.Add(back_edge);
98 }
99
100 int NumberOfBackEdges() const {
101 return back_edges_.Size();
102 }
103
104 private:
105 HBasicBlock* header_;
106 GrowableArray<HBasicBlock*> back_edges_;
107
108 DISALLOW_COPY_AND_ASSIGN(HLoopInformation);
109};
110
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000111// A block in a method. Contains the list of instructions represented
112// as a double linked list. Each block knows its predecessors and
113// successors.
114class HBasicBlock : public ArenaObject {
115 public:
116 explicit HBasicBlock(HGraph* graph)
117 : graph_(graph),
Nicolas Geoffray787c3072014-03-17 10:20:19 +0000118 predecessors_(graph->GetArena(), kDefaultNumberOfPredecessors),
119 successors_(graph->GetArena(), kDefaultNumberOfSuccessors),
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000120 first_instruction_(nullptr),
121 last_instruction_(nullptr),
Nicolas Geoffraybe9a92a2014-02-25 14:22:56 +0000122 loop_information_(nullptr),
123 dominator_(nullptr),
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000124 block_id_(-1) { }
125
Nicolas Geoffray787c3072014-03-17 10:20:19 +0000126 const GrowableArray<HBasicBlock*>* GetPredecessors() const {
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000127 return &predecessors_;
128 }
129
Nicolas Geoffray787c3072014-03-17 10:20:19 +0000130 const GrowableArray<HBasicBlock*>* GetSuccessors() const {
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000131 return &successors_;
132 }
133
Nicolas Geoffraybe9a92a2014-02-25 14:22:56 +0000134 void AddBackEdge(HBasicBlock* back_edge) {
135 if (loop_information_ == nullptr) {
Nicolas Geoffray787c3072014-03-17 10:20:19 +0000136 loop_information_ = new (graph_->GetArena()) HLoopInformation(this, graph_);
Nicolas Geoffraybe9a92a2014-02-25 14:22:56 +0000137 }
138 loop_information_->AddBackEdge(back_edge);
139 }
140
Nicolas Geoffray787c3072014-03-17 10:20:19 +0000141 HGraph* GetGraph() const { return graph_; }
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000142
Nicolas Geoffray787c3072014-03-17 10:20:19 +0000143 int GetBlockId() const { return block_id_; }
144 void SetBlockId(int id) { block_id_ = id; }
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000145
Nicolas Geoffray787c3072014-03-17 10:20:19 +0000146 HBasicBlock* GetDominator() const { return dominator_; }
147 void SetDominator(HBasicBlock* dominator) { dominator_ = dominator; }
Nicolas Geoffraybe9a92a2014-02-25 14:22:56 +0000148
149 int NumberOfBackEdges() const {
150 return loop_information_ == nullptr
151 ? 0
152 : loop_information_->NumberOfBackEdges();
153 }
154
Nicolas Geoffray787c3072014-03-17 10:20:19 +0000155 HInstruction* GetFirstInstruction() const { return first_instruction_; }
156 HInstruction* GetLastInstruction() const { return last_instruction_; }
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000157
158 void AddSuccessor(HBasicBlock* block) {
159 successors_.Add(block);
160 block->predecessors_.Add(this);
161 }
162
Nicolas Geoffraybe9a92a2014-02-25 14:22:56 +0000163 void RemovePredecessor(HBasicBlock* block) {
164 predecessors_.Delete(block);
165 }
166
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000167 void AddInstruction(HInstruction* instruction);
168
169 private:
170 HGraph* const graph_;
171 GrowableArray<HBasicBlock*> predecessors_;
172 GrowableArray<HBasicBlock*> successors_;
173 HInstruction* first_instruction_;
174 HInstruction* last_instruction_;
Nicolas Geoffraybe9a92a2014-02-25 14:22:56 +0000175 HLoopInformation* loop_information_;
176 HBasicBlock* dominator_;
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000177 int block_id_;
178
179 DISALLOW_COPY_AND_ASSIGN(HBasicBlock);
180};
181
182#define FOR_EACH_INSTRUCTION(M) \
Nicolas Geoffrayd8ee7372014-03-28 15:43:40 +0000183 M(Add) \
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +0000184 M(Equal) \
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000185 M(Exit) \
186 M(Goto) \
Nicolas Geoffraybe9a92a2014-02-25 14:22:56 +0000187 M(If) \
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +0000188 M(IntConstant) \
Nicolas Geoffray8ccc3f52014-03-19 10:34:11 +0000189 M(InvokeStatic) \
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +0000190 M(LoadLocal) \
191 M(Local) \
Nicolas Geoffraybab4ed72014-03-11 17:53:17 +0000192 M(Return) \
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000193 M(ReturnVoid) \
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +0000194 M(StoreLocal) \
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000195
Nicolas Geoffraybab4ed72014-03-11 17:53:17 +0000196#define FORWARD_DECLARATION(type) class H##type;
197FOR_EACH_INSTRUCTION(FORWARD_DECLARATION)
198#undef FORWARD_DECLARATION
199
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000200#define DECLARE_INSTRUCTION(type) \
201 virtual void Accept(HGraphVisitor* visitor); \
202 virtual const char* DebugName() const { return #type; } \
Nicolas Geoffraybab4ed72014-03-11 17:53:17 +0000203 virtual H##type* As##type() { return this; } \
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000204
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +0000205class HUseListNode : public ArenaObject {
206 public:
207 HUseListNode(HInstruction* instruction, HUseListNode* tail)
208 : instruction_(instruction), tail_(tail) { }
209
Nicolas Geoffray787c3072014-03-17 10:20:19 +0000210 HUseListNode* GetTail() const { return tail_; }
211 HInstruction* GetInstruction() const { return instruction_; }
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +0000212
213 private:
214 HInstruction* const instruction_;
215 HUseListNode* const tail_;
216
217 DISALLOW_COPY_AND_ASSIGN(HUseListNode);
218};
219
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000220class HInstruction : public ArenaObject {
221 public:
Nicolas Geoffraybab4ed72014-03-11 17:53:17 +0000222 HInstruction()
223 : previous_(nullptr),
224 next_(nullptr),
225 block_(nullptr),
226 id_(-1),
227 uses_(nullptr),
228 locations_(nullptr) { }
229
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000230 virtual ~HInstruction() { }
231
Nicolas Geoffray787c3072014-03-17 10:20:19 +0000232 HInstruction* GetNext() const { return next_; }
233 HInstruction* GetPrevious() const { return previous_; }
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000234
Nicolas Geoffray787c3072014-03-17 10:20:19 +0000235 HBasicBlock* GetBlock() const { return block_; }
236 void SetBlock(HBasicBlock* block) { block_ = block; }
Nicolas Geoffrayd4dd2552014-02-28 10:23:58 +0000237
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000238 virtual intptr_t InputCount() const = 0;
239 virtual HInstruction* InputAt(intptr_t i) const = 0;
240
241 virtual void Accept(HGraphVisitor* visitor) = 0;
242 virtual const char* DebugName() const = 0;
243
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +0000244 void AddUse(HInstruction* user) {
Nicolas Geoffray787c3072014-03-17 10:20:19 +0000245 uses_ = new (block_->GetGraph()->GetArena()) HUseListNode(user, uses_);
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +0000246 }
247
Nicolas Geoffray787c3072014-03-17 10:20:19 +0000248 HUseListNode* GetUses() const { return uses_; }
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +0000249
250 bool HasUses() const { return uses_ != nullptr; }
251
Nicolas Geoffray787c3072014-03-17 10:20:19 +0000252 int GetId() const { return id_; }
253 void SetId(int id) { id_ = id; }
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +0000254
Nicolas Geoffray787c3072014-03-17 10:20:19 +0000255 LocationSummary* GetLocations() const { return locations_; }
256 void SetLocations(LocationSummary* locations) { locations_ = locations; }
Nicolas Geoffraybab4ed72014-03-11 17:53:17 +0000257
258#define INSTRUCTION_TYPE_CHECK(type) \
259 virtual H##type* As##type() { return nullptr; }
260
261 FOR_EACH_INSTRUCTION(INSTRUCTION_TYPE_CHECK)
262#undef INSTRUCTION_TYPE_CHECK
263
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000264 private:
265 HInstruction* previous_;
266 HInstruction* next_;
Nicolas Geoffrayd4dd2552014-02-28 10:23:58 +0000267 HBasicBlock* block_;
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000268
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +0000269 // An instruction gets an id when it is added to the graph.
270 // It reflects creation order. A negative id means the instruction
271 // has not beed added to the graph.
272 int id_;
273
274 HUseListNode* uses_;
275
Nicolas Geoffraybab4ed72014-03-11 17:53:17 +0000276 // Set by the code generator.
277 LocationSummary* locations_;
278
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000279 friend class HBasicBlock;
280
281 DISALLOW_COPY_AND_ASSIGN(HInstruction);
282};
283
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +0000284class HUseIterator : public ValueObject {
285 public:
Nicolas Geoffray787c3072014-03-17 10:20:19 +0000286 explicit HUseIterator(HInstruction* instruction) : current_(instruction->GetUses()) { }
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +0000287
288 bool Done() const { return current_ == nullptr; }
289
290 void Advance() {
291 DCHECK(!Done());
Nicolas Geoffray787c3072014-03-17 10:20:19 +0000292 current_ = current_->GetTail();
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +0000293 }
294
295 HInstruction* Current() const {
296 DCHECK(!Done());
Nicolas Geoffray787c3072014-03-17 10:20:19 +0000297 return current_->GetInstruction();
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +0000298 }
299
300 private:
301 HUseListNode* current_;
302
303 friend class HValue;
304};
305
306class HInputIterator : public ValueObject {
307 public:
308 explicit HInputIterator(HInstruction* instruction) : instruction_(instruction), index_(0) { }
309
310 bool Done() const { return index_ == instruction_->InputCount(); }
311 HInstruction* Current() const { return instruction_->InputAt(index_); }
312 void Advance() { index_++; }
313
314 private:
315 HInstruction* instruction_;
316 int index_;
317
318 DISALLOW_COPY_AND_ASSIGN(HInputIterator);
319};
320
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000321class HInstructionIterator : public ValueObject {
322 public:
323 explicit HInstructionIterator(HBasicBlock* block)
Nicolas Geoffray787c3072014-03-17 10:20:19 +0000324 : instruction_(block->GetFirstInstruction()) {
325 next_ = Done() ? nullptr : instruction_->GetNext();
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000326 }
327
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +0000328 bool Done() const { return instruction_ == nullptr; }
329 HInstruction* Current() const { return instruction_; }
330 void Advance() {
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000331 instruction_ = next_;
Nicolas Geoffray787c3072014-03-17 10:20:19 +0000332 next_ = Done() ? nullptr : instruction_->GetNext();
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000333 }
334
335 private:
336 HInstruction* instruction_;
337 HInstruction* next_;
338};
339
340// An embedded container with N elements of type T. Used (with partial
341// specialization for N=0) because embedded arrays cannot have size 0.
342template<typename T, intptr_t N>
343class EmbeddedArray {
344 public:
345 EmbeddedArray() : elements_() { }
346
Nicolas Geoffray787c3072014-03-17 10:20:19 +0000347 intptr_t GetLength() const { return N; }
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000348
349 const T& operator[](intptr_t i) const {
Nicolas Geoffray787c3072014-03-17 10:20:19 +0000350 DCHECK_LT(i, GetLength());
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000351 return elements_[i];
352 }
353
354 T& operator[](intptr_t i) {
Nicolas Geoffray787c3072014-03-17 10:20:19 +0000355 DCHECK_LT(i, GetLength());
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000356 return elements_[i];
357 }
358
359 const T& At(intptr_t i) const {
360 return (*this)[i];
361 }
362
363 void SetAt(intptr_t i, const T& val) {
364 (*this)[i] = val;
365 }
366
367 private:
368 T elements_[N];
369};
370
371template<typename T>
372class EmbeddedArray<T, 0> {
373 public:
374 intptr_t length() const { return 0; }
375 const T& operator[](intptr_t i) const {
376 LOG(FATAL) << "Unreachable";
377 static T sentinel = 0;
378 return sentinel;
379 }
380 T& operator[](intptr_t i) {
381 LOG(FATAL) << "Unreachable";
382 static T sentinel = 0;
383 return sentinel;
384 }
385};
386
387template<intptr_t N>
388class HTemplateInstruction: public HInstruction {
389 public:
Nicolas Geoffraybe9a92a2014-02-25 14:22:56 +0000390 HTemplateInstruction<N>() : inputs_() { }
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000391 virtual ~HTemplateInstruction() { }
392
393 virtual intptr_t InputCount() const { return N; }
394 virtual HInstruction* InputAt(intptr_t i) const { return inputs_[i]; }
395
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +0000396 protected:
397 void SetRawInputAt(intptr_t i, HInstruction* instruction) {
398 inputs_[i] = instruction;
399 }
400
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000401 private:
402 EmbeddedArray<HInstruction*, N> inputs_;
403};
404
405// Represents dex's RETURN_VOID opcode. A HReturnVoid is a control flow
406// instruction that branches to the exit block.
407class HReturnVoid : public HTemplateInstruction<0> {
408 public:
Nicolas Geoffraybe9a92a2014-02-25 14:22:56 +0000409 HReturnVoid() { }
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000410
411 DECLARE_INSTRUCTION(ReturnVoid)
412
413 private:
414 DISALLOW_COPY_AND_ASSIGN(HReturnVoid);
415};
416
Nicolas Geoffraybab4ed72014-03-11 17:53:17 +0000417// Represents dex's RETURN opcodes. A HReturn is a control flow
418// instruction that branches to the exit block.
419class HReturn : public HTemplateInstruction<1> {
420 public:
421 explicit HReturn(HInstruction* value) {
422 SetRawInputAt(0, value);
423 }
424
425 DECLARE_INSTRUCTION(Return)
426
427 private:
428 DISALLOW_COPY_AND_ASSIGN(HReturn);
429};
430
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000431// The exit instruction is the only instruction of the exit block.
432// Instructions aborting the method (HTrow and HReturn) must branch to the
433// exit block.
434class HExit : public HTemplateInstruction<0> {
435 public:
Nicolas Geoffraybe9a92a2014-02-25 14:22:56 +0000436 HExit() { }
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000437
438 DECLARE_INSTRUCTION(Exit)
439
440 private:
441 DISALLOW_COPY_AND_ASSIGN(HExit);
442};
443
444// Jumps from one block to another.
445class HGoto : public HTemplateInstruction<0> {
446 public:
Nicolas Geoffraybe9a92a2014-02-25 14:22:56 +0000447 HGoto() { }
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000448
Nicolas Geoffrayd4dd2552014-02-28 10:23:58 +0000449 HBasicBlock* GetSuccessor() const {
Nicolas Geoffray787c3072014-03-17 10:20:19 +0000450 return GetBlock()->GetSuccessors()->Get(0);
Nicolas Geoffrayd4dd2552014-02-28 10:23:58 +0000451 }
452
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000453 DECLARE_INSTRUCTION(Goto)
454
455 private:
456 DISALLOW_COPY_AND_ASSIGN(HGoto);
457};
458
Nicolas Geoffraybe9a92a2014-02-25 14:22:56 +0000459// Conditional branch. A block ending with an HIf instruction must have
460// two successors.
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +0000461class HIf : public HTemplateInstruction<1> {
Nicolas Geoffraybe9a92a2014-02-25 14:22:56 +0000462 public:
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +0000463 explicit HIf(HInstruction* input) {
464 SetRawInputAt(0, input);
465 }
Nicolas Geoffraybe9a92a2014-02-25 14:22:56 +0000466
Nicolas Geoffraybab4ed72014-03-11 17:53:17 +0000467 HBasicBlock* IfTrueSuccessor() const {
Nicolas Geoffray787c3072014-03-17 10:20:19 +0000468 return GetBlock()->GetSuccessors()->Get(0);
Nicolas Geoffraybab4ed72014-03-11 17:53:17 +0000469 }
470
471 HBasicBlock* IfFalseSuccessor() const {
Nicolas Geoffray787c3072014-03-17 10:20:19 +0000472 return GetBlock()->GetSuccessors()->Get(1);
Nicolas Geoffraybab4ed72014-03-11 17:53:17 +0000473 }
474
Nicolas Geoffraybe9a92a2014-02-25 14:22:56 +0000475 DECLARE_INSTRUCTION(If)
476
477 private:
478 DISALLOW_COPY_AND_ASSIGN(HIf);
479};
480
Nicolas Geoffrayd8ee7372014-03-28 15:43:40 +0000481class HBinaryOperation : public HTemplateInstruction<2> {
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +0000482 public:
Nicolas Geoffrayd8ee7372014-03-28 15:43:40 +0000483 HBinaryOperation(Primitive::Type result_type,
484 HInstruction* left,
485 HInstruction* right) : result_type_(result_type) {
486 SetRawInputAt(0, left);
487 SetRawInputAt(1, right);
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +0000488 }
489
Nicolas Geoffrayd8ee7372014-03-28 15:43:40 +0000490 HInstruction* GetLeft() const { return InputAt(0); }
491 HInstruction* GetRight() const { return InputAt(1); }
492 Primitive::Type GetResultType() const { return result_type_; }
493
494 virtual bool IsCommutative() { return false; }
495
496 private:
497 const Primitive::Type result_type_;
498
499 DISALLOW_COPY_AND_ASSIGN(HBinaryOperation);
500};
501
502
503// Instruction to check if two inputs are equal to each other.
504class HEqual : public HBinaryOperation {
505 public:
506 HEqual(HInstruction* first, HInstruction* second)
507 : HBinaryOperation(Primitive::kPrimBoolean, first, second) {}
508
509 virtual bool IsCommutative() { return true; }
510
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +0000511 DECLARE_INSTRUCTION(Equal)
512
513 private:
514 DISALLOW_COPY_AND_ASSIGN(HEqual);
515};
516
517// A local in the graph. Corresponds to a Dex register.
518class HLocal : public HTemplateInstruction<0> {
519 public:
520 explicit HLocal(uint16_t reg_number) : reg_number_(reg_number) { }
521
522 DECLARE_INSTRUCTION(Local)
523
Nicolas Geoffray787c3072014-03-17 10:20:19 +0000524 uint16_t GetRegNumber() const { return reg_number_; }
Nicolas Geoffraybab4ed72014-03-11 17:53:17 +0000525
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +0000526 private:
Nicolas Geoffraybab4ed72014-03-11 17:53:17 +0000527 // The Dex register number.
528 const uint16_t reg_number_;
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +0000529
530 DISALLOW_COPY_AND_ASSIGN(HLocal);
531};
532
533// Load a given local. The local is an input of this instruction.
534class HLoadLocal : public HTemplateInstruction<1> {
535 public:
536 explicit HLoadLocal(HLocal* local) {
537 SetRawInputAt(0, local);
538 }
539
Nicolas Geoffraybab4ed72014-03-11 17:53:17 +0000540 HLocal* GetLocal() const { return reinterpret_cast<HLocal*>(InputAt(0)); }
541
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +0000542 DECLARE_INSTRUCTION(LoadLocal)
543
544 private:
545 DISALLOW_COPY_AND_ASSIGN(HLoadLocal);
546};
547
548// Store a value in a given local. This instruction has two inputs: the value
549// and the local.
550class HStoreLocal : public HTemplateInstruction<2> {
551 public:
552 HStoreLocal(HLocal* local, HInstruction* value) {
553 SetRawInputAt(0, local);
554 SetRawInputAt(1, value);
555 }
556
Nicolas Geoffraybab4ed72014-03-11 17:53:17 +0000557 HLocal* GetLocal() const { return reinterpret_cast<HLocal*>(InputAt(0)); }
558
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +0000559 DECLARE_INSTRUCTION(StoreLocal)
560
561 private:
562 DISALLOW_COPY_AND_ASSIGN(HStoreLocal);
563};
564
565// Constants of the type int. Those can be from Dex instructions, or
566// synthesized (for example with the if-eqz instruction).
567class HIntConstant : public HTemplateInstruction<0> {
568 public:
569 explicit HIntConstant(int32_t value) : value_(value) { }
570
Nicolas Geoffray787c3072014-03-17 10:20:19 +0000571 int32_t GetValue() const { return value_; }
Nicolas Geoffraybab4ed72014-03-11 17:53:17 +0000572
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +0000573 DECLARE_INSTRUCTION(IntConstant)
574
575 private:
576 const int32_t value_;
577
578 DISALLOW_COPY_AND_ASSIGN(HIntConstant);
579};
580
Nicolas Geoffray8ccc3f52014-03-19 10:34:11 +0000581class HInvoke : public HInstruction {
582 public:
583 HInvoke(ArenaAllocator* arena, uint32_t number_of_arguments, int32_t dex_pc)
584 : inputs_(arena, number_of_arguments),
585 dex_pc_(dex_pc) {
586 inputs_.SetSize(number_of_arguments);
587 }
588
589 virtual intptr_t InputCount() const { return inputs_.Size(); }
590 virtual HInstruction* InputAt(intptr_t i) const { return inputs_.Get(i); }
591
592 int32_t GetDexPc() const { return dex_pc_; }
593
594 protected:
595 GrowableArray<HInstruction*> inputs_;
596 const int32_t dex_pc_;
597
598 private:
599 DISALLOW_COPY_AND_ASSIGN(HInvoke);
600};
601
602class HInvokeStatic : public HInvoke {
603 public:
604 HInvokeStatic(ArenaAllocator* arena, uint32_t number_of_arguments, int32_t dex_pc, int32_t index_in_dex_cache)
605 : HInvoke(arena, number_of_arguments, dex_pc), index_in_dex_cache_(index_in_dex_cache) { }
606
607 uint32_t GetIndexInDexCache() const { return index_in_dex_cache_; }
608
609 DECLARE_INSTRUCTION(InvokeStatic)
610
611 private:
612 uint32_t index_in_dex_cache_;
613
614 DISALLOW_COPY_AND_ASSIGN(HInvokeStatic);
615};
616
Nicolas Geoffrayd8ee7372014-03-28 15:43:40 +0000617class HAdd : public HBinaryOperation {
618 public:
619 HAdd(Primitive::Type result_type, HInstruction* left, HInstruction* right)
620 : HBinaryOperation(result_type, left, right) {}
621
622 virtual bool IsCommutative() { return true; }
623
624 DECLARE_INSTRUCTION(Add);
625
626 private:
627 DISALLOW_COPY_AND_ASSIGN(HAdd);
628};
629
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000630class HGraphVisitor : public ValueObject {
631 public:
632 explicit HGraphVisitor(HGraph* graph) : graph_(graph) { }
633 virtual ~HGraphVisitor() { }
634
635 virtual void VisitInstruction(HInstruction* instruction) { }
636 virtual void VisitBasicBlock(HBasicBlock* block);
637
638 void VisitInsertionOrder();
639
Nicolas Geoffray787c3072014-03-17 10:20:19 +0000640 HGraph* GetGraph() const { return graph_; }
Nicolas Geoffrayd4dd2552014-02-28 10:23:58 +0000641
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000642 // Visit functions for instruction classes.
643#define DECLARE_VISIT_INSTRUCTION(name) \
644 virtual void Visit##name(H##name* instr) { VisitInstruction(instr); }
645
646 FOR_EACH_INSTRUCTION(DECLARE_VISIT_INSTRUCTION)
647
648#undef DECLARE_VISIT_INSTRUCTION
649
650 private:
651 HGraph* graph_;
652
653 DISALLOW_COPY_AND_ASSIGN(HGraphVisitor);
654};
655
656} // namespace art
657
658#endif // ART_COMPILER_OPTIMIZING_NODES_H_