Make x87 stack tracking more robust and avoid spilling

src/ia32/lithium-codegen-ia32.cc

Index: src/ia32/lithium-codegen-ia32.cc
diff --git a/src/ia32/lithium-codegen-ia32.cc b/src/ia32/lithium-codegen-ia32.cc
index 10115b1ac4744b14b0043293e0fc783b862502f5..e31c8859ac16176f85e9edc6b9988461f6747a49 100644
--- a/src/ia32/lithium-codegen-ia32.cc
+++ b/src/ia32/lithium-codegen-ia32.cc
@@ -29,6 +29,7 @@
 
 #if V8_TARGET_ARCH_IA32
 
+#include "lithium-allocator-inl.h"
 #include "ia32/lithium-codegen-ia32.h"
 #include "ic.h"
 #include "code-stubs.h"
@@ -335,6 +336,9 @@ bool LCodeGen::GeneratePrologue() {
 bool LCodeGen::GenerateBody() {
   ASSERT(is_generating());
   bool emit_instructions = true;
+
+  if (!CpuFeatures::IsSupported(SSE2))  PreRecordX87StackUsage();
+
   for (current_instruction_ = 0;
        !is_aborted() && current_instruction_ < instructions_->length();
        current_instruction_++) {
@@ -353,15 +357,29 @@ bool LCodeGen::GenerateBody() {
               instr->Mnemonic());
     }
 
-    if (!CpuFeatures::IsSupported(SSE2)) FlushX87StackIfNecessary(instr);
+    if (!CpuFeatures::IsSupported(SSE2)) {
+      FlushX87StackIfNecessary(instr);
+
+      if (instr->IsControl()) {
+        // TODO(olivf) sorry but if you entered this dark corner and
+        // triggered the assert below, you have to teach the x87 stack how to
+        // merge phi node inputs.
+        ASSERT(x87_stack_.depth() <= 1);
+        x87_stack_.leaving(current_block_,
+            static_cast<LControlInstruction<0, 0>*>(instr)->SuccessorAt(0));
+      }
+    }
 
     RecordAndUpdatePosition(instr->position());
 
     instr->CompileToNative(this);
 
-    if (!CpuFeatures::IsSupported(SSE2) &&
-        FLAG_debug_code && FLAG_enable_slow_asserts) {
+    if (!CpuFeatures::IsSupported(SSE2)) {
+      RestoreX87StackIfNecessary(instr);
+      if (!instr->IsLabel() && !instr->IsGap() &&
+          FLAG_debug_code && FLAG_enable_slow_asserts) {
         __ VerifyX87StackDepth(x87_stack_.depth());
+      }
     }
   }
   EnsureSpaceForLazyDeopt();
@@ -495,13 +513,6 @@ XMMRegister LCodeGen::ToDoubleRegister(int index) const {
 }
 
 
-void LCodeGen::X87LoadForUsage(X87Register reg) {
-  ASSERT(x87_stack_.Contains(reg));
-  x87_stack_.Fxch(reg);
-  x87_stack_.pop();
-}
-
-
 void LCodeGen::X87Stack::Fxch(X87Register reg, int other_slot) {
   ASSERT(Contains(reg) && stack_depth_ > other_slot);
   int i  = ArrayIndex(reg);
@@ -524,6 +535,74 @@ void LCodeGen::X87Stack::Fxch(X87Register reg, int other_slot) {
 }
 
 
+int LCodeGen::X87Stack::PhysicalPos(X87Register reg) {
+  return st2idx(ArrayIndex(reg));
+}
+
+
+void LCodeGen::X87Stack::leaving(HBasicBlock* block, HBasicBlock* next) {
+  for (int i = 0; i < X87Register::kNumAllocatableRegisters; i++) {
+    X87Register reg = X87Register::FromAllocationIndex(i);
+    // If by the end of block the register marked as defined here, but not
+    // yet on the stack, this means, the block dominates all definitions.
+    // To assert a consistent state of the stack for all successors, we
+    // push a dummy value here.
+    if (dominated_[i] == block && first_defined_[i] != block) {
+      if (FLAG_trace_x87) {
+        PrintF(stdout,
+            "%s is not defined in dominator block %d, pushing dummy\n",
+            X87Register::AllocationIndexToString(i), block->block_id());
+      }
+      push(reg);
+      masm()->fldz();
+    } else if (Contains(reg) && !dominated_[reg.code()]->Dominates(next)) {
+      if (FLAG_trace_x87) {
+        PrintF(stdout,
+            "freeing %s: def dominated by %d, but are leaving %d for %d\n",
+            X87Register::AllocationIndexToString(i),
+            dominated_[i]->block_id(), block->block_id(), next->block_id());
+      }
+      Free(reg);
+    }
+  }
+}
+
+
+void LCodeGen::X87Stack::record_usage(X87Register reg, HBasicBlock* block) {
+  ASSERT(first_defined_[reg.code()] != NULL);
+  record_definition(reg, block);
+}
+
+
+void LCodeGen::X87Stack::record_definition(X87Register reg,
+                                           HBasicBlock* block) {
+  int i = reg.code();
+  ASSERT(i < X87Register::kNumAllocatableRegisters);
+  if (first_defined_[i] == NULL) {
+    first_defined_[i] = dominated_[i] = block;
+    if (FLAG_trace_x87) {
+      PrintF(stdout, "%s first defined in %d\n",
+                     X87Register::AllocationIndexToString(i),
+                     block->block_id());
+    }
+  } else {
+    HBasicBlock* current = dominated_[i];
+    if (current == block) return;
+    while (current != NULL) {
+      if (current->Dominates(block)) break;
+      current = current->dominator();
+    }
+    ASSERT(current != NULL);
+    if (FLAG_trace_x87) {
+      PrintF(stdout, "%s reused in %d, update dominator to %d\n",
+                     X87Register::AllocationIndexToString(i),
+                     block->block_id(), current->block_id());
+    }
+    dominated_[i] = current;
+  }
+}
+
+
 int LCodeGen::X87Stack::st2idx(int pos) {
   return stack_depth_ - pos - 1;
 }
@@ -560,6 +639,17 @@ void LCodeGen::X87Stack::Free(X87Register reg) {
 }
 
 
+void LCodeGen::X87Mov(X87Register dst, X87Register src) {
+  if (x87_stack_.Contains(dst)) {
+    x87_stack_.Fxch(dst);
+    __ fstp(0);
+  } else {
+    x87_stack_.push(dst);
+  }
+  __ fld(x87_stack_.PhysicalPos(src));
+}
+
+
 void LCodeGen::X87Mov(X87Register dst, Operand src, X87OperandType opts) {
   if (x87_stack_.Contains(dst)) {
     x87_stack_.Fxch(dst);
@@ -618,7 +708,7 @@ void LCodeGen::X87Stack::CommitWrite(X87Register reg) {
   // Assert the reg is prepared to write, but not on the virtual stack yet
   ASSERT(!Contains(reg) && stack_[stack_depth_].is(reg) &&
       stack_depth_ < X87Register::kNumAllocatableRegisters);
-  stack_depth_++;
+  push(reg);
 }
 
 
@@ -632,25 +722,64 @@ void LCodeGen::X87PrepareBinaryOp(
 
 
 void LCodeGen::X87Stack::FlushIfNecessary(LInstruction* instr, LCodeGen* cgen) {
-  if (stack_depth_ > 0 && instr->ClobbersDoubleRegisters()) {
-    bool double_inputs = instr->HasDoubleRegisterInput();
-
-    // Flush stack from tos down, since FreeX87() will mess with tos
-    for (int i = stack_depth_-1; i >= 0; i--) {
-      X87Register reg = stack_[i];
-      // Skip registers which contain the inputs for the next instruction
-      // when flushing the stack
-      if (double_inputs && instr->IsDoubleInput(reg, cgen)) {
-        continue;
+  if (stack_depth_ > 0) {
+    if (instr->IsReturn()) {
+      while (stack_depth_ > 0) {
+        __ fstp(0);
+        stack_depth_--;
+      }
+    } else if (instr->ClobbersDoubleRegisters()) {
+      bool double_inputs = instr->HasDoubleRegisterInput();
+      int inp_arg = 0;
+      // Flush stack from tos down, to leave the inputs encountered first at
+      // the lower stack positions.
+      for (int i = stack_depth_-1; i >= 0; i--) {
+        X87Register reg = stack_[i];
+        // Skip registers which contain the inputs. By flushing from tos down,
+        // we effectively leave them at the lower end of the physical stack.
+        if (double_inputs && instr->IsDoubleInput(reg, cgen)) {
+          int old_pos = ArrayIndex(reg);
+          stack_[old_pos] = stack_[inp_arg];
+          stack_[inp_arg++] = reg;
+          continue;

[Toon Verwaest, 2013/08/22 13:33:41]

As discussed, this seems broken. If we swap input variables downwards, we'll
visit them again and they'll seem like input variables again; and we won't pop
non-input-variables we just swapped. Additionally, in larger stacks, we'll never
manage to get input variables that are being swapped upwards in the right
position.

I also don't like this kind of code at all; it's very hard to understand.

+        }
+        __ fstp(st2idx(i));
       }
-      Free(reg);
-      if (i < stack_depth_-1) i++;
     }
   }
-  if (instr->IsReturn()) {
-    while (stack_depth_ > 0) {
-      __ fstp(0);
-      stack_depth_--;
+}
+
+
+void LCodeGen::X87Stack::RestoreIfNecessary(LInstruction* instr,
+                                            LCodeGen* cgen) {
+  if (instr->ClobbersDoubleRegisters()) {
+    // Restoring the physical stack height is done after the instruction, which
+    // does not work if the instruction jumps somewhere else.
+    ASSERT(!instr->IsControl());
+    int amount = instr->HasDoubleRegisterResult()
+        ? stack_depth_ - 1 : stack_depth_;
+    for (int i = 0; i < amount; i++) __ fld(0);
+  }
+}
+
+
+void LCodeGen::PreRecordX87StackUsage() {
+  HBasicBlock* current = NULL;
+  for (current_instruction_ = 0;
+       !is_aborted() && current_instruction_ < instructions_->length();
+       current_instruction_++) {
+    LInstruction* instr = instructions_->at(current_instruction_);
+    if (instr->IsLabel()) current = LLabel::cast(instr)->block();
+    if (instr->HasDoubleRegisterResult()) {
+      X87Register res = ToX87Register(instr->result());
+      x87_stack_.record_definition(res, current);
+    }
+    for (UseIterator it(instr); !it.Done(); it.Advance()) {
+      LOperand* op = it.Current();
+      if (op != NULL && op->IsDoubleRegister()) {
+         X87Register res = ToX87Register(op);
+         x87_stack_.record_usage(res, current);
+      }
     }
   }
 }
@@ -1237,7 +1366,7 @@ void LCodeGen::DoLabel(LLabel* label) {
           label->block_id(),
           LabelType(label));
   __ bind(label->label());
-  current_block_ = label->block_id();
+  current_block_ = label->block();
   DoGap(label);
 }
 
@@ -2229,7 +2358,8 @@ void LCodeGen::DoArithmeticT(LArithmeticT* instr) {
 
 
 int LCodeGen::GetNextEmittedBlock() const {
-  for (int i = current_block_ + 1; i < graph()->blocks()->length(); ++i) {
+  for (int i = current_block_->block_id() + 1;
+       i < graph()->blocks()->length(); ++i) {
     if (!chunk_->GetLabel(i)->HasReplacement()) return i;
   }
   return -1;
@@ -2533,15 +2663,11 @@ void LCodeGen::DoCmpHoleAndBranch(LCmpHoleAndBranch* instr) {
   } else {
     // Put the value to the top of stack
     X87Register src = ToX87Register(instr->object());
-    X87LoadForUsage(src);
+    X87Fxch(src);
     __ fld(0);
     __ fld(0);
     __ FCmp();
-    Label ok;
-    __ j(parity_even, &ok);
-    __ fstp(0);
-    EmitFalseBranch(instr, no_condition);
-    __ bind(&ok);
+    EmitFalseBranch(instr, parity_odd);
   }
 
 
@@ -2551,7 +2677,7 @@ void LCodeGen::DoCmpHoleAndBranch(LCmpHoleAndBranch* instr) {
     XMMRegister input_reg = ToDoubleRegister(instr->object());
     __ movdbl(MemOperand(esp, 0), input_reg);
   } else {
-    __ fstp_d(MemOperand(esp, 0));
+    __ fst_d(MemOperand(esp, 0));
   }
 
   __ add(esp, Immediate(kDoubleSize));
@@ -5082,7 +5208,7 @@ void LCodeGen::DoNumberTagD(LNumberTagD* instr) {
   if (!use_sse2) {
     // Put the value to the top of stack
     X87Register src = ToX87Register(instr->value());
-    X87LoadForUsage(src);
+    X87Fxch(src);
   }
 
   DeferredNumberTagD* deferred = new(zone()) DeferredNumberTagD(this, instr);
@@ -5098,7 +5224,7 @@ void LCodeGen::DoNumberTagD(LNumberTagD* instr) {
     XMMRegister input_reg = ToDoubleRegister(instr->value());
     __ movdbl(FieldOperand(reg, HeapNumber::kValueOffset), input_reg);
   } else {
-    __ fstp_d(FieldOperand(reg, HeapNumber::kValueOffset));
+    __ fst_d(FieldOperand(reg, HeapNumber::kValueOffset));
   }
 }