Mercurial > hg > truffle

comparison graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScan.java @ 19212:95a7954ea155

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Add LinearScanPhase.
author Josef Eisl <josef.eisl@jku.at>
date Fri, 06 Feb 2015 20:25:14 +0100
parents 39e99cf01468
children 1cf73c50e3dc 4d70d150944f
comparison
equal deleted inserted replaced
19211:6081b30fe164 19212:95a7954ea155
54 * An implementation of the linear scan register allocator algorithm described in <a 54 * An implementation of the linear scan register allocator algorithm described in <a
55 * href="http://doi.acm.org/10.1145/1064979.1064998" 55 * href="http://doi.acm.org/10.1145/1064979.1064998"
56 * >"Optimized Interval Splitting in a Linear Scan Register Allocator"</a> by Christian Wimmer and 56 * >"Optimized Interval Splitting in a Linear Scan Register Allocator"</a> by Christian Wimmer and
57 * Hanspeter Moessenboeck. 57 * Hanspeter Moessenboeck.
58 */ 58 */
59 public final class LinearScan { 59 final class LinearScan {
60 60
61 final TargetDescription target; 61 final TargetDescription target;
62 final LIRGenerationResult res; 62 final LIRGenerationResult res;
63 final LIR ir; 63 final LIR ir;
64 final FrameMapBuilder frameMapBuilder; 64 final FrameMapBuilder frameMapBuilder;
107 * an operand is its {@linkplain LinearScan#operandNumber(Value) operand number}. 107 * an operand is its {@linkplain LinearScan#operandNumber(Value) operand number}.
108 */ 108 */
109 public BitSet liveKill; 109 public BitSet liveKill;
110 } 110 }
111 111
112 public final BlockMap<BlockData> blockData; 112 final BlockMap<BlockData> blockData;
113 113
114 /** 114 /**
115 * List of blocks in linear-scan order. This is only correct as long as the CFG does not change. 115 * List of blocks in linear-scan order. This is only correct as long as the CFG does not change.
116 */ 116 */
117 final List<? extends AbstractBlock<?>> sortedBlocks; 117 final List<? extends AbstractBlock<?>> sortedBlocks;
159 /** 159 /**
160 * The {@linkplain #operandNumber(Value) number} of the first variable operand allocated. 160 * The {@linkplain #operandNumber(Value) number} of the first variable operand allocated.
161 */ 161 */
162 private final int firstVariableNumber; 162 private final int firstVariableNumber;
163 163
164 public LinearScan(TargetDescription target, LIRGenerationResult res) { 164 LinearScan(TargetDescription target, LIRGenerationResult res) {
165 this.target = target; 165 this.target = target;
166 this.res = res; 166 this.res = res;
167 this.ir = res.getLIR(); 167 this.ir = res.getLIR();
168 this.frameMapBuilder = res.getFrameMapBuilder(); 168 this.frameMapBuilder = res.getFrameMapBuilder();
169 this.sortedBlocks = ir.linearScanOrder(); 169 this.sortedBlocks = ir.linearScanOrder();
176 // If all allocatable registers are caller saved, then no registers are live across a call 176 // If all allocatable registers are caller saved, then no registers are live across a call
177 // site. The register allocator can save time not trying to find a register at a call site. 177 // site. The register allocator can save time not trying to find a register at a call site.
178 this.callKillsRegisters = this.frameMapBuilder.getRegisterConfig().areAllAllocatableRegistersCallerSaved(); 178 this.callKillsRegisters = this.frameMapBuilder.getRegisterConfig().areAllAllocatableRegistersCallerSaved();
179 } 179 }
180 180
181 public int getFirstLirInstructionId(AbstractBlock<?> block) { 181 int getFirstLirInstructionId(AbstractBlock<?> block) {
182 int result = ir.getLIRforBlock(block).get(0).id(); 182 int result = ir.getLIRforBlock(block).get(0).id();
183 assert result >= 0; 183 assert result >= 0;
184 return result; 184 return result;
185 } 185 }
186 186
187 public int getLastLirInstructionId(AbstractBlock<?> block) { 187 int getLastLirInstructionId(AbstractBlock<?> block) {
188 List<LIRInstruction> instructions = ir.getLIRforBlock(block); 188 List<LIRInstruction> instructions = ir.getLIRforBlock(block);
189 int result = instructions.get(instructions.size() - 1).id(); 189 int result = instructions.get(instructions.size() - 1).id();
190 assert result >= 0; 190 assert result >= 0;
191 return result; 191 return result;
192 } 192 }
218 } 218 }
219 219
220 /** 220 /**
221 * Gets the highest operand number for a register operand. This value will never change. 221 * Gets the highest operand number for a register operand. This value will never change.
222 */ 222 */
223 public int maxRegisterNumber() { 223 int maxRegisterNumber() {
224 return firstVariableNumber - 1; 224 return firstVariableNumber - 1;
225 } 225 }
226 226
227 static final IntervalPredicate IS_PRECOLORED_INTERVAL = new IntervalPredicate() { 227 static final IntervalPredicate IS_PRECOLORED_INTERVAL = new IntervalPredicate() {
228 228
1372 } 1372 }
1373 1373
1374 sortedIntervals = combinedList; 1374 sortedIntervals = combinedList;
1375 } 1375 }
1376 1376
1377 public void allocateRegisters() { 1377 void allocateRegisters() {
1378 try (Indent indent = Debug.logAndIndent("allocate registers")) { 1378 try (Indent indent = Debug.logAndIndent("allocate registers")) {
1379 Interval precoloredIntervals; 1379 Interval precoloredIntervals;
1380 Interval notPrecoloredIntervals; 1380 Interval notPrecoloredIntervals;
1381 1381
1382 Interval.Pair result = createUnhandledLists(IS_PRECOLORED_INTERVAL, IS_VARIABLE_INTERVAL); 1382 Interval.Pair result = createUnhandledLists(IS_PRECOLORED_INTERVAL, IS_VARIABLE_INTERVAL);
1729 } 1729 }
1730 } 1730 }
1731 } 1731 }
1732 } 1732 }
1733 1733
1734 public static void allocate(TargetDescription target, LIRGenerationResult res) { 1734 void allocate() {
1735 new LinearScan(target, res).allocate();
1736 }
1737
1738 private void allocate() {
1739 1735
1740 /* 1736 /*
1741 * This is the point to enable debug logging for the whole register allocation. 1737 * This is the point to enable debug logging for the whole register allocation.
1742 */ 1738 */
1743 try (Indent indent = Debug.logAndIndent("LinearScan allocate")) { 1739 try (Indent indent = Debug.logAndIndent("LinearScan allocate")) {