hydrogen-bce.cc 17.7 KB
Newer Older
1
// Copyright 2013 the V8 project authors. All rights reserved.
2 3
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
4

5
#include "src/crankshaft/hydrogen-bce.h"
6 7 8 9

namespace v8 {
namespace internal {

10

11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49
// 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 {
 public:
  HValue* IndexBase() const { return index_base_; }
  HValue* Length() const { return length_; }

  uint32_t Hash() {
    return static_cast<uint32_t>(index_base_->Hashcode() ^ length_->Hashcode());
  }

  static BoundsCheckKey* Create(Zone* zone,
                                HBoundsCheck* check,
                                int32_t* offset) {
    if (!check->index()->representation().IsSmiOrInteger32()) return NULL;

    HValue* index_base = NULL;
    HConstant* constant = NULL;
    bool is_sub = false;

    if (check->index()->IsAdd()) {
      HAdd* index = HAdd::cast(check->index());
      if (index->left()->IsConstant()) {
        constant = HConstant::cast(index->left());
        index_base = index->right();
      } else if (index->right()->IsConstant()) {
        constant = HConstant::cast(index->right());
        index_base = index->left();
      }
    } else if (check->index()->IsSub()) {
      HSub* index = HSub::cast(check->index());
      is_sub = true;
50
      if (index->right()->IsConstant()) {
51 52 53
        constant = HConstant::cast(index->right());
        index_base = index->left();
      }
54 55 56
    } else if (check->index()->IsConstant()) {
      index_base = check->block()->graph()->GetConstant0();
      constant = HConstant::cast(check->index());
57 58
    }

59 60
    if (constant != NULL && constant->HasInteger32Value() &&
        constant->Integer32Value() != kMinInt) {
61 62 63 64 65 66 67 68 69 70 71 72
      *offset = is_sub ? - constant->Integer32Value()
                       : constant->Integer32Value();
    } else {
      *offset = 0;
      index_base = check->index();
    }

    return new(zone) BoundsCheckKey(index_base, check->length());
  }

 private:
  BoundsCheckKey(HValue* index_base, HValue* length)
73 74
      : index_base_(index_base),
        length_(length) { }
75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113

  HValue* index_base_;
  HValue* length_;

  DISALLOW_COPY_AND_ASSIGN(BoundsCheckKey);
};


// Data about each HBoundsCheck that can be eliminated or moved.
// It is the "value" in the dictionary indexed by "base-index, length"
// (the key is BoundsCheckKey).
// We scan the code with a dominator tree traversal.
// Traversing the dominator tree we keep a stack (implemented as a singly
// linked list) of "data" for each basic block that contains a relevant check
// with the same key (the dictionary holds the head of the list).
// We also keep all the "data" created for a given basic block in a list, and
// use it to "clean up" the dictionary when backtracking in the dominator tree
// traversal.
// Doing this each dictionary entry always directly points to the check that
// is dominating the code being examined now.
// We also track the current "offset" of the index expression and use it to
// decide if any check is already "covered" (so it can be removed) or not.
class BoundsCheckBbData: public ZoneObject {
 public:
  BoundsCheckKey* Key() const { return key_; }
  int32_t LowerOffset() const { return lower_offset_; }
  int32_t UpperOffset() const { return upper_offset_; }
  HBasicBlock* BasicBlock() const { return basic_block_; }
  HBoundsCheck* LowerCheck() const { return lower_check_; }
  HBoundsCheck* UpperCheck() const { return upper_check_; }
  BoundsCheckBbData* NextInBasicBlock() const { return next_in_bb_; }
  BoundsCheckBbData* FatherInDominatorTree() const { return father_in_dt_; }

  bool OffsetIsCovered(int32_t offset) const {
    return offset >= LowerOffset() && offset <= UpperOffset();
  }

  bool HasSingleCheck() { return lower_check_ == upper_check_; }

114 115 116
  void UpdateUpperOffsets(HBoundsCheck* check, int32_t offset) {
    BoundsCheckBbData* data = FatherInDominatorTree();
    while (data != NULL && data->UpperCheck() == check) {
117
      DCHECK(data->upper_offset_ < offset);
118 119 120 121 122 123 124 125
      data->upper_offset_ = offset;
      data = data->FatherInDominatorTree();
    }
  }

