Revision: 7674
Author: [email protected]
Date: Wed Apr 20 03:38:08 2011
Log: Change the Hydrogen representation of uses.
Rather than representing a use as a pointer to an HValue and then searching
for the specific (ambiguous) operand, we now represent a use as a pair of an
HValue and the input operand index. Additionally, use a linked list instead
of a growable array list since we never use random access.
This allows us to remove a bunch of similarly named and subtly different
functions from the HValue API. The cost in extra zone allocation per use is
partially offset by reusing use list nodes when replacing a use of one value
with another.
[email protected],[email protected]
Review URL: http://codereview.chromium.org/6881044
http://code.google.com/p/v8/source/detail?r=7674
Modified:
/branches/bleeding_edge/src/arm/lithium-arm.cc
/branches/bleeding_edge/src/hydrogen-instructions.cc
/branches/bleeding_edge/src/hydrogen-instructions.h
/branches/bleeding_edge/src/hydrogen.cc
/branches/bleeding_edge/src/hydrogen.h
/branches/bleeding_edge/src/ia32/lithium-ia32.cc
/branches/bleeding_edge/src/x64/lithium-x64.cc
=======================================
--- /branches/bleeding_edge/src/arm/lithium-arm.cc Wed Apr 20 02:08:26 2011
+++ /branches/bleeding_edge/src/arm/lithium-arm.cc Wed Apr 20 03:38:08 2011
@@ -858,22 +858,20 @@
// Shift operations can only deoptimize if we do a logical shift
// by 0 and the result cannot be truncated to int32.
- bool can_deopt = (op == Token::SHR && constant_value == 0);
- if (can_deopt) {
- bool can_truncate = true;
- for (int i = 0; i < instr->uses()->length(); i++) {
- if (!instr->uses()->at(i)->CheckFlag(HValue::kTruncatingToInt32)) {
- can_truncate = false;
+ bool may_deopt = (op == Token::SHR && constant_value == 0);
+ bool does_deopt = false;
+ if (may_deopt) {
+ for (HUseIterator it(instr->uses()); !it.Done(); it.Advance()) {
+ if (!it.value()->CheckFlag(HValue::kTruncatingToInt32)) {
+ does_deopt = true;
break;
}
}
- can_deopt = !can_truncate;
}
LInstruction* result =
- DefineSameAsFirst(new LShiftI(op, left, right, can_deopt));
- if (can_deopt) AssignEnvironment(result);
- return result;
+ DefineSameAsFirst(new LShiftI(op, left, right, does_deopt));
+ return does_deopt ? AssignEnvironment(result) : result;
}
=======================================
--- /branches/bleeding_edge/src/hydrogen-instructions.cc Tue Apr 19
02:11:21 2011
+++ /branches/bleeding_edge/src/hydrogen-instructions.cc Wed Apr 20
03:38:08 2011
@@ -264,31 +264,60 @@
}
-int HValue::LookupOperandIndex(int occurrence_index, HValue* op) {
- for (int i = 0; i < OperandCount(); ++i) {
- if (OperandAt(i) == op) {
- if (occurrence_index == 0) return i;
- --occurrence_index;
- }
- }
- return -1;
+bool HValue::IsDefinedAfter(HBasicBlock* other) const {
+ return block()->block_id() > other->block_id();
+}
+
+
+HUseIterator::HUseIterator(HUseListNode* head) : next_(head) {
+ Advance();
+}
+
+
+void HUseIterator::Advance() {
+ current_ = next_;
+ if (current_ != NULL) {
+ next_ = current_->tail();
+ value_ = current_->value();
+ index_ = current_->index();
+ }
}
-bool HValue::IsDefinedAfter(HBasicBlock* other) const {
- return block()->block_id() > other->block_id();
+int HValue::UseCount() const {
+ int count = 0;
+ for (HUseIterator it(uses()); !it.Done(); it.Advance()) ++count;
+ return count;
}
-bool HValue::UsesMultipleTimes(HValue* op) {
- bool seen = false;
- for (int i = 0; i < OperandCount(); ++i) {
- if (OperandAt(i) == op) {
- if (seen) return true;
- seen = true;
- }
- }
- return false;
+HUseListNode* HValue::RemoveUse(HValue* value, int index) {
+ HUseListNode* previous = NULL;
+ HUseListNode* current = use_list_;
+ while (current != NULL) {
+ if (current->value() == value && current->index() == index) {
+ if (previous == NULL) {
+ use_list_ = current->tail();
+ } else {
+ previous->set_tail(current->tail());
+ }
+ break;
+ }
+
+ previous = current;
+ current = current->tail();
+ }
+
+#ifdef DEBUG
+ // Do not reuse use list nodes in debug mode, zap them.
+ if (current != NULL) {
+ HUseListNode* temp =
+ new HUseListNode(current->value(), current->index(), NULL);
+ current->Zap();
+ current = temp;
+ }
+#endif
+ return current;
}
@@ -335,20 +364,25 @@
}
-void HValue::ReplaceAndDelete(HValue* other) {
- if (other != NULL) ReplaceValue(other);
- Delete();
+void HValue::DeleteAndReplaceWith(HValue* other) {
+ // We replace all uses first, so Delete can assert that there are none.
+ if (other != NULL) ReplaceAllUsesWith(other);
+ ASSERT(HasNoUses());
+ ClearOperands();
+ DeleteFromGraph();
}
-void HValue::ReplaceValue(HValue* other) {
- for (int i = 0; i < uses_.length(); ++i) {
- HValue* use = uses_[i];
- ASSERT(!use->block()->IsStartBlock());
- InternalReplaceAtUse(use, other);
- other->uses_.Add(use);
- }
- uses_.Rewind(0);
+void HValue::ReplaceAllUsesWith(HValue* other) {
+ while (use_list_ != NULL) {
+ HUseListNode* list_node = use_list_;
+ HValue* value = list_node->value();
+ ASSERT(!value->block()->IsStartBlock());
+ value->InternalSetOperandAt(list_node->index(), other);
+ use_list_ = list_node->tail();
+ list_node->set_tail(other->use_list_);
+ other->use_list_ = list_node;
+ }
}
@@ -357,44 +391,6 @@
SetOperandAt(i, NULL);
}
}
-
-
-void HValue::Delete() {
- ASSERT(HasNoUses());
- ClearOperands();
- DeleteFromGraph();
-}
-
-
-void HValue::ReplaceAtUse(HValue* use, HValue* other) {
- for (int i = 0; i < use->OperandCount(); ++i) {
- if (use->OperandAt(i) == this) {
- use->SetOperandAt(i, other);
- }
- }
-}
-
-
-void HValue::ReplaceFirstAtUse(HValue* use, HValue* other, Representation
r) {
- for (int i = 0; i < use->OperandCount(); ++i) {
- if (use->RequiredInputRepresentation(i).Equals(r) &&
- use->OperandAt(i) == this) {
- use->SetOperandAt(i, other);
- return;
- }
- }
-}
-
-
-void HValue::InternalReplaceAtUse(HValue* use, HValue* other) {
- for (int i = 0; i < use->OperandCount(); ++i) {
- if (use->OperandAt(i) == this) {
- // Call internal method that does not update use lists. The caller is
- // responsible for doing so.
- use->InternalSetOperandAt(i, other);
- }
- }
-}
void HValue::SetBlock(HBasicBlock* block) {
@@ -427,9 +423,20 @@
void HValue::RegisterUse(int index, HValue* new_value) {
HValue* old_value = OperandAt(index);
if (old_value == new_value) return;
- if (old_value != NULL) old_value->uses_.RemoveElement(this);
+
+ HUseListNode* removed = NULL;
+ if (old_value != NULL) {
+ removed = old_value->RemoveUse(this, index);
+ }
+
if (new_value != NULL) {
- new_value->uses_.Add(this);
+ if (removed == NULL) {
+ new_value->use_list_ =
+ new HUseListNode(this, index, new_value->use_list_);
+ } else {
+ removed->set_tail(new_value->use_list_);
+ new_value->use_list_ = removed;
+ }
}
}
@@ -926,7 +933,7 @@
stream->Add(" ");
}
stream->Add(" uses%d_%di_%dd_%dt]",
- uses()->length(),
+ UseCount(),
int32_non_phi_uses() + int32_indirect_uses(),
double_non_phi_uses() + double_indirect_uses(),
tagged_non_phi_uses() + tagged_indirect_uses());
@@ -944,8 +951,8 @@
bool HPhi::HasRealUses() {
- for (int i = 0; i < uses()->length(); i++) {
- if (!uses()->at(i)->IsPhi()) return true;
+ for (HUseIterator it(uses()); !it.Done(); it.Advance()) {
+ if (!it.value()->IsPhi()) return true;
}
return false;
}
@@ -978,12 +985,11 @@
void HPhi::InitRealUses(int phi_id) {
// Initialize real uses.
phi_id_ = phi_id;
- for (int j = 0; j < uses()->length(); j++) {
- HValue* use = uses()->at(j);
- if (!use->IsPhi()) {
- int index = use->LookupOperandIndex(0, this);
- Representation req_rep = use->RequiredInputRepresentation(index);
- non_phi_uses_[req_rep.kind()]++;
+ for (HUseIterator it(uses()); !it.Done(); it.Advance()) {
+ HValue* value = it.value();
+ if (!value->IsPhi()) {
+ Representation rep = value->RequiredInputRepresentation(it.index());
+ ++non_phi_uses_[rep.kind()];
}
}
}
=======================================
--- /branches/bleeding_edge/src/hydrogen-instructions.h Tue Apr 19 02:11:21
2011
+++ /branches/bleeding_edge/src/hydrogen-instructions.h Wed Apr 20 03:38:08
2011
@@ -403,6 +403,62 @@
};
+class HUseListNode: public ZoneObject {
+ public:
+ HUseListNode(HValue* value, int index, HUseListNode* tail)
+ : tail_(tail), value_(value), index_(index) {
+ }
+
+ HUseListNode* tail() const { return tail_; }
+ HValue* value() const { return value_; }
+ int index() const { return index_; }
+
+ void set_tail(HUseListNode* list) { tail_ = list; }
+
+#ifdef DEBUG
+ void Zap() {
+ tail_ = reinterpret_cast<HUseListNode*>(1);
+ value_ = NULL;
+ index_ = -1;
+ }
+#endif
+
+ private:
+ HUseListNode* tail_;
+ HValue* value_;
+ int index_;
+};
+
+
+// We reuse use list nodes behind the scenes as uses are added and deleted.
+// This class is the safe way to iterate uses while deleting them.
+class HUseIterator BASE_EMBEDDED {
+ public:
+ bool Done() { return current_ == NULL; }
+ void Advance();
+
+ HValue* value() {
+ ASSERT(!Done());
+ return value_;
+ }
+
+ int index() {
+ ASSERT(!Done());
+ return index_;
+ }
+
+ private:
+ explicit HUseIterator(HUseListNode* head);
+
+ HUseListNode* current_;
+ HUseListNode* next_;
+ HValue* value_;
+ int index_;
+
+ friend class HValue;
+};
+
+
class HValue: public ZoneObject {
public:
static const int kNoNumber = -1;
@@ -473,6 +529,7 @@
HValue() : block_(NULL),
id_(kNoNumber),
type_(HType::Tagged()),
+ use_list_(NULL),
range_(NULL),
flags_(0) {}
virtual ~HValue() {}
@@ -483,7 +540,7 @@
int id() const { return id_; }
void set_id(int id) { id_ = id; }
- SmallPointerList<HValue>* uses() { return &uses_; }
+ HUseIterator uses() const { return HUseIterator(use_list_); }
virtual bool EmitAtUses() { return false; }
Representation representation() const { return representation_; }
@@ -498,7 +555,7 @@
HType type() const { return type_; }
void set_type(HType type) {
- ASSERT(uses_.length() == 0);
+ ASSERT(HasNoUses());
type_ = type;
}
@@ -524,16 +581,13 @@
virtual HValue* OperandAt(int index) = 0;
void SetOperandAt(int index, HValue* value);
- int LookupOperandIndex(int occurrence_index, HValue* op);
- bool UsesMultipleTimes(HValue* op);
-
- void ReplaceAndDelete(HValue* other);
- void ReplaceValue(HValue* other);
- void ReplaceAtUse(HValue* use, HValue* other);
- void ReplaceFirstAtUse(HValue* use, HValue* other, Representation r);
- bool HasNoUses() const { return uses_.is_empty(); }
+ void DeleteAndReplaceWith(HValue* other);
+ bool HasNoUses() const { return use_list_ == NULL; }
+ bool HasMultipleUses() const {
+ return use_list_ != NULL && use_list_->tail() != NULL;
+ }
+ int UseCount() const;
void ClearOperands();
- void Delete();
int flags() const { return flags_; }
void SetFlag(Flag f) { flags_ |= (1 << f); }
@@ -611,7 +665,12 @@
return ChangesFlagsMask() & ~(1 << kChangesOsrEntries);
}
- void InternalReplaceAtUse(HValue* use, HValue* other);
+ // Remove the matching use from the use list if present. Returns the
+ // removed list node or NULL.
+ HUseListNode* RemoveUse(HValue* value, int index);
+
+ void ReplaceAllUsesWith(HValue* other);
+
void RegisterUse(int index, HValue* new_value);
HBasicBlock* block_;
@@ -622,7 +681,7 @@
Representation representation_;
HType type_;
- SmallPointerList<HValue> uses_;
+ HUseListNode* use_list_;
Range* range_;
int flags_;
@@ -2257,7 +2316,7 @@
void SetInputRepresentation(Representation r);
virtual bool EmitAtUses() {
- return !HasSideEffects() && (uses()->length() <= 1);
+ return !HasSideEffects() && !HasMultipleUses();
}
virtual Representation RequiredInputRepresentation(int index) const {
@@ -2299,7 +2358,7 @@
}
virtual bool EmitAtUses() {
- return !HasSideEffects() && (uses()->length() <= 1);
+ return !HasSideEffects() && !HasMultipleUses();
}
virtual Representation RequiredInputRepresentation(int index) const {
@@ -2322,7 +2381,7 @@
}
virtual bool EmitAtUses() {
- return !HasSideEffects() && (uses()->length() <= 1);
+ return !HasSideEffects() && !HasMultipleUses();
}
virtual Representation RequiredInputRepresentation(int index) const {
@@ -2382,7 +2441,7 @@
}
virtual bool EmitAtUses() {
- return !HasSideEffects() && (uses()->length() <= 1);
+ return !HasSideEffects() && !HasMultipleUses();
}
virtual Representation RequiredInputRepresentation(int index) const {
@@ -2504,7 +2563,7 @@
HValue* right() { return OperandAt(2); }
virtual bool EmitAtUses() {
- return !HasSideEffects() && (uses()->length() <= 1);
+ return !HasSideEffects() && !HasMultipleUses();
}
virtual Representation RequiredInputRepresentation(int index) const {
=======================================
--- /branches/bleeding_edge/src/hydrogen.cc Fri Apr 15 00:58:22 2011
+++ /branches/bleeding_edge/src/hydrogen.cc Wed Apr 20 03:38:08 2011
@@ -644,7 +644,7 @@
HInstruction* instr = blocks()->at(i)->first();
while (instr != NULL) {
HValue* value = instr->Canonicalize();
- if (value != instr) instr->ReplaceAndDelete(value);
+ if (value != instr) instr->DeleteAndReplaceWith(value);
instr = instr->next();
}
}
@@ -726,9 +726,9 @@
void HGraph::EliminateRedundantPhis() {
HPhase phase("Redundant phi elimination", this);
- // Worklist of phis that can potentially be eliminated. Initialized
- // with all phi nodes. When elimination of a phi node modifies
- // another phi node the modified phi node is added to the worklist.
+ // Worklist of phis that can potentially be eliminated. Initialized with
+ // all phi nodes. When elimination of a phi node modifies another phi
node
+ // the modified phi node is added to the worklist.
ZoneList<HPhi*> worklist(blocks_.length());
for (int i = 0; i < blocks_.length(); ++i) {
worklist.AddAll(*blocks_[i]->phis());
@@ -742,18 +742,14 @@
if (block == NULL) continue;
// Get replacement value if phi is redundant.
- HValue* value = phi->GetRedundantReplacement();
-
- if (value != NULL) {
- // Iterate through uses finding the ones that should be
- // replaced.
- SmallPointerList<HValue>* uses = phi->uses();
- while (!uses->is_empty()) {
- HValue* use = uses->RemoveLast();
- if (use != NULL) {
- phi->ReplaceAtUse(use, value);
- if (use->IsPhi()) worklist.Add(HPhi::cast(use));
- }
+ HValue* replacement = phi->GetRedundantReplacement();
+
+ if (replacement != NULL) {
+ // Iterate through the uses and replace them all.
+ for (HUseIterator it(phi->uses()); !it.Done(); it.Advance()) {
+ HValue* value = it.value();
+ value->SetOperandAt(it.index(), replacement);
+ if (value->IsPhi()) worklist.Add(HPhi::cast(value));
}
block->RemovePhi(phi);
}
@@ -831,8 +827,8 @@
HValue* current = worklist->RemoveLast();
in_worklist.Remove(current->id());
if (current->UpdateInferredType()) {
- for (int j = 0; j < current->uses()->length(); j++) {
- HValue* use = current->uses()->at(j);
+ for (HUseIterator it(current->uses()); !it.Done(); it.Advance()) {
+ HValue* use = it.value();
if (!in_worklist.Contains(use->id())) {
in_worklist.Add(use->id());
worklist->Add(use);
@@ -1445,7 +1441,7 @@
instr->Mnemonic(),
other->id(),
other->Mnemonic());
- instr->ReplaceAndDelete(other);
+ instr->DeleteAndReplaceWith(other);
} else {
map->Add(instr);
}
@@ -1529,12 +1525,12 @@
}
-void HInferRepresentation::AddDependantsToWorklist(HValue* current) {
- for (int i = 0; i < current->uses()->length(); ++i) {
- AddToWorklist(current->uses()->at(i));
- }
- for (int i = 0; i < current->OperandCount(); ++i) {
- AddToWorklist(current->OperandAt(i));
+void HInferRepresentation::AddDependantsToWorklist(HValue* value) {
+ for (HUseIterator it(value->uses()); !it.Done(); it.Advance()) {
+ AddToWorklist(it.value());
+ }
+ for (int i = 0; i < value->OperandCount(); ++i) {
+ AddToWorklist(value->OperandAt(i));
}
}
@@ -1543,37 +1539,30 @@
// given as the parameter has a benefit in terms of less necessary type
// conversions. If there is a benefit, then the representation of the
value is
// specialized.
-void HInferRepresentation::InferBasedOnUses(HValue* current) {
- Representation r = current->representation();
- if (r.IsSpecialization() || current->HasNoUses()) return;
- ASSERT(current->CheckFlag(HValue::kFlexibleRepresentation));
- Representation new_rep = TryChange(current);
+void HInferRepresentation::InferBasedOnUses(HValue* value) {
+ Representation r = value->representation();
+ if (r.IsSpecialization() || value->HasNoUses()) return;
+ ASSERT(value->CheckFlag(HValue::kFlexibleRepresentation));
+ Representation new_rep = TryChange(value);
if (!new_rep.IsNone()) {
- if (!current->representation().Equals(new_rep)) {
- current->ChangeRepresentation(new_rep);
- AddDependantsToWorklist(current);
+ if (!value->representation().Equals(new_rep)) {
+ value->ChangeRepresentation(new_rep);
+ AddDependantsToWorklist(value);
}
}
}
-Representation HInferRepresentation::TryChange(HValue* current) {
+Representation HInferRepresentation::TryChange(HValue* value) {
// Array of use counts for each representation.
- int use_count[Representation::kNumRepresentations];
- for (int i = 0; i < Representation::kNumRepresentations; i++) {
- use_count[i] = 0;
- }
-
- for (int i = 0; i < current->uses()->length(); ++i) {
- HValue* use = current->uses()->at(i);
- int index = use->LookupOperandIndex(0, current);
- Representation req_rep = use->RequiredInputRepresentation(index);
- if (req_rep.IsNone()) continue;
- if (use->IsPhi()) {
- HPhi* phi = HPhi::cast(use);
- phi->AddIndirectUsesTo(&use_count[0]);
- }
- use_count[req_rep.kind()]++;
+ int use_count[Representation::kNumRepresentations] = { 0 };
+
+ for (HUseIterator it(value->uses()); !it.Done(); it.Advance()) {
+ HValue* use = it.value();
+ Representation rep = use->RequiredInputRepresentation(it.index());
+ if (rep.IsNone()) continue;
+ if (use->IsPhi()) HPhi::cast(use)->AddIndirectUsesTo(&use_count[0]);
+ ++use_count[rep.kind()];
}
int tagged_count = use_count[Representation::kTagged];
int double_count = use_count[Representation::kDouble];
@@ -1581,7 +1570,7 @@
int non_tagged_count = double_count + int32_count;
// If a non-loop phi has tagged uses, don't convert it to untagged.
- if (current->IsPhi() && !current->block()->IsLoopHeader()) {
+ if (value->IsPhi() && !value->block()->IsLoopHeader()) {
if (tagged_count > 0) return Representation::None();
}
@@ -1602,41 +1591,39 @@
void HInferRepresentation::Analyze() {
HPhase phase("Infer representations", graph_);
- // (1) Initialize bit vectors and count real uses. Each phi
- // gets a bit-vector of length <number of phis>.
+ // (1) Initialize bit vectors and count real uses. Each phi gets a
+ // bit-vector of length <number of phis>.
const ZoneList<HPhi*>* phi_list = graph_->phi_list();
- int num_phis = phi_list->length();
- ScopedVector<BitVector*> connected_phis(num_phis);
- for (int i = 0; i < num_phis; i++) {
+ int phi_count = phi_list->length();
+ ScopedVector<BitVector*> connected_phis(phi_count);
+ for (int i = 0; i < phi_count; ++i) {
phi_list->at(i)->InitRealUses(i);
- connected_phis[i] = new(zone()) BitVector(num_phis);
+ connected_phis[i] = new(zone()) BitVector(phi_count);
connected_phis[i]->Add(i);
}
- // (2) Do a fixed point iteration to find the set of connected phis.
- // A phi is connected to another phi if its value is used either
- // directly or indirectly through a transitive closure of the def-use
- // relation.
+ // (2) Do a fixed point iteration to find the set of connected phis. A
+ // phi is connected to another phi if its value is used either directly
or
+ // indirectly through a transitive closure of the def-use relation.
bool change = true;
while (change) {
change = false;
- for (int i = 0; i < num_phis; i++) {
+ for (int i = 0; i < phi_count; ++i) {
HPhi* phi = phi_list->at(i);
- for (int j = 0; j < phi->uses()->length(); j++) {
- HValue* use = phi->uses()->at(j);
+ for (HUseIterator it(phi->uses()); !it.Done(); it.Advance()) {
+ HValue* use = it.value();
if (use->IsPhi()) {
- int phi_use = HPhi::cast(use)->phi_id();
- if (connected_phis[i]->UnionIsChanged(*connected_phis[phi_use]))
{
- change = true;
- }
+ int id = HPhi::cast(use)->phi_id();
+ change = change ||
+ connected_phis[i]->UnionIsChanged(*connected_phis[id]);
}
}
}
}
- // (3) Sum up the non-phi use counts of all connected phis.
- // Don't include the non-phi uses of the phi itself.
- for (int i = 0; i < num_phis; i++) {
+ // (3) Sum up the non-phi use counts of all connected phis. Don't
include
+ // the non-phi uses of the phi itself.
+ for (int i = 0; i < phi_count; ++i) {
HPhi* phi = phi_list->at(i);
for (BitVector::Iterator it(connected_phis.at(i));
!it.Done();
@@ -1746,17 +1733,16 @@
void HGraph::InsertRepresentationChangeForUse(HValue* value,
- HValue* use,
+ HValue* use_value,
+ int use_index,
Representation to) {
// Insert the representation change right before its use. For phi-uses we
// insert at the end of the corresponding predecessor.
HInstruction* next = NULL;
- if (use->IsPhi()) {
- int index = 0;
- while (use->OperandAt(index) != value) ++index;
- next = use->block()->predecessors()->at(index)->end();
+ if (use_value->IsPhi()) {
+ next = use_value->block()->predecessors()->at(use_index)->end();
} else {
- next = HInstruction::cast(use);
+ next = HInstruction::cast(use_value);
}
// For constants we try to make the representation change at compile
@@ -1764,7 +1750,7 @@
// information we treat constants like normal instructions and insert the
// change instructions for them.
HInstruction* new_value = NULL;
- bool is_truncating = use->CheckFlag(HValue::kTruncatingToInt32);
+ bool is_truncating = use_value->CheckFlag(HValue::kTruncatingToInt32);
if (value->IsConstant()) {
HConstant* constant = HConstant::cast(value);
// Try to create a new copy of the constant with the new
representation.
@@ -1779,89 +1765,26 @@
}
new_value->InsertBefore(next);
- value->ReplaceFirstAtUse(use, new_value, to);
+ use_value->SetOperandAt(use_index, new_value);
}
-int CompareConversionUses(HValue* a,
- HValue* b,
- Representation a_rep,
- Representation b_rep) {
- if (a_rep.kind() > b_rep.kind()) {
- // Make sure specializations are separated in the result array.
- return 1;
- }
- // Put truncating conversions before non-truncating conversions.
- bool a_truncate = a->CheckFlag(HValue::kTruncatingToInt32);
- bool b_truncate = b->CheckFlag(HValue::kTruncatingToInt32);
- if (a_truncate != b_truncate) {
- return a_truncate ? -1 : 1;
- }
- // Sort by increasing block ID.
- return a->block()->block_id() - b->block()->block_id();
-}
-
-
-void HGraph::InsertRepresentationChangesForValue(
- HValue* current,
- ZoneList<HValue*>* to_convert,
- ZoneList<Representation>* to_convert_reps) {
- Representation r = current->representation();
+void HGraph::InsertRepresentationChangesForValue(HValue* value) {
+ Representation r = value->representation();
if (r.IsNone()) return;
- if (current->uses()->is_empty()) return;
-
- // Collect the representation changes in a sorted list. This allows
- // us to avoid duplicate changes without searching the list.
- ASSERT(to_convert->is_empty());
- ASSERT(to_convert_reps->is_empty());
- for (int i = 0; i < current->uses()->length(); ++i) {
- HValue* use = current->uses()->at(i);
- // The occurrences index means the index within the operand array
of "use"
- // at which "current" is used. While iterating through the use array we
- // also have to iterate over the different occurrence indices.
- int occurrence_index = 0;
- if (use->UsesMultipleTimes(current)) {
- occurrence_index = current->uses()->CountOccurrences(use, 0, i - 1);
- if (FLAG_trace_representation) {
- PrintF("Instruction %d is used multiple times at %d;
occurrence=%d\n",
- current->id(),
- use->id(),
- occurrence_index);
- }
- }
- int operand_index = use->LookupOperandIndex(occurrence_index, current);
- Representation req = use->RequiredInputRepresentation(operand_index);
+ if (value->HasNoUses()) return;
+
+ for (HUseIterator it(value->uses()); !it.Done(); it.Advance()) {
+ HValue* use_value = it.value();
+ int use_index = it.index();
+ Representation req = use_value->RequiredInputRepresentation(use_index);
if (req.IsNone() || req.Equals(r)) continue;
- int index = 0;
- while (index < to_convert->length() &&
- CompareConversionUses(to_convert->at(index),
- use,
- to_convert_reps->at(index),
- req) < 0) {
- ++index;
- }
- if (FLAG_trace_representation) {
- PrintF("Inserting a representation change to %s of %d for use
at %d\n",
- req.Mnemonic(),
- current->id(),
- use->id());
- }
- to_convert->InsertAt(index, use);
- to_convert_reps->InsertAt(index, req);
- }
-
- for (int i = 0; i < to_convert->length(); ++i) {
- HValue* use = to_convert->at(i);
- Representation r_to = to_convert_reps->at(i);
- InsertRepresentationChangeForUse(current, use, r_to);
- }
-
- if (current->uses()->is_empty()) {
- ASSERT(current->IsConstant());
- current->Delete();
- }
- to_convert->Rewind(0);
- to_convert_reps->Rewind(0);
+ InsertRepresentationChangeForUse(value, use_value, use_index, req);
+ }
+ if (value->HasNoUses()) {
+ ASSERT(value->IsConstant());
+ value->DeleteAndReplaceWith(NULL);
+ }
}
@@ -1886,8 +1809,8 @@
for (int i = 0; i < phi_list()->length(); i++) {
HPhi* phi = phi_list()->at(i);
if (!phi->CheckFlag(HValue::kTruncatingToInt32)) continue;
- for (int j = 0; j < phi->uses()->length(); j++) {
- HValue* use = phi->uses()->at(j);
+ for (HUseIterator it(phi->uses()); !it.Done(); it.Advance()) {
+ HValue* use = it.value();
if (!use->CheckFlag(HValue::kTruncatingToInt32)) {
phi->ClearFlag(HValue::kTruncatingToInt32);
change = true;
@@ -1897,19 +1820,17 @@
}
}
- ZoneList<HValue*> value_list(4);
- ZoneList<Representation> rep_list(4);
for (int i = 0; i < blocks_.length(); ++i) {
// Process phi instructions first.
- for (int j = 0; j < blocks_[i]->phis()->length(); j++) {
- HPhi* phi = blocks_[i]->phis()->at(j);
- InsertRepresentationChangesForValue(phi, &value_list, &rep_list);
+ const ZoneList<HPhi*>* phis = blocks_[i]->phis();
+ for (int j = 0; j < phis->length(); j++) {
+ InsertRepresentationChangesForValue(phis->at(j));
}
// Process normal instructions.
HInstruction* current = blocks_[i]->first();
while (current != NULL) {
- InsertRepresentationChangesForValue(current, &value_list, &rep_list);
+ InsertRepresentationChangesForValue(current);
current = current->next();
}
}
@@ -5943,7 +5864,7 @@
HInstruction* instruction = current->first();
while (instruction != NULL) {
int bci = 0;
- int uses = instruction->uses()->length();
+ int uses = instruction->UseCount();
trace_.Add("%d %d ", bci, uses);
instruction->PrintNameTo(&trace_);
trace_.Add(" ");
=======================================
--- /branches/bleeding_edge/src/hydrogen.h Fri Apr 8 07:30:10 2011
+++ /branches/bleeding_edge/src/hydrogen.h Wed Apr 20 03:38:08 2011
@@ -277,11 +277,10 @@
void InsertTypeConversions(HInstruction* instr);
void PropagateMinusZeroChecks(HValue* value, BitVector* visited);
void InsertRepresentationChangeForUse(HValue* value,
- HValue* use,
+ HValue* use_value,
+ int use_index,
Representation to);
- void InsertRepresentationChangesForValue(HValue* current,
- ZoneList<HValue*>* value_list,
- ZoneList<Representation>*
rep_list);
+ void InsertRepresentationChangesForValue(HValue* value);
void InferTypes(ZoneList<HValue*>* worklist);
void InitializeInferredTypes(int from_inclusive, int to_inclusive);
void CheckForBackEdge(HBasicBlock* block, HBasicBlock* successor);
=======================================
--- /branches/bleeding_edge/src/ia32/lithium-ia32.cc Wed Apr 20 02:08:26
2011
+++ /branches/bleeding_edge/src/ia32/lithium-ia32.cc Wed Apr 20 03:38:08
2011
@@ -852,24 +852,22 @@
right = UseFixed(right_value, ecx);
}
- // Shift operations can only deoptimize if we do a logical shift
- // by 0 and the result cannot be truncated to int32.
- bool can_deopt = (op == Token::SHR && constant_value == 0);
- if (can_deopt) {
- bool can_truncate = true;
- for (int i = 0; i < instr->uses()->length(); i++) {
- if (!instr->uses()->at(i)->CheckFlag(HValue::kTruncatingToInt32)) {
- can_truncate = false;
+ // Shift operations can only deoptimize if we do a logical shift by 0 and
+ // the result cannot be truncated to int32.
+ bool may_deopt = (op == Token::SHR && constant_value == 0);
+ bool does_deopt = false;
+ if (may_deopt) {
+ for (HUseIterator it(instr->uses()); !it.Done(); it.Advance()) {
+ if (!it.value()->CheckFlag(HValue::kTruncatingToInt32)) {
+ does_deopt = true;
break;
}
}
- can_deopt = !can_truncate;
}
- LShiftI* result = new LShiftI(op, left, right, can_deopt);
- return can_deopt
- ? AssignEnvironment(DefineSameAsFirst(result))
- : DefineSameAsFirst(result);
+ LInstruction* result =
+ DefineSameAsFirst(new LShiftI(op, left, right, does_deopt));
+ return does_deopt ? AssignEnvironment(result) : result;
}
=======================================
--- /branches/bleeding_edge/src/x64/lithium-x64.cc Wed Apr 20 02:08:26 2011
+++ /branches/bleeding_edge/src/x64/lithium-x64.cc Wed Apr 20 03:38:08 2011
@@ -851,24 +851,22 @@
right = UseFixed(right_value, rcx);
}
- // Shift operations can only deoptimize if we do a logical shift
- // by 0 and the result cannot be truncated to int32.
- bool can_deopt = (op == Token::SHR && constant_value == 0);
- if (can_deopt) {
- bool can_truncate = true;
- for (int i = 0; i < instr->uses()->length(); i++) {
- if (!instr->uses()->at(i)->CheckFlag(HValue::kTruncatingToInt32)) {
- can_truncate = false;
+ // Shift operations can only deoptimize if we do a logical shift by 0 and
+ // the result cannot be truncated to int32.
+ bool may_deopt = (op == Token::SHR && constant_value == 0);
+ bool does_deopt = false;
+ if (may_deopt) {
+ for (HUseIterator it(instr->uses()); !it.Done(); it.Advance()) {
+ if (!it.value()->CheckFlag(HValue::kTruncatingToInt32)) {
+ does_deopt = true;
break;
}
}
- can_deopt = !can_truncate;
}
- LShiftI* result = new LShiftI(op, left, right, can_deopt);
- return can_deopt
- ? AssignEnvironment(DefineSameAsFirst(result))
- : DefineSameAsFirst(result);
+ LInstruction* result =
+ DefineSameAsFirst(new LShiftI(op, left, right, does_deopt));
+ return does_deopt ? AssignEnvironment(result) : result;
}
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
