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.util.Enumeration;
016import java.util.Iterator;
017import java.util.Map;
018
019import org.jikesrvm.compilers.opt.DefUse;
020import org.jikesrvm.compilers.opt.ir.BasicBlock;
021import org.jikesrvm.compilers.opt.ir.Instruction;
022
023import static org.jikesrvm.compilers.opt.ir.Operators.SPLIT;
024
025import org.jikesrvm.compilers.opt.ir.Register;
026import org.jikesrvm.compilers.opt.ir.Unary;
027import org.jikesrvm.compilers.opt.ir.operand.Operand;
028import org.jikesrvm.compilers.opt.ir.operand.RegisterOperand;
029import org.jikesrvm.compilers.opt.liveness.LiveAnalysis;
030
031/**
032 * Utility to help coalesce registers.
033 *
034 * @see CoalesceMoves
035 */
036class Coalesce {
037
038  private final Map<Instruction, Integer> instNumbers;
039
040  Coalesce(Map<Instruction, Integer> instNumbers) {
041    this.instNumbers = instNumbers;
042  }
043
044  /**
045   * Attempt to coalesce register r2 into register r1.  If this is legal,
046   * <ul>
047   * <li> rewrite all defs and uses of r2 as defs and uses of r1
048   * <li> update the liveness information
049   * <li> update the def-use chains
050   * </ul>
051   * <strong>PRECONDITION </strong> def-use chains must be computed and valid.
052   * @param live liveness information for the IR
053   * @param r1 the register that is the target of coalescing (i.e. the one that will remain)
054   * @param r2 the register that we want to coalesce (i.e. the one that will be "removed")
055   *
056   * @return {@code true} if the transformation succeeded, {@code false} otherwise.
057   */
058  public boolean attempt(LiveAnalysis live, Register r1, Register r2) {
059
060    // make sure r1 and r2 are not simultaneously live
061    if (isLiveAtDef(r2, r1, live)) return false;
062    if (isLiveAtDef(r1, r2, live)) return false;
063
064    // Liveness is OK.  Check for SPLIT operations
065    if (split(r1, r2)) return false;
066
067    // Don't merge a register with itself
068    if (r1 == r2) return false;
069
070    // Update liveness information to reflect the merge.
071    live.merge(r1, r2);
072
073    // Merge the defs.
074    for (Enumeration<RegisterOperand> e = DefUse.defs(r2); e.hasMoreElements();) {
075      RegisterOperand def = e.nextElement();
076      DefUse.removeDef(def);
077      def.setRegister(r1);
078      DefUse.recordDef(def);
079    }
080    // Merge the uses.
081    for (Enumeration<RegisterOperand> e = DefUse.uses(r2); e.hasMoreElements();) {
082      RegisterOperand use = e.nextElement();
083      DefUse.removeUse(use);
084      use.setRegister(r1);
085      DefUse.recordUse(use);
086    }
087    return true;
088  }
089
090  /**
091   * Is register r1 live at any def of register r2?
092   * <p>
093   * <strong>PRECONDITION </strong> def-use chains must be computed and valid.
094   *
095   * <p> Note: this implementation is not efficient.  The liveness data
096   * structures must be re-designed to support this efficiently.
097   *
098   * @param r1 the register that is checked for liveness
099   * @param r2 the register whose defs are checked against liveness
100   * @param live live analysis phase
101   * @return {@code true} if the register is live at any point where the other
102   *  register is defined
103   */
104  private boolean isLiveAtDef(Register r1, Register r2, LiveAnalysis live) {
105
106    for (Iterator<LiveIntervalElement> e = live.iterateLiveIntervals(r1); e.hasNext();) {
107      LiveIntervalElement elem = e.next();
108      BasicBlock bb = elem.getBasicBlock();
109      Instruction begin = (elem.getBegin() == null) ? bb.firstInstruction() : elem.getBegin();
110      Instruction end = (elem.getEnd() == null) ? bb.lastInstruction() : elem.getEnd();
111      int low = instNumbers.get(begin);
112      int high = instNumbers.get(end);
113      for (Enumeration<RegisterOperand> defs = DefUse.defs(r2); defs.hasMoreElements();) {
114        Operand def = defs.nextElement();
115        int n = instNumbers.get(def.instruction);
116        if (n >= low && n < high) {
117          return true;
118        }
119      }
120    }
121
122    // no conflict was found.
123    return false;
124  }
125
126  /**
127   * Is there an instruction r1 = split r2 or r2 = split r1??
128   *
129   * @param r1 a register
130   * @param r2 another register
131   * @return {@code true} if there's an operation that's a split and
132   *  has occurrences of both registers
133   */
134  private boolean split(Register r1, Register r2) {
135    for (Enumeration<RegisterOperand> e = DefUse.defs(r1); e.hasMoreElements();) {
136      RegisterOperand def = e.nextElement();
137      Instruction s = def.instruction;
138      if (s.operator() == SPLIT) {
139        Operand rhs = Unary.getVal(s);
140        if (rhs.similar(def)) return true;
141      }
142    }
143    for (Enumeration<RegisterOperand> e = DefUse.defs(r2); e.hasMoreElements();) {
144      RegisterOperand def = e.nextElement();
145      Instruction s = def.instruction;
146      if (s.operator() == SPLIT) {
147        Operand rhs = Unary.getVal(s);
148        if (rhs.similar(def)) return true;
149      }
150    }
151    return false;
152  }
153}