Nicolas Geoffray | 818f210 | 2014-02-18 16:43:35 +0000 | [diff] [blame] | 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 | |
Nicolas Geoffray | 4e3d23a | 2014-05-22 18:32:45 +0100 | [diff] [blame] | 20 | #include "locations.h" |
Nicolas Geoffray | e503832 | 2014-07-04 09:41:32 +0100 | [diff] [blame] | 21 | #include "offsets.h" |
Ian Rogers | e63db27 | 2014-07-15 15:36:11 -0700 | [diff] [blame] | 22 | #include "primitive.h" |
Nicolas Geoffray | 818f210 | 2014-02-18 16:43:35 +0000 | [diff] [blame] | 23 | #include "utils/allocation.h" |
Nicolas Geoffray | 0e33643 | 2014-02-26 18:24:38 +0000 | [diff] [blame] | 24 | #include "utils/arena_bit_vector.h" |
Nicolas Geoffray | 818f210 | 2014-02-18 16:43:35 +0000 | [diff] [blame] | 25 | #include "utils/growable_array.h" |
| 26 | |
| 27 | namespace art { |
| 28 | |
| 29 | class HBasicBlock; |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 30 | class HEnvironment; |
Nicolas Geoffray | 818f210 | 2014-02-18 16:43:35 +0000 | [diff] [blame] | 31 | class HInstruction; |
Nicolas Geoffray | 3ff386a | 2014-03-04 14:46:47 +0000 | [diff] [blame] | 32 | class HIntConstant; |
Nicolas Geoffray | 818f210 | 2014-02-18 16:43:35 +0000 | [diff] [blame] | 33 | class HGraphVisitor; |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 34 | class HPhi; |
Nicolas Geoffray | 3c04974 | 2014-09-24 18:10:46 +0100 | [diff] [blame] | 35 | class HSuspendCheck; |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 36 | class LiveInterval; |
Nicolas Geoffray | bab4ed7 | 2014-03-11 17:53:17 +0000 | [diff] [blame] | 37 | class LocationSummary; |
Nicolas Geoffray | 818f210 | 2014-02-18 16:43:35 +0000 | [diff] [blame] | 38 | |
| 39 | static const int kDefaultNumberOfBlocks = 8; |
| 40 | static const int kDefaultNumberOfSuccessors = 2; |
| 41 | static const int kDefaultNumberOfPredecessors = 2; |
Nicolas Geoffray | d31cf3d | 2014-09-08 17:30:24 +0100 | [diff] [blame] | 42 | static const int kDefaultNumberOfDominatedBlocks = 1; |
Nicolas Geoffray | be9a92a | 2014-02-25 14:22:56 +0000 | [diff] [blame] | 43 | static const int kDefaultNumberOfBackEdges = 1; |
Nicolas Geoffray | 818f210 | 2014-02-18 16:43:35 +0000 | [diff] [blame] | 44 | |
Dave Allison | 20dfc79 | 2014-06-16 20:44:29 -0700 | [diff] [blame] | 45 | enum IfCondition { |
| 46 | kCondEQ, |
| 47 | kCondNE, |
| 48 | kCondLT, |
| 49 | kCondLE, |
| 50 | kCondGT, |
| 51 | kCondGE, |
| 52 | }; |
| 53 | |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 54 | class HInstructionList { |
| 55 | public: |
| 56 | HInstructionList() : first_instruction_(nullptr), last_instruction_(nullptr) {} |
| 57 | |
| 58 | void AddInstruction(HInstruction* instruction); |
| 59 | void RemoveInstruction(HInstruction* instruction); |
| 60 | |
Roland Levillain | 6b46923 | 2014-09-25 10:10:38 +0100 | [diff] [blame] | 61 | // Return true if this list contains `instruction`. |
| 62 | bool Contains(HInstruction* instruction) const; |
| 63 | |
Roland Levillain | ccc07a9 | 2014-09-16 14:48:16 +0100 | [diff] [blame] | 64 | // Return true if `instruction1` is found before `instruction2` in |
| 65 | // this instruction list and false otherwise. Abort if none |
| 66 | // of these instructions is found. |
| 67 | bool FoundBefore(const HInstruction* instruction1, |
| 68 | const HInstruction* instruction2) const; |
| 69 | |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 70 | private: |
| 71 | HInstruction* first_instruction_; |
| 72 | HInstruction* last_instruction_; |
| 73 | |
| 74 | friend class HBasicBlock; |
| 75 | friend class HInstructionIterator; |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 76 | friend class HBackwardInstructionIterator; |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 77 | |
| 78 | DISALLOW_COPY_AND_ASSIGN(HInstructionList); |
| 79 | }; |
| 80 | |
Nicolas Geoffray | 818f210 | 2014-02-18 16:43:35 +0000 | [diff] [blame] | 81 | // Control-flow graph of a method. Contains a list of basic blocks. |
| 82 | class HGraph : public ArenaObject { |
| 83 | public: |
| 84 | explicit HGraph(ArenaAllocator* arena) |
| 85 | : arena_(arena), |
Nicolas Geoffray | be9a92a | 2014-02-25 14:22:56 +0000 | [diff] [blame] | 86 | blocks_(arena, kDefaultNumberOfBlocks), |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 87 | reverse_post_order_(arena, kDefaultNumberOfBlocks), |
Nicolas Geoffray | 4a34a42 | 2014-04-03 10:38:37 +0100 | [diff] [blame] | 88 | maximum_number_of_out_vregs_(0), |
Nicolas Geoffray | f583e59 | 2014-04-07 13:20:42 +0100 | [diff] [blame] | 89 | number_of_vregs_(0), |
| 90 | number_of_in_vregs_(0), |
Nicolas Geoffray | e503832 | 2014-07-04 09:41:32 +0100 | [diff] [blame] | 91 | number_of_temporaries_(0), |
Dave Allison | 20dfc79 | 2014-06-16 20:44:29 -0700 | [diff] [blame] | 92 | current_instruction_id_(0) {} |
Nicolas Geoffray | 818f210 | 2014-02-18 16:43:35 +0000 | [diff] [blame] | 93 | |
Nicolas Geoffray | 787c307 | 2014-03-17 10:20:19 +0000 | [diff] [blame] | 94 | ArenaAllocator* GetArena() const { return arena_; } |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 95 | const GrowableArray<HBasicBlock*>& GetBlocks() const { return blocks_; } |
Nicolas Geoffray | 818f210 | 2014-02-18 16:43:35 +0000 | [diff] [blame] | 96 | |
Nicolas Geoffray | 787c307 | 2014-03-17 10:20:19 +0000 | [diff] [blame] | 97 | HBasicBlock* GetEntryBlock() const { return entry_block_; } |
| 98 | HBasicBlock* GetExitBlock() const { return exit_block_; } |
Nicolas Geoffray | d4dd255 | 2014-02-28 10:23:58 +0000 | [diff] [blame] | 99 | |
Nicolas Geoffray | 787c307 | 2014-03-17 10:20:19 +0000 | [diff] [blame] | 100 | void SetEntryBlock(HBasicBlock* block) { entry_block_ = block; } |
| 101 | void SetExitBlock(HBasicBlock* block) { exit_block_ = block; } |
Nicolas Geoffray | d4dd255 | 2014-02-28 10:23:58 +0000 | [diff] [blame] | 102 | |
Nicolas Geoffray | 818f210 | 2014-02-18 16:43:35 +0000 | [diff] [blame] | 103 | void AddBlock(HBasicBlock* block); |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 104 | |
Nicolas Geoffray | be9a92a | 2014-02-25 14:22:56 +0000 | [diff] [blame] | 105 | void BuildDominatorTree(); |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 106 | void TransformToSSA(); |
| 107 | void SimplifyCFG(); |
Nicolas Geoffray | 818f210 | 2014-02-18 16:43:35 +0000 | [diff] [blame] | 108 | |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 109 | // Find all natural loops in this graph. Aborts computation and returns false |
Nicolas Geoffray | f635e63 | 2014-05-14 09:43:38 +0100 | [diff] [blame] | 110 | // if one loop is not natural, that is the header does not dominate the back |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 111 | // edge. |
| 112 | bool FindNaturalLoops() const; |
| 113 | |
| 114 | void SplitCriticalEdge(HBasicBlock* block, HBasicBlock* successor); |
| 115 | void SimplifyLoop(HBasicBlock* header); |
| 116 | |
Nicolas Geoffray | 3ff386a | 2014-03-04 14:46:47 +0000 | [diff] [blame] | 117 | int GetNextInstructionId() { |
| 118 | return current_instruction_id_++; |
| 119 | } |
| 120 | |
Nicolas Geoffray | 4a34a42 | 2014-04-03 10:38:37 +0100 | [diff] [blame] | 121 | uint16_t GetMaximumNumberOfOutVRegs() const { |
| 122 | return maximum_number_of_out_vregs_; |
| 123 | } |
| 124 | |
| 125 | void UpdateMaximumNumberOfOutVRegs(uint16_t new_value) { |
| 126 | maximum_number_of_out_vregs_ = std::max(new_value, maximum_number_of_out_vregs_); |
| 127 | } |
| 128 | |
Nicolas Geoffray | e503832 | 2014-07-04 09:41:32 +0100 | [diff] [blame] | 129 | void UpdateNumberOfTemporaries(size_t count) { |
| 130 | number_of_temporaries_ = std::max(count, number_of_temporaries_); |
| 131 | } |
| 132 | |
| 133 | size_t GetNumberOfTemporaries() const { |
| 134 | return number_of_temporaries_; |
| 135 | } |
| 136 | |
Nicolas Geoffray | f583e59 | 2014-04-07 13:20:42 +0100 | [diff] [blame] | 137 | void SetNumberOfVRegs(uint16_t number_of_vregs) { |
| 138 | number_of_vregs_ = number_of_vregs; |
| 139 | } |
| 140 | |
| 141 | uint16_t GetNumberOfVRegs() const { |
| 142 | return number_of_vregs_; |
| 143 | } |
| 144 | |
| 145 | void SetNumberOfInVRegs(uint16_t value) { |
| 146 | number_of_in_vregs_ = value; |
| 147 | } |
| 148 | |
| 149 | uint16_t GetNumberOfInVRegs() const { |
| 150 | return number_of_in_vregs_; |
| 151 | } |
| 152 | |
Nicolas Geoffray | ab032bc | 2014-07-15 12:55:21 +0100 | [diff] [blame] | 153 | uint16_t GetNumberOfLocalVRegs() const { |
| 154 | return number_of_vregs_ - number_of_in_vregs_; |
| 155 | } |
| 156 | |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 157 | const GrowableArray<HBasicBlock*>& GetReversePostOrder() const { |
| 158 | return reverse_post_order_; |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 159 | } |
Nicolas Geoffray | f583e59 | 2014-04-07 13:20:42 +0100 | [diff] [blame] | 160 | |
Nicolas Geoffray | 818f210 | 2014-02-18 16:43:35 +0000 | [diff] [blame] | 161 | private: |
Nicolas Geoffray | be9a92a | 2014-02-25 14:22:56 +0000 | [diff] [blame] | 162 | HBasicBlock* FindCommonDominator(HBasicBlock* first, HBasicBlock* second) const; |
| 163 | void VisitBlockForDominatorTree(HBasicBlock* block, |
| 164 | HBasicBlock* predecessor, |
| 165 | GrowableArray<size_t>* visits); |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 166 | void FindBackEdges(ArenaBitVector* visited); |
Nicolas Geoffray | be9a92a | 2014-02-25 14:22:56 +0000 | [diff] [blame] | 167 | void VisitBlockForBackEdges(HBasicBlock* block, |
| 168 | ArenaBitVector* visited, |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 169 | ArenaBitVector* visiting); |
Nicolas Geoffray | be9a92a | 2014-02-25 14:22:56 +0000 | [diff] [blame] | 170 | void RemoveDeadBlocks(const ArenaBitVector& visited) const; |
| 171 | |
Nicolas Geoffray | 818f210 | 2014-02-18 16:43:35 +0000 | [diff] [blame] | 172 | ArenaAllocator* const arena_; |
Nicolas Geoffray | be9a92a | 2014-02-25 14:22:56 +0000 | [diff] [blame] | 173 | |
| 174 | // List of blocks in insertion order. |
Nicolas Geoffray | 818f210 | 2014-02-18 16:43:35 +0000 | [diff] [blame] | 175 | GrowableArray<HBasicBlock*> blocks_; |
| 176 | |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 177 | // List of blocks to perform a reverse post order tree traversal. |
| 178 | GrowableArray<HBasicBlock*> reverse_post_order_; |
Nicolas Geoffray | be9a92a | 2014-02-25 14:22:56 +0000 | [diff] [blame] | 179 | |
Nicolas Geoffray | d4dd255 | 2014-02-28 10:23:58 +0000 | [diff] [blame] | 180 | HBasicBlock* entry_block_; |
| 181 | HBasicBlock* exit_block_; |
| 182 | |
Nicolas Geoffray | f583e59 | 2014-04-07 13:20:42 +0100 | [diff] [blame] | 183 | // The maximum number of virtual registers arguments passed to a HInvoke in this graph. |
Nicolas Geoffray | 4a34a42 | 2014-04-03 10:38:37 +0100 | [diff] [blame] | 184 | uint16_t maximum_number_of_out_vregs_; |
| 185 | |
Nicolas Geoffray | f583e59 | 2014-04-07 13:20:42 +0100 | [diff] [blame] | 186 | // The number of virtual registers in this method. Contains the parameters. |
| 187 | uint16_t number_of_vregs_; |
| 188 | |
| 189 | // The number of virtual registers used by parameters of this method. |
| 190 | uint16_t number_of_in_vregs_; |
| 191 | |
Nicolas Geoffray | e503832 | 2014-07-04 09:41:32 +0100 | [diff] [blame] | 192 | // The number of temporaries that will be needed for the baseline compiler. |
| 193 | size_t number_of_temporaries_; |
| 194 | |
Nicolas Geoffray | 3ff386a | 2014-03-04 14:46:47 +0000 | [diff] [blame] | 195 | // The current id to assign to a newly added instruction. See HInstruction.id_. |
| 196 | int current_instruction_id_; |
| 197 | |
Nicolas Geoffray | 818f210 | 2014-02-18 16:43:35 +0000 | [diff] [blame] | 198 | DISALLOW_COPY_AND_ASSIGN(HGraph); |
| 199 | }; |
| 200 | |
Nicolas Geoffray | be9a92a | 2014-02-25 14:22:56 +0000 | [diff] [blame] | 201 | class HLoopInformation : public ArenaObject { |
| 202 | public: |
| 203 | HLoopInformation(HBasicBlock* header, HGraph* graph) |
| 204 | : header_(header), |
Nicolas Geoffray | 3c04974 | 2014-09-24 18:10:46 +0100 | [diff] [blame] | 205 | suspend_check_(nullptr), |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 206 | back_edges_(graph->GetArena(), kDefaultNumberOfBackEdges), |
Nicolas Geoffray | b09aacb | 2014-09-17 18:21:53 +0100 | [diff] [blame] | 207 | // Make bit vector growable, as the number of blocks may change. |
| 208 | blocks_(graph->GetArena(), graph->GetBlocks().Size(), true) {} |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 209 | |
| 210 | HBasicBlock* GetHeader() const { |
| 211 | return header_; |
| 212 | } |
Nicolas Geoffray | be9a92a | 2014-02-25 14:22:56 +0000 | [diff] [blame] | 213 | |
Nicolas Geoffray | 3c04974 | 2014-09-24 18:10:46 +0100 | [diff] [blame] | 214 | HSuspendCheck* GetSuspendCheck() const { return suspend_check_; } |
| 215 | void SetSuspendCheck(HSuspendCheck* check) { suspend_check_ = check; } |
| 216 | bool HasSuspendCheck() const { return suspend_check_ != nullptr; } |
| 217 | |
Nicolas Geoffray | be9a92a | 2014-02-25 14:22:56 +0000 | [diff] [blame] | 218 | void AddBackEdge(HBasicBlock* back_edge) { |
| 219 | back_edges_.Add(back_edge); |
| 220 | } |
| 221 | |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 222 | void RemoveBackEdge(HBasicBlock* back_edge) { |
| 223 | back_edges_.Delete(back_edge); |
| 224 | } |
| 225 | |
| 226 | bool IsBackEdge(HBasicBlock* block) { |
| 227 | for (size_t i = 0, e = back_edges_.Size(); i < e; ++i) { |
| 228 | if (back_edges_.Get(i) == block) return true; |
| 229 | } |
| 230 | return false; |
| 231 | } |
| 232 | |
Nicolas Geoffray | be9a92a | 2014-02-25 14:22:56 +0000 | [diff] [blame] | 233 | int NumberOfBackEdges() const { |
| 234 | return back_edges_.Size(); |
| 235 | } |
| 236 | |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 237 | HBasicBlock* GetPreHeader() const; |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 238 | |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 239 | const GrowableArray<HBasicBlock*>& GetBackEdges() const { |
| 240 | return back_edges_; |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 241 | } |
| 242 | |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 243 | void ClearBackEdges() { |
| 244 | back_edges_.Reset(); |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 245 | } |
| 246 | |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 247 | // Find blocks that are part of this loop. Returns whether the loop is a natural loop, |
| 248 | // that is the header dominates the back edge. |
| 249 | bool Populate(); |
| 250 | |
| 251 | // Returns whether this loop information contains `block`. |
| 252 | // Note that this loop information *must* be populated before entering this function. |
| 253 | bool Contains(const HBasicBlock& block) const; |
| 254 | |
| 255 | // Returns whether this loop information is an inner loop of `other`. |
| 256 | // Note that `other` *must* be populated before entering this function. |
| 257 | bool IsIn(const HLoopInformation& other) const; |
| 258 | |
| 259 | const ArenaBitVector& GetBlocks() const { return blocks_; } |
| 260 | |
Nicolas Geoffray | be9a92a | 2014-02-25 14:22:56 +0000 | [diff] [blame] | 261 | private: |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 262 | // Internal recursive implementation of `Populate`. |
| 263 | void PopulateRecursive(HBasicBlock* block); |
| 264 | |
Nicolas Geoffray | be9a92a | 2014-02-25 14:22:56 +0000 | [diff] [blame] | 265 | HBasicBlock* header_; |
Nicolas Geoffray | 3c04974 | 2014-09-24 18:10:46 +0100 | [diff] [blame] | 266 | HSuspendCheck* suspend_check_; |
Nicolas Geoffray | be9a92a | 2014-02-25 14:22:56 +0000 | [diff] [blame] | 267 | GrowableArray<HBasicBlock*> back_edges_; |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 268 | ArenaBitVector blocks_; |
Nicolas Geoffray | be9a92a | 2014-02-25 14:22:56 +0000 | [diff] [blame] | 269 | |
| 270 | DISALLOW_COPY_AND_ASSIGN(HLoopInformation); |
| 271 | }; |
| 272 | |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 273 | static constexpr size_t kNoLifetime = -1; |
Nicolas Geoffray | 3c04974 | 2014-09-24 18:10:46 +0100 | [diff] [blame] | 274 | static constexpr uint32_t kNoDexPc = -1; |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 275 | |
Nicolas Geoffray | 818f210 | 2014-02-18 16:43:35 +0000 | [diff] [blame] | 276 | // A block in a method. Contains the list of instructions represented |
| 277 | // as a double linked list. Each block knows its predecessors and |
| 278 | // successors. |
Nicolas Geoffray | 3c04974 | 2014-09-24 18:10:46 +0100 | [diff] [blame] | 279 | |
Nicolas Geoffray | 818f210 | 2014-02-18 16:43:35 +0000 | [diff] [blame] | 280 | class HBasicBlock : public ArenaObject { |
| 281 | public: |
Nicolas Geoffray | 3c04974 | 2014-09-24 18:10:46 +0100 | [diff] [blame] | 282 | explicit HBasicBlock(HGraph* graph, uint32_t dex_pc = kNoDexPc) |
Nicolas Geoffray | 818f210 | 2014-02-18 16:43:35 +0000 | [diff] [blame] | 283 | : graph_(graph), |
Nicolas Geoffray | 787c307 | 2014-03-17 10:20:19 +0000 | [diff] [blame] | 284 | predecessors_(graph->GetArena(), kDefaultNumberOfPredecessors), |
| 285 | successors_(graph->GetArena(), kDefaultNumberOfSuccessors), |
Nicolas Geoffray | be9a92a | 2014-02-25 14:22:56 +0000 | [diff] [blame] | 286 | loop_information_(nullptr), |
| 287 | dominator_(nullptr), |
Nicolas Geoffray | d31cf3d | 2014-09-08 17:30:24 +0100 | [diff] [blame] | 288 | dominated_blocks_(graph->GetArena(), kDefaultNumberOfDominatedBlocks), |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 289 | block_id_(-1), |
Nicolas Geoffray | 3c04974 | 2014-09-24 18:10:46 +0100 | [diff] [blame] | 290 | dex_pc_(dex_pc), |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 291 | lifetime_start_(kNoLifetime), |
| 292 | lifetime_end_(kNoLifetime) {} |
Nicolas Geoffray | 818f210 | 2014-02-18 16:43:35 +0000 | [diff] [blame] | 293 | |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 294 | const GrowableArray<HBasicBlock*>& GetPredecessors() const { |
| 295 | return predecessors_; |
Nicolas Geoffray | 818f210 | 2014-02-18 16:43:35 +0000 | [diff] [blame] | 296 | } |
| 297 | |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 298 | const GrowableArray<HBasicBlock*>& GetSuccessors() const { |
| 299 | return successors_; |
Nicolas Geoffray | 818f210 | 2014-02-18 16:43:35 +0000 | [diff] [blame] | 300 | } |
| 301 | |
Nicolas Geoffray | d31cf3d | 2014-09-08 17:30:24 +0100 | [diff] [blame] | 302 | const GrowableArray<HBasicBlock*>& GetDominatedBlocks() const { |
| 303 | return dominated_blocks_; |
| 304 | } |
| 305 | |
Nicolas Geoffray | 3c04974 | 2014-09-24 18:10:46 +0100 | [diff] [blame] | 306 | bool IsEntryBlock() const { |
| 307 | return graph_->GetEntryBlock() == this; |
| 308 | } |
| 309 | |
| 310 | bool IsExitBlock() const { |
| 311 | return graph_->GetExitBlock() == this; |
| 312 | } |
| 313 | |
Nicolas Geoffray | be9a92a | 2014-02-25 14:22:56 +0000 | [diff] [blame] | 314 | void AddBackEdge(HBasicBlock* back_edge) { |
| 315 | if (loop_information_ == nullptr) { |
Nicolas Geoffray | 787c307 | 2014-03-17 10:20:19 +0000 | [diff] [blame] | 316 | loop_information_ = new (graph_->GetArena()) HLoopInformation(this, graph_); |
Nicolas Geoffray | be9a92a | 2014-02-25 14:22:56 +0000 | [diff] [blame] | 317 | } |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 318 | DCHECK_EQ(loop_information_->GetHeader(), this); |
Nicolas Geoffray | be9a92a | 2014-02-25 14:22:56 +0000 | [diff] [blame] | 319 | loop_information_->AddBackEdge(back_edge); |
| 320 | } |
| 321 | |
Nicolas Geoffray | 787c307 | 2014-03-17 10:20:19 +0000 | [diff] [blame] | 322 | HGraph* GetGraph() const { return graph_; } |
Nicolas Geoffray | 818f210 | 2014-02-18 16:43:35 +0000 | [diff] [blame] | 323 | |
Nicolas Geoffray | 787c307 | 2014-03-17 10:20:19 +0000 | [diff] [blame] | 324 | int GetBlockId() const { return block_id_; } |
| 325 | void SetBlockId(int id) { block_id_ = id; } |
Nicolas Geoffray | 818f210 | 2014-02-18 16:43:35 +0000 | [diff] [blame] | 326 | |
Nicolas Geoffray | 787c307 | 2014-03-17 10:20:19 +0000 | [diff] [blame] | 327 | HBasicBlock* GetDominator() const { return dominator_; } |
| 328 | void SetDominator(HBasicBlock* dominator) { dominator_ = dominator; } |
Nicolas Geoffray | d31cf3d | 2014-09-08 17:30:24 +0100 | [diff] [blame] | 329 | void AddDominatedBlock(HBasicBlock* block) { dominated_blocks_.Add(block); } |
Nicolas Geoffray | be9a92a | 2014-02-25 14:22:56 +0000 | [diff] [blame] | 330 | |
| 331 | int NumberOfBackEdges() const { |
| 332 | return loop_information_ == nullptr |
| 333 | ? 0 |
| 334 | : loop_information_->NumberOfBackEdges(); |
| 335 | } |
| 336 | |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 337 | HInstruction* GetFirstInstruction() const { return instructions_.first_instruction_; } |
| 338 | HInstruction* GetLastInstruction() const { return instructions_.last_instruction_; } |
Nicolas Geoffray | f635e63 | 2014-05-14 09:43:38 +0100 | [diff] [blame] | 339 | const HInstructionList& GetInstructions() const { return instructions_; } |
| 340 | const HInstructionList& GetPhis() const { return phis_; } |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 341 | HInstruction* GetFirstPhi() const { return phis_.first_instruction_; } |
Nicolas Geoffray | 818f210 | 2014-02-18 16:43:35 +0000 | [diff] [blame] | 342 | |
| 343 | void AddSuccessor(HBasicBlock* block) { |
| 344 | successors_.Add(block); |
| 345 | block->predecessors_.Add(this); |
| 346 | } |
| 347 | |
Nicolas Geoffray | ec7e472 | 2014-06-06 11:24:33 +0100 | [diff] [blame] | 348 | void ReplaceSuccessor(HBasicBlock* existing, HBasicBlock* new_block) { |
| 349 | size_t successor_index = GetSuccessorIndexOf(existing); |
| 350 | DCHECK_NE(successor_index, static_cast<size_t>(-1)); |
| 351 | existing->RemovePredecessor(this); |
| 352 | new_block->predecessors_.Add(this); |
| 353 | successors_.Put(successor_index, new_block); |
Nicolas Geoffray | be9a92a | 2014-02-25 14:22:56 +0000 | [diff] [blame] | 354 | } |
| 355 | |
Nicolas Geoffray | ec7e472 | 2014-06-06 11:24:33 +0100 | [diff] [blame] | 356 | void RemovePredecessor(HBasicBlock* block) { |
| 357 | predecessors_.Delete(block); |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 358 | } |
| 359 | |
| 360 | void ClearAllPredecessors() { |
| 361 | predecessors_.Reset(); |
| 362 | } |
| 363 | |
| 364 | void AddPredecessor(HBasicBlock* block) { |
| 365 | predecessors_.Add(block); |
| 366 | block->successors_.Add(this); |
| 367 | } |
| 368 | |
Nicolas Geoffray | 604c6e4 | 2014-09-17 12:08:44 +0100 | [diff] [blame] | 369 | void SwapPredecessors() { |
Nicolas Geoffray | c83d441 | 2014-09-18 16:46:20 +0100 | [diff] [blame] | 370 | DCHECK_EQ(predecessors_.Size(), 2u); |
Nicolas Geoffray | 604c6e4 | 2014-09-17 12:08:44 +0100 | [diff] [blame] | 371 | HBasicBlock* temp = predecessors_.Get(0); |
| 372 | predecessors_.Put(0, predecessors_.Get(1)); |
| 373 | predecessors_.Put(1, temp); |
| 374 | } |
| 375 | |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 376 | size_t GetPredecessorIndexOf(HBasicBlock* predecessor) { |
| 377 | for (size_t i = 0, e = predecessors_.Size(); i < e; ++i) { |
| 378 | if (predecessors_.Get(i) == predecessor) { |
| 379 | return i; |
| 380 | } |
| 381 | } |
| 382 | return -1; |
| 383 | } |
| 384 | |
Nicolas Geoffray | ec7e472 | 2014-06-06 11:24:33 +0100 | [diff] [blame] | 385 | size_t GetSuccessorIndexOf(HBasicBlock* successor) { |
| 386 | for (size_t i = 0, e = successors_.Size(); i < e; ++i) { |
| 387 | if (successors_.Get(i) == successor) { |
| 388 | return i; |
| 389 | } |
| 390 | } |
| 391 | return -1; |
| 392 | } |
| 393 | |
Nicolas Geoffray | 818f210 | 2014-02-18 16:43:35 +0000 | [diff] [blame] | 394 | void AddInstruction(HInstruction* instruction); |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 395 | void RemoveInstruction(HInstruction* instruction); |
Nicolas Geoffray | 4e3d23a | 2014-05-22 18:32:45 +0100 | [diff] [blame] | 396 | void InsertInstructionBefore(HInstruction* instruction, HInstruction* cursor); |
Roland Levillain | ccc07a9 | 2014-09-16 14:48:16 +0100 | [diff] [blame] | 397 | // Replace instruction `initial` with `replacement` within this block. |
| 398 | void ReplaceAndRemoveInstructionWith(HInstruction* initial, |
| 399 | HInstruction* replacement); |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 400 | void AddPhi(HPhi* phi); |
| 401 | void RemovePhi(HPhi* phi); |
| 402 | |
| 403 | bool IsLoopHeader() const { |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 404 | return (loop_information_ != nullptr) && (loop_information_->GetHeader() == this); |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 405 | } |
| 406 | |
Roland Levillain | 6b879dd | 2014-09-22 17:13:44 +0100 | [diff] [blame] | 407 | bool IsLoopPreHeaderFirstPredecessor() const { |
| 408 | DCHECK(IsLoopHeader()); |
| 409 | DCHECK(!GetPredecessors().IsEmpty()); |
| 410 | return GetPredecessors().Get(0) == GetLoopInformation()->GetPreHeader(); |
| 411 | } |
| 412 | |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 413 | HLoopInformation* GetLoopInformation() const { |
| 414 | return loop_information_; |
| 415 | } |
Nicolas Geoffray | 818f210 | 2014-02-18 16:43:35 +0000 | [diff] [blame] | 416 | |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 417 | // Set the loop_information_ on this block. This method overrides the current |
| 418 | // loop_information if it is an outer loop of the passed loop information. |
| 419 | void SetInLoop(HLoopInformation* info) { |
| 420 | if (IsLoopHeader()) { |
| 421 | // Nothing to do. This just means `info` is an outer loop. |
| 422 | } else if (loop_information_ == nullptr) { |
| 423 | loop_information_ = info; |
| 424 | } else if (loop_information_->Contains(*info->GetHeader())) { |
| 425 | // Block is currently part of an outer loop. Make it part of this inner loop. |
| 426 | // Note that a non loop header having a loop information means this loop information |
| 427 | // has already been populated |
| 428 | loop_information_ = info; |
| 429 | } else { |
| 430 | // Block is part of an inner loop. Do not update the loop information. |
| 431 | // Note that we cannot do the check `info->Contains(loop_information_)->GetHeader()` |
| 432 | // at this point, because this method is being called while populating `info`. |
| 433 | } |
| 434 | } |
| 435 | |
Nicolas Geoffray | 7dc206a | 2014-07-11 09:49:49 +0100 | [diff] [blame] | 436 | bool IsInLoop() const { return loop_information_ != nullptr; } |
| 437 | |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 438 | // Returns wheter this block dominates the blocked passed as parameter. |
| 439 | bool Dominates(HBasicBlock* block) const; |
| 440 | |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 441 | size_t GetLifetimeStart() const { return lifetime_start_; } |
| 442 | size_t GetLifetimeEnd() const { return lifetime_end_; } |
| 443 | |
| 444 | void SetLifetimeStart(size_t start) { lifetime_start_ = start; } |
| 445 | void SetLifetimeEnd(size_t end) { lifetime_end_ = end; } |
| 446 | |
Nicolas Geoffray | 3c04974 | 2014-09-24 18:10:46 +0100 | [diff] [blame] | 447 | uint32_t GetDexPc() const { return dex_pc_; } |
| 448 | |
Nicolas Geoffray | 818f210 | 2014-02-18 16:43:35 +0000 | [diff] [blame] | 449 | private: |
| 450 | HGraph* const graph_; |
| 451 | GrowableArray<HBasicBlock*> predecessors_; |
| 452 | GrowableArray<HBasicBlock*> successors_; |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 453 | HInstructionList instructions_; |
| 454 | HInstructionList phis_; |
Nicolas Geoffray | be9a92a | 2014-02-25 14:22:56 +0000 | [diff] [blame] | 455 | HLoopInformation* loop_information_; |
| 456 | HBasicBlock* dominator_; |
Nicolas Geoffray | d31cf3d | 2014-09-08 17:30:24 +0100 | [diff] [blame] | 457 | GrowableArray<HBasicBlock*> dominated_blocks_; |
Nicolas Geoffray | 818f210 | 2014-02-18 16:43:35 +0000 | [diff] [blame] | 458 | int block_id_; |
Nicolas Geoffray | 3c04974 | 2014-09-24 18:10:46 +0100 | [diff] [blame] | 459 | // The dex program counter of the first instruction of this block. |
| 460 | const uint32_t dex_pc_; |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 461 | size_t lifetime_start_; |
| 462 | size_t lifetime_end_; |
Nicolas Geoffray | 818f210 | 2014-02-18 16:43:35 +0000 | [diff] [blame] | 463 | |
| 464 | DISALLOW_COPY_AND_ASSIGN(HBasicBlock); |
| 465 | }; |
| 466 | |
Nicolas Geoffray | 96f89a2 | 2014-07-11 10:57:49 +0100 | [diff] [blame] | 467 | #define FOR_EACH_CONCRETE_INSTRUCTION(M) \ |
Nicolas Geoffray | d8ee737 | 2014-03-28 15:43:40 +0000 | [diff] [blame] | 468 | M(Add) \ |
Dave Allison | 20dfc79 | 2014-06-16 20:44:29 -0700 | [diff] [blame] | 469 | M(Condition) \ |
Nicolas Geoffray | 3ff386a | 2014-03-04 14:46:47 +0000 | [diff] [blame] | 470 | M(Equal) \ |
Dave Allison | 20dfc79 | 2014-06-16 20:44:29 -0700 | [diff] [blame] | 471 | M(NotEqual) \ |
| 472 | M(LessThan) \ |
| 473 | M(LessThanOrEqual) \ |
| 474 | M(GreaterThan) \ |
| 475 | M(GreaterThanOrEqual) \ |
Nicolas Geoffray | 818f210 | 2014-02-18 16:43:35 +0000 | [diff] [blame] | 476 | M(Exit) \ |
| 477 | M(Goto) \ |
Nicolas Geoffray | be9a92a | 2014-02-25 14:22:56 +0000 | [diff] [blame] | 478 | M(If) \ |
Nicolas Geoffray | 3ff386a | 2014-03-04 14:46:47 +0000 | [diff] [blame] | 479 | M(IntConstant) \ |
Nicolas Geoffray | 8ccc3f5 | 2014-03-19 10:34:11 +0000 | [diff] [blame] | 480 | M(InvokeStatic) \ |
Nicolas Geoffray | e982f0b | 2014-08-13 02:11:24 +0100 | [diff] [blame] | 481 | M(InvokeVirtual) \ |
Nicolas Geoffray | 3ff386a | 2014-03-04 14:46:47 +0000 | [diff] [blame] | 482 | M(LoadLocal) \ |
| 483 | M(Local) \ |
Nicolas Geoffray | 01bc96d | 2014-04-11 17:43:50 +0100 | [diff] [blame] | 484 | M(LongConstant) \ |
Nicolas Geoffray | 2e7038a | 2014-04-03 18:49:58 +0100 | [diff] [blame] | 485 | M(NewInstance) \ |
Nicolas Geoffray | b55f835 | 2014-04-07 15:26:35 +0100 | [diff] [blame] | 486 | M(Not) \ |
Nicolas Geoffray | f583e59 | 2014-04-07 13:20:42 +0100 | [diff] [blame] | 487 | M(ParameterValue) \ |
Nicolas Geoffray | 4e3d23a | 2014-05-22 18:32:45 +0100 | [diff] [blame] | 488 | M(ParallelMove) \ |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 489 | M(Phi) \ |
Nicolas Geoffray | bab4ed7 | 2014-03-11 17:53:17 +0000 | [diff] [blame] | 490 | M(Return) \ |
Nicolas Geoffray | 818f210 | 2014-02-18 16:43:35 +0000 | [diff] [blame] | 491 | M(ReturnVoid) \ |
Nicolas Geoffray | 3ff386a | 2014-03-04 14:46:47 +0000 | [diff] [blame] | 492 | M(StoreLocal) \ |
Nicolas Geoffray | f583e59 | 2014-04-07 13:20:42 +0100 | [diff] [blame] | 493 | M(Sub) \ |
Nicolas Geoffray | 412f10c | 2014-06-19 10:00:34 +0100 | [diff] [blame] | 494 | M(Compare) \ |
Nicolas Geoffray | e503832 | 2014-07-04 09:41:32 +0100 | [diff] [blame] | 495 | M(InstanceFieldGet) \ |
| 496 | M(InstanceFieldSet) \ |
Nicolas Geoffray | 3c7bb98 | 2014-07-23 16:04:16 +0100 | [diff] [blame] | 497 | M(ArrayGet) \ |
| 498 | M(ArraySet) \ |
| 499 | M(ArrayLength) \ |
| 500 | M(BoundsCheck) \ |
Nicolas Geoffray | e503832 | 2014-07-04 09:41:32 +0100 | [diff] [blame] | 501 | M(NullCheck) \ |
| 502 | M(Temporary) \ |
Nicolas Geoffray | fbc695f | 2014-09-15 15:33:30 +0000 | [diff] [blame] | 503 | M(SuspendCheck) \ |
Nicolas Geoffray | 818f210 | 2014-02-18 16:43:35 +0000 | [diff] [blame] | 504 | |
Nicolas Geoffray | 96f89a2 | 2014-07-11 10:57:49 +0100 | [diff] [blame] | 505 | #define FOR_EACH_INSTRUCTION(M) \ |
| 506 | FOR_EACH_CONCRETE_INSTRUCTION(M) \ |
Roland Levillain | ccc07a9 | 2014-09-16 14:48:16 +0100 | [diff] [blame] | 507 | M(Constant) \ |
| 508 | M(BinaryOperation) |
Dave Allison | 20dfc79 | 2014-06-16 20:44:29 -0700 | [diff] [blame] | 509 | |
Nicolas Geoffray | bab4ed7 | 2014-03-11 17:53:17 +0000 | [diff] [blame] | 510 | #define FORWARD_DECLARATION(type) class H##type; |
| 511 | FOR_EACH_INSTRUCTION(FORWARD_DECLARATION) |
| 512 | #undef FORWARD_DECLARATION |
| 513 | |
Roland Levillain | ccc07a9 | 2014-09-16 14:48:16 +0100 | [diff] [blame] | 514 | #define DECLARE_INSTRUCTION(type) \ |
Nicolas Geoffray | d31cf3d | 2014-09-08 17:30:24 +0100 | [diff] [blame] | 515 | virtual InstructionKind GetKind() const { return k##type; } \ |
Roland Levillain | ccc07a9 | 2014-09-16 14:48:16 +0100 | [diff] [blame] | 516 | virtual const char* DebugName() const { return #type; } \ |
| 517 | virtual const H##type* As##type() const OVERRIDE { return this; } \ |
| 518 | virtual H##type* As##type() OVERRIDE { return this; } \ |
| 519 | virtual bool InstructionTypeEquals(HInstruction* other) const { \ |
| 520 | return other->Is##type(); \ |
| 521 | } \ |
| 522 | virtual void Accept(HGraphVisitor* visitor) |
Nicolas Geoffray | 818f210 | 2014-02-18 16:43:35 +0000 | [diff] [blame] | 523 | |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 524 | template <typename T> |
Nicolas Geoffray | 3ff386a | 2014-03-04 14:46:47 +0000 | [diff] [blame] | 525 | class HUseListNode : public ArenaObject { |
| 526 | public: |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 527 | HUseListNode(T* user, size_t index, HUseListNode* tail) |
Dave Allison | 20dfc79 | 2014-06-16 20:44:29 -0700 | [diff] [blame] | 528 | : user_(user), index_(index), tail_(tail) {} |
Nicolas Geoffray | 3ff386a | 2014-03-04 14:46:47 +0000 | [diff] [blame] | 529 | |
Nicolas Geoffray | 787c307 | 2014-03-17 10:20:19 +0000 | [diff] [blame] | 530 | HUseListNode* GetTail() const { return tail_; } |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 531 | T* GetUser() const { return user_; } |
| 532 | size_t GetIndex() const { return index_; } |
| 533 | |
| 534 | void SetTail(HUseListNode<T>* node) { tail_ = node; } |
Nicolas Geoffray | 3ff386a | 2014-03-04 14:46:47 +0000 | [diff] [blame] | 535 | |
| 536 | private: |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 537 | T* const user_; |
| 538 | const size_t index_; |
| 539 | HUseListNode<T>* tail_; |
Nicolas Geoffray | 3ff386a | 2014-03-04 14:46:47 +0000 | [diff] [blame] | 540 | |
| 541 | DISALLOW_COPY_AND_ASSIGN(HUseListNode); |
| 542 | }; |
| 543 | |
Nicolas Geoffray | 065bf77 | 2014-09-03 14:51:22 +0100 | [diff] [blame] | 544 | // Represents the side effects an instruction may have. |
| 545 | class SideEffects : public ValueObject { |
| 546 | public: |
Nicolas Geoffray | d31cf3d | 2014-09-08 17:30:24 +0100 | [diff] [blame] | 547 | SideEffects() : flags_(0) {} |
| 548 | |
Nicolas Geoffray | 065bf77 | 2014-09-03 14:51:22 +0100 | [diff] [blame] | 549 | static SideEffects None() { |
| 550 | return SideEffects(0); |
| 551 | } |
| 552 | |
| 553 | static SideEffects All() { |
| 554 | return SideEffects(ChangesSomething().flags_ | DependsOnSomething().flags_); |
| 555 | } |
| 556 | |
| 557 | static SideEffects ChangesSomething() { |
| 558 | return SideEffects((1 << kFlagChangesCount) - 1); |
| 559 | } |
| 560 | |
| 561 | static SideEffects DependsOnSomething() { |
| 562 | int count = kFlagDependsOnCount - kFlagChangesCount; |
| 563 | return SideEffects(((1 << count) - 1) << kFlagChangesCount); |
| 564 | } |
| 565 | |
Nicolas Geoffray | d31cf3d | 2014-09-08 17:30:24 +0100 | [diff] [blame] | 566 | SideEffects Union(SideEffects other) const { |
| 567 | return SideEffects(flags_ | other.flags_); |
| 568 | } |
| 569 | |
Roland Levillain | 72bceff | 2014-09-15 18:29:00 +0100 | [diff] [blame] | 570 | bool HasSideEffects() const { |
| 571 | size_t all_bits_set = (1 << kFlagChangesCount) - 1; |
| 572 | return (flags_ & all_bits_set) != 0; |
| 573 | } |
| 574 | |
Nicolas Geoffray | d31cf3d | 2014-09-08 17:30:24 +0100 | [diff] [blame] | 575 | bool HasAllSideEffects() const { |
| 576 | size_t all_bits_set = (1 << kFlagChangesCount) - 1; |
| 577 | return all_bits_set == (flags_ & all_bits_set); |
| 578 | } |
| 579 | |
| 580 | bool DependsOn(SideEffects other) const { |
| 581 | size_t depends_flags = other.ComputeDependsFlags(); |
| 582 | return (flags_ & depends_flags) != 0; |
| 583 | } |
| 584 | |
| 585 | bool HasDependencies() const { |
| 586 | int count = kFlagDependsOnCount - kFlagChangesCount; |
| 587 | size_t all_bits_set = (1 << count) - 1; |
| 588 | return ((flags_ >> kFlagChangesCount) & all_bits_set) != 0; |
| 589 | } |
| 590 | |
Nicolas Geoffray | 065bf77 | 2014-09-03 14:51:22 +0100 | [diff] [blame] | 591 | private: |
| 592 | static constexpr int kFlagChangesSomething = 0; |
| 593 | static constexpr int kFlagChangesCount = kFlagChangesSomething + 1; |
| 594 | |
| 595 | static constexpr int kFlagDependsOnSomething = kFlagChangesCount; |
| 596 | static constexpr int kFlagDependsOnCount = kFlagDependsOnSomething + 1; |
| 597 | |
Nicolas Geoffray | 065bf77 | 2014-09-03 14:51:22 +0100 | [diff] [blame] | 598 | explicit SideEffects(size_t flags) : flags_(flags) {} |
| 599 | |
Nicolas Geoffray | d31cf3d | 2014-09-08 17:30:24 +0100 | [diff] [blame] | 600 | size_t ComputeDependsFlags() const { |
| 601 | return flags_ << kFlagChangesCount; |
| 602 | } |
| 603 | |
| 604 | size_t flags_; |
Nicolas Geoffray | 065bf77 | 2014-09-03 14:51:22 +0100 | [diff] [blame] | 605 | }; |
| 606 | |
Nicolas Geoffray | 818f210 | 2014-02-18 16:43:35 +0000 | [diff] [blame] | 607 | class HInstruction : public ArenaObject { |
| 608 | public: |
Nicolas Geoffray | 065bf77 | 2014-09-03 14:51:22 +0100 | [diff] [blame] | 609 | explicit HInstruction(SideEffects side_effects) |
Nicolas Geoffray | bab4ed7 | 2014-03-11 17:53:17 +0000 | [diff] [blame] | 610 | : previous_(nullptr), |
| 611 | next_(nullptr), |
| 612 | block_(nullptr), |
| 613 | id_(-1), |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 614 | ssa_index_(-1), |
Nicolas Geoffray | bab4ed7 | 2014-03-11 17:53:17 +0000 | [diff] [blame] | 615 | uses_(nullptr), |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 616 | env_uses_(nullptr), |
| 617 | environment_(nullptr), |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 618 | locations_(nullptr), |
| 619 | live_interval_(nullptr), |
Nicolas Geoffray | 065bf77 | 2014-09-03 14:51:22 +0100 | [diff] [blame] | 620 | lifetime_position_(kNoLifetime), |
| 621 | side_effects_(side_effects) {} |
Nicolas Geoffray | bab4ed7 | 2014-03-11 17:53:17 +0000 | [diff] [blame] | 622 | |
Dave Allison | 20dfc79 | 2014-06-16 20:44:29 -0700 | [diff] [blame] | 623 | virtual ~HInstruction() {} |
Nicolas Geoffray | 818f210 | 2014-02-18 16:43:35 +0000 | [diff] [blame] | 624 | |
Nicolas Geoffray | d31cf3d | 2014-09-08 17:30:24 +0100 | [diff] [blame] | 625 | #define DECLARE_KIND(type) k##type, |
| 626 | enum InstructionKind { |
| 627 | FOR_EACH_INSTRUCTION(DECLARE_KIND) |
| 628 | }; |
| 629 | #undef DECLARE_KIND |
| 630 | |
Nicolas Geoffray | 787c307 | 2014-03-17 10:20:19 +0000 | [diff] [blame] | 631 | HInstruction* GetNext() const { return next_; } |
| 632 | HInstruction* GetPrevious() const { return previous_; } |
Nicolas Geoffray | 818f210 | 2014-02-18 16:43:35 +0000 | [diff] [blame] | 633 | |
Nicolas Geoffray | 787c307 | 2014-03-17 10:20:19 +0000 | [diff] [blame] | 634 | HBasicBlock* GetBlock() const { return block_; } |
| 635 | void SetBlock(HBasicBlock* block) { block_ = block; } |
Nicolas Geoffray | 7dc206a | 2014-07-11 09:49:49 +0100 | [diff] [blame] | 636 | bool IsInBlock() const { return block_ != nullptr; } |
| 637 | bool IsInLoop() const { return block_->IsInLoop(); } |
Nicolas Geoffray | 3ac17fc | 2014-08-06 23:02:54 +0100 | [diff] [blame] | 638 | bool IsLoopHeaderPhi() { return IsPhi() && block_->IsLoopHeader(); } |
Nicolas Geoffray | d4dd255 | 2014-02-28 10:23:58 +0000 | [diff] [blame] | 639 | |
Roland Levillain | 6b879dd | 2014-09-22 17:13:44 +0100 | [diff] [blame] | 640 | virtual size_t InputCount() const = 0; |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 641 | virtual HInstruction* InputAt(size_t i) const = 0; |
Nicolas Geoffray | 818f210 | 2014-02-18 16:43:35 +0000 | [diff] [blame] | 642 | |
| 643 | virtual void Accept(HGraphVisitor* visitor) = 0; |
| 644 | virtual const char* DebugName() const = 0; |
| 645 | |
Nicolas Geoffray | 01bc96d | 2014-04-11 17:43:50 +0100 | [diff] [blame] | 646 | virtual Primitive::Type GetType() const { return Primitive::kPrimVoid; } |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 647 | virtual void SetRawInputAt(size_t index, HInstruction* input) = 0; |
Nicolas Geoffray | 01bc96d | 2014-04-11 17:43:50 +0100 | [diff] [blame] | 648 | |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 649 | virtual bool NeedsEnvironment() const { return false; } |
Nicolas Geoffray | ec7e472 | 2014-06-06 11:24:33 +0100 | [diff] [blame] | 650 | virtual bool IsControlFlow() const { return false; } |
Roland Levillain | 72bceff | 2014-09-15 18:29:00 +0100 | [diff] [blame] | 651 | bool HasSideEffects() const { return side_effects_.HasSideEffects(); } |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 652 | |
| 653 | void AddUseAt(HInstruction* user, size_t index) { |
| 654 | uses_ = new (block_->GetGraph()->GetArena()) HUseListNode<HInstruction>(user, index, uses_); |
Nicolas Geoffray | 3ff386a | 2014-03-04 14:46:47 +0000 | [diff] [blame] | 655 | } |
| 656 | |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 657 | void AddEnvUseAt(HEnvironment* user, size_t index) { |
Nicolas Geoffray | 724c963 | 2014-09-22 12:27:27 +0100 | [diff] [blame] | 658 | DCHECK(user != nullptr); |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 659 | env_uses_ = new (block_->GetGraph()->GetArena()) HUseListNode<HEnvironment>( |
| 660 | user, index, env_uses_); |
| 661 | } |
| 662 | |
| 663 | void RemoveUser(HInstruction* user, size_t index); |
Nicolas Geoffray | 724c963 | 2014-09-22 12:27:27 +0100 | [diff] [blame] | 664 | void RemoveEnvironmentUser(HEnvironment* user, size_t index); |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 665 | |
| 666 | HUseListNode<HInstruction>* GetUses() const { return uses_; } |
| 667 | HUseListNode<HEnvironment>* GetEnvUses() const { return env_uses_; } |
Nicolas Geoffray | 3ff386a | 2014-03-04 14:46:47 +0000 | [diff] [blame] | 668 | |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 669 | bool HasUses() const { return uses_ != nullptr || env_uses_ != nullptr; } |
Nicolas Geoffray | 7dc206a | 2014-07-11 09:49:49 +0100 | [diff] [blame] | 670 | bool HasEnvironmentUses() const { return env_uses_ != nullptr; } |
Nicolas Geoffray | 3ff386a | 2014-03-04 14:46:47 +0000 | [diff] [blame] | 671 | |
Nicolas Geoffray | f635e63 | 2014-05-14 09:43:38 +0100 | [diff] [blame] | 672 | size_t NumberOfUses() const { |
Nicolas Geoffray | 0d3f578 | 2014-05-14 09:43:38 +0100 | [diff] [blame] | 673 | // TODO: Optimize this method if it is used outside of the HGraphVisualizer. |
Nicolas Geoffray | f635e63 | 2014-05-14 09:43:38 +0100 | [diff] [blame] | 674 | size_t result = 0; |
| 675 | HUseListNode<HInstruction>* current = uses_; |
| 676 | while (current != nullptr) { |
| 677 | current = current->GetTail(); |
| 678 | ++result; |
| 679 | } |
| 680 | return result; |
| 681 | } |
| 682 | |
Roland Levillain | ccc07a9 | 2014-09-16 14:48:16 +0100 | [diff] [blame] | 683 | // Does this instruction dominate `other_instruction`? Aborts if |
| 684 | // this instruction and `other_instruction` are both phis. |
| 685 | bool Dominates(HInstruction* other_instruction) const; |
| 686 | |
Nicolas Geoffray | 787c307 | 2014-03-17 10:20:19 +0000 | [diff] [blame] | 687 | int GetId() const { return id_; } |
| 688 | void SetId(int id) { id_ = id; } |
Nicolas Geoffray | 3ff386a | 2014-03-04 14:46:47 +0000 | [diff] [blame] | 689 | |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 690 | int GetSsaIndex() const { return ssa_index_; } |
| 691 | void SetSsaIndex(int ssa_index) { ssa_index_ = ssa_index; } |
| 692 | bool HasSsaIndex() const { return ssa_index_ != -1; } |
| 693 | |
| 694 | bool HasEnvironment() const { return environment_ != nullptr; } |
| 695 | HEnvironment* GetEnvironment() const { return environment_; } |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 696 | void SetEnvironment(HEnvironment* environment) { environment_ = environment; } |
| 697 | |
Nicolas Geoffray | 3946844 | 2014-09-02 15:17:15 +0100 | [diff] [blame] | 698 | // Returns the number of entries in the environment. Typically, that is the |
| 699 | // number of dex registers in a method. It could be more in case of inlining. |
| 700 | size_t EnvironmentSize() const; |
| 701 | |
Nicolas Geoffray | 787c307 | 2014-03-17 10:20:19 +0000 | [diff] [blame] | 702 | LocationSummary* GetLocations() const { return locations_; } |
| 703 | void SetLocations(LocationSummary* locations) { locations_ = locations; } |
Nicolas Geoffray | bab4ed7 | 2014-03-11 17:53:17 +0000 | [diff] [blame] | 704 | |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 705 | void ReplaceWith(HInstruction* instruction); |
| 706 | |
Dave Allison | 20dfc79 | 2014-06-16 20:44:29 -0700 | [diff] [blame] | 707 | bool HasOnlyOneUse() const { |
| 708 | return uses_ != nullptr && uses_->GetTail() == nullptr; |
| 709 | } |
| 710 | |
Nicolas Geoffray | bab4ed7 | 2014-03-11 17:53:17 +0000 | [diff] [blame] | 711 | #define INSTRUCTION_TYPE_CHECK(type) \ |
Roland Levillain | ccc07a9 | 2014-09-16 14:48:16 +0100 | [diff] [blame] | 712 | bool Is##type() const { return (As##type() != nullptr); } \ |
| 713 | virtual const H##type* As##type() const { return nullptr; } \ |
Nicolas Geoffray | bab4ed7 | 2014-03-11 17:53:17 +0000 | [diff] [blame] | 714 | virtual H##type* As##type() { return nullptr; } |
| 715 | |
| 716 | FOR_EACH_INSTRUCTION(INSTRUCTION_TYPE_CHECK) |
| 717 | #undef INSTRUCTION_TYPE_CHECK |
| 718 | |
Nicolas Geoffray | 065bf77 | 2014-09-03 14:51:22 +0100 | [diff] [blame] | 719 | // Returns whether the instruction can be moved within the graph. |
| 720 | virtual bool CanBeMoved() const { return false; } |
| 721 | |
| 722 | // Returns whether the two instructions are of the same kind. |
| 723 | virtual bool InstructionTypeEquals(HInstruction* other) const { return false; } |
| 724 | |
| 725 | // Returns whether any data encoded in the two instructions is equal. |
| 726 | // This method does not look at the inputs. Both instructions must be |
| 727 | // of the same type, otherwise the method has undefined behavior. |
| 728 | virtual bool InstructionDataEquals(HInstruction* other) const { return false; } |
| 729 | |
| 730 | // Returns whether two instructions are equal, that is: |
| 731 | // 1) They have the same type and contain the same data, |
| 732 | // 2) Their inputs are identical. |
| 733 | bool Equals(HInstruction* other) const; |
| 734 | |
Nicolas Geoffray | d31cf3d | 2014-09-08 17:30:24 +0100 | [diff] [blame] | 735 | virtual InstructionKind GetKind() const = 0; |
| 736 | |
| 737 | virtual size_t ComputeHashCode() const { |
| 738 | size_t result = GetKind(); |
| 739 | for (size_t i = 0, e = InputCount(); i < e; ++i) { |
| 740 | result = (result * 31) + InputAt(i)->GetId(); |
| 741 | } |
| 742 | return result; |
| 743 | } |
| 744 | |
| 745 | SideEffects GetSideEffects() const { return side_effects_; } |
| 746 | |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 747 | size_t GetLifetimePosition() const { return lifetime_position_; } |
| 748 | void SetLifetimePosition(size_t position) { lifetime_position_ = position; } |
| 749 | LiveInterval* GetLiveInterval() const { return live_interval_; } |
| 750 | void SetLiveInterval(LiveInterval* interval) { live_interval_ = interval; } |
| 751 | bool HasLiveInterval() const { return live_interval_ != nullptr; } |
| 752 | |
Nicolas Geoffray | 818f210 | 2014-02-18 16:43:35 +0000 | [diff] [blame] | 753 | private: |
| 754 | HInstruction* previous_; |
| 755 | HInstruction* next_; |
Nicolas Geoffray | d4dd255 | 2014-02-28 10:23:58 +0000 | [diff] [blame] | 756 | HBasicBlock* block_; |
Nicolas Geoffray | 818f210 | 2014-02-18 16:43:35 +0000 | [diff] [blame] | 757 | |
Nicolas Geoffray | 3ff386a | 2014-03-04 14:46:47 +0000 | [diff] [blame] | 758 | // An instruction gets an id when it is added to the graph. |
| 759 | // It reflects creation order. A negative id means the instruction |
Nicolas Geoffray | 3946844 | 2014-09-02 15:17:15 +0100 | [diff] [blame] | 760 | // has not been added to the graph. |
Nicolas Geoffray | 3ff386a | 2014-03-04 14:46:47 +0000 | [diff] [blame] | 761 | int id_; |
| 762 | |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 763 | // When doing liveness analysis, instructions that have uses get an SSA index. |
| 764 | int ssa_index_; |
| 765 | |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 766 | // List of instructions that have this instruction as input. |
| 767 | HUseListNode<HInstruction>* uses_; |
| 768 | |
| 769 | // List of environments that contain this instruction. |
| 770 | HUseListNode<HEnvironment>* env_uses_; |
| 771 | |
Nicolas Geoffray | 3946844 | 2014-09-02 15:17:15 +0100 | [diff] [blame] | 772 | // The environment associated with this instruction. Not null if the instruction |
| 773 | // might jump out of the method. |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 774 | HEnvironment* environment_; |
Nicolas Geoffray | 3ff386a | 2014-03-04 14:46:47 +0000 | [diff] [blame] | 775 | |
Nicolas Geoffray | bab4ed7 | 2014-03-11 17:53:17 +0000 | [diff] [blame] | 776 | // Set by the code generator. |
| 777 | LocationSummary* locations_; |
| 778 | |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 779 | // Set by the liveness analysis. |
| 780 | LiveInterval* live_interval_; |
| 781 | |
| 782 | // Set by the liveness analysis, this is the position in a linear |
| 783 | // order of blocks where this instruction's live interval start. |
| 784 | size_t lifetime_position_; |
| 785 | |
Nicolas Geoffray | 065bf77 | 2014-09-03 14:51:22 +0100 | [diff] [blame] | 786 | const SideEffects side_effects_; |
| 787 | |
Nicolas Geoffray | 818f210 | 2014-02-18 16:43:35 +0000 | [diff] [blame] | 788 | friend class HBasicBlock; |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 789 | friend class HInstructionList; |
Nicolas Geoffray | 818f210 | 2014-02-18 16:43:35 +0000 | [diff] [blame] | 790 | |
| 791 | DISALLOW_COPY_AND_ASSIGN(HInstruction); |
| 792 | }; |
| 793 | |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 794 | template<typename T> |
Nicolas Geoffray | 3ff386a | 2014-03-04 14:46:47 +0000 | [diff] [blame] | 795 | class HUseIterator : public ValueObject { |
| 796 | public: |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 797 | explicit HUseIterator(HUseListNode<T>* uses) : current_(uses) {} |
Nicolas Geoffray | 3ff386a | 2014-03-04 14:46:47 +0000 | [diff] [blame] | 798 | |
| 799 | bool Done() const { return current_ == nullptr; } |
| 800 | |
| 801 | void Advance() { |
| 802 | DCHECK(!Done()); |
Nicolas Geoffray | 787c307 | 2014-03-17 10:20:19 +0000 | [diff] [blame] | 803 | current_ = current_->GetTail(); |
Nicolas Geoffray | 3ff386a | 2014-03-04 14:46:47 +0000 | [diff] [blame] | 804 | } |
| 805 | |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 806 | HUseListNode<T>* Current() const { |
Nicolas Geoffray | 3ff386a | 2014-03-04 14:46:47 +0000 | [diff] [blame] | 807 | DCHECK(!Done()); |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 808 | return current_; |
Nicolas Geoffray | 3ff386a | 2014-03-04 14:46:47 +0000 | [diff] [blame] | 809 | } |
| 810 | |
| 811 | private: |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 812 | HUseListNode<T>* current_; |
Nicolas Geoffray | 3ff386a | 2014-03-04 14:46:47 +0000 | [diff] [blame] | 813 | |
| 814 | friend class HValue; |
| 815 | }; |
| 816 | |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 817 | // A HEnvironment object contains the values of virtual registers at a given location. |
| 818 | class HEnvironment : public ArenaObject { |
| 819 | public: |
| 820 | HEnvironment(ArenaAllocator* arena, size_t number_of_vregs) : vregs_(arena, number_of_vregs) { |
| 821 | vregs_.SetSize(number_of_vregs); |
| 822 | for (size_t i = 0; i < number_of_vregs; i++) { |
| 823 | vregs_.Put(i, nullptr); |
| 824 | } |
| 825 | } |
| 826 | |
| 827 | void Populate(const GrowableArray<HInstruction*>& env) { |
| 828 | for (size_t i = 0; i < env.Size(); i++) { |
| 829 | HInstruction* instruction = env.Get(i); |
| 830 | vregs_.Put(i, instruction); |
| 831 | if (instruction != nullptr) { |
| 832 | instruction->AddEnvUseAt(this, i); |
| 833 | } |
| 834 | } |
| 835 | } |
| 836 | |
| 837 | void SetRawEnvAt(size_t index, HInstruction* instruction) { |
| 838 | vregs_.Put(index, instruction); |
| 839 | } |
| 840 | |
Nicolas Geoffray | 3946844 | 2014-09-02 15:17:15 +0100 | [diff] [blame] | 841 | HInstruction* GetInstructionAt(size_t index) const { |
| 842 | return vregs_.Get(index); |
| 843 | } |
| 844 | |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 845 | GrowableArray<HInstruction*>* GetVRegs() { |
| 846 | return &vregs_; |
| 847 | } |
| 848 | |
Nicolas Geoffray | 3946844 | 2014-09-02 15:17:15 +0100 | [diff] [blame] | 849 | size_t Size() const { return vregs_.Size(); } |
| 850 | |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 851 | private: |
| 852 | GrowableArray<HInstruction*> vregs_; |
| 853 | |
| 854 | DISALLOW_COPY_AND_ASSIGN(HEnvironment); |
| 855 | }; |
| 856 | |
Nicolas Geoffray | 3ff386a | 2014-03-04 14:46:47 +0000 | [diff] [blame] | 857 | class HInputIterator : public ValueObject { |
| 858 | public: |
Dave Allison | 20dfc79 | 2014-06-16 20:44:29 -0700 | [diff] [blame] | 859 | explicit HInputIterator(HInstruction* instruction) : instruction_(instruction), index_(0) {} |
Nicolas Geoffray | 3ff386a | 2014-03-04 14:46:47 +0000 | [diff] [blame] | 860 | |
| 861 | bool Done() const { return index_ == instruction_->InputCount(); } |
| 862 | HInstruction* Current() const { return instruction_->InputAt(index_); } |
| 863 | void Advance() { index_++; } |
| 864 | |
| 865 | private: |
| 866 | HInstruction* instruction_; |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 867 | size_t index_; |
Nicolas Geoffray | 3ff386a | 2014-03-04 14:46:47 +0000 | [diff] [blame] | 868 | |
| 869 | DISALLOW_COPY_AND_ASSIGN(HInputIterator); |
| 870 | }; |
| 871 | |
Nicolas Geoffray | 818f210 | 2014-02-18 16:43:35 +0000 | [diff] [blame] | 872 | class HInstructionIterator : public ValueObject { |
| 873 | public: |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 874 | explicit HInstructionIterator(const HInstructionList& instructions) |
| 875 | : instruction_(instructions.first_instruction_) { |
Nicolas Geoffray | 787c307 | 2014-03-17 10:20:19 +0000 | [diff] [blame] | 876 | next_ = Done() ? nullptr : instruction_->GetNext(); |
Nicolas Geoffray | 818f210 | 2014-02-18 16:43:35 +0000 | [diff] [blame] | 877 | } |
| 878 | |
Nicolas Geoffray | 3ff386a | 2014-03-04 14:46:47 +0000 | [diff] [blame] | 879 | bool Done() const { return instruction_ == nullptr; } |
| 880 | HInstruction* Current() const { return instruction_; } |
| 881 | void Advance() { |
Nicolas Geoffray | 818f210 | 2014-02-18 16:43:35 +0000 | [diff] [blame] | 882 | instruction_ = next_; |
Nicolas Geoffray | 787c307 | 2014-03-17 10:20:19 +0000 | [diff] [blame] | 883 | next_ = Done() ? nullptr : instruction_->GetNext(); |
Nicolas Geoffray | 818f210 | 2014-02-18 16:43:35 +0000 | [diff] [blame] | 884 | } |
| 885 | |
| 886 | private: |
| 887 | HInstruction* instruction_; |
| 888 | HInstruction* next_; |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 889 | |
| 890 | DISALLOW_COPY_AND_ASSIGN(HInstructionIterator); |
Nicolas Geoffray | 818f210 | 2014-02-18 16:43:35 +0000 | [diff] [blame] | 891 | }; |
| 892 | |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 893 | class HBackwardInstructionIterator : public ValueObject { |
| 894 | public: |
| 895 | explicit HBackwardInstructionIterator(const HInstructionList& instructions) |
| 896 | : instruction_(instructions.last_instruction_) { |
| 897 | next_ = Done() ? nullptr : instruction_->GetPrevious(); |
| 898 | } |
| 899 | |
| 900 | bool Done() const { return instruction_ == nullptr; } |
| 901 | HInstruction* Current() const { return instruction_; } |
| 902 | void Advance() { |
| 903 | instruction_ = next_; |
| 904 | next_ = Done() ? nullptr : instruction_->GetPrevious(); |
| 905 | } |
| 906 | |
| 907 | private: |
| 908 | HInstruction* instruction_; |
| 909 | HInstruction* next_; |
Nicolas Geoffray | ddb311f | 2014-05-16 09:28:54 +0100 | [diff] [blame] | 910 | |
| 911 | DISALLOW_COPY_AND_ASSIGN(HBackwardInstructionIterator); |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 912 | }; |
| 913 | |
Nicolas Geoffray | 818f210 | 2014-02-18 16:43:35 +0000 | [diff] [blame] | 914 | // An embedded container with N elements of type T. Used (with partial |
| 915 | // specialization for N=0) because embedded arrays cannot have size 0. |
| 916 | template<typename T, intptr_t N> |
| 917 | class EmbeddedArray { |
| 918 | public: |
Dave Allison | 20dfc79 | 2014-06-16 20:44:29 -0700 | [diff] [blame] | 919 | EmbeddedArray() : elements_() {} |
Nicolas Geoffray | 818f210 | 2014-02-18 16:43:35 +0000 | [diff] [blame] | 920 | |
Nicolas Geoffray | 787c307 | 2014-03-17 10:20:19 +0000 | [diff] [blame] | 921 | intptr_t GetLength() const { return N; } |
Nicolas Geoffray | 818f210 | 2014-02-18 16:43:35 +0000 | [diff] [blame] | 922 | |
| 923 | const T& operator[](intptr_t i) const { |
Nicolas Geoffray | 787c307 | 2014-03-17 10:20:19 +0000 | [diff] [blame] | 924 | DCHECK_LT(i, GetLength()); |
Nicolas Geoffray | 818f210 | 2014-02-18 16:43:35 +0000 | [diff] [blame] | 925 | return elements_[i]; |
| 926 | } |
| 927 | |
| 928 | T& operator[](intptr_t i) { |
Nicolas Geoffray | 787c307 | 2014-03-17 10:20:19 +0000 | [diff] [blame] | 929 | DCHECK_LT(i, GetLength()); |
Nicolas Geoffray | 818f210 | 2014-02-18 16:43:35 +0000 | [diff] [blame] | 930 | return elements_[i]; |
| 931 | } |
| 932 | |
| 933 | const T& At(intptr_t i) const { |
| 934 | return (*this)[i]; |
| 935 | } |
| 936 | |
| 937 | void SetAt(intptr_t i, const T& val) { |
| 938 | (*this)[i] = val; |
| 939 | } |
| 940 | |
| 941 | private: |
| 942 | T elements_[N]; |
| 943 | }; |
| 944 | |
| 945 | template<typename T> |
| 946 | class EmbeddedArray<T, 0> { |
| 947 | public: |
| 948 | intptr_t length() const { return 0; } |
| 949 | const T& operator[](intptr_t i) const { |
| 950 | LOG(FATAL) << "Unreachable"; |
| 951 | static T sentinel = 0; |
| 952 | return sentinel; |
| 953 | } |
| 954 | T& operator[](intptr_t i) { |
| 955 | LOG(FATAL) << "Unreachable"; |
| 956 | static T sentinel = 0; |
| 957 | return sentinel; |
| 958 | } |
| 959 | }; |
| 960 | |
| 961 | template<intptr_t N> |
| 962 | class HTemplateInstruction: public HInstruction { |
| 963 | public: |
Nicolas Geoffray | 065bf77 | 2014-09-03 14:51:22 +0100 | [diff] [blame] | 964 | HTemplateInstruction<N>(SideEffects side_effects) |
| 965 | : HInstruction(side_effects), inputs_() {} |
Dave Allison | 20dfc79 | 2014-06-16 20:44:29 -0700 | [diff] [blame] | 966 | virtual ~HTemplateInstruction() {} |
Nicolas Geoffray | 818f210 | 2014-02-18 16:43:35 +0000 | [diff] [blame] | 967 | |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 968 | virtual size_t InputCount() const { return N; } |
| 969 | virtual HInstruction* InputAt(size_t i) const { return inputs_[i]; } |
Nicolas Geoffray | 818f210 | 2014-02-18 16:43:35 +0000 | [diff] [blame] | 970 | |
Nicolas Geoffray | 3ff386a | 2014-03-04 14:46:47 +0000 | [diff] [blame] | 971 | protected: |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 972 | virtual void SetRawInputAt(size_t i, HInstruction* instruction) { |
Nicolas Geoffray | 3ff386a | 2014-03-04 14:46:47 +0000 | [diff] [blame] | 973 | inputs_[i] = instruction; |
| 974 | } |
| 975 | |
Nicolas Geoffray | 818f210 | 2014-02-18 16:43:35 +0000 | [diff] [blame] | 976 | private: |
| 977 | EmbeddedArray<HInstruction*, N> inputs_; |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 978 | |
| 979 | friend class SsaBuilder; |
Nicolas Geoffray | 818f210 | 2014-02-18 16:43:35 +0000 | [diff] [blame] | 980 | }; |
| 981 | |
Dave Allison | 20dfc79 | 2014-06-16 20:44:29 -0700 | [diff] [blame] | 982 | template<intptr_t N> |
Nicolas Geoffray | 065bf77 | 2014-09-03 14:51:22 +0100 | [diff] [blame] | 983 | class HExpression : public HTemplateInstruction<N> { |
Dave Allison | 20dfc79 | 2014-06-16 20:44:29 -0700 | [diff] [blame] | 984 | public: |
Nicolas Geoffray | 065bf77 | 2014-09-03 14:51:22 +0100 | [diff] [blame] | 985 | HExpression<N>(Primitive::Type type, SideEffects side_effects) |
| 986 | : HTemplateInstruction<N>(side_effects), type_(type) {} |
Dave Allison | 20dfc79 | 2014-06-16 20:44:29 -0700 | [diff] [blame] | 987 | virtual ~HExpression() {} |
| 988 | |
| 989 | virtual Primitive::Type GetType() const { return type_; } |
| 990 | |
| 991 | private: |
| 992 | const Primitive::Type type_; |
| 993 | }; |
| 994 | |
Nicolas Geoffray | 818f210 | 2014-02-18 16:43:35 +0000 | [diff] [blame] | 995 | // Represents dex's RETURN_VOID opcode. A HReturnVoid is a control flow |
| 996 | // instruction that branches to the exit block. |
| 997 | class HReturnVoid : public HTemplateInstruction<0> { |
| 998 | public: |
Nicolas Geoffray | 065bf77 | 2014-09-03 14:51:22 +0100 | [diff] [blame] | 999 | HReturnVoid() : HTemplateInstruction(SideEffects::None()) {} |
Nicolas Geoffray | ec7e472 | 2014-06-06 11:24:33 +0100 | [diff] [blame] | 1000 | |
| 1001 | virtual bool IsControlFlow() const { return true; } |
Nicolas Geoffray | 818f210 | 2014-02-18 16:43:35 +0000 | [diff] [blame] | 1002 | |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 1003 | DECLARE_INSTRUCTION(ReturnVoid); |
Nicolas Geoffray | 818f210 | 2014-02-18 16:43:35 +0000 | [diff] [blame] | 1004 | |
| 1005 | private: |
| 1006 | DISALLOW_COPY_AND_ASSIGN(HReturnVoid); |
| 1007 | }; |
| 1008 | |
Nicolas Geoffray | bab4ed7 | 2014-03-11 17:53:17 +0000 | [diff] [blame] | 1009 | // Represents dex's RETURN opcodes. A HReturn is a control flow |
| 1010 | // instruction that branches to the exit block. |
| 1011 | class HReturn : public HTemplateInstruction<1> { |
| 1012 | public: |
Nicolas Geoffray | 065bf77 | 2014-09-03 14:51:22 +0100 | [diff] [blame] | 1013 | explicit HReturn(HInstruction* value) : HTemplateInstruction(SideEffects::None()) { |
Nicolas Geoffray | bab4ed7 | 2014-03-11 17:53:17 +0000 | [diff] [blame] | 1014 | SetRawInputAt(0, value); |
| 1015 | } |
| 1016 | |
Nicolas Geoffray | ec7e472 | 2014-06-06 11:24:33 +0100 | [diff] [blame] | 1017 | virtual bool IsControlFlow() const { return true; } |
| 1018 | |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 1019 | DECLARE_INSTRUCTION(Return); |
Nicolas Geoffray | bab4ed7 | 2014-03-11 17:53:17 +0000 | [diff] [blame] | 1020 | |
| 1021 | private: |
| 1022 | DISALLOW_COPY_AND_ASSIGN(HReturn); |
| 1023 | }; |
| 1024 | |
Nicolas Geoffray | 818f210 | 2014-02-18 16:43:35 +0000 | [diff] [blame] | 1025 | // The exit instruction is the only instruction of the exit block. |
| 1026 | // Instructions aborting the method (HTrow and HReturn) must branch to the |
| 1027 | // exit block. |
| 1028 | class HExit : public HTemplateInstruction<0> { |
| 1029 | public: |
Nicolas Geoffray | 065bf77 | 2014-09-03 14:51:22 +0100 | [diff] [blame] | 1030 | HExit() : HTemplateInstruction(SideEffects::None()) {} |
Nicolas Geoffray | ec7e472 | 2014-06-06 11:24:33 +0100 | [diff] [blame] | 1031 | |
| 1032 | virtual bool IsControlFlow() const { return true; } |
Nicolas Geoffray | 818f210 | 2014-02-18 16:43:35 +0000 | [diff] [blame] | 1033 | |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 1034 | DECLARE_INSTRUCTION(Exit); |
Nicolas Geoffray | 818f210 | 2014-02-18 16:43:35 +0000 | [diff] [blame] | 1035 | |
| 1036 | private: |
| 1037 | DISALLOW_COPY_AND_ASSIGN(HExit); |
| 1038 | }; |
| 1039 | |
| 1040 | // Jumps from one block to another. |
| 1041 | class HGoto : public HTemplateInstruction<0> { |
| 1042 | public: |
Nicolas Geoffray | 065bf77 | 2014-09-03 14:51:22 +0100 | [diff] [blame] | 1043 | HGoto() : HTemplateInstruction(SideEffects::None()) {} |
| 1044 | |
| 1045 | virtual bool IsControlFlow() const { return true; } |
Nicolas Geoffray | 818f210 | 2014-02-18 16:43:35 +0000 | [diff] [blame] | 1046 | |
Nicolas Geoffray | d4dd255 | 2014-02-28 10:23:58 +0000 | [diff] [blame] | 1047 | HBasicBlock* GetSuccessor() const { |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 1048 | return GetBlock()->GetSuccessors().Get(0); |
Nicolas Geoffray | d4dd255 | 2014-02-28 10:23:58 +0000 | [diff] [blame] | 1049 | } |
| 1050 | |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 1051 | DECLARE_INSTRUCTION(Goto); |
Nicolas Geoffray | 818f210 | 2014-02-18 16:43:35 +0000 | [diff] [blame] | 1052 | |
| 1053 | private: |
| 1054 | DISALLOW_COPY_AND_ASSIGN(HGoto); |
| 1055 | }; |
| 1056 | |
Dave Allison | 20dfc79 | 2014-06-16 20:44:29 -0700 | [diff] [blame] | 1057 | |
Nicolas Geoffray | be9a92a | 2014-02-25 14:22:56 +0000 | [diff] [blame] | 1058 | // Conditional branch. A block ending with an HIf instruction must have |
| 1059 | // two successors. |
Nicolas Geoffray | 3ff386a | 2014-03-04 14:46:47 +0000 | [diff] [blame] | 1060 | class HIf : public HTemplateInstruction<1> { |
Nicolas Geoffray | be9a92a | 2014-02-25 14:22:56 +0000 | [diff] [blame] | 1061 | public: |
Nicolas Geoffray | 065bf77 | 2014-09-03 14:51:22 +0100 | [diff] [blame] | 1062 | explicit HIf(HInstruction* input) : HTemplateInstruction(SideEffects::None()) { |
Nicolas Geoffray | 3ff386a | 2014-03-04 14:46:47 +0000 | [diff] [blame] | 1063 | SetRawInputAt(0, input); |
| 1064 | } |
Nicolas Geoffray | be9a92a | 2014-02-25 14:22:56 +0000 | [diff] [blame] | 1065 | |
Nicolas Geoffray | 065bf77 | 2014-09-03 14:51:22 +0100 | [diff] [blame] | 1066 | virtual bool IsControlFlow() const { return true; } |
| 1067 | |
Nicolas Geoffray | bab4ed7 | 2014-03-11 17:53:17 +0000 | [diff] [blame] | 1068 | HBasicBlock* IfTrueSuccessor() const { |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 1069 | return GetBlock()->GetSuccessors().Get(0); |
Nicolas Geoffray | bab4ed7 | 2014-03-11 17:53:17 +0000 | [diff] [blame] | 1070 | } |
| 1071 | |
| 1072 | HBasicBlock* IfFalseSuccessor() const { |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 1073 | return GetBlock()->GetSuccessors().Get(1); |
Nicolas Geoffray | bab4ed7 | 2014-03-11 17:53:17 +0000 | [diff] [blame] | 1074 | } |
| 1075 | |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 1076 | DECLARE_INSTRUCTION(If); |
Nicolas Geoffray | be9a92a | 2014-02-25 14:22:56 +0000 | [diff] [blame] | 1077 | |
Dave Allison | 20dfc79 | 2014-06-16 20:44:29 -0700 | [diff] [blame] | 1078 | virtual bool IsIfInstruction() const { return true; } |
| 1079 | |
Nicolas Geoffray | be9a92a | 2014-02-25 14:22:56 +0000 | [diff] [blame] | 1080 | private: |
| 1081 | DISALLOW_COPY_AND_ASSIGN(HIf); |
| 1082 | }; |
| 1083 | |
Dave Allison | 20dfc79 | 2014-06-16 20:44:29 -0700 | [diff] [blame] | 1084 | class HBinaryOperation : public HExpression<2> { |
Nicolas Geoffray | 3ff386a | 2014-03-04 14:46:47 +0000 | [diff] [blame] | 1085 | public: |
Nicolas Geoffray | d8ee737 | 2014-03-28 15:43:40 +0000 | [diff] [blame] | 1086 | HBinaryOperation(Primitive::Type result_type, |
| 1087 | HInstruction* left, |
Nicolas Geoffray | 065bf77 | 2014-09-03 14:51:22 +0100 | [diff] [blame] | 1088 | HInstruction* right) : HExpression(result_type, SideEffects::None()) { |
Nicolas Geoffray | d8ee737 | 2014-03-28 15:43:40 +0000 | [diff] [blame] | 1089 | SetRawInputAt(0, left); |
| 1090 | SetRawInputAt(1, right); |
Nicolas Geoffray | 3ff386a | 2014-03-04 14:46:47 +0000 | [diff] [blame] | 1091 | } |
| 1092 | |
Nicolas Geoffray | d8ee737 | 2014-03-28 15:43:40 +0000 | [diff] [blame] | 1093 | HInstruction* GetLeft() const { return InputAt(0); } |
| 1094 | HInstruction* GetRight() const { return InputAt(1); } |
Dave Allison | 20dfc79 | 2014-06-16 20:44:29 -0700 | [diff] [blame] | 1095 | Primitive::Type GetResultType() const { return GetType(); } |
Nicolas Geoffray | d8ee737 | 2014-03-28 15:43:40 +0000 | [diff] [blame] | 1096 | |
| 1097 | virtual bool IsCommutative() { return false; } |
| 1098 | |
Nicolas Geoffray | 065bf77 | 2014-09-03 14:51:22 +0100 | [diff] [blame] | 1099 | virtual bool CanBeMoved() const { return true; } |
| 1100 | virtual bool InstructionDataEquals(HInstruction* other) const { return true; } |
| 1101 | |
Roland Levillain | 556c3d1 | 2014-09-18 15:25:07 +0100 | [diff] [blame] | 1102 | // Try to statically evaluate `operation` and return an HConstant |
| 1103 | // containing the result of this evaluation. If `operation` cannot |
| 1104 | // be evaluated as a constant, return nullptr. |
| 1105 | HConstant* TryStaticEvaluation(ArenaAllocator* allocator) const; |
| 1106 | |
| 1107 | // Apply this operation to `x` and `y`. |
| 1108 | virtual int32_t Evaluate(int32_t x, int32_t y) const = 0; |
| 1109 | virtual int64_t Evaluate(int64_t x, int64_t y) const = 0; |
| 1110 | |
Roland Levillain | ccc07a9 | 2014-09-16 14:48:16 +0100 | [diff] [blame] | 1111 | DECLARE_INSTRUCTION(BinaryOperation); |
| 1112 | |
Nicolas Geoffray | d8ee737 | 2014-03-28 15:43:40 +0000 | [diff] [blame] | 1113 | private: |
Nicolas Geoffray | d8ee737 | 2014-03-28 15:43:40 +0000 | [diff] [blame] | 1114 | DISALLOW_COPY_AND_ASSIGN(HBinaryOperation); |
| 1115 | }; |
| 1116 | |
Dave Allison | 20dfc79 | 2014-06-16 20:44:29 -0700 | [diff] [blame] | 1117 | class HCondition : public HBinaryOperation { |
Nicolas Geoffray | d8ee737 | 2014-03-28 15:43:40 +0000 | [diff] [blame] | 1118 | public: |
Dave Allison | 20dfc79 | 2014-06-16 20:44:29 -0700 | [diff] [blame] | 1119 | HCondition(HInstruction* first, HInstruction* second) |
Nicolas Geoffray | d8ee737 | 2014-03-28 15:43:40 +0000 | [diff] [blame] | 1120 | : HBinaryOperation(Primitive::kPrimBoolean, first, second) {} |
| 1121 | |
| 1122 | virtual bool IsCommutative() { return true; } |
Nicolas Geoffray | 18efde5 | 2014-09-22 15:51:11 +0100 | [diff] [blame] | 1123 | |
| 1124 | // For register allocation purposes, returns whether this instruction needs to be |
| 1125 | // materialized (that is, not just be in the processor flags). |
Dave Allison | 20dfc79 | 2014-06-16 20:44:29 -0700 | [diff] [blame] | 1126 | bool NeedsMaterialization() const; |
Nicolas Geoffray | d8ee737 | 2014-03-28 15:43:40 +0000 | [diff] [blame] | 1127 | |
Nicolas Geoffray | 18efde5 | 2014-09-22 15:51:11 +0100 | [diff] [blame] | 1128 | // For code generation purposes, returns whether this instruction is just before |
| 1129 | // `if_`, and disregard moves in between. |
| 1130 | bool IsBeforeWhenDisregardMoves(HIf* if_) const; |
| 1131 | |
Dave Allison | 20dfc79 | 2014-06-16 20:44:29 -0700 | [diff] [blame] | 1132 | DECLARE_INSTRUCTION(Condition); |
| 1133 | |
| 1134 | virtual IfCondition GetCondition() const = 0; |
| 1135 | |
| 1136 | private: |
| 1137 | DISALLOW_COPY_AND_ASSIGN(HCondition); |
| 1138 | }; |
| 1139 | |
| 1140 | // Instruction to check if two inputs are equal to each other. |
| 1141 | class HEqual : public HCondition { |
| 1142 | public: |
| 1143 | HEqual(HInstruction* first, HInstruction* second) |
| 1144 | : HCondition(first, second) {} |
Nicolas Geoffray | 01bc96d | 2014-04-11 17:43:50 +0100 | [diff] [blame] | 1145 | |
Roland Levillain | 556c3d1 | 2014-09-18 15:25:07 +0100 | [diff] [blame] | 1146 | virtual int32_t Evaluate(int32_t x, int32_t y) const { return x == y; } |
| 1147 | virtual int64_t Evaluate(int64_t x, int64_t y) const { return x == y; } |
| 1148 | |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 1149 | DECLARE_INSTRUCTION(Equal); |
Nicolas Geoffray | 3ff386a | 2014-03-04 14:46:47 +0000 | [diff] [blame] | 1150 | |
Dave Allison | 20dfc79 | 2014-06-16 20:44:29 -0700 | [diff] [blame] | 1151 | virtual IfCondition GetCondition() const { |
| 1152 | return kCondEQ; |
| 1153 | } |
| 1154 | |
Nicolas Geoffray | 3ff386a | 2014-03-04 14:46:47 +0000 | [diff] [blame] | 1155 | private: |
| 1156 | DISALLOW_COPY_AND_ASSIGN(HEqual); |
| 1157 | }; |
| 1158 | |
Dave Allison | 20dfc79 | 2014-06-16 20:44:29 -0700 | [diff] [blame] | 1159 | class HNotEqual : public HCondition { |
| 1160 | public: |
| 1161 | HNotEqual(HInstruction* first, HInstruction* second) |
| 1162 | : HCondition(first, second) {} |
| 1163 | |
Roland Levillain | 556c3d1 | 2014-09-18 15:25:07 +0100 | [diff] [blame] | 1164 | virtual int32_t Evaluate(int32_t x, int32_t y) const { return x != y; } |
| 1165 | virtual int64_t Evaluate(int64_t x, int64_t y) const { return x != y; } |
| 1166 | |
Dave Allison | 20dfc79 | 2014-06-16 20:44:29 -0700 | [diff] [blame] | 1167 | DECLARE_INSTRUCTION(NotEqual); |
| 1168 | |
| 1169 | virtual IfCondition GetCondition() const { |
| 1170 | return kCondNE; |
| 1171 | } |
| 1172 | |
| 1173 | private: |
| 1174 | DISALLOW_COPY_AND_ASSIGN(HNotEqual); |
| 1175 | }; |
| 1176 | |
| 1177 | class HLessThan : public HCondition { |
| 1178 | public: |
| 1179 | HLessThan(HInstruction* first, HInstruction* second) |
| 1180 | : HCondition(first, second) {} |
| 1181 | |
Roland Levillain | 556c3d1 | 2014-09-18 15:25:07 +0100 | [diff] [blame] | 1182 | virtual int32_t Evaluate(int32_t x, int32_t y) const { return x < y; } |
| 1183 | virtual int64_t Evaluate(int64_t x, int64_t y) const { return x < y; } |
| 1184 | |
Dave Allison | 20dfc79 | 2014-06-16 20:44:29 -0700 | [diff] [blame] | 1185 | DECLARE_INSTRUCTION(LessThan); |
| 1186 | |
| 1187 | virtual IfCondition GetCondition() const { |
| 1188 | return kCondLT; |
| 1189 | } |
| 1190 | |
| 1191 | private: |
| 1192 | DISALLOW_COPY_AND_ASSIGN(HLessThan); |
| 1193 | }; |
| 1194 | |
| 1195 | class HLessThanOrEqual : public HCondition { |
| 1196 | public: |
| 1197 | HLessThanOrEqual(HInstruction* first, HInstruction* second) |
| 1198 | : HCondition(first, second) {} |
| 1199 | |
Roland Levillain | 556c3d1 | 2014-09-18 15:25:07 +0100 | [diff] [blame] | 1200 | virtual int32_t Evaluate(int32_t x, int32_t y) const { return x <= y; } |
| 1201 | virtual int64_t Evaluate(int64_t x, int64_t y) const { return x <= y; } |
| 1202 | |
Dave Allison | 20dfc79 | 2014-06-16 20:44:29 -0700 | [diff] [blame] | 1203 | DECLARE_INSTRUCTION(LessThanOrEqual); |
| 1204 | |
| 1205 | virtual IfCondition GetCondition() const { |
| 1206 | return kCondLE; |
| 1207 | } |
| 1208 | |
| 1209 | private: |
| 1210 | DISALLOW_COPY_AND_ASSIGN(HLessThanOrEqual); |
| 1211 | }; |
| 1212 | |
| 1213 | class HGreaterThan : public HCondition { |
| 1214 | public: |
| 1215 | HGreaterThan(HInstruction* first, HInstruction* second) |
| 1216 | : HCondition(first, second) {} |
| 1217 | |
Roland Levillain | 556c3d1 | 2014-09-18 15:25:07 +0100 | [diff] [blame] | 1218 | virtual int32_t Evaluate(int32_t x, int32_t y) const { return x > y; } |
| 1219 | virtual int64_t Evaluate(int64_t x, int64_t y) const { return x > y; } |
| 1220 | |
Dave Allison | 20dfc79 | 2014-06-16 20:44:29 -0700 | [diff] [blame] | 1221 | DECLARE_INSTRUCTION(GreaterThan); |
| 1222 | |
| 1223 | virtual IfCondition GetCondition() const { |
| 1224 | return kCondGT; |
| 1225 | } |
| 1226 | |
| 1227 | private: |
| 1228 | DISALLOW_COPY_AND_ASSIGN(HGreaterThan); |
| 1229 | }; |
| 1230 | |
| 1231 | class HGreaterThanOrEqual : public HCondition { |
| 1232 | public: |
| 1233 | HGreaterThanOrEqual(HInstruction* first, HInstruction* second) |
| 1234 | : HCondition(first, second) {} |
| 1235 | |
Roland Levillain | 556c3d1 | 2014-09-18 15:25:07 +0100 | [diff] [blame] | 1236 | virtual int32_t Evaluate(int32_t x, int32_t y) const { return x >= y; } |
| 1237 | virtual int64_t Evaluate(int64_t x, int64_t y) const { return x >= y; } |
| 1238 | |
Dave Allison | 20dfc79 | 2014-06-16 20:44:29 -0700 | [diff] [blame] | 1239 | DECLARE_INSTRUCTION(GreaterThanOrEqual); |
| 1240 | |
| 1241 | virtual IfCondition GetCondition() const { |
| 1242 | return kCondGE; |
| 1243 | } |
| 1244 | |
| 1245 | private: |
| 1246 | DISALLOW_COPY_AND_ASSIGN(HGreaterThanOrEqual); |
| 1247 | }; |
| 1248 | |
| 1249 | |
Nicolas Geoffray | 412f10c | 2014-06-19 10:00:34 +0100 | [diff] [blame] | 1250 | // Instruction to check how two inputs compare to each other. |
| 1251 | // Result is 0 if input0 == input1, 1 if input0 > input1, or -1 if input0 < input1. |
| 1252 | class HCompare : public HBinaryOperation { |
| 1253 | public: |
| 1254 | HCompare(Primitive::Type type, HInstruction* first, HInstruction* second) |
| 1255 | : HBinaryOperation(Primitive::kPrimInt, first, second) { |
| 1256 | DCHECK_EQ(type, first->GetType()); |
| 1257 | DCHECK_EQ(type, second->GetType()); |
| 1258 | } |
| 1259 | |
Roland Levillain | 556c3d1 | 2014-09-18 15:25:07 +0100 | [diff] [blame] | 1260 | virtual int32_t Evaluate(int32_t x, int32_t y) const { |
| 1261 | return |
| 1262 | x == y ? 0 : |
| 1263 | x > y ? 1 : |
| 1264 | -1; |
| 1265 | } |
| 1266 | virtual int64_t Evaluate(int64_t x, int64_t y) const { |
| 1267 | return |
| 1268 | x == y ? 0 : |
| 1269 | x > y ? 1 : |
| 1270 | -1; |
| 1271 | } |
| 1272 | |
Nicolas Geoffray | 412f10c | 2014-06-19 10:00:34 +0100 | [diff] [blame] | 1273 | DECLARE_INSTRUCTION(Compare); |
| 1274 | |
| 1275 | private: |
| 1276 | DISALLOW_COPY_AND_ASSIGN(HCompare); |
| 1277 | }; |
| 1278 | |
Nicolas Geoffray | 3ff386a | 2014-03-04 14:46:47 +0000 | [diff] [blame] | 1279 | // A local in the graph. Corresponds to a Dex register. |
| 1280 | class HLocal : public HTemplateInstruction<0> { |
| 1281 | public: |
Nicolas Geoffray | 065bf77 | 2014-09-03 14:51:22 +0100 | [diff] [blame] | 1282 | explicit HLocal(uint16_t reg_number) |
| 1283 | : HTemplateInstruction(SideEffects::None()), reg_number_(reg_number) {} |
Nicolas Geoffray | 3ff386a | 2014-03-04 14:46:47 +0000 | [diff] [blame] | 1284 | |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 1285 | DECLARE_INSTRUCTION(Local); |
Nicolas Geoffray | 3ff386a | 2014-03-04 14:46:47 +0000 | [diff] [blame] | 1286 | |
Nicolas Geoffray | 787c307 | 2014-03-17 10:20:19 +0000 | [diff] [blame] | 1287 | uint16_t GetRegNumber() const { return reg_number_; } |
Nicolas Geoffray | bab4ed7 | 2014-03-11 17:53:17 +0000 | [diff] [blame] | 1288 | |
Nicolas Geoffray | 3ff386a | 2014-03-04 14:46:47 +0000 | [diff] [blame] | 1289 | private: |
Nicolas Geoffray | bab4ed7 | 2014-03-11 17:53:17 +0000 | [diff] [blame] | 1290 | // The Dex register number. |
| 1291 | const uint16_t reg_number_; |
Nicolas Geoffray | 3ff386a | 2014-03-04 14:46:47 +0000 | [diff] [blame] | 1292 | |
| 1293 | DISALLOW_COPY_AND_ASSIGN(HLocal); |
| 1294 | }; |
| 1295 | |
| 1296 | // Load a given local. The local is an input of this instruction. |
Dave Allison | 20dfc79 | 2014-06-16 20:44:29 -0700 | [diff] [blame] | 1297 | class HLoadLocal : public HExpression<1> { |
Nicolas Geoffray | 3ff386a | 2014-03-04 14:46:47 +0000 | [diff] [blame] | 1298 | public: |
Roland Levillain | 5799fc0 | 2014-09-25 12:15:20 +0100 | [diff] [blame] | 1299 | HLoadLocal(HLocal* local, Primitive::Type type) |
Nicolas Geoffray | 065bf77 | 2014-09-03 14:51:22 +0100 | [diff] [blame] | 1300 | : HExpression(type, SideEffects::None()) { |
Nicolas Geoffray | 3ff386a | 2014-03-04 14:46:47 +0000 | [diff] [blame] | 1301 | SetRawInputAt(0, local); |
| 1302 | } |
| 1303 | |
Nicolas Geoffray | bab4ed7 | 2014-03-11 17:53:17 +0000 | [diff] [blame] | 1304 | HLocal* GetLocal() const { return reinterpret_cast<HLocal*>(InputAt(0)); } |
| 1305 | |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 1306 | DECLARE_INSTRUCTION(LoadLocal); |
Nicolas Geoffray | 3ff386a | 2014-03-04 14:46:47 +0000 | [diff] [blame] | 1307 | |
| 1308 | private: |
| 1309 | DISALLOW_COPY_AND_ASSIGN(HLoadLocal); |
| 1310 | }; |
| 1311 | |
| 1312 | // Store a value in a given local. This instruction has two inputs: the value |
| 1313 | // and the local. |
| 1314 | class HStoreLocal : public HTemplateInstruction<2> { |
| 1315 | public: |
Nicolas Geoffray | 065bf77 | 2014-09-03 14:51:22 +0100 | [diff] [blame] | 1316 | HStoreLocal(HLocal* local, HInstruction* value) : HTemplateInstruction(SideEffects::None()) { |
Nicolas Geoffray | 3ff386a | 2014-03-04 14:46:47 +0000 | [diff] [blame] | 1317 | SetRawInputAt(0, local); |
| 1318 | SetRawInputAt(1, value); |
| 1319 | } |
| 1320 | |
Nicolas Geoffray | bab4ed7 | 2014-03-11 17:53:17 +0000 | [diff] [blame] | 1321 | HLocal* GetLocal() const { return reinterpret_cast<HLocal*>(InputAt(0)); } |
| 1322 | |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 1323 | DECLARE_INSTRUCTION(StoreLocal); |
Nicolas Geoffray | 3ff386a | 2014-03-04 14:46:47 +0000 | [diff] [blame] | 1324 | |
| 1325 | private: |
| 1326 | DISALLOW_COPY_AND_ASSIGN(HStoreLocal); |
| 1327 | }; |
| 1328 | |
Nicolas Geoffray | 96f89a2 | 2014-07-11 10:57:49 +0100 | [diff] [blame] | 1329 | class HConstant : public HExpression<0> { |
| 1330 | public: |
Nicolas Geoffray | 065bf77 | 2014-09-03 14:51:22 +0100 | [diff] [blame] | 1331 | explicit HConstant(Primitive::Type type) : HExpression(type, SideEffects::None()) {} |
| 1332 | |
| 1333 | virtual bool CanBeMoved() const { return true; } |
Nicolas Geoffray | 96f89a2 | 2014-07-11 10:57:49 +0100 | [diff] [blame] | 1334 | |
| 1335 | DECLARE_INSTRUCTION(Constant); |
| 1336 | |
| 1337 | private: |
| 1338 | DISALLOW_COPY_AND_ASSIGN(HConstant); |
| 1339 | }; |
| 1340 | |
Nicolas Geoffray | 3ff386a | 2014-03-04 14:46:47 +0000 | [diff] [blame] | 1341 | // Constants of the type int. Those can be from Dex instructions, or |
| 1342 | // synthesized (for example with the if-eqz instruction). |
Nicolas Geoffray | 96f89a2 | 2014-07-11 10:57:49 +0100 | [diff] [blame] | 1343 | class HIntConstant : public HConstant { |
Nicolas Geoffray | 3ff386a | 2014-03-04 14:46:47 +0000 | [diff] [blame] | 1344 | public: |
Nicolas Geoffray | 96f89a2 | 2014-07-11 10:57:49 +0100 | [diff] [blame] | 1345 | explicit HIntConstant(int32_t value) : HConstant(Primitive::kPrimInt), value_(value) {} |
Nicolas Geoffray | 3ff386a | 2014-03-04 14:46:47 +0000 | [diff] [blame] | 1346 | |
Nicolas Geoffray | 787c307 | 2014-03-17 10:20:19 +0000 | [diff] [blame] | 1347 | int32_t GetValue() const { return value_; } |
Nicolas Geoffray | bab4ed7 | 2014-03-11 17:53:17 +0000 | [diff] [blame] | 1348 | |
Nicolas Geoffray | 065bf77 | 2014-09-03 14:51:22 +0100 | [diff] [blame] | 1349 | virtual bool InstructionDataEquals(HInstruction* other) const { |
| 1350 | return other->AsIntConstant()->value_ == value_; |
| 1351 | } |
| 1352 | |
Nicolas Geoffray | d31cf3d | 2014-09-08 17:30:24 +0100 | [diff] [blame] | 1353 | virtual size_t ComputeHashCode() const { return GetValue(); } |
| 1354 | |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 1355 | DECLARE_INSTRUCTION(IntConstant); |
Nicolas Geoffray | 3ff386a | 2014-03-04 14:46:47 +0000 | [diff] [blame] | 1356 | |
| 1357 | private: |
| 1358 | const int32_t value_; |
| 1359 | |
| 1360 | DISALLOW_COPY_AND_ASSIGN(HIntConstant); |
| 1361 | }; |
| 1362 | |
Nicolas Geoffray | 96f89a2 | 2014-07-11 10:57:49 +0100 | [diff] [blame] | 1363 | class HLongConstant : public HConstant { |
Nicolas Geoffray | 01bc96d | 2014-04-11 17:43:50 +0100 | [diff] [blame] | 1364 | public: |
Nicolas Geoffray | 96f89a2 | 2014-07-11 10:57:49 +0100 | [diff] [blame] | 1365 | explicit HLongConstant(int64_t value) : HConstant(Primitive::kPrimLong), value_(value) {} |
Nicolas Geoffray | 01bc96d | 2014-04-11 17:43:50 +0100 | [diff] [blame] | 1366 | |
| 1367 | int64_t GetValue() const { return value_; } |
| 1368 | |
Nicolas Geoffray | 065bf77 | 2014-09-03 14:51:22 +0100 | [diff] [blame] | 1369 | virtual bool InstructionDataEquals(HInstruction* other) const { |
| 1370 | return other->AsLongConstant()->value_ == value_; |
| 1371 | } |
| 1372 | |
Nicolas Geoffray | d31cf3d | 2014-09-08 17:30:24 +0100 | [diff] [blame] | 1373 | virtual size_t ComputeHashCode() const { return static_cast<size_t>(GetValue()); } |
| 1374 | |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 1375 | DECLARE_INSTRUCTION(LongConstant); |
Nicolas Geoffray | 01bc96d | 2014-04-11 17:43:50 +0100 | [diff] [blame] | 1376 | |
| 1377 | private: |
| 1378 | const int64_t value_; |
| 1379 | |
| 1380 | DISALLOW_COPY_AND_ASSIGN(HLongConstant); |
| 1381 | }; |
| 1382 | |
Nicolas Geoffray | 8ccc3f5 | 2014-03-19 10:34:11 +0000 | [diff] [blame] | 1383 | class HInvoke : public HInstruction { |
| 1384 | public: |
Nicolas Geoffray | 01bc96d | 2014-04-11 17:43:50 +0100 | [diff] [blame] | 1385 | HInvoke(ArenaAllocator* arena, |
| 1386 | uint32_t number_of_arguments, |
| 1387 | Primitive::Type return_type, |
| 1388 | uint32_t dex_pc) |
Nicolas Geoffray | 065bf77 | 2014-09-03 14:51:22 +0100 | [diff] [blame] | 1389 | : HInstruction(SideEffects::All()), |
| 1390 | inputs_(arena, number_of_arguments), |
Nicolas Geoffray | 01bc96d | 2014-04-11 17:43:50 +0100 | [diff] [blame] | 1391 | return_type_(return_type), |
Nicolas Geoffray | 8ccc3f5 | 2014-03-19 10:34:11 +0000 | [diff] [blame] | 1392 | dex_pc_(dex_pc) { |
| 1393 | inputs_.SetSize(number_of_arguments); |
| 1394 | } |
| 1395 | |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 1396 | virtual size_t InputCount() const { return inputs_.Size(); } |
| 1397 | virtual HInstruction* InputAt(size_t i) const { return inputs_.Get(i); } |
| 1398 | |
| 1399 | // Runtime needs to walk the stack, so Dex -> Dex calls need to |
| 1400 | // know their environment. |
| 1401 | virtual bool NeedsEnvironment() const { return true; } |
Nicolas Geoffray | 8ccc3f5 | 2014-03-19 10:34:11 +0000 | [diff] [blame] | 1402 | |
Nicolas Geoffray | 4a34a42 | 2014-04-03 10:38:37 +0100 | [diff] [blame] | 1403 | void SetArgumentAt(size_t index, HInstruction* argument) { |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 1404 | SetRawInputAt(index, argument); |
| 1405 | } |
| 1406 | |
| 1407 | virtual void SetRawInputAt(size_t index, HInstruction* input) { |
| 1408 | inputs_.Put(index, input); |
Nicolas Geoffray | 4a34a42 | 2014-04-03 10:38:37 +0100 | [diff] [blame] | 1409 | } |
| 1410 | |
Nicolas Geoffray | 01bc96d | 2014-04-11 17:43:50 +0100 | [diff] [blame] | 1411 | virtual Primitive::Type GetType() const { return return_type_; } |
| 1412 | |
Nicolas Geoffray | 2e7038a | 2014-04-03 18:49:58 +0100 | [diff] [blame] | 1413 | uint32_t GetDexPc() const { return dex_pc_; } |
Nicolas Geoffray | 8ccc3f5 | 2014-03-19 10:34:11 +0000 | [diff] [blame] | 1414 | |
| 1415 | protected: |
| 1416 | GrowableArray<HInstruction*> inputs_; |
Nicolas Geoffray | 01bc96d | 2014-04-11 17:43:50 +0100 | [diff] [blame] | 1417 | const Primitive::Type return_type_; |
Nicolas Geoffray | 2e7038a | 2014-04-03 18:49:58 +0100 | [diff] [blame] | 1418 | const uint32_t dex_pc_; |
Nicolas Geoffray | 8ccc3f5 | 2014-03-19 10:34:11 +0000 | [diff] [blame] | 1419 | |
| 1420 | private: |
| 1421 | DISALLOW_COPY_AND_ASSIGN(HInvoke); |
| 1422 | }; |
| 1423 | |
| 1424 | class HInvokeStatic : public HInvoke { |
| 1425 | public: |
Nicolas Geoffray | 4a34a42 | 2014-04-03 10:38:37 +0100 | [diff] [blame] | 1426 | HInvokeStatic(ArenaAllocator* arena, |
| 1427 | uint32_t number_of_arguments, |
Nicolas Geoffray | 01bc96d | 2014-04-11 17:43:50 +0100 | [diff] [blame] | 1428 | Primitive::Type return_type, |
Nicolas Geoffray | 2e7038a | 2014-04-03 18:49:58 +0100 | [diff] [blame] | 1429 | uint32_t dex_pc, |
| 1430 | uint32_t index_in_dex_cache) |
Nicolas Geoffray | 01bc96d | 2014-04-11 17:43:50 +0100 | [diff] [blame] | 1431 | : HInvoke(arena, number_of_arguments, return_type, dex_pc), |
| 1432 | index_in_dex_cache_(index_in_dex_cache) {} |
Nicolas Geoffray | 8ccc3f5 | 2014-03-19 10:34:11 +0000 | [diff] [blame] | 1433 | |
| 1434 | uint32_t GetIndexInDexCache() const { return index_in_dex_cache_; } |
| 1435 | |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 1436 | DECLARE_INSTRUCTION(InvokeStatic); |
Nicolas Geoffray | 8ccc3f5 | 2014-03-19 10:34:11 +0000 | [diff] [blame] | 1437 | |
| 1438 | private: |
Nicolas Geoffray | 4a34a42 | 2014-04-03 10:38:37 +0100 | [diff] [blame] | 1439 | const uint32_t index_in_dex_cache_; |
Nicolas Geoffray | 8ccc3f5 | 2014-03-19 10:34:11 +0000 | [diff] [blame] | 1440 | |
| 1441 | DISALLOW_COPY_AND_ASSIGN(HInvokeStatic); |
| 1442 | }; |
| 1443 | |
Nicolas Geoffray | e982f0b | 2014-08-13 02:11:24 +0100 | [diff] [blame] | 1444 | class HInvokeVirtual : public HInvoke { |
| 1445 | public: |
| 1446 | HInvokeVirtual(ArenaAllocator* arena, |
| 1447 | uint32_t number_of_arguments, |
| 1448 | Primitive::Type return_type, |
| 1449 | uint32_t dex_pc, |
| 1450 | uint32_t vtable_index) |
| 1451 | : HInvoke(arena, number_of_arguments, return_type, dex_pc), |
| 1452 | vtable_index_(vtable_index) {} |
| 1453 | |
| 1454 | uint32_t GetVTableIndex() const { return vtable_index_; } |
| 1455 | |
| 1456 | DECLARE_INSTRUCTION(InvokeVirtual); |
| 1457 | |
| 1458 | private: |
| 1459 | const uint32_t vtable_index_; |
| 1460 | |
| 1461 | DISALLOW_COPY_AND_ASSIGN(HInvokeVirtual); |
| 1462 | }; |
| 1463 | |
Dave Allison | 20dfc79 | 2014-06-16 20:44:29 -0700 | [diff] [blame] | 1464 | class HNewInstance : public HExpression<0> { |
Nicolas Geoffray | 2e7038a | 2014-04-03 18:49:58 +0100 | [diff] [blame] | 1465 | public: |
Nicolas Geoffray | 065bf77 | 2014-09-03 14:51:22 +0100 | [diff] [blame] | 1466 | HNewInstance(uint32_t dex_pc, uint16_t type_index) |
| 1467 | : HExpression(Primitive::kPrimNot, SideEffects::None()), |
| 1468 | dex_pc_(dex_pc), |
| 1469 | type_index_(type_index) {} |
Nicolas Geoffray | 2e7038a | 2014-04-03 18:49:58 +0100 | [diff] [blame] | 1470 | |
| 1471 | uint32_t GetDexPc() const { return dex_pc_; } |
| 1472 | uint16_t GetTypeIndex() const { return type_index_; } |
| 1473 | |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 1474 | // Calls runtime so needs an environment. |
| 1475 | virtual bool NeedsEnvironment() const { return true; } |
| 1476 | |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 1477 | DECLARE_INSTRUCTION(NewInstance); |
Nicolas Geoffray | 2e7038a | 2014-04-03 18:49:58 +0100 | [diff] [blame] | 1478 | |
| 1479 | private: |
| 1480 | const uint32_t dex_pc_; |
| 1481 | const uint16_t type_index_; |
| 1482 | |
| 1483 | DISALLOW_COPY_AND_ASSIGN(HNewInstance); |
| 1484 | }; |
| 1485 | |
Nicolas Geoffray | d8ee737 | 2014-03-28 15:43:40 +0000 | [diff] [blame] | 1486 | class HAdd : public HBinaryOperation { |
| 1487 | public: |
| 1488 | HAdd(Primitive::Type result_type, HInstruction* left, HInstruction* right) |
| 1489 | : HBinaryOperation(result_type, left, right) {} |
| 1490 | |
| 1491 | virtual bool IsCommutative() { return true; } |
| 1492 | |
Roland Levillain | 556c3d1 | 2014-09-18 15:25:07 +0100 | [diff] [blame] | 1493 | virtual int32_t Evaluate(int32_t x, int32_t y) const { return x + y; } |
| 1494 | virtual int64_t Evaluate(int64_t x, int64_t y) const { return x + y; } |
| 1495 | |
Nicolas Geoffray | d8ee737 | 2014-03-28 15:43:40 +0000 | [diff] [blame] | 1496 | DECLARE_INSTRUCTION(Add); |
| 1497 | |
| 1498 | private: |
| 1499 | DISALLOW_COPY_AND_ASSIGN(HAdd); |
| 1500 | }; |
| 1501 | |
Nicolas Geoffray | f583e59 | 2014-04-07 13:20:42 +0100 | [diff] [blame] | 1502 | class HSub : public HBinaryOperation { |
| 1503 | public: |
| 1504 | HSub(Primitive::Type result_type, HInstruction* left, HInstruction* right) |
| 1505 | : HBinaryOperation(result_type, left, right) {} |
| 1506 | |
| 1507 | virtual bool IsCommutative() { return false; } |
| 1508 | |
Roland Levillain | 556c3d1 | 2014-09-18 15:25:07 +0100 | [diff] [blame] | 1509 | virtual int32_t Evaluate(int32_t x, int32_t y) const { return x + y; } |
| 1510 | virtual int64_t Evaluate(int64_t x, int64_t y) const { return x + y; } |
| 1511 | |
Nicolas Geoffray | f583e59 | 2014-04-07 13:20:42 +0100 | [diff] [blame] | 1512 | DECLARE_INSTRUCTION(Sub); |
| 1513 | |
| 1514 | private: |
| 1515 | DISALLOW_COPY_AND_ASSIGN(HSub); |
| 1516 | }; |
| 1517 | |
| 1518 | // The value of a parameter in this method. Its location depends on |
| 1519 | // the calling convention. |
Dave Allison | 20dfc79 | 2014-06-16 20:44:29 -0700 | [diff] [blame] | 1520 | class HParameterValue : public HExpression<0> { |
Nicolas Geoffray | f583e59 | 2014-04-07 13:20:42 +0100 | [diff] [blame] | 1521 | public: |
Nicolas Geoffray | 01bc96d | 2014-04-11 17:43:50 +0100 | [diff] [blame] | 1522 | HParameterValue(uint8_t index, Primitive::Type parameter_type) |
Nicolas Geoffray | 065bf77 | 2014-09-03 14:51:22 +0100 | [diff] [blame] | 1523 | : HExpression(parameter_type, SideEffects::None()), index_(index) {} |
Nicolas Geoffray | f583e59 | 2014-04-07 13:20:42 +0100 | [diff] [blame] | 1524 | |
| 1525 | uint8_t GetIndex() const { return index_; } |
| 1526 | |
| 1527 | DECLARE_INSTRUCTION(ParameterValue); |
| 1528 | |
| 1529 | private: |
| 1530 | // The index of this parameter in the parameters list. Must be less |
| 1531 | // than HGraph::number_of_in_vregs_; |
| 1532 | const uint8_t index_; |
| 1533 | |
| 1534 | DISALLOW_COPY_AND_ASSIGN(HParameterValue); |
| 1535 | }; |
| 1536 | |
Dave Allison | 20dfc79 | 2014-06-16 20:44:29 -0700 | [diff] [blame] | 1537 | class HNot : public HExpression<1> { |
Nicolas Geoffray | b55f835 | 2014-04-07 15:26:35 +0100 | [diff] [blame] | 1538 | public: |
Nicolas Geoffray | 065bf77 | 2014-09-03 14:51:22 +0100 | [diff] [blame] | 1539 | explicit HNot(HInstruction* input) : HExpression(Primitive::kPrimBoolean, SideEffects::None()) { |
Nicolas Geoffray | b55f835 | 2014-04-07 15:26:35 +0100 | [diff] [blame] | 1540 | SetRawInputAt(0, input); |
| 1541 | } |
| 1542 | |
Nicolas Geoffray | 065bf77 | 2014-09-03 14:51:22 +0100 | [diff] [blame] | 1543 | virtual bool CanBeMoved() const { return true; } |
| 1544 | virtual bool InstructionDataEquals(HInstruction* other) const { return true; } |
| 1545 | |
Nicolas Geoffray | b55f835 | 2014-04-07 15:26:35 +0100 | [diff] [blame] | 1546 | DECLARE_INSTRUCTION(Not); |
| 1547 | |
| 1548 | private: |
| 1549 | DISALLOW_COPY_AND_ASSIGN(HNot); |
| 1550 | }; |
| 1551 | |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 1552 | class HPhi : public HInstruction { |
| 1553 | public: |
| 1554 | HPhi(ArenaAllocator* arena, uint32_t reg_number, size_t number_of_inputs, Primitive::Type type) |
Nicolas Geoffray | 065bf77 | 2014-09-03 14:51:22 +0100 | [diff] [blame] | 1555 | : HInstruction(SideEffects::None()), |
| 1556 | inputs_(arena, number_of_inputs), |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 1557 | reg_number_(reg_number), |
Nicolas Geoffray | 7dc206a | 2014-07-11 09:49:49 +0100 | [diff] [blame] | 1558 | type_(type), |
| 1559 | is_live_(false) { |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 1560 | inputs_.SetSize(number_of_inputs); |
| 1561 | } |
| 1562 | |
| 1563 | virtual size_t InputCount() const { return inputs_.Size(); } |
| 1564 | virtual HInstruction* InputAt(size_t i) const { return inputs_.Get(i); } |
| 1565 | |
| 1566 | virtual void SetRawInputAt(size_t index, HInstruction* input) { |
| 1567 | inputs_.Put(index, input); |
| 1568 | } |
| 1569 | |
| 1570 | void AddInput(HInstruction* input); |
| 1571 | |
| 1572 | virtual Primitive::Type GetType() const { return type_; } |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 1573 | void SetType(Primitive::Type type) { type_ = type; } |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 1574 | |
| 1575 | uint32_t GetRegNumber() const { return reg_number_; } |
| 1576 | |
Nicolas Geoffray | 7dc206a | 2014-07-11 09:49:49 +0100 | [diff] [blame] | 1577 | void SetDead() { is_live_ = false; } |
| 1578 | void SetLive() { is_live_ = true; } |
| 1579 | bool IsDead() const { return !is_live_; } |
| 1580 | bool IsLive() const { return is_live_; } |
| 1581 | |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 1582 | DECLARE_INSTRUCTION(Phi); |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 1583 | |
Nicolas Geoffray | 96f89a2 | 2014-07-11 10:57:49 +0100 | [diff] [blame] | 1584 | private: |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 1585 | GrowableArray<HInstruction*> inputs_; |
| 1586 | const uint32_t reg_number_; |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 1587 | Primitive::Type type_; |
Nicolas Geoffray | 7dc206a | 2014-07-11 09:49:49 +0100 | [diff] [blame] | 1588 | bool is_live_; |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 1589 | |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 1590 | DISALLOW_COPY_AND_ASSIGN(HPhi); |
| 1591 | }; |
| 1592 | |
Nicolas Geoffray | e503832 | 2014-07-04 09:41:32 +0100 | [diff] [blame] | 1593 | class HNullCheck : public HExpression<1> { |
| 1594 | public: |
| 1595 | HNullCheck(HInstruction* value, uint32_t dex_pc) |
Nicolas Geoffray | 065bf77 | 2014-09-03 14:51:22 +0100 | [diff] [blame] | 1596 | : HExpression(value->GetType(), SideEffects::None()), dex_pc_(dex_pc) { |
Nicolas Geoffray | e503832 | 2014-07-04 09:41:32 +0100 | [diff] [blame] | 1597 | SetRawInputAt(0, value); |
| 1598 | } |
| 1599 | |
Nicolas Geoffray | 065bf77 | 2014-09-03 14:51:22 +0100 | [diff] [blame] | 1600 | virtual bool CanBeMoved() const { return true; } |
| 1601 | virtual bool InstructionDataEquals(HInstruction* other) const { return true; } |
| 1602 | |
Nicolas Geoffray | e503832 | 2014-07-04 09:41:32 +0100 | [diff] [blame] | 1603 | virtual bool NeedsEnvironment() const { return true; } |
| 1604 | |
| 1605 | uint32_t GetDexPc() const { return dex_pc_; } |
| 1606 | |
| 1607 | DECLARE_INSTRUCTION(NullCheck); |
| 1608 | |
| 1609 | private: |
| 1610 | const uint32_t dex_pc_; |
| 1611 | |
| 1612 | DISALLOW_COPY_AND_ASSIGN(HNullCheck); |
| 1613 | }; |
| 1614 | |
| 1615 | class FieldInfo : public ValueObject { |
| 1616 | public: |
Roland Levillain | 5799fc0 | 2014-09-25 12:15:20 +0100 | [diff] [blame] | 1617 | FieldInfo(MemberOffset field_offset, Primitive::Type field_type) |
Nicolas Geoffray | 3946844 | 2014-09-02 15:17:15 +0100 | [diff] [blame] | 1618 | : field_offset_(field_offset), field_type_(field_type) {} |
Nicolas Geoffray | e503832 | 2014-07-04 09:41:32 +0100 | [diff] [blame] | 1619 | |
| 1620 | MemberOffset GetFieldOffset() const { return field_offset_; } |
Nicolas Geoffray | 3946844 | 2014-09-02 15:17:15 +0100 | [diff] [blame] | 1621 | Primitive::Type GetFieldType() const { return field_type_; } |
Nicolas Geoffray | e503832 | 2014-07-04 09:41:32 +0100 | [diff] [blame] | 1622 | |
| 1623 | private: |
| 1624 | const MemberOffset field_offset_; |
Nicolas Geoffray | 3946844 | 2014-09-02 15:17:15 +0100 | [diff] [blame] | 1625 | const Primitive::Type field_type_; |
Nicolas Geoffray | e503832 | 2014-07-04 09:41:32 +0100 | [diff] [blame] | 1626 | }; |
| 1627 | |
| 1628 | class HInstanceFieldGet : public HExpression<1> { |
| 1629 | public: |
| 1630 | HInstanceFieldGet(HInstruction* value, |
| 1631 | Primitive::Type field_type, |
| 1632 | MemberOffset field_offset) |
Nicolas Geoffray | 065bf77 | 2014-09-03 14:51:22 +0100 | [diff] [blame] | 1633 | : HExpression(field_type, SideEffects::DependsOnSomething()), |
| 1634 | field_info_(field_offset, field_type) { |
Nicolas Geoffray | e503832 | 2014-07-04 09:41:32 +0100 | [diff] [blame] | 1635 | SetRawInputAt(0, value); |
| 1636 | } |
| 1637 | |
Nicolas Geoffray | 065bf77 | 2014-09-03 14:51:22 +0100 | [diff] [blame] | 1638 | virtual bool CanBeMoved() const { return true; } |
| 1639 | virtual bool InstructionDataEquals(HInstruction* other) const { |
| 1640 | size_t other_offset = other->AsInstanceFieldGet()->GetFieldOffset().SizeValue(); |
| 1641 | return other_offset == GetFieldOffset().SizeValue(); |
| 1642 | } |
| 1643 | |
Nicolas Geoffray | d31cf3d | 2014-09-08 17:30:24 +0100 | [diff] [blame] | 1644 | virtual size_t ComputeHashCode() const { |
| 1645 | return (HInstruction::ComputeHashCode() << 7) | GetFieldOffset().SizeValue(); |
| 1646 | } |
| 1647 | |
Nicolas Geoffray | e503832 | 2014-07-04 09:41:32 +0100 | [diff] [blame] | 1648 | MemberOffset GetFieldOffset() const { return field_info_.GetFieldOffset(); } |
Nicolas Geoffray | 3946844 | 2014-09-02 15:17:15 +0100 | [diff] [blame] | 1649 | Primitive::Type GetFieldType() const { return field_info_.GetFieldType(); } |
Nicolas Geoffray | e503832 | 2014-07-04 09:41:32 +0100 | [diff] [blame] | 1650 | |
| 1651 | DECLARE_INSTRUCTION(InstanceFieldGet); |
| 1652 | |
| 1653 | private: |
| 1654 | const FieldInfo field_info_; |
| 1655 | |
| 1656 | DISALLOW_COPY_AND_ASSIGN(HInstanceFieldGet); |
| 1657 | }; |
| 1658 | |
| 1659 | class HInstanceFieldSet : public HTemplateInstruction<2> { |
| 1660 | public: |
| 1661 | HInstanceFieldSet(HInstruction* object, |
| 1662 | HInstruction* value, |
Nicolas Geoffray | 3946844 | 2014-09-02 15:17:15 +0100 | [diff] [blame] | 1663 | Primitive::Type field_type, |
Nicolas Geoffray | e503832 | 2014-07-04 09:41:32 +0100 | [diff] [blame] | 1664 | MemberOffset field_offset) |
Nicolas Geoffray | 065bf77 | 2014-09-03 14:51:22 +0100 | [diff] [blame] | 1665 | : HTemplateInstruction(SideEffects::ChangesSomething()), |
| 1666 | field_info_(field_offset, field_type) { |
Nicolas Geoffray | e503832 | 2014-07-04 09:41:32 +0100 | [diff] [blame] | 1667 | SetRawInputAt(0, object); |
| 1668 | SetRawInputAt(1, value); |
| 1669 | } |
| 1670 | |
| 1671 | MemberOffset GetFieldOffset() const { return field_info_.GetFieldOffset(); } |
Nicolas Geoffray | 3946844 | 2014-09-02 15:17:15 +0100 | [diff] [blame] | 1672 | Primitive::Type GetFieldType() const { return field_info_.GetFieldType(); } |
Nicolas Geoffray | e503832 | 2014-07-04 09:41:32 +0100 | [diff] [blame] | 1673 | |
| 1674 | DECLARE_INSTRUCTION(InstanceFieldSet); |
| 1675 | |
| 1676 | private: |
| 1677 | const FieldInfo field_info_; |
| 1678 | |
| 1679 | DISALLOW_COPY_AND_ASSIGN(HInstanceFieldSet); |
| 1680 | }; |
| 1681 | |
Nicolas Geoffray | 3c7bb98 | 2014-07-23 16:04:16 +0100 | [diff] [blame] | 1682 | class HArrayGet : public HExpression<2> { |
| 1683 | public: |
| 1684 | HArrayGet(HInstruction* array, HInstruction* index, Primitive::Type type) |
Nicolas Geoffray | 065bf77 | 2014-09-03 14:51:22 +0100 | [diff] [blame] | 1685 | : HExpression(type, SideEffects::DependsOnSomething()) { |
Nicolas Geoffray | 3c7bb98 | 2014-07-23 16:04:16 +0100 | [diff] [blame] | 1686 | SetRawInputAt(0, array); |
| 1687 | SetRawInputAt(1, index); |
| 1688 | } |
| 1689 | |
Nicolas Geoffray | 065bf77 | 2014-09-03 14:51:22 +0100 | [diff] [blame] | 1690 | virtual bool CanBeMoved() const { return true; } |
| 1691 | virtual bool InstructionDataEquals(HInstruction* other) const { return true; } |
| 1692 | |
Nicolas Geoffray | 3c7bb98 | 2014-07-23 16:04:16 +0100 | [diff] [blame] | 1693 | DECLARE_INSTRUCTION(ArrayGet); |
| 1694 | |
| 1695 | private: |
| 1696 | DISALLOW_COPY_AND_ASSIGN(HArrayGet); |
| 1697 | }; |
| 1698 | |
| 1699 | class HArraySet : public HTemplateInstruction<3> { |
| 1700 | public: |
| 1701 | HArraySet(HInstruction* array, |
| 1702 | HInstruction* index, |
| 1703 | HInstruction* value, |
Nicolas Geoffray | 3946844 | 2014-09-02 15:17:15 +0100 | [diff] [blame] | 1704 | Primitive::Type component_type, |
Nicolas Geoffray | 065bf77 | 2014-09-03 14:51:22 +0100 | [diff] [blame] | 1705 | uint32_t dex_pc) |
| 1706 | : HTemplateInstruction(SideEffects::ChangesSomething()), |
| 1707 | dex_pc_(dex_pc), |
| 1708 | component_type_(component_type) { |
Nicolas Geoffray | 3c7bb98 | 2014-07-23 16:04:16 +0100 | [diff] [blame] | 1709 | SetRawInputAt(0, array); |
| 1710 | SetRawInputAt(1, index); |
| 1711 | SetRawInputAt(2, value); |
| 1712 | } |
| 1713 | |
| 1714 | virtual bool NeedsEnvironment() const { |
| 1715 | // We currently always call a runtime method to catch array store |
| 1716 | // exceptions. |
| 1717 | return InputAt(2)->GetType() == Primitive::kPrimNot; |
| 1718 | } |
| 1719 | |
| 1720 | uint32_t GetDexPc() const { return dex_pc_; } |
| 1721 | |
Nicolas Geoffray | 3946844 | 2014-09-02 15:17:15 +0100 | [diff] [blame] | 1722 | Primitive::Type GetComponentType() const { return component_type_; } |
| 1723 | |
Nicolas Geoffray | 3c7bb98 | 2014-07-23 16:04:16 +0100 | [diff] [blame] | 1724 | DECLARE_INSTRUCTION(ArraySet); |
| 1725 | |
| 1726 | private: |
| 1727 | const uint32_t dex_pc_; |
Nicolas Geoffray | 3946844 | 2014-09-02 15:17:15 +0100 | [diff] [blame] | 1728 | const Primitive::Type component_type_; |
Nicolas Geoffray | 3c7bb98 | 2014-07-23 16:04:16 +0100 | [diff] [blame] | 1729 | |
| 1730 | DISALLOW_COPY_AND_ASSIGN(HArraySet); |
| 1731 | }; |
| 1732 | |
| 1733 | class HArrayLength : public HExpression<1> { |
| 1734 | public: |
Nicolas Geoffray | 065bf77 | 2014-09-03 14:51:22 +0100 | [diff] [blame] | 1735 | explicit HArrayLength(HInstruction* array) |
| 1736 | : HExpression(Primitive::kPrimInt, SideEffects::None()) { |
| 1737 | // Note that arrays do not change length, so the instruction does not |
| 1738 | // depend on any write. |
Nicolas Geoffray | 3c7bb98 | 2014-07-23 16:04:16 +0100 | [diff] [blame] | 1739 | SetRawInputAt(0, array); |
| 1740 | } |
| 1741 | |
Nicolas Geoffray | 065bf77 | 2014-09-03 14:51:22 +0100 | [diff] [blame] | 1742 | virtual bool CanBeMoved() const { return true; } |
| 1743 | virtual bool InstructionDataEquals(HInstruction* other) const { return true; } |
| 1744 | |
Nicolas Geoffray | 3c7bb98 | 2014-07-23 16:04:16 +0100 | [diff] [blame] | 1745 | DECLARE_INSTRUCTION(ArrayLength); |
| 1746 | |
| 1747 | private: |
| 1748 | DISALLOW_COPY_AND_ASSIGN(HArrayLength); |
| 1749 | }; |
| 1750 | |
| 1751 | class HBoundsCheck : public HExpression<2> { |
| 1752 | public: |
| 1753 | HBoundsCheck(HInstruction* index, HInstruction* length, uint32_t dex_pc) |
Nicolas Geoffray | 065bf77 | 2014-09-03 14:51:22 +0100 | [diff] [blame] | 1754 | : HExpression(index->GetType(), SideEffects::None()), dex_pc_(dex_pc) { |
Nicolas Geoffray | 3c7bb98 | 2014-07-23 16:04:16 +0100 | [diff] [blame] | 1755 | DCHECK(index->GetType() == Primitive::kPrimInt); |
| 1756 | SetRawInputAt(0, index); |
| 1757 | SetRawInputAt(1, length); |
| 1758 | } |
| 1759 | |
Nicolas Geoffray | 065bf77 | 2014-09-03 14:51:22 +0100 | [diff] [blame] | 1760 | virtual bool CanBeMoved() const { return true; } |
| 1761 | virtual bool InstructionDataEquals(HInstruction* other) const { return true; } |
| 1762 | |
Nicolas Geoffray | 3c7bb98 | 2014-07-23 16:04:16 +0100 | [diff] [blame] | 1763 | virtual bool NeedsEnvironment() const { return true; } |
| 1764 | |
| 1765 | uint32_t GetDexPc() const { return dex_pc_; } |
| 1766 | |
| 1767 | DECLARE_INSTRUCTION(BoundsCheck); |
| 1768 | |
| 1769 | private: |
| 1770 | const uint32_t dex_pc_; |
| 1771 | |
| 1772 | DISALLOW_COPY_AND_ASSIGN(HBoundsCheck); |
| 1773 | }; |
| 1774 | |
Nicolas Geoffray | e503832 | 2014-07-04 09:41:32 +0100 | [diff] [blame] | 1775 | /** |
| 1776 | * Some DEX instructions are folded into multiple HInstructions that need |
| 1777 | * to stay live until the last HInstruction. This class |
| 1778 | * is used as a marker for the baseline compiler to ensure its preceding |
| 1779 | * HInstruction stays live. `index` is the temporary number that is used |
| 1780 | * for knowing the stack offset where to store the instruction. |
| 1781 | */ |
| 1782 | class HTemporary : public HTemplateInstruction<0> { |
| 1783 | public: |
Nicolas Geoffray | 065bf77 | 2014-09-03 14:51:22 +0100 | [diff] [blame] | 1784 | explicit HTemporary(size_t index) : HTemplateInstruction(SideEffects::None()), index_(index) {} |
Nicolas Geoffray | e503832 | 2014-07-04 09:41:32 +0100 | [diff] [blame] | 1785 | |
| 1786 | size_t GetIndex() const { return index_; } |
| 1787 | |
| 1788 | DECLARE_INSTRUCTION(Temporary); |
| 1789 | |
| 1790 | private: |
| 1791 | const size_t index_; |
| 1792 | |
| 1793 | DISALLOW_COPY_AND_ASSIGN(HTemporary); |
| 1794 | }; |
| 1795 | |
Nicolas Geoffray | fbc695f | 2014-09-15 15:33:30 +0000 | [diff] [blame] | 1796 | class HSuspendCheck : public HTemplateInstruction<0> { |
| 1797 | public: |
| 1798 | explicit HSuspendCheck(uint32_t dex_pc) |
Nicolas Geoffray | 9ebc72c | 2014-09-25 16:33:42 +0100 | [diff] [blame^] | 1799 | : HTemplateInstruction(SideEffects::None()), dex_pc_(dex_pc) {} |
Nicolas Geoffray | fbc695f | 2014-09-15 15:33:30 +0000 | [diff] [blame] | 1800 | |
| 1801 | virtual bool NeedsEnvironment() const { |
| 1802 | return true; |
| 1803 | } |
| 1804 | |
| 1805 | uint32_t GetDexPc() const { return dex_pc_; } |
| 1806 | |
| 1807 | DECLARE_INSTRUCTION(SuspendCheck); |
| 1808 | |
| 1809 | private: |
| 1810 | const uint32_t dex_pc_; |
| 1811 | |
| 1812 | DISALLOW_COPY_AND_ASSIGN(HSuspendCheck); |
| 1813 | }; |
| 1814 | |
Nicolas Geoffray | 4e3d23a | 2014-05-22 18:32:45 +0100 | [diff] [blame] | 1815 | class MoveOperands : public ArenaObject { |
| 1816 | public: |
| 1817 | MoveOperands(Location source, Location destination) |
| 1818 | : source_(source), destination_(destination) {} |
| 1819 | |
| 1820 | Location GetSource() const { return source_; } |
| 1821 | Location GetDestination() const { return destination_; } |
| 1822 | |
| 1823 | void SetSource(Location value) { source_ = value; } |
| 1824 | void SetDestination(Location value) { destination_ = value; } |
| 1825 | |
| 1826 | // The parallel move resolver marks moves as "in-progress" by clearing the |
| 1827 | // destination (but not the source). |
| 1828 | Location MarkPending() { |
| 1829 | DCHECK(!IsPending()); |
| 1830 | Location dest = destination_; |
| 1831 | destination_ = Location::NoLocation(); |
| 1832 | return dest; |
| 1833 | } |
| 1834 | |
| 1835 | void ClearPending(Location dest) { |
| 1836 | DCHECK(IsPending()); |
| 1837 | destination_ = dest; |
| 1838 | } |
| 1839 | |
| 1840 | bool IsPending() const { |
| 1841 | DCHECK(!source_.IsInvalid() || destination_.IsInvalid()); |
| 1842 | return destination_.IsInvalid() && !source_.IsInvalid(); |
| 1843 | } |
| 1844 | |
| 1845 | // True if this blocks a move from the given location. |
| 1846 | bool Blocks(Location loc) const { |
| 1847 | return !IsEliminated() && source_.Equals(loc); |
| 1848 | } |
| 1849 | |
| 1850 | // A move is redundant if it's been eliminated, if its source and |
| 1851 | // destination are the same, or if its destination is unneeded. |
| 1852 | bool IsRedundant() const { |
| 1853 | return IsEliminated() || destination_.IsInvalid() || source_.Equals(destination_); |
| 1854 | } |
| 1855 | |
| 1856 | // We clear both operands to indicate move that's been eliminated. |
| 1857 | void Eliminate() { |
| 1858 | source_ = destination_ = Location::NoLocation(); |
| 1859 | } |
| 1860 | |
| 1861 | bool IsEliminated() const { |
| 1862 | DCHECK(!source_.IsInvalid() || destination_.IsInvalid()); |
| 1863 | return source_.IsInvalid(); |
| 1864 | } |
| 1865 | |
| 1866 | private: |
| 1867 | Location source_; |
| 1868 | Location destination_; |
| 1869 | |
| 1870 | DISALLOW_COPY_AND_ASSIGN(MoveOperands); |
| 1871 | }; |
| 1872 | |
| 1873 | static constexpr size_t kDefaultNumberOfMoves = 4; |
| 1874 | |
| 1875 | class HParallelMove : public HTemplateInstruction<0> { |
| 1876 | public: |
Nicolas Geoffray | 065bf77 | 2014-09-03 14:51:22 +0100 | [diff] [blame] | 1877 | explicit HParallelMove(ArenaAllocator* arena) |
| 1878 | : HTemplateInstruction(SideEffects::None()), moves_(arena, kDefaultNumberOfMoves) {} |
Nicolas Geoffray | 4e3d23a | 2014-05-22 18:32:45 +0100 | [diff] [blame] | 1879 | |
| 1880 | void AddMove(MoveOperands* move) { |
| 1881 | moves_.Add(move); |
| 1882 | } |
| 1883 | |
| 1884 | MoveOperands* MoveOperandsAt(size_t index) const { |
| 1885 | return moves_.Get(index); |
| 1886 | } |
| 1887 | |
| 1888 | size_t NumMoves() const { return moves_.Size(); } |
| 1889 | |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 1890 | DECLARE_INSTRUCTION(ParallelMove); |
Nicolas Geoffray | 4e3d23a | 2014-05-22 18:32:45 +0100 | [diff] [blame] | 1891 | |
| 1892 | private: |
| 1893 | GrowableArray<MoveOperands*> moves_; |
| 1894 | |
| 1895 | DISALLOW_COPY_AND_ASSIGN(HParallelMove); |
| 1896 | }; |
| 1897 | |
Nicolas Geoffray | 818f210 | 2014-02-18 16:43:35 +0000 | [diff] [blame] | 1898 | class HGraphVisitor : public ValueObject { |
| 1899 | public: |
Dave Allison | 20dfc79 | 2014-06-16 20:44:29 -0700 | [diff] [blame] | 1900 | explicit HGraphVisitor(HGraph* graph) : graph_(graph) {} |
| 1901 | virtual ~HGraphVisitor() {} |
Nicolas Geoffray | 818f210 | 2014-02-18 16:43:35 +0000 | [diff] [blame] | 1902 | |
Dave Allison | 20dfc79 | 2014-06-16 20:44:29 -0700 | [diff] [blame] | 1903 | virtual void VisitInstruction(HInstruction* instruction) {} |
Nicolas Geoffray | 818f210 | 2014-02-18 16:43:35 +0000 | [diff] [blame] | 1904 | virtual void VisitBasicBlock(HBasicBlock* block); |
| 1905 | |
| 1906 | void VisitInsertionOrder(); |
| 1907 | |
Nicolas Geoffray | 787c307 | 2014-03-17 10:20:19 +0000 | [diff] [blame] | 1908 | HGraph* GetGraph() const { return graph_; } |
Nicolas Geoffray | d4dd255 | 2014-02-28 10:23:58 +0000 | [diff] [blame] | 1909 | |
Nicolas Geoffray | 818f210 | 2014-02-18 16:43:35 +0000 | [diff] [blame] | 1910 | // Visit functions for instruction classes. |
| 1911 | #define DECLARE_VISIT_INSTRUCTION(name) \ |
| 1912 | virtual void Visit##name(H##name* instr) { VisitInstruction(instr); } |
| 1913 | |
| 1914 | FOR_EACH_INSTRUCTION(DECLARE_VISIT_INSTRUCTION) |
| 1915 | |
| 1916 | #undef DECLARE_VISIT_INSTRUCTION |
| 1917 | |
| 1918 | private: |
| 1919 | HGraph* graph_; |
| 1920 | |
| 1921 | DISALLOW_COPY_AND_ASSIGN(HGraphVisitor); |
| 1922 | }; |
| 1923 | |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 1924 | class HInsertionOrderIterator : public ValueObject { |
| 1925 | public: |
| 1926 | explicit HInsertionOrderIterator(const HGraph& graph) : graph_(graph), index_(0) {} |
| 1927 | |
| 1928 | bool Done() const { return index_ == graph_.GetBlocks().Size(); } |
| 1929 | HBasicBlock* Current() const { return graph_.GetBlocks().Get(index_); } |
| 1930 | void Advance() { ++index_; } |
| 1931 | |
| 1932 | private: |
| 1933 | const HGraph& graph_; |
| 1934 | size_t index_; |
| 1935 | |
| 1936 | DISALLOW_COPY_AND_ASSIGN(HInsertionOrderIterator); |
| 1937 | }; |
| 1938 | |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 1939 | class HReversePostOrderIterator : public ValueObject { |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 1940 | public: |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 1941 | explicit HReversePostOrderIterator(const HGraph& graph) : graph_(graph), index_(0) {} |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 1942 | |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 1943 | bool Done() const { return index_ == graph_.GetReversePostOrder().Size(); } |
| 1944 | HBasicBlock* Current() const { return graph_.GetReversePostOrder().Get(index_); } |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 1945 | void Advance() { ++index_; } |
| 1946 | |
| 1947 | private: |
| 1948 | const HGraph& graph_; |
| 1949 | size_t index_; |
| 1950 | |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 1951 | DISALLOW_COPY_AND_ASSIGN(HReversePostOrderIterator); |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 1952 | }; |
| 1953 | |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 1954 | class HPostOrderIterator : public ValueObject { |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 1955 | public: |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 1956 | explicit HPostOrderIterator(const HGraph& graph) |
| 1957 | : graph_(graph), index_(graph_.GetReversePostOrder().Size()) {} |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 1958 | |
| 1959 | bool Done() const { return index_ == 0; } |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 1960 | HBasicBlock* Current() const { return graph_.GetReversePostOrder().Get(index_ - 1); } |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 1961 | void Advance() { --index_; } |
| 1962 | |
| 1963 | private: |
| 1964 | const HGraph& graph_; |
| 1965 | size_t index_; |
| 1966 | |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 1967 | DISALLOW_COPY_AND_ASSIGN(HPostOrderIterator); |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 1968 | }; |
| 1969 | |
Nicolas Geoffray | 818f210 | 2014-02-18 16:43:35 +0000 | [diff] [blame] | 1970 | } // namespace art |
| 1971 | |
| 1972 | #endif // ART_COMPILER_OPTIMIZING_NODES_H_ |