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