vm/c1/c1_LinearScan.cpp

167 // ********** functions for classification of intervals
202   // fixed intervals not needed for FPU stack allocation
207   // fixed intervals never contain oops
271 // (only used for parent intervals that are created during the building phase)
278   // assign register number for precolored intervals
285 // assign a new reg_num to the interval and append it to the list of intervals
286 // (only used for child intervals that are created during register allocation)
303   //       intervals (only the very beginning of the interval must be in memory)
310 // called during building of intervals
322       assert(def_pos <= interval->spill_definition_pos(), "positions are processed in reverse order when intervals are created");
390   // collect all intervals that must be stored after their definion.
402       assert(temp->from() >= prev->from(), "intervals not sorted");
403       assert(temp->spill_definition_pos() >= prev->spill_definition_pos(), "when intervals are sorted by from, then they must also be sorted by spill_definition_pos");
408     assert(temp->spill_definition_pos() <= temp->from() + 2, "only intervals defined once at their start-pos can be optimized");
621         // fixed intervals are never live at block boundaries, so
665         // fixed intervals are never live at block boundaries, so
698         // fixed intervals are never live at block boundaries, so
815   // check that fixed intervals are not live at block boundaries
816   // (live set must be empty at fixed intervals)
862 // ********** Phase 4: build intervals
956       // also add use_kind for dead intervals
964     // also add use_kind for dead intervals
972     TRACE_LINEAR_SCAN(2, tty->print_cr("Warning: dead value %d at %d in live intervals", reg_num, def_pos));
1257   // initialize interval list with expected number of intervals
1317     // Update intervals for registers live at the end of this block;
1322       assert(number >= LIR_OprDesc::vreg_base, "fixed intervals must not be live on block bounds");
1340     // definitions of intervals are processed before uses
1406   // add the range [0, 1[ to all fixed intervals
1407   // -> the register allocator need not handle unhandled fixed intervals
1440 bool find_interval(Interval* interval, IntervalArray* intervals) {
1442   int idx = intervals->find_sorted<Interval*, interval_cmp>(interval, found);
1454     if (intervals->at(i) == interval) {
1457     if (intervals->at(i)->from() != from) {
1462   for (int i = idx + 1; i < intervals->length(); i++) {
1463     if (intervals->at(i) == interval) {
1466     if (intervals->at(i)->from() != from) {
1474 bool LinearScan::is_sorted(IntervalArray* intervals) {
1478   for (int i = 0; i < intervals->length(); i++) {
1479     Interval* it = intervals->at(i);
1488   assert(null_count == 0, "Sorted intervals should not contain nulls");
1495       assert(find_interval(interval, intervals), "Lists do not contain same intervals");
1501   assert(interval_count() - null_count == intervals->length(),
1502       "Sorted list should contain the same amount of non-NULL intervals as unsorted list");
1573   // only some intervals are swapped. So this is much faster than a complete QuickSort
1584         // the asumption that the intervals are already sorted failed,
1596   assert(is_sorted(_sorted_intervals), "intervals unsorted");
1614     // no intervals have been added during allocation, so sorted list is already up to date
1615     assert(is_sorted(_sorted_intervals), "intervals unsorted");
1619   // conventional sort-algorithm for new intervals
1639   assert(is_sorted(_sorted_intervals), "intervals unsorted");
1673 // (insert moves at edges between blocks if intervals have been split)
1825           // collect all intervals that have been split between from_block and to_block
2390   // intervals that have no oops inside need not to be processed
2403   // walk before the current operation -> intervals that start at
2412   // Iterate through active intervals
2423     // moves, any intervals which end at this instruction are included
2836         // considered in the live ranges of intervals)
2847       // The operand must be live because debug information is considered when building the intervals
3199 // (check that all intervals have a correct register and that no registers are overwritten)
3203   TRACE_LINEAR_SCAN(2, tty->print_cr("********* verifying intervals ******************************************"));
3206   TRACE_LINEAR_SCAN(2, tty->print_cr("********* verifying that no oops are in fixed intervals ****************"));
3253     // special intervals that are created in MoveResolver
3355               assert(ok, "fixed intervals should never be live across an oopmap point");
3412       assert(value != NULL, "all intervals live across block boundaries must have Value");
3506     tty->print_cr("Input-State of intervals:");
3981   // check that all intervals have been processed
4158           assert(i1->to() <= i2->from() && i1->to() < i2->to(), "intervals overlapping");
4160           assert(i2->from() < i1->from(), "intervals start at same op_id");
4161           assert(i2->to() <= i1->from() && i2->to() < i1->to(), "intervals overlapping");
4232         tty->print_cr("two valid result intervals found for op_id %d: %d and %d", op_id, result->reg_num(), tmp->reg_num());
4235         assert(false, "two valid result intervals found");
4295   assert(LinearScan::is_virtual_interval(this), "cannot access use positions for fixed intervals");
4306   assert(LinearScan::is_virtual_interval(this), "cannot access use positions for fixed intervals");
4317   assert(LinearScan::is_virtual_interval(this), "cannot access use positions for fixed intervals");
4328   assert(LinearScan::is_virtual_interval(this), "cannot access use positions for fixed intervals");
4345   // do not add use positions for precolored intervals because
4412 // (the split parent) and the intervals that are split off this interval (the split children)
4419   assert(LinearScan::is_virtual_interval(this), "cannot split fixed intervals");
4487   assert(LinearScan::is_virtual_interval(this), "cannot split fixed intervals");
4568     // need a temporary operand for fixed intervals because type() cannot be called
4772     // intervals may start at same position -> prefer fixed interval
4990       assert(list->current_intersects_at(cur) == -1, "invalid optimization: intervals intersect");
5237     // Also kick parent intervals out of register to memory when they have no use
5238     // position. This avoids short interval in register surrounded by intervals in
5406   assert(unhandled_first(fixedKind) == Interval::end(), "must not have unhandled fixed intervals because all fixed intervals have a use at position 0");
5410   // only intervals overlapping with cur are processed, non-overlapping invervals can be ignored safely
5421       assert(hint_reg != any_reg && hint_regHi == any_reg, "must be for fixed intervals");
5565   assert(unhandled_first(fixedKind) == Interval::end(), "must not have unhandled fixed intervals because all fixed intervals have a use at position 0");
5574       tty->print("      reg %d: use_pos: %d, block_pos: %d, intervals: ", i, _use_pos[i], _block_pos[i]);
5662   // fast calculation of intervals that can never get a register because the
5716 // assign same spill slot to non-intersecting intervals
5731     // combining the stack slots for intervals where spill move optimization is applied
5766   // modify intervals such that cur gets the same stack slot as register_hint
5767   // delete use positions to prevent the intervals to get a register at beginning
5802     // (this is the normal case for most intervals)
5805     // assign same spill slot to non-intersecting intervals
5815     // spilled intervals need not be move to active-list
6419     case counter_interval:        return "intervals";
6420     case counter_fixed_interval:  return "fixed intervals";