Improve GVN dependency tracking by adding parameters to certain flags.

src/hydrogen.cc

 // Copyright 2011 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 987 matching lines @@
 
 void TraceGVN(const char* msg, ...) {
   if (FLAG_trace_gvn) {
     va_list arguments;
     va_start(arguments, msg);
     OS::VPrint(msg, arguments);
     va_end(arguments);
   }
 }
 
+class HEffectSet: public ZoneObject {
+ public:
+  HEffectSet() : parameters_(0) {

[fschneider, 2011/03/16 15:43:28]

Since Initialize() also initializes paramters_, there is no need to mention it
in the initializer list.

+    Initialize();
+  }
+
+  explicit HEffectSet(int flags) : parameters_(0) {

[fschneider, 2011/03/16 15:43:28]

Same here.

+    Initialize();
+    AddFlags(flags);
+  }
+
+  void Initialize() {
+    flags_ = 0;
+    flags_without_parameters_ = 0;
+    parameters_.Initialize(0);
+  }
+
+  void Add(HValue* value) {
+    int flags = value->flags() & HValue::ChangesFlagsMask();
+    if (flags == 0) return;
+    if (value->CheckFlag(HValue::kHasGVNParameter)) {
+      AddWithParameter(flags, value->GetGVNParameter());
+    } else {
+      AddWithoutParameter(flags);
+    }
+  }
+
+  void AddAll(const HEffectSet& other) {
+    flags_ |= other.flags_;
+    flags_without_parameters_ |= other.flags_without_parameters_;
+    for (int i = 0; i < other.parameters_.length(); i++) {
+      int flag = i << 1;

[fschneider, 2011/03/16 15:43:28]

You could move this line to after the continue.

+      if (other.parameters_[i] == NULL) continue;
+      for (int j = 0; j < other.parameters_[i]->length(); j++) {
+        InternalAddWithParameter(flag, other.parameters_[i]->at(j));
+      }
+    }
+  }
+
+  bool HasEffectOnAny(int depends_flags) const {
+    return (HValue::ConvertDependsToChangesFlags(depends_flags) & flags_) != 0;
+  }
+
+  bool HasEffectOn(HValue* value) const {
+    ASSERT(value->CheckFlag(HValue::kUseGVN));
+    int affected_flags =
+        HValue::ConvertDependsToChangesFlags(value->flags()) & flags_;
+    if (affected_flags == 0) return false;
+    if (!value->CheckFlag(HValue::kHasGVNParameter)) return true;
+    if ((affected_flags & flags_without_parameters_) != 0) return true;
+    // Only a single GVN flag can be set when we have a parameter
+    // (with a possible exception of the special OsrEntries flag).
+    affected_flags &= ~(1 << HValue::kChangesOsrEntries);
+    ASSERT(IsPowerOf2(affected_flags));
+    for (int i = 0; i < parameters_.length(); i++) {
+      int flag = i << 1;
+      if (((1 << flag) & affected_flags) != 0) {
+        if (parameters_[i] == NULL) return true;
+        return parameters_[i]->Contains(value->GetGVNParameter());
+      }
+    }
+    return true;
+  }
+
+  int flags() const { return flags_; }
+
+ private:
+  typedef ZoneList<intptr_t> ParameterList;
+
+  static const int kParameterListLengthLimit = 8;
+
+  void AddWithoutParameter(int flags) {
+    AddFlags(flags);
+    flags_without_parameters_ |= flags;
+  }
+
+  void AddWithParameter(int flags, intptr_t parameter) {
+    AddFlags(flags);
+    if ((flags_without_parameters_ & flags) != 0) return;
+    int flag = -1;
+    for (int i = 0; i < HValue::kFirstNonGVNFlag; i += 2) {
+      if ((flags & (1 << i)) != 0) {
+        flag = i;
+        break;
+      }
+    }
+    ASSERT(flag != -1);
+    ASSERT(flags == (1 << flag));
+    InternalAddWithParameter(flag, parameter);
+  }
+
+  void InternalAddWithParameter(int flag, intptr_t parameter) {
+    int flag_index = flag >> 1;
+    ASSERT(flag == (flag_index << 1));
+    if (parameters_.length() <= flag_index) {

[fschneider, 2011/03/16 15:43:28]

I find (flag_index >= parameters_.length()) better.

+      parameters_.AddBlock(NULL, flag_index - parameters_.length() + 1);
+    }
+    if (parameters_[flag_index] == NULL) {
+      parameters_[flag_index] = new ParameterList(2);
+    } else if (parameters_[flag_index]->Contains(parameter)) {
+      return;
+    }
+    if (parameters_[flag_index]->length() == kParameterListLengthLimit) {
+      // Too many parameters to track efficiently.
+      parameters_[flag_index] = NULL;
+      flags_without_parameters_ |= (1 << flag);
+      return;
+    }
+    parameters_[flag_index]->Add(parameter);
+  }
+
+  void AddFlags(int flags) {
+    ASSERT((flags & HValue::ChangesFlagsMask()) == flags);
+    flags_ |= flags;
+  }
+
+  int flags_;
+  int flags_without_parameters_;
+  ZoneList<ParameterList*> parameters_;
+
+  DISALLOW_COPY_AND_ASSIGN(HEffectSet);
+};
+
 
 HValueMap::HValueMap(const HValueMap* other)
     : array_size_(other->array_size_),
       lists_size_(other->lists_size_),
       count_(other->count_),
       present_flags_(other->present_flags_),
       array_(Zone::NewArray<HValueMapListElement>(other->array_size_)),
       lists_(Zone::NewArray<HValueMapListElement>(other->lists_size_)),
       free_list_head_(other->free_list_head_) {
   memcpy(array_, other->array_, array_size_ * sizeof(HValueMapListElement));
   memcpy(lists_, other->lists_, lists_size_ * sizeof(HValueMapListElement));
 }
 
 
