Add FLAG_trace_bce

src/hydrogen-bce.cc

 // Copyright 2013 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 12 matching lines @@
 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 
 #include "hydrogen-bce.h"
 
 namespace v8 {
 namespace internal {
 
+
 // 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.
 // To do so we keep a dictionary of all checks where the key if the pair
 // "exp, length".
 // The class BoundsCheckKey represents this key.
 class BoundsCheckKey : public ZoneObject {
@@ skipping 123 matching lines @@
                   int32_t new_offset) {
     ASSERT(new_check->index()->representation().IsSmiOrInteger32());
     bool keep_new_check = false;
 
     if (new_offset > upper_offset_) {
       upper_offset_ = new_offset;
       if (HasSingleCheck()) {
         keep_new_check = true;
         upper_check_ = new_check;
       } else {
-        TightenCheck(upper_check_, new_check);
+        TightenCheck(upper_check_, new_check, new_offset);
         UpdateUpperOffsets(upper_check_, upper_offset_);
       }
     } else if (new_offset < lower_offset_) {
       lower_offset_ = new_offset;
       if (HasSingleCheck()) {
         keep_new_check = true;
         lower_check_ = new_check;
       } else {
-        TightenCheck(lower_check_, new_check);
+        TightenCheck(lower_check_, new_check, new_offset);
         UpdateLowerOffsets(lower_check_, lower_offset_);
       }
     } else {
       // Should never have called CoverCheck() in this case.
       UNREACHABLE();
     }
 
     if (!keep_new_check) {
+      if (FLAG_trace_bce) {
+        OS::Print("Eliminating check #%d after tightening\n",
+                  new_check->id());
+      }
       new_check->block()->graph()->isolate()->counters()->
           bounds_checks_eliminated()->Increment();
       new_check->DeleteAndReplaceWith(new_check->ActualValue());
     } else {
       HBoundsCheck* first_check = new_check == lower_check_ ? upper_check_
                                                             : lower_check_;
+      if (FLAG_trace_bce) {
+        OS::Print("Moving second check #%d after first check #%d\n",
+                  new_check->id(), first_check->id());
+      }
       // The length is guaranteed to be live at first_check.
       ASSERT(new_check->length() == first_check->length());
       HInstruction* old_position = new_check->next();
       new_check->Unlink();
       new_check->InsertAfter(first_check);
       MoveIndexIfNecessary(new_check->index(), new_check, old_position);
     }
   }
 
   BoundsCheckBbData(BoundsCheckKey* key,
@@ skipping 58 matching lines @@
       HConstant::cast(left_input)->Unlink();
       HConstant::cast(left_input)->InsertBefore(index);
     }
     if (must_move_right_input) {
       HConstant::cast(right_input)->Unlink();
       HConstant::cast(right_input)->InsertBefore(index);
     }
   }
 
   void TightenCheck(HBoundsCheck* original_check,
-                    HBoundsCheck* tighter_check) {
+                    HBoundsCheck* tighter_check,
+                    int32_t new_offset) {
     ASSERT(original_check->length() == tighter_check->length());
     MoveIndexIfNecessary(tighter_check->index(), original_check, tighter_check);
     original_check->ReplaceAllUsesWith(original_check->index());
     original_check->SetOperandAt(0, tighter_check->index());
+    if (FLAG_trace_bce) {
+      OS::Print("Tightened check #%d with offset %d from #%d\n",
+                original_check->id(), new_offset, tighter_check->id());
+    }
   }
 
   DISALLOW_COPY_AND_ASSIGN(BoundsCheckBbData);
 };
 
 
 static bool BoundsCheckKeyMatch(void* key1, void* key2) {
   BoundsCheckKey* k1 = static_cast<BoundsCheckKey*>(key1);
   BoundsCheckKey* k2 = static_cast<BoundsCheckKey*>(key2);
   return k1->IndexBase() == k2->IndexBase() && k1->Length() == k2->Length();
@@ skipping 89 matching lines @@
     if (data == NULL) {
       bb_data_list = new(zone()) BoundsCheckBbData(key,
                                                    offset,
                                                    offset,
                                                    bb,
                                                    check,
                                                    check,
                                                    bb_data_list,
                                                    NULL);
       *data_p = bb_data_list;
+      if (FLAG_trace_bce) {
+        OS::Print("Fresh bounds check data for block #%d: [%d]\n",
+                  bb->block_id(), offset);
+      }
     } else if (data->OffsetIsCovered(offset)) {
       bb->graph()->isolate()->counters()->
           bounds_checks_eliminated()->Increment();
+      if (FLAG_trace_bce) {
+        OS::Print("Eliminating bounds check #%d, offset %d is covered\n",
+                  check->id(), offset);
+      }
       check->DeleteAndReplaceWith(check->ActualValue());
     } else if (data->BasicBlock() == bb) {
+      // TODO(jkummerow): I think the following logic would be preferable:
+      // if (data->Basicblock() == bb ||
+      //     graph()->use_optimistic_licm() ||
+      //     bb->IsLoopSuccessorDominator()) {
+      //   data->CoverCheck(check, offset)
+      // } else {
+      //   /* add pristine BCBbData like in (data == NULL) case above */
+      // }
+      // Even better would be: distinguish between read-only dominator-imposed
+      // knowledge and modifiable upper/lower checks.
+      // What happens currently is that the first bounds check in a dominated
+      // block will stay around while any further checks are hoisted out,
+      // which doesn't make sense. Investigate/fix this in a future CL.
       data->CoverCheck(check, offset);
     } else if (graph()->use_optimistic_licm() ||
                bb->IsLoopSuccessorDominator()) {
       int32_t new_lower_offset = offset < data->LowerOffset()
           ? offset
           : data->LowerOffset();
       int32_t new_upper_offset = offset > data->UpperOffset()
           ? offset
           : data->UpperOffset();
       bb_data_list = new(zone()) BoundsCheckBbData(key,
                                                    new_lower_offset,
                                                    new_upper_offset,
                                                    bb,
                                                    data->LowerCheck(),
                                                    data->UpperCheck(),
                                                    bb_data_list,
                                                    data);
+      if (FLAG_trace_bce) {
+        OS::Print("Updated bounds check data for block #%d: [%d - %d]\n",
+                  bb->block_id(), new_lower_offset, new_upper_offset);
+      }
       table_.Insert(key, bb_data_list, zone());
     }
   }
 
   return bb_data_list;
 }
 
 
 void HBoundsCheckEliminationPhase::PostProcessBlock(
     HBasicBlock* block, BoundsCheckBbData* data) {
   while (data != NULL) {
     if (data->FatherInDominatorTree()) {
       table_.Insert(data->Key(), data->FatherInDominatorTree(), zone());
     } else {
       table_.Delete(data->Key());
     }
     data = data->NextInBasicBlock();
   }
 }
 
 } }  // namespace v8::internal