Revision: 21593
Author: [email protected]
Date: Mon Jun 2 08:51:25 2014 UTC
Log: Handle HCheckInstanceType and HIsStringAndBranch in check
elimination.
[email protected]
Review URL: https://codereview.chromium.org/300423003
http://code.google.com/p/v8/source/detail?r=21593
Modified:
/branches/bleeding_edge/src/hydrogen-check-elimination.cc
/branches/bleeding_edge/src/hydrogen-check-elimination.h
/branches/bleeding_edge/src/hydrogen-instructions.cc
/branches/bleeding_edge/src/hydrogen-instructions.h
/branches/bleeding_edge/src/unique.h
=======================================
--- /branches/bleeding_edge/src/hydrogen-check-elimination.cc Tue May 27
07:57:22 2014 UTC
+++ /branches/bleeding_edge/src/hydrogen-check-elimination.cc Mon Jun 2
08:51:25 2014 UTC
@@ -104,6 +104,10 @@
ReduceCompareObjectEqAndBranch(HCompareObjectEqAndBranch::cast(instr));
break;
}
+ case HValue::kIsStringAndBranch: {
+ ReduceIsStringAndBranch(HIsStringAndBranch::cast(instr));
+ break;
+ }
case HValue::kTransitionElementsKind: {
ReduceTransitionElementsKind(
HTransitionElementsKind::cast(instr));
@@ -113,6 +117,10 @@
ReduceCheckHeapObject(HCheckHeapObject::cast(instr));
break;
}
+ case HValue::kCheckInstanceType: {
+ ReduceCheckInstanceType(HCheckInstanceType::cast(instr));
+ break;
+ }
default: {
// If the instruction changes maps uncontrollably, drop everything.
if (instr->CheckChangesFlag(kOsrEntries)) {
@@ -125,7 +133,7 @@
}
}
// Improvements possible:
- // - eliminate redundant HCheckSmi, HCheckInstanceType instructions
+ // - eliminate redundant HCheckSmi instructions
// - track which values have been HCheckHeapObject'd
}
@@ -261,6 +269,28 @@
ASSERT_NE(HCheckTableEntry::UNCHECKED_STABLE, re->state_);
}
learned = true;
+ } else if (end->IsIsStringAndBranch()) {
+ HIsStringAndBranch* cmp = HIsStringAndBranch::cast(end);
+ HValue* object = cmp->value()->ActualValue();
+ HCheckTableEntry* entry = copy->Find(object);
+ if (is_true_branch) {
+ // Learn on the true branch of if(IsString(x)).
+ if (entry == NULL) {
+ copy->Insert(object, NULL, string_maps(),
+ HCheckTableEntry::CHECKED);
+ } else {
+ EnsureChecked(entry, object, cmp);
+ entry->maps_ = entry->maps_->Intersect(string_maps(), zone);
+ ASSERT_NE(HCheckTableEntry::UNCHECKED_STABLE, entry->state_);
+ }
+ } else {
+ // Learn on the false branch of if(IsString(x)).
+ if (entry != NULL) {
+ EnsureChecked(entry, object, cmp);
+ entry->maps_ = entry->maps_->Subtract(string_maps(), zone);
+ ASSERT_NE(HCheckTableEntry::UNCHECKED_STABLE, entry->state_);
+ }
+ }
}
// Learning on false branches requires storing negative facts.
}
@@ -414,6 +444,50 @@
Insert(object, check, instr->maps(), state);
}
}
+
+ void ReduceCheckInstanceType(HCheckInstanceType* instr) {
+ HValue* value = instr->value()->ActualValue();
+ HCheckTableEntry* entry = Find(value);
+ if (entry == NULL) {
+ if (instr->check() == HCheckInstanceType::IS_STRING) {
+ Insert(value, NULL, string_maps(), HCheckTableEntry::CHECKED);
+ }
+ return;
+ }
+ UniqueSet<Map>* maps = new(zone()) UniqueSet<Map>(
+ entry->maps_->size(), zone());
+ for (int i = 0; i < entry->maps_->size(); ++i) {
+ InstanceType type;
+ Unique<Map> map = entry->maps_->at(i);
+ {
+ // This is safe, because maps don't move and their instance type
does
+ // not change.
+ AllowHandleDereference allow_deref;
+ type = map.handle()->instance_type();
+ }
+ if (instr->is_interval_check()) {
+ InstanceType first_type, last_type;
+ instr->GetCheckInterval(&first_type, &last_type);
+ if (first_type <= type && type <= last_type) maps->Add(map,
zone());
+ } else {
+ uint8_t mask, tag;
+ instr->GetCheckMaskAndTag(&mask, &tag);
+ if ((type & mask) == tag) maps->Add(map, zone());
+ }
+ }
+ if (maps->size() == entry->maps_->size()) {
+ TRACE(("Removing redundant CheckInstanceType #%d at B%d\n",
+ instr->id(), instr->block()->block_id()));
+ EnsureChecked(entry, value, instr);
+ instr->DeleteAndReplaceWith(value);
+ INC_STAT(removed_cit_);
+ } else if (maps->size() != 0) {
+ entry->maps_ = maps;
+ if (entry->state_ == HCheckTableEntry::UNCHECKED_STABLE) {
+ entry->state_ = HCheckTableEntry::CHECKED_STABLE;
+ }
+ }
+ }
void ReduceLoadNamedField(HLoadNamedField* instr) {
// Reduce a load of the map field when it is known to be a constant.
@@ -527,6 +601,28 @@
int unreachable_succ = 1 - succ;
instr->block()->MarkSuccEdgeUnreachable(unreachable_succ);
}
+
+ void ReduceIsStringAndBranch(HIsStringAndBranch* instr) {
+ HValue* value = instr->value()->ActualValue();
+ HCheckTableEntry* entry = Find(value);
+ if (entry == NULL) return;
+ EnsureChecked(entry, value, instr);
+ int succ;
+ if (entry->maps_->IsSubset(string_maps())) {
+ TRACE(("Marking redundant IsStringAndBranch #%d at B%d as true\n",
+ instr->id(), instr->block()->block_id()));
+ succ = 0;
+ } else {
+ MapSet intersection = entry->maps_->Intersect(string_maps(), zone());
+ if (intersection->size() > 0) return;
+ TRACE(("Marking redundant IsStringAndBranch #%d at B%d as false\n",
+ instr->id(), instr->block()->block_id()));
+ succ = 1;
+ }
+ instr->set_known_successor_index(succ);
+ int unreachable_succ = 1 - succ;
+ instr->block()->MarkSuccEdgeUnreachable(unreachable_succ);
+ }
void ReduceTransitionElementsKind(HTransitionElementsKind* instr) {
HValue* object = instr->object()->ActualValue();
@@ -688,6 +784,7 @@
}
Zone* zone() const { return phase_->zone(); }
+ MapSet string_maps() const { return phase_->string_maps(); }
friend class HCheckMapsEffects;
friend class HCheckEliminationPhase;
@@ -794,6 +891,7 @@
PRINT_STAT(redundant);
PRINT_STAT(removed);
PRINT_STAT(removed_cho);
+ PRINT_STAT(removed_cit);
PRINT_STAT(narrowed);
PRINT_STAT(loads);
PRINT_STAT(empty);
=======================================
--- /branches/bleeding_edge/src/hydrogen-check-elimination.h Tue Apr 29
06:42:26 2014 UTC
+++ /branches/bleeding_edge/src/hydrogen-check-elimination.h Mon Jun 2
08:51:25 2014 UTC
@@ -16,11 +16,20 @@
class HCheckEliminationPhase : public HPhase {
public:
explicit HCheckEliminationPhase(HGraph* graph)
- : HPhase("H_Check Elimination", graph), aliasing_() {
+ : HPhase("H_Check Elimination", graph), aliasing_(),
+ string_maps_(kStringMapsSize, zone()) {
+ // Compute the set of string maps.
+ #define ADD_STRING_MAP(type, size, name, Name) \
+ string_maps_.Add(Unique<Map>::CreateImmovable( \
+ graph->isolate()->factory()->name##_map()), zone());
+ STRING_TYPE_LIST(ADD_STRING_MAP)
+ #undef ADD_STRING_MAP
+ ASSERT_EQ(kStringMapsSize, string_maps_.size());
#ifdef DEBUG
redundant_ = 0;
removed_ = 0;
removed_cho_ = 0;
+ removed_cit_ = 0;
narrowed_ = 0;
loads_ = 0;
empty_ = 0;
@@ -35,13 +44,20 @@
friend class HCheckTable;
private:
+ const UniqueSet<Map>* string_maps() const { return &string_maps_; }
+
void PrintStats();
HAliasAnalyzer* aliasing_;
+ #define COUNT(type, size, name, Name) + 1
+ static const int kStringMapsSize = 0 STRING_TYPE_LIST(COUNT);
+ #undef COUNT
+ UniqueSet<Map> string_maps_;
#ifdef DEBUG
int redundant_;
int removed_;
int removed_cho_;
+ int removed_cit_;
int narrowed_;
int loads_;
int empty_;
=======================================
--- /branches/bleeding_edge/src/hydrogen-instructions.cc Mon Jun 2
07:02:24 2014 UTC
+++ /branches/bleeding_edge/src/hydrogen-instructions.cc Mon Jun 2
08:51:25 2014 UTC
@@ -3256,11 +3256,27 @@
bool HIsStringAndBranch::KnownSuccessorBlock(HBasicBlock** block) {
+ if (known_successor_index() != kNoKnownSuccessorIndex) {
+ *block = SuccessorAt(known_successor_index());
+ return true;
+ }
if (FLAG_fold_constants && value()->IsConstant()) {
*block = HConstant::cast(value())->HasStringValue()
? FirstSuccessor() : SecondSuccessor();
return true;
}
+ if (value()->type().IsString()) {
+ *block = FirstSuccessor();
+ return true;
+ }
+ if (value()->type().IsSmi() ||
+ value()->type().IsNull() ||
+ value()->type().IsBoolean() ||
+ value()->type().IsUndefined() ||
+ value()->type().IsJSObject()) {
+ *block = SecondSuccessor();
+ return true;
+ }
*block = NULL;
return false;
}
=======================================
--- /branches/bleeding_edge/src/hydrogen-instructions.h Mon Jun 2 07:02:24
2014 UTC
+++ /branches/bleeding_edge/src/hydrogen-instructions.h Mon Jun 2 08:51:25
2014 UTC
@@ -2908,6 +2908,8 @@
bool is_interval_check() const { return check_ <= LAST_INTERVAL_CHECK; }
void GetCheckInterval(InstanceType* first, InstanceType* last);
void GetCheckMaskAndTag(uint8_t* mask, uint8_t* tag);
+
+ Check check() const { return check_; }
DECLARE_CONCRETE_INSTRUCTION(CheckInstanceType)
@@ -4424,6 +4426,12 @@
}
virtual bool KnownSuccessorBlock(HBasicBlock** block) V8_OVERRIDE;
+
+ static const int kNoKnownSuccessorIndex = -1;
+ int known_successor_index() const { return known_successor_index_; }
+ void set_known_successor_index(int known_successor_index) {
+ known_successor_index_ = known_successor_index;
+ }
DECLARE_CONCRETE_INSTRUCTION(IsStringAndBranch)
@@ -4434,7 +4442,10 @@
HIsStringAndBranch(HValue* value,
HBasicBlock* true_target = NULL,
HBasicBlock* false_target = NULL)
- : HUnaryControlInstruction(value, true_target, false_target) {}
+ : HUnaryControlInstruction(value, true_target, false_target),
+ known_successor_index_(kNoKnownSuccessorIndex) { }
+
+ int known_successor_index_;
};
=======================================
--- /branches/bleeding_edge/src/unique.h Mon May 5 06:53:19 2014 UTC
+++ /branches/bleeding_edge/src/unique.h Mon Jun 2 08:51:25 2014 UTC
@@ -274,6 +274,25 @@
out->size_ = k;
return out;
}
+
+ // Returns a new set representing all elements from this set which are
not in
+ // that set. O(|this| * |that|).
+ UniqueSet<T>* Subtract(const UniqueSet<T>* that, Zone* zone) const {
+ if (that->size_ == 0) return this->Copy(zone);
+
+ UniqueSet<T>* out = new(zone) UniqueSet<T>(this->size_, zone);
+
+ int i = 0, j = 0;
+ while (i < this->size_) {
+ Unique<T> cand = this->array_[i];
+ if (!that->Contains(cand)) {
+ out->array_[j++] = cand;
+ }
+ }
+
+ out->size_ = j;
+ return out;
+ }
// Makes an exact copy of this set. O(|this|).
UniqueSet<T>* Copy(Zone* zone) const {
--
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
---
You received this message because you are subscribed to the Google Groups "v8-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
For more options, visit https://groups.google.com/d/optout.
