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 ASSERT(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 ASSERT(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 ASSERT(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 != NULL && 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 && 246 check->HasUpperLimit() && 247 check->upper_limit() == upper_constant_limit; 248 counters()->bounds_checks_eliminated()->Increment(); 249 current_check->check()->set_skip_check(); 250 } 251 252 // Choose the appropriate limit. 253 Zone* zone = graph()->zone(); 254 HValue* context = graph()->GetInvalidContext(); 255 HValue* limit = data->limit(); 256 if (has_upper_constant_limit) { 257 HConstant* new_limit = HConstant::New(zone, context, 258 upper_constant_limit); 259 new_limit->InsertBefore(pre_header->end()); 260 limit = new_limit; 261 } 262 263 // If necessary, redefine the limit in the preheader. 264 if (limit->IsInteger32Constant() && 265 limit->block() != pre_header && 266 !limit->block()->Dominates(pre_header)) { 267 HConstant* new_limit = HConstant::New(zone, context, 268 limit->GetInteger32Constant()); 269 new_limit->InsertBefore(pre_header->end()); 270 limit = new_limit; 271 } 272 273 // Do the hoisting. 274 HBoundsCheck* hoisted_check = HBoundsCheck::New( 275 zone, context, limit, check->check()->length()); 276 hoisted_check->InsertBefore(pre_header->end()); 277 hoisted_check->set_allow_equality(true); 278 counters()->bounds_checks_hoisted()->Increment(); 279 } 280 281 void CollectInductionVariableData(HBasicBlock* bb) { 282 bool additional_limit = false; 283 284 for (int i = 0; i < bb->phis()->length(); i++) { 285 HPhi* phi = bb->phis()->at(i); 286 phi->DetectInductionVariable(); 287 } 288 289 additional_limit = InductionVariableData::ComputeInductionVariableLimit( 290 bb, at(bb)->additional_limit()); 291 292 if (additional_limit) { 293 at(bb)->additional_limit()->updated_variable-> 294 UpdateAdditionalLimit(at(bb)->additional_limit()); 295 } 296 297 for (HInstruction* i = bb->first(); i != NULL; i = i->next()) { 298 if (!i->IsBoundsCheck()) continue; 299 HBoundsCheck* check = HBoundsCheck::cast(i); 300 InductionVariableData::BitwiseDecompositionResult decomposition; 301 InductionVariableData::DecomposeBitwise(check->index(), &decomposition); 302 if (!decomposition.base->IsPhi()) continue; 303 HPhi* phi = HPhi::cast(decomposition.base); 304 305 if (!phi->IsInductionVariable()) continue; 306 InductionVariableData* data = phi->induction_variable_data(); 307 308 // For now ignore loops decrementing the index. 309 if (data->increment() <= 0) continue; 310 if (!data->LowerLimitIsNonNegativeConstant()) continue; 311 312 // TODO(mmassi): skip OSR values for check->length(). 313 if (check->length() == data->limit() || 314 check->length() == data->additional_upper_limit()) { 315 counters()->bounds_checks_eliminated()->Increment(); 316 check->set_skip_check(); 317 continue; 318 } 319 320 if (!phi->IsLimitedInductionVariable()) continue; 321 322 int32_t limit = data->ComputeUpperLimit(decomposition.and_mask, 323 decomposition.or_mask); 324 phi->induction_variable_data()->AddCheck(check, limit); 325 } 326 327 for (int i = 0; i < bb->dominated_blocks()->length(); i++) { 328 CollectInductionVariableData(bb->dominated_blocks()->at(i)); 329 } 330 331 if (additional_limit) { 332 at(bb->block_id())->additional_limit()->updated_variable-> 333 UpdateAdditionalLimit(at(bb->block_id())->additional_limit()); 334 } 335 } 336 337 void EliminateRedundantBoundsChecks(HBasicBlock* bb) { 338 for (int i = 0; i < bb->phis()->length(); i++) { 339 HPhi* phi = bb->phis()->at(i); 340 if (!phi->IsLimitedInductionVariable()) continue; 341 342 InductionVariableData* induction_data = phi->induction_variable_data(); 343 InductionVariableData::ChecksRelatedToLength* current_length_group = 344 induction_data->checks(); 345 while (current_length_group != NULL) { 346 current_length_group->CloseCurrentBlock(); 347 InductionVariableData::InductionVariableCheck* current_base_check = 348 current_length_group->checks(); 349 InitializeLoop(induction_data); 350 351 while (current_base_check != NULL) { 352 ProcessRelatedChecks(current_base_check, induction_data); 353 while (current_base_check != NULL && 354 current_base_check->processed()) { 355 current_base_check = current_base_check->next(); 356 } 357 } 358 359 current_length_group = current_length_group->next(); 360 } 361 } 362 } 363 364 private: 365 HGraph* graph_; 366 HBasicBlock* loop_header_; 367 ZoneList<Element> elements_; 368 }; 369 370 371 void HBoundsCheckHoistingPhase::HoistRedundantBoundsChecks() { 372 InductionVariableBlocksTable table(graph()); 373 table.CollectInductionVariableData(graph()->entry_block()); 374 for (int i = 0; i < graph()->blocks()->length(); i++) { 375 table.EliminateRedundantBoundsChecks(graph()->blocks()->at(i)); 376 } 377 } 378 379 } } // namespace v8::internal 380