  void UpdateLowerOffsets(HBoundsCheck* check, int32_t offset) {
    BoundsCheckBbData* data = FatherInDominatorTree();
    while (data != NULL && data->LowerCheck() == check) {
126
      DCHECK(data->lower_offset_ > offset);
127 128 129 130 131
      data->lower_offset_ = offset;
      data = data->FatherInDominatorTree();
    }
  }

132 133 134 135 136 137 138 139 140 141 142 143
  // The goal of this method is to modify either upper_offset_ or
  // lower_offset_ so that also new_offset is covered (the covered
  // range grows).
  //
  // The precondition is that new_check follows UpperCheck() and
  // LowerCheck() in the same basic block, and that new_offset is not
  // covered (otherwise we could simply remove new_check).
  //
  // If HasSingleCheck() is true then new_check is added as "second check"
  // (either upper or lower; note that HasSingleCheck() becomes false).
  // Otherwise one of the current checks is modified so that it also covers
  // 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 148 149 150 151 152 153 154
    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 {
155
        TightenCheck(upper_check_, new_check, new_offset);
156
        UpdateUpperOffsets(upper_check_, upper_offset_);
157 158 159 160 161 162 163
      }
    } else if (new_offset < lower_offset_) {
      lower_offset_ = new_offset;
      if (HasSingleCheck()) {
        keep_new_check = true;
        lower_check_ = new_check;
      } else {
164
        TightenCheck(lower_check_, new_check, new_offset);
165
        UpdateLowerOffsets(lower_check_, lower_offset_);
166 167
      }
    } else {
168 169
      // Should never have called CoverCheck() in this case.
      UNREACHABLE();
170 171 172
    }

