| OLD | NEW |
|---|
| (Empty) |
| 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 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 | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 1405363003:
Move Hydrogen and Lithium to src/crankshaft/ (Closed)
Base URL: https://chromium.googlesource.com/v8/v8.git@master