Eliminate most of the jump target jumping, branching, and binding...

src/arm/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 29 matching lines @@
 #define __ ACCESS_MASM(cgen()->masm())
 
 void JumpTarget::DoJump() {
   ASSERT(cgen()->has_valid_frame());
   // Live non-frame registers are not allowed at unconditional jumps
   // because we have no way of invalidating the corresponding results
   // which are still live in the C++ code.
   ASSERT(cgen()->HasValidEntryRegisters());
 
   if (is_bound()) {
-    // Backward jump.  There is an expected frame to merge to.
+    // Backward jump.  There already a frame expectation at the target.
     ASSERT(direction_ == BIDIRECTIONAL);
-    cgen()->frame()->PrepareMergeTo(entry_frame_);
     cgen()->frame()->MergeTo(entry_frame_);
     cgen()->DeleteFrame();
-    __ jmp(&entry_label_);
   } else {
-    // Preconfigured entry frame is not used on ARM.
-    ASSERT(entry_frame_ == NULL);
-    // Forward jump.  The current frame is added to the end of the list
-    // of frames reaching the target block and a jump to the merge code
-    // is emitted.
-    AddReachingFrame(cgen()->frame());
-    RegisterFile empty;
-    cgen()->SetFrame(NULL, &empty);
-    __ jmp(&merge_labels_.last());
+    // Use the current frame as the expected one at the target if necessary.
+    if (entry_frame_ == NULL) {
+      entry_frame_ = cgen()->frame();
+      RegisterFile empty;
+      cgen()->SetFrame(NULL, &empty);
+    } else {
+      cgen()->frame()->MergeTo(entry_frame_);
+      cgen()->DeleteFrame();
+    }
+
+    // The predicate is_linked() should now be true.  The implementation

[Erik Corry, 2009/08/10 10:56:45]

This comment doesn't explain itself very well.

[Kevin Millikin (Chromium), 2009/08/10 11:11:31]

Reworded:

"The predicate is_linked() should be made true.  Its implementation detects the
presence of a frame pointer in the reaching_frames_ list."

+    // uses the presence of a frame pointer in the reaching_frames_ list.
+    if (!is_linked()) {
+      reaching_frames_.Add(NULL);
+      ASSERT(is_linked());
+    }
   }
+  __ jmp(&entry_label_);
 }
 
 
 void JumpTarget::DoBranch(Condition cc, Hint ignored) {
   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.
-
-    // 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;
-    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;
+    cgen()->frame()->MergeTo(entry_frame_);
+  } else {
+    // Clone the current frame to use as the expected one at the target if
+    // necessary.
+    if (entry_frame_ == NULL) {
+      entry_frame_ = new VirtualFrame(cgen()->frame());
     }
-
-    // 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;
-      }
+    // The predicate is_linked() should now be true.  The implementation
+    // uses the presence of a frame pointer in the reaching_frames_ list.
+    if (!is_linked()) {
+      reaching_frames_.Add(NULL);
+      ASSERT(is_linked());
     }
-
-    // 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);
-    cgen()->frame()->MergeTo(entry_frame_);
-    cgen()->DeleteFrame();
-    __ b(&entry_label_);
-    cgen()->SetFrame(fall_through_frame, &non_frame_registers);
-    __ bind(&original_fall_through);
-
-  } else {
-    // Preconfigured entry frame is not used on ARM.
-    ASSERT(entry_frame_ == NULL);
-    // 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());
   }
+  __ b(cc, &entry_label_);
 }
 
 
 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.
   ASSERT(cgen()->has_valid_frame());
   // There are no non-frame references across the call.
   ASSERT(cgen()->HasValidEntryRegisters());
   ASSERT(!is_linked());
 
-  cgen()->frame()->SpillAll();
+  // Calls are always 'forward' so we use a copy of the current frame (plus
+  // one for a return address) as the expected frame.
+  ASSERT(entry_frame_ == NULL);
   VirtualFrame* target_frame = new VirtualFrame(cgen()->frame());
   target_frame->Adjust(1);
-  // We do not expect a call with a preconfigured entry frame.
-  ASSERT(entry_frame_ == NULL);
-  AddReachingFrame(target_frame);
-  __ bl(&merge_labels_.last());
+  entry_frame_ = target_frame;
+
+  // is_linked() should now be true.  The JumpTarget class uses the presence
+  // of a frame pointer in the reaching_frames_ list.
+  reaching_frames_.Add(NULL);
+  ASSERT(is_linked());
+
+  __ bl(&entry_label_);
 }
 
 
 void JumpTarget::DoBind() {
   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->element_count() - 1);
-      if (difference > 0) {
-        frame->stack_pointer_ -= difference;
-        __ add(sp, sp, Operand(difference * kPointerSize));
-      }
-      __ bind(&entry_label_);
-      return;
+  if (cgen()->has_valid_frame()) {
+    // If there is a current frame we can use it on the fall through.
+    if (entry_frame_ == NULL) {
+      entry_frame_ = new VirtualFrame(cgen()->frame());
+    } else {
+      ASSERT(cgen()->frame()->Equals(entry_frame_));
     }
-
-    // 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 empty;
-      cgen()->SetFrame(frame, &empty);
-      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->element_count() - 1);
-      if (difference > 0) {
-        frame->stack_pointer_ -= difference;
-        __ add(sp, sp, Operand(difference * kPointerSize));
-      }
-      __ bind(&entry_label_);
-      return;
-    }
+  } else {
+    // If there is no current frame we must have an entry frame which we can
+    // copy.
+    ASSERT(entry_frame_ != NULL);
+    RegisterFile empty;
+    cgen()->SetFrame(new VirtualFrame(entry_frame_), &empty);
   }
 
