Merge V8 5.2.361.47 DO NOT MERGE
https://chromium.googlesource.com/v8/v8/+/5.2.361.47
FPIIM-449
Change-Id: Ibec421b85a9b88cb3a432ada642e469fe7e78346
(cherry picked from commit bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8)
diff --git a/src/compiler/escape-analysis.cc b/src/compiler/escape-analysis.cc
index b1a12b2..d11c3ab 100644
--- a/src/compiler/escape-analysis.cc
+++ b/src/compiler/escape-analysis.cc
@@ -24,7 +24,7 @@
namespace internal {
namespace compiler {
-using Alias = EscapeStatusAnalysis::Alias;
+typedef NodeId Alias;
#ifdef DEBUG
#define TRACE(...) \
@@ -35,6 +35,90 @@
#define TRACE(...)
#endif
+// EscapeStatusAnalysis determines for each allocation whether it escapes.
+class EscapeStatusAnalysis : public ZoneObject {
+ public:
+ enum Status {
+ kUnknown = 0u,
+ kTracked = 1u << 0,
+ kEscaped = 1u << 1,
+ kOnStack = 1u << 2,
+ kVisited = 1u << 3,
+ // A node is dangling, if it is a load of some kind, and does not have
+ // an effect successor.
+ kDanglingComputed = 1u << 4,
+ kDangling = 1u << 5,
+ // A node is is an effect branch point, if it has more than 2 non-dangling
+ // effect successors.
+ kBranchPointComputed = 1u << 6,
+ kBranchPoint = 1u << 7,
+ kInQueue = 1u << 8
+ };
+ typedef base::Flags<Status, uint16_t> StatusFlags;
+
+ void RunStatusAnalysis();
+
+ bool IsVirtual(Node* node);
+ bool IsEscaped(Node* node);
+ bool IsAllocation(Node* node);
+
+ bool IsInQueue(NodeId id);
+ void SetInQueue(NodeId id, bool on_stack);
+
+ void DebugPrint();
+
+ EscapeStatusAnalysis(EscapeAnalysis* object_analysis, Graph* graph,
+ Zone* zone);
+ void EnqueueForStatusAnalysis(Node* node);
+ bool SetEscaped(Node* node);
+ bool IsEffectBranchPoint(Node* node);
+ bool IsDanglingEffectNode(Node* node);
+ void ResizeStatusVector();
+ size_t GetStatusVectorSize();
+ bool IsVirtual(NodeId id);
+
+ Graph* graph() const { return graph_; }
+ void AssignAliases();
+ Alias GetAlias(NodeId id) const { return aliases_[id]; }
+ const ZoneVector<Alias>& GetAliasMap() const { return aliases_; }
+ Alias AliasCount() const { return next_free_alias_; }
+ static const Alias kNotReachable;
+ static const Alias kUntrackable;
+
+ bool IsNotReachable(Node* node);
+
+ private:
+ void Process(Node* node);
+ void ProcessAllocate(Node* node);
+ void ProcessFinishRegion(Node* node);
+ void ProcessStoreField(Node* node);
+ void ProcessStoreElement(Node* node);
+ bool CheckUsesForEscape(Node* node, bool phi_escaping = false) {
+ return CheckUsesForEscape(node, node, phi_escaping);
+ }
+ bool CheckUsesForEscape(Node* node, Node* rep, bool phi_escaping = false);
+ void RevisitUses(Node* node);
+ void RevisitInputs(Node* node);
+
+ Alias NextAlias() { return next_free_alias_++; }
+
+ bool HasEntry(Node* node);
+
+ bool IsAllocationPhi(Node* node);
+
+ ZoneVector<Node*> stack_;
+ EscapeAnalysis* object_analysis_;
+ Graph* const graph_;
+ ZoneVector<StatusFlags> status_;
+ Alias next_free_alias_;
+ ZoneVector<Node*> status_stack_;
+ ZoneVector<Alias> aliases_;
+
+ DISALLOW_COPY_AND_ASSIGN(EscapeStatusAnalysis);
+};
+
+DEFINE_OPERATORS_FOR_FLAGS(EscapeStatusAnalysis::StatusFlags)
+
const Alias EscapeStatusAnalysis::kNotReachable =
std::numeric_limits<Alias>::max();
const Alias EscapeStatusAnalysis::kUntrackable =
@@ -475,14 +559,11 @@
: stack_(zone),
object_analysis_(object_analysis),
graph_(graph),
- zone_(zone),
status_(zone),
next_free_alias_(0),
status_stack_(zone),
aliases_(zone) {}
-EscapeStatusAnalysis::~EscapeStatusAnalysis() {}
-
bool EscapeStatusAnalysis::HasEntry(Node* node) {
return status_[node->id()] & (kTracked | kEscaped);
}
@@ -712,6 +793,7 @@
}
break;
case IrOpcode::kSelect:
+ case IrOpcode::kTypeGuard:
if (SetEscaped(rep)) {
TRACE("Setting #%d (%s) to escaped because of use by #%d (%s)\n",
rep->id(), rep->op()->mnemonic(), use->id(),
@@ -721,7 +803,8 @@
break;
default:
if (use->op()->EffectInputCount() == 0 &&
- uses->op()->EffectInputCount() > 0) {
+ uses->op()->EffectInputCount() > 0 &&
+ !IrOpcode::IsJsOpcode(use->opcode())) {
TRACE("Encountered unaccounted use by #%d (%s)\n", use->id(),
use->op()->mnemonic());
UNREACHABLE();
@@ -759,8 +842,9 @@
EscapeAnalysis::EscapeAnalysis(Graph* graph, CommonOperatorBuilder* common,
Zone* zone)
- : status_analysis_(this, graph, zone),
+ : zone_(zone),
common_(common),
+ status_analysis_(new (zone) EscapeStatusAnalysis(this, graph, zone)),
virtual_states_(zone),
replacements_(zone),
cache_(nullptr) {}
@@ -769,13 +853,13 @@
void EscapeAnalysis::Run() {
replacements_.resize(graph()->NodeCount());
- status_analysis_.AssignAliases();
- if (status_analysis_.AliasCount() > 0) {
+ status_analysis_->AssignAliases();
+ if (status_analysis_->AliasCount() > 0) {
cache_ = new (zone()) MergeCache(zone());
replacements_.resize(graph()->NodeCount());
- status_analysis_.ResizeStatusVector();
+ status_analysis_->ResizeStatusVector();
RunObjectAnalysis();
- status_analysis_.RunStatusAnalysis();
+ status_analysis_->RunStatusAnalysis();
}
}
@@ -853,11 +937,11 @@
while (!queue.empty()) {
Node* node = queue.back();
queue.pop_back();
- status_analysis_.SetInQueue(node->id(), false);
+ status_analysis_->SetInQueue(node->id(), false);
if (Process(node)) {
for (Edge edge : node->use_edges()) {
Node* use = edge.from();
- if (IsNotReachable(use)) {
+ if (status_analysis_->IsNotReachable(use)) {
continue;
}
if (NodeProperties::IsEffectEdge(edge)) {
@@ -865,14 +949,14 @@
// We need DFS do avoid some duplication of VirtualStates and
// VirtualObjects, and we want to delay phis to improve performance.
if (use->opcode() == IrOpcode::kEffectPhi) {
- if (!status_analysis_.IsInQueue(use->id())) {
+ if (!status_analysis_->IsInQueue(use->id())) {
queue.push_front(use);
}
} else if ((use->opcode() != IrOpcode::kLoadField &&
use->opcode() != IrOpcode::kLoadElement) ||
- !IsDanglingEffectNode(use)) {
- if (!status_analysis_.IsInQueue(use->id())) {
- status_analysis_.SetInQueue(use->id(), true);
+ !status_analysis_->IsDanglingEffectNode(use)) {
+ if (!status_analysis_->IsInQueue(use->id())) {
+ status_analysis_->SetInQueue(use->id(), true);
queue.push_back(use);
}
} else {
@@ -1008,8 +1092,8 @@
if (!obj->AllFieldsClear()) {
obj = CopyForModificationAt(obj, state, node);
obj->ClearAllFields();
- TRACE("Cleared all fields of @%d:#%d\n", GetAlias(obj->id()),
- obj->id());
+ TRACE("Cleared all fields of @%d:#%d\n",
+ status_analysis_->GetAlias(obj->id()), obj->id());
}
}
break;
@@ -1035,7 +1119,7 @@
Node* node) {
if (obj->NeedCopyForModification()) {
state = CopyForModificationAt(state, node);
- return state->Copy(obj, GetAlias(obj->id()));
+ return state->Copy(obj, status_analysis_->GetAlias(obj->id()));
}
return obj;
}
@@ -1045,7 +1129,8 @@
#ifdef DEBUG
if (node->opcode() != IrOpcode::kLoadField &&
node->opcode() != IrOpcode::kLoadElement &&
- node->opcode() != IrOpcode::kLoad && IsDanglingEffectNode(node)) {
+ node->opcode() != IrOpcode::kLoad &&
+ status_analysis_->IsDanglingEffectNode(node)) {
PrintF("Dangeling effect node: #%d (%s)\n", node->id(),
node->op()->mnemonic());
UNREACHABLE();
@@ -1062,7 +1147,7 @@
static_cast<void*>(virtual_states_[effect->id()]),
effect->op()->mnemonic(), effect->id(), node->op()->mnemonic(),
node->id());
- if (IsEffectBranchPoint(effect) ||
+ if (status_analysis_->IsEffectBranchPoint(effect) ||
OperatorProperties::GetFrameStateInputCount(node->op()) > 0) {
virtual_states_[node->id()]->SetCopyRequired();
TRACE(", effect input %s#%d is branch point", effect->op()->mnemonic(),
@@ -1075,7 +1160,7 @@
void EscapeAnalysis::ProcessStart(Node* node) {
DCHECK_EQ(node->opcode(), IrOpcode::kStart);
virtual_states_[node->id()] =
- new (zone()) VirtualState(node, zone(), AliasCount());
+ new (zone()) VirtualState(node, zone(), status_analysis_->AliasCount());
}
bool EscapeAnalysis::ProcessEffectPhi(Node* node) {
@@ -1084,7 +1169,8 @@
VirtualState* mergeState = virtual_states_[node->id()];
if (!mergeState) {
- mergeState = new (zone()) VirtualState(node, zone(), AliasCount());
+ mergeState =
+ new (zone()) VirtualState(node, zone(), status_analysis_->AliasCount());
virtual_states_[node->id()] = mergeState;
changed = true;
TRACE("Effect Phi #%d got new virtual state %p.\n", node->id(),
@@ -1102,7 +1188,8 @@
if (state) {
cache_->states().push_back(state);
if (state == mergeState) {
- mergeState = new (zone()) VirtualState(node, zone(), AliasCount());
+ mergeState = new (zone())
+ VirtualState(node, zone(), status_analysis_->AliasCount());
virtual_states_[node->id()] = mergeState;
changed = true;
}
@@ -1122,7 +1209,7 @@
TRACE("Merge %s the node.\n", changed ? "changed" : "did not change");
if (changed) {
- status_analysis_.ResizeStatusVector();
+ status_analysis_->ResizeStatusVector();
}
return changed;
}
@@ -1131,7 +1218,7 @@
DCHECK_EQ(node->opcode(), IrOpcode::kAllocate);
ForwardVirtualState(node);
VirtualState* state = virtual_states_[node->id()];
- Alias alias = GetAlias(node->id());
+ Alias alias = status_analysis_->GetAlias(node->id());
// Check if we have already processed this node.
if (state->VirtualObjectFromAlias(alias)) {
@@ -1163,19 +1250,16 @@
Node* allocation = NodeProperties::GetValueInput(node, 0);
if (allocation->opcode() == IrOpcode::kAllocate) {
VirtualState* state = virtual_states_[node->id()];
- VirtualObject* obj = state->VirtualObjectFromAlias(GetAlias(node->id()));
+ VirtualObject* obj =
+ state->VirtualObjectFromAlias(status_analysis_->GetAlias(node->id()));
DCHECK_NOT_NULL(obj);
obj->SetInitialized();
}
}
-Node* EscapeAnalysis::replacement(NodeId id) {
- if (id >= replacements_.size()) return nullptr;
- return replacements_[id];
-}
-
Node* EscapeAnalysis::replacement(Node* node) {
- return replacement(node->id());
+ if (node->id() >= replacements_.size()) return nullptr;
+ return replacements_[node->id()];
}
bool EscapeAnalysis::SetReplacement(Node* node, Node* rep) {
@@ -1206,41 +1290,25 @@
}
Node* EscapeAnalysis::GetReplacement(Node* node) {
- return GetReplacement(node->id());
-}
-
-Node* EscapeAnalysis::GetReplacement(NodeId id) {
- Node* node = nullptr;
- while (replacement(id)) {
- node = replacement(id);
- id = node->id();
+ Node* result = nullptr;
+ while (replacement(node)) {
+ node = result = replacement(node);
}
- return node;
+ return result;
}
bool EscapeAnalysis::IsVirtual(Node* node) {
- if (node->id() >= status_analysis_.GetStatusVectorSize()) {
+ if (node->id() >= status_analysis_->GetStatusVectorSize()) {
return false;
}
- return status_analysis_.IsVirtual(node);
+ return status_analysis_->IsVirtual(node);
}
bool EscapeAnalysis::IsEscaped(Node* node) {
- if (node->id() >= status_analysis_.GetStatusVectorSize()) {
+ if (node->id() >= status_analysis_->GetStatusVectorSize()) {
return false;
}
- return status_analysis_.IsEscaped(node);
-}
-
-bool EscapeAnalysis::SetEscaped(Node* node) {
- return status_analysis_.SetEscaped(node);
-}
-
-VirtualObject* EscapeAnalysis::GetVirtualObject(Node* at, NodeId id) {
- if (VirtualState* states = virtual_states_[at->id()]) {
- return states->VirtualObjectFromAlias(GetAlias(id));
- }
- return nullptr;
+ return status_analysis_->IsEscaped(node);
}
bool EscapeAnalysis::CompareVirtualObjects(Node* left, Node* right) {
@@ -1269,7 +1337,7 @@
}
cache_->LoadVirtualObjectsForFieldsFrom(state,
- status_analysis_.GetAliasMap());
+ status_analysis_->GetAliasMap());
if (cache_->objects().size() == cache_->fields().size()) {
cache_->GetFields(offset);
if (cache_->fields().size() == cache_->objects().size()) {
@@ -1280,7 +1348,7 @@
Node* phi = graph()->NewNode(
common()->Phi(MachineRepresentation::kTagged, value_input_count),
value_input_count + 1, &cache_->fields().front());
- status_analysis_.ResizeStatusVector();
+ status_analysis_->ResizeStatusVector();
SetReplacement(load, phi);
TRACE(" got phi created.\n");
} else {
@@ -1360,7 +1428,7 @@
}
} else {
// We have a load from a non-const index, cannot eliminate object.
- if (SetEscaped(from)) {
+ if (status_analysis_->SetEscaped(from)) {
TRACE(
"Setting #%d (%s) to escaped because load element #%d from non-const "
"index #%d (%s)\n",
@@ -1415,7 +1483,7 @@
}
} else {
// We have a store to a non-const index, cannot eliminate object.
- if (SetEscaped(to)) {
+ if (status_analysis_->SetEscaped(to)) {
TRACE(
"Setting #%d (%s) to escaped because store element #%d to non-const "
"index #%d (%s)\n",
@@ -1426,8 +1494,8 @@
if (!obj->AllFieldsClear()) {
obj = CopyForModificationAt(obj, state, node);
obj->ClearAllFields();
- TRACE("Cleared all fields of @%d:#%d\n", GetAlias(obj->id()),
- obj->id());
+ TRACE("Cleared all fields of @%d:#%d\n",
+ status_analysis_->GetAlias(obj->id()), obj->id());
}
}
}
@@ -1475,21 +1543,17 @@
return nullptr;
}
-void EscapeAnalysis::DebugPrintObject(VirtualObject* object, Alias alias) {
- PrintF(" Alias @%d: Object #%d with %zu fields\n", alias, object->id(),
- object->field_count());
- for (size_t i = 0; i < object->field_count(); ++i) {
- if (Node* f = object->GetField(i)) {
- PrintF(" Field %zu = #%d (%s)\n", i, f->id(), f->op()->mnemonic());
- }
- }
-}
-
void EscapeAnalysis::DebugPrintState(VirtualState* state) {
PrintF("Dumping virtual state %p\n", static_cast<void*>(state));
- for (Alias alias = 0; alias < AliasCount(); ++alias) {
+ for (Alias alias = 0; alias < status_analysis_->AliasCount(); ++alias) {
if (VirtualObject* object = state->VirtualObjectFromAlias(alias)) {
- DebugPrintObject(object, alias);
+ PrintF(" Alias @%d: Object #%d with %zu fields\n", alias, object->id(),
+ object->field_count());
+ for (size_t i = 0; i < object->field_count(); ++i) {
+ if (Node* f = object->GetField(i)) {
+ PrintF(" Field %zu = #%d (%s)\n", i, f->id(), f->op()->mnemonic());
+ }
+ }
}
}
}
@@ -1511,17 +1575,17 @@
VirtualObject* EscapeAnalysis::GetVirtualObject(VirtualState* state,
Node* node) {
- if (node->id() >= status_analysis_.GetAliasMap().size()) return nullptr;
- Alias alias = GetAlias(node->id());
+ if (node->id() >= status_analysis_->GetAliasMap().size()) return nullptr;
+ Alias alias = status_analysis_->GetAlias(node->id());
if (alias >= state->size()) return nullptr;
return state->VirtualObjectFromAlias(alias);
}
bool EscapeAnalysis::ExistsVirtualAllocate() {
- for (size_t id = 0; id < status_analysis_.GetAliasMap().size(); ++id) {
- Alias alias = GetAlias(static_cast<NodeId>(id));
+ for (size_t id = 0; id < status_analysis_->GetAliasMap().size(); ++id) {
+ Alias alias = status_analysis_->GetAlias(static_cast<NodeId>(id));
if (alias < EscapeStatusAnalysis::kUntrackable) {
- if (status_analysis_.IsVirtual(static_cast<int>(id))) {
+ if (status_analysis_->IsVirtual(static_cast<int>(id))) {
return true;
}
}
@@ -1529,6 +1593,8 @@
return false;
}
+Graph* EscapeAnalysis::graph() const { return status_analysis_->graph(); }
+
} // namespace compiler
} // namespace internal
} // namespace v8