Change the way we handle backward jumps in the code generator. Keep...

src/jump-target-arm.cc

 // Copyright 2008 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
@@ skipping 52 matching lines @@
 
   is_linked_ = !is_bound_;
 }
 
 
 void JumpTarget::Branch(Condition cc, Hint ignored) {
   ASSERT(cgen_ != NULL);
   ASSERT(cgen_->has_valid_frame());
 
   if (is_bound()) {
+    ASSERT(direction_ == BIDIRECTIONAL);
     // Backward branch.  We have an expected frame to merge to on the
-    // backward edge.  We negate the condition and emit the merge code
-    // here.
-    //
-    // TODO(210): we should try to avoid negating the condition in the
-    // case where there is no merge code to emit.  Otherwise, we emit
-    // a branch around an unconditional jump.
-    ASSERT(direction_ == BIDIRECTIONAL);
+    // backward edge.
+
+    // Swap the current frame for a copy (we do the swapping to get
+    // the off-frame registers off the fall through) to use for the
+    // branch.
+    VirtualFrame* fall_through_frame = cgen_->frame();
+    VirtualFrame* branch_frame = new VirtualFrame(fall_through_frame);
+    RegisterFile non_frame_registers = RegisterAllocator::Reserved();
+    cgen_->SetFrame(branch_frame, &non_frame_registers);
+
+    // Check if we can avoid merge code.
+    cgen_->frame()->PrepareMergeTo(entry_frame_);
+    if (cgen_->frame()->Equals(entry_frame_)) {
+      // Branch right in to the block.
+      cgen_->DeleteFrame();
+      __ b(cc, &entry_label_);
+      cgen_->SetFrame(fall_through_frame, &non_frame_registers);
+      return;
+    }
+
+    // Check if we can reuse existing merge code.
+    for (int i = 0; i < reaching_frames_.length(); i++) {
+      if (reaching_frames_[i] != NULL &&
+          cgen_->frame()->Equals(reaching_frames_[i])) {
+        // Branch to the merge code.
+        cgen_->DeleteFrame();
+        __ b(cc, &merge_labels_[i]);
+        cgen_->SetFrame(fall_through_frame, &non_frame_registers);
+        return;
+      }
+    }
+
+    // To emit the merge code here, we negate the condition and branch
+    // around the merge code on the fall through path.
     Label original_fall_through;
     __ b(NegateCondition(cc), &original_fall_through);
-    // Swap the current frame for a copy of it, saving non-frame
-    // register reference counts and invalidating all non-frame register
-    // references except the reserved ones on the backward edge.
-    VirtualFrame* original_frame = cgen_->frame();
-    VirtualFrame* working_frame = new VirtualFrame(original_frame);
-    RegisterFile non_frame_registers = RegisterAllocator::Reserved();
-    cgen_->SetFrame(working_frame, &non_frame_registers);
+    cgen_->frame()->MergeTo(entry_frame_);
+    cgen_->DeleteFrame();
+    __ b(&entry_label_);
+    cgen_->SetFrame(fall_through_frame, &non_frame_registers);
+    __ bind(&original_fall_through);
 
-    working_frame->MergeTo(entry_frame_);
-    cgen_->DeleteFrame();
-    __ jmp(&entry_label_);
-
-    // Restore the frame and its associated non-frame registers.
-    cgen_->SetFrame(original_frame, &non_frame_registers);
-    __ bind(&original_fall_through);
   } else {
     // Forward branch.  A copy of the current frame is added to the end
     // of the list of frames reaching the target block and a branch to
     // the merge code is emitted.
     AddReachingFrame(new VirtualFrame(cgen_->frame()));
     __ b(cc, &merge_labels_.last());
+    is_linked_ = true;
   }
-
-  is_linked_ = !is_bound_;
 }
 
 
 void JumpTarget::Call() {
   // Call is used to push the address of the catch block on the stack as
   // a return address when compiling try/catch and try/finally.  We
   // fully spill the frame before making the call.  The expected frame
   // at the label (which should be the only one) is the spilled current
   // frame plus an in-memory return address.  The "fall-through" frame
   // at the return site is the spilled current frame.
@@ skipping 14 matching lines @@
 
 
 void JumpTarget::Bind(int mergable_elements) {
   ASSERT(cgen_ != NULL);
   ASSERT(!is_bound());
 
   // Live non-frame registers are not allowed at the start of a basic
   // block.
   ASSERT(!cgen_->has_valid_frame() || cgen_->HasValidEntryRegisters());
 
+  if (direction_ == FORWARD_ONLY) {
+    // A simple case: no forward jumps and no possible backward jumps.
+    if (!is_linked()) {
+      // The stack pointer can be floating above the top of the
+      // virtual frame before the bind.  Afterward, it should not.
+      ASSERT(cgen_->has_valid_frame());
+      VirtualFrame* frame = cgen_->frame();
+      int difference =
+          frame->stack_pointer_ - (frame->elements_.length() - 1);
+      if (difference > 0) {
+        frame->stack_pointer_ -= difference;
+        __ add(sp, sp, Operand(difference * kPointerSize));
+      }
+
+      is_bound_ = true;
+      return;
+    }
+
+    // Another simple case: no fall through, a single forward jump,
+    // and no possible backward jumps.
+    if (!cgen_->has_valid_frame() && reaching_frames_.length() == 1) {
+      // Pick up the only reaching frame, take ownership of it, and
+      // use it for the block about to be emitted.
+      VirtualFrame* frame = reaching_frames_[0];
+      RegisterFile reserved = RegisterAllocator::Reserved();
+      cgen_->SetFrame(frame, &reserved);
+      reaching_frames_[0] = NULL;
+      __ bind(&merge_labels_[0]);
+
+      // The stack pointer can be floating above the top of the
+      // virtual frame before the bind.  Afterward, it should not.
+      int difference =
+          frame->stack_pointer_ - (frame->elements_.length() - 1);
+      if (difference > 0) {
+        frame->stack_pointer_ -= difference;
+        __ add(sp, sp, Operand(difference * kPointerSize));
+      }
+
+      is_linked_ = false;
+      is_bound_ = true;
+      return;
+    }
+  }
+
+  // If there is a current frame, record it as the fall-through.  It
+  // is owned by the reaching frames for now.
+  bool had_fall_through = false;
+  if (cgen_->has_valid_frame()) {
+    had_fall_through = true;
+    AddReachingFrame(cgen_->frame());
+    RegisterFile empty;
+    cgen_->SetFrame(NULL, &empty);
+  }
+
   // Compute the frame to use for entry to the block.
   ComputeEntryFrame(mergable_elements);
 
+  // Some moves required to merge to an expected frame require purely
+  // frame state changes, and do not require any code generation.
+  // Perform those first to increase the possibility of finding equal
+  // frames below.
+  for (int i = 0; i < reaching_frames_.length(); i++) {
+    if (reaching_frames_[i] != NULL) {
+      reaching_frames_[i]->PrepareMergeTo(entry_frame_);
+    }
+  }
+
   if (is_linked()) {
     // There were forward jumps.  Handle merging the reaching frames
     // and possible fall through to the entry frame.
 
-    // Some moves required to merge to an expected frame require
-    // purely frame state changes, and do not require any code
-    // generation.  Perform those first to increase the possibility of
-    // finding equal frames below.
-    if (cgen_->has_valid_frame()) {
-      cgen_->frame()->PrepareMergeTo(entry_frame_);
-    }
-    for (int i = 0; i < reaching_frames_.length(); i++) {
-      reaching_frames_[i]->PrepareMergeTo(entry_frame_);
-    }
+    // Loop over the (non-null) reaching frames and process any that
+    // need merge code.  Iterate backwards through the list to handle
+    // the fall-through frame first.  Set frames that will be
+    // processed after 'i' to NULL if we want to avoid processing
+    // them.
+    for (int i = reaching_frames_.length() - 1; i >= 0; i--) {
+      VirtualFrame* frame = reaching_frames_[i];
 
-    // If there is a fall through to the jump target and it needs
-    // merge code, process it first.
-    if (cgen_->has_valid_frame() && !cgen_->frame()->Equals(entry_frame_)) {
-      // Loop over all the reaching frames, looking for any that can
-      // share merge code with this one.
-      for (int i = 0; i < reaching_frames_.length(); i++) {
-        if (cgen_->frame()->Equals(reaching_frames_[i])) {
-          // Set the reaching frames element to null to avoid
-          // processing it later, and then bind its entry label.
-          delete reaching_frames_[i];
+      if (frame != NULL) {
+        // Does the frame (probably) need merge code?
+        if (!frame->Equals(entry_frame_)) {
+          // We could have a valid frame as the fall through to the
+          // binding site or as the fall through from a previous merge
+          // code block.  Jump around the code we are about to
+          // generate.
+          if (cgen_->has_valid_frame()) {
+            cgen_->DeleteFrame();
+            __ b(&entry_label_);
+          }
+          // Pick up the frame for this block.  Assume ownership if
+          // there cannot be backward jumps.
+          RegisterFile reserved = RegisterAllocator::Reserved();
+          if (direction_ == BIDIRECTIONAL) {
+            cgen_->SetFrame(new VirtualFrame(frame), &reserved);
+          } else {
+            cgen_->SetFrame(frame, &reserved);
+            reaching_frames_[i] = NULL;
+          }
+          __ bind(&merge_labels_[i]);
+
+          // Loop over the remaining (non-null) reaching frames,
+          // looking for any that can share merge code with this one.
+          for (int j = 0; j < i; j++) {
+            VirtualFrame* other = reaching_frames_[j];
+            if (other != NULL && other->Equals(cgen_->frame())) {
+              // Set the reaching frame element to null to avoid
+              // processing it later, and then bind its entry label.
+              delete other;
+              reaching_frames_[j] = NULL;
+              __ bind(&merge_labels_[j]);
+            }
+          }
+
+          // Emit the merge code.
+          cgen_->frame()->MergeTo(entry_frame_);
+        } else if (i == reaching_frames_.length() - 1 && had_fall_through) {
+          // If this is the fall through, and it didn't need merge
+          // code, we need to pick up the frame so we can jump around
+          // subsequent merge blocks if necessary.
+          RegisterFile reserved = RegisterAllocator::Reserved();
+          cgen_->SetFrame(frame, &reserved);
           reaching_frames_[i] = NULL;
-          __ bind(&merge_labels_[i]);
         }
       }
-
-      // Emit the merge code.
-      cgen_->frame()->MergeTo(entry_frame_);
-    }
-
-    // Loop over the (non-null) reaching frames and process any that
-    // need merge code.
-    for (int i = 0; i < reaching_frames_.length(); i++) {
-      VirtualFrame* frame = reaching_frames_[i];
-      if (frame != NULL && !frame->Equals(entry_frame_)) {
-        // Set the reaching frames element to null to avoid processing
-        // it later.  Do not delete it as it is needed for merging.
-        reaching_frames_[i] = NULL;
-
-        // If the code generator has a current frame (a fall-through
-        // or a previously merged frame), insert a jump around the
-        // merge code we are about to generate.
-        if (cgen_->has_valid_frame()) {
-          cgen_->DeleteFrame();
-          __ jmp(&entry_label_);
-        }
-
-        // Set the frame to merge as the code generator's current
-        // frame and bind its merge label.
-        RegisterFile reserved_registers = RegisterAllocator::Reserved();
-        cgen_->SetFrame(frame, &reserved_registers);
-        __ bind(&merge_labels_[i]);
-
-        // Loop over the remaining (non-null) reaching frames, looking
-        // for any that can share merge code with this one.
-        for (int j = i + 1; j < reaching_frames_.length(); j++) {
-          VirtualFrame* other = reaching_frames_[j];
-          if (other != NULL && frame->Equals(other)) {
-            delete other;
-            reaching_frames_[j] = NULL;
-            __ bind(&merge_labels_[j]);
-          }
-        }
-
-        // Emit the merge code.
-        cgen_->frame()->MergeTo(entry_frame_);
-      }
     }
 
     // The code generator may not have a current frame if there was no
     // fall through and none of the reaching frames needed merging.
     // In that case, clone the entry frame as the current frame.
     if (!cgen_->has_valid_frame()) {
       RegisterFile reserved_registers = RegisterAllocator::Reserved();
       cgen_->SetFrame(new VirtualFrame(entry_frame_), &reserved_registers);
     }
 
     // There is certainly a current frame equal to the entry frame.
     // Bind the entry frame label.
     __ bind(&entry_label_);
 
     // There may be unprocessed reaching frames that did not need
-    // merge code.  Bind their merge labels to be the same as the
-    // entry label.
+    // merge code.  They will have unbound merge labels.  Bind their
+    // merge labels to be the same as the entry label and deallocate
+    // them.
     for (int i = 0; i < reaching_frames_.length(); i++) {
-      if (reaching_frames_[i] != NULL) {
+      if (!merge_labels_[i].is_bound()) {
         delete reaching_frames_[i];
+        reaching_frames_[i] = NULL;
         __ bind(&merge_labels_[i]);
       }
     }
 
-    // All the reaching frames except the one that is the current
-    // frame (if it is one of the reaching frames) have been deleted.
-    reaching_frames_.Clear();
-    merge_labels_.Clear();
+    // There are non-NULL reaching frames with bound labels for each
+    // merge block, but only on backward targets.
+  } else {
+    // There were no forward jumps.  There must be a current frame and
+    // this must be a bidirectional target.
+    ASSERT(reaching_frames_.length() == 1);
+    ASSERT(reaching_frames_[0] != NULL);
+    ASSERT(direction_ == BIDIRECTIONAL);
 
-  } else {
-    // There were no forward jumps.  The current frame is merged to
-    // the entry frame.
+    // Use a copy of the reaching frame so the original can be saved
+    // for possible reuse as a backward merge block.
+    RegisterFile reserved = RegisterAllocator::Reserved();
+    cgen_->SetFrame(new VirtualFrame(reaching_frames_[0]), &reserved);
+    __ bind(&merge_labels_[0]);
     cgen_->frame()->MergeTo(entry_frame_);
     __ bind(&entry_label_);
   }
 
   is_linked_ = false;
   is_bound_ = true;
 }
 
 #undef __
 
 
 } }  // namespace v8::internal