    if (!keep_new_check) {
173
      if (FLAG_trace_bce) {
174 175
        base::OS::Print("Eliminating check #%d after tightening\n",
                        new_check->id());
176
      }
177 178
      new_check->block()->graph()->isolate()->counters()->
          bounds_checks_eliminated()->Increment();
179
      new_check->DeleteAndReplaceWith(new_check->ActualValue());
180 181 182
    } else {
      HBoundsCheck* first_check = new_check == lower_check_ ? upper_check_
                                                            : lower_check_;
183
      if (FLAG_trace_bce) {
184 185
        base::OS::Print("Moving second check #%d after first check #%d\n",
                        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 190 191 192
      HInstruction* old_position = new_check->next();
      new_check->Unlink();
      new_check->InsertAfter(first_check);
      MoveIndexIfNecessary(new_check->index(), new_check, old_position);
193 194 195 196 197 198 199 200 201 202 203
    }
  }

  BoundsCheckBbData(BoundsCheckKey* key,
                    int32_t lower_offset,
                    int32_t upper_offset,
                    HBasicBlock* bb,
                    HBoundsCheck* lower_check,
                    HBoundsCheck* upper_check,
                    BoundsCheckBbData* next_in_bb,
                    BoundsCheckBbData* father_in_dt)
204 205 206 207 208 209 210 211
      : key_(key),
        lower_offset_(lower_offset),
        upper_offset_(upper_offset),
        basic_block_(bb),
        lower_check_(lower_check),
        upper_check_(upper_check),
        next_in_bb_(next_in_bb),
        father_in_dt_(father_in_dt) { }
212 213 214 215 216 217 218 219 220 221 222

 private:
  BoundsCheckKey* key_;
  int32_t lower_offset_;
  int32_t upper_offset_;
  HBasicBlock* basic_block_;
  HBoundsCheck* lower_check_;
  HBoundsCheck* upper_check_;
  BoundsCheckBbData* next_in_bb_;
  BoundsCheckBbData* father_in_dt_;

223 224 225
  void MoveIndexIfNecessary(HValue* index_raw,
                            HBoundsCheck* insert_before,
                            HInstruction* end_of_scan_range) {
226 227 228 229 230 231 232 233
    // index_raw can be HAdd(index_base, offset), HSub(index_base, offset),
    // HConstant(offset) or index_base directly.
    // In the latter case, no need to move anything.
    if (index_raw->IsAdd() || index_raw->IsSub()) {
      HArithmeticBinaryOperation* index =
          HArithmeticBinaryOperation::cast(index_raw);
      HValue* left_input = index->left();
      HValue* right_input = index->right();
234
      HValue* context = index->context();
235 236 237
      bool must_move_index = false;
      bool must_move_left_input = false;
      bool must_move_right_input = false;
238
      bool must_move_context = false;
239 240 241
      for (HInstruction* cursor = end_of_scan_range; cursor != insert_before;) {
        if (cursor == left_input) must_move_left_input = true;
        if (cursor == right_input) must_move_right_input = true;
242
        if (cursor == context) must_move_context = true;
243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263
        if (cursor == index) must_move_index = true;
        if (cursor->previous() == NULL) {
          cursor = cursor->block()->dominator()->end();
        } else {
          cursor = cursor->previous();
        }
      }
      if (must_move_index) {
        index->Unlink();
        index->InsertBefore(insert_before);
      }
      // The BCE algorithm only selects mergeable bounds checks that share
      // the same "index_base", so we'll only ever have to move constants.
      if (must_move_left_input) {
        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);
      }
264 265 266 267 268
      if (must_move_context) {
        // Contexts are always constants.
        HConstant::cast(context)->Unlink();
        HConstant::cast(context)->InsertBefore(index);
      }
269 270 271 272 273 274 275 276 277 278 279 280 281 282
    } else if (index_raw->IsConstant()) {
      HConstant* index = HConstant::cast(index_raw);
      bool must_move = false;
      for (HInstruction* cursor = end_of_scan_range; cursor != insert_before;) {
        if (cursor == index) must_move = true;
        if (cursor->previous() == NULL) {
          cursor = cursor->block()->dominator()->end();
        } else {
          cursor = cursor->previous();
        }
      }
      if (must_move) {
        index->Unlink();
        index->InsertBefore(insert_before);
283
      }
284 285 286
    }
  }

287
  void TightenCheck(HBoundsCheck* original_check,
288 289
                    HBoundsCheck* tighter_check,
                    int32_t new_offset) {
290
    DCHECK(original_check->length() == tighter_check->length());
291 292 293
    MoveIndexIfNecessary(tighter_check->index(), original_check, tighter_check);
    original_check->ReplaceAllUsesWith(original_check->index());
    original_check->SetOperandAt(0, tighter_check->index());
294
    if (FLAG_trace_bce) {
295 296
      base::OS::Print("Tightened check #%d with offset %d from #%d\n",
                      original_check->id(), new_offset, tighter_check->id());
297
    }
298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318
  }

  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();
}


BoundsCheckTable::BoundsCheckTable(Zone* zone)
    : ZoneHashMap(BoundsCheckKeyMatch, ZoneHashMap::kDefaultHashMapCapacity,
                  ZoneAllocationPolicy(zone)) { }


BoundsCheckBbData** BoundsCheckTable::LookupOrInsert(BoundsCheckKey* key,
                                                     Zone* zone) {
  return reinterpret_cast<BoundsCheckBbData**>(
319 320
      &(ZoneHashMap::LookupOrInsert(key, key->Hash(),
                                    ZoneAllocationPolicy(zone))->value));
321 322 323 324 325 326
}


void BoundsCheckTable::Insert(BoundsCheckKey* key,
                              BoundsCheckBbData* data,
                              Zone* zone) {
327 328
  ZoneHashMap::LookupOrInsert(key, key->Hash(), ZoneAllocationPolicy(zone))
      ->value = data;
329 330 331 332 333 334 335 336
}


void BoundsCheckTable::Delete(BoundsCheckKey* key) {
  Remove(key, key->Hash());
}


337 338 339 340 341 342 343 344
class HBoundsCheckEliminationState {
 public:
  HBasicBlock* block_;
  BoundsCheckBbData* bb_data_list_;
  int index_;
};


