Make the array bounds check elimination phase optional (and set the foundation for introducing SSI …

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 725 matching lines @@
 }
 
 
 HInstruction* HGraphBuilder::BuildUncheckedMonomorphicElementAccess(
     HValue* object,
     HValue* key,
     HValue* val,
     HCheckMaps* mapcheck,
     bool is_js_array,
     ElementsKind elements_kind,
-    bool is_store) {
+    bool is_store,
+    Representation checked_index_representation) {
   Zone* zone = this->zone();
   // No GVNFlag is necessary for ElementsKind if there is an explicit dependency
   // on a HElementsTransition instruction. The flag can also be removed if the
   // map to check has FAST_HOLEY_ELEMENTS, since there can be no further
   // ElementsKind transitions. Finally, the dependency can be removed for stores
   // for FAST_ELEMENTS, since a transition to HOLEY elements won't change the
   // generated store code.
   if ((elements_kind == FAST_HOLEY_ELEMENTS) ||
       (elements_kind == FAST_ELEMENTS && is_store)) {
     if (mapcheck != NULL) {
       mapcheck->ClearGVNFlag(kDependsOnElementsKind);
     }
   }
   bool fast_smi_only_elements = IsFastSmiElementsKind(elements_kind);
   bool fast_elements = IsFastObjectElementsKind(elements_kind);
   HInstruction* elements =
       AddInstruction(new(zone) HLoadElements(object, mapcheck));
   if (is_store && (fast_elements || fast_smi_only_elements)) {
     HCheckMaps* check_cow_map = new(zone) HCheckMaps(
         elements, Isolate::Current()->factory()->fixed_array_map(), zone);
     check_cow_map->ClearGVNFlag(kDependsOnElementsKind);
     AddInstruction(check_cow_map);
   }
   HInstruction* length = NULL;
   HInstruction* checked_key = NULL;
   if (IsExternalArrayElementsKind(elements_kind)) {
     length = AddInstruction(new(zone) HFixedArrayBaseLength(elements));
-    checked_key = AddInstruction(new(zone) HBoundsCheck(key, length,
-                                                        ALLOW_SMI_KEY));
+    checked_key = AddInstruction(new(zone) HBoundsCheck(
+        key, length, ALLOW_SMI_KEY, checked_index_representation));
     HLoadExternalArrayPointer* external_elements =
         new(zone) HLoadExternalArrayPointer(elements);
     AddInstruction(external_elements);
     return BuildExternalArrayElementAccess(
         external_elements, checked_key, val, mapcheck,
         elements_kind, is_store);
   }
   ASSERT(fast_smi_only_elements ||
          fast_elements ||
          IsFastDoubleElementsKind(elements_kind));
   if (is_js_array) {
     length = AddInstruction(new(zone) HJSArrayLength(object, mapcheck,
                                                      HType::Smi()));
   } else {
     length = AddInstruction(new(zone) HFixedArrayBaseLength(elements));
   }
-  checked_key = AddInstruction(new(zone) HBoundsCheck(key, length,
-                                                      ALLOW_SMI_KEY));
+  checked_key = AddInstruction(new(zone) HBoundsCheck(
+      key, length, ALLOW_SMI_KEY, checked_index_representation));
   return BuildFastElementAccess(elements, checked_key, val, mapcheck,
                                 elements_kind, is_store);
 }
 
 
 HOptimizedGraphBuilder::HOptimizedGraphBuilder(CompilationInfo* info,
                                                TypeFeedbackOracle* oracle)
     : HGraphBuilder(info),
       function_state_(NULL),
       initial_function_state_(this, info, oracle, NORMAL_RETURN),
@@ skipping 2692 matching lines @@
   if (FLAG_use_range) {
     HRangeAnalysis rangeAnalysis(this);
     rangeAnalysis.Analyze();
   }
   ComputeMinusZeroChecks();
 
   // Eliminate redundant stack checks on backwards branches.
   HStackCheckEliminator sce(this);
   sce.Process();
 
-  EliminateRedundantBoundsChecks();
-  DehoistSimpleArrayIndexComputations();
+  if (FLAG_array_bounds_checks_elimination) EliminateRedundantBoundsChecks();
+  if (FLAG_array_index_dehoisting) DehoistSimpleArrayIndexComputations();
   if (FLAG_dead_code_elimination) DeadCodeElimination();
 
+  ApplyActualValues();
+
   return true;
 }
 
 
 // We try to "factor up" HBoundsCheck instructions towards the root of the
 // dominator tree.
 // For now we handle checks where the index is like "exp + int32value".
 // If in the dominator tree we check "exp + v1" and later (dominated)
 // "exp + v2", if v2 <= v1 we can safely remove the second check, and if
 // v2 > v1 we can use v2 in the 1st check and again remove the second.
@@ skipping 139 matching lines @@
                                      new_check->index()->representation(),
                                      new_offset);
         if (!result) return false;
         lower_check_->SetOperandAt(0, added_lower_index_);
       }
     } else {
       ASSERT(false);
     }
 
     if (!keep_new_check) {
-      new_check->DeleteAndReplaceWith(NULL);
+      new_check->DeleteAndReplaceWith(new_check->ActualValue());
     }
 
     return true;
   }
 
   void RemoveZeroOperations() {
     RemoveZeroAdd(&added_lower_index_, &added_lower_offset_);
     RemoveZeroAdd(&added_upper_index_, &added_upper_offset_);
   }
 
