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     */
013    package org.jikesrvm.compilers.opt.regalloc;
014    
015    import java.util.Enumeration;
016    
017    import org.jikesrvm.compilers.opt.ir.BasicBlock;
018    import org.jikesrvm.compilers.opt.ir.IR;
019    import org.jikesrvm.compilers.opt.ir.Instruction;
020    import org.jikesrvm.compilers.opt.ir.InstructionEnumeration;
021    import org.jikesrvm.compilers.opt.ir.OperandEnumeration;
022    import org.jikesrvm.compilers.opt.ir.Register;
023    import org.jikesrvm.compilers.opt.ir.operand.MemoryOperand;
024    import org.jikesrvm.compilers.opt.ir.operand.Operand;
025    
026    /**
027     * An object that returns an estimate of the relative cost of spilling a
028     * symbolic register, based on basic block frequencies.
029     */
030    class BlockCountSpillCost extends SpillCostEstimator {
031    
032      BlockCountSpillCost(IR ir) {
033        calculate(ir);
034      }
035    
036      /**
037       * Calculate the estimated cost for each register.
038       */
039      void calculate(IR ir) {
040        final double moveFactor = ir.options.REGALLOC_SIMPLE_SPILL_COST_MOVE_FACTOR;
041        final double memoryOperandFactor = ir.options.REGALLOC_SIMPLE_SPILL_COST_MEMORY_OPERAND_FACTOR;
042        for (Enumeration<BasicBlock> blocks = ir.getBasicBlocks(); blocks.hasMoreElements();) {
043          BasicBlock bb = blocks.nextElement();
044          float freq = bb.getExecutionFrequency();
045          for (InstructionEnumeration e = bb.forwardInstrEnumerator(); e.hasMoreElements();) {
046            Instruction s = e.nextElement();
047            double factor = freq;
048    
049            if (s.isMove()) factor *= moveFactor;
050            double baseFactor = factor;
051            if (SimpleSpillCost.hasBadSizeMemoryOperand(s)) {
052              baseFactor *= memoryOperandFactor;
053            }
054    
055            // first deal with non-memory operands
056            for (OperandEnumeration e2 = s.getRootOperands(); e2.hasMoreElements();) {
057              Operand op = e2.nextElement();
058              if (op.isRegister()) {
059                Register r = op.asRegister().getRegister();
060                if (r.isSymbolic()) {
061                  update(r, baseFactor);
062                }
063              }
064            }
065            // now handle memory operands
066            factor *= memoryOperandFactor;
067            for (OperandEnumeration e2 = s.getMemoryOperands(); e2.hasMoreElements();) {
068              MemoryOperand M = (MemoryOperand) e2.nextElement();
069              if (M.base != null) {
070                Register r = M.base.getRegister();
071                if (r.isSymbolic()) {
072                  update(r, factor);
073                }
074              }
075              if (M.index != null) {
076                Register r = M.index.getRegister();
077                if (r.isSymbolic()) {
078                  update(r, factor);
079                }
080              }
081            }
082          }
083        }
084      }
085    }