// Copyright 2013 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#include "src/hydrogen-bce.h"
namespace v8 {
namespace internal {
// We try to "factor up" HBoundsCheck instructions towards the root of the
// dominator tree.
// For now we handle checks where the index is like "exp + int32value".
// If in the dominator tree we check "exp + v1" and later (dominated)
// "exp + v2", if v2 <= v1 we can safely remove the second check, and if
// v2 > v1 we can use v2 in the 1st check and again remove the second.
// To do so we keep a dictionary of all checks where the key if the pair
// "exp, length".
// The class BoundsCheckKey represents this key.
class BoundsCheckKey : public ZoneObject {
public:
HValue* IndexBase() const { return index_base_; }
HValue* Length() const { return length_; }
uint32_t Hash() {
return static_cast<uint32_t>(index_base_->Hashcode() ^ length_->Hashcode());
}
static BoundsCheckKey* Create(Zone* zone,
HBoundsCheck* check,
int32_t* offset) {
if (!check->index()->representation().IsSmiOrInteger32()) return NULL;
HValue* index_base = NULL;
HConstant* constant = NULL;
bool is_sub = false;
if (check->index()->IsAdd()) {
HAdd* index = HAdd::cast(check->index());
if (index->left()->IsConstant()) {
constant = HConstant::cast(index->left());
index_base = index->right();
} else if (index->right()->IsConstant()) {
constant = HConstant::cast(index->right());
index_base = index->left();
}
} else if (check->index()->IsSub()) {
HSub* index = HSub::cast(check->index());
is_sub = true;
if (index->right()->IsConstant()) {
constant = HConstant::cast(index->right());
index_base = index->left();
}
} else if (check->index()->IsConstant()) {
index_base = check->block()->graph()->GetConstant0();
constant = HConstant::cast(check->index());
}
if (constant != NULL && constant->HasInteger32Value()) {
*offset = is_sub ? - constant->Integer32Value()
: constant->Integer32Value();
} else {
*offset = 0;
index_base = check->index();
}
return new(zone) BoundsCheckKey(index_base, check->length());
}
private:
BoundsCheckKey(HValue* index_base, HValue* length)
: index_base_(index_base),
length_(length) { }
HValue* index_base_;
HValue* length_;
DISALLOW_COPY_AND_ASSIGN(BoundsCheckKey);
};
// Data about each HBoundsCheck that can be eliminated or moved.
// It is the "value" in the dictionary indexed by "base-index, length"
// (the key is BoundsCheckKey).
// We scan the code with a dominator tree traversal.
// Traversing the dominator tree we keep a stack (implemented as a singly
// linked list) of "data" for each basic block that contains a relevant check
// with the same key (the dictionary holds the head of the list).
// We also keep all the "data" created for a given basic block in a list, and
// use it to "clean up" the dictionary when backtracking in the dominator tree
// traversal.
// Doing this each dictionary entry always directly points to the check that
// is dominating the code being examined now.
// We also track the current "offset" of the index expression and use it to
// decide if any check is already "covered" (so it can be removed) or not.
class BoundsCheckBbData: public ZoneObject {
public:
BoundsCheckKey* Key() const { return key_; }
int32_t LowerOffset() const { return lower_offset_; }
int32_t UpperOffset() const { return upper_offset_; }
HBasicBlock* BasicBlock() const { return basic_block_; }
HBoundsCheck* LowerCheck() const { return lower_check_; }
HBoundsCheck* UpperCheck() const { return upper_check_; }
BoundsCheckBbData* NextInBasicBlock() const { return next_in_bb_; }
BoundsCheckBbData* FatherInDominatorTree() const { return father_in_dt_; }
bool OffsetIsCovered(int32_t offset) const {
return offset >= LowerOffset() && offset <= UpperOffset();
}
bool HasSingleCheck() { return lower_check_ == upper_check_; }
void UpdateUpperOffsets(HBoundsCheck* check, int32_t offset) {
BoundsCheckBbData* data = FatherInDominatorTree();
while (data != NULL && data->UpperCheck() == check) {
DCHECK(data->upper_offset_ < offset);
data->upper_offset_ = offset;
data = data->FatherInDominatorTree();
}
}
void UpdateLowerOffsets(HBoundsCheck* check, int32_t offset) {
BoundsCheckBbData* data = FatherInDominatorTree();
while (data != NULL && data->LowerCheck() == check) {
DCHECK(data->lower_offset_ > offset);
data->lower_offset_ = offset;
data = data->FatherInDominatorTree();
}
}
// The goal of this method is to modify either upper_offset_ or
// lower_offset_ so that also new_offset is covered (the covered
// range grows).
//
// The precondition is that new_check follows UpperCheck() and
// LowerCheck() in the same basic block, and that new_offset is not
// covered (otherwise we could simply remove new_check).
//
// If HasSingleCheck() is true then new_check is added as "second check"
// (either upper or lower; note that HasSingleCheck() becomes false).
// Otherwise one of the current checks is modified so that it also covers
// new_offset, and new_check is removed.
void CoverCheck(HBoundsCheck* new_check,
int32_t new_offset) {
DCHECK(new_check->index()->representation().IsSmiOrInteger32());
bool keep_new_check = false;
if (new_offset > upper_offset_) {
upper_offset_ = new_offset;
if (HasSingleCheck()) {
keep_new_check = true;
upper_check_ = new_check;
} else {
TightenCheck(upper_check_, new_check, new_offset);
UpdateUpperOffsets(upper_check_, upper_offset_);
}
} else if (new_offset < lower_offset_) {
lower_offset_ = new_offset;
if (HasSingleCheck()) {
keep_new_check = true;
lower_check_ = new_check;
} else {
TightenCheck(lower_check_, new_check, new_offset);
UpdateLowerOffsets(lower_check_, lower_offset_);
}
} else {
// Should never have called CoverCheck() in this case.
UNREACHABLE();
}
if (!keep_new_check) {
if (FLAG_trace_bce) {
base::OS::Print("Eliminating check #%d after tightening\n",
new_check->id());
}
new_check->block()->graph()->isolate()->counters()->
bounds_checks_eliminated()->Increment();
new_check->DeleteAndReplaceWith(new_check->ActualValue());
} else {
HBoundsCheck* first_check = new_check == lower_check_ ? upper_check_
: lower_check_;
if (FLAG_trace_bce) {
base::OS::Print("Moving second check #%d after first check #%d\n",
new_check->id(), first_check->id());
}
// The length is guaranteed to be live at first_check.
DCHECK(new_check->length() == first_check->length());
HInstruction* old_position = new_check->next();
new_check->Unlink();
new_check->InsertAfter(first_check);
MoveIndexIfNecessary(new_check->index(), new_check, old_position);
}
}
BoundsCheckBbData(BoundsCheckKey* key,
int32_t lower_offset,
int32_t upper_offset,
HBasicBlock* bb,
HBoundsCheck* lower_check,
HBoundsCheck* upper_check,
BoundsCheckBbData* next_in_bb,
BoundsCheckBbData* father_in_dt)
: key_(key),
lower_offset_(lower_offset),
upper_offset_(upper_offset),
basic_block_(bb),
lower_check_(lower_check),
upper_check_(upper_check),
next_in_bb_(next_in_bb),
father_in_dt_(father_in_dt) { }
private:
BoundsCheckKey* key_;
int32_t lower_offset_;
int32_t upper_offset_;
HBasicBlock* basic_block_;
HBoundsCheck* lower_check_;
HBoundsCheck* upper_check_;
BoundsCheckBbData* next_in_bb_;
BoundsCheckBbData* father_in_dt_;
void MoveIndexIfNecessary(HValue* index_raw,
HBoundsCheck* insert_before,
HInstruction* end_of_scan_range) {
// index_raw can be HAdd(index_base, offset), HSub(index_base, offset),
// HConstant(offset) or index_base directly.
// In the latter case, no need to move anything.
if (index_raw->IsAdd() || index_raw->IsSub()) {
HArithmeticBinaryOperation* index =
HArithmeticBinaryOperation::cast(index_raw);
HValue* left_input = index->left();
HValue* right_input = index->right();
bool must_move_index = false;
bool must_move_left_input = false;
bool must_move_right_input = false;
for (HInstruction* cursor = end_of_scan_range; cursor != insert_before;) {
if (cursor == left_input) must_move_left_input = true;
if (cursor == right_input) must_move_right_input = true;
if (cursor == index) must_move_index = true;
if (cursor->previous() == NULL) {
cursor = cursor->block()->dominator()->end();
} else {
cursor = cursor->previous();
}
}
if (must_move_index) {
index->Unlink();
index->InsertBefore(insert_before);
}
// The BCE algorithm only selects mergeable bounds checks that share
// the same "index_base", so we'll only ever have to move constants.
if (must_move_left_input) {
HConstant::cast(left_input)->Unlink();
HConstant::cast(left_input)->InsertBefore(index);
}
if (must_move_right_input) {
HConstant::cast(right_input)->Unlink();
HConstant::cast(right_input)->InsertBefore(index);
}
} else if (index_raw->IsConstant()) {
HConstant* index = HConstant::cast(index_raw);
bool must_move = false;
for (HInstruction* cursor = end_of_scan_range; cursor != insert_before;) {
if (cursor == index) must_move = true;
if (cursor->previous() == NULL) {
cursor = cursor->block()->dominator()->end();
} else {
cursor = cursor->previous();
}
}
if (must_move) {
index->Unlink();
index->InsertBefore(insert_before);
}
}
}
void TightenCheck(HBoundsCheck* original_check,
HBoundsCheck* tighter_check,
int32_t new_offset) {
DCHECK(original_check->length() == tighter_check->length());
MoveIndexIfNecessary(tighter_check->index(), original_check, tighter_check);
original_check->ReplaceAllUsesWith(original_check->index());
original_check->SetOperandAt(0, tighter_check->index());
if (FLAG_trace_bce) {
base::OS::Print("Tightened check #%d with offset %d from #%d\n",
original_check->id(), new_offset, tighter_check->id());
}
}
DISALLOW_COPY_AND_ASSIGN(BoundsCheckBbData);
};
static bool BoundsCheckKeyMatch(void* key1, void* key2) {
BoundsCheckKey* k1 = static_cast<BoundsCheckKey*>(key1);
BoundsCheckKey* k2 = static_cast<BoundsCheckKey*>(key2);
return k1->IndexBase() == k2->IndexBase() && k1->Length() == k2->Length();
}
BoundsCheckTable::BoundsCheckTable(Zone* zone)
: ZoneHashMap(BoundsCheckKeyMatch, ZoneHashMap::kDefaultHashMapCapacity,
ZoneAllocationPolicy(zone)) { }
BoundsCheckBbData** BoundsCheckTable::LookupOrInsert(BoundsCheckKey* key,
Zone* zone) {
return reinterpret_cast<BoundsCheckBbData**>(
&(Lookup(key, key->Hash(), true, ZoneAllocationPolicy(zone))->value));
}
void BoundsCheckTable::Insert(BoundsCheckKey* key,
BoundsCheckBbData* data,
Zone* zone) {
Lookup(key, key->Hash(), true, ZoneAllocationPolicy(zone))->value = data;
}
void BoundsCheckTable::Delete(BoundsCheckKey* key) {
Remove(key, key->Hash());
}
class HBoundsCheckEliminationState {
public:
HBasicBlock* block_;
BoundsCheckBbData* bb_data_list_;
int index_;
};
// Eliminates checks in bb and recursively in the dominated blocks.
// Also replace the results of check instructions with the original value, if
// the result is used. This is safe now, since we don't do code motion after
// this point. It enables better register allocation since the value produced
// by check instructions is really a copy of the original value.
void HBoundsCheckEliminationPhase::EliminateRedundantBoundsChecks(
HBasicBlock* entry) {
// Allocate the stack.
HBoundsCheckEliminationState* stack =
zone()->NewArray<HBoundsCheckEliminationState>(graph()->blocks()->length());
// Explicitly push the entry block.
stack[0].block_ = entry;
stack[0].bb_data_list_ = PreProcessBlock(entry);
stack[0].index_ = 0;
int stack_depth = 1;
// Implement depth-first traversal with a stack.
while (stack_depth > 0) {
int current = stack_depth - 1;
HBoundsCheckEliminationState* state = &stack[current];
const ZoneList<HBasicBlock*>* children = state->block_->dominated_blocks();
if (state->index_ < children->length()) {
// Recursively visit children blocks.
HBasicBlock* child = children->at(state->index_++);
int next = stack_depth++;
stack[next].block_ = child;
stack[next].bb_data_list_ = PreProcessBlock(child);
stack[next].index_ = 0;
} else {
// Finished with all children; post process the block.
PostProcessBlock(state->block_, state->bb_data_list_);
stack_depth--;
}
}
}
BoundsCheckBbData* HBoundsCheckEliminationPhase::PreProcessBlock(
HBasicBlock* bb) {
BoundsCheckBbData* bb_data_list = NULL;
for (HInstructionIterator it(bb); !it.Done(); it.Advance()) {
HInstruction* i = it.Current();
if (!i->IsBoundsCheck()) continue;
HBoundsCheck* check = HBoundsCheck::cast(i);
int32_t offset;
BoundsCheckKey* key =
BoundsCheckKey::Create(zone(), check, &offset);
if (key == NULL) continue;
BoundsCheckBbData** data_p = table_.LookupOrInsert(key, zone());
BoundsCheckBbData* data = *data_p;
if (data == NULL) {
bb_data_list = new(zone()) BoundsCheckBbData(key,
offset,
offset,
bb,
check,
check,
bb_data_list,
NULL);
*data_p = bb_data_list;
if (FLAG_trace_bce) {
base::OS::Print("Fresh bounds check data for block #%d: [%d]\n",
bb->block_id(), offset);
}
} else if (data->OffsetIsCovered(offset)) {
bb->graph()->isolate()->counters()->
bounds_checks_eliminated()->Increment();
if (FLAG_trace_bce) {
base::OS::Print("Eliminating bounds check #%d, offset %d is covered\n",
check->id(), offset);
}
check->DeleteAndReplaceWith(check->ActualValue());
} else if (data->BasicBlock() == bb) {
// TODO(jkummerow): I think the following logic would be preferable:
// if (data->Basicblock() == bb ||
// graph()->use_optimistic_licm() ||
// bb->IsLoopSuccessorDominator()) {
// data->CoverCheck(check, offset)
// } else {
// /* add pristine BCBbData like in (data == NULL) case above */
// }
// Even better would be: distinguish between read-only dominator-imposed
// knowledge and modifiable upper/lower checks.
// What happens currently is that the first bounds check in a dominated
// block will stay around while any further checks are hoisted out,
// which doesn't make sense. Investigate/fix this in a future CL.
data->CoverCheck(check, offset);
} else if (graph()->use_optimistic_licm() ||
bb->IsLoopSuccessorDominator()) {
int32_t new_lower_offset = offset < data->LowerOffset()
? offset
: data->LowerOffset();
int32_t new_upper_offset = offset > data->UpperOffset()
? offset
: data->UpperOffset();
bb_data_list = new(zone()) BoundsCheckBbData(key,
new_lower_offset,
new_upper_offset,
bb,
data->LowerCheck(),
data->UpperCheck(),
bb_data_list,
data);
if (FLAG_trace_bce) {
base::OS::Print("Updated bounds check data for block #%d: [%d - %d]\n",
bb->block_id(), new_lower_offset, new_upper_offset);
}
table_.Insert(key, bb_data_list, zone());
}
}
return bb_data_list;
}
void HBoundsCheckEliminationPhase::PostProcessBlock(
HBasicBlock* block, BoundsCheckBbData* data) {
while (data != NULL) {
if (data->FatherInDominatorTree()) {
table_.Insert(data->Key(), data->FatherInDominatorTree(), zone());
} else {
table_.Delete(data->Key());
}
data = data->NextInBasicBlock();
}
}
} } // namespace v8::internal