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

src/jump-target-ia32.cc

Index: src/jump-target-ia32.cc
===================================================================
--- src/jump-target-ia32.cc	(revision 1495)
+++ src/jump-target-ia32.cc	(working copy)
@@ -70,40 +70,58 @@
   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();
+      __ j(cc, &entry_label_, hint);
+      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();
+        __ j(cc, &merge_labels_[i], hint);
+        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;
     __ j(NegateCondition(cc), &original_fall_through, NegateHint(hint));
-    // 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);
-
-    working_frame->MergeTo(entry_frame_);
+    cgen_->frame()->MergeTo(entry_frame_);
     cgen_->DeleteFrame();
     __ jmp(&entry_label_);
+    cgen_->SetFrame(fall_through_frame, &non_frame_registers);
+    __ bind(&original_fall_through);
 
-    // 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()));
     __ j(cc, &merge_labels_.last(), hint);
+    is_linked_ = true;
   }
-
-  is_linked_ = !is_bound_;
 }
 
 
@@ -138,79 +156,130 @@
   // 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(Operand(esp), Immediate(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(Operand(esp), Immediate(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);
 
-  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++) {
+  // 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 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];
-          reaching_frames_[i] = NULL;
-          __ bind(&merge_labels_[i]);
-        }
-      }
+  if (is_linked()) {
+    // There were forward jumps.  Handle merging the reaching frames
+    // to the entry frame.
 
-      // 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++) {
+    // 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 (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_);
-        }
+      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();
+            __ jmp(&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]);
 
-        // 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 = 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]);
+            }
+          }
 
-        // 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_);
+        } else if (i == reaching_frames_.length() - 1 && had_fall_through) {
+          // If this is the fall through frame, 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;
         }
-
-        // Emit the merge code.
-        cgen_->frame()->MergeTo(entry_frame_);
       }
     }
 
@@ -227,23 +296,31 @@
     __ 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_);
   }