Experimental: improve the code generated for possibly boolean-valued...

src/codegen-ia32.cc

Index: src/codegen-ia32.cc
===================================================================
--- src/codegen-ia32.cc	(revision 1230)
+++ src/codegen-ia32.cc	(working copy)
@@ -45,6 +45,7 @@
       typeof_state_(NOT_INSIDE_TYPEOF),
       true_target_(NULL),
       false_target_(NULL),
+      fall_through_(NULL),
       previous_(NULL) {
   owner_->set_state(this);
 }
@@ -53,11 +54,13 @@
 CodeGenState::CodeGenState(CodeGenerator* owner,
                            TypeofState typeof_state,
                            JumpTarget* true_target,
-                           JumpTarget* false_target)
+                           JumpTarget* false_target,
+                           JumpTarget* fall_through)
     : owner_(owner),
       typeof_state_(typeof_state),
       true_target_(true_target),
       false_target_(false_target),
+      fall_through_(fall_through),
       previous_(owner->state()) {
   owner_->set_state(this);
 }
@@ -398,22 +401,60 @@
                                   TypeofState typeof_state,
                                   JumpTarget* true_target,
                                   JumpTarget* false_target,
+                                  JumpTarget* fall_through,
                                   bool force_control) {
   ASSERT(!in_spilled_code());
+  ASSERT(!fall_through->is_bound());
 #ifdef DEBUG
   int original_height = frame_->height();
 #endif
-  { CodeGenState new_state(this, typeof_state, true_target, false_target);
+  JumpTarget* non_fall_through =
+      (false_target == fall_through) ? true_target : false_target;
+  bool backward = non_fall_through->is_bound();
+  { CodeGenState new_state(this, typeof_state, true_target, false_target,
+                           fall_through);
     Visit(x);
   }
+  // There are four possibilities for the code generated by a call to
+  // Visit on an expression:
+  //
+  // 1. Conditional control flow to both control destinations by
+  //    branching to the non-fall-through destination and binding the
+  //    fall-through destination for the very next instruction to be
+  //    generated.
+  //
+  // 2. Unconditional control flow to the fall-through destination by
+  //    binding it (and not generating a branch or jump to the
+  //    non-fall-through destination).
+  //
+  // 3. Unconditional control flow to the non-fall-through destination
+  //    by jumping backward to it (if it was already bound) or binding
+  //    it.
+  //
+  // 4. No control flow and a result on top of the virtual frame.  In
+  //    this case there can still be dangling jumps to the true and
+  //    false labels (eg, from subexpressions of the short-circuited
+  //    boolean operators).
+  bool got_control = fall_through->is_bound() ||
+      (backward && !has_valid_frame()) ||
+      (!backward && non_fall_through->is_bound());
 
-  if (force_control && has_valid_frame()) {
+  if (force_control && !got_control) {
     // Convert the TOS value to a boolean in the condition code register.
-    ToBoolean(true_target, false_target);
+    ToBoolean(true_target, false_target, fall_through);
   }
 
-  ASSERT(!(force_control && has_valid_frame()));
-  ASSERT(!has_valid_frame() || frame_->height() == original_height + 1);
+#ifdef DEBUG
+  // ToBoolean will always bind the fall-through destination.
+  got_control = got_control || fall_through->is_bound();
+#endif
+  ASSERT(!force_control || got_control);
+  ASSERT(got_control || frame_->height() == original_height + 1);
+  ASSERT(!got_control ||
+         fall_through->is_bound() ||
+         (!fall_through->is_bound() && backward && !has_valid_frame()) ||
+         (!fall_through->is_bound() && !backward &&
+          non_fall_through->is_bound()));
 }
 
 
@@ -424,35 +465,46 @@
   ASSERT(!in_spilled_code());
   JumpTarget true_target(this);
   JumpTarget false_target(this);
-  LoadCondition(x, typeof_state, &true_target, &false_target, false);
+  LoadCondition(x, typeof_state, &true_target, &false_target,
+                &true_target, false);
 
-  if (true_target.is_linked() || false_target.is_linked()) {
-    // We have at least one condition value that has been "translated" into
-    // a branch, thus it needs to be loaded explicitly.
-    JumpTarget loaded(this);
-    if (has_valid_frame()) {
-      loaded.Jump();  // Don't lose the current TOS.
-    }
-    bool both = true_target.is_linked() && false_target.is_linked();
-    // Load "true" if necessary.
-    if (true_target.is_linked()) {
-      true_target.Bind();
-      VirtualFrame::SpilledScope spilled_scope(this);
-      frame_->EmitPush(Immediate(Factory::true_value()));
-    }
-    // If both "true" and "false" need to be reincarnated jump across the
-    // code for "false".
-    if (both) {
+  if (true_target.is_bound()) {
+    // We have control flow to the fall-through destination and
+    // possibly the non-fall-through.
+    frame_->Push(Factory::true_value());
+    if (false_target.is_linked()) {
+      JumpTarget loaded(this);
       loaded.Jump();
-    }
-    // Load "false" if necessary.
-    if (false_target.is_linked()) {
       false_target.Bind();
-      VirtualFrame::SpilledScope spilled_scope(this);
-      frame_->EmitPush(Immediate(Factory::false_value()));
+      frame_->Push(Factory::false_value());
+      loaded.Bind();
     }
-    // A value is loaded on all paths reaching this point.
-    loaded.Bind();
+  } else if (false_target.is_bound()) {
+    // We fell through to the label that was not our preferred fall
+    // through (ie, the expression was unconditionally false.
+    frame_->Push(Factory::false_value());
+  } else {
+    // We have a valid value on top of the frame, but we still may
+    // have dangling jumps to the true and false target from nested
+    // subexpressions (eg, the left subexpressions of the
+    // short-circuited boolean operators).
+    ASSERT(has_valid_frame());
+    if (true_target.is_linked() || false_target.is_linked()) {
+      JumpTarget loaded(this);
+      loaded.Jump();  // Don't lose the current TOS.
+      if (true_target.is_linked()) {
+        true_target.Bind();
+        frame_->Push(Factory::true_value());
+        if (false_target.is_linked()) {
+          loaded.Jump();
+        }
+      }
+      if (false_target.is_linked()) {
+        false_target.Bind();
+        frame_->Push(Factory::false_value());
+      }
+      loaded.Bind();
+    }
   }
   ASSERT(has_valid_frame());
   ASSERT(frame_->height() == original_height + 1);
@@ -569,6 +621,22 @@
 }
 
 
+void CodeGenerator::Branch(Condition cc,
+                           JumpTarget* true_target,
+                           JumpTarget* false_target,
+                           JumpTarget* fall_through) {
+  ASSERT(!fall_through->is_bound());
+  if (fall_through == false_target) {
+    true_target->Branch(cc);
+    false_target->Bind();
+  } else {
+    ASSERT(fall_through == true_target);
+    false_target->Branch(NegateCondition(cc));
+    true_target->Bind();
+  }
+}
+
+
 class ToBooleanStub: public CodeStub {
  public:
   ToBooleanStub() { }
@@ -585,7 +653,8 @@
 // convert it to a boolean in the condition code register or jump to
 // 'false_target'/'true_target' as appropriate.
 void CodeGenerator::ToBoolean(JumpTarget* true_target,
-                              JumpTarget* false_target) {
+                              JumpTarget* false_target,
+                              JumpTarget* fall_through) {
   Comment cmnt(masm_, "[ ToBoolean");
 
   // The value to convert should be popped from the stack.
@@ -619,8 +688,7 @@
   // Convert the result to a condition code.
   __ test(temp.reg(), Operand(temp.reg()));
   temp.Unuse();
-  true_target->Branch(not_equal);
-  false_target->Jump();
+  Branch(not_equal, true_target, false_target, fall_through);
 }
 
 
@@ -1249,7 +1317,8 @@
 void CodeGenerator::Comparison(Condition cc,
                                bool strict,
                                JumpTarget* true_target,
-                               JumpTarget* false_target) {
+                               JumpTarget* false_target,
+                               JumpTarget* fall_through) {
   // Strict only makes sense for equality comparisons.
   ASSERT(!strict || cc == equal);
 
@@ -1310,8 +1379,7 @@
   __ cmp(left_side.reg(), Operand(right_side.reg()));
   right_side.Unuse();
   left_side.Unuse();
-  true_target->Branch(cc);
-  false_target->Jump();
+  Branch(cc, true_target, false_target, fall_through);
 }
 
 
@@ -1347,8 +1415,7 @@
   // Test smi equality and comparison by signed int comparison.
   __ cmp(Operand(comparee.reg()), Immediate(smi_value));
   comparee.Unuse();
-  true_target()->Branch(cc);
-  false_target()->Jump();
+  Branch(cc);
 }
 
 
@@ -1554,36 +1621,36 @@
   if (has_then_stm && has_else_stm) {
     JumpTarget then(this);
     JumpTarget else_(this);
-    LoadCondition(node->condition(), NOT_INSIDE_TYPEOF, &then, &else_, true);
-    if (then.is_linked()) {
-      then.Bind();
+    LoadCondition(node->condition(), NOT_INSIDE_TYPEOF,
+                  &then, &else_, &then, true);
+    if (then.is_bound()) {
       Visit(node->then_statement());
-      if (has_valid_frame() && else_.is_linked()) {
-        // We have fallen through from the then block and we need to compile
-        // the else block.  Emit an unconditional jump around it.
-        exit.Jump();
+      if (else_.is_linked()) {
+        if (has_valid_frame()) {
+          exit.Jump();
+        }
+        else_.Bind();
       }
     }
-    if (else_.is_linked()) {
-      else_.Bind();
+    if (else_.is_bound()) {
       Visit(node->else_statement());
     }
 
   } else if (has_then_stm) {
     ASSERT(!has_else_stm);
     JumpTarget then(this);
-    LoadCondition(node->condition(), NOT_INSIDE_TYPEOF, &then, &exit, true);
-    if (then.is_linked()) {
-      then.Bind();
+    LoadCondition(node->condition(), NOT_INSIDE_TYPEOF,
+                  &then, &exit, &then, true);
+    if (then.is_bound()) {
       Visit(node->then_statement());
     }
 
   } else if (has_else_stm) {
     ASSERT(!has_then_stm);
     JumpTarget else_(this);
-    LoadCondition(node->condition(), NOT_INSIDE_TYPEOF, &exit, &else_, true);
-    if (else_.is_linked()) {
-      else_.Bind();
+    LoadCondition(node->condition(), NOT_INSIDE_TYPEOF,
+                  &exit, &else_, &else_, true);
+    if (else_.is_bound()) {
       Visit(node->else_statement());
     }
 
@@ -1592,10 +1659,9 @@
     // We only care about the condition's side effects (not its value
     // or control flow effect).  LoadCondition is called without
     // forcing control flow.
-    LoadCondition(node->condition(), NOT_INSIDE_TYPEOF, &exit, &exit, false);
-    if (has_valid_frame()) {
-      // Control flow can fall off the end of the condition with a
-      // value on the frame.
+    LoadCondition(node->condition(), NOT_INSIDE_TYPEOF,
+                  &exit, &exit, &exit, false);
+    if (!exit.is_bound()) {
       frame_->Drop();
     }
   }
@@ -1898,11 +1964,10 @@
     frame_->Dup();
     Load(clause->label());
     JumpTarget enter_body(this);
-    Comparison(equal, true, &enter_body, &next_test);
+    Comparison(equal, true, &enter_body, &next_test, &enter_body);
 
     // Before entering the body from the test remove the switch value from
     // the frame.
-    enter_body.Bind();
     frame_->Drop();
 
     // Label the body so that fall through is enabled.
@@ -2015,7 +2080,8 @@
         node->continue_target()->Bind();
         if (has_valid_frame()) {
           LoadCondition(node->cond(), NOT_INSIDE_TYPEOF,
-                        &body, node->break_target(), true);
+                        &body, node->break_target(), node->break_target(),
+                        true);
         }
       }
       break;
@@ -2039,11 +2105,10 @@
       if (info == DONT_KNOW) {
         JumpTarget body(this);
         LoadCondition(node->cond(), NOT_INSIDE_TYPEOF,
-                      &body, node->break_target(), true);
-        body.Bind();
+                      &body, node->break_target(), &body, true);
       }
 
-      if (has_valid_frame()) {
+      if (!node->break_target()->is_bound()) {
         CheckStack();  // TODO(1222600): ignore if body contains calls.
         Visit(node->body());
 
@@ -2082,11 +2147,10 @@
       if (info == DONT_KNOW) {
         JumpTarget body(this);
         LoadCondition(node->cond(), NOT_INSIDE_TYPEOF,
-                      &body, node->break_target(), true);
-        body.Bind();
+                      &body, node->break_target(), &body, true);
       }
 
-      if (has_valid_frame()) {
+      if (!node->break_target()->is_bound()) {
         CheckStack();  // TODO(1222600): ignore if body contains calls.
         Visit(node->body());
 
@@ -2117,7 +2181,12 @@
   }
 
   DecrementLoopNesting();
-  node->break_target()->Bind();
+  // The break target may have been bound in the condition of a do
+  // loop, or in the conditions of the other loops if they are
+  // unconditionally false.  Avoid rebinding it.
+  if (node->break_target()->is_linked()) {
+    node->break_target()->Bind();
+  }
 }
 
 
@@ -2656,20 +2725,18 @@
   JumpTarget then(this);
   JumpTarget else_(this);
   JumpTarget exit(this);
-  LoadCondition(node->condition(), NOT_INSIDE_TYPEOF, &then, &else_, true);
-  if (then.is_linked()) {
-    then.Bind();
+  LoadCondition(node->condition(), NOT_INSIDE_TYPEOF,
+                &then, &else_, &then, true);
+  if (then.is_bound()) {
     Load(node->then_expression(), typeof_state());
     if (else_.is_linked()) {
       exit.Jump();
+      else_.Bind();
     }
   }
-
-  if (else_.is_linked()) {
-    else_.Bind();
+  if (else_.is_bound()) {
     Load(node->else_expression(), typeof_state());
   }
-
   exit.Bind();
 }
 
@@ -2824,15 +2891,7 @@
   Variable* var = node->var();
   Expression* expr = var->rewrite();
   if (expr != NULL) {
-    // We have to be wary of calling Visit directly on expressions.  Because
-    // of special casing comparisons of the form typeof<expr> === "string",
-    // we can return from a call from Visit (to a comparison or a unary
-    // operation) without a virtual frame; which will probably crash if we
-    // try to emit frame code before reestablishing a frame.  Here we're
-    // safe as long as variable proxies can't rewrite into typeof
-    // comparisons or unary logical not expressions.
     Visit(expr);
-    ASSERT(has_valid_frame());
   } else {
     ASSERT(var->is_global());
     Reference ref(this, node);
@@ -3452,8 +3511,7 @@
   ASSERT(value.is_valid());
   __ test(value.reg(), Immediate(kSmiTagMask));
   value.Unuse();
-  true_target()->Branch(zero);
-  false_target()->Jump();
+  Branch(zero);
 }
 
 
@@ -3486,8 +3544,7 @@
   ASSERT(value.is_valid());
   __ test(value.reg(), Immediate(kSmiTagMask | 0x80000000));
   value.Unuse();
-  true_target()->Branch(zero);
-  false_target()->Jump();
+  Branch(zero);
 }
 
 
@@ -3648,8 +3705,7 @@
   __ cmp(temp.reg(), JS_ARRAY_TYPE);
   value.Unuse();
   temp.Unuse();
-  true_target()->Branch(equal);
-  false_target()->Jump();
+  Branch(equal);
 }
 
 
@@ -3754,8 +3810,7 @@
   __ cmp(right.reg(), Operand(left.reg()));
   right.Unuse();
   left.Unuse();
-  true_target()->Branch(equal);
-  false_target()->Jump();
+  Branch(equal);
 }
 
 
@@ -3814,7 +3869,7 @@
 
   if (op == Token::NOT) {
     LoadCondition(node->expression(), NOT_INSIDE_TYPEOF,
-                  false_target(), true_target(), true);
+                  false_target(), true_target(), fall_through(), true);
 
   } else if (op == Token::DELETE) {
     Property* property = node->expression()->AsProperty();
@@ -4149,16 +4204,18 @@
 
   if (op == Token::AND) {
     JumpTarget is_true(this);
+    bool backward = false_target()->is_bound();
     LoadCondition(node->left(), NOT_INSIDE_TYPEOF,
-                  &is_true, false_target(), false);
-    if (!has_valid_frame()) {
-      if (is_true.is_linked()) {
-        // Evaluate right side expression.
-        is_true.Bind();
-        LoadCondition(node->right(), NOT_INSIDE_TYPEOF,
-                      true_target(), false_target(), false);
-      }
-    } else {
+                  &is_true, false_target(), &is_true, false);
+    if (is_true.is_bound()) {
+      LoadCondition(node->right(), NOT_INSIDE_TYPEOF,
+                    true_target(), false_target(), fall_through(),
+                    false);
+    } else if (!backward && false_target()->is_bound()) {
+      // If the false target became bound due to the left operand,
+      // then that operand was unconditionally false.
+      return;
+    } else if (has_valid_frame()) {
       // We have a materialized value on the frame.
       JumpTarget pop_and_continue(this);
       JumpTarget exit(this);
@@ -4169,10 +4226,9 @@
       //
       // Duplicate the TOS value. The duplicate will be popped by ToBoolean.
       frame_->Dup();
-      ToBoolean(&pop_and_continue, &exit);
+      ToBoolean(&pop_and_continue, &exit, &pop_and_continue);
 
       // Pop the result of evaluating the first part.
-      pop_and_continue.Bind();
       frame_->Drop();
 
       // Evaluate right side expression.
@@ -4185,15 +4241,17 @@
 
   } else if (op == Token::OR) {
     JumpTarget is_false(this);
+    bool backward = true_target()->is_bound();
     LoadCondition(node->left(), NOT_INSIDE_TYPEOF,
-                  true_target(), &is_false, false);
-    if (!has_valid_frame()) {
-      if (is_false.is_linked()) {
-        // Evaluate right side expression.
-        is_false.Bind();
-        LoadCondition(node->right(), NOT_INSIDE_TYPEOF,
-                      true_target(), false_target(), false);
-      }
+                  true_target(), &is_false, &is_false, false);
+    if (is_false.is_bound()) {
+      LoadCondition(node->right(), NOT_INSIDE_TYPEOF,
+                    true_target(), false_target(), fall_through(),
+                    false);
+    } else if (!backward && true_target()->is_bound()) {
+      // If the true target became bound due to the left operand, then
+      // that operand was unconditionally true.
+      return;
     } else {
       // We have a materialized value on the frame.
       JumpTarget pop_and_continue(this);
@@ -4204,10 +4262,9 @@
       // section 9.2, page 30.
       // Duplicate the TOS value. The duplicate will be popped by ToBoolean.
       frame_->Dup();
-      ToBoolean(&exit, &pop_and_continue);
+      ToBoolean(&exit, &pop_and_continue, &pop_and_continue);
 
       // Pop the result of evaluating the first part.
-      pop_and_continue.Bind();
       frame_->Drop();
 
       // Evaluate right side expression.
@@ -4315,9 +4372,9 @@
         __ test(temp.reg(), Immediate(1 << Map::kIsUndetectable));
         cc = not_zero;
       }
+
       operand.Unuse();
-      true_target()->Branch(cc);
-      false_target()->Jump();
+      Branch(cc);
       return;
     }
   }
@@ -4344,8 +4401,7 @@
       __ mov(answer.reg(), FieldOperand(answer.reg(), HeapObject::kMapOffset));
       __ cmp(answer.reg(), Factory::heap_number_map());
       answer.Unuse();
-      true_target()->Branch(equal);
-      false_target()->Jump();
+      Branch(equal);
 
     } else if (check->Equals(Heap::string_symbol())) {
       __ test(answer.reg(), Immediate(kSmiTagMask));
@@ -4364,16 +4420,14 @@
       __ cmp(temp.reg(), FIRST_NONSTRING_TYPE);
       temp.Unuse();
       answer.Unuse();
-      true_target()->Branch(less);
-      false_target()->Jump();
+      Branch(less);
 
     } else if (check->Equals(Heap::boolean_symbol())) {
       __ cmp(answer.reg(), Factory::true_value());
       true_target()->Branch(equal);
       __ cmp(answer.reg(), Factory::false_value());
       answer.Unuse();
-      true_target()->Branch(equal);
-      false_target()->Jump();
+      Branch(equal);
 
     } else if (check->Equals(Heap::undefined_symbol())) {
       __ cmp(answer.reg(), Factory::undefined_value());
@@ -4389,8 +4443,7 @@
                  FieldOperand(answer.reg(), Map::kBitFieldOffset));
       __ test(answer.reg(), Immediate(1 << Map::kIsUndetectable));
       answer.Unuse();
-      true_target()->Branch(not_zero);
-      false_target()->Jump();
+      Branch(not_zero);
 
     } else if (check->Equals(Heap::function_symbol())) {
       __ test(answer.reg(), Immediate(kSmiTagMask));
@@ -4401,8 +4454,7 @@
                  FieldOperand(answer.reg(), Map::kInstanceTypeOffset));
       __ cmp(answer.reg(), JS_FUNCTION_TYPE);
       answer.Unuse();
-      true_target()->Branch(equal);
-      false_target()->Jump();
+      Branch(equal);
 
     } else if (check->Equals(Heap::object_symbol())) {
       __ test(answer.reg(), Immediate(kSmiTagMask));
@@ -4424,13 +4476,16 @@
       __ cmp(map.reg(), LAST_JS_OBJECT_TYPE);
       answer.Unuse();
       map.Unuse();
-      true_target()->Branch(less_equal);
-      false_target()->Jump();
+      Branch(less_equal);
     } else {
       // Uncommon case: typeof testing against a string literal that is
       // never returned from the typeof operator.
       answer.Unuse();
-      false_target()->Jump();
+      if (false_target()->is_bound()) {
+        false_target()->Jump();
+      } else {
+        false_target()->Bind();
+      }
     }
     return;
   }
@@ -4471,8 +4526,7 @@
       answer.ToRegister();
       __ test(answer.reg(), Operand(answer.reg()));
       answer.Unuse();
-      true_target()->Branch(zero);
-      false_target()->Jump();
+      Branch(zero);
       return;
     }
     default:
@@ -4490,7 +4544,7 @@
   } else {
     Load(left);
     Load(right);
-    Comparison(cc, strict, true_target(), false_target());
+    Comparison(cc, strict, true_target(), false_target(), fall_through());
   }
 }