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.liveness;
014
015 import org.jikesrvm.compilers.opt.ir.Register;
016 import org.jikesrvm.compilers.opt.ir.operand.RegisterOperand;
017
018 /**
019 * This file provides a sorted set of registers.
020 */
021 public class LiveSet {
022
023 /**
024 * The beginning of the list
025 */
026 private LiveSetElement first;
027
028 /**
029 * just used for debugging
030 */
031 private static final boolean DEBUG = false;
032
033 /**
034 * Empties the set.
035 */
036 public final void clear() {
037 first = null;
038 }
039
040 /**
041 * Determines if the item passed is in the current set
042 * @param item the register to search for
043 * @return whether the item was found
044 */
045 public boolean contains(Register item) {
046 if (DEBUG) {
047 System.out.println("looking for " + item + " in " + this);
048 }
049 // simply linear search
050 LiveSetEnumerator lsEnum = enumerator();
051 while (lsEnum.hasMoreElements()) {
052 Register elem = lsEnum.nextElement().getRegister();
053 if (item == elem) {
054 if (DEBUG) {
055 System.out.println("found it, returning true");
056 }
057 return true;
058 }
059 }
060 if (DEBUG) {
061 System.out.println("didn't find it, returning false");
062 }
063 return false;
064 }
065
066 /**
067 * create a new object from the passed parameter and add it to the list
068 * @param item an object that contains the register to used in the newly
069 * created object
070 */
071 public void add(RegisterOperand item) {
072 if (DEBUG) {
073 System.out.println("\t LiveSet.add (item) called with reg " + item);
074 System.out.println("\t before add:" + this);
075 }
076 // for each item in LiveSet add it to this.set
077 if (first == null) {
078 // add at the front
079 createAndAddToCurrentList(item, null);
080 } else {
081 LiveSetElement current = first;
082 LiveSetElement prev = null;
083 // traverse the current list looking for the appropriate place
084 int itemNumber = item.getRegister().number; // cache the item's number
085 while (current != null && current.getRegister().number < itemNumber) {
086 prev = current;
087 current = current.getNext();
088 }
089 // check if there is a next item
090 if (current != null) {
091 if (current.getRegister().number == itemNumber) {
092 // already in there. Check to see if we have an Address/Reference confusion.
093 // If we do, then prefer to have the Reference in the LiveSet as that will
094 // include item in the GC maps from this program point "up"
095 if (current.getRegisterType().isWordLikeType() && item.getType().isReferenceType()) {
096 current.setRegisterOperand(item);
097 }
098 } else {
099 createAndAddToCurrentList(item, prev);
100 }
101 } else { // current == null
102 // we ran off the end of the list, but prev still has the last element
103 createAndAddToCurrentList(item, prev);
104 }
105 }
106 if (DEBUG) {
107 System.out.println("\tafter add:" + this);
108 }
109 }
110
111 /**
112 * Adds the contents of the given set to this set.
113 * @param additionList the set to add to this set
114 * @return whether any additions were made
115 */
116 public boolean add(LiveSet additionList) {
117 // for each item in LiveSet add it to this.set
118 // recording if it was an addition
119 // first make sure there is something to add
120 if (additionList == null) {
121 return false;
122 }
123 LiveSetEnumerator lsEnum = additionList.enumerator();
124 if (!lsEnum.hasMoreElements()) {
125 return false;
126 }
127 if (DEBUG) {
128 System.out.println("\t LiveSet.add called");
129 System.out.println("\t currentList: " + this);
130 System.out.println("\t additionList: " + additionList);
131 }
132
133 boolean change = false;
134 if (first == null) {
135 // current list is empty, just deep copy the passed list
136 // handle the 1st element outside the loop
137 RegisterOperand newElem = lsEnum.nextElement();
138 first = new LiveSetElement(newElem);
139 LiveSetElement existingPtr = first;
140 while (lsEnum.hasMoreElements()) {
141 newElem = lsEnum.nextElement();
142 // copy additionList and add it to first list
143 LiveSetElement elem = new LiveSetElement(newElem);
144 existingPtr.setNext(elem);
145 existingPtr = elem;
146 }
147 change = true;
148 } else {
149 // both (sorted) lists have at least 1 element
150 // walk down the lists in parallel looking for items
151 // in the addition list that aren't in the current list
152 // We don't use the enumeration here, because it is more
153 // familiar not too.
154 LiveSetElement newPtr = additionList.first;
155 LiveSetElement curPtr = first;
156 // this is always one node before "curPtr". It is used for inserts
157 LiveSetElement curPrevPtr = null;
158 while (newPtr != null && curPtr != null) {
159 if (newPtr.getRegister().number < curPtr.getRegister().number) {
160 // found one in new list that is not in current list
161 // When we add, the "prev" ptr will be updated
162 curPrevPtr = createAndAddToCurrentList(newPtr.getRegisterOperand(), curPrevPtr);
163 // don't forget to update curPtr
164 curPtr = getNextPtr(curPrevPtr);
165 newPtr = newPtr.getNext();
166 change = true;
167 } else if (newPtr.getRegister().number > curPtr.getRegister().number) {
168 // need to move up current list
169 curPrevPtr = curPtr;
170 curPtr = curPtr.getNext();
171 } else {
172 // item is already in current list, update both list ptrs
173 curPrevPtr = curPtr;
174 curPtr = curPtr.getNext();
175 newPtr = newPtr.getNext();
176 }
177 }
178 // while there is still more on the new list, add them
179 while (newPtr != null) {
180 // When we add, the "prev" ptr will be updated
181 curPrevPtr = createAndAddToCurrentList(newPtr.getRegisterOperand(), curPrevPtr);
182 // don't forget to update curPtr
183 curPtr = getNextPtr(curPrevPtr);
184 newPtr = newPtr.getNext();
185 change = true;
186 }
187 }
188 if (DEBUG) {
189 System.out.println("\tafter add:" + this + "\n Change:" + change);
190 }
191 return change;
192 }
193
194 /**
195 * Removes the contents of the passed set from the this set, i.e.,
196 * {@code this = this - removeList}
197 * @param removalList the list to remove from this set
198 */
199 public void remove(LiveSet removalList) {
200 // for each item in the LiveSet
201 // remove it from this.set
202 // Since the "removalList" set is sorted we can perform the
203 // remove in 1 pass over the "this" set.
204 // first make sure there is something to remove
205 if (removalList == null) {
206 return;
207 }
208 LiveSetEnumerator lsEnum = removalList.enumerator();
209 if (!lsEnum.hasMoreElements()) {
210 return;
211 }
212 // if current list is empty, there is nothing to remove
213 if (first == null) {
214 return;
215 }
216 if (DEBUG) {
217 System.out.println("\t LiveSet.remove called");
218 System.out.println("\t currentList: " + this);
219 System.out.println("\t removalList: " + removalList);
220 }
221 // both (sorted) lists have at least 1 element
222 // walk down the lists in parallel looking for items
223 // in the removal list that are in the current list
224 // We don't use the enumeration here, because it is more
225 // familiar not too.
226 LiveSetElement newPtr = removalList.first;
227 LiveSetElement curPtr = first;
228 // this is always one node before "curPtr". It is used for removal
229 LiveSetElement curPrevPtr = null;
230 while (newPtr != null && curPtr != null) {
231 if (newPtr.getRegister().number < curPtr.getRegister().number) {
232 // found one in removal list that is not in current list
233 // move to next on removal list
234 newPtr = newPtr.getNext();
235 } else if (newPtr.getRegister().number > curPtr.getRegister().number) {
236 // need to move up current list, found 1 on current list not on
237 // removal list
238 curPrevPtr = curPtr;
239 curPtr = curPtr.getNext();
240 } else {
241 // found one on both lists, remove it!
242 if (curPrevPtr != null) {
243 curPrevPtr.setNext(curPtr.getNext());
244 } else {
245 // removing first item on list
246 first = curPtr.getNext();
247 }
248 // move up both lists, curPrevPtr is already correct
249 curPtr = curPtr.getNext();
250 newPtr = newPtr.getNext();
251 }
252 }
253 // once we leave the loop, we may have items on 1 list, but not
254 // on the other. these can't be removed so there is nothing to
255 // be done with them
256 if (DEBUG) {
257 System.out.println("\tafter remove:" + this);
258 }
259 }
260
261 /**
262 * Removes the passed register from this set.
263 * @param item the registerOperand holding the register of interest
264 */
265 void remove(RegisterOperand item) {
266 if (DEBUG) {
267 System.out.println("\tLiveSet.remove (item) called with reg " + item);
268 }
269 // only something to do if the set is non-empty
270 if (first != null) {
271 int itemNumber = item.getRegister().number; // cache the item's number
272 // special case the first element
273 if (first.getRegister().number == itemNumber) {
274 first = first.getNext();
275 } else {
276 LiveSetElement current = first.getNext();
277 LiveSetElement prev = first;
278 // run down the current list looking for appropriate place
279 while (current != null && current.getRegister().number < itemNumber) {
280 prev = current;
281 current = current.getNext();
282 }
283 // did we find it?
284 if (current != null && current.getRegister().number == itemNumber) {
285 prev.setNext(current.getNext());
286 }
287 }
288 }
289 }
290
291 /**
292 * Is the current set empty?
293 * @return {@code true} iff the set is empty
294 */
295 public boolean isEmpty() {
296 return first == null;
297 }
298
299 /**
300 * String-i-fy the current list
301 * @return the string-i-fied version
302 */
303 @Override
304 public String toString() {
305 StringBuilder buf = new StringBuilder("");
306 if (first == null) {
307 buf.append("empty");
308 } else {
309 LiveSetElement ptr = first;
310 while (ptr != null) {
311 buf.append(ptr.getRegisterOperand()).append(" ");
312 ptr = ptr.getNext();
313 }
314 }
315 return buf.toString();
316 }
317
318 /**
319 * Returns an enumerator of the list
320 * @return an enumerator of the list
321 */
322 public final LiveSetEnumerator enumerator() {
323 return new LiveSetEnumerator(first);
324 }
325
326 /**
327 * Copy the newElement into a new object and add it to the list
328 * after prevElement. If prevElement is null, update the "start"
329 * data member by inserting at the begining.
330 * @param register the element to copy and insert
331 * @param prevElement the element on the current list to insert after
332 * or null, indicating insert at the front
333 * @return the element that is prior to the newly inserted element
334 */
335 private LiveSetElement createAndAddToCurrentList(RegisterOperand register, LiveSetElement prevElement) {
336 LiveSetElement newElement = new LiveSetElement(register);
337 if (prevElement == null) {
338 // insert at front of list
339 newElement.setNext(first);
340 first = newElement;
341 } else {
342 // insert at non-front of list
343 newElement.setNext(prevElement.getNext());
344 prevElement.setNext(newElement);
345 }
346 // new Element is now the previous element to the "curent" one
347 // which was the node that followed prevElement on entry to this method
348
349 return newElement;
350 }
351
352 /**
353 * Inspects the passed ptr, if it is nonnull it returns its next field
354 * otherwise, it returns "first"
355 * @param ptr the ptr to look at it
356 * @return the next field (if ptr is nonnull) or first (if ptr is null)
357 */
358 private LiveSetElement getNextPtr(LiveSetElement ptr) {
359 if (ptr != null) {
360 return ptr.getNext();
361 } else {
362 return first;
363 }
364 }
365
366 }
367
368
369