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.BasicBlock;
016 import org.jikesrvm.compilers.opt.ir.Instruction;
017 import org.jikesrvm.compilers.opt.ir.Register;
018 import org.jikesrvm.compilers.opt.ir.operand.RegisterOperand;
019 import org.jikesrvm.compilers.opt.regalloc.LiveIntervalElement;
020
021 /**
022 * This class contains useful methods for managing liveIntervals.
023 */
024 final class LiveInterval {
025
026 private static final boolean DEBUG = false;
027
028 /**
029 * This method iterates over each element in the the passed live set.
030 * For each element, it checks if an existing live interval node for
031 * the basic block passed exists. If one does not exist, it creates
032 * a node with the end instruction being "inst". If one already exists
033 * no action is taken.
034 *
035 * @param set the set of registers, encoded as a LiveSet object
036 * @param block the basic block
037 * @param inst the instruction where the register's live range ends,
038 * null represents the end of the basic block
039 */
040 public static void createEndLiveRange(LiveSet set, BasicBlock block, Instruction inst) {
041 if (DEBUG) {
042 if (inst == null) {
043 System.out.println("The following are live on exit of block " + block.getNumber() + "\n" + set);
044 } else {
045 System.out.println("The following are live ending at inst\n " +
046 inst +
047 " for block " +
048 block.getNumber() +
049 "\n" +
050 set);
051 }
052 }
053
054 LiveSetEnumerator lsEnum = set.enumerator();
055 while (lsEnum.hasMoreElements()) {
056 RegisterOperand regOp = lsEnum.nextElement();
057 createEndLiveRange(regOp.getRegister(), block, inst);
058 }
059 }
060
061 /**
062 * This method checks if an existing unresolved live interval node, i.e.,
063 * one that has an end instruction, but no beginning instruction, is present
064 * for the register and basic block passed. If one does not exist, it
065 * creates a node with the end instruction being <code>inst</code>. If one
066 * already exists no action is taken.
067 *
068 * @param reg The register
069 * @param block The basic block
070 * @param inst The end instruction to use, if we have to create a neode.
071 */
072 public static void createEndLiveRange(Register reg, BasicBlock block, Instruction inst) {
073
074 if (DEBUG) {
075 System.out.println("Marking Register " +
076 reg +
077 "'s live range as ENDing at instruction\n " +
078 inst +
079 " in block #" +
080 block.getNumber());
081 printLiveIntervalList(block);
082 }
083
084 if (!containsUnresolvedElement(block, reg)) {
085 LiveIntervalElement elem = new LiveIntervalElement(reg, null, inst);
086
087 // add elem to the list for the basic block
088 block.prependLiveIntervalElement(elem);
089 }
090 }
091
092 /**
093 * This method finds the LiveInterval node for the register and basic block
094 * passed. It then sets the begin instruction to the instruction passed
095 * and moves the node to the proper place on the list block list.
096 * (The block list is sorted by "begin" instruction.
097 *
098 * @param reg the register of interest
099 * @param inst the "begin" instruction
100 * @param block the basic block of interest
101 */
102 public static void setStartLiveRange(Register reg, Instruction inst, BasicBlock block) {
103 if (DEBUG) {
104 System.out.println("Marking Register " +
105 reg +
106 "'s live range as STARTing at instruction\n " +
107 inst +
108 " in block #" +
109 block.getNumber());
110 }
111
112 LiveIntervalElement prev = null;
113 LiveIntervalElement elem = block.getFirstLiveIntervalElement();
114 while (elem != null) {
115 if (elem.getRegister() == reg && elem.getBegin() == null) {
116 break;
117 }
118
119 prev = elem;
120 elem = elem.getNext();
121 }
122
123 if (elem != null) {
124 elem.setBegin(inst);
125
126 // we want the list sorted by "begin" instruction. Since
127 // we are *assuming* that we are called in a traversal that is
128 // visiting instructions backwards, the instr passed will always
129 // be the most recent. Thus, we move "elem" to the front of the list.
130 if (prev != null) {
131 // remove elem from current position
132 prev.setNext(elem.getNext());
133
134 // add it to the begining
135 block.prependLiveIntervalElement(elem);
136 }
137
138 // if prev == null, the element is already first in the list!
139 } else {
140 // if we didn't find it, it means we have a def that is not later
141 // used, i.e., a dead assignment. This may exist because the
142 // instruction has side effects such as a function call or a PEI
143 // In this case, we create a LiveIntervalElement node with begining
144 // and ending instruction "inst"
145 LiveIntervalElement newElem = new LiveIntervalElement(reg, inst, inst);
146 block.prependLiveIntervalElement(newElem);
147 }
148
149 if (DEBUG) {
150 System.out.println("after add");
151 printLiveIntervalList(block);
152 }
153 }
154
155 /**
156 * This method finds any LiveInterval node that does not have a start
157 * instruction (it is null) and moves this node to the front of the list.
158 *
159 * @param block the basic block of interest
160 */
161 public static void moveUpwardExposedRegsToFront(BasicBlock block) {
162
163 LiveIntervalElement prev = block.getFirstLiveIntervalElement();
164 if (prev == null) {
165 return;
166 }
167
168 // The first element is already at the front, so move on to the next one
169 LiveIntervalElement elem = prev.getNext();
170
171 while (elem != null) {
172 if (elem.getBegin() == null) {
173 // remove elem from current position
174 prev.setNext(elem.getNext());
175
176 // add it to the begining, se
177 block.prependLiveIntervalElement(elem);
178
179 // the next victum is the *new* one after prev
180 elem = prev.getNext();
181 } else {
182 prev = elem;
183 elem = elem.getNext();
184 }
185 }
186 }
187
188 /**
189 * Check to see if an unresolved LiveIntervalElement node for the register
190 * passed exists for the basic block passed.
191 *
192 * @param block the block
193 * @param reg the register of interest
194 * @return <code>true</code> if it does or <code>false</code>
195 * if it does not
196 */
197 private static boolean containsUnresolvedElement(BasicBlock block, Register reg) {
198
199 if (DEBUG) {
200 System.out.println("containsUnresolvedElement called, block: " + block + " register: " + reg);
201 printLiveIntervalList(block);
202 }
203
204 for (LiveIntervalElement elem = block.getFirstLiveIntervalElement(); elem != null; elem = elem.getNext()) {
205 // if we got an element, down case it to LiveIntervalElement
206 if (elem.getRegister() == reg && elem.getBegin() == null) {
207 return true;
208 }
209 }
210 return false;
211 }
212
213 /**
214 * Print the live intervals for a block.
215 *
216 * @param block the block
217 */
218 public static void printLiveIntervalList(BasicBlock block) {
219 System.out.println("Live Interval List for " + block);
220 for (LiveIntervalElement elem = block.getFirstLiveIntervalElement(); elem != null; elem = elem.getNext()) {
221 System.out.println(" " + elem);
222 }
223 }
224 }