< prev index next >
hotspot/src/share/vm/c1/c1_LinearScan.cpp
Print this page
rev 10235 : 8067014: LinearScan::is_sorted significantly slows down fastdebug builds' performance
Reviewed-by: vlivanov
@@ -1,7 +1,7 @@
/*
- * Copyright (c) 2005, 2015, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 2005, 2016, Oracle and/or its affiliates. All rights reserved.
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* This code is free software; you can redistribute it and/or modify it
* under the terms of the GNU General Public License version 2 only, as
* published by the Free Software Foundation.
@@ -1432,46 +1432,78 @@
}
}
}
#ifndef PRODUCT
-bool LinearScan::is_sorted(IntervalArray* intervals) {
- int from = -1;
- int i, j;
- for (i = 0; i < intervals->length(); i ++) {
- Interval* it = intervals->at(i);
- if (it != NULL) {
- if (from > it->from()) {
- assert(false, "");
+int interval_cmp(Interval* const& l, Interval* const& r) {
+ return l->from() - r->from();
+}
+
+bool find_interval(Interval* interval, IntervalArray* intervals) {
+ bool found;
+ int idx = intervals->find_sorted<Interval*, interval_cmp>(interval, found);
+
+ if (!found) {
return false;
}
- from = it->from();
+
+ int from = interval->from();
+
+ // The index we've found using binary search is pointing to an interval
+ // that is defined in the same place as the interval we were looking for.
+ // So now we have to look around that index and find exact interval.
+ for (int i = idx; i >= 0; i--) {
+ if (intervals->at(i) == interval) {
+ return true;
+ }
+ if (intervals->at(i)->from() != from) {
+ break;
}
}
- // check in both directions if sorted list and unsorted list contain same intervals
- for (i = 0; i < interval_count(); i++) {
- if (interval_at(i) != NULL) {
- int num_found = 0;
- for (j = 0; j < intervals->length(); j++) {
- if (interval_at(i) == intervals->at(j)) {
- num_found++;
+ for (int i = idx + 1; i < intervals->length(); i++) {
+ if (intervals->at(i) == interval) {
+ return true;
}
+ if (intervals->at(i)->from() != from) {
+ break;
}
- assert(num_found == 1, "lists do not contain same intervals");
}
+
+ return false;
+}
+
+bool LinearScan::is_sorted(IntervalArray* intervals) {
+ int from = -1;
+ int null_count = 0;
+
+ for (int i = 0; i < intervals->length(); i++) {
+ Interval* it = intervals->at(i);
+ if (it != NULL) {
+ assert(from <= it->from(), "Intervals are unordered");
+ from = it->from();
+ } else {
+ null_count++;
}
- for (j = 0; j < intervals->length(); j++) {
- int num_found = 0;
- for (i = 0; i < interval_count(); i++) {
- if (interval_at(i) == intervals->at(j)) {
- num_found++;
}
+
+ assert(null_count == 0, "Sorted intervals should not contain nulls");
+
+ null_count = 0;
+
+ for (int i = 0; i < interval_count(); i++) {
+ Interval* interval = interval_at(i);
+ if (interval != NULL) {
+ assert(find_interval(interval, intervals), "Lists do not contain same intervals");
+ } else {
+ null_count++;
}
- assert(num_found == 1, "lists do not contain same intervals");
}
+ assert(interval_count() - null_count == intervals->length(),
+ "Sorted list should contain the same amount of non-NULL intervals as unsorted list");
+
return true;
}
#endif
void LinearScan::add_to_list(Interval** first, Interval** prev, Interval* interval) {
@@ -1534,11 +1566,11 @@
for (unsorted_idx = 0; unsorted_idx < unsorted_len; unsorted_idx++) {
if (unsorted_list->at(unsorted_idx) != NULL) {
sorted_len++;
}
}
- IntervalArray* sorted_list = new IntervalArray(sorted_len);
+ IntervalArray* sorted_list = new IntervalArray(sorted_len, sorted_len, NULL);
// special sorting algorithm: the original interval-list is almost sorted,
// only some intervals are swapped. So this is much faster than a complete QuickSort
for (unsorted_idx = 0; unsorted_idx < unsorted_len; unsorted_idx++) {
Interval* cur_interval = unsorted_list->at(unsorted_idx);
@@ -1587,11 +1619,12 @@
// conventional sort-algorithm for new intervals
new_list->sort(interval_cmp);
// merge old and new list (both already sorted) into one combined list
- IntervalArray* combined_list = new IntervalArray(old_len + new_len);
+ int combined_list_len = old_len + new_len;
+ IntervalArray* combined_list = new IntervalArray(combined_list_len, combined_list_len, NULL);
int old_idx = 0;
int new_idx = 0;
while (old_idx + new_idx < old_len + new_len) {
if (new_idx >= new_len || (old_idx < old_len && old_list->at(old_idx)->from() <= new_list->at(new_idx)->from())) {
@@ -3209,10 +3242,14 @@
if (!is_processed_reg_num(i1->assigned_reg())) {
tty->print_cr("Can not have an Interval for an ignored register"); i1->print(); tty->cr();
has_error = true;
}
+ // special intervals that are created in MoveResolver
+ // -> ignore them because the range information has no meaning there
+ if (i1->from() == 1 && i1->to() == 2) continue;
+
if (i1->first() == Range::end()) {
tty->print_cr("Interval %d has no Range", i1->reg_num()); i1->print(); tty->cr();
has_error = true;
}
@@ -3223,22 +3260,17 @@
}
}
for (int j = i + 1; j < len; j++) {
Interval* i2 = interval_at(j);
- if (i2 == NULL) continue;
-
- // special intervals that are created in MoveResolver
- // -> ignore them because the range information has no meaning there
- if (i1->from() == 1 && i1->to() == 2) continue;
- if (i2->from() == 1 && i2->to() == 2) continue;
+ if (i2 == NULL || (i2->from() == 1 && i2->to() == 2)) continue;
int r1 = i1->assigned_reg();
int r1Hi = i1->assigned_regHi();
int r2 = i2->assigned_reg();
int r2Hi = i2->assigned_regHi();
- if (i1->intersects(i2) && (r1 == r2 || r1 == r2Hi || (r1Hi != any_reg && (r1Hi == r2 || r1Hi == r2Hi)))) {
+ if ((r1 == r2 || r1 == r2Hi || (r1Hi != any_reg && (r1Hi == r2 || r1Hi == r2Hi))) && i1->intersects(i2)) {
tty->print_cr("Intervals %d and %d overlap and have the same register assigned", i1->reg_num(), i2->reg_num());
i1->print(); tty->cr();
i2->print(); tty->cr();
has_error = true;
}
@@ -3427,11 +3459,12 @@
}
void RegisterVerifier::verify(BlockBegin* start) {
// setup input registers (method arguments) for first block
- IntervalList* input_state = new IntervalList(state_size(), NULL);
+ int input_state_len = state_size();
+ IntervalList* input_state = new IntervalList(input_state_len, input_state_len, NULL);
CallingConvention* args = compilation()->frame_map()->incoming_arguments();
for (int n = 0; n < args->length(); n++) {
LIR_Opr opr = args->at(n);
if (opr->is_register()) {
Interval* interval = interval_at(reg_num(opr));
@@ -3541,11 +3574,11 @@
}
IntervalList* RegisterVerifier::copy(IntervalList* input_state) {
IntervalList* copy_state = new IntervalList(input_state->length());
- copy_state->push_all(input_state);
+ copy_state->appendAll(input_state);
return copy_state;
}
void RegisterVerifier::state_put(IntervalList* input_state, int reg, Interval* interval) {
if (reg != LinearScan::any_reg && reg < state_size()) {
@@ -5504,11 +5537,11 @@
if (regHi != any_reg) {
IntervalList* processed = _spill_intervals[reg];
for (int i = 0; i < _spill_intervals[regHi]->length(); i++) {
Interval* it = _spill_intervals[regHi]->at(i);
- if (processed->index_of(it) == -1) {
+ if (processed->find_from_end(it) == -1) {
remove_from_list(it);
split_and_spill_interval(it);
}
}
}
< prev index next >