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