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
7namespace v8 {
8namespace 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 */
25class 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 != 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
371void 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