1// Copyright 2014 the V8 project authors. All rights reserved. 2// Use of this source code is governed by a BSD-style license that can be 3// found in the LICENSE file. 4 5#include "src/compiler/gap-resolver.h" 6 7#include <algorithm> 8#include <functional> 9#include <set> 10 11namespace v8 { 12namespace internal { 13namespace compiler { 14 15namespace { 16 17#define REP_BIT(rep) (1 << static_cast<int>(rep)) 18 19const int kFloat32Bit = REP_BIT(MachineRepresentation::kFloat32); 20const int kFloat64Bit = REP_BIT(MachineRepresentation::kFloat64); 21 22inline bool Blocks(MoveOperands* move, InstructionOperand destination) { 23 return !move->IsEliminated() && move->source().InterferesWith(destination); 24} 25 26// Splits a FP move between two location operands into the equivalent series of 27// moves between smaller sub-operands, e.g. a double move to two single moves. 28// This helps reduce the number of cycles that would normally occur under FP 29// aliasing, and makes swaps much easier to implement. 30MoveOperands* Split(MoveOperands* move, MachineRepresentation smaller_rep, 31 ParallelMove* moves) { 32 DCHECK(!kSimpleFPAliasing); 33 // Splitting is only possible when the slot size is the same as float size. 34 DCHECK_EQ(kPointerSize, kFloatSize); 35 const LocationOperand& src_loc = LocationOperand::cast(move->source()); 36 const LocationOperand& dst_loc = LocationOperand::cast(move->destination()); 37 MachineRepresentation dst_rep = dst_loc.representation(); 38 DCHECK_NE(smaller_rep, dst_rep); 39 auto src_kind = src_loc.location_kind(); 40 auto dst_kind = dst_loc.location_kind(); 41 42 int aliases = 43 1 << (ElementSizeLog2Of(dst_rep) - ElementSizeLog2Of(smaller_rep)); 44 int base = -1; 45 USE(base); 46 DCHECK_EQ(aliases, RegisterConfiguration::Turbofan()->GetAliases( 47 dst_rep, 0, smaller_rep, &base)); 48 49 int src_index = -1; 50 int slot_size = (1 << ElementSizeLog2Of(smaller_rep)) / kPointerSize; 51 int src_step = 1; 52 if (src_kind == LocationOperand::REGISTER) { 53 src_index = src_loc.register_code() * aliases; 54 } else { 55 src_index = src_loc.index(); 56 // For operands that occuply multiple slots, the index refers to the last 57 // slot. On little-endian architectures, we start at the high slot and use a 58 // negative step so that register-to-slot moves are in the correct order. 59 src_step = -slot_size; 60 } 61 int dst_index = -1; 62 int dst_step = 1; 63 if (dst_kind == LocationOperand::REGISTER) { 64 dst_index = dst_loc.register_code() * aliases; 65 } else { 66 dst_index = dst_loc.index(); 67 dst_step = -slot_size; 68 } 69 70 // Reuse 'move' for the first fragment. It is not pending. 71 move->set_source(AllocatedOperand(src_kind, smaller_rep, src_index)); 72 move->set_destination(AllocatedOperand(dst_kind, smaller_rep, dst_index)); 73 // Add the remaining fragment moves. 74 for (int i = 1; i < aliases; ++i) { 75 src_index += src_step; 76 dst_index += dst_step; 77 moves->AddMove(AllocatedOperand(src_kind, smaller_rep, src_index), 78 AllocatedOperand(dst_kind, smaller_rep, dst_index)); 79 } 80 // Return the first fragment. 81 return move; 82} 83 84} // namespace 85 86void GapResolver::Resolve(ParallelMove* moves) { 87 // Clear redundant moves, and collect FP move representations if aliasing 88 // is non-simple. 89 int reps = 0; 90 for (size_t i = 0; i < moves->size();) { 91 MoveOperands* move = (*moves)[i]; 92 if (move->IsRedundant()) { 93 (*moves)[i] = moves->back(); 94 moves->pop_back(); 95 continue; 96 } 97 i++; 98 if (!kSimpleFPAliasing && move->destination().IsFPRegister()) { 99 reps |= 100 REP_BIT(LocationOperand::cast(move->destination()).representation()); 101 } 102 } 103 104 if (!kSimpleFPAliasing) { 105 if (reps && !base::bits::IsPowerOfTwo32(reps)) { 106 // Start with the smallest FP moves, so we never encounter smaller moves 107 // in the middle of a cycle of larger moves. 108 if ((reps & kFloat32Bit) != 0) { 109 split_rep_ = MachineRepresentation::kFloat32; 110 for (size_t i = 0; i < moves->size(); ++i) { 111 auto move = (*moves)[i]; 112 if (!move->IsEliminated() && move->destination().IsFloatRegister()) 113 PerformMove(moves, move); 114 } 115 } 116 if ((reps & kFloat64Bit) != 0) { 117 split_rep_ = MachineRepresentation::kFloat64; 118 for (size_t i = 0; i < moves->size(); ++i) { 119 auto move = (*moves)[i]; 120 if (!move->IsEliminated() && move->destination().IsDoubleRegister()) 121 PerformMove(moves, move); 122 } 123 } 124 } 125 split_rep_ = MachineRepresentation::kSimd128; 126 } 127 128 for (size_t i = 0; i < moves->size(); ++i) { 129 auto move = (*moves)[i]; 130 if (!move->IsEliminated()) PerformMove(moves, move); 131 } 132} 133 134void GapResolver::PerformMove(ParallelMove* moves, MoveOperands* move) { 135 // Each call to this function performs a move and deletes it from the move 136 // graph. We first recursively perform any move blocking this one. We mark a 137 // move as "pending" on entry to PerformMove in order to detect cycles in the 138 // move graph. We use operand swaps to resolve cycles, which means that a 139 // call to PerformMove could change any source operand in the move graph. 140 DCHECK(!move->IsPending()); 141 DCHECK(!move->IsRedundant()); 142 143 // Clear this move's destination to indicate a pending move. The actual 144 // destination is saved on the side. 145 InstructionOperand source = move->source(); 146 DCHECK(!source.IsInvalid()); // Or else it will look eliminated. 147 InstructionOperand destination = move->destination(); 148 move->SetPending(); 149 150 // We may need to split moves between FP locations differently. 151 bool is_fp_loc_move = !kSimpleFPAliasing && destination.IsFPLocationOperand(); 152 153 // Perform a depth-first traversal of the move graph to resolve dependencies. 154 // Any unperformed, unpending move with a source the same as this one's 155 // destination blocks this one so recursively perform all such moves. 156 for (size_t i = 0; i < moves->size(); ++i) { 157 auto other = (*moves)[i]; 158 if (other->IsEliminated()) continue; 159 if (other->IsPending()) continue; 160 if (other->source().InterferesWith(destination)) { 161 if (!kSimpleFPAliasing && is_fp_loc_move && 162 LocationOperand::cast(other->source()).representation() > 163 split_rep_) { 164 // 'other' must also be an FP location move. Break it into fragments 165 // of the same size as 'move'. 'other' is set to one of the fragments, 166 // and the rest are appended to 'moves'. 167 other = Split(other, split_rep_, moves); 168 // 'other' may not block destination now. 169 if (!other->source().InterferesWith(destination)) continue; 170 } 171 // Though PerformMove can change any source operand in the move graph, 172 // this call cannot create a blocking move via a swap (this loop does not 173 // miss any). Assume there is a non-blocking move with source A and this 174 // move is blocked on source B and there is a swap of A and B. Then A and 175 // B must be involved in the same cycle (or they would not be swapped). 176 // Since this move's destination is B and there is only a single incoming 177 // edge to an operand, this move must also be involved in the same cycle. 178 // In that case, the blocking move will be created but will be "pending" 179 // when we return from PerformMove. 180 PerformMove(moves, other); 181 } 182 } 183 184 // This move's source may have changed due to swaps to resolve cycles and so 185 // it may now be the last move in the cycle. If so remove it. 186 source = move->source(); 187 if (source.EqualsCanonicalized(destination)) { 188 move->Eliminate(); 189 return; 190 } 191 192 // We are about to resolve this move and don't need it marked as pending, so 193 // restore its destination. 194 move->set_destination(destination); 195 196 // The move may be blocked on a (at most one) pending move, in which case we 197 // have a cycle. Search for such a blocking move and perform a swap to 198 // resolve it. 199 auto blocker = std::find_if(moves->begin(), moves->end(), 200 std::bind2nd(std::ptr_fun(&Blocks), destination)); 201 if (blocker == moves->end()) { 202 // The easy case: This move is not blocked. 203 assembler_->AssembleMove(&source, &destination); 204 move->Eliminate(); 205 return; 206 } 207 208 // Ensure source is a register or both are stack slots, to limit swap cases. 209 if (source.IsStackSlot() || source.IsFPStackSlot()) { 210 std::swap(source, destination); 211 } 212 assembler_->AssembleSwap(&source, &destination); 213 move->Eliminate(); 214 215 // Update outstanding moves whose source may now have been moved. 216 if (!kSimpleFPAliasing && is_fp_loc_move) { 217 // We may have to split larger moves. 218 for (size_t i = 0; i < moves->size(); ++i) { 219 auto other = (*moves)[i]; 220 if (other->IsEliminated()) continue; 221 if (source.InterferesWith(other->source())) { 222 if (LocationOperand::cast(other->source()).representation() > 223 split_rep_) { 224 other = Split(other, split_rep_, moves); 225 if (!source.InterferesWith(other->source())) continue; 226 } 227 other->set_source(destination); 228 } else if (destination.InterferesWith(other->source())) { 229 if (LocationOperand::cast(other->source()).representation() > 230 split_rep_) { 231 other = Split(other, split_rep_, moves); 232 if (!destination.InterferesWith(other->source())) continue; 233 } 234 other->set_source(source); 235 } 236 } 237 } else { 238 for (auto other : *moves) { 239 if (other->IsEliminated()) continue; 240 if (source.EqualsCanonicalized(other->source())) { 241 other->set_source(destination); 242 } else if (destination.EqualsCanonicalized(other->source())) { 243 other->set_source(source); 244 } 245 } 246 } 247} 248} // namespace compiler 249} // namespace internal 250} // namespace v8 251