Make x87 stack tracking more robust and avoid spilling

src/ia32/lithium-codegen-ia32.cc

 // Copyright 2012 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 11 matching lines @@
 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 
 #include "v8.h"
 
 #if V8_TARGET_ARCH_IA32
 
+#include "lithium-allocator-inl.h"
 #include "ia32/lithium-codegen-ia32.h"
 #include "ic.h"
 #include "code-stubs.h"
 #include "deoptimizer.h"
 #include "stub-cache.h"
 #include "codegen.h"
 
 namespace v8 {
 namespace internal {
 
@@ skipping 286 matching lines @@
     // incoming context.
     __ CallRuntime(Runtime::kTraceEnter, 0);
   }
   return !is_aborted();
 }
 
 
 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_++) {
     LInstruction* instr = instructions_->at(current_instruction_);
 
     // Don't emit code for basic blocks with a replacement.
     if (instr->IsLabel()) {
       emit_instructions = !LLabel::cast(instr)->HasReplacement();
     }
     if (!emit_instructions) continue;
 
     if (FLAG_code_comments && instr->HasInterestingComment(this)) {
       Comment(";;; <@%d,#%d> %s",
               current_instruction_,
               instr->hydrogen_value()->id(),
               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();
   return !is_aborted();
 }
 
 
 bool LCodeGen::GenerateJumpTable() {
   Label needs_frame;
   if (jump_table_.length() > 0) {
@@ skipping 113 matching lines @@
 X87Register LCodeGen::ToX87Register(int index) const {
   return X87Register::FromAllocationIndex(index);
 }
 
 
 XMMRegister LCodeGen::ToDoubleRegister(int index) const {
   return XMMRegister::FromAllocationIndex(index);
 }
 
 
-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);
   int st = st2idx(i);
   if (st != other_slot) {
     int other_i = st2idx(other_slot);
     X87Register other = stack_[other_i];
     stack_[other_i]   = reg;
     stack_[i]         = other;
     if (st == 0) {
       __ fxch(other_slot);
     } else if (other_slot == 0) {
       __ fxch(st);
     } else {
       __ fxch(st);
       __ fxch(other_slot);
       __ fxch(st);
     }
   }
 }
 
 
+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;
 }
 
 
 int LCodeGen::X87Stack::ArrayIndex(X87Register reg) {
   for (int i = 0; i < stack_depth_; i++) {
     if (stack_[i].is(reg)) return i;
   }
   UNREACHABLE();
@@ skipping 16 matching lines @@
   if (st > 0) {
     // keep track of how fstp(i) changes the order of elements
     int tos_i = st2idx(0);
     stack_[i] = stack_[tos_i];
   }
   pop();
   __ fstp(st);
 }
 
 
+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);
     __ fstp(0);
   } else {
     x87_stack_.push(dst);
   }
   X87Fld(src, opts);
 }
 
@@ skipping 38 matching lines @@
   }
   // Mark this register as the next register to write to
   stack_[stack_depth_] = reg;
 }
 
 
 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);
 }
 
 
 void LCodeGen::X87PrepareBinaryOp(
     X87Register left, X87Register right, X87Register result) {
   // You need to use DefineSameAsFirst for x87 instructions
   ASSERT(result.is(left));
   x87_stack_.Fxch(right, 1);
   x87_stack_.Fxch(left);
 }
 
 
 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_--;
       }
-      Free(reg);
-      if (i < stack_depth_-1) i++;
-    }
-  }
-  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));
+      }
     }
   }
 }
+
+
+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);
+      }
+    }
+  }
+}
 
 
 void LCodeGen::EmitFlushX87ForDeopt() {
   // The deoptimizer does not support X87 Registers. But as long as we
   // deopt from a stub its not a problem, since we will re-materialize the
   // original stub inputs, which can't be double registers.
   ASSERT(info()->IsStub());
   if (FLAG_debug_code && FLAG_enable_slow_asserts) {
     __ pushfd();
     __ VerifyX87StackDepth(x87_stack_.depth());
@@ skipping 563 matching lines @@
 }
 
 
 void LCodeGen::DoLabel(LLabel* label) {
   Comment(";;; <@%d,#%d> -------------------- B%d%s --------------------",
           current_instruction_,
           label->hydrogen_value()->id(),
           label->block_id(),
           LabelType(label));
   __ bind(label->label());
-  current_block_ = label->block_id();
+  current_block_ = label->block();
   DoGap(label);
 }
 
 
 void LCodeGen::DoParallelMove(LParallelMove* move) {
   resolver_.Resolve(move);
 }
 
 
 void LCodeGen::DoGap(LGap* gap) {
@@ skipping 971 matching lines @@
   ASSERT(ToRegister(instr->right()).is(eax));
   ASSERT(ToRegister(instr->result()).is(eax));
 
   BinaryOpStub stub(instr->op(), NO_OVERWRITE);
   CallCode(stub.GetCode(isolate()), RelocInfo::CODE_TARGET, instr);
   __ nop();  // Signals no inlined code.
 }
 
 
 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;
 }
 
 
 template<class InstrType>
 void LCodeGen::EmitBranch(InstrType instr, Condition cc) {
   int left_block = instr->TrueDestination(chunk_);
   int right_block = instr->FalseDestination(chunk_);
@@ skipping 283 matching lines @@
 
   bool use_sse2 = CpuFeatures::IsSupported(SSE2);
   if (use_sse2) {
     CpuFeatureScope scope(masm(), SSE2);
     XMMRegister input_reg = ToDoubleRegister(instr->object());
     __ ucomisd(input_reg, input_reg);
     EmitFalseBranch(instr, parity_odd);
   } 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);
   }
 
 
   __ sub(esp, Immediate(kDoubleSize));
   if (use_sse2) {
     CpuFeatureScope scope(masm(), SSE2);
     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));
   int offset = sizeof(kHoleNanUpper32);
   __ cmp(MemOperand(esp, -offset), Immediate(kHoleNanUpper32));
   EmitBranch(instr, equal);
 }
 
 
 Condition LCodeGen::EmitIsObject(Register input,
@@ skipping 2510 matching lines @@
    private:
     LNumberTagD* instr_;
   };
 
   Register reg = ToRegister(instr->result());
 
   bool use_sse2 = CpuFeatures::IsSupported(SSE2);
   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);
   if (FLAG_inline_new) {
     Register tmp = ToRegister(instr->temp());
     __ AllocateHeapNumber(reg, tmp, no_reg, deferred->entry());
   } else {
     __ jmp(deferred->entry());
   }
   __ bind(deferred->exit());
   if (use_sse2) {
     CpuFeatureScope scope(masm(), SSE2);
     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));
   }
 }
 
 
 void LCodeGen::DoDeferredNumberTagD(LNumberTagD* instr) {
   // TODO(3095996): Get rid of this. For now, we need to make the
   // result register contain a valid pointer because it is already
   // contained in the register pointer map.
   Register reg = ToRegister(instr->result());
   __ Set(reg, Immediate(0));
@@ skipping 1438 matching lines @@
                               FixedArray::kHeaderSize - kPointerSize));
   __ bind(&done);
 }
 
 
 #undef __
 
 } }  // namespace v8::internal
 
 #endif  // V8_TARGET_ARCH_IA32