Home | History | Annotate | Download | only in optimizing
      1 /*
      2  * Copyright (C) 2016 The Android Open Source Project
      3  *
      4  * Licensed under the Apache License, Version 2.0 (the "License");
      5  * you may not use this file except in compliance with the License.
      6  * You may obtain a copy of the License at
      7  *
      8  *      http://www.apache.org/licenses/LICENSE-2.0
      9  *
     10  * Unless required by applicable law or agreed to in writing, software
     11  * distributed under the License is distributed on an "AS IS" BASIS,
     12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
     13  * See the License for the specific language governing permissions and
     14  * limitations under the License.
     15  */
     16 
     17 #include "register_allocation_resolver.h"
     18 
     19 #include "base/bit_vector-inl.h"
     20 #include "code_generator.h"
     21 #include "linear_order.h"
     22 #include "ssa_liveness_analysis.h"
     23 
     24 namespace art {
     25 
     26 RegisterAllocationResolver::RegisterAllocationResolver(CodeGenerator* codegen,
     27                                                        const SsaLivenessAnalysis& liveness)
     28       : allocator_(codegen->GetGraph()->GetAllocator()),
     29         codegen_(codegen),
     30         liveness_(liveness) {}
     31 
     32 void RegisterAllocationResolver::Resolve(ArrayRef<HInstruction* const> safepoints,
     33                                          size_t reserved_out_slots,
     34                                          size_t int_spill_slots,
     35                                          size_t long_spill_slots,
     36                                          size_t float_spill_slots,
     37                                          size_t double_spill_slots,
     38                                          size_t catch_phi_spill_slots,
     39                                          ArrayRef<LiveInterval* const> temp_intervals) {
     40   size_t spill_slots = int_spill_slots
     41                      + long_spill_slots
     42                      + float_spill_slots
     43                      + double_spill_slots
     44                      + catch_phi_spill_slots;
     45 
     46   // Update safepoints and calculate the size of the spills.
     47   UpdateSafepointLiveRegisters();
     48   size_t maximum_safepoint_spill_size = CalculateMaximumSafepointSpillSize(safepoints);
     49 
     50   // Computes frame size and spill mask.
     51   codegen_->InitializeCodeGeneration(spill_slots,
     52                                      maximum_safepoint_spill_size,
     53                                      reserved_out_slots,  // Includes slot(s) for the art method.
     54                                      codegen_->GetGraph()->GetLinearOrder());
     55 
     56   // Resolve outputs, including stack locations.
     57   // TODO: Use pointers of Location inside LiveInterval to avoid doing another iteration.
     58   for (size_t i = 0, e = liveness_.GetNumberOfSsaValues(); i < e; ++i) {
     59     HInstruction* instruction = liveness_.GetInstructionFromSsaIndex(i);
     60     LiveInterval* current = instruction->GetLiveInterval();
     61     LocationSummary* locations = instruction->GetLocations();
     62     Location location = locations->Out();
     63     if (instruction->IsParameterValue()) {
     64       // Now that we know the frame size, adjust the parameter's location.
     65       if (location.IsStackSlot()) {
     66         location = Location::StackSlot(location.GetStackIndex() + codegen_->GetFrameSize());
     67         current->SetSpillSlot(location.GetStackIndex());
     68         locations->UpdateOut(location);
     69       } else if (location.IsDoubleStackSlot()) {
     70         location = Location::DoubleStackSlot(location.GetStackIndex() + codegen_->GetFrameSize());
     71         current->SetSpillSlot(location.GetStackIndex());
     72         locations->UpdateOut(location);
     73       } else if (current->HasSpillSlot()) {
     74         current->SetSpillSlot(current->GetSpillSlot() + codegen_->GetFrameSize());
     75       }
     76     } else if (instruction->IsCurrentMethod()) {
     77       // The current method is always at offset 0.
     78       DCHECK(!current->HasSpillSlot() || (current->GetSpillSlot() == 0));
     79     } else if (instruction->IsPhi() && instruction->AsPhi()->IsCatchPhi()) {
     80       DCHECK(current->HasSpillSlot());
     81       size_t slot = current->GetSpillSlot()
     82                     + spill_slots
     83                     + reserved_out_slots
     84                     - catch_phi_spill_slots;
     85       current->SetSpillSlot(slot * kVRegSize);
     86     } else if (current->HasSpillSlot()) {
     87       // Adjust the stack slot, now that we know the number of them for each type.
     88       // The way this implementation lays out the stack is the following:
     89       // [parameter slots       ]
     90       // [art method (caller)   ]
     91       // [entry spill (core)    ]
     92       // [entry spill (float)   ]
     93       // [should_deoptimize flag] (this is optional)
     94       // [catch phi spill slots ]
     95       // [double spill slots    ]
     96       // [long spill slots      ]
     97       // [float spill slots     ]
     98       // [int/ref values        ]
     99       // [maximum out values    ] (number of arguments for calls)
    100       // [art method            ].
    101       size_t slot = current->GetSpillSlot();
    102       switch (current->GetType()) {
    103         case DataType::Type::kFloat64:
    104           slot += long_spill_slots;
    105           FALLTHROUGH_INTENDED;
    106         case DataType::Type::kUint64:
    107         case DataType::Type::kInt64:
    108           slot += float_spill_slots;
    109           FALLTHROUGH_INTENDED;
    110         case DataType::Type::kFloat32:
    111           slot += int_spill_slots;
    112           FALLTHROUGH_INTENDED;
    113         case DataType::Type::kReference:
    114         case DataType::Type::kUint32:
    115         case DataType::Type::kInt32:
    116         case DataType::Type::kUint16:
    117         case DataType::Type::kUint8:
    118         case DataType::Type::kInt8:
    119         case DataType::Type::kBool:
    120         case DataType::Type::kInt16:
    121           slot += reserved_out_slots;
    122           break;
    123         case DataType::Type::kVoid:
    124           LOG(FATAL) << "Unexpected type for interval " << current->GetType();
    125       }
    126       current->SetSpillSlot(slot * kVRegSize);
    127     }
    128 
    129     Location source = current->ToLocation();
    130 
    131     if (location.IsUnallocated()) {
    132       if (location.GetPolicy() == Location::kSameAsFirstInput) {
    133         if (locations->InAt(0).IsUnallocated()) {
    134           locations->SetInAt(0, source);
    135         } else {
    136           DCHECK(locations->InAt(0).Equals(source));
    137         }
    138       }
    139       locations->UpdateOut(source);
    140     } else {
    141       DCHECK(source.Equals(location));
    142     }
    143   }
    144 
    145   // Connect siblings and resolve inputs.
    146   for (size_t i = 0, e = liveness_.GetNumberOfSsaValues(); i < e; ++i) {
    147     HInstruction* instruction = liveness_.GetInstructionFromSsaIndex(i);
    148     ConnectSiblings(instruction->GetLiveInterval());
    149   }
    150 
    151   // Resolve non-linear control flow across branches. Order does not matter.
    152   for (HBasicBlock* block : codegen_->GetGraph()->GetLinearOrder()) {
    153     if (block->IsCatchBlock() ||
    154         (block->IsLoopHeader() && block->GetLoopInformation()->IsIrreducible())) {
    155       // Instructions live at the top of catch blocks or irreducible loop header
    156       // were forced to spill.
    157       if (kIsDebugBuild) {
    158         BitVector* live = liveness_.GetLiveInSet(*block);
    159         for (uint32_t idx : live->Indexes()) {
    160           LiveInterval* interval = liveness_.GetInstructionFromSsaIndex(idx)->GetLiveInterval();
    161           LiveInterval* sibling = interval->GetSiblingAt(block->GetLifetimeStart());
    162           // `GetSiblingAt` returns the sibling that contains a position, but there could be
    163           // a lifetime hole in it. `CoversSlow` returns whether the interval is live at that
    164           // position.
    165           if ((sibling != nullptr) && sibling->CoversSlow(block->GetLifetimeStart())) {
    166             DCHECK(!sibling->HasRegister());
    167           }
    168         }
    169       }
    170     } else {
    171       BitVector* live = liveness_.GetLiveInSet(*block);
    172       for (uint32_t idx : live->Indexes()) {
    173         LiveInterval* interval = liveness_.GetInstructionFromSsaIndex(idx)->GetLiveInterval();
    174         for (HBasicBlock* predecessor : block->GetPredecessors()) {
    175           ConnectSplitSiblings(interval, predecessor, block);
    176         }
    177       }
    178     }
    179   }
    180 
    181   // Resolve phi inputs. Order does not matter.
    182   for (HBasicBlock* block : codegen_->GetGraph()->GetLinearOrder()) {
    183     if (block->IsCatchBlock()) {
    184       // Catch phi values are set at runtime by the exception delivery mechanism.
    185     } else {
    186       for (HInstructionIterator inst_it(block->GetPhis()); !inst_it.Done(); inst_it.Advance()) {
    187         HInstruction* phi = inst_it.Current();
    188         for (size_t i = 0, e = block->GetPredecessors().size(); i < e; ++i) {
    189           HBasicBlock* predecessor = block->GetPredecessors()[i];
    190           DCHECK_EQ(predecessor->GetNormalSuccessors().size(), 1u);
    191           HInstruction* input = phi->InputAt(i);
    192           Location source = input->GetLiveInterval()->GetLocationAt(
    193               predecessor->GetLifetimeEnd() - 1);
    194           Location destination = phi->GetLiveInterval()->ToLocation();
    195           InsertParallelMoveAtExitOf(predecessor, phi, source, destination);
    196         }
    197       }
    198     }
    199   }
    200 
    201   // Resolve temp locations.
    202   for (LiveInterval* temp : temp_intervals) {
    203     if (temp->IsHighInterval()) {
    204       // High intervals can be skipped, they are already handled by the low interval.
    205       continue;
    206     }
    207     HInstruction* at = liveness_.GetTempUser(temp);
    208     size_t temp_index = liveness_.GetTempIndex(temp);
    209     LocationSummary* locations = at->GetLocations();
    210     switch (temp->GetType()) {
    211       case DataType::Type::kInt32:
    212         locations->SetTempAt(temp_index, Location::RegisterLocation(temp->GetRegister()));
    213         break;
    214 
    215       case DataType::Type::kFloat64:
    216         if (codegen_->NeedsTwoRegisters(DataType::Type::kFloat64)) {
    217           Location location = Location::FpuRegisterPairLocation(
    218               temp->GetRegister(), temp->GetHighInterval()->GetRegister());
    219           locations->SetTempAt(temp_index, location);
    220         } else {
    221           locations->SetTempAt(temp_index, Location::FpuRegisterLocation(temp->GetRegister()));
    222         }
    223         break;
    224 
    225       default:
    226         LOG(FATAL) << "Unexpected type for temporary location "
    227                    << temp->GetType();
    228     }
    229   }
    230 }
    231 
    232 void RegisterAllocationResolver::UpdateSafepointLiveRegisters() {
    233   for (size_t i = 0, e = liveness_.GetNumberOfSsaValues(); i < e; ++i) {
    234     HInstruction* instruction = liveness_.GetInstructionFromSsaIndex(i);
    235     for (LiveInterval* current = instruction->GetLiveInterval();
    236          current != nullptr;
    237          current = current->GetNextSibling()) {
    238       if (!current->HasRegister()) {
    239         continue;
    240       }
    241       Location source = current->ToLocation();
    242       for (SafepointPosition* safepoint_position = current->GetFirstSafepoint();
    243            safepoint_position != nullptr;
    244            safepoint_position = safepoint_position->GetNext()) {
    245         DCHECK(current->CoversSlow(safepoint_position->GetPosition()));
    246         LocationSummary* locations = safepoint_position->GetLocations();
    247         switch (source.GetKind()) {
    248           case Location::kRegister:
    249           case Location::kFpuRegister: {
    250             locations->AddLiveRegister(source);
    251             break;
    252           }
    253           case Location::kRegisterPair:
    254           case Location::kFpuRegisterPair: {
    255             locations->AddLiveRegister(source.ToLow());
    256             locations->AddLiveRegister(source.ToHigh());
    257             break;
    258           }
    259           case Location::kStackSlot:  // Fall-through
    260           case Location::kDoubleStackSlot:  // Fall-through
    261           case Location::kConstant: {
    262             // Nothing to do.
    263             break;
    264           }
    265           default: {
    266             LOG(FATAL) << "Unexpected location for object";
    267           }
    268         }
    269       }
    270     }
    271   }
    272 }
    273 
    274 size_t RegisterAllocationResolver::CalculateMaximumSafepointSpillSize(
    275     ArrayRef<HInstruction* const> safepoints) {
    276   size_t core_register_spill_size = codegen_->GetWordSize();
    277   size_t fp_register_spill_size = codegen_->GetFloatingPointSpillSlotSize();
    278   size_t maximum_safepoint_spill_size = 0u;
    279   for (HInstruction* instruction : safepoints) {
    280     LocationSummary* locations = instruction->GetLocations();
    281     if (locations->OnlyCallsOnSlowPath()) {
    282       size_t core_spills =
    283           codegen_->GetNumberOfSlowPathSpills(locations, /* core_registers */ true);
    284       size_t fp_spills =
    285           codegen_->GetNumberOfSlowPathSpills(locations, /* core_registers */ false);
    286       size_t spill_size =
    287           core_register_spill_size * core_spills + fp_register_spill_size * fp_spills;
    288       maximum_safepoint_spill_size = std::max(maximum_safepoint_spill_size, spill_size);
    289     } else if (locations->CallsOnMainAndSlowPath()) {
    290       // Nothing to spill on the slow path if the main path already clobbers caller-saves.
    291       DCHECK_EQ(0u, codegen_->GetNumberOfSlowPathSpills(locations, /* core_registers */ true));
    292       DCHECK_EQ(0u, codegen_->GetNumberOfSlowPathSpills(locations, /* core_registers */ false));
    293     }
    294   }
    295   return maximum_safepoint_spill_size;
    296 }
    297 
    298 void RegisterAllocationResolver::ConnectSiblings(LiveInterval* interval) {
    299   LiveInterval* current = interval;
    300   if (current->HasSpillSlot()
    301       && current->HasRegister()
    302       // Currently, we spill unconditionnally the current method in the code generators.
    303       && !interval->GetDefinedBy()->IsCurrentMethod()) {
    304     // We spill eagerly, so move must be at definition.
    305     Location loc;
    306     switch (interval->NumberOfSpillSlotsNeeded()) {
    307       case 1: loc = Location::StackSlot(interval->GetParent()->GetSpillSlot()); break;
    308       case 2: loc = Location::DoubleStackSlot(interval->GetParent()->GetSpillSlot()); break;
    309       case 4: loc = Location::SIMDStackSlot(interval->GetParent()->GetSpillSlot()); break;
    310       default: LOG(FATAL) << "Unexpected number of spill slots"; UNREACHABLE();
    311     }
    312     InsertMoveAfter(interval->GetDefinedBy(), interval->ToLocation(), loc);
    313   }
    314   UsePositionList::const_iterator use_it = current->GetUses().begin();
    315   const UsePositionList::const_iterator use_end = current->GetUses().end();
    316   EnvUsePositionList::const_iterator env_use_it = current->GetEnvironmentUses().begin();
    317   const EnvUsePositionList::const_iterator env_use_end = current->GetEnvironmentUses().end();
    318 
    319   // Walk over all siblings, updating locations of use positions, and
    320   // connecting them when they are adjacent.
    321   do {
    322     Location source = current->ToLocation();
    323 
    324     // Walk over all uses covered by this interval, and update the location
    325     // information.
    326 
    327     LiveRange* range = current->GetFirstRange();
    328     while (range != nullptr) {
    329       // Process uses in the closed interval [range->GetStart(), range->GetEnd()].
    330       // FindMatchingUseRange() expects a half-open interval, so pass `range->GetEnd() + 1u`.
    331       size_t range_begin = range->GetStart();
    332       size_t range_end = range->GetEnd() + 1u;
    333       auto matching_use_range =
    334           FindMatchingUseRange(use_it, use_end, range_begin, range_end);
    335       DCHECK(std::all_of(use_it,
    336                          matching_use_range.begin(),
    337                          [](const UsePosition& pos) { return pos.IsSynthesized(); }));
    338       for (const UsePosition& use : matching_use_range) {
    339         DCHECK(current->CoversSlow(use.GetPosition()) || (use.GetPosition() == range->GetEnd()));
    340         if (!use.IsSynthesized()) {
    341           LocationSummary* locations = use.GetUser()->GetLocations();
    342           Location expected_location = locations->InAt(use.GetInputIndex());
    343           // The expected (actual) location may be invalid in case the input is unused. Currently
    344           // this only happens for intrinsics.
    345           if (expected_location.IsValid()) {
    346             if (expected_location.IsUnallocated()) {
    347               locations->SetInAt(use.GetInputIndex(), source);
    348             } else if (!expected_location.IsConstant()) {
    349               AddInputMoveFor(
    350                   interval->GetDefinedBy(), use.GetUser(), source, expected_location);
    351             }
    352           } else {
    353             DCHECK(use.GetUser()->IsInvoke());
    354             DCHECK(use.GetUser()->AsInvoke()->GetIntrinsic() != Intrinsics::kNone);
    355           }
    356         }
    357       }
    358       use_it = matching_use_range.end();
    359 
    360       // Walk over the environment uses, and update their locations.
    361       auto matching_env_use_range =
    362           FindMatchingUseRange(env_use_it, env_use_end, range_begin, range_end);
    363       for (const EnvUsePosition& env_use : matching_env_use_range) {
    364         DCHECK(current->CoversSlow(env_use.GetPosition())
    365                || (env_use.GetPosition() == range->GetEnd()));
    366         HEnvironment* environment = env_use.GetEnvironment();
    367         environment->SetLocationAt(env_use.GetInputIndex(), source);
    368       }
    369       env_use_it = matching_env_use_range.end();
    370 
    371       range = range->GetNext();
    372     }
    373 
    374     // If the next interval starts just after this one, and has a register,
    375     // insert a move.
    376     LiveInterval* next_sibling = current->GetNextSibling();
    377     if (next_sibling != nullptr
    378         && next_sibling->HasRegister()
    379         && current->GetEnd() == next_sibling->GetStart()) {
    380       Location destination = next_sibling->ToLocation();
    381       InsertParallelMoveAt(current->GetEnd(), interval->GetDefinedBy(), source, destination);
    382     }
    383 
    384     for (SafepointPosition* safepoint_position = current->GetFirstSafepoint();
    385          safepoint_position != nullptr;
    386          safepoint_position = safepoint_position->GetNext()) {
    387       DCHECK(current->CoversSlow(safepoint_position->GetPosition()));
    388 
    389       if (current->GetType() == DataType::Type::kReference) {
    390         DCHECK(interval->GetDefinedBy()->IsActualObject())
    391             << interval->GetDefinedBy()->DebugName()
    392             << '(' << interval->GetDefinedBy()->GetId() << ')'
    393             << "@" << safepoint_position->GetInstruction()->DebugName()
    394             << '(' << safepoint_position->GetInstruction()->GetId() << ')';
    395         LocationSummary* locations = safepoint_position->GetLocations();
    396         if (current->GetParent()->HasSpillSlot()) {
    397           locations->SetStackBit(current->GetParent()->GetSpillSlot() / kVRegSize);
    398         }
    399         if (source.GetKind() == Location::kRegister) {
    400           locations->SetRegisterBit(source.reg());
    401         }
    402       }
    403     }
    404     current = next_sibling;
    405   } while (current != nullptr);
    406 
    407   // Following uses can only be synthesized uses.
    408   DCHECK(std::all_of(use_it, use_end, [](const UsePosition& pos) { return pos.IsSynthesized(); }));
    409 }
    410 
    411 static bool IsMaterializableEntryBlockInstructionOfGraphWithIrreducibleLoop(
    412     HInstruction* instruction) {
    413   return instruction->GetBlock()->GetGraph()->HasIrreducibleLoops() &&
    414          (instruction->IsConstant() || instruction->IsCurrentMethod());
    415 }
    416 
    417 void RegisterAllocationResolver::ConnectSplitSiblings(LiveInterval* interval,
    418                                                       HBasicBlock* from,
    419                                                       HBasicBlock* to) const {
    420   if (interval->GetNextSibling() == nullptr) {
    421     // Nothing to connect. The whole range was allocated to the same location.
    422     return;
    423   }
    424 
    425   // Find the intervals that cover `from` and `to`.
    426   size_t destination_position = to->GetLifetimeStart();
    427   size_t source_position = from->GetLifetimeEnd() - 1;
    428   LiveInterval* destination = interval->GetSiblingAt(destination_position);
    429   LiveInterval* source = interval->GetSiblingAt(source_position);
    430 
    431   if (destination == source) {
    432     // Interval was not split.
    433     return;
    434   }
    435 
    436   LiveInterval* parent = interval->GetParent();
    437   HInstruction* defined_by = parent->GetDefinedBy();
    438   if (codegen_->GetGraph()->HasIrreducibleLoops() &&
    439       (destination == nullptr || !destination->CoversSlow(destination_position))) {
    440     // Our live_in fixed point calculation has found that the instruction is live
    441     // in the `to` block because it will eventually enter an irreducible loop. Our
    442     // live interval computation however does not compute a fixed point, and
    443     // therefore will not have a location for that instruction for `to`.
    444     // Because the instruction is a constant or the ArtMethod, we don't need to
    445     // do anything: it will be materialized in the irreducible loop.
    446     DCHECK(IsMaterializableEntryBlockInstructionOfGraphWithIrreducibleLoop(defined_by))
    447         << defined_by->DebugName() << ":" << defined_by->GetId()
    448         << " " << from->GetBlockId() << " -> " << to->GetBlockId();
    449     return;
    450   }
    451 
    452   if (!destination->HasRegister()) {
    453     // Values are eagerly spilled. Spill slot already contains appropriate value.
    454     return;
    455   }
    456 
    457   Location location_source;
    458   // `GetSiblingAt` returns the interval whose start and end cover `position`,
    459   // but does not check whether the interval is inactive at that position.
    460   // The only situation where the interval is inactive at that position is in the
    461   // presence of irreducible loops for constants and ArtMethod.
    462   if (codegen_->GetGraph()->HasIrreducibleLoops() &&
    463       (source == nullptr || !source->CoversSlow(source_position))) {
    464     DCHECK(IsMaterializableEntryBlockInstructionOfGraphWithIrreducibleLoop(defined_by));
    465     if (defined_by->IsConstant()) {
    466       location_source = defined_by->GetLocations()->Out();
    467     } else {
    468       DCHECK(defined_by->IsCurrentMethod());
    469       switch (parent->NumberOfSpillSlotsNeeded()) {
    470         case 1: location_source = Location::StackSlot(parent->GetSpillSlot()); break;
    471         case 2: location_source = Location::DoubleStackSlot(parent->GetSpillSlot()); break;
    472         case 4: location_source = Location::SIMDStackSlot(parent->GetSpillSlot()); break;
    473         default: LOG(FATAL) << "Unexpected number of spill slots"; UNREACHABLE();
    474       }
    475     }
    476   } else {
    477     DCHECK(source != nullptr);
    478     DCHECK(source->CoversSlow(source_position));
    479     DCHECK(destination->CoversSlow(destination_position));
    480     location_source = source->ToLocation();
    481   }
    482 
    483   // If `from` has only one successor, we can put the moves at the exit of it. Otherwise
    484   // we need to put the moves at the entry of `to`.
    485   if (from->GetNormalSuccessors().size() == 1) {
    486     InsertParallelMoveAtExitOf(from,
    487                                defined_by,
    488                                location_source,
    489                                destination->ToLocation());
    490   } else {
    491     DCHECK_EQ(to->GetPredecessors().size(), 1u);
    492     InsertParallelMoveAtEntryOf(to,
    493                                 defined_by,
    494                                 location_source,
    495                                 destination->ToLocation());
    496   }
    497 }
    498 
    499 static bool IsValidDestination(Location destination) {
    500   return destination.IsRegister()
    501       || destination.IsRegisterPair()
    502       || destination.IsFpuRegister()
    503       || destination.IsFpuRegisterPair()
    504       || destination.IsStackSlot()
    505       || destination.IsDoubleStackSlot()
    506       || destination.IsSIMDStackSlot();
    507 }
    508 
    509 void RegisterAllocationResolver::AddMove(HParallelMove* move,
    510                                          Location source,
    511                                          Location destination,
    512                                          HInstruction* instruction,
    513                                          DataType::Type type) const {
    514   if (type == DataType::Type::kInt64
    515       && codegen_->ShouldSplitLongMoves()
    516       // The parallel move resolver knows how to deal with long constants.
    517       && !source.IsConstant()) {
    518     move->AddMove(source.ToLow(), destination.ToLow(), DataType::Type::kInt32, instruction);
    519     move->AddMove(source.ToHigh(), destination.ToHigh(), DataType::Type::kInt32, nullptr);
    520   } else {
    521     move->AddMove(source, destination, type, instruction);
    522   }
    523 }
    524 
    525 void RegisterAllocationResolver::AddInputMoveFor(HInstruction* input,
    526                                                  HInstruction* user,
    527                                                  Location source,
    528                                                  Location destination) const {
    529   if (source.Equals(destination)) return;
    530 
    531   DCHECK(!user->IsPhi());
    532 
    533   HInstruction* previous = user->GetPrevious();
    534   HParallelMove* move = nullptr;
    535   if (previous == nullptr
    536       || !previous->IsParallelMove()
    537       || previous->GetLifetimePosition() < user->GetLifetimePosition()) {
    538     move = new (allocator_) HParallelMove(allocator_);
    539     move->SetLifetimePosition(user->GetLifetimePosition());
    540     user->GetBlock()->InsertInstructionBefore(move, user);
    541   } else {
    542     move = previous->AsParallelMove();
    543   }
    544   DCHECK_EQ(move->GetLifetimePosition(), user->GetLifetimePosition());
    545   AddMove(move, source, destination, nullptr, input->GetType());
    546 }
    547 
    548 static bool IsInstructionStart(size_t position) {
    549   return (position & 1) == 0;
    550 }
    551 
    552 static bool IsInstructionEnd(size_t position) {
    553   return (position & 1) == 1;
    554 }
    555 
    556 void RegisterAllocationResolver::InsertParallelMoveAt(size_t position,
    557                                                       HInstruction* instruction,
    558                                                       Location source,
    559                                                       Location destination) const {
    560   DCHECK(IsValidDestination(destination)) << destination;
    561   if (source.Equals(destination)) return;
    562 
    563   HInstruction* at = liveness_.GetInstructionFromPosition(position / 2);
    564   HParallelMove* move;
    565   if (at == nullptr) {
    566     if (IsInstructionStart(position)) {
    567       // Block boundary, don't do anything the connection of split siblings will handle it.
    568       return;
    569     } else {
    570       // Move must happen before the first instruction of the block.
    571       at = liveness_.GetInstructionFromPosition((position + 1) / 2);
    572       // Note that parallel moves may have already been inserted, so we explicitly
    573       // ask for the first instruction of the block: `GetInstructionFromPosition` does
    574       // not contain the `HParallelMove` instructions.
    575       at = at->GetBlock()->GetFirstInstruction();
    576 
    577       if (at->GetLifetimePosition() < position) {
    578         // We may insert moves for split siblings and phi spills at the beginning of the block.
    579         // Since this is a different lifetime position, we need to go to the next instruction.
    580         DCHECK(at->IsParallelMove());
    581         at = at->GetNext();
    582       }
    583 
    584       if (at->GetLifetimePosition() != position) {
    585         DCHECK_GT(at->GetLifetimePosition(), position);
    586         move = new (allocator_) HParallelMove(allocator_);
    587         move->SetLifetimePosition(position);
    588         at->GetBlock()->InsertInstructionBefore(move, at);
    589       } else {
    590         DCHECK(at->IsParallelMove());
    591         move = at->AsParallelMove();
    592       }
    593     }
    594   } else if (IsInstructionEnd(position)) {
    595     // Move must happen after the instruction.
    596     DCHECK(!at->IsControlFlow());
    597     move = at->GetNext()->AsParallelMove();
    598     // This is a parallel move for connecting siblings in a same block. We need to
    599     // differentiate it with moves for connecting blocks, and input moves.
    600     if (move == nullptr || move->GetLifetimePosition() > position) {
    601       move = new (allocator_) HParallelMove(allocator_);
    602       move->SetLifetimePosition(position);
    603       at->GetBlock()->InsertInstructionBefore(move, at->GetNext());
    604     }
    605   } else {
    606     // Move must happen before the instruction.
    607     HInstruction* previous = at->GetPrevious();
    608     if (previous == nullptr
    609         || !previous->IsParallelMove()
    610         || previous->GetLifetimePosition() != position) {
    611       // If the previous is a parallel move, then its position must be lower
    612       // than the given `position`: it was added just after the non-parallel
    613       // move instruction that precedes `instruction`.
    614       DCHECK(previous == nullptr
    615              || !previous->IsParallelMove()
    616              || previous->GetLifetimePosition() < position);
    617       move = new (allocator_) HParallelMove(allocator_);
    618       move->SetLifetimePosition(position);
    619       at->GetBlock()->InsertInstructionBefore(move, at);
    620     } else {
    621       move = previous->AsParallelMove();
    622     }
    623   }
    624   DCHECK_EQ(move->GetLifetimePosition(), position);
    625   AddMove(move, source, destination, instruction, instruction->GetType());
    626 }
    627 
    628 void RegisterAllocationResolver::InsertParallelMoveAtExitOf(HBasicBlock* block,
    629                                                             HInstruction* instruction,
    630                                                             Location source,
    631                                                             Location destination) const {
    632   DCHECK(IsValidDestination(destination)) << destination;
    633   if (source.Equals(destination)) return;
    634 
    635   DCHECK_EQ(block->GetNormalSuccessors().size(), 1u);
    636   HInstruction* last = block->GetLastInstruction();
    637   // We insert moves at exit for phi predecessors and connecting blocks.
    638   // A block ending with an if or a packed switch cannot branch to a block
    639   // with phis because we do not allow critical edges. It can also not connect
    640   // a split interval between two blocks: the move has to happen in the successor.
    641   DCHECK(!last->IsIf() && !last->IsPackedSwitch());
    642   HInstruction* previous = last->GetPrevious();
    643   HParallelMove* move;
    644   // This is a parallel move for connecting blocks. We need to differentiate
    645   // it with moves for connecting siblings in a same block, and output moves.
    646   size_t position = last->GetLifetimePosition();
    647   if (previous == nullptr || !previous->IsParallelMove()
    648       || previous->AsParallelMove()->GetLifetimePosition() != position) {
    649     move = new (allocator_) HParallelMove(allocator_);
    650     move->SetLifetimePosition(position);
    651     block->InsertInstructionBefore(move, last);
    652   } else {
    653     move = previous->AsParallelMove();
    654   }
    655   AddMove(move, source, destination, instruction, instruction->GetType());
    656 }
    657 
    658 void RegisterAllocationResolver::InsertParallelMoveAtEntryOf(HBasicBlock* block,
    659                                                              HInstruction* instruction,
    660                                                              Location source,
    661                                                              Location destination) const {
    662   DCHECK(IsValidDestination(destination)) << destination;
    663   if (source.Equals(destination)) return;
    664 
    665   HInstruction* first = block->GetFirstInstruction();
    666   HParallelMove* move = first->AsParallelMove();
    667   size_t position = block->GetLifetimeStart();
    668   // This is a parallel move for connecting blocks. We need to differentiate
    669   // it with moves for connecting siblings in a same block, and input moves.
    670   if (move == nullptr || move->GetLifetimePosition() != position) {
    671     move = new (allocator_) HParallelMove(allocator_);
    672     move->SetLifetimePosition(position);
    673     block->InsertInstructionBefore(move, first);
    674   }
    675   AddMove(move, source, destination, instruction, instruction->GetType());
    676 }
    677 
    678 void RegisterAllocationResolver::InsertMoveAfter(HInstruction* instruction,
    679                                                  Location source,
    680                                                  Location destination) const {
    681   DCHECK(IsValidDestination(destination)) << destination;
    682   if (source.Equals(destination)) return;
    683 
    684   if (instruction->IsPhi()) {
    685     InsertParallelMoveAtEntryOf(instruction->GetBlock(), instruction, source, destination);
    686     return;
    687   }
    688 
    689   size_t position = instruction->GetLifetimePosition() + 1;
    690   HParallelMove* move = instruction->GetNext()->AsParallelMove();
    691   // This is a parallel move for moving the output of an instruction. We need
    692   // to differentiate with input moves, moves for connecting siblings in a
    693   // and moves for connecting blocks.
    694   if (move == nullptr || move->GetLifetimePosition() != position) {
    695     move = new (allocator_) HParallelMove(allocator_);
    696     move->SetLifetimePosition(position);
    697     instruction->GetBlock()->InsertInstructionBefore(move, instruction->GetNext());
    698   }
    699   AddMove(move, source, destination, instruction, instruction->GetType());
    700 }
    701 
    702 }  // namespace art
    703