nodes.h revision 0c365e674545159fd77b998081207f0685a605e5
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 "base/arena_containers.h"
21#include "base/arena_object.h"
22#include "entrypoints/quick/quick_entrypoints_enum.h"
23#include "handle.h"
24#include "handle_scope.h"
25#include "invoke_type.h"
26#include "locations.h"
27#include "mirror/class.h"
28#include "offsets.h"
29#include "primitive.h"
30#include "utils/arena_bit_vector.h"
31#include "utils/growable_array.h"
32
33namespace art {
34
35class GraphChecker;
36class HBasicBlock;
37class HDoubleConstant;
38class HEnvironment;
39class HFloatConstant;
40class HGraphVisitor;
41class HInstruction;
42class HIntConstant;
43class HInvoke;
44class HLongConstant;
45class HNullConstant;
46class HPhi;
47class HSuspendCheck;
48class LiveInterval;
49class LocationSummary;
50class SsaBuilder;
51
52static const int kDefaultNumberOfBlocks = 8;
53static const int kDefaultNumberOfSuccessors = 2;
54static const int kDefaultNumberOfPredecessors = 2;
55static const int kDefaultNumberOfDominatedBlocks = 1;
56static const int kDefaultNumberOfBackEdges = 1;
57
58static constexpr uint32_t kMaxIntShiftValue = 0x1f;
59static constexpr uint64_t kMaxLongShiftValue = 0x3f;
60
61enum IfCondition {
62  kCondEQ,
63  kCondNE,
64  kCondLT,
65  kCondLE,
66  kCondGT,
67  kCondGE,
68};
69
70class HInstructionList {
71 public:
72  HInstructionList() : first_instruction_(nullptr), last_instruction_(nullptr) {}
73
74  void AddInstruction(HInstruction* instruction);
75  void RemoveInstruction(HInstruction* instruction);
76
77  // Return true if this list contains `instruction`.
78  bool Contains(HInstruction* instruction) const;
79
80  // Return true if `instruction1` is found before `instruction2` in
81  // this instruction list and false otherwise.  Abort if none
82  // of these instructions is found.
83  bool FoundBefore(const HInstruction* instruction1,
84                   const HInstruction* instruction2) const;
85
86  bool IsEmpty() const { return first_instruction_ == nullptr; }
87  void Clear() { first_instruction_ = last_instruction_ = nullptr; }
88
89  // Update the block of all instructions to be `block`.
90  void SetBlockOfInstructions(HBasicBlock* block) const;
91
92  void AddAfter(HInstruction* cursor, const HInstructionList& instruction_list);
93  void Add(const HInstructionList& instruction_list);
94
95 private:
96  HInstruction* first_instruction_;
97  HInstruction* last_instruction_;
98
99  friend class HBasicBlock;
100  friend class HGraph;
101  friend class HInstruction;
102  friend class HInstructionIterator;
103  friend class HBackwardInstructionIterator;
104
105  DISALLOW_COPY_AND_ASSIGN(HInstructionList);
106};
107
108// Control-flow graph of a method. Contains a list of basic blocks.
109class HGraph : public ArenaObject<kArenaAllocMisc> {
110 public:
111  HGraph(ArenaAllocator* arena, bool debuggable = false, int start_instruction_id = 0)
112      : arena_(arena),
113        blocks_(arena, kDefaultNumberOfBlocks),
114        reverse_post_order_(arena, kDefaultNumberOfBlocks),
115        entry_block_(nullptr),
116        exit_block_(nullptr),
117        maximum_number_of_out_vregs_(0),
118        number_of_vregs_(0),
119        number_of_in_vregs_(0),
120        temporaries_vreg_slots_(0),
121        has_array_accesses_(false),
122        debuggable_(debuggable),
123        current_instruction_id_(start_instruction_id),
124        cached_null_constant_(nullptr),
125        cached_int_constants_(std::less<int32_t>(), arena->Adapter()),
126        cached_long_constants_(std::less<int64_t>(), arena->Adapter()) {}
127
128  ArenaAllocator* GetArena() const { return arena_; }
129  const GrowableArray<HBasicBlock*>& GetBlocks() const { return blocks_; }
130  HBasicBlock* GetBlock(size_t id) const { return blocks_.Get(id); }
131
132  HBasicBlock* GetEntryBlock() const { return entry_block_; }
133  HBasicBlock* GetExitBlock() const { return exit_block_; }
134
135  void SetEntryBlock(HBasicBlock* block) { entry_block_ = block; }
136  void SetExitBlock(HBasicBlock* block) { exit_block_ = block; }
137
138  void AddBlock(HBasicBlock* block);
139
140  // Try building the SSA form of this graph, with dominance computation and loop
141  // recognition. Returns whether it was successful in doing all these steps.
142  bool TryBuildingSsa() {
143    BuildDominatorTree();
144    // The SSA builder requires loops to all be natural. Specifically, the dead phi
145    // elimination phase checks the consistency of the graph when doing a post-order
146    // visit for eliminating dead phis: a dead phi can only have loop header phi
147    // users remaining when being visited.
148    if (!AnalyzeNaturalLoops()) return false;
149    TransformToSsa();
150    return true;
151  }
152
153  void BuildDominatorTree();
154  void TransformToSsa();
155  void SimplifyCFG();
156
157  // Analyze all natural loops in this graph. Returns false if one
158  // loop is not natural, that is the header does not dominate the
159  // back edge.
160  bool AnalyzeNaturalLoops() const;
161
162  // Inline this graph in `outer_graph`, replacing the given `invoke` instruction.
163  void InlineInto(HGraph* outer_graph, HInvoke* invoke);
164
165  void MergeEmptyBranches(HBasicBlock* start_block, HBasicBlock* end_block);
166
167  void SplitCriticalEdge(HBasicBlock* block, HBasicBlock* successor);
168  void SimplifyLoop(HBasicBlock* header);
169
170  int32_t GetNextInstructionId() {
171    DCHECK_NE(current_instruction_id_, INT32_MAX);
172    return current_instruction_id_++;
173  }
174
175  int32_t GetCurrentInstructionId() const {
176    return current_instruction_id_;
177  }
178
179  void SetCurrentInstructionId(int32_t id) {
180    current_instruction_id_ = id;
181  }
182
183  uint16_t GetMaximumNumberOfOutVRegs() const {
184    return maximum_number_of_out_vregs_;
185  }
186
187  void SetMaximumNumberOfOutVRegs(uint16_t new_value) {
188    maximum_number_of_out_vregs_ = new_value;
189  }
190
191  void UpdateTemporariesVRegSlots(size_t slots) {
192    temporaries_vreg_slots_ = std::max(slots, temporaries_vreg_slots_);
193  }
194
195  size_t GetTemporariesVRegSlots() const {
196    return temporaries_vreg_slots_;
197  }
198
199  void SetNumberOfVRegs(uint16_t number_of_vregs) {
200    number_of_vregs_ = number_of_vregs;
201  }
202
203  uint16_t GetNumberOfVRegs() const {
204    return number_of_vregs_;
205  }
206
207  void SetNumberOfInVRegs(uint16_t value) {
208    number_of_in_vregs_ = value;
209  }
210
211  uint16_t GetNumberOfLocalVRegs() const {
212    return number_of_vregs_ - number_of_in_vregs_;
213  }
214
215  const GrowableArray<HBasicBlock*>& GetReversePostOrder() const {
216    return reverse_post_order_;
217  }
218
219  bool HasArrayAccesses() const {
220    return has_array_accesses_;
221  }
222
223  void SetHasArrayAccesses(bool value) {
224    has_array_accesses_ = value;
225  }
226
227  bool IsDebuggable() const { return debuggable_; }
228
229  // Returns a constant of the given type and value. If it does not exist
230  // already, it is created and inserted into the graph. Only integral types
231  // are currently supported.
232  HConstant* GetConstant(Primitive::Type type, int64_t value);
233  HNullConstant* GetNullConstant();
234  HIntConstant* GetIntConstant(int32_t value) {
235    return CreateConstant(value, &cached_int_constants_);
236  }
237  HLongConstant* GetLongConstant(int64_t value) {
238    return CreateConstant(value, &cached_long_constants_);
239  }
240
241 private:
242  HBasicBlock* FindCommonDominator(HBasicBlock* first, HBasicBlock* second) const;
243  void VisitBlockForDominatorTree(HBasicBlock* block,
244                                  HBasicBlock* predecessor,
245                                  GrowableArray<size_t>* visits);
246  void FindBackEdges(ArenaBitVector* visited);
247  void VisitBlockForBackEdges(HBasicBlock* block,
248                              ArenaBitVector* visited,
249                              ArenaBitVector* visiting);
250  void RemoveInstructionsAsUsersFromDeadBlocks(const ArenaBitVector& visited) const;
251  void RemoveDeadBlocks(const ArenaBitVector& visited) const;
252
253  template <class InstType, typename ValueType>
254  InstType* CreateConstant(ValueType value, ArenaSafeMap<ValueType, InstType*>* cache);
255  void InsertConstant(HConstant* instruction);
256
257  ArenaAllocator* const arena_;
258
259  // List of blocks in insertion order.
260  GrowableArray<HBasicBlock*> blocks_;
261
262  // List of blocks to perform a reverse post order tree traversal.
263  GrowableArray<HBasicBlock*> reverse_post_order_;
264
265  HBasicBlock* entry_block_;
266  HBasicBlock* exit_block_;
267
268  // The maximum number of virtual registers arguments passed to a HInvoke in this graph.
269  uint16_t maximum_number_of_out_vregs_;
270
271  // The number of virtual registers in this method. Contains the parameters.
272  uint16_t number_of_vregs_;
273
274  // The number of virtual registers used by parameters of this method.
275  uint16_t number_of_in_vregs_;
276
277  // Number of vreg size slots that the temporaries use (used in baseline compiler).
278  size_t temporaries_vreg_slots_;
279
280  // Has array accesses. We can totally skip BCE if it's false.
281  bool has_array_accesses_;
282
283  // Indicates whether the graph should be compiled in a way that
284  // ensures full debuggability. If false, we can apply more
285  // aggressive optimizations that may limit the level of debugging.
286  const bool debuggable_;
287
288  // The current id to assign to a newly added instruction. See HInstruction.id_.
289  int32_t current_instruction_id_;
290
291  // Cached common constants often needed by optimization passes.
292  HNullConstant* cached_null_constant_;
293  ArenaSafeMap<int32_t, HIntConstant*> cached_int_constants_;
294  ArenaSafeMap<int64_t, HLongConstant*> cached_long_constants_;
295
296  ART_FRIEND_TEST(GraphTest, IfSuccessorSimpleJoinBlock1);
297  DISALLOW_COPY_AND_ASSIGN(HGraph);
298};
299
300class HLoopInformation : public ArenaObject<kArenaAllocMisc> {
301 public:
302  HLoopInformation(HBasicBlock* header, HGraph* graph)
303      : header_(header),
304        suspend_check_(nullptr),
305        back_edges_(graph->GetArena(), kDefaultNumberOfBackEdges),
306        // Make bit vector growable, as the number of blocks may change.
307        blocks_(graph->GetArena(), graph->GetBlocks().Size(), true) {}
308
309  HBasicBlock* GetHeader() const {
310    return header_;
311  }
312
313  void SetHeader(HBasicBlock* block) {
314    header_ = block;
315  }
316
317  HSuspendCheck* GetSuspendCheck() const { return suspend_check_; }
318  void SetSuspendCheck(HSuspendCheck* check) { suspend_check_ = check; }
319  bool HasSuspendCheck() const { return suspend_check_ != nullptr; }
320
321  void AddBackEdge(HBasicBlock* back_edge) {
322    back_edges_.Add(back_edge);
323  }
324
325  void RemoveBackEdge(HBasicBlock* back_edge) {
326    back_edges_.Delete(back_edge);
327  }
328
329  bool IsBackEdge(const HBasicBlock& block) const {
330    for (size_t i = 0, e = back_edges_.Size(); i < e; ++i) {
331      if (back_edges_.Get(i) == &block) return true;
332    }
333    return false;
334  }
335
336  size_t NumberOfBackEdges() const {
337    return back_edges_.Size();
338  }
339
340  HBasicBlock* GetPreHeader() const;
341
342  const GrowableArray<HBasicBlock*>& GetBackEdges() const {
343    return back_edges_;
344  }
345
346  void ClearBackEdges() {
347    back_edges_.Reset();
348  }
349
350  // Find blocks that are part of this loop. Returns whether the loop is a natural loop,
351  // that is the header dominates the back edge.
352  bool Populate();
353
354  // Returns whether this loop information contains `block`.
355  // Note that this loop information *must* be populated before entering this function.
356  bool Contains(const HBasicBlock& block) const;
357
358  // Returns whether this loop information is an inner loop of `other`.
359  // Note that `other` *must* be populated before entering this function.
360  bool IsIn(const HLoopInformation& other) const;
361
362  const ArenaBitVector& GetBlocks() const { return blocks_; }
363
364  void Add(HBasicBlock* block);
365  void Remove(HBasicBlock* block);
366
367 private:
368  // Internal recursive implementation of `Populate`.
369  void PopulateRecursive(HBasicBlock* block);
370
371  HBasicBlock* header_;
372  HSuspendCheck* suspend_check_;
373  GrowableArray<HBasicBlock*> back_edges_;
374  ArenaBitVector blocks_;
375
376  DISALLOW_COPY_AND_ASSIGN(HLoopInformation);
377};
378
379static constexpr size_t kNoLifetime = -1;
380static constexpr uint32_t kNoDexPc = -1;
381
382// A block in a method. Contains the list of instructions represented
383// as a double linked list. Each block knows its predecessors and
384// successors.
385
386class HBasicBlock : public ArenaObject<kArenaAllocMisc> {
387 public:
388  explicit HBasicBlock(HGraph* graph, uint32_t dex_pc = kNoDexPc)
389      : graph_(graph),
390        predecessors_(graph->GetArena(), kDefaultNumberOfPredecessors),
391        successors_(graph->GetArena(), kDefaultNumberOfSuccessors),
392        loop_information_(nullptr),
393        dominator_(nullptr),
394        dominated_blocks_(graph->GetArena(), kDefaultNumberOfDominatedBlocks),
395        block_id_(-1),
396        dex_pc_(dex_pc),
397        lifetime_start_(kNoLifetime),
398        lifetime_end_(kNoLifetime),
399        is_catch_block_(false) {}
400
401  const GrowableArray<HBasicBlock*>& GetPredecessors() const {
402    return predecessors_;
403  }
404
405  const GrowableArray<HBasicBlock*>& GetSuccessors() const {
406    return successors_;
407  }
408
409  const GrowableArray<HBasicBlock*>& GetDominatedBlocks() const {
410    return dominated_blocks_;
411  }
412
413  bool IsEntryBlock() const {
414    return graph_->GetEntryBlock() == this;
415  }
416
417  bool IsExitBlock() const {
418    return graph_->GetExitBlock() == this;
419  }
420
421  bool IsSingleGoto() const;
422
423  void AddBackEdge(HBasicBlock* back_edge) {
424    if (loop_information_ == nullptr) {
425      loop_information_ = new (graph_->GetArena()) HLoopInformation(this, graph_);
426    }
427    DCHECK_EQ(loop_information_->GetHeader(), this);
428    loop_information_->AddBackEdge(back_edge);
429  }
430
431  HGraph* GetGraph() const { return graph_; }
432  void SetGraph(HGraph* graph) { graph_ = graph; }
433
434  int GetBlockId() const { return block_id_; }
435  void SetBlockId(int id) { block_id_ = id; }
436
437  HBasicBlock* GetDominator() const { return dominator_; }
438  void SetDominator(HBasicBlock* dominator) { dominator_ = dominator; }
439  void AddDominatedBlock(HBasicBlock* block) { dominated_blocks_.Add(block); }
440  void ReplaceDominatedBlock(HBasicBlock* existing, HBasicBlock* new_block) {
441    for (size_t i = 0, e = dominated_blocks_.Size(); i < e; ++i) {
442      if (dominated_blocks_.Get(i) == existing) {
443        dominated_blocks_.Put(i, new_block);
444        return;
445      }
446    }
447    LOG(FATAL) << "Unreachable";
448    UNREACHABLE();
449  }
450
451  int NumberOfBackEdges() const {
452    return loop_information_ == nullptr
453        ? 0
454        : loop_information_->NumberOfBackEdges();
455  }
456
457  HInstruction* GetFirstInstruction() const { return instructions_.first_instruction_; }
458  HInstruction* GetLastInstruction() const { return instructions_.last_instruction_; }
459  const HInstructionList& GetInstructions() const { return instructions_; }
460  const HInstructionList& GetPhis() const { return phis_; }
461  HInstruction* GetFirstPhi() const { return phis_.first_instruction_; }
462
463  void AddSuccessor(HBasicBlock* block) {
464    successors_.Add(block);
465    block->predecessors_.Add(this);
466  }
467
468  void ReplaceSuccessor(HBasicBlock* existing, HBasicBlock* new_block) {
469    size_t successor_index = GetSuccessorIndexOf(existing);
470    DCHECK_NE(successor_index, static_cast<size_t>(-1));
471    existing->RemovePredecessor(this);
472    new_block->predecessors_.Add(this);
473    successors_.Put(successor_index, new_block);
474  }
475
476  void ReplacePredecessor(HBasicBlock* existing, HBasicBlock* new_block) {
477    size_t predecessor_index = GetPredecessorIndexOf(existing);
478    DCHECK_NE(predecessor_index, static_cast<size_t>(-1));
479    existing->RemoveSuccessor(this);
480    new_block->successors_.Add(this);
481    predecessors_.Put(predecessor_index, new_block);
482  }
483
484  void RemovePredecessor(HBasicBlock* block) {
485    predecessors_.Delete(block);
486  }
487
488  void RemoveSuccessor(HBasicBlock* block) {
489    successors_.Delete(block);
490  }
491
492  void ClearAllPredecessors() {
493    predecessors_.Reset();
494  }
495
496  void AddPredecessor(HBasicBlock* block) {
497    predecessors_.Add(block);
498    block->successors_.Add(this);
499  }
500
501  void SwapPredecessors() {
502    DCHECK_EQ(predecessors_.Size(), 2u);
503    HBasicBlock* temp = predecessors_.Get(0);
504    predecessors_.Put(0, predecessors_.Get(1));
505    predecessors_.Put(1, temp);
506  }
507
508  size_t GetPredecessorIndexOf(HBasicBlock* predecessor) {
509    for (size_t i = 0, e = predecessors_.Size(); i < e; ++i) {
510      if (predecessors_.Get(i) == predecessor) {
511        return i;
512      }
513    }
514    return -1;
515  }
516
517  size_t GetSuccessorIndexOf(HBasicBlock* successor) {
518    for (size_t i = 0, e = successors_.Size(); i < e; ++i) {
519      if (successors_.Get(i) == successor) {
520        return i;
521      }
522    }
523    return -1;
524  }
525
526  // Split the block into two blocks just after `cursor`. Returns the newly
527  // created block. Note that this method just updates raw block information,
528  // like predecessors, successors, dominators, and instruction list. It does not
529  // update the graph, reverse post order, loop information, nor make sure the
530  // blocks are consistent (for example ending with a control flow instruction).
531  HBasicBlock* SplitAfter(HInstruction* cursor);
532
533  // Merge `other` at the end of `this`. Successors and dominated blocks of
534  // `other` are changed to be successors and dominated blocks of `this`. Note
535  // that this method does not update the graph, reverse post order, loop
536  // information, nor make sure the blocks are consistent (for example ending
537  // with a control flow instruction).
538  void MergeWith(HBasicBlock* other);
539
540  // Replace `this` with `other`. Predecessors, successors, and dominated blocks
541  // of `this` are moved to `other`.
542  // Note that this method does not update the graph, reverse post order, loop
543  // information, nor make sure the blocks are consistent (for example ending
544  // with a control flow instruction).
545  void ReplaceWith(HBasicBlock* other);
546
547  // Disconnects `this` from all its predecessors, successors and the dominator.
548  // It assumes that `this` does not dominate any blocks.
549  // Note that this method does not update the graph, reverse post order, loop
550  // information, nor make sure the blocks are consistent (for example ending
551  // with a control flow instruction).
552  void DisconnectFromAll();
553
554  void AddInstruction(HInstruction* instruction);
555  void InsertInstructionBefore(HInstruction* instruction, HInstruction* cursor);
556  // Replace instruction `initial` with `replacement` within this block.
557  void ReplaceAndRemoveInstructionWith(HInstruction* initial,
558                                       HInstruction* replacement);
559  void AddPhi(HPhi* phi);
560  void InsertPhiAfter(HPhi* instruction, HPhi* cursor);
561  // RemoveInstruction and RemovePhi delete a given instruction from the respective
562  // instruction list. With 'ensure_safety' set to true, it verifies that the
563  // instruction is not in use and removes it from the use lists of its inputs.
564  void RemoveInstruction(HInstruction* instruction, bool ensure_safety = true);
565  void RemovePhi(HPhi* phi, bool ensure_safety = true);
566
567  bool IsLoopHeader() const {
568    return (loop_information_ != nullptr) && (loop_information_->GetHeader() == this);
569  }
570
571  bool IsLoopPreHeaderFirstPredecessor() const {
572    DCHECK(IsLoopHeader());
573    DCHECK(!GetPredecessors().IsEmpty());
574    return GetPredecessors().Get(0) == GetLoopInformation()->GetPreHeader();
575  }
576
577  HLoopInformation* GetLoopInformation() const {
578    return loop_information_;
579  }
580
581  // Set the loop_information_ on this block. Overrides the current
582  // loop_information if it is an outer loop of the passed loop information.
583  // Note that this method is called while creating the loop information.
584  void SetInLoop(HLoopInformation* info) {
585    if (IsLoopHeader()) {
586      // Nothing to do. This just means `info` is an outer loop.
587    } else if (loop_information_ == nullptr) {
588      loop_information_ = info;
589    } else if (loop_information_->Contains(*info->GetHeader())) {
590      // Block is currently part of an outer loop. Make it part of this inner loop.
591      // Note that a non loop header having a loop information means this loop information
592      // has already been populated
593      loop_information_ = info;
594    } else {
595      // Block is part of an inner loop. Do not update the loop information.
596      // Note that we cannot do the check `info->Contains(loop_information_)->GetHeader()`
597      // at this point, because this method is being called while populating `info`.
598    }
599  }
600
601  // Raw update of the loop information.
602  void SetLoopInformation(HLoopInformation* info) {
603    loop_information_ = info;
604  }
605
606  bool IsInLoop() const { return loop_information_ != nullptr; }
607
608  // Returns wheter this block dominates the blocked passed as parameter.
609  bool Dominates(HBasicBlock* block) const;
610
611  size_t GetLifetimeStart() const { return lifetime_start_; }
612  size_t GetLifetimeEnd() const { return lifetime_end_; }
613
614  void SetLifetimeStart(size_t start) { lifetime_start_ = start; }
615  void SetLifetimeEnd(size_t end) { lifetime_end_ = end; }
616
617  uint32_t GetDexPc() const { return dex_pc_; }
618
619  bool IsCatchBlock() const { return is_catch_block_; }
620  void SetIsCatchBlock() { is_catch_block_ = true; }
621
622  bool EndsWithControlFlowInstruction() const;
623  bool EndsWithIf() const;
624  bool HasSinglePhi() const;
625
626 private:
627  HGraph* graph_;
628  GrowableArray<HBasicBlock*> predecessors_;
629  GrowableArray<HBasicBlock*> successors_;
630  HInstructionList instructions_;
631  HInstructionList phis_;
632  HLoopInformation* loop_information_;
633  HBasicBlock* dominator_;
634  GrowableArray<HBasicBlock*> dominated_blocks_;
635  int block_id_;
636  // The dex program counter of the first instruction of this block.
637  const uint32_t dex_pc_;
638  size_t lifetime_start_;
639  size_t lifetime_end_;
640  bool is_catch_block_;
641
642  friend class HGraph;
643  friend class HInstruction;
644
645  DISALLOW_COPY_AND_ASSIGN(HBasicBlock);
646};
647
648// Iterates over the LoopInformation of all loops which contain 'block'
649// from the innermost to the outermost.
650class HLoopInformationOutwardIterator : public ValueObject {
651 public:
652  explicit HLoopInformationOutwardIterator(const HBasicBlock& block)
653      : current_(block.GetLoopInformation()) {}
654
655  bool Done() const { return current_ == nullptr; }
656
657  void Advance() {
658    DCHECK(!Done());
659    current_ = current_->GetHeader()->GetDominator()->GetLoopInformation();
660  }
661
662  HLoopInformation* Current() const {
663    DCHECK(!Done());
664    return current_;
665  }
666
667 private:
668  HLoopInformation* current_;
669
670  DISALLOW_COPY_AND_ASSIGN(HLoopInformationOutwardIterator);
671};
672
673#define FOR_EACH_CONCRETE_INSTRUCTION(M)                                \
674  M(Add, BinaryOperation)                                               \
675  M(And, BinaryOperation)                                               \
676  M(ArrayGet, Instruction)                                              \
677  M(ArrayLength, Instruction)                                           \
678  M(ArraySet, Instruction)                                              \
679  M(BoundsCheck, Instruction)                                           \
680  M(BoundType, Instruction)                                             \
681  M(CheckCast, Instruction)                                             \
682  M(ClinitCheck, Instruction)                                           \
683  M(Compare, BinaryOperation)                                           \
684  M(Condition, BinaryOperation)                                         \
685  M(Div, BinaryOperation)                                               \
686  M(DivZeroCheck, Instruction)                                          \
687  M(DoubleConstant, Constant)                                           \
688  M(Equal, Condition)                                                   \
689  M(Exit, Instruction)                                                  \
690  M(FloatConstant, Constant)                                            \
691  M(Goto, Instruction)                                                  \
692  M(GreaterThan, Condition)                                             \
693  M(GreaterThanOrEqual, Condition)                                      \
694  M(If, Instruction)                                                    \
695  M(InstanceFieldGet, Instruction)                                      \
696  M(InstanceFieldSet, Instruction)                                      \
697  M(InstanceOf, Instruction)                                            \
698  M(IntConstant, Constant)                                              \
699  M(InvokeInterface, Invoke)                                            \
700  M(InvokeStaticOrDirect, Invoke)                                       \
701  M(InvokeVirtual, Invoke)                                              \
702  M(LessThan, Condition)                                                \
703  M(LessThanOrEqual, Condition)                                         \
704  M(LoadClass, Instruction)                                             \
705  M(LoadException, Instruction)                                         \
706  M(LoadLocal, Instruction)                                             \
707  M(LoadString, Instruction)                                            \
708  M(Local, Instruction)                                                 \
709  M(LongConstant, Constant)                                             \
710  M(MonitorOperation, Instruction)                                      \
711  M(Mul, BinaryOperation)                                               \
712  M(Neg, UnaryOperation)                                                \
713  M(NewArray, Instruction)                                              \
714  M(NewInstance, Instruction)                                           \
715  M(Not, UnaryOperation)                                                \
716  M(NotEqual, Condition)                                                \
717  M(NullConstant, Instruction)                                          \
718  M(NullCheck, Instruction)                                             \
719  M(Or, BinaryOperation)                                                \
720  M(ParallelMove, Instruction)                                          \
721  M(ParameterValue, Instruction)                                        \
722  M(Phi, Instruction)                                                   \
723  M(Rem, BinaryOperation)                                               \
724  M(Return, Instruction)                                                \
725  M(ReturnVoid, Instruction)                                            \
726  M(Shl, BinaryOperation)                                               \
727  M(Shr, BinaryOperation)                                               \
728  M(StaticFieldGet, Instruction)                                        \
729  M(StaticFieldSet, Instruction)                                        \
730  M(StoreLocal, Instruction)                                            \
731  M(Sub, BinaryOperation)                                               \
732  M(SuspendCheck, Instruction)                                          \
733  M(Temporary, Instruction)                                             \
734  M(Throw, Instruction)                                                 \
735  M(TypeConversion, Instruction)                                        \
736  M(UShr, BinaryOperation)                                              \
737  M(Xor, BinaryOperation)                                               \
738
739#define FOR_EACH_INSTRUCTION(M)                                         \
740  FOR_EACH_CONCRETE_INSTRUCTION(M)                                      \
741  M(Constant, Instruction)                                              \
742  M(UnaryOperation, Instruction)                                        \
743  M(BinaryOperation, Instruction)                                       \
744  M(Invoke, Instruction)
745
746#define FORWARD_DECLARATION(type, super) class H##type;
747FOR_EACH_INSTRUCTION(FORWARD_DECLARATION)
748#undef FORWARD_DECLARATION
749
750#define DECLARE_INSTRUCTION(type)                                       \
751  InstructionKind GetKind() const OVERRIDE { return k##type; }          \
752  const char* DebugName() const OVERRIDE { return #type; }              \
753  const H##type* As##type() const OVERRIDE { return this; }             \
754  H##type* As##type() OVERRIDE { return this; }                         \
755  bool InstructionTypeEquals(HInstruction* other) const OVERRIDE {      \
756    return other->Is##type();                                           \
757  }                                                                     \
758  void Accept(HGraphVisitor* visitor) OVERRIDE
759
760template <typename T> class HUseList;
761
762template <typename T>
763class HUseListNode : public ArenaObject<kArenaAllocMisc> {
764 public:
765  HUseListNode* GetPrevious() const { return prev_; }
766  HUseListNode* GetNext() const { return next_; }
767  T GetUser() const { return user_; }
768  size_t GetIndex() const { return index_; }
769
770 private:
771  HUseListNode(T user, size_t index)
772      : user_(user), index_(index), prev_(nullptr), next_(nullptr) {}
773
774  T const user_;
775  const size_t index_;
776  HUseListNode<T>* prev_;
777  HUseListNode<T>* next_;
778
779  friend class HUseList<T>;
780
781  DISALLOW_COPY_AND_ASSIGN(HUseListNode);
782};
783
784template <typename T>
785class HUseList : public ValueObject {
786 public:
787  HUseList() : first_(nullptr) {}
788
789  void Clear() {
790    first_ = nullptr;
791  }
792
793  // Adds a new entry at the beginning of the use list and returns
794  // the newly created node.
795  HUseListNode<T>* AddUse(T user, size_t index, ArenaAllocator* arena) {
796    HUseListNode<T>* new_node = new (arena) HUseListNode<T>(user, index);
797    if (IsEmpty()) {
798      first_ = new_node;
799    } else {
800      first_->prev_ = new_node;
801      new_node->next_ = first_;
802      first_ = new_node;
803    }
804    return new_node;
805  }
806
807  HUseListNode<T>* GetFirst() const {
808    return first_;
809  }
810
811  void Remove(HUseListNode<T>* node) {
812    DCHECK(node != nullptr);
813    DCHECK(Contains(node));
814
815    if (node->prev_ != nullptr) {
816      node->prev_->next_ = node->next_;
817    }
818    if (node->next_ != nullptr) {
819      node->next_->prev_ = node->prev_;
820    }
821    if (node == first_) {
822      first_ = node->next_;
823    }
824  }
825
826  bool Contains(const HUseListNode<T>* node) const {
827    if (node == nullptr) {
828      return false;
829    }
830    for (HUseListNode<T>* current = first_; current != nullptr; current = current->GetNext()) {
831      if (current == node) {
832        return true;
833      }
834    }
835    return false;
836  }
837
838  bool IsEmpty() const {
839    return first_ == nullptr;
840  }
841
842  bool HasOnlyOneUse() const {
843    return first_ != nullptr && first_->next_ == nullptr;
844  }
845
846 private:
847  HUseListNode<T>* first_;
848};
849
850template<typename T>
851class HUseIterator : public ValueObject {
852 public:
853  explicit HUseIterator(const HUseList<T>& uses) : current_(uses.GetFirst()) {}
854
855  bool Done() const { return current_ == nullptr; }
856
857  void Advance() {
858    DCHECK(!Done());
859    current_ = current_->GetNext();
860  }
861
862  HUseListNode<T>* Current() const {
863    DCHECK(!Done());
864    return current_;
865  }
866
867 private:
868  HUseListNode<T>* current_;
869
870  friend class HValue;
871};
872
873// This class is used by HEnvironment and HInstruction classes to record the
874// instructions they use and pointers to the corresponding HUseListNodes kept
875// by the used instructions.
876template <typename T>
877class HUserRecord : public ValueObject {
878 public:
879  HUserRecord() : instruction_(nullptr), use_node_(nullptr) {}
880  explicit HUserRecord(HInstruction* instruction) : instruction_(instruction), use_node_(nullptr) {}
881
882  HUserRecord(const HUserRecord<T>& old_record, HUseListNode<T>* use_node)
883    : instruction_(old_record.instruction_), use_node_(use_node) {
884    DCHECK(instruction_ != nullptr);
885    DCHECK(use_node_ != nullptr);
886    DCHECK(old_record.use_node_ == nullptr);
887  }
888
889  HInstruction* GetInstruction() const { return instruction_; }
890  HUseListNode<T>* GetUseNode() const { return use_node_; }
891
892 private:
893  // Instruction used by the user.
894  HInstruction* instruction_;
895
896  // Corresponding entry in the use list kept by 'instruction_'.
897  HUseListNode<T>* use_node_;
898};
899
900// Represents the side effects an instruction may have.
901class SideEffects : public ValueObject {
902 public:
903  SideEffects() : flags_(0) {}
904
905  static SideEffects None() {
906    return SideEffects(0);
907  }
908
909  static SideEffects All() {
910    return SideEffects(ChangesSomething().flags_ | DependsOnSomething().flags_);
911  }
912
913  static SideEffects ChangesSomething() {
914    return SideEffects((1 << kFlagChangesCount) - 1);
915  }
916
917  static SideEffects DependsOnSomething() {
918    int count = kFlagDependsOnCount - kFlagChangesCount;
919    return SideEffects(((1 << count) - 1) << kFlagChangesCount);
920  }
921
922  SideEffects Union(SideEffects other) const {
923    return SideEffects(flags_ | other.flags_);
924  }
925
926  bool HasSideEffects() const {
927    size_t all_bits_set = (1 << kFlagChangesCount) - 1;
928    return (flags_ & all_bits_set) != 0;
929  }
930
931  bool HasAllSideEffects() const {
932    size_t all_bits_set = (1 << kFlagChangesCount) - 1;
933    return all_bits_set == (flags_ & all_bits_set);
934  }
935
936  bool DependsOn(SideEffects other) const {
937    size_t depends_flags = other.ComputeDependsFlags();
938    return (flags_ & depends_flags) != 0;
939  }
940
941  bool HasDependencies() const {
942    int count = kFlagDependsOnCount - kFlagChangesCount;
943    size_t all_bits_set = (1 << count) - 1;
944    return ((flags_ >> kFlagChangesCount) & all_bits_set) != 0;
945  }
946
947 private:
948  static constexpr int kFlagChangesSomething = 0;
949  static constexpr int kFlagChangesCount = kFlagChangesSomething + 1;
950
951  static constexpr int kFlagDependsOnSomething = kFlagChangesCount;
952  static constexpr int kFlagDependsOnCount = kFlagDependsOnSomething + 1;
953
954  explicit SideEffects(size_t flags) : flags_(flags) {}
955
956  size_t ComputeDependsFlags() const {
957    return flags_ << kFlagChangesCount;
958  }
959
960  size_t flags_;
961};
962
963// A HEnvironment object contains the values of virtual registers at a given location.
964class HEnvironment : public ArenaObject<kArenaAllocMisc> {
965 public:
966  HEnvironment(ArenaAllocator* arena, size_t number_of_vregs)
967     : vregs_(arena, number_of_vregs) {
968    vregs_.SetSize(number_of_vregs);
969    for (size_t i = 0; i < number_of_vregs; i++) {
970      vregs_.Put(i, HUserRecord<HEnvironment*>());
971    }
972  }
973
974  void CopyFrom(HEnvironment* env);
975
976  void SetRawEnvAt(size_t index, HInstruction* instruction) {
977    vregs_.Put(index, HUserRecord<HEnvironment*>(instruction));
978  }
979
980  HInstruction* GetInstructionAt(size_t index) const {
981    return vregs_.Get(index).GetInstruction();
982  }
983
984  void RemoveAsUserOfInput(size_t index) const;
985
986  size_t Size() const { return vregs_.Size(); }
987
988 private:
989  // Record instructions' use entries of this environment for constant-time removal.
990  // It should only be called by HInstruction when a new environment use is added.
991  void RecordEnvUse(HUseListNode<HEnvironment*>* env_use) {
992    DCHECK(env_use->GetUser() == this);
993    size_t index = env_use->GetIndex();
994    vregs_.Put(index, HUserRecord<HEnvironment*>(vregs_.Get(index), env_use));
995  }
996
997  GrowableArray<HUserRecord<HEnvironment*> > vregs_;
998
999  friend HInstruction;
1000
1001  DISALLOW_COPY_AND_ASSIGN(HEnvironment);
1002};
1003
1004class ReferenceTypeInfo : ValueObject {
1005 public:
1006  typedef Handle<mirror::Class> TypeHandle;
1007
1008  static ReferenceTypeInfo Create(TypeHandle type_handle, bool is_exact)
1009      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
1010    if (type_handle->IsObjectClass()) {
1011      // Override the type handle to be consistent with the case when we get to
1012      // Top but don't have the Object class available. It avoids having to guess
1013      // what value the type_handle has when it's Top.
1014      return ReferenceTypeInfo(TypeHandle(), is_exact, true);
1015    } else {
1016      return ReferenceTypeInfo(type_handle, is_exact, false);
1017    }
1018  }
1019
1020  static ReferenceTypeInfo CreateTop(bool is_exact) {
1021    return ReferenceTypeInfo(TypeHandle(), is_exact, true);
1022  }
1023
1024  bool IsExact() const { return is_exact_; }
1025  bool IsTop() const { return is_top_; }
1026
1027  Handle<mirror::Class> GetTypeHandle() const { return type_handle_; }
1028
1029  bool IsSupertypeOf(ReferenceTypeInfo rti) const SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
1030    if (IsTop()) {
1031      // Top (equivalent for java.lang.Object) is supertype of anything.
1032      return true;
1033    }
1034    if (rti.IsTop()) {
1035      // If we get here `this` is not Top() so it can't be a supertype.
1036      return false;
1037    }
1038    return GetTypeHandle()->IsAssignableFrom(rti.GetTypeHandle().Get());
1039  }
1040
1041  // Returns true if the type information provide the same amount of details.
1042  // Note that it does not mean that the instructions have the same actual type
1043  // (e.g. tops are equal but they can be the result of a merge).
1044  bool IsEqual(ReferenceTypeInfo rti) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
1045    if (IsExact() != rti.IsExact()) {
1046      return false;
1047    }
1048    if (IsTop() && rti.IsTop()) {
1049      // `Top` means java.lang.Object, so the types are equivalent.
1050      return true;
1051    }
1052    if (IsTop() || rti.IsTop()) {
1053      // If only one is top or object than they are not equivalent.
1054      // NB: We need this extra check because the type_handle of `Top` is invalid
1055      // and we cannot inspect its reference.
1056      return false;
1057    }
1058
1059    // Finally check the types.
1060    return GetTypeHandle().Get() == rti.GetTypeHandle().Get();
1061  }
1062
1063 private:
1064  ReferenceTypeInfo() : ReferenceTypeInfo(TypeHandle(), false, true) {}
1065  ReferenceTypeInfo(TypeHandle type_handle, bool is_exact, bool is_top)
1066      : type_handle_(type_handle), is_exact_(is_exact), is_top_(is_top) {}
1067
1068  // The class of the object.
1069  TypeHandle type_handle_;
1070  // Whether or not the type is exact or a superclass of the actual type.
1071  // Whether or not we have any information about this type.
1072  bool is_exact_;
1073  // A true value here means that the object type should be java.lang.Object.
1074  // We don't have access to the corresponding mirror object every time so this
1075  // flag acts as a substitute. When true, the TypeHandle refers to a null
1076  // pointer and should not be used.
1077  bool is_top_;
1078};
1079
1080std::ostream& operator<<(std::ostream& os, const ReferenceTypeInfo& rhs);
1081
1082class HInstruction : public ArenaObject<kArenaAllocMisc> {
1083 public:
1084  explicit HInstruction(SideEffects side_effects)
1085      : previous_(nullptr),
1086        next_(nullptr),
1087        block_(nullptr),
1088        id_(-1),
1089        ssa_index_(-1),
1090        environment_(nullptr),
1091        locations_(nullptr),
1092        live_interval_(nullptr),
1093        lifetime_position_(kNoLifetime),
1094        side_effects_(side_effects),
1095        reference_type_info_(ReferenceTypeInfo::CreateTop(/* is_exact */ false)) {}
1096
1097  virtual ~HInstruction() {}
1098
1099#define DECLARE_KIND(type, super) k##type,
1100  enum InstructionKind {
1101    FOR_EACH_INSTRUCTION(DECLARE_KIND)
1102  };
1103#undef DECLARE_KIND
1104
1105  HInstruction* GetNext() const { return next_; }
1106  HInstruction* GetPrevious() const { return previous_; }
1107
1108  HInstruction* GetNextDisregardingMoves() const;
1109  HInstruction* GetPreviousDisregardingMoves() const;
1110
1111  HBasicBlock* GetBlock() const { return block_; }
1112  void SetBlock(HBasicBlock* block) { block_ = block; }
1113  bool IsInBlock() const { return block_ != nullptr; }
1114  bool IsInLoop() const { return block_->IsInLoop(); }
1115  bool IsLoopHeaderPhi() { return IsPhi() && block_->IsLoopHeader(); }
1116
1117  virtual size_t InputCount() const = 0;
1118  HInstruction* InputAt(size_t i) const { return InputRecordAt(i).GetInstruction(); }
1119
1120  virtual void Accept(HGraphVisitor* visitor) = 0;
1121  virtual const char* DebugName() const = 0;
1122
1123  virtual Primitive::Type GetType() const { return Primitive::kPrimVoid; }
1124  void SetRawInputAt(size_t index, HInstruction* input) {
1125    SetRawInputRecordAt(index, HUserRecord<HInstruction*>(input));
1126  }
1127
1128  virtual bool NeedsEnvironment() const { return false; }
1129  virtual bool IsControlFlow() const { return false; }
1130  virtual bool CanThrow() const { return false; }
1131  bool HasSideEffects() const { return side_effects_.HasSideEffects(); }
1132
1133  virtual bool ActAsNullConstant() const { return false; }
1134
1135  // Does not apply for all instructions, but having this at top level greatly
1136  // simplifies the null check elimination.
1137  virtual bool CanBeNull() const {
1138    DCHECK_EQ(GetType(), Primitive::kPrimNot) << "CanBeNull only applies to reference types";
1139    return true;
1140  }
1141
1142  virtual bool CanDoImplicitNullCheck() const { return false; }
1143
1144  void SetReferenceTypeInfo(ReferenceTypeInfo reference_type_info) {
1145    DCHECK_EQ(GetType(), Primitive::kPrimNot);
1146    reference_type_info_ = reference_type_info;
1147  }
1148
1149  ReferenceTypeInfo GetReferenceTypeInfo() const {
1150    DCHECK_EQ(GetType(), Primitive::kPrimNot);
1151    return reference_type_info_;
1152  }
1153
1154  void AddUseAt(HInstruction* user, size_t index) {
1155    DCHECK(user != nullptr);
1156    HUseListNode<HInstruction*>* use =
1157        uses_.AddUse(user, index, GetBlock()->GetGraph()->GetArena());
1158    user->SetRawInputRecordAt(index, HUserRecord<HInstruction*>(user->InputRecordAt(index), use));
1159  }
1160
1161  void AddEnvUseAt(HEnvironment* user, size_t index) {
1162    DCHECK(user != nullptr);
1163    HUseListNode<HEnvironment*>* env_use =
1164        env_uses_.AddUse(user, index, GetBlock()->GetGraph()->GetArena());
1165    user->RecordEnvUse(env_use);
1166  }
1167
1168  void RemoveAsUserOfInput(size_t input) {
1169    HUserRecord<HInstruction*> input_use = InputRecordAt(input);
1170    input_use.GetInstruction()->uses_.Remove(input_use.GetUseNode());
1171  }
1172
1173  const HUseList<HInstruction*>& GetUses() const { return uses_; }
1174  const HUseList<HEnvironment*>& GetEnvUses() const { return env_uses_; }
1175
1176  bool HasUses() const { return !uses_.IsEmpty() || !env_uses_.IsEmpty(); }
1177  bool HasEnvironmentUses() const { return !env_uses_.IsEmpty(); }
1178  bool HasNonEnvironmentUses() const { return !uses_.IsEmpty(); }
1179
1180  // Does this instruction strictly dominate `other_instruction`?
1181  // Returns false if this instruction and `other_instruction` are the same.
1182  // Aborts if this instruction and `other_instruction` are both phis.
1183  bool StrictlyDominates(HInstruction* other_instruction) const;
1184
1185  int GetId() const { return id_; }
1186  void SetId(int id) { id_ = id; }
1187
1188  int GetSsaIndex() const { return ssa_index_; }
1189  void SetSsaIndex(int ssa_index) { ssa_index_ = ssa_index; }
1190  bool HasSsaIndex() const { return ssa_index_ != -1; }
1191
1192  bool HasEnvironment() const { return environment_ != nullptr; }
1193  HEnvironment* GetEnvironment() const { return environment_; }
1194  void SetEnvironment(HEnvironment* environment) { environment_ = environment; }
1195
1196  // Returns the number of entries in the environment. Typically, that is the
1197  // number of dex registers in a method. It could be more in case of inlining.
1198  size_t EnvironmentSize() const;
1199
1200  LocationSummary* GetLocations() const { return locations_; }
1201  void SetLocations(LocationSummary* locations) { locations_ = locations; }
1202
1203  void ReplaceWith(HInstruction* instruction);
1204  void ReplaceInput(HInstruction* replacement, size_t index);
1205
1206  // Move `this` instruction before `cursor`.
1207  void MoveBefore(HInstruction* cursor);
1208
1209#define INSTRUCTION_TYPE_CHECK(type, super)                                    \
1210  bool Is##type() const { return (As##type() != nullptr); }                    \
1211  virtual const H##type* As##type() const { return nullptr; }                  \
1212  virtual H##type* As##type() { return nullptr; }
1213
1214  FOR_EACH_INSTRUCTION(INSTRUCTION_TYPE_CHECK)
1215#undef INSTRUCTION_TYPE_CHECK
1216
1217  // Returns whether the instruction can be moved within the graph.
1218  virtual bool CanBeMoved() const { return false; }
1219
1220  // Returns whether the two instructions are of the same kind.
1221  virtual bool InstructionTypeEquals(HInstruction* other) const {
1222    UNUSED(other);
1223    return false;
1224  }
1225
1226  // Returns whether any data encoded in the two instructions is equal.
1227  // This method does not look at the inputs. Both instructions must be
1228  // of the same type, otherwise the method has undefined behavior.
1229  virtual bool InstructionDataEquals(HInstruction* other) const {
1230    UNUSED(other);
1231    return false;
1232  }
1233
1234  // Returns whether two instructions are equal, that is:
1235  // 1) They have the same type and contain the same data (InstructionDataEquals).
1236  // 2) Their inputs are identical.
1237  bool Equals(HInstruction* other) const;
1238
1239  virtual InstructionKind GetKind() const = 0;
1240
1241  virtual size_t ComputeHashCode() const {
1242    size_t result = GetKind();
1243    for (size_t i = 0, e = InputCount(); i < e; ++i) {
1244      result = (result * 31) + InputAt(i)->GetId();
1245    }
1246    return result;
1247  }
1248
1249  SideEffects GetSideEffects() const { return side_effects_; }
1250
1251  size_t GetLifetimePosition() const { return lifetime_position_; }
1252  void SetLifetimePosition(size_t position) { lifetime_position_ = position; }
1253  LiveInterval* GetLiveInterval() const { return live_interval_; }
1254  void SetLiveInterval(LiveInterval* interval) { live_interval_ = interval; }
1255  bool HasLiveInterval() const { return live_interval_ != nullptr; }
1256
1257  bool IsSuspendCheckEntry() const { return IsSuspendCheck() && GetBlock()->IsEntryBlock(); }
1258
1259  // Returns whether the code generation of the instruction will require to have access
1260  // to the current method. Such instructions are:
1261  // (1): Instructions that require an environment, as calling the runtime requires
1262  //      to walk the stack and have the current method stored at a specific stack address.
1263  // (2): Object literals like classes and strings, that are loaded from the dex cache
1264  //      fields of the current method.
1265  bool NeedsCurrentMethod() const {
1266    return NeedsEnvironment() || IsLoadClass() || IsLoadString();
1267  }
1268
1269  virtual bool NeedsDexCache() const { return false; }
1270
1271 protected:
1272  virtual const HUserRecord<HInstruction*> InputRecordAt(size_t i) const = 0;
1273  virtual void SetRawInputRecordAt(size_t index, const HUserRecord<HInstruction*>& input) = 0;
1274
1275 private:
1276  void RemoveEnvironmentUser(HUseListNode<HEnvironment*>* use_node) { env_uses_.Remove(use_node); }
1277
1278  HInstruction* previous_;
1279  HInstruction* next_;
1280  HBasicBlock* block_;
1281
1282  // An instruction gets an id when it is added to the graph.
1283  // It reflects creation order. A negative id means the instruction
1284  // has not been added to the graph.
1285  int id_;
1286
1287  // When doing liveness analysis, instructions that have uses get an SSA index.
1288  int ssa_index_;
1289
1290  // List of instructions that have this instruction as input.
1291  HUseList<HInstruction*> uses_;
1292
1293  // List of environments that contain this instruction.
1294  HUseList<HEnvironment*> env_uses_;
1295
1296  // The environment associated with this instruction. Not null if the instruction
1297  // might jump out of the method.
1298  HEnvironment* environment_;
1299
1300  // Set by the code generator.
1301  LocationSummary* locations_;
1302
1303  // Set by the liveness analysis.
1304  LiveInterval* live_interval_;
1305
1306  // Set by the liveness analysis, this is the position in a linear
1307  // order of blocks where this instruction's live interval start.
1308  size_t lifetime_position_;
1309
1310  const SideEffects side_effects_;
1311
1312  // TODO: for primitive types this should be marked as invalid.
1313  ReferenceTypeInfo reference_type_info_;
1314
1315  friend class GraphChecker;
1316  friend class HBasicBlock;
1317  friend class HEnvironment;
1318  friend class HGraph;
1319  friend class HInstructionList;
1320
1321  DISALLOW_COPY_AND_ASSIGN(HInstruction);
1322};
1323std::ostream& operator<<(std::ostream& os, const HInstruction::InstructionKind& rhs);
1324
1325class HInputIterator : public ValueObject {
1326 public:
1327  explicit HInputIterator(HInstruction* instruction) : instruction_(instruction), index_(0) {}
1328
1329  bool Done() const { return index_ == instruction_->InputCount(); }
1330  HInstruction* Current() const { return instruction_->InputAt(index_); }
1331  void Advance() { index_++; }
1332
1333 private:
1334  HInstruction* instruction_;
1335  size_t index_;
1336
1337  DISALLOW_COPY_AND_ASSIGN(HInputIterator);
1338};
1339
1340class HInstructionIterator : public ValueObject {
1341 public:
1342  explicit HInstructionIterator(const HInstructionList& instructions)
1343      : instruction_(instructions.first_instruction_) {
1344    next_ = Done() ? nullptr : instruction_->GetNext();
1345  }
1346
1347  bool Done() const { return instruction_ == nullptr; }
1348  HInstruction* Current() const { return instruction_; }
1349  void Advance() {
1350    instruction_ = next_;
1351    next_ = Done() ? nullptr : instruction_->GetNext();
1352  }
1353
1354 private:
1355  HInstruction* instruction_;
1356  HInstruction* next_;
1357
1358  DISALLOW_COPY_AND_ASSIGN(HInstructionIterator);
1359};
1360
1361class HBackwardInstructionIterator : public ValueObject {
1362 public:
1363  explicit HBackwardInstructionIterator(const HInstructionList& instructions)
1364      : instruction_(instructions.last_instruction_) {
1365    next_ = Done() ? nullptr : instruction_->GetPrevious();
1366  }
1367
1368  bool Done() const { return instruction_ == nullptr; }
1369  HInstruction* Current() const { return instruction_; }
1370  void Advance() {
1371    instruction_ = next_;
1372    next_ = Done() ? nullptr : instruction_->GetPrevious();
1373  }
1374
1375 private:
1376  HInstruction* instruction_;
1377  HInstruction* next_;
1378
1379  DISALLOW_COPY_AND_ASSIGN(HBackwardInstructionIterator);
1380};
1381
1382// An embedded container with N elements of type T.  Used (with partial
1383// specialization for N=0) because embedded arrays cannot have size 0.
1384template<typename T, intptr_t N>
1385class EmbeddedArray {
1386 public:
1387  EmbeddedArray() : elements_() {}
1388
1389  intptr_t GetLength() const { return N; }
1390
1391  const T& operator[](intptr_t i) const {
1392    DCHECK_LT(i, GetLength());
1393    return elements_[i];
1394  }
1395
1396  T& operator[](intptr_t i) {
1397    DCHECK_LT(i, GetLength());
1398    return elements_[i];
1399  }
1400
1401  const T& At(intptr_t i) const {
1402    return (*this)[i];
1403  }
1404
1405  void SetAt(intptr_t i, const T& val) {
1406    (*this)[i] = val;
1407  }
1408
1409 private:
1410  T elements_[N];
1411};
1412
1413template<typename T>
1414class EmbeddedArray<T, 0> {
1415 public:
1416  intptr_t length() const { return 0; }
1417  const T& operator[](intptr_t i) const {
1418    UNUSED(i);
1419    LOG(FATAL) << "Unreachable";
1420    UNREACHABLE();
1421  }
1422  T& operator[](intptr_t i) {
1423    UNUSED(i);
1424    LOG(FATAL) << "Unreachable";
1425    UNREACHABLE();
1426  }
1427};
1428
1429template<intptr_t N>
1430class HTemplateInstruction: public HInstruction {
1431 public:
1432  HTemplateInstruction<N>(SideEffects side_effects)
1433      : HInstruction(side_effects), inputs_() {}
1434  virtual ~HTemplateInstruction() {}
1435
1436  size_t InputCount() const OVERRIDE { return N; }
1437
1438 protected:
1439  const HUserRecord<HInstruction*> InputRecordAt(size_t i) const OVERRIDE { return inputs_[i]; }
1440
1441  void SetRawInputRecordAt(size_t i, const HUserRecord<HInstruction*>& input) OVERRIDE {
1442    inputs_[i] = input;
1443  }
1444
1445 private:
1446  EmbeddedArray<HUserRecord<HInstruction*>, N> inputs_;
1447
1448  friend class SsaBuilder;
1449};
1450
1451template<intptr_t N>
1452class HExpression : public HTemplateInstruction<N> {
1453 public:
1454  HExpression<N>(Primitive::Type type, SideEffects side_effects)
1455      : HTemplateInstruction<N>(side_effects), type_(type) {}
1456  virtual ~HExpression() {}
1457
1458  Primitive::Type GetType() const OVERRIDE { return type_; }
1459
1460 protected:
1461  Primitive::Type type_;
1462};
1463
1464// Represents dex's RETURN_VOID opcode. A HReturnVoid is a control flow
1465// instruction that branches to the exit block.
1466class HReturnVoid : public HTemplateInstruction<0> {
1467 public:
1468  HReturnVoid() : HTemplateInstruction(SideEffects::None()) {}
1469
1470  bool IsControlFlow() const OVERRIDE { return true; }
1471
1472  DECLARE_INSTRUCTION(ReturnVoid);
1473
1474 private:
1475  DISALLOW_COPY_AND_ASSIGN(HReturnVoid);
1476};
1477
1478// Represents dex's RETURN opcodes. A HReturn is a control flow
1479// instruction that branches to the exit block.
1480class HReturn : public HTemplateInstruction<1> {
1481 public:
1482  explicit HReturn(HInstruction* value) : HTemplateInstruction(SideEffects::None()) {
1483    SetRawInputAt(0, value);
1484  }
1485
1486  bool IsControlFlow() const OVERRIDE { return true; }
1487
1488  DECLARE_INSTRUCTION(Return);
1489
1490 private:
1491  DISALLOW_COPY_AND_ASSIGN(HReturn);
1492};
1493
1494// The exit instruction is the only instruction of the exit block.
1495// Instructions aborting the method (HThrow and HReturn) must branch to the
1496// exit block.
1497class HExit : public HTemplateInstruction<0> {
1498 public:
1499  HExit() : HTemplateInstruction(SideEffects::None()) {}
1500
1501  bool IsControlFlow() const OVERRIDE { return true; }
1502
1503  DECLARE_INSTRUCTION(Exit);
1504
1505 private:
1506  DISALLOW_COPY_AND_ASSIGN(HExit);
1507};
1508
1509// Jumps from one block to another.
1510class HGoto : public HTemplateInstruction<0> {
1511 public:
1512  HGoto() : HTemplateInstruction(SideEffects::None()) {}
1513
1514  bool IsControlFlow() const OVERRIDE { return true; }
1515
1516  HBasicBlock* GetSuccessor() const {
1517    return GetBlock()->GetSuccessors().Get(0);
1518  }
1519
1520  DECLARE_INSTRUCTION(Goto);
1521
1522 private:
1523  DISALLOW_COPY_AND_ASSIGN(HGoto);
1524};
1525
1526
1527// Conditional branch. A block ending with an HIf instruction must have
1528// two successors.
1529class HIf : public HTemplateInstruction<1> {
1530 public:
1531  explicit HIf(HInstruction* input) : HTemplateInstruction(SideEffects::None()) {
1532    SetRawInputAt(0, input);
1533  }
1534
1535  bool IsControlFlow() const OVERRIDE { return true; }
1536
1537  HBasicBlock* IfTrueSuccessor() const {
1538    return GetBlock()->GetSuccessors().Get(0);
1539  }
1540
1541  HBasicBlock* IfFalseSuccessor() const {
1542    return GetBlock()->GetSuccessors().Get(1);
1543  }
1544
1545  DECLARE_INSTRUCTION(If);
1546
1547  virtual bool IsIfInstruction() const { return true; }
1548
1549 private:
1550  DISALLOW_COPY_AND_ASSIGN(HIf);
1551};
1552
1553class HUnaryOperation : public HExpression<1> {
1554 public:
1555  HUnaryOperation(Primitive::Type result_type, HInstruction* input)
1556      : HExpression(result_type, SideEffects::None()) {
1557    SetRawInputAt(0, input);
1558  }
1559
1560  HInstruction* GetInput() const { return InputAt(0); }
1561  Primitive::Type GetResultType() const { return GetType(); }
1562
1563  bool CanBeMoved() const OVERRIDE { return true; }
1564  bool InstructionDataEquals(HInstruction* other) const OVERRIDE {
1565    UNUSED(other);
1566    return true;
1567  }
1568
1569  // Try to statically evaluate `operation` and return a HConstant
1570  // containing the result of this evaluation.  If `operation` cannot
1571  // be evaluated as a constant, return nullptr.
1572  HConstant* TryStaticEvaluation() const;
1573
1574  // Apply this operation to `x`.
1575  virtual int32_t Evaluate(int32_t x) const = 0;
1576  virtual int64_t Evaluate(int64_t x) const = 0;
1577
1578  DECLARE_INSTRUCTION(UnaryOperation);
1579
1580 private:
1581  DISALLOW_COPY_AND_ASSIGN(HUnaryOperation);
1582};
1583
1584class HBinaryOperation : public HExpression<2> {
1585 public:
1586  HBinaryOperation(Primitive::Type result_type,
1587                   HInstruction* left,
1588                   HInstruction* right) : HExpression(result_type, SideEffects::None()) {
1589    SetRawInputAt(0, left);
1590    SetRawInputAt(1, right);
1591  }
1592
1593  HInstruction* GetLeft() const { return InputAt(0); }
1594  HInstruction* GetRight() const { return InputAt(1); }
1595  Primitive::Type GetResultType() const { return GetType(); }
1596
1597  virtual bool IsCommutative() const { return false; }
1598
1599  // Put constant on the right.
1600  // Returns whether order is changed.
1601  bool OrderInputsWithConstantOnTheRight() {
1602    HInstruction* left = InputAt(0);
1603    HInstruction* right = InputAt(1);
1604    if (left->IsConstant() && !right->IsConstant()) {
1605      ReplaceInput(right, 0);
1606      ReplaceInput(left, 1);
1607      return true;
1608    }
1609    return false;
1610  }
1611
1612  // Order inputs by instruction id, but favor constant on the right side.
1613  // This helps GVN for commutative ops.
1614  void OrderInputs() {
1615    DCHECK(IsCommutative());
1616    HInstruction* left = InputAt(0);
1617    HInstruction* right = InputAt(1);
1618    if (left == right || (!left->IsConstant() && right->IsConstant())) {
1619      return;
1620    }
1621    if (OrderInputsWithConstantOnTheRight()) {
1622      return;
1623    }
1624    // Order according to instruction id.
1625    if (left->GetId() > right->GetId()) {
1626      ReplaceInput(right, 0);
1627      ReplaceInput(left, 1);
1628    }
1629  }
1630
1631  bool CanBeMoved() const OVERRIDE { return true; }
1632  bool InstructionDataEquals(HInstruction* other) const OVERRIDE {
1633    UNUSED(other);
1634    return true;
1635  }
1636
1637  // Try to statically evaluate `operation` and return a HConstant
1638  // containing the result of this evaluation.  If `operation` cannot
1639  // be evaluated as a constant, return nullptr.
1640  HConstant* TryStaticEvaluation() const;
1641
1642  // Apply this operation to `x` and `y`.
1643  virtual int32_t Evaluate(int32_t x, int32_t y) const = 0;
1644  virtual int64_t Evaluate(int64_t x, int64_t y) const = 0;
1645
1646  // Returns an input that can legally be used as the right input and is
1647  // constant, or nullptr.
1648  HConstant* GetConstantRight() const;
1649
1650  // If `GetConstantRight()` returns one of the input, this returns the other
1651  // one. Otherwise it returns nullptr.
1652  HInstruction* GetLeastConstantLeft() const;
1653
1654  DECLARE_INSTRUCTION(BinaryOperation);
1655
1656 private:
1657  DISALLOW_COPY_AND_ASSIGN(HBinaryOperation);
1658};
1659
1660class HCondition : public HBinaryOperation {
1661 public:
1662  HCondition(HInstruction* first, HInstruction* second)
1663      : HBinaryOperation(Primitive::kPrimBoolean, first, second),
1664        needs_materialization_(true) {}
1665
1666  bool NeedsMaterialization() const { return needs_materialization_; }
1667  void ClearNeedsMaterialization() { needs_materialization_ = false; }
1668
1669  // For code generation purposes, returns whether this instruction is just before
1670  // `if_`, and disregard moves in between.
1671  bool IsBeforeWhenDisregardMoves(HIf* if_) const;
1672
1673  DECLARE_INSTRUCTION(Condition);
1674
1675  virtual IfCondition GetCondition() const = 0;
1676
1677 private:
1678  // For register allocation purposes, returns whether this instruction needs to be
1679  // materialized (that is, not just be in the processor flags).
1680  bool needs_materialization_;
1681
1682  DISALLOW_COPY_AND_ASSIGN(HCondition);
1683};
1684
1685// Instruction to check if two inputs are equal to each other.
1686class HEqual : public HCondition {
1687 public:
1688  HEqual(HInstruction* first, HInstruction* second)
1689      : HCondition(first, second) {}
1690
1691  bool IsCommutative() const OVERRIDE { return true; }
1692
1693  int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE {
1694    return x == y ? 1 : 0;
1695  }
1696  int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE {
1697    return x == y ? 1 : 0;
1698  }
1699
1700  DECLARE_INSTRUCTION(Equal);
1701
1702  IfCondition GetCondition() const OVERRIDE {
1703    return kCondEQ;
1704  }
1705
1706 private:
1707  DISALLOW_COPY_AND_ASSIGN(HEqual);
1708};
1709
1710class HNotEqual : public HCondition {
1711 public:
1712  HNotEqual(HInstruction* first, HInstruction* second)
1713      : HCondition(first, second) {}
1714
1715  bool IsCommutative() const OVERRIDE { return true; }
1716
1717  int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE {
1718    return x != y ? 1 : 0;
1719  }
1720  int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE {
1721    return x != y ? 1 : 0;
1722  }
1723
1724  DECLARE_INSTRUCTION(NotEqual);
1725
1726  IfCondition GetCondition() const OVERRIDE {
1727    return kCondNE;
1728  }
1729
1730 private:
1731  DISALLOW_COPY_AND_ASSIGN(HNotEqual);
1732};
1733
1734class HLessThan : public HCondition {
1735 public:
1736  HLessThan(HInstruction* first, HInstruction* second)
1737      : HCondition(first, second) {}
1738
1739  int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE {
1740    return x < y ? 1 : 0;
1741  }
1742  int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE {
1743    return x < y ? 1 : 0;
1744  }
1745
1746  DECLARE_INSTRUCTION(LessThan);
1747
1748  IfCondition GetCondition() const OVERRIDE {
1749    return kCondLT;
1750  }
1751
1752 private:
1753  DISALLOW_COPY_AND_ASSIGN(HLessThan);
1754};
1755
1756class HLessThanOrEqual : public HCondition {
1757 public:
1758  HLessThanOrEqual(HInstruction* first, HInstruction* second)
1759      : HCondition(first, second) {}
1760
1761  int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE {
1762    return x <= y ? 1 : 0;
1763  }
1764  int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE {
1765    return x <= y ? 1 : 0;
1766  }
1767
1768  DECLARE_INSTRUCTION(LessThanOrEqual);
1769
1770  IfCondition GetCondition() const OVERRIDE {
1771    return kCondLE;
1772  }
1773
1774 private:
1775  DISALLOW_COPY_AND_ASSIGN(HLessThanOrEqual);
1776};
1777
1778class HGreaterThan : public HCondition {
1779 public:
1780  HGreaterThan(HInstruction* first, HInstruction* second)
1781      : HCondition(first, second) {}
1782
1783  int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE {
1784    return x > y ? 1 : 0;
1785  }
1786  int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE {
1787    return x > y ? 1 : 0;
1788  }
1789
1790  DECLARE_INSTRUCTION(GreaterThan);
1791
1792  IfCondition GetCondition() const OVERRIDE {
1793    return kCondGT;
1794  }
1795
1796 private:
1797  DISALLOW_COPY_AND_ASSIGN(HGreaterThan);
1798};
1799
1800class HGreaterThanOrEqual : public HCondition {
1801 public:
1802  HGreaterThanOrEqual(HInstruction* first, HInstruction* second)
1803      : HCondition(first, second) {}
1804
1805  int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE {
1806    return x >= y ? 1 : 0;
1807  }
1808  int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE {
1809    return x >= y ? 1 : 0;
1810  }
1811
1812  DECLARE_INSTRUCTION(GreaterThanOrEqual);
1813
1814  IfCondition GetCondition() const OVERRIDE {
1815    return kCondGE;
1816  }
1817
1818 private:
1819  DISALLOW_COPY_AND_ASSIGN(HGreaterThanOrEqual);
1820};
1821
1822
1823// Instruction to check how two inputs compare to each other.
1824// Result is 0 if input0 == input1, 1 if input0 > input1, or -1 if input0 < input1.
1825class HCompare : public HBinaryOperation {
1826 public:
1827  // The bias applies for floating point operations and indicates how NaN
1828  // comparisons are treated:
1829  enum Bias {
1830    kNoBias,  // bias is not applicable (i.e. for long operation)
1831    kGtBias,  // return 1 for NaN comparisons
1832    kLtBias,  // return -1 for NaN comparisons
1833  };
1834
1835  HCompare(Primitive::Type type, HInstruction* first, HInstruction* second, Bias bias)
1836      : HBinaryOperation(Primitive::kPrimInt, first, second), bias_(bias) {
1837    DCHECK_EQ(type, first->GetType());
1838    DCHECK_EQ(type, second->GetType());
1839  }
1840
1841  int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE {
1842    return
1843      x == y ? 0 :
1844      x > y ? 1 :
1845      -1;
1846  }
1847
1848  int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE {
1849    return
1850      x == y ? 0 :
1851      x > y ? 1 :
1852      -1;
1853  }
1854
1855  bool InstructionDataEquals(HInstruction* other) const OVERRIDE {
1856    return bias_ == other->AsCompare()->bias_;
1857  }
1858
1859  bool IsGtBias() { return bias_ == kGtBias; }
1860
1861  DECLARE_INSTRUCTION(Compare);
1862
1863 private:
1864  const Bias bias_;
1865
1866  DISALLOW_COPY_AND_ASSIGN(HCompare);
1867};
1868
1869// A local in the graph. Corresponds to a Dex register.
1870class HLocal : public HTemplateInstruction<0> {
1871 public:
1872  explicit HLocal(uint16_t reg_number)
1873      : HTemplateInstruction(SideEffects::None()), reg_number_(reg_number) {}
1874
1875  DECLARE_INSTRUCTION(Local);
1876
1877  uint16_t GetRegNumber() const { return reg_number_; }
1878
1879 private:
1880  // The Dex register number.
1881  const uint16_t reg_number_;
1882
1883  DISALLOW_COPY_AND_ASSIGN(HLocal);
1884};
1885
1886// Load a given local. The local is an input of this instruction.
1887class HLoadLocal : public HExpression<1> {
1888 public:
1889  HLoadLocal(HLocal* local, Primitive::Type type)
1890      : HExpression(type, SideEffects::None()) {
1891    SetRawInputAt(0, local);
1892  }
1893
1894  HLocal* GetLocal() const { return reinterpret_cast<HLocal*>(InputAt(0)); }
1895
1896  DECLARE_INSTRUCTION(LoadLocal);
1897
1898 private:
1899  DISALLOW_COPY_AND_ASSIGN(HLoadLocal);
1900};
1901
1902// Store a value in a given local. This instruction has two inputs: the value
1903// and the local.
1904class HStoreLocal : public HTemplateInstruction<2> {
1905 public:
1906  HStoreLocal(HLocal* local, HInstruction* value) : HTemplateInstruction(SideEffects::None()) {
1907    SetRawInputAt(0, local);
1908    SetRawInputAt(1, value);
1909  }
1910
1911  HLocal* GetLocal() const { return reinterpret_cast<HLocal*>(InputAt(0)); }
1912
1913  DECLARE_INSTRUCTION(StoreLocal);
1914
1915 private:
1916  DISALLOW_COPY_AND_ASSIGN(HStoreLocal);
1917};
1918
1919class HConstant : public HExpression<0> {
1920 public:
1921  explicit HConstant(Primitive::Type type) : HExpression(type, SideEffects::None()) {}
1922
1923  bool CanBeMoved() const OVERRIDE { return true; }
1924
1925  virtual bool IsMinusOne() const { return false; }
1926  virtual bool IsZero() const { return false; }
1927  virtual bool IsOne() const { return false; }
1928
1929  DECLARE_INSTRUCTION(Constant);
1930
1931 private:
1932  DISALLOW_COPY_AND_ASSIGN(HConstant);
1933};
1934
1935class HFloatConstant : public HConstant {
1936 public:
1937  float GetValue() const { return value_; }
1938
1939  bool InstructionDataEquals(HInstruction* other) const OVERRIDE {
1940    return bit_cast<uint32_t, float>(other->AsFloatConstant()->value_) ==
1941        bit_cast<uint32_t, float>(value_);
1942  }
1943
1944  size_t ComputeHashCode() const OVERRIDE { return static_cast<size_t>(GetValue()); }
1945
1946  bool IsMinusOne() const OVERRIDE {
1947    return bit_cast<uint32_t, float>(AsFloatConstant()->GetValue()) ==
1948        bit_cast<uint32_t, float>((-1.0f));
1949  }
1950  bool IsZero() const OVERRIDE {
1951    return AsFloatConstant()->GetValue() == 0.0f;
1952  }
1953  bool IsOne() const OVERRIDE {
1954    return bit_cast<uint32_t, float>(AsFloatConstant()->GetValue()) ==
1955        bit_cast<uint32_t, float>(1.0f);
1956  }
1957
1958  DECLARE_INSTRUCTION(FloatConstant);
1959
1960 private:
1961  explicit HFloatConstant(float value) : HConstant(Primitive::kPrimFloat), value_(value) {}
1962
1963  const float value_;
1964
1965  // Only the SsaBuilder can currently create floating-point constants. If we
1966  // ever need to create them later in the pipeline, we will have to handle them
1967  // the same way as integral constants.
1968  friend class SsaBuilder;
1969  DISALLOW_COPY_AND_ASSIGN(HFloatConstant);
1970};
1971
1972class HDoubleConstant : public HConstant {
1973 public:
1974  double GetValue() const { return value_; }
1975
1976  bool InstructionDataEquals(HInstruction* other) const OVERRIDE {
1977    return bit_cast<uint64_t, double>(other->AsDoubleConstant()->value_) ==
1978        bit_cast<uint64_t, double>(value_);
1979  }
1980
1981  size_t ComputeHashCode() const OVERRIDE { return static_cast<size_t>(GetValue()); }
1982
1983  bool IsMinusOne() const OVERRIDE {
1984    return bit_cast<uint64_t, double>(AsDoubleConstant()->GetValue()) ==
1985        bit_cast<uint64_t, double>((-1.0));
1986  }
1987  bool IsZero() const OVERRIDE {
1988    return AsDoubleConstant()->GetValue() == 0.0;
1989  }
1990  bool IsOne() const OVERRIDE {
1991    return bit_cast<uint64_t, double>(AsDoubleConstant()->GetValue()) ==
1992        bit_cast<uint64_t, double>(1.0);
1993  }
1994
1995  DECLARE_INSTRUCTION(DoubleConstant);
1996
1997 private:
1998  explicit HDoubleConstant(double value) : HConstant(Primitive::kPrimDouble), value_(value) {}
1999
2000  const double value_;
2001
2002  // Only the SsaBuilder can currently create floating-point constants. If we
2003  // ever need to create them later in the pipeline, we will have to handle them
2004  // the same way as integral constants.
2005  friend class SsaBuilder;
2006  DISALLOW_COPY_AND_ASSIGN(HDoubleConstant);
2007};
2008
2009class HNullConstant : public HConstant {
2010 public:
2011  bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE {
2012    return true;
2013  }
2014
2015  size_t ComputeHashCode() const OVERRIDE { return 0; }
2016
2017  bool ActAsNullConstant() const OVERRIDE { return true; }
2018
2019  DECLARE_INSTRUCTION(NullConstant);
2020
2021 private:
2022  HNullConstant() : HConstant(Primitive::kPrimNot) {}
2023
2024  friend class HGraph;
2025  DISALLOW_COPY_AND_ASSIGN(HNullConstant);
2026};
2027
2028// Constants of the type int. Those can be from Dex instructions, or
2029// synthesized (for example with the if-eqz instruction).
2030class HIntConstant : public HConstant {
2031 public:
2032  int32_t GetValue() const { return value_; }
2033
2034  bool InstructionDataEquals(HInstruction* other) const OVERRIDE {
2035    return other->AsIntConstant()->value_ == value_;
2036  }
2037
2038  size_t ComputeHashCode() const OVERRIDE { return GetValue(); }
2039
2040  // TODO: Null is represented by the `0` constant. In most cases we replace it
2041  // with a HNullConstant but we don't do it when comparing (a != null). This
2042  // method is an workaround until we fix the above.
2043  bool ActAsNullConstant() const OVERRIDE { return value_ == 0; }
2044
2045  bool IsMinusOne() const OVERRIDE { return GetValue() == -1; }
2046  bool IsZero() const OVERRIDE { return GetValue() == 0; }
2047  bool IsOne() const OVERRIDE { return GetValue() == 1; }
2048
2049  DECLARE_INSTRUCTION(IntConstant);
2050
2051 private:
2052  explicit HIntConstant(int32_t value) : HConstant(Primitive::kPrimInt), value_(value) {}
2053
2054  const int32_t value_;
2055
2056  friend class HGraph;
2057  ART_FRIEND_TEST(GraphTest, InsertInstructionBefore);
2058  ART_FRIEND_TEST(ParallelMoveTest, ConstantLast);
2059  DISALLOW_COPY_AND_ASSIGN(HIntConstant);
2060};
2061
2062class HLongConstant : public HConstant {
2063 public:
2064  int64_t GetValue() const { return value_; }
2065
2066  bool InstructionDataEquals(HInstruction* other) const OVERRIDE {
2067    return other->AsLongConstant()->value_ == value_;
2068  }
2069
2070  size_t ComputeHashCode() const OVERRIDE { return static_cast<size_t>(GetValue()); }
2071
2072  bool IsMinusOne() const OVERRIDE { return GetValue() == -1; }
2073  bool IsZero() const OVERRIDE { return GetValue() == 0; }
2074  bool IsOne() const OVERRIDE { return GetValue() == 1; }
2075
2076  DECLARE_INSTRUCTION(LongConstant);
2077
2078 private:
2079  explicit HLongConstant(int64_t value) : HConstant(Primitive::kPrimLong), value_(value) {}
2080
2081  const int64_t value_;
2082
2083  friend class HGraph;
2084  DISALLOW_COPY_AND_ASSIGN(HLongConstant);
2085};
2086
2087enum class Intrinsics {
2088#define OPTIMIZING_INTRINSICS(Name, IsStatic) k ## Name,
2089#include "intrinsics_list.h"
2090  kNone,
2091  INTRINSICS_LIST(OPTIMIZING_INTRINSICS)
2092#undef INTRINSICS_LIST
2093#undef OPTIMIZING_INTRINSICS
2094};
2095std::ostream& operator<<(std::ostream& os, const Intrinsics& intrinsic);
2096
2097class HInvoke : public HInstruction {
2098 public:
2099  size_t InputCount() const OVERRIDE { return inputs_.Size(); }
2100
2101  // Runtime needs to walk the stack, so Dex -> Dex calls need to
2102  // know their environment.
2103  bool NeedsEnvironment() const OVERRIDE { return true; }
2104
2105  void SetArgumentAt(size_t index, HInstruction* argument) {
2106    SetRawInputAt(index, argument);
2107  }
2108
2109  Primitive::Type GetType() const OVERRIDE { return return_type_; }
2110
2111  uint32_t GetDexPc() const { return dex_pc_; }
2112
2113  uint32_t GetDexMethodIndex() const { return dex_method_index_; }
2114
2115  Intrinsics GetIntrinsic() {
2116    return intrinsic_;
2117  }
2118
2119  void SetIntrinsic(Intrinsics intrinsic) {
2120    intrinsic_ = intrinsic;
2121  }
2122
2123  DECLARE_INSTRUCTION(Invoke);
2124
2125 protected:
2126  HInvoke(ArenaAllocator* arena,
2127          uint32_t number_of_arguments,
2128          Primitive::Type return_type,
2129          uint32_t dex_pc,
2130          uint32_t dex_method_index)
2131    : HInstruction(SideEffects::All()),
2132      inputs_(arena, number_of_arguments),
2133      return_type_(return_type),
2134      dex_pc_(dex_pc),
2135      dex_method_index_(dex_method_index),
2136      intrinsic_(Intrinsics::kNone) {
2137    inputs_.SetSize(number_of_arguments);
2138  }
2139
2140  const HUserRecord<HInstruction*> InputRecordAt(size_t i) const OVERRIDE { return inputs_.Get(i); }
2141  void SetRawInputRecordAt(size_t index, const HUserRecord<HInstruction*>& input) OVERRIDE {
2142    inputs_.Put(index, input);
2143  }
2144
2145  GrowableArray<HUserRecord<HInstruction*> > inputs_;
2146  const Primitive::Type return_type_;
2147  const uint32_t dex_pc_;
2148  const uint32_t dex_method_index_;
2149  Intrinsics intrinsic_;
2150
2151 private:
2152  DISALLOW_COPY_AND_ASSIGN(HInvoke);
2153};
2154
2155class HInvokeStaticOrDirect : public HInvoke {
2156 public:
2157  HInvokeStaticOrDirect(ArenaAllocator* arena,
2158                        uint32_t number_of_arguments,
2159                        Primitive::Type return_type,
2160                        uint32_t dex_pc,
2161                        uint32_t dex_method_index,
2162                        bool is_recursive,
2163                        InvokeType original_invoke_type,
2164                        InvokeType invoke_type)
2165      : HInvoke(arena, number_of_arguments, return_type, dex_pc, dex_method_index),
2166        original_invoke_type_(original_invoke_type),
2167        invoke_type_(invoke_type),
2168        is_recursive_(is_recursive) {}
2169
2170  bool CanDoImplicitNullCheck() const OVERRIDE {
2171    // We access the method via the dex cache so we can't do an implicit null check.
2172    // TODO: for intrinsics we can generate implicit null checks.
2173    return false;
2174  }
2175
2176  InvokeType GetOriginalInvokeType() const { return original_invoke_type_; }
2177  InvokeType GetInvokeType() const { return invoke_type_; }
2178  bool IsRecursive() const { return is_recursive_; }
2179  bool NeedsDexCache() const OVERRIDE { return !IsRecursive(); }
2180
2181  DECLARE_INSTRUCTION(InvokeStaticOrDirect);
2182
2183 private:
2184  const InvokeType original_invoke_type_;
2185  const InvokeType invoke_type_;
2186  const bool is_recursive_;
2187
2188  DISALLOW_COPY_AND_ASSIGN(HInvokeStaticOrDirect);
2189};
2190
2191class HInvokeVirtual : public HInvoke {
2192 public:
2193  HInvokeVirtual(ArenaAllocator* arena,
2194                 uint32_t number_of_arguments,
2195                 Primitive::Type return_type,
2196                 uint32_t dex_pc,
2197                 uint32_t dex_method_index,
2198                 uint32_t vtable_index)
2199      : HInvoke(arena, number_of_arguments, return_type, dex_pc, dex_method_index),
2200        vtable_index_(vtable_index) {}
2201
2202  bool CanDoImplicitNullCheck() const OVERRIDE {
2203    // TODO: Add implicit null checks in intrinsics.
2204    return !GetLocations()->Intrinsified();
2205  }
2206
2207  uint32_t GetVTableIndex() const { return vtable_index_; }
2208
2209  DECLARE_INSTRUCTION(InvokeVirtual);
2210
2211 private:
2212  const uint32_t vtable_index_;
2213
2214  DISALLOW_COPY_AND_ASSIGN(HInvokeVirtual);
2215};
2216
2217class HInvokeInterface : public HInvoke {
2218 public:
2219  HInvokeInterface(ArenaAllocator* arena,
2220                   uint32_t number_of_arguments,
2221                   Primitive::Type return_type,
2222                   uint32_t dex_pc,
2223                   uint32_t dex_method_index,
2224                   uint32_t imt_index)
2225      : HInvoke(arena, number_of_arguments, return_type, dex_pc, dex_method_index),
2226        imt_index_(imt_index) {}
2227
2228  bool CanDoImplicitNullCheck() const OVERRIDE {
2229    // TODO: Add implicit null checks in intrinsics.
2230    return !GetLocations()->Intrinsified();
2231  }
2232
2233  uint32_t GetImtIndex() const { return imt_index_; }
2234  uint32_t GetDexMethodIndex() const { return dex_method_index_; }
2235
2236  DECLARE_INSTRUCTION(InvokeInterface);
2237
2238 private:
2239  const uint32_t imt_index_;
2240
2241  DISALLOW_COPY_AND_ASSIGN(HInvokeInterface);
2242};
2243
2244class HNewInstance : public HExpression<0> {
2245 public:
2246  HNewInstance(uint32_t dex_pc, uint16_t type_index, QuickEntrypointEnum entrypoint)
2247      : HExpression(Primitive::kPrimNot, SideEffects::None()),
2248        dex_pc_(dex_pc),
2249        type_index_(type_index),
2250        entrypoint_(entrypoint) {}
2251
2252  uint32_t GetDexPc() const { return dex_pc_; }
2253  uint16_t GetTypeIndex() const { return type_index_; }
2254
2255  // Calls runtime so needs an environment.
2256  bool NeedsEnvironment() const OVERRIDE { return true; }
2257  // It may throw when called on:
2258  //   - interfaces
2259  //   - abstract/innaccessible/unknown classes
2260  // TODO: optimize when possible.
2261  bool CanThrow() const OVERRIDE { return true; }
2262
2263  bool CanBeNull() const OVERRIDE { return false; }
2264
2265  QuickEntrypointEnum GetEntrypoint() const { return entrypoint_; }
2266
2267  DECLARE_INSTRUCTION(NewInstance);
2268
2269 private:
2270  const uint32_t dex_pc_;
2271  const uint16_t type_index_;
2272  const QuickEntrypointEnum entrypoint_;
2273
2274  DISALLOW_COPY_AND_ASSIGN(HNewInstance);
2275};
2276
2277class HNeg : public HUnaryOperation {
2278 public:
2279  explicit HNeg(Primitive::Type result_type, HInstruction* input)
2280      : HUnaryOperation(result_type, input) {}
2281
2282  int32_t Evaluate(int32_t x) const OVERRIDE { return -x; }
2283  int64_t Evaluate(int64_t x) const OVERRIDE { return -x; }
2284
2285  DECLARE_INSTRUCTION(Neg);
2286
2287 private:
2288  DISALLOW_COPY_AND_ASSIGN(HNeg);
2289};
2290
2291class HNewArray : public HExpression<1> {
2292 public:
2293  HNewArray(HInstruction* length,
2294            uint32_t dex_pc,
2295            uint16_t type_index,
2296            QuickEntrypointEnum entrypoint)
2297      : HExpression(Primitive::kPrimNot, SideEffects::None()),
2298        dex_pc_(dex_pc),
2299        type_index_(type_index),
2300        entrypoint_(entrypoint) {
2301    SetRawInputAt(0, length);
2302  }
2303
2304  uint32_t GetDexPc() const { return dex_pc_; }
2305  uint16_t GetTypeIndex() const { return type_index_; }
2306
2307  // Calls runtime so needs an environment.
2308  bool NeedsEnvironment() const OVERRIDE { return true; }
2309
2310  // May throw NegativeArraySizeException, OutOfMemoryError, etc.
2311  bool CanThrow() const OVERRIDE { return true; }
2312
2313  bool CanBeNull() const OVERRIDE { return false; }
2314
2315  QuickEntrypointEnum GetEntrypoint() const { return entrypoint_; }
2316
2317  DECLARE_INSTRUCTION(NewArray);
2318
2319 private:
2320  const uint32_t dex_pc_;
2321  const uint16_t type_index_;
2322  const QuickEntrypointEnum entrypoint_;
2323
2324  DISALLOW_COPY_AND_ASSIGN(HNewArray);
2325};
2326
2327class HAdd : public HBinaryOperation {
2328 public:
2329  HAdd(Primitive::Type result_type, HInstruction* left, HInstruction* right)
2330      : HBinaryOperation(result_type, left, right) {}
2331
2332  bool IsCommutative() const OVERRIDE { return true; }
2333
2334  int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE {
2335    return x + y;
2336  }
2337  int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE {
2338    return x + y;
2339  }
2340
2341  DECLARE_INSTRUCTION(Add);
2342
2343 private:
2344  DISALLOW_COPY_AND_ASSIGN(HAdd);
2345};
2346
2347class HSub : public HBinaryOperation {
2348 public:
2349  HSub(Primitive::Type result_type, HInstruction* left, HInstruction* right)
2350      : HBinaryOperation(result_type, left, right) {}
2351
2352  int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE {
2353    return x - y;
2354  }
2355  int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE {
2356    return x - y;
2357  }
2358
2359  DECLARE_INSTRUCTION(Sub);
2360
2361 private:
2362  DISALLOW_COPY_AND_ASSIGN(HSub);
2363};
2364
2365class HMul : public HBinaryOperation {
2366 public:
2367  HMul(Primitive::Type result_type, HInstruction* left, HInstruction* right)
2368      : HBinaryOperation(result_type, left, right) {}
2369
2370  bool IsCommutative() const OVERRIDE { return true; }
2371
2372  int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { return x * y; }
2373  int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { return x * y; }
2374
2375  DECLARE_INSTRUCTION(Mul);
2376
2377 private:
2378  DISALLOW_COPY_AND_ASSIGN(HMul);
2379};
2380
2381class HDiv : public HBinaryOperation {
2382 public:
2383  HDiv(Primitive::Type result_type, HInstruction* left, HInstruction* right, uint32_t dex_pc)
2384      : HBinaryOperation(result_type, left, right), dex_pc_(dex_pc) {}
2385
2386  int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE {
2387    // Our graph structure ensures we never have 0 for `y` during constant folding.
2388    DCHECK_NE(y, 0);
2389    // Special case -1 to avoid getting a SIGFPE on x86(_64).
2390    return (y == -1) ? -x : x / y;
2391  }
2392
2393  int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE {
2394    DCHECK_NE(y, 0);
2395    // Special case -1 to avoid getting a SIGFPE on x86(_64).
2396    return (y == -1) ? -x : x / y;
2397  }
2398
2399  uint32_t GetDexPc() const { return dex_pc_; }
2400
2401  DECLARE_INSTRUCTION(Div);
2402
2403 private:
2404  const uint32_t dex_pc_;
2405
2406  DISALLOW_COPY_AND_ASSIGN(HDiv);
2407};
2408
2409class HRem : public HBinaryOperation {
2410 public:
2411  HRem(Primitive::Type result_type, HInstruction* left, HInstruction* right, uint32_t dex_pc)
2412      : HBinaryOperation(result_type, left, right), dex_pc_(dex_pc) {}
2413
2414  int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE {
2415    DCHECK_NE(y, 0);
2416    // Special case -1 to avoid getting a SIGFPE on x86(_64).
2417    return (y == -1) ? 0 : x % y;
2418  }
2419
2420  int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE {
2421    DCHECK_NE(y, 0);
2422    // Special case -1 to avoid getting a SIGFPE on x86(_64).
2423    return (y == -1) ? 0 : x % y;
2424  }
2425
2426  uint32_t GetDexPc() const { return dex_pc_; }
2427
2428  DECLARE_INSTRUCTION(Rem);
2429
2430 private:
2431  const uint32_t dex_pc_;
2432
2433  DISALLOW_COPY_AND_ASSIGN(HRem);
2434};
2435
2436class HDivZeroCheck : public HExpression<1> {
2437 public:
2438  HDivZeroCheck(HInstruction* value, uint32_t dex_pc)
2439      : HExpression(value->GetType(), SideEffects::None()), dex_pc_(dex_pc) {
2440    SetRawInputAt(0, value);
2441  }
2442
2443  bool CanBeMoved() const OVERRIDE { return true; }
2444
2445  bool InstructionDataEquals(HInstruction* other) const OVERRIDE {
2446    UNUSED(other);
2447    return true;
2448  }
2449
2450  bool NeedsEnvironment() const OVERRIDE { return true; }
2451  bool CanThrow() const OVERRIDE { return true; }
2452
2453  uint32_t GetDexPc() const { return dex_pc_; }
2454
2455  DECLARE_INSTRUCTION(DivZeroCheck);
2456
2457 private:
2458  const uint32_t dex_pc_;
2459
2460  DISALLOW_COPY_AND_ASSIGN(HDivZeroCheck);
2461};
2462
2463class HShl : public HBinaryOperation {
2464 public:
2465  HShl(Primitive::Type result_type, HInstruction* left, HInstruction* right)
2466      : HBinaryOperation(result_type, left, right) {}
2467
2468  int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { return x << (y & kMaxIntShiftValue); }
2469  int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { return x << (y & kMaxLongShiftValue); }
2470
2471  DECLARE_INSTRUCTION(Shl);
2472
2473 private:
2474  DISALLOW_COPY_AND_ASSIGN(HShl);
2475};
2476
2477class HShr : public HBinaryOperation {
2478 public:
2479  HShr(Primitive::Type result_type, HInstruction* left, HInstruction* right)
2480      : HBinaryOperation(result_type, left, right) {}
2481
2482  int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { return x >> (y & kMaxIntShiftValue); }
2483  int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { return x >> (y & kMaxLongShiftValue); }
2484
2485  DECLARE_INSTRUCTION(Shr);
2486
2487 private:
2488  DISALLOW_COPY_AND_ASSIGN(HShr);
2489};
2490
2491class HUShr : public HBinaryOperation {
2492 public:
2493  HUShr(Primitive::Type result_type, HInstruction* left, HInstruction* right)
2494      : HBinaryOperation(result_type, left, right) {}
2495
2496  int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE {
2497    uint32_t ux = static_cast<uint32_t>(x);
2498    uint32_t uy = static_cast<uint32_t>(y) & kMaxIntShiftValue;
2499    return static_cast<int32_t>(ux >> uy);
2500  }
2501
2502  int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE {
2503    uint64_t ux = static_cast<uint64_t>(x);
2504    uint64_t uy = static_cast<uint64_t>(y) & kMaxLongShiftValue;
2505    return static_cast<int64_t>(ux >> uy);
2506  }
2507
2508  DECLARE_INSTRUCTION(UShr);
2509
2510 private:
2511  DISALLOW_COPY_AND_ASSIGN(HUShr);
2512};
2513
2514class HAnd : public HBinaryOperation {
2515 public:
2516  HAnd(Primitive::Type result_type, HInstruction* left, HInstruction* right)
2517      : HBinaryOperation(result_type, left, right) {}
2518
2519  bool IsCommutative() const OVERRIDE { return true; }
2520
2521  int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { return x & y; }
2522  int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { return x & y; }
2523
2524  DECLARE_INSTRUCTION(And);
2525
2526 private:
2527  DISALLOW_COPY_AND_ASSIGN(HAnd);
2528};
2529
2530class HOr : public HBinaryOperation {
2531 public:
2532  HOr(Primitive::Type result_type, HInstruction* left, HInstruction* right)
2533      : HBinaryOperation(result_type, left, right) {}
2534
2535  bool IsCommutative() const OVERRIDE { return true; }
2536
2537  int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { return x | y; }
2538  int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { return x | y; }
2539
2540  DECLARE_INSTRUCTION(Or);
2541
2542 private:
2543  DISALLOW_COPY_AND_ASSIGN(HOr);
2544};
2545
2546class HXor : public HBinaryOperation {
2547 public:
2548  HXor(Primitive::Type result_type, HInstruction* left, HInstruction* right)
2549      : HBinaryOperation(result_type, left, right) {}
2550
2551  bool IsCommutative() const OVERRIDE { return true; }
2552
2553  int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { return x ^ y; }
2554  int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { return x ^ y; }
2555
2556  DECLARE_INSTRUCTION(Xor);
2557
2558 private:
2559  DISALLOW_COPY_AND_ASSIGN(HXor);
2560};
2561
2562// The value of a parameter in this method. Its location depends on
2563// the calling convention.
2564class HParameterValue : public HExpression<0> {
2565 public:
2566  HParameterValue(uint8_t index, Primitive::Type parameter_type, bool is_this = false)
2567      : HExpression(parameter_type, SideEffects::None()), index_(index), is_this_(is_this) {}
2568
2569  uint8_t GetIndex() const { return index_; }
2570
2571  bool CanBeNull() const OVERRIDE { return !is_this_; }
2572
2573  DECLARE_INSTRUCTION(ParameterValue);
2574
2575 private:
2576  // The index of this parameter in the parameters list. Must be less
2577  // than HGraph::number_of_in_vregs_.
2578  const uint8_t index_;
2579
2580  // Whether or not the parameter value corresponds to 'this' argument.
2581  const bool is_this_;
2582
2583  DISALLOW_COPY_AND_ASSIGN(HParameterValue);
2584};
2585
2586class HNot : public HUnaryOperation {
2587 public:
2588  explicit HNot(Primitive::Type result_type, HInstruction* input)
2589      : HUnaryOperation(result_type, input) {}
2590
2591  bool CanBeMoved() const OVERRIDE { return true; }
2592  bool InstructionDataEquals(HInstruction* other) const OVERRIDE {
2593    UNUSED(other);
2594    return true;
2595  }
2596
2597  int32_t Evaluate(int32_t x) const OVERRIDE { return ~x; }
2598  int64_t Evaluate(int64_t x) const OVERRIDE { return ~x; }
2599
2600  DECLARE_INSTRUCTION(Not);
2601
2602 private:
2603  DISALLOW_COPY_AND_ASSIGN(HNot);
2604};
2605
2606class HTypeConversion : public HExpression<1> {
2607 public:
2608  // Instantiate a type conversion of `input` to `result_type`.
2609  HTypeConversion(Primitive::Type result_type, HInstruction* input, uint32_t dex_pc)
2610      : HExpression(result_type, SideEffects::None()), dex_pc_(dex_pc) {
2611    SetRawInputAt(0, input);
2612    DCHECK_NE(input->GetType(), result_type);
2613  }
2614
2615  HInstruction* GetInput() const { return InputAt(0); }
2616  Primitive::Type GetInputType() const { return GetInput()->GetType(); }
2617  Primitive::Type GetResultType() const { return GetType(); }
2618
2619  // Required by the x86 and ARM code generators when producing calls
2620  // to the runtime.
2621  uint32_t GetDexPc() const { return dex_pc_; }
2622
2623  bool CanBeMoved() const OVERRIDE { return true; }
2624  bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE { return true; }
2625
2626  DECLARE_INSTRUCTION(TypeConversion);
2627
2628 private:
2629  const uint32_t dex_pc_;
2630
2631  DISALLOW_COPY_AND_ASSIGN(HTypeConversion);
2632};
2633
2634static constexpr uint32_t kNoRegNumber = -1;
2635
2636class HPhi : public HInstruction {
2637 public:
2638  HPhi(ArenaAllocator* arena, uint32_t reg_number, size_t number_of_inputs, Primitive::Type type)
2639      : HInstruction(SideEffects::None()),
2640        inputs_(arena, number_of_inputs),
2641        reg_number_(reg_number),
2642        type_(type),
2643        is_live_(false),
2644        can_be_null_(true) {
2645    inputs_.SetSize(number_of_inputs);
2646  }
2647
2648  // Returns a type equivalent to the given `type`, but that a `HPhi` can hold.
2649  static Primitive::Type ToPhiType(Primitive::Type type) {
2650    switch (type) {
2651      case Primitive::kPrimBoolean:
2652      case Primitive::kPrimByte:
2653      case Primitive::kPrimShort:
2654      case Primitive::kPrimChar:
2655        return Primitive::kPrimInt;
2656      default:
2657        return type;
2658    }
2659  }
2660
2661  size_t InputCount() const OVERRIDE { return inputs_.Size(); }
2662
2663  void AddInput(HInstruction* input);
2664
2665  Primitive::Type GetType() const OVERRIDE { return type_; }
2666  void SetType(Primitive::Type type) { type_ = type; }
2667
2668  bool CanBeNull() const OVERRIDE { return can_be_null_; }
2669  void SetCanBeNull(bool can_be_null) { can_be_null_ = can_be_null; }
2670
2671  uint32_t GetRegNumber() const { return reg_number_; }
2672
2673  void SetDead() { is_live_ = false; }
2674  void SetLive() { is_live_ = true; }
2675  bool IsDead() const { return !is_live_; }
2676  bool IsLive() const { return is_live_; }
2677
2678  DECLARE_INSTRUCTION(Phi);
2679
2680 protected:
2681  const HUserRecord<HInstruction*> InputRecordAt(size_t i) const OVERRIDE { return inputs_.Get(i); }
2682
2683  void SetRawInputRecordAt(size_t index, const HUserRecord<HInstruction*>& input) OVERRIDE {
2684    inputs_.Put(index, input);
2685  }
2686
2687 private:
2688  GrowableArray<HUserRecord<HInstruction*> > inputs_;
2689  const uint32_t reg_number_;
2690  Primitive::Type type_;
2691  bool is_live_;
2692  bool can_be_null_;
2693
2694  DISALLOW_COPY_AND_ASSIGN(HPhi);
2695};
2696
2697class HNullCheck : public HExpression<1> {
2698 public:
2699  HNullCheck(HInstruction* value, uint32_t dex_pc)
2700      : HExpression(value->GetType(), SideEffects::None()), dex_pc_(dex_pc) {
2701    SetRawInputAt(0, value);
2702  }
2703
2704  bool CanBeMoved() const OVERRIDE { return true; }
2705  bool InstructionDataEquals(HInstruction* other) const OVERRIDE {
2706    UNUSED(other);
2707    return true;
2708  }
2709
2710  bool NeedsEnvironment() const OVERRIDE { return true; }
2711
2712  bool CanThrow() const OVERRIDE { return true; }
2713
2714  bool CanBeNull() const OVERRIDE { return false; }
2715
2716  uint32_t GetDexPc() const { return dex_pc_; }
2717
2718  DECLARE_INSTRUCTION(NullCheck);
2719
2720 private:
2721  const uint32_t dex_pc_;
2722
2723  DISALLOW_COPY_AND_ASSIGN(HNullCheck);
2724};
2725
2726class FieldInfo : public ValueObject {
2727 public:
2728  FieldInfo(MemberOffset field_offset, Primitive::Type field_type, bool is_volatile)
2729      : field_offset_(field_offset), field_type_(field_type), is_volatile_(is_volatile) {}
2730
2731  MemberOffset GetFieldOffset() const { return field_offset_; }
2732  Primitive::Type GetFieldType() const { return field_type_; }
2733  bool IsVolatile() const { return is_volatile_; }
2734
2735 private:
2736  const MemberOffset field_offset_;
2737  const Primitive::Type field_type_;
2738  const bool is_volatile_;
2739};
2740
2741class HInstanceFieldGet : public HExpression<1> {
2742 public:
2743  HInstanceFieldGet(HInstruction* value,
2744                    Primitive::Type field_type,
2745                    MemberOffset field_offset,
2746                    bool is_volatile)
2747      : HExpression(field_type, SideEffects::DependsOnSomething()),
2748        field_info_(field_offset, field_type, is_volatile) {
2749    SetRawInputAt(0, value);
2750  }
2751
2752  bool CanBeMoved() const OVERRIDE { return !IsVolatile(); }
2753
2754  bool InstructionDataEquals(HInstruction* other) const OVERRIDE {
2755    HInstanceFieldGet* other_get = other->AsInstanceFieldGet();
2756    return GetFieldOffset().SizeValue() == other_get->GetFieldOffset().SizeValue();
2757  }
2758
2759  bool CanDoImplicitNullCheck() const OVERRIDE {
2760    return GetFieldOffset().Uint32Value() < kPageSize;
2761  }
2762
2763  size_t ComputeHashCode() const OVERRIDE {
2764    return (HInstruction::ComputeHashCode() << 7) | GetFieldOffset().SizeValue();
2765  }
2766
2767  const FieldInfo& GetFieldInfo() const { return field_info_; }
2768  MemberOffset GetFieldOffset() const { return field_info_.GetFieldOffset(); }
2769  Primitive::Type GetFieldType() const { return field_info_.GetFieldType(); }
2770  bool IsVolatile() const { return field_info_.IsVolatile(); }
2771
2772  DECLARE_INSTRUCTION(InstanceFieldGet);
2773
2774 private:
2775  const FieldInfo field_info_;
2776
2777  DISALLOW_COPY_AND_ASSIGN(HInstanceFieldGet);
2778};
2779
2780class HInstanceFieldSet : public HTemplateInstruction<2> {
2781 public:
2782  HInstanceFieldSet(HInstruction* object,
2783                    HInstruction* value,
2784                    Primitive::Type field_type,
2785                    MemberOffset field_offset,
2786                    bool is_volatile)
2787      : HTemplateInstruction(SideEffects::ChangesSomething()),
2788        field_info_(field_offset, field_type, is_volatile) {
2789    SetRawInputAt(0, object);
2790    SetRawInputAt(1, value);
2791  }
2792
2793  bool CanDoImplicitNullCheck() const OVERRIDE {
2794    return GetFieldOffset().Uint32Value() < kPageSize;
2795  }
2796
2797  const FieldInfo& GetFieldInfo() const { return field_info_; }
2798  MemberOffset GetFieldOffset() const { return field_info_.GetFieldOffset(); }
2799  Primitive::Type GetFieldType() const { return field_info_.GetFieldType(); }
2800  bool IsVolatile() const { return field_info_.IsVolatile(); }
2801  HInstruction* GetValue() const { return InputAt(1); }
2802
2803  DECLARE_INSTRUCTION(InstanceFieldSet);
2804
2805 private:
2806  const FieldInfo field_info_;
2807
2808  DISALLOW_COPY_AND_ASSIGN(HInstanceFieldSet);
2809};
2810
2811class HArrayGet : public HExpression<2> {
2812 public:
2813  HArrayGet(HInstruction* array, HInstruction* index, Primitive::Type type)
2814      : HExpression(type, SideEffects::DependsOnSomething()) {
2815    SetRawInputAt(0, array);
2816    SetRawInputAt(1, index);
2817  }
2818
2819  bool CanBeMoved() const OVERRIDE { return true; }
2820  bool InstructionDataEquals(HInstruction* other) const OVERRIDE {
2821    UNUSED(other);
2822    return true;
2823  }
2824  bool CanDoImplicitNullCheck() const OVERRIDE {
2825    // TODO: We can be smarter here.
2826    // Currently, the array access is always preceded by an ArrayLength or a NullCheck
2827    // which generates the implicit null check. There are cases when these can be removed
2828    // to produce better code. If we ever add optimizations to do so we should allow an
2829    // implicit check here (as long as the address falls in the first page).
2830    return false;
2831  }
2832
2833  void SetType(Primitive::Type type) { type_ = type; }
2834
2835  HInstruction* GetArray() const { return InputAt(0); }
2836  HInstruction* GetIndex() const { return InputAt(1); }
2837
2838  DECLARE_INSTRUCTION(ArrayGet);
2839
2840 private:
2841  DISALLOW_COPY_AND_ASSIGN(HArrayGet);
2842};
2843
2844class HArraySet : public HTemplateInstruction<3> {
2845 public:
2846  HArraySet(HInstruction* array,
2847            HInstruction* index,
2848            HInstruction* value,
2849            Primitive::Type expected_component_type,
2850            uint32_t dex_pc)
2851      : HTemplateInstruction(SideEffects::ChangesSomething()),
2852        dex_pc_(dex_pc),
2853        expected_component_type_(expected_component_type),
2854        needs_type_check_(value->GetType() == Primitive::kPrimNot) {
2855    SetRawInputAt(0, array);
2856    SetRawInputAt(1, index);
2857    SetRawInputAt(2, value);
2858  }
2859
2860  bool NeedsEnvironment() const OVERRIDE {
2861    // We currently always call a runtime method to catch array store
2862    // exceptions.
2863    return needs_type_check_;
2864  }
2865
2866  bool CanDoImplicitNullCheck() const OVERRIDE {
2867    // TODO: Same as for ArrayGet.
2868    return false;
2869  }
2870
2871  void ClearNeedsTypeCheck() {
2872    needs_type_check_ = false;
2873  }
2874
2875  bool NeedsTypeCheck() const { return needs_type_check_; }
2876
2877  uint32_t GetDexPc() const { return dex_pc_; }
2878
2879  HInstruction* GetArray() const { return InputAt(0); }
2880  HInstruction* GetIndex() const { return InputAt(1); }
2881  HInstruction* GetValue() const { return InputAt(2); }
2882
2883  Primitive::Type GetComponentType() const {
2884    // The Dex format does not type floating point index operations. Since the
2885    // `expected_component_type_` is set during building and can therefore not
2886    // be correct, we also check what is the value type. If it is a floating
2887    // point type, we must use that type.
2888    Primitive::Type value_type = GetValue()->GetType();
2889    return ((value_type == Primitive::kPrimFloat) || (value_type == Primitive::kPrimDouble))
2890        ? value_type
2891        : expected_component_type_;
2892  }
2893
2894  DECLARE_INSTRUCTION(ArraySet);
2895
2896 private:
2897  const uint32_t dex_pc_;
2898  const Primitive::Type expected_component_type_;
2899  bool needs_type_check_;
2900
2901  DISALLOW_COPY_AND_ASSIGN(HArraySet);
2902};
2903
2904class HArrayLength : public HExpression<1> {
2905 public:
2906  explicit HArrayLength(HInstruction* array)
2907      : HExpression(Primitive::kPrimInt, SideEffects::None()) {
2908    // Note that arrays do not change length, so the instruction does not
2909    // depend on any write.
2910    SetRawInputAt(0, array);
2911  }
2912
2913  bool CanBeMoved() const OVERRIDE { return true; }
2914  bool InstructionDataEquals(HInstruction* other) const OVERRIDE {
2915    UNUSED(other);
2916    return true;
2917  }
2918  bool CanDoImplicitNullCheck() const OVERRIDE { return true; }
2919
2920  DECLARE_INSTRUCTION(ArrayLength);
2921
2922 private:
2923  DISALLOW_COPY_AND_ASSIGN(HArrayLength);
2924};
2925
2926class HBoundsCheck : public HExpression<2> {
2927 public:
2928  HBoundsCheck(HInstruction* index, HInstruction* length, uint32_t dex_pc)
2929      : HExpression(index->GetType(), SideEffects::None()), dex_pc_(dex_pc) {
2930    DCHECK(index->GetType() == Primitive::kPrimInt);
2931    SetRawInputAt(0, index);
2932    SetRawInputAt(1, length);
2933  }
2934
2935  bool CanBeMoved() const OVERRIDE { return true; }
2936  bool InstructionDataEquals(HInstruction* other) const OVERRIDE {
2937    UNUSED(other);
2938    return true;
2939  }
2940
2941  bool NeedsEnvironment() const OVERRIDE { return true; }
2942
2943  bool CanThrow() const OVERRIDE { return true; }
2944
2945  uint32_t GetDexPc() const { return dex_pc_; }
2946
2947  DECLARE_INSTRUCTION(BoundsCheck);
2948
2949 private:
2950  const uint32_t dex_pc_;
2951
2952  DISALLOW_COPY_AND_ASSIGN(HBoundsCheck);
2953};
2954
2955/**
2956 * Some DEX instructions are folded into multiple HInstructions that need
2957 * to stay live until the last HInstruction. This class
2958 * is used as a marker for the baseline compiler to ensure its preceding
2959 * HInstruction stays live. `index` represents the stack location index of the
2960 * instruction (the actual offset is computed as index * vreg_size).
2961 */
2962class HTemporary : public HTemplateInstruction<0> {
2963 public:
2964  explicit HTemporary(size_t index) : HTemplateInstruction(SideEffects::None()), index_(index) {}
2965
2966  size_t GetIndex() const { return index_; }
2967
2968  Primitive::Type GetType() const OVERRIDE {
2969    // The previous instruction is the one that will be stored in the temporary location.
2970    DCHECK(GetPrevious() != nullptr);
2971    return GetPrevious()->GetType();
2972  }
2973
2974  DECLARE_INSTRUCTION(Temporary);
2975
2976 private:
2977  const size_t index_;
2978
2979  DISALLOW_COPY_AND_ASSIGN(HTemporary);
2980};
2981
2982class HSuspendCheck : public HTemplateInstruction<0> {
2983 public:
2984  explicit HSuspendCheck(uint32_t dex_pc)
2985      : HTemplateInstruction(SideEffects::None()), dex_pc_(dex_pc) {}
2986
2987  bool NeedsEnvironment() const OVERRIDE {
2988    return true;
2989  }
2990
2991  uint32_t GetDexPc() const { return dex_pc_; }
2992
2993  DECLARE_INSTRUCTION(SuspendCheck);
2994
2995 private:
2996  const uint32_t dex_pc_;
2997
2998  DISALLOW_COPY_AND_ASSIGN(HSuspendCheck);
2999};
3000
3001/**
3002 * Instruction to load a Class object.
3003 */
3004class HLoadClass : public HExpression<0> {
3005 public:
3006  HLoadClass(uint16_t type_index,
3007             bool is_referrers_class,
3008             uint32_t dex_pc)
3009      : HExpression(Primitive::kPrimNot, SideEffects::None()),
3010        type_index_(type_index),
3011        is_referrers_class_(is_referrers_class),
3012        dex_pc_(dex_pc),
3013        generate_clinit_check_(false),
3014        loaded_class_rti_(ReferenceTypeInfo::CreateTop(/* is_exact */ false)) {}
3015
3016  bool CanBeMoved() const OVERRIDE { return true; }
3017
3018  bool InstructionDataEquals(HInstruction* other) const OVERRIDE {
3019    return other->AsLoadClass()->type_index_ == type_index_;
3020  }
3021
3022  size_t ComputeHashCode() const OVERRIDE { return type_index_; }
3023
3024  uint32_t GetDexPc() const { return dex_pc_; }
3025  uint16_t GetTypeIndex() const { return type_index_; }
3026  bool IsReferrersClass() const { return is_referrers_class_; }
3027
3028  bool NeedsEnvironment() const OVERRIDE {
3029    // Will call runtime and load the class if the class is not loaded yet.
3030    // TODO: finer grain decision.
3031    return !is_referrers_class_;
3032  }
3033
3034  bool MustGenerateClinitCheck() const {
3035    return generate_clinit_check_;
3036  }
3037
3038  void SetMustGenerateClinitCheck() {
3039    generate_clinit_check_ = true;
3040  }
3041
3042  bool CanCallRuntime() const {
3043    return MustGenerateClinitCheck() || !is_referrers_class_;
3044  }
3045
3046  bool CanThrow() const OVERRIDE {
3047    // May call runtime and and therefore can throw.
3048    // TODO: finer grain decision.
3049    return !is_referrers_class_;
3050  }
3051
3052  ReferenceTypeInfo GetLoadedClassRTI() {
3053    return loaded_class_rti_;
3054  }
3055
3056  void SetLoadedClassRTI(ReferenceTypeInfo rti) {
3057    // Make sure we only set exact types (the loaded class should never be merged).
3058    DCHECK(rti.IsExact());
3059    loaded_class_rti_ = rti;
3060  }
3061
3062  bool IsResolved() {
3063    return loaded_class_rti_.IsExact();
3064  }
3065
3066  bool NeedsDexCache() const OVERRIDE { return !is_referrers_class_; }
3067
3068  DECLARE_INSTRUCTION(LoadClass);
3069
3070 private:
3071  const uint16_t type_index_;
3072  const bool is_referrers_class_;
3073  const uint32_t dex_pc_;
3074  // Whether this instruction must generate the initialization check.
3075  // Used for code generation.
3076  bool generate_clinit_check_;
3077
3078  ReferenceTypeInfo loaded_class_rti_;
3079
3080  DISALLOW_COPY_AND_ASSIGN(HLoadClass);
3081};
3082
3083class HLoadString : public HExpression<0> {
3084 public:
3085  HLoadString(uint32_t string_index, uint32_t dex_pc)
3086      : HExpression(Primitive::kPrimNot, SideEffects::None()),
3087        string_index_(string_index),
3088        dex_pc_(dex_pc) {}
3089
3090  bool CanBeMoved() const OVERRIDE { return true; }
3091
3092  bool InstructionDataEquals(HInstruction* other) const OVERRIDE {
3093    return other->AsLoadString()->string_index_ == string_index_;
3094  }
3095
3096  size_t ComputeHashCode() const OVERRIDE { return string_index_; }
3097
3098  uint32_t GetDexPc() const { return dex_pc_; }
3099  uint32_t GetStringIndex() const { return string_index_; }
3100
3101  // TODO: Can we deopt or debug when we resolve a string?
3102  bool NeedsEnvironment() const OVERRIDE { return false; }
3103  bool NeedsDexCache() const OVERRIDE { return true; }
3104
3105  DECLARE_INSTRUCTION(LoadString);
3106
3107 private:
3108  const uint32_t string_index_;
3109  const uint32_t dex_pc_;
3110
3111  DISALLOW_COPY_AND_ASSIGN(HLoadString);
3112};
3113
3114// TODO: Pass this check to HInvokeStaticOrDirect nodes.
3115/**
3116 * Performs an initialization check on its Class object input.
3117 */
3118class HClinitCheck : public HExpression<1> {
3119 public:
3120  explicit HClinitCheck(HLoadClass* constant, uint32_t dex_pc)
3121      : HExpression(Primitive::kPrimNot, SideEffects::ChangesSomething()),
3122        dex_pc_(dex_pc) {
3123    SetRawInputAt(0, constant);
3124  }
3125
3126  bool CanBeMoved() const OVERRIDE { return true; }
3127  bool InstructionDataEquals(HInstruction* other) const OVERRIDE {
3128    UNUSED(other);
3129    return true;
3130  }
3131
3132  bool NeedsEnvironment() const OVERRIDE {
3133    // May call runtime to initialize the class.
3134    return true;
3135  }
3136
3137  uint32_t GetDexPc() const { return dex_pc_; }
3138
3139  HLoadClass* GetLoadClass() const { return InputAt(0)->AsLoadClass(); }
3140
3141  DECLARE_INSTRUCTION(ClinitCheck);
3142
3143 private:
3144  const uint32_t dex_pc_;
3145
3146  DISALLOW_COPY_AND_ASSIGN(HClinitCheck);
3147};
3148
3149class HStaticFieldGet : public HExpression<1> {
3150 public:
3151  HStaticFieldGet(HInstruction* cls,
3152                  Primitive::Type field_type,
3153                  MemberOffset field_offset,
3154                  bool is_volatile)
3155      : HExpression(field_type, SideEffects::DependsOnSomething()),
3156        field_info_(field_offset, field_type, is_volatile) {
3157    SetRawInputAt(0, cls);
3158  }
3159
3160
3161  bool CanBeMoved() const OVERRIDE { return !IsVolatile(); }
3162
3163  bool InstructionDataEquals(HInstruction* other) const OVERRIDE {
3164    HStaticFieldGet* other_get = other->AsStaticFieldGet();
3165    return GetFieldOffset().SizeValue() == other_get->GetFieldOffset().SizeValue();
3166  }
3167
3168  size_t ComputeHashCode() const OVERRIDE {
3169    return (HInstruction::ComputeHashCode() << 7) | GetFieldOffset().SizeValue();
3170  }
3171
3172  const FieldInfo& GetFieldInfo() const { return field_info_; }
3173  MemberOffset GetFieldOffset() const { return field_info_.GetFieldOffset(); }
3174  Primitive::Type GetFieldType() const { return field_info_.GetFieldType(); }
3175  bool IsVolatile() const { return field_info_.IsVolatile(); }
3176
3177  DECLARE_INSTRUCTION(StaticFieldGet);
3178
3179 private:
3180  const FieldInfo field_info_;
3181
3182  DISALLOW_COPY_AND_ASSIGN(HStaticFieldGet);
3183};
3184
3185class HStaticFieldSet : public HTemplateInstruction<2> {
3186 public:
3187  HStaticFieldSet(HInstruction* cls,
3188                  HInstruction* value,
3189                  Primitive::Type field_type,
3190                  MemberOffset field_offset,
3191                  bool is_volatile)
3192      : HTemplateInstruction(SideEffects::ChangesSomething()),
3193        field_info_(field_offset, field_type, is_volatile) {
3194    SetRawInputAt(0, cls);
3195    SetRawInputAt(1, value);
3196  }
3197
3198  const FieldInfo& GetFieldInfo() const { return field_info_; }
3199  MemberOffset GetFieldOffset() const { return field_info_.GetFieldOffset(); }
3200  Primitive::Type GetFieldType() const { return field_info_.GetFieldType(); }
3201  bool IsVolatile() const { return field_info_.IsVolatile(); }
3202
3203  HInstruction* GetValue() const { return InputAt(1); }
3204
3205  DECLARE_INSTRUCTION(StaticFieldSet);
3206
3207 private:
3208  const FieldInfo field_info_;
3209
3210  DISALLOW_COPY_AND_ASSIGN(HStaticFieldSet);
3211};
3212
3213// Implement the move-exception DEX instruction.
3214class HLoadException : public HExpression<0> {
3215 public:
3216  HLoadException() : HExpression(Primitive::kPrimNot, SideEffects::None()) {}
3217
3218  DECLARE_INSTRUCTION(LoadException);
3219
3220 private:
3221  DISALLOW_COPY_AND_ASSIGN(HLoadException);
3222};
3223
3224class HThrow : public HTemplateInstruction<1> {
3225 public:
3226  HThrow(HInstruction* exception, uint32_t dex_pc)
3227      : HTemplateInstruction(SideEffects::None()), dex_pc_(dex_pc) {
3228    SetRawInputAt(0, exception);
3229  }
3230
3231  bool IsControlFlow() const OVERRIDE { return true; }
3232
3233  bool NeedsEnvironment() const OVERRIDE { return true; }
3234
3235  bool CanThrow() const OVERRIDE { return true; }
3236
3237  uint32_t GetDexPc() const { return dex_pc_; }
3238
3239  DECLARE_INSTRUCTION(Throw);
3240
3241 private:
3242  const uint32_t dex_pc_;
3243
3244  DISALLOW_COPY_AND_ASSIGN(HThrow);
3245};
3246
3247class HInstanceOf : public HExpression<2> {
3248 public:
3249  HInstanceOf(HInstruction* object,
3250              HLoadClass* constant,
3251              bool class_is_final,
3252              uint32_t dex_pc)
3253      : HExpression(Primitive::kPrimBoolean, SideEffects::None()),
3254        class_is_final_(class_is_final),
3255        dex_pc_(dex_pc) {
3256    SetRawInputAt(0, object);
3257    SetRawInputAt(1, constant);
3258  }
3259
3260  bool CanBeMoved() const OVERRIDE { return true; }
3261
3262  bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE {
3263    return true;
3264  }
3265
3266  bool NeedsEnvironment() const OVERRIDE {
3267    return false;
3268  }
3269
3270  uint32_t GetDexPc() const { return dex_pc_; }
3271
3272  bool IsClassFinal() const { return class_is_final_; }
3273
3274  DECLARE_INSTRUCTION(InstanceOf);
3275
3276 private:
3277  const bool class_is_final_;
3278  const uint32_t dex_pc_;
3279
3280  DISALLOW_COPY_AND_ASSIGN(HInstanceOf);
3281};
3282
3283class HBoundType : public HExpression<1> {
3284 public:
3285  HBoundType(HInstruction* input, ReferenceTypeInfo bound_type)
3286      : HExpression(Primitive::kPrimNot, SideEffects::None()),
3287        bound_type_(bound_type) {
3288    DCHECK_EQ(input->GetType(), Primitive::kPrimNot);
3289    SetRawInputAt(0, input);
3290  }
3291
3292  const ReferenceTypeInfo& GetBoundType() const { return bound_type_; }
3293
3294  bool CanBeNull() const OVERRIDE {
3295    // `null instanceof ClassX` always return false so we can't be null.
3296    return false;
3297  }
3298
3299  DECLARE_INSTRUCTION(BoundType);
3300
3301 private:
3302  // Encodes the most upper class that this instruction can have. In other words
3303  // it is always the case that GetBoundType().IsSupertypeOf(GetReferenceType()).
3304  // It is used to bound the type in cases like `if (x instanceof ClassX) {}`
3305  const ReferenceTypeInfo bound_type_;
3306
3307  DISALLOW_COPY_AND_ASSIGN(HBoundType);
3308};
3309
3310class HCheckCast : public HTemplateInstruction<2> {
3311 public:
3312  HCheckCast(HInstruction* object,
3313             HLoadClass* constant,
3314             bool class_is_final,
3315             uint32_t dex_pc)
3316      : HTemplateInstruction(SideEffects::None()),
3317        class_is_final_(class_is_final),
3318        dex_pc_(dex_pc) {
3319    SetRawInputAt(0, object);
3320    SetRawInputAt(1, constant);
3321  }
3322
3323  bool CanBeMoved() const OVERRIDE { return true; }
3324
3325  bool InstructionDataEquals(HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE {
3326    return true;
3327  }
3328
3329  bool NeedsEnvironment() const OVERRIDE {
3330    // Instruction may throw a CheckCastError.
3331    return true;
3332  }
3333
3334  bool CanThrow() const OVERRIDE { return true; }
3335
3336  uint32_t GetDexPc() const { return dex_pc_; }
3337
3338  bool IsClassFinal() const { return class_is_final_; }
3339
3340  DECLARE_INSTRUCTION(CheckCast);
3341
3342 private:
3343  const bool class_is_final_;
3344  const uint32_t dex_pc_;
3345
3346  DISALLOW_COPY_AND_ASSIGN(HCheckCast);
3347};
3348
3349class HMonitorOperation : public HTemplateInstruction<1> {
3350 public:
3351  enum OperationKind {
3352    kEnter,
3353    kExit,
3354  };
3355
3356  HMonitorOperation(HInstruction* object, OperationKind kind, uint32_t dex_pc)
3357    : HTemplateInstruction(SideEffects::None()), kind_(kind), dex_pc_(dex_pc) {
3358    SetRawInputAt(0, object);
3359  }
3360
3361  // Instruction may throw a Java exception, so we need an environment.
3362  bool NeedsEnvironment() const OVERRIDE { return true; }
3363  bool CanThrow() const OVERRIDE { return true; }
3364
3365  uint32_t GetDexPc() const { return dex_pc_; }
3366
3367  bool IsEnter() const { return kind_ == kEnter; }
3368
3369  DECLARE_INSTRUCTION(MonitorOperation);
3370
3371 private:
3372  const OperationKind kind_;
3373  const uint32_t dex_pc_;
3374
3375 private:
3376  DISALLOW_COPY_AND_ASSIGN(HMonitorOperation);
3377};
3378
3379class MoveOperands : public ArenaObject<kArenaAllocMisc> {
3380 public:
3381  MoveOperands(Location source, Location destination, HInstruction* instruction)
3382      : source_(source), destination_(destination), instruction_(instruction) {}
3383
3384  Location GetSource() const { return source_; }
3385  Location GetDestination() const { return destination_; }
3386
3387  void SetSource(Location value) { source_ = value; }
3388  void SetDestination(Location value) { destination_ = value; }
3389
3390  // The parallel move resolver marks moves as "in-progress" by clearing the
3391  // destination (but not the source).
3392  Location MarkPending() {
3393    DCHECK(!IsPending());
3394    Location dest = destination_;
3395    destination_ = Location::NoLocation();
3396    return dest;
3397  }
3398
3399  void ClearPending(Location dest) {
3400    DCHECK(IsPending());
3401    destination_ = dest;
3402  }
3403
3404  bool IsPending() const {
3405    DCHECK(!source_.IsInvalid() || destination_.IsInvalid());
3406    return destination_.IsInvalid() && !source_.IsInvalid();
3407  }
3408
3409  // True if this blocks a move from the given location.
3410  bool Blocks(Location loc) const {
3411    return !IsEliminated() && (source_.Contains(loc) || loc.Contains(source_));
3412  }
3413
3414  // A move is redundant if it's been eliminated, if its source and
3415  // destination are the same, or if its destination is unneeded.
3416  bool IsRedundant() const {
3417    return IsEliminated() || destination_.IsInvalid() || source_.Equals(destination_);
3418  }
3419
3420  // We clear both operands to indicate move that's been eliminated.
3421  void Eliminate() {
3422    source_ = destination_ = Location::NoLocation();
3423  }
3424
3425  bool IsEliminated() const {
3426    DCHECK(!source_.IsInvalid() || destination_.IsInvalid());
3427    return source_.IsInvalid();
3428  }
3429
3430  HInstruction* GetInstruction() const { return instruction_; }
3431
3432 private:
3433  Location source_;
3434  Location destination_;
3435  // The instruction this move is assocatied with. Null when this move is
3436  // for moving an input in the expected locations of user (including a phi user).
3437  // This is only used in debug mode, to ensure we do not connect interval siblings
3438  // in the same parallel move.
3439  HInstruction* instruction_;
3440};
3441
3442static constexpr size_t kDefaultNumberOfMoves = 4;
3443
3444class HParallelMove : public HTemplateInstruction<0> {
3445 public:
3446  explicit HParallelMove(ArenaAllocator* arena)
3447      : HTemplateInstruction(SideEffects::None()), moves_(arena, kDefaultNumberOfMoves) {}
3448
3449  void AddMove(Location source, Location destination, HInstruction* instruction) {
3450    DCHECK(source.IsValid());
3451    DCHECK(destination.IsValid());
3452    if (kIsDebugBuild) {
3453      if (instruction != nullptr) {
3454        for (size_t i = 0, e = moves_.Size(); i < e; ++i) {
3455          if (moves_.Get(i).GetInstruction() == instruction) {
3456            // Special case the situation where the move is for the spill slot
3457            // of the instruction.
3458            if ((GetPrevious() == instruction)
3459                || ((GetPrevious() == nullptr)
3460                    && instruction->IsPhi()
3461                    && instruction->GetBlock() == GetBlock())) {
3462              DCHECK_NE(destination.GetKind(), moves_.Get(i).GetDestination().GetKind())
3463                  << "Doing parallel moves for the same instruction.";
3464            } else {
3465              DCHECK(false) << "Doing parallel moves for the same instruction.";
3466            }
3467          }
3468        }
3469      }
3470      for (size_t i = 0, e = moves_.Size(); i < e; ++i) {
3471        DCHECK(!destination.Equals(moves_.Get(i).GetDestination()))
3472            << "Same destination for two moves in a parallel move.";
3473      }
3474    }
3475    moves_.Add(MoveOperands(source, destination, instruction));
3476  }
3477
3478  MoveOperands* MoveOperandsAt(size_t index) const {
3479    return moves_.GetRawStorage() + index;
3480  }
3481
3482  size_t NumMoves() const { return moves_.Size(); }
3483
3484  DECLARE_INSTRUCTION(ParallelMove);
3485
3486 private:
3487  GrowableArray<MoveOperands> moves_;
3488
3489  DISALLOW_COPY_AND_ASSIGN(HParallelMove);
3490};
3491
3492class HGraphVisitor : public ValueObject {
3493 public:
3494  explicit HGraphVisitor(HGraph* graph) : graph_(graph) {}
3495  virtual ~HGraphVisitor() {}
3496
3497  virtual void VisitInstruction(HInstruction* instruction) { UNUSED(instruction); }
3498  virtual void VisitBasicBlock(HBasicBlock* block);
3499
3500  // Visit the graph following basic block insertion order.
3501  void VisitInsertionOrder();
3502
3503  // Visit the graph following dominator tree reverse post-order.
3504  void VisitReversePostOrder();
3505
3506  HGraph* GetGraph() const { return graph_; }
3507
3508  // Visit functions for instruction classes.
3509#define DECLARE_VISIT_INSTRUCTION(name, super)                                        \
3510  virtual void Visit##name(H##name* instr) { VisitInstruction(instr); }
3511
3512  FOR_EACH_INSTRUCTION(DECLARE_VISIT_INSTRUCTION)
3513
3514#undef DECLARE_VISIT_INSTRUCTION
3515
3516 private:
3517  HGraph* const graph_;
3518
3519  DISALLOW_COPY_AND_ASSIGN(HGraphVisitor);
3520};
3521
3522class HGraphDelegateVisitor : public HGraphVisitor {
3523 public:
3524  explicit HGraphDelegateVisitor(HGraph* graph) : HGraphVisitor(graph) {}
3525  virtual ~HGraphDelegateVisitor() {}
3526
3527  // Visit functions that delegate to to super class.
3528#define DECLARE_VISIT_INSTRUCTION(name, super)                                        \
3529  void Visit##name(H##name* instr) OVERRIDE { Visit##super(instr); }
3530
3531  FOR_EACH_INSTRUCTION(DECLARE_VISIT_INSTRUCTION)
3532
3533#undef DECLARE_VISIT_INSTRUCTION
3534
3535 private:
3536  DISALLOW_COPY_AND_ASSIGN(HGraphDelegateVisitor);
3537};
3538
3539class HInsertionOrderIterator : public ValueObject {
3540 public:
3541  explicit HInsertionOrderIterator(const HGraph& graph) : graph_(graph), index_(0) {}
3542
3543  bool Done() const { return index_ == graph_.GetBlocks().Size(); }
3544  HBasicBlock* Current() const { return graph_.GetBlocks().Get(index_); }
3545  void Advance() { ++index_; }
3546
3547 private:
3548  const HGraph& graph_;
3549  size_t index_;
3550
3551  DISALLOW_COPY_AND_ASSIGN(HInsertionOrderIterator);
3552};
3553
3554class HReversePostOrderIterator : public ValueObject {
3555 public:
3556  explicit HReversePostOrderIterator(const HGraph& graph) : graph_(graph), index_(0) {
3557    // Check that reverse post order of the graph has been built.
3558    DCHECK(!graph.GetReversePostOrder().IsEmpty());
3559  }
3560
3561  bool Done() const { return index_ == graph_.GetReversePostOrder().Size(); }
3562  HBasicBlock* Current() const { return graph_.GetReversePostOrder().Get(index_); }
3563  void Advance() { ++index_; }
3564
3565 private:
3566  const HGraph& graph_;
3567  size_t index_;
3568
3569  DISALLOW_COPY_AND_ASSIGN(HReversePostOrderIterator);
3570};
3571
3572class HPostOrderIterator : public ValueObject {
3573 public:
3574  explicit HPostOrderIterator(const HGraph& graph)
3575      : graph_(graph), index_(graph_.GetReversePostOrder().Size()) {
3576    // Check that reverse post order of the graph has been built.
3577    DCHECK(!graph.GetReversePostOrder().IsEmpty());
3578  }
3579
3580  bool Done() const { return index_ == 0; }
3581  HBasicBlock* Current() const { return graph_.GetReversePostOrder().Get(index_ - 1); }
3582  void Advance() { --index_; }
3583
3584 private:
3585  const HGraph& graph_;
3586  size_t index_;
3587
3588  DISALLOW_COPY_AND_ASSIGN(HPostOrderIterator);
3589};
3590
3591// Iterator over the blocks that art part of the loop. Includes blocks part
3592// of an inner loop. The order in which the blocks are iterated is on their
3593// block id.
3594class HBlocksInLoopIterator : public ValueObject {
3595 public:
3596  explicit HBlocksInLoopIterator(const HLoopInformation& info)
3597      : blocks_in_loop_(info.GetBlocks()),
3598        blocks_(info.GetHeader()->GetGraph()->GetBlocks()),
3599        index_(0) {
3600    if (!blocks_in_loop_.IsBitSet(index_)) {
3601      Advance();
3602    }
3603  }
3604
3605  bool Done() const { return index_ == blocks_.Size(); }
3606  HBasicBlock* Current() const { return blocks_.Get(index_); }
3607  void Advance() {
3608    ++index_;
3609    for (size_t e = blocks_.Size(); index_ < e; ++index_) {
3610      if (blocks_in_loop_.IsBitSet(index_)) {
3611        break;
3612      }
3613    }
3614  }
3615
3616 private:
3617  const BitVector& blocks_in_loop_;
3618  const GrowableArray<HBasicBlock*>& blocks_;
3619  size_t index_;
3620
3621  DISALLOW_COPY_AND_ASSIGN(HBlocksInLoopIterator);
3622};
3623
3624inline int64_t Int64FromConstant(HConstant* constant) {
3625  DCHECK(constant->IsIntConstant() || constant->IsLongConstant());
3626  return constant->IsIntConstant() ? constant->AsIntConstant()->GetValue()
3627                                   : constant->AsLongConstant()->GetValue();
3628}
3629
3630}  // namespace art
3631
3632#endif  // ART_COMPILER_OPTIMIZING_NODES_H_
3633