-void HValueMap::Kill(int flags) {
-  int depends_flags = HValue::ConvertChangesToDependsFlags(flags);
-  if ((present_flags_ & depends_flags) == 0) return;
+void HValueMap::Kill(const HEffectSet& effects) {
+  if (!effects.HasEffectOnAny(present_flags_)) return;
   present_flags_ = 0;
   for (int i = 0; i < array_size_; ++i) {
     HValue* value = array_[i].value;
     if (value != NULL) {
       // Clear list of collisions first, so we know if it becomes empty.
       int kept = kNil;  // List of kept elements.
       int next;
       for (int current = array_[i].next; current != kNil; current = next) {
         next = lists_[current].next;
-        if ((lists_[current].value->flags() & depends_flags) != 0) {
+        if (effects.HasEffectOn(lists_[current].value)) {
           // Drop it.
           count_--;
           lists_[current].next = free_list_head_;
           free_list_head_ = current;
         } else {
           // Keep it.
           lists_[current].next = kept;
           kept = current;
           present_flags_ |= lists_[current].value->flags();
         }
       }
       array_[i].next = kept;
 
       // Now possibly drop directly indexed element.
-      if ((array_[i].value->flags() & depends_flags) != 0) {  // Drop it.
+      if (effects.HasEffectOn(array_[i].value)) {
         count_--;
         int head = array_[i].next;
         if (head == kNil) {
           array_[i].value = NULL;
         } else {
           array_[i].value = lists_[head].value;
           array_[i].next = lists_[head].next;
           lists_[head].next = free_list_head_;
           free_list_head_ = head;
         }
@@ skipping 160 matching lines @@
       HGoto::cast(instr)->set_include_stack_check(false);
       return;
     }
     instr = instr->next();
   }
 }
 
 
 class HGlobalValueNumberer BASE_EMBEDDED {
  public:
-  explicit HGlobalValueNumberer(HGraph* graph, CompilationInfo* info)
-      : graph_(graph),
-        info_(info),
-        block_side_effects_(graph_->blocks()->length()),
-        loop_side_effects_(graph_->blocks()->length()) {
+  HGlobalValueNumberer(HGraph* graph, CompilationInfo* info)
+      : graph_(graph), info_(info) {
     ASSERT(Heap::allow_allocation(false));
-    block_side_effects_.AddBlock(0, graph_->blocks()->length());
-    loop_side_effects_.AddBlock(0, graph_->blocks()->length());
+    int length = graph_->blocks()->length();
+    block_side_effects_ = Zone::NewArray<HEffectSet>(length);
+    loop_side_effects_ = Zone::NewArray<HEffectSet>(length);
+    for (int i = 0; i < length; i++) {
+      block_side_effects_[i].Initialize();
+      loop_side_effects_[i].Initialize();
+    }
   }
+
   ~HGlobalValueNumberer() {
     ASSERT(!Heap::allow_allocation(true));
   }
 
   void Analyze();
 
  private:
   void AnalyzeBlock(HBasicBlock* block, HValueMap* map);
   void ComputeBlockSideEffects();
   void LoopInvariantCodeMotion();
   void ProcessLoopBlock(HBasicBlock* block,
                         HBasicBlock* before_loop,
-                        int loop_kills);
+                        const HEffectSet& loop_effects);
   bool AllowCodeMotion();
   bool ShouldMove(HInstruction* instr, HBasicBlock* loop_header);
 
   HGraph* graph() { return graph_; }
   CompilationInfo* info() { return info_; }
 
   HGraph* graph_;
   CompilationInfo* info_;
 
-  // A map of block IDs to their side effects.
-  ZoneList<int> block_side_effects_;
+  // An array mapping block IDs to their side effects.
+  HEffectSet* block_side_effects_;
 
-  // A map of loop header block IDs to their loop's side effects.
-  ZoneList<int> loop_side_effects_;
+  // An array mapping loop header block IDs to their loop's side effects.
+  HEffectSet* loop_side_effects_;
 };
 
 
 void HGlobalValueNumberer::Analyze() {
   ComputeBlockSideEffects();
   if (FLAG_loop_invariant_code_motion) {
     LoopInvariantCodeMotion();
   }
   HValueMap* map = new HValueMap();
   AnalyzeBlock(graph_->blocks()->at(0), map);
 }
 
 
 void HGlobalValueNumberer::ComputeBlockSideEffects() {
   for (int i = graph_->blocks()->length() - 1; i >= 0; --i) {
     // Compute side effects for the block.
     HBasicBlock* block = graph_->blocks()->at(i);
     HInstruction* instr = block->first();
     int id = block->block_id();
-    int side_effects = 0;
-    while (instr != NULL) {
-      side_effects |= (instr->flags() & HValue::ChangesFlagsMask());
-      instr = instr->next();
-    }
-    block_side_effects_[id] |= side_effects;
+    HEffectSet* block_effects = &block_side_effects_[id];
 
     // Loop headers are part of their loop.
-    if (block->IsLoopHeader()) {
-      loop_side_effects_[id] |= side_effects;
+    HEffectSet* loop_effects =
+        block->IsLoopHeader() ? &loop_side_effects_[id] : NULL;
+
+    while (instr != NULL) {
+      block_effects->Add(instr);
+      if (loop_effects != NULL) loop_effects->Add(instr);
+      instr = instr->next();
     }
 
     // Propagate loop side effects upwards.
     if (block->HasParentLoopHeader()) {
       int header_id = block->parent_loop_header()->block_id();
-      loop_side_effects_[header_id] |=
-          block->IsLoopHeader() ? loop_side_effects_[id] : side_effects;
+      loop_side_effects_[header_id].AddAll(
+          block->IsLoopHeader() ? *loop_effects : *block_effects);
     }
   }
 }
 
 
 void HGlobalValueNumberer::LoopInvariantCodeMotion() {
   for (int i = graph_->blocks()->length() - 1; i >= 0; --i) {
     HBasicBlock* block = graph_->blocks()->at(i);
     if (block->IsLoopHeader()) {
-      int side_effects = loop_side_effects_[block->block_id()];
+      const HEffectSet& loop_effects = loop_side_effects_[block->block_id()];
       TraceGVN("Try loop invariant motion for block B%d effects=0x%x\n",
                block->block_id(),
-               side_effects);
+               loop_effects.flags());
 
       HBasicBlock* last = block->loop_information()->GetLastBackEdge();
       for (int j = block->block_id(); j <= last->block_id(); ++j) {
-        ProcessLoopBlock(graph_->blocks()->at(j), block, side_effects);
+        ProcessLoopBlock(graph_->blocks()->at(j), block, loop_effects);
       }
     }
   }
 }
 
 
 void HGlobalValueNumberer::ProcessLoopBlock(HBasicBlock* block,
                                             HBasicBlock* loop_header,
-                                            int loop_kills) {
+                                            const HEffectSet& loop_effects) {
   HBasicBlock* pre_header = loop_header->predecessors()->at(0);
-  int depends_flags = HValue::ConvertChangesToDependsFlags(loop_kills);
   TraceGVN("Loop invariant motion for B%d depends_flags=0x%x\n",
            block->block_id(),
-           depends_flags);
+           loop_effects.flags());
   HInstruction* instr = block->first();
   while (instr != NULL) {
     HInstruction* next = instr->next();
     if (instr->CheckFlag(HValue::kUseGVN) &&
-        (instr->flags() & depends_flags) == 0) {
+        !loop_effects.HasEffectOn(instr)) {
       TraceGVN("Checking instruction %d (%s)\n",
                instr->id(),
                instr->Mnemonic());
       bool inputs_loop_invariant = true;
       for (int i = 0; i < instr->OperandCount(); ++i) {
         if (instr->OperandAt(i)->IsDefinedAfter(pre_header)) {
           inputs_loop_invariant = false;
         }
       }
 
@@ skipping 59 matching lines @@
   }
 
   // Go through all instructions of the current block.
   HInstruction* instr = block->first();
   while (instr != NULL) {
     HInstruction* next = instr->next();
     int flags = (instr->flags() & HValue::ChangesFlagsMask());
     if (flags != 0) {
       ASSERT(!instr->CheckFlag(HValue::kUseGVN));
       // Clear all instructions in the map that are affected by side effects.
-      map->Kill(flags);
+      HEffectSet effects(flags);
+      map->Kill(effects);
       TraceGVN("Instruction %d kills\n", instr->id());
     } else if (instr->CheckFlag(HValue::kUseGVN)) {
       HValue* other = map->Lookup(instr);
       if (other != NULL) {
         ASSERT(instr->Equals(other) && other->Equals(instr));
         TraceGVN("Replacing value %d (%s) with value %d (%s)\n",
                  instr->id(),
                  instr->Mnemonic(),
                  other->id(),
                  other->Mnemonic());
@@ skipping 15 matching lines @@
     // If the dominated block is not a successor to this block we have to
     // kill everything killed on any path between this block and the
     // dominated block.  Note we rely on the block ordering.
     bool is_successor = false;
     int predecessor_count = dominated->predecessors()->length();
     for (int j = 0; !is_successor && j < predecessor_count; ++j) {
       is_successor = (dominated->predecessors()->at(j) == block);
     }
 
     if (!is_successor) {
-      int side_effects = 0;
+      HEffectSet side_effects;
       for (int j = block->block_id() + 1; j < dominated->block_id(); ++j) {
-        side_effects |= block_side_effects_[j];
+        side_effects.AddAll(block_side_effects_[j]);
       }
       successor_map->Kill(side_effects);
     }
 
     AnalyzeBlock(dominated, successor_map);
   }
 }
 
 
 class HInferRepresentation BASE_EMBEDDED {
@@ skipping 1561 matching lines @@
     // Negative property indices are in-object properties, indexed
     // from the end of the fixed part of the object.
     offset += type->instance_size();
   } else {
     offset += FixedArray::kHeaderSize;
   }
   HStoreNamedField* instr =
       new HStoreNamedField(object, name, value, is_in_object, offset);
   if (lookup->type() == MAP_TRANSITION) {
     Handle<Map> transition(lookup->GetTransitionMapFromMap(*type));
-    instr->set_transition(transition);
-    // TODO(fschneider): Record the new map type of the object in the IR to
-    // enable elimination of redundant checks after the transition store.
-    instr->SetFlag(HValue::kChangesMaps);
+    instr->SetTransition(transition);
   }
   return instr;
 }
 
 
 HInstruction* HGraphBuilder::BuildStoreNamedGeneric(HValue* object,
                                                     Handle<String> name,
                                                     HValue* value) {
   HContext* context = new HContext;
   AddInstruction(context);
@@ skipping 2853 matching lines @@
     }
   }
 
 #ifdef DEBUG
   if (graph_ != NULL) graph_->Verify();
   if (allocator_ != NULL) allocator_->Verify();
 #endif
 }
 
 } }  // namespace v8::internal