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