[turbofan] Deopt support for escape analysis

src/compiler/instruction-selector.cc

 // Copyright 2014 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "src/compiler/instruction-selector.h"
 
 #include <limits>
 
 #include "src/base/adapters.h"
 #include "src/compiler/instruction-selector-impl.h"
@@ skipping 241 matching lines @@
   rep = RepresentationOf(rep);
   sequence()->MarkAsRepresentation(rep, GetVirtualRegister(node));
 }
 
 
 namespace {
 
 enum class FrameStateInputKind { kAny, kStackSlot };
 
 
-InstructionOperand OperandForDeopt(OperandGenerator* g, Node* input,
+InstructionOperand OperandForDeopt(OperandGenerator* g, Node* node,
                                    FrameStateInputKind kind) {
-  switch (input->opcode()) {
+  switch (node->opcode()) {
     case IrOpcode::kInt32Constant:
     case IrOpcode::kNumberConstant:
     case IrOpcode::kFloat32Constant:
     case IrOpcode::kFloat64Constant:
     case IrOpcode::kHeapConstant:
-      return g->UseImmediate(input);
+      return g->UseImmediate(node);
     default:
       switch (kind) {
         case FrameStateInputKind::kStackSlot:
-          return g->UseUniqueSlot(input);
+          return g->UseUniqueSlot(node);
         case FrameStateInputKind::kAny:
-          return g->UseAny(input);
+          return g->UseAny(node);
       }
-      UNREACHABLE();
-      return InstructionOperand();
+  }
+  UNREACHABLE();
+  return InstructionOperand();
+}
+
+
+class StateObjectCache {
+ public:
+  explicit StateObjectCache(Zone* zone) : objects_(zone) {}
+  static const size_t kNotCached = SIZE_MAX;
+
+  size_t GetObjectId(Node* node) {
+    for (size_t i = 0; i < objects_.size(); ++i) {
+      if (objects_[i] == node) {
+        return i;
+      }
+    }
+    return kNotCached;
+  }
+
+  size_t InsertObject(Node* node) {
+    size_t id = objects_.size();
+    objects_.push_back(node);
+    return id;
+  }
+
+ private:
+  ZoneVector<Node*> objects_;
+};
+
+
+// Returns the number of instruction operands added to inputs.
+size_t AddOperandToStateValueDescriptor(StateValueDescriptor* desc,
+                                        InstructionOperandVector* inputs,
+                                        OperandGenerator* g,
+                                        StateObjectCache* cache, Node* input,
+                                        MachineType type,
+                                        FrameStateInputKind kind, Zone* zone) {
+  switch (input->opcode()) {
+    case IrOpcode::kObjectState: {
+      size_t id = cache->GetObjectId(input);
+      if (id == StateObjectCache::kNotCached) {
+        size_t entries = 0;
+        id = cache->InsertObject(input);
+        desc->fields().push_back(StateValueDescriptor::Recursive(zone, id));
+        StateValueDescriptor* new_desc = &desc->fields().back();
+        for (Edge edge : input->input_edges()) {
+          entries += AddOperandToStateValueDescriptor(
+              new_desc, inputs, g, cache, edge.to(), kMachAnyTagged, kind,
+              zone);
+        }
+        return entries;
+      } else {
+        desc->fields().push_back(StateValueDescriptor::Duplicate(zone, id));
+        return 0;
+      }
+      break;
+    }
+    default:
+      inputs->push_back(OperandForDeopt(g, input, kind));
+      desc->fields().push_back(StateValueDescriptor::Plain(zone, type));
+      return 1;
   }
 }
 
 
-void AddFrameStateInputs(Node* state, OperandGenerator* g,
-                         InstructionOperandVector* inputs,
-                         FrameStateDescriptor* descriptor,
-                         FrameStateInputKind kind, Zone* zone) {
+// Returns the number of instruction operands added to inputs.
+size_t AddInputsToFrameStateDescriptor(FrameStateDescriptor* desc, Node* state,
+                                       OperandGenerator* g,
+                                       StateObjectCache* cache,
+                                       InstructionOperandVector* inputs,
+                                       FrameStateInputKind kind, Zone* zone) {
   DCHECK_EQ(IrOpcode::kFrameState, state->op()->opcode());
 
-  if (descriptor->outer_state()) {
-    AddFrameStateInputs(state->InputAt(kFrameStateOuterStateInput), g, inputs,
-                        descriptor->outer_state(), kind, zone);
+  size_t entries = 0;
+  size_t initial_size = inputs->size();
+  USE(initial_size);  // initial_size is only used for debug.
+
+  if (desc->outer_state()) {
+    entries += AddInputsToFrameStateDescriptor(
+        desc->outer_state(), state->InputAt(kFrameStateOuterStateInput), g,
+        cache, inputs, kind, zone);
   }
 
   Node* parameters = state->InputAt(kFrameStateParametersInput);
   Node* locals = state->InputAt(kFrameStateLocalsInput);
   Node* stack = state->InputAt(kFrameStateStackInput);
   Node* context = state->InputAt(kFrameStateContextInput);
   Node* function = state->InputAt(kFrameStateFunctionInput);
 
-  DCHECK_EQ(descriptor->parameters_count(),
-            StateValuesAccess(parameters).size());
-  DCHECK_EQ(descriptor->locals_count(), StateValuesAccess(locals).size());
-  DCHECK_EQ(descriptor->stack_count(), StateValuesAccess(stack).size());
+  DCHECK_EQ(desc->parameters_count(), StateValuesAccess(parameters).size());
+  DCHECK_EQ(desc->locals_count(), StateValuesAccess(locals).size());
+  DCHECK_EQ(desc->stack_count(), StateValuesAccess(stack).size());
 
-  ZoneVector<MachineType> types(zone);
-  types.reserve(descriptor->GetSize());
-
-  size_t value_index = 0;
-  inputs->push_back(OperandForDeopt(g, function, kind));
-  descriptor->SetType(value_index++, kMachAnyTagged);
+  StateValueDescriptor* values_desc = desc->GetStateValueDescriptor();
+  entries += AddOperandToStateValueDescriptor(
+      values_desc, inputs, g, cache, function, kMachAnyTagged, kind, zone);
   for (StateValuesAccess::TypedNode input_node :
        StateValuesAccess(parameters)) {
-    inputs->push_back(OperandForDeopt(g, input_node.node, kind));
-    descriptor->SetType(value_index++, input_node.type);
+    entries += AddOperandToStateValueDescriptor(values_desc, inputs, g, cache,
+                                                input_node.node,
+                                                input_node.type, kind, zone);
   }
-  if (descriptor->HasContext()) {
-    inputs->push_back(OperandForDeopt(g, context, kind));
-    descriptor->SetType(value_index++, kMachAnyTagged);
+  if (desc->HasContext()) {
+    entries += AddOperandToStateValueDescriptor(
+        values_desc, inputs, g, cache, context, kMachAnyTagged, kind, zone);
   }
   for (StateValuesAccess::TypedNode input_node : StateValuesAccess(locals)) {
-    inputs->push_back(OperandForDeopt(g, input_node.node, kind));
-    descriptor->SetType(value_index++, input_node.type);
+    entries += AddOperandToStateValueDescriptor(values_desc, inputs, g, cache,
+                                                input_node.node,
+                                                input_node.type, kind, zone);
   }
   for (StateValuesAccess::TypedNode input_node : StateValuesAccess(stack)) {
-    inputs->push_back(OperandForDeopt(g, input_node.node, kind));
-    descriptor->SetType(value_index++, input_node.type);
+    entries += AddOperandToStateValueDescriptor(values_desc, inputs, g, cache,
+                                                input_node.node,
+                                                input_node.type, kind, zone);
   }
-  DCHECK(value_index == descriptor->GetSize());
+  DCHECK_EQ(initial_size + entries, inputs->size());
+  return entries;
 }
 
 }  // namespace
 
 
 // An internal helper class for generating the operands to calls.
 // TODO(bmeurer): Get rid of the CallBuffer business and make
 // InstructionSelector::VisitCall platform independent instead.
 struct CallBuffer {
   CallBuffer(Zone* zone, const CallDescriptor* descriptor,
@@ skipping 111 matching lines @@
       // The target is ignored, but we still need to pass a value here.
       buffer->instruction_args.push_back(g.UseImmediate(callee));
       break;
   }
   DCHECK_EQ(1u, buffer->instruction_args.size());
 
   // If the call needs a frame state, we insert the state information as
   // follows (n is the number of value inputs to the frame state):
   // arg 1               : deoptimization id.
   // arg 2 - arg (n + 1) : value inputs to the frame state.
+  size_t frame_state_entries = 0;
+  USE(frame_state_entries);  // frame_state_entries is only used for debug.
   if (buffer->frame_state_descriptor != NULL) {
     InstructionSequence::StateId state_id =
         sequence()->AddFrameStateDescriptor(buffer->frame_state_descriptor);
     buffer->instruction_args.push_back(g.TempImmediate(state_id.ToInt()));
 
     Node* frame_state =
         call->InputAt(static_cast<int>(buffer->descriptor->InputCount()));
-    AddFrameStateInputs(frame_state, &g, &buffer->instruction_args,
-                        buffer->frame_state_descriptor,
-                        FrameStateInputKind::kStackSlot, instruction_zone());
+
+    StateObjectCache cache(instruction_zone());
+
+    frame_state_entries =
+        1 + AddInputsToFrameStateDescriptor(
+                buffer->frame_state_descriptor, frame_state, &g, &cache,
+                &buffer->instruction_args, FrameStateInputKind::kStackSlot,
+                instruction_zone());
+
+    DCHECK_EQ(1 + frame_state_entries, buffer->instruction_args.size());
   }
-  DCHECK(1 + buffer->frame_state_value_count() ==
-         buffer->instruction_args.size());
 
   size_t input_count = static_cast<size_t>(buffer->input_count());
 
   // Split the arguments into pushed_nodes and instruction_args. Pushed
   // arguments require an explicit push instruction before the call and do
   // not appear as arguments to the call. Everything else ends up
   // as an InstructionOperand argument to the call.
   auto iter(call->inputs().begin());
   size_t pushed_count = 0;
   bool call_tail = (flags & kCallTail) != 0;
@@ skipping 15 matching lines @@
         buffer->pushed_nodes.resize(stack_index + 1, NULL);
       }
       DCHECK(!buffer->pushed_nodes[stack_index]);
       buffer->pushed_nodes[stack_index] = *iter;
       pushed_count++;
     } else {
       buffer->instruction_args.push_back(op);
     }
   }
   DCHECK_EQ(input_count, buffer->instruction_args.size() + pushed_count -
-                             buffer->frame_state_value_count());
+                             frame_state_entries);
   if (V8_TARGET_ARCH_STORES_RETURN_ADDRESS_ON_STACK && call_tail &&
       stack_param_delta != 0) {
     // For tail calls that change the size of their parameter list and keep
     // their return address on the stack, move the return address to just above
     // the parameters.
     LinkageLocation saved_return_location =
         LinkageLocation::ForSavedCallerReturnAddress();
     InstructionOperand return_address =
         g.UsePointerLocation(LinkageLocation::ConvertToTailCallerLocation(
                                  saved_return_location, stack_param_delta),
@@ skipping 185 matching lines @@
       return MarkAsReference(node), VisitConstant(node);
     case IrOpcode::kNumberConstant: {
       double value = OpParameter<double>(node);
       if (!IsSmiDouble(value)) MarkAsReference(node);
       return VisitConstant(node);
     }
     case IrOpcode::kCall:
       return VisitCall(node);
     case IrOpcode::kFrameState:
     case IrOpcode::kStateValues:
+    case IrOpcode::kObjectState:
       return;
     case IrOpcode::kLoad: {
       LoadRepresentation rep = OpParameter<LoadRepresentation>(node);
       MarkAsRepresentation(rep, node);
       return VisitLoad(node);
     }
     case IrOpcode::kStore:
       return VisitStore(node);
     case IrOpcode::kWord32And:
       return MarkAsWord32(node), VisitWord32And(node);
@@ skipping 675 matching lines @@
     }
     Emit(kArchRet, 0, nullptr, ret_count, value_locations);
   }
 }
 
 
 void InstructionSelector::VisitDeoptimize(Node* value) {
   OperandGenerator g(this);
 
   FrameStateDescriptor* desc = GetFrameStateDescriptor(value);
-  size_t arg_count = desc->GetTotalSize() + 1;  // Include deopt id.
 
   InstructionOperandVector args(instruction_zone());
-  args.reserve(arg_count);
+  args.reserve(desc->GetTotalSize() + 1);  // Include deopt id.
 
   InstructionSequence::StateId state_id =
       sequence()->AddFrameStateDescriptor(desc);
   args.push_back(g.TempImmediate(state_id.ToInt()));
 
-  AddFrameStateInputs(value, &g, &args, desc, FrameStateInputKind::kAny,
-                      instruction_zone());
+  StateObjectCache cache(instruction_zone());
 
-  DCHECK_EQ(args.size(), arg_count);
+  AddInputsToFrameStateDescriptor(desc, value, &g, &cache, &args,
+                                  FrameStateInputKind::kAny,
+                                  instruction_zone());
 
-  Emit(kArchDeoptimize, 0, nullptr, arg_count, &args.front(), 0, nullptr);
+  Emit(kArchDeoptimize, 0, nullptr, args.size(), &args.front(), 0, nullptr);
 }
 
 
 void InstructionSelector::VisitThrow(Node* value) {
   OperandGenerator g(this);
   Emit(kArchNop, g.NoOutput());  // TODO(titzer)
 }
 
 
 FrameStateDescriptor* InstructionSelector::GetFrameStateDescriptor(
@@ skipping 21 matching lines @@
   return new (instruction_zone()) FrameStateDescriptor(
       instruction_zone(), state_info.type(), state_info.bailout_id(),
       state_info.state_combine(), parameters, locals, stack,
       state_info.shared_info(), outer_state);
 }
 
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8