Implement basic array prefetching hints in Hydrogen.

src/hydrogen.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 1463 matching lines @@
           free_list_head_ = head;
         }
       } else {
         present_flags_.Add(value->gvn_flags());  // Keep it.
       }
     }
   }
 }
 
 
+void HValueMap::KillAll() {
+  present_flags_.RemoveAll();
+
+  if (count_ == 0) return;
+
+  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 next;
+      for (int current = array_[i].next; current != kNil; current = next) {
+        next = lists_[current].next;
+        // Drop it.
+        count_--;
+        lists_[current].next = free_list_head_;
+        free_list_head_ = current;
+      }
+      array_[i].next = kNil;
+
+      // Now drop directly indexed element.
+      count_--;
+      array_[i].value = NULL;
+    }
+  }
+  ASSERT(count_ == 0);
+}
+
+
 HValue* HValueMap::Lookup(HValue* value) const {
   uint32_t hash = static_cast<uint32_t>(value->Hashcode());
   uint32_t pos = Bound(hash);
   if (array_[pos].value != NULL) {
     if (array_[pos].value->Equals(value)) return array_[pos].value;
     int next = array_[pos].next;
     while (next != kNil) {
       if (lists_[next].value->Equals(value)) return lists_[next].value;
       next = lists_[next].next;
     }
@@ skipping 743 matching lines @@
                                                       dominated);
         successor_map->Kill(side_effects_on_all_paths);
         successor_dominators->Kill(side_effects_on_all_paths);
       }
     }
     current = next;
   }
 }
 
 
