14e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray/* 24e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray * Copyright (C) 2014 The Android Open Source Project 34e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray * 44e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray * Licensed under the Apache License, Version 2.0 (the "License"); 54e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray * you may not use this file except in compliance with the License. 64e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray * You may obtain a copy of the License at 74e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray * 84e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray * http://www.apache.org/licenses/LICENSE-2.0 94e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray * 104e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray * Unless required by applicable law or agreed to in writing, software 114e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray * distributed under the License is distributed on an "AS IS" BASIS, 124e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 134e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray * See the License for the specific language governing permissions and 144e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray * limitations under the License. 154e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray */ 164e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray 174e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray#include "parallel_move_resolver.h" 18225b6464a58ebe11c156144653f11a1c6607f4ebVladimir Marko 19225b6464a58ebe11c156144653f11a1c6607f4ebVladimir Marko#include "base/stl_util.h" 204e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray#include "nodes.h" 214e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray 224e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffraynamespace art { 234e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray 24ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xuvoid ParallelMoveResolver::BuildInitialMoveList(HParallelMove* parallel_move) { 25ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu // Perform a linear sweep of the moves to add them to the initial list of 26ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu // moves to perform, ignoring any move that is redundant (the source is 27ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu // the same as the destination, the destination is ignored and 28ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu // unallocated, or the move was already eliminated). 29ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu for (size_t i = 0; i < parallel_move->NumMoves(); ++i) { 30ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu MoveOperands* move = parallel_move->MoveOperandsAt(i); 31ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu if (!move->IsRedundant()) { 32225b6464a58ebe11c156144653f11a1c6607f4ebVladimir Marko moves_.push_back(move); 33ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu } 34ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu } 35ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu} 36ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu 37ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xuvoid ParallelMoveResolverWithSwap::EmitNativeCode(HParallelMove* parallel_move) { 38225b6464a58ebe11c156144653f11a1c6607f4ebVladimir Marko DCHECK(moves_.empty()); 394e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray // Build up a worklist of moves. 404e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray BuildInitialMoveList(parallel_move); 414e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray 426e18dcb5d2c35c646f2c95cb776abb79799f52aeMark Mendell // Move stack/stack slot to take advantage of a free register on constrained machines. 43225b6464a58ebe11c156144653f11a1c6607f4ebVladimir Marko for (size_t i = 0; i < moves_.size(); ++i) { 44225b6464a58ebe11c156144653f11a1c6607f4ebVladimir Marko const MoveOperands& move = *moves_[i]; 456e18dcb5d2c35c646f2c95cb776abb79799f52aeMark Mendell // Ignore constants and moves already eliminated. 466e18dcb5d2c35c646f2c95cb776abb79799f52aeMark Mendell if (move.IsEliminated() || move.GetSource().IsConstant()) { 476e18dcb5d2c35c646f2c95cb776abb79799f52aeMark Mendell continue; 486e18dcb5d2c35c646f2c95cb776abb79799f52aeMark Mendell } 496e18dcb5d2c35c646f2c95cb776abb79799f52aeMark Mendell 506e18dcb5d2c35c646f2c95cb776abb79799f52aeMark Mendell if ((move.GetSource().IsStackSlot() || move.GetSource().IsDoubleStackSlot()) && 516e18dcb5d2c35c646f2c95cb776abb79799f52aeMark Mendell (move.GetDestination().IsStackSlot() || move.GetDestination().IsDoubleStackSlot())) { 526e18dcb5d2c35c646f2c95cb776abb79799f52aeMark Mendell PerformMove(i); 536e18dcb5d2c35c646f2c95cb776abb79799f52aeMark Mendell } 546e18dcb5d2c35c646f2c95cb776abb79799f52aeMark Mendell } 556e18dcb5d2c35c646f2c95cb776abb79799f52aeMark Mendell 56225b6464a58ebe11c156144653f11a1c6607f4ebVladimir Marko for (size_t i = 0; i < moves_.size(); ++i) { 57225b6464a58ebe11c156144653f11a1c6607f4ebVladimir Marko const MoveOperands& move = *moves_[i]; 584e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray // Skip constants to perform them last. They don't block other moves 594e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray // and skipping such moves with register destinations keeps those 604e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray // registers free for the whole algorithm. 614e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray if (!move.IsEliminated() && !move.GetSource().IsConstant()) { 624e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray PerformMove(i); 634e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray } 644e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray } 654e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray 664e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray // Perform the moves with constant sources. 67225b6464a58ebe11c156144653f11a1c6607f4ebVladimir Marko for (size_t i = 0; i < moves_.size(); ++i) { 68225b6464a58ebe11c156144653f11a1c6607f4ebVladimir Marko MoveOperands* move = moves_[i]; 6948c310c431b110f6ab54907da20c4fa39a8f76b8Nicolas Geoffray if (!move->IsEliminated()) { 7048c310c431b110f6ab54907da20c4fa39a8f76b8Nicolas Geoffray DCHECK(move->GetSource().IsConstant()); 714e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray EmitMove(i); 7248c310c431b110f6ab54907da20c4fa39a8f76b8Nicolas Geoffray // Eliminate the move, in case following moves need a scratch register. 7348c310c431b110f6ab54907da20c4fa39a8f76b8Nicolas Geoffray move->Eliminate(); 744e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray } 754e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray } 764e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray 77225b6464a58ebe11c156144653f11a1c6607f4ebVladimir Marko moves_.clear(); 784e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray} 794e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray 80a2d15b5e486021bef330b70c21e99557cb116ee5Nicolas GeoffrayLocation LowOf(Location location) { 81a2d15b5e486021bef330b70c21e99557cb116ee5Nicolas Geoffray if (location.IsRegisterPair()) { 82a2d15b5e486021bef330b70c21e99557cb116ee5Nicolas Geoffray return Location::RegisterLocation(location.low()); 83a2d15b5e486021bef330b70c21e99557cb116ee5Nicolas Geoffray } else if (location.IsFpuRegisterPair()) { 84a2d15b5e486021bef330b70c21e99557cb116ee5Nicolas Geoffray return Location::FpuRegisterLocation(location.low()); 85a2d15b5e486021bef330b70c21e99557cb116ee5Nicolas Geoffray } else if (location.IsDoubleStackSlot()) { 86a2d15b5e486021bef330b70c21e99557cb116ee5Nicolas Geoffray return Location::StackSlot(location.GetStackIndex()); 87a2d15b5e486021bef330b70c21e99557cb116ee5Nicolas Geoffray } else { 88a2d15b5e486021bef330b70c21e99557cb116ee5Nicolas Geoffray return Location::NoLocation(); 89a2d15b5e486021bef330b70c21e99557cb116ee5Nicolas Geoffray } 90a2d15b5e486021bef330b70c21e99557cb116ee5Nicolas Geoffray} 91a2d15b5e486021bef330b70c21e99557cb116ee5Nicolas Geoffray 92a2d15b5e486021bef330b70c21e99557cb116ee5Nicolas GeoffrayLocation HighOf(Location location) { 93a2d15b5e486021bef330b70c21e99557cb116ee5Nicolas Geoffray if (location.IsRegisterPair()) { 94a2d15b5e486021bef330b70c21e99557cb116ee5Nicolas Geoffray return Location::RegisterLocation(location.high()); 95a2d15b5e486021bef330b70c21e99557cb116ee5Nicolas Geoffray } else if (location.IsFpuRegisterPair()) { 96a2d15b5e486021bef330b70c21e99557cb116ee5Nicolas Geoffray return Location::FpuRegisterLocation(location.high()); 97a2d15b5e486021bef330b70c21e99557cb116ee5Nicolas Geoffray } else if (location.IsDoubleStackSlot()) { 98a2d15b5e486021bef330b70c21e99557cb116ee5Nicolas Geoffray return Location::StackSlot(location.GetHighStackIndex(4)); 99a2d15b5e486021bef330b70c21e99557cb116ee5Nicolas Geoffray } else { 100a2d15b5e486021bef330b70c21e99557cb116ee5Nicolas Geoffray return Location::NoLocation(); 101a2d15b5e486021bef330b70c21e99557cb116ee5Nicolas Geoffray } 102a2d15b5e486021bef330b70c21e99557cb116ee5Nicolas Geoffray} 103a2d15b5e486021bef330b70c21e99557cb116ee5Nicolas Geoffray 104f7a0c4e421b5edaad5b7a15bfff687da28d0b287Nicolas Geoffray// Update the source of `move`, knowing that `updated_location` has been swapped 105f7a0c4e421b5edaad5b7a15bfff687da28d0b287Nicolas Geoffray// with `new_source`. Note that `updated_location` can be a pair, therefore if 106f7a0c4e421b5edaad5b7a15bfff687da28d0b287Nicolas Geoffray// `move` is non-pair, we need to extract which register to use. 107f7a0c4e421b5edaad5b7a15bfff687da28d0b287Nicolas Geoffraystatic void UpdateSourceOf(MoveOperands* move, Location updated_location, Location new_source) { 108f7a0c4e421b5edaad5b7a15bfff687da28d0b287Nicolas Geoffray Location source = move->GetSource(); 109a2d15b5e486021bef330b70c21e99557cb116ee5Nicolas Geoffray if (LowOf(updated_location).Equals(source)) { 110a2d15b5e486021bef330b70c21e99557cb116ee5Nicolas Geoffray move->SetSource(LowOf(new_source)); 111a2d15b5e486021bef330b70c21e99557cb116ee5Nicolas Geoffray } else if (HighOf(updated_location).Equals(source)) { 112a2d15b5e486021bef330b70c21e99557cb116ee5Nicolas Geoffray move->SetSource(HighOf(new_source)); 113a2d15b5e486021bef330b70c21e99557cb116ee5Nicolas Geoffray } else { 114a2d15b5e486021bef330b70c21e99557cb116ee5Nicolas Geoffray DCHECK(updated_location.Equals(source)) << updated_location << " " << source; 115f7a0c4e421b5edaad5b7a15bfff687da28d0b287Nicolas Geoffray move->SetSource(new_source); 116f7a0c4e421b5edaad5b7a15bfff687da28d0b287Nicolas Geoffray } 117f7a0c4e421b5edaad5b7a15bfff687da28d0b287Nicolas Geoffray} 1184e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray 119ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng XuMoveOperands* ParallelMoveResolverWithSwap::PerformMove(size_t index) { 1204e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray // Each call to this function performs a move and deletes it from the move 1214e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray // graph. We first recursively perform any move blocking this one. We 1224e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray // mark a move as "pending" on entry to PerformMove in order to detect 1234e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray // cycles in the move graph. We use operand swaps to resolve cycles, 1244e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray // which means that a call to PerformMove could change any source operand 1254e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray // in the move graph. 1264e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray 127225b6464a58ebe11c156144653f11a1c6607f4ebVladimir Marko MoveOperands* move = moves_[index]; 128f7a0c4e421b5edaad5b7a15bfff687da28d0b287Nicolas Geoffray DCHECK(!move->IsPending()); 129f7a0c4e421b5edaad5b7a15bfff687da28d0b287Nicolas Geoffray if (move->IsRedundant()) { 130f7a0c4e421b5edaad5b7a15bfff687da28d0b287Nicolas Geoffray // Because we swap register pairs first, following, un-pending 131f7a0c4e421b5edaad5b7a15bfff687da28d0b287Nicolas Geoffray // moves may become redundant. 132f7a0c4e421b5edaad5b7a15bfff687da28d0b287Nicolas Geoffray move->Eliminate(); 133f7a0c4e421b5edaad5b7a15bfff687da28d0b287Nicolas Geoffray return nullptr; 134f7a0c4e421b5edaad5b7a15bfff687da28d0b287Nicolas Geoffray } 1354e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray 1364e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray // Clear this move's destination to indicate a pending move. The actual 1374e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray // destination is saved in a stack-allocated local. Recursion may allow 1384e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray // multiple moves to be pending. 139f7a0c4e421b5edaad5b7a15bfff687da28d0b287Nicolas Geoffray DCHECK(!move->GetSource().IsInvalid()); 140f7a0c4e421b5edaad5b7a15bfff687da28d0b287Nicolas Geoffray Location destination = move->MarkPending(); 1414e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray 1424e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray // Perform a depth-first traversal of the move graph to resolve 1434e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray // dependencies. Any unperformed, unpending move with a source the same 1444e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray // as this one's destination blocks this one so recursively perform all 1454e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray // such moves. 146f7a0c4e421b5edaad5b7a15bfff687da28d0b287Nicolas Geoffray MoveOperands* required_swap = nullptr; 147225b6464a58ebe11c156144653f11a1c6607f4ebVladimir Marko for (size_t i = 0; i < moves_.size(); ++i) { 148225b6464a58ebe11c156144653f11a1c6607f4ebVladimir Marko const MoveOperands& other_move = *moves_[i]; 1494e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray if (other_move.Blocks(destination) && !other_move.IsPending()) { 1504e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray // Though PerformMove can change any source operand in the move graph, 151f7a0c4e421b5edaad5b7a15bfff687da28d0b287Nicolas Geoffray // calling `PerformMove` cannot create a blocking move via a swap 152f7a0c4e421b5edaad5b7a15bfff687da28d0b287Nicolas Geoffray // (this loop does not miss any). 153f7a0c4e421b5edaad5b7a15bfff687da28d0b287Nicolas Geoffray // For example, assume there is a non-blocking move with source A 1544e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray // and this move is blocked on source B and there is a swap of A and 1554e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray // B. Then A and B must be involved in the same cycle (or they would 1564e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray // not be swapped). Since this move's destination is B and there is 1574e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray // only a single incoming edge to an operand, this move must also be 1584e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray // involved in the same cycle. In that case, the blocking move will 1594e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray // be created but will be "pending" when we return from PerformMove. 160f7a0c4e421b5edaad5b7a15bfff687da28d0b287Nicolas Geoffray required_swap = PerformMove(i); 161f7a0c4e421b5edaad5b7a15bfff687da28d0b287Nicolas Geoffray 162f7a0c4e421b5edaad5b7a15bfff687da28d0b287Nicolas Geoffray if (required_swap == move) { 163f7a0c4e421b5edaad5b7a15bfff687da28d0b287Nicolas Geoffray // If this move is required to swap, we do so without looking 164f7a0c4e421b5edaad5b7a15bfff687da28d0b287Nicolas Geoffray // at the next moves. Swapping is not blocked by anything, it just 165f7a0c4e421b5edaad5b7a15bfff687da28d0b287Nicolas Geoffray // updates other moves's source. 166f7a0c4e421b5edaad5b7a15bfff687da28d0b287Nicolas Geoffray break; 167225b6464a58ebe11c156144653f11a1c6607f4ebVladimir Marko } else if (required_swap == moves_[i]) { 168f7a0c4e421b5edaad5b7a15bfff687da28d0b287Nicolas Geoffray // If `other_move` was swapped, we iterate again to find a new 169f7a0c4e421b5edaad5b7a15bfff687da28d0b287Nicolas Geoffray // potential cycle. 170f7a0c4e421b5edaad5b7a15bfff687da28d0b287Nicolas Geoffray required_swap = nullptr; 1713e3e4a762c23c3de66436b30e9fc65f35dad344cNicolas Geoffray i = -1; 172f7a0c4e421b5edaad5b7a15bfff687da28d0b287Nicolas Geoffray } else if (required_swap != nullptr) { 173f7a0c4e421b5edaad5b7a15bfff687da28d0b287Nicolas Geoffray // A move is required to swap. We walk back the cycle to find the 174c928591f5b2c544751bb3fb26dc614d3c2e67befRoland Levillain // move by just returning from this `PerformMove`. 175225b6464a58ebe11c156144653f11a1c6607f4ebVladimir Marko moves_[index]->ClearPending(destination); 176f7a0c4e421b5edaad5b7a15bfff687da28d0b287Nicolas Geoffray return required_swap; 177f7a0c4e421b5edaad5b7a15bfff687da28d0b287Nicolas Geoffray } 1784e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray } 1794e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray } 1804e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray 1814e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray // We are about to resolve this move and don't need it marked as 1824e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray // pending, so restore its destination. 1834e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray move->ClearPending(destination); 1844e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray 1854e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray // This move's source may have changed due to swaps to resolve cycles and 1864e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray // so it may now be the last move in the cycle. If so remove it. 1874e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray if (move->GetSource().Equals(destination)) { 1884e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray move->Eliminate(); 189f7a0c4e421b5edaad5b7a15bfff687da28d0b287Nicolas Geoffray DCHECK(required_swap == nullptr); 190f7a0c4e421b5edaad5b7a15bfff687da28d0b287Nicolas Geoffray return nullptr; 1914e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray } 1924e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray 1934e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray // The move may be blocked on a (at most one) pending move, in which case 1944e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray // we have a cycle. Search for such a blocking move and perform a swap to 1954e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray // resolve it. 1964e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray bool do_swap = false; 197f7a0c4e421b5edaad5b7a15bfff687da28d0b287Nicolas Geoffray if (required_swap != nullptr) { 198f7a0c4e421b5edaad5b7a15bfff687da28d0b287Nicolas Geoffray DCHECK_EQ(required_swap, move); 199f7a0c4e421b5edaad5b7a15bfff687da28d0b287Nicolas Geoffray do_swap = true; 200f7a0c4e421b5edaad5b7a15bfff687da28d0b287Nicolas Geoffray } else { 201225b6464a58ebe11c156144653f11a1c6607f4ebVladimir Marko for (MoveOperands* other_move : moves_) { 202225b6464a58ebe11c156144653f11a1c6607f4ebVladimir Marko if (other_move->Blocks(destination)) { 203c928591f5b2c544751bb3fb26dc614d3c2e67befRoland Levillain DCHECK(other_move->IsPending()) << "move=" << *move << " other_move=" << *other_move; 204225b6464a58ebe11c156144653f11a1c6607f4ebVladimir Marko if (!move->Is64BitMove() && other_move->Is64BitMove()) { 2059021825d1e73998b99c81e89c73796f6f2845471Nicolas Geoffray // We swap 64bits moves before swapping 32bits moves. Go back from the 2069021825d1e73998b99c81e89c73796f6f2845471Nicolas Geoffray // cycle by returning the move that must be swapped. 207225b6464a58ebe11c156144653f11a1c6607f4ebVladimir Marko return other_move; 208f7a0c4e421b5edaad5b7a15bfff687da28d0b287Nicolas Geoffray } 209f7a0c4e421b5edaad5b7a15bfff687da28d0b287Nicolas Geoffray do_swap = true; 210f7a0c4e421b5edaad5b7a15bfff687da28d0b287Nicolas Geoffray break; 211f7a0c4e421b5edaad5b7a15bfff687da28d0b287Nicolas Geoffray } 2124e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray } 2134e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray } 2144e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray 2154e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray if (do_swap) { 2164e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray EmitSwap(index); 2174e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray // Any unperformed (including pending) move with a source of either 2184e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray // this move's source or destination needs to have their source 2194e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray // changed to reflect the state of affairs after the swap. 2204e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray Location source = move->GetSource(); 221277ccbd200ea43590dfc06a93ae184a765327ad0Andreas Gampe Location swap_destination = move->GetDestination(); 2224e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray move->Eliminate(); 223225b6464a58ebe11c156144653f11a1c6607f4ebVladimir Marko for (MoveOperands* other_move : moves_) { 224225b6464a58ebe11c156144653f11a1c6607f4ebVladimir Marko if (other_move->Blocks(source)) { 225225b6464a58ebe11c156144653f11a1c6607f4ebVladimir Marko UpdateSourceOf(other_move, source, swap_destination); 226225b6464a58ebe11c156144653f11a1c6607f4ebVladimir Marko } else if (other_move->Blocks(swap_destination)) { 227225b6464a58ebe11c156144653f11a1c6607f4ebVladimir Marko UpdateSourceOf(other_move, swap_destination, source); 2284e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray } 2294e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray } 2309021825d1e73998b99c81e89c73796f6f2845471Nicolas Geoffray // If the swap was required because of a 64bits move in the middle of a cycle, 231f7a0c4e421b5edaad5b7a15bfff687da28d0b287Nicolas Geoffray // we return the swapped move, so that the caller knows it needs to re-iterate 232f7a0c4e421b5edaad5b7a15bfff687da28d0b287Nicolas Geoffray // its dependency loop. 233f7a0c4e421b5edaad5b7a15bfff687da28d0b287Nicolas Geoffray return required_swap; 2344e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray } else { 2354e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray // This move is not blocked. 2364e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray EmitMove(index); 2374e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray move->Eliminate(); 238f7a0c4e421b5edaad5b7a15bfff687da28d0b287Nicolas Geoffray DCHECK(required_swap == nullptr); 239f7a0c4e421b5edaad5b7a15bfff687da28d0b287Nicolas Geoffray return nullptr; 2404e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray } 2414e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray} 2424e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray 243ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xubool ParallelMoveResolverWithSwap::IsScratchLocation(Location loc) { 244225b6464a58ebe11c156144653f11a1c6607f4ebVladimir Marko for (MoveOperands* move : moves_) { 245225b6464a58ebe11c156144653f11a1c6607f4ebVladimir Marko if (move->Blocks(loc)) { 24686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray return false; 24786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 24886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 24986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 250225b6464a58ebe11c156144653f11a1c6607f4ebVladimir Marko for (MoveOperands* move : moves_) { 251225b6464a58ebe11c156144653f11a1c6607f4ebVladimir Marko if (move->GetDestination().Equals(loc)) { 25286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray return true; 25386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 25486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 25586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 25686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray return false; 25786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 25886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 259ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xuint ParallelMoveResolverWithSwap::AllocateScratchRegister(int blocked, 260ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu int register_count, 261ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu int if_scratch, 262ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu bool* spilled) { 263e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray DCHECK_NE(blocked, if_scratch); 26486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray int scratch = -1; 26586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray for (int reg = 0; reg < register_count; ++reg) { 26656b9ee6fe1d6880c5fca0e7feb28b25a1ded2e2fNicolas Geoffray if ((blocked != reg) && IsScratchLocation(Location::RegisterLocation(reg))) { 26786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray scratch = reg; 26886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray break; 26986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 27086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 27186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 27286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (scratch == -1) { 27386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray *spilled = true; 274e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray scratch = if_scratch; 27586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else { 27686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray *spilled = false; 27786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 27886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 27986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray return scratch; 28086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 28186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 28286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 283ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng XuParallelMoveResolverWithSwap::ScratchRegisterScope::ScratchRegisterScope( 284ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu ParallelMoveResolverWithSwap* resolver, int blocked, int if_scratch, int number_of_registers) 28586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray : resolver_(resolver), 28686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray reg_(kNoRegister), 28786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray spilled_(false) { 288e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray reg_ = resolver_->AllocateScratchRegister(blocked, number_of_registers, if_scratch, &spilled_); 28986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 29086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (spilled_) { 29186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray resolver->SpillScratch(reg_); 29286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 29386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 29486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 29586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 296ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng XuParallelMoveResolverWithSwap::ScratchRegisterScope::~ScratchRegisterScope() { 29786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (spilled_) { 29886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray resolver_->RestoreScratch(reg_); 29986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 30086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 30186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 302ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xuvoid ParallelMoveResolverNoSwap::EmitNativeCode(HParallelMove* parallel_move) { 303ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu DCHECK_EQ(GetNumberOfPendingMoves(), 0u); 304225b6464a58ebe11c156144653f11a1c6607f4ebVladimir Marko DCHECK(moves_.empty()); 305225b6464a58ebe11c156144653f11a1c6607f4ebVladimir Marko DCHECK(scratches_.empty()); 306ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu 307ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu // Backend dependent initialization. 308ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu PrepareForEmitNativeCode(); 309ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu 310ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu // Build up a worklist of moves. 311ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu BuildInitialMoveList(parallel_move); 312ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu 313225b6464a58ebe11c156144653f11a1c6607f4ebVladimir Marko for (size_t i = 0; i < moves_.size(); ++i) { 314225b6464a58ebe11c156144653f11a1c6607f4ebVladimir Marko const MoveOperands& move = *moves_[i]; 315ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu // Skip constants to perform them last. They don't block other moves and 316ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu // skipping such moves with register destinations keeps those registers 317ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu // free for the whole algorithm. 318ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu if (!move.IsEliminated() && !move.GetSource().IsConstant()) { 319ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu PerformMove(i); 320ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu } 321ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu } 322ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu 323ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu // Perform the moves with constant sources and register destinations with UpdateMoveSource() 324ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu // to reduce the number of literal loads. Stack destinations are skipped since we won't be benefit 325ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu // from changing the constant sources to stack locations. 326225b6464a58ebe11c156144653f11a1c6607f4ebVladimir Marko for (size_t i = 0; i < moves_.size(); ++i) { 327225b6464a58ebe11c156144653f11a1c6607f4ebVladimir Marko MoveOperands* move = moves_[i]; 328ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu Location destination = move->GetDestination(); 329ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu if (!move->IsEliminated() && !destination.IsStackSlot() && !destination.IsDoubleStackSlot()) { 330ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu Location source = move->GetSource(); 331ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu EmitMove(i); 332ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu move->Eliminate(); 333ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu // This may introduce additional instruction dependency, but reduce number 334ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu // of moves and possible literal loads. For example, 335ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu // Original moves: 336ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu // 1234.5678 -> D0 337ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu // 1234.5678 -> D1 338ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu // Updated moves: 339ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu // 1234.5678 -> D0 340ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu // D0 -> D1 341ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu UpdateMoveSource(source, destination); 342ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu } 343ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu } 344ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu 345ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu // Perform the rest of the moves. 346225b6464a58ebe11c156144653f11a1c6607f4ebVladimir Marko for (size_t i = 0; i < moves_.size(); ++i) { 347225b6464a58ebe11c156144653f11a1c6607f4ebVladimir Marko MoveOperands* move = moves_[i]; 348ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu if (!move->IsEliminated()) { 349ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu EmitMove(i); 350ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu move->Eliminate(); 351ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu } 352ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu } 353ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu 354ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu // All pending moves that we have added for resolve cycles should be performed. 355ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu DCHECK_EQ(GetNumberOfPendingMoves(), 0u); 356ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu 357ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu // Backend dependent cleanup. 358ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu FinishEmitNativeCode(); 359ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu 360225b6464a58ebe11c156144653f11a1c6607f4ebVladimir Marko moves_.clear(); 361225b6464a58ebe11c156144653f11a1c6607f4ebVladimir Marko scratches_.clear(); 362ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu} 363ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu 364ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng XuLocation ParallelMoveResolverNoSwap::GetScratchLocation(Location::Kind kind) { 365225b6464a58ebe11c156144653f11a1c6607f4ebVladimir Marko for (Location loc : scratches_) { 366ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu if (loc.GetKind() == kind && !IsBlockedByMoves(loc)) { 367ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu return loc; 368ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu } 369ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu } 370225b6464a58ebe11c156144653f11a1c6607f4ebVladimir Marko for (MoveOperands* move : moves_) { 371225b6464a58ebe11c156144653f11a1c6607f4ebVladimir Marko Location loc = move->GetDestination(); 372ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu if (loc.GetKind() == kind && !IsBlockedByMoves(loc)) { 373ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu return loc; 374ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu } 375ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu } 376ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu return Location::NoLocation(); 377ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu} 378ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu 379ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xuvoid ParallelMoveResolverNoSwap::AddScratchLocation(Location loc) { 380ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu if (kIsDebugBuild) { 381225b6464a58ebe11c156144653f11a1c6607f4ebVladimir Marko for (Location scratch : scratches_) { 382225b6464a58ebe11c156144653f11a1c6607f4ebVladimir Marko CHECK(!loc.Equals(scratch)); 383ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu } 384ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu } 385225b6464a58ebe11c156144653f11a1c6607f4ebVladimir Marko scratches_.push_back(loc); 386ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu} 387ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu 388ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xuvoid ParallelMoveResolverNoSwap::RemoveScratchLocation(Location loc) { 389ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu DCHECK(!IsBlockedByMoves(loc)); 390225b6464a58ebe11c156144653f11a1c6607f4ebVladimir Marko for (auto it = scratches_.begin(), end = scratches_.end(); it != end; ++it) { 391225b6464a58ebe11c156144653f11a1c6607f4ebVladimir Marko if (loc.Equals(*it)) { 392225b6464a58ebe11c156144653f11a1c6607f4ebVladimir Marko scratches_.erase(it); 393ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu break; 394ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu } 395ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu } 396ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu} 397ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu 398ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xuvoid ParallelMoveResolverNoSwap::PerformMove(size_t index) { 399ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu // Each call to this function performs a move and deletes it from the move 400ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu // graph. We first recursively perform any move blocking this one. We mark 401ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu // a move as "pending" on entry to PerformMove in order to detect cycles 402ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu // in the move graph. We use scratch location to resolve cycles, also 403ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu // additional pending moves might be added. After move has been performed, 404ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu // we will update source operand in the move graph to reduce dependencies in 405ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu // the graph. 406ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu 407225b6464a58ebe11c156144653f11a1c6607f4ebVladimir Marko MoveOperands* move = moves_[index]; 408ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu DCHECK(!move->IsPending()); 409ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu DCHECK(!move->IsEliminated()); 410ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu if (move->IsRedundant()) { 411ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu // Previous operations on the list of moves have caused this particular move 412ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu // to become a no-op, so we can safely eliminate it. Consider for example 413ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu // (0 -> 1) (1 -> 0) (1 -> 2). There is a cycle (0 -> 1) (1 -> 0), that we will 414ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu // resolve as (1 -> scratch) (0 -> 1) (scratch -> 0). If, by chance, '2' is 415ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu // used as the scratch location, the move (1 -> 2) will occur while resolving 416ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu // the cycle. When that move is emitted, the code will update moves with a '1' 417ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu // as their source to use '2' instead (see `UpdateMoveSource()`. In our example 418ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu // the initial move (1 -> 2) would then become the no-op (2 -> 2) that can be 419ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu // eliminated here. 420ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu move->Eliminate(); 421ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu return; 422ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu } 423ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu 424ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu // Clear this move's destination to indicate a pending move. The actual 425ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu // destination is saved in a stack-allocated local. Recursion may allow 426ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu // multiple moves to be pending. 427ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu DCHECK(!move->GetSource().IsInvalid()); 428ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu Location destination = move->MarkPending(); 429ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu 430ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu // Perform a depth-first traversal of the move graph to resolve 431ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu // dependencies. Any unperformed, unpending move with a source the same 432ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu // as this one's destination blocks this one so recursively perform all 433ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu // such moves. 434225b6464a58ebe11c156144653f11a1c6607f4ebVladimir Marko for (size_t i = 0; i < moves_.size(); ++i) { 435225b6464a58ebe11c156144653f11a1c6607f4ebVladimir Marko const MoveOperands& other_move = *moves_[i]; 436ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu if (other_move.Blocks(destination) && !other_move.IsPending()) { 437ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu PerformMove(i); 438ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu } 439ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu } 440ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu 441ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu // We are about to resolve this move and don't need it marked as 442ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu // pending, so restore its destination. 443ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu move->ClearPending(destination); 444ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu 445ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu // No one else should write to the move destination when the it is pending. 446ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu DCHECK(!move->IsRedundant()); 447ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu 448ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu Location source = move->GetSource(); 449ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu // The move may be blocked on several pending moves, in case we have a cycle. 450ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu if (IsBlockedByMoves(destination)) { 451ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu // For a cycle like: (A -> B) (B -> C) (C -> A), we change it to following 452ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu // sequence: 453ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu // (C -> scratch) # Emit right now. 454ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu // (A -> B) (B -> C) # Unblocked. 455ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu // (scratch -> A) # Add to pending_moves_, blocked by (A -> B). 456ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu Location::Kind kind = source.GetKind(); 457ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu DCHECK_NE(kind, Location::kConstant); 458ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu Location scratch = AllocateScratchLocationFor(kind); 459ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu // We only care about the move size. 460ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu Primitive::Type type = move->Is64BitMove() ? Primitive::kPrimLong : Primitive::kPrimInt; 461ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu // Perform (C -> scratch) 462ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu move->SetDestination(scratch); 463ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu EmitMove(index); 464ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu move->Eliminate(); 465ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu UpdateMoveSource(source, scratch); 466ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu // Add (scratch -> A). 467ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu AddPendingMove(scratch, destination, type); 468ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu } else { 469ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu // This move is not blocked. 470ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu EmitMove(index); 471ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu move->Eliminate(); 472ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu UpdateMoveSource(source, destination); 473ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu } 474ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu 475ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu // Moves in the pending list should not block any other moves. But performing 476ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu // unblocked moves in the pending list can free scratch registers, so we do this 477ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu // as early as possible. 478ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu MoveOperands* pending_move; 479ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu while ((pending_move = GetUnblockedPendingMove(source)) != nullptr) { 480ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu Location pending_source = pending_move->GetSource(); 481ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu Location pending_destination = pending_move->GetDestination(); 482ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu // We do not depend on the pending move index. So just delete the move instead 483ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu // of eliminating it to make the pending list cleaner. 484ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu DeletePendingMove(pending_move); 485ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu move->SetSource(pending_source); 486ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu move->SetDestination(pending_destination); 487ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu EmitMove(index); 488ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu move->Eliminate(); 489ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu UpdateMoveSource(pending_source, pending_destination); 490ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu // Free any unblocked locations in the scratch location list. 491225b6464a58ebe11c156144653f11a1c6607f4ebVladimir Marko // Note: Fetch size() on each iteration because scratches_ can be modified inside the loop. 492225b6464a58ebe11c156144653f11a1c6607f4ebVladimir Marko // FIXME: If FreeScratchLocation() removes the location from scratches_, 493225b6464a58ebe11c156144653f11a1c6607f4ebVladimir Marko // we skip the next location. This happens for arm64. 494225b6464a58ebe11c156144653f11a1c6607f4ebVladimir Marko for (size_t i = 0; i < scratches_.size(); ++i) { 495225b6464a58ebe11c156144653f11a1c6607f4ebVladimir Marko Location scratch = scratches_[i]; 496ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu // Only scratch overlapping with performed move source can be unblocked. 497ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu if (scratch.OverlapsWith(pending_source) && !IsBlockedByMoves(scratch)) { 498ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu FreeScratchLocation(pending_source); 499ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu } 500ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu } 501ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu } 502ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu} 503ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu 504ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xuvoid ParallelMoveResolverNoSwap::UpdateMoveSource(Location from, Location to) { 505ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu // This function is used to reduce the dependencies in the graph after 506ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu // (from -> to) has been performed. Since we ensure there is no move with the same 50791d65e024846717fce3572106cffe9b957b8902cRoland Levillain // destination, (to -> X) cannot be blocked while (from -> X) might still be 508ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu // blocked. Consider for example the moves (0 -> 1) (1 -> 2) (1 -> 3). After 509ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu // (1 -> 2) has been performed, the moves left are (0 -> 1) and (1 -> 3). There is 510ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu // a dependency between the two. If we update the source location from 1 to 2, we 511ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu // will get (0 -> 1) and (2 -> 3). There is no dependency between the two. 512ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu // 513ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu // This is not something we must do, but we can use fewer scratch locations with 514ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu // this trick. For example, we can avoid using additional scratch locations for 515ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu // moves (0 -> 1), (1 -> 2), (1 -> 0). 516225b6464a58ebe11c156144653f11a1c6607f4ebVladimir Marko for (MoveOperands* move : moves_) { 517ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu if (move->GetSource().Equals(from)) { 518ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu move->SetSource(to); 519ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu } 520ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu } 521ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu} 522ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu 523ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xuvoid ParallelMoveResolverNoSwap::AddPendingMove(Location source, 524ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu Location destination, Primitive::Type type) { 525225b6464a58ebe11c156144653f11a1c6607f4ebVladimir Marko pending_moves_.push_back(new (allocator_) MoveOperands(source, destination, type, nullptr)); 526ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu} 527ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu 528ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xuvoid ParallelMoveResolverNoSwap::DeletePendingMove(MoveOperands* move) { 529225b6464a58ebe11c156144653f11a1c6607f4ebVladimir Marko RemoveElement(pending_moves_, move); 530ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu} 531ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu 532ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng XuMoveOperands* ParallelMoveResolverNoSwap::GetUnblockedPendingMove(Location loc) { 533225b6464a58ebe11c156144653f11a1c6607f4ebVladimir Marko for (MoveOperands* move : pending_moves_) { 534ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu Location destination = move->GetDestination(); 535ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu // Only moves with destination overlapping with input loc can be unblocked. 536ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu if (destination.OverlapsWith(loc) && !IsBlockedByMoves(destination)) { 537ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu return move; 538ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu } 539ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu } 540ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu return nullptr; 541ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu} 542ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu 543ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xubool ParallelMoveResolverNoSwap::IsBlockedByMoves(Location loc) { 544225b6464a58ebe11c156144653f11a1c6607f4ebVladimir Marko for (MoveOperands* move : pending_moves_) { 545225b6464a58ebe11c156144653f11a1c6607f4ebVladimir Marko if (move->Blocks(loc)) { 546ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu return true; 547ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu } 548ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu } 549225b6464a58ebe11c156144653f11a1c6607f4ebVladimir Marko for (MoveOperands* move : moves_) { 550225b6464a58ebe11c156144653f11a1c6607f4ebVladimir Marko if (move->Blocks(loc)) { 551ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu return true; 552ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu } 553ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu } 554ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu return false; 555ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu} 556ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu 557ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu// So far it is only used for debugging purposes to make sure all pending moves 558ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu// have been performed. 559ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xusize_t ParallelMoveResolverNoSwap::GetNumberOfPendingMoves() { 560225b6464a58ebe11c156144653f11a1c6607f4ebVladimir Marko return pending_moves_.size(); 561ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu} 562ad4450e5c3ffaa9566216cc6fafbf5c11186c467Zheng Xu 5634e3d23aa1523718ea1fdf3a32516d2f9d81e84feNicolas Geoffray} // namespace art 564