nodes.h revision ddb7df25af45d7cd19ed1138e537973735cc78a5 
1/*
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 "locations.h"
21#include "offsets.h"
22#include "primitive.h"
23#include "utils/arena_object.h"
24#include "utils/arena_bit_vector.h"
25#include "utils/growable_array.h"
26
27namespace art {
28
29class HBasicBlock;
30class HEnvironment;
31class HInstruction;
32class HIntConstant;
33class HGraphVisitor;
34class HPhi;
35class HSuspendCheck;
36class LiveInterval;
37class LocationSummary;
38
39static const int kDefaultNumberOfBlocks = 8;
40static const int kDefaultNumberOfSuccessors = 2;
41static const int kDefaultNumberOfPredecessors = 2;
42static const int kDefaultNumberOfDominatedBlocks = 1;
43static const int kDefaultNumberOfBackEdges = 1;
44
45static constexpr uint32_t kMaxIntShiftValue = 0x1f;
46static constexpr uint64_t kMaxLongShiftValue = 0x3f;
47
48enum IfCondition {
49  kCondEQ,
50  kCondNE,
51  kCondLT,
52  kCondLE,
53  kCondGT,
54  kCondGE,
55};
56
57class HInstructionList {
58 public:
59  HInstructionList() : first_instruction_(nullptr), last_instruction_(nullptr) {}
60
61  void AddInstruction(HInstruction* instruction);
62  void RemoveInstruction(HInstruction* instruction);
63
64  // Return true if this list contains `instruction`.
65  bool Contains(HInstruction* instruction) const;
66
67  // Return true if `instruction1` is found before `instruction2` in
68  // this instruction list and false otherwise.  Abort if none
69  // of these instructions is found.
70  bool FoundBefore(const HInstruction* instruction1,
71                   const HInstruction* instruction2) const;
72
73 private:
74  HInstruction* first_instruction_;
75  HInstruction* last_instruction_;
76
77  friend class HBasicBlock;
78  friend class HInstructionIterator;
79  friend class HBackwardInstructionIterator;
80
81  DISALLOW_COPY_AND_ASSIGN(HInstructionList);
82};
83
84// Control-flow graph of a method. Contains a list of basic blocks.
85class HGraph : public ArenaObject<kArenaAllocMisc> {
86 public:
87  explicit HGraph(ArenaAllocator* arena)
88      : arena_(arena),
89        blocks_(arena, kDefaultNumberOfBlocks),
90        reverse_post_order_(arena, kDefaultNumberOfBlocks),
91        entry_block_(nullptr),
92        exit_block_(nullptr),
93        maximum_number_of_out_vregs_(0),
94        number_of_vregs_(0),
95        number_of_in_vregs_(0),
96        temporaries_vreg_slots_(0),
97        current_instruction_id_(0) {}
98
99  ArenaAllocator* GetArena() const { return arena_; }
100  const GrowableArray<HBasicBlock*>& GetBlocks() const { return blocks_; }
101  HBasicBlock* GetBlock(size_t id) const { return blocks_.Get(id); }
102
103  HBasicBlock* GetEntryBlock() const { return entry_block_; }
104  HBasicBlock* GetExitBlock() const { return exit_block_; }
105
106  void SetEntryBlock(HBasicBlock* block) { entry_block_ = block; }
107  void SetExitBlock(HBasicBlock* block) { exit_block_ = block; }
108
109  void AddBlock(HBasicBlock* block);
110
111  void BuildDominatorTree();
112  void TransformToSSA();
113  void SimplifyCFG();
114
115  // Find all natural loops in this graph. Aborts computation and returns false
116  // if one loop is not natural, that is the header does not dominate the back
117  // edge.
118  bool FindNaturalLoops() const;
119
120  void SplitCriticalEdge(HBasicBlock* block, HBasicBlock* successor);
121  void SimplifyLoop(HBasicBlock* header);
122
123  int GetNextInstructionId() {
124    return current_instruction_id_++;
125  }
126
127  uint16_t GetMaximumNumberOfOutVRegs() const {
128    return maximum_number_of_out_vregs_;
129  }
130
131  void UpdateMaximumNumberOfOutVRegs(uint16_t new_value) {
132    maximum_number_of_out_vregs_ = std::max(new_value, maximum_number_of_out_vregs_);
133  }
134
135  void UpdateTemporariesVRegSlots(size_t slots) {
136    temporaries_vreg_slots_ = std::max(slots, temporaries_vreg_slots_);
137  }
138
139  size_t GetTemporariesVRegSlots() const {
140    return temporaries_vreg_slots_;
141  }
142
143  void SetNumberOfVRegs(uint16_t number_of_vregs) {
144    number_of_vregs_ = number_of_vregs;
145  }
146
147  uint16_t GetNumberOfVRegs() const {
148    return number_of_vregs_;
149  }
150
151  void SetNumberOfInVRegs(uint16_t value) {
152    number_of_in_vregs_ = value;
153  }
154
155  uint16_t GetNumberOfInVRegs() const {
156    return number_of_in_vregs_;
157  }
158
159  uint16_t GetNumberOfLocalVRegs() const {
160    return number_of_vregs_ - number_of_in_vregs_;
161  }
162
163  const GrowableArray<HBasicBlock*>& GetReversePostOrder() const {
164    return reverse_post_order_;
165  }
166
167 private:
168  HBasicBlock* FindCommonDominator(HBasicBlock* first, HBasicBlock* second) const;
169  void VisitBlockForDominatorTree(HBasicBlock* block,
170                                  HBasicBlock* predecessor,
171                                  GrowableArray<size_t>* visits);
172  void FindBackEdges(ArenaBitVector* visited);
173  void VisitBlockForBackEdges(HBasicBlock* block,
174                              ArenaBitVector* visited,
175                              ArenaBitVector* visiting);
176  void RemoveDeadBlocks(const ArenaBitVector& visited) const;
177
178  ArenaAllocator* const arena_;
179
180  // List of blocks in insertion order.
181  GrowableArray<HBasicBlock*> blocks_;
182
183  // List of blocks to perform a reverse post order tree traversal.
184  GrowableArray<HBasicBlock*> reverse_post_order_;
185
186  HBasicBlock* entry_block_;
187  HBasicBlock* exit_block_;
188
189  // The maximum number of virtual registers arguments passed to a HInvoke in this graph.
190  uint16_t maximum_number_of_out_vregs_;
191
192  // The number of virtual registers in this method. Contains the parameters.
193  uint16_t number_of_vregs_;
194
195  // The number of virtual registers used by parameters of this method.
196  uint16_t number_of_in_vregs_;
197
198  // Number of vreg size slots that the temporaries use (used in baseline compiler).
199  size_t temporaries_vreg_slots_;
200
201  // The current id to assign to a newly added instruction. See HInstruction.id_.
202  int current_instruction_id_;
203
204  DISALLOW_COPY_AND_ASSIGN(HGraph);
205};
206
207class HLoopInformation : public ArenaObject<kArenaAllocMisc> {
208 public:
209  HLoopInformation(HBasicBlock* header, HGraph* graph)
210      : header_(header),
211        suspend_check_(nullptr),
212        back_edges_(graph->GetArena(), kDefaultNumberOfBackEdges),
213        // Make bit vector growable, as the number of blocks may change.
214        blocks_(graph->GetArena(), graph->GetBlocks().Size(), true) {}
215
216  HBasicBlock* GetHeader() const {
217    return header_;
218  }
219
220  HSuspendCheck* GetSuspendCheck() const { return suspend_check_; }
221  void SetSuspendCheck(HSuspendCheck* check) { suspend_check_ = check; }
222  bool HasSuspendCheck() const { return suspend_check_ != nullptr; }
223
224  void AddBackEdge(HBasicBlock* back_edge) {
225    back_edges_.Add(back_edge);
226  }
227
228  void RemoveBackEdge(HBasicBlock* back_edge) {
229    back_edges_.Delete(back_edge);
230  }
231
232  bool IsBackEdge(HBasicBlock* block) {
233    for (size_t i = 0, e = back_edges_.Size(); i < e; ++i) {
234      if (back_edges_.Get(i) == block) return true;
235    }
236    return false;
237  }
238
239  size_t NumberOfBackEdges() const {
240    return back_edges_.Size();
241  }
242
243  HBasicBlock* GetPreHeader() const;
244
245  const GrowableArray<HBasicBlock*>& GetBackEdges() const {
246    return back_edges_;
247  }
248
249  void ClearBackEdges() {
250    back_edges_.Reset();
251  }
252
253  // Find blocks that are part of this loop. Returns whether the loop is a natural loop,
254  // that is the header dominates the back edge.
255  bool Populate();
256
257  // Returns whether this loop information contains `block`.
258  // Note that this loop information *must* be populated before entering this function.
259  bool Contains(const HBasicBlock& block) const;
260
261  // Returns whether this loop information is an inner loop of `other`.
262  // Note that `other` *must* be populated before entering this function.
263  bool IsIn(const HLoopInformation& other) const;
264
265  const ArenaBitVector& GetBlocks() const { return blocks_; }
266
267 private:
268  // Internal recursive implementation of `Populate`.
269  void PopulateRecursive(HBasicBlock* block);
270
271  HBasicBlock* header_;
272  HSuspendCheck* suspend_check_;
273  GrowableArray<HBasicBlock*> back_edges_;
274  ArenaBitVector blocks_;
275
276  DISALLOW_COPY_AND_ASSIGN(HLoopInformation);
277};
278
279static constexpr size_t kNoLifetime = -1;
280static constexpr uint32_t kNoDexPc = -1;
281
282// A block in a method. Contains the list of instructions represented
283// as a double linked list. Each block knows its predecessors and
284// successors.
285
286class HBasicBlock : public ArenaObject<kArenaAllocMisc> {
287 public:
288  explicit HBasicBlock(HGraph* graph, uint32_t dex_pc = kNoDexPc)
289      : graph_(graph),
290        predecessors_(graph->GetArena(), kDefaultNumberOfPredecessors),
291        successors_(graph->GetArena(), kDefaultNumberOfSuccessors),
292        loop_information_(nullptr),
293        dominator_(nullptr),
294        dominated_blocks_(graph->GetArena(), kDefaultNumberOfDominatedBlocks),
295        block_id_(-1),
296        dex_pc_(dex_pc),
297        lifetime_start_(kNoLifetime),
298        lifetime_end_(kNoLifetime),
299        is_catch_block_(false) {}
300
301  const GrowableArray<HBasicBlock*>& GetPredecessors() const {
302    return predecessors_;
303  }
304
305  const GrowableArray<HBasicBlock*>& GetSuccessors() const {
306    return successors_;
307  }
308
309  const GrowableArray<HBasicBlock*>& GetDominatedBlocks() const {
310    return dominated_blocks_;
311  }
312
313  bool IsEntryBlock() const {
314    return graph_->GetEntryBlock() == this;
315  }
316
317  bool IsExitBlock() const {
318    return graph_->GetExitBlock() == this;
319  }
320
321  void AddBackEdge(HBasicBlock* back_edge) {
322    if (loop_information_ == nullptr) {
323      loop_information_ = new (graph_->GetArena()) HLoopInformation(this, graph_);
324    }
325    DCHECK_EQ(loop_information_->GetHeader(), this);
326    loop_information_->AddBackEdge(back_edge);
327  }
328
329  HGraph* GetGraph() const { return graph_; }
330
331  int GetBlockId() const { return block_id_; }
332  void SetBlockId(int id) { block_id_ = id; }
333
334  HBasicBlock* GetDominator() const { return dominator_; }
335  void SetDominator(HBasicBlock* dominator) { dominator_ = dominator; }
336  void AddDominatedBlock(HBasicBlock* block) { dominated_blocks_.Add(block); }
337
338  int NumberOfBackEdges() const {
339    return loop_information_ == nullptr
340        ? 0
341        : loop_information_->NumberOfBackEdges();
342  }
343
344  HInstruction* GetFirstInstruction() const { return instructions_.first_instruction_; }
345  HInstruction* GetLastInstruction() const { return instructions_.last_instruction_; }
346  const HInstructionList& GetInstructions() const { return instructions_; }
347  const HInstructionList& GetPhis() const { return phis_; }
348  HInstruction* GetFirstPhi() const { return phis_.first_instruction_; }
349
350  void AddSuccessor(HBasicBlock* block) {
351    successors_.Add(block);
352    block->predecessors_.Add(this);
353  }
354
355  void ReplaceSuccessor(HBasicBlock* existing, HBasicBlock* new_block) {
356    size_t successor_index = GetSuccessorIndexOf(existing);
357    DCHECK_NE(successor_index, static_cast<size_t>(-1));
358    existing->RemovePredecessor(this);
359    new_block->predecessors_.Add(this);
360    successors_.Put(successor_index, new_block);
361  }
362
363  void RemovePredecessor(HBasicBlock* block) {
364    predecessors_.Delete(block);
365  }
366
367  void ClearAllPredecessors() {
368    predecessors_.Reset();
369  }
370
371  void AddPredecessor(HBasicBlock* block) {
372    predecessors_.Add(block);
373    block->successors_.Add(this);
374  }
375
376  void SwapPredecessors() {
377    DCHECK_EQ(predecessors_.Size(), 2u);
378    HBasicBlock* temp = predecessors_.Get(0);
379    predecessors_.Put(0, predecessors_.Get(1));
380    predecessors_.Put(1, temp);
381  }
382
383  size_t GetPredecessorIndexOf(HBasicBlock* predecessor) {
384    for (size_t i = 0, e = predecessors_.Size(); i < e; ++i) {
385      if (predecessors_.Get(i) == predecessor) {
386        return i;
387      }
388    }
389    return -1;
390  }
391
392  size_t GetSuccessorIndexOf(HBasicBlock* successor) {
393    for (size_t i = 0, e = successors_.Size(); i < e; ++i) {
394      if (successors_.Get(i) == successor) {
395        return i;
396      }
397    }
398    return -1;
399  }
400
401  void AddInstruction(HInstruction* instruction);
402  void RemoveInstruction(HInstruction* instruction);
403  void InsertInstructionBefore(HInstruction* instruction, HInstruction* cursor);
404  // Replace instruction `initial` with `replacement` within this block.
405  void ReplaceAndRemoveInstructionWith(HInstruction* initial,
406                                       HInstruction* replacement);
407  void AddPhi(HPhi* phi);
408  void InsertPhiAfter(HPhi* instruction, HPhi* cursor);
409  void RemovePhi(HPhi* phi);
410
411  bool IsLoopHeader() const {
412    return (loop_information_ != nullptr) && (loop_information_->GetHeader() == this);
413  }
414
415  bool IsLoopPreHeaderFirstPredecessor() const {
416    DCHECK(IsLoopHeader());
417    DCHECK(!GetPredecessors().IsEmpty());
418    return GetPredecessors().Get(0) == GetLoopInformation()->GetPreHeader();
419  }
420
421  HLoopInformation* GetLoopInformation() const {
422    return loop_information_;
423  }
424
425  // Set the loop_information_ on this block. This method overrides the current
426  // loop_information if it is an outer loop of the passed loop information.
427  void SetInLoop(HLoopInformation* info) {
428    if (IsLoopHeader()) {
429      // Nothing to do. This just means `info` is an outer loop.
430    } else if (loop_information_ == nullptr) {
431      loop_information_ = info;
432    } else if (loop_information_->Contains(*info->GetHeader())) {
433      // Block is currently part of an outer loop. Make it part of this inner loop.
434      // Note that a non loop header having a loop information means this loop information
435      // has already been populated
436      loop_information_ = info;
437    } else {
438      // Block is part of an inner loop. Do not update the loop information.
439      // Note that we cannot do the check `info->Contains(loop_information_)->GetHeader()`
440      // at this point, because this method is being called while populating `info`.
441    }
442  }
443
444  bool IsInLoop() const { return loop_information_ != nullptr; }
445
446  // Returns wheter this block dominates the blocked passed as parameter.
447  bool Dominates(HBasicBlock* block) const;
448
449  size_t GetLifetimeStart() const { return lifetime_start_; }
450  size_t GetLifetimeEnd() const { return lifetime_end_; }
451
452  void SetLifetimeStart(size_t start) { lifetime_start_ = start; }
453  void SetLifetimeEnd(size_t end) { lifetime_end_ = end; }
454
455  uint32_t GetDexPc() const { return dex_pc_; }
456
457  bool IsCatchBlock() const { return is_catch_block_; }
458  void SetIsCatchBlock() { is_catch_block_ = true; }
459
460 private:
461  HGraph* const graph_;
462  GrowableArray<HBasicBlock*> predecessors_;
463  GrowableArray<HBasicBlock*> successors_;
464  HInstructionList instructions_;
465  HInstructionList phis_;
466  HLoopInformation* loop_information_;
467  HBasicBlock* dominator_;
468  GrowableArray<HBasicBlock*> dominated_blocks_;
469  int block_id_;
470  // The dex program counter of the first instruction of this block.
471  const uint32_t dex_pc_;
472  size_t lifetime_start_;
473  size_t lifetime_end_;
474  bool is_catch_block_;
475
476  DISALLOW_COPY_AND_ASSIGN(HBasicBlock);
477};
478
479#define FOR_EACH_CONCRETE_INSTRUCTION(M)                                \
480  M(Add, BinaryOperation)                                               \
481  M(And, BinaryOperation)                                               \
482  M(ArrayGet, Instruction)                                              \
483  M(ArrayLength, Instruction)                                           \
484  M(ArraySet, Instruction)                                              \
485  M(BoundsCheck, Instruction)                                           \
486  M(CheckCast, Instruction)                                             \
487  M(ClinitCheck, Instruction)                                           \
488  M(Compare, BinaryOperation)                                           \
489  M(Condition, BinaryOperation)                                         \
490  M(Div, BinaryOperation)                                               \
491  M(DivZeroCheck, Instruction)                                          \
492  M(DoubleConstant, Constant)                                           \
493  M(Equal, Condition)                                                   \
494  M(Exit, Instruction)                                                  \
495  M(FloatConstant, Constant)                                            \
496  M(Goto, Instruction)                                                  \
497  M(GreaterThan, Condition)                                             \
498  M(GreaterThanOrEqual, Condition)                                      \
499  M(If, Instruction)                                                    \
500  M(InstanceFieldGet, Instruction)                                      \
501  M(InstanceFieldSet, Instruction)                                      \
502  M(InstanceOf, Instruction)                                            \
503  M(IntConstant, Constant)                                              \
504  M(InvokeInterface, Invoke)                                            \
505  M(InvokeStatic, Invoke)                                               \
506  M(InvokeVirtual, Invoke)                                              \
507  M(LessThan, Condition)                                                \
508  M(LessThanOrEqual, Condition)                                         \
509  M(LoadClass, Instruction)                                             \
510  M(LoadException, Instruction)                                         \
511  M(LoadLocal, Instruction)                                             \
512  M(LoadString, Instruction)                                            \
513  M(Local, Instruction)                                                 \
514  M(LongConstant, Constant)                                             \
515  M(MonitorOperation, Instruction)                                      \
516  M(Mul, BinaryOperation)                                               \
517  M(Neg, UnaryOperation)                                                \
518  M(NewArray, Instruction)                                              \
519  M(NewInstance, Instruction)                                           \
520  M(Not, UnaryOperation)                                                \
521  M(NotEqual, Condition)                                                \
522  M(NullCheck, Instruction)                                             \
523  M(Or, BinaryOperation)                                                \
524  M(ParallelMove, Instruction)                                          \
525  M(ParameterValue, Instruction)                                        \
526  M(Phi, Instruction)                                                   \
527  M(Rem, BinaryOperation)                                               \
528  M(Return, Instruction)                                                \
529  M(ReturnVoid, Instruction)                                            \
530  M(Shl, BinaryOperation)                                               \
531  M(Shr, BinaryOperation)                                               \
532  M(StaticFieldGet, Instruction)                                        \
533  M(StaticFieldSet, Instruction)                                        \
534  M(StoreLocal, Instruction)                                            \
535  M(Sub, BinaryOperation)                                               \
536  M(SuspendCheck, Instruction)                                          \
537  M(Temporary, Instruction)                                             \
538  M(Throw, Instruction)                                                 \
539  M(TypeConversion, Instruction)                                        \
540  M(UShr, BinaryOperation)                                              \
541  M(Xor, BinaryOperation)                                               \
542
543#define FOR_EACH_INSTRUCTION(M)                                         \
544  FOR_EACH_CONCRETE_INSTRUCTION(M)                                      \
545  M(Constant, Instruction)                                              \
546  M(UnaryOperation, Instruction)                                        \
547  M(BinaryOperation, Instruction)                                       \
548  M(Invoke, Instruction)
549
550#define FORWARD_DECLARATION(type, super) class H##type;
551FOR_EACH_INSTRUCTION(FORWARD_DECLARATION)
552#undef FORWARD_DECLARATION
553
554#define DECLARE_INSTRUCTION(type)                                       \
555  virtual InstructionKind GetKind() const { return k##type; }           \
556  virtual const char* DebugName() const { return #type; }               \
557  virtual const H##type* As##type() const OVERRIDE { return this; }     \
558  virtual H##type* As##type() OVERRIDE { return this; }                 \
559  virtual bool InstructionTypeEquals(HInstruction* other) const {       \
560    return other->Is##type();                                           \
561  }                                                                     \
562  virtual void Accept(HGraphVisitor* visitor)
563
564template <typename T>
565class HUseListNode : public ArenaObject<kArenaAllocMisc> {
566 public:
567  HUseListNode(T* user, size_t index, HUseListNode* tail)
568      : user_(user), index_(index), tail_(tail) {}
569
570  HUseListNode* GetTail() const { return tail_; }
571  T* GetUser() const { return user_; }
572  size_t GetIndex() const { return index_; }
573
574  void SetTail(HUseListNode<T>* node) { tail_ = node; }
575
576 private:
577  T* const user_;
578  const size_t index_;
579  HUseListNode<T>* tail_;
580
581  DISALLOW_COPY_AND_ASSIGN(HUseListNode);
582};
583
584// Represents the side effects an instruction may have.
585class SideEffects : public ValueObject {
586 public:
587  SideEffects() : flags_(0) {}
588
589  static SideEffects None() {
590    return SideEffects(0);
591  }
592
593  static SideEffects All() {
594    return SideEffects(ChangesSomething().flags_ | DependsOnSomething().flags_);
595  }
596
597  static SideEffects ChangesSomething() {
598    return SideEffects((1 << kFlagChangesCount) - 1);
599  }
600
601  static SideEffects DependsOnSomething() {
602    int count = kFlagDependsOnCount - kFlagChangesCount;
603    return SideEffects(((1 << count) - 1) << kFlagChangesCount);
604  }
605
606  SideEffects Union(SideEffects other) const {
607    return SideEffects(flags_ | other.flags_);
608  }
609
610  bool HasSideEffects() const {
611    size_t all_bits_set = (1 << kFlagChangesCount) - 1;
612    return (flags_ & all_bits_set) != 0;
613  }
614
615  bool HasAllSideEffects() const {
616    size_t all_bits_set = (1 << kFlagChangesCount) - 1;
617    return all_bits_set == (flags_ & all_bits_set);
618  }
619
620  bool DependsOn(SideEffects other) const {
621    size_t depends_flags = other.ComputeDependsFlags();
622    return (flags_ & depends_flags) != 0;
623  }
624
625  bool HasDependencies() const {
626    int count = kFlagDependsOnCount - kFlagChangesCount;
627    size_t all_bits_set = (1 << count) - 1;
628    return ((flags_ >> kFlagChangesCount) & all_bits_set) != 0;
629  }
630
631 private:
632  static constexpr int kFlagChangesSomething = 0;
633  static constexpr int kFlagChangesCount = kFlagChangesSomething + 1;
634
635  static constexpr int kFlagDependsOnSomething = kFlagChangesCount;
636  static constexpr int kFlagDependsOnCount = kFlagDependsOnSomething + 1;
637
638  explicit SideEffects(size_t flags) : flags_(flags) {}
639
640  size_t ComputeDependsFlags() const {
641    return flags_ << kFlagChangesCount;
642  }
643
644  size_t flags_;
645};
646
647class HInstruction : public ArenaObject<kArenaAllocMisc> {
648 public:
649  explicit HInstruction(SideEffects side_effects)
650      : previous_(nullptr),
651        next_(nullptr),
652        block_(nullptr),
653        id_(-1),
654        ssa_index_(-1),
655        uses_(nullptr),
656        env_uses_(nullptr),
657        environment_(nullptr),
658        locations_(nullptr),
659        live_interval_(nullptr),
660        lifetime_position_(kNoLifetime),
661        side_effects_(side_effects) {}
662
663  virtual ~HInstruction() {}
664
665#define DECLARE_KIND(type, super) k##type,
666  enum InstructionKind {
667    FOR_EACH_INSTRUCTION(DECLARE_KIND)
668  };
669#undef DECLARE_KIND
670
671  HInstruction* GetNext() const { return next_; }
672  HInstruction* GetPrevious() const { return previous_; }
673
674  HBasicBlock* GetBlock() const { return block_; }
675  void SetBlock(HBasicBlock* block) { block_ = block; }
676  bool IsInBlock() const { return block_ != nullptr; }
677  bool IsInLoop() const { return block_->IsInLoop(); }
678  bool IsLoopHeaderPhi() { return IsPhi() && block_->IsLoopHeader(); }
679
680  virtual size_t InputCount() const = 0;
681  virtual HInstruction* InputAt(size_t i) const = 0;
682
683  virtual void Accept(HGraphVisitor* visitor) = 0;
684  virtual const char* DebugName() const = 0;
685
686  virtual Primitive::Type GetType() const { return Primitive::kPrimVoid; }
687  virtual void SetRawInputAt(size_t index, HInstruction* input) = 0;
688
689  virtual bool NeedsEnvironment() const { return false; }
690  virtual bool IsControlFlow() const { return false; }
691  virtual bool CanThrow() const { return false; }
692  bool HasSideEffects() const { return side_effects_.HasSideEffects(); }
693
694  void AddUseAt(HInstruction* user, size_t index) {
695    uses_ = new (block_->GetGraph()->GetArena()) HUseListNode<HInstruction>(user, index, uses_);
696  }
697
698  void AddEnvUseAt(HEnvironment* user, size_t index) {
699    DCHECK(user != nullptr);
700    env_uses_ = new (block_->GetGraph()->GetArena()) HUseListNode<HEnvironment>(
701        user, index, env_uses_);
702  }
703
704  void RemoveUser(HInstruction* user, size_t index);
705  void RemoveEnvironmentUser(HEnvironment* user, size_t index);
706
707  HUseListNode<HInstruction>* GetUses() const { return uses_; }
708  HUseListNode<HEnvironment>* GetEnvUses() const { return env_uses_; }
709
710  bool HasUses() const { return uses_ != nullptr || env_uses_ != nullptr; }
711  bool HasEnvironmentUses() const { return env_uses_ != nullptr; }
712
713  size_t NumberOfUses() const {
714    // TODO: Optimize this method if it is used outside of the HGraphVisualizer.
715    size_t result = 0;
716    HUseListNode<HInstruction>* current = uses_;
717    while (current != nullptr) {
718      current = current->GetTail();
719      ++result;
720    }
721    return result;
722  }
723
724  // Does this instruction strictly dominate `other_instruction`?
725  // Returns false if this instruction and `other_instruction` are the same.
726  // Aborts if this instruction and `other_instruction` are both phis.
727  bool StrictlyDominates(HInstruction* other_instruction) const;
728
729  int GetId() const { return id_; }
730  void SetId(int id) { id_ = id; }
731
732  int GetSsaIndex() const { return ssa_index_; }
733  void SetSsaIndex(int ssa_index) { ssa_index_ = ssa_index; }
734  bool HasSsaIndex() const { return ssa_index_ != -1; }
735
736  bool HasEnvironment() const { return environment_ != nullptr; }
737  HEnvironment* GetEnvironment() const { return environment_; }
738  void SetEnvironment(HEnvironment* environment) { environment_ = environment; }
739
740  // Returns the number of entries in the environment. Typically, that is the
741  // number of dex registers in a method. It could be more in case of inlining.
742  size_t EnvironmentSize() const;
743
744  LocationSummary* GetLocations() const { return locations_; }
745  void SetLocations(LocationSummary* locations) { locations_ = locations; }
746
747  void ReplaceWith(HInstruction* instruction);
748  void ReplaceInput(HInstruction* replacement, size_t index);
749
750  bool HasOnlyOneUse() const {
751    return uses_ != nullptr && uses_->GetTail() == nullptr;
752  }
753
754#define INSTRUCTION_TYPE_CHECK(type, super)                                    \
755  bool Is##type() const { return (As##type() != nullptr); }                    \
756  virtual const H##type* As##type() const { return nullptr; }                  \
757  virtual H##type* As##type() { return nullptr; }
758
759  FOR_EACH_INSTRUCTION(INSTRUCTION_TYPE_CHECK)
760#undef INSTRUCTION_TYPE_CHECK
761
762  // Returns whether the instruction can be moved within the graph.
763  virtual bool CanBeMoved() const { return false; }
764
765  // Returns whether the two instructions are of the same kind.
766  virtual bool InstructionTypeEquals(HInstruction* other) const {
767    UNUSED(other);
768    return false;
769  }
770
771  // Returns whether any data encoded in the two instructions is equal.
772  // This method does not look at the inputs. Both instructions must be
773  // of the same type, otherwise the method has undefined behavior.
774  virtual bool InstructionDataEquals(HInstruction* other) const {
775    UNUSED(other);
776    return false;
777  }
778
779  // Returns whether two instructions are equal, that is:
780  // 1) They have the same type and contain the same data (InstructionDataEquals).
781  // 2) Their inputs are identical.
782  bool Equals(HInstruction* other) const;
783
784  virtual InstructionKind GetKind() const = 0;
785
786  virtual size_t ComputeHashCode() const {
787    size_t result = GetKind();
788    for (size_t i = 0, e = InputCount(); i < e; ++i) {
789      result = (result * 31) + InputAt(i)->GetId();
790    }
791    return result;
792  }
793
794  SideEffects GetSideEffects() const { return side_effects_; }
795
796  size_t GetLifetimePosition() const { return lifetime_position_; }
797  void SetLifetimePosition(size_t position) { lifetime_position_ = position; }
798  LiveInterval* GetLiveInterval() const { return live_interval_; }
799  void SetLiveInterval(LiveInterval* interval) { live_interval_ = interval; }
800  bool HasLiveInterval() const { return live_interval_ != nullptr; }
801
802 private:
803  HInstruction* previous_;
804  HInstruction* next_;
805  HBasicBlock* block_;
806
807  // An instruction gets an id when it is added to the graph.
808  // It reflects creation order. A negative id means the instruction
809  // has not been added to the graph.
810  int id_;
811
812  // When doing liveness analysis, instructions that have uses get an SSA index.
813  int ssa_index_;
814
815  // List of instructions that have this instruction as input.
816  HUseListNode<HInstruction>* uses_;
817
818  // List of environments that contain this instruction.
819  HUseListNode<HEnvironment>* env_uses_;
820
821  // The environment associated with this instruction. Not null if the instruction
822  // might jump out of the method.
823  HEnvironment* environment_;
824
825  // Set by the code generator.
826  LocationSummary* locations_;
827
828  // Set by the liveness analysis.
829  LiveInterval* live_interval_;
830
831  // Set by the liveness analysis, this is the position in a linear
832  // order of blocks where this instruction's live interval start.
833  size_t lifetime_position_;
834
835  const SideEffects side_effects_;
836
837  friend class HBasicBlock;
838  friend class HInstructionList;
839
840  DISALLOW_COPY_AND_ASSIGN(HInstruction);
841};
842std::ostream& operator<<(std::ostream& os, const HInstruction::InstructionKind& rhs);
843
844template<typename T>
845class HUseIterator : public ValueObject {
846 public:
847  explicit HUseIterator(HUseListNode<T>* uses) : current_(uses) {}
848
849  bool Done() const { return current_ == nullptr; }
850
851  void Advance() {
852    DCHECK(!Done());
853    current_ = current_->GetTail();
854  }
855
856  HUseListNode<T>* Current() const {
857    DCHECK(!Done());
858    return current_;
859  }
860
861 private:
862  HUseListNode<T>* current_;
863
864  friend class HValue;
865};
866
867// A HEnvironment object contains the values of virtual registers at a given location.
868class HEnvironment : public ArenaObject<kArenaAllocMisc> {
869 public:
870  HEnvironment(ArenaAllocator* arena, size_t number_of_vregs) : vregs_(arena, number_of_vregs) {
871    vregs_.SetSize(number_of_vregs);
872    for (size_t i = 0; i < number_of_vregs; i++) {
873      vregs_.Put(i, nullptr);
874    }
875  }
876
877  void Populate(const GrowableArray<HInstruction*>& env) {
878    for (size_t i = 0; i < env.Size(); i++) {
879      HInstruction* instruction = env.Get(i);
880      vregs_.Put(i, instruction);
881      if (instruction != nullptr) {
882        instruction->AddEnvUseAt(this, i);
883      }
884    }
885  }
886
887  void SetRawEnvAt(size_t index, HInstruction* instruction) {
888    vregs_.Put(index, instruction);
889  }
890
891  HInstruction* GetInstructionAt(size_t index) const {
892    return vregs_.Get(index);
893  }
894
895  GrowableArray<HInstruction*>* GetVRegs() {
896    return &vregs_;
897  }
898
899  size_t Size() const { return vregs_.Size(); }
900
901 private:
902  GrowableArray<HInstruction*> vregs_;
903
904  DISALLOW_COPY_AND_ASSIGN(HEnvironment);
905};
906
907class HInputIterator : public ValueObject {
908 public:
909  explicit HInputIterator(HInstruction* instruction) : instruction_(instruction), index_(0) {}
910
911  bool Done() const { return index_ == instruction_->InputCount(); }
912  HInstruction* Current() const { return instruction_->InputAt(index_); }
913  void Advance() { index_++; }
914
915 private:
916  HInstruction* instruction_;
917  size_t index_;
918
919  DISALLOW_COPY_AND_ASSIGN(HInputIterator);
920};
921
922class HInstructionIterator : public ValueObject {
923 public:
924  explicit HInstructionIterator(const HInstructionList& instructions)
925      : instruction_(instructions.first_instruction_) {
926    next_ = Done() ? nullptr : instruction_->GetNext();
927  }
928
929  bool Done() const { return instruction_ == nullptr; }
930  HInstruction* Current() const { return instruction_; }
931  void Advance() {
932    instruction_ = next_;
933    next_ = Done() ? nullptr : instruction_->GetNext();
934  }
935
936 private:
937  HInstruction* instruction_;
938  HInstruction* next_;
939
940  DISALLOW_COPY_AND_ASSIGN(HInstructionIterator);
941};
942
943class HBackwardInstructionIterator : public ValueObject {
944 public:
945  explicit HBackwardInstructionIterator(const HInstructionList& instructions)
946      : instruction_(instructions.last_instruction_) {
947    next_ = Done() ? nullptr : instruction_->GetPrevious();
948  }
949
950  bool Done() const { return instruction_ == nullptr; }
951  HInstruction* Current() const { return instruction_; }
952  void Advance() {
953    instruction_ = next_;
954    next_ = Done() ? nullptr : instruction_->GetPrevious();
955  }
956
957 private:
958  HInstruction* instruction_;
959  HInstruction* next_;
960
961  DISALLOW_COPY_AND_ASSIGN(HBackwardInstructionIterator);
962};
963
964// An embedded container with N elements of type T.  Used (with partial
965// specialization for N=0) because embedded arrays cannot have size 0.
966template<typename T, intptr_t N>
967class EmbeddedArray {
968 public:
969  EmbeddedArray() : elements_() {}
970
971  intptr_t GetLength() const { return N; }
972
973  const T& operator[](intptr_t i) const {
974    DCHECK_LT(i, GetLength());
975    return elements_[i];
976  }
977
978  T& operator[](intptr_t i) {
979    DCHECK_LT(i, GetLength());
980    return elements_[i];
981  }
982
983  const T& At(intptr_t i) const {
984    return (*this)[i];
985  }
986
987  void SetAt(intptr_t i, const T& val) {
988    (*this)[i] = val;
989  }
990
991 private:
992  T elements_[N];
993};
994
995template<typename T>
996class EmbeddedArray<T, 0> {
997 public:
998  intptr_t length() const { return 0; }
999  const T& operator[](intptr_t i) const {
1000    UNUSED(i);
1001    LOG(FATAL) << "Unreachable";
1002    UNREACHABLE();
1003  }
1004  T& operator[](intptr_t i) {
1005    UNUSED(i);
1006    LOG(FATAL) << "Unreachable";
1007    UNREACHABLE();
1008  }
1009};
1010
1011template<intptr_t N>
1012class HTemplateInstruction: public HInstruction {
1013 public:
1014  HTemplateInstruction<N>(SideEffects side_effects)
1015      : HInstruction(side_effects), inputs_() {}
1016  virtual ~HTemplateInstruction() {}
1017
1018  virtual size_t InputCount() const { return N; }
1019  virtual HInstruction* InputAt(size_t i) const { return inputs_[i]; }
1020
1021 protected:
1022  virtual void SetRawInputAt(size_t i, HInstruction* instruction) {
1023    inputs_[i] = instruction;
1024  }
1025
1026 private:
1027  EmbeddedArray<HInstruction*, N> inputs_;
1028
1029  friend class SsaBuilder;
1030};
1031
1032template<intptr_t N>
1033class HExpression : public HTemplateInstruction<N> {
1034 public:
1035  HExpression<N>(Primitive::Type type, SideEffects side_effects)
1036      : HTemplateInstruction<N>(side_effects), type_(type) {}
1037  virtual ~HExpression() {}
1038
1039  virtual Primitive::Type GetType() const { return type_; }
1040
1041 protected:
1042  Primitive::Type type_;
1043};
1044
1045// Represents dex's RETURN_VOID opcode. A HReturnVoid is a control flow
1046// instruction that branches to the exit block.
1047class HReturnVoid : public HTemplateInstruction<0> {
1048 public:
1049  HReturnVoid() : HTemplateInstruction(SideEffects::None()) {}
1050
1051  virtual bool IsControlFlow() const { return true; }
1052
1053  DECLARE_INSTRUCTION(ReturnVoid);
1054
1055 private:
1056  DISALLOW_COPY_AND_ASSIGN(HReturnVoid);
1057};
1058
1059// Represents dex's RETURN opcodes. A HReturn is a control flow
1060// instruction that branches to the exit block.
1061class HReturn : public HTemplateInstruction<1> {
1062 public:
1063  explicit HReturn(HInstruction* value) : HTemplateInstruction(SideEffects::None()) {
1064    SetRawInputAt(0, value);
1065  }
1066
1067  virtual bool IsControlFlow() const { return true; }
1068
1069  DECLARE_INSTRUCTION(Return);
1070
1071 private:
1072  DISALLOW_COPY_AND_ASSIGN(HReturn);
1073};
1074
1075// The exit instruction is the only instruction of the exit block.
1076// Instructions aborting the method (HThrow and HReturn) must branch to the
1077// exit block.
1078class HExit : public HTemplateInstruction<0> {
1079 public:
1080  HExit() : HTemplateInstruction(SideEffects::None()) {}
1081
1082  virtual bool IsControlFlow() const { return true; }
1083
1084  DECLARE_INSTRUCTION(Exit);
1085
1086 private:
1087  DISALLOW_COPY_AND_ASSIGN(HExit);
1088};
1089
1090// Jumps from one block to another.
1091class HGoto : public HTemplateInstruction<0> {
1092 public:
1093  HGoto() : HTemplateInstruction(SideEffects::None()) {}
1094
1095  bool IsControlFlow() const OVERRIDE { return true; }
1096
1097  HBasicBlock* GetSuccessor() const {
1098    return GetBlock()->GetSuccessors().Get(0);
1099  }
1100
1101  DECLARE_INSTRUCTION(Goto);
1102
1103 private:
1104  DISALLOW_COPY_AND_ASSIGN(HGoto);
1105};
1106
1107
1108// Conditional branch. A block ending with an HIf instruction must have
1109// two successors.
1110class HIf : public HTemplateInstruction<1> {
1111 public:
1112  explicit HIf(HInstruction* input) : HTemplateInstruction(SideEffects::None()) {
1113    SetRawInputAt(0, input);
1114  }
1115
1116  bool IsControlFlow() const OVERRIDE { return true; }
1117
1118  HBasicBlock* IfTrueSuccessor() const {
1119    return GetBlock()->GetSuccessors().Get(0);
1120  }
1121
1122  HBasicBlock* IfFalseSuccessor() const {
1123    return GetBlock()->GetSuccessors().Get(1);
1124  }
1125
1126  DECLARE_INSTRUCTION(If);
1127
1128  virtual bool IsIfInstruction() const { return true; }
1129
1130 private:
1131  DISALLOW_COPY_AND_ASSIGN(HIf);
1132};
1133
1134class HUnaryOperation : public HExpression<1> {
1135 public:
1136  HUnaryOperation(Primitive::Type result_type, HInstruction* input)
1137      : HExpression(result_type, SideEffects::None()) {
1138    SetRawInputAt(0, input);
1139  }
1140
1141  HInstruction* GetInput() const { return InputAt(0); }
1142  Primitive::Type GetResultType() const { return GetType(); }
1143
1144  virtual bool CanBeMoved() const { return true; }
1145  virtual bool InstructionDataEquals(HInstruction* other) const {
1146    UNUSED(other);
1147    return true;
1148  }
1149
1150  // Try to statically evaluate `operation` and return a HConstant
1151  // containing the result of this evaluation.  If `operation` cannot
1152  // be evaluated as a constant, return nullptr.
1153  HConstant* TryStaticEvaluation() const;
1154
1155  // Apply this operation to `x`.
1156  virtual int32_t Evaluate(int32_t x) const = 0;
1157  virtual int64_t Evaluate(int64_t x) const = 0;
1158
1159  DECLARE_INSTRUCTION(UnaryOperation);
1160
1161 private:
1162  DISALLOW_COPY_AND_ASSIGN(HUnaryOperation);
1163};
1164
1165class HBinaryOperation : public HExpression<2> {
1166 public:
1167  HBinaryOperation(Primitive::Type result_type,
1168                   HInstruction* left,
1169                   HInstruction* right) : HExpression(result_type, SideEffects::None()) {
1170    SetRawInputAt(0, left);
1171    SetRawInputAt(1, right);
1172  }
1173
1174  HInstruction* GetLeft() const { return InputAt(0); }
1175  HInstruction* GetRight() const { return InputAt(1); }
1176  Primitive::Type GetResultType() const { return GetType(); }
1177
1178  virtual bool IsCommutative() { return false; }
1179
1180  virtual bool CanBeMoved() const { return true; }
1181  virtual bool InstructionDataEquals(HInstruction* other) const {
1182    UNUSED(other);
1183    return true;
1184  }
1185
1186  // Try to statically evaluate `operation` and return a HConstant
1187  // containing the result of this evaluation.  If `operation` cannot
1188  // be evaluated as a constant, return nullptr.
1189  HConstant* TryStaticEvaluation() const;
1190
1191  // Apply this operation to `x` and `y`.
1192  virtual int32_t Evaluate(int32_t x, int32_t y) const = 0;
1193  virtual int64_t Evaluate(int64_t x, int64_t y) const = 0;
1194
1195  DECLARE_INSTRUCTION(BinaryOperation);
1196
1197 private:
1198  DISALLOW_COPY_AND_ASSIGN(HBinaryOperation);
1199};
1200
1201class HCondition : public HBinaryOperation {
1202 public:
1203  HCondition(HInstruction* first, HInstruction* second)
1204      : HBinaryOperation(Primitive::kPrimBoolean, first, second),
1205        needs_materialization_(true) {}
1206
1207  virtual bool IsCommutative() { return true; }
1208
1209  bool NeedsMaterialization() const { return needs_materialization_; }
1210  void ClearNeedsMaterialization() { needs_materialization_ = false; }
1211
1212  // For code generation purposes, returns whether this instruction is just before
1213  // `if_`, and disregard moves in between.
1214  bool IsBeforeWhenDisregardMoves(HIf* if_) const;
1215
1216  DECLARE_INSTRUCTION(Condition);
1217
1218  virtual IfCondition GetCondition() const = 0;
1219
1220 private:
1221  // For register allocation purposes, returns whether this instruction needs to be
1222  // materialized (that is, not just be in the processor flags).
1223  bool needs_materialization_;
1224
1225  DISALLOW_COPY_AND_ASSIGN(HCondition);
1226};
1227
1228// Instruction to check if two inputs are equal to each other.
1229class HEqual : public HCondition {
1230 public:
1231  HEqual(HInstruction* first, HInstruction* second)
1232      : HCondition(first, second) {}
1233
1234  virtual int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE {
1235    return x == y ? 1 : 0;
1236  }
1237  virtual int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE {
1238    return x == y ? 1 : 0;
1239  }
1240
1241  DECLARE_INSTRUCTION(Equal);
1242
1243  virtual IfCondition GetCondition() const {
1244    return kCondEQ;
1245  }
1246
1247 private:
1248  DISALLOW_COPY_AND_ASSIGN(HEqual);
1249};
1250
1251class HNotEqual : public HCondition {
1252 public:
1253  HNotEqual(HInstruction* first, HInstruction* second)
1254      : HCondition(first, second) {}
1255
1256  virtual int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE {
1257    return x != y ? 1 : 0;
1258  }
1259  virtual int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE {
1260    return x != y ? 1 : 0;
1261  }
1262
1263  DECLARE_INSTRUCTION(NotEqual);
1264
1265  virtual IfCondition GetCondition() const {
1266    return kCondNE;
1267  }
1268
1269 private:
1270  DISALLOW_COPY_AND_ASSIGN(HNotEqual);
1271};
1272
1273class HLessThan : public HCondition {
1274 public:
1275  HLessThan(HInstruction* first, HInstruction* second)
1276      : HCondition(first, second) {}
1277
1278  virtual int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE {
1279    return x < y ? 1 : 0;
1280  }
1281  virtual int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE {
1282    return x < y ? 1 : 0;
1283  }
1284
1285  DECLARE_INSTRUCTION(LessThan);
1286
1287  virtual IfCondition GetCondition() const {
1288    return kCondLT;
1289  }
1290
1291 private:
1292  DISALLOW_COPY_AND_ASSIGN(HLessThan);
1293};
1294
1295class HLessThanOrEqual : public HCondition {
1296 public:
1297  HLessThanOrEqual(HInstruction* first, HInstruction* second)
1298      : HCondition(first, second) {}
1299
1300  virtual int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE {
1301    return x <= y ? 1 : 0;
1302  }
1303  virtual int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE {
1304    return x <= y ? 1 : 0;
1305  }
1306
1307  DECLARE_INSTRUCTION(LessThanOrEqual);
1308
1309  virtual IfCondition GetCondition() const {
1310    return kCondLE;
1311  }
1312
1313 private:
1314  DISALLOW_COPY_AND_ASSIGN(HLessThanOrEqual);
1315};
1316
1317class HGreaterThan : public HCondition {
1318 public:
1319  HGreaterThan(HInstruction* first, HInstruction* second)
1320      : HCondition(first, second) {}
1321
1322  virtual int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE {
1323    return x > y ? 1 : 0;
1324  }
1325  virtual int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE {
1326    return x > y ? 1 : 0;
1327  }
1328
1329  DECLARE_INSTRUCTION(GreaterThan);
1330
1331  virtual IfCondition GetCondition() const {
1332    return kCondGT;
1333  }
1334
1335 private:
1336  DISALLOW_COPY_AND_ASSIGN(HGreaterThan);
1337};
1338
1339class HGreaterThanOrEqual : public HCondition {
1340 public:
1341  HGreaterThanOrEqual(HInstruction* first, HInstruction* second)
1342      : HCondition(first, second) {}
1343
1344  virtual int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE {
1345    return x >= y ? 1 : 0;
1346  }
1347  virtual int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE {
1348    return x >= y ? 1 : 0;
1349  }
1350
1351  DECLARE_INSTRUCTION(GreaterThanOrEqual);
1352
1353  virtual IfCondition GetCondition() const {
1354    return kCondGE;
1355  }
1356
1357 private:
1358  DISALLOW_COPY_AND_ASSIGN(HGreaterThanOrEqual);
1359};
1360
1361
1362// Instruction to check how two inputs compare to each other.
1363// Result is 0 if input0 == input1, 1 if input0 > input1, or -1 if input0 < input1.
1364class HCompare : public HBinaryOperation {
1365 public:
1366  // The bias applies for floating point operations and indicates how NaN
1367  // comparisons are treated:
1368  enum Bias {
1369    kNoBias,  // bias is not applicable (i.e. for long operation)
1370    kGtBias,  // return 1 for NaN comparisons
1371    kLtBias,  // return -1 for NaN comparisons
1372  };
1373
1374  HCompare(Primitive::Type type, HInstruction* first, HInstruction* second, Bias bias)
1375      : HBinaryOperation(Primitive::kPrimInt, first, second), bias_(bias) {
1376    DCHECK_EQ(type, first->GetType());
1377    DCHECK_EQ(type, second->GetType());
1378  }
1379
1380  int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE {
1381    return
1382      x == y ? 0 :
1383      x > y ? 1 :
1384      -1;
1385  }
1386
1387  int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE {
1388    return
1389      x == y ? 0 :
1390      x > y ? 1 :
1391      -1;
1392  }
1393
1394  bool InstructionDataEquals(HInstruction* other) const OVERRIDE {
1395    return bias_ == other->AsCompare()->bias_;
1396  }
1397
1398  bool IsGtBias() { return bias_ == kGtBias; }
1399
1400  DECLARE_INSTRUCTION(Compare);
1401
1402 private:
1403  const Bias bias_;
1404
1405  DISALLOW_COPY_AND_ASSIGN(HCompare);
1406};
1407
1408// A local in the graph. Corresponds to a Dex register.
1409class HLocal : public HTemplateInstruction<0> {
1410 public:
1411  explicit HLocal(uint16_t reg_number)
1412      : HTemplateInstruction(SideEffects::None()), reg_number_(reg_number) {}
1413
1414  DECLARE_INSTRUCTION(Local);
1415
1416  uint16_t GetRegNumber() const { return reg_number_; }
1417
1418 private:
1419  // The Dex register number.
1420  const uint16_t reg_number_;
1421
1422  DISALLOW_COPY_AND_ASSIGN(HLocal);
1423};
1424
1425// Load a given local. The local is an input of this instruction.
1426class HLoadLocal : public HExpression<1> {
1427 public:
1428  HLoadLocal(HLocal* local, Primitive::Type type)
1429      : HExpression(type, SideEffects::None()) {
1430    SetRawInputAt(0, local);
1431  }
1432
1433  HLocal* GetLocal() const { return reinterpret_cast<HLocal*>(InputAt(0)); }
1434
1435  DECLARE_INSTRUCTION(LoadLocal);
1436
1437 private:
1438  DISALLOW_COPY_AND_ASSIGN(HLoadLocal);
1439};
1440
1441// Store a value in a given local. This instruction has two inputs: the value
1442// and the local.
1443class HStoreLocal : public HTemplateInstruction<2> {
1444 public:
1445  HStoreLocal(HLocal* local, HInstruction* value) : HTemplateInstruction(SideEffects::None()) {
1446    SetRawInputAt(0, local);
1447    SetRawInputAt(1, value);
1448  }
1449
1450  HLocal* GetLocal() const { return reinterpret_cast<HLocal*>(InputAt(0)); }
1451
1452  DECLARE_INSTRUCTION(StoreLocal);
1453
1454 private:
1455  DISALLOW_COPY_AND_ASSIGN(HStoreLocal);
1456};
1457
1458class HConstant : public HExpression<0> {
1459 public:
1460  explicit HConstant(Primitive::Type type) : HExpression(type, SideEffects::None()) {}
1461
1462  virtual bool CanBeMoved() const { return true; }
1463
1464  DECLARE_INSTRUCTION(Constant);
1465
1466 private:
1467  DISALLOW_COPY_AND_ASSIGN(HConstant);
1468};
1469
1470class HFloatConstant : public HConstant {
1471 public:
1472  explicit HFloatConstant(float value) : HConstant(Primitive::kPrimFloat), value_(value) {}
1473
1474  float GetValue() const { return value_; }
1475
1476  virtual bool InstructionDataEquals(HInstruction* other) const {
1477    return bit_cast<float, int32_t>(other->AsFloatConstant()->value_) ==
1478        bit_cast<float, int32_t>(value_);
1479  }
1480
1481  virtual size_t ComputeHashCode() const { return static_cast<size_t>(GetValue()); }
1482
1483  DECLARE_INSTRUCTION(FloatConstant);
1484
1485 private:
1486  const float value_;
1487
1488  DISALLOW_COPY_AND_ASSIGN(HFloatConstant);
1489};
1490
1491class HDoubleConstant : public HConstant {
1492 public:
1493  explicit HDoubleConstant(double value) : HConstant(Primitive::kPrimDouble), value_(value) {}
1494
1495  double GetValue() const { return value_; }
1496
1497  virtual bool InstructionDataEquals(HInstruction* other) const {
1498    return bit_cast<double, int64_t>(other->AsDoubleConstant()->value_) ==
1499        bit_cast<double, int64_t>(value_);
1500  }
1501
1502  virtual size_t ComputeHashCode() const { return static_cast<size_t>(GetValue()); }
1503
1504  DECLARE_INSTRUCTION(DoubleConstant);
1505
1506 private:
1507  const double value_;
1508
1509  DISALLOW_COPY_AND_ASSIGN(HDoubleConstant);
1510};
1511
1512// Constants of the type int. Those can be from Dex instructions, or
1513// synthesized (for example with the if-eqz instruction).
1514class HIntConstant : public HConstant {
1515 public:
1516  explicit HIntConstant(int32_t value) : HConstant(Primitive::kPrimInt), value_(value) {}
1517
1518  int32_t GetValue() const { return value_; }
1519
1520  virtual bool InstructionDataEquals(HInstruction* other) const {
1521    return other->AsIntConstant()->value_ == value_;
1522  }
1523
1524  virtual size_t ComputeHashCode() const { return GetValue(); }
1525
1526  DECLARE_INSTRUCTION(IntConstant);
1527
1528 private:
1529  const int32_t value_;
1530
1531  DISALLOW_COPY_AND_ASSIGN(HIntConstant);
1532};
1533
1534class HLongConstant : public HConstant {
1535 public:
1536  explicit HLongConstant(int64_t value) : HConstant(Primitive::kPrimLong), value_(value) {}
1537
1538  int64_t GetValue() const { return value_; }
1539
1540  virtual bool InstructionDataEquals(HInstruction* other) const {
1541    return other->AsLongConstant()->value_ == value_;
1542  }
1543
1544  virtual size_t ComputeHashCode() const { return static_cast<size_t>(GetValue()); }
1545
1546  DECLARE_INSTRUCTION(LongConstant);
1547
1548 private:
1549  const int64_t value_;
1550
1551  DISALLOW_COPY_AND_ASSIGN(HLongConstant);
1552};
1553
1554class HInvoke : public HInstruction {
1555 public:
1556  HInvoke(ArenaAllocator* arena,
1557          uint32_t number_of_arguments,
1558          Primitive::Type return_type,
1559          uint32_t dex_pc)
1560    : HInstruction(SideEffects::All()),
1561      inputs_(arena, number_of_arguments),
1562      return_type_(return_type),
1563      dex_pc_(dex_pc) {
1564    inputs_.SetSize(number_of_arguments);
1565  }
1566
1567  virtual size_t InputCount() const { return inputs_.Size(); }
1568  virtual HInstruction* InputAt(size_t i) const { return inputs_.Get(i); }
1569
1570  // Runtime needs to walk the stack, so Dex -> Dex calls need to
1571  // know their environment.
1572  virtual bool NeedsEnvironment() const { return true; }
1573
1574  void SetArgumentAt(size_t index, HInstruction* argument) {
1575    SetRawInputAt(index, argument);
1576  }
1577
1578  virtual void SetRawInputAt(size_t index, HInstruction* input) {
1579    inputs_.Put(index, input);
1580  }
1581
1582  virtual Primitive::Type GetType() const { return return_type_; }
1583
1584  uint32_t GetDexPc() const { return dex_pc_; }
1585
1586  DECLARE_INSTRUCTION(Invoke);
1587
1588 protected:
1589  GrowableArray<HInstruction*> inputs_;
1590  const Primitive::Type return_type_;
1591  const uint32_t dex_pc_;
1592
1593 private:
1594  DISALLOW_COPY_AND_ASSIGN(HInvoke);
1595};
1596
1597class HInvokeStatic : public HInvoke {
1598 public:
1599  HInvokeStatic(ArenaAllocator* arena,
1600                uint32_t number_of_arguments,
1601                Primitive::Type return_type,
1602                uint32_t dex_pc,
1603                uint32_t index_in_dex_cache)
1604      : HInvoke(arena, number_of_arguments, return_type, dex_pc),
1605        index_in_dex_cache_(index_in_dex_cache) {}
1606
1607  uint32_t GetIndexInDexCache() const { return index_in_dex_cache_; }
1608
1609  DECLARE_INSTRUCTION(InvokeStatic);
1610
1611 private:
1612  const uint32_t index_in_dex_cache_;
1613
1614  DISALLOW_COPY_AND_ASSIGN(HInvokeStatic);
1615};
1616
1617class HInvokeVirtual : public HInvoke {
1618 public:
1619  HInvokeVirtual(ArenaAllocator* arena,
1620                 uint32_t number_of_arguments,
1621                 Primitive::Type return_type,
1622                 uint32_t dex_pc,
1623                 uint32_t vtable_index)
1624      : HInvoke(arena, number_of_arguments, return_type, dex_pc),
1625        vtable_index_(vtable_index) {}
1626
1627  uint32_t GetVTableIndex() const { return vtable_index_; }
1628
1629  DECLARE_INSTRUCTION(InvokeVirtual);
1630
1631 private:
1632  const uint32_t vtable_index_;
1633
1634  DISALLOW_COPY_AND_ASSIGN(HInvokeVirtual);
1635};
1636
1637class HInvokeInterface : public HInvoke {
1638 public:
1639  HInvokeInterface(ArenaAllocator* arena,
1640                   uint32_t number_of_arguments,
1641                   Primitive::Type return_type,
1642                   uint32_t dex_pc,
1643                   uint32_t dex_method_index,
1644                   uint32_t imt_index)
1645      : HInvoke(arena, number_of_arguments, return_type, dex_pc),
1646        dex_method_index_(dex_method_index),
1647        imt_index_(imt_index) {}
1648
1649  uint32_t GetImtIndex() const { return imt_index_; }
1650  uint32_t GetDexMethodIndex() const { return dex_method_index_; }
1651
1652  DECLARE_INSTRUCTION(InvokeInterface);
1653
1654 private:
1655  const uint32_t dex_method_index_;
1656  const uint32_t imt_index_;
1657
1658  DISALLOW_COPY_AND_ASSIGN(HInvokeInterface);
1659};
1660
1661class HNewInstance : public HExpression<0> {
1662 public:
1663  HNewInstance(uint32_t dex_pc, uint16_t type_index)
1664      : HExpression(Primitive::kPrimNot, SideEffects::None()),
1665        dex_pc_(dex_pc),
1666        type_index_(type_index) {}
1667
1668  uint32_t GetDexPc() const { return dex_pc_; }
1669  uint16_t GetTypeIndex() const { return type_index_; }
1670
1671  // Calls runtime so needs an environment.
1672  virtual bool NeedsEnvironment() const { return true; }
1673
1674  DECLARE_INSTRUCTION(NewInstance);
1675
1676 private:
1677  const uint32_t dex_pc_;
1678  const uint16_t type_index_;
1679
1680  DISALLOW_COPY_AND_ASSIGN(HNewInstance);
1681};
1682
1683class HNeg : public HUnaryOperation {
1684 public:
1685  explicit HNeg(Primitive::Type result_type, HInstruction* input)
1686      : HUnaryOperation(result_type, input) {}
1687
1688  virtual int32_t Evaluate(int32_t x) const OVERRIDE { return -x; }
1689  virtual int64_t Evaluate(int64_t x) const OVERRIDE { return -x; }
1690
1691  DECLARE_INSTRUCTION(Neg);
1692
1693 private:
1694  DISALLOW_COPY_AND_ASSIGN(HNeg);
1695};
1696
1697class HNewArray : public HExpression<1> {
1698 public:
1699  HNewArray(HInstruction* length, uint32_t dex_pc, uint16_t type_index)
1700      : HExpression(Primitive::kPrimNot, SideEffects::None()),
1701        dex_pc_(dex_pc),
1702        type_index_(type_index) {
1703    SetRawInputAt(0, length);
1704  }
1705
1706  uint32_t GetDexPc() const { return dex_pc_; }
1707  uint16_t GetTypeIndex() const { return type_index_; }
1708
1709  // Calls runtime so needs an environment.
1710  virtual bool NeedsEnvironment() const { return true; }
1711
1712  DECLARE_INSTRUCTION(NewArray);
1713
1714 private:
1715  const uint32_t dex_pc_;
1716  const uint16_t type_index_;
1717
1718  DISALLOW_COPY_AND_ASSIGN(HNewArray);
1719};
1720
1721class HAdd : public HBinaryOperation {
1722 public:
1723  HAdd(Primitive::Type result_type, HInstruction* left, HInstruction* right)
1724      : HBinaryOperation(result_type, left, right) {}
1725
1726  virtual bool IsCommutative() { return true; }
1727
1728  virtual int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE {
1729    return x + y;
1730  }
1731  virtual int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE {
1732    return x + y;
1733  }
1734
1735  DECLARE_INSTRUCTION(Add);
1736
1737 private:
1738  DISALLOW_COPY_AND_ASSIGN(HAdd);
1739};
1740
1741class HSub : public HBinaryOperation {
1742 public:
1743  HSub(Primitive::Type result_type, HInstruction* left, HInstruction* right)
1744      : HBinaryOperation(result_type, left, right) {}
1745
1746  virtual int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE {
1747    return x - y;
1748  }
1749  virtual int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE {
1750    return x - y;
1751  }
1752
1753  DECLARE_INSTRUCTION(Sub);
1754
1755 private:
1756  DISALLOW_COPY_AND_ASSIGN(HSub);
1757};
1758
1759class HMul : public HBinaryOperation {
1760 public:
1761  HMul(Primitive::Type result_type, HInstruction* left, HInstruction* right)
1762      : HBinaryOperation(result_type, left, right) {}
1763
1764  virtual bool IsCommutative() { return true; }
1765
1766  virtual int32_t Evaluate(int32_t x, int32_t y) const { return x * y; }
1767  virtual int64_t Evaluate(int64_t x, int64_t y) const { return x * y; }
1768
1769  DECLARE_INSTRUCTION(Mul);
1770
1771 private:
1772  DISALLOW_COPY_AND_ASSIGN(HMul);
1773};
1774
1775class HDiv : public HBinaryOperation {
1776 public:
1777  HDiv(Primitive::Type result_type, HInstruction* left, HInstruction* right, uint32_t dex_pc)
1778      : HBinaryOperation(result_type, left, right), dex_pc_(dex_pc) {}
1779
1780  virtual int32_t Evaluate(int32_t x, int32_t y) const {
1781    // Our graph structure ensures we never have 0 for `y` during constant folding.
1782    DCHECK_NE(y, 0);
1783    // Special case -1 to avoid getting a SIGFPE on x86(_64).
1784    return (y == -1) ? -x : x / y;
1785  }
1786
1787  virtual int64_t Evaluate(int64_t x, int64_t y) const {
1788    DCHECK_NE(y, 0);
1789    // Special case -1 to avoid getting a SIGFPE on x86(_64).
1790    return (y == -1) ? -x : x / y;
1791  }
1792
1793  uint32_t GetDexPc() const { return dex_pc_; }
1794
1795  DECLARE_INSTRUCTION(Div);
1796
1797 private:
1798  const uint32_t dex_pc_;
1799
1800  DISALLOW_COPY_AND_ASSIGN(HDiv);
1801};
1802
1803class HRem : public HBinaryOperation {
1804 public:
1805  HRem(Primitive::Type result_type, HInstruction* left, HInstruction* right, uint32_t dex_pc)
1806      : HBinaryOperation(result_type, left, right), dex_pc_(dex_pc) {}
1807
1808  virtual int32_t Evaluate(int32_t x, int32_t y) const {
1809    DCHECK_NE(y, 0);
1810    // Special case -1 to avoid getting a SIGFPE on x86(_64).
1811    return (y == -1) ? 0 : x % y;
1812  }
1813
1814  virtual int64_t Evaluate(int64_t x, int64_t y) const {
1815    DCHECK_NE(y, 0);
1816    // Special case -1 to avoid getting a SIGFPE on x86(_64).
1817    return (y == -1) ? 0 : x % y;
1818  }
1819
1820  uint32_t GetDexPc() const { return dex_pc_; }
1821
1822  DECLARE_INSTRUCTION(Rem);
1823
1824 private:
1825  const uint32_t dex_pc_;
1826
1827  DISALLOW_COPY_AND_ASSIGN(HRem);
1828};
1829
1830class HDivZeroCheck : public HExpression<1> {
1831 public:
1832  HDivZeroCheck(HInstruction* value, uint32_t dex_pc)
1833      : HExpression(value->GetType(), SideEffects::None()), dex_pc_(dex_pc) {
1834    SetRawInputAt(0, value);
1835  }
1836
1837  bool CanBeMoved() const OVERRIDE { return true; }
1838
1839  bool InstructionDataEquals(HInstruction* other) const OVERRIDE {
1840    UNUSED(other);
1841    return true;
1842  }
1843
1844  bool NeedsEnvironment() const OVERRIDE { return true; }
1845  bool CanThrow() const OVERRIDE { return true; }
1846
1847  uint32_t GetDexPc() const { return dex_pc_; }
1848
1849  DECLARE_INSTRUCTION(DivZeroCheck);
1850
1851 private:
1852  const uint32_t dex_pc_;
1853
1854  DISALLOW_COPY_AND_ASSIGN(HDivZeroCheck);
1855};
1856
1857class HShl : public HBinaryOperation {
1858 public:
1859  HShl(Primitive::Type result_type, HInstruction* left, HInstruction* right)
1860      : HBinaryOperation(result_type, left, right) {}
1861
1862  int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { return x << (y & kMaxIntShiftValue); }
1863  int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { return x << (y & kMaxLongShiftValue); }
1864
1865  DECLARE_INSTRUCTION(Shl);
1866
1867 private:
1868  DISALLOW_COPY_AND_ASSIGN(HShl);
1869};
1870
1871class HShr : public HBinaryOperation {
1872 public:
1873  HShr(Primitive::Type result_type, HInstruction* left, HInstruction* right)
1874      : HBinaryOperation(result_type, left, right) {}
1875
1876  int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { return x >> (y & kMaxIntShiftValue); }
1877  int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { return x >> (y & kMaxLongShiftValue); }
1878
1879  DECLARE_INSTRUCTION(Shr);
1880
1881 private:
1882  DISALLOW_COPY_AND_ASSIGN(HShr);
1883};
1884
1885class HUShr : public HBinaryOperation {
1886 public:
1887  HUShr(Primitive::Type result_type, HInstruction* left, HInstruction* right)
1888      : HBinaryOperation(result_type, left, right) {}
1889
1890  int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE {
1891    uint32_t ux = static_cast<uint32_t>(x);
1892    uint32_t uy = static_cast<uint32_t>(y) & kMaxIntShiftValue;
1893    return static_cast<int32_t>(ux >> uy);
1894  }
1895
1896  int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE {
1897    uint64_t ux = static_cast<uint64_t>(x);
1898    uint64_t uy = static_cast<uint64_t>(y) & kMaxLongShiftValue;
1899    return static_cast<int64_t>(ux >> uy);
1900  }
1901
1902  DECLARE_INSTRUCTION(UShr);
1903
1904 private:
1905  DISALLOW_COPY_AND_ASSIGN(HUShr);
1906};
1907
1908class HAnd : public HBinaryOperation {
1909 public:
1910  HAnd(Primitive::Type result_type, HInstruction* left, HInstruction* right)
1911      : HBinaryOperation(result_type, left, right) {}
1912
1913  bool IsCommutative() OVERRIDE { return true; }
1914
1915  int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { return x & y; }
1916  int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { return x & y; }
1917
1918  DECLARE_INSTRUCTION(And);
1919
1920 private:
1921  DISALLOW_COPY_AND_ASSIGN(HAnd);
1922};
1923
1924class HOr : public HBinaryOperation {
1925 public:
1926  HOr(Primitive::Type result_type, HInstruction* left, HInstruction* right)
1927      : HBinaryOperation(result_type, left, right) {}
1928
1929  bool IsCommutative() OVERRIDE { return true; }
1930
1931  int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { return x | y; }
1932  int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { return x | y; }
1933
1934  DECLARE_INSTRUCTION(Or);
1935
1936 private:
1937  DISALLOW_COPY_AND_ASSIGN(HOr);
1938};
1939
1940class HXor : public HBinaryOperation {
1941 public:
1942  HXor(Primitive::Type result_type, HInstruction* left, HInstruction* right)
1943      : HBinaryOperation(result_type, left, right) {}
1944
1945  bool IsCommutative() OVERRIDE { return true; }
1946
1947  int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { return x ^ y; }
1948  int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { return x ^ y; }
1949
1950  DECLARE_INSTRUCTION(Xor);
1951
1952 private:
1953  DISALLOW_COPY_AND_ASSIGN(HXor);
1954};
1955
1956// The value of a parameter in this method. Its location depends on
1957// the calling convention.
1958class HParameterValue : public HExpression<0> {
1959 public:
1960  HParameterValue(uint8_t index, Primitive::Type parameter_type)
1961      : HExpression(parameter_type, SideEffects::None()), index_(index) {}
1962
1963  uint8_t GetIndex() const { return index_; }
1964
1965  DECLARE_INSTRUCTION(ParameterValue);
1966
1967 private:
1968  // The index of this parameter in the parameters list. Must be less
1969  // than HGraph::number_of_in_vregs_;
1970  const uint8_t index_;
1971
1972  DISALLOW_COPY_AND_ASSIGN(HParameterValue);
1973};
1974
1975class HNot : public HUnaryOperation {
1976 public:
1977  explicit HNot(Primitive::Type result_type, HInstruction* input)
1978      : HUnaryOperation(result_type, input) {}
1979
1980  virtual bool CanBeMoved() const { return true; }
1981  virtual bool InstructionDataEquals(HInstruction* other) const {
1982    UNUSED(other);
1983    return true;
1984  }
1985
1986  virtual int32_t Evaluate(int32_t x) const OVERRIDE { return ~x; }
1987  virtual int64_t Evaluate(int64_t x) const OVERRIDE { return ~x; }
1988
1989  DECLARE_INSTRUCTION(Not);
1990
1991 private:
1992  DISALLOW_COPY_AND_ASSIGN(HNot);
1993};
1994
1995class HTypeConversion : public HExpression<1> {
1996 public:
1997  // Instantiate a type conversion of `input` to `result_type`.
1998  HTypeConversion(Primitive::Type result_type, HInstruction* input)
1999      : HExpression(result_type, SideEffects::None()) {
2000    SetRawInputAt(0, input);
2001    DCHECK_NE(input->GetType(), result_type);
2002  }
2003
2004  HInstruction* GetInput() const { return InputAt(0); }
2005  Primitive::Type GetInputType() const { return GetInput()->GetType(); }
2006  Primitive::Type GetResultType() const { return GetType(); }
2007
2008  bool CanBeMoved() const OVERRIDE { return true; }
2009  bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE { return true; }
2010
2011  DECLARE_INSTRUCTION(TypeConversion);
2012
2013 private:
2014  DISALLOW_COPY_AND_ASSIGN(HTypeConversion);
2015};
2016
2017class HPhi : public HInstruction {
2018 public:
2019  HPhi(ArenaAllocator* arena, uint32_t reg_number, size_t number_of_inputs, Primitive::Type type)
2020      : HInstruction(SideEffects::None()),
2021        inputs_(arena, number_of_inputs),
2022        reg_number_(reg_number),
2023        type_(type),
2024        is_live_(false) {
2025    inputs_.SetSize(number_of_inputs);
2026  }
2027
2028  virtual size_t InputCount() const { return inputs_.Size(); }
2029  virtual HInstruction* InputAt(size_t i) const { return inputs_.Get(i); }
2030
2031  virtual void SetRawInputAt(size_t index, HInstruction* input) {
2032    inputs_.Put(index, input);
2033  }
2034
2035  void AddInput(HInstruction* input);
2036
2037  virtual Primitive::Type GetType() const { return type_; }
2038  void SetType(Primitive::Type type) { type_ = type; }
2039
2040  uint32_t GetRegNumber() const { return reg_number_; }
2041
2042  void SetDead() { is_live_ = false; }
2043  void SetLive() { is_live_ = true; }
2044  bool IsDead() const { return !is_live_; }
2045  bool IsLive() const { return is_live_; }
2046
2047  DECLARE_INSTRUCTION(Phi);
2048
2049 private:
2050  GrowableArray<HInstruction*> inputs_;
2051  const uint32_t reg_number_;
2052  Primitive::Type type_;
2053  bool is_live_;
2054
2055  DISALLOW_COPY_AND_ASSIGN(HPhi);
2056};
2057
2058class HNullCheck : public HExpression<1> {
2059 public:
2060  HNullCheck(HInstruction* value, uint32_t dex_pc)
2061      : HExpression(value->GetType(), SideEffects::None()), dex_pc_(dex_pc) {
2062    SetRawInputAt(0, value);
2063  }
2064
2065  virtual bool CanBeMoved() const { return true; }
2066  virtual bool InstructionDataEquals(HInstruction* other) const {
2067    UNUSED(other);
2068    return true;
2069  }
2070
2071  virtual bool NeedsEnvironment() const { return true; }
2072
2073  virtual bool CanThrow() const { return true; }
2074
2075  uint32_t GetDexPc() const { return dex_pc_; }
2076
2077  DECLARE_INSTRUCTION(NullCheck);
2078
2079 private:
2080  const uint32_t dex_pc_;
2081
2082  DISALLOW_COPY_AND_ASSIGN(HNullCheck);
2083};
2084
2085class FieldInfo : public ValueObject {
2086 public:
2087  FieldInfo(MemberOffset field_offset, Primitive::Type field_type)
2088      : field_offset_(field_offset), field_type_(field_type) {}
2089
2090  MemberOffset GetFieldOffset() const { return field_offset_; }
2091  Primitive::Type GetFieldType() const { return field_type_; }
2092
2093 private:
2094  const MemberOffset field_offset_;
2095  const Primitive::Type field_type_;
2096};
2097
2098class HInstanceFieldGet : public HExpression<1> {
2099 public:
2100  HInstanceFieldGet(HInstruction* value,
2101                    Primitive::Type field_type,
2102                    MemberOffset field_offset)
2103      : HExpression(field_type, SideEffects::DependsOnSomething()),
2104        field_info_(field_offset, field_type) {
2105    SetRawInputAt(0, value);
2106  }
2107
2108  virtual bool CanBeMoved() const { return true; }
2109  virtual bool InstructionDataEquals(HInstruction* other) const {
2110    size_t other_offset = other->AsInstanceFieldGet()->GetFieldOffset().SizeValue();
2111    return other_offset == GetFieldOffset().SizeValue();
2112  }
2113
2114  virtual size_t ComputeHashCode() const {
2115    return (HInstruction::ComputeHashCode() << 7) | GetFieldOffset().SizeValue();
2116  }
2117
2118  MemberOffset GetFieldOffset() const { return field_info_.GetFieldOffset(); }
2119  Primitive::Type GetFieldType() const { return field_info_.GetFieldType(); }
2120
2121  DECLARE_INSTRUCTION(InstanceFieldGet);
2122
2123 private:
2124  const FieldInfo field_info_;
2125
2126  DISALLOW_COPY_AND_ASSIGN(HInstanceFieldGet);
2127};
2128
2129class HInstanceFieldSet : public HTemplateInstruction<2> {
2130 public:
2131  HInstanceFieldSet(HInstruction* object,
2132                    HInstruction* value,
2133                    Primitive::Type field_type,
2134                    MemberOffset field_offset)
2135      : HTemplateInstruction(SideEffects::ChangesSomething()),
2136        field_info_(field_offset, field_type) {
2137    SetRawInputAt(0, object);
2138    SetRawInputAt(1, value);
2139  }
2140
2141  MemberOffset GetFieldOffset() const { return field_info_.GetFieldOffset(); }
2142  Primitive::Type GetFieldType() const { return field_info_.GetFieldType(); }
2143
2144  HInstruction* GetValue() const { return InputAt(1); }
2145
2146  DECLARE_INSTRUCTION(InstanceFieldSet);
2147
2148 private:
2149  const FieldInfo field_info_;
2150
2151  DISALLOW_COPY_AND_ASSIGN(HInstanceFieldSet);
2152};
2153
2154class HArrayGet : public HExpression<2> {
2155 public:
2156  HArrayGet(HInstruction* array, HInstruction* index, Primitive::Type type)
2157      : HExpression(type, SideEffects::DependsOnSomething()) {
2158    SetRawInputAt(0, array);
2159    SetRawInputAt(1, index);
2160  }
2161
2162  bool CanBeMoved() const OVERRIDE { return true; }
2163  bool InstructionDataEquals(HInstruction* other) const OVERRIDE {
2164    UNUSED(other);
2165    return true;
2166  }
2167  void SetType(Primitive::Type type) { type_ = type; }
2168
2169  HInstruction* GetArray() const { return InputAt(0); }
2170  HInstruction* GetIndex() const { return InputAt(1); }
2171
2172  DECLARE_INSTRUCTION(ArrayGet);
2173
2174 private:
2175  DISALLOW_COPY_AND_ASSIGN(HArrayGet);
2176};
2177
2178class HArraySet : public HTemplateInstruction<3> {
2179 public:
2180  HArraySet(HInstruction* array,
2181            HInstruction* index,
2182            HInstruction* value,
2183            Primitive::Type expected_component_type,
2184            uint32_t dex_pc)
2185      : HTemplateInstruction(SideEffects::ChangesSomething()),
2186        dex_pc_(dex_pc),
2187        expected_component_type_(expected_component_type),
2188        needs_type_check_(value->GetType() == Primitive::kPrimNot) {
2189    SetRawInputAt(0, array);
2190    SetRawInputAt(1, index);
2191    SetRawInputAt(2, value);
2192  }
2193
2194  bool NeedsEnvironment() const {
2195    // We currently always call a runtime method to catch array store
2196    // exceptions.
2197    return needs_type_check_;
2198  }
2199
2200  void ClearNeedsTypeCheck() {
2201    needs_type_check_ = false;
2202  }
2203
2204  bool NeedsTypeCheck() const { return needs_type_check_; }
2205
2206  uint32_t GetDexPc() const { return dex_pc_; }
2207
2208  HInstruction* GetArray() const { return InputAt(0); }
2209  HInstruction* GetIndex() const { return InputAt(1); }
2210  HInstruction* GetValue() const { return InputAt(2); }
2211
2212  Primitive::Type GetComponentType() const {
2213    // The Dex format does not type floating point index operations. Since the
2214    // `expected_component_type_` is set during building and can therefore not
2215    // be correct, we also check what is the value type. If it is a floating
2216    // point type, we must use that type.
2217    Primitive::Type value_type = GetValue()->GetType();
2218    return ((value_type == Primitive::kPrimFloat) || (value_type == Primitive::kPrimDouble))
2219        ? value_type
2220        : expected_component_type_;
2221  }
2222
2223  DECLARE_INSTRUCTION(ArraySet);
2224
2225 private:
2226  const uint32_t dex_pc_;
2227  const Primitive::Type expected_component_type_;
2228  bool needs_type_check_;
2229
2230  DISALLOW_COPY_AND_ASSIGN(HArraySet);
2231};
2232
2233class HArrayLength : public HExpression<1> {
2234 public:
2235  explicit HArrayLength(HInstruction* array)
2236      : HExpression(Primitive::kPrimInt, SideEffects::None()) {
2237    // Note that arrays do not change length, so the instruction does not
2238    // depend on any write.
2239    SetRawInputAt(0, array);
2240  }
2241
2242  virtual bool CanBeMoved() const { return true; }
2243  virtual bool InstructionDataEquals(HInstruction* other) const {
2244    UNUSED(other);
2245    return true;
2246  }
2247
2248  DECLARE_INSTRUCTION(ArrayLength);
2249
2250 private:
2251  DISALLOW_COPY_AND_ASSIGN(HArrayLength);
2252};
2253
2254class HBoundsCheck : public HExpression<2> {
2255 public:
2256  HBoundsCheck(HInstruction* index, HInstruction* length, uint32_t dex_pc)
2257      : HExpression(index->GetType(), SideEffects::None()), dex_pc_(dex_pc) {
2258    DCHECK(index->GetType() == Primitive::kPrimInt);
2259    SetRawInputAt(0, index);
2260    SetRawInputAt(1, length);
2261  }
2262
2263  virtual bool CanBeMoved() const { return true; }
2264  virtual bool InstructionDataEquals(HInstruction* other) const {
2265    UNUSED(other);
2266    return true;
2267  }
2268
2269  virtual bool NeedsEnvironment() const { return true; }
2270
2271  virtual bool CanThrow() const { return true; }
2272
2273  uint32_t GetDexPc() const { return dex_pc_; }
2274
2275  DECLARE_INSTRUCTION(BoundsCheck);
2276
2277 private:
2278  const uint32_t dex_pc_;
2279
2280  DISALLOW_COPY_AND_ASSIGN(HBoundsCheck);
2281};
2282
2283/**
2284 * Some DEX instructions are folded into multiple HInstructions that need
2285 * to stay live until the last HInstruction. This class
2286 * is used as a marker for the baseline compiler to ensure its preceding
2287 * HInstruction stays live. `index` represents the stack location index of the
2288 * instruction (the actual offset is computed as index * vreg_size).
2289 */
2290class HTemporary : public HTemplateInstruction<0> {
2291 public:
2292  explicit HTemporary(size_t index) : HTemplateInstruction(SideEffects::None()), index_(index) {}
2293
2294  size_t GetIndex() const { return index_; }
2295
2296  Primitive::Type GetType() const OVERRIDE {
2297    // The previous instruction is the one that will be stored in the temporary location.
2298    DCHECK(GetPrevious() != nullptr);
2299    return GetPrevious()->GetType();
2300  }
2301
2302  DECLARE_INSTRUCTION(Temporary);
2303
2304 private:
2305  const size_t index_;
2306
2307  DISALLOW_COPY_AND_ASSIGN(HTemporary);
2308};
2309
2310class HSuspendCheck : public HTemplateInstruction<0> {
2311 public:
2312  explicit HSuspendCheck(uint32_t dex_pc)
2313      : HTemplateInstruction(SideEffects::None()), dex_pc_(dex_pc) {}
2314
2315  virtual bool NeedsEnvironment() const {
2316    return true;
2317  }
2318
2319  uint32_t GetDexPc() const { return dex_pc_; }
2320
2321  DECLARE_INSTRUCTION(SuspendCheck);
2322
2323 private:
2324  const uint32_t dex_pc_;
2325
2326  DISALLOW_COPY_AND_ASSIGN(HSuspendCheck);
2327};
2328
2329/**
2330 * Instruction to load a Class object.
2331 */
2332class HLoadClass : public HExpression<0> {
2333 public:
2334  HLoadClass(uint16_t type_index,
2335             bool is_referrers_class,
2336             uint32_t dex_pc)
2337      : HExpression(Primitive::kPrimNot, SideEffects::None()),
2338        type_index_(type_index),
2339        is_referrers_class_(is_referrers_class),
2340        dex_pc_(dex_pc),
2341        generate_clinit_check_(false) {}
2342
2343  bool CanBeMoved() const OVERRIDE { return true; }
2344
2345  bool InstructionDataEquals(HInstruction* other) const OVERRIDE {
2346    return other->AsLoadClass()->type_index_ == type_index_;
2347  }
2348
2349  size_t ComputeHashCode() const OVERRIDE { return type_index_; }
2350
2351  uint32_t GetDexPc() const { return dex_pc_; }
2352  uint16_t GetTypeIndex() const { return type_index_; }
2353  bool IsReferrersClass() const { return is_referrers_class_; }
2354
2355  bool NeedsEnvironment() const OVERRIDE {
2356    // Will call runtime and load the class if the class is not loaded yet.
2357    // TODO: finer grain decision.
2358    return !is_referrers_class_;
2359  }
2360
2361  bool MustGenerateClinitCheck() const {
2362    return generate_clinit_check_;
2363  }
2364
2365  void SetMustGenerateClinitCheck() {
2366    generate_clinit_check_ = true;
2367  }
2368
2369  bool CanCallRuntime() const {
2370    return MustGenerateClinitCheck() || !is_referrers_class_;
2371  }
2372
2373  DECLARE_INSTRUCTION(LoadClass);
2374
2375 private:
2376  const uint16_t type_index_;
2377  const bool is_referrers_class_;
2378  const uint32_t dex_pc_;
2379  // Whether this instruction must generate the initialization check.
2380  // Used for code generation.
2381  bool generate_clinit_check_;
2382
2383  DISALLOW_COPY_AND_ASSIGN(HLoadClass);
2384};
2385
2386class HLoadString : public HExpression<0> {
2387 public:
2388  HLoadString(uint32_t string_index, uint32_t dex_pc)
2389      : HExpression(Primitive::kPrimNot, SideEffects::None()),
2390        string_index_(string_index),
2391        dex_pc_(dex_pc) {}
2392
2393  bool CanBeMoved() const OVERRIDE { return true; }
2394
2395  bool InstructionDataEquals(HInstruction* other) const OVERRIDE {
2396    return other->AsLoadString()->string_index_ == string_index_;
2397  }
2398
2399  size_t ComputeHashCode() const OVERRIDE { return string_index_; }
2400
2401  uint32_t GetDexPc() const { return dex_pc_; }
2402  uint32_t GetStringIndex() const { return string_index_; }
2403
2404  // TODO: Can we deopt or debug when we resolve a string?
2405  bool NeedsEnvironment() const OVERRIDE { return false; }
2406
2407  DECLARE_INSTRUCTION(LoadString);
2408
2409 private:
2410  const uint32_t string_index_;
2411  const uint32_t dex_pc_;
2412
2413  DISALLOW_COPY_AND_ASSIGN(HLoadString);
2414};
2415
2416// TODO: Pass this check to HInvokeStatic nodes.
2417/**
2418 * Performs an initialization check on its Class object input.
2419 */
2420class HClinitCheck : public HExpression<1> {
2421 public:
2422  explicit HClinitCheck(HLoadClass* constant, uint32_t dex_pc)
2423      : HExpression(Primitive::kPrimNot, SideEffects::All()),
2424        dex_pc_(dex_pc) {
2425    SetRawInputAt(0, constant);
2426  }
2427
2428  bool CanBeMoved() const OVERRIDE { return true; }
2429  bool InstructionDataEquals(HInstruction* other) const OVERRIDE {
2430    UNUSED(other);
2431    return true;
2432  }
2433
2434  bool NeedsEnvironment() const OVERRIDE {
2435    // May call runtime to initialize the class.
2436    return true;
2437  }
2438
2439  uint32_t GetDexPc() const { return dex_pc_; }
2440
2441  HLoadClass* GetLoadClass() const { return InputAt(0)->AsLoadClass(); }
2442
2443  DECLARE_INSTRUCTION(ClinitCheck);
2444
2445 private:
2446  const uint32_t dex_pc_;
2447
2448  DISALLOW_COPY_AND_ASSIGN(HClinitCheck);
2449};
2450
2451class HStaticFieldGet : public HExpression<1> {
2452 public:
2453  HStaticFieldGet(HInstruction* cls,
2454                  Primitive::Type field_type,
2455                  MemberOffset field_offset)
2456      : HExpression(field_type, SideEffects::DependsOnSomething()),
2457        field_info_(field_offset, field_type) {
2458    SetRawInputAt(0, cls);
2459  }
2460
2461  bool CanBeMoved() const OVERRIDE { return true; }
2462  bool InstructionDataEquals(HInstruction* other) const OVERRIDE {
2463    size_t other_offset = other->AsStaticFieldGet()->GetFieldOffset().SizeValue();
2464    return other_offset == GetFieldOffset().SizeValue();
2465  }
2466
2467  size_t ComputeHashCode() const OVERRIDE {
2468    return (HInstruction::ComputeHashCode() << 7) | GetFieldOffset().SizeValue();
2469  }
2470
2471  MemberOffset GetFieldOffset() const { return field_info_.GetFieldOffset(); }
2472  Primitive::Type GetFieldType() const { return field_info_.GetFieldType(); }
2473
2474  DECLARE_INSTRUCTION(StaticFieldGet);
2475
2476 private:
2477  const FieldInfo field_info_;
2478
2479  DISALLOW_COPY_AND_ASSIGN(HStaticFieldGet);
2480};
2481
2482class HStaticFieldSet : public HTemplateInstruction<2> {
2483 public:
2484  HStaticFieldSet(HInstruction* cls,
2485                  HInstruction* value,
2486                  Primitive::Type field_type,
2487                  MemberOffset field_offset)
2488      : HTemplateInstruction(SideEffects::ChangesSomething()),
2489        field_info_(field_offset, field_type) {
2490    SetRawInputAt(0, cls);
2491    SetRawInputAt(1, value);
2492  }
2493
2494  MemberOffset GetFieldOffset() const { return field_info_.GetFieldOffset(); }
2495  Primitive::Type GetFieldType() const { return field_info_.GetFieldType(); }
2496
2497  HInstruction* GetValue() const { return InputAt(1); }
2498
2499  DECLARE_INSTRUCTION(StaticFieldSet);
2500
2501 private:
2502  const FieldInfo field_info_;
2503
2504  DISALLOW_COPY_AND_ASSIGN(HStaticFieldSet);
2505};
2506
2507// Implement the move-exception DEX instruction.
2508class HLoadException : public HExpression<0> {
2509 public:
2510  HLoadException() : HExpression(Primitive::kPrimNot, SideEffects::None()) {}
2511
2512  DECLARE_INSTRUCTION(LoadException);
2513
2514 private:
2515  DISALLOW_COPY_AND_ASSIGN(HLoadException);
2516};
2517
2518class HThrow : public HTemplateInstruction<1> {
2519 public:
2520  HThrow(HInstruction* exception, uint32_t dex_pc)
2521      : HTemplateInstruction(SideEffects::None()), dex_pc_(dex_pc) {
2522    SetRawInputAt(0, exception);
2523  }
2524
2525  bool IsControlFlow() const OVERRIDE { return true; }
2526
2527  bool NeedsEnvironment() const OVERRIDE { return true; }
2528
2529  uint32_t GetDexPc() const { return dex_pc_; }
2530
2531  DECLARE_INSTRUCTION(Throw);
2532
2533 private:
2534  uint32_t dex_pc_;
2535
2536  DISALLOW_COPY_AND_ASSIGN(HThrow);
2537};
2538
2539class HInstanceOf : public HExpression<2> {
2540 public:
2541  HInstanceOf(HInstruction* object,
2542              HLoadClass* constant,
2543              bool class_is_final,
2544              uint32_t dex_pc)
2545      : HExpression(Primitive::kPrimBoolean, SideEffects::None()),
2546        class_is_final_(class_is_final),
2547        dex_pc_(dex_pc) {
2548    SetRawInputAt(0, object);
2549    SetRawInputAt(1, constant);
2550  }
2551
2552  bool CanBeMoved() const OVERRIDE { return true; }
2553
2554  bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE {
2555    return true;
2556  }
2557
2558  bool NeedsEnvironment() const OVERRIDE {
2559    return false;
2560  }
2561
2562  uint32_t GetDexPc() const { return dex_pc_; }
2563
2564  bool IsClassFinal() const { return class_is_final_; }
2565
2566  DECLARE_INSTRUCTION(InstanceOf);
2567
2568 private:
2569  const bool class_is_final_;
2570  const uint32_t dex_pc_;
2571
2572  DISALLOW_COPY_AND_ASSIGN(HInstanceOf);
2573};
2574
2575class HCheckCast : public HTemplateInstruction<2> {
2576 public:
2577  HCheckCast(HInstruction* object,
2578             HLoadClass* constant,
2579             bool class_is_final,
2580             uint32_t dex_pc)
2581      : HTemplateInstruction(SideEffects::None()),
2582        class_is_final_(class_is_final),
2583        dex_pc_(dex_pc) {
2584    SetRawInputAt(0, object);
2585    SetRawInputAt(1, constant);
2586  }
2587
2588  bool CanBeMoved() const OVERRIDE { return true; }
2589
2590  bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE {
2591    return true;
2592  }
2593
2594  bool NeedsEnvironment() const OVERRIDE {
2595    // Instruction may throw a CheckCastError.
2596    return true;
2597  }
2598
2599  bool CanThrow() const OVERRIDE { return true; }
2600
2601  uint32_t GetDexPc() const { return dex_pc_; }
2602
2603  bool IsClassFinal() const { return class_is_final_; }
2604
2605  DECLARE_INSTRUCTION(CheckCast);
2606
2607 private:
2608  const bool class_is_final_;
2609  const uint32_t dex_pc_;
2610
2611  DISALLOW_COPY_AND_ASSIGN(HCheckCast);
2612};
2613
2614class HMonitorOperation : public HTemplateInstruction<1> {
2615 public:
2616  enum OperationKind {
2617    kEnter,
2618    kExit,
2619  };
2620
2621  HMonitorOperation(HInstruction* object, OperationKind kind, uint32_t dex_pc)
2622    : HTemplateInstruction(SideEffects::None()), kind_(kind), dex_pc_(dex_pc) {
2623    SetRawInputAt(0, object);
2624  }
2625
2626  // Instruction may throw a Java exception, so we need an environment.
2627  bool NeedsEnvironment() const OVERRIDE { return true; }
2628  bool CanThrow() const OVERRIDE { return true; }
2629
2630  uint32_t GetDexPc() const { return dex_pc_; }
2631
2632  bool IsEnter() const { return kind_ == kEnter; }
2633
2634  DECLARE_INSTRUCTION(MonitorOperation);
2635
2636 protected:
2637  const OperationKind kind_;
2638  const uint32_t dex_pc_;
2639
2640 private:
2641  DISALLOW_COPY_AND_ASSIGN(HMonitorOperation);
2642};
2643
2644
2645class MoveOperands : public ArenaObject<kArenaAllocMisc> {
2646 public:
2647  MoveOperands(Location source, Location destination, HInstruction* instruction)
2648      : source_(source), destination_(destination), instruction_(instruction) {}
2649
2650  Location GetSource() const { return source_; }
2651  Location GetDestination() const { return destination_; }
2652
2653  void SetSource(Location value) { source_ = value; }
2654  void SetDestination(Location value) { destination_ = value; }
2655
2656  // The parallel move resolver marks moves as "in-progress" by clearing the
2657  // destination (but not the source).
2658  Location MarkPending() {
2659    DCHECK(!IsPending());
2660    Location dest = destination_;
2661    destination_ = Location::NoLocation();
2662    return dest;
2663  }
2664
2665  void ClearPending(Location dest) {
2666    DCHECK(IsPending());
2667    destination_ = dest;
2668  }
2669
2670  bool IsPending() const {
2671    DCHECK(!source_.IsInvalid() || destination_.IsInvalid());
2672    return destination_.IsInvalid() && !source_.IsInvalid();
2673  }
2674
2675  // True if this blocks a move from the given location.
2676  bool Blocks(Location loc) const {
2677    return !IsEliminated() && source_.Equals(loc);
2678  }
2679
2680  // A move is redundant if it's been eliminated, if its source and
2681  // destination are the same, or if its destination is unneeded.
2682  bool IsRedundant() const {
2683    return IsEliminated() || destination_.IsInvalid() || source_.Equals(destination_);
2684  }
2685
2686  // We clear both operands to indicate move that's been eliminated.
2687  void Eliminate() {
2688    source_ = destination_ = Location::NoLocation();
2689  }
2690
2691  bool IsEliminated() const {
2692    DCHECK(!source_.IsInvalid() || destination_.IsInvalid());
2693    return source_.IsInvalid();
2694  }
2695
2696  HInstruction* GetInstruction() const { return instruction_; }
2697
2698 private:
2699  Location source_;
2700  Location destination_;
2701  // The instruction this move is assocatied with. Null when this move is
2702  // for moving an input in the expected locations of user (including a phi user).
2703  // This is only used in debug mode, to ensure we do not connect interval siblings
2704  // in the same parallel move.
2705  HInstruction* instruction_;
2706
2707  DISALLOW_COPY_AND_ASSIGN(MoveOperands);
2708};
2709
2710static constexpr size_t kDefaultNumberOfMoves = 4;
2711
2712class HParallelMove : public HTemplateInstruction<0> {
2713 public:
2714  explicit HParallelMove(ArenaAllocator* arena)
2715      : HTemplateInstruction(SideEffects::None()), moves_(arena, kDefaultNumberOfMoves) {}
2716
2717  void AddMove(MoveOperands* move) {
2718    if (kIsDebugBuild && move->GetInstruction() != nullptr) {
2719      for (size_t i = 0, e = moves_.Size(); i < e; ++i) {
2720        DCHECK_NE(moves_.Get(i)->GetInstruction(), move->GetInstruction())
2721          << "Doing parallel moves for the same instruction.";
2722      }
2723    }
2724    moves_.Add(move);
2725  }
2726
2727  MoveOperands* MoveOperandsAt(size_t index) const {
2728    return moves_.Get(index);
2729  }
2730
2731  size_t NumMoves() const { return moves_.Size(); }
2732
2733  DECLARE_INSTRUCTION(ParallelMove);
2734
2735 private:
2736  GrowableArray<MoveOperands*> moves_;
2737
2738  DISALLOW_COPY_AND_ASSIGN(HParallelMove);
2739};
2740
2741class HGraphVisitor : public ValueObject {
2742 public:
2743  explicit HGraphVisitor(HGraph* graph) : graph_(graph) {}
2744  virtual ~HGraphVisitor() {}
2745
2746  virtual void VisitInstruction(HInstruction* instruction) { UNUSED(instruction); }
2747  virtual void VisitBasicBlock(HBasicBlock* block);
2748
2749  // Visit the graph following basic block insertion order.
2750  void VisitInsertionOrder();
2751
2752  // Visit the graph following dominator tree reverse post-order.
2753  void VisitReversePostOrder();
2754
2755  HGraph* GetGraph() const { return graph_; }
2756
2757  // Visit functions for instruction classes.
2758#define DECLARE_VISIT_INSTRUCTION(name, super)                                        \
2759  virtual void Visit##name(H##name* instr) { VisitInstruction(instr); }
2760
2761  FOR_EACH_INSTRUCTION(DECLARE_VISIT_INSTRUCTION)
2762
2763#undef DECLARE_VISIT_INSTRUCTION
2764
2765 private:
2766  HGraph* const graph_;
2767
2768  DISALLOW_COPY_AND_ASSIGN(HGraphVisitor);
2769};
2770
2771class HGraphDelegateVisitor : public HGraphVisitor {
2772 public:
2773  explicit HGraphDelegateVisitor(HGraph* graph) : HGraphVisitor(graph) {}
2774  virtual ~HGraphDelegateVisitor() {}
2775
2776  // Visit functions that delegate to to super class.
2777#define DECLARE_VISIT_INSTRUCTION(name, super)                                        \
2778  virtual void Visit##name(H##name* instr) OVERRIDE { Visit##super(instr); }
2779
2780  FOR_EACH_INSTRUCTION(DECLARE_VISIT_INSTRUCTION)
2781
2782#undef DECLARE_VISIT_INSTRUCTION
2783
2784 private:
2785  DISALLOW_COPY_AND_ASSIGN(HGraphDelegateVisitor);
2786};
2787
2788class HInsertionOrderIterator : public ValueObject {
2789 public:
2790  explicit HInsertionOrderIterator(const HGraph& graph) : graph_(graph), index_(0) {}
2791
2792  bool Done() const { return index_ == graph_.GetBlocks().Size(); }
2793  HBasicBlock* Current() const { return graph_.GetBlocks().Get(index_); }
2794  void Advance() { ++index_; }
2795
2796 private:
2797  const HGraph& graph_;
2798  size_t index_;
2799
2800  DISALLOW_COPY_AND_ASSIGN(HInsertionOrderIterator);
2801};
2802
2803class HReversePostOrderIterator : public ValueObject {
2804 public:
2805  explicit HReversePostOrderIterator(const HGraph& graph) : graph_(graph), index_(0) {}
2806
2807  bool Done() const { return index_ == graph_.GetReversePostOrder().Size(); }
2808  HBasicBlock* Current() const { return graph_.GetReversePostOrder().Get(index_); }
2809  void Advance() { ++index_; }
2810
2811 private:
2812  const HGraph& graph_;
2813  size_t index_;
2814
2815  DISALLOW_COPY_AND_ASSIGN(HReversePostOrderIterator);
2816};
2817
2818class HPostOrderIterator : public ValueObject {
2819 public:
2820  explicit HPostOrderIterator(const HGraph& graph)
2821      : graph_(graph), index_(graph_.GetReversePostOrder().Size()) {}
2822
2823  bool Done() const { return index_ == 0; }
2824  HBasicBlock* Current() const { return graph_.GetReversePostOrder().Get(index_ - 1); }
2825  void Advance() { --index_; }
2826
2827 private:
2828  const HGraph& graph_;
2829  size_t index_;
2830
2831  DISALLOW_COPY_AND_ASSIGN(HPostOrderIterator);
2832};
2833
2834}  // namespace art
2835
2836#endif  // ART_COMPILER_OPTIMIZING_NODES_H_
2837