Liveness analysis for environment slots in Hydrogen

src/hydrogen.h

 // 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 49 matching lines @@
 
   // Simple accessors.
   int block_id() const { return block_id_; }
   void set_block_id(int id) { block_id_ = id; }
   HGraph* graph() const { return graph_; }
   Isolate* isolate() const;
   const ZoneList<HPhi*>* phis() const { return &phis_; }
   HInstruction* first() const { return first_; }
   HInstruction* last() const { return last_; }
   void set_last(HInstruction* instr) { last_ = instr; }
-  HInstruction* GetLastInstruction();
   HControlInstruction* end() const { return end_; }
   HLoopInformation* loop_information() const { return loop_information_; }
   const ZoneList<HBasicBlock*>* predecessors() const { return &predecessors_; }
   bool HasPredecessor() const { return predecessors_.length() > 0; }
   const ZoneList<HBasicBlock*>* dominated_blocks() const {
     return &dominated_blocks_;
   }
   const ZoneList<int>* deleted_phis() const {
     return &deleted_phis_;
   }
@@ skipping 24 matching lines @@
   bool IsFinished() const { return end_ != NULL; }
   void AddPhi(HPhi* phi);
   void RemovePhi(HPhi* phi);
   void AddInstruction(HInstruction* instr);
   bool Dominates(HBasicBlock* other) const;
   int LoopNestingDepth() const;
 
   void SetInitialEnvironment(HEnvironment* env);
   void ClearEnvironment() { last_environment_ = NULL; }
   bool HasEnvironment() const { return last_environment_ != NULL; }
-  void UpdateEnvironment(HEnvironment* env) { last_environment_ = env; }
+  void UpdateEnvironment(HEnvironment* env);
   HBasicBlock* parent_loop_header() const { return parent_loop_header_; }
 
   void set_parent_loop_header(HBasicBlock* block) {
     ASSERT(parent_loop_header_ == NULL);
     parent_loop_header_ = block;
   }
 
   bool HasParentLoopHeader() const { return parent_loop_header_ != NULL; }
 
   void SetJoinId(BailoutId ast_id);
@@ skipping 23 matching lines @@
   // instruction and updating the bailout environment.
   void AddLeaveInlined(HValue* return_value, FunctionState* state);
 
   // If a target block is tagged as an inline function return, all
   // predecessors should contain the inlined exit sequence:
   //
   // LeaveInlined
   // Simulate (caller's environment)
   // Goto (target block)
   bool IsInlineReturnTarget() const { return is_inline_return_target_; }
-  void MarkAsInlineReturnTarget() { is_inline_return_target_ = true; }
+  void MarkAsInlineReturnTarget(HBasicBlock* enter_inlined_block) {

[titzer, 2013/05/23 12:34:55]

This name is somewhat difficult to parse. Is this the first block of the inlined
method? If so, inlined_entry_block might be a better name.

[Jakob Kummerow, 2013/05/24 09:49:35]

Done. (It's the block containing the HEnterInlined. We don't start a new block
when inlining.)

+    is_inline_return_target_ = true;
+    enter_inlined_block_ = enter_inlined_block;
+  }
+  HBasicBlock* enter_inlined_block() { return enter_inlined_block_; }
 
   bool IsDeoptimizing() const { return is_deoptimizing_; }
   void MarkAsDeoptimizing() { is_deoptimizing_ = true; }
 
   bool IsLoopSuccessorDominator() const {
     return dominates_loop_successors_;
   }
   void MarkAsLoopSuccessorDominator() {
     dominates_loop_successors_ = true;
   }
@@ skipping 22 matching lines @@
   HBasicBlock* dominator_;
   ZoneList<HBasicBlock*> dominated_blocks_;
   HEnvironment* last_environment_;
   // Outgoing parameter count at block exit, set during lithium translation.
   int argument_count_;
   // Instruction indices into the lithium code stream.
   int first_instruction_index_;
   int last_instruction_index_;
   ZoneList<int> deleted_phis_;
   HBasicBlock* parent_loop_header_;
