src/share/vm/c1/c1_LinearScan.cpp

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

@@ -1,7 +1,7 @@
 /*
- * Copyright (c) 2005, 2014, Oracle and/or its affiliates. All rights reserved.
+ * 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,46 +1431,92 @@
     }
   }
 }
 
 #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++;
     }
   }
 
-  // check in both directions if sorted list and unsorted list contain same intervals
+  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) {
-      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(binary_search(intervals, interval_at(i)),
+          "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) {