001/*
002 *  This file is part of the Jikes RVM project (http://jikesrvm.org).
003 *
004 *  This file is licensed to You under the Eclipse Public License (EPL);
005 *  You may not use this file except in compliance with the License. You
006 *  may obtain a copy of the License at
007 *
008 *      http://www.opensource.org/licenses/eclipse-1.0.php
009 *
010 *  See the COPYRIGHT.txt file distributed with this work for information
011 *  regarding copyright ownership.
012 */
013package org.jikesrvm.compilers.opt.regalloc;
014
015import java.lang.reflect.Constructor;
016
017import org.jikesrvm.compilers.opt.OptOptions;
018import org.jikesrvm.compilers.opt.OptimizingCompilerException;
019import org.jikesrvm.compilers.opt.driver.CompilerPhase;
020import org.jikesrvm.compilers.opt.ir.IR;
021
022public final class LinearScanPhase extends CompilerPhase {
023
024  /**
025   * An object which manages spill location assignments.
026   */
027  private SpillLocationManager spillManager;
028
029  private static final Constructor<CompilerPhase> constructor = getCompilerPhaseConstructor(LinearScanPhase.class);
030
031  /**
032   * {@inheritDoc}
033   * @return compiler phase constructor
034   */
035  @Override
036  public Constructor<CompilerPhase> getClassConstructor() {
037    return constructor;
038  }
039
040  /**
041   * @return {@code true} because register allocation is required
042   */
043  @Override
044  public boolean shouldPerform(OptOptions options) {
045    return true;
046  }
047
048  @Override
049  public String getName() {
050    return "Linear Scan";
051  }
052
053  @Override
054  public boolean printingEnabled(OptOptions options, boolean before) {
055    return false;
056  }
057
058  /**
059   *  Perform the linear scan register allocation algorithm.<p>
060   *
061   *  See TOPLAS 21(5), Sept 1999, p 895-913
062   *  @param ir the IR
063   */
064  @Override
065  public void perform(IR ir) {
066    // Create the object that manages spill locations
067    spillManager = new SpillLocationManager(ir);
068
069    ActiveSet active = createEmptySetOfActiveIntervals(ir);
070
071    // Intervals sorted by increasing start point
072    for (BasicInterval b : ir.MIRInfo.linearScanState.intervals) {
073
074      MappedBasicInterval bi = (MappedBasicInterval) b;
075      CompoundInterval ci = bi.container;
076
077      active.expireOldIntervals(bi);
078
079      // If the interval does not correspond to a physical register
080      // then we process it.
081      if (!ci.getRegister().isPhysical()) {
082        // Update register allocation based on the new interval.
083        active.allocate(bi, ci);
084      } else {
085        // Mark the physical register as currently allocated.
086        ci.getRegister().allocateRegister();
087      }
088      active.add(bi);
089    }
090
091    // update the state.
092    if (active.spilledSomething()) {
093      ir.MIRInfo.linearScanState.spilledSomething = true;
094    }
095  }
096
097  private ActiveSet createEmptySetOfActiveIntervals(IR ir) {
098    SpillCostEstimator spillCost = determineSpillCostEstimator(ir);
099    ActiveSet active = new ActiveSet(ir, spillManager, spillCost);
100    ir.MIRInfo.linearScanState.active = active;
101    return active;
102  }
103
104  private SpillCostEstimator determineSpillCostEstimator(IR ir) {
105    SpillCostEstimator spillCost = null;
106    switch (ir.options.REGALLOC_SPILL_COST_ESTIMATE) {
107      case OptOptions.REGALLOC_SIMPLE_SPILL_COST:
108        spillCost = new SimpleSpillCost(ir);
109        break;
110      case OptOptions.REGALLOC_BRAINDEAD_SPILL_COST:
111        spillCost = new BrainDeadSpillCost(ir);
112        break;
113      case OptOptions.REGALLOC_BLOCK_COUNT_SPILL_COST:
114        spillCost = new BlockCountSpillCost(ir);
115        break;
116      default:
117        OptimizingCompilerException.UNREACHABLE("unsupported spill cost");
118        spillCost = null;
119    }
120    return spillCost;
121  }
122}