< 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 /*
   2  * Copyright (c) 2005, 2014, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.
   8  *
   9  * This code is distributed in the hope that it will be useful, but WITHOUT
  10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12  * version 2 for more details (a copy is included in the LICENSE file that
  13  * accompanied this code).
  14  *
  15  * You should have received a copy of the GNU General Public License version
  16  * 2 along with this work; if not, write to the Free Software Foundation,
  17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  18  *
  19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  20  * or visit www.oracle.com if you need additional information or have any
  21  * questions.
  22  *


1416 
1417 // ********** Phase 5: actual register allocation
1418 
1419 int LinearScan::interval_cmp(Interval** a, Interval** b) {
1420   if (*a != NULL) {
1421     if (*b != NULL) {
1422       return (*a)->from() - (*b)->from();
1423     } else {
1424       return -1;
1425     }
1426   } else {
1427     if (*b != NULL) {
1428       return 1;
1429     } else {
1430       return 0;
1431     }
1432   }
1433 }
1434 
1435 #ifndef PRODUCT















































1436 bool LinearScan::is_sorted(IntervalArray* intervals) {
1437   int from = -1;
1438   int i, j;


1439   for (i = 0; i < intervals->length(); i ++) {
1440     Interval* it = intervals->at(i);
1441     if (it != NULL) {
1442       if (from > it->from()) {
1443         assert(false, "");
1444         return false;
1445       }
1446       from = it->from();


1447     }
1448   }
1449 
1450   // check in both directions if sorted list and unsorted list contain same intervals



1451   for (i = 0; i < interval_count(); i++) {
1452     if (interval_at(i) != NULL) {
1453       int num_found = 0;
1454       for (j = 0; j < intervals->length(); j++) {
1455         if (interval_at(i) == intervals->at(j)) {
1456           num_found++;
1457         }
1458       }
1459       assert(num_found == 1, "lists do not contain same intervals");
1460     }
1461   }
1462   for (j = 0; j < intervals->length(); j++) {
1463     int num_found = 0;
1464     for (i = 0; i < interval_count(); i++) {
1465       if (interval_at(i) == intervals->at(j)) {
1466         num_found++;
1467       }
1468     }
1469     assert(num_found == 1, "lists do not contain same intervals");
1470   }




1471 
1472   return true;
1473 }
1474 #endif
1475 
1476 void LinearScan::add_to_list(Interval** first, Interval** prev, Interval* interval) {
1477   if (*prev != NULL) {
1478     (*prev)->set_next(interval);
1479   } else {
1480     *first = interval;
1481   }
1482   *prev = interval;
1483 }
1484 
1485 void LinearScan::create_unhandled_lists(Interval** list1, Interval** list2, bool (is_list1)(const Interval* i), bool (is_list2)(const Interval* i)) {
1486   assert(is_sorted(_sorted_intervals), "interval list is not sorted");
1487 
1488   *list1 = *list2 = Interval::end();
1489 
1490   Interval* list1_prev = NULL;


   1 /*
   2  * Copyright (c) 2005, 2015, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.
   8  *
   9  * This code is distributed in the hope that it will be useful, but WITHOUT
  10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12  * version 2 for more details (a copy is included in the LICENSE file that
  13  * accompanied this code).
  14  *
  15  * You should have received a copy of the GNU General Public License version
  16  * 2 along with this work; if not, write to the Free Software Foundation,
  17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  18  *
  19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  20  * or visit www.oracle.com if you need additional information or have any
  21  * questions.
  22  *


1416 
1417 // ********** Phase 5: actual register allocation
1418 
1419 int LinearScan::interval_cmp(Interval** a, Interval** b) {
1420   if (*a != NULL) {
1421     if (*b != NULL) {
1422       return (*a)->from() - (*b)->from();
1423     } else {
1424       return -1;
1425     }
1426   } else {
1427     if (*b != NULL) {
1428       return 1;
1429     } else {
1430       return 0;
1431     }
1432   }
1433 }
1434 
1435 #ifndef PRODUCT
1436 bool binary_search(IntervalArray* intervals, Interval* interval) {
1437   int begin = 0;
1438   int end = intervals->length();
1439 
1440   while (end - begin > 0) {
1441     int idx = begin + (end - begin) / 2;
1442 
1443     if (intervals->at(idx) == interval) {
1444       return true;
1445     }
1446 
1447     int cmp = interval->from() - intervals->at(idx)->from();
1448     if (cmp < 0) {
1449       end = idx;
1450       continue;
1451     } else if (cmp > 0) {
1452       begin = idx + 1;
1453       continue;
1454     }
1455 
1456     // We found an interval that is defined in the same place as
1457     // an interval that we were looking for. Let's try to find it
1458     // somewhere around.
1459     for (int i = idx - 1; i >= 0; i--) {
1460       if (intervals->at(i) == interval) {
1461         return true;
1462       }
1463       if (intervals->at(i)->from() != interval->from()) {
1464         break;
1465       }
1466     }
1467 
1468     for (int i = idx + 1; i < intervals->length(); i++) {
1469       if (intervals->at(i) == interval) {
1470         return true;
1471       }
1472       if (intervals->at(i)->from() != interval->from()) {
1473         break;
1474       }
1475     }
1476     // We didn't find the interval in intervals that share
1477     // the same def point with it, so it's time to bailout.
1478     return false;
1479   }
1480   return false;
1481 }
1482 
1483 bool LinearScan::is_sorted(IntervalArray* intervals) {
1484   int from = -1;
1485   int i, j;
1486 
1487   int null_count = 0;
1488   for (i = 0; i < intervals->length(); i ++) {
1489     Interval* it = intervals->at(i);
1490     if (it != NULL) {
1491       if (from > it->from()) {
1492         assert(false, "");
1493         return false;
1494       }
1495       from = it->from();
1496     } else {
1497       null_count++;
1498     }
1499   }
1500 
1501   assert(null_count == 0, "Sorted intervals should not contain nulls");
1502 
1503   null_count = 0;
1504   // check that sorted list contains all non-NULL intervals from unsorted list
1505   for (i = 0; i < interval_count(); i++) {
1506     if (interval_at(i) != NULL) {
1507       assert(binary_search(intervals, interval_at(i)),
1508           "lists do not contain same intervals");
1509     } else {
1510       null_count++;











1511     }

1512   }
1513 
1514   assert(interval_count() - null_count == intervals->length(),
1515       "sorted list should contain the same amount of non-NULL intervals"
1516       " as unsorted list");
1517 
1518   return true;
1519 }
1520 #endif
1521 
1522 void LinearScan::add_to_list(Interval** first, Interval** prev, Interval* interval) {
1523   if (*prev != NULL) {
1524     (*prev)->set_next(interval);
1525   } else {
1526     *first = interval;
1527   }
1528   *prev = interval;
1529 }
1530 
1531 void LinearScan::create_unhandled_lists(Interval** list1, Interval** list2, bool (is_list1)(const Interval* i), bool (is_list2)(const Interval* i)) {
1532   assert(is_sorted(_sorted_intervals), "interval list is not sorted");
1533 
1534   *list1 = *list2 = Interval::end();
1535 
1536   Interval* list1_prev = NULL;


< prev index next >