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