Line data Source code
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-bce.h"
6 : #include "src/objects-inl.h"
7 :
8 : namespace v8 {
9 : namespace internal {
10 :
11 :
12 : // We try to "factor up" HBoundsCheck instructions towards the root of the
13 : // dominator tree.
14 : // For now we handle checks where the index is like "exp + int32value".
15 : // If in the dominator tree we check "exp + v1" and later (dominated)
16 : // "exp + v2", if v2 <= v1 we can safely remove the second check, and if
17 : // v2 > v1 we can use v2 in the 1st check and again remove the second.
18 : // To do so we keep a dictionary of all checks where the key if the pair
19 : // "exp, length".
20 : // The class BoundsCheckKey represents this key.
21 : class BoundsCheckKey : public ZoneObject {
22 : public:
23 : HValue* IndexBase() const { return index_base_; }
24 : HValue* Length() const { return length_; }
25 :
26 67043 : uint32_t Hash() {
27 67043 : return static_cast<uint32_t>(index_base_->Hashcode() ^ length_->Hashcode());
28 : }
29 :
30 34296 : static BoundsCheckKey* Create(Zone* zone,
31 : HBoundsCheck* check,
32 : int32_t* offset) {
33 34296 : if (!check->index()->representation().IsSmiOrInteger32()) return NULL;
34 :
35 : HValue* index_base = NULL;
36 43916 : HConstant* constant = NULL;
37 : bool is_sub = false;
38 :
39 34298 : if (check->index()->IsAdd()) {
40 : HAdd* index = HAdd::cast(check->index());
41 8353 : if (index->left()->IsConstant()) {
42 : constant = HConstant::cast(index->left());
43 : index_base = index->right();
44 6377 : } else if (index->right()->IsConstant()) {
45 : constant = HConstant::cast(index->right());
46 : index_base = index->left();
47 : }
48 25944 : } else if (check->index()->IsSub()) {
49 : HSub* index = HSub::cast(check->index());
50 : is_sub = true;
51 710 : if (index->right()->IsConstant()) {
52 : constant = HConstant::cast(index->right());
53 : index_base = index->left();
54 : }
55 25235 : } else if (check->index()->IsConstant()) {
56 5698 : index_base = check->block()->graph()->GetConstant0();
57 : constant = HConstant::cast(check->index());
58 : }
59 :
60 63578 : if (constant != NULL && constant->HasInteger32Value() &&
61 : constant->Integer32Value() != kMinInt) {
62 : *offset = is_sub ? - constant->Integer32Value()
63 29970 : : constant->Integer32Value();
64 : } else {
65 19662 : *offset = 0;
66 : index_base = check->index();
67 : }
68 :
69 34298 : return new(zone) BoundsCheckKey(index_base, check->length());
70 : }
71 :
72 : private:
73 : BoundsCheckKey(HValue* index_base, HValue* length)
74 : : index_base_(index_base),
75 34298 : length_(length) { }
76 :
77 : HValue* index_base_;
78 : HValue* length_;
79 :
80 : DISALLOW_COPY_AND_ASSIGN(BoundsCheckKey);
81 : };
82 :
83 :
84 : // Data about each HBoundsCheck that can be eliminated or moved.
85 : // It is the "value" in the dictionary indexed by "base-index, length"
86 : // (the key is BoundsCheckKey).
87 : // We scan the code with a dominator tree traversal.
88 : // Traversing the dominator tree we keep a stack (implemented as a singly
89 : // linked list) of "data" for each basic block that contains a relevant check
90 : // with the same key (the dictionary holds the head of the list).
91 : // We also keep all the "data" created for a given basic block in a list, and
92 : // use it to "clean up" the dictionary when backtracking in the dominator tree
93 : // traversal.
94 : // Doing this each dictionary entry always directly points to the check that
95 : // is dominating the code being examined now.
96 : // We also track the current "offset" of the index expression and use it to
97 : // decide if any check is already "covered" (so it can be removed) or not.
98 : class BoundsCheckBbData: public ZoneObject {
99 : public:
100 : BoundsCheckKey* Key() const { return key_; }
101 : int32_t LowerOffset() const { return lower_offset_; }
102 : int32_t UpperOffset() const { return upper_offset_; }
103 : HBasicBlock* BasicBlock() const { return basic_block_; }
104 : HBoundsCheck* LowerCheck() const { return lower_check_; }
105 : HBoundsCheck* UpperCheck() const { return upper_check_; }
106 : BoundsCheckBbData* NextInBasicBlock() const { return next_in_bb_; }
107 : BoundsCheckBbData* FatherInDominatorTree() const { return father_in_dt_; }
108 :
109 4129 : bool OffsetIsCovered(int32_t offset) const {
110 4129 : return offset >= LowerOffset() && offset <= UpperOffset();
111 : }
112 :
113 : bool HasSingleCheck() { return lower_check_ == upper_check_; }
114 :
115 835 : void UpdateUpperOffsets(HBoundsCheck* check, int32_t offset) {
116 26 : BoundsCheckBbData* data = FatherInDominatorTree();
117 861 : while (data != NULL && data->UpperCheck() == check) {
118 : DCHECK(data->upper_offset_ < offset);
119 13 : data->upper_offset_ = offset;
120 : data = data->FatherInDominatorTree();
121 : }
122 : }
123 :
124 96 : void UpdateLowerOffsets(HBoundsCheck* check, int32_t offset) {
125 34 : BoundsCheckBbData* data = FatherInDominatorTree();
126 130 : while (data != NULL && data->LowerCheck() == check) {
127 : DCHECK(data->lower_offset_ > offset);
128 17 : data->lower_offset_ = offset;
129 : data = data->FatherInDominatorTree();
130 : }
131 : }
132 :
133 : // The goal of this method is to modify either upper_offset_ or
134 : // lower_offset_ so that also new_offset is covered (the covered
135 : // range grows).
136 : //
137 : // The precondition is that new_check follows UpperCheck() and
138 : // LowerCheck() in the same basic block, and that new_offset is not
139 : // covered (otherwise we could simply remove new_check).
140 : //
141 : // If HasSingleCheck() is true then new_check is added as "second check"
142 : // (either upper or lower; note that HasSingleCheck() becomes false).
143 : // Otherwise one of the current checks is modified so that it also covers
144 : // new_offset, and new_check is removed.
145 1605 : void CoverCheck(HBoundsCheck* new_check,
146 1605 : int32_t new_offset) {
147 : DCHECK(new_check->index()->representation().IsSmiOrInteger32());
148 : bool keep_new_check = false;
149 :
150 1605 : if (new_offset > upper_offset_) {
151 1374 : upper_offset_ = new_offset;
152 1374 : if (HasSingleCheck()) {
153 : keep_new_check = true;
154 539 : upper_check_ = new_check;
155 : } else {
156 835 : TightenCheck(upper_check_, new_check, new_offset);
157 835 : UpdateUpperOffsets(upper_check_, upper_offset_);
158 : }
159 231 : } else if (new_offset < lower_offset_) {
160 231 : lower_offset_ = new_offset;
161 231 : if (HasSingleCheck()) {
162 : keep_new_check = true;
163 135 : lower_check_ = new_check;
164 : } else {
165 96 : TightenCheck(lower_check_, new_check, new_offset);
166 96 : UpdateLowerOffsets(lower_check_, lower_offset_);
167 : }
168 : } else {
169 : // Should never have called CoverCheck() in this case.
170 0 : UNREACHABLE();
171 : }
172 :
173 1605 : if (!keep_new_check) {
174 931 : if (FLAG_trace_bce) {
175 : base::OS::Print("Eliminating check #%d after tightening\n",
176 0 : new_check->id());
177 : }
178 : new_check->block()->graph()->isolate()->counters()->
179 931 : bounds_checks_eliminated()->Increment();
180 931 : new_check->DeleteAndReplaceWith(new_check->ActualValue());
181 : } else {
182 674 : HBoundsCheck* first_check = new_check == lower_check_ ? upper_check_
183 674 : : lower_check_;
184 674 : if (FLAG_trace_bce) {
185 : base::OS::Print("Moving second check #%d after first check #%d\n",
186 0 : new_check->id(), first_check->id());
187 : }
188 : // The length is guaranteed to be live at first_check.
189 : DCHECK(new_check->length() == first_check->length());
190 674 : HInstruction* old_position = new_check->next();
191 674 : new_check->Unlink();
192 674 : new_check->InsertAfter(first_check);
193 674 : MoveIndexIfNecessary(new_check->index(), new_check, old_position);
194 : }
195 1605 : }
196 :
197 : BoundsCheckBbData(BoundsCheckKey* key,
198 : int32_t lower_offset,
199 : int32_t upper_offset,
200 : HBasicBlock* bb,
201 : HBoundsCheck* lower_check,
202 : HBoundsCheck* upper_check,
203 : BoundsCheckBbData* next_in_bb,
204 : BoundsCheckBbData* father_in_dt)
205 : : key_(key),
206 : lower_offset_(lower_offset),
207 : upper_offset_(upper_offset),
208 : basic_block_(bb),
209 : lower_check_(lower_check),
210 : upper_check_(upper_check),
211 : next_in_bb_(next_in_bb),
212 32406 : father_in_dt_(father_in_dt) { }
213 :
214 : private:
215 : BoundsCheckKey* key_;
216 : int32_t lower_offset_;
217 : int32_t upper_offset_;
218 : HBasicBlock* basic_block_;
219 : HBoundsCheck* lower_check_;
220 : HBoundsCheck* upper_check_;
221 : BoundsCheckBbData* next_in_bb_;
222 : BoundsCheckBbData* father_in_dt_;
223 :
224 1605 : void MoveIndexIfNecessary(HValue* index_raw,
225 : HBoundsCheck* insert_before,
226 : HInstruction* end_of_scan_range) {
227 : // index_raw can be HAdd(index_base, offset), HSub(index_base, offset),
228 : // HConstant(offset) or index_base directly.
229 : // In the latter case, no need to move anything.
230 2908 : if (index_raw->IsAdd() || index_raw->IsSub()) {
231 : HArithmeticBinaryOperation* index =
232 : HArithmeticBinaryOperation::cast(index_raw);
233 : HValue* left_input = index->left();
234 : HValue* right_input = index->right();
235 : HValue* context = index->context();
236 : bool must_move_index = false;
237 : bool must_move_left_input = false;
238 : bool must_move_right_input = false;
239 : bool must_move_context = false;
240 4282 : for (HInstruction* cursor = end_of_scan_range; cursor != insert_before;) {
241 1812 : if (cursor == left_input) must_move_left_input = true;
242 1812 : if (cursor == right_input) must_move_right_input = true;
243 1812 : if (cursor == context) must_move_context = true;
244 1812 : if (cursor == index) must_move_index = true;
245 1812 : if (cursor->previous() == NULL) {
246 56 : cursor = cursor->block()->dominator()->end();
247 : } else {
248 : cursor = cursor->previous();
249 : }
250 : }
251 329 : if (must_move_index) {
252 327 : index->Unlink();
253 327 : index->InsertBefore(insert_before);
254 : }
255 : // The BCE algorithm only selects mergeable bounds checks that share
256 : // the same "index_base", so we'll only ever have to move constants.
257 329 : if (must_move_left_input) {
258 0 : HConstant::cast(left_input)->Unlink();
259 0 : HConstant::cast(left_input)->InsertBefore(index);
260 : }
261 329 : if (must_move_right_input) {
262 76 : HConstant::cast(right_input)->Unlink();
263 76 : HConstant::cast(right_input)->InsertBefore(index);
264 : }
265 329 : if (must_move_context) {
266 : // Contexts are always constants.
267 0 : HConstant::cast(context)->Unlink();
268 0 : HConstant::cast(context)->InsertBefore(index);
269 : }
270 1276 : } else if (index_raw->IsConstant()) {
271 : HConstant* index = HConstant::cast(index_raw);
272 : bool must_move = false;
273 192685 : for (HInstruction* cursor = end_of_scan_range; cursor != insert_before;) {
274 95708 : if (cursor == index) must_move = true;
275 95708 : if (cursor->previous() == NULL) {
276 80 : cursor = cursor->block()->dominator()->end();
277 : } else {
278 : cursor = cursor->previous();
279 : }
280 : }
281 1269 : if (must_move) {
282 1079 : index->Unlink();
283 1079 : index->InsertBefore(insert_before);
284 : }
285 : }
286 1605 : }
287 :
288 931 : void TightenCheck(HBoundsCheck* original_check,
289 : HBoundsCheck* tighter_check,
290 : int32_t new_offset) {
291 : DCHECK(original_check->length() == tighter_check->length());
292 931 : MoveIndexIfNecessary(tighter_check->index(), original_check, tighter_check);
293 931 : original_check->ReplaceAllUsesWith(original_check->index());
294 931 : original_check->SetOperandAt(0, tighter_check->index());
295 931 : if (FLAG_trace_bce) {
296 : base::OS::Print("Tightened check #%d with offset %d from #%d\n",
297 0 : original_check->id(), new_offset, tighter_check->id());
298 : }
299 931 : }
300 :
301 : DISALLOW_COPY_AND_ASSIGN(BoundsCheckBbData);
302 : };
303 :
304 :
305 35475 : static bool BoundsCheckKeyMatch(void* key1, void* key2) {
306 70894 : BoundsCheckKey* k1 = static_cast<BoundsCheckKey*>(key1);
307 70894 : BoundsCheckKey* k2 = static_cast<BoundsCheckKey*>(key2);
308 70894 : return k1->IndexBase() == k2->IndexBase() && k1->Length() == k2->Length();
309 : }
310 :
311 283728 : BoundsCheckTable::BoundsCheckTable(Zone* zone)
312 : : CustomMatcherZoneHashMap(BoundsCheckKeyMatch,
313 : ZoneHashMap::kDefaultHashMapCapacity,
314 283730 : ZoneAllocationPolicy(zone)) {}
315 :
316 : BoundsCheckBbData** BoundsCheckTable::LookupOrInsert(BoundsCheckKey* key,
317 : Zone* zone) {
318 : return reinterpret_cast<BoundsCheckBbData**>(
319 : &(CustomMatcherZoneHashMap::LookupOrInsert(key, key->Hash(),
320 34298 : ZoneAllocationPolicy(zone))
321 : ->value));
322 : }
323 :
324 :
325 : void BoundsCheckTable::Insert(BoundsCheckKey* key,
326 : BoundsCheckBbData* data,
327 : Zone* zone) {
328 : CustomMatcherZoneHashMap::LookupOrInsert(key, key->Hash(),
329 1357 : ZoneAllocationPolicy(zone))
330 679 : ->value = data;
331 : }
332 :
333 :
334 : void BoundsCheckTable::Delete(BoundsCheckKey* key) {
335 32069 : Remove(key, key->Hash());
336 : }
337 :
338 :
339 : class HBoundsCheckEliminationState {
340 : public:
341 : HBasicBlock* block_;
342 : BoundsCheckBbData* bb_data_list_;
343 : int index_;
344 : };
345 :
346 :
347 : // Eliminates checks in bb and recursively in the dominated blocks.
348 : // Also replace the results of check instructions with the original value, if
349 : // the result is used. This is safe now, since we don't do code motion after
350 : // this point. It enables better register allocation since the value produced
351 : // by check instructions is really a copy of the original value.
352 283729 : void HBoundsCheckEliminationPhase::EliminateRedundantBoundsChecks(
353 : HBasicBlock* entry) {
354 : // Allocate the stack.
355 : HBoundsCheckEliminationState* stack =
356 283729 : zone()->NewArray<HBoundsCheckEliminationState>(graph()->blocks()->length());
357 :
358 : // Explicitly push the entry block.
359 283729 : stack[0].block_ = entry;
360 283729 : stack[0].bb_data_list_ = PreProcessBlock(entry);
361 283717 : stack[0].index_ = 0;
362 : int stack_depth = 1;
363 :
364 : // Implement depth-first traversal with a stack.
365 9307005 : while (stack_depth > 0) {
366 8739558 : int current = stack_depth - 1;
367 8739558 : HBoundsCheckEliminationState* state = &stack[current];
368 8739558 : const ZoneList<HBasicBlock*>* children = state->block_->dominated_blocks();
369 :
370 8739558 : if (state->index_ < children->length()) {
371 : // Recursively visit children blocks.
372 8455734 : HBasicBlock* child = children->at(state->index_++);
373 4227867 : int next = stack_depth++;
374 4227867 : stack[next].block_ = child;
375 4227867 : stack[next].bb_data_list_ = PreProcessBlock(child);
376 4227934 : stack[next].index_ = 0;
377 : } else {
378 : // Finished with all children; post process the block.
379 4511691 : PostProcessBlock(state->block_, state->bb_data_list_);
380 : stack_depth--;
381 : }
382 : }
383 283730 : }
384 :
385 :
386 4511684 : BoundsCheckBbData* HBoundsCheckEliminationPhase::PreProcessBlock(
387 249 : HBasicBlock* bb) {
388 : BoundsCheckBbData* bb_data_list = NULL;
389 :
390 29723195 : for (HInstructionIterator it(bb); !it.Done(); it.Advance()) {
391 : HInstruction* i = it.Current();
392 75600261 : if (!i->IsBoundsCheck()) continue;
393 :
394 : HBoundsCheck* check = HBoundsCheck::cast(i);
395 34298 : int32_t offset = 0;
396 : BoundsCheckKey* key =
397 34298 : BoundsCheckKey::Create(zone(), check, &offset);
398 34298 : if (key == NULL) continue;
399 : BoundsCheckBbData** data_p = table_.LookupOrInsert(key, zone());
400 36954 : BoundsCheckBbData* data = *data_p;
401 34296 : if (data == NULL) {
402 : bb_data_list = new(zone()) BoundsCheckBbData(key,
403 : offset,
404 : offset,
405 : bb,
406 : check,
407 : check,
408 : bb_data_list,
409 32067 : NULL);
410 32067 : *data_p = bb_data_list;
411 32067 : if (FLAG_trace_bce) {
412 : base::OS::Print("Fresh bounds check data for block #%d: [%d]\n",
413 0 : bb->block_id(), offset);
414 : }
415 4458 : } else if (data->OffsetIsCovered(offset)) {
416 : bb->graph()->isolate()->counters()->
417 249 : bounds_checks_eliminated()->Increment();
418 249 : if (FLAG_trace_bce) {
419 : base::OS::Print("Eliminating bounds check #%d, offset %d is covered\n",
420 0 : check->id(), offset);
421 : }
422 249 : check->DeleteAndReplaceWith(check->ActualValue());
423 1980 : } else if (data->BasicBlock() == bb) {
424 : // TODO(jkummerow): I think the following logic would be preferable:
425 : // if (data->Basicblock() == bb ||
426 : // graph()->use_optimistic_licm() ||
427 : // bb->IsLoopSuccessorDominator()) {
428 : // data->CoverCheck(check, offset)
429 : // } else {
430 : // /* add pristine BCBbData like in (data == NULL) case above */
431 : // }
432 : // Even better would be: distinguish between read-only dominator-imposed
433 : // knowledge and modifiable upper/lower checks.
434 : // What happens currently is that the first bounds check in a dominated
435 : // block will stay around while any further checks are hoisted out,
436 : // which doesn't make sense. Investigate/fix this in a future CL.
437 1605 : data->CoverCheck(check, offset);
438 413 : } else if (graph()->use_optimistic_licm() ||
439 : bb->IsLoopSuccessorDominator()) {
440 : int32_t new_lower_offset = offset < data->LowerOffset()
441 : ? offset
442 339 : : data->LowerOffset();
443 : int32_t new_upper_offset = offset > data->UpperOffset()
444 : ? offset
445 339 : : data->UpperOffset();
446 : bb_data_list = new(zone()) BoundsCheckBbData(key,
447 : new_lower_offset,
448 : new_upper_offset,
449 : bb,
450 : data->LowerCheck(),
451 : data->UpperCheck(),
452 : bb_data_list,
453 : data);
454 339 : if (FLAG_trace_bce) {
455 : base::OS::Print("Updated bounds check data for block #%d: [%d - %d]\n",
456 0 : bb->block_id(), new_lower_offset, new_upper_offset);
457 : }
458 : table_.Insert(key, bb_data_list, zone());
459 : }
460 : }
461 :
462 4511648 : return bb_data_list;
463 : }
464 :
465 :
466 4511690 : void HBoundsCheckEliminationPhase::PostProcessBlock(
467 97224 : HBasicBlock* block, BoundsCheckBbData* data) {
468 9055788 : while (data != NULL) {
469 32408 : if (data->FatherInDominatorTree()) {
470 339 : table_.Insert(data->Key(), data->FatherInDominatorTree(), zone());
471 : } else {
472 : table_.Delete(data->Key());
473 : }
474 : data = data->NextInBasicBlock();
475 : }
476 4511690 : }
477 :
478 : } // namespace internal
479 : } // namespace v8
|
