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.ir;
014
015 import java.util.Iterator;
016 import java.util.List;
017 import java.util.ListIterator;
018 import org.jikesrvm.compilers.opt.OptimizingCompilerException;
019 import org.jikesrvm.compilers.opt.ir.operand.RegisterOperand;
020 import org.jikesrvm.compilers.opt.liveness.LiveSet;
021 import org.jikesrvm.compilers.opt.liveness.LiveSetEnumerator;
022 import org.jikesrvm.util.LinkedListRVM;
023
024 /**
025 * This class holds GC maps for various program points.
026 * This data structure is IR-based. In a later phase, this information
027 * will be used to create the final GC map (see OptMachineCodeMap.java)
028 */
029 public final class GCIRMap implements Iterable<GCIRMapElement> {
030 /**
031 * This is the list of maps.
032 * Each element on the list is an GCIRMapElement, which is a pair
033 * <ol>
034 * <li>an IR instruction (the GC point)
035 * <li>a list of RegSpillListElement, which initially hold symbolic
036 * registers that are references (these are expanded to either
037 * physical regs or spills by the register allocator)
038 * </ol>
039 */
040 private final LinkedListRVM<GCIRMapElement> list = new LinkedListRVM<GCIRMapElement>();
041
042 /**
043 * Used for class-wide debugging
044 */
045 private static final boolean DEBUG = false;
046
047 /**
048 * returns the number of GC points in this map, i.e., the number of
049 * instructions we have maps for.
050 * @return the number of GC points in this map
051 */
052 public int getNumInstructionMaps() {
053 return list.size();
054 }
055
056 /**
057 * Calculates the number of spill entries in this GCIRMap
058 * This is the total number of spills for all instructions
059 * in this map.
060 * @return the number of spill entries in this map
061 */
062 public int countNumSpillElements() {
063 // Since spill locations are not determined until after
064 // register allocation occurs, i.e., after the initial
065 // IR-based maps are created, we actually count the
066 // number of spills.
067 int count = 0;
068 for (GCIRMapElement elem : this) {
069 count += elem.countNumSpillElements();
070 }
071 return count;
072 }
073
074 /**
075 * TODO What is this method doing in this class ?? RJG
076 *
077 * This method creates a regSpillList from the passed live set.
078 * @param set the set of registers, encoded as a LiveSet object
079 * @return a list corresponding to the set passed
080 */
081 public List<RegSpillListElement> createDU(LiveSet set) {
082 if (DEBUG) {
083 System.out.println("creating a RegList for " + set);
084 }
085
086 // construct register list
087 List<RegSpillListElement> regList = new LinkedListRVM<RegSpillListElement>();
088 LiveSetEnumerator lsEnum = set.enumerator();
089 while (lsEnum.hasMoreElements()) {
090 RegisterOperand regOp = lsEnum.nextElement();
091
092 // add this register to the regList, if it is a reference
093 // and not a physcial register
094 if (regOp.getType().isReferenceType() && !regOp.getRegister().isPhysical()) {
095 RegSpillListElement elem = new RegSpillListElement(regOp.getRegister());
096 regList.add(elem);
097 }
098 }
099 return regList;
100 }
101
102 /**
103 * This method inserts a new entry into the GCIRMap
104 * @param inst the IR instruction we care about
105 * @param regList the set of symbolic registers as a list
106 */
107 public void insert(Instruction inst, List<RegSpillListElement> regList) {
108
109 // make a GCIRMapElement and put it on the big list
110 GCIRMapElement item = new GCIRMapElement(inst, regList);
111
112 if (DEBUG) {
113 System.out.println("Inserting new item: " + item);
114 }
115
116 list.add(item);
117 }
118
119 /**
120 * This method removes an entry in the GCIRMap that is specified
121 * by inst. Only one element of the list will be removed per call.
122 * If the instruction is not found in the GC Map and exeception is thrown.
123 * @param inst the IR instruction we want to remove
124 */
125 public void delete(Instruction inst) {
126
127 Iterator<GCIRMapElement> iter = list.iterator();
128 while (iter.hasNext()) {
129 GCIRMapElement ptr = iter.next();
130 if (ptr.getInstruction() == inst) {
131 iter.remove();
132 return;
133 }
134 }
135 throw new OptimizingCompilerException("GCIRMap.delete(" +
136 inst +
137 ") did not delete instruction from GC Map ");
138 }
139
140 /**
141 * This method moves an entry in the GCIRMap that is specified
142 * by inst to the end of the list. Only one element of the list will be moved per call.
143 * If the instruction is not found in the GC Map and exception is thrown.
144 * @param inst the IR instruction we want to remove
145 */
146 public void moveToEnd(Instruction inst) {
147 Iterator<GCIRMapElement> iter = list.iterator();
148 while (iter.hasNext()) {
149 GCIRMapElement newPtr = iter.next();
150 if (newPtr.getInstruction() == inst) {
151 iter.remove();
152 list.add(newPtr);
153 return;
154 }
155 }
156 throw new OptimizingCompilerException("GCIRMap.moveToEnd(" +
157 inst +
158 ") did not delete instruction from GC Map ");
159 }
160
161 /**
162 * This method inserts an entry for a "twin" instruction immediately after the
163 * original entry.
164 * If the instruction is not found in the GC Map an exception is thrown.
165 * @param inst the original IR instruction
166 * @param twin the new twin IR instruction
167 */
168 public void insertTwin(Instruction inst, Instruction twin) {
169 ListIterator<GCIRMapElement> iter = list.listIterator();
170 while (iter.hasNext()) {
171 GCIRMapElement newPtr = iter.next();
172 if (newPtr.getInstruction() == inst) {
173 iter.add(newPtr.createTwin(twin));
174 return;
175 }
176 }
177 throw new OptimizingCompilerException("GCIRMap.createTwin: " + inst + " not found");
178 }
179
180 @Override
181 public Iterator<GCIRMapElement> iterator() {
182 return list.iterator();
183 }
184
185 /**
186 * dumps the map
187 */
188 public void dump() {
189 System.out.println(toString());
190 }
191
192 /**
193 * @return string version of this object
194 */
195 @Override
196 public String toString() {
197 StringBuilder buf = new StringBuilder("");
198 if (list.isEmpty()) {
199 buf.append("empty");
200 } else {
201 for (GCIRMapElement ptr : list) {
202 buf.append(ptr);
203 }
204 }
205 return buf.toString();
206 }
207 }