345 346 347 348 349 350
// Eliminates checks in bb and recursively in the dominated blocks.
// Also replace the results of check instructions with the original value, if
// the result is used. This is safe now, since we don't do code motion after
// this point. It enables better register allocation since the value produced
// by check instructions is really a copy of the original value.
void HBoundsCheckEliminationPhase::EliminateRedundantBoundsChecks(
351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384
    HBasicBlock* entry) {
  // Allocate the stack.
  HBoundsCheckEliminationState* stack =
    zone()->NewArray<HBoundsCheckEliminationState>(graph()->blocks()->length());

  // Explicitly push the entry block.
  stack[0].block_ = entry;
  stack[0].bb_data_list_ = PreProcessBlock(entry);
  stack[0].index_ = 0;
  int stack_depth = 1;

  // Implement depth-first traversal with a stack.
  while (stack_depth > 0) {
    int current = stack_depth - 1;
    HBoundsCheckEliminationState* state = &stack[current];
    const ZoneList<HBasicBlock*>* children = state->block_->dominated_blocks();

    if (state->index_ < children->length()) {
      // Recursively visit children blocks.
      HBasicBlock* child = children->at(state->index_++);
      int next = stack_depth++;
      stack[next].block_ = child;
      stack[next].bb_data_list_ = PreProcessBlock(child);
      stack[next].index_ = 0;
    } else {
      // Finished with all children; post process the block.
      PostProcessBlock(state->block_, state->bb_data_list_);
      stack_depth--;
    }
  }
}


BoundsCheckBbData* HBoundsCheckEliminationPhase::PreProcessBlock(
385 386 387 388 389 390 391 392
    HBasicBlock* bb) {
  BoundsCheckBbData* bb_data_list = NULL;

  for (HInstructionIterator it(bb); !it.Done(); it.Advance()) {
    HInstruction* i = it.Current();
    if (!i->IsBoundsCheck()) continue;

    HBoundsCheck* check = HBoundsCheck::cast(i);
393
    int32_t offset = 0;
394 395 396 397 398 399 400 401 402 403 404 405 406 407 408
    BoundsCheckKey* key =
        BoundsCheckKey::Create(zone(), check, &offset);
    if (key == NULL) continue;
    BoundsCheckBbData** data_p = table_.LookupOrInsert(key, zone());
    BoundsCheckBbData* data = *data_p;
    if (data == NULL) {
      bb_data_list = new(zone()) BoundsCheckBbData(key,
                                                   offset,
                                                   offset,
                                                   bb,
                                                   check,
                                                   check,
                                                   bb_data_list,
                                                   NULL);
      *data_p = bb_data_list;
409
      if (FLAG_trace_bce) {
410 411
        base::OS::Print("Fresh bounds check data for block #%d: [%d]\n",
                        bb->block_id(), offset);
412
      }
413
    } else if (data->OffsetIsCovered(offset)) {
414 415
      bb->graph()->isolate()->counters()->
          bounds_checks_eliminated()->Increment();
416
      if (FLAG_trace_bce) {
417 418
        base::OS::Print("Eliminating bounds check #%d, offset %d is covered\n",
                        check->id(), offset);
419
      }
420
      check->DeleteAndReplaceWith(check->ActualValue());
421
    } else if (data->BasicBlock() == bb) {
422 423 424 425 426 427 428 429 430 431 432 433 434
      // 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.
435
      data->CoverCheck(check, offset);
436 437
    } else if (graph()->use_optimistic_licm() ||
               bb->IsLoopSuccessorDominator()) {
438 439 440 441 442 443 444 445 446 447 448 449 450 451
      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);
452
      if (FLAG_trace_bce) {
453 454
        base::OS::Print("Updated bounds check data for block #%d: [%d - %d]\n",
                        bb->block_id(), new_lower_offset, new_upper_offset);
455
      }
456 457 458 459
      table_.Insert(key, bb_data_list, zone());
    }
  }

460 461 462
  return bb_data_list;
}

463

464 465 466
void HBoundsCheckEliminationPhase::PostProcessBlock(
    HBasicBlock* block, BoundsCheckBbData* data) {
  while (data != NULL) {
467 468 469 470 471
    if (data->FatherInDominatorTree()) {
      table_.Insert(data->Key(), data->FatherInDominatorTree(), zone());
    } else {
      table_.Delete(data->Key());
    }
472
    data = data->NextInBasicBlock();
473 474 475
  }
}

476 477
}  // namespace internal
}  // namespace v8