1 // Copyright 2013 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/v8.h"
6
7 #include "src/arm64/delayed-masm-arm64-inl.h"
8 #include "src/arm64/lithium-codegen-arm64.h"
9 #include "src/arm64/lithium-gap-resolver-arm64.h"
10
11 namespace v8 {
12 namespace internal {
13
14 #define __ ACCESS_MASM((&masm_))
15
16
EndDelayedUse()17 void DelayedGapMasm::EndDelayedUse() {
18 DelayedMasm::EndDelayedUse();
19 if (scratch_register_used()) {
20 DCHECK(ScratchRegister().Is(root));
21 DCHECK(!pending());
22 InitializeRootRegister();
23 reset_scratch_register_used();
24 }
25 }
26
27
LGapResolver(LCodeGen * owner)28 LGapResolver::LGapResolver(LCodeGen* owner)
29 : cgen_(owner), masm_(owner, owner->masm()), moves_(32, owner->zone()),
30 root_index_(0), in_cycle_(false), saved_destination_(NULL) {
31 }
32
33
Resolve(LParallelMove * parallel_move)34 void LGapResolver::Resolve(LParallelMove* parallel_move) {
35 DCHECK(moves_.is_empty());
36 DCHECK(!masm_.pending());
37
38 // Build up a worklist of moves.
39 BuildInitialMoveList(parallel_move);
40
41 for (int i = 0; i < moves_.length(); ++i) {
42 LMoveOperands move = moves_[i];
43
44 // Skip constants to perform them last. They don't block other moves
45 // and skipping such moves with register destinations keeps those
46 // registers free for the whole algorithm.
47 if (!move.IsEliminated() && !move.source()->IsConstantOperand()) {
48 root_index_ = i; // Any cycle is found when we reach this move again.
49 PerformMove(i);
50 if (in_cycle_) RestoreValue();
51 }
52 }
53
54 // Perform the moves with constant sources.
55 for (int i = 0; i < moves_.length(); ++i) {
56 LMoveOperands move = moves_[i];
57
58 if (!move.IsEliminated()) {
59 DCHECK(move.source()->IsConstantOperand());
60 EmitMove(i);
61 }
62 }
63
64 __ EndDelayedUse();
65
66 moves_.Rewind(0);
67 }
68
69
BuildInitialMoveList(LParallelMove * parallel_move)70 void LGapResolver::BuildInitialMoveList(LParallelMove* parallel_move) {
71 // Perform a linear sweep of the moves to add them to the initial list of
72 // moves to perform, ignoring any move that is redundant (the source is
73 // the same as the destination, the destination is ignored and
74 // unallocated, or the move was already eliminated).
75 const ZoneList<LMoveOperands>* moves = parallel_move->move_operands();
76 for (int i = 0; i < moves->length(); ++i) {
77 LMoveOperands move = moves->at(i);
78 if (!move.IsRedundant()) moves_.Add(move, cgen_->zone());
79 }
80 Verify();
81 }
82
83
PerformMove(int index)84 void LGapResolver::PerformMove(int index) {
85 // Each call to this function performs a move and deletes it from the move
86 // graph. We first recursively perform any move blocking this one. We
87 // mark a move as "pending" on entry to PerformMove in order to detect
88 // cycles in the move graph.
89 LMoveOperands& current_move = moves_[index];
90
91 DCHECK(!current_move.IsPending());
92 DCHECK(!current_move.IsRedundant());
93
94 // Clear this move's destination to indicate a pending move. The actual
95 // destination is saved in a stack allocated local. Multiple moves can
96 // be pending because this function is recursive.
97 DCHECK(current_move.source() != NULL); // Otherwise it will look eliminated.
98 LOperand* destination = current_move.destination();
99 current_move.set_destination(NULL);
100
101 // Perform a depth-first traversal of the move graph to resolve
102 // dependencies. Any unperformed, unpending move with a source the same
103 // as this one's destination blocks this one so recursively perform all
104 // such moves.
105 for (int i = 0; i < moves_.length(); ++i) {
106 LMoveOperands other_move = moves_[i];
107 if (other_move.Blocks(destination) && !other_move.IsPending()) {
108 PerformMove(i);
109 // If there is a blocking, pending move it must be moves_[root_index_]
110 // and all other moves with the same source as moves_[root_index_] are
111 // sucessfully executed (because they are cycle-free) by this loop.
112 }
113 }
114
115 // We are about to resolve this move and don't need it marked as
116 // pending, so restore its destination.
117 current_move.set_destination(destination);
118
119 // The move may be blocked on a pending move, which must be the starting move.
120 // In this case, we have a cycle, and we save the source of this move to
121 // a scratch register to break it.
122 LMoveOperands other_move = moves_[root_index_];
123 if (other_move.Blocks(destination)) {
124 DCHECK(other_move.IsPending());
125 BreakCycle(index);
126 return;
127 }
128
129 // This move is no longer blocked.
130 EmitMove(index);
131 }
132
133
Verify()134 void LGapResolver::Verify() {
135 #ifdef ENABLE_SLOW_DCHECKS
136 // No operand should be the destination for more than one move.
137 for (int i = 0; i < moves_.length(); ++i) {
138 LOperand* destination = moves_[i].destination();
139 for (int j = i + 1; j < moves_.length(); ++j) {
140 SLOW_DCHECK(!destination->Equals(moves_[j].destination()));
141 }
142 }
143 #endif
144 }
145
146
BreakCycle(int index)147 void LGapResolver::BreakCycle(int index) {
148 DCHECK(moves_[index].destination()->Equals(moves_[root_index_].source()));
149 DCHECK(!in_cycle_);
150
151 // We save in a register the source of that move and we remember its
152 // destination. Then we mark this move as resolved so the cycle is
153 // broken and we can perform the other moves.
154 in_cycle_ = true;
155 LOperand* source = moves_[index].source();
156 saved_destination_ = moves_[index].destination();
157
158 if (source->IsRegister()) {
159 AcquireSavedValueRegister();
160 __ Mov(SavedValueRegister(), cgen_->ToRegister(source));
161 } else if (source->IsStackSlot()) {
162 AcquireSavedValueRegister();
163 __ Load(SavedValueRegister(), cgen_->ToMemOperand(source));
164 } else if (source->IsDoubleRegister()) {
165 __ Fmov(SavedFPValueRegister(), cgen_->ToDoubleRegister(source));
166 } else if (source->IsDoubleStackSlot()) {
167 __ Load(SavedFPValueRegister(), cgen_->ToMemOperand(source));
168 } else {
169 UNREACHABLE();
170 }
171
172 // Mark this move as resolved.
173 // This move will be actually performed by moving the saved value to this
174 // move's destination in LGapResolver::RestoreValue().
175 moves_[index].Eliminate();
176 }
177
178
RestoreValue()179 void LGapResolver::RestoreValue() {
180 DCHECK(in_cycle_);
181 DCHECK(saved_destination_ != NULL);
182
183 if (saved_destination_->IsRegister()) {
184 __ Mov(cgen_->ToRegister(saved_destination_), SavedValueRegister());
185 ReleaseSavedValueRegister();
186 } else if (saved_destination_->IsStackSlot()) {
187 __ Store(SavedValueRegister(), cgen_->ToMemOperand(saved_destination_));
188 ReleaseSavedValueRegister();
189 } else if (saved_destination_->IsDoubleRegister()) {
190 __ Fmov(cgen_->ToDoubleRegister(saved_destination_),
191 SavedFPValueRegister());
192 } else if (saved_destination_->IsDoubleStackSlot()) {
193 __ Store(SavedFPValueRegister(), cgen_->ToMemOperand(saved_destination_));
194 } else {
195 UNREACHABLE();
196 }
197
198 in_cycle_ = false;
199 saved_destination_ = NULL;
200 }
201
202
EmitMove(int index)203 void LGapResolver::EmitMove(int index) {
204 LOperand* source = moves_[index].source();
205 LOperand* destination = moves_[index].destination();
206
207 // Dispatch on the source and destination operand kinds. Not all
208 // combinations are possible.
209
210 if (source->IsRegister()) {
211 Register source_register = cgen_->ToRegister(source);
212 if (destination->IsRegister()) {
213 __ Mov(cgen_->ToRegister(destination), source_register);
214 } else {
215 DCHECK(destination->IsStackSlot());
216 __ Store(source_register, cgen_->ToMemOperand(destination));
217 }
218
219 } else if (source->IsStackSlot()) {
220 MemOperand source_operand = cgen_->ToMemOperand(source);
221 if (destination->IsRegister()) {
222 __ Load(cgen_->ToRegister(destination), source_operand);
223 } else {
224 DCHECK(destination->IsStackSlot());
225 EmitStackSlotMove(index);
226 }
227
228 } else if (source->IsConstantOperand()) {
229 LConstantOperand* constant_source = LConstantOperand::cast(source);
230 if (destination->IsRegister()) {
231 Register dst = cgen_->ToRegister(destination);
232 if (cgen_->IsSmi(constant_source)) {
233 __ Mov(dst, cgen_->ToSmi(constant_source));
234 } else if (cgen_->IsInteger32Constant(constant_source)) {
235 __ Mov(dst, cgen_->ToInteger32(constant_source));
236 } else {
237 __ LoadObject(dst, cgen_->ToHandle(constant_source));
238 }
239 } else if (destination->IsDoubleRegister()) {
240 DoubleRegister result = cgen_->ToDoubleRegister(destination);
241 __ Fmov(result, cgen_->ToDouble(constant_source));
242 } else {
243 DCHECK(destination->IsStackSlot());
244 DCHECK(!in_cycle_); // Constant moves happen after all cycles are gone.
245 if (cgen_->IsSmi(constant_source)) {
246 Smi* smi = cgen_->ToSmi(constant_source);
247 __ StoreConstant(reinterpret_cast<intptr_t>(smi),
248 cgen_->ToMemOperand(destination));
249 } else if (cgen_->IsInteger32Constant(constant_source)) {
250 __ StoreConstant(cgen_->ToInteger32(constant_source),
251 cgen_->ToMemOperand(destination));
252 } else {
253 Handle<Object> handle = cgen_->ToHandle(constant_source);
254 AllowDeferredHandleDereference smi_object_check;
255 if (handle->IsSmi()) {
256 Object* obj = *handle;
257 DCHECK(!obj->IsHeapObject());
258 __ StoreConstant(reinterpret_cast<intptr_t>(obj),
259 cgen_->ToMemOperand(destination));
260 } else {
261 AcquireSavedValueRegister();
262 __ LoadObject(SavedValueRegister(), handle);
263 __ Store(SavedValueRegister(), cgen_->ToMemOperand(destination));
264 ReleaseSavedValueRegister();
265 }
266 }
267 }
268
269 } else if (source->IsDoubleRegister()) {
270 DoubleRegister src = cgen_->ToDoubleRegister(source);
271 if (destination->IsDoubleRegister()) {
272 __ Fmov(cgen_->ToDoubleRegister(destination), src);
273 } else {
274 DCHECK(destination->IsDoubleStackSlot());
275 __ Store(src, cgen_->ToMemOperand(destination));
276 }
277
278 } else if (source->IsDoubleStackSlot()) {
279 MemOperand src = cgen_->ToMemOperand(source);
280 if (destination->IsDoubleRegister()) {
281 __ Load(cgen_->ToDoubleRegister(destination), src);
282 } else {
283 DCHECK(destination->IsDoubleStackSlot());
284 EmitStackSlotMove(index);
285 }
286
287 } else {
288 UNREACHABLE();
289 }
290
291 // The move has been emitted, we can eliminate it.
292 moves_[index].Eliminate();
293 }
294
295 } } // namespace v8::internal
296