| 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-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(graph()->isolate(), 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(graph()->isolate(), 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 graph()->isolate(), 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 internal | |
| 379 } // 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