blob: 012858920fb77f0b9bed2eca95cf5e664ad1f8f5 [file] [log] [blame]
Nicolas Geoffray818f2102014-02-18 16:43:35 +00001/*
2 * Copyright (C) 2014 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17#include "nodes.h"
Calin Juravle77520bc2015-01-12 18:45:46 +000018
Mark Mendelle82549b2015-05-06 10:55:34 -040019#include "code_generator.h"
Nicolas Geoffrayc32e7702014-04-24 12:43:16 +010020#include "ssa_builder.h"
David Brazdila4b8c212015-05-07 09:59:30 +010021#include "base/bit_vector-inl.h"
Vladimir Marko80afd022015-05-19 18:08:00 +010022#include "base/bit_utils.h"
David Brazdilbaf89b82015-09-15 11:36:54 +010023#include "mirror/class-inl.h"
Nicolas Geoffray818f2102014-02-18 16:43:35 +000024#include "utils/growable_array.h"
Calin Juravleacf735c2015-02-12 15:25:22 +000025#include "scoped_thread_state_change.h"
Nicolas Geoffray818f2102014-02-18 16:43:35 +000026
27namespace art {
28
29void HGraph::AddBlock(HBasicBlock* block) {
Vladimir Markofa6b93c2015-09-15 10:15:55 +010030 block->SetBlockId(blocks_.size());
31 blocks_.push_back(block);
Nicolas Geoffray818f2102014-02-18 16:43:35 +000032}
33
Nicolas Geoffray804d0932014-05-02 08:46:00 +010034void HGraph::FindBackEdges(ArenaBitVector* visited) {
Vladimir Markofa6b93c2015-09-15 10:15:55 +010035 ArenaBitVector visiting(arena_, blocks_.size(), false);
Nicolas Geoffrayd4dd2552014-02-28 10:23:58 +000036 VisitBlockForBackEdges(entry_block_, visited, &visiting);
Nicolas Geoffraybe9a92a2014-02-25 14:22:56 +000037}
38
Roland Levillainfc600dc2014-12-02 17:16:31 +000039static void RemoveAsUser(HInstruction* instruction) {
40 for (size_t i = 0; i < instruction->InputCount(); i++) {
David Brazdil1abb4192015-02-17 18:33:36 +000041 instruction->RemoveAsUserOfInput(i);
Roland Levillainfc600dc2014-12-02 17:16:31 +000042 }
43
Nicolas Geoffray0a23d742015-05-07 11:57:35 +010044 for (HEnvironment* environment = instruction->GetEnvironment();
45 environment != nullptr;
46 environment = environment->GetParent()) {
Roland Levillainfc600dc2014-12-02 17:16:31 +000047 for (size_t i = 0, e = environment->Size(); i < e; ++i) {
David Brazdil1abb4192015-02-17 18:33:36 +000048 if (environment->GetInstructionAt(i) != nullptr) {
49 environment->RemoveAsUserOfInput(i);
Roland Levillainfc600dc2014-12-02 17:16:31 +000050 }
51 }
52 }
53}
54
55void HGraph::RemoveInstructionsAsUsersFromDeadBlocks(const ArenaBitVector& visited) const {
Vladimir Markofa6b93c2015-09-15 10:15:55 +010056 for (size_t i = 0; i < blocks_.size(); ++i) {
Roland Levillainfc600dc2014-12-02 17:16:31 +000057 if (!visited.IsBitSet(i)) {
Vladimir Markofa6b93c2015-09-15 10:15:55 +010058 HBasicBlock* block = GetBlock(i);
Nicolas Geoffrayf776b922015-04-15 18:22:45 +010059 DCHECK(block->GetPhis().IsEmpty()) << "Phis are not inserted at this stage";
Roland Levillainfc600dc2014-12-02 17:16:31 +000060 for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
61 RemoveAsUser(it.Current());
62 }
63 }
64 }
65}
66
Nicolas Geoffrayf776b922015-04-15 18:22:45 +010067void HGraph::RemoveDeadBlocks(const ArenaBitVector& visited) {
Vladimir Markofa6b93c2015-09-15 10:15:55 +010068 for (size_t i = 0; i < blocks_.size(); ++i) {
Nicolas Geoffraybe9a92a2014-02-25 14:22:56 +000069 if (!visited.IsBitSet(i)) {
Vladimir Markofa6b93c2015-09-15 10:15:55 +010070 HBasicBlock* block = GetBlock(i);
Nicolas Geoffrayf776b922015-04-15 18:22:45 +010071 // We only need to update the successor, which might be live.
Vladimir Marko60584552015-09-03 13:35:12 +000072 for (HBasicBlock* successor : block->GetSuccessors()) {
73 successor->RemovePredecessor(block);
David Brazdil1abb4192015-02-17 18:33:36 +000074 }
Nicolas Geoffrayf776b922015-04-15 18:22:45 +010075 // Remove the block from the list of blocks, so that further analyses
76 // never see it.
Vladimir Markofa6b93c2015-09-15 10:15:55 +010077 blocks_[i] = nullptr;
Nicolas Geoffraybe9a92a2014-02-25 14:22:56 +000078 }
79 }
80}
81
82void HGraph::VisitBlockForBackEdges(HBasicBlock* block,
83 ArenaBitVector* visited,
Nicolas Geoffray804d0932014-05-02 08:46:00 +010084 ArenaBitVector* visiting) {
Nicolas Geoffray787c3072014-03-17 10:20:19 +000085 int id = block->GetBlockId();
Nicolas Geoffraybe9a92a2014-02-25 14:22:56 +000086 if (visited->IsBitSet(id)) return;
87
88 visited->SetBit(id);
89 visiting->SetBit(id);
Vladimir Marko60584552015-09-03 13:35:12 +000090 for (HBasicBlock* successor : block->GetSuccessors()) {
Nicolas Geoffray787c3072014-03-17 10:20:19 +000091 if (visiting->IsBitSet(successor->GetBlockId())) {
Nicolas Geoffraybe9a92a2014-02-25 14:22:56 +000092 successor->AddBackEdge(block);
93 } else {
94 VisitBlockForBackEdges(successor, visited, visiting);
95 }
96 }
97 visiting->ClearBit(id);
98}
99
100void HGraph::BuildDominatorTree() {
David Brazdilffee3d32015-07-06 11:48:53 +0100101 // (1) Simplify the CFG so that catch blocks have only exceptional incoming
102 // edges. This invariant simplifies building SSA form because Phis cannot
103 // collect both normal- and exceptional-flow values at the same time.
104 SimplifyCatchBlocks();
105
Vladimir Markofa6b93c2015-09-15 10:15:55 +0100106 ArenaBitVector visited(arena_, blocks_.size(), false);
Nicolas Geoffraybe9a92a2014-02-25 14:22:56 +0000107
David Brazdilffee3d32015-07-06 11:48:53 +0100108 // (2) Find the back edges in the graph doing a DFS traversal.
Nicolas Geoffraybe9a92a2014-02-25 14:22:56 +0000109 FindBackEdges(&visited);
110
David Brazdilffee3d32015-07-06 11:48:53 +0100111 // (3) Remove instructions and phis from blocks not visited during
Roland Levillainfc600dc2014-12-02 17:16:31 +0000112 // the initial DFS as users from other instructions, so that
113 // users can be safely removed before uses later.
114 RemoveInstructionsAsUsersFromDeadBlocks(visited);
115
David Brazdilffee3d32015-07-06 11:48:53 +0100116 // (4) Remove blocks not visited during the initial DFS.
Roland Levillainfc600dc2014-12-02 17:16:31 +0000117 // Step (4) requires dead blocks to be removed from the
Nicolas Geoffraybe9a92a2014-02-25 14:22:56 +0000118 // predecessors list of live blocks.
119 RemoveDeadBlocks(visited);
120
David Brazdilffee3d32015-07-06 11:48:53 +0100121 // (5) Simplify the CFG now, so that we don't need to recompute
Nicolas Geoffray622d9c32014-05-12 16:11:02 +0100122 // dominators and the reverse post order.
123 SimplifyCFG();
124
David Brazdilffee3d32015-07-06 11:48:53 +0100125 // (6) Compute the dominance information and the reverse post order.
Nicolas Geoffray1f82ecc2015-06-24 12:20:24 +0100126 ComputeDominanceInformation();
127}
128
129void HGraph::ClearDominanceInformation() {
130 for (HReversePostOrderIterator it(*this); !it.Done(); it.Advance()) {
131 it.Current()->ClearDominanceInformation();
132 }
Vladimir Markofa6b93c2015-09-15 10:15:55 +0100133 reverse_post_order_.clear();
Nicolas Geoffray1f82ecc2015-06-24 12:20:24 +0100134}
135
136void HBasicBlock::ClearDominanceInformation() {
Vladimir Marko60584552015-09-03 13:35:12 +0000137 dominated_blocks_.clear();
Nicolas Geoffray1f82ecc2015-06-24 12:20:24 +0100138 dominator_ = nullptr;
139}
140
141void HGraph::ComputeDominanceInformation() {
Vladimir Markofa6b93c2015-09-15 10:15:55 +0100142 DCHECK(reverse_post_order_.empty());
143 reverse_post_order_.reserve(blocks_.size());
144 ArenaVector<size_t> visits(blocks_.size(), 0u, arena_->Adapter());
145 reverse_post_order_.push_back(entry_block_);
Vladimir Marko60584552015-09-03 13:35:12 +0000146 for (HBasicBlock* successor : entry_block_->GetSuccessors()) {
147 VisitBlockForDominatorTree(successor, entry_block_, &visits);
Nicolas Geoffraybe9a92a2014-02-25 14:22:56 +0000148 }
149}
150
151HBasicBlock* HGraph::FindCommonDominator(HBasicBlock* first, HBasicBlock* second) const {
Vladimir Markofa6b93c2015-09-15 10:15:55 +0100152 ArenaBitVector visited(arena_, blocks_.size(), false);
Nicolas Geoffraybe9a92a2014-02-25 14:22:56 +0000153 // Walk the dominator tree of the first block and mark the visited blocks.
154 while (first != nullptr) {
Nicolas Geoffray787c3072014-03-17 10:20:19 +0000155 visited.SetBit(first->GetBlockId());
156 first = first->GetDominator();
Nicolas Geoffraybe9a92a2014-02-25 14:22:56 +0000157 }
158 // Walk the dominator tree of the second block until a marked block is found.
159 while (second != nullptr) {
Nicolas Geoffray787c3072014-03-17 10:20:19 +0000160 if (visited.IsBitSet(second->GetBlockId())) {
Nicolas Geoffraybe9a92a2014-02-25 14:22:56 +0000161 return second;
162 }
Nicolas Geoffray787c3072014-03-17 10:20:19 +0000163 second = second->GetDominator();
Nicolas Geoffraybe9a92a2014-02-25 14:22:56 +0000164 }
165 LOG(ERROR) << "Could not find common dominator";
166 return nullptr;
167}
168
169void HGraph::VisitBlockForDominatorTree(HBasicBlock* block,
170 HBasicBlock* predecessor,
Vladimir Markofa6b93c2015-09-15 10:15:55 +0100171 ArenaVector<size_t>* visits) {
Nicolas Geoffray787c3072014-03-17 10:20:19 +0000172 if (block->GetDominator() == nullptr) {
173 block->SetDominator(predecessor);
Nicolas Geoffraybe9a92a2014-02-25 14:22:56 +0000174 } else {
Nicolas Geoffray787c3072014-03-17 10:20:19 +0000175 block->SetDominator(FindCommonDominator(block->GetDominator(), predecessor));
Nicolas Geoffraybe9a92a2014-02-25 14:22:56 +0000176 }
177
Nicolas Geoffraybe9a92a2014-02-25 14:22:56 +0000178 // Once all the forward edges have been visited, we know the immediate
179 // dominator of the block. We can then start visiting its successors.
Vladimir Markofa6b93c2015-09-15 10:15:55 +0100180 DCHECK_LT(block->GetBlockId(), visits->size());
181 if (++(*visits)[block->GetBlockId()] ==
Vladimir Marko60584552015-09-03 13:35:12 +0000182 block->GetPredecessors().size() - block->NumberOfBackEdges()) {
Nicolas Geoffrayd31cf3d2014-09-08 17:30:24 +0100183 block->GetDominator()->AddDominatedBlock(block);
Vladimir Markofa6b93c2015-09-15 10:15:55 +0100184 reverse_post_order_.push_back(block);
Vladimir Marko60584552015-09-03 13:35:12 +0000185 for (HBasicBlock* successor : block->GetSuccessors()) {
186 VisitBlockForDominatorTree(successor, block, visits);
Nicolas Geoffraybe9a92a2014-02-25 14:22:56 +0000187 }
188 }
189}
190
Nicolas Geoffraye53798a2014-12-01 10:31:54 +0000191void HGraph::TransformToSsa() {
Vladimir Markofa6b93c2015-09-15 10:15:55 +0100192 DCHECK(!reverse_post_order_.empty());
Nicolas Geoffrayc32e7702014-04-24 12:43:16 +0100193 SsaBuilder ssa_builder(this);
194 ssa_builder.BuildSsa();
195}
196
David Brazdilfc6a86a2015-06-26 10:33:45 +0000197HBasicBlock* HGraph::SplitEdge(HBasicBlock* block, HBasicBlock* successor) {
David Brazdil3e187382015-06-26 09:59:52 +0000198 HBasicBlock* new_block = new (arena_) HBasicBlock(this, successor->GetDexPc());
199 AddBlock(new_block);
David Brazdil3e187382015-06-26 09:59:52 +0000200 // Use `InsertBetween` to ensure the predecessor index and successor index of
201 // `block` and `successor` are preserved.
202 new_block->InsertBetween(block, successor);
David Brazdilfc6a86a2015-06-26 10:33:45 +0000203 return new_block;
204}
205
206void HGraph::SplitCriticalEdge(HBasicBlock* block, HBasicBlock* successor) {
207 // Insert a new node between `block` and `successor` to split the
208 // critical edge.
209 HBasicBlock* new_block = SplitEdge(block, successor);
Yevgeny Rouban3ecfd652015-09-07 17:57:00 +0600210 new_block->AddInstruction(new (arena_) HGoto(successor->GetDexPc()));
Nicolas Geoffray622d9c32014-05-12 16:11:02 +0100211 if (successor->IsLoopHeader()) {
212 // If we split at a back edge boundary, make the new block the back edge.
213 HLoopInformation* info = successor->GetLoopInformation();
David Brazdil46e2a392015-03-16 17:31:52 +0000214 if (info->IsBackEdge(*block)) {
Nicolas Geoffray622d9c32014-05-12 16:11:02 +0100215 info->RemoveBackEdge(block);
216 info->AddBackEdge(new_block);
Nicolas Geoffrayc32e7702014-04-24 12:43:16 +0100217 }
218 }
219}
220
Nicolas Geoffray622d9c32014-05-12 16:11:02 +0100221void HGraph::SimplifyLoop(HBasicBlock* header) {
222 HLoopInformation* info = header->GetLoopInformation();
223
Nicolas Geoffray622d9c32014-05-12 16:11:02 +0100224 // Make sure the loop has only one pre header. This simplifies SSA building by having
225 // to just look at the pre header to know which locals are initialized at entry of the
226 // loop.
Vladimir Marko60584552015-09-03 13:35:12 +0000227 size_t number_of_incomings = header->GetPredecessors().size() - info->NumberOfBackEdges();
Nicolas Geoffray622d9c32014-05-12 16:11:02 +0100228 if (number_of_incomings != 1) {
Nicolas Geoffray3c049742014-09-24 18:10:46 +0100229 HBasicBlock* pre_header = new (arena_) HBasicBlock(this, header->GetDexPc());
Nicolas Geoffray622d9c32014-05-12 16:11:02 +0100230 AddBlock(pre_header);
Yevgeny Rouban3ecfd652015-09-07 17:57:00 +0600231 pre_header->AddInstruction(new (arena_) HGoto(header->GetDexPc()));
Nicolas Geoffray622d9c32014-05-12 16:11:02 +0100232
Vladimir Marko60584552015-09-03 13:35:12 +0000233 for (size_t pred = 0; pred < header->GetPredecessors().size(); ++pred) {
234 HBasicBlock* predecessor = header->GetPredecessor(pred);
Nicolas Geoffraydb216f42015-05-05 17:02:20 +0100235 if (!info->IsBackEdge(*predecessor)) {
Nicolas Geoffrayec7e4722014-06-06 11:24:33 +0100236 predecessor->ReplaceSuccessor(header, pre_header);
Nicolas Geoffray622d9c32014-05-12 16:11:02 +0100237 pred--;
Nicolas Geoffray622d9c32014-05-12 16:11:02 +0100238 }
239 }
240 pre_header->AddSuccessor(header);
241 }
Nicolas Geoffray604c6e42014-09-17 12:08:44 +0100242
Nicolas Geoffraydb216f42015-05-05 17:02:20 +0100243 // Make sure the first predecessor of a loop header is the incoming block.
Vladimir Marko60584552015-09-03 13:35:12 +0000244 if (info->IsBackEdge(*header->GetPredecessor(0))) {
245 HBasicBlock* to_swap = header->GetPredecessor(0);
246 for (size_t pred = 1, e = header->GetPredecessors().size(); pred < e; ++pred) {
247 HBasicBlock* predecessor = header->GetPredecessor(pred);
Nicolas Geoffraydb216f42015-05-05 17:02:20 +0100248 if (!info->IsBackEdge(*predecessor)) {
Vladimir Marko60584552015-09-03 13:35:12 +0000249 header->predecessors_[pred] = to_swap;
250 header->predecessors_[0] = predecessor;
Nicolas Geoffraydb216f42015-05-05 17:02:20 +0100251 break;
252 }
253 }
Nicolas Geoffray604c6e42014-09-17 12:08:44 +0100254 }
Nicolas Geoffray3c049742014-09-24 18:10:46 +0100255
256 // Place the suspend check at the beginning of the header, so that live registers
257 // will be known when allocating registers. Note that code generation can still
258 // generate the suspend check at the back edge, but needs to be careful with
259 // loop phi spill slots (which are not written to at back edge).
260 HInstruction* first_instruction = header->GetFirstInstruction();
261 if (!first_instruction->IsSuspendCheck()) {
262 HSuspendCheck* check = new (arena_) HSuspendCheck(header->GetDexPc());
263 header->InsertInstructionBefore(check, first_instruction);
264 first_instruction = check;
265 }
266 info->SetSuspendCheck(first_instruction->AsSuspendCheck());
Nicolas Geoffray622d9c32014-05-12 16:11:02 +0100267}
268
David Brazdilffee3d32015-07-06 11:48:53 +0100269static bool CheckIfPredecessorAtIsExceptional(const HBasicBlock& block, size_t pred_idx) {
Vladimir Marko60584552015-09-03 13:35:12 +0000270 HBasicBlock* predecessor = block.GetPredecessor(pred_idx);
David Brazdilffee3d32015-07-06 11:48:53 +0100271 if (!predecessor->EndsWithTryBoundary()) {
272 // Only edges from HTryBoundary can be exceptional.
273 return false;
274 }
275 HTryBoundary* try_boundary = predecessor->GetLastInstruction()->AsTryBoundary();
276 if (try_boundary->GetNormalFlowSuccessor() == &block) {
277 // This block is the normal-flow successor of `try_boundary`, but it could
278 // also be one of its exception handlers if catch blocks have not been
279 // simplified yet. Predecessors are unordered, so we will consider the first
280 // occurrence to be the normal edge and a possible second occurrence to be
281 // the exceptional edge.
282 return !block.IsFirstIndexOfPredecessor(predecessor, pred_idx);
283 } else {
284 // This is not the normal-flow successor of `try_boundary`, hence it must be
285 // one of its exception handlers.
286 DCHECK(try_boundary->HasExceptionHandler(block));
287 return true;
288 }
289}
290
291void HGraph::SimplifyCatchBlocks() {
Vladimir Markob7d8e8c2015-09-17 15:47:05 +0100292 // NOTE: We're appending new blocks inside the loop, so we need to use index because iterators
293 // can be invalidated. We remember the initial size to avoid iterating over the new blocks.
294 for (size_t block_id = 0u, end = blocks_.size(); block_id != end; ++block_id) {
295 HBasicBlock* catch_block = blocks_[block_id];
David Brazdilffee3d32015-07-06 11:48:53 +0100296 if (!catch_block->IsCatchBlock()) {
297 continue;
298 }
299
300 bool exceptional_predecessors_only = true;
Vladimir Marko60584552015-09-03 13:35:12 +0000301 for (size_t j = 0; j < catch_block->GetPredecessors().size(); ++j) {
David Brazdilffee3d32015-07-06 11:48:53 +0100302 if (!CheckIfPredecessorAtIsExceptional(*catch_block, j)) {
303 exceptional_predecessors_only = false;
304 break;
305 }
306 }
307
308 if (!exceptional_predecessors_only) {
309 // Catch block has normal-flow predecessors and needs to be simplified.
310 // Splitting the block before its first instruction moves all its
311 // instructions into `normal_block` and links the two blocks with a Goto.
312 // Afterwards, incoming normal-flow edges are re-linked to `normal_block`,
313 // leaving `catch_block` with the exceptional edges only.
314 // Note that catch blocks with normal-flow predecessors cannot begin with
315 // a MOVE_EXCEPTION instruction, as guaranteed by the verifier.
316 DCHECK(!catch_block->GetFirstInstruction()->IsLoadException());
317 HBasicBlock* normal_block = catch_block->SplitBefore(catch_block->GetFirstInstruction());
Vladimir Marko60584552015-09-03 13:35:12 +0000318 for (size_t j = 0; j < catch_block->GetPredecessors().size(); ++j) {
David Brazdilffee3d32015-07-06 11:48:53 +0100319 if (!CheckIfPredecessorAtIsExceptional(*catch_block, j)) {
Vladimir Marko60584552015-09-03 13:35:12 +0000320 catch_block->GetPredecessor(j)->ReplaceSuccessor(catch_block, normal_block);
David Brazdilffee3d32015-07-06 11:48:53 +0100321 --j;
322 }
323 }
324 }
325 }
326}
327
328void HGraph::ComputeTryBlockInformation() {
329 // Iterate in reverse post order to propagate try membership information from
330 // predecessors to their successors.
331 for (HReversePostOrderIterator it(*this); !it.Done(); it.Advance()) {
332 HBasicBlock* block = it.Current();
333 if (block->IsEntryBlock() || block->IsCatchBlock()) {
334 // Catch blocks after simplification have only exceptional predecessors
335 // and hence are never in tries.
336 continue;
337 }
338
339 // Infer try membership from the first predecessor. Having simplified loops,
340 // the first predecessor can never be a back edge and therefore it must have
341 // been visited already and had its try membership set.
Vladimir Marko60584552015-09-03 13:35:12 +0000342 HBasicBlock* first_predecessor = block->GetPredecessor(0);
David Brazdilffee3d32015-07-06 11:48:53 +0100343 DCHECK(!block->IsLoopHeader() || !block->GetLoopInformation()->IsBackEdge(*first_predecessor));
David Brazdilec16f792015-08-19 15:04:01 +0100344 const HTryBoundary* try_entry = first_predecessor->ComputeTryEntryOfSuccessors();
345 if (try_entry != nullptr) {
346 block->SetTryCatchInformation(new (arena_) TryCatchInformation(*try_entry));
347 }
David Brazdilffee3d32015-07-06 11:48:53 +0100348 }
349}
350
Nicolas Geoffray622d9c32014-05-12 16:11:02 +0100351void HGraph::SimplifyCFG() {
352 // Simplify the CFG for future analysis, and code generation:
353 // (1): Split critical edges.
354 // (2): Simplify loops by having only one back edge, and one preheader.
Vladimir Markob7d8e8c2015-09-17 15:47:05 +0100355 // NOTE: We're appending new blocks inside the loop, so we need to use index because iterators
356 // can be invalidated. We remember the initial size to avoid iterating over the new blocks.
357 for (size_t block_id = 0u, end = blocks_.size(); block_id != end; ++block_id) {
358 HBasicBlock* block = blocks_[block_id];
Nicolas Geoffrayf776b922015-04-15 18:22:45 +0100359 if (block == nullptr) continue;
David Brazdilffee3d32015-07-06 11:48:53 +0100360 if (block->NumberOfNormalSuccessors() > 1) {
Vladimir Marko60584552015-09-03 13:35:12 +0000361 for (size_t j = 0; j < block->GetSuccessors().size(); ++j) {
362 HBasicBlock* successor = block->GetSuccessor(j);
David Brazdilffee3d32015-07-06 11:48:53 +0100363 DCHECK(!successor->IsCatchBlock());
Vladimir Marko60584552015-09-03 13:35:12 +0000364 if (successor->GetPredecessors().size() > 1) {
Nicolas Geoffray622d9c32014-05-12 16:11:02 +0100365 SplitCriticalEdge(block, successor);
366 --j;
367 }
368 }
369 }
370 if (block->IsLoopHeader()) {
371 SimplifyLoop(block);
372 }
373 }
374}
375
Nicolas Geoffrayf5370122014-12-02 11:51:19 +0000376bool HGraph::AnalyzeNaturalLoops() const {
Nicolas Geoffrayf776b922015-04-15 18:22:45 +0100377 // Order does not matter.
378 for (HReversePostOrderIterator it(*this); !it.Done(); it.Advance()) {
379 HBasicBlock* block = it.Current();
Nicolas Geoffray622d9c32014-05-12 16:11:02 +0100380 if (block->IsLoopHeader()) {
David Brazdilffee3d32015-07-06 11:48:53 +0100381 if (block->IsCatchBlock()) {
382 // TODO: Dealing with exceptional back edges could be tricky because
383 // they only approximate the real control flow. Bail out for now.
384 return false;
385 }
Nicolas Geoffray622d9c32014-05-12 16:11:02 +0100386 HLoopInformation* info = block->GetLoopInformation();
387 if (!info->Populate()) {
388 // Abort if the loop is non natural. We currently bailout in such cases.
389 return false;
390 }
391 }
392 }
393 return true;
394}
395
David Brazdil8d5b8b22015-03-24 10:51:52 +0000396void HGraph::InsertConstant(HConstant* constant) {
397 // New constants are inserted before the final control-flow instruction
398 // of the graph, or at its end if called from the graph builder.
399 if (entry_block_->EndsWithControlFlowInstruction()) {
400 entry_block_->InsertInstructionBefore(constant, entry_block_->GetLastInstruction());
David Brazdil46e2a392015-03-16 17:31:52 +0000401 } else {
David Brazdil8d5b8b22015-03-24 10:51:52 +0000402 entry_block_->AddInstruction(constant);
David Brazdil46e2a392015-03-16 17:31:52 +0000403 }
404}
405
Yevgeny Rouban3ecfd652015-09-07 17:57:00 +0600406HNullConstant* HGraph::GetNullConstant(uint32_t dex_pc) {
Nicolas Geoffray18e68732015-06-17 23:09:05 +0100407 // For simplicity, don't bother reviving the cached null constant if it is
408 // not null and not in a block. Otherwise, we need to clear the instruction
409 // id and/or any invariants the graph is assuming when adding new instructions.
410 if ((cached_null_constant_ == nullptr) || (cached_null_constant_->GetBlock() == nullptr)) {
Yevgeny Rouban3ecfd652015-09-07 17:57:00 +0600411 cached_null_constant_ = new (arena_) HNullConstant(dex_pc);
David Brazdil8d5b8b22015-03-24 10:51:52 +0000412 InsertConstant(cached_null_constant_);
Nicolas Geoffrayd6138ef2015-02-18 14:48:53 +0000413 }
414 return cached_null_constant_;
415}
416
Nicolas Geoffray76b1e172015-05-27 17:18:33 +0100417HCurrentMethod* HGraph::GetCurrentMethod() {
Nicolas Geoffrayf78848f2015-06-17 11:57:56 +0100418 // For simplicity, don't bother reviving the cached current method if it is
419 // not null and not in a block. Otherwise, we need to clear the instruction
420 // id and/or any invariants the graph is assuming when adding new instructions.
421 if ((cached_current_method_ == nullptr) || (cached_current_method_->GetBlock() == nullptr)) {
Mathieu Chartiere401d142015-04-22 13:56:20 -0700422 cached_current_method_ = new (arena_) HCurrentMethod(
Yevgeny Rouban3ecfd652015-09-07 17:57:00 +0600423 Is64BitInstructionSet(instruction_set_) ? Primitive::kPrimLong : Primitive::kPrimInt,
424 entry_block_->GetDexPc());
Nicolas Geoffray76b1e172015-05-27 17:18:33 +0100425 if (entry_block_->GetFirstInstruction() == nullptr) {
426 entry_block_->AddInstruction(cached_current_method_);
427 } else {
428 entry_block_->InsertInstructionBefore(
429 cached_current_method_, entry_block_->GetFirstInstruction());
430 }
431 }
432 return cached_current_method_;
433}
434
Yevgeny Rouban3ecfd652015-09-07 17:57:00 +0600435HConstant* HGraph::GetConstant(Primitive::Type type, int64_t value, uint32_t dex_pc) {
David Brazdil8d5b8b22015-03-24 10:51:52 +0000436 switch (type) {
437 case Primitive::Type::kPrimBoolean:
438 DCHECK(IsUint<1>(value));
439 FALLTHROUGH_INTENDED;
440 case Primitive::Type::kPrimByte:
441 case Primitive::Type::kPrimChar:
442 case Primitive::Type::kPrimShort:
443 case Primitive::Type::kPrimInt:
444 DCHECK(IsInt(Primitive::ComponentSize(type) * kBitsPerByte, value));
Yevgeny Rouban3ecfd652015-09-07 17:57:00 +0600445 return GetIntConstant(static_cast<int32_t>(value), dex_pc);
David Brazdil8d5b8b22015-03-24 10:51:52 +0000446
447 case Primitive::Type::kPrimLong:
Yevgeny Rouban3ecfd652015-09-07 17:57:00 +0600448 return GetLongConstant(value, dex_pc);
David Brazdil8d5b8b22015-03-24 10:51:52 +0000449
450 default:
451 LOG(FATAL) << "Unsupported constant type";
452 UNREACHABLE();
David Brazdil46e2a392015-03-16 17:31:52 +0000453 }
David Brazdil46e2a392015-03-16 17:31:52 +0000454}
455
Nicolas Geoffrayf213e052015-04-27 08:53:46 +0000456void HGraph::CacheFloatConstant(HFloatConstant* constant) {
457 int32_t value = bit_cast<int32_t, float>(constant->GetValue());
458 DCHECK(cached_float_constants_.find(value) == cached_float_constants_.end());
459 cached_float_constants_.Overwrite(value, constant);
460}
461
462void HGraph::CacheDoubleConstant(HDoubleConstant* constant) {
463 int64_t value = bit_cast<int64_t, double>(constant->GetValue());
464 DCHECK(cached_double_constants_.find(value) == cached_double_constants_.end());
465 cached_double_constants_.Overwrite(value, constant);
466}
467
Nicolas Geoffray276d9da2015-02-02 18:24:11 +0000468void HLoopInformation::Add(HBasicBlock* block) {
469 blocks_.SetBit(block->GetBlockId());
470}
471
David Brazdil46e2a392015-03-16 17:31:52 +0000472void HLoopInformation::Remove(HBasicBlock* block) {
473 blocks_.ClearBit(block->GetBlockId());
474}
475
Nicolas Geoffray622d9c32014-05-12 16:11:02 +0100476void HLoopInformation::PopulateRecursive(HBasicBlock* block) {
477 if (blocks_.IsBitSet(block->GetBlockId())) {
478 return;
479 }
480
481 blocks_.SetBit(block->GetBlockId());
482 block->SetInLoop(this);
Vladimir Marko60584552015-09-03 13:35:12 +0000483 for (HBasicBlock* predecessor : block->GetPredecessors()) {
484 PopulateRecursive(predecessor);
Nicolas Geoffray622d9c32014-05-12 16:11:02 +0100485 }
486}
487
488bool HLoopInformation::Populate() {
David Brazdila4b8c212015-05-07 09:59:30 +0100489 DCHECK_EQ(blocks_.NumSetBits(), 0u) << "Loop information has already been populated";
Vladimir Markofa6b93c2015-09-15 10:15:55 +0100490 for (HBasicBlock* back_edge : GetBackEdges()) {
Nicolas Geoffraydb216f42015-05-05 17:02:20 +0100491 DCHECK(back_edge->GetDominator() != nullptr);
492 if (!header_->Dominates(back_edge)) {
493 // This loop is not natural. Do not bother going further.
494 return false;
495 }
Nicolas Geoffray622d9c32014-05-12 16:11:02 +0100496
Nicolas Geoffraydb216f42015-05-05 17:02:20 +0100497 // Populate this loop: starting with the back edge, recursively add predecessors
498 // that are not already part of that loop. Set the header as part of the loop
499 // to end the recursion.
500 // This is a recursive implementation of the algorithm described in
501 // "Advanced Compiler Design & Implementation" (Muchnick) p192.
502 blocks_.SetBit(header_->GetBlockId());
503 PopulateRecursive(back_edge);
504 }
Nicolas Geoffray622d9c32014-05-12 16:11:02 +0100505 return true;
506}
507
David Brazdila4b8c212015-05-07 09:59:30 +0100508void HLoopInformation::Update() {
509 HGraph* graph = header_->GetGraph();
510 for (uint32_t id : blocks_.Indexes()) {
Vladimir Markofa6b93c2015-09-15 10:15:55 +0100511 HBasicBlock* block = graph->GetBlock(id);
David Brazdila4b8c212015-05-07 09:59:30 +0100512 // Reset loop information of non-header blocks inside the loop, except
513 // members of inner nested loops because those should already have been
514 // updated by their own LoopInformation.
515 if (block->GetLoopInformation() == this && block != header_) {
516 block->SetLoopInformation(nullptr);
517 }
518 }
519 blocks_.ClearAllBits();
520
Vladimir Markofa6b93c2015-09-15 10:15:55 +0100521 if (back_edges_.empty()) {
David Brazdila4b8c212015-05-07 09:59:30 +0100522 // The loop has been dismantled, delete its suspend check and remove info
523 // from the header.
524 DCHECK(HasSuspendCheck());
525 header_->RemoveInstruction(suspend_check_);
526 header_->SetLoopInformation(nullptr);
527 header_ = nullptr;
528 suspend_check_ = nullptr;
529 } else {
530 if (kIsDebugBuild) {
Vladimir Markofa6b93c2015-09-15 10:15:55 +0100531 for (HBasicBlock* back_edge : back_edges_) {
532 DCHECK(header_->Dominates(back_edge));
David Brazdila4b8c212015-05-07 09:59:30 +0100533 }
534 }
535 // This loop still has reachable back edges. Repopulate the list of blocks.
536 bool populate_successful = Populate();
537 DCHECK(populate_successful);
538 }
539}
540
Nicolas Geoffray622d9c32014-05-12 16:11:02 +0100541HBasicBlock* HLoopInformation::GetPreHeader() const {
Nicolas Geoffray622d9c32014-05-12 16:11:02 +0100542 return header_->GetDominator();
543}
544
545bool HLoopInformation::Contains(const HBasicBlock& block) const {
546 return blocks_.IsBitSet(block.GetBlockId());
547}
548
549bool HLoopInformation::IsIn(const HLoopInformation& other) const {
550 return other.blocks_.IsBitSet(header_->GetBlockId());
551}
552
Nicolas Geoffraydb216f42015-05-05 17:02:20 +0100553size_t HLoopInformation::GetLifetimeEnd() const {
554 size_t last_position = 0;
Vladimir Markofa6b93c2015-09-15 10:15:55 +0100555 for (HBasicBlock* back_edge : GetBackEdges()) {
556 last_position = std::max(back_edge->GetLifetimeEnd(), last_position);
Nicolas Geoffraydb216f42015-05-05 17:02:20 +0100557 }
558 return last_position;
559}
560
Nicolas Geoffray622d9c32014-05-12 16:11:02 +0100561bool HBasicBlock::Dominates(HBasicBlock* other) const {
562 // Walk up the dominator tree from `other`, to find out if `this`
563 // is an ancestor.
564 HBasicBlock* current = other;
565 while (current != nullptr) {
566 if (current == this) {
567 return true;
568 }
569 current = current->GetDominator();
570 }
571 return false;
Nicolas Geoffrayc32e7702014-04-24 12:43:16 +0100572}
573
Nicolas Geoffray191c4b12014-10-07 14:14:27 +0100574static void UpdateInputsUsers(HInstruction* instruction) {
575 for (size_t i = 0, e = instruction->InputCount(); i < e; ++i) {
576 instruction->InputAt(i)->AddUseAt(instruction, i);
577 }
578 // Environment should be created later.
579 DCHECK(!instruction->HasEnvironment());
580}
581
Roland Levillainccc07a92014-09-16 14:48:16 +0100582void HBasicBlock::ReplaceAndRemoveInstructionWith(HInstruction* initial,
583 HInstruction* replacement) {
584 DCHECK(initial->GetBlock() == this);
585 InsertInstructionBefore(replacement, initial);
586 initial->ReplaceWith(replacement);
587 RemoveInstruction(initial);
588}
589
Nicolas Geoffrayc32e7702014-04-24 12:43:16 +0100590static void Add(HInstructionList* instruction_list,
591 HBasicBlock* block,
592 HInstruction* instruction) {
Nicolas Geoffray787c3072014-03-17 10:20:19 +0000593 DCHECK(instruction->GetBlock() == nullptr);
Nicolas Geoffray43c86422014-03-18 11:58:24 +0000594 DCHECK_EQ(instruction->GetId(), -1);
Nicolas Geoffrayc32e7702014-04-24 12:43:16 +0100595 instruction->SetBlock(block);
596 instruction->SetId(block->GetGraph()->GetNextInstructionId());
Nicolas Geoffray191c4b12014-10-07 14:14:27 +0100597 UpdateInputsUsers(instruction);
Nicolas Geoffrayc32e7702014-04-24 12:43:16 +0100598 instruction_list->AddInstruction(instruction);
599}
600
601void HBasicBlock::AddInstruction(HInstruction* instruction) {
602 Add(&instructions_, this, instruction);
603}
604
605void HBasicBlock::AddPhi(HPhi* phi) {
606 Add(&phis_, this, phi);
607}
608
David Brazdilc3d743f2015-04-22 13:40:50 +0100609void HBasicBlock::InsertInstructionBefore(HInstruction* instruction, HInstruction* cursor) {
610 DCHECK(!cursor->IsPhi());
611 DCHECK(!instruction->IsPhi());
612 DCHECK_EQ(instruction->GetId(), -1);
613 DCHECK_NE(cursor->GetId(), -1);
614 DCHECK_EQ(cursor->GetBlock(), this);
615 DCHECK(!instruction->IsControlFlow());
616 instruction->SetBlock(this);
617 instruction->SetId(GetGraph()->GetNextInstructionId());
618 UpdateInputsUsers(instruction);
619 instructions_.InsertInstructionBefore(instruction, cursor);
620}
621
Guillaume "Vermeille" Sanchez2967ec62015-04-24 16:36:52 +0100622void HBasicBlock::InsertInstructionAfter(HInstruction* instruction, HInstruction* cursor) {
623 DCHECK(!cursor->IsPhi());
624 DCHECK(!instruction->IsPhi());
625 DCHECK_EQ(instruction->GetId(), -1);
626 DCHECK_NE(cursor->GetId(), -1);
627 DCHECK_EQ(cursor->GetBlock(), this);
628 DCHECK(!instruction->IsControlFlow());
629 DCHECK(!cursor->IsControlFlow());
630 instruction->SetBlock(this);
631 instruction->SetId(GetGraph()->GetNextInstructionId());
632 UpdateInputsUsers(instruction);
633 instructions_.InsertInstructionAfter(instruction, cursor);
634}
635
Nicolas Geoffray102cbed2014-10-15 18:31:05 +0100636void HBasicBlock::InsertPhiAfter(HPhi* phi, HPhi* cursor) {
637 DCHECK_EQ(phi->GetId(), -1);
638 DCHECK_NE(cursor->GetId(), -1);
639 DCHECK_EQ(cursor->GetBlock(), this);
Nicolas Geoffray102cbed2014-10-15 18:31:05 +0100640 phi->SetBlock(this);
641 phi->SetId(GetGraph()->GetNextInstructionId());
642 UpdateInputsUsers(phi);
David Brazdilc3d743f2015-04-22 13:40:50 +0100643 phis_.InsertInstructionAfter(phi, cursor);
Nicolas Geoffray102cbed2014-10-15 18:31:05 +0100644}
645
Nicolas Geoffrayc32e7702014-04-24 12:43:16 +0100646static void Remove(HInstructionList* instruction_list,
647 HBasicBlock* block,
David Brazdil1abb4192015-02-17 18:33:36 +0000648 HInstruction* instruction,
649 bool ensure_safety) {
Nicolas Geoffrayc32e7702014-04-24 12:43:16 +0100650 DCHECK_EQ(block, instruction->GetBlock());
Nicolas Geoffrayc32e7702014-04-24 12:43:16 +0100651 instruction->SetBlock(nullptr);
652 instruction_list->RemoveInstruction(instruction);
David Brazdil1abb4192015-02-17 18:33:36 +0000653 if (ensure_safety) {
654 DCHECK(instruction->GetUses().IsEmpty());
655 DCHECK(instruction->GetEnvUses().IsEmpty());
656 RemoveAsUser(instruction);
657 }
Nicolas Geoffrayc32e7702014-04-24 12:43:16 +0100658}
659
David Brazdil1abb4192015-02-17 18:33:36 +0000660void HBasicBlock::RemoveInstruction(HInstruction* instruction, bool ensure_safety) {
David Brazdilc7508e92015-04-27 13:28:57 +0100661 DCHECK(!instruction->IsPhi());
David Brazdil1abb4192015-02-17 18:33:36 +0000662 Remove(&instructions_, this, instruction, ensure_safety);
Nicolas Geoffrayc32e7702014-04-24 12:43:16 +0100663}
664
David Brazdil1abb4192015-02-17 18:33:36 +0000665void HBasicBlock::RemovePhi(HPhi* phi, bool ensure_safety) {
666 Remove(&phis_, this, phi, ensure_safety);
Nicolas Geoffrayc32e7702014-04-24 12:43:16 +0100667}
668
David Brazdilc7508e92015-04-27 13:28:57 +0100669void HBasicBlock::RemoveInstructionOrPhi(HInstruction* instruction, bool ensure_safety) {
670 if (instruction->IsPhi()) {
671 RemovePhi(instruction->AsPhi(), ensure_safety);
672 } else {
673 RemoveInstruction(instruction, ensure_safety);
674 }
675}
676
Vladimir Marko71bf8092015-09-15 15:33:14 +0100677void HEnvironment::CopyFrom(const ArenaVector<HInstruction*>& locals) {
678 for (size_t i = 0; i < locals.size(); i++) {
679 HInstruction* instruction = locals[i];
Nicolas Geoffray8c0c91a2015-05-07 11:46:05 +0100680 SetRawEnvAt(i, instruction);
681 if (instruction != nullptr) {
682 instruction->AddEnvUseAt(this, i);
683 }
684 }
685}
686
David Brazdiled596192015-01-23 10:39:45 +0000687void HEnvironment::CopyFrom(HEnvironment* env) {
688 for (size_t i = 0; i < env->Size(); i++) {
689 HInstruction* instruction = env->GetInstructionAt(i);
690 SetRawEnvAt(i, instruction);
691 if (instruction != nullptr) {
692 instruction->AddEnvUseAt(this, i);
Nicolas Geoffrayc32e7702014-04-24 12:43:16 +0100693 }
David Brazdiled596192015-01-23 10:39:45 +0000694 }
695}
696
Mingyao Yang206d6fd2015-04-13 16:46:28 -0700697void HEnvironment::CopyFromWithLoopPhiAdjustment(HEnvironment* env,
698 HBasicBlock* loop_header) {
699 DCHECK(loop_header->IsLoopHeader());
700 for (size_t i = 0; i < env->Size(); i++) {
701 HInstruction* instruction = env->GetInstructionAt(i);
702 SetRawEnvAt(i, instruction);
703 if (instruction == nullptr) {
704 continue;
705 }
706 if (instruction->IsLoopHeaderPhi() && (instruction->GetBlock() == loop_header)) {
707 // At the end of the loop pre-header, the corresponding value for instruction
708 // is the first input of the phi.
709 HInstruction* initial = instruction->AsPhi()->InputAt(0);
710 DCHECK(initial->GetBlock()->Dominates(loop_header));
711 SetRawEnvAt(i, initial);
712 initial->AddEnvUseAt(this, i);
713 } else {
714 instruction->AddEnvUseAt(this, i);
715 }
716 }
717}
718
David Brazdil1abb4192015-02-17 18:33:36 +0000719void HEnvironment::RemoveAsUserOfInput(size_t index) const {
Vladimir Markofa6b93c2015-09-15 10:15:55 +0100720 DCHECK_LT(index, Size());
721 const HUserRecord<HEnvironment*>& user_record = vregs_[index];
David Brazdil1abb4192015-02-17 18:33:36 +0000722 user_record.GetInstruction()->RemoveEnvironmentUser(user_record.GetUseNode());
Nicolas Geoffrayc32e7702014-04-24 12:43:16 +0100723}
724
Calin Juravle77520bc2015-01-12 18:45:46 +0000725HInstruction* HInstruction::GetNextDisregardingMoves() const {
726 HInstruction* next = GetNext();
727 while (next != nullptr && next->IsParallelMove()) {
728 next = next->GetNext();
729 }
730 return next;
731}
732
733HInstruction* HInstruction::GetPreviousDisregardingMoves() const {
734 HInstruction* previous = GetPrevious();
735 while (previous != nullptr && previous->IsParallelMove()) {
736 previous = previous->GetPrevious();
737 }
738 return previous;
739}
740
Nicolas Geoffrayc32e7702014-04-24 12:43:16 +0100741void HInstructionList::AddInstruction(HInstruction* instruction) {
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000742 if (first_instruction_ == nullptr) {
743 DCHECK(last_instruction_ == nullptr);
744 first_instruction_ = last_instruction_ = instruction;
745 } else {
746 last_instruction_->next_ = instruction;
747 instruction->previous_ = last_instruction_;
748 last_instruction_ = instruction;
749 }
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000750}
751
David Brazdilc3d743f2015-04-22 13:40:50 +0100752void HInstructionList::InsertInstructionBefore(HInstruction* instruction, HInstruction* cursor) {
753 DCHECK(Contains(cursor));
754 if (cursor == first_instruction_) {
755 cursor->previous_ = instruction;
756 instruction->next_ = cursor;
757 first_instruction_ = instruction;
758 } else {
759 instruction->previous_ = cursor->previous_;
760 instruction->next_ = cursor;
761 cursor->previous_ = instruction;
762 instruction->previous_->next_ = instruction;
763 }
764}
765
766void HInstructionList::InsertInstructionAfter(HInstruction* instruction, HInstruction* cursor) {
767 DCHECK(Contains(cursor));
768 if (cursor == last_instruction_) {
769 cursor->next_ = instruction;
770 instruction->previous_ = cursor;
771 last_instruction_ = instruction;
772 } else {
773 instruction->next_ = cursor->next_;
774 instruction->previous_ = cursor;
775 cursor->next_ = instruction;
776 instruction->next_->previous_ = instruction;
777 }
778}
779
Nicolas Geoffrayc32e7702014-04-24 12:43:16 +0100780void HInstructionList::RemoveInstruction(HInstruction* instruction) {
781 if (instruction->previous_ != nullptr) {
782 instruction->previous_->next_ = instruction->next_;
783 }
784 if (instruction->next_ != nullptr) {
785 instruction->next_->previous_ = instruction->previous_;
786 }
787 if (instruction == first_instruction_) {
788 first_instruction_ = instruction->next_;
789 }
790 if (instruction == last_instruction_) {
791 last_instruction_ = instruction->previous_;
792 }
793}
794
Roland Levillain6b469232014-09-25 10:10:38 +0100795bool HInstructionList::Contains(HInstruction* instruction) const {
796 for (HInstructionIterator it(*this); !it.Done(); it.Advance()) {
797 if (it.Current() == instruction) {
798 return true;
799 }
800 }
801 return false;
802}
803
Roland Levillainccc07a92014-09-16 14:48:16 +0100804bool HInstructionList::FoundBefore(const HInstruction* instruction1,
805 const HInstruction* instruction2) const {
806 DCHECK_EQ(instruction1->GetBlock(), instruction2->GetBlock());
807 for (HInstructionIterator it(*this); !it.Done(); it.Advance()) {
808 if (it.Current() == instruction1) {
809 return true;
810 }
811 if (it.Current() == instruction2) {
812 return false;
813 }
814 }
815 LOG(FATAL) << "Did not find an order between two instructions of the same block.";
816 return true;
817}
818
Roland Levillain6c82d402014-10-13 16:10:27 +0100819bool HInstruction::StrictlyDominates(HInstruction* other_instruction) const {
820 if (other_instruction == this) {
821 // An instruction does not strictly dominate itself.
822 return false;
823 }
Roland Levillainccc07a92014-09-16 14:48:16 +0100824 HBasicBlock* block = GetBlock();
825 HBasicBlock* other_block = other_instruction->GetBlock();
826 if (block != other_block) {
827 return GetBlock()->Dominates(other_instruction->GetBlock());
828 } else {
829 // If both instructions are in the same block, ensure this
830 // instruction comes before `other_instruction`.
831 if (IsPhi()) {
832 if (!other_instruction->IsPhi()) {
833 // Phis appear before non phi-instructions so this instruction
834 // dominates `other_instruction`.
835 return true;
836 } else {
837 // There is no order among phis.
838 LOG(FATAL) << "There is no dominance between phis of a same block.";
839 return false;
840 }
841 } else {
842 // `this` is not a phi.
843 if (other_instruction->IsPhi()) {
844 // Phis appear before non phi-instructions so this instruction
845 // does not dominate `other_instruction`.
846 return false;
847 } else {
848 // Check whether this instruction comes before
849 // `other_instruction` in the instruction list.
850 return block->GetInstructions().FoundBefore(this, other_instruction);
851 }
852 }
853 }
854}
855
Nicolas Geoffrayc32e7702014-04-24 12:43:16 +0100856void HInstruction::ReplaceWith(HInstruction* other) {
Nicolas Geoffraya7062e02014-05-22 12:50:17 +0100857 DCHECK(other != nullptr);
David Brazdiled596192015-01-23 10:39:45 +0000858 for (HUseIterator<HInstruction*> it(GetUses()); !it.Done(); it.Advance()) {
859 HUseListNode<HInstruction*>* current = it.Current();
Nicolas Geoffrayc32e7702014-04-24 12:43:16 +0100860 HInstruction* user = current->GetUser();
861 size_t input_index = current->GetIndex();
862 user->SetRawInputAt(input_index, other);
863 other->AddUseAt(user, input_index);
864 }
865
David Brazdiled596192015-01-23 10:39:45 +0000866 for (HUseIterator<HEnvironment*> it(GetEnvUses()); !it.Done(); it.Advance()) {
867 HUseListNode<HEnvironment*>* current = it.Current();
Nicolas Geoffrayc32e7702014-04-24 12:43:16 +0100868 HEnvironment* user = current->GetUser();
869 size_t input_index = current->GetIndex();
870 user->SetRawEnvAt(input_index, other);
871 other->AddEnvUseAt(user, input_index);
872 }
873
David Brazdiled596192015-01-23 10:39:45 +0000874 uses_.Clear();
875 env_uses_.Clear();
Nicolas Geoffrayc32e7702014-04-24 12:43:16 +0100876}
877
Nicolas Geoffray102cbed2014-10-15 18:31:05 +0100878void HInstruction::ReplaceInput(HInstruction* replacement, size_t index) {
David Brazdil1abb4192015-02-17 18:33:36 +0000879 RemoveAsUserOfInput(index);
Nicolas Geoffray102cbed2014-10-15 18:31:05 +0100880 SetRawInputAt(index, replacement);
881 replacement->AddUseAt(this, index);
882}
883
Nicolas Geoffray39468442014-09-02 15:17:15 +0100884size_t HInstruction::EnvironmentSize() const {
885 return HasEnvironment() ? environment_->Size() : 0;
886}
887
Nicolas Geoffrayc32e7702014-04-24 12:43:16 +0100888void HPhi::AddInput(HInstruction* input) {
889 DCHECK(input->GetBlock() != nullptr);
Vladimir Markofa6b93c2015-09-15 10:15:55 +0100890 inputs_.push_back(HUserRecord<HInstruction*>(input));
891 input->AddUseAt(this, inputs_.size() - 1);
Nicolas Geoffrayc32e7702014-04-24 12:43:16 +0100892}
893
David Brazdil2d7352b2015-04-20 14:52:42 +0100894void HPhi::RemoveInputAt(size_t index) {
895 RemoveAsUserOfInput(index);
Vladimir Markofa6b93c2015-09-15 10:15:55 +0100896 inputs_.erase(inputs_.begin() + index);
Nicolas Geoffray5d7b7f82015-04-28 00:52:43 +0100897 for (size_t i = index, e = InputCount(); i < e; ++i) {
Vladimir Markofa6b93c2015-09-15 10:15:55 +0100898 DCHECK_EQ(InputRecordAt(i).GetUseNode()->GetIndex(), i + 1u);
Nicolas Geoffray5d7b7f82015-04-28 00:52:43 +0100899 InputRecordAt(i).GetUseNode()->SetIndex(i);
900 }
David Brazdil2d7352b2015-04-20 14:52:42 +0100901}
902
Nicolas Geoffray360231a2014-10-08 21:07:48 +0100903#define DEFINE_ACCEPT(name, super) \
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000904void H##name::Accept(HGraphVisitor* visitor) { \
905 visitor->Visit##name(this); \
906}
907
908FOR_EACH_INSTRUCTION(DEFINE_ACCEPT)
909
910#undef DEFINE_ACCEPT
911
912void HGraphVisitor::VisitInsertionOrder() {
Vladimir Markofa6b93c2015-09-15 10:15:55 +0100913 const ArenaVector<HBasicBlock*>& blocks = graph_->GetBlocks();
914 for (HBasicBlock* block : blocks) {
David Brazdil46e2a392015-03-16 17:31:52 +0000915 if (block != nullptr) {
916 VisitBasicBlock(block);
917 }
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000918 }
919}
920
Roland Levillain633021e2014-10-01 14:12:25 +0100921void HGraphVisitor::VisitReversePostOrder() {
922 for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) {
923 VisitBasicBlock(it.Current());
924 }
925}
926
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000927void HGraphVisitor::VisitBasicBlock(HBasicBlock* block) {
Nicolas Geoffrayf635e632014-05-14 09:43:38 +0100928 for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
Nicolas Geoffrayc32e7702014-04-24 12:43:16 +0100929 it.Current()->Accept(this);
930 }
Nicolas Geoffrayf635e632014-05-14 09:43:38 +0100931 for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
Nicolas Geoffray818f2102014-02-18 16:43:35 +0000932 it.Current()->Accept(this);
933 }
934}
935
Mark Mendelle82549b2015-05-06 10:55:34 -0400936HConstant* HTypeConversion::TryStaticEvaluation() const {
937 HGraph* graph = GetBlock()->GetGraph();
938 if (GetInput()->IsIntConstant()) {
939 int32_t value = GetInput()->AsIntConstant()->GetValue();
940 switch (GetResultType()) {
941 case Primitive::kPrimLong:
Yevgeny Rouban3ecfd652015-09-07 17:57:00 +0600942 return graph->GetLongConstant(static_cast<int64_t>(value), GetDexPc());
Mark Mendelle82549b2015-05-06 10:55:34 -0400943 case Primitive::kPrimFloat:
Yevgeny Rouban3ecfd652015-09-07 17:57:00 +0600944 return graph->GetFloatConstant(static_cast<float>(value), GetDexPc());
Mark Mendelle82549b2015-05-06 10:55:34 -0400945 case Primitive::kPrimDouble:
Yevgeny Rouban3ecfd652015-09-07 17:57:00 +0600946 return graph->GetDoubleConstant(static_cast<double>(value), GetDexPc());
Mark Mendelle82549b2015-05-06 10:55:34 -0400947 default:
948 return nullptr;
949 }
950 } else if (GetInput()->IsLongConstant()) {
951 int64_t value = GetInput()->AsLongConstant()->GetValue();
952 switch (GetResultType()) {
953 case Primitive::kPrimInt:
Yevgeny Rouban3ecfd652015-09-07 17:57:00 +0600954 return graph->GetIntConstant(static_cast<int32_t>(value), GetDexPc());
Mark Mendelle82549b2015-05-06 10:55:34 -0400955 case Primitive::kPrimFloat:
Yevgeny Rouban3ecfd652015-09-07 17:57:00 +0600956 return graph->GetFloatConstant(static_cast<float>(value), GetDexPc());
Mark Mendelle82549b2015-05-06 10:55:34 -0400957 case Primitive::kPrimDouble:
Yevgeny Rouban3ecfd652015-09-07 17:57:00 +0600958 return graph->GetDoubleConstant(static_cast<double>(value), GetDexPc());
Mark Mendelle82549b2015-05-06 10:55:34 -0400959 default:
960 return nullptr;
961 }
962 } else if (GetInput()->IsFloatConstant()) {
963 float value = GetInput()->AsFloatConstant()->GetValue();
964 switch (GetResultType()) {
965 case Primitive::kPrimInt:
966 if (std::isnan(value))
Yevgeny Rouban3ecfd652015-09-07 17:57:00 +0600967 return graph->GetIntConstant(0, GetDexPc());
Mark Mendelle82549b2015-05-06 10:55:34 -0400968 if (value >= kPrimIntMax)
Yevgeny Rouban3ecfd652015-09-07 17:57:00 +0600969 return graph->GetIntConstant(kPrimIntMax, GetDexPc());
Mark Mendelle82549b2015-05-06 10:55:34 -0400970 if (value <= kPrimIntMin)
Yevgeny Rouban3ecfd652015-09-07 17:57:00 +0600971 return graph->GetIntConstant(kPrimIntMin, GetDexPc());
972 return graph->GetIntConstant(static_cast<int32_t>(value), GetDexPc());
Mark Mendelle82549b2015-05-06 10:55:34 -0400973 case Primitive::kPrimLong:
974 if (std::isnan(value))
Yevgeny Rouban3ecfd652015-09-07 17:57:00 +0600975 return graph->GetLongConstant(0, GetDexPc());
Mark Mendelle82549b2015-05-06 10:55:34 -0400976 if (value >= kPrimLongMax)
Yevgeny Rouban3ecfd652015-09-07 17:57:00 +0600977 return graph->GetLongConstant(kPrimLongMax, GetDexPc());
Mark Mendelle82549b2015-05-06 10:55:34 -0400978 if (value <= kPrimLongMin)
Yevgeny Rouban3ecfd652015-09-07 17:57:00 +0600979 return graph->GetLongConstant(kPrimLongMin, GetDexPc());
980 return graph->GetLongConstant(static_cast<int64_t>(value), GetDexPc());
Mark Mendelle82549b2015-05-06 10:55:34 -0400981 case Primitive::kPrimDouble:
Yevgeny Rouban3ecfd652015-09-07 17:57:00 +0600982 return graph->GetDoubleConstant(static_cast<double>(value), GetDexPc());
Mark Mendelle82549b2015-05-06 10:55:34 -0400983 default:
984 return nullptr;
985 }
986 } else if (GetInput()->IsDoubleConstant()) {
987 double value = GetInput()->AsDoubleConstant()->GetValue();
988 switch (GetResultType()) {
989 case Primitive::kPrimInt:
990 if (std::isnan(value))
Yevgeny Rouban3ecfd652015-09-07 17:57:00 +0600991 return graph->GetIntConstant(0, GetDexPc());
Mark Mendelle82549b2015-05-06 10:55:34 -0400992 if (value >= kPrimIntMax)
Yevgeny Rouban3ecfd652015-09-07 17:57:00 +0600993 return graph->GetIntConstant(kPrimIntMax, GetDexPc());
Mark Mendelle82549b2015-05-06 10:55:34 -0400994 if (value <= kPrimLongMin)
Yevgeny Rouban3ecfd652015-09-07 17:57:00 +0600995 return graph->GetIntConstant(kPrimIntMin, GetDexPc());
996 return graph->GetIntConstant(static_cast<int32_t>(value), GetDexPc());
Mark Mendelle82549b2015-05-06 10:55:34 -0400997 case Primitive::kPrimLong:
998 if (std::isnan(value))
Yevgeny Rouban3ecfd652015-09-07 17:57:00 +0600999 return graph->GetLongConstant(0, GetDexPc());
Mark Mendelle82549b2015-05-06 10:55:34 -04001000 if (value >= kPrimLongMax)
Yevgeny Rouban3ecfd652015-09-07 17:57:00 +06001001 return graph->GetLongConstant(kPrimLongMax, GetDexPc());
Mark Mendelle82549b2015-05-06 10:55:34 -04001002 if (value <= kPrimLongMin)
Yevgeny Rouban3ecfd652015-09-07 17:57:00 +06001003 return graph->GetLongConstant(kPrimLongMin, GetDexPc());
1004 return graph->GetLongConstant(static_cast<int64_t>(value), GetDexPc());
Mark Mendelle82549b2015-05-06 10:55:34 -04001005 case Primitive::kPrimFloat:
Yevgeny Rouban3ecfd652015-09-07 17:57:00 +06001006 return graph->GetFloatConstant(static_cast<float>(value), GetDexPc());
Mark Mendelle82549b2015-05-06 10:55:34 -04001007 default:
1008 return nullptr;
1009 }
1010 }
1011 return nullptr;
1012}
1013
Roland Levillain9240d6a2014-10-20 16:47:04 +01001014HConstant* HUnaryOperation::TryStaticEvaluation() const {
1015 if (GetInput()->IsIntConstant()) {
Roland Levillain9867bc72015-08-05 10:21:34 +01001016 return Evaluate(GetInput()->AsIntConstant());
Roland Levillain9240d6a2014-10-20 16:47:04 +01001017 } else if (GetInput()->IsLongConstant()) {
Roland Levillain9867bc72015-08-05 10:21:34 +01001018 return Evaluate(GetInput()->AsLongConstant());
Roland Levillain9240d6a2014-10-20 16:47:04 +01001019 }
1020 return nullptr;
1021}
1022
1023HConstant* HBinaryOperation::TryStaticEvaluation() const {
Roland Levillain9867bc72015-08-05 10:21:34 +01001024 if (GetLeft()->IsIntConstant()) {
1025 if (GetRight()->IsIntConstant()) {
1026 return Evaluate(GetLeft()->AsIntConstant(), GetRight()->AsIntConstant());
1027 } else if (GetRight()->IsLongConstant()) {
1028 return Evaluate(GetLeft()->AsIntConstant(), GetRight()->AsLongConstant());
1029 }
1030 } else if (GetLeft()->IsLongConstant()) {
1031 if (GetRight()->IsIntConstant()) {
1032 return Evaluate(GetLeft()->AsLongConstant(), GetRight()->AsIntConstant());
1033 } else if (GetRight()->IsLongConstant()) {
1034 return Evaluate(GetLeft()->AsLongConstant(), GetRight()->AsLongConstant());
Nicolas Geoffray9ee66182015-01-16 12:35:40 +00001035 }
Roland Levillain556c3d12014-09-18 15:25:07 +01001036 }
1037 return nullptr;
1038}
Dave Allison20dfc792014-06-16 20:44:29 -07001039
Alexandre Ramesb2fd7bc2015-03-11 16:48:16 +00001040HConstant* HBinaryOperation::GetConstantRight() const {
1041 if (GetRight()->IsConstant()) {
1042 return GetRight()->AsConstant();
1043 } else if (IsCommutative() && GetLeft()->IsConstant()) {
1044 return GetLeft()->AsConstant();
1045 } else {
1046 return nullptr;
1047 }
1048}
1049
1050// If `GetConstantRight()` returns one of the input, this returns the other
Mathieu Chartier2cebb242015-04-21 16:50:40 -07001051// one. Otherwise it returns null.
Alexandre Ramesb2fd7bc2015-03-11 16:48:16 +00001052HInstruction* HBinaryOperation::GetLeastConstantLeft() const {
1053 HInstruction* most_constant_right = GetConstantRight();
1054 if (most_constant_right == nullptr) {
1055 return nullptr;
1056 } else if (most_constant_right == GetLeft()) {
1057 return GetRight();
1058 } else {
1059 return GetLeft();
1060 }
1061}
1062
Mingyao Yangd43b3ac2015-04-01 14:03:04 -07001063bool HCondition::IsBeforeWhenDisregardMoves(HInstruction* instruction) const {
1064 return this == instruction->GetPreviousDisregardingMoves();
Nicolas Geoffray18efde52014-09-22 15:51:11 +01001065}
1066
Nicolas Geoffray065bf772014-09-03 14:51:22 +01001067bool HInstruction::Equals(HInstruction* other) const {
1068 if (!InstructionTypeEquals(other)) return false;
Nicolas Geoffrayd31cf3d2014-09-08 17:30:24 +01001069 DCHECK_EQ(GetKind(), other->GetKind());
Nicolas Geoffray065bf772014-09-03 14:51:22 +01001070 if (!InstructionDataEquals(other)) return false;
1071 if (GetType() != other->GetType()) return false;
1072 if (InputCount() != other->InputCount()) return false;
1073
1074 for (size_t i = 0, e = InputCount(); i < e; ++i) {
1075 if (InputAt(i) != other->InputAt(i)) return false;
1076 }
Nicolas Geoffrayd31cf3d2014-09-08 17:30:24 +01001077 DCHECK_EQ(ComputeHashCode(), other->ComputeHashCode());
Nicolas Geoffray065bf772014-09-03 14:51:22 +01001078 return true;
1079}
1080
Ian Rogers6a3c1fc2014-10-31 00:33:20 -07001081std::ostream& operator<<(std::ostream& os, const HInstruction::InstructionKind& rhs) {
1082#define DECLARE_CASE(type, super) case HInstruction::k##type: os << #type; break;
1083 switch (rhs) {
1084 FOR_EACH_INSTRUCTION(DECLARE_CASE)
1085 default:
1086 os << "Unknown instruction kind " << static_cast<int>(rhs);
1087 break;
1088 }
1089#undef DECLARE_CASE
1090 return os;
1091}
1092
Nicolas Geoffray82091da2015-01-26 10:02:45 +00001093void HInstruction::MoveBefore(HInstruction* cursor) {
Nicolas Geoffraye53798a2014-12-01 10:31:54 +00001094 next_->previous_ = previous_;
1095 if (previous_ != nullptr) {
1096 previous_->next_ = next_;
1097 }
1098 if (block_->instructions_.first_instruction_ == this) {
1099 block_->instructions_.first_instruction_ = next_;
1100 }
Nicolas Geoffray82091da2015-01-26 10:02:45 +00001101 DCHECK_NE(block_->instructions_.last_instruction_, this);
Nicolas Geoffraye53798a2014-12-01 10:31:54 +00001102
1103 previous_ = cursor->previous_;
1104 if (previous_ != nullptr) {
1105 previous_->next_ = this;
1106 }
1107 next_ = cursor;
1108 cursor->previous_ = this;
1109 block_ = cursor->block_;
Nicolas Geoffray82091da2015-01-26 10:02:45 +00001110
1111 if (block_->instructions_.first_instruction_ == cursor) {
1112 block_->instructions_.first_instruction_ = this;
1113 }
Nicolas Geoffraye53798a2014-12-01 10:31:54 +00001114}
1115
David Brazdilfc6a86a2015-06-26 10:33:45 +00001116HBasicBlock* HBasicBlock::SplitBefore(HInstruction* cursor) {
1117 DCHECK(!graph_->IsInSsaForm()) << "Support for SSA form not implemented";
1118 DCHECK_EQ(cursor->GetBlock(), this);
1119
Yevgeny Rouban3ecfd652015-09-07 17:57:00 +06001120 HBasicBlock* new_block = new (GetGraph()->GetArena()) HBasicBlock(GetGraph(),
1121 cursor->GetDexPc());
David Brazdilfc6a86a2015-06-26 10:33:45 +00001122 new_block->instructions_.first_instruction_ = cursor;
1123 new_block->instructions_.last_instruction_ = instructions_.last_instruction_;
1124 instructions_.last_instruction_ = cursor->previous_;
1125 if (cursor->previous_ == nullptr) {
1126 instructions_.first_instruction_ = nullptr;
1127 } else {
1128 cursor->previous_->next_ = nullptr;
1129 cursor->previous_ = nullptr;
1130 }
1131
1132 new_block->instructions_.SetBlockOfInstructions(new_block);
Yevgeny Rouban3ecfd652015-09-07 17:57:00 +06001133 AddInstruction(new (GetGraph()->GetArena()) HGoto(new_block->GetDexPc()));
David Brazdilfc6a86a2015-06-26 10:33:45 +00001134
Vladimir Marko60584552015-09-03 13:35:12 +00001135 for (HBasicBlock* successor : GetSuccessors()) {
1136 new_block->successors_.push_back(successor);
1137 successor->predecessors_[successor->GetPredecessorIndexOf(this)] = new_block;
David Brazdilfc6a86a2015-06-26 10:33:45 +00001138 }
Vladimir Marko60584552015-09-03 13:35:12 +00001139 successors_.clear();
David Brazdilfc6a86a2015-06-26 10:33:45 +00001140 AddSuccessor(new_block);
1141
David Brazdil56e1acc2015-06-30 15:41:36 +01001142 GetGraph()->AddBlock(new_block);
David Brazdilfc6a86a2015-06-26 10:33:45 +00001143 return new_block;
1144}
1145
Nicolas Geoffray276d9da2015-02-02 18:24:11 +00001146HBasicBlock* HBasicBlock::SplitAfter(HInstruction* cursor) {
1147 DCHECK(!cursor->IsControlFlow());
1148 DCHECK_NE(instructions_.last_instruction_, cursor);
1149 DCHECK_EQ(cursor->GetBlock(), this);
Nicolas Geoffraye53798a2014-12-01 10:31:54 +00001150
Nicolas Geoffray276d9da2015-02-02 18:24:11 +00001151 HBasicBlock* new_block = new (GetGraph()->GetArena()) HBasicBlock(GetGraph(), GetDexPc());
1152 new_block->instructions_.first_instruction_ = cursor->GetNext();
1153 new_block->instructions_.last_instruction_ = instructions_.last_instruction_;
1154 cursor->next_->previous_ = nullptr;
1155 cursor->next_ = nullptr;
1156 instructions_.last_instruction_ = cursor;
1157
1158 new_block->instructions_.SetBlockOfInstructions(new_block);
Vladimir Marko60584552015-09-03 13:35:12 +00001159 for (HBasicBlock* successor : GetSuccessors()) {
1160 new_block->successors_.push_back(successor);
1161 successor->predecessors_[successor->GetPredecessorIndexOf(this)] = new_block;
Nicolas Geoffray276d9da2015-02-02 18:24:11 +00001162 }
Vladimir Marko60584552015-09-03 13:35:12 +00001163 successors_.clear();
Nicolas Geoffray276d9da2015-02-02 18:24:11 +00001164
Vladimir Marko60584552015-09-03 13:35:12 +00001165 for (HBasicBlock* dominated : GetDominatedBlocks()) {
Nicolas Geoffray276d9da2015-02-02 18:24:11 +00001166 dominated->dominator_ = new_block;
Vladimir Marko60584552015-09-03 13:35:12 +00001167 new_block->dominated_blocks_.push_back(dominated);
Nicolas Geoffray276d9da2015-02-02 18:24:11 +00001168 }
Vladimir Marko60584552015-09-03 13:35:12 +00001169 dominated_blocks_.clear();
Nicolas Geoffray276d9da2015-02-02 18:24:11 +00001170 return new_block;
1171}
1172
David Brazdilec16f792015-08-19 15:04:01 +01001173const HTryBoundary* HBasicBlock::ComputeTryEntryOfSuccessors() const {
David Brazdilffee3d32015-07-06 11:48:53 +01001174 if (EndsWithTryBoundary()) {
1175 HTryBoundary* try_boundary = GetLastInstruction()->AsTryBoundary();
1176 if (try_boundary->IsEntry()) {
David Brazdilec16f792015-08-19 15:04:01 +01001177 DCHECK(!IsTryBlock());
David Brazdilffee3d32015-07-06 11:48:53 +01001178 return try_boundary;
1179 } else {
David Brazdilec16f792015-08-19 15:04:01 +01001180 DCHECK(IsTryBlock());
1181 DCHECK(try_catch_information_->GetTryEntry().HasSameExceptionHandlersAs(*try_boundary));
David Brazdilffee3d32015-07-06 11:48:53 +01001182 return nullptr;
1183 }
David Brazdilec16f792015-08-19 15:04:01 +01001184 } else if (IsTryBlock()) {
1185 return &try_catch_information_->GetTryEntry();
David Brazdilffee3d32015-07-06 11:48:53 +01001186 } else {
David Brazdilec16f792015-08-19 15:04:01 +01001187 return nullptr;
David Brazdilffee3d32015-07-06 11:48:53 +01001188 }
David Brazdilfc6a86a2015-06-26 10:33:45 +00001189}
1190
1191static bool HasOnlyOneInstruction(const HBasicBlock& block) {
1192 return block.GetPhis().IsEmpty()
1193 && !block.GetInstructions().IsEmpty()
1194 && block.GetFirstInstruction() == block.GetLastInstruction();
1195}
1196
David Brazdil46e2a392015-03-16 17:31:52 +00001197bool HBasicBlock::IsSingleGoto() const {
David Brazdilfc6a86a2015-06-26 10:33:45 +00001198 return HasOnlyOneInstruction(*this) && GetLastInstruction()->IsGoto();
1199}
1200
1201bool HBasicBlock::IsSingleTryBoundary() const {
1202 return HasOnlyOneInstruction(*this) && GetLastInstruction()->IsTryBoundary();
David Brazdil46e2a392015-03-16 17:31:52 +00001203}
1204
David Brazdil8d5b8b22015-03-24 10:51:52 +00001205bool HBasicBlock::EndsWithControlFlowInstruction() const {
1206 return !GetInstructions().IsEmpty() && GetLastInstruction()->IsControlFlow();
1207}
1208
David Brazdilb2bd1c52015-03-25 11:17:37 +00001209bool HBasicBlock::EndsWithIf() const {
1210 return !GetInstructions().IsEmpty() && GetLastInstruction()->IsIf();
1211}
1212
David Brazdilffee3d32015-07-06 11:48:53 +01001213bool HBasicBlock::EndsWithTryBoundary() const {
1214 return !GetInstructions().IsEmpty() && GetLastInstruction()->IsTryBoundary();
1215}
1216
David Brazdilb2bd1c52015-03-25 11:17:37 +00001217bool HBasicBlock::HasSinglePhi() const {
1218 return !GetPhis().IsEmpty() && GetFirstPhi()->GetNext() == nullptr;
1219}
1220
David Brazdilffee3d32015-07-06 11:48:53 +01001221bool HTryBoundary::HasSameExceptionHandlersAs(const HTryBoundary& other) const {
Vladimir Marko60584552015-09-03 13:35:12 +00001222 if (GetBlock()->GetSuccessors().size() != other.GetBlock()->GetSuccessors().size()) {
David Brazdilffee3d32015-07-06 11:48:53 +01001223 return false;
1224 }
1225
David Brazdilb618ade2015-07-29 10:31:29 +01001226 // Exception handlers need to be stored in the same order.
1227 for (HExceptionHandlerIterator it1(*this), it2(other);
1228 !it1.Done();
1229 it1.Advance(), it2.Advance()) {
1230 DCHECK(!it2.Done());
1231 if (it1.Current() != it2.Current()) {
David Brazdilffee3d32015-07-06 11:48:53 +01001232 return false;
1233 }
1234 }
1235 return true;
1236}
1237
David Brazdil2d7352b2015-04-20 14:52:42 +01001238size_t HInstructionList::CountSize() const {
1239 size_t size = 0;
1240 HInstruction* current = first_instruction_;
1241 for (; current != nullptr; current = current->GetNext()) {
1242 size++;
1243 }
1244 return size;
1245}
1246
Nicolas Geoffray276d9da2015-02-02 18:24:11 +00001247void HInstructionList::SetBlockOfInstructions(HBasicBlock* block) const {
1248 for (HInstruction* current = first_instruction_;
1249 current != nullptr;
1250 current = current->GetNext()) {
1251 current->SetBlock(block);
1252 }
1253}
1254
1255void HInstructionList::AddAfter(HInstruction* cursor, const HInstructionList& instruction_list) {
1256 DCHECK(Contains(cursor));
1257 if (!instruction_list.IsEmpty()) {
1258 if (cursor == last_instruction_) {
1259 last_instruction_ = instruction_list.last_instruction_;
1260 } else {
1261 cursor->next_->previous_ = instruction_list.last_instruction_;
1262 }
1263 instruction_list.last_instruction_->next_ = cursor->next_;
1264 cursor->next_ = instruction_list.first_instruction_;
1265 instruction_list.first_instruction_->previous_ = cursor;
1266 }
1267}
1268
1269void HInstructionList::Add(const HInstructionList& instruction_list) {
David Brazdil46e2a392015-03-16 17:31:52 +00001270 if (IsEmpty()) {
1271 first_instruction_ = instruction_list.first_instruction_;
1272 last_instruction_ = instruction_list.last_instruction_;
1273 } else {
1274 AddAfter(last_instruction_, instruction_list);
1275 }
1276}
1277
David Brazdil2d7352b2015-04-20 14:52:42 +01001278void HBasicBlock::DisconnectAndDelete() {
1279 // Dominators must be removed after all the blocks they dominate. This way
1280 // a loop header is removed last, a requirement for correct loop information
1281 // iteration.
Vladimir Marko60584552015-09-03 13:35:12 +00001282 DCHECK(dominated_blocks_.empty());
David Brazdil46e2a392015-03-16 17:31:52 +00001283
David Brazdil2d7352b2015-04-20 14:52:42 +01001284 // Remove the block from all loops it is included in.
1285 for (HLoopInformationOutwardIterator it(*this); !it.Done(); it.Advance()) {
1286 HLoopInformation* loop_info = it.Current();
1287 loop_info->Remove(this);
1288 if (loop_info->IsBackEdge(*this)) {
Nicolas Geoffraydb216f42015-05-05 17:02:20 +01001289 // If this was the last back edge of the loop, we deliberately leave the
1290 // loop in an inconsistent state and will fail SSAChecker unless the
1291 // entire loop is removed during the pass.
David Brazdil2d7352b2015-04-20 14:52:42 +01001292 loop_info->RemoveBackEdge(this);
1293 }
1294 }
1295
1296 // Disconnect the block from its predecessors and update their control-flow
1297 // instructions.
Vladimir Marko60584552015-09-03 13:35:12 +00001298 for (HBasicBlock* predecessor : predecessors_) {
David Brazdil2d7352b2015-04-20 14:52:42 +01001299 HInstruction* last_instruction = predecessor->GetLastInstruction();
David Brazdil2d7352b2015-04-20 14:52:42 +01001300 predecessor->RemoveSuccessor(this);
Mark Mendellfe57faa2015-09-18 09:26:15 -04001301 uint32_t num_pred_successors = predecessor->GetSuccessors().size();
1302 if (num_pred_successors == 1u) {
1303 // If we have one successor after removing one, then we must have
1304 // had an HIf or HPackedSwitch, as they have more than one successor.
1305 // Replace those with a HGoto.
1306 DCHECK(last_instruction->IsIf() || last_instruction->IsPackedSwitch());
1307 predecessor->RemoveInstruction(last_instruction);
Yevgeny Rouban3ecfd652015-09-07 17:57:00 +06001308 predecessor->AddInstruction(new (graph_->GetArena()) HGoto(last_instruction->GetDexPc()));
Mark Mendellfe57faa2015-09-18 09:26:15 -04001309 } else if (num_pred_successors == 0u) {
David Brazdil2d7352b2015-04-20 14:52:42 +01001310 // The predecessor has no remaining successors and therefore must be dead.
1311 // We deliberately leave it without a control-flow instruction so that the
1312 // SSAChecker fails unless it is not removed during the pass too.
Mark Mendellfe57faa2015-09-18 09:26:15 -04001313 predecessor->RemoveInstruction(last_instruction);
1314 } else {
1315 // There are multiple successors left. This must come from a HPackedSwitch
1316 // and we are in the middle of removing the HPackedSwitch. Like above, leave
1317 // this alone, and the SSAChecker will fail if it is not removed as well.
1318 DCHECK(last_instruction->IsPackedSwitch());
David Brazdil2d7352b2015-04-20 14:52:42 +01001319 }
David Brazdil46e2a392015-03-16 17:31:52 +00001320 }
Vladimir Marko60584552015-09-03 13:35:12 +00001321 predecessors_.clear();
David Brazdil2d7352b2015-04-20 14:52:42 +01001322
Nicolas Geoffray1f82ecc2015-06-24 12:20:24 +01001323 // Disconnect the block from its successors and update their phis.
Vladimir Marko60584552015-09-03 13:35:12 +00001324 for (HBasicBlock* successor : successors_) {
David Brazdil2d7352b2015-04-20 14:52:42 +01001325 // Delete this block from the list of predecessors.
1326 size_t this_index = successor->GetPredecessorIndexOf(this);
Vladimir Marko60584552015-09-03 13:35:12 +00001327 successor->predecessors_.erase(successor->predecessors_.begin() + this_index);
David Brazdil2d7352b2015-04-20 14:52:42 +01001328
1329 // Check that `successor` has other predecessors, otherwise `this` is the
1330 // dominator of `successor` which violates the order DCHECKed at the top.
Vladimir Marko60584552015-09-03 13:35:12 +00001331 DCHECK(!successor->predecessors_.empty());
David Brazdil2d7352b2015-04-20 14:52:42 +01001332
David Brazdil2d7352b2015-04-20 14:52:42 +01001333 // Remove this block's entries in the successor's phis.
Vladimir Marko60584552015-09-03 13:35:12 +00001334 if (successor->predecessors_.size() == 1u) {
David Brazdil2d7352b2015-04-20 14:52:42 +01001335 // The successor has just one predecessor left. Replace phis with the only
1336 // remaining input.
1337 for (HInstructionIterator phi_it(successor->GetPhis()); !phi_it.Done(); phi_it.Advance()) {
1338 HPhi* phi = phi_it.Current()->AsPhi();
1339 phi->ReplaceWith(phi->InputAt(1 - this_index));
1340 successor->RemovePhi(phi);
1341 }
1342 } else {
1343 for (HInstructionIterator phi_it(successor->GetPhis()); !phi_it.Done(); phi_it.Advance()) {
1344 phi_it.Current()->AsPhi()->RemoveInputAt(this_index);
1345 }
1346 }
1347 }
Vladimir Marko60584552015-09-03 13:35:12 +00001348 successors_.clear();
David Brazdil2d7352b2015-04-20 14:52:42 +01001349
1350 // Disconnect from the dominator.
1351 dominator_->RemoveDominatedBlock(this);
1352 SetDominator(nullptr);
1353
1354 // Delete from the graph. The function safely deletes remaining instructions
1355 // and updates the reverse post order.
1356 graph_->DeleteDeadBlock(this);
1357 SetGraph(nullptr);
Nicolas Geoffray276d9da2015-02-02 18:24:11 +00001358}
1359
1360void HBasicBlock::MergeWith(HBasicBlock* other) {
David Brazdil2d7352b2015-04-20 14:52:42 +01001361 DCHECK_EQ(GetGraph(), other->GetGraph());
Vladimir Marko60584552015-09-03 13:35:12 +00001362 DCHECK(ContainsElement(dominated_blocks_, other));
1363 DCHECK_EQ(GetSingleSuccessor(), other);
1364 DCHECK_EQ(other->GetSinglePredecessor(), this);
Nicolas Geoffray276d9da2015-02-02 18:24:11 +00001365 DCHECK(other->GetPhis().IsEmpty());
1366
David Brazdil2d7352b2015-04-20 14:52:42 +01001367 // Move instructions from `other` to `this`.
1368 DCHECK(EndsWithControlFlowInstruction());
1369 RemoveInstruction(GetLastInstruction());
Nicolas Geoffray276d9da2015-02-02 18:24:11 +00001370 instructions_.Add(other->GetInstructions());
David Brazdil2d7352b2015-04-20 14:52:42 +01001371 other->instructions_.SetBlockOfInstructions(this);
1372 other->instructions_.Clear();
Nicolas Geoffray276d9da2015-02-02 18:24:11 +00001373
David Brazdil2d7352b2015-04-20 14:52:42 +01001374 // Remove `other` from the loops it is included in.
1375 for (HLoopInformationOutwardIterator it(*other); !it.Done(); it.Advance()) {
1376 HLoopInformation* loop_info = it.Current();
1377 loop_info->Remove(other);
1378 if (loop_info->IsBackEdge(*other)) {
Nicolas Geoffraydb216f42015-05-05 17:02:20 +01001379 loop_info->ReplaceBackEdge(other, this);
David Brazdil2d7352b2015-04-20 14:52:42 +01001380 }
1381 }
1382
1383 // Update links to the successors of `other`.
Vladimir Marko60584552015-09-03 13:35:12 +00001384 successors_.clear();
1385 while (!other->successors_.empty()) {
1386 HBasicBlock* successor = other->GetSuccessor(0);
Nicolas Geoffray276d9da2015-02-02 18:24:11 +00001387 successor->ReplacePredecessor(other, this);
1388 }
1389
David Brazdil2d7352b2015-04-20 14:52:42 +01001390 // Update the dominator tree.
Vladimir Marko60584552015-09-03 13:35:12 +00001391 RemoveDominatedBlock(other);
1392 for (HBasicBlock* dominated : other->GetDominatedBlocks()) {
1393 dominated_blocks_.push_back(dominated);
David Brazdil2d7352b2015-04-20 14:52:42 +01001394 dominated->SetDominator(this);
1395 }
Vladimir Marko60584552015-09-03 13:35:12 +00001396 other->dominated_blocks_.clear();
David Brazdil2d7352b2015-04-20 14:52:42 +01001397 other->dominator_ = nullptr;
1398
1399 // Clear the list of predecessors of `other` in preparation of deleting it.
Vladimir Marko60584552015-09-03 13:35:12 +00001400 other->predecessors_.clear();
David Brazdil2d7352b2015-04-20 14:52:42 +01001401
1402 // Delete `other` from the graph. The function updates reverse post order.
1403 graph_->DeleteDeadBlock(other);
1404 other->SetGraph(nullptr);
1405}
1406
1407void HBasicBlock::MergeWithInlined(HBasicBlock* other) {
1408 DCHECK_NE(GetGraph(), other->GetGraph());
Vladimir Marko60584552015-09-03 13:35:12 +00001409 DCHECK(GetDominatedBlocks().empty());
1410 DCHECK(GetSuccessors().empty());
David Brazdil2d7352b2015-04-20 14:52:42 +01001411 DCHECK(!EndsWithControlFlowInstruction());
Vladimir Marko60584552015-09-03 13:35:12 +00001412 DCHECK(other->GetSinglePredecessor()->IsEntryBlock());
David Brazdil2d7352b2015-04-20 14:52:42 +01001413 DCHECK(other->GetPhis().IsEmpty());
1414 DCHECK(!other->IsInLoop());
1415
1416 // Move instructions from `other` to `this`.
1417 instructions_.Add(other->GetInstructions());
1418 other->instructions_.SetBlockOfInstructions(this);
1419
1420 // Update links to the successors of `other`.
Vladimir Marko60584552015-09-03 13:35:12 +00001421 successors_.clear();
1422 while (!other->successors_.empty()) {
1423 HBasicBlock* successor = other->GetSuccessor(0);
David Brazdil2d7352b2015-04-20 14:52:42 +01001424 successor->ReplacePredecessor(other, this);
1425 }
1426
1427 // Update the dominator tree.
Vladimir Marko60584552015-09-03 13:35:12 +00001428 for (HBasicBlock* dominated : other->GetDominatedBlocks()) {
1429 dominated_blocks_.push_back(dominated);
Nicolas Geoffray276d9da2015-02-02 18:24:11 +00001430 dominated->SetDominator(this);
1431 }
Vladimir Marko60584552015-09-03 13:35:12 +00001432 other->dominated_blocks_.clear();
Nicolas Geoffray276d9da2015-02-02 18:24:11 +00001433 other->dominator_ = nullptr;
1434 other->graph_ = nullptr;
1435}
1436
1437void HBasicBlock::ReplaceWith(HBasicBlock* other) {
Vladimir Marko60584552015-09-03 13:35:12 +00001438 while (!GetPredecessors().empty()) {
1439 HBasicBlock* predecessor = GetPredecessor(0);
Nicolas Geoffray276d9da2015-02-02 18:24:11 +00001440 predecessor->ReplaceSuccessor(this, other);
1441 }
Vladimir Marko60584552015-09-03 13:35:12 +00001442 while (!GetSuccessors().empty()) {
1443 HBasicBlock* successor = GetSuccessor(0);
Nicolas Geoffray276d9da2015-02-02 18:24:11 +00001444 successor->ReplacePredecessor(this, other);
1445 }
Vladimir Marko60584552015-09-03 13:35:12 +00001446 for (HBasicBlock* dominated : GetDominatedBlocks()) {
1447 other->AddDominatedBlock(dominated);
Nicolas Geoffray276d9da2015-02-02 18:24:11 +00001448 }
1449 GetDominator()->ReplaceDominatedBlock(this, other);
1450 other->SetDominator(GetDominator());
1451 dominator_ = nullptr;
1452 graph_ = nullptr;
1453}
1454
1455// Create space in `blocks` for adding `number_of_new_blocks` entries
1456// starting at location `at`. Blocks after `at` are moved accordingly.
Vladimir Markofa6b93c2015-09-15 10:15:55 +01001457static void MakeRoomFor(ArenaVector<HBasicBlock*>* blocks,
Nicolas Geoffray276d9da2015-02-02 18:24:11 +00001458 size_t number_of_new_blocks,
Vladimir Markofa6b93c2015-09-15 10:15:55 +01001459 size_t after) {
1460 DCHECK_LT(after, blocks->size());
1461 size_t old_size = blocks->size();
Nicolas Geoffray276d9da2015-02-02 18:24:11 +00001462 size_t new_size = old_size + number_of_new_blocks;
Vladimir Markofa6b93c2015-09-15 10:15:55 +01001463 blocks->resize(new_size);
1464 std::copy_backward(blocks->begin() + after + 1u, blocks->begin() + old_size, blocks->end());
Nicolas Geoffray276d9da2015-02-02 18:24:11 +00001465}
1466
David Brazdil2d7352b2015-04-20 14:52:42 +01001467void HGraph::DeleteDeadBlock(HBasicBlock* block) {
1468 DCHECK_EQ(block->GetGraph(), this);
Vladimir Marko60584552015-09-03 13:35:12 +00001469 DCHECK(block->GetSuccessors().empty());
1470 DCHECK(block->GetPredecessors().empty());
1471 DCHECK(block->GetDominatedBlocks().empty());
David Brazdil2d7352b2015-04-20 14:52:42 +01001472 DCHECK(block->GetDominator() == nullptr);
1473
1474 for (HBackwardInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
1475 block->RemoveInstruction(it.Current());
1476 }
1477 for (HBackwardInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
1478 block->RemovePhi(it.Current()->AsPhi());
1479 }
1480
David Brazdilc7af85d2015-05-26 12:05:55 +01001481 if (block->IsExitBlock()) {
1482 exit_block_ = nullptr;
1483 }
1484
Vladimir Markofa6b93c2015-09-15 10:15:55 +01001485 RemoveElement(reverse_post_order_, block);
1486 blocks_[block->GetBlockId()] = nullptr;
David Brazdil2d7352b2015-04-20 14:52:42 +01001487}
1488
Calin Juravle2e768302015-07-28 14:41:11 +00001489HInstruction* HGraph::InlineInto(HGraph* outer_graph, HInvoke* invoke) {
David Brazdilc7af85d2015-05-26 12:05:55 +01001490 DCHECK(HasExitBlock()) << "Unimplemented scenario";
Nicolas Geoffrayd23eeef2015-05-18 22:31:29 +01001491 // Update the environments in this graph to have the invoke's environment
1492 // as parent.
1493 {
1494 HReversePostOrderIterator it(*this);
1495 it.Advance(); // Skip the entry block, we do not need to update the entry's suspend check.
1496 for (; !it.Done(); it.Advance()) {
1497 HBasicBlock* block = it.Current();
1498 for (HInstructionIterator instr_it(block->GetInstructions());
1499 !instr_it.Done();
1500 instr_it.Advance()) {
1501 HInstruction* current = instr_it.Current();
1502 if (current->NeedsEnvironment()) {
1503 current->GetEnvironment()->SetAndCopyParentChain(
1504 outer_graph->GetArena(), invoke->GetEnvironment());
1505 }
1506 }
1507 }
1508 }
1509 outer_graph->UpdateMaximumNumberOfOutVRegs(GetMaximumNumberOfOutVRegs());
1510 if (HasBoundsChecks()) {
1511 outer_graph->SetHasBoundsChecks(true);
1512 }
1513
Calin Juravle2e768302015-07-28 14:41:11 +00001514 HInstruction* return_value = nullptr;
Vladimir Markofa6b93c2015-09-15 10:15:55 +01001515 if (GetBlocks().size() == 3) {
Nicolas Geoffraybe31ff92015-02-04 14:52:20 +00001516 // Simple case of an entry block, a body block, and an exit block.
1517 // Put the body block's instruction into `invoke`'s block.
Vladimir Markofa6b93c2015-09-15 10:15:55 +01001518 HBasicBlock* body = GetBlock(1);
1519 DCHECK(GetBlock(0)->IsEntryBlock());
1520 DCHECK(GetBlock(2)->IsExitBlock());
Nicolas Geoffray276d9da2015-02-02 18:24:11 +00001521 DCHECK(!body->IsExitBlock());
1522 HInstruction* last = body->GetLastInstruction();
Nicolas Geoffraye53798a2014-12-01 10:31:54 +00001523
Nicolas Geoffray276d9da2015-02-02 18:24:11 +00001524 invoke->GetBlock()->instructions_.AddAfter(invoke, body->GetInstructions());
1525 body->GetInstructions().SetBlockOfInstructions(invoke->GetBlock());
Nicolas Geoffraye53798a2014-12-01 10:31:54 +00001526
Nicolas Geoffray276d9da2015-02-02 18:24:11 +00001527 // Replace the invoke with the return value of the inlined graph.
1528 if (last->IsReturn()) {
Calin Juravle2e768302015-07-28 14:41:11 +00001529 return_value = last->InputAt(0);
1530 invoke->ReplaceWith(return_value);
Nicolas Geoffray276d9da2015-02-02 18:24:11 +00001531 } else {
1532 DCHECK(last->IsReturnVoid());
Nicolas Geoffraye53798a2014-12-01 10:31:54 +00001533 }
Nicolas Geoffraye53798a2014-12-01 10:31:54 +00001534
Nicolas Geoffray276d9da2015-02-02 18:24:11 +00001535 invoke->GetBlock()->RemoveInstruction(last);
Nicolas Geoffraye53798a2014-12-01 10:31:54 +00001536 } else {
Nicolas Geoffray276d9da2015-02-02 18:24:11 +00001537 // Need to inline multiple blocks. We split `invoke`'s block
1538 // into two blocks, merge the first block of the inlined graph into
Nicolas Geoffraybe31ff92015-02-04 14:52:20 +00001539 // the first half, and replace the exit block of the inlined graph
Nicolas Geoffray276d9da2015-02-02 18:24:11 +00001540 // with the second half.
1541 ArenaAllocator* allocator = outer_graph->GetArena();
1542 HBasicBlock* at = invoke->GetBlock();
1543 HBasicBlock* to = at->SplitAfter(invoke);
1544
Vladimir Marko60584552015-09-03 13:35:12 +00001545 HBasicBlock* first = entry_block_->GetSuccessor(0);
Nicolas Geoffray276d9da2015-02-02 18:24:11 +00001546 DCHECK(!first->IsInLoop());
David Brazdil2d7352b2015-04-20 14:52:42 +01001547 at->MergeWithInlined(first);
Nicolas Geoffray276d9da2015-02-02 18:24:11 +00001548 exit_block_->ReplaceWith(to);
1549
1550 // Update all predecessors of the exit block (now the `to` block)
Nicolas Geoffray817bce72015-02-24 13:35:38 +00001551 // to not `HReturn` but `HGoto` instead.
Vladimir Marko60584552015-09-03 13:35:12 +00001552 bool returns_void = to->GetPredecessor(0)->GetLastInstruction()->IsReturnVoid();
1553 if (to->GetPredecessors().size() == 1) {
1554 HBasicBlock* predecessor = to->GetPredecessor(0);
Nicolas Geoffray276d9da2015-02-02 18:24:11 +00001555 HInstruction* last = predecessor->GetLastInstruction();
Nicolas Geoffray817bce72015-02-24 13:35:38 +00001556 if (!returns_void) {
1557 return_value = last->InputAt(0);
Nicolas Geoffray276d9da2015-02-02 18:24:11 +00001558 }
Yevgeny Rouban3ecfd652015-09-07 17:57:00 +06001559 predecessor->AddInstruction(new (allocator) HGoto(last->GetDexPc()));
Nicolas Geoffray276d9da2015-02-02 18:24:11 +00001560 predecessor->RemoveInstruction(last);
Nicolas Geoffray817bce72015-02-24 13:35:38 +00001561 } else {
1562 if (!returns_void) {
1563 // There will be multiple returns.
Nicolas Geoffray4f1a3842015-03-12 10:34:11 +00001564 return_value = new (allocator) HPhi(
Yevgeny Rouban3ecfd652015-09-07 17:57:00 +06001565 allocator, kNoRegNumber, 0, HPhi::ToPhiType(invoke->GetType()), to->GetDexPc());
Nicolas Geoffray817bce72015-02-24 13:35:38 +00001566 to->AddPhi(return_value->AsPhi());
1567 }
Vladimir Marko60584552015-09-03 13:35:12 +00001568 for (HBasicBlock* predecessor : to->GetPredecessors()) {
Nicolas Geoffray817bce72015-02-24 13:35:38 +00001569 HInstruction* last = predecessor->GetLastInstruction();
1570 if (!returns_void) {
1571 return_value->AsPhi()->AddInput(last->InputAt(0));
1572 }
Yevgeny Rouban3ecfd652015-09-07 17:57:00 +06001573 predecessor->AddInstruction(new (allocator) HGoto(last->GetDexPc()));
Nicolas Geoffray817bce72015-02-24 13:35:38 +00001574 predecessor->RemoveInstruction(last);
1575 }
Nicolas Geoffray276d9da2015-02-02 18:24:11 +00001576 }
1577
1578 if (return_value != nullptr) {
1579 invoke->ReplaceWith(return_value);
1580 }
1581
1582 // Update the meta information surrounding blocks:
1583 // (1) the graph they are now in,
1584 // (2) the reverse post order of that graph,
1585 // (3) the potential loop information they are now in.
1586
1587 // We don't add the entry block, the exit block, and the first block, which
1588 // has been merged with `at`.
1589 static constexpr int kNumberOfSkippedBlocksInCallee = 3;
1590
1591 // We add the `to` block.
1592 static constexpr int kNumberOfNewBlocksInCaller = 1;
Vladimir Markofa6b93c2015-09-15 10:15:55 +01001593 size_t blocks_added = (reverse_post_order_.size() - kNumberOfSkippedBlocksInCallee)
Nicolas Geoffray276d9da2015-02-02 18:24:11 +00001594 + kNumberOfNewBlocksInCaller;
1595
1596 // Find the location of `at` in the outer graph's reverse post order. The new
1597 // blocks will be added after it.
Vladimir Markofa6b93c2015-09-15 10:15:55 +01001598 size_t index_of_at = IndexOfElement(outer_graph->reverse_post_order_, at);
Nicolas Geoffray276d9da2015-02-02 18:24:11 +00001599 MakeRoomFor(&outer_graph->reverse_post_order_, blocks_added, index_of_at);
1600
1601 // Do a reverse post order of the blocks in the callee and do (1), (2),
1602 // and (3) to the blocks that apply.
1603 HLoopInformation* info = at->GetLoopInformation();
1604 for (HReversePostOrderIterator it(*this); !it.Done(); it.Advance()) {
1605 HBasicBlock* current = it.Current();
1606 if (current != exit_block_ && current != entry_block_ && current != first) {
1607 DCHECK(!current->IsInLoop());
1608 DCHECK(current->GetGraph() == this);
1609 current->SetGraph(outer_graph);
1610 outer_graph->AddBlock(current);
Vladimir Markofa6b93c2015-09-15 10:15:55 +01001611 outer_graph->reverse_post_order_[++index_of_at] = current;
Nicolas Geoffray276d9da2015-02-02 18:24:11 +00001612 if (info != nullptr) {
Nicolas Geoffray276d9da2015-02-02 18:24:11 +00001613 current->SetLoopInformation(info);
David Brazdil7d275372015-04-21 16:36:35 +01001614 for (HLoopInformationOutwardIterator loop_it(*at); !loop_it.Done(); loop_it.Advance()) {
1615 loop_it.Current()->Add(current);
1616 }
Nicolas Geoffray276d9da2015-02-02 18:24:11 +00001617 }
1618 }
1619 }
1620
1621 // Do (1), (2), and (3) to `to`.
1622 to->SetGraph(outer_graph);
1623 outer_graph->AddBlock(to);
Vladimir Markofa6b93c2015-09-15 10:15:55 +01001624 outer_graph->reverse_post_order_[++index_of_at] = to;
Nicolas Geoffray276d9da2015-02-02 18:24:11 +00001625 if (info != nullptr) {
Nicolas Geoffray276d9da2015-02-02 18:24:11 +00001626 to->SetLoopInformation(info);
David Brazdil7d275372015-04-21 16:36:35 +01001627 for (HLoopInformationOutwardIterator loop_it(*at); !loop_it.Done(); loop_it.Advance()) {
1628 loop_it.Current()->Add(to);
1629 }
David Brazdil46e2a392015-03-16 17:31:52 +00001630 if (info->IsBackEdge(*at)) {
Nicolas Geoffraydb216f42015-05-05 17:02:20 +01001631 // Only `to` can become a back edge, as the inlined blocks
1632 // are predecessors of `to`.
1633 info->ReplaceBackEdge(at, to);
Nicolas Geoffray276d9da2015-02-02 18:24:11 +00001634 }
1635 }
Nicolas Geoffraye53798a2014-12-01 10:31:54 +00001636 }
Nicolas Geoffray7c5367b2014-12-17 10:13:46 +00001637
David Brazdil05144f42015-04-16 15:18:00 +01001638 // Update the next instruction id of the outer graph, so that instructions
1639 // added later get bigger ids than those in the inner graph.
1640 outer_graph->SetCurrentInstructionId(GetNextInstructionId());
1641
1642 // Walk over the entry block and:
1643 // - Move constants from the entry block to the outer_graph's entry block,
1644 // - Replace HParameterValue instructions with their real value.
1645 // - Remove suspend checks, that hold an environment.
1646 // We must do this after the other blocks have been inlined, otherwise ids of
1647 // constants could overlap with the inner graph.
Roland Levillain4c0eb422015-04-24 16:43:49 +01001648 size_t parameter_index = 0;
David Brazdil05144f42015-04-16 15:18:00 +01001649 for (HInstructionIterator it(entry_block_->GetInstructions()); !it.Done(); it.Advance()) {
1650 HInstruction* current = it.Current();
1651 if (current->IsNullConstant()) {
Yevgeny Rouban3ecfd652015-09-07 17:57:00 +06001652 current->ReplaceWith(outer_graph->GetNullConstant(current->GetDexPc()));
David Brazdil05144f42015-04-16 15:18:00 +01001653 } else if (current->IsIntConstant()) {
Yevgeny Rouban3ecfd652015-09-07 17:57:00 +06001654 current->ReplaceWith(outer_graph->GetIntConstant(
1655 current->AsIntConstant()->GetValue(), current->GetDexPc()));
David Brazdil05144f42015-04-16 15:18:00 +01001656 } else if (current->IsLongConstant()) {
Yevgeny Rouban3ecfd652015-09-07 17:57:00 +06001657 current->ReplaceWith(outer_graph->GetLongConstant(
1658 current->AsLongConstant()->GetValue(), current->GetDexPc()));
Nicolas Geoffrayf213e052015-04-27 08:53:46 +00001659 } else if (current->IsFloatConstant()) {
Yevgeny Rouban3ecfd652015-09-07 17:57:00 +06001660 current->ReplaceWith(outer_graph->GetFloatConstant(
1661 current->AsFloatConstant()->GetValue(), current->GetDexPc()));
Nicolas Geoffrayf213e052015-04-27 08:53:46 +00001662 } else if (current->IsDoubleConstant()) {
Yevgeny Rouban3ecfd652015-09-07 17:57:00 +06001663 current->ReplaceWith(outer_graph->GetDoubleConstant(
1664 current->AsDoubleConstant()->GetValue(), current->GetDexPc()));
David Brazdil05144f42015-04-16 15:18:00 +01001665 } else if (current->IsParameterValue()) {
Roland Levillain4c0eb422015-04-24 16:43:49 +01001666 if (kIsDebugBuild
1667 && invoke->IsInvokeStaticOrDirect()
1668 && invoke->AsInvokeStaticOrDirect()->IsStaticWithExplicitClinitCheck()) {
1669 // Ensure we do not use the last input of `invoke`, as it
1670 // contains a clinit check which is not an actual argument.
1671 size_t last_input_index = invoke->InputCount() - 1;
1672 DCHECK(parameter_index != last_input_index);
1673 }
David Brazdil05144f42015-04-16 15:18:00 +01001674 current->ReplaceWith(invoke->InputAt(parameter_index++));
Nicolas Geoffray76b1e172015-05-27 17:18:33 +01001675 } else if (current->IsCurrentMethod()) {
1676 current->ReplaceWith(outer_graph->GetCurrentMethod());
David Brazdil05144f42015-04-16 15:18:00 +01001677 } else {
1678 DCHECK(current->IsGoto() || current->IsSuspendCheck());
1679 entry_block_->RemoveInstruction(current);
1680 }
1681 }
1682
Nicolas Geoffray7c5367b2014-12-17 10:13:46 +00001683 // Finally remove the invoke from the caller.
1684 invoke->GetBlock()->RemoveInstruction(invoke);
Calin Juravle2e768302015-07-28 14:41:11 +00001685
1686 return return_value;
Nicolas Geoffraye53798a2014-12-01 10:31:54 +00001687}
1688
Mingyao Yang3584bce2015-05-19 16:01:59 -07001689/*
1690 * Loop will be transformed to:
1691 * old_pre_header
1692 * |
1693 * if_block
1694 * / \
1695 * dummy_block deopt_block
1696 * \ /
1697 * new_pre_header
1698 * |
1699 * header
1700 */
1701void HGraph::TransformLoopHeaderForBCE(HBasicBlock* header) {
1702 DCHECK(header->IsLoopHeader());
1703 HBasicBlock* pre_header = header->GetDominator();
1704
1705 // Need this to avoid critical edge.
1706 HBasicBlock* if_block = new (arena_) HBasicBlock(this, header->GetDexPc());
1707 // Need this to avoid critical edge.
1708 HBasicBlock* dummy_block = new (arena_) HBasicBlock(this, header->GetDexPc());
1709 HBasicBlock* deopt_block = new (arena_) HBasicBlock(this, header->GetDexPc());
1710 HBasicBlock* new_pre_header = new (arena_) HBasicBlock(this, header->GetDexPc());
1711 AddBlock(if_block);
1712 AddBlock(dummy_block);
1713 AddBlock(deopt_block);
1714 AddBlock(new_pre_header);
1715
1716 header->ReplacePredecessor(pre_header, new_pre_header);
Vladimir Marko60584552015-09-03 13:35:12 +00001717 pre_header->successors_.clear();
1718 pre_header->dominated_blocks_.clear();
Mingyao Yang3584bce2015-05-19 16:01:59 -07001719
1720 pre_header->AddSuccessor(if_block);
1721 if_block->AddSuccessor(dummy_block); // True successor
1722 if_block->AddSuccessor(deopt_block); // False successor
1723 dummy_block->AddSuccessor(new_pre_header);
1724 deopt_block->AddSuccessor(new_pre_header);
1725
Vladimir Marko60584552015-09-03 13:35:12 +00001726 pre_header->dominated_blocks_.push_back(if_block);
Mingyao Yang3584bce2015-05-19 16:01:59 -07001727 if_block->SetDominator(pre_header);
Vladimir Marko60584552015-09-03 13:35:12 +00001728 if_block->dominated_blocks_.push_back(dummy_block);
Mingyao Yang3584bce2015-05-19 16:01:59 -07001729 dummy_block->SetDominator(if_block);
Vladimir Marko60584552015-09-03 13:35:12 +00001730 if_block->dominated_blocks_.push_back(deopt_block);
Mingyao Yang3584bce2015-05-19 16:01:59 -07001731 deopt_block->SetDominator(if_block);
Vladimir Marko60584552015-09-03 13:35:12 +00001732 if_block->dominated_blocks_.push_back(new_pre_header);
Mingyao Yang3584bce2015-05-19 16:01:59 -07001733 new_pre_header->SetDominator(if_block);
Vladimir Marko60584552015-09-03 13:35:12 +00001734 new_pre_header->dominated_blocks_.push_back(header);
Mingyao Yang3584bce2015-05-19 16:01:59 -07001735 header->SetDominator(new_pre_header);
1736
Vladimir Markofa6b93c2015-09-15 10:15:55 +01001737 size_t index_of_header = IndexOfElement(reverse_post_order_, header);
Mingyao Yang3584bce2015-05-19 16:01:59 -07001738 MakeRoomFor(&reverse_post_order_, 4, index_of_header - 1);
Vladimir Markofa6b93c2015-09-15 10:15:55 +01001739 reverse_post_order_[index_of_header++] = if_block;
1740 reverse_post_order_[index_of_header++] = dummy_block;
1741 reverse_post_order_[index_of_header++] = deopt_block;
1742 reverse_post_order_[index_of_header++] = new_pre_header;
Mingyao Yang3584bce2015-05-19 16:01:59 -07001743
1744 HLoopInformation* info = pre_header->GetLoopInformation();
1745 if (info != nullptr) {
1746 if_block->SetLoopInformation(info);
1747 dummy_block->SetLoopInformation(info);
1748 deopt_block->SetLoopInformation(info);
1749 new_pre_header->SetLoopInformation(info);
1750 for (HLoopInformationOutwardIterator loop_it(*pre_header);
1751 !loop_it.Done();
1752 loop_it.Advance()) {
1753 loop_it.Current()->Add(if_block);
1754 loop_it.Current()->Add(dummy_block);
1755 loop_it.Current()->Add(deopt_block);
1756 loop_it.Current()->Add(new_pre_header);
1757 }
1758 }
1759}
1760
Calin Juravle2e768302015-07-28 14:41:11 +00001761void HInstruction::SetReferenceTypeInfo(ReferenceTypeInfo rti) {
1762 if (kIsDebugBuild) {
1763 DCHECK_EQ(GetType(), Primitive::kPrimNot);
1764 ScopedObjectAccess soa(Thread::Current());
1765 DCHECK(rti.IsValid()) << "Invalid RTI for " << DebugName();
1766 if (IsBoundType()) {
1767 // Having the test here spares us from making the method virtual just for
1768 // the sake of a DCHECK.
1769 ReferenceTypeInfo upper_bound_rti = AsBoundType()->GetUpperBound();
1770 DCHECK(upper_bound_rti.IsSupertypeOf(rti))
1771 << " upper_bound_rti: " << upper_bound_rti
1772 << " rti: " << rti;
David Brazdilbaf89b82015-09-15 11:36:54 +01001773 DCHECK(!upper_bound_rti.GetTypeHandle()->CannotBeAssignedFromOtherTypes() || rti.IsExact());
Calin Juravle2e768302015-07-28 14:41:11 +00001774 }
1775 }
1776 reference_type_info_ = rti;
1777}
1778
1779ReferenceTypeInfo::ReferenceTypeInfo() : type_handle_(TypeHandle()), is_exact_(false) {}
1780
1781ReferenceTypeInfo::ReferenceTypeInfo(TypeHandle type_handle, bool is_exact)
1782 : type_handle_(type_handle), is_exact_(is_exact) {
1783 if (kIsDebugBuild) {
1784 ScopedObjectAccess soa(Thread::Current());
1785 DCHECK(IsValidHandle(type_handle));
1786 }
1787}
1788
Calin Juravleacf735c2015-02-12 15:25:22 +00001789std::ostream& operator<<(std::ostream& os, const ReferenceTypeInfo& rhs) {
1790 ScopedObjectAccess soa(Thread::Current());
1791 os << "["
Calin Juravle2e768302015-07-28 14:41:11 +00001792 << " is_valid=" << rhs.IsValid()
1793 << " type=" << (!rhs.IsValid() ? "?" : PrettyClass(rhs.GetTypeHandle().Get()))
Calin Juravleacf735c2015-02-12 15:25:22 +00001794 << " is_exact=" << rhs.IsExact()
1795 << " ]";
1796 return os;
1797}
1798
Mark Mendellc4701932015-04-10 13:18:51 -04001799bool HInstruction::HasAnyEnvironmentUseBefore(HInstruction* other) {
1800 // For now, assume that instructions in different blocks may use the
1801 // environment.
1802 // TODO: Use the control flow to decide if this is true.
1803 if (GetBlock() != other->GetBlock()) {
1804 return true;
1805 }
1806
1807 // We know that we are in the same block. Walk from 'this' to 'other',
1808 // checking to see if there is any instruction with an environment.
1809 HInstruction* current = this;
1810 for (; current != other && current != nullptr; current = current->GetNext()) {
1811 // This is a conservative check, as the instruction result may not be in
1812 // the referenced environment.
1813 if (current->HasEnvironment()) {
1814 return true;
1815 }
1816 }
1817
1818 // We should have been called with 'this' before 'other' in the block.
1819 // Just confirm this.
1820 DCHECK(current != nullptr);
1821 return false;
1822}
1823
1824void HInstruction::RemoveEnvironmentUsers() {
1825 for (HUseIterator<HEnvironment*> use_it(GetEnvUses()); !use_it.Done(); use_it.Advance()) {
1826 HUseListNode<HEnvironment*>* user_node = use_it.Current();
1827 HEnvironment* user = user_node->GetUser();
1828 user->SetRawEnvAt(user_node->GetIndex(), nullptr);
1829 }
1830 env_uses_.Clear();
1831}
1832
Nicolas Geoffray818f2102014-02-18 16:43:35 +00001833} // namespace art