blob: 944e80365f1f433f3a642ed26eccab9345acf82c [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
Nicolas Geoffray4e3d23a2014-05-22 18:32:45 +010020#include "locations.h"
Nicolas Geoffraye5038322014-07-04 09:41:32 +010021#include "offsets.h"
Ian Rogerse63db272014-07-15 15:36:11 -070022#include "primitive.h"
Nicolas Geoffray818f2102014-02-18 16:43:35 +000023#include "utils/allocation.h"
Nicolas Geoffray0e336432014-02-26 18:24:38 +000024#include "utils/arena_bit_vector.h"
Nicolas Geoffray818f2102014-02-18 16:43:35 +000025#include "utils/growable_array.h"
26
27namespace art {
28
29class HBasicBlock;
Nicolas Geoffrayc32e7702014-04-24 12:43:16 +010030class HEnvironment;
Nicolas Geoffray818f2102014-02-18 16:43:35 +000031class HInstruction;
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +000032class HIntConstant;
Nicolas Geoffray818f2102014-02-18 16:43:35 +000033class HGraphVisitor;
Nicolas Geoffrayc32e7702014-04-24 12:43:16 +010034class HPhi;
Nicolas Geoffray3c049742014-09-24 18:10:46 +010035class HSuspendCheck;
Nicolas Geoffrayddb311f2014-05-16 09:28:54 +010036class LiveInterval;
Nicolas Geoffraybab4ed72014-03-11 17:53:17 +000037class LocationSummary;
Nicolas Geoffray818f2102014-02-18 16:43:35 +000038
39static const int kDefaultNumberOfBlocks = 8;
40static const int kDefaultNumberOfSuccessors = 2;
41static const int kDefaultNumberOfPredecessors = 2;
Nicolas Geoffrayd31cf3d2014-09-08 17:30:24 +010042static const int kDefaultNumberOfDominatedBlocks = 1;
Nicolas Geoffraybe9a92a2014-02-25 14:22:56 +000043static const int kDefaultNumberOfBackEdges = 1;
Nicolas Geoffray818f2102014-02-18 16:43:35 +000044
Dave Allison20dfc792014-06-16 20:44:29 -070045enum IfCondition {
46 kCondEQ,
47 kCondNE,
48 kCondLT,
49 kCondLE,
50 kCondGT,
51 kCondGE,
52};
53
Nicolas Geoffrayc32e7702014-04-24 12:43:16 +010054class HInstructionList {
55 public:
56 HInstructionList() : first_instruction_(nullptr), last_instruction_(nullptr) {}
57
58 void AddInstruction(HInstruction* instruction);
59 void RemoveInstruction(HInstruction* instruction);
60
Roland Levillain6b469232014-09-25 10:10:38 +010061 // Return true if this list contains `instruction`.
62 bool Contains(HInstruction* instruction) const;
63
Roland Levillainccc07a92014-09-16 14:48:16 +010064 // Return true if `instruction1` is found before `instruction2` in
65 // this instruction list and false otherwise. Abort if none
66 // of these instructions is found.
67 bool FoundBefore(const HInstruction* instruction1,
68 const HInstruction* instruction2) const;
69
Nicolas Geoffrayc32e7702014-04-24 12:43:16 +010070 private:
71 HInstruction* first_instruction_;
72 HInstruction* last_instruction_;
73
74 friend class HBasicBlock;
75 friend class HInstructionIterator;
Nicolas Geoffray804d0932014-05-02 08:46:00 +010076 friend class HBackwardInstructionIterator;
Nicolas Geoffrayc32e7702014-04-24 12:43:16 +010077
78 DISALLOW_COPY_AND_ASSIGN(HInstructionList);
79};
80
Nicolas Geoffray818f2102014-02-18 16:43:35 +000081// Control-flow graph of a method. Contains a list of basic blocks.
82class HGraph : public ArenaObject {
83 public:
84 explicit HGraph(ArenaAllocator* arena)
85 : arena_(arena),
Nicolas Geoffraybe9a92a2014-02-25 14:22:56 +000086 blocks_(arena, kDefaultNumberOfBlocks),
Nicolas Geoffray622d9c32014-05-12 16:11:02 +010087 reverse_post_order_(arena, kDefaultNumberOfBlocks),
Nicolas Geoffray4a34a422014-04-03 10:38:37 +010088 maximum_number_of_out_vregs_(0),
Nicolas Geoffrayf583e592014-04-07 13:20:42 +010089 number_of_vregs_(0),
90 number_of_in_vregs_(0),
Nicolas Geoffraye5038322014-07-04 09:41:32 +010091 number_of_temporaries_(0),
Dave Allison20dfc792014-06-16 20:44:29 -070092 current_instruction_id_(0) {}
Nicolas Geoffray818f2102014-02-18 16:43:35 +000093
Nicolas Geoffray787c3072014-03-17 10:20:19 +000094 ArenaAllocator* GetArena() const { return arena_; }
Nicolas Geoffray804d0932014-05-02 08:46:00 +010095 const GrowableArray<HBasicBlock*>& GetBlocks() const { return blocks_; }
Nicolas Geoffray818f2102014-02-18 16:43:35 +000096
Nicolas Geoffray787c3072014-03-17 10:20:19 +000097 HBasicBlock* GetEntryBlock() const { return entry_block_; }
98 HBasicBlock* GetExitBlock() const { return exit_block_; }
Nicolas Geoffrayd4dd2552014-02-28 10:23:58 +000099
Nicolas Geoffray787c3072014-03-17 10:20:19 +0000100 void SetEntryBlock(HBasicBlock* block) { entry_block_ = block; }
101 void SetExitBlock(HBasicBlock* block) { exit_block_ = block; }
Nicolas Geoffrayd4dd2552014-02-28 10:23:58 +0000102
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000103 void AddBlock(HBasicBlock* block);
Nicolas Geoffrayc32e7702014-04-24 12:43:16 +0100104
Nicolas Geoffraybe9a92a2014-02-25 14:22:56 +0000105 void BuildDominatorTree();
Nicolas Geoffrayc32e7702014-04-24 12:43:16 +0100106 void TransformToSSA();
107 void SimplifyCFG();
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000108
Nicolas Geoffray622d9c32014-05-12 16:11:02 +0100109 // Find all natural loops in this graph. Aborts computation and returns false
Nicolas Geoffrayf635e632014-05-14 09:43:38 +0100110 // if one loop is not natural, that is the header does not dominate the back
Nicolas Geoffray622d9c32014-05-12 16:11:02 +0100111 // edge.
112 bool FindNaturalLoops() const;
113
114 void SplitCriticalEdge(HBasicBlock* block, HBasicBlock* successor);
115 void SimplifyLoop(HBasicBlock* header);
116
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +0000117 int GetNextInstructionId() {
118 return current_instruction_id_++;
119 }
120
Nicolas Geoffray4a34a422014-04-03 10:38:37 +0100121 uint16_t GetMaximumNumberOfOutVRegs() const {
122 return maximum_number_of_out_vregs_;
123 }
124
125 void UpdateMaximumNumberOfOutVRegs(uint16_t new_value) {
126 maximum_number_of_out_vregs_ = std::max(new_value, maximum_number_of_out_vregs_);
127 }
128
Nicolas Geoffraye5038322014-07-04 09:41:32 +0100129 void UpdateNumberOfTemporaries(size_t count) {
130 number_of_temporaries_ = std::max(count, number_of_temporaries_);
131 }
132
133 size_t GetNumberOfTemporaries() const {
134 return number_of_temporaries_;
135 }
136
Nicolas Geoffrayf583e592014-04-07 13:20:42 +0100137 void SetNumberOfVRegs(uint16_t number_of_vregs) {
138 number_of_vregs_ = number_of_vregs;
139 }
140
141 uint16_t GetNumberOfVRegs() const {
142 return number_of_vregs_;
143 }
144
145 void SetNumberOfInVRegs(uint16_t value) {
146 number_of_in_vregs_ = value;
147 }
148
149 uint16_t GetNumberOfInVRegs() const {
150 return number_of_in_vregs_;
151 }
152
Nicolas Geoffrayab032bc2014-07-15 12:55:21 +0100153 uint16_t GetNumberOfLocalVRegs() const {
154 return number_of_vregs_ - number_of_in_vregs_;
155 }
156
Nicolas Geoffray622d9c32014-05-12 16:11:02 +0100157 const GrowableArray<HBasicBlock*>& GetReversePostOrder() const {
158 return reverse_post_order_;
Nicolas Geoffrayc32e7702014-04-24 12:43:16 +0100159 }
Nicolas Geoffrayf583e592014-04-07 13:20:42 +0100160
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000161 private:
Nicolas Geoffraybe9a92a2014-02-25 14:22:56 +0000162 HBasicBlock* FindCommonDominator(HBasicBlock* first, HBasicBlock* second) const;
163 void VisitBlockForDominatorTree(HBasicBlock* block,
164 HBasicBlock* predecessor,
165 GrowableArray<size_t>* visits);
Nicolas Geoffray804d0932014-05-02 08:46:00 +0100166 void FindBackEdges(ArenaBitVector* visited);
Nicolas Geoffraybe9a92a2014-02-25 14:22:56 +0000167 void VisitBlockForBackEdges(HBasicBlock* block,
168 ArenaBitVector* visited,
Nicolas Geoffray804d0932014-05-02 08:46:00 +0100169 ArenaBitVector* visiting);
Nicolas Geoffraybe9a92a2014-02-25 14:22:56 +0000170 void RemoveDeadBlocks(const ArenaBitVector& visited) const;
171
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000172 ArenaAllocator* const arena_;
Nicolas Geoffraybe9a92a2014-02-25 14:22:56 +0000173
174 // List of blocks in insertion order.
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000175 GrowableArray<HBasicBlock*> blocks_;
176
Nicolas Geoffray622d9c32014-05-12 16:11:02 +0100177 // List of blocks to perform a reverse post order tree traversal.
178 GrowableArray<HBasicBlock*> reverse_post_order_;
Nicolas Geoffraybe9a92a2014-02-25 14:22:56 +0000179
Nicolas Geoffrayd4dd2552014-02-28 10:23:58 +0000180 HBasicBlock* entry_block_;
181 HBasicBlock* exit_block_;
182
Nicolas Geoffrayf583e592014-04-07 13:20:42 +0100183 // The maximum number of virtual registers arguments passed to a HInvoke in this graph.
Nicolas Geoffray4a34a422014-04-03 10:38:37 +0100184 uint16_t maximum_number_of_out_vregs_;
185
Nicolas Geoffrayf583e592014-04-07 13:20:42 +0100186 // The number of virtual registers in this method. Contains the parameters.
187 uint16_t number_of_vregs_;
188
189 // The number of virtual registers used by parameters of this method.
190 uint16_t number_of_in_vregs_;
191
Nicolas Geoffraye5038322014-07-04 09:41:32 +0100192 // The number of temporaries that will be needed for the baseline compiler.
193 size_t number_of_temporaries_;
194
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +0000195 // The current id to assign to a newly added instruction. See HInstruction.id_.
196 int current_instruction_id_;
197
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000198 DISALLOW_COPY_AND_ASSIGN(HGraph);
199};
200
Nicolas Geoffraybe9a92a2014-02-25 14:22:56 +0000201class HLoopInformation : public ArenaObject {
202 public:
203 HLoopInformation(HBasicBlock* header, HGraph* graph)
204 : header_(header),
Nicolas Geoffray3c049742014-09-24 18:10:46 +0100205 suspend_check_(nullptr),
Nicolas Geoffray622d9c32014-05-12 16:11:02 +0100206 back_edges_(graph->GetArena(), kDefaultNumberOfBackEdges),
Nicolas Geoffrayb09aacb2014-09-17 18:21:53 +0100207 // Make bit vector growable, as the number of blocks may change.
208 blocks_(graph->GetArena(), graph->GetBlocks().Size(), true) {}
Nicolas Geoffray622d9c32014-05-12 16:11:02 +0100209
210 HBasicBlock* GetHeader() const {
211 return header_;
212 }
Nicolas Geoffraybe9a92a2014-02-25 14:22:56 +0000213
Nicolas Geoffray3c049742014-09-24 18:10:46 +0100214 HSuspendCheck* GetSuspendCheck() const { return suspend_check_; }
215 void SetSuspendCheck(HSuspendCheck* check) { suspend_check_ = check; }
216 bool HasSuspendCheck() const { return suspend_check_ != nullptr; }
217
Nicolas Geoffraybe9a92a2014-02-25 14:22:56 +0000218 void AddBackEdge(HBasicBlock* back_edge) {
219 back_edges_.Add(back_edge);
220 }
221
Nicolas Geoffray622d9c32014-05-12 16:11:02 +0100222 void RemoveBackEdge(HBasicBlock* back_edge) {
223 back_edges_.Delete(back_edge);
224 }
225
226 bool IsBackEdge(HBasicBlock* block) {
227 for (size_t i = 0, e = back_edges_.Size(); i < e; ++i) {
228 if (back_edges_.Get(i) == block) return true;
229 }
230 return false;
231 }
232
Nicolas Geoffraybe9a92a2014-02-25 14:22:56 +0000233 int NumberOfBackEdges() const {
234 return back_edges_.Size();
235 }
236
Nicolas Geoffray622d9c32014-05-12 16:11:02 +0100237 HBasicBlock* GetPreHeader() const;
Nicolas Geoffrayc32e7702014-04-24 12:43:16 +0100238
Nicolas Geoffray622d9c32014-05-12 16:11:02 +0100239 const GrowableArray<HBasicBlock*>& GetBackEdges() const {
240 return back_edges_;
Nicolas Geoffrayc32e7702014-04-24 12:43:16 +0100241 }
242
Nicolas Geoffray622d9c32014-05-12 16:11:02 +0100243 void ClearBackEdges() {
244 back_edges_.Reset();
Nicolas Geoffrayc32e7702014-04-24 12:43:16 +0100245 }
246
Nicolas Geoffray622d9c32014-05-12 16:11:02 +0100247 // Find blocks that are part of this loop. Returns whether the loop is a natural loop,
248 // that is the header dominates the back edge.
249 bool Populate();
250
251 // Returns whether this loop information contains `block`.
252 // Note that this loop information *must* be populated before entering this function.
253 bool Contains(const HBasicBlock& block) const;
254
255 // Returns whether this loop information is an inner loop of `other`.
256 // Note that `other` *must* be populated before entering this function.
257 bool IsIn(const HLoopInformation& other) const;
258
259 const ArenaBitVector& GetBlocks() const { return blocks_; }
260
Nicolas Geoffraybe9a92a2014-02-25 14:22:56 +0000261 private:
Nicolas Geoffray622d9c32014-05-12 16:11:02 +0100262 // Internal recursive implementation of `Populate`.
263 void PopulateRecursive(HBasicBlock* block);
264
Nicolas Geoffraybe9a92a2014-02-25 14:22:56 +0000265 HBasicBlock* header_;
Nicolas Geoffray3c049742014-09-24 18:10:46 +0100266 HSuspendCheck* suspend_check_;
Nicolas Geoffraybe9a92a2014-02-25 14:22:56 +0000267 GrowableArray<HBasicBlock*> back_edges_;
Nicolas Geoffray622d9c32014-05-12 16:11:02 +0100268 ArenaBitVector blocks_;
Nicolas Geoffraybe9a92a2014-02-25 14:22:56 +0000269
270 DISALLOW_COPY_AND_ASSIGN(HLoopInformation);
271};
272
Nicolas Geoffrayddb311f2014-05-16 09:28:54 +0100273static constexpr size_t kNoLifetime = -1;
Nicolas Geoffray3c049742014-09-24 18:10:46 +0100274static constexpr uint32_t kNoDexPc = -1;
Nicolas Geoffrayddb311f2014-05-16 09:28:54 +0100275
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000276// A block in a method. Contains the list of instructions represented
277// as a double linked list. Each block knows its predecessors and
278// successors.
Nicolas Geoffray3c049742014-09-24 18:10:46 +0100279
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000280class HBasicBlock : public ArenaObject {
281 public:
Nicolas Geoffray3c049742014-09-24 18:10:46 +0100282 explicit HBasicBlock(HGraph* graph, uint32_t dex_pc = kNoDexPc)
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000283 : graph_(graph),
Nicolas Geoffray787c3072014-03-17 10:20:19 +0000284 predecessors_(graph->GetArena(), kDefaultNumberOfPredecessors),
285 successors_(graph->GetArena(), kDefaultNumberOfSuccessors),
Nicolas Geoffraybe9a92a2014-02-25 14:22:56 +0000286 loop_information_(nullptr),
287 dominator_(nullptr),
Nicolas Geoffrayd31cf3d2014-09-08 17:30:24 +0100288 dominated_blocks_(graph->GetArena(), kDefaultNumberOfDominatedBlocks),
Nicolas Geoffrayddb311f2014-05-16 09:28:54 +0100289 block_id_(-1),
Nicolas Geoffray3c049742014-09-24 18:10:46 +0100290 dex_pc_(dex_pc),
Nicolas Geoffrayddb311f2014-05-16 09:28:54 +0100291 lifetime_start_(kNoLifetime),
292 lifetime_end_(kNoLifetime) {}
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000293
Nicolas Geoffray622d9c32014-05-12 16:11:02 +0100294 const GrowableArray<HBasicBlock*>& GetPredecessors() const {
295 return predecessors_;
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000296 }
297
Nicolas Geoffray622d9c32014-05-12 16:11:02 +0100298 const GrowableArray<HBasicBlock*>& GetSuccessors() const {
299 return successors_;
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000300 }
301
Nicolas Geoffrayd31cf3d2014-09-08 17:30:24 +0100302 const GrowableArray<HBasicBlock*>& GetDominatedBlocks() const {
303 return dominated_blocks_;
304 }
305
Nicolas Geoffray3c049742014-09-24 18:10:46 +0100306 bool IsEntryBlock() const {
307 return graph_->GetEntryBlock() == this;
308 }
309
310 bool IsExitBlock() const {
311 return graph_->GetExitBlock() == this;
312 }
313
Nicolas Geoffraybe9a92a2014-02-25 14:22:56 +0000314 void AddBackEdge(HBasicBlock* back_edge) {
315 if (loop_information_ == nullptr) {
Nicolas Geoffray787c3072014-03-17 10:20:19 +0000316 loop_information_ = new (graph_->GetArena()) HLoopInformation(this, graph_);
Nicolas Geoffraybe9a92a2014-02-25 14:22:56 +0000317 }
Nicolas Geoffray622d9c32014-05-12 16:11:02 +0100318 DCHECK_EQ(loop_information_->GetHeader(), this);
Nicolas Geoffraybe9a92a2014-02-25 14:22:56 +0000319 loop_information_->AddBackEdge(back_edge);
320 }
321
Nicolas Geoffray787c3072014-03-17 10:20:19 +0000322 HGraph* GetGraph() const { return graph_; }
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000323
Nicolas Geoffray787c3072014-03-17 10:20:19 +0000324 int GetBlockId() const { return block_id_; }
325 void SetBlockId(int id) { block_id_ = id; }
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000326
Nicolas Geoffray787c3072014-03-17 10:20:19 +0000327 HBasicBlock* GetDominator() const { return dominator_; }
328 void SetDominator(HBasicBlock* dominator) { dominator_ = dominator; }
Nicolas Geoffrayd31cf3d2014-09-08 17:30:24 +0100329 void AddDominatedBlock(HBasicBlock* block) { dominated_blocks_.Add(block); }
Nicolas Geoffraybe9a92a2014-02-25 14:22:56 +0000330
331 int NumberOfBackEdges() const {
332 return loop_information_ == nullptr
333 ? 0
334 : loop_information_->NumberOfBackEdges();
335 }
336
Nicolas Geoffrayc32e7702014-04-24 12:43:16 +0100337 HInstruction* GetFirstInstruction() const { return instructions_.first_instruction_; }
338 HInstruction* GetLastInstruction() const { return instructions_.last_instruction_; }
Nicolas Geoffrayf635e632014-05-14 09:43:38 +0100339 const HInstructionList& GetInstructions() const { return instructions_; }
340 const HInstructionList& GetPhis() const { return phis_; }
Nicolas Geoffraya7062e02014-05-22 12:50:17 +0100341 HInstruction* GetFirstPhi() const { return phis_.first_instruction_; }
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000342
343 void AddSuccessor(HBasicBlock* block) {
344 successors_.Add(block);
345 block->predecessors_.Add(this);
346 }
347
Nicolas Geoffrayec7e4722014-06-06 11:24:33 +0100348 void ReplaceSuccessor(HBasicBlock* existing, HBasicBlock* new_block) {
349 size_t successor_index = GetSuccessorIndexOf(existing);
350 DCHECK_NE(successor_index, static_cast<size_t>(-1));
351 existing->RemovePredecessor(this);
352 new_block->predecessors_.Add(this);
353 successors_.Put(successor_index, new_block);
Nicolas Geoffraybe9a92a2014-02-25 14:22:56 +0000354 }
355
Nicolas Geoffrayec7e4722014-06-06 11:24:33 +0100356 void RemovePredecessor(HBasicBlock* block) {
357 predecessors_.Delete(block);
Nicolas Geoffray622d9c32014-05-12 16:11:02 +0100358 }
359
360 void ClearAllPredecessors() {
361 predecessors_.Reset();
362 }
363
364 void AddPredecessor(HBasicBlock* block) {
365 predecessors_.Add(block);
366 block->successors_.Add(this);
367 }
368
Nicolas Geoffray604c6e42014-09-17 12:08:44 +0100369 void SwapPredecessors() {
Nicolas Geoffrayc83d4412014-09-18 16:46:20 +0100370 DCHECK_EQ(predecessors_.Size(), 2u);
Nicolas Geoffray604c6e42014-09-17 12:08:44 +0100371 HBasicBlock* temp = predecessors_.Get(0);
372 predecessors_.Put(0, predecessors_.Get(1));
373 predecessors_.Put(1, temp);
374 }
375
Nicolas Geoffrayddb311f2014-05-16 09:28:54 +0100376 size_t GetPredecessorIndexOf(HBasicBlock* predecessor) {
377 for (size_t i = 0, e = predecessors_.Size(); i < e; ++i) {
378 if (predecessors_.Get(i) == predecessor) {
379 return i;
380 }
381 }
382 return -1;
383 }
384
Nicolas Geoffrayec7e4722014-06-06 11:24:33 +0100385 size_t GetSuccessorIndexOf(HBasicBlock* successor) {
386 for (size_t i = 0, e = successors_.Size(); i < e; ++i) {
387 if (successors_.Get(i) == successor) {
388 return i;
389 }
390 }
391 return -1;
392 }
393
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000394 void AddInstruction(HInstruction* instruction);
Nicolas Geoffrayc32e7702014-04-24 12:43:16 +0100395 void RemoveInstruction(HInstruction* instruction);
Nicolas Geoffray4e3d23a2014-05-22 18:32:45 +0100396 void InsertInstructionBefore(HInstruction* instruction, HInstruction* cursor);
Roland Levillainccc07a92014-09-16 14:48:16 +0100397 // Replace instruction `initial` with `replacement` within this block.
398 void ReplaceAndRemoveInstructionWith(HInstruction* initial,
399 HInstruction* replacement);
Nicolas Geoffrayc32e7702014-04-24 12:43:16 +0100400 void AddPhi(HPhi* phi);
401 void RemovePhi(HPhi* phi);
402
403 bool IsLoopHeader() const {
Nicolas Geoffray622d9c32014-05-12 16:11:02 +0100404 return (loop_information_ != nullptr) && (loop_information_->GetHeader() == this);
Nicolas Geoffrayc32e7702014-04-24 12:43:16 +0100405 }
406
Roland Levillain6b879dd2014-09-22 17:13:44 +0100407 bool IsLoopPreHeaderFirstPredecessor() const {
408 DCHECK(IsLoopHeader());
409 DCHECK(!GetPredecessors().IsEmpty());
410 return GetPredecessors().Get(0) == GetLoopInformation()->GetPreHeader();
411 }
412
Nicolas Geoffrayc32e7702014-04-24 12:43:16 +0100413 HLoopInformation* GetLoopInformation() const {
414 return loop_information_;
415 }
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000416
Nicolas Geoffray622d9c32014-05-12 16:11:02 +0100417 // Set the loop_information_ on this block. This method overrides the current
418 // loop_information if it is an outer loop of the passed loop information.
419 void SetInLoop(HLoopInformation* info) {
420 if (IsLoopHeader()) {
421 // Nothing to do. This just means `info` is an outer loop.
422 } else if (loop_information_ == nullptr) {
423 loop_information_ = info;
424 } else if (loop_information_->Contains(*info->GetHeader())) {
425 // Block is currently part of an outer loop. Make it part of this inner loop.
426 // Note that a non loop header having a loop information means this loop information
427 // has already been populated
428 loop_information_ = info;
429 } else {
430 // Block is part of an inner loop. Do not update the loop information.
431 // Note that we cannot do the check `info->Contains(loop_information_)->GetHeader()`
432 // at this point, because this method is being called while populating `info`.
433 }
434 }
435
Nicolas Geoffray7dc206a2014-07-11 09:49:49 +0100436 bool IsInLoop() const { return loop_information_ != nullptr; }
437
Nicolas Geoffray622d9c32014-05-12 16:11:02 +0100438 // Returns wheter this block dominates the blocked passed as parameter.
439 bool Dominates(HBasicBlock* block) const;
440
Nicolas Geoffrayddb311f2014-05-16 09:28:54 +0100441 size_t GetLifetimeStart() const { return lifetime_start_; }
442 size_t GetLifetimeEnd() const { return lifetime_end_; }
443
444 void SetLifetimeStart(size_t start) { lifetime_start_ = start; }
445 void SetLifetimeEnd(size_t end) { lifetime_end_ = end; }
446
Nicolas Geoffray3c049742014-09-24 18:10:46 +0100447 uint32_t GetDexPc() const { return dex_pc_; }
448
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000449 private:
450 HGraph* const graph_;
451 GrowableArray<HBasicBlock*> predecessors_;
452 GrowableArray<HBasicBlock*> successors_;
Nicolas Geoffrayc32e7702014-04-24 12:43:16 +0100453 HInstructionList instructions_;
454 HInstructionList phis_;
Nicolas Geoffraybe9a92a2014-02-25 14:22:56 +0000455 HLoopInformation* loop_information_;
456 HBasicBlock* dominator_;
Nicolas Geoffrayd31cf3d2014-09-08 17:30:24 +0100457 GrowableArray<HBasicBlock*> dominated_blocks_;
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000458 int block_id_;
Nicolas Geoffray3c049742014-09-24 18:10:46 +0100459 // The dex program counter of the first instruction of this block.
460 const uint32_t dex_pc_;
Nicolas Geoffrayddb311f2014-05-16 09:28:54 +0100461 size_t lifetime_start_;
462 size_t lifetime_end_;
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000463
464 DISALLOW_COPY_AND_ASSIGN(HBasicBlock);
465};
466
Nicolas Geoffray96f89a22014-07-11 10:57:49 +0100467#define FOR_EACH_CONCRETE_INSTRUCTION(M) \
Nicolas Geoffrayd8ee7372014-03-28 15:43:40 +0000468 M(Add) \
Dave Allison20dfc792014-06-16 20:44:29 -0700469 M(Condition) \
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +0000470 M(Equal) \
Dave Allison20dfc792014-06-16 20:44:29 -0700471 M(NotEqual) \
472 M(LessThan) \
473 M(LessThanOrEqual) \
474 M(GreaterThan) \
475 M(GreaterThanOrEqual) \
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000476 M(Exit) \
477 M(Goto) \
Nicolas Geoffraybe9a92a2014-02-25 14:22:56 +0000478 M(If) \
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +0000479 M(IntConstant) \
Nicolas Geoffray8ccc3f52014-03-19 10:34:11 +0000480 M(InvokeStatic) \
Nicolas Geoffraye982f0b2014-08-13 02:11:24 +0100481 M(InvokeVirtual) \
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +0000482 M(LoadLocal) \
483 M(Local) \
Nicolas Geoffray01bc96d2014-04-11 17:43:50 +0100484 M(LongConstant) \
Nicolas Geoffray2e7038a2014-04-03 18:49:58 +0100485 M(NewInstance) \
Nicolas Geoffrayb55f8352014-04-07 15:26:35 +0100486 M(Not) \
Nicolas Geoffrayf583e592014-04-07 13:20:42 +0100487 M(ParameterValue) \
Nicolas Geoffray4e3d23a2014-05-22 18:32:45 +0100488 M(ParallelMove) \
Nicolas Geoffrayc32e7702014-04-24 12:43:16 +0100489 M(Phi) \
Nicolas Geoffraybab4ed72014-03-11 17:53:17 +0000490 M(Return) \
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000491 M(ReturnVoid) \
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +0000492 M(StoreLocal) \
Nicolas Geoffrayf583e592014-04-07 13:20:42 +0100493 M(Sub) \
Nicolas Geoffray412f10c2014-06-19 10:00:34 +0100494 M(Compare) \
Nicolas Geoffraye5038322014-07-04 09:41:32 +0100495 M(InstanceFieldGet) \
496 M(InstanceFieldSet) \
Nicolas Geoffray3c7bb982014-07-23 16:04:16 +0100497 M(ArrayGet) \
498 M(ArraySet) \
499 M(ArrayLength) \
500 M(BoundsCheck) \
Nicolas Geoffraye5038322014-07-04 09:41:32 +0100501 M(NullCheck) \
502 M(Temporary) \
Nicolas Geoffrayfbc695f2014-09-15 15:33:30 +0000503 M(SuspendCheck) \
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000504
Nicolas Geoffray96f89a22014-07-11 10:57:49 +0100505#define FOR_EACH_INSTRUCTION(M) \
506 FOR_EACH_CONCRETE_INSTRUCTION(M) \
Roland Levillainccc07a92014-09-16 14:48:16 +0100507 M(Constant) \
508 M(BinaryOperation)
Dave Allison20dfc792014-06-16 20:44:29 -0700509
Nicolas Geoffraybab4ed72014-03-11 17:53:17 +0000510#define FORWARD_DECLARATION(type) class H##type;
511FOR_EACH_INSTRUCTION(FORWARD_DECLARATION)
512#undef FORWARD_DECLARATION
513
Roland Levillainccc07a92014-09-16 14:48:16 +0100514#define DECLARE_INSTRUCTION(type) \
Nicolas Geoffrayd31cf3d2014-09-08 17:30:24 +0100515 virtual InstructionKind GetKind() const { return k##type; } \
Roland Levillainccc07a92014-09-16 14:48:16 +0100516 virtual const char* DebugName() const { return #type; } \
517 virtual const H##type* As##type() const OVERRIDE { return this; } \
518 virtual H##type* As##type() OVERRIDE { return this; } \
519 virtual bool InstructionTypeEquals(HInstruction* other) const { \
520 return other->Is##type(); \
521 } \
522 virtual void Accept(HGraphVisitor* visitor)
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000523
Nicolas Geoffrayc32e7702014-04-24 12:43:16 +0100524template <typename T>
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +0000525class HUseListNode : public ArenaObject {
526 public:
Nicolas Geoffrayc32e7702014-04-24 12:43:16 +0100527 HUseListNode(T* user, size_t index, HUseListNode* tail)
Dave Allison20dfc792014-06-16 20:44:29 -0700528 : user_(user), index_(index), tail_(tail) {}
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +0000529
Nicolas Geoffray787c3072014-03-17 10:20:19 +0000530 HUseListNode* GetTail() const { return tail_; }
Nicolas Geoffrayc32e7702014-04-24 12:43:16 +0100531 T* GetUser() const { return user_; }
532 size_t GetIndex() const { return index_; }
533
534 void SetTail(HUseListNode<T>* node) { tail_ = node; }
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +0000535
536 private:
Nicolas Geoffrayc32e7702014-04-24 12:43:16 +0100537 T* const user_;
538 const size_t index_;
539 HUseListNode<T>* tail_;
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +0000540
541 DISALLOW_COPY_AND_ASSIGN(HUseListNode);
542};
543
Nicolas Geoffray065bf772014-09-03 14:51:22 +0100544// Represents the side effects an instruction may have.
545class SideEffects : public ValueObject {
546 public:
Nicolas Geoffrayd31cf3d2014-09-08 17:30:24 +0100547 SideEffects() : flags_(0) {}
548
Nicolas Geoffray065bf772014-09-03 14:51:22 +0100549 static SideEffects None() {
550 return SideEffects(0);
551 }
552
553 static SideEffects All() {
554 return SideEffects(ChangesSomething().flags_ | DependsOnSomething().flags_);
555 }
556
557 static SideEffects ChangesSomething() {
558 return SideEffects((1 << kFlagChangesCount) - 1);
559 }
560
561 static SideEffects DependsOnSomething() {
562 int count = kFlagDependsOnCount - kFlagChangesCount;
563 return SideEffects(((1 << count) - 1) << kFlagChangesCount);
564 }
565
Nicolas Geoffrayd31cf3d2014-09-08 17:30:24 +0100566 SideEffects Union(SideEffects other) const {
567 return SideEffects(flags_ | other.flags_);
568 }
569
Roland Levillain72bceff2014-09-15 18:29:00 +0100570 bool HasSideEffects() const {
571 size_t all_bits_set = (1 << kFlagChangesCount) - 1;
572 return (flags_ & all_bits_set) != 0;
573 }
574
Nicolas Geoffrayd31cf3d2014-09-08 17:30:24 +0100575 bool HasAllSideEffects() const {
576 size_t all_bits_set = (1 << kFlagChangesCount) - 1;
577 return all_bits_set == (flags_ & all_bits_set);
578 }
579
580 bool DependsOn(SideEffects other) const {
581 size_t depends_flags = other.ComputeDependsFlags();
582 return (flags_ & depends_flags) != 0;
583 }
584
585 bool HasDependencies() const {
586 int count = kFlagDependsOnCount - kFlagChangesCount;
587 size_t all_bits_set = (1 << count) - 1;
588 return ((flags_ >> kFlagChangesCount) & all_bits_set) != 0;
589 }
590
Nicolas Geoffray065bf772014-09-03 14:51:22 +0100591 private:
592 static constexpr int kFlagChangesSomething = 0;
593 static constexpr int kFlagChangesCount = kFlagChangesSomething + 1;
594
595 static constexpr int kFlagDependsOnSomething = kFlagChangesCount;
596 static constexpr int kFlagDependsOnCount = kFlagDependsOnSomething + 1;
597
Nicolas Geoffray065bf772014-09-03 14:51:22 +0100598 explicit SideEffects(size_t flags) : flags_(flags) {}
599
Nicolas Geoffrayd31cf3d2014-09-08 17:30:24 +0100600 size_t ComputeDependsFlags() const {
601 return flags_ << kFlagChangesCount;
602 }
603
604 size_t flags_;
Nicolas Geoffray065bf772014-09-03 14:51:22 +0100605};
606
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000607class HInstruction : public ArenaObject {
608 public:
Nicolas Geoffray065bf772014-09-03 14:51:22 +0100609 explicit HInstruction(SideEffects side_effects)
Nicolas Geoffraybab4ed72014-03-11 17:53:17 +0000610 : previous_(nullptr),
611 next_(nullptr),
612 block_(nullptr),
613 id_(-1),
Nicolas Geoffray804d0932014-05-02 08:46:00 +0100614 ssa_index_(-1),
Nicolas Geoffraybab4ed72014-03-11 17:53:17 +0000615 uses_(nullptr),
Nicolas Geoffrayc32e7702014-04-24 12:43:16 +0100616 env_uses_(nullptr),
617 environment_(nullptr),
Nicolas Geoffrayddb311f2014-05-16 09:28:54 +0100618 locations_(nullptr),
619 live_interval_(nullptr),
Nicolas Geoffray065bf772014-09-03 14:51:22 +0100620 lifetime_position_(kNoLifetime),
621 side_effects_(side_effects) {}
Nicolas Geoffraybab4ed72014-03-11 17:53:17 +0000622
Dave Allison20dfc792014-06-16 20:44:29 -0700623 virtual ~HInstruction() {}
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000624
Nicolas Geoffrayd31cf3d2014-09-08 17:30:24 +0100625#define DECLARE_KIND(type) k##type,
626 enum InstructionKind {
627 FOR_EACH_INSTRUCTION(DECLARE_KIND)
628 };
629#undef DECLARE_KIND
630
Nicolas Geoffray787c3072014-03-17 10:20:19 +0000631 HInstruction* GetNext() const { return next_; }
632 HInstruction* GetPrevious() const { return previous_; }
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000633
Nicolas Geoffray787c3072014-03-17 10:20:19 +0000634 HBasicBlock* GetBlock() const { return block_; }
635 void SetBlock(HBasicBlock* block) { block_ = block; }
Nicolas Geoffray7dc206a2014-07-11 09:49:49 +0100636 bool IsInBlock() const { return block_ != nullptr; }
637 bool IsInLoop() const { return block_->IsInLoop(); }
Nicolas Geoffray3ac17fc2014-08-06 23:02:54 +0100638 bool IsLoopHeaderPhi() { return IsPhi() && block_->IsLoopHeader(); }
Nicolas Geoffrayd4dd2552014-02-28 10:23:58 +0000639
Roland Levillain6b879dd2014-09-22 17:13:44 +0100640 virtual size_t InputCount() const = 0;
Nicolas Geoffrayc32e7702014-04-24 12:43:16 +0100641 virtual HInstruction* InputAt(size_t i) const = 0;
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000642
643 virtual void Accept(HGraphVisitor* visitor) = 0;
644 virtual const char* DebugName() const = 0;
645
Nicolas Geoffray01bc96d2014-04-11 17:43:50 +0100646 virtual Primitive::Type GetType() const { return Primitive::kPrimVoid; }
Nicolas Geoffrayc32e7702014-04-24 12:43:16 +0100647 virtual void SetRawInputAt(size_t index, HInstruction* input) = 0;
Nicolas Geoffray01bc96d2014-04-11 17:43:50 +0100648
Nicolas Geoffrayc32e7702014-04-24 12:43:16 +0100649 virtual bool NeedsEnvironment() const { return false; }
Nicolas Geoffrayec7e4722014-06-06 11:24:33 +0100650 virtual bool IsControlFlow() const { return false; }
Roland Levillain72bceff2014-09-15 18:29:00 +0100651 bool HasSideEffects() const { return side_effects_.HasSideEffects(); }
Nicolas Geoffrayc32e7702014-04-24 12:43:16 +0100652
653 void AddUseAt(HInstruction* user, size_t index) {
654 uses_ = new (block_->GetGraph()->GetArena()) HUseListNode<HInstruction>(user, index, uses_);
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +0000655 }
656
Nicolas Geoffrayc32e7702014-04-24 12:43:16 +0100657 void AddEnvUseAt(HEnvironment* user, size_t index) {
Nicolas Geoffray724c9632014-09-22 12:27:27 +0100658 DCHECK(user != nullptr);
Nicolas Geoffrayc32e7702014-04-24 12:43:16 +0100659 env_uses_ = new (block_->GetGraph()->GetArena()) HUseListNode<HEnvironment>(
660 user, index, env_uses_);
661 }
662
663 void RemoveUser(HInstruction* user, size_t index);
Nicolas Geoffray724c9632014-09-22 12:27:27 +0100664 void RemoveEnvironmentUser(HEnvironment* user, size_t index);
Nicolas Geoffrayc32e7702014-04-24 12:43:16 +0100665
666 HUseListNode<HInstruction>* GetUses() const { return uses_; }
667 HUseListNode<HEnvironment>* GetEnvUses() const { return env_uses_; }
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +0000668
Nicolas Geoffray804d0932014-05-02 08:46:00 +0100669 bool HasUses() const { return uses_ != nullptr || env_uses_ != nullptr; }
Nicolas Geoffray7dc206a2014-07-11 09:49:49 +0100670 bool HasEnvironmentUses() const { return env_uses_ != nullptr; }
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +0000671
Nicolas Geoffrayf635e632014-05-14 09:43:38 +0100672 size_t NumberOfUses() const {
Nicolas Geoffray0d3f5782014-05-14 09:43:38 +0100673 // TODO: Optimize this method if it is used outside of the HGraphVisualizer.
Nicolas Geoffrayf635e632014-05-14 09:43:38 +0100674 size_t result = 0;
675 HUseListNode<HInstruction>* current = uses_;
676 while (current != nullptr) {
677 current = current->GetTail();
678 ++result;
679 }
680 return result;
681 }
682
Roland Levillainccc07a92014-09-16 14:48:16 +0100683 // Does this instruction dominate `other_instruction`? Aborts if
684 // this instruction and `other_instruction` are both phis.
685 bool Dominates(HInstruction* other_instruction) const;
686
Nicolas Geoffray787c3072014-03-17 10:20:19 +0000687 int GetId() const { return id_; }
688 void SetId(int id) { id_ = id; }
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +0000689
Nicolas Geoffray804d0932014-05-02 08:46:00 +0100690 int GetSsaIndex() const { return ssa_index_; }
691 void SetSsaIndex(int ssa_index) { ssa_index_ = ssa_index; }
692 bool HasSsaIndex() const { return ssa_index_ != -1; }
693
694 bool HasEnvironment() const { return environment_ != nullptr; }
695 HEnvironment* GetEnvironment() const { return environment_; }
Nicolas Geoffrayc32e7702014-04-24 12:43:16 +0100696 void SetEnvironment(HEnvironment* environment) { environment_ = environment; }
697
Nicolas Geoffray39468442014-09-02 15:17:15 +0100698 // Returns the number of entries in the environment. Typically, that is the
699 // number of dex registers in a method. It could be more in case of inlining.
700 size_t EnvironmentSize() const;
701
Nicolas Geoffray787c3072014-03-17 10:20:19 +0000702 LocationSummary* GetLocations() const { return locations_; }
703 void SetLocations(LocationSummary* locations) { locations_ = locations; }
Nicolas Geoffraybab4ed72014-03-11 17:53:17 +0000704
Nicolas Geoffrayc32e7702014-04-24 12:43:16 +0100705 void ReplaceWith(HInstruction* instruction);
706
Dave Allison20dfc792014-06-16 20:44:29 -0700707 bool HasOnlyOneUse() const {
708 return uses_ != nullptr && uses_->GetTail() == nullptr;
709 }
710
Nicolas Geoffraybab4ed72014-03-11 17:53:17 +0000711#define INSTRUCTION_TYPE_CHECK(type) \
Roland Levillainccc07a92014-09-16 14:48:16 +0100712 bool Is##type() const { return (As##type() != nullptr); } \
713 virtual const H##type* As##type() const { return nullptr; } \
Nicolas Geoffraybab4ed72014-03-11 17:53:17 +0000714 virtual H##type* As##type() { return nullptr; }
715
716 FOR_EACH_INSTRUCTION(INSTRUCTION_TYPE_CHECK)
717#undef INSTRUCTION_TYPE_CHECK
718
Nicolas Geoffray065bf772014-09-03 14:51:22 +0100719 // Returns whether the instruction can be moved within the graph.
720 virtual bool CanBeMoved() const { return false; }
721
722 // Returns whether the two instructions are of the same kind.
723 virtual bool InstructionTypeEquals(HInstruction* other) const { return false; }
724
725 // Returns whether any data encoded in the two instructions is equal.
726 // This method does not look at the inputs. Both instructions must be
727 // of the same type, otherwise the method has undefined behavior.
728 virtual bool InstructionDataEquals(HInstruction* other) const { return false; }
729
730 // Returns whether two instructions are equal, that is:
731 // 1) They have the same type and contain the same data,
732 // 2) Their inputs are identical.
733 bool Equals(HInstruction* other) const;
734
Nicolas Geoffrayd31cf3d2014-09-08 17:30:24 +0100735 virtual InstructionKind GetKind() const = 0;
736
737 virtual size_t ComputeHashCode() const {
738 size_t result = GetKind();
739 for (size_t i = 0, e = InputCount(); i < e; ++i) {
740 result = (result * 31) + InputAt(i)->GetId();
741 }
742 return result;
743 }
744
745 SideEffects GetSideEffects() const { return side_effects_; }
746
Nicolas Geoffrayddb311f2014-05-16 09:28:54 +0100747 size_t GetLifetimePosition() const { return lifetime_position_; }
748 void SetLifetimePosition(size_t position) { lifetime_position_ = position; }
749 LiveInterval* GetLiveInterval() const { return live_interval_; }
750 void SetLiveInterval(LiveInterval* interval) { live_interval_ = interval; }
751 bool HasLiveInterval() const { return live_interval_ != nullptr; }
752
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000753 private:
754 HInstruction* previous_;
755 HInstruction* next_;
Nicolas Geoffrayd4dd2552014-02-28 10:23:58 +0000756 HBasicBlock* block_;
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000757
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +0000758 // An instruction gets an id when it is added to the graph.
759 // It reflects creation order. A negative id means the instruction
Nicolas Geoffray39468442014-09-02 15:17:15 +0100760 // has not been added to the graph.
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +0000761 int id_;
762
Nicolas Geoffray804d0932014-05-02 08:46:00 +0100763 // When doing liveness analysis, instructions that have uses get an SSA index.
764 int ssa_index_;
765
Nicolas Geoffrayc32e7702014-04-24 12:43:16 +0100766 // List of instructions that have this instruction as input.
767 HUseListNode<HInstruction>* uses_;
768
769 // List of environments that contain this instruction.
770 HUseListNode<HEnvironment>* env_uses_;
771
Nicolas Geoffray39468442014-09-02 15:17:15 +0100772 // The environment associated with this instruction. Not null if the instruction
773 // might jump out of the method.
Nicolas Geoffrayc32e7702014-04-24 12:43:16 +0100774 HEnvironment* environment_;
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +0000775
Nicolas Geoffraybab4ed72014-03-11 17:53:17 +0000776 // Set by the code generator.
777 LocationSummary* locations_;
778
Nicolas Geoffrayddb311f2014-05-16 09:28:54 +0100779 // Set by the liveness analysis.
780 LiveInterval* live_interval_;
781
782 // Set by the liveness analysis, this is the position in a linear
783 // order of blocks where this instruction's live interval start.
784 size_t lifetime_position_;
785
Nicolas Geoffray065bf772014-09-03 14:51:22 +0100786 const SideEffects side_effects_;
787
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000788 friend class HBasicBlock;
Nicolas Geoffrayc32e7702014-04-24 12:43:16 +0100789 friend class HInstructionList;
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000790
791 DISALLOW_COPY_AND_ASSIGN(HInstruction);
792};
793
Nicolas Geoffrayc32e7702014-04-24 12:43:16 +0100794template<typename T>
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +0000795class HUseIterator : public ValueObject {
796 public:
Nicolas Geoffrayc32e7702014-04-24 12:43:16 +0100797 explicit HUseIterator(HUseListNode<T>* uses) : current_(uses) {}
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +0000798
799 bool Done() const { return current_ == nullptr; }
800
801 void Advance() {
802 DCHECK(!Done());
Nicolas Geoffray787c3072014-03-17 10:20:19 +0000803 current_ = current_->GetTail();
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +0000804 }
805
Nicolas Geoffrayc32e7702014-04-24 12:43:16 +0100806 HUseListNode<T>* Current() const {
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +0000807 DCHECK(!Done());
Nicolas Geoffrayc32e7702014-04-24 12:43:16 +0100808 return current_;
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +0000809 }
810
811 private:
Nicolas Geoffrayc32e7702014-04-24 12:43:16 +0100812 HUseListNode<T>* current_;
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +0000813
814 friend class HValue;
815};
816
Nicolas Geoffrayc32e7702014-04-24 12:43:16 +0100817// A HEnvironment object contains the values of virtual registers at a given location.
818class HEnvironment : public ArenaObject {
819 public:
820 HEnvironment(ArenaAllocator* arena, size_t number_of_vregs) : vregs_(arena, number_of_vregs) {
821 vregs_.SetSize(number_of_vregs);
822 for (size_t i = 0; i < number_of_vregs; i++) {
823 vregs_.Put(i, nullptr);
824 }
825 }
826
827 void Populate(const GrowableArray<HInstruction*>& env) {
828 for (size_t i = 0; i < env.Size(); i++) {
829 HInstruction* instruction = env.Get(i);
830 vregs_.Put(i, instruction);
831 if (instruction != nullptr) {
832 instruction->AddEnvUseAt(this, i);
833 }
834 }
835 }
836
837 void SetRawEnvAt(size_t index, HInstruction* instruction) {
838 vregs_.Put(index, instruction);
839 }
840
Nicolas Geoffray39468442014-09-02 15:17:15 +0100841 HInstruction* GetInstructionAt(size_t index) const {
842 return vregs_.Get(index);
843 }
844
Nicolas Geoffrayc32e7702014-04-24 12:43:16 +0100845 GrowableArray<HInstruction*>* GetVRegs() {
846 return &vregs_;
847 }
848
Nicolas Geoffray39468442014-09-02 15:17:15 +0100849 size_t Size() const { return vregs_.Size(); }
850
Nicolas Geoffrayc32e7702014-04-24 12:43:16 +0100851 private:
852 GrowableArray<HInstruction*> vregs_;
853
854 DISALLOW_COPY_AND_ASSIGN(HEnvironment);
855};
856
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +0000857class HInputIterator : public ValueObject {
858 public:
Dave Allison20dfc792014-06-16 20:44:29 -0700859 explicit HInputIterator(HInstruction* instruction) : instruction_(instruction), index_(0) {}
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +0000860
861 bool Done() const { return index_ == instruction_->InputCount(); }
862 HInstruction* Current() const { return instruction_->InputAt(index_); }
863 void Advance() { index_++; }
864
865 private:
866 HInstruction* instruction_;
Nicolas Geoffrayc32e7702014-04-24 12:43:16 +0100867 size_t index_;
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +0000868
869 DISALLOW_COPY_AND_ASSIGN(HInputIterator);
870};
871
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000872class HInstructionIterator : public ValueObject {
873 public:
Nicolas Geoffrayc32e7702014-04-24 12:43:16 +0100874 explicit HInstructionIterator(const HInstructionList& instructions)
875 : instruction_(instructions.first_instruction_) {
Nicolas Geoffray787c3072014-03-17 10:20:19 +0000876 next_ = Done() ? nullptr : instruction_->GetNext();
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000877 }
878
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +0000879 bool Done() const { return instruction_ == nullptr; }
880 HInstruction* Current() const { return instruction_; }
881 void Advance() {
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000882 instruction_ = next_;
Nicolas Geoffray787c3072014-03-17 10:20:19 +0000883 next_ = Done() ? nullptr : instruction_->GetNext();
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000884 }
885
886 private:
887 HInstruction* instruction_;
888 HInstruction* next_;
Nicolas Geoffrayddb311f2014-05-16 09:28:54 +0100889
890 DISALLOW_COPY_AND_ASSIGN(HInstructionIterator);
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000891};
892
Nicolas Geoffray804d0932014-05-02 08:46:00 +0100893class HBackwardInstructionIterator : public ValueObject {
894 public:
895 explicit HBackwardInstructionIterator(const HInstructionList& instructions)
896 : instruction_(instructions.last_instruction_) {
897 next_ = Done() ? nullptr : instruction_->GetPrevious();
898 }
899
900 bool Done() const { return instruction_ == nullptr; }
901 HInstruction* Current() const { return instruction_; }
902 void Advance() {
903 instruction_ = next_;
904 next_ = Done() ? nullptr : instruction_->GetPrevious();
905 }
906
907 private:
908 HInstruction* instruction_;
909 HInstruction* next_;
Nicolas Geoffrayddb311f2014-05-16 09:28:54 +0100910
911 DISALLOW_COPY_AND_ASSIGN(HBackwardInstructionIterator);
Nicolas Geoffray804d0932014-05-02 08:46:00 +0100912};
913
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000914// An embedded container with N elements of type T. Used (with partial
915// specialization for N=0) because embedded arrays cannot have size 0.
916template<typename T, intptr_t N>
917class EmbeddedArray {
918 public:
Dave Allison20dfc792014-06-16 20:44:29 -0700919 EmbeddedArray() : elements_() {}
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000920
Nicolas Geoffray787c3072014-03-17 10:20:19 +0000921 intptr_t GetLength() const { return N; }
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000922
923 const T& operator[](intptr_t i) const {
Nicolas Geoffray787c3072014-03-17 10:20:19 +0000924 DCHECK_LT(i, GetLength());
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000925 return elements_[i];
926 }
927
928 T& operator[](intptr_t i) {
Nicolas Geoffray787c3072014-03-17 10:20:19 +0000929 DCHECK_LT(i, GetLength());
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000930 return elements_[i];
931 }
932
933 const T& At(intptr_t i) const {
934 return (*this)[i];
935 }
936
937 void SetAt(intptr_t i, const T& val) {
938 (*this)[i] = val;
939 }
940
941 private:
942 T elements_[N];
943};
944
945template<typename T>
946class EmbeddedArray<T, 0> {
947 public:
948 intptr_t length() const { return 0; }
949 const T& operator[](intptr_t i) const {
950 LOG(FATAL) << "Unreachable";
951 static T sentinel = 0;
952 return sentinel;
953 }
954 T& operator[](intptr_t i) {
955 LOG(FATAL) << "Unreachable";
956 static T sentinel = 0;
957 return sentinel;
958 }
959};
960
961template<intptr_t N>
962class HTemplateInstruction: public HInstruction {
963 public:
Nicolas Geoffray065bf772014-09-03 14:51:22 +0100964 HTemplateInstruction<N>(SideEffects side_effects)
965 : HInstruction(side_effects), inputs_() {}
Dave Allison20dfc792014-06-16 20:44:29 -0700966 virtual ~HTemplateInstruction() {}
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000967
Nicolas Geoffrayc32e7702014-04-24 12:43:16 +0100968 virtual size_t InputCount() const { return N; }
969 virtual HInstruction* InputAt(size_t i) const { return inputs_[i]; }
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000970
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +0000971 protected:
Nicolas Geoffrayc32e7702014-04-24 12:43:16 +0100972 virtual void SetRawInputAt(size_t i, HInstruction* instruction) {
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +0000973 inputs_[i] = instruction;
974 }
975
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000976 private:
977 EmbeddedArray<HInstruction*, N> inputs_;
Nicolas Geoffrayc32e7702014-04-24 12:43:16 +0100978
979 friend class SsaBuilder;
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000980};
981
Dave Allison20dfc792014-06-16 20:44:29 -0700982template<intptr_t N>
Nicolas Geoffray065bf772014-09-03 14:51:22 +0100983class HExpression : public HTemplateInstruction<N> {
Dave Allison20dfc792014-06-16 20:44:29 -0700984 public:
Nicolas Geoffray065bf772014-09-03 14:51:22 +0100985 HExpression<N>(Primitive::Type type, SideEffects side_effects)
986 : HTemplateInstruction<N>(side_effects), type_(type) {}
Dave Allison20dfc792014-06-16 20:44:29 -0700987 virtual ~HExpression() {}
988
989 virtual Primitive::Type GetType() const { return type_; }
990
991 private:
992 const Primitive::Type type_;
993};
994
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000995// Represents dex's RETURN_VOID opcode. A HReturnVoid is a control flow
996// instruction that branches to the exit block.
997class HReturnVoid : public HTemplateInstruction<0> {
998 public:
Nicolas Geoffray065bf772014-09-03 14:51:22 +0100999 HReturnVoid() : HTemplateInstruction(SideEffects::None()) {}
Nicolas Geoffrayec7e4722014-06-06 11:24:33 +01001000
1001 virtual bool IsControlFlow() const { return true; }
Nicolas Geoffray818f2102014-02-18 16:43:35 +00001002
Nicolas Geoffraya7062e02014-05-22 12:50:17 +01001003 DECLARE_INSTRUCTION(ReturnVoid);
Nicolas Geoffray818f2102014-02-18 16:43:35 +00001004
1005 private:
1006 DISALLOW_COPY_AND_ASSIGN(HReturnVoid);
1007};
1008
Nicolas Geoffraybab4ed72014-03-11 17:53:17 +00001009// Represents dex's RETURN opcodes. A HReturn is a control flow
1010// instruction that branches to the exit block.
1011class HReturn : public HTemplateInstruction<1> {
1012 public:
Nicolas Geoffray065bf772014-09-03 14:51:22 +01001013 explicit HReturn(HInstruction* value) : HTemplateInstruction(SideEffects::None()) {
Nicolas Geoffraybab4ed72014-03-11 17:53:17 +00001014 SetRawInputAt(0, value);
1015 }
1016
Nicolas Geoffrayec7e4722014-06-06 11:24:33 +01001017 virtual bool IsControlFlow() const { return true; }
1018
Nicolas Geoffraya7062e02014-05-22 12:50:17 +01001019 DECLARE_INSTRUCTION(Return);
Nicolas Geoffraybab4ed72014-03-11 17:53:17 +00001020
1021 private:
1022 DISALLOW_COPY_AND_ASSIGN(HReturn);
1023};
1024
Nicolas Geoffray818f2102014-02-18 16:43:35 +00001025// The exit instruction is the only instruction of the exit block.
1026// Instructions aborting the method (HTrow and HReturn) must branch to the
1027// exit block.
1028class HExit : public HTemplateInstruction<0> {
1029 public:
Nicolas Geoffray065bf772014-09-03 14:51:22 +01001030 HExit() : HTemplateInstruction(SideEffects::None()) {}
Nicolas Geoffrayec7e4722014-06-06 11:24:33 +01001031
1032 virtual bool IsControlFlow() const { return true; }
Nicolas Geoffray818f2102014-02-18 16:43:35 +00001033
Nicolas Geoffraya7062e02014-05-22 12:50:17 +01001034 DECLARE_INSTRUCTION(Exit);
Nicolas Geoffray818f2102014-02-18 16:43:35 +00001035
1036 private:
1037 DISALLOW_COPY_AND_ASSIGN(HExit);
1038};
1039
1040// Jumps from one block to another.
1041class HGoto : public HTemplateInstruction<0> {
1042 public:
Nicolas Geoffray065bf772014-09-03 14:51:22 +01001043 HGoto() : HTemplateInstruction(SideEffects::None()) {}
1044
1045 virtual bool IsControlFlow() const { return true; }
Nicolas Geoffray818f2102014-02-18 16:43:35 +00001046
Nicolas Geoffrayd4dd2552014-02-28 10:23:58 +00001047 HBasicBlock* GetSuccessor() const {
Nicolas Geoffray622d9c32014-05-12 16:11:02 +01001048 return GetBlock()->GetSuccessors().Get(0);
Nicolas Geoffrayd4dd2552014-02-28 10:23:58 +00001049 }
1050
Nicolas Geoffraya7062e02014-05-22 12:50:17 +01001051 DECLARE_INSTRUCTION(Goto);
Nicolas Geoffray818f2102014-02-18 16:43:35 +00001052
1053 private:
1054 DISALLOW_COPY_AND_ASSIGN(HGoto);
1055};
1056
Dave Allison20dfc792014-06-16 20:44:29 -07001057
Nicolas Geoffraybe9a92a2014-02-25 14:22:56 +00001058// Conditional branch. A block ending with an HIf instruction must have
1059// two successors.
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +00001060class HIf : public HTemplateInstruction<1> {
Nicolas Geoffraybe9a92a2014-02-25 14:22:56 +00001061 public:
Nicolas Geoffray065bf772014-09-03 14:51:22 +01001062 explicit HIf(HInstruction* input) : HTemplateInstruction(SideEffects::None()) {
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +00001063 SetRawInputAt(0, input);
1064 }
Nicolas Geoffraybe9a92a2014-02-25 14:22:56 +00001065
Nicolas Geoffray065bf772014-09-03 14:51:22 +01001066 virtual bool IsControlFlow() const { return true; }
1067
Nicolas Geoffraybab4ed72014-03-11 17:53:17 +00001068 HBasicBlock* IfTrueSuccessor() const {
Nicolas Geoffray622d9c32014-05-12 16:11:02 +01001069 return GetBlock()->GetSuccessors().Get(0);
Nicolas Geoffraybab4ed72014-03-11 17:53:17 +00001070 }
1071
1072 HBasicBlock* IfFalseSuccessor() const {
Nicolas Geoffray622d9c32014-05-12 16:11:02 +01001073 return GetBlock()->GetSuccessors().Get(1);
Nicolas Geoffraybab4ed72014-03-11 17:53:17 +00001074 }
1075
Nicolas Geoffraya7062e02014-05-22 12:50:17 +01001076 DECLARE_INSTRUCTION(If);
Nicolas Geoffraybe9a92a2014-02-25 14:22:56 +00001077
Dave Allison20dfc792014-06-16 20:44:29 -07001078 virtual bool IsIfInstruction() const { return true; }
1079
Nicolas Geoffraybe9a92a2014-02-25 14:22:56 +00001080 private:
1081 DISALLOW_COPY_AND_ASSIGN(HIf);
1082};
1083
Dave Allison20dfc792014-06-16 20:44:29 -07001084class HBinaryOperation : public HExpression<2> {
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +00001085 public:
Nicolas Geoffrayd8ee7372014-03-28 15:43:40 +00001086 HBinaryOperation(Primitive::Type result_type,
1087 HInstruction* left,
Nicolas Geoffray065bf772014-09-03 14:51:22 +01001088 HInstruction* right) : HExpression(result_type, SideEffects::None()) {
Nicolas Geoffrayd8ee7372014-03-28 15:43:40 +00001089 SetRawInputAt(0, left);
1090 SetRawInputAt(1, right);
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +00001091 }
1092
Nicolas Geoffrayd8ee7372014-03-28 15:43:40 +00001093 HInstruction* GetLeft() const { return InputAt(0); }
1094 HInstruction* GetRight() const { return InputAt(1); }
Dave Allison20dfc792014-06-16 20:44:29 -07001095 Primitive::Type GetResultType() const { return GetType(); }
Nicolas Geoffrayd8ee7372014-03-28 15:43:40 +00001096
1097 virtual bool IsCommutative() { return false; }
1098
Nicolas Geoffray065bf772014-09-03 14:51:22 +01001099 virtual bool CanBeMoved() const { return true; }
1100 virtual bool InstructionDataEquals(HInstruction* other) const { return true; }
1101
Roland Levillain556c3d12014-09-18 15:25:07 +01001102 // Try to statically evaluate `operation` and return an HConstant
1103 // containing the result of this evaluation. If `operation` cannot
1104 // be evaluated as a constant, return nullptr.
1105 HConstant* TryStaticEvaluation(ArenaAllocator* allocator) const;
1106
1107 // Apply this operation to `x` and `y`.
1108 virtual int32_t Evaluate(int32_t x, int32_t y) const = 0;
1109 virtual int64_t Evaluate(int64_t x, int64_t y) const = 0;
1110
Roland Levillainccc07a92014-09-16 14:48:16 +01001111 DECLARE_INSTRUCTION(BinaryOperation);
1112
Nicolas Geoffrayd8ee7372014-03-28 15:43:40 +00001113 private:
Nicolas Geoffrayd8ee7372014-03-28 15:43:40 +00001114 DISALLOW_COPY_AND_ASSIGN(HBinaryOperation);
1115};
1116
Dave Allison20dfc792014-06-16 20:44:29 -07001117class HCondition : public HBinaryOperation {
Nicolas Geoffrayd8ee7372014-03-28 15:43:40 +00001118 public:
Dave Allison20dfc792014-06-16 20:44:29 -07001119 HCondition(HInstruction* first, HInstruction* second)
Nicolas Geoffrayd8ee7372014-03-28 15:43:40 +00001120 : HBinaryOperation(Primitive::kPrimBoolean, first, second) {}
1121
1122 virtual bool IsCommutative() { return true; }
Nicolas Geoffray18efde52014-09-22 15:51:11 +01001123
1124 // For register allocation purposes, returns whether this instruction needs to be
1125 // materialized (that is, not just be in the processor flags).
Dave Allison20dfc792014-06-16 20:44:29 -07001126 bool NeedsMaterialization() const;
Nicolas Geoffrayd8ee7372014-03-28 15:43:40 +00001127
Nicolas Geoffray18efde52014-09-22 15:51:11 +01001128 // For code generation purposes, returns whether this instruction is just before
1129 // `if_`, and disregard moves in between.
1130 bool IsBeforeWhenDisregardMoves(HIf* if_) const;
1131
Dave Allison20dfc792014-06-16 20:44:29 -07001132 DECLARE_INSTRUCTION(Condition);
1133
1134 virtual IfCondition GetCondition() const = 0;
1135
1136 private:
1137 DISALLOW_COPY_AND_ASSIGN(HCondition);
1138};
1139
1140// Instruction to check if two inputs are equal to each other.
1141class HEqual : public HCondition {
1142 public:
1143 HEqual(HInstruction* first, HInstruction* second)
1144 : HCondition(first, second) {}
Nicolas Geoffray01bc96d2014-04-11 17:43:50 +01001145
Roland Levillain556c3d12014-09-18 15:25:07 +01001146 virtual int32_t Evaluate(int32_t x, int32_t y) const { return x == y; }
1147 virtual int64_t Evaluate(int64_t x, int64_t y) const { return x == y; }
1148
Nicolas Geoffraya7062e02014-05-22 12:50:17 +01001149 DECLARE_INSTRUCTION(Equal);
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +00001150
Dave Allison20dfc792014-06-16 20:44:29 -07001151 virtual IfCondition GetCondition() const {
1152 return kCondEQ;
1153 }
1154
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +00001155 private:
1156 DISALLOW_COPY_AND_ASSIGN(HEqual);
1157};
1158
Dave Allison20dfc792014-06-16 20:44:29 -07001159class HNotEqual : public HCondition {
1160 public:
1161 HNotEqual(HInstruction* first, HInstruction* second)
1162 : HCondition(first, second) {}
1163
Roland Levillain556c3d12014-09-18 15:25:07 +01001164 virtual int32_t Evaluate(int32_t x, int32_t y) const { return x != y; }
1165 virtual int64_t Evaluate(int64_t x, int64_t y) const { return x != y; }
1166
Dave Allison20dfc792014-06-16 20:44:29 -07001167 DECLARE_INSTRUCTION(NotEqual);
1168
1169 virtual IfCondition GetCondition() const {
1170 return kCondNE;
1171 }
1172
1173 private:
1174 DISALLOW_COPY_AND_ASSIGN(HNotEqual);
1175};
1176
1177class HLessThan : public HCondition {
1178 public:
1179 HLessThan(HInstruction* first, HInstruction* second)
1180 : HCondition(first, second) {}
1181
Roland Levillain556c3d12014-09-18 15:25:07 +01001182 virtual int32_t Evaluate(int32_t x, int32_t y) const { return x < y; }
1183 virtual int64_t Evaluate(int64_t x, int64_t y) const { return x < y; }
1184
Dave Allison20dfc792014-06-16 20:44:29 -07001185 DECLARE_INSTRUCTION(LessThan);
1186
1187 virtual IfCondition GetCondition() const {
1188 return kCondLT;
1189 }
1190
1191 private:
1192 DISALLOW_COPY_AND_ASSIGN(HLessThan);
1193};
1194
1195class HLessThanOrEqual : public HCondition {
1196 public:
1197 HLessThanOrEqual(HInstruction* first, HInstruction* second)
1198 : HCondition(first, second) {}
1199
Roland Levillain556c3d12014-09-18 15:25:07 +01001200 virtual int32_t Evaluate(int32_t x, int32_t y) const { return x <= y; }
1201 virtual int64_t Evaluate(int64_t x, int64_t y) const { return x <= y; }
1202
Dave Allison20dfc792014-06-16 20:44:29 -07001203 DECLARE_INSTRUCTION(LessThanOrEqual);
1204
1205 virtual IfCondition GetCondition() const {
1206 return kCondLE;
1207 }
1208
1209 private:
1210 DISALLOW_COPY_AND_ASSIGN(HLessThanOrEqual);
1211};
1212
1213class HGreaterThan : public HCondition {
1214 public:
1215 HGreaterThan(HInstruction* first, HInstruction* second)
1216 : HCondition(first, second) {}
1217
Roland Levillain556c3d12014-09-18 15:25:07 +01001218 virtual int32_t Evaluate(int32_t x, int32_t y) const { return x > y; }
1219 virtual int64_t Evaluate(int64_t x, int64_t y) const { return x > y; }
1220
Dave Allison20dfc792014-06-16 20:44:29 -07001221 DECLARE_INSTRUCTION(GreaterThan);
1222
1223 virtual IfCondition GetCondition() const {
1224 return kCondGT;
1225 }
1226
1227 private:
1228 DISALLOW_COPY_AND_ASSIGN(HGreaterThan);
1229};
1230
1231class HGreaterThanOrEqual : public HCondition {
1232 public:
1233 HGreaterThanOrEqual(HInstruction* first, HInstruction* second)
1234 : HCondition(first, second) {}
1235
Roland Levillain556c3d12014-09-18 15:25:07 +01001236 virtual int32_t Evaluate(int32_t x, int32_t y) const { return x >= y; }
1237 virtual int64_t Evaluate(int64_t x, int64_t y) const { return x >= y; }
1238
Dave Allison20dfc792014-06-16 20:44:29 -07001239 DECLARE_INSTRUCTION(GreaterThanOrEqual);
1240
1241 virtual IfCondition GetCondition() const {
1242 return kCondGE;
1243 }
1244
1245 private:
1246 DISALLOW_COPY_AND_ASSIGN(HGreaterThanOrEqual);
1247};
1248
1249
Nicolas Geoffray412f10c2014-06-19 10:00:34 +01001250// Instruction to check how two inputs compare to each other.
1251// Result is 0 if input0 == input1, 1 if input0 > input1, or -1 if input0 < input1.
1252class HCompare : public HBinaryOperation {
1253 public:
1254 HCompare(Primitive::Type type, HInstruction* first, HInstruction* second)
1255 : HBinaryOperation(Primitive::kPrimInt, first, second) {
1256 DCHECK_EQ(type, first->GetType());
1257 DCHECK_EQ(type, second->GetType());
1258 }
1259
Roland Levillain556c3d12014-09-18 15:25:07 +01001260 virtual int32_t Evaluate(int32_t x, int32_t y) const {
1261 return
1262 x == y ? 0 :
1263 x > y ? 1 :
1264 -1;
1265 }
1266 virtual int64_t Evaluate(int64_t x, int64_t y) const {
1267 return
1268 x == y ? 0 :
1269 x > y ? 1 :
1270 -1;
1271 }
1272
Nicolas Geoffray412f10c2014-06-19 10:00:34 +01001273 DECLARE_INSTRUCTION(Compare);
1274
1275 private:
1276 DISALLOW_COPY_AND_ASSIGN(HCompare);
1277};
1278
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +00001279// A local in the graph. Corresponds to a Dex register.
1280class HLocal : public HTemplateInstruction<0> {
1281 public:
Nicolas Geoffray065bf772014-09-03 14:51:22 +01001282 explicit HLocal(uint16_t reg_number)
1283 : HTemplateInstruction(SideEffects::None()), reg_number_(reg_number) {}
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +00001284
Nicolas Geoffraya7062e02014-05-22 12:50:17 +01001285 DECLARE_INSTRUCTION(Local);
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +00001286
Nicolas Geoffray787c3072014-03-17 10:20:19 +00001287 uint16_t GetRegNumber() const { return reg_number_; }
Nicolas Geoffraybab4ed72014-03-11 17:53:17 +00001288
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +00001289 private:
Nicolas Geoffraybab4ed72014-03-11 17:53:17 +00001290 // The Dex register number.
1291 const uint16_t reg_number_;
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +00001292
1293 DISALLOW_COPY_AND_ASSIGN(HLocal);
1294};
1295
1296// Load a given local. The local is an input of this instruction.
Dave Allison20dfc792014-06-16 20:44:29 -07001297class HLoadLocal : public HExpression<1> {
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +00001298 public:
Roland Levillain5799fc02014-09-25 12:15:20 +01001299 HLoadLocal(HLocal* local, Primitive::Type type)
Nicolas Geoffray065bf772014-09-03 14:51:22 +01001300 : HExpression(type, SideEffects::None()) {
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +00001301 SetRawInputAt(0, local);
1302 }
1303
Nicolas Geoffraybab4ed72014-03-11 17:53:17 +00001304 HLocal* GetLocal() const { return reinterpret_cast<HLocal*>(InputAt(0)); }
1305
Nicolas Geoffraya7062e02014-05-22 12:50:17 +01001306 DECLARE_INSTRUCTION(LoadLocal);
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +00001307
1308 private:
1309 DISALLOW_COPY_AND_ASSIGN(HLoadLocal);
1310};
1311
1312// Store a value in a given local. This instruction has two inputs: the value
1313// and the local.
1314class HStoreLocal : public HTemplateInstruction<2> {
1315 public:
Nicolas Geoffray065bf772014-09-03 14:51:22 +01001316 HStoreLocal(HLocal* local, HInstruction* value) : HTemplateInstruction(SideEffects::None()) {
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +00001317 SetRawInputAt(0, local);
1318 SetRawInputAt(1, value);
1319 }
1320
Nicolas Geoffraybab4ed72014-03-11 17:53:17 +00001321 HLocal* GetLocal() const { return reinterpret_cast<HLocal*>(InputAt(0)); }
1322
Nicolas Geoffraya7062e02014-05-22 12:50:17 +01001323 DECLARE_INSTRUCTION(StoreLocal);
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +00001324
1325 private:
1326 DISALLOW_COPY_AND_ASSIGN(HStoreLocal);
1327};
1328
Nicolas Geoffray96f89a22014-07-11 10:57:49 +01001329class HConstant : public HExpression<0> {
1330 public:
Nicolas Geoffray065bf772014-09-03 14:51:22 +01001331 explicit HConstant(Primitive::Type type) : HExpression(type, SideEffects::None()) {}
1332
1333 virtual bool CanBeMoved() const { return true; }
Nicolas Geoffray96f89a22014-07-11 10:57:49 +01001334
1335 DECLARE_INSTRUCTION(Constant);
1336
1337 private:
1338 DISALLOW_COPY_AND_ASSIGN(HConstant);
1339};
1340
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +00001341// Constants of the type int. Those can be from Dex instructions, or
1342// synthesized (for example with the if-eqz instruction).
Nicolas Geoffray96f89a22014-07-11 10:57:49 +01001343class HIntConstant : public HConstant {
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +00001344 public:
Nicolas Geoffray96f89a22014-07-11 10:57:49 +01001345 explicit HIntConstant(int32_t value) : HConstant(Primitive::kPrimInt), value_(value) {}
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +00001346
Nicolas Geoffray787c3072014-03-17 10:20:19 +00001347 int32_t GetValue() const { return value_; }
Nicolas Geoffraybab4ed72014-03-11 17:53:17 +00001348
Nicolas Geoffray065bf772014-09-03 14:51:22 +01001349 virtual bool InstructionDataEquals(HInstruction* other) const {
1350 return other->AsIntConstant()->value_ == value_;
1351 }
1352
Nicolas Geoffrayd31cf3d2014-09-08 17:30:24 +01001353 virtual size_t ComputeHashCode() const { return GetValue(); }
1354
Nicolas Geoffraya7062e02014-05-22 12:50:17 +01001355 DECLARE_INSTRUCTION(IntConstant);
Nicolas Geoffray3ff386a2014-03-04 14:46:47 +00001356
1357 private:
1358 const int32_t value_;
1359
1360 DISALLOW_COPY_AND_ASSIGN(HIntConstant);
1361};
1362
Nicolas Geoffray96f89a22014-07-11 10:57:49 +01001363class HLongConstant : public HConstant {
Nicolas Geoffray01bc96d2014-04-11 17:43:50 +01001364 public:
Nicolas Geoffray96f89a22014-07-11 10:57:49 +01001365 explicit HLongConstant(int64_t value) : HConstant(Primitive::kPrimLong), value_(value) {}
Nicolas Geoffray01bc96d2014-04-11 17:43:50 +01001366
1367 int64_t GetValue() const { return value_; }
1368
Nicolas Geoffray065bf772014-09-03 14:51:22 +01001369 virtual bool InstructionDataEquals(HInstruction* other) const {
1370 return other->AsLongConstant()->value_ == value_;
1371 }
1372
Nicolas Geoffrayd31cf3d2014-09-08 17:30:24 +01001373 virtual size_t ComputeHashCode() const { return static_cast<size_t>(GetValue()); }
1374
Nicolas Geoffraya7062e02014-05-22 12:50:17 +01001375 DECLARE_INSTRUCTION(LongConstant);
Nicolas Geoffray01bc96d2014-04-11 17:43:50 +01001376
1377 private:
1378 const int64_t value_;
1379
1380 DISALLOW_COPY_AND_ASSIGN(HLongConstant);
1381};
1382
Nicolas Geoffray8ccc3f52014-03-19 10:34:11 +00001383class HInvoke : public HInstruction {
1384 public:
Nicolas Geoffray01bc96d2014-04-11 17:43:50 +01001385 HInvoke(ArenaAllocator* arena,
1386 uint32_t number_of_arguments,
1387 Primitive::Type return_type,
1388 uint32_t dex_pc)
Nicolas Geoffray065bf772014-09-03 14:51:22 +01001389 : HInstruction(SideEffects::All()),
1390 inputs_(arena, number_of_arguments),
Nicolas Geoffray01bc96d2014-04-11 17:43:50 +01001391 return_type_(return_type),
Nicolas Geoffray8ccc3f52014-03-19 10:34:11 +00001392 dex_pc_(dex_pc) {
1393 inputs_.SetSize(number_of_arguments);
1394 }
1395
Nicolas Geoffrayc32e7702014-04-24 12:43:16 +01001396 virtual size_t InputCount() const { return inputs_.Size(); }
1397 virtual HInstruction* InputAt(size_t i) const { return inputs_.Get(i); }
1398
1399 // Runtime needs to walk the stack, so Dex -> Dex calls need to
1400 // know their environment.
1401 virtual bool NeedsEnvironment() const { return true; }
Nicolas Geoffray8ccc3f52014-03-19 10:34:11 +00001402
Nicolas Geoffray4a34a422014-04-03 10:38:37 +01001403 void SetArgumentAt(size_t index, HInstruction* argument) {
Nicolas Geoffrayc32e7702014-04-24 12:43:16 +01001404 SetRawInputAt(index, argument);
1405 }
1406
1407 virtual void SetRawInputAt(size_t index, HInstruction* input) {
1408 inputs_.Put(index, input);
Nicolas Geoffray4a34a422014-04-03 10:38:37 +01001409 }
1410
Nicolas Geoffray01bc96d2014-04-11 17:43:50 +01001411 virtual Primitive::Type GetType() const { return return_type_; }
1412
Nicolas Geoffray2e7038a2014-04-03 18:49:58 +01001413 uint32_t GetDexPc() const { return dex_pc_; }
Nicolas Geoffray8ccc3f52014-03-19 10:34:11 +00001414
1415 protected:
1416 GrowableArray<HInstruction*> inputs_;
Nicolas Geoffray01bc96d2014-04-11 17:43:50 +01001417 const Primitive::Type return_type_;
Nicolas Geoffray2e7038a2014-04-03 18:49:58 +01001418 const uint32_t dex_pc_;
Nicolas Geoffray8ccc3f52014-03-19 10:34:11 +00001419
1420 private:
1421 DISALLOW_COPY_AND_ASSIGN(HInvoke);
1422};
1423
1424class HInvokeStatic : public HInvoke {
1425 public:
Nicolas Geoffray4a34a422014-04-03 10:38:37 +01001426 HInvokeStatic(ArenaAllocator* arena,
1427 uint32_t number_of_arguments,
Nicolas Geoffray01bc96d2014-04-11 17:43:50 +01001428 Primitive::Type return_type,
Nicolas Geoffray2e7038a2014-04-03 18:49:58 +01001429 uint32_t dex_pc,
1430 uint32_t index_in_dex_cache)
Nicolas Geoffray01bc96d2014-04-11 17:43:50 +01001431 : HInvoke(arena, number_of_arguments, return_type, dex_pc),
1432 index_in_dex_cache_(index_in_dex_cache) {}
Nicolas Geoffray8ccc3f52014-03-19 10:34:11 +00001433
1434 uint32_t GetIndexInDexCache() const { return index_in_dex_cache_; }
1435
Nicolas Geoffraya7062e02014-05-22 12:50:17 +01001436 DECLARE_INSTRUCTION(InvokeStatic);
Nicolas Geoffray8ccc3f52014-03-19 10:34:11 +00001437
1438 private:
Nicolas Geoffray4a34a422014-04-03 10:38:37 +01001439 const uint32_t index_in_dex_cache_;
Nicolas Geoffray8ccc3f52014-03-19 10:34:11 +00001440
1441 DISALLOW_COPY_AND_ASSIGN(HInvokeStatic);
1442};
1443
Nicolas Geoffraye982f0b2014-08-13 02:11:24 +01001444class HInvokeVirtual : public HInvoke {
1445 public:
1446 HInvokeVirtual(ArenaAllocator* arena,
1447 uint32_t number_of_arguments,
1448 Primitive::Type return_type,
1449 uint32_t dex_pc,
1450 uint32_t vtable_index)
1451 : HInvoke(arena, number_of_arguments, return_type, dex_pc),
1452 vtable_index_(vtable_index) {}
1453
1454 uint32_t GetVTableIndex() const { return vtable_index_; }
1455
1456 DECLARE_INSTRUCTION(InvokeVirtual);
1457
1458 private:
1459 const uint32_t vtable_index_;
1460
1461 DISALLOW_COPY_AND_ASSIGN(HInvokeVirtual);
1462};
1463
Dave Allison20dfc792014-06-16 20:44:29 -07001464class HNewInstance : public HExpression<0> {
Nicolas Geoffray2e7038a2014-04-03 18:49:58 +01001465 public:
Nicolas Geoffray065bf772014-09-03 14:51:22 +01001466 HNewInstance(uint32_t dex_pc, uint16_t type_index)
1467 : HExpression(Primitive::kPrimNot, SideEffects::None()),
1468 dex_pc_(dex_pc),
1469 type_index_(type_index) {}
Nicolas Geoffray2e7038a2014-04-03 18:49:58 +01001470
1471 uint32_t GetDexPc() const { return dex_pc_; }
1472 uint16_t GetTypeIndex() const { return type_index_; }
1473
Nicolas Geoffrayc32e7702014-04-24 12:43:16 +01001474 // Calls runtime so needs an environment.
1475 virtual bool NeedsEnvironment() const { return true; }
1476
Nicolas Geoffraya7062e02014-05-22 12:50:17 +01001477 DECLARE_INSTRUCTION(NewInstance);
Nicolas Geoffray2e7038a2014-04-03 18:49:58 +01001478
1479 private:
1480 const uint32_t dex_pc_;
1481 const uint16_t type_index_;
1482
1483 DISALLOW_COPY_AND_ASSIGN(HNewInstance);
1484};
1485
Nicolas Geoffrayd8ee7372014-03-28 15:43:40 +00001486class HAdd : public HBinaryOperation {
1487 public:
1488 HAdd(Primitive::Type result_type, HInstruction* left, HInstruction* right)
1489 : HBinaryOperation(result_type, left, right) {}
1490
1491 virtual bool IsCommutative() { return true; }
1492
Roland Levillain556c3d12014-09-18 15:25:07 +01001493 virtual int32_t Evaluate(int32_t x, int32_t y) const { return x + y; }
1494 virtual int64_t Evaluate(int64_t x, int64_t y) const { return x + y; }
1495
Nicolas Geoffrayd8ee7372014-03-28 15:43:40 +00001496 DECLARE_INSTRUCTION(Add);
1497
1498 private:
1499 DISALLOW_COPY_AND_ASSIGN(HAdd);
1500};
1501
Nicolas Geoffrayf583e592014-04-07 13:20:42 +01001502class HSub : public HBinaryOperation {
1503 public:
1504 HSub(Primitive::Type result_type, HInstruction* left, HInstruction* right)
1505 : HBinaryOperation(result_type, left, right) {}
1506
1507 virtual bool IsCommutative() { return false; }
1508
Roland Levillain556c3d12014-09-18 15:25:07 +01001509 virtual int32_t Evaluate(int32_t x, int32_t y) const { return x + y; }
1510 virtual int64_t Evaluate(int64_t x, int64_t y) const { return x + y; }
1511
Nicolas Geoffrayf583e592014-04-07 13:20:42 +01001512 DECLARE_INSTRUCTION(Sub);
1513
1514 private:
1515 DISALLOW_COPY_AND_ASSIGN(HSub);
1516};
1517
1518// The value of a parameter in this method. Its location depends on
1519// the calling convention.
Dave Allison20dfc792014-06-16 20:44:29 -07001520class HParameterValue : public HExpression<0> {
Nicolas Geoffrayf583e592014-04-07 13:20:42 +01001521 public:
Nicolas Geoffray01bc96d2014-04-11 17:43:50 +01001522 HParameterValue(uint8_t index, Primitive::Type parameter_type)
Nicolas Geoffray065bf772014-09-03 14:51:22 +01001523 : HExpression(parameter_type, SideEffects::None()), index_(index) {}
Nicolas Geoffrayf583e592014-04-07 13:20:42 +01001524
1525 uint8_t GetIndex() const { return index_; }
1526
1527 DECLARE_INSTRUCTION(ParameterValue);
1528
1529 private:
1530 // The index of this parameter in the parameters list. Must be less
1531 // than HGraph::number_of_in_vregs_;
1532 const uint8_t index_;
1533
1534 DISALLOW_COPY_AND_ASSIGN(HParameterValue);
1535};
1536
Dave Allison20dfc792014-06-16 20:44:29 -07001537class HNot : public HExpression<1> {
Nicolas Geoffrayb55f8352014-04-07 15:26:35 +01001538 public:
Nicolas Geoffray065bf772014-09-03 14:51:22 +01001539 explicit HNot(HInstruction* input) : HExpression(Primitive::kPrimBoolean, SideEffects::None()) {
Nicolas Geoffrayb55f8352014-04-07 15:26:35 +01001540 SetRawInputAt(0, input);
1541 }
1542
Nicolas Geoffray065bf772014-09-03 14:51:22 +01001543 virtual bool CanBeMoved() const { return true; }
1544 virtual bool InstructionDataEquals(HInstruction* other) const { return true; }
1545
Nicolas Geoffrayb55f8352014-04-07 15:26:35 +01001546 DECLARE_INSTRUCTION(Not);
1547
1548 private:
1549 DISALLOW_COPY_AND_ASSIGN(HNot);
1550};
1551
Nicolas Geoffrayc32e7702014-04-24 12:43:16 +01001552class HPhi : public HInstruction {
1553 public:
1554 HPhi(ArenaAllocator* arena, uint32_t reg_number, size_t number_of_inputs, Primitive::Type type)
Nicolas Geoffray065bf772014-09-03 14:51:22 +01001555 : HInstruction(SideEffects::None()),
1556 inputs_(arena, number_of_inputs),
Nicolas Geoffrayc32e7702014-04-24 12:43:16 +01001557 reg_number_(reg_number),
Nicolas Geoffray7dc206a2014-07-11 09:49:49 +01001558 type_(type),
1559 is_live_(false) {
Nicolas Geoffrayc32e7702014-04-24 12:43:16 +01001560 inputs_.SetSize(number_of_inputs);
1561 }
1562
1563 virtual size_t InputCount() const { return inputs_.Size(); }
1564 virtual HInstruction* InputAt(size_t i) const { return inputs_.Get(i); }
1565
1566 virtual void SetRawInputAt(size_t index, HInstruction* input) {
1567 inputs_.Put(index, input);
1568 }
1569
1570 void AddInput(HInstruction* input);
1571
1572 virtual Primitive::Type GetType() const { return type_; }
Nicolas Geoffraya7062e02014-05-22 12:50:17 +01001573 void SetType(Primitive::Type type) { type_ = type; }
Nicolas Geoffrayc32e7702014-04-24 12:43:16 +01001574
1575 uint32_t GetRegNumber() const { return reg_number_; }
1576
Nicolas Geoffray7dc206a2014-07-11 09:49:49 +01001577 void SetDead() { is_live_ = false; }
1578 void SetLive() { is_live_ = true; }
1579 bool IsDead() const { return !is_live_; }
1580 bool IsLive() const { return is_live_; }
1581
Nicolas Geoffraya7062e02014-05-22 12:50:17 +01001582 DECLARE_INSTRUCTION(Phi);
Nicolas Geoffrayc32e7702014-04-24 12:43:16 +01001583
Nicolas Geoffray96f89a22014-07-11 10:57:49 +01001584 private:
Nicolas Geoffrayc32e7702014-04-24 12:43:16 +01001585 GrowableArray<HInstruction*> inputs_;
1586 const uint32_t reg_number_;
Nicolas Geoffraya7062e02014-05-22 12:50:17 +01001587 Primitive::Type type_;
Nicolas Geoffray7dc206a2014-07-11 09:49:49 +01001588 bool is_live_;
Nicolas Geoffrayc32e7702014-04-24 12:43:16 +01001589
Nicolas Geoffrayc32e7702014-04-24 12:43:16 +01001590 DISALLOW_COPY_AND_ASSIGN(HPhi);
1591};
1592
Nicolas Geoffraye5038322014-07-04 09:41:32 +01001593class HNullCheck : public HExpression<1> {
1594 public:
1595 HNullCheck(HInstruction* value, uint32_t dex_pc)
Nicolas Geoffray065bf772014-09-03 14:51:22 +01001596 : HExpression(value->GetType(), SideEffects::None()), dex_pc_(dex_pc) {
Nicolas Geoffraye5038322014-07-04 09:41:32 +01001597 SetRawInputAt(0, value);
1598 }
1599
Nicolas Geoffray065bf772014-09-03 14:51:22 +01001600 virtual bool CanBeMoved() const { return true; }
1601 virtual bool InstructionDataEquals(HInstruction* other) const { return true; }
1602
Nicolas Geoffraye5038322014-07-04 09:41:32 +01001603 virtual bool NeedsEnvironment() const { return true; }
1604
1605 uint32_t GetDexPc() const { return dex_pc_; }
1606
1607 DECLARE_INSTRUCTION(NullCheck);
1608
1609 private:
1610 const uint32_t dex_pc_;
1611
1612 DISALLOW_COPY_AND_ASSIGN(HNullCheck);
1613};
1614
1615class FieldInfo : public ValueObject {
1616 public:
Roland Levillain5799fc02014-09-25 12:15:20 +01001617 FieldInfo(MemberOffset field_offset, Primitive::Type field_type)
Nicolas Geoffray39468442014-09-02 15:17:15 +01001618 : field_offset_(field_offset), field_type_(field_type) {}
Nicolas Geoffraye5038322014-07-04 09:41:32 +01001619
1620 MemberOffset GetFieldOffset() const { return field_offset_; }
Nicolas Geoffray39468442014-09-02 15:17:15 +01001621 Primitive::Type GetFieldType() const { return field_type_; }
Nicolas Geoffraye5038322014-07-04 09:41:32 +01001622
1623 private:
1624 const MemberOffset field_offset_;
Nicolas Geoffray39468442014-09-02 15:17:15 +01001625 const Primitive::Type field_type_;
Nicolas Geoffraye5038322014-07-04 09:41:32 +01001626};
1627
1628class HInstanceFieldGet : public HExpression<1> {
1629 public:
1630 HInstanceFieldGet(HInstruction* value,
1631 Primitive::Type field_type,
1632 MemberOffset field_offset)
Nicolas Geoffray065bf772014-09-03 14:51:22 +01001633 : HExpression(field_type, SideEffects::DependsOnSomething()),
1634 field_info_(field_offset, field_type) {
Nicolas Geoffraye5038322014-07-04 09:41:32 +01001635 SetRawInputAt(0, value);
1636 }
1637
Nicolas Geoffray065bf772014-09-03 14:51:22 +01001638 virtual bool CanBeMoved() const { return true; }
1639 virtual bool InstructionDataEquals(HInstruction* other) const {
1640 size_t other_offset = other->AsInstanceFieldGet()->GetFieldOffset().SizeValue();
1641 return other_offset == GetFieldOffset().SizeValue();
1642 }
1643
Nicolas Geoffrayd31cf3d2014-09-08 17:30:24 +01001644 virtual size_t ComputeHashCode() const {
1645 return (HInstruction::ComputeHashCode() << 7) | GetFieldOffset().SizeValue();
1646 }
1647
Nicolas Geoffraye5038322014-07-04 09:41:32 +01001648 MemberOffset GetFieldOffset() const { return field_info_.GetFieldOffset(); }
Nicolas Geoffray39468442014-09-02 15:17:15 +01001649 Primitive::Type GetFieldType() const { return field_info_.GetFieldType(); }
Nicolas Geoffraye5038322014-07-04 09:41:32 +01001650
1651 DECLARE_INSTRUCTION(InstanceFieldGet);
1652
1653 private:
1654 const FieldInfo field_info_;
1655
1656 DISALLOW_COPY_AND_ASSIGN(HInstanceFieldGet);
1657};
1658
1659class HInstanceFieldSet : public HTemplateInstruction<2> {
1660 public:
1661 HInstanceFieldSet(HInstruction* object,
1662 HInstruction* value,
Nicolas Geoffray39468442014-09-02 15:17:15 +01001663 Primitive::Type field_type,
Nicolas Geoffraye5038322014-07-04 09:41:32 +01001664 MemberOffset field_offset)
Nicolas Geoffray065bf772014-09-03 14:51:22 +01001665 : HTemplateInstruction(SideEffects::ChangesSomething()),
1666 field_info_(field_offset, field_type) {
Nicolas Geoffraye5038322014-07-04 09:41:32 +01001667 SetRawInputAt(0, object);
1668 SetRawInputAt(1, value);
1669 }
1670
1671 MemberOffset GetFieldOffset() const { return field_info_.GetFieldOffset(); }
Nicolas Geoffray39468442014-09-02 15:17:15 +01001672 Primitive::Type GetFieldType() const { return field_info_.GetFieldType(); }
Nicolas Geoffraye5038322014-07-04 09:41:32 +01001673
1674 DECLARE_INSTRUCTION(InstanceFieldSet);
1675
1676 private:
1677 const FieldInfo field_info_;
1678
1679 DISALLOW_COPY_AND_ASSIGN(HInstanceFieldSet);
1680};
1681
Nicolas Geoffray3c7bb982014-07-23 16:04:16 +01001682class HArrayGet : public HExpression<2> {
1683 public:
1684 HArrayGet(HInstruction* array, HInstruction* index, Primitive::Type type)
Nicolas Geoffray065bf772014-09-03 14:51:22 +01001685 : HExpression(type, SideEffects::DependsOnSomething()) {
Nicolas Geoffray3c7bb982014-07-23 16:04:16 +01001686 SetRawInputAt(0, array);
1687 SetRawInputAt(1, index);
1688 }
1689
Nicolas Geoffray065bf772014-09-03 14:51:22 +01001690 virtual bool CanBeMoved() const { return true; }
1691 virtual bool InstructionDataEquals(HInstruction* other) const { return true; }
1692
Nicolas Geoffray3c7bb982014-07-23 16:04:16 +01001693 DECLARE_INSTRUCTION(ArrayGet);
1694
1695 private:
1696 DISALLOW_COPY_AND_ASSIGN(HArrayGet);
1697};
1698
1699class HArraySet : public HTemplateInstruction<3> {
1700 public:
1701 HArraySet(HInstruction* array,
1702 HInstruction* index,
1703 HInstruction* value,
Nicolas Geoffray39468442014-09-02 15:17:15 +01001704 Primitive::Type component_type,
Nicolas Geoffray065bf772014-09-03 14:51:22 +01001705 uint32_t dex_pc)
1706 : HTemplateInstruction(SideEffects::ChangesSomething()),
1707 dex_pc_(dex_pc),
1708 component_type_(component_type) {
Nicolas Geoffray3c7bb982014-07-23 16:04:16 +01001709 SetRawInputAt(0, array);
1710 SetRawInputAt(1, index);
1711 SetRawInputAt(2, value);
1712 }
1713
1714 virtual bool NeedsEnvironment() const {
1715 // We currently always call a runtime method to catch array store
1716 // exceptions.
1717 return InputAt(2)->GetType() == Primitive::kPrimNot;
1718 }
1719
1720 uint32_t GetDexPc() const { return dex_pc_; }
1721
Nicolas Geoffray39468442014-09-02 15:17:15 +01001722 Primitive::Type GetComponentType() const { return component_type_; }
1723
Nicolas Geoffray3c7bb982014-07-23 16:04:16 +01001724 DECLARE_INSTRUCTION(ArraySet);
1725
1726 private:
1727 const uint32_t dex_pc_;
Nicolas Geoffray39468442014-09-02 15:17:15 +01001728 const Primitive::Type component_type_;
Nicolas Geoffray3c7bb982014-07-23 16:04:16 +01001729
1730 DISALLOW_COPY_AND_ASSIGN(HArraySet);
1731};
1732
1733class HArrayLength : public HExpression<1> {
1734 public:
Nicolas Geoffray065bf772014-09-03 14:51:22 +01001735 explicit HArrayLength(HInstruction* array)
1736 : HExpression(Primitive::kPrimInt, SideEffects::None()) {
1737 // Note that arrays do not change length, so the instruction does not
1738 // depend on any write.
Nicolas Geoffray3c7bb982014-07-23 16:04:16 +01001739 SetRawInputAt(0, array);
1740 }
1741
Nicolas Geoffray065bf772014-09-03 14:51:22 +01001742 virtual bool CanBeMoved() const { return true; }
1743 virtual bool InstructionDataEquals(HInstruction* other) const { return true; }
1744
Nicolas Geoffray3c7bb982014-07-23 16:04:16 +01001745 DECLARE_INSTRUCTION(ArrayLength);
1746
1747 private:
1748 DISALLOW_COPY_AND_ASSIGN(HArrayLength);
1749};
1750
1751class HBoundsCheck : public HExpression<2> {
1752 public:
1753 HBoundsCheck(HInstruction* index, HInstruction* length, uint32_t dex_pc)
Nicolas Geoffray065bf772014-09-03 14:51:22 +01001754 : HExpression(index->GetType(), SideEffects::None()), dex_pc_(dex_pc) {
Nicolas Geoffray3c7bb982014-07-23 16:04:16 +01001755 DCHECK(index->GetType() == Primitive::kPrimInt);
1756 SetRawInputAt(0, index);
1757 SetRawInputAt(1, length);
1758 }
1759
Nicolas Geoffray065bf772014-09-03 14:51:22 +01001760 virtual bool CanBeMoved() const { return true; }
1761 virtual bool InstructionDataEquals(HInstruction* other) const { return true; }
1762
Nicolas Geoffray3c7bb982014-07-23 16:04:16 +01001763 virtual bool NeedsEnvironment() const { return true; }
1764
1765 uint32_t GetDexPc() const { return dex_pc_; }
1766
1767 DECLARE_INSTRUCTION(BoundsCheck);
1768
1769 private:
1770 const uint32_t dex_pc_;
1771
1772 DISALLOW_COPY_AND_ASSIGN(HBoundsCheck);
1773};
1774
Nicolas Geoffraye5038322014-07-04 09:41:32 +01001775/**
1776 * Some DEX instructions are folded into multiple HInstructions that need
1777 * to stay live until the last HInstruction. This class
1778 * is used as a marker for the baseline compiler to ensure its preceding
1779 * HInstruction stays live. `index` is the temporary number that is used
1780 * for knowing the stack offset where to store the instruction.
1781 */
1782class HTemporary : public HTemplateInstruction<0> {
1783 public:
Nicolas Geoffray065bf772014-09-03 14:51:22 +01001784 explicit HTemporary(size_t index) : HTemplateInstruction(SideEffects::None()), index_(index) {}
Nicolas Geoffraye5038322014-07-04 09:41:32 +01001785
1786 size_t GetIndex() const { return index_; }
1787
1788 DECLARE_INSTRUCTION(Temporary);
1789
1790 private:
1791 const size_t index_;
1792
1793 DISALLOW_COPY_AND_ASSIGN(HTemporary);
1794};
1795
Nicolas Geoffrayfbc695f2014-09-15 15:33:30 +00001796class HSuspendCheck : public HTemplateInstruction<0> {
1797 public:
1798 explicit HSuspendCheck(uint32_t dex_pc)
Nicolas Geoffray9ebc72c2014-09-25 16:33:42 +01001799 : HTemplateInstruction(SideEffects::None()), dex_pc_(dex_pc) {}
Nicolas Geoffrayfbc695f2014-09-15 15:33:30 +00001800
1801 virtual bool NeedsEnvironment() const {
1802 return true;
1803 }
1804
1805 uint32_t GetDexPc() const { return dex_pc_; }
1806
1807 DECLARE_INSTRUCTION(SuspendCheck);
1808
1809 private:
1810 const uint32_t dex_pc_;
1811
1812 DISALLOW_COPY_AND_ASSIGN(HSuspendCheck);
1813};
1814
Nicolas Geoffray4e3d23a2014-05-22 18:32:45 +01001815class MoveOperands : public ArenaObject {
1816 public:
1817 MoveOperands(Location source, Location destination)
1818 : source_(source), destination_(destination) {}
1819
1820 Location GetSource() const { return source_; }
1821 Location GetDestination() const { return destination_; }
1822
1823 void SetSource(Location value) { source_ = value; }
1824 void SetDestination(Location value) { destination_ = value; }
1825
1826 // The parallel move resolver marks moves as "in-progress" by clearing the
1827 // destination (but not the source).
1828 Location MarkPending() {
1829 DCHECK(!IsPending());
1830 Location dest = destination_;
1831 destination_ = Location::NoLocation();
1832 return dest;
1833 }
1834
1835 void ClearPending(Location dest) {
1836 DCHECK(IsPending());
1837 destination_ = dest;
1838 }
1839
1840 bool IsPending() const {
1841 DCHECK(!source_.IsInvalid() || destination_.IsInvalid());
1842 return destination_.IsInvalid() && !source_.IsInvalid();
1843 }
1844
1845 // True if this blocks a move from the given location.
1846 bool Blocks(Location loc) const {
1847 return !IsEliminated() && source_.Equals(loc);
1848 }
1849
1850 // A move is redundant if it's been eliminated, if its source and
1851 // destination are the same, or if its destination is unneeded.
1852 bool IsRedundant() const {
1853 return IsEliminated() || destination_.IsInvalid() || source_.Equals(destination_);
1854 }
1855
1856 // We clear both operands to indicate move that's been eliminated.
1857 void Eliminate() {
1858 source_ = destination_ = Location::NoLocation();
1859 }
1860
1861 bool IsEliminated() const {
1862 DCHECK(!source_.IsInvalid() || destination_.IsInvalid());
1863 return source_.IsInvalid();
1864 }
1865
1866 private:
1867 Location source_;
1868 Location destination_;
1869
1870 DISALLOW_COPY_AND_ASSIGN(MoveOperands);
1871};
1872
1873static constexpr size_t kDefaultNumberOfMoves = 4;
1874
1875class HParallelMove : public HTemplateInstruction<0> {
1876 public:
Nicolas Geoffray065bf772014-09-03 14:51:22 +01001877 explicit HParallelMove(ArenaAllocator* arena)
1878 : HTemplateInstruction(SideEffects::None()), moves_(arena, kDefaultNumberOfMoves) {}
Nicolas Geoffray4e3d23a2014-05-22 18:32:45 +01001879
1880 void AddMove(MoveOperands* move) {
1881 moves_.Add(move);
1882 }
1883
1884 MoveOperands* MoveOperandsAt(size_t index) const {
1885 return moves_.Get(index);
1886 }
1887
1888 size_t NumMoves() const { return moves_.Size(); }
1889
Nicolas Geoffraya7062e02014-05-22 12:50:17 +01001890 DECLARE_INSTRUCTION(ParallelMove);
Nicolas Geoffray4e3d23a2014-05-22 18:32:45 +01001891
1892 private:
1893 GrowableArray<MoveOperands*> moves_;
1894
1895 DISALLOW_COPY_AND_ASSIGN(HParallelMove);
1896};
1897
Nicolas Geoffray818f2102014-02-18 16:43:35 +00001898class HGraphVisitor : public ValueObject {
1899 public:
Dave Allison20dfc792014-06-16 20:44:29 -07001900 explicit HGraphVisitor(HGraph* graph) : graph_(graph) {}
1901 virtual ~HGraphVisitor() {}
Nicolas Geoffray818f2102014-02-18 16:43:35 +00001902
Dave Allison20dfc792014-06-16 20:44:29 -07001903 virtual void VisitInstruction(HInstruction* instruction) {}
Nicolas Geoffray818f2102014-02-18 16:43:35 +00001904 virtual void VisitBasicBlock(HBasicBlock* block);
1905
1906 void VisitInsertionOrder();
1907
Nicolas Geoffray787c3072014-03-17 10:20:19 +00001908 HGraph* GetGraph() const { return graph_; }
Nicolas Geoffrayd4dd2552014-02-28 10:23:58 +00001909
Nicolas Geoffray818f2102014-02-18 16:43:35 +00001910 // Visit functions for instruction classes.
1911#define DECLARE_VISIT_INSTRUCTION(name) \
1912 virtual void Visit##name(H##name* instr) { VisitInstruction(instr); }
1913
1914 FOR_EACH_INSTRUCTION(DECLARE_VISIT_INSTRUCTION)
1915
1916#undef DECLARE_VISIT_INSTRUCTION
1917
1918 private:
1919 HGraph* graph_;
1920
1921 DISALLOW_COPY_AND_ASSIGN(HGraphVisitor);
1922};
1923
Nicolas Geoffray804d0932014-05-02 08:46:00 +01001924class HInsertionOrderIterator : public ValueObject {
1925 public:
1926 explicit HInsertionOrderIterator(const HGraph& graph) : graph_(graph), index_(0) {}
1927
1928 bool Done() const { return index_ == graph_.GetBlocks().Size(); }
1929 HBasicBlock* Current() const { return graph_.GetBlocks().Get(index_); }
1930 void Advance() { ++index_; }
1931
1932 private:
1933 const HGraph& graph_;
1934 size_t index_;
1935
1936 DISALLOW_COPY_AND_ASSIGN(HInsertionOrderIterator);
1937};
1938
Nicolas Geoffray622d9c32014-05-12 16:11:02 +01001939class HReversePostOrderIterator : public ValueObject {
Nicolas Geoffray804d0932014-05-02 08:46:00 +01001940 public:
Nicolas Geoffray622d9c32014-05-12 16:11:02 +01001941 explicit HReversePostOrderIterator(const HGraph& graph) : graph_(graph), index_(0) {}
Nicolas Geoffray804d0932014-05-02 08:46:00 +01001942
Nicolas Geoffray622d9c32014-05-12 16:11:02 +01001943 bool Done() const { return index_ == graph_.GetReversePostOrder().Size(); }
1944 HBasicBlock* Current() const { return graph_.GetReversePostOrder().Get(index_); }
Nicolas Geoffray804d0932014-05-02 08:46:00 +01001945 void Advance() { ++index_; }
1946
1947 private:
1948 const HGraph& graph_;
1949 size_t index_;
1950
Nicolas Geoffray622d9c32014-05-12 16:11:02 +01001951 DISALLOW_COPY_AND_ASSIGN(HReversePostOrderIterator);
Nicolas Geoffray804d0932014-05-02 08:46:00 +01001952};
1953
Nicolas Geoffray622d9c32014-05-12 16:11:02 +01001954class HPostOrderIterator : public ValueObject {
Nicolas Geoffray804d0932014-05-02 08:46:00 +01001955 public:
Nicolas Geoffray622d9c32014-05-12 16:11:02 +01001956 explicit HPostOrderIterator(const HGraph& graph)
1957 : graph_(graph), index_(graph_.GetReversePostOrder().Size()) {}
Nicolas Geoffray804d0932014-05-02 08:46:00 +01001958
1959 bool Done() const { return index_ == 0; }
Nicolas Geoffray622d9c32014-05-12 16:11:02 +01001960 HBasicBlock* Current() const { return graph_.GetReversePostOrder().Get(index_ - 1); }
Nicolas Geoffray804d0932014-05-02 08:46:00 +01001961 void Advance() { --index_; }
1962
1963 private:
1964 const HGraph& graph_;
1965 size_t index_;
1966
Nicolas Geoffray622d9c32014-05-12 16:11:02 +01001967 DISALLOW_COPY_AND_ASSIGN(HPostOrderIterator);
Nicolas Geoffray804d0932014-05-02 08:46:00 +01001968};
1969
Nicolas Geoffray818f2102014-02-18 16:43:35 +00001970} // namespace art
1971
1972#endif // ART_COMPILER_OPTIMIZING_NODES_H_