+class HArrayPrefetchHint BASE_EMBEDDED {
+ public:
+  explicit HArrayPrefetchHint(HGraph* graph) :
+      graph_(graph), zone_(graph->zone()), induction_vars_(4, zone_) {
+    value_map_ = new(zone_) HValueMap(zone_);
+  }
+
+  void Analyze();
+
+ private:
+  class HIntInductionVar {
+   public:
+    HIntInductionVar(HValue* value, int32_t step)
+        : value_(value), step_(step) { }
+
+    HValue* value_;
+    int32_t step_;
+  };
+
+  void TraceArrayPrefetchHint(const char* msg, ...);
+  HValue* LookupOrInsert(HValue* value, HInstruction* insert_place);
+  void ProcessLoopBlock(HBasicBlock* block, HBasicBlock* loop_header);
+  bool AnalyzeInductionVars(HBasicBlock* loop_header);
+  bool IsInductionVar(HValue* value, int32_t* step);
+
+  HGraph* graph_;
+  Zone* zone_;
+  HValueMap* value_map_;
+  // A "conservative" list of the integer induction vars in the processed loop.
+  ZoneList<HIntInductionVar> induction_vars_;
+};
+
+
+void HArrayPrefetchHint::TraceArrayPrefetchHint(const char* msg, ...) {
+  if (FLAG_trace_prefetch_hint) {
+    va_list arguments;
+    va_start(arguments, msg);
+    OS::VPrint(msg, arguments);
+    va_end(arguments);
+  }
+}
+
+
+// Implement a naive CSE for the newly generated instructions during the
+// Array prefetch hint phase which is performed after GVN/LICM because
+// it depends on LICM to generate more "obvious" loop invariants.
+// Alternatively, if we perform the array prefetch hint phase before GVN/LICM,
+// we don't need this trick but we may be not catching some cases with
+// non-obvious loop invariants, as we don't want to perform similar expensive
+// analysis as LICM does.
+// Performing iterative GVN (like GVN->Array prefetch hints->GVN) is too
+// overkill to be considered.
+HValue* HArrayPrefetchHint::LookupOrInsert(HValue* value,
+    HInstruction* insert_place) {
+  ASSERT(value->IsInstruction());
+  HValue* cached = value_map_->Lookup(value);
+  if (cached == NULL) {
+    HInstruction* instr = HInstruction::cast(value);
+    instr->InsertBefore(insert_place);
+    value_map_->Add(instr, zone_);
+    cached = value;
+  }
+  return cached;
+}
+
+
+bool HArrayPrefetchHint::IsInductionVar(HValue* value, int32_t* step) {
+  for (int i = 0; i < induction_vars_.length(); i++) {
+    if (induction_vars_[i].value_ == value) {
+      *step = induction_vars_[i].step_;
+      return true;
+    }
+  }
+  return false;
+}
+
+
+bool HArrayPrefetchHint::AnalyzeInductionVars(HBasicBlock* loop_header) {
+  induction_vars_.Clear();
+
+  HBasicBlock* pre_header = loop_header->predecessors()->at(0);
+  for (int i = 0; i < loop_header->phis()->length(); i++) {
+    HPhi* phi = loop_header->phis()->at(i);
+    // Only consider the obvious induction variables because
+    // we really don't want to perform expensive analysis here.
+    if (phi->OperandCount() == 2 &&
+        !phi->OperandAt(0)->IsDefinedAfter(pre_header) &&
+        phi->representation().IsInteger32()) {
+      HValue* var_update = phi->OperandAt(1);
+      // We only consider the "linear" integer induction variable for now.
+      if (var_update->IsAdd() || var_update->IsSub()) {
+        HValue* left_value = HBinaryOperation::cast(var_update)->left();
+        HValue* right_value = HBinaryOperation::cast(var_update)->right();
+        int32_t step_value = 0;
+
+        if (left_value == phi && right_value->IsConstant()) {
+          // The most common cases, like "i++" or "i--".
+          step_value = HConstant::cast(right_value)->Integer32Value();
+          if (var_update->IsSub()) step_value = -step_value;
+        } else if (var_update->IsAdd() &&
+            left_value->IsConstant() && right_value == phi) {
+          // Abnormal things like "i = 1 + i".
+          step_value = HConstant::cast(left_value)->Integer32Value();
+        }
+
+        if (step_value != 0) {
+          induction_vars_.Add(HIntInductionVar(phi, step_value), zone_);
+          TraceArrayPrefetchHint(
+              "Found linear integer induction variable for B%d: %d, step: %d\n",
+              loop_header->block_id(), phi->id(), step_value);
+        }
+      }
+    }
+  }
+
+  return (induction_vars_.length() > 0);
+}
+
+
+void HArrayPrefetchHint::ProcessLoopBlock(
+    HBasicBlock* block, HBasicBlock* loop_header) {
+
+  TraceArrayPrefetchHint("Array prefetch hint for B%d\n",
+              block->block_id());
+
+  HBasicBlock* pre_header = loop_header->predecessors()->at(0);
+  HInstruction* instr = block->first();
+  while (instr != NULL) {
+    HInstruction* next = instr->next();
+    // TODO(yxian): Probably use a kUseArrayPrefetchHint flag if there are
+    // other kinds of instructions to be taken in.
+    if (instr->IsLoadKeyed()) {
+      int32_t step_value = 0;
+      TraceArrayPrefetchHint("Checking instruction %d (%s)\n",
+                  instr->id(),
+                  instr->Mnemonic());
+      HValue* key = HLoadKeyed::cast(instr)->key();
+      if (key->IsBoundsCheck()) key = HBoundsCheck::cast(key)->index();
+      HValue* prefetch_distance = NULL;
+      bool new_instr = true;
+      if (IsInductionVar(key, &step_value)) {
+        prefetch_distance = new(zone_)
+            HConstant(step_value, Representation::Integer32());
+      } else if (key->representation().IsInteger32() &&
+          (key->IsAdd() || key->IsSub() || key->IsMul() || key->IsDiv())) {
+        HBinaryOperation* arith = HBinaryOperation::cast(key);
+        HValue* left = arith->left();
+        HValue* right = arith->right();
+        HValue* invariant = NULL;
+
+        if (IsInductionVar(left, &step_value) &&
+            !right->IsDefinedAfter(pre_header)) {
+          invariant = right;
+        } else if (IsInductionVar(right, &step_value) &&
+            !left->IsDefinedAfter(pre_header)) {
+          invariant = left;
+        }
+
+        if (invariant != NULL) {
+          if (key->IsAdd()) {
+            prefetch_distance = new(zone_)
+                HConstant(step_value, Representation::Integer32());
+          } else if (key->IsSub()) {
+            int32_t distance = invariant == left ? -step_value : step_value;
+            prefetch_distance = new(zone_)
+                HConstant(distance, Representation::Integer32());
+          } else if (key->IsMul()) {
+            // If the step_value is 1, we should just use the
+            // "invariant" as the distance instead of creating new instr.
+            if (step_value == 1) {
+              prefetch_distance = invariant;
+              new_instr = false;
+            } else if (invariant->IsConstant()) {
+              prefetch_distance = new(zone_) HConstant(
+                  step_value * HConstant::cast(invariant)->Integer32Value(),
+                  Representation::Integer32());
+            } else {
+              HValue* step = new(zone_)
+                  HConstant(step_value, Representation::Integer32());
+              step = LookupOrInsert(step, pre_header->end());
+              prefetch_distance = new(zone_)
+                  HMul(arith->context(), invariant, step);
+              // This is definitely an integer32. As we perform this phase
+              // after the representation inference phase, we need to specify
+              // it explicitly.
+              prefetch_distance->
+                  ChangeRepresentation(Representation::Integer32());
+            }
+          }
+        }
+      }
+
+      if (prefetch_distance != NULL) {
+        if (new_instr) {
+          prefetch_distance = LookupOrInsert(
+              prefetch_distance, pre_header->end());
+        }
+
+        TraceArrayPrefetchHint(
+            "Inserting array prefetching hint for instruction %d: %d\n",
+            instr->id(), prefetch_distance->id());
+        HLoadKeyed::cast(instr)->SetPrefetchDistance(prefetch_distance);
+      }
+    }
+    instr = next;
+  }
+}
+
+
+void HArrayPrefetchHint::Analyze() {
+  HPhase phase("H_Insert Array prefetching hints", graph_);
+
+  for (int i = 0; i < graph_->blocks()->length(); ++i) {
+    HBasicBlock* block = graph_->blocks()->at(i);
+    if (block->IsLoopHeader() && AnalyzeInductionVars(block)) {
+      TraceArrayPrefetchHint("Try array prefetch hint for block B%d\n",
+                  block->block_id());
+      value_map_->KillAll();
+      HBasicBlock* last = block->loop_information()->GetLastBackEdge();
+      for (int j = block->block_id(); j <= last->block_id(); ++j) {
+        ProcessLoopBlock(graph_->blocks()->at(j), block);
+      }
+    }
+  }
+}
+
+
 void HInferRepresentation::AddToWorklist(HValue* current) {
   if (current->representation().IsTagged()) return;
   if (!current->CheckFlag(HValue::kFlexibleRepresentation)) return;
   if (in_worklist_.Contains(current->id())) return;
   worklist_.Add(current, zone());
   in_worklist_.Add(current->id());
 }
 
 
 void HInferRepresentation::Analyze() {
@@ skipping 1052 matching lines @@
     bool removed_side_effects = gvn.Analyze();
     // Trigger a second analysis pass to further eliminate duplicate values that
     // could only be discovered by removing side-effect-generating instructions
     // during the first pass.
     if (FLAG_smi_only_arrays && removed_side_effects) {
       removed_side_effects = gvn.Analyze();
       ASSERT(!removed_side_effects);
     }
   }
 