-  // 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());  // Return value ignored.
-    RegisterFile empty;
-    cgen()->SetFrame(NULL, &empty);
-  }
-
-  // Compute the frame to use for entry to the block.
-  if (entry_frame_ == NULL) {
-    ComputeEntryFrame();
-  }
-
-  // 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_);
-    }
-  }
-
+  // is_linked() should now be false.  We may have inserted a bogus reaching
+  // frame to make it true, remove it now.
   if (is_linked()) {
-    // There were forward jumps.  Handle merging the reaching frames
-    // and possible fall through to the 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 (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 empty;
-          if (direction_ == BIDIRECTIONAL) {
-            cgen()->SetFrame(new VirtualFrame(frame), &empty);
-          } else {
-            cgen()->SetFrame(frame, &empty);
-            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.
-              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 empty;
-          cgen()->SetFrame(frame, &empty);
-          reaching_frames_[i] = NULL;
-        }
-      }
-    }
-
-    // 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 empty;
-      cgen()->SetFrame(new VirtualFrame(entry_frame_), &empty);
-    }
-
-    // There may be unprocessed reaching frames that did not need
-    // 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 (!merge_labels_[i].is_bound()) {
-        reaching_frames_[i] = NULL;
-        __ bind(&merge_labels_[i]);
-      }
-    }
-
-    // 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);
-
-    // Use a copy of the reaching frame so the original can be saved
-    // for possible reuse as a backward merge block.
-    RegisterFile empty;
-    cgen()->SetFrame(new VirtualFrame(reaching_frames_[0]), &empty);
-    __ bind(&merge_labels_[0]);
-    cgen()->frame()->MergeTo(entry_frame_);
+    reaching_frames_.Clear();
   }
 
   __ bind(&entry_label_);
 }
 
+
+void BreakTarget::Jump() {
+  // On ARM we do not currently emit merge code for jumps, so we need to do
+  // it explicitly here.  The only merging necessary is to drop extra
+  // statement state from the stack.
+  ASSERT(cgen()->has_valid_frame());
+  int count = cgen()->frame()->height() - expected_height_;

[Erik Corry, 2009/08/10 10:56:45]

Should we assert that count is positive?

[Kevin Millikin (Chromium), 2009/08/10 11:11:31]

Yea verily.  Even better it should go in VirtualFrame::Drop.  I've added it for
all platforms.

+  cgen()->frame()->Drop(count);
+  DoJump();
+}
+
+
+void BreakTarget::Jump(Result* arg) {
+  // On ARM we do not currently emit merge code for jumps, so we need to do
+  // it explicitly here.  The only merging necessary is to drop extra
+  // statement state from the stack.
+  ASSERT(cgen()->has_valid_frame());
+  int count = cgen()->frame()->height() - expected_height_;
+  cgen()->frame()->Drop(count);
+  cgen()->frame()->Push(arg);
+  DoJump();
+}
+
+
+void BreakTarget::Bind() {
+#ifdef DEBUG
+  // All the forward-reaching frames should have been adjusted at the
+  // jumps to this target.
+  for (int i = 0; i < reaching_frames_.length(); i++) {
+    ASSERT(reaching_frames_[i] == NULL ||
+           reaching_frames_[i]->height() == expected_height_);
+  }
+#endif
+  // Drop leftover statement state from the frame before merging, even
+  // on the fall through.  This is so we can bind the return target
+  // with state on the frame.
+  if (cgen()->has_valid_frame()) {
+    int count = cgen()->frame()->height() - expected_height_;
+    // On ARM we do not currently emit merge code at binding sites, so we need
+    // to do it explicitly here.  The only merging necessary is to drop extra
+    // statement state from the stack.
+    cgen()->frame()->Drop(count);
+  }
+
+  DoBind();
+}
+
+
+void BreakTarget::Bind(Result* arg) {
+#ifdef DEBUG
+  // All the forward-reaching frames should have been adjusted at the
+  // jumps to this target.
+  for (int i = 0; i < reaching_frames_.length(); i++) {
+    ASSERT(reaching_frames_[i] == NULL ||
+           reaching_frames_[i]->height() == expected_height_ + 1);
+  }
+#endif
+  // Drop leftover statement state from the frame before merging, even
+  // on the fall through.  This is so we can bind the return target
+  // with state on the frame.
+  if (cgen()->has_valid_frame()) {
+    int count = cgen()->frame()->height() - expected_height_;
+    // On ARM we do not currently emit merge code at binding sites, so we need
+    // to do it explicitly here.  The only merging necessary is to drop extra
+    // statement state from the stack.
+    cgen()->frame()->ForgetElements(count);
+    cgen()->frame()->Push(arg);
+  }
+  DoBind();
+  *arg = cgen()->frame()->Pop();
+}
+
+
 #undef __
 
 
 } }  // namespace v8::internal