-  bool is_inline_return_target_;
-  bool is_deoptimizing_;
-  bool dominates_loop_successors_;
-  bool is_osr_entry_;
+  // For blocks marked as inline return target: the block with HEnterInlined.
+  HBasicBlock* enter_inlined_block_;
+  bool is_inline_return_target_ : 1;
+  bool is_deoptimizing_ : 1;
+  bool dominates_loop_successors_ : 1;
+  bool is_osr_entry_ : 1;
 };
 
 
 class HPredecessorIterator BASE_EMBEDDED {
  public:
   explicit HPredecessorIterator(HBasicBlock* block)
       : predecessor_list_(block->predecessors()), current_(0) { }
 
   bool Done() { return current_ >= predecessor_list_->length(); }
   HBasicBlock* Current() { return predecessor_list_->at(current_); }
@@ skipping 63 matching lines @@
   void EliminateRedundantPhis();
   void Canonicalize();
   void OrderBlocks();
   void AssignDominators();
   void SetupInformativeDefinitions();
   void EliminateRedundantBoundsChecks();
   void DehoistSimpleArrayIndexComputations();
   void RestoreActualValues();
   void DeadCodeElimination(const char *phase_name);
   void PropagateDeoptimizingMark();
+  void EnvironmentLivenessAnalysis();
 
   // Returns false if there are phi-uses of the arguments-object
   // which are not supported by the optimizing compiler.
   bool CheckArgumentsPhiUses();
 
   // Returns false if there are phi-uses of an uninitialized const
   // which are not supported by the optimizing compiler.
   bool CheckConstPhiUses();
 
   void CollectPhis();
@@ skipping 57 matching lines @@
 
   void set_osr_values(ZoneList<HUnknownOSRValue*>* values) {
     osr_values_.set(values);
   }
 
   int update_type_change_checksum(int delta) {
     type_change_checksum_ += delta;
     return type_change_checksum_;
   }
 
+  void update_biggest_environment_ever(int environment_size) {

[titzer, 2013/05/23 12:34:55]

Cute name, but "maximum_environment_size" would also work.

[Jakob Kummerow, 2013/05/24 09:49:35]

Done.

+    if (environment_size > biggest_environment_ever_) {
+      biggest_environment_ever_ = environment_size;
+    }
+  }
+
   bool use_optimistic_licm() {
     return use_optimistic_licm_;
   }
 
   void set_use_optimistic_licm(bool value) {
     use_optimistic_licm_ = value;
   }
 
   bool has_soft_deoptimize() {
     return has_soft_deoptimize_;
@@ skipping 28 matching lines @@
 
  private:
   HConstant* GetConstantInt32(SetOncePointer<HConstant>* pointer,
                               int32_t integer_value);
   HConstant* GetConstantSmi(SetOncePointer<HConstant>* pointer,
                             int32_t integer_value);
 
   void MarkLive(HValue* ref, HValue* instr, ZoneList<HValue*>* worklist);
   void MarkLiveInstructions();
   void RemoveDeadInstructions();
+  void ZapEnvironmentSlot(int index, HSimulate* simulate);

[titzer, 2013/05/23 12:34:55]

Maybe "Kill" or "Null" or "Remove"?

[Jakob Kummerow, 2013/05/24 09:49:35]

We use "zap" in other places, so I'd like to keep the name.

   void MarkAsDeoptimizingRecursively(HBasicBlock* block);
   void NullifyUnreachableInstructions();
   void InsertTypeConversions(HInstruction* instr);
   void PropagateMinusZeroChecks(HValue* value, BitVector* visited);
   void RecursivelyMarkPhiDeoptimizeOnUndefined(HPhi* phi);
   void InsertRepresentationChangeForUse(HValue* value,
                                         HValue* use_value,
                                         int use_index,
                                         Representation to);
   void InsertRepresentationChangesForValue(HValue* value);
@@ skipping 29 matching lines @@
   SetOncePointer<ZoneList<HUnknownOSRValue*> > osr_values_;
 
   CompilationInfo* info_;
   Zone* zone_;
 
   bool is_recursive_;
   bool use_optimistic_licm_;
   bool has_soft_deoptimize_;
   bool depends_on_empty_array_proto_elements_;
   int type_change_checksum_;
+  int biggest_environment_ever_;
 
   DISALLOW_COPY_AND_ASSIGN(HGraph);
 };
 
 
 Zone* HBasicBlock::zone() const { return graph_->zone(); }
 
 
 // Type of stack frame an environment might refer to.
 enum FrameType {
@@ skipping 41 matching lines @@
 
   int length() const { return values_.length(); }
   bool is_special_index(int i) const {
     return i >= parameter_count() && i < parameter_count() + specials_count();
   }
 
   int first_expression_index() const {
     return parameter_count() + specials_count() + local_count();
   }
 
+  int first_local_index() const {
+    return parameter_count() + specials_count();
+  }
+
   void Bind(Variable* variable, HValue* value) {
     Bind(IndexFor(variable), value);
   }
 
   void Bind(int index, HValue* value);
 
   void BindContext(HValue* value) {
     Bind(parameter_count(), value);
   }
 
@@ skipping 77 matching lines @@
     pop_count_ = 0;
     push_count_ = 0;
     assigned_variables_.Clear();
   }
 
   void SetValueAt(int index, HValue* value) {
     ASSERT(index < length());
     values_[index] = value;
   }
 
+  // Map a variable to an environment index.  Parameter indices are shifted
+  // by 1 (receiver is parameter index -1 but environment index 0).
+  // Stack-allocated local indices are shifted by the number of parameters.
+  int IndexFor(Variable* variable) const {
+    ASSERT(variable->IsStackAllocated());
+    int shift = variable->IsParameter()
+        ? 1
+        : parameter_count_ + specials_count_;
+    return variable->index() + shift;
+  }
+
+  bool is_local_index(int i) const {
+    return i >= first_local_index() &&
+           i < first_expression_index();
+  }
+
   void PrintTo(StringStream* stream);
   void PrintToStd();
 
   Zone* zone() const { return zone_; }
 
  private:
   HEnvironment(const HEnvironment* other, Zone* zone);
 
   HEnvironment(HEnvironment* outer,
                Handle<JSFunction> closure,
                FrameType frame_type,
                int arguments,
                Zone* zone);
 
   // Create an artificial stub environment (e.g. for argument adaptor or
   // constructor stub).
   HEnvironment* CreateStubEnvironment(HEnvironment* outer,
                                       Handle<JSFunction> target,
                                       FrameType frame_type,
                                       int arguments) const;
 
   // True if index is included in the expression stack part of the environment.
   bool HasExpressionAt(int index) const;
 
   void Initialize(int parameter_count, int local_count, int stack_height);
   void Initialize(const HEnvironment* other);
 
-  // Map a variable to an environment index.  Parameter indices are shifted
-  // by 1 (receiver is parameter index -1 but environment index 0).
-  // Stack-allocated local indices are shifted by the number of parameters.
-  int IndexFor(Variable* variable) const {
-    ASSERT(variable->IsStackAllocated());
-    int shift = variable->IsParameter()
-        ? 1
-        : parameter_count_ + specials_count_;
-    return variable->index() + shift;
-  }
-
   Handle<JSFunction> closure_;
   // Value array [parameters] [specials] [locals] [temporaries].
   ZoneList<HValue*> values_;
   GrowableBitVector assigned_variables_;
   FrameType frame_type_;
   int parameter_count_;
   int specials_count_;
   int local_count_;
   HEnvironment* outer_;
   HEnterInlined* entry_;
@@ skipping 859 matching lines @@
                           HBasicBlock* loop_successor,
                           HBasicBlock* break_block);
 
   HBasicBlock* JoinContinue(IterationStatement* statement,
                             HBasicBlock* exit_block,
                             HBasicBlock* continue_block);
 
   HValue* Top() const { return environment()->Top(); }
   void Drop(int n) { environment()->Drop(n); }
   void Bind(Variable* var, HValue* value) { environment()->Bind(var, value); }