+  if (FLAG_array_prefetch_hint) {
+    HArrayPrefetchHint arrayPrefetchHint(this);
+    arrayPrefetchHint.Analyze();
+  }
+
   if (FLAG_use_range) {
     HRangeAnalysis rangeAnalysis(this);
     rangeAnalysis.Analyze();
   }
   ComputeMinusZeroChecks();
 
   // Eliminate redundant stack checks on backwards branches.
   HStackCheckEliminator sce(this);
   sce.Process();
 
@@ skipping 1241 matching lines @@
   set_current_block(loop_successor);
   Drop(5);
 
   set_current_block(loop_body);
 
   HValue* key = AddInstruction(
       new(zone()) HLoadKeyed(
           environment()->ExpressionStackAt(2),  // Enum cache.
           environment()->ExpressionStackAt(0),  // Iteration index.
           environment()->ExpressionStackAt(0),
+          graph()->GetConstantUndefined(),
           FAST_ELEMENTS));
 
   // Check if the expected map still matches that of the enumerable.
   // If not just deoptimize.
   AddInstruction(new(zone()) HCheckMapValue(
       environment()->ExpressionStackAt(4),
       environment()->ExpressionStackAt(3)));
 
   Bind(each_var, key);
 
@@ skipping 1463 matching lines @@
         break;
     }
     return new(zone()) HStoreKeyed(external_elements,
                                    checked_key,
                                    val,
                                    elements_kind);
   } else {
     ASSERT(val == NULL);
     HLoadKeyed* load =
        new(zone()) HLoadKeyed(
-           external_elements, checked_key, dependency, elements_kind);
+           external_elements, checked_key, dependency,
+           graph()->GetConstantUndefined(), elements_kind);
     if (FLAG_opt_safe_uint32_operations &&
         elements_kind == EXTERNAL_UNSIGNED_INT_ELEMENTS) {
       graph()->RecordUint32Instruction(load);
     }
     return load;
   }
 }
 
 
 HInstruction* HGraphBuilder::BuildFastElementAccess(HValue* elements,
@@ skipping 18 matching lines @@
             elements, checked_key, val, elements_kind);
       default:
         UNREACHABLE();
         return NULL;
     }
   }
   // It's an element load (!is_store).
   return new(zone()) HLoadKeyed(elements,
                                 checked_key,
                                 load_dependency,
+                                graph()->GetConstantUndefined(),
                                 elements_kind);
 }
 
 
 HInstruction* HGraphBuilder::BuildMonomorphicElementAccess(HValue* object,
                                                            HValue* key,
                                                            HValue* val,
                                                            HValue* dependency,
                                                            Handle<Map> map,
                                                            bool is_store) {
@@ skipping 3947 matching lines @@
     }
   }
 
 #ifdef DEBUG
   if (graph_ != NULL) graph_->Verify(false);  // No full verify.
   if (allocator_ != NULL) allocator_->Verify();
 #endif
 }
 
 } }  // namespace v8::internal