1bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org// Copyright 2013 the V8 project authors. All rights reserved. 23484964a86451e86dcf04be9bd8c0d76ee04f081rossberg@chromium.org// Use of this source code is governed by a BSD-style license that can be 33484964a86451e86dcf04be9bd8c0d76ee04f081rossberg@chromium.org// found in the LICENSE file. 4bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org 5196eb601290dc49c3754da728dc58700dff2de1bmachenbach@chromium.org#include "src/hydrogen-bce.h" 6bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org 7bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.orgnamespace v8 { 8bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.orgnamespace internal { 9bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org 1069f64b1a8bfa6f5418b7c1f71d4e0833f76e93edmachenbach@chromium.org 11bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org// We try to "factor up" HBoundsCheck instructions towards the root of the 12bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org// dominator tree. 13bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org// For now we handle checks where the index is like "exp + int32value". 14bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org// If in the dominator tree we check "exp + v1" and later (dominated) 15bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org// "exp + v2", if v2 <= v1 we can safely remove the second check, and if 16bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org// v2 > v1 we can use v2 in the 1st check and again remove the second. 17bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org// To do so we keep a dictionary of all checks where the key if the pair 18bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org// "exp, length". 19bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org// The class BoundsCheckKey represents this key. 20bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.orgclass BoundsCheckKey : public ZoneObject { 21bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org public: 22bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org HValue* IndexBase() const { return index_base_; } 23bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org HValue* Length() const { return length_; } 24bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org 25bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org uint32_t Hash() { 26bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org return static_cast<uint32_t>(index_base_->Hashcode() ^ length_->Hashcode()); 27bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org } 28bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org 29bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org static BoundsCheckKey* Create(Zone* zone, 30bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org HBoundsCheck* check, 31bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org int32_t* offset) { 32bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org if (!check->index()->representation().IsSmiOrInteger32()) return NULL; 33bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org 34bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org HValue* index_base = NULL; 35bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org HConstant* constant = NULL; 36bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org bool is_sub = false; 37bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org 38bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org if (check->index()->IsAdd()) { 39bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org HAdd* index = HAdd::cast(check->index()); 40bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org if (index->left()->IsConstant()) { 41bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org constant = HConstant::cast(index->left()); 42bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org index_base = index->right(); 43bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org } else if (index->right()->IsConstant()) { 44bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org constant = HConstant::cast(index->right()); 45bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org index_base = index->left(); 46bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org } 47bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org } else if (check->index()->IsSub()) { 48bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org HSub* index = HSub::cast(check->index()); 49bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org is_sub = true; 50afb6326f5a59f22f94255389bf72fa7a9381742dbmeurer@chromium.org if (index->right()->IsConstant()) { 51bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org constant = HConstant::cast(index->right()); 52bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org index_base = index->left(); 53bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org } 5438de99aae2d4efc5796aa6935c1648447ec32fc8machenbach@chromium.org } else if (check->index()->IsConstant()) { 5538de99aae2d4efc5796aa6935c1648447ec32fc8machenbach@chromium.org index_base = check->block()->graph()->GetConstant0(); 5638de99aae2d4efc5796aa6935c1648447ec32fc8machenbach@chromium.org constant = HConstant::cast(check->index()); 57bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org } 58bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org 59bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org if (constant != NULL && constant->HasInteger32Value()) { 60bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org *offset = is_sub ? - constant->Integer32Value() 61bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org : constant->Integer32Value(); 62bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org } else { 63bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org *offset = 0; 64bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org index_base = check->index(); 65bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org } 66bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org 67bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org return new(zone) BoundsCheckKey(index_base, check->length()); 68bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org } 69bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org 70bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org private: 71bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org BoundsCheckKey(HValue* index_base, HValue* length) 72fb79f8683208e62002112b4406ec9dadda54dec2machenbach@chromium.org : index_base_(index_base), 73fb79f8683208e62002112b4406ec9dadda54dec2machenbach@chromium.org length_(length) { } 74bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org 75bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org HValue* index_base_; 76bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org HValue* length_; 77bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org 78bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org DISALLOW_COPY_AND_ASSIGN(BoundsCheckKey); 79bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org}; 80bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org 81bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org 82bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org// Data about each HBoundsCheck that can be eliminated or moved. 83bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org// It is the "value" in the dictionary indexed by "base-index, length" 84bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org// (the key is BoundsCheckKey). 85bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org// We scan the code with a dominator tree traversal. 86bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org// Traversing the dominator tree we keep a stack (implemented as a singly 87bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org// linked list) of "data" for each basic block that contains a relevant check 88bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org// with the same key (the dictionary holds the head of the list). 89bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org// We also keep all the "data" created for a given basic block in a list, and 90bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org// use it to "clean up" the dictionary when backtracking in the dominator tree 91bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org// traversal. 92bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org// Doing this each dictionary entry always directly points to the check that 93bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org// is dominating the code being examined now. 94bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org// We also track the current "offset" of the index expression and use it to 95bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org// decide if any check is already "covered" (so it can be removed) or not. 96bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.orgclass BoundsCheckBbData: public ZoneObject { 97bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org public: 98bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org BoundsCheckKey* Key() const { return key_; } 99bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org int32_t LowerOffset() const { return lower_offset_; } 100bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org int32_t UpperOffset() const { return upper_offset_; } 101bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org HBasicBlock* BasicBlock() const { return basic_block_; } 102bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org HBoundsCheck* LowerCheck() const { return lower_check_; } 103bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org HBoundsCheck* UpperCheck() const { return upper_check_; } 104bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org BoundsCheckBbData* NextInBasicBlock() const { return next_in_bb_; } 105bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org BoundsCheckBbData* FatherInDominatorTree() const { return father_in_dt_; } 106bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org 107bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org bool OffsetIsCovered(int32_t offset) const { 108bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org return offset >= LowerOffset() && offset <= UpperOffset(); 109bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org } 110bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org 111bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org bool HasSingleCheck() { return lower_check_ == upper_check_; } 112bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org 1136b6df382019a622ba20133e47bbe2e6f323b013bdslomov@chromium.org void UpdateUpperOffsets(HBoundsCheck* check, int32_t offset) { 1146b6df382019a622ba20133e47bbe2e6f323b013bdslomov@chromium.org BoundsCheckBbData* data = FatherInDominatorTree(); 1156b6df382019a622ba20133e47bbe2e6f323b013bdslomov@chromium.org while (data != NULL && data->UpperCheck() == check) { 116e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(data->upper_offset_ < offset); 1176b6df382019a622ba20133e47bbe2e6f323b013bdslomov@chromium.org data->upper_offset_ = offset; 1186b6df382019a622ba20133e47bbe2e6f323b013bdslomov@chromium.org data = data->FatherInDominatorTree(); 1196b6df382019a622ba20133e47bbe2e6f323b013bdslomov@chromium.org } 1206b6df382019a622ba20133e47bbe2e6f323b013bdslomov@chromium.org } 1216b6df382019a622ba20133e47bbe2e6f323b013bdslomov@chromium.org 1226b6df382019a622ba20133e47bbe2e6f323b013bdslomov@chromium.org void UpdateLowerOffsets(HBoundsCheck* check, int32_t offset) { 1236b6df382019a622ba20133e47bbe2e6f323b013bdslomov@chromium.org BoundsCheckBbData* data = FatherInDominatorTree(); 1246b6df382019a622ba20133e47bbe2e6f323b013bdslomov@chromium.org while (data != NULL && data->LowerCheck() == check) { 125e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(data->lower_offset_ > offset); 1266b6df382019a622ba20133e47bbe2e6f323b013bdslomov@chromium.org data->lower_offset_ = offset; 1276b6df382019a622ba20133e47bbe2e6f323b013bdslomov@chromium.org data = data->FatherInDominatorTree(); 1286b6df382019a622ba20133e47bbe2e6f323b013bdslomov@chromium.org } 1296b6df382019a622ba20133e47bbe2e6f323b013bdslomov@chromium.org } 1306b6df382019a622ba20133e47bbe2e6f323b013bdslomov@chromium.org 131bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org // The goal of this method is to modify either upper_offset_ or 132bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org // lower_offset_ so that also new_offset is covered (the covered 133bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org // range grows). 134bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org // 135bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org // The precondition is that new_check follows UpperCheck() and 136bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org // LowerCheck() in the same basic block, and that new_offset is not 137bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org // covered (otherwise we could simply remove new_check). 138bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org // 139bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org // If HasSingleCheck() is true then new_check is added as "second check" 140bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org // (either upper or lower; note that HasSingleCheck() becomes false). 141bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org // Otherwise one of the current checks is modified so that it also covers 142bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org // new_offset, and new_check is removed. 143fb79f8683208e62002112b4406ec9dadda54dec2machenbach@chromium.org void CoverCheck(HBoundsCheck* new_check, 144bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org int32_t new_offset) { 145e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(new_check->index()->representation().IsSmiOrInteger32()); 146bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org bool keep_new_check = false; 147bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org 148bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org if (new_offset > upper_offset_) { 149bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org upper_offset_ = new_offset; 150bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org if (HasSingleCheck()) { 151bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org keep_new_check = true; 152bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org upper_check_ = new_check; 153bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org } else { 15469f64b1a8bfa6f5418b7c1f71d4e0833f76e93edmachenbach@chromium.org TightenCheck(upper_check_, new_check, new_offset); 1556b6df382019a622ba20133e47bbe2e6f323b013bdslomov@chromium.org UpdateUpperOffsets(upper_check_, upper_offset_); 156bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org } 157bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org } else if (new_offset < lower_offset_) { 158bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org lower_offset_ = new_offset; 159bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org if (HasSingleCheck()) { 160bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org keep_new_check = true; 161bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org lower_check_ = new_check; 162bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org } else { 16369f64b1a8bfa6f5418b7c1f71d4e0833f76e93edmachenbach@chromium.org TightenCheck(lower_check_, new_check, new_offset); 1642904d1a42292be3056c2dd3f98822f8e1470fa72machenbach@chromium.org UpdateLowerOffsets(lower_check_, lower_offset_); 165bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org } 166bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org } else { 167fb79f8683208e62002112b4406ec9dadda54dec2machenbach@chromium.org // Should never have called CoverCheck() in this case. 168fb79f8683208e62002112b4406ec9dadda54dec2machenbach@chromium.org UNREACHABLE(); 169bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org } 170bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org 171bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org if (!keep_new_check) { 17269f64b1a8bfa6f5418b7c1f71d4e0833f76e93edmachenbach@chromium.org if (FLAG_trace_bce) { 1735de0074a922429f5e0ec2cf140c2d2989bf88140yangguo@chromium.org base::OS::Print("Eliminating check #%d after tightening\n", 1745de0074a922429f5e0ec2cf140c2d2989bf88140yangguo@chromium.org new_check->id()); 17569f64b1a8bfa6f5418b7c1f71d4e0833f76e93edmachenbach@chromium.org } 176fb732b17922ea75830be4db6b80534c4827d8a55jkummerow@chromium.org new_check->block()->graph()->isolate()->counters()-> 177fb732b17922ea75830be4db6b80534c4827d8a55jkummerow@chromium.org bounds_checks_eliminated()->Increment(); 178bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org new_check->DeleteAndReplaceWith(new_check->ActualValue()); 179fb79f8683208e62002112b4406ec9dadda54dec2machenbach@chromium.org } else { 180fb79f8683208e62002112b4406ec9dadda54dec2machenbach@chromium.org HBoundsCheck* first_check = new_check == lower_check_ ? upper_check_ 181fb79f8683208e62002112b4406ec9dadda54dec2machenbach@chromium.org : lower_check_; 18269f64b1a8bfa6f5418b7c1f71d4e0833f76e93edmachenbach@chromium.org if (FLAG_trace_bce) { 1835de0074a922429f5e0ec2cf140c2d2989bf88140yangguo@chromium.org base::OS::Print("Moving second check #%d after first check #%d\n", 1845de0074a922429f5e0ec2cf140c2d2989bf88140yangguo@chromium.org new_check->id(), first_check->id()); 18569f64b1a8bfa6f5418b7c1f71d4e0833f76e93edmachenbach@chromium.org } 186fb79f8683208e62002112b4406ec9dadda54dec2machenbach@chromium.org // The length is guaranteed to be live at first_check. 187e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(new_check->length() == first_check->length()); 188fb79f8683208e62002112b4406ec9dadda54dec2machenbach@chromium.org HInstruction* old_position = new_check->next(); 189fb79f8683208e62002112b4406ec9dadda54dec2machenbach@chromium.org new_check->Unlink(); 190fb79f8683208e62002112b4406ec9dadda54dec2machenbach@chromium.org new_check->InsertAfter(first_check); 191fb79f8683208e62002112b4406ec9dadda54dec2machenbach@chromium.org MoveIndexIfNecessary(new_check->index(), new_check, old_position); 192bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org } 193bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org } 194bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org 195bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org BoundsCheckBbData(BoundsCheckKey* key, 196bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org int32_t lower_offset, 197bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org int32_t upper_offset, 198bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org HBasicBlock* bb, 199bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org HBoundsCheck* lower_check, 200bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org HBoundsCheck* upper_check, 201bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org BoundsCheckBbData* next_in_bb, 202bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org BoundsCheckBbData* father_in_dt) 203fb79f8683208e62002112b4406ec9dadda54dec2machenbach@chromium.org : key_(key), 204fb79f8683208e62002112b4406ec9dadda54dec2machenbach@chromium.org lower_offset_(lower_offset), 205fb79f8683208e62002112b4406ec9dadda54dec2machenbach@chromium.org upper_offset_(upper_offset), 206fb79f8683208e62002112b4406ec9dadda54dec2machenbach@chromium.org basic_block_(bb), 207fb79f8683208e62002112b4406ec9dadda54dec2machenbach@chromium.org lower_check_(lower_check), 208fb79f8683208e62002112b4406ec9dadda54dec2machenbach@chromium.org upper_check_(upper_check), 209fb79f8683208e62002112b4406ec9dadda54dec2machenbach@chromium.org next_in_bb_(next_in_bb), 210fb79f8683208e62002112b4406ec9dadda54dec2machenbach@chromium.org father_in_dt_(father_in_dt) { } 211bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org 212bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org private: 213bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org BoundsCheckKey* key_; 214bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org int32_t lower_offset_; 215bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org int32_t upper_offset_; 216bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org HBasicBlock* basic_block_; 217bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org HBoundsCheck* lower_check_; 218bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org HBoundsCheck* upper_check_; 219bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org BoundsCheckBbData* next_in_bb_; 220bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org BoundsCheckBbData* father_in_dt_; 221bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org 222fb79f8683208e62002112b4406ec9dadda54dec2machenbach@chromium.org void MoveIndexIfNecessary(HValue* index_raw, 223fb79f8683208e62002112b4406ec9dadda54dec2machenbach@chromium.org HBoundsCheck* insert_before, 224fb79f8683208e62002112b4406ec9dadda54dec2machenbach@chromium.org HInstruction* end_of_scan_range) { 22538de99aae2d4efc5796aa6935c1648447ec32fc8machenbach@chromium.org // index_raw can be HAdd(index_base, offset), HSub(index_base, offset), 22638de99aae2d4efc5796aa6935c1648447ec32fc8machenbach@chromium.org // HConstant(offset) or index_base directly. 22738de99aae2d4efc5796aa6935c1648447ec32fc8machenbach@chromium.org // In the latter case, no need to move anything. 22838de99aae2d4efc5796aa6935c1648447ec32fc8machenbach@chromium.org if (index_raw->IsAdd() || index_raw->IsSub()) { 22938de99aae2d4efc5796aa6935c1648447ec32fc8machenbach@chromium.org HArithmeticBinaryOperation* index = 23038de99aae2d4efc5796aa6935c1648447ec32fc8machenbach@chromium.org HArithmeticBinaryOperation::cast(index_raw); 23138de99aae2d4efc5796aa6935c1648447ec32fc8machenbach@chromium.org HValue* left_input = index->left(); 23238de99aae2d4efc5796aa6935c1648447ec32fc8machenbach@chromium.org HValue* right_input = index->right(); 23338de99aae2d4efc5796aa6935c1648447ec32fc8machenbach@chromium.org bool must_move_index = false; 23438de99aae2d4efc5796aa6935c1648447ec32fc8machenbach@chromium.org bool must_move_left_input = false; 23538de99aae2d4efc5796aa6935c1648447ec32fc8machenbach@chromium.org bool must_move_right_input = false; 23638de99aae2d4efc5796aa6935c1648447ec32fc8machenbach@chromium.org for (HInstruction* cursor = end_of_scan_range; cursor != insert_before;) { 23738de99aae2d4efc5796aa6935c1648447ec32fc8machenbach@chromium.org if (cursor == left_input) must_move_left_input = true; 23838de99aae2d4efc5796aa6935c1648447ec32fc8machenbach@chromium.org if (cursor == right_input) must_move_right_input = true; 23938de99aae2d4efc5796aa6935c1648447ec32fc8machenbach@chromium.org if (cursor == index) must_move_index = true; 24038de99aae2d4efc5796aa6935c1648447ec32fc8machenbach@chromium.org if (cursor->previous() == NULL) { 24138de99aae2d4efc5796aa6935c1648447ec32fc8machenbach@chromium.org cursor = cursor->block()->dominator()->end(); 24238de99aae2d4efc5796aa6935c1648447ec32fc8machenbach@chromium.org } else { 24338de99aae2d4efc5796aa6935c1648447ec32fc8machenbach@chromium.org cursor = cursor->previous(); 24438de99aae2d4efc5796aa6935c1648447ec32fc8machenbach@chromium.org } 24538de99aae2d4efc5796aa6935c1648447ec32fc8machenbach@chromium.org } 24638de99aae2d4efc5796aa6935c1648447ec32fc8machenbach@chromium.org if (must_move_index) { 24738de99aae2d4efc5796aa6935c1648447ec32fc8machenbach@chromium.org index->Unlink(); 24838de99aae2d4efc5796aa6935c1648447ec32fc8machenbach@chromium.org index->InsertBefore(insert_before); 24938de99aae2d4efc5796aa6935c1648447ec32fc8machenbach@chromium.org } 25038de99aae2d4efc5796aa6935c1648447ec32fc8machenbach@chromium.org // The BCE algorithm only selects mergeable bounds checks that share 25138de99aae2d4efc5796aa6935c1648447ec32fc8machenbach@chromium.org // the same "index_base", so we'll only ever have to move constants. 25238de99aae2d4efc5796aa6935c1648447ec32fc8machenbach@chromium.org if (must_move_left_input) { 25338de99aae2d4efc5796aa6935c1648447ec32fc8machenbach@chromium.org HConstant::cast(left_input)->Unlink(); 25438de99aae2d4efc5796aa6935c1648447ec32fc8machenbach@chromium.org HConstant::cast(left_input)->InsertBefore(index); 25538de99aae2d4efc5796aa6935c1648447ec32fc8machenbach@chromium.org } 25638de99aae2d4efc5796aa6935c1648447ec32fc8machenbach@chromium.org if (must_move_right_input) { 25738de99aae2d4efc5796aa6935c1648447ec32fc8machenbach@chromium.org HConstant::cast(right_input)->Unlink(); 25838de99aae2d4efc5796aa6935c1648447ec32fc8machenbach@chromium.org HConstant::cast(right_input)->InsertBefore(index); 25938de99aae2d4efc5796aa6935c1648447ec32fc8machenbach@chromium.org } 26038de99aae2d4efc5796aa6935c1648447ec32fc8machenbach@chromium.org } else if (index_raw->IsConstant()) { 26138de99aae2d4efc5796aa6935c1648447ec32fc8machenbach@chromium.org HConstant* index = HConstant::cast(index_raw); 26238de99aae2d4efc5796aa6935c1648447ec32fc8machenbach@chromium.org bool must_move = false; 26338de99aae2d4efc5796aa6935c1648447ec32fc8machenbach@chromium.org for (HInstruction* cursor = end_of_scan_range; cursor != insert_before;) { 26438de99aae2d4efc5796aa6935c1648447ec32fc8machenbach@chromium.org if (cursor == index) must_move = true; 26538de99aae2d4efc5796aa6935c1648447ec32fc8machenbach@chromium.org if (cursor->previous() == NULL) { 26638de99aae2d4efc5796aa6935c1648447ec32fc8machenbach@chromium.org cursor = cursor->block()->dominator()->end(); 26738de99aae2d4efc5796aa6935c1648447ec32fc8machenbach@chromium.org } else { 26838de99aae2d4efc5796aa6935c1648447ec32fc8machenbach@chromium.org cursor = cursor->previous(); 26938de99aae2d4efc5796aa6935c1648447ec32fc8machenbach@chromium.org } 27038de99aae2d4efc5796aa6935c1648447ec32fc8machenbach@chromium.org } 27138de99aae2d4efc5796aa6935c1648447ec32fc8machenbach@chromium.org if (must_move) { 27238de99aae2d4efc5796aa6935c1648447ec32fc8machenbach@chromium.org index->Unlink(); 27338de99aae2d4efc5796aa6935c1648447ec32fc8machenbach@chromium.org index->InsertBefore(insert_before); 274fb79f8683208e62002112b4406ec9dadda54dec2machenbach@chromium.org } 275bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org } 276bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org } 277bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org 278fb79f8683208e62002112b4406ec9dadda54dec2machenbach@chromium.org void TightenCheck(HBoundsCheck* original_check, 27969f64b1a8bfa6f5418b7c1f71d4e0833f76e93edmachenbach@chromium.org HBoundsCheck* tighter_check, 28069f64b1a8bfa6f5418b7c1f71d4e0833f76e93edmachenbach@chromium.org int32_t new_offset) { 281e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(original_check->length() == tighter_check->length()); 282fb79f8683208e62002112b4406ec9dadda54dec2machenbach@chromium.org MoveIndexIfNecessary(tighter_check->index(), original_check, tighter_check); 283fb79f8683208e62002112b4406ec9dadda54dec2machenbach@chromium.org original_check->ReplaceAllUsesWith(original_check->index()); 284fb79f8683208e62002112b4406ec9dadda54dec2machenbach@chromium.org original_check->SetOperandAt(0, tighter_check->index()); 28569f64b1a8bfa6f5418b7c1f71d4e0833f76e93edmachenbach@chromium.org if (FLAG_trace_bce) { 2865de0074a922429f5e0ec2cf140c2d2989bf88140yangguo@chromium.org base::OS::Print("Tightened check #%d with offset %d from #%d\n", 2875de0074a922429f5e0ec2cf140c2d2989bf88140yangguo@chromium.org original_check->id(), new_offset, tighter_check->id()); 28869f64b1a8bfa6f5418b7c1f71d4e0833f76e93edmachenbach@chromium.org } 289bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org } 290bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org 291bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org DISALLOW_COPY_AND_ASSIGN(BoundsCheckBbData); 292bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org}; 293bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org 294bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org 295bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.orgstatic bool BoundsCheckKeyMatch(void* key1, void* key2) { 296bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org BoundsCheckKey* k1 = static_cast<BoundsCheckKey*>(key1); 297bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org BoundsCheckKey* k2 = static_cast<BoundsCheckKey*>(key2); 298bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org return k1->IndexBase() == k2->IndexBase() && k1->Length() == k2->Length(); 299bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org} 300bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org 301bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org 302bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.orgBoundsCheckTable::BoundsCheckTable(Zone* zone) 303bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org : ZoneHashMap(BoundsCheckKeyMatch, ZoneHashMap::kDefaultHashMapCapacity, 304bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org ZoneAllocationPolicy(zone)) { } 305bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org 306bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org 307bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.orgBoundsCheckBbData** BoundsCheckTable::LookupOrInsert(BoundsCheckKey* key, 308bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org Zone* zone) { 309bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org return reinterpret_cast<BoundsCheckBbData**>( 310bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org &(Lookup(key, key->Hash(), true, ZoneAllocationPolicy(zone))->value)); 311bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org} 312bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org 313bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org 314bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.orgvoid BoundsCheckTable::Insert(BoundsCheckKey* key, 315bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org BoundsCheckBbData* data, 316bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org Zone* zone) { 317bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org Lookup(key, key->Hash(), true, ZoneAllocationPolicy(zone))->value = data; 318bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org} 319bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org 320bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org 321bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.orgvoid BoundsCheckTable::Delete(BoundsCheckKey* key) { 322bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org Remove(key, key->Hash()); 323bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org} 324bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org 325bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org 326528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.orgclass HBoundsCheckEliminationState { 327528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.org public: 328528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.org HBasicBlock* block_; 329528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.org BoundsCheckBbData* bb_data_list_; 330528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.org int index_; 331528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.org}; 332528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.org 333528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.org 334bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org// Eliminates checks in bb and recursively in the dominated blocks. 335bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org// Also replace the results of check instructions with the original value, if 336bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org// the result is used. This is safe now, since we don't do code motion after 337bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org// this point. It enables better register allocation since the value produced 338bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org// by check instructions is really a copy of the original value. 339bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.orgvoid HBoundsCheckEliminationPhase::EliminateRedundantBoundsChecks( 340528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.org HBasicBlock* entry) { 341528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.org // Allocate the stack. 342528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.org HBoundsCheckEliminationState* stack = 343528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.org zone()->NewArray<HBoundsCheckEliminationState>(graph()->blocks()->length()); 344528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.org 345528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.org // Explicitly push the entry block. 346528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.org stack[0].block_ = entry; 347528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.org stack[0].bb_data_list_ = PreProcessBlock(entry); 348528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.org stack[0].index_ = 0; 349528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.org int stack_depth = 1; 350528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.org 351528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.org // Implement depth-first traversal with a stack. 352528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.org while (stack_depth > 0) { 353528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.org int current = stack_depth - 1; 354528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.org HBoundsCheckEliminationState* state = &stack[current]; 355528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.org const ZoneList<HBasicBlock*>* children = state->block_->dominated_blocks(); 356528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.org 357528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.org if (state->index_ < children->length()) { 358528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.org // Recursively visit children blocks. 359528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.org HBasicBlock* child = children->at(state->index_++); 360528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.org int next = stack_depth++; 361528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.org stack[next].block_ = child; 362528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.org stack[next].bb_data_list_ = PreProcessBlock(child); 363528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.org stack[next].index_ = 0; 364528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.org } else { 365528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.org // Finished with all children; post process the block. 366528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.org PostProcessBlock(state->block_, state->bb_data_list_); 367528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.org stack_depth--; 368528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.org } 369528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.org } 370528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.org} 371528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.org 372528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.org 373528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.orgBoundsCheckBbData* HBoundsCheckEliminationPhase::PreProcessBlock( 374bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org HBasicBlock* bb) { 375bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org BoundsCheckBbData* bb_data_list = NULL; 376bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org 377bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org for (HInstructionIterator it(bb); !it.Done(); it.Advance()) { 378bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org HInstruction* i = it.Current(); 379bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org if (!i->IsBoundsCheck()) continue; 380bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org 381bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org HBoundsCheck* check = HBoundsCheck::cast(i); 382bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org int32_t offset; 383bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org BoundsCheckKey* key = 384bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org BoundsCheckKey::Create(zone(), check, &offset); 385bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org if (key == NULL) continue; 386bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org BoundsCheckBbData** data_p = table_.LookupOrInsert(key, zone()); 387bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org BoundsCheckBbData* data = *data_p; 388bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org if (data == NULL) { 389bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org bb_data_list = new(zone()) BoundsCheckBbData(key, 390bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org offset, 391bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org offset, 392bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org bb, 393bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org check, 394bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org check, 395bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org bb_data_list, 396bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org NULL); 397bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org *data_p = bb_data_list; 39869f64b1a8bfa6f5418b7c1f71d4e0833f76e93edmachenbach@chromium.org if (FLAG_trace_bce) { 3995de0074a922429f5e0ec2cf140c2d2989bf88140yangguo@chromium.org base::OS::Print("Fresh bounds check data for block #%d: [%d]\n", 4005de0074a922429f5e0ec2cf140c2d2989bf88140yangguo@chromium.org bb->block_id(), offset); 40169f64b1a8bfa6f5418b7c1f71d4e0833f76e93edmachenbach@chromium.org } 402bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org } else if (data->OffsetIsCovered(offset)) { 403fb732b17922ea75830be4db6b80534c4827d8a55jkummerow@chromium.org bb->graph()->isolate()->counters()-> 404fb732b17922ea75830be4db6b80534c4827d8a55jkummerow@chromium.org bounds_checks_eliminated()->Increment(); 40569f64b1a8bfa6f5418b7c1f71d4e0833f76e93edmachenbach@chromium.org if (FLAG_trace_bce) { 4065de0074a922429f5e0ec2cf140c2d2989bf88140yangguo@chromium.org base::OS::Print("Eliminating bounds check #%d, offset %d is covered\n", 4075de0074a922429f5e0ec2cf140c2d2989bf88140yangguo@chromium.org check->id(), offset); 40869f64b1a8bfa6f5418b7c1f71d4e0833f76e93edmachenbach@chromium.org } 409bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org check->DeleteAndReplaceWith(check->ActualValue()); 410fb79f8683208e62002112b4406ec9dadda54dec2machenbach@chromium.org } else if (data->BasicBlock() == bb) { 41169f64b1a8bfa6f5418b7c1f71d4e0833f76e93edmachenbach@chromium.org // TODO(jkummerow): I think the following logic would be preferable: 41269f64b1a8bfa6f5418b7c1f71d4e0833f76e93edmachenbach@chromium.org // if (data->Basicblock() == bb || 41369f64b1a8bfa6f5418b7c1f71d4e0833f76e93edmachenbach@chromium.org // graph()->use_optimistic_licm() || 41469f64b1a8bfa6f5418b7c1f71d4e0833f76e93edmachenbach@chromium.org // bb->IsLoopSuccessorDominator()) { 41569f64b1a8bfa6f5418b7c1f71d4e0833f76e93edmachenbach@chromium.org // data->CoverCheck(check, offset) 41669f64b1a8bfa6f5418b7c1f71d4e0833f76e93edmachenbach@chromium.org // } else { 41769f64b1a8bfa6f5418b7c1f71d4e0833f76e93edmachenbach@chromium.org // /* add pristine BCBbData like in (data == NULL) case above */ 41869f64b1a8bfa6f5418b7c1f71d4e0833f76e93edmachenbach@chromium.org // } 41969f64b1a8bfa6f5418b7c1f71d4e0833f76e93edmachenbach@chromium.org // Even better would be: distinguish between read-only dominator-imposed 42069f64b1a8bfa6f5418b7c1f71d4e0833f76e93edmachenbach@chromium.org // knowledge and modifiable upper/lower checks. 42169f64b1a8bfa6f5418b7c1f71d4e0833f76e93edmachenbach@chromium.org // What happens currently is that the first bounds check in a dominated 42269f64b1a8bfa6f5418b7c1f71d4e0833f76e93edmachenbach@chromium.org // block will stay around while any further checks are hoisted out, 42369f64b1a8bfa6f5418b7c1f71d4e0833f76e93edmachenbach@chromium.org // which doesn't make sense. Investigate/fix this in a future CL. 424fb79f8683208e62002112b4406ec9dadda54dec2machenbach@chromium.org data->CoverCheck(check, offset); 4250f6d2bb71d05a2a2fa33acccf8a0ef762e57148fhpayer@chromium.org } else if (graph()->use_optimistic_licm() || 4260f6d2bb71d05a2a2fa33acccf8a0ef762e57148fhpayer@chromium.org bb->IsLoopSuccessorDominator()) { 427bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org int32_t new_lower_offset = offset < data->LowerOffset() 428bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org ? offset 429bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org : data->LowerOffset(); 430bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org int32_t new_upper_offset = offset > data->UpperOffset() 431bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org ? offset 432bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org : data->UpperOffset(); 433bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org bb_data_list = new(zone()) BoundsCheckBbData(key, 434bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org new_lower_offset, 435bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org new_upper_offset, 436bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org bb, 437bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org data->LowerCheck(), 438bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org data->UpperCheck(), 439bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org bb_data_list, 440bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org data); 44169f64b1a8bfa6f5418b7c1f71d4e0833f76e93edmachenbach@chromium.org if (FLAG_trace_bce) { 4425de0074a922429f5e0ec2cf140c2d2989bf88140yangguo@chromium.org base::OS::Print("Updated bounds check data for block #%d: [%d - %d]\n", 4435de0074a922429f5e0ec2cf140c2d2989bf88140yangguo@chromium.org bb->block_id(), new_lower_offset, new_upper_offset); 44469f64b1a8bfa6f5418b7c1f71d4e0833f76e93edmachenbach@chromium.org } 445bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org table_.Insert(key, bb_data_list, zone()); 446bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org } 447bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org } 448bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org 449528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.org return bb_data_list; 450528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.org} 451528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.org 452bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org 453528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.orgvoid HBoundsCheckEliminationPhase::PostProcessBlock( 454528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.org HBasicBlock* block, BoundsCheckBbData* data) { 455528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.org while (data != NULL) { 456bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org if (data->FatherInDominatorTree()) { 457bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org table_.Insert(data->Key(), data->FatherInDominatorTree(), zone()); 458bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org } else { 459bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org table_.Delete(data->Key()); 460bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org } 461528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.org data = data->NextInBasicBlock(); 462bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org } 463bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org} 464bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org 465bee51999422c0eeaae85ed99b5c0bd4126510ff1danno@chromium.org} } // namespace v8::internal 466