deps/v8/src/hydrogen-bce.cc

   1 // Copyright 2013 the V8 project authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include "src/hydrogen-bce.h"
   6
   7 namespace v8 {
   8 namespace internal {
   9
  10
  11 // We try to "factor up" HBoundsCheck instructions towards the root of the
  12 // dominator tree.
  13 // For now we handle checks where the index is like "exp + int32value".
  14 // If in the dominator tree we check "exp + v1" and later (dominated)
  15 // "exp + v2", if v2 <= v1 we can safely remove the second check, and if
  16 // v2 > v1 we can use v2 in the 1st check and again remove the second.
  17 // To do so we keep a dictionary of all checks where the key if the pair
  18 // "exp, length".
  19 // The class BoundsCheckKey represents this key.
  20 class BoundsCheckKey : public ZoneObject {
  21  public:
  22   HValue* IndexBase() const { return index_base_; }
  23   HValue* Length() const { return length_; }
  24
  25   uint32_t Hash() {
  26     return static_cast<uint32_t>(index_base_->Hashcode() ^ length_->Hashcode());
  27   }
  28
  29   static BoundsCheckKey* Create(Zone* zone,
  30                                 HBoundsCheck* check,
  31                                 int32_t* offset) {
  32     if (!check->index()->representation().IsSmiOrInteger32()) return NULL;
  33
  34     HValue* index_base = NULL;
  35     HConstant* constant = NULL;
  36     bool is_sub = false;
  37
  38     if (check->index()->IsAdd()) {
  39       HAdd* index = HAdd::cast(check->index());
  40       if (index->left()->IsConstant()) {
  41         constant = HConstant::cast(index->left());
  42         index_base = index->right();
  43       } else if (index->right()->IsConstant()) {
  44         constant = HConstant::cast(index->right());
  45         index_base = index->left();
  46       }
  47     } else if (check->index()->IsSub()) {
  48       HSub* index = HSub::cast(check->index());
  49       is_sub = true;
  50       if (index->right()->IsConstant()) {
  51         constant = HConstant::cast(index->right());
  52         index_base = index->left();
  53       }
  54     } else if (check->index()->IsConstant()) {
  55       index_base = check->block()->graph()->GetConstant0();
  56       constant = HConstant::cast(check->index());
  57     }
  58
  59     if (constant != NULL && constant->HasInteger32Value() &&
  60         constant->Integer32Value() != kMinInt) {
  61       *offset = is_sub ? - constant->Integer32Value()
  62                        : constant->Integer32Value();
  63     } else {
  64       *offset = 0;
  65       index_base = check->index();
  66     }
  67
  68     return new(zone) BoundsCheckKey(index_base, check->length());
  69   }
  70
  71  private:
  72   BoundsCheckKey(HValue* index_base, HValue* length)
  73       : index_base_(index_base),
  74         length_(length) { }
  75
  76   HValue* index_base_;
  77   HValue* length_;
  78
  79   DISALLOW_COPY_AND_ASSIGN(BoundsCheckKey);
  80 };
  81
  82
  83 // Data about each HBoundsCheck that can be eliminated or moved.
  84 // It is the "value" in the dictionary indexed by "base-index, length"
  85 // (the key is BoundsCheckKey).
  86 // We scan the code with a dominator tree traversal.
  87 // Traversing the dominator tree we keep a stack (implemented as a singly
  88 // linked list) of "data" for each basic block that contains a relevant check
  89 // with the same key (the dictionary holds the head of the list).
  90 // We also keep all the "data" created for a given basic block in a list, and
  91 // use it to "clean up" the dictionary when backtracking in the dominator tree
  92 // traversal.
  93 // Doing this each dictionary entry always directly points to the check that
  94 // is dominating the code being examined now.
  95 // We also track the current "offset" of the index expression and use it to
  96 // decide if any check is already "covered" (so it can be removed) or not.
  97 class BoundsCheckBbData: public ZoneObject {
  98  public:
  99   BoundsCheckKey* Key() const { return key_; }
 100   int32_t LowerOffset() const { return lower_offset_; }
 101   int32_t UpperOffset() const { return upper_offset_; }
 102   HBasicBlock* BasicBlock() const { return basic_block_; }
 103   HBoundsCheck* LowerCheck() const { return lower_check_; }
 104   HBoundsCheck* UpperCheck() const { return upper_check_; }
 105   BoundsCheckBbData* NextInBasicBlock() const { return next_in_bb_; }
 106   BoundsCheckBbData* FatherInDominatorTree() const { return father_in_dt_; }
 107
 108   bool OffsetIsCovered(int32_t offset) const {
 109     return offset >= LowerOffset() && offset <= UpperOffset();
 110   }
 111
 112   bool HasSingleCheck() { return lower_check_ == upper_check_; }
 113
 114   void UpdateUpperOffsets(HBoundsCheck* check, int32_t offset) {
 115     BoundsCheckBbData* data = FatherInDominatorTree();
 116     while (data != NULL && data->UpperCheck() == check) {
 117       DCHECK(data->upper_offset_ < offset);
 118       data->upper_offset_ = offset;
 119       data = data->FatherInDominatorTree();
 120     }
 121   }
 122
 123   void UpdateLowerOffsets(HBoundsCheck* check, int32_t offset) {
 124     BoundsCheckBbData* data = FatherInDominatorTree();
 125     while (data != NULL && data->LowerCheck() == check) {
 126       DCHECK(data->lower_offset_ > offset);
 127       data->lower_offset_ = offset;
 128       data = data->FatherInDominatorTree();
 129     }
 130   }
 131
 132   // The goal of this method is to modify either upper_offset_ or
 133   // lower_offset_ so that also new_offset is covered (the covered
 134   // range grows).
 135   //
 136   // The precondition is that new_check follows UpperCheck() and
 137   // LowerCheck() in the same basic block, and that new_offset is not
 138   // covered (otherwise we could simply remove new_check).
 139   //
 140   // If HasSingleCheck() is true then new_check is added as "second check"
 141   // (either upper or lower; note that HasSingleCheck() becomes false).
 142   // Otherwise one of the current checks is modified so that it also covers
 143   // new_offset, and new_check is removed.
 144   void CoverCheck(HBoundsCheck* new_check,
 145                   int32_t new_offset) {
 146     DCHECK(new_check->index()->representation().IsSmiOrInteger32());
 147     bool keep_new_check = false;
 148
 149     if (new_offset > upper_offset_) {
 150       upper_offset_ = new_offset;
 151       if (HasSingleCheck()) {
 152         keep_new_check = true;
 153         upper_check_ = new_check;
 154       } else {
 155         TightenCheck(upper_check_, new_check, new_offset);
 156         UpdateUpperOffsets(upper_check_, upper_offset_);
 157       }
 158     } else if (new_offset < lower_offset_) {
 159       lower_offset_ = new_offset;
 160       if (HasSingleCheck()) {
 161         keep_new_check = true;
 162         lower_check_ = new_check;
 163       } else {
 164         TightenCheck(lower_check_, new_check, new_offset);
 165         UpdateLowerOffsets(lower_check_, lower_offset_);
 166       }
 167     } else {
 168       // Should never have called CoverCheck() in this case.
 169       UNREACHABLE();
 170     }
 171
 172     if (!keep_new_check) {
 173       if (FLAG_trace_bce) {
 174         base::OS::Print("Eliminating check #%d after tightening\n",
 175                         new_check->id());
 176       }
 177       new_check->block()->graph()->isolate()->counters()->
 178           bounds_checks_eliminated()->Increment();
 179       new_check->DeleteAndReplaceWith(new_check->ActualValue());
 180     } else {
 181       HBoundsCheck* first_check = new_check == lower_check_ ? upper_check_
 182                                                             : lower_check_;
 183       if (FLAG_trace_bce) {
 184         base::OS::Print("Moving second check #%d after first check #%d\n",
 185                         new_check->id(), first_check->id());
 186       }
 187       // The length is guaranteed to be live at first_check.
 188       DCHECK(new_check->length() == first_check->length());
 189       HInstruction* old_position = new_check->next();
 190       new_check->Unlink();
 191       new_check->InsertAfter(first_check);
 192       MoveIndexIfNecessary(new_check->index(), new_check, old_position);
 193     }
 194   }
 195
 196   BoundsCheckBbData(BoundsCheckKey* key,
 197                     int32_t lower_offset,
 198                     int32_t upper_offset,
 199                     HBasicBlock* bb,
 200                     HBoundsCheck* lower_check,
 201                     HBoundsCheck* upper_check,
 202                     BoundsCheckBbData* next_in_bb,
 203                     BoundsCheckBbData* father_in_dt)
 204       : key_(key),
 205         lower_offset_(lower_offset),
 206         upper_offset_(upper_offset),
 207         basic_block_(bb),
 208         lower_check_(lower_check),
 209         upper_check_(upper_check),
 210         next_in_bb_(next_in_bb),
 211         father_in_dt_(father_in_dt) { }
 212
 213  private:
 214   BoundsCheckKey* key_;
 215   int32_t lower_offset_;
 216   int32_t upper_offset_;
 217   HBasicBlock* basic_block_;
 218   HBoundsCheck* lower_check_;
 219   HBoundsCheck* upper_check_;
 220   BoundsCheckBbData* next_in_bb_;
 221   BoundsCheckBbData* father_in_dt_;
 222
 223   void MoveIndexIfNecessary(HValue* index_raw,
 224                             HBoundsCheck* insert_before,
 225                             HInstruction* end_of_scan_range) {
 226     // index_raw can be HAdd(index_base, offset), HSub(index_base, offset),
 227     // HConstant(offset) or index_base directly.
 228     // In the latter case, no need to move anything.
 229     if (index_raw->IsAdd() || index_raw->IsSub()) {
 230       HArithmeticBinaryOperation* index =
 231           HArithmeticBinaryOperation::cast(index_raw);
 232       HValue* left_input = index->left();
 233       HValue* right_input = index->right();
 234       bool must_move_index = false;
 235       bool must_move_left_input = false;
 236       bool must_move_right_input = false;
 237       for (HInstruction* cursor = end_of_scan_range; cursor != insert_before;) {
 238         if (cursor == left_input) must_move_left_input = true;
 239         if (cursor == right_input) must_move_right_input = true;
 240         if (cursor == index) must_move_index = true;
 241         if (cursor->previous() == NULL) {
 242           cursor = cursor->block()->dominator()->end();
 243         } else {
 244           cursor = cursor->previous();
 245         }
 246       }
 247       if (must_move_index) {
 248         index->Unlink();
 249         index->InsertBefore(insert_before);
 250       }
 251       // The BCE algorithm only selects mergeable bounds checks that share
 252       // the same "index_base", so we'll only ever have to move constants.
 253       if (must_move_left_input) {
 254         HConstant::cast(left_input)->Unlink();
 255         HConstant::cast(left_input)->InsertBefore(index);
 256       }
 257       if (must_move_right_input) {
 258         HConstant::cast(right_input)->Unlink();
 259         HConstant::cast(right_input)->InsertBefore(index);
 260       }
 261     } else if (index_raw->IsConstant()) {
 262       HConstant* index = HConstant::cast(index_raw);
 263       bool must_move = false;
 264       for (HInstruction* cursor = end_of_scan_range; cursor != insert_before;) {
 265         if (cursor == index) must_move = true;
 266         if (cursor->previous() == NULL) {
 267           cursor = cursor->block()->dominator()->end();
 268         } else {
 269           cursor = cursor->previous();
 270         }
 271       }
 272       if (must_move) {
 273         index->Unlink();
 274         index->InsertBefore(insert_before);
 275       }
 276     }
 277   }
 278
 279   void TightenCheck(HBoundsCheck* original_check,
 280                     HBoundsCheck* tighter_check,
 281                     int32_t new_offset) {
 282     DCHECK(original_check->length() == tighter_check->length());
 283     MoveIndexIfNecessary(tighter_check->index(), original_check, tighter_check);
 284     original_check->ReplaceAllUsesWith(original_check->index());
 285     original_check->SetOperandAt(0, tighter_check->index());
 286     if (FLAG_trace_bce) {
 287       base::OS::Print("Tightened check #%d with offset %d from #%d\n",
 288                       original_check->id(), new_offset, tighter_check->id());
 289     }
 290   }
 291
 292   DISALLOW_COPY_AND_ASSIGN(BoundsCheckBbData);
 293 };
 294
 295
 296 static bool BoundsCheckKeyMatch(void* key1, void* key2) {
 297   BoundsCheckKey* k1 = static_cast<BoundsCheckKey*>(key1);
 298   BoundsCheckKey* k2 = static_cast<BoundsCheckKey*>(key2);
 299   return k1->IndexBase() == k2->IndexBase() && k1->Length() == k2->Length();
 300 }
 301
 302
 303 BoundsCheckTable::BoundsCheckTable(Zone* zone)
 304     : ZoneHashMap(BoundsCheckKeyMatch, ZoneHashMap::kDefaultHashMapCapacity,
 305                   ZoneAllocationPolicy(zone)) { }
 306
 307
 308 BoundsCheckBbData** BoundsCheckTable::LookupOrInsert(BoundsCheckKey* key,
 309                                                      Zone* zone) {
 310   return reinterpret_cast<BoundsCheckBbData**>(
 311       &(Lookup(key, key->Hash(), true, ZoneAllocationPolicy(zone))->value));
 312 }
 313
 314
 315 void BoundsCheckTable::Insert(BoundsCheckKey* key,
 316                               BoundsCheckBbData* data,
 317                               Zone* zone) {
 318   Lookup(key, key->Hash(), true, ZoneAllocationPolicy(zone))->value = data;
 319 }
 320
 321
 322 void BoundsCheckTable::Delete(BoundsCheckKey* key) {
 323   Remove(key, key->Hash());
 324 }
 325
 326
 327 class HBoundsCheckEliminationState {
 328  public:
 329   HBasicBlock* block_;
 330   BoundsCheckBbData* bb_data_list_;
 331   int index_;
 332 };
 333
 334
 335 // Eliminates checks in bb and recursively in the dominated blocks.
 336 // Also replace the results of check instructions with the original value, if
 337 // the result is used. This is safe now, since we don't do code motion after
 338 // this point. It enables better register allocation since the value produced
 339 // by check instructions is really a copy of the original value.
 340 void HBoundsCheckEliminationPhase::EliminateRedundantBoundsChecks(
 341     HBasicBlock* entry) {
 342   // Allocate the stack.
 343   HBoundsCheckEliminationState* stack =
 344     zone()->NewArray<HBoundsCheckEliminationState>(graph()->blocks()->length());
 345
 346   // Explicitly push the entry block.
 347   stack[0].block_ = entry;
 348   stack[0].bb_data_list_ = PreProcessBlock(entry);
 349   stack[0].index_ = 0;
 350   int stack_depth = 1;
 351
 352   // Implement depth-first traversal with a stack.
 353   while (stack_depth > 0) {
 354     int current = stack_depth - 1;
 355     HBoundsCheckEliminationState* state = &stack[current];
 356     const ZoneList<HBasicBlock*>* children = state->block_->dominated_blocks();
 357
 358     if (state->index_ < children->length()) {
 359       // Recursively visit children blocks.
 360       HBasicBlock* child = children->at(state->index_++);
 361       int next = stack_depth++;
 362       stack[next].block_ = child;
 363       stack[next].bb_data_list_ = PreProcessBlock(child);
 364       stack[next].index_ = 0;
 365     } else {
 366       // Finished with all children; post process the block.
 367       PostProcessBlock(state->block_, state->bb_data_list_);
 368       stack_depth--;
 369     }
 370   }
 371 }
 372
 373
 374 BoundsCheckBbData* HBoundsCheckEliminationPhase::PreProcessBlock(
 375     HBasicBlock* bb) {
 376   BoundsCheckBbData* bb_data_list = NULL;
 377
 378   for (HInstructionIterator it(bb); !it.Done(); it.Advance()) {
 379     HInstruction* i = it.Current();
 380     if (!i->IsBoundsCheck()) continue;
 381
 382     HBoundsCheck* check = HBoundsCheck::cast(i);
 383     int32_t offset = 0;
 384     BoundsCheckKey* key =
 385         BoundsCheckKey::Create(zone(), check, &offset);
 386     if (key == NULL) continue;
 387     BoundsCheckBbData** data_p = table_.LookupOrInsert(key, zone());
 388     BoundsCheckBbData* data = *data_p;
 389     if (data == NULL) {
 390       bb_data_list = new(zone()) BoundsCheckBbData(key,
 391                                                    offset,
 392                                                    offset,
 393                                                    bb,
 394                                                    check,
 395                                                    check,
 396                                                    bb_data_list,
 397                                                    NULL);
 398       *data_p = bb_data_list;
 399       if (FLAG_trace_bce) {
 400         base::OS::Print("Fresh bounds check data for block #%d: [%d]\n",
 401                         bb->block_id(), offset);
 402       }
 403     } else if (data->OffsetIsCovered(offset)) {
 404       bb->graph()->isolate()->counters()->
 405           bounds_checks_eliminated()->Increment();
 406       if (FLAG_trace_bce) {
 407         base::OS::Print("Eliminating bounds check #%d, offset %d is covered\n",
 408                         check->id(), offset);
 409       }
 410       check->DeleteAndReplaceWith(check->ActualValue());
 411     } else if (data->BasicBlock() == bb) {
 412       // TODO(jkummerow): I think the following logic would be preferable:
 413       // if (data->Basicblock() == bb ||
 414       //     graph()->use_optimistic_licm() ||
 415       //     bb->IsLoopSuccessorDominator()) {
 416       //   data->CoverCheck(check, offset)
 417       // } else {
 418       //   /* add pristine BCBbData like in (data == NULL) case above */
 419       // }
 420       // Even better would be: distinguish between read-only dominator-imposed
 421       // knowledge and modifiable upper/lower checks.
 422       // What happens currently is that the first bounds check in a dominated
 423       // block will stay around while any further checks are hoisted out,
 424       // which doesn't make sense. Investigate/fix this in a future CL.
 425       data->CoverCheck(check, offset);
 426     } else if (graph()->use_optimistic_licm() ||
 427                bb->IsLoopSuccessorDominator()) {
 428       int32_t new_lower_offset = offset < data->LowerOffset()
 429           ? offset
 430           : data->LowerOffset();
 431       int32_t new_upper_offset = offset > data->UpperOffset()
 432           ? offset
 433           : data->UpperOffset();
 434       bb_data_list = new(zone()) BoundsCheckBbData(key,
 435                                                    new_lower_offset,
 436                                                    new_upper_offset,
 437                                                    bb,
 438                                                    data->LowerCheck(),
 439                                                    data->UpperCheck(),
 440                                                    bb_data_list,
 441                                                    data);
 442       if (FLAG_trace_bce) {
 443         base::OS::Print("Updated bounds check data for block #%d: [%d - %d]\n",
 444                         bb->block_id(), new_lower_offset, new_upper_offset);
 445       }
 446       table_.Insert(key, bb_data_list, zone());
 447     }
 448   }
 449
 450   return bb_data_list;
 451 }
 452
 453
 454 void HBoundsCheckEliminationPhase::PostProcessBlock(
 455     HBasicBlock* block, BoundsCheckBbData* data) {
 456   while (data != NULL) {
 457     if (data->FatherInDominatorTree()) {
 458       table_.Insert(data->Key(), data->FatherInDominatorTree(), zone());
 459     } else {
 460       table_.Delete(data->Key());
 461     }
 462     data = data->NextInBasicBlock();
 463   }
 464 }
 465
 466 } }  // namespace v8::internal