+  bool IsEligibleForEnvironmentLivenessAnalysis(Variable* var,
+                                                int index,
+                                                HEnvironment* env) {
+    // |this| and |arguments| are always live; zapping parameters isn't
+    // safe because function.arguments can inspect them at any time.
+    return !var->is_this() &&
+           !var->is_arguments() &&
+           env->is_local_index(index);
+  }
+  void BindIfLive(Variable* var, HValue* value) {
+    HEnvironment* env = environment();
+    int index = env->IndexFor(var);
+    env->Bind(index, value);
+    if (IsEligibleForEnvironmentLivenessAnalysis(var, index, env)) {
+      AddInstruction(new(zone()) HEnvironmentBind(index));
+    }
+  }
+  HValue* LookupAndMakeLive(Variable* var) {
+    HEnvironment* env = environment();
+    int index = env->IndexFor(var);
+    HValue* value = env->Lookup(index);
+    if (IsEligibleForEnvironmentLivenessAnalysis(var, index, env)) {
+      AddInstruction(new(zone()) HEnvironmentLookup(index));
+    }
+    return value;
+  }
 
   // The value of the arguments object is allowed in some but not most value
   // contexts.  (It's allowed in all effect contexts and disallowed in all
   // test contexts.)
   void VisitForValue(Expression* expr,
                      ArgumentsAllowedFlag flag = ARGUMENTS_NOT_ALLOWED);
   void VisitForTypeOf(Expression* expr);
   void VisitForEffect(Expression* expr);
   void VisitForControl(Expression* expr,
                        HBasicBlock* true_block,
@@ skipping 477 matching lines @@
   EmbeddedVector<char, 64> filename_;
   HeapStringAllocator string_allocator_;
   StringStream trace_;
   int indent_;
 };
 
 
 } }  // namespace v8::internal
 
 #endif  // V8_HYDROGEN_H_