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-bch.h"
      6 
      7 namespace v8 {
      8 namespace internal {
      9 
     10 /*
     11  * This class is a table with one element for eack basic block.
     12  *
     13  * It is used to check if, inside one loop, all execution paths contain
     14  * a bounds check for a particular [index, length] combination.
     15  * The reason is that if there is a path that stays in the loop without
     16  * executing a check then the check cannot be hoisted out of the loop (it
     17  * would likely fail and cause a deopt for no good reason).
     18  * We also check is there are paths that exit the loop early, and if yes we
     19  * perform the hoisting only if graph()->use_optimistic_licm() is true.
     20  * The reason is that such paths are realtively common and harmless (like in
     21  * a "search" method that scans an array until an element is found), but in
     22  * some cases they could cause a deopt if we hoist the check so this is a
     23  * situation we need to detect.
     24  */
     25 class InductionVariableBlocksTable BASE_EMBEDDED {
     26  public:
     27   class Element {
     28    public:
     29     static const int kNoBlock = -1;
     30 
     31     HBasicBlock* block() { return block_; }
     32     void set_block(HBasicBlock* block) { block_ = block; }
     33     bool is_start() { return is_start_; }
     34     bool is_proper_exit() { return is_proper_exit_; }
     35     bool is_in_loop() { return is_in_loop_; }
     36     bool has_check() { return has_check_; }
     37     void set_has_check() { has_check_ = true; }
     38     InductionVariableLimitUpdate* additional_limit() {
     39       return &additional_limit_;
     40     }
     41 
     42     /*
     43      * Initializes the table element for a given loop (identified by its
     44      * induction variable).
     45      */
     46     void InitializeLoop(InductionVariableData* data) {
     47       DCHECK(data->limit() != NULL);
     48       HLoopInformation* loop = data->phi()->block()->current_loop();
     49       is_start_ = (block() == loop->loop_header());
     50       is_proper_exit_ = (block() == data->induction_exit_target());
     51       is_in_loop_ = loop->IsNestedInThisLoop(block()->current_loop());
     52       has_check_ = false;
     53     }
     54 
     55     // Utility methods to iterate over dominated blocks.
     56     void ResetCurrentDominatedBlock() { current_dominated_block_ = kNoBlock; }
     57     HBasicBlock* CurrentDominatedBlock() {
     58       DCHECK(current_dominated_block_ != kNoBlock);
     59       return current_dominated_block_ < block()->dominated_blocks()->length() ?
     60           block()->dominated_blocks()->at(current_dominated_block_) : NULL;
     61     }
     62     HBasicBlock* NextDominatedBlock() {
     63       current_dominated_block_++;
     64       return CurrentDominatedBlock();
     65     }
     66 
     67     Element()
     68         : block_(NULL), is_start_(false), is_proper_exit_(false),
     69           has_check_(false), additional_limit_(),
     70           current_dominated_block_(kNoBlock) {}
     71 
     72    private:
     73     HBasicBlock* block_;
     74     bool is_start_;
     75     bool is_proper_exit_;
     76     bool is_in_loop_;
     77     bool has_check_;
     78     InductionVariableLimitUpdate additional_limit_;
     79     int current_dominated_block_;
     80   };
     81 
     82   HGraph* graph() const { return graph_; }
     83   Counters* counters() const { return graph()->isolate()->counters(); }
     84   HBasicBlock* loop_header() const { return loop_header_; }
     85   Element* at(int index) const { return &(elements_.at(index)); }
     86   Element* at(HBasicBlock* block) const { return at(block->block_id()); }
     87 
     88   void AddCheckAt(HBasicBlock* block) {
     89     at(block->block_id())->set_has_check();
     90   }
     91 
     92   /*
     93    * Initializes the table for a given loop (identified by its induction
     94    * variable).
     95    */
     96   void InitializeLoop(InductionVariableData* data) {
     97     for (int i = 0; i < graph()->blocks()->length(); i++) {
     98       at(i)->InitializeLoop(data);
     99     }
    100     loop_header_ = data->phi()->block()->current_loop()->loop_header();
    101   }
    102 
    103 
    104   enum Hoistability {
    105     HOISTABLE,
    106     OPTIMISTICALLY_HOISTABLE,
    107     NOT_HOISTABLE
    108   };
    109 
    110   /*
    111    * This method checks if it is appropriate to hoist the bounds checks on an
    112    * induction variable out of the loop.
    113    * The problem is that in the loop code graph there could be execution paths
    114    * where the check is not performed, but hoisting the check has the same
    115    * semantics as performing it at every loop iteration, which could cause
    116    * unnecessary check failures (which would mean unnecessary deoptimizations).
    117    * The method returns OK if there are no paths that perform an iteration
    118    * (loop back to the header) without meeting a check, or UNSAFE is set if
    119    * early exit paths are found.
    120    */
    121   Hoistability CheckHoistability() {
    122     for (int i = 0; i < elements_.length(); i++) {
    123       at(i)->ResetCurrentDominatedBlock();
    124     }
    125     bool unsafe = false;
    126 
    127     HBasicBlock* current = loop_header();
    128     while (current != NULL) {
    129       HBasicBlock* next;
    130 
    131       if (at(current)->has_check() || !at(current)->is_in_loop()) {
    132         // We found a check or we reached a dominated block out of the loop,
    133         // therefore this block is safe and we can backtrack.
    134         next = NULL;
    135       } else {
    136         for (int i = 0; i < current->end()->SuccessorCount(); i ++) {
    137           Element* successor = at(current->end()->SuccessorAt(i));
    138 
    139           if (!successor->is_in_loop()) {
    140             if (!successor->is_proper_exit()) {
    141               // We found a path that exits the loop early, and is not the exit
    142               // related to the induction limit, therefore hoisting checks is
    143               // an optimistic assumption.
    144               unsafe = true;
    145             }
    146           }
    147 
    148           if (successor->is_start()) {
    149             // We found a path that does one loop iteration without meeting any
    150             // check, therefore hoisting checks would be likely to cause
    151             // unnecessary deopts.
    152             return NOT_HOISTABLE;
    153           }
    154         }
    155 
    156         next = at(current)->NextDominatedBlock();
    157       }
    158 
    159       // If we have no next block we need to backtrack the tree traversal.
    160       while (next == NULL) {
    161         current = current->dominator();
    162         if (current != NULL) {
    163           next = at(current)->NextDominatedBlock();
    164         } else {
    165           // We reached the root: next stays NULL.
    166           next = NULL;
    167           break;
    168         }
    169       }
    170 
    171       current = next;
    172     }
    173 
    174     return unsafe ? OPTIMISTICALLY_HOISTABLE : HOISTABLE;
    175   }
    176 
    177   explicit InductionVariableBlocksTable(HGraph* graph)
    178     : graph_(graph), loop_header_(NULL),
    179       elements_(graph->blocks()->length(), graph->zone()) {
    180     for (int i = 0; i < graph->blocks()->length(); i++) {
    181       Element element;
    182       element.set_block(graph->blocks()->at(i));
    183       elements_.Add(element, graph->zone());
    184       DCHECK(at(i)->block()->block_id() == i);
    185     }
    186   }
    187 
    188   // Tries to hoist a check out of its induction loop.
    189   void ProcessRelatedChecks(
    190       InductionVariableData::InductionVariableCheck* check,
    191       InductionVariableData* data) {
    192     HValue* length = check->check()->length();
    193     check->set_processed();
    194     HBasicBlock* header =
    195         data->phi()->block()->current_loop()->loop_header();
    196     HBasicBlock* pre_header = header->predecessors()->at(0);
    197     // Check that the limit is defined in the loop preheader.
    198     if (!data->limit()->IsInteger32Constant()) {
    199       HBasicBlock* limit_block = data->limit()->block();
    200       if (limit_block != pre_header &&
    201           !limit_block->Dominates(pre_header)) {
    202         return;
    203       }
    204     }
    205     // Check that the length and limit have compatible representations.
    206     if (!(data->limit()->representation().Equals(
    207             length->representation()) ||
    208         data->limit()->IsInteger32Constant())) {
    209       return;
    210     }
    211     // Check that the length is defined in the loop preheader.
    212     if (check->check()->length()->block() != pre_header &&
    213         !check->check()->length()->block()->Dominates(pre_header)) {
    214       return;
    215     }
    216 
    217     // Add checks to the table.
    218     for (InductionVariableData::InductionVariableCheck* current_check = check;
    219          current_check != NULL;
    220          current_check = current_check->next()) {
    221       if (current_check->check()->length() != length) continue;
    222 
    223       AddCheckAt(current_check->check()->block());
    224       current_check->set_processed();
    225     }
    226 
    227     // Check that we will not cause unwanted deoptimizations.
    228     Hoistability hoistability = CheckHoistability();
    229     if (hoistability == NOT_HOISTABLE ||
    230         (hoistability == OPTIMISTICALLY_HOISTABLE &&
    231          !graph()->use_optimistic_licm())) {
    232       return;
    233     }
    234 
    235     // We will do the hoisting, but we must see if the limit is "limit" or if
    236     // all checks are done on constants: if all check are done against the same
    237     // constant limit we will use that instead of the induction limit.
    238     bool has_upper_constant_limit = true;
    239     int32_t upper_constant_limit =
    240         check->HasUpperLimit() ? check->upper_limit() : 0;
    241     for (InductionVariableData::InductionVariableCheck* current_check = check;
    242          current_check != NULL;
    243          current_check = current_check->next()) {
    244       has_upper_constant_limit =
    245           has_upper_constant_limit && current_check->HasUpperLimit() &&
    246           current_check->upper_limit() == upper_constant_limit;
    247       counters()->bounds_checks_eliminated()->Increment();
    248       current_check->check()->set_skip_check();
    249     }
    250 
    251     // Choose the appropriate limit.
    252     Zone* zone = graph()->zone();
    253     HValue* context = graph()->GetInvalidContext();
    254     HValue* limit = data->limit();
    255     if (has_upper_constant_limit) {
    256       HConstant* new_limit = HConstant::New(graph()->isolate(), zone, context,
    257                                             upper_constant_limit);
    258       new_limit->InsertBefore(pre_header->end());
    259       limit = new_limit;
    260     }
    261 
    262     // If necessary, redefine the limit in the preheader.
    263     if (limit->IsInteger32Constant() &&
    264         limit->block() != pre_header &&
    265         !limit->block()->Dominates(pre_header)) {
    266       HConstant* new_limit = HConstant::New(graph()->isolate(), zone, context,
    267                                             limit->GetInteger32Constant());
    268       new_limit->InsertBefore(pre_header->end());
    269       limit = new_limit;
    270     }
    271 
    272     // Do the hoisting.
    273     HBoundsCheck* hoisted_check = HBoundsCheck::New(
    274         graph()->isolate(), zone, context, limit, check->check()->length());
    275     hoisted_check->InsertBefore(pre_header->end());
    276     hoisted_check->set_allow_equality(true);
    277     counters()->bounds_checks_hoisted()->Increment();
    278   }
    279 
    280   void CollectInductionVariableData(HBasicBlock* bb) {
    281     bool additional_limit = false;
    282 
    283     for (int i = 0; i < bb->phis()->length(); i++) {
    284       HPhi* phi = bb->phis()->at(i);
    285       phi->DetectInductionVariable();
    286     }
    287 
    288     additional_limit = InductionVariableData::ComputeInductionVariableLimit(
    289         bb, at(bb)->additional_limit());
    290 
    291     if (additional_limit) {
    292       at(bb)->additional_limit()->updated_variable->
    293           UpdateAdditionalLimit(at(bb)->additional_limit());
    294     }
    295 
    296     for (HInstruction* i = bb->first(); i != NULL; i = i->next()) {
    297       if (!i->IsBoundsCheck()) continue;
    298       HBoundsCheck* check = HBoundsCheck::cast(i);
    299       InductionVariableData::BitwiseDecompositionResult decomposition;
    300       InductionVariableData::DecomposeBitwise(check->index(), &decomposition);
    301       if (!decomposition.base->IsPhi()) continue;
    302       HPhi* phi = HPhi::cast(decomposition.base);
    303 
    304       if (!phi->IsInductionVariable()) continue;
    305       InductionVariableData* data = phi->induction_variable_data();
    306 
    307       // For now ignore loops decrementing the index.
    308       if (data->increment() <= 0) continue;
    309       if (!data->LowerLimitIsNonNegativeConstant()) continue;
    310 
    311       // TODO(mmassi): skip OSR values for check->length().
    312       if (check->length() == data->limit() ||
    313           check->length() == data->additional_upper_limit()) {
    314         counters()->bounds_checks_eliminated()->Increment();
    315         check->set_skip_check();
    316         continue;
    317       }
    318 
    319       if (!phi->IsLimitedInductionVariable()) continue;
    320 
    321       int32_t limit = data->ComputeUpperLimit(decomposition.and_mask,
    322                                               decomposition.or_mask);
    323       phi->induction_variable_data()->AddCheck(check, limit);
    324     }
    325 
    326     for (int i = 0; i < bb->dominated_blocks()->length(); i++) {
    327       CollectInductionVariableData(bb->dominated_blocks()->at(i));
    328     }
    329 
    330     if (additional_limit) {
    331       at(bb->block_id())->additional_limit()->updated_variable->
    332           UpdateAdditionalLimit(at(bb->block_id())->additional_limit());
    333     }
    334   }
    335 
    336   void EliminateRedundantBoundsChecks(HBasicBlock* bb) {
    337     for (int i = 0; i < bb->phis()->length(); i++) {
    338       HPhi* phi = bb->phis()->at(i);
    339       if (!phi->IsLimitedInductionVariable()) continue;
    340 
    341       InductionVariableData* induction_data = phi->induction_variable_data();
    342       InductionVariableData::ChecksRelatedToLength* current_length_group =
    343           induction_data->checks();
    344       while (current_length_group != NULL) {
    345         current_length_group->CloseCurrentBlock();
    346         InductionVariableData::InductionVariableCheck* current_base_check =
    347             current_length_group->checks();
    348         InitializeLoop(induction_data);
    349 
    350         while (current_base_check != NULL) {
    351           ProcessRelatedChecks(current_base_check, induction_data);
    352           while (current_base_check != NULL &&
    353                  current_base_check->processed()) {
    354             current_base_check = current_base_check->next();
    355           }
    356         }
    357 
    358         current_length_group = current_length_group->next();
    359       }
    360     }
    361   }
    362 
    363  private:
    364   HGraph* graph_;
    365   HBasicBlock* loop_header_;
    366   ZoneList<Element> elements_;
    367 };
    368 
    369 
    370 void HBoundsCheckHoistingPhase::HoistRedundantBoundsChecks() {
    371   InductionVariableBlocksTable table(graph());
    372   table.CollectInductionVariableData(graph()->entry_block());
    373   for (int i = 0; i < graph()->blocks()->length(); i++) {
    374     table.EliminateRedundantBoundsChecks(graph()->blocks()->at(i));
    375   }
    376 }
    377 
    378 }  // namespace internal
    379 }  // namespace v8
    380