@@ skipping 115 matching lines @@
 // this point. It enables better register allocation since the value produced
 // by check instructions is really a copy of the original value.
 void HGraph::EliminateRedundantBoundsChecks(HBasicBlock* bb,
                                             BoundsCheckTable* table) {
   BoundsCheckBbData* bb_data_list = NULL;
 
   for (HInstruction* i = bb->first(); i != NULL; i = i->next()) {
     if (!i->IsBoundsCheck()) continue;
 
     HBoundsCheck* check = HBoundsCheck::cast(i);
-    check->ReplaceAllUsesWith(check->index());
-
-    if (!FLAG_array_bounds_checks_elimination) continue;
-
     int32_t offset;
     BoundsCheckKey* key =
         BoundsCheckKey::Create(zone(), check, &offset);
     if (key == NULL) continue;
     BoundsCheckBbData** data_p = table->LookupOrInsert(key, zone());
     BoundsCheckBbData* data = *data_p;
     if (data == NULL) {
       bb_data_list = new(zone()) BoundsCheckBbData(key,
                                                    offset,
                                                    offset,
                                                    bb,
                                                    check,
                                                    check,
                                                    bb_data_list,
                                                    NULL);
       *data_p = bb_data_list;
     } else if (data->OffsetIsCovered(offset)) {
-      check->DeleteAndReplaceWith(NULL);
+      check->DeleteAndReplaceWith(check->ActualValue());
     } else if (data->BasicBlock() != bb ||
                !data->CoverCheck(check, offset)) {
       // If the check is in the current BB we try to modify it by calling
       // "CoverCheck", but if also that fails we record the current offsets
       // in a new data instance because from now on they are covered.
       int32_t new_lower_offset = offset < data->LowerOffset()
           ? offset
           : data->LowerOffset();
       int32_t new_upper_offset = offset > data->UpperOffset()
           ? offset
@@ skipping 76 matching lines @@
   if (index->HasNoUses()) {
     index->DeleteAndReplaceWith(NULL);
   }
   ASSERT(value >= 0);
   array_operation->SetIndexOffset(static_cast<uint32_t>(value));
   array_operation->SetDehoisted(true);
 }
 
 
 void HGraph::DehoistSimpleArrayIndexComputations() {
-  if (!FLAG_array_index_dehoisting) return;
-
   HPhase phase("H_Dehoist index computations", this);
   for (int i = 0; i < blocks()->length(); ++i) {
     for (HInstruction* instr = blocks()->at(i)->first();
         instr != NULL;
         instr = instr->next()) {
       ArrayInstructionInterface* array_instruction = NULL;
       if (instr->IsLoadKeyed()) {
         HLoadKeyed* op = HLoadKeyed::cast(instr);
         array_instruction = static_cast<ArrayInstructionInterface*>(op);
       } else if (instr->IsStoreKeyed()) {
@@ skipping 31 matching lines @@
     }
     instr->DeleteAndReplaceWith(NULL);
     for (int i = 0; i < instr->OperandCount(); ++i) {
       HValue* operand = instr->OperandAt(i);
       if (operand->IsDead()) worklist.Add(HInstruction::cast(operand), zone());
     }
   }
 }
 
 
+void HGraph::ApplyActualValues() {
+  HPhase phase("H_Apply actual values", this);

[Jakob Kummerow, 2013/01/10 16:06:47]

It would be nice to be able to skip this completely when it is not needed (when
there is no HBoundsCheck around). Feel free to fix that in a follow-up CL.

+
+  for (int block_index = 0; block_index < blocks()->length(); block_index++) {
+    HBasicBlock* block = blocks()->at(block_index);
+
+    for (int i = 0; i < block->phis()->length(); i++) {
+      HPhi* phi = block->phis()->at(i);
+      if (phi->ActualValue() != phi) {

[Jakob Kummerow, 2013/01/10 16:06:47]

This can never be true, right? Let's not do the work, then. If you want to be
extra careful, you can put in a guard:

#ifdef DEBUG
    for (...) {
      // A phi's actual value is currently always itself.
      HPhi* phi = block->phis()->at(i);
      ASSERT(phi->ActualValue() == phi);
    }
#endif

+        phi->ReplaceAllUsesWith(phi->ActualValue());
+      }
+    }
+
+    for (HInstruction* instruction = block->first();
+        instruction != NULL;
+        instruction = instruction->next()) {
+      if (instruction->ActualValue() != instruction) {
+        instruction->ReplaceAllUsesWith(instruction->ActualValue());
+      }
+    }
+  }
+}
+
+
 void HOptimizedGraphBuilder::AddPhi(HPhi* instr) {
   ASSERT(current_block() != NULL);
   current_block()->AddPhi(instr);
 }
 
 
 void HOptimizedGraphBuilder::PushAndAdd(HInstruction* instr) {
   Push(instr);
   AddInstruction(instr);
 }
@@ skipping 6212 matching lines @@
     }
   }
 
 #ifdef DEBUG
   if (graph_ != NULL) graph_->Verify(false);  // No full verify.
   if (allocator_ != NULL) allocator_->Verify();
 #endif
 }
 
 } }  // namespace v8::internal