1// Copyright 2013 the V8 project authors. All rights reserved. 2// Redistribution and use in source and binary forms, with or without 3// modification, are permitted provided that the following conditions are 4// met: 5// 6// * Redistributions of source code must retain the above copyright 7// notice, this list of conditions and the following disclaimer. 8// * Redistributions in binary form must reproduce the above 9// copyright notice, this list of conditions and the following 10// disclaimer in the documentation and/or other materials provided 11// with the distribution. 12// * Neither the name of Google Inc. nor the names of its 13// contributors may be used to endorse or promote products derived 14// from this software without specific prior written permission. 15// 16// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 17// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 18// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 19// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 20// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 21// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 22// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 26// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27 28#include "hydrogen-bce.h" 29 30namespace v8 { 31namespace internal { 32 33// We try to "factor up" HBoundsCheck instructions towards the root of the 34// dominator tree. 35// For now we handle checks where the index is like "exp + int32value". 36// If in the dominator tree we check "exp + v1" and later (dominated) 37// "exp + v2", if v2 <= v1 we can safely remove the second check, and if 38// v2 > v1 we can use v2 in the 1st check and again remove the second. 39// To do so we keep a dictionary of all checks where the key if the pair 40// "exp, length". 41// The class BoundsCheckKey represents this key. 42class BoundsCheckKey : public ZoneObject { 43 public: 44 HValue* IndexBase() const { return index_base_; } 45 HValue* Length() const { return length_; } 46 47 uint32_t Hash() { 48 return static_cast<uint32_t>(index_base_->Hashcode() ^ length_->Hashcode()); 49 } 50 51 static BoundsCheckKey* Create(Zone* zone, 52 HBoundsCheck* check, 53 int32_t* offset) { 54 if (!check->index()->representation().IsSmiOrInteger32()) return NULL; 55 56 HValue* index_base = NULL; 57 HConstant* constant = NULL; 58 bool is_sub = false; 59 60 if (check->index()->IsAdd()) { 61 HAdd* index = HAdd::cast(check->index()); 62 if (index->left()->IsConstant()) { 63 constant = HConstant::cast(index->left()); 64 index_base = index->right(); 65 } else if (index->right()->IsConstant()) { 66 constant = HConstant::cast(index->right()); 67 index_base = index->left(); 68 } 69 } else if (check->index()->IsSub()) { 70 HSub* index = HSub::cast(check->index()); 71 is_sub = true; 72 if (index->left()->IsConstant()) { 73 constant = HConstant::cast(index->left()); 74 index_base = index->right(); 75 } else if (index->right()->IsConstant()) { 76 constant = HConstant::cast(index->right()); 77 index_base = index->left(); 78 } 79 } 80 81 if (constant != NULL && constant->HasInteger32Value()) { 82 *offset = is_sub ? - constant->Integer32Value() 83 : constant->Integer32Value(); 84 } else { 85 *offset = 0; 86 index_base = check->index(); 87 } 88 89 return new(zone) BoundsCheckKey(index_base, check->length()); 90 } 91 92 private: 93 BoundsCheckKey(HValue* index_base, HValue* length) 94 : index_base_(index_base), 95 length_(length) { } 96 97 HValue* index_base_; 98 HValue* length_; 99 100 DISALLOW_COPY_AND_ASSIGN(BoundsCheckKey); 101}; 102 103 104// Data about each HBoundsCheck that can be eliminated or moved. 105// It is the "value" in the dictionary indexed by "base-index, length" 106// (the key is BoundsCheckKey). 107// We scan the code with a dominator tree traversal. 108// Traversing the dominator tree we keep a stack (implemented as a singly 109// linked list) of "data" for each basic block that contains a relevant check 110// with the same key (the dictionary holds the head of the list). 111// We also keep all the "data" created for a given basic block in a list, and 112// use it to "clean up" the dictionary when backtracking in the dominator tree 113// traversal. 114// Doing this each dictionary entry always directly points to the check that 115// is dominating the code being examined now. 116// We also track the current "offset" of the index expression and use it to 117// decide if any check is already "covered" (so it can be removed) or not. 118class BoundsCheckBbData: public ZoneObject { 119 public: 120 BoundsCheckKey* Key() const { return key_; } 121 int32_t LowerOffset() const { return lower_offset_; } 122 int32_t UpperOffset() const { return upper_offset_; } 123 HBasicBlock* BasicBlock() const { return basic_block_; } 124 HBoundsCheck* LowerCheck() const { return lower_check_; } 125 HBoundsCheck* UpperCheck() const { return upper_check_; } 126 BoundsCheckBbData* NextInBasicBlock() const { return next_in_bb_; } 127 BoundsCheckBbData* FatherInDominatorTree() const { return father_in_dt_; } 128 129 bool OffsetIsCovered(int32_t offset) const { 130 return offset >= LowerOffset() && offset <= UpperOffset(); 131 } 132 133 bool HasSingleCheck() { return lower_check_ == upper_check_; } 134 135 // The goal of this method is to modify either upper_offset_ or 136 // lower_offset_ so that also new_offset is covered (the covered 137 // range grows). 138 // 139 // The precondition is that new_check follows UpperCheck() and 140 // LowerCheck() in the same basic block, and that new_offset is not 141 // covered (otherwise we could simply remove new_check). 142 // 143 // If HasSingleCheck() is true then new_check is added as "second check" 144 // (either upper or lower; note that HasSingleCheck() becomes false). 145 // Otherwise one of the current checks is modified so that it also covers 146 // new_offset, and new_check is removed. 147 // 148 // If the check cannot be modified because the context is unknown it 149 // returns false, otherwise it returns true. 150 bool CoverCheck(HBoundsCheck* new_check, 151 int32_t new_offset) { 152 ASSERT(new_check->index()->representation().IsSmiOrInteger32()); 153 bool keep_new_check = false; 154 155 if (new_offset > upper_offset_) { 156 upper_offset_ = new_offset; 157 if (HasSingleCheck()) { 158 keep_new_check = true; 159 upper_check_ = new_check; 160 } else { 161 bool result = BuildOffsetAdd(upper_check_, 162 &added_upper_index_, 163 &added_upper_offset_, 164 Key()->IndexBase(), 165 new_check->index()->representation(), 166 new_offset); 167 if (!result) return false; 168 upper_check_->ReplaceAllUsesWith(upper_check_->index()); 169 upper_check_->SetOperandAt(0, added_upper_index_); 170 } 171 } else if (new_offset < lower_offset_) { 172 lower_offset_ = new_offset; 173 if (HasSingleCheck()) { 174 keep_new_check = true; 175 lower_check_ = new_check; 176 } else { 177 bool result = BuildOffsetAdd(lower_check_, 178 &added_lower_index_, 179 &added_lower_offset_, 180 Key()->IndexBase(), 181 new_check->index()->representation(), 182 new_offset); 183 if (!result) return false; 184 lower_check_->ReplaceAllUsesWith(lower_check_->index()); 185 lower_check_->SetOperandAt(0, added_lower_index_); 186 } 187 } else { 188 ASSERT(false); 189 } 190 191 if (!keep_new_check) { 192 new_check->block()->graph()->isolate()->counters()-> 193 bounds_checks_eliminated()->Increment(); 194 new_check->DeleteAndReplaceWith(new_check->ActualValue()); 195 } 196 197 return true; 198 } 199 200 void RemoveZeroOperations() { 201 RemoveZeroAdd(&added_lower_index_, &added_lower_offset_); 202 RemoveZeroAdd(&added_upper_index_, &added_upper_offset_); 203 } 204 205 BoundsCheckBbData(BoundsCheckKey* key, 206 int32_t lower_offset, 207 int32_t upper_offset, 208 HBasicBlock* bb, 209 HBoundsCheck* lower_check, 210 HBoundsCheck* upper_check, 211 BoundsCheckBbData* next_in_bb, 212 BoundsCheckBbData* father_in_dt) 213 : key_(key), 214 lower_offset_(lower_offset), 215 upper_offset_(upper_offset), 216 basic_block_(bb), 217 lower_check_(lower_check), 218 upper_check_(upper_check), 219 added_lower_index_(NULL), 220 added_lower_offset_(NULL), 221 added_upper_index_(NULL), 222 added_upper_offset_(NULL), 223 next_in_bb_(next_in_bb), 224 father_in_dt_(father_in_dt) { } 225 226 private: 227 BoundsCheckKey* key_; 228 int32_t lower_offset_; 229 int32_t upper_offset_; 230 HBasicBlock* basic_block_; 231 HBoundsCheck* lower_check_; 232 HBoundsCheck* upper_check_; 233 HInstruction* added_lower_index_; 234 HConstant* added_lower_offset_; 235 HInstruction* added_upper_index_; 236 HConstant* added_upper_offset_; 237 BoundsCheckBbData* next_in_bb_; 238 BoundsCheckBbData* father_in_dt_; 239 240 // Given an existing add instruction and a bounds check it tries to 241 // find the current context (either of the add or of the check index). 242 HValue* IndexContext(HInstruction* add, HBoundsCheck* check) { 243 if (add != NULL && add->IsAdd()) { 244 return HAdd::cast(add)->context(); 245 } 246 if (check->index()->IsBinaryOperation()) { 247 return HBinaryOperation::cast(check->index())->context(); 248 } 249 return NULL; 250 } 251 252 // This function returns false if it cannot build the add because the 253 // current context cannot be determined. 254 bool BuildOffsetAdd(HBoundsCheck* check, 255 HInstruction** add, 256 HConstant** constant, 257 HValue* original_value, 258 Representation representation, 259 int32_t new_offset) { 260 HValue* index_context = IndexContext(*add, check); 261 if (index_context == NULL) return false; 262 263 Zone* zone = BasicBlock()->zone(); 264 HConstant* new_constant = HConstant::New(zone, index_context, 265 new_offset, representation); 266 if (*add == NULL) { 267 new_constant->InsertBefore(check); 268 (*add) = HAdd::New(zone, index_context, original_value, new_constant); 269 (*add)->AssumeRepresentation(representation); 270 (*add)->InsertBefore(check); 271 } else { 272 new_constant->InsertBefore(*add); 273 (*constant)->DeleteAndReplaceWith(new_constant); 274 } 275 *constant = new_constant; 276 return true; 277 } 278 279 void RemoveZeroAdd(HInstruction** add, HConstant** constant) { 280 if (*add != NULL && (*add)->IsAdd() && (*constant)->Integer32Value() == 0) { 281 (*add)->DeleteAndReplaceWith(HAdd::cast(*add)->left()); 282 (*constant)->DeleteAndReplaceWith(NULL); 283 } 284 } 285 286 DISALLOW_COPY_AND_ASSIGN(BoundsCheckBbData); 287}; 288 289 290static bool BoundsCheckKeyMatch(void* key1, void* key2) { 291 BoundsCheckKey* k1 = static_cast<BoundsCheckKey*>(key1); 292 BoundsCheckKey* k2 = static_cast<BoundsCheckKey*>(key2); 293 return k1->IndexBase() == k2->IndexBase() && k1->Length() == k2->Length(); 294} 295 296 297BoundsCheckTable::BoundsCheckTable(Zone* zone) 298 : ZoneHashMap(BoundsCheckKeyMatch, ZoneHashMap::kDefaultHashMapCapacity, 299 ZoneAllocationPolicy(zone)) { } 300 301 302BoundsCheckBbData** BoundsCheckTable::LookupOrInsert(BoundsCheckKey* key, 303 Zone* zone) { 304 return reinterpret_cast<BoundsCheckBbData**>( 305 &(Lookup(key, key->Hash(), true, ZoneAllocationPolicy(zone))->value)); 306} 307 308 309void BoundsCheckTable::Insert(BoundsCheckKey* key, 310 BoundsCheckBbData* data, 311 Zone* zone) { 312 Lookup(key, key->Hash(), true, ZoneAllocationPolicy(zone))->value = data; 313} 314 315 316void BoundsCheckTable::Delete(BoundsCheckKey* key) { 317 Remove(key, key->Hash()); 318} 319 320 321class HBoundsCheckEliminationState { 322 public: 323 HBasicBlock* block_; 324 BoundsCheckBbData* bb_data_list_; 325 int index_; 326}; 327 328 329// Eliminates checks in bb and recursively in the dominated blocks. 330// Also replace the results of check instructions with the original value, if 331// the result is used. This is safe now, since we don't do code motion after 332// this point. It enables better register allocation since the value produced 333// by check instructions is really a copy of the original value. 334void HBoundsCheckEliminationPhase::EliminateRedundantBoundsChecks( 335 HBasicBlock* entry) { 336 // Allocate the stack. 337 HBoundsCheckEliminationState* stack = 338 zone()->NewArray<HBoundsCheckEliminationState>(graph()->blocks()->length()); 339 340 // Explicitly push the entry block. 341 stack[0].block_ = entry; 342 stack[0].bb_data_list_ = PreProcessBlock(entry); 343 stack[0].index_ = 0; 344 int stack_depth = 1; 345 346 // Implement depth-first traversal with a stack. 347 while (stack_depth > 0) { 348 int current = stack_depth - 1; 349 HBoundsCheckEliminationState* state = &stack[current]; 350 const ZoneList<HBasicBlock*>* children = state->block_->dominated_blocks(); 351 352 if (state->index_ < children->length()) { 353 // Recursively visit children blocks. 354 HBasicBlock* child = children->at(state->index_++); 355 int next = stack_depth++; 356 stack[next].block_ = child; 357 stack[next].bb_data_list_ = PreProcessBlock(child); 358 stack[next].index_ = 0; 359 } else { 360 // Finished with all children; post process the block. 361 PostProcessBlock(state->block_, state->bb_data_list_); 362 stack_depth--; 363 } 364 } 365} 366 367 368BoundsCheckBbData* HBoundsCheckEliminationPhase::PreProcessBlock( 369 HBasicBlock* bb) { 370 BoundsCheckBbData* bb_data_list = NULL; 371 372 for (HInstructionIterator it(bb); !it.Done(); it.Advance()) { 373 HInstruction* i = it.Current(); 374 if (!i->IsBoundsCheck()) continue; 375 376 HBoundsCheck* check = HBoundsCheck::cast(i); 377 int32_t offset; 378 BoundsCheckKey* key = 379 BoundsCheckKey::Create(zone(), check, &offset); 380 if (key == NULL) continue; 381 BoundsCheckBbData** data_p = table_.LookupOrInsert(key, zone()); 382 BoundsCheckBbData* data = *data_p; 383 if (data == NULL) { 384 bb_data_list = new(zone()) BoundsCheckBbData(key, 385 offset, 386 offset, 387 bb, 388 check, 389 check, 390 bb_data_list, 391 NULL); 392 *data_p = bb_data_list; 393 } else if (data->OffsetIsCovered(offset)) { 394 bb->graph()->isolate()->counters()-> 395 bounds_checks_eliminated()->Increment(); 396 check->DeleteAndReplaceWith(check->ActualValue()); 397 } else if (data->BasicBlock() != bb || 398 !data->CoverCheck(check, offset)) { 399 // If the check is in the current BB we try to modify it by calling 400 // "CoverCheck", but if also that fails we record the current offsets 401 // in a new data instance because from now on they are covered. 402 int32_t new_lower_offset = offset < data->LowerOffset() 403 ? offset 404 : data->LowerOffset(); 405 int32_t new_upper_offset = offset > data->UpperOffset() 406 ? offset 407 : data->UpperOffset(); 408 bb_data_list = new(zone()) BoundsCheckBbData(key, 409 new_lower_offset, 410 new_upper_offset, 411 bb, 412 data->LowerCheck(), 413 data->UpperCheck(), 414 bb_data_list, 415 data); 416 table_.Insert(key, bb_data_list, zone()); 417 } 418 } 419 420 return bb_data_list; 421} 422 423 424void HBoundsCheckEliminationPhase::PostProcessBlock( 425 HBasicBlock* block, BoundsCheckBbData* data) { 426 while (data != NULL) { 427 data->RemoveZeroOperations(); 428 if (data->FatherInDominatorTree()) { 429 table_.Insert(data->Key(), data->FatherInDominatorTree(), zone()); 430 } else { 431 table_.Delete(data->Key()); 432 } 433 data = data->NextInBasicBlock(); 434 } 435} 436 437} } // namespace v8::internal 438