src/v8/src/hydrogen-bch.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-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(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(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         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 v8::internal