1/*
2 * Copyright (C) 2014 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16#include "nodes.h"
17
18#include <cfloat>
19
20#include "code_generator.h"
21#include "common_dominator.h"
22#include "ssa_builder.h"
23#include "base/bit_vector-inl.h"
24#include "base/bit_utils.h"
25#include "base/stl_util.h"
26#include "intrinsics.h"
27#include "mirror/class-inl.h"
28#include "scoped_thread_state_change.h"
29
30namespace art {
31
32// Enable floating-point static evaluation during constant folding
33// only if all floating-point operations and constants evaluate in the
34// range and precision of the type used (i.e., 32-bit float, 64-bit
35// double).
36static constexpr bool kEnableFloatingPointStaticEvaluation = (FLT_EVAL_METHOD == 0);
37
38void HGraph::InitializeInexactObjectRTI(StackHandleScopeCollection* handles) {
39  ScopedObjectAccess soa(Thread::Current());
40  // Create the inexact Object reference type and store it in the HGraph.
41  ClassLinker* linker = Runtime::Current()->GetClassLinker();
42  inexact_object_rti_ = ReferenceTypeInfo::Create(
43      handles->NewHandle(linker->GetClassRoot(ClassLinker::kJavaLangObject)),
44      /* is_exact */ false);
45}
46
47void HGraph::AddBlock(HBasicBlock* block) {
48  block->SetBlockId(blocks_.size());
49  blocks_.push_back(block);
50}
51
52void HGraph::FindBackEdges(ArenaBitVector* visited) {
53  // "visited" must be empty on entry, it's an output argument for all visited (i.e. live) blocks.
54  DCHECK_EQ(visited->GetHighestBitSet(), -1);
55
56  // Nodes that we're currently visiting, indexed by block id.
57  ArenaBitVector visiting(arena_, blocks_.size(), false, kArenaAllocGraphBuilder);
58  // Number of successors visited from a given node, indexed by block id.
59  ArenaVector<size_t> successors_visited(blocks_.size(),
60                                         0u,
61                                         arena_->Adapter(kArenaAllocGraphBuilder));
62  // Stack of nodes that we're currently visiting (same as marked in "visiting" above).
63  ArenaVector<HBasicBlock*> worklist(arena_->Adapter(kArenaAllocGraphBuilder));
64  constexpr size_t kDefaultWorklistSize = 8;
65  worklist.reserve(kDefaultWorklistSize);
66  visited->SetBit(entry_block_->GetBlockId());
67  visiting.SetBit(entry_block_->GetBlockId());
68  worklist.push_back(entry_block_);
69
70  while (!worklist.empty()) {
71    HBasicBlock* current = worklist.back();
72    uint32_t current_id = current->GetBlockId();
73    if (successors_visited[current_id] == current->GetSuccessors().size()) {
74      visiting.ClearBit(current_id);
75      worklist.pop_back();
76    } else {
77      HBasicBlock* successor = current->GetSuccessors()[successors_visited[current_id]++];
78      uint32_t successor_id = successor->GetBlockId();
79      if (visiting.IsBitSet(successor_id)) {
80        DCHECK(ContainsElement(worklist, successor));
81        successor->AddBackEdge(current);
82      } else if (!visited->IsBitSet(successor_id)) {
83        visited->SetBit(successor_id);
84        visiting.SetBit(successor_id);
85        worklist.push_back(successor);
86      }
87    }
88  }
89}
90
91static void RemoveEnvironmentUses(HInstruction* instruction) {
92  for (HEnvironment* environment = instruction->GetEnvironment();
93       environment != nullptr;
94       environment = environment->GetParent()) {
95    for (size_t i = 0, e = environment->Size(); i < e; ++i) {
96      if (environment->GetInstructionAt(i) != nullptr) {
97        environment->RemoveAsUserOfInput(i);
98      }
99    }
100  }
101}
102
103static void RemoveAsUser(HInstruction* instruction) {
104  for (size_t i = 0; i < instruction->InputCount(); i++) {
105    instruction->RemoveAsUserOfInput(i);
106  }
107
108  RemoveEnvironmentUses(instruction);
109}
110
111void HGraph::RemoveInstructionsAsUsersFromDeadBlocks(const ArenaBitVector& visited) const {
112  for (size_t i = 0; i < blocks_.size(); ++i) {
113    if (!visited.IsBitSet(i)) {
114      HBasicBlock* block = blocks_[i];
115      if (block == nullptr) continue;
116      DCHECK(block->GetPhis().IsEmpty()) << "Phis are not inserted at this stage";
117      for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
118        RemoveAsUser(it.Current());
119      }
120    }
121  }
122}
123
124void HGraph::RemoveDeadBlocks(const ArenaBitVector& visited) {
125  for (size_t i = 0; i < blocks_.size(); ++i) {
126    if (!visited.IsBitSet(i)) {
127      HBasicBlock* block = blocks_[i];
128      if (block == nullptr) continue;
129      // We only need to update the successor, which might be live.
130      for (HBasicBlock* successor : block->GetSuccessors()) {
131        successor->RemovePredecessor(block);
132      }
133      // Remove the block from the list of blocks, so that further analyses
134      // never see it.
135      blocks_[i] = nullptr;
136      if (block->IsExitBlock()) {
137        SetExitBlock(nullptr);
138      }
139      // Mark the block as removed. This is used by the HGraphBuilder to discard
140      // the block as a branch target.
141      block->SetGraph(nullptr);
142    }
143  }
144}
145
146GraphAnalysisResult HGraph::BuildDominatorTree() {
147  ArenaBitVector visited(arena_, blocks_.size(), false, kArenaAllocGraphBuilder);
148
149  // (1) Find the back edges in the graph doing a DFS traversal.
150  FindBackEdges(&visited);
151
152  // (2) Remove instructions and phis from blocks not visited during
153  //     the initial DFS as users from other instructions, so that
154  //     users can be safely removed before uses later.
155  RemoveInstructionsAsUsersFromDeadBlocks(visited);
156
157  // (3) Remove blocks not visited during the initial DFS.
158  //     Step (5) requires dead blocks to be removed from the
159  //     predecessors list of live blocks.
160  RemoveDeadBlocks(visited);
161
162  // (4) Simplify the CFG now, so that we don't need to recompute
163  //     dominators and the reverse post order.
164  SimplifyCFG();
165
166  // (5) Compute the dominance information and the reverse post order.
167  ComputeDominanceInformation();
168
169  // (6) Analyze loops discovered through back edge analysis, and
170  //     set the loop information on each block.
171  GraphAnalysisResult result = AnalyzeLoops();
172  if (result != kAnalysisSuccess) {
173    return result;
174  }
175
176  // (7) Precompute per-block try membership before entering the SSA builder,
177  //     which needs the information to build catch block phis from values of
178  //     locals at throwing instructions inside try blocks.
179  ComputeTryBlockInformation();
180
181  return kAnalysisSuccess;
182}
183
184void HGraph::ClearDominanceInformation() {
185  for (HReversePostOrderIterator it(*this); !it.Done(); it.Advance()) {
186    it.Current()->ClearDominanceInformation();
187  }
188  reverse_post_order_.clear();
189}
190
191void HGraph::ClearLoopInformation() {
192  SetHasIrreducibleLoops(false);
193  for (HReversePostOrderIterator it(*this); !it.Done(); it.Advance()) {
194    it.Current()->SetLoopInformation(nullptr);
195  }
196}
197
198void HBasicBlock::ClearDominanceInformation() {
199  dominated_blocks_.clear();
200  dominator_ = nullptr;
201}
202
203HInstruction* HBasicBlock::GetFirstInstructionDisregardMoves() const {
204  HInstruction* instruction = GetFirstInstruction();
205  while (instruction->IsParallelMove()) {
206    instruction = instruction->GetNext();
207  }
208  return instruction;
209}
210
211static bool UpdateDominatorOfSuccessor(HBasicBlock* block, HBasicBlock* successor) {
212  DCHECK(ContainsElement(block->GetSuccessors(), successor));
213
214  HBasicBlock* old_dominator = successor->GetDominator();
215  HBasicBlock* new_dominator =
216      (old_dominator == nullptr) ? block
217                                 : CommonDominator::ForPair(old_dominator, block);
218
219  if (old_dominator == new_dominator) {
220    return false;
221  } else {
222    successor->SetDominator(new_dominator);
223    return true;
224  }
225}
226
227void HGraph::ComputeDominanceInformation() {
228  DCHECK(reverse_post_order_.empty());
229  reverse_post_order_.reserve(blocks_.size());
230  reverse_post_order_.push_back(entry_block_);
231
232  // Number of visits of a given node, indexed by block id.
233  ArenaVector<size_t> visits(blocks_.size(), 0u, arena_->Adapter(kArenaAllocGraphBuilder));
234  // Number of successors visited from a given node, indexed by block id.
235  ArenaVector<size_t> successors_visited(blocks_.size(),
236                                         0u,
237                                         arena_->Adapter(kArenaAllocGraphBuilder));
238  // Nodes for which we need to visit successors.
239  ArenaVector<HBasicBlock*> worklist(arena_->Adapter(kArenaAllocGraphBuilder));
240  constexpr size_t kDefaultWorklistSize = 8;
241  worklist.reserve(kDefaultWorklistSize);
242  worklist.push_back(entry_block_);
243
244  while (!worklist.empty()) {
245    HBasicBlock* current = worklist.back();
246    uint32_t current_id = current->GetBlockId();
247    if (successors_visited[current_id] == current->GetSuccessors().size()) {
248      worklist.pop_back();
249    } else {
250      HBasicBlock* successor = current->GetSuccessors()[successors_visited[current_id]++];
251      UpdateDominatorOfSuccessor(current, successor);
252
253      // Once all the forward edges have been visited, we know the immediate
254      // dominator of the block. We can then start visiting its successors.
255      if (++visits[successor->GetBlockId()] ==
256          successor->GetPredecessors().size() - successor->NumberOfBackEdges()) {
257        reverse_post_order_.push_back(successor);
258        worklist.push_back(successor);
259      }
260    }
261  }
262
263  // Check if the graph has back edges not dominated by their respective headers.
264  // If so, we need to update the dominators of those headers and recursively of
265  // their successors. We do that with a fix-point iteration over all blocks.
266  // The algorithm is guaranteed to terminate because it loops only if the sum
267  // of all dominator chains has decreased in the current iteration.
268  bool must_run_fix_point = false;
269  for (HBasicBlock* block : blocks_) {
270    if (block != nullptr &&
271        block->IsLoopHeader() &&
272        block->GetLoopInformation()->HasBackEdgeNotDominatedByHeader()) {
273      must_run_fix_point = true;
274      break;
275    }
276  }
277  if (must_run_fix_point) {
278    bool update_occurred = true;
279    while (update_occurred) {
280      update_occurred = false;
281      for (HReversePostOrderIterator it(*this); !it.Done(); it.Advance()) {
282        HBasicBlock* block = it.Current();
283        for (HBasicBlock* successor : block->GetSuccessors()) {
284          update_occurred |= UpdateDominatorOfSuccessor(block, successor);
285        }
286      }
287    }
288  }
289
290  // Make sure that there are no remaining blocks whose dominator information
291  // needs to be updated.
292  if (kIsDebugBuild) {
293    for (HReversePostOrderIterator it(*this); !it.Done(); it.Advance()) {
294      HBasicBlock* block = it.Current();
295      for (HBasicBlock* successor : block->GetSuccessors()) {
296        DCHECK(!UpdateDominatorOfSuccessor(block, successor));
297      }
298    }
299  }
300
301  // Populate `dominated_blocks_` information after computing all dominators.
302  // The potential presence of irreducible loops requires to do it after.
303  for (HReversePostOrderIterator it(*this); !it.Done(); it.Advance()) {
304    HBasicBlock* block = it.Current();
305    if (!block->IsEntryBlock()) {
306      block->GetDominator()->AddDominatedBlock(block);
307    }
308  }
309}
310
311HBasicBlock* HGraph::SplitEdge(HBasicBlock* block, HBasicBlock* successor) {
312  HBasicBlock* new_block = new (arena_) HBasicBlock(this, successor->GetDexPc());
313  AddBlock(new_block);
314  // Use `InsertBetween` to ensure the predecessor index and successor index of
315  // `block` and `successor` are preserved.
316  new_block->InsertBetween(block, successor);
317  return new_block;
318}
319
320void HGraph::SplitCriticalEdge(HBasicBlock* block, HBasicBlock* successor) {
321  // Insert a new node between `block` and `successor` to split the
322  // critical edge.
323  HBasicBlock* new_block = SplitEdge(block, successor);
324  new_block->AddInstruction(new (arena_) HGoto(successor->GetDexPc()));
325  if (successor->IsLoopHeader()) {
326    // If we split at a back edge boundary, make the new block the back edge.
327    HLoopInformation* info = successor->GetLoopInformation();
328    if (info->IsBackEdge(*block)) {
329      info->RemoveBackEdge(block);
330      info->AddBackEdge(new_block);
331    }
332  }
333}
334
335void HGraph::SimplifyLoop(HBasicBlock* header) {
336  HLoopInformation* info = header->GetLoopInformation();
337
338  // Make sure the loop has only one pre header. This simplifies SSA building by having
339  // to just look at the pre header to know which locals are initialized at entry of the
340  // loop. Also, don't allow the entry block to be a pre header: this simplifies inlining
341  // this graph.
342  size_t number_of_incomings = header->GetPredecessors().size() - info->NumberOfBackEdges();
343  if (number_of_incomings != 1 || (GetEntryBlock()->GetSingleSuccessor() == header)) {
344    HBasicBlock* pre_header = new (arena_) HBasicBlock(this, header->GetDexPc());
345    AddBlock(pre_header);
346    pre_header->AddInstruction(new (arena_) HGoto(header->GetDexPc()));
347
348    for (size_t pred = 0; pred < header->GetPredecessors().size(); ++pred) {
349      HBasicBlock* predecessor = header->GetPredecessors()[pred];
350      if (!info->IsBackEdge(*predecessor)) {
351        predecessor->ReplaceSuccessor(header, pre_header);
352        pred--;
353      }
354    }
355    pre_header->AddSuccessor(header);
356  }
357
358  // Make sure the first predecessor of a loop header is the incoming block.
359  if (info->IsBackEdge(*header->GetPredecessors()[0])) {
360    HBasicBlock* to_swap = header->GetPredecessors()[0];
361    for (size_t pred = 1, e = header->GetPredecessors().size(); pred < e; ++pred) {
362      HBasicBlock* predecessor = header->GetPredecessors()[pred];
363      if (!info->IsBackEdge(*predecessor)) {
364        header->predecessors_[pred] = to_swap;
365        header->predecessors_[0] = predecessor;
366        break;
367      }
368    }
369  }
370
371  HInstruction* first_instruction = header->GetFirstInstruction();
372  if (first_instruction != nullptr && first_instruction->IsSuspendCheck()) {
373    // Called from DeadBlockElimination. Update SuspendCheck pointer.
374    info->SetSuspendCheck(first_instruction->AsSuspendCheck());
375  }
376}
377
378void HGraph::ComputeTryBlockInformation() {
379  // Iterate in reverse post order to propagate try membership information from
380  // predecessors to their successors.
381  for (HReversePostOrderIterator it(*this); !it.Done(); it.Advance()) {
382    HBasicBlock* block = it.Current();
383    if (block->IsEntryBlock() || block->IsCatchBlock()) {
384      // Catch blocks after simplification have only exceptional predecessors
385      // and hence are never in tries.
386      continue;
387    }
388
389    // Infer try membership from the first predecessor. Having simplified loops,
390    // the first predecessor can never be a back edge and therefore it must have
391    // been visited already and had its try membership set.
392    HBasicBlock* first_predecessor = block->GetPredecessors()[0];
393    DCHECK(!block->IsLoopHeader() || !block->GetLoopInformation()->IsBackEdge(*first_predecessor));
394    const HTryBoundary* try_entry = first_predecessor->ComputeTryEntryOfSuccessors();
395    if (try_entry != nullptr &&
396        (block->GetTryCatchInformation() == nullptr ||
397         try_entry != &block->GetTryCatchInformation()->GetTryEntry())) {
398      // We are either setting try block membership for the first time or it
399      // has changed.
400      block->SetTryCatchInformation(new (arena_) TryCatchInformation(*try_entry));
401    }
402  }
403}
404
405void HGraph::SimplifyCFG() {
406// Simplify the CFG for future analysis, and code generation:
407  // (1): Split critical edges.
408  // (2): Simplify loops by having only one preheader.
409  // NOTE: We're appending new blocks inside the loop, so we need to use index because iterators
410  // can be invalidated. We remember the initial size to avoid iterating over the new blocks.
411  for (size_t block_id = 0u, end = blocks_.size(); block_id != end; ++block_id) {
412    HBasicBlock* block = blocks_[block_id];
413    if (block == nullptr) continue;
414    if (block->GetSuccessors().size() > 1) {
415      // Only split normal-flow edges. We cannot split exceptional edges as they
416      // are synthesized (approximate real control flow), and we do not need to
417      // anyway. Moves that would be inserted there are performed by the runtime.
418      ArrayRef<HBasicBlock* const> normal_successors = block->GetNormalSuccessors();
419      for (size_t j = 0, e = normal_successors.size(); j < e; ++j) {
420        HBasicBlock* successor = normal_successors[j];
421        DCHECK(!successor->IsCatchBlock());
422        if (successor == exit_block_) {
423          // (Throw/Return/ReturnVoid)->TryBoundary->Exit. Special case which we
424          // do not want to split because Goto->Exit is not allowed.
425          DCHECK(block->IsSingleTryBoundary());
426        } else if (successor->GetPredecessors().size() > 1) {
427          SplitCriticalEdge(block, successor);
428          // SplitCriticalEdge could have invalidated the `normal_successors`
429          // ArrayRef. We must re-acquire it.
430          normal_successors = block->GetNormalSuccessors();
431          DCHECK_EQ(normal_successors[j]->GetSingleSuccessor(), successor);
432          DCHECK_EQ(e, normal_successors.size());
433        }
434      }
435    }
436    if (block->IsLoopHeader()) {
437      SimplifyLoop(block);
438    } else if (!block->IsEntryBlock() &&
439               block->GetFirstInstruction() != nullptr &&
440               block->GetFirstInstruction()->IsSuspendCheck()) {
441      // We are being called by the dead code elimiation pass, and what used to be
442      // a loop got dismantled. Just remove the suspend check.
443      block->RemoveInstruction(block->GetFirstInstruction());
444    }
445  }
446}
447
448GraphAnalysisResult HGraph::AnalyzeLoops() const {
449  // We iterate post order to ensure we visit inner loops before outer loops.
450  // `PopulateRecursive` needs this guarantee to know whether a natural loop
451  // contains an irreducible loop.
452  for (HPostOrderIterator it(*this); !it.Done(); it.Advance()) {
453    HBasicBlock* block = it.Current();
454    if (block->IsLoopHeader()) {
455      if (block->IsCatchBlock()) {
456        // TODO: Dealing with exceptional back edges could be tricky because
457        //       they only approximate the real control flow. Bail out for now.
458        return kAnalysisFailThrowCatchLoop;
459      }
460      block->GetLoopInformation()->Populate();
461    }
462  }
463  return kAnalysisSuccess;
464}
465
466void HLoopInformation::Dump(std::ostream& os) {
467  os << "header: " << header_->GetBlockId() << std::endl;
468  os << "pre header: " << GetPreHeader()->GetBlockId() << std::endl;
469  for (HBasicBlock* block : back_edges_) {
470    os << "back edge: " << block->GetBlockId() << std::endl;
471  }
472  for (HBasicBlock* block : header_->GetPredecessors()) {
473    os << "predecessor: " << block->GetBlockId() << std::endl;
474  }
475  for (uint32_t idx : blocks_.Indexes()) {
476    os << "  in loop: " << idx << std::endl;
477  }
478}
479
480void HGraph::InsertConstant(HConstant* constant) {
481  // New constants are inserted before the SuspendCheck at the bottom of the
482  // entry block. Note that this method can be called from the graph builder and
483  // the entry block therefore may not end with SuspendCheck->Goto yet.
484  HInstruction* insert_before = nullptr;
485
486  HInstruction* gota = entry_block_->GetLastInstruction();
487  if (gota != nullptr && gota->IsGoto()) {
488    HInstruction* suspend_check = gota->GetPrevious();
489    if (suspend_check != nullptr && suspend_check->IsSuspendCheck()) {
490      insert_before = suspend_check;
491    } else {
492      insert_before = gota;
493    }
494  }
495
496  if (insert_before == nullptr) {
497    entry_block_->AddInstruction(constant);
498  } else {
499    entry_block_->InsertInstructionBefore(constant, insert_before);
500  }
501}
502
503HNullConstant* HGraph::GetNullConstant(uint32_t dex_pc) {
504  // For simplicity, don't bother reviving the cached null constant if it is
505  // not null and not in a block. Otherwise, we need to clear the instruction
506  // id and/or any invariants the graph is assuming when adding new instructions.
507  if ((cached_null_constant_ == nullptr) || (cached_null_constant_->GetBlock() == nullptr)) {
508    cached_null_constant_ = new (arena_) HNullConstant(dex_pc);
509    cached_null_constant_->SetReferenceTypeInfo(inexact_object_rti_);
510    InsertConstant(cached_null_constant_);
511  }
512  if (kIsDebugBuild) {
513    ScopedObjectAccess soa(Thread::Current());
514    DCHECK(cached_null_constant_->GetReferenceTypeInfo().IsValid());
515  }
516  return cached_null_constant_;
517}
518
519HCurrentMethod* HGraph::GetCurrentMethod() {
520  // For simplicity, don't bother reviving the cached current method if it is
521  // not null and not in a block. Otherwise, we need to clear the instruction
522  // id and/or any invariants the graph is assuming when adding new instructions.
523  if ((cached_current_method_ == nullptr) || (cached_current_method_->GetBlock() == nullptr)) {
524    cached_current_method_ = new (arena_) HCurrentMethod(
525        Is64BitInstructionSet(instruction_set_) ? Primitive::kPrimLong : Primitive::kPrimInt,
526        entry_block_->GetDexPc());
527    if (entry_block_->GetFirstInstruction() == nullptr) {
528      entry_block_->AddInstruction(cached_current_method_);
529    } else {
530      entry_block_->InsertInstructionBefore(
531          cached_current_method_, entry_block_->GetFirstInstruction());
532    }
533  }
534  return cached_current_method_;
535}
536
537HConstant* HGraph::GetConstant(Primitive::Type type, int64_t value, uint32_t dex_pc) {
538  switch (type) {
539    case Primitive::Type::kPrimBoolean:
540      DCHECK(IsUint<1>(value));
541      FALLTHROUGH_INTENDED;
542    case Primitive::Type::kPrimByte:
543    case Primitive::Type::kPrimChar:
544    case Primitive::Type::kPrimShort:
545    case Primitive::Type::kPrimInt:
546      DCHECK(IsInt(Primitive::ComponentSize(type) * kBitsPerByte, value));
547      return GetIntConstant(static_cast<int32_t>(value), dex_pc);
548
549    case Primitive::Type::kPrimLong:
550      return GetLongConstant(value, dex_pc);
551
552    default:
553      LOG(FATAL) << "Unsupported constant type";
554      UNREACHABLE();
555  }
556}
557
558void HGraph::CacheFloatConstant(HFloatConstant* constant) {
559  int32_t value = bit_cast<int32_t, float>(constant->GetValue());
560  DCHECK(cached_float_constants_.find(value) == cached_float_constants_.end());
561  cached_float_constants_.Overwrite(value, constant);
562}
563
564void HGraph::CacheDoubleConstant(HDoubleConstant* constant) {
565  int64_t value = bit_cast<int64_t, double>(constant->GetValue());
566  DCHECK(cached_double_constants_.find(value) == cached_double_constants_.end());
567  cached_double_constants_.Overwrite(value, constant);
568}
569
570void HLoopInformation::Add(HBasicBlock* block) {
571  blocks_.SetBit(block->GetBlockId());
572}
573
574void HLoopInformation::Remove(HBasicBlock* block) {
575  blocks_.ClearBit(block->GetBlockId());
576}
577
578void HLoopInformation::PopulateRecursive(HBasicBlock* block) {
579  if (blocks_.IsBitSet(block->GetBlockId())) {
580    return;
581  }
582
583  blocks_.SetBit(block->GetBlockId());
584  block->SetInLoop(this);
585  if (block->IsLoopHeader()) {
586    // We're visiting loops in post-order, so inner loops must have been
587    // populated already.
588    DCHECK(block->GetLoopInformation()->IsPopulated());
589    if (block->GetLoopInformation()->IsIrreducible()) {
590      contains_irreducible_loop_ = true;
591    }
592  }
593  for (HBasicBlock* predecessor : block->GetPredecessors()) {
594    PopulateRecursive(predecessor);
595  }
596}
597
598void HLoopInformation::PopulateIrreducibleRecursive(HBasicBlock* block, ArenaBitVector* finalized) {
599  size_t block_id = block->GetBlockId();
600
601  // If `block` is in `finalized`, we know its membership in the loop has been
602  // decided and it does not need to be revisited.
603  if (finalized->IsBitSet(block_id)) {
604    return;
605  }
606
607  bool is_finalized = false;
608  if (block->IsLoopHeader()) {
609    // If we hit a loop header in an irreducible loop, we first check if the
610    // pre header of that loop belongs to the currently analyzed loop. If it does,
611    // then we visit the back edges.
612    // Note that we cannot use GetPreHeader, as the loop may have not been populated
613    // yet.
614    HBasicBlock* pre_header = block->GetPredecessors()[0];
615    PopulateIrreducibleRecursive(pre_header, finalized);
616    if (blocks_.IsBitSet(pre_header->GetBlockId())) {
617      block->SetInLoop(this);
618      blocks_.SetBit(block_id);
619      finalized->SetBit(block_id);
620      is_finalized = true;
621
622      HLoopInformation* info = block->GetLoopInformation();
623      for (HBasicBlock* back_edge : info->GetBackEdges()) {
624        PopulateIrreducibleRecursive(back_edge, finalized);
625      }
626    }
627  } else {
628    // Visit all predecessors. If one predecessor is part of the loop, this
629    // block is also part of this loop.
630    for (HBasicBlock* predecessor : block->GetPredecessors()) {
631      PopulateIrreducibleRecursive(predecessor, finalized);
632      if (!is_finalized && blocks_.IsBitSet(predecessor->GetBlockId())) {
633        block->SetInLoop(this);
634        blocks_.SetBit(block_id);
635        finalized->SetBit(block_id);
636        is_finalized = true;
637      }
638    }
639  }
640
641  // All predecessors have been recursively visited. Mark finalized if not marked yet.
642  if (!is_finalized) {
643    finalized->SetBit(block_id);
644  }
645}
646
647void HLoopInformation::Populate() {
648  DCHECK_EQ(blocks_.NumSetBits(), 0u) << "Loop information has already been populated";
649  // Populate this loop: starting with the back edge, recursively add predecessors
650  // that are not already part of that loop. Set the header as part of the loop
651  // to end the recursion.
652  // This is a recursive implementation of the algorithm described in
653  // "Advanced Compiler Design & Implementation" (Muchnick) p192.
654  HGraph* graph = header_->GetGraph();
655  blocks_.SetBit(header_->GetBlockId());
656  header_->SetInLoop(this);
657
658  bool is_irreducible_loop = HasBackEdgeNotDominatedByHeader();
659
660  if (is_irreducible_loop) {
661    ArenaBitVector visited(graph->GetArena(),
662                           graph->GetBlocks().size(),
663                           /* expandable */ false,
664                           kArenaAllocGraphBuilder);
665    // Stop marking blocks at the loop header.
666    visited.SetBit(header_->GetBlockId());
667
668    for (HBasicBlock* back_edge : GetBackEdges()) {
669      PopulateIrreducibleRecursive(back_edge, &visited);
670    }
671  } else {
672    for (HBasicBlock* back_edge : GetBackEdges()) {
673      PopulateRecursive(back_edge);
674    }
675  }
676
677  if (!is_irreducible_loop && graph->IsCompilingOsr()) {
678    // When compiling in OSR mode, all loops in the compiled method may be entered
679    // from the interpreter. We treat this OSR entry point just like an extra entry
680    // to an irreducible loop, so we need to mark the method's loops as irreducible.
681    // This does not apply to inlined loops which do not act as OSR entry points.
682    if (suspend_check_ == nullptr) {
683      // Just building the graph in OSR mode, this loop is not inlined. We never build an
684      // inner graph in OSR mode as we can do OSR transition only from the outer method.
685      is_irreducible_loop = true;
686    } else {
687      // Look at the suspend check's environment to determine if the loop was inlined.
688      DCHECK(suspend_check_->HasEnvironment());
689      if (!suspend_check_->GetEnvironment()->IsFromInlinedInvoke()) {
690        is_irreducible_loop = true;
691      }
692    }
693  }
694  if (is_irreducible_loop) {
695    irreducible_ = true;
696    contains_irreducible_loop_ = true;
697    graph->SetHasIrreducibleLoops(true);
698  }
699}
700
701HBasicBlock* HLoopInformation::GetPreHeader() const {
702  HBasicBlock* block = header_->GetPredecessors()[0];
703  DCHECK(irreducible_ || (block == header_->GetDominator()));
704  return block;
705}
706
707bool HLoopInformation::Contains(const HBasicBlock& block) const {
708  return blocks_.IsBitSet(block.GetBlockId());
709}
710
711bool HLoopInformation::IsIn(const HLoopInformation& other) const {
712  return other.blocks_.IsBitSet(header_->GetBlockId());
713}
714
715bool HLoopInformation::IsDefinedOutOfTheLoop(HInstruction* instruction) const {
716  return !blocks_.IsBitSet(instruction->GetBlock()->GetBlockId());
717}
718
719size_t HLoopInformation::GetLifetimeEnd() const {
720  size_t last_position = 0;
721  for (HBasicBlock* back_edge : GetBackEdges()) {
722    last_position = std::max(back_edge->GetLifetimeEnd(), last_position);
723  }
724  return last_position;
725}
726
727bool HLoopInformation::HasBackEdgeNotDominatedByHeader() const {
728  for (HBasicBlock* back_edge : GetBackEdges()) {
729    DCHECK(back_edge->GetDominator() != nullptr);
730    if (!header_->Dominates(back_edge)) {
731      return true;
732    }
733  }
734  return false;
735}
736
737bool HLoopInformation::DominatesAllBackEdges(HBasicBlock* block) {
738  for (HBasicBlock* back_edge : GetBackEdges()) {
739    if (!block->Dominates(back_edge)) {
740      return false;
741    }
742  }
743  return true;
744}
745
746bool HBasicBlock::Dominates(HBasicBlock* other) const {
747  // Walk up the dominator tree from `other`, to find out if `this`
748  // is an ancestor.
749  HBasicBlock* current = other;
750  while (current != nullptr) {
751    if (current == this) {
752      return true;
753    }
754    current = current->GetDominator();
755  }
756  return false;
757}
758
759static void UpdateInputsUsers(HInstruction* instruction) {
760  for (size_t i = 0, e = instruction->InputCount(); i < e; ++i) {
761    instruction->InputAt(i)->AddUseAt(instruction, i);
762  }
763  // Environment should be created later.
764  DCHECK(!instruction->HasEnvironment());
765}
766
767void HBasicBlock::ReplaceAndRemoveInstructionWith(HInstruction* initial,
768                                                  HInstruction* replacement) {
769  DCHECK(initial->GetBlock() == this);
770  if (initial->IsControlFlow()) {
771    // We can only replace a control flow instruction with another control flow instruction.
772    DCHECK(replacement->IsControlFlow());
773    DCHECK_EQ(replacement->GetId(), -1);
774    DCHECK_EQ(replacement->GetType(), Primitive::kPrimVoid);
775    DCHECK_EQ(initial->GetBlock(), this);
776    DCHECK_EQ(initial->GetType(), Primitive::kPrimVoid);
777    DCHECK(initial->GetUses().empty());
778    DCHECK(initial->GetEnvUses().empty());
779    replacement->SetBlock(this);
780    replacement->SetId(GetGraph()->GetNextInstructionId());
781    instructions_.InsertInstructionBefore(replacement, initial);
782    UpdateInputsUsers(replacement);
783  } else {
784    InsertInstructionBefore(replacement, initial);
785    initial->ReplaceWith(replacement);
786  }
787  RemoveInstruction(initial);
788}
789
790void HBasicBlock::MoveInstructionBefore(HInstruction* insn, HInstruction* cursor) {
791  DCHECK(!cursor->IsPhi());
792  DCHECK(!insn->IsPhi());
793  DCHECK(!insn->IsControlFlow());
794  DCHECK(insn->CanBeMoved());
795  DCHECK(!insn->HasSideEffects());
796
797  HBasicBlock* from_block = insn->GetBlock();
798  HBasicBlock* to_block = cursor->GetBlock();
799  DCHECK(from_block != to_block);
800
801  from_block->RemoveInstruction(insn, /* ensure_safety */ false);
802  insn->SetBlock(to_block);
803  to_block->instructions_.InsertInstructionBefore(insn, cursor);
804}
805
806static void Add(HInstructionList* instruction_list,
807                HBasicBlock* block,
808                HInstruction* instruction) {
809  DCHECK(instruction->GetBlock() == nullptr);
810  DCHECK_EQ(instruction->GetId(), -1);
811  instruction->SetBlock(block);
812  instruction->SetId(block->GetGraph()->GetNextInstructionId());
813  UpdateInputsUsers(instruction);
814  instruction_list->AddInstruction(instruction);
815}
816
817void HBasicBlock::AddInstruction(HInstruction* instruction) {
818  Add(&instructions_, this, instruction);
819}
820
821void HBasicBlock::AddPhi(HPhi* phi) {
822  Add(&phis_, this, phi);
823}
824
825void HBasicBlock::InsertInstructionBefore(HInstruction* instruction, HInstruction* cursor) {
826  DCHECK(!cursor->IsPhi());
827  DCHECK(!instruction->IsPhi());
828  DCHECK_EQ(instruction->GetId(), -1);
829  DCHECK_NE(cursor->GetId(), -1);
830  DCHECK_EQ(cursor->GetBlock(), this);
831  DCHECK(!instruction->IsControlFlow());
832  instruction->SetBlock(this);
833  instruction->SetId(GetGraph()->GetNextInstructionId());
834  UpdateInputsUsers(instruction);
835  instructions_.InsertInstructionBefore(instruction, cursor);
836}
837
838void HBasicBlock::InsertInstructionAfter(HInstruction* instruction, HInstruction* cursor) {
839  DCHECK(!cursor->IsPhi());
840  DCHECK(!instruction->IsPhi());
841  DCHECK_EQ(instruction->GetId(), -1);
842  DCHECK_NE(cursor->GetId(), -1);
843  DCHECK_EQ(cursor->GetBlock(), this);
844  DCHECK(!instruction->IsControlFlow());
845  DCHECK(!cursor->IsControlFlow());
846  instruction->SetBlock(this);
847  instruction->SetId(GetGraph()->GetNextInstructionId());
848  UpdateInputsUsers(instruction);
849  instructions_.InsertInstructionAfter(instruction, cursor);
850}
851
852void HBasicBlock::InsertPhiAfter(HPhi* phi, HPhi* cursor) {
853  DCHECK_EQ(phi->GetId(), -1);
854  DCHECK_NE(cursor->GetId(), -1);
855  DCHECK_EQ(cursor->GetBlock(), this);
856  phi->SetBlock(this);
857  phi->SetId(GetGraph()->GetNextInstructionId());
858  UpdateInputsUsers(phi);
859  phis_.InsertInstructionAfter(phi, cursor);
860}
861
862static void Remove(HInstructionList* instruction_list,
863                   HBasicBlock* block,
864                   HInstruction* instruction,
865                   bool ensure_safety) {
866  DCHECK_EQ(block, instruction->GetBlock());
867  instruction->SetBlock(nullptr);
868  instruction_list->RemoveInstruction(instruction);
869  if (ensure_safety) {
870    DCHECK(instruction->GetUses().empty());
871    DCHECK(instruction->GetEnvUses().empty());
872    RemoveAsUser(instruction);
873  }
874}
875
876void HBasicBlock::RemoveInstruction(HInstruction* instruction, bool ensure_safety) {
877  DCHECK(!instruction->IsPhi());
878  Remove(&instructions_, this, instruction, ensure_safety);
879}
880
881void HBasicBlock::RemovePhi(HPhi* phi, bool ensure_safety) {
882  Remove(&phis_, this, phi, ensure_safety);
883}
884
885void HBasicBlock::RemoveInstructionOrPhi(HInstruction* instruction, bool ensure_safety) {
886  if (instruction->IsPhi()) {
887    RemovePhi(instruction->AsPhi(), ensure_safety);
888  } else {
889    RemoveInstruction(instruction, ensure_safety);
890  }
891}
892
893void HEnvironment::CopyFrom(const ArenaVector<HInstruction*>& locals) {
894  for (size_t i = 0; i < locals.size(); i++) {
895    HInstruction* instruction = locals[i];
896    SetRawEnvAt(i, instruction);
897    if (instruction != nullptr) {
898      instruction->AddEnvUseAt(this, i);
899    }
900  }
901}
902
903void HEnvironment::CopyFrom(HEnvironment* env) {
904  for (size_t i = 0; i < env->Size(); i++) {
905    HInstruction* instruction = env->GetInstructionAt(i);
906    SetRawEnvAt(i, instruction);
907    if (instruction != nullptr) {
908      instruction->AddEnvUseAt(this, i);
909    }
910  }
911}
912
913void HEnvironment::CopyFromWithLoopPhiAdjustment(HEnvironment* env,
914                                                 HBasicBlock* loop_header) {
915  DCHECK(loop_header->IsLoopHeader());
916  for (size_t i = 0; i < env->Size(); i++) {
917    HInstruction* instruction = env->GetInstructionAt(i);
918    SetRawEnvAt(i, instruction);
919    if (instruction == nullptr) {
920      continue;
921    }
922    if (instruction->IsLoopHeaderPhi() && (instruction->GetBlock() == loop_header)) {
923      // At the end of the loop pre-header, the corresponding value for instruction
924      // is the first input of the phi.
925      HInstruction* initial = instruction->AsPhi()->InputAt(0);
926      SetRawEnvAt(i, initial);
927      initial->AddEnvUseAt(this, i);
928    } else {
929      instruction->AddEnvUseAt(this, i);
930    }
931  }
932}
933
934void HEnvironment::RemoveAsUserOfInput(size_t index) const {
935  const HUserRecord<HEnvironment*>& env_use = vregs_[index];
936  HInstruction* user = env_use.GetInstruction();
937  auto before_env_use_node = env_use.GetBeforeUseNode();
938  user->env_uses_.erase_after(before_env_use_node);
939  user->FixUpUserRecordsAfterEnvUseRemoval(before_env_use_node);
940}
941
942HInstruction::InstructionKind HInstruction::GetKind() const {
943  return GetKindInternal();
944}
945
946HInstruction* HInstruction::GetNextDisregardingMoves() const {
947  HInstruction* next = GetNext();
948  while (next != nullptr && next->IsParallelMove()) {
949    next = next->GetNext();
950  }
951  return next;
952}
953
954HInstruction* HInstruction::GetPreviousDisregardingMoves() const {
955  HInstruction* previous = GetPrevious();
956  while (previous != nullptr && previous->IsParallelMove()) {
957    previous = previous->GetPrevious();
958  }
959  return previous;
960}
961
962void HInstructionList::AddInstruction(HInstruction* instruction) {
963  if (first_instruction_ == nullptr) {
964    DCHECK(last_instruction_ == nullptr);
965    first_instruction_ = last_instruction_ = instruction;
966  } else {
967    last_instruction_->next_ = instruction;
968    instruction->previous_ = last_instruction_;
969    last_instruction_ = instruction;
970  }
971}
972
973void HInstructionList::InsertInstructionBefore(HInstruction* instruction, HInstruction* cursor) {
974  DCHECK(Contains(cursor));
975  if (cursor == first_instruction_) {
976    cursor->previous_ = instruction;
977    instruction->next_ = cursor;
978    first_instruction_ = instruction;
979  } else {
980    instruction->previous_ = cursor->previous_;
981    instruction->next_ = cursor;
982    cursor->previous_ = instruction;
983    instruction->previous_->next_ = instruction;
984  }
985}
986
987void HInstructionList::InsertInstructionAfter(HInstruction* instruction, HInstruction* cursor) {
988  DCHECK(Contains(cursor));
989  if (cursor == last_instruction_) {
990    cursor->next_ = instruction;
991    instruction->previous_ = cursor;
992    last_instruction_ = instruction;
993  } else {
994    instruction->next_ = cursor->next_;
995    instruction->previous_ = cursor;
996    cursor->next_ = instruction;
997    instruction->next_->previous_ = instruction;
998  }
999}
1000
1001void HInstructionList::RemoveInstruction(HInstruction* instruction) {
1002  if (instruction->previous_ != nullptr) {
1003    instruction->previous_->next_ = instruction->next_;
1004  }
1005  if (instruction->next_ != nullptr) {
1006    instruction->next_->previous_ = instruction->previous_;
1007  }
1008  if (instruction == first_instruction_) {
1009    first_instruction_ = instruction->next_;
1010  }
1011  if (instruction == last_instruction_) {
1012    last_instruction_ = instruction->previous_;
1013  }
1014}
1015
1016bool HInstructionList::Contains(HInstruction* instruction) const {
1017  for (HInstructionIterator it(*this); !it.Done(); it.Advance()) {
1018    if (it.Current() == instruction) {
1019      return true;
1020    }
1021  }
1022  return false;
1023}
1024
1025bool HInstructionList::FoundBefore(const HInstruction* instruction1,
1026                                   const HInstruction* instruction2) const {
1027  DCHECK_EQ(instruction1->GetBlock(), instruction2->GetBlock());
1028  for (HInstructionIterator it(*this); !it.Done(); it.Advance()) {
1029    if (it.Current() == instruction1) {
1030      return true;
1031    }
1032    if (it.Current() == instruction2) {
1033      return false;
1034    }
1035  }
1036  LOG(FATAL) << "Did not find an order between two instructions of the same block.";
1037  return true;
1038}
1039
1040bool HInstruction::StrictlyDominates(HInstruction* other_instruction) const {
1041  if (other_instruction == this) {
1042    // An instruction does not strictly dominate itself.
1043    return false;
1044  }
1045  HBasicBlock* block = GetBlock();
1046  HBasicBlock* other_block = other_instruction->GetBlock();
1047  if (block != other_block) {
1048    return GetBlock()->Dominates(other_instruction->GetBlock());
1049  } else {
1050    // If both instructions are in the same block, ensure this
1051    // instruction comes before `other_instruction`.
1052    if (IsPhi()) {
1053      if (!other_instruction->IsPhi()) {
1054        // Phis appear before non phi-instructions so this instruction
1055        // dominates `other_instruction`.
1056        return true;
1057      } else {
1058        // There is no order among phis.
1059        LOG(FATAL) << "There is no dominance between phis of a same block.";
1060        return false;
1061      }
1062    } else {
1063      // `this` is not a phi.
1064      if (other_instruction->IsPhi()) {
1065        // Phis appear before non phi-instructions so this instruction
1066        // does not dominate `other_instruction`.
1067        return false;
1068      } else {
1069        // Check whether this instruction comes before
1070        // `other_instruction` in the instruction list.
1071        return block->GetInstructions().FoundBefore(this, other_instruction);
1072      }
1073    }
1074  }
1075}
1076
1077void HInstruction::RemoveEnvironment() {
1078  RemoveEnvironmentUses(this);
1079  environment_ = nullptr;
1080}
1081
1082void HInstruction::ReplaceWith(HInstruction* other) {
1083  DCHECK(other != nullptr);
1084  // Note: fixup_end remains valid across splice_after().
1085  auto fixup_end = other->uses_.empty() ? other->uses_.begin() : ++other->uses_.begin();
1086  other->uses_.splice_after(other->uses_.before_begin(), uses_);
1087  other->FixUpUserRecordsAfterUseInsertion(fixup_end);
1088
1089  // Note: env_fixup_end remains valid across splice_after().
1090  auto env_fixup_end =
1091      other->env_uses_.empty() ? other->env_uses_.begin() : ++other->env_uses_.begin();
1092  other->env_uses_.splice_after(other->env_uses_.before_begin(), env_uses_);
1093  other->FixUpUserRecordsAfterEnvUseInsertion(env_fixup_end);
1094
1095  DCHECK(uses_.empty());
1096  DCHECK(env_uses_.empty());
1097}
1098
1099void HInstruction::ReplaceInput(HInstruction* replacement, size_t index) {
1100  HUserRecord<HInstruction*> input_use = InputRecordAt(index);
1101  if (input_use.GetInstruction() == replacement) {
1102    // Nothing to do.
1103    return;
1104  }
1105  HUseList<HInstruction*>::iterator before_use_node = input_use.GetBeforeUseNode();
1106  // Note: fixup_end remains valid across splice_after().
1107  auto fixup_end =
1108      replacement->uses_.empty() ? replacement->uses_.begin() : ++replacement->uses_.begin();
1109  replacement->uses_.splice_after(replacement->uses_.before_begin(),
1110                                  input_use.GetInstruction()->uses_,
1111                                  before_use_node);
1112  replacement->FixUpUserRecordsAfterUseInsertion(fixup_end);
1113  input_use.GetInstruction()->FixUpUserRecordsAfterUseRemoval(before_use_node);
1114}
1115
1116size_t HInstruction::EnvironmentSize() const {
1117  return HasEnvironment() ? environment_->Size() : 0;
1118}
1119
1120void HPhi::AddInput(HInstruction* input) {
1121  DCHECK(input->GetBlock() != nullptr);
1122  inputs_.push_back(HUserRecord<HInstruction*>(input));
1123  input->AddUseAt(this, inputs_.size() - 1);
1124}
1125
1126void HPhi::RemoveInputAt(size_t index) {
1127  RemoveAsUserOfInput(index);
1128  inputs_.erase(inputs_.begin() + index);
1129  for (size_t i = index, e = InputCount(); i < e; ++i) {
1130    DCHECK_EQ(InputRecordAt(i).GetUseNode()->GetIndex(), i + 1u);
1131    InputRecordAt(i).GetUseNode()->SetIndex(i);
1132  }
1133}
1134
1135#define DEFINE_ACCEPT(name, super)                                             \
1136void H##name::Accept(HGraphVisitor* visitor) {                                 \
1137  visitor->Visit##name(this);                                                  \
1138}
1139
1140FOR_EACH_CONCRETE_INSTRUCTION(DEFINE_ACCEPT)
1141
1142#undef DEFINE_ACCEPT
1143
1144void HGraphVisitor::VisitInsertionOrder() {
1145  const ArenaVector<HBasicBlock*>& blocks = graph_->GetBlocks();
1146  for (HBasicBlock* block : blocks) {
1147    if (block != nullptr) {
1148      VisitBasicBlock(block);
1149    }
1150  }
1151}
1152
1153void HGraphVisitor::VisitReversePostOrder() {
1154  for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) {
1155    VisitBasicBlock(it.Current());
1156  }
1157}
1158
1159void HGraphVisitor::VisitBasicBlock(HBasicBlock* block) {
1160  for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
1161    it.Current()->Accept(this);
1162  }
1163  for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
1164    it.Current()->Accept(this);
1165  }
1166}
1167
1168HConstant* HTypeConversion::TryStaticEvaluation() const {
1169  HGraph* graph = GetBlock()->GetGraph();
1170  if (GetInput()->IsIntConstant()) {
1171    int32_t value = GetInput()->AsIntConstant()->GetValue();
1172    switch (GetResultType()) {
1173      case Primitive::kPrimLong:
1174        return graph->GetLongConstant(static_cast<int64_t>(value), GetDexPc());
1175      case Primitive::kPrimFloat:
1176        return graph->GetFloatConstant(static_cast<float>(value), GetDexPc());
1177      case Primitive::kPrimDouble:
1178        return graph->GetDoubleConstant(static_cast<double>(value), GetDexPc());
1179      default:
1180        return nullptr;
1181    }
1182  } else if (GetInput()->IsLongConstant()) {
1183    int64_t value = GetInput()->AsLongConstant()->GetValue();
1184    switch (GetResultType()) {
1185      case Primitive::kPrimInt:
1186        return graph->GetIntConstant(static_cast<int32_t>(value), GetDexPc());
1187      case Primitive::kPrimFloat:
1188        return graph->GetFloatConstant(static_cast<float>(value), GetDexPc());
1189      case Primitive::kPrimDouble:
1190        return graph->GetDoubleConstant(static_cast<double>(value), GetDexPc());
1191      default:
1192        return nullptr;
1193    }
1194  } else if (GetInput()->IsFloatConstant()) {
1195    float value = GetInput()->AsFloatConstant()->GetValue();
1196    switch (GetResultType()) {
1197      case Primitive::kPrimInt:
1198        if (std::isnan(value))
1199          return graph->GetIntConstant(0, GetDexPc());
1200        if (value >= kPrimIntMax)
1201          return graph->GetIntConstant(kPrimIntMax, GetDexPc());
1202        if (value <= kPrimIntMin)
1203          return graph->GetIntConstant(kPrimIntMin, GetDexPc());
1204        return graph->GetIntConstant(static_cast<int32_t>(value), GetDexPc());
1205      case Primitive::kPrimLong:
1206        if (std::isnan(value))
1207          return graph->GetLongConstant(0, GetDexPc());
1208        if (value >= kPrimLongMax)
1209          return graph->GetLongConstant(kPrimLongMax, GetDexPc());
1210        if (value <= kPrimLongMin)
1211          return graph->GetLongConstant(kPrimLongMin, GetDexPc());
1212        return graph->GetLongConstant(static_cast<int64_t>(value), GetDexPc());
1213      case Primitive::kPrimDouble:
1214        return graph->GetDoubleConstant(static_cast<double>(value), GetDexPc());
1215      default:
1216        return nullptr;
1217    }
1218  } else if (GetInput()->IsDoubleConstant()) {
1219    double value = GetInput()->AsDoubleConstant()->GetValue();
1220    switch (GetResultType()) {
1221      case Primitive::kPrimInt:
1222        if (std::isnan(value))
1223          return graph->GetIntConstant(0, GetDexPc());
1224        if (value >= kPrimIntMax)
1225          return graph->GetIntConstant(kPrimIntMax, GetDexPc());
1226        if (value <= kPrimLongMin)
1227          return graph->GetIntConstant(kPrimIntMin, GetDexPc());
1228        return graph->GetIntConstant(static_cast<int32_t>(value), GetDexPc());
1229      case Primitive::kPrimLong:
1230        if (std::isnan(value))
1231          return graph->GetLongConstant(0, GetDexPc());
1232        if (value >= kPrimLongMax)
1233          return graph->GetLongConstant(kPrimLongMax, GetDexPc());
1234        if (value <= kPrimLongMin)
1235          return graph->GetLongConstant(kPrimLongMin, GetDexPc());
1236        return graph->GetLongConstant(static_cast<int64_t>(value), GetDexPc());
1237      case Primitive::kPrimFloat:
1238        return graph->GetFloatConstant(static_cast<float>(value), GetDexPc());
1239      default:
1240        return nullptr;
1241    }
1242  }
1243  return nullptr;
1244}
1245
1246HConstant* HUnaryOperation::TryStaticEvaluation() const {
1247  if (GetInput()->IsIntConstant()) {
1248    return Evaluate(GetInput()->AsIntConstant());
1249  } else if (GetInput()->IsLongConstant()) {
1250    return Evaluate(GetInput()->AsLongConstant());
1251  } else if (kEnableFloatingPointStaticEvaluation) {
1252    if (GetInput()->IsFloatConstant()) {
1253      return Evaluate(GetInput()->AsFloatConstant());
1254    } else if (GetInput()->IsDoubleConstant()) {
1255      return Evaluate(GetInput()->AsDoubleConstant());
1256    }
1257  }
1258  return nullptr;
1259}
1260
1261HConstant* HBinaryOperation::TryStaticEvaluation() const {
1262  if (GetLeft()->IsIntConstant() && GetRight()->IsIntConstant()) {
1263    return Evaluate(GetLeft()->AsIntConstant(), GetRight()->AsIntConstant());
1264  } else if (GetLeft()->IsLongConstant()) {
1265    if (GetRight()->IsIntConstant()) {
1266      // The binop(long, int) case is only valid for shifts and rotations.
1267      DCHECK(IsShl() || IsShr() || IsUShr() || IsRor()) << DebugName();
1268      return Evaluate(GetLeft()->AsLongConstant(), GetRight()->AsIntConstant());
1269    } else if (GetRight()->IsLongConstant()) {
1270      return Evaluate(GetLeft()->AsLongConstant(), GetRight()->AsLongConstant());
1271    }
1272  } else if (GetLeft()->IsNullConstant() && GetRight()->IsNullConstant()) {
1273    // The binop(null, null) case is only valid for equal and not-equal conditions.
1274    DCHECK(IsEqual() || IsNotEqual()) << DebugName();
1275    return Evaluate(GetLeft()->AsNullConstant(), GetRight()->AsNullConstant());
1276  } else if (kEnableFloatingPointStaticEvaluation) {
1277    if (GetLeft()->IsFloatConstant() && GetRight()->IsFloatConstant()) {
1278      return Evaluate(GetLeft()->AsFloatConstant(), GetRight()->AsFloatConstant());
1279    } else if (GetLeft()->IsDoubleConstant() && GetRight()->IsDoubleConstant()) {
1280      return Evaluate(GetLeft()->AsDoubleConstant(), GetRight()->AsDoubleConstant());
1281    }
1282  }
1283  return nullptr;
1284}
1285
1286HConstant* HBinaryOperation::GetConstantRight() const {
1287  if (GetRight()->IsConstant()) {
1288    return GetRight()->AsConstant();
1289  } else if (IsCommutative() && GetLeft()->IsConstant()) {
1290    return GetLeft()->AsConstant();
1291  } else {
1292    return nullptr;
1293  }
1294}
1295
1296// If `GetConstantRight()` returns one of the input, this returns the other
1297// one. Otherwise it returns null.
1298HInstruction* HBinaryOperation::GetLeastConstantLeft() const {
1299  HInstruction* most_constant_right = GetConstantRight();
1300  if (most_constant_right == nullptr) {
1301    return nullptr;
1302  } else if (most_constant_right == GetLeft()) {
1303    return GetRight();
1304  } else {
1305    return GetLeft();
1306  }
1307}
1308
1309std::ostream& operator<<(std::ostream& os, const ComparisonBias& rhs) {
1310  switch (rhs) {
1311    case ComparisonBias::kNoBias:
1312      return os << "no_bias";
1313    case ComparisonBias::kGtBias:
1314      return os << "gt_bias";
1315    case ComparisonBias::kLtBias:
1316      return os << "lt_bias";
1317    default:
1318      LOG(FATAL) << "Unknown ComparisonBias: " << static_cast<int>(rhs);
1319      UNREACHABLE();
1320  }
1321}
1322
1323bool HCondition::IsBeforeWhenDisregardMoves(HInstruction* instruction) const {
1324  return this == instruction->GetPreviousDisregardingMoves();
1325}
1326
1327bool HInstruction::Equals(HInstruction* other) const {
1328  if (!InstructionTypeEquals(other)) return false;
1329  DCHECK_EQ(GetKind(), other->GetKind());
1330  if (!InstructionDataEquals(other)) return false;
1331  if (GetType() != other->GetType()) return false;
1332  if (InputCount() != other->InputCount()) return false;
1333
1334  for (size_t i = 0, e = InputCount(); i < e; ++i) {
1335    if (InputAt(i) != other->InputAt(i)) return false;
1336  }
1337  DCHECK_EQ(ComputeHashCode(), other->ComputeHashCode());
1338  return true;
1339}
1340
1341std::ostream& operator<<(std::ostream& os, const HInstruction::InstructionKind& rhs) {
1342#define DECLARE_CASE(type, super) case HInstruction::k##type: os << #type; break;
1343  switch (rhs) {
1344    FOR_EACH_INSTRUCTION(DECLARE_CASE)
1345    default:
1346      os << "Unknown instruction kind " << static_cast<int>(rhs);
1347      break;
1348  }
1349#undef DECLARE_CASE
1350  return os;
1351}
1352
1353void HInstruction::MoveBefore(HInstruction* cursor) {
1354  next_->previous_ = previous_;
1355  if (previous_ != nullptr) {
1356    previous_->next_ = next_;
1357  }
1358  if (block_->instructions_.first_instruction_ == this) {
1359    block_->instructions_.first_instruction_ = next_;
1360  }
1361  DCHECK_NE(block_->instructions_.last_instruction_, this);
1362
1363  previous_ = cursor->previous_;
1364  if (previous_ != nullptr) {
1365    previous_->next_ = this;
1366  }
1367  next_ = cursor;
1368  cursor->previous_ = this;
1369  block_ = cursor->block_;
1370
1371  if (block_->instructions_.first_instruction_ == cursor) {
1372    block_->instructions_.first_instruction_ = this;
1373  }
1374}
1375
1376void HInstruction::MoveBeforeFirstUserAndOutOfLoops() {
1377  DCHECK(!CanThrow());
1378  DCHECK(!HasSideEffects());
1379  DCHECK(!HasEnvironmentUses());
1380  DCHECK(HasNonEnvironmentUses());
1381  DCHECK(!IsPhi());  // Makes no sense for Phi.
1382  DCHECK_EQ(InputCount(), 0u);
1383
1384  // Find the target block.
1385  auto uses_it = GetUses().begin();
1386  auto uses_end = GetUses().end();
1387  HBasicBlock* target_block = uses_it->GetUser()->GetBlock();
1388  ++uses_it;
1389  while (uses_it != uses_end && uses_it->GetUser()->GetBlock() == target_block) {
1390    ++uses_it;
1391  }
1392  if (uses_it != uses_end) {
1393    // This instruction has uses in two or more blocks. Find the common dominator.
1394    CommonDominator finder(target_block);
1395    for (; uses_it != uses_end; ++uses_it) {
1396      finder.Update(uses_it->GetUser()->GetBlock());
1397    }
1398    target_block = finder.Get();
1399    DCHECK(target_block != nullptr);
1400  }
1401  // Move to the first dominator not in a loop.
1402  while (target_block->IsInLoop()) {
1403    target_block = target_block->GetDominator();
1404    DCHECK(target_block != nullptr);
1405  }
1406
1407  // Find insertion position.
1408  HInstruction* insert_pos = nullptr;
1409  for (const HUseListNode<HInstruction*>& use : GetUses()) {
1410    if (use.GetUser()->GetBlock() == target_block &&
1411        (insert_pos == nullptr || use.GetUser()->StrictlyDominates(insert_pos))) {
1412      insert_pos = use.GetUser();
1413    }
1414  }
1415  if (insert_pos == nullptr) {
1416    // No user in `target_block`, insert before the control flow instruction.
1417    insert_pos = target_block->GetLastInstruction();
1418    DCHECK(insert_pos->IsControlFlow());
1419    // Avoid splitting HCondition from HIf to prevent unnecessary materialization.
1420    if (insert_pos->IsIf()) {
1421      HInstruction* if_input = insert_pos->AsIf()->InputAt(0);
1422      if (if_input == insert_pos->GetPrevious()) {
1423        insert_pos = if_input;
1424      }
1425    }
1426  }
1427  MoveBefore(insert_pos);
1428}
1429
1430HBasicBlock* HBasicBlock::SplitBefore(HInstruction* cursor) {
1431  DCHECK(!graph_->IsInSsaForm()) << "Support for SSA form not implemented.";
1432  DCHECK_EQ(cursor->GetBlock(), this);
1433
1434  HBasicBlock* new_block = new (GetGraph()->GetArena()) HBasicBlock(GetGraph(),
1435                                                                    cursor->GetDexPc());
1436  new_block->instructions_.first_instruction_ = cursor;
1437  new_block->instructions_.last_instruction_ = instructions_.last_instruction_;
1438  instructions_.last_instruction_ = cursor->previous_;
1439  if (cursor->previous_ == nullptr) {
1440    instructions_.first_instruction_ = nullptr;
1441  } else {
1442    cursor->previous_->next_ = nullptr;
1443    cursor->previous_ = nullptr;
1444  }
1445
1446  new_block->instructions_.SetBlockOfInstructions(new_block);
1447  AddInstruction(new (GetGraph()->GetArena()) HGoto(new_block->GetDexPc()));
1448
1449  for (HBasicBlock* successor : GetSuccessors()) {
1450    new_block->successors_.push_back(successor);
1451    successor->predecessors_[successor->GetPredecessorIndexOf(this)] = new_block;
1452  }
1453  successors_.clear();
1454  AddSuccessor(new_block);
1455
1456  GetGraph()->AddBlock(new_block);
1457  return new_block;
1458}
1459
1460HBasicBlock* HBasicBlock::CreateImmediateDominator() {
1461  DCHECK(!graph_->IsInSsaForm()) << "Support for SSA form not implemented.";
1462  DCHECK(!IsCatchBlock()) << "Support for updating try/catch information not implemented.";
1463
1464  HBasicBlock* new_block = new (GetGraph()->GetArena()) HBasicBlock(GetGraph(), GetDexPc());
1465
1466  for (HBasicBlock* predecessor : GetPredecessors()) {
1467    new_block->predecessors_.push_back(predecessor);
1468    predecessor->successors_[predecessor->GetSuccessorIndexOf(this)] = new_block;
1469  }
1470  predecessors_.clear();
1471  AddPredecessor(new_block);
1472
1473  GetGraph()->AddBlock(new_block);
1474  return new_block;
1475}
1476
1477HBasicBlock* HBasicBlock::SplitBeforeForInlining(HInstruction* cursor) {
1478  DCHECK_EQ(cursor->GetBlock(), this);
1479
1480  HBasicBlock* new_block = new (GetGraph()->GetArena()) HBasicBlock(GetGraph(),
1481                                                                    cursor->GetDexPc());
1482  new_block->instructions_.first_instruction_ = cursor;
1483  new_block->instructions_.last_instruction_ = instructions_.last_instruction_;
1484  instructions_.last_instruction_ = cursor->previous_;
1485  if (cursor->previous_ == nullptr) {
1486    instructions_.first_instruction_ = nullptr;
1487  } else {
1488    cursor->previous_->next_ = nullptr;
1489    cursor->previous_ = nullptr;
1490  }
1491
1492  new_block->instructions_.SetBlockOfInstructions(new_block);
1493
1494  for (HBasicBlock* successor : GetSuccessors()) {
1495    new_block->successors_.push_back(successor);
1496    successor->predecessors_[successor->GetPredecessorIndexOf(this)] = new_block;
1497  }
1498  successors_.clear();
1499
1500  for (HBasicBlock* dominated : GetDominatedBlocks()) {
1501    dominated->dominator_ = new_block;
1502    new_block->dominated_blocks_.push_back(dominated);
1503  }
1504  dominated_blocks_.clear();
1505  return new_block;
1506}
1507
1508HBasicBlock* HBasicBlock::SplitAfterForInlining(HInstruction* cursor) {
1509  DCHECK(!cursor->IsControlFlow());
1510  DCHECK_NE(instructions_.last_instruction_, cursor);
1511  DCHECK_EQ(cursor->GetBlock(), this);
1512
1513  HBasicBlock* new_block = new (GetGraph()->GetArena()) HBasicBlock(GetGraph(), GetDexPc());
1514  new_block->instructions_.first_instruction_ = cursor->GetNext();
1515  new_block->instructions_.last_instruction_ = instructions_.last_instruction_;
1516  cursor->next_->previous_ = nullptr;
1517  cursor->next_ = nullptr;
1518  instructions_.last_instruction_ = cursor;
1519
1520  new_block->instructions_.SetBlockOfInstructions(new_block);
1521  for (HBasicBlock* successor : GetSuccessors()) {
1522    new_block->successors_.push_back(successor);
1523    successor->predecessors_[successor->GetPredecessorIndexOf(this)] = new_block;
1524  }
1525  successors_.clear();
1526
1527  for (HBasicBlock* dominated : GetDominatedBlocks()) {
1528    dominated->dominator_ = new_block;
1529    new_block->dominated_blocks_.push_back(dominated);
1530  }
1531  dominated_blocks_.clear();
1532  return new_block;
1533}
1534
1535const HTryBoundary* HBasicBlock::ComputeTryEntryOfSuccessors() const {
1536  if (EndsWithTryBoundary()) {
1537    HTryBoundary* try_boundary = GetLastInstruction()->AsTryBoundary();
1538    if (try_boundary->IsEntry()) {
1539      DCHECK(!IsTryBlock());
1540      return try_boundary;
1541    } else {
1542      DCHECK(IsTryBlock());
1543      DCHECK(try_catch_information_->GetTryEntry().HasSameExceptionHandlersAs(*try_boundary));
1544      return nullptr;
1545    }
1546  } else if (IsTryBlock()) {
1547    return &try_catch_information_->GetTryEntry();
1548  } else {
1549    return nullptr;
1550  }
1551}
1552
1553bool HBasicBlock::HasThrowingInstructions() const {
1554  for (HInstructionIterator it(GetInstructions()); !it.Done(); it.Advance()) {
1555    if (it.Current()->CanThrow()) {
1556      return true;
1557    }
1558  }
1559  return false;
1560}
1561
1562static bool HasOnlyOneInstruction(const HBasicBlock& block) {
1563  return block.GetPhis().IsEmpty()
1564      && !block.GetInstructions().IsEmpty()
1565      && block.GetFirstInstruction() == block.GetLastInstruction();
1566}
1567
1568bool HBasicBlock::IsSingleGoto() const {
1569  return HasOnlyOneInstruction(*this) && GetLastInstruction()->IsGoto();
1570}
1571
1572bool HBasicBlock::IsSingleTryBoundary() const {
1573  return HasOnlyOneInstruction(*this) && GetLastInstruction()->IsTryBoundary();
1574}
1575
1576bool HBasicBlock::EndsWithControlFlowInstruction() const {
1577  return !GetInstructions().IsEmpty() && GetLastInstruction()->IsControlFlow();
1578}
1579
1580bool HBasicBlock::EndsWithIf() const {
1581  return !GetInstructions().IsEmpty() && GetLastInstruction()->IsIf();
1582}
1583
1584bool HBasicBlock::EndsWithTryBoundary() const {
1585  return !GetInstructions().IsEmpty() && GetLastInstruction()->IsTryBoundary();
1586}
1587
1588bool HBasicBlock::HasSinglePhi() const {
1589  return !GetPhis().IsEmpty() && GetFirstPhi()->GetNext() == nullptr;
1590}
1591
1592ArrayRef<HBasicBlock* const> HBasicBlock::GetNormalSuccessors() const {
1593  if (EndsWithTryBoundary()) {
1594    // The normal-flow successor of HTryBoundary is always stored at index zero.
1595    DCHECK_EQ(successors_[0], GetLastInstruction()->AsTryBoundary()->GetNormalFlowSuccessor());
1596    return ArrayRef<HBasicBlock* const>(successors_).SubArray(0u, 1u);
1597  } else {
1598    // All successors of blocks not ending with TryBoundary are normal.
1599    return ArrayRef<HBasicBlock* const>(successors_);
1600  }
1601}
1602
1603ArrayRef<HBasicBlock* const> HBasicBlock::GetExceptionalSuccessors() const {
1604  if (EndsWithTryBoundary()) {
1605    return GetLastInstruction()->AsTryBoundary()->GetExceptionHandlers();
1606  } else {
1607    // Blocks not ending with TryBoundary do not have exceptional successors.
1608    return ArrayRef<HBasicBlock* const>();
1609  }
1610}
1611
1612bool HTryBoundary::HasSameExceptionHandlersAs(const HTryBoundary& other) const {
1613  ArrayRef<HBasicBlock* const> handlers1 = GetExceptionHandlers();
1614  ArrayRef<HBasicBlock* const> handlers2 = other.GetExceptionHandlers();
1615
1616  size_t length = handlers1.size();
1617  if (length != handlers2.size()) {
1618    return false;
1619  }
1620
1621  // Exception handlers need to be stored in the same order.
1622  for (size_t i = 0; i < length; ++i) {
1623    if (handlers1[i] != handlers2[i]) {
1624      return false;
1625    }
1626  }
1627  return true;
1628}
1629
1630size_t HInstructionList::CountSize() const {
1631  size_t size = 0;
1632  HInstruction* current = first_instruction_;
1633  for (; current != nullptr; current = current->GetNext()) {
1634    size++;
1635  }
1636  return size;
1637}
1638
1639void HInstructionList::SetBlockOfInstructions(HBasicBlock* block) const {
1640  for (HInstruction* current = first_instruction_;
1641       current != nullptr;
1642       current = current->GetNext()) {
1643    current->SetBlock(block);
1644  }
1645}
1646
1647void HInstructionList::AddAfter(HInstruction* cursor, const HInstructionList& instruction_list) {
1648  DCHECK(Contains(cursor));
1649  if (!instruction_list.IsEmpty()) {
1650    if (cursor == last_instruction_) {
1651      last_instruction_ = instruction_list.last_instruction_;
1652    } else {
1653      cursor->next_->previous_ = instruction_list.last_instruction_;
1654    }
1655    instruction_list.last_instruction_->next_ = cursor->next_;
1656    cursor->next_ = instruction_list.first_instruction_;
1657    instruction_list.first_instruction_->previous_ = cursor;
1658  }
1659}
1660
1661void HInstructionList::AddBefore(HInstruction* cursor, const HInstructionList& instruction_list) {
1662  DCHECK(Contains(cursor));
1663  if (!instruction_list.IsEmpty()) {
1664    if (cursor == first_instruction_) {
1665      first_instruction_ = instruction_list.first_instruction_;
1666    } else {
1667      cursor->previous_->next_ = instruction_list.first_instruction_;
1668    }
1669    instruction_list.last_instruction_->next_ = cursor;
1670    instruction_list.first_instruction_->previous_ = cursor->previous_;
1671    cursor->previous_ = instruction_list.last_instruction_;
1672  }
1673}
1674
1675void HInstructionList::Add(const HInstructionList& instruction_list) {
1676  if (IsEmpty()) {
1677    first_instruction_ = instruction_list.first_instruction_;
1678    last_instruction_ = instruction_list.last_instruction_;
1679  } else {
1680    AddAfter(last_instruction_, instruction_list);
1681  }
1682}
1683
1684// Should be called on instructions in a dead block in post order. This method
1685// assumes `insn` has been removed from all users with the exception of catch
1686// phis because of missing exceptional edges in the graph. It removes the
1687// instruction from catch phi uses, together with inputs of other catch phis in
1688// the catch block at the same index, as these must be dead too.
1689static void RemoveUsesOfDeadInstruction(HInstruction* insn) {
1690  DCHECK(!insn->HasEnvironmentUses());
1691  while (insn->HasNonEnvironmentUses()) {
1692    const HUseListNode<HInstruction*>& use = insn->GetUses().front();
1693    size_t use_index = use.GetIndex();
1694    HBasicBlock* user_block =  use.GetUser()->GetBlock();
1695    DCHECK(use.GetUser()->IsPhi() && user_block->IsCatchBlock());
1696    for (HInstructionIterator phi_it(user_block->GetPhis()); !phi_it.Done(); phi_it.Advance()) {
1697      phi_it.Current()->AsPhi()->RemoveInputAt(use_index);
1698    }
1699  }
1700}
1701
1702void HBasicBlock::DisconnectAndDelete() {
1703  // Dominators must be removed after all the blocks they dominate. This way
1704  // a loop header is removed last, a requirement for correct loop information
1705  // iteration.
1706  DCHECK(dominated_blocks_.empty());
1707
1708  // The following steps gradually remove the block from all its dependants in
1709  // post order (b/27683071).
1710
1711  // (1) Store a basic block that we'll use in step (5) to find loops to be updated.
1712  //     We need to do this before step (4) which destroys the predecessor list.
1713  HBasicBlock* loop_update_start = this;
1714  if (IsLoopHeader()) {
1715    HLoopInformation* loop_info = GetLoopInformation();
1716    // All other blocks in this loop should have been removed because the header
1717    // was their dominator.
1718    // Note that we do not remove `this` from `loop_info` as it is unreachable.
1719    DCHECK(!loop_info->IsIrreducible());
1720    DCHECK_EQ(loop_info->GetBlocks().NumSetBits(), 1u);
1721    DCHECK_EQ(static_cast<uint32_t>(loop_info->GetBlocks().GetHighestBitSet()), GetBlockId());
1722    loop_update_start = loop_info->GetPreHeader();
1723  }
1724
1725  // (2) Disconnect the block from its successors and update their phis.
1726  for (HBasicBlock* successor : successors_) {
1727    // Delete this block from the list of predecessors.
1728    size_t this_index = successor->GetPredecessorIndexOf(this);
1729    successor->predecessors_.erase(successor->predecessors_.begin() + this_index);
1730
1731    // Check that `successor` has other predecessors, otherwise `this` is the
1732    // dominator of `successor` which violates the order DCHECKed at the top.
1733    DCHECK(!successor->predecessors_.empty());
1734
1735    // Remove this block's entries in the successor's phis. Skip exceptional
1736    // successors because catch phi inputs do not correspond to predecessor
1737    // blocks but throwing instructions. The inputs of the catch phis will be
1738    // updated in step (3).
1739    if (!successor->IsCatchBlock()) {
1740      if (successor->predecessors_.size() == 1u) {
1741        // The successor has just one predecessor left. Replace phis with the only
1742        // remaining input.
1743        for (HInstructionIterator phi_it(successor->GetPhis()); !phi_it.Done(); phi_it.Advance()) {
1744          HPhi* phi = phi_it.Current()->AsPhi();
1745          phi->ReplaceWith(phi->InputAt(1 - this_index));
1746          successor->RemovePhi(phi);
1747        }
1748      } else {
1749        for (HInstructionIterator phi_it(successor->GetPhis()); !phi_it.Done(); phi_it.Advance()) {
1750          phi_it.Current()->AsPhi()->RemoveInputAt(this_index);
1751        }
1752      }
1753    }
1754  }
1755  successors_.clear();
1756
1757  // (3) Remove instructions and phis. Instructions should have no remaining uses
1758  //     except in catch phis. If an instruction is used by a catch phi at `index`,
1759  //     remove `index`-th input of all phis in the catch block since they are
1760  //     guaranteed dead. Note that we may miss dead inputs this way but the
1761  //     graph will always remain consistent.
1762  for (HBackwardInstructionIterator it(GetInstructions()); !it.Done(); it.Advance()) {
1763    HInstruction* insn = it.Current();
1764    RemoveUsesOfDeadInstruction(insn);
1765    RemoveInstruction(insn);
1766  }
1767  for (HInstructionIterator it(GetPhis()); !it.Done(); it.Advance()) {
1768    HPhi* insn = it.Current()->AsPhi();
1769    RemoveUsesOfDeadInstruction(insn);
1770    RemovePhi(insn);
1771  }
1772
1773  // (4) Disconnect the block from its predecessors and update their
1774  //     control-flow instructions.
1775  for (HBasicBlock* predecessor : predecessors_) {
1776    // We should not see any back edges as they would have been removed by step (3).
1777    DCHECK(!IsInLoop() || !GetLoopInformation()->IsBackEdge(*predecessor));
1778
1779    HInstruction* last_instruction = predecessor->GetLastInstruction();
1780    if (last_instruction->IsTryBoundary() && !IsCatchBlock()) {
1781      // This block is the only normal-flow successor of the TryBoundary which
1782      // makes `predecessor` dead. Since DCE removes blocks in post order,
1783      // exception handlers of this TryBoundary were already visited and any
1784      // remaining handlers therefore must be live. We remove `predecessor` from
1785      // their list of predecessors.
1786      DCHECK_EQ(last_instruction->AsTryBoundary()->GetNormalFlowSuccessor(), this);
1787      while (predecessor->GetSuccessors().size() > 1) {
1788        HBasicBlock* handler = predecessor->GetSuccessors()[1];
1789        DCHECK(handler->IsCatchBlock());
1790        predecessor->RemoveSuccessor(handler);
1791        handler->RemovePredecessor(predecessor);
1792      }
1793    }
1794
1795    predecessor->RemoveSuccessor(this);
1796    uint32_t num_pred_successors = predecessor->GetSuccessors().size();
1797    if (num_pred_successors == 1u) {
1798      // If we have one successor after removing one, then we must have
1799      // had an HIf, HPackedSwitch or HTryBoundary, as they have more than one
1800      // successor. Replace those with a HGoto.
1801      DCHECK(last_instruction->IsIf() ||
1802             last_instruction->IsPackedSwitch() ||
1803             (last_instruction->IsTryBoundary() && IsCatchBlock()));
1804      predecessor->RemoveInstruction(last_instruction);
1805      predecessor->AddInstruction(new (graph_->GetArena()) HGoto(last_instruction->GetDexPc()));
1806    } else if (num_pred_successors == 0u) {
1807      // The predecessor has no remaining successors and therefore must be dead.
1808      // We deliberately leave it without a control-flow instruction so that the
1809      // GraphChecker fails unless it is not removed during the pass too.
1810      predecessor->RemoveInstruction(last_instruction);
1811    } else {
1812      // There are multiple successors left. The removed block might be a successor
1813      // of a PackedSwitch which will be completely removed (perhaps replaced with
1814      // a Goto), or we are deleting a catch block from a TryBoundary. In either
1815      // case, leave `last_instruction` as is for now.
1816      DCHECK(last_instruction->IsPackedSwitch() ||
1817             (last_instruction->IsTryBoundary() && IsCatchBlock()));
1818    }
1819  }
1820  predecessors_.clear();
1821
1822  // (5) Remove the block from all loops it is included in. Skip the inner-most
1823  //     loop if this is the loop header (see definition of `loop_update_start`)
1824  //     because the loop header's predecessor list has been destroyed in step (4).
1825  for (HLoopInformationOutwardIterator it(*loop_update_start); !it.Done(); it.Advance()) {
1826    HLoopInformation* loop_info = it.Current();
1827    loop_info->Remove(this);
1828    if (loop_info->IsBackEdge(*this)) {
1829      // If this was the last back edge of the loop, we deliberately leave the
1830      // loop in an inconsistent state and will fail GraphChecker unless the
1831      // entire loop is removed during the pass.
1832      loop_info->RemoveBackEdge(this);
1833    }
1834  }
1835
1836  // (6) Disconnect from the dominator.
1837  dominator_->RemoveDominatedBlock(this);
1838  SetDominator(nullptr);
1839
1840  // (7) Delete from the graph, update reverse post order.
1841  graph_->DeleteDeadEmptyBlock(this);
1842  SetGraph(nullptr);
1843}
1844
1845void HBasicBlock::MergeWith(HBasicBlock* other) {
1846  DCHECK_EQ(GetGraph(), other->GetGraph());
1847  DCHECK(ContainsElement(dominated_blocks_, other));
1848  DCHECK_EQ(GetSingleSuccessor(), other);
1849  DCHECK_EQ(other->GetSinglePredecessor(), this);
1850  DCHECK(other->GetPhis().IsEmpty());
1851
1852  // Move instructions from `other` to `this`.
1853  DCHECK(EndsWithControlFlowInstruction());
1854  RemoveInstruction(GetLastInstruction());
1855  instructions_.Add(other->GetInstructions());
1856  other->instructions_.SetBlockOfInstructions(this);
1857  other->instructions_.Clear();
1858
1859  // Remove `other` from the loops it is included in.
1860  for (HLoopInformationOutwardIterator it(*other); !it.Done(); it.Advance()) {
1861    HLoopInformation* loop_info = it.Current();
1862    loop_info->Remove(other);
1863    if (loop_info->IsBackEdge(*other)) {
1864      loop_info->ReplaceBackEdge(other, this);
1865    }
1866  }
1867
1868  // Update links to the successors of `other`.
1869  successors_.clear();
1870  while (!other->successors_.empty()) {
1871    HBasicBlock* successor = other->GetSuccessors()[0];
1872    successor->ReplacePredecessor(other, this);
1873  }
1874
1875  // Update the dominator tree.
1876  RemoveDominatedBlock(other);
1877  for (HBasicBlock* dominated : other->GetDominatedBlocks()) {
1878    dominated_blocks_.push_back(dominated);
1879    dominated->SetDominator(this);
1880  }
1881  other->dominated_blocks_.clear();
1882  other->dominator_ = nullptr;
1883
1884  // Clear the list of predecessors of `other` in preparation of deleting it.
1885  other->predecessors_.clear();
1886
1887  // Delete `other` from the graph. The function updates reverse post order.
1888  graph_->DeleteDeadEmptyBlock(other);
1889  other->SetGraph(nullptr);
1890}
1891
1892void HBasicBlock::MergeWithInlined(HBasicBlock* other) {
1893  DCHECK_NE(GetGraph(), other->GetGraph());
1894  DCHECK(GetDominatedBlocks().empty());
1895  DCHECK(GetSuccessors().empty());
1896  DCHECK(!EndsWithControlFlowInstruction());
1897  DCHECK(other->GetSinglePredecessor()->IsEntryBlock());
1898  DCHECK(other->GetPhis().IsEmpty());
1899  DCHECK(!other->IsInLoop());
1900
1901  // Move instructions from `other` to `this`.
1902  instructions_.Add(other->GetInstructions());
1903  other->instructions_.SetBlockOfInstructions(this);
1904
1905  // Update links to the successors of `other`.
1906  successors_.clear();
1907  while (!other->successors_.empty()) {
1908    HBasicBlock* successor = other->GetSuccessors()[0];
1909    successor->ReplacePredecessor(other, this);
1910  }
1911
1912  // Update the dominator tree.
1913  for (HBasicBlock* dominated : other->GetDominatedBlocks()) {
1914    dominated_blocks_.push_back(dominated);
1915    dominated->SetDominator(this);
1916  }
1917  other->dominated_blocks_.clear();
1918  other->dominator_ = nullptr;
1919  other->graph_ = nullptr;
1920}
1921
1922void HBasicBlock::ReplaceWith(HBasicBlock* other) {
1923  while (!GetPredecessors().empty()) {
1924    HBasicBlock* predecessor = GetPredecessors()[0];
1925    predecessor->ReplaceSuccessor(this, other);
1926  }
1927  while (!GetSuccessors().empty()) {
1928    HBasicBlock* successor = GetSuccessors()[0];
1929    successor->ReplacePredecessor(this, other);
1930  }
1931  for (HBasicBlock* dominated : GetDominatedBlocks()) {
1932    other->AddDominatedBlock(dominated);
1933  }
1934  GetDominator()->ReplaceDominatedBlock(this, other);
1935  other->SetDominator(GetDominator());
1936  dominator_ = nullptr;
1937  graph_ = nullptr;
1938}
1939
1940void HGraph::DeleteDeadEmptyBlock(HBasicBlock* block) {
1941  DCHECK_EQ(block->GetGraph(), this);
1942  DCHECK(block->GetSuccessors().empty());
1943  DCHECK(block->GetPredecessors().empty());
1944  DCHECK(block->GetDominatedBlocks().empty());
1945  DCHECK(block->GetDominator() == nullptr);
1946  DCHECK(block->GetInstructions().IsEmpty());
1947  DCHECK(block->GetPhis().IsEmpty());
1948
1949  if (block->IsExitBlock()) {
1950    SetExitBlock(nullptr);
1951  }
1952
1953  RemoveElement(reverse_post_order_, block);
1954  blocks_[block->GetBlockId()] = nullptr;
1955  block->SetGraph(nullptr);
1956}
1957
1958void HGraph::UpdateLoopAndTryInformationOfNewBlock(HBasicBlock* block,
1959                                                   HBasicBlock* reference,
1960                                                   bool replace_if_back_edge) {
1961  if (block->IsLoopHeader()) {
1962    // Clear the information of which blocks are contained in that loop. Since the
1963    // information is stored as a bit vector based on block ids, we have to update
1964    // it, as those block ids were specific to the callee graph and we are now adding
1965    // these blocks to the caller graph.
1966    block->GetLoopInformation()->ClearAllBlocks();
1967  }
1968
1969  // If not already in a loop, update the loop information.
1970  if (!block->IsInLoop()) {
1971    block->SetLoopInformation(reference->GetLoopInformation());
1972  }
1973
1974  // If the block is in a loop, update all its outward loops.
1975  HLoopInformation* loop_info = block->GetLoopInformation();
1976  if (loop_info != nullptr) {
1977    for (HLoopInformationOutwardIterator loop_it(*block);
1978         !loop_it.Done();
1979         loop_it.Advance()) {
1980      loop_it.Current()->Add(block);
1981    }
1982    if (replace_if_back_edge && loop_info->IsBackEdge(*reference)) {
1983      loop_info->ReplaceBackEdge(reference, block);
1984    }
1985  }
1986
1987  // Copy TryCatchInformation if `reference` is a try block, not if it is a catch block.
1988  TryCatchInformation* try_catch_info = reference->IsTryBlock()
1989      ? reference->GetTryCatchInformation()
1990      : nullptr;
1991  block->SetTryCatchInformation(try_catch_info);
1992}
1993
1994HInstruction* HGraph::InlineInto(HGraph* outer_graph, HInvoke* invoke) {
1995  DCHECK(HasExitBlock()) << "Unimplemented scenario";
1996  // Update the environments in this graph to have the invoke's environment
1997  // as parent.
1998  {
1999    HReversePostOrderIterator it(*this);
2000    it.Advance();  // Skip the entry block, we do not need to update the entry's suspend check.
2001    for (; !it.Done(); it.Advance()) {
2002      HBasicBlock* block = it.Current();
2003      for (HInstructionIterator instr_it(block->GetInstructions());
2004           !instr_it.Done();
2005           instr_it.Advance()) {
2006        HInstruction* current = instr_it.Current();
2007        if (current->NeedsEnvironment()) {
2008          DCHECK(current->HasEnvironment());
2009          current->GetEnvironment()->SetAndCopyParentChain(
2010              outer_graph->GetArena(), invoke->GetEnvironment());
2011        }
2012      }
2013    }
2014  }
2015  outer_graph->UpdateMaximumNumberOfOutVRegs(GetMaximumNumberOfOutVRegs());
2016  if (HasBoundsChecks()) {
2017    outer_graph->SetHasBoundsChecks(true);
2018  }
2019
2020  HInstruction* return_value = nullptr;
2021  if (GetBlocks().size() == 3) {
2022    // Simple case of an entry block, a body block, and an exit block.
2023    // Put the body block's instruction into `invoke`'s block.
2024    HBasicBlock* body = GetBlocks()[1];
2025    DCHECK(GetBlocks()[0]->IsEntryBlock());
2026    DCHECK(GetBlocks()[2]->IsExitBlock());
2027    DCHECK(!body->IsExitBlock());
2028    DCHECK(!body->IsInLoop());
2029    HInstruction* last = body->GetLastInstruction();
2030
2031    // Note that we add instructions before the invoke only to simplify polymorphic inlining.
2032    invoke->GetBlock()->instructions_.AddBefore(invoke, body->GetInstructions());
2033    body->GetInstructions().SetBlockOfInstructions(invoke->GetBlock());
2034
2035    // Replace the invoke with the return value of the inlined graph.
2036    if (last->IsReturn()) {
2037      return_value = last->InputAt(0);
2038    } else {
2039      DCHECK(last->IsReturnVoid());
2040    }
2041
2042    invoke->GetBlock()->RemoveInstruction(last);
2043  } else {
2044    // Need to inline multiple blocks. We split `invoke`'s block
2045    // into two blocks, merge the first block of the inlined graph into
2046    // the first half, and replace the exit block of the inlined graph
2047    // with the second half.
2048    ArenaAllocator* allocator = outer_graph->GetArena();
2049    HBasicBlock* at = invoke->GetBlock();
2050    // Note that we split before the invoke only to simplify polymorphic inlining.
2051    HBasicBlock* to = at->SplitBeforeForInlining(invoke);
2052
2053    HBasicBlock* first = entry_block_->GetSuccessors()[0];
2054    DCHECK(!first->IsInLoop());
2055    at->MergeWithInlined(first);
2056    exit_block_->ReplaceWith(to);
2057
2058    // Update the meta information surrounding blocks:
2059    // (1) the graph they are now in,
2060    // (2) the reverse post order of that graph,
2061    // (3) their potential loop information, inner and outer,
2062    // (4) try block membership.
2063    // Note that we do not need to update catch phi inputs because they
2064    // correspond to the register file of the outer method which the inlinee
2065    // cannot modify.
2066
2067    // We don't add the entry block, the exit block, and the first block, which
2068    // has been merged with `at`.
2069    static constexpr int kNumberOfSkippedBlocksInCallee = 3;
2070
2071    // We add the `to` block.
2072    static constexpr int kNumberOfNewBlocksInCaller = 1;
2073    size_t blocks_added = (reverse_post_order_.size() - kNumberOfSkippedBlocksInCallee)
2074        + kNumberOfNewBlocksInCaller;
2075
2076    // Find the location of `at` in the outer graph's reverse post order. The new
2077    // blocks will be added after it.
2078    size_t index_of_at = IndexOfElement(outer_graph->reverse_post_order_, at);
2079    MakeRoomFor(&outer_graph->reverse_post_order_, blocks_added, index_of_at);
2080
2081    // Do a reverse post order of the blocks in the callee and do (1), (2), (3)
2082    // and (4) to the blocks that apply.
2083    for (HReversePostOrderIterator it(*this); !it.Done(); it.Advance()) {
2084      HBasicBlock* current = it.Current();
2085      if (current != exit_block_ && current != entry_block_ && current != first) {
2086        DCHECK(current->GetTryCatchInformation() == nullptr);
2087        DCHECK(current->GetGraph() == this);
2088        current->SetGraph(outer_graph);
2089        outer_graph->AddBlock(current);
2090        outer_graph->reverse_post_order_[++index_of_at] = current;
2091        UpdateLoopAndTryInformationOfNewBlock(current, at,  /* replace_if_back_edge */ false);
2092      }
2093    }
2094
2095    // Do (1), (2), (3) and (4) to `to`.
2096    to->SetGraph(outer_graph);
2097    outer_graph->AddBlock(to);
2098    outer_graph->reverse_post_order_[++index_of_at] = to;
2099    // Only `to` can become a back edge, as the inlined blocks
2100    // are predecessors of `to`.
2101    UpdateLoopAndTryInformationOfNewBlock(to, at, /* replace_if_back_edge */ true);
2102
2103    // Update all predecessors of the exit block (now the `to` block)
2104    // to not `HReturn` but `HGoto` instead.
2105    bool returns_void = to->GetPredecessors()[0]->GetLastInstruction()->IsReturnVoid();
2106    if (to->GetPredecessors().size() == 1) {
2107      HBasicBlock* predecessor = to->GetPredecessors()[0];
2108      HInstruction* last = predecessor->GetLastInstruction();
2109      if (!returns_void) {
2110        return_value = last->InputAt(0);
2111      }
2112      predecessor->AddInstruction(new (allocator) HGoto(last->GetDexPc()));
2113      predecessor->RemoveInstruction(last);
2114    } else {
2115      if (!returns_void) {
2116        // There will be multiple returns.
2117        return_value = new (allocator) HPhi(
2118            allocator, kNoRegNumber, 0, HPhi::ToPhiType(invoke->GetType()), to->GetDexPc());
2119        to->AddPhi(return_value->AsPhi());
2120      }
2121      for (HBasicBlock* predecessor : to->GetPredecessors()) {
2122        HInstruction* last = predecessor->GetLastInstruction();
2123        if (!returns_void) {
2124          DCHECK(last->IsReturn());
2125          return_value->AsPhi()->AddInput(last->InputAt(0));
2126        }
2127        predecessor->AddInstruction(new (allocator) HGoto(last->GetDexPc()));
2128        predecessor->RemoveInstruction(last);
2129      }
2130    }
2131  }
2132
2133  // Walk over the entry block and:
2134  // - Move constants from the entry block to the outer_graph's entry block,
2135  // - Replace HParameterValue instructions with their real value.
2136  // - Remove suspend checks, that hold an environment.
2137  // We must do this after the other blocks have been inlined, otherwise ids of
2138  // constants could overlap with the inner graph.
2139  size_t parameter_index = 0;
2140  for (HInstructionIterator it(entry_block_->GetInstructions()); !it.Done(); it.Advance()) {
2141    HInstruction* current = it.Current();
2142    HInstruction* replacement = nullptr;
2143    if (current->IsNullConstant()) {
2144      replacement = outer_graph->GetNullConstant(current->GetDexPc());
2145    } else if (current->IsIntConstant()) {
2146      replacement = outer_graph->GetIntConstant(
2147          current->AsIntConstant()->GetValue(), current->GetDexPc());
2148    } else if (current->IsLongConstant()) {
2149      replacement = outer_graph->GetLongConstant(
2150          current->AsLongConstant()->GetValue(), current->GetDexPc());
2151    } else if (current->IsFloatConstant()) {
2152      replacement = outer_graph->GetFloatConstant(
2153          current->AsFloatConstant()->GetValue(), current->GetDexPc());
2154    } else if (current->IsDoubleConstant()) {
2155      replacement = outer_graph->GetDoubleConstant(
2156          current->AsDoubleConstant()->GetValue(), current->GetDexPc());
2157    } else if (current->IsParameterValue()) {
2158      if (kIsDebugBuild
2159          && invoke->IsInvokeStaticOrDirect()
2160          && invoke->AsInvokeStaticOrDirect()->IsStaticWithExplicitClinitCheck()) {
2161        // Ensure we do not use the last input of `invoke`, as it
2162        // contains a clinit check which is not an actual argument.
2163        size_t last_input_index = invoke->InputCount() - 1;
2164        DCHECK(parameter_index != last_input_index);
2165      }
2166      replacement = invoke->InputAt(parameter_index++);
2167    } else if (current->IsCurrentMethod()) {
2168      replacement = outer_graph->GetCurrentMethod();
2169    } else {
2170      DCHECK(current->IsGoto() || current->IsSuspendCheck());
2171      entry_block_->RemoveInstruction(current);
2172    }
2173    if (replacement != nullptr) {
2174      current->ReplaceWith(replacement);
2175      // If the current is the return value then we need to update the latter.
2176      if (current == return_value) {
2177        DCHECK_EQ(entry_block_, return_value->GetBlock());
2178        return_value = replacement;
2179      }
2180    }
2181  }
2182
2183  return return_value;
2184}
2185
2186/*
2187 * Loop will be transformed to:
2188 *       old_pre_header
2189 *             |
2190 *          if_block
2191 *           /    \
2192 *  true_block   false_block
2193 *           \    /
2194 *       new_pre_header
2195 *             |
2196 *           header
2197 */
2198void HGraph::TransformLoopHeaderForBCE(HBasicBlock* header) {
2199  DCHECK(header->IsLoopHeader());
2200  HBasicBlock* old_pre_header = header->GetDominator();
2201
2202  // Need extra block to avoid critical edge.
2203  HBasicBlock* if_block = new (arena_) HBasicBlock(this, header->GetDexPc());
2204  HBasicBlock* true_block = new (arena_) HBasicBlock(this, header->GetDexPc());
2205  HBasicBlock* false_block = new (arena_) HBasicBlock(this, header->GetDexPc());
2206  HBasicBlock* new_pre_header = new (arena_) HBasicBlock(this, header->GetDexPc());
2207  AddBlock(if_block);
2208  AddBlock(true_block);
2209  AddBlock(false_block);
2210  AddBlock(new_pre_header);
2211
2212  header->ReplacePredecessor(old_pre_header, new_pre_header);
2213  old_pre_header->successors_.clear();
2214  old_pre_header->dominated_blocks_.clear();
2215
2216  old_pre_header->AddSuccessor(if_block);
2217  if_block->AddSuccessor(true_block);  // True successor
2218  if_block->AddSuccessor(false_block);  // False successor
2219  true_block->AddSuccessor(new_pre_header);
2220  false_block->AddSuccessor(new_pre_header);
2221
2222  old_pre_header->dominated_blocks_.push_back(if_block);
2223  if_block->SetDominator(old_pre_header);
2224  if_block->dominated_blocks_.push_back(true_block);
2225  true_block->SetDominator(if_block);
2226  if_block->dominated_blocks_.push_back(false_block);
2227  false_block->SetDominator(if_block);
2228  if_block->dominated_blocks_.push_back(new_pre_header);
2229  new_pre_header->SetDominator(if_block);
2230  new_pre_header->dominated_blocks_.push_back(header);
2231  header->SetDominator(new_pre_header);
2232
2233  // Fix reverse post order.
2234  size_t index_of_header = IndexOfElement(reverse_post_order_, header);
2235  MakeRoomFor(&reverse_post_order_, 4, index_of_header - 1);
2236  reverse_post_order_[index_of_header++] = if_block;
2237  reverse_post_order_[index_of_header++] = true_block;
2238  reverse_post_order_[index_of_header++] = false_block;
2239  reverse_post_order_[index_of_header++] = new_pre_header;
2240
2241  // The pre_header can never be a back edge of a loop.
2242  DCHECK((old_pre_header->GetLoopInformation() == nullptr) ||
2243         !old_pre_header->GetLoopInformation()->IsBackEdge(*old_pre_header));
2244  UpdateLoopAndTryInformationOfNewBlock(
2245      if_block, old_pre_header, /* replace_if_back_edge */ false);
2246  UpdateLoopAndTryInformationOfNewBlock(
2247      true_block, old_pre_header, /* replace_if_back_edge */ false);
2248  UpdateLoopAndTryInformationOfNewBlock(
2249      false_block, old_pre_header, /* replace_if_back_edge */ false);
2250  UpdateLoopAndTryInformationOfNewBlock(
2251      new_pre_header, old_pre_header, /* replace_if_back_edge */ false);
2252}
2253
2254static void CheckAgainstUpperBound(ReferenceTypeInfo rti, ReferenceTypeInfo upper_bound_rti)
2255    SHARED_REQUIRES(Locks::mutator_lock_) {
2256  if (rti.IsValid()) {
2257    DCHECK(upper_bound_rti.IsSupertypeOf(rti))
2258        << " upper_bound_rti: " << upper_bound_rti
2259        << " rti: " << rti;
2260    DCHECK(!upper_bound_rti.GetTypeHandle()->CannotBeAssignedFromOtherTypes() || rti.IsExact())
2261        << " upper_bound_rti: " << upper_bound_rti
2262        << " rti: " << rti;
2263  }
2264}
2265
2266void HInstruction::SetReferenceTypeInfo(ReferenceTypeInfo rti) {
2267  if (kIsDebugBuild) {
2268    DCHECK_EQ(GetType(), Primitive::kPrimNot);
2269    ScopedObjectAccess soa(Thread::Current());
2270    DCHECK(rti.IsValid()) << "Invalid RTI for " << DebugName();
2271    if (IsBoundType()) {
2272      // Having the test here spares us from making the method virtual just for
2273      // the sake of a DCHECK.
2274      CheckAgainstUpperBound(rti, AsBoundType()->GetUpperBound());
2275    }
2276  }
2277  reference_type_handle_ = rti.GetTypeHandle();
2278  SetPackedFlag<kFlagReferenceTypeIsExact>(rti.IsExact());
2279}
2280
2281void HBoundType::SetUpperBound(const ReferenceTypeInfo& upper_bound, bool can_be_null) {
2282  if (kIsDebugBuild) {
2283    ScopedObjectAccess soa(Thread::Current());
2284    DCHECK(upper_bound.IsValid());
2285    DCHECK(!upper_bound_.IsValid()) << "Upper bound should only be set once.";
2286    CheckAgainstUpperBound(GetReferenceTypeInfo(), upper_bound);
2287  }
2288  upper_bound_ = upper_bound;
2289  SetPackedFlag<kFlagUpperCanBeNull>(can_be_null);
2290}
2291
2292ReferenceTypeInfo ReferenceTypeInfo::Create(TypeHandle type_handle, bool is_exact) {
2293  if (kIsDebugBuild) {
2294    ScopedObjectAccess soa(Thread::Current());
2295    DCHECK(IsValidHandle(type_handle));
2296    if (!is_exact) {
2297      DCHECK(!type_handle->CannotBeAssignedFromOtherTypes())
2298          << "Callers of ReferenceTypeInfo::Create should ensure is_exact is properly computed";
2299    }
2300  }
2301  return ReferenceTypeInfo(type_handle, is_exact);
2302}
2303
2304std::ostream& operator<<(std::ostream& os, const ReferenceTypeInfo& rhs) {
2305  ScopedObjectAccess soa(Thread::Current());
2306  os << "["
2307     << " is_valid=" << rhs.IsValid()
2308     << " type=" << (!rhs.IsValid() ? "?" : PrettyClass(rhs.GetTypeHandle().Get()))
2309     << " is_exact=" << rhs.IsExact()
2310     << " ]";
2311  return os;
2312}
2313
2314bool HInstruction::HasAnyEnvironmentUseBefore(HInstruction* other) {
2315  // For now, assume that instructions in different blocks may use the
2316  // environment.
2317  // TODO: Use the control flow to decide if this is true.
2318  if (GetBlock() != other->GetBlock()) {
2319    return true;
2320  }
2321
2322  // We know that we are in the same block. Walk from 'this' to 'other',
2323  // checking to see if there is any instruction with an environment.
2324  HInstruction* current = this;
2325  for (; current != other && current != nullptr; current = current->GetNext()) {
2326    // This is a conservative check, as the instruction result may not be in
2327    // the referenced environment.
2328    if (current->HasEnvironment()) {
2329      return true;
2330    }
2331  }
2332
2333  // We should have been called with 'this' before 'other' in the block.
2334  // Just confirm this.
2335  DCHECK(current != nullptr);
2336  return false;
2337}
2338
2339void HInvoke::SetIntrinsic(Intrinsics intrinsic,
2340                           IntrinsicNeedsEnvironmentOrCache needs_env_or_cache,
2341                           IntrinsicSideEffects side_effects,
2342                           IntrinsicExceptions exceptions) {
2343  intrinsic_ = intrinsic;
2344  IntrinsicOptimizations opt(this);
2345
2346  // Adjust method's side effects from intrinsic table.
2347  switch (side_effects) {
2348    case kNoSideEffects: SetSideEffects(SideEffects::None()); break;
2349    case kReadSideEffects: SetSideEffects(SideEffects::AllReads()); break;
2350    case kWriteSideEffects: SetSideEffects(SideEffects::AllWrites()); break;
2351    case kAllSideEffects: SetSideEffects(SideEffects::AllExceptGCDependency()); break;
2352  }
2353
2354  if (needs_env_or_cache == kNoEnvironmentOrCache) {
2355    opt.SetDoesNotNeedDexCache();
2356    opt.SetDoesNotNeedEnvironment();
2357  } else {
2358    // If we need an environment, that means there will be a call, which can trigger GC.
2359    SetSideEffects(GetSideEffects().Union(SideEffects::CanTriggerGC()));
2360  }
2361  // Adjust method's exception status from intrinsic table.
2362  SetCanThrow(exceptions == kCanThrow);
2363}
2364
2365bool HNewInstance::IsStringAlloc() const {
2366  ScopedObjectAccess soa(Thread::Current());
2367  return GetReferenceTypeInfo().IsStringClass();
2368}
2369
2370bool HInvoke::NeedsEnvironment() const {
2371  if (!IsIntrinsic()) {
2372    return true;
2373  }
2374  IntrinsicOptimizations opt(*this);
2375  return !opt.GetDoesNotNeedEnvironment();
2376}
2377
2378bool HInvokeStaticOrDirect::NeedsDexCacheOfDeclaringClass() const {
2379  if (GetMethodLoadKind() != MethodLoadKind::kDexCacheViaMethod) {
2380    return false;
2381  }
2382  if (!IsIntrinsic()) {
2383    return true;
2384  }
2385  IntrinsicOptimizations opt(*this);
2386  return !opt.GetDoesNotNeedDexCache();
2387}
2388
2389void HInvokeStaticOrDirect::InsertInputAt(size_t index, HInstruction* input) {
2390  inputs_.insert(inputs_.begin() + index, HUserRecord<HInstruction*>(input));
2391  input->AddUseAt(this, index);
2392  // Update indexes in use nodes of inputs that have been pushed further back by the insert().
2393  for (size_t i = index + 1u, size = inputs_.size(); i != size; ++i) {
2394    DCHECK_EQ(InputRecordAt(i).GetUseNode()->GetIndex(), i - 1u);
2395    InputRecordAt(i).GetUseNode()->SetIndex(i);
2396  }
2397}
2398
2399void HInvokeStaticOrDirect::RemoveInputAt(size_t index) {
2400  RemoveAsUserOfInput(index);
2401  inputs_.erase(inputs_.begin() + index);
2402  // Update indexes in use nodes of inputs that have been pulled forward by the erase().
2403  for (size_t i = index, e = InputCount(); i < e; ++i) {
2404    DCHECK_EQ(InputRecordAt(i).GetUseNode()->GetIndex(), i + 1u);
2405    InputRecordAt(i).GetUseNode()->SetIndex(i);
2406  }
2407}
2408
2409std::ostream& operator<<(std::ostream& os, HInvokeStaticOrDirect::MethodLoadKind rhs) {
2410  switch (rhs) {
2411    case HInvokeStaticOrDirect::MethodLoadKind::kStringInit:
2412      return os << "string_init";
2413    case HInvokeStaticOrDirect::MethodLoadKind::kRecursive:
2414      return os << "recursive";
2415    case HInvokeStaticOrDirect::MethodLoadKind::kDirectAddress:
2416      return os << "direct";
2417    case HInvokeStaticOrDirect::MethodLoadKind::kDirectAddressWithFixup:
2418      return os << "direct_fixup";
2419    case HInvokeStaticOrDirect::MethodLoadKind::kDexCachePcRelative:
2420      return os << "dex_cache_pc_relative";
2421    case HInvokeStaticOrDirect::MethodLoadKind::kDexCacheViaMethod:
2422      return os << "dex_cache_via_method";
2423    default:
2424      LOG(FATAL) << "Unknown MethodLoadKind: " << static_cast<int>(rhs);
2425      UNREACHABLE();
2426  }
2427}
2428
2429std::ostream& operator<<(std::ostream& os, HInvokeStaticOrDirect::ClinitCheckRequirement rhs) {
2430  switch (rhs) {
2431    case HInvokeStaticOrDirect::ClinitCheckRequirement::kExplicit:
2432      return os << "explicit";
2433    case HInvokeStaticOrDirect::ClinitCheckRequirement::kImplicit:
2434      return os << "implicit";
2435    case HInvokeStaticOrDirect::ClinitCheckRequirement::kNone:
2436      return os << "none";
2437    default:
2438      LOG(FATAL) << "Unknown ClinitCheckRequirement: " << static_cast<int>(rhs);
2439      UNREACHABLE();
2440  }
2441}
2442
2443bool HLoadString::InstructionDataEquals(HInstruction* other) const {
2444  HLoadString* other_load_string = other->AsLoadString();
2445  if (string_index_ != other_load_string->string_index_ ||
2446      GetPackedFields() != other_load_string->GetPackedFields()) {
2447    return false;
2448  }
2449  LoadKind load_kind = GetLoadKind();
2450  if (HasAddress(load_kind)) {
2451    return GetAddress() == other_load_string->GetAddress();
2452  } else if (HasStringReference(load_kind)) {
2453    return IsSameDexFile(GetDexFile(), other_load_string->GetDexFile());
2454  } else {
2455    DCHECK(HasDexCacheReference(load_kind)) << load_kind;
2456    // If the string indexes and dex files are the same, dex cache element offsets
2457    // must also be the same, so we don't need to compare them.
2458    return IsSameDexFile(GetDexFile(), other_load_string->GetDexFile());
2459  }
2460}
2461
2462void HLoadString::SetLoadKindInternal(LoadKind load_kind) {
2463  // Once sharpened, the load kind should not be changed again.
2464  DCHECK_EQ(GetLoadKind(), LoadKind::kDexCacheViaMethod);
2465  SetPackedField<LoadKindField>(load_kind);
2466
2467  if (load_kind != LoadKind::kDexCacheViaMethod) {
2468    RemoveAsUserOfInput(0u);
2469    SetRawInputAt(0u, nullptr);
2470  }
2471  if (!NeedsEnvironment()) {
2472    RemoveEnvironment();
2473    SetSideEffects(SideEffects::None());
2474  }
2475}
2476
2477std::ostream& operator<<(std::ostream& os, HLoadString::LoadKind rhs) {
2478  switch (rhs) {
2479    case HLoadString::LoadKind::kBootImageLinkTimeAddress:
2480      return os << "BootImageLinkTimeAddress";
2481    case HLoadString::LoadKind::kBootImageLinkTimePcRelative:
2482      return os << "BootImageLinkTimePcRelative";
2483    case HLoadString::LoadKind::kBootImageAddress:
2484      return os << "BootImageAddress";
2485    case HLoadString::LoadKind::kDexCacheAddress:
2486      return os << "DexCacheAddress";
2487    case HLoadString::LoadKind::kDexCachePcRelative:
2488      return os << "DexCachePcRelative";
2489    case HLoadString::LoadKind::kDexCacheViaMethod:
2490      return os << "DexCacheViaMethod";
2491    default:
2492      LOG(FATAL) << "Unknown HLoadString::LoadKind: " << static_cast<int>(rhs);
2493      UNREACHABLE();
2494  }
2495}
2496
2497void HInstruction::RemoveEnvironmentUsers() {
2498  for (const HUseListNode<HEnvironment*>& use : GetEnvUses()) {
2499    HEnvironment* user = use.GetUser();
2500    user->SetRawEnvAt(use.GetIndex(), nullptr);
2501  }
2502  env_uses_.clear();
2503}
2504
2505// Returns an instruction with the opposite Boolean value from 'cond'.
2506HInstruction* HGraph::InsertOppositeCondition(HInstruction* cond, HInstruction* cursor) {
2507  ArenaAllocator* allocator = GetArena();
2508
2509  if (cond->IsCondition() &&
2510      !Primitive::IsFloatingPointType(cond->InputAt(0)->GetType())) {
2511    // Can't reverse floating point conditions.  We have to use HBooleanNot in that case.
2512    HInstruction* lhs = cond->InputAt(0);
2513    HInstruction* rhs = cond->InputAt(1);
2514    HInstruction* replacement = nullptr;
2515    switch (cond->AsCondition()->GetOppositeCondition()) {  // get *opposite*
2516      case kCondEQ: replacement = new (allocator) HEqual(lhs, rhs); break;
2517      case kCondNE: replacement = new (allocator) HNotEqual(lhs, rhs); break;
2518      case kCondLT: replacement = new (allocator) HLessThan(lhs, rhs); break;
2519      case kCondLE: replacement = new (allocator) HLessThanOrEqual(lhs, rhs); break;
2520      case kCondGT: replacement = new (allocator) HGreaterThan(lhs, rhs); break;
2521      case kCondGE: replacement = new (allocator) HGreaterThanOrEqual(lhs, rhs); break;
2522      case kCondB:  replacement = new (allocator) HBelow(lhs, rhs); break;
2523      case kCondBE: replacement = new (allocator) HBelowOrEqual(lhs, rhs); break;
2524      case kCondA:  replacement = new (allocator) HAbove(lhs, rhs); break;
2525      case kCondAE: replacement = new (allocator) HAboveOrEqual(lhs, rhs); break;
2526      default:
2527        LOG(FATAL) << "Unexpected condition";
2528        UNREACHABLE();
2529    }
2530    cursor->GetBlock()->InsertInstructionBefore(replacement, cursor);
2531    return replacement;
2532  } else if (cond->IsIntConstant()) {
2533    HIntConstant* int_const = cond->AsIntConstant();
2534    if (int_const->IsFalse()) {
2535      return GetIntConstant(1);
2536    } else {
2537      DCHECK(int_const->IsTrue()) << int_const->GetValue();
2538      return GetIntConstant(0);
2539    }
2540  } else {
2541    HInstruction* replacement = new (allocator) HBooleanNot(cond);
2542    cursor->GetBlock()->InsertInstructionBefore(replacement, cursor);
2543    return replacement;
2544  }
2545}
2546
2547std::ostream& operator<<(std::ostream& os, const MoveOperands& rhs) {
2548  os << "["
2549     << " source=" << rhs.GetSource()
2550     << " destination=" << rhs.GetDestination()
2551     << " type=" << rhs.GetType()
2552     << " instruction=";
2553  if (rhs.GetInstruction() != nullptr) {
2554    os << rhs.GetInstruction()->DebugName() << ' ' << rhs.GetInstruction()->GetId();
2555  } else {
2556    os << "null";
2557  }
2558  os << " ]";
2559  return os;
2560}
2561
2562std::ostream& operator<<(std::ostream& os, TypeCheckKind rhs) {
2563  switch (rhs) {
2564    case TypeCheckKind::kUnresolvedCheck:
2565      return os << "unresolved_check";
2566    case TypeCheckKind::kExactCheck:
2567      return os << "exact_check";
2568    case TypeCheckKind::kClassHierarchyCheck:
2569      return os << "class_hierarchy_check";
2570    case TypeCheckKind::kAbstractClassCheck:
2571      return os << "abstract_class_check";
2572    case TypeCheckKind::kInterfaceCheck:
2573      return os << "interface_check";
2574    case TypeCheckKind::kArrayObjectCheck:
2575      return os << "array_object_check";
2576    case TypeCheckKind::kArrayCheck:
2577      return os << "array_check";
2578    default:
2579      LOG(FATAL) << "Unknown TypeCheckKind: " << static_cast<int>(rhs);
2580      UNREACHABLE();
2581  }
2582}
2583
2584}  // namespace art
2585