Home | History | Annotate | Download | only in crankshaft 
      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/crankshaft/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       HValue* context = index->context();
    235       bool must_move_index = false;
    236       bool must_move_left_input = false;
    237       bool must_move_right_input = false;
    238       bool must_move_context = false;
    239       for (HInstruction* cursor = end_of_scan_range; cursor != insert_before;) {
    240         if (cursor == left_input) must_move_left_input = true;
    241         if (cursor == right_input) must_move_right_input = true;
    242         if (cursor == context) must_move_context = true;
    243         if (cursor == index) must_move_index = true;
    244         if (cursor->previous() == NULL) {
    245           cursor = cursor->block()->dominator()->end();
    246         } else {
    247           cursor = cursor->previous();
    248         }
    249       }
    250       if (must_move_index) {
    251         index->Unlink();
    252         index->InsertBefore(insert_before);
    253       }
    254       // The BCE algorithm only selects mergeable bounds checks that share
    255       // the same "index_base", so we'll only ever have to move constants.
    256       if (must_move_left_input) {
    257         HConstant::cast(left_input)->Unlink();
    258         HConstant::cast(left_input)->InsertBefore(index);
    259       }
    260       if (must_move_right_input) {
    261         HConstant::cast(right_input)->Unlink();
    262         HConstant::cast(right_input)->InsertBefore(index);
    263       }
    264       if (must_move_context) {
    265         // Contexts are always constants.
    266         HConstant::cast(context)->Unlink();
    267         HConstant::cast(context)->InsertBefore(index);
    268       }
    269     } else if (index_raw->IsConstant()) {
    270       HConstant* index = HConstant::cast(index_raw);
    271       bool must_move = false;
    272       for (HInstruction* cursor = end_of_scan_range; cursor != insert_before;) {
    273         if (cursor == index) must_move = true;
    274         if (cursor->previous() == NULL) {
    275           cursor = cursor->block()->dominator()->end();
    276         } else {
    277           cursor = cursor->previous();
    278         }
    279       }
    280       if (must_move) {
    281         index->Unlink();
    282         index->InsertBefore(insert_before);
    283       }
    284     }
    285   }
    286 
    287   void TightenCheck(HBoundsCheck* original_check,
    288                     HBoundsCheck* tighter_check,
    289                     int32_t new_offset) {
    290     DCHECK(original_check->length() == tighter_check->length());
    291     MoveIndexIfNecessary(tighter_check->index(), original_check, tighter_check);
    292     original_check->ReplaceAllUsesWith(original_check->index());
    293     original_check->SetOperandAt(0, tighter_check->index());
    294     if (FLAG_trace_bce) {
    295       base::OS::Print("Tightened check #%d with offset %d from #%d\n",
    296                       original_check->id(), new_offset, tighter_check->id());
    297     }
    298   }
    299 
    300   DISALLOW_COPY_AND_ASSIGN(BoundsCheckBbData);
    301 };
    302 
    303 
    304 static bool BoundsCheckKeyMatch(void* key1, void* key2) {
    305   BoundsCheckKey* k1 = static_cast<BoundsCheckKey*>(key1);
    306   BoundsCheckKey* k2 = static_cast<BoundsCheckKey*>(key2);
    307   return k1->IndexBase() == k2->IndexBase() && k1->Length() == k2->Length();
    308 }
    309 
    310 
    311 BoundsCheckTable::BoundsCheckTable(Zone* zone)
    312     : ZoneHashMap(BoundsCheckKeyMatch, ZoneHashMap::kDefaultHashMapCapacity,
    313                   ZoneAllocationPolicy(zone)) { }
    314 
    315 
    316 BoundsCheckBbData** BoundsCheckTable::LookupOrInsert(BoundsCheckKey* key,
    317                                                      Zone* zone) {
    318   return reinterpret_cast<BoundsCheckBbData**>(
    319       &(ZoneHashMap::LookupOrInsert(key, key->Hash(),
    320                                     ZoneAllocationPolicy(zone))->value));
    321 }
    322 
    323 
    324 void BoundsCheckTable::Insert(BoundsCheckKey* key,
    325                               BoundsCheckBbData* data,
    326                               Zone* zone) {
    327   ZoneHashMap::LookupOrInsert(key, key->Hash(), ZoneAllocationPolicy(zone))
    328       ->value = data;
    329 }
    330 
    331 
    332 void BoundsCheckTable::Delete(BoundsCheckKey* key) {
    333   Remove(key, key->Hash());
    334 }
    335 
    336 
    337 class HBoundsCheckEliminationState {
    338  public:
    339   HBasicBlock* block_;
    340   BoundsCheckBbData* bb_data_list_;
    341   int index_;
    342 };
    343 
    344 
    345 // Eliminates checks in bb and recursively in the dominated blocks.
    346 // Also replace the results of check instructions with the original value, if
    347 // the result is used. This is safe now, since we don't do code motion after
    348 // this point. It enables better register allocation since the value produced
    349 // by check instructions is really a copy of the original value.
    350 void HBoundsCheckEliminationPhase::EliminateRedundantBoundsChecks(
    351     HBasicBlock* entry) {
    352   // Allocate the stack.
    353   HBoundsCheckEliminationState* stack =
    354     zone()->NewArray<HBoundsCheckEliminationState>(graph()->blocks()->length());
    355 
    356   // Explicitly push the entry block.
    357   stack[0].block_ = entry;
    358   stack[0].bb_data_list_ = PreProcessBlock(entry);
    359   stack[0].index_ = 0;
    360   int stack_depth = 1;
    361 
    362   // Implement depth-first traversal with a stack.
    363   while (stack_depth > 0) {
    364     int current = stack_depth - 1;
    365     HBoundsCheckEliminationState* state = &stack[current];
    366     const ZoneList<HBasicBlock*>* children = state->block_->dominated_blocks();
    367 
    368     if (state->index_ < children->length()) {
    369       // Recursively visit children blocks.
    370       HBasicBlock* child = children->at(state->index_++);
    371       int next = stack_depth++;
    372       stack[next].block_ = child;
    373       stack[next].bb_data_list_ = PreProcessBlock(child);
    374       stack[next].index_ = 0;
    375     } else {
    376       // Finished with all children; post process the block.
    377       PostProcessBlock(state->block_, state->bb_data_list_);
    378       stack_depth--;
    379     }
    380   }
    381 }
    382 
    383 
    384 BoundsCheckBbData* HBoundsCheckEliminationPhase::PreProcessBlock(
    385     HBasicBlock* bb) {
    386   BoundsCheckBbData* bb_data_list = NULL;
    387 
    388   for (HInstructionIterator it(bb); !it.Done(); it.Advance()) {
    389     HInstruction* i = it.Current();
    390     if (!i->IsBoundsCheck()) continue;
    391 
    392     HBoundsCheck* check = HBoundsCheck::cast(i);
    393     int32_t offset = 0;
    394     BoundsCheckKey* key =
    395         BoundsCheckKey::Create(zone(), check, &offset);
    396     if (key == NULL) continue;
    397     BoundsCheckBbData** data_p = table_.LookupOrInsert(key, zone());
    398     BoundsCheckBbData* data = *data_p;
    399     if (data == NULL) {
    400       bb_data_list = new(zone()) BoundsCheckBbData(key,
    401                                                    offset,
    402                                                    offset,
    403                                                    bb,
    404                                                    check,
    405                                                    check,
    406                                                    bb_data_list,
    407                                                    NULL);
    408       *data_p = bb_data_list;
    409       if (FLAG_trace_bce) {
    410         base::OS::Print("Fresh bounds check data for block #%d: [%d]\n",
    411                         bb->block_id(), offset);
    412       }
    413     } else if (data->OffsetIsCovered(offset)) {
    414       bb->graph()->isolate()->counters()->
    415           bounds_checks_eliminated()->Increment();
    416       if (FLAG_trace_bce) {
    417         base::OS::Print("Eliminating bounds check #%d, offset %d is covered\n",
    418                         check->id(), offset);
    419       }
    420       check->DeleteAndReplaceWith(check->ActualValue());
    421     } else if (data->BasicBlock() == bb) {
    422       // TODO(jkummerow): I think the following logic would be preferable:
    423       // if (data->Basicblock() == bb ||
    424       //     graph()->use_optimistic_licm() ||
    425       //     bb->IsLoopSuccessorDominator()) {
    426       //   data->CoverCheck(check, offset)
    427       // } else {
    428       //   /* add pristine BCBbData like in (data == NULL) case above */
    429       // }
    430       // Even better would be: distinguish between read-only dominator-imposed
    431       // knowledge and modifiable upper/lower checks.
    432       // What happens currently is that the first bounds check in a dominated
    433       // block will stay around while any further checks are hoisted out,
    434       // which doesn't make sense. Investigate/fix this in a future CL.
    435       data->CoverCheck(check, offset);
    436     } else if (graph()->use_optimistic_licm() ||
    437                bb->IsLoopSuccessorDominator()) {
    438       int32_t new_lower_offset = offset < data->LowerOffset()
    439           ? offset
    440           : data->LowerOffset();
    441       int32_t new_upper_offset = offset > data->UpperOffset()
    442           ? offset
    443           : data->UpperOffset();
    444       bb_data_list = new(zone()) BoundsCheckBbData(key,
    445                                                    new_lower_offset,
    446                                                    new_upper_offset,
    447                                                    bb,
    448                                                    data->LowerCheck(),
    449                                                    data->UpperCheck(),
    450                                                    bb_data_list,
    451                                                    data);
    452       if (FLAG_trace_bce) {
    453         base::OS::Print("Updated bounds check data for block #%d: [%d - %d]\n",
    454                         bb->block_id(), new_lower_offset, new_upper_offset);
    455       }
    456       table_.Insert(key, bb_data_list, zone());
    457     }
    458   }
    459 
    460   return bb_data_list;
    461 }
    462 
    463 
    464 void HBoundsCheckEliminationPhase::PostProcessBlock(
    465     HBasicBlock* block, BoundsCheckBbData* data) {
    466   while (data != NULL) {
    467     if (data->FatherInDominatorTree()) {
    468       table_.Insert(data->Key(), data->FatherInDominatorTree(), zone());
    469     } else {
    470       table_.Delete(data->Key());
    471     }
    472     data = data->NextInBasicBlock();
    473   }
    474 }
    475 
    476 }  // namespace internal
    477 }  // namespace v8
    478