< prev index next >

src/share/vm/c1/c1_LinearScan.cpp

Print this page
rev 7921 : 8067014: LinearScan::is_sorted significantly slows down fastdebug builds' performance
Reviewed-by:

*** 1,7 **** /* ! * Copyright (c) 2005, 2014, 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. --- 1,7 ---- /* ! * Copyright (c) 2005, 2015, 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.
*** 1431,1476 **** } } } #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, ""); return false; } from = it->from(); } } ! // 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++; ! } ! } ! assert(num_found == 1, "lists do not contain same intervals"); ! } ! } ! 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(num_found == 1, "lists do not contain same intervals"); } return true; } #endif void LinearScan::add_to_list(Interval** first, Interval** prev, Interval* interval) { --- 1431,1522 ---- } } } #ifndef PRODUCT + bool binary_search(IntervalArray* intervals, Interval* interval) { + int begin = 0; + int end = intervals->length(); + + while (end - begin > 0) { + int idx = begin + (end - begin) / 2; + + if (intervals->at(idx) == interval) { + return true; + } + + int cmp = interval->from() - intervals->at(idx)->from(); + if (cmp < 0) { + end = idx; + continue; + } else if (cmp > 0) { + begin = idx + 1; + continue; + } + + // We found an interval that is defined in the same place as + // an interval that we were looking for. Let's try to find it + // somewhere around. + for (int i = idx - 1; i >= 0; i--) { + if (intervals->at(i) == interval) { + return true; + } + if (intervals->at(i)->from() != interval->from()) { + break; + } + } + + for (int i = idx + 1; i < intervals->length(); i++) { + if (intervals->at(i) == interval) { + return true; + } + if (intervals->at(i)->from() != interval->from()) { + break; + } + } + // We didn't find the interval in intervals that share + // the same def point with it, so it's time to bailout. + return false; + } + return false; + } + bool LinearScan::is_sorted(IntervalArray* intervals) { int from = -1; int i, j; + + int null_count = 0; for (i = 0; i < intervals->length(); i ++) { Interval* it = intervals->at(i); if (it != NULL) { if (from > it->from()) { assert(false, ""); return false; } from = it->from(); + } else { + null_count++; } } ! assert(null_count == 0, "Sorted intervals should not contain nulls"); ! ! null_count = 0; ! // check that sorted list contains all non-NULL intervals from unsorted list for (i = 0; i < interval_count(); i++) { if (interval_at(i) != NULL) { ! assert(binary_search(intervals, interval_at(i)), ! "lists do not contain same intervals"); ! } else { ! null_count++; } } + 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) {
< prev index next >