virtual-frame.cc 12.2 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
// Copyright 2009 the V8 project authors. All rights reserved.
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
//     * Redistributions of source code must retain the above copyright
//       notice, this list of conditions and the following disclaimer.
//     * Redistributions in binary form must reproduce the above
//       copyright notice, this list of conditions and the following
//       disclaimer in the documentation and/or other materials provided
//       with the distribution.
//     * Neither the name of Google Inc. nor the names of its
//       contributors may be used to endorse or promote products derived
//       from this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

#include "v8.h"

#include "codegen-inl.h"
31
#include "register-allocator-inl.h"
32

33 34
namespace v8 {
namespace internal {
35 36 37 38 39 40

// -------------------------------------------------------------------------
// VirtualFrame implementation.

// When cloned, a frame is a deep copy of the original.
VirtualFrame::VirtualFrame(VirtualFrame* original)
41
    : elements_(original->element_count()),
42
      stack_pointer_(original->stack_pointer_) {
43
  elements_.AddAll(original->elements_);
44 45 46 47
  // Copy register locations from original.
  memcpy(&register_locations_,
         original->register_locations_,
         sizeof(register_locations_));
48 49 50 51 52
}


FrameElement VirtualFrame::CopyElementAt(int index) {
  ASSERT(index >= 0);
53
  ASSERT(index < element_count());
54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75

  FrameElement target = elements_[index];
  FrameElement result;

  switch (target.type()) {
    case FrameElement::CONSTANT:
      // We do not copy constants and instead return a fresh unsynced
      // constant.
      result = FrameElement::ConstantElement(target.handle(),
                                             FrameElement::NOT_SYNCED);
      break;

    case FrameElement::COPY:
      // We do not allow copies of copies, so we follow one link to
      // the actual backing store of a copy before making a copy.
      index = target.index();
      ASSERT(elements_[index].is_memory() || elements_[index].is_register());
      // Fall through.

    case FrameElement::MEMORY:  // Fall through.
    case FrameElement::REGISTER:
      // All copies are backed by memory or register locations.
76 77 78 79
      result.set_type(FrameElement::COPY);
      result.clear_copied();
      result.clear_sync();
      result.set_index(index);
80
      elements_[index].set_copied();
81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97
      break;

    case FrameElement::INVALID:
      // We should not try to copy invalid elements.
      UNREACHABLE();
      break;
  }
  return result;
}


// Modify the state of the virtual frame to match the actual frame by adding
// extra in-memory elements to the top of the virtual frame.  The extra
// elements will be externally materialized on the actual frame (eg, by
// pushing an exception handler).  No code is emitted.
void VirtualFrame::Adjust(int count) {
  ASSERT(count >= 0);
98
  ASSERT(stack_pointer_ == element_count() - 1);
99 100 101 102 103 104 105 106

  for (int i = 0; i < count; i++) {
    elements_.Add(FrameElement::MemoryElement());
  }
  stack_pointer_ += count;
}


107 108
void VirtualFrame::ForgetElements(int count) {
  ASSERT(count >= 0);
109
  ASSERT(element_count() >= count);
110

111 112 113
  for (int i = 0; i < count; i++) {
    FrameElement last = elements_.RemoveLast();
    if (last.is_register()) {
114 115 116
      // A hack to properly count register references for the code
      // generator's current frame and also for other frames.  The
      // same code appears in PrepareMergeTo.
117
      if (cgen()->frame() == this) {
118 119
        Unuse(last.reg());
      } else {
120
        set_register_location(last.reg(), kIllegalIndex);
121
      }
122 123 124 125 126
    }
  }
}


127
// If there are any registers referenced only by the frame, spill one.
128
Register VirtualFrame::SpillAnyRegister() {
129
  // Find the leftmost (ordered by register number) register whose only
130
  // reference is in the frame.
131
  for (int i = 0; i < RegisterAllocator::kNumRegisters; i++) {
132
    if (is_used(i) && cgen()->allocator()->count(i) == 1) {
133 134 135
      SpillElementAt(register_location(i));
      ASSERT(!cgen()->allocator()->is_used(i));
      return RegisterAllocator::ToRegister(i);
136 137
    }
  }
138
  return no_reg;
139 140 141 142 143 144 145 146
}


// Make the type of the element at a given index be MEMORY.
void VirtualFrame::SpillElementAt(int index) {
  if (!elements_[index].is_valid()) return;

  SyncElementAt(index);
147 148 149 150 151
  // The element is now in memory.  Its copied flag is preserved.
  FrameElement new_element = FrameElement::MemoryElement();
  if (elements_[index].is_copied()) {
    new_element.set_copied();
  }
152 153 154
  if (elements_[index].is_register()) {
    Unuse(elements_[index].reg());
  }
155
  elements_[index] = new_element;
156 157 158 159 160
}


// Clear the dirty bit for the element at a given index.
void VirtualFrame::SyncElementAt(int index) {
161
  if (index <= stack_pointer_) {
162 163 164
    if (!elements_[index].is_synced()) SyncElementBelowStackPointer(index);
  } else if (index == stack_pointer_ + 1) {
    SyncElementByPushing(index);
165
  } else {
166
    SyncRange(stack_pointer_ + 1, index);
167 168 169 170 171 172
  }
}


// Make the type of all elements be MEMORY.
void VirtualFrame::SpillAll() {
173
  for (int i = 0; i < element_count(); i++) {
174 175 176 177 178 179
    SpillElementAt(i);
  }
}


void VirtualFrame::PrepareMergeTo(VirtualFrame* expected) {
180 181 182
  // Perform state changes on this frame that will make merge to the
  // expected frame simpler or else increase the likelihood that his
  // frame will match another.
183
  for (int i = 0; i < element_count(); i++) {
184 185
    FrameElement source = elements_[i];
    FrameElement target = expected->elements_[i];
186

187 188
    if (!target.is_valid() ||
        (target.is_memory() && !source.is_memory() && source.is_synced())) {
189 190 191 192
      // No code needs to be generated to invalidate valid elements.
      // No code needs to be generated to move values to memory if
      // they are already synced.  We perform those moves here, before
      // merging.
193 194 195 196
      if (source.is_register()) {
        // If the frame is the code generator's current frame, we have
        // to decrement both the frame-internal and global register
        // counts.
197
        if (cgen()->frame() == this) {
198 199
          Unuse(source.reg());
        } else {
200
          set_register_location(source.reg(), kIllegalIndex);
201 202 203
        }
      }
      elements_[i] = target;
204 205 206 207 208 209 210
    } else if (target.is_register() && !target.is_synced() &&
               !source.is_memory()) {
      // If an element's target is a register that doesn't need to be
      // synced, and the element is not in memory, then the sync state
      // of the element is irrelevant.  We clear the sync bit.
      ASSERT(source.is_valid());
      elements_[i].clear_sync();
211 212 213 214 215 216 217 218 219 220
    }
  }
}


void VirtualFrame::PrepareForCall(int spilled_args, int dropped_args) {
  ASSERT(height() >= dropped_args);
  ASSERT(height() >= spilled_args);
  ASSERT(dropped_args <= spilled_args);

221
  SyncRange(0, element_count() - 1);
222
  // Spill registers.
223
  for (int i = 0; i < RegisterAllocator::kNumRegisters; i++) {
224
    if (is_used(i)) {
225
      SpillElementAt(register_location(i));
226
    }
227 228
  }

229
  // Spill the arguments.
230
  for (int i = element_count() - spilled_args; i < element_count(); i++) {
231
    if (!elements_[i].is_memory()) {
232 233 234 235 236 237 238 239 240 241 242 243
      SpillElementAt(i);
    }
  }

  // Forget the frame elements that will be popped by the call.
  Forget(dropped_args);
}


void VirtualFrame::PrepareForReturn() {
  // Spill all locals. This is necessary to make sure all locals have
  // the right value when breaking at the return site in the debugger.
244 245 246
  for (int i = 0; i < expression_base_index(); i++) {
    SpillElementAt(i);
  }
247 248 249 250
}


void VirtualFrame::SetElementAt(int index, Result* value) {
251
  int frame_index = element_count() - index - 1;
252
  ASSERT(frame_index >= 0);
253
  ASSERT(frame_index < element_count());
254 255 256 257 258
  ASSERT(value->is_valid());
  FrameElement original = elements_[frame_index];

  // Early exit if the element is the same as the one being set.
  bool same_register = original.is_register()
259 260
      && value->is_register()
      && original.reg().is(value->reg());
261
  bool same_constant = original.is_constant()
262 263
      && value->is_constant()
      && original.handle().is_identical_to(value->handle());
264 265 266 267 268
  if (same_register || same_constant) {
    value->Unuse();
    return;
  }

269
  InvalidateFrameSlotAt(frame_index);
270 271 272

  FrameElement new_element;
  if (value->is_register()) {
273 274 275 276
    if (is_used(value->reg())) {
      // The register already appears on the frame.  Either the existing
      // register element, or the new element at frame_index, must be made
      // a copy.
277
      int i = register_location(value->reg());
278

279
      if (i < frame_index) {
280
        // The register FrameElement is lower in the frame than the new copy.
281 282 283 284 285 286 287 288 289 290 291
        elements_[frame_index] = CopyElementAt(i);
      } else {
        // There was an early bailout for the case of setting a
        // register element to itself.
        ASSERT(i != frame_index);
        elements_[frame_index] = elements_[i];
        elements_[i] = CopyElementAt(frame_index);
        if (elements_[frame_index].is_synced()) {
          elements_[i].set_sync();
        }
        elements_[frame_index].clear_sync();
292 293
        set_register_location(value->reg(), frame_index);
        for (int j = i + 1; j < element_count(); j++) {
294 295 296 297 298
          if (elements_[j].is_copy() && elements_[j].index() == i) {
            elements_[j].set_index(frame_index);
          }
        }
      }
299 300 301 302 303
    } else {
      // The register value->reg() was not already used on the frame.
      Use(value->reg(), frame_index);
      elements_[frame_index] =
          FrameElement::RegisterElement(value->reg(),
304
                                        FrameElement::NOT_SYNCED);
305 306 307 308 309 310 311 312 313 314 315 316
    }
  } else {
    ASSERT(value->is_constant());
    elements_[frame_index] =
        FrameElement::ConstantElement(value->handle(),
                                      FrameElement::NOT_SYNCED);
  }
  value->Unuse();
}


void VirtualFrame::PushFrameSlotAt(int index) {
317
  elements_.Add(CopyElementAt(index));
318 319 320
}


321
void VirtualFrame::Push(Register reg) {
322
  if (is_used(reg)) {
323
    int index = register_location(reg);
324 325
    FrameElement element = CopyElementAt(index);
    elements_.Add(element);
326
  } else {
327
    Use(reg, element_count());
328 329
    FrameElement element =
        FrameElement::RegisterElement(reg,
330
                                      FrameElement::NOT_SYNCED);
331
    elements_.Add(element);
332 333 334 335 336
  }
}


void VirtualFrame::Push(Handle<Object> value) {
337 338 339
  FrameElement element =
      FrameElement::ConstantElement(value, FrameElement::NOT_SYNCED);
  elements_.Add(element);
340 341 342 343 344 345 346 347 348 349 350 351 352 353 354
}


void VirtualFrame::Nip(int num_dropped) {
  ASSERT(num_dropped >= 0);
  if (num_dropped == 0) return;
  Result tos = Pop();
  if (num_dropped > 1) {
    Drop(num_dropped - 1);
  }
  SetElementAt(0, &tos);
}


bool VirtualFrame::Equals(VirtualFrame* other) {
355
#ifdef DEBUG
356 357
  for (int i = 0; i < RegisterAllocator::kNumRegisters; i++) {
    if (register_location(i) != other->register_location(i)) {
358 359
      return false;
    }
360
  }
361
  if (element_count() != other->element_count()) return false;
362 363
#endif
  if (stack_pointer_ != other->stack_pointer_) return false;
364
  for (int i = 0; i < element_count(); i++) {
365 366
    if (!elements_[i].Equals(other->elements_[i])) return false;
  }
367 368 369 370

  return true;
}

371 372 373 374 375 376 377 378 379 380

// Specialization of List::ResizeAdd to non-inlined version for FrameElements.
// The function ResizeAdd becomes a real function, whose implementation is the
// inlined ResizeAddInternal.
template <>
void List<FrameElement,
          FreeStoreAllocationPolicy>::ResizeAdd(const FrameElement& element) {
  ResizeAddInternal(element);
}

381
} }  // namespace v8::internal