1 // Copyright 2009 the V8 project authors. All rights reserved. 2 // Redistribution and use in source and binary forms, with or without 3 // modification, are permitted provided that the following conditions are 4 // met: 5 // 6 // * Redistributions of source code must retain the above copyright 7 // notice, this list of conditions and the following disclaimer. 8 // * Redistributions in binary form must reproduce the above 9 // copyright notice, this list of conditions and the following 10 // disclaimer in the documentation and/or other materials provided 11 // with the distribution. 12 // * Neither the name of Google Inc. nor the names of its 13 // contributors may be used to endorse or promote products derived 14 // from this software without specific prior written permission. 15 // 16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 17 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 18 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 19 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 20 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 21 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 22 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27 28 #include "v8.h" 29 30 #include "codegen-inl.h" 31 #include "register-allocator-inl.h" 32 33 namespace v8 { 34 namespace internal { 35 36 // ------------------------------------------------------------------------- 37 // VirtualFrame implementation. 38 39 // When cloned, a frame is a deep copy of the original. 40 VirtualFrame::VirtualFrame(VirtualFrame* original) 41 : elements_(original->element_count()), 42 stack_pointer_(original->stack_pointer_) { 43 elements_.AddAll(original->elements_); 44 // Copy register locations from original. 45 memcpy(®ister_locations_, 46 original->register_locations_, 47 sizeof(register_locations_)); 48 } 49 50 51 // Create a duplicate of an existing valid frame element. 52 // We can pass an optional number type information that will override the 53 // existing information about the backing element. The new information must 54 // not conflict with the existing type information and must be equally or 55 // more precise. The default parameter value kUninitialized means that there 56 // is no additional information. 57 FrameElement VirtualFrame::CopyElementAt(int index, NumberInfo::Type info) { 58 ASSERT(index >= 0); 59 ASSERT(index < element_count()); 60 61 FrameElement target = elements_[index]; 62 FrameElement result; 63 64 switch (target.type()) { 65 case FrameElement::CONSTANT: 66 // We do not copy constants and instead return a fresh unsynced 67 // constant. 68 result = FrameElement::ConstantElement(target.handle(), 69 FrameElement::NOT_SYNCED); 70 break; 71 72 case FrameElement::COPY: 73 // We do not allow copies of copies, so we follow one link to 74 // the actual backing store of a copy before making a copy. 75 index = target.index(); 76 ASSERT(elements_[index].is_memory() || elements_[index].is_register()); 77 // Fall through. 78 79 case FrameElement::MEMORY: // Fall through. 80 case FrameElement::REGISTER: { 81 // All copies are backed by memory or register locations. 82 result.set_type(FrameElement::COPY); 83 result.clear_copied(); 84 result.clear_sync(); 85 result.set_index(index); 86 elements_[index].set_copied(); 87 // Update backing element's number information. 88 NumberInfo::Type existing = elements_[index].number_info(); 89 ASSERT(existing != NumberInfo::kUninitialized); 90 // Assert that the new type information (a) does not conflict with the 91 // existing one and (b) is equally or more precise. 92 ASSERT((info == NumberInfo::kUninitialized) || 93 (existing | info) != NumberInfo::kUninitialized); 94 ASSERT(existing <= info); 95 elements_[index].set_number_info(info != NumberInfo::kUninitialized 96 ? info 97 : existing); 98 break; 99 } 100 case FrameElement::INVALID: 101 // We should not try to copy invalid elements. 102 UNREACHABLE(); 103 break; 104 } 105 return result; 106 } 107 108 109 // Modify the state of the virtual frame to match the actual frame by adding 110 // extra in-memory elements to the top of the virtual frame. The extra 111 // elements will be externally materialized on the actual frame (eg, by 112 // pushing an exception handler). No code is emitted. 113 void VirtualFrame::Adjust(int count) { 114 ASSERT(count >= 0); 115 ASSERT(stack_pointer_ == element_count() - 1); 116 117 for (int i = 0; i < count; i++) { 118 elements_.Add(FrameElement::MemoryElement(NumberInfo::kUnknown)); 119 } 120 stack_pointer_ += count; 121 } 122 123 124 void VirtualFrame::ForgetElements(int count) { 125 ASSERT(count >= 0); 126 ASSERT(element_count() >= count); 127 128 for (int i = 0; i < count; i++) { 129 FrameElement last = elements_.RemoveLast(); 130 if (last.is_register()) { 131 // A hack to properly count register references for the code 132 // generator's current frame and also for other frames. The 133 // same code appears in PrepareMergeTo. 134 if (cgen()->frame() == this) { 135 Unuse(last.reg()); 136 } else { 137 set_register_location(last.reg(), kIllegalIndex); 138 } 139 } 140 } 141 } 142 143 144 // If there are any registers referenced only by the frame, spill one. 145 Register VirtualFrame::SpillAnyRegister() { 146 // Find the leftmost (ordered by register number) register whose only 147 // reference is in the frame. 148 for (int i = 0; i < RegisterAllocator::kNumRegisters; i++) { 149 if (is_used(i) && cgen()->allocator()->count(i) == 1) { 150 SpillElementAt(register_location(i)); 151 ASSERT(!cgen()->allocator()->is_used(i)); 152 return RegisterAllocator::ToRegister(i); 153 } 154 } 155 return no_reg; 156 } 157 158 159 // Make the type of the element at a given index be MEMORY. 160 void VirtualFrame::SpillElementAt(int index) { 161 if (!elements_[index].is_valid()) return; 162 163 SyncElementAt(index); 164 // Number type information is preserved. 165 // Copies get their number information from their backing element. 166 NumberInfo::Type info; 167 if (!elements_[index].is_copy()) { 168 info = elements_[index].number_info(); 169 } else { 170 info = elements_[elements_[index].index()].number_info(); 171 } 172 // The element is now in memory. Its copied flag is preserved. 173 FrameElement new_element = FrameElement::MemoryElement(info); 174 if (elements_[index].is_copied()) { 175 new_element.set_copied(); 176 } 177 if (elements_[index].is_register()) { 178 Unuse(elements_[index].reg()); 179 } 180 elements_[index] = new_element; 181 } 182 183 184 // Clear the dirty bit for the element at a given index. 185 void VirtualFrame::SyncElementAt(int index) { 186 if (index <= stack_pointer_) { 187 if (!elements_[index].is_synced()) SyncElementBelowStackPointer(index); 188 } else if (index == stack_pointer_ + 1) { 189 SyncElementByPushing(index); 190 } else { 191 SyncRange(stack_pointer_ + 1, index); 192 } 193 } 194 195 196 // Make the type of all elements be MEMORY. 197 void VirtualFrame::SpillAll() { 198 for (int i = 0; i < element_count(); i++) { 199 SpillElementAt(i); 200 } 201 } 202 203 204 void VirtualFrame::PrepareMergeTo(VirtualFrame* expected) { 205 // Perform state changes on this frame that will make merge to the 206 // expected frame simpler or else increase the likelihood that his 207 // frame will match another. 208 for (int i = 0; i < element_count(); i++) { 209 FrameElement source = elements_[i]; 210 FrameElement target = expected->elements_[i]; 211 212 if (!target.is_valid() || 213 (target.is_memory() && !source.is_memory() && source.is_synced())) { 214 // No code needs to be generated to invalidate valid elements. 215 // No code needs to be generated to move values to memory if 216 // they are already synced. We perform those moves here, before 217 // merging. 218 if (source.is_register()) { 219 // If the frame is the code generator's current frame, we have 220 // to decrement both the frame-internal and global register 221 // counts. 222 if (cgen()->frame() == this) { 223 Unuse(source.reg()); 224 } else { 225 set_register_location(source.reg(), kIllegalIndex); 226 } 227 } 228 elements_[i] = target; 229 } else if (target.is_register() && !target.is_synced() && 230 !source.is_memory()) { 231 // If an element's target is a register that doesn't need to be 232 // synced, and the element is not in memory, then the sync state 233 // of the element is irrelevant. We clear the sync bit. 234 ASSERT(source.is_valid()); 235 elements_[i].clear_sync(); 236 } 237 } 238 } 239 240 241 void VirtualFrame::PrepareForCall(int spilled_args, int dropped_args) { 242 ASSERT(height() >= dropped_args); 243 ASSERT(height() >= spilled_args); 244 ASSERT(dropped_args <= spilled_args); 245 246 SyncRange(0, element_count() - 1); 247 // Spill registers. 248 for (int i = 0; i < RegisterAllocator::kNumRegisters; i++) { 249 if (is_used(i)) { 250 SpillElementAt(register_location(i)); 251 } 252 } 253 254 // Spill the arguments. 255 for (int i = element_count() - spilled_args; i < element_count(); i++) { 256 if (!elements_[i].is_memory()) { 257 SpillElementAt(i); 258 } 259 } 260 261 // Forget the frame elements that will be popped by the call. 262 Forget(dropped_args); 263 } 264 265 266 void VirtualFrame::PrepareForReturn() { 267 // Spill all locals. This is necessary to make sure all locals have 268 // the right value when breaking at the return site in the debugger. 269 for (int i = 0; i < expression_base_index(); i++) { 270 SpillElementAt(i); 271 } 272 } 273 274 275 void VirtualFrame::SetElementAt(int index, Result* value) { 276 int frame_index = element_count() - index - 1; 277 ASSERT(frame_index >= 0); 278 ASSERT(frame_index < element_count()); 279 ASSERT(value->is_valid()); 280 FrameElement original = elements_[frame_index]; 281 282 // Early exit if the element is the same as the one being set. 283 bool same_register = original.is_register() 284 && value->is_register() 285 && original.reg().is(value->reg()); 286 bool same_constant = original.is_constant() 287 && value->is_constant() 288 && original.handle().is_identical_to(value->handle()); 289 if (same_register || same_constant) { 290 value->Unuse(); 291 return; 292 } 293 294 InvalidateFrameSlotAt(frame_index); 295 296 if (value->is_register()) { 297 if (is_used(value->reg())) { 298 // The register already appears on the frame. Either the existing 299 // register element, or the new element at frame_index, must be made 300 // a copy. 301 int i = register_location(value->reg()); 302 303 if (i < frame_index) { 304 // The register FrameElement is lower in the frame than the new copy. 305 elements_[frame_index] = CopyElementAt(i); 306 } else { 307 // There was an early bailout for the case of setting a 308 // register element to itself. 309 ASSERT(i != frame_index); 310 elements_[frame_index] = elements_[i]; 311 elements_[i] = CopyElementAt(frame_index); 312 if (elements_[frame_index].is_synced()) { 313 elements_[i].set_sync(); 314 } 315 elements_[frame_index].clear_sync(); 316 set_register_location(value->reg(), frame_index); 317 for (int j = i + 1; j < element_count(); j++) { 318 if (elements_[j].is_copy() && elements_[j].index() == i) { 319 elements_[j].set_index(frame_index); 320 } 321 } 322 } 323 } else { 324 // The register value->reg() was not already used on the frame. 325 Use(value->reg(), frame_index); 326 elements_[frame_index] = 327 FrameElement::RegisterElement(value->reg(), 328 FrameElement::NOT_SYNCED, 329 value->number_info()); 330 } 331 } else { 332 ASSERT(value->is_constant()); 333 elements_[frame_index] = 334 FrameElement::ConstantElement(value->handle(), 335 FrameElement::NOT_SYNCED); 336 } 337 value->Unuse(); 338 } 339 340 341 void VirtualFrame::PushFrameSlotAt(int index) { 342 elements_.Add(CopyElementAt(index)); 343 } 344 345 346 void VirtualFrame::Push(Register reg, NumberInfo::Type info) { 347 if (is_used(reg)) { 348 int index = register_location(reg); 349 FrameElement element = CopyElementAt(index, info); 350 elements_.Add(element); 351 } else { 352 Use(reg, element_count()); 353 FrameElement element = 354 FrameElement::RegisterElement(reg, FrameElement::NOT_SYNCED, info); 355 elements_.Add(element); 356 } 357 } 358 359 360 void VirtualFrame::Push(Handle<Object> value) { 361 FrameElement element = 362 FrameElement::ConstantElement(value, FrameElement::NOT_SYNCED); 363 elements_.Add(element); 364 } 365 366 367 void VirtualFrame::Nip(int num_dropped) { 368 ASSERT(num_dropped >= 0); 369 if (num_dropped == 0) return; 370 Result tos = Pop(); 371 if (num_dropped > 1) { 372 Drop(num_dropped - 1); 373 } 374 SetElementAt(0, &tos); 375 } 376 377 378 bool VirtualFrame::Equals(VirtualFrame* other) { 379 #ifdef DEBUG 380 for (int i = 0; i < RegisterAllocator::kNumRegisters; i++) { 381 if (register_location(i) != other->register_location(i)) { 382 return false; 383 } 384 } 385 if (element_count() != other->element_count()) return false; 386 #endif 387 if (stack_pointer_ != other->stack_pointer_) return false; 388 for (int i = 0; i < element_count(); i++) { 389 if (!elements_[i].Equals(other->elements_[i])) return false; 390 } 391 392 return true; 393 } 394 395 396 // Specialization of List::ResizeAdd to non-inlined version for FrameElements. 397 // The function ResizeAdd becomes a real function, whose implementation is the 398 // inlined ResizeAddInternal. 399 template <> 400 void List<FrameElement, 401 FreeStoreAllocationPolicy>::ResizeAdd(const FrameElement& element) { 402 ResizeAddInternal(element); 403 } 404 405 } } // namespace v8::internal 406