ager@chromium.org | 5ec4892 | 2009-05-05 07:25:34 +0000 | [diff] [blame] | 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 | |
ager@chromium.org | 5aa501c | 2009-06-23 07:57:28 +0000 | [diff] [blame] | 28 | #include "v8.h" |
| 29 | |
| 30 | #include "codegen-inl.h" |
| 31 | #include "jump-target-inl.h" |
| 32 | #include "register-allocator-inl.h" |
| 33 | |
| 34 | namespace v8 { |
| 35 | namespace internal { |
| 36 | |
| 37 | // ------------------------------------------------------------------------- |
| 38 | // JumpTarget implementation. |
| 39 | |
| 40 | #define __ ACCESS_MASM(cgen()->masm()) |
| 41 | |
| 42 | void JumpTarget::DoJump() { |
| 43 | ASSERT(cgen()->has_valid_frame()); |
| 44 | // Live non-frame registers are not allowed at unconditional jumps |
| 45 | // because we have no way of invalidating the corresponding results |
| 46 | // which are still live in the C++ code. |
| 47 | ASSERT(cgen()->HasValidEntryRegisters()); |
| 48 | |
| 49 | if (is_bound()) { |
| 50 | // Backward jump. There is an expected frame to merge to. |
| 51 | ASSERT(direction_ == BIDIRECTIONAL); |
| 52 | cgen()->frame()->PrepareMergeTo(entry_frame_); |
| 53 | cgen()->frame()->MergeTo(entry_frame_); |
| 54 | cgen()->DeleteFrame(); |
| 55 | __ jmp(&entry_label_); |
| 56 | } else if (entry_frame_ != NULL) { |
| 57 | // Forward jump with a preconfigured entry frame. Assert the |
| 58 | // current frame matches the expected one and jump to the block. |
| 59 | ASSERT(cgen()->frame()->Equals(entry_frame_)); |
| 60 | cgen()->DeleteFrame(); |
| 61 | __ jmp(&entry_label_); |
| 62 | } else { |
| 63 | // Forward jump. Remember the current frame and emit a jump to |
| 64 | // its merge code. |
| 65 | AddReachingFrame(cgen()->frame()); |
| 66 | RegisterFile empty; |
| 67 | cgen()->SetFrame(NULL, &empty); |
| 68 | __ jmp(&merge_labels_.last()); |
| 69 | } |
| 70 | } |
| 71 | |
| 72 | |
| 73 | void JumpTarget::DoBranch(Condition cc, Hint b) { |
| 74 | ASSERT(cgen() != NULL); |
| 75 | ASSERT(cgen()->has_valid_frame()); |
| 76 | |
| 77 | if (is_bound()) { |
| 78 | ASSERT(direction_ == BIDIRECTIONAL); |
| 79 | // Backward branch. We have an expected frame to merge to on the |
| 80 | // backward edge. |
| 81 | |
| 82 | // Swap the current frame for a copy (we do the swapping to get |
| 83 | // the off-frame registers off the fall through) to use for the |
| 84 | // branch. |
| 85 | VirtualFrame* fall_through_frame = cgen()->frame(); |
| 86 | VirtualFrame* branch_frame = new VirtualFrame(fall_through_frame); |
| 87 | RegisterFile non_frame_registers; |
| 88 | cgen()->SetFrame(branch_frame, &non_frame_registers); |
| 89 | |
| 90 | // Check if we can avoid merge code. |
| 91 | cgen()->frame()->PrepareMergeTo(entry_frame_); |
| 92 | if (cgen()->frame()->Equals(entry_frame_)) { |
| 93 | // Branch right in to the block. |
| 94 | cgen()->DeleteFrame(); |
| 95 | __ j(cc, &entry_label_); |
| 96 | cgen()->SetFrame(fall_through_frame, &non_frame_registers); |
| 97 | return; |
| 98 | } |
| 99 | |
| 100 | // Check if we can reuse existing merge code. |
| 101 | for (int i = 0; i < reaching_frames_.length(); i++) { |
| 102 | if (reaching_frames_[i] != NULL && |
| 103 | cgen()->frame()->Equals(reaching_frames_[i])) { |
| 104 | // Branch to the merge code. |
| 105 | cgen()->DeleteFrame(); |
| 106 | __ j(cc, &merge_labels_[i]); |
| 107 | cgen()->SetFrame(fall_through_frame, &non_frame_registers); |
| 108 | return; |
| 109 | } |
| 110 | } |
| 111 | |
| 112 | // To emit the merge code here, we negate the condition and branch |
| 113 | // around the merge code on the fall through path. |
| 114 | Label original_fall_through; |
| 115 | __ j(NegateCondition(cc), &original_fall_through); |
| 116 | cgen()->frame()->MergeTo(entry_frame_); |
| 117 | cgen()->DeleteFrame(); |
| 118 | __ jmp(&entry_label_); |
| 119 | cgen()->SetFrame(fall_through_frame, &non_frame_registers); |
| 120 | __ bind(&original_fall_through); |
| 121 | |
| 122 | } else if (entry_frame_ != NULL) { |
| 123 | // Forward branch with a preconfigured entry frame. Assert the |
| 124 | // current frame matches the expected one and branch to the block. |
| 125 | ASSERT(cgen()->frame()->Equals(entry_frame_)); |
| 126 | // Explicitly use the macro assembler instead of __ as forward |
| 127 | // branches are expected to be a fixed size (no inserted |
| 128 | // coverage-checking instructions please). This is used in |
| 129 | // Reference::GetValue. |
| 130 | cgen()->masm()->j(cc, &entry_label_); |
| 131 | |
| 132 | } else { |
| 133 | // Forward branch. A copy of the current frame is remembered and |
| 134 | // a branch to the merge code is emitted. Explicitly use the |
| 135 | // macro assembler instead of __ as forward branches are expected |
| 136 | // to be a fixed size (no inserted coverage-checking instructions |
| 137 | // please). This is used in Reference::GetValue. |
| 138 | AddReachingFrame(new VirtualFrame(cgen()->frame())); |
| 139 | cgen()->masm()->j(cc, &merge_labels_.last()); |
| 140 | } |
| 141 | } |
| 142 | |
| 143 | |
| 144 | void JumpTarget::Call() { |
| 145 | // Call is used to push the address of the catch block on the stack as |
| 146 | // a return address when compiling try/catch and try/finally. We |
| 147 | // fully spill the frame before making the call. The expected frame |
| 148 | // at the label (which should be the only one) is the spilled current |
| 149 | // frame plus an in-memory return address. The "fall-through" frame |
| 150 | // at the return site is the spilled current frame. |
| 151 | ASSERT(cgen() != NULL); |
| 152 | ASSERT(cgen()->has_valid_frame()); |
| 153 | // There are no non-frame references across the call. |
| 154 | ASSERT(cgen()->HasValidEntryRegisters()); |
| 155 | ASSERT(!is_linked()); |
| 156 | |
| 157 | cgen()->frame()->SpillAll(); |
| 158 | VirtualFrame* target_frame = new VirtualFrame(cgen()->frame()); |
| 159 | target_frame->Adjust(1); |
| 160 | // We do not expect a call with a preconfigured entry frame. |
| 161 | ASSERT(entry_frame_ == NULL); |
| 162 | AddReachingFrame(target_frame); |
| 163 | __ call(&merge_labels_.last()); |
| 164 | } |
| 165 | |
| 166 | |
| 167 | void JumpTarget::DoBind() { |
| 168 | ASSERT(cgen() != NULL); |
| 169 | ASSERT(!is_bound()); |
| 170 | |
| 171 | // Live non-frame registers are not allowed at the start of a basic |
| 172 | // block. |
| 173 | ASSERT(!cgen()->has_valid_frame() || cgen()->HasValidEntryRegisters()); |
| 174 | |
| 175 | // Fast case: the jump target was manually configured with an entry |
| 176 | // frame to use. |
| 177 | if (entry_frame_ != NULL) { |
| 178 | // Assert no reaching frames to deal with. |
| 179 | ASSERT(reaching_frames_.is_empty()); |
| 180 | ASSERT(!cgen()->has_valid_frame()); |
| 181 | |
| 182 | RegisterFile empty; |
| 183 | if (direction_ == BIDIRECTIONAL) { |
| 184 | // Copy the entry frame so the original can be used for a |
| 185 | // possible backward jump. |
| 186 | cgen()->SetFrame(new VirtualFrame(entry_frame_), &empty); |
| 187 | } else { |
| 188 | // Take ownership of the entry frame. |
| 189 | cgen()->SetFrame(entry_frame_, &empty); |
| 190 | entry_frame_ = NULL; |
| 191 | } |
| 192 | __ bind(&entry_label_); |
| 193 | return; |
| 194 | } |
| 195 | |
| 196 | if (!is_linked()) { |
| 197 | ASSERT(cgen()->has_valid_frame()); |
| 198 | if (direction_ == FORWARD_ONLY) { |
| 199 | // Fast case: no forward jumps and no possible backward jumps. |
| 200 | // The stack pointer can be floating above the top of the |
| 201 | // virtual frame before the bind. Afterward, it should not. |
| 202 | VirtualFrame* frame = cgen()->frame(); |
| 203 | int difference = frame->stack_pointer_ - (frame->element_count() - 1); |
| 204 | if (difference > 0) { |
| 205 | frame->stack_pointer_ -= difference; |
| 206 | __ addq(rsp, Immediate(difference * kPointerSize)); |
| 207 | } |
| 208 | } else { |
| 209 | ASSERT(direction_ == BIDIRECTIONAL); |
| 210 | // Fast case: no forward jumps, possible backward ones. Remove |
| 211 | // constants and copies above the watermark on the fall-through |
| 212 | // frame and use it as the entry frame. |
| 213 | cgen()->frame()->MakeMergable(); |
| 214 | entry_frame_ = new VirtualFrame(cgen()->frame()); |
| 215 | } |
| 216 | __ bind(&entry_label_); |
| 217 | return; |
| 218 | } |
| 219 | |
| 220 | if (direction_ == FORWARD_ONLY && |
| 221 | !cgen()->has_valid_frame() && |
| 222 | reaching_frames_.length() == 1) { |
| 223 | // Fast case: no fall-through, a single forward jump, and no |
| 224 | // possible backward jumps. Pick up the only reaching frame, take |
| 225 | // ownership of it, and use it for the block about to be emitted. |
| 226 | VirtualFrame* frame = reaching_frames_[0]; |
| 227 | RegisterFile empty; |
| 228 | cgen()->SetFrame(frame, &empty); |
| 229 | reaching_frames_[0] = NULL; |
| 230 | __ bind(&merge_labels_[0]); |
| 231 | |
| 232 | // The stack pointer can be floating above the top of the |
| 233 | // virtual frame before the bind. Afterward, it should not. |
| 234 | int difference = frame->stack_pointer_ - (frame->element_count() - 1); |
| 235 | if (difference > 0) { |
| 236 | frame->stack_pointer_ -= difference; |
| 237 | __ addq(rsp, Immediate(difference * kPointerSize)); |
| 238 | } |
| 239 | |
| 240 | __ bind(&entry_label_); |
| 241 | return; |
| 242 | } |
| 243 | |
| 244 | // If there is a current frame, record it as the fall-through. It |
| 245 | // is owned by the reaching frames for now. |
| 246 | bool had_fall_through = false; |
| 247 | if (cgen()->has_valid_frame()) { |
| 248 | had_fall_through = true; |
| 249 | AddReachingFrame(cgen()->frame()); // Return value ignored. |
| 250 | RegisterFile empty; |
| 251 | cgen()->SetFrame(NULL, &empty); |
| 252 | } |
| 253 | |
| 254 | // Compute the frame to use for entry to the block. |
| 255 | ComputeEntryFrame(); |
| 256 | |
| 257 | // Some moves required to merge to an expected frame require purely |
| 258 | // frame state changes, and do not require any code generation. |
| 259 | // Perform those first to increase the possibility of finding equal |
| 260 | // frames below. |
| 261 | for (int i = 0; i < reaching_frames_.length(); i++) { |
| 262 | if (reaching_frames_[i] != NULL) { |
| 263 | reaching_frames_[i]->PrepareMergeTo(entry_frame_); |
| 264 | } |
| 265 | } |
| 266 | |
| 267 | if (is_linked()) { |
| 268 | // There were forward jumps. Handle merging the reaching frames |
| 269 | // to the entry frame. |
| 270 | |
| 271 | // Loop over the (non-null) reaching frames and process any that |
| 272 | // need merge code. Iterate backwards through the list to handle |
| 273 | // the fall-through frame first. Set frames that will be |
| 274 | // processed after 'i' to NULL if we want to avoid processing |
| 275 | // them. |
| 276 | for (int i = reaching_frames_.length() - 1; i >= 0; i--) { |
| 277 | VirtualFrame* frame = reaching_frames_[i]; |
| 278 | |
| 279 | if (frame != NULL) { |
| 280 | // Does the frame (probably) need merge code? |
| 281 | if (!frame->Equals(entry_frame_)) { |
| 282 | // We could have a valid frame as the fall through to the |
| 283 | // binding site or as the fall through from a previous merge |
| 284 | // code block. Jump around the code we are about to |
| 285 | // generate. |
| 286 | if (cgen()->has_valid_frame()) { |
| 287 | cgen()->DeleteFrame(); |
| 288 | __ jmp(&entry_label_); |
| 289 | } |
| 290 | // Pick up the frame for this block. Assume ownership if |
| 291 | // there cannot be backward jumps. |
| 292 | RegisterFile empty; |
| 293 | if (direction_ == BIDIRECTIONAL) { |
| 294 | cgen()->SetFrame(new VirtualFrame(frame), &empty); |
| 295 | } else { |
| 296 | cgen()->SetFrame(frame, &empty); |
| 297 | reaching_frames_[i] = NULL; |
| 298 | } |
| 299 | __ bind(&merge_labels_[i]); |
| 300 | |
| 301 | // Loop over the remaining (non-null) reaching frames, |
| 302 | // looking for any that can share merge code with this one. |
| 303 | for (int j = 0; j < i; j++) { |
| 304 | VirtualFrame* other = reaching_frames_[j]; |
| 305 | if (other != NULL && other->Equals(cgen()->frame())) { |
| 306 | // Set the reaching frame element to null to avoid |
| 307 | // processing it later, and then bind its entry label. |
| 308 | reaching_frames_[j] = NULL; |
| 309 | __ bind(&merge_labels_[j]); |
| 310 | } |
| 311 | } |
| 312 | |
| 313 | // Emit the merge code. |
| 314 | cgen()->frame()->MergeTo(entry_frame_); |
| 315 | } else if (i == reaching_frames_.length() - 1 && had_fall_through) { |
| 316 | // If this is the fall through frame, and it didn't need |
| 317 | // merge code, we need to pick up the frame so we can jump |
| 318 | // around subsequent merge blocks if necessary. |
| 319 | RegisterFile empty; |
| 320 | cgen()->SetFrame(frame, &empty); |
| 321 | reaching_frames_[i] = NULL; |
| 322 | } |
| 323 | } |
| 324 | } |
| 325 | |
| 326 | // The code generator may not have a current frame if there was no |
| 327 | // fall through and none of the reaching frames needed merging. |
| 328 | // In that case, clone the entry frame as the current frame. |
| 329 | if (!cgen()->has_valid_frame()) { |
| 330 | RegisterFile empty; |
| 331 | cgen()->SetFrame(new VirtualFrame(entry_frame_), &empty); |
| 332 | } |
| 333 | |
| 334 | // There may be unprocessed reaching frames that did not need |
| 335 | // merge code. They will have unbound merge labels. Bind their |
| 336 | // merge labels to be the same as the entry label and deallocate |
| 337 | // them. |
| 338 | for (int i = 0; i < reaching_frames_.length(); i++) { |
| 339 | if (!merge_labels_[i].is_bound()) { |
| 340 | reaching_frames_[i] = NULL; |
| 341 | __ bind(&merge_labels_[i]); |
| 342 | } |
| 343 | } |
| 344 | |
| 345 | // There are non-NULL reaching frames with bound labels for each |
| 346 | // merge block, but only on backward targets. |
| 347 | } else { |
| 348 | // There were no forward jumps. There must be a current frame and |
| 349 | // this must be a bidirectional target. |
| 350 | ASSERT(reaching_frames_.length() == 1); |
| 351 | ASSERT(reaching_frames_[0] != NULL); |
| 352 | ASSERT(direction_ == BIDIRECTIONAL); |
| 353 | |
| 354 | // Use a copy of the reaching frame so the original can be saved |
| 355 | // for possible reuse as a backward merge block. |
| 356 | RegisterFile empty; |
| 357 | cgen()->SetFrame(new VirtualFrame(reaching_frames_[0]), &empty); |
| 358 | __ bind(&merge_labels_[0]); |
| 359 | cgen()->frame()->MergeTo(entry_frame_); |
| 360 | } |
| 361 | |
| 362 | __ bind(&entry_label_); |
| 363 | } |
| 364 | |
christian.plesner.hansen@gmail.com | 5a6af92 | 2009-08-12 14:20:51 +0000 | [diff] [blame] | 365 | |
| 366 | void BreakTarget::Jump() { |
| 367 | // Drop leftover statement state from the frame before merging, without |
| 368 | // emitting code. |
| 369 | ASSERT(cgen()->has_valid_frame()); |
| 370 | int count = cgen()->frame()->height() - expected_height_; |
| 371 | cgen()->frame()->ForgetElements(count); |
| 372 | DoJump(); |
| 373 | } |
| 374 | |
| 375 | |
| 376 | void BreakTarget::Jump(Result* arg) { |
| 377 | // Drop leftover statement state from the frame before merging, without |
| 378 | // emitting code. |
| 379 | ASSERT(cgen()->has_valid_frame()); |
| 380 | int count = cgen()->frame()->height() - expected_height_; |
| 381 | cgen()->frame()->ForgetElements(count); |
| 382 | cgen()->frame()->Push(arg); |
| 383 | DoJump(); |
| 384 | } |
| 385 | |
| 386 | |
| 387 | void BreakTarget::Bind() { |
| 388 | #ifdef DEBUG |
| 389 | // All the forward-reaching frames should have been adjusted at the |
| 390 | // jumps to this target. |
| 391 | for (int i = 0; i < reaching_frames_.length(); i++) { |
| 392 | ASSERT(reaching_frames_[i] == NULL || |
| 393 | reaching_frames_[i]->height() == expected_height_); |
| 394 | } |
| 395 | #endif |
| 396 | // Drop leftover statement state from the frame before merging, even on |
| 397 | // the fall through. This is so we can bind the return target with state |
| 398 | // on the frame. |
| 399 | if (cgen()->has_valid_frame()) { |
| 400 | int count = cgen()->frame()->height() - expected_height_; |
| 401 | cgen()->frame()->ForgetElements(count); |
| 402 | } |
| 403 | DoBind(); |
| 404 | } |
| 405 | |
| 406 | |
| 407 | void BreakTarget::Bind(Result* arg) { |
| 408 | #ifdef DEBUG |
| 409 | // All the forward-reaching frames should have been adjusted at the |
| 410 | // jumps to this target. |
| 411 | for (int i = 0; i < reaching_frames_.length(); i++) { |
| 412 | ASSERT(reaching_frames_[i] == NULL || |
| 413 | reaching_frames_[i]->height() == expected_height_ + 1); |
| 414 | } |
| 415 | #endif |
| 416 | // Drop leftover statement state from the frame before merging, even on |
| 417 | // the fall through. This is so we can bind the return target with state |
| 418 | // on the frame. |
| 419 | if (cgen()->has_valid_frame()) { |
| 420 | int count = cgen()->frame()->height() - expected_height_; |
| 421 | cgen()->frame()->ForgetElements(count); |
| 422 | cgen()->frame()->Push(arg); |
| 423 | } |
| 424 | DoBind(); |
| 425 | *arg = cgen()->frame()->Pop(); |
| 426 | } |
| 427 | |
| 428 | |
ager@chromium.org | 5aa501c | 2009-06-23 07:57:28 +0000 | [diff] [blame] | 429 | #undef __ |
| 430 | |
| 431 | |
| 432 | } } // namespace v8::internal |