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