Reviewers: Yang, Kasper Lund, danno,
Message:
@yangguo , @kasper, please review it, thanks!
Description:
optimize Deoptimizer::GetOutputInfo to binary search
BUG=
Please review this at https://codereview.chromium.org/334713011/
SVN Base: https://github.com/v8/v8.git@master
Affected files (+21, -7 lines):
M src/deoptimizer.cc
M src/full-codegen.h
M src/full-codegen.cc
M src/utils.h
Index: src/deoptimizer.cc
diff --git a/src/deoptimizer.cc b/src/deoptimizer.cc
index
2b39ff6965e89a1290c03d1af0ea33c20c2c963a..a793931d76e5f94f836179959dd164154186514a
100644
--- a/src/deoptimizer.cc
+++ b/src/deoptimizer.cc
@@ -690,14 +690,17 @@ int Deoptimizer::GetDeoptimizationId(Isolate* isolate,
int Deoptimizer::GetOutputInfo(DeoptimizationOutputData* data,
BailoutId id,
SharedFunctionInfo* shared) {
- // TODO(kasperl): For now, we do a simple linear search for the PC
- // offset associated with the given node id. This should probably be
- // changed to a binary search.
int length = data->DeoptPoints();
- for (int i = 0; i < length; i++) {
- if (data->AstId(i) == id) {
- return data->PcAndState(i)->value();
- }
+ int low = 0, high = length - 1, mid;
+ while (low <= high) {
+ mid = low + (high - low) / 2;
+ if (id == data->AstId(mid)) {
+ return data->PcAndState(mid)->value();
+ } else if (id < data->AstId(mid)) {
+ high = mid - 1;
+ } else {
+ low = mid + 1;
+ }
}
PrintF(stderr, "[couldn't find pc offset for node=%d]\n", id.ToInt());
PrintF(stderr, "[method: %s]\n", shared->DebugName()->ToCString().get());
Index: src/full-codegen.cc
diff --git a/src/full-codegen.cc b/src/full-codegen.cc
index
088a9c9a7ed1409ba31667608a3ecdd8b1e8f6a2..f28d1ceed32efe950276c21ecd949384ad0942b3
100644
--- a/src/full-codegen.cc
+++ b/src/full-codegen.cc
@@ -377,6 +377,7 @@ void
FullCodeGenerator::PopulateDeoptimizationData(Handle<Code> code) {
int length = bailout_entries_.length();
Handle<DeoptimizationOutputData> data =
DeoptimizationOutputData::New(isolate(), length, TENURED);
+ bailout_entries_.Sort(&BailoutEntry::CompareBailoutId);
for (int i = 0; i < length; i++) {
data->SetAstId(i, bailout_entries_[i].id);
data->SetPcAndState(i, Smi::FromInt(bailout_entries_[i].pc_and_state));
Index: src/full-codegen.h
diff --git a/src/full-codegen.h b/src/full-codegen.h
index
cede9acaddf1c13a46b359b37c55893ab54f2038..5b86615ba3b5213e1600581ba95a48d173c83200
100644
--- a/src/full-codegen.h
+++ b/src/full-codegen.h
@@ -625,6 +625,15 @@ class FullCodeGenerator: public AstVisitor {
struct BailoutEntry {
BailoutId id;
unsigned pc_and_state;
+ static int CompareBailoutId(const BailoutEntry* a, const BailoutEntry*
b) {
+ if (a->id == b->id) {
+ return 0;
+ } else if (a->id < b->id) {
+ return -1;
+ } else {
+ return +1;
+ }
+ }
};
struct BackEdgeEntry {
Index: src/utils.h
diff --git a/src/utils.h b/src/utils.h
index
da5d0fcab88587b2f2437948b5929efba8480b10..c9794e1d86f8d10440aa2b3daa78d6c6587d66c9
100644
--- a/src/utils.h
+++ b/src/utils.h
@@ -1094,6 +1094,7 @@ class BailoutId {
bool IsNone() const { return id_ == kNoneId; }
bool operator==(const BailoutId& other) const { return id_ == other.id_;
}
bool operator!=(const BailoutId& other) const { return id_ != other.id_;
}
+ bool operator<(const BailoutId& other) const { return id_ < other.id_; }
private:
static const int kNoneId = -1;
--
--
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.
