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 "jump-target-inl.h" 32 #include "register-allocator-inl.h" 33 34 namespace v8 { 35 namespace internal { 36 37 // ------------------------------------------------------------------------- 38 // JumpTarget implementation. 39 40 bool JumpTarget::compiling_deferred_code_ = false; 41 42 43 void JumpTarget::Unuse() { 44 reaching_frames_.Clear(); 45 merge_labels_.Clear(); 46 entry_frame_ = NULL; 47 entry_label_.Unuse(); 48 } 49 50 51 void JumpTarget::ComputeEntryFrame() { 52 // Given: a collection of frames reaching by forward CFG edges and 53 // the directionality of the block. Compute: an entry frame for the 54 // block. 55 56 Counters::compute_entry_frame.Increment(); 57 #ifdef DEBUG 58 if (compiling_deferred_code_) { 59 ASSERT(reaching_frames_.length() > 1); 60 VirtualFrame* frame = reaching_frames_[0]; 61 bool all_identical = true; 62 for (int i = 1; i < reaching_frames_.length(); i++) { 63 if (!frame->Equals(reaching_frames_[i])) { 64 all_identical = false; 65 break; 66 } 67 } 68 ASSERT(!all_identical || all_identical); 69 } 70 #endif 71 72 // Choose an initial frame. 73 VirtualFrame* initial_frame = reaching_frames_[0]; 74 75 // A list of pointers to frame elements in the entry frame. NULL 76 // indicates that the element has not yet been determined. 77 int length = initial_frame->element_count(); 78 ZoneList<FrameElement*> elements(length); 79 80 // Initially populate the list of elements based on the initial 81 // frame. 82 for (int i = 0; i < length; i++) { 83 FrameElement element = initial_frame->elements_[i]; 84 // We do not allow copies or constants in bidirectional frames. 85 if (direction_ == BIDIRECTIONAL) { 86 if (element.is_constant() || element.is_copy()) { 87 elements.Add(NULL); 88 continue; 89 } 90 } 91 elements.Add(&initial_frame->elements_[i]); 92 } 93 94 // Compute elements based on the other reaching frames. 95 if (reaching_frames_.length() > 1) { 96 for (int i = 0; i < length; i++) { 97 FrameElement* element = elements[i]; 98 for (int j = 1; j < reaching_frames_.length(); j++) { 99 // Element computation is monotonic: new information will not 100 // change our decision about undetermined or invalid elements. 101 if (element == NULL || !element->is_valid()) break; 102 103 element = element->Combine(&reaching_frames_[j]->elements_[i]); 104 105 FrameElement* other = &reaching_frames_[j]->elements_[i]; 106 if (element != NULL && !element->is_copy()) { 107 ASSERT(other != NULL); 108 // We overwrite the number information of one of the incoming frames. 109 // This is safe because we only use the frame for emitting merge code. 110 // The number information of incoming frames is not used anymore. 111 element->set_number_info(NumberInfo::Combine(element->number_info(), 112 other->number_info())); 113 } 114 } 115 elements[i] = element; 116 } 117 } 118 119 // Build the new frame. A freshly allocated frame has memory elements 120 // for the parameters and some platform-dependent elements (e.g., 121 // return address). Replace those first. 122 entry_frame_ = new VirtualFrame(); 123 int index = 0; 124 for (; index < entry_frame_->element_count(); index++) { 125 FrameElement* target = elements[index]; 126 // If the element is determined, set it now. Count registers. Mark 127 // elements as copied exactly when they have a copy. Undetermined 128 // elements are initially recorded as if in memory. 129 if (target != NULL) { 130 entry_frame_->elements_[index] = *target; 131 InitializeEntryElement(index, target); 132 } 133 } 134 // Then fill in the rest of the frame with new elements. 135 for (; index < length; index++) { 136 FrameElement* target = elements[index]; 137 if (target == NULL) { 138 entry_frame_->elements_.Add( 139 FrameElement::MemoryElement(NumberInfo::kUninitialized)); 140 } else { 141 entry_frame_->elements_.Add(*target); 142 InitializeEntryElement(index, target); 143 } 144 } 145 146 // Allocate any still-undetermined frame elements to registers or 147 // memory, from the top down. 148 for (int i = length - 1; i >= 0; i--) { 149 if (elements[i] == NULL) { 150 // Loop over all the reaching frames to check whether the element 151 // is synced on all frames and to count the registers it occupies. 152 bool is_synced = true; 153 RegisterFile candidate_registers; 154 int best_count = kMinInt; 155 int best_reg_num = RegisterAllocator::kInvalidRegister; 156 NumberInfo::Type info = NumberInfo::kUninitialized; 157 158 for (int j = 0; j < reaching_frames_.length(); j++) { 159 FrameElement element = reaching_frames_[j]->elements_[i]; 160 if (direction_ == BIDIRECTIONAL) { 161 info = NumberInfo::kUnknown; 162 } else if (!element.is_copy()) { 163 info = NumberInfo::Combine(info, element.number_info()); 164 } else { 165 // New elements will not be copies, so get number information from 166 // backing element in the reaching frame. 167 info = NumberInfo::Combine(info, 168 reaching_frames_[j]->elements_[element.index()].number_info()); 169 } 170 is_synced = is_synced && element.is_synced(); 171 if (element.is_register() && !entry_frame_->is_used(element.reg())) { 172 // Count the register occurrence and remember it if better 173 // than the previous best. 174 int num = RegisterAllocator::ToNumber(element.reg()); 175 candidate_registers.Use(num); 176 if (candidate_registers.count(num) > best_count) { 177 best_count = candidate_registers.count(num); 178 best_reg_num = num; 179 } 180 } 181 } 182 183 // We must have a number type information now (not for copied elements). 184 ASSERT(entry_frame_->elements_[i].is_copy() 185 || info != NumberInfo::kUninitialized); 186 187 // If the value is synced on all frames, put it in memory. This 188 // costs nothing at the merge code but will incur a 189 // memory-to-register move when the value is needed later. 190 if (is_synced) { 191 // Already recorded as a memory element. 192 // Set combined number info. 193 entry_frame_->elements_[i].set_number_info(info); 194 continue; 195 } 196 197 // Try to put it in a register. If there was no best choice 198 // consider any free register. 199 if (best_reg_num == RegisterAllocator::kInvalidRegister) { 200 for (int j = 0; j < RegisterAllocator::kNumRegisters; j++) { 201 if (!entry_frame_->is_used(j)) { 202 best_reg_num = j; 203 break; 204 } 205 } 206 } 207 208 if (best_reg_num != RegisterAllocator::kInvalidRegister) { 209 // If there was a register choice, use it. Preserve the copied 210 // flag on the element. 211 bool is_copied = entry_frame_->elements_[i].is_copied(); 212 Register reg = RegisterAllocator::ToRegister(best_reg_num); 213 entry_frame_->elements_[i] = 214 FrameElement::RegisterElement(reg, FrameElement::NOT_SYNCED, 215 NumberInfo::kUninitialized); 216 if (is_copied) entry_frame_->elements_[i].set_copied(); 217 entry_frame_->set_register_location(reg, i); 218 } 219 // Set combined number info. 220 entry_frame_->elements_[i].set_number_info(info); 221 } 222 } 223 224 // If we have incoming backward edges assert we forget all number information. 225 #ifdef DEBUG 226 if (direction_ == BIDIRECTIONAL) { 227 for (int i = 0; i < length; ++i) { 228 if (!entry_frame_->elements_[i].is_copy()) { 229 ASSERT(entry_frame_->elements_[i].number_info() == 230 NumberInfo::kUnknown); 231 } 232 } 233 } 234 #endif 235 236 // The stack pointer is at the highest synced element or the base of 237 // the expression stack. 238 int stack_pointer = length - 1; 239 while (stack_pointer >= entry_frame_->expression_base_index() && 240 !entry_frame_->elements_[stack_pointer].is_synced()) { 241 stack_pointer--; 242 } 243 entry_frame_->stack_pointer_ = stack_pointer; 244 } 245 246 247 void JumpTarget::Jump() { 248 DoJump(); 249 } 250 251 252 void JumpTarget::Jump(Result* arg) { 253 ASSERT(cgen()->has_valid_frame()); 254 255 cgen()->frame()->Push(arg); 256 DoJump(); 257 } 258 259 260 void JumpTarget::Branch(Condition cc, Hint hint) { 261 DoBranch(cc, hint); 262 } 263 264 265 #ifdef DEBUG 266 #define DECLARE_ARGCHECK_VARS(name) \ 267 Result::Type name##_type = name->type(); \ 268 Register name##_reg = name->is_register() ? name->reg() : no_reg 269 270 #define ASSERT_ARGCHECK(name) \ 271 ASSERT(name->type() == name##_type); \ 272 ASSERT(!name->is_register() || name->reg().is(name##_reg)) 273 274 #else 275 #define DECLARE_ARGCHECK_VARS(name) do {} while (false) 276 277 #define ASSERT_ARGCHECK(name) do {} while (false) 278 #endif 279 280 void JumpTarget::Branch(Condition cc, Result* arg, Hint hint) { 281 ASSERT(cgen()->has_valid_frame()); 282 283 // We want to check that non-frame registers at the call site stay in 284 // the same registers on the fall-through branch. 285 DECLARE_ARGCHECK_VARS(arg); 286 287 cgen()->frame()->Push(arg); 288 DoBranch(cc, hint); 289 *arg = cgen()->frame()->Pop(); 290 291 ASSERT_ARGCHECK(arg); 292 } 293 294 295 void BreakTarget::Branch(Condition cc, Result* arg, Hint hint) { 296 ASSERT(cgen()->has_valid_frame()); 297 298 int count = cgen()->frame()->height() - expected_height_; 299 if (count > 0) { 300 // We negate and branch here rather than using DoBranch's negate 301 // and branch. This gives us a hook to remove statement state 302 // from the frame. 303 JumpTarget fall_through; 304 // Branch to fall through will not negate, because it is a 305 // forward-only target. 306 fall_through.Branch(NegateCondition(cc), NegateHint(hint)); 307 Jump(arg); // May emit merge code here. 308 fall_through.Bind(); 309 } else { 310 DECLARE_ARGCHECK_VARS(arg); 311 cgen()->frame()->Push(arg); 312 DoBranch(cc, hint); 313 *arg = cgen()->frame()->Pop(); 314 ASSERT_ARGCHECK(arg); 315 } 316 } 317 318 #undef DECLARE_ARGCHECK_VARS 319 #undef ASSERT_ARGCHECK 320 321 322 void JumpTarget::Bind() { 323 DoBind(); 324 } 325 326 327 void JumpTarget::Bind(Result* arg) { 328 if (cgen()->has_valid_frame()) { 329 cgen()->frame()->Push(arg); 330 } 331 DoBind(); 332 *arg = cgen()->frame()->Pop(); 333 } 334 335 336 void JumpTarget::AddReachingFrame(VirtualFrame* frame) { 337 ASSERT(reaching_frames_.length() == merge_labels_.length()); 338 ASSERT(entry_frame_ == NULL); 339 Label fresh; 340 merge_labels_.Add(fresh); 341 reaching_frames_.Add(frame); 342 } 343 344 345 // ------------------------------------------------------------------------- 346 // BreakTarget implementation. 347 348 void BreakTarget::set_direction(Directionality direction) { 349 JumpTarget::set_direction(direction); 350 ASSERT(cgen()->has_valid_frame()); 351 expected_height_ = cgen()->frame()->height(); 352 } 353 354 355 void BreakTarget::CopyTo(BreakTarget* destination) { 356 ASSERT(destination != NULL); 357 destination->direction_ = direction_; 358 destination->reaching_frames_.Rewind(0); 359 destination->reaching_frames_.AddAll(reaching_frames_); 360 destination->merge_labels_.Rewind(0); 361 destination->merge_labels_.AddAll(merge_labels_); 362 destination->entry_frame_ = entry_frame_; 363 destination->entry_label_ = entry_label_; 364 destination->expected_height_ = expected_height_; 365 } 366 367 368 void BreakTarget::Branch(Condition cc, Hint hint) { 369 ASSERT(cgen()->has_valid_frame()); 370 371 int count = cgen()->frame()->height() - expected_height_; 372 if (count > 0) { 373 // We negate and branch here rather than using DoBranch's negate 374 // and branch. This gives us a hook to remove statement state 375 // from the frame. 376 JumpTarget fall_through; 377 // Branch to fall through will not negate, because it is a 378 // forward-only target. 379 fall_through.Branch(NegateCondition(cc), NegateHint(hint)); 380 Jump(); // May emit merge code here. 381 fall_through.Bind(); 382 } else { 383 DoBranch(cc, hint); 384 } 385 } 386 387 388 // ------------------------------------------------------------------------- 389 // ShadowTarget implementation. 390 391 ShadowTarget::ShadowTarget(BreakTarget* shadowed) { 392 ASSERT(shadowed != NULL); 393 other_target_ = shadowed; 394 395 #ifdef DEBUG 396 is_shadowing_ = true; 397 #endif 398 // While shadowing this shadow target saves the state of the original. 399 shadowed->CopyTo(this); 400 401 // The original's state is reset. 402 shadowed->Unuse(); 403 ASSERT(cgen()->has_valid_frame()); 404 shadowed->set_expected_height(cgen()->frame()->height()); 405 } 406 407 408 void ShadowTarget::StopShadowing() { 409 ASSERT(is_shadowing_); 410 411 // The states of this target, which was shadowed, and the original 412 // target, which was shadowing, are swapped. 413 BreakTarget temp; 414 other_target_->CopyTo(&temp); 415 CopyTo(other_target_); 416 temp.CopyTo(this); 417 temp.Unuse(); 418 419 #ifdef DEBUG 420 is_shadowing_ = false; 421 #endif 422 } 423 424 425 } } // namespace v8::internal 426