Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 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/crankshaft/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 |